1 """Module symbol-table generator""" 2 3 from compiler import ast 4 from compiler.consts import SC_LOCAL, SC_GLOBAL, SC_FREE, SC_CELL, SC_UNKNOWN 5 from compiler.misc import mangle 6 import types 7 8 9 import sys 10 11 MANGLE_LEN = 256 12 13 class Scope: 14 # XXX how much information do I need about each name? 15 def __init__(self, name, module, klass=None): 16 self.name = name 17 self.module = module 18 self.defs = {} 19 self.uses = {} 20 self.globals = {} 21 self.params = {} 22 self.frees = {} 23 self.cells = {} 24 self.children = [] 25 # nested is true if the class could contain free variables, 26 # i.e. if it is nested within another function. 27 self.nested = None 28 self.generator = None 29 self.klass = None 30 if klass is not None: 31 for i in range(len(klass)): 32 if klass[i] != '_': 33 self.klass = klass[i:] 34 break 35 36 def __repr__(self): 37 return "<%s: %s>" % (self.__class__.__name__, self.name) 38 39 def mangle(self, name): 40 if self.klass is None: 41 return name 42 return mangle(name, self.klass) 43 44 def add_def(self, name): 45 self.defs[self.mangle(name)] = 1 46 47 def add_use(self, name): 48 self.uses[self.mangle(name)] = 1 49 50 def add_global(self, name): 51 name = self.mangle(name) 52 if name in self.uses or name in self.defs: 53 pass # XXX warn about global following def/use 54 if name in self.params: 55 raise SyntaxError, "%s in %s is global and parameter" % \ 56 (name, self.name) 57 self.globals[name] = 1 58 self.module.add_def(name) 59 60 def add_param(self, name): 61 name = self.mangle(name) 62 self.defs[name] = 1 63 self.params[name] = 1 64 65 def get_names(self): 66 d = {} 67 d.update(self.defs) 68 d.update(self.uses) 69 d.update(self.globals) 70 return d.keys() 71 72 def add_child(self, child): 73 self.children.append(child) 74 75 def get_children(self): 76 return self.children 77 78 def DEBUG(self): 79 print >> sys.stderr, self.name, self.nested and "nested" or "" 80 print >> sys.stderr, "\tglobals: ", self.globals 81 print >> sys.stderr, "\tcells: ", self.cells 82 print >> sys.stderr, "\tdefs: ", self.defs 83 print >> sys.stderr, "\tuses: ", self.uses 84 print >> sys.stderr, "\tfrees:", self.frees 85 86 def check_name(self, name): 87 """Return scope of name. 88 89 The scope of a name could be LOCAL, GLOBAL, FREE, or CELL. 90 """ 91 if name in self.globals: 92 return SC_GLOBAL 93 if name in self.cells: 94 return SC_CELL 95 if name in self.defs: 96 return SC_LOCAL 97 if self.nested and (name in self.frees or name in self.uses): 98 return SC_FREE 99 if self.nested: 100 return SC_UNKNOWN 101 else: 102 return SC_GLOBAL 103 104 def get_free_vars(self): 105 if not self.nested: 106 return () 107 free = {} 108 free.update(self.frees) 109 for name in self.uses.keys(): 110 if name not in self.defs and name not in self.globals: 111 free[name] = 1 112 return free.keys() 113 114 def handle_children(self): 115 for child in self.children: 116 frees = child.get_free_vars() 117 globals = self.add_frees(frees) 118 for name in globals: 119 child.force_global(name) 120 121 def force_global(self, name): 122 """Force name to be global in scope. 123 124 Some child of the current node had a free reference to name. 125 When the child was processed, it was labelled a free 126 variable. Now that all its enclosing scope have been 127 processed, the name is known to be a global or builtin. So 128 walk back down the child chain and set the name to be global 129 rather than free. 130 131 Be careful to stop if a child does not think the name is 132 free. 133 """ 134 self.globals[name] = 1 135 if name in self.frees: 136 del self.frees[name] 137 for child in self.children: 138 if child.check_name(name) == SC_FREE: 139 child.force_global(name) 140 141 def add_frees(self, names): 142 """Process list of free vars from nested scope. 143 144 Returns a list of names that are either 1) declared global in the 145 parent or 2) undefined in a top-level parent. In either case, 146 the nested scope should treat them as globals. 147 """ 148 child_globals = [] 149 for name in names: 150 sc = self.check_name(name) 151 if self.nested: 152 if sc == SC_UNKNOWN or sc == SC_FREE \ 153 or isinstance(self, ClassScope): 154 self.frees[name] = 1 155 elif sc == SC_GLOBAL: 156 child_globals.append(name) 157 elif isinstance(self, FunctionScope) and sc == SC_LOCAL: 158 self.cells[name] = 1 159 elif sc != SC_CELL: 160 child_globals.append(name) 161 else: 162 if sc == SC_LOCAL: 163 self.cells[name] = 1 164 elif sc != SC_CELL: 165 child_globals.append(name) 166 return child_globals 167 168 def get_cell_vars(self): 169 return self.cells.keys() 170 171 class ModuleScope(Scope): 172 __super_init = Scope.__init__ 173 174 def __init__(self): 175 self.__super_init("global", self) 176 177 class FunctionScope(Scope): 178 pass 179 180 class GenExprScope(Scope): 181 __super_init = Scope.__init__ 182 183 __counter = 1 184 185 def __init__(self, module, klass=None): 186 i = self.__counter 187 self.__counter += 1 188 self.__super_init("generator expression<%d>"%i, module, klass) 189 self.add_param('.0') 190 191 def get_names(self): 192 keys = Scope.get_names(self) 193 return keys 194 195 class LambdaScope(FunctionScope): 196 __super_init = Scope.__init__ 197 198 __counter = 1 199 200 def __init__(self, module, klass=None): 201 i = self.__counter 202 self.__counter += 1 203 self.__super_init("lambda.%d" % i, module, klass) 204 205 class ClassScope(Scope): 206 __super_init = Scope.__init__ 207 208 def __init__(self, name, module): 209 self.__super_init(name, module, name) 210 211 class SymbolVisitor: 212 def __init__(self): 213 self.scopes = {} 214 self.klass = None 215 216 # node that define new scopes 217 218 def visitModule(self, node): 219 scope = self.module = self.scopes[node] = ModuleScope() 220 self.visit(node.node, scope) 221 222 visitExpression = visitModule 223 224 def visitFunction(self, node, parent): 225 if node.decorators: 226 self.visit(node.decorators, parent) 227 parent.add_def(node.name) 228 for n in node.defaults: 229 self.visit(n, parent) 230 scope = FunctionScope(node.name, self.module, self.klass) 231 if parent.nested or isinstance(parent, FunctionScope): 232 scope.nested = 1 233 self.scopes[node] = scope 234 self._do_args(scope, node.argnames) 235 self.visit(node.code, scope) 236 self.handle_free_vars(scope, parent) 237 238 def visitGenExpr(self, node, parent): 239 scope = GenExprScope(self.module, self.klass); 240 if parent.nested or isinstance(parent, FunctionScope) \ 241 or isinstance(parent, GenExprScope): 242 scope.nested = 1 243 244 self.scopes[node] = scope 245 self.visit(node.code, scope) 246 247 self.handle_free_vars(scope, parent) 248 249 def visitGenExprInner(self, node, scope): 250 for genfor in node.quals: 251 self.visit(genfor, scope) 252 253 self.visit(node.expr, scope) 254 255 def visitGenExprFor(self, node, scope): 256 self.visit(node.assign, scope, 1) 257 self.visit(node.iter, scope) 258 for if_ in node.ifs: 259 self.visit(if_, scope) 260 261 def visitGenExprIf(self, node, scope): 262 self.visit(node.test, scope) 263 264 def visitLambda(self, node, parent, assign=0): 265 # Lambda is an expression, so it could appear in an expression 266 # context where assign is passed. The transformer should catch 267 # any code that has a lambda on the left-hand side. 268 assert not assign 269 270 for n in node.defaults: 271 self.visit(n, parent) 272 scope = LambdaScope(self.module, self.klass) 273 if parent.nested or isinstance(parent, FunctionScope): 274 scope.nested = 1 275 self.scopes[node] = scope 276 self._do_args(scope, node.argnames) 277 self.visit(node.code, scope) 278 self.handle_free_vars(scope, parent) 279 280 def _do_args(self, scope, args): 281 for name in args: 282 if type(name) == types.TupleType: 283 self._do_args(scope, name) 284 else: 285 scope.add_param(name) 286 287 def handle_free_vars(self, scope, parent): 288 parent.add_child(scope) 289 scope.handle_children() 290 291 def visitClass(self, node, parent): 292 parent.add_def(node.name) 293 for n in node.bases: 294 self.visit(n, parent) 295 scope = ClassScope(node.name, self.module) 296 if parent.nested or isinstance(parent, FunctionScope): 297 scope.nested = 1 298 if node.doc is not None: 299 scope.add_def('__doc__') 300 scope.add_def('__module__') 301 self.scopes[node] = scope 302 prev = self.klass 303 self.klass = node.name 304 self.visit(node.code, scope) 305 self.klass = prev 306 self.handle_free_vars(scope, parent) 307 308 # name can be a def or a use 309 310 # XXX a few calls and nodes expect a third "assign" arg that is 311 # true if the name is being used as an assignment. only 312 # expressions contained within statements may have the assign arg. 313 314 def visitName(self, node, scope, assign=0): 315 if assign: 316 scope.add_def(node.name) 317 else: 318 scope.add_use(node.name) 319 320 # operations that bind new names 321 322 def visitFor(self, node, scope): 323 self.visit(node.assign, scope, 1) 324 self.visit(node.list, scope) 325 self.visit(node.body, scope) 326 if node.else_: 327 self.visit(node.else_, scope) 328 329 def visitFrom(self, node, scope): 330 for name, asname in node.names: 331 if name == "*": 332 continue 333 scope.add_def(asname or name) 334 335 def visitImport(self, node, scope): 336 for name, asname in node.names: 337 i = name.find(".") 338 if i > -1: 339 name = name[:i] 340 scope.add_def(asname or name) 341 342 def visitGlobal(self, node, scope): 343 for name in node.names: 344 scope.add_global(name) 345 346 def visitAssign(self, node, scope): 347 """Propagate assignment flag down to child nodes. 348 349 The Assign node doesn't itself contains the variables being 350 assigned to. Instead, the children in node.nodes are visited 351 with the assign flag set to true. When the names occur in 352 those nodes, they are marked as defs. 353 354 Some names that occur in an assignment target are not bound by 355 the assignment, e.g. a name occurring inside a slice. The 356 visitor handles these nodes specially; they do not propagate 357 the assign flag to their children. 358 """ 359 for n in node.nodes: 360 self.visit(n, scope, 1) 361 self.visit(node.expr, scope) 362 363 def visitAssName(self, node, scope, assign=1): 364 scope.add_def(node.name) 365 366 def visitAssAttr(self, node, scope, assign=0): 367 self.visit(node.expr, scope, 0) 368 369 def visitSubscript(self, node, scope, assign=0): 370 self.visit(node.expr, scope, 0) 371 for n in node.subs: 372 self.visit(n, scope, 0) 373 374 def visitSlice(self, node, scope, assign=0): 375 self.visit(node.expr, scope, 0) 376 if node.lower: 377 self.visit(node.lower, scope, 0) 378 if node.upper: 379 self.visit(node.upper, scope, 0) 380 381 def visitAugAssign(self, node, scope): 382 # If the LHS is a name, then this counts as assignment. 383 # Otherwise, it's just use. 384 self.visit(node.node, scope) 385 if isinstance(node.node, ast.Name): 386 self.visit(node.node, scope, 1) # XXX worry about this 387 self.visit(node.expr, scope) 388 389 # prune if statements if tests are false 390 391 _const_types = types.StringType, types.IntType, types.FloatType 392 393 def visitIf(self, node, scope): 394 for test, body in node.tests: 395 if isinstance(test, ast.Const): 396 if type(test.value) in self._const_types: 397 if not test.value: 398 continue 399 self.visit(test, scope) 400 self.visit(body, scope) 401 if node.else_: 402 self.visit(node.else_, scope) 403 404 # a yield statement signals a generator 405 406 def visitYield(self, node, scope): 407 scope.generator = 1 408 self.visit(node.value, scope) 409 410 def list_eq(l1, l2): 411 return sorted(l1) == sorted(l2) 412 413 if __name__ == "__main__": 414 import sys 415 from compiler import parseFile, walk 416 import symtable 417 418 def get_names(syms): 419 return [s for s in [s.get_name() for s in syms.get_symbols()] 420 if not (s.startswith('_[') or s.startswith('.'))] 421 422 for file in sys.argv[1:]: 423 print file 424 f = open(file) 425 buf = f.read() 426 f.close() 427 syms = symtable.symtable(buf, file, "exec") 428 mod_names = get_names(syms) 429 tree = parseFile(file) 430 s = SymbolVisitor() 431 walk(tree, s) 432 433 # compare module-level symbols 434 names2 = s.scopes[tree].get_names() 435 436 if not list_eq(mod_names, names2): 437 print 438 print "oops", file 439 print sorted(mod_names) 440 print sorted(names2) 441 sys.exit(-1) 442 443 d = {} 444 d.update(s.scopes) 445 del d[tree] 446 scopes = d.values() 447 del d 448 449 for s in syms.get_symbols(): 450 if s.is_namespace(): 451 l = [sc for sc in scopes 452 if sc.name == s.get_name()] 453 if len(l) > 1: 454 print "skipping", s.get_name() 455 else: 456 if not list_eq(get_names(s.get_namespace()), 457 l[0].get_names()): 458 print s.get_name() 459 print sorted(get_names(s.get_namespace())) 460 print sorted(l[0].get_names()) 461 sys.exit(-1)