Skip to content

Commit b4f2e92

Browse files
authored
Merge pull request #4806 from HypothesisWorks/claude/widening-shrinks
Widen values from specific one_of branches into wider strategies
2 parents dba4a65 + 9431e20 commit b4f2e92

15 files changed

Lines changed: 879 additions & 15 deletions

File tree

‎hypothesis/RELEASE.rst‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
RELEASE_TYPE: patch
2+
3+
This release improves shrinking for strategies like
4+
``st.text() | some_more_complicated_strategy``: values produced by the more
5+
specific strategy can now be shrunk as if they had been generated by the
6+
wider strategy. (Values from :func:`~hypothesis.strategies.just` are the
7+
exception, as generating them makes no choices which could be re-encoded.)

‎hypothesis/src/hypothesis/errors.py‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -64,6 +64,14 @@ class ChoiceTooLarge(HypothesisException):
6464
"""An internal error raised by choice_from_index."""
6565

6666

67+
class CannotInvert(HypothesisException):
68+
"""
69+
Internal error raised by SearchStrategy._invert, either because the value
70+
is not produced by that strategy, or because we haven't implemented an
71+
inversion for it.
72+
"""
73+
74+
6775
class Flaky(_Trimmable):
6876
"""
6977
Base class for indeterministic failures. Usually one of the more

‎hypothesis/src/hypothesis/internal/conjecture/choice.py‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -81,6 +81,23 @@ def __post_init__(self) -> None:
8181
assert self.count > 0
8282

8383

84+
@dataclass(slots=True, frozen=True)
85+
class ValueHole:
86+
"""A hole in a choice sequence, carrying a value instead of choices.
87+
88+
When ``ConjectureData.draw`` finds a ValueHole at the current prefix
89+
position, it asks the strategy being drawn to ``_invert`` the value, and
90+
on success splices the resulting choices into the prefix in place of the
91+
hole - so the value is re-encoded by whichever strategy is drawn at that
92+
position, with that strategy's own constraints. If no strategy claims the
93+
hole (inversion failed, or the hole fell out of alignment with strategy
94+
draw boundaries), it is treated as a misalignment when a draw_* call
95+
reaches it.
96+
"""
97+
98+
value: ChoiceT
99+
100+
84101
@dataclass(slots=True, frozen=False)
85102
class ChoiceNode:
86103
type: ChoiceTypeT

‎hypothesis/src/hypothesis/internal/conjecture/data.py‎

Lines changed: 64 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,7 @@
2828
)
2929

3030
from hypothesis.errors import (
31+
CannotInvert,
3132
CannotProceedScopeT,
3233
ChoiceTooLarge,
3334
FlakyStrategyDefinition,
@@ -48,6 +49,7 @@
4849
FloatConstraints,
4950
IntegerConstraints,
5051
StringConstraints,
52+
ValueHole,
5153
choice_constraints_key,
5254
choice_from_index,
5355
choice_permitted,
@@ -139,6 +141,10 @@ def structural_coverage(label: int) -> StructuralCoverageTag:
139141
# performance. We lose scan resistance, but that's probably fine here.
140142
POOLED_CONSTRAINTS_CACHE: LRUCache[tuple[Any, ...], ChoiceConstraintsT] = LRUCache(4096)
141143

144+
# A tuple rather than a set so that ``in`` works even if a value's class has
145+
# an unhashable metaclass. Exact type checks also exclude symbolic backends.
146+
_PRIMITIVE_CHOICE_TYPES: tuple[type, ...] = (int, bool, str, bytes, float)
147+
142148

143149
class Span:
144150
"""A span tracks the hierarchical structure of choices within a single test run.
@@ -240,6 +246,13 @@ def children(self) -> "list[Span]":
240246
order."""
241247
return [self.owner[i] for i in self.owner.children[self.index]]
242248

249+
@property
250+
def recorded_value(self) -> Any:
251+
"""The value produced by the strategy draw corresponding to this span,
252+
or ``None`` if no value was recorded. Only values of the primitive
253+
choice types (int, bool, float, str, bytes) are recorded."""
254+
return self.owner.span_values.get(self.index)
255+
243256

244257
class SpanProperty:
245258
"""There are many properties of spans that we calculate by
@@ -325,6 +338,7 @@ def __init__(self) -> None:
325338
# The number of spans started so far, which is also the index that the
326339
# next span to start will get. Spans are indexed in start order.
327340
self.span_count = 0
341+
self.span_values: dict[int, Any] = {}
328342

