hashsig: the similarity heap evicts but never inserts, so the retained set is not the extremes #7375

What

hashsig_heap_insert (src/libgit2/hashsig.c:114-129) never inserts once the heap is full. The
branch commented "pop top if new element should replace it" pops the root and discards val:

	/* if heap is full, pop top if new element should replace it */
	else if (h->cmp(&val, &h->values[0], NULL) > 0) {
		h->size--;
		h->values[0] = h->values[h->size];
		hashsig_heap_down(h, 0);
	}

val is never stored. The eviction is correct; the replacement is missing.

The knock-on is that the heap drops to 126 and the branch above it then admits the next run hash
unconditionally, whatever it is, because h->size < h->asize is true again. So for any file with
more than HASHSIG_HEAP_SIZE runs, a qualifying value is swapped for an arbitrary one, repeatedly,
and the retained set is not the 127 extremes the comparison assumes.

Two visible consequences:

1. The signature is order-dependent. A min-hash over a multiset should not depend on the order
   the elements arrive in; this one does, because which values survive is decided by what happens to
   follow a qualifying value.
2. git_hashsig_compare can take the wrong branch. It tests a->mins.size < HASHSIG_HEAP_SIZE
   to decide between comparing one heap and averaging two. With the bug the final size is 126 or 127
   depending on whether the last qualifying insert happened to be followed by another run, so two
   large files can be compared by different rules. I see both values in practice — 126 for one
   512 KB fixture, 127 for its neighbours.

How I measured it

I am a downstream consumer (via git2 0.20 / libgit2-sys 0.18.3, libgit2 1.9.2; the file is
byte-identical on main today). I ported hashsig_add_hashes and the heap into Rust so I could
compare libgit2's own score against an ideal 127-sample min-hash over the same run hashes.

The port reproduces libgit2's score exactly on all 96 cells of a sweep — binary and text
content, 1 KB to 8 MB, one byte / 0.1% / 1% of bytes edited, against the index and against the
working tree — which is what makes the numbers below attributable to the heap rather than to my
reimplementation. libgit2's score is recovered by binary-searching rename_threshold on a real
repository until the pair stops being reported as GIT_DELTA_RENAMED.

ideal is the same algorithm with the three lines below applied; nothing else differs.

The error grows with the number of runs, which is what the mechanism predicts: below 127 runs the
buggy branch never executes and the two agree. Worst gap measured: 24 points.

In fairness: in this sweep the error never by itself flipped a verdict at the default 50%
threshold — the 0.1% rows are above it either way and the 1% rows below it either way — and it is
not always pessimistic (one 1 MB truncation fixture scores 53 from libgit2 against 47 ideal). What I
can say is that it is a 24-point error on a 100-point scale read against a 50-point threshold.

Suggested fix

The usual replace-root-and-sift-down:

	else if (h->cmp(&val, &h->values[0], NULL) > 0) {
		h->values[0] = val;
		hashsig_heap_down(h, 0);
	}

A black-box test that discriminates

Build a buffer A with well over 127 runs. Compute its true 127 smallest and 127 largest run
hashes, then build B by editing only bytes in runs whose hashes are in neither set. A correct
min-hash scores A against B at 100, because every sampled extreme is untouched. The current code
scores lower, because its retained set contains values that are not extremes.

Like #7349, this changes the signatures computed for existing content, and therefore the
similarity scores and rename-detection results that follow from them.