Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | from test.test_support import verbose |
2 | import random | |
3 | from UserList import UserList | |
4 | ||
5 | nerrors = 0 | |
6 | ||
7 | def check(tag, expected, raw, compare=None): | |
8 | global nerrors | |
9 | ||
10 | if verbose: | |
11 | print " checking", tag | |
12 | ||
13 | orig = raw[:] # save input in case of error | |
14 | if compare: | |
15 | raw.sort(compare) | |
16 | else: | |
17 | raw.sort() | |
18 | ||
19 | if len(expected) != len(raw): | |
20 | print "error in", tag | |
21 | print "length mismatch;", len(expected), len(raw) | |
22 | print expected | |
23 | print orig | |
24 | print raw | |
25 | nerrors += 1 | |
26 | return | |
27 | ||
28 | for i, good in enumerate(expected): | |
29 | maybe = raw[i] | |
30 | if good is not maybe: | |
31 | print "error in", tag | |
32 | print "out of order at index", i, good, maybe | |
33 | print expected | |
34 | print orig | |
35 | print raw | |
36 | nerrors += 1 | |
37 | return | |
38 | ||
39 | # Try a variety of sizes at and around powers of 2, and at powers of 10. | |
40 | sizes = [0] | |
41 | for power in range(1, 10): | |
42 | n = 2 ** power | |
43 | sizes.extend(range(n-1, n+2)) | |
44 | sizes.extend([10, 100, 1000]) | |
45 | ||
46 | class Complains(object): | |
47 | maybe_complain = True | |
48 | ||
49 | def __init__(self, i): | |
50 | self.i = i | |
51 | ||
52 | def __lt__(self, other): | |
53 | if Complains.maybe_complain and random.random() < 0.001: | |
54 | if verbose: | |
55 | print " complaining at", self, other | |
56 | raise RuntimeError | |
57 | return self.i < other.i | |
58 | ||
59 | def __repr__(self): | |
60 | return "Complains(%d)" % self.i | |
61 | ||
62 | class Stable(object): | |
63 | def __init__(self, key, i): | |
64 | self.key = key | |
65 | self.index = i | |
66 | ||
67 | def __cmp__(self, other): | |
68 | return cmp(self.key, other.key) | |
69 | ||
70 | def __repr__(self): | |
71 | return "Stable(%d, %d)" % (self.key, self.index) | |
72 | ||
73 | for n in sizes: | |
74 | x = range(n) | |
75 | if verbose: | |
76 | print "Testing size", n | |
77 | ||
78 | s = x[:] | |
79 | check("identity", x, s) | |
80 | ||
81 | s = x[:] | |
82 | s.reverse() | |
83 | check("reversed", x, s) | |
84 | ||
85 | s = x[:] | |
86 | random.shuffle(s) | |
87 | check("random permutation", x, s) | |
88 | ||
89 | y = x[:] | |
90 | y.reverse() | |
91 | s = x[:] | |
92 | check("reversed via function", y, s, lambda a, b: cmp(b, a)) | |
93 | ||
94 | if verbose: | |
95 | print " Checking against an insane comparison function." | |
96 | print " If the implementation isn't careful, this may segfault." | |
97 | s = x[:] | |
98 | s.sort(lambda a, b: int(random.random() * 3) - 1) | |
99 | check("an insane function left some permutation", x, s) | |
100 | ||
101 | x = [Complains(i) for i in x] | |
102 | s = x[:] | |
103 | random.shuffle(s) | |
104 | Complains.maybe_complain = True | |
105 | it_complained = False | |
106 | try: | |
107 | s.sort() | |
108 | except RuntimeError: | |
109 | it_complained = True | |
110 | if it_complained: | |
111 | Complains.maybe_complain = False | |
112 | check("exception during sort left some permutation", x, s) | |
113 | ||
114 | s = [Stable(random.randrange(10), i) for i in xrange(n)] | |
115 | augmented = [(e, e.index) for e in s] | |
116 | augmented.sort() # forced stable because ties broken by index | |
117 | x = [e for e, i in augmented] # a stable sort of s | |
118 | check("stability", x, s) | |
119 | ||
120 | ||
121 | import unittest | |
122 | from test import test_support | |
123 | import sys | |
124 | ||
125 | #============================================================================== | |
126 | ||
127 | class TestBugs(unittest.TestCase): | |
128 | ||
129 | def test_bug453523(self): | |
130 | # bug 453523 -- list.sort() crasher. | |
131 | # If this fails, the most likely outcome is a core dump. | |
132 | # Mutations during a list sort should raise a ValueError. | |
133 | ||
134 | class C: | |
135 | def __lt__(self, other): | |
136 | if L and random.random() < 0.75: | |
137 | L.pop() | |
138 | else: | |
139 | L.append(3) | |
140 | return random.random() < 0.5 | |
141 | ||
142 | L = [C() for i in range(50)] | |
143 | self.assertRaises(ValueError, L.sort) | |
144 | ||
145 | def test_cmpNone(self): | |
146 | # Testing None as a comparison function. | |
147 | ||
148 | L = range(50) | |
149 | random.shuffle(L) | |
150 | L.sort(None) | |
151 | self.assertEqual(L, range(50)) | |
152 | ||
153 | def test_undetected_mutation(self): | |
154 | # Python 2.4a1 did not always detect mutation | |
155 | memorywaster = [] | |
156 | for i in range(20): | |
157 | def mutating_cmp(x, y): | |
158 | L.append(3) | |
159 | L.pop() | |
160 | return cmp(x, y) | |
161 | L = [1,2] | |
162 | self.assertRaises(ValueError, L.sort, mutating_cmp) | |
163 | def mutating_cmp(x, y): | |
164 | L.append(3) | |
165 | del L[:] | |
166 | return cmp(x, y) | |
167 | self.assertRaises(ValueError, L.sort, mutating_cmp) | |
168 | memorywaster = [memorywaster] | |
169 | ||
170 | #============================================================================== | |
171 | ||
172 | class TestDecorateSortUndecorate(unittest.TestCase): | |
173 | ||
174 | def test_decorated(self): | |
175 | data = 'The quick Brown fox Jumped over The lazy Dog'.split() | |
176 | copy = data[:] | |
177 | random.shuffle(data) | |
178 | data.sort(key=str.lower) | |
179 | copy.sort(cmp=lambda x,y: cmp(x.lower(), y.lower())) | |
180 | ||
181 | def test_baddecorator(self): | |
182 | data = 'The quick Brown fox Jumped over The lazy Dog'.split() | |
183 | self.assertRaises(TypeError, data.sort, None, lambda x,y: 0) | |
184 | ||
185 | def test_stability(self): | |
186 | data = [(random.randrange(100), i) for i in xrange(200)] | |
187 | copy = data[:] | |
188 | data.sort(key=lambda (x,y): x) # sort on the random first field | |
189 | copy.sort() # sort using both fields | |
190 | self.assertEqual(data, copy) # should get the same result | |
191 | ||
192 | def test_cmp_and_key_combination(self): | |
193 | # Verify that the wrapper has been removed | |
194 | def compare(x, y): | |
195 | self.assertEqual(type(x), str) | |
196 | self.assertEqual(type(x), str) | |
197 | return cmp(x, y) | |
198 | data = 'The quick Brown fox Jumped over The lazy Dog'.split() | |
199 | data.sort(cmp=compare, key=str.lower) | |
200 | ||
201 | def test_badcmp_with_key(self): | |
202 | # Verify that the wrapper has been removed | |
203 | data = 'The quick Brown fox Jumped over The lazy Dog'.split() | |
204 | self.assertRaises(TypeError, data.sort, "bad", str.lower) | |
205 | ||
206 | def test_key_with_exception(self): | |
207 | # Verify that the wrapper has been removed | |
208 | data = range(-2,2) | |
209 | dup = data[:] | |
210 | self.assertRaises(ZeroDivisionError, data.sort, None, lambda x: 1/x) | |
211 | self.assertEqual(data, dup) | |
212 | ||
213 | def test_key_with_mutation(self): | |
214 | data = range(10) | |
215 | def k(x): | |
216 | del data[:] | |
217 | data[:] = range(20) | |
218 | return x | |
219 | self.assertRaises(ValueError, data.sort, key=k) | |
220 | ||
221 | def test_key_with_mutating_del(self): | |
222 | data = range(10) | |
223 | class SortKiller(object): | |
224 | def __init__(self, x): | |
225 | pass | |
226 | def __del__(self): | |
227 | del data[:] | |
228 | data[:] = range(20) | |
229 | self.assertRaises(ValueError, data.sort, key=SortKiller) | |
230 | ||
231 | def test_key_with_mutating_del_and_exception(self): | |
232 | data = range(10) | |
233 | ## dup = data[:] | |
234 | class SortKiller(object): | |
235 | def __init__(self, x): | |
236 | if x > 2: | |
237 | raise RuntimeError | |
238 | def __del__(self): | |
239 | del data[:] | |
240 | data[:] = range(20) | |
241 | self.assertRaises(RuntimeError, data.sort, key=SortKiller) | |
242 | ## major honking subtlety: we *can't* do: | |
243 | ## | |
244 | ## self.assertEqual(data, dup) | |
245 | ## | |
246 | ## because there is a reference to a SortKiller in the | |
247 | ## traceback and by the time it dies we're outside the call to | |
248 | ## .sort() and so the list protection gimmicks are out of | |
249 | ## date (this cost some brain cells to figure out...). | |
250 | ||
251 | def test_reverse(self): | |
252 | data = range(100) | |
253 | random.shuffle(data) | |
254 | data.sort(reverse=True) | |
255 | self.assertEqual(data, range(99,-1,-1)) | |
256 | self.assertRaises(TypeError, data.sort, "wrong type") | |
257 | ||
258 | def test_reverse_stability(self): | |
259 | data = [(random.randrange(100), i) for i in xrange(200)] | |
260 | copy1 = data[:] | |
261 | copy2 = data[:] | |
262 | data.sort(cmp=lambda x,y: cmp(x[0],y[0]), reverse=True) | |
263 | copy1.sort(cmp=lambda x,y: cmp(y[0],x[0])) | |
264 | self.assertEqual(data, copy1) | |
265 | copy2.sort(key=lambda x: x[0], reverse=True) | |
266 | self.assertEqual(data, copy2) | |
267 | ||
268 | #============================================================================== | |
269 | ||
270 | def test_main(verbose=None): | |
271 | test_classes = ( | |
272 | TestDecorateSortUndecorate, | |
273 | TestBugs, | |
274 | ) | |
275 | ||
276 | test_support.run_unittest(*test_classes) | |
277 | ||
278 | # verify reference counting | |
279 | if verbose and hasattr(sys, "gettotalrefcount"): | |
280 | import gc | |
281 | counts = [None] * 5 | |
282 | for i in xrange(len(counts)): | |
283 | test_support.run_unittest(*test_classes) | |
284 | gc.collect() | |
285 | counts[i] = sys.gettotalrefcount() | |
286 | print counts | |
287 | ||
288 | if __name__ == "__main__": | |
289 | test_main(verbose=True) |