| 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 range(10) always reports its length as ten, |
| 13 |
but it=iter(range(10)) starts at ten, and then goes to nine after next(it). |
| 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, range 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 permanently 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 dynamically 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 itertools import repeat |
| 46 |
from collections import deque |
| 47 |
from operator import length_hint |
| 48 |
|
| 49 |
n = 10 |
| 50 |
|
| 51 |
|
| 52 |
class TestInvariantWithoutMutations: |
| 53 |
|
| 54 |
def test_invariant(self): |
| 55 |
it = self.it |
| 56 |
for i in reversed(range(1, n+1)): |
| 57 |
self.assertEqual(length_hint(it), i) |
| 58 |
next(it) |
| 59 |
self.assertEqual(length_hint(it), 0) |
| 60 |
self.assertRaises(StopIteration, next, it) |
| 61 |
self.assertEqual(length_hint(it), 0) |
| 62 |
|
| 63 |
class TestTemporarilyImmutable(TestInvariantWithoutMutations): |
| 64 |
|
| 65 |
def test_immutable_during_iteration(self): |
| 66 |
# objects such as deques, sets, and dictionaries enforce |
| 67 |
# length immutability during iteration |
| 68 |
|
| 69 |
it = self.it |
| 70 |
self.assertEqual(length_hint(it), n) |
| 71 |
next(it) |
| 72 |
self.assertEqual(length_hint(it), n-1) |
| 73 |
self.mutate() |
| 74 |
self.assertRaises(RuntimeError, next, it) |
| 75 |
self.assertEqual(length_hint(it), 0) |
| 76 |
|
| 77 |
## ------- Concrete Type Tests ------- |
| 78 |
|
| 79 |
class TestRepeat(TestInvariantWithoutMutations, unittest.TestCase): |
| 80 |
|
| 81 |
def setUp(self): |
| 82 |
self.it = repeat(None, n) |
| 83 |
|
| 84 |
class TestXrange(TestInvariantWithoutMutations, unittest.TestCase): |
| 85 |
|
| 86 |
def setUp(self): |
| 87 |
self.it = iter(range(n)) |
| 88 |
|
| 89 |
class TestXrangeCustomReversed(TestInvariantWithoutMutations, unittest.TestCase): |
| 90 |
|
| 91 |
def setUp(self): |
| 92 |
self.it = reversed(range(n)) |
| 93 |
|
| 94 |
class TestTuple(TestInvariantWithoutMutations, unittest.TestCase): |
| 95 |
|
| 96 |
def setUp(self): |
| 97 |
self.it = iter(tuple(range(n))) |
| 98 |
|
| 99 |
## ------- Types that should not be mutated during iteration ------- |
| 100 |
|
| 101 |
class TestDeque(TestTemporarilyImmutable, unittest.TestCase): |
| 102 |
|
| 103 |
def setUp(self): |
| 104 |
d = deque(range(n)) |
| 105 |
self.it = iter(d) |
| 106 |
self.mutate = d.pop |
| 107 |
|
| 108 |
class TestDequeReversed(TestTemporarilyImmutable, unittest.TestCase): |
| 109 |
|
| 110 |
def setUp(self): |
| 111 |
d = deque(range(n)) |
| 112 |
self.it = reversed(d) |
| 113 |
self.mutate = d.pop |
| 114 |
|
| 115 |
class TestDictKeys(TestTemporarilyImmutable, unittest.TestCase): |
| 116 |
|
| 117 |
def setUp(self): |
| 118 |
d = dict.fromkeys(range(n)) |
| 119 |
self.it = iter(d) |
| 120 |
self.mutate = d.popitem |
| 121 |
|
| 122 |
class TestDictItems(TestTemporarilyImmutable, unittest.TestCase): |
| 123 |
|
| 124 |
def setUp(self): |
| 125 |
d = dict.fromkeys(range(n)) |
| 126 |
self.it = iter(d.items()) |
| 127 |
self.mutate = d.popitem |
| 128 |
|
| 129 |
class TestDictValues(TestTemporarilyImmutable, unittest.TestCase): |
| 130 |
|
| 131 |
def setUp(self): |
| 132 |
d = dict.fromkeys(range(n)) |
| 133 |
self.it = iter(d.values()) |
| 134 |
self.mutate = d.popitem |
| 135 |
|
| 136 |
class TestSet(TestTemporarilyImmutable, unittest.TestCase): |
| 137 |
|
| 138 |
def setUp(self): |
| 139 |
d = set(range(n)) |
| 140 |
self.it = iter(d) |
| 141 |
self.mutate = d.pop |
| 142 |
|
| 143 |
## ------- Types that can mutate during iteration ------- |
| 144 |
|
| 145 |
class TestList(TestInvariantWithoutMutations, unittest.TestCase): |
| 146 |
|
| 147 |
def setUp(self): |
| 148 |
self.it = iter(range(n)) |
| 149 |
|
| 150 |
def test_mutation(self): |
| 151 |
d = list(range(n)) |
| 152 |
it = iter(d) |
| 153 |
next(it) |
| 154 |
next(it) |
| 155 |
self.assertEqual(length_hint(it), n - 2) |
| 156 |
d.append(n) |
| 157 |
self.assertEqual(length_hint(it), n - 1) # grow with append |
| 158 |
d[1:] = [] |
| 159 |
self.assertEqual(length_hint(it), 0) |
| 160 |
self.assertEqual(list(it), []) |
| 161 |
d.extend(range(20)) |
| 162 |
self.assertEqual(length_hint(it), 0) |
| 163 |
|
| 164 |
|
| 165 |
class TestListReversed(TestInvariantWithoutMutations, unittest.TestCase): |
| 166 |
|
| 167 |
def setUp(self): |
| 168 |
self.it = reversed(range(n)) |
| 169 |
|
| 170 |
def test_mutation(self): |
| 171 |
d = list(range(n)) |
| 172 |
it = reversed(d) |
| 173 |
next(it) |
| 174 |
next(it) |
| 175 |
self.assertEqual(length_hint(it), n - 2) |
| 176 |
d.append(n) |
| 177 |
self.assertEqual(length_hint(it), n - 2) # ignore append |
| 178 |
d[1:] = [] |
| 179 |
self.assertEqual(length_hint(it), 0) |
| 180 |
self.assertEqual(list(it), []) # confirm invariant |
| 181 |
d.extend(range(20)) |
| 182 |
self.assertEqual(length_hint(it), 0) |
| 183 |
|
| 184 |
## -- Check to make sure exceptions are not suppressed by __length_hint__() |
| 185 |
|
| 186 |
|
| 187 |
class BadLen(object): |
| 188 |
def __iter__(self): |
| 189 |
return iter(range(10)) |
| 190 |
|
| 191 |
def __len__(self): |
| 192 |
raise RuntimeError('hello') |
| 193 |
|
| 194 |
|
| 195 |
class BadLengthHint(object): |
| 196 |
def __iter__(self): |
| 197 |
return iter(range(10)) |
| 198 |
|
| 199 |
def __length_hint__(self): |
| 200 |
raise RuntimeError('hello') |
| 201 |
|
| 202 |
|
| 203 |
class NoneLengthHint(object): |
| 204 |
def __iter__(self): |
| 205 |
return iter(range(10)) |
| 206 |
|
| 207 |
def __length_hint__(self): |
| 208 |
return NotImplemented |
| 209 |
|
| 210 |
|
| 211 |
class TestLengthHintExceptions(unittest.TestCase): |
| 212 |
|
| 213 |
def test_issue1242657(self): |
| 214 |
self.assertRaises(RuntimeError, list, BadLen()) |
| 215 |
self.assertRaises(RuntimeError, list, BadLengthHint()) |
| 216 |
self.assertRaises(RuntimeError, [].extend, BadLen()) |
| 217 |
self.assertRaises(RuntimeError, [].extend, BadLengthHint()) |
| 218 |
b = bytearray(range(10)) |
| 219 |
self.assertRaises(RuntimeError, b.extend, BadLen()) |
| 220 |
self.assertRaises(RuntimeError, b.extend, BadLengthHint()) |
| 221 |
|
| 222 |
def test_invalid_hint(self): |
| 223 |
# Make sure an invalid result doesn't muck-up the works |
| 224 |
self.assertEqual(list(NoneLengthHint()), list(range(10))) |
| 225 |
|
| 226 |
|
| 227 |
if __name__ == "__main__": |
| 228 |
unittest.main() |