Author: Maciej Fijalkowski <[email protected]>
Branch:
Changeset: r58910:bed016253ff4
Date: 2012-11-14 14:04 +0100
http://bitbucket.org/pypy/pypy/changeset/bed016253ff4/
Log: (pjenvey, fijal reviewing) merge length-hint branch.
This branch brings __length_hint__ special method to PyPy
implementing PEP that number I don't memorize and I don't have
internet.
diff --git a/pypy/interpreter/baseobjspace.py b/pypy/interpreter/baseobjspace.py
--- a/pypy/interpreter/baseobjspace.py
+++ b/pypy/interpreter/baseobjspace.py
@@ -862,18 +862,10 @@
"""
# If we can guess the expected length we can preallocate.
try:
- lgt_estimate = self.len_w(w_iterable)
- except OperationError, o:
- if (not o.match(self, self.w_AttributeError) and
- not o.match(self, self.w_TypeError)):
- raise
- items = []
- else:
- try:
- items = newlist_hint(lgt_estimate)
- except MemoryError:
- items = [] # it might have lied
- #
+ items = newlist_hint(self.length_hint(w_iterable, 0))
+ except MemoryError:
+ items = [] # it might have lied
+
tp = self.type(w_iterator)
while True:
unpackiterable_driver.jit_merge_point(tp=tp,
@@ -933,6 +925,36 @@
return self._unpackiterable_known_length_jitlook(w_iterator,
expected_length)
+ def length_hint(self, w_obj, default):
+ """Return the length of an object, consulting its __length_hint__
+ method if necessary.
+ """
+ try:
+ return self.len_w(w_obj)
+ except OperationError, e:
+ if not (e.match(self, self.w_TypeError) or
+ e.match(self, self.w_AttributeError)):
+ raise
+
+ w_descr = self.lookup(w_obj, '__length_hint__')
+ if w_descr is None:
+ return default
+ try:
+ w_hint = self.get_and_call_function(w_descr, w_obj)
+ except OperationError, e:
+ if not (e.match(self, self.w_TypeError) or
+ e.match(self, self.w_AttributeError)):
+ raise
+ return default
+ if self.is_w(w_hint, self.w_NotImplemented):
+ return default
+
+ hint = self.int_w(w_hint)
+ if hint < 0:
+ raise OperationError(self.w_ValueError, self.wrap(
+ "__length_hint__() should return >= 0"))
+ return hint
+
def fixedview(self, w_iterable, expected_length=-1):
""" A fixed list view of w_iterable. Don't modify the result
"""
@@ -969,6 +991,10 @@
def newlist_str(self, list_s):
return self.newlist([self.wrap(s) for s in list_s])
+ def newlist_hint(self, sizehint):
+ from pypy.objspace.std.listobject import make_empty_list_with_size
+ return make_empty_list_with_size(self, sizehint)
+
@jit.unroll_safe
def exception_match(self, w_exc_type, w_check_class):
"""Checks if the given exception type matches 'w_check_class'."""
diff --git a/pypy/module/__builtin__/app_functional.py
b/pypy/module/__builtin__/app_functional.py
--- a/pypy/module/__builtin__/app_functional.py
+++ b/pypy/module/__builtin__/app_functional.py
@@ -2,6 +2,9 @@
Plain Python definition of the builtin functions oriented towards
functional programming.
"""
+from __future__ import with_statement
+import operator
+from __pypy__ import resizelist_hint, newlist_hint
# ____________________________________________________________
@@ -66,38 +69,66 @@
if num_collections == 1:
if none_func:
return list(collections[0])
- else:
- # Special case for the really common case of a single collection,
- # this can be eliminated if we could unroll that loop that creates
- # `args` based on whether or not len(collections) was constant
- result = []
- for item in collections[0]:
+ # Special case for the really common case of a single collection,
+ # this can be eliminated if we could unroll that loop that creates
+ # `args` based on whether or not len(collections) was constant
+ seq = collections[0]
+ with _ManagedNewlistHint(operator._length_hint(seq, 0)) as result:
+ for item in seq:
result.append(func(item))
return result
- result = []
- # Pair of (iterator, has_finished)
- iterators = [(iter(seq), False) for seq in collections]
- while True:
- cont = False
- args = []
- for idx, (iterator, has_finished) in enumerate(iterators):
- val = None
- if not has_finished:
- try:
- val = next(iterator)
- except StopIteration:
- iterators[idx] = (None, True)
+
+ # Gather the iterators (pair of (iter, has_finished)) and guess the
+ # result length (the max of the input lengths)
+ iterators = []
+ max_hint = 0
+ for seq in collections:
+ iterators.append((iter(seq), False))
+ max_hint = max(max_hint, operator._length_hint(seq, 0))
+
+ with _ManagedNewlistHint(max_hint) as result:
+ while True:
+ cont = False
+ args = []
+ for idx, (iterator, has_finished) in enumerate(iterators):
+ val = None
+ if not has_finished:
+ try:
+ val = next(iterator)
+ except StopIteration:
+ iterators[idx] = (None, True)
+ else:
+ cont = True
+ args.append(val)
+ args = tuple(args)
+ if cont:
+ if none_func:
+ result.append(args)
else:
- cont = True
- args.append(val)
- args = tuple(args)
- if cont:
- if none_func:
- result.append(args)
+ result.append(func(*args))
else:
- result.append(func(*args))
- else:
- return result
+ return result
+
+class _ManagedNewlistHint(object):
+ """ Context manager returning a newlist_hint upon entry.
+
+ Upon exit the list's underlying capacity will be cut back to match
+ its length if necessary (incase the initial length_hint was too
+ large).
+ """
+
+ def __init__(self, length_hint):
+ self.length_hint = length_hint
+ self.list = newlist_hint(length_hint)
+
+ def __enter__(self):
+ return self.list
+
+ def __exit__(self, type, value, tb):
+ if type is None:
+ extended = len(self.list)
+ if extended < self.length_hint:
+ resizelist_hint(self.list, extended)
sentinel = object()
@@ -135,17 +166,18 @@
return _filter_string(func, seq, unicode)
elif isinstance(seq, tuple):
return _filter_tuple(func, seq)
- result = []
- for item in seq:
- if func(item):
- result.append(item)
+ with _ManagedNewlistHint(operator._length_hint(seq, 0)) as result:
+ for item in seq:
+ if func(item):
+ result.append(item)
return result
def _filter_string(func, string, str_type):
if func is bool and type(string) is str_type:
return string
- result = []
- for i in range(len(string)):
+ length = len(string)
+ result = newlist_hint(length)
+ for i in range(length):
# You must call __getitem__ on the strings, simply iterating doesn't
# work :/
item = string[i]
@@ -156,8 +188,9 @@
return str_type().join(result)
def _filter_tuple(func, seq):
- result = []
- for i in range(len(seq)):
+ length = len(seq)
+ result = newlist_hint(length)
+ for i in range(length):
# Again, must call __getitem__, at least there are tests.
item = seq[i]
if func(item):
@@ -172,11 +205,23 @@
in length to the length of the shortest argument sequence."""
if not sequences:
return []
- result = []
- iterators = [iter(seq) for seq in sequences]
- while True:
- try:
- items = [next(it) for it in iterators]
- except StopIteration:
- return result
- result.append(tuple(items))
+
+ # Gather the iterators and guess the result length (the min of the
+ # input lengths)
+ iterators = []
+ min_hint = -1
+ for seq in sequences:
+ iterators.append(iter(seq))
+ hint = operator._length_hint(seq, min_hint)
+ if min_hint == -1 or hint < min_hint:
+ min_hint = hint
+ if min_hint == -1:
+ min_hint = 0
+
+ with _ManagedNewlistHint(min_hint) as result:
+ while True:
+ try:
+ items = [next(it) for it in iterators]
+ except StopIteration:
+ return result
+ result.append(tuple(items))
diff --git a/pypy/module/__builtin__/functional.py
b/pypy/module/__builtin__/functional.py
--- a/pypy/module/__builtin__/functional.py
+++ b/pypy/module/__builtin__/functional.py
@@ -271,6 +271,9 @@
def descr___iter__(self, space):
return space.wrap(self)
+ def descr_length(self, space):
+ return space.wrap(0 if self.remaining == -1 else self.remaining + 1)
+
def descr_next(self, space):
if self.remaining >= 0:
w_index = space.wrap(self.remaining)
@@ -297,9 +300,10 @@
return space.newtuple([w_new_inst, w_info])
W_ReversedIterator.typedef = TypeDef("reversed",
- __iter__=interp2app(W_ReversedIterator.descr___iter__),
- next=interp2app(W_ReversedIterator.descr_next),
- __reduce__=interp2app(W_ReversedIterator.descr___reduce__),
+ __iter__ = interp2app(W_ReversedIterator.descr___iter__),
+ __length_hint__ = interp2app(W_ReversedIterator.descr_length),
+ next = interp2app(W_ReversedIterator.descr_next),
+ __reduce__ = interp2app(W_ReversedIterator.descr___reduce__),
)
# exported through _pickle_support
@@ -423,7 +427,7 @@
raise OperationError(self.space.w_StopIteration, self.space.w_None)
def descr_len(self):
- return self.space.wrap(self.remaining)
+ return self.space.wrap(self.get_remaining())
def descr_reduce(self):
from pypy.interpreter.mixedmodule import MixedModule
@@ -442,8 +446,7 @@
W_XRangeIterator.typedef = TypeDef("rangeiterator",
__iter__ = interp2app(W_XRangeIterator.descr_iter),
-# XXX __length_hint__()
-## __len__ = interp2app(W_XRangeIterator.descr_len),
+ __length_hint__ = interp2app(W_XRangeIterator.descr_len),
next = interp2app(W_XRangeIterator.descr_next),
__reduce__ = interp2app(W_XRangeIterator.descr_reduce),
)
diff --git a/pypy/module/__builtin__/test/test_functional.py
b/pypy/module/__builtin__/test/test_functional.py
--- a/pypy/module/__builtin__/test/test_functional.py
+++ b/pypy/module/__builtin__/test/test_functional.py
@@ -87,6 +87,15 @@
def test_three_lists(self):
assert zip([1,2,3], [1,2], [1,2,3]) == [(1,1,1), (2,2,2)]
+ def test_bad_length_hint(self):
+ class Foo(object):
+ def __length_hint__(self):
+ return NotImplemented
+ def __iter__(self):
+ if False:
+ yield None
+ assert zip(Foo()) == []
+
class AppTestReduce:
def test_None(self):
raises(TypeError, reduce, lambda x, y: x+y, [1,2,3], None)
diff --git a/pypy/module/__pypy__/__init__.py b/pypy/module/__pypy__/__init__.py
--- a/pypy/module/__pypy__/__init__.py
+++ b/pypy/module/__pypy__/__init__.py
@@ -43,6 +43,8 @@
'do_what_I_mean' : 'interp_magic.do_what_I_mean',
'list_strategy' : 'interp_magic.list_strategy',
'validate_fd' : 'interp_magic.validate_fd',
+ 'resizelist_hint' : 'interp_magic.resizelist_hint',
+ 'newlist_hint' : 'interp_magic.newlist_hint',
'newdict' : 'interp_dict.newdict',
'dictstrategy' : 'interp_dict.dictstrategy',
}
diff --git a/pypy/module/__pypy__/interp_magic.py
b/pypy/module/__pypy__/interp_magic.py
--- a/pypy/module/__pypy__/interp_magic.py
+++ b/pypy/module/__pypy__/interp_magic.py
@@ -2,6 +2,7 @@
from pypy.interpreter.error import OperationError, wrap_oserror
from pypy.interpreter.gateway import unwrap_spec
from pypy.rlib.objectmodel import we_are_translated
+from pypy.objspace.std.listobject import W_ListObject
from pypy.objspace.std.typeobject import MethodCache
from pypy.objspace.std.mapdict import IndexCache
from pypy.rlib import rposix
@@ -75,7 +76,6 @@
return space.wrap(42)
def list_strategy(space, w_list):
- from pypy.objspace.std.listobject import W_ListObject
if isinstance(w_list, W_ListObject):
return space.wrap(w_list.strategy._applevel_repr)
else:
@@ -95,3 +95,14 @@
space.wrap('cp%d' % rwin32.GetConsoleCP()),
space.wrap('cp%d' % rwin32.GetConsoleOutputCP()),
])
+
+@unwrap_spec(sizehint=int)
+def resizelist_hint(space, w_iterable, sizehint):
+ if not isinstance(w_iterable, W_ListObject):
+ raise OperationError(space.w_TypeError,
+ space.wrap("arg 1 must be a 'list'"))
+ w_iterable._resize_hint(sizehint)
+
+@unwrap_spec(sizehint=int)
+def newlist_hint(space, sizehint):
+ return space.newlist_hint(sizehint)
diff --git a/pypy/module/_collections/interp_deque.py
b/pypy/module/_collections/interp_deque.py
--- a/pypy/module/_collections/interp_deque.py
+++ b/pypy/module/_collections/interp_deque.py
@@ -517,6 +517,9 @@
def iter(self):
return self.space.wrap(self)
+ def length(self):
+ return self.space.wrap(self.counter)
+
def next(self):
self.deque.checklock(self.lock)
if self.counter == 0:
@@ -532,8 +535,9 @@
return w_x
W_DequeIter.typedef = TypeDef("deque_iterator",
- __iter__ = interp2app(W_DequeIter.iter),
- next = interp2app(W_DequeIter.next),
+ __iter__ = interp2app(W_DequeIter.iter),
+ __length_hint__ = interp2app(W_DequeIter.length),
+ next = interp2app(W_DequeIter.next),
)
W_DequeIter.typedef.acceptable_as_base_class = False
@@ -552,6 +556,9 @@
def iter(self):
return self.space.wrap(self)
+ def length(self):
+ return self.space.wrap(self.counter)
+
def next(self):
self.deque.checklock(self.lock)
if self.counter == 0:
@@ -567,8 +574,9 @@
return w_x
W_DequeRevIter.typedef = TypeDef("deque_reverse_iterator",
- __iter__ = interp2app(W_DequeRevIter.iter),
- next = interp2app(W_DequeRevIter.next),
+ __iter__ = interp2app(W_DequeRevIter.iter),
+ __length_hint__ = interp2app(W_DequeRevIter.length),
+ next = interp2app(W_DequeRevIter.next),
)
W_DequeRevIter.typedef.acceptable_as_base_class = False
diff --git a/pypy/module/itertools/interp_itertools.py
b/pypy/module/itertools/interp_itertools.py
--- a/pypy/module/itertools/interp_itertools.py
+++ b/pypy/module/itertools/interp_itertools.py
@@ -90,7 +90,7 @@
self.count = 0
else:
self.counting = True
- self.count = self.space.int_w(w_times)
+ self.count = max(self.space.int_w(w_times), 0)
def next_w(self):
if self.counting:
@@ -102,6 +102,11 @@
def iter_w(self):
return self.space.wrap(self)
+ def length_w(self):
+ if not self.counting:
+ return self.space.w_NotImplemented
+ return self.space.wrap(self.count)
+
def repr_w(self):
objrepr = self.space.str_w(self.space.repr(self.w_obj))
if self.counting:
@@ -118,10 +123,11 @@
W_Repeat.typedef = TypeDef(
'repeat',
__module__ = 'itertools',
- __new__ = interp2app(W_Repeat___new__),
- __iter__ = interp2app(W_Repeat.iter_w),
- next = interp2app(W_Repeat.next_w),
- __repr__ = interp2app(W_Repeat.repr_w),
+ __new__ = interp2app(W_Repeat___new__),
+ __iter__ = interp2app(W_Repeat.iter_w),
+ __length_hint__ = interp2app(W_Repeat.length_w),
+ next = interp2app(W_Repeat.next_w),
+ __repr__ = interp2app(W_Repeat.repr_w),
__doc__ = """Make an iterator that returns object over and over again.
Runs indefinitely unless the times argument is specified. Used
as argument to imap() for invariant parameters to the called
diff --git a/pypy/module/itertools/test/test_itertools.py
b/pypy/module/itertools/test/test_itertools.py
--- a/pypy/module/itertools/test/test_itertools.py
+++ b/pypy/module/itertools/test/test_itertools.py
@@ -89,11 +89,15 @@
def test_repeat_len(self):
import itertools
+ import operator
r = itertools.repeat('a', 15)
r.next()
raises(TypeError, "len(itertools.repeat('xkcd'))")
+ r = itertools.repeat('a', -3)
+ assert operator._length_hint(r, 3) == 0
+
def test_takewhile(self):
import itertools
diff --git a/pypy/module/operator/__init__.py b/pypy/module/operator/__init__.py
--- a/pypy/module/operator/__init__.py
+++ b/pypy/module/operator/__init__.py
@@ -37,7 +37,7 @@
'sub', 'truediv', 'truth', 'xor',
'iadd', 'iand', 'iconcat', 'idiv', 'ifloordiv',
'ilshift', 'imod', 'imul', 'ior', 'ipow', 'irepeat',
- 'irshift', 'isub', 'itruediv', 'ixor']
+ 'irshift', 'isub', 'itruediv', 'ixor', '_length_hint']
interpleveldefs = {}
diff --git a/pypy/module/operator/interp_operator.py
b/pypy/module/operator/interp_operator.py
--- a/pypy/module/operator/interp_operator.py
+++ b/pypy/module/operator/interp_operator.py
@@ -1,4 +1,5 @@
from pypy.interpreter.error import OperationError
+from pypy.interpreter.gateway import unwrap_spec
def index(space, w_a):
return space.index(w_a)
@@ -240,3 +241,8 @@
return space.inplace_mul(w_obj1, w_obj2)
+# _length_hint (to be length_hint in 3.4)
+
+@unwrap_spec(default=int)
+def _length_hint(space, w_iterable, default):
+ return space.wrap(space.length_hint(w_iterable, default))
diff --git a/pypy/objspace/std/dicttype.py b/pypy/objspace/std/dicttype.py
--- a/pypy/objspace/std/dicttype.py
+++ b/pypy/objspace/std/dicttype.py
@@ -139,6 +139,12 @@
# ____________________________________________________________
+def descr_dictiter__length_hint__(space, w_self):
+ from pypy.objspace.std.dictmultiobject import W_BaseDictMultiIterObject
+ assert isinstance(w_self, W_BaseDictMultiIterObject)
+ return space.wrap(w_self.iteratorimplementation.length())
+
+
def descr_dictiter__reduce__(w_self, space):
"""
This is a slightly special case of pickling.
@@ -195,7 +201,8 @@
dictiter_typedef = StdTypeDef("dictionaryiterator",
- __reduce__ = gateway.interp2app(descr_dictiter__reduce__),
+ __length_hint__ = gateway.interp2app(descr_dictiter__length_hint__),
+ __reduce__ = gateway.interp2app(descr_dictiter__reduce__),
)
# ____________________________________________________________
diff --git a/pypy/objspace/std/iterobject.py b/pypy/objspace/std/iterobject.py
--- a/pypy/objspace/std/iterobject.py
+++ b/pypy/objspace/std/iterobject.py
@@ -71,10 +71,6 @@
w_seqiter.index += 1
return w_item
-# XXX __length_hint__()
-##def len__SeqIter(space, w_seqiter):
-## return w_seqiter.getlength(space)
-
def iter__FastTupleIter(space, w_seqiter):
return w_seqiter
@@ -92,10 +88,6 @@
w_seqiter.index = index + 1
return w_item
-# XXX __length_hint__()
-##def len__FastTupleIter(space, w_seqiter):
-## return w_seqiter.getlength(space)
-
def iter__FastListIter(space, w_seqiter):
return w_seqiter
@@ -115,10 +107,6 @@
w_seqiter.index = index + 1
return w_item
-# XXX __length_hint__()
-##def len__FastListIter(space, w_seqiter):
-## return w_seqiter.getlength(space)
-
def iter__ReverseSeqIter(space, w_seqiter):
return w_seqiter
@@ -136,20 +124,4 @@
raise OperationError(space.w_StopIteration, space.w_None)
return w_item
-# XXX __length_hint__()
-##def len__ReverseSeqIter(space, w_seqiter):
-## if w_seqiter.w_seq is None:
-## return space.wrap(0)
-## index = w_seqiter.index+1
-## w_length = space.len(w_seqiter.w_seq)
-## # if length of sequence is less than index :exhaust iterator
-## if space.is_true(space.gt(space.wrap(w_seqiter.index), w_length)):
-## w_len = space.wrap(0)
-## w_seqiter.w_seq = None
-## else:
-## w_len =space.wrap(index)
-## if space.is_true(space.lt(w_len,space.wrap(0))):
-## w_len = space.wrap(0)
-## return w_len
-
register_all(vars())
diff --git a/pypy/objspace/std/itertype.py b/pypy/objspace/std/itertype.py
--- a/pypy/objspace/std/itertype.py
+++ b/pypy/objspace/std/itertype.py
@@ -23,6 +23,12 @@
tup = [w_self.w_seq, space.wrap(w_self.index)]
return space.newtuple([new_inst, space.newtuple(tup)])
+
+def descr_seqiter__length_hint__(space, w_self):
+ from pypy.objspace.std.iterobject import W_AbstractSeqIterObject
+ assert isinstance(w_self, W_AbstractSeqIterObject)
+ return w_self.getlength(space)
+
# ____________________________________________________________
def descr_reverseseqiter__reduce__(w_self, space):
@@ -39,6 +45,24 @@
tup = [w_self.w_seq, space.wrap(w_self.index)]
return space.newtuple([new_inst, space.newtuple(tup)])
+
+def descr_reverseseqiter__length_hint__(space, w_self):
+ from pypy.objspace.std.iterobject import W_ReverseSeqIterObject
+ assert isinstance(w_self, W_ReverseSeqIterObject)
+ if w_self.w_seq is None:
+ return space.wrap(0)
+ index = w_self.index + 1
+ w_length = space.len(w_self.w_seq)
+ # if length of sequence is less than index :exhaust iterator
+ if space.is_true(space.gt(space.wrap(w_self.index), w_length)):
+ w_len = space.wrap(0)
+ w_self.w_seq = None
+ else:
+ w_len = space.wrap(index)
+ if space.is_true(space.lt(w_len, space.wrap(0))):
+ w_len = space.wrap(0)
+ return w_len
+
# ____________________________________________________________
iter_typedef = StdTypeDef("sequenceiterator",
__doc__ = '''iter(collection) -> iterator
@@ -49,11 +73,13 @@
In the second form, the callable is called until it returns the sentinel.''',
__reduce__ = gateway.interp2app(descr_seqiter__reduce__),
+ __length_hint__ = gateway.interp2app(descr_seqiter__length_hint__),
)
iter_typedef.acceptable_as_base_class = False
reverse_iter_typedef = StdTypeDef("reversesequenceiterator",
__reduce__ = gateway.interp2app(descr_reverseseqiter__reduce__),
+ __length_hint__ = gateway.interp2app(descr_reverseseqiter__length_hint__),
)
reverse_iter_typedef.acceptable_as_base_class = False
diff --git a/pypy/objspace/std/listobject.py b/pypy/objspace/std/listobject.py
--- a/pypy/objspace/std/listobject.py
+++ b/pypy/objspace/std/listobject.py
@@ -2,12 +2,14 @@
from pypy.objspace.std.register_all import register_all
from pypy.objspace.std.multimethod import FailedToImplement
from pypy.interpreter.error import OperationError, operationerrfmt
+from pypy.interpreter.generator import GeneratorIterator
from pypy.objspace.std.inttype import wrapint
from pypy.objspace.std.listtype import get_list_index
from pypy.objspace.std.sliceobject import W_SliceObject, normalize_simple_slice
from pypy.objspace.std import slicetype
from pypy.interpreter import gateway, baseobjspace
-from pypy.rlib.objectmodel import instantiate, specialize, newlist_hint
+from pypy.rlib.objectmodel import (instantiate, newlist_hint, specialize,
+ resizelist_hint)
from pypy.rlib.listsort import make_timsort_class
from pypy.rlib import rerased, jit, debug
from pypy.interpreter.argument import Signature
@@ -32,6 +34,11 @@
storage = strategy.erase(None)
return W_ListObject.from_storage_and_strategy(space, storage, strategy)
+def make_empty_list_with_size(space, hint):
+ strategy = SizeListStrategy(space, hint)
+ storage = strategy.erase(None)
+ return W_ListObject.from_storage_and_strategy(space, storage, strategy)
+
@jit.look_inside_iff(lambda space, list_w, sizehint:
jit.isconstant(len(list_w)) and len(list_w) <
UNROLL_CUTOFF)
def get_strategy_from_list_objects(space, list_w, sizehint):
@@ -70,6 +77,34 @@
return space.fromcache(ObjectListStrategy)
+def _get_printable_location(w_type):
+ return ('list__do_extend_from_iterable [w_type=%s]' %
+ w_type.getname(w_type.space))
+
+_do_extend_jitdriver = jit.JitDriver(
+ name='list__do_extend_from_iterable',
+ greens=['w_type'],
+ reds=['i', 'w_iterator', 'w_list'],
+ get_printable_location=_get_printable_location)
+
+def _do_extend_from_iterable(space, w_list, w_iterable):
+ w_iterator = space.iter(w_iterable)
+ w_type = space.type(w_iterator)
+ i = 0
+ while True:
+ _do_extend_jitdriver.jit_merge_point(w_type=w_type,
+ i=i,
+ w_iterator=w_iterator,
+ w_list=w_list)
+ try:
+ w_list.append(space.next(w_iterator))
+ except OperationError, e:
+ if not e.match(space, space.w_StopIteration):
+ raise
+ break
+ i += 1
+ return i
+
def is_W_IntObject(w_object):
from pypy.objspace.std.intobject import W_IntObject
return type(w_object) is W_IntObject
@@ -166,6 +201,11 @@
with the same strategy and a copy of the storage"""
return self.strategy.clone(self)
+ def _resize_hint(self, hint):
+ """Ensure the underlying list has room for at least hint
+ elements without changing the len() of the list"""
+ return self.strategy._resize_hint(self, hint)
+
def copy_into(self, other):
"""Used only when extending an EmptyList. Sets the EmptyLists
strategy and storage according to the other W_List"""
@@ -274,9 +314,9 @@
index not."""
self.strategy.insert(self, index, w_item)
- def extend(self, items_w):
+ def extend(self, w_any):
"""Appends the given list of wrapped items."""
- self.strategy.extend(self, items_w)
+ self.strategy.extend(self, w_any)
def reverse(self):
"""Reverses the list."""
@@ -305,6 +345,9 @@
def copy_into(self, w_list, w_other):
raise NotImplementedError
+ def _resize_hint(self, w_list, hint):
+ raise NotImplementedError
+
def contains(self, w_list, w_obj):
# needs to be safe against eq_w() mutating the w_list behind our back
i = 0
@@ -370,9 +413,30 @@
def insert(self, w_list, index, w_item):
raise NotImplementedError
- def extend(self, w_list, items_w):
+ def extend(self, w_list, w_any):
+ if type(w_any) is W_ListObject or (isinstance(w_any, W_ListObject) and
+ self.space._uses_list_iter(w_any)):
+ self._extend_from_list(w_list, w_any)
+ elif isinstance(w_any, GeneratorIterator):
+ w_any.unpack_into_w(w_list)
+ else:
+ self._extend_from_iterable(w_list, w_any)
+
+ def _extend_from_list(self, w_list, w_other):
raise NotImplementedError
+ def _extend_from_iterable(self, w_list, w_iterable):
+ """Extend w_list from a generic iterable"""
+ length_hint = self.space.length_hint(w_iterable, 0)
+ if length_hint:
+ w_list._resize_hint(w_list.length() + length_hint)
+
+ extended = _do_extend_from_iterable(self.space, w_list, w_iterable)
+
+ # cut back if the length hint was too large
+ if extended < length_hint:
+ w_list._resize_hint(w_list.length())
+
def reverse(self, w_list):
raise NotImplementedError
@@ -409,6 +473,11 @@
def copy_into(self, w_list, w_other):
pass
+ def _resize_hint(self, w_list, hint):
+ assert hint >= 0
+ if hint:
+ w_list.strategy = SizeListStrategy(self.space, hint)
+
def contains(self, w_list, w_obj):
return False
@@ -481,9 +550,32 @@
assert index == 0
self.append(w_list, w_item)
- def extend(self, w_list, w_other):
+ def _extend_from_list(self, w_list, w_other):
w_other.copy_into(w_list)
+ def _extend_from_iterable(self, w_list, w_iterable):
+ from pypy.objspace.std.tupleobject import W_AbstractTupleObject
+ space = self.space
+ if isinstance(w_iterable, W_AbstractTupleObject):
+ w_list.__init__(space, w_iterable.getitems_copy())
+ return
+
+ intlist = space.listview_int(w_iterable)
+ if intlist is not None:
+ w_list.strategy = strategy = space.fromcache(IntegerListStrategy)
+ # need to copy because intlist can share with w_iterable
+ w_list.lstorage = strategy.erase(intlist[:])
+ return
+
+ strlist = space.listview_str(w_iterable)
+ if strlist is not None:
+ w_list.strategy = strategy = space.fromcache(StringListStrategy)
+ # need to copy because intlist can share with w_iterable
+ w_list.lstorage = strategy.erase(strlist[:])
+ return
+
+ ListStrategy._extend_from_iterable(self, w_list, w_iterable)
+
def reverse(self, w_list):
pass
@@ -494,6 +586,10 @@
self.sizehint = sizehint
ListStrategy.__init__(self, space)
+ def _resize_hint(self, w_list, hint):
+ assert hint >= 0
+ self.sizehint = hint
+
class RangeListStrategy(ListStrategy):
"""RangeListStrategy is used when a list is created using the range method.
The storage is a tuple containing only three integers start, step and
length
@@ -526,6 +622,10 @@
w_clone = W_ListObject.from_storage_and_strategy(self.space, storage,
self)
return w_clone
+ def _resize_hint(self, w_list, hint):
+ # XXX: this could be supported
+ assert hint >= 0
+
def copy_into(self, w_list, w_other):
w_other.strategy = self
w_other.lstorage = w_list.lstorage
@@ -660,9 +760,9 @@
self.switch_to_integer_strategy(w_list)
w_list.insert(index, w_item)
- def extend(self, w_list, items_w):
+ def extend(self, w_list, w_any):
self.switch_to_integer_strategy(w_list)
- w_list.extend(items_w)
+ w_list.extend(w_any)
def reverse(self, w_list):
self.switch_to_integer_strategy(w_list)
@@ -708,6 +808,9 @@
w_clone = W_ListObject.from_storage_and_strategy(self.space, storage,
self)
return w_clone
+ def _resize_hint(self, w_list, hint):
+ resizelist_hint(self.unerase(w_list.lstorage), hint)
+
def copy_into(self, w_list, w_other):
w_other.strategy = self
items = self.unerase(w_list.lstorage)[:]
@@ -792,7 +895,7 @@
w_list.switch_to_object_strategy()
w_list.insert(index, w_item)
- def extend(self, w_list, w_other):
+ def _extend_from_list(self, w_list, w_other):
l = self.unerase(w_list.lstorage)
if self.list_is_correct_type(w_other):
l += self.unerase(w_other.lstorage)
@@ -1095,52 +1198,12 @@
init_defaults = [None]
def init__List(space, w_list, __args__):
- from pypy.objspace.std.tupleobject import W_AbstractTupleObject
# this is on the silly side
w_iterable, = __args__.parse_obj(
None, 'list', init_signature, init_defaults)
w_list.clear(space)
if w_iterable is not None:
- if type(w_iterable) is W_ListObject:
- w_iterable.copy_into(w_list)
- return
- elif isinstance(w_iterable, W_AbstractTupleObject):
- w_list.__init__(space, w_iterable.getitems_copy())
- return
-
- intlist = space.listview_int(w_iterable)
- if intlist is not None:
- w_list.strategy = strategy = space.fromcache(IntegerListStrategy)
- # need to copy because intlist can share with w_iterable
- w_list.lstorage = strategy.erase(intlist[:])
- return
-
- strlist = space.listview_str(w_iterable)
- if strlist is not None:
- w_list.strategy = strategy = space.fromcache(StringListStrategy)
- # need to copy because intlist can share with w_iterable
- w_list.lstorage = strategy.erase(strlist[:])
- return
-
- # xxx special hack for speed
- from pypy.interpreter.generator import GeneratorIterator
- if isinstance(w_iterable, GeneratorIterator):
- w_iterable.unpack_into_w(w_list)
- return
- # /xxx
- _init_from_iterable(space, w_list, w_iterable)
-
-def _init_from_iterable(space, w_list, w_iterable):
- # in its own function to make the JIT look into init__List
- w_iterator = space.iter(w_iterable)
- while True:
- try:
- w_item = space.next(w_iterator)
- except OperationError, e:
- if not e.match(space, space.w_StopIteration):
- raise
- break # done
- w_list.append(w_item)
+ w_list.extend(w_iterable)
def len__List(space, w_list):
result = w_list.length()
@@ -1210,7 +1273,7 @@
return w_list1
def inplace_add__List_List(space, w_list1, w_list2):
- list_extend__List_List(space, w_list1, w_list2)
+ list_extend__List_ANY(space, w_list1, w_list2)
return w_list1
def mul_list_times(space, w_list, w_times):
@@ -1361,13 +1424,8 @@
w_list.append(w_any)
return space.w_None
-def list_extend__List_List(space, w_list, w_other):
- w_list.extend(w_other)
- return space.w_None
-
def list_extend__List_ANY(space, w_list, w_any):
- w_other = W_ListObject(space, space.listview(w_any))
- w_list.extend(w_other)
+ w_list.extend(w_any)
return space.w_None
# default of w_idx is space.w_None (see listtype.py)
diff --git a/pypy/objspace/std/setobject.py b/pypy/objspace/std/setobject.py
--- a/pypy/objspace/std/setobject.py
+++ b/pypy/objspace/std/setobject.py
@@ -957,13 +957,6 @@
return w_key
raise OperationError(space.w_StopIteration, space.w_None)
-# XXX __length_hint__()
-##def len__SetIterObject(space, w_setiter):
-## content = w_setiter.content
-## if content is None or w_setiter.len == -1:
-## return space.wrap(0)
-## return space.wrap(w_setiter.len - w_setiter.pos)
-
# some helper functions
def newset(space):
diff --git a/pypy/objspace/std/settype.py b/pypy/objspace/std/settype.py
--- a/pypy/objspace/std/settype.py
+++ b/pypy/objspace/std/settype.py
@@ -81,4 +81,11 @@
set_typedef.registermethods(globals())
-setiter_typedef = StdTypeDef("setiterator")
+def descr_setiterator__length_hint__(space, w_self):
+ from pypy.objspace.std.setobject import W_SetIterObject
+ assert isinstance(w_self, W_SetIterObject)
+ return space.wrap(w_self.iterimplementation.length())
+
+setiter_typedef = StdTypeDef("setiterator",
+ __length_hint__ = gateway.interp2app(descr_setiterator__length_hint__),
+ )
diff --git a/pypy/objspace/std/test/test_lengthhint.py
b/pypy/objspace/std/test/test_lengthhint.py
new file mode 100644
--- /dev/null
+++ b/pypy/objspace/std/test/test_lengthhint.py
@@ -0,0 +1,143 @@
+from pypy.module._collections.interp_deque import W_Deque
+from pypy.module.itertools.interp_itertools import W_Repeat
+
+class TestLengthHint:
+
+ SIZE = 4
+ ITEMS = range(SIZE)
+
+ def _test_length_hint(self, w_obj):
+ space = self.space
+ assert space.length_hint(w_obj, 8) == self.SIZE
+
+ w_iter = space.iter(w_obj)
+ assert space.int_w(
+ space.call_method(w_iter, '__length_hint__')) == self.SIZE
+ assert space.length_hint(w_iter, 8) == self.SIZE
+
+ space.next(w_iter)
+ assert space.length_hint(w_iter, 8) == self.SIZE - 1
+
+ def test_bytearray(self):
+ space = self.space
+ w_bytearray = space.call_function(space.w_bytearray,
+ space.wrap(self.ITEMS))
+ self._test_length_hint(w_bytearray)
+
+ def test_dict(self):
+ space = self.space
+ w_dict = space.call_function(space.w_dict,
+ space.wrap((i, None) for i in self.ITEMS))
+ self._test_length_hint(w_dict)
+
+ def test_dict_iterkeys(self):
+ w_iterkeys = self.space.appexec([], """():
+ return dict.fromkeys(%r).iterkeys()
+ """ % self.ITEMS)
+ self._test_length_hint(w_iterkeys)
+
+ def test_dict_values(self):
+ w_itervalues = self.space.appexec([], """():
+ return dict.fromkeys(%r).itervalues()
+ """ % self.ITEMS)
+ self._test_length_hint(w_itervalues)
+
+ def test_frozenset(self):
+ space = self.space
+ w_set = space.call_function(space.w_frozenset, space.wrap(self.ITEMS))
+ self._test_length_hint(w_set)
+
+ def test_set(self):
+ space = self.space
+ w_set = space.call_function(space.w_set, space.wrap(self.ITEMS))
+ self._test_length_hint(w_set)
+
+ def test_list(self):
+ self._test_length_hint(self.space.wrap(self.ITEMS))
+
+ def test_str(self):
+ self._test_length_hint(self.space.wrap('P' * self.SIZE))
+
+ def test_unicode(self):
+ self._test_length_hint(self.space.wrap(u'Y' * self.SIZE))
+
+ def test_tuple(self):
+ self._test_length_hint(self.space.newtuple(self.ITEMS))
+
+ def test_reversed(self):
+ # test the generic reversed iterator (w_foo lacks __reversed__)
+ space = self.space
+ w_foo = space.appexec([], """():
+ class Foo(object):
+ def __len__(self):
+ return %r
+ def __getitem__(self, index):
+ if 0 <= index < %r:
+ return index
+ raise IndexError()
+ return Foo()
+ """ % (self.SIZE, self.SIZE))
+ w_reversed = space.call_method(space.builtin, 'reversed', w_foo)
+ assert space.int_w(
+ space.call_method(w_reversed, '__length_hint__')) == self.SIZE
+ self._test_length_hint(w_reversed)
+
+ def test_reversedsequenceiterator(self):
+ space = self.space
+ w_reversed = space.call_method(space.builtin, 'reversed',
+ space.wrap(self.ITEMS))
+ assert space.int_w(
+ space.call_method(w_reversed, '__length_hint__')) == self.SIZE
+ self._test_length_hint(w_reversed)
+
+ def test_xrange(self):
+ space = self.space
+ w_xrange = space.call_method(space.builtin, 'xrange',
+ space.newint(self.SIZE))
+ self._test_length_hint(w_xrange)
+
+ def test_itertools_repeat(self):
+ space = self.space
+ self._test_length_hint(W_Repeat(space, space.wrap(22),
+ space.wrap(self.SIZE)))
+
+ def test_collections_deque(self):
+ space = self.space
+ w_deque = W_Deque(space)
+ space.call_method(w_deque, '__init__', space.wrap(self.ITEMS))
+ self._test_length_hint(w_deque)
+ self._test_length_hint(w_deque.reviter())
+
+ def test_default(self):
+ space = self.space
+ assert space.length_hint(space.w_False, 3) == 3
+
+ def test_NotImplemented(self):
+ space = self.space
+ w_foo = space.appexec([], """():
+ class Foo(object):
+ def __length_hint__(self):
+ return NotImplemented
+ return Foo()
+ """)
+ assert space.length_hint(w_foo, 3) == 3
+
+ def test_invalid_hint(self):
+ space = self.space
+ w_foo = space.appexec([], """():
+ class Foo(object):
+ def __length_hint__(self):
+ return -1
+ return Foo()
+ """)
+ space.raises_w(space.w_ValueError, space.length_hint, w_foo, 3)
+
+ def test_exc(self):
+ space = self.space
+ w_foo = space.appexec([], """():
+ class Foo(object):
+ def __length_hint__(self):
+ 1 / 0
+ return Foo()
+ """)
+ space.raises_w(space.w_ZeroDivisionError, space.length_hint, w_foo, 3)
diff --git a/pypy/objspace/std/test/test_listobject.py
b/pypy/objspace/std/test/test_listobject.py
--- a/pypy/objspace/std/test/test_listobject.py
+++ b/pypy/objspace/std/test/test_listobject.py
@@ -400,6 +400,11 @@
space.call_method(w_l, 'append', space.w_None)
assert isinstance(w_l.strategy, ObjectListStrategy)
+ def test_newlist_hint(self):
+ space = self.space
+ w_lst = space.newlist_hint(13)
+ assert isinstance(w_lst.strategy, SizeListStrategy)
+ assert w_lst.strategy.sizehint == 13
class AppTestW_ListObject(object):
def setup_class(cls):
@@ -1195,7 +1200,16 @@
class SubClass(base):
def __iter__(self):
return iter("foobar")
- assert list(SubClass(arg)) == ['f', 'o', 'o', 'b', 'a', 'r']
+ sub = SubClass(arg)
+ assert list(sub) == ['f', 'o', 'o', 'b', 'a', 'r']
+ l = []
+ l.extend(sub)
+ assert l == ['f', 'o', 'o', 'b', 'a', 'r']
+ # test another list strategy
+ l = ['Z']
+ l.extend(sub)
+ assert l == ['Z', 'f', 'o', 'o', 'b', 'a', 'r']
+
class Sub2(base):
pass
assert list(Sub2(arg)) == list(base(arg))
diff --git a/pypy/rlib/objectmodel.py b/pypy/rlib/objectmodel.py
--- a/pypy/rlib/objectmodel.py
+++ b/pypy/rlib/objectmodel.py
@@ -348,6 +348,25 @@
hop.exception_is_here()
return rtype_newlist(hop, v_sizehint=v)
+def resizelist_hint(l, sizehint):
+ """Reallocate the underlying list to the specified sizehint"""
+ return
+
+class Entry(ExtRegistryEntry):
+ _about_ = resizelist_hint
+
+ def compute_result_annotation(self, s_l, s_sizehint):
+ from pypy.annotation import model as annmodel
+ assert isinstance(s_l, annmodel.SomeList)
+ assert isinstance(s_sizehint, annmodel.SomeInteger)
+ s_l.listdef.listitem.resize()
+
+ def specialize_call(self, hop):
+ r_list = hop.args_r[0]
+ v_list, v_sizehint = hop.inputargs(*hop.args_r)
+ hop.exception_is_here()
+ hop.gendirectcall(r_list.LIST._ll_resize_hint, v_list, v_sizehint)
+
# ____________________________________________________________
#
# id-like functions. The idea is that calling hash() or id() is not
diff --git a/pypy/rlib/test/test_objectmodel.py
b/pypy/rlib/test/test_objectmodel.py
--- a/pypy/rlib/test/test_objectmodel.py
+++ b/pypy/rlib/test/test_objectmodel.py
@@ -2,6 +2,7 @@
from pypy.rlib.objectmodel import *
from pypy.translator.translator import TranslationContext, graphof
from pypy.rpython.test.tool import BaseRtypingTest, LLRtypeMixin, OORtypeMixin
+from pypy.rpython.test.test_llinterp import interpret
from pypy.conftest import option
def strange_key_eq(key1, key2):
@@ -526,3 +527,27 @@
break
assert llop.args[2] is graph.startblock.inputargs[0]
+def test_resizelist_hint():
+ from pypy.annotation.model import SomeInteger
+ def f(z):
+ x = []
+ resizelist_hint(x, 39)
+ return len(x)
+
+ graph = getgraph(f, [SomeInteger()])
+ for _, op in graph.iterblockops():
+ if op.opname == 'direct_call':
+ break
+ call_name = op.args[0].value._obj.graph.name
+ assert call_name.startswith('_ll_list_resize_hint')
+ call_arg2 = op.args[2].value
+ assert call_arg2 == 39
+
+def test_resizelist_hint_len():
+ def f(i):
+ l = [44]
+ resizelist_hint(l, i)
+ return len(l)
+
+ r = interpret(f, [29])
+ assert r == 1
diff --git a/pypy/rpython/lltypesystem/rlist.py
b/pypy/rpython/lltypesystem/rlist.py
--- a/pypy/rpython/lltypesystem/rlist.py
+++ b/pypy/rpython/lltypesystem/rlist.py
@@ -103,6 +103,7 @@
"_ll_resize_ge": _ll_list_resize_ge,
"_ll_resize_le": _ll_list_resize_le,
"_ll_resize": _ll_list_resize,
+ "_ll_resize_hint":
_ll_list_resize_hint,
}),
hints = {'list': True})
)
@@ -171,11 +172,11 @@
# adapted C code
@enforceargs(None, int, None)
-def _ll_list_resize_really(l, newsize, overallocate):
+def _ll_list_resize_hint_really(l, newsize, overallocate):
"""
- Ensure l.items has room for at least newsize elements, and set
- l.length to newsize. Note that l.items may change, and even if
- newsize is less than l.length on entry.
+ Ensure l.items has room for at least newsize elements. Note that
+ l.items may change, and even if newsize is less than l.length on
+ entry.
"""
# This over-allocates proportional to the list size, making room
# for additional growth. The over-allocation is mild, but is
@@ -210,8 +211,31 @@
else:
p = newsize
rgc.ll_arraycopy(items, newitems, 0, 0, p)
+ l.items = newitems
+
[email protected]_look_inside
+def _ll_list_resize_hint(l, newsize):
+ """Ensure l.items has room for at least newsize elements without
+ setting l.length to newsize.
+
+ Used before (and after) a batch operation that will likely grow the
+ list to the newsize (and after the operation incase the initial
+ guess lied).
+ """
+ assert newsize >= 0, "negative list length"
+ allocated = len(l.items)
+ if allocated < newsize or newsize < (allocated >> 1) - 5:
+ _ll_list_resize_hint_really(l, newsize, False)
+
+@enforceargs(None, int, None)
+def _ll_list_resize_really(l, newsize, overallocate):
+ """
+ Ensure l.items has room for at least newsize elements, and set
+ l.length to newsize. Note that l.items may change, and even if
+ newsize is less than l.length on entry.
+ """
+ _ll_list_resize_hint_really(l, newsize, overallocate)
l.length = newsize
- l.items = newitems
# this common case was factored out of _ll_list_resize
# to see if inlining it gives some speed-up.
diff --git a/pypy/rpython/ootypesystem/ootype.py
b/pypy/rpython/ootypesystem/ootype.py
--- a/pypy/rpython/ootypesystem/ootype.py
+++ b/pypy/rpython/ootypesystem/ootype.py
@@ -580,6 +580,7 @@
"_ll_resize_ge": Meth([Signed], Void),
"_ll_resize_le": Meth([Signed], Void),
"_ll_resize": Meth([Signed], Void),
+ "_ll_resize_hint": Meth([Signed], Void),
})
self._setup_methods(generic_types)
diff --git a/pypy/rpython/rlist.py b/pypy/rpython/rlist.py
--- a/pypy/rpython/rlist.py
+++ b/pypy/rpython/rlist.py
@@ -25,6 +25,8 @@
'_ll_resize_le': (['self', Signed ], Void),
# resize to exactly the given size
'_ll_resize': (['self', Signed ], Void),
+ # realloc the underlying list
+ '_ll_resize_hint': (['self', Signed ], Void),
})
diff --git a/pypy/translator/cli/src/pypylib.cs
b/pypy/translator/cli/src/pypylib.cs
--- a/pypy/translator/cli/src/pypylib.cs
+++ b/pypy/translator/cli/src/pypylib.cs
@@ -840,6 +840,11 @@
this._ll_resize_le(length);
}
+ public void _ll_resize_hint(int length)
+ {
+ this.Capacity(length);
+ }
+
public void _ll_resize_ge(int length)
{
if (this.Count < length)
@@ -883,6 +888,7 @@
public void ll_getitem_fast(int index) { }
public void ll_setitem_fast(int index) { }
public void _ll_resize(int length) { this.Count = length; }
+ public void _ll_resize_hint(int length) { }
public void _ll_resize_ge(int length) { this.Count = length; }
public void _ll_resize_le(int length) { this.Count = length; }
}
diff --git a/pypy/translator/jvm/src/pypy/PyPy.java
b/pypy/translator/jvm/src/pypy/PyPy.java
--- a/pypy/translator/jvm/src/pypy/PyPy.java
+++ b/pypy/translator/jvm/src/pypy/PyPy.java
@@ -1085,6 +1085,10 @@
_ll_resize_le(self, length);
}
+ public static void _ll_resize_hint(ArrayList self, int length) {
+ self.ensureCapacity(length);
+ }
+
// ----------------------------------------------------------------------
// ll_math
//
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
