0001 """ Test Iterator Length Transparency 0002 0003 Some functions or methods which accept general iterable arguments have 0004 optional, more efficient code paths if they know how many items to expect. 0005 For instance, map(func, iterable), will pre-allocate the exact amount of 0006 space required whenever the iterable can report its length. 0007 0008 The desired invariant is: len(it)==len(list(it)). 0009 0010 A complication is that an iterable and iterator can be the same object. To 0011 maintain the invariant, an iterator needs to dynamically update its length. 0012 For instance, an iterable such as xrange(10) always reports its length as ten, 0013 but it=iter(xrange(10)) starts at ten, and then goes to nine after it.next(). 0014 Having this capability means that map() can ignore the distinction between 0015 map(func, iterable) and map(func, iter(iterable)). 0016 0017 When the iterable is immutable, the implementation can straight-forwardly 0018 report the original length minus the cumulative number of calls to next(). 0019 This is the case for tuples, xrange objects, and itertools.repeat(). 0020 0021 Some containers become temporarily immutable during iteration. This includes 0022 dicts, sets, and collections.deque. Their implementation is equally simple 0023 though they need to permantently set their length to zero whenever there is 0024 an attempt to iterate after a length mutation. 0025 0026 The situation slightly more involved whenever an object allows length mutation 0027 during iteration. Lists and sequence iterators are dynanamically updatable. 0028 So, if a list is extended during iteration, the iterator will continue through 0029 the new items. If it shrinks to a point before the most recent iteration, 0030 then no further items are available and the length is reported at zero. 0031 0032 Reversed objects can also be wrapped around mutable objects; however, any 0033 appends after the current position are ignored. Any other approach leads 0034 to confusion and possibly returning the same item more than once. 0035 0036 The iterators not listed above, such as enumerate and the other itertools, 0037 are not length transparent because they have no way to distinguish between 0038 iterables that report static length and iterators whose length changes with 0039 each call (i.e. the difference between enumerate('abc') and 0040 enumerate(iter('abc')). 0041 0042 """ 0043 0044 import unittest 0045 from test import test_support 0046 from itertools import repeat, count 0047 from collections import deque 0048 from UserList import UserList 0049 0050 n = 10 0051 0052 class TestInvariantWithoutMutations(unittest.TestCase): 0053 0054 def test_invariant(self): 0055 it = self.it 0056 for i in reversed(xrange(1, n+1)): 0057 self.assertEqual(len(it), i) 0058 it.next() 0059 self.assertEqual(len(it), 0) 0060 self.assertRaises(StopIteration, it.next) 0061 self.assertEqual(len(it), 0) 0062 0063 class TestTemporarilyImmutable(TestInvariantWithoutMutations): 0064 0065 def test_immutable_during_iteration(self): 0066 # objects such as deques, sets, and dictionaries enforce 0067 # length immutability during iteration 0068 0069 it = self.it 0070 self.assertEqual(len(it), n) 0071 it.next() 0072 self.assertEqual(len(it), n-1) 0073 self.mutate() 0074 self.assertRaises(RuntimeError, it.next) 0075 self.assertEqual(len(it), 0) 0076 0077 ## ------- Concrete Type Tests ------- 0078 0079 class TestRepeat(TestInvariantWithoutMutations): 0080 0081 def setUp(self): 0082 self.it = repeat(None, n) 0083 0084 def test_no_len_for_infinite_repeat(self): 0085 # The repeat() object can also be infinite 0086 self.assertRaises(TypeError, len, repeat(None)) 0087 0088 class TestXrange(TestInvariantWithoutMutations): 0089 0090 def setUp(self): 0091 self.it = iter(xrange(n)) 0092 0093 class TestXrangeCustomReversed(TestInvariantWithoutMutations): 0094 0095 def setUp(self): 0096 self.it = reversed(xrange(n)) 0097 0098 class TestTuple(TestInvariantWithoutMutations): 0099 0100 def setUp(self): 0101 self.it = iter(tuple(xrange(n))) 0102 0103 ## ------- Types that should not be mutated during iteration ------- 0104 0105 class TestDeque(TestTemporarilyImmutable): 0106 0107 def setUp(self): 0108 d = deque(xrange(n)) 0109 self.it = iter(d) 0110 self.mutate = d.pop 0111 0112 class TestDequeReversed(TestTemporarilyImmutable): 0113 0114 def setUp(self): 0115 d = deque(xrange(n)) 0116 self.it = reversed(d) 0117 self.mutate = d.pop 0118 0119 class TestDictKeys(TestTemporarilyImmutable): 0120 0121 def setUp(self): 0122 d = dict.fromkeys(xrange(n)) 0123 self.it = iter(d) 0124 self.mutate = d.popitem 0125 0126 class TestDictItems(TestTemporarilyImmutable): 0127 0128 def setUp(self): 0129 d = dict.fromkeys(xrange(n)) 0130 self.it = d.iteritems() 0131 self.mutate = d.popitem 0132 0133 class TestDictValues(TestTemporarilyImmutable): 0134 0135 def setUp(self): 0136 d = dict.fromkeys(xrange(n)) 0137 self.it = d.itervalues() 0138 self.mutate = d.popitem 0139 0140 class TestSet(TestTemporarilyImmutable): 0141 0142 def setUp(self): 0143 d = set(xrange(n)) 0144 self.it = iter(d) 0145 self.mutate = d.pop 0146 0147 ## ------- Types that can mutate during iteration ------- 0148 0149 class TestList(TestInvariantWithoutMutations): 0150 0151 def setUp(self): 0152 self.it = iter(range(n)) 0153 0154 def test_mutation(self): 0155 d = range(n) 0156 it = iter(d) 0157 it.next() 0158 it.next() 0159 self.assertEqual(len(it), n-2) 0160 d.append(n) 0161 self.assertEqual(len(it), n-1) # grow with append 0162 d[1:] = [] 0163 self.assertEqual(len(it), 0) 0164 self.assertEqual(list(it), []) 0165 d.extend(xrange(20)) 0166 self.assertEqual(len(it), 0) 0167 0168 class TestListReversed(TestInvariantWithoutMutations): 0169 0170 def setUp(self): 0171 self.it = reversed(range(n)) 0172 0173 def test_mutation(self): 0174 d = range(n) 0175 it = reversed(d) 0176 it.next() 0177 it.next() 0178 self.assertEqual(len(it), n-2) 0179 d.append(n) 0180 self.assertEqual(len(it), n-2) # ignore append 0181 d[1:] = [] 0182 self.assertEqual(len(it), 0) 0183 self.assertEqual(list(it), []) # confirm invariant 0184 d.extend(xrange(20)) 0185 self.assertEqual(len(it), 0) 0186 0187 class TestSeqIter(TestInvariantWithoutMutations): 0188 0189 def setUp(self): 0190 self.it = iter(UserList(range(n))) 0191 0192 def test_mutation(self): 0193 d = UserList(range(n)) 0194 it = iter(d) 0195 it.next() 0196 it.next() 0197 self.assertEqual(len(it), n-2) 0198 d.append(n) 0199 self.assertEqual(len(it), n-1) # grow with append 0200 d[1:] = [] 0201 self.assertEqual(len(it), 0) 0202 self.assertEqual(list(it), []) 0203 d.extend(xrange(20)) 0204 self.assertEqual(len(it), 0) 0205 0206 class TestSeqIterReversed(TestInvariantWithoutMutations): 0207 0208 def setUp(self): 0209 self.it = reversed(UserList(range(n))) 0210 0211 def test_mutation(self): 0212 d = UserList(range(n)) 0213 it = reversed(d) 0214 it.next() 0215 it.next() 0216 self.assertEqual(len(it), n-2) 0217 d.append(n) 0218 self.assertEqual(len(it), n-2) # ignore append 0219 d[1:] = [] 0220 self.assertEqual(len(it), 0) 0221 self.assertEqual(list(it), []) # confirm invariant 0222 d.extend(xrange(20)) 0223 self.assertEqual(len(it), 0) 0224 0225 0226 0227 if __name__ == "__main__": 0228 0229 unittests = [ 0230 TestRepeat, 0231 TestXrange, 0232 TestXrangeCustomReversed, 0233 TestTuple, 0234 TestDeque, 0235 TestDequeReversed, 0236 TestDictKeys, 0237 TestDictItems, 0238 TestDictValues, 0239 TestSet, 0240 TestList, 0241 TestListReversed, 0242 TestSeqIter, 0243 TestSeqIterReversed, 0244 ] 0245 test_support.run_unittest(*unittests) 0246
Generated by PyXR 0.9.4