[Zope-Checkins] CVS: Zope/lib/python/RestrictedPython/compiler_2_1 - __init__.py:1.2.2.1 ast.py:1.2.2.1 ast.txt:1.2.2.1 astgen.py:1.2.2.1 consts.py:1.2.2.1 future.py:1.2.2.1 misc.py:1.2.2.1 pyassem.py:1.2.2.1 pycodegen.py:1.2.2.1 symbols.py:1.2.2.1 transformer.py:1.2.2.1 visitor.py:1.2.2.1

[Shane Hathaway]

Update of /cvs-repository/Zope/lib/python/RestrictedPython/compiler_2_1
In directory cvs.zope.org:/tmp/cvs-serv26004/compiler_2_1

Added Files:
      Tag: Zope-2_5-branch
	__init__.py ast.py ast.txt astgen.py consts.py future.py 
	misc.py pyassem.py pycodegen.py symbols.py transformer.py 
	visitor.py 
Log Message:
Merged RestrictedPython-2_2-branch.


=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/__init__.py ===
"""Package for parsing and compiling Python source code

There are several functions defined at the top level that are imported
from modules contained in the package.

parse(buf) -> AST
    Converts a string containing Python source code to an abstract
    syntax tree (AST).  The AST is defined in compiler.ast.

parseFile(path) -> AST
    The same as parse(open(path))

walk(ast, visitor, verbose=None)
    Does a pre-order walk over the ast using the visitor instance.
    See compiler.visitor for details.

compile(filename)
    Generates a .pyc file by compilining filename.
"""

from transformer import parse, parseFile
from visitor import walk
from pycodegen import compile



=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/ast.py === (587/687 lines abridged)
"""Python abstract syntax node definitions

This file is automatically generated.
"""
from types import TupleType, ListType
from consts import CO_VARARGS, CO_VARKEYWORDS

def flatten(list):
    l = []
    for elt in list:
        t = type(elt)
        if t is TupleType or t is ListType:
            for elt2 in flatten(elt):
                l.append(elt2)
        else:
            l.append(elt)
    return l

def asList(nodes):
    l = []
    for item in nodes:
        if hasattr(item, "asList"):
            l.append(item.asList())
        else:
            t = type(item)
            if t is TupleType or t is ListType:
                l.append(tuple(asList(item)))
            else:
                l.append(item)
    return l

nodes = {}

class Node:
    lineno = None
    def getType(self):
        pass
    def getChildren(self):
        # XXX It would be better to generate flat values to begin with
        return flatten(self._getChildren())
    def asList(self):
        return tuple(asList(self.getChildren()))

class EmptyNode(Node):
    def __init__(self):
        self.lineno = None

class If(Node):
    nodes["if"] = "If"
    def __init__(self, tests, else_):

[-=- -=- -=- 587 lines omitted -=- -=- -=-]

        return "AssTuple(%s)" % (repr(self.nodes),)

class For(Node):
    nodes["for"] = "For"
    def __init__(self, assign, list, body, else_):
        self.assign = assign
        self.list = list
        self.body = body
        self.else_ = else_
    def _getChildren(self):
        return self.assign, self.list, self.body, self.else_
    def __repr__(self):
        return "For(%s, %s, %s, %s)" % (repr(self.assign), repr(self.list), repr(self.body), repr(self.else_))

class Raise(Node):
    nodes["raise"] = "Raise"
    def __init__(self, expr1, expr2, expr3):
        self.expr1 = expr1
        self.expr2 = expr2
        self.expr3 = expr3
    def _getChildren(self):
        return self.expr1, self.expr2, self.expr3
    def __repr__(self):
        return "Raise(%s, %s, %s)" % (repr(self.expr1), repr(self.expr2), repr(self.expr3))

class From(Node):
    nodes["from"] = "From"
    def __init__(self, modname, names):
        self.modname = modname
        self.names = names
    def _getChildren(self):
        return self.modname, self.names
    def __repr__(self):
        return "From(%s, %s)" % (repr(self.modname), repr(self.names))

class Slice(Node):
    nodes["slice"] = "Slice"
    def __init__(self, expr, flags, lower, upper):
        self.expr = expr
        self.flags = flags
        self.lower = lower
        self.upper = upper
    def _getChildren(self):
        return self.expr, self.flags, self.lower, self.upper
    def __repr__(self):
        return "Slice(%s, %s, %s, %s)" % (repr(self.expr), repr(self.flags), repr(self.lower), repr(self.upper))

klasses = globals()
for k in nodes.keys():
    nodes[k] = klasses[nodes[k]]


