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