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        od.x = ['x']
291        od.z = ['z']
292        def check(dup):
293            msg = "\ncopy: %s\nod: %s" % (dup, od)
294            self.assertIsNot(dup, od, msg)
295            self.assertEqual(dup, od)
296            self.assertEqual(list(dup.items()), list(od.items()))
297            self.assertEqual(len(dup), len(od))
298            self.assertEqual(type(dup), type(od))
299        check(od.copy())
300        dup = copy.copy(od)
301        check(dup)
302        self.assertIs(dup.x, od.x)
303        self.assertIs(dup.z, od.z)
304        self.assertFalse(hasattr(dup, 'y'))
305        dup = copy.deepcopy(od)
306        check(dup)
307        self.assertEqual(dup.x, od.x)
308        self.assertIsNot(dup.x, od.x)
309        self.assertEqual(dup.z, od.z)
310        self.assertIsNot(dup.z, od.z)
311        self.assertFalse(hasattr(dup, 'y'))
312        # pickle directly pulls the module, so we have to fake it
313        with replaced_module('collections', self.module):
314            for proto in range(pickle.HIGHEST_PROTOCOL + 1):
315                with self.subTest(proto=proto):
316                    dup = pickle.loads(pickle.dumps(od, proto))
317                    check(dup)
318                    self.assertEqual(dup.x, od.x)
319                    self.assertEqual(dup.z, od.z)
320                    self.assertFalse(hasattr(dup, 'y'))
321        check(eval(repr(od)))
322        update_test = OrderedDict()
323        update_test.update(od)
324        check(update_test)
325        check(OrderedDict(od))
326
327    def test_yaml_linkage(self):
328        OrderedDict = self.OrderedDict
329        # Verify that __reduce__ is setup in a way that supports PyYAML's dump() feature.
330        # In yaml, lists are native but tuples are not.
331        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
332        od = OrderedDict(pairs)
333        # yaml.dump(od) -->
334        # '!!python/object/apply:__main__.OrderedDict\n- - [a, 1]\n  - [b, 2]\n'
335        self.assertTrue(all(type(pair)==list for pair in od.__reduce__()[1]))
336
337    def test_reduce_not_too_fat(self):
338        OrderedDict = self.OrderedDict
339        # do not save instance dictionary if not needed
340        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
341        od = OrderedDict(pairs)
342        self.assertIsInstance(od.__dict__, dict)
343        self.assertIsNone(od.__reduce__()[2])
344        od.x = 10
345        self.assertEqual(od.__dict__['x'], 10)
346        self.assertEqual(od.__reduce__()[2], {'x': 10})
347
348    def test_pickle_recursive(self):
349        OrderedDict = self.OrderedDict
350        od = OrderedDict()
351        od[1] = od
352
353        # pickle directly pulls the module, so we have to fake it
354        with replaced_module('collections', self.module):
355            for proto in range(-1, pickle.HIGHEST_PROTOCOL + 1):
356                dup = pickle.loads(pickle.dumps(od, proto))
357                self.assertIsNot(dup, od)
358                self.assertEqual(list(dup.keys()), [1])
359                self.assertIs(dup[1], dup)
360
361    def test_repr(self):
362        OrderedDict = self.OrderedDict
363        od = OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])
364        self.assertEqual(repr(od),
365            "OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])")
366        self.assertEqual(eval(repr(od)), od)
367        self.assertEqual(repr(OrderedDict()), "OrderedDict()")
368
369    def test_repr_recursive(self):
370        OrderedDict = self.OrderedDict
371        # See issue #9826
372        od = OrderedDict.fromkeys('abc')
373        od['x'] = od
374        self.assertEqual(repr(od),
375            "OrderedDict([('a', None), ('b', None), ('c', None), ('x', ...)])")
376
377    def test_repr_recursive_values(self):
378        OrderedDict = self.OrderedDict
379        od = OrderedDict()
380        od[42] = od.values()
381        r = repr(od)
382        # Cannot perform a stronger test, as the contents of the repr
383        # are implementation-dependent.  All we can say is that we
384        # want a str result, not an exception of any sort.
385        self.assertIsInstance(r, str)
386        od[42] = od.items()
387        r = repr(od)
388        # Again.
389        self.assertIsInstance(r, str)
390
391    def test_setdefault(self):
392        OrderedDict = self.OrderedDict
393        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
394        shuffle(pairs)
395        od = OrderedDict(pairs)
396        pair_order = list(od.items())
397        self.assertEqual(od.setdefault('a', 10), 3)
398        # make sure order didn't change
399        self.assertEqual(list(od.items()), pair_order)
400        self.assertEqual(od.setdefault('x', 10), 10)
401        # make sure 'x' is added to the end
402        self.assertEqual(list(od.items())[-1], ('x', 10))
403        self.assertEqual(od.setdefault('g', default=9), 9)
404
405        # make sure setdefault still works when __missing__ is defined
406        class Missing(OrderedDict):
407            def __missing__(self, key):
408                return 0
409        self.assertEqual(Missing().setdefault(5, 9), 9)
410
411    def test_reinsert(self):
412        OrderedDict = self.OrderedDict
413        # Given insert a, insert b, delete a, re-insert a,
414        # verify that a is now later than b.
415        od = OrderedDict()
416        od['a'] = 1
417        od['b'] = 2
418        del od['a']
419        self.assertEqual(list(od.items()), [('b', 2)])
420        od['a'] = 1
421        self.assertEqual(list(od.items()), [('b', 2), ('a', 1)])
422
423    def test_move_to_end(self):
424        OrderedDict = self.OrderedDict
425        od = OrderedDict.fromkeys('abcde')
426        self.assertEqual(list(od), list('abcde'))
427        od.move_to_end('c')
428        self.assertEqual(list(od), list('abdec'))
429        od.move_to_end('c', False)
430        self.assertEqual(list(od), list('cabde'))
431        od.move_to_end('c', False)
432        self.assertEqual(list(od), list('cabde'))
433        od.move_to_end('e')
434        self.assertEqual(list(od), list('cabde'))
435        od.move_to_end('b', last=False)
436        self.assertEqual(list(od), list('bcade'))
437        with self.assertRaises(KeyError):
438            od.move_to_end('x')
439        with self.assertRaises(KeyError):
440            od.move_to_end('x', False)
441
442    def test_move_to_end_issue25406(self):
443        OrderedDict = self.OrderedDict
444        od = OrderedDict.fromkeys('abc')
445        od.move_to_end('c', last=False)
446        self.assertEqual(list(od), list('cab'))
447        od.move_to_end('a', last=False)
448        self.assertEqual(list(od), list('acb'))
449
450        od = OrderedDict.fromkeys('abc')
451        od.move_to_end('a')
452        self.assertEqual(list(od), list('bca'))
453        od.move_to_end('c')
454        self.assertEqual(list(od), list('bac'))
455
456    def test_sizeof(self):
457        OrderedDict = self.OrderedDict
458        # Wimpy test: Just verify the reported size is larger than a regular dict
459        d = dict(a=1)
460        od = OrderedDict(**d)
461        self.assertGreater(sys.getsizeof(od), sys.getsizeof(d))
462
463    def test_views(self):
464        OrderedDict = self.OrderedDict
465        # See http://bugs.python.org/issue24286
466        s = 'the quick brown fox jumped over a lazy dog yesterday before dawn'.split()
467        od = OrderedDict.fromkeys(s)
468        self.assertEqual(od.keys(), dict(od).keys())
469        self.assertEqual(od.items(), dict(od).items())
470
471    def test_override_update(self):
472        OrderedDict = self.OrderedDict
473        # Verify that subclasses can override update() without breaking __init__()
474        class MyOD(OrderedDict):
475            def update(self, *args, **kwds):
476                raise Exception()
477        items = [('a', 1), ('c', 3), ('b', 2)]
478        self.assertEqual(list(MyOD(items).items()), items)
479
480    def test_highly_nested(self):
481        # Issues 25395 and 35983: test that the trashcan mechanism works
482        # correctly for OrderedDict: deleting a highly nested OrderDict
483        # should not crash Python.
484        OrderedDict = self.OrderedDict
485        obj = None
486        for _ in range(1000):
487            obj = OrderedDict([(None, obj)])
488        del obj
489        support.gc_collect()
490
491    def test_highly_nested_subclass(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        deleted = []
497        class MyOD(OrderedDict):
498            def __del__(self):
499                deleted.append(self.i)
500        obj = None
501        for i in range(100):
502            obj = MyOD([(None, obj)])
503            obj.i = i
504        del obj
505        support.gc_collect()
506        self.assertEqual(deleted, list(reversed(range(100))))
507
508    def test_delitem_hash_collision(self):
509        OrderedDict = self.OrderedDict
510
511        class Key:
512            def __init__(self, hash):
513                self._hash = hash
514                self.value = str(id(self))
515            def __hash__(self):
516                return self._hash
517            def __eq__(self, other):
518                try:
519                    return self.value == other.value
520                except AttributeError:
521                    return False
522            def __repr__(self):
523                return self.value
524
525        def blocking_hash(hash):
526            # See the collision-handling in lookdict (in Objects/dictobject.c).
527            MINSIZE = 8
528            i = (hash & MINSIZE-1)
529            return (i << 2) + i + hash + 1
530
531        COLLIDING = 1
532
533        key = Key(COLLIDING)
534        colliding = Key(COLLIDING)
535        blocking = Key(blocking_hash(COLLIDING))
536
537        od = OrderedDict()
538        od[key] = ...
539        od[blocking] = ...
540        od[colliding] = ...
541        od['after'] = ...
542
543        del od[blocking]
544        del od[colliding]
545        self.assertEqual(list(od.items()), [(key, ...), ('after', ...)])
546
547    def test_issue24347(self):
548        OrderedDict = self.OrderedDict
549
550        class Key:
551            def __hash__(self):
552                return randrange(100000)
553
554        od = OrderedDict()
555        for i in range(100):
556            key = Key()
557            od[key] = i
558
559        # These should not crash.
560        with self.assertRaises(KeyError):
561            list(od.values())
562        with self.assertRaises(KeyError):
563            list(od.items())
564        with self.assertRaises(KeyError):
565            repr(od)
566        with self.assertRaises(KeyError):
567            od.copy()
568
569    def test_issue24348(self):
570        OrderedDict = self.OrderedDict
571
572        class Key:
573            def __hash__(self):
574                return 1
575
576        od = OrderedDict()
577        od[Key()] = 0
578        # This should not crash.
579        od.popitem()
580
581    def test_issue24667(self):
582        """
583        dict resizes after a certain number of insertion operations,
584        whether or not there were deletions that freed up slots in the
585        hash table.  During fast node lookup, OrderedDict must correctly
586        respond to all resizes, even if the current "size" is the same
587        as the old one.  We verify that here by forcing a dict resize
588        on a sparse odict and then perform an operation that should
589        trigger an odict resize (e.g. popitem).  One key aspect here is
590        that we will keep the size of the odict the same at each popitem
591        call.  This verifies that we handled the dict resize properly.
592        """
593        OrderedDict = self.OrderedDict
594
595        od = OrderedDict()
596        for c0 in '0123456789ABCDEF':
597            for c1 in '0123456789ABCDEF':
598                if len(od) == 4:
599                    # This should not raise a KeyError.
600                    od.popitem(last=False)
601                key = c0 + c1
602                od[key] = key
603
604    # Direct use of dict methods
605
606    def test_dict_setitem(self):
607        OrderedDict = self.OrderedDict
608        od = OrderedDict()
609        dict.__setitem__(od, 'spam', 1)
610        self.assertNotIn('NULL', repr(od))
611
612    def test_dict_delitem(self):
613        OrderedDict = self.OrderedDict
614        od = OrderedDict()
615        od['spam'] = 1
616        od['ham'] = 2
617        dict.__delitem__(od, 'spam')
618        with self.assertRaises(KeyError):
619            repr(od)
620
621    def test_dict_clear(self):
622        OrderedDict = self.OrderedDict
623        od = OrderedDict()
624        od['spam'] = 1
625        od['ham'] = 2
626        dict.clear(od)
627        self.assertNotIn('NULL', repr(od))
628
629    def test_dict_pop(self):
630        OrderedDict = self.OrderedDict
631        od = OrderedDict()
632        od['spam'] = 1
633        od['ham'] = 2
634        dict.pop(od, 'spam')
635        with self.assertRaises(KeyError):
636            repr(od)
637
638    def test_dict_popitem(self):
639        OrderedDict = self.OrderedDict
640        od = OrderedDict()
641        od['spam'] = 1
642        od['ham'] = 2
643        dict.popitem(od)
644        with self.assertRaises(KeyError):
645            repr(od)
646
647    def test_dict_setdefault(self):
648        OrderedDict = self.OrderedDict
649        od = OrderedDict()
650        dict.setdefault(od, 'spam', 1)
651        self.assertNotIn('NULL', repr(od))
652
653    def test_dict_update(self):
654        OrderedDict = self.OrderedDict
655        od = OrderedDict()
656        dict.update(od, [('spam', 1)])
657        self.assertNotIn('NULL', repr(od))
658
659    def test_reference_loop(self):
660        # Issue 25935
661        OrderedDict = self.OrderedDict
662        class A:
663            od = OrderedDict()
664        A.od[A] = None
665        r = weakref.ref(A)
666        del A
667        gc.collect()
668        self.assertIsNone(r())
669
670    def test_free_after_iterating(self):
671        support.check_free_after_iterating(self, iter, self.OrderedDict)
672        support.check_free_after_iterating(self, lambda d: iter(d.keys()), self.OrderedDict)
673        support.check_free_after_iterating(self, lambda d: iter(d.values()), self.OrderedDict)
674        support.check_free_after_iterating(self, lambda d: iter(d.items()), self.OrderedDict)
675
676    def test_merge_operator(self):
677        OrderedDict = self.OrderedDict
678
679        a = OrderedDict({0: 0, 1: 1, 2: 1})
680        b = OrderedDict({1: 1, 2: 2, 3: 3})
681
682        c = a.copy()
683        d = a.copy()
684        c |= b
685        d |= list(b.items())
686        expected = OrderedDict({0: 0, 1: 1, 2: 2, 3: 3})
687        self.assertEqual(a | dict(b), expected)
688        self.assertEqual(a | b, expected)
689        self.assertEqual(c, expected)
690        self.assertEqual(d, expected)
691
692        c = b.copy()
693        c |= a
694        expected = OrderedDict({1: 1, 2: 1, 3: 3, 0: 0})
695        self.assertEqual(dict(b) | a, expected)
696        self.assertEqual(b | a, expected)
697        self.assertEqual(c, expected)
698
699        self.assertIs(type(a | b), OrderedDict)
700        self.assertIs(type(dict(a) | b), OrderedDict)
701        self.assertIs(type(a | dict(b)), OrderedDict)
702
703        expected = a.copy()
704        a |= ()
705        a |= ""
706        self.assertEqual(a, expected)
707
708        with self.assertRaises(TypeError):
709            a | None
710        with self.assertRaises(TypeError):
711            a | ()
712        with self.assertRaises(TypeError):
713            a | "BAD"
714        with self.assertRaises(TypeError):
715            a | ""
716        with self.assertRaises(ValueError):
717            a |= "BAD"
718
719    @support.cpython_only
720    def test_ordered_dict_items_result_gc(self):
721        # bpo-42536: OrderedDict.items's tuple-reuse speed trick breaks the GC's
722        # assumptions about what can be untracked. Make sure we re-track result
723        # tuples whenever we reuse them.
724        it = iter(self.OrderedDict({None: []}).items())
725        gc.collect()
726        # That GC collection probably untracked the recycled internal result
727        # tuple, which is initialized to (None, None). Make sure it's re-tracked
728        # when it's mutated and returned from __next__:
729        self.assertTrue(gc.is_tracked(next(it)))
730
731class PurePythonOrderedDictTests(OrderedDictTests, unittest.TestCase):
732
733    module = py_coll
734    OrderedDict = py_coll.OrderedDict
735
736
737class CPythonBuiltinDictTests(unittest.TestCase):
738    """Builtin dict preserves insertion order.
739
740    Reuse some of tests in OrderedDict selectively.
741    """
742
743    module = builtins
744    OrderedDict = dict
745
746for method in (
747    "test_init test_update test_abc test_clear test_delitem " +
748    "test_setitem test_detect_deletion_during_iteration " +
749    "test_popitem test_reinsert test_override_update " +
750    "test_highly_nested test_highly_nested_subclass " +
751    "test_delitem_hash_collision ").split():
752    setattr(CPythonBuiltinDictTests, method, getattr(OrderedDictTests, method))
753del method
754
755
756@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
757class CPythonOrderedDictTests(OrderedDictTests, unittest.TestCase):
758
759    module = c_coll
760    OrderedDict = c_coll.OrderedDict
761    check_sizeof = support.check_sizeof
762
763    @support.cpython_only
764    def test_sizeof_exact(self):
765        OrderedDict = self.OrderedDict
766        calcsize = struct.calcsize
767        size = support.calcobjsize
768        check = self.check_sizeof
769
770        basicsize = size('nQ2P' + '3PnPn2P')
771        keysize = calcsize('n2BI2n')
772
773        entrysize = calcsize('n2P')
774        p = calcsize('P')
775        nodesize = calcsize('Pn2P')
776
777        od = OrderedDict()
778        check(od, basicsize)  # 8byte indices + 8*2//3 * entry table
779        od.x = 1
780        check(od, basicsize)
781        od.update([(i, i) for i in range(3)])
782        check(od, basicsize + keysize + 8*p + 8 + 5*entrysize + 3*nodesize)
783        od.update([(i, i) for i in range(3, 10)])
784        check(od, basicsize + keysize + 16*p + 16 + 10*entrysize + 10*nodesize)
785
786        check(od.keys(), size('P'))
787        check(od.items(), size('P'))
788        check(od.values(), size('P'))
789
790        itersize = size('iP2n2P')
791        check(iter(od), itersize)
792        check(iter(od.keys()), itersize)
793        check(iter(od.items()), itersize)
794        check(iter(od.values()), itersize)
795
796    def test_key_change_during_iteration(self):
797        OrderedDict = self.OrderedDict
798
799        od = OrderedDict.fromkeys('abcde')
800        self.assertEqual(list(od), list('abcde'))
801        with self.assertRaises(RuntimeError):
802            for i, k in enumerate(od):
803                od.move_to_end(k)
804                self.assertLess(i, 5)
805        with self.assertRaises(RuntimeError):
806            for k in od:
807                od['f'] = None
808        with self.assertRaises(RuntimeError):
809            for k in od:
810                del od['c']
811        self.assertEqual(list(od), list('bdeaf'))
812
813    def test_iterators_pickling(self):
814        OrderedDict = self.OrderedDict
815        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
816        od = OrderedDict(pairs)
817
818        for method_name in ('keys', 'values', 'items'):
819            meth = getattr(od, method_name)
820            expected = list(meth())[1:]
821            for i in range(pickle.HIGHEST_PROTOCOL + 1):
822                with self.subTest(method_name=method_name, protocol=i):
823                    it = iter(meth())
824                    next(it)
825                    p = pickle.dumps(it, i)
826                    unpickled = pickle.loads(p)
827                    self.assertEqual(list(unpickled), expected)
828                    self.assertEqual(list(it), expected)
829
830    @support.cpython_only
831    def test_weakref_list_is_not_traversed(self):
832        # Check that the weakref list is not traversed when collecting
833        # OrderedDict objects. See bpo-39778 for more information.
834
835        gc.collect()
836
837        x = self.OrderedDict()
838        x.cycle = x
839
840        cycle = []
841        cycle.append(cycle)
842
843        x_ref = weakref.ref(x)
844        cycle.append(x_ref)
845
846        del x, cycle, x_ref
847
848        gc.collect()
849
850
851class PurePythonOrderedDictSubclassTests(PurePythonOrderedDictTests):
852
853    module = py_coll
854    class OrderedDict(py_coll.OrderedDict):
855        pass
856
857
858class CPythonOrderedDictSubclassTests(CPythonOrderedDictTests):
859
860    module = c_coll
861    class OrderedDict(c_coll.OrderedDict):
862        pass
863
864
865class PurePythonOrderedDictWithSlotsCopyingTests(unittest.TestCase):
866
867    module = py_coll
868    class OrderedDict(py_coll.OrderedDict):
869        __slots__ = ('x', 'y')
870    test_copying = OrderedDictTests.test_copying
871
872
873@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
874class CPythonOrderedDictWithSlotsCopyingTests(unittest.TestCase):
875
876    module = c_coll
877    class OrderedDict(c_coll.OrderedDict):
878        __slots__ = ('x', 'y')
879    test_copying = OrderedDictTests.test_copying
880
881
882class PurePythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
883
884    @classmethod
885    def setUpClass(cls):
886        cls.type2test = py_coll.OrderedDict
887
888    def test_popitem(self):
889        d = self._empty_mapping()
890        self.assertRaises(KeyError, d.popitem)
891
892
893@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
894class CPythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
895
896    @classmethod
897    def setUpClass(cls):
898        cls.type2test = c_coll.OrderedDict
899
900    def test_popitem(self):
901        d = self._empty_mapping()
902        self.assertRaises(KeyError, d.popitem)
903
904
905class PurePythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
906
907    @classmethod
908    def setUpClass(cls):
909        class MyOrderedDict(py_coll.OrderedDict):
910            pass
911        cls.type2test = MyOrderedDict
912
913    def test_popitem(self):
914        d = self._empty_mapping()
915        self.assertRaises(KeyError, d.popitem)
916
917
918@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
919class CPythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
920
921    @classmethod
922    def setUpClass(cls):
923        class MyOrderedDict(c_coll.OrderedDict):
924            pass
925        cls.type2test = MyOrderedDict
926
927    def test_popitem(self):
928        d = self._empty_mapping()
929        self.assertRaises(KeyError, d.popitem)
930
931
932class SimpleLRUCache:
933
934    def __init__(self, size):
935        super().__init__()
936        self.size = size
937        self.counts = dict.fromkeys(('get', 'set', 'del'), 0)
938
939    def __getitem__(self, item):
940        self.counts['get'] += 1
941        value = super().__getitem__(item)
942        self.move_to_end(item)
943        return value
944
945    def __setitem__(self, key, value):
946        self.counts['set'] += 1
947        while key not in self and len(self) >= self.size:
948            self.popitem(last=False)
949        super().__setitem__(key, value)
950        self.move_to_end(key)
951
952    def __delitem__(self, key):
953        self.counts['del'] += 1
954        super().__delitem__(key)
955
956
957class SimpleLRUCacheTests:
958
959    def test_add_after_full(self):
960        c = self.type2test(2)
961        c['t1'] = 1
962        c['t2'] = 2
963        c['t3'] = 3
964        self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
965        self.assertEqual(list(c), ['t2', 't3'])
966        self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
967
968    def test_popitem(self):
969        c = self.type2test(3)
970        for i in range(1, 4):
971            c[i] = i
972        self.assertEqual(c.popitem(last=False), (1, 1))
973        self.assertEqual(c.popitem(last=True), (3, 3))
974        self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
975
976    def test_pop(self):
977        c = self.type2test(3)
978        for i in range(1, 4):
979            c[i] = i
980        self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
981        self.assertEqual(c.pop(2), 2)
982        self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
983        self.assertEqual(c.pop(4, 0), 0)
984        self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
985        self.assertRaises(KeyError, c.pop, 4)
986        self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
987
988    def test_change_order_on_get(self):
989        c = self.type2test(3)
990        for i in range(1, 4):
991            c[i] = i
992        self.assertEqual(list(c), list(range(1, 4)))
993        self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
994        self.assertEqual(c[2], 2)
995        self.assertEqual(c.counts, {'get': 1, 'set': 3, 'del': 0})
996        self.assertEqual(list(c), [1, 3, 2])
997
998
999class PySimpleLRUCacheTests(SimpleLRUCacheTests, unittest.TestCase):
1000
1001    class type2test(SimpleLRUCache, py_coll.OrderedDict):
1002        pass
1003
1004
1005@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
1006class CSimpleLRUCacheTests(SimpleLRUCacheTests, unittest.TestCase):
1007
1008    @classmethod
1009    def setUpClass(cls):
1010        class type2test(SimpleLRUCache, c_coll.OrderedDict):
1011            pass
1012        cls.type2test = type2test
1013
1014
1015if __name__ == "__main__":
1016    unittest.main()
1017