{"thread":{"id":"56031","subject":"git log exclude pathspec from file - supported? plans?","startedAt":"2021-06-30T16:59:58Z","lastAt":"2021-07-01T21:43:27Z","messageCount":8,"participants":["Martin Langhoff","Jeff King","Ævar Arnfjörð Bjarmason"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"428832","messageId":"CACPiFCLXxwaWOuR6sy8H4hCG-H0ZFvVYma7COfDq3zxoUt=VtA@mail.gmail.com","threadId":"56031","inReplyTo":"CACPiFCLtj5QF6_Goc5UYh9KHWgkrKtjApL-cCH04S5gdTFyk7Q@mail.gmail.com","subject":"git log exclude pathspec from file - supported? plans?","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2021-06-30T16:59:43Z","receivedAt":"2021-06-30T16:59:58Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"Hi Git Gang!\n\nlong time no see! I'm doing some complex git repo spelunking and\npushing the boundaries of the pathspec magic for excludes.\n\nIs there a reasonable way to provide a (potentially large) set of\nexcludes? something like\n\n     git log --exclude-pathspec-file paths-to-exclude.txt .\n\nHas there been discussion / patches / plans related to this? I may\nhave some cycles (hopefully!)\n\ncheers,\n\n\nm\n-- \n martin.langhoff@gmail.com\n - ask interesting questions  ~  http://linkedin.com/in/martinlanghoff\n - don't be distracted        ~  http://github.com/martin-langhoff\n   by shiny stuff\n"},{"id":"428843","messageId":"YNywsEbFcrQFeH91@coredump.intra.peff.net","threadId":"56031","inReplyTo":"CACPiFCLXxwaWOuR6sy8H4hCG-H0ZFvVYma7COfDq3zxoUt=VtA@mail.gmail.com","subject":"Re: git log exclude pathspec from file - supported? plans?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-06-30T17:58:08Z","receivedAt":"2021-06-30T17:58:11Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 30, 2021 at 12:59:43PM -0400, Martin Langhoff wrote:\n\n> long time no see! I'm doing some complex git repo spelunking and\n> pushing the boundaries of the pathspec magic for excludes.\n> \n> Is there a reasonable way to provide a (potentially large) set of\n> excludes? something like\n> \n>      git log --exclude-pathspec-file paths-to-exclude.txt .\n> \n> Has there been discussion / patches / plans related to this? I may\n> have some cycles (hopefully!)\n\nYou can feed pathspecs via --stdin. So:\n\n  {\n\techo \"--\"\n\tsed s/^/:^/ paths-to-exclude.txt\n  } | git log --stdin\n\nworks. Obviously it's not as turn-key if you really do have a list of\npaths in a file already, but it's much more flexible.\n\nI'll caution you that the pathspec code is not well-optimized to handle\na large number of pathspecs. E.g.:\n\n  [no pathspecs]\n  $ time git rev-list HEAD /dev/null\n  real\t0m0.033s\n  user\t0m0.017s\n  sys\t0m0.017s\n\n  [trivial pathspec; now we have to actually open up trees]\n  $ { echo --; echo .; } >input\n  $ time git rev-list HEAD --stdin <input >/dev/null\n  real\t0m1.338s\n  user\t0m1.294s\n  sys\t0m0.045s\n\n  [lots of pathspecs; now we spend loads of time actually matching\n   strings; the ^C is when I got bored and killed it]\n  $ { echo --; git ls-files; } >input\n  $ time git rev-list HEAD --stdin <input >/dev/null\n  ^C\n  real\t1m24.406s\n  user\t1m24.369s\n  sys\t0m0.036s\n\nThe problem is that we try to linearly match every pathspec against\nevery path we consider, so it's quadratic-ish in the number of files in\nthe repo. I played a long time ago with storing non-wildcard pathspecs\nin a trie that we could traverse as we talked the individual trees we\nwere matching. It performed well, but IIRC the interface was hacky (I\nhad to bolt it specifically onto the way the tree-walker uses\npathspecs, and the other pathspec matchers didn't benefit at all).\n\nI can probably dig it up if anybody's interested in looking at it.\n\n-Peff\n"},{"id":"428849","messageId":"87sg0zdx7z.fsf@evledraar.gmail.com","threadId":"56031","inReplyTo":"YNywsEbFcrQFeH91@coredump.intra.peff.net","subject":"Re: git log exclude pathspec from file - supported? plans?","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-06-30T18:22:35Z","receivedAt":"2021-06-30T18:27:34Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Wed, Jun 30 2021, Jeff King wrote:\n\n> On Wed, Jun 30, 2021 at 12:59:43PM -0400, Martin Langhoff wrote:\n>\n>> long time no see! I'm doing some complex git repo spelunking and\n>> pushing the boundaries of the pathspec magic for excludes.\n>> \n>> Is there a reasonable way to provide a (potentially large) set of\n>> excludes? something like\n>> \n>>      git log --exclude-pathspec-file paths-to-exclude.txt .\n>> \n>> Has there been discussion / patches / plans related to this? I may\n>> have some cycles (hopefully!)\n>\n> You can feed pathspecs via --stdin. So:\n>\n>   {\n> \techo \"--\"\n> \tsed s/^/:^/ paths-to-exclude.txt\n>   } | git log --stdin\n>\n> works. Obviously it's not as turn-key if you really do have a list of\n> paths in a file already, but it's much more flexible.\n>\n> I'll caution you that the pathspec code is not well-optimized to handle\n> a large number of pathspecs. E.g.:\n>\n>   [no pathspecs]\n>   $ time git rev-list HEAD /dev/null\n>   real\t0m0.033s\n>   user\t0m0.017s\n>   sys\t0m0.017s\n>\n>   [trivial pathspec; now we have to actually open up trees]\n>   $ { echo --; echo .; } >input\n>   $ time git rev-list HEAD --stdin <input >/dev/null\n>   real\t0m1.338s\n>   user\t0m1.294s\n>   sys\t0m0.045s\n>\n>   [lots of pathspecs; now we spend loads of time actually matching\n>    strings; the ^C is when I got bored and killed it]\n>   $ { echo --; git ls-files; } >input\n>   $ time git rev-list HEAD --stdin <input >/dev/null\n>   ^C\n>   real\t1m24.406s\n>   user\t1m24.369s\n>   sys\t0m0.036s\n>\n> The problem is that we try to linearly match every pathspec against\n> every path we consider, so it's quadratic-ish in the number of files in\n> the repo. I played a long time ago with storing non-wildcard pathspecs\n> in a trie that we could traverse as we talked the individual trees we\n> were matching. It performed well, but IIRC the interface was hacky (I\n> had to bolt it specifically onto the way the tree-walker uses\n> pathspecs, and the other pathspec matchers didn't benefit at all).\n>\n> I can probably dig it up if anybody's interested in looking at it.\n\nIf it's not too much trouble I'd find it interesting, but I likely won't\ndo anything with it any time soon.\n\nOne of the PCREv2 experiments I had very early WIP work towards was to\ncreate a search index for commit messages, contents etc. and stick it in\nsomething similar to the --changed-paths part of the commit-graph.\n\nThe PCREv2 codebase actually has (supposedly) a bug-for-bug compatible\nimplementation of our wildmatch function as a translator to a PCREv2\nregex, I have a brnch somewhere where we run all our wildmatch tests\nagainst it successfully.\n\nSo couple that with regex introspection, and a search index that\ne.g. creates a trie bloom filter, then as long as your --grep=<RX>,\n-G<RX> or pathspec has at least 3 fixed strings among its wildcards we\ncan ask the bloom filter \"is this commit a candidate for this regex\nsearching this path/commit message/diff/whatever\".\n\nSo you can have indexed matches for things like '*/test-lib.sh\", not\njust prefixes or fixed-strings.\n"},{"id":"428984","messageId":"YN4zKVK7gvuIZ0vK@coredump.intra.peff.net","threadId":"56031","inReplyTo":"87sg0zdx7z.fsf@evledraar.gmail.com","subject":"Re: git log exclude pathspec from file - supported? plans?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-01T21:27:05Z","receivedAt":"2021-07-01T21:27:09Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 30, 2021 at 08:22:35PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> > The problem is that we try to linearly match every pathspec against\n> > every path we consider, so it's quadratic-ish in the number of files in\n> > the repo. I played a long time ago with storing non-wildcard pathspecs\n> > in a trie that we could traverse as we talked the individual trees we\n> > were matching. It performed well, but IIRC the interface was hacky (I\n> > had to bolt it specifically onto the way the tree-walker uses\n> > pathspecs, and the other pathspec matchers didn't benefit at all).\n> >\n> > I can probably dig it up if anybody's interested in looking at it.\n> \n> If it's not too much trouble I'd find it interesting, but I likely won't\n> do anything with it any time soon.\n\nThe patches are from 2014 (yikes). I forward ported them to the current\ntip of master, but beware:\n\n  - it fails a test in t4010 matching a gitlink with a trailing \"/\" in the\n    pathspec (which I think just didn't exist back then). I suspect this\n    is a simple bug (the trie has to record a bit for \"this must be a\n    dir\", and it probably just doesn't understand gitlinks properly).\n\n  - the original renamed diff_tree_sha1() to diff_tree_sha1_recurse(),\n    which we then call internally while recursing (to pass the trie\n    cursor). And then top-level calls use a diff_tree_sha1() wrapper\n    that kicks off the traversal (to avoid disrupting other callers).\n\n    When forward-porting, those functions got renamed and reorganized to\n    handle multi-parent diffs. I was able to just use the internal\n    ll_diff_tree_paths() as my \"recurse\" version, but I'm not 100% sure\n    that's right (e.g., should internal calls to ll_diff_tree_oid also\n    grow a cursor parameter?)\n\n  - a few bits had to be ported from the 2-parent case to handle\n    n-parents. It _looked_ pretty trivial as I did it, but it's entirely\n    possible there are gotchas. Tests seem to pass, though (there are no\n    specific tests for finding changes in a merge here, but all tree\n    diffs should be using the new code).\n\n  - there are a few basic tests included, but this was never run in any\n    kind of production setting. Caveat emptor. :)\n\n> One of the PCREv2 experiments I had very early WIP work towards was to\n> create a search index for commit messages, contents etc. and stick it in\n> something similar to the --changed-paths part of the commit-graph.\n\nYeah, to some degree --change-paths may mitigate this, since for a\nseries of simple pathspecs we'd generate the bloom filter once and then\nget O(1) matching per commit.\n\nMy ulterior motive with all of this was to plug it into our custom\n\"blame-tree\" (i.e., which commit last-touched each path), with the idea\nbeing that we'd start with a big pathspec, and then shrink it as we find\nanswers. Removing an item from a bloom filter is awkward, but possible.\n\nAnyway, here are the patches.\n\n  [1/3]: pathspec: add optional trie index\n  [2/3]: pathspec: turn on tries when appropriate\n  [3/3]: tree-diff: use pathspec tries\n\n Makefile                      |   1 +\n pathspec.c                    | 127 ++++++++++++++++++++++++++++++++++\n pathspec.h                    |  13 ++++\n t/helper/test-pathspec.c      |  96 +++++++++++++++++++++++++\n t/helper/test-tool.c          |   1 +\n t/helper/test-tool.h          |   1 +\n t/perf/p4002-diff-pathspec.sh |  26 +++++++\n t/t6137-pathspec-trie.sh      |  57 +++++++++++++++\n tree-diff.c                   | 102 +++++++++++++++++++++++----\n 9 files changed, 411 insertions(+), 13 deletions(-)\n create mode 100644 t/helper/test-pathspec.c\n create mode 100755 t/perf/p4002-diff-pathspec.sh\n create mode 100755 t/t6137-pathspec-trie.sh\n\n-Peff\n"},{"id":"428985","messageId":"YN4z9cIrph/OBvw6@coredump.intra.peff.net","threadId":"56031","inReplyTo":"YN4zKVK7gvuIZ0vK@coredump.intra.peff.net","subject":"[PATCH 1/3] pathspec: add optional trie index","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-01T21:30:29Z","receivedAt":"2021-07-01T21:30:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When checking if a path matches our pathspec list, in the\nworst case we walk the whole list linearly to check each\npathspec.  As a result, an operation like a tree diff does\n`O(paths * pathspecs)` comparisons. If we assume that the\nnumber of pathspecs may approach the number of paths, this\nis `O(n^2)` in the number of paths.  We have to do it this\nway in the general case because pathspecs may be arbitrary\nfnmatch expressions, and we cannot create any meaningful\nindex.\n\nHowever, it is common that all of the pathspecs are vanilla\nprefixes (e.g., \"git.c\" or \"Documentation/\") that do not use\nany wildcards or magic features. In such a case, we can\nindex the pathspec list to give us faster lookups.\n\nThe simplest solution would be to keep the pathspec list\nsorted, and use a binary search over the entries for each\npath. This turns out to be rather tricky, though, as we are\nnot looking for an exact match in the list. We must also\nfind prefix matches, and take care to handle trailing\nslashes for directories.\n\nInstead, this patch introduces a pathspec_trie struct, which\nrepresents the pathspecs as a graph of entries. For\nexample, the pathspec list [\"foo/bar\", \"foo/baz/\"] would be\nrepresented as:\n\n        (bar, terminal)\n       /\n  (foo)\n       \\\n        (baz, terminal, must_be_dir)\n\nTo see if a path \"foo/eek\" is covered by the pathspec, we\nwalk the trie, matching \"foo\" but ultimately seeing that\n\"eek\" is not mentioned.\n\nThis provides us with two optimizations:\n\n  1. The children of each trie node are simple strings\n     representing directory components. This means we can sort\n     and binary-search them, giving us logarithmic lookups\n     (but note that rather than one log lookup on the whole\n     pathname, it is a sequence of smaller log lookups on\n     components of the pathname).\n\n  2. Many users of the pathspec code do not feed full\n     pathnames, but instead are walking a tree hierarchy\n     themselves, and limiting the walk as they go. They can\n     walk the trie at the same time, meanining they avoid\n     looking repeatedly at parts of the pathspec we already\n     know are matched. The current code, by contrast, will\n     repeatedly match \"foo/\" against each pathspec when\n     looking at \"foo/bar\", \"foo/baz\", etc.\n\nNote that this patch just introduces the data structure; the\ncode is not used anywhere yet.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n Makefile                 |   1 +\n pathspec.c               | 125 +++++++++++++++++++++++++++++++++++++++\n pathspec.h               |  12 ++++\n t/helper/test-pathspec.c |  98 ++++++++++++++++++++++++++++++\n t/helper/test-tool.c     |   1 +\n t/helper/test-tool.h     |   1 +\n t/t6137-pathspec-trie.sh |  57 ++++++++++++++++++\n 7 files changed, 295 insertions(+)\n create mode 100644 t/helper/test-pathspec.c\n create mode 100755 t/t6137-pathspec-trie.sh\n\ndiff --git a/Makefile b/Makefile\nindex c3565fc0f8..675f51a330 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -726,6 +726,7 @@ TEST_BUILTINS_OBJS += test-online-cpus.o\n TEST_BUILTINS_OBJS += test-parse-options.o\n TEST_BUILTINS_OBJS += test-parse-pathspec-file.o\n TEST_BUILTINS_OBJS += test-path-utils.o\n+TEST_BUILTINS_OBJS += test-pathspec.o\n TEST_BUILTINS_OBJS += test-pcre2-config.o\n TEST_BUILTINS_OBJS += test-pkt-line.o\n TEST_BUILTINS_OBJS += test-prio-queue.o\ndiff --git a/pathspec.c b/pathspec.c\nindex 08f8d3eedc..24a24f627e 100644\n--- a/pathspec.c\n+++ b/pathspec.c\n@@ -760,3 +760,128 @@ int match_pathspec_attrs(struct index_state *istate,\n \n \treturn 1;\n }\n+\n+/*\n+ * This is basically a strcmp, but we do not want the caller\n+ * to have to terminate \"a\", so we pretend as if it had a NUL.\n+ */\n+static int pathspec_trie_cmp(const char *a, size_t a_len,\n+\t\t\t     const char *b)\n+{\n+\tint ret = strncmp(a, b, a_len);\n+\treturn ret ?\n+\t\tret :\n+\t\t(unsigned char)0 - (unsigned char )b[a_len];\n+}\n+\n+/*\n+ * Do a binary search on one level of the pathspec_trie. If found,\n+ * returns the offset of the item in the entry list. If not found,\n+ * return a negative value encoding the offset where it would be inserted\n+ * (you can recover the true offset with \"-pos - 1\").\n+ */\n+int pathspec_trie_lookup(const struct pathspec_trie *parent,\n+\t\t\t const char *path, size_t len)\n+{\n+\tint lo = 0, hi = parent->nr;\n+\twhile (lo < hi) {\n+\t\tint mi = lo + ((hi - lo) / 2);\n+\t\tint cmp;\n+\n+\t\tcmp = pathspec_trie_cmp(path, len, parent->entries[mi]->path);\n+\t\tif (!cmp)\n+\t\t\treturn mi;\n+\t\tif (cmp < 0)\n+\t\t\thi = mi;\n+\t\telse\n+\t\t\tlo = mi + 1;\n+\t}\n+\treturn -lo - 1;\n+}\n+\n+static struct pathspec_trie *alloc_pathspec_trie(const char *path, size_t len)\n+{\n+\tstruct pathspec_trie *ret = xcalloc(1, sizeof(*ret) + len);\n+\tmemcpy(ret->path, path, len);\n+\treturn ret;\n+}\n+\n+/*\n+ * Add \"path\" to the trie rooted at \"t\".\n+ */\n+static void add_pathspec_trie(struct pathspec_trie *t, const char *path)\n+{\n+\t/*\n+\t * Special case the empty path (i.e., \".\"), as our splitting algorithm\n+\t * below assumes at least one component.\n+\t */\n+\tif (!*path) {\n+\t\tt->terminal = 1;\n+\t\treturn;\n+\t}\n+\n+\twhile (1) {\n+\t\tconst char *slash = strchrnul(path, '/');\n+\t\tsize_t len = slash - path;\n+\t\tint pos;\n+\n+\t\tpos = pathspec_trie_lookup(t, path, len);\n+\t\tif (pos < 0) {\n+\t\t\tALLOC_GROW(t->entries, t->nr + 1, t->alloc);\n+\n+\t\t\tpos = -pos - 1;\n+\t\t\tif (pos < t->nr)\n+\t\t\t\tmemmove(t->entries + pos + 1,\n+\t\t\t\t\tt->entries + pos,\n+\t\t\t\t\tsizeof(*t->entries) * (t->nr - pos));\n+\t\t\tt->entries[pos] = alloc_pathspec_trie(path, len);\n+\t\t\tt->nr++;\n+\t\t}\n+\n+\t\tt = t->entries[pos];\n+\t\tpath += len;\n+\n+\t\tif (!*path) {\n+\t\t\tt->must_be_dir = 0;\n+\t\t\tt->terminal = 1;\n+\t\t\treturn;\n+\t\t}\n+\n+\t\twhile (*path == '/')\n+\t\t\tpath++;\n+\t\tif (!*path) {\n+\t\t\t/*\n+\t\t\t * if we were already a terminal, then do not set\n+\t\t\t * must_be_dir; we are \"foo/\", but we already had a\n+\t\t\t * pathspec \"foo\", which is a superset of us.\n+\t\t\t */\n+\t\t\tif (!t->terminal)\n+\t\t\t\tt->must_be_dir = 1;\n+\t\t\tt->terminal = 1;\n+\t\t\treturn;\n+\t\t}\n+\t}\n+}\n+\n+struct pathspec_trie *build_pathspec_trie(const struct pathspec *pathspec)\n+{\n+\tstruct pathspec_trie *ret;\n+\tint i;\n+\n+\t/* we only make a trie for plain-vanilla pathspecs */\n+\tif (pathspec->has_wildcard || (pathspec->magic & ~PATHSPEC_LITERAL))\n+\t\treturn NULL;\n+\n+\tret = alloc_pathspec_trie(\"\", 0);\n+\n+\t/*\n+\t * XXX we could construct the trie more efficiently by creating each\n+\t * node with all of its entries in sorted order. But this is much\n+\t * simpler, and since we only do this once at the start of a traversal,\n+\t * it's probably fast enough.\n+\t */\n+\tfor (i = 0; i < pathspec->nr; i++)\n+\t\tadd_pathspec_trie(ret, pathspec->items[i].match);\n+\n+\treturn ret;\n+}\ndiff --git a/pathspec.h b/pathspec.h\nindex fceebb876f..15c9244d08 100644\n--- a/pathspec.h\n+++ b/pathspec.h\n@@ -22,6 +22,14 @@ struct index_state;\n \n #define PATHSPEC_ONESTAR 1\t/* the pathspec pattern satisfies GFNM_ONESTAR */\n \n+struct pathspec_trie {\n+\tstruct pathspec_trie **entries;\n+\tint nr, alloc;\n+\tunsigned terminal:1,\n+\t\t must_be_dir:1;\n+\tchar path[FLEX_ARRAY];\n+};\n+\n /**\n  * See glossary-context.txt for the syntax of pathspec.\n  * In memory, a pathspec set is represented by \"struct pathspec\" and is\n@@ -172,4 +180,8 @@ int match_pathspec_attrs(struct index_state *istate,\n \t\t\t const char *name, int namelen,\n \t\t\t const struct pathspec_item *item);\n \n+struct pathspec_trie *build_pathspec_trie(const struct pathspec *);\n+int pathspec_trie_lookup(const struct pathspec_trie *pst,\n+\t\t\t const char *path, size_t len);\n+\n #endif /* PATHSPEC_H */\ndiff --git a/t/helper/test-pathspec.c b/t/helper/test-pathspec.c\nnew file mode 100644\nindex 0000000000..3f1b8f1a79\n--- /dev/null\n+++ b/t/helper/test-pathspec.c\n@@ -0,0 +1,98 @@\n+#include \"test-tool.h\"\n+#include \"pathspec.h\"\n+\n+static const char usage_msg[] =\n+\"test-tool pathspec trie [pathspecs...] -- [paths....]\";\n+\n+/*\n+ * XXX Yuck. This is a lot of complicated code specific to our test. Even if it\n+ * runs correctly, we have no real guarantee that the actual trie users are\n+ * doing it right. And reusing their code is tough, because it happens as part\n+ * of their own traversals (e.g., we walk the pathspec trie while walking the\n+ * tree objects themselves).\n+ *\n+ * This whole test program should probably go away in favor of directly testing\n+ * the tree-diff code.\n+ */\n+static int trie_match(const struct pathspec_trie *pst,\n+\t\t      const char *path)\n+{\n+\tint pathlen = strlen(path);\n+\tint is_dir = 0;\n+\n+\tif (pathlen > 0 && path[pathlen-1] == '/') {\n+\t\tis_dir = 1;\n+\t\tpathlen--;\n+\t}\n+\n+\twhile (pathlen) {\n+\t\tconst char *slash = memchr(path, '/', pathlen);\n+\t\tint component_len;\n+\t\tint pos;\n+\n+\t\tif (slash)\n+\t\t\tcomponent_len = slash - path;\n+\t\telse\n+\t\t\tcomponent_len = pathlen;\n+\n+\t\tpos = pathspec_trie_lookup(pst, path, component_len);\n+\t\tif (pos < 0)\n+\t\t\treturn 0;\n+\n+\t\tpst = pst->entries[pos];\n+\t\tpath += component_len;\n+\t\tpathlen -= component_len;\n+\n+\t\twhile (pathlen && *path == '/') {\n+\t\t\tpath++;\n+\t\t\tpathlen--;\n+\t\t}\n+\n+\t\tif (pst->terminal) {\n+\t\t\tif (!pst->must_be_dir)\n+\t\t\t\treturn 1;\n+\t\t\tif (pathlen)\n+\t\t\t\treturn 1;\n+\t\t\treturn is_dir;\n+\t\t}\n+\t}\n+\treturn 0;\n+}\n+\n+static int cmd_trie(const char **argv)\n+{\n+\tconst char **specs, **paths;\n+\tstruct pathspec pathspec;\n+\tstruct pathspec_trie *trie;\n+\n+\tpaths = specs = argv;\n+\twhile (*paths && strcmp(*paths, \"--\"))\n+\t\tpaths++;\n+\tif (*paths)\n+\t\t*paths++ = NULL;\n+\n+\tparse_pathspec(&pathspec, 0, 0, \"\", specs);\n+\ttrie = build_pathspec_trie(&pathspec);\n+\tif (!trie)\n+\t\tdie(\"unable to make trie from pathspec\");\n+\n+\tfor (; *paths; paths++) {\n+\t\tif (trie_match(trie, *paths))\n+\t\t\tprintf(\"yes\\n\");\n+\t\telse\n+\t\t\tprintf(\"no\\n\");\n+\t}\n+\treturn 0;\n+}\n+\n+int cmd__pathspec(int argc, const char **argv)\n+{\n+\tconst char *cmd = argv[1];\n+\n+\tif (!cmd)\n+\t\tusage(usage_msg);\n+\telse if (!strcmp(cmd, \"trie\"))\n+\t\treturn cmd_trie(argv + 2);\n+\telse\n+\t\tdie(\"unknown cmd: %s\", cmd);\n+}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex c5bd0c6d4c..c5dc6153e0 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -47,6 +47,7 @@ static struct test_cmd cmds[] = {\n \t{ \"parse-options\", cmd__parse_options },\n \t{ \"parse-pathspec-file\", cmd__parse_pathspec_file },\n \t{ \"path-utils\", cmd__path_utils },\n+\t{ \"pathspec\", cmd__pathspec },\n \t{ \"pcre2-config\", cmd__pcre2_config },\n \t{ \"pkt-line\", cmd__pkt_line },\n \t{ \"prio-queue\", cmd__prio_queue },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex e8069a3b22..878aba1bc8 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -35,6 +35,7 @@ int cmd__oidmap(int argc, const char **argv);\n int cmd__online_cpus(int argc, const char **argv);\n int cmd__parse_options(int argc, const char **argv);\n int cmd__parse_pathspec_file(int argc, const char** argv);\n+int cmd__pathspec(int argc, const char **argv);\n int cmd__path_utils(int argc, const char **argv);\n int cmd__pcre2_config(int argc, const char **argv);\n int cmd__pkt_line(int argc, const char **argv);\ndiff --git a/t/t6137-pathspec-trie.sh b/t/t6137-pathspec-trie.sh\nnew file mode 100755\nindex 0000000000..ca2935c7db\n--- /dev/null\n+++ b/t/t6137-pathspec-trie.sh\n@@ -0,0 +1,57 @@\n+#!/bin/sh\n+\n+test_description='test optimized pathspec trie lookup'\n+. ./test-lib.sh\n+\n+# This is a basic lookup test; the offsets are there to provide\n+# some variation in where we land in our binary search.\n+ps=\"faa fzz foo/bar foo/baa foo/bzz\"\n+for offset in a \"a b\" \"a b c\"; do\n+\ttest_expect_success \"lookups with ps=$offset $ps\" \"\n+\t\tcat >expect <<-\\\\EOF &&\n+\t\tno\n+\t\tyes\n+\t\tyes\n+\t\tno\n+\t\tEOF\n+\t\ttest-tool pathspec trie $offset $ps -- f faa foo/bar foo/baz >actual &&\n+\t\ttest_cmp expect actual\n+\t\"\n+done\n+\n+test_expect_success 'pathspecs match by prefix' '\n+\tcat >expect <<-\\EOF &&\n+\tyes\n+\tyes\n+\tyes\n+\tEOF\n+\ttest-tool pathspec trie foo -- foo foo/bar foo/with/deep/subdirs >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'trailing slash sets must_be_dir' '\n+\tcat >expect <<-\\EOF &&\n+\tno\n+\tyes\n+\tyes\n+\tEOF\n+\ttest-tool pathspec trie dir/ -- dir dir/ dir/foo\n+'\n+\n+test_expect_success 'overlapping pathspecs allow the \"loose\" side' '\n+\techo yes >expect &&\n+\ttest-tool pathspec trie foo foo/ -- foo >actual &&\n+\ttest_cmp expect actual &&\n+\ttest-tool pathspec trie foo/ foo -- foo >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success '\".\" at the root matches everything' '\n+\tcat >expect <<-\\EOF &&\n+\tyes\n+\tyes\n+\tEOF\n+\ttest-tool pathspec trie . -- foo foo/bar\n+'\n+\n+test_done\n-- \n2.32.0.359.g3de86e008e.dirty\n\n"},{"id":"428986","messageId":"YN40B00vK2ul6yMW@coredump.intra.peff.net","threadId":"56031","inReplyTo":"YN4zKVK7gvuIZ0vK@coredump.intra.peff.net","subject":"[PATCH 2/3] pathspec: turn on tries when appropriate","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-01T21:30:47Z","receivedAt":"2021-07-01T21:30:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"An earlier commit introduced pathspec_tries, but we did not\nactually generate them by default. This patch causes us to\ndo so when it is possible (i.e., when no wildcards or other\npathspec magic are in use). This doesn't actually do\nanything yet, though, as none of the pathspec users have\nlearned to make use of the tries.\n\nWe embed the pathspec_trie directly inside the \"struct\npathspec\". This is not strictly necessary, as once created,\nthe trie does not depend on the original pathspec. However,\nsince the intended use is to optimize existing pathspec\ncallers, passing the trie around as part of the pathspec\nwill minimize disruption to the call chain.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n pathspec.c               | 2 ++\n pathspec.h               | 1 +\n t/helper/test-pathspec.c | 6 ++----\n 3 files changed, 5 insertions(+), 4 deletions(-)\n\ndiff --git a/pathspec.c b/pathspec.c\nindex 24a24f627e..435dfd3117 100644\n--- a/pathspec.c\n+++ b/pathspec.c\n@@ -639,6 +639,8 @@ void parse_pathspec(struct pathspec *pathspec,\n \t\t\tBUG(\"PATHSPEC_MAXDEPTH_VALID and PATHSPEC_KEEP_ORDER are incompatible\");\n \t\tQSORT(pathspec->items, pathspec->nr, pathspec_item_cmp);\n \t}\n+\n+\tpathspec->trie = build_pathspec_trie(pathspec);\n }\n \n void parse_pathspec_file(struct pathspec *pathspec, unsigned magic_mask,\ndiff --git a/pathspec.h b/pathspec.h\nindex 15c9244d08..5329c0a6f6 100644\n--- a/pathspec.h\n+++ b/pathspec.h\n@@ -61,6 +61,7 @@ struct pathspec {\n \t\t} *attr_match;\n \t\tstruct attr_check *attr_check;\n \t} *items;\n+\tstruct pathspec_trie *trie;\n };\n \n #define GUARD_PATHSPEC(ps, mask) \\\ndiff --git a/t/helper/test-pathspec.c b/t/helper/test-pathspec.c\nindex 3f1b8f1a79..0fb059409b 100644\n--- a/t/helper/test-pathspec.c\n+++ b/t/helper/test-pathspec.c\n@@ -63,7 +63,6 @@ static int cmd_trie(const char **argv)\n {\n \tconst char **specs, **paths;\n \tstruct pathspec pathspec;\n-\tstruct pathspec_trie *trie;\n \n \tpaths = specs = argv;\n \twhile (*paths && strcmp(*paths, \"--\"))\n@@ -72,12 +71,11 @@ static int cmd_trie(const char **argv)\n \t\t*paths++ = NULL;\n \n \tparse_pathspec(&pathspec, 0, 0, \"\", specs);\n-\ttrie = build_pathspec_trie(&pathspec);\n-\tif (!trie)\n+\tif (!pathspec.trie)\n \t\tdie(\"unable to make trie from pathspec\");\n \n \tfor (; *paths; paths++) {\n-\t\tif (trie_match(trie, *paths))\n+\t\tif (trie_match(pathspec.trie, *paths))\n \t\t\tprintf(\"yes\\n\");\n \t\telse\n \t\t\tprintf(\"no\\n\");\n-- \n2.32.0.359.g3de86e008e.dirty\n\n"},{"id":"428987","messageId":"YN41crLqEwmRTy4G@coredump.intra.peff.net","threadId":"56031","inReplyTo":"YN4zKVK7gvuIZ0vK@coredump.intra.peff.net","subject":"[PATCH 3/3] tree-diff: use pathspec tries","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-01T21:36:50Z","receivedAt":"2021-07-01T21:36:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The tree-diff currently matches each pathspec against every\nentry of the tree. For the common case of a handful of\npathspecs, this is not a big deal. However, if you have a\nlarge number of pathspecs, it gets noticeably slow.\n\nNow that we have the pathspec_trie optimization, we can do\nmuch better (at least for simple cases without wildcards).\nHere are numbers for running \"git rev-list\" with limiting\npathspecs of varying sizes, both before and after this\npatch:\n\nTest                 origin              HEAD\n---------------------------------------------------------------\n4001.2: size=1       0.12(0.11+0.00)     0.12(0.12+0.00) +0.0%\n4001.3: size=2       0.17(0.16+0.00)     0.16(0.15+0.01) -5.9%\n4001.4: size=4       0.17(0.17+0.00)     0.17(0.17+0.00) +0.0%\n4001.5: size=8       0.21(0.20+0.00)     0.20(0.20+0.00) -4.8%\n4001.6: size=16      0.25(0.24+0.00)     0.21(0.20+0.00) -16.0%\n4001.7: size=32      0.31(0.31+0.00)     0.21(0.20+0.00) -32.3%\n4001.8: size=64      0.43(0.41+0.01)     0.21(0.21+0.00) -51.2%\n4001.9: size=128     0.73(0.72+0.00)     0.22(0.21+0.00) -69.9%\n4001.10: size=256    2.02(2.02+0.00)     0.37(0.36+0.00) -81.7%\n4001.11: size=512    6.78(6.78+0.00)     0.64(0.64+0.00) -90.6%\n4001.12: size=1024   23.67(23.67+0.02)   1.22(1.20+0.01) -94.8%\n\nFor small pathspecs, we produce no real difference (which is\ngood; we know we are asymptotically better, but we have not\nregressed our constant factor). Between 16 and 32 pathspecs we\nstart to see some small improvement, and the benefit keeps\ngrowing with the number of pathspecs.\n\nObviously these large-pathspec cases are unusual. But you\nmight use them, for example, if the pathspecs were generated\nprogramatically (e.g., if you want the history of all files\nthat are in Documentation/ _now_, not what was historically\never there, you would expand the pathspec at the current\ntree, and feed the result to rev-list).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThis commit message is the original from 2014. The perf script got\nbumped to p4002, but the results today are similar (actually, the\n\"before\" code is slower, but perhaps that's because we have a lot more\ncommits in git.git these days).\n\n t/perf/p4002-diff-pathspec.sh |  26 +++++++++\n tree-diff.c                   | 102 +++++++++++++++++++++++++++++-----\n 2 files changed, 115 insertions(+), 13 deletions(-)\n create mode 100755 t/perf/p4002-diff-pathspec.sh\n\ndiff --git a/t/perf/p4002-diff-pathspec.sh b/t/perf/p4002-diff-pathspec.sh\nnew file mode 100755\nindex 0000000000..3d35b3579d\n--- /dev/null\n+++ b/t/perf/p4002-diff-pathspec.sh\n@@ -0,0 +1,26 @@\n+#!/bin/sh\n+\n+test_description='diff performance with many pathspecs'\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+sizes='1 2 4 8 16 32 64 128 256 512 1024'\n+\n+test_expect_success 'create pathspec lists' '\n+\tgit ls-tree --name-only -r HEAD >all &&\n+\tfor i in $sizes; do\n+\t\t{\n+\t\t\tprintf \"%s\\n\" -- &&\n+\t\t\thead -$i all\n+\t\t} >ps-$i\n+\tdone\n+'\n+\n+for i in $sizes; do\n+\ttest_perf \"size=$i\" \"\n+\t\tgit rev-list HEAD --stdin <ps-$i >/dev/null\n+\t\"\n+done\n+\n+test_done\ndiff --git a/tree-diff.c b/tree-diff.c\nindex 1572615bd9..47836941dd 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -28,7 +28,8 @@\n static struct combine_diff_path *ll_diff_tree_paths(\n \tstruct combine_diff_path *p, const struct object_id *oid,\n \tconst struct object_id **parents_oid, int nparent,\n-\tstruct strbuf *base, struct diff_options *opt);\n+\tstruct strbuf *base, struct diff_options *opt,\n+\tstruct pathspec_trie *pst);\n static void ll_diff_tree_oid(const struct object_id *old_oid,\n \t\t\t     const struct object_id *new_oid,\n \t\t\t     struct strbuf *base, struct diff_options *opt);\n@@ -179,7 +180,7 @@ static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,\n static struct combine_diff_path *emit_path(struct combine_diff_path *p,\n \tstruct strbuf *base, struct diff_options *opt, int nparent,\n \tstruct tree_desc *t, struct tree_desc *tp,\n-\tint imin)\n+\tint imin, struct pathspec_trie *pst)\n {\n \tunsigned short mode;\n \tconst char *path;\n@@ -283,23 +284,95 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,\n \t\t\tparents_oid[i] = tpi_valid ? &tp[i].entry.oid : NULL;\n \t\t}\n \n+\t\t/*\n+\t\t * As we recurse through the tree objects, move through\n+\t\t * our pathspec trie, as well. The one exception is if\n+\t\t * we already hit a terminal node. This means we have a strict\n+\t\t * prefix match (e.g., \"foo/\" matched, and we are in\n+\t\t * \"foo/bar\"). We don't have to bother with checking the\n+\t\t * pathspec at all anymore in that case.\n+\t\t *\n+\t\t * Note that the \"pos < 0\" case should not happen here,\n+\t\t * as we would have skipped the tree entry as uninteresting\n+\t\t * earlier. As a safety measure, we turn off the trie\n+\t\t * optimization and fall back to doing regular pathspec\n+\t\t * matching in this case.\n+\t\t */\n+\t\tif (pst && !pst->terminal) {\n+\t\t\tint pos = pathspec_trie_lookup(pst, path, pathlen);\n+\t\t\tif (pos < 0)\n+\t\t\t\tpst = NULL;\n+\t\t\telse\n+\t\t\t\tpst = pst->entries[pos];\n+\t\t}\n+\n \t\tstrbuf_add(base, path, pathlen);\n \t\tstrbuf_addch(base, '/');\n-\t\tp = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt);\n+\t\tp = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt, pst);\n \t\tFAST_ARRAY_FREE(parents_oid, nparent);\n \t}\n \n \tstrbuf_setlen(base, old_baselen);\n \treturn p;\n }\n \n+static enum interesting match_pathspec_trie_entry(struct pathspec_trie *pst,\n+\t\t\t\t\t\t  const struct name_entry *entry)\n+{\n+\tint pos;\n+\n+\t/*\n+\t * If our base directory is matched, then everything below is\n+\t * interesting (i.e., a prefix match).\n+\t */\n+\tif (pst->terminal)\n+\t\treturn entry_interesting;\n+\n+\t/*\n+\t * Otherwise, look up the actual entry. If we don't mention it at all,\n+\t * it's definitely uninteresting. But furthermore, if we're at the\n+\t * end of our sorted list, we know that nothing after it is\n+\t * interesting, either.\n+\t *\n+\t * XXX It seems like we should have to make special consideration here\n+\t * for the sort order of trees. But tree_entry_interesting does not\n+\t * seem to. Is it OK, is tree_entry_interesting buggy too, or am I\n+\t * reading it wrong? This optimization gives substantial speedups, so\n+\t * we really need to keep it or something like it.\n+\t */\n+\tpos = pathspec_trie_lookup(pst, entry->path, tree_entry_len(entry));\n+\tif (pos < 0) {\n+\t\tif (-pos - 1 == pst->nr)\n+\t\t\treturn all_entries_not_interesting;\n+\t\telse\n+\t\t\treturn entry_not_interesting;\n+\t}\n+\n+\t/*\n+\t * We definitely have the entry. First we have to resolve any directory\n+\t * restrictions; if there aren't any, then it's definitely interesting.\n+\t *\n+\t * Note that we do not need to check the \"terminal\" flag of the\n+\t * resulting trie node. If it is not set, then this particular entry\n+\t * does not match our pathspec, but we do still need to traverse\n+\t * through it to get to the interesting things inside. It's interesting\n+\t * either way.\n+\t */\n+\tif (pst->entries[pos]->must_be_dir)\n+\t\treturn !!S_ISDIR(entry->mode);\n+\treturn entry_interesting;\n+}\n+\n static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,\n-\t\t\t       struct diff_options *opt)\n+\t\t\t       struct diff_options *opt,\n+\t\t\t       struct pathspec_trie *pst)\n {\n \tenum interesting match;\n \n \twhile (t->size) {\n-\t\tmatch = tree_entry_interesting(opt->repo->index, &t->entry,\n+\t\tmatch = pst ?\n+\t\t\tmatch_pathspec_trie_entry(pst, &t->entry) :\n+\t\t\ttree_entry_interesting(opt->repo->index, &t->entry,\n \t\t\t\t\t       base, 0, &opt->pathspec);\n \t\tif (match) {\n \t\t\tif (match == all_entries_not_interesting)\n@@ -310,7 +383,6 @@ static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,\n \t}\n }\n \n-\n /*\n  * generate paths for combined diff D(sha1,parents_oid[])\n  *\n@@ -406,7 +478,8 @@ static inline void update_tp_entries(struct tree_desc *tp, int nparent)\n static struct combine_diff_path *ll_diff_tree_paths(\n \tstruct combine_diff_path *p, const struct object_id *oid,\n \tconst struct object_id **parents_oid, int nparent,\n-\tstruct strbuf *base, struct diff_options *opt)\n+\tstruct strbuf *base, struct diff_options *opt,\n+\tstruct pathspec_trie *pst)\n {\n \tstruct tree_desc t, *tp;\n \tvoid *ttree, **tptree;\n@@ -438,9 +511,9 @@ static struct combine_diff_path *ll_diff_tree_paths(\n \t\t\tbreak;\n \n \t\tif (opt->pathspec.nr) {\n-\t\t\tskip_uninteresting(&t, base, opt);\n+\t\t\tskip_uninteresting(&t, base, opt, pst);\n \t\t\tfor (i = 0; i < nparent; i++)\n-\t\t\t\tskip_uninteresting(&tp[i], base, opt);\n+\t\t\t\tskip_uninteresting(&tp[i], base, opt, pst);\n \t\t}\n \n \t\t/* comparing is finished when all trees are done */\n@@ -505,7 +578,7 @@ static struct combine_diff_path *ll_diff_tree_paths(\n \n \t\t\t/* D += {δ(t,pi) if pi=p[imin];  \"+a\" if pi > p[imin]} */\n \t\t\tp = emit_path(p, base, opt, nparent,\n-\t\t\t\t\t&t, tp, imin);\n+\t\t\t\t\t&t, tp, imin, pst);\n \n \t\tskip_emit_t_tp:\n \t\t\t/* t↓,  ∀ pi=p[imin]  pi↓ */\n@@ -517,7 +590,7 @@ static struct combine_diff_path *ll_diff_tree_paths(\n \t\telse if (cmp < 0) {\n \t\t\t/* D += \"+t\" */\n \t\t\tp = emit_path(p, base, opt, nparent,\n-\t\t\t\t\t&t, /*tp=*/NULL, -1);\n+\t\t\t\t\t&t, /*tp=*/NULL, -1, pst);\n \n \t\t\t/* t↓ */\n \t\t\tupdate_tree_entry(&t);\n@@ -533,7 +606,7 @@ static struct combine_diff_path *ll_diff_tree_paths(\n \t\t\t}\n \n \t\t\tp = emit_path(p, base, opt, nparent,\n-\t\t\t\t\t/*t=*/NULL, tp, imin);\n+\t\t\t\t\t/*t=*/NULL, tp, imin, pst);\n \n \t\tskip_emit_tp:\n \t\t\t/* ∀ pi=p[imin]  pi↓ */\n@@ -555,7 +628,10 @@ struct combine_diff_path *diff_tree_paths(\n \tconst struct object_id **parents_oid, int nparent,\n \tstruct strbuf *base, struct diff_options *opt)\n {\n-\tp = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt);\n+\t/* XXX if base is not empty, we need to walk its paths\n+\t * to get to the right level of the trie */\n+\tp = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt,\n+\t\t\t       opt->pathspec.trie);\n \n \t/*\n \t * free pre-allocated last element, if any\n-- \n2.32.0.359.g3de86e008e.dirty\n"},{"id":"428988","messageId":"YN42+1dN8bML3tQ8@coredump.intra.peff.net","threadId":"56031","inReplyTo":"YN4zKVK7gvuIZ0vK@coredump.intra.peff.net","subject":"Re: git log exclude pathspec from file - supported? plans?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-01T21:43:23Z","receivedAt":"2021-07-01T21:43:27Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 01, 2021 at 05:27:05PM -0400, Jeff King wrote:\n\n> > One of the PCREv2 experiments I had very early WIP work towards was to\n> > create a search index for commit messages, contents etc. and stick it in\n> > something similar to the --changed-paths part of the commit-graph.\n> \n> Yeah, to some degree --change-paths may mitigate this, since for a\n> series of simple pathspecs we'd generate the bloom filter once and then\n> get O(1) matching per commit.\n\nThe timings for \"git rev-list\" I shared earlier were with commit-graphs,\nbut not with changed-path filters. They don't seem to help much, though.\n\nI suspect the reason is that they can never give a definite answer. They\ncan only say \"probably, yes, this commit is worth looking at\". And then\nwe have to do the same slow, linear pathspec match on that commit. And\nif your pathspec contains virtually every path in the first place, then\nthe answer from the bloom filters will always be \"probably, yes\".\n\nSo I guess they are not really a silver bullet here.\n\n-Peff\n"}]}