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["name"] = new_name 304 305 # Instantiate the copy, avoiding side-effects with original and defining. 306 307 node = self.__class__(**common) 308 node.defining = self.defining 309 310 # Add links to copied nodes from original AST nodes. 311 312 if node.original is not None and node.defining: 313 if not hasattr(node.original, "_nodes"): 314 node.original._nodes = [] 315 node.original._nodes.append(node) 316 317 # Copy attributes of different types. 318 319 for attr in self.expression_attributes: 320 if hasattr(self, attr): 321 n = getattr(self, attr) 322 if n is None: 323 n2 = n 324 else: 325 n2 = n.copy() 326 setattr(node, attr, n2) 327 328 for attr in self.invocation_attributes: 329 if hasattr(self, attr): 330 l = getattr(self, attr) 331 l2 = [] 332 for name, n in l: 333 if n is None: 334 l2.append((name, n)) 335 else: 336 l2.append((name, n.copy())) 337 setattr(node, attr, l2) 338 339 for attr in self.grouping_attributes: 340 if hasattr(self, attr): 341 l = getattr(self, attr) 342 setattr(node, attr, [n.copy() for n in l]) 343 344 # Arguments are usually processed further - "args" is useless. 345 346 if hasattr(self, "pos_args"): 347 node.pos_args = [n.copy() for n in self.pos_args] 348 349 if hasattr(self, "kw_args"): 350 node.kw_args = {} 351 for name, n in self.kw_args.items(): 352 node.kw_args[name] = n.copy() 353 354 return node 355 356 # These are the supported "operations" described by simplified program nodes. 357 358 class Pass(Node): "A placeholder node corresponding to pass." 359 class Assign(Node): "A grouping node for assignment-related operations." 360 class Keyword(Node): "A grouping node for keyword arguments." 361 class Global(Node): "A global name designator." 362 class Import(Node): "A module import operation." 363 class LoadTemp(Node): "Load a previously-stored temporary value." 364 class LoadName(Node): "Load a named object." 365 class LoadAttr(Node): "Load an object attribute." 366 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 367 class LoadExc(Node): "Load a handled exception." 368 class CheckExc(Node): "Check a handled exception." 369 class StoreTemp(Node): "Store a temporary value." 370 class StoreName(Node): "Associate a name with an object." 371 class StoreAttr(Node): "Associate an object's attribute with a value." 372 class ReleaseTemp(Node): "Release a temporary value." 373 class Try(Node): "A try...except...else...finally grouping node." 374 class Raise(Node): "An exception raising node." 375 class Not(Node): "A negation of an expression." 376 377 # There are two types of return node: return from function and return from 378 # block. 379 380 class Return(Node): 381 382 "Return an evaluated expression." 383 384 pass 385 386 class ReturnFromFunction(Return): 387 pass 388 389 class ReturnFromBlock(Return): 390 pass 391 392 # Some behaviour is set as the default in conditional nodes but may be 393 # overridden. 394 395 class Conditional(Node): 396 397 "A conditional node consisting of a test and outcomes." 398 399 def __init__(self, *args, **kw): 400 self.isolate_test = 0 401 Node.__init__(self, *args, **kw) 402 403 # Invocations involve some more work to process calculated attributes. 404 405 class Invoke(Node): 406 407 "An invocation." 408 409 pass 410 411 class InvokeFunction(Invoke): 412 413 "A function or method invocation." 414 415 def __init__(self, *args, **kw): 416 self.args = [] 417 self.star = None 418 self.dstar = None 419 Invoke.__init__(self, *args, **kw) 420 self.set_args(self.args) 421 self.share_locals = 0 422 423 def set_args(self, args): 424 425 "Sort the 'args' into positional and keyword arguments." 426 427 self.pos_args = [] 428 self.kw_args = {} 429 add_kw = 0 430 for arg in args: 431 if not add_kw: 432 if not isinstance(arg, Keyword): 433 self.pos_args.append(arg) 434 else: 435 add_kw = 1 436 if add_kw: 437 if isinstance(arg, Keyword): 438 self.kw_args[arg.name] = arg.expr 439 else: 440 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 441 442 class InvokeBlock(Invoke): 443 444 "A block or loop invocation." 445 446 def __init__(self, *args, **kw): 447 self.share_locals = 1 448 Invoke.__init__(self, *args, **kw) 449 450 # Named nodes are those which can be referenced in some way. 451 452 class WithName: 453 454 "Node naming." 455 456 def __init__(self): 457 self._full_name = name(self, self.name or "$untitled") 458 459 def full_name(self): 460 return self._full_name 461 462 # Program structure nodes. 463 464 class Subprogram(Node, WithName): 465 466 "A subprogram: functions, methods and loops." 467 468 def __init__(self, *args, **kw): 469 Node.__init__(self, *args, **kw) 470 WithName.__init__(self) 471 472 class Comparable(Node): 473 474 "Comparable nodes implementing the 'full_name' method." 475 476 def __eq__(self, other): 477 # NOTE: Single instance: all instances are the same 478 # NOTE: Multiple instances: all instances are different 479 if hasattr(other, "full_name"): 480 return self.full_name() == other.full_name() 481 else: 482 return NotImplemented 483 484 def __hash__(self): 485 return id(self) 486 487 class Module(Comparable): 488 489 "A Python module." 490 491 def full_name(self): 492 return "module %s" % self.name 493 494 # Special non-program nodes. 495 496 class Structure(Comparable): "A non-program node containing some kind of namespace." 497 498 class _Class(Structure, WithName): 499 500 "A Python class." 501 502 def __init__(self, *args, **kw): 503 Structure.__init__(self, *args, **kw) 504 WithName.__init__(self) 505 506 def full_name(self): 507 return "class %s" % self._full_name 508 509 class SingleInstanceClass(_Class): 510 511 "A Python class." 512 513 def __init__(self, *args, **kw): 514 _Class.__init__(self, *args, **kw) 515 self.instance = None 516 517 def has_instance(self, node): 518 return self.instance is not None 519 520 def add_instance(self, node, instance): 521 self.instance = instance 522 523 def get_instance(self, node): 524 return self.instance 525 526 def get_instance_name(self, instance): 527 return self._full_name 528 529 # Attribute propagation. 530 531 def get_attribute_for_instance(self, attribute, instance): 532 return attribute 533 534 class MultipleInstanceClass(_Class): 535 536 "A Python class." 537 538 def __init__(self, *args, **kw): 539 _Class.__init__(self, *args, **kw) 540 self.instances = {} 541 self.attributes_for_instances = {} 542 543 def _get_key(self, node): 544 return id(getattr(node, "original", None)) # self.module.original 545 546 def has_instance(self, node): 547 return self.instances.has_key(self._get_key(node)) 548 549 def add_instance(self, node, instance): 550 self.instances[self._get_key(node)] = instance 551 552 def get_instance(self, node): 553 return self.instances[self._get_key(node)] 554 555 def get_instance_name(self, instance): 556 return name(instance, self._full_name) 557 558 # Attribute propagation. 559 560 def get_attribute_for_instance(self, attribute, instance): 561 if isinstance(attribute.type, Subprogram): 562 subprogram = attribute.type 563 key = (subprogram, instance) 564 if not self.attributes_for_instances.has_key(key): 565 self.attributes_for_instances[key] = Attribute(attribute.context, subprogram.copy(subprogram.full_name())) 566 return self.attributes_for_instances[key] 567 else: 568 return attribute 569 570 class Instance(Structure): 571 572 "An instance." 573 574 def full_name(self): 575 return self.get_class().get_instance_name(self) 576 577 def get_class(self): 578 return self.namespace.load("__class__")[0].type 579 580 def __repr__(self): 581 return "Instance of type '%s'" % self.full_name() 582 583 def __eq__(self, other): 584 # NOTE: Single instance: all instances are the same 585 # NOTE: Multiple instances: all instances are different 586 return self.full_name() == other.full_name() 587 588 def __hash__(self): 589 return id(self) 590 591 class Constant(Instance): 592 593 "A constant initialised with a type name for future processing." 594 595 def __init__(self, *args, **kw): 596 Instance.__init__(self, *args, **kw) 597 self.typename = self.value.__class__.__name__ 598 599 # NOTE: Hacked full_name avoiding instantiation ordering issues: 600 # NOTE: initialise built-in types, initialise built-in constants. 601 602 #def full_name(self): 603 # return self.typename + "-c" 604 605 class Attribute: 606 607 """ 608 An attribute abstraction, indicating the type of the attribute along with 609 its context or origin. 610 """ 611 612 def __init__(self, context, type): 613 self.context = context 614 self.type = type 615 616 def __eq__(self, other): 617 return hasattr(other, "type") and other.type == self.type or other == self.type 618 619 def __repr__(self): 620 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 621 622 def __hash__(self): 623 return id(self) 624 625 class Self: 626 627 """ 628 A program node encapsulating object/context information in an argument list. 629 This is not particularly like Attribute, Class, Instance or other such 630 things, since it actually appears in the program representation. 631 """ 632 633 def __init__(self, attribute): 634 self.types = [attribute] 635 636 # Configuration setting. 637 638 Class = SingleInstanceClass 639 #Class = MultipleInstanceClass 640 641 def set_single_instance_mode(): 642 global Class 643 Class = SingleInstanceClass 644 645 def set_multiple_instance_mode(): 646 global Class 647 Class = MultipleInstanceClass 648 649 # vim: tabstop=4 expandtab shiftwidth=4