Skip to content

Commit 77ca292

Browse files
committed
Implement _invert for most remaining strategy combinators
Port the per-strategy inversions from the original inversion draft onto the single-CannotInvert lineage: just()/sampled_from (via an exact-type, top-level-NaN-aware equal_values helper in junkdrawer, which recurses through lists and tuples but deliberately falls back to plain == for other containers), tuples and lists (via an invert_many counterpart of cu.many), unique lists (including the sampled pool variant, whose indices are relative to the not-yet-drawn elements), text over non-standard one-character element strategies (as a list of single-character draws), dates, times, datetimes and timedeltas, permutations (by reversing the Fisher-Yates shuffle), zero-argument and dataclass builds, filtered strategies, the NaN strategy, and delegation for deferred, limited, and recursive strategies. Collection inversions re-raise nested failures with add_note breadcrumbs recording the index and strategy, so failures deep in a strategy tree are debuggable. Aware-bounded datetimes invert through the same frame decision as generation: the wall-clock-window computation is extracted from draw_aware_datetime into a pure helper shared with _invert, which encodes the timezone draw first and then the multipart fields in the drawing frame - the value's own wall clock, or its UTC conversion when generation would recurse via UTC. Anything doubtful raises CannotInvert: unrepresentable bounds, instants outside the bounds, imaginary values in the UTC frame (their conversion does not round trip), or a tzinfo the timezones strategy cannot re-encode - which includes the default timezones() strategy for now, a flatmap of keys mapped through ZoneInfo. OneOfStrategy._invert gains two guards: an early exit once a candidate of at most two choices is found, since only a zero-choice branch could beat it, and a thread-local reentrancy check, since a self-referential strategy can route a branch's inversion of the same value back to the same one_of and recurse forever - a wrapper like .filter hides the cycle from branch flattening, which otherwise collapses direct self-references. Span values are now also recorded for None and the immutable datetime types, so the widening shrink pass applies to them too; since None is a recordable value, Span.recorded_value reports absence - including a collected weakly-held value - with a no_recorded_value sentinel rather than None. Widening still only helps when the wide branch's encoding is no longer than the specific branch's, since the shrinker never accepts a longer choice sequence; tests pin both directions. Co-Authored-By: Claude Fable 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01KbvBiusz22hjM4bxRcAtEB
1 parent 5b20755 commit 77ca292

20 files changed

Lines changed: 1088 additions & 70 deletions

File tree

