Armin Rigo avatar Armin Rigo committed bf255bb

Moved the branch back into the trunk.

Comments (0)

Files changed (282)

+General
+=======
+
+* 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 std.utest (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/README.txt

+guiding design/implementation ideas
+-----------------------------------
+
+Annotation aims at providing type inference to RPython programs. 
+Annotation works from the flowmodel of a program. (A flowmodel
+can be viewed as an information-preserving 'dead code' representation
+of a program.)  
+
+Annotation mainly deals with connecting interesting information
+to SomeValue's which are instances of a very simple class::
+
+   class SomeValue:
+        pass
+
+A SomeValue represents a possible state within a program. 
+Any information about the type or more specific information
+like being a constant is done by an Annotation. E.g. the
+an int-type annotation is expressed like this: 
+
+   Annotation(op.type, someval1, someval2)
+   Annotation(op.constant(int), someval2)
+
+Note especially how the constant-ness of someval2 encodes the
+information 'someval2 is exactly int'.  SomeValue's are values on which
+little is known by default, unless Annotation's are used to restrict
+them. 
+
+Keep in mind that the more Annotation's you have on SomeValue, the more
+restricted it is, i.e. the less real values it can represent.  A newly
+created SomeValue() has no annotation by default, i.e. can represent
+anything at all.  At the other extreme, there is a special
+'blackholevalue' that behaves as if it had all Annotation's set on it;
+it stands for an impossible, non-existent value (because all these
+Annotations are contradictory). The name 'blackholevalue' reminds you
+that during type inference SomeValue's start with a lot of annotations
+(possibly as a 'blackholevalue'), and annotations are killed -- less
+annotations, more possibilities. 
+
+Annotations are stored in a global list, which is an AnnotationSet instance.  AnnotationSet provides (via Transactions) methods to query, add and kill annotations.  It also manages "sharing": two different SomeValue's can be later found to be identical (in the Python sense of "is"), and the AnnotationSet can be taught about this.
+
+You can't directly add annotations to an AnnotationSet. Adding an
+annotation is considered to be dependent on previous annotations. 
+Thus you invoke annset.record(func), and your function 'func' will
+be invoked with a 'Recorder' instance: you perform queries with it
+and when you add/set a new annotation the recorder will remember
+the dependency of the previous (queried) annotation towards the
+new annotation. 

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, SomeList, SomeDict
+from pypy.annotation.model import SomeTuple, SomeImpossibleValue
+from pypy.annotation.model import SomeInstance, SomeFunction, SomeMethod
+from pypy.annotation.model import SomeBuiltin, SomeIterator
+from pypy.annotation.model import unionof, set, setunion, missing_operation
+from pypy.annotation.factory import generalize
+
+
+# XXX unify this with ObjSpace.MethodTable
+BINARY_OPERATIONS = set(['add', 'sub', 'mul', 'div', 'mod',
+                         'getitem', 'setitem',
+                         'inplace_add', 'inplace_sub',
+                         'lt', 'le', 'eq', 'ne', 'gt', 'ge',
+                         'union'])
+
+for opname in BINARY_OPERATIONS:
+    missing_operation(pairtype(SomeObject, SomeObject), opname)
+
+
+class __extend__(pairtype(SomeObject, SomeObject)):
+
+    def union((obj1, obj2)):
+        if obj1 == obj2:
+            return obj1
+        else:
+            return SomeObject()
+
+    def inplace_add((obj1, obj2)):
+        return pair(obj1, obj2).add()   # default
+
+    def inplace_sub((obj1, obj2)):
+        return pair(obj1, obj2).sub()   # default
+
+
+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)
+
+    def add((int1, int2)):
+        return SomeInteger(nonneg = int1.nonneg and int2.nonneg,
+                           unsigned = int1.unsigned or int2.unsigned)
+
+    mul = div = mod = add
+
+    def sub((int1, int2)):
+        return SomeInteger(unsigned = int1.unsigned or int2.unsigned)
+
+    def lt((int1, int2)): return SomeBool()
+    def le((int1, int2)): return SomeBool()
+    def eq((int1, int2)): return SomeBool()
+    def ne((int1, int2)): return SomeBool()
+    def gt((int1, int2)): return SomeBool()
+    def ge((int1, int2)): return SomeBool()
+
+
+class __extend__(pairtype(SomeBool, SomeBool)):
+
+    def union((boo1, boo2)):
+        return SomeBool()
+
+
+class __extend__(pairtype(SomeString, SomeString)):
+
+    def union((str1, str2)):
+        return SomeString()
+
+    def add((str1, str2)):
+        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
+
+    def inplace_add((lst1, lst2)):
+        pair(lst1, SomeInteger()).setitem(lst2.s_item)
+        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)):
+        result = dic1.items.copy()
+        for key, s_value in dic2.items.items():
+            if key in result:
+                result[key] = unionof(result[key], s_value)
+            else:
+                result[key] = s_value
+        return SomeDict(setunion(dic1.factories, dic2.factories), result)
+
+
+class __extend__(pairtype(SomeDict, SomeObject)):
+
+    def getitem((dic1, obj2)):
+        if obj2.is_constant():
+            return dic1.items.get(obj2.const, SomeImpossibleValue())
+        else:
+            return SomeObject()
+
+    def setitem((dic1, obj2), s_value):
+        assert obj2.is_constant()
+        key = obj2.const
+        generalize(dic1.factories, key, s_value)
+
+
+class __extend__(pairtype(SomeTuple, SomeInteger)):
+    
+    def getitem((tup1, int2)):
+        if int2.is_constant():
+            return tup1.items[int2.const]
+        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(SomeInteger, SomeList)):
+    
+    def mul((int1, lst2)):
+        return lst2
+
+
+class __extend__(pairtype(SomeInstance, SomeInstance)):
+
+    def union((ins1, ins2)):
+        basedef = ins1.classdef.commonbase(ins2.classdef)
+        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:
+            return SomeObject()
+        else:
+            s_self = unionof(bltn1.s_self, bltn2.s_self)
+            return SomeBuiltin(bltn1.analyser, s_self)
+
+
+class __extend__(pairtype(SomeFunction, SomeFunction)):
+
+    def union((fun1, fun2)):
+        return SomeFunction(setunion(fun1.funcs, fun2.funcs))
+
+
+class __extend__(pairtype(SomeMethod, SomeMethod)):
+
+    def union((met1, met2)):
+        # the union of the two meths dictionaries is a dictionary
+        #   {func: commonbase(met1[func], met2[func])}
+        # note that this case is probably very rare
+        # (the same Python object found in two different classes)
+        d = met1.meths.copy()
+        for func, classdef in met2.meths.items():
+            if func in d:
+                classdef = classdef.commonbase(d[func])
+            d[func] = classdef
+        return SomeMethod(d)
+
+
+class __extend__(pairtype(SomeImpossibleValue, SomeObject)):
+    def union((imp1, obj2)):
+        return obj2
+
+class __extend__(pairtype(SomeObject, SomeImpossibleValue)):
+    def union((obj1, imp2)):
+        return obj1

