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 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 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 ## -- Check to make sure exceptions are not suppressed by __length_hint__() 199 200 201 class BadLen(object): 202 def __iter__(self): return iter(range(10)) 203 def __len__(self): 204 raise RuntimeError('hello') 205 206 class BadLengthHint(object): 207 def __iter__(self): return iter(range(10)) 208 def __length_hint__(self): 209 raise RuntimeError('hello') 210 211 class NoneLengthHint(object): 212 def __iter__(self): return iter(range(10)) 213 def __length_hint__(self): 214 return None 215 216 class 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 238 def 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 256 if __name__ == "__main__": 257 test_main() 258
