Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# This file is part of Hypothesis, which may be found at
2# https://github.com/HypothesisWorks/hypothesis/
3#
4# Copyright the Hypothesis Authors.
5# Individual contributors are listed in AUTHORS.rst and the git log.
6#
7# This Source Code Form is subject to the terms of the Mozilla Public License,
8# v. 2.0. If a copy of the MPL was not distributed with this file, You can
9# obtain one at https://mozilla.org/MPL/2.0/.
11"""This module implements various useful common functions for shrinking tasks."""
14class Shrinker:
15 """A Shrinker object manages a single value and a predicate it should
16 satisfy, and attempts to improve it in some direction, making it smaller
17 and simpler."""
19 def __init__(
20 self,
21 initial,
22 predicate,
23 *,
24 full=False,
25 debug=False,
26 name=None,
27 **kwargs,
28 ):
29 self.setup(**kwargs)
30 self.current = self.make_immutable(initial)
31 self.initial = self.current
32 self.full = full
33 self.changes = 0
34 self.name = name
36 self.__predicate = predicate
37 self.__seen = {self.make_canonical(self.current)}
38 self.debugging_enabled = debug
40 @property
41 def calls(self) -> int:
42 return len(self.__seen)
44 def __repr__(self) -> str:
45 return "{}({}initial={!r}, current={!r})".format(
46 type(self).__name__,
47 "" if self.name is None else f"{self.name!r}, ",
48 self.initial,
49 self.current,
50 )
52 def setup(self, **kwargs):
53 """Runs initial setup code.
55 Convenience function for children that doesn't require messing
56 with the signature of init.
57 """
59 def delegate(self, other_class, convert_to, convert_from, **kwargs):
60 """Delegates shrinking to another shrinker class, by converting the
61 current value to and from it with provided functions."""
62 self.call_shrinker(
63 other_class,
64 convert_to(self.current),
65 lambda v: self.consider(convert_from(v)),
66 **kwargs,
67 )
69 def call_shrinker(self, other_class, initial, predicate, **kwargs):
70 """Calls another shrinker class, passing through the relevant context
71 variables.
73 Note we explicitly do not pass through full.
74 """
76 return other_class.shrink(initial, predicate, **kwargs)
78 def debug(self, *args: object) -> None:
79 if self.debugging_enabled:
80 print("DEBUG", self, *args)
82 @classmethod
83 def shrink(cls, initial, predicate, **kwargs):
84 """Shrink the value ``initial`` subject to the constraint that it
85 satisfies ``predicate``.
87 Returns the shrunk value.
88 """
89 shrinker = cls(initial, predicate, **kwargs)
90 shrinker.run()
91 return shrinker.current
93 def run(self):
94 """Run for an appropriate number of steps to improve the current value.
96 If self.full is True, will run until no further improvements can
97 be found.
98 """
99 if self.short_circuit():
100 return
101 if self.full:
102 prev = -1
103 while self.changes != prev:
104 prev = self.changes
105 self.run_step()
106 else:
107 self.run_step()
108 self.debug("COMPLETE")
110 def consider(self, value):
111 """Try using ``value`` as a possible candidate improvement.
113 Return True if self.current is canonically equal to value after the call, either because
114 the value was incorporated as an improvement or because it had that value already.
115 """
116 value = self.make_immutable(value)
117 self.debug(f"considering {value!r}")
118 canonical = self.make_canonical(value)
119 if canonical == self.make_canonical(self.current):
120 return True
121 if canonical in self.__seen:
122 return False
123 self.__seen.add(canonical)
124 self.check_invariants(value)
125 if not self.left_is_better(value, self.current):
126 self.debug(f"Rejected {value!r} as no better than {self.current=}")
127 return False
128 if self.__predicate(value):
129 self.debug(f"shrinking to {value!r}")
130 self.changes += 1
131 self.current = value
132 return True
133 else:
134 self.debug(f"Rejected {value!r} not satisfying predicate")
135 return False
137 def make_canonical(self, value):
138 """Convert immutable value into a canonical and hashable, but not necessarily equal,
139 representation of itself.
141 This representation is used only for tracking already-seen values, not passed to the
142 shrinker.
144 Defaults to just returning the (immutable) input value.
145 """
146 return value
148 def make_immutable(self, value):
149 """Convert value into an immutable representation of itself.
151 It is these immutable versions that the shrinker will work on.
153 Defaults to just returning the value.
154 """
155 return value
157 def check_invariants(self, value):
158 """Make appropriate assertions about the value to ensure that it is
159 valid for this shrinker.
161 Does nothing by default.
162 """
164 def short_circuit(self):
165 """Possibly attempt to do some shrinking.
167 If this returns True, the ``run`` method will terminate early
168 without doing any more work.
169 """
170 return False
172 def left_is_better(self, left, right):
173 """Returns True if the left is strictly simpler than the right
174 according to the standards of this shrinker."""
175 raise NotImplementedError
177 def run_step(self):
178 """Run a single step of the main shrink loop, attempting to improve the
179 current value."""
180 raise NotImplementedError