‎hypothesis/RELEASE.rst‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
RELEASE_TYPE: patch
2+
3+
This release extends a recent shrinking improvement to many more strategies.
4+
In unions like ``wide_strategy | specific_strategy``, values produced by the
5+
specific branch can now be re-encoded and shrunk as if generated by the wider
6+
branch when the strategies involved include
7+
:func:`~hypothesis.strategies.sampled_from`,
8+
:func:`~hypothesis.strategies.lists`, :func:`~hypothesis.strategies.tuples`,
9+
:func:`~hypothesis.strategies.builds` of a dataclass,
10+
:func:`~hypothesis.strategies.permutations`, the
11+
:func:`~hypothesis.strategies.dates` family of strategies, and filtered,
12+
deferred, or recursive combinations of them - where previously only the
13+
primitive strategies could re-encode a value.

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

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@
1212
from collections.abc import Callable, Hashable, Iterable, Sequence
1313
from dataclasses import dataclass
1414
from typing import (
15+
Any,
1516
Literal,
1617
TypeAlias,
1718
TypedDict,
@@ -95,7 +96,8 @@ class ValueHole:
9596
reaches it.
9697
"""
9798

98-
value: ChoiceT
99+
# any value a strategy might re-encode, not just the choice types
100+
value: Any
99101

100102

101103
@dataclass(slots=True, frozen=False)

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

Lines changed: 53 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -8,8 +8,11 @@
88
# v. 2.0. If a copy of the MPL was not distributed with this file, You can
99
# obtain one at https://mozilla.org/MPL/2.0/.
1010

11+
import datetime
1112
import math
1213
import time
14+
import types
15+
import weakref
1316
from collections import defaultdict
1417
from collections.abc import Hashable, Iterable, Iterator, Sequence
1518
from dataclasses import dataclass, field
@@ -72,7 +75,7 @@
7275
from hypothesis.internal.intervalsets import IntervalSet
7376
from hypothesis.internal.observability import PredicateCounts
7477
from hypothesis.reporting import debug_report
75-
from hypothesis.utils.conventions import not_set
78+
from hypothesis.utils.conventions import UniqueIdentifier, not_set
7679
from hypothesis.utils.deprecation import note_deprecation
7780
from hypothesis.utils.threading import ThreadLocal
7881

@@ -141,9 +144,28 @@ def structural_coverage(label: int) -> StructuralCoverageTag:
141144
# performance. We lose scan resistance, but that's probably fine here.
142145
POOLED_CONSTRAINTS_CACHE: LRUCache[tuple[Any, ...], ChoiceConstraintsT] = LRUCache(4096)
143146

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+
# The exact types whose values record_value_for_span holds directly: small
148+
# immutable stdlib types, none of which support weak references. Values of
149+
# any other type are held via weakref where possible, so that recording never
150+
# extends an object's lifetime. A tuple rather than a set so that ``in``
151+
# works even if a value's class has an unhashable metaclass. Exact type
152+
# checks also exclude symbolic backends.
153+
_RECORDABLE_VALUE_TYPES: tuple[type, ...] = (
154+
int,
155+
bool,
156+
str,
157+
bytes,
158+
float,
159+
types.NoneType,
160+
datetime.date,
161+
datetime.time,
162+
datetime.datetime,
163+
datetime.timedelta,
164+
)
165+
166+
# Sentinel distinguishing "no value was recorded for this span" from a
167+
# recorded value of None.
168+
no_recorded_value = UniqueIdentifier("no_recorded_value")
147169

148170

149171
class Span:
@@ -249,9 +271,13 @@ def children(self) -> "list[Span]":
249271
@property
250272
def recorded_value(self) -> Any:
251273
"""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)
274+
or the ``no_recorded_value`` sentinel if no value was recorded, or if
275+
a weakly-referenced value has since been collected."""
276+
value = self.owner.span_values.get(self.index, no_recorded_value)
277+
if isinstance(value, weakref.ReferenceType):
278+
referent = value()
279+
return no_recorded_value if referent is None else referent
280+
return value
255281

256282

257283
class SpanProperty:
@@ -363,12 +389,17 @@ def stop_span(self, *, discard: bool) -> None:
363389
self.trail.append(TrailType.STOP_SPAN_NO_DISCARD)
364390

365391
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
392+
# Record ``value`` against the span at ``span_index``. Called by
393+
# ConjectureData.draw with the value each strategy's do_draw returned.
394+
# Values which can be neither held directly nor weakly referenced
395+
# (e.g. stdlib containers) are not recorded, and so cannot widen.
396+
if type(value) in _RECORDABLE_VALUE_TYPES:
397+
self.span_values[span_index] = value
398+
else:
399+
try:
400+
self.span_values[span_index] = weakref.ref(value)
401+
except TypeError:
402+
pass
372403

373404

374405
class _starts_and_ends(SpanProperty):
@@ -740,6 +771,7 @@ def __init__(
740771
self.expected_traceback: str | None = None
741772

742773
self.prefix = prefix
774+
self._inverting = False
743775
self.nodes: tuple[ChoiceNode, ...] = ()
744776
self.misaligned_at: MisalignedAt | None = None
745777
self.cannot_proceed_scope: CannotProceedScopeT | None = None
@@ -822,6 +854,11 @@ def _draw(
822854
observe: bool,
823855
forced: ChoiceT | None,
824856
) -> ChoiceT:
857+
if self._inverting:
858+
# A strategy tried to draw while re-encoding a ValueHole - e.g. a
859+
# filter predicate which draws, like stateful's rule filters.
860+
# Inversions must be pure, so treat this as unencodable.
861+
raise CannotInvert("cannot draw during _invert")
825862
# this is somewhat redundant with the length > max_length check at the
826863
# end of the function, but avoids trying to use a null self.random when
827864
# drawing past the node of a ConjectureData.for_choices data.
@@ -1249,6 +1286,7 @@ def draw(
12491286
and self.index < len(self.prefix)
12501287
and isinstance(hole := self.prefix[self.index], ValueHole)
12511288
):
1289+
self._inverting = True
12521290
try:
12531291
inverted = unwrapped._invert(hole.value)
12541292
except CannotInvert:
@@ -1259,6 +1297,8 @@ def draw(
12591297
+ inverted
12601298
+ tuple(self.prefix[self.index + 1 :])
12611299
)
1300+
finally:
1301+
self._inverting = False
12621302

12631303
span_index = self.__span_record.span_count
12641304
self.start_span(label=label)

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

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,10 +32,34 @@
3232
)
3333

3434
from hypothesis.errors import HypothesisWarning
35+
from hypothesis.internal.floats import float_to_int
3536

3637
T = TypeVar("T")
3738

3839

40+
def equal_values(a: Any, b: Any) -> bool:
41+
"""Like ==, but requires identical types (so True != 1 != 1.0) and
42+
compares floats by bitpattern (so nan == nan and 0.0 != -0.0), applying
43+
both rules elementwise through lists and tuples.
44+
45+
Values of any other type - dicts, sets, arbitrary objects - are compared
46+
by plain == after the type check, so a NaN, signed zero, or bool/int
47+
confusion nested inside them is missed: a NaN there compares unequal and
48+
a nested True matches 1. Callers use this for best-effort,
49+
replay-verified inversion, where such a miss costs a widening opportunity
50+
- the replay produces a wrong or unequal value and is rejected - never
51+
correctness.
52+
"""
53+
if type(a) is not type(b):
54+
return False
55+
if isinstance(a, float):
56+
# by bitpattern, matching choice_equal
57+
return float_to_int(a) == float_to_int(b)
58+
if isinstance(a, (list, tuple)):
59+
return len(a) == len(b) and all(map(equal_values, a, b))
60+
return bool(a == b)
61+
62+
3963
def replace_all(
4064
ls: Sequence[T],
4165
replacements: Iterable[tuple[int, int, Sequence[T]]],

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

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@
4040
Status,
4141
_Overrun,
4242
draw_choice,
43+
no_recorded_value,
4344
)
4445
from hypothesis.internal.conjecture.junkdrawer import (
4546
endswith,
@@ -1670,7 +1671,7 @@ def widen_to_span_with_recorded_value(self, chooser):
16701671
# (e.g. the selector draw's own span), or a one_of whose current
16711672
# branch made no choices, like just() - and a re-encoding of the
16721673
# latter would be longer, which incorporate_test_data rejects.
1673-
lambda i: self.spans[i].recorded_value is not None
1674+
lambda i: self.spans[i].recorded_value is not no_recorded_value
16741675
and self.spans[i].choice_count > 1,
16751676
)
16761677
span = self.spans[span_idx]

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

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@
2525
from hypothesis.internal.lambda_sources import _function_key
2626

2727
if TYPE_CHECKING:
28+
from hypothesis.internal.conjecture.choice import ChoiceT
2829
from hypothesis.internal.conjecture.data import ConjectureData
2930

3031

@@ -357,6 +358,23 @@ def reject(self, why: str | None = None) -> None:
357358
self.force_stop = True
358359

359360

361+
class invert_many:
362+
"""The inversion counterpart of ``many``: the boolean choices that
363+
``many`` would draw for a collection of known size. Fixed-size collections
364+
draw no booleans at all; variable-size ones draw a continuation boolean
365+
before each element (forced while below min_size, but forced draws still
366+
consume a choice) and a final False to stop (forced at max_size)."""
367+
368+
def __init__(self, min_size: int, max_size: int | float) -> None:
369+
self._variable_size = min_size != max_size
370+
371+
def more(self) -> tuple["ChoiceT", ...]:
372+
return (True,) if self._variable_size else ()
373+
374+
def done(self) -> tuple["ChoiceT", ...]:
375+
return (False,) if self._variable_size else ()
376+
377+
360378
SMALLEST_POSITIVE_FLOAT: float = next_up(0.0) or sys.float_info.min
361379

362380

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

Lines changed: 92 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -15,11 +15,13 @@
1515

1616
from hypothesis import strategies as st
1717
from hypothesis.control import current_build_context
18-
from hypothesis.errors import InvalidArgument
18+
from hypothesis.errors import CannotInvert, InvalidArgument
19+
from hypothesis.internal.compat import add_note
1920
from hypothesis.internal.conjecture import utils as cu
21+
from hypothesis.internal.conjecture.choice import ChoiceT
2022
from hypothesis.internal.conjecture.data import ConjectureData
2123
from hypothesis.internal.conjecture.engine import BUFFER_SIZE
22-
from hypothesis.internal.conjecture.junkdrawer import LazySequenceCopy
24+
from hypothesis.internal.conjecture.junkdrawer import LazySequenceCopy, equal_values
2325
from hypothesis.internal.conjecture.utils import combine_labels
2426
from hypothesis.internal.filtering import get_integer_predicate_bounds
2527
from hypothesis.internal.reflection import is_identity_function
@@ -86,6 +88,22 @@ def do_draw(self, data: ConjectureData) -> tuple[Ex, ...]:
8688
)
8789
return result
8890

91+
def _invert(self, value: Any) -> tuple[ChoiceT, ...]:
92+
if not isinstance(value, tuple) or len(value) != len(self.element_strategies):
93+
raise CannotInvert(
94+
f"{value!r} is not a tuple of length {len(self.element_strategies)}"
95+
)
96+
choices: list[ChoiceT] = []
97+
for i, (strategy, element) in enumerate(
98+
zip(self.element_strategies, value, strict=True)
99+
):
100+
try:
101+
choices.extend(strategy._invert(element))
102+
except CannotInvert as exc:
103+
add_note(exc, f"at index {i} of {value!r}, strategy={self!r}")
104+
raise
105+
return tuple(choices)
106+
89107
def calc_is_empty(self, recur: RecurT) -> bool:
90108
return any(recur(e) for e in self.element_strategies)
91109

@@ -219,6 +237,31 @@ def do_draw(self, data: ConjectureData) -> list[Ex]:
219237
result.append(data.draw(self.element_strategy))
220238
return result
221239

240+
def _invert(self, value: Any) -> tuple[ChoiceT, ...]:
241+
if not isinstance(value, list):
242+
raise CannotInvert(f"{value!r} is not a list")
243+
if not (self.min_size <= len(value) <= self.max_size):
244+
raise CannotInvert(
245+
f"len={len(value)} outside "
246+
f"[{self.min_size}, {self.max_size!r}] for {self!r}"
247+
)
248+
if self.element_strategy.is_empty:
249+
# do_draw returns [] without drawing anything
250+
if value:
251+
raise CannotInvert(f"elements of {self!r} are empty")
252+
return ()
253+
elements = cu.invert_many(self.min_size, self.max_size)
254+
choices: list[ChoiceT] = []
255+
for i, element in enumerate(value):
256+
choices.extend(elements.more())
257+
try:
258+
choices.extend(self.element_strategy._invert(element))
259+
except CannotInvert as exc:
260+
add_note(exc, f"at index {i} of {value!r}, strategy={self!r}")
261+
raise
262+
choices.extend(elements.done())
263+
return tuple(choices)
264+
222265
def __repr__(self) -> str:
223266
return (
224267
f"{self.__class__.__name__}({self.element_strategy!r}, "
@@ -327,6 +370,20 @@ def not_yet_in_unique_list(val: Ex) -> bool: # type: ignore # covariant type pa
327370
assert self.max_size >= len(result) >= self.min_size
328371
return result
329372

373+
def _invert(self, value: Any) -> tuple[ChoiceT, ...]:
374+
if self.tuple_suffixes is not None:
375+
# each element interleaves an element_strategy draw with a
376+
# tuple_suffixes draw, which we cannot separate here
377+
raise CannotInvert(f"cannot invert {self!r} with tuple_suffixes")
378+
# A valid unique list draws exactly like a ListStrategy, since every
379+
# element passes the uniqueness filter on its first draw.
380+
choices = ListStrategy._invert(self, value)
381+
for keyfunc in self.keys:
382+
keys = list(map(keyfunc, value))
383+
if len(set(keys)) != len(keys):
384+
raise CannotInvert(f"{value!r} has duplicate keys for {self!r}")
385+
return choices
386+
330387

331388
class UniqueSampledListStrategy(UniqueListStrategy):
332389
def do_draw(self, data: ConjectureData) -> list[Ex]:
@@ -362,6 +419,39 @@ def do_draw(self, data: ConjectureData) -> list[Ex]:
362419
assert self.max_size >= len(result) >= self.min_size
363420
return result
364421

422+
def _invert(self, value: Any) -> tuple[ChoiceT, ...]:
423+
if self.tuple_suffixes is not None:
424+
raise CannotInvert(f"cannot invert {self!r} with tuple_suffixes")
425+
if not isinstance(value, list):
426+
raise CannotInvert(f"{value!r} is not a list")
427+
if not (self.min_size <= len(value) <= self.max_size):
428+
raise CannotInvert(
429+
f"len={len(value)} outside "
430+
f"[{self.min_size}, {self.max_size!r}] for {self!r}"
431+
)
432+
# do_draw indexes into the pool of not-yet-drawn elements, so each
433+
# index is relative to what remains, not to the original elements.
434+
assert isinstance(self.element_strategy, SampledFromStrategy)
435+
remaining = list(self.element_strategy.elements)
436+
elements = cu.invert_many(self.min_size, self.max_size)
437+
choices: list[ChoiceT] = []
438+
for i, target in enumerate(value):
439+
choices.extend(elements.more())
440+
for j, candidate in enumerate(remaining):
441+
if equal_values(self.element_strategy._transform(candidate), target):
442+
choices.append(j)
443+
remaining.pop(j)
444+
break
445+
else:
446+
raise CannotInvert(
447+
f"at index {i} of {value!r}: {target!r} is not among the "
448+
f"remaining elements of {self!r}"
449+
)
450+
if remaining:
451+
# with an exhausted pool, do_draw stops without drawing a boolean
452+
choices.extend(elements.done())
453+
return tuple(choices)
454+
365455

366456
class FixedDictStrategy(SearchStrategy[Mapping[Any, Any]]):
367457
"""A strategy which produces mappings with a fixed set of keys, given a

0 commit comments

Comments
 (0)