Python code coverage for Lib/test/test_sort.py

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