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.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()