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", 69 "returns_value", "is_method", "ref", "module", "structures", "original") 70 71 expression_attributes = "expr", "lvalue", "test" 72 73 argument_attributes = "star", "dstar" 74 75 invocation_attributes = "params", # not "args" - see "pos_args", "kw_args" 76 77 grouping_attributes = ("code", "body", "else_", "handler", "finally_", 78 "choices", "nodes") 79 80 def __init__(self, original=None, defining=0, **kw): 81 82 """ 83 Initialise a program node with a link to an optional 'original' AST 84 node. An optional 'defining' parameter (if set to a true value), sets 85 this node as the defining node in the original. 86 """ 87 88 self.original = original 89 self.defining = defining 90 self.copies = {} 91 92 if self.original is not None and defining: 93 self.original._node = self 94 for name, value in kw.items(): 95 setattr(self, name, value) 96 97 # Annotations. 98 99 self.types = set() 100 self.annotated = 0 101 102 def __hash__(self): 103 return id(self) 104 105 def __repr__(self): 106 107 "Return a readable representation." 108 109 if hasattr(self, "full_name"): 110 s = "%s '%s'" % (self.__class__.__name__, self.full_name()) 111 elif hasattr(self, "name"): 112 s = "%s '%s'" % (self.__class__.__name__, self.name) 113 elif hasattr(self, "index"): 114 s = "%s (%s)" % (self.__class__.__name__, self.index) 115 elif hasattr(self, "value"): 116 s = "%s %s" % (self.__class__.__name__, repr(self.value)) 117 elif hasattr(self, "ref"): 118 s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) 119 else: 120 s = "%s" % (self.__class__.__name__,) 121 122 # Annotations. 123 124 if self.types: 125 return "%s -> %s" % (s, self.types) 126 else: 127 return s 128 129 def _pprint(self, indent, continuation, s, stream=None): 130 131 """ 132 Print, at the given 'indent' level, with the given 'continuation' text, 133 the string 's', either to the given, optional 'stream' or to standard 134 output, this node's "pretty" representation. 135 """ 136 137 stream = stream or sys.stdout 138 if continuation: 139 print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s 140 else: 141 print >>stream, (" " * indent) + s 142 143 def pprint(self, indent=0, continuation=None, stream=None): 144 145 """ 146 Print, at the given, optional 'indent', with the given optional 147 'continuation' text, either to the given, optional 'stream' or to 148 standard output, this node's "pretty" representation along with its 149 children and their "pretty" representation (and so on). 150 """ 151 152 stream = stream or sys.stdout 153 self._pprint(indent, continuation, repr(self), stream) 154 155 # Subprogram-related details. 156 157 if hasattr(self, "params"): 158 for name, default in self.params: 159 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 160 if hasattr(self, "star") and self.star: 161 name, default = self.star 162 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 163 if hasattr(self, "dstar") and self.dstar: 164 name, default = self.dstar 165 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 166 if getattr(self, "internal", 0): 167 self._pprint(indent + 2, "( ", "internal", stream=stream) 168 if getattr(self, "structure", 0): 169 self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) 170 171 # Expression-related details. 172 173 if hasattr(self, "expr"): 174 self.expr.pprint(indent + 2, "- ", stream=stream) 175 if hasattr(self, "nodes"): 176 for node in self.nodes: 177 node.pprint(indent + 2, "- ", stream=stream) 178 if hasattr(self, "lvalue"): 179 self.lvalue.pprint(indent + 2, "->", stream=stream) 180 if hasattr(self, "nstype"): 181 self._pprint(indent + 2, "", self.nstype, stream=stream) 182 if hasattr(self, "args"): 183 for arg in self.pos_args: 184 arg.pprint(indent + 2, "( ", stream=stream) 185 for name, arg in self.kw_args.items(): 186 arg.pprint(indent + 2, "( ", stream=stream) 187 if hasattr(self, "star") and self.star: 188 self.star.pprint(indent + 2, "( ", stream=stream) 189 if hasattr(self, "dstar") and self.dstar: 190 self.dstar.pprint(indent + 2, "( ", stream=stream) 191 192 # Statement-related details. 193 194 if hasattr(self, "test"): 195 self.test.pprint(indent + 2, "? ", stream=stream) 196 for attr in self.grouping_attributes: 197 if hasattr(self, attr) and getattr(self, attr): 198 self._pprint(indent, "", "%s {" % attr, stream=stream) 199 for node in getattr(self, attr): 200 node.pprint(indent + 2, stream=stream) 201 self._pprint(indent, "", "}", stream=stream) 202 203 # Annotations. 204 205 if hasattr(self, "accesses"): 206 self._pprint(indent, "", "--------", stream=stream) 207 for ref, attributes in self.accesses.items(): 208 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, 209 ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes]) 210 ), stream=stream) 211 self._pprint(indent, "", "--------", stream=stream) 212 if hasattr(self, "writes"): 213 self._pprint(indent, "", "--------", stream=stream) 214 for ref, attribute in self.writes.items(): 215 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) 216 self._pprint(indent, "", "--------", stream=stream) 217 218 # Node discovery functions. 219 220 def active(self): 221 222 "Return the active copies of this node or a list containing this node." 223 224 return self.copies.values() or [self] 225 226 def is_annotated(self): 227 228 """ 229 Return whether active copies of this node (or this node itself) is 230 annotated. 231 """ 232 233 return reduce(operator.or_, [n.annotated for n in self.active()]) 234 235 # Node manipulation functions. 236 237 def copy(self, instance=None, new_name=None): 238 239 """ 240 Perform a deep copy of the node, optionally specifying the 'instance' 241 for whom the copy has been requested and a 'new_name' for the copied 242 node. Return new unannotated copies of the node and its descendants. 243 """ 244 245 # Copy the common attributes of this node. 246 247 common = {} 248 for attr in self.common_attributes: 249 if hasattr(self, attr): 250 common[attr] = getattr(self, attr) 251 252 # Add new attributes specially for copies. 253 254 common["instance"] = instance 255 256 if new_name is not None: 257 common["copy_of"] = self 258 common["name"] = new_name 259 260 # Instantiate the copy, avoiding side-effects with original and defining. 261 262 node = self.__class__(**common) 263 node.defining = self.defining 264 265 # Add links to copies from originals. 266 267 self.copies[instance] = node 268 269 # Copy attributes of different types. 270 271 for attr in self.expression_attributes: 272 if hasattr(self, attr): 273 n = getattr(self, attr) 274 if n is None: 275 n2 = n 276 else: 277 n2 = n.copy(instance) 278 setattr(node, attr, n2) 279 280 for attr in self.argument_attributes: 281 if hasattr(self, attr): 282 t = getattr(self, attr) 283 if t is None: 284 t2 = t 285 else: 286 name, n = t 287 n2 = n.copy(instance) 288 t2 = name, n2 289 setattr(node, attr, t2) 290 291 for attr in self.invocation_attributes: 292 if hasattr(self, attr): 293 l = getattr(self, attr) 294 l2 = [] 295 for name, n in l: 296 if n is None: 297 l2.append((name, n)) 298 else: 299 l2.append((name, n.copy(instance))) 300 setattr(node, attr, l2) 301 302 for attr in self.grouping_attributes: 303 if hasattr(self, attr): 304 l = getattr(self, attr) 305 setattr(node, attr, [n.copy(instance) for n in l]) 306 307 # Arguments are usually processed further - "args" is useless. 308 309 if hasattr(self, "pos_args"): 310 node.pos_args = [n.copy(instance) for n in self.pos_args] 311 312 if hasattr(self, "kw_args"): 313 node.kw_args = {} 314 for name, n in self.kw_args.items(): 315 node.kw_args[name] = n.copy(instance) 316 317 return node 318 319 # These are the supported "operations" described by simplified program nodes. 320 321 class Pass(Node): "A placeholder node corresponding to pass." 322 class Assign(Node): "A grouping node for assignment-related operations." 323 class Keyword(Node): "A grouping node for keyword arguments." 324 class Global(Node): "A global name designator." 325 class Import(Node): "A module import operation." 326 class LoadTemp(Node): "Load a previously-stored temporary value." 327 class LoadName(Node): "Load a named object." 328 class LoadAttr(Node): "Load an object attribute." 329 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 330 class LoadExc(Node): "Load a handled exception." 331 class ResetExc(Node): "Reset the exception state." 332 class StoreTemp(Node): "Store a temporary value." 333 class StoreName(Node): "Associate a name with an object." 334 class StoreAttr(Node): "Associate an object's attribute with a value." 335 class ReleaseTemp(Node): "Release a temporary value." 336 class Try(Node): "A try...except...else...finally grouping node." 337 class Not(Node): "A negation of an expression." 338 class CheckType(Node): "Check a value's type from a list of choices." 339 class Return(Node): "Return an evaluated expression." 340 class Invoke(Node): "An invocation." 341 class MakeTuple(Node): "Make a tuple object." 342 343 class Constant(Node): 344 345 "A constant initialised with a type name for future processing." 346 347 def __init__(self, original=None, defining=0, name=None, value=None, *args, **kw): 348 Node.__init__(self, original, defining, *args, **kw) 349 self.name = name 350 self.value = value 351 self.typename = self.value.__class__.__name__ 352 353 # There are two types of return node: return from function and return from 354 # block. 355 356 class ReturnFromFunction(Return): 357 pass 358 359 class ReturnFromBlock(Return): 360 pass 361 362 # NOTE: Not actually supported. 363 # Additionally, yield statements act like return statements for the purposes 364 # of this system. 365 366 class Yield(ReturnFromFunction): 367 pass 368 369 # Some behaviour is set as the default in conditional nodes but may be 370 # overridden. 371 372 class Conditional(Node): 373 374 "A conditional node consisting of a test and outcomes." 375 376 def __init__(self, *args, **kw): 377 self.isolate_test = 0 378 Node.__init__(self, *args, **kw) 379 380 # Invocations involve some more work to process calculated attributes. 381 382 class Raise(Invoke): 383 384 "An exception raising node which may behave like an invocation." 385 386 def __init__(self, original=None, defining=0, expr=None, traceback=None, **kw): 387 388 """ 389 Initialise the invocation with the following optional parameters: 390 391 * The 'original' AST node represented by this invocation. 392 * Whether this invocation is 'defining' (false by default). 393 * The 'expr' or expression indicating the invoked subprogram. 394 * The 'traceback' associated with the raised exception. 395 """ 396 397 Invoke.__init__(self, original, defining, expr=expr, traceback=traceback, **kw) 398 self.share_locals = 0 399 self.consumed_args = {} 400 self.raises = set() 401 402 class InvokeFunction(Invoke): 403 404 "A function or method invocation." 405 406 def __init__(self, original=None, defining=0, expr=None, args=None, star=None, dstar=None, **kw): 407 408 """ 409 Initialise the invocation with the following optional parameters: 410 411 * The 'original' AST node represented by this invocation. 412 * Whether this invocation is 'defining' (false by default). 413 * The 'expr' or expression indicating the invoked subprogram. 414 * The 'args' or arguments to be supplied, yielding the 'pos_args' and 415 'kw_args' attributes on this object. 416 * The 'star' argument containing additional unlabelled arguments. 417 * The 'dstar' argument containing keyword arguments. 418 """ 419 420 Invoke.__init__(self, original, defining, expr=expr, args=(args or []), star=star, dstar=dstar, **kw) 421 self.set_args(self.args) 422 self.share_locals = 0 423 self.consumed_args = {} 424 self.raises = set() 425 426 def set_args(self, args): 427 428 "Sort the 'args' into positional and keyword arguments." 429 430 self.pos_args = [] 431 self.kw_args = {} 432 add_kw = 0 433 for arg in args: 434 if not add_kw: 435 if not isinstance(arg, Keyword): 436 self.pos_args.append(arg) 437 else: 438 add_kw = 1 439 if add_kw: 440 if isinstance(arg, Keyword): 441 self.kw_args[arg.name] = arg.expr 442 else: 443 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 444 445 class InvokeRef(Invoke): 446 447 "A block or loop invocation." 448 449 def __init__(self, original=None, defining=0, ref=None, produces_result=1, share_locals=1, **kw): 450 451 """ 452 Initialise the invocation with the following optional parameters: 453 454 * The 'original' AST node represented by this invocation. 455 * Whether this invocation is 'defining' (false by default). 456 * The 'ref' indicating the subprogram to be invoked. 457 * Whether a result is produced as indicated by 'produces_result' (true 458 by default). 459 * Whether the subprogram shares the locals of the caller as indicated 460 by 'share_locals' (true by default). 461 """ 462 463 Invoke.__init__(self, original, defining, ref=ref, produces_result=produces_result, share_locals=share_locals, **kw) 464 self.raises = set() 465 466 # Program structure nodes. 467 468 class Module(Node, Structure): 469 470 "A Python module." 471 472 def __init__(self, *args, **kw): 473 Node.__init__(self, *args, **kw) 474 self.structure = None 475 self.params = [] 476 self.star = None 477 self.dstar = None 478 479 def full_name(self): 480 return "module %s" % self.name 481 482 class Subprogram(Node, WithName, Structure): 483 484 "A subprogram: functions, methods and loops." 485 486 def __init__(self, original=None, defining=0, name=None, module=None, structure=None, 487 structures=None, internal=0, returns_value=1, is_method=0, params=None, star=None, 488 dstar=None, **kw): 489 490 """ 491 Initialise the subprogram with the following optional parameters: 492 493 * The 'original' AST node represented by this subprogram. 494 * Whether this subprogram is 'defining' or not (false by default). 495 * The 'name' of this subprogram which may be None. 496 * The 'module' in which this subprogram is found. 497 * The 'structure' initialised by this subprogram. 498 * The 'structures' within which this subprogram resides. 499 * The 'internal' status of this subprogram (false by default), which 500 if true typically means that a loop or operation is being 501 represented. 502 * Whether a value is returned, as specified by 'returns_value' (true 503 by default). 504 * Whether the subprogram is a method, as specified by 'is_method' 505 (false by default). 506 * The 'params' (a parameter list which is empty by default). 507 * The 'star' parameter which collects excess positional arguments. 508 * The 'dstar' parameter which collects unmatched keyword arguments. 509 """ 510 511 Node.__init__(self, original, defining, name=name, module=module, structure=structure, 512 structures=structures, internal=internal, returns_value=returns_value, 513 is_method=is_method, params=(params or []), star=star, dstar=dstar, **kw) 514 515 WithName.__init__(self) 516 self.raises = set() 517 self.returns = set() 518 self.return_locals = set() 519 self.paramtypes = {} 520 self.namespace = Namespace() # NOTE: Temporary. 521 522 def specialisations(self): 523 524 "Return the active specialisations using only distinct instances." 525 526 distinct_instances = {} 527 528 subprograms = set() 529 for instance, subprogram in self.copies.items() or [(None, self)]: 530 if instance is None: 531 subprograms.add(subprogram) 532 continue 533 534 cls = instance.get_class() 535 if not distinct_instances.has_key(cls): 536 distinct_instances[cls] = cls.get_distinct_instances() 537 distinct_instance = distinct_instances[cls][instance] 538 if instance is distinct_instance: 539 subprograms.add(subprogram) 540 541 return subprograms 542 543 # vim: tabstop=4 expandtab shiftwidth=4