Armin Rigo avatar Armin Rigo committed 6a00154

Merge, last step: copy branch as head.

Comments (0)

Files changed (343)

+General
+=======
+
+* missing pieces currently borrowed from CPython: the bytecode
+  compiler, a number of C modules, and some types -- as printed
+  when running py.py:  "faking <type xyz>".
+
+* not all of CPython's exceptions use the same __init__!
+
+* refactor the cmdline-entrypoints to PyPy aka py.py main.py 
+  interactive.py and traceinteractive.py towards a unified 
+  cmdline tool (py.py) possibly including translator-related
+  things too. 
+
+* cleanup the contents of the tool directory 
+
+* an oldie: move interpreter/unittest_w.py somewhere more appropriate
+  and give it a better name.
+
+* (documentation) remove/retire all web-pages referencing e.g.
+  AnnSpace or other deprecated stuff
+
+* Review, enhance the new mixed-level module mechanism
+  (e.g. the module/builtin*.py files comprise the builtin module)
+  and try to apply the same technique for the application level 
+  type definitions (types.py). Think about a way to split up
+  especially app-level definitions of __builtin__ into multiple
+  files. (like allowing __builtin__ to be a directory with files
+  comprising the complete definition of the builtin module etc.pp) 
+
+* review whatever you like 
+
+StdObjSpace
+===========
+
+* find a way via hacking or elegance to run CPython's unit tests
+  against the StdObjSpace.
+
+* String formatting is agonizingly slow.
+
+* Provide an importer that can import packages. (we have a 
+  limited __import__ builtin defined)  <---- done now?
+
+  Consider PEP 302, new import hooks.
+  Try to write as much as possible in app-level.
+  How would PyPy import CPython extensions?
+
+* (documentation) generate a nice dot-graph from the structure of PyPy
+
+* port pypy's testing framework to py.test (probably a sprint topic, 
+  as some discussion how to do it is required) 
+
+* clear out and do a clean implementation of multimethod delegation.
+  The idea is to give 'kinds' to arguments according to their use,
+  e.g. 'numeric argument' or 'object whose identity is preserved'.
+  A 'kind' encapsulates a set of delegation functions. Armin has
+  already written documentation for the envisioned new multimethod 
+  implementation:
+
+  http://codespeak.net/pypy/index.cgi?doc/objspace/multimethod
+
+  (now irrelevant?  not sure... (nowadays, we have the descriptor 
+  mechanism implemented right before EuroPython 2004 for both the 
+  trivial and the stdobjspace))
+
+Translator
+==========
+
+* enhance the translator components to accept more of PyPy ...
+
+Tools
+=====
+
+* add web server thread (!) that allows inspection of e.g.
+  interpreter-level tracebacks (and stop clogging the user's terminal
+  with them).  --> there is some preliminary working code in
+  tool/tb_server
+
+* Interpreter level tracebacks are spectacular in their uselessness,
+  especially since the advent of descroperation.  It should be
+  possible to construct something like an app-level traceback even
+  when there's no OperationError.
+
+* improve traceobjectspace! currently it only catches 
+  calls from outside the space into the space but not
+  the ones where space operations involve calling more space 
+  operations (the latter are not traced)!  (fixed?)
+# empty

pypy/annotation/__init__.py

+#

pypy/annotation/binaryop.py

