Lib/test/test_dict.py

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