1 #!/usr/bin/env python 2 3 """ 4 Simplified program nodes for easier type propagation and analysis. This module 5 contains nodes representing program instructions or operations, program 6 structure or organisation, and abstract program data. 7 8 Copyright (C) 2006, 2007 Paul Boddie <paul@boddie.org.uk> 9 10 This software is free software; you can redistribute it and/or 11 modify it under the terms of the GNU General Public License as 12 published by the Free Software Foundation; either version 2 of 13 the License, or (at your option) any later version. 14 15 This software is distributed in the hope that it will be useful, 16 but WITHOUT ANY WARRANTY; without even the implied warranty of 17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 GNU General Public License for more details. 19 20 You should have received a copy of the GNU General Public 21 License along with this library; see the file LICENCE.txt 22 If not, write to the Free Software Foundation, Inc., 23 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA 24 """ 25 26 from simplify.simplified.utils import Structure, WithName, name 27 import sys 28 import operator 29 30 # Simplified program nodes. 31 32 class Node: 33 34 """ 35 A result node with common attributes: 36 37 original The original node from which this node was created. 38 defining Whether the node defines something in the original program. 39 name Any name involved (variable or attribute). 40 index Any index involved (temporary variable name). 41 value Any constant value. 42 ref Any reference to (for example) subprograms. 43 nstype Any indication of the namespace type involved in a name access. 44 45 Expression-related attributes: 46 47 expr Any contributing expression. 48 lvalue Any target expression. 49 test Any test expression in a conditional instruction. 50 51 Invocation and subprogram attributes: 52 53 args Any collection of argument nodes. 54 params Any collection of parameter nodes and defaults. 55 56 Tuple construction attributes: 57 58 nodes Any expressions used to initialise a tuple 59 60 Statement-grouping attributes: 61 62 body Any conditional code depending on the success of a test. 63 else_ Any conditional code depending on the failure of a test. 64 handler Any exception handler code. 65 finally_ Any code which will be executed regardless. 66 code Any unconditional code. 67 choices Any choices which may be included in the final program. 68 """ 69 70 common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original" 71 expression_attributes = "expr", "lvalue", "test" 72 argument_attributes = "star", "dstar" 73 invocation_attributes = "params", # not "args" - see "pos_args", "kw_args" 74 grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices", "nodes" 75 76 def __init__(self, original=None, defining=0, **kw): 77 78 """ 79 Initialise a program node with a link to an optional 'original' AST 80 node. An optional 'defining' parameter (if set to a true value), sets 81 this node as the defining node in the original. 82 """ 83 84 self.original = original 85 self.defining = defining 86 self.copies = {} 87 88 if self.original is not None and defining: 89 self.original._node = self 90 for name, value in kw.items(): 91 setattr(self, name, value) 92 93 # Annotations. 94 95 self.types = set() 96 self.annotated = 0 97 98 def __repr__(self): 99 100 "Return a readable representation." 101 102 if hasattr(self, "full_name"): 103 s = "%s '%s'" % (self.__class__.__name__, self.full_name()) 104 elif hasattr(self, "name"): 105 s = "%s '%s'" % (self.__class__.__name__, self.name) 106 elif hasattr(self, "index"): 107 s = "%s (%s)" % (self.__class__.__name__, self.index) 108 elif hasattr(self, "value"): 109 s = "%s %s" % (self.__class__.__name__, repr(self.value)) 110 elif hasattr(self, "ref"): 111 s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) 112 else: 113 s = "%s" % (self.__class__.__name__,) 114 115 # Annotations. 116 117 if self.types: 118 return "%s -> %s" % (s, self.types) 119 else: 120 return s 121 122 def _pprint(self, indent, continuation, s, stream=None): 123 124 """ 125 Print, at the given 'indent' level, with the given 'continuation' text, 126 the string 's', either to the given, optional 'stream' or to standard 127 output, this node's "pretty" representation. 128 """ 129 130 stream = stream or sys.stdout 131 if continuation: 132 print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s 133 else: 134 print >>stream, (" " * indent) + s 135 136 def pprint(self, indent=0, continuation=None, stream=None): 137 138 """ 139 Print, at the given, optional 'indent', with the given optional 140 'continuation' text, either to the given, optional 'stream' or to 141 standard output, this node's "pretty" representation along with its 142 children and their "pretty" representation (and so on). 143 """ 144 145 stream = stream or sys.stdout 146 self._pprint(indent, continuation, repr(self), stream) 147 148 # Subprogram-related details. 149 150 if hasattr(self, "params"): 151 for name, default in self.params: 152 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 153 if hasattr(self, "star") and self.star: 154 name, default = self.star 155 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 156 if hasattr(self, "dstar") and self.dstar: 157 name, default = self.dstar 158 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 159 if getattr(self, "internal", 0): 160 self._pprint(indent + 2, "( ", "internal", stream=stream) 161 if getattr(self, "structure", 0): 162 self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) 163 164 # Expression-related details. 165 166 if hasattr(self, "expr"): 167 self.expr.pprint(indent + 2, "- ", stream=stream) 168 if hasattr(self, "nodes"): 169 for node in self.nodes: 170 node.pprint(indent + 2, "- ", stream=stream) 171 if hasattr(self, "lvalue"): 172 self.lvalue.pprint(indent + 2, "->", stream=stream) 173 if hasattr(self, "nstype"): 174 self._pprint(indent + 2, "", self.nstype, stream=stream) 175 if hasattr(self, "args"): 176 for arg in self.pos_args: 177 arg.pprint(indent + 2, "( ", stream=stream) 178 for name, arg in self.kw_args.items(): 179 arg.pprint(indent + 2, "( ", stream=stream) 180 if hasattr(self, "star") and self.star: 181 self.star.pprint(indent + 2, "( ", stream=stream) 182 if hasattr(self, "dstar") and self.dstar: 183 self.dstar.pprint(indent + 2, "( ", stream=stream) 184 185 # Statement-related details. 186 187 if hasattr(self, "test"): 188 self.test.pprint(indent + 2, "? ", stream=stream) 189 for attr in self.grouping_attributes: 190 if hasattr(self, attr) and getattr(self, attr): 191 self._pprint(indent, "", "%s {" % attr, stream=stream) 192 for node in getattr(self, attr): 193 node.pprint(indent + 2, stream=stream) 194 self._pprint(indent, "", "}", stream=stream) 195 196 # Annotations. 197 198 if hasattr(self, "accesses"): 199 self._pprint(indent, "", "--------", stream=stream) 200 for ref, attributes in self.accesses.items(): 201 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream) 202 self._pprint(indent, "", "--------", stream=stream) 203 if hasattr(self, "writes"): 204 self._pprint(indent, "", "--------", stream=stream) 205 for ref, attribute in self.writes.items(): 206 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) 207 self._pprint(indent, "", "--------", stream=stream) 208 209 # Node discovery functions. 210 211 def active(self): 212 213 "Return the active copies of this node or a list containing this node." 214 215 return self.copies.values() or [self] 216 217 def is_annotated(self): 218 219 """ 220 Return whether active copies of this node (or this node itself) is 221 annotated. 222 """ 223 224 return reduce(operator.or_, [n.annotated for n in self.active()]) 225 226 # Node manipulation functions. 227 228 def copy(self, instance=None, new_name=None): 229 230 """ 231 Perform a deep copy of the node, optionally specifying the 'instance' 232 for whom the copy has been requested and a 'new_name' for the copied 233 node. Return new unannotated copies of the node and its descendants. 234 """ 235 236 # Copy the common attributes of this node. 237 238 common = {} 239 for attr in self.common_attributes: 240 if hasattr(self, attr): 241 common[attr] = getattr(self, attr) 242 243 # Add new attributes specially for copies. 244 245 common["instance"] = instance 246 247 if new_name is not None: 248 common["copy_of"] = self 249 common["name"] = new_name 250 251 # Instantiate the copy, avoiding side-effects with original and defining. 252 253 node = self.__class__(**common) 254 node.defining = self.defining 255 256 # Add links to copies from originals. 257 258 self.copies[instance] = node 259 260 # Copy attributes of different types. 261 262 for attr in self.expression_attributes: 263 if hasattr(self, attr): 264 n = getattr(self, attr) 265 if n is None: 266 n2 = n 267 else: 268 n2 = n.copy(instance) 269 setattr(node, attr, n2) 270 271 for attr in self.argument_attributes: 272 if hasattr(self, attr): 273 t = getattr(self, attr) 274 if t is None: 275 t2 = t 276 else: 277 name, n = t 278 n2 = n.copy(instance) 279 t2 = name, n2 280 setattr(node, attr, t2) 281 282 for attr in self.invocation_attributes: 283 if hasattr(self, attr): 284 l = getattr(self, attr) 285 l2 = [] 286 for name, n in l: 287 if n is None: 288 l2.append((name, n)) 289 else: 290 l2.append((name, n.copy(instance))) 291 setattr(node, attr, l2) 292 293 for attr in self.grouping_attributes: 294 if hasattr(self, attr): 295 l = getattr(self, attr) 296 setattr(node, attr, [n.copy(instance) for n in l]) 297 298 # Arguments are usually processed further - "args" is useless. 299 300 if hasattr(self, "pos_args"): 301 node.pos_args = [n.copy(instance) for n in self.pos_args] 302 303 if hasattr(self, "kw_args"): 304 node.kw_args = {} 305 for name, n in self.kw_args.items(): 306 node.kw_args[name] = n.copy(instance) 307 308 return node 309 310 # These are the supported "operations" described by simplified program nodes. 311 312 class Pass(Node): "A placeholder node corresponding to pass." 313 class Assign(Node): "A grouping node for assignment-related operations." 314 class Keyword(Node): "A grouping node for keyword arguments." 315 class Global(Node): "A global name designator." 316 class Import(Node): "A module import operation." 317 class LoadTemp(Node): "Load a previously-stored temporary value." 318 class LoadName(Node): "Load a named object." 319 class LoadAttr(Node): "Load an object attribute." 320 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 321 class LoadExc(Node): "Load a handled exception." 322 class ResetExc(Node): "Reset the exception state." 323 class StoreTemp(Node): "Store a temporary value." 324 class StoreName(Node): "Associate a name with an object." 325 class StoreAttr(Node): "Associate an object's attribute with a value." 326 class ReleaseTemp(Node): "Release a temporary value." 327 class Try(Node): "A try...except...else...finally grouping node." 328 class Raise(Node): "An exception raising node." 329 class Not(Node): "A negation of an expression." 330 class CheckType(Node): "Check a value's type from a list of choices." 331 class Return(Node): "Return an evaluated expression." 332 class Invoke(Node): "An invocation." 333 class MakeTuple(Node): "Make a tuple object." 334 335 # There are two types of return node: return from function and return from 336 # block. 337 338 class ReturnFromFunction(Return): 339 pass 340 341 class ReturnFromBlock(Return): 342 pass 343 344 # NOTE: Not actually supported. 345 # Additionally, yield statements act like return statements for the purposes 346 # of this system. 347 348 class Yield(ReturnFromFunction): 349 pass 350 351 # Some behaviour is set as the default in conditional nodes but may be 352 # overridden. 353 354 class Conditional(Node): 355 356 "A conditional node consisting of a test and outcomes." 357 358 def __init__(self, *args, **kw): 359 self.isolate_test = 0 360 Node.__init__(self, *args, **kw) 361 362 # Invocations involve some more work to process calculated attributes. 363 364 class InvokeFunction(Invoke): 365 366 "A function or method invocation." 367 368 def __init__(self, *args, **kw): 369 self.args = [] 370 self.star = None 371 self.dstar = None 372 Invoke.__init__(self, *args, **kw) 373 self.set_args(self.args) 374 self.share_locals = 0 375 376 def set_args(self, args): 377 378 "Sort the 'args' into positional and keyword arguments." 379 380 self.pos_args = [] 381 self.kw_args = {} 382 add_kw = 0 383 for arg in args: 384 if not add_kw: 385 if not isinstance(arg, Keyword): 386 self.pos_args.append(arg) 387 else: 388 add_kw = 1 389 if add_kw: 390 if isinstance(arg, Keyword): 391 self.kw_args[arg.name] = arg.expr 392 else: 393 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 394 395 class InvokeRef(Invoke): 396 397 "A block or loop invocation." 398 399 def __init__(self, *args, **kw): 400 self.share_locals = 1 401 Invoke.__init__(self, *args, **kw) 402 403 # Program structure nodes. 404 405 class Module(Node, Structure): 406 407 "A Python module." 408 409 def full_name(self): 410 return "module %s" % self.name 411 412 class Subprogram(Node, WithName): 413 414 "A subprogram: functions, methods and loops." 415 416 def __init__(self, *args, **kw): 417 Node.__init__(self, *args, **kw) 418 WithName.__init__(self) 419 self.raises = set() 420 self.returns = set() 421 self.return_locals = set() 422 423 # vim: tabstop=4 expandtab shiftwidth=4