+"""
+Binary operations between SomeValues.
+"""
+
+from pypy.annotation.pairtype import pair, pairtype
+from pypy.annotation.model import SomeObject, SomeInteger, SomeBool
+from pypy.annotation.model import SomeString, SomeChar, SomeList, SomeDict
+from pypy.annotation.model import SomeTuple, SomeImpossibleValue
+from pypy.annotation.model import SomeInstance, SomeBuiltin, SomeIterator
+from pypy.annotation.model import SomePBC
+from pypy.annotation.model import unionof, set, setunion, missing_operation
+from pypy.annotation.factory import generalize
+from pypy.annotation.bookkeeper import getbookkeeper
+from pypy.annotation.classdef import isclassdef
+from pypy.objspace.flow.model import Constant
+
+# convenience only!
+def immutablevalue(x):
+    return getbookkeeper().immutablevalue(x)
+
+# XXX unify this with ObjSpace.MethodTable
+BINARY_OPERATIONS = set(['add', 'sub', 'mul', 'div', 'mod',
+                         'and_', 'or_', 'xor',
+                         'getitem', 'setitem',
+                         'inplace_add', 'inplace_sub',
+                         'lt', 'le', 'eq', 'ne', 'gt', 'ge', 'is_',
+                         'union'])
+
+for opname in BINARY_OPERATIONS:
+    missing_operation(pairtype(SomeObject, SomeObject), opname)
+
+#class __extend__(pairtype(SomeFunction, SomeObject)):
+#    def union((obj1, obj2)):
+#        raise TypeError, "generalizing not allowed: %r AND %r" % (obj1, obj2)
+#
+#class __extend__(pairtype(SomeObject, SomeFunction)):
+#    def union((obj1, obj2)):
+#        raise TypeError, "generalizing not allowed: %r AND %r" % (obj2, obj1)
+
+class __extend__(pairtype(SomeObject, SomeObject)):
+
+    def union((obj1, obj2)):
+        if obj1 == obj2:
+            return obj1
+        else:
+            #if isinstance(obj1, SomeFunction) or \
+            #   isinstance(obj2, SomeFunction): 
+            #   raise TypeError, ("generalizing not allowed:"
+            #                     "%r AND %r" % (obj1, obj2))
+            #    
+            result = SomeObject()
+            # try to preserve the origin of SomeObjects
+            if obj1 == result:
+                return obj1
+            elif obj2 == result:
+                return obj2
+            else:
+                return result
+
+    def inplace_add((obj1, obj2)):
+        return pair(obj1, obj2).add()   # default
+
+    def inplace_sub((obj1, obj2)):
+        return pair(obj1, obj2).sub()   # default
+
+    def lt((obj1, obj2)):
+        if obj1.is_constant() and obj2.is_constant():
+            return immutablevalue(obj1.const < obj2.const)
+        else:
+            return SomeBool()
+
+    def le((obj1, obj2)):
+        if obj1.is_constant() and obj2.is_constant():
+            return immutablevalue(obj1.const <= obj2.const)
+        else:
+            return SomeBool()
+
+    def eq((obj1, obj2)):
+        if obj1.is_constant() and obj2.is_constant():
+            return immutablevalue(obj1.const == obj2.const)
+        else:
+            return SomeBool()
+
+    def ne((obj1, obj2)):
+        if obj1.is_constant() and obj2.is_constant():
+            return immutablevalue(obj1.const != obj2.const)
+        else:
+            return SomeBool()
+
+    def gt((obj1, obj2)):
+        if obj1.is_constant() and obj2.is_constant():
+            return immutablevalue(obj1.const > obj2.const)
+        else:
+            return SomeBool()
+
+    def ge((obj1, obj2)):
+        if obj1.is_constant() and obj2.is_constant():
+            return immutablevalue(obj1.const >= obj2.const)
+        else:
+            return SomeBool()
+
+    def is_((obj1, obj2)):
+        # XXX assumption: for "X is Y" we for simplification 
+        #     assume that X is possibly variable and Y constant 
+        #     (and not the other way round) 
+        r = SomeBool()
+        if obj2.is_constant():
+            if obj1.is_constant(): 
+                r.const = obj1.const is obj2.const 
+        # XXX HACK HACK HACK
+        # XXX HACK HACK HACK
+        # XXX HACK HACK HACK
+        fn, block, i = getbookkeeper().position_key
+        annotator = getbookkeeper().annotator
+        op = block.operations[i]
+        assert op.opname == "is_" 
+        assert len(op.args) == 2
+        assert annotator.binding(op.args[0]) == obj1 
+        r.knowntypedata = (op.args[0], obj2)
+        return r
+
+class __extend__(pairtype(SomeInteger, SomeInteger)):
+    # unsignedness is considered a rare and contagious disease
+
+    def union((int1, int2)):
+        return SomeInteger(nonneg = int1.nonneg and int2.nonneg,
+                           unsigned = int1.unsigned or int2.unsigned)
+
+    add = mul = div = mod = or_ = xor = union
+
+    def sub((int1, int2)):
+        return SomeInteger(unsigned = int1.unsigned or int2.unsigned)
+
+    def and_((int1, int2)):
+        return SomeInteger(nonneg = int1.nonneg or int1.nonneg,
+                           unsigned = int1.unsigned or int2.unsigned)
+
+
+class __extend__(pairtype(SomeBool, SomeBool)):
+
+    def union((boo1, boo2)):
+        s = SomeBool() 
+        if getattr(boo1, 'const', -1) == getattr(boo2, 'const', -2): 
+            s.const = boo1.const 
+        if hasattr(boo1, 'knowntypedata') and \
+           hasattr(boo2, 'knowntypedata') and \
+           boo1.knowntypedata[0] == boo2.knowntypedata[0]: 
+            s.knowntypedata = (
+                boo1.knowntypedata[0], 
+                unionof(boo1.knowntypedata[1], boo2.knowntypedata[1]))
+        return s 
+
+class __extend__(pairtype(SomeString, SomeString)):
+
+    def union((str1, str2)):
+        return SomeString()
+
+    def add((str1, str2)):
+        return SomeString()
+
+
+class __extend__(pairtype(SomeString, SomeObject)):
+
+    def mod((str, args)):
+        return SomeString()
+
+
+class __extend__(pairtype(SomeList, SomeList)):
+
+    def union((lst1, lst2)):
+        return SomeList(setunion(lst1.factories, lst2.factories),
+                        s_item = unionof(lst1.s_item, lst2.s_item))
+
+    add = union
+
+
+class __extend__(pairtype(SomeList, SomeObject)):
+
+    def inplace_add((lst1, obj2)):
+        s_iter = obj2.iter()
+        pair(lst1, SomeInteger()).setitem(s_iter.next())
+        return lst1
+
+
+class __extend__(pairtype(SomeTuple, SomeTuple)):
+
+    def union((tup1, tup2)):
+        if len(tup1.items) != len(tup2.items):
+            return SomeObject()
+        else:
+            unions = [unionof(x,y) for x,y in zip(tup1.items, tup2.items)]
+            return SomeTuple(items = unions)
+
+    def add((tup1, tup2)):
+        return SomeTuple(items = tup1.items + tup2.items)
+
+
+class __extend__(pairtype(SomeDict, SomeDict)):
+
+    def union((dic1, dic2)):
+        return SomeDict(setunion(dic1.factories, dic2.factories),
+                        unionof(dic1.s_key, dic2.s_key),
+                        unionof(dic1.s_value, dic2.s_value))
+
+
+class __extend__(pairtype(SomeDict, SomeObject)):
+
+    def getitem((dic1, obj2)):
+        return dic1.s_value
+
+    def setitem((dic1, obj2), s_value):
+        generalize(dic1.factories, obj2, s_value)
+
+
+class __extend__(pairtype(SomeTuple, SomeInteger)):
+    
+    def getitem((tup1, int2)):
+        if int2.is_constant():
+            try:
+                return tup1.items[int2.const]
+            except IndexError:
+                return SomeImpossibleValue()
+        else:
+            return unionof(*tup1.items)
+
+
+class __extend__(pairtype(SomeList, SomeInteger)):
+    
+    def mul((lst1, int2)):
+        return lst1
+
+    def getitem((lst1, int2)):
+        return lst1.s_item
+
+    def setitem((lst1, int2), s_value):
+        generalize(lst1.factories, s_value)
+
+
+class __extend__(pairtype(SomeString, SomeInteger)):
+
+    def getitem((str1, int2)):
+        return SomeChar()
+
+
+class __extend__(pairtype(SomeInteger, SomeList)):
+    
+    def mul((int1, lst2)):
+        return lst2
+
+
+class __extend__(pairtype(SomeInstance, SomeInstance)):
+
+    def union((ins1, ins2)):
+        basedef = ins1.classdef.commonbase(ins2.classdef)
+        if basedef is None:
+            # print warning?
+            return SomeObject()
+        return SomeInstance(basedef)
+
+class __extend__(pairtype(SomeIterator, SomeIterator)):
+
+    def union((iter1, iter2)):
+        return SomeIterator(unionof(iter1.s_item, iter2.s_item))
+
+
+class __extend__(pairtype(SomeBuiltin, SomeBuiltin)):
+
+    def union((bltn1, bltn2)):
+        if bltn1.analyser != bltn2.analyser:
+            assert False, "merging incompatible builtins == BAD!"
+            return SomeObject()
+        else:
+            s_self = unionof(bltn1.s_self, bltn2.s_self)
+            return SomeBuiltin(bltn1.analyser, s_self)
+
+class __extend__(pairtype(SomePBC, SomePBC)):
+    def union((pbc1, pbc2)):
+        if len(pbc2.prebuiltinstances) > len(pbc1.prebuiltinstances):
+            pbc1, pbc2 = pbc2, pbc1
+        d = pbc1.prebuiltinstances.copy()
+        for x, classdef in pbc2.prebuiltinstances.items():
+            if x in d:
+                if bool(isclassdef(classdef)) ^ bool(isclassdef(d[x])):
+                    raise Exception(
+                        "union failed for %r with classdefs %r and %r" % 
+                        (x, classdef, d[x]))
+                if isclassdef(classdef):
+                    classdef = classdef.commonbase(d[x])
+            d[x] = classdef
+        return SomePBC(d)
+
+class __extend__(pairtype(SomeImpossibleValue, SomeObject)):
+    def union((imp1, obj2)):
+        return obj2
+
+class __extend__(pairtype(SomeObject, SomeImpossibleValue)):
+    def union((obj1, imp2)):
+        return obj1
+
+class __extend__(pairtype(SomeInstance, SomePBC)):
+    def union((ins, pbc)):
+        classdef = ins.classdef.superdef_containing(pbc.knowntype)
+        if classdef is None:
+            # print warning?
+            return SomeObject()
+        return SomeInstance(classdef)
+
+class __extend__(pairtype(SomePBC, SomeInstance)):
+    def union((pbc, ins)):
+        return pair(ins, pbc).union()

pypy/annotation/bookkeeper.py

