1 #!/usr/bin/env python 2 3 """ 4 Annotate simplified AST 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 # Namespaces and 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, structure=None): 57 self.structure = structure 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 class Attribute: 83 84 """ 85 An attribute abstraction, indicating the type of the attribute along with 86 its context or origin. 87 """ 88 89 def __init__(self, context, type): 90 self.context = context 91 self.type = type 92 93 def __eq__(self, other): 94 return hasattr(other, "type") and other.type == self.type or other == self.type 95 96 def find_methods(structure, name): 97 98 """ 99 Find for the given 'structure' all methods for the given 'name', visiting 100 base classes where appropriate and returning the methods in order of 101 descending precedence for all possible base classes. 102 """ 103 104 try: 105 return structure.namespace.load(name) 106 except KeyError: 107 methods = [] 108 if hasattr(structure, "base_refs"): 109 for base_refs in structure.base_refs: 110 for base_ref in base_refs: 111 l = find_methods(base_ref, name) 112 if l: 113 for method in l: 114 if method not in methods: 115 methods.append(method) 116 return methods 117 118 # Annotation. 119 120 class Annotator(Visitor): 121 122 """ 123 The type annotator which traverses the program nodes, typically depth-first, 124 and maintains a record of the current set of types applying to the currently 125 considered operation. Such types are also recorded on the nodes, and a 126 special "system" record is maintained to monitor the level of annotation 127 activity with a view to recognising when no more annotations are possible. 128 """ 129 130 def __init__(self): 131 Visitor.__init__(self) 132 self.system = system 133 self.types = None 134 self.temp = {} 135 136 # Satisfy visitor issues. 137 138 self.visitor = self 139 140 def process(self, node, locals=None, globals=None, builtins=None): 141 142 """ 143 Process a subprogram or module 'node', indicating any initial 'locals', 144 'globals' and 'builtins' if any are defined. Return an annotated 145 subprogram or module. Note that this method may mutate nodes in the 146 original program. 147 """ 148 149 # Obtain a namespace either based on locals or on a structure. 150 151 self.namespace = Namespace(structure=getattr(node, "structure", None)) 152 if locals is not None: 153 self.namespace.merge_namespace(locals) 154 155 # Determine the global namespace. 156 157 self.global_namespace = globals or self.namespace # NOTE: Improve this. 158 self.builtins_namespace = builtins or self.namespace # NOTE: Improve this. 159 node.namespace = self.namespace 160 161 # Remember return values. 162 163 self.returns = [] 164 165 # Add namespace details to any structure involved. 166 167 if hasattr(node, "structure") and node.structure is not None: 168 node.structure.namespace = self.namespace 169 170 # Initialise bases where appropriate. 171 172 if hasattr(node.structure, "bases"): 173 base_refs = [] 174 for base in node.structure.bases: 175 self.dispatch(base) 176 base_refs.append(self.types) 177 node.structure.base_refs = base_refs 178 179 # Dispatch to the code itself. 180 181 result = self.dispatch(node) 182 183 return result 184 185 def annotate(self, node): 186 187 "Annotate the given 'node' in the system." 188 189 self.system.annotate(node, self.types) 190 191 # Visitor methods. 192 193 def default(self, node): 194 195 """ 196 Process the given 'node', given that it does not have a specific 197 handler. 198 """ 199 200 for attr in ("expr", "lvalue", "test", "handler"): 201 value = getattr(node, attr, None) 202 if value is not None: 203 setattr(node, attr, self.dispatch(value)) 204 for attr in ("body", "else_", "finally_", "code"): 205 value = getattr(node, attr, None) 206 if value is not None: 207 setattr(node, attr, self.dispatches(value)) 208 return node 209 210 def dispatch(self, node, *args): 211 return Visitor.dispatch(self, node, *args) 212 213 def visitLoadRef(self, loadref): 214 self.types = [loadref.ref] 215 self.annotate(loadref) 216 return loadref 217 218 def visitLoadName(self, loadname): 219 self.types = self.namespace.load(loadname.name) 220 result = loadname 221 self.annotate(result) 222 return result 223 224 def visitStoreName(self, storename): 225 storename.expr = self.dispatch(storename.expr) 226 self.namespace.store(storename.name, self.types) 227 return storename 228 229 def visitLoadGlobal(self, loadglobal): 230 try: 231 self.types = self.global_namespace.load(loadglobal.name) 232 except KeyError: 233 self.types = self.builtins_namespace.load(loadglobal.name) 234 self.annotate(loadglobal) 235 return loadglobal 236 237 def visitStoreGlobal(self, storeglobal): 238 storeglobal.expr = self.dispatch(storeglobal.expr) 239 self.global_namespace.merge(storeglobal.name, self.types) 240 return storeglobal 241 242 def visitLoadTemp(self, loadtemp): 243 index = getattr(loadtemp, "index", None) 244 self.types = self.temp[index] 245 self.annotate(loadtemp) 246 return loadtemp 247 248 def visitStoreTemp(self, storetemp): 249 storetemp.expr = self.dispatch(storetemp.expr) 250 index = getattr(storetemp, "index", None) 251 self.temp[index] = self.types 252 return storetemp 253 254 def visitReleaseTemp(self, releasetemp): 255 index = getattr(releasetemp, "index", None) 256 del self.temp[index] 257 return releasetemp 258 259 def visitLoadAttr(self, loadattr): 260 loadattr.expr = self.dispatch(loadattr.expr) 261 types = [] 262 for ref in self.types: 263 for type in ref.namespace.load(loadattr.name): 264 types.append(Attribute(ref, type)) 265 self.types = types 266 self.annotate(loadattr) 267 return loadattr 268 269 def visitStoreAttr(self, storeattr): 270 storeattr.expr = self.dispatch(storeattr.expr) 271 expr = self.types 272 storeattr.lvalue = self.dispatch(storeattr.lvalue) 273 for ref in self.types: 274 ref.namespace.store(storeattr.name, expr) 275 return storeattr 276 277 def visitReturn(self, return_): 278 if hasattr(return_, "expr"): 279 return_.expr = self.dispatch(return_.expr) 280 self.returns += self.types 281 return return_ 282 283 def visitInvoke(self, invoke): 284 invoke.expr = self.dispatch(invoke.expr) 285 expr = self.types 286 287 # NOTE: Consider initialiser invocation for classes. 288 289 types = [] 290 args = [] 291 292 # Get type information for regular arguments. 293 294 for arg in invoke.args: 295 args.append(self.dispatch(arg)) 296 types.append(self.types) 297 298 # Get type information for star and dstar arguments. 299 300 if invoke.star is not None: 301 param, default = invoke.star 302 default = self.dispatch(default) 303 invoke.star = param, default 304 types.append(default.types) 305 306 if invoke.dstar is not None: 307 param, default = invoke.dstar 308 default = self.dispatch(default) 309 invoke.dstar = param, default 310 types.append(default.types) 311 312 invoke.args = args 313 invoke.types = expr 314 315 # NOTE: Now locate and invoke the subprogram. 316 317 for subprogram in expr: 318 319 # NOTE: Deal with class invocations by providing instance objects, 320 # NOTE: and with object invocations by using __call__ methods. 321 322 if hasattr(invoke, "same_frame") and invoke.same_frame: 323 namespace = self.namespace 324 else: 325 items = self.make_items(invoke, subprogram) 326 namespace = self.make_namespace(items) 327 328 annotator = Annotator() 329 annotator.process(subprogram, namespace, self.global_namespace) 330 331 # NOTE: Annotate the node with invocation details. 332 # NOTE: This should really be as part of a table of alternatives. 333 334 if hasattr(subprogram, "returns_value") and subprogram.returns_value: 335 self.types = annotator.returns 336 self.annotate(invoke) 337 338 return invoke 339 340 # Utility methods. 341 342 def make_items(self, invocation, subprogram): 343 # NOTE: Support star and dstar. 344 args = invocation.args 345 params = subprogram.params 346 items = [] 347 keywords = {} 348 349 # Process the specified arguments. 350 351 for arg in args: 352 if isinstance(arg, Keyword): 353 keywords[arg.name] = arg.expr 354 continue 355 elif params: 356 param, default = params[0] 357 if arg is None: 358 arg = self.dispatch(default) 359 else: 360 raise TypeError, "Invocation has too many arguments." 361 items.append((param, arg.types)) 362 params = params[1:] 363 364 # Collect the remaining defaults. 365 366 while params: 367 param, default = params[0] 368 if keywords.has_key(param): 369 arg = keywords[param] 370 else: 371 arg = self.dispatch(default) 372 items.append((param, arg.types)) 373 params = params[1:] 374 375 # Add star and dstar. 376 377 if invocation.star is not None: 378 if subprogram.star is not None: 379 param, default = subprogram.star 380 items.append((param, invocation.star.types)) 381 else: 382 raise TypeError, "Invocation provides unwanted *args." 383 elif subprogram.star is not None: 384 param, default = subprogram.star 385 items.append((param, self.dispatch(default))) 386 387 if invocation.dstar is not None: 388 if subprogram.dstar is not None: 389 param, default = subprogram.dstar 390 items.append((param, invocation.dstar.types)) 391 else: 392 raise TypeError, "Invocation provides unwanted **args." 393 elif subprogram.dstar is not None: 394 param, default = subprogram.dstar 395 items.append((param, self.dispatch(default))) 396 397 return items 398 399 def make_namespace(self, items): 400 namespace = Namespace() 401 namespace.merge_items(items) 402 return namespace 403 404 # vim: tabstop=4 expandtab shiftwidth=4