Skip to content

Commit d6911d5

Browse files
Zac-HDZac-HD
committed
fix recursion
1 parent 94b9bef commit d6911d5

File tree

5 files changed

+75
-23
lines changed

5 files changed

+75
-23
lines changed

‎hypothesis-python/RELEASE.rst‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
RELEASE_TYPE: patch
2+
3+
This patch fixes a bug where |st.recursive| would fail in cases where the
4+
``extend=`` function does not reference it's argument - which was assumed
5+
by the recent ``min_leaves=`` feature, because the strategy can't actually
6+
recurse otherwise. (:issue:`4638`)
7+
8+
Now, the historical behavior is working-but-deprecated, or an error if you
9+
explicitly pass ``min_leaves=``.

‎hypothesis-python/src/hypothesis/strategies/_internal/core.py‎

Lines changed: 3 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1857,18 +1857,16 @@ def recursive(
18571857
base: SearchStrategy[Ex],
18581858
extend: Callable[[SearchStrategy[Any]], SearchStrategy[T]],
18591859
*,
1860-
min_leaves: int = 1,
1860+
min_leaves: int | None = None,
18611861
max_leaves: int = 100,
18621862
) -> SearchStrategy[T | Ex]:
18631863
"""base: A strategy to start from.
18641864
18651865
extend: A function which takes a strategy and returns a new strategy.
18661866
1867-
min_leaves: The minimum number of elements to be drawn from base on a given
1868-
run.
1867+
min_leaves: The minimum number of elements to be drawn from base on a given run.
18691868
1870-
max_leaves: The maximum number of elements to be drawn from base on a given
1871-
run.
1869+
max_leaves: The maximum number of elements to be drawn from base on a given run.
18721870
18731871
This returns a strategy ``S`` such that ``S = extend(base | S)``. That is,
18741872
values may be drawn from base, or from any strategy reachable by mixing
@@ -1882,9 +1880,7 @@ def recursive(
18821880
Examples from this strategy shrink by trying to reduce the amount of
18831881
recursion and by shrinking according to the shrinking behaviour of base
18841882
and the result of extend.
1885-
18861883
"""
1887-
18881884
return RecursiveStrategy(base, extend, min_leaves, max_leaves)
18891885

18901886

‎hypothesis-python/src/hypothesis/strategies/_internal/recursive.py‎

Lines changed: 37 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -10,11 +10,13 @@
1010

1111
import threading
1212
import warnings
13+
from collections.abc import Callable
1314
from contextlib import contextmanager
1415

1516
from hypothesis.errors import HypothesisWarning, InvalidArgument
1617
from hypothesis.internal.reflection import (
1718
get_pretty_function_description,
19+
is_first_param_referenced_in_function,
1820
is_identity_function,
1921
)
2022
from hypothesis.internal.validation import check_type
@@ -23,6 +25,7 @@
2325
SearchStrategy,
2426
check_strategy,
2527
)
28+
from hypothesis.utils.deprecation import note_deprecation
2629

2730

2831
class LimitReached(BaseException):
@@ -76,27 +79,25 @@ def capped(self, max_templates):
7679

7780

7881
class RecursiveStrategy(SearchStrategy):
79-
def __init__(self, base, extend, min_leaves, max_leaves):
82+
def __init__(
83+
self,
84+
base: SearchStrategy,
85+
extend: Callable[[SearchStrategy], SearchStrategy],
86+
min_leaves: int | None,
87+
max_leaves: int,
88+
):
8089
super().__init__()
8190
self.min_leaves = min_leaves
8291
self.max_leaves = max_leaves
8392
self.base = base
8493
self.limited_base = LimitedStrategy(base)
8594
self.extend = extend
8695

87-
if is_identity_function(extend):
88-
warnings.warn(
89-
"extend=lambda x: x is a no-op; you probably want to use a "
90-
"different extend function, or just use the base strategy directly.",
91-
HypothesisWarning,
92-
stacklevel=5,
93-
)
94-
9596
strategies = [self.limited_base, self.extend(self.limited_base)]
9697
while 2 ** (len(strategies) - 1) <= max_leaves:
9798
strategies.append(extend(OneOfStrategy(tuple(strategies))))
9899
# If min_leaves > 1, we can never draw from base directly
99-
if min_leaves > 1:
100+
if isinstance(min_leaves, int) and min_leaves > 1:
100101
strategies = strategies[1:]
101102
self.strategy = OneOfStrategy(strategies)
102103