=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/ast.txt ===
Module: doc, node
Stmt: nodes
Function: name, argnames, defaults, flags, doc, code
Lambda: argnames, defaults, flags, code
Class: name, bases, doc, code
Pass: 
Break: 
Continue: 
For: assign, list, body, else_
While: test, body, else_
If: tests, else_
Exec: expr, locals, globals
From: modname, names
Import: names
Raise: expr1, expr2, expr3
TryFinally: body, final
TryExcept: body, handlers, else_
Return: value
Const: value
Print: nodes, dest
Printnl: nodes, dest
Discard: expr
AugAssign: node, op, expr
Assign: nodes, expr
AssTuple: nodes
AssList: nodes
AssName: name, flags
AssAttr: expr, attrname, flags
ListComp: expr, quals
ListCompFor: assign, list, ifs
ListCompIf: test
List: nodes
Dict: items
Not: expr
Compare: expr, ops
Name: name
Global: names
Backquote: expr
Getattr: expr, attrname
CallFunc: node, args, star_args = None, dstar_args = None
Keyword: name, expr
Subscript: expr, flags, subs
Ellipsis: 
Sliceobj: nodes
Slice: expr, flags, lower, upper
Assert: test, fail
Tuple: nodes
Or: nodes
And: nodes
Bitor: nodes
Bitxor: nodes
Bitand: nodes
LeftShift: (left, right)
RightShift: (left, right)
Add: (left, right)
Sub: (left, right)
Mul: (left, right)
Div: (left, right)
Mod: (left, right)
Power: (left, right)
UnaryAdd: expr
UnarySub: expr
Invert: expr

init(Function):
    self.varargs = self.kwargs = None
    if flags & CO_VARARGS:
        self.varargs = 1
    if flags & CO_VARKEYWORDS:
        self.kwargs = 1

init(Lambda):
    self.varargs = self.kwargs = None
    if flags & CO_VARARGS:
        self.varargs = 1
    if flags & CO_VARKEYWORDS:
        self.kwargs = 1


=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/astgen.py ===
"""Generate ast module from specification"""

import fileinput
import getopt
import re
import sys
from StringIO import StringIO

SPEC = "ast.txt"
COMMA = ", "

def load_boilerplate(file):
    f = open(file)
    buf = f.read()
    f.close()
    i = buf.find('### ''PROLOGUE')
    j = buf.find('### ''EPILOGUE')
    pro = buf[i+12:j].strip()
    epi = buf[j+12:].strip()
    return pro, epi

def strip_default(arg):
    """Return the argname from an 'arg = default' string"""
    i = arg.find('=')
    if i == -1:
        return arg
    return arg[:i].strip()

class NodeInfo:
    """Each instance describes a specific AST node"""
    def __init__(self, name, args):
        self.name = name
        self.args = args.strip()
        self.argnames = self.get_argnames()
        self.nargs = len(self.argnames)
        self.children = COMMA.join(["self.%s" % c
                                    for c in self.argnames])
        self.init = []

    def get_argnames(self):
        if '(' in self.args:
            i = self.args.find('(')
            j = self.args.rfind(')')
            args = self.args[i+1:j]
        else:
            args = self.args
        return [strip_default(arg.strip())
                for arg in args.split(',') if arg]

    def gen_source(self):
        buf = StringIO()
        print >> buf, "class %s(Node):" % self.name
        print >> buf, '    nodes["%s"] = "%s"' % (self.name.lower(), self.name)
        self._gen_init(buf)
        self._gen_getChildren(buf)
        self._gen_repr(buf)
        buf.seek(0, 0)
        return buf.read()

    def _gen_init(self, buf):
        print >> buf, "    def __init__(self, %s):" % self.args
        if self.argnames:
            for name in self.argnames:
                print >> buf, "        self.%s = %s" % (name, name)
        else:
            print >> buf, "        pass"
        if self.init:
            print >> buf, "".join(["    " + line for line in self.init])

    def _gen_getChildren(self, buf):
        print >> buf, "    def _getChildren(self):"
        if self.argnames:
            if self.nargs == 1:
                print >> buf, "        return %s," % self.children
            else:
                print >> buf, "        return %s" % self.children
        else:
            print >> buf, "        return ()"

    def _gen_repr(self, buf):
        print >> buf, "    def __repr__(self):"
        if self.argnames:
            fmt = COMMA.join(["%s"] * self.nargs)
            vals = ["repr(self.%s)" % name for name in self.argnames]
            vals = COMMA.join(vals)
            if self.nargs == 1:
                vals = vals + ","
            print >> buf, '        return "%s(%s)" %% (%s)' % \
                  (self.name, fmt, vals)
        else:
            print >> buf, '        return "%s()"' % self.name

rx_init = re.compile('init\((.*)\):')

def parse_spec(file):
    classes = {}
    cur = None
    for line in fileinput.input(file):
        mo = rx_init.search(line)
        if mo is None:
            if cur is None:
                # a normal entry
                try:
                    name, args = line.split(':')
                except ValueError:
                    continue
                classes[name] = NodeInfo(name, args)
                cur = None
            else:
                # some code for the __init__ method
                cur.init.append(line)
        else:
            # some extra code for a Node's __init__ method
            name = mo.group(1)
            cur = classes[name]
    return classes.values()

