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