# HG changeset patch
# User paulb@jeremy
# Date 1153691833 -7200
# Node ID c9ce39c2076a8ab327aacaf20b439e112e2e75a8
# Parent  929af7341cec7d16eece56bf4653d0b59e452f85
Added the beginnings of invocation support.
Fixed/improved constant and built-in type initialisation.


diff -r 929af7341cec -r c9ce39c2076a annotate.py
--- a/annotate.py	Sun Jul 23 23:56:11 2006 +0200
+++ b/annotate.py	Sun Jul 23 23:57:13 2006 +0200
@@ -1,7 +1,9 @@
 #!/usr/bin/env python
 
 """
-Traverse and annotate simplified AST structures.
+Annotate simplified AST structures. The code in this module operates upon nodes
+which are produced when simplifying AST node trees originating from the compiler
+module.
 
 Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk>
 
@@ -24,7 +26,33 @@
 from simplified import *
 import compiler
 
+class System:
+
+    "A class maintaining the state of the annotation system."
+
+    def __init__(self):
+        self.count = 0
+    def init(self, node):
+        if not hasattr(node, "types"):
+            node.types = []
+    def annotate(self, node, types):
+        self.init(node)
+        for type in types:
+            if type not in node.types:
+                node.types.append(type)
+                self.count += 1
+
+system = System()
+
+# Namespaces and related abstractions.
+
 class Namespace:
+
+    """
+    A local namespace which may either relate to a genuine set of function
+    locals or the initialisation of a structure.
+    """
+
     def __init__(self, local_is_structure=0):
         if local_is_structure:
             self.local = "structure"
@@ -62,7 +90,10 @@
             return self.names[name]
 
     def merge(self, namespace):
-        for name, types in namespace.names.items():
+        self.merge_items(namespace.names.items())
+
+    def merge_items(self, items):
+        for name, types in items:
             if not self.names.has_key(name):
                 self.names[name] = types
             else:
@@ -71,35 +102,56 @@
                     if type not in existing:
                         existing.append(type)
 
-class System:
-    def __init__(self):
-        self.count = 0
-    def init(self, node):
-        if not hasattr(node, "types"):
-            node.types = []
-    def annotate(self, node, types):
-        for type in types:
-            if type not in node.types:
-                node.types.append(type)
-                self.count += 1
+class Attribute:
+
+    """
+    An attribute abstraction, indicating the type of the attribute along with
+    its context or origin.
+    """
+
+    def __init__(self, context, type):
+        self.context = context
+        self.type = type
+
+    def __eq__(self, other):
+        return hasattr(other, "type") and other.type == self.type or other == self.type
+
+# Annotation.
 
 class Annotator(Visitor):
+
+    """
+    The type annotator which traverses the program nodes, typically depth-first,
+    and maintains a record of the current set of types applying to the currently
+    considered operation. Such types are also recorded on the nodes, and a
+    special "system" record is maintained to monitor the level of annotation
+    activity with a view to recognising when no more annotations are possible.
+    """
+
     def __init__(self):
         Visitor.__init__(self)
-        self.system = System()
+        self.system = system
         self.types = None
         self.temp = {}
 
-    def process(self, node, global_namespace=None):
+    def process(self, node, locals=None, globals=None):
+
+        """
+        Process a subprogram or module 'node', indicating any initial 'locals'
+        and 'globals' if either are defined. Return an annotated subprogram or
+        module. Note that this method may mutate nodes in the original program.
+        """
+
         if hasattr(node, "structure"):
-            self.structure = node.structure
-            has_structure = 1
+            self.structure = node.structure; has_structure = 1
         else:
-            self.structure = None
-            has_structure = 0
+            self.structure = None; has_structure = 0
 
         self.namespace = Namespace(self.structure is not None)
-        self.global_namespace = global_namespace or self.namespace # NOTE: Improve this.
+        if locals is not None:
+            self.namespace.merge(locals)
+
+        self.global_namespace = globals or self.namespace # NOTE: Improve this.
 
         if has_structure:
             node.structure.namespace = self.namespace
@@ -110,27 +162,23 @@
 
         return result
 
+    def annotate(self, node):
+
+        "Annotate the given 'node' in the system."
+
+        self.system.annotate(node, self.types)
+
     def default(self, node):
+
+        """
+        Process the given 'node', given that it does not have a specific
+        handler.
+        """
+
         for attr in ("args",):
             value = getattr(node, attr, None)
             if value is not None:
                 setattr(node, attr, self.dispatches(value))
-
-        # NOTE: This will eventually use both defaults and supplied arguments.
-
-        for attr in ("params",):
-            value = getattr(node, attr, None)
-            if value is not None:
-                params = []
-                for name, default in value:
-                    if default is not None:
-                        n = self.dispatch(default)
-                        self.namespace.store(name, self.types)
-                    else:
-                        n = None
-                        self.namespace.store(name, [])
-                    params.append((name, n))
-                setattr(node, attr, params)
         for attr in ("expr", "lvalue", "test", "handler", "star", "dstar"):
             value = getattr(node, attr, None)
             if value is not None:
@@ -151,22 +199,23 @@
 
     def visitLoadRef(self, loadref):
         self.types = [loadref.ref]
+        self.annotate(loadref)
         return loadref
 
     def visitLoadName(self, loadname):
         scope = self.namespace.find_for_load(loadname.name)
-        print "LoadName", scope
         if scope == "structure":
-            return self.dispatch(LoadAttr(expr=LoadRef(ref=self.structure), name=loadname.name))
+            result = self.dispatch(LoadAttr(expr=LoadRef(ref=self.structure), name=loadname.name))
         elif scope == "global":
-            return self.dispatch(LoadGlobal(name=loadname.name))
+            result = self.dispatch(LoadGlobal(name=loadname.name))
         else:
             self.types = self.namespace.load(loadname.name)
-            return loadname
+            result = loadname
+            self.annotate(result)
+        return result
 
     def visitStoreName(self, storename):
         scope = self.namespace.find_for_store(storename.name)
-        print "StoreName", scope
         if scope == "structure":
             return self.dispatch(StoreAttr(lvalue=LoadRef(ref=self.structure), name=storename.name, expr=storename.expr))
         elif scope == "global":
@@ -178,6 +227,7 @@
 
     def visitLoadGlobal(self, loadglobal):
         self.types = self.global_namespace.load(loadglobal.name)
+        self.annotate(loadglobal)
         return loadglobal
 
     def visitStoreGlobal(self, storeglobal):
@@ -191,6 +241,7 @@
     def visitLoadTemp(self, loadtemp):
         index = getattr(loadtemp, "index", None)
         self.types = self.temp[index]
+        self.annotate(loadtemp)
         return loadtemp
 
     def visitStoreTemp(self, storetemp):
@@ -208,8 +259,10 @@
         loadattr.expr = self.dispatch(loadattr.expr)
         types = []
         for ref in self.types:
-            types += ref.namespace.load(loadattr.name)
+            for type in ref.namespace.load(loadattr.name):
+                types.append(Attribute(ref, type))
         self.types = types
+        self.annotate(loadattr)
         return loadattr
 
     def visitStoreAttr(self, storeattr):
@@ -220,4 +273,103 @@
             ref.namespace.store(storeattr.name, expr)
         return storeattr
 
+    def visitInvoke(self, invoke):
+        invoke.expr = self.dispatch(invoke.expr)
+        expr = self.types
+        types = []
+        args = []
+
+        # Get type information for regular arguments.
+
+        for arg in invoke.args:
+            args.append(self.dispatch(arg))
+            types.append(self.types)
+
+        # Get type information for star and dstar arguments.
+
+        if invoke.star is not None:
+            param, default = invoke.star
+            default = self.dispatch(default)
+            invoke.star = param, default
+            types.append(default.types)
+
+        if invoke.dstar is not None:
+            param, default = invoke.dstar
+            default = self.dispatch(default)
+            invoke.dstar = param, default
+            types.append(default.types)
+
+        invoke.args = args
+        invoke.types = expr
+
+        # NOTE: Now locate and invoke the subprogram.
+
+        for subprogram in expr:
+            items = self.make_items(invoke, subprogram)
+            self.process(subprogram, self.make_namespace(items), self.global_namespace)
+
+        return invoke
+
+    def make_items(self, invocation, subprogram):
+        # NOTE: Support star and dstar.
+        args = invocation.args
+        params = subprogram.params
+        items = []
+        keywords = {}
+
+        # Process the specified arguments.
+
+        for arg in args:
+            if isinstance(arg, Keyword):
+                keywords[arg.name] = arg.expr
+                continue
+            elif params:
+                param, default = params[0]
+                if arg is None:
+                    arg = self.dispatch(default)
+            else:
+                raise TypeError, "Invocation has too many arguments."
+            items.append((param, arg.types))
+            params = params[1:]
+
+        # Collect the remaining defaults.
+
+        while params:
+            param, default = params[0]
+            if keywords.has_key(param):
+                arg = keywords[param]
+            else:
+                arg = self.dispatch(default)
+            items.append((param, arg.types))
+            params = params[1:]
+
+        # Add star and dstar.
+
+        if invocation.star is not None:
+            if subprogram.star is not None:
+                param, default = subprogram.star
+                items.append((param, invocation.star.types))
+            else:
+                raise TypeError, "Invocation provides unwanted *args."
+        elif subprogram.star is not None:
+            param, default = subprogram.star
+            items.append((param, self.dispatch(default)))
+
+        if invocation.dstar is not None:
+            if subprogram.dstar is not None:
+                param, default = subprogram.dstar
+                items.append((param, invocation.dstar.types))
+            else:
+                raise TypeError, "Invocation provides unwanted **args."
+        elif subprogram.dstar is not None:
+            param, default = subprogram.dstar
+            items.append((param, self.dispatch(default)))
+
+        return items
+
+    def make_namespace(self, items):
+        namespace = Namespace()
+        namespace.merge_items(items)
+        return namespace
+
 # vim: tabstop=4 expandtab shiftwidth=4
diff -r 929af7341cec -r c9ce39c2076a simplified.py
--- a/simplified.py	Sun Jul 23 23:56:11 2006 +0200
+++ b/simplified.py	Sun Jul 23 23:57:13 2006 +0200
@@ -23,6 +23,29 @@
 
 from compiler.visitor import ASTVisitor
 
+# Elementary visitor support.
+
+class Visitor(ASTVisitor):
+
+    "A visitor base class."
+
+    def __init__(self):
+        ASTVisitor.__init__(self)
+
+    def default(self, node, *args):
+        raise ValueError, node.__class__
+
+    def dispatch(self, node, *args):
+        return ASTVisitor.dispatch(self, node, *args)
+
+    def dispatches(self, nodes, *args):
+        results = []
+        for node in nodes:
+            results.append(self.dispatch(node, *args))
+        return results
+
+# Simplified program nodes.
+
 class Node:
 
     """
