{"thread":{"id":"30734","subject":"[PATCH 1/4] Unindent excluded_from_list()","startedAt":"2012-06-07T07:53:34Z","lastAt":"2012-06-08T02:37:19Z","messageCount":7,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Nguyen Thai Ngoc Duy"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"193036","messageId":"1339055617-23028-1-git-send-email-pclouds@gmail.com","threadId":"30734","inReplyTo":null,"subject":"[PATCH 1/4] Unindent excluded_from_list()","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-06-07T07:53:34Z","receivedAt":"2012-06-07T07:53:34Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Return early if el->nr == 0. Unindent one more level for FNM_PATHNAME\ncode block as this block is getting complex and may need more\nindentation.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \nSigned-off-by: Junio C Hamano \n---\n nd/exclude-workaround-top-heavy updates. no changes on this patch.\n\n dir.c | 96 +++++++++++++++++++++++++++++++++----------------------------------\n 1 file changed, 48 insertions(+), 48 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex ed1510f..e756de1 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -498,56 +498,56 @@ int excluded_from_list(const char *pathname,\n {\n \tint i;\n \n-\tif (el->nr) {\n-\t\tfor (i = el->nr - 1; 0 <= i; i--) {\n-\t\t\tstruct exclude *x = el->excludes[i];\n-\t\t\tconst char *exclude = x->pattern;\n-\t\t\tint to_exclude = x->to_exclude;\n-\n-\t\t\tif (x->flags & EXC_FLAG_MUSTBEDIR) {\n-\t\t\t\tif (*dtype == DT_UNKNOWN)\n-\t\t\t\t\t*dtype = get_dtype(NULL, pathname, pathlen);\n-\t\t\t\tif (*dtype != DT_DIR)\n-\t\t\t\t\tcontinue;\n-\t\t\t}\n+\tif (!el->nr)\n+\t\treturn -1;\t/* undefined */\n+\n+\tfor (i = el->nr - 1; 0 <= i; i--) {\n+\t\tstruct exclude *x = el->excludes[i];\n+\t\tconst char *exclude = x->pattern;\n+\t\tint to_exclude = x->to_exclude;\n+\n+\t\tif (x->flags & EXC_FLAG_MUSTBEDIR) {\n+\t\t\tif (*dtype == DT_UNKNOWN)\n+\t\t\t\t*dtype = get_dtype(NULL, pathname, pathlen);\n+\t\t\tif (*dtype != DT_DIR)\n+\t\t\t\tcontinue;\n+\t\t}\n \n-\t\t\tif (x->flags & EXC_FLAG_NODIR) {\n-\t\t\t\t/* match basename */\n-\t\t\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n-\t\t\t\t\tif (!strcmp_icase(exclude, basename))\n-\t\t\t\t\t\treturn to_exclude;\n-\t\t\t\t} else if (x->flags & EXC_FLAG_ENDSWITH) {\n-\t\t\t\t\tif (x->patternlen - 1 <= pathlen &&\n-\t\t\t\t\t !strcmp_icase(exclude + 1, pathname + pathlen - x->patternlen + 1))\n-\t\t\t\t\t\treturn to_exclude;\n-\t\t\t\t} else {\n-\t\t\t\t\tif (fnmatch_icase(exclude, basename, 0) == 0)\n-\t\t\t\t\t\treturn to_exclude;\n-\t\t\t\t}\n-\t\t\t}\n-\t\t\telse {\n-\t\t\t\t/* match with FNM_PATHNAME:\n-\t\t\t\t * exclude has base (baselen long) implicitly\n-\t\t\t\t * in front of it.\n-\t\t\t\t */\n-\t\t\t\tint baselen = x->baselen;\n-\t\t\t\tif (*exclude == '/')\n-\t\t\t\t\texclude++;\n-\n-\t\t\t\tif (pathlen < baselen ||\n-\t\t\t\t (baselen && pathname[baselen-1] != '/') ||\n-\t\t\t\t strncmp_icase(pathname, x->base, baselen))\n-\t\t\t\t continue;\n-\n-\t\t\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n-\t\t\t\t\tif (!strcmp_icase(exclude, pathname + baselen))\n-\t\t\t\t\t\treturn to_exclude;\n-\t\t\t\t} else {\n-\t\t\t\t\tif (fnmatch_icase(exclude, pathname+baselen,\n-\t\t\t\t\t\t FNM_PATHNAME) == 0)\n-\t\t\t\t\t return to_exclude;\n-\t\t\t\t}\n+\t\tif (x->flags & EXC_FLAG_NODIR) {\n+\t\t\t/* match basename */\n+\t\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n+\t\t\t\tif (!strcmp_icase(exclude, basename))\n+\t\t\t\t\treturn to_exclude;\n+\t\t\t} else if (x->flags & EXC_FLAG_ENDSWITH) {\n+\t\t\t\tif (x->patternlen - 1 <= pathlen &&\n+\t\t\t\t !strcmp_icase(exclude + 1, pathname + pathlen - x->patternlen + 1))\n+\t\t\t\t\treturn to_exclude;\n+\t\t\t} else {\n+\t\t\t\tif (fnmatch_icase(exclude, basename, 0) == 0)\n+\t\t\t\t\treturn to_exclude;\n \t\t\t}\n+\t\t\tcontinue;\n+\t\t}\n+\n+\n+\t\t/* match with FNM_PATHNAME:\n+\t\t * exclude has base (baselen long) implicitly in front of it.\n+\t\t */\n+\t\tif (*exclude == '/')\n+\t\t\texclude++;\n+\n+\t\tif (pathlen < x->baselen ||\n+\t\t (x->baselen && pathname[x->baselen-1] != '/') ||\n+\t\t strncmp_icase(pathname, x->base, x->baselen))\n+\t\t\tcontinue;\n+\n+\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n+\t\t\tif (!strcmp_icase(exclude, pathname + x->baselen))\n+\t\t\t\treturn to_exclude;\n+\t\t} else {\n+\t\t\tif (fnmatch_icase(exclude, pathname+x->baselen,\n+\t\t\t\t\t FNM_PATHNAME) == 0)\n+\t\t\t\treturn to_exclude;\n \t\t}\n \t}\n \treturn -1; /* undecided */\n-- \n1.7.11.rc1.185.g281ad67\n"},{"id":"193037","messageId":"1339055617-23028-2-git-send-email-pclouds@gmail.com","threadId":"30734","inReplyTo":"1339055617-23028-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/4] dir.c: get rid of the wildcard symbol set in no_wildcard()","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-06-07T07:53:35Z","receivedAt":"2012-06-07T07:53:35Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Elsewhere in this file is_glob_special() is also used to check for\nwildcards, which is defined in ctype. Make no_wildcard() also use this\nfunction (indirectly via simple_length())\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 32 ++++++++++++++++----------------\n 1 file changed, 16 insertions(+), 16 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex e756de1..bbf958c 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -288,9 +288,24 @@ int match_pathspec_depth(const struct pathspec *ps,\n \treturn retval;\n }\n \n+/*\n+ * Return the length of the \"simple\" part of a path match limiter.\n+ */\n+static int simple_length(const char *match)\n+{\n+\tint len = -1;\n+\n+\tfor (;;) {\n+\t\tunsigned char c = *match++;\n+\t\tlen++;\n+\t\tif (c == '\\0' || is_glob_special(c))\n+\t\t\treturn len;\n+\t}\n+}\n+\n static int no_wildcard(const char *string)\n {\n-\treturn string[strcspn(string, \"*?[{\\\\\")] == '\\0';\n+\treturn string[simple_length(string)] == '\\0';\n }\n \n void add_exclude(const char *string, const char *base,\n@@ -997,21 +1012,6 @@ static int cmp_name(const void *p1, const void *p2)\n \t\t\t\t e2->name, e2->len);\n }\n \n-/*\n- * Return the length of the \"simple\" part of a path match limiter.\n- */\n-static int simple_length(const char *match)\n-{\n-\tint len = -1;\n-\n-\tfor (;;) {\n-\t\tunsigned char c = *match++;\n-\t\tlen++;\n-\t\tif (c == '\\0' || is_glob_special(c))\n-\t\t\treturn len;\n-\t}\n-}\n-\n static struct path_simplify *create_simplify(const char **pathspec)\n {\n \tint nr, alloc = 0;\n-- \n1.7.11.rc1.185.g281ad67\n"},{"id":"193038","messageId":"1339055617-23028-3-git-send-email-pclouds@gmail.com","threadId":"30734","inReplyTo":"1339055617-23028-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 3/4] exclude: do strcmp as much as possible before fnmatch","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-06-07T07:53:36Z","receivedAt":"2012-06-07T07:53:36Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"this also avoids calling fnmatch() if the non-wildcard prefix is\nlonger than basename\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n Fixed the global \"wildcards\" string thing by using simple_length().\n\n dir.c | 37 ++++++++++++++++++++++++-------------\n dir.h | 2 +-\n 2 files changed, 25 insertions(+), 14 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex bbf958c..94fe9f8 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -341,8 +341,7 @@ void add_exclude(const char *string, const char *base,\n \tx->flags = flags;\n \tif (!strchr(string, '/'))\n \t\tx->flags |= EXC_FLAG_NODIR;\n-\tif (no_wildcard(string))\n-\t\tx->flags |= EXC_FLAG_NOWILDCARD;\n+\tx->nowildcardlen = simple_length(string);\n \tif (*string == '*' && no_wildcard(string+1))\n \t\tx->flags |= EXC_FLAG_ENDSWITH;\n \tALLOC_GROW(which->excludes, which->nr + 1, which->alloc);\n@@ -518,8 +517,9 @@ int excluded_from_list(const char *pathname,\n \n \tfor (i = el->nr - 1; 0 <= i; i--) {\n \t\tstruct exclude *x = el->excludes[i];\n-\t\tconst char *exclude = x->pattern;\n+\t\tconst char *name, *exclude = x->pattern;\n \t\tint to_exclude = x->to_exclude;\n+\t\tint namelen, prefix = x->nowildcardlen;\n \n \t\tif (x->flags & EXC_FLAG_MUSTBEDIR) {\n \t\t\tif (*dtype == DT_UNKNOWN)\n@@ -530,7 +530,7 @@ int excluded_from_list(const char *pathname,\n \n \t\tif (x->flags & EXC_FLAG_NODIR) {\n \t\t\t/* match basename */\n-\t\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n+\t\t\tif (prefix == x->patternlen) {\n \t\t\t\tif (!strcmp_icase(exclude, basename))\n \t\t\t\t\treturn to_exclude;\n \t\t\t} else if (x->flags & EXC_FLAG_ENDSWITH) {\n@@ -544,26 +544,37 @@ int excluded_from_list(const char *pathname,\n \t\t\tcontinue;\n \t\t}\n \n-\n \t\t/* match with FNM_PATHNAME:\n \t\t * exclude has base (baselen long) implicitly in front of it.\n \t\t */\n-\t\tif (*exclude == '/')\n+\t\tif (*exclude == '/') {\n \t\t\texclude++;\n+\t\t\tprefix--;\n+\t\t}\n \n \t\tif (pathlen < x->baselen ||\n \t\t (x->baselen && pathname[x->baselen-1] != '/') ||\n \t\t strncmp_icase(pathname, x->base, x->baselen))\n \t\t\tcontinue;\n \n-\t\tif (x->flags & EXC_FLAG_NOWILDCARD) {\n-\t\t\tif (!strcmp_icase(exclude, pathname + x->baselen))\n-\t\t\t\treturn to_exclude;\n-\t\t} else {\n-\t\t\tif (fnmatch_icase(exclude, pathname+x->baselen,\n-\t\t\t\t\t FNM_PATHNAME) == 0)\n-\t\t\t\treturn to_exclude;\n+\t\tnamelen = x->baselen ? pathlen - x->baselen : pathlen;\n+\t\tname = pathname + pathlen - namelen;\n+\n+\t\t/* if the non-wildcard part is longer than the\n+\t\t remaining pathname, surely it cannot match */\n+\t\tif (prefix > namelen)\n+\t\t\tcontinue;\n+\n+\t\tif (prefix) {\n+\t\t\tif (strncmp_icase(exclude, name, prefix))\n+\t\t\t\tcontinue;\n+\t\t\texclude += prefix;\n+\t\t\tname += prefix;\n+\t\t\tnamelen -= prefix;\n \t\t}\n+\n+\t\tif (!namelen || !fnmatch_icase(exclude, name, FNM_PATHNAME))\n+\t\t\treturn to_exclude;\n \t}\n \treturn -1; /* undecided */\n }\ndiff --git a/dir.h b/dir.h\nindex 58b6fc7..39fc145 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -7,7 +7,6 @@ struct dir_entry {\n };\n \n #define EXC_FLAG_NODIR 1\n-#define EXC_FLAG_NOWILDCARD 2\n #define EXC_FLAG_ENDSWITH 4\n #define EXC_FLAG_MUSTBEDIR 8\n \n@@ -17,6 +16,7 @@ struct exclude_list {\n \tstruct exclude {\n \t\tconst char *pattern;\n \t\tint patternlen;\n+\t\tint nowildcardlen;\n \t\tconst char *base;\n \t\tint baselen;\n \t\tint to_exclude;\n-- \n1.7.11.rc1.185.g281ad67\n"},{"id":"193039","messageId":"1339055617-23028-4-git-send-email-pclouds@gmail.com","threadId":"30734","inReplyTo":"1339055617-23028-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 4/4] exclude: reuse last basename comparison","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-06-07T07:53:37Z","receivedAt":"2012-06-07T07:53:37Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"If two consecutive patterns share the same \"base\" and we just compared\nbase against pathname last time, we can just reuse the last comparison\nresult.\n\nThis optmization is made with read_directory() in mind. Notice that\nall exclude patterns share the same \"base\" pointer, which is basebuf[]\nfrom \"struct dir\" (given indirectly by prep_exclude()) and patterns\nfrom the same .gitignore will stay in the same order. This opens an\nopportunity for this optimization when there are a lot of patterns in\nsubdirectories-with-long-path-name/.gitignore.\n\nOther users of excluded_from_list() unlikely take advantage of this,\nunless add_excludes() learns to pre-compare two consecutive bases and\nsave the result, so excluded_from_list() can perform a cheap \"are\nthese two bases the same\" check.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n I haven't put more thought/work on optimizing the big top .gitignore\n case yet. But something like this is probably worth doing anyway.\n Pathspec might use the same optimization. If a user does (notice no\n quotes)\n \n git something long/path/to/here/*.[ch]\n\n we would need to compare \"long/path/to/here\" all over again (I\n haven't checked the code though).\n\n dir.c | 23 ++++++++++++++++++++---\n 1 file changed, 20 insertions(+), 3 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 94fe9f8..2964076 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -511,6 +511,7 @@ int excluded_from_list(const char *pathname,\n \t\t struct exclude_list *el)\n {\n \tint i;\n+\tint last_basecmp = el->nr, basecmp_result;\n \n \tif (!el->nr)\n \t\treturn -1;\t/* undefined */\n@@ -552,9 +553,25 @@ int excluded_from_list(const char *pathname,\n \t\t\tprefix--;\n \t\t}\n \n-\t\tif (pathlen < x->baselen ||\n-\t\t (x->baselen && pathname[x->baselen-1] != '/') ||\n-\t\t strncmp_icase(pathname, x->base, x->baselen))\n+\t\tif (i < el->nr - 1 &&\n+\t\t last_basecmp == i + 1 &&\n+\t\t x->base == el->excludes[last_basecmp]->base &&\n+\t\t x->baselen == el->excludes[last_basecmp]->baselen)\n+\t\t\t/*\n+\t\t\t * we have the same \"base\" as last time and\n+\t\t\t * last time we came here too (i.e. no break\n+\t\t\t * or continue from the above code), reuse\n+\t\t\t * basecmp_result\n+\t\t\t */\n+\t\t\t;\n+\t\telse\n+\t\t\t/* anything other than zero is ok, we don't\n+\t\t\t really care about the sorting order */\n+\t\t\tbasecmp_result = pathlen < x->baselen ||\n+\t\t\t\t(x->baselen && pathname[x->baselen - 1] != '/') ||\n+\t\t\t\tstrncmp_icase(pathname, x->base, x->baselen);\n+\t\tlast_basecmp = i;\n+\t\tif (basecmp_result)\n \t\t\tcontinue;\n \n \t\tnamelen = x->baselen ? pathlen - x->baselen : pathlen;\n-- \n1.7.11.rc1.185.g281ad67\n"},{"id":"193094","messageId":"7vipf3geo2.fsf@alter.siamese.dyndns.org","threadId":"30734","inReplyTo":"1339055617-23028-4-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 4/4] exclude: reuse last basename comparison","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-06-07T18:28:13Z","receivedAt":"2012-06-07T18:28:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy writes:\n\n> If two consecutive patterns share the same \"base\" and we just compared\n> base against pathname last time, we can just reuse the last comparison\n> result.\n>\n> This optmization is made with read_directory() in mind. Notice that\n\ns/optm/optim/; just in case you need to reroll this one later.\n"},{"id":"193095","messageId":"7vd35bge2u.fsf@alter.siamese.dyndns.org","threadId":"30734","inReplyTo":"1339055617-23028-4-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 4/4] exclude: reuse last basename comparison","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-06-07T18:40:57Z","receivedAt":"2012-06-07T18:40:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy writes:\n\n> diff --git a/dir.c b/dir.c\n> index 94fe9f8..2964076 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -511,6 +511,7 @@ int excluded_from_list(const char *pathname,\n> \t\t struct exclude_list *el)\n> {\n> \tint i;\n> +\tint last_basecmp = el->nr, basecmp_result;\n\nGcc complains that basecmp_result may be used without initialized in\nthis function.\n"},{"id":"193122","messageId":"CACsJy8BChqegyvo8Oqj6Rk+kWR245sSngWeQcBZXKWLgTw9t_w@mail.gmail.com","threadId":"30734","inReplyTo":"7vd35bge2u.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 4/4] exclude: reuse last basename comparison","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-06-08T02:37:19Z","receivedAt":"2012-06-08T02:37:19Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Jun 8, 2012 at 1:40 AM, Junio C Hamano wrote:\n> Nguyễn Thái Ngọc Duy writes:\n>\n>> diff --git a/dir.c b/dir.c\n>> index 94fe9f8..2964076 100644\n>> --- a/dir.c\n>> +++ b/dir.c\n>> @@ -511,6 +511,7 @@ int excluded_from_list(const char *pathname,\n>>                      struct exclude_list *el)\n>>  {\n>>       int i;\n>> +     int last_basecmp = el->nr, basecmp_result;\n>\n> Gcc complains that basecmp_result may be used without initialized in\n> this function.\n\nI'm pretty sure it's fault positive.\n-- \nDuy\n"}]}