+"""
+The Bookkeeper class.
+"""
+
+from types import FunctionType, ClassType, MethodType
+from types import BuiltinMethodType
+from pypy.annotation.model import *
+from pypy.annotation.classdef import ClassDef
+from pypy.interpreter.miscutils import getthreadlocals
+from pypy.tool.hack import func_with_new_name
+from pypy.interpreter.pycode import CO_VARARGS
+
+class Bookkeeper:
+    """The log of choices that have been made while analysing the operations.
+    It ensures that the same 'choice objects' will be returned if we ask
+    again during reflowing.  Like ExecutionContext, there is an implicit
+    Bookkeeper that can be obtained from a thread-local variable.
+
+    Currently used for factories and user-defined classes."""
+
+    def __init__(self, annotator):
+        self.annotator = annotator
+        self.creationpoints = {} # map position-in-a-block to its Factory
+        self.userclasses = {}    # map classes to ClassDefs
+        self.userclasseslist = []# userclasses.keys() in creation order
+        self.cachespecializations = {}
+        self.pbccache = {}
+        # import ordering hack
+        global BUILTIN_ANALYZERS
+        from pypy.annotation.builtin import BUILTIN_ANALYZERS
+
+    def enter(self, position_key):
+        """Start of an operation.
+        The operation is uniquely identified by the given key."""
+        self.position_key = position_key
+        getthreadlocals().bookkeeper = self
+
+    def leave(self):
+        """End of an operation."""
+        del getthreadlocals().bookkeeper
+        del self.position_key
+
+    def is_in_an_operation(self):
+        return hasattr(self, 'position_key')
+
+    def getfactory(self, factorycls):
+        """Get the Factory associated with the current position,
+        or build it if it doesn't exist yet."""
+        try:
+            factory = self.creationpoints[self.position_key]
+        except KeyError:
+            factory = factorycls()
+            factory.bookkeeper = self
+            factory.position_key = self.position_key
+            self.creationpoints[self.position_key] = factory
+        assert isinstance(factory, factorycls)
+        return factory
+
+    def getclassdef(self, cls):
+        """Get the ClassDef associated with the given user cls."""
+        if cls is object:
+            return None
+        try:
+            return self.userclasses[cls]
+        except KeyError:
+            cdef = ClassDef(cls, self)
+            self.userclasses[cls] = cdef
+            self.userclasseslist.append(cdef)
+            return self.userclasses[cls]
+
+
+    def immutablevalue(self, x):
+        """The most precise SomeValue instance that contains the
+        immutable value x."""
+        tp = type(x)
+        if tp is bool:
+            result = SomeBool()
+        elif tp is int:
+            result = SomeInteger(nonneg = x>=0)
+        elif tp is str:
+            result = SomeString()
+        elif tp is tuple:
+            result = SomeTuple(items = [self.immutablevalue(e) for e in x])
+        elif tp is list:
+            items_s = [self.immutablevalue(e) for e in x]
+            result = SomeList({}, unionof(*items_s))
+        elif tp is dict:   # exactly a dict
+            keys_s   = [self.immutablevalue(e) for e in x.keys()]
+            values_s = [self.immutablevalue(e) for e in x.values()]
+            result = SomeDict({}, unionof(*keys_s), unionof(*values_s))
+        elif ishashable(x) and x in BUILTIN_ANALYZERS:
+            result = SomeBuiltin(BUILTIN_ANALYZERS[x])
+        elif callable(x) or isinstance(x, staticmethod): # XXX
+            # maybe 'x' is a method bound to a not-yet-frozen cache?
+            # fun fun fun.
+            if (hasattr(x, 'im_self') and isinstance(x.im_self, Cache)
+                and not x.im_self.frozen):
+                x.im_self.freeze()
+            if hasattr(x, '__self__') and x.__self__ is not None:
+                s_self = self.immutablevalue(x.__self__)
+                try:
+                    result = s_self.find_method(x.__name__)
+                except AttributeError:
+                    result = SomeObject()
+            else:
+                return self.getpbc(x)
+        elif hasattr(x, '__class__') \
+                 and x.__class__.__module__ != '__builtin__':
+            if isinstance(x, Cache) and not x.frozen:
+                x.freeze()
+            return self.getpbc(x)
+        elif x is None:
+            return self.getpbc(None)
+        else:
+            result = SomeObject()
+        result.const = x
+        return result
+
+    def getpbc(self, x):
+        try:
+            # this is not just an optimization, but needed to avoid
+            # infinitely repeated calls to add_source_for_attribute()
+            return self.pbccache[x]
+        except KeyError:
+            result = SomePBC({x: True}) # pre-built inst
+            clsdef = self.getclassdef(new_or_old_class(x))
+            for attr in getattr(x, '__dict__', {}):
+                clsdef.add_source_for_attribute(attr, x)
+            self.pbccache[x] = result
+            return result
+
+    def valueoftype(self, t):
+        """The most precise SomeValue instance that contains all
+        objects of type t."""
+        if t is bool:
+            return SomeBool()
+        elif t is int:
+            return SomeInteger()
+        elif t is str:
+            return SomeString()
+        elif t is list:
+            return SomeList(factories={})
+        # can't do dict, tuple
+        elif isinstance(t, (type, ClassType)) and \
+                 t.__module__ != '__builtin__':
+            classdef = self.getclassdef(t)
+            if self.is_in_an_operation():
+                # woha! instantiating a "mutable" SomeXxx like
+                # SomeInstance is always dangerous, because we need to
+                # allow reflowing from the current operation if/when
+                # the classdef later changes.
+                classdef.instantiation_locations[self.position_key] = True
+            return SomeInstance(classdef)
+        else:
+            o = SomeObject()
+            o.knowntype = t
+            return o
+
+    def pycall(self, func, args):
+        if func is None:   # consider None as a NULL function pointer
+            return SomeImpossibleValue()
+        if isinstance(func, (type, ClassType)) and \
+            func.__module__ != '__builtin__':
+            cls = func
+            x = getattr(cls, "_specialize_", False)
+            if x:
+                if x == "location":
+                    cls = self.specialize_by_key(cls, self.position_key)
+                else:
+                    raise Exception, \
+                          "unsupported specialization type '%s'"%(x,)
+
+            classdef = self.getclassdef(cls)
+            classdef.instantiation_locations[self.position_key] = True 
+            s_instance = SomeInstance(classdef)
+            # flow into __init__() if the class has got one
+            init = getattr(cls, '__init__', None)
+            if init is not None and init != object.__init__:
+                # don't record the access of __init__ on the classdef
+                # because it is not a dynamic attribute look-up, but
+                # merely a static function call
+                if hasattr(init, 'im_func'):
+                    init = init.im_func
+                else:
+                    assert isinstance(init, BuiltinMethodType)
+                s_init = self.immutablevalue(init)
+                s_init.call(args.prepend(s_instance))
+            else:
+                try:
+                    args.fixedunpack(0)
+                except ValueError:
+                    raise Exception, "no __init__ found in %r" % (cls,)
+            return s_instance
+        if hasattr(func, '__call__') and \
+           isinstance(func.__call__, MethodType):
+            func = func.__call__
+        if hasattr(func, 'im_func'):
+            if func.im_self is not None:
+                s_self = self.immutablevalue(func.im_self)
+                args = args.prepend(s_self)
+            # for debugging only, but useful to keep anyway:
+            try:
+                func.im_func.class_ = func.im_class
+            except AttributeError:
+                # probably a builtin function, we don't care to preserve
+                # class information then
+                pass
+            func = func.im_func
+        assert isinstance(func, FunctionType), "expected function, got %r"%func
+        # do we need to specialize this function in several versions?
+        x = getattr(func, '_specialize_', False)
+        #if not x: 
+        #    x = 'argtypes'
+        if x:
+            if x == 'argtypes':
+                key = short_type_name(args)
+                func = self.specialize_by_key(func, key,
+                                              func.__name__+'__'+key)
+            elif x == "location":
+                # fully specialize: create one version per call position
+                func = self.specialize_by_key(func, self.position_key)
+            else:
+                raise Exception, "unsupported specialization type '%s'"%(x,)
+
+        elif func.func_code.co_flags & CO_VARARGS:
+            # calls to *arg functions: create one version per number of args
+            assert not args.kwds_w, (
+                "keyword forbidden in calls to *arg functions")
+            nbargs = len(args.arguments_w)
+            if args.w_stararg is not None:
+                s_len = args.w_stararg.len()
+                assert s_len.is_constant(), "calls require known number of args"
+                nbargs += s_len.const
+            func = self.specialize_by_key(func, nbargs,
+                                          name='%s__%d' % (func.func_name,
+                                                           nbargs))
+        return self.annotator.recursivecall(func, self.position_key, args)
+
+    def specialize_by_key(self, thing, key, name=None):
+        key = thing, key
+        try:
+            thing = self.cachespecializations[key]
+        except KeyError:
+            if isinstance(thing, FunctionType):
+                # XXX XXX XXX HAAAAAAAAAAAACK
+                self.annotator.translator.getflowgraph(thing)
+                thing = func_with_new_name(thing, name or thing.func_name)
+            elif isinstance(thing, (type, ClassType)):
+                assert not "not working yet"
+                thing = type(thing)(name or thing.__name__, (thing,))
+            else:
+                raise Exception, "specializing %r?? why??"%thing
+            self.cachespecializations[key] = thing
+        return thing
+        
+
+def getbookkeeper():
+    """Get the current Bookkeeper.
+    Only works during the analysis of an operation."""
+    return getthreadlocals().bookkeeper
+
+def ishashable(x):
+    try:
+        hash(x)
+    except TypeError:
+        return False
+    else:
+        return True
+
+def short_type_name(args):
+    l = []
+    shape, args_w = args.flatten()
+    for x in args_w:
+        if isinstance(x, SomeInstance) and hasattr(x, 'knowntype'):
+            name = "SI_" + x.knowntype.__name__
+        else:
+            name = x.__class__.__name__
+        l.append(name)
+    return "__".join(l)

