# Python code coverage for Lib/test/test_sort.py

# | count | content |
---|---|---|

1 | n/a | from test import support |

2 | n/a | import random |

3 | n/a | import unittest |

4 | n/a | from functools import cmp_to_key |

5 | n/a | |

6 | n/a | verbose = support.verbose |

7 | n/a | nerrors = 0 |

8 | n/a | |

9 | n/a | |

10 | n/a | def check(tag, expected, raw, compare=None): |

11 | n/a | global nerrors |

12 | n/a | |

13 | n/a | if verbose: |

14 | n/a | print(" checking", tag) |

15 | n/a | |

16 | n/a | orig = raw[:] # save input in case of error |

17 | n/a | if compare: |

18 | n/a | raw.sort(key=cmp_to_key(compare)) |

19 | n/a | else: |

20 | n/a | raw.sort() |

21 | n/a | |

22 | n/a | if len(expected) != len(raw): |

23 | n/a | print("error in", tag) |

24 | n/a | print("length mismatch;", len(expected), len(raw)) |

25 | n/a | print(expected) |

26 | n/a | print(orig) |

27 | n/a | print(raw) |

28 | n/a | nerrors += 1 |

29 | n/a | return |

30 | n/a | |

31 | n/a | for i, good in enumerate(expected): |

32 | n/a | maybe = raw[i] |

33 | n/a | if good is not maybe: |

34 | n/a | print("error in", tag) |

35 | n/a | print("out of order at index", i, good, maybe) |

36 | n/a | print(expected) |

37 | n/a | print(orig) |

38 | n/a | print(raw) |

39 | n/a | nerrors += 1 |

40 | n/a | return |

41 | n/a | |

42 | n/a | class TestBase(unittest.TestCase): |

43 | n/a | def testStressfully(self): |

44 | n/a | # Try a variety of sizes at and around powers of 2, and at powers of 10. |

45 | n/a | sizes = [0] |

46 | n/a | for power in range(1, 10): |

47 | n/a | n = 2 ** power |

48 | n/a | sizes.extend(range(n-1, n+2)) |

49 | n/a | sizes.extend([10, 100, 1000]) |

50 | n/a | |

51 | n/a | class Complains(object): |

52 | n/a | maybe_complain = True |

53 | n/a | |

54 | n/a | def __init__(self, i): |

55 | n/a | self.i = i |

56 | n/a | |

57 | n/a | def __lt__(self, other): |

58 | n/a | if Complains.maybe_complain and random.random() < 0.001: |

59 | n/a | if verbose: |

60 | n/a | print(" complaining at", self, other) |

61 | n/a | raise RuntimeError |

62 | n/a | return self.i < other.i |

63 | n/a | |

64 | n/a | def __repr__(self): |

65 | n/a | return "Complains(%d)" % self.i |

66 | n/a | |

67 | n/a | class Stable(object): |

68 | n/a | def __init__(self, key, i): |

69 | n/a | self.key = key |

70 | n/a | self.index = i |

71 | n/a | |

72 | n/a | def __lt__(self, other): |

73 | n/a | return self.key < other.key |

74 | n/a | |

75 | n/a | def __repr__(self): |

76 | n/a | return "Stable(%d, %d)" % (self.key, self.index) |

77 | n/a | |

78 | n/a | for n in sizes: |

79 | n/a | x = list(range(n)) |

80 | n/a | if verbose: |

81 | n/a | print("Testing size", n) |

82 | n/a | |

83 | n/a | s = x[:] |

84 | n/a | check("identity", x, s) |

85 | n/a | |

86 | n/a | s = x[:] |

87 | n/a | s.reverse() |

88 | n/a | check("reversed", x, s) |

89 | n/a | |

90 | n/a | s = x[:] |

91 | n/a | random.shuffle(s) |

92 | n/a | check("random permutation", x, s) |

93 | n/a | |

94 | n/a | y = x[:] |

95 | n/a | y.reverse() |

96 | n/a | s = x[:] |

97 | n/a | check("reversed via function", y, s, lambda a, b: (b>a)-(b<a)) |

98 | n/a | |

99 | n/a | if verbose: |

100 | n/a | print(" Checking against an insane comparison function.") |

