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