Breaking change from 1.0.1 to 1.0.2 in gaps()

[luukvanderduim]

Commit 9d0b125 may have introduced a bug in another project and is likely a breaking change.

Psst (a Spotify client) is a user of RangeSet and it has a bug jpochyla/psst#301 that is evoked by the changes made in version v1.0.2 of rangemap but not by v1.0.1. Bisecting lead to 9d0b125 as the commit that introduced the problem.

In order to see what behavior changed in rangemap, I copied (~30) tests from map to set as RangeSet is used in Psst.
Then I copied all set tests to the v1.0.1 commit too and found one test that fails in v1.0.1, but passes in v1.0.2:

    #[test]
    fn empty_outer_range_with_items_away_from_both_sides() {
        let mut range_set: RangeSet<u32> = RangeSet::new();
        // 0 1 2 3 4 5 6 7 8 9
        // ◌ ◆---◇ ◌ ◌ ◌ ◌ ◌ ◌
        range_set.insert(1..3);
        // 0 1 2 3 4 5 6 7 8 9
        // ◌ ◌ ◌ ◌ ◌ ◆---◇ ◌ ◌
        range_set.insert(5..7);
        // 0 1 2 3 4 5 6 7 8 9
        // ◌ ◌ ◌ ◌ ◆ ◌ ◌ ◌ ◌ ◌
        let outer_range = 4..4;
        let mut gaps = range_set.gaps(&outer_range);
        // Should yield a gap covering the zero-width outer range.
        assert_eq!(gaps.next(), Some(4..4));
        // Gaps iterator should be fused.
        assert_eq!(gaps.next(), None);
        assert_eq!(gaps.next(), None);
    }

Which fails like so:

    ---- set::tests::empty_outer_range_with_items_away_from_both_sides stdout ----
    thread 'set::tests::empty_outer_range_with_items_away_from_both_sides' panicked at 'assertion failed: `(left == right)`
      left: `None`,
     right: `Some(4..4)`', src/set.rs:789:9
    note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

The 1.0.2 version says, yes the empty outer range can contain a gap, being the empty range itself.
However 1.0.1 disagrees.

Looking at the definition of ranges in std::ops::Range:

The range start..end contains all values with start <= x < end. It is empty if start >= end.

I would argue that 1.0.1 is correct as when the range's start is equal to end, it contains all values start <= x < start and the 'gap' x cannot be both smaller than start and greater than or equal to start.

[jeffparsons]

Thanks for the detailed report, @luukvanderduim!

I've just released version 1.0.3 with this issue fixed.

[luukvanderduim]

Awesome! It looks like fixing this also fixed Psst!

[luukvanderduim]

It looks like the test mentioned earlier still fails on RangeSet.
For convenience I added a PR with all the test I thought to be relevant to set.

[jeffparsons]

Huh... that's odd. I will pull your branch and take a look when I get a chance — might be a couple of days though. Hopefully the test itself is wrong! 🤞

[jeffparsons]

@luukvanderduim I had a look at the failing test on your branch, and it seems to me that the problem is with the test. I already fixed the definition of that test upstream here: c56ec88#diff-110e61eb735b79c762510f02f157a12094bcf2b9a15d2ed767532a0e3d5f7bafL1122 before releasing version 1.0.3.

I don't think I'll merge the PR, by the way, because RangeSet is little more than a thin wrapper around RangeMap where the value type is () (just like std::collections::BTreeSet is a thin wrapper around BTreeMap). I.e. the tests won't be testing anything interesting on BTreeSet because it's all the same logic that it's testing.

If you're convinced, I'll close this again and also close #49.

[luukvanderduim]

Oh dear. I clearly wasn't thinking. I see what you mean, of course the test is wrong. Sorry about the noise and thanks for your swift responses!
I will remove the PR!

I like what you did simplifying the gaps iterator. In Psst, with rangemap 1.0.2, it ended up returning ranges where start > end it appears. I suspect that had something to do with the peekable in Gaps. I tried to isolate a case, but could not unfortunately as that would have helped test coverage.

[luukvanderduim]

Yay! A test case that fails on a rangemap tree at commit 92c5030 (v1.0.2) that has method gaps() yield a 'start > end'-range, where it should have returned None. This is what actually bit Psst, (but is fixed in rangemap 1.0.3,) but is not covered by any existing test.

You might want to consider adding this test (or a generalized version of this case) to prevent a future re-occurrence.

   #[test]
   fn outer_range_has_rangemap_return_start_greater_than_end_gaps() {
       let mut range_set: RangeSet<u64> = RangeSet::new();
       let outer_range: Range<u64> = 6110..268254;

        range_set.insert(144..327828);
        range_set.insert(6092380..6157916);

        let mut gaps = range_set.gaps(&outer_range);

        assert_eq!(gaps.next(), None);
   }

Which fails like this on 1.0.2:

---- set::tests::outer_range_has_rangemap_return_start_greater_than_end_gaps stdout ----
thread 'set::tests::outer_range_has_rangemap_return_start_greater_than_end_gaps' panicked at 'assertion failed: `(left == right)`
  left: `Some(327828..268254)`,
 right: `None`', src/set.rs:381:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Weird huh?