pypy/annotation/builtin.py

+"""
+Built-in functions.
+"""
+
+import types
+from pypy.annotation.model import SomeInteger, SomeObject, SomeChar, SomeBool
+from pypy.annotation.model import SomeList, SomeString, SomeTuple
+from pypy.annotation.bookkeeper import getbookkeeper
+from pypy.annotation.factory import ListFactory
+from pypy.objspace.flow.model import Constant
+import pypy.objspace.std.restricted_int
+
+# convenience only!
+def immutablevalue(x):
+    return getbookkeeper().immutablevalue(x)
+
+def builtin_len(s_obj):
+    return s_obj.len()
+
+def builtin_range(*args):
+    factory = getbookkeeper().getfactory(ListFactory)
+    factory.generalize(SomeInteger())  # XXX nonneg=...
+    return factory.create()
+
+def builtin_pow(s_base, s_exponent, *args):
+    if s_base.knowntype is s_exponent.knowntype is int:
+        return SomeInteger()
+    else:
+        return SomeObject()
+
+def builtin_int(s_obj):     # we can consider 'int' as a function
+    return SomeInteger()
+
+def restricted_uint(s_obj):    # for r_uint
+    return SomeInteger(nonneg=True, unsigned=True)
+
+def builtin_chr(s_int):
+    return SomeChar()
+
+def builtin_unicode(s_obj): 
+    return SomeString() 
+
+def builtin_float(s_obj): 
+    return SomeObject() 
+
+def builtin_long(s_str): 
+    return SomeObject() 
+
+def our_issubclass(cls1, cls2):
+    """ we're going to try to be less silly in the face of old-style classes"""
+    return cls2 is object or issubclass(cls1, cls2)
+
+def builtin_isinstance(s_obj, s_type):
+    s = SomeBool() 
+    if s_type.is_constant():
+        typ = s_type.const
+        # XXX bit of a hack:
+        if issubclass(typ, (int, long)):
+            typ = int
+        if s_obj.is_constant():
+            s.const = isinstance(s_obj.const, typ)
+        elif our_issubclass(s_obj.knowntype, typ):
+            s.const = True 
+        elif not our_issubclass(typ, s_obj.knowntype): 
+            s.const = False 
+        # XXX HACK HACK HACK
+        # XXX HACK HACK HACK
+        # XXX HACK HACK HACK
+        bk = getbookkeeper()
+        fn, block, i = bk.position_key
+        annotator = bk.annotator
+        op = block.operations[i]
+        assert op.opname == "simple_call" 
+        assert len(op.args) == 3
+        assert op.args[0] == Constant(isinstance)
+        assert annotator.binding(op.args[1]) == s_obj
+        s.knowntypedata = (op.args[1], bk.valueoftype(typ))
+    return s 
+
+def builtin_issubclass(s_cls1, s_cls2):
+    if s_cls1.is_constant() and s_cls2.is_constant():
+        return immutablevalue(issubclass(s_cls1.const, s_cls2.const))
+    else:
+        return SomeBool()
+
+def builtin_getattr(s_obj, s_attr, s_default=None):
+    if not s_attr.is_constant() or not isinstance(s_attr.const, str):
+        print "UN-RPYTHONIC-WARNING", \
+              'getattr(%r, %r) is not RPythonic enough' % (s_obj, s_attr)
+        return SomeObject()
+    return s_obj.getattr(s_attr)
+
+def builtin_hasattr(s_obj, s_attr):
+    if not s_attr.is_constant() or not isinstance(s_attr.const, str):
+        print "UN-RPYTHONIC-WARNING", \
+              'hasattr(%r, %r) is not RPythonic enough' % (s_obj, s_attr)
+    return SomeBool()
+
+def builtin_hash(s_obj):
+    return SomeInteger()
+
+def builtin_callable(s_obj):
+    return SomeBool()
+
+def builtin_tuple(s_iterable):
+    if isinstance(s_iterable, SomeTuple):
+        return s_iterable
+    return SomeObject()
+
+def builtin_type(s_obj, *moreargs):
+    if moreargs:
+        raise Exception, 'type() called with more than one argument'
+    if s_obj.is_constant():
+        return immutablevalue(type(s_obj.const))
+    return SomeObject()
+
+def builtin_str(s_obj):
+    return SomeString()
+
+def builtin_list(s_iterable):
+    factory = getbookkeeper().getfactory(ListFactory)
+    s_iter = s_iterable.iter()
+    factory.generalize(s_iter.next())
+    return factory.create()
+
+def builtin_apply(*stuff):
+    print "XXX ignoring apply%r" % (stuff,)
+    return SomeObject()
+
+def builtin_compile(*stuff):
+    s = SomeObject()
+    s.knowntype = types.CodeType
+    return s
+
+def exception_init(s_self, *args):
+    s_self.setattr(immutablevalue('args'), SomeTuple(args))
+
+# collect all functions
+import __builtin__
+BUILTIN_ANALYZERS = {}
+for name, value in globals().items():
+    if name.startswith('builtin_'):
+        original = getattr(__builtin__, name[8:])
+        BUILTIN_ANALYZERS[original] = value
+
+BUILTIN_ANALYZERS[pypy.objspace.std.restricted_int.r_int] = builtin_int
+BUILTIN_ANALYZERS[pypy.objspace.std.restricted_int.r_uint] = restricted_uint
+BUILTIN_ANALYZERS[Exception.__init__.im_func] = exception_init
+

