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 @support.cpython_only 658 def test_ordered_dict_items_result_gc(self): 659 # bpo-42536: OrderedDict.items's tuple-reuse speed trick breaks the GC's 660 # assumptions about what can be untracked. Make sure we re-track result 661 # tuples whenever we reuse them. 662 it = iter(self.OrderedDict({None: []}).items()) 663 gc.collect() 664 # That GC collection probably untracked the recycled internal result 665 # tuple, which is initialized to (None, None). Make sure it's re-tracked 666 # when it's mutated and returned from __next__: 667 self.assertTrue(gc.is_tracked(next(it))) 668 669class PurePythonOrderedDictTests(OrderedDictTests, unittest.TestCase): 670 671 module = py_coll 672 OrderedDict = py_coll.OrderedDict 673 674 675class CPythonBuiltinDictTests(unittest.TestCase): 676 """Builtin dict preserves insertion order. 677 678 Reuse some of tests in OrderedDict selectively. 679 """ 680 681 module = builtins 682 OrderedDict = dict 683 684for method in ( 685 "test_init test_update test_abc test_clear test_delitem " + 686 "test_setitem test_detect_deletion_during_iteration " + 687 "test_popitem test_reinsert test_override_update " + 688 "test_highly_nested test_highly_nested_subclass " + 689 "test_delitem_hash_collision ").split(): 690 setattr(CPythonBuiltinDictTests, method, getattr(OrderedDictTests, method)) 691del method 692 693 694@unittest.skipUnless(c_coll, 'requires the C version of the collections module') 695class CPythonOrderedDictTests(OrderedDictTests, unittest.TestCase): 696 697 module = c_coll 698 OrderedDict = c_coll.OrderedDict 699 check_sizeof = support.check_sizeof 700 701 @support.cpython_only 702 def test_sizeof_exact(self): 703 OrderedDict = self.OrderedDict 704 calcsize = struct.calcsize 705 size = support.calcobjsize 706 check = self.check_sizeof 707 708 basicsize = size('nQ2P' + '3PnPn2P') + calcsize('2nP2n') 709 710 entrysize = calcsize('n2P') 711 p = calcsize('P') 712 nodesize = calcsize('Pn2P') 713 714 od = OrderedDict() 715 check(od, basicsize + 8 + 5*entrysize) # 8byte indices + 8*2//3 * entry table 716 od.x = 1 717 check(od, basicsize + 8 + 5*entrysize) 718 od.update([(i, i) for i in range(3)]) 719 check(od, basicsize + 8*p + 8 + 5*entrysize + 3*nodesize) 720 od.update([(i, i) for i in range(3, 10)]) 721 check(od, basicsize + 16*p + 16 + 10*entrysize + 10*nodesize) 722 723 check(od.keys(), size('P')) 724 check(od.items(), size('P')) 725 check(od.values(), size('P')) 726 727 itersize = size('iP2n2P') 728 check(iter(od), itersize) 729 check(iter(od.keys()), itersize) 730 check(iter(od.items()), itersize) 731 check(iter(od.values()), itersize) 732 733 def test_key_change_during_iteration(self): 734 OrderedDict = self.OrderedDict 735 736 od = OrderedDict.fromkeys('abcde') 737 self.assertEqual(list(od), list('abcde')) 738 with self.assertRaises(RuntimeError): 739 for i, k in enumerate(od): 740 od.move_to_end(k) 741 self.assertLess(i, 5) 742 with self.assertRaises(RuntimeError): 743 for k in od: 744 od['f'] = None 745 with self.assertRaises(RuntimeError): 746 for k in od: 747 del od['c'] 748 self.assertEqual(list(od), list('bdeaf')) 749 750 def test_iterators_pickling(self): 751 OrderedDict = self.OrderedDict 752 pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] 753 od = OrderedDict(pairs) 754 755 for method_name in ('keys', 'values', 'items'): 756 meth = getattr(od, method_name) 757 expected = list(meth())[1:] 758 for i in range(pickle.HIGHEST_PROTOCOL + 1): 759 with self.subTest(method_name=method_name, protocol=i): 760 it = iter(meth()) 761 next(it) 762 p = pickle.dumps(it, i) 763 unpickled = pickle.loads(p) 764 self.assertEqual(list(unpickled), expected) 765 self.assertEqual(list(it), expected) 766 767 @support.cpython_only 768 def test_weakref_list_is_not_traversed(self): 769 # Check that the weakref list is not traversed when collecting 770 # OrderedDict objects. See bpo-39778 for more information. 771 772 gc.collect() 773 774 x = self.OrderedDict() 775 x.cycle = x 776 777 cycle = [] 778 cycle.append(cycle) 779 780 x_ref = weakref.ref(x) 781 cycle.append(x_ref) 782 783 del x, cycle, x_ref 784 785 gc.collect() 786 787 788class PurePythonOrderedDictSubclassTests(PurePythonOrderedDictTests): 789 790 module = py_coll 791 class OrderedDict(py_coll.OrderedDict): 792 pass 793 794 795class CPythonOrderedDictSubclassTests(CPythonOrderedDictTests): 796 797 module = c_coll 798 class OrderedDict(c_coll.OrderedDict): 799 pass 800 801 802class PurePythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): 803 804 @classmethod 805 def setUpClass(cls): 806 cls.type2test = py_coll.OrderedDict 807 808 def test_popitem(self): 809 d = self._empty_mapping() 810 self.assertRaises(KeyError, d.popitem) 811 812 813@unittest.skipUnless(c_coll, 'requires the C version of the collections module') 814class CPythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): 815 816 @classmethod 817 def setUpClass(cls): 818 cls.type2test = c_coll.OrderedDict 819 820 def test_popitem(self): 821 d = self._empty_mapping() 822 self.assertRaises(KeyError, d.popitem) 823 824 825class PurePythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): 826 827 @classmethod 828 def setUpClass(cls): 829 class MyOrderedDict(py_coll.OrderedDict): 830 pass 831 cls.type2test = MyOrderedDict 832 833 def test_popitem(self): 834 d = self._empty_mapping() 835 self.assertRaises(KeyError, d.popitem) 836 837 838@unittest.skipUnless(c_coll, 'requires the C version of the collections module') 839class CPythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): 840 841 @classmethod 842 def setUpClass(cls): 843 class MyOrderedDict(c_coll.OrderedDict): 844 pass 845 cls.type2test = MyOrderedDict 846 847 def test_popitem(self): 848 d = self._empty_mapping() 849 self.assertRaises(KeyError, d.popitem) 850 851 852if __name__ == "__main__": 853 unittest.main() 854