git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[RFC PATCH 7/7] pack-objects: support `--delta-islands` with `--path-walk`

From
Taylor Blau <me@ttaylorr.com>
Date
May 4, 2026, 00:11 UTC
Message-ID
<0a1a9ed1e3c8f883587800c232e504937d706bc0.1777853408.git.me@ttaylorr.com>
In-Reply-To
<cover.1777853408.git.me@ttaylorr.com>

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 <me@ttaylorr.com>
---
 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=<spec>` forms `blob:none`, `blob:limit=<n>`,
-`sparse:oid=<blob>`, `tree:0`, `object:type=<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=<spec>` forms `blob:none`,
+`blob:limit=<n>`, `sparse:oid=<blob>`, `tree:0`, `object:type=<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
Previous: Taylor BlauNext: Derrick Stolee
Message 12 of 13 in “pack-bitmap: resolve various `--path-walk` incompatibilities”
  1. 0/7 pack-bitmap: resolve various `--path-walk` incompatibilitiesTaylor Blau, May 4, 2026
  2. 1/7 pack-objects: update `--path-walk`'s existing incompatibilitiesTaylor Blau, May 4, 2026
  3. Derrick StoleeMay 4, 2026
  4. 2/7 path-walk: support `tree:0` filterTaylor Blau, May 4, 2026
  5. Derrick StoleeMay 4, 2026
  6. Kristoffer HaugsbakkMay 4, 2026
  7. 3/7 path-walk: support `object:type` filterTaylor Blau, May 4, 2026
  8. Derrick StoleeMay 4, 2026
  9. 4/7 path-walk: support `combine` filterTaylor Blau, May 4, 2026
  10. 5/7 pack-objects: support reachability bitmaps with `--path-walk`Taylor Blau, May 4, 2026
  11. 6/7 pack-objects: extract `record_tree_depth()` helperTaylor Blau, May 4, 2026
  12. 7/7 pack-objects: support `--delta-islands` with `--path-walk`Taylor Blau, May 4, 2026
  13. Derrick StoleeMay 4, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.