pypy/annotation/classdef.py

+"""
+Type inference for user-defined classes.
+"""
+
+from __future__ import generators
+from types import FunctionType
+from pypy.annotation.model import SomeImpossibleValue, unionof
+
+
+class Attribute:
+    # readonly-ness
+    # SomeThing-ness
+    # more potential sources (pbcs or classes) of information
+
+    def __init__(self, name, bookkeeper):
+        self.name = name
+        self.bookkeeper = bookkeeper
+        self.sources = {} # source -> None or ClassDef
+        # XXX a SomeImpossibleValue() constant?  later!!
+        self.s_value = SomeImpossibleValue()
+        self.readonly = True
+
+    def getvalue(self):
+        while self.sources:
+            source, classdef = self.sources.popitem()
+            s_value = self.bookkeeper.immutablevalue(
+                source.__dict__[self.name])
+            if classdef:
+                s_value = s_value.bindcallables(classdef)
+            self.s_value = unionof(self.s_value, s_value)
+        return self.s_value
+
+    def merge(self, other):
+        assert self.name == other.name
+        self.sources.update(other.sources)
+        self.s_value = unionof(self.s_value, other.s_value)
+        self.readonly = self.readonly and other.readonly
+
+
+class ClassDef:
+    "Wraps a user class."
+
+    def __init__(self, cls, bookkeeper):
+        self.bookkeeper = bookkeeper
+        self.attrs = {}          # {name: Attribute}
+        self.revision = 0        # which increases the revision number
+        self.instantiation_locations = {}
+        self.cls = cls
+        self.subdefs = {}
+        assert (len(cls.__bases__) <= 1 or
+                cls.__bases__[1:] == (object,),   # for baseobjspace.Wrappable
+                "single inheritance only right now: %r" % (cls,))
+        if cls.__bases__:
+            base = cls.__bases__[0]
+        else:
+            base = object
+        self.basedef = bookkeeper.getclassdef(base)
+        if self.basedef:
+            self.basedef.subdefs[cls] = self
+
+        # collect the (supposed constant) class attributes
+        for name, value in cls.__dict__.items():
+            # ignore some special attributes
+            if name.startswith('_') and not isinstance(value, FunctionType):
+                continue
+            if isinstance(value, FunctionType):
+                value.class_ = cls # remember that this is really a method
+            self.add_source_for_attribute(name, cls, self)
+
+    def add_source_for_attribute(self, attr, source, clsdef=None):
+        self.find_attribute(attr).sources[source] = clsdef
+
+    def locate_attribute(self, attr):
+        for cdef in self.getmro():
+            if attr in cdef.attrs:
+                return cdef
+        self.generalize_attr(attr)
+        return self
+
+    def find_attribute(self, attr):
+        return self.locate_attribute(attr).attrs[attr]
+    
+    def __repr__(self):
+        return "<ClassDef '%s.%s'>" % (self.cls.__module__, self.cls.__name__)
+
+    def commonbase(self, other):
+        while other is not None and not issubclass(self.cls, other.cls):
+            other = other.basedef
+        return other
+
+    def superdef_containing(self, cls):
+        clsdef = self
+        while clsdef is not None and not issubclass(cls, clsdef.cls):
+            clsdef = clsdef.basedef
+        return clsdef
+
+    def getmro(self):
+        while self is not None:
+            yield self
+            self = self.basedef
+
+    def getallsubdefs(self):
+        pending = [self]
+        seen = {}
+        for clsdef in pending:
+            yield clsdef
+            for sub in clsdef.subdefs.values():
+                if sub not in seen:
+                    pending.append(sub)
+                    seen[sub] = True
+
+    def getallinstantiations(self):
+        locations = {}
+        for clsdef in self.getallsubdefs():
+            locations.update(clsdef.instantiation_locations)
+        return locations
+
+    def _generalize_attr(self, attr, s_value):
+        # first remove the attribute from subclasses -- including us!
+        subclass_attrs = []
+        for subdef in self.getallsubdefs():
+            if attr in subdef.attrs:
+                subclass_attrs.append(subdef.attrs[attr])
+                del subdef.attrs[attr]
+            # bump the revision number of this class and all subclasses
+            subdef.revision += 1
+
+        # do the generalization
+        newattr = Attribute(attr, self.bookkeeper)
+        if s_value:
+            newattr.s_value = s_value
+            
+        for subattr in subclass_attrs:
+            newattr.merge(subattr)
+        self.attrs[attr] = newattr
+
+        # reflow from all factories
+        for position in self.getallinstantiations():
+            self.bookkeeper.annotator.reflowfromposition(position)
+
+    def generalize_attr(self, attr, s_value=None):
+        # if the attribute exists in a superclass, generalize there.
+        for clsdef in self.getmro():
+            if attr in clsdef.attrs:
+                clsdef._generalize_attr(attr, s_value)
+        else:
+            self._generalize_attr(attr, s_value)
+
+    def about_attribute(self, name):
+        for cdef in self.getmro():
+            if name in cdef.attrs:
+                s_result = cdef.attrs[name].s_value
+                if s_result != SomeImpossibleValue():
+                    return s_result
+                else:
+                    return None
+        return None
+
+
+def isclassdef(x):
+    return isinstance(x, ClassDef)

pypy/annotation/factory.py

+"""
+Mutable Objects Factories.
+
+A factory is associated to an SpaceOperation in the source that creates a
+built-in mutable object: currently 'newlist' and 'newdict'.
+The factory remembers how general an object it has to create here.
+"""
+
+from pypy.annotation.model import SomeList, SomeDict
+from pypy.annotation.model import SomeImpossibleValue, unionof
+from pypy.annotation.bookkeeper import getbookkeeper
+
+
+class BlockedInference(Exception):
+    """This exception signals the type inference engine that the situation
+    is currently blocked, and that it should try to progress elsewhere."""
+
+    def __init__(self):
+        try:
+            self.break_at = getbookkeeper().position_key
+        except AttributeError:
+            self.break_at = None
+
+    def __repr__(self):
+        return "<BlockedInference break_at %r>" %(self.break_at,)
+    __str__ = __repr__
+
+
+class ListFactory:
+    s_item = SomeImpossibleValue()
+
+    def __repr__(self):
+        return '%s(s_item=%r)' % (self.__class__.__name__, self.s_item)
+
+    def create(self):
+        return SomeList(factories = {self: True}, s_item = self.s_item)
+
+    def generalize(self, s_new_item):
+        if not self.s_item.contains(s_new_item):
+            self.s_item = unionof(self.s_item, s_new_item)
+            return True
+        else:
+            return False
+
+
+class DictFactory:
+    s_key   = SomeImpossibleValue()
+    s_value = SomeImpossibleValue()
+
+    def __repr__(self):
+        return '%s(s_key=%r, s_value=%r)' % (self.__class__.__name__,
+                                             self.s_key, self.s_value)
+
+    def create(self):
+        return SomeDict(factories = {self: True},
+                        s_key     = self.s_key,
+                        s_value   = self.s_value)
+
+    def generalize(self, s_new_key, s_new_value):
+        if (self.s_key.contains(s_new_key) and
+            self.s_value.contains(s_new_value)):
+            return False
+        self.s_key   = unionof(self.s_key,   s_new_key)
+        self.s_value = unionof(self.s_value, s_new_value)
+        return True
+
+
+def generalize(factories, *args):
+    """Signals all the factories in the given set to generalize themselves.
+    The args must match the signature of the generalize() method of the
+    particular factories (which should all be of the same class).
+    """
+    modified = [factory for factory in factories if factory.generalize(*args)]
+    if modified:
+        for factory in modified:
+            factory.bookkeeper.annotator.reflowfromposition(factory.position_key)
+        raise BlockedInference   # reflow now

