Hypothesis: IndexError in OneOfStrategy.do_draw (intermittent)

[mulkieran]

You can see the trace in the Travis CI here: https://travis-ci.org/stratis-storage/hs-dbus-signature/jobs/418270565.

The source is available here: https://github.com/mulkieran/hs-dbus-signature/tree/master-hypothesis-2.

The interesting method is here: https://github.com/mulkieran/hs-dbus-signature/blob/master-hypothesis-2/tests/test_strategy.py#L107 and it is short but weird.

Essentially, I wrote a strategy for generating arbitrary instance of the strategy that this is testing. I draw from that strategy to get a strategy to test, and then I draw from the particular strategy being tested to try to demonstrate that every strategy will at least yield some values. The strategy itself is built using the recursive strategy, which explains the depth of the stack trace.

If there is a better way to test that any strategy will at least yield something please let me know.

If this index error is actually demonstrating that one strategy has been found that does not yield any elements that would be cool, too.

Occurs under coverage but also not under coverage, and not consistently under either, but always in OneOfStrategy.

Occurs when code is this as well

    @given(strategies.data(), dbus_signature_strategy())  # pylint: disable=no-value-for-parameter
    @settings(max_examples=50)
    def testNoBlacklist(self, data, strategy):
        """
        Just make sure there is a result for an arbitrary legal strategy.
        """
        # pylint: disable=no-value-for-parameter
        data.draw(strategy)

[mulkieran]

Using example() as I was previously doing seems to have had much the same effect: https://travis-ci.org/stratis-storage/hs-dbus-signature/jobs/414712665.

[mulkieran]

Travis tests are still at Python 3.4, but the problem is also in Python 3.6.6 as it is reproducible on my home machine.

[DRMacIver]

Huh. That definitely shouldn't be possible.

I'm afraid I have zero time to investigate in the next week-ish. Happy to field questions if anyone else wants to though. My guess based on eye balling the code is that it's probably a bug in Sampler from hypothesis.internal.conjecture.utils. I guess first question is to confirm which index is out of bound and why.

[mulkieran]

I have an example where i is 2 and both arrays have length 2.

The original strategy is:

builds(<function str.join>, lists(elements=recursive(sampled_from(['b', 'd', 'g', 'h', 'i', 'n', 'o', 'q', 's', 't', 'u', 'v', 'x', 'y']), lambda children: struct_fun(children) | array_fun(children) | dict_fun(children), max_leaves=8), min_size=5))

Anyone would think this could be obtained by calling:
dbus_signatures(max_codes=8, min_complete_types=5)
but, alas, it repeatedly does not get the IndexError with that signature strategy specified.

[mulkieran]

dbus_signature_strategy, the function that returns the strategy that generates the signature strategies is a composite strategy, and I'm getting to thinking that that is the source of the problem.
I think I can probably go farther with at least trying to eliminate that as the source of the problem.

[DRMacIver]

but, alas, it repeatedly does not get the IndexError with that signature strategy specified.

Is it possible that the error is coming from the strategy that generates those strategies rather than the strategy itself?

[mulkieran]

I think we have the same idea. I'll try to follow it up some more tomorrow.

[mulkieran]

Sorry, "tomorrow" has become "just as soon as I can manage".

[Zac-HD]

Hey, @mulkieran - I think I've tracked this down to a bug in OneOfStrategy, where if bias is not None the sampler might be operating off the pre-flattened list of strategies. That's usually shorter, but could be longer and thus raise an IndexError. I haven't written a good regression test yet, but if you want to try out the fix feedback would be great:

https://github.com/HypothesisWorks/hypothesis/compare/master...Zac-HD:oneof-indexerror

[Zac-HD]

Got it; this does indeed fix it. If the extend function in recursive(...) returns a one_of with some strategy appearing in multiple positions, that could trigger the error above. This in turn could happen when two or more of the array/dict/struct options were disabled, iff max_codes was also >= 8.

The minimal reproducer is simply recursive(none(), lambda x: x | x)

Fix incoming!

[mulkieran]

Ok! Thanks for finding this.