Skip to content

Commit 7e309df

Browse files
committed
Invert dictionaries, unique lists with tuple_suffixes, and fixed_dictionaries
UniqueListStrategy._invert now splits each (key, *suffix) element between the elements strategy and the tuple_suffixes TupleStrategy, with uniqueness checked over the keys alone; UniqueSampledListStrategy gains the same suffix support on top of its pool-relative index encoding. MappedStrategy._invert handles dict-like packs - the shape st.dictionaries maps over a unique list of pairs - by inverting the value's items list. FixedDictStrategy._invert encodes required values in declaration order, optional-key selections mirroring do_draw's swap-with-last pop, and an identity shuffle for the final ordering, which mapping equality ignores. Co-Authored-By: Claude Fable 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01KbvBiusz22hjM4bxRcAtEB
1 parent 77ca292 commit 7e309df

4 files changed

Lines changed: 187 additions & 19 deletions

File tree

‎hypothesis/RELEASE.rst‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,8 @@ specific branch can now be re-encoded and shrunk as if generated by the wider
66
branch when the strategies involved include
77
:func:`~hypothesis.strategies.sampled_from`,
88
:func:`~hypothesis.strategies.lists`, :func:`~hypothesis.strategies.tuples`,
9+
:func:`~hypothesis.strategies.dictionaries` and
10+
:func:`~hypothesis.strategies.fixed_dictionaries`,
911
:func:`~hypothesis.strategies.builds` of a dataclass,
1012
:func:`~hypothesis.strategies.permutations`, the
1113
:func:`~hypothesis.strategies.dates` family of strategies, and filtered,

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

Lines changed: 99 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -370,19 +370,52 @@ def not_yet_in_unique_list(val: Ex) -> bool: # type: ignore # covariant type pa
370370
assert self.max_size >= len(result) >= self.min_size
371371
return result
372372

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)
373+
def _check_unique_keys(self, elements: list[Any]) -> None:
381374
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
375+
try:
376+
keys = list(map(keyfunc, elements))
377+
unique = len(set(keys)) == len(keys)
378+
except Exception:
379+
raise CannotInvert(
380+
f"could not compute uniqueness keys for {self!r}"
381+
) from None
382+
if not unique:
383+
raise CannotInvert(f"{elements!r} has duplicate keys for {self!r}")
384+
385+
def _split_suffixed(self, value: Any) -> list[Any]:
386+
# With tuple_suffixes, each element is (key, *suffix): the key drawn
387+
# from element_strategy, then the suffix from tuple_suffixes.
388+
# Uniqueness applies to the key alone.
389+
if not isinstance(value, list):
390+
raise CannotInvert(f"{value!r} is not a list")
391+
if not all(isinstance(e, tuple) and e for e in value):
392+
raise CannotInvert(f"{value!r} is not a list of nonempty tuples")
393+
return [e[0] for e in value]
394+
395+
def _invert(self, value: Any) -> tuple[ChoiceT, ...]:
396+
if self.tuple_suffixes is None:
397+
# A valid unique list draws exactly like a ListStrategy, since
398+
# every element passes the uniqueness filter on its first draw.
399+
self._check_unique_keys(value)
400+
return ListStrategy._invert(self, value)
401+
self._check_unique_keys(self._split_suffixed(value))
402+
if not (self.min_size <= len(value) <= self.max_size):
403+
raise CannotInvert(
404+
f"len={len(value)} outside "
405+
f"[{self.min_size}, {self.max_size!r}] for {self!r}"
406+
)
407+
elements = cu.invert_many(self.min_size, self.max_size)
408+
choices: list[ChoiceT] = []
409+
for i, element in enumerate(value):
410+
choices.extend(elements.more())
411+
try:
412+
choices.extend(self.element_strategy._invert(element[0]))
413+
choices.extend(self.tuple_suffixes._invert(tuple(element[1:])))
414+
except CannotInvert as exc:
415+
add_note(exc, f"at index {i} of {value!r}, strategy={self!r}")
416+
raise
417+
choices.extend(elements.done())
418+
return tuple(choices)
386419

387420

388421
class UniqueSampledListStrategy(UniqueListStrategy):
@@ -420,22 +453,21 @@ def do_draw(self, data: ConjectureData) -> list[Ex]:
420453
return result
421454

