Python code coverage for Lib/test/test_ordered_dict.py

#	count	content
1	n/a	import builtins
2	n/a	import contextlib
3	n/a	import copy
4	n/a	import gc
5	n/a	import pickle
6	n/a	from random import randrange, shuffle
7	n/a	import struct
8	n/a	import sys
9	n/a	import unittest
10	n/a	import weakref
11	n/a	from collections.abc import MutableMapping
12	n/a	from test import mapping_tests, support
13	n/a
14	n/a
15	n/a	py_coll = support.import_fresh_module('collections', blocked=['_collections'])
16	n/a	c_coll = support.import_fresh_module('collections', fresh=['_collections'])
17	n/a
18	n/a
19	n/a	@contextlib.contextmanager
20	n/a	def replaced_module(name, replacement):
21	n/a	original_module = sys.modules[name]
22	n/a	sys.modules[name] = replacement
23	n/a	try:
24	n/a	yield
25	n/a	finally:
26	n/a	sys.modules[name] = original_module
27	n/a
28	n/a
29	n/a	class OrderedDictTests:
30	n/a
31	n/a	def test_init(self):
32	n/a	OrderedDict = self.OrderedDict
33	n/a	with self.assertRaises(TypeError):
34	n/a	OrderedDict([('a', 1), ('b', 2)], None) # too many args
35	n/a	pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]
36	n/a	self.assertEqual(sorted(OrderedDict(dict(pairs)).items()), pairs) # dict input
37	n/a	self.assertEqual(sorted(OrderedDict(**dict(pairs)).items()), pairs) # kwds input
38	n/a	self.assertEqual(list(OrderedDict(pairs).items()), pairs) # pairs input
39	n/a	self.assertEqual(list(OrderedDict([('a', 1), ('b', 2), ('c', 9), ('d', 4)],
40	n/a	c=3, e=5).items()), pairs) # mixed input
41	n/a
42	n/a	# make sure no positional args conflict with possible kwdargs
43	n/a	self.assertEqual(list(OrderedDict(self=42).items()), [('self', 42)])
44	n/a	self.assertEqual(list(OrderedDict(other=42).items()), [('other', 42)])
45	n/a	self.assertRaises(TypeError, OrderedDict, 42)
46	n/a	self.assertRaises(TypeError, OrderedDict, (), ())
47	n/a	self.assertRaises(TypeError, OrderedDict.__init__)
48	n/a
49	n/a	# Make sure that direct calls to __init__ do not clear previous contents
50	n/a	d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)])
51	n/a	d.__init__([('e', 5), ('f', 6)], g=7, d=4)
52	n/a	self.assertEqual(list(d.items()),
53	n/a	[('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)])
54	n/a
55	n/a	def test_468(self):
56	n/a	OrderedDict = self.OrderedDict
57	n/a	items = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)]
58	n/a	shuffle(items)
59	n/a	argdict = OrderedDict(items)
60	n/a	d = OrderedDict(**argdict)
61	n/a	self.assertEqual(list(d.items()), items)
62	n/a
63	n/a	def test_update(self):
64	n/a	OrderedDict = self.OrderedDict
65	n/a	with self.assertRaises(TypeError):
66	n/a	OrderedDict().update([('a', 1), ('b', 2)], None) # too many args
67	n/a	pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]
68	n/a	od = OrderedDict()
69	n/a	od.update(dict(pairs))
70	n/a	self.assertEqual(sorted(od.items()), pairs) # dict input
71	n/a	od = OrderedDict()
72	n/a	od.update(**dict(pairs))
73	n/a	self.assertEqual(sorted(od.items()), pairs) # kwds input
74	n/a	od = OrderedDict()
75	n/a	od.update(pairs)
76	n/a	self.assertEqual(list(od.items()), pairs) # pairs input
77	n/a	od = OrderedDict()
78	n/a	od.update([('a', 1), ('b', 2), ('c', 9), ('d', 4)], c=3, e=5)
79	n/a	self.assertEqual(list(od.items()), pairs) # mixed input
80	n/a
81	n/a	# Issue 9137: Named argument called 'other' or 'self'
82	n/a	# shouldn't be treated specially.
83	n/a	od = OrderedDict()
84	n/a	od.update(self=23)
85	n/a	self.assertEqual(list(od.items()), [('self', 23)])
86	n/a	od = OrderedDict()
87	n/a	od.update(other={})
88	n/a	self.assertEqual(list(od.items()), [('other', {})])
89	n/a	od = OrderedDict()
90	n/a	od.update(red=5, blue=6, other=7, self=8)
91	n/a	self.assertEqual(sorted(list(od.items())),
92	n/a	[('blue', 6), ('other', 7), ('red', 5), ('self', 8)])
93	n/a
94	n/a	# Make sure that direct calls to update do not clear previous contents
95	n/a	# add that updates items are not moved to the end
96	n/a	d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)])
97	n/a	d.update([('e', 5), ('f', 6)], g=7, d=4)
98	n/a	self.assertEqual(list(d.items()),
99	n/a	[('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)])
100	n/a
101	n/a	self.assertRaises(TypeError, OrderedDict().update, 42)
102	n/a	self.assertRaises(TypeError, OrderedDict().update, (), ())
103	n/a	self.assertRaises(TypeError, OrderedDict.update)
104	n/a
105	n/a	self.assertRaises(TypeError, OrderedDict().update, 42)
106	n/a	self.assertRaises(TypeError, OrderedDict().update, (), ())
107	n/a	self.assertRaises(TypeError, OrderedDict.update)
108	n/a
109	n/a	def test_init_calls(self):
110	n/a	calls = []
111	n/a	class Spam:
112	n/a	def keys(self):
113	n/a	calls.append('keys')
114	n/a	return ()
115	n/a	def items(self):
116	n/a	calls.append('items')
117	n/a	return ()
118	n/a
119	n/a	self.OrderedDict(Spam())
120	n/a	self.assertEqual(calls, ['keys'])
121	n/a
122	n/a	def test_fromkeys(self):
123	n/a	OrderedDict = self.OrderedDict
124	n/a	od = OrderedDict.fromkeys('abc')
125	n/a	self.assertEqual(list(od.items()), [(c, None) for c in 'abc'])
126	n/a	od = OrderedDict.fromkeys('abc', value=None)
127	n/a	self.assertEqual(list(od.items()), [(c, None) for c in 'abc'])
128	n/a	od = OrderedDict.fromkeys('abc', value=0)
129	n/a	self.assertEqual(list(od.items()), [(c, 0) for c in 'abc'])
130	n/a
131	n/a	def test_abc(self):
132	n/a	OrderedDict = self.OrderedDict
133	n/a	self.assertIsInstance(OrderedDict(), MutableMapping)
134	n/a	self.assertTrue(issubclass(OrderedDict, MutableMapping))
135	n/a
136	n/a	def test_clear(self):
137	n/a	OrderedDict = self.OrderedDict
138	n/a	pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
139	n/a	shuffle(pairs)
140	n/a	od = OrderedDict(pairs)
141	n/a	self.assertEqual(len(od), len(pairs))
142	n/a	od.clear()
143	n/a	self.assertEqual(len(od), 0)
144	n/a
145	n/a	def test_delitem(self):
146	n/a	OrderedDict = self.OrderedDict
147	n/a	pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
148	n/a	od = OrderedDict(pairs)
149	n/a	del od['a']
150	n/a	self.assertNotIn('a', od)
151	n/a	with self.assertRaises(KeyError):
152	n/a	del od['a']
153	n/a	self.assertEqual(list(od.items()), pairs[:2] + pairs[3:])
154	n/a
155	n/a	def test_setitem(self):
156	n/a	OrderedDict = self.OrderedDict
157	n/a	od = OrderedDict([('d', 1), ('b', 2), ('c', 3), ('a', 4), ('e', 5)])
158	n/a	od['c'] = 10 # existing element
159	n/a	od['f'] = 20 # new element
160	n/a	self.assertEqual(list(od.items()),
161	n/a	[('d', 1), ('b', 2), ('c', 10), ('a', 4), ('e', 5), ('f', 20)])
162	n/a
163	n/a	def test_iterators(self):
164	n/a	OrderedDict = self.OrderedDict
165	n/a	pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
166	n/a	shuffle(pairs)
167	n/a	od = OrderedDict(pairs)
168	n/a	self.assertEqual(list(od), [t[0] for t in pairs])
169	n/a	self.assertEqual(list(od.keys()), [t[0] for t in pairs])
170	n/a	self.assertEqual(list(od.values()), [t[1] for t in pairs])
171	n/a	self.assertEqual(list(od.items()), pairs)
172	n/a	self.assertEqual(list(reversed(od)),
173	n/a	[t[0] for t in reversed(pairs)])
174	n/a	self.assertEqual(list(reversed(od.keys())),
175	n/a	[t[0] for t in reversed(pairs)])
176	n/a	self.assertEqual(list(reversed(od.values())),
177	n/a	[t[1] for t in reversed(pairs)])
178	n/a	self.assertEqual(list(reversed(od.items())), list(reversed(pairs)))
179	n/a
180	n/a	def test_detect_deletion_during_iteration(self):
181	n/a	OrderedDict = self.OrderedDict
182	n/a	od = OrderedDict.fromkeys('abc')
183	n/a	it = iter(od)
184	n/a	key = next(it)
185	n/a	del od[key]
186	n/a	with self.assertRaises(Exception):
187	n/a	# Note, the exact exception raised is not guaranteed
188	n/a	# The only guarantee that the next() will not succeed
189	n/a	next(it)
190	n/a
191	n/a	def test_sorted_iterators(self):
192	n/a	OrderedDict = self.OrderedDict
193	n/a	with self.assertRaises(TypeError):
194	n/a	OrderedDict([('a', 1), ('b', 2)], None)
195	n/a	pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]
196	n/a	od = OrderedDict(pairs)
197	n/a	self.assertEqual(sorted(od), [t[0] for t in pairs])
198	n/a	self.assertEqual(sorted(od.keys()), [t[0] for t in pairs])
199	n/a	self.assertEqual(sorted(od.values()), [t[1] for t in pairs])
200	n/a	self.assertEqual(sorted(od.items()), pairs)
201	n/a	self.assertEqual(sorted(reversed(od)),
202	n/a	sorted([t[0] for t in reversed(pairs)]))
203	n/a
204	n/a	def test_iterators_empty(self):
205	n/a	OrderedDict = self.OrderedDict
206	n/a	od = OrderedDict()
207	n/a	empty = []
208	n/a	self.assertEqual(list(od), empty)
209	n/a	self.assertEqual(list(od.keys()), empty)
210	n/a	self.assertEqual(list(od.values()), empty)
211	n/a	self.assertEqual(list(od.items()), empty)
212	n/a	self.assertEqual(list(reversed(od)), empty)
213	n/a	self.assertEqual(list(reversed(od.keys())), empty)
214	n/a	self.assertEqual(list(reversed(od.values())), empty)
215	n/a	self.assertEqual(list(reversed(od.items())), empty)
216	n/a
217	n/a	def test_popitem(self):
218	n/a	OrderedDict = self.OrderedDict
219	n/a	pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
220	n/a	shuffle(pairs)
221	n/a	od = OrderedDict(pairs)
222	n/a	while pairs:
223	n/a	self.assertEqual(od.popitem(), pairs.pop())
224	n/a	with self.assertRaises(KeyError):
225	n/a	od.popitem()
226	n/a	self.assertEqual(len(od), 0)
227	n/a
228	n/a	def test_popitem_last(self):
229	n/a	OrderedDict = self.OrderedDict
230	n/a	pairs = [(i, i) for i in range(30)]
231	n/a
232	n/a	obj = OrderedDict(pairs)
233	n/a	for i in range(8):
234	n/a	obj.popitem(True)
235	n/a	obj.popitem(True)
236	n/a	obj.popitem(last=True)
237	n/a	self.assertEqual(len(obj), 20)
238	n/a
239	n/a	def test_pop(self):
240	n/a	OrderedDict = self.OrderedDict
241	n/a	pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
242	n/a	shuffle(pairs)
243	n/a	od = OrderedDict(pairs)
244	n/a	shuffle(pairs)
245	n/a	while pairs:
246	n/a	k, v = pairs.pop()
247	n/a	self.assertEqual(od.pop(k), v)
248	n/a	with self.assertRaises(KeyError):
249	n/a	od.pop('xyz')
250	n/a	self.assertEqual(len(od), 0)
251	n/a	self.assertEqual(od.pop(k, 12345), 12345)
252	n/a
253	n/a	# make sure pop still works when __missing__ is defined
254	n/a	class Missing(OrderedDict):
255	n/a	def __missing__(self, key):
256	n/a	return 0
257	n/a	m = Missing(a=1)
258	n/a	self.assertEqual(m.pop('b', 5), 5)
259	n/a	self.assertEqual(m.pop('a', 6), 1)
260	n/a	self.assertEqual(m.pop('a', 6), 6)
261	n/a	self.assertEqual(m.pop('a', default=6), 6)
262	n/a	with self.assertRaises(KeyError):
263	n/a	m.pop('a')
264	n/a
265	n/a	def test_equality(self):
266	n/a	OrderedDict = self.OrderedDict
267	n/a	pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
268	n/a	shuffle(pairs)
269	n/a	od1 = OrderedDict(pairs)
270	n/a	od2 = OrderedDict(pairs)
271	n/a	self.assertEqual(od1, od2) # same order implies equality
272	n/a	pairs = pairs[2:] + pairs[:2]
273	n/a	od2 = OrderedDict(pairs)
274	n/a	self.assertNotEqual(od1, od2) # different order implies inequality
275	n/a	# comparison to regular dict is not order sensitive
276	n/a	self.assertEqual(od1, dict(od2))
277	n/a	self.assertEqual(dict(od2), od1)
278	n/a	# different length implied inequality
279	n/a	self.assertNotEqual(od1, OrderedDict(pairs[:-1]))
280	n/a
281	n/a	def test_copying(self):
282	n/a	OrderedDict = self.OrderedDict
283	n/a	# Check that ordered dicts are copyable, deepcopyable, picklable,
284	n/a	# and have a repr/eval round-trip
285	n/a	pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
286	n/a	od = OrderedDict(pairs)
287	n/a	def check(dup):
288	n/a	msg = "\ncopy: %s\nod: %s" % (dup, od)
289	n/a	self.assertIsNot(dup, od, msg)
290	n/a	self.assertEqual(dup, od)
291	n/a	self.assertEqual(list(dup.items()), list(od.items()))
292	n/a	self.assertEqual(len(dup), len(od))
293	n/a	self.assertEqual(type(dup), type(od))
294	n/a	check(od.copy())
295	n/a	check(copy.copy(od))
296	n/a	check(copy.deepcopy(od))
297	n/a	# pickle directly pulls the module, so we have to fake it
298	n/a	with replaced_module('collections', self.module):
299	n/a	for proto in range(pickle.HIGHEST_PROTOCOL + 1):
300	n/a	with self.subTest(proto=proto):
301	n/a	check(pickle.loads(pickle.dumps(od, proto)))
302	n/a	check(eval(repr(od)))
303	n/a	update_test = OrderedDict()
304	n/a	update_test.update(od)
305	n/a	check(update_test)
306	n/a	check(OrderedDict(od))
307	n/a
308	n/a	def test_yaml_linkage(self):
309	n/a	OrderedDict = self.OrderedDict
310	n/a	# Verify that __reduce__ is setup in a way that supports PyYAML's dump() feature.
311	n/a	# In yaml, lists are native but tuples are not.
312	n/a	pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
313	n/a	od = OrderedDict(pairs)
314	n/a	# yaml.dump(od) -->
315	n/a	# '!!python/object/apply:__main__.OrderedDict\n- - [a, 1]\n - [b, 2]\n'
316	n/a	self.assertTrue(all(type(pair)==list for pair in od.__reduce__()[1]))
317	n/a
318	n/a	def test_reduce_not_too_fat(self):
319	n/a	OrderedDict = self.OrderedDict
320	n/a	# do not save instance dictionary if not needed
321	n/a	pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
322	n/a	od = OrderedDict(pairs)
323	n/a	self.assertIsInstance(od.__dict__, dict)
324	n/a	self.assertIsNone(od.__reduce__()[2])
325	n/a	od.x = 10
326	n/a	self.assertEqual(od.__dict__['x'], 10)
327	n/a	self.assertEqual(od.__reduce__()[2], {'x': 10})
328	n/a
329	n/a	def test_pickle_recursive(self):
330	n/a	OrderedDict = self.OrderedDict
331	n/a	od = OrderedDict()
332	n/a	od[1] = od
333	n/a
334	n/a	# pickle directly pulls the module, so we have to fake it
335	n/a	with replaced_module('collections', self.module):
336	n/a	for proto in range(-1, pickle.HIGHEST_PROTOCOL + 1):
337	n/a	dup = pickle.loads(pickle.dumps(od, proto))
338	n/a	self.assertIsNot(dup, od)
339	n/a	self.assertEqual(list(dup.keys()), [1])
340	n/a	self.assertIs(dup[1], dup)
341	n/a
342	n/a	def test_repr(self):
343	n/a	OrderedDict = self.OrderedDict
344	n/a	od = OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])
345	n/a	self.assertEqual(repr(od),
346	n/a	"OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])")
347	n/a	self.assertEqual(eval(repr(od)), od)
348	n/a	self.assertEqual(repr(OrderedDict()), "OrderedDict()")
349	n/a
350	n/a	def test_repr_recursive(self):
351	n/a	OrderedDict = self.OrderedDict
352	n/a	# See issue #9826
353	n/a	od = OrderedDict.fromkeys('abc')
354	n/a	od['x'] = od
355	n/a	self.assertEqual(repr(od),
356	n/a	"OrderedDict([('a', None), ('b', None), ('c', None), ('x', ...)])")
357	n/a
358	n/a	def test_setdefault(self):
359	n/a	OrderedDict = self.OrderedDict
360	n/a	pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
361	n/a	shuffle(pairs)
362	n/a	od = OrderedDict(pairs)
363	n/a	pair_order = list(od.items())
364	n/a	self.assertEqual(od.setdefault('a', 10), 3)
365	n/a	# make sure order didn't change
366	n/a	self.assertEqual(list(od.items()), pair_order)
367	n/a	self.assertEqual(od.setdefault('x', 10), 10)
368	n/a	# make sure 'x' is added to the end
369	n/a	self.assertEqual(list(od.items())[-1], ('x', 10))
370	n/a	self.assertEqual(od.setdefault('g', default=9), 9)
371	n/a
372	n/a	# make sure setdefault still works when __missing__ is defined
373	n/a	class Missing(OrderedDict):
374	n/a	def __missing__(self, key):
375	n/a	return 0
376	n/a	self.assertEqual(Missing().setdefault(5, 9), 9)
377	n/a
378	n/a	def test_reinsert(self):
379	n/a	OrderedDict = self.OrderedDict
380	n/a	# Given insert a, insert b, delete a, re-insert a,
381	n/a	# verify that a is now later than b.
382	n/a	od = OrderedDict()
383	n/a	od['a'] = 1
384	n/a	od['b'] = 2
385	n/a	del od['a']
386	n/a	self.assertEqual(list(od.items()), [('b', 2)])
387	n/a	od['a'] = 1
388	n/a	self.assertEqual(list(od.items()), [('b', 2), ('a', 1)])
389	n/a
390	n/a	def test_move_to_end(self):
391	n/a	OrderedDict = self.OrderedDict
392	n/a	od = OrderedDict.fromkeys('abcde')
393	n/a	self.assertEqual(list(od), list('abcde'))
394	n/a	od.move_to_end('c')
395	n/a	self.assertEqual(list(od), list('abdec'))
396	n/a	od.move_to_end('c', 0)
397	n/a	self.assertEqual(list(od), list('cabde'))
398	n/a	od.move_to_end('c', 0)
399	n/a	self.assertEqual(list(od), list('cabde'))
400	n/a	od.move_to_end('e')
401	n/a	self.assertEqual(list(od), list('cabde'))
402	n/a	od.move_to_end('b', last=False)
403	n/a	self.assertEqual(list(od), list('bcade'))
404	n/a	with self.assertRaises(KeyError):
405	n/a	od.move_to_end('x')
406	n/a	with self.assertRaises(KeyError):
407	n/a	od.move_to_end('x', 0)
408	n/a
409	n/a	def test_move_to_end_issue25406(self):
410	n/a	OrderedDict = self.OrderedDict
411	n/a	od = OrderedDict.fromkeys('abc')
412	n/a	od.move_to_end('c', last=False)
413	n/a	self.assertEqual(list(od), list('cab'))
414	n/a	od.move_to_end('a', last=False)
415	n/a	self.assertEqual(list(od), list('acb'))
416	n/a
417	n/a	od = OrderedDict.fromkeys('abc')
418	n/a	od.move_to_end('a')
419	n/a	self.assertEqual(list(od), list('bca'))
420	n/a	od.move_to_end('c')
421	n/a	self.assertEqual(list(od), list('bac'))
422	n/a
423	n/a	def test_sizeof(self):
424	n/a	OrderedDict = self.OrderedDict
425	n/a	# Wimpy test: Just verify the reported size is larger than a regular dict
426	n/a	d = dict(a=1)
427	n/a	od = OrderedDict(**d)
428	n/a	self.assertGreater(sys.getsizeof(od), sys.getsizeof(d))
429	n/a
430	n/a	def test_views(self):
431	n/a	OrderedDict = self.OrderedDict
432	n/a	# See http://bugs.python.org/issue24286
433	n/a	s = 'the quick brown fox jumped over a lazy dog yesterday before dawn'.split()
434	n/a	od = OrderedDict.fromkeys(s)
435	n/a	self.assertEqual(od.keys(), dict(od).keys())
436	n/a	self.assertEqual(od.items(), dict(od).items())
437	n/a
438	n/a	def test_override_update(self):
439	n/a	OrderedDict = self.OrderedDict
440	n/a	# Verify that subclasses can override update() without breaking __init__()
441	n/a	class MyOD(OrderedDict):
442	n/a	def update(self, args, *kwds):
443	n/a	raise Exception()
444	n/a	items = [('a', 1), ('c', 3), ('b', 2)]
445	n/a	self.assertEqual(list(MyOD(items).items()), items)
446	n/a
447	n/a	def test_highly_nested(self):
448	n/a	# Issue 25395: crashes during garbage collection
449	n/a	OrderedDict = self.OrderedDict
450	n/a	obj = None
451	n/a	for _ in range(1000):
452	n/a	obj = OrderedDict([(None, obj)])
453	n/a	del obj
454	n/a	support.gc_collect()
455	n/a
456	n/a	def test_highly_nested_subclass(self):
457	n/a	# Issue 25395: crashes during garbage collection
458	n/a	OrderedDict = self.OrderedDict
459	n/a	deleted = []
460	n/a	class MyOD(OrderedDict):
461	n/a	def __del__(self):
462	n/a	deleted.append(self.i)
463	n/a	obj = None
464	n/a	for i in range(100):
465	n/a	obj = MyOD([(None, obj)])
466	n/a	obj.i = i
467	n/a	del obj
468	n/a	support.gc_collect()
469	n/a	self.assertEqual(deleted, list(reversed(range(100))))
470	n/a
471	n/a	def test_delitem_hash_collision(self):
472	n/a	OrderedDict = self.OrderedDict
473	n/a
474	n/a	class Key:
475	n/a	def __init__(self, hash):
476	n/a	self._hash = hash
477	n/a	self.value = str(id(self))
478	n/a	def __hash__(self):
479	n/a	return self._hash
480	n/a	def __eq__(self, other):
481	n/a	try:
482	n/a	return self.value == other.value
483	n/a	except AttributeError:
484	n/a	return False
485	n/a	def __repr__(self):
486	n/a	return self.value
487	n/a
488	n/a	def blocking_hash(hash):
489	n/a	# See the collision-handling in lookdict (in Objects/dictobject.c).
490	n/a	MINSIZE = 8
491	n/a	i = (hash & MINSIZE-1)
492	n/a	return (i << 2) + i + hash + 1
493	n/a
494	n/a	COLLIDING = 1
495	n/a
496	n/a	key = Key(COLLIDING)
497	n/a	colliding = Key(COLLIDING)
498	n/a	blocking = Key(blocking_hash(COLLIDING))
499	n/a
500	n/a	od = OrderedDict()
501	n/a	od[key] = ...
502	n/a	od[blocking] = ...
503	n/a	od[colliding] = ...
504	n/a	od['after'] = ...
505	n/a
506	n/a	del od[blocking]
507	n/a	del od[colliding]
508	n/a	self.assertEqual(list(od.items()), [(key, ...), ('after', ...)])
509	n/a
510	n/a	def test_issue24347(self):
511	n/a	OrderedDict = self.OrderedDict
512	n/a
513	n/a	class Key:
514	n/a	def __hash__(self):
515	n/a	return randrange(100000)
516	n/a
517	n/a	od = OrderedDict()
518	n/a	for i in range(100):
519	n/a	key = Key()
520	n/a	od[key] = i
521	n/a
522	n/a	# These should not crash.
523	n/a	with self.assertRaises(KeyError):
524	n/a	list(od.values())
525	n/a	with self.assertRaises(KeyError):
526	n/a	list(od.items())
527	n/a	with self.assertRaises(KeyError):
528	n/a	repr(od)
529	n/a	with self.assertRaises(KeyError):
530	n/a	od.copy()
531	n/a
532	n/a	def test_issue24348(self):
533	n/a	OrderedDict = self.OrderedDict
534	n/a
535	n/a	class Key:
536	n/a	def __hash__(self):
537	n/a	return 1
538	n/a
539	n/a	od = OrderedDict()
540	n/a	od[Key()] = 0
541	n/a	# This should not crash.
542	n/a	od.popitem()
543	n/a
544	n/a	def test_issue24667(self):
545	n/a	"""
546	n/a	dict resizes after a certain number of insertion operations,
547	n/a	whether or not there were deletions that freed up slots in the
548	n/a	hash table. During fast node lookup, OrderedDict must correctly
549	n/a	respond to all resizes, even if the current "size" is the same
550	n/a	as the old one. We verify that here by forcing a dict resize
551	n/a	on a sparse odict and then perform an operation that should
552	n/a	trigger an odict resize (e.g. popitem). One key aspect here is
553	n/a	that we will keep the size of the odict the same at each popitem
554	n/a	call. This verifies that we handled the dict resize properly.
555	n/a	"""
556	n/a	OrderedDict = self.OrderedDict
557	n/a
558	n/a	od = OrderedDict()
559	n/a	for c0 in '0123456789ABCDEF':
560	n/a	for c1 in '0123456789ABCDEF':
561	n/a	if len(od) == 4:
562	n/a	# This should not raise a KeyError.
563	n/a	od.popitem(last=False)
564	n/a	key = c0 + c1
565	n/a	od[key] = key
566	n/a
567	n/a	# Direct use of dict methods
568	n/a
569	n/a	def test_dict_setitem(self):
570	n/a	OrderedDict = self.OrderedDict
571	n/a	od = OrderedDict()
572	n/a	dict.__setitem__(od, 'spam', 1)
573	n/a	self.assertNotIn('NULL', repr(od))
574	n/a
575	n/a	def test_dict_delitem(self):
576	n/a	OrderedDict = self.OrderedDict
577	n/a	od = OrderedDict()
578	n/a	od['spam'] = 1
579	n/a	od['ham'] = 2
580	n/a	dict.__delitem__(od, 'spam')
581	n/a	with self.assertRaises(KeyError):
582	n/a	repr(od)
583	n/a
584	n/a	def test_dict_clear(self):
585	n/a	OrderedDict = self.OrderedDict
586	n/a	od = OrderedDict()
587	n/a	od['spam'] = 1
588	n/a	od['ham'] = 2
589	n/a	dict.clear(od)
590	n/a	self.assertNotIn('NULL', repr(od))
591	n/a
592	n/a	def test_dict_pop(self):
593	n/a	OrderedDict = self.OrderedDict
594	n/a	od = OrderedDict()
595	n/a	od['spam'] = 1
596	n/a	od['ham'] = 2
597	n/a	dict.pop(od, 'spam')
598	n/a	with self.assertRaises(KeyError):
599	n/a	repr(od)
600	n/a
601	n/a	def test_dict_popitem(self):
602	n/a	OrderedDict = self.OrderedDict
603	n/a	od = OrderedDict()
604	n/a	od['spam'] = 1
605	n/a	od['ham'] = 2
606	n/a	dict.popitem(od)
607	n/a	with self.assertRaises(KeyError):
608	n/a	repr(od)
609	n/a
610	n/a	def test_dict_setdefault(self):
611	n/a	OrderedDict = self.OrderedDict
612	n/a	od = OrderedDict()
613	n/a	dict.setdefault(od, 'spam', 1)
614	n/a	self.assertNotIn('NULL', repr(od))
615	n/a
616	n/a	def test_dict_update(self):
617	n/a	OrderedDict = self.OrderedDict
618	n/a	od = OrderedDict()
619	n/a	dict.update(od, [('spam', 1)])
620	n/a	self.assertNotIn('NULL', repr(od))
621	n/a
622	n/a	def test_reference_loop(self):
623	n/a	# Issue 25935
624	n/a	OrderedDict = self.OrderedDict
625	n/a	class A:
626	n/a	od = OrderedDict()
627	n/a	A.od[A] = None
628	n/a	r = weakref.ref(A)
629	n/a	del A
630	n/a	gc.collect()
631	n/a	self.assertIsNone(r())
632	n/a
633	n/a	def test_free_after_iterating(self):
634	n/a	support.check_free_after_iterating(self, iter, self.OrderedDict)
635	n/a	support.check_free_after_iterating(self, lambda d: iter(d.keys()), self.OrderedDict)
636	n/a	support.check_free_after_iterating(self, lambda d: iter(d.values()), self.OrderedDict)
637	n/a	support.check_free_after_iterating(self, lambda d: iter(d.items()), self.OrderedDict)
638	n/a
639	n/a
640	n/a	class PurePythonOrderedDictTests(OrderedDictTests, unittest.TestCase):
641	n/a
642	n/a	module = py_coll
643	n/a	OrderedDict = py_coll.OrderedDict
644	n/a
645	n/a
646	n/a	class CPythonBuiltinDictTests(unittest.TestCase):
647	n/a	"""Builtin dict preserves insertion order.
648	n/a
649	n/a	Reuse some of tests in OrderedDict selectively.
650	n/a	"""
651	n/a
652	n/a	module = builtins
653	n/a	OrderedDict = dict
654	n/a
655	n/a	for method in (
656	n/a	"test_init test_update test_abc test_clear test_delitem " +
657	n/a	"test_setitem test_detect_deletion_during_iteration " +
658	n/a	"test_popitem test_reinsert test_override_update " +
659	n/a	"test_highly_nested test_highly_nested_subclass " +
660	n/a	"test_delitem_hash_collision ").split():
661	n/a	setattr(CPythonBuiltinDictTests, method, getattr(OrderedDictTests, method))
662	n/a	del method
663	n/a
664	n/a
665	n/a	@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
666	n/a	class CPythonOrderedDictTests(OrderedDictTests, unittest.TestCase):
667	n/a
668	n/a	module = c_coll
669	n/a	OrderedDict = c_coll.OrderedDict
670	n/a	check_sizeof = support.check_sizeof
671	n/a
672	n/a	@support.cpython_only
673	n/a	def test_sizeof_exact(self):
674	n/a	OrderedDict = self.OrderedDict
675	n/a	calcsize = struct.calcsize
676	n/a	size = support.calcobjsize
677	n/a	check = self.check_sizeof
678	n/a
679	n/a	basicsize = size('nQ2P' + '3PnPn2P') + calcsize('2nP2n')
680	n/a
681	n/a	entrysize = calcsize('n2P')
682	n/a	p = calcsize('P')
683	n/a	nodesize = calcsize('Pn2P')
684	n/a
685	n/a	od = OrderedDict()
686	n/a	check(od, basicsize + 8p + 8 + 5entrysize) # 8byte indicies + 82//3 entry table
687	n/a	od.x = 1
688	n/a	check(od, basicsize + 8p + 8 + 5entrysize)
689	n/a	od.update([(i, i) for i in range(3)])
690	n/a	check(od, basicsize + 8p + 8 + 5entrysize + 3*nodesize)
691	n/a	od.update([(i, i) for i in range(3, 10)])
692	n/a	check(od, basicsize + 16p + 16 + 10entrysize + 10*nodesize)
693	n/a
694	n/a	check(od.keys(), size('P'))
695	n/a	check(od.items(), size('P'))
696	n/a	check(od.values(), size('P'))
697	n/a
698	n/a	itersize = size('iP2n2P')
699	n/a	check(iter(od), itersize)
700	n/a	check(iter(od.keys()), itersize)
701	n/a	check(iter(od.items()), itersize)
702	n/a	check(iter(od.values()), itersize)
703	n/a
704	n/a	def test_key_change_during_iteration(self):
705	n/a	OrderedDict = self.OrderedDict
706	n/a
707	n/a	od = OrderedDict.fromkeys('abcde')
708	n/a	self.assertEqual(list(od), list('abcde'))
709	n/a	with self.assertRaises(RuntimeError):
710	n/a	for i, k in enumerate(od):
711	n/a	od.move_to_end(k)
712	n/a	self.assertLess(i, 5)
713	n/a	with self.assertRaises(RuntimeError):
714	n/a	for k in od:
715	n/a	od['f'] = None
716	n/a	with self.assertRaises(RuntimeError):
717	n/a	for k in od:
718	n/a	del od['c']
719	n/a	self.assertEqual(list(od), list('bdeaf'))
720	n/a
721	n/a
722	n/a	class PurePythonOrderedDictSubclassTests(PurePythonOrderedDictTests):
723	n/a
724	n/a	module = py_coll
725	n/a	class OrderedDict(py_coll.OrderedDict):
726	n/a	pass
727	n/a
728	n/a
729	n/a	class CPythonOrderedDictSubclassTests(CPythonOrderedDictTests):
730	n/a
731	n/a	module = c_coll
732	n/a	class OrderedDict(c_coll.OrderedDict):
733	n/a	pass
734	n/a
735	n/a
736	n/a	class PurePythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
737	n/a
738	n/a	@classmethod
739	n/a	def setUpClass(cls):
740	n/a	cls.type2test = py_coll.OrderedDict
741	n/a
742	n/a	def test_popitem(self):
743	n/a	d = self._empty_mapping()
744	n/a	self.assertRaises(KeyError, d.popitem)
745	n/a
746	n/a
747	n/a	@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
748	n/a	class CPythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
749	n/a
750	n/a	@classmethod
751	n/a	def setUpClass(cls):
752	n/a	cls.type2test = c_coll.OrderedDict
753	n/a
754	n/a	def test_popitem(self):
755	n/a	d = self._empty_mapping()
756	n/a	self.assertRaises(KeyError, d.popitem)
757	n/a
758	n/a
759	n/a	class PurePythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
760	n/a
761	n/a	@classmethod
762	n/a	def setUpClass(cls):
763	n/a	class MyOrderedDict(py_coll.OrderedDict):
764	n/a	pass
765	n/a	cls.type2test = MyOrderedDict
766	n/a
767	n/a	def test_popitem(self):
768	n/a	d = self._empty_mapping()
769	n/a	self.assertRaises(KeyError, d.popitem)
770	n/a
771	n/a
772	n/a	@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
773	n/a	class CPythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
774	n/a
775	n/a	@classmethod
776	n/a	def setUpClass(cls):
777	n/a	class MyOrderedDict(c_coll.OrderedDict):
778	n/a	pass
779	n/a	cls.type2test = MyOrderedDict
780	n/a
781	n/a	def test_popitem(self):
782	n/a	d = self._empty_mapping()
783	n/a	self.assertRaises(KeyError, d.popitem)
784	n/a
785	n/a
786	n/a	if __name__ == "__main__":
787	n/a	unittest.main()