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