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