How to use with recursive namedtuple?

[ZelphirKaltstahl]

I would like to make a recursive strategy for a namedtuple, to use in a unit test, but could not find a way yet how to do this properly with hypothesis:

# tree.py

from collections import namedtuple

TreeNode = namedtuple('TreeNode', ['value', 'children'])

And the test code I have so far:

import unittest

from hypothesis import (
    given,
    strategies as st,
)

from tree import TreeNode

# A recursive strategy needs a strategy for generating a single
# non-compound (with regards to the structure that is supposed to be
# generated) value, and a way of making compound values.
recursive_tree_strat = st.recursive(
    # non-compound value generator
    st.builds(TreeNode, st.integers(), ...),  # <-- What to put here instead of ellipsis? Maybe cannot use `builds` for this?
    # compound value creator
    lambda children: st.tuples(children, children),
    # some limits
    max_leaves=10  # why no max depth?!
)

In the test case I want to be able to use the strategy like any other strategy:

class TestRecursiveDataTuples(unittest.TestCase):
    @given(x=recursive_tree_strat)
    def test_can_be_compound(self, x):
        if not isinstance(x, int):
            assert isinstance(x, TreeNode)  # or whatever other test

All examples I found so far are with simple values, not compound ones, but in a tree I need children, which are of the very structure, that I am trying to create a strategy for. How can this be achieved? Maybe I should not be using builds?

If I run the tests without the ellipsis in place, I get of course the following error:

TypeError: TreeNode.__new__() missing 1 required positional argument: 'children'

because the TreeNode namedtuple is missing an argument, because I did not specify another args in the call to builds. However, I am not sure what I can put there instead.

If I call builds with an additonal TreeNode, of course that is also wrong, because TreeNode is not a strategy, but the class of the value I want to create. I get the following error then:

    raise InvalidArgument(
hypothesis.errors.InvalidArgument: Expected a SearchStrategy but got <class 'tree.TreeNode'> (type=type)

EDIT-1:

When using from_type(TreeNode) as argument, I also get an error, back to missing 2 arguments, probably for an internal call done by from_type(?):

recursive_tree_strat = st.recursive(
    st.builds(TreeNode, st.integers(), st.from_type(TreeNode)),
    lambda children: st.tuples(children, children),
    max_leaves=10
)

Gets the following error:

TypeError: TreeNode.__new__() missing 2 required positional arguments: 'value' and 'children'

[ZelphirKaltstahl]

I found the following in another issue (#3026):

class RecursiveClass:
    def __init__(self, value: int, next_node: typing.Optional["SomeClass"]):
        assert value > 0
        self.value = value
        self.next_node = next_node

st.register_type_strategy(
    RecursiveClass,
    st.builds(RecursiveClass, value=st.integers(min_value=1))  # next_node inferred from type annotation
)


build_strategy_for_some_class = st.builds(
    SomeClass,
    value=st.integers(min_value=1),
    next_node=st.none() | st.deferred(lambda: st.from_type(SomeClass)),
)
st.register_type_strategy(SomeClass, build_strategy_for_some_class)

But I don't know how I can make it work for namedtuples, with non-optional arguments. For the example I posted above it would make sense to use None or the empty list [] as children argument for the case of having no children in the tree (being a leaf node).

I can change the namedtuple to use the defaults keyword argument:

from collections import namedtuple

TreeNode = namedtuple('TreeNode', ('value', 'children'), defaults=(0, None))

Then try the following:

recursive_tree_strat = st.recursive(
    # note the missing argument
    st.builds(TreeNode, st.integers()),
    lambda children: st.tuples(children, children),
    max_leaves=100
)


class TestRecursiveDataNamedtuples(unittest.TestCase):
    @given(x=recursive_tree_strat)
    def test_can_be_compound(self, x):
        if not isinstance(x, int):
            assert isinstance(x, TreeNode)

But this also results in an error:

TypeError: TreeNode.__new__() missing 1 required positional argument: 'children'

======================================================================
ERROR: test_can_be_compound (test_tree.TestRecursiveDataTuples)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/test/test_tree.py", line 30, in test_can_be_compound
    def test_can_be_compound(self, x):
  File "/venv/lib/python3.10/site-packages/hypothesis/core.py", line 1396, in wrapped_test
    raise the_error_hypothesis_found
  File "/test/test_tree.py", line 31, in test_can_be_compound
    logger.debug("testing with x: %s" % x)
TypeError: not all arguments converted during string formatting
Falsifying example: test_can_be_compound(
    x=(0, 0),
    self=<test_tree.TestRecursiveDataTuples testMethod=test_can_be_compound>,
)

Hypothesis does not seem to realize, that there is a default value for the namedtuple, which it could use to make a leaf.

[Zac-HD]

You seem to be unsure about the type of children - it can't actually be a TreeNode (or pair of them, etc) because that would require unbounded recursion. Can you write out a typing.NamedTuple to clarify this? If so, st.from_type(TreeNode) should work with that.

[ZelphirKaltstahl]

You seem to be unsure about the type of children - it can't actually be a TreeNode (or pair of them, etc) because that would require unbounded recursion.

But that is exactly what I want to do. Not limiting, how deep the recursion can go in the code of the data structure (in this case a named tuple), but limit it through the means of hypothesis for the tests. For tests I can assume some maximum depth for a realistic case, but I cannot assume that in the actual code, otherwise I make the data structure less general purpose and arbitrarily limited in nature. In general there are often data structures, especially trees, which can theoretically have arbitrary depth and I cannot limit them ahead of time in their own code. That would defeat their purpose.

Can you write out a typing.NamedTuple to clarify this?

I don't know how I would do so. The children of a TreeNode must be a list (or tuple, or set, or similar) of potentially any number of TreeNodes. I don't want to limit what the data structure can do, in order to satisfy a test scenario.

Is it generally impossible with hypothesis to generate data for (unbounded) recursive data types? I imagined something like specifying a maximum depth and after reaching that depth (counting along, while generating layers of the recursive data structure iteratively) hypothesis would generate a None or [] as children attribute.

[Zac-HD]

class TreeNode(typing.NamedTuple):
    value: int
    children: "typing.Collection[TreeNode]"  # base case is an empty collection

st.from_type(TreeNode)  # this should work fine

You must have a base case where it's possible for a TreeNode to have no children; otherwise no finitely-large TreeNode exists. In this case, that's possible because children might be an empty collection.

[ZelphirKaltstahl]

Could you leave this open, until I had time to verify, that the code you posted actually does, what I am looking for? @Zac-HD