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 if attribute is None: 373 print "Invocation type is None" 374 continue 375 376 subprogram = attribute.type 377 378 # If a subprogram is defined, invoke it. 379 380 self.invoke_subprogram(invoke, subprogram) 381 invocations[callable] = subprogram 382 383 # If a class is involved, presume that it must create a new 384 # object. 385 386 if isinstance(attr.type, Class): 387 self.namespace.set_types([Attribute(None, attribute.context)]) 388 self.annotate(invoke) 389 390 invoke.invocations = invocations 391 392 return invoke 393 394 # Utility methods. 395 396 def invoke_subprogram(self, invoke, subprogram): 397 398 """ 399 Invoke using the given 'invoke' node the given 'subprogram'. 400 """ 401 402 # Test to see if anything has changed. 403 404 if hasattr(invoke, "syscount") and invoke.syscount == self.system.count: 405 return 406 407 # Test for context information. 408 409 if hasattr(subprogram, "context"): 410 context = subprogram.context 411 target = subprogram.type 412 else: 413 context = None 414 target = subprogram 415 416 print target 417 418 # Provide the correct namespace for the invocation. 419 420 if getattr(invoke, "same_frame", 0): 421 namespace = Namespace() 422 namespace.merge_namespace(self.namespace) 423 else: 424 items = self.make_items(invoke, target, context) 425 namespace = self.make_namespace(items) 426 427 # Process the subprogram. 428 429 self.process_node(subprogram, namespace) 430 431 # NOTE: Improve and verify this. 432 433 if getattr(subprogram, "returns_value", 0): 434 self.namespace.set_types(self.last_returns) 435 self.annotate(invoke) 436 437 if getattr(invoke, "same_frame", 0): 438 for locals in self.returned_locals: 439 self.namespace.merge_namespace(locals) 440 441 # Remember the state of the system. 442 443 invoke.syscount = self.system.count 444 445 def make_items(self, invocation, subprogram, context): 446 447 """ 448 Make an items mapping for the 'invocation' of the 'subprogram' using the 449 given 'context' (which may be None). 450 """ 451 452 if context is not None: 453 args = [context] + invocation.args 454 else: 455 args = invocation.args 456 457 params = subprogram.params 458 items = [] 459 keywords = {} 460 461 # Process the specified arguments. 462 463 for arg in args: 464 if isinstance(arg, Keyword): 465 keywords[arg.name] = arg.expr 466 continue 467 elif params: 468 param, default = params[0] 469 if arg is None: 470 arg = self.dispatch(default) 471 else: 472 raise TypeError, "Invocation has too many arguments." 473 items.append((param, arg.types)) 474 params = params[1:] 475 476 # Collect the remaining defaults. 477 478 while params: 479 param, default = params[0] 480 if keywords.has_key(param): 481 arg = keywords[param] 482 else: 483 arg = self.dispatch(default) 484 items.append((param, arg.types)) 485 params = params[1:] 486 487 # Add star and dstar. 488 489 if invocation.star is not None: 490 if subprogram.star is not None: 491 param, default = subprogram.star 492 items.append((param, invocation.star.types)) 493 else: 494 raise TypeError, "Invocation provides unwanted *args." 495 elif subprogram.star is not None: 496 param, default = subprogram.star 497 items.append((param, self.dispatch(default))) 498 499 if invocation.dstar is not None: 500 if subprogram.dstar is not None: 501 param, default = subprogram.dstar 502 items.append((param, invocation.dstar.types)) 503 else: 504 raise TypeError, "Invocation provides unwanted **args." 505 elif subprogram.dstar is not None: 506 param, default = subprogram.dstar 507 items.append((param, self.dispatch(default))) 508 509 return items 510 511 def make_namespace(self, items): 512 namespace = Namespace() 513 namespace.merge_items(items) 514 return namespace 515 516 # Namespace-related abstractions. 517 518 class Namespace: 519 520 """ 521 A local namespace which may either relate to a genuine set of function 522 locals or the initialisation of a structure or module. 523 """ 524 525 def __init__(self): 526 527 """ 528 Initialise the namespace with a mapping of local names to possible 529 types, a list of return values and of possible returned local 530 namespaces. The namespace also tracks the "current" types and a mapping 531 of temporary value names to types. 532 """ 533 534 self.names = {} 535 self.returns = [] 536 self.return_locals = [] 537 self.temp = {} 538 self.types = [] 539 540 def set_types(self, types): 541 self.types = types 542 543 def store(self, name, types): 544 self.names[name] = types 545 546 def load(self, name): 547 return self.names[name] 548 549 def merge(self, name, types): 550 if not self.names.has_key(name): 551 self.names[name] = types[:] 552 else: 553 existing = self.names[name] 554 for type in types: 555 if type not in existing: 556 existing.append(type) 557 558 def merge_namespace(self, namespace): 559 self.merge_items(namespace.names.items()) 560 561 def merge_items(self, items): 562 for name, types in items: 563 self.merge(name, types) 564 565 def snapshot(self): 566 567 "Make a snapshot of the locals and remember them." 568 569 namespace = Namespace() 570 namespace.merge_namespace(self) 571 self.return_locals.append(namespace) 572 573 def __repr__(self): 574 return repr(self.names) 575 576 class Attribute: 577 578 """ 579 An attribute abstraction, indicating the type of the attribute along with 580 its context or origin. 581 """ 582 583 def __init__(self, context, type): 584 self.context = context 585 self.type = type 586 587 def __eq__(self, other): 588 return hasattr(other, "type") and other.type == self.type or other == self.type 589 590 def __repr__(self): 591 return "Attribute of type %s (context %s)" % (self.type, self.context) 592 593 def find_attributes(structure, name): 594 595 """ 596 Find for the given 'structure' all attributes for the given 'name', visiting 597 base classes where appropriate and returning the attributes in order of 598 descending precedence for all possible base classes. 599 600 The elements in the result list are 2-tuples which contain the attribute and 601 the structure involved in accessing the attribute. 602 """ 603 604 # First attempt to search the instance/class namespace. 605 606 try: 607 l = structure.namespace.load(name) 608 attributes = [] 609 for attribute in l: 610 attributes.append((attribute, structure)) 611 612 # If that does not work, attempt to investigate any class or base classes. 613 614 except KeyError: 615 attributes = [] 616 617 # Investigate any instance's implementing class. 618 619 if isinstance(structure, Instance): 620 for cls in structure.namespace.load("__class__"): 621 l = get_attributes(cls, name) 622 for attribute in l: 623 if attribute not in attributes: 624 attributes.append(attribute) 625 626 # Investigate any class's base classes. 627 628 elif isinstance(structure, Class): 629 630 # If no base classes exist, return an indicator that no attribute 631 # exists. 632 633 if not structure.base_refs: 634 return [(None, structure)] 635 636 # Otherwise, find all possible base classes. 637 638 for base_refs in structure.base_refs: 639 base_attributes = [] 640 641 # For each base class, find attributes either in the base 642 # class or its own base classes. 643 644 for base_ref in base_refs: 645 l = get_attributes(base_ref, name) 646 for attribute in l: 647 if attribute not in base_attributes: 648 base_attributes.append(attribute) 649 650 attributes += base_attributes 651 652 return attributes 653 654 def get_attributes(structure, name): 655 656 """ 657 Return all possible attributes for the given 'structure' having the given 658 'name', wrapping each attribute in an Attribute object which includes 659 context information for the attribute access. 660 661 The elements in the result list are 2-tuples which contain the attribute and 662 the structure involved in accessing the attribute. 663 """ 664 665 if isinstance(structure, Attribute): 666 structure = structure.type 667 return find_attributes(structure, name) 668 669 # vim: tabstop=4 expandtab shiftwidth=4