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