home *** CD-ROM | disk | FTP | other *** search
/ Komputer for Alle 2004 #2 / K-CD-2-2004.ISO / OpenOffice Sv / f_0397 / python-core-2.2.2 / lib / compiler / symbols.py < prev    next >
Encoding:
Python Source  |  2003-07-18  |  12.8 KB  |  420 lines
  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)
  420.