{"thread":{"id":"32440","subject":"[PATCH 1/8] compat/fnmatch: respect NO_FNMATCH* even on glibc","startedAt":"2012-12-22T07:57:00Z","lastAt":"2012-12-28T07:15:41Z","messageCount":14,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Nguyen Thai Ngoc Duy"],"isPatch":true,"patchVersion":1,"patchTotal":8},"messages":[{"id":"205390","messageId":"1356163028-29967-1-git-send-email-pclouds@gmail.com","threadId":"32440","inReplyTo":null,"subject":"[PATCH 0/8] fnmatch replacement step 1","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-22T07:57:00Z","receivedAt":"2012-12-22T07:57:00Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This series makes wildmatch compatible with fnmatch, at least for\nFNM_CASEFOLD and FNM_PATHNAME. This makes it possible to use wildmatch\nas a fnmatch replacement. The replacement is optional and turned on via\nUSE_WILDMATCH.\n\nStep 2 would be turn USE_WILDMATCH by default and remove\ncompat/fnmatch. We can leave it for now until we are certain we don't\nintroduce any kind of regressions.\n\nMeasurement is performed to see how wildmatch compete with\nfnmatch(es). I was surprised that my glibc version is even slower than\ncompat/fnmatch. For more details, see 5/8. wildmatch is faster (about\n20%) in most cases. It is slower in '*/*/*' tests both with and without\nFNM_PATHNAME. 7/8 and 8/8 fix that, making wildmatch fastest in all\n(tested) cases.\n\nI'd appreciate if people test it with more patterns (both weird and\ncommonly used) against different fnmatch versions and turn on\nUSE_WILDMATCH to see if we need to fix something else, both correctness\nand performance. So far I'm convinced that the replacement is a good\nthing to do.\n\nThe series requires nd/wildmatch, obviously.\n\nNguyễn Thái Ngọc Duy (8):\n compat/fnmatch: respect NO_FNMATCH* even on glibc\n wildmatch: rename constants and update prototype\n wildmatch: make dowild() take arbitrary flags\n wildmatch: support \"no FNM_PATHNAME\" mode\n test-wildmatch: add \"perf\" command to compare wildmatch and fnmatch\n Makefile: add USE_WILDMATCH to use wildmatch as fnmatch\n wildmatch: make a special case for \"*/\" with FNM_PATHNAME\n wildmatch: advance faster in + patterns\n\n Makefile | 6 +++\n compat/fnmatch/fnmatch.c | 3 +-\n dir.c | 3 +-\n git-compat-util.h | 13 +++++\n t/t3070-wildmatch.sh | 27 ++++++++++\n test-wildmatch.c | 82 +++++++++++++++++++++++++++-\n wildmatch.c | 137 +++++++++++++++++++++++++++++------------------\n wildmatch.h | 23 +++++---\n 8 files changed, 232 insertions(+), 62 deletions(-)\n\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"205389","messageId":"1356163028-29967-2-git-send-email-pclouds@gmail.com","threadId":"32440","inReplyTo":"1356163028-29967-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 1/8] compat/fnmatch: respect NO_FNMATCH* even on glibc","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-22T07:57:01Z","receivedAt":"2012-12-22T07:57:01Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n compat/fnmatch/fnmatch.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/compat/fnmatch/fnmatch.c b/compat/fnmatch/fnmatch.c\nindex 9473aed..6f7387d 100644\n--- a/compat/fnmatch/fnmatch.c\n+++ b/compat/fnmatch/fnmatch.c\n@@ -55,7 +55,8 @@\n program understand `configure --with-gnu-libc' and omit the object files,\n it is simpler to just do this in the source for each such file. */\n \n-#if defined _LIBC || !defined __GNU_LIBRARY__\n+#if defined NO_FNMATCH || defined NO_FNMATCH_CASEFOLD || \\\n+ defined _LIBC || !defined __GNU_LIBRARY__\n \n \n # if defined STDC_HEADERS || !defined isascii\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"205392","messageId":"1356163028-29967-3-git-send-email-pclouds@gmail.com","threadId":"32440","inReplyTo":"1356163028-29967-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/8] wildmatch: rename constants and update prototype","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-22T07:57:02Z","receivedAt":"2012-12-22T07:57:02Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"- All exported constants now have a prefix WM_\n- Do not rely on FNM_* constants, use the WM_ counterparts\n- Remove TRUE and FALSE to follow Git's coding style\n- While at it, turn flags type from int to unsigned int\n- Add an (unused yet) argument to carry extra information\n so that we don't have to change the prototype again later\n when we need to pass other stuff to wildmatch\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 3 +-\n test-wildmatch.c | 4 +--\n wildmatch.c | 86 +++++++++++++++++++++++++++-----------------------------\n wildmatch.h | 22 ++++++++++-----\n 4 files changed, 61 insertions(+), 54 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex cb7328b..175a182 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -595,7 +595,8 @@ int match_pathname(const char *pathname, int pathlen,\n \t}\n \n \treturn wildmatch(pattern, name,\n-\t\t\t ignore_case ? FNM_CASEFOLD : 0) == 0;\n+\t\t\t ignore_case ? WM_CASEFOLD : 0,\n+\t\t\t NULL) == 0;\n }\n \n /* Scan the list and let the last match determine the fate.\ndiff --git a/test-wildmatch.c b/test-wildmatch.c\nindex e384c8e..4bb23b4 100644\n--- a/test-wildmatch.c\n+++ b/test-wildmatch.c\n@@ -12,9 +12,9 @@ int main(int argc, char **argv)\n \t\t\targv[i] += 3;\n \t}\n \tif (!strcmp(argv[1], \"wildmatch\"))\n-\t\treturn !!wildmatch(argv[3], argv[2], 0);\n+\t\treturn !!wildmatch(argv[3], argv[2], 0, NULL);\n \telse if (!strcmp(argv[1], \"iwildmatch\"))\n-\t\treturn !!wildmatch(argv[3], argv[2], FNM_CASEFOLD);\n+\t\treturn !!wildmatch(argv[3], argv[2], WM_CASEFOLD, NULL);\n \telse if (!strcmp(argv[1], \"fnmatch\"))\n \t\treturn !!fnmatch(argv[3], argv[2], FNM_PATHNAME);\n \telse\ndiff --git a/wildmatch.c b/wildmatch.c\nindex 3972e26..6ee1b09 100644\n--- a/wildmatch.c\n+++ b/wildmatch.c\n@@ -18,9 +18,6 @@ typedef unsigned char uchar;\n #define NEGATE_CLASS\t'!'\n #define NEGATE_CLASS2\t'^'\n \n-#define FALSE 0\n-#define TRUE 1\n-\n #define CC_EQ(class, len, litmatch) ((len) == sizeof (litmatch)-1 \\\n \t\t\t\t && *(class) == *(litmatch) \\\n \t\t\t\t && strncmp((char*)class, litmatch, len) == 0)\n@@ -63,7 +60,7 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)\n \t\tint matched, special;\n \t\tuchar t_ch, prev_ch;\n \t\tif ((t_ch = *text) == '\\0' && p_ch != '*')\n-\t\t\treturn ABORT_ALL;\n+\t\t\treturn WM_ABORT_ALL;\n \t\tif (force_lower_case && ISUPPER(t_ch))\n \t\t\tt_ch = tolower(t_ch);\n \t\tif (force_lower_case && ISUPPER(p_ch))\n@@ -76,12 +73,12 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)\n \t\t\t/* FALLTHROUGH */\n \t\tdefault:\n \t\t\tif (t_ch != p_ch)\n-\t\t\t\treturn NOMATCH;\n+\t\t\t\treturn WM_NOMATCH;\n \t\t\tcontinue;\n \t\tcase '?':\n \t\t\t/* Match anything but '/'. */\n \t\t\tif (t_ch == '/')\n-\t\t\t\treturn NOMATCH;\n+\t\t\t\treturn WM_NOMATCH;\n \t\t\tcontinue;\n \t\tcase '*':\n \t\t\tif (*++p == '*') {\n@@ -100,33 +97,33 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)\n \t\t\t\t\t * both foo/bar and foo/a/bar.\n \t\t\t\t\t */\n \t\t\t\t\tif (p[0] == '/' &&\n-\t\t\t\t\t dowild(p + 1, text, force_lower_case) == MATCH)\n-\t\t\t\t\t\treturn MATCH;\n-\t\t\t\t\tspecial = TRUE;\n+\t\t\t\t\t dowild(p + 1, text, force_lower_case) == WM_MATCH)\n+\t\t\t\t\t\treturn WM_MATCH;\n+\t\t\t\t\tspecial = 1;\n \t\t\t\t} else\n-\t\t\t\t\treturn ABORT_MALFORMED;\n+\t\t\t\t\treturn WM_ABORT_MALFORMED;\n \t\t\t} else\n-\t\t\t\tspecial = FALSE;\n+\t\t\t\tspecial = 0;\n \t\t\tif (*p == '\\0') {\n \t\t\t\t/* Trailing \"**\" matches everything. Trailing \"*\" matches\n \t\t\t\t * only if there are no more slash characters. */\n \t\t\t\tif (!special) {\n \t\t\t\t\tif (strchr((char*)text, '/') != NULL)\n-\t\t\t\t\t\treturn NOMATCH;\n+\t\t\t\t\t\treturn WM_NOMATCH;\n \t\t\t\t}\n-\t\t\t\treturn MATCH;\n+\t\t\t\treturn WM_MATCH;\n \t\t\t}\n \t\t\twhile (1) {\n \t\t\t\tif (t_ch == '\\0')\n \t\t\t\t\tbreak;\n-\t\t\t\tif ((matched = dowild(p, text, force_lower_case)) != NOMATCH) {\n-\t\t\t\t\tif (!special || matched != ABORT_TO_STARSTAR)\n+\t\t\t\tif ((matched = dowild(p, text, force_lower_case)) != WM_NOMATCH) {\n+\t\t\t\t\tif (!special || matched != WM_ABORT_TO_STARSTAR)\n \t\t\t\t\t\treturn matched;\n \t\t\t\t} else if (!special && t_ch == '/')\n-\t\t\t\t\treturn ABORT_TO_STARSTAR;\n+\t\t\t\t\treturn WM_ABORT_TO_STARSTAR;\n \t\t\t\tt_ch = *++text;\n \t\t\t}\n-\t\t\treturn ABORT_ALL;\n+\t\t\treturn WM_ABORT_ALL;\n \t\tcase '[':\n \t\t\tp_ch = *++p;\n #ifdef NEGATE_CLASS2\n@@ -134,101 +131,102 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)\n \t\t\t\tp_ch = NEGATE_CLASS;\n #endif\n \t\t\t/* Assign literal TRUE/FALSE because of \"matched\" comparison. */\n-\t\t\tspecial = p_ch == NEGATE_CLASS? TRUE : FALSE;\n+\t\t\tspecial = p_ch == NEGATE_CLASS;\n \t\t\tif (special) {\n \t\t\t\t/* Inverted character class. */\n \t\t\t\tp_ch = *++p;\n \t\t\t}\n \t\t\tprev_ch = 0;\n-\t\t\tmatched = FALSE;\n+\t\t\tmatched = 0;\n \t\t\tdo {\n \t\t\t\tif (!p_ch)\n-\t\t\t\t\treturn ABORT_ALL;\n+\t\t\t\t\treturn WM_ABORT_ALL;\n \t\t\t\tif (p_ch == '\\\\') {\n \t\t\t\t\tp_ch = *++p;\n \t\t\t\t\tif (!p_ch)\n-\t\t\t\t\t\treturn ABORT_ALL;\n+\t\t\t\t\t\treturn WM_ABORT_ALL;\n \t\t\t\t\tif (t_ch == p_ch)\n-\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\tmatched = 1;\n \t\t\t\t} else if (p_ch == '-' && prev_ch && p[1] && p[1] != ']') {\n \t\t\t\t\tp_ch = *++p;\n \t\t\t\t\tif (p_ch == '\\\\') {\n \t\t\t\t\t\tp_ch = *++p;\n \t\t\t\t\t\tif (!p_ch)\n-\t\t\t\t\t\t\treturn ABORT_ALL;\n+\t\t\t\t\t\t\treturn WM_ABORT_ALL;\n \t\t\t\t\t}\n \t\t\t\t\tif (t_ch <= p_ch && t_ch >= prev_ch)\n-\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\tp_ch = 0; /* This makes \"prev_ch\" get set to 0. */\n \t\t\t\t} else if (p_ch == '[' && p[1] == ':') {\n \t\t\t\t\tconst uchar *s;\n \t\t\t\t\tint i;\n \t\t\t\t\tfor (s = p += 2; (p_ch = *p) && p_ch != ']'; p++) {} /*SHARED ITERATOR*/\n \t\t\t\t\tif (!p_ch)\n-\t\t\t\t\t\treturn ABORT_ALL;\n+\t\t\t\t\t\treturn WM_ABORT_ALL;\n \t\t\t\t\ti = p - s - 1;\n \t\t\t\t\tif (i < 0 || p[-1] != ':') {\n \t\t\t\t\t\t/* Didn't find \":]\", so treat like a normal set. */\n \t\t\t\t\t\tp = s - 2;\n \t\t\t\t\t\tp_ch = '[';\n \t\t\t\t\t\tif (t_ch == p_ch)\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t\tcontinue;\n \t\t\t\t\t}\n \t\t\t\t\tif (CC_EQ(s,i, \"alnum\")) {\n \t\t\t\t\t\tif (ISALNUM(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else if (CC_EQ(s,i, \"alpha\")) {\n \t\t\t\t\t\tif (ISALPHA(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else if (CC_EQ(s,i, \"blank\")) {\n \t\t\t\t\t\tif (ISBLANK(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else if (CC_EQ(s,i, \"cntrl\")) {\n \t\t\t\t\t\tif (ISCNTRL(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else if (CC_EQ(s,i, \"digit\")) {\n \t\t\t\t\t\tif (ISDIGIT(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else if (CC_EQ(s,i, \"graph\")) {\n \t\t\t\t\t\tif (ISGRAPH(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else if (CC_EQ(s,i, \"lower\")) {\n \t\t\t\t\t\tif (ISLOWER(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else if (CC_EQ(s,i, \"print\")) {\n \t\t\t\t\t\tif (ISPRINT(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else if (CC_EQ(s,i, \"punct\")) {\n \t\t\t\t\t\tif (ISPUNCT(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else if (CC_EQ(s,i, \"space\")) {\n \t\t\t\t\t\tif (ISSPACE(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else if (CC_EQ(s,i, \"upper\")) {\n \t\t\t\t\t\tif (ISUPPER(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else if (CC_EQ(s,i, \"xdigit\")) {\n \t\t\t\t\t\tif (ISXDIGIT(t_ch))\n-\t\t\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\t\t\tmatched = 1;\n \t\t\t\t\t} else /* malformed [:class:] string */\n-\t\t\t\t\t\treturn ABORT_ALL;\n+\t\t\t\t\t\treturn WM_ABORT_ALL;\n \t\t\t\t\tp_ch = 0; /* This makes \"prev_ch\" get set to 0. */\n \t\t\t\t} else if (t_ch == p_ch)\n-\t\t\t\t\tmatched = TRUE;\n+\t\t\t\t\tmatched = 1;\n \t\t\t} while (prev_ch = p_ch, (p_ch = *++p) != ']');\n \t\t\tif (matched == special || t_ch == '/')\n-\t\t\t\treturn NOMATCH;\n+\t\t\t\treturn WM_NOMATCH;\n \t\t\tcontinue;\n \t\t}\n \t}\n \n-\treturn *text ? NOMATCH : MATCH;\n+\treturn *text ? WM_NOMATCH : WM_MATCH;\n }\n \n /* Match the \"pattern\" against the \"text\" string. */\n-int wildmatch(const char *pattern, const char *text, int flags)\n+int wildmatch(const char *pattern, const char *text,\n+\t unsigned int flags, struct wildopts *wo)\n {\n \treturn dowild((const uchar*)pattern, (const uchar*)text,\n-\t\t flags & FNM_CASEFOLD ? 1 :0);\n+\t\t flags & WM_CASEFOLD ? 1 :0);\n }\ndiff --git a/wildmatch.h b/wildmatch.h\nindex 984a38c..1c814fd 100644\n--- a/wildmatch.h\n+++ b/wildmatch.h\n@@ -1,9 +1,17 @@\n-/* wildmatch.h */\n+#ifndef WILDMATCH_H\n+#define WILDMATCH_H\n \n-#define ABORT_MALFORMED 2\n-#define NOMATCH 1\n-#define MATCH 0\n-#define ABORT_ALL -1\n-#define ABORT_TO_STARSTAR -2\n+#define WM_CASEFOLD 1\n \n-int wildmatch(const char *pattern, const char *text, int flags);\n+#define WM_ABORT_MALFORMED 2\n+#define WM_NOMATCH 1\n+#define WM_MATCH 0\n+#define WM_ABORT_ALL -1\n+#define WM_ABORT_TO_STARSTAR -2\n+\n+struct wildopts;\n+\n+int wildmatch(const char *pattern, const char *text,\n+\t unsigned int flags,\n+\t struct wildopts *wo);\n+#endif\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"205393","messageId":"1356163028-29967-4-git-send-email-pclouds@gmail.com","threadId":"32440","inReplyTo":"1356163028-29967-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 3/8] wildmatch: make dowild() take arbitrary flags","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-22T07:57:03Z","receivedAt":"2012-12-22T07:57:03Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n wildmatch.c | 13 ++++++-------\n 1 file changed, 6 insertions(+), 7 deletions(-)\n\ndiff --git a/wildmatch.c b/wildmatch.c\nindex 6ee1b09..a79f97e 100644\n--- a/wildmatch.c\n+++ b/wildmatch.c\n@@ -52,7 +52,7 @@ typedef unsigned char uchar;\n #define ISXDIGIT(c) (ISASCII(c) && isxdigit(c))\n \n /* Match pattern \"p\" against \"text\" */\n-static int dowild(const uchar *p, const uchar *text, int force_lower_case)\n+static int dowild(const uchar *p, const uchar *text, unsigned int flags)\n {\n \tuchar p_ch;\n \n@@ -61,9 +61,9 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)\n \t\tuchar t_ch, prev_ch;\n \t\tif ((t_ch = *text) == '\\0' && p_ch != '*')\n \t\t\treturn WM_ABORT_ALL;\n-\t\tif (force_lower_case && ISUPPER(t_ch))\n+\t\tif ((flags & WM_CASEFOLD) && ISUPPER(t_ch))\n \t\t\tt_ch = tolower(t_ch);\n-\t\tif (force_lower_case && ISUPPER(p_ch))\n+\t\tif ((flags & WM_CASEFOLD) && ISUPPER(p_ch))\n \t\t\tp_ch = tolower(p_ch);\n \t\tswitch (p_ch) {\n \t\tcase '\\\\':\n@@ -97,7 +97,7 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)\n \t\t\t\t\t * both foo/bar and foo/a/bar.\n \t\t\t\t\t */\n \t\t\t\t\tif (p[0] == '/' &&\n-\t\t\t\t\t dowild(p + 1, text, force_lower_case) == WM_MATCH)\n+\t\t\t\t\t dowild(p + 1, text, flags) == WM_MATCH)\n \t\t\t\t\t\treturn WM_MATCH;\n \t\t\t\t\tspecial = 1;\n \t\t\t\t} else\n@@ -116,7 +116,7 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)\n \t\t\twhile (1) {\n \t\t\t\tif (t_ch == '\\0')\n \t\t\t\t\tbreak;\n-\t\t\t\tif ((matched = dowild(p, text, force_lower_case)) != WM_NOMATCH) {\n+\t\t\t\tif ((matched = dowild(p, text, flags)) != WM_NOMATCH) {\n \t\t\t\t\tif (!special || matched != WM_ABORT_TO_STARSTAR)\n \t\t\t\t\t\treturn matched;\n \t\t\t\t} else if (!special && t_ch == '/')\n@@ -227,6 +227,5 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)\n int wildmatch(const char *pattern, const char *text,\n \t unsigned int flags, struct wildopts *wo)\n {\n-\treturn dowild((const uchar*)pattern, (const uchar*)text,\n-\t\t flags & WM_CASEFOLD ? 1 :0);\n+\treturn dowild((const uchar*)pattern, (const uchar*)text, flags);\n }\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"205391","messageId":"1356163028-29967-5-git-send-email-pclouds@gmail.com","threadId":"32440","inReplyTo":"1356163028-29967-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 4/8] wildmatch: support \"no FNM_PATHNAME\" mode","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-22T07:57:04Z","receivedAt":"2012-12-22T07:57:04Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"So far, wildmatch() has always honoured directory boundary and there\nwas no way to turn it off. Make it behave more like fnmatch() by\nrequiring all callers that want the FNM_PATHNAME behaviour to pass\nthat in the equivalent flag WM_PATHNAME. Callers that do not specify\nWM_PATHNAME will get wildcards like ? and * in their patterns matched\nagainst '/', just like not passing FNM_PATHNAME to fnmatch().\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n dir.c | 2 +-\n t/t3070-wildmatch.sh | 27 +++++++++++++++++++++++++++\n test-wildmatch.c | 6 ++++--\n wildmatch.c | 13 +++++++++----\n wildmatch.h | 1 +\n 5 files changed, 42 insertions(+), 7 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 175a182..6ef0396 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -595,7 +595,7 @@ int match_pathname(const char *pathname, int pathlen,\n \t}\n \n \treturn wildmatch(pattern, name,\n-\t\t\t ignore_case ? WM_CASEFOLD : 0,\n+\t\t\t WM_PATHNAME | (ignore_case ? WM_CASEFOLD : 0),\n \t\t\t NULL) == 0;\n }\n \ndiff --git a/t/t3070-wildmatch.sh b/t/t3070-wildmatch.sh\nindex d5bafef..dbfa903 100755\n--- a/t/t3070-wildmatch.sh\n+++ b/t/t3070-wildmatch.sh\n@@ -29,6 +29,18 @@ match() {\n fi\n }\n \n+pathmatch() {\n+ if [ $1 = 1 ]; then\n+\ttest_expect_success \"pathmatch: match '$2' '$3'\" \"\n+\t test-wildmatch pathmatch '$2' '$3'\n+\t\"\n+ else\n+\ttest_expect_success \"pathmatch: no match '$2' '$3'\" \"\n+\t ! test-wildmatch pathmatch '$2' '$3'\n+\t\"\n+ fi\n+}\n+\n # Basic wildmat features\n match 1 1 foo foo\n match 0 0 foo bar\n@@ -192,4 +204,19 @@ match 0 0 'XXX/adobe/courier/bold/o/normal//12/120/75/75/X/70/iso8859/1' 'XXX/*/\n match 1 0 'abcd/abcdefg/abcdefghijk/abcdefghijklmnop.txt' '**/*a*b*g*n*t'\n match 0 0 'abcd/abcdefg/abcdefghijk/abcdefghijklmnop.txtz' '**/*a*b*g*n*t'\n \n+pathmatch 1 foo foo\n+pathmatch 0 foo fo\n+pathmatch 1 foo/bar foo/bar\n+pathmatch 1 foo/bar 'foo/*'\n+pathmatch 1 foo/bba/arr 'foo/*'\n+pathmatch 1 foo/bba/arr 'foo/**'\n+pathmatch 1 foo/bba/arr 'foo*'\n+pathmatch 1 foo/bba/arr 'foo**'\n+pathmatch 1 foo/bba/arr 'foo/*arr'\n+pathmatch 1 foo/bba/arr 'foo/**arr'\n+pathmatch 0 foo/bba/arr 'foo/*z'\n+pathmatch 0 foo/bba/arr 'foo/**z'\n+pathmatch 1 foo/bar 'foo?bar'\n+pathmatch 1 foo/bar 'foo[/]bar'\n+\n test_done\ndiff --git a/test-wildmatch.c b/test-wildmatch.c\nindex 4bb23b4..a5f4833 100644\n--- a/test-wildmatch.c\n+++ b/test-wildmatch.c\n@@ -12,9 +12,11 @@ int main(int argc, char **argv)\n \t\t\targv[i] += 3;\n \t}\n \tif (!strcmp(argv[1], \"wildmatch\"))\n-\t\treturn !!wildmatch(argv[3], argv[2], 0, NULL);\n+\t\treturn !!wildmatch(argv[3], argv[2], WM_PATHNAME, NULL);\n \telse if (!strcmp(argv[1], \"iwildmatch\"))\n-\t\treturn !!wildmatch(argv[3], argv[2], WM_CASEFOLD, NULL);\n+\t\treturn !!wildmatch(argv[3], argv[2], WM_PATHNAME | WM_CASEFOLD, NULL);\n+\telse if (!strcmp(argv[1], \"pathmatch\"))\n+\t\treturn !!wildmatch(argv[3], argv[2], 0, NULL);\n \telse if (!strcmp(argv[1], \"fnmatch\"))\n \t\treturn !!fnmatch(argv[3], argv[2], FNM_PATHNAME);\n \telse\ndiff --git a/wildmatch.c b/wildmatch.c\nindex a79f97e..4fe1d65 100644\n--- a/wildmatch.c\n+++ b/wildmatch.c\n@@ -77,14 +77,17 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)\n \t\t\tcontinue;\n \t\tcase '?':\n \t\t\t/* Match anything but '/'. */\n-\t\t\tif (t_ch == '/')\n+\t\t\tif ((flags & WM_PATHNAME) && t_ch == '/')\n \t\t\t\treturn WM_NOMATCH;\n \t\t\tcontinue;\n \t\tcase '*':\n \t\t\tif (*++p == '*') {\n \t\t\t\tconst uchar *prev_p = p - 2;\n \t\t\t\twhile (*++p == '*') {}\n-\t\t\t\tif ((prev_p == text || *prev_p == '/') ||\n+\t\t\t\tif (!(flags & WM_PATHNAME))\n+\t\t\t\t\t/* without WM_PATHNAME, '*' == '**' */\n+\t\t\t\t\tspecial = 1;\n+\t\t\t\telse if ((prev_p == text || *prev_p == '/') ||\n \t\t\t\t (*p == '\\0' || *p == '/' ||\n \t\t\t\t (p[0] == '\\\\' && p[1] == '/'))) {\n \t\t\t\t\t/*\n@@ -103,7 +106,8 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)\n \t\t\t\t} else\n \t\t\t\t\treturn WM_ABORT_MALFORMED;\n \t\t\t} else\n-\t\t\t\tspecial = 0;\n+\t\t\t\t/* without WM_PATHNAME, '*' == '**' */\n+\t\t\t\tspecial = flags & WM_PATHNAME ? 0 : 1;\n \t\t\tif (*p == '\\0') {\n \t\t\t\t/* Trailing \"**\" matches everything. Trailing \"*\" matches\n \t\t\t\t * only if there are no more slash characters. */\n@@ -214,7 +218,8 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)\n \t\t\t\t} else if (t_ch == p_ch)\n \t\t\t\t\tmatched = 1;\n \t\t\t} while (prev_ch = p_ch, (p_ch = *++p) != ']');\n-\t\t\tif (matched == special || t_ch == '/')\n+\t\t\tif (matched == special ||\n+\t\t\t ((flags & WM_PATHNAME) && t_ch == '/'))\n \t\t\t\treturn WM_NOMATCH;\n \t\t\tcontinue;\n \t\t}\ndiff --git a/wildmatch.h b/wildmatch.h\nindex 1c814fd..4090c8f 100644\n--- a/wildmatch.h\n+++ b/wildmatch.h\n@@ -2,6 +2,7 @@\n #define WILDMATCH_H\n \n #define WM_CASEFOLD 1\n+#define WM_PATHNAME 2\n \n #define WM_ABORT_MALFORMED 2\n #define WM_NOMATCH 1\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"205394","messageId":"1356163028-29967-6-git-send-email-pclouds@gmail.com","threadId":"32440","inReplyTo":"1356163028-29967-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 5/8] test-wildmatch: add \"perf\" command to compare wildmatch and fnmatch","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-22T07:57:05Z","receivedAt":"2012-12-22T07:57:05Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"It takes a text file, a pattern, a number and pathname flag. Each\nline in the text file is matched against the pattern times. If\n\"pathname\" is given, FNM_PATHNAME is used.\n\ntest-wildmatch is built with -O2 and tested against glibc 2.14.1 (also\n-O2) and compat/fnmatch. The input file is linux-2.6.git file list.\n is 2000. The complete command list is at the end.\n\nwildmatch is beaten in the following cases. Apparently it needs some\nimprovement in FNM_PATHNAME case:\n\nglibc, '*/*/*' with FNM_PATHNAME:\nwildmatch 8s 1559us\nfnmatch 1s 11877us or 12.65% faster\n\ncompat, '*/*/*' with FNM_PATHNAME:\nwildmatch 7s 922458us\nfnmatch 2s 905111us or 36.67% faster\n\ncompat, '*/*/*' without FNM_PATHNAME:\nwildmatch 7s 264201us\nfnmatch 2s 1897us or 27.56% faster\n\ncompat, '[a-z]*/[a-z]*/[a-z]*' with FNM_PATHNAME:\nwildmatch 8s 742827us\nfnmatch 0s 922943us or 10.56% faster\n\ncompat, '[a-z]*/[a-z]*/[a-z]*' without FNM_PATHNAME:\nwildmatch 8s 284520us\nfnmatch 0s 6936us or 0.08% faster\n\nThe rest of glibc numbers\n-------------------------\n\n'Documentation/*'\nwildmatch 1s 529479us\nfnmatch 1s 98263us or 71.81% slower\n\n'drivers/*'\nwildmatch 1s 988288us\nfnmatch 1s 192049us or 59.95% slower\n\n'Documentation/*' pathname\nwildmatch 1s 557507us\nfnmatch 1s 93696us or 70.22% slower\n\n'drivers/*' pathname\nwildmatch 2s 161626us\nfnmatch 1s 230372us or 56.92% slower\n\n'[Dd]ocu[Mn]entation/*'\nwildmatch 1s 776581us\nfnmatch 1s 471693us or 82.84% slower\n\n'[Dd]o?u[Mn]en?ati?n/*'\nwildmatch 1s 770770us\nfnmatch 1s 555727us or 87.86% slower\n\n'[Dd]o?u[Mn]en?ati?n/*' pathname\nwildmatch 1s 783507us\nfnmatch 1s 537029us or 86.18% slower\n\n'[A-Za-z][A-Za-z]??*'\nwildmatch 4s 110386us\nfnmatch 4s 926306us or 119.85% slower\n\n'[A-Za-z][A-Za-z]??'\nwildmatch 3s 918114us\nfnmatch 3s 686175us or 94.08% slower\n\n'[A-Za-z][A-Za-z]??*' pathname\nwildmatch 4s 453746us\nfnmatch 4s 955856us or 111.27% slower\n\n'[A-Za-z][A-Za-z]??' pathname\nwildmatch 3s 896646us\nfnmatch 3s 733828us or 95.82% slower\n\n'*/*/*'\nwildmatch 7s 287985us\nfnmatch 1s 74083us or 14.74% slower\n\n'[a-z]*/[a-z]*/[a-z]*' pathname\nwildmatch 8s 796659us\nfnmatch 1s 568409us or 17.83% slower\n\n'[a-z]*/[a-z]*/[a-z]*'\nwildmatch 8s 316559us\nfnmatch 3s 430652us or 41.25% slower\n\nThe rest of compat numbers\n--------------------------\n\n'Documentation/*'\nwildmatch 1s 520389us\nfnmatch 0s 62579us or 4.12% slower\n\n'drivers/*'\nwildmatch 1s 955354us\nfnmatch 0s 190109us or 9.72% slower\n\n'Documentation/*' pathname\nwildmatch 1s 561675us\nfnmatch 0s 55336us or 3.54% slower\n\n'drivers/*' pathname\nwildmatch 2s 106100us\nfnmatch 0s 219680us or 10.43% slower\n\n'[Dd]ocu[Mn]entation/*'\nwildmatch 1s 750810us\nfnmatch 0s 542721us or 31.00% slower\n\n'[Dd]o?u[Mn]en?ati?n/*'\nwildmatch 1s 724791us\nfnmatch 0s 538948us or 31.25% slower\n\n'[Dd]o?u[Mn]en?ati?n/*' pathname\nwildmatch 1s 731403us\nfnmatch 0s 537474us or 31.04% slower\n\n'[A-Za-z][A-Za-z]??*'\nwildmatch 4s 28555us\nfnmatch 1s 67297us or 26.49% slower\n\n'[A-Za-z][A-Za-z]??'\nwildmatch 3s 838279us\nfnmatch 0s 880005us or 22.93% slower\n\n'[A-Za-z][A-Za-z]??*' pathname\nwildmatch 4s 379476us\nfnmatch 1s 55643us or 24.10% slower\n\n'[A-Za-z][A-Za-z]??' pathname\nwildmatch 3s 830910us\nfnmatch 0s 849699us or 22.18% slower\n\nThe following commands are used:\n\nLANG=C ./test-wildmatch perf /tmp/filelist.txt 'Documentation/*' 2000\nLANG=C ./test-wildmatch perf /tmp/filelist.txt 'drivers/*' 2000\nLANG=C ./test-wildmatch perf /tmp/filelist.txt 'Documentation/*' 2000 pathname\nLANG=C ./test-wildmatch perf /tmp/filelist.txt 'drivers/*' 2000 pathname\nLANG=C ./test-wildmatch perf /tmp/filelist.txt '[Dd]ocu[Mn]entation/*' 2000\nLANG=C ./test-wildmatch perf /tmp/filelist.txt '[Dd]o?u[Mn]en?ati?n/*' 2000\nLANG=C ./test-wildmatch perf /tmp/filelist.txt '[Dd]o?u[Mn]en?ati?n/*' 2000 pathname\nLANG=C ./test-wildmatch perf /tmp/filelist.txt '[A-Za-z][A-Za-z]??*' 2000\nLANG=C ./test-wildmatch perf /tmp/filelist.txt '[A-Za-z][A-Za-z]??' 2000\nLANG=C ./test-wildmatch perf /tmp/filelist.txt '[A-Za-z][A-Za-z]??*' 2000 pathname\nLANG=C ./test-wildmatch perf /tmp/filelist.txt '[A-Za-z][A-Za-z]??' 2000 pathname\nLANG=C ./test-wildmatch perf /tmp/filelist.txt '*/*/*' 2000\nLANG=C ./test-wildmatch perf /tmp/filelist.txt '*/*/*' 2000 pathname\nLANG=C ./test-wildmatch perf /tmp/filelist.txt '[a-z]*/[a-z]*/[a-z]*' 2000 pathname\nLANG=C ./test-wildmatch perf /tmp/filelist.txt '[a-z]*/[a-z]*/[a-z]*' 2000\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n test-wildmatch.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 73 insertions(+)\n\ndiff --git a/test-wildmatch.c b/test-wildmatch.c\nindex a5f4833..ac86800 100644\n--- a/test-wildmatch.c\n+++ b/test-wildmatch.c\n@@ -1,9 +1,82 @@\n #include \"cache.h\"\n #include \"wildmatch.h\"\n \n+static int perf(int ac, char **av)\n+{\n+\tstruct timeval tv1, tv2;\n+\tstruct stat st;\n+\tint fd, i, n, flags1 = 0, flags2 = 0;\n+\tchar *buffer, *p;\n+\tuint32_t usec1, usec2;\n+\tconst char *lang;\n+\tconst char *file = av[0];\n+\tconst char *pattern = av[1];\n+\n+\tlang = getenv(\"LANG\");\n+\tif (lang && strcmp(lang, \"C\"))\n+\t\tdie(\"Please test it on C locale.\");\n+\n+\tif ((fd = open(file, O_RDONLY)) == -1 || fstat(fd, &st))\n+\t\tdie_errno(\"file open\");\n+\n+\tbuffer = xmalloc(st.st_size + 2);\n+\tif (read(fd, buffer, st.st_size) != st.st_size)\n+\t\tdie_errno(\"read\");\n+\n+\tbuffer[st.st_size] = '\\0';\n+\tbuffer[st.st_size + 1] = '\\0';\n+\tfor (i = 0; i < st.st_size; i++)\n+\t\tif (buffer[i] == '\\n')\n+\t\t\tbuffer[i] = '\\0';\n+\n+\tn = atoi(av[2]);\n+\tif (av[3] && !strcmp(av[3], \"pathname\")) {\n+\t\tflags1 = WM_PATHNAME;\n+\t\tflags2 = FNM_PATHNAME;\n+\t}\n+\n+\tgettimeofday(&tv1, NULL);\n+\tfor (i = 0; i < n; i++) {\n+\t\tfor (p = buffer; *p; p += strlen(p) + 1)\n+\t\t\twildmatch(pattern, p, flags1, NULL);\n+\t}\n+\tgettimeofday(&tv2, NULL);\n+\n+\tusec1 = (uint32_t)tv2.tv_sec * 1000000 + tv2.tv_usec;\n+\tusec1 -= (uint32_t)tv1.tv_sec * 1000000 + tv1.tv_usec;\n+\tprintf(\"wildmatch %ds %dus\\n\",\n+\t (int)(usec1 / 1000000),\n+\t (int)(usec1 % 1000000));\n+\n+\tgettimeofday(&tv1, NULL);\n+\tfor (i = 0; i < n; i++) {\n+\t\tfor (p = buffer; *p; p += strlen(p) + 1)\n+\t\t\tfnmatch(pattern, p, flags2);\n+\t}\n+\tgettimeofday(&tv2, NULL);\n+\n+\tusec2 = (uint32_t)tv2.tv_sec * 1000000 + tv2.tv_usec;\n+\tusec2 -= (uint32_t)tv1.tv_sec * 1000000 + tv1.tv_usec;\n+\tif (usec2 > usec1)\n+\t\tprintf(\"fnmatch %ds %dus or %.2f%% slower\\n\",\n+\t\t (int)((usec2 - usec1) / 1000000),\n+\t\t (int)((usec2 - usec1) % 1000000),\n+\t\t (float)(usec2 - usec1) / usec1 * 100);\n+\telse\n+\t\tprintf(\"fnmatch %ds %dus or %.2f%% faster\\n\",\n+\t\t (int)((usec1 - usec2) / 1000000),\n+\t\t (int)((usec1 - usec2) % 1000000),\n+\t\t (float)(usec1 - usec2) / usec1 * 100);\n+\treturn 0;\n+}\n+\n int main(int argc, char **argv)\n {\n \tint i;\n+\n+\tif (!strcmp(argv[1], \"perf\"))\n+\t\treturn perf(argc - 2, argv + 2);\n+\n \tfor (i = 2; i < argc; i++) {\n \t\tif (argv[i][0] == '/')\n \t\t\tdie(\"Forward slash is not allowed at the beginning of the\\n\"\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"205396","messageId":"1356163028-29967-7-git-send-email-pclouds@gmail.com","threadId":"32440","inReplyTo":"1356163028-29967-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 6/8] Makefile: add USE_WILDMATCH to use wildmatch as fnmatch","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-22T07:57:06Z","receivedAt":"2012-12-22T07:57:06Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This is similar to NO_FNMATCH but it uses wildmatch instead of\ncompat/fnmatch. This is an intermediate step to let wildmatch be used\nas fnmatch replacement for wider audience before it replaces fnmatch\ncompletely and compat/fnmatch is removed.\n\nfnmatch in test-wildmatch is not impacted by this and is the only\nplace that NO_FNMATCH or NO_FNMATCH_CASEFOLD remain active when\nUSE_WILDMATCH is set.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n Makefile | 6 ++++++\n git-compat-util.h | 13 +++++++++++++\n test-wildmatch.c | 3 +++\n 3 files changed, 22 insertions(+)\n\ndiff --git a/Makefile b/Makefile\nindex bc868d1..24e2774 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -99,6 +99,9 @@ all::\n # Define NO_FNMATCH_CASEFOLD if your fnmatch function doesn't have the\n # FNM_CASEFOLD GNU extension.\n #\n+# Define USE_WILDMATCH if you want to use Git's wildmatch\n+# implementation as fnmatch\n+#\n # Define NO_GECOS_IN_PWENT if you don't have pw_gecos in struct passwd\n # in the C library.\n #\n@@ -1625,6 +1628,9 @@ ifdef NO_FNMATCH_CASEFOLD\n \tCOMPAT_OBJS += compat/fnmatch/fnmatch.o\n endif\n endif\n+ifdef USE_WILDMATCH\n+\tCOMPAT_CFLAGS += -DUSE_WILDMATCH\n+endif\n ifdef NO_SETENV\n \tCOMPAT_CFLAGS += -DNO_SETENV\n \tCOMPAT_OBJS += compat/setenv.o\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 02f48f6..b2c7638 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -106,7 +106,9 @@\n #include \n #include \n #include \n+#ifndef USE_WILDMATCH\n #include \n+#endif\n #include \n #include \n #include \n@@ -238,6 +240,17 @@ extern char *gitbasename(char *);\n \n #include \"compat/bswap.h\"\n \n+#ifdef USE_WILDMATCH\n+#include \"wildmatch.h\"\n+#define FNM_PATHNAME WM_PATHNAME\n+#define FNM_CASEFOLD WM_CASEFOLD\n+#define FNM_NOMATCH WM_NOMATCH\n+static inline int fnmatch(const char *pattern, const char *string, int flags)\n+{\n+\treturn wildmatch(pattern, string, flags, NULL);\n+}\n+#endif\n+\n /* General helper functions */\n extern void vreportf(const char *prefix, const char *err, va_list params);\n extern void vwritef(int fd, const char *prefix, const char *err, va_list params);\ndiff --git a/test-wildmatch.c b/test-wildmatch.c\nindex ac86800..a3e2643 100644\n--- a/test-wildmatch.c\n+++ b/test-wildmatch.c\n@@ -1,3 +1,6 @@\n+#ifdef USE_WILDMATCH\n+#undef USE_WILDMATCH /* We need real fnmatch implementation here */\n+#endif\n #include \"cache.h\"\n #include \"wildmatch.h\"\n \n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"205395","messageId":"1356163028-29967-8-git-send-email-pclouds@gmail.com","threadId":"32440","inReplyTo":"1356163028-29967-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 7/8] wildmatch: make a special case for \"*/\" with FNM_PATHNAME","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-22T07:57:07Z","receivedAt":"2012-12-22T07:57:07Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Normally we need recursion for \"*\". In this case we know that it\nmatches everything until \"/\" so we can skip the recursion.\n\nglibc, '*/*/*' on linux-2.6.git file list 2000 times\nbefore:\nwildmatch 8s 74513us\nfnmatch 1s 97042us or 13.59% faster\nafter:\nwildmatch 3s 521862us\nfnmatch 3s 488616us or 99.06% slower\n\nSame test with compat/fnmatch:\nwildmatch 8s 110763us\nfnmatch 2s 980845us or 36.75% faster\nwildmatch 3s 522156us\nfnmatch 1s 544487us or 43.85% slower\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n wildmatch.c | 12 ++++++++++++\n 1 file changed, 12 insertions(+)\n\ndiff --git a/wildmatch.c b/wildmatch.c\nindex 4fe1d65..3794c4d 100644\n--- a/wildmatch.c\n+++ b/wildmatch.c\n@@ -116,6 +116,18 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)\n \t\t\t\t\t\treturn WM_NOMATCH;\n \t\t\t\t}\n \t\t\t\treturn WM_MATCH;\n+\t\t\t} else if (*p == '/' && (flags & WM_PATHNAME) && !special) {\n+\t\t\t\t/*\n+\t\t\t\t * an asterisk followed by a slash\n+\t\t\t\t * with WM_PATHNAME matches the next\n+\t\t\t\t * directory\n+\t\t\t\t */\n+\t\t\t\tconst char *slash = strchr((char*)text, '/');\n+\t\t\t\tif (!slash)\n+\t\t\t\t\treturn WM_NOMATCH;\n+\t\t\t\ttext = (const uchar*)slash;\n+\t\t\t\t/* the slash is consumed by the top-level for loop */\n+\t\t\t\tbreak;\n \t\t\t}\n \t\t\twhile (1) {\n \t\t\t\tif (t_ch == '\\0')\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"205397","messageId":"1356163028-29967-9-git-send-email-pclouds@gmail.com","threadId":"32440","inReplyTo":"1356163028-29967-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 8/8] wildmatch: advance faster in + patterns","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-22T07:57:08Z","receivedAt":"2012-12-22T07:57:08Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"compat, '*/*/*' on linux-2.6.git file list 2000 times, before:\nwildmatch 7s 985049us\nfnmatch 2s 735541us or 34.26% faster\n\nand after:\nwildmatch 4s 492549us\nfnmatch 0s 888263us or 19.77% slower\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n wildmatch.c | 21 +++++++++++++++++++++\n 1 file changed, 21 insertions(+)\n\ndiff --git a/wildmatch.c b/wildmatch.c\nindex 3794c4d..68b02e4 100644\n--- a/wildmatch.c\n+++ b/wildmatch.c\n@@ -132,6 +132,27 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)\n \t\t\twhile (1) {\n \t\t\t\tif (t_ch == '\\0')\n \t\t\t\t\tbreak;\n+\t\t\t\t/*\n+\t\t\t\t * Try to advance faster when an asterisk is\n+\t\t\t\t * followed by a literal. We know in this case\n+\t\t\t\t * that the the string before the literal\n+\t\t\t\t * must belong to \"*\".\n+\t\t\t\t */\n+\t\t\t\tif (!is_glob_special(*p)) {\n+\t\t\t\t\tp_ch = *p;\n+\t\t\t\t\tif ((flags & WM_CASEFOLD) && ISUPPER(p_ch))\n+\t\t\t\t\t\tp_ch = tolower(p_ch);\n+\t\t\t\t\twhile ((t_ch = *text) != '\\0' &&\n+\t\t\t\t\t (!(flags & WM_PATHNAME) || t_ch != '/')) {\n+\t\t\t\t\t\tif ((flags & WM_CASEFOLD) && ISUPPER(t_ch))\n+\t\t\t\t\t\t\tt_ch = tolower(t_ch);\n+\t\t\t\t\t\tif (t_ch == p_ch)\n+\t\t\t\t\t\t\tbreak;\n+\t\t\t\t\t\ttext++;\n+\t\t\t\t\t}\n+\t\t\t\t\tif (t_ch != p_ch)\n+\t\t\t\t\t\treturn WM_NOMATCH;\n+\t\t\t\t}\n \t\t\t\tif ((matched = dowild(p, text, flags)) != WM_NOMATCH) {\n \t\t\t\t\tif (!special || matched != WM_ABORT_TO_STARSTAR)\n \t\t\t\t\t\treturn matched;\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"205500","messageId":"7vvcboodpg.fsf@alter.siamese.dyndns.org","threadId":"32440","inReplyTo":"1356163028-29967-3-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 2/8] wildmatch: rename constants and update prototype","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-12-26T18:44:43Z","receivedAt":"2012-12-26T18:44:43Z","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> @@ -134,101 +131,102 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)\n> \t\t\t\tp_ch = NEGATE_CLASS;\n> #endif\n> \t\t\t/* Assign literal TRUE/FALSE because of \"matched\" comparison. */\n> -\t\t\tspecial = p_ch == NEGATE_CLASS? TRUE : FALSE;\n> +\t\t\tspecial = p_ch == NEGATE_CLASS;\n\nLeftover comment needs to be reworded as well???\n\n> \t\t\tif (special) {\n> \t\t\t\t/* Inverted character class. */\n> \t\t\t\tp_ch = *++p;\n> \t\t\t}\n\nI'd prefer \"special\" used in the \"case '['\" given a more sensible\nname here.\n"},{"id":"205582","messageId":"7vwqw2k833.fsf@alter.siamese.dyndns.org","threadId":"32440","inReplyTo":"1356163028-29967-5-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 4/8] wildmatch: support \"no FNM_PATHNAME\" mode","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-12-28T06:24:16Z","receivedAt":"2012-12-28T06:24:16Z","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/wildmatch.c b/wildmatch.c\n> index a79f97e..4fe1d65 100644\n> --- a/wildmatch.c\n> +++ b/wildmatch.c\n> @@ -77,14 +77,17 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)\n> \t\t\tcontinue;\n> \t\tcase '?':\n> \t\t\t/* Match anything but '/'. */\n> -\t\t\tif (t_ch == '/')\n> +\t\t\tif ((flags & WM_PATHNAME) && t_ch == '/')\n> \t\t\t\treturn WM_NOMATCH;\n> \t\t\tcontinue;\n> \t\tcase '*':\n> \t\t\tif (*++p == '*') {\n> \t\t\t\tconst uchar *prev_p = p - 2;\n> \t\t\t\twhile (*++p == '*') {}\n> -\t\t\t\tif ((prev_p == text || *prev_p == '/') ||\n> +\t\t\t\tif (!(flags & WM_PATHNAME))\n> +\t\t\t\t\t/* without WM_PATHNAME, '*' == '**' */\n> +\t\t\t\t\tspecial = 1;\n> +\t\t\t\telse if ((prev_p == text || *prev_p == '/') ||\n\nNot a new issue in this patch, but here, \"prev_p\" points into the\npattern string, two bytes before p, which is the byte before the\n\"**\" that we are looking at (which might be before the beginning of\nthe pattern). \"text\" is the string we are trying to match that\npattern against. How can these two pointers be compared to yield a\nmeaningful value?\n\n> \t\t\t\t (*p == '\\0' || *p == '/' ||\n> \t\t\t\t (p[0] == '\\\\' && p[1] == '/'))) {\n\nOK. \"**/\", \"**\" (end of pattern), and \"**\\/\" are handled here. \n\nDo we have to worry about \"**[/]\" the same way, or a class never\nmatches the directory separator, even if it is a singleton class\nthat consists of '/' (which is fine by me)? If so, is \"\\/\" more or\nless like \"[/]\"?\n"},{"id":"205583","messageId":"7vpq1uk82q.fsf@alter.siamese.dyndns.org","threadId":"32440","inReplyTo":"1356163028-29967-9-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 8/8] wildmatch: advance faster in + patterns","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-12-28T06:24:29Z","receivedAt":"2012-12-28T06:24:29Z","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> compat, '*/*/*' on linux-2.6.git file list 2000 times, before:\n> wildmatch 7s 985049us\n> fnmatch 2s 735541us or 34.26% faster\n>\n> and after:\n> wildmatch 4s 492549us\n> fnmatch 0s 888263us or 19.77% slower\n>\n> Signed-off-by: Nguyễn Thái Ngọc Duy \n> ---\n> wildmatch.c | 21 +++++++++++++++++++++\n> 1 file changed, 21 insertions(+)\n>\n> diff --git a/wildmatch.c b/wildmatch.c\n> index 3794c4d..68b02e4 100644\n> --- a/wildmatch.c\n> +++ b/wildmatch.c\n> @@ -132,6 +132,27 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)\n> \t\t\twhile (1) {\n> \t\t\t\tif (t_ch == '\\0')\n> \t\t\t\t\tbreak;\n> +\t\t\t\t/*\n> +\t\t\t\t * Try to advance faster when an asterisk is\n> +\t\t\t\t * followed by a literal. We know in this case\n> +\t\t\t\t * that the the string before the literal\n> +\t\t\t\t * must belong to \"*\".\n> +\t\t\t\t */\n> +\t\t\t\tif (!is_glob_special(*p)) {\n\nSo far, we have looked at \"*x\" or \"**x\" in the pattern, p points at\n'x' (not an asterisk), and we have \"text\" to match. For \"text\" to\nmatch this pattern, the earlier part of it that is consumed to match\nthe asterisk must be followed by \"x\". \"special\" tells us if we are\nallowed to treat '/' as matching the asterisk.\n\n> +\t\t\t\t\tp_ch = *p;\n> +\t\t\t\t\tif ((flags & WM_CASEFOLD) && ISUPPER(p_ch))\n> +\t\t\t\t\t\tp_ch = tolower(p_ch);\n\nThat \"x\" in the example is picked up here and stored in \"p_ch\".\nLet's skip over \"text\" and find that \"x\" in there.\n\n> +\t\t\t\t\twhile ((t_ch = *text) != '\\0' &&\n> +\t\t\t\t\t (!(flags & WM_PATHNAME) || t_ch != '/')) {\n\nWhy do we look at (flags & WM_PATHMAME) and not \"special\" here?\n\n> +\t\t\t\t\t\tif ((flags & WM_CASEFOLD) && ISUPPER(t_ch))\n> +\t\t\t\t\t\t\tt_ch = tolower(t_ch);\n> +\t\t\t\t\t\tif (t_ch == p_ch)\n> +\t\t\t\t\t\t\tbreak;\n\nFound it.\n\n> +\t\t\t\t\t\ttext++;\n> +\t\t\t\t\t}\n> +\t\t\t\t\tif (t_ch != p_ch)\n> +\t\t\t\t\t\treturn WM_NOMATCH;\n\nIf we did not find that \"x\", then \"**x\" or \"*x\" can never match.\nOK. And at this point \"text\" points at that \"x\" we found, and \"p\"\npoints at \"x\" after the asterisk in the pattern.\n\nLooks good so far. Thanks.\n\n> +\t\t\t\t}\n> \t\t\t\tif ((matched = dowild(p, text, flags)) != WM_NOMATCH) {\n> \t\t\t\t\tif (!special || matched != WM_ABORT_TO_STARSTAR)\n> \t\t\t\t\t\treturn matched;\n"},{"id":"205585","messageId":"CACsJy8A5PqVpn4SihSdDv6w5xusr1ac4MBETJ0mzvvguZ2YwnQ@mail.gmail.com","threadId":"32440","inReplyTo":"7vpq1uk82q.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 8/8] wildmatch: advance faster in + patterns","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-28T06:56:56Z","receivedAt":"2012-12-28T06:56:56Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Dec 28, 2012 at 1:24 PM, Junio C Hamano wrote:\n>> + while ((t_ch = *text) != '\\0' &&\n>> + (!(flags & WM_PATHNAME) || t_ch != '/')) {\n>\n> Why do we look at (flags & WM_PATHMAME) and not \"special\" here?\n\nBecause I was careless. Thanks for spotting it. I'll fix it and add\nsome more tests about ** with WM_PATHNAME.\n-- \nDuy\n"},{"id":"205586","messageId":"CACsJy8C7Y8xLVVhUtt1g234XnHrTbjRCBcY261QEe-y81A1YUw@mail.gmail.com","threadId":"32440","inReplyTo":"7vwqw2k833.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 4/8] wildmatch: support \"no FNM_PATHNAME\" mode","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-28T07:15:41Z","receivedAt":"2012-12-28T07:15:41Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Dec 28, 2012 at 1:24 PM, Junio C Hamano wrote:\n>> if (*++p == '*') {\n>> const uchar *prev_p = p - 2;\n>> while (*++p == '*') {}\n>> - if ((prev_p == text || *prev_p == '/') ||\n>> + if (!(flags & WM_PATHNAME))\n>> + /* without WM_PATHNAME, '*' == '**' */\n>> + special = 1;\n>> + else if ((prev_p == text || *prev_p == '/') ||\n>\n> Not a new issue in this patch,\n\nNo, it's an issue from nd/wildmatch, 40bbee0 (wildmatch: adjust \"**\"\nbehavior - 2012-10-15).\n\n> but here, \"prev_p\" points into the\n> pattern string, two bytes before p, which is the byte before the\n> \"**\" that we are looking at (which might be before the beginning of\n> the pattern). \"text\" is the string we are trying to match that\n> pattern against. How can these two pointers be compared to yield a\n> meaningful value?\n\nThey can't. I wanted to check whether \"**\" is at the start of the\npattern (so no preceding '/' needed) and used a wrong pointer to\ncompare to. Funny there is a test about this and it does not catch it\nbecause prev_p access something before the pattern. Will fix.\n\n>\n>> (*p == '\\0' || *p == '/' ||\n>> (p[0] == '\\\\' && p[1] == '/'))) {\n>\n> OK. \"**/\", \"**\" (end of pattern), and \"**\\/\" are handled here.\n>\n> Do we have to worry about \"**[/]\" the same way, or a class never\n> matches the directory separator, even if it is a singleton class\n> that consists of '/' (which is fine by me)? If so, is \"\\/\" more or\n> less like \"[/]\"?\n\nThis is a special case of \"**\" with FNM_PATHNAME on. With\nFNM_PATHNAME, '[]' and '?' cannot match '/' so any patterns with '[/]'\nmatch nothing. I think we don't need to worry about this case.\n-- \nDuy\n"}]}