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 if structure is not None: 59 self.local = "structure" 60 else: 61 self.local = "local" 62 self.names = {} 63 self.not_local = [] 64 65 def make_global(self, name): 66 if name not in self.not_local: 67 self.not_local.append(name) 68 69 def find_for_store(self, name): 70 if name not in self.not_local: 71 return self.local 72 else: 73 return "global" 74 75 def find_for_load(self, name): 76 if name not in self.not_local and self.names.has_key(name): 77 return self.local 78 else: 79 return "global" 80 81 def store(self, name, types): 82 if name not in self.not_local: 83 self.names[name] = types 84 else: 85 raise KeyError, name 86 87 def load(self, name): 88 if name in self.not_local or not self.names.has_key(name): 89 raise KeyError, name 90 else: 91 return self.names[name] 92 93 def merge(self, namespace): 94 self.merge_items(namespace.names.items()) 95 96 def merge_items(self, items): 97 for name, types in items: 98 if not self.names.has_key(name): 99 self.names[name] = types 100 else: 101 existing = self.names[name] 102 for type in types: 103 if type not in existing: 104 existing.append(type) 105 106 class Attribute: 107 108 """ 109 An attribute abstraction, indicating the type of the attribute along with 110 its context or origin. 111 """ 112 113 def __init__(self, context, type): 114 self.context = context 115 self.type = type 116 117 def __eq__(self, other): 118 return hasattr(other, "type") and other.type == self.type or other == self.type 119 120 # Annotation. 121 122 class Annotator(Visitor): 123 124 """ 125 The type annotator which traverses the program nodes, typically depth-first, 126 and maintains a record of the current set of types applying to the currently 127 considered operation. Such types are also recorded on the nodes, and a 128 special "system" record is maintained to monitor the level of annotation 129 activity with a view to recognising when no more annotations are possible. 130 """ 131 132 def __init__(self): 133 Visitor.__init__(self) 134 self.system = system 135 self.types = None 136 self.temp = {} 137 138 # Satisfy visitor issues. 139 140 self.visitor = self 141 142 def process(self, node, locals=None, globals=None): 143 144 """ 145 Process a subprogram or module 'node', indicating any initial 'locals' 146 and 'globals' if either are defined. Return an annotated subprogram or 147 module. Note that this method may mutate nodes in the original program. 148 """ 149 150 # Obtain a namespace either based on locals or on a structure. 151 152 self.namespace = Namespace(structure=getattr(node, "structure", None)) 153 if locals is not None: 154 self.namespace.merge(locals) 155 156 # Determine the global namespace. 157 158 self.global_namespace = globals 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 visitGlobal(self, global_): 214 for name in global_.names: 215 self.namespace.make_global(name) 216 return global_ 217 218 def visitLoadRef(self, loadref): 219 self.types = [loadref.ref] 220 self.annotate(loadref) 221 return loadref 222 223 def visitLoadName(self, loadname): 224 scope = self.namespace.find_for_load(loadname.name) 225 if scope == "structure": 226 result = self.dispatch(LoadAttr(expr=LoadRef(ref=self.namespace.structure), name=loadname.name)) 227 elif scope == "global": 228 result = self.dispatch(LoadGlobal(name=loadname.name)) 229 else: 230 self.types = self.namespace.load(loadname.name) 231 result = loadname 232 self.annotate(result) 233 return result 234 235 def visitStoreName(self, storename): 236 scope = self.namespace.find_for_store(storename.name) 237 if scope == "structure": 238 return self.dispatch(StoreAttr(lvalue=LoadRef(ref=self.namespace.structure), name=storename.name, expr=storename.expr)) 239 elif scope == "global": 240 return self.dispatch(StoreGlobal(name=storename.name, expr=storename.expr)) 241 else: 242 storename.expr = self.dispatch(storename.expr) 243 self.namespace.store(storename.name, self.types) 244 return storename 245 246 def visitLoadGlobal(self, loadglobal): 247 self.types = self.global_namespace.load(loadglobal.name) 248 self.annotate(loadglobal) 249 return loadglobal 250 251 def visitStoreGlobal(self, storeglobal): 252 storeglobal.expr = self.dispatch(storeglobal.expr) 253 254 # NOTE: This may always be a merge operation. 255 256 self.global_namespace.store(storeglobal.name, self.types) 257 return storeglobal 258 259 def visitLoadTemp(self, loadtemp): 260 index = getattr(loadtemp, "index", None) 261 self.types = self.temp[index] 262 self.annotate(loadtemp) 263 return loadtemp 264 265 def visitStoreTemp(self, storetemp): 266 storetemp.expr = self.dispatch(storetemp.expr) 267 index = getattr(storetemp, "index", None) 268 self.temp[index] = self.types 269 return storetemp 270 271 def visitReleaseTemp(self, releasetemp): 272 index = getattr(releasetemp, "index", None) 273 del self.temp[index] 274 return releasetemp 275 276 def visitLoadAttr(self, loadattr): 277 loadattr.expr = self.dispatch(loadattr.expr) 278 types = [] 279 for ref in self.types: 280 for type in ref.namespace.load(loadattr.name): 281 types.append(Attribute(ref, type)) 282 self.types = types 283 self.annotate(loadattr) 284 return loadattr 285 286 def visitStoreAttr(self, storeattr): 287 storeattr.expr = self.dispatch(storeattr.expr) 288 expr = self.types 289 storeattr.lvalue = self.dispatch(storeattr.lvalue) 290 for ref in self.types: 291 ref.namespace.store(storeattr.name, expr) 292 return storeattr 293 294 def visitReturn(self, return_): 295 if hasattr(return_, "expr"): 296 return_.expr = self.dispatch(return_.expr) 297 self.returns += self.types 298 return return_ 299 300 def visitInvoke(self, invoke): 301 invoke.expr = self.dispatch(invoke.expr) 302 expr = self.types 303 304 # NOTE: Consider initialiser invocation for classes. 305 306 types = [] 307 args = [] 308 309 # Get type information for regular arguments. 310 311 for arg in invoke.args: 312 args.append(self.dispatch(arg)) 313 types.append(self.types) 314 315 # Get type information for star and dstar arguments. 316 317 if invoke.star is not None: 318 param, default = invoke.star 319 default = self.dispatch(default) 320 invoke.star = param, default 321 types.append(default.types) 322 323 if invoke.dstar is not None: 324 param, default = invoke.dstar 325 default = self.dispatch(default) 326 invoke.dstar = param, default 327 types.append(default.types) 328 329 invoke.args = args 330 invoke.types = expr 331 332 # NOTE: Now locate and invoke the subprogram. 333 334 for subprogram in expr: 335 336 # NOTE: Deal with class invocations by providing instance objects, 337 # NOTE: and with object invocations by using __call__ methods. 338 339 if hasattr(invoke, "same_frame") and invoke.same_frame: 340 namespace = self.namespace 341 else: 342 items = self.make_items(invoke, subprogram) 343 namespace = self.make_namespace(items) 344 345 annotator = Annotator() 346 annotator.process(subprogram, namespace, self.global_namespace) 347 348 # NOTE: Annotate the node with invocation details. 349 # NOTE: This should really be as part of a table of alternatives. 350 351 if hasattr(subprogram, "returns_value") and subprogram.returns_value: 352 self.types = annotator.returns 353 self.annotate(invoke) 354 355 return invoke 356 357 # Utility methods. 358 359 def make_items(self, invocation, subprogram): 360 # NOTE: Support star and dstar. 361 args = invocation.args 362 params = subprogram.params 363 items = [] 364 keywords = {} 365 366 # Process the specified arguments. 367 368 for arg in args: 369 if isinstance(arg, Keyword): 370 keywords[arg.name] = arg.expr 371 continue 372 elif params: 373 param, default = params[0] 374 if arg is None: 375 arg = self.dispatch(default) 376 else: 377 raise TypeError, "Invocation has too many arguments." 378 items.append((param, arg.types)) 379 params = params[1:] 380 381 # Collect the remaining defaults. 382 383 while params: 384 param, default = params[0] 385 if keywords.has_key(param): 386 arg = keywords[param] 387 else: 388 arg = self.dispatch(default) 389 items.append((param, arg.types)) 390 params = params[1:] 391 392 # Add star and dstar. 393 394 if invocation.star is not None: 395 if subprogram.star is not None: 396 param, default = subprogram.star 397 items.append((param, invocation.star.types)) 398 else: 399 raise TypeError, "Invocation provides unwanted *args." 400 elif subprogram.star is not None: 401 param, default = subprogram.star 402 items.append((param, self.dispatch(default))) 403 404 if invocation.dstar is not None: 405 if subprogram.dstar is not None: 406 param, default = subprogram.dstar 407 items.append((param, invocation.dstar.types)) 408 else: 409 raise TypeError, "Invocation provides unwanted **args." 410 elif subprogram.dstar is not None: 411 param, default = subprogram.dstar 412 items.append((param, self.dispatch(default))) 413 414 return items 415 416 def make_namespace(self, items): 417 namespace = Namespace() 418 namespace.merge_items(items) 419 return namespace 420 421 # vim: tabstop=4 expandtab shiftwidth=4