Re: [PATCH 09/17] midx: do not require packs to be sorted in lexicographic order

[Patrick Steinhardt <ps@pks.im>]

On Sat, Dec 06, 2025 at 03:31:25PM -0500, Taylor Blau wrote:
> Note that this produces MIDXs which may be incompatible with earlier
> versions of Git that have stricter requirements on the layout of packs
> within a MIDX. This patch does *not* modify the version number of the
> MIDX format, since existing versions of Git already know to gracefully
> ignore a MIDX with packs that appear out-of-order.

Interesting. Did you verify how other implementations of Git behave if
we start to relax this requirement? It seems like a somewhat dangerous
assumption to me that this will just continue to work.

Also, is there a reason why you prefer this over bumping the version
number?

> @@ -656,17 +652,37 @@ 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]);
> +}
> +
>  static int midx_contains_pack_1(struct multi_pack_index *m,
>  				const char *idx_or_pack_name)
>  {
>  	uint32_t first = 0, last = m->num_packs;
>  
> +	if (!m->pack_names_sorted) {
> +		uint32_t i;
> +
> +		ALLOC_ARRAY(m->pack_names_sorted, m->num_packs);
> +
> +		for (i = 0; i < m->num_packs; i++)
> +			m->pack_names_sorted[i] = i;
> +
> +		QSORT_S(m->pack_names_sorted, m->num_packs, midx_pack_names_cmp,
> +			m);
> +	}
> +
>  	while (first < last) {
>  		uint32_t mid = first + (last - first) / 2;
>  		const char *current;
>  		int cmp;
>  
> -		current = m->pack_names[mid];
> +		current = m->pack_names[m->pack_names_sorted[mid]];
>  		cmp = cmp_idx_or_pack_name(idx_or_pack_name, current);
>  		if (!cmp)
>  			return 1;

I assume that it cannot happen that we append to the array of MIDX'd
packs after we have sorted. It would mean that the MIDX somehow changed
its representation or was amended to, which isn't possible.

Patrick