from_type() does not resolve forward references outside of function annotations

[desmond-dsouza]

The sample code:

import typing as T

import hypothesis as H
import hypothesis.strategies as S

class Tree(T.NamedTuple):
    val: int
    l: T.Optional["Tree"]
    r: T.Optional["Tree"]
    def size(self):
        return 1 + (self.l.size() if self.l else 0) + (self.r.size() if self.r else 0)

@H.given(t = S.infer)
def test_tree(t: Tree):
    if t.size() > 3:
        assert False
        H.note(t)
    else:
        assert True

(Part of) the stack trace:

platform darwin -- Python 3.6.1, pytest-3.2.1, py-1.4.34, pluggy-0.4.0
rootdir: /Users/desmond/Documents/code/code-python/Try1/tests, inifile:
plugins: xonsh-0.5.12, hypothesis-3.38.9
collected 4 items
foo_test.py ...F
foo_test.py:36 (test_tree)
args = (<class 'foo_test.Tree'>,), kwargs = {}, kwargs_cache_key = set()
cache_key = (<function from_type at 0x112216a60>, ((<class 'type'>, <class 'foo_test.Tree'>),), frozenset())
result = builds(Tree, l=builds(lazy_error), r=builds(lazy_error), val=integers())

    @proxies(fn)
    def cached_strategy(*args, **kwargs):
        kwargs_cache_key = set()
        try:
            for k, v in kwargs.items():
                kwargs_cache_key.add((k, convert_value(v)))
        except TypeError:
            return fn(*args, **kwargs)
        cache_key = (
            fn,
            tuple(map(convert_value, args)), frozenset(kwargs_cache_key))
        try:
>           return STRATEGY_CACHE[cache_key]

/Users/desmond/anaconda3/lib/python3.6/site-packages/hypothesis/strategies.py:107: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

self = {(<function booleans at 0x112763e18>, (), frozenset()): booleans(), (<function fractions at 0x112216d90>, ((<class 'No...(tuples(), fixed_dictionaries({})).map(lambda value: target(*value[0], **value[1])),
 'val': WideRangeIntStrategy()}))}
key = (<function from_type at 0x112216a60>, ((<class 'type'>, <class 'foo_test.Tree'>),), frozenset())

    def __getitem__(self, key):
>       i = self.keys_to_indices[key]
E       KeyError: (<function from_type at 0x112216a60>, ((<class 'type'>, <class 'foo_test.Tree'>),), frozenset())

[Zac-HD]

Thanks for the report - I'll need to poke around a bit to decide on the best fix, but this is a great bug report
and will make that much easier 😄

[DRMacIver]

I'll need to poke around a bit to decide on the best fix

FWIW, I'd guess that wrapping from_type output in a deferred strategy is probably the way to go. This sort of free recursion is kinda what they're for.

[desmond-dsouza]

Yes, probably a couple of deferred needed. I might do it by hand like this (though I think they came out lopsided when I tried this):

GenTree = S.builds(Tree,
                   S.integers(),
                   S.one_of(S.none(), S.deferred(lambda: GenTree)),
                   S.one_of(S.none(), S.deferred(lambda: GenTree)))

(Side comment: I wonder why type annotations use strings for recursive types or forward references, instead of thunks / lambdas).

Related question: I was originally going to jump into stateful testing to try out trees, but got confused by some things in the examples described, so I'll ask here. Feel free to remove / move if appropriate:

• (Caveat: my understanding only) The example of BalancedTrees has no mutable state or side effects other than the Bundles, and those exist to help create a reasonable set of immutable trees using pure functions, to then feed to the balance_tree pure function and then to the check_balanced invariant. Is that the intent of the example? Why not just assert a boolean version of check_balanced at the end of balance_tree? Does the instantiation of these Bundles need to be user-visible? This may be partly a question about example selection.

• Why does BalancedTrees need to be a class? Would a module provide a lighter touch, much like pyunit / unittest vs. pytest?

Thanks for sharing a great library.

[Zac-HD]

Side comment: I wonder why type annotations use strings for recursive types or forward references, instead of thunks / lambdas.

I'll leave the others, but this is because type annotations are meant to work for static analysis and thus can't require evaluating code.

[Zac-HD]

We actually have two problems here:

1. Forward references are not currently handled, and are resolved for function annotations but not always for types (as in this case)
2. I'm pretty sure recursion in the lookup is also broken, but I'll have to fix (1) before diagnosing and handling recursion

[DRMacIver]

@Zac-HD based on #1026 (comment), is this actually closed? It seems like the fix doesn't support NamedTuple (though based on discussion it seems like we might not be able to)

[Zac-HD]

Unfortunately there is no way to resolve forward references in Python 3.6, if they are not function annotations. The example above should now fail with an explicit ResolutionFailed though, and explain that forward references are not supported - that's the best I can do 😢

[DRMacIver]

@Zac-HD In which case I think I'll reopen the issue. Even if we can't/won't fix this any time soon I think it's a legitimate thing to want supported. Hopefully in future it will become easier to do so (or maybe we'll figure out some clever trick).

[Zac-HD]

Fair enough! I consider that a feature request though, which might be possible on Python 3.7 😄

(retagged, retitled, unassigned myself)

[Zac-HD]

Deferred annotations make this slightly less annoying, because an official way to resolve forward references has now been published: https://www.python.org/dev/peps/pep-0563/#resolving-type-hints-at-runtime

What to do when this fails at runtime - and especially how to make the error message useful - is left as an exercise for the implementer.