@@ -87,6 +110,12 @@
         if hasattr(self, "params"):
             for name, default in self.params:
                 self._pprint(indent + 2, "( ", "%s -> %s" % (name, default))
+            if hasattr(self, "star") and self.star:
+                name, default = self.star
+                self._pprint(indent + 2, "( ", "%s -> %s" % (name, default))
+            if hasattr(self, "dstar") and self.dstar:
+                name, default = self.dstar
+                self._pprint(indent + 2, "( ", "%s -> %s" % (name, default))
         if getattr(self, "acquire_locals", 0):
             self._pprint(indent + 2, "( ", "acquiring locals")
         if getattr(self, "structure", 0):
@@ -111,10 +140,14 @@
         if hasattr(self, "args"):
             for arg in self.args:
                 arg.pprint(indent + 2, "( ")
+            if hasattr(self, "star") and self.star:
+                self.star.pprint(indent + 2, "( ")
+            if hasattr(self, "dstar") and self.dstar:
+                self.dstar.pprint(indent + 2, "( ")
 
 class Module(Node): "A Python module."
 class Subprogram(Node): "A subprogram: functions, methods and loops."
-class Class(Node): "A Python class."
+class Constant(Node): "A constant."
 class Pass(Node): "A placeholder node corresponding to pass."
 class Invoke(Node): "A function, method or loop invocation."
 class Return(Node): "Return an evaluated expression."
