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", "star", "dstar" 167 invocation_attributes = "params", # not "args" - see "pos_args", "kw_args" 168 grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices" 169 170 def __init__(self, original=None, defining=0, **kw): 171 172 """ 173 Initialise a program node with a link to an optional 'original' AST 174 node. An optional 'defining' parameter (if set to a true value), sets 175 this node as the defining node in the original. 176 """ 177 178 self.original = original 179 self.defining = defining 180 self.copies = [] 181 182 if self.original is not None and defining: 183 self.original._node = self 184 for name, value in kw.items(): 185 setattr(self, name, value) 186 187 def __repr__(self): 188 189 "Return a readable representation." 190 191 if hasattr(self, "full_name"): 192 s = "%s '%s'" % (self.__class__.__name__, self.full_name()) 193 elif hasattr(self, "name"): 194 s = "%s '%s'" % (self.__class__.__name__, self.name) 195 elif hasattr(self, "index"): 196 s = "%s (%s)" % (self.__class__.__name__, self.index) 197 elif hasattr(self, "value"): 198 s = "%s %s" % (self.__class__.__name__, repr(self.value)) 199 elif hasattr(self, "ref"): 200 s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) 201 else: 202 s = "%s" % (self.__class__.__name__,) 203 204 # Annotations. 205 206 if hasattr(self, "types"): 207 return "%s -> %s" % (s, self.types) 208 else: 209 return s 210 211 def _pprint(self, indent, continuation, s, stream=None): 212 213 """ 214 Print, at the given 'indent' level, with the given 'continuation' text, 215 the string 's', either to the given, optional 'stream' or to standard 216 output, this node's "pretty" representation. 217 """ 218 219 stream = stream or sys.stdout 220 if continuation: 221 print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s 222 else: 223 print >>stream, (" " * indent) + s 224 225 def pprint(self, indent=0, continuation=None, stream=None): 226 227 """ 228 Print, at the given, optional 'indent', with the given optional 229 'continuation' text, either to the given, optional 'stream' or to 230 standard output, this node's "pretty" representation along with its 231 children and their "pretty" representation (and so on). 232 """ 233 234 stream = stream or sys.stdout 235 self._pprint(indent, continuation, repr(self), stream) 236 237 # Subprogram-related details. 238 239 if hasattr(self, "params"): 240 for name, default in self.params: 241 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 242 if hasattr(self, "star") and self.star: 243 name, default = self.star 244 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 245 if hasattr(self, "dstar") and self.dstar: 246 name, default = self.dstar 247 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 248 if getattr(self, "internal", 0): 249 self._pprint(indent + 2, "( ", "internal", stream=stream) 250 if getattr(self, "structure", 0): 251 self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) 252 253 # Expression-related details. 254 255 if hasattr(self, "expr"): 256 self.expr.pprint(indent + 2, "- ", stream=stream) 257 if hasattr(self, "nodes"): 258 for node in self.nodes: 259 node.pprint(indent + 2, "- ", stream=stream) 260 if hasattr(self, "lvalue"): 261 self.lvalue.pprint(indent + 2, "->", stream=stream) 262 if hasattr(self, "nstype"): 263 self._pprint(indent + 2, "", self.nstype, stream=stream) 264 if hasattr(self, "args"): 265 for arg in self.pos_args: 266 arg.pprint(indent + 2, "( ", stream=stream) 267 for name, arg in self.kw_args.items(): 268 arg.pprint(indent + 2, "( ", stream=stream) 269 if hasattr(self, "star") and self.star: 270 self.star.pprint(indent + 2, "( ", stream=stream) 271 if hasattr(self, "dstar") and self.dstar: 272 self.dstar.pprint(indent + 2, "( ", stream=stream) 273 274 # Statement-related details. 275 276 if hasattr(self, "test"): 277 self.test.pprint(indent + 2, "? ", stream=stream) 278 for attr in self.grouping_attributes: 279 if hasattr(self, attr) and getattr(self, attr): 280 self._pprint(indent, "", "%s {" % attr, stream=stream) 281 for node in getattr(self, attr): 282 node.pprint(indent + 2, stream=stream) 283 self._pprint(indent, "", "}", stream=stream) 284 285 # Annotations. 286 287 if hasattr(self, "accesses"): 288 self._pprint(indent, "", "--------", stream=stream) 289 for ref, attributes in self.accesses.items(): 290 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream) 291 self._pprint(indent, "", "--------", stream=stream) 292 if hasattr(self, "writes"): 293 self._pprint(indent, "", "--------", stream=stream) 294 for ref, attribute in self.writes.items(): 295 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) 296 self._pprint(indent, "", "--------", stream=stream) 297 298 # Node discovery functions. 299 300 def active(self): 301 302 "Return the active copies of this node or a list containing this node." 303 304 return self.copies or [self] 305 306 # Node manipulation functions. 307 308 def copy(self, new_name=None): 309 310 """ 311 Perform a deep copy of the node, optionally specifying a 'new_name', 312 returning a new unannotated copy. 313 """ 314 315 # Copy the common attributes of this node. 316 317 common = {} 318 for attr in self.common_attributes: 319 if hasattr(self, attr): 320 common[attr] = getattr(self, attr) 321 322 if new_name is not None: 323 common["copy_of"] = self 324 common["name"] = new_name 325 326 # Instantiate the copy, avoiding side-effects with original and defining. 327 328 node = self.__class__(**common) 329 node.defining = self.defining 330 331 # Add links to copies from originals. 332 333 self.copies.append(node) 334 335 # Copy attributes of different types. 336 337 for attr in self.expression_attributes: 338 if hasattr(self, attr): 339 n = getattr(self, attr) 340 if n is None: 341 n2 = n 342 else: 343 n2 = n.copy() 344 setattr(node, attr, n2) 345 346 for attr in self.invocation_attributes: 347 if hasattr(self, attr): 348 l = getattr(self, attr) 349 l2 = [] 350 for name, n in l: 351 if n is None: 352 l2.append((name, n)) 353 else: 354 l2.append((name, n.copy())) 355 setattr(node, attr, l2) 356 357 for attr in self.grouping_attributes: 358 if hasattr(self, attr): 359 l = getattr(self, attr) 360 setattr(node, attr, [n.copy() for n in l]) 361 362 # Arguments are usually processed further - "args" is useless. 363 364 if hasattr(self, "pos_args"): 365 node.pos_args = [n.copy() for n in self.pos_args] 366 367 if hasattr(self, "kw_args"): 368 node.kw_args = {} 369 for name, n in self.kw_args.items(): 370 node.kw_args[name] = n.copy() 371 372 return node 373 374 # Comparable nodes based on naming. 375 376 class Comparable(Node): 377 378 "Comparable nodes implementing the 'full_name' method." 379 380 def __eq__(self, other): 381 # NOTE: Single instance: all instances are the same 382 # NOTE: Multiple instances: all instances are different 383 if hasattr(other, "full_name"): 384 return self.full_name() == other.full_name() 385 else: 386 return NotImplemented 387 388 def __hash__(self): 389 return id(self) 390 391 # These are the supported "operations" described by simplified program nodes. 392 393 class Pass(Node): "A placeholder node corresponding to pass." 394 class Assign(Node): "A grouping node for assignment-related operations." 395 class Keyword(Node): "A grouping node for keyword arguments." 396 class Global(Node): "A global name designator." 397 class Import(Node): "A module import operation." 398 class LoadTemp(Node): "Load a previously-stored temporary value." 399 class LoadName(Node): "Load a named object." 400 class LoadAttr(Node): "Load an object attribute." 401 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 402 class LoadExc(Node): "Load a handled exception." 403 class ResetExc(Node): "Reset the exception state." 404 class StoreTemp(Node): "Store a temporary value." 405 class StoreName(Node): "Associate a name with an object." 406 class StoreAttr(Node): "Associate an object's attribute with a value." 407 class ReleaseTemp(Node): "Release a temporary value." 408 class Try(Node): "A try...except...else...finally grouping node." 409 class Raise(Node): "An exception raising node." 410 class Not(Node): "A negation of an expression." 411 class CheckType(Node): "Check a value's type from a list of choices." 412 413 # There are two types of return node: return from function and return from 414 # block. 415 416 class Return(Node): 417 418 "Return an evaluated expression." 419 420 pass 421 422 class ReturnFromFunction(Return): 423 pass 424 425 class ReturnFromBlock(Return): 426 pass 427 428 # Some behaviour is set as the default in conditional nodes but may be 429 # overridden. 430 431 class Conditional(Node): 432 433 "A conditional node consisting of a test and outcomes." 434 435 def __init__(self, *args, **kw): 436 self.isolate_test = 0 437 Node.__init__(self, *args, **kw) 438 439 # Invocations involve some more work to process calculated attributes. 440 441 class Invoke(Node): 442 443 "An invocation." 444 445 pass 446 447 class InvokeFunction(Invoke): 448 449 "A function or method invocation." 450 451 def __init__(self, *args, **kw): 452 self.args = [] 453 self.star = None 454 self.dstar = None 455 Invoke.__init__(self, *args, **kw) 456 self.set_args(self.args) 457 self.share_locals = 0 458 459 def set_args(self, args): 460 461 "Sort the 'args' into positional and keyword arguments." 462 463 self.pos_args = [] 464 self.kw_args = {} 465 add_kw = 0 466 for arg in args: 467 if not add_kw: 468 if not isinstance(arg, Keyword): 469 self.pos_args.append(arg) 470 else: 471 add_kw = 1 472 if add_kw: 473 if isinstance(arg, Keyword): 474 self.kw_args[arg.name] = arg.expr 475 else: 476 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 477 478 class InvokeBlock(Invoke): 479 480 "A block or loop invocation." 481 482 def __init__(self, *args, **kw): 483 self.share_locals = 1 484 Invoke.__init__(self, *args, **kw) 485 486 # Program structure nodes. 487 488 class Subprogram(Node, WithName): 489 490 "A subprogram: functions, methods and loops." 491 492 def __init__(self, *args, **kw): 493 Node.__init__(self, *args, **kw) 494 WithName.__init__(self) 495 496 class Module(Comparable): 497 498 "A Python module." 499 500 def full_name(self): 501 return "module %s" % self.name 502 503 # Special non-program nodes. 504 505 class Structure(Comparable): "A non-program node containing some kind of namespace." 506 507 class _Class(Structure, WithName): 508 509 "A Python class." 510 511 def __init__(self, *args, **kw): 512 Structure.__init__(self, *args, **kw) 513 WithName.__init__(self) 514 515 def full_name(self): 516 return "class %s" % self._full_name 517 518 class SingleInstanceClass(_Class): 519 520 "A Python class." 521 522 def __init__(self, *args, **kw): 523 _Class.__init__(self, *args, **kw) 524 self.instance = None 525 526 def has_instance(self, node): 527 return self.instance is not None 528 529 def add_instance(self, node, instance): 530 self.instance = instance 531 532 def get_instance(self, node): 533 return self.instance 534 535 def get_instance_name(self, instance): 536 return self._full_name 537 538 # Attribute propagation. 539 540 def get_attribute_for_instance(self, attribute, instance): 541 return attribute 542 543 class MultipleInstanceClass(_Class): 544 545 "A Python class." 546 547 def __init__(self, *args, **kw): 548 _Class.__init__(self, *args, **kw) 549 self.instances = {} 550 self.attributes_for_instances = {} 551 552 def _get_key(self, node): 553 return id(getattr(node, "original", None)) # self.module.original 554 555 def has_instance(self, node): 556 return self.instances.has_key(self._get_key(node)) 557 558 def add_instance(self, node, instance): 559 self.instances[self._get_key(node)] = instance 560 561 def get_instance(self, node): 562 return self.instances[self._get_key(node)] 563 564 def get_instance_name(self, instance): 565 return name(instance, self._full_name) 566 567 # Attribute propagation. 568 569 def get_attribute_for_instance(self, attribute, instance): 570 if isinstance(attribute.type, Subprogram): 571 subprogram = attribute.type 572 key = (subprogram, instance) 573 if not self.attributes_for_instances.has_key(key): 574 self.attributes_for_instances[key] = Attribute(attribute.context, subprogram.copy(subprogram.full_name())) 575 return self.attributes_for_instances[key] 576 else: 577 return attribute 578 579 class SelectiveMultipleInstanceClass(MultipleInstanceClass): 580 581 "A Python class which provides multiple instances depending on the class." 582 583 def _get_key(self, node): 584 if self.namespace.has_key("__atomic__"): 585 return id(self) 586 else: 587 return MultipleInstanceClass._get_key(self, node) 588 589 class Instance(Structure): 590 591 "An instance." 592 593 def full_name(self): 594 return self.get_class().get_instance_name(self) 595 596 def get_class(self): 597 return self.namespace.load("__class__")[0].type 598 599 def __repr__(self): 600 return "Instance of type '%s'" % self.full_name() 601 602 def __eq__(self, other): 603 # NOTE: Single instance: all instances are the same 604 # NOTE: Multiple instances: all instances are different 605 return self.full_name() == other.full_name() 606 607 def __hash__(self): 608 return id(self) 609 610 class Constant(Instance): 611 612 "A constant initialised with a type name for future processing." 613 614 def __init__(self, *args, **kw): 615 Instance.__init__(self, *args, **kw) 616 self.typename = self.value.__class__.__name__ 617 618 # NOTE: Hacked full_name avoiding instantiation ordering issues: 619 # NOTE: initialise built-in types, initialise built-in constants. 620 621 #def full_name(self): 622 # return self.typename + "-c" 623 624 class Attribute: 625 626 """ 627 An attribute abstraction, indicating the type of the attribute along with 628 its context or origin. 629 """ 630 631 def __init__(self, context, type): 632 self.context = context 633 self.type = type 634 635 def __eq__(self, other): 636 return hasattr(other, "type") and other.type == self.type or other == self.type 637 638 def __repr__(self): 639 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 640 641 def __hash__(self): 642 return id(self) 643 644 # Additional program and AST nodes. 645 646 class Self: 647 648 """ 649 A program node encapsulating object/context information in an argument list. 650 This is not particularly like Attribute, Class, Instance or other such 651 things, since it actually appears in the program representation. 652 """ 653 654 def __init__(self, attribute): 655 self.types = [attribute] 656 657 class Op: 658 659 "A replacement AST node representing an operation in a Compare construct." 660 661 def __init__(self, name, expr): 662 self.name = name 663 self.expr = expr 664 665 # Configuration setting. 666 667 Class = SingleInstanceClass 668 #Class = MultipleInstanceClass 669 670 def set_single_instance_mode(): 671 global Class 672 Class = SingleInstanceClass 673 674 def set_multiple_instance_mode(): 675 global Class 676 Class = MultipleInstanceClass 677 678 def set_selective_multiple_instance_mode(): 679 global Class 680 Class = SelectiveMultipleInstanceClass 681 682 # vim: tabstop=4 expandtab shiftwidth=4