101 | n/a | print(" If the implementation isn't careful, this may segfault.") |

102 | n/a | s = x[:] |

103 | n/a | s.sort(key=cmp_to_key(lambda a, b: int(random.random() * 3) - 1)) |

104 | n/a | check("an insane function left some permutation", x, s) |

105 | n/a | |

106 | n/a | if len(x) >= 2: |

107 | n/a | def bad_key(x): |

108 | n/a | raise RuntimeError |

109 | n/a | s = x[:] |

110 | n/a | self.assertRaises(RuntimeError, s.sort, key=bad_key) |

111 | n/a | |

112 | n/a | x = [Complains(i) for i in x] |

113 | n/a | s = x[:] |

114 | n/a | random.shuffle(s) |

115 | n/a | Complains.maybe_complain = True |

116 | n/a | it_complained = False |

117 | n/a | try: |

118 | n/a | s.sort() |

119 | n/a | except RuntimeError: |

120 | n/a | it_complained = True |

121 | n/a | if it_complained: |

122 | n/a | Complains.maybe_complain = False |

123 | n/a | check("exception during sort left some permutation", x, s) |

124 | n/a | |

125 | n/a | s = [Stable(random.randrange(10), i) for i in range(n)] |

126 | n/a | augmented = [(e, e.index) for e in s] |

127 | n/a | augmented.sort() # forced stable because ties broken by index |

128 | n/a | x = [e for e, i in augmented] # a stable sort of s |

129 | n/a | check("stability", x, s) |

130 | n/a | |

131 | n/a | #============================================================================== |

132 | n/a | |

133 | n/a | class TestBugs(unittest.TestCase): |

134 | n/a | |

135 | n/a | def test_bug453523(self): |

136 | n/a | # bug 453523 -- list.sort() crasher. |

137 | n/a | # If this fails, the most likely outcome is a core dump. |

138 | n/a | # Mutations during a list sort should raise a ValueError. |

139 | n/a | |

140 | n/a | class C: |

141 | n/a | def __lt__(self, other): |

142 | n/a | if L and random.random() < 0.75: |

143 | n/a | L.pop() |

144 | n/a | else: |

145 | n/a | L.append(3) |

146 | n/a | return random.random() < 0.5 |

147 | n/a | |

148 | n/a | L = [C() for i in range(50)] |

149 | n/a | self.assertRaises(ValueError, L.sort) |

150 | n/a | |

151 | n/a | def test_undetected_mutation(self): |

152 | n/a | # Python 2.4a1 did not always detect mutation |

153 | n/a | memorywaster = [] |

154 | n/a | for i in range(20): |

155 | n/a | def mutating_cmp(x, y): |

156 | n/a | L.append(3) |

157 | n/a | L.pop() |

158 | n/a | return (x > y) - (x < y) |

159 | n/a | L = [1,2] |

160 | n/a | self.assertRaises(ValueError, L.sort, key=cmp_to_key(mutating_cmp)) |

161 | n/a | def mutating_cmp(x, y): |

162 | n/a | L.append(3) |

163 | n/a | del L[:] |

164 | n/a | return (x > y) - (x < y) |

165 | n/a | self.assertRaises(ValueError, L.sort, key=cmp_to_key(mutating_cmp)) |

166 | n/a | memorywaster = [memorywaster] |

167 | n/a | |

168 | n/a | #============================================================================== |

169 | n/a | |

170 | n/a | class TestDecorateSortUndecorate(unittest.TestCase): |

171 | n/a | |

172 | n/a | def test_decorated(self): |

173 | n/a | data = 'The quick Brown fox Jumped over The lazy Dog'.split() |

174 | n/a | copy = data[:] |

175 | n/a | random.shuffle(data) |

176 | n/a | data.sort(key=str.lower) |

177 | n/a | def my_cmp(x, y): |

178 | n/a | xlower, ylower = x.lower(), y.lower() |

179 | n/a | return (xlower > ylower) - (xlower < ylower) |

180 | n/a | copy.sort(key=cmp_to_key(my_cmp)) |

181 | n/a | |

182 | n/a | def test_baddecorator(self): |

183 | n/a | data = 'The quick Brown fox Jumped over The lazy Dog'.split() |

184 | n/a | self.assertRaises(TypeError, data.sort, key=lambda x,y: 0) |

