Python code coverage for Lib/test/test_mutants.py

#	count	content
1	n/a	from test.support import verbose, TESTFN
2	n/a	import random
3	n/a	import os
4	n/a
5	n/a	# From SF bug #422121: Insecurities in dict comparison.
6	n/a
7	n/a	# Safety of code doing comparisons has been an historical Python weak spot.
8	n/a	# The problem is that comparison of structures written in C naturally
9	n/a	# wants to hold on to things like the size of the container, or "the
10	n/a	# biggest" containee so far, across a traversal of the container; but
11	n/a	# code to do containee comparisons can call back into Python and mutate
12	n/a	# the container in arbitrary ways while the C loop is in midstream. If the
13	n/a	# C code isn't extremely paranoid about digging things out of memory on
14	n/a	# each trip, and artificially boosting refcounts for the duration, anything
15	n/a	# from infinite loops to OS crashes can result (yes, I use Windows <wink>).
16	n/a	#
17	n/a	# The other problem is that code designed to provoke a weakness is usually
18	n/a	# white-box code, and so catches only the particular vulnerabilities the
19	n/a	# author knew to protect against. For example, Python's list.sort() code
20	n/a	# went thru many iterations as one "new" vulnerability after another was
21	n/a	# discovered.
22	n/a	#
23	n/a	# So the dict comparison test here uses a black-box approach instead,
24	n/a	# generating dicts of various sizes at random, and performing random
25	n/a	# mutations on them at random times. This proved very effective,
26	n/a	# triggering at least six distinct failure modes the first 20 times I
27	n/a	# ran it. Indeed, at the start, the driver never got beyond 6 iterations
28	n/a	# before the test died.
29	n/a
30	n/a	# The dicts are global to make it easy to mutate tham from within functions.
31	n/a	dict1 = {}
32	n/a	dict2 = {}
33	n/a
34	n/a	# The current set of keys in dict1 and dict2. These are materialized as
35	n/a	# lists to make it easy to pick a dict key at random.
36	n/a	dict1keys = []
37	n/a	dict2keys = []
38	n/a
39	n/a	# Global flag telling maybe_mutate() whether to consider mutating.
40	n/a	mutate = 0
41	n/a
42	n/a	# If global mutate is true, consider mutating a dict. May or may not
43	n/a	# mutate a dict even if mutate is true. If it does decide to mutate a
44	n/a	# dict, it picks one of {dict1, dict2} at random, and deletes a random
45	n/a	# entry from it; or, more rarely, adds a random element.
46	n/a
47	n/a	def maybe_mutate():
48	n/a	global mutate
49	n/a	if not mutate:
50	n/a	return
51	n/a	if random.random() < 0.5:
52	n/a	return
53	n/a
54	n/a	if random.random() < 0.5:
55	n/a	target, keys = dict1, dict1keys
56	n/a	else:
57	n/a	target, keys = dict2, dict2keys
58	n/a
59	n/a	if random.random() < 0.2:
60	n/a	# Insert a new key.
61	n/a	mutate = 0 # disable mutation until key inserted
62	n/a	while 1:
63	n/a	newkey = Horrid(random.randrange(100))
64	n/a	if newkey not in target:
65	n/a	break
66	n/a	target[newkey] = Horrid(random.randrange(100))
67	n/a	keys.append(newkey)
68	n/a	mutate = 1
69	n/a
70	n/a	elif keys:
71	n/a	# Delete a key at random.
72	n/a	mutate = 0 # disable mutation until key deleted
73	n/a	i = random.randrange(len(keys))
74	n/a	key = keys[i]
75	n/a	del target[key]
76	n/a	del keys[i]
77	n/a	mutate = 1
78	n/a
79	n/a	# A horrid class that triggers random mutations of dict1 and dict2 when
80	n/a	# instances are compared.
81	n/a
82	n/a	class Horrid:
83	n/a	def __init__(self, i):
84	n/a	# Comparison outcomes are determined by the value of i.
85	n/a	self.i = i
86	n/a
87	n/a	# An artificial hashcode is selected at random so that we don't
88	n/a	# have any systematic relationship between comparison outcomes
89	n/a	# (based on self.i and other.i) and relative position within the
90	n/a	# hash vector (based on hashcode).
91	n/a	# XXX This is no longer effective.
92	n/a	##self.hashcode = random.randrange(1000000000)
93	n/a
94	n/a	def __hash__(self):
95	n/a	return 42
96	n/a	return self.hashcode
97	n/a
98	n/a	def __eq__(self, other):
99	n/a	maybe_mutate() # The point of the test.
100	n/a	return self.i == other.i
101	n/a
102	n/a	def __ne__(self, other):
103	n/a	raise RuntimeError("I didn't expect some kind of Spanish inquisition!")
104	n/a
105	n/a	__lt__ = __le__ = __gt__ = __ge__ = __ne__
106	n/a
107	n/a	def __repr__(self):
108	n/a	return "Horrid(%d)" % self.i
109	n/a
110	n/a	# Fill dict d with numentries (Horrid(i), Horrid(j)) key-value pairs,
111	n/a	# where i and j are selected at random from the candidates list.
112	n/a	# Return d.keys() after filling.
113	n/a
114	n/a	def fill_dict(d, candidates, numentries):
115	n/a	d.clear()
116	n/a	for i in range(numentries):
117	n/a	d[Horrid(random.choice(candidates))] = \
118	n/a	Horrid(random.choice(candidates))
119	n/a	return list(d.keys())
120	n/a
121	n/a	# Test one pair of randomly generated dicts, each with n entries.
122	n/a	# Note that dict comparison is trivial if they don't have the same number
123	n/a	# of entires (then the "shorter" dict is instantly considered to be the
124	n/a	# smaller one, without even looking at the entries).
125	n/a
126	n/a	def test_one(n):
127	n/a	global mutate, dict1, dict2, dict1keys, dict2keys
128	n/a
129	n/a	# Fill the dicts without mutating them.
130	n/a	mutate = 0
131	n/a	dict1keys = fill_dict(dict1, range(n), n)
132	n/a	dict2keys = fill_dict(dict2, range(n), n)
133	n/a
134	n/a	# Enable mutation, then compare the dicts so long as they have the
135	n/a	# same size.
136	n/a	mutate = 1
137	n/a	if verbose:
138	n/a	print("trying w/ lengths", len(dict1), len(dict2), end=' ')
139	n/a	while dict1 and len(dict1) == len(dict2):
140	n/a	if verbose:
141	n/a	print(".", end=' ')
142	n/a	c = dict1 == dict2
143	n/a	if verbose:
144	n/a	print()
145	n/a
146	n/a	# Run test_one n times. At the start (before the bugs were fixed), 20
147	n/a	# consecutive runs of this test each blew up on or before the sixth time
148	n/a	# test_one was run. So n doesn't have to be large to get an interesting
149	n/a	# test.
150	n/a	# OTOH, calling with large n is also interesting, to ensure that the fixed
151	n/a	# code doesn't hold on to refcounts too long (in which case memory would
152	n/a	# leak).
153	n/a
154	n/a	def test(n):
155	n/a	for i in range(n):
156	n/a	test_one(random.randrange(1, 100))
157	n/a
158	n/a	# See last comment block for clues about good values for n.
159	n/a	test(100)
160	n/a
161	n/a	##########################################################################
162	n/a	# Another segfault bug, distilled by Michael Hudson from a c.l.py post.
163	n/a
164	n/a	class Child:
165	n/a	def __init__(self, parent):
166	n/a	self.__dict__['parent'] = parent
167	n/a	def __getattr__(self, attr):
168	n/a	self.parent.a = 1
169	n/a	self.parent.b = 1
170	n/a	self.parent.c = 1
171	n/a	self.parent.d = 1
172	n/a	self.parent.e = 1
173	n/a	self.parent.f = 1
174	n/a	self.parent.g = 1
175	n/a	self.parent.h = 1
176	n/a	self.parent.i = 1
177	n/a	return getattr(self.parent, attr)
178	n/a
179	n/a	class Parent:
180	n/a	def __init__(self):
181	n/a	self.a = Child(self)
182	n/a
183	n/a	# Hard to say what this will print! May vary from time to time. But
184	n/a	# we're specifically trying to test the tp_print slot here, and this is
185	n/a	# the clearest way to do it. We print the result to a temp file so that
186	n/a	# the expected-output file doesn't need to change.
187	n/a
188	n/a	f = open(TESTFN, "w")
189	n/a	print(Parent().__dict__, file=f)
190	n/a	f.close()
191	n/a	os.unlink(TESTFN)
192	n/a
193	n/a	##########################################################################
194	n/a	# And another core-dumper from Michael Hudson.
195	n/a
196	n/a	dict = {}
197	n/a
198	n/a	# Force dict to malloc its table.
199	n/a	for i in range(1, 10):
200	n/a	dict[i] = i
201	n/a
202	n/a	f = open(TESTFN, "w")
203	n/a
204	n/a	class Machiavelli:
205	n/a	def __repr__(self):
206	n/a	dict.clear()
207	n/a
208	n/a	# Michael sez: "doesn't crash without this. don't know why."
209	n/a	# Tim sez: "luck of the draw; crashes with or without for me."
210	n/a	print(file=f)
211	n/a
212	n/a	return repr("machiavelli")
213	n/a
214	n/a	def __hash__(self):
215	n/a	return 0
216	n/a
217	n/a	dict[Machiavelli()] = Machiavelli()
218	n/a
219	n/a	print(str(dict), file=f)
220	n/a	f.close()
221	n/a	os.unlink(TESTFN)
222	n/a	del f, dict
223	n/a
224	n/a
225	n/a	##########################################################################
226	n/a	# And another core-dumper from Michael Hudson.
227	n/a
228	n/a	dict = {}
229	n/a
230	n/a	# let's force dict to malloc its table
231	n/a	for i in range(1, 10):
232	n/a	dict[i] = i
233	n/a
234	n/a	class Machiavelli2:
235	n/a	def __eq__(self, other):
236	n/a	dict.clear()
237	n/a	return 1
238	n/a
239	n/a	def __hash__(self):
240	n/a	return 0
241	n/a
242	n/a	dict[Machiavelli2()] = Machiavelli2()
243	n/a
244	n/a	try:
245	n/a	dict[Machiavelli2()]
246	n/a	except KeyError:
247	n/a	pass
248	n/a
249	n/a	del dict
250	n/a
251	n/a	##########################################################################
252	n/a	# And another core-dumper from Michael Hudson.
253	n/a
254	n/a	dict = {}
255	n/a
256	n/a	# let's force dict to malloc its table
257	n/a	for i in range(1, 10):
258	n/a	dict[i] = i
259	n/a
260	n/a	class Machiavelli3:
261	n/a	def __init__(self, id):
262	n/a	self.id = id
263	n/a
264	n/a	def __eq__(self, other):
265	n/a	if self.id == other.id:
266	n/a	dict.clear()
267	n/a	return 1
268	n/a	else:
269	n/a	return 0
270	n/a
271	n/a	def __repr__(self):
272	n/a	return "%s(%s)"%(self.__class__.__name__, self.id)
273	n/a
274	n/a	def __hash__(self):
275	n/a	return 0
276	n/a
277	n/a	dict[Machiavelli3(1)] = Machiavelli3(0)
278	n/a	dict[Machiavelli3(2)] = Machiavelli3(0)
279	n/a
280	n/a	f = open(TESTFN, "w")
281	n/a	try:
282	n/a	try:
283	n/a	print(dict[Machiavelli3(2)], file=f)
284	n/a	except KeyError:
285	n/a	pass
286	n/a	finally:
287	n/a	f.close()
288	n/a	os.unlink(TESTFN)
289	n/a
290	n/a	del dict
291	n/a	del dict1, dict2, dict1keys, dict2keys