Repository navigation
RangeSet.Overlaps answers false on a continuous domain when the operand ends exactly where a later element begins #106
Description
RangeSet<TRange, T>.Overlaps(IRange<T>) — and Overlaps(RangeSet<TRange, T>), which delegates to it — answers false on a continuous domain when the operand's exclusive upper bound sits exactly on a later element's lower bound, although an earlier element shares values with it. PostgreSQL's && answers true.
var set = RangeSet<DecimalRange, decimal>.From([DecimalRange.CreateFinite(1, 4), DecimalRange.CreateFinite(5, 8)]);
// {[1,4),[5,8)}
set.Overlaps(DecimalRange.CreateFinite(3, 5)); // false — shares [3,4) with the first element
set.Overlaps(DecimalRange.CreateUnboundedStart(5, false)); // false — (,5) covers the whole first element
set.Overlaps(RangeSet<DecimalRange, decimal>.From([DecimalRange.CreateFinite(3, 5)])); // false
set.Intersect(DecimalRange.CreateFinite(3, 5)); // {[3,4)} — the right answer, from the same setSELECT '{[1,4),[5,8)}'::nummultirange && '[3,5)'::numrange, -- t
'{[1,4),[5,8)}'::nummultirange && '(,5)'::numrange, -- t
'{[1,4),[5,8)}'::nummultirange && '{[3,5)}'::nummultirange; -- tMeasured on main (7f4dc47) against PostgreSQL 17.11. Through EF Core the same query gives memory false, server true for r.Bands.Overlaps(DecimalRange.CreateFinite(3, 5)) on a nummultirange column holding that set — the translation (&&) is right, so the disagreement is between memory and the database, the hard-to-notice kind.
Cause (src/CodoMetis.ValueRanges/RangeSet.cs, Overlaps(IRange<T>)): the method binary-searches for the last element whose lower bound is at or below the operand's upper bound and tests only that candidate. The comment argues that if the candidate doesn't overlap, no earlier element can. That holds when the candidate lies entirely left of the operand, but not when the candidate starts at the operand's upper bound and one side is exclusive: then the candidate doesn't overlap, yet the element before it may. On a discrete domain the canonical closed form makes the case unreachable (an operand [3,5) becomes [3,4], and the candidate is then [1,4]), which is why neither SmallModelMultirangeOracleTests (discrete) nor ContinuousMultirangeParityTests (+, -, *, complement — no predicates) caught it.
A randomized differential run (200,000 random DecimalRange sets and operands, every RangeSet operation against a per-element naive answer) fails only Overlaps(range) and Overlaps(set); Contains, Intersect, Union, Except, Complement, parse round trip, Equals/GetHashCode and the invariant all agree. Contains(IRange<T>) uses the same binary search, but there the candidate choice is sound: an earlier element containing the operand would overlap or be adjacent to the candidate.
Fix (10.0.0): when the candidate at index i doesn't overlap and i > 0, also test element i - 1 (that is the only other element that can share values, because elements are disjoint and non-adjacent). It changes an answer queries return today, so it's a 10.0.0 fix under the release rule.
Tests: add a continuous shape sweep for the multirange predicates (&&, @>, <@, -|-, <<, >>, &<, &>) against nummultirange, beside ContinuousMultirangeParityTests, which today sweeps only the algebra. Seed the fix by reverting it and keep the seed under test/oracles/seeds/.
Found in the 10.0.0 bug hunt. No oracle sweep found it (a hand-written differential did), so no found-by/oracle.
Activity
CaffeinatedCoder commentedon Oct 17, 2026
Second measurement, directly against PostgreSQL 17.11: 600 random
RangeSet<DecimalRange, decimal>operands paired with a random range and with a random set (1,200 rows), every multirange predicate (@>,&&,-|-,<<,>>,&<,&>),=, the algebra (*,+,-),range_merge,isempty,lower_inf,upper_inf, and theIsInfinity/IsFiniteforms, memory versus server.Only
&&disagrees: 13 of 1,200 rows, all of the shape described above. One set-versus-set example, sinceOverlaps(RangeSet)probes with the smaller set and so hits the same candidate choice from the other side:Everything else agreed on every row, so the fix is contained to
Overlaps(IRange<T>).CaffeinatedCoder commentedon Oct 17, 2026
The differential fuzzing sweep (#104,
DifferentialFuzzParityTests) finds this one independently. At the default seed and 200 rows per type it hitsOverlaps(range)andOverlaps(set)onDecimalRange,DateTimeRange,DateTimeOffsetRangeandLocalDateTimeRange. At 2,000 rows it also hitsInstantRangeandTimeRange, so every continuous type is affected. It shows through a column, an inlined constant and a parameter alike. Memory answersfalse; EF Core and PostgreSQL on the literals both answertrue. The sweep's rows are registered as candidates against this issue intest/oracles/candidates.json(family RangeSet.Overlaps skips the element before the candidate). The fix's PR removes them. Itscandidate fixedfailure says which ones.CaffeinatedCoder commentedon Oct 17, 2026
Test-gap evidence for the fix's test, measured by seeding on a scratch clone of main: with the
RangeSet.Overlapstranslation changed from&&to@>, the live-PostgreSQL integration suite (149 tests) and the conventions suite stayed green; only the two SQL-text testsRangeSet_OverlapsandRangeSet_Overlaps_SetinQueryTranslationTestsfailed. The executed cases use a disjoint operand (ExecutedQueryTests,OverlapsDisjoint) or a discrete probe (MultirangeCoverageTests), neither of which can tell&&from@>.Claim E02 (
predicates-translate-to-operators) listsContinuousMultirangeParityTestsamong its holders, which overstates it: that sweep covers+,-,*and the complement, not the predicates. The continuous predicate sweep proposed above should become a holder of E02 and of theRangeSet.Overlapssurface, with this seed kept undertest/oracles/seeds/.CaffeinatedCoder commentedon Oct 17, 2026
Oracle check (main at 3ecfa10): Would be caught today (retroactive; a hand-written differential found it, not an oracle) by
DifferentialFuzzParityTests(Ranges_AgreeWithPostgres), through the candidate rows> Overlaps(range)and> Overlaps(set).Verified by a run on 3ecfa10. At the default seed, 8 lines report
SKIPPED [known candidate, #106]acrossDecimalRange,DateTimeRange,DateTimeOffsetRangeandLocalDateTimeRange, through column, constant and parameter. The fuzz sweep samples, so it catches this by chance rather than by construction. No continuous predicate sweep exists, and claim E02 namesContinuousMultirangeParityTestsas a holder, which it is not (#134).CaffeinatedCoder commentedon Oct 18, 2026
Fixed in #167 (
fix/rangeset-overlaps-previous-element, 10.0.0). What is now true:RangeSet.Overlaps(IRange<T>)picks the last element that starts before the operand ends (lower bound below the upper bound, or at it when both are inclusive), so{[1,4),[5,8)}.Overlaps([3,5)),.Overlaps((,5))and.Overlaps({[3,5)})aretrue, as&&is.Contains(IRange<T>)keeps the value-only search, whose key is the operand's lower bound.ContinuousMultirangeParityTestsnow holds the predicate half claim E02 named it for: every ordered pair of the 64 subsets through@>,&&,<<,>>,&<,&>,-|-, and every subset against 19 single ranges (8,512 rows). With the fix reverted it reports 132Overlapsrows; the seedrangeset-overlaps-skips-previous-elementkeeps that revert and is caught by it and byDifferentialFuzzParityTests.docs/migration.md(Check RangeSet.Overlaps on a continuous element type) carry it.