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( 251 LoadAttr(loadname.original, loadname.defining, 252 expr=LoadRef(loadname.original, 253 ref=self.namespace.structure), 254 name=loadname.name, 255 nstype="structure") 256 ) 257 258 # For global accesses (ie. those outside the local namespace)... 259 260 elif scope == "global": 261 262 # Where a distinct global namespace exists, examine it. 263 264 if self.global_namespace is not None: 265 scope = self.global_namespace.find_for_load(loadname.name) 266 267 # Where the name is outside the global namespace, it must be a 268 # built-in. 269 270 if scope == "global": 271 result = self.dispatch( 272 LoadAttr(loadname.original, loadname.defining, 273 expr=LoadRef(loadname.original, 274 ref=self.builtins), 275 name=loadname.name, 276 nstype="module") 277 ) 278 279 # Otherwise, it is within the global namespace and must be a 280 # global. 281 282 else: 283 result = self.dispatch( 284 LoadAttr(loadname.original, loadname.defining, 285 expr=LoadRef(loadname.original, 286 ref=self.module), 287 name=loadname.name, 288 nstype="module") 289 ) 290 291 # Where no global namespace exists, we are at the module level and 292 # must be accessing a built-in. 293 294 else: 295 result = self.dispatch( 296 LoadAttr(loadname.original, loadname.defining, 297 expr=LoadRef(loadname.original, 298 ref=self.builtins), 299 name=loadname.name, 300 nstype="module") 301 ) 302 303 # For local accesses... 304 305 else: 306 307 # Where a distinct global namespace exists, it must be a local. 308 309 if self.global_namespace is not None: 310 result = loadname 311 312 # Otherwise, we must be accessing a global (which is local at the 313 # module level). 314 315 else: 316 result = self.dispatch( 317 LoadAttr(loadname.original, loadname.defining, 318 expr=LoadRef(loadname.original, 319 ref=self.module), 320 name=loadname.name, 321 nstype="module") 322 ) 323 324 return result 325 326 def visitStoreName(self, storename): 327 328 "Transform the 'storename' node to a specific, scope-sensitive node." 329 330 scope = self.namespace.find_for_store(storename.name) 331 332 # For structure namespaces, store an attribute. 333 334 if scope == "structure": 335 return self.dispatch( 336 StoreAttr(storename.original, storename.defining, 337 lvalue=LoadRef(storename.original, 338 ref=self.namespace.structure), 339 name=storename.name, 340 expr=storename.expr, 341 nstype="structure") 342 ) 343 344 # Where the name is outside the local namespace, disallow any built-in 345 # assignment and store the name globally. 346 347 elif scope == "global": 348 return self.dispatch( 349 StoreAttr(storename.original, storename.defining, 350 lvalue=LoadRef(storename.original, 351 ref=self.module), 352 name=storename.name, 353 expr=storename.expr, 354 nstype="module") 355 ) 356 357 # For local namespace accesses... 358 359 else: 360 self.namespace.store(storename.name) 361 362 # If a distinct global namespace exists, it must be a local access. 363 364 if self.global_namespace is not None: 365 return storename 366 367 # Otherwise, the name is being set at the module level and is 368 # considered global. 369 370 else: 371 return self.dispatch( 372 StoreAttr(storename.original, storename.defining, 373 lvalue=LoadRef(storename.original, 374 ref=self.module), 375 name=storename.name, 376 expr=storename.expr, 377 nstype="module") 378 ) 379 380 def visitInvokeFunction(self, invoke): 381 382 "Transform the 'invoke' node, performing processing on subprograms." 383 384 return self.default(invoke) 385 386 def visitInvokeBlock(self, invoke): 387 388 "Transform the 'invoke' node, performing processing on subprograms." 389 390 # The special case of internal subprogram invocation is addressed by 391 # propagating namespace information to the subprogram and processing it. 392 393 subprogram = self.process_node(invoke.expr.ref, self.namespace) 394 if subprogram is not None: 395 self.subprograms.append(subprogram) 396 return invoke 397 398 class ScopeMismatch(Exception): 399 pass 400 401 class NameOrganiser: 402 403 """ 404 A local namespace which may either relate to a genuine set of function 405 locals or the initialisation of a structure. 406 """ 407 408 def __init__(self, structure=None): 409 410 "Initialise the namespace with an optional 'structure'." 411 412 self.structure = structure 413 if structure is not None: 414 self.local = "structure" 415 else: 416 self.local = "local" 417 418 # Names may be self.local or "global". 419 420 self.names = {} 421 422 def make_global(self, name): 423 if not self.names.has_key(name): 424 self.names[name] = "global" 425 elif self.names[name] == self.local: 426 raise ScopeMismatch, "Name '%s' already considered as %s." % (name, self.local) 427 428 def find_for_load(self, name): 429 return self.names.get(name, "global") 430 431 def find_for_store(self, name): 432 return self.names.get(name, self.local) 433 434 def store(self, name): 435 if self.names.get(name) != "global": 436 self.names[name] = self.local 437 else: 438 raise ScopeMismatch, "Name '%s' already considered as global." % name 439 440 def merge(self, name, scope): 441 if self.names.get(name) in (None, scope): 442 self.names[name] = scope 443 else: 444 raise ScopeMismatch, "Name '%s' already considered as %s." % (name, self.names[name]) 445 446 def merge_namespace(self, namespace): 447 self.merge_items(namespace.names.items()) 448 449 def merge_items(self, items): 450 for name, scope in items: 451 self.merge(name, scope) 452 453 def __repr__(self): 454 return repr(self.names) 455 456 # Convenience functions. 457 458 def fix(module, builtins=None): 459 460 """ 461 Fix the names in the given 'module', also employing the optional 'builtins' 462 module, if specified. 463 """ 464 465 fixer = Fixer() 466 if builtins is not None: 467 fixer.process(module, builtins) 468 else: 469 fixer.process(module) 470 471 # vim: tabstop=4 expandtab shiftwidth=4