1 #!/usr/bin/env python 2 3 """ 4 Annotate program node structures. The code in this module operates upon nodes 5 which are produced when simplifying AST node trees originating from the compiler 6 module. 7 8 Copyright (C) 2006 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 27 To use this module, the easiest approach is to use the annotate function: 28 29 annotate(module, builtins) 30 31 The more complicated approach involves obtaining an Annotator: 32 33 annotator = Annotator() 34 35 Then, processing an existing module with it: 36 37 annotator.process(module) 38 39 If a module containing built-in classes and functions has already been 40 annotated, such a module should be passed in as an additional argument: 41 42 annotator.process(module, builtins) 43 """ 44 45 from simplified import * 46 import compiler 47 48 class System: 49 50 """ 51 A class maintaining the state of the annotation system. When the system 52 counter can no longer be incremented by any annotation operation, the 53 system may be considered stable and fully annotated. 54 """ 55 56 def __init__(self): 57 self.count = 0 58 def init(self, node): 59 if not hasattr(node, "types"): 60 node.types = [] 61 def annotate(self, node, types): 62 self.init(node) 63 for type in types: 64 if type not in node.types: 65 node.types.append(type) 66 self.count += 1 67 68 system = System() 69 70 # Exceptions. 71 72 class AnnotationError(Exception): 73 def __init__(self, exc, node, *args): 74 Exception.__init__(self, *args) 75 self.nodes = [node] 76 self.exc = exc 77 def add(self, node): 78 self.nodes.append(node) 79 def __str__(self): 80 return "%s, %s" % (self.exc, self.nodes) 81 82 class AnnotationMessage(Exception): 83 pass 84 85 # Annotation. 86 87 class Annotator(Visitor): 88 89 """ 90 The type annotator which traverses the program nodes, typically depth-first, 91 and maintains a record of the current set of types applying to the currently 92 considered operation. Such types are also recorded on the nodes, and a 93 special "system" record is maintained to monitor the level of annotation 94 activity with a view to recognising when no more annotations are possible. 95 96 Throughout the annotation activity, type information consists of lists of 97 Attribute objects where such objects retain information about the context of 98 the type (since a value in the program may be associated with an object or 99 class) and the actual type of the value being manipulated. Upon accessing 100 attribute information on namespaces, additional accessor information is also 101 exchanged - this provides a means of distinguishing between the different 102 types possible when the means of constructing the namespace may depend on 103 run-time behaviour. 104 """ 105 106 def __init__(self): 107 108 "Initialise the visitor." 109 110 Visitor.__init__(self) 111 self.system = system 112 113 # Satisfy visitor issues. 114 115 self.visitor = self 116 117 def process(self, module, builtins=None): 118 119 """ 120 Process the given 'module', using the optional 'builtins' to access 121 built-in classes and functions. 122 """ 123 124 self.subprograms = [] 125 self.current_subprograms = [] 126 self.current_namespaces = [] 127 128 # Give constants their own namespace. 129 130 for value, constant in module.simplifier.constants.items(): 131 constant.namespace = Namespace() 132 133 # Process the module, supplying builtins if possible. 134 135 self.global_namespace = Namespace() 136 137 if builtins is not None: 138 self.builtins_namespace = builtins.namespace 139 else: 140 self.builtins_namespace = self.global_namespace 141 142 return self.process_node(module) 143 144 def process_node(self, node, locals=None): 145 146 """ 147 Process a subprogram or module 'node', indicating any initial 'locals'. 148 Return an annotated subprogram or module. Note that this method may 149 mutate nodes in the original program. 150 """ 151 152 # Prevent infinite recursion. 153 154 if node in self.current_subprograms: 155 return node 156 157 # Determine the namespace. 158 159 if locals: 160 self.namespace = locals 161 else: 162 self.namespace = self.global_namespace 163 164 # Record the current subprogram and namespace. 165 166 self.current_subprograms.append(node) 167 self.current_namespaces.append(self.namespace) 168 169 # Add namespace details to any structure involved. 170 171 if getattr(node, "structure", None) is not None: 172 node.structure.namespace = Namespace() 173 174 # Initialise bases where appropriate. 175 176 if hasattr(node.structure, "bases"): 177 base_refs = [] 178 for base in node.structure.bases: 179 self.dispatch(base) 180 base_refs.append(self.namespace.types) 181 node.structure.base_refs = base_refs 182 183 # Dispatch to the code itself. 184 185 node.namespace = self.namespace 186 result = self.dispatch(node) 187 result.namespace = self.namespace 188 189 # Obtain the return values. 190 191 self.last_returns = self.namespace.returns 192 self.returned_locals = self.namespace.return_locals 193 194 # Restore the previous subprogram and namespace. 195 196 self.current_namespaces.pop() 197 if self.current_namespaces: 198 self.namespace = self.current_namespaces[-1] 199 200 self.current_subprograms.pop() 201 202 return result 203 204 def annotate(self, node): 205 206 "Annotate the given 'node' in the system." 207 208 self.system.annotate(node, self.namespace.types) 209 210 # Visitor methods. 211 212 def default(self, node): 213 214 """ 215 Process the given 'node', given that it does not have a specific 216 handler. 217 """ 218 219 for attr in ("expr", "lvalue", "test", "handler"): 220 value = getattr(node, attr, None) 221 if value is not None: 222 setattr(node, attr, self.dispatch(value)) 223 for attr in ("body", "else_", "finally_", "code"): 224 value = getattr(node, attr, None) 225 if value is not None: 226 setattr(node, attr, self.dispatches(value)) 227 return node 228 229 def dispatch(self, node, *args): 230 try: 231 return Visitor.dispatch(self, node, *args) 232 except AnnotationError, exc: 233 exc.add(node) 234 raise 235 except AnnotationMessage, exc: 236 raise AnnotationError(exc, node) 237 238 def visitLoadRef(self, loadref): 239 self.namespace.set_types([Attribute(None, loadref.ref)]) 240 self.annotate(loadref) 241 return loadref 242 243 def visitLoadName(self, loadname): 244 self.namespace.set_types(self.namespace.load(loadname.name)) 245 result = loadname 246 self.annotate(result) 247 return result 248 249 def visitStoreName(self, storename): 250 storename.expr = self.dispatch(storename.expr) 251 self.namespace.store(storename.name, self.namespace.types) 252 return storename 253 254 def visitLoadTemp(self, loadtemp): 255 index = getattr(loadtemp, "index", None) 256 self.namespace.set_types(self.namespace.temp[index][-1]) 257 self.annotate(loadtemp) 258 return loadtemp 259 260 def visitStoreTemp(self, storetemp): 261 storetemp.expr = self.dispatch(storetemp.expr) 262 index = getattr(storetemp, "index", None) 263 if not self.namespace.temp.has_key(index): 264 self.namespace.temp[index] = [] 265 self.namespace.temp[index].append(self.namespace.types) 266 return storetemp 267 268 def visitReleaseTemp(self, releasetemp): 269 index = getattr(releasetemp, "index", None) 270 self.namespace.temp[index].pop() 271 return releasetemp 272 273 def visitLoadAttr(self, loadattr): 274 loadattr.expr = self.dispatch(loadattr.expr) 275 types = [] 276 accesses = {} 277 for attr in self.namespace.types: 278 if not accesses.has_key(attr.type): 279 accesses[attr.type] = [] 280 for attribute, accessor in get_attributes(attr.type, loadattr.name): 281 if attribute is not None: 282 types.append(attribute) 283 else: 284 print "Empty attribute via accessor", accessor 285 accesses[attr.type].append((attribute, accessor)) 286 self.namespace.set_types(types) 287 loadattr.accesses = accesses 288 self.annotate(loadattr) 289 return loadattr 290 291 def visitStoreAttr(self, storeattr): 292 storeattr.expr = self.dispatch(storeattr.expr) 293 expr = self.namespace.types 294 storeattr.lvalue = self.dispatch(storeattr.lvalue) 295 writes = {} 296 for attr in self.namespace.types: 297 if attr is None: 298 print "Empty attribute storage attempt" 299 continue 300 attr.type.namespace.store(storeattr.name, expr) 301 writes[attr.type] = attr.type.namespace.load(storeattr.name) 302 storeattr.writes = writes 303 return storeattr 304 305 def visitConditional(self, conditional): 306 307 # Conditionals keep local namespace changes isolated. 308 # With Return nodes inside the body/else sections, the changes are 309 # communicated to the caller. 310 311 conditional.test = self.dispatch(conditional.test) 312 saved_namespace = self.namespace 313 314 self.namespace = Namespace() 315 self.namespace.merge_namespace(saved_namespace) 316 conditional.body = self.dispatches(conditional.body) 317 body_namespace = self.namespace 318 319 self.namespace = Namespace() 320 self.namespace.merge_namespace(saved_namespace) 321 conditional.else_ = self.dispatches(conditional.else_) 322 else_namespace = self.namespace 323 324 self.namespace = Namespace() 325 self.namespace.merge_namespace(body_namespace) 326 self.namespace.merge_namespace(else_namespace) 327 return conditional 328 329 def visitReturn(self, return_): 330 if hasattr(return_, "expr"): 331 return_.expr = self.dispatch(return_.expr) 332 self.namespace.returns += self.namespace.types 333 self.annotate(return_) 334 self.namespace.snapshot() 335 return return_ 336 337 def visitInvoke(self, invoke): 338 invoke.expr = self.dispatch(invoke.expr) 339 invocation_types = self.namespace.types 340 341 if isinstance(invoke, InvokeFunction): 342 self.process_args(invoke) 343 344 # Now locate and invoke the subprogram. This can be complicated because 345 # the target may be a class or object, and there may be many different 346 # related subprograms. 347 348 invocations = [] 349 350 # Visit each callable in turn, finding subprograms. 351 352 for attr in invocation_types: 353 354 # Deal with class invocations by providing instance objects. 355 # Here, each class is queried for the __init__ method, which may 356 # exist for some combinations of classes in a hierarchy but not for 357 # others. 358 359 if isinstance(attr.type, Class): 360 attributes = get_attributes(attr.type, "__init__") 361 362 # Deal with object invocations by using __call__ methods. 363 364 elif isinstance(attr.type, Instance): 365 attributes = get_attributes(attr.type, "__call__") 366 367 # Normal functions or methods are more straightforward. 368 # Here, we model them using an attribute with no context and with 369 # no associated accessor. 370 371 else: 372 attributes = [(attr, None)] 373 374 # Inspect each attribute and extract the subprogram. 375 376 for attribute, accessor in attributes: 377 378 # If a class is involved, presume that it must create a new 379 # object. 380 381 if isinstance(attr.type, Class): 382 383 # Instantiate the class. 384 # NOTE: Should probably only allocate a single instance. 385 386 instance = Instance() 387 instance.namespace = Namespace() 388 instance.namespace.store("__class__", [attr.type]) 389 390 # For instantiations, switch the context. 391 392 if attribute is not None: 393 attribute = Attribute(instance, attribute.type) 394 395 # Skip cases where no callable is found. 396 397 if attribute is not None: 398 399 # If a subprogram is defined, invoke it. 400 401 self.invoke_subprogram(invoke, attribute) 402 if attribute.type not in invocations: 403 invocations.append(attribute.type) 404 405 else: 406 print "Invocation type is None for", accessor 407 408 if isinstance(attr.type, Class): 409 410 # Associate the instance with the result of this invocation. 411 412 self.namespace.set_types([Attribute(None, instance)]) 413 self.annotate(invoke) 414 415 invoke.invocations = invocations 416 417 return invoke 418 419 visitInvokeFunction = visitInvoke 420 visitInvokeBlock = visitInvoke 421 422 # Utility methods. 423 424 def invoke_subprogram(self, invoke, subprogram): 425 426 """ 427 Invoke using the given 'invoke' node the given 'subprogram'. 428 """ 429 430 # Test to see if anything has changed. 431 432 if hasattr(invoke, "syscount") and invoke.syscount == self.system.count: 433 return 434 435 # Test for context information, making it into a real attribute. 436 437 if subprogram.context is not None: 438 context = Attribute(None, subprogram.context) 439 target = subprogram.type 440 else: 441 context = None 442 target = subprogram.type 443 444 # Provide the correct namespace for the invocation. 445 446 if isinstance(invoke, InvokeBlock): 447 namespace = Namespace() 448 namespace.merge_namespace(self.namespace) 449 else: 450 items = self.make_items(invoke, target, context) 451 namespace = self.make_namespace(items) 452 453 # Process the subprogram. 454 455 self.process_node(target, namespace) 456 457 # NOTE: Improve and verify this. 458 459 if getattr(target, "returns_value", 0): 460 self.namespace.set_types(self.last_returns) 461 self.annotate(invoke) 462 463 if isinstance(invoke, InvokeBlock): 464 for locals in self.returned_locals: 465 self.namespace.merge_namespace(locals) 466 467 # Remember the state of the system. 468 469 invoke.syscount = self.system.count 470 471 def process_args(self, invoke): 472 473 # NOTE: Consider initialiser invocation for classes. 474 475 types = [] 476 args = [] 477 478 # Get type information for regular arguments. 479 480 for arg in invoke.args: 481 args.append(self.dispatch(arg)) 482 types.append(self.namespace.types) 483 484 # Get type information for star and dstar arguments. 485 486 if invoke.star is not None: 487 param, default = invoke.star 488 default = self.dispatch(default) 489 invoke.star = param, default 490 types.append(default.types) 491 492 if invoke.dstar is not None: 493 param, default = invoke.dstar 494 default = self.dispatch(default) 495 invoke.dstar = param, default 496 types.append(default.types) 497 498 invoke.args = args 499 500 def make_items(self, invocation, subprogram, context): 501 502 """ 503 Make an items mapping for the 'invocation' of the 'subprogram' using the 504 given 'context' (which may be None). 505 """ 506 507 if context is not None: 508 args = [Self(context)] + invocation.args 509 else: 510 args = invocation.args 511 512 # Sort the arguments into positional and keyword arguments. 513 514 pos_args = [] 515 kw_args = [] 516 add_kw = 0 517 for arg in args: 518 if not add_kw: 519 if not isinstance(arg, Keyword): 520 pos_args.append(arg) 521 else: 522 add_kw = 1 523 if add_kw: 524 if isinstance(arg, Keyword): 525 kw_args.append(arg) 526 else: 527 raise AnnotationMessage, "Positional argument appears after keyword arguments in '%s'." % callfunc 528 529 params = subprogram.params 530 items = [] 531 star_args = [] 532 533 # Match each positional argument, taking excess arguments as star args. 534 535 for arg in pos_args: 536 if params: 537 param, default = params[0] 538 if arg is None: 539 arg = default 540 items.append((param, arg.types)) 541 params = params[1:] 542 else: 543 star_args.append(arg) 544 545 # Collect the remaining defaults. 546 547 while params: 548 param, default = params[0] 549 if kw_args.has_key(param): 550 arg = kw_args[param] 551 elif default is None: 552 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) 553 items.append((param, arg.types)) 554 params = params[1:] 555 556 # Add star and dstar. 557 558 if star_args or invocation.star is not None: 559 if subprogram.star is not None: 560 param, default = subprogram.star 561 items.append((param, invocation.star.types)) 562 else: 563 raise AnnotationMessage, "Invocation provides unwanted *args." 564 elif subprogram.star is not None: 565 param, default = subprogram.star 566 arg = self.dispatch(default) # NOTE: Review reprocessing. 567 items.append((param, arg.types)) 568 569 if kw_args or invocation.dstar is not None: 570 if subprogram.dstar is not None: 571 param, default = subprogram.dstar 572 items.append((param, invocation.dstar.types)) 573 else: 574 raise AnnotationMessage, "Invocation provides unwanted **args." 575 elif subprogram.dstar is not None: 576 param, default = subprogram.dstar 577 arg = self.dispatch(default) # NOTE: Review reprocessing. 578 items.append((param, arg.types)) 579 580 return items 581 582 def make_namespace(self, items): 583 namespace = Namespace() 584 namespace.merge_items(items) 585 return namespace 586 587 # Namespace-related abstractions. 588 589 class Namespace: 590 591 """ 592 A local namespace which may either relate to a genuine set of function 593 locals or the initialisation of a structure or module. 594 """ 595 596 def __init__(self): 597 598 """ 599 Initialise the namespace with a mapping of local names to possible 600 types, a list of return values and of possible returned local 601 namespaces. The namespace also tracks the "current" types and a mapping 602 of temporary value names to types. 603 """ 604 605 self.names = {} 606 self.returns = [] 607 self.return_locals = [] 608 self.temp = {} 609 self.types = [] 610 611 def set_types(self, types): 612 self.types = types 613 614 def store(self, name, types): 615 self.names[name] = types 616 617 def load(self, name): 618 return self.names[name] 619 620 def merge_namespace(self, namespace): 621 self.merge_items(namespace.names.items()) 622 self.returns += namespace.returns 623 624 def merge_items(self, items): 625 for name, types in items: 626 self.merge(name, types) 627 628 def merge(self, name, types): 629 if not self.names.has_key(name): 630 self.names[name] = types[:] 631 else: 632 existing = self.names[name] 633 for type in types: 634 if type not in existing: 635 existing.append(type) 636 637 def snapshot(self): 638 639 "Make a snapshot of the locals and remember them." 640 641 namespace = Namespace() 642 namespace.merge_namespace(self) 643 self.return_locals.append(namespace) 644 645 def __repr__(self): 646 return repr(self.names) 647 648 class Attribute: 649 650 """ 651 An attribute abstraction, indicating the type of the attribute along with 652 its context or origin. 653 """ 654 655 def __init__(self, context, type): 656 self.context = context 657 self.type = type 658 659 def __eq__(self, other): 660 return hasattr(other, "type") and other.type == self.type or other == self.type 661 662 def __repr__(self): 663 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 664 665 class Self: 666 def __init__(self, attribute): 667 self.types = [attribute] 668 669 def find_attributes(structure, name): 670 671 """ 672 Find for the given 'structure' all attributes for the given 'name', visiting 673 base classes where appropriate and returning the attributes in order of 674 descending precedence for all possible base classes. 675 676 The elements in the result list are 2-tuples which contain the attribute and 677 the structure involved in accessing the attribute. 678 """ 679 680 # First attempt to search the instance/class namespace. 681 682 try: 683 l = structure.namespace.load(name) 684 attributes = [] 685 for attribute in l: 686 attributes.append((attribute, structure)) 687 688 # If that does not work, attempt to investigate any class or base classes. 689 690 except KeyError: 691 attributes = [] 692 693 # Investigate any instance's implementing class. 694 695 if isinstance(structure, Instance): 696 for cls in structure.namespace.load("__class__"): 697 l = get_attributes(cls, name) 698 for attribute in l: 699 if attribute not in attributes: 700 attributes.append(attribute) 701 702 # Investigate any class's base classes. 703 704 elif isinstance(structure, Class): 705 706 # If no base classes exist, return an indicator that no attribute 707 # exists. 708 709 if not structure.base_refs: 710 return [(None, structure)] 711 712 # Otherwise, find all possible base classes. 713 714 for base_refs in structure.base_refs: 715 base_attributes = [] 716 717 # For each base class, find attributes either in the base 718 # class or its own base classes. 719 720 for base_ref in base_refs: 721 l = get_attributes(base_ref, name) 722 for attribute in l: 723 if attribute not in base_attributes: 724 base_attributes.append(attribute) 725 726 attributes += base_attributes 727 728 return attributes 729 730 def get_attributes(structure, name): 731 732 """ 733 Return all possible attributes for the given 'structure' having the given 734 'name', wrapping each attribute in an Attribute object which includes 735 context information for the attribute access. 736 737 The elements in the result list are 2-tuples which contain the attribute and 738 the structure involved in accessing the attribute. 739 """ 740 741 if isinstance(structure, Attribute): 742 structure = structure.type 743 results = [] 744 for attribute, accessor in find_attributes(structure, name): 745 if attribute is not None and isinstance(structure, Structure): 746 results.append((Attribute(structure, attribute.type), accessor)) 747 else: 748 results.append((attribute, accessor)) 749 return results 750 751 # Convenience functions. 752 753 def annotate(module, builtins=None): 754 755 """ 756 Annotate the given 'module', also employing the optional 'builtins' module, 757 if specified. 758 """ 759 760 annotator = Annotator() 761 if builtins is not None: 762 annotator.process(module, builtins) 763 else: 764 annotator.process(module) 765 766 def annotate_all(modules, builtins): 767 annotate(builtins) 768 for module in modules: 769 annotate(module, builtins) 770 771 # vim: tabstop=4 expandtab shiftwidth=4