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