blob: 9101f6c884695c4e190961178f3da5c4a69f2ae8 [file] [log] [blame]
Raymond Hettinger7892b1c2004-04-12 18:10:01 +00001""" Test Iterator Length Transparency
2
3Some functions or methods which accept general iterable arguments have
4optional, more efficient code paths if they know how many items to expect.
5For instance, map(func, iterable), will pre-allocate the exact amount of
6space required whenever the iterable can report its length.
7
8The desired invariant is: len(it)==len(list(it)).
9
10A complication is that an iterable and iterator can be the same object. To
11maintain the invariant, an iterator needs to dynamically update its length.
Guido van Rossum805365e2007-05-07 22:24:25 +000012For instance, an iterable such as range(10) always reports its length as ten,
13but it=iter(range(10)) starts at ten, and then goes to nine after next(it).
Raymond Hettinger7892b1c2004-04-12 18:10:01 +000014Having this capability means that map() can ignore the distinction between
15map(func, iterable) and map(func, iter(iterable)).
16
17When the iterable is immutable, the implementation can straight-forwardly
18report the original length minus the cumulative number of calls to next().
Guido van Rossum805365e2007-05-07 22:24:25 +000019This is the case for tuples, range objects, and itertools.repeat().
Raymond Hettinger7892b1c2004-04-12 18:10:01 +000020
21Some containers become temporarily immutable during iteration. This includes
22dicts, sets, and collections.deque. Their implementation is equally simple
Ezio Melotti13925002011-03-16 11:05:33 +020023though they need to permanently set their length to zero whenever there is
Raymond Hettinger7892b1c2004-04-12 18:10:01 +000024an attempt to iterate after a length mutation.
25
26The situation slightly more involved whenever an object allows length mutation
Ezio Melotti13925002011-03-16 11:05:33 +020027during iteration. Lists and sequence iterators are dynamically updatable.
Raymond Hettinger7892b1c2004-04-12 18:10:01 +000028So, if a list is extended during iteration, the iterator will continue through
29the new items. If it shrinks to a point before the most recent iteration,
30then no further items are available and the length is reported at zero.
31
32Reversed objects can also be wrapped around mutable objects; however, any
33appends after the current position are ignored. Any other approach leads
34to confusion and possibly returning the same item more than once.
35
36The iterators not listed above, such as enumerate and the other itertools,
37are not length transparent because they have no way to distinguish between
38iterables that report static length and iterators whose length changes with
39each call (i.e. the difference between enumerate('abc') and
40enumerate(iter('abc')).
41
42"""
43
44import unittest
Benjamin Petersonee8712c2008-05-20 21:35:26 +000045from test import support
Raymond Hettinger6b27cda2005-09-24 21:23:05 +000046from itertools import repeat
Raymond Hettinger7892b1c2004-04-12 18:10:01 +000047from collections import deque
Georg Brandl1a3284e2007-12-02 09:40:06 +000048from builtins import len as _len
Raymond Hettinger7892b1c2004-04-12 18:10:01 +000049
50n = 10
51
Raymond Hettinger6b27cda2005-09-24 21:23:05 +000052def len(obj):
53 try:
54 return _len(obj)
55 except TypeError:
56 try:
Armin Rigof5b3e362006-02-11 21:32:43 +000057 # note: this is an internal undocumented API,
58 # don't rely on it in your own programs
59 return obj.__length_hint__()
Raymond Hettinger6b27cda2005-09-24 21:23:05 +000060 except AttributeError:
61 raise TypeError
62
Ezio Melottid13c0082013-04-17 04:34:05 +030063class TestInvariantWithoutMutations:
Raymond Hettinger7892b1c2004-04-12 18:10:01 +000064
65 def test_invariant(self):
Tim Peters27f88362004-07-08 04:22:35 +000066 it = self.it
Guido van Rossum805365e2007-05-07 22:24:25 +000067 for i in reversed(range(1, n+1)):
Tim Peters27f88362004-07-08 04:22:35 +000068 self.assertEqual(len(it), i)
Georg Brandla18af4e2007-04-21 15:47:16 +000069 next(it)
Tim Peters27f88362004-07-08 04:22:35 +000070 self.assertEqual(len(it), 0)
Georg Brandla18af4e2007-04-21 15:47:16 +000071 self.assertRaises(StopIteration, next, it)
Tim Peters27f88362004-07-08 04:22:35 +000072 self.assertEqual(len(it), 0)
Raymond Hettinger7892b1c2004-04-12 18:10:01 +000073
74class TestTemporarilyImmutable(TestInvariantWithoutMutations):
75
76 def test_immutable_during_iteration(self):
77 # objects such as deques, sets, and dictionaries enforce
78 # length immutability during iteration
79
80 it = self.it
81 self.assertEqual(len(it), n)
Georg Brandla18af4e2007-04-21 15:47:16 +000082 next(it)
Raymond Hettinger7892b1c2004-04-12 18:10:01 +000083 self.assertEqual(len(it), n-1)
84 self.mutate()
Georg Brandla18af4e2007-04-21 15:47:16 +000085 self.assertRaises(RuntimeError, next, it)
Raymond Hettinger7892b1c2004-04-12 18:10:01 +000086 self.assertEqual(len(it), 0)
87
88## ------- Concrete Type Tests -------
89
Ezio Melottid13c0082013-04-17 04:34:05 +030090class TestRepeat(TestInvariantWithoutMutations, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +000091
92 def setUp(self):
93 self.it = repeat(None, n)
94
95 def test_no_len_for_infinite_repeat(self):
96 # The repeat() object can also be infinite
97 self.assertRaises(TypeError, len, repeat(None))
98
Ezio Melottid13c0082013-04-17 04:34:05 +030099class TestXrange(TestInvariantWithoutMutations, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000100
101 def setUp(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000102 self.it = iter(range(n))
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000103
Ezio Melottid13c0082013-04-17 04:34:05 +0300104class TestXrangeCustomReversed(TestInvariantWithoutMutations, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000105
106 def setUp(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000107 self.it = reversed(range(n))
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000108
Ezio Melottid13c0082013-04-17 04:34:05 +0300109class TestTuple(TestInvariantWithoutMutations, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000110
111 def setUp(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000112 self.it = iter(tuple(range(n)))
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000113
114## ------- Types that should not be mutated during iteration -------
115
Ezio Melottid13c0082013-04-17 04:34:05 +0300116class TestDeque(TestTemporarilyImmutable, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000117
118 def setUp(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000119 d = deque(range(n))
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000120 self.it = iter(d)
121 self.mutate = d.pop
122
Ezio Melottid13c0082013-04-17 04:34:05 +0300123class TestDequeReversed(TestTemporarilyImmutable, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000124
125 def setUp(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000126 d = deque(range(n))
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000127 self.it = reversed(d)
128 self.mutate = d.pop
129
Ezio Melottid13c0082013-04-17 04:34:05 +0300130class TestDictKeys(TestTemporarilyImmutable, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000131
132 def setUp(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000133 d = dict.fromkeys(range(n))
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000134 self.it = iter(d)
135 self.mutate = d.popitem
136
Ezio Melottid13c0082013-04-17 04:34:05 +0300137class TestDictItems(TestTemporarilyImmutable, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000138
139 def setUp(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000140 d = dict.fromkeys(range(n))
Brett Cannoneb6b0ee2007-02-22 04:45:13 +0000141 self.it = iter(d.items())
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000142 self.mutate = d.popitem
143
Ezio Melottid13c0082013-04-17 04:34:05 +0300144class TestDictValues(TestTemporarilyImmutable, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000145
146 def setUp(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000147 d = dict.fromkeys(range(n))
Brett Cannoneb6b0ee2007-02-22 04:45:13 +0000148 self.it = iter(d.values())
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000149 self.mutate = d.popitem
150
Ezio Melottid13c0082013-04-17 04:34:05 +0300151class TestSet(TestTemporarilyImmutable, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000152
153 def setUp(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000154 d = set(range(n))
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000155 self.it = iter(d)
156 self.mutate = d.pop
157
158## ------- Types that can mutate during iteration -------
159
Ezio Melottid13c0082013-04-17 04:34:05 +0300160class TestList(TestInvariantWithoutMutations, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000161
162 def setUp(self):
163 self.it = iter(range(n))
164
165 def test_mutation(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000166 d = list(range(n))
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000167 it = iter(d)
Georg Brandla18af4e2007-04-21 15:47:16 +0000168 next(it)
169 next(it)
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000170 self.assertEqual(len(it), n-2)
171 d.append(n)
172 self.assertEqual(len(it), n-1) # grow with append
173 d[1:] = []
174 self.assertEqual(len(it), 0)
175 self.assertEqual(list(it), [])
Guido van Rossum805365e2007-05-07 22:24:25 +0000176 d.extend(range(20))
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000177 self.assertEqual(len(it), 0)
178
Ezio Melottid13c0082013-04-17 04:34:05 +0300179class TestListReversed(TestInvariantWithoutMutations, unittest.TestCase):
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000180
181 def setUp(self):
182 self.it = reversed(range(n))
183
184 def test_mutation(self):
Guido van Rossum805365e2007-05-07 22:24:25 +0000185 d = list(range(n))
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000186 it = reversed(d)
Georg Brandla18af4e2007-04-21 15:47:16 +0000187 next(it)
188 next(it)
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000189 self.assertEqual(len(it), n-2)
190 d.append(n)
191 self.assertEqual(len(it), n-2) # ignore append
192 d[1:] = []
193 self.assertEqual(len(it), 0)
194 self.assertEqual(list(it), []) # confirm invariant
Guido van Rossum805365e2007-05-07 22:24:25 +0000195 d.extend(range(20))
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000196 self.assertEqual(len(it), 0)
197
Raymond Hettingere8364232009-02-02 22:55:09 +0000198## -- Check to make sure exceptions are not suppressed by __length_hint__()
199
200
201class BadLen(object):
202 def __iter__(self): return iter(range(10))
203 def __len__(self):
204 raise RuntimeError('hello')
205
206class BadLengthHint(object):
207 def __iter__(self): return iter(range(10))
208 def __length_hint__(self):
209 raise RuntimeError('hello')
210
Raymond Hettinger5d654122009-02-03 02:12:10 +0000211class NoneLengthHint(object):
212 def __iter__(self): return iter(range(10))
213 def __length_hint__(self):
214 return None
215
Raymond Hettingere8364232009-02-02 22:55:09 +0000216class TestLengthHintExceptions(unittest.TestCase):
217
218 def test_issue1242657(self):
219 self.assertRaises(RuntimeError, list, BadLen())
220 self.assertRaises(RuntimeError, list, BadLengthHint())
221 self.assertRaises(RuntimeError, [].extend, BadLen())
222 self.assertRaises(RuntimeError, [].extend, BadLengthHint())
223 b = bytearray(range(10))
224 self.assertRaises(RuntimeError, b.extend, BadLen())
225 self.assertRaises(RuntimeError, b.extend, BadLengthHint())
Raymond Hettinger7892b1c2004-04-12 18:10:01 +0000226
Raymond Hettinger5d654122009-02-03 02:12:10 +0000227 def test_invalid_hint(self):
228 # Make sure an invalid result doesn't muck-up the works
229 self.assertEqual(list(NoneLengthHint()), list(range(10)))
230
231
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000232if __name__ == "__main__":
Ezio Melottid13c0082013-04-17 04:34:05 +0300233 unittest.main()