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

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.shrinking.common import Shrinker 

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

15from hypothesis.internal.conjecture.utils import identity 

16 

17 

18class Collection(Shrinker): 

19 def setup( 

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

21 ): 

22 self.ElementShrinker = ElementShrinker 

23 self.to_order = to_order 

24 self.from_order = from_order 

25 self.min_size = min_size 

26 

27 def make_immutable(self, value): 

28 return tuple(value) 

29 

30 def short_circuit(self): 

31 zero = self.from_order(0) 

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

33 

34 def left_is_better(self, left, right): 

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

36 return True 

37 

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

39 for v1, v2 in zip(left, right): 

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

41 continue 

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

43 

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

45 # by our ordering. 

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

47 return False 

48 

49 def run_step(self): 

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

51 # short_circuit. 

52 zero = self.from_order(0) 

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

54 

55 # try deleting each element in turn, starting from the back 

56 # TODO_BETTER_SHRINK: adaptively delete here by deleting larger chunks at once 

57 # if early deletes succeed. use find_integer. turns O(n) into O(log(n)) 

58 for i in reversed(range(len(self.current))): 

59 self.consider(self.current[:i] + self.current[i + 1 :]) 

60 

61 # then try reordering 

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

63 

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

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

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

67 for val in duplicated: 

68 self.ElementShrinker.shrink( 

69 self.to_order(val), 

70 lambda v: self.consider( 

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

72 ), 

73 ) 

74 

75 # then try minimizing each element in turn 

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

77 self.ElementShrinker.shrink( 

78 self.to_order(val), 

79 lambda v: self.consider( 

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

81 ), 

82 )