]> git.ipfire.org Git - thirdparty/git.git/commit
pack-bitmap: fix inverted binary search in `pseudo_merge_at()`
authorTaylor Blau <me@ttaylorr.com>
Tue, 12 May 2026 00:46:57 +0000 (20:46 -0400)
committerJunio C Hamano <gitster@pobox.com>
Tue, 12 May 2026 01:36:18 +0000 (10:36 +0900)
commitb1e3fcdb9b087b4d69836dd5a228648008ff419a
treeea4112e24d163894d661b8327267ddfc53986dcf
parentff21343a597cfa5d6cc5ea463f5941644d9bf754
pack-bitmap: fix inverted binary search in `pseudo_merge_at()`

The binary search in `pseudo_merge_at()` has its "lo" and "hi" updates
swapped: when the midpoint's offset is less than the target, it sets `hi
= mi` (searching left) instead of `lo = mi + 1` (searching right), and
vice versa.

This means that lookups for pseudo-merges whose offset is not near the
midpoint of the pseudo-merge table are likely to fail.

In practice, with a single pseudo-merge group this is masked because the
lone entry is always at the midpoint. With multiple groups, the inverted
comparisons cause lookups to search in the wrong direction, potentially
missing entries.

Swap the "lo" and "hi" assignments to search in the correct direction,
making it possible to apply pseudo-merges during fill-in when more than
one pseudo-merge exists in a group.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
pseudo-merge.c
t/t5333-pseudo-merge-bitmaps.sh