def main():
    prologue, epilogue = load_boilerplate(sys.argv[-1])
    print prologue
    print
    classes = parse_spec(SPEC)
    for info in classes:
        print info.gen_source()
    print epilogue

if __name__ == "__main__":
    main()
    sys.exit(0)

### PROLOGUE
"""Python abstract syntax node definitions

This file is automatically generated.
"""
from types import TupleType, ListType
from consts import CO_VARARGS, CO_VARKEYWORDS

def flatten(list):
    l = []
    for elt in list:
        t = type(elt)
        if t is TupleType or t is ListType:
            for elt2 in flatten(elt):
                l.append(elt2)
        else:
            l.append(elt)
    return l

def asList(nodes):
    l = []
    for item in nodes:
        if hasattr(item, "asList"):
            l.append(item.asList())
        else:
            t = type(item)
            if t is TupleType or t is ListType:
                l.append(tuple(asList(item)))
            else:
                l.append(item)
    return l

nodes = {}

class Node:
    lineno = None
    def getType(self):
        pass
    def getChildren(self):
        # XXX It would be better to generate flat values to begin with
        return flatten(self._getChildren())
    def asList(self):
        return tuple(asList(self.getChildren()))

class EmptyNode(Node):
    def __init__(self):
        self.lineno = None

### EPILOGUE
klasses = globals()
for k in nodes.keys():
    nodes[k] = klasses[nodes[k]]


=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/consts.py ===
# operation flags
OP_ASSIGN = 'OP_ASSIGN'
OP_DELETE = 'OP_DELETE'
OP_APPLY = 'OP_APPLY'

SC_LOCAL = 1
SC_GLOBAL = 2
SC_FREE = 3
SC_CELL = 4
SC_UNKNOWN = 5

CO_OPTIMIZED = 0x0001
CO_NEWLOCALS = 0x0002
CO_VARARGS = 0x0004
CO_VARKEYWORDS = 0x0008
CO_NESTED = 0x0010


=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/future.py ===
"""Parser for future statements

"""

import ast
from visitor import walk

def is_future(stmt):
    """Return true if statement is a well-formed future statement"""
    if not isinstance(stmt, ast.From):
        return 0
    if stmt.modname == "__future__":
        return 1
    else:
        return 0

class FutureParser:

    features = ("nested_scopes",)
    
    def __init__(self):
        self.found = {} # set

    def visitModule(self, node):
        if node.doc is None:
            off = 0
        else:
            off = 1

        stmt = node.node
        for s in stmt.nodes[off:]:
            if not self.check_stmt(s):
                break

    def check_stmt(self, stmt):
        if is_future(stmt):
            for name, asname in stmt.names:
                if name in self.features:
                    self.found[name] = 1
                else:
                    raise SyntaxError, \
                          "future feature %s is not defined" % name
            stmt.valid_future = 1
            return 1
        return 0

    def get_features(self):
        """Return list of features enabled by future statements"""
        return self.found.keys()

class BadFutureParser:
    """Check for invalid future statements"""

    def visitFrom(self, node):
        if hasattr(node, 'valid_future'):
            return
        if node.modname != "__future__":
            return
        raise SyntaxError, "invalid future statement"

def find_futures(node):
    p1 = FutureParser()
    p2 = BadFutureParser()
    walk(node, p1)
    walk(node, p2)
    return p1.get_features()

if __name__ == "__main__":
    import sys
    from transformer import parseFile

    for file in sys.argv[1:]:
        print file
        tree = parseFile(file)
        v = FutureParser()
        walk(tree, v)
        print v.found
        print



=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/misc.py ===
import types

def flatten(tup):
    elts = []
    for elt in tup:
        if type(elt) == types.TupleType:
            elts = elts + flatten(elt)
        else:
            elts.append(elt)
    return elts

class Set:
    def __init__(self):
        self.elts = {}
    def __len__(self):
        return len(self.elts)
    def __contains__(self, elt):
        return self.elts.has_key(elt)
    def add(self, elt):
        self.elts[elt] = elt
    def elements(self):
        return self.elts.keys()
    def has_elt(self, elt):
        return self.elts.has_key(elt)
    def remove(self, elt):
        del self.elts[elt]
    def copy(self):
        c = Set()
        c.elts.update(self.elts)
        return c

class Stack:
    def __init__(self):
        self.stack = []
        self.pop = self.stack.pop
    def __len__(self):
        return len(self.stack)
    def push(self, elt):
        self.stack.append(elt)
    def top(self):
        return self.stack[-1]
    def __getitem__(self, index): # needed by visitContinue()
        return self.stack[index]

MANGLE_LEN = 256 # magic constant from compile.c

