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, local_is_structure=0): 57 if local_is_structure: 58 self.local = "structure" 59 else: 60 self.local = "local" 61 self.names = {} 62 self.not_local = [] 63 64 def make_global(self, name): 65 if name not in self.not_local: 66 self.not_local.append(name) 67 68 def find_for_store(self, name): 69 if name not in self.not_local: 70 return self.local 71 else: 72 return "global" 73 74 def find_for_load(self, name): 75 if name not in self.not_local and self.names.has_key(name): 76 return self.local 77 else: 78 return "global" 79 80 def store(self, name, types): 81 if name not in self.not_local: 82 self.names[name] = types 83 else: 84 raise KeyError, name 85 86 def load(self, name): 87 if name in self.not_local or not self.names.has_key(name): 88 raise KeyError, name 89 else: 90 return self.names[name] 91 92 def merge(self, namespace): 93 self.merge_items(namespace.names.items()) 94 95 def merge_items(self, items): 96 for name, types in items: 97 if not self.names.has_key(name): 98 self.names[name] = types 99 else: 100 existing = self.names[name] 101 for type in types: 102 if type not in existing: 103 existing.append(type) 104 105 class Attribute: 106 107 """ 108 An attribute abstraction, indicating the type of the attribute along with 109 its context or origin. 110 """ 111 112 def __init__(self, context, type): 113 self.context = context 114 self.type = type 115 116 def __eq__(self, other): 117 return hasattr(other, "type") and other.type == self.type or other == self.type 118 119 # Annotation. 120 121 class Annotator(Visitor): 122 123 """ 124 The type annotator which traverses the program nodes, typically depth-first, 125 and maintains a record of the current set of types applying to the currently 126 considered operation. Such types are also recorded on the nodes, and a 127 special "system" record is maintained to monitor the level of annotation 128 activity with a view to recognising when no more annotations are possible. 129 """ 130 131 def __init__(self): 132 Visitor.__init__(self) 133 self.system = system 134 self.types = None 135 self.temp = {} 136 137 def process(self, node, locals=None, globals=None): 138 139 """ 140 Process a subprogram or module 'node', indicating any initial 'locals' 141 and 'globals' if either are defined. Return an annotated subprogram or 142 module. Note that this method may mutate nodes in the original program. 143 """ 144 145 if hasattr(node, "structure"): 146 self.structure = node.structure; has_structure = 1 147 else: 148 self.structure = None; has_structure = 0 149 150 self.namespace = Namespace(self.structure is not None) 151 if locals is not None: 152 self.namespace.merge(locals) 153 154 self.global_namespace = globals or self.namespace # NOTE: Improve this. 155 156 if has_structure: 157 node.structure.namespace = self.namespace 158 node.namespace = self.namespace 159 160 self.visitor = self 161 result = self.dispatch(node) 162 163 return result 164 165 def annotate(self, node): 166 167 "Annotate the given 'node' in the system." 168 169 self.system.annotate(node, self.types) 170 171 def default(self, node): 172 173 """ 174 Process the given 'node', given that it does not have a specific 175 handler. 176 """ 177 178 for attr in ("args",): 179 value = getattr(node, attr, None) 180 if value is not None: 181 setattr(node, attr, self.dispatches(value)) 182 for attr in ("expr", "lvalue", "test", "handler", "star", "dstar"): 183 value = getattr(node, attr, None) 184 if value is not None: 185 setattr(node, attr, self.dispatch(value)) 186 for attr in ("body", "else_", "finally_", "code"): 187 value = getattr(node, attr, None) 188 if value is not None: 189 setattr(node, attr, self.dispatches(value)) 190 return node 191 192 def dispatch(self, node, *args): 193 return Visitor.dispatch(self, node, *args) 194 195 def visitGlobal(self, global_): 196 for name in global_.names: 197 self.namespace.make_global(name) 198 return global_ 199 200 def visitLoadRef(self, loadref): 201 self.types = [loadref.ref] 202 self.annotate(loadref) 203 return loadref 204 205 def visitLoadName(self, loadname): 206 scope = self.namespace.find_for_load(loadname.name) 207 if scope == "structure": 208 result = self.dispatch(LoadAttr(expr=LoadRef(ref=self.structure), name=loadname.name)) 209 elif scope == "global": 210 result = self.dispatch(LoadGlobal(name=loadname.name)) 211 else: 212 self.types = self.namespace.load(loadname.name) 213 result = loadname 214 self.annotate(result) 215 return result 216 217 def visitStoreName(self, storename): 218 scope = self.namespace.find_for_store(storename.name) 219 if scope == "structure": 220 return self.dispatch(StoreAttr(lvalue=LoadRef(ref=self.structure), name=storename.name, expr=storename.expr)) 221 elif scope == "global": 222 return self.dispatch(StoreGlobal(name=storename.name, expr=storename.expr)) 223 else: 224 storename.expr = self.dispatch(storename.expr) 225 self.namespace.store(storename.name, self.types) 226 return storename 227 228 def visitLoadGlobal(self, loadglobal): 229 self.types = self.global_namespace.load(loadglobal.name) 230 self.annotate(loadglobal) 231 return loadglobal 232 233 def visitStoreGlobal(self, storeglobal): 234 storeglobal.expr = self.dispatch(storeglobal.expr) 235 236 # NOTE: This may always be a merge operation. 237 238 self.global_namespace.store(storeglobal.name, self.types) 239 return storeglobal 240 241 def visitLoadTemp(self, loadtemp): 242 index = getattr(loadtemp, "index", None) 243 self.types = self.temp[index] 244 self.annotate(loadtemp) 245 return loadtemp 246 247 def visitStoreTemp(self, storetemp): 248 storetemp.expr = self.dispatch(storetemp.expr) 249 index = getattr(storetemp, "index", None) 250 self.temp[index] = self.types 251 return storetemp 252 253 def visitReleaseTemp(self, releasetemp): 254 index = getattr(releasetemp, "index", None) 255 del self.temp[index] 256 return releasetemp 257 258 def visitLoadAttr(self, loadattr): 259 loadattr.expr = self.dispatch(loadattr.expr) 260 types = [] 261 for ref in self.types: 262 for type in ref.namespace.load(loadattr.name): 263 types.append(Attribute(ref, type)) 264 self.types = types 265 self.annotate(loadattr) 266 return loadattr 267 268 def visitStoreAttr(self, storeattr): 269 storeattr.expr = self.dispatch(storeattr.expr) 270 expr = self.types 271 storeattr.lvalue = self.dispatch(storeattr.lvalue) 272 for ref in self.types: 273 ref.namespace.store(storeattr.name, expr) 274 return storeattr 275 276 def visitInvoke(self, invoke): 277 invoke.expr = self.dispatch(invoke.expr) 278 expr = self.types 279 types = [] 280 args = [] 281 282 # Get type information for regular arguments. 283 284 for arg in invoke.args: 285 args.append(self.dispatch(arg)) 286 types.append(self.types) 287 288 # Get type information for star and dstar arguments. 289 290 if invoke.star is not None: 291 param, default = invoke.star 292 default = self.dispatch(default) 293 invoke.star = param, default 294 types.append(default.types) 295 296 if invoke.dstar is not None: 297 param, default = invoke.dstar 298 default = self.dispatch(default) 299 invoke.dstar = param, default 300 types.append(default.types) 301 302 invoke.args = args 303 invoke.types = expr 304 305 # NOTE: Now locate and invoke the subprogram. 306 307 for subprogram in expr: 308 items = self.make_items(invoke, subprogram) 309 self.process(subprogram, self.make_namespace(items), self.global_namespace) 310 311 return invoke 312 313 def make_items(self, invocation, subprogram): 314 # NOTE: Support star and dstar. 315 args = invocation.args 316 params = subprogram.params 317 items = [] 318 keywords = {} 319 320 # Process the specified arguments. 321 322 for arg in args: 323 if isinstance(arg, Keyword): 324 keywords[arg.name] = arg.expr 325 continue 326 elif params: 327 param, default = params[0] 328 if arg is None: 329 arg = self.dispatch(default) 330 else: 331 raise TypeError, "Invocation has too many arguments." 332 items.append((param, arg.types)) 333 params = params[1:] 334 335 # Collect the remaining defaults. 336 337 while params: 338 param, default = params[0] 339 if keywords.has_key(param): 340 arg = keywords[param] 341 else: 342 arg = self.dispatch(default) 343 items.append((param, arg.types)) 344 params = params[1:] 345 346 # Add star and dstar. 347 348 if invocation.star is not None: 349 if subprogram.star is not None: 350 param, default = subprogram.star 351 items.append((param, invocation.star.types)) 352 else: 353 raise TypeError, "Invocation provides unwanted *args." 354 elif subprogram.star is not None: 355 param, default = subprogram.star 356 items.append((param, self.dispatch(default))) 357 358 if invocation.dstar is not None: 359 if subprogram.dstar is not None: 360 param, default = subprogram.dstar 361 items.append((param, invocation.dstar.types)) 362 else: 363 raise TypeError, "Invocation provides unwanted **args." 364 elif subprogram.dstar is not None: 365 param, default = subprogram.dstar 366 items.append((param, self.dispatch(default))) 367 368 return items 369 370 def make_namespace(self, items): 371 namespace = Namespace() 372 namespace.merge_items(items) 373 return namespace 374 375 # vim: tabstop=4 expandtab shiftwidth=4