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

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.