paulb@19 | 1 | #!/usr/bin/env python |
paulb@19 | 2 | |
paulb@19 | 3 | """ |
paulb@24 | 4 | Annotate simplified AST structures. The code in this module operates upon nodes |
paulb@24 | 5 | which are produced when simplifying AST node trees originating from the compiler |
paulb@24 | 6 | module. |
paulb@19 | 7 | |
paulb@19 | 8 | Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk> |
paulb@19 | 9 | |
paulb@19 | 10 | This software is free software; you can redistribute it and/or |
paulb@19 | 11 | modify it under the terms of the GNU General Public License as |
paulb@19 | 12 | published by the Free Software Foundation; either version 2 of |
paulb@19 | 13 | the License, or (at your option) any later version. |
paulb@19 | 14 | |
paulb@19 | 15 | This software is distributed in the hope that it will be useful, |
paulb@19 | 16 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
paulb@19 | 17 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
paulb@19 | 18 | GNU General Public License for more details. |
paulb@19 | 19 | |
paulb@19 | 20 | You should have received a copy of the GNU General Public |
paulb@19 | 21 | License along with this library; see the file LICENCE.txt |
paulb@19 | 22 | If not, write to the Free Software Foundation, Inc., |
paulb@19 | 23 | 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA |
paulb@19 | 24 | """ |
paulb@19 | 25 | |
paulb@19 | 26 | from simplified import * |
paulb@19 | 27 | import compiler |
paulb@19 | 28 | |
paulb@24 | 29 | class System: |
paulb@24 | 30 | |
paulb@24 | 31 | "A class maintaining the state of the annotation system." |
paulb@24 | 32 | |
paulb@24 | 33 | def __init__(self): |
paulb@24 | 34 | self.count = 0 |
paulb@24 | 35 | def init(self, node): |
paulb@24 | 36 | if not hasattr(node, "types"): |
paulb@24 | 37 | node.types = [] |
paulb@24 | 38 | def annotate(self, node, types): |
paulb@24 | 39 | self.init(node) |
paulb@24 | 40 | for type in types: |
paulb@24 | 41 | if type not in node.types: |
paulb@24 | 42 | node.types.append(type) |
paulb@24 | 43 | self.count += 1 |
paulb@24 | 44 | |
paulb@24 | 45 | system = System() |
paulb@24 | 46 | |
paulb@24 | 47 | # Namespaces and related abstractions. |
paulb@24 | 48 | |
paulb@19 | 49 | class Namespace: |
paulb@24 | 50 | |
paulb@24 | 51 | """ |
paulb@24 | 52 | A local namespace which may either relate to a genuine set of function |
paulb@24 | 53 | locals or the initialisation of a structure. |
paulb@24 | 54 | """ |
paulb@24 | 55 | |
paulb@21 | 56 | def __init__(self, local_is_structure=0): |
paulb@20 | 57 | if local_is_structure: |
paulb@20 | 58 | self.local = "structure" |
paulb@20 | 59 | else: |
paulb@20 | 60 | self.local = "local" |
paulb@19 | 61 | self.names = {} |
paulb@19 | 62 | self.not_local = [] |
paulb@19 | 63 | |
paulb@19 | 64 | def make_global(self, name): |
paulb@19 | 65 | if name not in self.not_local: |
paulb@19 | 66 | self.not_local.append(name) |
paulb@19 | 67 | |
paulb@21 | 68 | def find_for_store(self, name): |
paulb@20 | 69 | if name not in self.not_local: |
paulb@20 | 70 | return self.local |
paulb@20 | 71 | else: |
paulb@20 | 72 | return "global" |
paulb@20 | 73 | |
paulb@21 | 74 | def find_for_load(self, name): |
paulb@21 | 75 | if name not in self.not_local and self.names.has_key(name): |
paulb@21 | 76 | return self.local |
paulb@21 | 77 | else: |
paulb@21 | 78 | return "global" |
paulb@21 | 79 | |
paulb@19 | 80 | def store(self, name, types): |
paulb@19 | 81 | if name not in self.not_local: |
paulb@19 | 82 | self.names[name] = types |
paulb@19 | 83 | else: |
paulb@21 | 84 | raise KeyError, name |
paulb@19 | 85 | |
paulb@19 | 86 | def load(self, name): |
paulb@19 | 87 | if name in self.not_local or not self.names.has_key(name): |
paulb@21 | 88 | raise KeyError, name |
paulb@19 | 89 | else: |
paulb@19 | 90 | return self.names[name] |
paulb@19 | 91 | |
paulb@19 | 92 | def merge(self, namespace): |
paulb@24 | 93 | self.merge_items(namespace.names.items()) |
paulb@24 | 94 | |
paulb@24 | 95 | def merge_items(self, items): |
paulb@24 | 96 | for name, types in items: |
paulb@19 | 97 | if not self.names.has_key(name): |
paulb@19 | 98 | self.names[name] = types |
paulb@19 | 99 | else: |
paulb@19 | 100 | existing = self.names[name] |
paulb@19 | 101 | for type in types: |
paulb@19 | 102 | if type not in existing: |
paulb@19 | 103 | existing.append(type) |
paulb@19 | 104 | |
paulb@24 | 105 | class Attribute: |
paulb@24 | 106 | |
paulb@24 | 107 | """ |
paulb@24 | 108 | An attribute abstraction, indicating the type of the attribute along with |
paulb@24 | 109 | its context or origin. |
paulb@24 | 110 | """ |
paulb@24 | 111 | |
paulb@24 | 112 | def __init__(self, context, type): |
paulb@24 | 113 | self.context = context |
paulb@24 | 114 | self.type = type |
paulb@24 | 115 | |
paulb@24 | 116 | def __eq__(self, other): |
paulb@24 | 117 | return hasattr(other, "type") and other.type == self.type or other == self.type |
paulb@24 | 118 | |
paulb@24 | 119 | # Annotation. |
paulb@19 | 120 | |
paulb@20 | 121 | class Annotator(Visitor): |
paulb@24 | 122 | |
paulb@24 | 123 | """ |
paulb@24 | 124 | The type annotator which traverses the program nodes, typically depth-first, |
paulb@24 | 125 | and maintains a record of the current set of types applying to the currently |
paulb@24 | 126 | considered operation. Such types are also recorded on the nodes, and a |
paulb@24 | 127 | special "system" record is maintained to monitor the level of annotation |
paulb@24 | 128 | activity with a view to recognising when no more annotations are possible. |
paulb@24 | 129 | """ |
paulb@24 | 130 | |
paulb@19 | 131 | def __init__(self): |
paulb@19 | 132 | Visitor.__init__(self) |
paulb@24 | 133 | self.system = system |
paulb@19 | 134 | self.types = None |
paulb@19 | 135 | self.temp = {} |
paulb@19 | 136 | |
paulb@24 | 137 | def process(self, node, locals=None, globals=None): |
paulb@24 | 138 | |
paulb@24 | 139 | """ |
paulb@24 | 140 | Process a subprogram or module 'node', indicating any initial 'locals' |
paulb@24 | 141 | and 'globals' if either are defined. Return an annotated subprogram or |
paulb@24 | 142 | module. Note that this method may mutate nodes in the original program. |
paulb@24 | 143 | """ |
paulb@24 | 144 | |
paulb@19 | 145 | if hasattr(node, "structure"): |
paulb@24 | 146 | self.structure = node.structure; has_structure = 1 |
paulb@20 | 147 | else: |
paulb@24 | 148 | self.structure = None; has_structure = 0 |
paulb@20 | 149 | |
paulb@20 | 150 | self.namespace = Namespace(self.structure is not None) |
paulb@24 | 151 | if locals is not None: |
paulb@24 | 152 | self.namespace.merge(locals) |
paulb@24 | 153 | |
paulb@24 | 154 | self.global_namespace = globals or self.namespace # NOTE: Improve this. |
paulb@21 | 155 | |
paulb@20 | 156 | if has_structure: |
paulb@19 | 157 | node.structure.namespace = self.namespace |
paulb@21 | 158 | node.namespace = self.namespace |
paulb@19 | 159 | |
paulb@20 | 160 | self.visitor = self |
paulb@20 | 161 | result = self.dispatch(node) |
paulb@20 | 162 | |
paulb@20 | 163 | return result |
paulb@20 | 164 | |
paulb@24 | 165 | def annotate(self, node): |
paulb@24 | 166 | |
paulb@24 | 167 | "Annotate the given 'node' in the system." |
paulb@24 | 168 | |
paulb@24 | 169 | self.system.annotate(node, self.types) |
paulb@24 | 170 | |
paulb@19 | 171 | def default(self, node): |
paulb@24 | 172 | |
paulb@24 | 173 | """ |
paulb@24 | 174 | Process the given 'node', given that it does not have a specific |
paulb@24 | 175 | handler. |
paulb@24 | 176 | """ |
paulb@24 | 177 | |
paulb@21 | 178 | for attr in ("args",): |
paulb@19 | 179 | value = getattr(node, attr, None) |
paulb@19 | 180 | if value is not None: |
paulb@20 | 181 | setattr(node, attr, self.dispatches(value)) |
paulb@19 | 182 | for attr in ("expr", "lvalue", "test", "handler", "star", "dstar"): |
paulb@19 | 183 | value = getattr(node, attr, None) |
paulb@19 | 184 | if value is not None: |
paulb@20 | 185 | setattr(node, attr, self.dispatch(value)) |
paulb@19 | 186 | for attr in ("body", "else_", "finally_", "code"): |
paulb@19 | 187 | value = getattr(node, attr, None) |
paulb@19 | 188 | if value is not None: |
paulb@20 | 189 | setattr(node, attr, self.dispatches(value)) |
paulb@20 | 190 | return node |
paulb@20 | 191 | |
paulb@20 | 192 | def dispatch(self, node, *args): |
paulb@20 | 193 | return Visitor.dispatch(self, node, *args) |
paulb@19 | 194 | |
paulb@19 | 195 | def visitGlobal(self, global_): |
paulb@19 | 196 | for name in global_.names: |
paulb@21 | 197 | self.namespace.make_global(name) |
paulb@20 | 198 | return global_ |
paulb@19 | 199 | |
paulb@19 | 200 | def visitLoadRef(self, loadref): |
paulb@19 | 201 | self.types = [loadref.ref] |
paulb@24 | 202 | self.annotate(loadref) |
paulb@20 | 203 | return loadref |
paulb@19 | 204 | |
paulb@19 | 205 | def visitLoadName(self, loadname): |
paulb@21 | 206 | scope = self.namespace.find_for_load(loadname.name) |
paulb@21 | 207 | if scope == "structure": |
paulb@24 | 208 | result = self.dispatch(LoadAttr(expr=LoadRef(ref=self.structure), name=loadname.name)) |
paulb@21 | 209 | elif scope == "global": |
paulb@24 | 210 | result = self.dispatch(LoadGlobal(name=loadname.name)) |
paulb@20 | 211 | else: |
paulb@21 | 212 | self.types = self.namespace.load(loadname.name) |
paulb@24 | 213 | result = loadname |
paulb@24 | 214 | self.annotate(result) |
paulb@24 | 215 | return result |
paulb@19 | 216 | |
paulb@19 | 217 | def visitStoreName(self, storename): |
paulb@21 | 218 | scope = self.namespace.find_for_store(storename.name) |
paulb@21 | 219 | if scope == "structure": |
paulb@20 | 220 | return self.dispatch(StoreAttr(lvalue=LoadRef(ref=self.structure), name=storename.name, expr=storename.expr)) |
paulb@21 | 221 | elif scope == "global": |
paulb@21 | 222 | return self.dispatch(StoreGlobal(name=storename.name, expr=storename.expr)) |
paulb@20 | 223 | else: |
paulb@21 | 224 | storename.expr = self.dispatch(storename.expr) |
paulb@21 | 225 | self.namespace.store(storename.name, self.types) |
paulb@20 | 226 | return storename |
paulb@19 | 227 | |
paulb@21 | 228 | def visitLoadGlobal(self, loadglobal): |
paulb@21 | 229 | self.types = self.global_namespace.load(loadglobal.name) |
paulb@24 | 230 | self.annotate(loadglobal) |
paulb@21 | 231 | return loadglobal |
paulb@21 | 232 | |
paulb@21 | 233 | def visitStoreGlobal(self, storeglobal): |
paulb@21 | 234 | storeglobal.expr = self.dispatch(storeglobal.expr) |
paulb@21 | 235 | |
paulb@21 | 236 | # NOTE: This may always be a merge operation. |
paulb@21 | 237 | |
paulb@21 | 238 | self.global_namespace.store(storeglobal.name, self.types) |
paulb@21 | 239 | return storeglobal |
paulb@21 | 240 | |
paulb@19 | 241 | def visitLoadTemp(self, loadtemp): |
paulb@19 | 242 | index = getattr(loadtemp, "index", None) |
paulb@19 | 243 | self.types = self.temp[index] |
paulb@24 | 244 | self.annotate(loadtemp) |
paulb@20 | 245 | return loadtemp |
paulb@19 | 246 | |
paulb@19 | 247 | def visitStoreTemp(self, storetemp): |
paulb@21 | 248 | storetemp.expr = self.dispatch(storetemp.expr) |
paulb@19 | 249 | index = getattr(storetemp, "index", None) |
paulb@19 | 250 | self.temp[index] = self.types |
paulb@20 | 251 | return storetemp |
paulb@19 | 252 | |
paulb@19 | 253 | def visitReleaseTemp(self, releasetemp): |
paulb@19 | 254 | index = getattr(releasetemp, "index", None) |
paulb@19 | 255 | del self.temp[index] |
paulb@20 | 256 | return releasetemp |
paulb@20 | 257 | |
paulb@20 | 258 | def visitLoadAttr(self, loadattr): |
paulb@21 | 259 | loadattr.expr = self.dispatch(loadattr.expr) |
paulb@20 | 260 | types = [] |
paulb@20 | 261 | for ref in self.types: |
paulb@24 | 262 | for type in ref.namespace.load(loadattr.name): |
paulb@24 | 263 | types.append(Attribute(ref, type)) |
paulb@20 | 264 | self.types = types |
paulb@24 | 265 | self.annotate(loadattr) |
paulb@20 | 266 | return loadattr |
paulb@20 | 267 | |
paulb@20 | 268 | def visitStoreAttr(self, storeattr): |
paulb@21 | 269 | storeattr.expr = self.dispatch(storeattr.expr) |
paulb@20 | 270 | expr = self.types |
paulb@21 | 271 | storeattr.lvalue = self.dispatch(storeattr.lvalue) |
paulb@20 | 272 | for ref in self.types: |
paulb@20 | 273 | ref.namespace.store(storeattr.name, expr) |
paulb@20 | 274 | return storeattr |
paulb@19 | 275 | |
paulb@24 | 276 | def visitInvoke(self, invoke): |
paulb@24 | 277 | invoke.expr = self.dispatch(invoke.expr) |
paulb@24 | 278 | expr = self.types |
paulb@24 | 279 | types = [] |
paulb@24 | 280 | args = [] |
paulb@24 | 281 | |
paulb@24 | 282 | # Get type information for regular arguments. |
paulb@24 | 283 | |
paulb@24 | 284 | for arg in invoke.args: |
paulb@24 | 285 | args.append(self.dispatch(arg)) |
paulb@24 | 286 | types.append(self.types) |
paulb@24 | 287 | |
paulb@24 | 288 | # Get type information for star and dstar arguments. |
paulb@24 | 289 | |
paulb@24 | 290 | if invoke.star is not None: |
paulb@24 | 291 | param, default = invoke.star |
paulb@24 | 292 | default = self.dispatch(default) |
paulb@24 | 293 | invoke.star = param, default |
paulb@24 | 294 | types.append(default.types) |
paulb@24 | 295 | |
paulb@24 | 296 | if invoke.dstar is not None: |
paulb@24 | 297 | param, default = invoke.dstar |
paulb@24 | 298 | default = self.dispatch(default) |
paulb@24 | 299 | invoke.dstar = param, default |
paulb@24 | 300 | types.append(default.types) |
paulb@24 | 301 | |
paulb@24 | 302 | invoke.args = args |
paulb@24 | 303 | invoke.types = expr |
paulb@24 | 304 | |
paulb@24 | 305 | # NOTE: Now locate and invoke the subprogram. |
paulb@24 | 306 | |
paulb@24 | 307 | for subprogram in expr: |
paulb@24 | 308 | items = self.make_items(invoke, subprogram) |
paulb@24 | 309 | self.process(subprogram, self.make_namespace(items), self.global_namespace) |
paulb@24 | 310 | |
paulb@24 | 311 | return invoke |
paulb@24 | 312 | |
paulb@24 | 313 | def make_items(self, invocation, subprogram): |
paulb@24 | 314 | # NOTE: Support star and dstar. |
paulb@24 | 315 | args = invocation.args |
paulb@24 | 316 | params = subprogram.params |
paulb@24 | 317 | items = [] |
paulb@24 | 318 | keywords = {} |
paulb@24 | 319 | |
paulb@24 | 320 | # Process the specified arguments. |
paulb@24 | 321 | |
paulb@24 | 322 | for arg in args: |
paulb@24 | 323 | if isinstance(arg, Keyword): |
paulb@24 | 324 | keywords[arg.name] = arg.expr |
paulb@24 | 325 | continue |
paulb@24 | 326 | elif params: |
paulb@24 | 327 | param, default = params[0] |
paulb@24 | 328 | if arg is None: |
paulb@24 | 329 | arg = self.dispatch(default) |
paulb@24 | 330 | else: |
paulb@24 | 331 | raise TypeError, "Invocation has too many arguments." |
paulb@24 | 332 | items.append((param, arg.types)) |
paulb@24 | 333 | params = params[1:] |
paulb@24 | 334 | |
paulb@24 | 335 | # Collect the remaining defaults. |
paulb@24 | 336 | |
paulb@24 | 337 | while params: |
paulb@24 | 338 | param, default = params[0] |
paulb@24 | 339 | if keywords.has_key(param): |
paulb@24 | 340 | arg = keywords[param] |
paulb@24 | 341 | else: |
paulb@24 | 342 | arg = self.dispatch(default) |
paulb@24 | 343 | items.append((param, arg.types)) |
paulb@24 | 344 | params = params[1:] |
paulb@24 | 345 | |
paulb@24 | 346 | # Add star and dstar. |
paulb@24 | 347 | |
paulb@24 | 348 | if invocation.star is not None: |
paulb@24 | 349 | if subprogram.star is not None: |
paulb@24 | 350 | param, default = subprogram.star |
paulb@24 | 351 | items.append((param, invocation.star.types)) |
paulb@24 | 352 | else: |
paulb@24 | 353 | raise TypeError, "Invocation provides unwanted *args." |
paulb@24 | 354 | elif subprogram.star is not None: |
paulb@24 | 355 | param, default = subprogram.star |
paulb@24 | 356 | items.append((param, self.dispatch(default))) |
paulb@24 | 357 | |
paulb@24 | 358 | if invocation.dstar is not None: |
paulb@24 | 359 | if subprogram.dstar is not None: |
paulb@24 | 360 | param, default = subprogram.dstar |
paulb@24 | 361 | items.append((param, invocation.dstar.types)) |
paulb@24 | 362 | else: |
paulb@24 | 363 | raise TypeError, "Invocation provides unwanted **args." |
paulb@24 | 364 | elif subprogram.dstar is not None: |
paulb@24 | 365 | param, default = subprogram.dstar |
paulb@24 | 366 | items.append((param, self.dispatch(default))) |
paulb@24 | 367 | |
paulb@24 | 368 | return items |
paulb@24 | 369 | |
paulb@24 | 370 | def make_namespace(self, items): |
paulb@24 | 371 | namespace = Namespace() |
paulb@24 | 372 | namespace.merge_items(items) |
paulb@24 | 373 | return namespace |
paulb@24 | 374 | |
paulb@19 | 375 | # vim: tabstop=4 expandtab shiftwidth=4 |