422455
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")
425456
if not isinstance(value, list):
426457
raise CannotInvert(f"{value!r} is not a list")
427458
if not (self.min_size <= len(value) <= self.max_size):
428459
raise CannotInvert(
429460
f"len={len(value)} outside "
430461
f"[{self.min_size}, {self.max_size!r}] for {self!r}"
431462
)
463+
targets = value if self.tuple_suffixes is None else self._split_suffixed(value)
432464
# do_draw indexes into the pool of not-yet-drawn elements, so each
433465
# index is relative to what remains, not to the original elements.
434466
assert isinstance(self.element_strategy, SampledFromStrategy)
435467
remaining = list(self.element_strategy.elements)
436468
elements = cu.invert_many(self.min_size, self.max_size)
437469
choices: list[ChoiceT] = []
438-
for i, target in enumerate(value):
470+
for i, (element, target) in enumerate(zip(value, targets, strict=True)):
439471
choices.extend(elements.more())
440472
for j, candidate in enumerate(remaining):
441473
if equal_values(self.element_strategy._transform(candidate), target):
@@ -447,6 +479,12 @@ def _invert(self, value: Any) -> tuple[ChoiceT, ...]:
447479
f"at index {i} of {value!r}: {target!r} is not among the "
448480
f"remaining elements of {self!r}"
449481
)
482+
if self.tuple_suffixes is not None:
483+
try:
484+
choices.extend(self.tuple_suffixes._invert(tuple(element[1:])))
485+
except CannotInvert as exc:
486+
add_note(exc, f"at index {i} of {value!r}, strategy={self!r}")
487+
raise
450488
if remaining:
451489
# with an exhausted pool, do_draw stops without drawing a boolean
452490
choices.extend(elements.done())
@@ -513,6 +551,52 @@ def do_draw(self, data: ConjectureData) -> Mapping[Any, Any]:
513551
)
514552
return value
515553

554+
def _invert(self, value: Any) -> tuple[ChoiceT, ...]:
555+
if not isinstance(value, Mapping):
556+
raise CannotInvert(f"{value!r} is not a mapping")
557+
optional = self.optional or {}
558+
if any(k not in value for k in self.mapping) or any(
559+
k not in self.mapping and k not in optional for k in value
560+
):
561+
raise CannotInvert(f"{value!r} has the wrong keys for {self!r}")
562+
563+
choices: list[ChoiceT] = []
564+
npairs = len(self.mapping)
565+
for key, strategy in self.mapping.items():
566+
try:
567+
choices.extend(strategy._invert(value[key]))
568+
except CannotInvert as exc:
569+
add_note(exc, f"at key {key!r} of {value!r}, strategy={self!r}")
570+
raise
571+
572+
if self.optional is not None:
573+
# do_draw selects each present optional key by its index in the
574+
# remaining-keys list, which pops via swap-with-last.
575+
remaining = [k for k, v in self.optional.items() if not v.is_empty]
576+
present = [k for k in remaining if k in value and k not in self.mapping]
577+
if npairs + len(present) != len(value):
578+
# a present optional key whose strategy is empty
579+
raise CannotInvert(f"{value!r} has the wrong keys for {self!r}")
580+
selector = cu.invert_many(0, len(remaining))
581+
for key in present:
582+
choices.extend(selector.more())
583+
j = remaining.index(key)
584+
choices.append(j)
585+
remaining[-1], remaining[j] = remaining[j], remaining[-1]
586+
remaining.pop()
587+
try:
588+
choices.extend(self.optional[key]._invert(value[key]))
589+
except CannotInvert as exc:
590+
add_note(exc, f"at key {key!r} of {value!r}, strategy={self!r}")
591+
raise
592+
choices.extend(selector.done())
593+
npairs += len(present)
594+
595+
# an identity shuffle for do_draw's final fisher_yates_shuffle of the
596+
# pairs; mappings compare equal regardless of iteration order
597+
choices.extend(range(npairs - 1))
598+
return tuple(choices)
599+
516600
def calc_is_empty(self, recur: RecurT) -> bool:
517601
return recur(self.fixed)
518602

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

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1124,6 +1124,18 @@ def do_draw(self, data: ConjectureData) -> MappedTo:
11241124
data.stop_span(discard=True)
11251125
raise UnsatisfiedAssumption
11261126

