Hypothesis: Simple test never stop?

[tahsmith]

The following example seems to never pass, using hypothesis-4.24.6 running with pytest-5.0.0.
Going back to hypothesis 4.9.0, same pytest, the test passes almost instantly.

This looks like a regression but unsure.

from hypothesis import given
import hypothesis.strategies as st


@given(x=st.one_of(st.just(0)
                   | st.just(1)),
       y=st.one_of(st.just(0)
                   | st.just(1)
                   | st.just(2)))
def test_x_y(x, y):
    assert True

See also a stack overflow q I asked https://stackoverflow.com/questions/56831605/why-does-my-simple-finite-hypothesis-test-never-stop

[hoefling]

Note that it is also reproducible with e.g. sampled_from:

s_leq_one = st.sampled_from((0, 1))
s_leq_two = st.sampled_from((0, 1, 2))

@given(x=s_leq_one, y=s_leq_two)
def test(x, y):
    ...

[Zac-HD]

We have an internal integer_range helper. This keeps generating random numbers with the correct number of bits until it gets one in the desired range... which means there is an unbounded number of ways to generate the two-bit number "2" ([3, 3, ..., 3, 2]). So the main slowdown is that Hypothesis is now smart enough to do just this, as it can tell that it's seen the shorter versions before. IMO this is an emergent problem that should be fixed by changing the implementation of integer_range.

Separately, this isn't so terribly slow if you only pass the y argument, but I'm not sure what's going on there. More details as I have them.

[DRMacIver]

This is a duplicate of #1864, which is fixed in #2030.

[tahsmith]

Although #1864 is fixed, my example still does not finish. I think this is a separate bug.

pytest, hypothesis config:

platform darwin -- Python 3.7.3, pytest-5.0.0, py-1.8.0, pluggy-0.12.0
hypothesis profile 'default' -> database=DirectoryBasedExampleDatabase(...)
rootdir: ...
plugins: hypothesis-4.26.2

Slightly simplified example without redundant one_ofs:

@given(x=st.just(0)
         | st.just(1),
       y=st.just(0)
         | st.just(1)
         | st.just(2))
def test_x_y(x, y):
    assert True

Also the example from hoefling still fails on 4.26.2

[Zalathar]

This also hangs on 622497c (4.26.2):

@given(
    x=st.integers(0, 1),
    y=st.integers(0, 2),
)
def test_x_y(x, y):
    assert True

[Zalathar]

Similar to #1864, the “hang” occurs in generate_novel_prefix, which ends up needing an increasingly-ludicrous number of retries (millions+) to find a novel prefix by chance.

[Zalathar]

This isn't solved by #2030, because generate_novel_prefix is effectively doing its own rejection sampling of candidate prefixes in a while True loop, separate from example-level rejection.

[DRMacIver]

On investigation, you're right (though it's not millions - that was true of the earlier version of this but the fact that we separate out finding the require prefix cuts out most of those), but it is hundreds. That's weird though - it shouldn't be possible for it to go that high because we only do rejection sampling on the first free block, which should almost never be that saturated. Will investigate what's going on.

[DRMacIver]

Will investigate what's going on.

Ah, I see what's going on now. I've made a wrong assumption there that the rejection sampling only fails at the first block. Effectively the problem in this test is that we end up with long forced sequences in the middle of the byte stream after the first free byte.