{"thread":{"id":"32138","subject":"[PATCH 0/4] Some pathspec wildcard optimization","startedAt":"2012-11-18T09:13:05Z","lastAt":"2012-11-20T19:47:53Z","messageCount":11,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Nguyen Thai Ngoc Duy"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"203459","messageId":"1353229989-13075-1-git-send-email-pclouds@gmail.com","threadId":"32138","inReplyTo":null,"subject":"[PATCH 0/4] Some pathspec wildcard optimization","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-11-18T09:13:05Z","receivedAt":"2012-11-18T09:13:05Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This ports the \"*.c\" optimization from .gitignore to pathspec code.\n\nNguyễn Thái Ngọc Duy (4):\n  pathspec: save the non-wildcard length part\n  pathspec: do exact comparison on the leading non-wildcard part\n  pathspec: apply \"*.c\" optimization from exclude\n  tree_entry_interesting: do basedir compare on wildcard patterns when\n    possible\n\n builtin/ls-files.c |  2 +-\n builtin/ls-tree.c  |  2 +-\n cache.h            |  5 +++-\n dir.c              | 35 ++++++++++++++++++++++---\n dir.h              |  9 +++++++\n tree-walk.c        | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++----\n 6 files changed, 117 insertions(+), 11 deletions(-)\n\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"203461","messageId":"1353229989-13075-2-git-send-email-pclouds@gmail.com","threadId":"32138","inReplyTo":"1353229989-13075-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 1/4] pathspec: save the non-wildcard length part","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-11-18T09:13:06Z","receivedAt":"2012-11-18T09:13:06Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"We marks pathspec with wildcards with the field use_wildcard. We could\ndo better by saving the length of the non-wildcard part, which can be\nfor optimizations such as f9f6e2c (exclude: do strcmp as much as\npossible before fnmatch - 2012-06-07)\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/ls-files.c | 2 +-\n builtin/ls-tree.c  | 2 +-\n cache.h            | 2 +-\n dir.c              | 6 +++---\n tree-walk.c        | 4 ++--\n 5 files changed, 8 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/ls-files.c b/builtin/ls-files.c\nindex b5434af..4a9ee69 100644\n--- a/builtin/ls-files.c\n+++ b/builtin/ls-files.c\n@@ -337,7 +337,7 @@ void overlay_tree_on_cache(const char *tree_name, const char *prefix)\n \t\tmatchbuf[0] = prefix;\n \t\tmatchbuf[1] = NULL;\n \t\tinit_pathspec(&pathspec, matchbuf);\n-\t\tpathspec.items[0].use_wildcard = 0;\n+\t\tpathspec.items[0].nowildcard_len = pathspec.items[0].len;\n \t} else\n \t\tinit_pathspec(&pathspec, NULL);\n \tif (read_tree(tree, 1, &pathspec))\ndiff --git a/builtin/ls-tree.c b/builtin/ls-tree.c\nindex 235c17c..fb76e38 100644\n--- a/builtin/ls-tree.c\n+++ b/builtin/ls-tree.c\n@@ -168,7 +168,7 @@ int cmd_ls_tree(int argc, const char **argv, const char *prefix)\n \n \tinit_pathspec(&pathspec, get_pathspec(prefix, argv + 1));\n \tfor (i = 0; i < pathspec.nr; i++)\n-\t\tpathspec.items[i].use_wildcard = 0;\n+\t\tpathspec.items[i].nowildcard_len = pathspec.items[i].len;\n \tpathspec.has_wildcard = 0;\n \ttree = parse_tree_indirect(sha1);\n \tif (!tree)\ndiff --git a/cache.h b/cache.h\nindex dbd8018..bf031f1 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -482,7 +482,7 @@ struct pathspec {\n \tstruct pathspec_item {\n \t\tconst char *match;\n \t\tint len;\n-\t\tunsigned int use_wildcard:1;\n+\t\tint nowildcard_len;\n \t} *items;\n };\n \ndiff --git a/dir.c b/dir.c\nindex 5a83aa7..c391d46 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -230,7 +230,7 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,\n \t\t\treturn MATCHED_RECURSIVELY;\n \t}\n \n-\tif (item->use_wildcard && !fnmatch(match, name, 0))\n+\tif (item->nowildcard_len < item->len && !fnmatch(match, name, 0))\n \t\treturn MATCHED_FNMATCH;\n \n \treturn 0;\n@@ -1429,8 +1429,8 @@ int init_pathspec(struct pathspec *pathspec, const char **paths)\n \n \t\titem->match = path;\n \t\titem->len = strlen(path);\n-\t\titem->use_wildcard = !no_wildcard(path);\n-\t\tif (item->use_wildcard)\n+\t\titem->nowildcard_len = simple_length(path);\n+\t\tif (item->nowildcard_len < item->len)\n \t\t\tpathspec->has_wildcard = 1;\n \t}\n \ndiff --git a/tree-walk.c b/tree-walk.c\nindex 3f54c02..af871c5 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -626,7 +626,7 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,\n \t\t\t\t\t&never_interesting))\n \t\t\t\treturn entry_interesting;\n \n-\t\t\tif (item->use_wildcard) {\n+\t\t\tif (item->nowildcard_len < item->len) {\n \t\t\t\tif (!fnmatch(match + baselen, entry->path, 0))\n \t\t\t\t\treturn entry_interesting;\n \n@@ -642,7 +642,7 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,\n \t\t}\n \n match_wildcards:\n-\t\tif (!item->use_wildcard)\n+\t\tif (item->nowildcard_len == item->len)\n \t\t\tcontinue;\n \n \t\t/*\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"293731","messageId":"1353229989-13075-3-git-send-email-pclouds@gmail.com","threadId":"32138","inReplyTo":"1353229989-13075-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/4] pathspec: do exact comparison on the leading non-wildcard part","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-11-18T09:13:07Z","receivedAt":"2012-11-18T09:13:07Z","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 <pclouds@gmail.com>\n---\n dir.c       | 18 +++++++++++++++++-\n dir.h       |  8 ++++++++\n tree-walk.c |  6 ++++--\n 3 files changed, 29 insertions(+), 3 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex c391d46..e4e6ca1 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -34,6 +34,21 @@ int fnmatch_icase(const char *pattern, const char *string, int flags)\n \treturn fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));\n }\n \n+inline int git_fnmatch(const char *pattern, const char *string,\n+\t\t       int flags, int prefix)\n+{\n+\tint fnm_flags = 0;\n+\tif (flags & GF_PATHNAME)\n+\t\tfnm_flags |= FNM_PATHNAME;\n+\tif (prefix > 0) {\n+\t\tif (strncmp(pattern, string, prefix))\n+\t\t\treturn FNM_NOMATCH;\n+\t\tpattern += prefix;\n+\t\tstring += prefix;\n+\t}\n+\treturn fnmatch(pattern, string, fnm_flags);\n+}\n+\n static size_t common_prefix_len(const char **pathspec)\n {\n \tconst char *n, *first;\n@@ -230,7 +245,8 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,\n \t\t\treturn MATCHED_RECURSIVELY;\n \t}\n \n-\tif (item->nowildcard_len < item->len && !fnmatch(match, name, 0))\n+\tif (item->nowildcard_len < item->len &&\n+\t    !git_fnmatch(match, name, 0, item->nowildcard_len - prefix))\n \t\treturn MATCHED_FNMATCH;\n \n \treturn 0;\ndiff --git a/dir.h b/dir.h\nindex f5c89e3..4cd5074 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -139,4 +139,12 @@ extern int strcmp_icase(const char *a, const char *b);\n extern int strncmp_icase(const char *a, const char *b, size_t count);\n extern int fnmatch_icase(const char *pattern, const char *string, int flags);\n \n+/*\n+ * The prefix part of pattern must not contains wildcards.\n+ */\n+#define GF_PATHNAME 1\n+\n+extern int git_fnmatch(const char *pattern, const char *string,\n+\t\t       int flags, int prefix);\n+\n #endif\ndiff --git a/tree-walk.c b/tree-walk.c\nindex af871c5..2fcf3c0 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -627,7 +627,8 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,\n \t\t\t\treturn entry_interesting;\n \n \t\t\tif (item->nowildcard_len < item->len) {\n-\t\t\t\tif (!fnmatch(match + baselen, entry->path, 0))\n+\t\t\t\tif (!git_fnmatch(match + baselen, entry->path,\n+\t\t\t\t\t\t 0, item->nowildcard_len - baselen))\n \t\t\t\t\treturn entry_interesting;\n \n \t\t\t\t/*\n@@ -652,7 +653,8 @@ match_wildcards:\n \n \t\tstrbuf_add(base, entry->path, pathlen);\n \n-\t\tif (!fnmatch(match, base->buf + base_offset, 0)) {\n+\t\tif (!git_fnmatch(match, base->buf + base_offset,\n+\t\t\t\t 0, item->nowildcard_len)) {\n \t\t\tstrbuf_setlen(base, base_offset + baselen);\n \t\t\treturn entry_interesting;\n \t\t}\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"203460","messageId":"1353229989-13075-4-git-send-email-pclouds@gmail.com","threadId":"32138","inReplyTo":"1353229989-13075-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 3/4] pathspec: apply \"*.c\" optimization from exclude","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-11-18T09:13:08Z","receivedAt":"2012-11-18T09:13:08Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"-O2 build on linux-2.6, without the patch:\n\n$ time git rev-list --quiet HEAD -- '*.c'\n\nreal    0m40.770s\nuser    0m40.290s\nsys     0m0.256s\n\nWith the patch\n\n$ time ~/w/git/git rev-list --quiet HEAD -- '*.c'\n\nreal    0m34.288s\nuser    0m33.997s\nsys     0m0.205s\n\nThe above command is not supposed to be widely popular. It's chosen\nbecause it exercises pathspec matching a lot. The point is it cuts\ndown matching time for popular patterns like *.c, which could be used\nas pathspec in other places.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n cache.h     |  3 +++\n dir.c       | 17 +++++++++++++++--\n dir.h       |  1 +\n tree-walk.c |  6 ++++--\n 4 files changed, 23 insertions(+), 4 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex bf031f1..d18f584 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -473,6 +473,8 @@ extern int index_name_is_other(const struct index_state *, const char *, int);\n extern int ie_match_stat(const struct index_state *, struct cache_entry *, struct stat *, unsigned int);\n extern int ie_modified(const struct index_state *, struct cache_entry *, struct stat *, unsigned int);\n \n+#define PSF_ONESTAR 1\n+\n struct pathspec {\n \tconst char **raw; /* get_pathspec() result, not freed by free_pathspec() */\n \tint nr;\n@@ -483,6 +485,7 @@ struct pathspec {\n \t\tconst char *match;\n \t\tint len;\n \t\tint nowildcard_len;\n+\t\tint flags;\n \t} *items;\n };\n \ndiff --git a/dir.c b/dir.c\nindex e4e6ca1..d00f240 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -46,6 +46,12 @@ inline int git_fnmatch(const char *pattern, const char *string,\n \t\tpattern += prefix;\n \t\tstring += prefix;\n \t}\n+\tif (flags & GF_ONESTAR) {\n+\t\tint pattern_len = strlen(++pattern);\n+\t\tint string_len = strlen(string);\n+\t\treturn strcmp(pattern,\n+\t\t\t      string + string_len - pattern_len);\n+\t}\n \treturn fnmatch(pattern, string, fnm_flags);\n }\n \n@@ -246,7 +252,9 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,\n \t}\n \n \tif (item->nowildcard_len < item->len &&\n-\t    !git_fnmatch(match, name, 0, item->nowildcard_len - prefix))\n+\t    !git_fnmatch(match, name,\n+\t\t\t item->flags & PSF_ONESTAR ? GF_ONESTAR : 0,\n+\t\t\t item->nowildcard_len - prefix))\n \t\treturn MATCHED_FNMATCH;\n \n \treturn 0;\n@@ -1446,8 +1454,13 @@ int init_pathspec(struct pathspec *pathspec, const char **paths)\n \t\titem->match = path;\n \t\titem->len = strlen(path);\n \t\titem->nowildcard_len = simple_length(path);\n-\t\tif (item->nowildcard_len < item->len)\n+\t\titem->flags = 0;\n+\t\tif (item->nowildcard_len < item->len) {\n \t\t\tpathspec->has_wildcard = 1;\n+\t\t\tif (path[item->nowildcard_len] == '*' &&\n+\t\t\t    no_wildcard(path + item->nowildcard_len + 1))\n+\t\t\t\titem->flags |= PSF_ONESTAR;\n+\t\t}\n \t}\n \n \tqsort(pathspec->items, pathspec->nr,\ndiff --git a/dir.h b/dir.h\nindex 4cd5074..590532b 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -143,6 +143,7 @@ extern int fnmatch_icase(const char *pattern, const char *string, int flags);\n  * The prefix part of pattern must not contains wildcards.\n  */\n #define GF_PATHNAME 1\n+#define GF_ONESTAR  2\n \n extern int git_fnmatch(const char *pattern, const char *string,\n \t\t       int flags, int prefix);\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 2fcf3c0..42fe610 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -628,7 +628,8 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,\n \n \t\t\tif (item->nowildcard_len < item->len) {\n \t\t\t\tif (!git_fnmatch(match + baselen, entry->path,\n-\t\t\t\t\t\t 0, item->nowildcard_len - baselen))\n+\t\t\t\t\t\t item->flags & PSF_ONESTAR ? GF_ONESTAR : 0,\n+\t\t\t\t\t\t item->nowildcard_len - baselen))\n \t\t\t\t\treturn entry_interesting;\n \n \t\t\t\t/*\n@@ -654,7 +655,8 @@ match_wildcards:\n \t\tstrbuf_add(base, entry->path, pathlen);\n \n \t\tif (!git_fnmatch(match, base->buf + base_offset,\n-\t\t\t\t 0, item->nowildcard_len)) {\n+\t\t\t\t item->flags & PSF_ONESTAR ? GF_ONESTAR : 0,\n+\t\t\t\t item->nowildcard_len)) {\n \t\t\tstrbuf_setlen(base, base_offset + baselen);\n \t\t\treturn entry_interesting;\n \t\t}\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"203462","messageId":"1353229989-13075-5-git-send-email-pclouds@gmail.com","threadId":"32138","inReplyTo":"1353229989-13075-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 4/4] tree_entry_interesting: do basedir compare on wildcard patterns when possible","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-11-18T09:13:09Z","receivedAt":"2012-11-18T09:13:09Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Currently we treat \"*.c\" and \"path/to/*.c\" the same way. Which means\nwe check all possible paths in repo against \"path/to/*.c\". One could\nsee that \"path/elsewhere/foo.c\" obviously cannot match \"path/to/*.c\"\nand we only need to check all paths _inside_ \"path/to/\" against that\npattern.\n\nThis patch checks the leading fixed part of a pathspec against base\ndirectory and exit early if possible. We could even optimize further\nin \"path/to/something*.c\" case (i.e. check the fixed part against\nname_entry as well) but that's more complicated and probably does not\ngain us much.\n\n-O2 build on linux-2.6, without and with this patch respectively:\n\n$ time git rev-list --quiet HEAD -- 'drivers/*.c'\n\nreal    1m9.484s\nuser    1m9.128s\nsys     0m0.181s\n\n$ time ~/w/git/git rev-list --quiet HEAD -- 'drivers/*.c'\n\nreal    0m15.710s\nuser    0m15.564s\nsys     0m0.107s\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n tree-walk.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 62 insertions(+), 1 deletion(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 42fe610..dcc1015 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -573,6 +573,52 @@ static int match_dir_prefix(const char *base,\n }\n \n /*\n+ * Perform matching on the leading non-wildcard part of\n+ * pathspec. item->nowildcard_len must be greater than zero. Return\n+ * non-zero if base is matched.\n+ */\n+static int match_wildcard_base(const struct pathspec_item *item,\n+\t\t\t       const char *base, int baselen,\n+\t\t\t       int *matched)\n+{\n+\tconst char *match = item->match;\n+\t/* the wildcard part is not considered in this function */\n+\tint matchlen = item->nowildcard_len;\n+\n+\tif (baselen) {\n+\t\tint dirlen;\n+\t\t/*\n+\t\t * Return early if base is longer than the\n+\t\t * non-wildcard part but it does not match.\n+\t\t */\n+\t\tif (baselen >= matchlen) {\n+\t\t\t*matched = matchlen;\n+\t\t\treturn !strncmp(base, match, matchlen);\n+\t\t}\n+\n+\t\tdirlen = matchlen;\n+\t\twhile (dirlen && match[dirlen - 1] != '/')\n+\t\t\tdirlen--;\n+\n+\t\t/* Return early if base is shorter than the\n+\t\t   non-wildcard part but it does not match. Note that\n+\t\t   base ends with '/' so we are sure it really matches\n+\t\t   directory */\n+\t\tif (strncmp(base, match, baselen))\n+\t\t\treturn 0;\n+\t\t*matched = baselen;\n+\t} else\n+\t\t*matched = 0;\n+\t/*\n+\t * we could have checked entry against the non-wildcard part\n+\t * that is not in base and does similar never_interesting\n+\t * optimization as in match_entry. For now just be happy with\n+\t * base comparison.\n+\t */\n+\treturn entry_interesting;\n+}\n+\n+/*\n  * Is a tree entry interesting given the pathspec we have?\n  *\n  * Pre-condition: either baselen == base_offset (i.e. empty path)\n@@ -602,7 +648,7 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,\n \t\tconst struct pathspec_item *item = ps->items+i;\n \t\tconst char *match = item->match;\n \t\tconst char *base_str = base->buf + base_offset;\n-\t\tint matchlen = item->len;\n+\t\tint matchlen = item->len, matched = 0;\n \n \t\tif (baselen >= matchlen) {\n \t\t\t/* If it doesn't match, move along... */\n@@ -647,9 +693,24 @@ match_wildcards:\n \t\tif (item->nowildcard_len == item->len)\n \t\t\tcontinue;\n \n+\t\tif (item->nowildcard_len &&\n+\t\t    !match_wildcard_base(item, base_str, baselen, &matched))\n+\t\t\treturn entry_not_interesting;\n+\n \t\t/*\n \t\t * Concatenate base and entry->path into one and do\n \t\t * fnmatch() on it.\n+\t\t *\n+\t\t * While we could avoid concatenation in certain cases\n+\t\t * [1], which saves a memcpy and potentially a\n+\t\t * realloc, it turns out not worth it. Measurement on\n+\t\t * linux-2.6 does not show any clear improvements,\n+\t\t * partly because of the nowildcard_len optimization\n+\t\t * in git_fnmatch(). Avoid micro-optimizations here.\n+\t\t *\n+\t\t * [1] if match_wildcard_base() says the base\n+\t\t * directory is already matched, we only need to match\n+\t\t * the rest, which is shorter so _in theory_ faster.\n \t\t */\n \n \t\tstrbuf_add(base, entry->path, pathlen);\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"203515","messageId":"7v6251wao5.fsf@alter.siamese.dyndns.org","threadId":"32138","inReplyTo":"1353229989-13075-2-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 1/4] pathspec: save the non-wildcard length part","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-11-19T20:48:35Z","receivedAt":"2012-11-19T20:48:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n> We marks pathspec with wildcards with the field use_wildcard. We could\n\ns/marks/mark;\n\n> do better by saving the length of the non-wildcard part, which can be\n> for optimizations such as f9f6e2c (exclude: do strcmp as much as\n\ns/for /used &/;\n\n> possible before fnmatch - 2012-06-07)\n>\n> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n\nThe code looks straightforward and correct.  Thanks.\n\n> ---\n>  builtin/ls-files.c | 2 +-\n>  builtin/ls-tree.c  | 2 +-\n>  cache.h            | 2 +-\n>  dir.c              | 6 +++---\n>  tree-walk.c        | 4 ++--\n>  5 files changed, 8 insertions(+), 8 deletions(-)\n>\n> diff --git a/builtin/ls-files.c b/builtin/ls-files.c\n> index b5434af..4a9ee69 100644\n> --- a/builtin/ls-files.c\n> +++ b/builtin/ls-files.c\n> @@ -337,7 +337,7 @@ void overlay_tree_on_cache(const char *tree_name, const char *prefix)\n>  \t\tmatchbuf[0] = prefix;\n>  \t\tmatchbuf[1] = NULL;\n>  \t\tinit_pathspec(&pathspec, matchbuf);\n> -\t\tpathspec.items[0].use_wildcard = 0;\n> +\t\tpathspec.items[0].nowildcard_len = pathspec.items[0].len;\n>  \t} else\n>  \t\tinit_pathspec(&pathspec, NULL);\n>  \tif (read_tree(tree, 1, &pathspec))\n> diff --git a/builtin/ls-tree.c b/builtin/ls-tree.c\n> index 235c17c..fb76e38 100644\n> --- a/builtin/ls-tree.c\n> +++ b/builtin/ls-tree.c\n> @@ -168,7 +168,7 @@ int cmd_ls_tree(int argc, const char **argv, const char *prefix)\n>  \n>  \tinit_pathspec(&pathspec, get_pathspec(prefix, argv + 1));\n>  \tfor (i = 0; i < pathspec.nr; i++)\n> -\t\tpathspec.items[i].use_wildcard = 0;\n> +\t\tpathspec.items[i].nowildcard_len = pathspec.items[i].len;\n>  \tpathspec.has_wildcard = 0;\n>  \ttree = parse_tree_indirect(sha1);\n>  \tif (!tree)\n> diff --git a/cache.h b/cache.h\n> index dbd8018..bf031f1 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -482,7 +482,7 @@ struct pathspec {\n>  \tstruct pathspec_item {\n>  \t\tconst char *match;\n>  \t\tint len;\n> -\t\tunsigned int use_wildcard:1;\n> +\t\tint nowildcard_len;\n>  \t} *items;\n>  };\n>  \n> diff --git a/dir.c b/dir.c\n> index 5a83aa7..c391d46 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -230,7 +230,7 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,\n>  \t\t\treturn MATCHED_RECURSIVELY;\n>  \t}\n>  \n> -\tif (item->use_wildcard && !fnmatch(match, name, 0))\n> +\tif (item->nowildcard_len < item->len && !fnmatch(match, name, 0))\n>  \t\treturn MATCHED_FNMATCH;\n>  \n>  \treturn 0;\n> @@ -1429,8 +1429,8 @@ int init_pathspec(struct pathspec *pathspec, const char **paths)\n>  \n>  \t\titem->match = path;\n>  \t\titem->len = strlen(path);\n> -\t\titem->use_wildcard = !no_wildcard(path);\n> -\t\tif (item->use_wildcard)\n> +\t\titem->nowildcard_len = simple_length(path);\n> +\t\tif (item->nowildcard_len < item->len)\n>  \t\t\tpathspec->has_wildcard = 1;\n>  \t}\n>  \n> diff --git a/tree-walk.c b/tree-walk.c\n> index 3f54c02..af871c5 100644\n> --- a/tree-walk.c\n> +++ b/tree-walk.c\n> @@ -626,7 +626,7 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,\n>  \t\t\t\t\t&never_interesting))\n>  \t\t\t\treturn entry_interesting;\n>  \n> -\t\t\tif (item->use_wildcard) {\n> +\t\t\tif (item->nowildcard_len < item->len) {\n>  \t\t\t\tif (!fnmatch(match + baselen, entry->path, 0))\n>  \t\t\t\t\treturn entry_interesting;\n>  \n> @@ -642,7 +642,7 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,\n>  \t\t}\n>  \n>  match_wildcards:\n> -\t\tif (!item->use_wildcard)\n> +\t\tif (item->nowildcard_len == item->len)\n>  \t\t\tcontinue;\n>  \n>  \t\t/*\n"},{"id":"203516","messageId":"7vzk2duw3m.fsf@alter.siamese.dyndns.org","threadId":"32138","inReplyTo":"1353229989-13075-3-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 2/4] pathspec: do exact comparison on the leading non-wildcard part","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-11-19T20:54:45Z","receivedAt":"2012-11-19T20:54:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n> ---\n>  dir.c       | 18 +++++++++++++++++-\n>  dir.h       |  8 ++++++++\n>  tree-walk.c |  6 ++++--\n>  3 files changed, 29 insertions(+), 3 deletions(-)\n>\n> diff --git a/dir.c b/dir.c\n> index c391d46..e4e6ca1 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -34,6 +34,21 @@ int fnmatch_icase(const char *pattern, const char *string, int flags)\n>  \treturn fnmatch(pattern, string, flags | (ignore_case ? FNM_CASEFOLD : 0));\n>  }\n>  \n> +inline int git_fnmatch(const char *pattern, const char *string,\n> +\t\t       int flags, int prefix)\n> +{\n> +\tint fnm_flags = 0;\n> +\tif (flags & GF_PATHNAME)\n> +\t\tfnm_flags |= FNM_PATHNAME;\n> +\tif (prefix > 0) {\n> +\t\tif (strncmp(pattern, string, prefix))\n> +\t\t\treturn FNM_NOMATCH;\n> +\t\tpattern += prefix;\n> +\t\tstring += prefix;\n> +\t}\n> +\treturn fnmatch(pattern, string, fnm_flags);\n\nHow would we protect this optimization from future breakages?\n\nOnce we start using FNM_PERIOD, this becomes unsafe, as the simple\npart in \"foo/bar*baz\" would be \"foo/bar\" with remainder \"*baz\".\n\nThe pattern \"foo/bar*baz\" should match \"foo/bar.baz\" with FNM_PERIOD\nset.  But with this optimization, fnmatch is fed pattern=\"*baz\",\nstring=\".baz\" and they would not match.\n"},{"id":"203517","messageId":"7vtxsluw3k.fsf@alter.siamese.dyndns.org","threadId":"32138","inReplyTo":"1353229989-13075-4-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 3/4] pathspec: apply \"*.c\" optimization from exclude","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-11-19T21:20:09Z","receivedAt":"2012-11-19T21:20:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n> -O2 build on linux-2.6, without the patch:\n\nBefore the result, can you briefly explain what '\"*.c\" optimization\nfrom exclude' the title talks about is?\n\n    When a pattern contains only a single asterisk, e.g. \"foo*bar\",\n    after literally comparing the leading part \"foo\" with the\n    string, we can compare the tail of the string and make sure it\n    matches \"bar\", instead of running fnmatch() on \"*bar\" against\n    the remainder of the string.\n\nThe funny thing was that trying to explain what the logic should do\nmakes one realize potential issues in the implementation of that\nlogic ;-)  See below.\n\n> $ time git rev-list --quiet HEAD -- '*.c'\n>\n> real    0m40.770s\n> user    0m40.290s\n> sys     0m0.256s\n>\n> With the patch\n>\n> $ time ~/w/git/git rev-list --quiet HEAD -- '*.c'\n>\n> real    0m34.288s\n> user    0m33.997s\n> sys     0m0.205s\n>\n> The above command is not supposed to be widely popular.\n\nHrm, perhaps.  I use \"git grep <pattern> -- \\*.c\" quite a lot, but\nhaven't seen use case for \\*.c in the context of the \"log\" family.\n\n> diff --git a/cache.h b/cache.h\n> index bf031f1..d18f584 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -473,6 +473,8 @@ extern int index_name_is_other(const struct index_state *, const char *, int);\n>  extern int ie_match_stat(const struct index_state *, struct cache_entry *, struct stat *, unsigned int);\n>  extern int ie_modified(const struct index_state *, struct cache_entry *, struct stat *, unsigned int);\n>  \n> +#define PSF_ONESTAR 1\n\nTogether with the GF_ prefix in the previous, PSF_ prefix needs a\nbit of in-code explanation.  Is it just an RC3L (random combination\nof 3 letters?)\n\n> @@ -46,6 +46,12 @@ inline int git_fnmatch(const char *pattern, const char *string,\n>  \t\tpattern += prefix;\n>  \t\tstring += prefix;\n>  \t}\n> +\tif (flags & GF_ONESTAR) {\n> +\t\tint pattern_len = strlen(++pattern);\n> +\t\tint string_len = strlen(string);\n> +\t\treturn strcmp(pattern,\n> +\t\t\t      string + string_len - pattern_len);\n> +\t}\n\nWhat happens when pattern=\"foo*oob\" and string=\"foob\"?\n\nThe prefix match before this code determines that the literal prefix\nin the pattern matches with the early part of the string, and makes\npattern=\"*oob\" and string=\"b\".\n\nWhen you come to strcmp(), you see that string_len is 1, pattern_len\nis 3, and pattern is \"oob\".  string+string_len-pattern_len = \"oob\",\none past the beginning of the original string \"foob\".  They match.\n\nOops?\n\n\treturn (string_len < pattern_len) ||\n        \tstrcmp(pattern, string + string_len - pattern_len);\n\nperhaps?\n"},{"id":"203558","messageId":"CACsJy8DqTR12sckwMm_Zzv2UbdX6jvvyFm3Fx9-b8a-NVXWL9g@mail.gmail.com","threadId":"32138","inReplyTo":"7vzk2duw3m.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/4] pathspec: do exact comparison on the leading non-wildcard part","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-11-20T13:09:50Z","receivedAt":"2012-11-20T13:09:50Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Nov 20, 2012 at 3:54 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> How would we protect this optimization from future breakages?\n>\n> Once we start using FNM_PERIOD, this becomes unsafe, as the simple\n> part in \"foo/bar*baz\" would be \"foo/bar\" with remainder \"*baz\".\n>\n> The pattern \"foo/bar*baz\" should match \"foo/bar.baz\" with FNM_PERIOD\n> set.  But with this optimization, fnmatch is fed pattern=\"*baz\",\n> string=\".baz\" and they would not match.\n\nThe first question is how FNM_PERIOD comes in the first place without\nbreaking the current syntax. I guess we just turn off the optimization\nif FNM_PERIOD is used.\n\nMy secret \"plan\" is to convert all fnmatch() calls to git_fnmatch()\nthen replace fnmatch() with wildmatch() and move these optimization\ndown to wildmatch(). I think we can handle FNM_PERIOD case better down\nthere because string is still \"foo/bar.baz\".\n-- \nDuy\n"},{"id":"203559","messageId":"CACsJy8C=vdvHYgMr8Qa7M+Mq=QO6p6dsOFm_ZW=Nf2VQrPwaMg@mail.gmail.com","threadId":"32138","inReplyTo":"7vtxsluw3k.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/4] pathspec: apply \"*.c\" optimization from exclude","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-11-20T13:23:35Z","receivedAt":"2012-11-20T13:23:35Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Nov 20, 2012 at 4:20 AM, Junio C Hamano <gitster@pobox.com> wrote:\n>> $ time git rev-list --quiet HEAD -- '*.c'\n>>\n>> real    0m40.770s\n>> user    0m40.290s\n>> sys     0m0.256s\n>>\n>> With the patch\n>>\n>> $ time ~/w/git/git rev-list --quiet HEAD -- '*.c'\n>>\n>> real    0m34.288s\n>> user    0m33.997s\n>> sys     0m0.205s\n>>\n>> The above command is not supposed to be widely popular.\n>\n> Hrm, perhaps.  I use \"git grep <pattern> -- \\*.c\" quite a lot, but\n> haven't seen use case for \\*.c in the context of the \"log\" family.\n\n\"git diff *.c\" is also helpful (maybe \"git diff *.[ch]\" is more often\nused). But I suspect I/O dominates in both grep and diff cases. I just\ntry to make sure matching code won't show up in profile.\n\n\n>> +#define PSF_ONESTAR 1\n>\n> Together with the GF_ prefix in the previous, PSF_ prefix needs a\n> bit of in-code explanation.  Is it just an RC3L (random combination\n> of 3 letters?)\n\nI'm pretty sure \"PS\" stands for pathspec. \"F\" is probably from\nfnmatch. Any suggestions?\n\n\n>> @@ -46,6 +46,12 @@ inline int git_fnmatch(const char *pattern, const char *string,\n>>               pattern += prefix;\n>>               string += prefix;\n>>       }\n>> +     if (flags & GF_ONESTAR) {\n>> +             int pattern_len = strlen(++pattern);\n>> +             int string_len = strlen(string);\n>> +             return strcmp(pattern,\n>> +                           string + string_len - pattern_len);\n>> +     }\n>\n> What happens when pattern=\"foo*oob\" and string=\"foob\"?\n>\n> The prefix match before this code determines that the literal prefix\n> in the pattern matches with the early part of the string, and makes\n> pattern=\"*oob\" and string=\"b\".\n>\n> When you come to strcmp(), you see that string_len is 1, pattern_len\n> is 3, and pattern is \"oob\".  string+string_len-pattern_len = \"oob\",\n> one past the beginning of the original string \"foob\".  They match.\n>\n> Oops?\n\nOops indead. I'll need to check exclude code too :(\n\n\n>         return (string_len < pattern_len) ||\n>                 strcmp(pattern, string + string_len - pattern_len);\n>\n> perhaps?\n\nYeah.\n-- \nDuy\n"},{"id":"203565","messageId":"7vlidwrr86.fsf@alter.siamese.dyndns.org","threadId":"32138","inReplyTo":"CACsJy8C=vdvHYgMr8Qa7M+Mq=QO6p6dsOFm_ZW=Nf2VQrPwaMg@mail.gmail.com","subject":"Re: [PATCH 3/4] pathspec: apply \"*.c\" optimization from exclude","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-11-20T19:47:53Z","receivedAt":"2012-11-20T19:47:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:\n\n>> When you come to strcmp(), you see that string_len is 1, pattern_len\n>> is 3, and pattern is \"oob\".  string+string_len-pattern_len = \"oob\",\n>> one past the beginning of the original string \"foob\".  They match.\n>>\n>> Oops?\n>\n> Oops indead. I'll need to check exclude code too :(\n\nOk, the one queued on 'pu' has been locally fixed when I sent the\nmessage you are responding to.\n"}]}