Merge branch 'nd/retire-fnmatch'

Replace our use of fnmatch(3) with a more feature-rich wildmatch.
A handful patches at the bottom have been moved to nd/wildmatch to
graduate as part of that branch, before this series solidifies.

We may want to mark USE_WILDMATCH as an experimental curiosity a
bit more clearly (i.e. should not be enabled in production
environment, because it will make the behaviour between builds
unpredictable).

* nd/retire-fnmatch:
  Makefile: add USE_WILDMATCH to use wildmatch as fnmatch
  wildmatch: advance faster in <asterisk> + <literal> patterns
  wildmatch: make a special case for "*/" with FNM_PATHNAME
  test-wildmatch: add "perf" command to compare wildmatch and fnmatch
  wildmatch: support "no FNM_PATHNAME" mode
  wildmatch: make dowild() take arbitrary flags
  wildmatch: rename constants and update prototype

7 files changed, 249 insertions, 62 deletions

diff --git a/Makefile b/Makefile
index 11e85a6396..731b6a8834 100644
--- a/Makefile
+++ b/Makefile
@@ -105,6 +105,9 @@ all::
 # Define NO_FNMATCH_CASEFOLD if your fnmatch function doesn't have the
 # FNM_CASEFOLD GNU extension.
 #
+# Define USE_WILDMATCH if you want to use Git's wildmatch
+# implementation as fnmatch
+#
 # Define NO_GECOS_IN_PWENT if you don't have pw_gecos in struct passwd
 # in the C library.
 #
@@ -1225,6 +1228,9 @@ ifdef NO_FNMATCH_CASEFOLD
 	COMPAT_OBJS += compat/fnmatch/fnmatch.o
 endif
 endif
+ifdef USE_WILDMATCH
+	COMPAT_CFLAGS += -DUSE_WILDMATCH
+endif
 ifdef NO_SETENV
 	COMPAT_CFLAGS += -DNO_SETENV
 	COMPAT_OBJS += compat/setenv.o
diff --git a/dir.c b/dir.c
index cf1e6b0082..57394e452e 100644
--- a/dir.c
+++ b/dir.c
@@ -685,7 +685,8 @@ int match_pathname(const char *pathname, int pathlen,
 	}
 
 	return wildmatch(pattern, name,
-			 ignore_case ? FNM_CASEFOLD : 0) == 0;
+			 WM_PATHNAME | (ignore_case ? WM_CASEFOLD : 0),
+			 NULL) == 0;
 }
 
 /*
diff --git a/git-compat-util.h b/git-compat-util.h
index dab545e02e..cc2abeea0d 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -112,7 +112,9 @@
 #include <sys/time.h>
 #include <time.h>
 #include <signal.h>
+#ifndef USE_WILDMATCH
 #include <fnmatch.h>
+#endif
 #include <assert.h>
 #include <regex.h>
 #include <utime.h>
@@ -280,6 +282,17 @@ extern char *gitbasename(char *);
 
 #include "compat/bswap.h"
 
+#ifdef USE_WILDMATCH
+#include "wildmatch.h"
+#define FNM_PATHNAME WM_PATHNAME
+#define FNM_CASEFOLD WM_CASEFOLD
+#define FNM_NOMATCH  WM_NOMATCH
+static inline int fnmatch(const char *pattern, const char *string, int flags)
+{
+	return wildmatch(pattern, string, flags, NULL);
+}
+#endif
+
 /* General helper functions */
 extern void vreportf(const char *prefix, const char *err, va_list params);
 extern void vwritef(int fd, const char *prefix, const char *err, va_list params);
diff --git a/t/t3070-wildmatch.sh b/t/t3070-wildmatch.sh
index af54c83111..4c37057ddf 100755
--- a/t/t3070-wildmatch.sh
+++ b/t/t3070-wildmatch.sh
@@ -29,6 +29,18 @@ match() {
     fi
 }
 
+pathmatch() {
+    if [ $1 = 1 ]; then
+	test_expect_success "pathmatch:    match '$2' '$3'" "
+	    test-wildmatch pathmatch '$2' '$3'
+	"
+    else
+	test_expect_success "pathmatch: no match '$2' '$3'" "
+	    ! test-wildmatch pathmatch '$2' '$3'
+	"
+    fi
+}
+
 # Basic wildmat features
 match 1 1 foo foo
 match 0 0 foo bar
