test_sort.py 8.95 KB
Newer Older
1
from test import support
2
import random
3 4
import sys
import unittest
5
from functools import cmp_to_key
6

7
verbose = support.verbose
8 9
nerrors = 0

10

11 12 13 14
def check(tag, expected, raw, compare=None):
    global nerrors

    if verbose:
15
        print("    checking", tag)
16 17 18

    orig = raw[:]   # save input in case of error
    if compare:
19
        raw.sort(key=cmp_to_key(compare))
20 21 22 23
    else:
        raw.sort()

    if len(expected) != len(raw):
24 25 26 27 28
        print("error in", tag)
        print("length mismatch;", len(expected), len(raw))
        print(expected)
        print(orig)
        print(raw)
29 30 31 32 33 34
        nerrors += 1
        return

    for i, good in enumerate(expected):
        maybe = raw[i]
        if good is not maybe:
35 36 37 38 39
            print("error in", tag)
            print("out of order at index", i, good, maybe)
            print(expected)
            print(orig)
            print(raw)
40 41 42
            nerrors += 1
            return

43 44 45 46 47 48 49 50
class TestBase(unittest.TestCase):
    def testStressfully(self):
        # Try a variety of sizes at and around powers of 2, and at powers of 10.
        sizes = [0]
        for power in range(1, 10):
            n = 2 ** power
            sizes.extend(range(n-1, n+2))
        sizes.extend([10, 100, 1000])
51

52 53
        class Complains(object):
            maybe_complain = True
54

55 56
            def __init__(self, i):
                self.i = i
57

58 59 60
            def __lt__(self, other):
                if Complains.maybe_complain and random.random() < 0.001:
                    if verbose:
61
                        print("        complaining at", self, other)
62 63
                    raise RuntimeError
                return self.i < other.i
64

65 66
            def __repr__(self):
                return "Complains(%d)" % self.i
67

68 69 70 71
        class Stable(object):
            def __init__(self, key, i):
                self.key = key
                self.index = i
72

73 74
            def __lt__(self, other):
                return self.key < other.key
75

76 77
            def __repr__(self):
                return "Stable(%d, %d)" % (self.key, self.index)
78

79
        for n in sizes:
80
            x = list(range(n))
81
            if verbose:
82
                print("Testing size", n)
83

84 85
            s = x[:]
            check("identity", x, s)
86

87 88 89
            s = x[:]
            s.reverse()
            check("reversed", x, s)
90

91 92 93
            s = x[:]
            random.shuffle(s)
            check("random permutation", x, s)
94

95 96 97
            y = x[:]
            y.reverse()
            s = x[:]
98
            check("reversed via function", y, s, lambda a, b: (b>a)-(b<a))
99

100
            if verbose:
101 102
                print("    Checking against an insane comparison function.")
                print("        If the implementation isn't careful, this may segfault.")
103
            s = x[:]
104
            s.sort(key=cmp_to_key(lambda a, b:  int(random.random() * 3) - 1))
105 106
            check("an insane function left some permutation", x, s)

107 108 109 110 111 112
            if len(x) >= 2:
                def bad_key(x):
                    raise RuntimeError
                s = x[:]
                self.assertRaises(RuntimeError, s.sort, key=bad_key)

113 114 115 116 117 118 119 120 121 122 123 124 125
            x = [Complains(i) for i in x]
            s = x[:]
            random.shuffle(s)
            Complains.maybe_complain = True
            it_complained = False
            try:
                s.sort()
            except RuntimeError:
                it_complained = True
            if it_complained:
                Complains.maybe_complain = False
                check("exception during sort left some permutation", x, s)

126
            s = [Stable(random.randrange(10), i) for i in range(n)]
127 128 129 130
            augmented = [(e, e.index) for e in s]
            augmented.sort()    # forced stable because ties broken by index
            x = [e for e, i in augmented] # a stable sort of s
            check("stability", x, s)
131

132
#==============================================================================
133

134
class TestBugs(unittest.TestCase):
135

136 137 138 139
    def test_bug453523(self):
        # bug 453523 -- list.sort() crasher.
        # If this fails, the most likely outcome is a core dump.
        # Mutations during a list sort should raise a ValueError.
140

141 142 143 144 145 146 147 148 149 150 151
        class C:
            def __lt__(self, other):
                if L and random.random() < 0.75:
                    L.pop()
                else:
                    L.append(3)
                return random.random() < 0.5

        L = [C() for i in range(50)]
        self.assertRaises(ValueError, L.sort)

152 153 154 155 156 157 158
    def test_undetected_mutation(self):
        # Python 2.4a1 did not always detect mutation
        memorywaster = []
        for i in range(20):
            def mutating_cmp(x, y):
                L.append(3)
                L.pop()
159
                return (x > y) - (x < y)
160
            L = [1,2]
