Commits

mattip  committed 0ba3dc9 Merge

merge default into branch

  • Participants
  • Parent commits 730ce60, b26d37a
  • Branches numpypy-longdouble

Comments (0)

Files changed (66)

File README

-=====================================
-PyPy: Python in Python Implementation 
-=====================================
-
-Welcome to PyPy!
-
-PyPy is both an implementation of the Python programming language, and
-an extensive compiler framework for dynamic language implementations.
-You can build self-contained Python implementations which execute
-independently from CPython.
-
-The home page is:
-
-    http://pypy.org/
-
-The getting-started document will help guide you:
-
-    http://doc.pypy.org/en/latest/getting-started.html
-
-It will also point you to the rest of the documentation which is generated
-from files in the pypy/doc directory within the source repositories. Enjoy
-and send us feedback!
-
-    the pypy-dev team <pypy-dev@python.org>
+=====================================
+PyPy: Python in Python Implementation 
+=====================================
+
+Welcome to PyPy!
+
+PyPy is both an implementation of the Python programming language, and
+an extensive compiler framework for dynamic language implementations.
+You can build self-contained Python implementations which execute
+independently from CPython.
+
+The home page is:
+
+    http://pypy.org/
+
+The getting-started document will help guide you:
+
+    http://doc.pypy.org/en/latest/getting-started.html
+
+It will also point you to the rest of the documentation which is generated
+from files in the pypy/doc directory within the source repositories. Enjoy
+and send us feedback!
+
+    the pypy-dev team <pypy-dev@python.org>

File lib-python/2.7/ctypes/test/test_internals.py

 # This tests the internal _objects attribute
 import unittest
 from ctypes import *
-from sys import getrefcount as grc
+try:
+    from sys import getrefcount as grc
+except ImportError:
+    grc = None      # e.g. PyPy
 
 # XXX This test must be reviewed for correctness!!!
 
         self.assertEqual(id(a), id(b))
 
     def test_ints(self):
+        if grc is None:
+            return unittest.skip("no sys.getrefcount()")
         i = 42000123
         refcnt = grc(i)
         ci = c_int(i)
         self.assertEqual(ci._objects, None)
 
     def test_c_char_p(self):
+        if grc is None:
+            return unittest.skip("no sys.getrefcount()")
         s = "Hello, World"
         refcnt = grc(s)
         cs = c_char_p(s)

File lib-python/2.7/ctypes/test/test_memfunctions.py

         s = string_at("foo bar")
         # XXX The following may be wrong, depending on how Python
         # manages string instances
-        self.assertEqual(2, sys.getrefcount(s))
+        if hasattr(sys, 'getrefcount'):
+            self.assertEqual(2, sys.getrefcount(s))
         self.assertTrue(s, "foo bar")
 
         self.assertEqual(string_at("foo bar", 8), "foo bar\0")

File lib-python/2.7/ctypes/test/test_python_api.py

 
 ################################################################
 
-from sys import getrefcount as grc
+try:
+    from sys import getrefcount as grc
+except ImportError:
+    grc = None      # e.g. PyPy
 if sys.version_info > (2, 4):
     c_py_ssize_t = c_size_t
 else:

File lib-python/2.7/ctypes/test/test_refcounts.py

 class RefcountTestCase(unittest.TestCase):
 
     def test_1(self):
-        from sys import getrefcount as grc
+        try:
+            from sys import getrefcount as grc
+        except ImportError:
+            return unittest.skip("no sys.getrefcount()")
 
         f = dll._testfunc_callback_i_if
         f.restype = ctypes.c_int
 
 
     def test_refcount(self):
-        from sys import getrefcount as grc
+        try:
+            from sys import getrefcount as grc
+        except ImportError:
+            return unittest.skip("no sys.getrefcount()")
         def func(*args):
             pass
         # this is the standard refcount for func
 class AnotherLeak(unittest.TestCase):
     def test_callback(self):
         import sys
+        try:
+            from sys import getrefcount
+        except ImportError:
+            return unittest.skip("no sys.getrefcount()")
 
         proto = ctypes.CFUNCTYPE(ctypes.c_int, ctypes.c_int, ctypes.c_int)
         def func(a, b):

File lib-python/2.7/timeit.py

         else:
             it = [None] * number
         gcold = gc.isenabled()
-        gc.disable()
+        if '__pypy__' not in sys.builtin_module_names:
+            gc.disable()    # only do that on CPython
         try:
             timing = self.inner(it, self.timer)
         finally:

File lib_pypy/_ctypes_test.py

 import tempfile
 import gc
 
-# Monkeypatch & hacks to let ctypes.tests import.
-# This should be removed at some point.
-sys.getrefcount = lambda x: len(gc.get_referrers(x)) - 1
-
 def compile_shared():
     """Compile '_ctypes_test.c' into an extension module, and import it
     """

File lib_pypy/stackless.py

     def insert(self):
         if self.blocked:
             raise RuntimeError, "You cannot run a blocked tasklet"
-            if not self.alive:
-                raise RuntimeError, "You cannot run an unbound(dead) tasklet"
+        if not self.alive:
+            raise RuntimeError, "You cannot run an unbound(dead) tasklet"
         _scheduler_append(self)
 
     def remove(self):

File pypy/annotation/annrpython.py

 from pypy.objspace.flow.model import (Variable, Constant, FunctionGraph,
                                       c_last_exception, checkgraph)
 from pypy.translator import simplify, transform
-from pypy.annotation import model as annmodel, signature
+from pypy.annotation import model as annmodel, signature, unaryop, binaryop
 from pypy.annotation.bookkeeper import Bookkeeper
 import py
 log = py.log.Producer("annrpython")
         # occour for this specific, typed operation.
         if block.exitswitch == c_last_exception:
             op = block.operations[-1]
-            if op.opname in annmodel.BINARY_OPERATIONS:
+            if op.opname in binaryop.BINARY_OPERATIONS:
                 arg1 = self.binding(op.args[0])
                 arg2 = self.binding(op.args[1])
                 binop = getattr(pair(arg1, arg2), op.opname, None)
                 can_only_throw = annmodel.read_can_only_throw(binop, arg1, arg2)
-            elif op.opname in annmodel.UNARY_OPERATIONS:
+            elif op.opname in unaryop.UNARY_OPERATIONS:
                 arg1 = self.binding(op.args[0])
                 opname = op.opname
                 if opname == 'contains': opname = 'op_contains'
         return self.bookkeeper.newdict()
 
 
-    def _registeroperations(cls, model):
+    def _registeroperations(cls, unary_ops, binary_ops):
         # All unary operations
         d = {}
-        for opname in model.UNARY_OPERATIONS:
+        for opname in unary_ops:
             fnname = 'consider_op_' + opname
             exec py.code.Source("""
 def consider_op_%s(self, arg, *args):
 """ % (opname, opname)).compile() in globals(), d
             setattr(cls, fnname, d[fnname])
         # All binary operations
