]>
Commit | Line | Data |
---|---|---|
4710c53d | 1 | """ Test Iterator Length Transparency\r |
2 | \r | |
3 | Some functions or methods which accept general iterable arguments have\r | |
4 | optional, more efficient code paths if they know how many items to expect.\r | |
5 | For instance, map(func, iterable), will pre-allocate the exact amount of\r | |
6 | space required whenever the iterable can report its length.\r | |
7 | \r | |
8 | The desired invariant is: len(it)==len(list(it)).\r | |
9 | \r | |
10 | A complication is that an iterable and iterator can be the same object. To\r | |
11 | maintain the invariant, an iterator needs to dynamically update its length.\r | |
12 | For instance, an iterable such as xrange(10) always reports its length as ten,\r | |
13 | but it=iter(xrange(10)) starts at ten, and then goes to nine after it.next().\r | |
14 | Having this capability means that map() can ignore the distinction between\r | |
15 | map(func, iterable) and map(func, iter(iterable)).\r | |
16 | \r | |
17 | When the iterable is immutable, the implementation can straight-forwardly\r | |
18 | report the original length minus the cumulative number of calls to next().\r | |
19 | This is the case for tuples, xrange objects, and itertools.repeat().\r | |
20 | \r | |
21 | Some containers become temporarily immutable during iteration. This includes\r | |
22 | dicts, sets, and collections.deque. Their implementation is equally simple\r | |
23 | though they need to permanently set their length to zero whenever there is\r | |
24 | an attempt to iterate after a length mutation.\r | |
25 | \r | |
26 | The situation slightly more involved whenever an object allows length mutation\r | |
27 | during iteration. Lists and sequence iterators are dynamically updatable.\r | |
28 | So, if a list is extended during iteration, the iterator will continue through\r | |
29 | the new items. If it shrinks to a point before the most recent iteration,\r | |
30 | then no further items are available and the length is reported at zero.\r | |
31 | \r | |
32 | Reversed objects can also be wrapped around mutable objects; however, any\r | |
33 | appends after the current position are ignored. Any other approach leads\r | |
34 | to confusion and possibly returning the same item more than once.\r | |
35 | \r | |
36 | The iterators not listed above, such as enumerate and the other itertools,\r | |
37 | are not length transparent because they have no way to distinguish between\r | |
38 | iterables that report static length and iterators whose length changes with\r | |
39 | each call (i.e. the difference between enumerate('abc') and\r | |
40 | enumerate(iter('abc')).\r | |
41 | \r | |
42 | """\r | |
43 | \r | |
44 | import unittest\r | |
45 | from test import test_support\r | |
46 | from itertools import repeat\r | |
47 | from collections import deque\r | |
48 | from __builtin__ import len as _len\r | |
49 | \r | |
50 | n = 10\r | |
51 | \r | |
52 | def len(obj):\r | |
53 | try:\r | |
54 | return _len(obj)\r | |
55 | except TypeError:\r | |
56 | try:\r | |
57 | # note: this is an internal undocumented API,\r | |
58 | # don't rely on it in your own programs\r | |
59 | return obj.__length_hint__()\r | |
60 | except AttributeError:\r | |
61 | raise TypeError\r | |
62 | \r | |
63 | class TestInvariantWithoutMutations(unittest.TestCase):\r | |
64 | \r | |
65 | def test_invariant(self):\r | |
66 | it = self.it\r | |
67 | for i in reversed(xrange(1, n+1)):\r | |
68 | self.assertEqual(len(it), i)\r | |
69 | it.next()\r | |
70 | self.assertEqual(len(it), 0)\r | |
71 | self.assertRaises(StopIteration, it.next)\r | |
72 | self.assertEqual(len(it), 0)\r | |
73 | \r | |
74 | class TestTemporarilyImmutable(TestInvariantWithoutMutations):\r | |
75 | \r | |
76 | def test_immutable_during_iteration(self):\r | |
77 | # objects such as deques, sets, and dictionaries enforce\r | |
78 | # length immutability during iteration\r | |
79 | \r | |
80 | it = self.it\r | |
81 | self.assertEqual(len(it), n)\r | |
82 | it.next()\r | |
83 | self.assertEqual(len(it), n-1)\r | |
84 | self.mutate()\r | |
85 | self.assertRaises(RuntimeError, it.next)\r | |
86 | self.assertEqual(len(it), 0)\r | |
87 | \r | |
88 | ## ------- Concrete Type Tests -------\r | |
89 | \r | |
90 | class TestRepeat(TestInvariantWithoutMutations):\r | |
91 | \r | |
92 | def setUp(self):\r | |
93 | self.it = repeat(None, n)\r | |
94 | \r | |
95 | def test_no_len_for_infinite_repeat(self):\r | |
96 | # The repeat() object can also be infinite\r | |
97 | self.assertRaises(TypeError, len, repeat(None))\r | |
98 | \r | |
99 | class TestXrange(TestInvariantWithoutMutations):\r | |
100 | \r | |
101 | def setUp(self):\r | |
102 | self.it = iter(xrange(n))\r | |
103 | \r | |
104 | class TestXrangeCustomReversed(TestInvariantWithoutMutations):\r | |
105 | \r | |
106 | def setUp(self):\r | |
107 | self.it = reversed(xrange(n))\r | |
108 | \r | |
109 | class TestTuple(TestInvariantWithoutMutations):\r | |
110 | \r | |
111 | def setUp(self):\r | |
112 | self.it = iter(tuple(xrange(n)))\r | |
113 | \r | |
114 | ## ------- Types that should not be mutated during iteration -------\r | |
115 | \r | |
116 | class TestDeque(TestTemporarilyImmutable):\r | |
117 | \r | |
118 | def setUp(self):\r | |
119 | d = deque(xrange(n))\r | |
120 | self.it = iter(d)\r | |
121 | self.mutate = d.pop\r | |
122 | \r | |
123 | class TestDequeReversed(TestTemporarilyImmutable):\r | |
124 | \r | |
125 | def setUp(self):\r | |
126 | d = deque(xrange(n))\r | |
127 | self.it = reversed(d)\r | |
128 | self.mutate = d.pop\r | |
129 | \r | |
130 | class TestDictKeys(TestTemporarilyImmutable):\r | |
131 | \r | |
132 | def setUp(self):\r | |
133 | d = dict.fromkeys(xrange(n))\r | |
134 | self.it = iter(d)\r | |
135 | self.mutate = d.popitem\r | |
136 | \r | |
137 | class TestDictItems(TestTemporarilyImmutable):\r | |
138 | \r | |
139 | def setUp(self):\r | |
140 | d = dict.fromkeys(xrange(n))\r | |
141 | self.it = d.iteritems()\r | |
142 | self.mutate = d.popitem\r | |
143 | \r | |
144 | class TestDictValues(TestTemporarilyImmutable):\r | |
145 | \r | |
146 | def setUp(self):\r | |
147 | d = dict.fromkeys(xrange(n))\r | |
148 | self.it = d.itervalues()\r | |
149 | self.mutate = d.popitem\r | |
150 | \r | |
151 | class TestSet(TestTemporarilyImmutable):\r | |
152 | \r | |
153 | def setUp(self):\r | |
154 | d = set(xrange(n))\r | |
155 | self.it = iter(d)\r | |
156 | self.mutate = d.pop\r | |
157 | \r | |
158 | ## ------- Types that can mutate during iteration -------\r | |
159 | \r | |
160 | class TestList(TestInvariantWithoutMutations):\r | |
161 | \r | |
162 | def setUp(self):\r | |
163 | self.it = iter(range(n))\r | |
164 | \r | |
165 | def test_mutation(self):\r | |
166 | d = range(n)\r | |
167 | it = iter(d)\r | |
168 | it.next()\r | |
169 | it.next()\r | |
170 | self.assertEqual(len(it), n-2)\r | |
171 | d.append(n)\r | |
172 | self.assertEqual(len(it), n-1) # grow with append\r | |
173 | d[1:] = []\r | |
174 | self.assertEqual(len(it), 0)\r | |
175 | self.assertEqual(list(it), [])\r | |
176 | d.extend(xrange(20))\r | |
177 | self.assertEqual(len(it), 0)\r | |
178 | \r | |
179 | class TestListReversed(TestInvariantWithoutMutations):\r | |
180 | \r | |
181 | def setUp(self):\r | |
182 | self.it = reversed(range(n))\r | |
183 | \r | |
184 | def test_mutation(self):\r | |
185 | d = range(n)\r | |
186 | it = reversed(d)\r | |
187 | it.next()\r | |
188 | it.next()\r | |
189 | self.assertEqual(len(it), n-2)\r | |
190 | d.append(n)\r | |
191 | self.assertEqual(len(it), n-2) # ignore append\r | |
192 | d[1:] = []\r | |
193 | self.assertEqual(len(it), 0)\r | |
194 | self.assertEqual(list(it), []) # confirm invariant\r | |
195 | d.extend(xrange(20))\r | |
196 | self.assertEqual(len(it), 0)\r | |
197 | \r | |
198 | ## -- Check to make sure exceptions are not suppressed by __length_hint__()\r | |
199 | \r | |
200 | \r | |
201 | class BadLen(object):\r | |
202 | def __iter__(self): return iter(range(10))\r | |
203 | def __len__(self):\r | |
204 | raise RuntimeError('hello')\r | |
205 | \r | |
206 | class BadLengthHint(object):\r | |
207 | def __iter__(self): return iter(range(10))\r | |
208 | def __length_hint__(self):\r | |
209 | raise RuntimeError('hello')\r | |
210 | \r | |
211 | class NoneLengthHint(object):\r | |
212 | def __iter__(self): return iter(range(10))\r | |
213 | def __length_hint__(self):\r | |
214 | return None\r | |
215 | \r | |
216 | class TestLengthHintExceptions(unittest.TestCase):\r | |
217 | \r | |
218 | def test_issue1242657(self):\r | |
219 | self.assertRaises(RuntimeError, list, BadLen())\r | |
220 | self.assertRaises(RuntimeError, list, BadLengthHint())\r | |
221 | self.assertRaises(RuntimeError, [].extend, BadLen())\r | |
222 | self.assertRaises(RuntimeError, [].extend, BadLengthHint())\r | |
223 | self.assertRaises(RuntimeError, zip, BadLen())\r | |
224 | self.assertRaises(RuntimeError, zip, BadLengthHint())\r | |
225 | self.assertRaises(RuntimeError, filter, None, BadLen())\r | |
226 | self.assertRaises(RuntimeError, filter, None, BadLengthHint())\r | |
227 | self.assertRaises(RuntimeError, map, chr, BadLen())\r | |
228 | self.assertRaises(RuntimeError, map, chr, BadLengthHint())\r | |
229 | b = bytearray(range(10))\r | |
230 | self.assertRaises(RuntimeError, b.extend, BadLen())\r | |
231 | self.assertRaises(RuntimeError, b.extend, BadLengthHint())\r | |
232 | \r | |
233 | def test_invalid_hint(self):\r | |
234 | # Make sure an invalid result doesn't muck-up the works\r | |
235 | self.assertEqual(list(NoneLengthHint()), list(range(10)))\r | |
236 | \r | |
237 | \r | |
238 | def test_main():\r | |
239 | unittests = [\r | |
240 | TestRepeat,\r | |
241 | TestXrange,\r | |
242 | TestXrangeCustomReversed,\r | |
243 | TestTuple,\r | |
244 | TestDeque,\r | |
245 | TestDequeReversed,\r | |
246 | TestDictKeys,\r | |
247 | TestDictItems,\r | |
248 | TestDictValues,\r | |
249 | TestSet,\r | |
250 | TestList,\r | |
251 | TestListReversed,\r | |
252 | TestLengthHintExceptions,\r | |
253 | ]\r | |
254 | test_support.run_unittest(*unittests)\r | |
255 | \r | |
256 | if __name__ == "__main__":\r | |
257 | test_main()\r |