1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/simplified.py Sat Jul 08 21:47:12 2006 +0200
1.3 @@ -0,0 +1,109 @@
1.4 +#!/usr/bin/env python
1.5 +
1.6 +"""
1.7 +Simplified AST nodes for easier type propagation and analysis.
1.8 +
1.9 +Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk>
1.10 +
1.11 +This software is free software; you can redistribute it and/or
1.12 +modify it under the terms of the GNU General Public License as
1.13 +published by the Free Software Foundation; either version 2 of
1.14 +the License, or (at your option) any later version.
1.15 +
1.16 +This software is distributed in the hope that it will be useful,
1.17 +but WITHOUT ANY WARRANTY; without even the implied warranty of
1.18 +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1.19 +GNU General Public License for more details.
1.20 +
1.21 +You should have received a copy of the GNU General Public
1.22 +License along with this library; see the file LICENCE.txt
1.23 +If not, write to the Free Software Foundation, Inc.,
1.24 +51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
1.25 +"""
1.26 +
1.27 +class Node:
1.28 +
1.29 + """
1.30 + A result node with common attributes:
1.31 +
1.32 + original The original node from which this node was created.
1.33 + statements Any underlying statements.
1.34 + expr Any contributing expression.
1.35 + name Any name involved (variable or attribute).
1.36 + code Any code grouped by this node.
1.37 + ref Any reference to (for example) subprograms.
1.38 + """
1.39 +
1.40 + def __init__(self, original=None, **kw):
1.41 + self.original = original
1.42 + for name, value in kw.items():
1.43 + setattr(self, name, value)
1.44 +
1.45 + def __repr__(self):
1.46 + if hasattr(self, "name"):
1.47 + return "%s '%s' (at %x)" % (self.__class__, self.name, id(self))
1.48 + elif hasattr(self, "value"):
1.49 + return "%s %s (at %x)" % (self.__class__, repr(self.value), id(self))
1.50 + elif hasattr(self, "ref"):
1.51 + return "%s '%s' (at %x)" % (self.__class__, self.ref.name, id(self))
1.52 + else:
1.53 + return "%s (at %x)" % (self.__class__, id(self))
1.54 +
1.55 + def _pprint(self, indent, continuation, s):
1.56 + if continuation:
1.57 + print (" " * max(0, indent - len(continuation))) + continuation + s
1.58 + else:
1.59 + print (" " * indent) + s
1.60 +
1.61 + def pprint(self, indent=0, continuation=None):
1.62 + self._pprint(indent, continuation, repr(self))
1.63 +
1.64 + # Show other details.
1.65 +
1.66 + if hasattr(self, "params"):
1.67 + for name, default in self.params:
1.68 + self._pprint(indent + 2, "( ", "%s -> %s" % (name, default))
1.69 + if getattr(self, "acquire_locals", 0):
1.70 + self._pprint(indent + 2, "( ", "acquiring locals")
1.71 + if hasattr(self, "spec"):
1.72 + self.spec.pprint(indent + 2, "E ")
1.73 + if hasattr(self, "test"):
1.74 + self.test.pprint(indent + 2, "? ")
1.75 + for attr in "code", "tests", "body", "handlers", "else_", "finally_":
1.76 + if hasattr(self, attr) and getattr(self, attr):
1.77 + self._pprint(indent, "", "{ (%s)" % attr)
1.78 + for node in getattr(self, attr):
1.79 + node.pprint(indent + 2)
1.80 + self._pprint(indent, "", "}")
1.81 + if hasattr(self, "expr"):
1.82 + self.expr.pprint(indent + 2, "- ")
1.83 + if hasattr(self, "lvalue"):
1.84 + self.lvalue.pprint(indent + 2, "= ")
1.85 + if hasattr(self, "args"):
1.86 + for arg in self.args:
1.87 + arg.pprint(indent + 2, "( ")
1.88 +
1.89 +class Module(Node): "A Python module."
1.90 +class Subprogram(Node): "A subprogram: functions, methods and loops."
1.91 +class Class(Node): "A Python class."
1.92 +class Pass(Node): "A placeholder node corresponding to pass."
1.93 +class Invoke(Node): "A function, method or loop invocation."
1.94 +class Return(Node): "Return an evaluated expression."
1.95 +class Assign(Node): "A grouping node for assignment-related operations."
1.96 +class Keyword(Node): "A grouping node for keyword arguments."
1.97 +class LoadTemp(Node): "Load a previously-stored temporary value."
1.98 +class LoadName(Node): "Load a named object."
1.99 +class LoadAttr(Node): "Load an object attribute."
1.100 +class LoadConst(Node): "Load a constant."
1.101 +class LoadRef(Node): "Load a reference, typically a subprogram."
1.102 +class LoadExc(Node): "Load a handled exception."
1.103 +class StoreTemp(Node): "Store a temporary value."
1.104 +class StoreName(Node): "Associate a name with an object."
1.105 +class StoreAttr(Node): "Associate an object's attribute with a value."
1.106 +class ReleaseTemp(Node): "Release a temporary value."
1.107 +class If(Node): "A multitest conditional node."
1.108 +class Conditional(Node): "A conditional node consisting of a test and outcomes."
1.109 +class Try(Node): "A try...except...else...finally grouping node."
1.110 +class Except(Node): "An exception handler node."
1.111 +
1.112 +# vim: tabstop=4 expandtab shiftwidth=4
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/simplify.py Sat Jul 08 21:47:12 2006 +0200
2.3 @@ -0,0 +1,376 @@
2.4 +#!/usr/bin/env python
2.5 +
2.6 +"""
2.7 +Simplify AST structures for easier type propagation and analysis.
2.8 +
2.9 +Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk>
2.10 +
2.11 +This software is free software; you can redistribute it and/or
2.12 +modify it under the terms of the GNU General Public License as
2.13 +published by the Free Software Foundation; either version 2 of
2.14 +the License, or (at your option) any later version.
2.15 +
2.16 +This software is distributed in the hope that it will be useful,
2.17 +but WITHOUT ANY WARRANTY; without even the implied warranty of
2.18 +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2.19 +GNU General Public License for more details.
2.20 +
2.21 +You should have received a copy of the GNU General Public
2.22 +License along with this library; see the file LICENCE.txt
2.23 +If not, write to the Free Software Foundation, Inc.,
2.24 +51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
2.25 +"""
2.26 +
2.27 +from compiler.visitor import ASTVisitor
2.28 +import compiler.ast
2.29 +from simplified import *
2.30 +
2.31 +class Simplifier(ASTVisitor):
2.32 +
2.33 + """
2.34 + A simplifying visitor for AST nodes.
2.35 +
2.36 + Covered: AssAttr, AssList, AssName, AssTuple, Assign, Break, CallFunc, Class,
2.37 + Const, Continue, Dict, Discard, For, Function, Getattr, If, Keyword, Lambda,
2.38 + List, Module, Name, Pass, Return, Stmt, TryExcept, TryFinally, Tuple,
2.39 + While.
2.40 +
2.41 + Missing: Add, And, Assert, AugAssign, Backquote, Bitand, Bitor, Bitxor,
2.42 + Compare, Decorators, Div, Ellipsis, Exec,
2.43 + FloorDiv, From, Global, Import, Invert, LeftShift,
2.44 + ListComp, ListCompFor, ListCompIf, Mod, Mul, Not, Or, Power,
2.45 + Print, Printnl, Raise, RightShift, Slice, Sliceobj, Sub,
2.46 + Subscript, UnaryAdd, UnarySub, Yield.
2.47 + """
2.48 +
2.49 + def __init__(self):
2.50 + ASTVisitor.__init__(self)
2.51 + self.result = None
2.52 + self.subprograms = []
2.53 + self.current_subprograms = []
2.54 +
2.55 + # Generic visitor methods.
2.56 +
2.57 + def default(self, node, *args):
2.58 + raise ValueError, node.__class__
2.59 +
2.60 + def dispatch(self, node, *args):
2.61 + return ASTVisitor.dispatch(self, node, *args)
2.62 +
2.63 + def dispatches(self, nodes, *args):
2.64 + results = []
2.65 + for node in nodes:
2.66 + results.append(self.dispatch(node, *args))
2.67 + return results
2.68 +
2.69 + # Placeholder or deletion transformations.
2.70 +
2.71 + def visitStmt(self, stmt):
2.72 + return self.dispatches(stmt.nodes)
2.73 +
2.74 + def visitPass(self, pass_):
2.75 + return Pass(pass_)
2.76 +
2.77 + def visitDiscard(self, discard):
2.78 + return self.dispatch(discard.expr)
2.79 +
2.80 + # Relatively trivial transformations.
2.81 +
2.82 + def visitModule(self, module):
2.83 + self.result = Module(module)
2.84 + self.result.code = self.dispatch(module.node)
2.85 + return self.result
2.86 +
2.87 + def visitClass(self, class_):
2.88 + result = Class(class_, name=class_.name, bases=class_.bases)
2.89 + result.code = self.dispatch(class_.code)
2.90 + return result
2.91 +
2.92 + def visitGetattr(self, getattr):
2.93 + result = LoadAttr(getattr, name=getattr.attrname)
2.94 + result.expr = self.dispatch(getattr.expr)
2.95 + return result
2.96 +
2.97 + def visitKeyword(self, keyword):
2.98 + result = Keyword(keyword, name=keyword.name)
2.99 + result.expr = self.dispatch(keyword.expr)
2.100 + return result
2.101 +
2.102 + def visitName(self, name):
2.103 + result = LoadName(name, name=name.name)
2.104 + return result
2.105 +
2.106 + def visitConst(self, const):
2.107 + result = LoadConst(const, value=const.value)
2.108 + return result
2.109 +
2.110 + def visitReturn(self, return_):
2.111 + result = Return(return_)
2.112 + result.expr = self.dispatch(return_.value)
2.113 + return result
2.114 +
2.115 + def visitBreak(self, break_):
2.116 + result = Return(break_)
2.117 + return result
2.118 +
2.119 + def visitContinue(self, continue_):
2.120 + result = Invoke(same_frame=1, star=None, dstar=None, args=[])
2.121 + result.expr = LoadRef(ref=self.current_subprograms[-1])
2.122 + return result
2.123 +
2.124 + def visitIf(self, if_):
2.125 + result = If(if_, else_=[])
2.126 + tests = []
2.127 + for compare, stmt in if_.tests:
2.128 + test = Conditional(else_=[], test=Invoke(
2.129 + expr=LoadAttr(expr=self.dispatch(compare), name="__true__"),
2.130 + params=[], star=None, dstar=None))
2.131 + test.body = self.dispatch(stmt)
2.132 + tests.append(test)
2.133 + result.tests = tests
2.134 + if if_.else_ is not None:
2.135 + result.else_ = self.dispatch(if_.else_)
2.136 + return result
2.137 +
2.138 + def _visitBuiltin(self, builtin, name):
2.139 + result = Invoke(expr=LoadName(name=name))
2.140 + args = []
2.141 + for node in builtin.nodes:
2.142 + args.append(self.dispatch(node))
2.143 + result.args = args
2.144 + return result
2.145 +
2.146 + def visitTuple(self, tuple):
2.147 + return self._visitBuiltin(tuple, "Tuple")
2.148 +
2.149 + def visitList(self, list):
2.150 + return self._visitBuiltin(list, "List")
2.151 +
2.152 + def visitDict(self, dict):
2.153 + result = Invoke(expr=LoadName(name="Dict"))
2.154 + args = []
2.155 + for key, value in dict.items:
2.156 + tuple = Invoke(expr=LoadName(name="Tuple"), star=None, dstar=None)
2.157 + tuple.args = [self.dispatch(key), self.dispatch(value)]
2.158 + args.append(tuple)
2.159 + result.args = args
2.160 + return result
2.161 +
2.162 + # Assignments.
2.163 +
2.164 + def visitAssign(self, assign):
2.165 + result = Assign(assign)
2.166 + store = StoreTemp(expr=self.dispatch(assign.expr))
2.167 + release = ReleaseTemp()
2.168 + result.code = [store] + self.dispatches(assign.nodes, 0) + [release]
2.169 + return result
2.170 +
2.171 + def visitAssList(self, asslist, in_sequence=0):
2.172 + if not in_sequence:
2.173 + expr = LoadTemp(asslist)
2.174 + else:
2.175 + expr = Invoke(asslist, expr=LoadAttr(expr=LoadTemp(), name="next"))
2.176 + result = Assign(asslist)
2.177 + store = StoreTemp(expr=Invoke(expr=LoadAttr(name="__iter__", expr=expr)))
2.178 + release = ReleaseTemp()
2.179 + result.code = [store] + self.dispatches(asslist.nodes, 1) + [release]
2.180 + return result
2.181 +
2.182 + visitAssTuple = visitAssList
2.183 +
2.184 + def _visitAssNameOrAttr(self, node, in_sequence):
2.185 + if not in_sequence:
2.186 + return LoadTemp(node)
2.187 + else:
2.188 + return Invoke(node, expr=LoadAttr(expr=LoadTemp(), name="next"))
2.189 +
2.190 + def visitAssName(self, assname, in_sequence=0):
2.191 + expr = self._visitAssNameOrAttr(assname, in_sequence)
2.192 + result = StoreName(assname, name=assname.name, expr=expr)
2.193 + return result
2.194 +
2.195 + def visitAssAttr(self, assattr, in_sequence=0):
2.196 + expr = self._visitAssNameOrAttr(assattr, in_sequence)
2.197 + lvalue = self.dispatch(assattr.expr)
2.198 + result = StoreAttr(assattr, name=assattr.attrname, lvalue=lvalue, expr=expr)
2.199 + return result
2.200 +
2.201 + # Invocation and subprogram transformations.
2.202 +
2.203 + def _visitFunction(self, function, subprogram):
2.204 + if function.flags & 4 != 0: has_star = 1
2.205 + else: has_star = 0
2.206 + if function.flags & 8 != 0: has_dstar = 1
2.207 + else: has_dstar = 0
2.208 + ndefaults = len(function.defaults)
2.209 + npositional = len(function.argnames) - has_star - has_dstar
2.210 + if has_star: star = function.argnames[npositional]
2.211 + else: star = None
2.212 + if has_dstar: dstar = function.argnames[npositional + has_star]
2.213 + else: dstar = None
2.214 +
2.215 + params = []
2.216 + for i in range(0, npositional - ndefaults):
2.217 + params.append((function.argnames[i], None))
2.218 +
2.219 + # NOTE: Fix/process defaults.
2.220 +
2.221 + for i in range(0, ndefaults):
2.222 + default = function.defaults[i]
2.223 + if default is not None:
2.224 + params.append((function.argnames[npositional - ndefaults + i], self.dispatch(default)))
2.225 + else:
2.226 + params.append((function.argnames[npositional - ndefaults + i], default))
2.227 +
2.228 + subprogram.params = params
2.229 + subprogram.star = star
2.230 + subprogram.dstar = dstar
2.231 + self.subprograms.append(subprogram)
2.232 +
2.233 + def visitFunction(self, function):
2.234 +
2.235 + # Make a subprogram for the function and record it outside the main
2.236 + # tree.
2.237 +
2.238 + subprogram = Subprogram(function, name=function.name, star=None, dstar=None)
2.239 + self.current_subprograms.append(subprogram)
2.240 + subprogram.code = self.dispatch(function.code)
2.241 + self.current_subprograms.pop()
2.242 + self._visitFunction(function, subprogram)
2.243 +
2.244 + # Make a definition of the function associating it with a name.
2.245 +
2.246 + result = Assign(function)
2.247 + load = LoadRef(ref=subprogram)
2.248 + store = StoreName(name=function.name)
2.249 + result.code = [load, store]
2.250 + return result
2.251 +
2.252 + def visitLambda(self, lambda_):
2.253 +
2.254 + # Make a subprogram for the function and record it outside the main
2.255 + # tree.
2.256 +
2.257 + subprogram = Subprogram(lambda_, name=hex(id(lambda_)), star=None, dstar=None)
2.258 + self.current_subprograms.append(subprogram)
2.259 + subprogram.code = [Return(expr=self.dispatch(lambda_.code))]
2.260 + self.current_subprograms.pop()
2.261 + self._visitFunction(lambda_, subprogram)
2.262 +
2.263 + # Get the subprogram reference to the lambda.
2.264 +
2.265 + return LoadRef(ref=subprogram)
2.266 +
2.267 + def visitCallFunc(self, callfunc):
2.268 + result = Invoke(callfunc, same_frame=0, star=None, dstar=None)
2.269 + result.args = self.dispatches(callfunc.args)
2.270 + if callfunc.star_args is not None:
2.271 + result.star = self.dispatch(callfunc.star_args)
2.272 + if callfunc.dstar_args is not None:
2.273 + result.dstar = self.dispatch(callfunc.dstar_args)
2.274 + result.expr = self.dispatch(callfunc.node)
2.275 + return result
2.276 +
2.277 + def visitWhile(self, while_):
2.278 +
2.279 + # Make a subprogram for the block and record it outside the main tree.
2.280 +
2.281 + subprogram = Subprogram(while_, name=hex(id(while_)), acquire_locals=1, params=[], star=None, dstar=None)
2.282 + self.current_subprograms.append(subprogram)
2.283 +
2.284 + # Include a conditional statement in the subprogram.
2.285 +
2.286 + test = Conditional(else_=[])
2.287 + test.test = Invoke(expr=LoadAttr(expr=self.dispatch(while_.test), name="__true__"),
2.288 + params=[], star=None, dstar=None)
2.289 +
2.290 + # Inside the conditional, add a recursive invocation to the subprogram
2.291 + # if the test condition was satisfied.
2.292 +
2.293 + continuation = Invoke(same_frame=1, star=None, dstar=None, args=[])
2.294 + continuation.expr = LoadRef(ref=subprogram)
2.295 + test.body = self.dispatch(while_.body) + [continuation]
2.296 + if while_.else_ is not None:
2.297 + test.else_ = self.dispatch(while_.else_)
2.298 + subprogram.code = [test]
2.299 +
2.300 + self.current_subprograms.pop()
2.301 + self.subprograms.append(subprogram)
2.302 +
2.303 + # Make an invocation of the subprogram.
2.304 +
2.305 + result = Invoke(while_, same_frame=1, star=None, dstar=None, args=[])
2.306 + result.expr = LoadRef(ref=subprogram)
2.307 + return result
2.308 +
2.309 + def visitFor(self, for_):
2.310 +
2.311 + # Make a subprogram for the block and record it outside the main tree.
2.312 +
2.313 + subprogram = Subprogram(for_, name=hex(id(for_)), acquire_locals=1, params=[], star=None, dstar=None)
2.314 + self.current_subprograms.append(subprogram)
2.315 +
2.316 + # Wrap the assignment in a try...except statement.
2.317 +
2.318 + try_except = Try(body=[], handlers=[], else_=[], finally_=[])
2.319 + except_spec = Invoke(expr=LoadName(name="Tuple"), params=[LoadName(name="StopIteration")])
2.320 + stopiteration = Except(spec=except_spec)
2.321 + stopiteration.code = self.dispatch(for_.else_)
2.322 + try_except.handlers = [stopiteration]
2.323 +
2.324 + assign = Assign()
2.325 + assign.code = [
2.326 + StoreTemp(expr=Invoke(expr=LoadAttr(expr=LoadTemp(), name="next"))),
2.327 + self.dispatch(for_.assign),
2.328 + ReleaseTemp()
2.329 + ]
2.330 +
2.331 + # Inside the conditional, add a recursive invocation to the subprogram
2.332 + # if the test condition was satisfied.
2.333 +
2.334 + continuation = Invoke(same_frame=1, star=None, dstar=None, args=[])
2.335 + continuation.expr = LoadRef(ref=subprogram)
2.336 + try_except.body = [assign] + self.dispatch(for_.body) + [continuation]
2.337 + subprogram.code = [try_except]
2.338 +
2.339 + self.subprograms.append(subprogram)
2.340 + self.current_subprograms.pop()
2.341 +
2.342 + # Obtain an iterator for the sequence involved.
2.343 + # Then, make an invocation of the subprogram.
2.344 +
2.345 + result = Assign(for_)
2.346 + result.code = [
2.347 + StoreTemp(expr=Invoke(expr=LoadAttr(name="__iter__", expr=self.dispatch(for_.list)))),
2.348 + Invoke(expr=LoadRef(ref=subprogram), same_frame=1, star=None, dstar=None, args=[]),
2.349 + ReleaseTemp()
2.350 + ]
2.351 + return result
2.352 +
2.353 + # Exception node transformations.
2.354 +
2.355 + def visitTryExcept(self, tryexcept):
2.356 + result = Try(tryexcept, body=[], handlers=[], else_=[], finally_=[])
2.357 + if tryexcept.body is not None:
2.358 + result.body = self.dispatch(tryexcept.body)
2.359 + if tryexcept.else_ is not None:
2.360 + result.else_ = self.dispatch(tryexcept.else_)
2.361 + handlers = []
2.362 + for spec, assign, stmt in tryexcept.handlers:
2.363 + get_exc = Assign()
2.364 + get_exc.code = [StoreTemp(expr=LoadExc()), self.dispatch(assign), ReleaseTemp()]
2.365 + handler = Except(spec=self.dispatch(spec))
2.366 + handler.code = [get_exc] + self.dispatch(stmt)
2.367 + handlers.append(handler)
2.368 + result.handlers = handlers
2.369 + return result
2.370 +
2.371 + def visitTryFinally(self, tryfinally):
2.372 + result = Try(tryfinally, body=[], handlers=[], else_=[], finally_=[])
2.373 + if tryfinally.body is not None:
2.374 + result.body = self.dispatch(tryfinally.body)
2.375 + if tryfinally.final is not None:
2.376 + result.finally_ = self.dispatch(tryfinally.final)
2.377 + return result
2.378 +
2.379 +# vim: tabstop=4 expandtab shiftwidth=4