# [PATCH 1/4] Unindent excluded_from_list() 7 messages from 2012-06-07 to 2012-06-08. Participants: Nguyễn Thái Ngọc Duy, Junio C Hamano, Nguyen Thai Ngoc Duy. Thread: https://gitlist.dev/t/30734 ## Nguyễn Thái Ngọc Duy, 2012-06-07 07:53 Subject: [PATCH 1/4] Unindent excluded_from_list() Message-ID: <1339055617-23028-1-git-send-email-pclouds@gmail.com> URL: https://gitlist.dev/e/1339055617-23028-1-git-send-email-pclouds%40gmail.com ``` Return early if el->nr == 0. Unindent one more level for FNM_PATHNAME code block as this block is getting complex and may need more indentation. Signed-off-by: Nguyễn Thái Ngọc Duy Signed-off-by: Junio C Hamano --- nd/exclude-workaround-top-heavy updates. no changes on this patch. dir.c | 96 +++++++++++++++++++++++++++++++++---------------------------------- 1 file changed, 48 insertions(+), 48 deletions(-) diff --git a/dir.c b/dir.c index ed1510f..e756de1 100644 --- a/dir.c +++ b/dir.c @@ -498,56 +498,56 @@ int excluded_from_list(const char *pathname, { int i; - if (el->nr) { - for (i = el->nr - 1; 0 <= i; i--) { - struct exclude *x = el->excludes[i]; - const char *exclude = x->pattern; - int to_exclude = x->to_exclude; - - if (x->flags & EXC_FLAG_MUSTBEDIR) { - if (*dtype == DT_UNKNOWN) - *dtype = get_dtype(NULL, pathname, pathlen); - if (*dtype != DT_DIR) - continue; - } + if (!el->nr) + return -1; /* undefined */ + + for (i = el->nr - 1; 0 <= i; i--) { + struct exclude *x = el->excludes[i]; + const char *exclude = x->pattern; + int to_exclude = x->to_exclude; + + if (x->flags & EXC_FLAG_MUSTBEDIR) { + if (*dtype == DT_UNKNOWN) + *dtype = get_dtype(NULL, pathname, pathlen); + if (*dtype != DT_DIR) + continue; + } - if (x->flags & EXC_FLAG_NODIR) { - /* match basename */ - if (x->flags & EXC_FLAG_NOWILDCARD) { - if (!strcmp_icase(exclude, basename)) - return to_exclude; - } else if (x->flags & EXC_FLAG_ENDSWITH) { - if (x->patternlen - 1 <= pathlen && - !strcmp_icase(exclude + 1, pathname + pathlen - x->patternlen + 1)) - return to_exclude; - } else { - if (fnmatch_icase(exclude, basename, 0) == 0) - return to_exclude; - } - } - else { - /* match with FNM_PATHNAME: - * exclude has base (baselen long) implicitly - * in front of it. - */ - int baselen = x->baselen; - if (*exclude == '/') - exclude++; - - if (pathlen < baselen || - (baselen && pathname[baselen-1] != '/') || - strncmp_icase(pathname, x->base, baselen)) - continue; - - if (x->flags & EXC_FLAG_NOWILDCARD) { - if (!strcmp_icase(exclude, pathname + baselen)) - return to_exclude; - } else { - if (fnmatch_icase(exclude, pathname+baselen, - FNM_PATHNAME) == 0) - return to_exclude; - } + if (x->flags & EXC_FLAG_NODIR) { + /* match basename */ + if (x->flags & EXC_FLAG_NOWILDCARD) { + if (!strcmp_icase(exclude, basename)) + return to_exclude; + } else if (x->flags & EXC_FLAG_ENDSWITH) { + if (x->patternlen - 1 <= pathlen && + !strcmp_icase(exclude + 1, pathname + pathlen - x->patternlen + 1)) + return to_exclude; + } else { + if (fnmatch_icase(exclude, basename, 0) == 0) + return to_exclude; } + continue; + } + + + /* match with FNM_PATHNAME: + * exclude has base (baselen long) implicitly in front of it. + */ + if (*exclude == '/') + exclude++; + + if (pathlen < x->baselen || + (x->baselen && pathname[x->baselen-1] != '/') || + strncmp_icase(pathname, x->base, x->baselen)) + continue; + + if (x->flags & EXC_FLAG_NOWILDCARD) { + if (!strcmp_icase(exclude, pathname + x->baselen)) + return to_exclude; + } else { + if (fnmatch_icase(exclude, pathname+x->baselen, + FNM_PATHNAME) == 0) + return to_exclude; } } return -1; /* undecided */ -- 1.7.11.rc1.185.g281ad67 ``` ## Nguyễn Thái Ngọc Duy, 2012-06-07 07:53 Subject: [PATCH 2/4] dir.c: get rid of the wildcard symbol set in no_wildcard() Message-ID: <1339055617-23028-2-git-send-email-pclouds@gmail.com> URL: https://gitlist.dev/e/1339055617-23028-2-git-send-email-pclouds%40gmail.com In-Reply-To: <1339055617-23028-1-git-send-email-pclouds@gmail.com> ``` Elsewhere in this file is_glob_special() is also used to check for wildcards, which is defined in ctype. Make no_wildcard() also use this function (indirectly via simple_length()) Signed-off-by: Nguyễn Thái Ngọc Duy --- dir.c | 32 ++++++++++++++++---------------- 1 file changed, 16 insertions(+), 16 deletions(-) diff --git a/dir.c b/dir.c index e756de1..bbf958c 100644 --- a/dir.c +++ b/dir.c @@ -288,9 +288,24 @@ int match_pathspec_depth(const struct pathspec *ps, return retval; } +/* + * Return the length of the "simple" part of a path match limiter. + */ +static int simple_length(const char *match) +{ + int len = -1; + + for (;;) { + unsigned char c = *match++; + len++; + if (c == '\0' || is_glob_special(c)) + return len; + } +} + static int no_wildcard(const char *string) { - return string[strcspn(string, "*?[{\\")] == '\0'; + return string[simple_length(string)] == '\0'; } void add_exclude(const char *string, const char *base, @@ -997,21 +1012,6 @@ static int cmp_name(const void *p1, const void *p2) e2->name, e2->len); } -/* - * Return the length of the "simple" part of a path match limiter. - */ -static int simple_length(const char *match) -{ - int len = -1; - - for (;;) { - unsigned char c = *match++; - len++; - if (c == '\0' || is_glob_special(c)) - return len; - } -} - static struct path_simplify *create_simplify(const char **pathspec) { int nr, alloc = 0; -- 1.7.11.rc1.185.g281ad67 ``` ## Nguyễn Thái Ngọc Duy, 2012-06-07 07:53 Subject: [PATCH 3/4] exclude: do strcmp as much as possible before fnmatch Message-ID: <1339055617-23028-3-git-send-email-pclouds@gmail.com> URL: https://gitlist.dev/e/1339055617-23028-3-git-send-email-pclouds%40gmail.com In-Reply-To: <1339055617-23028-1-git-send-email-pclouds@gmail.com> ``` this also avoids calling fnmatch() if the non-wildcard prefix is longer than basename Signed-off-by: Nguyễn Thái Ngọc Duy --- Fixed the global "wildcards" string thing by using simple_length(). dir.c | 37 ++++++++++++++++++++++++------------- dir.h | 2 +- 2 files changed, 25 insertions(+), 14 deletions(-) diff --git a/dir.c b/dir.c index bbf958c..94fe9f8 100644 --- a/dir.c +++ b/dir.c @@ -341,8 +341,7 @@ void add_exclude(const char *string, const char *base, x->flags = flags; if (!strchr(string, '/')) x->flags |= EXC_FLAG_NODIR; - if (no_wildcard(string)) - x->flags |= EXC_FLAG_NOWILDCARD; + x->nowildcardlen = simple_length(string); if (*string == '*' && no_wildcard(string+1)) x->flags |= EXC_FLAG_ENDSWITH; ALLOC_GROW(which->excludes, which->nr + 1, which->alloc); @@ -518,8 +517,9 @@ int excluded_from_list(const char *pathname, for (i = el->nr - 1; 0 <= i; i--) { struct exclude *x = el->excludes[i]; - const char *exclude = x->pattern; + const char *name, *exclude = x->pattern; int to_exclude = x->to_exclude; + int namelen, prefix = x->nowildcardlen; if (x->flags & EXC_FLAG_MUSTBEDIR) { if (*dtype == DT_UNKNOWN) @@ -530,7 +530,7 @@ int excluded_from_list(const char *pathname, if (x->flags & EXC_FLAG_NODIR) { /* match basename */ - if (x->flags & EXC_FLAG_NOWILDCARD) { + if (prefix == x->patternlen) { if (!strcmp_icase(exclude, basename)) return to_exclude; } else if (x->flags & EXC_FLAG_ENDSWITH) { @@ -544,26 +544,37 @@ int excluded_from_list(const char *pathname, continue; } - /* match with FNM_PATHNAME: * exclude has base (baselen long) implicitly in front of it. */ - if (*exclude == '/') + if (*exclude == '/') { exclude++; + prefix--; + } if (pathlen < x->baselen || (x->baselen && pathname[x->baselen-1] != '/') || strncmp_icase(pathname, x->base, x->baselen)) continue; - if (x->flags & EXC_FLAG_NOWILDCARD) { - if (!strcmp_icase(exclude, pathname + x->baselen)) - return to_exclude; - } else { - if (fnmatch_icase(exclude, pathname+x->baselen, - FNM_PATHNAME) == 0) - return to_exclude; + namelen = x->baselen ? pathlen - x->baselen : pathlen; + name = pathname + pathlen - namelen; + + /* if the non-wildcard part is longer than the + remaining pathname, surely it cannot match */ + if (prefix > namelen) + continue; + + if (prefix) { + if (strncmp_icase(exclude, name, prefix)) + continue; + exclude += prefix; + name += prefix; + namelen -= prefix; } + + if (!namelen || !fnmatch_icase(exclude, name, FNM_PATHNAME)) + return to_exclude; } return -1; /* undecided */ } diff --git a/dir.h b/dir.h index 58b6fc7..39fc145 100644 --- a/dir.h +++ b/dir.h @@ -7,7 +7,6 @@ struct dir_entry { }; #define EXC_FLAG_NODIR 1 -#define EXC_FLAG_NOWILDCARD 2 #define EXC_FLAG_ENDSWITH 4 #define EXC_FLAG_MUSTBEDIR 8 @@ -17,6 +16,7 @@ struct exclude_list { struct exclude { const char *pattern; int patternlen; + int nowildcardlen; const char *base; int baselen; int to_exclude; -- 1.7.11.rc1.185.g281ad67 ``` ## Nguyễn Thái Ngọc Duy, 2012-06-07 07:53 Subject: [PATCH 4/4] exclude: reuse last basename comparison Message-ID: <1339055617-23028-4-git-send-email-pclouds@gmail.com> URL: https://gitlist.dev/e/1339055617-23028-4-git-send-email-pclouds%40gmail.com In-Reply-To: <1339055617-23028-1-git-send-email-pclouds@gmail.com> ``` If two consecutive patterns share the same "base" and we just compared base against pathname last time, we can just reuse the last comparison result. This optmization is made with read_directory() in mind. Notice that all exclude patterns share the same "base" pointer, which is basebuf[] from "struct dir" (given indirectly by prep_exclude()) and patterns from the same .gitignore will stay in the same order. This opens an opportunity for this optimization when there are a lot of patterns in subdirectories-with-long-path-name/.gitignore. Other users of excluded_from_list() unlikely take advantage of this, unless add_excludes() learns to pre-compare two consecutive bases and save the result, so excluded_from_list() can perform a cheap "are these two bases the same" check. Signed-off-by: Nguyễn Thái Ngọc Duy --- I haven't put more thought/work on optimizing the big top .gitignore case yet. But something like this is probably worth doing anyway. Pathspec might use the same optimization. If a user does (notice no quotes) git something long/path/to/here/*.[ch] we would need to compare "long/path/to/here" all over again (I haven't checked the code though). dir.c | 23 ++++++++++++++++++++--- 1 file changed, 20 insertions(+), 3 deletions(-) diff --git a/dir.c b/dir.c index 94fe9f8..2964076 100644 --- a/dir.c +++ b/dir.c @@ -511,6 +511,7 @@ int excluded_from_list(const char *pathname, struct exclude_list *el) { int i; + int last_basecmp = el->nr, basecmp_result; if (!el->nr) return -1; /* undefined */ @@ -552,9 +553,25 @@ int excluded_from_list(const char *pathname, prefix--; } - if (pathlen < x->baselen || - (x->baselen && pathname[x->baselen-1] != '/') || - strncmp_icase(pathname, x->base, x->baselen)) + if (i < el->nr - 1 && + last_basecmp == i + 1 && + x->base == el->excludes[last_basecmp]->base && + x->baselen == el->excludes[last_basecmp]->baselen) + /* + * we have the same "base" as last time and + * last time we came here too (i.e. no break + * or continue from the above code), reuse + * basecmp_result + */ + ; + else + /* anything other than zero is ok, we don't + really care about the sorting order */ + basecmp_result = pathlen < x->baselen || + (x->baselen && pathname[x->baselen - 1] != '/') || + strncmp_icase(pathname, x->base, x->baselen); + last_basecmp = i; + if (basecmp_result) continue; namelen = x->baselen ? pathlen - x->baselen : pathlen; -- 1.7.11.rc1.185.g281ad67 ``` ## Junio C Hamano, 2012-06-07 18:28 Subject: Re: [PATCH 4/4] exclude: reuse last basename comparison Message-ID: <7vipf3geo2.fsf@alter.siamese.dyndns.org> URL: https://gitlist.dev/e/7vipf3geo2.fsf%40alter.siamese.dyndns.org In-Reply-To: <1339055617-23028-4-git-send-email-pclouds@gmail.com> ``` Nguyễn Thái Ngọc Duy writes: > If two consecutive patterns share the same "base" and we just compared > base against pathname last time, we can just reuse the last comparison > result. > > This optmization is made with read_directory() in mind. Notice that s/optm/optim/; just in case you need to reroll this one later. ``` ## Junio C Hamano, 2012-06-07 18:40 Subject: Re: [PATCH 4/4] exclude: reuse last basename comparison Message-ID: <7vd35bge2u.fsf@alter.siamese.dyndns.org> URL: https://gitlist.dev/e/7vd35bge2u.fsf%40alter.siamese.dyndns.org In-Reply-To: <1339055617-23028-4-git-send-email-pclouds@gmail.com> ``` Nguyễn Thái Ngọc Duy writes: > diff --git a/dir.c b/dir.c > index 94fe9f8..2964076 100644 > --- a/dir.c > +++ b/dir.c > @@ -511,6 +511,7 @@ int excluded_from_list(const char *pathname, > struct exclude_list *el) > { > int i; > + int last_basecmp = el->nr, basecmp_result; Gcc complains that basecmp_result may be used without initialized in this function. ``` ## Nguyen Thai Ngoc Duy, 2012-06-08 02:37 Subject: Re: [PATCH 4/4] exclude: reuse last basename comparison Message-ID: URL: https://gitlist.dev/e/CACsJy8BChqegyvo8Oqj6Rk%2BkWR245sSngWeQcBZXKWLgTw9t_w%40mail.gmail.com In-Reply-To: <7vd35bge2u.fsf@alter.siamese.dyndns.org> ``` On Fri, Jun 8, 2012 at 1:40 AM, Junio C Hamano wrote: > Nguyễn Thái Ngọc Duy writes: > >> diff --git a/dir.c b/dir.c >> index 94fe9f8..2964076 100644 >> --- a/dir.c >> +++ b/dir.c >> @@ -511,6 +511,7 @@ int excluded_from_list(const char *pathname, >>                      struct exclude_list *el) >>  { >>       int i; >> +     int last_basecmp = el->nr, basecmp_result; > > Gcc complains that basecmp_result may be used without initialized in > this function. I'm pretty sure it's fault positive. -- Duy ```