1import builtins 2import contextlib 3import copy 4import gc 5import pickle 6from random import randrange, shuffle 7import struct 8import sys 9import unittest 10import weakref 11from collections.abc import MutableMapping 12from test import mapping_tests, support 13 14 15py_coll = support.import_fresh_module('collections', blocked=['_collections']) 16c_coll = support.import_fresh_module('collections', fresh=['_collections']) 17 18 19@contextlib.contextmanager 20def replaced_module(name, replacement): 21 original_module = sys.modules[name] 22 sys.modules[name] = replacement 23 try: 24 yield 25 finally: 26 sys.modules[name] = original_module 27 28 29class OrderedDictTests: 30 31 def test_init(self): 32 OrderedDict = self.OrderedDict 33 with self.assertRaises(TypeError): 34 OrderedDict([('a', 1), ('b', 2)], None) # too many args 35 pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] 36 self.assertEqual(sorted(OrderedDict(dict(pairs)).items()), pairs) # dict input 37 self.assertEqual(sorted(OrderedDict(**dict(pairs)).items()), pairs) # kwds input 38 self.assertEqual(list(OrderedDict(pairs).items()), pairs) # pairs input 39 self.assertEqual(list(OrderedDict([('a', 1), ('b', 2), ('c', 9), ('d', 4)], 40 c=3, e=5).items()), pairs) # mixed input 41 42 # make sure no positional args conflict with possible kwdargs 43 self.assertEqual(list(OrderedDict(self=42).items()), [('self', 42)]) 44 self.assertEqual(list(OrderedDict(other=42).items()), [('other', 42)]) 45 self.assertRaises(TypeError, OrderedDict, 42) 46 self.assertRaises(TypeError, OrderedDict, (), ()) 47 self.assertRaises(TypeError, OrderedDict.__init__) 48 49 # Make sure that direct calls to __init__ do not clear previous contents 50 d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)]) 51 d.__init__([('e', 5), ('f', 6)], g=7, d=4) 52 self.assertEqual(list(d.items()), 53 [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)]) 54 55 def test_468(self): 56 OrderedDict = self.OrderedDict 57 items = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)] 58 shuffle(items) 59 argdict = OrderedDict(items) 60 d = OrderedDict(**argdict) 61 self.assertEqual(list(d.items()), items) 62 63 def test_update(self): 64 OrderedDict = self.OrderedDict 65 with self.assertRaises(TypeError): 66 OrderedDict().update([('a', 1), ('b', 2)], None) # too many args 67 pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] 68 od = OrderedDict() 69 od.update(dict(pairs)) 70 self.assertEqual(sorted(od.items()), pairs) # dict input 71 od = OrderedDict() 72 od.update(**dict(pairs)) 73 self.assertEqual(sorted(od.items()), pairs) # kwds input 74 od = OrderedDict() 75 od.update(pairs) 76 self.assertEqual(list(od.items()), pairs) # pairs input 77 od = OrderedDict() 78 od.update([('a', 1), ('b', 2), ('c', 9), ('d', 4)], c=3, e=5) 79 self.assertEqual(list(od.items()), pairs) # mixed input 80 81 # Issue 9137: Named argument called 'other' or 'self' 82 # shouldn't be treated specially. 83 od = OrderedDict() 84 od.update(self=23) 85 self.assertEqual(list(od.items()), [('self', 23)]) 86 od = OrderedDict() 87 od.update(other={}) 88 self.assertEqual(list(od.items()), [('other', {})]) 89 od = OrderedDict() 90 od.update(red=5, blue=6, other=7, self=8) 91 self.assertEqual(sorted(list(od.items())), 92 [('blue', 6), ('other', 7), ('red', 5), ('self', 8)]) 93 94 # Make sure that direct calls to update do not clear previous contents 95 # add that updates items are not moved to the end 96 d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)]) 97 d.update([('e', 5), ('f', 6)], g=7, d=4) 98 self.assertEqual(list(d.items()), 99 [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)]) 100 101 self.assertRaises(TypeError, OrderedDict().update, 42) 102 self.assertRaises(TypeError, OrderedDict().update, (), ()) 103 self.assertRaises(TypeError, OrderedDict.update) 104 105 self.assertRaises(TypeError, OrderedDict().update, 42) 106 self.assertRaises(TypeError, OrderedDict().update, (), ()) 107 self.assertRaises(TypeError, OrderedDict.update) 108 109 def test_init_calls(self): 110 calls = [] 111 class Spam: 112 def keys(self): 113 calls.append('keys') 114 return () 115 def items(self): 116 calls.append('items') 117 return () 118 119 self.OrderedDict(Spam()) 120 self.assertEqual(calls, ['keys']) 121 122 def test_fromkeys(self): 123 OrderedDict = self.OrderedDict 124 od = OrderedDict.fromkeys('abc') 125 self.assertEqual(list(od.items()), [(c, None) for c in 'abc']) 126 od = OrderedDict.fromkeys('abc', value=None) 127 self.assertEqual(list(od.items()), [(c, None) for c in 'abc']) 128 od = OrderedDict.fromkeys('abc', value=0) 129 self.assertEqual(list(od.items()), [(c, 0) for c in 'abc']) 130 131 def test_abc(self): 132 OrderedDict = self.OrderedDict 133 self.assertIsInstance(OrderedDict(), MutableMapping) 134 self.assertTrue(issubclass(OrderedDict, MutableMapping)) 135 136 def test_clear(self): 137 OrderedDict = self.OrderedDict 138 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 139 shuffle(pairs) 140 od = OrderedDict(pairs) 141 self.assertEqual(len(od), len(pairs)) 142 od.clear() 143 self.assertEqual(len(od), 0) 144 145 def test_delitem(self): 146 OrderedDict = self.OrderedDict 147 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 148 od = OrderedDict(pairs) 149 del od['a'] 150 self.assertNotIn('a', od) 151 with self.assertRaises(KeyError): 152 del od['a'] 153 self.assertEqual(list(od.items()), pairs[:2] + pairs[3:]) 154 155 def test_setitem(self): 156 OrderedDict = self.OrderedDict 157 od = OrderedDict([('d', 1), ('b', 2), ('c', 3), ('a', 4), ('e', 5)]) 158 od['c'] = 10 # existing element 159 od['f'] = 20 # new element 160 self.assertEqual(list(od.items()), 161 [('d', 1), ('b', 2), ('c', 10), ('a', 4), ('e', 5), ('f', 20)]) 162 163 def test_iterators(self): 164 OrderedDict = self.OrderedDict 165 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 166 shuffle(pairs) 167 od = OrderedDict(pairs) 168 self.assertEqual(list(od), [t[0] for t in pairs]) 169 self.assertEqual(list(od.keys()), [t[0] for t in pairs]) 170 self.assertEqual(list(od.values()), [t[1] for t in pairs]) 171 self.assertEqual(list(od.items()), pairs) 172 self.assertEqual(list(reversed(od)), 173 [t[0] for t in reversed(pairs)]) 174 self.assertEqual(list(reversed(od.keys())), 175 [t[0] for t in reversed(pairs)]) 176 self.assertEqual(list(reversed(od.values())), 177 [t[1] for t in reversed(pairs)]) 178 self.assertEqual(list(reversed(od.items())), list(reversed(pairs))) 179 180 def test_detect_deletion_during_iteration(self): 181 OrderedDict = self.OrderedDict 182 od = OrderedDict.fromkeys('abc') 183 it = iter(od) 184 key = next(it) 185 del od[key] 186 with self.assertRaises(Exception): 187 # Note, the exact exception raised is not guaranteed 188 # The only guarantee that the next() will not succeed 189 next(it) 190 191 def test_sorted_iterators(self): 192 OrderedDict = self.OrderedDict 193 with self.assertRaises(TypeError): 194 OrderedDict([('a', 1), ('b', 2)], None) 195 pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] 196 od = OrderedDict(pairs) 197 self.assertEqual(sorted(od), [t[0] for t in pairs]) 198 self.assertEqual(sorted(od.keys()), [t[0] for t in pairs]) 199 self.assertEqual(sorted(od.values()), [t[1] for t in pairs]) 200 self.assertEqual(sorted(od.items()), pairs) 201 self.assertEqual(sorted(reversed(od)), 202 sorted([t[0] for t in reversed(pairs)])) 203 204 def test_iterators_empty(self): 205 OrderedDict = self.OrderedDict 206 od = OrderedDict() 207 empty = [] 208 self.assertEqual(list(od), empty) 209 self.assertEqual(list(od.keys()), empty) 210 self.assertEqual(list(od.values()), empty) 211 self.assertEqual(list(od.items()), empty) 212 self.assertEqual(list(reversed(od)), empty) 213 self.assertEqual(list(reversed(od.keys())), empty) 214 self.assertEqual(list(reversed(od.values())), empty) 215 self.assertEqual(list(reversed(od.items())), empty) 216 217 def test_popitem(self): 218 OrderedDict = self.OrderedDict 219 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 220 shuffle(pairs) 221 od = OrderedDict(pairs) 222 while pairs: 223 self.assertEqual(od.popitem(), pairs.pop()) 224 with self.assertRaises(KeyError): 225 od.popitem() 226 self.assertEqual(len(od), 0) 227 228 def test_popitem_last(self): 229 OrderedDict = self.OrderedDict 230 pairs = [(i, i) for i in range(30)] 231 232 obj = OrderedDict(pairs) 233 for i in range(8): 234 obj.popitem(True) 235 obj.popitem(True) 236 obj.popitem(last=True) 237 self.assertEqual(len(obj), 20) 238 239 def test_pop(self): 240 OrderedDict = self.OrderedDict 241 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 242 shuffle(pairs) 243 od = OrderedDict(pairs) 244 shuffle(pairs) 245 while pairs: 246 k, v = pairs.pop() 247 self.assertEqual(od.pop(k), v) 248 with self.assertRaises(KeyError): 249 od.pop('xyz') 250 self.assertEqual(len(od), 0) 251 self.assertEqual(od.pop(k, 12345), 12345) 252 253 # make sure pop still works when __missing__ is defined 254 class Missing(OrderedDict): 255 def __missing__(self, key): 256 return 0 257 m = Missing(a=1) 258 self.assertEqual(m.pop('b', 5), 5) 259 self.assertEqual(m.pop('a', 6), 1) 260 self.assertEqual(m.pop('a', 6), 6) 261 self.assertEqual(m.pop('a', default=6), 6) 262 with self.assertRaises(KeyError): 263 m.pop('a') 264 265 def test_equality(self): 266 OrderedDict = self.OrderedDict 267 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 268 shuffle(pairs) 269 od1 = OrderedDict(pairs) 270 od2 = OrderedDict(pairs) 271 self.assertEqual(od1, od2) # same order implies equality 272 pairs = pairs[2:] + pairs[:2] 273 od2 = OrderedDict(pairs) 274 self.assertNotEqual(od1, od2) # different order implies inequality 275 # comparison to regular dict is not order sensitive 276 self.assertEqual(od1, dict(od2)) 277 self.assertEqual(dict(od2), od1) 278 # different length implied inequality 279 self.assertNotEqual(od1, OrderedDict(pairs[:-1])) 280 281 def test_copying(self): 282 OrderedDict = self.OrderedDict 283 # Check that ordered dicts are copyable, deepcopyable, picklable, 284 # and have a repr/eval round-trip 285 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 286 od = OrderedDict(pairs) 287 def check(dup): 288 msg = "\ncopy: %s\nod: %s" % (dup, od) 289 self.assertIsNot(dup, od, msg) 290 self.assertEqual(dup, od) 291 self.assertEqual(list(dup.items()), list(od.items())) 292 self.assertEqual(len(dup), len(od)) 293 self.assertEqual(type(dup), type(od)) 294 check(od.copy()) 295 check(copy.copy(od)) 296 check(copy.deepcopy(od)) 297 # pickle directly pulls the module, so we have to fake it 298 with replaced_module('collections', self.module): 299 for proto in range(pickle.HIGHEST_PROTOCOL + 1): 300 with self.subTest(proto=proto): 301 check(pickle.loads(pickle.dumps(od, proto))) 302 check(eval(repr(od))) 303 update_test = OrderedDict() 304 update_test.update(od) 305 check(update_test) 306 check(OrderedDict(od)) 307 308 def test_yaml_linkage(self): 309 OrderedDict = self.OrderedDict 310 # Verify that __reduce__ is setup in a way that supports PyYAML's dump() feature. 311 # In yaml, lists are native but tuples are not. 312 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 313 od = OrderedDict(pairs) 314 # yaml.dump(od) --> 315 # '!!python/object/apply:__main__.OrderedDict\n- - [a, 1]\n - [b, 2]\n' 316 self.assertTrue(all(type(pair)==list for pair in od.__reduce__()[1])) 317 318 def test_reduce_not_too_fat(self): 319 OrderedDict = self.OrderedDict 320 # do not save instance dictionary if not needed 321 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 322 od = OrderedDict(pairs) 323 self.assertIsInstance(od.__dict__, dict) 324 self.assertIsNone(od.__reduce__()[2]) 325 od.x = 10 326 self.assertEqual(od.__dict__['x'], 10) 327 self.assertEqual(od.__reduce__()[2], {'x': 10}) 328 329 def test_pickle_recursive(self): 330 OrderedDict = self.OrderedDict 331 od = OrderedDict() 332 od[1] = od 333 334 # pickle directly pulls the module, so we have to fake it 335 with replaced_module('collections', self.module): 336 for proto in range(-1, pickle.HIGHEST_PROTOCOL + 1): 337 dup = pickle.loads(pickle.dumps(od, proto)) 338 self.assertIsNot(dup, od) 339 self.assertEqual(list(dup.keys()), [1]) 340 self.assertIs(dup[1], dup) 341 342 def test_repr(self): 343 OrderedDict = self.OrderedDict 344 od = OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]) 345 self.assertEqual(repr(od), 346 "OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])") 347 self.assertEqual(eval(repr(od)), od) 348 self.assertEqual(repr(OrderedDict()), "OrderedDict()") 349 350 def test_repr_recursive(self): 351 OrderedDict = self.OrderedDict 352 # See issue #9826 353 od = OrderedDict.fromkeys('abc') 354 od['x'] = od 355 self.assertEqual(repr(od), 356 "OrderedDict([('a', None), ('b', None), ('c', None), ('x', ...)])") 357 358 def test_setdefault(self): 359 OrderedDict = self.OrderedDict 360 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 361 shuffle(pairs) 362 od = OrderedDict(pairs) 363 pair_order = list(od.items()) 364 self.assertEqual(od.setdefault('a', 10), 3) 365 # make sure order didn't change 366 self.assertEqual(list(od.items()), pair_order) 367 self.assertEqual(od.setdefault('x', 10), 10) 368 # make sure 'x' is added to the end 369 self.assertEqual(list(od.items())[-1], ('x', 10)) 370 self.assertEqual(od.setdefault('g', default=9), 9) 371 372 # make sure setdefault still works when __missing__ is defined 373 class Missing(OrderedDict): 374 def __missing__(self, key): 375 return 0 376 self.assertEqual(Missing().setdefault(5, 9), 9) 377 378 def test_reinsert(self): 379 OrderedDict = self.OrderedDict 380 # Given insert a, insert b, delete a, re-insert a, 381 # verify that a is now later than b. 382 od = OrderedDict() 383 od['a'] = 1 384 od['b'] = 2 385 del od['a'] 386 self.assertEqual(list(od.items()), [('b', 2)]) 387 od['a'] = 1 388 self.assertEqual(list(od.items()), [('b', 2), ('a', 1)]) 389 390 def test_move_to_end(self): 391 OrderedDict = self.OrderedDict 392 od = OrderedDict.fromkeys('abcde') 393 self.assertEqual(list(od), list('abcde')) 394 od.move_to_end('c') 395 self.assertEqual(list(od), list('abdec')) 396 od.move_to_end('c', 0) 397 self.assertEqual(list(od), list('cabde')) 398 od.move_to_end('c', 0) 399 self.assertEqual(list(od), list('cabde')) 400 od.move_to_end('e') 401 self.assertEqual(list(od), list('cabde')) 402 od.move_to_end('b', last=False) 403 self.assertEqual(list(od), list('bcade')) 404 with self.assertRaises(KeyError): 405 od.move_to_end('x') 406 with self.assertRaises(KeyError): 407 od.move_to_end('x', 0) 408 409 def test_move_to_end_issue25406(self): 410 OrderedDict = self.OrderedDict 411 od = OrderedDict.fromkeys('abc') 412 od.move_to_end('c', last=False) 413 self.assertEqual(list(od), list('cab')) 414 od.move_to_end('a', last=False) 415 self.assertEqual(list(od), list('acb')) 416 417 od = OrderedDict.fromkeys('abc') 418 od.move_to_end('a') 419 self.assertEqual(list(od), list('bca')) 420 od.move_to_end('c') 421 self.assertEqual(list(od), list('bac')) 422 423 def test_sizeof(self): 424 OrderedDict = self.OrderedDict 425 # Wimpy test: Just verify the reported size is larger than a regular dict 426 d = dict(a=1) 427 od = OrderedDict(**d) 428 self.assertGreater(sys.getsizeof(od), sys.getsizeof(d)) 429 430 def test_views(self): 431 OrderedDict = self.OrderedDict 432 # See http://bugs.python.org/issue24286 433 s = 'the quick brown fox jumped over a lazy dog yesterday before dawn'.split() 434 od = OrderedDict.fromkeys(s) 435 self.assertEqual(od.keys(), dict(od).keys()) 436 self.assertEqual(od.items(), dict(od).items()) 437 438 def test_override_update(self): 439 OrderedDict = self.OrderedDict 440 # Verify that subclasses can override update() without breaking __init__() 441 class MyOD(OrderedDict): 442 def update(self, *args, **kwds): 443 raise Exception() 444 items = [('a', 1), ('c', 3), ('b', 2)] 445 self.assertEqual(list(MyOD(items).items()), items) 446 447 def test_highly_nested(self): 448 # Issue 25395: crashes during garbage collection 449 OrderedDict = self.OrderedDict 450 obj = None 451 for _ in range(1000): 452 obj = OrderedDict([(None, obj)]) 453 del obj 454 support.gc_collect() 455 456 def test_highly_nested_subclass(self): 457 # Issue 25395: crashes during garbage collection 458 OrderedDict = self.OrderedDict 459 deleted = [] 460 class MyOD(OrderedDict): 461 def __del__(self): 462 deleted.append(self.i) 463 obj = None 464 for i in range(100): 465 obj = MyOD([(None, obj)]) 466 obj.i = i 467 del obj 468 support.gc_collect() 469 self.assertEqual(deleted, list(reversed(range(100)))) 470 471 def test_delitem_hash_collision(self): 472 OrderedDict = self.OrderedDict 473 474 class Key: 475 def __init__(self, hash): 476 self._hash = hash 477 self.value = str(id(self)) 478 def __hash__(self): 479 return self._hash 480 def __eq__(self, other): 481 try: 482 return self.value == other.value 483 except AttributeError: 484 return False 485 def __repr__(self): 486 return self.value 487 488 def blocking_hash(hash): 489 # See the collision-handling in lookdict (in Objects/dictobject.c). 490 MINSIZE = 8 491 i = (hash & MINSIZE-1) 492 return (i << 2) + i + hash + 1 493 494 COLLIDING = 1 495 496 key = Key(COLLIDING) 497 colliding = Key(COLLIDING) 498 blocking = Key(blocking_hash(COLLIDING)) 499 500 od = OrderedDict() 501 od[key] = ... 502 od[blocking] = ... 503 od[colliding] = ... 504 od['after'] = ... 505 506 del od[blocking] 507 del od[colliding] 508 self.assertEqual(list(od.items()), [(key, ...), ('after', ...)]) 509 510 def test_issue24347(self): 511 OrderedDict = self.OrderedDict 512 513 class Key: 514 def __hash__(self): 515 return randrange(100000) 516 517 od = OrderedDict() 518 for i in range(100): 519 key = Key() 520 od[key] = i 521 522 # These should not crash. 523 with self.assertRaises(KeyError): 524 list(od.values()) 525 with self.assertRaises(KeyError): 526 list(od.items()) 527 with self.assertRaises(KeyError): 528 repr(od) 529 with self.assertRaises(KeyError): 530 od.copy() 531 532 def test_issue24348(self): 533 OrderedDict = self.OrderedDict 534 535 class Key: 536 def __hash__(self): 537 return 1 538 539 od = OrderedDict() 540 od[Key()] = 0 541 # This should not crash. 542 od.popitem() 543 544 def test_issue24667(self): 545 """ 546 dict resizes after a certain number of insertion operations, 547 whether or not there were deletions that freed up slots in the 548 hash table. During fast node lookup, OrderedDict must correctly 549 respond to all resizes, even if the current "size" is the same 550 as the old one. We verify that here by forcing a dict resize 551 on a sparse odict and then perform an operation that should 552 trigger an odict resize (e.g. popitem). One key aspect here is 553 that we will keep the size of the odict the same at each popitem 554 call. This verifies that we handled the dict resize properly. 555 """ 556 OrderedDict = self.OrderedDict 557 558 od = OrderedDict() 559 for c0 in '0123456789ABCDEF': 560 for c1 in '0123456789ABCDEF': 561 if len(od) == 4: 562 # This should not raise a KeyError. 563 od.popitem(last=False) 564 key = c0 + c1 565 od[key] = key 566 567 # Direct use of dict methods 568 569 def test_dict_setitem(self): 570 OrderedDict = self.OrderedDict 571 od = OrderedDict() 572 dict.__setitem__(od, 'spam', 1) 573 self.assertNotIn('NULL', repr(od)) 574 575 def test_dict_delitem(self): 576 OrderedDict = self.OrderedDict 577 od = OrderedDict() 578 od['spam'] = 1 579 od['ham'] = 2 580 dict.__delitem__(od, 'spam') 581 with self.assertRaises(KeyError): 582 repr(od) 583 584 def test_dict_clear(self): 585 OrderedDict = self.OrderedDict 586 od = OrderedDict() 587 od['spam'] = 1 588 od['ham'] = 2 589 dict.clear(od) 590 self.assertNotIn('NULL', repr(od)) 591 592 def test_dict_pop(self): 593 OrderedDict = self.OrderedDict 594 od = OrderedDict() 595 od['spam'] = 1 596 od['ham'] = 2 597 dict.pop(od, 'spam') 598 with self.assertRaises(KeyError): 599 repr(od) 600 601 def test_dict_popitem(self): 602 OrderedDict = self.OrderedDict 603 od = OrderedDict() 604 od['spam'] = 1 605 od['ham'] = 2 606 dict.popitem(od) 607 with self.assertRaises(KeyError): 608 repr(od) 609 610 def test_dict_setdefault(self): 611 OrderedDict = self.OrderedDict 612 od = OrderedDict() 613 dict.setdefault(od, 'spam', 1) 614 self.assertNotIn('NULL', repr(od)) 615 616 def test_dict_update(self): 617 OrderedDict = self.OrderedDict 618 od = OrderedDict() 619 dict.update(od, [('spam', 1)]) 620 self.assertNotIn('NULL', repr(od)) 621 622 def test_reference_loop(self): 623 # Issue 25935 624 OrderedDict = self.OrderedDict 625 class A: 626 od = OrderedDict() 627 A.od[A] = None 628 r = weakref.ref(A) 629 del A 630 gc.collect() 631 self.assertIsNone(r()) 632 633 def test_free_after_iterating(self): 634 support.check_free_after_iterating(self, iter, self.OrderedDict) 635 support.check_free_after_iterating(self, lambda d: iter(d.keys()), self.OrderedDict) 636 support.check_free_after_iterating(self, lambda d: iter(d.values()), self.OrderedDict) 637 support.check_free_after_iterating(self, lambda d: iter(d.items()), self.OrderedDict) 638 639 640class PurePythonOrderedDictTests(OrderedDictTests, unittest.TestCase): 641 642 module = py_coll 643 OrderedDict = py_coll.OrderedDict 644 645 646class CPythonBuiltinDictTests(unittest.TestCase): 647 """Builtin dict preserves insertion order. 648 649 Reuse some of tests in OrderedDict selectively. 650 """ 651 652 module = builtins 653 OrderedDict = dict 654 655for method in ( 656 "test_init test_update test_abc test_clear test_delitem " + 657 "test_setitem test_detect_deletion_during_iteration " + 658 "test_popitem test_reinsert test_override_update " + 659 "test_highly_nested test_highly_nested_subclass " + 660 "test_delitem_hash_collision ").split(): 661 setattr(CPythonBuiltinDictTests, method, getattr(OrderedDictTests, method)) 662del method 663 664 665@unittest.skipUnless(c_coll, 'requires the C version of the collections module') 666class CPythonOrderedDictTests(OrderedDictTests, unittest.TestCase): 667 668 module = c_coll 669 OrderedDict = c_coll.OrderedDict 670 check_sizeof = support.check_sizeof 671 672 @support.cpython_only 673 def test_sizeof_exact(self): 674 OrderedDict = self.OrderedDict 675 calcsize = struct.calcsize 676 size = support.calcobjsize 677 check = self.check_sizeof 678 679 basicsize = size('nQ2P' + '3PnPn2P') + calcsize('2nP2n') 680 681 entrysize = calcsize('n2P') 682 p = calcsize('P') 683 nodesize = calcsize('Pn2P') 684 685 od = OrderedDict() 686 check(od, basicsize + 8*p + 8 + 5*entrysize) # 8byte indicies + 8*2//3 * entry table 687 od.x = 1 688 check(od, basicsize + 8*p + 8 + 5*entrysize) 689 od.update([(i, i) for i in range(3)]) 690 check(od, basicsize + 8*p + 8 + 5*entrysize + 3*nodesize) 691 od.update([(i, i) for i in range(3, 10)]) 692 check(od, basicsize + 16*p + 16 + 10*entrysize + 10*nodesize) 693 694 check(od.keys(), size('P')) 695 check(od.items(), size('P')) 696 check(od.values(), size('P')) 697 698 itersize = size('iP2n2P') 699 check(iter(od), itersize) 700 check(iter(od.keys()), itersize) 701 check(iter(od.items()), itersize) 702 check(iter(od.values()), itersize) 703 704 def test_key_change_during_iteration(self): 705 OrderedDict = self.OrderedDict 706 707 od = OrderedDict.fromkeys('abcde') 708 self.assertEqual(list(od), list('abcde')) 709 with self.assertRaises(RuntimeError): 710 for i, k in enumerate(od): 711 od.move_to_end(k) 712 self.assertLess(i, 5) 713 with self.assertRaises(RuntimeError): 714 for k in od: 715 od['f'] = None 716 with self.assertRaises(RuntimeError): 717 for k in od: 718 del od['c'] 719 self.assertEqual(list(od), list('bdeaf')) 720 721 722class PurePythonOrderedDictSubclassTests(PurePythonOrderedDictTests): 723 724 module = py_coll 725 class OrderedDict(py_coll.OrderedDict): 726 pass 727 728 729class CPythonOrderedDictSubclassTests(CPythonOrderedDictTests): 730 731 module = c_coll 732 class OrderedDict(c_coll.OrderedDict): 733 pass 734 735 736class PurePythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): 737 738 @classmethod 739 def setUpClass(cls): 740 cls.type2test = py_coll.OrderedDict 741 742 def test_popitem(self): 743 d = self._empty_mapping() 744 self.assertRaises(KeyError, d.popitem) 745 746 747@unittest.skipUnless(c_coll, 'requires the C version of the collections module') 748class CPythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): 749 750 @classmethod 751 def setUpClass(cls): 752 cls.type2test = c_coll.OrderedDict 753 754 def test_popitem(self): 755 d = self._empty_mapping() 756 self.assertRaises(KeyError, d.popitem) 757 758 759class PurePythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): 760 761 @classmethod 762 def setUpClass(cls): 763 class MyOrderedDict(py_coll.OrderedDict): 764 pass 765 cls.type2test = MyOrderedDict 766 767 def test_popitem(self): 768 d = self._empty_mapping() 769 self.assertRaises(KeyError, d.popitem) 770 771 772@unittest.skipUnless(c_coll, 'requires the C version of the collections module') 773class CPythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): 774 775 @classmethod 776 def setUpClass(cls): 777 class MyOrderedDict(c_coll.OrderedDict): 778 pass 779 cls.type2test = MyOrderedDict 780 781 def test_popitem(self): 782 d = self._empty_mapping() 783 self.assertRaises(KeyError, d.popitem) 784 785 786if __name__ == "__main__": 787 unittest.main() 788