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