@@ -191,5 +203,36 @@ match 1 1 'XXX/adobe/courier/bold/o/normal//12/120/75/75/m/70/iso8859/1' 'XXX/*/
 match 0 0 'XXX/adobe/courier/bold/o/normal//12/120/75/75/X/70/iso8859/1' 'XXX/*/*/*/*/*/*/12/*/*/*/m/*/*/*'
 match 1 0 'abcd/abcdefg/abcdefghijk/abcdefghijklmnop.txt' '**/*a*b*g*n*t'
 match 0 0 'abcd/abcdefg/abcdefghijk/abcdefghijklmnop.txtz' '**/*a*b*g*n*t'
+match 0 x foo '*/*/*'
+match 0 x foo/bar '*/*/*'
+match 1 x foo/bba/arr '*/*/*'
+match 0 x foo/bb/aa/rr '*/*/*'
+match 1 x foo/bb/aa/rr '**/**/**'
+match 1 x abcXdefXghi '*X*i'
+match 0 x ab/cXd/efXg/hi '*X*i'
+match 1 x ab/cXd/efXg/hi '*/*X*/*/*i'
+match 1 x ab/cXd/efXg/hi '**/*X*/**/*i'
+
+pathmatch 1 foo foo
+pathmatch 0 foo fo
+pathmatch 1 foo/bar foo/bar
+pathmatch 1 foo/bar 'foo/*'
+pathmatch 1 foo/bba/arr 'foo/*'
+pathmatch 1 foo/bba/arr 'foo/**'
+pathmatch 1 foo/bba/arr 'foo*'
+pathmatch 1 foo/bba/arr 'foo**'
+pathmatch 1 foo/bba/arr 'foo/*arr'
+pathmatch 1 foo/bba/arr 'foo/**arr'
+pathmatch 0 foo/bba/arr 'foo/*z'
+pathmatch 0 foo/bba/arr 'foo/**z'
+pathmatch 1 foo/bar 'foo?bar'
+pathmatch 1 foo/bar 'foo[/]bar'
+pathmatch 0 foo '*/*/*'
+pathmatch 0 foo/bar '*/*/*'
+pathmatch 1 foo/bba/arr '*/*/*'
+pathmatch 1 foo/bb/aa/rr '*/*/*'
+pathmatch 1 abcXdefXghi '*X*i'
+pathmatch 1 ab/cXd/efXg/hi '*/*X*/*/*i'
+pathmatch 1 ab/cXd/efXg/hi '*Xg*i'
 
 test_done
diff --git a/test-wildmatch.c b/test-wildmatch.c
index e384c8edb1..a3e2643fbc 100644
--- a/test-wildmatch.c
+++ b/test-wildmatch.c
@@ -1,9 +1,85 @@
+#ifdef USE_WILDMATCH
+#undef USE_WILDMATCH  /* We need real fnmatch implementation here */
+#endif
 #include "cache.h"
 #include "wildmatch.h"
 
