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