def mangle(name, klass):
    if not name.startswith('__'):
        return name
    if len(name) + 2 >= MANGLE_LEN:
        return name
    if name.endswith('__'):
        return name
    try:
        i = 0
        while klass[i] == '_':
            i = i + 1
    except IndexError:
        return name
    klass = klass[i:]

    tlen = len(klass) + len(name)
    if tlen > MANGLE_LEN:
        klass = klass[:MANGLE_LEN-tlen]

    return "_%s%s" % (klass, name)



=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/pyassem.py === (727/827 lines abridged)
"""A flow graph representation for Python bytecode"""

from __future__ import nested_scopes

import dis
import new
import string
import sys
import types

import misc
from consts import CO_OPTIMIZED, CO_NEWLOCALS, CO_VARARGS, CO_VARKEYWORDS

def xxx_sort(l):
    l = l[:]
    def sorter(a, b):
        return cmp(a.bid, b.bid)
    l.sort(sorter)
    return l

class FlowGraph:
    def __init__(self):
        self.current = self.entry = Block()
        self.exit = Block("exit")
        self.blocks = misc.Set()
        self.blocks.add(self.entry)
        self.blocks.add(self.exit)

    def startBlock(self, block):
        if self._debug:
            if self.current:
                print "end", repr(self.current)
                print "    next", self.current.next
                print "   ", self.current.get_children()
            print repr(block)
        self.current = block

    def nextBlock(self, block=None):
        # XXX think we need to specify when there is implicit transfer
        # from one block to the next.  might be better to represent this
        # with explicit JUMP_ABSOLUTE instructions that are optimized
        # out when they are unnecessary.
        #
        # I think this strategy works: each block has a child
        # designated as "next" which is returned as the last of the
        # children.  because the nodes in a graph are emitted in
        # reverse post order, the "next" block will always be emitted
        # immediately after its parent.
        # Worry: maintaining this invariant could be tricky
        if block is None:

[-=- -=- -=- 727 lines omitted -=- -=- -=-]

        'STORE_ATTR': -2,
        'DELETE_ATTR': -1,
        'STORE_GLOBAL': -1,
        'BUILD_MAP': 1,
        'COMPARE_OP': -1,
        'STORE_FAST': -1,
        'IMPORT_STAR': -1,
        'IMPORT_NAME': 0,
        'IMPORT_FROM': 1,
        'LOAD_ATTR': 0, # unlike other loads
        # close enough...
        'SETUP_EXCEPT': 3,
        'SETUP_FINALLY': 3,
        'FOR_LOOP': 1,
        }
    # use pattern match
    patterns = [
        ('BINARY_', -1),
        ('LOAD_', 1),
        ]

    def UNPACK_SEQUENCE(self, count):
        return count-1
    def BUILD_TUPLE(self, count):
        return -count+1
    def BUILD_LIST(self, count):
        return -count+1
    def CALL_FUNCTION(self, argc):
        hi, lo = divmod(argc, 256)
        return -(lo + hi * 2)
    def CALL_FUNCTION_VAR(self, argc):
        return self.CALL_FUNCTION(argc)-1
    def CALL_FUNCTION_KW(self, argc):
        return self.CALL_FUNCTION(argc)-1
    def CALL_FUNCTION_VAR_KW(self, argc):
        return self.CALL_FUNCTION(argc)-2
    def MAKE_FUNCTION(self, argc):
        return -argc
    def MAKE_CLOSURE(self, argc):
        # XXX need to account for free variables too!
        return -argc
    def BUILD_SLICE(self, argc):
        if argc == 2:
            return -1
        elif argc == 3:
            return -2
    def DUP_TOPX(self, argc):
        return argc

findDepth = StackDepthTracker().findDepth


=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/pycodegen.py === (1248/1348 lines abridged)
import imp
import os
import marshal
import stat
import string
import struct
import sys
import types
from cStringIO import StringIO

import ast
from transformer import parse
from visitor import walk
import pyassem, misc, future, symbols
from consts import SC_LOCAL, SC_GLOBAL, SC_FREE, SC_CELL
from consts import CO_VARARGS, CO_VARKEYWORDS, CO_NEWLOCALS, CO_NESTED
from pyassem import TupleArg

# Do we have Python 1.x or Python 2.x?
try:
    VERSION = sys.version_info[0]
except AttributeError:
    VERSION = 1

callfunc_opcode_info = {
    # (Have *args, Have **args) : opcode
    (0,0) : "CALL_FUNCTION",
    (1,0) : "CALL_FUNCTION_VAR",
    (0,1) : "CALL_FUNCTION_KW",
    (1,1) : "CALL_FUNCTION_VAR_KW",
}

LOOP = 1
EXCEPT = 2
TRY_FINALLY = 3
END_FINALLY = 4

