0001 from test.test_support import verbose 0002 import random 0003 from UserList import UserList 0004 0005 nerrors = 0 0006 0007 def check(tag, expected, raw, compare=None): 0008 global nerrors 0009 0010 if verbose: 0011 print " checking", tag 0012 0013 orig = raw[:] # save input in case of error 0014 if compare: 0015 raw.sort(compare) 0016 else: 0017 raw.sort() 0018 0019 if len(expected) != len(raw): 0020 print "error in", tag 0021 print "length mismatch;", len(expected), len(raw) 0022 print expected 0023 print orig 0024 print raw 0025 nerrors += 1 0026 return 0027 0028 for i, good in enumerate(expected): 0029 maybe = raw[i] 0030 if good is not maybe: 0031 print "error in", tag 0032 print "out of order at index", i, good, maybe 0033 print expected 0034 print orig 0035 print raw 0036 nerrors += 1 0037 return 0038 0039 # Try a variety of sizes at and around powers of 2, and at powers of 10. 0040 sizes = [0] 0041 for power in range(1, 10): 0042 n = 2 ** power 0043 sizes.extend(range(n-1, n+2)) 0044 sizes.extend([10, 100, 1000]) 0045 0046 class Complains(object): 0047 maybe_complain = True 0048 0049 def __init__(self, i): 0050 self.i = i 0051 0052 def __lt__(self, other): 0053 if Complains.maybe_complain and random.random() < 0.001: 0054 if verbose: 0055 print " complaining at", self, other 0056 raise RuntimeError 0057 return self.i < other.i 0058 0059 def __repr__(self): 0060 return "Complains(%d)" % self.i 0061 0062 class Stable(object): 0063 def __init__(self, key, i): 0064 self.key = key 0065 self.index = i 0066 0067 def __cmp__(self, other): 0068 return cmp(self.key, other.key) 0069 0070 def __repr__(self): 0071 return "Stable(%d, %d)" % (self.key, self.index) 0072 0073 for n in sizes: 0074 x = range(n) 0075 if verbose: 0076 print "Testing size", n 0077 0078 s = x[:] 0079 check("identity", x, s) 0080 0081 s = x[:] 0082 s.reverse() 0083 check("reversed", x, s) 0084 0085 s = x[:] 0086 random.shuffle(s) 0087 check("random permutation", x, s) 0088 0089 y = x[:] 0090 y.reverse() 0091 s = x[:] 0092 check("reversed via function", y, s, lambda a, b: cmp(b, a)) 0093 0094 if verbose: 0095 print " Checking against an insane comparison function." 0096 print " If the implementation isn't careful, this may segfault." 0097 s = x[:] 0098 s.sort(lambda a, b: int(random.random() * 3) - 1) 0099 check("an insane function left some permutation", x, s) 0100 0101 x = [Complains(i) for i in x] 0102 s = x[:] 0103 random.shuffle(s) 0104 Complains.maybe_complain = True 0105 it_complained = False 0106 try: 0107 s.sort() 0108 except RuntimeError: 0109 it_complained = True 0110 if it_complained: 0111 Complains.maybe_complain = False 0112 check("exception during sort left some permutation", x, s) 0113 0114 s = [Stable(random.randrange(10), i) for i in xrange(n)] 0115 augmented = [(e, e.index) for e in s] 0116 augmented.sort() # forced stable because ties broken by index 0117 x = [e for e, i in augmented] # a stable sort of s 0118 check("stability", x, s) 0119 0120 0121 import unittest 0122 from test import test_support 0123 import sys 0124 0125 #============================================================================== 0126 0127 class TestBugs(unittest.TestCase): 0128 0129 def test_bug453523(self): 0130 # bug 453523 -- list.sort() crasher. 0131 # If this fails, the most likely outcome is a core dump. 0132 # Mutations during a list sort should raise a ValueError. 0133 0134 class C: 0135 def __lt__(self, other): 0136 if L and random.random() < 0.75: 0137 L.pop() 0138 else: 0139 L.append(3) 0140 return random.random() < 0.5 0141 0142 L = [C() for i in range(50)] 0143 self.assertRaises(ValueError, L.sort) 0144 0145 def test_cmpNone(self): 0146 # Testing None as a comparison function. 0147 0148 L = range(50) 0149 random.shuffle(L) 0150 L.sort(None) 0151 self.assertEqual(L, range(50)) 0152 0153 def test_undetected_mutation(self): 0154 # Python 2.4a1 did not always detect mutation 0155 memorywaster = [] 0156 for i in range(20): 0157 def mutating_cmp(x, y): 0158 L.append(3) 0159 L.pop() 0160 return cmp(x, y) 0161 L = [1,2] 0162 self.assertRaises(ValueError, L.sort, mutating_cmp) 0163 def mutating_cmp(x, y): 0164 L.append(3) 0165 del L[:] 0166 return cmp(x, y) 0167 self.assertRaises(ValueError, L.sort, mutating_cmp) 0168 memorywaster = [memorywaster] 0169 0170 #============================================================================== 0171 0172 class TestDecorateSortUndecorate(unittest.TestCase): 0173 0174 def test_decorated(self): 0175 data = 'The quick Brown fox Jumped over The lazy Dog'.split() 0176 copy = data[:] 0177 random.shuffle(data) 0178 data.sort(key=str.lower) 0179 copy.sort(cmp=lambda x,y: cmp(x.lower(), y.lower())) 0180 0181 def test_baddecorator(self): 0182 data = 'The quick Brown fox Jumped over The lazy Dog'.split() 0183 self.assertRaises(TypeError, data.sort, None, lambda x,y: 0) 0184 0185 def test_stability(self): 0186 data = [(random.randrange(100), i) for i in xrange(200)] 0187 copy = data[:] 0188 data.sort(key=lambda (x,y): x) # sort on the random first field 0189 copy.sort() # sort using both fields 0190 self.assertEqual(data, copy) # should get the same result 0191 0192 def test_cmp_and_key_combination(self): 0193 # Verify that the wrapper has been removed 0194 def compare(x, y): 0195 self.assertEqual(type(x), str) 0196 self.assertEqual(type(x), str) 0197 return cmp(x, y) 0198 data = 'The quick Brown fox Jumped over The lazy Dog'.split() 0199 data.sort(cmp=compare, key=str.lower) 0200 0201 def test_badcmp_with_key(self): 0202 # Verify that the wrapper has been removed 0203 data = 'The quick Brown fox Jumped over The lazy Dog'.split() 0204 self.assertRaises(TypeError, data.sort, "bad", str.lower) 0205 0206 def test_key_with_exception(self): 0207 # Verify that the wrapper has been removed 0208 data = range(-2,2) 0209 dup = data[:] 0210 self.assertRaises(ZeroDivisionError, data.sort, None, lambda x: 1/x) 0211 self.assertEqual(data, dup) 0212 0213 def test_key_with_mutation(self): 0214 data = range(10) 0215 def k(x): 0216 del data[:] 0217 data[:] = range(20) 0218 return x 0219 self.assertRaises(ValueError, data.sort, key=k) 0220 0221 def test_key_with_mutating_del(self): 0222 data = range(10) 0223 class SortKiller(object): 0224 def __init__(self, x): 0225 pass 0226 def __del__(self): 0227 del data[:] 0228 data[:] = range(20) 0229 self.assertRaises(ValueError, data.sort, key=SortKiller) 0230 0231 def test_key_with_mutating_del_and_exception(self): 0232 data = range(10) 0233 ## dup = data[:] 0234 class SortKiller(object): 0235 def __init__(self, x): 0236 if x > 2: 0237 raise RuntimeError 0238 def __del__(self): 0239 del data[:] 0240 data[:] = range(20) 0241 self.assertRaises(RuntimeError, data.sort, key=SortKiller) 0242 ## major honking subtlety: we *can't* do: 0243 ## 0244 ## self.assertEqual(data, dup) 0245 ## 0246 ## because there is a reference to a SortKiller in the 0247 ## traceback and by the time it dies we're outside the call to 0248 ## .sort() and so the list protection gimmicks are out of 0249 ## date (this cost some brain cells to figure out...). 0250 0251 def test_reverse(self): 0252 data = range(100) 0253 random.shuffle(data) 0254 data.sort(reverse=True) 0255 self.assertEqual(data, range(99,-1,-1)) 0256 self.assertRaises(TypeError, data.sort, "wrong type") 0257 0258 def test_reverse_stability(self): 0259 data = [(random.randrange(100), i) for i in xrange(200)] 0260 copy1 = data[:] 0261 copy2 = data[:] 0262 data.sort(cmp=lambda x,y: cmp(x[0],y[0]), reverse=True) 0263 copy1.sort(cmp=lambda x,y: cmp(y[0],x[0])) 0264 self.assertEqual(data, copy1) 0265 copy2.sort(key=lambda x: x[0], reverse=True) 0266 self.assertEqual(data, copy2) 0267 0268 #============================================================================== 0269 0270 def test_main(verbose=None): 0271 test_classes = ( 0272 TestDecorateSortUndecorate, 0273 TestBugs, 0274 ) 0275 0276 test_support.run_unittest(*test_classes) 0277 0278 # verify reference counting 0279 if verbose and hasattr(sys, "gettotalrefcount"): 0280 import gc 0281 counts = [None] * 5 0282 for i in xrange(len(counts)): 0283 test_support.run_unittest(*test_classes) 0284 gc.collect() 0285 counts[i] = sys.gettotalrefcount() 0286 print counts 0287 0288 if __name__ == "__main__": 0289 test_main(verbose=True) 0290
Generated by PyXR 0.9.4