Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve handling of self-referential strategies #2794

Closed
Stranger6667 opened this issue Jan 31, 2021 · 1 comment · Fixed by #2889
Closed

Improve handling of self-referential strategies #2794

Stranger6667 opened this issue Jan 31, 2021 · 1 comment · Fixed by #2889
Labels
bug something is clearly wrong here internals Stuff that only Hypothesis devs should ever see

Comments

@Stranger6667
Copy link
Collaborator

As mentioned in #2783, the following strategy is not explicitly forbidden but fails with an AssertionError:

from hypothesis import strategies as st

SELF_REF = st.recursive(
    st.deferred(lambda: SELF_REF | st.booleans()),
    lambda s: st.lists(s, min_size=1)
)

There is an alternative strategy that produces the same data, but doesn't fail the same way:

SELF_REF = st.recursive(
    st.booleans(),
    lambda s: st.lists(s, min_size=1)
)

I am not sure if all self-referential strategies can be rewritten like this, but probably we can either explicitly forbid such strategies or revisit our drawing approach for them.

Here is my reasoning from #2783

As far as I see, the cap is needed to prevent the drawing from this strategy & generating a certain maximum amount of leaves. However, assuming a single thread (more on the multi-threaded behavior in the next section) and such a self-referential strategy, I am not sure if capping is needed as it is - we can just apply it once on the first capped usage and make all subsequent calls no-op (e.g., just yield without modifying marked). Then we still have the marker set only once on the very first RecursiveStrategy.do_draw call, and it will be monotonically decreasing. Therefore, we'll have the max size properly maintained, and there will be no oversized subtrees because, at some point, LimitReached will occur.

@Stranger6667 Stranger6667 added internals Stuff that only Hypothesis devs should ever see opinions-sought tell us what you think about these ones! labels Jan 31, 2021
@Zac-HD
Copy link
Member

Zac-HD commented Jan 31, 2021

As an API design principle, any strategy should be acceptable wherever a strategy is needed - so I'd much rather make this work than specifically disallow some strategies. That wouldn't technically be a breaking change since it's never worked before, but IMO it should have worked.

Fortunately I think it should be reasonably easy to make the capping logic work for self-referential strategies; just remove the assertion and ensure we only un-set the cap if it was added by this draw (not an outer draw). Plus some tests to make me confident that I'm right 😅

@Zac-HD Zac-HD added bug something is clearly wrong here and removed opinions-sought tell us what you think about these ones! labels Feb 25, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug something is clearly wrong here internals Stuff that only Hypothesis devs should ever see
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants