prompt: We are currently solving the following issue within our repository. Here is the issue text:
  --- BEGIN ISSUE ---
  Improve handling of self-referential strategies
  As mentioned in #2783, the following strategy is not explicitly forbidden but fails with an `AssertionError`:
  
  ```python
  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:
  
  ```python
  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.
  
  
  
  --- END ISSUE ---
  
  Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
  --- BEGIN FILES ---
  Path: `hypothesis-python/src/hypothesis/strategies/_internal/recursive.py`
  Content:
  ```
  1 # This file is part of Hypothesis, which may be found at
  2 # https://github.com/HypothesisWorks/hypothesis/
  3 #
  4 # Most of this work is copyright (C) 2013-2021 David R. MacIver
  5 # (david@drmaciver.com), but it contains contributions by others. See
  6 # CONTRIBUTING.rst for a full list of people who may hold copyright, and
  7 # consult the git log if you need to determine who owns an individual
  8 # contribution.
  9 #
  10 # This Source Code Form is subject to the terms of the Mozilla Public License,
  11 # v. 2.0. If a copy of the MPL was not distributed with this file, You can
  12 # obtain one at https://mozilla.org/MPL/2.0/.
  13 #
  14 # END HEADER
  15 
  16 import threading
  17 from contextlib import contextmanager
  18 
  19 from hypothesis.internal.lazyformat import lazyformat
  20 from hypothesis.internal.reflection import get_pretty_function_description
  21 from hypothesis.strategies._internal.strategies import (
  22     OneOfStrategy,
  23     SearchStrategy,
  24     check_strategy,
  25 )
  26 
  27 
  28 class LimitReached(BaseException):
  29     pass
  30 
  31 
  32 class LimitedStrategy(SearchStrategy):
  33     def __init__(self, strategy):
  34         super().__init__()
  35         self.base_strategy = strategy
  36         self._threadlocal = threading.local()
  37 
  38     @property
  39     def marker(self):
  40         return getattr(self._threadlocal, "marker", 0)
  41 
  42     @marker.setter
  43     def marker(self, value):
  44         self._threadlocal.marker = value
  45 
  46     @property
  47     def currently_capped(self):
  48         return getattr(self._threadlocal, "currently_capped", False)
  49 
  50     @currently_capped.setter
  51     def currently_capped(self, value):
  52         self._threadlocal.currently_capped = value
  53 
  54     def __repr__(self):
  55         return f"LimitedStrategy({self.base_strategy!r})"
  56 
  57     def do_validate(self):
  58         self.base_strategy.validate()
  59 
  60     def do_draw(self, data):
  61         assert self.currently_capped
  62         if self.marker <= 0:
  63             raise LimitReached()
  64         self.marker -= 1
  65         return data.draw(self.base_strategy)
  66 
  67     @contextmanager
  68     def capped(self, max_templates):
  69         assert not self.currently_capped
  70         try:
  71             self.currently_capped = True
  72             self.marker = max_templates
  73             yield
  74         finally:
  75             self.currently_capped = False
  76 
  77 
  78 class RecursiveStrategy(SearchStrategy):
  79     def __init__(self, base, extend, max_leaves):
  80         self.max_leaves = max_leaves
  81         self.base = base
  82         self.limited_base = LimitedStrategy(base)
  83         self.extend = extend
  84 
  85         strategies = [self.limited_base, self.extend(self.limited_base)]
  86         while 2 ** (len(strategies) - 1) <= max_leaves:
  87             strategies.append(extend(OneOfStrategy(tuple(strategies))))
  88         self.strategy = OneOfStrategy(strategies)
  89 
  90     def __repr__(self):
  91         if not hasattr(self, "_cached_repr"):
  92             self._cached_repr = "recursive(%r, %s, max_leaves=%d)" % (
  93                 self.base,
  94                 get_pretty_function_description(self.extend),
  95                 self.max_leaves,
  96             )
  97         return self._cached_repr
  98 
  99     def do_validate(self):
  100         check_strategy(self.base, "base")
  101         extended = self.extend(self.limited_base)
  102         check_strategy(extended, f"extend({self.limited_base!r})")
  103         self.limited_base.validate()
  104         extended.validate()
  105 
  106     def do_draw(self, data):
  107         count = 0
  108         while True:
  109             try:
  110                 with self.limited_base.capped(self.max_leaves):
  111                     return data.draw(self.strategy)
  112             except LimitReached:
  113                 # Workaround for possible coverage bug - this branch is definitely
  114                 # covered but for some reason is showing up as not covered.
  115                 if count == 0:  # pragma: no branch
  116                     data.note_event(
  117                         lazyformat(
  118                             "Draw for %r exceeded max_leaves and had to be retried",
  119                             self,
  120                         )
  121                     )
  122                 count += 1
  123
  ```
  --- END FILES ---
  
  Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.
  
  Here is an example:
  
  ```diff
  diff --git a/examples/server_async.py b/examples/server_async.py
  --- a/examples/server_async.py
  +++ b/examples/server_async.py
  @@ -313,4 +313,4 @@
   
   
   if __name__ == "__main__":
  -    asyncio.run(run_async_server("."), debug=True)
  +    asyncio.run(run_async_server(), debug=True)
  diff --git a/examples/server_sync.py b/examples/server_sync.py
  --- a/examples/server_sync.py
  +++ b/examples/server_sync.py
  @@ -313,5 +313,5 @@
   
   
   if __name__ == "__main__":
  -    server = run_sync_server(".")
  +    server = run_sync_server()
       server.shutdown()
  
  ```
  
golden_diff: diff --git a/hypothesis-python/src/hypothesis/strategies/_internal/recursive.py b/hypothesis-python/src/hypothesis/strategies/_internal/recursive.py
  --- a/hypothesis-python/src/hypothesis/strategies/_internal/recursive.py
  +++ b/hypothesis-python/src/hypothesis/strategies/_internal/recursive.py
  @@ -66,13 +66,13 @@
   
       @contextmanager
       def capped(self, max_templates):
  -        assert not self.currently_capped
           try:
  +            was_capped = self.currently_capped
               self.currently_capped = True
               self.marker = max_templates
               yield
           finally:
  -            self.currently_capped = False
  +            self.currently_capped = was_capped
   
   
   class RecursiveStrategy(SearchStrategy):
  
verification_info: {"golden_diff": "diff --git a/hypothesis-python/src/hypothesis/strategies/_internal/recursive.py b/hypothesis-python/src/hypothesis/strategies/_internal/recursive.py\n--- a/hypothesis-python/src/hypothesis/strategies/_internal/recursive.py\n+++ b/hypothesis-python/src/hypothesis/strategies/_internal/recursive.py\n@@ -66,13 +66,13 @@\n \n     @contextmanager\n     def capped(self, max_templates):\n-        assert not self.currently_capped\n         try:\n+            was_capped = self.currently_capped\n             self.currently_capped = True\n             self.marker = max_templates\n             yield\n         finally:\n-            self.currently_capped = False\n+            self.currently_capped = was_capped\n \n \n class RecursiveStrategy(SearchStrategy):\n", "issue": "Improve handling of self-referential strategies\nAs mentioned in #2783, the following strategy is not explicitly forbidden but fails with an `AssertionError`:\r\n\r\n```python\r\nfrom hypothesis import strategies as st\r\n\r\nSELF_REF = st.recursive(\r\n    st.deferred(lambda: SELF_REF | st.booleans()),\r\n    lambda s: st.lists(s, min_size=1)\r\n)\r\n```\r\n\r\nThere is an alternative strategy that produces the same data, but doesn't fail the same way:\r\n\r\n```python\r\nSELF_REF = st.recursive(\r\n    st.booleans(),\r\n    lambda s: st.lists(s, min_size=1)\r\n)\r\n```\r\n\r\nI 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.\r\n\r\nHere is my reasoning from #2783 \r\n\r\n> 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.\r\n\r\n\n", "before_files": [{"content": "# This file is part of Hypothesis, which may be found at\n# https://github.com/HypothesisWorks/hypothesis/\n#\n# Most of this work is copyright (C) 2013-2021 David R. MacIver\n# (david@drmaciver.com), but it contains contributions by others. See\n# CONTRIBUTING.rst for a full list of people who may hold copyright, and\n# consult the git log if you need to determine who owns an individual\n# contribution.\n#\n# This Source Code Form is subject to the terms of the Mozilla Public License,\n# v. 2.0. If a copy of the MPL was not distributed with this file, You can\n# obtain one at https://mozilla.org/MPL/2.0/.\n#\n# END HEADER\n\nimport threading\nfrom contextlib import contextmanager\n\nfrom hypothesis.internal.lazyformat import lazyformat\nfrom hypothesis.internal.reflection import get_pretty_function_description\nfrom hypothesis.strategies._internal.strategies import (\n    OneOfStrategy,\n    SearchStrategy,\n    check_strategy,\n)\n\n\nclass LimitReached(BaseException):\n    pass\n\n\nclass LimitedStrategy(SearchStrategy):\n    def __init__(self, strategy):\n        super().__init__()\n        self.base_strategy = strategy\n        self._threadlocal = threading.local()\n\n    @property\n    def marker(self):\n        return getattr(self._threadlocal, \"marker\", 0)\n\n    @marker.setter\n    def marker(self, value):\n        self._threadlocal.marker = value\n\n    @property\n    def currently_capped(self):\n        return getattr(self._threadlocal, \"currently_capped\", False)\n\n    @currently_capped.setter\n    def currently_capped(self, value):\n        self._threadlocal.currently_capped = value\n\n    def __repr__(self):\n        return f\"LimitedStrategy({self.base_strategy!r})\"\n\n    def do_validate(self):\n        self.base_strategy.validate()\n\n    def do_draw(self, data):\n        assert self.currently_capped\n        if self.marker <= 0:\n            raise LimitReached()\n        self.marker -= 1\n        return data.draw(self.base_strategy)\n\n    @contextmanager\n    def capped(self, max_templates):\n        assert not self.currently_capped\n        try:\n            self.currently_capped = True\n            self.marker = max_templates\n            yield\n        finally:\n            self.currently_capped = False\n\n\nclass RecursiveStrategy(SearchStrategy):\n    def __init__(self, base, extend, max_leaves):\n        self.max_leaves = max_leaves\n        self.base = base\n        self.limited_base = LimitedStrategy(base)\n        self.extend = extend\n\n        strategies = [self.limited_base, self.extend(self.limited_base)]\n        while 2 ** (len(strategies) - 1) <= max_leaves:\n            strategies.append(extend(OneOfStrategy(tuple(strategies))))\n        self.strategy = OneOfStrategy(strategies)\n\n    def __repr__(self):\n        if not hasattr(self, \"_cached_repr\"):\n            self._cached_repr = \"recursive(%r, %s, max_leaves=%d)\" % (\n                self.base,\n                get_pretty_function_description(self.extend),\n                self.max_leaves,\n            )\n        return self._cached_repr\n\n    def do_validate(self):\n        check_strategy(self.base, \"base\")\n        extended = self.extend(self.limited_base)\n        check_strategy(extended, f\"extend({self.limited_base!r})\")\n        self.limited_base.validate()\n        extended.validate()\n\n    def do_draw(self, data):\n        count = 0\n        while True:\n            try:\n                with self.limited_base.capped(self.max_leaves):\n                    return data.draw(self.strategy)\n            except LimitReached:\n                # Workaround for possible coverage bug - this branch is definitely\n                # covered but for some reason is showing up as not covered.\n                if count == 0:  # pragma: no branch\n                    data.note_event(\n                        lazyformat(\n                            \"Draw for %r exceeded max_leaves and had to be retried\",\n                            self,\n                        )\n                    )\n                count += 1\n", "path": "hypothesis-python/src/hypothesis/strategies/_internal/recursive.py"}], "after_files": [{"content": "# This file is part of Hypothesis, which may be found at\n# https://github.com/HypothesisWorks/hypothesis/\n#\n# Most of this work is copyright (C) 2013-2021 David R. MacIver\n# (david@drmaciver.com), but it contains contributions by others. See\n# CONTRIBUTING.rst for a full list of people who may hold copyright, and\n# consult the git log if you need to determine who owns an individual\n# contribution.\n#\n# This Source Code Form is subject to the terms of the Mozilla Public License,\n# v. 2.0. If a copy of the MPL was not distributed with this file, You can\n# obtain one at https://mozilla.org/MPL/2.0/.\n#\n# END HEADER\n\nimport threading\nfrom contextlib import contextmanager\n\nfrom hypothesis.internal.lazyformat import lazyformat\nfrom hypothesis.internal.reflection import get_pretty_function_description\nfrom hypothesis.strategies._internal.strategies import (\n    OneOfStrategy,\n    SearchStrategy,\n    check_strategy,\n)\n\n\nclass LimitReached(BaseException):\n    pass\n\n\nclass LimitedStrategy(SearchStrategy):\n    def __init__(self, strategy):\n        super().__init__()\n        self.base_strategy = strategy\n        self._threadlocal = threading.local()\n\n    @property\n    def marker(self):\n        return getattr(self._threadlocal, \"marker\", 0)\n\n    @marker.setter\n    def marker(self, value):\n        self._threadlocal.marker = value\n\n    @property\n    def currently_capped(self):\n        return getattr(self._threadlocal, \"currently_capped\", False)\n\n    @currently_capped.setter\n    def currently_capped(self, value):\n        self._threadlocal.currently_capped = value\n\n    def __repr__(self):\n        return f\"LimitedStrategy({self.base_strategy!r})\"\n\n    def do_validate(self):\n        self.base_strategy.validate()\n\n    def do_draw(self, data):\n        assert self.currently_capped\n        if self.marker <= 0:\n            raise LimitReached()\n        self.marker -= 1\n        return data.draw(self.base_strategy)\n\n    @contextmanager\n    def capped(self, max_templates):\n        try:\n            was_capped = self.currently_capped\n            self.currently_capped = True\n            self.marker = max_templates\n            yield\n        finally:\n            self.currently_capped = was_capped\n\n\nclass RecursiveStrategy(SearchStrategy):\n    def __init__(self, base, extend, max_leaves):\n        self.max_leaves = max_leaves\n        self.base = base\n        self.limited_base = LimitedStrategy(base)\n        self.extend = extend\n\n        strategies = [self.limited_base, self.extend(self.limited_base)]\n        while 2 ** (len(strategies) - 1) <= max_leaves:\n            strategies.append(extend(OneOfStrategy(tuple(strategies))))\n        self.strategy = OneOfStrategy(strategies)\n\n    def __repr__(self):\n        if not hasattr(self, \"_cached_repr\"):\n            self._cached_repr = \"recursive(%r, %s, max_leaves=%d)\" % (\n                self.base,\n                get_pretty_function_description(self.extend),\n                self.max_leaves,\n            )\n        return self._cached_repr\n\n    def do_validate(self):\n        check_strategy(self.base, \"base\")\n        extended = self.extend(self.limited_base)\n        check_strategy(extended, f\"extend({self.limited_base!r})\")\n        self.limited_base.validate()\n        extended.validate()\n\n    def do_draw(self, data):\n        count = 0\n        while True:\n            try:\n                with self.limited_base.capped(self.max_leaves):\n                    return data.draw(self.strategy)\n            except LimitReached:\n                # Workaround for possible coverage bug - this branch is definitely\n                # covered but for some reason is showing up as not covered.\n                if count == 0:  # pragma: no branch\n                    data.note_event(\n                        lazyformat(\n                            \"Draw for %r exceeded max_leaves and had to be retried\",\n                            self,\n                        )\n                    )\n                count += 1\n", "path": "hypothesis-python/src/hypothesis/strategies/_internal/recursive.py"}]}