def compile(filename, display=0):
    f = open(filename)
    buf = f.read()
    f.close()
    mod = Module(buf, filename)
    try:
        mod.compile(display)
    except SyntaxError:
        raise
    else:
        f = open(filename + "c", "wb")
        mod.dump(f)
        f.close()

[-=- -=- -=- 1248 lines omitted -=- -=- -=-]

        elif self.op != node.flags:
            raise ValueError, "mixed ops in stmt"
    visitAssAttr = visitAssName
    visitSubscript = visitAssName

class Delegator:
    """Base class to support delegation for augmented assignment nodes

    To generator code for augmented assignments, we use the following
    wrapper classes.  In visitAugAssign, the left-hand expression node
    is visited twice.  The first time the visit uses the normal method
    for that node .  The second time the visit uses a different method
    that generates the appropriate code to perform the assignment.
    These delegator classes wrap the original AST nodes in order to
    support the variant visit methods.
    """
    def __init__(self, obj):
        self.obj = obj

    def __getattr__(self, attr):
        return getattr(self.obj, attr)

class AugGetattr(Delegator):
    pass

class AugName(Delegator):
    pass

class AugSlice(Delegator):
    pass

class AugSubscript(Delegator):
    pass


wrapper = {
    ast.Getattr: AugGetattr,
    ast.Name: AugName,
    ast.Slice: AugSlice,
    ast.Subscript: AugSubscript,
    }

def wrap_aug(node):
    return wrapper[node.__class__](node)

if __name__ == "__main__":
    import sys

    for file in sys.argv[1:]:
        compile(file)


=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/symbols.py ===
"""Module symbol-table generator"""

import ast
from consts import SC_LOCAL, SC_GLOBAL, SC_FREE, SC_CELL, SC_UNKNOWN
from misc import mangle
import types

import sys

MANGLE_LEN = 256

class Scope:
    # XXX how much information do I need about each name?
    def __init__(self, name, module, klass=None):
        self.name = name
        self.module = module
        self.defs = {}
        self.uses = {}
        self.globals = {}
        self.params = {}
        self.frees = {}
        self.cells = {}
        self.children = []
        # nested is true if the class could contain free variables,
        # i.e. if it is nested within another function.
        self.nested = None
        self.klass = None
        if klass is not None:
            for i in range(len(klass)):
                if klass[i] != '_':
                    self.klass = klass[i:]
                    break

    def __repr__(self):
        return "<%s: %s>" % (self.__class__.__name__, self.name)

    def mangle(self, name):
        if self.klass is None:
            return name
        return mangle(name, self.klass)

    def add_def(self, name):
        self.defs[self.mangle(name)] = 1

    def add_use(self, name):
        self.uses[self.mangle(name)] = 1

    def add_global(self, name):
        name = self.mangle(name)
        if self.uses.has_key(name) or self.defs.has_key(name):
            pass # XXX warn about global following def/use
        if self.params.has_key(name):
            raise SyntaxError, "%s in %s is global and parameter" % \
                  (name, self.name)
        self.globals[name] = 1
        self.module.add_def(name)

    def add_param(self, name):
        name = self.mangle(name)
        self.defs[name] = 1
        self.params[name] = 1

    def get_names(self):
        d = {}
        d.update(self.defs)
        d.update(self.uses)
        d.update(self.globals)
        return d.keys()

    def add_child(self, child):
        self.children.append(child)

    def get_children(self):
        return self.children

    def DEBUG(self):
        return
        print >> sys.stderr, self.name, self.nested and "nested" or ""
        print >> sys.stderr, "\tglobals: ", self.globals
        print >> sys.stderr, "\tcells: ", self.cells
        print >> sys.stderr, "\tdefs: ", self.defs
        print >> sys.stderr, "\tuses: ", self.uses
        print >> sys.stderr, "\tfrees:", self.frees

    def check_name(self, name):
        """Return scope of name.

        The scope of a name could be LOCAL, GLOBAL, FREE, or CELL.
        """
        if self.globals.has_key(name):
            return SC_GLOBAL
        if self.cells.has_key(name):
            return SC_CELL
        if self.defs.has_key(name):
            return SC_LOCAL
        if self.nested and (self.frees.has_key(name) or
                            self.uses.has_key(name)):
            return SC_FREE
        if self.nested:
            return SC_UNKNOWN
        else:
            return SC_GLOBAL

    def get_free_vars(self):
        if not self.nested:
            return ()
        free = {}
        free.update(self.frees)
        for name in self.uses.keys():
            if not (self.defs.has_key(name) or
                    self.globals.has_key(name)):
                free[name] = 1
        return free.keys()

    def handle_children(self):
        for child in self.children:
            frees = child.get_free_vars()
            globals = self.add_frees(frees)
            for name in globals:
                child.force_global(name)

    def force_global(self, name):
        """Force name to be global in scope.

        Some child of the current node had a free reference to name.
        When the child was processed, it was labelled a free
        variable.  Now that all its enclosing scope have been
        processed, the name is known to be a global or builtin.  So
        walk back down the child chain and set the name to be global
        rather than free.

        Be careful to stop if a child does not think the name is
        free. 
        """
        self.globals[name] = 1
        if self.frees.has_key(name):
            del self.frees[name]
        for child in self.children:
            if child.check_name(name) == SC_FREE:
                child.force_global(name)

    def add_frees(self, names):
        """Process list of free vars from nested scope.

        Returns a list of names that are either 1) declared global in the
        parent or 2) undefined in a top-level parent.  In either case,
        the nested scope should treat them as globals.
        """
        child_globals = []
        for name in names:
            sc = self.check_name(name)
            if self.nested:
                if sc == SC_UNKNOWN or sc == SC_FREE \
                   or isinstance(self, ClassScope):
                    self.frees[name] = 1
                elif sc == SC_GLOBAL:
                    child_globals.append(name)
                elif isinstance(self, FunctionScope) and sc == SC_LOCAL:
                    self.cells[name] = 1
                elif sc != SC_CELL:
                    child_globals.append(name)
            else:
                if sc == SC_LOCAL:
                    self.cells[name] = 1
                elif sc != SC_CELL:
                    child_globals.append(name)
        return child_globals

    def get_cell_vars(self):
        return self.cells.keys()

