|
1 """ Test Iterator Length Transparency |
|
2 |
|
3 Some functions or methods which accept general iterable arguments have |
|
4 optional, more efficient code paths if they know how many items to expect. |
|
5 For instance, map(func, iterable), will pre-allocate the exact amount of |
|
6 space required whenever the iterable can report its length. |
|
7 |
|
8 The desired invariant is: len(it)==len(list(it)). |
|
9 |
|
10 A complication is that an iterable and iterator can be the same object. To |
|
11 maintain the invariant, an iterator needs to dynamically update its length. |
|
12 For instance, an iterable such as xrange(10) always reports its length as ten, |
|
13 but it=iter(xrange(10)) starts at ten, and then goes to nine after it.next(). |
|
14 Having this capability means that map() can ignore the distinction between |
|
15 map(func, iterable) and map(func, iter(iterable)). |
|
16 |
|
17 When the iterable is immutable, the implementation can straight-forwardly |
|
18 report the original length minus the cumulative number of calls to next(). |
|
19 This is the case for tuples, xrange objects, and itertools.repeat(). |
|
20 |
|
21 Some containers become temporarily immutable during iteration. This includes |
|
22 dicts, sets, and collections.deque. Their implementation is equally simple |
|
23 though they need to permantently set their length to zero whenever there is |
|
24 an attempt to iterate after a length mutation. |
|
25 |
|
26 The situation slightly more involved whenever an object allows length mutation |
|
27 during iteration. Lists and sequence iterators are dynanamically updatable. |
|
28 So, if a list is extended during iteration, the iterator will continue through |
|
29 the new items. If it shrinks to a point before the most recent iteration, |
|
30 then no further items are available and the length is reported at zero. |
|
31 |
|
32 Reversed objects can also be wrapped around mutable objects; however, any |
|
33 appends after the current position are ignored. Any other approach leads |
|
34 to confusion and possibly returning the same item more than once. |
|
35 |
|
36 The iterators not listed above, such as enumerate and the other itertools, |
|
37 are not length transparent because they have no way to distinguish between |
|
38 iterables that report static length and iterators whose length changes with |
|
39 each call (i.e. the difference between enumerate('abc') and |
|
40 enumerate(iter('abc')). |
|
41 |
|
42 """ |
|
43 |
|
44 import unittest |
|
45 from test import test_support |
|
46 from itertools import repeat |
|
47 from collections import deque |
|
48 from __builtin__ import len as _len |
|
49 |
|
50 n = 10 |
|
51 |
|
52 def 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 |
|
63 class 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 |
|
74 class 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 |
|
90 class 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 |
|
99 class TestXrange(TestInvariantWithoutMutations): |
|
100 |
|
101 def setUp(self): |
|
102 self.it = iter(xrange(n)) |
|
103 |
|
104 class TestXrangeCustomReversed(TestInvariantWithoutMutations): |
|
105 |
|
106 def setUp(self): |
|
107 self.it = reversed(xrange(n)) |
|
108 |
|
109 class 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 |
|
116 class TestDeque(TestTemporarilyImmutable): |
|
117 |
|
118 def setUp(self): |
|
119 d = deque(xrange(n)) |
|
120 self.it = iter(d) |
|
121 self.mutate = d.pop |
|
122 |
|
123 class TestDequeReversed(TestTemporarilyImmutable): |
|
124 |
|
125 def setUp(self): |
|
126 d = deque(xrange(n)) |
|
127 self.it = reversed(d) |
|
128 self.mutate = d.pop |
|
129 |
|
130 class TestDictKeys(TestTemporarilyImmutable): |
|
131 |
|
132 def setUp(self): |
|
133 d = dict.fromkeys(xrange(n)) |
|
134 self.it = iter(d) |
|
135 self.mutate = d.popitem |
|
136 |
|
137 class TestDictItems(TestTemporarilyImmutable): |
|
138 |
|
139 def setUp(self): |
|
140 d = dict.fromkeys(xrange(n)) |
|
141 self.it = d.iteritems() |
|
142 self.mutate = d.popitem |
|
143 |
|
144 class TestDictValues(TestTemporarilyImmutable): |
|
145 |
|
146 def setUp(self): |
|
147 d = dict.fromkeys(xrange(n)) |
|
148 self.it = d.itervalues() |
|
149 self.mutate = d.popitem |
|
150 |
|
151 class 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 |
|
160 class 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 |
|
179 class 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 def test_main(): |
|
199 unittests = [ |
|
200 TestRepeat, |
|
201 TestXrange, |
|
202 TestXrangeCustomReversed, |
|
203 TestTuple, |
|
204 TestDeque, |
|
205 TestDequeReversed, |
|
206 TestDictKeys, |
|
207 TestDictItems, |
|
208 TestDictValues, |
|
209 TestSet, |
|
210 TestList, |
|
211 TestListReversed, |
|
212 ] |
|
213 test_support.run_unittest(*unittests) |
|
214 |
|
215 if __name__ == "__main__": |
|
216 test_main() |