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
11from hypothesis.internal.conjecture.shrinking.common import Shrinker
12from hypothesis.internal.conjecture.shrinking.ordering import Ordering
13
14
15def identity(v):
16 return v
17
18
19class Collection(Shrinker):
20 def setup(self, *, ElementShrinker, to_order=identity, from_order=identity):
21 self.ElementShrinker = ElementShrinker
22 self.to_order = to_order
23 self.from_order = from_order
24
25 def make_immutable(self, value):
26 return tuple(value)
27
28 def left_is_better(self, left, right):
29 if len(left) < len(right):
30 return True
31
32 # examine elements one by one from the left until an element differs.
33 for v1, v2 in zip(left, right):
34 if self.to_order(v1) == self.to_order(v2):
35 continue
36 return self.to_order(v1) < self.to_order(v2)
37
38 # equal length and all values were equal by our ordering, so must be equal
39 # by our ordering.
40 assert list(map(self.to_order, left)) == list(map(self.to_order, right))
41 return False
42
43 def run_step(self):
44 # try deleting each element in turn, starting from the back
45 # TODO_BETTER_SHRINK: adaptively delete here by deleting larger chunks at once
46 # if early deletes succeed. use find_integer. turns O(n) into O(log(n))
47 for i in reversed(range(len(self.current))):
48 self.consider(self.current[:i] + self.current[i + 1 :])
49
50 # then try reordering
51 Ordering.shrink(self.current, self.consider, key=self.to_order)
52
53 # then try minimizing each element in turn
54 for i, val in enumerate(self.current):
55 self.ElementShrinker.shrink(
56 self.to_order(val),
57 lambda v: self.consider(
58 self.current[:i] + (self.from_order(v),) + self.current[i + 1 :]
59 ),
60 )