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, 2007 Paul Boddie <paul@boddie.org.uk> 8 9 This program is free software; you can redistribute it and/or modify it under 10 the terms of the GNU General Public License as published by the Free Software 11 Foundation; either version 3 of the License, or (at your option) any later 12 version. 13 14 This program is distributed in the hope that it will be useful, but WITHOUT 15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 16 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 17 details. 18 19 You should have received a copy of the GNU General Public License along with 20 this program. If not, see <http://www.gnu.org/licenses/>. 21 22 -------- 23 24 To use this module, the easiest approach is to use the fix function: 25 26 fix(module) 27 28 The more complicated approach involves instantiating a Fixer object: 29 30 fixer = Fixer() 31 32 Then, applying the fixer to an existing module: 33 34 fixer.process(module) 35 36 If a module containing built-in classes and functions exists, apply the fixer as 37 follows: 38 39 fixer.process(module, builtins) 40 """ 41 42 from simplify.simplified import * 43 44 # Fixing of name-related operations. 45 46 class Fixer(Visitor): 47 48 """ 49 The name fixer which traverses the program nodes in a module, typically 50 depth-first, and maintains a record of name usage in the different 51 namespaces. As a consequence of various observations, some parts of the 52 program node tree are modified with different operations employed to those 53 originally defined. 54 55 There are two kinds of subprograms in modules: functions/methods and 56 internal subprograms which support things like loops. The latter kind of 57 subprogram may acquire the locals from their callers and must therefore be 58 traversed with information from such callers. Thus, we choose the top-level 59 code and all functions/methods as roots for processing, following 60 invocations of internal subprograms in order to reach all subprograms that 61 are defined in each module. 62 63 top-level 64 ... 65 invoke function 66 ... 67 invoke loop -> subprogram (internal) 68 ... 69 70 subprogram (function) 71 ... 72 invoke loop -> subprogram (internal) 73 ... 74 75 ... 76 77 The above approach should guarantee that all subprograms are traversed and 78 that all name lookups are correctly categorised. 79 """ 80 81 def __init__(self): 82 83 "Initialise the name fixer." 84 85 Visitor.__init__(self) 86 87 # Satisfy visitor issues. 88 89 self.visitor = self 90 91 def process(self, module, builtins=None): 92 93 """ 94 Process the given 'module' optionally using some 'builtins' to reference 95 built-in objects. 96 """ 97 98 # The fixer maintains a list of transformed subprograms (added for each 99 # of the processing "roots" and also for each invoked internal 100 # subprogram), along with a list of current subprograms (used to avoid 101 # recursion issues) and a list of current namespaces (used to recall 102 # namespaces upon invoking internal subprograms). 103 104 self.subprograms = [] 105 self.current_subprograms = [] 106 self.current_namespaces = [] 107 108 # First, process the top-level code, finding out which names are 109 # defined at that level. 110 111 self.global_namespace = None 112 self.module = module 113 self.builtins = builtins or module 114 115 self.process_node(self.module) 116 117 # Then, process all functions and methods, providing a global namespace. 118 # By setting a global namespace, we influence the resolution of names: 119 # those which are global to the top-level module (processed above) are 120 # considered as built-in names, whereas those which are global to a 121 # function or method are searched for in the global namespace. 122 123 self.global_namespace = self.namespace 124 125 for subprogram in self.module.simplifier.subprograms: 126 127 # Internal subprograms are skipped here and processed specially via 128 # Invoke nodes. 129 130 if not getattr(subprogram, "internal", 0): 131 self.subprograms.append(self.process_node(subprogram)) 132 133 # Ultimately, we redefine the list of subprograms on the visitor. 134 135 self.module.simplifier.subprograms = self.subprograms 136 return self.module 137 138 def process_node(self, node, namespace=None): 139 140 """ 141 Process a subprogram or module 'node', discovering from attributes on 142 'node' any initial locals. Return a modified subprogram or module. 143 """ 144 145 # Do not process subprograms already being processed. 146 147 if node in self.current_subprograms: 148 return None 149 150 # Obtain a namespace either based on locals or on a structure. 151 152 structure = structure=getattr(node, "structure", None) 153 154 # If passed some namespace, use that as the current namespace. 155 156 if namespace is not None: 157 self.namespace.merge_namespace(namespace) 158 else: 159 self.namespace = NameOrganiser(structure) 160 161 # Record the current subprogram and namespace. 162 163 self.current_subprograms.append(node) 164 self.current_namespaces.append(self.namespace) 165 166 # NOTE: Avoid PEP 227 (nested scopes) whilst permitting references to a 167 # NOTE: subprogram within itself. Do not define the name of the function 168 # NOTE: within a method definition. 169 170 if isinstance(node, Subprogram) and getattr(node, "name", None) is not None and not getattr(node, "is_method", 0): 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", "nodes"): 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 visitInvokeRef(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 if invoke.share_locals: 406 subprogram = self.process_node(invoke.ref, self.namespace) 407 else: 408 subprogram = self.process_node(invoke.ref) 409 410 if subprogram is not None: 411 self.subprograms.append(subprogram) 412 return invoke 413 414 class ScopeMismatch(Exception): 415 pass 416 417 class NameOrganiser: 418 419 """ 420 A local namespace which may either relate to a genuine set of function 421 locals or the initialisation of a structure. 422 """ 423 424 def __init__(self, structure=None): 425 426 "Initialise the namespace with an optional 'structure'." 427 428 self.structure = structure 429 if structure is not None: 430 self.local = "structure" 431 else: 432 self.local = "local" 433 434 # Names may be self.local or "global". 435 436 self.names = {} 437 438 def make_global(self, name): 439 if not self.names.has_key(name): 440 self.names[name] = "global" 441 elif self.names[name] == self.local: 442 raise ScopeMismatch, "Name '%s' already considered as %s." % (name, self.local) 443 444 def find_for_load(self, name): 445 return self.names.get(name, "global") 446 447 def find_for_store(self, name): 448 return self.names.get(name, self.local) 449 450 def store(self, name): 451 if self.names.get(name) != "global": 452 self.names[name] = self.local 453 else: 454 raise ScopeMismatch, "Name '%s' already considered as global." % name 455 456 def merge(self, name, scope): 457 if self.names.get(name) in (None, scope): 458 self.names[name] = scope 459 else: 460 raise ScopeMismatch, "Name '%s' already considered as %s." % (name, self.names[name]) 461 462 def merge_namespace(self, namespace): 463 self.merge_items(namespace.names.items()) 464 465 def merge_items(self, items): 466 for name, scope in items: 467 self.merge(name, scope) 468 469 def __repr__(self): 470 return repr(self.names) 471 472 # Convenience functions. 473 474 def fix(module, builtins=None): 475 476 """ 477 Fix the names in the given 'module', also employing the optional 'builtins' 478 module, if specified. 479 """ 480 481 fixer = Fixer() 482 if builtins is not None: 483 fixer.process(module, builtins) 484 else: 485 fixer.process(module) 486 487 # vim: tabstop=4 expandtab shiftwidth=4