1""" 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.
12For instance, an iterable such as xrange(10) always reports its length as ten,
13but it=iter(xrange(10)) starts at ten, and then goes to nine after it.next().
14Having 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().
19This is the case for tuples, xrange objects, and itertools.repeat().
20
21Some containers become temporarily immutable during iteration.  This includes
22dicts, sets, and collections.deque.  Their implementation is equally simple
23though they need to permanently set their length to zero whenever there is
24an attempt to iterate after a length mutation.
25
26The situation slightly more involved whenever an object allows length mutation
27during iteration.  Lists and sequence iterators are dynamically updatable.
28So, 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
45from test import test_support
46from itertools import repeat
47from collections import deque
48from __builtin__ import len as _len
49
50n = 10
51
52def len(obj):
53    try:
54        return _len(obj)
55    except TypeError:
56        try:
57            # note: this is an internal undocumented API,
58            # don't rely on it in your own programs
59            return obj.__length_hint__()
60        except AttributeError:
61            raise TypeError
62
63class TestInvariantWithoutMutations(unittest.TestCase):
64
65    def test_invariant(self):
66        it = self.it
67        for i in reversed(xrange(1, n+1)):
68            self.assertEqual(len(it), i)
69            it.next()
70        self.assertEqual(len(it), 0)
71        self.assertRaises(StopIteration, it.next)
72        self.assertEqual(len(it), 0)
73
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)
82        it.next()
83        self.assertEqual(len(it), n-1)
84        self.mutate()
85        self.assertRaises(RuntimeError, it.next)
86        self.assertEqual(len(it), 0)
87
88## ------- Concrete Type Tests -------
89
90class TestRepeat(TestInvariantWithoutMutations):
91
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
99class TestXrange(TestInvariantWithoutMutations):
100
101    def setUp(self):
102        self.it = iter(xrange(n))
103
104class TestXrangeCustomReversed(TestInvariantWithoutMutations):
105
106    def setUp(self):
107        self.it = reversed(xrange(n))
108
109class TestTuple(TestInvariantWithoutMutations):
110
111    def setUp(self):
112        self.it = iter(tuple(xrange(n)))
113
114## ------- Types that should not be mutated during iteration -------
115
116class TestDeque(TestTemporarilyImmutable):
117
118    def setUp(self):
119        d = deque(xrange(n))
120        self.it = iter(d)
121        self.mutate = d.pop
122
123class TestDequeReversed(TestTemporarilyImmutable):
124
125    def setUp(self):
126        d = deque(xrange(n))
127        self.it = reversed(d)
128        self.mutate = d.pop
129
130class TestDictKeys(TestTemporarilyImmutable):
131
132    def setUp(self):
133        d = dict.fromkeys(xrange(n))
134        self.it = iter(d)
135        self.mutate = d.popitem
136
137class TestDictItems(TestTemporarilyImmutable):
138
139    def setUp(self):
140        d = dict.fromkeys(xrange(n))
141        self.it = d.iteritems()
142        self.mutate = d.popitem
143
144class TestDictValues(TestTemporarilyImmutable):
145
146    def setUp(self):
147        d = dict.fromkeys(xrange(n))
148        self.it = d.itervalues()
149        self.mutate = d.popitem
150
151class TestSet(TestTemporarilyImmutable):
152
153    def setUp(self):
154        d = set(xrange(n))
155        self.it = iter(d)
156        self.mutate = d.pop
157
158## ------- Types that can mutate during iteration -------
159
160class TestList(TestInvariantWithoutMutations):
161
162    def setUp(self):
163        self.it = iter(range(n))
164
165    def test_mutation(self):
166        d = range(n)
167        it = iter(d)
168        it.next()
169        it.next()
170        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), [])
176        d.extend(xrange(20))
177        self.assertEqual(len(it), 0)
178
179class TestListReversed(TestInvariantWithoutMutations):
180
181    def setUp(self):
182        self.it = reversed(range(n))
183
184    def test_mutation(self):
185        d = range(n)
186        it = reversed(d)
187        it.next()
188        it.next()
189        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
195        d.extend(xrange(20))
196        self.assertEqual(len(it), 0)
197
198## -- 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
211class NoneLengthHint(object):
212    def __iter__(self): return iter(range(10))
213    def __length_hint__(self):
214        return None
215
216class 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        self.assertRaises(RuntimeError, zip, BadLen())
224        self.assertRaises(RuntimeError, zip, BadLengthHint())
225        self.assertRaises(RuntimeError, filter, None, BadLen())
226        self.assertRaises(RuntimeError, filter, None, BadLengthHint())
227        self.assertRaises(RuntimeError, map, chr, BadLen())
228        self.assertRaises(RuntimeError, map, chr, BadLengthHint())
229        b = bytearray(range(10))
230        self.assertRaises(RuntimeError, b.extend, BadLen())
231        self.assertRaises(RuntimeError, b.extend, BadLengthHint())
232
233    def test_invalid_hint(self):
234        # Make sure an invalid result doesn't muck-up the works
235        self.assertEqual(list(NoneLengthHint()), list(range(10)))
236
237
238def test_main():
239    unittests = [
240        TestRepeat,
241        TestXrange,
242        TestXrangeCustomReversed,
243        TestTuple,
244        TestDeque,
245        TestDequeReversed,
246        TestDictKeys,
247        TestDictItems,
248        TestDictValues,
249        TestSet,
250        TestList,
251        TestListReversed,
252        TestLengthHintExceptions,
253    ]
254    test_support.run_unittest(*unittests)
255
256if __name__ == "__main__":
257    test_main()
258