Debian Codegraph @

Lib/test/test_dict.py

raw
1 import collections
2 import collections.abc
3 import gc
4 import pickle
5 import random
6 import re
7 import string
8 import sys
9 import unittest
10 import weakref
11 from test import support
12 from test.support import import_helper
13
14
15 class CustomHash:
16 def __init__(self, hash):
17 self.hash = hash
18 def __hash__(self):
19 return self.hash
20 def __repr__(self):
21 return f'<CustomHash {self.hash} at {id(self):#x}>'
22
23
24 class DictTest(unittest.TestCase):
25
26 def test_invalid_keyword_arguments(self):
27 class Custom(dict):
28 pass
29 for invalid in {1 : 2}, Custom({1 : 2}):
30 with self.assertRaises(TypeError):
31 dict(**invalid)
32 with self.assertRaises(TypeError):
33 {}.update(**invalid)
34
35 def test_constructor(self):
36 # calling built-in types without argument must return empty
37 self.assertEqual(dict(), {})
38 self.assertIsNot(dict(), {})
39
40 def test_literal_constructor(self):
41 # check literal constructor for different sized dicts
42 # (to exercise the BUILD_MAP oparg).
43 for n in (0, 1, 6, 256, 400):
44 items = [(''.join(random.sample(string.ascii_letters, 8)), i)
45 for i in range(n)]
46 random.shuffle(items)
47 formatted_items = ('{!r}: {:d}'.format(k, v) for k, v in items)
48 dictliteral = '{' + ', '.join(formatted_items) + '}'
49 self.assertEqual(eval(dictliteral), dict(items))
50
51 def test_merge_operator(self):
52
53 a = {0: 0, 1: 1, 2: 1}
54 b = {1: 1, 2: 2, 3: 3}
55
56 c = a.copy()
57 c |= b
58
59 self.assertEqual(a | b, {0: 0, 1: 1, 2: 2, 3: 3})
60 self.assertEqual(c, {0: 0, 1: 1, 2: 2, 3: 3})
61
62 c = b.copy()
63 c |= a
64
65 self.assertEqual(b | a, {1: 1, 2: 1, 3: 3, 0: 0})
66 self.assertEqual(c, {1: 1, 2: 1, 3: 3, 0: 0})
67
68 c = a.copy()
69 c |= [(1, 1), (2, 2), (3, 3)]
70
71 self.assertEqual(c, {0: 0, 1: 1, 2: 2, 3: 3})
72
73 self.assertIs(a.__or__(None), NotImplemented)
74 self.assertIs(a.__or__(()), NotImplemented)
75 self.assertIs(a.__or__("BAD"), NotImplemented)
76 self.assertIs(a.__or__(""), NotImplemented)
77
78 self.assertRaises(TypeError, a.__ior__, None)
79 self.assertEqual(a.__ior__(()), {0: 0, 1: 1, 2: 1})
80 self.assertRaises(ValueError, a.__ior__, "BAD")
81 self.assertEqual(a.__ior__(""), {0: 0, 1: 1, 2: 1})
82
83 def test_bool(self):
84 self.assertIs(not {}, True)
85 self.assertTrue({1: 2})
86 self.assertIs(bool({}), False)
87 self.assertIs(bool({1: 2}), True)
88
89 def test_keys(self):
90 d = {}
91 self.assertEqual(set(d.keys()), set())
92 d = {'a': 1, 'b': 2}
93 k = d.keys()
94 self.assertEqual(set(k), {'a', 'b'})
95 self.assertIn('a', k)
96 self.assertIn('b', k)
97 self.assertIn('a', d)
98 self.assertIn('b', d)
99 self.assertRaises(TypeError, d.keys, None)
100 self.assertEqual(repr(dict(a=1).keys()), "dict_keys(['a'])")
101
102 def test_values(self):
103 d = {}
104 self.assertEqual(set(d.values()), set())
105 d = {1:2}
106 self.assertEqual(set(d.values()), {2})
107 self.assertRaises(TypeError, d.values, None)
108 self.assertEqual(repr(dict(a=1).values()), "dict_values([1])")
109
110 def test_items(self):
111 d = {}
112 self.assertEqual(set(d.items()), set())
113
114 d = {1:2}
115 self.assertEqual(set(d.items()), {(1, 2)})
116 self.assertRaises(TypeError, d.items, None)
117 self.assertEqual(repr(dict(a=1).items()), "dict_items([('a', 1)])")
118
119 def test_views_mapping(self):
120 mappingproxy = type(type.__dict__)
121 class Dict(dict):
122 pass
123 for cls in [dict, Dict]:
124 d = cls()
125 m1 = d.keys().mapping
126 m2 = d.values().mapping
127 m3 = d.items().mapping
128
129 for m in [m1, m2, m3]:
130 self.assertIsInstance(m, mappingproxy)
131 self.assertEqual(m, d)
132
133 d["foo"] = "bar"
134
135 for m in [m1, m2, m3]:
136 self.assertIsInstance(m, mappingproxy)
137 self.assertEqual(m, d)
138
139 def test_contains(self):
140 d = {}
141 self.assertNotIn('a', d)
142 self.assertFalse('a' in d)
143 self.assertTrue('a' not in d)
144 d = {'a': 1, 'b': 2}
145 self.assertIn('a', d)
146 self.assertIn('b', d)
147 self.assertNotIn('c', d)
148
149 self.assertRaises(TypeError, d.__contains__)
150
151 def test_len(self):
152 d = {}
153 self.assertEqual(len(d), 0)
154 d = {'a': 1, 'b': 2}
155 self.assertEqual(len(d), 2)
156
157 def test_getitem(self):
158 d = {'a': 1, 'b': 2}
159 self.assertEqual(d['a'], 1)
160 self.assertEqual(d['b'], 2)
161 d['c'] = 3
162 d['a'] = 4
163 self.assertEqual(d['c'], 3)
164 self.assertEqual(d['a'], 4)
165 del d['b']
166 self.assertEqual(d, {'a': 4, 'c': 3})
167
168 self.assertRaises(TypeError, d.__getitem__)
169
170 class BadEq(object):
171 def __eq__(self, other):
172 raise Exc()
173 def __hash__(self):
174 return 24
175
176 d = {}
177 d[BadEq()] = 42
178 self.assertRaises(KeyError, d.__getitem__, 23)
179
180 class Exc(Exception): pass
181
182 class BadHash(object):
183 fail = False
184 def __hash__(self):
185 if self.fail:
186 raise Exc()
187 else:
188 return 42
189
190 x = BadHash()
191 d[x] = 42
192 x.fail = True
193 self.assertRaises(Exc, d.__getitem__, x)
194
195 def test_clear(self):
196 d = {1:1, 2:2, 3:3}
197 d.clear()
198 self.assertEqual(d, {})
199
200 self.assertRaises(TypeError, d.clear, None)
201
202 def test_update(self):
203 d = {}
204 d.update({1:100})
205 d.update({2:20})
206 d.update({1:1, 2:2, 3:3})
207 self.assertEqual(d, {1:1, 2:2, 3:3})
208
209 d.update()
210 self.assertEqual(d, {1:1, 2:2, 3:3})
211
212 self.assertRaises((TypeError, AttributeError), d.update, None)
213
214 class SimpleUserDict:
215 def __init__(self):
216 self.d = {1:1, 2:2, 3:3}
217 def keys(self):
218 return self.d.keys()
219 def __getitem__(self, i):
220 return self.d[i]
221 d.clear()
222 d.update(SimpleUserDict())
223 self.assertEqual(d, {1:1, 2:2, 3:3})
224
225 class Exc(Exception): pass
226
227 d.clear()
228 class FailingUserDict:
229 def keys(self):
230 raise Exc
231 self.assertRaises(Exc, d.update, FailingUserDict())
232
233 class FailingUserDict:
234 def keys(self):
235 class BogonIter:
236 def __init__(self):
237 self.i = 1
238 def __iter__(self):
239 return self
240 def __next__(self):
241 if self.i:
242 self.i = 0
243 return 'a'
244 raise Exc
245 return BogonIter()
246 def __getitem__(self, key):
247 return key
248 self.assertRaises(Exc, d.update, FailingUserDict())
249
250 class FailingUserDict:
251 def keys(self):
252 class BogonIter:
253 def __init__(self):
254 self.i = ord('a')
255 def __iter__(self):
256 return self
257 def __next__(self):
258 if self.i <= ord('z'):
259 rtn = chr(self.i)
260 self.i += 1
261 return rtn
262 raise StopIteration
263 return BogonIter()
264 def __getitem__(self, key):
265 raise Exc
266 self.assertRaises(Exc, d.update, FailingUserDict())
267
268 class badseq(object):
269 def __iter__(self):
270 return self
271 def __next__(self):
272 raise Exc()
273
274 self.assertRaises(Exc, {}.update, badseq())
275
276 self.assertRaises(ValueError, {}.update, [(1, 2, 3)])
277
278 def test_update_type_error(self):
279 with self.assertRaises(TypeError) as cm:
280 {}.update([object() for _ in range(3)])
281
282 self.assertEqual(str(cm.exception), "object is not iterable")
283 self.assertEqual(
284 cm.exception.__notes__,
285 ['Cannot convert dictionary update sequence element #0 to a sequence'],
286 )
287
288 def badgen():
289 yield "key"
290 raise TypeError("oops")
291 yield "value"
292
293 with self.assertRaises(TypeError) as cm:
294 dict([badgen() for _ in range(3)])
295
296 self.assertEqual(str(cm.exception), "oops")
297 self.assertEqual(
298 cm.exception.__notes__,
299 ['Cannot convert dictionary update sequence element #0 to a sequence'],
300 )
301
302 def test_update_shared_keys(self):
303 class MyClass: pass
304
305 # Subclass str to enable us to create an object during the
306 # dict.update() call.
307 class MyStr(str):
308 def __hash__(self):
309 return super().__hash__()
310
311 def __eq__(self, other):
312 # Create an object that shares the same PyDictKeysObject as
313 # obj.__dict__.
314 obj2 = MyClass()
315 obj2.a = "a"
316 obj2.b = "b"
317 obj2.c = "c"
318 return super().__eq__(other)
319
320 obj = MyClass()
321 obj.a = "a"
322 obj.b = "b"
323
324 x = {}
325 x[MyStr("a")] = MyStr("a")
326
327 # gh-132617: this previously raised "dict mutated during update" error
328 x.update(obj.__dict__)
329
330 self.assertEqual(x, {
331 MyStr("a"): "a",
332 "b": "b",
333 })
334
335 def test_fromkeys(self):
336 self.assertEqual(dict.fromkeys('abc'), {'a':None, 'b':None, 'c':None})
337 d = {}
338 self.assertIsNot(d.fromkeys('abc'), d)
339 self.assertEqual(d.fromkeys('abc'), {'a':None, 'b':None, 'c':None})
340 self.assertEqual(d.fromkeys((4,5),0), {4:0, 5:0})
341 self.assertEqual(d.fromkeys([]), {})
342 def g():
343 yield 1
344 self.assertEqual(d.fromkeys(g()), {1:None})
345 self.assertRaises(TypeError, {}.fromkeys, 3)
346 class dictlike(dict): pass
347 self.assertEqual(dictlike.fromkeys('a'), {'a':None})
348 self.assertEqual(dictlike().fromkeys('a'), {'a':None})
349 self.assertIsInstance(dictlike.fromkeys('a'), dictlike)
350 self.assertIsInstance(dictlike().fromkeys('a'), dictlike)
351 class mydict(dict):
352 def __new__(cls):
353 return collections.UserDict()
354 ud = mydict.fromkeys('ab')
355 self.assertEqual(ud, {'a':None, 'b':None})
356 self.assertIsInstance(ud, collections.UserDict)
357 self.assertRaises(TypeError, dict.fromkeys)
358
359 class Exc(Exception): pass
360
361 class baddict1(dict):
362 def __init__(self):
363 raise Exc()
364
365 self.assertRaises(Exc, baddict1.fromkeys, [1])
366
367 class BadSeq(object):
368 def __iter__(self):
369 return self
370 def __next__(self):
371 raise Exc()
372
373 self.assertRaises(Exc, dict.fromkeys, BadSeq())
374
375 class baddict2(dict):
376 def __setitem__(self, key, value):
377 raise Exc()
378
379 self.assertRaises(Exc, baddict2.fromkeys, [1])
380
381 # test fast path for dictionary inputs
382 res = dict(zip(range(6), [0]*6))
383 d = dict(zip(range(6), range(6)))
384 self.assertEqual(dict.fromkeys(d, 0), res)
385 # test fast path for set inputs
386 d = set(range(6))
387 self.assertEqual(dict.fromkeys(d, 0), res)
388 # test slow path for other iterable inputs
389 d = list(range(6))
390 self.assertEqual(dict.fromkeys(d, 0), res)
391
392 # test fast path when object's constructor returns large non-empty dict
393 class baddict3(dict):
394 def __new__(cls):
395 return d
396 d = {i : i for i in range(1000)}
397 res = d.copy()
398 res.update(a=None, b=None, c=None)
399 self.assertEqual(baddict3.fromkeys({"a", "b", "c"}), res)
400
401 # test slow path when object is a proper subclass of dict
402 class baddict4(dict):
403 def __init__(self):
404 dict.__init__(self, d)
405 d = {i : i for i in range(1000)}
406 res = d.copy()
407 res.update(a=None, b=None, c=None)
408 self.assertEqual(baddict4.fromkeys({"a", "b", "c"}), res)
409
410 def test_copy(self):
411 d = {1: 1, 2: 2, 3: 3}
412 self.assertIsNot(d.copy(), d)
413 self.assertEqual(d.copy(), d)
414 self.assertEqual(d.copy(), {1: 1, 2: 2, 3: 3})
415
416 copy = d.copy()
417 d[4] = 4
418 self.assertNotEqual(copy, d)
419
420 self.assertEqual({}.copy(), {})
421 self.assertRaises(TypeError, d.copy, None)
422
423 def test_copy_fuzz(self):
424 for dict_size in [10, 100, 1000, 10000, 100000]:
425 dict_size = random.randrange(
426 dict_size // 2, dict_size + dict_size // 2)
427 with self.subTest(dict_size=dict_size):
428 d = {}
429 for i in range(dict_size):
430 d[i] = i
431
432 d2 = d.copy()
433 self.assertIsNot(d2, d)
434 self.assertEqual(d, d2)
435 d2['key'] = 'value'
436 self.assertNotEqual(d, d2)
437 self.assertEqual(len(d2), len(d) + 1)
438
439 def test_copy_maintains_tracking(self):
440 class A:
441 pass
442
443 key = A()
444
445 for d in ({}, {'a': 1}, {key: 'val'}):
446 d2 = d.copy()
447 self.assertEqual(gc.is_tracked(d), gc.is_tracked(d2))
448
449 def test_copy_noncompact(self):
450 # Dicts don't compact themselves on del/pop operations.
451 # Copy will use a slow merging strategy that produces
452 # a compacted copy when roughly 33% of dict is a non-used
453 # keys-space (to optimize memory footprint).
454 # In this test we want to hit the slow/compacting
455 # branch of dict.copy() and make sure it works OK.
456 d = {k: k for k in range(1000)}
457 for k in range(950):
458 del d[k]
459 d2 = d.copy()
460 self.assertEqual(d2, d)
461
462 def test_get(self):
463 d = {}
464 self.assertIs(d.get('c'), None)
465 self.assertEqual(d.get('c', 3), 3)
466 d = {'a': 1, 'b': 2}
467 self.assertIs(d.get('c'), None)
468 self.assertEqual(d.get('c', 3), 3)
469 self.assertEqual(d.get('a'), 1)
470 self.assertEqual(d.get('a', 3), 1)
471 self.assertRaises(TypeError, d.get)
472 self.assertRaises(TypeError, d.get, None, None, None)
473
474 def test_setdefault(self):
475 # dict.setdefault()
476 d = {}
477 self.assertIs(d.setdefault('key0'), None)
478 d.setdefault('key0', [])
479 self.assertIs(d.setdefault('key0'), None)
480 d.setdefault('key', []).append(3)
481 self.assertEqual(d['key'][0], 3)
482 d.setdefault('key', []).append(4)
483 self.assertEqual(len(d['key']), 2)
484 self.assertRaises(TypeError, d.setdefault)
485
486 class Exc(Exception): pass
487
488 class BadHash(object):
489 fail = False
490 def __hash__(self):
491 if self.fail:
492 raise Exc()
493 else:
494 return 42
495
496 x = BadHash()
497 d[x] = 42
498 x.fail = True
499 self.assertRaises(Exc, d.setdefault, x, [])
500
501 def test_setdefault_atomic(self):
502 # Issue #13521: setdefault() calls __hash__ and __eq__ only once.
503 class Hashed(object):
504 def __init__(self):
505 self.hash_count = 0
506 self.eq_count = 0
507 def __hash__(self):
508 self.hash_count += 1
509 return 42
510 def __eq__(self, other):
511 self.eq_count += 1
512 return id(self) == id(other)
513 hashed1 = Hashed()
514 y = {hashed1: 5}
515 hashed2 = Hashed()
516 y.setdefault(hashed2, [])
517 self.assertEqual(hashed1.hash_count, 1)
518 self.assertEqual(hashed2.hash_count, 1)
519 self.assertEqual(hashed1.eq_count + hashed2.eq_count, 1)
520
521 def test_setitem_atomic_at_resize(self):
522 class Hashed(object):
523 def __init__(self):
524 self.hash_count = 0
525 self.eq_count = 0
526 def __hash__(self):
527 self.hash_count += 1
528 return 42
529 def __eq__(self, other):
530 self.eq_count += 1
531 return id(self) == id(other)
532 hashed1 = Hashed()
533 # 5 items
534 y = {hashed1: 5, 0: 0, 1: 1, 2: 2, 3: 3}
535 hashed2 = Hashed()
536 # 6th item forces a resize
537 y[hashed2] = []
538 self.assertEqual(hashed1.hash_count, 1)
539 self.assertEqual(hashed2.hash_count, 1)
540 self.assertEqual(hashed1.eq_count + hashed2.eq_count, 1)
541
542 def test_popitem(self):
543 # dict.popitem()
544 for copymode in -1, +1:
545 # -1: b has same structure as a
546 # +1: b is a.copy()
547 for log2size in range(12):
548 size = 2**log2size
549 a = {}
550 b = {}
551 for i in range(size):
552 a[repr(i)] = i
553 if copymode < 0:
554 b[repr(i)] = i
555 if copymode > 0:
556 b = a.copy()
557 for i in range(size):
558 ka, va = ta = a.popitem()
559 self.assertEqual(va, int(ka))
560 kb, vb = tb = b.popitem()
561 self.assertEqual(vb, int(kb))
562 self.assertFalse(copymode < 0 and ta != tb)
563 self.assertFalse(a)
564 self.assertFalse(b)
565
566 d = {}
567 self.assertRaises(KeyError, d.popitem)
568
569 def test_pop(self):
570 # Tests for pop with specified key
571 d = {}
572 k, v = 'abc', 'def'
573 d[k] = v
574 self.assertRaises(KeyError, d.pop, 'ghi')
575
576 self.assertEqual(d.pop(k), v)
577 self.assertEqual(len(d), 0)
578
579 self.assertRaises(KeyError, d.pop, k)
580
581 self.assertEqual(d.pop(k, v), v)
582 d[k] = v
583 self.assertEqual(d.pop(k, 1), v)
584
585 self.assertRaises(TypeError, d.pop)
586
587 class Exc(Exception): pass
588
589 class BadHash(object):
590 fail = False
591 def __hash__(self):
592 if self.fail:
593 raise Exc()
594 else:
595 return 42
596
597 x = BadHash()
598 d[x] = 42
599 x.fail = True
600 self.assertRaises(Exc, d.pop, x)
601
602 def test_mutating_iteration(self):
603 # changing dict size during iteration
604 d = {}
605 d[1] = 1
606 with self.assertRaises(RuntimeError):
607 for i in d:
608 d[i+1] = 1
609
610 def test_mutating_iteration_delete(self):
611 # change dict content during iteration
612 d = {}
613 d[0] = 0
614 with self.assertRaises(RuntimeError):
615 for i in d:
616 del d[0]
617 d[0] = 0
618
619 def test_mutating_iteration_delete_over_values(self):
620 # change dict content during iteration
621 d = {}
622 d[0] = 0
623 with self.assertRaises(RuntimeError):
624 for i in d.values():
625 del d[0]
626 d[0] = 0
627
628 def test_mutating_iteration_delete_over_items(self):
629 # change dict content during iteration
630 d = {}
631 d[0] = 0
632 with self.assertRaises(RuntimeError):
633 for i in d.items():
634 del d[0]
635 d[0] = 0
636
637 def test_mutating_lookup(self):
638 # changing dict during a lookup (issue #14417)
639 class NastyKey:
640 mutate_dict = None
641
642 def __init__(self, value):
643 self.value = value
644
645 def __hash__(self):
646 # hash collision!
647 return 1
648
649 def __eq__(self, other):
650 if NastyKey.mutate_dict:
651 mydict, key = NastyKey.mutate_dict
652 NastyKey.mutate_dict = None
653 del mydict[key]
654 return self.value == other.value
655
656 key1 = NastyKey(1)
657 key2 = NastyKey(2)
658 d = {key1: 1}
659 NastyKey.mutate_dict = (d, key1)
660 d[key2] = 2
661 self.assertEqual(d, {key2: 2})
662
663 def test_repr(self):
664 d = {}
665 self.assertEqual(repr(d), '{}')
666 d[1] = 2
667 self.assertEqual(repr(d), '{1: 2}')
668 d = {}
669 d[1] = d
670 self.assertEqual(repr(d), '{1: {...}}')
671
672 class Exc(Exception): pass
673
674 class BadRepr(object):
675 def __repr__(self):
676 raise Exc()
677
678 d = {1: BadRepr()}
679 self.assertRaises(Exc, repr, d)
680
681 @support.skip_wasi_stack_overflow()
682 @support.skip_emscripten_stack_overflow()
683 def test_repr_deep(self):
684 d = {}
685 for i in range(support.exceeds_recursion_limit()):
686 d = {1: d}
687 self.assertRaises(RecursionError, repr, d)
688
689 def test_eq(self):
690 self.assertEqual({}, {})
691 self.assertEqual({1: 2}, {1: 2})
692
693 class Exc(Exception): pass
694
695 class BadCmp(object):
696 def __eq__(self, other):
697 raise Exc()
698 def __hash__(self):
699 return 1
700
701 d1 = {BadCmp(): 1}
702 d2 = {1: 1}
703
704 with self.assertRaises(Exc):
705 d1 == d2
706
707 def test_keys_contained(self):
708 self.helper_keys_contained(lambda x: x.keys())
709 self.helper_keys_contained(lambda x: x.items())
710
711 def helper_keys_contained(self, fn):
712 # Test rich comparisons against dict key views, which should behave the
713 # same as sets.
714 empty = fn(dict())
715 empty2 = fn(dict())
716 smaller = fn({1:1, 2:2})
717 larger = fn({1:1, 2:2, 3:3})
718 larger2 = fn({1:1, 2:2, 3:3})
719 larger3 = fn({4:1, 2:2, 3:3})
720
721 self.assertTrue(smaller < larger)
722 self.assertTrue(smaller <= larger)
723 self.assertTrue(larger > smaller)
724 self.assertTrue(larger >= smaller)
725
726 self.assertFalse(smaller >= larger)
727 self.assertFalse(smaller > larger)
728 self.assertFalse(larger <= smaller)
729 self.assertFalse(larger < smaller)
730
731 self.assertFalse(smaller < larger3)
732 self.assertFalse(smaller <= larger3)
733 self.assertFalse(larger3 > smaller)
734 self.assertFalse(larger3 >= smaller)
735
736 # Inequality strictness
737 self.assertTrue(larger2 >= larger)
738 self.assertTrue(larger2 <= larger)
739 self.assertFalse(larger2 > larger)
740 self.assertFalse(larger2 < larger)
741
742 self.assertTrue(larger == larger2)
743 self.assertTrue(smaller != larger)
744
745 # There is an optimization on the zero-element case.
746 self.assertTrue(empty == empty2)
747 self.assertFalse(empty != empty2)
748 self.assertFalse(empty == smaller)
749 self.assertTrue(empty != smaller)
750
751 # With the same size, an elementwise compare happens
752 self.assertTrue(larger != larger3)
753 self.assertFalse(larger == larger3)
754
755 def test_errors_in_view_containment_check(self):
756 class C:
757 def __eq__(self, other):
758 raise RuntimeError
759
760 d1 = {1: C()}
761 d2 = {1: C()}
762 with self.assertRaises(RuntimeError):
763 d1.items() == d2.items()
764 with self.assertRaises(RuntimeError):
765 d1.items() != d2.items()
766 with self.assertRaises(RuntimeError):
767 d1.items() <= d2.items()
768 with self.assertRaises(RuntimeError):
769 d1.items() >= d2.items()
770
771 d3 = {1: C(), 2: C()}
772 with self.assertRaises(RuntimeError):
773 d2.items() < d3.items()
774 with self.assertRaises(RuntimeError):
775 d3.items() > d2.items()
776
777 def test_dictview_set_operations_on_keys(self):
778 k1 = {1:1, 2:2}.keys()
779 k2 = {1:1, 2:2, 3:3}.keys()
780 k3 = {4:4}.keys()
781
782 self.assertEqual(k1 - k2, set())
783 self.assertEqual(k1 - k3, {1,2})
784 self.assertEqual(k2 - k1, {3})
785 self.assertEqual(k3 - k1, {4})
786 self.assertEqual(k1 & k2, {1,2})
787 self.assertEqual(k1 & k3, set())
788 self.assertEqual(k1 | k2, {1,2,3})
789 self.assertEqual(k1 ^ k2, {3})
790 self.assertEqual(k1 ^ k3, {1,2,4})
791
792 def test_dictview_set_operations_on_items(self):
793 k1 = {1:1, 2:2}.items()
794 k2 = {1:1, 2:2, 3:3}.items()
795 k3 = {4:4}.items()
796
797 self.assertEqual(k1 - k2, set())
798 self.assertEqual(k1 - k3, {(1,1), (2,2)})
799 self.assertEqual(k2 - k1, {(3,3)})
800 self.assertEqual(k3 - k1, {(4,4)})
801 self.assertEqual(k1 & k2, {(1,1), (2,2)})
802 self.assertEqual(k1 & k3, set())
803 self.assertEqual(k1 | k2, {(1,1), (2,2), (3,3)})
804 self.assertEqual(k1 ^ k2, {(3,3)})
805 self.assertEqual(k1 ^ k3, {(1,1), (2,2), (4,4)})
806
807 def test_items_symmetric_difference(self):
808 rr = random.randrange
809 for _ in range(100):
810 left = {x:rr(3) for x in range(20) if rr(2)}
811 right = {x:rr(3) for x in range(20) if rr(2)}
812 with self.subTest(left=left, right=right):
813 expected = set(left.items()) ^ set(right.items())
814 actual = left.items() ^ right.items()
815 self.assertEqual(actual, expected)
816
817 def test_dictview_mixed_set_operations(self):
818 # Just a few for .keys()
819 self.assertTrue({1:1}.keys() == {1})
820 self.assertTrue({1} == {1:1}.keys())
821 self.assertEqual({1:1}.keys() | {2}, {1, 2})
822 self.assertEqual({2} | {1:1}.keys(), {1, 2})
823 # And a few for .items()
824 self.assertTrue({1:1}.items() == {(1,1)})
825 self.assertTrue({(1,1)} == {1:1}.items())
826 self.assertEqual({1:1}.items() | {2}, {(1,1), 2})
827 self.assertEqual({2} | {1:1}.items(), {(1,1), 2})
828
829 def test_missing(self):
830 # Make sure dict doesn't have a __missing__ method
831 self.assertNotHasAttr(dict, "__missing__")
832 self.assertNotHasAttr({}, "__missing__")
833 # Test several cases:
834 # (D) subclass defines __missing__ method returning a value
835 # (E) subclass defines __missing__ method raising RuntimeError
836 # (F) subclass sets __missing__ instance variable (no effect)
837 # (G) subclass doesn't define __missing__ at all
838 class D(dict):
839 def __missing__(self, key):
840 return 42
841 d = D({1: 2, 3: 4})
842 self.assertEqual(d[1], 2)
843 self.assertEqual(d[3], 4)
844 self.assertNotIn(2, d)
845 self.assertNotIn(2, d.keys())
846 self.assertEqual(d[2], 42)
847
848 class E(dict):
849 def __missing__(self, key):
850 raise RuntimeError(key)
851 e = E()
852 with self.assertRaises(RuntimeError) as c:
853 e[42]
854 self.assertEqual(c.exception.args, (42,))
855
856 class F(dict):
857 def __init__(self):
858 # An instance variable __missing__ should have no effect
859 self.__missing__ = lambda key: None
860 f = F()
861 with self.assertRaises(KeyError) as c:
862 f[42]
863 self.assertEqual(c.exception.args, (42,))
864
865 class G(dict):
866 pass
867 g = G()
868 with self.assertRaises(KeyError) as c:
869 g[42]
870 self.assertEqual(c.exception.args, (42,))
871
872 def test_tuple_keyerror(self):
873 # SF #1576657
874 d = {}
875 with self.assertRaises(KeyError) as c:
876 d[(1,)]
877 self.assertEqual(c.exception.args, ((1,),))
878
879 def test_bad_key(self):
880 # Dictionary lookups should fail if __eq__() raises an exception.
881 class CustomException(Exception):
882 pass
883
884 class BadDictKey:
885 def __hash__(self):
886 return hash(self.__class__)
887
888 def __eq__(self, other):
889 if isinstance(other, self.__class__):
890 raise CustomException
891 return other
892
893 d = {}
894 x1 = BadDictKey()
895 x2 = BadDictKey()
896 d[x1] = 1
897 for stmt in ['d[x2] = 2',
898 'z = d[x2]',
899 'x2 in d',
900 'd.get(x2)',
901 'd.setdefault(x2, 42)',
902 'd.pop(x2)',
903 'd.update({x2: 2})']:
904 with self.assertRaises(CustomException):
905 exec(stmt, locals())
906
907 def test_resize1(self):
908 # Dict resizing bug, found by Jack Jansen in 2.2 CVS development.
909 # This version got an assert failure in debug build, infinite loop in
910 # release build. Unfortunately, provoking this kind of stuff requires
911 # a mix of inserts and deletes hitting exactly the right hash codes in
912 # exactly the right order, and I can't think of a randomized approach
913 # that would be *likely* to hit a failing case in reasonable time.
914
915 d = {}
916 for i in range(5):
917 d[i] = i
918 for i in range(5):
919 del d[i]
920 for i in range(5, 9): # i==8 was the problem
921 d[i] = i
922
923 def test_resize2(self):
924 # Another dict resizing bug (SF bug #1456209).
925 # This caused Segmentation faults or Illegal instructions.
926
927 class X(object):
928 def __hash__(self):
929 return 5
930 def __eq__(self, other):
931 if resizing:
932 d.clear()
933 return False
934 d = {}
935 resizing = False
936 d[X()] = 1
937 d[X()] = 2
938 d[X()] = 3
939 d[X()] = 4
940 d[X()] = 5
941 # now trigger a resize
942 resizing = True
943 d[9] = 6
944
945 def test_empty_presized_dict_in_freelist(self):
946 # Bug #3537: if an empty but presized dict with a size larger
947 # than 7 was in the freelist, it triggered an assertion failure
948 with self.assertRaises(ZeroDivisionError):
949 d = {'a': 1 // 0, 'b': None, 'c': None, 'd': None, 'e': None,
950 'f': None, 'g': None, 'h': None}
951 d = {}
952
953 def test_container_iterator(self):
954 # Bug #3680: tp_traverse was not implemented for dictiter and
955 # dictview objects.
956 class C(object):
957 pass
958 views = (dict.items, dict.values, dict.keys)
959 for v in views:
960 obj = C()
961 ref = weakref.ref(obj)
962 container = {obj: 1}
963 obj.v = v(container)
964 obj.x = iter(obj.v)
965 del obj, container
966 gc.collect()
967 self.assertIs(ref(), None, "Cycle was not collected")
968
969 def make_shared_key_dict(self, n):
970 class C:
971 pass
972
973 dicts = []
974 for i in range(n):
975 a = C()
976 a.x, a.y, a.z = 1, 2, 3
977 dicts.append(a.__dict__)
978
979 return dicts
980
981 @support.cpython_only
982 def test_splittable_setdefault(self):
983 """split table must keep correct insertion
984 order when attributes are adding using setdefault()"""
985 a, b = self.make_shared_key_dict(2)
986
987 a['a'] = 1
988 size_a = sys.getsizeof(a)
989 a['b'] = 2
990 b.setdefault('b', 2)
991 size_b = sys.getsizeof(b)
992 b['a'] = 1
993
994 self.assertEqual(list(a), ['x', 'y', 'z', 'a', 'b'])
995 self.assertEqual(list(b), ['x', 'y', 'z', 'b', 'a'])
996
997 @support.cpython_only
998 def test_splittable_del(self):
999 """split table must be combined when del d[k]"""
1000 a, b = self.make_shared_key_dict(2)
1001
1002 orig_size = sys.getsizeof(a)
1003
1004 del a['y'] # split table is combined
1005 with self.assertRaises(KeyError):
1006 del a['y']
1007
1008 self.assertEqual(list(a), ['x', 'z'])
1009 self.assertEqual(list(b), ['x', 'y', 'z'])
1010
1011 # Two dicts have different insertion order.
1012 a['y'] = 42
1013 self.assertEqual(list(a), ['x', 'z', 'y'])
1014 self.assertEqual(list(b), ['x', 'y', 'z'])
1015
1016 @support.cpython_only
1017 def test_splittable_pop(self):
1018 a, b = self.make_shared_key_dict(2)
1019
1020 a.pop('y')
1021 with self.assertRaises(KeyError):
1022 a.pop('y')
1023
1024 self.assertEqual(list(a), ['x', 'z'])
1025 self.assertEqual(list(b), ['x', 'y', 'z'])
1026
1027 # Two dicts have different insertion order.
1028 a['y'] = 42
1029 self.assertEqual(list(a), ['x', 'z', 'y'])
1030 self.assertEqual(list(b), ['x', 'y', 'z'])
1031
1032 @support.cpython_only
1033 def test_splittable_pop_pending(self):
1034 """pop a pending key in a split table should not crash"""
1035 a, b = self.make_shared_key_dict(2)
1036
1037 a['a'] = 4
1038 with self.assertRaises(KeyError):
1039 b.pop('a')
1040
1041 @support.cpython_only
1042 def test_splittable_popitem(self):
1043 """split table must be combined when d.popitem()"""
1044 a, b = self.make_shared_key_dict(2)
1045
1046 orig_size = sys.getsizeof(a)
1047
1048 item = a.popitem() # split table is combined
1049 self.assertEqual(item, ('z', 3))
1050 with self.assertRaises(KeyError):
1051 del a['z']
1052
1053 self.assertGreater(sys.getsizeof(a), orig_size)
1054 self.assertEqual(list(a), ['x', 'y'])
1055 self.assertEqual(list(b), ['x', 'y', 'z'])
1056
1057 @support.cpython_only
1058 def test_splittable_update(self):
1059 """dict.update(other) must preserve order in other."""
1060 class C:
1061 def __init__(self, order):
1062 if order:
1063 self.a, self.b, self.c = 1, 2, 3
1064 else:
1065 self.c, self.b, self.a = 1, 2, 3
1066 o = C(True)
1067 o = C(False) # o.__dict__ has reversed order.
1068 self.assertEqual(list(o.__dict__), ["c", "b", "a"])
1069
1070 d = {}
1071 d.update(o.__dict__)
1072 self.assertEqual(list(d), ["c", "b", "a"])
1073
1074 @support.cpython_only
1075 def test_splittable_to_generic_combinedtable(self):
1076 """split table must be correctly resized and converted to generic combined table"""
1077 class C:
1078 pass
1079
1080 a = C()
1081 a.x = 1
1082 d = a.__dict__
1083 d[2] = 2 # split table is resized to a generic combined table
1084
1085 self.assertEqual(list(d), ['x', 2])
1086
1087 def test_iterator_pickling(self):
1088 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1089 data = {1:"a", 2:"b", 3:"c"}
1090 it = iter(data)
1091 d = pickle.dumps(it, proto)
1092 it = pickle.loads(d)
1093 self.assertEqual(list(it), list(data))
1094
1095 it = pickle.loads(d)
1096 try:
1097 drop = next(it)
1098 except StopIteration:
1099 continue
1100 d = pickle.dumps(it, proto)
1101 it = pickle.loads(d)
1102 del data[drop]
1103 self.assertEqual(list(it), list(data))
1104
1105 def test_itemiterator_pickling(self):
1106 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1107 data = {1:"a", 2:"b", 3:"c"}
1108 # dictviews aren't picklable, only their iterators
1109 itorg = iter(data.items())
1110 d = pickle.dumps(itorg, proto)
1111 it = pickle.loads(d)
1112 # note that the type of the unpickled iterator
1113 # is not necessarily the same as the original. It is
1114 # merely an object supporting the iterator protocol, yielding
1115 # the same objects as the original one.
1116 # self.assertEqual(type(itorg), type(it))
1117 self.assertIsInstance(it, collections.abc.Iterator)
1118 self.assertEqual(dict(it), data)
1119
1120 it = pickle.loads(d)
1121 drop = next(it)
1122 d = pickle.dumps(it, proto)
1123 it = pickle.loads(d)
1124 del data[drop[0]]
1125 self.assertEqual(dict(it), data)
1126
1127 def test_valuesiterator_pickling(self):
1128 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1129 data = {1:"a", 2:"b", 3:"c"}
1130 # data.values() isn't picklable, only its iterator
1131 it = iter(data.values())
1132 d = pickle.dumps(it, proto)
1133 it = pickle.loads(d)
1134 self.assertEqual(list(it), list(data.values()))
1135
1136 it = pickle.loads(d)
1137 drop = next(it)
1138 d = pickle.dumps(it, proto)
1139 it = pickle.loads(d)
1140 values = list(it) + [drop]
1141 self.assertEqual(sorted(values), sorted(list(data.values())))
1142
1143 def test_reverseiterator_pickling(self):
1144 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1145 data = {1:"a", 2:"b", 3:"c"}
1146 it = reversed(data)
1147 d = pickle.dumps(it, proto)
1148 it = pickle.loads(d)
1149 self.assertEqual(list(it), list(reversed(data)))
1150
1151 it = pickle.loads(d)
1152 try:
1153 drop = next(it)
1154 except StopIteration:
1155 continue
1156 d = pickle.dumps(it, proto)
1157 it = pickle.loads(d)
1158 del data[drop]
1159 self.assertEqual(list(it), list(reversed(data)))
1160
1161 def test_reverseitemiterator_pickling(self):
1162 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1163 data = {1:"a", 2:"b", 3:"c"}
1164 # dictviews aren't picklable, only their iterators
1165 itorg = reversed(data.items())
1166 d = pickle.dumps(itorg, proto)
1167 it = pickle.loads(d)
1168 # note that the type of the unpickled iterator
1169 # is not necessarily the same as the original. It is
1170 # merely an object supporting the iterator protocol, yielding
1171 # the same objects as the original one.
1172 # self.assertEqual(type(itorg), type(it))
1173 self.assertIsInstance(it, collections.abc.Iterator)
1174 self.assertEqual(dict(it), data)
1175
1176 it = pickle.loads(d)
1177 drop = next(it)
1178 d = pickle.dumps(it, proto)
1179 it = pickle.loads(d)
1180 del data[drop[0]]
1181 self.assertEqual(dict(it), data)
1182
1183 def test_reversevaluesiterator_pickling(self):
1184 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1185 data = {1:"a", 2:"b", 3:"c"}
1186 # data.values() isn't picklable, only its iterator
1187 it = reversed(data.values())
1188 d = pickle.dumps(it, proto)
1189 it = pickle.loads(d)
1190 self.assertEqual(list(it), list(reversed(data.values())))
1191
1192 it = pickle.loads(d)
1193 drop = next(it)
1194 d = pickle.dumps(it, proto)
1195 it = pickle.loads(d)
1196 values = list(it) + [drop]
1197 self.assertEqual(sorted(values), sorted(data.values()))
1198
1199 def test_instance_dict_getattr_str_subclass(self):
1200 class Foo:
1201 def __init__(self, msg):
1202 self.msg = msg
1203 f = Foo('123')
1204 class _str(str):
1205 pass
1206 self.assertEqual(f.msg, getattr(f, _str('msg')))
1207 self.assertEqual(f.msg, f.__dict__[_str('msg')])
1208
1209 def test_object_set_item_single_instance_non_str_key(self):
1210 class Foo: pass
1211 f = Foo()
1212 f.__dict__[1] = 1
1213 f.a = 'a'
1214 self.assertEqual(f.__dict__, {1:1, 'a':'a'})
1215
1216 def check_reentrant_insertion(self, mutate):
1217 # This object will trigger mutation of the dict when replaced
1218 # by another value. Note this relies on refcounting: the test
1219 # won't achieve its purpose on fully-GCed Python implementations.
1220 class Mutating:
1221 def __del__(self):
1222 mutate(d)
1223
1224 d = {k: Mutating() for k in 'abcdefghijklmnopqr'}
1225 for k in list(d):
1226 d[k] = k
1227
1228 def test_reentrant_insertion(self):
1229 # Reentrant insertion shouldn't crash (see issue #22653)
1230 def mutate(d):
1231 d['b'] = 5
1232 self.check_reentrant_insertion(mutate)
1233
1234 def mutate(d):
1235 d.update(self.__dict__)
1236 d.clear()
1237 self.check_reentrant_insertion(mutate)
1238
1239 def mutate(d):
1240 while d:
1241 d.popitem()
1242 self.check_reentrant_insertion(mutate)
1243
1244 def test_merge_and_mutate(self):
1245 class X:
1246 def __hash__(self):
1247 return 0
1248
1249 def __eq__(self, o):
1250 other.clear()
1251 return False
1252
1253 l = [(i,0) for i in range(1, 1337)]
1254 other = dict(l)
1255 other[X()] = 0
1256 d = {X(): 0, 1: 1}
1257 self.assertRaises(RuntimeError, d.update, other)
1258
1259 def test_free_after_iterating(self):
1260 support.check_free_after_iterating(self, iter, dict)
1261 support.check_free_after_iterating(self, lambda d: iter(d.keys()), dict)
1262 support.check_free_after_iterating(self, lambda d: iter(d.values()), dict)
1263 support.check_free_after_iterating(self, lambda d: iter(d.items()), dict)
1264
1265 def test_equal_operator_modifying_operand(self):
1266 # test fix for seg fault reported in bpo-27945 part 3.
1267 class X():
1268 def __del__(self):
1269 dict_b.clear()
1270
1271 def __eq__(self, other):
1272 dict_a.clear()
1273 return True
1274
1275 def __hash__(self):
1276 return 13
1277
1278 dict_a = {X(): 0}
1279 dict_b = {X(): X()}
1280 self.assertTrue(dict_a == dict_b)
1281
1282 # test fix for seg fault reported in bpo-38588 part 1.
1283 class Y:
1284 def __eq__(self, other):
1285 dict_d.clear()
1286 return True
1287
1288 dict_c = {0: Y()}
1289 dict_d = {0: set()}
1290 self.assertTrue(dict_c == dict_d)
1291
1292 def test_fromkeys_operator_modifying_dict_operand(self):
1293 # test fix for seg fault reported in issue 27945 part 4a.
1294 class X(int):
1295 def __hash__(self):
1296 return 13
1297
1298 def __eq__(self, other):
1299 if len(d) > 1:
1300 d.clear()
1301 return False
1302
1303 d = {} # this is required to exist so that d can be constructed!
1304 d = {X(1): 1, X(2): 2}
1305 try:
1306 dict.fromkeys(d) # shouldn't crash
1307 except RuntimeError: # implementation defined
1308 pass
1309
1310 def test_fromkeys_operator_modifying_set_operand(self):
1311 # test fix for seg fault reported in issue 27945 part 4b.
1312 class X(int):
1313 def __hash__(self):
1314 return 13
1315
1316 def __eq__(self, other):
1317 if len(d) > 1:
1318 d.clear()
1319 return False
1320
1321 d = {} # this is required to exist so that d can be constructed!
1322 d = {X(1), X(2)}
1323 try:
1324 dict.fromkeys(d) # shouldn't crash
1325 except RuntimeError: # implementation defined
1326 pass
1327
1328 def test_dictitems_contains_use_after_free(self):
1329 class X:
1330 def __eq__(self, other):
1331 d.clear()
1332 return NotImplemented
1333
1334 d = {0: set()}
1335 (0, X()) in d.items()
1336
1337 def test_dict_contain_use_after_free(self):
1338 # bpo-40489
1339 class S(str):
1340 def __eq__(self, other):
1341 d.clear()
1342 return NotImplemented
1343
1344 def __hash__(self):
1345 return hash('test')
1346
1347 d = {S(): 'value'}
1348 self.assertFalse('test' in d)
1349
1350 def test_init_use_after_free(self):
1351 class X:
1352 def __hash__(self):
1353 pair[:] = []
1354 return 13
1355
1356 pair = [X(), 123]
1357 dict([pair])
1358
1359 def test_oob_indexing_dictiter_iternextitem(self):
1360 class X(int):
1361 def __del__(self):
1362 d.clear()
1363
1364 d = {i: X(i) for i in range(8)}
1365
1366 def iter_and_mutate():
1367 for result in d.items():
1368 if result[0] == 2:
1369 d[2] = None # free d[2] --> X(2).__del__ was called
1370
1371 self.assertRaises(RuntimeError, iter_and_mutate)
1372
1373 def test_reversed(self):
1374 d = {"a": 1, "b": 2, "foo": 0, "c": 3, "d": 4}
1375 del d["foo"]
1376 r = reversed(d)
1377 self.assertEqual(list(r), list('dcba'))
1378 self.assertRaises(StopIteration, next, r)
1379
1380 def test_reverse_iterator_for_empty_dict(self):
1381 # bpo-38525: reversed iterator should work properly
1382
1383 # empty dict is directly used for reference count test
1384 self.assertEqual(list(reversed({})), [])
1385 self.assertEqual(list(reversed({}.items())), [])
1386 self.assertEqual(list(reversed({}.values())), [])
1387 self.assertEqual(list(reversed({}.keys())), [])
1388
1389 # dict() and {} don't trigger the same code path
1390 self.assertEqual(list(reversed(dict())), [])
1391 self.assertEqual(list(reversed(dict().items())), [])
1392 self.assertEqual(list(reversed(dict().values())), [])
1393 self.assertEqual(list(reversed(dict().keys())), [])
1394
1395 def test_reverse_iterator_for_shared_shared_dicts(self):
1396 class A:
1397 def __init__(self, x, y):
1398 if x: self.x = x
1399 if y: self.y = y
1400
1401 self.assertEqual(list(reversed(A(1, 2).__dict__)), ['y', 'x'])
1402 self.assertEqual(list(reversed(A(1, 0).__dict__)), ['x'])
1403 self.assertEqual(list(reversed(A(0, 1).__dict__)), ['y'])
1404
1405 def test_dict_copy_order(self):
1406 # bpo-34320
1407 od = collections.OrderedDict([('a', 1), ('b', 2)])
1408 od.move_to_end('a')
1409 expected = list(od.items())
1410
1411 copy = dict(od)
1412 self.assertEqual(list(copy.items()), expected)
1413
1414 # dict subclass doesn't override __iter__
1415 class CustomDict(dict):
1416 pass
1417
1418 pairs = [('a', 1), ('b', 2), ('c', 3)]
1419
1420 d = CustomDict(pairs)
1421 self.assertEqual(pairs, list(dict(d).items()))
1422
1423 class CustomReversedDict(dict):
1424 def keys(self):
1425 return reversed(list(dict.keys(self)))
1426
1427 __iter__ = keys
1428
1429 def items(self):
1430 return reversed(dict.items(self))
1431
1432 d = CustomReversedDict(pairs)
1433 self.assertEqual(pairs[::-1], list(dict(d).items()))
1434
1435 @support.cpython_only
1436 def test_dict_items_result_gc(self):
1437 # bpo-42536: dict.items's tuple-reuse speed trick breaks the GC's
1438 # assumptions about what can be untracked. Make sure we re-track result
1439 # tuples whenever we reuse them.
1440 it = iter({None: []}.items())
1441 gc.collect()
1442 # That GC collection probably untracked the recycled internal result
1443 # tuple, which is initialized to (None, None). Make sure it's re-tracked
1444 # when it's mutated and returned from __next__:
1445 self.assertTrue(gc.is_tracked(next(it)))
1446
1447 @support.cpython_only
1448 def test_dict_items_result_gc_reversed(self):
1449 # Same as test_dict_items_result_gc above, but reversed.
1450 it = reversed({None: []}.items())
1451 gc.collect()
1452 self.assertTrue(gc.is_tracked(next(it)))
1453
1454 def test_store_evilattr(self):
1455 class EvilAttr:
1456 def __init__(self, d):
1457 self.d = d
1458
1459 def __del__(self):
1460 if 'attr' in self.d:
1461 del self.d['attr']
1462 gc.collect()
1463
1464 class Obj:
1465 pass
1466
1467 obj = Obj()
1468 obj.__dict__ = {}
1469 for _ in range(10):
1470 obj.attr = EvilAttr(obj.__dict__)
1471
1472 def test_str_nonstr(self):
1473 # cpython uses a different lookup function if the dict only contains
1474 # `str` keys. Make sure the unoptimized path is used when a non-`str`
1475 # key appears.
1476
1477 class StrSub(str):
1478 pass
1479
1480 eq_count = 0
1481 # This class compares equal to the string 'key3'
1482 class Key3:
1483 def __hash__(self):
1484 return hash('key3')
1485
1486 def __eq__(self, other):
1487 nonlocal eq_count
1488 if isinstance(other, Key3) or isinstance(other, str) and other == 'key3':
1489 eq_count += 1
1490 return True
1491 return False
1492
1493 key3_1 = StrSub('key3')
1494 key3_2 = Key3()
1495 key3_3 = Key3()
1496
1497 dicts = []
1498
1499 # Create dicts of the form `{'key1': 42, 'key2': 43, key3: 44}` in a
1500 # bunch of different ways. In all cases, `key3` is not of type `str`.
1501 # `key3_1` is a `str` subclass and `key3_2` is a completely unrelated
1502 # type.
1503 for key3 in (key3_1, key3_2):
1504 # A literal
1505 dicts.append({'key1': 42, 'key2': 43, key3: 44})
1506
1507 # key3 inserted via `dict.__setitem__`
1508 d = {'key1': 42, 'key2': 43}
1509 d[key3] = 44
1510 dicts.append(d)
1511
1512 # key3 inserted via `dict.setdefault`
1513 d = {'key1': 42, 'key2': 43}
1514 self.assertEqual(d.setdefault(key3, 44), 44)
1515 dicts.append(d)
1516
1517 # key3 inserted via `dict.update`
1518 d = {'key1': 42, 'key2': 43}
1519 d.update({key3: 44})
1520 dicts.append(d)
1521
1522 # key3 inserted via `dict.__ior__`
1523 d = {'key1': 42, 'key2': 43}
1524 d |= {key3: 44}
1525 dicts.append(d)
1526
1527 # `dict(iterable)`
1528 def make_pairs():
1529 yield ('key1', 42)
1530 yield ('key2', 43)
1531 yield (key3, 44)
1532 d = dict(make_pairs())
1533 dicts.append(d)
1534
1535 # `dict.copy`
1536 d = d.copy()
1537 dicts.append(d)
1538
1539 # dict comprehension
1540 d = {key: 42 + i for i,key in enumerate(['key1', 'key2', key3])}
1541 dicts.append(d)
1542
1543 for d in dicts:
1544 with self.subTest(d=d):
1545 self.assertEqual(d.get('key1'), 42)
1546
1547 # Try to make an object that is of type `str` and is equal to
1548 # `'key1'`, but (at least on cpython) is a different object.
1549 noninterned_key1 = 'ke'
1550 noninterned_key1 += 'y1'
1551 if support.check_impl_detail(cpython=True):
1552 # suppress a SyntaxWarning
1553 interned_key1 = 'key1'
1554 self.assertFalse(noninterned_key1 is interned_key1)
1555 self.assertEqual(d.get(noninterned_key1), 42)
1556
1557 self.assertEqual(d.get('key3'), 44)
1558 self.assertEqual(d.get(key3_1), 44)
1559 self.assertEqual(d.get(key3_2), 44)
1560
1561 # `key3_3` itself is definitely not a dict key, so make sure
1562 # that `__eq__` gets called.
1563 #
1564 # Note that this might not hold for `key3_1` and `key3_2`
1565 # because they might be the same object as one of the dict keys,
1566 # in which case implementations are allowed to skip the call to
1567 # `__eq__`.
1568 eq_count = 0
1569 self.assertEqual(d.get(key3_3), 44)
1570 self.assertGreaterEqual(eq_count, 1)
1571
1572 def test_overwrite_managed_dict(self):
1573 # GH-130327: Overwriting an object's managed dictionary with another object's
1574 # skipped traversal in favor of inline values, causing the GC to believe that
1575 # the __dict__ wasn't reachable.
1576 import gc
1577
1578 class Shenanigans:
1579 pass
1580
1581 to_be_deleted = Shenanigans()
1582 to_be_deleted.attr = "whatever"
1583 holds_reference = Shenanigans()
1584 holds_reference.__dict__ = to_be_deleted.__dict__
1585 holds_reference.ref = {"circular": to_be_deleted, "data": 42}
1586
1587 del to_be_deleted
1588 gc.collect()
1589 self.assertEqual(holds_reference.ref['data'], 42)
1590 self.assertEqual(holds_reference.attr, "whatever")
1591
1592 def test_unhashable_key(self):
1593 d = {'a': 1}
1594 key = [1, 2, 3]
1595
1596 def check_unhashable_key():
1597 msg = "cannot use 'list' as a dict key (unhashable type: 'list')"
1598 return self.assertRaisesRegex(TypeError, re.escape(msg))
1599
1600 with check_unhashable_key():
1601 key in d
1602 with check_unhashable_key():
1603 d[key]
1604 with check_unhashable_key():
1605 d[key] = 2
1606 with check_unhashable_key():
1607 d.setdefault(key, 2)
1608 with check_unhashable_key():
1609 d.pop(key)
1610 with check_unhashable_key():
1611 d.get(key)
1612
1613 # Only TypeError exception is overriden,
1614 # other exceptions are left unchanged.
1615 class HashError:
1616 def __hash__(self):
1617 raise KeyError('error')
1618
1619 key2 = HashError()
1620 with self.assertRaises(KeyError):
1621 key2 in d
1622 with self.assertRaises(KeyError):
1623 d[key2]
1624 with self.assertRaises(KeyError):
1625 d[key2] = 2
1626 with self.assertRaises(KeyError):
1627 d.setdefault(key2, 2)
1628 with self.assertRaises(KeyError):
1629 d.pop(key2)
1630 with self.assertRaises(KeyError):
1631 d.get(key2)
1632
1633 def test_clear_at_lookup(self):
1634 # gh-140551 dict crash if clear is called at lookup stage
1635 class X:
1636 def __hash__(self):
1637 return 1
1638 def __eq__(self, other):
1639 nonlocal d
1640 d.clear()
1641
1642 d = {}
1643 for _ in range(10):
1644 d[X()] = None
1645
1646 self.assertEqual(len(d), 1)
1647
1648 d = {}
1649 for _ in range(10):
1650 d.setdefault(X(), None)
1651
1652 self.assertEqual(len(d), 1)
1653
1654 def test_split_table_update_with_str_subclass(self):
1655 # gh-142218: inserting into a split table dictionary with a non str
1656 # key that matches an existing key.
1657 class MyStr(str): pass
1658 class MyClass: pass
1659 obj = MyClass()
1660 obj.attr = 1
1661 obj.__dict__[MyStr('attr')] = 2
1662 self.assertEqual(obj.attr, 2)
1663
1664 def test_split_table_insert_with_str_subclass(self):
1665 # gh-143189: inserting into split table dictionary with a non str
1666 # key that matches an existing key in the shared table but not in
1667 # the dict yet.
1668
1669 class MyStr(str): pass
1670 class MyClass: pass
1671
1672 obj = MyClass()
1673 obj.attr1 = 1
1674
1675 obj2 = MyClass()
1676 d = obj2.__dict__
1677 d[MyStr("attr1")] = 2
1678 self.assertIsInstance(list(d)[0], MyStr)
1679
1680 def test_hash_collision_remove_add(self):
1681 self.maxDiff = None
1682 # There should be enough space, so all elements with unique hash
1683 # will be placed in corresponding cells without collision.
1684 n = 64
1685 items = [(CustomHash(h), h) for h in range(n)]
1686 # Keys with hash collision.
1687 a = CustomHash(n)
1688 b = CustomHash(n)
1689 items += [(a, 'a'), (b, 'b')]
1690 d = dict(items)
1691 self.assertEqual(len(d), len(items), d)
1692 del d[a]
1693 # "a" has been replaced with a dummy.
1694 del items[n]
1695 self.assertEqual(len(d), len(items), d)
1696 self.assertEqual(d, dict(items))
1697 d[b] = 'c'
1698 # "b" should not replace the dummy.
1699 items[n] = (b, 'c')
1700 self.assertEqual(len(d), len(items), d)
1701 self.assertEqual(d, dict(items))
1702
1703 def test_clear_reentrant_embedded(self):
1704 # gh-130555: dict.clear() must be safe when values are embedded
1705 # in an object and a destructor mutates the dict.
1706 class MyObj: pass
1707 class ClearOnDelete:
1708 def __del__(self):
1709 nonlocal x
1710 del x
1711
1712 x = MyObj()
1713 x.a = ClearOnDelete()
1714
1715 d = x.__dict__
1716 d.clear()
1717
1718 def test_clear_reentrant_cycle(self):
1719 # gh-130555: dict.clear() must be safe for embedded dicts when the
1720 # object is part of a reference cycle and the last reference to the
1721 # dict is via the cycle.
1722 class MyObj: pass
1723 obj = MyObj()
1724 obj.f = obj
1725 obj.attr = "attr"
1726
1727 d = obj.__dict__
1728 del obj
1729
1730 d.clear()
1731
1732 def test_clear_reentrant_force_combined(self):
1733 # gh-130555: dict.clear() must be safe when a destructor forces the
1734 # dict from embedded/split to combined (setting ma_values to NULL).
1735 class MyObj: pass
1736 class ForceConvert:
1737 def __del__(self):
1738 d[1] = "trigger"
1739
1740 x = MyObj()
1741 x.a = ForceConvert()
1742 x.b = "other"
1743
1744 d = x.__dict__
1745 d.clear()
1746
1747 def test_clear_reentrant_delete(self):
1748 # gh-130555: dict.clear() must be safe when a destructor deletes
1749 # a key from the same embedded dict.
1750 class MyObj: pass
1751 class DelKey:
1752 def __del__(self):
1753 try:
1754 del d['b']
1755 except KeyError:
1756 pass
1757
1758 x = MyObj()
1759 x.a = DelKey()
1760 x.b = "value_b"
1761 x.c = "value_c"
1762
1763 d = x.__dict__
1764 d.clear()
1765
1766
1767 class CAPITest(unittest.TestCase):
1768
1769 # Test _PyDict_GetItem_KnownHash()
1770 @support.cpython_only
1771 def test_getitem_knownhash(self):
1772 _testinternalcapi = import_helper.import_module('_testinternalcapi')
1773 dict_getitem_knownhash = _testinternalcapi.dict_getitem_knownhash
1774
1775 d = {'x': 1, 'y': 2, 'z': 3}
1776 self.assertEqual(dict_getitem_knownhash(d, 'x', hash('x')), 1)
1777 self.assertEqual(dict_getitem_knownhash(d, 'y', hash('y')), 2)
1778 self.assertEqual(dict_getitem_knownhash(d, 'z', hash('z')), 3)
1779
1780 # not a dict
1781 self.assertRaises(SystemError, dict_getitem_knownhash, [], 1, hash(1))
1782 # key does not exist
1783 self.assertRaises(KeyError, dict_getitem_knownhash, {}, 1, hash(1))
1784
1785 class Exc(Exception): pass
1786 class BadEq:
1787 def __eq__(self, other):
1788 raise Exc
1789 def __hash__(self):
1790 return 7
1791
1792 k1, k2 = BadEq(), BadEq()
1793 d = {k1: 1}
1794 self.assertEqual(dict_getitem_knownhash(d, k1, hash(k1)), 1)
1795 self.assertRaises(Exc, dict_getitem_knownhash, d, k2, hash(k2))
1796
1797
1798 from test import mapping_tests
1799
1800 class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
1801 type2test = dict
1802
1803 class Dict(dict):
1804 pass
1805
1806 class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
1807 type2test = Dict
1808
1809
1810 if __name__ == "__main__":
1811 unittest.main()