1 #!/usr/bin/env python 2 3 """ 4 Fix name-related operations. The code in this module operates upon simplified 5 program node trees. 6 7 Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk> 8 9 This software is free software; you can redistribute it and/or 10 modify it under the terms of the GNU General Public License as 11 published by the Free Software Foundation; either version 2 of 12 the License, or (at your option) any later version. 13 14 This software is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public 20 License along with this library; see the file LICENCE.txt 21 If not, write to the Free Software Foundation, Inc., 22 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA 23 24 -------- 25 26 To use this module, the easiest approach is to use the fix function: 27 28 fix(module) 29 30 The more complicated approach involves instantiating a Fixer object: 31 32 fixer = Fixer() 33 34 Then, applying the fixer to an existing module: 35 36 fixer.process(module) 37 38 If a module containing built-in classes and functions exists, apply the fixer as 39 follows: 40 41 fixer.process(module, builtins) 42 """ 43 44 from simplified import * 45 46 # Fixing of name-related operations. 47 48 class Fixer(Visitor): 49 50 """ 51 The name fixer which traverses the program nodes in a module, typically 52 depth-first, and maintains a record of name usage in the different 53 namespaces. As a consequence of various observations, some parts of the 54 program node tree are modified with different operations employed to those 55 originally defined. 56 57 There are two kinds of subprograms in modules: functions/methods and 58 internal subprograms which support things like loops. The latter kind of 59 subprogram may acquire the locals from their callers and must therefore be 60 traversed with information from such callers. Thus, we choose the top-level 61 code and all functions/methods as roots for processing, following 62 invocations of internal subprograms in order to reach all subprograms that 63 are defined in each module. 64 65 top-level 66 ... 67 invoke function 68 ... 69 invoke loop -> subprogram (internal) 70 ... 71 72 subprogram (function) 73 ... 74 invoke loop -> subprogram (internal) 75 ... 76 77 ... 78 79 The above approach should guarantee that all subprograms are traversed and 80 that all name lookups are correctly categorised. 81 """ 82 83 def __init__(self): 84 85 "Initialise the name fixer." 86 87 Visitor.__init__(self) 88 89 # Satisfy visitor issues. 90 91 self.visitor = self 92 93 def process(self, module, builtins=None): 94 95 """ 96 Process the given 'module' optionally using some 'builtins' to reference 97 built-in objects. 98 """ 99 100 # The fixer maintains a list of transformed subprograms (added for each 101 # of the processing "roots" and also for each invoked internal 102 # subprogram), along with a list of current subprograms (used to avoid 103 # recursion issues) and a list of current namespaces (used to recall 104 # namespaces upon invoking internal subprograms). 105 106 self.subprograms = [] 107 self.current_subprograms = [] 108 self.current_namespaces = [] 109 110 # First, process the top-level code, finding out which names are 111 # defined at that level. 112 113 self.global_namespace = None 114 self.module = module 115 self.builtins = builtins 116 117 self.process_node(self.module) 118 119 # Then, process all functions and methods, providing a global namespace. 120 # By setting a global namespace, we influence the resolution of names: 121 # those which are global to the top-level module (processed above) are 122 # considered as built-in names, whereas those which are global to a 123 # function or method are searched for in the global namespace. 124 125 self.global_namespace = self.namespace 126 127 for subprogram in self.module.simplifier.subprograms: 128 129 # Internal subprograms are skipped here and processed specially via 130 # Invoke nodes. 131 132 if not getattr(subprogram, "acquire_locals", 0): 133 self.subprograms.append(self.process_node(subprogram)) 134 135 # Ultimately, we redefine the list of subprograms on the visitor. 136 137 self.module.simplifier.subprograms = self.subprograms 138 return self.module 139 140 def process_node(self, node, namespace=None): 141 142 """ 143 Process a subprogram or module 'node', discovering from attributes on 144 'node' any initial locals. Return a modified subprogram or module. 145 """ 146 147 # Do not process subprograms already being processed. 148 149 if node in self.current_subprograms: 150 return None 151 152 # Obtain a namespace either based on locals or on a structure. 153 154 structure = structure=getattr(node, "structure", None) 155 self.namespace = NameOrganiser(structure) 156 157 # Record the current subprogram and namespace. 158 159 self.current_subprograms.append(node) 160 self.current_namespaces.append(self.namespace) 161 162 # If passed some namespace, merge its contents into this namespace. 163 164 if namespace is not None: 165 self.namespace.merge_namespace(namespace) 166 167 # Register the names of parameters in the namespace. 168 169 if hasattr(node, "params"): 170 new_params = [] 171 for param, default in node.params: 172 new_params.append((param, self.dispatch(default))) 173 self.namespace.store(param) 174 node.params = new_params 175 if getattr(node, "star", None): 176 param, default = node.star 177 self.namespace.store(param) 178 node.star = param, self.dispatch(default) 179 if getattr(node, "dstar", None): 180 param, default = node.dstar 181 self.namespace.store(param) 182 node.dstar = param, self.dispatch(default) 183 184 # Add namespace details to any structure involved. 185 186 if hasattr(node, "structure") and node.structure is not None: 187 188 # Initialise bases where appropriate. 189 190 if hasattr(node.structure, "bases"): 191 bases = [] 192 for base in node.structure.bases: 193 bases.append(self.dispatch(base)) 194 node.structure.bases = bases 195 196 # Dispatch to the code itself. 197 198 result = self.dispatch(node) 199 result.organiser = self.namespace 200 201 # Restore the previous subprogram and namespace. 202 203 self.current_namespaces.pop() 204 if self.current_namespaces: 205 self.namespace = self.current_namespaces[-1] 206 self.current_subprograms.pop() 207 208 return result 209 210 # Visitor methods. 211 212 def default(self, node): 213 214 """ 215 Process the given 'node', given that it does not have a specific 216 handler. 217 """ 218 219 for attr in ("args",): 220 value = getattr(node, attr, None) 221 if value is not None: 222 setattr(node, attr, self.dispatches(value)) 223 for attr in ("expr", "lvalue", "test", "star", "dstar"): 224 value = getattr(node, attr, None) 225 if value is not None: 226 setattr(node, attr, self.dispatch(value)) 227 for attr in ("body", "else_", "handler", "finally_", "code", "choices"): 228 value = getattr(node, attr, None) 229 if value is not None: 230 setattr(node, attr, self.dispatches(value)) 231 return node 232 233 def dispatch(self, node, *args): 234 return Visitor.dispatch(self, node, *args) 235 236 def visitGlobal(self, global_): 237 for name in global_.names: 238 self.namespace.make_global(name) 239 return global_ 240 241 def visitLoadName(self, loadname): 242 243 "Transform the 'loadname' node to a specific, scope-sensitive node." 244 245 scope = self.namespace.find_for_load(loadname.name) 246 247 # For structure namespaces, load an attribute. 248 249 if scope == "structure": 250 result = self.dispatch(LoadAttr(expr=LoadRef(ref=self.namespace.structure), name=loadname.name, nstype="structure")) 251 252 # For global accesses (ie. those outside the local namespace)... 253 254 elif scope == "global": 255 256 # Where a distinct global namespace exists, examine it. 257 258 if self.global_namespace is not None: 259 scope = self.global_namespace.find_for_load(loadname.name) 260 261 # Where the name is outside the global namespace, it must be a 262 # built-in. 263 264 if scope == "global": 265 result = self.dispatch(LoadAttr(expr=LoadRef(ref=self.builtins), name=loadname.name, nstype="module")) 266 267 # Otherwise, it is within the global namespace and must be a 268 # global. 269 270 else: 271 result = self.dispatch(LoadAttr(expr=LoadRef(ref=self.module), name=loadname.name, nstype="module")) 272 273 # Where no global namespace exists, we are at the module level and 274 # must be accessing a built-in. 275 276 else: 277 result = self.dispatch(LoadAttr(expr=LoadRef(ref=self.builtins), name=loadname.name, nstype="module")) 278 279 # For local accesses... 280 281 else: 282 283 # Where a distinct global namespace exists, it must be a local. 284 285 if self.global_namespace is not None: 286 result = loadname 287 288 # Otherwise, we must be accessing a global (which is local at the 289 # module level). 290 291 else: 292 result = self.dispatch(LoadAttr(expr=LoadRef(ref=self.module), name=loadname.name, nstype="module")) 293 294 return result 295 296 def visitStoreName(self, storename): 297 298 "Transform the 'storename' node to a specific, scope-sensitive node." 299 300 scope = self.namespace.find_for_store(storename.name) 301 302 # For structure namespaces, store an attribute. 303 304 if scope == "structure": 305 return self.dispatch(StoreAttr(lvalue=LoadRef(ref=self.namespace.structure), name=storename.name, expr=storename.expr, nstype="structure")) 306 307 # Where the name is outside the local namespace, disallow any built-in 308 # assignment and store the name globally. 309 310 elif scope == "global": 311 return self.dispatch(StoreAttr(lvalue=LoadRef(ref=self.module), name=storename.name, expr=storename.expr, nstype="module")) 312 313 # For local namespace accesses... 314 315 else: 316 self.namespace.store(storename.name) 317 318 # If a distinct global namespace exists, it must be a local access. 319 320 if self.global_namespace is not None: 321 return storename 322 323 # Otherwise, the name is being set at the module level and is 324 # considered global. 325 326 else: 327 return self.dispatch(StoreAttr(lvalue=LoadRef(ref=self.module), name=storename.name, expr=storename.expr, nstype="module")) 328 329 def visitInvokeFunction(self, invoke): 330 331 "Transform the 'invoke' node, performing processing on subprograms." 332 333 return self.default(invoke) 334 335 def visitInvokeBlock(self, invoke): 336 337 "Transform the 'invoke' node, performing processing on subprograms." 338 339 # The special case of internal subprogram invocation is addressed by 340 # propagating namespace information to the subprogram and processing it. 341 342 subprogram = self.process_node(invoke.expr.ref, self.namespace) 343 if subprogram is not None: 344 self.subprograms.append(subprogram) 345 return invoke 346 347 class ScopeMismatch(Exception): 348 pass 349 350 class NameOrganiser: 351 352 """ 353 A local namespace which may either relate to a genuine set of function 354 locals or the initialisation of a structure. 355 """ 356 357 def __init__(self, structure=None): 358 359 "Initialise the namespace with an optional 'structure'." 360 361 self.structure = structure 362 if structure is not None: 363 self.local = "structure" 364 else: 365 self.local = "local" 366 367 # Names may be self.local or "global". 368 369 self.names = {} 370 371 def make_global(self, name): 372 if not self.names.has_key(name): 373 self.names[name] = "global" 374 elif self.names[name] == self.local: 375 raise ScopeMismatch, "Name '%s' already considered as %s." % (name, self.local) 376 377 def find_for_load(self, name): 378 return self.names.get(name, "global") 379 380 def find_for_store(self, name): 381 return self.names.get(name, self.local) 382 383 def store(self, name): 384 if self.names.get(name) != "global": 385 self.names[name] = self.local 386 else: 387 raise ScopeMismatch, "Name '%s' already considered as global." % name 388 389 def merge(self, name, scope): 390 if self.names.get(name) in (None, scope): 391 self.names[name] = scope 392 else: 393 raise ScopeMismatch, "Name '%s' already considered as %s." % (name, self.names[name]) 394 395 def merge_namespace(self, namespace): 396 self.merge_items(namespace.names.items()) 397 398 def merge_items(self, items): 399 for name, scope in items: 400 self.merge(name, scope) 401 402 def __repr__(self): 403 return repr(self.names) 404 405 # Convenience functions. 406 407 def fix(module, builtins=None): 408 409 """ 410 Fix the names in the given 'module', also employing the optional 'builtins' 411 module, if specified. 412 """ 413 414 fixer = Fixer() 415 if builtins is not None: 416 fixer.process(module, builtins) 417 else: 418 fixer.process(module) 419 420 # vim: tabstop=4 expandtab shiftwidth=4