Hypothesis: Stuck in a loop forever when shrinking with targeted property-based testing

[ksaaskil]

Hi, thanks for the awesome library! I'm trying to wrap by head around hypothesis.target so I tried playing with an artificial example. The test generates floats smaller than a threshold value and it's expected to fail when the float is close enough to the magic value 42.5. Targeting works fine here as in many cases it can find the problematic value when non-targeted generation cannot.

However, sometimes it gets stuck in a loop forever. Here's an example that gets stuck in my case:

from hypothesis import given, target, settings, Phase, Verbosity, seed
import hypothesis.strategies as some
import math

@given(d=some.floats().filter(lambda x: abs(x) < 1000))
@settings(
    max_examples=1000,
    verbosity=Verbosity.debug,
    phases=[
        Phase.generate,
        Phase.target,
        Phase.shrink,
    ],  # Skip Phase.reuse to not run previous counter-examples
)
@seed(93962505385993024185959759429298090872)
def test_targeting_square_loss(d):
    """
    Contrived example of targeting properties.
    Disabling Phase.target or removing `target(-loss)` will most likely make the test pass.
    """
    # Assume this value triggers a bug
    target_value = 42.5

    should_fail = abs(d - target_value) < 0.5

    if should_fail:
        print("Failing with value {}".format(d))
        raise Exception("Critically close to {}, got {}".format(target_value, d))

    # Target the value
    loss = math.pow((d - target_value), 2.0)
    target(-loss)

The verbose printing keeps printing lines such as:

Shrink pass profiling
---------------------

Shrinking made a total of 0 calls of which 2 shrank. This deleted 0 bytes out of 11.

Useful passes:


Useless passes:


block_program('XXX')
...

I'm using Hypothesis 5.8.3 and running the test in pytest. I know the test is contrived, but I'm mostly wondering why it gets stuck.

EDIT: I'm exaggerating that it would be stuck forever, I stopped waiting after a minute or so :)

[DRMacIver]

Thanks for the bug report! I've got a hunch as to what might be going on here - we've got a bit at the end which uses shrinking to try to find minimized versions of each target score, and I suspect it's getting over eager in terms of how much work it's doing. I'll take a look into this today.

[Zalathar]

My guess is that if a failure is found during pareto_optimise, the example limits in test_function get implicitly switched off, so there's nothing preventing the optimizer from running for way too long.

(I had recently noticed this as a theoretical problem, but wasn't sure if it could happen in practice.)

[DRMacIver]

My guess is that if a failure is found during pareto_optimise, the example limits in test_function get implicitly switched off, so there's nothing preventing the optimizer from running for way too long.

This was also one of my guesses when looking into it, but it turns out that it's actually a genuine infinite loop. It's confusingly hard to trigger through "nice" tests, but it's obviously a potential problem once I looked in the right place. PR incoming shortly.

[DRMacIver]

Ah, attempting to explain in the PR why we're not hitting this bug all the time let me figure out what's actually going on. It's a problem with the fact that the pareto front is approximate. If we shrink something in the pareto front to something that ~was already in the pareto front~ dominates it without triggering an eviction then this can cause us to get stuck.