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