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 compiler.visitor import ASTVisitor 27 import sys 28 29 # Exceptions. 30 31 class SimplifiedError(Exception): 32 33 "An error in the annotation process." 34 35 def __init__(self, exc, node, *args): 36 37 """ 38 Initialise the error with an existing exception 'exc', the 'node' at 39 which this error occurs, along with additional optional arguments. 40 """ 41 42 Exception.__init__(self, *args) 43 self.nodes = [node] 44 self.exc = exc 45 46 def add(self, node): 47 48 "Add the given 'node' to the path of nodes leading from the exception." 49 50 self.nodes.append(node) 51 52 def __str__(self): 53 54 "Return a string showing the principal exception details." 55 56 return "%s, %s" % (self.exc, self.nodes) 57 58 # Unique name registration. 59 60 class Naming: 61 62 "Maintain records of unique names for each simple name." 63 64 index_separator = "-" 65 66 def __init__(self): 67 self.obj_to_name = {} 68 self.names = {} 69 70 def get(self, obj): 71 return self.obj_to_name[obj] 72 73 def set(self, obj, name): 74 if self.obj_to_name.has_key(obj): 75 return 76 if not self.names.has_key(name): 77 self.names[name] = 0 78 n = self.names[name] + 1 79 self.names[name] = n 80 self.obj_to_name[obj] = "%s%s%d" % (name, self.index_separator, n) 81 82 naming = Naming() 83 84 def name(obj, name): 85 86 "Return a unique name for the given 'obj', indicating the base 'name'." 87 88 naming.set(obj, name) 89 return naming.get(obj) 90 91 # Elementary visitor support. 92 93 class Visitor(ASTVisitor): 94 95 "A visitor base class." 96 97 def __init__(self): 98 ASTVisitor.__init__(self) 99 100 def default(self, node, *args): 101 raise ValueError, node.__class__ 102 103 def dispatch(self, node, *args): 104 return ASTVisitor.dispatch(self, node, *args) 105 106 def dispatches(self, nodes, *args): 107 results = [] 108 for node in nodes: 109 results.append(self.dispatch(node, *args)) 110 return results 111 112 def dispatch_dict(self, d, *args): 113 results = {} 114 for name, node in d.items(): 115 results[name] = self.dispatch(node, *args) 116 return results 117 118 # Simplified program nodes. 119 120 class Node: 121 122 """ 123 A result node with common attributes: 124 125 original The original node from which this node was created. 126 defining Whether the node defines something in the original program. 127 name Any name involved (variable or attribute). 128 index Any index involved (temporary variable name). 129 value Any constant value. 130 ref Any reference to (for example) subprograms. 131 nstype Any indication of the namespace type involved in a name access. 132 133 Expression-related attributes: 134 135 expr Any contributing expression. 136 lvalue Any target expression. 137 test Any test expression in a conditional instruction. 138 139 Invocation and subprogram attributes: 140 141 args Any collection of argument nodes. 142 params Any collection of parameter nodes and defaults. 143 144 Statement-grouping attributes: 145 146 body Any conditional code depending on the success of a test. 147 else_ Any conditional code depending on the failure of a test. 148 handler Any exception handler code. 149 finally_ Any code which will be executed regardless. 150 code Any unconditional code. 151 choices Any choices which may be included in the final program. 152 """ 153 154 common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original" 155 expression_attributes = "expr", "lvalue", "test", "star", "dstar" 156 invocation_attributes = "params", # not "args" - see "pos_args", "kw_args" 157 grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices" 158 159 def __init__(self, original=None, defining=0, **kw): 160 161 """ 162 Initialise a program node with a link to an optional 'original' AST 163 node. An optional 'defining' parameter (if set to a true value), sets 164 this node as the defining node in the original. 165 """ 166 167 self.original = original 168 self.defining = defining 169 170 if self.original is not None and defining: 171 self.original._node = self 172 for name, value in kw.items(): 173 setattr(self, name, value) 174 175 def __repr__(self): 176 177 "Return a readable representation." 178 179 if hasattr(self, "full_name"): 180 s = "%s '%s'" % (self.__class__.__name__, self.full_name()) 181 elif hasattr(self, "name"): 182 s = "%s '%s'" % (self.__class__.__name__, self.name) 183 elif hasattr(self, "index"): 184 s = "%s (%s)" % (self.__class__.__name__, self.index) 185 elif hasattr(self, "value"): 186 s = "%s %s" % (self.__class__.__name__, repr(self.value)) 187 elif hasattr(self, "ref"): 188 s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) 189 else: 190 s = "%s" % (self.__class__.__name__,) 191 192 # Annotations. 193 194 if hasattr(self, "types"): 195 return "%s -> %s" % (s, self.types) 196 else: 197 return s 198 199 def _pprint(self, indent, continuation, s, stream=None): 200 201 """ 202 Print, at the given 'indent' level, with the given 'continuation' text, 203 the string 's', either to the given, optional 'stream' or to standard 204 output, this node's "pretty" representation. 205 """ 206 207 stream = stream or sys.stdout 208 if continuation: 209 print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s 210 else: 211 print >>stream, (" " * indent) + s 212 213 def pprint(self, indent=0, continuation=None, stream=None): 214 215 """ 216 Print, at the given, optional 'indent', with the given optional 217 'continuation' text, either to the given, optional 'stream' or to 218 standard output, this node's "pretty" representation along with its 219 children and their "pretty" representation (and so on). 220 """ 221 222 stream = stream or sys.stdout 223 self._pprint(indent, continuation, repr(self), stream) 224 225 # Subprogram-related details. 226 227 if hasattr(self, "params"): 228 for name, default in self.params: 229 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 230 if hasattr(self, "star") and self.star: 231 name, default = self.star 232 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 233 if hasattr(self, "dstar") and self.dstar: 234 name, default = self.dstar 235 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 236 if getattr(self, "internal", 0): 237 self._pprint(indent + 2, "( ", "internal", stream=stream) 238 if getattr(self, "structure", 0): 239 self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) 240 241 # Expression-related details. 242 243 if hasattr(self, "expr"): 244 self.expr.pprint(indent + 2, "- ", stream=stream) 245 if hasattr(self, "nodes"): 246 for node in self.nodes: 247 node.pprint(indent + 2, "- ", stream=stream) 248 if hasattr(self, "lvalue"): 249 self.lvalue.pprint(indent + 2, "->", stream=stream) 250 if hasattr(self, "nstype"): 251 self._pprint(indent + 2, "", self.nstype, stream=stream) 252 if hasattr(self, "args"): 253 for arg in self.pos_args: 254 arg.pprint(indent + 2, "( ", stream=stream) 255 for name, arg in self.kw_args.items(): 256 arg.pprint(indent + 2, "( ", stream=stream) 257 if hasattr(self, "star") and self.star: 258 self.star.pprint(indent + 2, "( ", stream=stream) 259 if hasattr(self, "dstar") and self.dstar: 260 self.dstar.pprint(indent + 2, "( ", stream=stream) 261 262 # Statement-related details. 263 264 if hasattr(self, "test"): 265 self.test.pprint(indent + 2, "? ", stream=stream) 266 for attr in self.grouping_attributes: 267 if hasattr(self, attr) and getattr(self, attr): 268 self._pprint(indent, "", "%s {" % attr, stream=stream) 269 for node in getattr(self, attr): 270 node.pprint(indent + 2, stream=stream) 271 self._pprint(indent, "", "}", stream=stream) 272 273 # Annotations. 274 275 if hasattr(self, "accesses"): 276 self._pprint(indent, "", "--------", stream=stream) 277 for ref, attributes in self.accesses.items(): 278 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream) 279 self._pprint(indent, "", "--------", stream=stream) 280 if hasattr(self, "writes"): 281 self._pprint(indent, "", "--------", stream=stream) 282 for ref, attribute in self.writes.items(): 283 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) 284 self._pprint(indent, "", "--------", stream=stream) 285 286 # Node manipulation functions. 287 288 def copy(self, new_name=None): 289 290 """ 291 Perform a deep copy of the node, optionally specifying a 'new_name', 292 returning a new unannotated copy. 293 """ 294 295 # Copy the common attributes of this node. 296 297 common = {} 298 for attr in self.common_attributes: 299 if hasattr(self, attr): 300 common[attr] = getattr(self, attr) 301 302 if new_name is not None: 303 common["copy_of"] = self 304 common["name"] = new_name 305 306 # Instantiate the copy, avoiding side-effects with original and defining. 307 308 node = self.__class__(**common) 309 node.defining = self.defining 310 311 # Add links to copied nodes from original AST nodes. 312 313 if node.original is not None and node.defining: 314 if not hasattr(node.original, "_nodes"): 315 node.original._nodes = [] 316 node.original._nodes.append(node) 317 318 # Copy attributes of different types. 319 320 for attr in self.expression_attributes: 321 if hasattr(self, attr): 322 n = getattr(self, attr) 323 if n is None: 324 n2 = n 325 else: 326 n2 = n.copy() 327 setattr(node, attr, n2) 328 329 for attr in self.invocation_attributes: 330 if hasattr(self, attr): 331 l = getattr(self, attr) 332 l2 = [] 333 for name, n in l: 334 if n is None: 335 l2.append((name, n)) 336 else: 337 l2.append((name, n.copy())) 338 setattr(node, attr, l2) 339 340 for attr in self.grouping_attributes: 341 if hasattr(self, attr): 342 l = getattr(self, attr) 343 setattr(node, attr, [n.copy() for n in l]) 344 345 # Arguments are usually processed further - "args" is useless. 346 347 if hasattr(self, "pos_args"): 348 node.pos_args = [n.copy() for n in self.pos_args] 349 350 if hasattr(self, "kw_args"): 351 node.kw_args = {} 352 for name, n in self.kw_args.items(): 353 node.kw_args[name] = n.copy() 354 355 return node 356 357 # These are the supported "operations" described by simplified program nodes. 358 359 class Pass(Node): "A placeholder node corresponding to pass." 360 class Assign(Node): "A grouping node for assignment-related operations." 361 class Keyword(Node): "A grouping node for keyword arguments." 362 class Global(Node): "A global name designator." 363 class Import(Node): "A module import operation." 364 class LoadTemp(Node): "Load a previously-stored temporary value." 365 class LoadName(Node): "Load a named object." 366 class LoadAttr(Node): "Load an object attribute." 367 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 368 class LoadExc(Node): "Load a handled exception." 369 class CheckExc(Node): "Check a handled exception." 370 class ResetExc(Node): "Reset the exception state." 371 class StoreTemp(Node): "Store a temporary value." 372 class StoreName(Node): "Associate a name with an object." 373 class StoreAttr(Node): "Associate an object's attribute with a value." 374 class ReleaseTemp(Node): "Release a temporary value." 375 class Try(Node): "A try...except...else...finally grouping node." 376 class Raise(Node): "An exception raising node." 377 class Not(Node): "A negation of an expression." 378 379 # There are two types of return node: return from function and return from 380 # block. 381 382 class Return(Node): 383 384 "Return an evaluated expression." 385 386 pass 387 388 class ReturnFromFunction(Return): 389 pass 390 391 class ReturnFromBlock(Return): 392 pass 393 394 # Some behaviour is set as the default in conditional nodes but may be 395 # overridden. 396 397 class Conditional(Node): 398 399 "A conditional node consisting of a test and outcomes." 400 401 def __init__(self, *args, **kw): 402 self.isolate_test = 0 403 Node.__init__(self, *args, **kw) 404 405 # Invocations involve some more work to process calculated attributes. 406 407 class Invoke(Node): 408 409 "An invocation." 410 411 pass 412 413 class InvokeFunction(Invoke): 414 415 "A function or method invocation." 416 417 def __init__(self, *args, **kw): 418 self.args = [] 419 self.star = None 420 self.dstar = None 421 Invoke.__init__(self, *args, **kw) 422 self.set_args(self.args) 423 self.share_locals = 0 424 425 def set_args(self, args): 426 427 "Sort the 'args' into positional and keyword arguments." 428 429 self.pos_args = [] 430 self.kw_args = {} 431 add_kw = 0 432 for arg in args: 433 if not add_kw: 434 if not isinstance(arg, Keyword): 435 self.pos_args.append(arg) 436 else: 437 add_kw = 1 438 if add_kw: 439 if isinstance(arg, Keyword): 440 self.kw_args[arg.name] = arg.expr 441 else: 442 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 443 444 class InvokeBlock(Invoke): 445 446 "A block or loop invocation." 447 448 def __init__(self, *args, **kw): 449 self.share_locals = 1 450 Invoke.__init__(self, *args, **kw) 451 452 # Named nodes are those which can be referenced in some way. 453 454 class WithName: 455 456 "Node naming." 457 458 def __init__(self): 459 self._full_name = name(self, self.name or "$untitled") 460 461 def full_name(self): 462 return self._full_name 463 464 # Program structure nodes. 465 466 class Subprogram(Node, WithName): 467 468 "A subprogram: functions, methods and loops." 469 470 def __init__(self, *args, **kw): 471 Node.__init__(self, *args, **kw) 472 WithName.__init__(self) 473 474 class Comparable(Node): 475 476 "Comparable nodes implementing the 'full_name' method." 477 478 def __eq__(self, other): 479 # NOTE: Single instance: all instances are the same 480 # NOTE: Multiple instances: all instances are different 481 if hasattr(other, "full_name"): 482 return self.full_name() == other.full_name() 483 else: 484 return NotImplemented 485 486 def __hash__(self): 487 return id(self) 488 489 class Module(Comparable): 490 491 "A Python module." 492 493 def full_name(self): 494 return "module %s" % self.name 495 496 # Special non-program nodes. 497 498 class Structure(Comparable): "A non-program node containing some kind of namespace." 499 500 class _Class(Structure, WithName): 501 502 "A Python class." 503 504 def __init__(self, *args, **kw): 505 Structure.__init__(self, *args, **kw) 506 WithName.__init__(self) 507 508 def full_name(self): 509 return "class %s" % self._full_name 510 511 class SingleInstanceClass(_Class): 512 513 "A Python class." 514 515 def __init__(self, *args, **kw): 516 _Class.__init__(self, *args, **kw) 517 self.instance = None 518 519 def has_instance(self, node): 520 return self.instance is not None 521 522 def add_instance(self, node, instance): 523 self.instance = instance 524 525 def get_instance(self, node): 526 return self.instance 527 528 def get_instance_name(self, instance): 529 return self._full_name 530 531 # Attribute propagation. 532 533 def get_attribute_for_instance(self, attribute, instance): 534 return attribute 535 536 class MultipleInstanceClass(_Class): 537 538 "A Python class." 539 540 def __init__(self, *args, **kw): 541 _Class.__init__(self, *args, **kw) 542 self.instances = {} 543 self.attributes_for_instances = {} 544 545 def _get_key(self, node): 546 return id(getattr(node, "original", None)) # self.module.original 547 548 def has_instance(self, node): 549 return self.instances.has_key(self._get_key(node)) 550 551 def add_instance(self, node, instance): 552 self.instances[self._get_key(node)] = instance 553 554 def get_instance(self, node): 555 return self.instances[self._get_key(node)] 556 557 def get_instance_name(self, instance): 558 return name(instance, self._full_name) 559 560 # Attribute propagation. 561 562 def get_attribute_for_instance(self, attribute, instance): 563 if isinstance(attribute.type, Subprogram): 564 subprogram = attribute.type 565 key = (subprogram, instance) 566 if not self.attributes_for_instances.has_key(key): 567 self.attributes_for_instances[key] = Attribute(attribute.context, subprogram.copy(subprogram.full_name())) 568 return self.attributes_for_instances[key] 569 else: 570 return attribute 571 572 class Instance(Structure): 573 574 "An instance." 575 576 def full_name(self): 577 return self.get_class().get_instance_name(self) 578 579 def get_class(self): 580 return self.namespace.load("__class__")[0].type 581 582 def __repr__(self): 583 return "Instance of type '%s'" % self.full_name() 584 585 def __eq__(self, other): 586 # NOTE: Single instance: all instances are the same 587 # NOTE: Multiple instances: all instances are different 588 return self.full_name() == other.full_name() 589 590 def __hash__(self): 591 return id(self) 592 593 class Constant(Instance): 594 595 "A constant initialised with a type name for future processing." 596 597 def __init__(self, *args, **kw): 598 Instance.__init__(self, *args, **kw) 599 self.typename = self.value.__class__.__name__ 600 601 # NOTE: Hacked full_name avoiding instantiation ordering issues: 602 # NOTE: initialise built-in types, initialise built-in constants. 603 604 #def full_name(self): 605 # return self.typename + "-c" 606 607 class Attribute: 608 609 """ 610 An attribute abstraction, indicating the type of the attribute along with 611 its context or origin. 612 """ 613 614 def __init__(self, context, type): 615 self.context = context 616 self.type = type 617 618 def __eq__(self, other): 619 return hasattr(other, "type") and other.type == self.type or other == self.type 620 621 def __repr__(self): 622 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 623 624 def __hash__(self): 625 return id(self) 626 627 class Self: 628 629 """ 630 A program node encapsulating object/context information in an argument list. 631 This is not particularly like Attribute, Class, Instance or other such 632 things, since it actually appears in the program representation. 633 """ 634 635 def __init__(self, attribute): 636 self.types = [attribute] 637 638 # Configuration setting. 639 640 Class = SingleInstanceClass 641 #Class = MultipleInstanceClass 642 643 def set_single_instance_mode(): 644 global Class 645 Class = SingleInstanceClass 646 647 def set_multiple_instance_mode(): 648 global Class 649 Class = MultipleInstanceClass 650 651 # vim: tabstop=4 expandtab shiftwidth=4