Re: [PATCH 2/4] pack-objects: ensure tree/tag closure with '--stdin-packs=follow'

[Jeff King <peff@peff.net>]

On Thu, Oct 01, 2026 at 07:51:48PM -0500, Taylor Blau wrote:

> On Thu, Oct 01, 2026 at 04:22:11PM -0700, Elijah Newren wrote:
> > With the oid_array and parent-first pack order, the blobs are visited
> > as sub/a and sub/b, so sub/* -delta applies. With the oidset, the
> > subtree is visited first and the blobs are seen as a and b, so one is
> > delta-compressed. When the root is processed later, the subtree is
> > already marked SEEN and is not revisited with the sub/ prefix.
> >
> > The oid_array does not manufacture parent-before-child ordering if the
> > input pack itself has the subtree first; this path information is
> > explicitly best-effort. But it preserves a useful order when one
> > exists, whereas an oidset discards it.
> 
> Sure, though as Peff and I discussed elsewhere in the thread, there are
> also situations where you can produce a sub-optimal pack even with
> oid_array. That's because the namehash you get for a given tree object
> depends on the path you took to get there.
> 
> So you can certainly come up with examples where the ordering of tree
> objects in an array of extra roots produces a lesser-quality delta
> selection than the same objects permuted into some different order.

Hmm. Yeah, it is not a 100% solved issue, for sure, but I think Elijah
has a point. Even though yes, we may see trees in weird orders between
packs, or when visited separate from another commit, the ordering in a
single pack _is_ useful, because it puts root trees before subtrees.

So even though these are a few objects we're rescuing out of a cruft
pack, we'd expect them to be correlated. E.g., an update to "a/b/c/file"
is going to have four trees: the root, a, a/b, and a/b/c. And we'd like
to visit them in that order. Which is the order in which we'd typically
write them in a pack.

One thing I'm not 100% on is if that "typically" qualifier applies to
cruft packs. We might be throwing objects in there with a little less
thought, because the point is that they're _not_ reachable, and we
didn't get there from a traversal. So I dunno.

> The other thing to keep in mind is that, while there are clearly
> trade-offs as we have discussed here, the oidset ensures that we don't
> allocate memory wastefully when the same object is listed multiple times
> as an extra root.

Yeah, that was my thinking when endorsing the oidset earlier; it is
better bounded. It can have worse memory use in practice, though,
because it's a hash table rather than a vanilla array. So if we don't
expect a lot of duplicates, then the simpler array may be more
efficient.

-Peff