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