Debian Codegraph @

Lib/test/test_ordered_dict.py

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