Re: [PATCH v2 10/18] midx: do not require packs to be sorted in lexicographic order

From: Taylor Blau <me@ttaylorr.com>
Date: Feb 24, 2026, 18:47 UTC
Message-ID: <aZ3yQ7D54jcyQhLY@nand.local>
In-Reply-To: <aXhqo3f-NeUcO2IM@pks.im>

On Tue, Jan 27, 2026 at 08:34:59AM +0100, Patrick Steinhardt wrote:

Show 10 quoted lines

> On Wed, Jan 14, 2026 at 02:54:45PM -0500, Taylor Blau wrote:
> [snip]
> > Because this change produces MIDXs which may not be correctly read with
> > external tools or older versions of Git. Though older versions of Git
> > know how to gracefully degrade and ignore any MIDX(s) they consider
> > corrupt, external tools may not be as robust. To avoid unintentionally
> > breaking any such tools, guard this change behind a version bump in the
> > MIDX's on-disk format.
>
> s/Because t/T/?

Nice spotting, thank you.

Show 8 quoted lines

> > @@ -105,6 +108,8 @@ struct write_midx_context {
> >
> >  	uint32_t preferred_pack_idx;
> >
> > +	int version; /* must be MIDX_VERSION_V1 or _V2 */
>
> Tiny nit: this could be converted into an `enum` for implicit
> documentation.

I wrote it this way initially, but ended up dropping the type down to "int" because the enum values named "_V1" and "_V2" would have integral values of "1", and "2", respectively.

Show 25 quoted lines

> > diff --git a/midx.c b/midx.c
> > index 19ef230d3fd..1327d0a3695 100644
> > --- a/midx.c
> > +++ b/midx.c
> > @@ -656,17 +658,40 @@ int cmp_idx_or_pack_name(const char *idx_or_pack_name,
> >  	return strcmp(idx_or_pack_name, idx_name);
> >  }
> >
> > +
> > +static int midx_pack_names_cmp(const void *a, const void *b, void *m_)
> > +{
> > +	struct multi_pack_index *m = m_;
> > +	return strcmp(m->pack_names[*(const size_t *)a],
> > +		      m->pack_names[*(const size_t *)b]);
> > +}
>
> Okay, this took a second to figure out. The `pack_names_sorted` is an
> array of `size_t` indexes into `m->pack_names`. So what we get here are
> these indices, and we can compare by using those indices via
> `m->pack_names`. Makes sense.
>
> I was wondering whether this would be easier to follow if
> `pack_names_sorted` was a simple array of unowned pointers. So it would
> contain the same pointers as `pack_names`, but properly sorted. It would
> have the downside of more confusing ownership semantics though.

Exactly. For that reason, I generally prefer holding onto a permutation array (of indices) rather than a permuted form of the existing array. The ownership of the former is unambiguous, but the latter is IMHO not.

> I assume we cannot live with a simple `bool sorted` field and then sort
> `pack_names` lazily?

Unfortunately not, because the pack_names array is indexed by the pack_int_id, which we have to preserve.

Thanks, Taylor