pathspec: apply "*.c" optimization from exclude

When a pattern contains only a single asterisk as wildcard,
e.g. "foo*bar", after literally comparing the leading part "foo" with
the string, we can compare the tail of the string and make sure it
matches "bar", instead of running fnmatch() on "*bar" against the
remainder of the string.

-O2 build on linux-2.6, without the patch:

$ time git rev-list --quiet HEAD -- '*.c'

real    0m40.770s
user    0m40.290s
sys     0m0.256s

With the patch

$ time ~/w/git/git rev-list --quiet HEAD -- '*.c'

real    0m34.288s
user    0m33.997s
sys     0m0.205s

The above command is not supposed to be widely popular. It's chosen
because it exercises pathspec matching a lot. The point is it cuts
down matching time for popular patterns like *.c, which could be used
as pathspec in other places.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 16 insertions, 2 deletions

diff --git a/dir.c b/dir.c
index f81e1d2917..9afd388604 100644
--- a/dir.c
+++ b/dir.c
@@ -46,6 +46,13 @@ inline int git_fnmatch(const char *pattern, const char *string,
 		pattern += prefix;
 		string += prefix;
 	}
+	if (flags & GFNM_ONESTAR) {
+		int pattern_len = strlen(++pattern);
+		int string_len = strlen(string);
+		return string_len < pattern_len ||
+		       strcmp(pattern,
+			      string + string_len - pattern_len);
+	}
 	return fnmatch(pattern, string, fnm_flags);
 }
 
@@ -246,7 +253,9 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,
 	}
 
 	if (item->nowildcard_len < item->len &&
-	    !git_fnmatch(match, name, 0, item->nowildcard_len - prefix))
+	    !git_fnmatch(match, name,
+			 item->flags & PATHSPEC_ONESTAR ? GFNM_ONESTAR : 0,
+			 item->nowildcard_len - prefix))
 		return MATCHED_FNMATCH;
 
 	return 0;
@@ -1446,8 +1455,13 @@ int init_pathspec(struct pathspec *pathspec, const char **paths)
 		item->match = path;
 		item->len = strlen(path);
 		item->nowildcard_len = simple_length(path);
-		if (item->nowildcard_len < item->len)
+		item->flags = 0;
+		if (item->nowildcard_len < item->len) {
 			pathspec->has_wildcard = 1;
+			if (path[item->nowildcard_len] == '*' &&
+			    no_wildcard(path + item->nowildcard_len + 1))
+				item->flags |= PATHSPEC_ONESTAR;
+		}
 	}
 
 	qsort(pathspec->items, pathspec->nr,