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

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 defaultdict 

12from collections.abc import Iterable, Sequence 

13from random import Random 

14from typing import Callable, Optional 

15 

16from hypothesis.internal.conjecture.junkdrawer import LazySequenceCopy 

17 

18 

19def prefix_selection_order( 

20 prefix: Sequence[int], 

21) -> Callable[[int, int], Iterable[int]]: 

22 """Select choices starting from ``prefix```, 

23 preferring to move left then wrapping around 

24 to the right.""" 

25 

26 def selection_order(depth: int, n: int) -> Iterable[int]: 

27 if depth < len(prefix): 

28 i = prefix[depth] 

29 if i >= n: 

30 i = n - 1 

31 yield from range(i, -1, -1) 

32 yield from range(n - 1, i, -1) 

33 else: 

34 yield from range(n - 1, -1, -1) 

35 

36 return selection_order 

37 

38 

39def random_selection_order(random: Random) -> Callable[[int, int], Iterable[int]]: 

40 """Select choices uniformly at random.""" 

41 

42 def selection_order(depth: int, n: int) -> Iterable[int]: 

43 pending = LazySequenceCopy(range(n)) 

44 while pending: 

45 i = random.randrange(0, len(pending)) 

46 yield pending.pop(i) 

47 

48 return selection_order 

49 

50 

51class Chooser: 

52 """A source of nondeterminism for use in shrink passes.""" 

53 

54 def __init__( 

55 self, 

56 tree: "ChoiceTree", 

57 selection_order: Callable[[int, int], Iterable[int]], 

58 ): 

59 self.__selection_order = selection_order 

60 self.__node_trail = [tree.root] 

61 self.__choices: list[int] = [] 

62 self.__finished = False 

63 

64 def choose( 

65 self, 

66 values: Sequence[int], 

67 condition: Callable[[int], bool] = lambda x: True, 

68 ) -> int: 

69 """Return some element of values satisfying the condition 

70 that will not lead to an exhausted branch, or raise DeadBranch 

71 if no such element exist". 

72 """ 

73 assert not self.__finished 

74 node = self.__node_trail[-1] 

75 if node.live_child_count is None: 

76 node.live_child_count = len(values) 

77 node.n = len(values) 

78 

79 assert node.live_child_count > 0 or len(values) == 0 

80 

81 for i in self.__selection_order(len(self.__choices), len(values)): 

82 if node.live_child_count == 0: 

83 break 

84 if not node.children[i].exhausted: 

85 v = values[i] 

86 if condition(v): 

87 self.__choices.append(i) 

88 self.__node_trail.append(node.children[i]) 

89 return v 

90 else: 

91 node.children[i] = DeadNode 

92 node.live_child_count -= 1 

93 assert node.live_child_count == 0 

94 raise DeadBranch 

95 

96 def finish(self) -> Sequence[int]: 

97 """Record the decisions made in the underlying tree and return 

98 a prefix that can be used for the next Chooser to be used.""" 

99 self.__finished = True 

100 assert len(self.__node_trail) == len(self.__choices) + 1 

101 

102 result = tuple(self.__choices) 

103 

104 self.__node_trail[-1].live_child_count = 0 

105 while len(self.__node_trail) > 1 and self.__node_trail[-1].exhausted: 

106 self.__node_trail.pop() 

107 assert len(self.__node_trail) == len(self.__choices) 

108 i = self.__choices.pop() 

109 target = self.__node_trail[-1] 

110 target.children[i] = DeadNode 

111 assert target.live_child_count is not None 

112 target.live_child_count -= 1 

113 

114 return result 

115 

116 

117class ChoiceTree: 

118 """Records sequences of choices made during shrinking so that we 

119 can track what parts of a pass has run. Used to create Chooser 

120 objects that are the main interface that a pass uses to make 

121 decisions about what to do. 

122 """ 

123 

124 def __init__(self) -> None: 

125 self.root = TreeNode() 

126 

127 @property 

128 def exhausted(self) -> bool: 

129 return self.root.exhausted 

130 

131 def step( 

132 self, 

133 selection_order: Callable[[int, int], Iterable[int]], 

134 f: Callable[[Chooser], None], 

135 ) -> Sequence[int]: 

136 assert not self.exhausted 

137 

138 chooser = Chooser(self, selection_order) 

139 try: 

140 f(chooser) 

141 except DeadBranch: 

142 pass 

143 return chooser.finish() 

144 

145 

146class TreeNode: 

147 def __init__(self) -> None: 

148 self.children: dict[int, TreeNode] = defaultdict(TreeNode) 

149 self.live_child_count: Optional[int] = None 

150 self.n: Optional[int] = None 

151 

152 @property 

153 def exhausted(self) -> bool: 

154 return self.live_child_count == 0 

155 

156 

157DeadNode = TreeNode() 

158DeadNode.live_child_count = 0 

159 

160 

161class DeadBranch(Exception): 

162 pass