Migrate our core representation to the typed choice sequence

[tybug]

This epic-style issue tracks our work on migrating the internals of Hypothesis from a bytestring to the typed choice sequence.

This is a huge change that touches every part of Hypothesis. The short version is that we have encountered several shortcomings of Hypothesis internals over time, which have limited the efficiency of input generation and shrinking, and made alternative backends infeasible. We expect this migration to give moderate efficiency gains and pave a clear path forward to future integration with alternative backends or other powerful features which are currently intractable.

Bytestring

Hypothesis currently works at the level of a bytestring (a sequence of bytes).

• To generate inputs, view strategies as a parser of the bytestring which interpret bytes as a series of random choices
• Store inputs in the db as their bytestring representation
• Shrink inputs by shrinking their corresponding bytestring ("internal shrinking").
• Generate novel inputs by generating a novel prefix of the bytestring (via DataTree internally) and randomly generating the remaining bytes.

But, the bytestring has its limitations.

• Redundancy. The mapping of bytes ↦ input is not injective, so an input may have many byte representations. For instance, 0 is represented by many different bytestrings, so any strategy using st.integers() effectively wastes some number of inputs (except for detecting flakiness). See also generate_novel_prefix interacts poorly with biased_coin (and lists) #1574.
• Precision. Effecting predictable changes in the input via changes in the bytestring is difficult, in e.g. shrinking. For instance, we would like to be able to "naturally" shrink floats, eg by exponentially ramping up division or truncation. Doing this in the byte representation is quite nasty. In fact, we currently hack around this by parsing bytes which look like they could represent floats into a float, shrinking that, and serializing it back into the bytestring.

