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