* Add unittests for iterators that report their length

* Document the differences between them
* Fix corner cases covered by the unittests
* Use Py_RETURN_NONE where possible for dictionaries

1 files changed, 245 insertions, 0 deletions

diff --git a/Lib/test/test_iterlen.py b/Lib/test/test_iterlen.py
new file mode 100644
index 0000000..f77169f
--- /dev/null
+++ b/Lib/test/test_iterlen.py
@@ -0,0 +1,245 @@
+""" Test Iterator Length Transparency
+
+Some functions or methods which accept general iterable arguments have
+optional, more efficient code paths if they know how many items to expect.
+For instance, map(func, iterable), will pre-allocate the exact amount of
+space required whenever the iterable can report its length.
+
+The desired invariant is:  len(it)==len(list(it)).
+
+A complication is that an iterable and iterator can be the same object. To
+maintain the invariant, an iterator needs to dynamically update its length.
+For instance, an iterable such as xrange(10) always reports its length as ten,
+but it=iter(xrange(10)) starts at ten, and then goes to nine after it.next().
+Having this capability means that map() can ignore the distinction between
+map(func, iterable) and map(func, iter(iterable)).
+
+When the iterable is immutable, the implementation can straight-forwardly
+report the original length minus the cumulative number of calls to next().
+This is the case for tuples, xrange objects, and itertools.repeat().
+
+Some containers become temporarily immutable during iteration.  This includes
+dicts, sets, and collections.deque.  Their implementation is equally simple
+though they need to permantently set their length to zero whenever there is
+an attempt to iterate after a length mutation.
+
+The situation slightly more involved whenever an object allows length mutation
+during iteration.  Lists and sequence iterators are dynanamically updatable.
+So, if a list is extended during iteration, the iterator will continue through
+the new items.  If it shrinks to a point before the most recent iteration,
+then no further items are available and the length is reported at zero.
+
+Reversed objects can also be wrapped around mutable objects; however, any
+appends after the current position are ignored.  Any other approach leads
+to confusion and possibly returning the same item more than once.
+
+The iterators not listed above, such as enumerate and the other itertools,
+are not length transparent because they have no way to distinguish between
+iterables that report static length and iterators whose length changes with
+each call (i.e. the difference between enumerate('abc') and
+enumerate(iter('abc')).
+
+"""
+
+import unittest
+from test import test_support
+from itertools import repeat, count
+from collections import deque
+from UserList import UserList
+
+n = 10
+
+class TestInvariantWithoutMutations(unittest.TestCase):
+
+    def test_invariant(self):
+            it = self.it
+            for i in reversed(xrange(1, n+1)):
+                self.assertEqual(len(it), i)
+                it.next()
+            self.assertEqual(len(it), 0)
+            self.assertRaises(StopIteration, it.next)
+            self.assertEqual(len(it), 0)
+
+class TestTemporarilyImmutable(TestInvariantWithoutMutations):
+
+    def test_immutable_during_iteration(self):
+        # objects such as deques, sets, and dictionaries enforce
+        # length immutability  during iteration
+
+        it = self.it
+        self.assertEqual(len(it), n)
+        it.next()
+        self.assertEqual(len(it), n-1)
+        self.mutate()
+        self.assertRaises(RuntimeError, it.next)
+        self.assertEqual(len(it), 0)
+
+## ------- Concrete Type Tests -------
+
+class TestRepeat(TestInvariantWithoutMutations):
+
+    def setUp(self):
+        self.it = repeat(None, n)
+
+    def test_no_len_for_infinite_repeat(self):
+        # The repeat() object can also be infinite
+        self.assertRaises(TypeError, len, repeat(None))
+
+class TestXrange(TestInvariantWithoutMutations):
+
+    def setUp(self):
+        self.it = iter(xrange(n))
+
+class TestXrangeCustomReversed(TestInvariantWithoutMutations):
+
+    def setUp(self):
+        self.it = reversed(xrange(n))
+
+class TestTuple(TestInvariantWithoutMutations):
+
+    def setUp(self):
+        self.it = iter(tuple(xrange(n)))
+
+## ------- Types that should not be mutated during iteration -------
+
+class TestDeque(TestTemporarilyImmutable):
+
+    def setUp(self):
+        d = deque(xrange(n))
+        self.it = iter(d)
+        self.mutate = d.pop
+
+class TestDequeReversed(TestTemporarilyImmutable):
+
+    def setUp(self):
+        d = deque(xrange(n))
+        self.it = reversed(d)
+        self.mutate = d.pop
+
+class TestDictKeys(TestTemporarilyImmutable):
+
+    def setUp(self):
+        d = dict.fromkeys(xrange(n))
+        self.it = iter(d)
+        self.mutate = d.popitem
+
+class TestDictItems(TestTemporarilyImmutable):
+
+    def setUp(self):
+        d = dict.fromkeys(xrange(n))
+        self.it = d.iteritems()
+        self.mutate = d.popitem
+
+class TestDictValues(TestTemporarilyImmutable):
+
+    def setUp(self):
+        d = dict.fromkeys(xrange(n))
+        self.it = d.itervalues()
+        self.mutate = d.popitem
+
+class TestSet(TestTemporarilyImmutable):
+
+    def setUp(self):
+        d = set(xrange(n))
+        self.it = iter(d)
+        self.mutate = d.pop
+
+## ------- Types that can mutate during iteration -------
+
+class TestList(TestInvariantWithoutMutations):
+
+    def setUp(self):
+        self.it = iter(range(n))
+
+    def test_mutation(self):
+        d = range(n)
+        it = iter(d)
+        it.next()
+        it.next()
+        self.assertEqual(len(it), n-2)
+        d.append(n)
+        self.assertEqual(len(it), n-1)  # grow with append
+        d[1:] = []
+        self.assertEqual(len(it), 0)
+        self.assertEqual(list(it), [])
+        d.extend(xrange(20))
+        self.assertEqual(len(it), 0)
+
+class TestListReversed(TestInvariantWithoutMutations):
+
+    def setUp(self):
+        self.it = reversed(range(n))
+
+    def test_mutation(self):
+        d = range(n)
+        it = reversed(d)
+        it.next()
+        it.next()
+        self.assertEqual(len(it), n-2)
+        d.append(n)
+        self.assertEqual(len(it), n-2)  # ignore append
+        d[1:] = []
+        self.assertEqual(len(it), 0)
+        self.assertEqual(list(it), [])  # confirm invariant
+        d.extend(xrange(20))
+        self.assertEqual(len(it), 0)
+
+class TestSeqIter(TestInvariantWithoutMutations):
+
+    def setUp(self):
+        self.it = iter(UserList(range(n)))
+
+    def test_mutation(self):
+        d = UserList(range(n))
+        it = iter(d)
+        it.next()
+        it.next()
+        self.assertEqual(len(it), n-2)
+        d.append(n)
+        self.assertEqual(len(it), n-1)  # grow with append
+        d[1:] = []
+        self.assertEqual(len(it), 0)
+        self.assertEqual(list(it), [])
+        d.extend(xrange(20))
+        self.assertEqual(len(it), 0)
+
+class TestSeqIterReversed(TestInvariantWithoutMutations):
+
+    def setUp(self):
+        self.it = reversed(UserList(range(n)))
+
+    def test_mutation(self):
+        d = UserList(range(n))
+        it = reversed(d)
+        it.next()
+        it.next()
+        self.assertEqual(len(it), n-2)
+        d.append(n)
+        self.assertEqual(len(it), n-2)  # ignore append
+        d[1:] = []
+        self.assertEqual(len(it), 0)
+        self.assertEqual(list(it), [])  # confirm invariant
+        d.extend(xrange(20))
+        self.assertEqual(len(it), 0)
+
+
+
+if __name__ == "__main__":
+
+    unittests = [
+        TestRepeat,
+        TestXrange,
+        TestXrangeCustomReversed,
+        TestTuple,
+        TestDeque,
+        TestDequeReversed,
+        TestDictKeys,
+        TestDictItems,
+        TestDictValues,
+        TestSet,
+        TestList,
+        TestListReversed,
+        TestSeqIter,
+        TestSeqIterReversed,
+    ]
+    test_support.run_unittest(*unittests)