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 = self.namespace = NameOrganiser() 112 self.module = module 113 self.builtins = builtins or module 114 115 self.process_node(self.module, self.namespace) 116 117 # Then, process all functions and methods. 118 119 for subprogram in self.module.simplifier.subprograms: 120 121 # Internal subprograms are skipped here and processed specially via 122 # Invoke nodes. 123 124 if not subprogram.internal: 125 self.subprograms.add(self.process_node(subprogram)) 126 127 # Ultimately, we redefine the list of subprograms on the visitor. 128 129 self.module.simplifier.subprograms = self.subprograms 130 return self.module 131 132 def process_node(self, node, namespace=None): 133 134 """ 135 Process a subprogram or module 'node', discovering from attributes on 136 'node' any initial locals. Return a modified subprogram or module. 137 """ 138 139 # Do not process subprograms already being processed. 140 141 if node in self.current_subprograms: 142 return None 143 144 # Obtain a namespace either based on locals or on a structure. 145 146 structure = node.structure 147 148 # If passed some namespace, use that as the current namespace. 149 150 if namespace is not None: 151 self.namespace.merge_namespace(namespace) 152 else: 153 self.namespace = NameOrganiser(structure) 154 155 # Record the current subprogram and namespace. 156 157 self.current_subprograms.append(node) 158 self.current_namespaces.append(self.namespace) 159 160 # NOTE: Avoid PEP 227 (nested scopes) whilst permitting references to a 161 # NOTE: subprogram within itself. Do not define the name of the function 162 # NOTE: within a method definition. 163 164 if isinstance(node, Subprogram) and node.name is not None and not node.is_method: 165 self.namespace.store(node.name) 166 167 # Register the names of parameters in the namespace. 168 169 if 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 node.star: 176 param, default = node.star 177 self.namespace.store(param) 178 node.star = param, self.dispatch(default) 179 if node.dstar: 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 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 ("pos_args",): 220 value = getattr(node, attr, None) 221 if value is not None: 222 setattr(node, attr, self.dispatches(value)) 223 for attr in ("kw_args",): 224 value = getattr(node, attr, None) 225 if value is not None: 226 setattr(node, attr, self.dispatch_dict(value)) 227 for attr in ("expr", "lvalue", "test", "star", "dstar"): 228 value = getattr(node, attr, None) 229 if value is not None: 230 setattr(node, attr, self.dispatch(value)) 231 for attr in ("body", "else_", "handler", "finally_", "code", "choices", "nodes"): 232 value = getattr(node, attr, None) 233 if value is not None: 234 setattr(node, attr, self.dispatches(value)) 235 return node 236 237 def visitGlobal(self, global_): 238 for name in global_.names: 239 self.namespace.make_global(name) 240 return global_ 241 242 def visitLoadName(self, loadname): 243 244 "Transform the 'loadname' node to a specific, scope-sensitive node." 245 246 scope = self.namespace.find_for_load(loadname.name) 247 248 # For structure namespaces, load an attribute. 249 250 if scope == "structure": 251 result = self.dispatch( 252 LoadAttr(loadname.original, loadname.defining, 253 expr=LoadRef(loadname.original, 254 ref=self.namespace.structure), 255 name=loadname.name, 256 nstype="structure") 257 ) 258 259 # For global accesses (ie. those outside the local namespace)... 260 261 elif scope == "global": 262 263 # Where a distinct global namespace exists, examine it. 264 265 if self.global_namespace is not self.namespace: 266 scope = self.global_namespace.find_for_load(loadname.name) 267 268 # Where the name is outside the global namespace, it must be a 269 # built-in. 270 271 if scope == "global": 272 result = self.dispatch( 273 LoadAttr(loadname.original, loadname.defining, 274 expr=LoadRef(loadname.original, 275 ref=self.builtins), 276 name=loadname.name, 277 nstype="module") 278 ) 279 280 # Otherwise, it is within the global namespace and must be a 281 # global. 282 283 else: 284 result = self.dispatch( 285 LoadAttr(loadname.original, loadname.defining, 286 expr=LoadRef(loadname.original, 287 ref=self.module), 288 name=loadname.name, 289 nstype="module") 290 ) 291 292 # Where no global namespace exists, we are at the module level and 293 # must be accessing a built-in. 294 295 else: 296 result = self.dispatch( 297 LoadAttr(loadname.original, loadname.defining, 298 expr=LoadRef(loadname.original, 299 ref=self.builtins), 300 name=loadname.name, 301 nstype="module") 302 ) 303 304 # For local accesses... 305 306 else: 307 308 # Where a distinct global namespace exists, it must be a local. 309 310 if self.global_namespace is not self.namespace: 311 result = loadname 312 313 # Otherwise, we must be accessing a global (which is local at the 314 # module level). 315 316 else: 317 result = self.dispatch( 318 LoadAttr(loadname.original, loadname.defining, 319 expr=LoadRef(loadname.original, 320 ref=self.module), 321 name=loadname.name, 322 nstype="module") 323 ) 324 325 return result 326 327 def visitStoreName(self, storename): 328 329 "Transform the 'storename' node to a specific, scope-sensitive node." 330 331 scope = self.namespace.find_for_store(storename.name) 332 333 # For structure namespaces, store an attribute. 334 335 if scope == "structure": 336 self.namespace.store(storename.name) 337 338 return self.dispatch( 339 StoreAttr(storename.original, storename.defining, 340 lvalue=LoadRef(storename.original, 341 ref=self.namespace.structure), 342 name=storename.name, 343 expr=storename.expr, 344 nstype="structure") 345 ) 346 347 # Where the name is outside the local namespace, disallow any built-in 348 # assignment and store the name globally. 349 350 elif scope == "global": 351 return self.dispatch( 352 StoreAttr(storename.original, storename.defining, 353 lvalue=LoadRef(storename.original, 354 ref=self.module), 355 name=storename.name, 356 expr=storename.expr, 357 nstype="module") 358 ) 359 360 # For local namespace accesses... 361 362 else: 363 self.namespace.store(storename.name) 364 365 # If a distinct global namespace exists, it must be a local access. 366 367 if self.global_namespace is not self.namespace: 368 return storename 369 370 # Otherwise, the name is being set at the module level and is 371 # considered global. 372 373 else: 374 return self.dispatch( 375 StoreAttr(storename.original, storename.defining, 376 lvalue=LoadRef(storename.original, 377 ref=self.module), 378 name=storename.name, 379 expr=storename.expr, 380 nstype="module") 381 ) 382 383 def visitInvokeFunction(self, invoke): 384 385 "Transform the 'invoke' node, performing processing on subprograms." 386 387 return self.default(invoke) 388 389 def visitInvokeRef(self, invoke): 390 391 "Transform the 'invoke' node, performing processing on subprograms." 392 393 # The special case of internal subprogram invocation is addressed by 394 # propagating namespace information to the subprogram and processing it. 395 396 if invoke.share_locals: 397 subprogram = self.process_node(invoke.ref, self.namespace) 398 else: 399 subprogram = self.process_node(invoke.ref) 400 401 if subprogram is not None: 402 self.subprograms.add(subprogram) 403 return invoke 404 405 class ScopeMismatch(Exception): 406 pass 407 408 class NameOrganiser: 409 410 """ 411 A local namespace which may either relate to a genuine set of function 412 locals or the initialisation of a structure. 413 """ 414 415 def __init__(self, structure=None): 416 417 "Initialise the namespace with an optional 'structure'." 418 419 self.structure = structure 420 if structure is not None: 421 self.local = "structure" 422 else: 423 self.local = "local" 424 425 # Names may be self.local or "global". 426 427 self.names = {} 428 429 def make_global(self, name): 430 if not self.names.has_key(name): 431 self.names[name] = "global" 432 elif self.names[name] == self.local: 433 raise ScopeMismatch, "Name '%s' already considered as %s." % (name, self.local) 434 435 def find_for_load(self, name): 436 return self.names.get(name, "global") 437 438 def find_for_store(self, name): 439 return self.names.get(name, self.local) 440 441 def store(self, name): 442 if self.names.get(name) != "global": 443 self.names[name] = self.local 444 else: 445 raise ScopeMismatch, "Name '%s' already considered as global." % name 446 447 def merge(self, name, scope): 448 if self.names.get(name) in (None, scope): 449 self.names[name] = scope 450 else: 451 raise ScopeMismatch, "Name '%s' already considered as %s." % (name, self.names[name]) 452 453 def merge_namespace(self, namespace): 454 self.merge_items(namespace.names.items()) 455 456 def merge_items(self, items): 457 for name, scope in items: 458 self.merge(name, scope) 459 460 def __repr__(self): 461 return repr(self.names) 462 463 # Convenience functions. 464 465 def fix(module, builtins=None): 466 467 """ 468 Fix the names in the given 'module', also employing the optional 'builtins' 469 module, if specified. 470 """ 471 472 fixer = Fixer() 473 if builtins is not None: 474 fixer.process(module, builtins) 475 else: 476 fixer.process(module) 477 478 # vim: tabstop=4 expandtab shiftwidth=4