Python code coverage for Lib/test/test_dict.py

#	count	content
1	n/a	import collections
2	n/a	import collections.abc
3	n/a	import gc
4	n/a	import pickle
5	n/a	import random
6	n/a	import string
7	n/a	import sys
8	n/a	import unittest
9	n/a	import weakref
10	n/a	from test import support
11	n/a
12	n/a
13	n/a	class DictTest(unittest.TestCase):
14	n/a
15	n/a	def test_invalid_keyword_arguments(self):
16	n/a	class Custom(dict):
17	n/a	pass
18	n/a	for invalid in {1 : 2}, Custom({1 : 2}):
19	n/a	with self.assertRaises(TypeError):
20	n/a	dict(**invalid)
21	n/a	with self.assertRaises(TypeError):
22	n/a	{}.update(**invalid)
23	n/a
24	n/a	def test_constructor(self):
25	n/a	# calling built-in types without argument must return empty
26	n/a	self.assertEqual(dict(), {})
27	n/a	self.assertIsNot(dict(), {})
28	n/a
29	n/a	def test_literal_constructor(self):
30	n/a	# check literal constructor for different sized dicts
31	n/a	# (to exercise the BUILD_MAP oparg).
32	n/a	for n in (0, 1, 6, 256, 400):
33	n/a	items = [(''.join(random.sample(string.ascii_letters, 8)), i)
34	n/a	for i in range(n)]
35	n/a	random.shuffle(items)
36	n/a	formatted_items = ('{!r}: {:d}'.format(k, v) for k, v in items)
37	n/a	dictliteral = '{' + ', '.join(formatted_items) + '}'
38	n/a	self.assertEqual(eval(dictliteral), dict(items))
39	n/a
40	n/a	def test_bool(self):
41	n/a	self.assertIs(not {}, True)
42	n/a	self.assertTrue({1: 2})
43	n/a	self.assertIs(bool({}), False)
44	n/a	self.assertIs(bool({1: 2}), True)
45	n/a
46	n/a	def test_keys(self):
47	n/a	d = {}
48	n/a	self.assertEqual(set(d.keys()), set())
49	n/a	d = {'a': 1, 'b': 2}
50	n/a	k = d.keys()
51	n/a	self.assertEqual(set(k), {'a', 'b'})
52	n/a	self.assertIn('a', k)
53	n/a	self.assertIn('b', k)
54	n/a	self.assertIn('a', d)
55	n/a	self.assertIn('b', d)
56	n/a	self.assertRaises(TypeError, d.keys, None)
57	n/a	self.assertEqual(repr(dict(a=1).keys()), "dict_keys(['a'])")
58	n/a
59	n/a	def test_values(self):
60	n/a	d = {}
61	n/a	self.assertEqual(set(d.values()), set())
62	n/a	d = {1:2}
63	n/a	self.assertEqual(set(d.values()), {2})
64	n/a	self.assertRaises(TypeError, d.values, None)
65	n/a	self.assertEqual(repr(dict(a=1).values()), "dict_values([1])")
66	n/a
67	n/a	def test_items(self):
68	n/a	d = {}
69	n/a	self.assertEqual(set(d.items()), set())
70	n/a
71	n/a	d = {1:2}
72	n/a	self.assertEqual(set(d.items()), {(1, 2)})
73	n/a	self.assertRaises(TypeError, d.items, None)
74	n/a	self.assertEqual(repr(dict(a=1).items()), "dict_items([('a', 1)])")
75	n/a
76	n/a	def test_contains(self):
77	n/a	d = {}
78	n/a	self.assertNotIn('a', d)
79	n/a	self.assertFalse('a' in d)
80	n/a	self.assertTrue('a' not in d)
81	n/a	d = {'a': 1, 'b': 2}
82	n/a	self.assertIn('a', d)
83	n/a	self.assertIn('b', d)
84	n/a	self.assertNotIn('c', d)
85	n/a
86	n/a	self.assertRaises(TypeError, d.__contains__)
87	n/a
88	n/a	def test_len(self):
89	n/a	d = {}
90	n/a	self.assertEqual(len(d), 0)
91	n/a	d = {'a': 1, 'b': 2}
92	n/a	self.assertEqual(len(d), 2)
93	n/a
94	n/a	def test_getitem(self):
95	n/a	d = {'a': 1, 'b': 2}
96	n/a	self.assertEqual(d['a'], 1)
97	n/a	self.assertEqual(d['b'], 2)
98	n/a	d['c'] = 3
99	n/a	d['a'] = 4
100	n/a	self.assertEqual(d['c'], 3)
101	n/a	self.assertEqual(d['a'], 4)
102	n/a	del d['b']
103	n/a	self.assertEqual(d, {'a': 4, 'c': 3})
104	n/a
105	n/a	self.assertRaises(TypeError, d.__getitem__)
106	n/a
107	n/a	class BadEq(object):
108	n/a	def __eq__(self, other):
109	n/a	raise Exc()
110	n/a	def __hash__(self):
111	n/a	return 24
112	n/a
113	n/a	d = {}
114	n/a	d[BadEq()] = 42
115	n/a	self.assertRaises(KeyError, d.__getitem__, 23)
116	n/a
117	n/a	class Exc(Exception): pass
118	n/a
119	n/a	class BadHash(object):
120	n/a	fail = False
121	n/a	def __hash__(self):
122	n/a	if self.fail:
123	n/a	raise Exc()
124	n/a	else:
125	n/a	return 42
126	n/a
127	n/a	x = BadHash()
128	n/a	d[x] = 42
129	n/a	x.fail = True
130	n/a	self.assertRaises(Exc, d.__getitem__, x)
131	n/a
132	n/a	def test_clear(self):
133	n/a	d = {1:1, 2:2, 3:3}
134	n/a	d.clear()
135	n/a	self.assertEqual(d, {})
136	n/a
137	n/a	self.assertRaises(TypeError, d.clear, None)
138	n/a
139	n/a	def test_update(self):
140	n/a	d = {}
141	n/a	d.update({1:100})
142	n/a	d.update({2:20})
143	n/a	d.update({1:1, 2:2, 3:3})
144	n/a	self.assertEqual(d, {1:1, 2:2, 3:3})
145	n/a
146	n/a	d.update()
147	n/a	self.assertEqual(d, {1:1, 2:2, 3:3})
148	n/a
149	n/a	self.assertRaises((TypeError, AttributeError), d.update, None)
150	n/a
151	n/a	class SimpleUserDict:
152	n/a	def __init__(self):
153	n/a	self.d = {1:1, 2:2, 3:3}
154	n/a	def keys(self):
155	n/a	return self.d.keys()
156	n/a	def __getitem__(self, i):
157	n/a	return self.d[i]
158	n/a	d.clear()
159	n/a	d.update(SimpleUserDict())
160	n/a	self.assertEqual(d, {1:1, 2:2, 3:3})
161	n/a
162	n/a	class Exc(Exception): pass
163	n/a
164	n/a	d.clear()
165	n/a	class FailingUserDict:
166	n/a	def keys(self):
167	n/a	raise Exc
168	n/a	self.assertRaises(Exc, d.update, FailingUserDict())
169	n/a
170	n/a	class FailingUserDict:
171	n/a	def keys(self):
172	n/a	class BogonIter:
173	n/a	def __init__(self):
174	n/a	self.i = 1
175	n/a	def __iter__(self):
176	n/a	return self
177	n/a	def __next__(self):
178	n/a	if self.i:
179	n/a	self.i = 0
180	n/a	return 'a'
181	n/a	raise Exc
182	n/a	return BogonIter()
183	n/a	def __getitem__(self, key):
184	n/a	return key
185	n/a	self.assertRaises(Exc, d.update, FailingUserDict())
186	n/a
187	n/a	class FailingUserDict:
188	n/a	def keys(self):
189	n/a	class BogonIter:
190	n/a	def __init__(self):
191	n/a	self.i = ord('a')
192	n/a	def __iter__(self):
193	n/a	return self
194	n/a	def __next__(self):
195	n/a	if self.i <= ord('z'):
196	n/a	rtn = chr(self.i)
197	n/a	self.i += 1
198	n/a	return rtn
199	n/a	raise StopIteration
200	n/a	return BogonIter()
201	n/a	def __getitem__(self, key):
202	n/a	raise Exc
203	n/a	self.assertRaises(Exc, d.update, FailingUserDict())
204	n/a
205	n/a	class badseq(object):
206	n/a	def __iter__(self):
207	n/a	return self
208	n/a	def __next__(self):
209	n/a	raise Exc()
210	n/a
211	n/a	self.assertRaises(Exc, {}.update, badseq())
212	n/a
213	n/a	self.assertRaises(ValueError, {}.update, [(1, 2, 3)])
214	n/a
215	n/a	def test_fromkeys(self):
216	n/a	self.assertEqual(dict.fromkeys('abc'), {'a':None, 'b':None, 'c':None})
217	n/a	d = {}
218	n/a	self.assertIsNot(d.fromkeys('abc'), d)
219	n/a	self.assertEqual(d.fromkeys('abc'), {'a':None, 'b':None, 'c':None})
220	n/a	self.assertEqual(d.fromkeys((4,5),0), {4:0, 5:0})
221	n/a	self.assertEqual(d.fromkeys([]), {})
222	n/a	def g():
223	n/a	yield 1
224	n/a	self.assertEqual(d.fromkeys(g()), {1:None})
225	n/a	self.assertRaises(TypeError, {}.fromkeys, 3)
226	n/a	class dictlike(dict): pass
227	n/a	self.assertEqual(dictlike.fromkeys('a'), {'a':None})
228	n/a	self.assertEqual(dictlike().fromkeys('a'), {'a':None})
229	n/a	self.assertIsInstance(dictlike.fromkeys('a'), dictlike)
230	n/a	self.assertIsInstance(dictlike().fromkeys('a'), dictlike)
231	n/a	class mydict(dict):
232	n/a	def __new__(cls):
233	n/a	return collections.UserDict()
234	n/a	ud = mydict.fromkeys('ab')
235	n/a	self.assertEqual(ud, {'a':None, 'b':None})
236	n/a	self.assertIsInstance(ud, collections.UserDict)
237	n/a	self.assertRaises(TypeError, dict.fromkeys)
238	n/a
239	n/a	class Exc(Exception): pass
240	n/a
241	n/a	class baddict1(dict):
242	n/a	def __init__(self):
243	n/a	raise Exc()
244	n/a
245	n/a	self.assertRaises(Exc, baddict1.fromkeys, [1])
246	n/a
247	n/a	class BadSeq(object):
248	n/a	def __iter__(self):
249	n/a	return self
250	n/a	def __next__(self):
251	n/a	raise Exc()
252	n/a
253	n/a	self.assertRaises(Exc, dict.fromkeys, BadSeq())
254	n/a
255	n/a	class baddict2(dict):
256	n/a	def __setitem__(self, key, value):
257	n/a	raise Exc()
258	n/a
259	n/a	self.assertRaises(Exc, baddict2.fromkeys, [1])
260	n/a
261	n/a	# test fast path for dictionary inputs
262	n/a	d = dict(zip(range(6), range(6)))
263	n/a	self.assertEqual(dict.fromkeys(d, 0), dict(zip(range(6), [0]*6)))
264	n/a
265	n/a	class baddict3(dict):
266	n/a	def __new__(cls):
267	n/a	return d
268	n/a	d = {i : i for i in range(10)}
269	n/a	res = d.copy()
270	n/a	res.update(a=None, b=None, c=None)
271	n/a	self.assertEqual(baddict3.fromkeys({"a", "b", "c"}), res)
272	n/a
273	n/a	def test_copy(self):
274	n/a	d = {1:1, 2:2, 3:3}
275	n/a	self.assertEqual(d.copy(), {1:1, 2:2, 3:3})
276	n/a	self.assertEqual({}.copy(), {})
277	n/a	self.assertRaises(TypeError, d.copy, None)
278	n/a
279	n/a	def test_get(self):
280	n/a	d = {}
281	n/a	self.assertIs(d.get('c'), None)
282	n/a	self.assertEqual(d.get('c', 3), 3)
283	n/a	d = {'a': 1, 'b': 2}
284	n/a	self.assertIs(d.get('c'), None)
285	n/a	self.assertEqual(d.get('c', 3), 3)
286	n/a	self.assertEqual(d.get('a'), 1)
287	n/a	self.assertEqual(d.get('a', 3), 1)
288	n/a	self.assertRaises(TypeError, d.get)
289	n/a	self.assertRaises(TypeError, d.get, None, None, None)
290	n/a
291	n/a	def test_setdefault(self):
292	n/a	# dict.setdefault()
293	n/a	d = {}
294	n/a	self.assertIs(d.setdefault('key0'), None)
295	n/a	d.setdefault('key0', [])
296	n/a	self.assertIs(d.setdefault('key0'), None)
297	n/a	d.setdefault('key', []).append(3)
298	n/a	self.assertEqual(d['key'][0], 3)
299	n/a	d.setdefault('key', []).append(4)
300	n/a	self.assertEqual(len(d['key']), 2)
301	n/a	self.assertRaises(TypeError, d.setdefault)
302	n/a
303	n/a	class Exc(Exception): pass
304	n/a
305	n/a	class BadHash(object):
306	n/a	fail = False
307	n/a	def __hash__(self):
308	n/a	if self.fail:
309	n/a	raise Exc()
310	n/a	else:
311	n/a	return 42
312	n/a
313	n/a	x = BadHash()
314	n/a	d[x] = 42
315	n/a	x.fail = True
316	n/a	self.assertRaises(Exc, d.setdefault, x, [])
317	n/a
318	n/a	def test_setdefault_atomic(self):
319	n/a	# Issue #13521: setdefault() calls __hash__ and __eq__ only once.
320	n/a	class Hashed(object):
321	n/a	def __init__(self):
322	n/a	self.hash_count = 0
323	n/a	self.eq_count = 0
324	n/a	def __hash__(self):
325	n/a	self.hash_count += 1
326	n/a	return 42
327	n/a	def __eq__(self, other):
328	n/a	self.eq_count += 1
329	n/a	return id(self) == id(other)
330	n/a	hashed1 = Hashed()
331	n/a	y = {hashed1: 5}
332	n/a	hashed2 = Hashed()
333	n/a	y.setdefault(hashed2, [])
334	n/a	self.assertEqual(hashed1.hash_count, 1)
335	n/a	self.assertEqual(hashed2.hash_count, 1)
336	n/a	self.assertEqual(hashed1.eq_count + hashed2.eq_count, 1)
337	n/a
338	n/a	def test_setitem_atomic_at_resize(self):
339	n/a	class Hashed(object):
340	n/a	def __init__(self):
341	n/a	self.hash_count = 0
342	n/a	self.eq_count = 0
343	n/a	def __hash__(self):
344	n/a	self.hash_count += 1
345	n/a	return 42
346	n/a	def __eq__(self, other):
347	n/a	self.eq_count += 1
348	n/a	return id(self) == id(other)
349	n/a	hashed1 = Hashed()
350	n/a	# 5 items
351	n/a	y = {hashed1: 5, 0: 0, 1: 1, 2: 2, 3: 3}
352	n/a	hashed2 = Hashed()
353	n/a	# 6th item forces a resize
354	n/a	y[hashed2] = []
355	n/a	self.assertEqual(hashed1.hash_count, 1)
356	n/a	self.assertEqual(hashed2.hash_count, 1)
357	n/a	self.assertEqual(hashed1.eq_count + hashed2.eq_count, 1)
358	n/a
359	n/a	def test_popitem(self):
360	n/a	# dict.popitem()
361	n/a	for copymode in -1, +1:
362	n/a	# -1: b has same structure as a
363	n/a	# +1: b is a.copy()
364	n/a	for log2size in range(12):
365	n/a	size = 2**log2size
366	n/a	a = {}
367	n/a	b = {}
368	n/a	for i in range(size):
369	n/a	a[repr(i)] = i
370	n/a	if copymode < 0:
371	n/a	b[repr(i)] = i
372	n/a	if copymode > 0:
373	n/a	b = a.copy()
374	n/a	for i in range(size):
375	n/a	ka, va = ta = a.popitem()
376	n/a	self.assertEqual(va, int(ka))
377	n/a	kb, vb = tb = b.popitem()
378	n/a	self.assertEqual(vb, int(kb))
379	n/a	self.assertFalse(copymode < 0 and ta != tb)
380	n/a	self.assertFalse(a)
381	n/a	self.assertFalse(b)
382	n/a
383	n/a	d = {}
384	n/a	self.assertRaises(KeyError, d.popitem)
385	n/a
386	n/a	def test_pop(self):
387	n/a	# Tests for pop with specified key
388	n/a	d = {}
389	n/a	k, v = 'abc', 'def'
390	n/a	d[k] = v
391	n/a	self.assertRaises(KeyError, d.pop, 'ghi')
392	n/a
393	n/a	self.assertEqual(d.pop(k), v)
394	n/a	self.assertEqual(len(d), 0)
395	n/a
396	n/a	self.assertRaises(KeyError, d.pop, k)
397	n/a
398	n/a	self.assertEqual(d.pop(k, v), v)
399	n/a	d[k] = v
400	n/a	self.assertEqual(d.pop(k, 1), v)
401	n/a
402	n/a	self.assertRaises(TypeError, d.pop)
403	n/a
404	n/a	class Exc(Exception): pass
405	n/a
406	n/a	class BadHash(object):
407	n/a	fail = False
408	n/a	def __hash__(self):
409	n/a	if self.fail:
410	n/a	raise Exc()
411	n/a	else:
412	n/a	return 42
413	n/a
414	n/a	x = BadHash()
415	n/a	d[x] = 42
416	n/a	x.fail = True
417	n/a	self.assertRaises(Exc, d.pop, x)
418	n/a
419	n/a	def test_mutating_iteration(self):
420	n/a	# changing dict size during iteration
421	n/a	d = {}
422	n/a	d[1] = 1
423	n/a	with self.assertRaises(RuntimeError):
424	n/a	for i in d:
425	n/a	d[i+1] = 1
426	n/a
427	n/a	def test_mutating_lookup(self):
428	n/a	# changing dict during a lookup (issue #14417)
429	n/a	class NastyKey:
430	n/a	mutate_dict = None
431	n/a
432	n/a	def __init__(self, value):
433	n/a	self.value = value
434	n/a
435	n/a	def __hash__(self):
436	n/a	# hash collision!
437	n/a	return 1
438	n/a
439	n/a	def __eq__(self, other):
440	n/a	if NastyKey.mutate_dict:
441	n/a	mydict, key = NastyKey.mutate_dict
442	n/a	NastyKey.mutate_dict = None
443	n/a	del mydict[key]
444	n/a	return self.value == other.value
445	n/a
446	n/a	key1 = NastyKey(1)
447	n/a	key2 = NastyKey(2)
448	n/a	d = {key1: 1}
449	n/a	NastyKey.mutate_dict = (d, key1)
450	n/a	d[key2] = 2
451	n/a	self.assertEqual(d, {key2: 2})
452	n/a
453	n/a	def test_repr(self):
454	n/a	d = {}
455	n/a	self.assertEqual(repr(d), '{}')
456	n/a	d[1] = 2
457	n/a	self.assertEqual(repr(d), '{1: 2}')
458	n/a	d = {}
459	n/a	d[1] = d
460	n/a	self.assertEqual(repr(d), '{1: {...}}')
461	n/a
462	n/a	class Exc(Exception): pass
463	n/a
464	n/a	class BadRepr(object):
465	n/a	def __repr__(self):
466	n/a	raise Exc()
467	n/a
468	n/a	d = {1: BadRepr()}
469	n/a	self.assertRaises(Exc, repr, d)
470	n/a
471	n/a	def test_eq(self):
472	n/a	self.assertEqual({}, {})
473	n/a	self.assertEqual({1: 2}, {1: 2})
474	n/a
475	n/a	class Exc(Exception): pass
476	n/a
477	n/a	class BadCmp(object):
478	n/a	def __eq__(self, other):
479	n/a	raise Exc()
480	n/a	def __hash__(self):
481	n/a	return 1
482	n/a
483	n/a	d1 = {BadCmp(): 1}
484	n/a	d2 = {1: 1}
485	n/a
486	n/a	with self.assertRaises(Exc):
487	n/a	d1 == d2
488	n/a
489	n/a	def test_keys_contained(self):
490	n/a	self.helper_keys_contained(lambda x: x.keys())
491	n/a	self.helper_keys_contained(lambda x: x.items())
492	n/a
493	n/a	def helper_keys_contained(self, fn):
494	n/a	# Test rich comparisons against dict key views, which should behave the
495	n/a	# same as sets.
496	n/a	empty = fn(dict())
497	n/a	empty2 = fn(dict())
498	n/a	smaller = fn({1:1, 2:2})
499	n/a	larger = fn({1:1, 2:2, 3:3})
500	n/a	larger2 = fn({1:1, 2:2, 3:3})
501	n/a	larger3 = fn({4:1, 2:2, 3:3})
502	n/a
503	n/a	self.assertTrue(smaller < larger)
504	n/a	self.assertTrue(smaller <= larger)
505	n/a	self.assertTrue(larger > smaller)
506	n/a	self.assertTrue(larger >= smaller)
507	n/a
508	n/a	self.assertFalse(smaller >= larger)
509	n/a	self.assertFalse(smaller > larger)
510	n/a	self.assertFalse(larger <= smaller)
511	n/a	self.assertFalse(larger < smaller)
512	n/a
513	n/a	self.assertFalse(smaller < larger3)
514	n/a	self.assertFalse(smaller <= larger3)
515	n/a	self.assertFalse(larger3 > smaller)
516	n/a	self.assertFalse(larger3 >= smaller)
517	n/a
518	n/a	# Inequality strictness
519	n/a	self.assertTrue(larger2 >= larger)
520	n/a	self.assertTrue(larger2 <= larger)
521	n/a	self.assertFalse(larger2 > larger)
522	n/a	self.assertFalse(larger2 < larger)
523	n/a
524	n/a	self.assertTrue(larger == larger2)
525	n/a	self.assertTrue(smaller != larger)
526	n/a
527	n/a	# There is an optimization on the zero-element case.
528	n/a	self.assertTrue(empty == empty2)
529	n/a	self.assertFalse(empty != empty2)
530	n/a	self.assertFalse(empty == smaller)
531	n/a	self.assertTrue(empty != smaller)
532	n/a
533	n/a	# With the same size, an elementwise compare happens
534	n/a	self.assertTrue(larger != larger3)
535	n/a	self.assertFalse(larger == larger3)
536	n/a
537	n/a	def test_errors_in_view_containment_check(self):
538	n/a	class C:
539	n/a	def __eq__(self, other):
540	n/a	raise RuntimeError
541	n/a
542	n/a	d1 = {1: C()}
543	n/a	d2 = {1: C()}
544	n/a	with self.assertRaises(RuntimeError):
545	n/a	d1.items() == d2.items()
546	n/a	with self.assertRaises(RuntimeError):
547	n/a	d1.items() != d2.items()
548	n/a	with self.assertRaises(RuntimeError):
549	n/a	d1.items() <= d2.items()
550	n/a	with self.assertRaises(RuntimeError):
551	n/a	d1.items() >= d2.items()
552	n/a
553	n/a	d3 = {1: C(), 2: C()}
554	n/a	with self.assertRaises(RuntimeError):
555	n/a	d2.items() < d3.items()
556	n/a	with self.assertRaises(RuntimeError):
557	n/a	d3.items() > d2.items()
558	n/a
559	n/a	def test_dictview_set_operations_on_keys(self):
560	n/a	k1 = {1:1, 2:2}.keys()
561	n/a	k2 = {1:1, 2:2, 3:3}.keys()
562	n/a	k3 = {4:4}.keys()
563	n/a
564	n/a	self.assertEqual(k1 - k2, set())
565	n/a	self.assertEqual(k1 - k3, {1,2})
566	n/a	self.assertEqual(k2 - k1, {3})
567	n/a	self.assertEqual(k3 - k1, {4})
568	n/a	self.assertEqual(k1 & k2, {1,2})
569	n/a	self.assertEqual(k1 & k3, set())
570	n/a	self.assertEqual(k1 \| k2, {1,2,3})
571	n/a	self.assertEqual(k1 ^ k2, {3})
572	n/a	self.assertEqual(k1 ^ k3, {1,2,4})
573	n/a
574	n/a	def test_dictview_set_operations_on_items(self):
575	n/a	k1 = {1:1, 2:2}.items()
576	n/a	k2 = {1:1, 2:2, 3:3}.items()
577	n/a	k3 = {4:4}.items()
578	n/a
579	n/a	self.assertEqual(k1 - k2, set())
580	n/a	self.assertEqual(k1 - k3, {(1,1), (2,2)})
581	n/a	self.assertEqual(k2 - k1, {(3,3)})
582	n/a	self.assertEqual(k3 - k1, {(4,4)})
583	n/a	self.assertEqual(k1 & k2, {(1,1), (2,2)})
584	n/a	self.assertEqual(k1 & k3, set())
585	n/a	self.assertEqual(k1 \| k2, {(1,1), (2,2), (3,3)})
586	n/a	self.assertEqual(k1 ^ k2, {(3,3)})
587	n/a	self.assertEqual(k1 ^ k3, {(1,1), (2,2), (4,4)})
588	n/a
589	n/a	def test_dictview_mixed_set_operations(self):
590	n/a	# Just a few for .keys()
591	n/a	self.assertTrue({1:1}.keys() == {1})
592	n/a	self.assertTrue({1} == {1:1}.keys())
593	n/a	self.assertEqual({1:1}.keys() \| {2}, {1, 2})
594	n/a	self.assertEqual({2} \| {1:1}.keys(), {1, 2})
595	n/a	# And a few for .items()
596	n/a	self.assertTrue({1:1}.items() == {(1,1)})
597	n/a	self.assertTrue({(1,1)} == {1:1}.items())
598	n/a	self.assertEqual({1:1}.items() \| {2}, {(1,1), 2})
599	n/a	self.assertEqual({2} \| {1:1}.items(), {(1,1), 2})
600	n/a
601	n/a	def test_missing(self):
602	n/a	# Make sure dict doesn't have a __missing__ method
603	n/a	self.assertFalse(hasattr(dict, "__missing__"))
604	n/a	self.assertFalse(hasattr({}, "__missing__"))
605	n/a	# Test several cases:
606	n/a	# (D) subclass defines __missing__ method returning a value
607	n/a	# (E) subclass defines __missing__ method raising RuntimeError
608	n/a	# (F) subclass sets __missing__ instance variable (no effect)
609	n/a	# (G) subclass doesn't define __missing__ at all
610	n/a	class D(dict):
611	n/a	def __missing__(self, key):
612	n/a	return 42
613	n/a	d = D({1: 2, 3: 4})
614	n/a	self.assertEqual(d[1], 2)
615	n/a	self.assertEqual(d[3], 4)
616	n/a	self.assertNotIn(2, d)
617	n/a	self.assertNotIn(2, d.keys())
618	n/a	self.assertEqual(d[2], 42)
619	n/a
620	n/a	class E(dict):
621	n/a	def __missing__(self, key):
622	n/a	raise RuntimeError(key)
623	n/a	e = E()
624	n/a	with self.assertRaises(RuntimeError) as c:
625	n/a	e[42]
626	n/a	self.assertEqual(c.exception.args, (42,))
627	n/a
628	n/a	class F(dict):
629	n/a	def __init__(self):
630	n/a	# An instance variable __missing__ should have no effect
631	n/a	self.__missing__ = lambda key: None
632	n/a	f = F()
633	n/a	with self.assertRaises(KeyError) as c:
634	n/a	f[42]
635	n/a	self.assertEqual(c.exception.args, (42,))
636	n/a
637	n/a	class G(dict):
638	n/a	pass
639	n/a	g = G()
640	n/a	with self.assertRaises(KeyError) as c:
641	n/a	g[42]
642	n/a	self.assertEqual(c.exception.args, (42,))
643	n/a
644	n/a	def test_tuple_keyerror(self):
645	n/a	# SF #1576657
646	n/a	d = {}
647	n/a	with self.assertRaises(KeyError) as c:
648	n/a	d[(1,)]
649	n/a	self.assertEqual(c.exception.args, ((1,),))
650	n/a
651	n/a	def test_bad_key(self):
652	n/a	# Dictionary lookups should fail if __eq__() raises an exception.
653	n/a	class CustomException(Exception):
654	n/a	pass
655	n/a
656	n/a	class BadDictKey:
657	n/a	def __hash__(self):
658	n/a	return hash(self.__class__)
659	n/a
660	n/a	def __eq__(self, other):
661	n/a	if isinstance(other, self.__class__):
662	n/a	raise CustomException
663	n/a	return other
664	n/a
665	n/a	d = {}
666	n/a	x1 = BadDictKey()
667	n/a	x2 = BadDictKey()
668	n/a	d[x1] = 1
669	n/a	for stmt in ['d[x2] = 2',
670	n/a	'z = d[x2]',
671	n/a	'x2 in d',
672	n/a	'd.get(x2)',
673	n/a	'd.setdefault(x2, 42)',
674	n/a	'd.pop(x2)',
675	n/a	'd.update({x2: 2})']:
676	n/a	with self.assertRaises(CustomException):
677	n/a	exec(stmt, locals())
678	n/a
679	n/a	def test_resize1(self):
680	n/a	# Dict resizing bug, found by Jack Jansen in 2.2 CVS development.
681	n/a	# This version got an assert failure in debug build, infinite loop in
682	n/a	# release build. Unfortunately, provoking this kind of stuff requires
683	n/a	# a mix of inserts and deletes hitting exactly the right hash codes in
684	n/a	# exactly the right order, and I can't think of a randomized approach
685	n/a	# that would be likely to hit a failing case in reasonable time.
686	n/a
687	n/a	d = {}
688	n/a	for i in range(5):
689	n/a	d[i] = i
690	n/a	for i in range(5):
691	n/a	del d[i]
692	n/a	for i in range(5, 9): # i==8 was the problem
693	n/a	d[i] = i
694	n/a
695	n/a	def test_resize2(self):
696	n/a	# Another dict resizing bug (SF bug #1456209).
697	n/a	# This caused Segmentation faults or Illegal instructions.
698	n/a
699	n/a	class X(object):
700	n/a	def __hash__(self):
701	n/a	return 5
702	n/a	def __eq__(self, other):
703	n/a	if resizing:
704	n/a	d.clear()
705	n/a	return False
706	n/a	d = {}
707	n/a	resizing = False
708	n/a	d[X()] = 1
709	n/a	d[X()] = 2
710	n/a	d[X()] = 3
711	n/a	d[X()] = 4
712	n/a	d[X()] = 5
713	n/a	# now trigger a resize
714	n/a	resizing = True
715	n/a	d[9] = 6
716	n/a
717	n/a	def test_empty_presized_dict_in_freelist(self):
718	n/a	# Bug #3537: if an empty but presized dict with a size larger
719	n/a	# than 7 was in the freelist, it triggered an assertion failure
720	n/a	with self.assertRaises(ZeroDivisionError):
721	n/a	d = {'a': 1 // 0, 'b': None, 'c': None, 'd': None, 'e': None,
722	n/a	'f': None, 'g': None, 'h': None}
723	n/a	d = {}
724	n/a
725	n/a	def test_container_iterator(self):
726	n/a	# Bug #3680: tp_traverse was not implemented for dictiter and
727	n/a	# dictview objects.
728	n/a	class C(object):
729	n/a	pass
730	n/a	views = (dict.items, dict.values, dict.keys)
731	n/a	for v in views:
732	n/a	obj = C()
733	n/a	ref = weakref.ref(obj)
734	n/a	container = {obj: 1}
735	n/a	obj.v = v(container)
736	n/a	obj.x = iter(obj.v)
737	n/a	del obj, container
738	n/a	gc.collect()
739	n/a	self.assertIs(ref(), None, "Cycle was not collected")
740	n/a
741	n/a	def _not_tracked(self, t):
742	n/a	# Nested containers can take several collections to untrack
743	n/a	gc.collect()
744	n/a	gc.collect()
745	n/a	self.assertFalse(gc.is_tracked(t), t)
746	n/a
747	n/a	def _tracked(self, t):
748	n/a	self.assertTrue(gc.is_tracked(t), t)
749	n/a	gc.collect()
750	n/a	gc.collect()
751	n/a	self.assertTrue(gc.is_tracked(t), t)
752	n/a
753	n/a	@support.cpython_only
754	n/a	def test_track_literals(self):
755	n/a	# Test GC-optimization of dict literals
756	n/a	x, y, z, w = 1.5, "a", (1, None), []
757	n/a
758	n/a	self._not_tracked({})
759	n/a	self._not_tracked({x:(), y:x, z:1})
760	n/a	self._not_tracked({1: "a", "b": 2})
761	n/a	self._not_tracked({1: 2, (None, True, False, ()): int})
762	n/a	self._not_tracked({1: object()})
763	n/a
764	n/a	# Dicts with mutable elements are always tracked, even if those
765	n/a	# elements are not tracked right now.
766	n/a	self._tracked({1: []})
767	n/a	self._tracked({1: ([],)})
768	n/a	self._tracked({1: {}})
769	n/a	self._tracked({1: set()})
770	n/a
771	n/a	@support.cpython_only
772	n/a	def test_track_dynamic(self):
773	n/a	# Test GC-optimization of dynamically-created dicts
774	n/a	class MyObject(object):
775	n/a	pass
776	n/a	x, y, z, w, o = 1.5, "a", (1, object()), [], MyObject()
777	n/a
778	n/a	d = dict()
779	n/a	self._not_tracked(d)
780	n/a	d[1] = "a"
781	n/a	self._not_tracked(d)
782	n/a	d[y] = 2
783	n/a	self._not_tracked(d)
784	n/a	d[z] = 3
785	n/a	self._not_tracked(d)
786	n/a	self._not_tracked(d.copy())
787	n/a	d[4] = w
788	n/a	self._tracked(d)
789	n/a	self._tracked(d.copy())
790	n/a	d[4] = None
791	n/a	self._not_tracked(d)
792	n/a	self._not_tracked(d.copy())
793	n/a
794	n/a	# dd isn't tracked right now, but it may mutate and therefore d
795	n/a	# which contains it must be tracked.
796	n/a	d = dict()
797	n/a	dd = dict()
798	n/a	d[1] = dd
799	n/a	self._not_tracked(dd)
800	n/a	self._tracked(d)
801	n/a	dd[1] = d
802	n/a	self._tracked(dd)
803	n/a
804	n/a	d = dict.fromkeys([x, y, z])
805	n/a	self._not_tracked(d)
806	n/a	dd = dict()
807	n/a	dd.update(d)
808	n/a	self._not_tracked(dd)
809	n/a	d = dict.fromkeys([x, y, z, o])
810	n/a	self._tracked(d)
811	n/a	dd = dict()
812	n/a	dd.update(d)
813	n/a	self._tracked(dd)
814	n/a
815	n/a	d = dict(x=x, y=y, z=z)
816	n/a	self._not_tracked(d)
817	n/a	d = dict(x=x, y=y, z=z, w=w)
818	n/a	self._tracked(d)
819	n/a	d = dict()
820	n/a	d.update(x=x, y=y, z=z)
821	n/a	self._not_tracked(d)
822	n/a	d.update(w=w)
823	n/a	self._tracked(d)
824	n/a
825	n/a	d = dict([(x, y), (z, 1)])
826	n/a	self._not_tracked(d)
827	n/a	d = dict([(x, y), (z, w)])
828	n/a	self._tracked(d)
829	n/a	d = dict()
830	n/a	d.update([(x, y), (z, 1)])
831	n/a	self._not_tracked(d)
832	n/a	d.update([(x, y), (z, w)])
833	n/a	self._tracked(d)
834	n/a
835	n/a	@support.cpython_only
836	n/a	def test_track_subtypes(self):
837	n/a	# Dict subtypes are always tracked
838	n/a	class MyDict(dict):
839	n/a	pass
840	n/a	self._tracked(MyDict())
841	n/a
842	n/a	def make_shared_key_dict(self, n):
843	n/a	class C:
844	n/a	pass
845	n/a
846	n/a	dicts = []
847	n/a	for i in range(n):
848	n/a	a = C()
849	n/a	a.x, a.y, a.z = 1, 2, 3
850	n/a	dicts.append(a.__dict__)
851	n/a
852	n/a	return dicts
853	n/a
854	n/a	@support.cpython_only
855	n/a	def test_splittable_setdefault(self):
856	n/a	"""split table must be combined when setdefault()
857	n/a	breaks insertion order"""
858	n/a	a, b = self.make_shared_key_dict(2)
859	n/a
860	n/a	a['a'] = 1
861	n/a	size_a = sys.getsizeof(a)
862	n/a	a['b'] = 2
863	n/a	b.setdefault('b', 2)
864	n/a	size_b = sys.getsizeof(b)
865	n/a	b['a'] = 1
866	n/a
867	n/a	self.assertGreater(size_b, size_a)
868	n/a	self.assertEqual(list(a), ['x', 'y', 'z', 'a', 'b'])
869	n/a	self.assertEqual(list(b), ['x', 'y', 'z', 'b', 'a'])
870	n/a
871	n/a	@support.cpython_only
872	n/a	def test_splittable_del(self):
873	n/a	"""split table must be combined when del d[k]"""
874	n/a	a, b = self.make_shared_key_dict(2)
875	n/a
876	n/a	orig_size = sys.getsizeof(a)
877	n/a
878	n/a	del a['y'] # split table is combined
879	n/a	with self.assertRaises(KeyError):
880	n/a	del a['y']
881	n/a
882	n/a	self.assertGreater(sys.getsizeof(a), orig_size)
883	n/a	self.assertEqual(list(a), ['x', 'z'])
884	n/a	self.assertEqual(list(b), ['x', 'y', 'z'])
885	n/a
886	n/a	# Two dicts have different insertion order.
887	n/a	a['y'] = 42
888	n/a	self.assertEqual(list(a), ['x', 'z', 'y'])
889	n/a	self.assertEqual(list(b), ['x', 'y', 'z'])
890	n/a
891	n/a	@support.cpython_only
892	n/a	def test_splittable_pop(self):
893	n/a	"""split table must be combined when d.pop(k)"""
894	n/a	a, b = self.make_shared_key_dict(2)
895	n/a
896	n/a	orig_size = sys.getsizeof(a)
897	n/a
898	n/a	a.pop('y') # split table is combined
899	n/a	with self.assertRaises(KeyError):
900	n/a	a.pop('y')
901	n/a
902	n/a	self.assertGreater(sys.getsizeof(a), orig_size)
903	n/a	self.assertEqual(list(a), ['x', 'z'])
904	n/a	self.assertEqual(list(b), ['x', 'y', 'z'])
905	n/a
906	n/a	# Two dicts have different insertion order.
907	n/a	a['y'] = 42
908	n/a	self.assertEqual(list(a), ['x', 'z', 'y'])
909	n/a	self.assertEqual(list(b), ['x', 'y', 'z'])
910	n/a
911	n/a	@support.cpython_only
912	n/a	def test_splittable_pop_pending(self):
913	n/a	"""pop a pending key in a splitted table should not crash"""
914	n/a	a, b = self.make_shared_key_dict(2)
915	n/a
916	n/a	a['a'] = 4
917	n/a	with self.assertRaises(KeyError):
918	n/a	b.pop('a')
919	n/a
920	n/a	@support.cpython_only
921	n/a	def test_splittable_popitem(self):
922	n/a	"""split table must be combined when d.popitem()"""
923	n/a	a, b = self.make_shared_key_dict(2)
924	n/a
925	n/a	orig_size = sys.getsizeof(a)
926	n/a
927	n/a	item = a.popitem() # split table is combined
928	n/a	self.assertEqual(item, ('z', 3))
929	n/a	with self.assertRaises(KeyError):
930	n/a	del a['z']
931	n/a
932	n/a	self.assertGreater(sys.getsizeof(a), orig_size)
933	n/a	self.assertEqual(list(a), ['x', 'y'])
934	n/a	self.assertEqual(list(b), ['x', 'y', 'z'])
935	n/a
936	n/a	@support.cpython_only
937	n/a	def test_splittable_setattr_after_pop(self):
938	n/a	"""setattr() must not convert combined table into split table."""
939	n/a	# Issue 28147
940	n/a	import _testcapi
941	n/a
942	n/a	class C:
943	n/a	pass
944	n/a	a = C()
945	n/a
946	n/a	a.a = 1
947	n/a	self.assertTrue(_testcapi.dict_hassplittable(a.__dict__))
948	n/a
949	n/a	# dict.pop() convert it to combined table
950	n/a	a.__dict__.pop('a')
951	n/a	self.assertFalse(_testcapi.dict_hassplittable(a.__dict__))
952	n/a
953	n/a	# But C should not convert a.__dict__ to split table again.
954	n/a	a.a = 1
955	n/a	self.assertFalse(_testcapi.dict_hassplittable(a.__dict__))
956	n/a
957	n/a	# Same for popitem()
958	n/a	a = C()
959	n/a	a.a = 2
960	n/a	self.assertTrue(_testcapi.dict_hassplittable(a.__dict__))
961	n/a	a.__dict__.popitem()
962	n/a	self.assertFalse(_testcapi.dict_hassplittable(a.__dict__))
963	n/a	a.a = 3
964	n/a	self.assertFalse(_testcapi.dict_hassplittable(a.__dict__))
965	n/a
966	n/a	def test_iterator_pickling(self):
967	n/a	for proto in range(pickle.HIGHEST_PROTOCOL + 1):
968	n/a	data = {1:"a", 2:"b", 3:"c"}
969	n/a	it = iter(data)
970	n/a	d = pickle.dumps(it, proto)
971	n/a	it = pickle.loads(d)
972	n/a	self.assertEqual(sorted(it), sorted(data))
973	n/a
974	n/a	it = pickle.loads(d)
975	n/a	try:
976	n/a	drop = next(it)
977	n/a	except StopIteration:
978	n/a	continue
979	n/a	d = pickle.dumps(it, proto)
980	n/a	it = pickle.loads(d)
981	n/a	del data[drop]
982	n/a	self.assertEqual(sorted(it), sorted(data))
983	n/a
984	n/a	def test_itemiterator_pickling(self):
985	n/a	for proto in range(pickle.HIGHEST_PROTOCOL + 1):
986	n/a	data = {1:"a", 2:"b", 3:"c"}
987	n/a	# dictviews aren't picklable, only their iterators
988	n/a	itorg = iter(data.items())
989	n/a	d = pickle.dumps(itorg, proto)
990	n/a	it = pickle.loads(d)
991	n/a	# note that the type of the unpickled iterator
992	n/a	# is not necessarily the same as the original. It is
993	n/a	# merely an object supporting the iterator protocol, yielding
994	n/a	# the same objects as the original one.
995	n/a	# self.assertEqual(type(itorg), type(it))
996	n/a	self.assertIsInstance(it, collections.abc.Iterator)
997	n/a	self.assertEqual(dict(it), data)
998	n/a
999	n/a	it = pickle.loads(d)
1000	n/a	drop = next(it)
1001	n/a	d = pickle.dumps(it, proto)
1002	n/a	it = pickle.loads(d)
1003	n/a	del data[drop[0]]
1004	n/a	self.assertEqual(dict(it), data)
1005	n/a
1006	n/a	def test_valuesiterator_pickling(self):
1007	n/a	for proto in range(pickle.HIGHEST_PROTOCOL):
1008	n/a	data = {1:"a", 2:"b", 3:"c"}
1009	n/a	# data.values() isn't picklable, only its iterator
1010	n/a	it = iter(data.values())
1011	n/a	d = pickle.dumps(it, proto)
1012	n/a	it = pickle.loads(d)
1013	n/a	self.assertEqual(sorted(list(it)), sorted(list(data.values())))
1014	n/a
1015	n/a	it = pickle.loads(d)
1016	n/a	drop = next(it)
1017	n/a	d = pickle.dumps(it, proto)
1018	n/a	it = pickle.loads(d)
1019	n/a	values = list(it) + [drop]
1020	n/a	self.assertEqual(sorted(values), sorted(list(data.values())))
1021	n/a
1022	n/a	def test_instance_dict_getattr_str_subclass(self):
1023	n/a	class Foo:
1024	n/a	def __init__(self, msg):
1025	n/a	self.msg = msg
1026	n/a	f = Foo('123')
1027	n/a	class _str(str):
1028	n/a	pass
1029	n/a	self.assertEqual(f.msg, getattr(f, _str('msg')))
1030	n/a	self.assertEqual(f.msg, f.__dict__[_str('msg')])
1031	n/a
1032	n/a	def test_object_set_item_single_instance_non_str_key(self):
1033	n/a	class Foo: pass
1034	n/a	f = Foo()
1035	n/a	f.__dict__[1] = 1
1036	n/a	f.a = 'a'
1037	n/a	self.assertEqual(f.__dict__, {1:1, 'a':'a'})
1038	n/a
1039	n/a	def check_reentrant_insertion(self, mutate):
1040	n/a	# This object will trigger mutation of the dict when replaced
1041	n/a	# by another value. Note this relies on refcounting: the test
1042	n/a	# won't achieve its purpose on fully-GCed Python implementations.
1043	n/a	class Mutating:
1044	n/a	def __del__(self):
1045	n/a	mutate(d)
1046	n/a
1047	n/a	d = {k: Mutating() for k in 'abcdefghijklmnopqr'}
1048	n/a	for k in list(d):
1049	n/a	d[k] = k
1050	n/a
1051	n/a	def test_reentrant_insertion(self):
1052	n/a	# Reentrant insertion shouldn't crash (see issue #22653)
1053	n/a	def mutate(d):
1054	n/a	d['b'] = 5
1055	n/a	self.check_reentrant_insertion(mutate)
1056	n/a
1057	n/a	def mutate(d):
1058	n/a	d.update(self.__dict__)
1059	n/a	d.clear()
1060	n/a	self.check_reentrant_insertion(mutate)
1061	n/a
1062	n/a	def mutate(d):
1063	n/a	while d:
1064	n/a	d.popitem()
1065	n/a	self.check_reentrant_insertion(mutate)
1066	n/a
1067	n/a	def test_merge_and_mutate(self):
1068	n/a	class X:
1069	n/a	def __hash__(self):
1070	n/a	return 0
1071	n/a
1072	n/a	def __eq__(self, o):
1073	n/a	other.clear()
1074	n/a	return False
1075	n/a
1076	n/a	l = [(i,0) for i in range(1, 1337)]
1077	n/a	other = dict(l)
1078	n/a	other[X()] = 0
1079	n/a	d = {X(): 0, 1: 1}
1080	n/a	self.assertRaises(RuntimeError, d.update, other)
1081	n/a
1082	n/a	def test_free_after_iterating(self):
1083	n/a	support.check_free_after_iterating(self, iter, dict)
1084	n/a	support.check_free_after_iterating(self, lambda d: iter(d.keys()), dict)
1085	n/a	support.check_free_after_iterating(self, lambda d: iter(d.values()), dict)
1086	n/a	support.check_free_after_iterating(self, lambda d: iter(d.items()), dict)
1087	n/a
1088	n/a
1089	n/a	class CAPITest(unittest.TestCase):
1090	n/a
1091	n/a	# Test _PyDict_GetItem_KnownHash()
1092	n/a	@support.cpython_only
1093	n/a	def test_getitem_knownhash(self):
1094	n/a	from _testcapi import dict_getitem_knownhash
1095	n/a
1096	n/a	d = {'x': 1, 'y': 2, 'z': 3}
1097	n/a	self.assertEqual(dict_getitem_knownhash(d, 'x', hash('x')), 1)
1098	n/a	self.assertEqual(dict_getitem_knownhash(d, 'y', hash('y')), 2)
1099	n/a	self.assertEqual(dict_getitem_knownhash(d, 'z', hash('z')), 3)
1100	n/a
1101	n/a	# not a dict
1102	n/a	self.assertRaises(SystemError, dict_getitem_knownhash, [], 1, hash(1))
1103	n/a	# key does not exist
1104	n/a	self.assertRaises(KeyError, dict_getitem_knownhash, {}, 1, hash(1))
1105	n/a
1106	n/a	class Exc(Exception): pass
1107	n/a	class BadEq:
1108	n/a	def __eq__(self, other):
1109	n/a	raise Exc
1110	n/a	def __hash__(self):
1111	n/a	return 7
1112	n/a
1113	n/a	k1, k2 = BadEq(), BadEq()
1114	n/a	d = {k1: 1}
1115	n/a	self.assertEqual(dict_getitem_knownhash(d, k1, hash(k1)), 1)
1116	n/a	self.assertRaises(Exc, dict_getitem_knownhash, d, k2, hash(k2))
1117	n/a
1118	n/a
1119	n/a	from test import mapping_tests
1120	n/a
1121	n/a	class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
1122	n/a	type2test = dict
1123	n/a
1124	n/a	class Dict(dict):
1125	n/a	pass
1126	n/a
1127	n/a	class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
1128	n/a	type2test = Dict
1129	n/a
1130	n/a
1131	n/a	if __name__ == "__main__":
1132	n/a	unittest.main()