1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/simplified/program.py Fri Apr 06 00:53:18 2007 +0200
1.3 @@ -0,0 +1,407 @@
1.4 +#!/usr/bin/env python
1.5 +
1.6 +"""
1.7 +Simplified program nodes for easier type propagation and analysis. This module
1.8 +contains nodes representing program instructions or operations, program
1.9 +structure or organisation, and abstract program data.
1.10 +
1.11 +Copyright (C) 2006, 2007 Paul Boddie <paul@boddie.org.uk>
1.12 +
1.13 +This software is free software; you can redistribute it and/or
1.14 +modify it under the terms of the GNU General Public License as
1.15 +published by the Free Software Foundation; either version 2 of
1.16 +the License, or (at your option) any later version.
1.17 +
1.18 +This software is distributed in the hope that it will be useful,
1.19 +but WITHOUT ANY WARRANTY; without even the implied warranty of
1.20 +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1.21 +GNU General Public License for more details.
1.22 +
1.23 +You should have received a copy of the GNU General Public
1.24 +License along with this library; see the file LICENCE.txt
1.25 +If not, write to the Free Software Foundation, Inc.,
1.26 +51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
1.27 +"""
1.28 +
1.29 +from simplified.utils import Structure, WithName, name
1.30 +import sys
1.31 +
1.32 +# Simplified program nodes.
1.33 +
1.34 +class Node:
1.35 +
1.36 + """
1.37 + A result node with common attributes:
1.38 +
1.39 + original The original node from which this node was created.
1.40 + defining Whether the node defines something in the original program.
1.41 + name Any name involved (variable or attribute).
1.42 + index Any index involved (temporary variable name).
1.43 + value Any constant value.
1.44 + ref Any reference to (for example) subprograms.
1.45 + nstype Any indication of the namespace type involved in a name access.
1.46 +
1.47 + Expression-related attributes:
1.48 +
1.49 + expr Any contributing expression.
1.50 + lvalue Any target expression.
1.51 + test Any test expression in a conditional instruction.
1.52 +
1.53 + Invocation and subprogram attributes:
1.54 +
1.55 + args Any collection of argument nodes.
1.56 + params Any collection of parameter nodes and defaults.
1.57 +
1.58 + Statement-grouping attributes:
1.59 +
1.60 + body Any conditional code depending on the success of a test.
1.61 + else_ Any conditional code depending on the failure of a test.
1.62 + handler Any exception handler code.
1.63 + finally_ Any code which will be executed regardless.
1.64 + code Any unconditional code.
1.65 + choices Any choices which may be included in the final program.
1.66 + """
1.67 +
1.68 + common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original"
1.69 + expression_attributes = "expr", "lvalue", "test"
1.70 + argument_attributes = "star", "dstar"
1.71 + invocation_attributes = "params", # not "args" - see "pos_args", "kw_args"
1.72 + grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices"
1.73 +
1.74 + def __init__(self, original=None, defining=0, **kw):
1.75 +
1.76 + """
1.77 + Initialise a program node with a link to an optional 'original' AST
1.78 + node. An optional 'defining' parameter (if set to a true value), sets
1.79 + this node as the defining node in the original.
1.80 + """
1.81 +
1.82 + self.original = original
1.83 + self.defining = defining
1.84 + self.copies = {}
1.85 +
1.86 + if self.original is not None and defining:
1.87 + self.original._node = self
1.88 + for name, value in kw.items():
1.89 + setattr(self, name, value)
1.90 +
1.91 + # Annotations.
1.92 +
1.93 + self.types = set()
1.94 +
1.95 + def __repr__(self):
1.96 +
1.97 + "Return a readable representation."
1.98 +
1.99 + if hasattr(self, "full_name"):
1.100 + s = "%s '%s'" % (self.__class__.__name__, self.full_name())
1.101 + elif hasattr(self, "name"):
1.102 + s = "%s '%s'" % (self.__class__.__name__, self.name)
1.103 + elif hasattr(self, "index"):
1.104 + s = "%s (%s)" % (self.__class__.__name__, self.index)
1.105 + elif hasattr(self, "value"):
1.106 + s = "%s %s" % (self.__class__.__name__, repr(self.value))
1.107 + elif hasattr(self, "ref"):
1.108 + s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name))
1.109 + else:
1.110 + s = "%s" % (self.__class__.__name__,)
1.111 +
1.112 + # Annotations.
1.113 +
1.114 + if self.types:
1.115 + return "%s -> %s" % (s, self.types)
1.116 + else:
1.117 + return s
1.118 +
1.119 + def _pprint(self, indent, continuation, s, stream=None):
1.120 +
1.121 + """
1.122 + Print, at the given 'indent' level, with the given 'continuation' text,
1.123 + the string 's', either to the given, optional 'stream' or to standard
1.124 + output, this node's "pretty" representation.
1.125 + """
1.126 +
1.127 + stream = stream or sys.stdout
1.128 + if continuation:
1.129 + print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s
1.130 + else:
1.131 + print >>stream, (" " * indent) + s
1.132 +
1.133 + def pprint(self, indent=0, continuation=None, stream=None):
1.134 +
1.135 + """
1.136 + Print, at the given, optional 'indent', with the given optional
1.137 + 'continuation' text, either to the given, optional 'stream' or to
1.138 + standard output, this node's "pretty" representation along with its
1.139 + children and their "pretty" representation (and so on).
1.140 + """
1.141 +
1.142 + stream = stream or sys.stdout
1.143 + self._pprint(indent, continuation, repr(self), stream)
1.144 +
1.145 + # Subprogram-related details.
1.146 +
1.147 + if hasattr(self, "params"):
1.148 + for name, default in self.params:
1.149 + self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream)
1.150 + if hasattr(self, "star") and self.star:
1.151 + name, default = self.star
1.152 + self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream)
1.153 + if hasattr(self, "dstar") and self.dstar:
1.154 + name, default = self.dstar
1.155 + self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream)
1.156 + if getattr(self, "internal", 0):
1.157 + self._pprint(indent + 2, "( ", "internal", stream=stream)
1.158 + if getattr(self, "structure", 0):
1.159 + self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream)
1.160 +
1.161 + # Expression-related details.
1.162 +
1.163 + if hasattr(self, "expr"):
1.164 + self.expr.pprint(indent + 2, "- ", stream=stream)
1.165 + if hasattr(self, "nodes"):
1.166 + for node in self.nodes:
1.167 + node.pprint(indent + 2, "- ", stream=stream)
1.168 + if hasattr(self, "lvalue"):
1.169 + self.lvalue.pprint(indent + 2, "->", stream=stream)
1.170 + if hasattr(self, "nstype"):
1.171 + self._pprint(indent + 2, "", self.nstype, stream=stream)
1.172 + if hasattr(self, "args"):
1.173 + for arg in self.pos_args:
1.174 + arg.pprint(indent + 2, "( ", stream=stream)
1.175 + for name, arg in self.kw_args.items():
1.176 + arg.pprint(indent + 2, "( ", stream=stream)
1.177 + if hasattr(self, "star") and self.star:
1.178 + self.star.pprint(indent + 2, "( ", stream=stream)
1.179 + if hasattr(self, "dstar") and self.dstar:
1.180 + self.dstar.pprint(indent + 2, "( ", stream=stream)
1.181 +
1.182 + # Statement-related details.
1.183 +
1.184 + if hasattr(self, "test"):
1.185 + self.test.pprint(indent + 2, "? ", stream=stream)
1.186 + for attr in self.grouping_attributes:
1.187 + if hasattr(self, attr) and getattr(self, attr):
1.188 + self._pprint(indent, "", "%s {" % attr, stream=stream)
1.189 + for node in getattr(self, attr):
1.190 + node.pprint(indent + 2, stream=stream)
1.191 + self._pprint(indent, "", "}", stream=stream)
1.192 +
1.193 + # Annotations.
1.194 +
1.195 + if hasattr(self, "accesses"):
1.196 + self._pprint(indent, "", "--------", stream=stream)
1.197 + for ref, attributes in self.accesses.items():
1.198 + self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream)
1.199 + self._pprint(indent, "", "--------", stream=stream)
1.200 + if hasattr(self, "writes"):
1.201 + self._pprint(indent, "", "--------", stream=stream)
1.202 + for ref, attribute in self.writes.items():
1.203 + self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream)
1.204 + self._pprint(indent, "", "--------", stream=stream)
1.205 +
1.206 + # Node discovery functions.
1.207 +
1.208 + def active(self):
1.209 +
1.210 + "Return the active copies of this node or a list containing this node."
1.211 +
1.212 + return self.copies.values() or [self]
1.213 +
1.214 + # Node manipulation functions.
1.215 +
1.216 + def copy(self, instance=None, new_name=None):
1.217 +
1.218 + """
1.219 + Perform a deep copy of the node, optionally specifying the 'instance'
1.220 + for whom the copy has been requested and a 'new_name' for the copied
1.221 + node. Return new unannotated copies of the node and its descendants.
1.222 + """
1.223 +
1.224 + # Copy the common attributes of this node.
1.225 +
1.226 + common = {}
1.227 + for attr in self.common_attributes:
1.228 + if hasattr(self, attr):
1.229 + common[attr] = getattr(self, attr)
1.230 +
1.231 + # Add new attributes specially for copies.
1.232 +
1.233 + common["instance"] = instance
1.234 +
1.235 + if new_name is not None:
1.236 + common["copy_of"] = self
1.237 + common["name"] = new_name
1.238 +
1.239 + # Instantiate the copy, avoiding side-effects with original and defining.
1.240 +
1.241 + node = self.__class__(**common)
1.242 + node.defining = self.defining
1.243 +
1.244 + # Add links to copies from originals.
1.245 +
1.246 + self.copies[instance] = node
1.247 +
1.248 + # Copy attributes of different types.
1.249 +
1.250 + for attr in self.expression_attributes:
1.251 + if hasattr(self, attr):
1.252 + n = getattr(self, attr)
1.253 + if n is None:
1.254 + n2 = n
1.255 + else:
1.256 + n2 = n.copy(instance)
1.257 + setattr(node, attr, n2)
1.258 +
1.259 + for attr in self.argument_attributes:
1.260 + if hasattr(self, attr):
1.261 + t = getattr(self, attr)
1.262 + if t is None:
1.263 + t2 = t
1.264 + else:
1.265 + name, n = t
1.266 + n2 = n.copy(instance)
1.267 + t2 = name, n2
1.268 + setattr(node, attr, t2)
1.269 +
1.270 + for attr in self.invocation_attributes:
1.271 + if hasattr(self, attr):
1.272 + l = getattr(self, attr)
1.273 + l2 = []
1.274 + for name, n in l:
1.275 + if n is None:
1.276 + l2.append((name, n))
1.277 + else:
1.278 + l2.append((name, n.copy(instance)))
1.279 + setattr(node, attr, l2)
1.280 +
1.281 + for attr in self.grouping_attributes:
1.282 + if hasattr(self, attr):
1.283 + l = getattr(self, attr)
1.284 + setattr(node, attr, [n.copy(instance) for n in l])
1.285 +
1.286 + # Arguments are usually processed further - "args" is useless.
1.287 +
1.288 + if hasattr(self, "pos_args"):
1.289 + node.pos_args = [n.copy(instance) for n in self.pos_args]
1.290 +
1.291 + if hasattr(self, "kw_args"):
1.292 + node.kw_args = {}
1.293 + for name, n in self.kw_args.items():
1.294 + node.kw_args[name] = n.copy(instance)
1.295 +
1.296 + return node
1.297 +
1.298 +# These are the supported "operations" described by simplified program nodes.
1.299 +
1.300 +class Pass(Node): "A placeholder node corresponding to pass."
1.301 +class Assign(Node): "A grouping node for assignment-related operations."
1.302 +class Keyword(Node): "A grouping node for keyword arguments."
1.303 +class Global(Node): "A global name designator."
1.304 +class Import(Node): "A module import operation."
1.305 +class LoadTemp(Node): "Load a previously-stored temporary value."
1.306 +class LoadName(Node): "Load a named object."
1.307 +class LoadAttr(Node): "Load an object attribute."
1.308 +class LoadRef(Node): "Load a reference, typically a subprogram or a constant."
1.309 +class LoadExc(Node): "Load a handled exception."
1.310 +class ResetExc(Node): "Reset the exception state."
1.311 +class StoreTemp(Node): "Store a temporary value."
1.312 +class StoreName(Node): "Associate a name with an object."
1.313 +class StoreAttr(Node): "Associate an object's attribute with a value."
1.314 +class ReleaseTemp(Node): "Release a temporary value."
1.315 +class Try(Node): "A try...except...else...finally grouping node."
1.316 +class Raise(Node): "An exception raising node."
1.317 +class Not(Node): "A negation of an expression."
1.318 +class CheckType(Node): "Check a value's type from a list of choices."
1.319 +class Return(Node): "Return an evaluated expression."
1.320 +class Invoke(Node): "An invocation."
1.321 +
1.322 +# There are two types of return node: return from function and return from
1.323 +# block.
1.324 +
1.325 +class ReturnFromFunction(Return):
1.326 + pass
1.327 +
1.328 +class ReturnFromBlock(Return):
1.329 + pass
1.330 +
1.331 +# NOTE: Not actually supported.
1.332 +# Additionally, yield statements act like return statements for the purposes
1.333 +# of this system.
1.334 +
1.335 +class Yield(ReturnFromFunction):
1.336 + pass
1.337 +
1.338 +# Some behaviour is set as the default in conditional nodes but may be
1.339 +# overridden.
1.340 +
1.341 +class Conditional(Node):
1.342 +
1.343 + "A conditional node consisting of a test and outcomes."
1.344 +
1.345 + def __init__(self, *args, **kw):
1.346 + self.isolate_test = 0
1.347 + Node.__init__(self, *args, **kw)
1.348 +
1.349 +# Invocations involve some more work to process calculated attributes.
1.350 +
1.351 +class InvokeFunction(Invoke):
1.352 +
1.353 + "A function or method invocation."
1.354 +
1.355 + def __init__(self, *args, **kw):
1.356 + self.args = []
1.357 + self.star = None
1.358 + self.dstar = None
1.359 + Invoke.__init__(self, *args, **kw)
1.360 + self.set_args(self.args)
1.361 + self.share_locals = 0
1.362 +
1.363 + def set_args(self, args):
1.364 +
1.365 + "Sort the 'args' into positional and keyword arguments."
1.366 +
1.367 + self.pos_args = []
1.368 + self.kw_args = {}
1.369 + add_kw = 0
1.370 + for arg in args:
1.371 + if not add_kw:
1.372 + if not isinstance(arg, Keyword):
1.373 + self.pos_args.append(arg)
1.374 + else:
1.375 + add_kw = 1
1.376 + if add_kw:
1.377 + if isinstance(arg, Keyword):
1.378 + self.kw_args[arg.name] = arg.expr
1.379 + else:
1.380 + raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self
1.381 +
1.382 +class InvokeRef(Invoke):
1.383 +
1.384 + "A block or loop invocation."
1.385 +
1.386 + def __init__(self, *args, **kw):
1.387 + self.share_locals = 1
1.388 + Invoke.__init__(self, *args, **kw)
1.389 +
1.390 +# Program structure nodes.
1.391 +
1.392 +class Module(Node, Structure):
1.393 +
1.394 + "A Python module."
1.395 +
1.396 + def full_name(self):
1.397 + return "module %s" % self.name
1.398 +
1.399 +class Subprogram(Node, WithName):
1.400 +
1.401 + "A subprogram: functions, methods and loops."
1.402 +
1.403 + def __init__(self, *args, **kw):
1.404 + Node.__init__(self, *args, **kw)
1.405 + WithName.__init__(self)
1.406 + self.raises = set()
1.407 + self.returns = set()
1.408 + self.return_locals = set()
1.409 +
1.410 +# vim: tabstop=4 expandtab shiftwidth=4