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