161
            self.assertRaises(ValueError, L.sort, key=cmp_to_key(mutating_cmp))
162 163 164
            def mutating_cmp(x, y):
                L.append(3)
                del L[:]
165
                return (x > y) - (x < y)
166
            self.assertRaises(ValueError, L.sort, key=cmp_to_key(mutating_cmp))
167 168
            memorywaster = [memorywaster]

169 170 171 172 173 174 175 176 177
#==============================================================================

class TestDecorateSortUndecorate(unittest.TestCase):

    def test_decorated(self):
        data = 'The quick Brown fox Jumped over The lazy Dog'.split()
        copy = data[:]
        random.shuffle(data)
        data.sort(key=str.lower)
178 179 180
        def my_cmp(x, y):
            xlower, ylower = x.lower(), y.lower()
            return (xlower > ylower) - (xlower < ylower)
181
        copy.sort(key=cmp_to_key(my_cmp))
182 183 184

    def test_baddecorator(self):
        data = 'The quick Brown fox Jumped over The lazy Dog'.split()
185
        self.assertRaises(TypeError, data.sort, key=lambda x,y: 0)
186 187

    def test_stability(self):
188
        data = [(random.randrange(100), i) for i in range(200)]
189
        copy = data[:]
190
        data.sort(key=lambda t: t[0])   # sort on the random first field
191 192 193
        copy.sort()                     # sort using both fields
        self.assertEqual(data, copy)    # should get the same result

194 195
    def test_key_with_exception(self):
        # Verify that the wrapper has been removed
196
        data = list(range(-2, 2))
197
        dup = data[:]
198
        self.assertRaises(ZeroDivisionError, data.sort, key=lambda x: 1/x)
199 200
        self.assertEqual(data, dup)

201
    def test_key_with_mutation(self):
202
        data = list(range(10))
203 204 205 206 207 208 209
        def k(x):
            del data[:]
            data[:] = range(20)
            return x
        self.assertRaises(ValueError, data.sort, key=k)

    def test_key_with_mutating_del(self):
210
        data = list(range(10))
211 212 213 214 215 216
        class SortKiller(object):
            def __init__(self, x):
                pass
            def __del__(self):
                del data[:]
                data[:] = range(20)
217 218
            def __lt__(self, other):
                return id(self) < id(other)
219 220 221
        self.assertRaises(ValueError, data.sort, key=SortKiller)

    def test_key_with_mutating_del_and_exception(self):
222
        data = list(range(10))
223 224 225 226 227 228 229
        ## dup = data[:]
        class SortKiller(object):
            def __init__(self, x):
                if x > 2:
                    raise RuntimeError
            def __del__(self):
                del data[:]
230
                data[:] = list(range(20))
231 232 233 234 235 236 237 238 239 240
        self.assertRaises(RuntimeError, data.sort, key=SortKiller)
        ## major honking subtlety: we *can't* do:
        ##
        ## self.assertEqual(data, dup)
        ##
        ## because there is a reference to a SortKiller in the
        ## traceback and by the time it dies we're outside the call to
        ## .sort() and so the list protection gimmicks are out of
        ## date (this cost some brain cells to figure out...).

241
    def test_reverse(self):
242
        data = list(range(100))
243 244
        random.shuffle(data)
        data.sort(reverse=True)
245
        self.assertEqual(data, list(range(99,-1,-1)))
246 247

    def test_reverse_stability(self):
248
        data = [(random.randrange(100), i) for i in range(200)]
249 250
        copy1 = data[:]
        copy2 = data[:]
251 252 253 254 255 256
        def my_cmp(x, y):
            x0, y0 = x[0], y[0]
            return (x0 > y0) - (x0 < y0)
        def my_cmp_reversed(x, y):
            x0, y0 = x[0], y[0]
            return (y0 > x0) - (y0 < x0)
257 258
        data.sort(key=cmp_to_key(my_cmp), reverse=True)
        copy1.sort(key=cmp_to_key(my_cmp_reversed))
259 260 261 262 263 264 265 266
        self.assertEqual(data, copy1)
        copy2.sort(key=lambda x: x[0], reverse=True)
        self.assertEqual(data, copy2)

#==============================================================================

def test_main(verbose=None):
    test_classes = (
267
        TestBase,
268 269 270 271
        TestDecorateSortUndecorate,
        TestBugs,
    )

272
    support.run_unittest(*test_classes)
273 274 275 276 277

    # verify reference counting
    if verbose and hasattr(sys, "gettotalrefcount"):
        import gc
        counts = [None] * 5
278
        for i in range(len(counts)):
279
            support.run_unittest(*test_classes)
280 281
            gc.collect()
            counts[i] = sys.gettotalrefcount()
282
        print(counts)
283 284 285

if __name__ == "__main__":
    test_main(verbose=True)