class ModuleScope(Scope):
    __super_init = Scope.__init__
    
    def __init__(self):
        self.__super_init("global", self)

class FunctionScope(Scope):
    pass

class LambdaScope(FunctionScope):
    __super_init = Scope.__init__

    __counter = 1
    
    def __init__(self, module, klass=None):
        i = self.__counter
        self.__counter += 1
        self.__super_init("lambda.%d" % i, module, klass)

class ClassScope(Scope):
    __super_init = Scope.__init__

    def __init__(self, name, module):
        self.__super_init(name, module, name)

class SymbolVisitor:
    def __init__(self):
        self.scopes = {}
        self.klass = None
        
    # node that define new scopes

    def visitModule(self, node):
        scope = self.module = self.scopes[node] = ModuleScope()
        self.visit(node.node, scope)

    def visitFunction(self, node, parent):
        parent.add_def(node.name)
        for n in node.defaults:
            self.visit(n, parent)
        scope = FunctionScope(node.name, self.module, self.klass)
        if parent.nested or isinstance(parent, FunctionScope):
            scope.nested = 1
        self.scopes[node] = scope
        self._do_args(scope, node.argnames)
        self.visit(node.code, scope)
        self.handle_free_vars(scope, parent)
        scope.DEBUG()
        
    def visitLambda(self, node, parent):
        for n in node.defaults:
            self.visit(n, parent)
        scope = LambdaScope(self.module, self.klass)
        if parent.nested or isinstance(parent, FunctionScope):
            scope.nested = 1
        self.scopes[node] = scope
        self._do_args(scope, node.argnames)
        self.visit(node.code, scope)
        self.handle_free_vars(scope, parent)

    def _do_args(self, scope, args):
        for name in args:
            if type(name) == types.TupleType:
                self._do_args(scope, name)
            else:
                scope.add_param(name)

    def handle_free_vars(self, scope, parent):
        parent.add_child(scope)
        if scope.children:
            scope.DEBUG()
        scope.handle_children()

    def visitClass(self, node, parent):
        parent.add_def(node.name)
        for n in node.bases:
            self.visit(n, parent)
        scope = ClassScope(node.name, self.module)
        if parent.nested or isinstance(parent, FunctionScope):
            scope.nested = 1
        self.scopes[node] = scope
        prev = self.klass
        self.klass = node.name
        self.visit(node.code, scope)
        self.klass = prev
        self.handle_free_vars(scope, parent)

    # name can be a def or a use

    # XXX a few calls and nodes expect a third "assign" arg that is
    # true if the name is being used as an assignment.  only
    # expressions contained within statements may have the assign arg.

    def visitName(self, node, scope, assign=0):
        if assign:
            scope.add_def(node.name)
        else:
            scope.add_use(node.name)

    # operations that bind new names

    def visitFor(self, node, scope):
        self.visit(node.assign, scope, 1)
        self.visit(node.list, scope)
        self.visit(node.body, scope)
        if node.else_:
            self.visit(node.else_, scope)

    def visitFrom(self, node, scope):
        for name, asname in node.names:
            if name == "*":
                continue
            scope.add_def(asname or name)

    def visitImport(self, node, scope):
        for name, asname in node.names:
            i = name.find(".")
            if i > -1:
                name = name[:i]
            scope.add_def(asname or name)

    def visitGlobal(self, node, scope):
        for name in node.names:
            scope.add_global(name)

    def visitAssign(self, node, scope):
        """Propagate assignment flag down to child nodes.

        The Assign node doesn't itself contains the variables being
        assigned to.  Instead, the children in node.nodes are visited
        with the assign flag set to true.  When the names occur in
        those nodes, they are marked as defs.

        Some names that occur in an assignment target are not bound by
        the assignment, e.g. a name occurring inside a slice.  The
        visitor handles these nodes specially; they do not propagate
        the assign flag to their children.
        """
        for n in node.nodes:
            self.visit(n, scope, 1)
        self.visit(node.expr, scope)

    def visitAssName(self, node, scope, assign=1):
        scope.add_def(node.name)

    def visitAssAttr(self, node, scope, assign=0):
        self.visit(node.expr, scope, 0)

    def visitSubscript(self, node, scope, assign=0):
        self.visit(node.expr, scope, 0)
        for n in node.subs:
            self.visit(n, scope, 0)

    def visitSlice(self, node, scope, assign=0):
        self.visit(node.expr, scope, 0)
        if node.lower:
            self.visit(node.lower, scope, 0)
        if node.upper:
            self.visit(node.upper, scope, 0)

    def visitAugAssign(self, node, scope):
        # If the LHS is a name, then this counts as assignment.
        # Otherwise, it's just use.
        self.visit(node.node, scope)
        if isinstance(node.node, ast.Name):
            self.visit(node.node, scope, 1) # XXX worry about this
        self.visit(node.expr, scope)

    # prune if statements if tests are false

    _const_types = types.StringType, types.IntType, types.FloatType

    def visitIf(self, node, scope):
        for test, body in node.tests:
            if isinstance(test, ast.Const):
                if type(test.value) in self._const_types:
                    if not test.value:
                        continue
            self.visit(test, scope)
            self.visit(body, scope)
        if node.else_:
            self.visit(node.else_, scope)

