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 or module 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, "internal", 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 # NOTE: Avoid PEP 227 (nested scopes) whilst permitting references to a 168 # NOTE: subprogram within itself. 169 170 if hasattr(node, "name") and node.name is not None: 171 self.namespace.store(node.name) 172 173 # Register the names of parameters in the namespace. 174 175 if hasattr(node, "params"): 176 new_params = [] 177 for param, default in node.params: 178 new_params.append((param, self.dispatch(default))) 179 self.namespace.store(param) 180 node.params = new_params 181 if getattr(node, "star", None): 182 param, default = node.star 183 self.namespace.store(param) 184 node.star = param, self.dispatch(default) 185 if getattr(node, "dstar", None): 186 param, default = node.dstar 187 self.namespace.store(param) 188 node.dstar = param, self.dispatch(default) 189 190 # Add namespace details to any structure involved. 191 192 if hasattr(node, "structure") and node.structure is not None: 193 194 # Initialise bases where appropriate. 195 196 if hasattr(node.structure, "bases"): 197 bases = [] 198 for base in node.structure.bases: 199 bases.append(self.dispatch(base)) 200 node.structure.bases = bases 201 202 # Dispatch to the code itself. 203 204 result = self.dispatch(node) 205 result.organiser = self.namespace 206 207 # Restore the previous subprogram and namespace. 208 209 self.current_namespaces.pop() 210 if self.current_namespaces: 211 self.namespace = self.current_namespaces[-1] 212 self.current_subprograms.pop() 213 214 return result 215 216 # Visitor methods. 217 218 def default(self, node): 219 220 """ 221 Process the given 'node', given that it does not have a specific 222 handler. 223 """ 224 225 for attr in ("pos_args",): 226 value = getattr(node, attr, None) 227 if value is not None: 228 setattr(node, attr, self.dispatches(value)) 229 for attr in ("kw_args",): 230 value = getattr(node, attr, None) 231 if value is not None: 232 setattr(node, attr, self.dispatch_dict(value)) 233 for attr in ("expr", "lvalue", "test", "star", "dstar"): 234 value = getattr(node, attr, None) 235 if value is not None: 236 setattr(node, attr, self.dispatch(value)) 237 for attr in ("body", "else_", "handler", "finally_", "code", "choices"): 238 value = getattr(node, attr, None) 239 if value is not None: 240 setattr(node, attr, self.dispatches(value)) 241 return node 242 243 def dispatch(self, node, *args): 244 return Visitor.dispatch(self, node, *args) 245 246 def visitGlobal(self, global_): 247 for name in global_.names: 248 self.namespace.make_global(name) 249 return global_ 250 251 def visitLoadName(self, loadname): 252 253 "Transform the 'loadname' node to a specific, scope-sensitive node." 254 255 scope = self.namespace.find_for_load(loadname.name) 256 257 # For structure namespaces, load an attribute. 258 259 if scope == "structure": 260 result = self.dispatch( 261 LoadAttr(loadname.original, loadname.defining, 262 expr=LoadRef(loadname.original, 263 ref=self.namespace.structure), 264 name=loadname.name, 265 nstype="structure") 266 ) 267 268 # For global accesses (ie. those outside the local namespace)... 269 270 elif scope == "global": 271 272 # Where a distinct global namespace exists, examine it. 273 274 if self.global_namespace is not None: 275 scope = self.global_namespace.find_for_load(loadname.name) 276 277 # Where the name is outside the global namespace, it must be a 278 # built-in. 279 280 if scope == "global": 281 result = self.dispatch( 282 LoadAttr(loadname.original, loadname.defining, 283 expr=LoadRef(loadname.original, 284 ref=self.builtins), 285 name=loadname.name, 286 nstype="module") 287 ) 288 289 # Otherwise, it is within the global namespace and must be a 290 # global. 291 292 else: 293 result = self.dispatch( 294 LoadAttr(loadname.original, loadname.defining, 295 expr=LoadRef(loadname.original, 296 ref=self.module), 297 name=loadname.name, 298 nstype="module") 299 ) 300 301 # Where no global namespace exists, we are at the module level and 302 # must be accessing a built-in. 303 304 else: 305 result = self.dispatch( 306 LoadAttr(loadname.original, loadname.defining, 307 expr=LoadRef(loadname.original, 308 ref=self.builtins), 309 name=loadname.name, 310 nstype="module") 311 ) 312 313 # For local accesses... 314 315 else: 316 317 # Where a distinct global namespace exists, it must be a local. 318 319 if self.global_namespace is not None: 320 result = loadname 321 322 # Otherwise, we must be accessing a global (which is local at the 323 # module level). 324 325 else: 326 result = self.dispatch( 327 LoadAttr(loadname.original, loadname.defining, 328 expr=LoadRef(loadname.original, 329 ref=self.module), 330 name=loadname.name, 331 nstype="module") 332 ) 333 334 return result 335 336 def visitStoreName(self, storename): 337 338 "Transform the 'storename' node to a specific, scope-sensitive node." 339 340 scope = self.namespace.find_for_store(storename.name) 341 342 # For structure namespaces, store an attribute. 343 344 if scope == "structure": 345 self.namespace.store(storename.name) 346 347 return self.dispatch( 348 StoreAttr(storename.original, storename.defining, 349 lvalue=LoadRef(storename.original, 350 ref=self.namespace.structure), 351 name=storename.name, 352 expr=storename.expr, 353 nstype="structure") 354 ) 355 356 # Where the name is outside the local namespace, disallow any built-in 357 # assignment and store the name globally. 358 359 elif scope == "global": 360 return self.dispatch( 361 StoreAttr(storename.original, storename.defining, 362 lvalue=LoadRef(storename.original, 363 ref=self.module), 364 name=storename.name, 365 expr=storename.expr, 366 nstype="module") 367 ) 368 369 # For local namespace accesses... 370 371 else: 372 self.namespace.store(storename.name) 373 374 # If a distinct global namespace exists, it must be a local access. 375 376 if self.global_namespace is not None: 377 return storename 378 379 # Otherwise, the name is being set at the module level and is 380 # considered global. 381 382 else: 383 return self.dispatch( 384 StoreAttr(storename.original, storename.defining, 385 lvalue=LoadRef(storename.original, 386 ref=self.module), 387 name=storename.name, 388 expr=storename.expr, 389 nstype="module") 390 ) 391 392 def visitInvokeFunction(self, invoke): 393 394 "Transform the 'invoke' node, performing processing on subprograms." 395 396 return self.default(invoke) 397 398 def visitInvokeBlock(self, invoke): 399 400 "Transform the 'invoke' node, performing processing on subprograms." 401 402 # The special case of internal subprogram invocation is addressed by 403 # propagating namespace information to the subprogram and processing it. 404 405 subprogram = self.process_node(invoke.expr.ref, self.namespace) 406 if subprogram is not None: 407 self.subprograms.append(subprogram) 408 return invoke 409 410 class ScopeMismatch(Exception): 411 pass 412 413 class NameOrganiser: 414 415 """ 416 A local namespace which may either relate to a genuine set of function 417 locals or the initialisation of a structure. 418 """ 419 420 def __init__(self, structure=None): 421 422 "Initialise the namespace with an optional 'structure'." 423 424 self.structure = structure 425 if structure is not None: 426 self.local = "structure" 427 else: 428 self.local = "local" 429 430 # Names may be self.local or "global". 431 432 self.names = {} 433 434 def make_global(self, name): 435 if not self.names.has_key(name): 436 self.names[name] = "global" 437 elif self.names[name] == self.local: 438 raise ScopeMismatch, "Name '%s' already considered as %s." % (name, self.local) 439 440 def find_for_load(self, name): 441 return self.names.get(name, "global") 442 443 def find_for_store(self, name): 444 return self.names.get(name, self.local) 445 446 def store(self, name): 447 if self.names.get(name) != "global": 448 self.names[name] = self.local 449 else: 450 raise ScopeMismatch, "Name '%s' already considered as global." % name 451 452 def merge(self, name, scope): 453 if self.names.get(name) in (None, scope): 454 self.names[name] = scope 455 else: 456 raise ScopeMismatch, "Name '%s' already considered as %s." % (name, self.names[name]) 457 458 def merge_namespace(self, namespace): 459 self.merge_items(namespace.names.items()) 460 461 def merge_items(self, items): 462 for name, scope in items: 463 self.merge(name, scope) 464 465 def __repr__(self): 466 return repr(self.names) 467 468 # Convenience functions. 469 470 def fix(module, builtins=None): 471 472 """ 473 Fix the names in the given 'module', also employing the optional 'builtins' 474 module, if specified. 475 """ 476 477 fixer = Fixer() 478 if builtins is not None: 479 fixer.process(module, builtins) 480 else: 481 fixer.process(module) 482 483 # vim: tabstop=4 expandtab shiftwidth=4