185 | n/a | |

186 | n/a | def test_stability(self): |

187 | n/a | data = [(random.randrange(100), i) for i in range(200)] |

188 | n/a | copy = data[:] |

189 | n/a | data.sort(key=lambda t: t[0]) # sort on the random first field |

190 | n/a | copy.sort() # sort using both fields |

191 | n/a | self.assertEqual(data, copy) # should get the same result |

192 | n/a | |

193 | n/a | def test_key_with_exception(self): |

194 | n/a | # Verify that the wrapper has been removed |

195 | n/a | data = list(range(-2, 2)) |

196 | n/a | dup = data[:] |

197 | n/a | self.assertRaises(ZeroDivisionError, data.sort, key=lambda x: 1/x) |

198 | n/a | self.assertEqual(data, dup) |

199 | n/a | |

200 | n/a | def test_key_with_mutation(self): |

201 | n/a | data = list(range(10)) |

202 | n/a | def k(x): |

203 | n/a | del data[:] |

204 | n/a | data[:] = range(20) |

205 | n/a | return x |

206 | n/a | self.assertRaises(ValueError, data.sort, key=k) |

207 | n/a | |

208 | n/a | def test_key_with_mutating_del(self): |

209 | n/a | data = list(range(10)) |

210 | n/a | class SortKiller(object): |

211 | n/a | def __init__(self, x): |

212 | n/a | pass |

213 | n/a | def __del__(self): |

214 | n/a | del data[:] |

215 | n/a | data[:] = range(20) |

216 | n/a | def __lt__(self, other): |

217 | n/a | return id(self) < id(other) |

218 | n/a | self.assertRaises(ValueError, data.sort, key=SortKiller) |

219 | n/a | |

220 | n/a | def test_key_with_mutating_del_and_exception(self): |

221 | n/a | data = list(range(10)) |

222 | n/a | ## dup = data[:] |

223 | n/a | class SortKiller(object): |

224 | n/a | def __init__(self, x): |

225 | n/a | if x > 2: |

226 | n/a | raise RuntimeError |

227 | n/a | def __del__(self): |

228 | n/a | del data[:] |

229 | n/a | data[:] = list(range(20)) |

230 | n/a | self.assertRaises(RuntimeError, data.sort, key=SortKiller) |

231 | n/a | ## major honking subtlety: we *can't* do: |

232 | n/a | ## |

233 | n/a | ## self.assertEqual(data, dup) |

234 | n/a | ## |

235 | n/a | ## because there is a reference to a SortKiller in the |

236 | n/a | ## traceback and by the time it dies we're outside the call to |

237 | n/a | ## .sort() and so the list protection gimmicks are out of |

238 | n/a | ## date (this cost some brain cells to figure out...). |

239 | n/a | |

240 | n/a | def test_reverse(self): |

241 | n/a | data = list(range(100)) |

242 | n/a | random.shuffle(data) |

243 | n/a | data.sort(reverse=True) |

244 | n/a | self.assertEqual(data, list(range(99,-1,-1))) |

245 | n/a | |

246 | n/a | def test_reverse_stability(self): |

247 | n/a | data = [(random.randrange(100), i) for i in range(200)] |

248 | n/a | copy1 = data[:] |

249 | n/a | copy2 = data[:] |

250 | n/a | def my_cmp(x, y): |

251 | n/a | x0, y0 = x[0], y[0] |

252 | n/a | return (x0 > y0) - (x0 < y0) |

253 | n/a | def my_cmp_reversed(x, y): |

254 | n/a | x0, y0 = x[0], y[0] |

255 | n/a | return (y0 > x0) - (y0 < x0) |

256 | n/a | data.sort(key=cmp_to_key(my_cmp), reverse=True) |

257 | n/a | copy1.sort(key=cmp_to_key(my_cmp_reversed)) |

258 | n/a | self.assertEqual(data, copy1) |

259 | n/a | copy2.sort(key=lambda x: x[0], reverse=True) |

260 | n/a | self.assertEqual(data, copy2) |

261 | n/a | |

262 | n/a | #============================================================================== |

263 | n/a | |

264 | n/a | if __name__ == "__main__": |

265 | n/a | unittest.main() |