@@ -115,17 +116,39 @@ def do_validate(self) -> None:
115116
check_strategy(extended, f"extend({self.limited_base!r})")
116117
self.limited_base.validate()
117118
extended.validate()
118-
check_type(int, self.min_leaves, "min_leaves")
119+
if is_identity_function(self.extend):
120+
warnings.warn(
121+
"extend=lambda x: x is a no-op; you probably want to use a "
122+
"different extend function, or just use the base strategy directly.",
123+
HypothesisWarning,
124+
stacklevel=5,
125+
)
126+
if not is_first_param_referenced_in_function(self.extend):
127+
msg = (
128+
f"extend={get_pretty_function_description(self.extend)} doesn't use "
129+
"it's argument, and thus can't actually recurse!"
130+
)
131+
if self.min_leaves is None:
132+
note_deprecation(
133+
msg,
134+
since="RELEASEDAY",
135+
has_codemod=False,
136+
stacklevel=1,
137+
)
138+
else:
139+
raise InvalidArgument(msg)
140+
if self.min_leaves is not None:
141+
check_type(int, self.min_leaves, "min_leaves")
119142
check_type(int, self.max_leaves, "max_leaves")
120-
if self.min_leaves <= 0:
143+
if self.min_leaves is not None and self.min_leaves <= 0:
121144
raise InvalidArgument(
122145
f"min_leaves={self.min_leaves!r} must be greater than zero"
123146
)
124147
if self.max_leaves <= 0:
125148
raise InvalidArgument(
126149
f"max_leaves={self.max_leaves!r} must be greater than zero"
127150
)
128-
if self.min_leaves > self.max_leaves:
151+
if (self.min_leaves or 1) > self.max_leaves:
129152
raise InvalidArgument(
130153
f"min_leaves={self.min_leaves!r} must be less than or equal to "
131154
f"max_leaves={self.max_leaves!r}"
@@ -138,7 +161,7 @@ def do_draw(self, data):
138161
with self.limited_base.capped(self.max_leaves):
139162
result = data.draw(self.strategy)
140163
leaves_drawn = self.max_leaves - self.limited_base.marker
141-
if leaves_drawn < self.min_leaves:
164+
if self.min_leaves and leaves_drawn < self.min_leaves:
142165
data.events[
143166
f"Draw for {self!r} had fewer than "
144167
f"min_leaves={self.min_leaves} and had to be retried"

‎hypothesis-python/tests/conjecture/test_engine.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -596,7 +596,7 @@ def f(data):
596596
runner.run()
597597

598598
out, _ = capsys.readouterr()
599-
assert re.match(r"\d+ choices \(.*\) -> ", out)
599+
assert re.match(r"\d+ choices -> ", out)
600600
assert "INTERESTING" in out
601601

602602

‎hypothesis-python/tests/cover/test_recursive.py‎

Lines changed: 25 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,10 +15,12 @@
1515

1616
from tests.common.debug import (
1717
assert_all_examples,
18+
assert_no_examples,
1819
check_can_generate_examples,
1920
find_any,
2021
minimal,
2122
)
23+
from tests.common.utils import checks_deprecated_behaviour
2224

2325

2426
@given(st.recursive(st.booleans(), st.lists, max_leaves=10))
@@ -80,6 +82,28 @@ def test_issue_1502_regression(s):
8082
pass
8183

8284

85+
def test_recursive_can_generate_varied_structures():
86+
values = st.recursive(st.none(), st.lists)
87+
88+
find_any(values, lambda x: x is None)
89+
find_any(values, lambda x: isinstance(x, list))
90+
find_any(
91+
values, lambda x: isinstance(x, list) and any(isinstance(y, list) for y in x)
92+
)
93+
94+
95+
@checks_deprecated_behaviour
96+
def test_recursive_can_generate_varied_structures_without_using_leaves():
97+
values = st.recursive(st.none(), lambda _: st.lists(st.none()))
98+
99+
find_any(values, lambda x: x is None)
100+
find_any(values, lambda x: isinstance(x, list))
101+
# The bad `extend` function means we can't actually recurse!
102+
assert_no_examples(
103+
values, lambda x: isinstance(x, list) and any(isinstance(y, list) for y in x)
104+
)
105+
106+
83107
@pytest.mark.parametrize(
84108
"s",
85109
[
@@ -129,4 +153,4 @@ def test_can_set_exact_leaf_count(tree):
129153

130154
def test_identity_extend_warns():
131155
with pytest.warns(HypothesisWarning, match="extend=lambda x: x is a no-op"):
132-
st.recursive(st.none(), lambda x: x)
156+
st.recursive(st.none(), lambda x: x).validate()

0 commit comments

Comments
 (0)