source: python/trunk/Lib/test/test_dict.py

Last change on this file was 391, checked in by dmik, 11 years ago

python: Merge vendor 2.7.6 to trunk.
  • Property svn:eol-style set to native
File size: 20.8 KB
Line 
1import unittest
2from test import test_support
3
4import UserDict, random, string
5import gc, weakref
6
7
8class DictTest(unittest.TestCase):
9 def test_constructor(self):
10 # calling built-in types without argument must return empty
11 self.assertEqual(dict(), {})
12 self.assertIsNot(dict(), {})
13
14 def test_literal_constructor(self):
15 # check literal constructor for different sized dicts
16 # (to exercise the BUILD_MAP oparg).
17 for n in (0, 1, 6, 256, 400):
18 items = [(''.join(random.sample(string.letters, 8)), i)
19 for i in range(n)]
20 random.shuffle(items)
21 formatted_items = ('{!r}: {:d}'.format(k, v) for k, v in items)
22 dictliteral = '{' + ', '.join(formatted_items) + '}'
23 self.assertEqual(eval(dictliteral), dict(items))
24
25 def test_bool(self):
26 self.assertIs(not {}, True)
27 self.assertTrue({1: 2})
28 self.assertIs(bool({}), False)
29 self.assertIs(bool({1: 2}), True)
30
31 def test_keys(self):
32 d = {}
33 self.assertEqual(d.keys(), [])
34 d = {'a': 1, 'b': 2}
35 k = d.keys()
36 self.assertEqual(set(k), {'a', 'b'})
37 self.assertIn('a', k)
38 self.assertIn('b', k)
39 self.assertTrue(d.has_key('a'))
40 self.assertTrue(d.has_key('b'))
41 self.assertRaises(TypeError, d.keys, None)
42
43 def test_values(self):
44 d = {}
45 self.assertEqual(d.values(), [])
46 d = {1:2}
47 self.assertEqual(d.values(), [2])
48
49 self.assertRaises(TypeError, d.values, None)
50
51 def test_items(self):
52 d = {}
53 self.assertEqual(d.items(), [])
54
55 d = {1:2}
56 self.assertEqual(d.items(), [(1, 2)])
57
58 self.assertRaises(TypeError, d.items, None)
59
60 def test_has_key(self):
61 d = {}
62 self.assertFalse(d.has_key('a'))
63 d = {'a': 1, 'b': 2}
64 k = d.keys()
65 k.sort()
66 self.assertEqual(k, ['a', 'b'])
67
68 self.assertRaises(TypeError, d.has_key)
69
70 def test_contains(self):
71 d = {}
72 self.assertNotIn('a', d)
73 self.assertFalse('a' in d)
74 self.assertTrue('a' not in d)
75 d = {'a': 1, 'b': 2}
76 self.assertIn('a', d)
77 self.assertIn('b', d)
78 self.assertNotIn('c', d)
79
80 self.assertRaises(TypeError, d.__contains__)
81
82 def test_len(self):
83 d = {}
84 self.assertEqual(len(d), 0)
85 d = {'a': 1, 'b': 2}
86 self.assertEqual(len(d), 2)
87
88 def test_getitem(self):
89 d = {'a': 1, 'b': 2}
90 self.assertEqual(d['a'], 1)
91 self.assertEqual(d['b'], 2)
92 d['c'] = 3
93 d['a'] = 4
94 self.assertEqual(d['c'], 3)
95 self.assertEqual(d['a'], 4)
96 del d['b']
97 self.assertEqual(d, {'a': 4, 'c': 3})
98
99 self.assertRaises(TypeError, d.__getitem__)
100
101 class BadEq(object):
102 def __eq__(self, other):
103 raise Exc()
104 def __hash__(self):
105 return 24
106
107 d = {}
108 d[BadEq()] = 42
109 self.assertRaises(KeyError, d.__getitem__, 23)
110
111 class Exc(Exception): pass
112
113 class BadHash(object):
114 fail = False
115 def __hash__(self):
116 if self.fail:
117 raise Exc()
118 else:
119 return 42
120
121 x = BadHash()
122 d[x] = 42
123 x.fail = True
124 self.assertRaises(Exc, d.__getitem__, x)
125
126 def test_clear(self):
127 d = {1:1, 2:2, 3:3}
128 d.clear()
129 self.assertEqual(d, {})
130
131 self.assertRaises(TypeError, d.clear, None)
132
133 def test_update(self):
134 d = {}
135 d.update({1:100})
136 d.update({2:20})
137 d.update({1:1, 2:2, 3:3})
138 self.assertEqual(d, {1:1, 2:2, 3:3})
139
140 d.update()
141 self.assertEqual(d, {1:1, 2:2, 3:3})
142
143 self.assertRaises((TypeError, AttributeError), d.update, None)
144
145 class SimpleUserDict:
146 def __init__(self):
147 self.d = {1:1, 2:2, 3:3}
148 def keys(self):
149 return self.d.keys()
150 def __getitem__(self, i):
151 return self.d[i]
152 d.clear()
153 d.update(SimpleUserDict())
154 self.assertEqual(d, {1:1, 2:2, 3:3})
155
156 class Exc(Exception): pass
157
158 d.clear()
159 class FailingUserDict:
160 def keys(self):
161 raise Exc
162 self.assertRaises(Exc, d.update, FailingUserDict())
163
164 class FailingUserDict:
165 def keys(self):
166 class BogonIter:
167 def __init__(self):
168 self.i = 1
169 def __iter__(self):
170 return self
171 def next(self):
172 if self.i:
173 self.i = 0
174 return 'a'
175 raise Exc
176 return BogonIter()
177 def __getitem__(self, key):
178 return key
179 self.assertRaises(Exc, d.update, FailingUserDict())
180
181 class FailingUserDict:
182 def keys(self):
183 class BogonIter:
184 def __init__(self):
185 self.i = ord('a')
186 def __iter__(self):
187 return self
188 def next(self):
189 if self.i <= ord('z'):
190 rtn = chr(self.i)
191 self.i += 1
192 return rtn
193 raise StopIteration
194 return BogonIter()
195 def __getitem__(self, key):
196 raise Exc
197 self.assertRaises(Exc, d.update, FailingUserDict())
198
199 class badseq(object):
200 def __iter__(self):
201 return self
202 def next(self):
203 raise Exc()
204
205 self.assertRaises(Exc, {}.update, badseq())
206
207 self.assertRaises(ValueError, {}.update, [(1, 2, 3)])
208
209 def test_fromkeys(self):
210 self.assertEqual(dict.fromkeys('abc'), {'a':None, 'b':None, 'c':None})
211 d = {}
212 self.assertIsNot(d.fromkeys('abc'), d)
213 self.assertEqual(d.fromkeys('abc'), {'a':None, 'b':None, 'c':None})
214 self.assertEqual(d.fromkeys((4,5),0), {4:0, 5:0})
215 self.assertEqual(d.fromkeys([]), {})
216 def g():
217 yield 1
218 self.assertEqual(d.fromkeys(g()), {1:None})
219 self.assertRaises(TypeError, {}.fromkeys, 3)
220 class dictlike(dict): pass
221 self.assertEqual(dictlike.fromkeys('a'), {'a':None})
222 self.assertEqual(dictlike().fromkeys('a'), {'a':None})
223 self.assertIsInstance(dictlike.fromkeys('a'), dictlike)
224 self.assertIsInstance(dictlike().fromkeys('a'), dictlike)
225 class mydict(dict):
226 def __new__(cls):
227 return UserDict.UserDict()
228 ud = mydict.fromkeys('ab')
229 self.assertEqual(ud, {'a':None, 'b':None})
230 self.assertIsInstance(ud, UserDict.UserDict)
231 self.assertRaises(TypeError, dict.fromkeys)
232
233 class Exc(Exception): pass
234
235 class baddict1(dict):
236 def __init__(self):
237 raise Exc()
238
239 self.assertRaises(Exc, baddict1.fromkeys, [1])
240
241 class BadSeq(object):
242 def __iter__(self):
243 return self
244 def next(self):
245 raise Exc()
246
247 self.assertRaises(Exc, dict.fromkeys, BadSeq())
248
249 class baddict2(dict):
250 def __setitem__(self, key, value):
251 raise Exc()
252
253 self.assertRaises(Exc, baddict2.fromkeys, [1])
254
255 # test fast path for dictionary inputs
256 d = dict(zip(range(6), range(6)))
257 self.assertEqual(dict.fromkeys(d, 0), dict(zip(range(6), [0]*6)))
258
259 class baddict3(dict):
260 def __new__(cls):
261 return d
262 d = {i : i for i in range(10)}
263 res = d.copy()
264 res.update(a=None, b=None, c=None)
265 self.assertEqual(baddict3.fromkeys({"a", "b", "c"}), res)
266
267 def test_copy(self):
268 d = {1:1, 2:2, 3:3}
269 self.assertEqual(d.copy(), {1:1, 2:2, 3:3})
270 self.assertEqual({}.copy(), {})
271 self.assertRaises(TypeError, d.copy, None)
272
273 def test_get(self):
274 d = {}
275 self.assertIs(d.get('c'), None)
276 self.assertEqual(d.get('c', 3), 3)
277 d = {'a': 1, 'b': 2}
278 self.assertIs(d.get('c'), None)
279 self.assertEqual(d.get('c', 3), 3)
280 self.assertEqual(d.get('a'), 1)
281 self.assertEqual(d.get('a', 3), 1)
282 self.assertRaises(TypeError, d.get)
283 self.assertRaises(TypeError, d.get, None, None, None)
284
285 def test_setdefault(self):
286 # dict.setdefault()
287 d = {}
288 self.assertIs(d.setdefault('key0'), None)
289 d.setdefault('key0', [])
290 self.assertIs(d.setdefault('key0'), None)
291 d.setdefault('key', []).append(3)
292 self.assertEqual(d['key'][0], 3)
293 d.setdefault('key', []).append(4)
294 self.assertEqual(len(d['key']), 2)
295 self.assertRaises(TypeError, d.setdefault)
296
297 class Exc(Exception): pass
298
299 class BadHash(object):
300 fail = False
301 def __hash__(self):
302 if self.fail:
303 raise Exc()
304 else:
305 return 42
306
307 x = BadHash()
308 d[x] = 42
309 x.fail = True
310 self.assertRaises(Exc, d.setdefault, x, [])
311
312 def test_setdefault_atomic(self):
313 # Issue #13521: setdefault() calls __hash__ and __eq__ only once.
314 class Hashed(object):
315 def __init__(self):
316 self.hash_count = 0
317 self.eq_count = 0
318 def __hash__(self):
319 self.hash_count += 1
320 return 42
321 def __eq__(self, other):
322 self.eq_count += 1
323 return id(self) == id(other)
324 hashed1 = Hashed()
325 y = {hashed1: 5}
326 hashed2 = Hashed()
327 y.setdefault(hashed2, [])
328 self.assertEqual(hashed1.hash_count, 1)
329 self.assertEqual(hashed2.hash_count, 1)
330 self.assertEqual(hashed1.eq_count + hashed2.eq_count, 1)
331
332 def test_popitem(self):
333 # dict.popitem()
334 for copymode in -1, +1:
335 # -1: b has same structure as a
336 # +1: b is a.copy()
337 for log2size in range(12):
338 size = 2**log2size
339 a = {}
340 b = {}
341 for i in range(size):
342 a[repr(i)] = i
343 if copymode < 0:
344 b[repr(i)] = i
345 if copymode > 0:
346 b = a.copy()
347 for i in range(size):
348 ka, va = ta = a.popitem()
349 self.assertEqual(va, int(ka))
350 kb, vb = tb = b.popitem()
351 self.assertEqual(vb, int(kb))
352 self.assertFalse(copymode < 0 and ta != tb)
353 self.assertFalse(a)
354 self.assertFalse(b)
355
356 d = {}
357 self.assertRaises(KeyError, d.popitem)
358
359 def test_pop(self):
360 # Tests for pop with specified key
361 d = {}
362 k, v = 'abc', 'def'
363 d[k] = v
364 self.assertRaises(KeyError, d.pop, 'ghi')
365
366 self.assertEqual(d.pop(k), v)
367 self.assertEqual(len(d), 0)
368
369 self.assertRaises(KeyError, d.pop, k)
370
371 # verify longs/ints get same value when key > 32 bits
372 # (for 64-bit archs). See SF bug #689659.
373 x = 4503599627370496L
374 y = 4503599627370496
375 h = {x: 'anything', y: 'something else'}
376 self.assertEqual(h[x], h[y])
377
378 self.assertEqual(d.pop(k, v), v)
379 d[k] = v
380 self.assertEqual(d.pop(k, 1), v)
381
382 self.assertRaises(TypeError, d.pop)
383
384 class Exc(Exception): pass
385
386 class BadHash(object):
387 fail = False
388 def __hash__(self):
389 if self.fail:
390 raise Exc()
391 else:
392 return 42
393
394 x = BadHash()
395 d[x] = 42
396 x.fail = True
397 self.assertRaises(Exc, d.pop, x)
398
399 def test_mutatingiteration(self):
400 # changing dict size during iteration
401 d = {}
402 d[1] = 1
403 with self.assertRaises(RuntimeError):
404 for i in d:
405 d[i+1] = 1
406
407 def test_repr(self):
408 d = {}
409 self.assertEqual(repr(d), '{}')
410 d[1] = 2
411 self.assertEqual(repr(d), '{1: 2}')
412 d = {}
413 d[1] = d
414 self.assertEqual(repr(d), '{1: {...}}')
415
416 class Exc(Exception): pass
417
418 class BadRepr(object):
419 def __repr__(self):
420 raise Exc()
421
422 d = {1: BadRepr()}
423 self.assertRaises(Exc, repr, d)
424
425 def test_le(self):
426 self.assertFalse({} < {})
427 self.assertFalse({1: 2} < {1L: 2L})
428
429 class Exc(Exception): pass
430
431 class BadCmp(object):
432 def __eq__(self, other):
433 raise Exc()
434 def __hash__(self):
435 return 42
436
437 d1 = {BadCmp(): 1}
438 d2 = {1: 1}
439
440 with self.assertRaises(Exc):
441 d1 < d2
442
443 def test_missing(self):
444 # Make sure dict doesn't have a __missing__ method
445 self.assertFalse(hasattr(dict, "__missing__"))
446 self.assertFalse(hasattr({}, "__missing__"))
447 # Test several cases:
448 # (D) subclass defines __missing__ method returning a value
449 # (E) subclass defines __missing__ method raising RuntimeError
450 # (F) subclass sets __missing__ instance variable (no effect)
451 # (G) subclass doesn't define __missing__ at a all
452 class D(dict):
453 def __missing__(self, key):
454 return 42
455 d = D({1: 2, 3: 4})
456 self.assertEqual(d[1], 2)
457 self.assertEqual(d[3], 4)
458 self.assertNotIn(2, d)
459 self.assertNotIn(2, d.keys())
460 self.assertEqual(d[2], 42)
461
462 class E(dict):
463 def __missing__(self, key):
464 raise RuntimeError(key)
465 e = E()
466 with self.assertRaises(RuntimeError) as c:
467 e[42]
468 self.assertEqual(c.exception.args, (42,))
469
470 class F(dict):
471 def __init__(self):
472 # An instance variable __missing__ should have no effect
473 self.__missing__ = lambda key: None
474 f = F()
475 with self.assertRaises(KeyError) as c:
476 f[42]
477 self.assertEqual(c.exception.args, (42,))
478
479 class G(dict):
480 pass
481 g = G()
482 with self.assertRaises(KeyError) as c:
483 g[42]
484 self.assertEqual(c.exception.args, (42,))
485
486 def test_tuple_keyerror(self):
487 # SF #1576657
488 d = {}
489 with self.assertRaises(KeyError) as c:
490 d[(1,)]
491 self.assertEqual(c.exception.args, ((1,),))
492
493 def test_bad_key(self):
494 # Dictionary lookups should fail if __cmp__() raises an exception.
495 class CustomException(Exception):
496 pass
497
498 class BadDictKey:
499 def __hash__(self):
500 return hash(self.__class__)
501
502 def __cmp__(self, other):
503 if isinstance(other, self.__class__):
504 raise CustomException
505 return other
506
507 d = {}
508 x1 = BadDictKey()
509 x2 = BadDictKey()
510 d[x1] = 1
511 for stmt in ['d[x2] = 2',
512 'z = d[x2]',
513 'x2 in d',
514 'd.has_key(x2)',
515 'd.get(x2)',
516 'd.setdefault(x2, 42)',
517 'd.pop(x2)',
518 'd.update({x2: 2})']:
519 with self.assertRaises(CustomException):
520 exec stmt in locals()
521
522 def test_resize1(self):
523 # Dict resizing bug, found by Jack Jansen in 2.2 CVS development.
524 # This version got an assert failure in debug build, infinite loop in
525 # release build. Unfortunately, provoking this kind of stuff requires
526 # a mix of inserts and deletes hitting exactly the right hash codes in
527 # exactly the right order, and I can't think of a randomized approach
528 # that would be *likely* to hit a failing case in reasonable time.
529
530 d = {}
531 for i in range(5):
532 d[i] = i
533 for i in range(5):
534 del d[i]
535 for i in range(5, 9): # i==8 was the problem
536 d[i] = i
537
538 def test_resize2(self):
539 # Another dict resizing bug (SF bug #1456209).
540 # This caused Segmentation faults or Illegal instructions.
541
542 class X(object):
543 def __hash__(self):
544 return 5
545 def __eq__(self, other):
546 if resizing:
547 d.clear()
548 return False
549 d = {}
550 resizing = False
551 d[X()] = 1
552 d[X()] = 2
553 d[X()] = 3
554 d[X()] = 4
555 d[X()] = 5
556 # now trigger a resize
557 resizing = True
558 d[9] = 6
559
560 def test_empty_presized_dict_in_freelist(self):
561 # Bug #3537: if an empty but presized dict with a size larger
562 # than 7 was in the freelist, it triggered an assertion failure
563 with self.assertRaises(ZeroDivisionError):
564 d = {'a': 1 // 0, 'b': None, 'c': None, 'd': None, 'e': None,
565 'f': None, 'g': None, 'h': None}
566 d = {}
567
568 def test_container_iterator(self):
569 # Bug #3680: tp_traverse was not implemented for dictiter objects
570 class C(object):
571 pass
572 iterators = (dict.iteritems, dict.itervalues, dict.iterkeys)
573 for i in iterators:
574 obj = C()
575 ref = weakref.ref(obj)
576 container = {obj: 1}
577 obj.x = i(container)
578 del obj, container
579 gc.collect()
580 self.assertIs(ref(), None, "Cycle was not collected")
581
582 def _not_tracked(self, t):
583 # Nested containers can take several collections to untrack
584 gc.collect()
585 gc.collect()
586 self.assertFalse(gc.is_tracked(t), t)
587
588 def _tracked(self, t):
589 self.assertTrue(gc.is_tracked(t), t)
590 gc.collect()
591 gc.collect()
592 self.assertTrue(gc.is_tracked(t), t)
593
594 @test_support.cpython_only
595 def test_track_literals(self):
596 # Test GC-optimization of dict literals
597 x, y, z, w = 1.5, "a", (1, None), []
598
599 self._not_tracked({})
600 self._not_tracked({x:(), y:x, z:1})
601 self._not_tracked({1: "a", "b": 2})
602 self._not_tracked({1: 2, (None, True, False, ()): int})
603 self._not_tracked({1: object()})
604
605 # Dicts with mutable elements are always tracked, even if those
606 # elements are not tracked right now.
607 self._tracked({1: []})
608 self._tracked({1: ([],)})
609 self._tracked({1: {}})
610 self._tracked({1: set()})
611
612 @test_support.cpython_only
613 def test_track_dynamic(self):
614 # Test GC-optimization of dynamically-created dicts
615 class MyObject(object):
616 pass
617 x, y, z, w, o = 1.5, "a", (1, object()), [], MyObject()
618
619 d = dict()
620 self._not_tracked(d)
621 d[1] = "a"
622 self._not_tracked(d)
623 d[y] = 2
624 self._not_tracked(d)
625 d[z] = 3
626 self._not_tracked(d)
627 self._not_tracked(d.copy())
628 d[4] = w
629 self._tracked(d)
630 self._tracked(d.copy())
631 d[4] = None
632 self._not_tracked(d)
633 self._not_tracked(d.copy())
634
635 # dd isn't tracked right now, but it may mutate and therefore d
636 # which contains it must be tracked.
637 d = dict()
638 dd = dict()
639 d[1] = dd
640 self._not_tracked(dd)
641 self._tracked(d)
642 dd[1] = d
643 self._tracked(dd)
644
645 d = dict.fromkeys([x, y, z])
646 self._not_tracked(d)
647 dd = dict()
648 dd.update(d)
649 self._not_tracked(dd)
650 d = dict.fromkeys([x, y, z, o])
651 self._tracked(d)
652 dd = dict()
653 dd.update(d)
654 self._tracked(dd)
655
656 d = dict(x=x, y=y, z=z)
657 self._not_tracked(d)
658 d = dict(x=x, y=y, z=z, w=w)
659 self._tracked(d)
660 d = dict()
661 d.update(x=x, y=y, z=z)
662 self._not_tracked(d)
663 d.update(w=w)
664 self._tracked(d)
665
666 d = dict([(x, y), (z, 1)])
667 self._not_tracked(d)
668 d = dict([(x, y), (z, w)])
669 self._tracked(d)
670 d = dict()
671 d.update([(x, y), (z, 1)])
672 self._not_tracked(d)
673 d.update([(x, y), (z, w)])
674 self._tracked(d)
675
676 @test_support.cpython_only
677 def test_track_subtypes(self):
678 # Dict subtypes are always tracked
679 class MyDict(dict):
680 pass
681 self._tracked(MyDict())
682
683
684from test import mapping_tests
685
686class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
687 type2test = dict
688
689class Dict(dict):
690 pass
691
692class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
693 type2test = Dict
694
695def test_main():
696 with test_support.check_py3k_warnings(
697 ('dict(.has_key..| inequality comparisons) not supported in 3.x',
698 DeprecationWarning)):
699 test_support.run_unittest(
700 DictTest,
701 GeneralMappingTests,
702 SubclassMappingTests,
703 )
704
705if __name__ == "__main__":
706 test_main()
Note: See TracBrowser for help on using the repository browser.