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