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 class Constant(Node): 336 337 "A constant initialised with a type name for future processing." 338 339 def __init__(self, original=None, defining=0, name=None, value=None, *args, **kw): 340 Node.__init__(self, original, defining, *args, **kw) 341 self.name = name 342 self.value = value 343 self.typename = self.value.__class__.__name__ 344 345 # There are two types of return node: return from function and return from 346 # block. 347 348 class ReturnFromFunction(Return): 349 pass 350 351 class ReturnFromBlock(Return): 352 pass 353 354 # NOTE: Not actually supported. 355 # Additionally, yield statements act like return statements for the purposes 356 # of this system. 357 358 class Yield(ReturnFromFunction): 359 pass 360 361 # Some behaviour is set as the default in conditional nodes but may be 362 # overridden. 363 364 class Conditional(Node): 365 366 "A conditional node consisting of a test and outcomes." 367 368 def __init__(self, *args, **kw): 369 self.isolate_test = 0 370 Node.__init__(self, *args, **kw) 371 372 # Invocations involve some more work to process calculated attributes. 373 374 class Raise(Invoke): 375 376 "An exception raising node which may behave like an invocation." 377 378 def __init__(self, original=None, defining=0, expr=None, traceback=None, **kw): 379 380 """ 381 Initialise the invocation with the following optional parameters: 382 383 * The 'original' AST node represented by this invocation. 384 * Whether this invocation is 'defining' (false by default). 385 * The 'expr' or expression indicating the invoked subprogram. 386 * The 'traceback' associated with the raised exception. 387 """ 388 389 Invoke.__init__(self, original, defining, expr=expr, traceback=traceback, **kw) 390 self.share_locals = 0 391 self.consumed_args = {} 392 self.raises = set() 393 394 class InvokeFunction(Invoke): 395 396 "A function or method invocation." 397 398 def __init__(self, original=None, defining=0, expr=None, args=None, star=None, dstar=None, **kw): 399 400 """ 401 Initialise the invocation with the following optional parameters: 402 403 * The 'original' AST node represented by this invocation. 404 * Whether this invocation is 'defining' (false by default). 405 * The 'expr' or expression indicating the invoked subprogram. 406 * The 'args' or arguments to be supplied, yielding the 'pos_args' and 407 'kw_args' attributes on this object. 408 * The 'star' argument containing additional unlabelled arguments. 409 * The 'dstar' argument containing keyword arguments. 410 """ 411 412 Invoke.__init__(self, original, defining, expr=expr, args=(args or []), star=star, dstar=dstar, **kw) 413 self.set_args(self.args) 414 self.share_locals = 0 415 self.consumed_args = {} 416 self.raises = set() 417 418 def set_args(self, args): 419 420 "Sort the 'args' into positional and keyword arguments." 421 422 self.pos_args = [] 423 self.kw_args = {} 424 add_kw = 0 425 for arg in args: 426 if not add_kw: 427 if not isinstance(arg, Keyword): 428 self.pos_args.append(arg) 429 else: 430 add_kw = 1 431 if add_kw: 432 if isinstance(arg, Keyword): 433 self.kw_args[arg.name] = arg.expr 434 else: 435 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 436 437 class InvokeRef(Invoke): 438 439 "A block or loop invocation." 440 441 def __init__(self, original=None, defining=0, ref=None, produces_result=1, share_locals=1, **kw): 442 443 """ 444 Initialise the invocation with the following optional parameters: 445 446 * The 'original' AST node represented by this invocation. 447 * Whether this invocation is 'defining' (false by default). 448 * The 'ref' indicating the subprogram to be invoked. 449 * Whether a result is produced as indicated by 'produces_result' (true 450 by default). 451 * Whether the subprogram shares the locals of the caller as indicated 452 by 'share_locals' (true by default). 453 """ 454 455 Invoke.__init__(self, original, defining, ref=ref, produces_result=produces_result, share_locals=share_locals, **kw) 456 self.raises = set() 457 458 # Program structure nodes. 459 460 class Module(Node, Structure): 461 462 "A Python module." 463 464 def __init__(self, *args, **kw): 465 Node.__init__(self, *args, **kw) 466 self.structure = None 467 self.params = [] 468 self.star = None 469 self.dstar = None 470 471 def full_name(self): 472 return "module %s" % self.name 473 474 class Subprogram(Node, WithName, Structure): 475 476 "A subprogram: functions, methods and loops." 477 478 def __init__(self, original=None, defining=0, name=None, module=None, structure=None, 479 structures=None, internal=0, returns_value=1, is_method=0, params=None, star=None, 480 dstar=None, **kw): 481 482 """ 483 Initialise the subprogram with the following optional parameters: 484 485 * The 'original' AST node represented by this subprogram. 486 * Whether this subprogram is 'defining' or not (false by default). 487 * The 'name' of this subprogram which may be None. 488 * The 'module' in which this subprogram is found. 489 * The 'structure' initialised by this subprogram. 490 * The 'structures' within which this subprogram resides. 491 * The 'internal' status of this subprogram (false by default), which 492 if true typically means that a loop or operation is being 493 represented. 494 * Whether a value is returned, as specified by 'returns_value' (true 495 by default). 496 * Whether the subprogram is a method, as specified by 'is_method' 497 (false by default). 498 * The 'params' (a parameter list which is empty by default). 499 * The 'star' parameter which collects excess positional arguments. 500 * The 'dstar' parameter which collects unmatched keyword arguments. 501 """ 502 503 Node.__init__(self, original, defining, name=name, module=module, structure=structure, 504 structures=structures, internal=internal, returns_value=returns_value, 505 is_method=is_method, params=(params or []), star=star, dstar=dstar, **kw) 506 507 WithName.__init__(self) 508 self.raises = set() 509 self.returns = set() 510 self.return_locals = set() 511 self.paramtypes = {} 512 self.namespace = Namespace() # NOTE: Temporary. 513 514 def specialisations(self): 515 516 "Return the active specialisations using only distinct instances." 517 518 distinct_instances = {} 519 520 subprograms = set() 521 for instance, subprogram in self.copies.items() or [(None, self)]: 522 if instance is None: 523 subprograms.add(subprogram) 524 continue 525 526 cls = instance.get_class() 527 if not distinct_instances.has_key(cls): 528 distinct_instances[cls] = cls.get_distinct_instances() 529 distinct_instance = distinct_instances[cls][instance] 530 if instance is distinct_instance: 531 subprograms.add(subprogram) 532 533 return subprograms 534 535 # vim: tabstop=4 expandtab shiftwidth=4