@@ -126,7 +159,6 @@
 class LoadName(Node): "Load a named object."
 class LoadGlobal(Node): "Load a named global object."
 class LoadAttr(Node): "Load an object attribute."
-class LoadConst(Node): "Load a constant."
 class LoadRef(Node): "Load a reference, typically a subprogram."
 class LoadExc(Node): "Load a handled exception."
 class StoreTemp(Node): "Store a temporary value."
@@ -138,24 +170,6 @@
 class Try(Node): "A try...except...else...finally grouping node."
 class Raise(Node): "An exception raising node."
 class Not(Node): "A negation of an expression."
-
-class Visitor(ASTVisitor):
-
-    "A visitor base class."
-
-    def __init__(self):
-        ASTVisitor.__init__(self)
-
-    def default(self, node, *args):
-        raise ValueError, node.__class__
-
-    def dispatch(self, node, *args):
-        return ASTVisitor.dispatch(self, node, *args)
-
-    def dispatches(self, nodes, *args):
-        results = []
-        for node in nodes:
-            results.append(self.dispatch(node, *args))
-        return results
+class Class(Node): "A Python class."
 
 # vim: tabstop=4 expandtab shiftwidth=4
diff -r 929af7341cec -r c9ce39c2076a simplify.py
--- a/simplify.py	Sun Jul 23 23:56:11 2006 +0200
+++ b/simplify.py	Sun Jul 23 23:57:13 2006 +0200
@@ -1,7 +1,9 @@
 #!/usr/bin/env python
 
 """
-Simplify AST structures for easier type propagation and analysis.
+Simplify AST structures for easier type propagation and analysis. The code in
+this module processes AST trees originating from the compiler module and
+produces a result tree consisting of instruction-oriented program nodes.
 
 Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk>
 
@@ -46,7 +48,8 @@
         Visitor.__init__(self)
         self.result = None              # The resulting tree.
         self.subprograms = []           # Subprograms outside the tree.
-        self.structures = []            # Structures/classes
+        self.structures = []            # Structures/classes.
+        self.constants = {}             # Constants.
         self.current_subprograms = []   # Current subprograms being processed.
 
     def process(self, node):
@@ -115,7 +118,9 @@
         return result
 
     def visitConst(self, const):
-        result = LoadConst(const, value=const.value)
+        if not self.constants.has_key(const.value):
+            self.constants[const.value] = Constant(name=repr(const.value), value=const.value)
+        result = LoadRef(ref=self.constants[const.value])
         return result
 
     def visitReturn(self, return_):
@@ -146,16 +151,16 @@
         return result
 
     def visitTuple(self, tuple):
-        return self._visitBuiltin(tuple, "Tuple")
+        return self._visitBuiltin(tuple, "tuple")
 
     def visitList(self, list):
-        return self._visitBuiltin(list, "List")
+        return self._visitBuiltin(list, "list")
 
     def visitDict(self, dict):
-        result = Invoke(dict, expr=LoadName(name="Dict"))
+        result = Invoke(dict, expr=LoadName(name="dict"))
         args = []
         for key, value in dict.items:
-            tuple = Invoke(expr=LoadName(name="Tuple"), star=None, dstar=None)
+            tuple = Invoke(expr=LoadName(name="tuple"), star=None, dstar=None)
             tuple.args = [self.dispatch(key), self.dispatch(value)]
             args.append(tuple)
         result.args = args
@@ -549,7 +554,7 @@
         if len(subs) == 1:
             return self.dispatch(subs[0])
         else:
-            return Invoke(expr=LoadName(name="Tuple"), args=self.dispatches(subs))
+            return Invoke(expr=LoadName(name="tuple"), args=self.dispatches(subs))
 
     def visitSubscript(self, subscript, in_sequence=0):
         value = self._visitAssNameOrAttr(subscript, in_sequence)
@@ -562,7 +567,9 @@
         structure = Class(name=hex(id(class_)), bases=class_.bases)
         self.structures.append(structure)
 
-        subprogram = Subprogram(name=hex(id(class_)), acquire_locals=1, structure=structure, params=[], star=None, dstar=None)
+        # Make a subprogram which initialises the class structure.
+
+        subprogram = Subprogram(name=hex(id(class_)), structure=structure, params=[], star=None, dstar=None)
         self.current_subprograms.append(subprogram)
 
         subprogram.code = self.dispatch(class_.code)
@@ -585,10 +592,17 @@
         else: has_dstar = 0
         ndefaults = len(function.defaults)
         npositional = len(function.argnames) - has_star - has_dstar
-        if has_star: star = function.argnames[npositional]
-        else: star = None
-        if has_dstar: dstar = function.argnames[npositional + has_star]
-        else: dstar = None
+
+        # Produce star and dstar parameters with appropriate defaults.
+
+        if has_star:
+            star = (function.argnames[npositional], Invoke(expr=LoadName(name="list"), args=[], star=None, dstar=None))
+        else:
+            star = None
+        if has_dstar:
+            dstar = (function.argnames[npositional + has_star], Invoke(expr=LoadName(name="dict"), args=[], star=None, dstar=None))
+        else:
+            dstar = None
 
         params = []
         for i in range(0, npositional - ndefaults):