-        for opname in model.BINARY_OPERATIONS:
+        for opname in binary_ops:
             fnname = 'consider_op_' + opname
             exec py.code.Source("""
 def consider_op_%s(self, arg1, arg2, *args):
     _registeroperations = classmethod(_registeroperations)
 
 # register simple operations handling
-RPythonAnnotator._registeroperations(annmodel)
+RPythonAnnotator._registeroperations(unaryop.UNARY_OPERATIONS, binaryop.BINARY_OPERATIONS)
 
 
 class BlockedInference(Exception):

File pypy/annotation/binaryop.py

 from pypy.tool.pairtype import pair, pairtype
 from pypy.annotation.model import SomeObject, SomeInteger, SomeBool, s_Bool
 from pypy.annotation.model import SomeString, SomeChar, SomeList, SomeDict
-from pypy.annotation.model import SomeUnicodeCodePoint, SomeStringOrUnicode
+from pypy.annotation.model import SomeUnicodeCodePoint, SomeUnicodeString
 from pypy.annotation.model import SomeTuple, SomeImpossibleValue, s_ImpossibleValue
 from pypy.annotation.model import SomeInstance, SomeBuiltin, SomeIterator
 from pypy.annotation.model import SomePBC, SomeFloat, s_None
 from pypy.annotation.model import read_can_only_throw
 from pypy.annotation.model import add_knowntypedata, merge_knowntypedata
 from pypy.annotation.model import SomeGenericCallable
-from pypy.annotation.model import SomeUnicodeString
 from pypy.annotation.bookkeeper import getbookkeeper
 from pypy.objspace.flow.model import Variable, Constant
 from pypy.rlib import rarithmetic
         for s_item in s_tuple.items:
             if isinstance(s_item, SomeFloat):
                 pass   # or s_item is a subclass, like SomeInteger
-            elif isinstance(s_item, SomeStringOrUnicode) and s_item.no_nul:
+            elif (isinstance(s_item, SomeString) or
+                  isinstance(s_item, SomeUnicodeString)) and s_item.no_nul:
                 pass
             else:
                 no_nul = False

File pypy/annotation/model.py

             self.knowntypedata = knowntypedata
 
 class SomeStringOrUnicode(SomeObject):
+    """Base class for shared implementation of SomeString and SomeUnicodeString.
+
+    Cannot be an annotation."""
+
     immutable = True
     can_be_None=False
     no_nul = False  # No NUL character in the string.
 
     def __init__(self, can_be_None=False, no_nul=False):
+        assert type(self) is not SomeStringOrUnicode
         if can_be_None:
             self.can_be_None = True
         if no_nul:
             d2 = d2.copy(); d2['no_nul'] = 0   # ignored
         return d1 == d2
 
+    def nonnoneify(self):
+        return self.__class__(can_be_None=False, no_nul=self.no_nul)
+
 class SomeString(SomeStringOrUnicode):
     "Stands for an object which is known to be a string."
     knowntype = str
 
-    def nonnoneify(self):
-        return SomeString(can_be_None=False, no_nul=self.no_nul)
-
 class SomeUnicodeString(SomeStringOrUnicode):
     "Stands for an object which is known to be an unicode string"
     knowntype = unicode
 
-    def nonnoneify(self):
-        return SomeUnicodeString(can_be_None=False, no_nul=self.no_nul)
-
 class SomeChar(SomeString):
     "Stands for an object known to be a string of length 1."
     can_be_None = False
     else:
         raise RuntimeError("The annotator relies on 'assert' statements from the\n"
                      "\tannotated program: you cannot run it with 'python -O'.")
-
-# this has the side-effect of registering the unary and binary operations
-from pypy.annotation.unaryop  import UNARY_OPERATIONS
-from pypy.annotation.binaryop import BINARY_OPERATIONS

File pypy/annotation/signature.py

     actualtypes[:] = params_s
 
 def enforce_signature_return(funcdesc, sigtype, inferredtype):
-    return finish_type(sigtype, funcdesc.bookkeeper, funcdesc.pyobj)
+    s_sigret = finish_type(sigtype, funcdesc.bookkeeper, funcdesc.pyobj)
+    if not s_sigret.contains(inferredtype):
+        raise Exception("%r return value:\n"
+                        "expected %s,\n"
+                        "     got %s" % (funcdesc, s_sigret, inferredtype))
+    return s_sigret

File pypy/doc/config/objspace.usemodules.time.txt

 Use the 'time' module. 
 
 Obsolete; use :config:`objspace.usemodules.rctime` for our up-to-date version
-of the application-level 'time' module.
+of the application-level 'time' module, at least for C-like targets (the C
+and LLVM backends).

File pypy/module/_cffi_backend/misc.py

 from __future__ import with_statement
 from pypy.interpreter.error import OperationError, operationerrfmt
 from pypy.rpython.lltypesystem import lltype, llmemory, rffi
-from pypy.rlib.rarithmetic import r_uint, r_ulonglong
+from pypy.rlib.rarithmetic import r_uint, r_ulonglong, is_signed_integer_type
 from pypy.rlib.unroll import unrolling_iterable
 from pypy.rlib.objectmodel import keepalive_until_here, specialize
 from pypy.rlib import jit
 
 @specialize.argtype(1)
 def write_raw_integer_data(target, source, size):
-    for TP, TPP in _prim_unsigned_types:
-        if size == rffi.sizeof(TP):
-            rffi.cast(TPP, target)[0] = rffi.cast(TP, source)
-            return
+    if is_signed_integer_type(lltype.typeOf(source)):
+        for TP, TPP in _prim_signed_types:
+            if size == rffi.sizeof(TP):
+                rffi.cast(TPP, target)[0] = rffi.cast(TP, source)
+                return
+    else:
+        for TP, TPP in _prim_unsigned_types:
+            if size == rffi.sizeof(TP):
+                rffi.cast(TPP, target)[0] = rffi.cast(TP, source)
+                return
     raise NotImplementedError("bad integer size")
 
 def write_raw_float_data(target, source, size):

File pypy/module/_hashlib/interp_hashlib.py

         + rffi.sizeof(ropenssl.EVP_MD) * 2 + 208
 
 class W_Hash(Wrappable):
-    ctx = lltype.nullptr(ropenssl.EVP_MD_CTX.TO)
+    NULL_CTX = lltype.nullptr(ropenssl.EVP_MD_CTX.TO)
+    ctx = NULL_CTX
 
-    def __init__(self, space, name):
+    def __init__(self, space, name, copy_from=NULL_CTX):
         self.name = name
         digest_type = self.digest_type_by_name(space)
         self.digest_size = rffi.getintfield(digest_type, 'c_md_size')
         ctx = lltype.malloc(ropenssl.EVP_MD_CTX.TO, flavor='raw')
         rgc.add_memory_pressure(HASH_MALLOC_SIZE + self.digest_size)
         try:
-            ropenssl.EVP_DigestInit(ctx, digest_type)
+            if copy_from:
+                ropenssl.EVP_MD_CTX_copy(ctx, copy_from)
+            else:
+                ropenssl.EVP_DigestInit(ctx, digest_type)
             self.ctx = ctx
         except:
             lltype.free(ctx, flavor='raw')
             raise
 
     def __del__(self):
-        # self.lock.free()
         if self.ctx:
             ropenssl.EVP_MD_CTX_cleanup(self.ctx)
             lltype.free(self.ctx, flavor='raw')
 
     def copy(self, space):
         "Return a copy of the hash object."
-        w_hash = W_Hash(space, self.name)
         with self.lock:
-            ropenssl.EVP_MD_CTX_copy(w_hash.ctx, self.ctx)
-        return w_hash
+            return W_Hash(space, self.name, copy_from=self.ctx)
 
     def digest(self, space):
         "Return the digest value as a string of binary data."

File pypy/module/cpyext/src/pythread.c

 int
 PyThread_acquire_lock(PyThread_type_lock lock, int waitflag)
 {
-    return RPyThreadAcquireLock((struct RPyOpaqueThreadLock*)lock, waitflag);
+    return RPyThreadAcquireLock((struct RPyOpaque_ThreadLock*)lock, waitflag);
 }
 
 void
 PyThread_release_lock(PyThread_type_lock lock)
 {
-    RPyThreadReleaseLock((struct RPyOpaqueThreadLock*)lock);
+    RPyThreadReleaseLock((struct RPyOpaque_ThreadLock*)lock);
 }
 
 

File pypy/module/fcntl/test/test_fcntl.py

             os.unlink(i)
 
 class AppTestFcntl:
-    spaceconfig = dict(usemodules=('fcntl', 'array', 'struct', 'termios'))
+    spaceconfig = dict(usemodules=('fcntl', 'array', 'struct', 'termios', 'select', 'rctime'))
     def setup_class(cls):
         tmpprefix = str(udir.ensure('test_fcntl', dir=1).join('tmp_'))
         cls.w_tmp = cls.space.wrap(tmpprefix)
         import fcntl
         import array
         import os
+        import pty
+        import time
 
         try:
             from termios import TIOCGPGRP
         #raises(TypeError, fcntl.ioctl, 0, TIOCGPGRP, float(0))
         raises(TypeError, fcntl.ioctl, 0, TIOCGPGRP, 1, "foo")
 
+        child_pid, mfd = pty.fork()
+        if child_pid == 0:
+            # We're the child
+            time.sleep(1)
+            os._exit(0)
         try:
-            mfd = open("/dev/tty", 'r')
-        except IOError:
-            skip("couldn't open /dev/tty")
-        try:
+            # We're the parent, we want TIOCGPGRP calls after child started but before it dies
+            time.sleep(0.5)
+
             buf = array.array('i', [0])
             res = fcntl.ioctl(mfd, TIOCGPGRP, buf, True)
             assert res == 0
             res = fcntl.ioctl(mfd, TIOCGPGRP, "\x00\x00\x00\x00")
             assert res == expected
         finally:
-            mfd.close()
+            os.close(mfd)
 
     def test_ioctl_int(self):
         import os
         import fcntl
+        import pty
 
         try:
             from termios import TCFLSH, TCIOFLUSH
         except ImportError:
             skip("don't know how to test ioctl() on this platform")
 
-        try:
-            mfd = open("/dev/tty", 'r')
-        except IOError:
-            skip("couldn't open /dev/tty")
+        mfd, sfd = pty.openpty()
         try:
             assert fcntl.ioctl(mfd, TCFLSH, TCIOFLUSH) == 0
         finally:
-            mfd.close()
+            os.close(mfd)
+            os.close(sfd)
 
     def test_large_flag(self):
         import sys

File pypy/module/imp/test/test_import.py

 
 
 class AppTestMultithreadedImp(object):
-    spaceconfig = dict(usemodules=['thread', 'time'])
+    spaceconfig = dict(usemodules=['thread', 'rctime'])
 
     def setup_class(cls):
         #if not conftest.option.runappdirect:

File pypy/module/thread/test/support.py

 
 
 class GenericTestThread:
-    spaceconfig = dict(usemodules=('thread', 'time', 'signal'))
+    spaceconfig = dict(usemodules=('thread', 'rctime', 'signal'))
 
     def setup_class(cls):
         if cls.runappdirect:
                         return
                     adaptivedelay *= 1.05
                 print '*** timed out ***'
+            cls.w_waitfor = plain_waitfor
 
-            cls.w_waitfor = plain_waitfor
+            def py_timeout_killer(self, *args, **kwargs):
+                timeout_killer(*args, **kwargs)
+            cls.w_timeout_killer = cls.space.wrap(py_timeout_killer)
         else:
             @unwrap_spec(delay=int)
             def py_waitfor(space, w_condition, delay=1):
                 waitfor(space, w_condition, delay)
+            cls.w_waitfor = cls.space.wrap(interp2app(py_waitfor))
 
-            cls.w_waitfor = cls.space.wrap(interp2app(py_waitfor))
+            def py_timeout_killer(space, __args__):
+                args_w, kwargs_w = __args__.unpack()
+                args = map(space.unwrap, args_w)
+                kwargs = dict([
+                    (k, space.unwrap(v))
+                    for k, v in kwargs_w.iteritems()
+                ])
+                timeout_killer(*args, **kwargs)
+            cls.w_timeout_killer = cls.space.wrap(interp2app(py_timeout_killer))
+
         cls.w_busywait = cls.space.appexec([], """():
             import time
             return time.sleep
         """)
-
-        def py_timeout_killer(space, __args__):
-            args_w, kwargs_w = __args__.unpack()
-            args = map(space.unwrap, args_w)
-            kwargs = dict([
-                (k, space.unwrap(v))
-                for k, v in kwargs_w.iteritems()
-            ])
-            timeout_killer(*args, **kwargs)
-
-        cls.w_timeout_killer = cls.space.wrap(interp2app(py_timeout_killer))

File pypy/rlib/objectmodel.py

     def decorator(f):
         def get_annotation(t):
             from pypy.annotation.signature import annotation
-            from pypy.annotation.model import SomeObject, SomeStringOrUnicode
+            from pypy.annotation.model import SomeObject, SomeString, SomeUnicodeString
             if isinstance(t, SomeObject):
                 return t
             s_result = annotation(t)
-            if isinstance(s_result, SomeStringOrUnicode):
+            if (isinstance(s_result, SomeString) or
+                isinstance(s_result, SomeUnicodeString)):
                 return s_result.__class__(can_be_None=True)
             return s_result
         def get_type_descr_of_argument(arg):

File pypy/rlib/parsing/ebnfparse.py

 import py
+
 from pypy.rlib.parsing.parsing import PackratParser, Rule
-from pypy.rlib.parsing.tree import Nonterminal, Symbol, RPythonVisitor
+from pypy.rlib.parsing.tree import Nonterminal, RPythonVisitor
 from pypy.rlib.parsing.codebuilder import Codebuilder
 from pypy.rlib.parsing.regexparse import parse_regex
-import string
-from pypy.rlib.parsing.regex import *
+from pypy.rlib.parsing.regex import StringExpression
 from pypy.rlib.parsing.deterministic import DFA
 from pypy.rlib.parsing.lexer import Lexer, DummyLexer
 from pypy.rlib.objectmodel import we_are_translated
 
-set = py.builtin.set
 
 def make_ebnf_parser():
     NONTERMINALNAME = parse_regex("([a-z]|_)[a-z0-9_]*")
     assert len(s) == 1
     s = s[0]
     s.visit(visitor)
-    
+
     rules, changes = visitor.get_rules_and_changes()
     maker = TransformerMaker(rules, changes)
     ToAstVisitor = maker.make_transformer()
         s = parser.parse(tokens)
         if not we_are_translated():
             try:
-                if py.test.config.option.view: 
+                if py.test.config.option.view:
                     s.view()
             except AttributeError:
                 pass
-                
+
         return s
     return parse
 
             assert change == " " or change == newchange
             result.append((name, newchange))
         return result
-    
+
     def visit_decorated(self, node):
         expansions = node.children[0].visit(self)
         expansions, changes = zip(*expansions)
 
     def create_returning_code(self, expansion, subchange):
         assert len(expansion) == len(subchange)
-        children = []
         self.emit("children = []")
         for i, (symbol, c) in enumerate(zip(expansion, subchange)):
             if c == "[":

File pypy/rlib/rarithmetic.py

         return r_class(0)
 most_neg_value_of._annspecialcase_ = 'specialize:memo'
 
+def is_signed_integer_type(tp):
+    from pypy.rpython.lltypesystem import lltype, rffi
+    if tp is lltype.Signed:
+        return True
+    try:
+        r_class = rffi.platform.numbertype_to_rclass[tp]
+        return r_class.SIGNED
+    except KeyError:
+        return False   # not an integer type
+is_signed_integer_type._annspecialcase_ = 'specialize:memo'
+
 def highest_bit(n):
     """
     Calculates the highest set bit in n.  This function assumes that n is a

File pypy/rlib/rgc.py

 def get_rpy_roots():
     "NOT_RPYTHON"
     # Return the 'roots' from the GC.
-    # This stub is not usable on top of CPython.
     # The gc typically returns a list that ends with a few NULL_GCREFs.
-    raise NotImplementedError
+    return [_GcRef(x) for x in gc.get_objects()]
 
 def get_rpy_referents(gcref):
     "NOT_RPYTHON"

File pypy/rlib/test/test_rarithmetic.py

     assert most_neg_value_of_same_type(r_longlong(123)) == llmin
     assert most_neg_value_of_same_type(r_ulonglong(123)) == 0
 
+def test_is_signed_integer_type():
+    from pypy.rpython.lltypesystem import lltype, rffi
+    assert is_signed_integer_type(lltype.Signed)
+    assert is_signed_integer_type(rffi.SIGNEDCHAR)
+    assert is_signed_integer_type(lltype.SignedLongLong)
+    assert not is_signed_integer_type(lltype.Unsigned)
+    assert not is_signed_integer_type(lltype.UnsignedLongLong)
+    assert not is_signed_integer_type(lltype.Char)
+    assert not is_signed_integer_type(lltype.UniChar)
+    assert not is_signed_integer_type(lltype.Bool)
+
 def test_r_ulonglong():
     x = r_longlong(-1)
     y = r_ulonglong(x)

File pypy/rlib/test/test_signature.py

 from pypy.rlib import types
 from pypy.annotation import model
 from pypy.translator.translator import TranslationContext, graphof
+from pypy.rpython.lltypesystem import rstr
+from pypy.rpython.annlowlevel import LowLevelAnnotatorPolicy
 
 
-def annotate_at(f):
+def annotate_at(f, policy=None):
     t = TranslationContext()
-    a = t.buildannotator()
-    a.annotate_helper(f, [model.s_ImpossibleValue]*f.func_code.co_argcount)
+    a = t.buildannotator(policy=policy)
+    a.annotate_helper(f, [model.s_ImpossibleValue]*f.func_code.co_argcount, policy=policy)
     return a
 
 def sigof(a, f):
     g = graphof(a.translator, f)
     return [a.bindings[v] for v in g.startblock.inputargs] + [a.bindings[g.getreturnvar()]]
 
-def getsig(f):
-    a = annotate_at(f)
+def getsig(f, policy=None):
+    a = annotate_at(f, policy=policy)
     return sigof(a, f)
 
 def check_annotator_fails(caller):
     assert caller.func_name in repr(exc.args)
 
 
-def test_signature_bookkeeping():
+def test_bookkeeping():
     @signature('x', 'y', returns='z')
     def f(a, b):
         return a + len(b)
     assert f.foo == 'foo'
     assert f(1, 'hello') == 6
 
-def test_signature_basic():
+def test_basic():
     @signature(types.int(), types.str(), returns=types.char())
     def f(a, b):
         return b[a]
     assert getsig(f) == [model.SomeInteger(), model.SomeString(), model.SomeChar()]
 
-def test_signature_arg_errors():
+def test_arg_errors():
     @signature(types.int(), types.str(), returns=types.int())
     def f(a, b):
         return a + len(b)
     def bad_for_body(): # would give error inside 'f' body, instead errors at call
         f('a', 'b')
 
-def test_signature_return():
+def test_return():
     @signature(returns=types.str())
     def f():
         return 'a'
     a = annotate_at(g)
     assert sigof(a, f) == [model.SomeString(), model.SomeString()]
 
-def test_signature_return_errors():
+def test_return_errors():
     @check_annotator_fails
     @signature(returns=types.int())
     def int_not_char():
         return 'a'
+
     @check_annotator_fails
     @signature(types.str(), returns=types.int())
     def str_to_int(s):
         return s
 
+    @signature(returns=types.str())
+    def str_not_None():
+        return None
+    @check_annotator_fails
+    def caller_of_str_not_None():
+        return str_not_None()
 
-def test_signature_none():
+@py.test.mark.xfail
+def test_return_errors_xfail():
+    @check_annotator_fails
+    @signature(returns=types.str())
+    def str_not_None():
+        return None
+
+
+def test_none():
     @signature(returns=types.none())
     def f():
         pass
     assert getsig(f) == [model.s_None]
 
-def test_signature_float():
+def test_float():
     @signature(types.longfloat(), types.singlefloat(), returns=types.float())
     def f(a, b):
         return 3.0
     assert getsig(f) == [model.SomeLongFloat(), model.SomeSingleFloat(), model.SomeFloat()]
 
-def test_signature_unicode():
+def test_unicode():
     @signature(types.unicode(), returns=types.int())
     def f(u):
         return len(u)
     assert getsig(f) == [model.SomeUnicodeString(), model.SomeInteger()]
 
 
-def test_signature_list():
+def test_ptr():
+    policy = LowLevelAnnotatorPolicy()
+    @signature(types.ptr(rstr.STR), returns=types.none())
+    def f(buf):
+        pass
+    argtype = getsig(f, policy=policy)[0]
+    assert isinstance(argtype, model.SomePtr)
+    assert argtype.ll_ptrtype.TO == rstr.STR
+
+    def g():
+        f(rstr.mallocstr(10))
+    getsig(g, policy=policy)
+
+
+def test_list():
     @signature(types.list(types.int()), returns=types.int())
     def f(a):
         return len(a)
         l.append('b')
     getsig(can_append)
 
-def test_signature_array():
+def test_array():
     @signature(returns=types.array(types.int()))
     def f():
         return [1]
         l.append(2)
     check_annotator_fails(try_append)
 
-def test_signature_dict():
+def test_dict():
     @signature(returns=types.dict(types.str(), types.int()))
     def f():
         return {'a': 1, 'b': 2}
     assert rettype.dictdef.dictvalue.s_value == model.SomeInteger()
 
 
-def test_signature_instance():
+def test_instance():
     class C1(object):
         pass
     class C2(C1):
     def bad_for_body():
         f(C1())
 
-def test_signature_self():
+def test_self():
     @finishsigs
     class C(object):
         @signature(types.self(), types.self(), returns=types.none())
     assert isinstance(argtype, model.SomeInstance)
     assert argtype.classdef.classdesc.pyobj == C
 
-def test_signature_self_error():
+def test_self_error():
     class C(object):
         @signature(types.self(), returns=types.none())
         def incomplete_sig_meth(self):

File pypy/rlib/types.py

     return model.SomeChar()
 
 
+def ptr(ll_type):
+    from pypy.rpython.lltypesystem.lltype import Ptr
+    return model.SomePtr(Ptr(ll_type))
+
+
 def list(element):
     listdef = ListDef(None, element, mutated=True, resized=True)
     return model.SomeList(listdef)

File pypy/rpython/lltypesystem/lltype.py

         assert n is None
         o = _opaque(T, initialization=initialization)
     else:
-        raise TypeError, "malloc for Structs and Arrays only"
-    if T._gckind != 'gc' and not immortal and flavor.startswith('gc'):
+        raise TypeError, "malloc: unmallocable type"
+    if flavor == 'gc' and T._gckind != 'gc' and not immortal:
         raise TypeError, "gc flavor malloc of a non-GC non-immortal structure"
     if flavor == "raw" and not immortal and track_allocation:
         leakfinder.remember_malloc(o, framedepth=2)
-    solid = immortal or not flavor.startswith('gc') # immortal or non-gc case
+    solid = immortal or flavor == 'raw'
     return _ptr(Ptr(T), o, solid)
 
 def free(p, flavor, track_allocation=True):

File pypy/rpython/lltypesystem/rffi.py

     # char* -> str
     # doesn't free char*
     def charp2str(cp):
-        b = builder_class()
+        size = 0
+        while cp[size] != lastchar:
+            size += 1
+        b = builder_class(size)
         i = 0
         while cp[i] != lastchar:
             b.append(cp[i])

File pypy/rpython/rmodel.py

 from pypy.tool.pairtype import pairtype, extendabletype, pair
-from pypy.annotation import model as annmodel
+from pypy.annotation import model as annmodel, unaryop, binaryop
 from pypy.annotation import description
 from pypy.objspace.flow.model import Constant
 from pypy.rpython.lltypesystem.lltype import \
                                         "'%s' on %r" % (opname, self))
         setattr(rcls, attr, missing_rtype_operation)
 