def sort(l):
    l = l[:]
    l.sort()
    return l

def list_eq(l1, l2):
    return sort(l1) == sort(l2)

if __name__ == "__main__":
    import sys
    from transformer import parseFile
    from visitor import walk
    import symtable

    def get_names(syms):
        return [s for s in [s.get_name() for s in syms.get_symbols()]
                if not (s.startswith('_[') or s.startswith('.'))]        
    
    for file in sys.argv[1:]:
        print file
        f = open(file)
        buf = f.read()
        f.close()
        syms = symtable.symtable(buf, file, "exec")
        mod_names = get_names(syms)
        tree = parseFile(file)
        s = SymbolVisitor()
        walk(tree, s)

        # compare module-level symbols
        names2 = s.scopes[tree].get_names()

        if not list_eq(mod_names, names2):
            print
            print "oops", file
            print sort(mod_names)
            print sort(names2)
            sys.exit(-1)

        d = {}
        d.update(s.scopes)
        del d[tree]
        scopes = d.values()
        del d

        for s in syms.get_symbols():
            if s.is_namespace():
                l = [sc for sc in scopes
                     if sc.name == s.get_name()]
                if len(l) > 1:
                    print "skipping", s.get_name()
                else:
                    if not list_eq(get_names(s.get_namespace()),
                                   l[0].get_names()):
                        print s.get_name()
                        print sort(get_names(s.get_namespace()))
                        print sort(l[0].get_names())
                        sys.exit(-1)


=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/transformer.py === (1204/1304 lines abridged)
"""Parse tree transformation module.

Transforms Python source code into an abstract syntax tree (AST)
defined in the ast module.

The simplest ways to invoke this module are via parse and parseFile.
parse(buf) -> AST
parseFile(path) -> AST
"""

# Original version written by Greg Stein (gstein@lyra.org)
#                         and Bill Tutt (rassilon@lima.mudlib.org)
# February 1997.
#
# Modifications and improvements for Python 2.0 by Jeremy Hylton and
# Mark Hammond

# Portions of this file are:
# Copyright (C) 1997-1998 Greg Stein. All Rights Reserved.
#
# This module is provided under a BSD-ish license. See
#   http://www.opensource.org/licenses/bsd-license.html
# and replace OWNER, ORGANIZATION, and YEAR as appropriate.

from ast import *
import parser
# Care must be taken to use only symbols and tokens defined in Python
# 1.5.2 for code branches executed in 1.5.2
import symbol
import token
import string
import sys

error = 'walker.error'

from consts import CO_VARARGS, CO_VARKEYWORDS
from consts import OP_ASSIGN, OP_DELETE, OP_APPLY

def parseFile(path):
    f = open(path)
    src = f.read()
    f.close()
    return parse(src)

def parse(buf):
    return Transformer().parsesuite(buf)

def asList(nodes):
    l = []
    for item in nodes:

