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 def process(self, node, locals=None, globals=None): 139 140 """ 141 Process a subprogram or module 'node', indicating any initial 'locals' 142 and 'globals' if either are defined. Return an annotated subprogram or 143 module. Note that this method may mutate nodes in the original program. 144 """ 145 146 # Obtain a namespace either based on locals or on a structure. 147 148 self.namespace = Namespace(structure=getattr(node, "structure", None)) 149 if locals is not None: 150 self.namespace.merge(locals) 151 152 # Determine the global namespace. 153 154 self.global_namespace = globals or self.namespace # NOTE: Improve this. 155 node.namespace = self.namespace 156 157 # Add namespace details to any structure involved. 158 159 if hasattr(node, "structure") and node.structure is not None: 160 node.structure.namespace = self.namespace 161 162 # Satisfy visitor issues and then dispatch. 163 164 self.visitor = self 165 result = self.dispatch(node) 166 167 return result 168 169 def annotate(self, node): 170 171 "Annotate the given 'node' in the system." 172 173 self.system.annotate(node, self.types) 174 175 # Visitor methods. 176 177 def default(self, node): 178 179 """ 180 Process the given 'node', given that it does not have a specific 181 handler. 182 """ 183 184 for attr in ("expr", "lvalue", "test", "handler"): 185 value = getattr(node, attr, None) 186 if value is not None: 187 setattr(node, attr, self.dispatch(value)) 188 for attr in ("body", "else_", "finally_", "code"): 189 value = getattr(node, attr, None) 190 if value is not None: 191 setattr(node, attr, self.dispatches(value)) 192 return node 193 194 def dispatch(self, node, *args): 195 return Visitor.dispatch(self, node, *args) 196 197 def visitGlobal(self, global_): 198 for name in global_.names: 199 self.namespace.make_global(name) 200 return global_ 201 202 def visitLoadRef(self, loadref): 203 self.types = [loadref.ref] 204 self.annotate(loadref) 205 return loadref 206 207 def visitLoadName(self, loadname): 208 scope = self.namespace.find_for_load(loadname.name) 209 if scope == "structure": 210 result = self.dispatch(LoadAttr(expr=LoadRef(ref=self.namespace.structure), name=loadname.name)) 211 elif scope == "global": 212 result = self.dispatch(LoadGlobal(name=loadname.name)) 213 else: 214 self.types = self.namespace.load(loadname.name) 215 result = loadname 216 self.annotate(result) 217 return result 218 219 def visitStoreName(self, storename): 220 scope = self.namespace.find_for_store(storename.name) 221 if scope == "structure": 222 return self.dispatch(StoreAttr(lvalue=LoadRef(ref=self.namespace.structure), name=storename.name, expr=storename.expr)) 223 elif scope == "global": 224 return self.dispatch(StoreGlobal(name=storename.name, expr=storename.expr)) 225 else: 226 storename.expr = self.dispatch(storename.expr) 227 self.namespace.store(storename.name, self.types) 228 return storename 229 230 def visitLoadGlobal(self, loadglobal): 231 self.types = self.global_namespace.load(loadglobal.name) 232 self.annotate(loadglobal) 233 return loadglobal 234 235 def visitStoreGlobal(self, storeglobal): 236 storeglobal.expr = self.dispatch(storeglobal.expr) 237 238 # NOTE: This may always be a merge operation. 239 240 self.global_namespace.store(storeglobal.name, self.types) 241 return storeglobal 242 243 def visitLoadTemp(self, loadtemp): 244 index = getattr(loadtemp, "index", None) 245 self.types = self.temp[index] 246 self.annotate(loadtemp) 247 return loadtemp 248 249 def visitStoreTemp(self, storetemp): 250 storetemp.expr = self.dispatch(storetemp.expr) 251 index = getattr(storetemp, "index", None) 252 self.temp[index] = self.types 253 return storetemp 254 255 def visitReleaseTemp(self, releasetemp): 256 index = getattr(releasetemp, "index", None) 257 del self.temp[index] 258 return releasetemp 259 260 def visitLoadAttr(self, loadattr): 261 loadattr.expr = self.dispatch(loadattr.expr) 262 types = [] 263 for ref in self.types: 264 for type in ref.namespace.load(loadattr.name): 265 types.append(Attribute(ref, type)) 266 self.types = types 267 self.annotate(loadattr) 268 return loadattr 269 270 def visitStoreAttr(self, storeattr): 271 storeattr.expr = self.dispatch(storeattr.expr) 272 expr = self.types 273 storeattr.lvalue = self.dispatch(storeattr.lvalue) 274 for ref in self.types: 275 ref.namespace.store(storeattr.name, expr) 276 return storeattr 277 278 def visitInvoke(self, invoke): 279 invoke.expr = self.dispatch(invoke.expr) 280 expr = self.types 281 282 # NOTE: Consider initialiser invocation for classes. 283 284 types = [] 285 args = [] 286 287 # Get type information for regular arguments. 288 289 for arg in invoke.args: 290 args.append(self.dispatch(arg)) 291 types.append(self.types) 292 293 # Get type information for star and dstar arguments. 294 295 if invoke.star is not None: 296 param, default = invoke.star 297 default = self.dispatch(default) 298 invoke.star = param, default 299 types.append(default.types) 300 301 if invoke.dstar is not None: 302 param, default = invoke.dstar 303 default = self.dispatch(default) 304 invoke.dstar = param, default 305 types.append(default.types) 306 307 invoke.args = args 308 invoke.types = expr 309 310 # NOTE: Now locate and invoke the subprogram. 311 312 for subprogram in expr: 313 if hasattr(invoke, "same_frame") and invoke.same_frame: 314 namespace = self.namespace 315 else: 316 items = self.make_items(invoke, subprogram) 317 namespace = self.make_namespace(items) 318 319 annotator = Annotator() 320 annotator.process(subprogram, namespace, self.global_namespace) 321 322 # NOTE: Annotate the node with invocation details. 323 324 return invoke 325 326 # Utility methods. 327 328 def make_items(self, invocation, subprogram): 329 # NOTE: Support star and dstar. 330 args = invocation.args 331 params = subprogram.params 332 items = [] 333 keywords = {} 334 335 # Process the specified arguments. 336 337 for arg in args: 338 if isinstance(arg, Keyword): 339 keywords[arg.name] = arg.expr 340 continue 341 elif params: 342 param, default = params[0] 343 if arg is None: 344 arg = self.dispatch(default) 345 else: 346 raise TypeError, "Invocation has too many arguments." 347 items.append((param, arg.types)) 348 params = params[1:] 349 350 # Collect the remaining defaults. 351 352 while params: 353 param, default = params[0] 354 if keywords.has_key(param): 355 arg = keywords[param] 356 else: 357 arg = self.dispatch(default) 358 items.append((param, arg.types)) 359 params = params[1:] 360 361 # Add star and dstar. 362 363 if invocation.star is not None: 364 if subprogram.star is not None: 365 param, default = subprogram.star 366 items.append((param, invocation.star.types)) 367 else: 368 raise TypeError, "Invocation provides unwanted *args." 369 elif subprogram.star is not None: 370 param, default = subprogram.star 371 items.append((param, self.dispatch(default))) 372 373 if invocation.dstar is not None: 374 if subprogram.dstar is not None: 375 param, default = subprogram.dstar 376 items.append((param, invocation.dstar.types)) 377 else: 378 raise TypeError, "Invocation provides unwanted **args." 379 elif subprogram.dstar is not None: 380 param, default = subprogram.dstar 381 items.append((param, self.dispatch(default))) 382 383 return items 384 385 def make_namespace(self, items): 386 namespace = Namespace() 387 namespace.merge_items(items) 388 return namespace 389 390 # vim: tabstop=4 expandtab shiftwidth=4