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/.
10
11"""This module implements various useful common functions for shrinking tasks."""
12
13
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."""
18
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
35
36 self.__predicate = predicate
37 self.__seen = set()
38 self.debugging_enabled = debug
39
40 @property
41 def calls(self):
42 return len(self.__seen)
43
44 def __repr__(self):
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 )
51
52 def setup(self, **kwargs):
53 """Runs initial setup code.
54
55 Convenience function for children that doesn't require messing
56 with the signature of init.
57 """
58
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 )
68
69 def call_shrinker(self, other_class, initial, predicate, **kwargs):
70 """Calls another shrinker class, passing through the relevant context
71 variables.
72
73 Note we explicitly do not pass through full.
74 """
75
76 return other_class.shrink(initial, predicate, **kwargs)
77
78 def debug(self, *args):
79 if self.debugging_enabled:
80 print("DEBUG", self, *args)
81
82 @classmethod
83 def shrink(cls, initial, predicate, **kwargs):
84 """Shrink the value ``initial`` subject to the constraint that it
85 satisfies ``predicate``.
86
87 Returns the shrunk value.
88 """
89 shrinker = cls(initial, predicate, **kwargs)
90 shrinker.run()
91 return shrinker.current
92
93 def run(self):
94 """Run for an appropriate number of steps to improve the current value.
95
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")
109
110 def incorporate(self, value):
111 """Try using ``value`` as a possible candidate improvement.
112
113 Return True if it works.
114 """
115 value = self.make_immutable(value)
116 self.check_invariants(value)
117 if not self.left_is_better(value, self.current):
118 if value != self.current and (value == value):
119 self.debug(f"Rejected {value!r} as worse than {self.current=}")
120 return False
121 if value in self.__seen:
122 return False
123 self.__seen.add(value)
124 if self.__predicate(value):
125 self.debug(f"shrinking to {value!r}")
126 self.changes += 1
127 self.current = value
128 return True
129 return False
130
131 def consider(self, value):
132 """Returns True if make_immutable(value) == self.current after calling
133 self.incorporate(value)."""
134 self.debug(f"considering {value}")
135 value = self.make_immutable(value)
136 if value == self.current:
137 return True
138 return self.incorporate(value)
139
140 def make_immutable(self, value):
141 """Convert value into an immutable (and hashable) representation of
142 itself.
143
144 It is these immutable versions that the shrinker will work on.
145
146 Defaults to just returning the value.
147 """
148 return value
149
150 def check_invariants(self, value):
151 """Make appropriate assertions about the value to ensure that it is
152 valid for this shrinker.
153
154 Does nothing by default.
155 """
156
157 def short_circuit(self):
158 """Possibly attempt to do some shrinking.
159
160 If this returns True, the ``run`` method will terminate early
161 without doing any more work.
162 """
163 return False
164
165 def left_is_better(self, left, right):
166 """Returns True if the left is strictly simpler than the right
167 according to the standards of this shrinker."""
168 raise NotImplementedError
169
170 def run_step(self):
171 """Run a single step of the main shrink loop, attempting to improve the
172 current value."""
173 raise NotImplementedError