1 from test import test_support 2 import random 3 import sys 4 import unittest 5 6 verbose = test_support.verbose 7 nerrors = 0 8 9 def check(tag, expected, raw, compare=None): 10 global nerrors 11 12 if verbose: 13 print " checking", tag 14 15 orig = raw[:] # save input in case of error 16 if compare: 17 raw.sort(compare) 18 else: 19 raw.sort() 20 21 if len(expected) != len(raw): 22 print "error in", tag 23 print "length mismatch;", len(expected), len(raw) 24 print expected 25 print orig 26 print raw 27 nerrors += 1 28 return 29 30 for i, good in enumerate(expected): 31 maybe = raw[i] 32 if good is not maybe: 33 print "error in", tag 34 print "out of order at index", i, good, maybe 35 print expected 36 print orig 37 print raw 38 nerrors += 1 39 return 40 41 class TestBase(unittest.TestCase): 42 def testStressfully(self): 43 # Try a variety of sizes at and around powers of 2, and at powers of 10. 44 sizes = [0] 45 for power in range(1, 10): 46 n = 2 ** power 47 sizes.extend(range(n-1, n+2)) 48 sizes.extend([10, 100, 1000]) 49 50 class Complains(object): 51 maybe_complain = True 52 53 def __init__(self, i): 54 self.i = i 55 56 def __lt__(self, other): 57 if Complains.maybe_complain and random.random() < 0.001: 58 if verbose: 59 print " complaining at", self, other 60 raise RuntimeError 61 return self.i < other.i 62 63 def __repr__(self): 64 return "Complains(%d)" % self.i 65 66 class Stable(object): 67 def __init__(self, key, i): 68 self.key = key 69 self.index = i 70 71 def __cmp__(self, other): 72 return cmp(self.key, other.key) 73 __hash__ = None # Silence Py3k warning 74 75 def __repr__(self): 76 return "Stable(%d, %d)" % (self.key, self.index) 77 78 for n in sizes: 79 x = range(n) 80 if verbose: 81 print "Testing size", n 82 83 s = x[:] 84 check("identity", x, s) 85 86 s = x[:] 87 s.reverse() 88 check("reversed", x, s) 89 90 s = x[:] 91 random.shuffle(s) 92 check("random permutation", x, s) 93 94 y = x[:] 95 y.reverse() 96 s = x[:] 97 check("reversed via function", y, s, lambda a, b: cmp(b, a)) 98 99 if verbose: 100 print " Checking against an insane comparison function." 101 print " If the implementation isn't careful, this may segfault." 102 s = x[:] 103 s.sort(lambda a, b: int(random.random() * 3) - 1) 104 check("an insane function left some permutation", x, s) 105 106 x = [Complains(i) for i in x] 107 s = x[:] 108 random.shuffle(s) 109 Complains.maybe_complain = True 110 it_complained = False 111 try: 112 s.sort() 113 except RuntimeError: 114 it_complained = True 115 if it_complained: 116 Complains.maybe_complain = False 117 check("exception during sort left some permutation", x, s) 118 119 s = [Stable(random.randrange(10), i) for i in xrange(n)] 120 augmented = [(e, e.index) for e in s] 121 augmented.sort() # forced stable because ties broken by index 122 x = [e for e, i in augmented] # a stable sort of s 123 check("stability", x, s) 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: x[0]) # 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 TestBase, 273 TestDecorateSortUndecorate, 274 TestBugs, 275 ) 276 277 with test_support.check_py3k_warnings( 278 ("the cmp argument is not supported", DeprecationWarning)): 279 test_support.run_unittest(*test_classes) 280 281 # verify reference counting 282 if verbose and hasattr(sys, "gettotalrefcount"): 283 import gc 284 counts = [None] * 5 285 for i in xrange(len(counts)): 286 test_support.run_unittest(*test_classes) 287 gc.collect() 288 counts[i] = sys.gettotalrefcount() 289 print counts 290 291 if __name__ == "__main__": 292 test_main(verbose=True) 293
