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