Lib/test/test_iterlen.py

   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 permantently 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 dynanamically 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()