1127+
def _invert(self, value: Any) -> tuple[ChoiceT, ...]:
1128+
# map() is not invertible in general, but a dict-like pack - e.g. the
1129+
# dict_class which st.dictionaries maps over a unique list of
1130+
# (key, value) tuples - inverts as its list of items.
1131+
if (
1132+
isinstance(self.pack, type)
1133+
and issubclass(self.pack, abc.Mapping)
1134+
and isinstance(value, self.pack)
1135+
):
1136+
return self.mapped_strategy._invert(list(value.items()))
1137+
raise CannotInvert(f"cannot invert {self!r} (value={value!r})")
1138+
11271139
@property
11281140
def branches(self) -> Sequence[SearchStrategy[MappedTo]]:
11291141
return [

‎hypothesis/tests/cover/test_invert.py‎

Lines changed: 74 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@
1212
import datetime as dt
1313
import math
1414
import zoneinfo
15+
from collections import OrderedDict
1516

1617
import pytest
1718

@@ -301,6 +302,50 @@ def test_unique_sampled_lists(data):
301302
check_roundtrip_many(st.lists(st.sampled_from(elements), unique=True), data)
302303

303304

305+
@given(st.data())
306+
def test_unique_lists_of_tuples(data):
307+
# rearranged into element_strategy=integers plus tuple_suffixes
308+
strategy = st.lists(st.tuples(st.integers(), st.text()), unique_by=lambda t: t[0])
309+
check_roundtrip_many(strategy, data)
310+
311+
312+
@given(st.data())
313+
def test_dictionaries(data):
314+
min_size = data.draw(st.integers(0, 3))
315+
max_size = data.draw(st.none() | st.integers(min_size + 1, min_size + 5))
316+
strategy = st.dictionaries(
317+
st.text(), st.integers(), min_size=min_size, max_size=max_size
318+
)
319+
check_roundtrip_many(strategy, data)
320+
321+
322+
@given(st.data())
323+
def test_dictionaries_with_dict_class(data):
324+
strategy = st.dictionaries(st.text(), st.integers(), dict_class=OrderedDict)
325+
check_roundtrip_many(strategy, data)
326+
327+
328+
@given(st.data())
329+
def test_dictionaries_sampled_keys(data):
330+
# small integer keys draw from a fixed pool via UniqueSampledListStrategy
331+
check_roundtrip_many(st.dictionaries(st.integers(0, 5), st.booleans()), data)
332+
333+
334+
@given(st.data())
335+
def test_fixed_dictionaries(data):
336+
check_roundtrip_many(
337+
st.fixed_dictionaries({"a": st.integers(), "b": st.booleans()}), data
338+
)
339+
340+
341+
@given(st.data())
342+
def test_fixed_dictionaries_with_optional(data):
343+
strategy = st.fixed_dictionaries(
344+
{"a": st.integers()}, optional={"b": st.integers(), "c": st.text()}
345+
)
346+
check_roundtrip_many(strategy, data)
347+
348+
304349
@given(st.data())
305350
def test_deferred(data):
306351
check_roundtrip_many(st.deferred(lambda: st.integers()), data)
@@ -353,6 +398,21 @@ def test_roundtrip_explicit(strategy, value):
353398
(st.lists(st.integers(), max_size=2), [1, 2, 3]),
354399
(st.lists(st.integers(), unique=True), [1, 1]),
355400
(st.lists(st.sampled_from([1, 2, 3]), unique=True), [1, 4]),
401+
# duplicate keys, unrepresentable in a dict but not in the list form
402+
(
403+
st.lists(st.tuples(st.integers(), st.text()), unique_by=lambda t: t[0]),
404+
[(1, "x"), (1, "y")],
405+
),
406+
(st.dictionaries(st.text(), st.integers()), {1: 2}),
407+
(st.dictionaries(st.text(), st.integers()), [("a", 1)]),
408+
(st.dictionaries(st.text(), st.integers(), max_size=1), {"a": 1, "b": 2}),
409+
(st.fixed_dictionaries({"a": st.integers()}), {"a": 1, "z": 2}),
410+
(st.fixed_dictionaries({"a": st.integers()}), {}),
411+
(st.fixed_dictionaries({"a": st.integers()}), {"a": "not an int"}),
412+
(
413+
st.fixed_dictionaries({"a": st.integers()}, optional={"b": st.nothing()}),
414+
{"a": 1, "b": 2},
415+
),
356416
(st.tuples(st.integers(), st.booleans()), (5,)),
357417
(st.tuples(st.integers(), st.booleans()), (5, True, "extra")),
358418
(st.floats(allow_nan=True).filter(math.isnan), 1.0),
@@ -425,12 +485,8 @@ def test_out_of_image_raises(strategy, value):
425485
# a mapped element strategy is not rewritten to OneCharStringStrategy
426486
# (unlike e.g. sampled_from of characters, which is)
427487
(st.text(st.characters().map(str.upper), max_size=5), "A"),
428-
# dictionaries build unique lists of (key, value) tuples via
429-
# tuple_suffixes, which inversion cannot pick apart
430-
(st.dictionaries(st.integers(), st.integers()), {1: 2}),
431488
(st.sets(st.integers()), {1}),
432489
(st.frozensets(st.integers()), frozenset()),
433-
(st.fixed_dictionaries({"a": st.integers()}), {"a": 1}),
434490
(st.builds(lambda x, y: x + y, st.integers(), st.integers()), 3),
435491
(st.shared(st.integers()), 0),
436492
(
@@ -505,6 +561,20 @@ def test_unimplemented_raises(strategy, value):
505561
(2022, 5, 15),
506562
),
507563
(st.timedeltas(), dt.timedelta(days=2, seconds=3), (2, 3, 0)),
564+
(st.dictionaries(st.text(), st.integers()), {}, (False,)),
565+
(st.dictionaries(st.text(), st.integers()), {"a": 1}, (True, "a", 1, False)),
566+
# required value, then presence-selection of the optional key and its
567+
# value, then an identity shuffle of the two pairs
568+
(
569+
st.fixed_dictionaries({"a": st.integers()}, optional={"b": st.booleans()}),
570+
{"a": 5, "b": True},
571+
(5, True, 0, True, False, 0),
572+
),
573+
(
574+
st.fixed_dictionaries({"a": st.integers()}, optional={"b": st.booleans()}),
575+
{"a": 5},
576+
(5, False),
577+
),
508578
(st.integers().filter(lambda x: x > 0), 5, (5,)),
509579
],
510580
)

0 commit comments

Comments
 (0)