pypy/annotation/model.py

+"""
+This file defines the 'subset' SomeValue classes.
+
+An instance of a SomeValue class stands for a Python object that has some
+known properties, for example that is known to be a list of non-negative
+integers.  Each instance can be considered as an object that is only
+'partially defined'.  Another point of view is that each instance is a
+generic element in some specific subset of the set of all objects.
+
+"""
+
+# Old terminology still in use here and there:
+#    SomeValue means one of the SomeXxx classes in this file.
+#    Cell is an instance of one of these classes.
+#
+# Think about cells as potato-shaped circles in a diagram:
+#    ______________________________________________________
+#   / SomeObject()                                         \
+#  /   ___________________________          ______________  \
+#  |  / SomeInteger(nonneg=False) \____    / SomeString() \  \
+#  | /     __________________________  \   |              |  |
+#  | |    / SomeInteger(nonneg=True) \ |   |      "hello" |  |
+#  | |    |   0    42       _________/ |   \______________/  |
+#  | \ -3 \________________/           /                     |
+#  \  \                     -5   _____/                      /
+#   \  \________________________/              3.1416       /
+#    \_____________________________________________________/
+#
+
+
+from types import ClassType, BuiltinFunctionType, FunctionType, MethodType
+from types import InstanceType
+import pypy
+from pypy.annotation.pairtype import pair, extendabletype
+from pypy.objspace.flow.model import Constant
+from pypy.tool.cache import Cache 
+import inspect
+
+
+DEBUG = True    # set to False to disable recording of debugging information
+
+
+class SomeObject:
+    """The set of all objects.  Each instance stands
+    for an arbitrary object about which nothing is known."""
+    __metaclass__ = extendabletype
+    knowntype = object
+    def __eq__(self, other):
+        return (self.__class__ is other.__class__ and
+                self.__dict__  == other.__dict__)
+    def __ne__(self, other):
+        return not (self == other)
+    def __repr__(self):
+        items = self.__dict__.items()
+        items.sort()
+        args = []
+        for k, v in items:
+            m = getattr(self, 'fmt_' + k, repr)
+            r = m(v)
+            if r is not None:
+                args.append('%s=%s'%(k, r))
+        kwds = ', '.join(args)
+        return '%s(%s)' % (self.__class__.__name__, kwds)
+
+    def fmt_knowntype(self, t):
+        return t.__name__
+    
+    def contains(self, other):
+        return self == other or pair(self, other).union() == self
+    def is_constant(self):
+        return hasattr(self, 'const')
+
+    # for debugging, record where each instance comes from
+    # this is disabled if DEBUG is set to False
+    _coming_from = {}
+    def __new__(cls, *args, **kw):
+        self = super(SomeObject, cls).__new__(cls, *args, **kw)
+        if DEBUG:
+            try:
+                bookkeeper = pypy.annotation.bookkeeper.getbookkeeper()
+                position_key = bookkeeper.position_key
+            except AttributeError:
+                pass
+            else:
+                SomeObject._coming_from[id(self)] = position_key, None
+        return self
+    def origin(self):
+        return SomeObject._coming_from.get(id(self), (None, None))[0]
+    origin = property(origin)
+    def caused_by_merge(self):
+        return SomeObject._coming_from.get(id(self), (None, None))[1]
+    def set_caused_by_merge(self, nvalue):
+        SomeObject._coming_from[id(self)] = self.origin, nvalue
+    caused_by_merge = property(caused_by_merge, set_caused_by_merge)
+    del set_caused_by_merge
+
+
+class SomeInteger(SomeObject):
+    "Stands for an object which is known to be an integer."
+    knowntype = int
+    def __init__(self, nonneg=False, unsigned=False):
+        self.nonneg = nonneg
+        self.unsigned = unsigned  # pypy.objspace.std.restricted_int.r_uint
+
+
+class SomeBool(SomeInteger):
+    "Stands for true or false."
+    knowntype = bool
+    nonneg = True
+    unsigned = False
+    def __init__(self):
+        pass
+
+
+class SomeString(SomeObject):
+    "Stands for an object which is known to be a string."
+    knowntype = str
+
+
+class SomeChar(SomeString):
+    "Stands for an object known to be a string of length 1."
+
+
+class SomeList(SomeObject):
+    "Stands for a homogenous list of any length."
+    knowntype = list
+    def __init__(self, factories, s_item=SomeObject()):
+        self.factories = factories
+        self.s_item = s_item     # general enough for any element
+
+
+class SomeTuple(SomeObject):
+    "Stands for a tuple of known length."
+    knowntype = tuple
+    def __init__(self, items):
+        self.items = tuple(items)   # tuple of s_xxx elements
+        for i in items:
+            if not i.is_constant():
+                break
+        else:
+            self.const = tuple([i.const for i in items])
+
+
+class SomeDict(SomeObject):
+    "Stands for a dict."
+    knowntype = dict
+    def __init__(self, factories, s_key, s_value):
+        self.factories = factories
+        self.s_key = s_key
+        self.s_value = s_value
+
+
+class SomeIterator(SomeObject):
+    "Stands for an iterator returning objects of a known type."
+    knowntype = type(iter([]))  # arbitrarily chose seqiter as the type
+    def __init__(self, s_item=SomeObject()):
+        self.s_item = s_item
+
+
+class SomeInstance(SomeObject):
+    "Stands for an instance of a (user-defined) class."
+    def __init__(self, classdef):
+        self.classdef = classdef
+        self.knowntype = classdef.cls
+        self.revision = classdef.revision
+    def fmt_knowntype(self, kt):
+        return None
+    def fmt_classdef(self, cd):
+        return cd.cls.__name__
+
+def new_or_old_class(c):
+    if hasattr(c, '__class__'):
+        return c.__class__
+    else:
+        return type(c)
+
+class SomePBC(SomeObject):
+    """Stands for a global user instance, built prior to the analysis,
+    or a set of such instances."""
+    def __init__(self, prebuiltinstances):
+        # prebuiltinstances is a dictionary containing concrete python
+        # objects as keys.
+        # if the key is a function, the value can be a classdef to
+        # indicate that it is really a method.
+        prebuiltinstances = prebuiltinstances.copy()
+        self.prebuiltinstances = prebuiltinstances
+        self.simplify()
+        self.knowntype = reduce(commonbase,
+                                [new_or_old_class(x) for x in prebuiltinstances])
+        if prebuiltinstances.values() == [True]:
+            # hack for the convenience of direct callers to SomePBC():
+            # only if there is a single object in prebuiltinstances and
+            # it doesn't have an associated ClassDef
+            self.const, = prebuiltinstances
+    def simplify(self):
+        # We check that the dictionary does not contain at the same time
+        # a function bound to a classdef, and constant bound method objects
+        # on that class.
+        for x, ignored in self.prebuiltinstances.items():
+            if isinstance(x, MethodType) and x.im_func in self.prebuiltinstances:
+                classdef = self.prebuiltinstances[x.im_func]
+                if isinstance(x.im_self, classdef.cls):
+                    del self.prebuiltinstances[x]
+
+    def fmt_prebuiltinstances(self, pbis):
+        if hasattr(self, 'const'):
+            return None
+        else:
+            return '{...%s...}'%(len(pbis),)
+
+    def fmt_knowntype(self, kt):
+        if self.is_constant():
+            return None
+        else:
+            return kt.__name__
+
+class SomeBuiltin(SomeObject):
+    "Stands for a built-in function or method with special-cased analysis."
+    knowntype = BuiltinFunctionType  # == BuiltinMethodType
+    def __init__(self, analyser, s_self=None):
+        self.analyser = analyser
+        self.s_self = s_self
+
+
+class SomeImpossibleValue(SomeObject):
+    """The empty set.  Instances are placeholders for objects that
+    will never show up at run-time, e.g. elements of an empty list."""
+
+
+def unionof(*somevalues):
+    "The most precise SomeValue instance that contains all the values."
+    s1 = SomeImpossibleValue()
+    for s2 in somevalues:
+        if s1 != s2:
+            s1 = pair(s1, s2).union()
+    if DEBUG and s1.caused_by_merge is None and len(somevalues) > 1:
+        s1.caused_by_merge = somevalues
+    return s1
+
+# ____________________________________________________________
+# internal
+
+def setunion(d1, d2):
+    "Union of two sets represented as dictionaries."
+    d = d1.copy()
+    d.update(d2)
+    return d
+
+def set(it):
+    "Turn an iterable into a set."
+    d = {}
+    for x in it:
+        d[x] = True
+    return d
+
+def commonbase(cls1, cls2):   # XXX single inheritance only  XXX hum
+    l1 = inspect.getmro(cls1)
+    l2 = inspect.getmro(cls2) 
+    if l1[-1] != object: 
+        l1 = l1 + (object,) 
+    if l2[-1] != object: 
+        l2 = l2 + (object,) 
+    for x in l1: 
+        if x in l2: 
+            return x 
+    assert 0, "couldn't get to commonbase of %r and %r" % (cls1, cls2)
+
+def missing_operation(cls, name):
+    def default_op(*args):
+        #print '* warning, no type available for %s(%s)' % (
+        #    name, ', '.join([repr(a) for a in args]))
+        return SomeObject()
+    setattr(cls, name, default_op)
+
+# 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

