{"thread":{"id":"59203","subject":"[PATCH] blame-tree: add library and tests via \"test-tool blame-tree\"","startedAt":"2023-02-05T20:47:16Z","lastAt":"2023-03-08T15:50:12Z","messageCount":6,"participants":["Ævar Arnfjörð Bjarmason","Derrick Stolee","Jeff King","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"471541","messageId":"patch-1.1-0ea849d900b-20230205T204104Z-avarab@gmail.com","threadId":"59203","inReplyTo":null,"subject":"[PATCH] blame-tree: add library and tests via \"test-tool blame-tree\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2023-02-05T20:47:03Z","receivedAt":"2023-02-05T20:47:16Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"From: Jeff King <peff@peff.net>\n\nThe \"blame-tree\" library allows for finding the most recent\nmodification to paths in a tree. It does so by expanding the tree at a\ngiven commit, taking note of the current state of each path, and then\nwalking backwards through history looking for commits where each path\nchanged into its final sha1.\n\nThe \"git blame-tree\" command was first noted on the ML 2011[1], and\nover the years there have been mentions of it[2][3], and whether it\ncould be upstreamed. The sources have been available at [4]'s\n\"jk/blame-tree-wip\" and \"jk/faster-blame-tree-wip\" branches.\n\nThis change attempts to start upstreaming this command, but rather\nthan adding a command whose interface & semantics may be controversial\nstarts by exposing & testing the core of its library through a new\ntest helper.\n\nAn eventual \"git blame-tree\" command, or e.g. a new format for \"git\nls-tree\" to show what a path \"blames\" to can then be implemented with\nthis library.\n\nAside from changing the code found at [4] into a test-tool the most\nnotable changes here are:\n\n* Removing the \"--max-depth\" changes to the diff code. We'll need\n  those eventually, but it's not required for a blame of a given list\n  of paths.\n\n  As has been noted in previous on-list discussions the semantics of\n  the \"max-depth\" changes might be controversial, so it's worthwhile\n  to split those out so that they can be reviewed separately.\n\n* Made the \"blame-tree\" helper take \"--\" before any revision options,\n  for clarity. An eventual built-in command (if any) probably doesn't\n  want to enforce this, but it makes it clearer in the test helper\n  what's an argument for \"blame-tree\" itself, and what's an argument for\n  the revision machinery.\n\n* Minor updates for using C99 syntax, and \"size_t\" instead of \"int\"\n  when we're iterating over types whose \"nr\" is that size.\n\n* Avoid sub-shelling in the tests, use \"test-tool -C ..\" instead.\n\n1. https://lore.kernel.org/git/20110302164031.GA18233@sigill.intra.peff.net/\n2. https://lore.kernel.org/git/20160831054201.ldlwptlmcndjmfwu@sigill.intra.peff.net/\n3. https://public-inbox.org/git/20130318121243.GC14789@sigill.intra.peff.net/\n4. https://github.com/peff/git/\n4. https://gitlab.com/gitlab-org/git/-/issues/114\n\nCommit-message-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\nSigned-off-by: Jeff King <peff@peff.net>\nSigned-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n---\n\nThe range-diff here is to peff's jk/blame-tree-wip. As noted above\nthis is far from the full thing, but hopefully getting the basic bits\nof the library (sans the max-depth question) will make the review of\nsubsequent bits easier.\n\nCI & branch for this at:\nhttps://github.com/avar/git/tree/avar-jk/blame-tree-prep\n\nRange-diff:\n1:  65cfa9c91cd < -:  ----------- within_depth: fix return for empty path\n2:  fa5f0c6dbec < -:  ----------- teach tree-diff a max-depth parameter\n3:  c632d45c474 < -:  ----------- combine-diff: zero memory used for callback filepairs\n4:  259e04af942 ! 1:  0ea849d900b add blame-tree command [ci skip]\n    @@ Metadata\n     Author: Jeff King <peff@peff.net>\n     \n      ## Commit message ##\n    -    add blame-tree command [ci skip]\n    +    blame-tree: add library and tests via \"test-tool blame-tree\"\n     \n    -    This command shows the most recent modification to paths in\n    -    a tree. It does so by expanding the tree at a given commit,\n    -    taking note of the current state of each path, and then\n    -    walking backwards through history looking for commits where\n    -    each path changed into its final sha1.\n    +    The \"blame-tree\" library allows for finding the most recent\n    +    modification to paths in a tree. It does so by expanding the tree at a\n    +    given commit, taking note of the current state of each path, and then\n    +    walking backwards through history looking for commits where each path\n    +    changed into its final sha1.\n     \n    -    Signed-off-by: Jeff King <peff@peff.net>\n    +    The \"git blame-tree\" command was first noted on the ML 2011[1], and\n    +    over the years there have been mentions of it[2][3], and whether it\n    +    could be upstreamed. The sources have been available at [4]'s\n    +    \"jk/blame-tree-wip\" and \"jk/faster-blame-tree-wip\" branches.\n     \n    - ## .gitignore ##\n    -@@\n    - /git-archive\n    - /git-bisect\n    - /git-blame\n    -+/git-blame-tree\n    - /git-branch\n    - /git-bugreport\n    - /git-bundle\n    +    This change attempts to start upstreaming this command, but rather\n    +    than adding a command whose interface & semantics may be controversial\n    +    starts by exposing & testing the core of its library through a new\n    +    test helper.\n    +\n    +    An eventual \"git blame-tree\" command, or e.g. a new format for \"git\n    +    ls-tree\" to show what a path \"blames\" to can then be implemented with\n    +    this library.\n    +\n    +    Aside from changing the code found at [4] into a test-tool the most\n    +    notable changes here are:\n    +\n    +    * Removing the \"--max-depth\" changes to the diff code. We'll need\n    +      those eventually, but it's not required for a blame of a given list\n    +      of paths.\n    +\n    +      As has been noted in previous on-list discussions the semantics of\n    +      the \"max-depth\" changes might be controversial, so it's worthwhile\n    +      to split those out so that they can be reviewed separately.\n    +\n    +    * Made the \"blame-tree\" helper take \"--\" before any revision options,\n    +      for clarity. An eventual built-in command (if any) probably doesn't\n    +      want to enforce this, but it makes it clearer in the test helper\n    +      what's an argument for \"blame-tree\" itself, and what's an argument for\n    +      the revision machinery.\n    +\n    +    * Minor updates for using C99 syntax, and \"size_t\" instead of \"int\"\n    +      when we're iterating over types whose \"nr\" is that size.\n    +\n    +    * Avoid sub-shelling in the tests, use \"test-tool -C ..\" instead.\n    +\n    +    1. https://lore.kernel.org/git/20110302164031.GA18233@sigill.intra.peff.net/\n    +    2. https://lore.kernel.org/git/20160831054201.ldlwptlmcndjmfwu@sigill.intra.peff.net/\n    +    3. https://public-inbox.org/git/20130318121243.GC14789@sigill.intra.peff.net/\n    +    4. https://github.com/peff/git/\n    +    4. https://gitlab.com/gitlab-org/git/-/issues/114\n    +\n    +    Commit-message-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n    +    Signed-off-by: Jeff King <peff@peff.net>\n    +    Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n     \n      ## Makefile ##\n    +@@ Makefile: PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))\n    + \n    + TEST_BUILTINS_OBJS += test-advise.o\n    + TEST_BUILTINS_OBJS += test-bitmap.o\n    ++TEST_BUILTINS_OBJS += test-blame-tree.o\n    + TEST_BUILTINS_OBJS += test-bloom.o\n    + TEST_BUILTINS_OBJS += test-bundle-uri.o\n    + TEST_BUILTINS_OBJS += test-cache-tree.o\n     @@ Makefile: LIB_OBJS += archive.o\n      LIB_OBJS += attr.o\n      LIB_OBJS += base85.o\n    @@ Makefile: LIB_OBJS += archive.o\n      LIB_OBJS += blame.o\n      LIB_OBJS += blob.o\n      LIB_OBJS += bloom.o\n    -@@ Makefile: BUILTIN_OBJS += builtin/apply.o\n    - BUILTIN_OBJS += builtin/archive.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\n     \n      ## blame-tree.c (new) ##\n     @@\n     +#include \"cache.h\"\n     +#include \"blame-tree.h\"\n    ++#include \"strvec.h\"\n    ++#include \"hash.h\"\n     +#include \"commit.h\"\n    -+#include \"diff.h\"\n     +#include \"diffcore.h\"\n    ++#include \"diff.h\"\n    ++#include \"object.h\"\n     +#include \"revision.h\"\n     +#include \"log-tree.h\"\n    -+#include \"dir.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    @@ blame-tree.c (new)\n     +};\n     +\n     +static void add_from_diff(struct diff_queue_struct *q,\n    -+\t\t\t  struct diff_options *opt,\n    -+\t\t\t  void *data)\n    ++\t\t\t  struct diff_options *opt, void *data)\n     +{\n     +\tstruct blame_tree *bt = data;\n    -+\tint i;\n     +\n    -+\tfor (i = 0; i < q->nr; i++) {\n    ++\tfor (size_t 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\tstring_list_append(&bt->paths, p->two->path)->util = ent;\n     +\t}\n     +}\n     +\n     +static int add_from_revs(struct blame_tree *bt)\n     +{\n    -+\tunsigned int i;\n    -+\tint count = 0;\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 (i = 0; i < bt->rev.pending.nr; i++) {\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    -+\n    -+\t\tdiff_tree_sha1(EMPTY_TREE_SHA1_BIN, obj->item->oid.hash, \"\", &diffopt);\n    ++\t\t\treturn error(_(\"can only blame one tree at a time\"));\n    ++\t\tdiff_tree_oid(the_hash_algo->empty_tree, &obj->item->oid, \"\",\n    ++\t\t\t      &diffopt);\n     +\t\tdiff_flush(&diffopt);\n     +\t}\n     +\n    @@ blame-tree.c (new)\n     +\treturn 0;\n     +}\n     +\n    -+void blame_tree_init(struct blame_tree *bt, int argc, const char **argv,\n    -+\t\t     const char *prefix)\n    ++void blame_tree_init(struct blame_tree *bt,\n    ++\t\t     const struct blame_tree_options *opts)\n     +{\n    -+\tmemset(bt, 0, sizeof(*bt));\n    -+\tbt->paths.strdup_strings = 1;\n    -+\n    -+\tinit_revisions(&bt->rev, prefix);\n    -+\tbt->rev.def = \"HEAD\";\n    ++\tinit_revisions(&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    -+\tDIFF_OPT_SET(&bt->rev.diffopt, RECURSIVE);\n    -+\tsetup_revisions(argc, argv, &bt->rev, NULL);\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    ++\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    -+\n     +struct blame_tree_callback_data {\n     +\tstruct commit *commit;\n     +\tstruct string_list *paths;\n    -+\tint num_interesting;\n    ++\tsize_t num_interesting;\n     +\n    -+\tblame_tree_callback callback;\n    ++\tblame_tree_fn callback;\n     +\tvoid *callback_data;\n     +};\n     +\n    @@ blame-tree.c (new)\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 (oidcmp(oid, &ent->oid))\n    ++\tif (!oideq(oid, &ent->oid))\n     +\t\treturn;\n     +\n     +\tent->commit = data->commit;\n    @@ blame-tree.c (new)\n     +}\n     +\n     +static void blame_diff(struct diff_queue_struct *q,\n    -+\t\t\t struct diff_options *opt, void *cbdata)\n    ++\t\t       struct diff_options *opt, void *cbdata)\n     +{\n     +\tstruct blame_tree_callback_data *data = cbdata;\n    -+\tint i;\n     +\n    -+\tfor (i = 0; i < q->nr; i++) {\n    ++\tfor (size_t 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    @@ blame-tree.c (new)\n     +\t}\n     +}\n     +\n    -+int blame_tree_run(struct blame_tree *bt, blame_tree_callback cb, void *cbdata)\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    @@ blame-tree.c (new)\n     +\n     +\tprepare_revision_walk(&bt->rev);\n     +\n    -+\twhile (data.num_interesting > 0) {\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_sha1(EMPTY_TREE_SHA1_BIN,\n    -+\t\t\t\t       data.commit->object.oid.hash,\n    ++\t\t\tdiff_tree_oid(the_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}\n    -+\t\telse\n    ++\t\t} else {\n     +\t\t\tlog_tree_commit(&bt->rev, data.commit);\n    ++\t\t}\n     +\t}\n     +\n     +\treturn 0;\n    @@ blame-tree.h (new)\n     +#ifndef BLAME_TREE_H\n     +#define BLAME_TREE_H\n     +\n    -+#include \"commit.h\"\n    -+#include \"diff.h\"\n    -+#include \"revision.h\"\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    ++#define BLAME_TREE_OPTIONS_INIT(...) { \\\n    ++\t.args = STRVEC_INIT, \\\n    ++\t__VA_ARGS__ \\\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     +};\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 blame_tree *,\n    -+\t\t     int argc, const char **argv, const char *prefix);\n    ++void blame_tree_init(struct blame_tree *bt,\n    ++\t\t     const struct blame_tree_options *opts);\n     +void blame_tree_release(struct blame_tree *);\n     +\n    -+typedef void (*blame_tree_callback)(const char *path,\n    -+\t\t\t\t    const struct commit *commit,\n    -+\t\t\t\t    void *data);\n    -+int blame_tree_run(struct blame_tree *,\n    -+\t\t   blame_tree_callback cb,\n    -+\t\t   void *data);\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 */\n     \n    - ## builtin.h ##\n    -@@ builtin.h: int cmd_apply(int argc, const char **argv, const char *prefix);\n    - int cmd_archive(int argc, const char **argv, const char *prefix);\n    - int cmd_bisect(int argc, const char **argv, const char *prefix);\n    - int cmd_blame(int argc, const char **argv, const char *prefix);\n    -+int cmd_blame_tree(int argc, const char **argv, const char *prefix);\n    - int cmd_branch(int argc, const char **argv, const char *prefix);\n    - int cmd_bugreport(int argc, const char **argv, const char *prefix);\n    - int cmd_bundle(int argc, const char **argv, const char *prefix);\n    -\n    - ## builtin/blame-tree.c (new) ##\n    + ## t/helper/test-blame-tree.c (new) ##\n     @@\n    -+#include \"cache.h\"\n    ++#include \"test-tool.h\"\n     +#include \"blame-tree.h\"\n     +#include \"quote.h\"\n    ++#include \"config.h\"\n     +#include \"parse-options.h\"\n     +\n     +static void show_entry(const char *path, const struct commit *commit, void *d)\n    @@ builtin/blame-tree.c (new)\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    ++\twrite_name_quoted(path, stdout, bt->rev.diffopt.line_termination);\n     +\n     +\tfflush(stdout);\n     +}\n     +\n    -+int cmd_blame_tree(int argc, const char **argv, const char *prefix)\n    ++int cmd__blame_tree(int argc, const char **argv)\n     +{\n    -+\tstruct blame_tree bt;\n    ++\tconst char *prefix = setup_git_directory();\n    ++\tstruct blame_tree_options opts = BLAME_TREE_OPTIONS_INIT(\n    ++\t\t.prefix = prefix,\n    ++\t\t.recursive = 1,\n    ++\t);\n    ++\tstruct blame_tree bt = BLAME_TREE_INIT;\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    ++\tstatic char const* const usage[] = {\n    ++\t\t\"test-tool blame-tree [--no-recursive] [-- <rev-opts>]\",\n    ++\t\tNULL\n    ++\t};\n    ++\n    ++\targc = parse_options(argc, argv, prefix, options, usage,\n    ++\t\t\t     PARSE_OPT_KEEP_DASHDASH);\n    ++\n    ++\tif (argc) {\n    ++\t\tif (strcmp(argv[0], \"--\") &&\n    ++\t\t    strcmp(argv[0], \"--end-of-options\"))\n    ++\t\t\tusage_msg_opt(\"need -- before <rev-opts>\", usage, options);\n    ++\t\targc--;\n    ++\t\targv++;\n    ++\t}\n     +\n    -+\tgit_config(git_default_config, NULL);\n    ++\tif (repo_get_oid(the_repository, \"HEAD\", &opts.oid))\n    ++\t\t die(\"unable to get HEAD\");\n     +\n    -+\tblame_tree_init(&bt, argc, argv, prefix);\n    ++\tstrvec_push(&opts.args, \"blame-tree\");\n    ++\tif (argc)\n    ++\t\tstrvec_pushv(&opts.args, argv);\n    ++\tblame_tree_init(&bt, &opts);\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     +}\n     \n    - ## git.c ##\n    -@@ git.c: static struct cmd_struct commands[] = {\n    - \t{ \"archive\", cmd_archive, RUN_SETUP_GENTLY },\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 },\n    + ## t/helper/test-tool.c ##\n    +@@ t/helper/test-tool.c: static const char * const test_tool_usage[] = {\n    + static struct test_cmd cmds[] = {\n    + \t{ \"advise\", cmd__advise_if_enabled },\n    + \t{ \"bitmap\", cmd__bitmap },\n    ++\t{ \"blame-tree\", cmd__blame_tree },\n    + \t{ \"bloom\", cmd__bloom },\n    + \t{ \"bundle-uri\", cmd__bundle_uri },\n    + \t{ \"cache-tree\", cmd__cache_tree },\n    +\n    + ## t/helper/test-tool.h ##\n    +@@\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);\n     \n    - ## t/t8011-blame-tree.sh (new) ##\n    + ## t/t8020-blame-tree-lib.sh (new) ##\n     @@\n     +#!/bin/sh\n     +\n    -+test_description='basic blame-tree tests'\n    ++test_description='basic blame-tree library tests'\n    ++\n     +. ./test-lib.sh\n     +\n     +test_expect_success 'setup' '\n    @@ t/t8011-blame-tree.sh (new)\n     +'\n     +\n     +test_expect_success 'cannot blame two trees' '\n    -+\ttest_must_fail git blame-tree HEAD HEAD~1\n    ++\ttest_must_fail test-tool 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    -+\tgit blame-tree \"$@\" >actual &&\n    -+\tgit name-rev --stdin --name-only --tags <actual >tmp &&\n    -+\tmv tmp actual &&\n    -+\ttr '\\t' ' ' <actual >tmp &&\n    -+\tmv tmp actual &&\n    -+\tsort <actual >tmp &&\n    -+\tmv tmp actual &&\n    ++\ttest_when_finished \"rm -f tmp.*\" &&\n    ++\ttest-tool ${indir:+-C \"$indir\"} \\\n    ++\t\tblame-tree \"$@\" >tmp.1 &&\n    ++\tgit name-rev --annotate-stdin --name-only --tags \\\n    ++\t\t<tmp.1 >tmp.2 &&\n    ++\ttr '\\t' ' ' <tmp.2 >tmp.3 &&\n    ++\tsort tmp.3 >actual &&\n     +\ttest_cmp expect actual\n     +}\n     +\n    @@ t/t8011-blame-tree.sh (new)\n     +'\n     +\n     +test_expect_success 'blame root' '\n    -+\tcheck_blame --max-depth=0 <<-\\EOF\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 --max-depth=1 a <<-\\EOF\n    ++\tcheck_blame -- a <<-\\EOF\n     +\t2 a/file\n    -+\t3 a/b\n    ++\t3 a/b/file\n     +\tEOF\n     +'\n     +\n     +test_expect_success 'blame from non-HEAD commit' '\n    -+\tcheck_blame --max-depth=0 HEAD^ <<-\\EOF\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    -+\tcd a &&\n    -+\tcheck_blame --max-depth=0 <<-\\EOF\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     +\n    -+test_expect_success 'blame from subdir uses relative pathspecs' '(\n    -+\tcd a &&\n    -+\tcheck_blame --max-depth=1 b <<-\\EOF\n    ++test_expect_success 'blame from subdir uses relative pathspecs' '\n    ++\tcheck_blame -C a -- b <<-\\EOF\n     +\t3 a/b/file\n     +\tEOF\n    -+)'\n    ++'\n     +\n     +test_expect_success 'limit blame traversal by count' '\n    -+\tcheck_blame --max-depth=0 -1 <<-\\EOF\n    ++\tcheck_blame --no-recursive -- -1 <<-\\EOF\n     +\t3 a\n     +\t^2 file\n     +\tEOF\n     +'\n     +\n     +test_expect_success 'limit blame traversal by commit' '\n    -+\tcheck_blame --max-depth=0 HEAD~2..HEAD <<-\\EOF\n    ++\tcheck_blame --no-recursive -- HEAD~2..HEAD <<-\\EOF\n     +\t3 a\n     +\t^1 file\n     +\tEOF\n    @@ t/t8011-blame-tree.sh (new)\n     +\ttest_commit c2 conflict &&\n     +\ttest_must_fail git merge c1 &&\n     +\ttest_commit resolved conflict &&\n    -+\tcheck_blame conflict <<-\\EOF\n    ++\tcheck_blame -- conflict <<-\\EOF\n     +\tresolved conflict\n     +\tEOF\n     +'\n\n Makefile                   |   2 +\n blame-tree.c               | 195 +++++++++++++++++++++++++++++++++++++\n blame-tree.h               |  39 ++++++++\n t/helper/test-blame-tree.c |  62 ++++++++++++\n t/helper/test-tool.c       |   1 +\n t/helper/test-tool.h       |   1 +\n t/t8020-blame-tree-lib.sh  | 138 ++++++++++++++++++++++++++\n 7 files changed, 438 insertions(+)\n create mode 100644 blame-tree.c\n create mode 100644 blame-tree.h\n create mode 100644 t/helper/test-blame-tree.c\n create mode 100755 t/t8020-blame-tree-lib.sh\n\ndiff --git a/Makefile b/Makefile\nindex 45bd6ac9c3e..ed82dfee8e7 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -786,6 +786,7 @@ PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))\n \n TEST_BUILTINS_OBJS += test-advise.o\n TEST_BUILTINS_OBJS += test-bitmap.o\n+TEST_BUILTINS_OBJS += test-blame-tree.o\n TEST_BUILTINS_OBJS += test-bloom.o\n TEST_BUILTINS_OBJS += test-bundle-uri.o\n TEST_BUILTINS_OBJS += test-cache-tree.o\n@@ -974,6 +975,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\ndiff --git a/blame-tree.c b/blame-tree.c\nnew file mode 100644\nindex 00000000000..dc739b23bff\n--- /dev/null\n+++ b/blame-tree.c\n@@ -0,0 +1,195 @@\n+#include \"cache.h\"\n+#include \"blame-tree.h\"\n+#include \"strvec.h\"\n+#include \"hash.h\"\n+#include \"commit.h\"\n+#include \"diffcore.h\"\n+#include \"diff.h\"\n+#include \"object.h\"\n+#include \"revision.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, void *data)\n+{\n+\tstruct blame_tree *bt = data;\n+\n+\tfor (size_t 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+\n+\t\toidcpy(&ent->oid, &p->two->oid);\n+\t\tstring_list_append(&bt->paths, p->two->path)->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(the_hash_algo->empty_tree, &obj->item->oid, \"\",\n+\t\t\t      &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 blame_tree *bt,\n+\t\t     const struct blame_tree_options *opts)\n+{\n+\tinit_revisions(&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, void *cbdata)\n+{\n+\tstruct blame_tree_callback_data *data = cbdata;\n+\n+\tfor (size_t 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(the_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 00000000000..fb4ba1004e7\n--- /dev/null\n+++ b/blame-tree.h\n@@ -0,0 +1,39 @@\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+#define BLAME_TREE_OPTIONS_INIT(...) { \\\n+\t.args = STRVEC_INIT, \\\n+\t__VA_ARGS__ \\\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+};\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 blame_tree *bt,\n+\t\t     const struct blame_tree_options *opts);\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/t/helper/test-blame-tree.c b/t/helper/test-blame-tree.c\nnew file mode 100644\nindex 00000000000..1ea5ff783af\n--- /dev/null\n+++ b/t/helper/test-blame-tree.c\n@@ -0,0 +1,62 @@\n+#include \"test-tool.h\"\n+#include \"blame-tree.h\"\n+#include \"quote.h\"\n+#include \"config.h\"\n+#include \"parse-options.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+\twrite_name_quoted(path, stdout, bt->rev.diffopt.line_termination);\n+\n+\tfflush(stdout);\n+}\n+\n+int cmd__blame_tree(int argc, const char **argv)\n+{\n+\tconst char *prefix = setup_git_directory();\n+\tstruct blame_tree_options opts = BLAME_TREE_OPTIONS_INIT(\n+\t\t.prefix = prefix,\n+\t\t.recursive = 1,\n+\t);\n+\tstruct blame_tree bt = BLAME_TREE_INIT;\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+\tstatic char const* const usage[] = {\n+\t\t\"test-tool blame-tree [--no-recursive] [-- <rev-opts>]\",\n+\t\tNULL\n+\t};\n+\n+\targc = parse_options(argc, argv, prefix, options, usage,\n+\t\t\t     PARSE_OPT_KEEP_DASHDASH);\n+\n+\tif (argc) {\n+\t\tif (strcmp(argv[0], \"--\") &&\n+\t\t    strcmp(argv[0], \"--end-of-options\"))\n+\t\t\tusage_msg_opt(\"need -- before <rev-opts>\", usage, options);\n+\t\targc--;\n+\t\targv++;\n+\t}\n+\n+\tif (repo_get_oid(the_repository, \"HEAD\", &opts.oid))\n+\t\t die(\"unable to get HEAD\");\n+\n+\tstrvec_push(&opts.args, \"blame-tree\");\n+\tif (argc)\n+\t\tstrvec_pushv(&opts.args, argv);\n+\tblame_tree_init(&bt, &opts);\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/t/helper/test-tool.c b/t/helper/test-tool.c\nindex abe8a785eb6..8f34ff18d6f 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -12,6 +12,7 @@ static const char * const test_tool_usage[] = {\n static struct test_cmd cmds[] = {\n \t{ \"advise\", cmd__advise_if_enabled },\n \t{ \"bitmap\", cmd__bitmap },\n+\t{ \"blame-tree\", cmd__blame_tree },\n \t{ \"bloom\", cmd__bloom },\n \t{ \"bundle-uri\", cmd__bundle_uri },\n \t{ \"cache-tree\", cmd__cache_tree },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex ea2672436c9..745a2097000 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/t8020-blame-tree-lib.sh b/t/t8020-blame-tree-lib.sh\nnew file mode 100755\nindex 00000000000..4213c25de8b\n--- /dev/null\n+++ b/t/t8020-blame-tree-lib.sh\n@@ -0,0 +1,138 @@\n+#!/bin/sh\n+\n+test_description='basic blame-tree library 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 test-tool 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+\ttest-tool ${indir:+-C \"$indir\"} \\\n+\t\tblame-tree \"$@\" >tmp.1 &&\n+\tgit name-rev --annotate-stdin --name-only --tags \\\n+\t\t<tmp.1 >tmp.2 &&\n+\ttr '\\t' ' ' <tmp.2 >tmp.3 &&\n+\tsort tmp.3 >actual &&\n+\ttest_cmp expect actual\n+}\n+\n+test_expect_success 'blame recursive' '\n+\tcheck_blame <<-\\EOF\n+\t1 file\n+\t2 a/file\n+\t3 a/b/file\n+\tEOF\n+'\n+\n+test_expect_success 'blame root' '\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+\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 -- b <<-\\EOF\n+\t3 a/b/file\n+\tEOF\n+'\n+\n+test_expect_success 'limit blame traversal by count' '\n+\tcheck_blame --no-recursive -- -1 <<-\\EOF\n+\t3 a\n+\t^2 file\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-- \n2.39.1.1398.g1368d6f56cf\n\n"},{"id":"471923","messageId":"4ab0b2b0-b045-2346-ccc1-19f9b23d0a02@github.com","threadId":"59203","inReplyTo":"patch-1.1-0ea849d900b-20230205T204104Z-avarab@gmail.com","subject":"Re: [PATCH] blame-tree: add library and tests via \"test-tool blame-tree\"","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-02-10T15:42:13Z","receivedAt":"2023-02-10T15:42:20Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/5/2023 3:47 PM, Ævar Arnfjörð Bjarmason wrote:\n\nI've been meaning to get to this all week, but today was my first chance.\n\n> The \"blame-tree\" library allows for finding the most recent\n> modification to paths in a tree. It does so by expanding the tree at a\n> given commit, taking note of the current state of each path, and then\n> walking backwards through history looking for commits where each path\n> changed into its final sha1.\n>\n> The \"git blame-tree\" command was first noted on the ML 2011[1], and\n> over the years there have been mentions of it[2][3], and whether it\n> could be upstreamed. The sources have been available at [4]'s\n> \"jk/blame-tree-wip\" and \"jk/faster-blame-tree-wip\" branches.\n>\n> This change attempts to start upstreaming this command, but rather\n> than adding a command whose interface & semantics may be controversial\n> starts by exposing & testing the core of its library through a new\n> test helper.\n\nOne thing that I think is important for this work and the future we build\non top of it is that we need to reconsider every fact about the existing\ncontribution and make sure the new thing is built for the actual needs.\n\nIn that vein, I think your use of a test-tool is a really good one. It can\nhelp us define an API boundary that could then be reflected in a CLI in\nindependent review from improved algorithms underneath the API.\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> +#define BLAME_TREE_OPTIONS_INIT(...) { \\\n> +\t.args = STRVEC_INIT, \\\n> +\t__VA_ARGS__ \\\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> +};\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 blame_tree *bt,\n> +\t\t     const struct blame_tree_options *opts);\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\nHowever, this API is too leaky. Specifically, it allows passing arbitrary\n'args' instead of structured options.\n\nBefore I get into what I think needs to change here, let's look at the\ninitial implementation:\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(the_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> +}\n\nWhen I think of 'blame-tree', I think of the following output:\n\n  For each path (within a pathspec, recursive or not), output the first\n  commit that changed that path according to simplified file history. This\n  history walk begins at a single commit, but may be terminated by a\n  negative commit range, so the output could indicate that we reached the\n  boundary.\n\nWith that definition, the most-obvious first implementation would be to\nfirst generate the path list, then run\n`git rev-list -n 1 <revisions> -- <path>` for each path in the pathspec.\nThis could be done by N prepare_revision_walk()/get_revision() executions\nwithin a loop instead of actually executing subcommands.\n\nThe implementation in this patch is simultaneously smarter than that basic\napproach, but also not smart enough for the best performance. In order to\nget the optimal performance, the following parts of my output definition\nare critical:\n\n 1. We use simplified file history.\n 2. The history walk begins at a single commit.\n\nIf either of these conditions are broken, then the current-best algorithm\ncannot be used (and even more: our proactive caching mechanism cannot be\nused).\n\nThe API as currently defined does not allow us to enforce that restriction\nbecause the arbitrary arguments could specify `--full-history`, or worse\n`--simplify-merge` (and also `--first-parent`) to modify the history mode\nor even `--all` to modify the number of starting commits.\n\nThe version we use in our custom fork has the historical baggage of this\nopen-ended argument-parsing, but because we have full control of the\ncallers to the CLI, we have enforced that those arguments are not being\nused. While we are not currently reviewing the CLI of a builtin, the API\nlayer is essentially providing a pass-through of arbitrary revision options.\n\nI am happy to see that the 'struct blame_tree_options' includes a callback\nfor the output, as that is valuable for both reporting results to stdout\nor to collect results into a list for caching purposes, in the future\nwhere we have that ability.\n\n--- Recommended API ---\n\nUsing 'struct blame_tree_options' instead of many parameters creates a\ngood future-proof method prototype, so we can always _add_ options when\nexplicitly understood as important to callers of one kind or another.\n\nHowever, to drop the arbitrary 'args' we need to instead make it very\nexplicit which commits are being used in the history walk.\n\nstruct blame_tree_options {\n\tstruct object_id oid;\n\tconst char *prefix;\n\tunsigned int recursive;\n\tstruct commit *start;\n\tstruct commit_list *uninteresting;\n};\n\nThis definition of the struct should be enough to demonstrate the behavior\nwe are describing. However, for the v1 of the API, we may even want to\ncompletely remove the 'uninteresting' choice, and instead focus only on a\nsingle starting position ('start'). If we decide that 'uninteresting' is\nvaluable, then it can be added again later, hopefully after the primary\nuse of this command is established.\n\nAgain, thinking about the lifetime of this command in our infrastructure,\nthe commit range behavior was used at one point as a performance improvement\nwhere a cache was given for a specific starting commit B, then we\ndynamically computed the blame-tree for the range B..A when given a new\ncommit A, and merged the two results together. However, this was not always\ncorrect due to complexities around parallel changes. A different caching\nmechanism was built into the low-level algorithm itself which resolves\nthese complications, but also _that cache cannot be used when given range\nqueries_.\n\nFurther, I recommend building the simplest implementation first, since it\nis actually closer to the very fast implementation in that it has two\nparts:\n\n 1. Compute the list of paths at the tip.\n 2. Perform history walks for those paths.\n\nThe fast implementation does a single history walk that essentially walks\nthe simplified history for all of the paths simultaneously, but it is\ncritical to have that list of paths at the start of that walk. In that way\nit's actually easier to adapt the simpler algorithm to the current-best\nalgorithm than it is to adapt the smart algorithm from this patch to the\ncurrent-best algorithm.\n\nAll this is to say, that I'd like to see this API start with the smallest\npossible surface area and with the simplest implementation, and then I'd\nbe happy to contribute those algorithms within the API boundary while the\nCLI is handled independently.\n\nThanks,\n-Stolee\n"},{"id":"472266","messageId":"Y+/mnnJUz75yfWCN@coredump.intra.peff.net","threadId":"59203","inReplyTo":"patch-1.1-0ea849d900b-20230205T204104Z-avarab@gmail.com","subject":"Re: [PATCH] blame-tree: add library and tests via \"test-tool blame-tree\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2023-02-17T20:42:06Z","receivedAt":"2023-02-17T20:42:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Feb 05, 2023 at 09:47:03PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> From: Jeff King <peff@peff.net>\n\nI appreciate being credited, of course, but at some point I think this\nbecomes \"Based-on-a-patch-by\". And we may have crossed the line here.\n\n> The \"blame-tree\" library allows for finding the most recent\n> modification to paths in a tree. It does so by expanding the tree at a\n> given commit, taking note of the current state of each path, and then\n> walking backwards through history looking for commits where each path\n> changed into its final sha1.\n> \n> The \"git blame-tree\" command was first noted on the ML 2011[1], and\n> over the years there have been mentions of it[2][3], and whether it\n> could be upstreamed. The sources have been available at [4]'s\n> \"jk/blame-tree-wip\" and \"jk/faster-blame-tree-wip\" branches.\n\nSort of. jk/blame-tree-wip probably matches what I sent to the list in\n2011 (and that probably matches what was deployed at GitHub at the\ntime). And like all of my branches, I continually rebase it on git.git's\nmaster branch. But like all branches in my repo with \"-wip\" in them, it\nis not part of my daily driver, and I generally do not even build it\n(and I would not be surprised if it does not build at all, or one of\nthose rebases introduced a horrible bug).\n\nThe jk/faster-blame-tree-wip was an experiment from 2014 to narrow the\npathspec as we found answers. But it was never deployed anywhere, and\nlikewise may or may not even build now. I think the general idea there\nis sound (make pathspec lookups faster by using a trie, and then narrow\nit), but I suspect it's not a full solution. In particular, I don't\nthink it does anything clever with merges. Since we are narrowing the\npathspec as we traverse, we can't rely on the usual pruning of side\nbranches that happens via limit_list(), as that is all up-front. So it\nprobably needs to look at each merge as we traverse and cull parents\nbased on TREESAME.\n\nI believe GitHub later had patches to do that, but they didn't use the\npathspec machinery (because without the tries, it becomes accidentally\nquadratic in the number of paths). I didn't work on those patches,\nthough (Stolee and Taylor did), and they're not anywhere in my\nrepository (and I no longer have access to the private github repo).\n\n> This change attempts to start upstreaming this command, but rather\n> than adding a command whose interface & semantics may be controversial\n> starts by exposing & testing the core of its library through a new\n> test helper.\n> \n> An eventual \"git blame-tree\" command, or e.g. a new format for \"git\n> ls-tree\" to show what a path \"blames\" to can then be implemented with\n> this library.\n\nOK. It's a little weird, as I do think the interface and semantics are\nthe more interesting part, but this certainly isn't hurting anybody to\ngo this route.\n\n> * Removing the \"--max-depth\" changes to the diff code. We'll need\n>   those eventually, but it's not required for a blame of a given list\n>   of paths.\n> \n>   As has been noted in previous on-list discussions the semantics of\n>   the \"max-depth\" changes might be controversial, so it's worthwhile\n>   to split those out so that they can be reviewed separately.\n\nThat's probably reasonable. The only two interesting \"depths\" are really\n\"recurse\" and \"don't recurse\" (where \"recurse\" is probably what you'd\nput in a user-facing tool, and \"don't recurse\" is what a site like\nGitHub uses to do the blame for a single level of tree it's showing).\nAnd that narrows the problem space quite a bit.\n\n> * Made the \"blame-tree\" helper take \"--\" before any revision options,\n>   for clarity. An eventual built-in command (if any) probably doesn't\n>   want to enforce this, but it makes it clearer in the test helper\n>   what's an argument for \"blame-tree\" itself, and what's an argument for\n>   the revision machinery.\n\nOK. Since this is just a test-helper, we don't care too much either way.\n\n> * Minor updates for using C99 syntax, and \"size_t\" instead of \"int\"\n>   when we're iterating over types whose \"nr\" is that size.\n\nReasonable.\n\n> * Avoid sub-shelling in the tests, use \"test-tool -C ..\" instead.\n\nYeah, the original code probably predates \"-C\". ;)\n\n> The range-diff here is to peff's jk/blame-tree-wip. As noted above\n> this is far from the full thing, but hopefully getting the basic bits\n> of the library (sans the max-depth question) will make the review of\n> subsequent bits easier.\n\nI doubt this range-diff is useful to anybody. I'm probably the person\nmost likely to make sense of it, and it means nothing to me. It probably\nmakes sense conceptually to just treat this as a new topic that happens\nto be based on older work.\n\nBut if you did want to base it on something, you probably ought to do so\non what GitHub is currently running in production (and again, talk to\nTaylor or Stolee for that). Unless the intent is to use this as a base\nfor showing their changes. Though even then, I'm not sure the\nintermediate state is all that interesting.\n\n> [oodles of patch]\n\nTBH, I didn't really look at this closely. It's been a decade, so even\nfor me reviewing this would basically be looking at it from scratch. And\nas my Git time is a bit limited these days, I can't really promise\ntimely review of a big topic.\n\n-Peff\n"},{"id":"473121","messageId":"230307.86o7p4zm4s.gmgdl@evledraar.gmail.com","threadId":"59203","inReplyTo":"4ab0b2b0-b045-2346-ccc1-19f9b23d0a02@github.com","subject":"Re: [PATCH] blame-tree: add library and tests via \"test-tool blame-tree\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2023-03-07T13:56:29Z","receivedAt":"2023-03-07T14:18:57Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Feb 10 2023, Derrick Stolee wrote:\n\n> On 2/5/2023 3:47 PM, Ævar Arnfjörð Bjarmason wrote:\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>> +#define BLAME_TREE_OPTIONS_INIT(...) { \\\n>> +\t.args = STRVEC_INIT, \\\n>> +\t__VA_ARGS__ \\\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>> +};\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 blame_tree *bt,\n>> +\t\t     const struct blame_tree_options *opts);\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> However, this API is too leaky. Specifically, it allows passing arbitrary\n> 'args' instead of structured options.\n>\n> Before I get into what I think needs to change here, let's look at the\n> initial implementation:\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(the_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>> +}\n>\n> When I think of 'blame-tree', I think of the following output:\n>\n>   For each path (within a pathspec, recursive or not), output the first\n>   commit that changed that path according to simplified file history. This\n>   history walk begins at a single commit, but may be terminated by a\n>   negative commit range, so the output could indicate that we reached the\n>   boundary.\n>\n> With that definition, the most-obvious first implementation would be to\n> first generate the path list, then run\n> `git rev-list -n 1 <revisions> -- <path>` for each path in the pathspec.\n> This could be done by N prepare_revision_walk()/get_revision() executions\n> within a loop instead of actually executing subcommands.\n>\n> The implementation in this patch is simultaneously smarter than that basic\n> approach, but also not smart enough for the best performance. In order to\n> get the optimal performance, the following parts of my output definition\n> are critical:\n>\n>  1. We use simplified file history.\n>  2. The history walk begins at a single commit.\n>\n> If either of these conditions are broken, then the current-best algorithm\n> cannot be used (and even more: our proactive caching mechanism cannot be\n> used).\n>\n> The API as currently defined does not allow us to enforce that restriction\n> because the arbitrary arguments could specify `--full-history`, or worse\n> `--simplify-merge` (and also `--first-parent`) to modify the history mode\n> or even `--all` to modify the number of starting commits.\n\nThere's already a limitation on --all in this patch, or anything else\nthat would yield a many<->many rev<->path relationship, e.g. \"--all\" or\n\"HEAD HEAD~\", that's covered by the \"can only blame one tree at a time\"\nerror condition.\n\nFor --full-history v.s. --simplify-merge the output on git.git at least\n(maybe not on others?) would be the same:\n\n\tdiff -u <(t/helper/test-tool -C \"$PWD/t\" blame-tree -- --full-history) <(t/helper/test-tool -C \"$PWD/t\" blame-tree -- --simplify-merge)\n\nBut of course for --first-parent it's not, but more on that below.\n\n> The version we use in our custom fork has the historical baggage of this\n> open-ended argument-parsing, but because we have full control of the\n> callers to the CLI, we have enforced that those arguments are not being\n> used. While we are not currently reviewing the CLI of a builtin, the API\n> layer is essentially providing a pass-through of arbitrary revision options.\n>\n> I am happy to see that the 'struct blame_tree_options' includes a callback\n> for the output, as that is valuable for both reporting results to stdout\n> or to collect results into a list for caching purposes, in the future\n> where we have that ability.\n>\n> --- Recommended API ---\n>\n> Using 'struct blame_tree_options' instead of many parameters creates a\n> good future-proof method prototype, so we can always _add_ options when\n> explicitly understood as important to callers of one kind or another.\n>\n> However, to drop the arbitrary 'args' we need to instead make it very\n> explicit which commits are being used in the history walk.\n>\n> struct blame_tree_options {\n> \tstruct object_id oid;\n> \tconst char *prefix;\n> \tunsigned int recursive;\n> \tstruct commit *start;\n> \tstruct commit_list *uninteresting;\n> };\n>\n> This definition of the struct should be enough to demonstrate the behavior\n> we are describing. However, for the v1 of the API, we may even want to\n> completely remove the 'uninteresting' choice, and instead focus only on a\n> single starting position ('start'). If we decide that 'uninteresting' is\n> valuable, then it can be added again later, hopefully after the primary\n> use of this command is established.\n>\n> Again, thinking about the lifetime of this command in our infrastructure,\n> the commit range behavior was used at one point as a performance improvement\n> where a cache was given for a specific starting commit B, then we\n> dynamically computed the blame-tree for the range B..A when given a new\n> commit A, and merged the two results together. However, this was not always\n> correct due to complexities around parallel changes. A different caching\n> mechanism was built into the low-level algorithm itself which resolves\n> these complications, but also _that cache cannot be used when given range\n> queries_.\n>\n> Further, I recommend building the simplest implementation first, since it\n> is actually closer to the very fast implementation in that it has two\n> parts:\n>\n>  1. Compute the list of paths at the tip.\n>  2. Perform history walks for those paths.\n>\n> The fast implementation does a single history walk that essentially walks\n> the simplified history for all of the paths simultaneously, but it is\n> critical to have that list of paths at the start of that walk. In that way\n> it's actually easier to adapt the simpler algorithm to the current-best\n> algorithm than it is to adapt the smart algorithm from this patch to the\n> current-best algorithm.\n>\n> All this is to say, that I'd like to see this API start with the smallest\n> possible surface area and with the simplest implementation, and then I'd\n> be happy to contribute those algorithms within the API boundary while the\n> CLI is handled independently.\n\nI hear your concern about leaving this open for optimization, and in\ngeneral I'd vehemently agree with it, except for needing to eventually\nfeed a command-line to setup_revisions().\n\nIdeally the revision API would make what you're describing easy, but the\nway it's currently implemented (and changing it would be a much larger\nproject) someone who'd like to pass structured options in the way you'd\ndescribe will end up having to re-implement bug-for-bug compatible\nversions of some subset of the option parsing in revision.c.\n\nIsn't a way to get the best of both worlds to have a small snippet of\ncode that inspects the \"struct rev_info\" before & after\nsetup_revisions(), and which would only implement certain optimizations\nif certain known options are provided, but not if any unknown ones are?\n\nThat way those who'd like the faster happy path could use that subset of\noptions, while the general API would allow any revision options. We'd\nthen error() or BUG() out only if we fail to map our expected paths to\nOIDs.\n\nSpecifically, I'm thinking of something similar to what\nmatch_stat_with_submodule() in diff-lib.c now does with \"orig_flags\".\n\nI also think as a practical matter it's acceptable for us to leave the\nunderlying low-level API open-ended for potential (ab)use, while any\nporcelain or plumbing tool for this would document that a given narrow\nsubset of revision options is what we expect.\n\nThat's what we do for format-patch, and e.g. as of my df569c3f31f\n(range-diff doc: add a section about output stability, 2018-11-09)\nrange-diff explicitly documents that feeding it options it won't expect\nmight result in nonsense output.\n\nI think those are all good ways forward here, and I'd much prefer those\nto having to re-implement or pull out subsets of the current option\nparsing logic in revision.c. What do you think?\n"},{"id":"473196","messageId":"d102dd22-778d-add6-faf9-20bf87d107c7@github.com","threadId":"59203","inReplyTo":"230307.86o7p4zm4s.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH] blame-tree: add library and tests via \"test-tool blame-tree\"","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-03-08T15:30:43Z","receivedAt":"2023-03-08T15:30:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/7/2023 8:56 AM, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Fri, Feb 10 2023, Derrick Stolee wrote:\n\n>> All this is to say, that I'd like to see this API start with the smallest\n>> possible surface area and with the simplest implementation, and then I'd\n>> be happy to contribute those algorithms within the API boundary while the\n>> CLI is handled independently.\n> \n> I hear your concern about leaving this open for optimization, and in\n> general I'd vehemently agree with it, except for needing to eventually\n> feed a command-line to setup_revisions().\n\nThe most-correct way to build this, with full optimizations, does not\ninvolve revisions.c at all, so this \"eventually\" is incorrect. It's\nonly something to do for the \"first\" implementation, as a reference.\n\nIn order to do the single-walk approach for every path simultaneously,\nwe _must_ have full control of the commit walk. There was a time where\nwe had done a single-walk approach by letting the revision machinery\nwalk all commits that changed the base tree, then looked for changes\nto the contained paths. However, this results in _incorrect_ results\nbecause commits that would normally be ignored by the simplified\nhistory walk for \"<dir>/<entry>\" were not ignored by the simplified\nhistory walk for \"<dir>/\" and thus that algorithm presented _incorrect\nresults_.\n\nFor that reason, doing a single walk that outputs the blame-tree\nresults for each path must have full control over which commits are\nwalked and which paths could emit a change for those commits. This\nmeans we must not use revision.c as a base for full control.\n\n> Ideally the revision API would make what you're describing easy, but the\n> way it's currently implemented (and changing it would be a much larger\n> project) someone who'd like to pass structured options in the way you'd\n> describe will end up having to re-implement bug-for-bug compatible\n> versions of some subset of the option parsing in revision.c.\n\nThe subset of option parsing is \"a starting revision\" and \"a base tree\"\nand _perhaps_ \"is the diff recursive or not?\" (and this last one isn't\neven in revision.c yet). That does not seem like using revision.c's\nparsing is actually helpful at all.\n\n> Isn't a way to get the best of both worlds to have a small snippet of\n> code that inspects the \"struct rev_info\" before & after\n> setup_revisions(), and which would only implement certain optimizations\n> if certain known options are provided, but not if any unknown ones are?\n> \n> That way those who'd like the faster happy path could use that subset of\n> options, while the general API would allow any revision options. We'd\n> then error() or BUG() out only if we fail to map our expected paths to\n> OIDs.\n \nThis option requires examining the long and ever-growing list of options\nto struct rev_info which will take much more work than parsing a starting\nref and a path from the command-line.\n\n> I think those are all good ways forward here, and I'd much prefer those\n> to having to re-implement or pull out subsets of the current option\n> parsing logic in revision.c. What do you think?\n\nI think you are skirting over the difficult part about upstreaming the\nblame-tree command, which is the biggest reason we have not done it in\nthe past. The way it is implemented in our fork started with this \"just\nparse args using revision.c\" because that's the easiest way to implement\nthe naive implementation, but we were able to make optimizations on top\nonly because we had full control over the callers not using any other\noptions. We would not have been able to make the assumptions that allowed\nthose performance enhancements without that control. Actually building the\ninterface in a way that guarantees the behavior will be stable and\nunderstood is not easy, but is worth doing well.\n\nThanks,\n-Stolee\n"},{"id":"473197","messageId":"ZAiuojxNifGo3n97@nand.local","threadId":"59203","inReplyTo":"230307.86o7p4zm4s.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH] blame-tree: add library and tests via \"test-tool blame-tree\"","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-03-08T15:49:54Z","receivedAt":"2023-03-08T15:50:12Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Mar 07, 2023 at 02:56:29PM +0100, Ævar Arnfjörð Bjarmason wrote:\n> I hear your concern about leaving this open for optimization, and in\n> general I'd vehemently agree with it, except for needing to eventually\n> feed a command-line to setup_revisions().\n>\n> Ideally the revision API would make what you're describing easy, but the\n> way it's currently implemented (and changing it would be a much larger\n> project) someone who'd like to pass structured options in the way you'd\n> describe will end up having to re-implement bug-for-bug compatible\n> versions of some subset of the option parsing in revision.c.\n\nI get what you are both saying here, but I think I find myself tending\nto agree with Ævar a little bit more here.\n\nIn an ideal world, sure, having the blame-tree API take a single struct\ncalled 'blame_tree_options' would be very clean. But the crux is that we\nhave to pass some arguments to setup_revisions(), and that our problems\nhere stem from the leakiness of *that* API, not this one.\n\nI ran into a similar problem when looking at rewriting the bitmap\ntraversal code a year or so ago (which is sadly still on my to-do list).\n\nWithout getting into the details, part of that work involved calling\nlimit_list() as a function of setup_revisions() to discover the\ntraversal boundary. And if the caller happened to put --topo-order in\ntheir command-line arguments, we wouldn't end up calling limit_list() at\nall, since (as Stolee well knows ;-)) those two code paths are quite\ndifferent.\n\nI can't recall if I either detected if '--topo-order' was passed (by\nlooking to see if `revs.topo_order` was set), or grafted an extra\n`--no-topo-order` argument onto the end of the list. Either way, I think\nthose two problems are more or less equivalent in this context, and that\nit seemed like a much more expedient solution to work around the\nfundamental leakiness of the setup_revision() API rather than refactor\nit.\n\n> Isn't a way to get the best of both worlds to have a small snippet of\n> code that inspects the \"struct rev_info\" before & after\n> setup_revisions(), and which would only implement certain optimizations\n> if certain known options are provided, but not if any unknown ones are?\n\nYeah, I think this is basically the same as my \"let's check if the caller\npassed `--topo-order` by checking the `revs.topo_order` bit\" above.\n\n> I think those are all good ways forward here, and I'd much prefer those\n> to having to re-implement or pull out subsets of the current option\n> parsing logic in revision.c. What do you think?\n\nSame :-).\n\nThanks,\nTaylor\n"}]}