+static int perf(int ac, char **av)
+{
+	struct timeval tv1, tv2;
+	struct stat st;
+	int fd, i, n, flags1 = 0, flags2 = 0;
+	char *buffer, *p;
+	uint32_t usec1, usec2;
+	const char *lang;
+	const char *file = av[0];
+	const char *pattern = av[1];
+
+	lang = getenv("LANG");
+	if (lang && strcmp(lang, "C"))
+		die("Please test it on C locale.");
+
+	if ((fd = open(file, O_RDONLY)) == -1 || fstat(fd, &st))
+		die_errno("file open");
+
+	buffer = xmalloc(st.st_size + 2);
+	if (read(fd, buffer, st.st_size) != st.st_size)
+		die_errno("read");
+
+	buffer[st.st_size] = '\0';
+	buffer[st.st_size + 1] = '\0';
+	for (i = 0; i < st.st_size; i++)
+		if (buffer[i] == '\n')
+			buffer[i] = '\0';
+
+	n = atoi(av[2]);
+	if (av[3] && !strcmp(av[3], "pathname")) {
+		flags1 = WM_PATHNAME;
+		flags2 = FNM_PATHNAME;
+	}
+
+	gettimeofday(&tv1, NULL);
+	for (i = 0; i < n; i++) {
+		for (p = buffer; *p; p += strlen(p) + 1)
+			wildmatch(pattern, p, flags1, NULL);
+	}
+	gettimeofday(&tv2, NULL);
+
+	usec1 = (uint32_t)tv2.tv_sec * 1000000 + tv2.tv_usec;
+	usec1 -= (uint32_t)tv1.tv_sec * 1000000 + tv1.tv_usec;
+	printf("wildmatch %ds %dus\n",
+	       (int)(usec1 / 1000000),
+	       (int)(usec1 % 1000000));
+
+	gettimeofday(&tv1, NULL);
+	for (i = 0; i < n; i++) {
+		for (p = buffer; *p; p += strlen(p) + 1)
+			fnmatch(pattern, p, flags2);
+	}
+	gettimeofday(&tv2, NULL);
+
+	usec2 = (uint32_t)tv2.tv_sec * 1000000 + tv2.tv_usec;
+	usec2 -= (uint32_t)tv1.tv_sec * 1000000 + tv1.tv_usec;
+	if (usec2 > usec1)
+		printf("fnmatch   %ds %dus or %.2f%% slower\n",
+		       (int)((usec2 - usec1) / 1000000),
+		       (int)((usec2 - usec1) % 1000000),
+		       (float)(usec2 - usec1) / usec1 * 100);
+	else
+		printf("fnmatch   %ds %dus or %.2f%% faster\n",
+		       (int)((usec1 - usec2) / 1000000),
+		       (int)((usec1 - usec2) % 1000000),
+		       (float)(usec1 - usec2) / usec1 * 100);
+	return 0;
+}
+
 int main(int argc, char **argv)
 {
 	int i;
+
+	if (!strcmp(argv[1], "perf"))
+		return perf(argc - 2, argv + 2);
+
 	for (i = 2; i < argc; i++) {
 		if (argv[i][0] == '/')
 			die("Forward slash is not allowed at the beginning of the\n"
@@ -12,9 +88,11 @@ int main(int argc, char **argv)
 			argv[i] += 3;
 	}
 	if (!strcmp(argv[1], "wildmatch"))
-		return !!wildmatch(argv[3], argv[2], 0);
+		return !!wildmatch(argv[3], argv[2], WM_PATHNAME, NULL);
 	else if (!strcmp(argv[1], "iwildmatch"))
-		return !!wildmatch(argv[3], argv[2], FNM_CASEFOLD);
+		return !!wildmatch(argv[3], argv[2], WM_PATHNAME | WM_CASEFOLD, NULL);
+	else if (!strcmp(argv[1], "pathmatch"))
+		return !!wildmatch(argv[3], argv[2], 0, NULL);
 	else if (!strcmp(argv[1], "fnmatch"))
 		return !!fnmatch(argv[3], argv[2], FNM_PATHNAME);
 	else
diff --git a/wildmatch.c b/wildmatch.c
index 2d3ed84364..7192bdc1b8 100644
--- a/wildmatch.c
+++ b/wildmatch.c
@@ -18,9 +18,6 @@ typedef unsigned char uchar;
 #define NEGATE_CLASS	'!'
 #define NEGATE_CLASS2	'^'
 
-#define FALSE 0
-#define TRUE 1
-
 #define CC_EQ(class, len, litmatch) ((len) == sizeof (litmatch)-1 \
 				    && *(class) == *(litmatch) \
 				    && strncmp((char*)class, litmatch, len) == 0)
@@ -55,7 +52,7 @@ typedef unsigned char uchar;
 #define ISXDIGIT(c) (ISASCII(c) && isxdigit(c))
 
 /* Match pattern "p" against "text" */
-static int dowild(const uchar *p, const uchar *text, int force_lower_case)
+static int dowild(const uchar *p, const uchar *text, unsigned int flags)
 {
 	uchar p_ch;
 	const uchar *pattern = p;
@@ -64,10 +61,10 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)
 		int matched, match_slash, negated;
 		uchar t_ch, prev_ch;
 		if ((t_ch = *text) == '\0' && p_ch != '*')
-			return ABORT_ALL;
-		if (force_lower_case && ISUPPER(t_ch))
+			return WM_ABORT_ALL;
+		if ((flags & WM_CASEFOLD) && ISUPPER(t_ch))
 			t_ch = tolower(t_ch);
-		if (force_lower_case && ISUPPER(p_ch))
+		if ((flags & WM_CASEFOLD) && ISUPPER(p_ch))
 			p_ch = tolower(p_ch);
 		switch (p_ch) {
 		case '\\':
@@ -77,18 +74,21 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)
 			/* FALLTHROUGH */
 		default:
 			if (t_ch != p_ch)
-				return NOMATCH;
+				return WM_NOMATCH;
 			continue;
 		case '?':
 			/* Match anything but '/'. */
-			if (t_ch == '/')
-				return NOMATCH;
+			if ((flags & WM_PATHNAME) && t_ch == '/')
+				return WM_NOMATCH;
 			continue;
 		case '*':
 			if (*++p == '*') {
 				const uchar *prev_p = p - 2;
 				while (*++p == '*') {}
-				if ((prev_p < pattern || *prev_p == '/') &&
+				if (!(flags & WM_PATHNAME))
+					/* without WM_PATHNAME, '*' == '**' */
+					match_slash = 1;
+				else if ((prev_p < pattern || *prev_p == '/') &&
 				    (*p == '\0' || *p == '/' ||
 				     (p[0] == '\\' && p[1] == '/'))) {
 					/*
@@ -101,135 +101,172 @@ static int dowild(const uchar *p, const uchar *text, int force_lower_case)
 					 * both foo/bar and foo/a/bar.
 					 */
 					if (p[0] == '/' &&
-					    dowild(p + 1, text, force_lower_case) == MATCH)
-						return MATCH;
-					match_slash = TRUE;
+					    dowild(p + 1, text, flags) == WM_MATCH)
+						return WM_MATCH;
+					match_slash = 1;
 				} else
-					return ABORT_MALFORMED;
+					return WM_ABORT_MALFORMED;
 			} else
-				match_slash = FALSE;
+				/* without WM_PATHNAME, '*' == '**' */
+				match_slash = flags & WM_PATHNAME ? 0 : 1;
 			if (*p == '\0') {
 				/* Trailing "**" matches everything.  Trailing "*" matches
 				 * only if there are no more slash characters. */
 				if (!match_slash) {
 					if (strchr((char*)text, '/') != NULL)
-						return NOMATCH;
+						return WM_NOMATCH;
 				}
-				return MATCH;
+				return WM_MATCH;
+			} else if (!match_slash && *p == '/') {
+				/*
+				 * _one_ asterisk followed by a slash
+				 * with WM_PATHNAME matches the next
+				 * directory
+				 */
+				const char *slash = strchr((char*)text, '/');
+				if (!slash)
+					return WM_NOMATCH;
+				text = (const uchar*)slash;
+				/* the slash is consumed by the top-level for loop */
+				break;
 			}
 			while (1) {
 				if (t_ch == '\0')
 					break;
-				if ((matched = dowild(p, text,  force_lower_case)) != NOMATCH) {
-					if (!match_slash || matched != ABORT_TO_STARSTAR)
+				/*
+				 * Try to advance faster when an asterisk is
+				 * followed by a literal. We know in this case
+				 * that the the string before the literal
+				 * must belong to "*".
+				 * If match_slash is false, do not look past
+				 * the first slash as it cannot belong to '*'.
+				 */
+				if (!is_glob_special(*p)) {
+					p_ch = *p;
+					if ((flags & WM_CASEFOLD) && ISUPPER(p_ch))
+						p_ch = tolower(p_ch);
+					while ((t_ch = *text) != '\0' &&
+					       (match_slash || t_ch != '/')) {
+						if ((flags & WM_CASEFOLD) && ISUPPER(t_ch))
+							t_ch = tolower(t_ch);
+						if (t_ch == p_ch)
+							break;
+						text++;
+					}
+					if (t_ch != p_ch)
+						return WM_NOMATCH;
+				}
+				if ((matched = dowild(p, text, flags)) != WM_NOMATCH) {
+					if (!match_slash || matched != WM_ABORT_TO_STARSTAR)
 						return matched;
 				} else if (!match_slash && t_ch == '/')
-					return ABORT_TO_STARSTAR;
+					return WM_ABORT_TO_STARSTAR;
 				t_ch = *++text;
 			}
-			return ABORT_ALL;
+			return WM_ABORT_ALL;
 		case '[':
 			p_ch = *++p;
 #ifdef NEGATE_CLASS2
 			if (p_ch == NEGATE_CLASS2)
 				p_ch = NEGATE_CLASS;
 #endif
-			/* Assign literal TRUE/FALSE because of "matched" comparison. */
-			negated = p_ch == NEGATE_CLASS? TRUE : FALSE;
+			/* Assign literal 1/0 because of "matched" comparison. */
+			negated = p_ch == NEGATE_CLASS ? 1 : 0;
 			if (negated) {
 				/* Inverted character class. */
 				p_ch = *++p;
 			}
 			prev_ch = 0;
-			matched = FALSE;
+			matched = 0;
 			do {
 				if (!p_ch)
-					return ABORT_ALL;
+					return WM_ABORT_ALL;
 				if (p_ch == '\\') {
 					p_ch = *++p;
 					if (!p_ch)
-						return ABORT_ALL;
+						return WM_ABORT_ALL;
 					if (t_ch == p_ch)
-						matched = TRUE;
+						matched = 1;
 				} else if (p_ch == '-' && prev_ch && p[1] && p[1] != ']') {
 					p_ch = *++p;
 					if (p_ch == '\\') {
 						p_ch = *++p;
 						if (!p_ch)
-							return ABORT_ALL;
+							return WM_ABORT_ALL;
 					}
 					if (t_ch <= p_ch && t_ch >= prev_ch)
-						matched = TRUE;
+						matched = 1;
 					p_ch = 0; /* This makes "prev_ch" get set to 0. */
 				} else if (p_ch == '[' && p[1] == ':') {
 					const uchar *s;
 					int i;
 					for (s = p += 2; (p_ch = *p) && p_ch != ']'; p++) {} /*SHARED ITERATOR*/
 					if (!p_ch)
-						return ABORT_ALL;
+						return WM_ABORT_ALL;
 					i = p - s - 1;
 					if (i < 0 || p[-1] != ':') {
 						/* Didn't find ":]", so treat like a normal set. */
 						p = s - 2;
 						p_ch = '[';
 						if (t_ch == p_ch)
-							matched = TRUE;
+							matched = 1;
 						continue;
 					}
 					if (CC_EQ(s,i, "alnum")) {
 						if (ISALNUM(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else if (CC_EQ(s,i, "alpha")) {
 						if (ISALPHA(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else if (CC_EQ(s,i, "blank")) {
 						if (ISBLANK(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else if (CC_EQ(s,i, "cntrl")) {
 						if (ISCNTRL(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else if (CC_EQ(s,i, "digit")) {
 						if (ISDIGIT(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else if (CC_EQ(s,i, "graph")) {
 						if (ISGRAPH(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else if (CC_EQ(s,i, "lower")) {
 						if (ISLOWER(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else if (CC_EQ(s,i, "print")) {
 						if (ISPRINT(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else if (CC_EQ(s,i, "punct")) {
 						if (ISPUNCT(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else if (CC_EQ(s,i, "space")) {
 						if (ISSPACE(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else if (CC_EQ(s,i, "upper")) {
 						if (ISUPPER(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else if (CC_EQ(s,i, "xdigit")) {
 						if (ISXDIGIT(t_ch))
-							matched = TRUE;
+							matched = 1;
 					} else /* malformed [:class:] string */
-						return ABORT_ALL;
+						return WM_ABORT_ALL;
 					p_ch = 0; /* This makes "prev_ch" get set to 0. */
 				} else if (t_ch == p_ch)
-					matched = TRUE;
+					matched = 1;
 			} while (prev_ch = p_ch, (p_ch = *++p) != ']');
-			if (matched == negated || t_ch == '/')
-				return NOMATCH;
+			if (matched == negated ||
+			    ((flags & WM_PATHNAME) && t_ch == '/'))
+				return WM_NOMATCH;
 			continue;
 		}
 	}
 
-	return *text ? NOMATCH : MATCH;
+	return *text ? WM_NOMATCH : WM_MATCH;
 }
 
 /* Match the "pattern" against the "text" string. */
-int wildmatch(const char *pattern, const char *text, int flags)
+int wildmatch(const char *pattern, const char *text,
+	      unsigned int flags, struct wildopts *wo)
 {
-	return dowild((const uchar*)pattern, (const uchar*)text,
-		      flags & FNM_CASEFOLD ? 1 :0);
+	return dowild((const uchar*)pattern, (const uchar*)text, flags);
 }
diff --git a/wildmatch.h b/wildmatch.h
index 984a38cdc2..4090c8f4bb 100644
--- a/wildmatch.h
+++ b/wildmatch.h
@@ -1,9 +1,18 @@
-/* wildmatch.h */
+#ifndef WILDMATCH_H
+#define WILDMATCH_H
 
-#define ABORT_MALFORMED 2
-#define NOMATCH 1
-#define MATCH 0
-#define ABORT_ALL -1
-#define ABORT_TO_STARSTAR -2
+#define WM_CASEFOLD 1
+#define WM_PATHNAME 2
 
-int wildmatch(const char *pattern, const char *text, int flags);
+#define WM_ABORT_MALFORMED 2
+#define WM_NOMATCH 1
+#define WM_MATCH 0
+#define WM_ABORT_ALL -1
+#define WM_ABORT_TO_STARSTAR -2
+
+struct wildopts;
+
+int wildmatch(const char *pattern, const char *text,
+	      unsigned int flags,
+	      struct wildopts *wo);
+#endif