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 __hash__(self): 99 return id(self) 100 101 def __repr__(self): 102 103 "Return a readable representation." 104 105 if hasattr(self, "full_name"): 106 s = "%s '%s'" % (self.__class__.__name__, self.full_name()) 107 elif hasattr(self, "name"): 108 s = "%s '%s'" % (self.__class__.__name__, self.name) 109 elif hasattr(self, "index"): 110 s = "%s (%s)" % (self.__class__.__name__, self.index) 111 elif hasattr(self, "value"): 112 s = "%s %s" % (self.__class__.__name__, repr(self.value)) 113 elif hasattr(self, "ref"): 114 s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) 115 else: 116 s = "%s" % (self.__class__.__name__,) 117 118 # Annotations. 119 120 if self.types: 121 return "%s -> %s" % (s, self.types) 122 else: 123 return s 124 125 def _pprint(self, indent, continuation, s, stream=None): 126 127 """ 128 Print, at the given 'indent' level, with the given 'continuation' text, 129 the string 's', either to the given, optional 'stream' or to standard 130 output, this node's "pretty" representation. 131 """ 132 133 stream = stream or sys.stdout 134 if continuation: 135 print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s 136 else: 137 print >>stream, (" " * indent) + s 138 139 def pprint(self, indent=0, continuation=None, stream=None): 140 141 """ 142 Print, at the given, optional 'indent', with the given optional 143 'continuation' text, either to the given, optional 'stream' or to 144 standard output, this node's "pretty" representation along with its 145 children and their "pretty" representation (and so on). 146 """ 147 148 stream = stream or sys.stdout 149 self._pprint(indent, continuation, repr(self), stream) 150 151 # Subprogram-related details. 152 153 if hasattr(self, "params"): 154 for name, default in self.params: 155 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 156 if hasattr(self, "star") and self.star: 157 name, default = self.star 158 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 159 if hasattr(self, "dstar") and self.dstar: 160 name, default = self.dstar 161 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 162 if getattr(self, "internal", 0): 163 self._pprint(indent + 2, "( ", "internal", stream=stream) 164 if getattr(self, "structure", 0): 165 self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) 166 167 # Expression-related details. 168 169 if hasattr(self, "expr"): 170 self.expr.pprint(indent + 2, "- ", stream=stream) 171 if hasattr(self, "nodes"): 172 for node in self.nodes: 173 node.pprint(indent + 2, "- ", stream=stream) 174 if hasattr(self, "lvalue"): 175 self.lvalue.pprint(indent + 2, "->", stream=stream) 176 if hasattr(self, "nstype"): 177 self._pprint(indent + 2, "", self.nstype, stream=stream) 178 if hasattr(self, "args"): 179 for arg in self.pos_args: 180 arg.pprint(indent + 2, "( ", stream=stream) 181 for name, arg in self.kw_args.items(): 182 arg.pprint(indent + 2, "( ", stream=stream) 183 if hasattr(self, "star") and self.star: 184 self.star.pprint(indent + 2, "( ", stream=stream) 185 if hasattr(self, "dstar") and self.dstar: 186 self.dstar.pprint(indent + 2, "( ", stream=stream) 187 188 # Statement-related details. 189 190 if hasattr(self, "test"): 191 self.test.pprint(indent + 2, "? ", stream=stream) 192 for attr in self.grouping_attributes: 193 if hasattr(self, attr) and getattr(self, attr): 194 self._pprint(indent, "", "%s {" % attr, stream=stream) 195 for node in getattr(self, attr): 196 node.pprint(indent + 2, stream=stream) 197 self._pprint(indent, "", "}", stream=stream) 198 199 # Annotations. 200 201 if hasattr(self, "accesses"): 202 self._pprint(indent, "", "--------", stream=stream) 203 for ref, attributes in self.accesses.items(): 204 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream) 205 self._pprint(indent, "", "--------", stream=stream) 206 if hasattr(self, "writes"): 207 self._pprint(indent, "", "--------", stream=stream) 208 for ref, attribute in self.writes.items(): 209 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) 210 self._pprint(indent, "", "--------", stream=stream) 211 212 # Node discovery functions. 213 214 def active(self): 215 216 "Return the active copies of this node or a list containing this node." 217 218 return self.copies.values() or [self] 219 220 def is_annotated(self): 221 222 """ 223 Return whether active copies of this node (or this node itself) is 224 annotated. 225 """ 226 227 return reduce(operator.or_, [n.annotated for n in self.active()]) 228 229 # Node manipulation functions. 230 231 def copy(self, instance=None, new_name=None): 232 233 """ 234 Perform a deep copy of the node, optionally specifying the 'instance' 235 for whom the copy has been requested and a 'new_name' for the copied 236 node. Return new unannotated copies of the node and its descendants. 237 """ 238 239 # Copy the common attributes of this node. 240 241 common = {} 242 for attr in self.common_attributes: 243 if hasattr(self, attr): 244 common[attr] = getattr(self, attr) 245 246 # Add new attributes specially for copies. 247 248 common["instance"] = instance 249 250 if new_name is not None: 251 common["copy_of"] = self 252 common["name"] = new_name 253 254 # Instantiate the copy, avoiding side-effects with original and defining. 255 256 node = self.__class__(**common) 257 node.defining = self.defining 258 259 # Add links to copies from originals. 260 261 self.copies[instance] = node 262 263 # Copy attributes of different types. 264 265 for attr in self.expression_attributes: 266 if hasattr(self, attr): 267 n = getattr(self, attr) 268 if n is None: 269 n2 = n 270 else: 271 n2 = n.copy(instance) 272 setattr(node, attr, n2) 273 274 for attr in self.argument_attributes: 275 if hasattr(self, attr): 276 t = getattr(self, attr) 277 if t is None: 278 t2 = t 279 else: 280 name, n = t 281 n2 = n.copy(instance) 282 t2 = name, n2 283 setattr(node, attr, t2) 284 285 for attr in self.invocation_attributes: 286 if hasattr(self, attr): 287 l = getattr(self, attr) 288 l2 = [] 289 for name, n in l: 290 if n is None: 291 l2.append((name, n)) 292 else: 293 l2.append((name, n.copy(instance))) 294 setattr(node, attr, l2) 295 296 for attr in self.grouping_attributes: 297 if hasattr(self, attr): 298 l = getattr(self, attr) 299 setattr(node, attr, [n.copy(instance) for n in l]) 300 301 # Arguments are usually processed further - "args" is useless. 302 303 if hasattr(self, "pos_args"): 304 node.pos_args = [n.copy(instance) for n in self.pos_args] 305 306 if hasattr(self, "kw_args"): 307 node.kw_args = {} 308 for name, n in self.kw_args.items(): 309 node.kw_args[name] = n.copy(instance) 310 311 return node 312 313 # These are the supported "operations" described by simplified program nodes. 314 315 class Pass(Node): "A placeholder node corresponding to pass." 316 class Assign(Node): "A grouping node for assignment-related operations." 317 class Keyword(Node): "A grouping node for keyword arguments." 318 class Global(Node): "A global name designator." 319 class Import(Node): "A module import operation." 320 class LoadTemp(Node): "Load a previously-stored temporary value." 321 class LoadName(Node): "Load a named object." 322 class LoadAttr(Node): "Load an object attribute." 323 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 324 class LoadExc(Node): "Load a handled exception." 325 class ResetExc(Node): "Reset the exception state." 326 class StoreTemp(Node): "Store a temporary value." 327 class StoreName(Node): "Associate a name with an object." 328 class StoreAttr(Node): "Associate an object's attribute with a value." 329 class ReleaseTemp(Node): "Release a temporary value." 330 class Try(Node): "A try...except...else...finally grouping node." 331 class Raise(Node): "An exception raising node." 332 class Not(Node): "A negation of an expression." 333 class CheckType(Node): "Check a value's type from a list of choices." 334 class Return(Node): "Return an evaluated expression." 335 class Invoke(Node): "An invocation." 336 class MakeTuple(Node): "Make a tuple object." 337 338 # There are two types of return node: return from function and return from 339 # block. 340 341 class ReturnFromFunction(Return): 342 pass 343 344 class ReturnFromBlock(Return): 345 pass 346 347 # NOTE: Not actually supported. 348 # Additionally, yield statements act like return statements for the purposes 349 # of this system. 350 351 class Yield(ReturnFromFunction): 352 pass 353 354 # Some behaviour is set as the default in conditional nodes but may be 355 # overridden. 356 357 class Conditional(Node): 358 359 "A conditional node consisting of a test and outcomes." 360 361 def __init__(self, *args, **kw): 362 self.isolate_test = 0 363 Node.__init__(self, *args, **kw) 364 365 # Invocations involve some more work to process calculated attributes. 366 367 class InvokeFunction(Invoke): 368 369 "A function or method invocation." 370 371 def __init__(self, *args, **kw): 372 self.args = [] 373 self.star = None 374 self.dstar = None 375 Invoke.__init__(self, *args, **kw) 376 self.set_args(self.args) 377 self.share_locals = 0 378 379 def set_args(self, args): 380 381 "Sort the 'args' into positional and keyword arguments." 382 383 self.pos_args = [] 384 self.kw_args = {} 385 add_kw = 0 386 for arg in args: 387 if not add_kw: 388 if not isinstance(arg, Keyword): 389 self.pos_args.append(arg) 390 else: 391 add_kw = 1 392 if add_kw: 393 if isinstance(arg, Keyword): 394 self.kw_args[arg.name] = arg.expr 395 else: 396 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 397 398 class InvokeRef(Invoke): 399 400 "A block or loop invocation." 401 402 def __init__(self, *args, **kw): 403 self.share_locals = 1 404 Invoke.__init__(self, *args, **kw) 405 406 # Program structure nodes. 407 408 class Module(Node, Structure): 409 410 "A Python module." 411 412 def full_name(self): 413 return "module %s" % self.name 414 415 class Subprogram(Node, WithName): 416 417 "A subprogram: functions, methods and loops." 418 419 def __init__(self, *args, **kw): 420 Node.__init__(self, *args, **kw) 421 WithName.__init__(self) 422 self.raises = set() 423 self.returns = set() 424 self.return_locals = set() 425 426 # vim: tabstop=4 expandtab shiftwidth=4