{"thread":{"id":"62282","subject":"[PATCH 00/17] pack-objects: add --path-walk option for better deltas","startedAt":"2024-10-08T14:12:07Z","lastAt":"2024-10-31T21:07:53Z","messageCount":55,"participants":["Derrick Stolee via GitGitGadget","Taylor Blau","Derrick Stolee","Patrick Steinhardt","Jonathan Tan"],"isPatch":true,"patchVersion":1,"patchTotal":17},"messages":[{"id":"504426","messageId":"pull.1813.git.1728396723.gitgitgadget@gmail.com","threadId":"62282","inReplyTo":null,"subject":"[PATCH 00/17] pack-objects: add --path-walk option for better deltas","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-10-08T14:11:46Z","receivedAt":"2024-10-08T14:12:07Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This is a reviewable series introducing the path-walk API and its\napplication within the 'git pack-objects --path-walk' machinery. This API\nwas previously discussed in the path-walk RFC [1] and the patch series\naround the --full-name-hash option (branch ds/pack-name-hash-tweak) [2].\nThis series conflicts with ds/pack-name-hash-tweak, but that was on hold\nbecause it did not seem as critical based on community interest.\n\n[1]\nhttps://lore.kernel.org/git/pull.1786.git.1725935335.gitgitgadget@gmail.com\n\n[2]\nhttps://lore.kernel.org/git/pull.1785.git.1725890210.gitgitgadget@gmail.com\n\nThe primary motivation for this feature is its use to shrink the packfile\ncreated by 'git push' when there are many name-hash collisions. This need\nwas discovered in several Javascript repositories that use the beachball\ntool [3] to generate CHANGELOG.md and CHANGELOG.json files. When a batch of\nthese files are created at the same time and pushed to a release branch, the\n'git pack-objects' process has many collisions among these files and delta\nbases are selected poorly.\n\n[3] https://github.com/microsoft/beachball\n\nIn some cases, 'git push' is pushing 60-100 MB when the new path-walk\nalgorithm will identify better delta bases and pack the same objects into a\nthin pack less than 1 MB. This was the most extreme example we could find\nand is present in a private monorepo. However, the microsoft/fluentui repo\n[4] is a good example for demonstrating similar improvements. The patch\ndescriptions frequently refer to this repo and which commit should be\nchecked out to reproduce this behavior.\n\n[4] https://github.com/microsoft/fluentui\n\nThe path-walk API is a new way to walk objects. Traditionally, the revision\nAPI walks objects by visiting a commit, then visiting its root tree and\nrecursing through trees to visit reachable objects that were not previously\nvisited. The path-walk API visits objects in batches based on the path\nwalked from a root tree to that object. (Only the first discovered path is\nchosen; this avoids certain kinds of Git bombs.)\n\nThis has an immediate application to 'git pack-objects'.\n\nWhen using the traditional revision API to walk objects, each object is\nemitted with an associated path. Since this path may appear for many objects\nspread across the full list, a heuristic is used: the \"name-hash\" is stored\nfor that object instead of the full path name. This name-hash will group\nobjects at the same path together, but also has a form of \"locality\" to\ngroup likely-similar objects together. When there are few collisions in the\nname-hash function, this helps compress objects that appear at the same path\nas well as help compress objects across different paths that have similar\nsuffixes. When there are many versions of the same path, then finding delta\nbases across that family of objects is very important. When there are few\nversions of the same path, then finding cross-name delta bases is also\nimportant. The former is important for clones and repacks while the latter\nis important for shallow clones. They can both be important for pushes. In\nall cases, this approach is fraught when there are many name-hash collisions\nas the window size becomes a limiting factor for finding quality delta\nbases.\n\nWhen using the path-walk API to walk objects, we group objects by the same\npath from the start. We don't need to store the path name, since we have the\nobjects already in a group. We can compute deltas within that group and then\nuse the name-hash approach to resort the object list and look for\nopportunistic cross-path deltas. Thus, the path-walk approach allows finding\ndelta bases at least as good as the traditional revision API approach.\n(Caveat: if we assume delta reuse and the existing deltas were computed with\nthe revision API approach, then the path-walk API approach may result in\nslightly worse delta compression. The performance tests in this series use\n--no-reuse-delta for this reason.)\n\nOnce 'git pack-objects --path-walk' exists, we have a few ways to take\nadvantage of it in other places:\n\n * The new 'pack.usePathWalk' config option will assume the --path-walk\n option. This allows 'git push' to assume this value and get the effect we\n want. This is similar to the 'pack.useSparse' config option that uses a\n similar path-based walk to limit the set of boundary objects.\n\n * 'git repack' learns a '--path-walk' option to pass to its child 'git\n pack-objects' process. This is also implied by 'pack.usePathWalk' but\n allows for testing without modifying repository config.\n\nI'll repeat the following table of repacking results when using 'git repack\n-adf [--path-walk]' on a set of repositories with many name-hash collisions.\nOnly the microsoft/fluentui repository is publicly available for testing, so\nthe others are left as Repo B/C/D.\n\n| Repo | Standard Repack | With --path-walk |\n|----------|-----------------|------------------|\n| fluentui | 438 MB | 148 MB |\n| Repo B | 6,255 MB | 778 MB |\n| Repo C | 37,737 MB | 6,158 MB |\n| Repo D | 130,049 MB | 4,432 MB |\n\n\nWhile this series is replacing ds/pack-name-hash-tweak and its introduction\nof the --full-name-hash option, it is worth comparing that option to the\n--path-walk option.\n\n * The --full-name-hash option is a much smaller code change, as it drops\n into the existing uses of the name-hash function.\n\n * The --full-name-hash option is more likely to integrate with server-side\n features such as delta islands and reachability bitmaps due to not\n changing the object walk. It was already noted that the .bitmap files\n store name-hash values, so there is some compatibility required to\n integrate with bitmaps. The --path-walk option will be more difficult to\n integrate with those options (at least during a repack), but maybe is not\n impossible; the --path-walk option will not work when reading\n reachability bitmaps, since we are avoiding walking trees entirely.\n\n * The --full-name-hash option is good when there are many name-hash\n collisions and many versions of the paths with those collisions. When\n creating a shallow clone or certain kinds of pushes, the --full-name-hash\n option is much worse at finding cross-path delta bases since it loses the\n locality of the standard name-hash function. The --path-walk option\n includes a second pass of delta computation using the standard name-hash\n function and thus finds good cross-path delta bases when they improve\n upon the same-path delta bases.\n\nThere are a few differences from the RFC version of this series:\n\n 1. The last two patches refactor the approach to perform delta calculations\n by path after the object walk and then allows those delta calculations\n to happen in a threaded manner.\n\n 2. Both 'git pack-objects' and 'git repack' are removed from the t0450\n exclusion list.\n\n 3. The path-walk API has improved technical documentation that is extended\n as its functionality is expanded.\n\n 4. Various bugs have been patched with matching tests. The new 'test-tool\n path-walk' helper allows for careful testing of the API separately from\n its use within other commands.\n\nThanks, - Stolee\n\nDerrick Stolee (17):\n path-walk: introduce an object walk by path\n t6601: add helper for testing path-walk API\n path-walk: allow consumer to specify object types\n path-walk: allow visiting tags\n revision: create mark_trees_uninteresting_dense()\n path-walk: add prune_all_uninteresting option\n pack-objects: extract should_attempt_deltas()\n pack-objects: add --path-walk option\n pack-objects: update usage to match docs\n p5313: add performance tests for --path-walk\n pack-objects: introduce GIT_TEST_PACK_PATH_WALK\n repack: add --path-walk option\n repack: update usage to match docs\n pack-objects: enable --path-walk via config\n scalar: enable path-walk during push via config\n pack-objects: refactor path-walk delta phase\n pack-objects: thread the path-based compression\n\n Documentation/config/feature.txt | 4 +\n Documentation/config/pack.txt | 8 +\n Documentation/git-pack-objects.txt | 23 +-\n Documentation/git-repack.txt | 17 +-\n Documentation/technical/api-path-walk.txt | 73 ++++\n Makefile | 2 +\n builtin/pack-objects.c | 410 ++++++++++++++++++++--\n builtin/repack.c | 9 +-\n ci/run-build-and-tests.sh | 1 +\n pack-objects.h | 12 +\n path-walk.c | 404 +++++++++++++++++++++\n path-walk.h | 64 ++++\n repo-settings.c | 3 +\n repo-settings.h | 1 +\n revision.c | 15 +\n revision.h | 1 +\n scalar.c | 1 +\n t/README | 4 +\n t/helper/test-path-walk.c | 114 ++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n t/perf/p5313-pack-objects.sh | 77 ++++\n t/t0411-clone-from-partial.sh | 6 +\n t/t0450/txt-help-mismatches | 2 -\n t/t5300-pack-object.sh | 21 ++\n t/t5306-pack-nobase.sh | 5 +\n t/t5310-pack-bitmaps.sh | 13 +-\n t/t5316-pack-delta-depth.sh | 9 +-\n t/t5332-multi-pack-reuse.sh | 7 +\n t/t6601-path-walk.sh | 301 ++++++++++++++++\n t/t7406-submodule-update.sh | 4 +\n 31 files changed, 1563 insertions(+), 50 deletions(-)\n create mode 100644 Documentation/technical/api-path-walk.txt\n create mode 100644 path-walk.c\n create mode 100644 path-walk.h\n create mode 100644 t/helper/test-path-walk.c\n create mode 100755 t/perf/p5313-pack-objects.sh\n create mode 100755 t/t6601-path-walk.sh\n\n\nbase-commit: e9356ba3ea2a6754281ff7697b3e5a1697b21e24\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1813%2Fderrickstolee%2Fpath-walk-upstream-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1813/derrickstolee/path-walk-upstream-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1813\n-- \ngitgitgadget\n"},{"id":"504427","messageId":"98bdc94a773d797152bebfbfda88fa1bb0707821.1728396724.git.gitgitgadget@gmail.com","threadId":"62282","inReplyTo":"pull.1813.git.1728396723.gitgitgadget@gmail.com","subject":"[PATCH 01/17] path-walk: introduce an object walk by path","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-10-08T14:11:47Z","receivedAt":"2024-10-08T14:12:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn anticipation of a few planned applications, introduce the most basic form\nof a path-walk API. It currently assumes that there are no UNINTERESTING\nobjects and does not include any complicated filters. It calls a function\npointer on groups of tree and blob objects as grouped by path. This only\nincludes objects the first time they are discovered, so an object that\nappears at multiple paths will not be included in two batches.\n\nThere are many future adaptations that could be made, but they are left for\nfuture updates when consumers are ready to take advantage of those features.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/api-path-walk.txt | 54 +++++\n Makefile | 1 +\n path-walk.c | 241 ++++++++++++++++++++++\n path-walk.h | 43 ++++\n 4 files changed, 339 insertions(+)\n create mode 100644 Documentation/technical/api-path-walk.txt\n create mode 100644 path-walk.c\n create mode 100644 path-walk.h\n\ndiff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt\nnew file mode 100644\nindex 00000000000..6472222ae6d\n--- /dev/null\n+++ b/Documentation/technical/api-path-walk.txt\n@@ -0,0 +1,54 @@\n+Path-Walk API\n+=============\n+\n+The path-walk API is used to walk reachable objects, but to visit objects\n+in batches based on a common path they appear in, or by type.\n+\n+For example, all reachable commits are visited in a group. All tags are\n+visited in a group. Then, all root trees are visited. At some point, all\n+blobs reachable via a path `my/dir/to/A` are visited. When there are\n+multiple paths possible to reach the same object, then only one of those\n+paths is used to visit the object.\n+\n+When walking a range of commits with some `UNINTERESTING` objects, the\n+objects with the `UNINTERESTING` flag are included in these batches. In\n+order to walk `UNINTERESTING` objects, the `--boundary` option must be\n+used in the commit walk in order to visit `UNINTERESTING` commits.\n+\n+Basics\n+------\n+\n+To use the path-walk API, include `path-walk.h` and call\n+`walk_objects_by_path()` with a customized `path_walk_info` struct. The\n+struct is used to set all of the options for how the walk should proceed.\n+Let's dig into the different options and their use.\n+\n+`path_fn` and `path_fn_data`::\n+\tThe most important option is the `path_fn` option, which is a\n+\tfunction pointer to the callback that can execute logic on the\n+\tobject IDs for objects grouped by type and path. This function\n+\talso receives a `data` value that corresponds to the\n+\t`path_fn_data` member, for providing custom data structures to\n+\tthis callback function.\n+\n+`revs`::\n+\tTo configure the exact details of the reachable set of objects,\n+\tuse the `revs` member and initialize it using the revision\n+\tmachinery in `revision.h`. Initialize `revs` using calls such as\n+\t`setup_revisions()` or `parse_revision_opt()`. Do not call\n+\t`prepare_revision_walk()`, as that will be called within\n+\t`walk_objects_by_path()`.\n++\n+It is also important that you do not specify the `--objects` flag for the\n+`revs` struct. The revision walk should only be used to walk commits, and\n+the objects will be walked in a separate way based on those starting\n+commits.\n++\n+If you want the path-walk API to emit `UNINTERESTING` objects based on the\n+commit walk's boundary, be sure to set `revs.boundary` so the boundary\n+commits are emitted.\n+\n+Examples\n+--------\n+\n+See example usages in future changes.\ndiff --git a/Makefile b/Makefile\nindex 7344a7f7257..d0d8d6888e3 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1094,6 +1094,7 @@ LIB_OBJS += parse-options.o\n LIB_OBJS += patch-delta.o\n LIB_OBJS += patch-ids.o\n LIB_OBJS += path.o\n+LIB_OBJS += path-walk.o\n LIB_OBJS += pathspec.o\n LIB_OBJS += pkt-line.o\n LIB_OBJS += preload-index.o\ndiff --git a/path-walk.c b/path-walk.c\nnew file mode 100644\nindex 00000000000..66840187e28\n--- /dev/null\n+++ b/path-walk.c\n@@ -0,0 +1,241 @@\n+/*\n+ * path-walk.c: implementation for path-based walks of the object graph.\n+ */\n+#include \"git-compat-util.h\"\n+#include \"path-walk.h\"\n+#include \"blob.h\"\n+#include \"commit.h\"\n+#include \"dir.h\"\n+#include \"hashmap.h\"\n+#include \"hex.h\"\n+#include \"object.h\"\n+#include \"oid-array.h\"\n+#include \"revision.h\"\n+#include \"string-list.h\"\n+#include \"strmap.h\"\n+#include \"trace2.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n+\n+struct type_and_oid_list\n+{\n+\tenum object_type type;\n+\tstruct oid_array oids;\n+};\n+\n+#define TYPE_AND_OID_LIST_INIT { \\\n+\t.type = OBJ_NONE, \t \\\n+\t.oids = OID_ARRAY_INIT\t \\\n+}\n+\n+struct path_walk_context {\n+\t/**\n+\t * Repeats of data in 'struct path_walk_info' for\n+\t * access with fewer characters.\n+\t */\n+\tstruct repository *repo;\n+\tstruct rev_info *revs;\n+\tstruct path_walk_info *info;\n+\n+\t/**\n+\t * Map a path to a 'struct type_and_oid_list'\n+\t * containing the objects discovered at that\n+\t * path.\n+\t */\n+\tstruct strmap paths_to_lists;\n+\n+\t/**\n+\t * Store the current list of paths in a stack, to\n+\t * facilitate depth-first-search without recursion.\n+\t */\n+\tstruct string_list path_stack;\n+};\n+\n+static int add_children(struct path_walk_context *ctx,\n+\t\t\tconst char *base_path,\n+\t\t\tstruct object_id *oid)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct strbuf path = STRBUF_INIT;\n+\tsize_t base_len;\n+\tstruct tree *tree = lookup_tree(ctx->repo, oid);\n+\n+\tif (!tree) {\n+\t\terror(_(\"failed to walk children of tree %s: not found\"),\n+\t\t oid_to_hex(oid));\n+\t\treturn -1;\n+\t} else if (parse_tree_gently(tree, 1)) {\n+\t\tdie(\"bad tree object %s\", oid_to_hex(oid));\n+\t}\n+\n+\tstrbuf_addstr(&path, base_path);\n+\tbase_len = path.len;\n+\n+\tparse_tree(tree);\n+\tinit_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size);\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tstruct type_and_oid_list *list;\n+\t\tstruct object *o;\n+\t\t/* Not actually true, but we will ignore submodules later. */\n+\t\tenum object_type type = S_ISDIR(entry.mode) ? OBJ_TREE : OBJ_BLOB;\n+\n+\t\t/* Skip submodules. */\n+\t\tif (S_ISGITLINK(entry.mode))\n+\t\t\tcontinue;\n+\n+\t\tif (type == OBJ_TREE) {\n+\t\t\tstruct tree *child = lookup_tree(ctx->repo, &entry.oid);\n+\t\t\to = child ? &child->object : NULL;\n+\t\t} else if (type == OBJ_BLOB) {\n+\t\t\tstruct blob *child = lookup_blob(ctx->repo, &entry.oid);\n+\t\t\to = child ? &child->object : NULL;\n+\t\t} else {\n+\t\t\t/* Wrong type? */\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (!o) /* report error?*/\n+\t\t\tcontinue;\n+\n+\t\t/* Skip this object if already seen. */\n+\t\tif (o->flags & SEEN)\n+\t\t\tcontinue;\n+\t\to->flags |= SEEN;\n+\n+\t\tstrbuf_setlen(&path, base_len);\n+\t\tstrbuf_add(&path, entry.path, entry.pathlen);\n+\n+\t\t/*\n+\t\t * Trees will end with \"/\" for concatenation and distinction\n+\t\t * from blobs at the same path.\n+\t\t */\n+\t\tif (type == OBJ_TREE)\n+\t\t\tstrbuf_addch(&path, '/');\n+\n+\t\tif (!(list = strmap_get(&ctx->paths_to_lists, path.buf))) {\n+\t\t\tCALLOC_ARRAY(list, 1);\n+\t\t\tlist->type = type;\n+\t\t\tstrmap_put(&ctx->paths_to_lists, path.buf, list);\n+\t\t\tstring_list_append(&ctx->path_stack, path.buf);\n+\t\t}\n+\t\toid_array_append(&list->oids, &entry.oid);\n+\t}\n+\n+\tfree_tree_buffer(tree);\n+\tstrbuf_release(&path);\n+\treturn 0;\n+}\n+\n+/*\n+ * For each path in paths_to_explore, walk the trees another level\n+ * and add any found blobs to the batch (but only if they exist and\n+ * haven't been added yet).\n+ */\n+static int walk_path(struct path_walk_context *ctx,\n+\t\t const char *path)\n+{\n+\tstruct type_and_oid_list *list;\n+\tint ret = 0;\n+\n+\tlist = strmap_get(&ctx->paths_to_lists, path);\n+\n+\t/* Evaluate function pointer on this data. */\n+\tret = ctx->info->path_fn(path, &list->oids, list->type,\n+\t\t\t\t ctx->info->path_fn_data);\n+\n+\t/* Expand data for children. */\n+\tif (list->type == OBJ_TREE) {\n+\t\tfor (size_t i = 0; i < list->oids.nr; i++) {\n+\t\t\tret |= add_children(ctx,\n+\t\t\t\t\t path,\n+\t\t\t\t\t &list->oids.oid[i]);\n+\t\t}\n+\t}\n+\n+\toid_array_clear(&list->oids);\n+\tstrmap_remove(&ctx->paths_to_lists, path, 1);\n+\treturn ret;\n+}\n+\n+static void clear_strmap(struct strmap *map)\n+{\n+\tstruct hashmap_iter iter;\n+\tstruct strmap_entry *e;\n+\n+\thashmap_for_each_entry(&map->map, &iter, e, ent) {\n+\t\tstruct type_and_oid_list *list = e->value;\n+\t\toid_array_clear(&list->oids);\n+\t}\n+\tstrmap_clear(map, 1);\n+\tstrmap_init(map);\n+}\n+\n+/**\n+ * Given the configuration of 'info', walk the commits based on 'info->revs' and\n+ * call 'info->path_fn' on each discovered path.\n+ *\n+ * Returns nonzero on an error.\n+ */\n+int walk_objects_by_path(struct path_walk_info *info)\n+{\n+\tconst char *root_path = \"\";\n+\tint ret = 0;\n+\tsize_t commits_nr = 0, paths_nr = 0;\n+\tstruct commit *c;\n+\tstruct type_and_oid_list *root_tree_list;\n+\tstruct path_walk_context ctx = {\n+\t\t.repo = info->revs->repo,\n+\t\t.revs = info->revs,\n+\t\t.info = info,\n+\t\t.path_stack = STRING_LIST_INIT_DUP,\n+\t\t.paths_to_lists = STRMAP_INIT\n+\t};\n+\n+\ttrace2_region_enter(\"path-walk\", \"commit-walk\", info->revs->repo);\n+\n+\t/* Insert a single list for the root tree into the paths. */\n+\tCALLOC_ARRAY(root_tree_list, 1);\n+\troot_tree_list->type = OBJ_TREE;\n+\tstrmap_put(&ctx.paths_to_lists, root_path, root_tree_list);\n+\n+\tif (prepare_revision_walk(info->revs))\n+\t\tdie(_(\"failed to setup revision walk\"));\n+\n+\twhile ((c = get_revision(info->revs))) {\n+\t\tstruct object_id *oid = get_commit_tree_oid(c);\n+\t\tstruct tree *t = lookup_tree(info->revs->repo, oid);\n+\t\tcommits_nr++;\n+\n+\t\tif (t) {\n+\t\t\tif (t->object.flags & SEEN)\n+\t\t\t\tcontinue;\n+\t\t\tt->object.flags |= SEEN;\n+\t\t\toid_array_append(&root_tree_list->oids, oid);\n+\t\t} else {\n+\t\t\twarning(\"could not find tree %s\", oid_to_hex(oid));\n+\t\t}\n+\t}\n+\n+\ttrace2_data_intmax(\"path-walk\", ctx.repo, \"commits\", commits_nr);\n+\ttrace2_region_leave(\"path-walk\", \"commit-walk\", info->revs->repo);\n+\n+\tstring_list_append(&ctx.path_stack, root_path);\n+\n+\ttrace2_region_enter(\"path-walk\", \"path-walk\", info->revs->repo);\n+\twhile (!ret && ctx.path_stack.nr) {\n+\t\tchar *path = ctx.path_stack.items[ctx.path_stack.nr - 1].string;\n+\t\tctx.path_stack.nr--;\n+\t\tpaths_nr++;\n+\n+\t\tret = walk_path(&ctx, path);\n+\n+\t\tfree(path);\n+\t}\n+\ttrace2_data_intmax(\"path-walk\", ctx.repo, \"paths\", paths_nr);\n+\ttrace2_region_leave(\"path-walk\", \"path-walk\", info->revs->repo);\n+\n+\tclear_strmap(&ctx.paths_to_lists);\n+\tstring_list_clear(&ctx.path_stack, 0);\n+\treturn ret;\n+}\ndiff --git a/path-walk.h b/path-walk.h\nnew file mode 100644\nindex 00000000000..c9e94a98bc8\n--- /dev/null\n+++ b/path-walk.h\n@@ -0,0 +1,43 @@\n+/*\n+ * path-walk.h : Methods and structures for walking the object graph in batches\n+ * by the paths that can reach those objects.\n+ */\n+#include \"object.h\" /* Required for 'enum object_type'. */\n+\n+struct rev_info;\n+struct oid_array;\n+\n+/**\n+ * The type of a function pointer for the method that is called on a list of\n+ * objects reachable at a given path.\n+ */\n+typedef int (*path_fn)(const char *path,\n+\t\t struct oid_array *oids,\n+\t\t enum object_type type,\n+\t\t void *data);\n+\n+struct path_walk_info {\n+\t/**\n+\t * revs provides the definitions for the commit walk, including\n+\t * which commits are UNINTERESTING or not.\n+\t */\n+\tstruct rev_info *revs;\n+\n+\t/**\n+\t * The caller wishes to execute custom logic on objects reachable at a\n+\t * given path. Every reachable object will be visited exactly once, and\n+\t * the first path to see an object wins. This may not be a stable choice.\n+\t */\n+\tpath_fn path_fn;\n+\tvoid *path_fn_data;\n+};\n+\n+#define PATH_WALK_INFO_INIT { 0 }\n+\n+/**\n+ * Given the configuration of 'info', walk the commits based on 'info->revs' and\n+ * call 'info->path_fn' on each discovered path.\n+ *\n+ * Returns nonzero on an error.\n+ */\n+int walk_objects_by_path(struct path_walk_info *info);\n-- \ngitgitgadget\n\n"},{"id":"504428","messageId":"a00ab0c62c9f9c495981d9e565fdd10303ebe079.1728396724.git.gitgitgadget@gmail.com","threadId":"62282","inReplyTo":"pull.1813.git.1728396723.gitgitgadget@gmail.com","subject":"[PATCH 02/17] t6601: add helper for testing path-walk API","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-10-08T14:11:48Z","receivedAt":"2024-10-08T14:12:09Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAdd some tests based on the current behavior, doing interesting checks\nfor different sets of branches, ranges, and the --boundary option. This\nsets a baseline for the behavior and we can extend it as new options are\nintroduced.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/api-path-walk.txt | 3 +-\n Makefile | 1 +\n t/helper/test-path-walk.c | 86 ++++++++++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n t/t6601-path-walk.sh | 130 ++++++++++++++++++++++\n 6 files changed, 221 insertions(+), 1 deletion(-)\n create mode 100644 t/helper/test-path-walk.c\n create mode 100755 t/t6601-path-walk.sh\n\ndiff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt\nindex 6472222ae6d..e588897ab8d 100644\n--- a/Documentation/technical/api-path-walk.txt\n+++ b/Documentation/technical/api-path-walk.txt\n@@ -51,4 +51,5 @@ commits are emitted.\n Examples\n --------\n \n-See example usages in future changes.\n+See example usages in:\n+\t`t/helper/test-path-walk.c`\ndiff --git a/Makefile b/Makefile\nindex d0d8d6888e3..50413d96492 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -818,6 +818,7 @@ TEST_BUILTINS_OBJS += test-parse-options.o\n 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-pcre2-config.o\n TEST_BUILTINS_OBJS += test-pkt-line.o\n TEST_BUILTINS_OBJS += test-proc-receive.o\ndiff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c\nnew file mode 100644\nindex 00000000000..3c48f017fa0\n--- /dev/null\n+++ b/t/helper/test-path-walk.c\n@@ -0,0 +1,86 @@\n+#define USE_THE_REPOSITORY_VARIABLE\n+\n+#include \"test-tool.h\"\n+#include \"environment.h\"\n+#include \"hex.h\"\n+#include \"object-name.h\"\n+#include \"object.h\"\n+#include \"pretty.h\"\n+#include \"revision.h\"\n+#include \"setup.h\"\n+#include \"parse-options.h\"\n+#include \"path-walk.h\"\n+#include \"oid-array.h\"\n+\n+static const char * const path_walk_usage[] = {\n+\tN_(\"test-tool path-walk -- \"),\n+\tNULL\n+};\n+\n+struct path_walk_test_data {\n+\tuintmax_t tree_nr;\n+\tuintmax_t blob_nr;\n+};\n+\n+static int emit_block(const char *path, struct oid_array *oids,\n+\t\t enum object_type type, void *data)\n+{\n+\tstruct path_walk_test_data *tdata = data;\n+\tconst char *typestr;\n+\n+\tswitch (type) {\n+\tcase OBJ_TREE:\n+\t\ttypestr = \"TREE\";\n+\t\ttdata->tree_nr += oids->nr;\n+\t\tbreak;\n+\n+\tcase OBJ_BLOB:\n+\t\ttypestr = \"BLOB\";\n+\t\ttdata->blob_nr += oids->nr;\n+\t\tbreak;\n+\n+\tdefault:\n+\t\tBUG(\"we do not understand this type\");\n+\t}\n+\n+\tfor (size_t i = 0; i < oids->nr; i++)\n+\t\tprintf(\"%s:%s:%s\\n\", typestr, path, oid_to_hex(&oids->oid[i]));\n+\n+\treturn 0;\n+}\n+\n+int cmd__path_walk(int argc, const char **argv)\n+{\n+\tint res;\n+\tstruct rev_info revs = REV_INFO_INIT;\n+\tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n+\tstruct path_walk_test_data data = { 0 };\n+\tstruct option options[] = {\n+\t\tOPT_END(),\n+\t};\n+\n+\tinitialize_repository(the_repository);\n+\tsetup_git_directory();\n+\trevs.repo = the_repository;\n+\n+\targc = parse_options(argc, argv, NULL,\n+\t\t\t options, path_walk_usage,\n+\t\t\t PARSE_OPT_KEEP_UNKNOWN_OPT | PARSE_OPT_KEEP_ARGV0);\n+\n+\tif (argc > 1)\n+\t\tsetup_revisions(argc, argv, &revs, NULL);\n+\telse\n+\t\tusage(path_walk_usage[0]);\n+\n+\tinfo.revs = &revs;\n+\tinfo.path_fn = emit_block;\n+\tinfo.path_fn_data = &data;\n+\n+\tres = walk_objects_by_path(&info);\n+\n+\tprintf(\"trees:%\" PRIuMAX \"\\n\"\n+\t \"blobs:%\" PRIuMAX \"\\n\",\n+\t data.tree_nr, data.blob_nr);\n+\n+\treturn res;\n+}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex 1ebb69a5dc4..43676e7b93a 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -52,6 +52,7 @@ static struct test_cmd cmds[] = {\n \t{ \"parse-subcommand\", cmd__parse_subcommand },\n \t{ \"partial-clone\", cmd__partial_clone },\n \t{ \"path-utils\", cmd__path_utils },\n+\t{ \"path-walk\", cmd__path_walk },\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 21802ac27da..9cfc5da6e57 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -45,6 +45,7 @@ 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__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);\n int cmd__pkt_line(int argc, const char **argv);\n int cmd__proc_receive(int argc, const char **argv);\ndiff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh\nnew file mode 100755\nindex 00000000000..ca18b61c3f1\n--- /dev/null\n+++ b/t/t6601-path-walk.sh\n@@ -0,0 +1,130 @@\n+#!/bin/sh\n+\n+test_description='direct path-walk API tests'\n+\n+. ./test-lib.sh\n+\n+test_expect_success 'setup test repository' '\n+\tgit checkout -b base &&\n+\n+\tmkdir left &&\n+\tmkdir right &&\n+\techo a >a &&\n+\techo b >left/b &&\n+\techo c >right/c &&\n+\tgit add . &&\n+\tgit commit -m \"first\" &&\n+\n+\techo d >right/d &&\n+\tgit add right &&\n+\tgit commit -m \"second\" &&\n+\n+\techo bb >left/b &&\n+\tgit commit -a -m \"third\" &&\n+\n+\tgit checkout -b topic HEAD~1 &&\n+\techo cc >right/c &&\n+\tgit commit -a -m \"topic\"\n+'\n+\n+test_expect_success 'all' '\n+\ttest-tool path-walk -- --all >out &&\n+\n+\tcat >expect <<-EOF &&\n+\tTREE::$(git rev-parse topic^{tree})\n+\tTREE::$(git rev-parse base^{tree})\n+\tTREE::$(git rev-parse base~1^{tree})\n+\tTREE::$(git rev-parse base~2^{tree})\n+\tTREE:left/:$(git rev-parse base:left)\n+\tTREE:left/:$(git rev-parse base~2:left)\n+\tTREE:right/:$(git rev-parse topic:right)\n+\tTREE:right/:$(git rev-parse base~1:right)\n+\tTREE:right/:$(git rev-parse base~2:right)\n+\ttrees:9\n+\tBLOB:a:$(git rev-parse base~2:a)\n+\tBLOB:left/b:$(git rev-parse base~2:left/b)\n+\tBLOB:left/b:$(git rev-parse base:left/b)\n+\tBLOB:right/c:$(git rev-parse base~2:right/c)\n+\tBLOB:right/c:$(git rev-parse topic:right/c)\n+\tBLOB:right/d:$(git rev-parse base~1:right/d)\n+\tblobs:6\n+\tEOF\n+\n+\tsort expect >expect.sorted &&\n+\tsort out >out.sorted &&\n+\n+\ttest_cmp expect.sorted out.sorted\n+'\n+\n+test_expect_success 'topic only' '\n+\ttest-tool path-walk -- topic >out &&\n+\n+\tcat >expect <<-EOF &&\n+\tTREE::$(git rev-parse topic^{tree})\n+\tTREE::$(git rev-parse base~1^{tree})\n+\tTREE::$(git rev-parse base~2^{tree})\n+\tTREE:left/:$(git rev-parse base~2:left)\n+\tTREE:right/:$(git rev-parse topic:right)\n+\tTREE:right/:$(git rev-parse base~1:right)\n+\tTREE:right/:$(git rev-parse base~2:right)\n+\ttrees:7\n+\tBLOB:a:$(git rev-parse base~2:a)\n+\tBLOB:left/b:$(git rev-parse base~2:left/b)\n+\tBLOB:right/c:$(git rev-parse base~2:right/c)\n+\tBLOB:right/c:$(git rev-parse topic:right/c)\n+\tBLOB:right/d:$(git rev-parse base~1:right/d)\n+\tblobs:5\n+\tEOF\n+\n+\tsort expect >expect.sorted &&\n+\tsort out >out.sorted &&\n+\n+\ttest_cmp expect.sorted out.sorted\n+'\n+\n+test_expect_success 'topic, not base' '\n+\ttest-tool path-walk -- topic --not base >out &&\n+\n+\tcat >expect <<-EOF &&\n+\tTREE::$(git rev-parse topic^{tree})\n+\tTREE:left/:$(git rev-parse topic:left)\n+\tTREE:right/:$(git rev-parse topic:right)\n+\ttrees:3\n+\tBLOB:a:$(git rev-parse topic:a)\n+\tBLOB:left/b:$(git rev-parse topic:left/b)\n+\tBLOB:right/c:$(git rev-parse topic:right/c)\n+\tBLOB:right/d:$(git rev-parse topic:right/d)\n+\tblobs:4\n+\tEOF\n+\n+\tsort expect >expect.sorted &&\n+\tsort out >out.sorted &&\n+\n+\ttest_cmp expect.sorted out.sorted\n+'\n+\n+test_expect_success 'topic, not base, boundary' '\n+\ttest-tool path-walk -- --boundary topic --not base >out &&\n+\n+\tcat >expect <<-EOF &&\n+\tTREE::$(git rev-parse topic^{tree})\n+\tTREE::$(git rev-parse base~1^{tree})\n+\tTREE:left/:$(git rev-parse base~1:left)\n+\tTREE:right/:$(git rev-parse topic:right)\n+\tTREE:right/:$(git rev-parse base~1:right)\n+\ttrees:5\n+\tBLOB:a:$(git rev-parse base~1:a)\n+\tBLOB:left/b:$(git rev-parse base~1:left/b)\n+\tBLOB:right/c:$(git rev-parse base~1:right/c)\n+\tBLOB:right/c:$(git rev-parse topic:right/c)\n+\tBLOB:right/d:$(git rev-parse base~1:right/d)\n+\tblobs:5\n+\tEOF\n+\n+\tsort expect >expect.sorted &&\n+\tsort out >out.sorted &&\n+\n+\ttest_cmp expect.sorted out.sorted\n+'\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"504429","messageId":"14375d19392c406d903f6cb26be5a39c4c2ff1e9.1728396724.git.gitgitgadget@gmail.com","threadId":"62282","inReplyTo":"pull.1813.git.1728396723.gitgitgadget@gmail.com","subject":"[PATCH 03/17] path-walk: allow consumer to specify object types","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-10-08T14:11:49Z","receivedAt":"2024-10-08T14:12:10Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWe add the ability to filter the object types in the path-walk API so\nthe callback function is called fewer times.\n\nThis adds the ability to ask for the commits in a list, as well. Future\nchanges will add the ability to visit annotated tags.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/api-path-walk.txt | 9 +++\n path-walk.c | 39 ++++++++++--\n path-walk.h | 13 +++-\n t/helper/test-path-walk.c | 17 +++++-\n t/t6601-path-walk.sh | 72 +++++++++++++++++++++++\n 5 files changed, 141 insertions(+), 9 deletions(-)\n\ndiff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt\nindex e588897ab8d..b7ae476ea0a 100644\n--- a/Documentation/technical/api-path-walk.txt\n+++ b/Documentation/technical/api-path-walk.txt\n@@ -48,6 +48,15 @@ If you want the path-walk API to emit `UNINTERESTING` objects based on the\n commit walk's boundary, be sure to set `revs.boundary` so the boundary\n commits are emitted.\n \n+`commits`, `blobs`, `trees`::\n+\tBy default, these members are enabled and signal that the path-walk\n+\tAPI should call the `path_fn` on objects of these types. Specialized\n+\tapplications could disable some options to make it simpler to walk\n+\tthe objects or to have fewer calls to `path_fn`.\n++\n+While it is possible to walk only commits in this way, consumers would be\n+better off using the revision walk API instead.\n+\n Examples\n --------\n \ndiff --git a/path-walk.c b/path-walk.c\nindex 66840187e28..22e1aa13f31 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -84,6 +84,10 @@ static int add_children(struct path_walk_context *ctx,\n \t\tif (S_ISGITLINK(entry.mode))\n \t\t\tcontinue;\n \n+\t\t/* If the caller doesn't want blobs, then don't bother. */\n+\t\tif (!ctx->info->blobs && type == OBJ_BLOB)\n+\t\t\tcontinue;\n+\n \t\tif (type == OBJ_TREE) {\n \t\t\tstruct tree *child = lookup_tree(ctx->repo, &entry.oid);\n \t\t\to = child ? &child->object : NULL;\n@@ -140,9 +144,11 @@ static int walk_path(struct path_walk_context *ctx,\n \n \tlist = strmap_get(&ctx->paths_to_lists, path);\n \n-\t/* Evaluate function pointer on this data. */\n-\tret = ctx->info->path_fn(path, &list->oids, list->type,\n-\t\t\t\t ctx->info->path_fn_data);\n+\t/* Evaluate function pointer on this data, if requested. */\n+\tif ((list->type == OBJ_TREE && ctx->info->trees) ||\n+\t (list->type == OBJ_BLOB && ctx->info->blobs))\n+\t\tret = ctx->info->path_fn(path, &list->oids, list->type,\n+\t\t\t\t\tctx->info->path_fn_data);\n \n \t/* Expand data for children. */\n \tif (list->type == OBJ_TREE) {\n@@ -184,6 +190,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tsize_t commits_nr = 0, paths_nr = 0;\n \tstruct commit *c;\n \tstruct type_and_oid_list *root_tree_list;\n+\tstruct type_and_oid_list *commit_list;\n \tstruct path_walk_context ctx = {\n \t\t.repo = info->revs->repo,\n \t\t.revs = info->revs,\n@@ -194,19 +201,32 @@ int walk_objects_by_path(struct path_walk_info *info)\n \n \ttrace2_region_enter(\"path-walk\", \"commit-walk\", info->revs->repo);\n \n+\tCALLOC_ARRAY(commit_list, 1);\n+\tcommit_list->type = OBJ_COMMIT;\n+\n \t/* Insert a single list for the root tree into the paths. */\n \tCALLOC_ARRAY(root_tree_list, 1);\n \troot_tree_list->type = OBJ_TREE;\n \tstrmap_put(&ctx.paths_to_lists, root_path, root_tree_list);\n-\n \tif (prepare_revision_walk(info->revs))\n \t\tdie(_(\"failed to setup revision walk\"));\n \n \twhile ((c = get_revision(info->revs))) {\n-\t\tstruct object_id *oid = get_commit_tree_oid(c);\n-\t\tstruct tree *t = lookup_tree(info->revs->repo, oid);\n+\t\tstruct object_id *oid;\n+\t\tstruct tree *t;\n \t\tcommits_nr++;\n \n+\t\tif (info->commits)\n+\t\t\toid_array_append(&commit_list->oids,\n+\t\t\t\t\t &c->object.oid);\n+\n+\t\t/* If we only care about commits, then skip trees. */\n+\t\tif (!info->trees && !info->blobs)\n+\t\t\tcontinue;\n+\n+\t\toid = get_commit_tree_oid(c);\n+\t\tt = lookup_tree(info->revs->repo, oid);\n+\n \t\tif (t) {\n \t\t\tif (t->object.flags & SEEN)\n \t\t\t\tcontinue;\n@@ -220,6 +240,13 @@ int walk_objects_by_path(struct path_walk_info *info)\n \ttrace2_data_intmax(\"path-walk\", ctx.repo, \"commits\", commits_nr);\n \ttrace2_region_leave(\"path-walk\", \"commit-walk\", info->revs->repo);\n \n+\t/* Track all commits. */\n+\tif (info->commits)\n+\t\tret = info->path_fn(\"\", &commit_list->oids, OBJ_COMMIT,\n+\t\t\t\t info->path_fn_data);\n+\toid_array_clear(&commit_list->oids);\n+\tfree(commit_list);\n+\n \tstring_list_append(&ctx.path_stack, root_path);\n \n \ttrace2_region_enter(\"path-walk\", \"path-walk\", info->revs->repo);\ndiff --git a/path-walk.h b/path-walk.h\nindex c9e94a98bc8..6ef372d8942 100644\n--- a/path-walk.h\n+++ b/path-walk.h\n@@ -30,9 +30,20 @@ struct path_walk_info {\n \t */\n \tpath_fn path_fn;\n \tvoid *path_fn_data;\n+\t/**\n+\t * Initialize which object types the path_fn should be called on. This\n+\t * could also limit the walk to skip blobs if not set.\n+\t */\n+\tint commits;\n+\tint trees;\n+\tint blobs;\n };\n \n-#define PATH_WALK_INFO_INIT { 0 }\n+#define PATH_WALK_INFO_INIT { \\\n+\t.blobs = 1,\t\t\\\n+\t.trees = 1,\t\t\\\n+\t.commits = 1,\t\t\\\n+}\n \n /**\n * Given the configuration of 'info', walk the commits based on 'info->revs' and\ndiff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c\nindex 3c48f017fa0..37c5e3e31e8 100644\n--- a/t/helper/test-path-walk.c\n+++ b/t/helper/test-path-walk.c\n@@ -18,6 +18,7 @@ static const char * const path_walk_usage[] = {\n };\n \n struct path_walk_test_data {\n+\tuintmax_t commit_nr;\n \tuintmax_t tree_nr;\n \tuintmax_t blob_nr;\n };\n@@ -29,6 +30,11 @@ static int emit_block(const char *path, struct oid_array *oids,\n \tconst char *typestr;\n \n \tswitch (type) {\n+\tcase OBJ_COMMIT:\n+\t\ttypestr = \"COMMIT\";\n+\t\ttdata->commit_nr += oids->nr;\n+\t\tbreak;\n+\n \tcase OBJ_TREE:\n \t\ttypestr = \"TREE\";\n \t\ttdata->tree_nr += oids->nr;\n@@ -56,6 +62,12 @@ int cmd__path_walk(int argc, const char **argv)\n \tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n \tstruct path_walk_test_data data = { 0 };\n \tstruct option options[] = {\n+\t\tOPT_BOOL(0, \"blobs\", &info.blobs,\n+\t\t\t N_(\"toggle inclusion of blob objects\")),\n+\t\tOPT_BOOL(0, \"commits\", &info.commits,\n+\t\t\t N_(\"toggle inclusion of commit objects\")),\n+\t\tOPT_BOOL(0, \"trees\", &info.trees,\n+\t\t\t N_(\"toggle inclusion of tree objects\")),\n \t\tOPT_END(),\n \t};\n \n@@ -78,9 +90,10 @@ int cmd__path_walk(int argc, const char **argv)\n \n \tres = walk_objects_by_path(&info);\n \n-\tprintf(\"trees:%\" PRIuMAX \"\\n\"\n+\tprintf(\"commits:%\" PRIuMAX \"\\n\"\n+\t \"trees:%\" PRIuMAX \"\\n\"\n \t \"blobs:%\" PRIuMAX \"\\n\",\n-\t data.tree_nr, data.blob_nr);\n+\t data.commit_nr, data.tree_nr, data.blob_nr);\n \n \treturn res;\n }\ndiff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh\nindex ca18b61c3f1..e4788664f93 100755\n--- a/t/t6601-path-walk.sh\n+++ b/t/t6601-path-walk.sh\n@@ -31,6 +31,11 @@ test_expect_success 'all' '\n \ttest-tool path-walk -- --all >out &&\n \n \tcat >expect <<-EOF &&\n+\tCOMMIT::$(git rev-parse topic)\n+\tCOMMIT::$(git rev-parse base)\n+\tCOMMIT::$(git rev-parse base~1)\n+\tCOMMIT::$(git rev-parse base~2)\n+\tcommits:4\n \tTREE::$(git rev-parse topic^{tree})\n \tTREE::$(git rev-parse base^{tree})\n \tTREE::$(git rev-parse base~1^{tree})\n@@ -60,6 +65,10 @@ test_expect_success 'topic only' '\n \ttest-tool path-walk -- topic >out &&\n \n \tcat >expect <<-EOF &&\n+\tCOMMIT::$(git rev-parse topic)\n+\tCOMMIT::$(git rev-parse base~1)\n+\tCOMMIT::$(git rev-parse base~2)\n+\tcommits:3\n \tTREE::$(git rev-parse topic^{tree})\n \tTREE::$(git rev-parse base~1^{tree})\n \tTREE::$(git rev-parse base~2^{tree})\n@@ -86,6 +95,8 @@ test_expect_success 'topic, not base' '\n \ttest-tool path-walk -- topic --not base >out &&\n \n \tcat >expect <<-EOF &&\n+\tCOMMIT::$(git rev-parse topic)\n+\tcommits:1\n \tTREE::$(git rev-parse topic^{tree})\n \tTREE:left/:$(git rev-parse topic:left)\n \tTREE:right/:$(git rev-parse topic:right)\n@@ -103,10 +114,71 @@ test_expect_success 'topic, not base' '\n \ttest_cmp expect.sorted out.sorted\n '\n \n+test_expect_success 'topic, not base, only blobs' '\n+\ttest-tool path-walk --no-trees --no-commits \\\n+\t\t-- topic --not base >out &&\n+\n+\tcat >expect <<-EOF &&\n+\tcommits:0\n+\ttrees:0\n+\tBLOB:a:$(git rev-parse topic:a)\n+\tBLOB:left/b:$(git rev-parse topic:left/b)\n+\tBLOB:right/c:$(git rev-parse topic:right/c)\n+\tBLOB:right/d:$(git rev-parse topic:right/d)\n+\tblobs:4\n+\tEOF\n+\n+\tsort expect >expect.sorted &&\n+\tsort out >out.sorted &&\n+\n+\ttest_cmp expect.sorted out.sorted\n+'\n+\n+# No, this doesn't make a lot of sense for the path-walk API,\n+# but it is possible to do.\n+test_expect_success 'topic, not base, only commits' '\n+\ttest-tool path-walk --no-blobs --no-trees \\\n+\t\t-- topic --not base >out &&\n+\n+\tcat >expect <<-EOF &&\n+\tCOMMIT::$(git rev-parse topic)\n+\tcommits:1\n+\ttrees:0\n+\tblobs:0\n+\tEOF\n+\n+\tsort expect >expect.sorted &&\n+\tsort out >out.sorted &&\n+\n+\ttest_cmp expect.sorted out.sorted\n+'\n+\n+test_expect_success 'topic, not base, only trees' '\n+\ttest-tool path-walk --no-blobs --no-commits \\\n+\t\t-- topic --not base >out &&\n+\n+\tcat >expect <<-EOF &&\n+\tcommits:0\n+\tTREE::$(git rev-parse topic^{tree})\n+\tTREE:left/:$(git rev-parse topic:left)\n+\tTREE:right/:$(git rev-parse topic:right)\n+\ttrees:3\n+\tblobs:0\n+\tEOF\n+\n+\tsort expect >expect.sorted &&\n+\tsort out >out.sorted &&\n+\n+\ttest_cmp expect.sorted out.sorted\n+'\n+\n test_expect_success 'topic, not base, boundary' '\n \ttest-tool path-walk -- --boundary topic --not base >out &&\n \n \tcat >expect <<-EOF &&\n+\tCOMMIT::$(git rev-parse topic)\n+\tCOMMIT::$(git rev-parse base~1)\n+\tcommits:2\n \tTREE::$(git rev-parse topic^{tree})\n \tTREE::$(git rev-parse base~1^{tree})\n \tTREE:left/:$(git rev-parse base~1:left)\n-- \ngitgitgadget\n\n"},{"id":"504430","messageId":"6f48cddadc0ad1a6dc3caec9d81e014b668c1f03.1728396724.git.gitgitgadget@gmail.com","threadId":"62282","inReplyTo":"pull.1813.git.1728396723.gitgitgadget@gmail.com","subject":"[PATCH 04/17] path-walk: allow visiting tags","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-10-08T14:11:50Z","receivedAt":"2024-10-08T14:12:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn anticipation of using the path-walk API to analyze tags or include\nthem in a pack-file, add the ability to walk the tags that were included\nin the revision walk.\n\nWhen these tag objects point to blobs or trees, we need to make sure\nthose objects are also visited. Treat tagged trees as root trees, but\nput the tagged blobs in their own category.\n\nBe careful about objects that are referred to by multiple references.\n\nCo-authored-by: Johannes Schindelin \nSigned-off-by: Johannes Schindelin \nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/api-path-walk.txt | 2 +-\n path-walk.c | 76 ++++++++++++++++++++\n path-walk.h | 2 +\n t/helper/test-path-walk.c | 13 +++-\n t/t6601-path-walk.sh | 85 +++++++++++++++++++++--\n 5 files changed, 170 insertions(+), 8 deletions(-)\n\ndiff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt\nindex b7ae476ea0a..5fea1d1db17 100644\n--- a/Documentation/technical/api-path-walk.txt\n+++ b/Documentation/technical/api-path-walk.txt\n@@ -48,7 +48,7 @@ If you want the path-walk API to emit `UNINTERESTING` objects based on the\n commit walk's boundary, be sure to set `revs.boundary` so the boundary\n commits are emitted.\n \n-`commits`, `blobs`, `trees`::\n+`commits`, `blobs`, `trees`, `tags`::\n \tBy default, these members are enabled and signal that the path-walk\n \tAPI should call the `path_fn` on objects of these types. Specialized\n \tapplications could disable some options to make it simpler to walk\ndiff --git a/path-walk.c b/path-walk.c\nindex 22e1aa13f31..7cd461adf47 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -13,6 +13,7 @@\n #include \"revision.h\"\n #include \"string-list.h\"\n #include \"strmap.h\"\n+#include \"tag.h\"\n #include \"trace2.h\"\n #include \"tree.h\"\n #include \"tree-walk.h\"\n@@ -204,13 +205,88 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tCALLOC_ARRAY(commit_list, 1);\n \tcommit_list->type = OBJ_COMMIT;\n \n+\tif (info->tags)\n+\t\tinfo->revs->tag_objects = 1;\n+\n \t/* Insert a single list for the root tree into the paths. */\n \tCALLOC_ARRAY(root_tree_list, 1);\n \troot_tree_list->type = OBJ_TREE;\n \tstrmap_put(&ctx.paths_to_lists, root_path, root_tree_list);\n+\n+\t/*\n+\t * Set these values before preparing the walk to catch\n+\t * lightweight tags pointing to non-commits.\n+\t */\n+\tinfo->revs->blob_objects = info->blobs;\n+\tinfo->revs->tree_objects = info->trees;\n+\n \tif (prepare_revision_walk(info->revs))\n \t\tdie(_(\"failed to setup revision walk\"));\n \n+\tinfo->revs->blob_objects = info->revs->tree_objects = 0;\n+\n+\tif (info->tags) {\n+\t\tstruct oid_array tagged_blob_list = OID_ARRAY_INIT;\n+\t\tstruct oid_array tags = OID_ARRAY_INIT;\n+\n+\t\ttrace2_region_enter(\"path-walk\", \"tag-walk\", info->revs->repo);\n+\n+\t\t/*\n+\t\t * Walk any pending objects at this point, but they should only\n+\t\t * be tags.\n+\t\t */\n+\t\tfor (size_t i = 0; i < info->revs->pending.nr; i++) {\n+\t\t\tstruct object_array_entry *pending = info->revs->pending.objects + i;\n+\t\t\tstruct object *obj = pending->item;\n+\n+\t\t\tif (obj->type == OBJ_COMMIT || obj->flags & SEEN)\n+\t\t\t\tcontinue;\n+\n+\t\t\tobj->flags |= SEEN;\n+\n+\t\t\twhile (obj->type == OBJ_TAG) {\n+\t\t\t\tstruct tag *tag = lookup_tag(info->revs->repo,\n+\t\t\t\t\t\t\t &obj->oid);\n+\t\t\t\tif (oid_array_lookup(&tags, &obj->oid) < 0)\n+\t\t\t\t\toid_array_append(&tags, &obj->oid);\n+\t\t\t\tobj = tag->tagged;\n+\t\t\t}\n+\n+\t\t\tswitch (obj->type) {\n+\t\t\tcase OBJ_TREE:\n+\t\t\t\tif (info->trees &&\n+\t\t\t\t oid_array_lookup(&root_tree_list->oids, &obj->oid) < 0)\n+\t\t\t\t\toid_array_append(&root_tree_list->oids, &obj->oid);\n+\t\t\t\tbreak;\n+\n+\t\t\tcase OBJ_BLOB:\n+\t\t\t\tif (info->blobs &&\n+\t\t\t\t oid_array_lookup(&tagged_blob_list, &obj->oid) < 0)\n+\t\t\t\t\toid_array_append(&tagged_blob_list, &obj->oid);\n+\t\t\t\tbreak;\n+\n+\t\t\tcase OBJ_COMMIT:\n+\t\t\t\t/* Make sure it is in the object walk */\n+\t\t\t\tadd_pending_object(info->revs, obj, \"\");\n+\t\t\t\tbreak;\n+\n+\t\t\tdefault:\n+\t\t\t\tBUG(\"should not see any other type here\");\n+\t\t\t}\n+\t\t}\n+\n+\t\tinfo->path_fn(\"\", &tags, OBJ_TAG, info->path_fn_data);\n+\n+\t\tif (tagged_blob_list.nr && info->blobs)\n+\t\t\tinfo->path_fn(\"/tagged-blobs\", &tagged_blob_list, OBJ_BLOB,\n+\t\t\t\t info->path_fn_data);\n+\n+\t\ttrace2_data_intmax(\"path-walk\", ctx.repo, \"tags\", tags.nr);\n+\t\ttrace2_region_leave(\"path-walk\", \"tag-walk\", info->revs->repo);\n+\t\toid_array_clear(&tags);\n+\t\toid_array_clear(&tagged_blob_list);\n+\t}\n+\n \twhile ((c = get_revision(info->revs))) {\n \t\tstruct object_id *oid;\n \t\tstruct tree *t;\ndiff --git a/path-walk.h b/path-walk.h\nindex 6ef372d8942..3f3b63180ef 100644\n--- a/path-walk.h\n+++ b/path-walk.h\n@@ -37,12 +37,14 @@ struct path_walk_info {\n \tint commits;\n \tint trees;\n \tint blobs;\n+\tint tags;\n };\n \n #define PATH_WALK_INFO_INIT { \\\n \t.blobs = 1,\t\t\\\n \t.trees = 1,\t\t\\\n \t.commits = 1,\t\t\\\n+\t.tags = 1,\t\t\\\n }\n \n /**\ndiff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c\nindex 37c5e3e31e8..c6c60d68749 100644\n--- a/t/helper/test-path-walk.c\n+++ b/t/helper/test-path-walk.c\n@@ -21,6 +21,7 @@ struct path_walk_test_data {\n \tuintmax_t commit_nr;\n \tuintmax_t tree_nr;\n \tuintmax_t blob_nr;\n+\tuintmax_t tag_nr;\n };\n \n static int emit_block(const char *path, struct oid_array *oids,\n@@ -45,6 +46,11 @@ static int emit_block(const char *path, struct oid_array *oids,\n \t\ttdata->blob_nr += oids->nr;\n \t\tbreak;\n \n+\tcase OBJ_TAG:\n+\t\ttypestr = \"TAG\";\n+\t\ttdata->tag_nr += oids->nr;\n+\t\tbreak;\n+\n \tdefault:\n \t\tBUG(\"we do not understand this type\");\n \t}\n@@ -66,6 +72,8 @@ int cmd__path_walk(int argc, const char **argv)\n \t\t\t N_(\"toggle inclusion of blob objects\")),\n \t\tOPT_BOOL(0, \"commits\", &info.commits,\n \t\t\t N_(\"toggle inclusion of commit objects\")),\n+\t\tOPT_BOOL(0, \"tags\", &info.tags,\n+\t\t\t N_(\"toggle inclusion of tag objects\")),\n \t\tOPT_BOOL(0, \"trees\", &info.trees,\n \t\t\t N_(\"toggle inclusion of tree objects\")),\n \t\tOPT_END(),\n@@ -92,8 +100,9 @@ int cmd__path_walk(int argc, const char **argv)\n \n \tprintf(\"commits:%\" PRIuMAX \"\\n\"\n \t \"trees:%\" PRIuMAX \"\\n\"\n-\t \"blobs:%\" PRIuMAX \"\\n\",\n-\t data.commit_nr, data.tree_nr, data.blob_nr);\n+\t \"blobs:%\" PRIuMAX \"\\n\"\n+\t \"tags:%\" PRIuMAX \"\\n\",\n+\t data.commit_nr, data.tree_nr, data.blob_nr, data.tag_nr);\n \n \treturn res;\n }\ndiff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh\nindex e4788664f93..7758e2529ee 100755\n--- a/t/t6601-path-walk.sh\n+++ b/t/t6601-path-walk.sh\n@@ -7,24 +7,55 @@ test_description='direct path-walk API tests'\n test_expect_success 'setup test repository' '\n \tgit checkout -b base &&\n \n+\t# Make some objects that will only be reachable\n+\t# via non-commit tags.\n+\tmkdir child &&\n+\techo file >child/file &&\n+\tgit add child &&\n+\tgit commit -m \"will abandon\" &&\n+\tgit tag -a -m \"tree\" tree-tag HEAD^{tree} &&\n+\techo file2 >file2 &&\n+\tgit add file2 &&\n+\tgit commit --amend -m \"will abandon\" &&\n+\tgit tag tree-tag2 HEAD^{tree} &&\n+\n+\techo blob >file &&\n+\tblob_oid=$(git hash-object -t blob -w --stdin file2 &&\n+\tblob2_oid=$(git hash-object -t blob -w --stdin a &&\n \techo b >left/b &&\n \techo c >right/c &&\n \tgit add . &&\n-\tgit commit -m \"first\" &&\n+\tgit commit --amend -m \"first\" &&\n+\tgit tag -m \"first\" first HEAD &&\n \n \techo d >right/d &&\n \tgit add right &&\n \tgit commit -m \"second\" &&\n+\tgit tag -a -m \"second (under)\" second.1 HEAD &&\n+\tgit tag -a -m \"second (top)\" second.2 second.1 &&\n \n+\t# Set up file/dir collision in history.\n+\trm a &&\n+\tmkdir a &&\n+\techo a >a/a &&\n \techo bb >left/b &&\n-\tgit commit -a -m \"third\" &&\n+\tgit add a left &&\n+\tgit commit -m \"third\" &&\n+\tgit tag -a -m \"third\" third &&\n \n \tgit checkout -b topic HEAD~1 &&\n \techo cc >right/c &&\n-\tgit commit -a -m \"topic\"\n+\tgit commit -a -m \"topic\" &&\n+\tgit tag -a -m \"fourth\" fourth\n '\n \n test_expect_success 'all' '\n@@ -40,19 +71,35 @@ test_expect_success 'all' '\n \tTREE::$(git rev-parse base^{tree})\n \tTREE::$(git rev-parse base~1^{tree})\n \tTREE::$(git rev-parse base~2^{tree})\n+\tTREE::$(git rev-parse refs/tags/tree-tag^{})\n+\tTREE::$(git rev-parse refs/tags/tree-tag2^{})\n+\tTREE:a/:$(git rev-parse base:a)\n \tTREE:left/:$(git rev-parse base:left)\n \tTREE:left/:$(git rev-parse base~2:left)\n \tTREE:right/:$(git rev-parse topic:right)\n \tTREE:right/:$(git rev-parse base~1:right)\n \tTREE:right/:$(git rev-parse base~2:right)\n-\ttrees:9\n+\tTREE:child/:$(git rev-parse refs/tags/tree-tag^{}:child)\n+\ttrees:13\n \tBLOB:a:$(git rev-parse base~2:a)\n+\tBLOB:file2:$(git rev-parse refs/tags/tree-tag2^{}:file2)\n \tBLOB:left/b:$(git rev-parse base~2:left/b)\n \tBLOB:left/b:$(git rev-parse base:left/b)\n \tBLOB:right/c:$(git rev-parse base~2:right/c)\n \tBLOB:right/c:$(git rev-parse topic:right/c)\n \tBLOB:right/d:$(git rev-parse base~1:right/d)\n-\tblobs:6\n+\tBLOB:/tagged-blobs:$(git rev-parse refs/tags/blob-tag^{})\n+\tBLOB:/tagged-blobs:$(git rev-parse refs/tags/blob-tag2^{})\n+\tBLOB:child/file:$(git rev-parse refs/tags/tree-tag^{}:child/file)\n+\tblobs:10\n+\tTAG::$(git rev-parse refs/tags/first)\n+\tTAG::$(git rev-parse refs/tags/second.1)\n+\tTAG::$(git rev-parse refs/tags/second.2)\n+\tTAG::$(git rev-parse refs/tags/third)\n+\tTAG::$(git rev-parse refs/tags/fourth)\n+\tTAG::$(git rev-parse refs/tags/tree-tag)\n+\tTAG::$(git rev-parse refs/tags/blob-tag)\n+\ttags:7\n \tEOF\n \n \tsort expect >expect.sorted &&\n@@ -83,6 +130,7 @@ test_expect_success 'topic only' '\n \tBLOB:right/c:$(git rev-parse topic:right/c)\n \tBLOB:right/d:$(git rev-parse base~1:right/d)\n \tblobs:5\n+\ttags:0\n \tEOF\n \n \tsort expect >expect.sorted &&\n@@ -106,6 +154,7 @@ test_expect_success 'topic, not base' '\n \tBLOB:right/c:$(git rev-parse topic:right/c)\n \tBLOB:right/d:$(git rev-parse topic:right/d)\n \tblobs:4\n+\ttags:0\n \tEOF\n \n \tsort expect >expect.sorted &&\n@@ -126,6 +175,7 @@ test_expect_success 'topic, not base, only blobs' '\n \tBLOB:right/c:$(git rev-parse topic:right/c)\n \tBLOB:right/d:$(git rev-parse topic:right/d)\n \tblobs:4\n+\ttags:0\n \tEOF\n \n \tsort expect >expect.sorted &&\n@@ -145,6 +195,7 @@ test_expect_success 'topic, not base, only commits' '\n \tcommits:1\n \ttrees:0\n \tblobs:0\n+\ttags:0\n \tEOF\n \n \tsort expect >expect.sorted &&\n@@ -164,6 +215,7 @@ test_expect_success 'topic, not base, only trees' '\n \tTREE:right/:$(git rev-parse topic:right)\n \ttrees:3\n \tblobs:0\n+\ttags:0\n \tEOF\n \n \tsort expect >expect.sorted &&\n@@ -191,6 +243,7 @@ test_expect_success 'topic, not base, boundary' '\n \tBLOB:right/c:$(git rev-parse topic:right/c)\n \tBLOB:right/d:$(git rev-parse base~1:right/d)\n \tblobs:5\n+\ttags:0\n \tEOF\n \n \tsort expect >expect.sorted &&\n@@ -199,4 +252,26 @@ test_expect_success 'topic, not base, boundary' '\n \ttest_cmp expect.sorted out.sorted\n '\n \n+test_expect_success 'trees are reported exactly once' '\n+\ttest_when_finished \"rm -rf unique-trees\" &&\n+\ttest_create_repo unique-trees &&\n+\t(\n+\t\tcd unique-trees &&\n+\t\tmkdir initial &&\n+\t\ttest_commit initial/file &&\n+\n+\t\tgit switch -c move-to-top &&\n+\t\tgit mv initial/file.t ./ &&\n+\t\ttest_tick &&\n+\t\tgit commit -m moved &&\n+\n+\t\tgit update-ref refs/heads/other HEAD\n+\t) &&\n+\n+\ttest-tool -C unique-trees path-walk -- --all >out &&\n+\ttree=$(git -C unique-trees rev-parse HEAD:) &&\n+\tgrep \"$tree\" out >out-filtered &&\n+\ttest_line_count = 1 out-filtered\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"504431","messageId":"cd98447f7c8a3ee6b7566b12e00eaecd6e8c0c38.1728396724.git.gitgitgadget@gmail.com","threadId":"62282","inReplyTo":"pull.1813.git.1728396723.gitgitgadget@gmail.com","subject":"[PATCH 05/17] revision: create mark_trees_uninteresting_dense()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-10-08T14:11:51Z","receivedAt":"2024-10-08T14:12:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe sparse tree walk algorithm was created in d5d2e93577e (revision:\nimplement sparse algorithm, 2019-01-16) and involves using the\nmark_trees_uninteresting_sparse() method. This method takes a repository\nand an oidset of tree IDs, some of which have the UNINTERESTING flag and\nsome of which do not.\n\nCreate a method that has an equivalent set of preconditions but uses a\n\"dense\" walk (recursively visits all reachable trees, as long as they\nhave not previously been marked UNINTERESTING). This is an important\ndifference from mark_tree_uninteresting(), which short-circuits if the\ngiven tree has the UNINTERESTING flag.\n\nA use of this method will be added in a later change, with a condition\nset whether the sparse or dense approach should be used.\n\nSigned-off-by: Derrick Stolee \n---\n revision.c | 15 +++++++++++++++\n revision.h | 1 +\n 2 files changed, 16 insertions(+)\n\ndiff --git a/revision.c b/revision.c\nindex 2d7ad2bddff..bdc312f1538 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -219,6 +219,21 @@ static void add_children_by_path(struct repository *r,\n \tfree_tree_buffer(tree);\n }\n \n+void mark_trees_uninteresting_dense(struct repository *r,\n+\t\t\t\t struct oidset *trees)\n+{\n+\tstruct object_id *oid;\n+\tstruct oidset_iter iter;\n+\n+\toidset_iter_init(trees, &iter);\n+\twhile ((oid = oidset_iter_next(&iter))) {\n+\t\tstruct tree *tree = lookup_tree(r, oid);\n+\n+\t\tif (tree && (tree->object.flags & UNINTERESTING))\n+\t\t\tmark_tree_contents_uninteresting(r, tree);\n+\t}\n+}\n+\n void mark_trees_uninteresting_sparse(struct repository *r,\n \t\t\t\t struct oidset *trees)\n {\ndiff --git a/revision.h b/revision.h\nindex 71e984c452b..8938b2db112 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -487,6 +487,7 @@ void put_revision_mark(const struct rev_info *revs,\n \n void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit);\n void mark_tree_uninteresting(struct repository *r, struct tree *tree);\n+void mark_trees_uninteresting_dense(struct repository *r, struct oidset *trees);\n void mark_trees_uninteresting_sparse(struct repository *r, struct oidset *trees);\n \n void show_object_with_name(FILE *, struct object *, const char *);\n-- \ngitgitgadget\n\n"},{"id":"504432","messageId":"214e10a99841f09361081a6a0f182f66f420aa09.1728396724.git.gitgitgadget@gmail.com","threadId":"62282","inReplyTo":"pull.1813.git.1728396723.gitgitgadget@gmail.com","subject":"[PATCH 06/17] path-walk: add prune_all_uninteresting option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-10-08T14:11:52Z","receivedAt":"2024-10-08T14:12:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis option causes the path-walk API to act like the sparse tree-walk\nalgorithm implemented by mark_trees_uninteresting_sparse() in\nlist-objects.c.\n\nStarting from the commits marked as UNINTERESTING, their root trees and\nall objects reachable from those trees are UNINTERSTING, at least as we\nwalk path-by-path. When we reach a path where all objects associated\nwith that path are marked UNINTERESTING, then do no continue walking the\nchildren of that path.\n\nWe need to be careful to pass the UNINTERESTING flag in a deep way on\nthe UNINTERESTING objects before we start the path-walk, or else the\ndepth-first search for the path-walk API may accidentally report some\nobjects as interesting.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/api-path-walk.txt | 8 +++\n path-walk.c | 64 ++++++++++++++++++++++-\n path-walk.h | 8 +++\n t/helper/test-path-walk.c | 10 +++-\n t/t6601-path-walk.sh | 40 +++++++++++---\n 5 files changed, 118 insertions(+), 12 deletions(-)\n\ndiff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt\nindex 5fea1d1db17..c51f92cd649 100644\n--- a/Documentation/technical/api-path-walk.txt\n+++ b/Documentation/technical/api-path-walk.txt\n@@ -57,6 +57,14 @@ commits are emitted.\n While it is possible to walk only commits in this way, consumers would be\n better off using the revision walk API instead.\n \n+`prune_all_uninteresting`::\n+\tBy default, all reachable paths are emitted by the path-walk API.\n+\tThis option allows consumers to declare that they are not\n+\tinterested in paths where all included objects are marked with the\n+\t`UNINTERESTING` flag. This requires using the `boundary` option in\n+\tthe revision walk so that the walk emits commits marked with the\n+\t`UNINTERESTING` flag.\n+\n Examples\n --------\n \ndiff --git a/path-walk.c b/path-walk.c\nindex 7cd461adf47..dce0840937e 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -22,6 +22,7 @@ struct type_and_oid_list\n {\n \tenum object_type type;\n \tstruct oid_array oids;\n+\tint maybe_interesting;\n };\n \n #define TYPE_AND_OID_LIST_INIT { \\\n@@ -124,6 +125,8 @@ static int add_children(struct path_walk_context *ctx,\n \t\t\tstrmap_put(&ctx->paths_to_lists, path.buf, list);\n \t\t\tstring_list_append(&ctx->path_stack, path.buf);\n \t\t}\n+\t\tif (!(o->flags & UNINTERESTING))\n+\t\t\tlist->maybe_interesting = 1;\n \t\toid_array_append(&list->oids, &entry.oid);\n \t}\n \n@@ -145,6 +148,40 @@ static int walk_path(struct path_walk_context *ctx,\n \n \tlist = strmap_get(&ctx->paths_to_lists, path);\n \n+\tif (ctx->info->prune_all_uninteresting) {\n+\t\t/*\n+\t\t * This is true if all objects were UNINTERESTING\n+\t\t * when added to the list.\n+\t\t */\n+\t\tif (!list->maybe_interesting)\n+\t\t\treturn 0;\n+\n+\t\t/*\n+\t\t * But it's still possible that the objects were set\n+\t\t * as UNINTERESTING after being added. Do a quick check.\n+\t\t */\n+\t\tlist->maybe_interesting = 0;\n+\t\tfor (size_t i = 0;\n+\t\t !list->maybe_interesting && i < list->oids.nr;\n+\t\t i++) {\n+\t\t\tif (list->type == OBJ_TREE) {\n+\t\t\t\tstruct tree *t = lookup_tree(ctx->repo,\n+\t\t\t\t\t\t\t &list->oids.oid[i]);\n+\t\t\t\tif (t && !(t->object.flags & UNINTERESTING))\n+\t\t\t\t\tlist->maybe_interesting = 1;\n+\t\t\t} else {\n+\t\t\t\tstruct blob *b = lookup_blob(ctx->repo,\n+\t\t\t\t\t\t\t &list->oids.oid[i]);\n+\t\t\t\tif (b && !(b->object.flags & UNINTERESTING))\n+\t\t\t\t\tlist->maybe_interesting = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/* We have confirmed that all objects are UNINTERESTING. */\n+\t\tif (!list->maybe_interesting)\n+\t\t\treturn 0;\n+\t}\n+\n \t/* Evaluate function pointer on this data, if requested. */\n \tif ((list->type == OBJ_TREE && ctx->info->trees) ||\n \t (list->type == OBJ_BLOB && ctx->info->blobs))\n@@ -187,7 +224,7 @@ static void clear_strmap(struct strmap *map)\n int walk_objects_by_path(struct path_walk_info *info)\n {\n \tconst char *root_path = \"\";\n-\tint ret = 0;\n+\tint ret = 0, has_uninteresting = 0;\n \tsize_t commits_nr = 0, paths_nr = 0;\n \tstruct commit *c;\n \tstruct type_and_oid_list *root_tree_list;\n@@ -199,6 +236,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \t\t.path_stack = STRING_LIST_INIT_DUP,\n \t\t.paths_to_lists = STRMAP_INIT\n \t};\n+\tstruct oidset root_tree_set = OIDSET_INIT;\n \n \ttrace2_region_enter(\"path-walk\", \"commit-walk\", info->revs->repo);\n \n@@ -211,6 +249,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \t/* Insert a single list for the root tree into the paths. */\n \tCALLOC_ARRAY(root_tree_list, 1);\n \troot_tree_list->type = OBJ_TREE;\n+\troot_tree_list->maybe_interesting = 1;\n \tstrmap_put(&ctx.paths_to_lists, root_path, root_tree_list);\n \n \t/*\n@@ -304,10 +343,16 @@ int walk_objects_by_path(struct path_walk_info *info)\n \t\tt = lookup_tree(info->revs->repo, oid);\n \n \t\tif (t) {\n+\t\t\tif ((c->object.flags & UNINTERESTING)) {\n+\t\t\t\tt->object.flags |= UNINTERESTING;\n+\t\t\t\thas_uninteresting = 1;\n+\t\t\t}\n+\n \t\t\tif (t->object.flags & SEEN)\n \t\t\t\tcontinue;\n \t\t\tt->object.flags |= SEEN;\n-\t\t\toid_array_append(&root_tree_list->oids, oid);\n+\t\t\tif (!oidset_insert(&root_tree_set, oid))\n+\t\t\t\toid_array_append(&root_tree_list->oids, oid);\n \t\t} else {\n \t\t\twarning(\"could not find tree %s\", oid_to_hex(oid));\n \t\t}\n@@ -323,6 +368,21 @@ int walk_objects_by_path(struct path_walk_info *info)\n \toid_array_clear(&commit_list->oids);\n \tfree(commit_list);\n \n+\t/*\n+\t * Before performing a DFS of our paths and emitting them as interesting,\n+\t * do a full walk of the trees to distribute the UNINTERESTING bit. Use\n+\t * the sparse algorithm if prune_all_uninteresting was set.\n+\t */\n+\tif (has_uninteresting) {\n+\t\ttrace2_region_enter(\"path-walk\", \"uninteresting-walk\", info->revs->repo);\n+\t\tif (info->prune_all_uninteresting)\n+\t\t\tmark_trees_uninteresting_sparse(ctx.repo, &root_tree_set);\n+\t\telse\n+\t\t\tmark_trees_uninteresting_dense(ctx.repo, &root_tree_set);\n+\t\ttrace2_region_leave(\"path-walk\", \"uninteresting-walk\", info->revs->repo);\n+\t}\n+\toidset_clear(&root_tree_set);\n+\n \tstring_list_append(&ctx.path_stack, root_path);\n \n \ttrace2_region_enter(\"path-walk\", \"path-walk\", info->revs->repo);\ndiff --git a/path-walk.h b/path-walk.h\nindex 3f3b63180ef..3e44c4b8a58 100644\n--- a/path-walk.h\n+++ b/path-walk.h\n@@ -38,6 +38,14 @@ struct path_walk_info {\n \tint trees;\n \tint blobs;\n \tint tags;\n+\n+\t/**\n+\t * When 'prune_all_uninteresting' is set and a path has all objects\n+\t * marked as UNINTERESTING, then the path-walk will not visit those\n+\t * objects. It will not call path_fn on those objects and will not\n+\t * walk the children of such trees.\n+\t */\n+\tint prune_all_uninteresting;\n };\n \n #define PATH_WALK_INFO_INIT { \\\ndiff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c\nindex c6c60d68749..06b103d8760 100644\n--- a/t/helper/test-path-walk.c\n+++ b/t/helper/test-path-walk.c\n@@ -55,8 +55,12 @@ static int emit_block(const char *path, struct oid_array *oids,\n \t\tBUG(\"we do not understand this type\");\n \t}\n \n-\tfor (size_t i = 0; i < oids->nr; i++)\n-\t\tprintf(\"%s:%s:%s\\n\", typestr, path, oid_to_hex(&oids->oid[i]));\n+\tfor (size_t i = 0; i < oids->nr; i++) {\n+\t\tstruct object *o = lookup_unknown_object(the_repository,\n+\t\t\t\t\t\t\t &oids->oid[i]);\n+\t\tprintf(\"%s:%s:%s%s\\n\", typestr, path, oid_to_hex(&oids->oid[i]),\n+\t\t o->flags & UNINTERESTING ? \":UNINTERESTING\" : \"\");\n+\t}\n \n \treturn 0;\n }\n@@ -76,6 +80,8 @@ int cmd__path_walk(int argc, const char **argv)\n \t\t\t N_(\"toggle inclusion of tag objects\")),\n \t\tOPT_BOOL(0, \"trees\", &info.trees,\n \t\t\t N_(\"toggle inclusion of tree objects\")),\n+\t\tOPT_BOOL(0, \"prune\", &info.prune_all_uninteresting,\n+\t\t\t N_(\"toggle pruning of uninteresting paths\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh\nindex 7758e2529ee..943adc6c8f1 100755\n--- a/t/t6601-path-walk.sh\n+++ b/t/t6601-path-walk.sh\n@@ -229,19 +229,19 @@ test_expect_success 'topic, not base, boundary' '\n \n \tcat >expect <<-EOF &&\n \tCOMMIT::$(git rev-parse topic)\n-\tCOMMIT::$(git rev-parse base~1)\n+\tCOMMIT::$(git rev-parse base~1):UNINTERESTING\n \tcommits:2\n \tTREE::$(git rev-parse topic^{tree})\n-\tTREE::$(git rev-parse base~1^{tree})\n-\tTREE:left/:$(git rev-parse base~1:left)\n+\tTREE::$(git rev-parse base~1^{tree}):UNINTERESTING\n+\tTREE:left/:$(git rev-parse base~1:left):UNINTERESTING\n \tTREE:right/:$(git rev-parse topic:right)\n-\tTREE:right/:$(git rev-parse base~1:right)\n+\tTREE:right/:$(git rev-parse base~1:right):UNINTERESTING\n \ttrees:5\n-\tBLOB:a:$(git rev-parse base~1:a)\n-\tBLOB:left/b:$(git rev-parse base~1:left/b)\n-\tBLOB:right/c:$(git rev-parse base~1:right/c)\n+\tBLOB:a:$(git rev-parse base~1:a):UNINTERESTING\n+\tBLOB:left/b:$(git rev-parse base~1:left/b):UNINTERESTING\n+\tBLOB:right/c:$(git rev-parse base~1:right/c):UNINTERESTING\n \tBLOB:right/c:$(git rev-parse topic:right/c)\n-\tBLOB:right/d:$(git rev-parse base~1:right/d)\n+\tBLOB:right/d:$(git rev-parse base~1:right/d):UNINTERESTING\n \tblobs:5\n \ttags:0\n \tEOF\n@@ -252,6 +252,30 @@ test_expect_success 'topic, not base, boundary' '\n \ttest_cmp expect.sorted out.sorted\n '\n \n+test_expect_success 'topic, not base, boundary with pruning' '\n+\ttest-tool path-walk --prune -- --boundary topic --not base >out &&\n+\n+\tcat >expect <<-EOF &&\n+\tCOMMIT::$(git rev-parse topic)\n+\tCOMMIT::$(git rev-parse base~1):UNINTERESTING\n+\tcommits:2\n+\tTREE::$(git rev-parse topic^{tree})\n+\tTREE::$(git rev-parse base~1^{tree}):UNINTERESTING\n+\tTREE:right/:$(git rev-parse topic:right)\n+\tTREE:right/:$(git rev-parse base~1:right):UNINTERESTING\n+\ttrees:4\n+\tBLOB:right/c:$(git rev-parse base~1:right/c):UNINTERESTING\n+\tBLOB:right/c:$(git rev-parse topic:right/c)\n+\tblobs:2\n+\ttags:0\n+\tEOF\n+\n+\tsort expect >expect.sorted &&\n+\tsort out >out.sorted &&\n+\n+\ttest_cmp expect.sorted out.sorted\n+'\n+\n test_expect_success 'trees are reported exactly once' '\n \ttest_when_finished \"rm -rf unique-trees\" &&\n \ttest_create_repo unique-trees &&\n-- \ngitgitgadget\n\n"},{"id":"504433","messageId":"cd360ad104017ceaa9fb43ae036be79f767b557b.1728396724.git.gitgitgadget@gmail.com","threadId":"62282","inReplyTo":"pull.1813.git.1728396723.gitgitgadget@gmail.com","subject":"[PATCH 07/17] pack-objects: extract should_attempt_deltas()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-10-08T14:11:53Z","receivedAt":"2024-10-08T14:12:13Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis will be helpful in a future change that introduces a new way to\ncompute deltas.\n\nBe careful to preserve the nr_deltas counting logic in the existing\nmethod, but take the rest of the logic wholesale.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/pack-objects.c | 53 +++++++++++++++++++++++-------------------\n 1 file changed, 29 insertions(+), 24 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 0fc0680b402..82f4ca04000 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3167,6 +3167,33 @@ static int add_ref_tag(const char *tag UNUSED, const char *referent UNUSED, cons\n \treturn 0;\n }\n \n+static int should_attempt_deltas(struct object_entry *entry)\n+{\n+\tif (DELTA(entry))\n+\t\treturn 0;\n+\n+\tif (!entry->type_valid ||\n+\t oe_size_less_than(&to_pack, entry, 50))\n+\t\treturn 0;\n+\n+\tif (entry->no_try_delta)\n+\t\treturn 0;\n+\n+\tif (!entry->preferred_base) {\n+\t\tif (oe_type(entry) < 0)\n+\t\t\tdie(_(\"unable to get type of object %s\"),\n+\t\t\t\toid_to_hex(&entry->idx.oid));\n+\t} else if (oe_type(entry) < 0) {\n+\t\t/*\n+\t\t * This object is not found, but we\n+\t\t * don't have to include it anyway.\n+\t\t */\n+\t\treturn 0;\n+\t}\n+\n+\treturn 1;\n+}\n+\n static void prepare_pack(int window, int depth)\n {\n \tstruct object_entry **delta_list;\n@@ -3197,33 +3224,11 @@ static void prepare_pack(int window, int depth)\n \tfor (i = 0; i < to_pack.nr_objects; i++) {\n \t\tstruct object_entry *entry = to_pack.objects + i;\n \n-\t\tif (DELTA(entry))\n-\t\t\t/* This happens if we decided to reuse existing\n-\t\t\t * delta from a pack. \"reuse_delta &&\" is implied.\n-\t\t\t */\n-\t\t\tcontinue;\n-\n-\t\tif (!entry->type_valid ||\n-\t\t oe_size_less_than(&to_pack, entry, 50))\n+\t\tif (!should_attempt_deltas(entry))\n \t\t\tcontinue;\n \n-\t\tif (entry->no_try_delta)\n-\t\t\tcontinue;\n-\n-\t\tif (!entry->preferred_base) {\n+\t\tif (!entry->preferred_base)\n \t\t\tnr_deltas++;\n-\t\t\tif (oe_type(entry) < 0)\n-\t\t\t\tdie(_(\"unable to get type of object %s\"),\n-\t\t\t\t oid_to_hex(&entry->idx.oid));\n-\t\t} else {\n-\t\t\tif (oe_type(entry) < 0) {\n-\t\t\t\t/*\n-\t\t\t\t * This object is not found, but we\n-\t\t\t\t * don't have to include it anyway.\n-\t\t\t\t */\n-\t\t\t\tcontinue;\n-\t\t\t}\n-\t\t}\n \n \t\tdelta_list[n++] = entry;\n \t}\n-- \ngitgitgadget\n\n"},{"id":"504434","messageId":"f8ee11d3003e743affb39835ba3583dd2498e576.1728396724.git.gitgitgadget@gmail.com","threadId":"62282","inReplyTo":"pull.1813.git.1728396723.gitgitgadget@gmail.com","subject":"[PATCH 08/17] pack-objects: add --path-walk option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-10-08T14:11:54Z","receivedAt":"2024-10-08T14:12:15Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn order to more easily compute delta bases among objects that appear at the\nexact same path, add a --path-walk option to 'git pack-objects'.\n\nThis option will use the path-walk API instead of the object walk given by\nthe revision machinery. Since objects will be provided in batches\nrepresenting a common path, those objects can be tested for delta bases\nimmediately instead of waiting for a sort of the full object list by\nname-hash. This has multiple benefits, including avoiding collisions by\nname-hash.\n\nThe objects marked as UNINTERESTING are included in these batches, so we\nare guaranteeing some locality to find good delta bases.\n\nAfter the individual passes are done on a per-path basis, the default\nname-hash is used to find other opportunistic delta bases that did not\nmatch exactly by the full path name.\n\nThe current implementation performs delta calculations while walking\nobjects, which is not ideal for a few reasons. First, this will cause\nthe \"Enumerating objects\" phase to be much longer than usual. Second, it\ndoes not take advantage of threading during the path-scoped delta\ncalculations. Even with this lack of threading, the path-walk option is\nsometimes faster than the usual approach. Future changes will refactor\nthis code to allow for threading, but that complexity is deferred until\nlater to keep this patch as simple as possible.\n\nThis new walk is incompatible with some features and is ignored by\nothers:\n\n * Object filters are not currently integrated with the path-walk API,\n such as sparse-checkout or tree depth. A blobless packfile could be\n integrated easily, but that is deferred for later.\n\n * Server-focused features such as delta islands, shallow packs, and\n using a bitmap index are incompatible with the path-walk API.\n\n * The path walk API is only compatible with the --revs option, not\n taking object lists or pack lists over stdin. These alternative ways\n to specify the objects currently ignores the --path-walk option\n without even a warning.\n\nFuture changes will create performance tests that demonstrate the power\nof this approach.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-pack-objects.txt | 13 +-\n Documentation/technical/api-path-walk.txt | 3 +-\n builtin/pack-objects.c | 147 ++++++++++++++++++++--\n t/t5300-pack-object.sh | 17 +++\n 4 files changed, 169 insertions(+), 11 deletions(-)\n\ndiff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt\nindex e32404c6aae..f2fda800a43 100644\n--- a/Documentation/git-pack-objects.txt\n+++ b/Documentation/git-pack-objects.txt\n@@ -15,7 +15,8 @@ SYNOPSIS\n \t[--revs [--unpacked | --all]] [--keep-pack=]\n \t[--cruft] [--cruft-expiration=