{"thread":{"id":"32183","subject":"[PATCH v2 0/4] nd/pathspec-wildcard","startedAt":"2012-11-24T04:33:47Z","lastAt":"2012-11-24T04:33:51Z","messageCount":5,"participants":["Nguyễn Thái Ngọc Duy"],"isPatch":true,"patchVersion":2,"patchTotal":4},"messages":[{"id":"203755","messageId":"1353731631-20593-1-git-send-email-pclouds@gmail.com","threadId":"32183","inReplyTo":null,"subject":"[PATCH v2 0/4] nd/pathspec-wildcard","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-11-24T04:33:47Z","receivedAt":"2012-11-24T04:33:47Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"The only change (apart from what Junio's made after I sent the series)\nis rename GF_* to GFNM_* and PSF_* to PATHSPEC_* with a brief explanation\nfor each flag.\n\n.gitignore code does not have \"foo*oob\" bug that the original series has.\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              | 36 +++++++++++++++++++++++---\n dir.h              |  9 +++++++\n tree-walk.c        | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++----\n 6 files changed, 118 insertions(+), 11 deletions(-)\n\n-- \n1.8.0.rc2.23.g1fb49df\n"},{"id":"203757","messageId":"1353731631-20593-2-git-send-email-pclouds@gmail.com","threadId":"32183","inReplyTo":"1353731631-20593-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 1/4] pathspec: save the non-wildcard length part","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-11-24T04:33:48Z","receivedAt":"2012-11-24T04:33:48Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"We mark pathspec with wildcards with the field use_wildcard. We\ncould do better by saving the length of the non-wildcard part, which\ncan be used for optimizations such as f9f6e2c (exclude: do strcmp as\nmuch as possible before fnmatch - 2012-06-07).\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\nSigned-off-by: Junio C Hamano <gitster@pobox.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":"203756","messageId":"1353731631-20593-3-git-send-email-pclouds@gmail.com","threadId":"32183","inReplyTo":"1353731631-20593-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 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-24T04:33:49Z","receivedAt":"2012-11-24T04:33:49Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"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\ndiff --git a/dir.c b/dir.c\nindex c391d46..f81e1d2 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 & GFNM_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..0e8ae84 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 GFNM_PATHNAME 1\t\t/* similar to FNM_PATHNAME */\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":"203758","messageId":"1353731631-20593-4-git-send-email-pclouds@gmail.com","threadId":"32183","inReplyTo":"1353731631-20593-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 3/4] pathspec: apply \"*.c\" optimization from exclude","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-11-24T04:33:50Z","receivedAt":"2012-11-24T04:33:50Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"When a pattern contains only a single asterisk as wildcard,\ne.g. \"foo*bar\", after literally comparing the leading part \"foo\" with\nthe string, we can compare the tail of the string and make sure it\nmatches \"bar\", instead of running fnmatch() on \"*bar\" against the\nremainder of the string.\n\n-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 The optimization's condition could be loosen to \"only one asterisk\"\n (iow, fixed-length wildcards are OK, e.g. \"abc[de]gh*.[ch]\") when we\n have a custom fnmatch implementation that supports dry-run, so it can\n parse the pattern and determine the actual string length of\n \"abc[de]gh\" and \".[ch]\". We would have something similar to regcomp in\n addition to git_fnmatch().\n\n cache.h     |  3 +++\n dir.c       | 18 ++++++++++++++++--\n dir.h       |  1 +\n tree-walk.c |  6 ++++--\n 4 files changed, 24 insertions(+), 4 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex bf031f1..babf9e5 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 PATHSPEC_ONESTAR 1\t/* the pathspec pattern sastisfies GFNM_ONESTAR */\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 f81e1d2..9afd388 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -46,6 +46,13 @@ inline int git_fnmatch(const char *pattern, const char *string,\n \t\tpattern += prefix;\n \t\tstring += prefix;\n \t}\n+\tif (flags & GFNM_ONESTAR) {\n+\t\tint pattern_len = strlen(++pattern);\n+\t\tint string_len = strlen(string);\n+\t\treturn string_len < pattern_len ||\n+\t\t       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 +253,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 & PATHSPEC_ONESTAR ? GFNM_ONESTAR : 0,\n+\t\t\t item->nowildcard_len - prefix))\n \t\treturn MATCHED_FNMATCH;\n \n \treturn 0;\n@@ -1446,8 +1455,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 |= PATHSPEC_ONESTAR;\n+\t\t}\n \t}\n \n \tqsort(pathspec->items, pathspec->nr,\ndiff --git a/dir.h b/dir.h\nindex 0e8ae84..ab5af42 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 GFNM_PATHNAME 1\t\t/* similar to FNM_PATHNAME */\n+#define GFNM_ONESTAR  2\t\t/* there is only _one_ wildcard, a star */\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..585899e 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 & PATHSPEC_ONESTAR ? GFNM_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 & PATHSPEC_ONESTAR ? GFNM_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":"203759","messageId":"1353731631-20593-5-git-send-email-pclouds@gmail.com","threadId":"32183","inReplyTo":"1353731631-20593-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 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-24T04:33:51Z","receivedAt":"2012-11-24T04:33:51Z","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>\nSigned-off-by: Junio C Hamano <gitster@pobox.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 585899e..9d6e59b 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"}]}