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_all(self, visitor, builtins_visitor=None): 202 203 # Give constants their own namespace. 204 205 for value, constant in visitor.constants.items(): 206 constant.namespace = Namespace() 207 208 # Process the module, supplying builtins if possible. 209 210 if builtins_visitor is not None: 211 return self.process(visitor.result, builtins=builtins_visitor.result.namespace) 212 else: 213 return self.process(visitor.result) 214 215 def process(self, node, locals=None, globals=None, builtins=None): 216 217 """ 218 Process a subprogram or module 'node', indicating any initial 'locals'. 219 Return an annotated subprogram or module. Note that this method may 220 mutate nodes in the original program. 221 """ 222 223 # Determine the global namespace. 224 # NOTE: Improve this. 225 226 self.global_namespace = globals or Namespace() 227 self.builtins_namespace = builtins or self.global_namespace 228 self.namespace = locals or self.global_namespace 229 230 # Record the namespace on the node. 231 # NOTE: This may eventually be a specialisation node. 232 233 node.namespace = self.namespace 234 235 # Remember return values and locals snapshots. 236 237 self.returns = [] 238 self.return_locals = [] 239 self.types = None 240 self.temp = {} 241 242 # Add namespace details to any structure involved. 243 244 if getattr(node, "structure", None) is not None: 245 node.structure.namespace = Namespace() 246 247 # Initialise bases where appropriate. 248 249 if hasattr(node.structure, "bases"): 250 base_refs = [] 251 for base in node.structure.bases: 252 self.dispatch(base) 253 base_refs.append(self.types) 254 node.structure.base_refs = base_refs 255 256 # Dispatch to the code itself. 257 258 result = self.dispatch(node) 259 return result 260 261 def annotate(self, node): 262 263 "Annotate the given 'node' in the system." 264 265 self.system.annotate(node, self.types) 266 267 def add_locals_snapshot(self): 268 269 "Make a snapshot of the locals and remember them." 270 271 namespace = Namespace() 272 namespace.merge_namespace(self.namespace) 273 self.return_locals.append(namespace) 274 275 # Visitor methods. 276 277 def default(self, node): 278 279 """ 280 Process the given 'node', given that it does not have a specific 281 handler. 282 """ 283 284 for attr in ("expr", "lvalue", "test", "handler"): 285 value = getattr(node, attr, None) 286 if value is not None: 287 setattr(node, attr, self.dispatch(value)) 288 for attr in ("body", "else_", "finally_", "code"): 289 value = getattr(node, attr, None) 290 if value is not None: 291 setattr(node, attr, self.dispatches(value)) 292 return node 293 294 def dispatch(self, node, *args): 295 try: 296 return Visitor.dispatch(self, node, *args) 297 except: 298 print "Failed using node", node 299 raise 300 301 def visitLoadRef(self, loadref): 302 self.types = [loadref.ref] 303 self.annotate(loadref) 304 return loadref 305 306 def visitLoadName(self, loadname): 307 self.types = self.namespace.load(loadname.name) 308 result = loadname 309 self.annotate(result) 310 return result 311 312 def visitStoreName(self, storename): 313 storename.expr = self.dispatch(storename.expr) 314 self.namespace.store(storename.name, self.types) 315 return storename 316 317 def visitLoadGlobal(self, loadglobal): 318 try: 319 self.types = self.global_namespace.load(loadglobal.name) 320 except KeyError: 321 self.types = self.builtins_namespace.load(loadglobal.name) 322 self.annotate(loadglobal) 323 return loadglobal 324 325 def visitStoreGlobal(self, storeglobal): 326 storeglobal.expr = self.dispatch(storeglobal.expr) 327 self.global_namespace.merge(storeglobal.name, self.types) 328 return storeglobal 329 330 def visitLoadTemp(self, loadtemp): 331 index = getattr(loadtemp, "index", None) 332 self.types = self.temp[index][-1] 333 self.annotate(loadtemp) 334 return loadtemp 335 336 def visitStoreTemp(self, storetemp): 337 storetemp.expr = self.dispatch(storetemp.expr) 338 index = getattr(storetemp, "index", None) 339 if not self.temp.has_key(index): 340 self.temp[index] = [] 341 self.temp[index].append(self.types) 342 return storetemp 343 344 def visitReleaseTemp(self, releasetemp): 345 index = getattr(releasetemp, "index", None) 346 self.temp[index].pop() 347 return releasetemp 348 349 def visitLoadAttr(self, loadattr): 350 loadattr.expr = self.dispatch(loadattr.expr) 351 types = [] 352 accesses = {} 353 for ref in self.types: 354 if not accesses.has_key(ref): 355 accesses[ref] = [] 356 for attribute, accessor in get_attributes(ref, loadattr.name): 357 if attribute.type is not None: 358 types.append(type) 359 accesses[ref].append((attribute, accessor)) 360 self.types = types 361 loadattr.accesses = accesses 362 self.annotate(loadattr) 363 return loadattr 364 365 def visitStoreAttr(self, storeattr): 366 storeattr.expr = self.dispatch(storeattr.expr) 367 expr = self.types 368 storeattr.lvalue = self.dispatch(storeattr.lvalue) 369 accesses = {} 370 for ref in self.types: 371 ref.namespace.store(storeattr.name, expr) 372 accesses[ref] = ref.namespace.load(storeattr.name) 373 storeattr.accesses = accesses 374 return storeattr 375 376 def visitConditional(self, conditional): 377 378 # Conditionals keep local namespace changes isolated. 379 # With Return nodes inside the body/else sections, the changes are 380 # communicated to the caller. 381 382 conditional.test = self.dispatch(conditional.test) 383 saved_namespace = self.namespace 384 385 self.namespace = Namespace() 386 self.namespace.merge_namespace(saved_namespace) 387 conditional.body = self.dispatches(conditional.body) 388 body_namespace = self.namespace 389 390 self.namespace = Namespace() 391 self.namespace.merge_namespace(saved_namespace) 392 conditional.else_ = self.dispatches(conditional.else_) 393 else_namespace = self.namespace 394 395 self.namespace = Namespace() 396 self.namespace.merge_namespace(body_namespace) 397 self.namespace.merge_namespace(else_namespace) 398 return conditional 399 400 def visitReturn(self, return_): 401 if hasattr(return_, "expr"): 402 return_.expr = self.dispatch(return_.expr) 403 self.returns += self.types 404 self.add_locals_snapshot() 405 return return_ 406 407 def visitInvoke(self, invoke): 408 invoke.expr = self.dispatch(invoke.expr) 409 expr = self.types 410 411 # NOTE: Consider initialiser invocation for classes. 412 413 types = [] 414 args = [] 415 416 # Get type information for regular arguments. 417 418 for arg in invoke.args: 419 args.append(self.dispatch(arg)) 420 types.append(self.types) 421 422 # Get type information for star and dstar arguments. 423 424 if invoke.star is not None: 425 param, default = invoke.star 426 default = self.dispatch(default) 427 invoke.star = param, default 428 types.append(default.types) 429 430 if invoke.dstar is not None: 431 param, default = invoke.dstar 432 default = self.dispatch(default) 433 invoke.dstar = param, default 434 types.append(default.types) 435 436 invoke.args = args 437 438 # Now locate and invoke the subprogram. This can be complicated because 439 # the target may be a class or object, and there may be many different 440 # related subprograms. 441 442 invocations = {} 443 444 # Visit each callable in turn, finding subprograms. 445 446 for callable in expr: 447 448 # Deal with class invocations by providing instance objects. 449 # Here, each class is queried for the __init__ method, which may 450 # exist for some combinations of classes in a hierarchy but not for 451 # others. 452 453 if isinstance(callable, Class): 454 attributes = get_attributes(callable, "__init__") 455 456 # Deal with object invocations by using __call__ methods. 457 458 elif isinstance(callable, Instance): 459 attributes = get_attributes(callable, "__call__") 460 461 # Normal functions or methods are more straightforward. 462 # Here, we model them using an attribute with no context and with 463 # no associated accessor. 464 465 else: 466 attributes = [(Attribute(None, callable), None)] 467 468 # Inspect each attribute and extract the subprogram. 469 470 for attribute, accessor in attributes: 471 subprogram = attribute.type 472 473 # If a subprogram is defined, invoke it. 474 475 if subprogram is not None: 476 self.invoke_subprogram(invoke, subprogram) 477 invocations[callable] = subprogram 478 479 # If a class is involved, presume that it must create a new 480 # object. 481 482 if isinstance(callable, Class): 483 self.types = [attribute.context] 484 self.annotate(invoke) 485 486 invoke.invocations = invocations 487 488 return invoke 489 490 # Utility methods. 491 492 def invoke_subprogram(self, invoke, subprogram): 493 494 """ 495 Invoke using the given 'invoke' node the given 'subprogram'. 496 """ 497 498 # Test to see if anything has changed. 499 500 if hasattr(invoke, "syscount") and invoke.syscount == self.system.count: 501 return 502 503 # Test for context information. 504 505 if hasattr(subprogram, "context"): 506 context = subprogram.context 507 target = subprogram.type 508 else: 509 context = None 510 target = subprogram 511 512 # Provide the correct namespace for the invocation. 513 514 if getattr(invoke, "same_frame", 0): 515 namespace = Namespace() 516 namespace.merge_namespace(self.namespace) 517 else: 518 items = self.make_items(invoke, target, context) 519 namespace = self.make_namespace(items) 520 521 # Process the subprogram. 522 523 annotator = Annotator() 524 annotator.process(subprogram, namespace, self.global_namespace, self.builtins_namespace) 525 526 # NOTE: Annotate the node with invocation details. 527 # NOTE: This should really be as part of a table of alternatives. 528 529 if getattr(subprogram, "returns_value", 0): 530 self.types = annotator.returns 531 self.annotate(invoke) 532 533 if getattr(invoke, "same_frame", 0): 534 for locals in annotator.return_locals: 535 self.namespace.merge_namespace(locals) 536 537 # Remember the state of the system. 538 539 invoke.syscount = self.system.count 540 541 def make_items(self, invocation, subprogram, context): 542 543 """ 544 Make an items mapping for the 'invocation' of the 'subprogram' using the 545 given 'context' (which may be None). 546 """ 547 548 if context is not None: 549 args = [context] + invocation.args 550 else: 551 args = invocation.args 552 553 params = subprogram.params 554 items = [] 555 keywords = {} 556 557 # Process the specified arguments. 558 559 for arg in args: 560 if isinstance(arg, Keyword): 561 keywords[arg.name] = arg.expr 562 continue 563 elif params: 564 param, default = params[0] 565 if arg is None: 566 arg = self.dispatch(default) 567 else: 568 raise TypeError, "Invocation has too many arguments." 569 items.append((param, arg.types)) 570 params = params[1:] 571 572 # Collect the remaining defaults. 573 574 while params: 575 param, default = params[0] 576 if keywords.has_key(param): 577 arg = keywords[param] 578 else: 579 arg = self.dispatch(default) 580 items.append((param, arg.types)) 581 params = params[1:] 582 583 # Add star and dstar. 584 585 if invocation.star is not None: 586 if subprogram.star is not None: 587 param, default = subprogram.star 588 items.append((param, invocation.star.types)) 589 else: 590 raise TypeError, "Invocation provides unwanted *args." 591 elif subprogram.star is not None: 592 param, default = subprogram.star 593 items.append((param, self.dispatch(default))) 594 595 if invocation.dstar is not None: 596 if subprogram.dstar is not None: 597 param, default = subprogram.dstar 598 items.append((param, invocation.dstar.types)) 599 else: 600 raise TypeError, "Invocation provides unwanted **args." 601 elif subprogram.dstar is not None: 602 param, default = subprogram.dstar 603 items.append((param, self.dispatch(default))) 604 605 return items 606 607 def make_namespace(self, items): 608 namespace = Namespace() 609 namespace.merge_items(items) 610 return namespace 611 612 # vim: tabstop=4 expandtab shiftwidth=4