ยปCore Development>Code coverage>Lib/test/test_sort.py

Python code coverage for Lib/test/test_sort.py

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