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