* 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
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)