{"thread":{"id":"63201","subject":"[PATCH 0/8] Introduce git-blame-tree(1) command","startedAt":"2025-03-26T20:19:20Z","lastAt":"2025-04-01T09:29:54Z","messageCount":15,"participants":["Toon Claes","Taylor Blau","Jeff King","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":8},"messages":[{"id":"515111","messageId":"20250326-toon-blame-tree-v1-0-4173133f3786@iotcl.com","threadId":"63201","inReplyTo":null,"subject":"[PATCH 0/8] Introduce git-blame-tree(1) command","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-03-26T20:18:24Z","receivedAt":"2025-03-26T20:19:20Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"This is yet another attempt to upstream the builtin command\n`git-blame-tree(1)`. This command is similar to git-blame(1) and shows\nthe most recent modification to paths in a tree..\n\nThe last attempt (I'm aware of) was made by Ævar in 2023[1]. That\nseries was based of patches by Peff written in 2011[2].\n\nIn contrary to Ævar's attempt, my series implements the\n`git-blame-tree(1)` standalone command. Ævar suggested to only implement\nthe blame-tree subsystem, and test it through test-tool. But since the\ncommand line options of that test-tool subcommand were very similar to\nthe standalone command we want to land, I decided transfer the test-tool\nsubcommand into a real Git builtin. Also, nowadays if we want to test\nthe blame-tree subsystem independently, we should use clar unit tests\ninstead of test-tool.\n\nThis series brings back the --max-depth changes. I know Ævar removed\nthem because there was controversy, but I think they are relevant to\ninclude. And I want to open up the conversation again.\n\nAlso extra patches from Peff are included to implement pathspec tries.\nI've taken them from Peff's fork on GitHub[3], but they also have been\nposted to this mailing list[4].\n\nOther improvements I've made:\n\n* Rebase onto current master.\n\n* Remove the use of USE_THE_REPOSITORY_VARIABLE.\n\n* Fix various memory leaks.\n\n* Moved code from blame-tree.c to pathspec.c, as suggested in Peff's\n last patch on GitHub.\n\n* Updated the benchmark results in the last commit message, although the\n numbers were roughly the same.\n\nI don't expect this code to be deemed ready to merge, but I mainly want\nto gather as much feedback as possible and use it to iterate toward\nactually getting it merged.\n\nThere are some things I know that are missing, for example\n`--porcelain`, but those can be added in a follow-up. At the moment\nthere's one test marked `test_expect_failure`, but I was not able yet\nidentify that bug.\n\nSo, let me know what you think?\n\n--\nToon\n\n[1]: https://lore.kernel.org/git/patch-1.1-0ea849d900b-20230205T204104Z-avarab@gmail.com/\n[2]: https://lore.kernel.org/git/20110302164031.GA18233@sigill.intra.peff.net/\n[3]: https://github.com/peff/git/tree/jk/faster-blame-tree-wip\n[4]: https://lore.kernel.org/git/YN4zKVK7gvuIZ0vK@coredump.intra.peff.net/\n\n---\nJeff King (7):\n combine-diff: zero memory used for callback filepairs\n within_depth: fix return for empty path\n diff: teach tree-diff a max-depth parameter\n pathspec: add optional trie index\n pathspec: turn on tries when appropriate\n tree-diff: use pathspec tries\n blame-tree: narrow pathspec as we traverse\n\nToon Claes (1):\n blame-tree: introduce new subcommand to blame files\n\n .gitignore | 1 +\n Documentation/diff-options.adoc | 26 +++++\n Makefile | 3 +\n blame-tree.c | 216 ++++++++++++++++++++++++++++++++++++++++\n blame-tree.h | 43 ++++++++\n builtin.h | 1 +\n builtin/blame-tree.c | 67 +++++++++++++\n combine-diff.c | 2 +-\n diff-lib.c | 5 +\n diff.c | 18 ++++\n diff.h | 9 ++\n dir.c | 2 +-\n git.c | 1 +\n meson.build | 2 +\n pathspec.c | 216 ++++++++++++++++++++++++++++++++++++++++\n pathspec.h | 27 +++++\n t/helper/meson.build | 1 +\n t/helper/test-pathspec.c | 96 ++++++++++++++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 2 +\n t/meson.build | 3 +\n t/perf/p4003-diff-pathspec.sh | 26 +++++\n t/t4071-diff-max-depth.sh | 109 ++++++++++++++++++++\n t/t6137-pathspec-trie.sh | 57 +++++++++++\n t/t8020-blame-tree.sh | 142 ++++++++++++++++++++++++++\n tree-diff.c | 176 +++++++++++++++++++++++++++++---\n 26 files changed, 1235 insertions(+), 17 deletions(-)\n---\n\n\n\n---\n\nbase-commit: 683c54c999c301c2cd6f715c411407c413b1d84e\nchange-id: 20250326-toon-blame-tree-2ca74d7712ac\n\nThanks\n--\nToon\n\n"},{"id":"515112","messageId":"20250326-toon-blame-tree-v1-1-4173133f3786@iotcl.com","threadId":"63201","inReplyTo":"20250326-toon-blame-tree-v1-0-4173133f3786@iotcl.com","subject":"[PATCH 1/8] combine-diff: zero memory used for callback filepairs","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-03-26T20:18:25Z","receivedAt":"2025-03-26T20:19:31Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"From: Jeff King \n\nIn commit 25e5e2bf85 (combine-diff: support format_callback,\n2011-08-19), the combined-diff code learned how to make a multi-sourced\ndiff_filepair to pass to a diff callback. When we create each filepair,\nwe do not bother to fill in many of the fields, because they would make\nno sense (e.g., there can be no rename score or broken_pair flag because\nwe do not go through the diffcore filters). However, we did not even\nbother to zero them, leading to random values. Let's make sure\neverything is blank with xcalloc, just as the regular diff code does.\n\nWe would potentially want to set the \"status\" flag to\nsomething non-zero, but it is not clear to what. Possibly a\nnew DIFF_STATUS_COMBINED would make sense, as this is not\nstrictly a modification, nor does it fit any other category.\n\nSince it is not yet clear what callers would want, this\npatch simply leaves it as \"0\", the same empty flag that is\nseen when diffcore_std is not used at all.\n\nSigned-off-by: Jeff King \n---\n combine-diff.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 9527f3160d..1deb8c7374 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -1315,7 +1315,7 @@ static struct diff_filepair *combined_pair(struct combine_diff_path *p,\n \tstruct diff_filepair *pair;\n \tstruct diff_filespec *pool;\n \n-\tpair = xmalloc(sizeof(*pair));\n+\tCALLOC_ARRAY(pair, 1);\n \tCALLOC_ARRAY(pool, st_add(num_parent, 1));\n \tpair->one = pool + 1;\n \tpair->two = pool;\n\n-- \n2.49.0.rc2\n\n"},{"id":"515113","messageId":"20250326-toon-blame-tree-v1-2-4173133f3786@iotcl.com","threadId":"63201","inReplyTo":"20250326-toon-blame-tree-v1-0-4173133f3786@iotcl.com","subject":"[PATCH 2/8] within_depth: fix return for empty path","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-03-26T20:18:26Z","receivedAt":"2025-03-26T20:19:36Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"From: Jeff King \n\nThe within_depth function is used to check whether pathspecs\nlimited by a max-depth parameter are acceptable. It takes a\npath to check, a maximum depth, and a \"base\" depth. It\ncounts the components in the path (by counting slashes),\nadds them to the base, and compare them to the maximum.\n\nHowever, if the base does not have any slashes at all, we\nalways return \"true\". If the base depth is 0, then this is\ncorrect; no matter what the maximum is, we are always within\nit. However, if the base depth is greater than 0, then we\nmight return an erroneous result.\n\nThis ends up not causing any user-visible bugs in the\ncurrent code. The call sites in dir.c always pass a base\ndepth of 0, so are unaffected. But tree_entry_interesting\nuses this function differently: it will pass the prefix of\nthe current entry, along with a \"1\" if the entry is a\ndirectory, in essence checking whether items inside the\nentry would be of interest. It turns out not to make a\ndifference in behavior, but the reasoning is complex.\n\nGiven a tree like:\n\n file\n a/file\n a/b/file\n\nwalking the tree and calling tree_entry_interesting will\nyield the following results:\n\n (with max_depth=0):\n file: yes\n a: yes\n a/file: no\n a/b: no\n\n (with max_depth=1):\n file: yes\n a: yes\n a/file: yes\n a/b: no\n\nSo we have inconsistent behavior in considering directories\ninteresting. If they are at the edge of our depth but at the\nroot, we will recurse into them, but then find all of their\nentries uninteresting (e.g., in the first case, we will look\nat \"a\" but find \"a/*\" uninteresting). But if they are at the\nedge of our depth and not at the root, then we will not\nrecurse (in the second example, we do not even bother\nentering \"a/b\").\n\nThis turns out not to matter because the only caller which\nuses max-depth pathspecs is cmd_grep, which only cares about\nblob entries. From its perspective, it is exactly the same\nto not recurse into a subtree, or to recurse and find that\nit contains no matching entries. Not recursing is merely an\noptimization.\n\nIt is debatable whether tree_entry_interesting should\nconsider such an entry interesting. The only caller does not\ncare if it sees the tree itself, and can benefit from the\noptimization. But if we add a \"max-depth\" limiter to regular\ndiffs, then a diff with DIFF_OPT_TREE_IN_RECURSIVE would\nprobably want to show the tree itself, but not what it\ncontains.\n\nThis patch just fixes within_depth, which means we consider\nsuch entries uninteresting (and makes the current caller\nhappy). If we want to change that in the future, then this\nfix is still the correct first step, as the current behavior is\nsimply inconsistent.\n\nSigned-off-by: Jeff King \n---\n dir.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/dir.c b/dir.c\nindex cbd82be6c9..3aead2a599 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -278,7 +278,7 @@ int within_depth(const char *name, int namelen,\n \t\tif (depth > max_depth)\n \t\t\treturn 0;\n \t}\n-\treturn 1;\n+\treturn depth <= max_depth;\n }\n \n /*\n\n-- \n2.49.0.rc2\n\n"},{"id":"515114","messageId":"20250326-toon-blame-tree-v1-3-4173133f3786@iotcl.com","threadId":"63201","inReplyTo":"20250326-toon-blame-tree-v1-0-4173133f3786@iotcl.com","subject":"[PATCH 3/8] diff: teach tree-diff a max-depth parameter","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-03-26T20:18:27Z","receivedAt":"2025-03-26T20:19:39Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"From: Jeff King \n\nWhen you are doing a tree-diff, there are basically two\noptions: do not recurse into subtrees at all, or recurse\nindefinitely. While most callers would want to always\nrecurse and see full pathnames, some may want the efficiency\nof looking only at a particular level of the tree. This is\ncurrently easy to do for the top-level (just turn off\nrecursion), but you cannot say \"show me what changed in\nsubdir/, but do not recurse\".\n\nThis patch adds a max-depth parameter which is measured from\nthe closest pathspec match, so that you can do:\n\n git log --raw --max-depth=1 a/b/c\n\nand see the contents of a/b/c/, but not those of a/b/c/d/\n(you would see the --raw entry for a/b/c/d in such a case).\n\nSigned-off-by: Jeff King \n---\n Documentation/diff-options.adoc | 26 ++++++++++\n diff-lib.c | 5 ++\n diff.c | 18 +++++++\n diff.h | 9 ++++\n t/meson.build | 1 +\n t/t4071-diff-max-depth.sh | 109 ++++++++++++++++++++++++++++++++++++++++\n tree-diff.c | 78 ++++++++++++++++++++++++++--\n 7 files changed, 243 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/diff-options.adoc b/Documentation/diff-options.adoc\nindex 640eb6e7db..8bb523d933 100644\n--- a/Documentation/diff-options.adoc\n+++ b/Documentation/diff-options.adoc\n@@ -887,5 +887,31 @@ endif::git-format-patch[]\n \treverted with `--ita-visible-in-index`. Both options are\n \texperimental and could be removed in future.\n \n+--max-depth=::\n+\n+\tLimit diff recursion to `` levels (implies `-r`). The depth\n+\tis measured from the closest pathspec. Given a tree containing\n+\t`foo/bar/baz`, the following list shows the matches generated by\n+\teach set of options:\n++\n+--\n+ - `--max-depth=0 -- foo`: `foo`\n+\n+ - `--max-depth=1 -- foo`: `foo/bar`\n+\n+ - `--max-depth=2 -- foo`: `foo/bar/baz`\n+\n+ - `--max-depth=1 -- foo/bar`: `foo/bar/baz`\n+--\n++\n+If no pathspec is given, the depth is measured as if all\n+top-level entries were specified. Note that this is different\n+than measuring from the root, in that `--max-depth=0` would\n+still return `foo`. This allows you to still limit depth while\n+asking for a subset of the top-level entries.\n++\n+Note that this option is only supported for diffs between tree objects,\n+not against the index or working tree.\n+\n For more detailed explanation on these common options, see also\n linkgit:gitdiffcore[7].\ndiff --git a/diff-lib.c b/diff-lib.c\nindex 353b473ed5..34d61cc6a0 100644\n--- a/diff-lib.c\n+++ b/diff-lib.c\n@@ -115,6 +115,9 @@ void run_diff_files(struct rev_info *revs, unsigned int option)\n \tuint64_t start = getnanotime();\n \tstruct index_state *istate = revs->diffopt.repo->index;\n \n+\tif (revs->diffopt.max_depth_valid)\n+\t\tdie(\"max-depth is not supported for worktree diffs\");\n+\n \tdiff_set_mnemonic_prefix(&revs->diffopt, \"i/\", \"w/\");\n \n \trefresh_fsmonitor(istate);\n@@ -560,6 +563,8 @@ static int diff_cache(struct rev_info *revs,\n \topts.dst_index = NULL;\n \topts.pathspec = &revs->diffopt.pathspec;\n \topts.pathspec->recursive = 1;\n+\tif (revs->diffopt.max_depth_valid)\n+\t\tdie(\"max-depth is not supported for index diffs\");\n \n \tinit_tree_desc(&t, &tree->object.oid, tree->buffer, tree->size);\n \treturn unpack_trees(1, &t, &opts);\ndiff --git a/diff.c b/diff.c\nindex c89c15d98e..acf2212a4a 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -4986,6 +4986,9 @@ void diff_setup_done(struct diff_options *options)\n \t\t\toptions->filter = ~filter_bit[DIFF_STATUS_FILTER_AON];\n \t\toptions->filter &= ~options->filter_not;\n \t}\n+\n+\tif (options->pathspec.has_wildcard && options->max_depth_valid)\n+\t\tdie(\"max-depth cannot be used with wildcard pathspecs\");\n }\n \n int parse_long_opt(const char *opt, const char **argv,\n@@ -5620,6 +5623,18 @@ static int diff_opt_rotate_to(const struct option *opt, const char *arg, int uns\n \treturn 0;\n }\n \n+static int diff_opt_max_depth(const struct option *opt,\n+\t\t\t const char *arg, int unset)\n+{\n+\tstruct diff_options *options = opt->value;\n+\n+\tBUG_ON_OPT_NEG(unset);\n+\toptions->flags.recursive = 1;\n+\toptions->max_depth = strtol(arg, NULL, 10);\n+\toptions->max_depth_valid = 1;\n+\treturn 0;\n+}\n+\n /*\n * Consider adding new flags to __git_diff_common_options\n * in contrib/completion/git-completion.bash\n@@ -5895,6 +5910,9 @@ struct option *add_diff_options(const struct option *opts,\n \t\t{ OPTION_CALLBACK, 0, \"output\", options, N_(\"\"),\n \t\t N_(\"output to a specific file\"),\n \t\t PARSE_OPT_NONEG, NULL, 0, diff_opt_output },\n+\t\tOPT_CALLBACK_F(0, \"max-depth\", options, N_(\"\"),\n+\t\t\t N_(\"maximum tree depth to recurse\"),\n+\t\t\t PARSE_OPT_NONEG, diff_opt_max_depth),\n \n \t\tOPT_END()\n \t};\ndiff --git a/diff.h b/diff.h\nindex ff0348e4a9..a07d2178c4 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -396,6 +396,15 @@ struct diff_options {\n \tstruct strmap *additional_path_headers;\n \n \tint no_free;\n+\n+\t/*\n+\t * The extra \"valid\" flag is a slight hack. The value \"0\" is perfectly\n+\t * valid for max-depth. We would normally use -1 to indicate \"not set\",\n+\t * but there are many code paths which assume that assume that just\n+\t * zero-ing out a diff_options is enough to initialize it.\n+\t */\n+\tint max_depth;\n+\tint max_depth_valid;\n };\n \n unsigned diff_filter_bit(char status);\ndiff --git a/t/meson.build b/t/meson.build\nindex a59da26be3..950d1b7483 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -500,6 +500,7 @@ integration_tests = [\n 't4067-diff-partial-clone.sh',\n 't4068-diff-symmetric-merge-base.sh',\n 't4069-remerge-diff.sh',\n+ 't4071-diff-max-depth.sh',\n 't4100-apply-stat.sh',\n 't4101-apply-nonl.sh',\n 't4102-apply-rename.sh',\ndiff --git a/t/t4071-diff-max-depth.sh b/t/t4071-diff-max-depth.sh\nnew file mode 100755\nindex 0000000000..1545ebb869\n--- /dev/null\n+++ b/t/t4071-diff-max-depth.sh\n@@ -0,0 +1,109 @@\n+#!/bin/sh\n+\n+test_description='check that diff --max-depth will limit recursion'\n+. ./test-lib.sh\n+\n+make_dir() {\n+\tmkdir -p \"$1\" &&\n+\techo \"$2\" >\"$1/file\"\n+}\n+\n+make_files() {\n+\techo \"$1\" >file &&\n+\tmake_dir one \"$1\" &&\n+\tmake_dir one/two \"$1\" &&\n+\tmake_dir one/two/three \"$1\"\n+}\n+\n+test_expect_success 'setup' '\n+\tgit commit --allow-empty -m empty &&\n+\tgit tag empty &&\n+\tmake_files added &&\n+\tgit add . &&\n+\tgit commit -m added &&\n+\tmake_files modified &&\n+\tgit add . &&\n+\tgit commit -m modified &&\n+\tmake_files index &&\n+\tgit add . &&\n+\tmake_files worktree\n+'\n+\n+test_expect_success '--max-depth is disallowed with wildcard pathspecs' '\n+\ttest_must_fail git diff-tree --max-depth=0 HEAD^ HEAD -- \"f*\"\n+'\n+\n+check_one() {\n+\ttype=$1; shift\n+\targs=$1; shift\n+\tpath=$1; shift\n+\tdepth=$1; shift\n+\ttest_expect_${expect:-success} \"diff-$type $args, path=$path, depth=$depth\" \"\n+\t\tfor i in $*; do echo \\$i; done >expect &&\n+\t\tgit diff-$type --max-depth=$depth --name-only $args -- $path >actual &&\n+\t\ttest_cmp expect actual\n+\t\"\n+}\n+\n+# For tree comparisons, we expect to see subtrees at the boundary\n+# get their own entry.\n+check_trees() {\n+\tcheck_one tree \"$*\" '' 0 file one\n+\tcheck_one tree \"$*\" '' 1 file one/file one/two\n+\tcheck_one tree \"$*\" '' 2 file one/file one/two/file one/two/three\n+\tcheck_one tree \"$*\" '' 3 file one/file one/two/file one/two/three/file\n+\tcheck_one tree \"$*\" one 0 one\n+\tcheck_one tree \"$*\" one 1 one/file one/two\n+\tcheck_one tree \"$*\" one 2 one/file one/two/file one/two/three\n+\tcheck_one tree \"$*\" one 3 one/file one/two/file one/two/three/file\n+\tcheck_one tree \"$*\" one/two 0 one/two\n+\tcheck_one tree \"$*\" one/two 1 one/two/file one/two/three\n+\tcheck_one tree \"$*\" one/two 2 one/two/file one/two/three/file\n+\tcheck_one tree \"$*\" one/two/three 0 one/two/three\n+\tcheck_one tree \"$*\" one/two/three 1 one/two/three/file\n+}\n+\n+# But for index comparisons, we do not store subtrees at all, so we do not\n+# expect them.\n+check_index() {\n+\tcheck_one \"$@\" '' 0 file\n+\tcheck_one \"$@\" '' 1 file one/file\n+\tcheck_one \"$@\" '' 2 file one/file one/two/file\n+\tcheck_one \"$@\" '' 3 file one/file one/two/file one/two/three/file\n+\tcheck_one \"$@\" one 0\n+\tcheck_one \"$@\" one 1 one/file\n+\tcheck_one \"$@\" one 2 one/file one/two/file\n+\tcheck_one \"$@\" one 3 one/file one/two/file one/two/three/file\n+\tcheck_one \"$@\" one/two 0\n+\tcheck_one \"$@\" one/two 1 one/two/file\n+\tcheck_one \"$@\" one/two 2 one/two/file one/two/three/file\n+\tcheck_one \"$@\" one/two/three 0\n+\tcheck_one \"$@\" one/two/three 1 one/two/three/file\n+}\n+\n+# Check as a modification...\n+check_trees HEAD^ HEAD\n+# ...and as an addition...\n+check_trees empty HEAD\n+# ...and as a deletion.\n+check_trees HEAD empty\n+\n+# We currently only implement max-depth for trees.\n+expect=failure\n+# Check index against a tree\n+check_index index \"--cached HEAD\"\n+# and index against the worktree\n+check_index files \"\"\n+expect=\n+\n+test_expect_success 'find shortest path within embedded pathspecs' '\n+\tcat >expect <<-\\EOF &&\n+\tone/file\n+\tone/two/file\n+\tone/two/three/file\n+\tEOF\n+\tgit diff-tree --max-depth=2 --name-only HEAD^ HEAD -- one one/two >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\ndiff --git a/tree-diff.c b/tree-diff.c\nindex 60c558c2b5..2a744dfaec 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -13,6 +13,7 @@\n #include \"tree-walk.h\"\n #include \"environment.h\"\n #include \"repository.h\"\n+#include \"dir.h\"\n \n /*\n * Some mode bits are also used internally for computations.\n@@ -48,6 +49,73 @@\n \t\tfree((x)); \\\n } while(0)\n \n+/* Returns true if and only if \"dir\" is a leading directory of \"path\" */\n+static int is_dir_prefix(const char *path, const char *dir, int dirlen)\n+{\n+\treturn !strncmp(path, dir, dirlen) &&\n+\t\t(!path[dirlen] || path[dirlen] == '/');\n+}\n+\n+static int check_recursion_depth(struct strbuf *name,\n+\t\t\t\t const struct pathspec *ps,\n+\t\t\t\t int max_depth)\n+{\n+\tint i;\n+\n+\tif (!ps->nr)\n+\t\treturn within_depth(name->buf, name->len, 1, max_depth);\n+\n+\t/*\n+\t * We look through the pathspecs in reverse-sorted order, because we\n+\t * want to find the longest match first (e.g., \"a/b\" is better for\n+\t * checking depth than \"a/b/c\").\n+\t */\n+\tfor (i = ps->nr - 1; i >= 0; i--) {\n+\t\tconst struct pathspec_item *item = ps->items+i;\n+\n+\t\t/*\n+\t\t * If the name to match is longer than the pathspec, then we\n+\t\t * are only interested if the pathspec matches and we are\n+\t\t * within the allowed depth.\n+\t\t */\n+\t\tif (name->len >= item->len) {\n+\t\t\tif (!is_dir_prefix(name->buf, item->match, item->len))\n+\t\t\t\tcontinue;\n+\t\t\treturn within_depth(name->buf + item->len,\n+\t\t\t\t\t name->len - item->len,\n+\t\t\t\t\t 1, max_depth);\n+\t\t}\n+\n+\t\t/*\n+\t\t * Otherwise, our name is shorter than the pathspec. We need to\n+\t\t * check if it is a prefix of the pathspec; if so, we must\n+\t\t * always recurse in order to process further (the resulting\n+\t\t * paths we find might or might not match our pathspec, but we\n+\t\t * cannot know until we recurse).\n+\t\t */\n+\t\tif (is_dir_prefix(item->match, name->buf, name->len))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n+static int should_recurse(struct strbuf *name, struct diff_options *opt)\n+{\n+\tif (!opt->flags.recursive)\n+\t\treturn 0;\n+\tif (!opt->max_depth_valid)\n+\t\treturn 1;\n+\n+\t/*\n+\t * We catch this during diff_setup_done, but let's double-check\n+\t * against any internal munging.\n+\t */\n+\tif (opt->pathspec.has_wildcard)\n+\t\tdie(\"BUG: wildcard pathspecs are incompatible with max-depth\");\n+\n+\treturn check_recursion_depth(name, &opt->pathspec, opt->max_depth);\n+}\n+\n static void ll_diff_tree_paths(\n \tstruct combine_diff_path ***tail, const struct object_id *oid,\n \tconst struct object_id **parents_oid, int nparent,\n@@ -170,9 +238,13 @@ static void emit_path(struct combine_diff_path ***tail,\n \t\tmode = 0;\n \t}\n \n-\tif (opt->flags.recursive && isdir) {\n-\t\trecurse = 1;\n-\t\temitthis = opt->flags.tree_in_recursive;\n+\tif (isdir) {\n+\t\tstrbuf_add(base, path, pathlen);\n+\t\tif (should_recurse(base, opt)) {\n+\t\t\trecurse = 1;\n+\t\t\temitthis = opt->flags.tree_in_recursive;\n+\t\t}\n+\t\tstrbuf_setlen(base, old_baselen);\n \t}\n \n \tif (emitthis) {\n\n-- \n2.49.0.rc2\n\n"},{"id":"515115","messageId":"20250326-toon-blame-tree-v1-4-4173133f3786@iotcl.com","threadId":"63201","inReplyTo":"20250326-toon-blame-tree-v1-0-4173133f3786@iotcl.com","subject":"[PATCH 4/8] blame-tree: introduce new subcommand to blame files","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-03-26T20:18:28Z","receivedAt":"2025-03-26T20:19:44Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Similar to git-blame(1), introduce a new subcommand git-blame-tree(1).\nThis command shows the most recent modification to paths in a tree. It\ndoes so by expanding the tree at a given commit, taking note of the\ncurrent state of each path, and then walking backwards through history\nlooking for commits where each path changed into its final commit ID.\n\nBased-on-a-patch-by: Jeff King \nImproved-by: \"Ævar Arnfjörð Bjarmason\" \nSigned-off-by: Toon Claes \n---\n .gitignore | 1 +\n Makefile | 2 +\n blame-tree.c | 198 ++++++++++++++++++++++++++++++++++++++++++++++++++\n blame-tree.h | 43 +++++++++++\n builtin.h | 1 +\n builtin/blame-tree.c | 67 +++++++++++++++++\n git.c | 1 +\n meson.build | 2 +\n t/helper/test-tool.h | 1 +\n t/meson.build | 1 +\n t/t8020-blame-tree.sh | 142 ++++++++++++++++++++++++++++++++++++\n 11 files changed, 459 insertions(+)\n\ndiff --git a/.gitignore b/.gitignore\nindex 08a66ca508..27faa0ce90 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -22,6 +22,7 @@\n /git-backfill\n /git-bisect\n /git-blame\n+/git-blame-tree\n /git-branch\n /git-bugreport\n /git-bundle\ndiff --git a/Makefile b/Makefile\nindex 7315507381..92fdfc76df 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -972,6 +972,7 @@ LIB_OBJS += archive.o\n LIB_OBJS += attr.o\n LIB_OBJS += base85.o\n LIB_OBJS += bisect.o\n+LIB_OBJS += blame-tree.o\n LIB_OBJS += blame.o\n LIB_OBJS += blob.o\n LIB_OBJS += bloom.o\n@@ -1215,6 +1216,7 @@ BUILTIN_OBJS += builtin/archive.o\n BUILTIN_OBJS += builtin/backfill.o\n BUILTIN_OBJS += builtin/bisect.o\n BUILTIN_OBJS += builtin/blame.o\n+BUILTIN_OBJS += builtin/blame-tree.o\n BUILTIN_OBJS += builtin/branch.o\n BUILTIN_OBJS += builtin/bugreport.o\n BUILTIN_OBJS += builtin/bundle.o\ndiff --git a/blame-tree.c b/blame-tree.c\nnew file mode 100644\nindex 0000000000..ed4ec1e694\n--- /dev/null\n+++ b/blame-tree.c\n@@ -0,0 +1,198 @@\n+#include \"git-compat-util.h\"\n+#include \"blame-tree.h\"\n+#include \"strvec.h\"\n+#include \"hex.h\"\n+#include \"commit.h\"\n+#include \"diffcore.h\"\n+#include \"diff.h\"\n+#include \"object.h\"\n+#include \"revision.h\"\n+#include \"repository.h\"\n+#include \"log-tree.h\"\n+\n+void blame_tree_opts_release(struct blame_tree_options *bto)\n+{\n+\tstrvec_clear(&bto->args);\n+}\n+\n+struct blame_tree_entry {\n+\tstruct object_id oid;\n+\tstruct commit *commit;\n+};\n+\n+static void add_from_diff(struct diff_queue_struct *q,\n+\t\t\t struct diff_options *opt UNUSED, void *data)\n+{\n+\tstruct blame_tree *bt = data;\n+\n+\tfor (int i = 0; i < q->nr; i++) {\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tstruct blame_tree_entry *ent = xcalloc(1, sizeof(*ent));\n+\t\tstruct string_list_item *it;\n+\n+\t\toidcpy(&ent->oid, &p->two->oid);\n+\t\tit = string_list_append(&bt->paths, p->two->path);\n+\t\tit->util = ent;\n+\t}\n+}\n+\n+static int add_from_revs(struct blame_tree *bt)\n+{\n+\tsize_t count = 0;\n+\tstruct diff_options diffopt;\n+\n+\tmemcpy(&diffopt, &bt->rev.diffopt, sizeof(diffopt));\n+\tdiffopt.output_format = DIFF_FORMAT_CALLBACK;\n+\tdiffopt.format_callback = add_from_diff;\n+\tdiffopt.format_callback_data = bt;\n+\tdiffopt.no_free = 1;\n+\n+\tfor (size_t i = 0; i < bt->rev.pending.nr; i++) {\n+\t\tstruct object_array_entry *obj = bt->rev.pending.objects + i;\n+\n+\t\tif (obj->item->flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\n+\t\tif (count++)\n+\t\t\treturn error(_(\"can only blame one tree at a time\"));\n+\t\tdiff_tree_oid(bt->rev.repo->hash_algo->empty_tree,\n+\t\t\t &obj->item->oid, \"\", &diffopt);\n+\t\tdiff_flush(&diffopt);\n+\t}\n+\n+\tstring_list_sort(&bt->paths);\n+\treturn 0;\n+}\n+\n+void blame_tree_init(struct repository *r, struct blame_tree *bt,\n+\t\t const struct blame_tree_options *opts)\n+{\n+\trepo_init_revisions(r, &bt->rev, opts->prefix);\n+\tbt->rev.def = oid_to_hex(&opts->oid);\n+\tbt->rev.combine_merges = 1;\n+\tbt->rev.show_root_diff = 1;\n+\tbt->rev.boundary = 1;\n+\tbt->rev.no_commit_id = 1;\n+\tbt->rev.diff = 1;\n+\tbt->rev.diffopt.flags.recursive = opts->recursive;\n+\tsetup_revisions(opts->args.nr, opts->args.v, &bt->rev, NULL);\n+\n+\tif (add_from_revs(bt) < 0)\n+\t\tdie(_(\"unable to setup blame-tree\"));\n+}\n+\n+void blame_tree_release(struct blame_tree *bt)\n+{\n+\tstring_list_clear(&bt->paths, 1);\n+\trelease_revisions(&bt->rev);\n+}\n+\n+struct blame_tree_callback_data {\n+\tstruct commit *commit;\n+\tstruct string_list *paths;\n+\tsize_t num_interesting;\n+\n+\tblame_tree_fn callback;\n+\tvoid *callback_data;\n+};\n+\n+static void mark_path(const char *path, const struct object_id *oid,\n+\t\t struct blame_tree_callback_data *data)\n+{\n+\tstruct string_list_item *item = string_list_lookup(data->paths, path);\n+\tstruct blame_tree_entry *ent;\n+\n+\t/* Is it even a path that exists in our tree? */\n+\tif (!item)\n+\t\treturn;\n+\n+\t/* Have we already blamed a commit? */\n+\tent = item->util;\n+\tif (ent->commit)\n+\t\treturn;\n+\n+\t/*\n+\t * Is it arriving at a version of interest, or is it from a side branch\n+\t * which did not contribute to the final state?\n+\t */\n+\tif (!oideq(oid, &ent->oid))\n+\t\treturn;\n+\n+\tent->commit = data->commit;\n+\tdata->num_interesting--;\n+\tif (data->callback)\n+\t\tdata->callback(path, data->commit, data->callback_data);\n+}\n+\n+static void blame_diff(struct diff_queue_struct *q,\n+\t\t struct diff_options *opt UNUSED, void *cbdata)\n+{\n+\tstruct blame_tree_callback_data *data = cbdata;\n+\n+\tfor (int i = 0; i < q->nr; i++) {\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tswitch (p->status) {\n+\t\tcase DIFF_STATUS_DELETED:\n+\t\t\t/*\n+\t\t\t * There's no point in feeding a deletion, as it could\n+\t\t\t * not have resulted in our current state, which\n+\t\t\t * actually has the file.\n+\t\t\t */\n+\t\t\tbreak;\n+\n+\t\tdefault:\n+\t\t\t/*\n+\t\t\t * Otherwise, we care only that we somehow arrived at\n+\t\t\t * a final path/sha1 state. Note that this covers some\n+\t\t\t * potentially controversial areas, including:\n+\t\t\t *\n+\t\t\t * 1. A rename or copy will be blamed, as it is the\n+\t\t\t * first time the content has arrived at the given\n+\t\t\t * path.\n+\t\t\t *\n+\t\t\t * 2. Even a non-content modification like a mode or\n+\t\t\t * type change will trigger it.\n+\t\t\t *\n+\t\t\t * We take the inclusive approach for now, and blame\n+\t\t\t * anything which impacts the path. Options to tweak\n+\t\t\t * the behavior (e.g., to \"--follow\" the content across\n+\t\t\t * renames) can come later.\n+\t\t\t */\n+\t\t\tmark_path(p->two->path, &p->two->oid, data);\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+}\n+\n+int blame_tree_run(struct blame_tree *bt, blame_tree_fn cb, void *cbdata)\n+{\n+\tstruct blame_tree_callback_data data;\n+\n+\tdata.paths = &bt->paths;\n+\tdata.num_interesting = bt->paths.nr;\n+\tdata.callback = cb;\n+\tdata.callback_data = cbdata;\n+\n+\tbt->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n+\tbt->rev.diffopt.format_callback = blame_diff;\n+\tbt->rev.diffopt.format_callback_data = &data;\n+\n+\tprepare_revision_walk(&bt->rev);\n+\n+\twhile (data.num_interesting) {\n+\t\tdata.commit = get_revision(&bt->rev);\n+\t\tif (!data.commit)\n+\t\t\tbreak;\n+\n+\t\tif (data.commit->object.flags & BOUNDARY) {\n+\t\t\tdiff_tree_oid(bt->rev.repo->hash_algo->empty_tree,\n+\t\t\t\t &data.commit->object.oid,\n+\t\t\t\t \"\", &bt->rev.diffopt);\n+\t\t\tdiff_flush(&bt->rev.diffopt);\n+\t\t} else {\n+\t\t\tlog_tree_commit(&bt->rev, data.commit);\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+}\ndiff --git a/blame-tree.h b/blame-tree.h\nnew file mode 100644\nindex 0000000000..ea06298f88\n--- /dev/null\n+++ b/blame-tree.h\n@@ -0,0 +1,43 @@\n+#ifndef BLAME_TREE_H\n+#define BLAME_TREE_H\n+\n+#include \"hash.h\"\n+#include \"strvec.h\"\n+#include \"string-list.h\"\n+#include \"revision.h\"\n+#include \"commit.h\"\n+\n+struct blame_tree_options {\n+\tstruct object_id oid;\n+\tconst char *prefix;\n+\tunsigned int recursive;\n+\tstruct strvec args;\n+};\n+\n+#define BLAME_TREE_OPTIONS_INIT(...) { \\\n+\t.args = STRVEC_INIT, \\\n+\t__VA_ARGS__ \\\n+}\n+\n+void blame_tree_opts_release(struct blame_tree_options *bto);\n+\n+struct blame_tree {\n+\tstruct string_list paths;\n+\tstruct rev_info rev;\n+\tstruct repository *repository;\n+};\n+#define BLAME_TREE_INIT { \\\n+\t.paths = STRING_LIST_INIT_DUP, \\\n+\t.rev = REV_INFO_INIT, \\\n+}\n+\n+void blame_tree_init(struct repository *r, struct blame_tree *bt,\n+\t\t const struct blame_tree_options *opts);\n+\n+void blame_tree_release(struct blame_tree *);\n+\n+typedef void (*blame_tree_fn)(const char *path, const struct commit *commit,\n+\t\t\t void *data);\n+int blame_tree_run(struct blame_tree *bt, blame_tree_fn cb, void *data);\n+\n+#endif /* BLAME_TREE_H */\ndiff --git a/builtin.h b/builtin.h\nindex 993a583872..be3176924d 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -123,6 +123,7 @@ int cmd_archive(int argc, const char **argv, const char *prefix, struct reposito\n int cmd_backfill(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_bisect(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_blame(int argc, const char **argv, const char *prefix, struct repository *repo);\n+int cmd_blame_tree(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_branch(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_bugreport(int argc, const char **argv, const char *prefix, struct repository *repo);\n int cmd_bundle(int argc, const char **argv, const char *prefix, struct repository *repo);\ndiff --git a/builtin/blame-tree.c b/builtin/blame-tree.c\nnew file mode 100644\nindex 0000000000..bc404b63f3\n--- /dev/null\n+++ b/builtin/blame-tree.c\n@@ -0,0 +1,67 @@\n+#define USE_THE_REPOSITORY_VARIABLE\n+\n+#include \"git-compat-util.h\"\n+#include \"blame-tree.h\"\n+#include \"strvec.h\"\n+#include \"hex.h\"\n+#include \"quote.h\"\n+#include \"config.h\"\n+#include \"environment.h\"\n+#include \"object-name.h\"\n+#include \"parse-options.h\"\n+#include \"builtin.h\"\n+#include \"setup.h\"\n+\n+static void show_entry(const char *path, const struct commit *commit, void *d)\n+{\n+\tstruct blame_tree *bt = d;\n+\n+\tif (commit->object.flags & BOUNDARY)\n+\t\tputchar('^');\n+\tprintf(\"%s\\t\", oid_to_hex(&commit->object.oid));\n+\n+\tif (bt->rev.diffopt.line_termination)\n+\t\twrite_name_quoted(path, stdout, '\\n');\n+\telse\n+\t\tprintf(\"%s%c\", path, '\\0');\n+\n+\tfflush(stdout);\n+}\n+\n+int cmd_blame_tree(int argc, const char **argv, const char *prefix, struct repository *repo)\n+{\n+\tstruct blame_tree bt = BLAME_TREE_INIT;\n+\tstruct blame_tree_options opts = BLAME_TREE_OPTIONS_INIT(\n+\t\t.prefix = prefix,\n+\t);\n+\n+\tstruct option options[] = {\n+\t\tOPT_BOOL(0, \"recursive\", &opts.recursive,\n+\t\t\t \"recurse into to subtrees\"),\n+\t\tOPT_END()\n+\t};\n+\n+\tconst char * const blame_tree_usage[] = {\n+\t\tN_(\"git blame-tree [--no-recursive] []\"),\n+\t\tNULL,\n+\t};\n+\n+\tgit_config(git_default_config, NULL);\n+\n+\tif (repo_get_oid(the_repository, \"HEAD\", &opts.oid))\n+\t\t die(\"unable to get HEAD\");\n+\n+\targc = parse_options(argc, argv, prefix, options, blame_tree_usage,\n+\t\t\t PARSE_OPT_KEEP_ARGV0 | PARSE_OPT_KEEP_UNKNOWN_OPT);\n+\tif (argc)\n+\t\tstrvec_pushv(&opts.args, argv);\n+\n+\tblame_tree_init(repo, &bt, &opts);\n+\n+\tif (blame_tree_run(&bt, show_entry, &bt) < 0)\n+\t\tdie(_(\"error running blame-tree traversal\"));\n+\tblame_tree_release(&bt);\n+\tblame_tree_opts_release(&opts);\n+\n+\treturn 0;\n+}\ndiff --git a/git.c b/git.c\nindex 450d6aaa86..42de740378 100644\n--- a/git.c\n+++ b/git.c\n@@ -509,6 +509,7 @@ static struct cmd_struct commands[] = {\n \t{ \"backfill\", cmd_backfill, RUN_SETUP },\n \t{ \"bisect\", cmd_bisect, RUN_SETUP },\n \t{ \"blame\", cmd_blame, RUN_SETUP },\n+\t{ \"blame-tree\", cmd_blame_tree, RUN_SETUP },\n \t{ \"branch\", cmd_branch, RUN_SETUP | DELAY_PAGER_CONFIG },\n \t{ \"bugreport\", cmd_bugreport, RUN_SETUP_GENTLY },\n \t{ \"bundle\", cmd_bundle, RUN_SETUP_GENTLY },\ndiff --git a/meson.build b/meson.build\nindex efe2871c9d..dd231b669b 100644\n--- a/meson.build\n+++ b/meson.build\n@@ -241,6 +241,7 @@ libgit_sources = [\n 'attr.c',\n 'base85.c',\n 'bisect.c',\n+ 'blame-tree.c',\n 'blame.c',\n 'blob.c',\n 'bloom.c',\n@@ -512,6 +513,7 @@ builtin_sources = [\n 'builtin/archive.c',\n 'builtin/backfill.c',\n 'builtin/bisect.c',\n+ 'builtin/blame-tree.c',\n 'builtin/blame.c',\n 'builtin/branch.c',\n 'builtin/bugreport.c',\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex 6d62a5b53d..41cc3730dc 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -5,6 +5,7 @@\n \n int cmd__advise_if_enabled(int argc, const char **argv);\n int cmd__bitmap(int argc, const char **argv);\n+int cmd__blame_tree(int argc, const char **argv);\n int cmd__bloom(int argc, const char **argv);\n int cmd__bundle_uri(int argc, const char **argv);\n int cmd__cache_tree(int argc, const char **argv);\ndiff --git a/t/meson.build b/t/meson.build\nindex 950d1b7483..6f6485c8b4 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -960,6 +960,7 @@ integration_tests = [\n 't8012-blame-colors.sh',\n 't8013-blame-ignore-revs.sh',\n 't8014-blame-ignore-fuzzy.sh',\n+ 't8020-blame-tree.sh',\n 't9001-send-email.sh',\n 't9002-column.sh',\n 't9003-help-autocorrect.sh',\ndiff --git a/t/t8020-blame-tree.sh b/t/t8020-blame-tree.sh\nnew file mode 100755\nindex 0000000000..5fd2c079fe\n--- /dev/null\n+++ b/t/t8020-blame-tree.sh\n@@ -0,0 +1,142 @@\n+#!/bin/sh\n+\n+test_description='blame-tree tests'\n+\n+. ./test-lib.sh\n+\n+test_expect_success 'setup' '\n+\ttest_commit 1 file &&\n+\tmkdir a &&\n+\ttest_commit 2 a/file &&\n+\tmkdir a/b &&\n+\ttest_commit 3 a/b/file\n+'\n+\n+test_expect_success 'cannot blame two trees' '\n+\ttest_must_fail git blame-tree HEAD HEAD~1\n+'\n+\n+check_blame() {\n+\tlocal indir= &&\n+\twhile test $# != 0\n+\tdo\n+\t\tcase \"$1\" in\n+\t\t-C)\n+\t\t\tindir=\"$2\"\n+\t\t\tshift\n+\t\t\t;;\n+\t\t*)\n+\t\t\tbreak\n+\t\t\t;;\n+\t\tesac &&\n+\t\tshift\n+\tdone &&\n+\n+\tcat >expect &&\n+\ttest_when_finished \"rm -f tmp.*\" &&\n+\tgit ${indir:+-C \"$indir\"} blame-tree \"$@\" >tmp.1 &&\n+\tgit name-rev --annotate-stdin --name-only --tags \\\n+\t\ttmp.2 &&\n+\ttr '\\t' ' ' tmp.3 &&\n+\tsort tmp.3 >actual &&\n+\ttest_cmp expect actual\n+}\n+\n+test_expect_success 'blame recursive' '\n+\tcheck_blame --recursive <<-\\EOF\n+\t1 file\n+\t2 a/file\n+\t3 a/b/file\n+\tEOF\n+'\n+\n+test_expect_success 'blame non-recursive' '\n+\tcheck_blame --no-recursive <<-\\EOF\n+\t1 file\n+\t3 a\n+\tEOF\n+'\n+\n+test_expect_success 'blame subdir' '\n+\tcheck_blame a <<-\\EOF\n+\t3 a\n+\tEOF\n+'\n+\n+test_expect_success 'blame subdir recursive' '\n+\tcheck_blame --recursive a <<-\\EOF\n+\t2 a/file\n+\t3 a/b/file\n+\tEOF\n+'\n+\n+test_expect_success 'blame from non-HEAD commit' '\n+\tcheck_blame --no-recursive HEAD^ <<-\\EOF\n+\t1 file\n+\t2 a\n+\tEOF\n+'\n+\n+test_expect_success 'blame from subdir defaults to root' '\n+\tcheck_blame -C a --no-recursive <<-\\EOF\n+\t1 file\n+\t3 a\n+\tEOF\n+'\n+\n+test_expect_success 'blame from subdir uses relative pathspecs' '\n+\tcheck_blame -C a --recursive b <<-\\EOF\n+\t3 a/b/file\n+\tEOF\n+'\n+\n+test_expect_failure 'limit blame traversal by count' '\n+\tcheck_blame --no-recursive -1 <<-\\EOF\n+\t3 a\n+\tEOF\n+'\n+\n+test_expect_success 'limit blame traversal by commit' '\n+\tcheck_blame --no-recursive HEAD~2..HEAD <<-\\EOF\n+\t3 a\n+\t^1 file\n+\tEOF\n+'\n+\n+test_expect_success 'only blame files in the current tree' '\n+\tgit rm -rf a &&\n+\tgit commit -m \"remove a\" &&\n+\tcheck_blame <<-\\EOF\n+\t1 file\n+\tEOF\n+'\n+\n+test_expect_success 'cross merge boundaries in blaming' '\n+\tgit checkout HEAD^0 &&\n+\tgit rm -rf . &&\n+\ttest_commit m1 &&\n+\tgit checkout HEAD^ &&\n+\tgit rm -rf . &&\n+\ttest_commit m2 &&\n+\tgit merge m1 &&\n+\tcheck_blame <<-\\EOF\n+\tm1 m1.t\n+\tm2 m2.t\n+\tEOF\n+'\n+\n+test_expect_success 'blame merge for resolved conflicts' '\n+\tgit checkout HEAD^0 &&\n+\tgit rm -rf . &&\n+\ttest_commit c1 conflict &&\n+\tgit checkout HEAD^ &&\n+\tgit rm -rf . &&\n+\ttest_commit c2 conflict &&\n+\ttest_must_fail git merge c1 &&\n+\ttest_commit resolved conflict &&\n+\tcheck_blame conflict <<-\\EOF\n+\tresolved conflict\n+\tEOF\n+'\n+\n+test_done\n\n-- \n2.49.0.rc2\n\n"},{"id":"515116","messageId":"20250326-toon-blame-tree-v1-5-4173133f3786@iotcl.com","threadId":"63201","inReplyTo":"20250326-toon-blame-tree-v1-0-4173133f3786@iotcl.com","subject":"[PATCH 5/8] pathspec: add optional trie index","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-03-26T20:18:29Z","receivedAt":"2025-03-26T20:19:48Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"From: Jeff King \n\nWhen 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 \n---\n Makefile | 1 +\n pathspec.c | 119 +++++++++++++++++++++++++++++++++++++++++++++++\n pathspec.h | 23 +++++++++\n t/helper/meson.build | 1 +\n t/helper/test-pathspec.c | 98 ++++++++++++++++++++++++++++++++++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n t/meson.build | 1 +\n t/t6137-pathspec-trie.sh | 57 +++++++++++++++++++++++\n 9 files changed, 302 insertions(+)\n\ndiff --git a/Makefile b/Makefile\nindex 92fdfc76df..c90607baa1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -827,6 +827,7 @@ TEST_BUILTINS_OBJS += test-parse-pathspec-file.o\n TEST_BUILTINS_OBJS += test-partial-clone.o\n TEST_BUILTINS_OBJS += test-path-utils.o\n TEST_BUILTINS_OBJS += test-path-walk.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-proc-receive.o\ndiff --git a/pathspec.c b/pathspec.c\nindex 89663645e1..0e381fd748 100644\n--- a/pathspec.c\n+++ b/pathspec.c\n@@ -17,6 +17,125 @@\n #include \"quote.h\"\n #include \"wildmatch.h\"\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+static struct pathspec_trie *pathspec_trie_alloc(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 pathspec_trie_add(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] = pathspec_trie_alloc(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 *pathspec_trie_build(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 = pathspec_trie_alloc(\"\", 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\tpathspec_trie_add(ret, pathspec->items[i].match);\n+\n+\treturn ret;\n+}\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 /*\n * Finds which of the given pathspecs match items in the index.\n *\ndiff --git a/pathspec.h b/pathspec.h\nindex de537cff3c..71bafb78a9 100644\n--- a/pathspec.h\n+++ b/pathspec.h\n@@ -2,6 +2,7 @@\n #define PATHSPEC_H\n \n struct index_state;\n+struct pathspec;\n \n /* Pathspec magic */\n #define PATHSPEC_FROMTOP\t(1<<0)\n@@ -22,6 +23,28 @@ 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+ * Build a pathspec_trie for the given pathspec.\n+ */\n+struct pathspec_trie *pathspec_trie_build(const struct pathspec *);\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 *pst,\n+\t\t\t const char *path, size_t len);\n+\n /**\n * See glossary-content.txt for the syntax of pathspec.\n * In memory, a pathspec set is represented by \"struct pathspec\" and is\ndiff --git a/t/helper/meson.build b/t/helper/meson.build\nindex d2cabaa2bc..f6dc3e443b 100644\n--- a/t/helper/meson.build\n+++ b/t/helper/meson.build\n@@ -42,6 +42,7 @@ test_tool_sources = [\n 'test-partial-clone.c',\n 'test-path-utils.c',\n 'test-path-walk.c',\n+ 'test-pathspec.c',\n 'test-pcre2-config.c',\n 'test-pkt-line.c',\n 'test-proc-receive.c',\ndiff --git a/t/helper/test-pathspec.c b/t/helper/test-pathspec.c\nnew file mode 100644\nindex 0000000000..c04417681f\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 = pathspec_trie_build(&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 UNUSED, 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 50dc4dac4e..bc0a1b9245 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -54,6 +54,7 @@ static struct test_cmd cmds[] = {\n \t{ \"partial-clone\", cmd__partial_clone },\n \t{ \"path-utils\", cmd__path_utils },\n \t{ \"path-walk\", cmd__path_walk },\n+\t{ \"pathspec\", cmd__pathspec },\n \t{ \"pcre2-config\", cmd__pcre2_config },\n \t{ \"pkt-line\", cmd__pkt_line },\n \t{ \"proc-receive\", cmd__proc_receive },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex 41cc3730dc..5e79fa38ca 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -46,6 +46,7 @@ int cmd__parse_options_flags(int argc, const char **argv);\n int cmd__parse_pathspec_file(int argc, const char** argv);\n int cmd__parse_subcommand(int argc, const char **argv);\n int cmd__partial_clone(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__path_walk(int argc, const char **argv);\n int cmd__pcre2_config(int argc, const char **argv);\ndiff --git a/t/meson.build b/t/meson.build\nindex 6f6485c8b4..bb29c36b2a 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -788,6 +788,7 @@ integration_tests = [\n 't6134-pathspec-in-submodule.sh',\n 't6135-pathspec-with-attrs.sh',\n 't6136-pathspec-in-bare.sh',\n+ 't6137-pathspec-trie.sh',\n 't6200-fmt-merge-msg.sh',\n 't6300-for-each-ref.sh',\n 't6301-for-each-ref-errors.sh',\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\n-- \n2.49.0.rc2\n\n"},{"id":"515117","messageId":"20250326-toon-blame-tree-v1-6-4173133f3786@iotcl.com","threadId":"63201","inReplyTo":"20250326-toon-blame-tree-v1-0-4173133f3786@iotcl.com","subject":"[PATCH 6/8] pathspec: turn on tries when appropriate","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-03-26T20:18:30Z","receivedAt":"2025-03-26T20:19:54Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"From: Jeff King \n\nAn 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 \n---\n pathspec.c | 19 +++++++++++++++++++\n pathspec.h | 1 +\n t/helper/test-pathspec.c | 6 ++----\n 3 files changed, 22 insertions(+), 4 deletions(-)\n\ndiff --git a/pathspec.c b/pathspec.c\nindex 0e381fd748..c174edef32 100644\n--- a/pathspec.c\n+++ b/pathspec.c\n@@ -117,6 +117,19 @@ struct pathspec_trie *pathspec_trie_build(const struct pathspec *pathspec)\n \treturn ret;\n }\n \n+static void pathspec_trie_clear(struct pathspec_trie *t)\n+{\n+\tif (t) {\n+\t\tfor (size_t i = 0; i < t->nr; i++) {\n+\t\t\tpathspec_trie_clear(t->entries[i]);\n+\t\t\tFREE_AND_NULL(t->entries[i]);\n+\t\t}\n+\n+\t\tt->nr = 0;\n+\t\tFREE_AND_NULL(t->entries);\n+\t}\n+}\n+\n int pathspec_trie_lookup(const struct pathspec_trie *parent,\n \t\t\t const char *path, size_t len)\n {\n@@ -799,6 +812,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 = pathspec_trie_build(pathspec);\n }\n \n void parse_pathspec_file(struct pathspec *pathspec, unsigned magic_mask,\n@@ -859,6 +874,8 @@ void copy_pathspec(struct pathspec *dst, const struct pathspec *src)\n \n \t\td->attr_check = attr_check_dup(s->attr_check);\n \t}\n+\n+\tdst->trie = pathspec_trie_build(dst);\n }\n \n void clear_pathspec(struct pathspec *pathspec)\n@@ -877,6 +894,8 @@ void clear_pathspec(struct pathspec *pathspec)\n \t\t\tattr_check_free(pathspec->items[i].attr_check);\n \t}\n \n+\tpathspec_trie_clear(pathspec->trie);\n+\tFREE_AND_NULL(pathspec->trie);\n \tFREE_AND_NULL(pathspec->items);\n \tpathspec->nr = 0;\n }\ndiff --git a/pathspec.h b/pathspec.h\nindex 71bafb78a9..ff11599d25 100644\n--- a/pathspec.h\n+++ b/pathspec.h\n@@ -76,6 +76,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 c04417681f..72e335abc1 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 = pathspec_trie_build(&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\n-- \n2.49.0.rc2\n\n"},{"id":"515118","messageId":"20250326-toon-blame-tree-v1-7-4173133f3786@iotcl.com","threadId":"63201","inReplyTo":"20250326-toon-blame-tree-v1-0-4173133f3786@iotcl.com","subject":"[PATCH 7/8] tree-diff: use pathspec tries","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-03-26T20:18:31Z","receivedAt":"2025-03-26T20:19:57Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"From: Jeff King \n\nThe 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---------------------------------------------------------------\n4003.2: size=1 0.12(0.11+0.00) 0.12(0.12+0.00) +0.0%\n4003.3: size=2 0.17(0.16+0.00) 0.16(0.15+0.01) -5.9%\n4003.4: size=4 0.17(0.17+0.00) 0.17(0.17+0.00) +0.0%\n4003.5: size=8 0.21(0.20+0.00) 0.20(0.20+0.00) -4.8%\n4003.6: size=16 0.25(0.24+0.00) 0.21(0.20+0.00) -16.0%\n4003.7: size=32 0.31(0.31+0.00) 0.21(0.20+0.00) -32.3%\n4003.8: size=64 0.43(0.41+0.01) 0.21(0.21+0.00) -51.2%\n4003.9: size=128 0.73(0.72+0.00) 0.22(0.21+0.00) -69.9%\n4003.10: size=256 2.02(2.02+0.00) 0.37(0.36+0.00) -81.7%\n4003.11: size=512 6.78(6.78+0.00) 0.64(0.64+0.00) -90.6%\n4003.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 \n---\n t/perf/p4003-diff-pathspec.sh | 26 ++++++++++++\n tree-diff.c | 98 +++++++++++++++++++++++++++++++++++++------\n 2 files changed, 112 insertions(+), 12 deletions(-)\n\ndiff --git a/t/perf/p4003-diff-pathspec.sh b/t/perf/p4003-diff-pathspec.sh\nnew file mode 100755\nindex 0000000000..02312d1b0c\n--- /dev/null\n+++ b/t/perf/p4003-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 || return 1\n+\tdone\n+'\n+\n+for i in $sizes; do\n+\ttest_perf \"size=$i\" \"\n+\t\tgit rev-list HEAD --stdin /dev/null\n+\t\"\n+done\n+\n+test_done\ndiff --git a/tree-diff.c b/tree-diff.c\nindex 2a744dfaec..f3d916201b 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -120,7 +120,8 @@ static void ll_diff_tree_paths(\n \tstruct combine_diff_path ***tail, const struct object_id *oid,\n \tconst struct object_id **parents_oid, int nparent,\n \tstruct strbuf *base, struct diff_options *opt,\n-\tint depth);\n+\tint depth, struct pathspec_trie *pst);\n+\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@@ -205,7 +206,7 @@ static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_\n static void emit_path(struct combine_diff_path ***tail,\n \t\t struct strbuf *base, struct diff_options *opt,\n \t\t int nparent, struct tree_desc *t, struct tree_desc *tp,\n-\t\t int imin, int depth)\n+\t\t int imin, int depth, struct pathspec_trie *pst)\n {\n \tunsigned short mode;\n \tconst char *path;\n@@ -309,23 +310,95 @@ static void emit_path(struct combine_diff_path ***tail,\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\tll_diff_tree_paths(tail, oid, parents_oid, nparent, base, opt,\n-\t\t\t\t depth + 1);\n+\t\t\t\t depth + 1, pst);\n \t\tFAST_ARRAY_FREE(parents_oid, nparent);\n \t}\n \n \tstrbuf_setlen(base, old_baselen);\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, &opt->pathspec);\n \t\tif (match) {\n \t\t\tif (match == all_entries_not_interesting)\n@@ -433,7 +506,7 @@ static void ll_diff_tree_paths(\n \tstruct combine_diff_path ***tail, const struct object_id *oid,\n \tconst struct object_id **parents_oid, int nparent,\n \tstruct strbuf *base, struct diff_options *opt,\n-\tint depth)\n+\tint depth, struct pathspec_trie *pst)\n {\n \tstruct tree_desc t, *tp;\n \tvoid *ttree, **tptree;\n@@ -468,9 +541,9 @@ static void 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@@ -535,7 +608,7 @@ static void ll_diff_tree_paths(\n \n \t\t\t/* D += {δ(t,pi) if pi=p[imin]; \"+a\" if pi > p[imin]} */\n \t\t\temit_path(tail, base, opt, nparent,\n-\t\t\t\t &t, tp, imin, depth);\n+\t\t\t\t &t, tp, imin, depth, pst);\n \n \t\tskip_emit_t_tp:\n \t\t\t/* t↓, ∀ pi=p[imin] pi↓ */\n@@ -547,7 +620,7 @@ static void ll_diff_tree_paths(\n \t\telse if (cmp < 0) {\n \t\t\t/* D += \"+t\" */\n \t\t\temit_path(tail, base, opt, nparent,\n-\t\t\t\t &t, /*tp=*/NULL, -1, depth);\n+\t\t\t\t &t, /*tp=*/NULL, -1, depth, pst);\n \n \t\t\t/* t↓ */\n \t\t\tupdate_tree_entry(&t);\n@@ -563,7 +636,7 @@ static void ll_diff_tree_paths(\n \t\t\t}\n \n \t\t\temit_path(tail, base, opt, nparent,\n-\t\t\t\t /*t=*/NULL, tp, imin, depth);\n+\t\t\t\t /*t=*/NULL, tp, imin, depth, pst);\n \n \t\tskip_emit_tp:\n \t\t\t/* ∀ pi=p[imin] pi↓ */\n@@ -584,7 +657,8 @@ struct combine_diff_path *diff_tree_paths(\n \tstruct strbuf *base, struct diff_options *opt)\n {\n \tstruct combine_diff_path *head = NULL, **tail = &head;\n-\tll_diff_tree_paths(&tail, oid, parents_oid, nparent, base, opt, 0);\n+\tll_diff_tree_paths(&tail, oid, parents_oid, nparent, base, opt,\n+\t\t\t 0, opt->pathspec.trie);\n \treturn head;\n }\n \n\n-- \n2.49.0.rc2\n\n"},{"id":"515119","messageId":"20250326-toon-blame-tree-v1-8-4173133f3786@iotcl.com","threadId":"63201","inReplyTo":"20250326-toon-blame-tree-v1-0-4173133f3786@iotcl.com","subject":"[PATCH 8/8] blame-tree: narrow pathspec as we traverse","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-03-26T20:18:32Z","receivedAt":"2025-03-26T20:19:59Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"From: Jeff King \n\nAs we find out the \"last touched\" for each path, we cease to\ncare about that path. However, we traditionally have not\ntold the revision-walking machinery about this, for two\nreasons:\n\n 1. Munging the pathspecs mid-traversal is not an\n officially supported thing to be doing. It does seem to\n work, though, and with Duy's recent pathspec\n refactoring, it's fairly straightforward.\n\n 2. The pathspec machinery is slow. We know have to look at\n each pathspec to see if each tree entry is interesting.\n And since our cost to handle a diff_filepair is so\n cheap, it doesn't really help us much.\n\nIt turns out that (2) is not quite right, though. For the\ndiffs themselves, limiting the pathspec doesn't help at all.\nBut it does mean that we can simplify history more\naggressively, which may mean avoiding whole swaths of\nhistory that don't touch interesting paths. This happens\nespecially near the end of the traversal, when we are only\ninterested in a few paths, and there are many side branches\nthat do not touch any of them.\n\nAnd as of the last commit, the pathspec machinery is no\nlonger quadratic, so the cost to use it is easily worth\npaying, even for large trees.\n\nHere are runs of `git blame-tree --max-depth=0` for\ntorvalds/linux (a complex history with a small root tree)\nand git/git (a flat hierarchy with a large root tree):\n\nFor git/git:\n\n Benchmark 1: ./git.old blame-tree --max-depth=0\n Time (mean ± σ): 2.223 s ± 0.360 s [User: 1.808 s, System: 0.369 s]\n Range (min … max): 1.866 s … 2.927 s 10 runs\n\n Benchmark 2: ./git.new blame-tree --max-depth=0\n Time (mean ± σ): 945.0 ms ± 93.4 ms [User: 783.6 ms, System: 131.0 ms]\n Range (min … max): 846.4 ms … 1071.5 ms 10 runs\n\n Summary\n ./git.new blame-tree --max-depth=0 ran\n 2.35 ± 0.45 times faster than git.old blame-tree --max-depth=0\n\nFor torvalds/linux:\n\n Benchmark 1: ./git.old blame-tree --max-depth=0\n Time (mean ± σ): 13.504 s ± 0.545 s [User: 12.605 s, System: 0.583 s]\n Range (min … max): 12.947 s … 14.488 s 10 runs\n\n Benchmark 2: ./git.new blame-tree --max-depth=0\n Time (mean ± σ): 622.8 ms ± 39.2 ms [User: 522.1 ms, System: 95.7 ms]\n Range (min … max): 556.6 ms … 681.6 ms 10 runs\n\n Summary\n ./git.new blame-tree --max-depth=0 ran\n 21.68 ± 1.62 times faster than ./git.old blame-tree --max-depth=0\n\nNote that the output may change slightly in some cases due\nto the history pruning. This should be acceptable, as either\noutput is correct in these cases (e.g., scenarios like a\ncherry-picked commit on two parallel branches).\n\nSigned-off-by: Jeff King \n---\n blame-tree.c | 18 ++++++++++++++\n pathspec.c | 78 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n pathspec.h | 3 +++\n 3 files changed, 99 insertions(+)\n\ndiff --git a/blame-tree.c b/blame-tree.c\nindex ed4ec1e694..7be67520f8 100644\n--- a/blame-tree.c\n+++ b/blame-tree.c\n@@ -79,6 +79,18 @@ void blame_tree_init(struct repository *r, struct blame_tree *bt,\n \n \tif (add_from_revs(bt) < 0)\n \t\tdie(_(\"unable to setup blame-tree\"));\n+\n+\tpathspec_setup(&bt->rev.prune_data, &bt->paths);\n+\tcopy_pathspec(&bt->rev.pruning.pathspec, &bt->rev.prune_data);\n+\tcopy_pathspec(&bt->rev.diffopt.pathspec, &bt->rev.prune_data);\n+\tbt->rev.prune = 1;\n+\n+\t/*\n+\t * Have the diff engine tell us about everything, including trees.\n+\t * We may have used --max-depth to get our list of paths to blame,\n+\t * in which case we would mention trees explicitly.\n+\t */\n+\tbt->rev.diffopt.flags.tree_in_recursive = 1;\n }\n \n void blame_tree_release(struct blame_tree *bt)\n@@ -91,6 +103,7 @@ struct blame_tree_callback_data {\n \tstruct commit *commit;\n \tstruct string_list *paths;\n \tsize_t num_interesting;\n+\tstruct rev_info *rev;\n \n \tblame_tree_fn callback;\n \tvoid *callback_data;\n@@ -122,6 +135,10 @@ static void mark_path(const char *path, const struct object_id *oid,\n \tdata->num_interesting--;\n \tif (data->callback)\n \t\tdata->callback(path, data->commit, data->callback_data);\n+\n+\tpathspec_drop(&data->rev->pruning.pathspec, path);\n+\tclear_pathspec(&data->rev->diffopt.pathspec);\n+\tcopy_pathspec(&data->rev->diffopt.pathspec, &data->rev->pruning.pathspec);\n }\n \n static void blame_diff(struct diff_queue_struct *q,\n@@ -172,6 +189,7 @@ int blame_tree_run(struct blame_tree *bt, blame_tree_fn cb, void *cbdata)\n \tdata.num_interesting = bt->paths.nr;\n \tdata.callback = cb;\n \tdata.callback_data = cbdata;\n+\tdata.rev = &bt->rev;\n \n \tbt->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n \tbt->rev.diffopt.format_callback = blame_diff;\ndiff --git a/pathspec.c b/pathspec.c\nindex c174edef32..7ef2a55280 100644\n--- a/pathspec.c\n+++ b/pathspec.c\n@@ -117,6 +117,50 @@ struct pathspec_trie *pathspec_trie_build(const struct pathspec *pathspec)\n \treturn ret;\n }\n \n+static void pathspec_drop_from_trie(struct pathspec *ps,\n+\t\t\t\t const char *path)\n+{\n+\tstruct pathspec_trie *prev = NULL, *cur = ps->trie;\n+\tint pos = -1;\n+\n+\tif (!cur)\n+\t\treturn;\n+\n+\twhile (*path) {\n+\t\tconst char *end = strchrnul(path, '/');\n+\t\tsize_t len = end - path;\n+\t\tpos = pathspec_trie_lookup(cur, path, len);\n+\n+\t\tif (pos < 0)\n+\t\t\tdie(\"BUG: didn't find the pathspec trie we matched\");\n+\n+\t\tprev = cur;\n+\t\tcur = cur->entries[pos];\n+\t\tpath = end;\n+\t\twhile (*path == '/')\n+\t\t\tpath++;\n+\t}\n+\n+\tif (!cur->terminal)\n+\t\tdie(\"BUG: pathspec trie we found isn't terminal?\");\n+\n+\tif (cur->nr) {\n+\t\tcur->terminal = 0;\n+\t\tcur->must_be_dir = 0;\n+\t\treturn;\n+\t}\n+\n+\tfree(cur);\n+\tif (pos < 0)\n+\t\tps->trie = NULL;\n+\telse if (prev) {\n+\t\tprev->nr--;\n+\t\tmemmove(prev->entries + pos,\n+\t\t\tprev->entries + pos + 1,\n+\t\t\tsizeof(*prev->entries) * (prev->nr - pos));\n+\t}\n+}\n+\n static void pathspec_trie_clear(struct pathspec_trie *t)\n {\n \tif (t) {\n@@ -878,6 +922,40 @@ void copy_pathspec(struct pathspec *dst, const struct pathspec *src)\n \tdst->trie = pathspec_trie_build(dst);\n }\n \n+void pathspec_setup(struct pathspec *ps, const struct string_list *paths)\n+{\n+\tstruct strvec argv = STRVEC_INIT;\n+\tsize_t i;\n+\n+\tfor (i = 0; i < paths->nr; i++)\n+\t\tstrvec_push(&argv, paths->items[i].string);\n+\n+\tclear_pathspec(ps);\n+\tparse_pathspec(ps, PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,\n+\t\t PATHSPEC_PREFER_FULL | PATHSPEC_LITERAL_PATH, \"\",\n+\t\t argv.v);\n+\tstrvec_clear(&argv);\n+}\n+\n+void pathspec_drop(struct pathspec *ps, const char *path)\n+{\n+\tint i;\n+\n+\t/* We know these are literals, so we can just strcmp */\n+\tfor (i = 0; i < ps->nr; i++)\n+\t\tif (!strcmp(ps->items[i].match, path))\n+\t\t\tbreak;\n+\n+\tif (i == ps->nr)\n+\t\tdie(\"BUG: didn't find the pathspec we just matched\");\n+\n+\tmemmove(ps->items + i, ps->items + i + 1,\n+\t\tsizeof(*ps->items) * (ps->nr - i - 1));\n+\tps->nr--;\n+\n+\tpathspec_drop_from_trie(ps, path);\n+}\n+\n void clear_pathspec(struct pathspec *pathspec)\n {\n \tint i, j;\ndiff --git a/pathspec.h b/pathspec.h\nindex ff11599d25..a46b3177e3 100644\n--- a/pathspec.h\n+++ b/pathspec.h\n@@ -3,6 +3,7 @@\n \n struct index_state;\n struct pathspec;\n+struct string_list;\n \n /* Pathspec magic */\n #define PATHSPEC_FROMTOP\t(1<<0)\n@@ -152,6 +153,8 @@ void parse_pathspec_file(struct pathspec *pathspec,\n \t\t\t int nul_term_line);\n \n void copy_pathspec(struct pathspec *dst, const struct pathspec *src);\n+void pathspec_setup(struct pathspec *ps, const struct string_list *paths);\n+void pathspec_drop(struct pathspec *ps, const char *path);\n void clear_pathspec(struct pathspec *);\n \n /*\n\n-- \n2.49.0.rc2\n\n"},{"id":"515122","messageId":"Z+Rl43VR3ErE0Bu4@nand.local","threadId":"63201","inReplyTo":"20250326-toon-blame-tree-v1-0-4173133f3786@iotcl.com","subject":"Re: [PATCH 0/8] Introduce git-blame-tree(1) command","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-26T20:38:59Z","receivedAt":"2025-03-26T20:39:01Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Wed, Mar 26, 2025 at 09:18:24PM +0100, Toon Claes wrote:\n> This is yet another attempt to upstream the builtin command\n> `git-blame-tree(1)`. This command is similar to git-blame(1) and shows\n> the most recent modification to paths in a tree..\n>\n> The last attempt (I'm aware of) was made by Ævar in 2023[1]. That\n> series was based of patches by Peff written in 2011[2].\n\nFor what it's worth, the blame-tree implementation that this came from\nhas evolved significantly since it was originally written in 2011. Most\nrecently Stolee and I worked on a version that uses changed-path Bloom\nfilters to narrow the search, passing un-blamed paths to their parents\nat each level of the traversal.\n\nI wonder if it would be easier to start from scratch with the modern\nimplementation rather than land this one and try to build on top of it.\n\nThanks,\nTaylor\n"},{"id":"515131","messageId":"20250327063243.GB3042475@coredump.intra.peff.net","threadId":"63201","inReplyTo":"Z+Rl43VR3ErE0Bu4@nand.local","subject":"Re: [PATCH 0/8] Introduce git-blame-tree(1) command","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-03-27T06:32:43Z","receivedAt":"2025-03-27T06:32:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 26, 2025 at 04:38:59PM -0400, Taylor Blau wrote:\n\n> On Wed, Mar 26, 2025 at 09:18:24PM +0100, Toon Claes wrote:\n> > This is yet another attempt to upstream the builtin command\n> > `git-blame-tree(1)`. This command is similar to git-blame(1) and shows\n> > the most recent modification to paths in a tree..\n> >\n> > The last attempt (I'm aware of) was made by Ævar in 2023[1]. That\n> > series was based of patches by Peff written in 2011[2].\n> \n> For what it's worth, the blame-tree implementation that this came from\n> has evolved significantly since it was originally written in 2011. Most\n> recently Stolee and I worked on a version that uses changed-path Bloom\n> filters to narrow the search, passing un-blamed paths to their parents\n> at each level of the traversal.\n> \n> I wonder if it would be easier to start from scratch with the modern\n> implementation rather than land this one and try to build on top of it.\n\nYeah, I'd suggest starting with that work from you and Stolee (though I\ndo not know if it was ever made public?). It should be much faster and\nwill have been battle-tested in production.\n\nThe pathspec-trie stuff is, I think, still a reasonable idea for general\nuse. But IIRC, the rewritten blame-tree you guys worked on does not\nbenefit from it, because it ditches pathspecs entirely (both because\nthey're too slow without the tries, but also because it's important to\ncontinually narrow the pathspec while traversing). That trie code was\nnever run in production, I think (and I see there is a patch to narrow\nthe pathspec while traversing; I suspect that likewise was never used).\n\nThe max-depth diff code is also in theory a reasonable thing to have in\ngeneral. But it is awkward to use, and not really necessary for\nblame-tree. There we really only care about recursing vs not recursing,\nbut the usual \"recursive\" flag for diffing isn't enough (we have to\nrecurse down to the tree of interest, but may not want to go further). I\ndon't remember how that is handled in your blame-tree rewrites.\n\nSo that really mostly leaves the blame-tree scaffolding itself. I\nremember Junio left a lot of good comments on the original thread on how\nmerges should be handled, but I don't think I ever fixed those bits. I\ndon't recall what your rewritten code does there, but I think it may\nhave improved things.\n\nSo yeah. I don't know if all of this is really a very good starting\npoint. Taylor, if you can share the current code that GitHub is running,\nI think that would be beneficial for the community.\n\n-Peff\n"},{"id":"515195","messageId":"511c7ce2-cd1c-4d0a-98b7-c7f5569a3eef@gmail.com","threadId":"63201","inReplyTo":"Z+Rl43VR3ErE0Bu4@nand.local","subject":"Re: [PATCH 0/8] Introduce git-blame-tree(1) command","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-03-27T12:04:50Z","receivedAt":"2025-03-27T12:04:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/26/2025 4:38 PM, Taylor Blau wrote:\n> On Wed, Mar 26, 2025 at 09:18:24PM +0100, Toon Claes wrote:\n>> This is yet another attempt to upstream the builtin command\n>> `git-blame-tree(1)`. This command is similar to git-blame(1) and shows\n>> the most recent modification to paths in a tree..\n>>\n>> The last attempt (I'm aware of) was made by Ævar in 2023[1]. That\n>> series was based of patches by Peff written in 2011[2].\n> \n> For what it's worth, the blame-tree implementation that this came from\n> has evolved significantly since it was originally written in 2011. Most\n> recently Stolee and I worked on a version that uses changed-path Bloom\n> filters to narrow the search, passing un-blamed paths to their parents\n> at each level of the traversal.\n\nIt's worth mentioning that the underlying algorithm was nearly rebuilt\nfrom scratch with this \"passing un-blamed paths to their parents\" aspect,\nwhich unlocked other features such as caching results to be used by\nfuture queries, even when the tip branch advances.\n\nWith that in mind, using the 2011 version is unlikely to be valuable.\n\nTaylor: do you have a drop of the latest blame-tree implementation that\ncould be shared with Toon?\n\nThanks,\n-Stolee\n\n"},{"id":"515210","messageId":"Z+XJ+1L3PnC9Dyba@nand.local","threadId":"63201","inReplyTo":"20250327063243.GB3042475@coredump.intra.peff.net","subject":"Re: [PATCH 0/8] Introduce git-blame-tree(1) command","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-27T21:58:19Z","receivedAt":"2025-03-27T21:58:21Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Mar 27, 2025 at 02:32:43AM -0400, Jeff King wrote:\n> The pathspec-trie stuff is, I think, still a reasonable idea for general\n> use. But IIRC, the rewritten blame-tree you guys worked on does not\n> benefit from it, because it ditches pathspecs entirely (both because\n> they're too slow without the tries, but also because it's important to\n> continually narrow the pathspec while traversing). That trie code was\n> never run in production, I think (and I see there is a patch to narrow\n> the pathspec while traversing; I suspect that likewise was never used).\n\nYeah, the rewritten blame-tree code uses changed-path Bloom filters to\nnarrow the set of revisions that we need to actually compute tree-diffs\nfor.\n\nThe general idea is that we have a set of paths that we have yet to\nblame, and those are the \"interesting\" ones. IOW, if a changed-path\nBloom filter tells us that we are at some revision where there is maybe\na change to one or more unblamed paths, we need to compute a tree-diff.\nBut if the Bloom filter says \"no\", then we can skip the tree-diff at\nthat layer entirely.\n\n> The max-depth diff code is also in theory a reasonable thing to have in\n> general. But it is awkward to use, and not really necessary for\n> blame-tree. There we really only care about recursing vs not recursing,\n> but the usual \"recursive\" flag for diffing isn't enough (we have to\n> recurse down to the tree of interest, but may not want to go further). I\n> don't remember how that is handled in your blame-tree rewrites.\n\nI think that's mostly true, but the blame-tree caching stuff that Stolee\nworked on many years ago and mentioned below does require it IIRC.\n\n> So yeah. I don't know if all of this is really a very good starting\n> point. Taylor, if you can share the current code that GitHub is running,\n> I think that would be beneficial for the community.\n\nSure. You can fetch from the 'tb/blame-tree' branch from my tree (which\nis located at 'git@github.com:ttaylorr/git.git'). I owe a huge \"thank\nyou\" to Victoria Dye, who split out the various topics from GitHub's\nfork into individual rebased branches.\n\nThere were many more patches on top that came after Victoria's split\nabove, and I applied those manually. The commit structure probably needs\nsignificant clean-up and polishing before it's ready for serious review,\nsince this is more-or-less a raw dump of the work on GitHub's side over\nmore than a decade.\n\nIt also doesn't pass the tests in t9932 (and the test number should\nprobably also be reworked, it's in the t99xx range so that inclusion in\nGitHub's fork doesn't cause collisions with new tests when we merge\nupstream). To that end, I removed everybody's Signed-off-by in case I\nhave mangled their work in some way unintentionally.\n\nThanks,\nTaylor\n"},{"id":"515232","messageId":"87wmc9ffpo.fsf@iotcl.com","threadId":"63201","inReplyTo":"Z+XJ+1L3PnC9Dyba@nand.local","subject":"Re: [PATCH 0/8] Introduce git-blame-tree(1) command","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-03-28T13:27:15Z","receivedAt":"2025-03-28T13:27:31Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Taylor Blau writes:\n\n> Sure. You can fetch from the 'tb/blame-tree' branch from my tree (which\n> is located at 'git@github.com:ttaylorr/git.git'). I owe a huge \"thank\n> you\" to Victoria Dye, who split out the various topics from GitHub's\n> fork into individual rebased branches.\n>\n> There were many more patches on top that came after Victoria's split\n> above, and I applied those manually. The commit structure probably needs\n> significant clean-up and polishing before it's ready for serious review,\n> since this is more-or-less a raw dump of the work on GitHub's side over\n> more than a decade.\n>\n> It also doesn't pass the tests in t9932 (and the test number should\n> probably also be reworked, it's in the t99xx range so that inclusion in\n> GitHub's fork doesn't cause collisions with new tests when we merge\n> upstream). To that end, I removed everybody's Signed-off-by in case I\n> have mangled their work in some way unintentionally.\n\nThanks for sharing. I will check it out.\n\n-- \nToon\n"},{"id":"515416","messageId":"20250401092952.GD21089@coredump.intra.peff.net","threadId":"63201","inReplyTo":"Z+XJ+1L3PnC9Dyba@nand.local","subject":"Re: [PATCH 0/8] Introduce git-blame-tree(1) command","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-04-01T09:29:52Z","receivedAt":"2025-04-01T09:29:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 27, 2025 at 05:58:19PM -0400, Taylor Blau wrote:\n\n> On Thu, Mar 27, 2025 at 02:32:43AM -0400, Jeff King wrote:\n> > The pathspec-trie stuff is, I think, still a reasonable idea for general\n> > use. But IIRC, the rewritten blame-tree you guys worked on does not\n> > benefit from it, because it ditches pathspecs entirely (both because\n> > they're too slow without the tries, but also because it's important to\n> > continually narrow the pathspec while traversing). That trie code was\n> > never run in production, I think (and I see there is a patch to narrow\n> > the pathspec while traversing; I suspect that likewise was never used).\n> \n> Yeah, the rewritten blame-tree code uses changed-path Bloom filters to\n> narrow the set of revisions that we need to actually compute tree-diffs\n> for.\n> \n> The general idea is that we have a set of paths that we have yet to\n> blame, and those are the \"interesting\" ones. IOW, if a changed-path\n> Bloom filter tells us that we are at some revision where there is maybe\n> a change to one or more unblamed paths, we need to compute a tree-diff.\n> But if the Bloom filter says \"no\", then we can skip the tree-diff at\n> that layer entirely.\n\nYou'd still in theory benefit from the tree-diffs you _do_ run using a\ncontinually narrowing pathspec. Skimming over the code from your\ntb/blame-tree branch, it looks like it's just fed the original pathspec.\nBut that's probably good enough in practice. Especially for\nnon-recursive blame-trees, where pruning already-matched entries will\nnever save you from opening another tree anyway.\n\n> > So yeah. I don't know if all of this is really a very good starting\n> > point. Taylor, if you can share the current code that GitHub is running,\n> > I think that would be beneficial for the community.\n> \n> Sure. You can fetch from the 'tb/blame-tree' branch from my tree (which\n> is located at 'git@github.com:ttaylorr/git.git'). I owe a huge \"thank\n> you\" to Victoria Dye, who split out the various topics from GitHub's\n> fork into individual rebased branches.\n\nThanks. I don't have time to pick it up as a topic myself, but hopefully\nit can be useful to Toon (or any others interested in the topic).\n\n-Peff\n"}]}