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