329343
def freeze(self) -> None:
330344
self.__index_of_labels = None
@@ -348,6 +362,14 @@ def stop_span(self, *, discard: bool) -> None:
348362
else:
349363
self.trail.append(TrailType.STOP_SPAN_NO_DISCARD)
350364

365+
def record_value_for_span(self, span_index: int, value: Any) -> None:
366+
# Record ``value`` against the span at ``span_index``, if it is one of
367+
# the primitive choice types. Called by ConjectureData.draw with the
368+
# value each strategy's do_draw returned.
369+
if type(value) not in _PRIMITIVE_CHOICE_TYPES:
370+
return
371+
self.span_values[span_index] = value
372+
351373

352374
class _starts_and_ends(SpanProperty):
353375
def __init__(self, spans: "Spans") -> None:
@@ -447,6 +469,7 @@ class Spans:
447469
def __init__(self, record: SpanRecord) -> None:
448470
self.trail = record.trail
449471
self.labels = record.labels
472+
self.span_values = record.span_values
450473
self.__length = self.trail.count(
451474
TrailType.STOP_SPAN_DISCARD
452475
) + record.trail.count(TrailType.STOP_SPAN_NO_DISCARD)
@@ -608,7 +631,7 @@ class ConjectureData:
608631
@classmethod
609632
def for_choices(
610633
cls,
611-
choices: Sequence[ChoiceTemplate | ChoiceT],
634+
choices: Sequence[ChoiceTemplate | ValueHole | ChoiceT],
612635
*,
613636
observer: DataObserver | None = None,
614637
provider: PrimitiveProvider | type[PrimitiveProvider] = HypothesisProvider,
@@ -630,7 +653,7 @@ def __init__(
630653
random: Random | None,
631654
observer: DataObserver | None = None,
632655
provider: PrimitiveProvider | type[PrimitiveProvider] = HypothesisProvider,
633-
prefix: Sequence[ChoiceTemplate | ChoiceT] | None = None,
656+
prefix: Sequence[ChoiceTemplate | ValueHole | ChoiceT] | None = None,
634657
max_choices: int | None = None,
635658
provider_kw: dict[str, Any] | None = None,
636659
) -> None:
@@ -1079,6 +1102,19 @@ def _pop_choice(
10791102
self.mark_overrun()
10801103
return choice
10811104

1105+
if isinstance(value, ValueHole):
1106+
# A hole that no strategy claimed: either its value could not be
1107+
# inverted, or it fell out of alignment with strategy draw
1108+
# boundaries. Treat it as a misalignment.
1109+
if self.misaligned_at is None:
1110+
self.misaligned_at = (self.index, choice_type, constraints, forced)
1111+
try:
1112+
choice = choice_from_index(0, choice_type, constraints)
1113+
except ChoiceTooLarge:
1114+
self.mark_overrun()
1115+
self.index += 1
1116+
return choice
1117+
10821118
choice = value
10831119
node_choice_type = {
10841120
str: "string",
@@ -1203,11 +1239,35 @@ def draw(
12031239
label = unwrapped.label
12041240
assert isinstance(label, int)
12051241

1242+
# If the next prefix element is a ValueHole, we are the strategy being
1243+
# asked to re-encode its value: replace the hole with our inversion of
1244+
# it, and let do_draw consume those choices (under our own constraints)
1245+
# as usual. If we can't invert it, leave the hole for _pop_choice to
1246+
# treat as a misalignment.
1247+
if (
1248+
self.prefix is not None
1249+
and self.index < len(self.prefix)
1250+
and isinstance(hole := self.prefix[self.index], ValueHole)
1251+
):
1252+
try:
1253+
inverted = unwrapped._invert(hole.value)
1254+
except CannotInvert:
1255+
pass
1256+
else:
1257+
self.prefix = (
1258+
tuple(self.prefix[: self.index])
1259+
+ inverted
1260+
+ tuple(self.prefix[self.index + 1 :])
1261+
)
1262+
1263+
span_index = self.__span_record.span_count
12061264
self.start_span(label=label)
12071265
try:
12081266
if not at_top_level:
12091267
try:
1210-
return unwrapped.do_draw(self)
1268+
v = unwrapped.do_draw(self)
1269+
self.__span_record.record_value_for_span(span_index, v)
1270+
return v
12111271
except FlakyStrategyDefinition as err:
12121272
# Record the strategy stack as the error unwinds, so that an
12131273
# inconsistent-generation failure is explained in terms of the
@@ -1234,6 +1294,7 @@ def draw(
12341294
if observability_enabled():
12351295
avoid = self.provider.avoid_realization
12361296
self._observability_args[key] = to_jsonable(v, avoid_realization=avoid)
1297+
self.__span_record.record_value_for_span(span_index, v)
12371298
return v
12381299
finally:
12391300
self.stop_span()

‎hypothesis/src/hypothesis/internal/conjecture/engine.py‎

Lines changed: 25 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@
4040
ChoiceNode,
4141
ChoiceT,
4242
ChoiceTemplate,
43+
ValueHole,
4344
choices_key,
4445
)
4546
from hypothesis.internal.conjecture.data import (
@@ -234,10 +235,15 @@ class CallStats(TypedDict):
234235
)
235236

236237

237-
def choice_count(choices: Sequence[ChoiceT | ChoiceTemplate]) -> int | None:
238+
def choice_count(
239+
choices: Sequence[ChoiceT | ChoiceTemplate | ValueHole],
240+
) -> int | None:
238241
count = 0
239242
for choice in choices:
240-
if isinstance(choice, ChoiceTemplate):
243+
if isinstance(choice, ValueHole):
244+
# expands to however many choices the inverting strategy emits
245+
return None
246+
elif isinstance(choice, ChoiceTemplate):
241247
if choice.count is None:
242248
return None
243249
count += choice.count
@@ -453,7 +459,7 @@ def _cache(self, data: ConjectureData) -> None:
453459

454460
def cached_test_function(
455461
self,
456-
choices: Sequence[ChoiceT | ChoiceTemplate],
462+
choices: Sequence[ChoiceT | ChoiceTemplate | ValueHole],
457463
*,
458464
error_on_discard: bool = False,
459465
extend: int | Literal["full"] = 0,
@@ -466,11 +472,14 @@ def cached_test_function(
466472
result has discards if we cannot determine from previous runs whether
467473
it will have a discard.
468474
"""
469-
# node templates represent a not-yet-filled hole and therefore cannot
470-
# be cached or retrieved from the cache.
471-
if not any(isinstance(choice, ChoiceTemplate) for choice in choices):
472-
# this type cast is validated by the isinstance check above (ie, there
473-
# are no ChoiceTemplate elements).
475+
# node templates and value holes represent a not-yet-filled hole and
476+
# therefore cannot be cached or retrieved from the cache.
477+
has_value_hole = any(isinstance(choice, ValueHole) for choice in choices)
478+
if not has_value_hole and not any(
479+
isinstance(choice, ChoiceTemplate) for choice in choices
480+
):
481+
# this type cast is validated by the isinstance checks above (ie,
482+
# there are no ChoiceTemplate or ValueHole elements).
474483
choices = cast(Sequence[ChoiceT], choices)
475484
key = self._cache_key(choices)
476485
try:
@@ -498,6 +507,13 @@ def cached_test_function(
498507
trial_observer = DiscardObserver()
499508

500509
try:
510+
# A ValueHole is only resolvable by the strategy drawn at its
511+
# position, so tree simulation - which replays at the choice level
512+
# with no strategies involved - would resolve it incorrectly.
513+
# (ChoiceTemplate is fine: its resolution is deterministic at the
514+
# choice level, so simulation and the real run agree.)
515+
if has_value_hole:
516+
raise PreviouslyUnseenBehaviour
501517
trial_data = self.new_conjecture_data(
502518
choices, observer=trial_observer, max_choices=max_length
503519
)
@@ -1575,7 +1591,7 @@ def _run(self) -> None:
15751591

15761592
def new_conjecture_data(
15771593
self,
1578-
prefix: Sequence[ChoiceT | ChoiceTemplate],
1594+
prefix: Sequence[ChoiceT | ChoiceTemplate | ValueHole],
15791595
*,
15801596
observer: DataObserver | None = None,
15811597
max_choices: int | None = None,

‎hypothesis/src/hypothesis/internal/conjecture/shrinker.py‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@
2525
from hypothesis.internal.conjecture.choice import (
2626
ChoiceNode,
2727
ChoiceT,
28+
ValueHole,
2829
choice_equal,
2930
choice_from_index,
3031
choice_key,
@@ -353,6 +354,7 @@ def __init__(
353354
ShrinkPass(self.lower_integers_together),
354355
ShrinkPass(self.lower_duplicated_characters),
355356
ShrinkPass(self.normalize_unicode_chars),
357+
ShrinkPass(self.widen_to_span_with_recorded_value),
356358
]
357359

358360
# Because the shrinker is also used to `pareto_optimise` in the target phase,
@@ -1635,6 +1637,51 @@ def normalize_unicode_chars(self, chooser):
16351637
):
16361638
return
16371639

1640+
def widen_to_span_with_recorded_value(self, chooser):
1641+
"""Replace a strategy's choices with a ValueHole carrying the value it
1642+
produced, so that the replay re-encodes that value more simply.
1643+
1644+
We look for a span which starts with a non-forced zero-based non-zero
1645+
integer choice (heuristically: a one_of branch selector), makes more
1646+
than one choice, and has a recorded value, and propose the same
1647+
choice sequence with the span's choices replaced by a single
1648+
ValueHole. At replay time the hole is claimed by whichever strategy
1649+
draws at that position: a one_of's ``_invert`` tries every alternative
1650+
in-process and returns the simplest encoding whose image contains the
1651+
value, so one test execution covers all of its branches. If the
1652+
result is a strictly simpler choice sequence which still fails, it is
1653+
kept, and normal shrinking takes the re-encoded value the rest of the
1654+
way. All knowledge of how to encode values lives with the strategies,
1655+
not here.
1656+
"""
1657+
node = chooser.choose(
1658+
self.nodes,
1659+
lambda n: (
1660+
n.type == "integer"
1661+
and not n.was_forced
1662+
and n.constraints["min_value"] == 0
1663+
and n.value != 0
1664+
),
1665+
)
1666+
1667+
span_idx = chooser.choose(
1668+
self.spans_starting_at[node.index],
1669+
# Single-choice spans are excluded: they are either not a one_of
1670+
# (e.g. the selector draw's own span), or a one_of whose current
1671+
# branch made no choices, like just() - and a re-encoding of the
1672+
# latter would be longer, which incorporate_test_data rejects.
1673+
lambda i: self.spans[i].recorded_value is not None
1674+
and self.spans[i].choice_count > 1,
1675+
)
1676+
span = self.spans[span_idx]
1677+
1678+
attempt = (
1679+
self.choices[: span.start]
1680+
+ (ValueHole(span.recorded_value),)
1681+
+ self.choices[span.end :]
1682+
)
1683+
self.incorporate_test_data(self.engine.cached_test_function(attempt))
1684+
16381685
def minimize_nodes(self, nodes):
16391686
choice_type = nodes[0].type
16401687
value = nodes[0].value

‎hypothesis/src/hypothesis/strategies/_internal/lazy.py‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@
1414
from weakref import WeakKeyDictionary
1515

1616
from hypothesis.configuration import check_sideeffect_during_initialization
17+
from hypothesis.internal.conjecture.choice import ChoiceT
1718
from hypothesis.internal.conjecture.data import ConjectureData
1819
from hypothesis.internal.reflection import (
1920
convert_keyword_arguments,
@@ -174,3 +175,6 @@ def __repr__(self) -> str:
174175

175176
def do_draw(self, data: ConjectureData) -> Ex:
176177
return data.draw(self.wrapped_strategy)
178+
179+
def _invert(self, value: Any) -> tuple[ChoiceT, ...]:
180+
return self.wrapped_strategy._invert(value)

‎hypothesis/src/hypothesis/strategies/_internal/misc.py‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,8 @@
1111
from collections.abc import Callable
1212
from typing import TYPE_CHECKING, Any, NoReturn
1313

14+
from hypothesis.errors import CannotInvert
15+
from hypothesis.internal.conjecture.choice import ChoiceT
1416
from hypothesis.internal.conjecture.data import ConjectureData
1517
from hypothesis.internal.reflection import get_pretty_function_description
1618
from hypothesis.strategies._internal.strategies import (
@@ -134,5 +136,10 @@ class BooleansStrategy(SearchStrategy[bool]):
134136
def do_draw(self, data: ConjectureData) -> bool:
135137
return data.draw_boolean()
136138

139+
def _invert(self, value: Any) -> tuple[ChoiceT, ...]:
140+
if not isinstance(value, bool):
141+
raise CannotInvert(f"{value!r} is not a bool")
142+
return (value,)
143+
137144
def __repr__(self) -> str:
138145
return "booleans()"

0 commit comments

Comments
 (0)