Commits

Armin Rigo committed 036ab71 Merge

hg merge default

Comments (0)

Files changed (38)

pypy/interpreter/argument.py

File contents unchanged.

pypy/interpreter/baseobjspace.py

         """
         # 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,
         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
         """
     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'."""

pypy/interpreter/test/test_argument.py

File contents unchanged.

pypy/jit/backend/arm/arch.py

 static int pypy__arm_int_div(int a, int b) {
     return a/b;
 }
-static uint pypy__arm_uint_div(uint a, uint b) {
+static unsigned int pypy__arm_uint_div(unsigned int a, unsigned int b) {
     return a/b;
 }
-static int pypy__arm_int_mod(uint a, uint b) {
+static int pypy__arm_int_mod(int a, int b) {
     return a % b;
 }
 """])

pypy/jit/backend/arm/test/test_regalloc.py

         return -1
 
 
+def get_zero_division_error(self):
+    # for tests, a random emulated ll_inst will do
+    ll_inst = lltype.malloc(rclass.OBJECT)
+    ll_inst.typeptr = lltype.malloc(rclass.OBJECT_VTABLE,
+                                    immortal=True)
+    _zer_error_vtable = llmemory.cast_ptr_to_adr(ll_inst.typeptr)
+    zer_vtable = self.cast_adr_to_int(_zer_error_vtable)
+    zer_inst = lltype.cast_opaque_ptr(llmemory.GCREF, ll_inst)
+    return zer_vtable, zer_inst
+
+
 class BaseTestRegalloc(object):
     cpu = CPU(None, None)
     cpu.setup_once()
     f_calldescr = cpu.calldescrof(FPTR.TO, FPTR.TO.ARGS, FPTR.TO.RESULT,
                                                     EffectInfo.MOST_GENERAL)
 
-    zero_division_tp, zero_division_value = cpu.get_zero_division_error()
+    zero_division_tp, zero_division_value = get_zero_division_error(cpu)
     zd_addr = cpu.cast_int_to_adr(zero_division_tp)
     zero_division_error = llmemory.cast_adr_to_ptr(zd_addr,
                                             lltype.Ptr(rclass.OBJECT_VTABLE))

pypy/jit/backend/llgraph/runner.py

File contents unchanged.

pypy/jit/backend/llsupport/llmodel.py

File contents unchanged.

pypy/jit/backend/x86/test/test_regalloc.py

     def _compute_next_usage(self, v, _):
         return -1
 
+
+def get_zero_division_error(self):
+    # for tests, a random emulated ll_inst will do
+    ll_inst = lltype.malloc(rclass.OBJECT)
+    ll_inst.typeptr = lltype.malloc(rclass.OBJECT_VTABLE,
+                                    immortal=True)
+    _zer_error_vtable = llmemory.cast_ptr_to_adr(ll_inst.typeptr)
+    zer_vtable = self.cast_adr_to_int(_zer_error_vtable)
+    zer_inst = lltype.cast_opaque_ptr(llmemory.GCREF, ll_inst)
+    return zer_vtable, zer_inst
+
+
 class BaseTestRegalloc(object):
     cpu = CPU(None, None)
     cpu.setup_once()
                               zero_division_value)
     FPTR = lltype.Ptr(lltype.FuncType([lltype.Signed], lltype.Void))
     raising_fptr = llhelper(FPTR, raising_func)
-    zero_division_tp, zero_division_value = cpu.get_zero_division_error()
+    zero_division_tp, zero_division_value = get_zero_division_error(cpu)
     zd_addr = cpu.cast_int_to_adr(zero_division_tp)
     zero_division_error = llmemory.cast_adr_to_ptr(zd_addr,
                                             lltype.Ptr(rclass.OBJECT_VTABLE))

pypy/jit/metainterp/test/test_ajit.py

                     found += 1
             assert found == 2
 
-    def test_loop_automatic_reds(self):
-        myjitdriver = JitDriver(greens = ['m'], reds = 'auto')
-        def f(n, m):
-            res = 0
-            # try to have lots of red vars, so that if there is an error in
-            # the ordering of reds, there are low chances that the test passes
-            # by chance
-            a = b = c = d = n
-            while n > 0:
-                myjitdriver.jit_merge_point(m=m)
-                n -= 1
-                a += 1 # dummy unused red
-                b += 2 # dummy unused red
-                c += 3 # dummy unused red
-                d += 4 # dummy unused red
-                res += m*2
-            return res
-        expected = f(21, 5)
-        res = self.meta_interp(f, [21, 5])
-        assert res == expected
-        self.check_resops(int_sub=2, int_mul=0, int_add=10)
-
-    def test_loop_automatic_reds_with_floats_and_refs(self):
-        myjitdriver = JitDriver(greens = ['m'], reds = 'auto')
-        class MyObj(object):
-            def __init__(self, val):
-                self.val = val
-        def f(n, m):
-            res = 0
-            # try to have lots of red vars, so that if there is an error in
-            # the ordering of reds, there are low chances that the test passes
-            # by chance
-            i1 = i2 = i3 = i4 = n
-            f1 = f2 = f3 = f4 = float(n)
-            r1 = r2 = r3 = r4 = MyObj(n)
-            while n > 0:
-                myjitdriver.jit_merge_point(m=m)
-                n -= 1
-                i1 += 1 # dummy unused red
-                i2 += 2 # dummy unused red
-                i3 += 3 # dummy unused red
-                i4 += 4 # dummy unused red
-                f1 += 1 # dummy unused red
-                f2 += 2 # dummy unused red
-                f3 += 3 # dummy unused red
-                f4 += 4 # dummy unused red
-                r1.val += 1 # dummy unused red
-                r2.val += 2 # dummy unused red
-                r3.val += 3 # dummy unused red
-                r4.val += 4 # dummy unused red
-                res += m*2
-            return res
-        expected = f(21, 5)
-        res = self.meta_interp(f, [21, 5])
-        assert res == expected
-        self.check_resops(int_sub=2, int_mul=0, int_add=18, float_add=8)
-
-    def test_loop_automatic_reds_livevars_before_jit_merge_point(self):
-        myjitdriver = JitDriver(greens = ['m'], reds = 'auto')
-        def f(n, m):
-            res = 0
-            while n > 0:
-                n -= 1
-                myjitdriver.jit_merge_point(m=m)
-                res += m*2
-            return res
-        expected = f(21, 5)
-        res = self.meta_interp(f, [21, 5])
-        assert res == expected
-        self.check_resops(int_sub=2, int_mul=0, int_add=2)
-
     def test_loop_variant_mul1(self):
         myjitdriver = JitDriver(greens = [], reds = ['y', 'res', 'x'])
         def f(x, y):
                 i += 1
         res = self.meta_interp(f, [32])
         assert res == f(32)
-
-    def test_inline_in_portal(self):
-        myjitdriver = JitDriver(greens = [], reds = 'auto')
-        class MyRange(object):
-            def __init__(self, n):
-                self.cur = 0
-                self.n = n
-
-            def __iter__(self):
-                return self
-
-            @myjitdriver.inline_in_portal
-            def next(self):
-                myjitdriver.jit_merge_point()
-                if self.cur == self.n:
-                    raise StopIteration
-                self.cur += 1
-                return self.cur
-
-        def f(n, m):
-            res = 0
-            for i in MyRange(100):
-                res += i
-            return res
-        expected = f(21, 5)
-        res = self.meta_interp(f, [21, 5])
-        assert res == expected
-        self.check_resops(int_eq=2, int_add=4)
         
 class XXXDisabledTestOOtype(BasicTests, OOJitMixin):
 

pypy/jit/metainterp/test/test_warmspot.py

                            'int_sub': 2})
 
     def test_void_red_variable(self):
-        mydriver = JitDriver(greens=[], reds=['a', 'm'])
+        mydriver = JitDriver(greens=[], reds=['m'])
         def f1(m):
             a = None
             while m > 0:
-                mydriver.jit_merge_point(a=a, m=m)
+                mydriver.jit_merge_point(m=m)
                 m = m - 1
                 if m == 10:
                     pass   # other case
         self.meta_interp(f1, [18])
 
 
+    def test_loop_automatic_reds(self):
+        myjitdriver = JitDriver(greens = ['m'], reds = 'auto')
+        def f(n, m):
+            res = 0
+            # try to have lots of red vars, so that if there is an error in
+            # the ordering of reds, there are low chances that the test passes
+            # by chance
+            a = b = c = d = n
+            while n > 0:
+                myjitdriver.jit_merge_point(m=m)
+                n -= 1
+                a += 1 # dummy unused red
+                b += 2 # dummy unused red
+                c += 3 # dummy unused red
+                d += 4 # dummy unused red
+                res += m*2
+            return res
+        expected = f(21, 5)
+        res = self.meta_interp(f, [21, 5])
+        assert res == expected
+        self.check_resops(int_sub=2, int_mul=0, int_add=10)
+
+    def test_loop_automatic_reds_with_floats_and_refs(self):
+        myjitdriver = JitDriver(greens = ['m'], reds = 'auto')
+        class MyObj(object):
+            def __init__(self, val):
+                self.val = val
+        def f(n, m):
+            res = 0
+            # try to have lots of red vars, so that if there is an error in
+            # the ordering of reds, there are low chances that the test passes
+            # by chance
+            i1 = i2 = i3 = i4 = n
+            f1 = f2 = f3 = f4 = float(n)
+            r1 = r2 = r3 = r4 = MyObj(n)
+            while n > 0:
+                myjitdriver.jit_merge_point(m=m)
+                n -= 1
+                i1 += 1 # dummy unused red
+                i2 += 2 # dummy unused red
+                i3 += 3 # dummy unused red
+                i4 += 4 # dummy unused red
+                f1 += 1 # dummy unused red
+                f2 += 2 # dummy unused red
+                f3 += 3 # dummy unused red
+                f4 += 4 # dummy unused red
+                r1.val += 1 # dummy unused red
+                r2.val += 2 # dummy unused red
+                r3.val += 3 # dummy unused red
+                r4.val += 4 # dummy unused red
+                res += m*2
+            return res
+        expected = f(21, 5)
+        res = self.meta_interp(f, [21, 5])
+        assert res == expected
+        self.check_resops(int_sub=2, int_mul=0, int_add=18, float_add=8)
+
+    def test_loop_automatic_reds_livevars_before_jit_merge_point(self):
+        myjitdriver = JitDriver(greens = ['m'], reds = 'auto')
+        def f(n, m):
+            res = 0
+            while n > 0:
+                n -= 1
+                myjitdriver.jit_merge_point(m=m)
+                res += m*2
+            return res
+        expected = f(21, 5)
+        res = self.meta_interp(f, [21, 5])
+        assert res == expected
+        self.check_resops(int_sub=2, int_mul=0, int_add=2)
+
+    def test_inline_in_portal(self):
+        myjitdriver = JitDriver(greens = [], reds = 'auto')
+        class MyRange(object):
+            def __init__(self, n):
+                self.cur = 0
+                self.n = n
+
+            def __iter__(self):
+                return self
+
+            @myjitdriver.inline_in_portal
+            def next(self):
+                myjitdriver.jit_merge_point()
+                if self.cur == self.n:
+                    raise StopIteration
+                self.cur += 1
+                return self.cur
+
+        def one():
+            res = 0
+            for i in MyRange(10):
+                res += i
+            return res
+
+        def two():
+            res = 0
+            for i in MyRange(13):
+                res += i * 2
+            return res
+
+        def f(n, m):
+            res = one() * 100
+            res += two()
+            return res
+        expected = f(21, 5)
+        res = self.meta_interp(f, [21, 5])
+        assert res == expected
+        self.check_resops(int_eq=4, int_add=8)
+        self.check_trace_count(2)
+
 class TestLLWarmspot(WarmspotTests, LLJitMixin):
     CPUClass = runner.LLGraphCPU
     type_system = 'lltype'

pypy/module/__builtin__/app_functional.py

 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
 
 # ____________________________________________________________
 
     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()
 
         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]
     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):
 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))

pypy/module/__builtin__/functional.py

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

pypy/module/__builtin__/test/test_functional.py

    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)

pypy/module/__pypy__/__init__.py

         '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',
     }

pypy/module/__pypy__/interp_magic.py

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

pypy/module/_collections/interp_deque.py

     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:
         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
 
     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:
         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
 

pypy/module/itertools/interp_itertools.py

             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:
     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:
 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

pypy/module/itertools/test/test_itertools.py

 
     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
 

pypy/module/operator/__init__.py

                     '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 = {}
 

pypy/module/operator/interp_operator.py

 from pypy.interpreter.error import OperationError
+from pypy.interpreter.gateway import unwrap_spec
 
 def index(space, w_a):
     return space.index(w_a)
 
     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))

pypy/module/pypyjit/test_pypy_c/model.py

File contents unchanged.

pypy/objspace/std/dictmultiobject.py

 init_signature = Signature(['seq_or_map'], None, 'kwargs')
 init_defaults = [None]
 
+
 def update1(space, w_dict, w_data):
     if space.findattr(w_data, space.wrap("keys")) is None:
         # no 'keys' method, so we assume it is a sequence of pairs
-        for w_pair in space.listview(w_data):
-            pair = space.fixedview(w_pair)
-            if len(pair) != 2:
-                raise OperationError(space.w_ValueError,
-                             space.wrap("sequence of pairs expected"))
-            w_key, w_value = pair
-            w_dict.setitem(w_key, w_value)
+        update1_pairs(space, w_dict, w_data)
     else:
         if isinstance(w_data, W_DictMultiObject):    # optimization case only
             update1_dict_dict(space, w_dict, w_data)
         else:
             # general case -- "for k in o.keys(): dict.__setitem__(d, k, o[k])"
-            w_keys = space.call_method(w_data, "keys")
-            for w_key in space.listview(w_keys):
-                w_value = space.getitem(w_data, w_key)
-                w_dict.setitem(w_key, w_value)
+            update1_keys(space, w_dict, w_data)
 
+
+@jit.look_inside_iff(lambda space, w_dict, w_data: w_dict_unrolling_heuristic(w_data))
 def update1_dict_dict(space, w_dict, w_data):
     iterator = w_data.iteritems()
     while 1:
             break
         w_dict.setitem(w_key, w_value)
 
+
+def update1_pairs(space, w_dict, w_data):
+    for w_pair in space.listview(w_data):
+        pair = space.fixedview(w_pair)
+        if len(pair) != 2:
+            raise OperationError(space.w_ValueError,
+                         space.wrap("sequence of pairs expected"))
+        w_key, w_value = pair
+        w_dict.setitem(w_key, w_value)
+
+
+def update1_keys(space, w_dict, w_data):
+    w_keys = space.call_method(w_data, "keys")
+    for w_key in space.listview(w_keys):
+        w_value = space.getitem(w_data, w_key)
+        w_dict.setitem(w_key, w_value)
+
+
 def init_or_update(space, w_dict, __args__, funcname):
     w_src, w_kwds = __args__.parse_obj(
             None, funcname,

pypy/objspace/std/dicttype.py

 
 # ____________________________________________________________
 
+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.
 
 
 dictiter_typedef = StdTypeDef("dictionaryiterator",
-    __reduce__ = gateway.interp2app(descr_dictiter__reduce__),
+    __length_hint__ = gateway.interp2app(descr_dictiter__length_hint__),
+    __reduce__      = gateway.interp2app(descr_dictiter__reduce__),
     )
 
 # ____________________________________________________________

pypy/objspace/std/iterobject.py

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

pypy/objspace/std/itertype.py

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

pypy/objspace/std/listobject.py

 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
     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):
 
     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
         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"""
         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."""
     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
     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
 
     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
 
         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
 
         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
         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
         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)
         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)[:]
         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)
 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()
     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):
     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)

pypy/objspace/std/setobject.py

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

pypy/objspace/std/settype.py

 
 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__),
+    )

pypy/objspace/std/test/test_lengthhint.py

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

pypy/objspace/std/test/test_listobject.py

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

pypy/objspace/std/test/test_liststrategies.py

File contents unchanged.

pypy/rlib/objectmodel.py

         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

pypy/rlib/test/test_objectmodel.py

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

pypy/rpython/lltypesystem/rlist.py

                                           "_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})
                              )
 # 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
         else:
             p = newsize
         rgc.ll_arraycopy(items, newitems, 0, 0, p)
+    l.items = newitems
+
+@jit.dont_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.

pypy/rpython/ootypesystem/ootype.py

             "_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)

pypy/rpython/rlist.py

     '_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),
 })
 
 

pypy/translator/cli/src/pypylib.cs

                 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) 
         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; }
     }

pypy/translator/jvm/src/pypy/PyPy.java

             _ll_resize_le(self, length); 
     }
 
+    public static void _ll_resize_hint(ArrayList self, int length) {
+        self.ensureCapacity(length);
+    }
+
     // ----------------------------------------------------------------------
     // ll_math
     //