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 program is free software; you can redistribute it and/or modify it under 11 the terms of the GNU General Public License as published by the Free Software 12 Foundation; either version 3 of the License, or (at your option) any later 13 version. 14 15 This program is distributed in the hope that it will be useful, but WITHOUT 16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 17 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 18 details. 19 20 You should have received a copy of the GNU General Public License along with 21 this program. If not, see <http://www.gnu.org/licenses/>. 22 """ 23 24 from simplify.simplified.utils import Structure, WithName, name, Namespace 25 import sys 26 import operator 27 28 # Simplified program nodes. 29 30 class Node: 31 32 """ 33 A result node with common attributes: 34 35 original The original node from which this node was created. 36 defining Whether the node defines something in the original program. 37 name Any name involved (variable or attribute). 38 index Any index involved (temporary variable name). 39 value Any constant value. 40 ref Any reference to (for example) subprograms. 41 nstype Any indication of the namespace type involved in a name access. 42 43 Expression-related attributes: 44 45 expr Any contributing expression. 46 lvalue Any target expression. 47 test Any test expression in a conditional instruction. 48 49 Invocation and subprogram attributes: 50 51 args Any collection of argument nodes. 52 params Any collection of parameter nodes and defaults. 53 54 Tuple construction attributes: 55 56 nodes Any expressions used to initialise a tuple 57 58 Statement-grouping attributes: 59 60 body Any conditional code depending on the success of a test. 61 else_ Any conditional code depending on the failure of a test. 62 handler Any exception handler code. 63 finally_ Any code which will be executed regardless. 64 code Any unconditional code. 65 choices Any choices which may be included in the final program. 66 """ 67 68 common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original" 69 expression_attributes = "expr", "lvalue", "test" 70 argument_attributes = "star", "dstar" 71 invocation_attributes = "params", # not "args" - see "pos_args", "kw_args" 72 grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices", "nodes" 73 74 def __init__(self, original=None, defining=0, **kw): 75 76 """ 77 Initialise a program node with a link to an optional 'original' AST 78 node. An optional 'defining' parameter (if set to a true value), sets 79 this node as the defining node in the original. 80 """ 81 82 self.original = original 83 self.defining = defining 84 self.copies = {} 85 86 if self.original is not None and defining: 87 self.original._node = self 88 for name, value in kw.items(): 89 setattr(self, name, value) 90 91 # Annotations. 92 93 self.types = set() 94 self.annotated = 0 95 96 def __hash__(self): 97 return id(self) 98 99 def __repr__(self): 100 101 "Return a readable representation." 102 103 if hasattr(self, "full_name"): 104 s = "%s '%s'" % (self.__class__.__name__, self.full_name()) 105 elif hasattr(self, "name"): 106 s = "%s '%s'" % (self.__class__.__name__, self.name) 107 elif hasattr(self, "index"): 108 s = "%s (%s)" % (self.__class__.__name__, self.index) 109 elif hasattr(self, "value"): 110 s = "%s %s" % (self.__class__.__name__, repr(self.value)) 111 elif hasattr(self, "ref"): 112 s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) 113 else: 114 s = "%s" % (self.__class__.__name__,) 115 116 # Annotations. 117 118 if self.types: 119 return "%s -> %s" % (s, self.types) 120 else: 121 return s 122 123 def _pprint(self, indent, continuation, s, stream=None): 124 125 """ 126 Print, at the given 'indent' level, with the given 'continuation' text, 127 the string 's', either to the given, optional 'stream' or to standard 128 output, this node's "pretty" representation. 129 """ 130 131 stream = stream or sys.stdout 132 if continuation: 133 print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s 134 else: 135 print >>stream, (" " * indent) + s 136 137 def pprint(self, indent=0, continuation=None, stream=None): 138 139 """ 140 Print, at the given, optional 'indent', with the given optional 141 'continuation' text, either to the given, optional 'stream' or to 142 standard output, this node's "pretty" representation along with its 143 children and their "pretty" representation (and so on). 144 """ 145 146 stream = stream or sys.stdout 147 self._pprint(indent, continuation, repr(self), stream) 148 149 # Subprogram-related details. 150 151 if hasattr(self, "params"): 152 for name, default in self.params: 153 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 154 if hasattr(self, "star") and self.star: 155 name, default = self.star 156 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 157 if hasattr(self, "dstar") and self.dstar: 158 name, default = self.dstar 159 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 160 if getattr(self, "internal", 0): 161 self._pprint(indent + 2, "( ", "internal", stream=stream) 162 if getattr(self, "structure", 0): 163 self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) 164 165 # Expression-related details. 166 167 if hasattr(self, "expr"): 168 self.expr.pprint(indent + 2, "- ", stream=stream) 169 if hasattr(self, "nodes"): 170 for node in self.nodes: 171 node.pprint(indent + 2, "- ", stream=stream) 172 if hasattr(self, "lvalue"): 173 self.lvalue.pprint(indent + 2, "->", stream=stream) 174 if hasattr(self, "nstype"): 175 self._pprint(indent + 2, "", self.nstype, stream=stream) 176 if hasattr(self, "args"): 177 for arg in self.pos_args: 178 arg.pprint(indent + 2, "( ", stream=stream) 179 for name, arg in self.kw_args.items(): 180 arg.pprint(indent + 2, "( ", stream=stream) 181 if hasattr(self, "star") and self.star: 182 self.star.pprint(indent + 2, "( ", stream=stream) 183 if hasattr(self, "dstar") and self.dstar: 184 self.dstar.pprint(indent + 2, "( ", stream=stream) 185 186 # Statement-related details. 187 188 if hasattr(self, "test"): 189 self.test.pprint(indent + 2, "? ", stream=stream) 190 for attr in self.grouping_attributes: 191 if hasattr(self, attr) and getattr(self, attr): 192 self._pprint(indent, "", "%s {" % attr, stream=stream) 193 for node in getattr(self, attr): 194 node.pprint(indent + 2, stream=stream) 195 self._pprint(indent, "", "}", stream=stream) 196 197 # Annotations. 198 199 if hasattr(self, "accesses"): 200 self._pprint(indent, "", "--------", stream=stream) 201 for ref, attributes in self.accesses.items(): 202 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream) 203 self._pprint(indent, "", "--------", stream=stream) 204 if hasattr(self, "writes"): 205 self._pprint(indent, "", "--------", stream=stream) 206 for ref, attribute in self.writes.items(): 207 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) 208 self._pprint(indent, "", "--------", stream=stream) 209 210 # Node discovery functions. 211 212 def active(self): 213 214 "Return the active copies of this node or a list containing this node." 215 216 return self.copies.values() or [self] 217 218 def is_annotated(self): 219 220 """ 221 Return whether active copies of this node (or this node itself) is 222 annotated. 223 """ 224 225 return reduce(operator.or_, [n.annotated for n in self.active()]) 226 227 # Node manipulation functions. 228 229 def copy(self, instance=None, new_name=None): 230 231 """ 232 Perform a deep copy of the node, optionally specifying the 'instance' 233 for whom the copy has been requested and a 'new_name' for the copied 234 node. Return new unannotated copies of the node and its descendants. 235 """ 236 237 # Copy the common attributes of this node. 238 239 common = {} 240 for attr in self.common_attributes: 241 if hasattr(self, attr): 242 common[attr] = getattr(self, attr) 243 244 # Add new attributes specially for copies. 245 246 common["instance"] = instance 247 248 if new_name is not None: 249 common["copy_of"] = self 250 common["name"] = new_name 251 252 # Instantiate the copy, avoiding side-effects with original and defining. 253 254 node = self.__class__(**common) 255 node.defining = self.defining 256 257 # Add links to copies from originals. 258 259 self.copies[instance] = node 260 261 # Copy attributes of different types. 262 263 for attr in self.expression_attributes: 264 if hasattr(self, attr): 265 n = getattr(self, attr) 266 if n is None: 267 n2 = n 268 else: 269 n2 = n.copy(instance) 270 setattr(node, attr, n2) 271 272 for attr in self.argument_attributes: 273 if hasattr(self, attr): 274 t = getattr(self, attr) 275 if t is None: 276 t2 = t 277 else: 278 name, n = t 279 n2 = n.copy(instance) 280 t2 = name, n2 281 setattr(node, attr, t2) 282 283 for attr in self.invocation_attributes: 284 if hasattr(self, attr): 285 l = getattr(self, attr) 286 l2 = [] 287 for name, n in l: 288 if n is None: 289 l2.append((name, n)) 290 else: 291 l2.append((name, n.copy(instance))) 292 setattr(node, attr, l2) 293 294 for attr in self.grouping_attributes: 295 if hasattr(self, attr): 296 l = getattr(self, attr) 297 setattr(node, attr, [n.copy(instance) for n in l]) 298 299 # Arguments are usually processed further - "args" is useless. 300 301 if hasattr(self, "pos_args"): 302 node.pos_args = [n.copy(instance) for n in self.pos_args] 303 304 if hasattr(self, "kw_args"): 305 node.kw_args = {} 306 for name, n in self.kw_args.items(): 307 node.kw_args[name] = n.copy(instance) 308 309 return node 310 311 # These are the supported "operations" described by simplified program nodes. 312 313 class Pass(Node): "A placeholder node corresponding to pass." 314 class Assign(Node): "A grouping node for assignment-related operations." 315 class Keyword(Node): "A grouping node for keyword arguments." 316 class Global(Node): "A global name designator." 317 class Import(Node): "A module import operation." 318 class LoadTemp(Node): "Load a previously-stored temporary value." 319 class LoadName(Node): "Load a named object." 320 class LoadAttr(Node): "Load an object attribute." 321 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 322 class LoadExc(Node): "Load a handled exception." 323 class ResetExc(Node): "Reset the exception state." 324 class StoreTemp(Node): "Store a temporary value." 325 class StoreName(Node): "Associate a name with an object." 326 class StoreAttr(Node): "Associate an object's attribute with a value." 327 class ReleaseTemp(Node): "Release a temporary value." 328 class Try(Node): "A try...except...else...finally grouping 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 Raise(Invoke): 365 366 "An exception raising node which may behave like an invocation." 367 368 def __init__(self, original=None, defining=0, expr=None, traceback=None, **kw): 369 370 """ 371 Initialise the invocation with the following optional parameters: 372 373 * The 'original' AST node represented by this invocation. 374 * Whether this invocation is 'defining' (false by default). 375 * The 'expr' or expression indicating the invoked subprogram. 376 * The 'traceback' associated with the raised exception. 377 """ 378 379 Invoke.__init__(self, original, defining, expr=expr, traceback=traceback, **kw) 380 self.share_locals = 0 381 self.raises = set() 382 383 class InvokeFunction(Invoke): 384 385 "A function or method invocation." 386 387 def __init__(self, original=None, defining=0, expr=None, args=None, star=None, dstar=None, **kw): 388 389 """ 390 Initialise the invocation with the following optional parameters: 391 392 * The 'original' AST node represented by this invocation. 393 * Whether this invocation is 'defining' (false by default). 394 * The 'expr' or expression indicating the invoked subprogram. 395 * The 'args' or arguments to be supplied, yielding the 'pos_args' and 396 'kw_args' attributes on this object. 397 * The 'star' argument containing additional unlabelled arguments. 398 * The 'dstar' argument containing keyword arguments. 399 """ 400 401 Invoke.__init__(self, original, defining, expr=expr, args=(args or []), star=star, dstar=dstar, **kw) 402 self.set_args(self.args) 403 self.share_locals = 0 404 self.raises = set() 405 406 def set_args(self, args): 407 408 "Sort the 'args' into positional and keyword arguments." 409 410 self.pos_args = [] 411 self.kw_args = {} 412 add_kw = 0 413 for arg in args: 414 if not add_kw: 415 if not isinstance(arg, Keyword): 416 self.pos_args.append(arg) 417 else: 418 add_kw = 1 419 if add_kw: 420 if isinstance(arg, Keyword): 421 self.kw_args[arg.name] = arg.expr 422 else: 423 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 424 425 class InvokeRef(Invoke): 426 427 "A block or loop invocation." 428 429 def __init__(self, original=None, defining=0, ref=None, produces_result=1, share_locals=1, **kw): 430 431 """ 432 Initialise the invocation with the following optional parameters: 433 434 * The 'original' AST node represented by this invocation. 435 * Whether this invocation is 'defining' (false by default). 436 * The 'ref' indicating the subprogram to be invoked. 437 * Whether a result is produced as indicated by 'produces_result' (true 438 by default). 439 * Whether the subprogram shares the locals of the caller as indicated 440 by 'share_locals' (true by default). 441 """ 442 443 Invoke.__init__(self, original, defining, ref=ref, produces_result=produces_result, share_locals=share_locals, **kw) 444 self.raises = set() 445 446 # Program structure nodes. 447 448 class Module(Node, Structure): 449 450 "A Python module." 451 452 def __init__(self, *args, **kw): 453 Node.__init__(self, *args, **kw) 454 self.structure = None 455 456 def full_name(self): 457 return "module %s" % self.name 458 459 class Subprogram(Node, WithName, Structure): 460 461 "A subprogram: functions, methods and loops." 462 463 def __init__(self, original=None, defining=0, name=None, module=None, structure=None, 464 structures=None, internal=0, returns_value=1, is_method=0, params=None, star=None, 465 dstar=None, **kw): 466 467 """ 468 Initialise the subprogram with the following optional parameters: 469 470 * The 'original' AST node represented by this subprogram. 471 * Whether this subprogram is 'defining' or not (false by default). 472 * The 'name' of this subprogram which may be None. 473 * The 'module' in which this subprogram is found. 474 * The 'structure' initialised by this subprogram. 475 * The 'structures' within which this subprogram resides. 476 * The 'internal' status of this subprogram (false by default), which 477 if true typically means that a loop or operation is being 478 represented. 479 * Whether a value is returned, as specified by 'returns_value' (true 480 by default). 481 * Whether the subprogram is a method, as specified by 'is_method' 482 (false by default). 483 * The 'params' (a parameter list which is empty by default). 484 * The 'star' parameter which collects excess positional arguments. 485 * The 'dstar' parameter which collects unmatched keyword arguments. 486 """ 487 488 Node.__init__(self, original, defining, name=name, module=module, structure=structure, 489 structures=structures, internal=internal, returns_value=returns_value, 490 is_method=is_method, params=(params or []), star=star, dstar=dstar, **kw) 491 492 WithName.__init__(self) 493 self.raises = set() 494 self.returns = set() 495 self.return_locals = set() 496 self.paramtypes = {} 497 self.namespace = Namespace() # NOTE: Temporary. 498 499 # vim: tabstop=4 expandtab shiftwidth=4