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