1 import unittest 2 from test import test_support 3 4 import UserDict, random, string 5 import gc, weakref 6 7 8 class DictTest(unittest.TestCase): 9 def test_constructor(self): 10 # calling built-in types without argument must return empty 11 self.assertEqual(dict(), {}) 12 self.assertIsNot(dict(), {}) 13 14 def test_literal_constructor(self): 15 # check literal constructor for different sized dicts 16 # (to exercise the BUILD_MAP oparg). 17 for n in (0, 1, 6, 256, 400): 18 items = [(''.join(random.sample(string.letters, 8)), i) 19 for i in range(n)] 20 random.shuffle(items) 21 formatted_items = ('{!r}: {:d}'.format(k, v) for k, v in items) 22 dictliteral = '{' + ', '.join(formatted_items) + '}' 23 self.assertEqual(eval(dictliteral), dict(items)) 24 25 def test_bool(self): 26 self.assertIs(not {}, True) 27 self.assertTrue({1: 2}) 28 self.assertIs(bool({}), False) 29 self.assertIs(bool({1: 2}), True) 30 31 def test_keys(self): 32 d = {} 33 self.assertEqual(d.keys(), []) 34 d = {'a': 1, 'b': 2} 35 k = d.keys() 36 self.assertEqual(set(k), {'a', 'b'}) 37 self.assertIn('a', k) 38 self.assertIn('b', k) 39 self.assertTrue(d.has_key('a')) 40 self.assertTrue(d.has_key('b')) 41 self.assertRaises(TypeError, d.keys, None) 42 43 def test_values(self): 44 d = {} 45 self.assertEqual(d.values(), []) 46 d = {1:2} 47 self.assertEqual(d.values(), [2]) 48 49 self.assertRaises(TypeError, d.values, None) 50 51 def test_items(self): 52 d = {} 53 self.assertEqual(d.items(), []) 54 55 d = {1:2} 56 self.assertEqual(d.items(), [(1, 2)]) 57 58 self.assertRaises(TypeError, d.items, None) 59 60 def test_has_key(self): 61 d = {} 62 self.assertFalse(d.has_key('a')) 63 d = {'a': 1, 'b': 2} 64 k = d.keys() 65 k.sort() 66 self.assertEqual(k, ['a', 'b']) 67 68 self.assertRaises(TypeError, d.has_key) 69 70 def test_contains(self): 71 d = {} 72 self.assertNotIn('a', d) 73 self.assertFalse('a' in d) 74 self.assertTrue('a' not in d) 75 d = {'a': 1, 'b': 2} 76 self.assertIn('a', d) 77 self.assertIn('b', d) 78 self.assertNotIn('c', d) 79 80 self.assertRaises(TypeError, d.__contains__) 81 82 def test_len(self): 83 d = {} 84 self.assertEqual(len(d), 0) 85 d = {'a': 1, 'b': 2} 86 self.assertEqual(len(d), 2) 87 88 def test_getitem(self): 89 d = {'a': 1, 'b': 2} 90 self.assertEqual(d['a'], 1) 91 self.assertEqual(d['b'], 2) 92 d['c'] = 3 93 d['a'] = 4 94 self.assertEqual(d['c'], 3) 95 self.assertEqual(d['a'], 4) 96 del d['b'] 97 self.assertEqual(d, {'a': 4, 'c': 3}) 98 99 self.assertRaises(TypeError, d.__getitem__) 100 101 class BadEq(object): 102 def __eq__(self, other): 103 raise Exc() 104 def __hash__(self): 105 return 24 106 107 d = {} 108 d[BadEq()] = 42 109 self.assertRaises(KeyError, d.__getitem__, 23) 110 111 class Exc(Exception): pass 112 113 class BadHash(object): 114 fail = False 115 def __hash__(self): 116 if self.fail: 117 raise Exc() 118 else: 119 return 42 120 121 x = BadHash() 122 d[x] = 42 123 x.fail = True 124 self.assertRaises(Exc, d.__getitem__, x) 125 126 def test_clear(self): 127 d = {1:1, 2:2, 3:3} 128 d.clear() 129 self.assertEqual(d, {}) 130 131 self.assertRaises(TypeError, d.clear, None) 132 133 def test_update(self): 134 d = {} 135 d.update({1:100}) 136 d.update({2:20}) 137 d.update({1:1, 2:2, 3:3}) 138 self.assertEqual(d, {1:1, 2:2, 3:3}) 139 140 d.update() 141 self.assertEqual(d, {1:1, 2:2, 3:3}) 142 143 self.assertRaises((TypeError, AttributeError), d.update, None) 144 145 class SimpleUserDict: 146 def __init__(self): 147 self.d = {1:1, 2:2, 3:3} 148 def keys(self): 149 return self.d.keys() 150 def __getitem__(self, i): 151 return self.d[i] 152 d.clear() 153 d.update(SimpleUserDict()) 154 self.assertEqual(d, {1:1, 2:2, 3:3}) 155 156 class Exc(Exception): pass 157 158 d.clear() 159 class FailingUserDict: 160 def keys(self): 161 raise Exc 162 self.assertRaises(Exc, d.update, FailingUserDict()) 163 164 class FailingUserDict: 165 def keys(self): 166 class BogonIter: 167 def __init__(self): 168 self.i = 1 169 def __iter__(self): 170 return self 171 def next(self): 172 if self.i: 173 self.i = 0 174 return 'a' 175 raise Exc 176 return BogonIter() 177 def __getitem__(self, key): 178 return key 179 self.assertRaises(Exc, d.update, FailingUserDict()) 180 181 class FailingUserDict: 182 def keys(self): 183 class BogonIter: 184 def __init__(self): 185 self.i = ord('a') 186 def __iter__(self): 187 return self 188 def next(self): 189 if self.i <= ord('z'): 190 rtn = chr(self.i) 191 self.i += 1 192 return rtn 193 raise StopIteration 194 return BogonIter() 195 def __getitem__(self, key): 196 raise Exc 197 self.assertRaises(Exc, d.update, FailingUserDict()) 198 199 class badseq(object): 200 def __iter__(self): 201 return self 202 def next(self): 203 raise Exc() 204 205 self.assertRaises(Exc, {}.update, badseq()) 206 207 self.assertRaises(ValueError, {}.update, [(1, 2, 3)]) 208 209 def test_fromkeys(self): 210 self.assertEqual(dict.fromkeys('abc'), {'a':None, 'b':None, 'c':None}) 211 d = {} 212 self.assertIsNot(d.fromkeys('abc'), d) 213 self.assertEqual(d.fromkeys('abc'), {'a':None, 'b':None, 'c':None}) 214 self.assertEqual(d.fromkeys((4,5),0), {4:0, 5:0}) 215 self.assertEqual(d.fromkeys([]), {}) 216 def g(): 217 yield 1 218 self.assertEqual(d.fromkeys(g()), {1:None}) 219 self.assertRaises(TypeError, {}.fromkeys, 3) 220 class dictlike(dict): pass 221 self.assertEqual(dictlike.fromkeys('a'), {'a':None}) 222 self.assertEqual(dictlike().fromkeys('a'), {'a':None}) 223 self.assertIsInstance(dictlike.fromkeys('a'), dictlike) 224 self.assertIsInstance(dictlike().fromkeys('a'), dictlike) 225 class mydict(dict): 226 def __new__(cls): 227 return UserDict.UserDict() 228 ud = mydict.fromkeys('ab') 229 self.assertEqual(ud, {'a':None, 'b':None}) 230 self.assertIsInstance(ud, UserDict.UserDict) 231 self.assertRaises(TypeError, dict.fromkeys) 232 233 class Exc(Exception): pass 234 235 class baddict1(dict): 236 def __init__(self): 237 raise Exc() 238 239 self.assertRaises(Exc, baddict1.fromkeys, [1]) 240 241 class BadSeq(object): 242 def __iter__(self): 243 return self 244 def next(self): 245 raise Exc() 246 247 self.assertRaises(Exc, dict.fromkeys, BadSeq()) 248 249 class baddict2(dict): 250 def __setitem__(self, key, value): 251 raise Exc() 252 253 self.assertRaises(Exc, baddict2.fromkeys, [1]) 254 255 # test fast path for dictionary inputs 256 d = dict(zip(range(6), range(6))) 257 self.assertEqual(dict.fromkeys(d, 0), dict(zip(range(6), [0]*6))) 258 259 class baddict3(dict): 260 def __new__(cls): 261 return d 262 d = {i : i for i in range(10)} 263 res = d.copy() 264 res.update(a=None, b=None, c=None) 265 self.assertEqual(baddict3.fromkeys({"a", "b", "c"}), res) 266 267 def test_copy(self): 268 d = {1:1, 2:2, 3:3} 269 self.assertEqual(d.copy(), {1:1, 2:2, 3:3}) 270 self.assertEqual({}.copy(), {}) 271 self.assertRaises(TypeError, d.copy, None) 272 273 def test_get(self): 274 d = {} 275 self.assertIs(d.get('c'), None) 276 self.assertEqual(d.get('c', 3), 3) 277 d = {'a': 1, 'b': 2} 278 self.assertIs(d.get('c'), None) 279 self.assertEqual(d.get('c', 3), 3) 280 self.assertEqual(d.get('a'), 1) 281 self.assertEqual(d.get('a', 3), 1) 282 self.assertRaises(TypeError, d.get) 283 self.assertRaises(TypeError, d.get, None, None, None) 284 285 def test_setdefault(self): 286 # dict.setdefault() 287 d = {} 288 self.assertIs(d.setdefault('key0'), None) 289 d.setdefault('key0', []) 290 self.assertIs(d.setdefault('key0'), None) 291 d.setdefault('key', []).append(3) 292 self.assertEqual(d['key'][0], 3) 293 d.setdefault('key', []).append(4) 294 self.assertEqual(len(d['key']), 2) 295 self.assertRaises(TypeError, d.setdefault) 296 297 class Exc(Exception): pass 298 299 class BadHash(object): 300 fail = False 301 def __hash__(self): 302 if self.fail: 303 raise Exc() 304 else: 305 return 42 306 307 x = BadHash() 308 d[x] = 42 309 x.fail = True 310 self.assertRaises(Exc, d.setdefault, x, []) 311 312 def test_setdefault_atomic(self): 313 # Issue #13521: setdefault() calls __hash__ and __eq__ only once. 314 class Hashed(object): 315 def __init__(self): 316 self.hash_count = 0 317 self.eq_count = 0 318 def __hash__(self): 319 self.hash_count += 1 320 return 42 321 def __eq__(self, other): 322 self.eq_count += 1 323 return id(self) == id(other) 324 hashed1 = Hashed() 325 y = {hashed1: 5} 326 hashed2 = Hashed() 327 y.setdefault(hashed2, []) 328 self.assertEqual(hashed1.hash_count, 1) 329 self.assertEqual(hashed2.hash_count, 1) 330 self.assertEqual(hashed1.eq_count + hashed2.eq_count, 1) 331 332 def test_popitem(self): 333 # dict.popitem() 334 for copymode in -1, +1: 335 # -1: b has same structure as a 336 # +1: b is a.copy() 337 for log2size in range(12): 338 size = 2**log2size 339 a = {} 340 b = {} 341 for i in range(size): 342 a[repr(i)] = i 343 if copymode < 0: 344 b[repr(i)] = i 345 if copymode > 0: 346 b = a.copy() 347 for i in range(size): 348 ka, va = ta = a.popitem() 349 self.assertEqual(va, int(ka)) 350 kb, vb = tb = b.popitem() 351 self.assertEqual(vb, int(kb)) 352 self.assertFalse(copymode < 0 and ta != tb) 353 self.assertFalse(a) 354 self.assertFalse(b) 355 356 d = {} 357 self.assertRaises(KeyError, d.popitem) 358 359 def test_pop(self): 360 # Tests for pop with specified key 361 d = {} 362 k, v = 'abc', 'def' 363 d[k] = v 364 self.assertRaises(KeyError, d.pop, 'ghi') 365 366 self.assertEqual(d.pop(k), v) 367 self.assertEqual(len(d), 0) 368 369 self.assertRaises(KeyError, d.pop, k) 370 371 # verify longs/ints get same value when key > 32 bits 372 # (for 64-bit archs). See SF bug #689659. 373 x = 4503599627370496L 374 y = 4503599627370496 375 h = {x: 'anything', y: 'something else'} 376 self.assertEqual(h[x], h[y]) 377 378 self.assertEqual(d.pop(k, v), v) 379 d[k] = v 380 self.assertEqual(d.pop(k, 1), v) 381 382 self.assertRaises(TypeError, d.pop) 383 384 class Exc(Exception): pass 385 386 class BadHash(object): 387 fail = False 388 def __hash__(self): 389 if self.fail: 390 raise Exc() 391 else: 392 return 42 393 394 x = BadHash() 395 d[x] = 42 396 x.fail = True 397 self.assertRaises(Exc, d.pop, x) 398 399 def test_mutatingiteration(self): 400 # changing dict size during iteration 401 d = {} 402 d[1] = 1 403 with self.assertRaises(RuntimeError): 404 for i in d: 405 d[i+1] = 1 406 407 def test_repr(self): 408 d = {} 409 self.assertEqual(repr(d), '{}') 410 d[1] = 2 411 self.assertEqual(repr(d), '{1: 2}') 412 d = {} 413 d[1] = d 414 self.assertEqual(repr(d), '{1: {...}}') 415 416 class Exc(Exception): pass 417 418 class BadRepr(object): 419 def __repr__(self): 420 raise Exc() 421 422 d = {1: BadRepr()} 423 self.assertRaises(Exc, repr, d) 424 425 def test_le(self): 426 self.assertFalse({} < {}) 427 self.assertFalse({1: 2} < {1L: 2L}) 428 429 class Exc(Exception): pass 430 431 class BadCmp(object): 432 def __eq__(self, other): 433 raise Exc() 434 def __hash__(self): 435 return 42 436 437 d1 = {BadCmp(): 1} 438 d2 = {1: 1} 439 440 with self.assertRaises(Exc): 441 d1 < d2 442 443 def test_missing(self): 444 # Make sure dict doesn't have a __missing__ method 445 self.assertFalse(hasattr(dict, "__missing__")) 446 self.assertFalse(hasattr({}, "__missing__")) 447 # Test several cases: 448 # (D) subclass defines __missing__ method returning a value 449 # (E) subclass defines __missing__ method raising RuntimeError 450 # (F) subclass sets __missing__ instance variable (no effect) 451 # (G) subclass doesn't define __missing__ at all 452 class D(dict): 453 def __missing__(self, key): 454 return 42 455 d = D({1: 2, 3: 4}) 456 self.assertEqual(d[1], 2) 457 self.assertEqual(d[3], 4) 458 self.assertNotIn(2, d) 459 self.assertNotIn(2, d.keys()) 460 self.assertEqual(d[2], 42) 461 462 class E(dict): 463 def __missing__(self, key): 464 raise RuntimeError(key) 465 e = E() 466 with self.assertRaises(RuntimeError) as c: 467 e[42] 468 self.assertEqual(c.exception.args, (42,)) 469 470 class F(dict): 471 def __init__(self): 472 # An instance variable __missing__ should have no effect 473 self.__missing__ = lambda key: None 474 f = F() 475 with self.assertRaises(KeyError) as c: 476 f[42] 477 self.assertEqual(c.exception.args, (42,)) 478 479 class G(dict): 480 pass 481 g = G() 482 with self.assertRaises(KeyError) as c: 483 g[42] 484 self.assertEqual(c.exception.args, (42,)) 485 486 def test_tuple_keyerror(self): 487 # SF #1576657 488 d = {} 489 with self.assertRaises(KeyError) as c: 490 d[(1,)] 491 self.assertEqual(c.exception.args, ((1,),)) 492 493 def test_bad_key(self): 494 # Dictionary lookups should fail if __cmp__() raises an exception. 495 class CustomException(Exception): 496 pass 497 498 class BadDictKey: 499 def __hash__(self): 500 return hash(self.__class__) 501 502 def __cmp__(self, other): 503 if isinstance(other, self.__class__): 504 raise CustomException 505 return other 506 507 d = {} 508 x1 = BadDictKey() 509 x2 = BadDictKey() 510 d[x1] = 1 511 for stmt in ['d[x2] = 2', 512 'z = d[x2]', 513 'x2 in d', 514 'd.has_key(x2)', 515 'd.get(x2)', 516 'd.setdefault(x2, 42)', 517 'd.pop(x2)', 518 'd.update({x2: 2})']: 519 with self.assertRaises(CustomException): 520 exec stmt in locals() 521 522 def test_resize1(self): 523 # Dict resizing bug, found by Jack Jansen in 2.2 CVS development. 524 # This version got an assert failure in debug build, infinite loop in 525 # release build. Unfortunately, provoking this kind of stuff requires 526 # a mix of inserts and deletes hitting exactly the right hash codes in 527 # exactly the right order, and I can't think of a randomized approach 528 # that would be *likely* to hit a failing case in reasonable time. 529 530 d = {} 531 for i in range(5): 532 d[i] = i 533 for i in range(5): 534 del d[i] 535 for i in range(5, 9): # i==8 was the problem 536 d[i] = i 537 538 def test_resize2(self): 539 # Another dict resizing bug (SF bug #1456209). 540 # This caused Segmentation faults or Illegal instructions. 541 542 class X(object): 543 def __hash__(self): 544 return 5 545 def __eq__(self, other): 546 if resizing: 547 d.clear() 548 return False 549 d = {} 550 resizing = False 551 d[X()] = 1 552 d[X()] = 2 553 d[X()] = 3 554 d[X()] = 4 555 d[X()] = 5 556 # now trigger a resize 557 resizing = True 558 d[9] = 6 559 560 def test_empty_presized_dict_in_freelist(self): 561 # Bug #3537: if an empty but presized dict with a size larger 562 # than 7 was in the freelist, it triggered an assertion failure 563 with self.assertRaises(ZeroDivisionError): 564 d = {'a': 1 // 0, 'b': None, 'c': None, 'd': None, 'e': None, 565 'f': None, 'g': None, 'h': None} 566 d = {} 567 568 def test_container_iterator(self): 569 # Bug #3680: tp_traverse was not implemented for dictiter objects 570 class C(object): 571 pass 572 iterators = (dict.iteritems, dict.itervalues, dict.iterkeys) 573 for i in iterators: 574 obj = C() 575 ref = weakref.ref(obj) 576 container = {obj: 1} 577 obj.x = i(container) 578 del obj, container 579 gc.collect() 580 self.assertIs(ref(), None, "Cycle was not collected") 581 582 def _not_tracked(self, t): 583 # Nested containers can take several collections to untrack 584 gc.collect() 585 gc.collect() 586 self.assertFalse(gc.is_tracked(t), t) 587 588 def _tracked(self, t): 589 self.assertTrue(gc.is_tracked(t), t) 590 gc.collect() 591 gc.collect() 592 self.assertTrue(gc.is_tracked(t), t) 593 594 @test_support.cpython_only 595 def test_track_literals(self): 596 # Test GC-optimization of dict literals 597 x, y, z, w = 1.5, "a", (1, None), [] 598 599 self._not_tracked({}) 600 self._not_tracked({x:(), y:x, z:1}) 601 self._not_tracked({1: "a", "b": 2}) 602 self._not_tracked({1: 2, (None, True, False, ()): int}) 603 self._not_tracked({1: object()}) 604 605 # Dicts with mutable elements are always tracked, even if those 606 # elements are not tracked right now. 607 self._tracked({1: []}) 608 self._tracked({1: ([],)}) 609 self._tracked({1: {}}) 610 self._tracked({1: set()}) 611 612 @test_support.cpython_only 613 def test_track_dynamic(self): 614 # Test GC-optimization of dynamically-created dicts 615 class MyObject(object): 616 pass 617 x, y, z, w, o = 1.5, "a", (1, object()), [], MyObject() 618 619 d = dict() 620 self._not_tracked(d) 621 d[1] = "a" 622 self._not_tracked(d) 623 d[y] = 2 624 self._not_tracked(d) 625 d[z] = 3 626 self._not_tracked(d) 627 self._not_tracked(d.copy()) 628 d[4] = w 629 self._tracked(d) 630 self._tracked(d.copy()) 631 d[4] = None 632 self._not_tracked(d) 633 self._not_tracked(d.copy()) 634 635 # dd isn't tracked right now, but it may mutate and therefore d 636 # which contains it must be tracked. 637 d = dict() 638 dd = dict() 639 d[1] = dd 640 self._not_tracked(dd) 641 self._tracked(d) 642 dd[1] = d 643 self._tracked(dd) 644 645 d = dict.fromkeys([x, y, z]) 646 self._not_tracked(d) 647 dd = dict() 648 dd.update(d) 649 self._not_tracked(dd) 650 d = dict.fromkeys([x, y, z, o]) 651 self._tracked(d) 652 dd = dict() 653 dd.update(d) 654 self._tracked(dd) 655 656 d = dict(x=x, y=y, z=z) 657 self._not_tracked(d) 658 d = dict(x=x, y=y, z=z, w=w) 659 self._tracked(d) 660 d = dict() 661 d.update(x=x, y=y, z=z) 662 self._not_tracked(d) 663 d.update(w=w) 664 self._tracked(d) 665 666 d = dict([(x, y), (z, 1)]) 667 self._not_tracked(d) 668 d = dict([(x, y), (z, w)]) 669 self._tracked(d) 670 d = dict() 671 d.update([(x, y), (z, 1)]) 672 self._not_tracked(d) 673 d.update([(x, y), (z, w)]) 674 self._tracked(d) 675 676 @test_support.cpython_only 677 def test_track_subtypes(self): 678 # Dict subtypes are always tracked 679 class MyDict(dict): 680 pass 681 self._tracked(MyDict()) 682 683 684 def test_free_after_iterating(self): 685 test_support.check_free_after_iterating(self, iter, dict) 686 test_support.check_free_after_iterating(self, lambda d: d.iterkeys(), dict) 687 test_support.check_free_after_iterating(self, lambda d: d.itervalues(), dict) 688 test_support.check_free_after_iterating(self, lambda d: d.iteritems(), dict) 689 test_support.check_free_after_iterating(self, lambda d: iter(d.viewkeys()), dict) 690 test_support.check_free_after_iterating(self, lambda d: iter(d.viewvalues()), dict) 691 test_support.check_free_after_iterating(self, lambda d: iter(d.viewitems()), dict) 692 693 from test import mapping_tests 694 695 class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol): 696 type2test = dict 697 698 class Dict(dict): 699 pass 700 701 class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol): 702 type2test = Dict 703 704 def test_main(): 705 with test_support.check_py3k_warnings( 706 ('dict(.has_key..| inequality comparisons) not supported in 3.x', 707 DeprecationWarning)): 708 test_support.run_unittest( 709 DictTest, 710 GeneralMappingTests, 711 SubclassMappingTests, 712 ) 713 714 if __name__ == "__main__": 715 test_main() 716