HypothesisWorks / hypothesis

Hypothesis is a powerful, flexible, and easy to use library for property-based testing.
https://hypothesis.works
Other
7.39k stars 578 forks source link

Implement `LazySequenceCopy.pop(i)` #3987

Closed tybug closed 1 month ago

tybug commented 1 month ago

UniqueSampledListStrategy uses LazySequenceCopy to pop elements from the list. Because LazySequenceCopy only implemented pop-from-end, we swapped the element we wanted to pop to the end before popping. But this leaves the list in a bad state for shrinking: if i = 0, we just swapped the last element, which is the most complicated in shrinking order, to the front of the list, leaving it there for future passes. This means an ir tree of [0, 0, 0] indicating the first three elements of the sequence corresponds to {0, 8, 9} for sets(range(10)).

The solution is properly implementing .pop(i). I've applied this in other places we use the swap trick, though I'm less confident than UniqueSampledListStrategy that this is not a behavioral change.

Zac-HD commented 1 month ago

Looks like we're no longer triggering the KeyError case from our conjecture-coverage tests: https://github.com/HypothesisWorks/hypothesis/blob/4e77eea09b7867e1283f27b5b097cd0407d981b1/hypothesis-python/src/hypothesis/internal/conjecture/engine.py#L379-L382

tybug commented 1 month ago

that coverage was hopefully fixed in #3991. I've rebased on master, let's see how it goes