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