1# tests common to dict and UserDict
2import unittest
3import UserDict
4import test_support
5import sys
6
7
8class BasicTestMappingProtocol(unittest.TestCase):
9    # This base class can be used to check that an object conforms to the
10    # mapping protocol
11
12    # Functions that can be useful to override to adapt to dictionary
13    # semantics
14    type2test = None # which class is being tested (overwrite in subclasses)
15
16    def _reference(self):
17        """Return a dictionary of values which are invariant by storage
18        in the object under test."""
19        return {1:2, "key1":"value1", "key2":(1,2,3)}
20    def _empty_mapping(self):
21        """Return an empty mapping object"""
22        return self.type2test()
23    def _full_mapping(self, data):
24        """Return a mapping object with the value contained in data
25        dictionary"""
26        x = self._empty_mapping()
27        for key, value in data.items():
28            x[key] = value
29        return x
30
31    def __init__(self, *args, **kw):
32        unittest.TestCase.__init__(self, *args, **kw)
33        self.reference = self._reference().copy()
34
35        # A (key, value) pair not in the mapping
36        key, value = self.reference.popitem()
37        self.other = {key:value}
38
39        # A (key, value) pair in the mapping
40        key, value = self.reference.popitem()
41        self.inmapping = {key:value}
42        self.reference[key] = value
43
44    def test_read(self):
45        # Test for read only operations on mapping
46        p = self._empty_mapping()
47        p1 = dict(p) #workaround for singleton objects
48        d = self._full_mapping(self.reference)
49        if d is p:
50            p = p1
51        #Indexing
52        for key, value in self.reference.items():
53            self.assertEqual(d[key], value)
54        knownkey = self.other.keys()[0]
55        self.assertRaises(KeyError, lambda:d[knownkey])
56        #len
57        self.assertEqual(len(p), 0)
58        self.assertEqual(len(d), len(self.reference))
59        #in
60        for k in self.reference:
61            self.assertIn(k, d)
62        for k in self.other:
63            self.assertNotIn(k, d)
64        #has_key
65        with test_support.check_py3k_warnings(quiet=True):
66            for k in self.reference:
67                self.assertTrue(d.has_key(k))
68            for k in self.other:
69                self.assertFalse(d.has_key(k))
70        #cmp
71        self.assertEqual(cmp(p,p), 0)
72        self.assertEqual(cmp(d,d), 0)
73        self.assertEqual(cmp(p,d), -1)
74        self.assertEqual(cmp(d,p), 1)
75        #__non__zero__
76        if p: self.fail("Empty mapping must compare to False")
77        if not d: self.fail("Full mapping must compare to True")
78        # keys(), items(), iterkeys() ...
79        def check_iterandlist(iter, lst, ref):
80            self.assertTrue(hasattr(iter, 'next'))
81            self.assertTrue(hasattr(iter, '__iter__'))
82            x = list(iter)
83            self.assertTrue(set(x)==set(lst)==set(ref))
84        check_iterandlist(d.iterkeys(), d.keys(), self.reference.keys())
85        check_iterandlist(iter(d), d.keys(), self.reference.keys())
86        check_iterandlist(d.itervalues(), d.values(), self.reference.values())
87        check_iterandlist(d.iteritems(), d.items(), self.reference.items())
88        #get
89        key, value = d.iteritems().next()
90        knownkey, knownvalue = self.other.iteritems().next()
91        self.assertEqual(d.get(key, knownvalue), value)
92        self.assertEqual(d.get(knownkey, knownvalue), knownvalue)
93        self.assertNotIn(knownkey, d)
94
95    def test_write(self):
96        # Test for write operations on mapping
97        p = self._empty_mapping()
98        #Indexing
99        for key, value in self.reference.items():
100            p[key] = value
101            self.assertEqual(p[key], value)
102        for key in self.reference.keys():
103            del p[key]
104            self.assertRaises(KeyError, lambda:p[key])
105        p = self._empty_mapping()
106        #update
107        p.update(self.reference)
108        self.assertEqual(dict(p), self.reference)
109        items = p.items()
110        p = self._empty_mapping()
111        p.update(items)
112        self.assertEqual(dict(p), self.reference)
113        d = self._full_mapping(self.reference)
114        #setdefault
115        key, value = d.iteritems().next()
116        knownkey, knownvalue = self.other.iteritems().next()
117        self.assertEqual(d.setdefault(key, knownvalue), value)
118        self.assertEqual(d[key], value)
119        self.assertEqual(d.setdefault(knownkey, knownvalue), knownvalue)
120        self.assertEqual(d[knownkey], knownvalue)
121        #pop
122        self.assertEqual(d.pop(knownkey), knownvalue)
123        self.assertNotIn(knownkey, d)
124        self.assertRaises(KeyError, d.pop, knownkey)
125        default = 909
126        d[knownkey] = knownvalue
127        self.assertEqual(d.pop(knownkey, default), knownvalue)
128        self.assertNotIn(knownkey, d)
129        self.assertEqual(d.pop(knownkey, default), default)
130        #popitem
131        key, value = d.popitem()
132        self.assertNotIn(key, d)
133        self.assertEqual(value, self.reference[key])
134        p=self._empty_mapping()
135        self.assertRaises(KeyError, p.popitem)
136
137    def test_constructor(self):
138        self.assertEqual(self._empty_mapping(), self._empty_mapping())
139
140    def test_bool(self):
141        self.assertTrue(not self._empty_mapping())
142        self.assertTrue(self.reference)
143        self.assertTrue(bool(self._empty_mapping()) is False)
144        self.assertTrue(bool(self.reference) is True)
145
146    def test_keys(self):
147        d = self._empty_mapping()
148        self.assertEqual(d.keys(), [])
149        d = self.reference
150        self.assertIn(self.inmapping.keys()[0], d.keys())
151        self.assertNotIn(self.other.keys()[0], d.keys())
152        self.assertRaises(TypeError, d.keys, None)
153
154    def test_values(self):
155        d = self._empty_mapping()
156        self.assertEqual(d.values(), [])
157
158        self.assertRaises(TypeError, d.values, None)
159
160    def test_items(self):
161        d = self._empty_mapping()
162        self.assertEqual(d.items(), [])
163
164        self.assertRaises(TypeError, d.items, None)
165
166    def test_len(self):
167        d = self._empty_mapping()
168        self.assertEqual(len(d), 0)
169
170    def test_getitem(self):
171        d = self.reference
172        self.assertEqual(d[self.inmapping.keys()[0]], self.inmapping.values()[0])
173
174        self.assertRaises(TypeError, d.__getitem__)
175
176    def test_update(self):
177        # mapping argument
178        d = self._empty_mapping()
179        d.update(self.other)
180        self.assertEqual(d.items(), self.other.items())
181
182        # No argument
183        d = self._empty_mapping()
184        d.update()
185        self.assertEqual(d, self._empty_mapping())
186
187        # item sequence
188        d = self._empty_mapping()
189        d.update(self.other.items())
190        self.assertEqual(d.items(), self.other.items())
191
192        # Iterator
193        d = self._empty_mapping()
194        d.update(self.other.iteritems())
195        self.assertEqual(d.items(), self.other.items())
196
197        # FIXME: Doesn't work with UserDict
198        # self.assertRaises((TypeError, AttributeError), d.update, None)
199        self.assertRaises((TypeError, AttributeError), d.update, 42)
200
201        outerself = self
202        class SimpleUserDict:
203            def __init__(self):
204                self.d = outerself.reference
205            def keys(self):
206                return self.d.keys()
207            def __getitem__(self, i):
208                return self.d[i]
209        d.clear()
210        d.update(SimpleUserDict())
211        i1 = d.items()
212        i2 = self.reference.items()
213
214        def safe_sort_key(kv):
215            k, v = kv
216            return id(type(k)), id(type(v)), k, v
217        i1.sort(key=safe_sort_key)
218        i2.sort(key=safe_sort_key)
219        self.assertEqual(i1, i2)
220
221        class Exc(Exception): pass
222
223        d = self._empty_mapping()
224        class FailingUserDict:
225            def keys(self):
226                raise Exc
227        self.assertRaises(Exc, d.update, FailingUserDict())
228
229        d.clear()
230
231        class FailingUserDict:
232            def keys(self):
233                class BogonIter:
234                    def __init__(self):
235                        self.i = 1
236                    def __iter__(self):
237                        return self
238                    def next(self):
239                        if self.i:
240                            self.i = 0
241                            return 'a'
242                        raise Exc
243                return BogonIter()
244            def __getitem__(self, key):
245                return key
246        self.assertRaises(Exc, d.update, FailingUserDict())
247
248        class FailingUserDict:
249            def keys(self):
250                class BogonIter:
251                    def __init__(self):
252                        self.i = ord('a')
253                    def __iter__(self):
254                        return self
255                    def next(self):
256                        if self.i <= ord('z'):
257                            rtn = chr(self.i)
258                            self.i += 1
259                            return rtn
260                        raise StopIteration
261                return BogonIter()
262            def __getitem__(self, key):
263                raise Exc
264        self.assertRaises(Exc, d.update, FailingUserDict())
265
266        d = self._empty_mapping()
267        class badseq(object):
268            def __iter__(self):
269                return self
270            def next(self):
271                raise Exc()
272
273        self.assertRaises(Exc, d.update, badseq())
274
275        self.assertRaises(ValueError, d.update, [(1, 2, 3)])
276
277    # no test_fromkeys or test_copy as both os.environ and selves don't support it
278
279    def test_get(self):
280        d = self._empty_mapping()
281        self.assertTrue(d.get(self.other.keys()[0]) is None)
282        self.assertEqual(d.get(self.other.keys()[0], 3), 3)
283        d = self.reference
284        self.assertTrue(d.get(self.other.keys()[0]) is None)
285        self.assertEqual(d.get(self.other.keys()[0], 3), 3)
286        self.assertEqual(d.get(self.inmapping.keys()[0]), self.inmapping.values()[0])
287        self.assertEqual(d.get(self.inmapping.keys()[0], 3), self.inmapping.values()[0])
288        self.assertRaises(TypeError, d.get)
289        self.assertRaises(TypeError, d.get, None, None, None)
290
291    def test_setdefault(self):
292        d = self._empty_mapping()
293        self.assertRaises(TypeError, d.setdefault)
294
295    def test_popitem(self):
296        d = self._empty_mapping()
297        self.assertRaises(KeyError, d.popitem)
298        self.assertRaises(TypeError, d.popitem, 42)
299
300    def test_pop(self):
301        d = self._empty_mapping()
302        k, v = self.inmapping.items()[0]
303        d[k] = v
304        self.assertRaises(KeyError, d.pop, self.other.keys()[0])
305
306        self.assertEqual(d.pop(k), v)
307        self.assertEqual(len(d), 0)
308
309        self.assertRaises(KeyError, d.pop, k)
310
311
312class TestMappingProtocol(BasicTestMappingProtocol):
313    def test_constructor(self):
314        BasicTestMappingProtocol.test_constructor(self)
315        self.assertTrue(self._empty_mapping() is not self._empty_mapping())
316        self.assertEqual(self.type2test(x=1, y=2), {"x": 1, "y": 2})
317
318    def test_bool(self):
319        BasicTestMappingProtocol.test_bool(self)
320        self.assertTrue(not self._empty_mapping())
321        self.assertTrue(self._full_mapping({"x": "y"}))
322        self.assertTrue(bool(self._empty_mapping()) is False)
323        self.assertTrue(bool(self._full_mapping({"x": "y"})) is True)
324
325    def test_keys(self):
326        BasicTestMappingProtocol.test_keys(self)
327        d = self._empty_mapping()
328        self.assertEqual(d.keys(), [])
329        d = self._full_mapping({'a': 1, 'b': 2})
330        k = d.keys()
331        self.assertIn('a', k)
332        self.assertIn('b', k)
333        self.assertNotIn('c', k)
334
335    def test_values(self):
336        BasicTestMappingProtocol.test_values(self)
337        d = self._full_mapping({1:2})
338        self.assertEqual(d.values(), [2])
339
340    def test_items(self):
341        BasicTestMappingProtocol.test_items(self)
342
343        d = self._full_mapping({1:2})
344        self.assertEqual(d.items(), [(1, 2)])
345
346    def test_has_key(self):
347        d = self._empty_mapping()
348        self.assertTrue(not d.has_key('a'))
349        d = self._full_mapping({'a': 1, 'b': 2})
350        k = d.keys()
351        k.sort(key=lambda k: (id(type(k)), k))
352        self.assertEqual(k, ['a', 'b'])
353
354        self.assertRaises(TypeError, d.has_key)
355
356    def test_contains(self):
357        d = self._empty_mapping()
358        self.assertNotIn('a', d)
359        self.assertTrue(not ('a' in d))
360        self.assertTrue('a' not in d)
361        d = self._full_mapping({'a': 1, 'b': 2})
362        self.assertIn('a', d)
363        self.assertIn('b', d)
364        self.assertNotIn('c', d)
365
366        self.assertRaises(TypeError, d.__contains__)
367
368    def test_len(self):
369        BasicTestMappingProtocol.test_len(self)
370        d = self._full_mapping({'a': 1, 'b': 2})
371        self.assertEqual(len(d), 2)
372
373    def test_getitem(self):
374        BasicTestMappingProtocol.test_getitem(self)
375        d = self._full_mapping({'a': 1, 'b': 2})
376        self.assertEqual(d['a'], 1)
377        self.assertEqual(d['b'], 2)
378        d['c'] = 3
379        d['a'] = 4
380        self.assertEqual(d['c'], 3)
381        self.assertEqual(d['a'], 4)
382        del d['b']
383        self.assertEqual(d, {'a': 4, 'c': 3})
384
385        self.assertRaises(TypeError, d.__getitem__)
386
387    def test_clear(self):
388        d = self._full_mapping({1:1, 2:2, 3:3})
389        d.clear()
390        self.assertEqual(d, {})
391
392        self.assertRaises(TypeError, d.clear, None)
393
394    def test_update(self):
395        BasicTestMappingProtocol.test_update(self)
396        # mapping argument
397        d = self._empty_mapping()
398        d.update({1:100})
399        d.update({2:20})
400        d.update({1:1, 2:2, 3:3})
401        self.assertEqual(d, {1:1, 2:2, 3:3})
402
403        # no argument
404        d.update()
405        self.assertEqual(d, {1:1, 2:2, 3:3})
406
407        # keyword arguments
408        d = self._empty_mapping()
409        d.update(x=100)
410        d.update(y=20)
411        d.update(x=1, y=2, z=3)
412        self.assertEqual(d, {"x":1, "y":2, "z":3})
413
414        # item sequence
415        d = self._empty_mapping()
416        d.update([("x", 100), ("y", 20)])
417        self.assertEqual(d, {"x":100, "y":20})
418
419        # Both item sequence and keyword arguments
420        d = self._empty_mapping()
421        d.update([("x", 100), ("y", 20)], x=1, y=2)
422        self.assertEqual(d, {"x":1, "y":2})
423
424        # iterator
425        d = self._full_mapping({1:3, 2:4})
426        d.update(self._full_mapping({1:2, 3:4, 5:6}).iteritems())
427        self.assertEqual(d, {1:2, 2:4, 3:4, 5:6})
428
429        class SimpleUserDict:
430            def __init__(self):
431                self.d = {1:1, 2:2, 3:3}
432            def keys(self):
433                return self.d.keys()
434            def __getitem__(self, i):
435                return self.d[i]
436        d.clear()
437        d.update(SimpleUserDict())
438        self.assertEqual(d, {1:1, 2:2, 3:3})
439
440    def test_fromkeys(self):
441        self.assertEqual(self.type2test.fromkeys('abc'), {'a':None, 'b':None, 'c':None})
442        d = self._empty_mapping()
443        self.assertTrue(not(d.fromkeys('abc') is d))
444        self.assertEqual(d.fromkeys('abc'), {'a':None, 'b':None, 'c':None})
445        self.assertEqual(d.fromkeys((4,5),0), {4:0, 5:0})
446        self.assertEqual(d.fromkeys([]), {})
447        def g():
448            yield 1
449        self.assertEqual(d.fromkeys(g()), {1:None})
450        self.assertRaises(TypeError, {}.fromkeys, 3)
451        class dictlike(self.type2test): pass
452        self.assertEqual(dictlike.fromkeys('a'), {'a':None})
453        self.assertEqual(dictlike().fromkeys('a'), {'a':None})
454        self.assertTrue(dictlike.fromkeys('a').__class__ is dictlike)
455        self.assertTrue(dictlike().fromkeys('a').__class__ is dictlike)
456        # FIXME: the following won't work with UserDict, because it's an old style class
457        # self.assertTrue(type(dictlike.fromkeys('a')) is dictlike)
458        class mydict(self.type2test):
459            def __new__(cls):
460                return UserDict.UserDict()
461        ud = mydict.fromkeys('ab')
462        self.assertEqual(ud, {'a':None, 'b':None})
463        # FIXME: the following won't work with UserDict, because it's an old style class
464        # self.assertIsInstance(ud, UserDict.UserDict)
465        self.assertRaises(TypeError, dict.fromkeys)
466
467        class Exc(Exception): pass
468
469        class baddict1(self.type2test):
470            def __init__(self):
471                raise Exc()
472
473        self.assertRaises(Exc, baddict1.fromkeys, [1])
474
475        class BadSeq(object):
476            def __iter__(self):
477                return self
478            def next(self):
479                raise Exc()
480
481        self.assertRaises(Exc, self.type2test.fromkeys, BadSeq())
482
483        class baddict2(self.type2test):
484            def __setitem__(self, key, value):
485                raise Exc()
486
487        self.assertRaises(Exc, baddict2.fromkeys, [1])
488
489    def test_copy(self):
490        d = self._full_mapping({1:1, 2:2, 3:3})
491        self.assertEqual(d.copy(), {1:1, 2:2, 3:3})
492        d = self._empty_mapping()
493        self.assertEqual(d.copy(), d)
494        self.assertIsInstance(d.copy(), d.__class__)
495        self.assertRaises(TypeError, d.copy, None)
496
497    def test_get(self):
498        BasicTestMappingProtocol.test_get(self)
499        d = self._empty_mapping()
500        self.assertTrue(d.get('c') is None)
501        self.assertEqual(d.get('c', 3), 3)
502        d = self._full_mapping({'a' : 1, 'b' : 2})
503        self.assertTrue(d.get('c') is None)
504        self.assertEqual(d.get('c', 3), 3)
505        self.assertEqual(d.get('a'), 1)
506        self.assertEqual(d.get('a', 3), 1)
507
508    def test_setdefault(self):
509        BasicTestMappingProtocol.test_setdefault(self)
510        d = self._empty_mapping()
511        self.assertTrue(d.setdefault('key0') is None)
512        d.setdefault('key0', [])
513        self.assertTrue(d.setdefault('key0') is None)
514        d.setdefault('key', []).append(3)
515        self.assertEqual(d['key'][0], 3)
516        d.setdefault('key', []).append(4)
517        self.assertEqual(len(d['key']), 2)
518
519    def test_popitem(self):
520        BasicTestMappingProtocol.test_popitem(self)
521        for copymode in -1, +1:
522            # -1: b has same structure as a
523            # +1: b is a.copy()
524            for log2size in range(12):
525                size = 2**log2size
526                a = self._empty_mapping()
527                b = self._empty_mapping()
528                for i in range(size):
529                    a[repr(i)] = i
530                    if copymode < 0:
531                        b[repr(i)] = i
532                if copymode > 0:
533                    b = a.copy()
534                for i in range(size):
535                    ka, va = ta = a.popitem()
536                    self.assertEqual(va, int(ka))
537                    kb, vb = tb = b.popitem()
538                    self.assertEqual(vb, int(kb))
539                    self.assertTrue(not(copymode < 0 and ta != tb))
540                self.assertTrue(not a)
541                self.assertTrue(not b)
542
543    def test_pop(self):
544        BasicTestMappingProtocol.test_pop(self)
545
546        # Tests for pop with specified key
547        d = self._empty_mapping()
548        k, v = 'abc', 'def'
549
550        # verify longs/ints get same value when key > 32 bits (for 64-bit archs)
551        # see SF bug #689659
552        x = 4503599627370496L
553        y = 4503599627370496
554        h = self._full_mapping({x: 'anything', y: 'something else'})
555        self.assertEqual(h[x], h[y])
556
557        self.assertEqual(d.pop(k, v), v)
558        d[k] = v
559        self.assertEqual(d.pop(k, 1), v)
560
561
562class TestHashMappingProtocol(TestMappingProtocol):
563
564    def test_getitem(self):
565        TestMappingProtocol.test_getitem(self)
566        class Exc(Exception): pass
567
568        class BadEq(object):
569            def __eq__(self, other):
570                raise Exc()
571            def __hash__(self):
572                return 24
573
574        d = self._empty_mapping()
575        d[BadEq()] = 42
576        self.assertRaises(KeyError, d.__getitem__, 23)
577
578        class BadHash(object):
579            fail = False
580            def __hash__(self):
581                if self.fail:
582                    raise Exc()
583                else:
584                    return 42
585
586        d = self._empty_mapping()
587        x = BadHash()
588        d[x] = 42
589        x.fail = True
590        self.assertRaises(Exc, d.__getitem__, x)
591
592    def test_fromkeys(self):
593        TestMappingProtocol.test_fromkeys(self)
594        class mydict(self.type2test):
595            def __new__(cls):
596                return UserDict.UserDict()
597        ud = mydict.fromkeys('ab')
598        self.assertEqual(ud, {'a':None, 'b':None})
599        self.assertIsInstance(ud, UserDict.UserDict)
600
601    def test_pop(self):
602        TestMappingProtocol.test_pop(self)
603
604        class Exc(Exception): pass
605
606        class BadHash(object):
607            fail = False
608            def __hash__(self):
609                if self.fail:
610                    raise Exc()
611                else:
612                    return 42
613
614        d = self._empty_mapping()
615        x = BadHash()
616        d[x] = 42
617        x.fail = True
618        self.assertRaises(Exc, d.pop, x)
619
620    def test_mutatingiteration(self):
621        d = self._empty_mapping()
622        d[1] = 1
623        try:
624            for i in d:
625                d[i+1] = 1
626        except RuntimeError:
627            pass
628        else:
629            self.fail("changing dict size during iteration doesn't raise Error")
630
631    def test_repr(self):
632        d = self._empty_mapping()
633        self.assertEqual(repr(d), '{}')
634        d[1] = 2
635        self.assertEqual(repr(d), '{1: 2}')
636        d = self._empty_mapping()
637        d[1] = d
638        self.assertEqual(repr(d), '{1: {...}}')
639
640        class Exc(Exception): pass
641
642        class BadRepr(object):
643            def __repr__(self):
644                raise Exc()
645
646        d = self._full_mapping({1: BadRepr()})
647        self.assertRaises(Exc, repr, d)
648
649    def test_repr_deep(self):
650        d = self._empty_mapping()
651        for i in range(sys.getrecursionlimit() + 100):
652            d0 = d
653            d = self._empty_mapping()
654            d[1] = d0
655        self.assertRaises(RuntimeError, repr, d)
656
657    def test_le(self):
658        self.assertTrue(not (self._empty_mapping() < self._empty_mapping()))
659        self.assertTrue(not (self._full_mapping({1: 2}) < self._full_mapping({1L: 2L})))
660
661        class Exc(Exception): pass
662
663        class BadCmp(object):
664            def __eq__(self, other):
665                raise Exc()
666            def __hash__(self):
667                return 42
668
669        d1 = self._full_mapping({BadCmp(): 1})
670        d2 = self._full_mapping({1: 1})
671        try:
672            d1 < d2
673        except Exc:
674            pass
675        else:
676            self.fail("< didn't raise Exc")
677
678    def test_setdefault(self):
679        TestMappingProtocol.test_setdefault(self)
680
681        class Exc(Exception): pass
682
683        class BadHash(object):
684            fail = False
685            def __hash__(self):
686                if self.fail:
687                    raise Exc()
688                else:
689                    return 42
690
691        d = self._empty_mapping()
692        x = BadHash()
693        d[x] = 42
694        x.fail = True
695        self.assertRaises(Exc, d.setdefault, x, [])
696