pypy/annotation/pairtype.py

+"""
+XXX A docstring should go here.
+"""
+
+class extendabletype(type):
+    """A type with a syntax trick: 'class __extend__(t)' actually extends
+    the definition of 't' instead of creating a new subclass."""
+    def __new__(cls, name, bases, dict):
+        if name == '__extend__':
+            cls = bases[0]   # override data into the existing base
+            for key, value in dict.items():
+                setattr(cls, key, value)
+            return None
+        else:
+            return super(extendabletype, cls).__new__(cls, name, bases, dict)
+
+
+def pair(a, b):
+    """Return a pair object."""
+    tp = pairtype(a.__class__, b.__class__)
+    return tp((a, b))   # tp is a subclass of tuple
+
+pairtypecache = {}
+
+def pairtype(cls1, cls2):
+    """type(pair(a,b)) is pairtype(a.__class__, b.__class__)."""
+    try:
+        pair = pairtypecache[cls1, cls2]
+    except KeyError:
+        name = 'pairtype(%s, %s)' % (cls1.__name__, cls2.__name__)
+        bases1 = [pairtype(base1, cls2) for base1 in cls1.__bases__]
+        bases2 = [pairtype(cls1, base2) for base2 in cls2.__bases__]
+        bases = tuple(bases1 + bases2) or (tuple,)  # 'tuple': ultimate base
+        pair = pairtypecache[cls1, cls2] = extendabletype(name, bases, {})
+    return pair
Add a comment to this file

pypy/annotation/test/__init__.py

Empty file added.

pypy/annotation/test/autopath.py

+"""
+self cloning, automatic path configuration 
+
+copy this into any subdirectory of pypy from which scripts need 
+to be run, typically all of the test subdirs. 
+The idea is that any such script simply issues
+
+    import autopath
+
+and this will make sure that the parent directory containing "pypy"
+is in sys.path. 
+
+If you modify the master "autopath.py" version (in pypy/tool/autopath.py) 
+you can directly run it which will copy itself on all autopath.py files
+it finds under the pypy root directory. 
+
+This module always provides these attributes:
+
+    pypydir    pypy root directory path 
+    this_dir   directory where this autopath.py resides 
+
+"""
+
+
+def __dirinfo(part):
+    """ return (partdir, this_dir) and insert parent of partdir
+    into sys.path.  If the parent directories don't have the part
+    an EnvironmentError is raised."""
+
+    import sys, os
+    try:
+        head = this_dir = os.path.realpath(os.path.dirname(__file__))
+    except NameError:
+        head = this_dir = os.path.realpath(os.path.dirname(sys.argv[0]))
+
+    while head:
+        partdir = head
+        head, tail = os.path.split(head)
+        if tail == part:
+            break
+    else:
+        raise EnvironmentError, "'%s' missing in '%r'" % (partdir, this_dir)
+    
+    checkpaths = sys.path[:]
+    pypy_root = os.path.join(head, '')
+    
+    while checkpaths:
+        orig = checkpaths.pop()
+        if os.path.join(os.path.realpath(orig), '').startswith(pypy_root):
+            sys.path.remove(orig)
+    sys.path.insert(0, head)
+
+    munged = {}
+    for name, mod in sys.modules.items():
+        fn = getattr(mod, '__file__', None)
+        if '.' in name or not isinstance(fn, str):
+            continue
+        newname = os.path.splitext(os.path.basename(fn))[0]
+        if not newname.startswith(part + '.'):
+            continue
+        path = os.path.join(os.path.dirname(os.path.realpath(fn)), '')
+        if path.startswith(pypy_root) and newname != part:
+            modpaths = os.path.normpath(path[len(pypy_root):]).split(os.sep)
+            if newname != '__init__':
+                modpaths.append(newname)
+            modpath = '.'.join(modpaths)
+            if modpath not in sys.modules:
+                munged[modpath] = mod
+
+    for name, mod in munged.iteritems():
+        if name not in sys.modules:
+            sys.modules[name] = mod
+        if '.' in name:
+            prename = name[:name.rfind('.')]
+            postname = name[len(prename)+1:]
+            if prename not in sys.modules:
+                __import__(prename)
+                if not hasattr(sys.modules[prename], postname):
+                    setattr(sys.modules[prename], postname, mod)
+
+    return partdir, this_dir
+
+def __clone():
+    """ clone master version of autopath.py into all subdirs """
+    from os.path import join, walk
+    if not this_dir.endswith(join('pypy','tool')):
+        raise EnvironmentError("can only clone master version "
+                               "'%s'" % join(pypydir, 'tool',_myname))
+
+
+    def sync_walker(arg, dirname, fnames):
+        if _myname in fnames:
+            fn = join(dirname, _myname)
+            f = open(fn, 'rwb+')
+            try:
+                if f.read() == arg:
+                    print "checkok", fn
+                else:
+                    print "syncing", fn
+                    f = open(fn, 'w')
+                    f.write(arg)
+            finally:
+                f.close()
+    s = open(join(pypydir, 'tool', _myname), 'rb').read()
+    walk(pypydir, sync_walker, s)
+
+_myname = 'autopath.py'
+
+# set guaranteed attributes
+
+pypydir, this_dir = __dirinfo('pypy')
+
+if __name__ == '__main__':
+    __clone()

