Merge pull request #4639 from Zac-HD/fix-recursive-strategy

Zac-HD · web-flow · commit 8cc1f3827158 · 2026-01-12T00:06:52.000-08:00
Fix and deprecate unusual uses of `st.recursive()`
diff --git a/hypothesis-python/RELEASE.rst b/hypothesis-python/RELEASE.rst
@@ -0,0 +1,9 @@
+RELEASE_TYPE: patch
+
+This patch fixes a bug where |st.recursive| would fail in cases where the
+``extend=`` function does not reference it's argument - which was assumed
+by the recent ``min_leaves=`` feature, because the strategy can't actually
+recurse otherwise.  (:issue:`4638`)
+
+Now, the historical behavior is working-but-deprecated, or an error if you
+explicitly pass ``min_leaves=``.
diff --git a/hypothesis-python/src/hypothesis/internal/conjecture/data.py b/hypothesis-python/src/hypothesis/internal/conjecture/data.py
@@ -646,21 +646,21 @@ def __init__(
         self.overdraw = 0
         self._random = random
 
-        self.length = 0
-        self.index = 0
-        self.output = ""
-        self.status = Status.VALID
-        self.frozen = False
-        self.testcounter = threadlocal.global_test_counter
+        self.length: int = 0
+        self.index: int = 0
+        self.output: str = ""
+        self.status: Status = Status.VALID
+        self.frozen: bool = False
+        self.testcounter: int = threadlocal.global_test_counter
         threadlocal.global_test_counter += 1
         self.start_time = time.perf_counter()
         self.gc_start_time = gc_cumulative_time()
         self.events: dict[str, str | int | float] = {}
         self.interesting_origin: InterestingOrigin | None = None
         self.draw_times: dict[str, float] = {}
         self._stateful_run_times: dict[str, float] = defaultdict(float)
-        self.max_depth = 0
-        self.has_discards = False
+        self.max_depth: int = 0
+        self.has_discards: bool = False
 
         self.provider: PrimitiveProvider = (
             provider(self, **provider_kw) if isinstance(provider, type) else provider
@@ -683,9 +683,8 @@ def __init__(
         # examples for reporting purposes.
         self.__spans: Spans | None = None
 
-        # We want the top level span to have depth 0, so we start
-        # at -1.
-        self.depth = -1
+        # We want the top level span to have depth 0, so we start at -1.
+        self.depth: int = -1
         self.__span_record = SpanRecord()
 
         # Slice indices for discrete reportable parts that which-parts-matter can
diff --git a/hypothesis-python/src/hypothesis/internal/conjecture/engine.py b/hypothesis-python/src/hypothesis/internal/conjecture/engine.py
@@ -911,10 +911,14 @@ def debug_data(self, data: ConjectureData | ConjectureResult) -> None:
         status = repr(data.status)
         if data.status == Status.INTERESTING:
             status = f"{status} ({data.interesting_origin!r})"
+        elif data.status == Status.INVALID and isinstance(data, ConjectureData):
+            assert isinstance(data, ConjectureData)  # mypy is silly
+            status = f"{status} ({data.events.get('invalid because', '?')})"
 
+        newline_tab = "\n\t"
         self.debug(
-            f"{len(data.choices)} choices {data.choices} -> {status}"
-            f"{', ' + data.output if data.output else ''}"
+            f"{len(data.choices)} choices -> {status}\n\t{data.choices}"
+            f"{newline_tab + data.output if data.output else ''}"
         )
 
     def observe_for_provider(self) -> AbstractContextManager:
diff --git a/hypothesis-python/src/hypothesis/strategies/_internal/core.py b/hypothesis-python/src/hypothesis/strategies/_internal/core.py
@@ -1857,18 +1857,16 @@ def recursive(
     base: SearchStrategy[Ex],
     extend: Callable[[SearchStrategy[Any]], SearchStrategy[T]],
     *,
-    min_leaves: int = 1,
+    min_leaves: int | None = None,
     max_leaves: int = 100,
 ) -> SearchStrategy[T | Ex]:
     """base: A strategy to start from.
 
     extend: A function which takes a strategy and returns a new strategy.
 
-    min_leaves: The minimum number of elements to be drawn from base on a given
-    run.
+    min_leaves: The minimum number of elements to be drawn from base on a given run.
 
-    max_leaves: The maximum number of elements to be drawn from base on a given
-    run.
+    max_leaves: The maximum number of elements to be drawn from base on a given run.
 
     This returns a strategy ``S`` such that ``S = extend(base | S)``. That is,
     values may be drawn from base, or from any strategy reachable by mixing
@@ -1882,9 +1880,7 @@ def recursive(
     Examples from this strategy shrink by trying to reduce the amount of
     recursion and by shrinking according to the shrinking behaviour of base
     and the result of extend.
-
     """
-
     return RecursiveStrategy(base, extend, min_leaves, max_leaves)
 
 
diff --git a/hypothesis-python/src/hypothesis/strategies/_internal/recursive.py b/hypothesis-python/src/hypothesis/strategies/_internal/recursive.py
@@ -10,11 +10,13 @@
 
 import threading
 import warnings
+from collections.abc import Callable
 from contextlib import contextmanager
 
 from hypothesis.errors import HypothesisWarning, InvalidArgument
 from hypothesis.internal.reflection import (
     get_pretty_function_description,
+    is_first_param_referenced_in_function,
     is_identity_function,
 )
 from hypothesis.internal.validation import check_type
@@ -23,6 +25,7 @@
     SearchStrategy,
     check_strategy,
 )
+from hypothesis.utils.deprecation import note_deprecation
 
 
 class LimitReached(BaseException):
@@ -76,27 +79,25 @@ def capped(self, max_templates):
 
 
 class RecursiveStrategy(SearchStrategy):
-    def __init__(self, base, extend, min_leaves, max_leaves):
+    def __init__(
+        self,
+        base: SearchStrategy,
+        extend: Callable[[SearchStrategy], SearchStrategy],
+        min_leaves: int | None,
+        max_leaves: int,
+    ):
         super().__init__()
         self.min_leaves = min_leaves
         self.max_leaves = max_leaves
         self.base = base
         self.limited_base = LimitedStrategy(base)
         self.extend = extend
 
-        if is_identity_function(extend):
-            warnings.warn(
-                "extend=lambda x: x is a no-op; you probably want to use a "
-                "different extend function, or just use the base strategy directly.",
-                HypothesisWarning,
-                stacklevel=5,
-            )
-
         strategies = [self.limited_base, self.extend(self.limited_base)]
         while 2 ** (len(strategies) - 1) <= max_leaves:
             strategies.append(extend(OneOfStrategy(tuple(strategies))))
         # If min_leaves > 1, we can never draw from base directly
-        if min_leaves > 1:
+        if min_leaves is not None and min_leaves > 1:
             strategies = strategies[1:]
         self.strategy = OneOfStrategy(strategies)
 
@@ -115,17 +116,42 @@ def do_validate(self) -> None:
         check_strategy(extended, f"extend({self.limited_base!r})")
         self.limited_base.validate()
         extended.validate()
-        check_type(int, self.min_leaves, "min_leaves")
+
+        if is_identity_function(self.extend):
+            warnings.warn(
+                "extend=lambda x: x is a no-op; you probably want to use a "
+                "different extend function, or just use the base strategy directly.",
+                HypothesisWarning,
+                stacklevel=5,
+            )
+
+        if not is_first_param_referenced_in_function(self.extend):
+            msg = (
+                f"extend={get_pretty_function_description(self.extend)} doesn't use "
+                "it's argument, and thus can't actually recurse!"
+            )
+            if self.min_leaves is None:
+                note_deprecation(
+                    msg,
+                    since="RELEASEDAY",
+                    has_codemod=False,
+                    stacklevel=1,
+                )
+            else:
+                raise InvalidArgument(msg)
+
+        if self.min_leaves is not None:
+            check_type(int, self.min_leaves, "min_leaves")
         check_type(int, self.max_leaves, "max_leaves")
-        if self.min_leaves <= 0:
+        if self.min_leaves is not None and self.min_leaves <= 0:
             raise InvalidArgument(
                 f"min_leaves={self.min_leaves!r} must be greater than zero"
             )
         if self.max_leaves <= 0:
             raise InvalidArgument(
                 f"max_leaves={self.max_leaves!r} must be greater than zero"
             )
-        if self.min_leaves > self.max_leaves:
+        if (self.min_leaves or 1) > self.max_leaves:
             raise InvalidArgument(
                 f"min_leaves={self.min_leaves!r} must be less than or equal to "
                 f"max_leaves={self.max_leaves!r}"
@@ -138,7 +164,7 @@ def do_draw(self, data):
                 with self.limited_base.capped(self.max_leaves):
                     result = data.draw(self.strategy)
                     leaves_drawn = self.max_leaves - self.limited_base.marker
-                    if leaves_drawn < self.min_leaves:
+                    if self.min_leaves and leaves_drawn < self.min_leaves:
                         data.events[
                             f"Draw for {self!r} had fewer than "
                             f"min_leaves={self.min_leaves} and had to be retried"
diff --git a/hypothesis-python/tests/conjecture/test_engine.py b/hypothesis-python/tests/conjecture/test_engine.py
@@ -596,7 +596,7 @@ def f(data):
     runner.run()
 
     out, _ = capsys.readouterr()
-    assert re.match(r"\d+ choices \(.*\) -> ", out)
+    assert re.match(r"\d+ choices -> ", out)
     assert "INTERESTING" in out
 
 
diff --git a/hypothesis-python/tests/cover/test_recursive.py b/hypothesis-python/tests/cover/test_recursive.py
@@ -15,10 +15,12 @@
 
 from tests.common.debug import (
     assert_all_examples,
+    assert_no_examples,
     check_can_generate_examples,
     find_any,
     minimal,
 )
+from tests.common.utils import checks_deprecated_behaviour
 
 
 @given(st.recursive(st.booleans(), st.lists, max_leaves=10))
@@ -80,6 +82,28 @@ def test_issue_1502_regression(s):
     pass
 
 
+def test_recursive_can_generate_varied_structures():
+    values = st.recursive(st.none(), st.lists)
+
+    find_any(values, lambda x: x is None)
+    find_any(values, lambda x: isinstance(x, list))
+    find_any(
+        values, lambda x: isinstance(x, list) and any(isinstance(y, list) for y in x)
+    )
+
+
+@checks_deprecated_behaviour
+def test_recursive_can_generate_varied_structures_without_using_leaves():
+    values = st.recursive(st.none(), lambda _: st.lists(st.none()))
+
+    find_any(values, lambda x: x is None)
+    find_any(values, lambda x: isinstance(x, list))
+    # The bad `extend` function means we can't actually recurse!
+    assert_no_examples(
+        values, lambda x: isinstance(x, list) and any(isinstance(y, list) for y in x)
+    )
+
+
 @pytest.mark.parametrize(
     "s",
     [
@@ -92,6 +116,7 @@ def test_issue_1502_regression(s):
         st.recursive(st.none(), st.lists, min_leaves=0),
         st.recursive(st.none(), st.lists, min_leaves=1.0),
         st.recursive(st.none(), st.lists, min_leaves=10, max_leaves=5),
+        st.recursive(st.none(), lambda _: st.lists(st.none()), min_leaves=1),
     ],
 )
 def test_invalid_args(s):
@@ -129,4 +154,4 @@ def test_can_set_exact_leaf_count(tree):
 
 def test_identity_extend_warns():
     with pytest.warns(HypothesisWarning, match="extend=lambda x: x is a no-op"):
-        st.recursive(st.none(), lambda x: x)
+        st.recursive(st.none(), lambda x: x).validate()
