0001 """Module symbol-table generator""" 0002 0003 from compiler import ast 0004 from compiler.consts import SC_LOCAL, SC_GLOBAL, SC_FREE, SC_CELL, SC_UNKNOWN 0005 from compiler.misc import mangle 0006 import types 0007 0008 0009 import sys 0010 0011 MANGLE_LEN = 256 0012 0013 class Scope: 0014 # XXX how much information do I need about each name? 0015 def __init__(self, name, module, klass=None): 0016 self.name = name 0017 self.module = module 0018 self.defs = {} 0019 self.uses = {} 0020 self.globals = {} 0021 self.params = {} 0022 self.frees = {} 0023 self.cells = {} 0024 self.children = [] 0025 # nested is true if the class could contain free variables, 0026 # i.e. if it is nested within another function. 0027 self.nested = None 0028 self.generator = None 0029 self.klass = None 0030 if klass is not None: 0031 for i in range(len(klass)): 0032 if klass[i] != '_': 0033 self.klass = klass[i:] 0034 break 0035 0036 def __repr__(self): 0037 return "<%s: %s>" % (self.__class__.__name__, self.name) 0038 0039 def mangle(self, name): 0040 if self.klass is None: 0041 return name 0042 return mangle(name, self.klass) 0043 0044 def add_def(self, name): 0045 self.defs[self.mangle(name)] = 1 0046 0047 def add_use(self, name): 0048 self.uses[self.mangle(name)] = 1 0049 0050 def add_global(self, name): 0051 name = self.mangle(name) 0052 if self.uses.has_key(name) or self.defs.has_key(name): 0053 pass # XXX warn about global following def/use 0054 if self.params.has_key(name): 0055 raise SyntaxError, "%s in %s is global and parameter" % \ 0056 (name, self.name) 0057 self.globals[name] = 1 0058 self.module.add_def(name) 0059 0060 def add_param(self, name): 0061 name = self.mangle(name) 0062 self.defs[name] = 1 0063 self.params[name] = 1 0064 0065 def get_names(self): 0066 d = {} 0067 d.update(self.defs) 0068 d.update(self.uses) 0069 d.update(self.globals) 0070 return d.keys() 0071 0072 def add_child(self, child): 0073 self.children.append(child) 0074 0075 def get_children(self): 0076 return self.children 0077 0078 def DEBUG(self): 0079 print >> sys.stderr, self.name, self.nested and "nested" or "" 0080 print >> sys.stderr, "\tglobals: ", self.globals 0081 print >> sys.stderr, "\tcells: ", self.cells 0082 print >> sys.stderr, "\tdefs: ", self.defs 0083 print >> sys.stderr, "\tuses: ", self.uses 0084 print >> sys.stderr, "\tfrees:", self.frees 0085 0086 def check_name(self, name): 0087 """Return scope of name. 0088 0089 The scope of a name could be LOCAL, GLOBAL, FREE, or CELL. 0090 """ 0091 if self.globals.has_key(name): 0092 return SC_GLOBAL 0093 if self.cells.has_key(name): 0094 return SC_CELL 0095 if self.defs.has_key(name): 0096 return SC_LOCAL 0097 if self.nested and (self.frees.has_key(name) or 0098 self.uses.has_key(name)): 0099 return SC_FREE 0100 if self.nested: 0101 return SC_UNKNOWN 0102 else: 0103 return SC_GLOBAL 0104 0105 def get_free_vars(self): 0106 if not self.nested: 0107 return () 0108 free = {} 0109 free.update(self.frees) 0110 for name in self.uses.keys(): 0111 if not (self.defs.has_key(name) or 0112 self.globals.has_key(name)): 0113 free[name] = 1 0114 return free.keys() 0115 0116 def handle_children(self): 0117 for child in self.children: 0118 frees = child.get_free_vars() 0119 globals = self.add_frees(frees) 0120 for name in globals: 0121 child.force_global(name) 0122 0123 def force_global(self, name): 0124 """Force name to be global in scope. 0125 0126 Some child of the current node had a free reference to name. 0127 When the child was processed, it was labelled a free 0128 variable. Now that all its enclosing scope have been 0129 processed, the name is known to be a global or builtin. So 0130 walk back down the child chain and set the name to be global 0131 rather than free. 0132 0133 Be careful to stop if a child does not think the name is 0134 free. 0135 """ 0136 self.globals[name] = 1 0137 if self.frees.has_key(name): 0138 del self.frees[name] 0139 for child in self.children: 0140 if child.check_name(name) == SC_FREE: 0141 child.force_global(name) 0142 0143 def add_frees(self, names): 0144 """Process list of free vars from nested scope. 0145 0146 Returns a list of names that are either 1) declared global in the 0147 parent or 2) undefined in a top-level parent. In either case, 0148 the nested scope should treat them as globals. 0149 """ 0150 child_globals = [] 0151 for name in names: 0152 sc = self.check_name(name) 0153 if self.nested: 0154 if sc == SC_UNKNOWN or sc == SC_FREE \ 0155 or isinstance(self, ClassScope): 0156 self.frees[name] = 1 0157 elif sc == SC_GLOBAL: 0158 child_globals.append(name) 0159 elif isinstance(self, FunctionScope) and sc == SC_LOCAL: 0160 self.cells[name] = 1 0161 elif sc != SC_CELL: 0162 child_globals.append(name) 0163 else: 0164 if sc == SC_LOCAL: 0165 self.cells[name] = 1 0166 elif sc != SC_CELL: 0167 child_globals.append(name) 0168 return child_globals 0169 0170 def get_cell_vars(self): 0171 return self.cells.keys() 0172 0173 class ModuleScope(Scope): 0174 __super_init = Scope.__init__ 0175 0176 def __init__(self): 0177 self.__super_init("global", self) 0178 0179 class FunctionScope(Scope): 0180 pass 0181 0182 class GenExprScope(Scope): 0183 __super_init = Scope.__init__ 0184 0185 __counter = 1 0186 0187 def __init__(self, module, klass=None): 0188 i = self.__counter 0189 self.__counter += 1 0190 self.__super_init("generator expression<%d>"%i, module, klass) 0191 self.add_param('[outmost-iterable]') 0192 0193 def get_names(self): 0194 keys = Scope.get_names() 0195 return keys 0196 0197 class LambdaScope(FunctionScope): 0198 __super_init = Scope.__init__ 0199 0200 __counter = 1 0201 0202 def __init__(self, module, klass=None): 0203 i = self.__counter 0204 self.__counter += 1 0205 self.__super_init("lambda.%d" % i, module, klass) 0206 0207 class ClassScope(Scope): 0208 __super_init = Scope.__init__ 0209 0210 def __init__(self, name, module): 0211 self.__super_init(name, module, name) 0212 0213 class SymbolVisitor: 0214 def __init__(self): 0215 self.scopes = {} 0216 self.klass = None 0217 0218 # node that define new scopes 0219 0220 def visitModule(self, node): 0221 scope = self.module = self.scopes[node] = ModuleScope() 0222 self.visit(node.node, scope) 0223 0224 visitExpression = visitModule 0225 0226 def visitFunction(self, node, parent): 0227 if node.decorators: 0228 self.visit(node.decorators, parent) 0229 parent.add_def(node.name) 0230 for n in node.defaults: 0231 self.visit(n, parent) 0232 scope = FunctionScope(node.name, self.module, self.klass) 0233 if parent.nested or isinstance(parent, FunctionScope): 0234 scope.nested = 1 0235 self.scopes[node] = scope 0236 self._do_args(scope, node.argnames) 0237 self.visit(node.code, scope) 0238 self.handle_free_vars(scope, parent) 0239 0240 def visitGenExpr(self, node, parent): 0241 scope = GenExprScope(self.module, self.klass); 0242 if parent.nested or isinstance(parent, FunctionScope) \ 0243 or isinstance(parent, GenExprScope): 0244 scope.nested = 1 0245 0246 self.scopes[node] = scope 0247 self.visit(node.code, scope) 0248 0249 self.handle_free_vars(scope, parent) 0250 0251 def visitGenExprInner(self, node, scope): 0252 for genfor in node.quals: 0253 self.visit(genfor, scope) 0254 0255 self.visit(node.expr, scope) 0256 0257 def visitGenExprFor(self, node, scope): 0258 self.visit(node.assign, scope, 1) 0259 self.visit(node.iter, scope) 0260 for if_ in node.ifs: 0261 self.visit(if_, scope) 0262 0263 def visitGenExprIf(self, node, scope): 0264 self.visit(node.test, scope) 0265 0266 def visitLambda(self, node, parent, assign=0): 0267 # Lambda is an expression, so it could appear in an expression 0268 # context where assign is passed. The transformer should catch 0269 # any code that has a lambda on the left-hand side. 0270 assert not assign 0271 0272 for n in node.defaults: 0273 self.visit(n, parent) 0274 scope = LambdaScope(self.module, self.klass) 0275 if parent.nested or isinstance(parent, FunctionScope): 0276 scope.nested = 1 0277 self.scopes[node] = scope 0278 self._do_args(scope, node.argnames) 0279 self.visit(node.code, scope) 0280 self.handle_free_vars(scope, parent) 0281 0282 def _do_args(self, scope, args): 0283 for name in args: 0284 if type(name) == types.TupleType: 0285 self._do_args(scope, name) 0286 else: 0287 scope.add_param(name) 0288 0289 def handle_free_vars(self, scope, parent): 0290 parent.add_child(scope) 0291 scope.handle_children() 0292 0293 def visitClass(self, node, parent): 0294 parent.add_def(node.name) 0295 for n in node.bases: 0296 self.visit(n, parent) 0297 scope = ClassScope(node.name, self.module) 0298 if parent.nested or isinstance(parent, FunctionScope): 0299 scope.nested = 1 0300 if node.doc is not None: 0301 scope.add_def('__doc__') 0302 scope.add_def('__module__') 0303 self.scopes[node] = scope 0304 prev = self.klass 0305 self.klass = node.name 0306 self.visit(node.code, scope) 0307 self.klass = prev 0308 self.handle_free_vars(scope, parent) 0309 0310 # name can be a def or a use 0311 0312 # XXX a few calls and nodes expect a third "assign" arg that is 0313 # true if the name is being used as an assignment. only 0314 # expressions contained within statements may have the assign arg. 0315 0316 def visitName(self, node, scope, assign=0): 0317 if assign: 0318 scope.add_def(node.name) 0319 else: 0320 scope.add_use(node.name) 0321 0322 # operations that bind new names 0323 0324 def visitFor(self, node, scope): 0325 self.visit(node.assign, scope, 1) 0326 self.visit(node.list, scope) 0327 self.visit(node.body, scope) 0328 if node.else_: 0329 self.visit(node.else_, scope) 0330 0331 def visitFrom(self, node, scope): 0332 for name, asname in node.names: 0333 if name == "*": 0334 continue 0335 scope.add_def(asname or name) 0336 0337 def visitImport(self, node, scope): 0338 for name, asname in node.names: 0339 i = name.find(".") 0340 if i > -1: 0341 name = name[:i] 0342 scope.add_def(asname or name) 0343 0344 def visitGlobal(self, node, scope): 0345 for name in node.names: 0346 scope.add_global(name) 0347 0348 def visitAssign(self, node, scope): 0349 """Propagate assignment flag down to child nodes. 0350 0351 The Assign node doesn't itself contains the variables being 0352 assigned to. Instead, the children in node.nodes are visited 0353 with the assign flag set to true. When the names occur in 0354 those nodes, they are marked as defs. 0355 0356 Some names that occur in an assignment target are not bound by 0357 the assignment, e.g. a name occurring inside a slice. The 0358 visitor handles these nodes specially; they do not propagate 0359 the assign flag to their children. 0360 """ 0361 for n in node.nodes: 0362 self.visit(n, scope, 1) 0363 self.visit(node.expr, scope) 0364 0365 def visitAssName(self, node, scope, assign=1): 0366 scope.add_def(node.name) 0367 0368 def visitAssAttr(self, node, scope, assign=0): 0369 self.visit(node.expr, scope, 0) 0370 0371 def visitSubscript(self, node, scope, assign=0): 0372 self.visit(node.expr, scope, 0) 0373 for n in node.subs: 0374 self.visit(n, scope, 0) 0375 0376 def visitSlice(self, node, scope, assign=0): 0377 self.visit(node.expr, scope, 0) 0378 if node.lower: 0379 self.visit(node.lower, scope, 0) 0380 if node.upper: 0381 self.visit(node.upper, scope, 0) 0382 0383 def visitAugAssign(self, node, scope): 0384 # If the LHS is a name, then this counts as assignment. 0385 # Otherwise, it's just use. 0386 self.visit(node.node, scope) 0387 if isinstance(node.node, ast.Name): 0388 self.visit(node.node, scope, 1) # XXX worry about this 0389 self.visit(node.expr, scope) 0390 0391 # prune if statements if tests are false 0392 0393 _const_types = types.StringType, types.IntType, types.FloatType 0394 0395 def visitIf(self, node, scope): 0396 for test, body in node.tests: 0397 if isinstance(test, ast.Const): 0398 if type(test.value) in self._const_types: 0399 if not test.value: 0400 continue 0401 self.visit(test, scope) 0402 self.visit(body, scope) 0403 if node.else_: 0404 self.visit(node.else_, scope) 0405 0406 # a yield statement signals a generator 0407 0408 def visitYield(self, node, scope): 0409 scope.generator = 1 0410 self.visit(node.value, scope) 0411 0412 def sort(l): 0413 l = l[:] 0414 l.sort() 0415 return l 0416 0417 def list_eq(l1, l2): 0418 return sort(l1) == sort(l2) 0419 0420 if __name__ == "__main__": 0421 import sys 0422 from compiler import parseFile, walk 0423 import symtable 0424 0425 def get_names(syms): 0426 return [s for s in [s.get_name() for s in syms.get_symbols()] 0427 if not (s.startswith('_[') or s.startswith('.'))] 0428 0429 for file in sys.argv[1:]: 0430 print file 0431 f = open(file) 0432 buf = f.read() 0433 f.close() 0434 syms = symtable.symtable(buf, file, "exec") 0435 mod_names = get_names(syms) 0436 tree = parseFile(file) 0437 s = SymbolVisitor() 0438 walk(tree, s) 0439 0440 # compare module-level symbols 0441 names2 = s.scopes[tree].get_names() 0442 0443 if not list_eq(mod_names, names2): 0444 print 0445 print "oops", file 0446 print sort(mod_names) 0447 print sort(names2) 0448 sys.exit(-1) 0449 0450 d = {} 0451 d.update(s.scopes) 0452 del d[tree] 0453 scopes = d.values() 0454 del d 0455 0456 for s in syms.get_symbols(): 0457 if s.is_namespace(): 0458 l = [sc for sc in scopes 0459 if sc.name == s.get_name()] 0460 if len(l) > 1: 0461 print "skipping", s.get_name() 0462 else: 0463 if not list_eq(get_names(s.get_namespace()), 0464 l[0].get_names()): 0465 print s.get_name() 0466 print sort(get_names(s.get_namespace())) 0467 print sort(l[0].get_names()) 0468 sys.exit(-1) 0469
Generated by PyXR 0.9.4