Lib/test/test_sort.py

   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,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         TestBase,
 273         TestDecorateSortUndecorate,
 274         TestBugs,
 275     )
 276
 277     test_support.run_unittest(*test_classes)
 278
 279     # verify reference counting
 280     if verbose and hasattr(sys, "gettotalrefcount"):
 281         import gc
 282         counts = [None] * 5
 283         for i in xrange(len(counts)):
 284             test_support.run_unittest(*test_classes)
 285             gc.collect()
 286             counts[i] = sys.gettotalrefcount()
 287         print counts
 288
 289 if __name__ == "__main__":
 290     test_main(verbose=True)