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 self.types = None 166 self.temp = {} 167 168 # Satisfy visitor issues. 169 170 self.visitor = self 171 172 def process_all(self, visitor, builtins_visitor=None): 173 174 # Give constants their own namespace. 175 176 for value, constant in visitor.constants.items(): 177 constant.namespace = Namespace() 178 179 # Process the module, supplying builtins if possible. 180 181 if builtins_visitor is not None: 182 return self.process(visitor.result, builtins=builtins_visitor.result.namespace) 183 else: 184 return self.process(visitor.result) 185 186 def process(self, node, locals=None, globals=None, builtins=None): 187 188 """ 189 Process a subprogram or module 'node', indicating any initial 'locals'. 190 Return an annotated subprogram or module. Note that this method may 191 mutate nodes in the original program. 192 """ 193 194 # Determine the global namespace. 195 # NOTE: Improve this. 196 197 self.global_namespace = globals or Namespace() 198 self.builtins_namespace = builtins or self.global_namespace 199 self.namespace = locals or self.global_namespace 200 201 # Record the namespace on the node. 202 # NOTE: This may eventually be a specialisation node. 203 204 node.namespace = self.namespace 205 206 # Remember return values and locals snapshots. 207 208 self.returns = [] 209 self.return_locals = [] 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] 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 self.temp[index] = self.types 309 return storetemp 310 311 def visitReleaseTemp(self, releasetemp): 312 index = getattr(releasetemp, "index", None) 313 del self.temp[index] 314 return releasetemp 315 316 def visitLoadAttr(self, loadattr): 317 loadattr.expr = self.dispatch(loadattr.expr) 318 types = [] 319 for ref in self.types: 320 for type in get_attributes(ref, loadattr.name): 321 types.append(type) 322 self.types = types 323 self.annotate(loadattr) 324 return loadattr 325 326 def visitStoreAttr(self, storeattr): 327 storeattr.expr = self.dispatch(storeattr.expr) 328 expr = self.types 329 storeattr.lvalue = self.dispatch(storeattr.lvalue) 330 for ref in self.types: 331 ref.namespace.store(storeattr.name, expr) 332 return storeattr 333 334 def visitConditional(self, conditional): 335 336 # Conditionals keep local namespace changes isolated. 337 # With Return nodes inside the body/else sections, the changes are 338 # communicated to the caller. 339 340 conditional.test = self.dispatch(conditional.test) 341 saved_namespace = self.namespace 342 343 self.namespace = Namespace() 344 self.namespace.merge_namespace(saved_namespace) 345 conditional.body = self.dispatches(conditional.body) 346 347 self.namespace = Namespace() 348 self.namespace.merge_namespace(saved_namespace) 349 conditional.else_ = self.dispatches(conditional.else_) 350 351 self.namespace = saved_namespace 352 return conditional 353 354 def visitReturn(self, return_): 355 if hasattr(return_, "expr"): 356 return_.expr = self.dispatch(return_.expr) 357 self.returns += self.types 358 self.add_locals_snapshot() 359 return return_ 360 361 def visitInvoke(self, invoke): 362 invoke.expr = self.dispatch(invoke.expr) 363 expr = self.types 364 365 # NOTE: Consider initialiser invocation for classes. 366 367 types = [] 368 args = [] 369 370 # Get type information for regular arguments. 371 372 for arg in invoke.args: 373 args.append(self.dispatch(arg)) 374 types.append(self.types) 375 376 # Get type information for star and dstar arguments. 377 378 if invoke.star is not None: 379 param, default = invoke.star 380 default = self.dispatch(default) 381 invoke.star = param, default 382 types.append(default.types) 383 384 if invoke.dstar is not None: 385 param, default = invoke.dstar 386 default = self.dispatch(default) 387 invoke.dstar = param, default 388 types.append(default.types) 389 390 invoke.args = args 391 invoke.types = expr 392 393 # Now locate and invoke the subprogram. This can be complicated because 394 # the target may be a class or object, and there may be many different 395 # related subprograms. 396 397 invocations = [] 398 399 # Visit each callable in turn 400 401 for callable in expr: 402 403 # Deal with class invocations by providing instance objects. 404 # Here, each class is queried for the __init__ method, which may 405 # exist for some combinations of classes in a hierarchy but not for 406 # others. 407 408 if isinstance(callable, Class): 409 subprograms = get_attributes(callable, "__init__") 410 411 # Deal with object invocations by using __call__ methods. 412 413 elif isinstance(callable, Instance): 414 subprograms = get_attributes(callable, "__call__") 415 416 # Normal functions or methods are more straightforward. 417 418 else: 419 subprograms = [callable] 420 421 for subprogram in subprograms: 422 if subprogram is not None: 423 invocations.append(self.invoke_subprogram(invoke, subprogram)) 424 425 return invoke 426 427 # Utility methods. 428 429 def invoke_subprogram(self, invoke, subprogram): 430 431 """ 432 Invoke using the given 'invoke' node the given 'subprogram'. 433 """ 434 435 # Test for context information. 436 437 if hasattr(subprogram, "context"): 438 context = subprogram.context 439 target = subprogram.type 440 else: 441 context = None 442 target = subprogram 443 444 # Provide the correct namespace for the invocation. 445 446 if getattr(invoke, "same_frame", 0): 447 namespace = Namespace() 448 namespace.merge_namespace(self.namespace) 449 else: 450 items = self.make_items(invoke, target, context) 451 namespace = self.make_namespace(items) 452 453 # Process the subprogram. 454 455 annotator = Annotator() 456 annotator.process(subprogram, namespace, self.global_namespace, self.builtins_namespace) 457 458 # NOTE: Annotate the node with invocation details. 459 # NOTE: This should really be as part of a table of alternatives. 460 461 if getattr(subprogram, "returns_value", 0): 462 self.types = annotator.returns 463 self.annotate(invoke) 464 465 if getattr(invoke, "same_frame", 0): 466 for locals in annotator.return_locals: 467 self.namespace.merge_namespace(locals) 468 469 def make_items(self, invocation, subprogram, context): 470 471 """ 472 Make an items mapping for the 'invocation' of the 'subprogram' using the 473 given 'context' (which may be None). 474 """ 475 476 if context is not None: 477 args = [context] + invocation.args 478 else: 479 args = invocation.args 480 481 params = subprogram.params 482 items = [] 483 keywords = {} 484 485 # Process the specified arguments. 486 487 for arg in args: 488 if isinstance(arg, Keyword): 489 keywords[arg.name] = arg.expr 490 continue 491 elif params: 492 param, default = params[0] 493 if arg is None: 494 arg = self.dispatch(default) 495 else: 496 raise TypeError, "Invocation has too many arguments." 497 items.append((param, arg.types)) 498 params = params[1:] 499 500 # Collect the remaining defaults. 501 502 while params: 503 param, default = params[0] 504 if keywords.has_key(param): 505 arg = keywords[param] 506 else: 507 arg = self.dispatch(default) 508 items.append((param, arg.types)) 509 params = params[1:] 510 511 # Add star and dstar. 512 513 if invocation.star is not None: 514 if subprogram.star is not None: 515 param, default = subprogram.star 516 items.append((param, invocation.star.types)) 517 else: 518 raise TypeError, "Invocation provides unwanted *args." 519 elif subprogram.star is not None: 520 param, default = subprogram.star 521 items.append((param, self.dispatch(default))) 522 523 if invocation.dstar is not None: 524 if subprogram.dstar is not None: 525 param, default = subprogram.dstar 526 items.append((param, invocation.dstar.types)) 527 else: 528 raise TypeError, "Invocation provides unwanted **args." 529 elif subprogram.dstar is not None: 530 param, default = subprogram.dstar 531 items.append((param, self.dispatch(default))) 532 533 return items 534 535 def make_namespace(self, items): 536 namespace = Namespace() 537 namespace.merge_items(items) 538 return namespace 539 540 # vim: tabstop=4 expandtab shiftwidth=4