pypy/annotation/builtin.py

+"""
+Built-in functions.
+"""
+
+from pypy.annotation.model import SomeInteger, SomeObject
+from pypy.annotation.factory import ListFactory, getbookkeeper
+import pypy.objspace.std.restricted_int
+
+
+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)
+
+
+# collect all functions
+import __builtin__
+BUILTIN_FUNCTIONS = {}
+for name, value in globals().items():
+    if name.startswith('builtin_'):
+        original = getattr(__builtin__, name[8:])
+        BUILTIN_FUNCTIONS[original] = value
+
+BUILTIN_FUNCTIONS[pypy.objspace.std.restricted_int.r_int] = builtin_int
+BUILTIN_FUNCTIONS[pypy.objspace.std.restricted_int.r_uint] = restricted_uint

pypy/annotation/factory.py

+"""
+Mutable Objects Factories.
+
+A factory is associated to an SpaceOperation in the source that creates a
+mutable object, currently 'newlist' and 'call' (which can build instances).
+The factory remembers how general an object it has to create here.
+"""
+
+from __future__ import generators
+from types import FunctionType
+from pypy.annotation.model import SomeImpossibleValue, SomeList, SomeDict
+from pypy.annotation.model import SomeObject, SomeInstance
+from pypy.annotation.model import unionof, immutablevalue
+from pypy.interpreter.miscutils import getthreadlocals
+
+
+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
+
+
+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
+
+    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 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 getbookkeeper():
+    """Get the current Bookkeeper.
+    Only works during the analysis of an operation."""
+    return getthreadlocals().bookkeeper
+
+
+#
+#  Factories
+#
+
+def generalize(factories, *args):
+    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
+
+
+class ListFactory:
+    s_item = SomeImpossibleValue()
+
+    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:
+    items = {}
+
+    def create(self):
+        return SomeDict(factories = {self: True}, items = self.items)
+
+    def generalize(self, key, s_new_value):
+        self.items = self.items.copy()
+        if key not in self.items:
+            self.items[key] = s_new_value
+            return True
+        elif not self.items[key].contains(s_new_value):
+            self.items[key] = unionof(self.items[key], s_new_value)
+            return True
+        else:
+            return False
+
+
+class FuncCallFactory:
+
+    def pycall(self, func, *args):
+        return self.bookkeeper.annotator.recursivecall(func, self, *args)
+
+
+class InstanceFactory(FuncCallFactory):
+
+    def create(self, cls, *args):
+        classdef = self.bookkeeper.getclassdef(cls)
+        classdef.instancefactories[self] = 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__:
+            self.pycall(init, s_instance, *args)
+        else:
+            assert not args, "no __init__ found in %r" % (cls,)
+        return s_instance
+
+
+class ClassDef:
+    "Wraps a user class."
+
+    def __init__(self, cls, bookkeeper):
+        self.attrs = {}          # attrs is updated with new information
+        self.revision = 0        # which increases the revision number
+        self.instancefactories = {}
+        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
+        s_self = SomeInstance(self)
+        for name, value in cls.__dict__.items():
+            # ignore some special attributes
+            if name.startswith('_') and not isinstance(value, FunctionType):
+                continue
+            # although self.getallfactories() is currently empty,
+            # the following might still invalidate some blocks if it
+            # generalizes existing values in parent classes
+            s_value = immutablevalue(value)
+            s_value = s_value.classattribute(self)
+            self.generalize(name, s_value, bookkeeper)
+
+    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 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 getallfactories(self):
+        factories = {}
+        for clsdef in self.getallsubdefs():
+            factories.update(clsdef.instancefactories)
+        return factories
+
+    def generalize(self, attr, s_value, bookkeeper=None):
+        # we make sure that an attribute never appears both in a class
+        # and in some subclass, in two steps:
+        # (1) check if the attribute is already in a superclass
+        for clsdef in self.getmro():
+            if attr in clsdef.attrs:
+                self = clsdef   # generalize the parent class instead
+                break
+        # (2) remove the attribute from subclasses
+        subclass_values = []
+        for subdef in self.getallsubdefs():
+            if attr in subdef.attrs:
+                subclass_values.append(subdef.attrs[attr])
+                del subdef.attrs[attr]
+            # bump the revision number of this class and all subclasses
+            subdef.revision += 1
+        self.attrs[attr] = unionof(s_value, *subclass_values)
+        # reflow from all factories
+        if bookkeeper:
+            for factory in self.getallfactories():
+                bookkeeper.annotator.reflowfromposition(factory.position_key)

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 pypy.annotation.pairtype import pair, extendabletype
+
+
+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):
+        kwds = ', '.join(['%s=%r' % item for item in self.__dict__.items()])
+        return '%s(%s)' % (self.__class__.__name__, kwds)
+    def contains(self, other):
+        return self == other or pair(self, other).union() == self
+    def is_constant(self):
+        return hasattr(self, 'const')
+
+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 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
+
+class SomeDict(SomeObject):
+    "Stands for a dict with known keys."
+    knowntype = dict
+    def __init__(self, factories, items):
+        self.factories = factories
+        self.items = items    # dict {realkey: 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 SomeClass(SomeObject):
+    "Stands for a user-defined class object."
+    # only used when the class object is loaded in a variable
+    knowntype = ClassType
+    def __init__(self, cls):
+        self.cls = cls
+
+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
+
+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 SomeFunction(SomeObject):
+    """Stands for a Python function (or some function out of a list).
+    Alternatively, it can be a constant bound or unbound method."""
+    knowntype = FunctionType
+    def __init__(self, funcs):
+        self.funcs = funcs   # set of functions that this one may be
+
+class SomeMethod(SomeObject):
+    "Stands for a bound Python method (or some method out of a list)."
+    knowntype = MethodType
+    def __init__(self, meths):
+        self.meths = meths   # map {python_function: classdef}
+
+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()
+    return s1
+
+def ishashable(x):
+    try:
+        hash(x)
+    except TypeError:
+        return False
+    else:
+        return True
+
+def immutablevalue(x):
+    "The most precise SomeValue instance that contains the immutable value x."
+    if isinstance(bool, type) and isinstance(x, bool):
+        result = SomeBool()
+    elif isinstance(x, int):
+        result = SomeInteger(nonneg = x>=0)
+    elif isinstance(x, str):
+        result = SomeString()
+    elif isinstance(x, tuple):
+        result = SomeTuple(items = [immutablevalue(e) for e in x])
+    elif ishashable(x) and x in BUILTIN_FUNCTIONS:
+        result = SomeBuiltin(BUILTIN_FUNCTIONS[x])
+    elif isinstance(x, (type, ClassType)) and x.__module__ != '__builtin__':
+        result = SomeClass(x)
+    elif isinstance(x, (FunctionType, MethodType)):
+        result = SomeFunction({x: True})
+    else:
+        result = SomeObject()
+    result.const = x
+    return result
+
+def valueoftype(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={})
+    else:
+        return SomeObject()
+
+##def decode_simple_call(s_args, s_kwds):
+##    s_nbargs = s_args.len()
+##    if not s_nbargs.is_constant():
+##        return None
+##    nbargs = s_nbargs.const
+##    arglist = [pair(s_args, immutablevalue(j)).getitem()
+##               for j in range(nbargs)]
+##    s_nbkwds = s_kwds.len()
+##    if not s_nbkwds.is_constant() or s_nbkwds.const != 0:
+##        return None    # XXX deal with dictionaries with keywords
+##    return arglist
+
+
+# ____________________________________________________________
+# 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 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
+from pypy.annotation.builtin  import BUILTIN_FUNCTIONS

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
+
+
+# ____________________________________________________________
+
+if __name__ == '__main__':
+    from unittest2 import check
+    
+    ### 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)
+
+    check.equal(pair(3,4).add(), 'integer: 3+4')
+    check.equal(pair(3,4).sub(), 'integer: 3-4')
+    check.equal(pair(3,True).add(), 'integer: 3+True')
+    check.equal(pair(3,True).sub(), 'integer: 3-True')
+    check.equal(pair(False,4).add(), 'integer: False+4')
+    check.equal(pair(False,4).sub(), 'integer: False-4')
+    check.equal(pair(False,True).add(), 'bool: False+True')
+    check.equal(pair(False,True).sub(), 'integer: False-True')
+
+    ### 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()
+    check.equal(p.data, ['I1', 'I2', 'Shello', 'I3', 'L2', 'L3'])
+
+    ### 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'])
+    check.equal(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'])
+    check.equal(g.progn, ["(do 'something)"])
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 dont have the part
+    an EnvironmentError is raised."""
+
+    import sys, os 
+    try:
+        head = this_dir = os.path.abspath(os.path.dirname(__file__))
+    except NameError:
+        head = this_dir = os.path.abspath(os.path.dirname(sys.argv[0]))
+
+    while head:
+        partdir = head
+        head, tail = os.path.split(head)
+        if tail == part:
+            try:
+                sys.path.remove(head)
+            except ValueError:
+                pass
+            sys.path.insert(0, head)
+            return partdir, this_dir
+        
+    raise EnvironmentError, "'%s' missing in '%r'" % (pathpart,this_path)
+
+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])
+
+
+if __name__ == '__main__':
+    for name, value in globals().items():
+        if name.startswith('test_'):
+            value()

pypy/annotation/unaryop.py

+"""
+Unary operations on SomeValues.
+"""
+
+from types import FunctionType
+from pypy.annotation.pairtype import pair
+from pypy.annotation.model import SomeObject, SomeInteger, SomeBool
+from pypy.annotation.model import SomeString, SomeList, SomeDict
+from pypy.annotation.model import SomeTuple, SomeImpossibleValue
+from pypy.annotation.model import SomeInstance, SomeBuiltin, SomeClass
+from pypy.annotation.model import SomeFunction, SomeMethod, SomeIterator
+from pypy.annotation.model import immutablevalue
+from pypy.annotation.model import unionof, set, setunion, missing_operation
+from pypy.annotation.factory import BlockedInference, getbookkeeper
+from pypy.annotation.factory import InstanceFactory, FuncCallFactory
+
+
+UNARY_OPERATIONS = set(['len', 'is_true', 'getattr', 'setattr', 'simple_call',
+                        '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):
+        return SomeBool()
+
+    def getattr(obj, s_attr):
+        # get a SomeBuiltin if the SomeObject has
+        # a corresponding method to handle it
+        if s_attr.is_constant() and isinstance(s_attr.const, str):
+            attr = s_attr.const
+            analyser = getattr(obj.__class__, 'method_' + attr, None)
+            if analyser is not None:
+                return SomeBuiltin(analyser, obj)
+            # if the SomeObject is itself a constant, allow reading its attrs
+            if obj.is_constant() and hasattr(obj.const, attr):
+                return immutablevalue(getattr(obj.const, attr))
+        return SomeObject()
+
+    def classattribute(obj, classdef):
+        return obj   # default unbound __get__ implementation
+
+
+class __extend__(SomeTuple):
+
+    def len(tup):
+        return immutablevalue(len(tup.items))
+
+
+class __extend__(SomeDict):
+
+    def len(dic):
+        return immutablevalue(len(dic.items))
+
+
+class __extend__(SomeList):
+
+    def method_append(lst, s_item):
+        pair(lst, SomeInteger()).setitem(s_item)
+
+    def iter(lst):
+        return SomeIterator(lst.s_item)
+
+
+class __extend__(SomeIterator):
+
+    def next(itr):
+        return itr.s_item
+
+
+class __extend__(SomeInstance):
+
+    def currentdef(ins):
+        if ins.revision != ins.classdef.revision:
+            #print ins.revision, ins.classdef.revision
+            raise BlockedInference
+        return ins.classdef
+
+    def getattr(ins, s_attr):
+        if s_attr.is_constant() and isinstance(s_attr.const, str):
+            attr = s_attr.const
+            #print 'getattr:', ins, attr, ins.classdef.revision
+            # look for the attribute in the MRO order
+            for clsdef in ins.currentdef().getmro():
+                if attr in clsdef.attrs:
+                    # XXX we can't see the difference between function objects
+                    # XXX on classes or on instances, so this will incorrectly
+                    # XXX turn functions read from instances into methods
+                    return clsdef.attrs[attr]
+            # maybe the attribute exists in some subclass? if so, lift it
+            clsdef = ins.classdef
+            clsdef.generalize(attr, SomeImpossibleValue(), getbookkeeper())
+            raise BlockedInference
+        return SomeObject()
+
+    def setattr(ins, s_attr, s_value):
+        if s_attr.is_constant() and isinstance(s_attr.const, str):
+            attr = s_attr.const
+            for clsdef in ins.currentdef().getmro():
+                if attr in clsdef.attrs:
+                    # look for the attribute in ins.classdef or a parent class
+                    s_existing = clsdef.attrs[attr]
+                    if s_existing.contains(s_value):
+                        return   # already general enough, nothing to do
+                    break
+            else:
+                # if the attribute doesn't exist yet, create it here
+                clsdef = ins.classdef
+            # create or update the attribute in clsdef
+            clsdef.generalize(attr, s_value, getbookkeeper())
+            raise BlockedInference
+        return SomeObject()
+
+
+class __extend__(SomeBuiltin):
+
+    def simple_call(bltn, *args):
+        if bltn.s_self is not None:
+            return bltn.analyser(bltn.s_self, *args)
+        else:
+            return bltn.analyser(*args)
+
+
+class __extend__(SomeClass):
+
+    def simple_call(cls, *args):
+        factory = getbookkeeper().getfactory(InstanceFactory)
+        return factory.create(cls.cls, *args)
+
+
+class __extend__(SomeFunction):
+
+    def simple_call(fun, *args):
+        factory = getbookkeeper().getfactory(FuncCallFactory)
+        results = [factory.pycall(func, *args) for func in fun.funcs]
+        return unionof(*results)
+
+    def classattribute(fun, classdef):   # function -> unbound method
+        d = {}
+        for func in fun.funcs:
+            assert isinstance(func, FunctionType), (
+                "%r should not be read out of class %r" % (func, classdef))
+            d[func] = classdef
+        return SomeMethod(d)
+
+
+class __extend__(SomeMethod):
+
+    def simple_call(met, *args):
+        factory = getbookkeeper().getfactory(FuncCallFactory)
+        results = []
+        for func, classdef in met.meths.items():
+            # create s_self and record the creation in the factory
+            s_self = SomeInstance(classdef)
+            classdef.instancefactories[factory] = True
+            # call func(s_self, *arglist)
+            results.append(factory.pycall(func, s_self, *args))
+        return unionof(*results)

pypy/appspace/__init__.py

+#

pypy/appspace/_float_formatting.py

+import math
+
+# from the excessive effort department, routines for printing floating
+# point numbers from
+
+# "Printing Floating-Point Numbers Quickly and Accurately" by Burger &
+# Dybvig, Proceedings of the SIGPLAN '96 Conference on Programming
+# Language Design and Implementation.
+
+# The paper contains scheme code which has been specialized for IEEE
+# doubles and converted into Python by Michael Hudson.
+
+# XXX unfortunately, we need the fixed-format output routines, the source
+# for which is not included in the paper... for now, just put up with
+# occasionally incorrectly rounded final digits.  I'll get to it.
+
+# XXX should run this at interpreter level, really....
+
+def decode_float(f):
+    """decode_float(float) -> int, int
+
+    Return (m, e), the mantissa and exponent respectively of
+    f (assuming f is an IEEE double), i.e. f == m * 2**e and
+    2**52 <= m < 2**53."""
+    m, e = math.frexp(f)
+    m = long(m*2.0**53)
+    e -= 53
+    return m, e
+
+def decompose(f):
+    """decompose(float) -> int, int, int, int
+
+    Return r, s, m_plus, m_minus for f, in the terms of
+    Burger and Dybvig's paper (see Table 1).
+
+    To spell this out: f = r/s, (r+m+)/s is halfway to the
+    next largest floating point number, (r-m-) halfway to
+    the next smallest."""
+    m, e = decode_float(f)
+    if e >= 0:
+        if not m != 2**52:
+            be = 2**e
+            return m*be*2, 2, be, be
+        else:
+            be = 2**e
+            be1 = 2*be
+            return m*be1*2, 4, be1, be
+    else:
+        if e == -1075 or m != 2**52:
+            return m*2, 2**(-e+1), 1, 1
+        else:
+            return m*4, 2**(-e+2), 2, 1
+
+
+def flonum2digits(f):
+    """flonum2digits(float) -> [int], int
+
+    Given a float f return [d1, ..., dn], k such that
+
+        0.[d1][d2]...[dn] * 10**k
+
+    is the shortest decimal representation that will
+    reproduce f when read in by a correctly rounding input
+    routine (under any strategy for breaking ties)."""
+    
+    assert f >= 0
+    if f == 0.0:
+        return ['0'], 1
+
+    # See decompose's docstring for what these mean.
+    r, s, m_plus, m_minus = decompose(f)
+
+    # k is the index, relative to the radix point of the
+    # most-significant non-zero digit of the infinite
+    # decimal expansion of f.  This calculation has the
+    # potential to underestimate by one (handled below).
+    k = long(math.ceil(math.log10(f) - 1e-10))
+
+    if k >= 0:
+        s *= 10 ** k
+    else:
+        scale = 10 ** -k
+        r *= scale
+        m_plus *= scale
+        m_minus *= scale
+
+    # Check that we got k right above.
+    if r + m_plus > s:
+        s *= 10
+        k += 1
+
+    # Generate the digits.
+    rr = []
+    while 1:
+        d, r = divmod(r*10, s)
+        m_plus *= 10
+        m_minus *= 10
+        tc1 = r < m_minus
+        tc2 = (r + m_plus) > s
+        if tc2:
+            rr.append(d+1)
+        else:
+            rr.append(d)
+        if tc1 or tc2:
+            break
+        
+    assert max(rr) < 10
+    assert min(rr) >= 0
+
+    return map(str, rr), k

pypy/appspace/_formatting.py

+# Application level implementation of string formatting.
+
+# There's some insane stuff in here.  Blame CPython.  Please.
+
+# Known problems:
+# (1) rounding isn't always right (see comments in _float_formatting).
+# (2) something goes wrong in the f_alt case of %g handling.
+# (3) it's really, really slow.
+
+class _Flags(object):
+    def __repr__(self):
+        return "<%s>"%(', '.join([f for f in self.__dict__ 
+                                  if f[0] == 'f' and getattr(self, f)]),)
+    f_ljust = 0
+    f_sign = 0
+    f_blank = 0
+    f_alt = 0
+    f_zero = 0
+
+
+def value_next(valueiter):
+    try:
+        return valueiter.next()
+    except StopIteration:
+        raise TypeError('not enough arguments for format string')    
+
+
+def peel_num(c, fmtiter, valueiter):
+    if c == '*':
+        v = value_next(valueiter)
+        if not isinstance(v, int):
+            raise TypeError, "* wants int"
+        return fmtiter.next(), v
+    n = ''
+    while c in '0123456789':
+        n += c
+        c = fmtiter.next()
+    if n:
+        return c, int(n)
+    else:
+        return c, 0
+
+
+def peel_flags(c, fmtiter):
+    flags = _Flags()
+    while 1:
+        if c == '-':
+            flags.f_ljust = True
+        elif c == '+':
+            flags.f_sign = True
+        elif c == ' ':
+            flags.f_blank = True
+        elif c == '#':
+            flags.f_alt = True
+        elif c == '0':
+            flags.f_zero = True
+        else:
+            break
+        c = fmtiter.next()
+    return c, flags
+
+
+def parse_fmt(fmtiter, valueiter, valuedict):
+    """return (char, flags, width, prec, value)
+    partially consumes fmtiter & valueiter"""
+    c = fmtiter.next()
+    gotvalue = False
+    if c == '(':
+        n = ''
+        pcount = 1
+        while 1:
+            c = fmtiter.next()
+            if c == ')':
+                pcount -= 1
+                if pcount == 0:
+                    break
+            elif c == '(':
+                pcount += 1
+            n += c
+        value = valuedict[n]
+        gotvalue = True
+        c = fmtiter.next()
+    c, flags = peel_flags(c, fmtiter)
+    c, width = peel_num(c, fmtiter, valueiter)
+    if c == '.':
+        c, prec = peel_num(fmtiter.next(), fmtiter, valueiter)
+    else:
+        prec = None
+    if c in 'hlL':
+        c = fmtiter.next()
+    if width and width < 0:
+        # this can happen with *-args
+        flags.f_ljust = True
+        width = -width
+    if not gotvalue:
+        if c == '%':
+            # did YOU realize that "%4%"%() == '   %'??
+            value = '%'
+            c = 's'
+        else:
+            value = value_next(valueiter)
+    return (c, flags, width, prec, value)
+
+
+class Formatter(object):
+    def __init__(self, char, flags, width, prec, value):
+        self.char = char
+        self.flags = flags
+        self.width = width
+        self.prec = prec
+        self.value = value
+ 
+    def numeric_preprocess(self, v):
+        # negative zeroes?
+        # * mwh giggles, falls over
+        # still, if we can recognize them, here's the place to do it.
+        import math
+        if v < 0 or v == 0 and math.atan2(0, v) != 0:
+            sign = '-'
+            v = -v            
+        else:
+            if self.flags.f_sign:
+                sign = '+'
+            elif self.flags.f_blank:
+                sign = ' '
+            else:
+                sign = ''
+        return v, sign
+
+    def numeric_postprocess(self, r, sign):
+        assert self.char in 'iduoxXeEfFgG'
+        padchar = ' '
+        if self.flags.f_zero:
+            padchar = '0'
+        if self.width is not None:
+            p = self.width - len(r) - len(sign)
+            if self.flags.f_ljust:
+                r = sign + r + ' '*p
+            else:
+                if self.flags.f_zero:
+                    r = sign+padchar*p + r
+                else:
+                    r = padchar*p + sign + r                    
+        else:
+            r = sign + r
+        return r
+
+    def format(self):
+        raise NotImplementedError
+
+    def std_wp(self, r):
+        assert self.char not in 'iduoxXeEfFgG'
+        if self.prec is not None:
+            r = r[:self.prec]
+        if self.width is not None:
+            p = self.width - len(r)
+            if self.flags.f_ljust:
+                r = r + ' '*p
+            else:
+                r = ' '*p + r
+        return r
+
+
+def funcFormatter(*funcs):
+    class _F(Formatter):
+        def format(self):
+            r = self.value
+            for f in funcs:
+                r = f(r)
+            return self.std_wp(r)
+    return _F
+
+
+def maybe_int(value):
+    try:
+        inter = value.__int__
+    except AttributeError:
+        raise TypeError, "an integer argument is required"
+    return inter()
+
+
+def maybe_float(value):
+    try:
+        floater = value.__float__
+    except AttributeError:
+        raise TypeError, "a float argument is required"
+    return floater()
+
+
+from _float_formatting import flonum2digits
+
+class FloatFormatter(Formatter):
+    def eDigits(self, ds):
+        ds = ds[:self.prec + 1] + ['0'] * (self.prec + 1 - len(ds))
+        if self.prec > 0 or self.flags.f_alt:
+            ds[1:1] = ['.']
+        return ''.join(ds)
+
+    def fDigits(self, ds, k):
+        p = max(self.prec, 0)
+        if 0 < k < len(ds):
+            if len(ds) - k < p:
+                ds.extend(['0'] * (p - (len(ds) - k)))
+            else:
+                ds = ds[:p + k]
+            ds[k:k] = ['.']
+        elif k <= 0:
+            ds[0:0] = ['0']*(-k)
+            ds = ds[:p]
+            ds.extend(['0'] * (p - len(ds)))
+            ds[0:0]= ['0', '.']
+        elif k >= len(ds):
+            ds.extend((k-len(ds))*['0'] + ['.'] + ['0']*p)
+        return ''.join(ds)
+
+    def format(self):
+        v = maybe_float(self.value)
+        v, sign = self.numeric_preprocess(v)
+        if self.prec is None:
+            self.prec = 6
+        r = self._format(v)
+        return self.numeric_postprocess(r, sign)
+        
+
+class FloatFFormatter(FloatFormatter):
+    def _format(self, v):
+        if v/1e25 > 1e25:
+            return floatGFormatter('g', self.flags, self.width,
+                                   self.prec, self.value).format()
+        ds, k = flonum2digits(v)
+        digits = self.fDigits(ds, k)
+        if  not self.flags.f_alt:
+            digits = digits.rstrip('.')
+        return digits
+
+
+class FloatEFormatter(FloatFormatter):
+    def _format(self, v):
+        ds, k = flonum2digits(v)
+        digits = self.eDigits(ds)
+        return "%s%c%+03d"%(digits, self.char, k-1)
+
+
+class FloatGFormatter(FloatFormatter):
+    # The description of %g in the Python documentation lies
+    # in a variety of minor ways.
+    # Gah, this still isn't quite right in the f_alt case.
+    # (One has to wonder who might care).
+    def _format(self, v):
+        ds, k = flonum2digits(v)
+        ds = ds[:self.prec] # XXX rounding!
+        if -4 < k <= self.prec:
+            digits = self.fDigits(ds, k)
+            if not self.flags.f_alt:
+                digits = digits.rstrip('0').rstrip('.')
+            r = digits
+        else:
+            digits = self.eDigits(ds)
+            if not self.flags.f_alt:
+                digits = digits.rstrip('0').rstrip('.')
+            r = "%se%+03d"%(digits, k-1)
+        return r
+
+
+class HexFormatter(Formatter):
+    # NB: this has 2.4 semantics wrt. negative values
+    def format(self):
+        v, sign = self.numeric_preprocess(maybe_int(self.value))
+        r = hex(v)[2:]
+        if self.prec is not None and len(r) < self.prec:
+            r = '0'*(self.prec - len(r)) + r
+        if self.flags.f_alt:
+            r = '0x' + r
+        if self.char == 'X':
+            r = r.upper()
+        return self.numeric_postprocess(r, sign)
+
+
+class OctFormatter(Formatter):
+    # NB: this has 2.4 semantics wrt. negative values
+    def format(self):
+        v, sign = self.numeric_preprocess(maybe_int(self.value))
+        r = oct(v)
+        if not self.flags.f_alt:
+            r = r[1:]
+        if self.prec is not None and len(r) < self.prec:
+            r = '0'*(self.prec - len(r)) + r
+        return self.numeric_postprocess(r, sign)
+
+
+class IntFormatter(Formatter):
+    # NB: this has 2.4 semantics wrt. negative values (for %u)
+    def format(self):
+        v, sign = self.numeric_preprocess(maybe_int(self.value))
+        r = str(v)
+        if self.prec is not None and len(r) < self.prec:
+            r = '0'*(self.prec - len(r)) + r
+        return self.numeric_postprocess(r, sign)
+
+
+class CharFormatter(Formatter):
+    def format(self):
+        if isinstance(self.value, str):
+            v = self.value
+            if len(v) != 1:
+                raise TypeError, "%c requires int or char"
+        else:
+            i = maybe_int(self.value)
+            if not 0 <= i <= 255:
+                raise OverflowError("OverflowError: unsigned byte "
+                                    "integer is greater than maximum")
+            v = chr(i)
+        self.prec = None
+        return self.std_wp(v)
+
+
+format_registry = {
+    'd':IntFormatter,
+    'i':IntFormatter,
+    'o':OctFormatter,
+    'u':IntFormatter,
+    'x':HexFormatter,
+    'X':HexFormatter,
+    'e':FloatEFormatter,
+    'E':FloatEFormatter,
+    'f':FloatFFormatter,
+    'F':FloatFFormatter,
+    'g':FloatGFormatter,
+    'G':FloatGFormatter,
+    'c':CharFormatter,
+    's':funcFormatter(str),
+    'r':funcFormatter(repr),
+    # this *can* get accessed, by e.g. '%()4%'%{'':1}.
+    # The usual %% case has to be handled specially as it
+    # doesn't consume a value.
+    '%':funcFormatter(lambda x:'%'),
+    }
+
+    
+class FmtIter(object):
+    def __init__(self, fmt):
+        self.fmt = fmt
+        self.i = 0
+
+    def __iter__(self):
+        return self
+
+    def next(self):
+        try:
+            c = self.fmt[self.i]
+        except IndexError:
+            raise StopIteration
+        self.i += 1
+        return c
+
+    def skip_to_fmt(self):
+        i = self.i
+        j = self.fmt.find('%', i)
+        if j < 0:
+            self.i = len(self.fmt)
+            return self.fmt[i:]
+        else:
+            self.i = j
+            return self.fmt[i:j]
+
+
+def format(fmt, values, valuedict=None):
+    fmtiter = FmtIter(fmt)
+    valueiter = iter(values)
+    r = []
+    try:
+        for c in fmtiter:
+            if c == '%':
+                t = parse_fmt(fmtiter, valueiter, valuedict)
+                try:
+                    f = format_registry[t[0]]
+                except KeyError:
+                    raise ValueError("unsupported format character "
+                                     "'%s' (%x) at index %d"
+                                     %(t[0], ord(t[0]), fmtiter.i))
+                r.append(f(*t).format())
+            else:
+                # efficiency hack:
+                r.append(c + fmtiter.skip_to_fmt())
+    except StopIteration:
+        raise ValueError, "incomplete format"
+    try:
+        valueiter.next()
+    except StopIteration:
+        pass
+    else:
+        if valuedict is None:
+            raise TypeError('not all arguments converted '
+                            'during string formatting')
+    return ''.join(r)
+            

pypy/appspace/_types.py

+"""
+Definition of the standard Python types.
+"""
+
+# XXX we can't do this import yet
+from sys import pypy
+import __builtin__
+import _types
+
+__all__ = ['BooleanType', 'BufferType', 'BuiltinFunctionType',
+           'BuiltinMethodType', 'ClassType', 'CodeType', 'ComplexType',
+           'DictProxyType', 'DictType', 'DictionaryType', 'EllipsisType',
+           'FileType', 'FloatType', 'FrameType', 'FunctionType',
+           'GeneratorType', 'InstanceType', 'IntType', 'LambdaType',
+           'ListType', 'LongType', 'MethodType', 'ModuleType', 'NoneType',