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