Generating an interval set in hypothesis

I have some code that works with intervals, which are really just python dicts with the following structure:

{
    "name": "some utf8 string",
    "start": 0.0,  # 0.0 <= start < 1.0
    "end": 1.0,    # start < end <= 1.0
    "size": 1.0,   # size == end - start
}

Writing a strategy for a single interval is relatively straightforward. I’d like to write a strategy to generate interval sets. An interval set is a list of intervals, such that:

• The list contains an arbitrary number of intervals.
• The interval names are unique.
• The intervals do not overlap.
• All intervals are contained within the range (0.0, 1.0).
• Each interval’s size is correct.
• The intervals do not have to be contiguous and the entire range doesn’t need to be covered.

How would you write this strategy?

Answer

I managed to get this working with the following strategies. This is almost certainly sub-optimal but does produce the desired object state.

import math
import sys

from hypothesis import strategies as st

@composite
def range_strategy(draw):
    """Produces start-end pairs within the 0.0–1.0 interval"""
    start = 0.0
    end = 1.0
    ranges = []

    while draw(st.booleans()):
        range_start = draw(st.floats(min_value=start, max_value=end, exclude_max=True)
        range_end = draw(st.floats(min_value=range_start, max_value=end, exclude_min=True)
        ranges.append((range_start, range_end))

        if math.isclose(range_end, end, abs_tol=sys.float_info.epsilon):
            # We hit the ceiling so we're done
            break
        start = math.nextafter(range_end, float("inf"))
    return ranges


@composite
def interval_set_strategy(draw):
    ranges = draw(range_strategy())
    intervals = st.just(
        map(
            lambda range: {
                "name": draw(st.text()),
                "start": range[0],
                "end": range[1],
                "size": range[1] - range[0],
            }
        ),
        ranges
    )

    return draw(st.builds(list, intervals))