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         self.scopes[node] = scope
 253         prev = self.klass
 254         self.klass = node.name
 255         self.visit(node.code, scope)
 256         self.klass = prev
 257         self.handle_free_vars(scope, parent)
 258
 259     # name can be a def or a use
 260
 261     # XXX a few calls and nodes expect a third "assign" arg that is
 262     # true if the name is being used as an assignment.  only
 263     # expressions contained within statements may have the assign arg.
 264
 265     def visitName(self, node, scope, assign=0):
 266         if assign:
 267             scope.add_def(node.name)
 268         else:
 269             scope.add_use(node.name)
 270
 271     # operations that bind new names
 272
 273     def visitFor(self, node, scope):
 274         self.visit(node.assign, scope, 1)
 275         self.visit(node.list, scope)
 276         self.visit(node.body, scope)
 277         if node.else_:
 278             self.visit(node.else_, scope)
 279
 280     def visitFrom(self, node, scope):
 281         for name, asname in node.names:
 282             if name == "*":
 283                 continue
 284             scope.add_def(asname or name)
 285
 286     def visitImport(self, node, scope):
 287         for name, asname in node.names:
 288             i = name.find(".")
 289             if i > -1:
 290                 name = name[:i]
 291             scope.add_def(asname or name)
 292
 293     def visitGlobal(self, node, scope):
 294         for name in node.names:
 295             scope.add_global(name)
 296
 297     def visitAssign(self, node, scope):
 298         """Propagate assignment flag down to child nodes.
 299
 300         The Assign node doesn't itself contains the variables being
 301         assigned to.  Instead, the children in node.nodes are visited
 302         with the assign flag set to true.  When the names occur in
 303         those nodes, they are marked as defs.
 304
 305         Some names that occur in an assignment target are not bound by
 306         the assignment, e.g. a name occurring inside a slice.  The
 307         visitor handles these nodes specially; they do not propagate
 308         the assign flag to their children.
 309         """
 310         for n in node.nodes:
 311             self.visit(n, scope, 1)
 312         self.visit(node.expr, scope)
 313
 314     def visitAssName(self, node, scope, assign=1):
 315         scope.add_def(node.name)
 316
 317     def visitAssAttr(self, node, scope, assign=0):
 318         self.visit(node.expr, scope, 0)
 319
 320     def visitSubscript(self, node, scope, assign=0):
 321         self.visit(node.expr, scope, 0)
 322         for n in node.subs:
 323             self.visit(n, scope, 0)
 324
 325     def visitSlice(self, node, scope, assign=0):
 326         self.visit(node.expr, scope, 0)
 327         if node.lower:
 328             self.visit(node.lower, scope, 0)
 329         if node.upper:
 330             self.visit(node.upper, scope, 0)
 331
 332     def visitAugAssign(self, node, scope):
 333         # If the LHS is a name, then this counts as assignment.
 334         # Otherwise, it's just use.
 335         self.visit(node.node, scope)
 336         if isinstance(node.node, ast.Name):
 337             self.visit(node.node, scope, 1) # XXX worry about this
 338         self.visit(node.expr, scope)
 339
 340     # prune if statements if tests are false
 341
 342     _const_types = types.StringType, types.IntType, types.FloatType
 343
 344     def visitIf(self, node, scope):
 345         for test, body in node.tests:
 346             if isinstance(test, ast.Const):
 347                 if type(test.value) in self._const_types:
 348                     if not test.value:
 349                         continue
 350             self.visit(test, scope)
 351             self.visit(body, scope)
 352         if node.else_:
 353             self.visit(node.else_, scope)
 354
 355     # a yield statement signals a generator
 356
 357     def visitYield(self, node, scope):
 358         scope.generator = 1
 359         self.visit(node.value, scope)
 360
 361 def sort(l):
 362     l = l[:]
 363     l.sort()
 364     return l
 365
 366 def list_eq(l1, l2):
 367     return sort(l1) == sort(l2)
 368
 369 if __name__ == "__main__":
 370     import sys
 371     from compiler import parseFile, walk
 372     import symtable
 373
 374     def get_names(syms):
 375         return [s for s in [s.get_name() for s in syms.get_symbols()]
 376                 if not (s.startswith('_[') or s.startswith('.'))]
 377
 378     for file in sys.argv[1:]:
 379         print file
 380         f = open(file)
 381         buf = f.read()
 382         f.close()
 383         syms = symtable.symtable(buf, file, "exec")
 384         mod_names = get_names(syms)
 385         tree = parseFile(file)
 386         s = SymbolVisitor()
 387         walk(tree, s)
 388
 389         # compare module-level symbols
 390         names2 = s.scopes[tree].get_names()
 391
 392         if not list_eq(mod_names, names2):
 393             print
 394             print "oops", file
 395             print sort(mod_names)
 396             print sort(names2)
 397             sys.exit(-1)
 398
 399         d = {}
 400         d.update(s.scopes)
 401         del d[tree]
 402         scopes = d.values()
 403         del d
 404
 405         for s in syms.get_symbols():
 406             if s.is_namespace():
 407                 l = [sc for sc in scopes
 408                      if sc.name == s.get_name()]
 409                 if len(l) > 1:
 410                     print "skipping", s.get_name()
 411                 else:
 412                     if not list_eq(get_names(s.get_namespace()),
 413                                    l[0].get_names()):
 414                         print s.get_name()
 415                         print sort(get_names(s.get_namespace()))
 416                         print sort(l[0].get_names())
 417                         sys.exit(-1)