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_repr_recursive_values(self): 359 OrderedDict = self.OrderedDict 360 od = OrderedDict() 361 od[42] = od.values() 362 r = repr(od) 363 # Cannot perform a stronger test, as the contents of the repr 364 # are implementation-dependent. All we can say is that we 365 # want a str result, not an exception of any sort. 366 self.assertIsInstance(r, str) 367 od[42] = od.items() 368 r = repr(od) 369 # Again. 370 self.assertIsInstance(r, str) 371 372 def test_setdefault(self): 373 OrderedDict = self.OrderedDict 374 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 375 shuffle(pairs) 376 od = OrderedDict(pairs) 377 pair_order = list(od.items()) 378 self.assertEqual(od.setdefault('a', 10), 3) 379 # make sure order didn't change 380 self.assertEqual(list(od.items()), pair_order) 381 self.assertEqual(od.setdefault('x', 10), 10) 382 # make sure 'x' is added to the end 383 self.assertEqual(list(od.items())[-1], ('x', 10)) 384 self.assertEqual(od.setdefault('g', default=9), 9) 385 386 # make sure setdefault still works when __missing__ is defined 387 class Missing(OrderedDict): 388 def __missing__(self, key): 389 return 0 390 self.assertEqual(Missing().setdefault(5, 9), 9) 391 392 def test_reinsert(self): 393 OrderedDict = self.OrderedDict 394 # Given insert a, insert b, delete a, re-insert a, 395 # verify that a is now later than b. 396 od = OrderedDict() 397 od['a'] = 1 398 od['b'] = 2 399 del od['a'] 400 self.assertEqual(list(od.items()), [('b', 2)]) 401 od['a'] = 1 402 self.assertEqual(list(od.items()), [('b', 2), ('a', 1)]) 403 404 def test_move_to_end(self): 405 OrderedDict = self.OrderedDict 406 od = OrderedDict.fromkeys('abcde') 407 self.assertEqual(list(od), list('abcde')) 408 od.move_to_end('c') 409 self.assertEqual(list(od), list('abdec')) 410 od.move_to_end('c', 0) 411 self.assertEqual(list(od), list('cabde')) 412 od.move_to_end('c', 0) 413 self.assertEqual(list(od), list('cabde')) 414 od.move_to_end('e') 415 self.assertEqual(list(od), list('cabde')) 416 od.move_to_end('b', last=False) 417 self.assertEqual(list(od), list('bcade')) 418 with self.assertRaises(KeyError): 419 od.move_to_end('x') 420 with self.assertRaises(KeyError): 421 od.move_to_end('x', 0) 422 423 def test_move_to_end_issue25406(self): 424 OrderedDict = self.OrderedDict 425 od = OrderedDict.fromkeys('abc') 426 od.move_to_end('c', last=False) 427 self.assertEqual(list(od), list('cab')) 428 od.move_to_end('a', last=False) 429 self.assertEqual(list(od), list('acb')) 430 431 od = OrderedDict.fromkeys('abc') 432 od.move_to_end('a') 433 self.assertEqual(list(od), list('bca')) 434 od.move_to_end('c') 435 self.assertEqual(list(od), list('bac')) 436 437 def test_sizeof(self): 438 OrderedDict = self.OrderedDict 439 # Wimpy test: Just verify the reported size is larger than a regular dict 440 d = dict(a=1) 441 od = OrderedDict(**d) 442 self.assertGreater(sys.getsizeof(od), sys.getsizeof(d)) 443 444 def test_views(self): 445 OrderedDict = self.OrderedDict 446 # See http://bugs.python.org/issue24286 447 s = 'the quick brown fox jumped over a lazy dog yesterday before dawn'.split() 448 od = OrderedDict.fromkeys(s) 449 self.assertEqual(od.keys(), dict(od).keys()) 450 self.assertEqual(od.items(), dict(od).items()) 451 452 def test_override_update(self): 453 OrderedDict = self.OrderedDict 454 # Verify that subclasses can override update() without breaking __init__() 455 class MyOD(OrderedDict): 456 def update(self, *args, **kwds): 457 raise Exception() 458 items = [('a', 1), ('c', 3), ('b', 2)] 459 self.assertEqual(list(MyOD(items).items()), items) 460 461 def test_highly_nested(self): 462 # Issues 25395 and 35983: test that the trashcan mechanism works 463 # correctly for OrderedDict: deleting a highly nested OrderDict 464 # should not crash Python. 465 OrderedDict = self.OrderedDict 466 obj = None 467 for _ in range(1000): 468 obj = OrderedDict([(None, obj)]) 469 del obj 470 support.gc_collect() 471 472 def test_highly_nested_subclass(self): 473 # Issues 25395 and 35983: test that the trashcan mechanism works 474 # correctly for OrderedDict: deleting a highly nested OrderDict 475 # should not crash Python. 476 OrderedDict = self.OrderedDict 477 deleted = [] 478 class MyOD(OrderedDict): 479 def __del__(self): 480 deleted.append(self.i) 481 obj = None 482 for i in range(100): 483 obj = MyOD([(None, obj)]) 484 obj.i = i 485 del obj 486 support.gc_collect() 487 self.assertEqual(deleted, list(reversed(range(100)))) 488 489 def test_delitem_hash_collision(self): 490 OrderedDict = self.OrderedDict 491 492 class Key: 493 def __init__(self, hash): 494 self._hash = hash 495 self.value = str(id(self)) 496 def __hash__(self): 497 return self._hash 498 def __eq__(self, other): 499 try: 500 return self.value == other.value 501 except AttributeError: 502 return False 503 def __repr__(self): 504 return self.value 505 506 def blocking_hash(hash): 507 # See the collision-handling in lookdict (in Objects/dictobject.c). 508 MINSIZE = 8 509 i = (hash & MINSIZE-1) 510 return (i << 2) + i + hash + 1 511 512 COLLIDING = 1 513 514 key = Key(COLLIDING) 515 colliding = Key(COLLIDING) 516 blocking = Key(blocking_hash(COLLIDING)) 517 518 od = OrderedDict() 519 od[key] = ... 520 od[blocking] = ... 521 od[colliding] = ... 522 od['after'] = ... 523 524 del od[blocking] 525 del od[colliding] 526 self.assertEqual(list(od.items()), [(key, ...), ('after', ...)]) 527 528 def test_issue24347(self): 529 OrderedDict = self.OrderedDict 530 531 class Key: 532 def __hash__(self): 533 return randrange(100000) 534 535 od = OrderedDict() 536 for i in range(100): 537 key = Key() 538 od[key] = i 539 540 # These should not crash. 541 with self.assertRaises(KeyError): 542 list(od.values()) 543 with self.assertRaises(KeyError): 544 list(od.items()) 545 with self.assertRaises(KeyError): 546 repr(od) 547 with self.assertRaises(KeyError): 548 od.copy() 549 550 def test_issue24348(self): 551 OrderedDict = self.OrderedDict 552 553 class Key: 554 def __hash__(self): 555 return 1 556 557 od = OrderedDict() 558 od[Key()] = 0 559 # This should not crash. 560 od.popitem() 561 562 def test_issue24667(self): 563 """ 564 dict resizes after a certain number of insertion operations, 565 whether or not there were deletions that freed up slots in the 566 hash table. During fast node lookup, OrderedDict must correctly 567 respond to all resizes, even if the current "size" is the same 568 as the old one. We verify that here by forcing a dict resize 569 on a sparse odict and then perform an operation that should 570 trigger an odict resize (e.g. popitem). One key aspect here is 571 that we will keep the size of the odict the same at each popitem 572 call. This verifies that we handled the dict resize properly. 573 """ 574 OrderedDict = self.OrderedDict 575 576 od = OrderedDict() 577 for c0 in '0123456789ABCDEF': 578 for c1 in '0123456789ABCDEF': 579 if len(od) == 4: 580 # This should not raise a KeyError. 581 od.popitem(last=False) 582 key = c0 + c1 583 od[key] = key 584 585 # Direct use of dict methods 586 587 def test_dict_setitem(self): 588 OrderedDict = self.OrderedDict 589 od = OrderedDict() 590 dict.__setitem__(od, 'spam', 1) 591 self.assertNotIn('NULL', repr(od)) 592 593 def test_dict_delitem(self): 594 OrderedDict = self.OrderedDict 595 od = OrderedDict() 596 od['spam'] = 1 597 od['ham'] = 2 598 dict.__delitem__(od, 'spam') 599 with self.assertRaises(KeyError): 600 repr(od) 601 602 def test_dict_clear(self): 603 OrderedDict = self.OrderedDict 604 od = OrderedDict() 605 od['spam'] = 1 606 od['ham'] = 2 607 dict.clear(od) 608 self.assertNotIn('NULL', repr(od)) 609 610 def test_dict_pop(self): 611 OrderedDict = self.OrderedDict 612 od = OrderedDict() 613 od['spam'] = 1 614 od['ham'] = 2 615 dict.pop(od, 'spam') 616 with self.assertRaises(KeyError): 617 repr(od) 618 619 def test_dict_popitem(self): 620 OrderedDict = self.OrderedDict 621 od = OrderedDict() 622 od['spam'] = 1 623 od['ham'] = 2 624 dict.popitem(od) 625 with self.assertRaises(KeyError): 626 repr(od) 627 628 def test_dict_setdefault(self): 629 OrderedDict = self.OrderedDict 630 od = OrderedDict() 631 dict.setdefault(od, 'spam', 1) 632 self.assertNotIn('NULL', repr(od)) 633 634 def test_dict_update(self): 635 OrderedDict = self.OrderedDict 636 od = OrderedDict() 637 dict.update(od, [('spam', 1)]) 638 self.assertNotIn('NULL', repr(od)) 639 640 def test_reference_loop(self): 641 # Issue 25935 642 OrderedDict = self.OrderedDict 643 class A: 644 od = OrderedDict() 645 A.od[A] = None 646 r = weakref.ref(A) 647 del A 648 gc.collect() 649 self.assertIsNone(r()) 650 651 def test_free_after_iterating(self): 652 support.check_free_after_iterating(self, iter, self.OrderedDict) 653 support.check_free_after_iterating(self, lambda d: iter(d.keys()), self.OrderedDict) 654 support.check_free_after_iterating(self, lambda d: iter(d.values()), self.OrderedDict) 655 support.check_free_after_iterating(self, lambda d: iter(d.items()), self.OrderedDict) 656 657 658class PurePythonOrderedDictTests(OrderedDictTests, unittest.TestCase): 659 660 module = py_coll 661 OrderedDict = py_coll.OrderedDict 662 663 664class CPythonBuiltinDictTests(unittest.TestCase): 665 """Builtin dict preserves insertion order. 666 667 Reuse some of tests in OrderedDict selectively. 668 """ 669 670 module = builtins 671 OrderedDict = dict 672 673for method in ( 674 "test_init test_update test_abc test_clear test_delitem " + 675 "test_setitem test_detect_deletion_during_iteration " + 676 "test_popitem test_reinsert test_override_update " + 677 "test_highly_nested test_highly_nested_subclass " + 678 "test_delitem_hash_collision ").split(): 679 setattr(CPythonBuiltinDictTests, method, getattr(OrderedDictTests, method)) 680del method 681 682 683@unittest.skipUnless(c_coll, 'requires the C version of the collections module') 684class CPythonOrderedDictTests(OrderedDictTests, unittest.TestCase): 685 686 module = c_coll 687 OrderedDict = c_coll.OrderedDict 688 check_sizeof = support.check_sizeof 689 690 @support.cpython_only 691 def test_sizeof_exact(self): 692 OrderedDict = self.OrderedDict 693 calcsize = struct.calcsize 694 size = support.calcobjsize 695 check = self.check_sizeof 696 697 basicsize = size('nQ2P' + '3PnPn2P') + calcsize('2nP2n') 698 699 entrysize = calcsize('n2P') 700 p = calcsize('P') 701 nodesize = calcsize('Pn2P') 702 703 od = OrderedDict() 704 check(od, basicsize + 8 + 5*entrysize) # 8byte indices + 8*2//3 * entry table 705 od.x = 1 706 check(od, basicsize + 8 + 5*entrysize) 707 od.update([(i, i) for i in range(3)]) 708 check(od, basicsize + 8*p + 8 + 5*entrysize + 3*nodesize) 709 od.update([(i, i) for i in range(3, 10)]) 710 check(od, basicsize + 16*p + 16 + 10*entrysize + 10*nodesize) 711 712 check(od.keys(), size('P')) 713 check(od.items(), size('P')) 714 check(od.values(), size('P')) 715 716 itersize = size('iP2n2P') 717 check(iter(od), itersize) 718 check(iter(od.keys()), itersize) 719 check(iter(od.items()), itersize) 720 check(iter(od.values()), itersize) 721 722 def test_key_change_during_iteration(self): 723 OrderedDict = self.OrderedDict 724 725 od = OrderedDict.fromkeys('abcde') 726 self.assertEqual(list(od), list('abcde')) 727 with self.assertRaises(RuntimeError): 728 for i, k in enumerate(od): 729 od.move_to_end(k) 730 self.assertLess(i, 5) 731 with self.assertRaises(RuntimeError): 732 for k in od: 733 od['f'] = None 734 with self.assertRaises(RuntimeError): 735 for k in od: 736 del od['c'] 737 self.assertEqual(list(od), list('bdeaf')) 738 739 def test_iterators_pickling(self): 740 OrderedDict = self.OrderedDict 741 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 742 od = OrderedDict(pairs) 743 744 for method_name in ('keys', 'values', 'items'): 745 meth = getattr(od, method_name) 746 expected = list(meth())[1:] 747 for i in range(pickle.HIGHEST_PROTOCOL + 1): 748 with self.subTest(method_name=method_name, protocol=i): 749 it = iter(meth()) 750 next(it) 751 p = pickle.dumps(it, i) 752 unpickled = pickle.loads(p) 753 self.assertEqual(list(unpickled), expected) 754 self.assertEqual(list(it), expected) 755 756 @support.cpython_only 757 def test_weakref_list_is_not_traversed(self): 758 # Check that the weakref list is not traversed when collecting 759 # OrderedDict objects. See bpo-39778 for more information. 760 761 gc.collect() 762 763 x = self.OrderedDict() 764 x.cycle = x 765 766 cycle = [] 767 cycle.append(cycle) 768 769 x_ref = weakref.ref(x) 770 cycle.append(x_ref) 771 772 del x, cycle, x_ref 773 774 gc.collect() 775 776 777class PurePythonOrderedDictSubclassTests(PurePythonOrderedDictTests): 778 779 module = py_coll 780 class OrderedDict(py_coll.OrderedDict): 781 pass 782 783 784class CPythonOrderedDictSubclassTests(CPythonOrderedDictTests): 785 786 module = c_coll 787 class OrderedDict(c_coll.OrderedDict): 788 pass 789 790 791class PurePythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): 792 793 @classmethod 794 def setUpClass(cls): 795 cls.type2test = py_coll.OrderedDict 796 797 def test_popitem(self): 798 d = self._empty_mapping() 799 self.assertRaises(KeyError, d.popitem) 800 801 802@unittest.skipUnless(c_coll, 'requires the C version of the collections module') 803class CPythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): 804 805 @classmethod 806 def setUpClass(cls): 807 cls.type2test = c_coll.OrderedDict 808 809 def test_popitem(self): 810 d = self._empty_mapping() 811 self.assertRaises(KeyError, d.popitem) 812 813 814class PurePythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): 815 816 @classmethod 817 def setUpClass(cls): 818 class MyOrderedDict(py_coll.OrderedDict): 819 pass 820 cls.type2test = MyOrderedDict 821 822 def test_popitem(self): 823 d = self._empty_mapping() 824 self.assertRaises(KeyError, d.popitem) 825 826 827@unittest.skipUnless(c_coll, 'requires the C version of the collections module') 828class CPythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): 829 830 @classmethod 831 def setUpClass(cls): 832 class MyOrderedDict(c_coll.OrderedDict): 833 pass 834 cls.type2test = MyOrderedDict 835 836 def test_popitem(self): 837 d = self._empty_mapping() 838 self.assertRaises(KeyError, d.popitem) 839 840 841if __name__ == "__main__": 842 unittest.main() 843