From: Taylor Blau Date: Mon, 04 May 2026 00:11:34 GMT Subject: [RFC PATCH 7/7] pack-objects: support `--delta-islands` with `--path-walk` Message-ID: <0a1a9ed1e3c8f883587800c232e504937d706bc0.1777853408.git.me@ttaylorr.com> In-Reply-To: Since the inception of `--path-walk`, this option has a documented incompatibility with `--delta-islands`. When discussing those original patches on the list, a message from Stolee in [1] noted the following: this could be remedied by [...] doing a separate walk to identify islands using the normal method In a related portion of the thread, Peff explains[2]: The delta islands code already does its own tree walk to propagate the bits down (it does rely on the base walk's show_commit() to propagate through the commits). Once each object has its island bitmaps, I think however you choose to come up with delta candidates [...] you should be able to use it. It's fundamentally just answering the question of "am I allowed to delta between these two objects". That is similar to what this patch does, and it turns out the cheaper option (do the side-effects inside the path-walk callback rather than via a second walk) is sufficient. Recall how delta-islands are computed during a normal repack: - `show_commit()` calls `propagate_island_marks()` for each commit, which merges the commit's island bitset onto its root tree object and onto each of its parent commits. - `show_object()` for a tree records the tree's depth derived from the slash-separated pathname. Subsequent `resolve_tree_islands()` uses that depth to walk trees in increasing-depth order, propagating each tree's marks to its children. - At delta-search time, `in_same_island()` enforces that a delta target's island bitmap is a subset of its base's: every island that reaches the target must also reach the base. Path-walk's enumeration callback is `add_objects_by_path()`. It already adds objects to `to_pack', but until now did not perform any of the island-related side effects. Two things are needed: - For each commit batch, call `propagate_island_marks()` on the commit, exactly as show_commit() does. Order matters here. `mark_remote_island_1()` only seeds marks on tip commits, so a non-tip commit has marks in the `island_marks` map only after some descendant has already had `propagate_island_marks()` run on it. If we see a commit before its descendants, its `island_marks` entry would still be empty, the call would be a no-op, and that commit's root tree would never receive any marks at all. As a consequence, `resolve_tree_islands()` would later look up the tree, find nothing, and propagate nothing. The traversal must visit children before parents. The path-walk batch preserves that order mechanically. Path-walk appends commits to its `OBJ_COMMIT` batch as they come back from the same `get_revision()` loop the regular traversal uses, and `add_objects_by_path()` iterates the batch in array order. So every commit reaches `propagate_island_marks()` in the same sequence that `show_commit()` would have seen it, and the descendant-first chain that the algorithm relies on is intact. Skip the call for boundary commits to match `show_commit()`, which is only invoked for interesting commits (this call is a no-op anyway for boundary commits since they are not in 'island_marks', but matching `show_commit()` exactly keeps the two enumeration modes tidy). - For each tree batch, record the tree's depth from the path. Use the `record_tree_depth()` helper from the previous commit so both callbacks behave identically, including the "max-depth-wins" behavior when a tree is reached via more than one path. The helper accepts both the show_object() path shape ("foo", "foo/bar") and the path-walk shape with a trailing '/' ("foo/", "foo/bar/"), so depths recorded from either traversal mode are directly comparable. This is implicit in the implementation sketch from Peff above. `resolve_tree_islands()` sorts trees by `oe->tree_depth` (ascending) before propagating marks down, so that a parent tree's marks are finalized before its children inherit them. Without recording the depth at path-walk time, every path-walk-discovered tree would land at depth 0 in `to_pack`, the sort would lose its ordering, and children could inherit marks from parents whose own contributions had not yet been merged in. With those two pieces in place, `resolve_tree_islands()` receives identical input to a normal traversal, so the existing correctness argument carries over verbatim: depth-ordered processing guarantees that a parent tree's marks are propagated to a child only after the parent itself has been finalized, and the "is-this-a-subset" check at delta time is the same regardless of how the marks got there. Coverage in t5320 exercises both repack flavors (with and without '-b'), confirms that cross-island deltas remain forbidden, and that intra-island deltas are still allowed. [1]: https://lore.kernel.org/git/9aa2471b-0850-4707-9733-d3b33609f5f2@gmail.com/ [2]: https://lore.kernel.org/git/20240911063203.GA1538586@coredump.intra.peff.net/ Signed-off-by: Taylor Blau --- Documentation/git-pack-objects.adoc | 15 +++++++-------- builtin/pack-objects.c | 22 ++++++++++++++++++---- t/t5320-delta-islands.sh | 29 +++++++++++++++++++++++++++++ 3 files changed, 54 insertions(+), 12 deletions(-) diff --git a/Documentation/git-pack-objects.adoc b/Documentation/git-pack-objects.adoc index 60e594c7bc4..aa7a9721203 100644 --- a/Documentation/git-pack-objects.adoc +++ b/Documentation/git-pack-objects.adoc @@ -402,14 +402,13 @@ will be automatically changed to version `1`. of filenames that cause collisions in Git's default name-hash algorithm. + -Incompatible with `--delta-islands`. Path-walk supports -the `--filter=` forms `blob:none`, `blob:limit=`, -`sparse:oid=`, `tree:0`, `object:type=`, and `combine:` -over any of those. Other filter forms fall back to the regular object -traversal. When `--use-bitmap-index` is specified with `--path-walk`, a -successful bitmap traversal is used for object enumeration, with -path-walk remaining as the fallback traversal when the bitmap cannot -satisfy the request. +Path-walk supports the `--filter=` forms `blob:none`, +`blob:limit=`, `sparse:oid=`, `tree:0`, `object:type=`, +and `combine:` over any of those. Other filter forms fall back to the +regular object traversal. When `--use-bitmap-index` is specified with +`--path-walk`, a successful bitmap traversal is used for object +enumeration, with path-walk remaining as the fallback traversal when +the bitmap cannot satisfy the request. DELTA ISLANDS diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index 842d1fcac29..d79366db3de 100644 --- a/builtin/pack-objects.c +++ b/builtin/pack-objects.c @@ -4739,13 +4739,29 @@ static int add_objects_by_path(const char *path, add_object_entry(oid, type, path, exclude); - if (type == OBJ_COMMIT && write_bitmap_index) { + if (type == OBJ_COMMIT) { struct commit *commit; + if (!write_bitmap_index && !use_delta_islands) + continue; + commit = lookup_commit(the_repository, oid); if (!commit) die(_("could not find commit %s"), oid_to_hex(oid)); - index_commit_for_bitmap(commit); + if (write_bitmap_index) + index_commit_for_bitmap(commit); + /* + * Skip island propagation for boundary commits. + * The regular traversal's show_commit() is only + * called for interesting commits; matching that + * here keeps path-walk from doing extra work that + * would only be a no-op anyway (boundary commits + * are not in island_marks). + */ + if (use_delta_islands && !exclude) + propagate_island_marks(the_repository, commit); + } else if (type == OBJ_TREE && use_delta_islands) { + record_tree_depth(oid, path); } } @@ -5196,8 +5212,6 @@ int cmd_pack_objects(int argc, const char *option = NULL; if (!path_walk_filter_compatible(&filter_options)) option = "--filter"; - else if (use_delta_islands) - option = "--delta-islands"; if (option) { warning(_("cannot use %s with %s"), diff --git a/t/t5320-delta-islands.sh b/t/t5320-delta-islands.sh index 2c961c70963..9b28344a0a3 100755 --- a/t/t5320-delta-islands.sh +++ b/t/t5320-delta-islands.sh @@ -53,6 +53,35 @@ test_expect_success 'separate islands disallows delta' ' ! is_delta_base $two $one ' +test_expect_success 'path-walk island repack respects islands' ' + GIT_TRACE2_EVENT="$(pwd)/trace.path-walk-islands" \ + git -c "pack.island=refs/heads/(.*)" repack -adfi \ + --path-walk 2>err && + test_region pack-objects path-walk trace.path-walk-islands && + test_grep ! "cannot use --delta-islands with --path-walk" err && + ! is_delta_base $one $two && + ! is_delta_base $two $one +' + +test_expect_success 'path-walk island bitmap repack respects islands' ' + GIT_TRACE2_EVENT="$(pwd)/trace.path-walk-island-bitmap" \ + git -c "pack.island=refs/heads/(.*)" repack -a -d -f -i -b \ + --path-walk 2>err && + test_region pack-objects path-walk trace.path-walk-island-bitmap && + test_path_is_file .git/objects/pack/*.bitmap && + git rev-list --test-bitmap --use-bitmap-index one && + test_grep ! "cannot use --delta-islands with --path-walk" err && + ! is_delta_base $one $two && + ! is_delta_base $two $one +' + +test_expect_success 'path-walk same island allows delta' ' + GIT_TRACE2_EVENT="$(pwd)/trace.path-walk-same-island" \ + git -c "pack.island=refs/heads" repack -adfi --path-walk && + test_region pack-objects path-walk trace.path-walk-same-island && + is_delta_base $one $two +' + test_expect_success 'same island allows delta' ' git -c "pack.island=refs/heads" repack -adfi && is_delta_base $one $two -- 2.54.0.4.g6aa0d38a4ec