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