Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/hypothesis/internal/conjecture/shrinking/collection.py: 27%

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 collections import Counter 

12 

13from hypothesis.internal.conjecture.junkdrawer import find_integer 

14from hypothesis.internal.conjecture.shrinking.common import Shrinker 

15from hypothesis.internal.conjecture.shrinking.ordering import Ordering 

16from hypothesis.internal.conjecture.utils import identity 

17 

18 

19class Collection(Shrinker): 

20 def setup( 

21 self, *, ElementShrinker, min_size, to_order=identity, from_order=identity 

22 ): 

23 self.ElementShrinker = ElementShrinker 

24 self.to_order = to_order 

25 self.from_order = from_order 

26 self.min_size = min_size 

27 

28 def make_immutable(self, value): 

29 return tuple(value) 

30 

31 def short_circuit(self): 

32 zero = self.from_order(0) 

33 return self.consider([zero] * self.min_size) 

34 

35 def left_is_better(self, left, right): 

36 if len(left) < len(right): 

37 return True 

38 

39 # examine elements one by one from the left until an element differs. 

40 for v1, v2 in zip(left, right, strict=False): 

41 if self.to_order(v1) == self.to_order(v2): 

42 continue 

43 return self.to_order(v1) < self.to_order(v2) 

44 

45 # equal length and all values were equal by our ordering, so must be equal 

46 # by our ordering. 

47 assert list(map(self.to_order, left)) == list(map(self.to_order, right)) 

48 return False 

49 

50 def run_step(self): 

51 # try all-zero first; we already considered all-zero-and-smallest in 

52 # short_circuit. 

53 zero = self.from_order(0) 

54 self.consider([zero] * len(self.current)) 

55 

56 # try deleting elements, starting from the back. We adaptively grow the 

57 # chunk we delete via find_integer, so a run of deletable elements costs 

58 # O(log(n)) calls rather than O(n). 

59 i = len(self.current) - 1 

60 while i >= 0: 

61 base = self.current 

62 

63 def delete_k(k, *, i=i, base=base): 

64 # delete the k elements ending at index i, i.e. base[i - k + 1 : i + 1] 

65 return k <= i + 1 and self.consider(base[: i - k + 1] + base[i + 1 :]) 

66 

67 # advance past the (possibly deleted) chunk; max(k, 1) ensures progress 

68 i -= max(find_integer(delete_k), 1) 

69 

70 # then try reordering 

71 Ordering.shrink(self.current, self.consider, key=self.to_order) 

72 

73 # then try minimizing all duplicated elements together simultaneously. This 

74 # helps in cases like https://github.com/HypothesisWorks/hypothesis/issues/4286 

75 duplicated = {val for val, count in Counter(self.current).items() if count > 1} 

76 for val in duplicated: 

77 self.ElementShrinker.shrink( 

78 self.to_order(val), 

79 lambda v: self.consider( 

80 tuple(self.from_order(v) if x == val else x for x in self.current) 

81 ), 

82 ) 

83 

84 # then try minimizing each element in turn 

85 for i, val in enumerate(self.current): 

86 self.ElementShrinker.shrink( 

87 self.to_order(val), 

88 lambda v: self.consider( 

89 self.current[:i] + (self.from_order(v),) + self.current[i + 1 :] 

90 ), 

91 )