Lib/compiler/symbols.py

   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 self.uses.has_key(name) or self.defs.has_key(name):
  53             pass # XXX warn about global following def/use
  54         if self.params.has_key(name):
  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 self.globals.has_key(name):
  92             return SC_GLOBAL
  93         if self.cells.has_key(name):
  94             return SC_CELL
  95         if self.defs.has_key(name):
  96             return SC_LOCAL
  97         if self.nested and (self.frees.has_key(name) or
  98                             self.uses.has_key(name)):
  99             return SC_FREE
 100         if self.nested:
 101             return SC_UNKNOWN
 102         else:
 103             return SC_GLOBAL
 104
 105     def get_free_vars(self):
 106         if not self.nested:
 107             return ()
 108         free = {}
 109         free.update(self.frees)
 110         for name in self.uses.keys():
 111             if not (self.defs.has_key(name) or
 112                     self.globals.has_key(name)):
 113                 free[name] = 1
 114         return free.keys()
 115
 116     def handle_children(self):
 117         for child in self.children:
 118             frees = child.get_free_vars()
 119             globals = self.add_frees(frees)
 120             for name in globals:
 121                 child.force_global(name)
 122
 123     def force_global(self, name):
 124         """Force name to be global in scope.
 125
 126         Some child of the current node had a free reference to name.
 127         When the child was processed, it was labelled a free
 128         variable.  Now that all its enclosing scope have been
 129         processed, the name is known to be a global or builtin.  So
 130         walk back down the child chain and set the name to be global
 131         rather than free.
 132
 133         Be careful to stop if a child does not think the name is
 134         free.
 135         """
 136         self.globals[name] = 1
 137         if self.frees.has_key(name):
 138             del self.frees[name]
 139         for child in self.children:
 140             if child.check_name(name) == SC_FREE:
 141                 child.force_global(name)
 142
 143     def add_frees(self, names):
 144         """Process list of free vars from nested scope.
 145
 146         Returns a list of names that are either 1) declared global in the
 147         parent or 2) undefined in a top-level parent.  In either case,
 148         the nested scope should treat them as globals.
 149         """
 150         child_globals = []
 151         for name in names:
 152             sc = self.check_name(name)
 153             if self.nested:
 154                 if sc == SC_UNKNOWN or sc == SC_FREE \
 155                    or isinstance(self, ClassScope):
 156                     self.frees[name] = 1
 157                 elif sc == SC_GLOBAL:
 158                     child_globals.append(name)
 159                 elif isinstance(self, FunctionScope) and sc == SC_LOCAL:
 160                     self.cells[name] = 1
 161                 elif sc != SC_CELL:
 162                     child_globals.append(name)
 163             else:
 164                 if sc == SC_LOCAL:
 165                     self.cells[name] = 1
 166                 elif sc != SC_CELL:
 167                     child_globals.append(name)
 168         return child_globals
 169
 170     def get_cell_vars(self):
 171         return self.cells.keys()
 172
 173 class ModuleScope(Scope):
 174     __super_init = Scope.__init__
 175
 176     def __init__(self):
 177         self.__super_init("global", self)
 178
 179 class FunctionScope(Scope):
 180     pass
 181
 182 class LambdaScope(FunctionScope):
 183     __super_init = Scope.__init__
 184
 185     __counter = 1
 186
 187     def __init__(self, module, klass=None):
 188         i = self.__counter
 189         self.__counter += 1
 190         self.__super_init("lambda.%d" % i, module, klass)
 191
 192 class ClassScope(Scope):
 193     __super_init = Scope.__init__
 194
 195     def __init__(self, name, module):
 196         self.__super_init(name, module, name)
 197
 198 class SymbolVisitor:
 199     def __init__(self):
 200         self.scopes = {}
 201         self.klass = None
 202
 203     # node that define new scopes
 204
 205     def visitModule(self, node):
 206         scope = self.module = self.scopes[node] = ModuleScope()
 207         self.visit(node.node, scope)
 208
 209     visitExpression = visitModule
 210
 211     def visitFunction(self, node, parent):
 212         parent.add_def(node.name)
 213         for n in node.defaults:
 214             self.visit(n, parent)
 215         scope = FunctionScope(node.name, self.module, self.klass)
 216         if parent.nested or isinstance(parent, FunctionScope):
 217             scope.nested = 1
 218         self.scopes[node] = scope
 219         self._do_args(scope, node.argnames)
 220         self.visit(node.code, scope)
 221         self.handle_free_vars(scope, parent)
 222
 223     def visitLambda(self, node, parent):
 224         for n in node.defaults:
 225             self.visit(n, parent)
 226         scope = LambdaScope(self.module, self.klass)
 227         if parent.nested or isinstance(parent, FunctionScope):
 228             scope.nested = 1
 229         self.scopes[node] = scope
 230         self._do_args(scope, node.argnames)
 231         self.visit(node.code, scope)
 232         self.handle_free_vars(scope, parent)
 233
 234     def _do_args(self, scope, args):
 235         for name in args:
 236             if type(name) == types.TupleType:
 237                 self._do_args(scope, name)
 238             else:
 239                 scope.add_param(name)
 240
 241     def handle_free_vars(self, scope, parent):
 242         parent.add_child(scope)
 243         scope.handle_children()
 244
 245     def visitClass(self, node, parent):
 246         parent.add_def(node.name)
 247         for n in node.bases:
 248             self.visit(n, parent)
 249         scope = ClassScope(node.name, self.module)
 250         if parent.nested or isinstance(parent, FunctionScope):
 251             scope.nested = 1
 252         if node.doc is not None:
 253             scope.add_def('__doc__')
 254         self.scopes[node] = scope
 255         prev = self.klass
 256         self.klass = node.name
 257         self.visit(node.code, scope)
 258         self.klass = prev
 259         self.handle_free_vars(scope, parent)
 260
 261     # name can be a def or a use
 262
 263     # XXX a few calls and nodes expect a third "assign" arg that is
 264     # true if the name is being used as an assignment.  only
 265     # expressions contained within statements may have the assign arg.
 266
 267     def visitName(self, node, scope, assign=0):
 268         if assign:
 269             scope.add_def(node.name)
 270         else:
 271             scope.add_use(node.name)
 272
 273     # operations that bind new names
 274
 275     def visitFor(self, node, scope):
 276         self.visit(node.assign, scope, 1)
 277         self.visit(node.list, scope)
 278         self.visit(node.body, scope)
 279         if node.else_:
 280             self.visit(node.else_, scope)
 281
 282     def visitFrom(self, node, scope):
 283         for name, asname in node.names:
 284             if name == "*":
 285                 continue
 286             scope.add_def(asname or name)
 287
 288     def visitImport(self, node, scope):
 289         for name, asname in node.names:
 290             i = name.find(".")
 291             if i > -1:
 292                 name = name[:i]
 293             scope.add_def(asname or name)
 294
 295     def visitGlobal(self, node, scope):
 296         for name in node.names:
 297             scope.add_global(name)
 298
 299     def visitAssign(self, node, scope):
 300         """Propagate assignment flag down to child nodes.
 301
 302         The Assign node doesn't itself contains the variables being
 303         assigned to.  Instead, the children in node.nodes are visited
 304         with the assign flag set to true.  When the names occur in
 305         those nodes, they are marked as defs.
 306
 307         Some names that occur in an assignment target are not bound by
 308         the assignment, e.g. a name occurring inside a slice.  The
 309         visitor handles these nodes specially; they do not propagate
 310         the assign flag to their children.
 311         """
 312         for n in node.nodes:
 313             self.visit(n, scope, 1)
 314         self.visit(node.expr, scope)
 315
 316     def visitAssName(self, node, scope, assign=1):
 317         scope.add_def(node.name)
 318
 319     def visitAssAttr(self, node, scope, assign=0):
 320         self.visit(node.expr, scope, 0)
 321
 322     def visitSubscript(self, node, scope, assign=0):
 323         self.visit(node.expr, scope, 0)
 324         for n in node.subs:
 325             self.visit(n, scope, 0)
 326
 327     def visitSlice(self, node, scope, assign=0):
 328         self.visit(node.expr, scope, 0)
 329         if node.lower:
 330             self.visit(node.lower, scope, 0)
 331         if node.upper:
 332             self.visit(node.upper, scope, 0)
 333
 334     def visitAugAssign(self, node, scope):
 335         # If the LHS is a name, then this counts as assignment.
 336         # Otherwise, it's just use.
 337         self.visit(node.node, scope)
 338         if isinstance(node.node, ast.Name):
 339             self.visit(node.node, scope, 1) # XXX worry about this
 340         self.visit(node.expr, scope)
 341
 342     # prune if statements if tests are false
 343
 344     _const_types = types.StringType, types.IntType, types.FloatType
 345
 346     def visitIf(self, node, scope):
 347         for test, body in node.tests:
 348             if isinstance(test, ast.Const):
 349                 if type(test.value) in self._const_types:
 350                     if not test.value:
 351                         continue
 352             self.visit(test, scope)
 353             self.visit(body, scope)
 354         if node.else_:
 355             self.visit(node.else_, scope)
 356
 357     # a yield statement signals a generator
 358
 359     def visitYield(self, node, scope):
 360         scope.generator = 1
 361         self.visit(node.value, scope)
 362
 363 def sort(l):
 364     l = l[:]
 365     l.sort()
 366     return l
 367
 368 def list_eq(l1, l2):
 369     return sort(l1) == sort(l2)
 370
 371 if __name__ == "__main__":
 372     import sys
 373     from compiler import parseFile, walk
 374     import symtable
 375
 376     def get_names(syms):
 377         return [s for s in [s.get_name() for s in syms.get_symbols()]
 378                 if not (s.startswith('_[') or s.startswith('.'))]
 379
 380     for file in sys.argv[1:]:
 381         print file
 382         f = open(file)
 383         buf = f.read()
 384         f.close()
 385         syms = symtable.symtable(buf, file, "exec")
 386         mod_names = get_names(syms)
 387         tree = parseFile(file)
 388         s = SymbolVisitor()
 389         walk(tree, s)
 390
 391         # compare module-level symbols
 392         names2 = s.scopes[tree].get_names()
 393
 394         if not list_eq(mod_names, names2):
 395             print
 396             print "oops", file
 397             print sort(mod_names)
 398             print sort(names2)
 399             sys.exit(-1)
 400
 401         d = {}
 402         d.update(s.scopes)
 403         del d[tree]
 404         scopes = d.values()
 405         del d
 406
 407         for s in syms.get_symbols():
 408             if s.is_namespace():
 409                 l = [sc for sc in scopes
 410                      if sc.name == s.get_name()]
 411                 if len(l) > 1:
 412                     print "skipping", s.get_name()
 413                 else:
 414                     if not list_eq(get_names(s.get_namespace()),
 415                                    l[0].get_names()):
 416                         print s.get_name()
 417                         print sort(get_names(s.get_namespace()))
 418                         print sort(l[0].get_names())
 419                         sys.exit(-1)