-for opname in annmodel.UNARY_OPERATIONS:
+for opname in unaryop.UNARY_OPERATIONS:
     make_missing_op(Repr, opname)
 
-for opname in annmodel.BINARY_OPERATIONS:
+for opname in binaryop.BINARY_OPERATIONS:
     make_missing_op(pairtype(Repr, Repr), opname)
 
 # not in BINARY_OPERATIONS

File pypy/rpython/rtyper.py

 import os
 import py
 from pypy.tool.pairtype import pair
-from pypy.annotation import model as annmodel
+from pypy.annotation import model as annmodel, unaryop, binaryop
 from pypy.annotation.annrpython import FAIL
 from pypy.objspace.flow.model import Variable, Constant
 from pypy.objspace.flow.model import SpaceOperation, c_last_exception
 
     # __________ regular operations __________
 
-    def _registeroperations(cls, model):
+    def _registeroperations(cls, unary_ops, binary_ops):
         d = {}
         # All unary operations
-        for opname in model.UNARY_OPERATIONS:
+        for opname in unary_ops:
             fnname = 'translate_op_' + opname
             exec py.code.compile("""
                 def translate_op_%s(self, hop):
                 """ % (opname, opname)) in globals(), d
             setattr(cls, fnname, d[fnname])
         # All binary operations