pypy/annotation/test/test_model.py

+
+import autopath
+from pypy.annotation.model import *
+
+
+s1 = SomeObject()
+s2 = SomeInteger(nonneg=True)
+s3 = SomeInteger(nonneg=False)
+s4 = SomeList({}, SomeTuple([SomeInteger(nonneg=True), SomeString()]))
+s5 = SomeList({}, SomeTuple([SomeInteger(nonneg=False), SomeString()]))
+s6 = SomeImpossibleValue()
+slist = [s1,s2,s3,s4,s5,s6]
+
+def test_equality():
+    assert s1 != s2 != s3 != s4 != s5 != s6
+    assert s1 == SomeObject()
+    assert s2 == SomeInteger(nonneg=True)
+    assert s3 == SomeInteger(nonneg=False)
+    assert s4 == SomeList({}, SomeTuple([SomeInteger(nonneg=True), SomeString()]))
+    assert s5 == SomeList({}, SomeTuple([SomeInteger(nonneg=False), SomeString()]))
+    assert s6 == SomeImpossibleValue()
+
+def test_contains():
+    assert ([(s,t) for s in slist for t in slist if s.contains(t)] ==
+            [(s1,s1), (s1,s2), (s1,s3), (s1,s4), (s1,s5), (s1,s6),
+                      (s2,s2),                            (s2,s6),
+                      (s3,s2), (s3,s3),                   (s3,s6),
+                                        (s4,s4),          (s4,s6),
+                                        (s5,s4), (s5,s5), (s5,s6),
+                                                          (s6,s6)])
+
+def test_union():
+    assert ([unionof(s,t) for s in slist for t in slist] ==
+            [s1, s1, s1, s1, s1, s1,
+             s1, s2, s3, s1, s1, s2,
+             s1, s3, s3, s1, s1, s3,
+             s1, s1, s1, s4, s5, s4,
+             s1, s1, s1, s5, s5, s5,
+             s1, s2, s3, s4, s5, s6])
+
+def test_commonbase_simple():
+    class A0: 
+        pass
+    class A1(A0): 
+        pass
+    class A2(A0): 
+        pass
+    class B1(object):
+        pass
+    class B2(object):
+        pass
+    class B3(object, A0):
+        pass
+    assert commonbase(A1,A2) is A0 
+    assert commonbase(A1,A0) is A0
+    assert commonbase(A1,A1) is A1
+    assert commonbase(A2,B2) is object 
+    assert commonbase(A2,B3) is A0 
+
+if __name__ == '__main__':
+    for name, value in globals().items():
+        if name.startswith('test_'):
+            value()

pypy/annotation/test/test_pairtype.py

+
+from pypy.annotation.pairtype import pairtype, pair
+
+def test_binop(): 
+    ### Binary operation example
+    class __extend__(pairtype(int, int)):
+        def add((x, y)):
+            return 'integer: %s+%s' % (x, y)
+        def sub((x, y)):
+            return 'integer: %s-%s' % (x, y)
+
+    class __extend__(pairtype(bool, bool)):
+        def add((x, y)):
+            return 'bool: %s+%s' % (x, y)
+
+    assert pair(3,4).add() == 'integer: 3+4'
+    assert pair(3,4).sub() == 'integer: 3-4'
+    assert pair(3,True).add() == 'integer: 3+True'
+    assert pair(3,True).sub() == 'integer: 3-True'
+    assert pair(False,4).add() == 'integer: False+4'
+    assert pair(False,4).sub() == 'integer: False-4'
+    assert pair(False,True).add() == 'bool: False+True'
+    assert pair(False,True).sub() == 'integer: False-True'
+
+def test_somebuiltin(): 
+    ### Operation on built-in types
+    class MiniPickler:
+        def __init__(self):
+            self.data = []
+        def emit(self, datum):
+            self.data.append(datum)
+
+    class __extend__(pairtype(MiniPickler, int)):
+        def write((pickler, x)):
+            pickler.emit('I%d' % x)
+
+    class __extend__(pairtype(MiniPickler, str)):
+        def write((pickler, x)):
+            pickler.emit('S%s' % x)
+
+    class __extend__(pairtype(MiniPickler, list)):
+        def write((pickler, x)):
+            for item in x:
+                pair(pickler, item).write()
+            pickler.emit('L%d' % len(x))
+
+    p = MiniPickler()
+    pair(p, [1, 2, ['hello', 3]]).write()
+    assert p.data == ['I1', 'I2', 'Shello', 'I3', 'L2', 'L3']
+
+def test_some_multimethod(): 
+    ### Another multimethod example
+    class Block:
+        def __init__(self, exit):
+            self.exit = exit
+    class Jump:
+        pass
+    class Switch:
+        pass
+    
+    class C_Generator:
+        def __init__(self):
+            self.lines = []
+
+    class __extend__(pairtype(C_Generator, Block)):
+        def emit((gen, block), inputvars):
+            gen.lines.append("C code for block")
+            outputvars = inputvars + ['v4', 'v5']
+            pair(gen, block.exit).emit(outputvars)
+
+    class __extend__(pairtype(C_Generator, Jump)):
+        def emit((gen, jump), inputvars):
+            gen.lines.append("goto xyz")
+
+    class __extend__(pairtype(C_Generator, Switch)):
+        def emit((gen, jump), inputvars):
+            gen.lines.append("switch (%s) { ... }" % inputvars[-1])
+
+    g = C_Generator()
+    pair(g, Block(Switch())).emit(['v1', 'v2'])
+    assert g.lines == ["C code for block", "switch (v5) { ... }"] 
+
+    class Lisp_Generator:
+        def __init__(self):
+            self.progn = []
+
+    class __extend__(pairtype(Lisp_Generator, Block)):
+        def emit((gen, block), inputvars):
+            gen.progn.append("(do 'something)")
+
+    g = Lisp_Generator()
+    pair(g, Block(Switch())).emit(['v1', 'v2'])
+    assert g.progn == ["(do 'something)"]

pypy/annotation/unaryop.py

+"""
+Unary operations on SomeValues.
+"""
+
+from types import FunctionType
+from pypy.interpreter.argument import Arguments
+from pypy.annotation.pairtype import pair
+from pypy.annotation.model import SomeObject, SomeInteger, SomeBool
+from pypy.annotation.model import SomeString, SomeChar, SomeList, SomeDict
+from pypy.annotation.model import SomeTuple, SomeImpossibleValue
+from pypy.annotation.model import SomeInstance, SomeBuiltin 
+from pypy.annotation.model import SomeIterator, SomePBC, new_or_old_class
+from pypy.annotation.model import unionof, set, setunion, missing_operation
+from pypy.annotation.factory import BlockedInference
+from pypy.annotation.bookkeeper import getbookkeeper
+from pypy.annotation.classdef import isclassdef
+
+# convenience only!
+def immutablevalue(x):
+    return getbookkeeper().immutablevalue(x)
+
+UNARY_OPERATIONS = set(['len', 'is_true', 'getattr', 'setattr',
+                        'simple_call', 'call_args',
+                        'iter', 'next'])
+
+for opname in UNARY_OPERATIONS:
+    missing_operation(SomeObject, opname)
+
+
+class __extend__(SomeObject):
+    
+    def len(obj):
+        return SomeInteger(nonneg=True)
+
+    def is_true(obj):
+        if obj.is_constant():
+            return immutablevalue(bool(obj.const))
+        else:
+            s_len = obj.len()
+            if s_len.is_constant():