[-=- -=- -=- 1204 lines omitted -=- -=- -=-]

    symbol.try_stmt,
    symbol.suite,
    symbol.testlist,
    symbol.test,
    symbol.and_test,
    symbol.not_test,
    symbol.comparison,
    symbol.exprlist,
    symbol.expr,
    symbol.xor_expr,
    symbol.and_expr,
    symbol.shift_expr,
    symbol.arith_expr,
    symbol.term,
    symbol.factor,
    symbol.power,
    symbol.atom,
    ]

_assign_types = [
    symbol.test,
    symbol.and_test,
    symbol.not_test,
    symbol.comparison,
    symbol.expr,
    symbol.xor_expr,
    symbol.and_expr,
    symbol.shift_expr,
    symbol.arith_expr,
    symbol.term,
    symbol.factor,
    ]

import types
_names = {}
for k, v in symbol.sym_name.items():
    _names[k] = v
for k, v in token.tok_name.items():
    _names[k] = v

def debug_tree(tree):
    l = []
    for elt in tree:
        if type(elt) == types.IntType:
            l.append(_names.get(elt, elt))
        elif type(elt) == types.StringType:
            l.append(elt)
        else:
            l.append(debug_tree(elt))
    return l


=== Added File Zope/lib/python/RestrictedPython/compiler_2_1/visitor.py ===
import sys
import ast

class ASTVisitor:
    """Performs a depth-first walk of the AST

    The ASTVisitor will walk the AST, performing either a preorder or
    postorder traversal depending on which method is called.

    methods:
    preorder(tree, visitor)
    postorder(tree, visitor)
        tree: an instance of ast.Node
        visitor: an instance with visitXXX methods

    The ASTVisitor is responsible for walking over the tree in the
    correct order.  For each node, it checks the visitor argument for
    a method named 'visitNodeType' where NodeType is the name of the
    node's class, e.g. Class.  If the method exists, it is called
    with the node as its sole argument.

    The visitor method for a particular node type can control how
    child nodes are visited during a preorder walk.  (It can't control
    the order during a postorder walk, because it is called _after_
    the walk has occurred.)  The ASTVisitor modifies the visitor
    argument by adding a visit method to the visitor; this method can
    be used to visit a particular child node.  If the visitor method
    returns a true value, the ASTVisitor will not traverse the child
    nodes.

    XXX The interface for controlling the preorder walk needs to be
    re-considered.  The current interface is convenient for visitors
    that mostly let the ASTVisitor do everything.  For something like
    a code generator, where you want to walk to occur in a specific
    order, it's a pain to add "return 1" to the end of each method.
    """

    VERBOSE = 0

    def __init__(self):
        self.node = None
        self._cache = {}

    def default(self, node, *args):
        for child in node.getChildren():
            if isinstance(child, ast.Node):
                apply(self._preorder, (child,) + args)

    def dispatch(self, node, *args):
        self.node = node
        klass = node.__class__
        meth = self._cache.get(klass, None)
        if meth is None:
            className = klass.__name__
            meth = getattr(self.visitor, 'visit' + className, self.default)
            self._cache[klass] = meth
        if self.VERBOSE > 0:
            className = klass.__name__
            if self.VERBOSE == 1:
                if meth == 0:
                    print "dispatch", className
            else:
                print "dispatch", className, (meth and meth.__name__ or '')
        return meth(node, *args)

    def preorder(self, tree, visitor, *args):
        """Do preorder walk of tree using visitor"""
        self.visitor = visitor
        visitor.visit = self._preorder
        self._preorder(tree, *args) # XXX *args make sense?

    _preorder = dispatch

class ExampleASTVisitor(ASTVisitor):
    """Prints examples of the nodes that aren't visited

    This visitor-driver is only useful for development, when it's
    helpful to develop a visitor incremently, and get feedback on what
    you still have to do.
    """
    examples = {}
    
    def dispatch(self, node, *args):
        self.node = node
        meth = self._cache.get(node.__class__, None)
        className = node.__class__.__name__
        if meth is None:
            meth = getattr(self.visitor, 'visit' + className, 0)
            self._cache[node.__class__] = meth
        if self.VERBOSE > 1:
            print "dispatch", className, (meth and meth.__name__ or '')
        if meth:
            return apply(meth, (node,) + args)
        elif self.VERBOSE > 0:
            klass = node.__class__
            if not self.examples.has_key(klass):
                self.examples[klass] = klass
                print
                print self.visitor
                print klass
                for attr in dir(node):
                    if attr[0] != '_':
                        print "\t", "%-12.12s" % attr, getattr(node, attr)
                print
            return apply(self.default, (node,) + args)

_walker = ASTVisitor
def walk(tree, visitor, verbose=None):
    w = _walker()
    if verbose is not None:
        w.VERBOSE = verbose
    w.preorder(tree, visitor)
    return w.visitor

def dumpNode(node):
    print node.__class__
    for attr in dir(node):
        if attr[0] != '_':
            print "\t", "%-10.10s" % attr, getattr(node, attr)