-        for opname in model.BINARY_OPERATIONS:
+        for opname in binary_ops:
             fnname = 'translate_op_' + opname
             exec py.code.compile("""
                 def translate_op_%s(self, hop):
         attachRuntimeTypeInfo(GCSTRUCT, funcptr, destrptr, None)
 
 # register operations from annotation model
-RPythonTyper._registeroperations(annmodel)
+RPythonTyper._registeroperations(unaryop.UNARY_OPERATIONS, binaryop.BINARY_OPERATIONS)
 
 # ____________________________________________________________
 

File pypy/rpython/test/test_rbool.py

 from pypy.translator.translator import TranslationContext
-from pypy.annotation import model as annmodel
+from pypy.annotation import unaryop, binaryop
 from pypy.rpython.test import snippet
 from pypy.rpython.test.tool import BaseRtypingTest, LLRtypeMixin, OORtypeMixin
 
 
     def DONTtest_unary_operations(self):
         # XXX TODO test if all unary operations are implemented
-        for opname in annmodel.UNARY_OPERATIONS:
+        for opname in unaryop.UNARY_OPERATIONS:
             print 'UNARY_OPERATIONS:', opname
 
     def DONTtest_binary_operations(self):
         # XXX TODO test if all binary operations are implemented
-        for opname in annmodel.BINARY_OPERATIONS:
+        for opname in binaryop.BINARY_OPERATIONS:
             print 'BINARY_OPERATIONS:', opname
 
 class BaseTestRbool(BaseRtypingTest):

File pypy/rpython/test/test_rfloat.py

 import sys
 from pypy.translator.translator import TranslationContext
+from pypy.annotation import unaryop, binaryop
 from pypy.rpython.test import snippet
 from pypy.rpython.test.tool import BaseRtypingTest, LLRtypeMixin, OORtypeMixin
 from pypy.rlib.rarithmetic import (
 
     def DONTtest_unary_operations(self):
         # XXX TODO test if all unary operations are implemented
-        for opname in annmodel.UNARY_OPERATIONS:
+        for opname in unaryop.UNARY_OPERATIONS:
             print 'UNARY_OPERATIONS:', opname
 
     def DONTtest_binary_operations(self):
         # XXX TODO test if all binary operations are implemented
-        for opname in annmodel.BINARY_OPERATIONS:
+        for opname in binaryop.BINARY_OPERATIONS:
             print 'BINARY_OPERATIONS:', opname
 
 class BaseTestRfloat(BaseRtypingTest):
     def test_formatd_huge(self):
         skip('formatd is broken on ootype')
 
-    def test_string_to_float(self):
-        skip('string_to_float is broken on ootype')
+    def test_parts_to_float(self):
+        skip('parts_to_float is broken on ootype')

File pypy/rpython/test/test_rint.py

 import py
 import sys, operator
 from pypy.translator.translator import TranslationContext
-from pypy.annotation import model as annmodel
+from pypy.annotation import unaryop, binaryop
 from pypy.rpython.test import snippet
 from pypy.rlib.rarithmetic import r_int, r_uint, r_longlong, r_ulonglong
 from pypy.rlib.rarithmetic import ovfcheck, r_int64, intmask, int_between
 
     def DONTtest_unary_operations(self):
         # XXX TODO test if all unary operations are implemented
-        for opname in annmodel.UNARY_OPERATIONS:
+        for opname in unaryop.UNARY_OPERATIONS:
             print 'UNARY_OPERATIONS:', opname
 
     def DONTtest_binary_operations(self):
         # XXX TODO test if all binary operations are implemented
-        for opname in annmodel.BINARY_OPERATIONS:
+        for opname in binaryop.BINARY_OPERATIONS:
             print 'BINARY_OPERATIONS:', opname
 
 

File pypy/rpython/test/test_runicode.py

         def percentS(ch):
             x = "%s" % (ch + "bc")
             y = u"%s" % (unichr(ord(ch)) + u"bc")
-            return len(x)+len(y)
+            return len(x) + len(y)
         #
         res = self.interpret(percentS, ["a"])
         assert res == 6
         py.test.skip("not supported")
 
     test_char_isxxx = unsupported
+    test_isdigit = unsupported
+    test_str_isalpha = unsupported
     test_upper = unsupported
     test_lower = unsupported
     test_splitlines = unsupported

File pypy/tool/algo/unionfind.py

-# This is a general algorithm used by the annotator.
+# This is a general algorithm used by the annotator, translator, and other code
 
 # union-find impl, a info object is attached to the roots
 
+
 class UnionFind(object):
-
     def __init__(self, info_factory=None):
         self.link_to_parent = {}
         self.weight = {}
     # mapping-like [] access
     def __getitem__(self, obj):
         if obj not in self.link_to_parent:
-            raise KeyError, obj
+            raise KeyError(obj)
 
         ignore, rep, info = self.find(obj)
 
 
         return False, parent, self.root_info[parent]
 
-
     def union(self, obj1, obj2): # -> not_noop, rep, info
 
         new1, rep1, info1 = self.find(obj1)
         self.root_info[rep1] = info1
 
         return True, rep1, info1
-        
-
-    

File pypy/tool/genstatistic.py

 pypydir = py.path.local(autopath.pypydir)
 
 def isdocfile(p):
-    return p.ext == '.txt' or p.basename in ('README', 'NOTES', 'LICENSE')
+    return (p.ext in ('.txt', '.rst') or
+            p.basename in ('README', 'NOTES', 'LICENSE'))
 
 def istestfile(p):
     if not p.check(file=1, ext='.py'): 

File pypy/tool/pytest/objspace.py

             if key == 'usemodules':
                 if info is not None:
                     for modname in value:
+                        if modname == 'time':
+                            continue   # always either 'time' or 'rctime',
+                                       # and any is fine
                         ok = info.get('objspace.usemodules.%s' % modname,
                                       False)
                         if not ok:

File pypy/tool/release/package.py

     shutil.copytree(str(basedir.join('lib_pypy')),
                     str(pypydir.join('lib_pypy')),
                     ignore=ignore_patterns('.svn', 'py', '*.pyc', '*~'))
-    for file in ['LICENSE', 'README']:
+    for file in ['LICENSE', 'README.rst']:
         shutil.copy(str(basedir.join(file)), str(pypydir))
     pypydir.ensure('include', dir=True)
     if sys.platform == 'win32':

File pypy/tool/release/test/test_package.py

         assert not prefix.join('lib_pypy', 'py').check()
         assert not prefix.join('lib_pypy', 'ctypes_configure').check()
         assert prefix.join('LICENSE').check()
-        assert prefix.join('README').check()
+        assert prefix.join('README.rst').check()
         if package.USE_ZIPFILE_MODULE:
             zh = zipfile.ZipFile(str(builddir.join('%s.zip' % test)))
             assert zh.open('%s/lib_pypy/syslog.py' % test)

File pypy/translator/backendopt/canraise.py

-from pypy.translator.simplify import get_graph
-from pypy.rpython.lltypesystem.lloperation import llop, LL_OPERATIONS
-from pypy.rpython.lltypesystem import lltype
+import py
+
+from pypy.rpython.lltypesystem.lloperation import LL_OPERATIONS
+from pypy.tool.ansi_print import ansi_log
 from pypy.translator.backendopt import graphanalyze
 from pypy.translator.simplify import get_funcobj
 
-import py
-from pypy.tool.ansi_print import ansi_log
-log = py.log.Producer("canraise") 
-py.log.setconsumer("canraise", ansi_log) 
+log = py.log.Producer("canraise")
+py.log.setconsumer("canraise", ansi_log)
+
 
 class RaiseAnalyzer(graphanalyze.BoolGraphAnalyzer):
     def analyze_simple_operation(self, op, graphinfo):

File pypy/translator/backendopt/constfold.py

-from pypy.objspace.flow.model import Constant, Variable, SpaceOperation
-from pypy.objspace.flow.model import c_last_exception
-from pypy.objspace.flow.model import mkentrymap
-from pypy.translator.backendopt.support import log
-from pypy.translator.simplify import eliminate_empty_blocks
+from pypy.objspace.flow.model import (Constant, Variable, SpaceOperation,
+    c_last_exception, mkentrymap)
+from pypy.rpython.lltypesystem import lltype
+from pypy.rpython.lltypesystem.lloperation import llop
 from pypy.translator.unsimplify import insert_empty_block, split_block
-from pypy.rpython.lltypesystem.lloperation import llop
-from pypy.rpython.lltypesystem import lltype
 
 
 def fold_op_list(operations, constants, exit_early=False, exc_catch=False):
                     pass
                 except (KeyboardInterrupt, SystemExit):
                     raise
-                except Exception, e:
+                except Exception:
                     pass   # turn off reporting these as warnings: useless
                     #log.WARNING('constant-folding %r:' % (spaceop,))
                     #log.WARNING('  %s: %s' % (e.__class__.__name__, e))
 def constant_fold_block(block):
     constants = {}
     block.operations = fold_op_list(block.operations, constants,
-                           exc_catch = block.exitswitch == c_last_exception)
+                           exc_catch=block.exitswitch == c_last_exception)
     if constants:
         if block.exitswitch in constants:
             switch = constants[block.exitswitch].value
         if same_as:
             constant_fold_block(block)
     return count
-                
+
 def constant_fold_graph(graph):
     # first fold inside the blocks
     for block in graph.iterblocks():
                     constants[v2] = v1
             if constants:
                 prepare_constant_fold_link(link, constants, splitblocks)
-        if  splitblocks:
+        if splitblocks:
             rewire_links(splitblocks, graph)
         if not diffused and not splitblocks:
             break # finished

File pypy/translator/backendopt/escape.py

-from pypy.objspace.flow.model import Variable, Constant
+from pypy.objspace.flow.model import Variable
 from pypy.rpython.lltypesystem import lltype
 from pypy.translator.simplify import get_graph
-from pypy.rpython.rmodel import inputconst
-from pypy.translator.backendopt import support
 from pypy.tool.uid import uid
 
+
 class CreationPoint(object):
     def __init__(self, creation_method, TYPE, op=None):
         self.escapes = False
 
     def seen_graphs(self):
         return self.functionargs.keys()
-    
+
     def getstate(self, var_or_const):
         if not isonheap(var_or_const):
             return None
             varstate = VarState(crep)
         self.varstates[var_or_const] = varstate
         return varstate
-            
+
     def getstates(self, varorconstlist):
         return [self.getstate(var) for var in varorconstlist]
-    
+
     def setstate(self, var, state):
         self.varstates[var] = state
-    
+
     def get_creationpoint(self, var, method="?", op=None):
         if var in self.creationpoints:
             return self.creationpoints[var]
         crep = CreationPoint(method, var.concretetype, op)
         self.creationpoints[var] = crep
         return crep
-    
+
     def schedule_function(self, graph):
         startblock = graph.startblock
         if graph in self.functionargs:
             return
         self.curr_block = block
         self.curr_graph = graph
-        
+
         for op in block.operations:
             self.flow_operation(op)
         for exit in block.exits:
 
     def flow_operation(self, op):
         args = self.getstates(op.args)
-        opimpl = getattr(self, 'op_'+op.opname, None)
+        opimpl = getattr(self, 'op_' + op.opname, None)
         if opimpl is not None:
             res = opimpl(op, *args)
             if res is not NotImplemented:
                 self.setstate(op.result, res)
                 return
-            
+
         if isonheap(op.result) or filter(None, args):
             for arg in args:
                 if arg is not None:
                     self.escapes(arg)
-        
+
     def complete(self):
         while self.scheduled:
             block, graph = self.scheduled.popitem()
 
     def op_cast_pointer(self, op, state):
         return state
-    
+
     def op_setfield(self, op, objstate, fieldname, valuestate):
         if valuestate is not None:
             # be pessimistic for now:
     def op_getarrayitem(self, op, objstate, indexstate):
         if isonheap(op.result):
             return VarState(self.get_creationpoint(op.result, "getarrayitem", op))
-    
+
     def op_getfield(self, op, objstate, fieldname):
         if isonheap(op.result):
             # assume that getfield creates a new value
     seen = {}
     return [graph for graph in adi.seen_graphs()
         if is_malloc_like(adi, graph, seen)]
-
-
-

File pypy/translator/backendopt/finalizer.py

     ok_operations = ['ptr_nonzero', 'ptr_eq', 'ptr_ne', 'free', 'same_as',
                      'direct_ptradd', 'force_cast', 'track_alloc_stop',
                      'raw_free']
-    
+
     def analyze_light_finalizer(self, graph):
         result = self.analyze_direct_call(graph)
         if (result is self.top_result() and
             getattr(graph.func, '_must_be_light_finalizer_', False)):
             raise FinalizerError(FinalizerError.__doc__, graph)
         return result
-    
+
     def analyze_simple_operation(self, op, graphinfo):
         if op.opname in self.ok_operations:
             return self.bottom_result()
             TP = op.result.concretetype
             if not isinstance(TP, lltype.Ptr) or TP.TO._gckind == 'raw':
                 # primitive type
-                return self.bottom_result()            
+                return self.bottom_result()
         return self.top_result()

File pypy/translator/backendopt/graphanalyze.py

 from pypy.translator.simplify import get_graph, get_funcobj
-from pypy.rpython.lltypesystem.lloperation import llop, LL_OPERATIONS
-from pypy.rpython.lltypesystem import lltype
+from pypy.tool.algo.unionfind import UnionFind
+
 
 class GraphAnalyzer(object):
     verbose = False
 
     def __init__(self, translator):
         self.translator = translator
-        self.analyzed_calls = {}
-        self.analyzed_indirect_calls = {}
-        self.recursion_hit = False
+        self._analyzed_calls = UnionFind(lambda graph: Dependency(self))
 
     # method overridden by subclasses
 
     @staticmethod
-    def join_two_results(result1, result2):
-        raise NotImplementedError("abstract base class")
-
-    @staticmethod
     def bottom_result():
         raise NotImplementedError("abstract base class")
 
         # only an optimization, safe to always return False
         return False
 
+    @staticmethod
+    def result_builder():
+        raise NotImplementedError("abstract base class")
+
+    @staticmethod
+    def add_to_result(result, other):
+        raise NotImplementedError("abstract base class")
+
+    @staticmethod
+    def finalize_builder(result):
+        raise NotImplementedError("abstract base class")
+
+    @staticmethod
+    def join_two_results(result1, result2):
+        raise NotImplementedError("abstract base class")
+
     def analyze_simple_operation(self, op, graphinfo=None):
         raise NotImplementedError("abstract base class")
 
 
     # general methods
 
-    def join_results(self, results):
-        result = self.bottom_result()
-        for sub in results:
-            result = self.join_two_results(result, sub)
-        return result
-
     def compute_graph_info(self, graph):
         return None
 
         return x
 
     def analyze_direct_call(self, graph, seen=None):
-        if graph in self.analyzed_calls:
-            return self.analyzed_calls[graph]
         if seen is None:
-            seen = set([graph])
-            self.recursion_hit = False
-            started_here = True
-        elif graph in seen:
-            self.recursion_hit = True
-            return self.bottom_result()
-        else:
-            started_here = False
-            seen.add(graph)
-        result = self.bottom_result()
+            seen = DependencyTracker(self)
+        if not seen.enter(graph):
+            return seen.get_cached_result(graph)
+        result = self.result_builder()
         graphinfo = self.compute_graph_info(graph)
         for block in graph.iterblocks():
             if block is graph.startblock:
-                result = self.join_two_results(
-                        result, self.analyze_startblock(block, seen))
+                result = self.add_to_result(
+                    result,
+                    self.analyze_startblock(block, seen)
+                )
             elif block is graph.exceptblock:
-                result = self.join_two_results(
-                        result, self.analyze_exceptblock(block, seen))
-            for op in block.operations:
-                result = self.join_two_results(
-                        result, self.analyze(op, seen, graphinfo))
-            for exit in block.exits:
-                result = self.join_two_results(
-                        result, self.analyze_link(exit, seen))
+                result = self.add_to_result(
+                    result,
+                    self.analyze_exceptblock(block, seen)
+                )
+            if not self.is_top_result(result):
+                for op in block.operations:
+                    result = self.add_to_result(
+                        result,
+                        self.analyze(op, seen, graphinfo)
+                    )
+                    if self.is_top_result(result):
+                        break
+            if not self.is_top_result(result):
+                for exit in block.exits:
+                    result = self.add_to_result(
+                        result,
+                        self.analyze_link(exit, seen)
+                    )
+                    if self.is_top_result(result):
+                        break
             if self.is_top_result(result):
-                self.analyzed_calls[graph] = result
-                return result
-        if not self.recursion_hit or started_here:
-            self.analyzed_calls[graph] = result
+                break
+        result = self.finalize_builder(result)
+        seen.leave_with(result)
         return result
 
     def analyze_indirect_call(self, graphs, seen=None):
-        graphs_t = tuple(graphs)
-        try:
-            return self.analyzed_indirect_calls[graphs_t]
-        except KeyError:
-            results = []
-            cache = True
-            for graph in graphs:
-                results.append(self.analyze_direct_call(graph, seen))
-                cache = cache and (graph in self.analyzed_calls)
-            res = self.join_results(results)
-            if cache:
-                self.analyzed_indirect_calls[graphs_t] = res
-            return res
+        result = self.result_builder()
+        for graph in graphs:
+            result = self.add_to_result(
+                result,
+                self.analyze_direct_call(graph, seen)
+            )
+            if self.is_top_result(result):
+                break
+        return self.finalize_builder(result)
 
     def analyze_oosend(self, TYPE, name, seen=None):
         graphs = TYPE._lookup_graphs(name)
             for block, op in graph.iterblockops():
                 self.analyze(op)
 
+
+class Dependency(object):
+    def __init__(self, analyzer):
+        self._analyzer = analyzer
+        self._result = analyzer.bottom_result()
+
+    def merge_with_result(self, result):
+        self._result = self._analyzer.join_two_results(self._result, result)
+
+    def absorb(self, other):
+        self.merge_with_result(other._result)
+
+
+class DependencyTracker(object):
+    """This tracks the analysis of cyclic call graphs."""
+
+    # The point is that GraphAnalyzer works fine if the question we ask
+    # is about a single graph; but in the case of recursion, it will
+    # fail if we ask about multiple graphs.  The purpose of this
+    # class is to fix the cache in GraphAnalyzer._analyzed_calls after
+    # each round, whenever a new set of graphs have been added to it.
+    # It works by assuming that the following is correct: for any set of
+    # graphs that can all (indirectly) call each other, all these graphs
+    # will get the same answer that is the 'join_two_results' of all of
+    # them.
+
+    def __init__(self, analyzer):
+        self.analyzer = analyzer
+        # the UnionFind object, which works like a mapping {graph: Dependency}
+        # (shared with GraphAnalyzer._analyzed_calls)
+        self.graph_results = analyzer._analyzed_calls
+        # the current stack of graphs being analyzed
+        self.current_stack = []
+        self.current_stack_set = set()
+
+    def enter(self, graph):
+        if graph not in self.graph_results:
+            self.current_stack.append(graph)
+            self.current_stack_set.add(graph)
+            self.graph_results.find(graph)
+            return True
+        else:
+            if graph in self.current_stack_set:
+                # found a cycle; merge all graphs in that cycle
+                i = len(self.current_stack) - 1
+                while self.current_stack[i] is not graph:
+                    self.graph_results.union(self.current_stack[i], graph)
+                    i -= 1
+            return False
+
+    def leave_with(self, result):
+        graph = self.current_stack.pop()
+        self.current_stack_set.remove(graph)
+        dep = self.graph_results[graph]
+        dep.merge_with_result(result)
+
+    def get_cached_result(self, graph):
+        dep = self.graph_results[graph]
+        return dep._result
+
+
 class BoolGraphAnalyzer(GraphAnalyzer):
     """generic way to analyze graphs: recursively follow it until the first
     operation is found on which self.analyze_simple_operation returns True"""
 
-    @staticmethod
-    def join_two_results(result1, result2):
-        return result1 or result2
+    def bottom_result(self):
+        return False
 
-    @staticmethod
-    def is_top_result(result):
+    def top_result(self):
+        return True
+
+    def is_top_result(self, result):
         return result
 
-    @staticmethod
-    def bottom_result():
+    def result_builder(self):
         return False
 
-    @staticmethod
-    def top_result():
-        return True
+    def add_to_result(self, result, other):
+        return self.join_two_results(result, other)
 
+    def finalize_builder(self, result):
+        return result
+
+    def join_two_results(self, result1, result2):
+        return result1 or result2

File pypy/translator/backendopt/inline.py

 import sys
-from pypy.translator.simplify import join_blocks, cleanup_graph
-from pypy.translator.simplify import get_graph, get_funcobj
-from pypy.translator.unsimplify import copyvar
-from pypy.objspace.flow.model import Variable, Constant, Block, Link
-from pypy.objspace.flow.model import SpaceOperation, c_last_exception
-from pypy.objspace.flow.model import FunctionGraph
-from pypy.objspace.flow.model import mkentrymap, checkgraph
-from pypy.annotation import model as annmodel
-from pypy.rpython.lltypesystem.lltype import Bool, Signed, typeOf, Void, Ptr
-from pypy.rpython.lltypesystem.lltype import normalizeptr
+
+from pypy.objspace.flow.model import (Variable, Constant, Block, Link,
+    SpaceOperation, c_last_exception, FunctionGraph, mkentrymap)
+from pypy.rpython.lltypesystem.lltype import Bool, Signed, typeOf, Void, Ptr, normalizeptr
 from pypy.rpython.ootypesystem import ootype
-from pypy.rpython import rmodel
 from pypy.tool.algo import sparsemat
 from pypy.translator.backendopt import removenoops
-from pypy.translator.backendopt.support import log
-from pypy.translator.unsimplify import split_block
-from pypy.translator.backendopt.support import find_backedges, find_loop_blocks
 from pypy.translator.backendopt.canraise import RaiseAnalyzer
+from pypy.translator.backendopt.support import log, find_loop_blocks
+from pypy.translator.simplify import join_blocks, cleanup_graph, get_graph, get_funcobj
+from pypy.translator.unsimplify import copyvar, split_block
+
 
 class CannotInline(Exception):
     pass
 
+
 def get_meth_from_oosend(op):
-    method_name = op.args[0].value
     INSTANCE = op.args[1].concretetype
     _, meth = INSTANCE._lookup(op.args[0].value)
     virtual = getattr(meth, '_virtual', True)
     else:
         return meth
 
-class CanRaise:
+
+class CanRaise(object):
     def __init__(self, can_raise):
         self.can_raise = can_raise
 
+
 def collect_called_graphs(graph, translator, include_oosend=True):
     graphs_or_something = {}
     for block in graph.iterblocks():
 def inline_function(translator, inline_func, graph, lltype_to_classdef,
                     raise_analyzer, call_count_pred=None, cleanup=True):
     inliner = Inliner(translator, graph, inline_func, lltype_to_classdef,
-                      raise_analyzer = raise_analyzer,
+                      raise_analyzer=raise_analyzer,
                       call_count_pred=call_count_pred, cleanup=cleanup)
     return inliner.inline_all()
 
 def simple_inline_function(translator, inline_func, graph):
     inliner = Inliner(translator, graph, inline_func,
                       translator.rtyper.lltype_to_classdef_mapping(),
-                      raise_analyzer = RaiseAnalyzer(translator))
+                      raise_analyzer=RaiseAnalyzer(translator))
     return inliner.inline_all()
 
 
     #(e.g. if you do only raise XXXError) by doing pattern matching
     currvar = block.exits[0].args[1]
     ops = block.operations
-    i = len(ops)-1
+    i = len(ops) - 1
     while True:
         if isinstance(currvar, Constant):
             value = currvar.value
     return False
 
 class BaseInliner(object):
-    def __init__(self, translator, graph, lltype_to_classdef, 
+    def __init__(self, translator, graph, lltype_to_classdef,
                  inline_guarded_calls=False,
                  inline_guarded_calls_no_matter_what=False,
                  raise_analyzer=None,
                 label = countop.args[1].value
                 if not call_count_pred(label):
                     continue
-            operation = block.operations[index_operation]
             self.inline_once(block, index_operation)
             count += 1
         if self.do_cleanup:
             index_operation == len(block.operations) - 1):
             self.exception_guarded = True
             if self.inline_guarded_calls:
-                if (not self.inline_guarded_calls_no_matter_what and 
+                if (not self.inline_guarded_calls_no_matter_what and
                     does_raise_directly(self.graph_to_inline, self.raise_analyzer)):
                     raise CannotInline("can't inline because the call is exception guarded")
             elif any_call_to_raising_graphs(self.graph_to_inline,
                       for var in self.original_passon_vars]
         self._passon_vars[cache_key] = result
         return result
-        
+
     def copy_operation(self, op):
         args = [self.get_new_name(arg) for arg in op.args]
         result = SpaceOperation(op.opname, args, self.get_new_name(op.result))
         if hasattr(link, 'llexitcase'):
             newlink.llexitcase = link.llexitcase
         return newlink
-        
 
     def find_args_in_exceptional_case(self, link, block, etype, evalue, afterblock, passon_vars):
         linkargs = []
         copiedreturnblock.exitswitch = None
         copiedreturnblock.recloseblock(linkfrominlined)
         assert copiedreturnblock.exits[0].target == afterblock
-       
+
     def rewire_exceptblock(self, afterblock):
         #let links to exceptblock of the graph to inline go to graphs exceptblock
         copiedexceptblock = self.copy_block(self.graph_to_inline.exceptblock)
                         else:
                             # if self.graph.exceptblock was never used before
                             a2.concretetype = a1.concretetype
-    
+
     def rewire_exceptblock_with_guard(self, afterblock, copiedexceptblock):
         # this rewiring does not always succeed. in the cases where it doesn't
         # there will be generic code inserted
 
     def generic_exception_matching(self, afterblock, copiedexceptblock):
         #XXXXX don't look: insert blocks that do exception matching
-        #for the cases where direct matching did not work        
+        #for the cases where direct matching did not work
         exc_match = Constant(
             self.translator.rtyper.getexceptiondata().fn_exception_match)
         exc_match.concretetype = typeOf(exc_match.value)
         linktoinlined.args = passon_args
         afterblock.inputargs = [self.op.result] + afterblock.inputargs
         if self.graph_to_inline.returnblock in self.entrymap:
-            self.rewire_returnblock(afterblock) 
+            self.rewire_returnblock(afterblock)
         if self.graph_to_inline.exceptblock in self.entrymap:
             self.rewire_exceptblock(afterblock)
         if self.exception_guarded:
                     if graph is not None and graph in ok_to_call:
                         add(parentgraph, block, op, graph)
     return result
-    
+
 def instrument_inline_candidates(graphs, threshold):
     cache = {None: False}
     def candidate(graph):
     for parentgraph in graphs:
         for block in parentgraph.iterblocks():
             ops = block.operations
-            i = len(ops)-1
+            i = len(ops) - 1
             while i >= 0:
                 op = ops[i]
                 i -= 1
                         dummy.concretetype = Void
                         count = SpaceOperation('instrument_count',
                                                [tag, label], dummy)
-                        ops.insert(i+1, count)
+                        ops.insert(i + 1, count)
                         n += 1
     log.inlining("%d call sites instrumented" % n)
 
                   callgraph=None,
                   call_count_pred=None,
                   heuristic=inlining_heuristic):
-    
+
     assert threshold is not None and threshold != 1
     to_cleanup = {}
     from heapq import heappush, heappop, heapreplace, heapify
         count = auto_inlining(translator, threshold, callgraph=callgraph,
                               heuristic=heuristic,
                               call_count_pred=call_count_pred)
-        log.inlining('inlined %d callsites.'% (count,))
+        log.inlining('inlined %d callsites.' % (count,))
         for graph in graphs:
             removenoops.remove_duplicate_casts(graph, translator)

File pypy/translator/backendopt/malloc.py

-from pypy.objspace.flow.model import Variable, Constant, Block, Link
-from pypy.objspace.flow.model import SpaceOperation
+from pypy.objspace.flow.model import Variable, Constant, SpaceOperation
 from pypy.tool.algo.unionfind import UnionFind
 from pypy.rpython.lltypesystem import lltype
 from pypy.rpython.ootypesystem import ootype
 from pypy.translator.backendopt import removenoops
 from pypy.translator.backendopt.support import log
 
+
 class LifeTime: