Skip to content

Commit a9eff28

Browse files
authored
Merge pull request #4842 from HypothesisWorks/claude/invert-everything
`._invert()` for many more strategies
2 parents 5b20755 + c555e58 commit a9eff28

20 files changed

Lines changed: 1433 additions & 103 deletions

File tree

‎hypothesis/RELEASE.rst‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
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.dictionaries` and
10+
:func:`~hypothesis.strategies.fixed_dictionaries`,
11+
:func:`~hypothesis.strategies.builds` of a dataclass,
12+
:func:`~hypothesis.strategies.permutations`, the
13+
:func:`~hypothesis.strategies.dates` family of strategies, and filtered,
14+
deferred, or recursive combinations of them.

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

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -95,7 +95,8 @@ class ValueHole:
9595
reaches it.
9696
"""
9797

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

100101

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

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

Lines changed: 51 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,26 @@ 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+
no_recorded_value = UniqueIdentifier("no_recorded_value")
147167

148168

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

256280

257281
class SpanProperty:
@@ -363,12 +387,17 @@ def stop_span(self, *, discard: bool) -> None:
363387
self.trail.append(TrailType.STOP_SPAN_NO_DISCARD)
364388

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

373402

374403
class _starts_and_ends(SpanProperty):
@@ -740,6 +769,7 @@ def __init__(
740769
self.expected_traceback: str | None = None
741770

742771
self.prefix = prefix
772+
self._inverting = False
743773
self.nodes: tuple[ChoiceNode, ...] = ()
744774
self.misaligned_at: MisalignedAt | None = None
745775
self.cannot_proceed_scope: CannotProceedScopeT | None = None
@@ -822,6 +852,11 @@ def _draw(
822852
observe: bool,
823853
forced: ChoiceT | None,
824854
) -> ChoiceT:
855+
if self._inverting:
856+
# A strategy tried to draw while re-encoding a ValueHole - e.g. a
857+
# filter predicate which draws, like stateful's rule filters.
858+
# Inversions must be pure, so treat this as unencodable.
859+
raise CannotInvert("cannot draw during _invert")
825860
# this is somewhat redundant with the length > max_length check at the
826861
# end of the function, but avoids trying to use a null self.random when
827862
# drawing past the node of a ConjectureData.for_choices data.
@@ -1249,6 +1284,7 @@ def draw(
12491284
and self.index < len(self.prefix)
12501285
and isinstance(hole := self.prefix[self.index], ValueHole)
12511286
):
1287+
self._inverting = True
12521288
try:
12531289
inverted = unwrapped._invert(hole.value)
12541290
except CannotInvert:
@@ -1259,6 +1295,8 @@ def draw(
12591295
+ inverted
12601296
+ tuple(self.prefix[self.index + 1 :])
12611297
)
1298+
finally:
1299+
self._inverting = False
12621300

12631301
span_index = self.__span_record.span_count
12641302
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 around each element. Fixed-size collections draw no
364+
booleans at all; variable-size ones draw a continuation boolean before
365+
each element (forced while below min_size, but forced draws still consume
366+
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

0 commit comments

Comments
 (0)