# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1152388032 -7200
# Node ID 1eb049d8af395774a5b50f3df0c4b128ba7fbc05

A simplified AST processor.


diff -r 000000000000 -r 1eb049d8af39 simplified.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/simplified.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,109 @@
+#!/usr/bin/env python
+
+"""
+Simplified AST nodes for easier type propagation and analysis.
+
+Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk>
+
+This software is free software; you can redistribute it and/or
+modify it under the terms of the GNU General Public License as
+published by the Free Software Foundation; either version 2 of
+the License, or (at your option) any later version.
+
+This software is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public
+License along with this library; see the file LICENCE.txt
+If not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+"""
+
+class Node:
+
+    """
+    A result node with common attributes:
+
+    original    The original node from which this node was created.
+    statements  Any underlying statements.
+    expr        Any contributing expression.
+    name        Any name involved (variable or attribute).
+    code        Any code grouped by this node.
+    ref         Any reference to (for example) subprograms.
+    """
+
+    def __init__(self, original=None, **kw):
+        self.original = original
+        for name, value in kw.items():
+            setattr(self, name, value)
+
+    def __repr__(self):
+        if hasattr(self, "name"):
+            return "%s '%s' (at %x)" % (self.__class__, self.name, id(self))
+        elif hasattr(self, "value"):
+            return "%s %s (at %x)" % (self.__class__, repr(self.value), id(self))
+        elif hasattr(self, "ref"):
+            return "%s '%s' (at %x)" % (self.__class__, self.ref.name, id(self))
+        else:
+            return "%s (at %x)" % (self.__class__, id(self))
+
+    def _pprint(self, indent, continuation, s):
+        if continuation:
+            print (" " * max(0, indent - len(continuation))) + continuation + s
+        else:
+            print (" " * indent) + s
+
+    def pprint(self, indent=0, continuation=None):
+        self._pprint(indent, continuation, repr(self))
+
+        # Show other details.
+
+        if hasattr(self, "params"):
+            for name, default in self.params:
+                self._pprint(indent + 2, "( ", "%s -> %s" % (name, default))
+        if getattr(self, "acquire_locals", 0):
+            self._pprint(indent + 2, "( ", "acquiring locals")
+        if hasattr(self, "spec"):
+            self.spec.pprint(indent + 2, "E ")
+        if hasattr(self, "test"):
+            self.test.pprint(indent + 2, "? ")
+        for attr in "code", "tests", "body", "handlers", "else_", "finally_":
+            if hasattr(self, attr) and getattr(self, attr):
+                self._pprint(indent, "", "{ (%s)" % attr)
+                for node in getattr(self, attr):
+                    node.pprint(indent + 2)
+                self._pprint(indent, "", "}")
+        if hasattr(self, "expr"):
+            self.expr.pprint(indent + 2, "- ")
+        if hasattr(self, "lvalue"):
+            self.lvalue.pprint(indent + 2, "= ")
+        if hasattr(self, "args"):
+            for arg in self.args:
+                arg.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 Pass(Node): "A placeholder node corresponding to pass."
+class Invoke(Node): "A function, method or loop invocation."
+class Return(Node): "Return an evaluated expression."
+class Assign(Node): "A grouping node for assignment-related operations."
+class Keyword(Node): "A grouping node for keyword arguments."
+class LoadTemp(Node): "Load a previously-stored temporary value."
+class LoadName(Node): "Load a named 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."
+class StoreName(Node): "Associate a name with an object."
+class StoreAttr(Node): "Associate an object's attribute with a value."
+class ReleaseTemp(Node): "Release a temporary value."
+class If(Node): "A multitest conditional node."
+class Conditional(Node): "A conditional node consisting of a test and outcomes."
+class Try(Node): "A try...except...else...finally grouping node."
+class Except(Node): "An exception handler node."
+
+# vim: tabstop=4 expandtab shiftwidth=4
diff -r 000000000000 -r 1eb049d8af39 simplify.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/simplify.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,376 @@
+#!/usr/bin/env python
+
+"""
+Simplify AST structures for easier type propagation and analysis.
+
+Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk>
+
+This software is free software; you can redistribute it and/or
+modify it under the terms of the GNU General Public License as
+published by the Free Software Foundation; either version 2 of
+the License, or (at your option) any later version.
+
+This software is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public
+License along with this library; see the file LICENCE.txt
+If not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+"""
+
+from compiler.visitor import ASTVisitor
+import compiler.ast
+from simplified import *
+
+class Simplifier(ASTVisitor):
+
+    """
+    A simplifying visitor for AST nodes.
+
+    Covered: AssAttr, AssList, AssName, AssTuple, Assign, Break, CallFunc, Class,
+             Const, Continue, Dict, Discard, For, Function, Getattr, If, Keyword, Lambda,
+             List, Module, Name, Pass, Return, Stmt, TryExcept, TryFinally, Tuple,
+             While.
+
+    Missing: Add, And, Assert, AugAssign, Backquote, Bitand, Bitor, Bitxor,
+             Compare, Decorators, Div, Ellipsis, Exec,
+             FloorDiv, From, Global, Import, Invert, LeftShift,
+             ListComp, ListCompFor, ListCompIf, Mod, Mul, Not, Or, Power,
+             Print, Printnl, Raise, RightShift, Slice, Sliceobj, Sub,
+             Subscript, UnaryAdd, UnarySub, Yield.
+    """
+
+    def __init__(self):
+        ASTVisitor.__init__(self)
+        self.result = None
+        self.subprograms = []
+        self.current_subprograms = []
+
+    # Generic visitor methods.
+
+    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
+
+    # Placeholder or deletion transformations.
+
+    def visitStmt(self, stmt):
+        return self.dispatches(stmt.nodes)
+
+    def visitPass(self, pass_):
+        return Pass(pass_)
+
+    def visitDiscard(self, discard):
+        return self.dispatch(discard.expr)
+
+    # Relatively trivial transformations.
+
+    def visitModule(self, module):
+        self.result = Module(module)
+        self.result.code = self.dispatch(module.node)
+        return self.result
+
+    def visitClass(self, class_):
+        result = Class(class_, name=class_.name, bases=class_.bases)
+        result.code = self.dispatch(class_.code)
+        return result
+
+    def visitGetattr(self, getattr):
+        result = LoadAttr(getattr, name=getattr.attrname)
+        result.expr = self.dispatch(getattr.expr)
+        return result
+
+    def visitKeyword(self, keyword):
+        result = Keyword(keyword, name=keyword.name)
+        result.expr = self.dispatch(keyword.expr)
+        return result
+
+    def visitName(self, name):
+        result = LoadName(name, name=name.name)
+        return result
+
+    def visitConst(self, const):
+        result = LoadConst(const, value=const.value)
+        return result
+
+    def visitReturn(self, return_):
+        result = Return(return_)
+        result.expr = self.dispatch(return_.value)
+        return result
+
+    def visitBreak(self, break_):
+        result = Return(break_)
+        return result
+
+    def visitContinue(self, continue_):
+        result = Invoke(same_frame=1, star=None, dstar=None, args=[])
+        result.expr = LoadRef(ref=self.current_subprograms[-1])
+        return result
+
+    def visitIf(self, if_):
+        result = If(if_, else_=[])
+        tests = []
+        for compare, stmt in if_.tests:
+            test = Conditional(else_=[], test=Invoke(
+                expr=LoadAttr(expr=self.dispatch(compare), name="__true__"),
+                params=[], star=None, dstar=None))
+            test.body = self.dispatch(stmt)
+            tests.append(test)
+        result.tests = tests
+        if if_.else_ is not None:
+            result.else_ = self.dispatch(if_.else_)
+        return result
+
+    def _visitBuiltin(self, builtin, name):
+        result = Invoke(expr=LoadName(name=name))
+        args = []
+        for node in builtin.nodes:
+            args.append(self.dispatch(node))
+        result.args = args
+        return result
+
+    def visitTuple(self, tuple):
+        return self._visitBuiltin(tuple, "Tuple")
+
+    def visitList(self, list):
+        return self._visitBuiltin(list, "List")
+
+    def visitDict(self, dict):
+        result = Invoke(expr=LoadName(name="Dict"))
+        args = []
+        for key, value in dict.items:
+            tuple = Invoke(expr=LoadName(name="Tuple"), star=None, dstar=None)
+            tuple.args = [self.dispatch(key), self.dispatch(value)]
+            args.append(tuple)
+        result.args = args
+        return result
+
+    # Assignments.
+
+    def visitAssign(self, assign):
+        result = Assign(assign)
+        store = StoreTemp(expr=self.dispatch(assign.expr))
+        release = ReleaseTemp()
+        result.code = [store] + self.dispatches(assign.nodes, 0) + [release]
+        return result
+
+    def visitAssList(self, asslist, in_sequence=0):
+        if not in_sequence:
+            expr = LoadTemp(asslist)
+        else:
+            expr = Invoke(asslist, expr=LoadAttr(expr=LoadTemp(), name="next"))
+        result = Assign(asslist)
+        store = StoreTemp(expr=Invoke(expr=LoadAttr(name="__iter__", expr=expr)))
+        release = ReleaseTemp()
+        result.code = [store] + self.dispatches(asslist.nodes, 1) + [release]
+        return result
+
+    visitAssTuple = visitAssList
+
+    def _visitAssNameOrAttr(self, node, in_sequence):
+        if not in_sequence:
+            return LoadTemp(node)
+        else:
+            return Invoke(node, expr=LoadAttr(expr=LoadTemp(), name="next"))
+
+    def visitAssName(self, assname, in_sequence=0):
+        expr = self._visitAssNameOrAttr(assname, in_sequence)
+        result = StoreName(assname, name=assname.name, expr=expr)
+        return result
+
+    def visitAssAttr(self, assattr, in_sequence=0):
+        expr = self._visitAssNameOrAttr(assattr, in_sequence)
+        lvalue = self.dispatch(assattr.expr)
+        result = StoreAttr(assattr, name=assattr.attrname, lvalue=lvalue, expr=expr)
+        return result
+
+    # Invocation and subprogram transformations.
+
+    def _visitFunction(self, function, subprogram):
+        if function.flags & 4 != 0: has_star = 1
+        else: has_star = 0
+        if function.flags & 8 != 0: has_dstar = 1
+        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
+
+        params = []
+        for i in range(0, npositional - ndefaults):
+            params.append((function.argnames[i], None))
+
+        # NOTE: Fix/process defaults.
+
+        for i in range(0, ndefaults):
+            default = function.defaults[i]
+            if default is not None:
+                params.append((function.argnames[npositional - ndefaults + i], self.dispatch(default)))
+            else:
+                params.append((function.argnames[npositional - ndefaults + i], default))
+
+        subprogram.params = params
+        subprogram.star = star
+        subprogram.dstar = dstar
+        self.subprograms.append(subprogram)
+
+    def visitFunction(self, function):
+
+        # Make a subprogram for the function and record it outside the main
+        # tree.
+
+        subprogram = Subprogram(function, name=function.name, star=None, dstar=None)
+        self.current_subprograms.append(subprogram)
+        subprogram.code = self.dispatch(function.code)
+        self.current_subprograms.pop()
+        self._visitFunction(function, subprogram)
+
+        # Make a definition of the function associating it with a name.
+
+        result = Assign(function)
+        load = LoadRef(ref=subprogram)
+        store = StoreName(name=function.name)
+        result.code = [load, store]
+        return result
+
+    def visitLambda(self, lambda_):
+
+        # Make a subprogram for the function and record it outside the main
+        # tree.
+
+        subprogram = Subprogram(lambda_, name=hex(id(lambda_)), star=None, dstar=None)
+        self.current_subprograms.append(subprogram)
+        subprogram.code = [Return(expr=self.dispatch(lambda_.code))]
+        self.current_subprograms.pop()
+        self._visitFunction(lambda_, subprogram)
+
+        # Get the subprogram reference to the lambda.
+
+        return LoadRef(ref=subprogram)
+
+    def visitCallFunc(self, callfunc):
+        result = Invoke(callfunc, same_frame=0, star=None, dstar=None)
+        result.args = self.dispatches(callfunc.args)
+        if callfunc.star_args is not None:
+            result.star = self.dispatch(callfunc.star_args)
+        if callfunc.dstar_args is not None:
+            result.dstar = self.dispatch(callfunc.dstar_args)
+        result.expr = self.dispatch(callfunc.node)
+        return result
+
+    def visitWhile(self, while_):
+
+        # Make a subprogram for the block and record it outside the main tree.
+
+        subprogram = Subprogram(while_, name=hex(id(while_)), acquire_locals=1, params=[], star=None, dstar=None)
+        self.current_subprograms.append(subprogram)
+
+        # Include a conditional statement in the subprogram.
+
+        test = Conditional(else_=[])
+        test.test = Invoke(expr=LoadAttr(expr=self.dispatch(while_.test), name="__true__"),
+            params=[], star=None, dstar=None)
+
+        # Inside the conditional, add a recursive invocation to the subprogram
+        # if the test condition was satisfied.
+
+        continuation = Invoke(same_frame=1, star=None, dstar=None, args=[])
+        continuation.expr = LoadRef(ref=subprogram)
+        test.body = self.dispatch(while_.body) + [continuation]
+        if while_.else_ is not None:
+            test.else_ = self.dispatch(while_.else_)
+        subprogram.code = [test]
+
+        self.current_subprograms.pop()
+        self.subprograms.append(subprogram)
+
+        # Make an invocation of the subprogram.
+
+        result = Invoke(while_, same_frame=1, star=None, dstar=None, args=[])
+        result.expr = LoadRef(ref=subprogram)
+        return result
+
+    def visitFor(self, for_):
+
+        # Make a subprogram for the block and record it outside the main tree.
+
+        subprogram = Subprogram(for_, name=hex(id(for_)), acquire_locals=1, params=[], star=None, dstar=None)
+        self.current_subprograms.append(subprogram)
+
+        # Wrap the assignment in a try...except statement.
+
+        try_except = Try(body=[], handlers=[], else_=[], finally_=[])
+        except_spec = Invoke(expr=LoadName(name="Tuple"), params=[LoadName(name="StopIteration")])
+        stopiteration = Except(spec=except_spec)
+        stopiteration.code = self.dispatch(for_.else_)
+        try_except.handlers = [stopiteration]
+
+        assign = Assign()
+        assign.code = [
+            StoreTemp(expr=Invoke(expr=LoadAttr(expr=LoadTemp(), name="next"))),
+            self.dispatch(for_.assign),
+            ReleaseTemp()
+            ]
+
+        # Inside the conditional, add a recursive invocation to the subprogram
+        # if the test condition was satisfied.
+
+        continuation = Invoke(same_frame=1, star=None, dstar=None, args=[])
+        continuation.expr = LoadRef(ref=subprogram)
+        try_except.body = [assign] + self.dispatch(for_.body) + [continuation]
+        subprogram.code = [try_except]
+
+        self.subprograms.append(subprogram)
+        self.current_subprograms.pop()
+
+        # Obtain an iterator for the sequence involved.
+        # Then, make an invocation of the subprogram.
+
+        result = Assign(for_)
+        result.code = [
+            StoreTemp(expr=Invoke(expr=LoadAttr(name="__iter__", expr=self.dispatch(for_.list)))),
+            Invoke(expr=LoadRef(ref=subprogram), same_frame=1, star=None, dstar=None, args=[]),
+            ReleaseTemp()
+            ]
+        return result
+
+    # Exception node transformations.
+
+    def visitTryExcept(self, tryexcept):
+        result = Try(tryexcept, body=[], handlers=[], else_=[], finally_=[])
+        if tryexcept.body is not None:
+            result.body = self.dispatch(tryexcept.body)
+        if tryexcept.else_ is not None:
+            result.else_ = self.dispatch(tryexcept.else_)
+        handlers = []
+        for spec, assign, stmt in tryexcept.handlers:
+            get_exc = Assign()
+            get_exc.code = [StoreTemp(expr=LoadExc()), self.dispatch(assign), ReleaseTemp()]
+            handler = Except(spec=self.dispatch(spec))
+            handler.code = [get_exc] + self.dispatch(stmt)
+            handlers.append(handler)
+        result.handlers = handlers
+        return result
+
+    def visitTryFinally(self, tryfinally):
+        result = Try(tryfinally, body=[], handlers=[], else_=[], finally_=[])
+        if tryfinally.body is not None:
+            result.body = self.dispatch(tryfinally.body)
+        if tryfinally.final is not None:
+            result.finally_ = self.dispatch(tryfinally.final)
+        return result
+
+# vim: tabstop=4 expandtab shiftwidth=4
diff -r 000000000000 -r 1eb049d8af39 test.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,4 @@
+import simplify, compiler, sys
+visitor = simplify.Simplifier()
+m = compiler.parseFile(sys.argv[1])
+v = compiler.walk(m, visitor, visitor)
diff -r 000000000000 -r 1eb049d8af39 tests/break.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/break.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,3 @@
+while 1:
+    if x:
+        break
diff -r 000000000000 -r 1eb049d8af39 tests/continue.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/continue.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,4 @@
+while 1:
+    if x:
+        continue
+    x = y
diff -r 000000000000 -r 1eb049d8af39 tests/dict.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/dict.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,1 @@
+x = {1:2, 3:4}
diff -r 000000000000 -r 1eb049d8af39 tests/for.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/for.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,7 @@
+for a, b in range(c, d):
+    for i in range(a, b):
+        x = i
+    else:
+        x = y
+else:
+    a = b
diff -r 000000000000 -r 1eb049d8af39 tests/if.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/if.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,6 @@
+if a:
+    x = 1
+elif b:
+    x = 2
+else:
+    x = 3
diff -r 000000000000 -r 1eb049d8af39 tests/lambda.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/lambda.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,1 @@
+map(lambda x: x.y(), l)
diff -r 000000000000 -r 1eb049d8af39 tests/list.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/list.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,1 @@
+x = [1, 2, a]
diff -r 000000000000 -r 1eb049d8af39 tests/original.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/original.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,10 @@
+class A:
+    x = 123
+    def m(self, x):
+        self.x = x
+def f(a, b, c=2, *d, **e):
+    return g(a, b, c=2, *d, **e)
+a = A()
+b = a.x = c
+[a, b, c] = l
+a, b, c = l
diff -r 000000000000 -r 1eb049d8af39 tests/tryexcept.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/tryexcept.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,6 @@
+try:
+    x = y
+except A, e:
+    a = b
+except (B, C), f:
+    a = c
diff -r 000000000000 -r 1eb049d8af39 tests/tryfinally.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/tryfinally.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,4 @@
+try:
+    x.y()
+finally:
+    y.x()
diff -r 000000000000 -r 1eb049d8af39 tests/while.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/while.py	Sat Jul 08 21:47:12 2006 +0200
@@ -0,0 +1,7 @@
+while a:
+    while x:
+        x = y.m()
+    else:
+        x = y.n()
+else:
+    a = b