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 UserList import UserList

    49 from __builtin__ import len as _len

    50 

    51 n = 10

    52 

    53 def len(obj):

    54     try:

    55         return _len(obj)

    56     except TypeError:

    57         try:

    58             # note: this is an internal undocumented API,

    59             # don't rely on it in your own programs

    60             return obj.__length_hint__()

    61         except AttributeError:

    62             raise TypeError

    63 

    64 class TestInvariantWithoutMutations(unittest.TestCase):

    65 

    66     def test_invariant(self):

    67         it = self.it

    68         for i in reversed(xrange(1, n+1)):

    69             self.assertEqual(len(it), i)

    70             it.next()

    71         self.assertEqual(len(it), 0)

    72         self.assertRaises(StopIteration, it.next)

    73         self.assertEqual(len(it), 0)

    74 

    75 class TestTemporarilyImmutable(TestInvariantWithoutMutations):

    76 

    77     def test_immutable_during_iteration(self):

    78         # objects such as deques, sets, and dictionaries enforce

    79         # length immutability  during iteration

    80 

    81         it = self.it

    82         self.assertEqual(len(it), n)

    83         it.next()

    84         self.assertEqual(len(it), n-1)

    85         self.mutate()

    86         self.assertRaises(RuntimeError, it.next)

    87         self.assertEqual(len(it), 0)

    88 

    89 ## ------- Concrete Type Tests -------

    90 

    91 class TestRepeat(TestInvariantWithoutMutations):

    92 

    93     def setUp(self):

    94         self.it = repeat(None, n)

    95 

    96     def test_no_len_for_infinite_repeat(self):

    97         # The repeat() object can also be infinite

    98         self.assertRaises(TypeError, len, repeat(None))

    99 

   100 class TestXrange(TestInvariantWithoutMutations):

   101 

   102     def setUp(self):

   103         self.it = iter(xrange(n))

   104 

   105 class TestXrangeCustomReversed(TestInvariantWithoutMutations):

   106 

   107     def setUp(self):

   108         self.it = reversed(xrange(n))

   109 

   110 class TestTuple(TestInvariantWithoutMutations):

   111 

   112     def setUp(self):

   113         self.it = iter(tuple(xrange(n)))

   114 

   115 ## ------- Types that should not be mutated during iteration -------

   116 

   117 class TestDeque(TestTemporarilyImmutable):

   118 

   119     def setUp(self):

   120         d = deque(xrange(n))

   121         self.it = iter(d)

   122         self.mutate = d.pop

   123 

   124 class TestDequeReversed(TestTemporarilyImmutable):

   125 

   126     def setUp(self):

   127         d = deque(xrange(n))

   128         self.it = reversed(d)

   129         self.mutate = d.pop

   130 

   131 class TestDictKeys(TestTemporarilyImmutable):

   132 

   133     def setUp(self):

   134         d = dict.fromkeys(xrange(n))

   135         self.it = iter(d)

   136         self.mutate = d.popitem

   137 

   138 class TestDictItems(TestTemporarilyImmutable):

   139 

   140     def setUp(self):

   141         d = dict.fromkeys(xrange(n))

   142         self.it = d.iteritems()

   143         self.mutate = d.popitem

   144 

   145 class TestDictValues(TestTemporarilyImmutable):

   146 

   147     def setUp(self):

   148         d = dict.fromkeys(xrange(n))

   149         self.it = d.itervalues()

   150         self.mutate = d.popitem

   151 

   152 class TestSet(TestTemporarilyImmutable):

   153 

   154     def setUp(self):

   155         d = set(xrange(n))

   156         self.it = iter(d)

   157         self.mutate = d.pop

   158 

   159 ## ------- Types that can mutate during iteration -------

   160 

   161 class TestList(TestInvariantWithoutMutations):

   162 

   163     def setUp(self):

   164         self.it = iter(range(n))

   165 

   166     def test_mutation(self):

   167         d = range(n)

   168         it = iter(d)

   169         it.next()

   170         it.next()

   171         self.assertEqual(len(it), n-2)

   172         d.append(n)

   173         self.assertEqual(len(it), n-1)  # grow with append

   174         d[1:] = []

   175         self.assertEqual(len(it), 0)

   176         self.assertEqual(list(it), [])

   177         d.extend(xrange(20))

   178         self.assertEqual(len(it), 0)

   179 

   180 class TestListReversed(TestInvariantWithoutMutations):

   181 

   182     def setUp(self):

   183         self.it = reversed(range(n))

   184 

   185     def test_mutation(self):

   186         d = range(n)

   187         it = reversed(d)

   188         it.next()

   189         it.next()

   190         self.assertEqual(len(it), n-2)

   191         d.append(n)

   192         self.assertEqual(len(it), n-2)  # ignore append

   193         d[1:] = []

   194         self.assertEqual(len(it), 0)

   195         self.assertEqual(list(it), [])  # confirm invariant

   196         d.extend(xrange(20))

   197         self.assertEqual(len(it), 0)

   198 

   199 class TestSeqIter(TestInvariantWithoutMutations):

   200 

   201     def setUp(self):

   202         self.it = iter(UserList(range(n)))

   203 

   204     def test_mutation(self):

   205         d = UserList(range(n))

   206         it = iter(d)

   207         it.next()

   208         it.next()

   209         self.assertEqual(len(it), n-2)

   210         d.append(n)

   211         self.assertEqual(len(it), n-1)  # grow with append

   212         d[1:] = []

   213         self.assertEqual(len(it), 0)

   214         self.assertEqual(list(it), [])

   215         d.extend(xrange(20))

   216         self.assertEqual(len(it), 0)

   217 

   218 class TestSeqIterReversed(TestInvariantWithoutMutations):

   219 

   220     def setUp(self):

   221         self.it = reversed(UserList(range(n)))

   222 

   223     def test_mutation(self):

   224         d = UserList(range(n))

   225         it = reversed(d)

   226         it.next()

   227         it.next()

   228         self.assertEqual(len(it), n-2)

   229         d.append(n)

   230         self.assertEqual(len(it), n-2)  # ignore append

   231         d[1:] = []

   232         self.assertEqual(len(it), 0)

   233         self.assertEqual(list(it), [])  # confirm invariant

   234         d.extend(xrange(20))

   235         self.assertEqual(len(it), 0)

   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         TestSeqIter,

   253         TestSeqIterReversed,

   254     ]

   255     test_support.run_unittest(*unittests)

   256 

   257 if __name__ == "__main__":

   258     test_main()