""" 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 permanently 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 dynamically 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 | |
from collections import deque | |
from __builtin__ import len as _len | |
n = 10 | |
def len(obj): | |
try: | |
return _len(obj) | |
except TypeError: | |
try: | |
# note: this is an internal undocumented API, | |
# don't rely on it in your own programs | |
return obj.__length_hint__() | |
except AttributeError: | |
raise TypeError | |
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) | |
## -- Check to make sure exceptions are not suppressed by __length_hint__() | |
class BadLen(object): | |
def __iter__(self): return iter(range(10)) | |
def __len__(self): | |
raise RuntimeError('hello') | |
class BadLengthHint(object): | |
def __iter__(self): return iter(range(10)) | |
def __length_hint__(self): | |
raise RuntimeError('hello') | |
class NoneLengthHint(object): | |
def __iter__(self): return iter(range(10)) | |
def __length_hint__(self): | |
return None | |
class TestLengthHintExceptions(unittest.TestCase): | |
def test_issue1242657(self): | |
self.assertRaises(RuntimeError, list, BadLen()) | |
self.assertRaises(RuntimeError, list, BadLengthHint()) | |
self.assertRaises(RuntimeError, [].extend, BadLen()) | |
self.assertRaises(RuntimeError, [].extend, BadLengthHint()) | |
self.assertRaises(RuntimeError, zip, BadLen()) | |
self.assertRaises(RuntimeError, zip, BadLengthHint()) | |
self.assertRaises(RuntimeError, filter, None, BadLen()) | |
self.assertRaises(RuntimeError, filter, None, BadLengthHint()) | |
self.assertRaises(RuntimeError, map, chr, BadLen()) | |
self.assertRaises(RuntimeError, map, chr, BadLengthHint()) | |
b = bytearray(range(10)) | |
self.assertRaises(RuntimeError, b.extend, BadLen()) | |
self.assertRaises(RuntimeError, b.extend, BadLengthHint()) | |
def test_invalid_hint(self): | |
# Make sure an invalid result doesn't muck-up the works | |
self.assertEqual(list(NoneLengthHint()), list(range(10))) | |
def test_main(): | |
unittests = [ | |
TestRepeat, | |
TestXrange, | |
TestXrangeCustomReversed, | |
TestTuple, | |
TestDeque, | |
TestDequeReversed, | |
TestDictKeys, | |
TestDictItems, | |
TestDictValues, | |
TestSet, | |
TestList, | |
TestListReversed, | |
TestLengthHintExceptions, | |
] | |
test_support.run_unittest(*unittests) | |
if __name__ == "__main__": | |
test_main() |