These limitations extend equally to alternative backends over the bytestring. e.g. for CrossHair (#3086) integration, bytes is simply too low level to get an efficient SMT algorithm out of.

Typed Choice Sequence

Enter the typed choice sequence, which replaces the bytestring. We lift up the representation from bytes to a slightly higher representation at the level of five types: boolean, integer, float, string, and bytes.

class PrimitiveProvider(abc.ABC):
    @abc.abstractmethod
    def draw_boolean(
        self,
        p: float = 0.5,
    ) -> bool:
        ...

    @abc.abstractmethod
    def draw_integer(
        self,
        min_value: int | None = None,
        max_value: int | None = None,
        *,
        # weights are for choosing an element index from a bounded range
        weights: Sequence[float] | None = None,
        shrink_towards: int = 0,
    ) -> int:
        ...

    @abc.abstractmethod
    def draw_float(
        self,
        *,
        min_value: float = -math.inf,
        max_value: float = math.inf,
        allow_nan: bool = True,
        smallest_nonzero_magnitude: float,
    ) -> float:
        ...

    @abc.abstractmethod
    def draw_string(
        self,
        intervals: IntervalSet,
        *,
        min_size: int = 0,
        max_size: int | None = None,
    ) -> str:
        ...

    @abc.abstractmethod
    def draw_bytes(
        self,
        min_size: int = 0,
        max_size: int | None = None,
    ) -> bytes:
        ...

This improves redundancy (as DataTree operates at this higher level) and precision (as we retain type and shape information about what was previously spans of the bytestring). The end goal is rebuilding input generation, shrinking, targeted pbt, the explain phase, the database, etc on the typed choice sequence, and we expect to see performance gains in each (except the database).

Roadmap

Completed:

• initial refactorings
  • Move float, integer, string, byte, and boolean drawing logic into PrimitiveProvider #3788
  • Support forcing all primitives #3801
• Migrate DataTree to the new IR #3818
• Add support for crosshair backend #3806
• migrate Float shrinker to the ir #3899
• Migrate most shrinker functions to the ir #3962
• Remove sub-ir examples #4007 (+ migrate generate_mutations_from)
• Add support for variable-width bytes in the IR #4097
• Fold integer endpoint upweighting into weights= #4138
• Implement extend for cached_test_function_ir #4159
• Migrate explain phase to the typed choice sequence #4162
• Migrate Optimiser to the typed choice sequence #4163
• Migrate generate_novel_prefix to the typed choice sequence #4172

Future work, roughly in order of expected completion:

• finish lower_blocks_together in the shrinker
• migrate ParetoOptimiser
• define and use a shrink ordering for the ir
• migrate database to serialized ir

[JonathanPlasse]

This is super interesting!
Thank you for writing this detailed issue.
I would like to get involved with hypothesis.
What would constitute a good first contribution here?

[Zac-HD]

Welcome, Jonathan! We'd love to have you continue contributing - I already really appreciate the type-annotation-improvements for our numpy and pandas extras, so this would be a third contribution 😻

@tybug might have some ideas here, but my impression is that the "refactor for an IR" project in this issue is more-or-less a serialized set of tasks and so adding a second person is unlikely to help much - even with just one we've had a few times where there were two or three PRs stacked up and accumulating merge conflicts between them.

As an alternative, #3764 should be a fairly self-contained bugfix. On the more ambitious side, #3914 would also benefit from ongoing work on that - testing, observability, reporting whatever bugs you surface, etc. Or of course you're welcome to work on any other open issue which appeals to you!

[JonathanPlasse]

Thanks, I will start with #3764 and then take on the different issue on #3914.

[Zac-HD]

We may still use the bitstream representation for some things (database?).

I was thinking that we'd still serialize to a bytestring - that's the ultimate interop format, and when we need to handle weird unicode and floats like subnormals or non-standard bitpatterns for nan I don't want to trust whatever database backend our users cook up to round-trip correctly. Existing formats like protobuf or msgpack all have constraints like "unicode strings must be valid utf-8" or "numbers limited to bits", so I wrote a custom serializer instead 🙂

[tybug]

yeah, this is a hard one to parallelize 😄. Some of the steps may subtly depend on others in ways that aren't obvious until one is knee deep in implementing it.

so I wrote a custom serializer instead 🙂

Nice! I agree with the reasoning here. Added a task for this. This probably needs to be the absolute last thing to switch to the ir.

[Zac-HD]

Definitely the last thing to switch, I just got nerdsniped 😅

[tybug]

I'm working on migrating shrinker block programs. Our upweighting for large integer ranges is giving the shrinker trouble, because it means that a simpler tree can result in a longer buffer: the buffer runs through the weighted distribution and draws n bits from some small bucket, while the tree runs through the uniform distribution (as a result of forced=True) and draws m > n bits, where the difference in m and n is large enough that it offsets whatever simplification is made by the tree.

Real example of this:

b1 = b'\x01\x00\x01\x00\x00\x00\x01\x00\x01\x00\x00\x00\x01\x00\x01\x00\x00\x00\x01\x00\x01\x00\x00\x00\x01\x00\x01\x00\x00\x00\x00'
b2 = b'\x01\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00'
s = st.lists(st.integers(0, 2**40))

print("complex result, smaller buffer", ConjectureData.for_buffer(b1).draw(s))
# complex result, smaller buffer [0, 0, 0, 0, 0]
print("simpler result, larger buffer", ConjectureData.for_buffer(b2).draw(s))
# simpler result, larger buffer [0, 0, 0, 0]

As a result I'd like to look at moving that weighting logic into IntegerStrategy, which imo is where it logically belongs anyway, not at the ir layer. To accommodate this with weights, we'll need a structure that can express weights for entire ranges, not just "weight points and everything else is uniform". What do you think of weights=[(a, b, p), ...] where union((a, b), ...) == [min_value, max_value], sum(p) == 1, and len((a, b), ...) <= 255?

[Zac-HD]

What if we forced even more instead?

If we choose a smaller bits size, instead of drawing the main value from a narrower range we draw a value-to-force from the narrower range, and then force-draw it from the full range. The choice of fewer bits is then cleanly deletable without changing the interpretation of subsequent bits.

[tybug]

We could do that! I'm fairly confident exactly what you stated, or some small variation, would work.

I was thinking of killing two birds with one stone here, though. Do you think the upweighting belongs in the ir or in st.integers()? If we're going to move it out of the ir eventually anyway, I think now is the right time to do it, both while it's causing problems and we're changing the weights interface.

[Zac-HD]

I think doing it 'below' the IR, so we just represent a single integer value with a minimum of redundancy, is the principled approach here. "Literally just give me an integer" feels like it should be bijective 😅

[tybug]

The concern is that moving the weighting to st.integers() will result in drawing an integer correspond to more than one ir draw? I think we can avoid this via weights (and wouldn't want to move the weighting if we couldn't). I was thinking of something like this, where we combine the probability distributions upfront and pass it to weights. We wouldn't need to draw a boolean with p=7/8. Probability computations are pseudocode for whatever representation we use.

class IntegersStrategy(SearchStrategy):

    ...

    def do_draw(self, data):

        weights = None
        if self.end is not None and self.start is not None:
            bits = (self.end - self.start).bit_length()

            # For large ranges, we combine the uniform random distribution from draw_bits
            # with a weighting scheme with moderate chance.  Cutoff at 2 ** 24 so that our
            # choice of unicode characters is uniform but the 32bit distribution is not.
            if bits > 24:
                def weighted():
                    # INT_SIZES = (8, 16, 32, 64, 128)
                    # INT_SIZES_SAMPLER = Sampler((4.0, 8.0, 1.0, 1.0, 0.5), observe=False)
                    total = 4.0 + 8.0 + 1.0 + 1.0 + 0.5
                    return (
                        (4.0 / total) * (-2**8, 2**8),
                        # ...except split these into two ranges to avoid double counting bits=8
                        (8.0 / total) * (-2**16, 2**16),
                        (1.0 / total) * (-2**32, 2**32),
                        (1.0 / total) * (-2**64, 2**64),
                        (0.5 / total) * (-2**128, 2**128),
                    )
                weights = (
                    (7 / 8) * weighted()
                    + (1 / 8) * uniform()
                )

            # for bounded integers, make the near-bounds more likely
            weights = (
                weights
                + (2 / 128) * self.start
                + (1 / 64) * self.end
                + (1 / 128) * (self.start + 1)
                + (1 / 128) * (self.end - 1)
            )
            # ... also renormalize weights to p=1, or have the ir do that

        return data.draw_integer(
            min_value=self.start, max_value=self.end, weights=weights
        )

Now the ir draw_integer is truly uniform, but st.integers() keeps the same distribution as before.

[Zac-HD]

That would work! I'm also fine with the IR draw_integer remaining non-uniform above 24 bits, if that's easier.

[tybug]

I'm working on a native ordering for the IR (wip branch). My current plan is to have a bijective map ir_ordering: (value: IRType) <-> (order: int). The order depends on the kwargs of the node and order = 0 indicates the simplest value for that node.

This will replace some ad-hoc constructs:

• node.trivial becomes ir_ordering(node, to="index") == 0
• all_children becomes for i in range(compute_max_children(node)): yield ir_ordering(i, to="value")

We can also take advantage of this ordering as a unified representation to work over when convenient, just like the bytestring was. I plan to use this ordering to migrate Optimiser to the IR until/if we add ir-specific mutations, and to replace our shrinker misalignment logic, which currently uses the bytestring as an intermediary.

Two things:

• I'm very open to feedback on this structure or plan in general, though I'm also relatively confident in this plan in the absence of any feedback
• I have stopped work here at defining the ordering on floats (and likely won't return for a few weeks). This is our opportunity to redefine the ordering on floats, free from any shrinking or byte restrictions. I think there are some things here that don't make sense:

>>> sorted([0.01 * n for n in range(100)], key=float_to_lex)
[0.0, 0.5, 0.75, 0.8300000000000001, 0.54, 0.79, 0.71, 0.96, 0.52, 0.77, 0.56, 0.81, 0.73, 0.98, 0.51, 0.76, 0.72, 0.97, 0.55, 0.8, 0.53, 0.78, 0.74, 0.99, 0.5700000000000001, 0.8200000000000001, 0.59, 0.84, 0.67, 0.92, 0.63, 0.88, 0.61, 0.86, 0.6900000000000001, 0.9400000000000001, 0.65, 0.9, 0.68, 0.93, 0.6, 0.85, 0.64, 0.89, 0.7000000000000001, 0.9500000000000001, 0.62, 0.87, 0.58, 0.66, 0.91, 0.25, 0.27, 0.48, 0.26, 0.28, 0.49, 0.38, 0.36, 0.4, 0.39, 0.37, 0.41000000000000003, 0.42, 0.46, 0.44, 0.43, 0.47000000000000003, 0.45, 0.34, 0.3, 0.32, 0.35000000000000003, 0.31, 0.29, 0.33, 0.24, 0.13, 0.14, 0.19, 0.18, 0.2, 0.21, 0.23, 0.22, 0.17, 0.15, 0.16, 0.12, 0.07, 0.09, 0.1, 0.11, 0.08, 0.06, 0.05, 0.04, 0.03, 0.02, 0.01]
>>> 

like 0.54 < 0.1, and all of the last ~10 values not being smaller.

I guess a starting point is, how should we order [0, 1)? We don't have to go crazy with this – the ordering only has an impact insofar as the shrinker can intelligently match it¹, there are just too many floats – but @Zac-HD I'm curious if you've thought about a good ordering before 🙂. I'm tempted to say [0] + [0.1 * n for n in range(10)] + [0.05 * n for n in range(20)] + [0.025 * n for n in range(40)] + ... (ignoring duplicates), but I don't know how this would hold up against exponent/mantissa realities of floats.

Footnotes

1. I'm realizing that our ordering and shrinker are strongly decoupled in the IR, and to see benefits both need to be updated. There's no point to defining an intelligent and complicated ordering on floats if the shrinker never tries (ordering-)smaller floats. ↩

[Zac-HD]

• this plan sounds good to me overall
• I'd prefer having a pair of functions ir_node_to_index and ir_index_to_node rather than accepting a kwarg to specify the direction
• gosh, doing ~anything with floats is going to suck in some ways. I think trying to work with base-ten values is basically futile. Instead, I'd represent the float x as an improper fraction a + (b / 2**c) and shrink as for the tuple (c, b, a) - meaning integers are simplest, then multiples of a half, a quarter, an eighth, etc. The interval 0 .. 2 would then be, in increasing shrink order, 0, 1, 2, 1/2, 1+1/2, 1/4, 3/4, 1+1/4, 1+3/4, 1/8, .... This jumps around the number line a bit but is fairly well-behaved in the binary-representation space, and we can make the shrinker aware of a couple of different notions of locality as needed.

[tybug]

An update: we've steadily been working towards this goal over the past 6 months. The current status is that input generation and redundancy tracking (via DataTree) and the shrinking algorithm are comfortably on the typed choice sequence. What remains is moving the database and the definition of a "simpler" input (currently lexicographic ordering over bytes). While these two steps still encompass a substantial amount of work, we expect that most of the major complications involved in the migration have been solved.

The typed choice sequence has been incrementally worsening performance (#4076 (comment)) as we maintain two internal representations simultaneously. We expect this to improve roughly back to the status quo once Hypothesis is fully on the TCS. And it may well already be a wash due to the increased bug-finding power of the TCS (because of e.g. less duplication).