Change 'values written by' to use the original Program's environment.

[l3full.git] / l3lang / ast.py

#
# Author:  Michael H. Hohn (mhhohn@lbl.gov)
#
# Copyright (c) 2006, The Regents of the University of California
# 
# See legal.txt and license.txt
# 

#*    imports
from __future__ import generators       # yield
import pdb, exceptions, sys, os, weakref
from types import *
from copy import deepcopy, copy
from pprint import pprint
import os, re

import l3lang.globals as glbl
from l3lang import utils


#

#*    utilities
exclude_names = {
    "_primary": 1,
    "_eval_env": 1,
    "_def_env": 1,
    "_storage": 1,
    "_primary_ids": 1,
    "_matcher": 1,
}


def dict2str(t):
    """ Produce the assignment sequence for a function call;
    omit exclude_names entries.
    """
    s = ""
    items = filter(lambda (k,v): not exclude_names.has_key(k),
                   t.items())
    if items != []:
        for k,v in items[:-1]:
            # k = v, ...
            s += str(k) + " = " + repr(v) + ', '
        k,v = items[-1]
        s += str(k) + " = " + repr(v)
    return s

def tuple2str(t):
    """Produce a tuple useable in a function call.
    The simple [1:-1] hack fails for (1,)
    """
    assert(type(t) == TupleType)
    if len(t) == 1:
        return repr(t)[1:-2]
    else:
        return repr(t)[1:-1]


def to_plain_python_f(itm, storage):
    item = storage.load( itm )
    try:
        return item.to_plain_python(storage)
    except AttributeError:
        return item


def row_adjust(tree):
    # Reduce the source text row index by one, for all nodes in the
    # tree.
    def _adjust(self):
        # Make rows start at 0
        if self._first_char != None:
            row, col = self._first_char
            self._first_char = (row-1, col)

        if self._last_char != None:
            row, col = self._last_char
            self._last_char = (row-1, col)

    for node in tree.top_down():
        _adjust(node)

    return tree

class InterfaceOnly(Exception):
    pass

def cross_reference_trees(storage, block, newblock):
    # cross-reference tree elements, one-to-one, for later
    # interaction.
    src = block.raw_seq_expr().top_down()
    dest = newblock.raw_seq_expr().top_down()
    try:
        while 1:
            storage.push_attributes(src.next()._id,
                                    "interp_clone", dest.next()._id)
    except StopIteration:
        pass

def cross_ref_trees(storage, block, newblock):
    # cross-reference tree elements, one-to-one, for later
    # interaction.
    src = block.top_down()
    dest = newblock.top_down()
    try:
        while 1:
            storage.push_attributes(src.next()._id,
                                    "interp_clone", dest.next()._id)
    except StopIteration:
        pass


def copy_char_info(source_tree, target_tree):
    # Assuming identical tree structure, overlay the source_tree's
    # source string info (the string and character positions) on the
    # target tree.
    source_string = source_tree._source_string
    src = source_tree.top_down()
    dest = target_tree.top_down()
    try:
        while 1:
            ss = src.next();    dd = dest.next()
            dd._source_string = source_string
            dd._first_char = ss._first_char
            dd._last_char = ss._last_char
    except StopIteration:
        pass

def copy_attribute(source_tree, target_tree, att):
    # Assuming identical tree structure, overlay the source_tree's
    # ATT attribute source on the target tree.
    src = source_tree.top_down()
    dest = target_tree.top_down()
    try:
        while 1:
            ss = src.next();    dd = dest.next()
            dd.__dict__[att] = ss.__dict__[att]
    except StopIteration:
        pass


def rowcol_to_index(rowcol, text):
    # Convert the (row, column) index used by _first_char and
    # _last_char into an index of the string.
    # This assumes Universal file reads; all EOLs are \n.
    row, col = rowcol
    start = 0
    for i in xrange(0, row):
        start = text.find('\n', start) + 1
    return start + col


#*    core types
#
#**        common base class
# class Value: ??
class astType:
    """
    Provide common functionality for Nested() and Immediate().

    Also provide dummy functions for the real interface provided
    by Nested and Immediate;  these functions raise exceptions if not
    overridden.

    raw_* members work on in-memory trees, before tree.setup() is run.

    """
    def __str__(self):
        raise InterfaceOnly

    def __repr__(self):
        raise InterfaceOnly

    def prefix_dump(self, indent=0):
        raise InterfaceOnly

    def traverse_depth(self):
        raise InterfaceOnly

    def traverse_breadth(self, head=1):
        raise InterfaceOnly

    def __len__(self):
        raise InterfaceOnly

    def __getitem__(self, index):
        raise InterfaceOnly

    def interpret(self, env, storage):
        raise InterfaceOnly

def __init__(self, *primary, **kwds):
    self._source_string = None
    self._source_file   = None
    self._pre_interp_hook = None    # callable of type
                                    # ((l3tree, env, storage) -> None)
    self._attributes = {}           # generic attributes, kept as
                                    # (key -> value) pairs.
astType.__init__ = __init__

def set_source_string(self, source_string):
    # Adjustment for block constructs at EOF
    lines = len(source_string.split('\n'))

    for node in self.top_down():
        node._source_string = source_string

        # Adjustment for block constructs at EOF
        if node._last_char != None:
            row2, col2 = node._last_char
            if row2 >= lines:
                node._last_char = (lines - 1, col2)

    return self
astType.set_source_string = set_source_string

def set_source_file(self, source_file):
    for node in self.top_down():
        node._source_file = source_file
    return self
astType.set_source_file = set_source_file


#
#**        Nested base class
class Nested(astType):
    """
    Collection of common functionality for all language elements.

    The _primary key is the constructor argument tuple, e.g.,
    for Sum(1,2), _primary is (1,2).

    Keyword arguments are merged with the instance __dict__.
    """
    pass

def __str__(self):
    return self.__repr__()
Nested.__str__ = __str__

def __len__(self):
    return len(self._primary)
Nested.__len__ = __len__

def repr_long(self):
    dict_str = dict2str(self.__dict__)
    if dict_str:
        dict_str = ', ' + dict_str
    return self.__class__.__name__ + '(' + \
           tuple2str(self._primary) + dict_str + ')'
Nested.repr_long = repr_long

def __repr__(self):
    return "%s(%s, %d)" % (self.__class__.__name__,
                           tuple2str(self._primary),
                           self._id)
def __repr__(self):
    return "%s(%s)" % (self.__class__.__name__, tuple2str(self._primary))
Nested.__repr__ = __repr__

def __getitem__(self, i):
    return (self._primary[i])
Nested.__getitem__ = __getitem__

def __getslice__(self, i):
    raise Exception("slicing is not defined for Nested.")
Nested.__getslice__ = __getslice__

def __init__(self, *primary, **kwds):
    self._primary       = primary
    self.__dict__.update(kwds)
    self._init_kwds     = kwds
    # (row, column), 0-relative
    self._first_char    = None
    self._last_char     = None          # column is one past last character.

    return astType.__init__(self, *primary, **kwds)
Nested.__init__ = __init__

def childrens_ids(self):
    return [ch._id for ch in self._primary]
Nested.childrens_ids = childrens_ids

def find_child_index(self, id):
    idx = 0
    for cc in self._primary:
        if cc._id == id:
            return idx
        idx +=1
    return None
Nested.find_child_index = find_child_index

def __deepcopy__(self, memo):
    # Also see aList.__deepcopy__
    # 
    # See copy_attribute() to restore missing attributes
    # 
    rv = self.__class__(*self._primary, **self._init_kwds)
    direct_ref = ['_arg_env',
                  '_block_env',
                  '_def_env',
                  '_matcher',
                  '_eval_env',
                  ## '_primary',  # the subtree had better be copied...
                  '_storage',
                  '_pre_interp_hook',
                  ]
    stuff = {}
    for k,v in self.__dict__.items():
        if k in direct_ref:
            stuff[k] = self.__dict__[k]
        else:
            stuff[k] = deepcopy(v)
    rv.__dict__.update(stuff)

    # Re-assign non-copyable members (e.g. from __init__) on a
    # per-class basis, or invalidate the member to insure explicit
    # errors. 

    # This is needed to maintain any graph structures in the original,
    # instead of getting a tree (pickle mostly avoids this problem,
    # but __deepcopy__ does not).

    # Members to look at come from __init__(), setup(), and
    # interpret(). 

    # Re-establish graph structures where possible...
    None

    # ... but ensure exceptions for others.
    try:    del rv._parent 
    except: pass

    try:    del rv._id
    except: pass
    
    ###try:    del rv._primary_ids
    ###except: pass

    return rv
Nested.__deepcopy__ = __deepcopy__

def deref(self, index):
    return (self._primary[index])
Nested.deref = deref


def eql(self, other):
    # Recursive content equality test -- not physical equality.

    # as in Matcher.match,
    # Trees are assumed to have interface functions
    # __len__, __getitem__, and __class__

    if self.__class__ == other.__class__: # identical head
        # Test children
        nc = self.__len__()
        if nc != other.__len__():
            return False
        # Compare ALL children.
        for c in range(0,nc):
            if self[c].eql(other[c]):
                continue
            else:
                return False
        return True
    else:
        return False
Nested.eql = eql


def eql_1(self, other):
    # Non-recursive value equality test -- not physical equality.

    # As in Matcher.match,
    # Trees are assumed to have interface functions
    # __len__, __getitem__, and __class__

    if self.__class__ == other.__class__: # identical head
        # Same size?
        nc = self.__len__()
        if nc != other.__len__():
            return False
        return True
    else:
        return False
Nested.eql_1 = eql_1


#
#**        Immediate base class
class Immediate(astType):
    """
    Common functionality for all Immediate types.
    Note: this class cannot be instantiated -- it must be subclassed.
    """

    def traverse_depth(self):
        yield self

    def traverse_breadth(self, head=0):
        yield self

    def __len__(self):
        return 0

    def __getitem__(self, i):
        raise IndexError

def __init__(self, *primary, **kwds):
    assert not isinstance(primary[0], astType) # No nesting here!
    self._first_char = None
    self._last_char = None
    self._primary = primary
    self._init_kwds = kwds
    self.__dict__.update(kwds)
    self.__class__.__bases__[1].__init__(self)
    return astType.__init__(self, *primary, **kwds)
Immediate.__init__ = __init__


def __deepcopy__(self, memo):
    # Also see aList.__deepcopy__, Nested.__deepcopy__
    rv = self.__class__(*self._primary, **self._init_kwds)
    direct_ref = ['_arg_env',
                  '_block_env',
                  '_def_env',
                  '_matcher',
                  '_eval_env',
                  '_storage',
                  '_pre_interp_hook',
                  ]
    stuff = {}
    for k,v in self.__dict__.items():
        if k in direct_ref:
            stuff[k] = self.__dict__[k]
        else:
            stuff[k] = deepcopy(v)
    rv.__dict__.update(stuff)

    # Re-establish graph structures where possible...
    None

    # ... but ensure exceptions for others.
    try:    del rv._parent 
    except: pass

    try:    del rv._id
    except: pass
    
    return rv
Immediate.__deepcopy__ = __deepcopy__


def childrens_ids(self):
    return []
Immediate.childrens_ids = childrens_ids

def __str__(self):
    return self.__repr__()
Immediate.__str__ = __str__

def eql(self, other):
    # May be expanded...
    if self.__class__ == other.__class__:
        return self._primary[0] == other._primary[0]
    else:
        return False
Immediate.eql = eql
Immediate.eql_1 = eql

def repr_long(self):
    dict_str = dict2str(self.__dict__)
    if dict_str:
        dict_str = ', ' + dict_str
    return self.__class__.__name__ + '(' + \
           self.__class__.__bases__[1].__repr__(self._primary[0]) + \
           dict_str + ')'
Immediate.repr_long = repr_long

def __repr__(self):
    if self.__dict__.has_key('_id'):
        return "%s(%s, %d)" % (
            self.__class__.__name__,
            self.__class__.__bases__[1].__repr__(self._primary[0]),
            self._id)
    else:
        return "%s(%s)" % (
            self.__class__.__name__,
            self.__class__.__bases__[1].__repr__(self._primary[0]),
            )
def __repr__(self):
    return "%s(%s)" % (
        self.__class__.__name__,
        self.__class__.__bases__[1].__repr__(self._primary[0]),
        )
Immediate.__repr__ = __repr__

def to_plain_python(self, storage):
    return self._primary[0]
Immediate.to_plain_python = to_plain_python

#
#**        Language core
class InterpreterError(exceptions.Exception):
    def __init__(self, args=None):
        self.args = args

class UnboundSymbol(exceptions.Exception):
    def __init__(self, args=None):
        self.args = args

class Interpret_tail_call(exceptions.Exception):
    # Used for passing tail call information UP the Python stack.
    # Arg: (tree, env, finish_progs)
    # where
    #   tree is the astType to continue executing
    #   env is the environment to evaluate in
    #   finish_progs is a list of functions to run after the tail call
    #                is finished.  Args are the .interpret() return
    #                value.
    def __init__(self, args=None):
        self.args = args

class Interpret_return(exceptions.Exception):
    def __init__(self, args=None):
        self.args = args

#
#***            Nested() types 
#****                Program
class Program(Nested):
    #
    # Program(seq_expr)
    #
    pass


def __init__(self, *primary, **kwds):
    self._outl_parent = None            # astType weakref. 
    self._outl_children = None          # (astType weakref) vaList
    self._outl_type  = 'subtree'        # "flat" | "nested" | "subtree"

    self.p_label = None                 # StringType
    return Nested.__init__(self, *primary, **kwds)
Program.__init__ = __init__

def set_label(self, lbl):
    assert isinstance(lbl, StringType)
    self.p_label = lbl
Program.set_label = set_label

def get_label(self):
    return self.p_label
Program.get_label = get_label

def eval_env(self):
    return getattr(self, "_eval_env", None)
Program.eval_env = eval_env



# 
#****                Return
class Return(Nested):
    # Return(expr)
    pass
#****                Loop
class Loop(Nested):
    # Loop(seq_expr)
    # The name, args, modifiers, body split is internally available.
    pass

# 
#****                Function
class Function(Nested):
    #
    # Function(opt_block_args, seq_expr)  { |a, ...| c;d;...}
    #
    pass

def nargs(self):
    """
    Return number of positional arguments.
    """
    return len(self.positional_block_args())
Function.nargs = nargs

def seq_expr(self):
    return self.deref(1)
Function.seq_expr = seq_expr

def raw_seq_expr(self):
    return self._primary[1]
Function.raw_seq_expr = raw_seq_expr

def __init__(self, *primary, **kwds):
    # self._binding_env = None
    self._binding_name = None           # "foo" for def foo(): BLOCK and
                                        # foo = { || ...}
    ## self._clone_of     = None           # source block
    return Nested.__init__(self, *primary, **kwds)
Function.__init__ = __init__


def block_copy(self, storage):
    # copy all, including envs.  This requires a all copies to come
    # from the original skeleton.
    rv = deepcopy(self)
    copy_char_info(self, rv)
    ## rv._clone_of = self._id
    return rv
Function.block_copy = block_copy

def named_block_args(self, symbols = 0):
    """
    Return named block args as (name : string, value : astType) list.
    """
    ma = Matcher()
    kv_pairs = []
    for ba in self.block_args():
        # Skip to keyword args.
        if ma.match(ba, MarkerTyped(String('name'), Symbol('symbol'))):
            continue

        # name  = val
        if not ma.match(ba, Set(MarkerTyped(String('name'), Symbol('_')),
                                Marker('val'))):
            raise InterpreterError, \
                  "Expected 'name' or 'key = value' argument, got: " + str(ba)

        if symbols:
            kv_pairs.append((ma._matches['name'], ma._matches['val']))
        else:
            kv_pairs.append((ma._matches['name'].as_index(),
                              ma._matches['val']))
    return kv_pairs
Function.named_block_args = named_block_args

def positional_block_args(self, symbols = 0):
    # Return a (string list) of argument names.
    ma = Matcher()
    arg_names = []
    for ba in self.block_args():
        # if not ma.match_exp_str(ba, '!! name symbol'):
        if not ma.match(ba, MarkerTyped(String('name'), Symbol('symbol'))):
            # Skip remaining (keyword) args.
            return arg_names
            ## raise InterpreterError, "Invalid argument type: " + str(ba)
        if symbols:
            arg_names.append(ma._matches['name'])
        else:
            arg_names.append(ma._matches['name'].as_index())
    return arg_names
Function.positional_block_args = positional_block_args

def block_args(self):
    # Return list of all arguments.
    return self.deref(0)
Function.block_args = block_args
# 
#****                Call
class Call(Nested):
    #
    # Call(simple_expr, simple_expr_list) f a b ...
    #
    # Interpretation
    pass

def positional_args(self):
    # Return (astType list) of  positional args.
    ma = Matcher()
    lst = []
    for ba in self.block_args():
        # Grab all all but `name  = val`.
        if not ma.match(ba, Set(MarkerTyped(String('name'), Symbol('_')),
                                Marker('val'))):
            lst.append(ba)
    return lst
Call.positional_args = positional_args

def named_args(self):
    """
    Return named block args as (name : string, value : astType) list.
    """
    ma = Matcher()
    kv_pairs = []
    for ba in self.block_args():
        # name  = val
        if ma.match(ba, Set(MarkerTyped(String('name'), Symbol('_')),
                            Marker('val'))):

            kv_pairs.append((ma._matches['name'].as_index(),
                             ma._matches['val']))
    return kv_pairs
Call.named_args = named_args

def nargs(self):
    """
    Return number of positional arguments.
    """
    return len(self.positional_args())
Call.nargs = nargs

def block_args(self):
    # Return list of all arguments.
    return self.deref(1)
Call.block_args = block_args


def __init__(self, *primary, **kwds):
    # ?? self._id_count = 0
    # ?? self._called_block = None
    Nested.__init__(self,*primary, **kwds)
Call.__init__ = __init__
# 
#****                Member
class Member(Nested):
    #
    # Member(simple_expr, simple_expr)  [ a.b ]
    #
    pass
# 
#****                If
class If(Nested):
    # If(cond, yes, no)
    pass

def __init__(self, *primary, **kwds):
    return Nested.__init__(self, *primary, **kwds)
If.__init__ = __init__

# 
#****                Labeled
class Labeled(Nested):
    def interpret(self, env, storage):
        pass
# 
#****                Let
class Let(Nested):
    # HERE.  scheme-style implementation
    def interpret(self, env, storage):
        pass
# 
#****                Set
class Set(Nested):
    #
    # Set(simple_expr, expr)
    #
    pass

def arg_names(self, raw_symbols = 0):
    # Return argument names as string list.
    # Also see Set.interpret
    args = self.deref(0)
    if isinstance(args, Tuple):
        name_list = []
        arg_list = args._primary[0]
        for nm in arg_list:
            # if not self._matcher.match_exp_str(nm, '!! name symbol'):
            if not self._matcher.match(nm, MarkerTyped(String('name'),
                                                      Symbol('symbol'))):
                raise InterpreterError, \
                      "Set: Invalid argument type: " + str(nm)
            if raw_symbols:
                name_list.append( self._matcher.get('name') )
            else:
                name_list.append( self._matcher.get('name').as_index() )
        return name_list

    # elif self._matcher.match_exp_str( args, '!! name symbol'):
    elif (self._matcher.match(args, MarkerTyped(String('name'),
                                                Symbol('_'))) or 
          self._matcher.match(args, MarkerTyped(String('name'),
                                                String('_')))):
        if raw_symbols:
            return [ self._matcher.get('name') ]
        else:
            return [ self._matcher.get('name').as_index() ]
    else:
        raise InterpreterError, "Set: Invalid first argument type: " + \
              str(self.deref(0))
Set.arg_names = arg_names

# 
#****                List
class List(Nested):
    #
    # List(alist)
    #

    # All List operations should forward to the contained alist.
    pass

def __init__(self, *primary, **kwds):
    self.l_label = None                 # StringType
    return Nested.__init__(self, *primary, **kwds)
List.__init__ = __init__

def set_label(self, lbl):
    assert isinstance(lbl, StringType)
    self.l_label = lbl
List.set_label = set_label

def get_label(self):
    return self.l_label
List.get_label = get_label

### eval_list ??
### def to_plain_python(self, storage):
###     return [to_plain_python_f(itm, storage)
###             for itm in self._eval_list]
### List.to_plain_python = to_plain_python

def find_child_index(self, id):
    return self._primary[0].find_child_index(id)
List.find_child_index = find_child_index

## def __len__(self):
##     return len(self._primary[0])
## List.__len__ = __len__

# This special definition breaks much code; use explicit access instead.
# def __getitem__(self, i):
#     return self._primary[0][i]
# List.__getitem__ = __getitem__


# 
#****                viewList
def viewList(*primary, **kwds):
    return Program(*primary, **kwds)


class cls_viewList(List):
    """
    A subclass of List for viewing of selected subtrees (outlining).
    """
    pass


def __repr__(self):
    return "%s(%s, %s)" % (self.__class__.__name__,
                             self.l_label,
                             tuple2str(self._primary),
                             )
cls_viewList.__repr__ = __repr__

def __init__(self, *primary, **kwds):
    self._outl_parent = None            # astType weakref. 
    self._outl_children = None          # (astType weakref) vaList
    self._outl_type  = 'nested'     # "flat" | "nested" | "subtree"
    return List.__init__(self, *primary, **kwds)
cls_viewList.__init__ = __init__

# 
#****                Map
class Map(Nested):
    #
    # Map(alist)
    #
    """
    The general mapping type.
    """
    pass

def __init__(self, *primary, **kwds):
    self._binding_name = None
    self.m_label = None                 # special display label.
    return Nested.__init__(self, *primary, **kwds)
Map.__init__ = __init__

def set_label(self, lbl):
    self.m_label = lbl
Map.set_label = set_label

def get(self, key):
    raise "internally modified: update calling code"
    return self._eval_env.ie_lookup_1(key)
Map.get = get

def to_plain_python(self, storage):
    dct = (self._eval_env._bindings)
    # dict_to_plain_python:
    newdct = {}
    for k,v in dct.items():
        # HERE. Env *should* use Path()s ...
        newdct[k] = v.to_plain_python(storage)
    return newdct
Map.to_plain_python = to_plain_python
# 
#****                Subdir(Map)
class Subdir(Map):
    # 
    # Subdir is a Map in which some keys are file names with the
    # absolute path as value.  Other entries are regular Map entries.
    # 
    pass

# 
#****                Tuple
class Tuple(Nested):
    #
    # Tuple(alist)
    #
    pass
def __init__(self, *primary, **kwds):
    Nested.__init__(self, *primary, **kwds)
    self.l_label = None                 # StringType
    self._primary[0].setthe(layout = 'horizontal')
Tuple.__init__ = __init__


#
#***            Immediate() types

# Broken:
# class Bool(Immediate, bool):
#       pass
# 
#****                Int
class Int(Immediate, IntType):
    pass
# 
#****                Float
class Float(Immediate, FloatType):
    pass
# 
#****                Complex
class Complex(Immediate, ComplexType):  # To be added...
    pass
# 
#****                String
class String(Immediate, StringType):
    pass

def as_index(self):
    return self._primary[0]
String.as_index = as_index

def FilepathString(name):
    assert isinstance(name, StringType), "Expecting string for file path."
    rv = String(name)
    if os.path.exists(name):
        rv._isfile = True
    else:
        rv._isfile = False
    return rv
    
def isfile(self):
    ''' Is (or was) self a valid file name? '''
    fe = getattr(self, "_isfile", None)
    if fe is None:
        if os.path.exists(self._primary[0]):
            self._isfile = True
            return True
        else:
            self._isfile = False
            return False
    else:
        return fe
String.isfile = isfile


# 
#****                Comment
class Comment(String, StringType):
    """
    A subclass of String with support for comments.
    """
    pass

# # def __init__(self):
# #     String.__init__(self)
# #     self._string = string
# # Comment.__init__ = __init__


# 
#****                Symbol
class Symbol(Immediate, StringType):
    pass

def as_index(self):
    return self._primary[0]
Symbol.as_index = as_index

#
#***            Specials
#****                Native
class Native:
    # Native is the general placeholder to use when native Python
    # VALUES are to be included in a tree, or when an external value
    # (say, the content of a file) is to be handled "natively".
    #
    # E.g. a Numeric array
    # resulting from interpretation may be put into a new tree for
    # display. 
    #
    # Native is similar to aNone and Immediates in behavior.  It
    # evaluates to the Python value it holds.
    # 

    def __str__(self):
        return self.__repr__()

    def __repr__(self):
        return "%s(%s)" % (self.__class__.__name__,
                           self._primary[0].__class__.__name__)

    def traverse_depth(self):
        yield self

    def traverse_breadth(self, head=0):
        yield self

def __init__(self, primary, **kwds):
    self._primary    = (primary,)
    self.__dict__.update(kwds)
    self._first_char = None
    self._last_char  = None
    self._pre_interp_hook = None    # callable of type
                                    # ((l3tree, env, storage) -> None)
    self._attributes = {}           # generic attributes, kept as
                                    # (key -> value) pairs.
Native.__init__ = __init__

def to_plain_python(self, storage):
    return self._primary[0]
Native.to_plain_python = to_plain_python

def value(self):
    return self._primary[0]
Native.value = value

# # def set_source_string(self, source_string):
# #     # Adjustment for block constructs at EOF
# #     lines = len(source_string.split('\n'))
# #     self._source_string = source_string

# #     # Adjustment for block constructs at EOF
# #     if self._last_char != None:
# #         row2, col2 = self._last_char
# #         if row2 >= lines:
# #             self._last_char = (lines - 1, col2)

# #     return self
# # Native.set_source_string = set_source_string

# # def eql(self, other):
# #     if self.__class__ == other.__class__:
# #         return True
# #     else:
# #         return False
# # Native.eql = eql

# 
#****                aNone
class aNone:
    # To allow attachment of labels, and for uniformity, the ast.None()
    # class is instantiated on every use, just as the other Immediate()s
    # 
    # This class should inherit from None, but this is illegal.
    # All Immediate() functions must be provided.

    def __str__(self):
        return self.__repr__()

    def __repr__(self):
        return self.__class__.__name__ + '()'

    def traverse_depth(self):
        yield self

    def traverse_breadth(self, head=0):
        yield self

def __len__(self):
    # For compatibility with Matcher().
    return 0
aNone.__len__ = __len__

def __init__(self, *primary, **kwds):
    self._primary    = (None,)
    self.__dict__.update(kwds)
    self._first_char = None
    self._last_char  = None
    self._pre_interp_hook = None    # callable of type
                                    # ((l3tree, env, storage) -> None)
    self._attributes = {}           # generic attributes, kept as
                                    # (key -> value) pairs.
aNone.__init__ = __init__

def to_plain_python(self, storage):
    return None
aNone.to_plain_python = to_plain_python

def set_source_string(self, source_string):
    # Adjustment for block constructs at EOF
    lines = len(source_string.split('\n'))

    self._source_string = source_string

    # Adjustment for block constructs at EOF
    if self._last_char != None:
        row2, col2 = self._last_char
        if row2 >= lines:
            self._last_char = (lines - 1, col2)

    return self
aNone.set_source_string = set_source_string

def eql(self, other):
    if self.__class__ == other.__class__:
        return True
    else:
        return False
aNone.eql = eql
aNone.eql_1 = eql



# Also see class Nested, aTree
# Note: this class' instances pickle improperly with protocol < 2, and
# python versions < 2.3
#****                aList
class aList(ListType):
    # 
    # To simplify interpret() and setup() code, the regular list needs
    # some extra features.
    #   In particular, access consistent with other astType requires the
    # 
    #       self._primary
    # 
    #   field; list access uses
    #
    #       self
    #       
    #   as ususal.
    #   
    # Updates of either require updates of both.
    #
    # Note: the List() class is for the L3 ast; the aList() class
    # is INTERNAL.
    # 
    # 
    def __str__(self):
        return self.__repr__()

    def __add__(self, other):
        return self.__class__( ListType.__add__(self, other) )

def __repr__(self):
    return self.__class__.__name__ + '(' + \
           ListType.__repr__(self) +  ')'
aList.__repr__ = __repr__

def repr_long(self):
    dict_str = dict2str(self.__dict__)
    if dict_str:
        dict_str = ', ' + dict_str
    return self.__class__.__name__ + '(' + \
           ListType.__repr__(self) + dict_str + ')'
aList.repr_long = repr_long

def __init__(self, arg, **kwds):
    ListType.__init__(self, arg)
    self._primary = (arg,)              # Form is ( [...], )
    # ?? self._id = None
    # ?? for textual persistence. use with __repr__.  Test.
    self.__dict__.update(kwds)
    self._first_char = None
    self._last_char  = None
    self._parent = None
    self._pre_interp_hook = None    # callable of type
                                    # ((l3tree, env, storage) -> None)
    self._attributes = {}           # generic attributes, kept as
                                    # (key -> value) pairs.
aList.__init__ = __init__


def to_plain_python(self, storage):
    return self._primary[0]
aList.to_plain_python = to_plain_python

def deref(self, index):
    return (self[index])
aList.deref = deref

def dependencies(self, env):
    """ Set up post-setup, pre-execution structures.
    """
    for child in self._primary:     child.dependencies(env)
aList.dependencies = dependencies

def eql(self, other):
    # as in Matcher.match,
    # Trees are assumed to have interface functions
    # __len__, __getitem__, and __class__

    if self.__class__ == other.__class__: # identical head
        # Test children
        nc = self.__len__()
        if nc != other.__len__():
            return False
        # Compare ALL children.
        for c in range(0,nc):
            if self[c].eql(other[c]):
                continue
            else:
                return False
        return True
    else:
        return False
aList.eql = eql


def eql_1(self, other):
    if self.__class__ == other.__class__: # identical head
        # Same number of children?
        nc = self.__len__()
        if nc != other.__len__():
            return False
        return True
    else:
        return False
aList.eql_1 = eql_1

def find_child_index(self, id):
    # Also see Nested.
    idx = 0
    for cc in self:
        if cc._id == id:
            return idx
        idx +=1
    return None
aList.find_child_index = find_child_index


# This __deepcopy__ (of a list subclass) causes infinite recursion
# during .interpret...
# # def __deepcopy__(self, memo):
# #     # Also see Nested.__deepcopy__
# #     # 
# #     # See copy_attribute() to restore missing attributes
# #     # 
# #     rv = self.__class__(*self._primary)
# #     direct_ref = ['_arg_env',
# #                   '_block_env',
# #                   '_def_env',
# #                   '_matcher',
# #                   '_eval_env',
# #                   ## '_primary',  # the subtree had better be copied...
# #                   '_storage',
# #                   ]
# #     stuff = {}
# #     for k,v in self.__dict__.items():
# #         if k in direct_ref:
# #             stuff[k] = self.__dict__[k]
# #         else:
# #             stuff[k] = deepcopy(v)
# #     rv.__dict__.update(stuff)

# #     try:    del rv._parent 
# #     except: pass

# #     try:    del rv._id
# #     except: pass
    
# #     return rv
# # aList.__deepcopy__ = __deepcopy__



# Defining this then also requires __getslice__;
# it also makes other code very hard to check.  Use explicit syntax
# instead.
# def __getitem__(self, index):
#     return storage.load(ListType.__getitem__(self, index))
# aList.__getitem__ = __getitem__

# 
#****                vaList
class vaList(aList):
    ''' subclass of aList with necessary restrictions for use in
    spanning trees.
        - no interpretation
        - no changes to children
        - no persistence
    '''
    pass


def interpret(self, env, storage):
    raise Exception("vaList must not be interpreted.  Internal error.")
vaList.interpret = interpret


def insert_child_rec(self, index, new, storage):
    raise Exception("Insertion into collapsed list is ambiguous, hence "
                    "not possible.  Expand the list first.  ")
vaList.insert_child_rec = insert_child_rec


def replace_child(self, orig_id, new_node):
    assert isinstance(orig_id, IntType)
    idx = self.find_child_index(orig_id)
    if idx is None:
        raise ReplacementError, "Child not found."
    # Update direct references.
    foo = self._primary[0]
    foo[idx] = new_node
    self._primary = (foo,)
    self[idx] = new_node
vaList.replace_child = replace_child


def insert_child(self, index, child):
    assert self._id != None
    # Also see Nested.insert_child()
    foo = self._primary[0]
    foo.insert(index, child)
    self._primary = (foo,)
    self.insert(index, child)
vaList.insert_child = insert_child


def detach_child(self, orig_id, storage):
    assert isinstance(orig_id, IntType)
    idx = self.find_child_index(orig_id)
    if idx is None:
        raise ReplacementError, "Child not found."
    # Update direct references.
    foo = self._primary[0]
    del foo[idx]
    self._primary = (foo,)
    del self[idx]
vaList.detach_child = detach_child


def setup_valist(self, w_, parallel_nd):
    # Return an empty alist, .setup() using the environment of
    # `parallel_nd`. 
    storage = w_.state_.storage
    parent = empty_parent()
    def_env = storage.get_attribute(parallel_nd._id, "stored_from_env")
    # Form the raw list.
    rv, _ = vaList([]).setup(parent, def_env, storage)
    return rv
vaList.setup_valist = setup_valist



#
#****                matcher elements
class Marker(Immediate, StringType):
    # Marker('symbol')
    pass

def name(self):
    # Note: no _storage use: MarkerTyped is Immediate()
    return (self._primary[0])
Marker.name = name

# 
#****                MarkerTyped
class MarkerTyped(Nested):
    # !! name expr -> MarkerTyped(Symbol('name'), expr)
    # where expr is a type sample.
    pass

def name(self):
    # Notice _storage use: MarkerTyped is Nested()
    return self.deref(0).as_index()
MarkerTyped.name = name

def expr(self):
    return self.deref(1)
MarkerTyped.expr = expr

# class Set(astType):
#     pass

#
#****                Inline
class Inline(Nested):
    #
    #   Inline( python_init_string )
    #       Raw Python code (especially module imports) can be provided here.
    #
    pass

def __init__(self, *primary, **kwds):
    ( self._python_init_string, ) = primary
    return Nested.__init__(self, *primary, **kwds)
Inline.__init__ = __init__

def __deepcopy__(self, memo):
    rv = Nested.__deepcopy__(self, memo)
    rv._update_refs()
    return rv    
Inline.__deepcopy__ = __deepcopy__


#
#****                Macro 

class Macro(Nested):
    #
    # Macro( in_args, body )
    #
    pass

def __init__(self, *primary, **kwds):
    Nested.__init__(self, *primary, **kwds)
Macro.__init__ = __init__

def block_copy(self, storage):
    rv = deepcopy(self)
    copy_char_info(self, rv)
    ## rv._clone_of = self._id
    return rv
Macro.block_copy = block_copy


def block_args(self):
    # Return list of all arguments.
    return self.deref(0)
Macro.block_args = block_args

def nargs(self):
    """
    Return number of arguments.
    """
    return len(self.block_args())
Macro.nargs = nargs

def raw_seq_expr(self):
    return self._primary[1]
Macro.raw_seq_expr = raw_seq_expr


#
#**        Editing / high level support

# Notes
# =========
#     The a[A-Z]* classes are meant for explicit construction; they have
#     no parsing elements.  Some a[A-Z]* classes (a)dd something to
#     built-in types.
#
#     The e[A-Z]* classes are meant for explicit construction; they
#     are intended for (e)diting functionality.
#


#
#***            macro manager (selection tree)
#
# The selection_tree format:
#
#    tree  ::= [tree label leaf * ]
#    leaf  ::= tree | value
#    value ::= anything not eTree
#

class eTree(Nested):
    #
    # eTree(label, l1, l2, ...)
    #
    def __init__(self, *primary, **kwds):
        Nested.__init__(self, *primary, **kwds)
        self._label = primary[0]

def __deepcopy__(self, memo):
    rv = Nested.__deepcopy__(self, memo)
    # Re-establish graph structures.
    rv._label = rv._primary[0]
    return rv    
eTree.__deepcopy__ = __deepcopy__


def append(self, subtree,
           model_cb = lambda subtree, subtree_idx : 0 ):
    # Append subtree and return new child's logical index.
    self._primary += (subtree,)
    subtree_idx = len(self._primary) - 2

    # Run external updates.
    model_cb(subtree, subtree_idx)

    return subtree_idx
eTree.append = append
#
#**        possible future derived types
# class Future(Nested):
#     pass


# class Cond(Nested):
#     pass

# class Manual_and(Nested):
#     pass

# class Manual_or(Nested):
#     pass

# class Dynamic_and(Nested):
#     pass

# class Dynamic_or(Nested):
#     pass

# class Vector(Nested):
#     pass

#*    Low-level program printing support
#**        source_substring
def source_substring(self):
    """
    Return the leading substring for self, at most one line.
    """
    if self._first_char != None:
        row1, col1 = self._first_char
    else:
        return "no_source"

    if self._last_char != None:
        row2, col2 = self._last_char
        str = self._source_string.split('\n')[row1]
        if row2 > row1:
            return str[col1:]
        else:
            return str[col1:col2]
    else:
        return "no_source"
astType.source_substring = source_substring

# 
#**        character range
def set_char_range(self, first, last):
    self._first_char = first
    self._last_char = last
    return self
Nested.set_char_range = set_char_range
Immediate.set_char_range = set_char_range
aNone.set_char_range = set_char_range
aList.set_char_range = set_char_range

def llet_char_range(self, first, last):
    # If self has no character range yet, set it. 
    if self._first_char is None:
        self._first_char = first
        self._last_char = last
    return self
Nested.llet_char_range = llet_char_range
Immediate.llet_char_range = llet_char_range
aNone.llet_char_range = llet_char_range
aList.llet_char_range = llet_char_range


def get_char_range(self):
    # Return (row, col), (row, col) pair.  Upper left / lower right.
    if self._first_char is None:
        if isinstance(self, Comment):
            pass
        else:
            glbl.logger.info("%s has no character position info." % self)
        return (0,0), (0,0)
    return self._first_char, self._last_char
Nested.get_char_range = get_char_range
Immediate.get_char_range = get_char_range
aList.get_char_range = get_char_range
aNone.get_char_range = get_char_range

# 
#**        source_string
def source_string(self):
    tst = astType.source_string(self)
    if tst != "no_source":
        return tst
    return self[0].source_string()
Program.source_string = source_string

# This is clearly wrong:
# # def source_string(self):
# #     return "\n".join( [child.source_string() for child in self] )
# # aList.source_string = source_string

def source_string(self):
    # 
    # Return the source string for self.
    # 
    if self._first_char != None:
        row1, col1 = self._first_char
    else:
        return "no_source"
    
    if not self._source_string:
        return "no_source"
    
    lines = self._source_string.split('\n')
    
    if self._last_char != None:
        row2, col2 = self._last_char
        if row2 > row1:
            lines = [ lines[i] for i in range(row1, row2 + 1) ]
            ### lines = [ lines[i] for i in range(row1, row2) ]
            lines[0] = lines[0][col1:None]
            lines[-1] = lines[-1][None:col2]
            return "\n".join(lines)
        else:
            return lines[row1][col1:col2]
    else:
        return "no_source"
astType.source_string = source_string
aNone.source_string = source_string
aList.source_string = source_string


def source_string(self):
    if (self._source_string == None) or (self._first_char == None):
        return self._primary[0]
    else:
        return astType.source_string(self)
Symbol.source_string = source_string

#
#**        source string information
def has_source_string(self):
    return self._first_char is not None
astType.has_source_string = has_source_string
aList.has_source_string = has_source_string
aNone.has_source_string = has_source_string

def has_source_string(self):
    return False
Native.has_source_string = has_source_string

def num_lines(self):
    if self.has_source_string():
        row1, col1 = self._first_char
        row2, col2 = self._last_char
        return (row2 - row1 + 1)
    else:
        raise Exception("No source string available.")
astType.num_lines = num_lines
aList.num_lines = num_lines
aNone.num_lines = num_lines



# 
#**        l3_repr
def l3_repr_dedented(self):
    # 
    # Return (a parseable?) representation of self, with leading
    # whitespace/indentation stripped  w.r.t. the first line.
    # 

    # E.g., given ::
    # 
    #         |<--- margin  
    #         return for_mic(mic + 1, iteration + 1,
    #                        lastp, lastp + num_img(mic + 1))
    # 
    # l3_repr(for_mic) would return ::
    # 
    #         |<--- margin  
    #         for_mic(mic + 1, iteration + 1,
    #                                    lastp, lastp + num_img(mic + 1))
    # 
    # while l3_repr_dedented returns
    # 
    #         |<--- margin  
    #         for_mic(mic + 1, iteration + 1,
    #                 lastp, lastp + num_img(mic + 1))
    # 
    # Note that split/join are inverses:
    #   "\n".join( "\n\na".split('\n')) -> '\n\na'
    # 

    (frow, fcol), (lrow, lcol) =  self.get_char_range()
    txt = self.l3_repr()
    if fcol > 0:
        txt_s = txt.split('\n')
        # Take the first line unchanged.
        txt_l = [ txt_s[0] ]          
        chopped_lines = False
        for ll in txt_s[1:None] :
            # Strip leading junk from remaining lines.
            txt_l.append( ll[fcol:None] )
            # Warn about chopped characters
            if len(ll) > 0 and (not ll[0:fcol].isspace()):
                chopped_lines = True
        if chopped_lines:
            # For strings, chopping the left returns a different
            # string.  Similarly, expressions must not be chopped.
            print ("WARNING: source expression has inverted indentation."
                   "  Expect display oddities.\n"
                   "    Expression: %(txt)s\n"
                   % locals())
            txt = self.l3_repr()
        else:
            txt = "\n".join(txt_l)
    return txt
astType.l3_repr_dedented = l3_repr_dedented
aNone.l3_repr_dedented = l3_repr_dedented
aList.l3_repr_dedented = l3_repr_dedented


def l3_repr(self):
    # Return a parseable representation of self.
    if self._source_string in [None]:
        raise Exception("No valid l3 string available for " + repr(self))
    else:
        return self.source_string()
astType.l3_repr = l3_repr
astType.l3_string = l3_repr
aNone.l3_repr = l3_repr
aList.l3_repr = l3_repr



def l3_repr(self):
    # Return a parseable representation of self.
    if self._source_string in [None]:
        return self._primary[0]
    else:
        return self.source_string()
String.l3_repr = l3_repr
Symbol.l3_repr = l3_repr
Symbol.l3_string = l3_repr

def l3_repr(self):
    # Return a parseable representation of self.
    if self._source_string in [None]:
        return str(self._primary[0])
    else:
        return self.source_string()
Immediate.l3_repr = l3_repr


# 
#**        l3_string
def l3_string(self):
    # Return a more legible (but not parseable) representation of
    # self. 
    st = self.l3_repr()
    if len(st) < 2:
        return st
    if len(st) < 6:
        if st[0] == st[-1] and st[0] in [ '"', "'" ]:
            return st[1:-1]
        else:
            return st
    else:
        "'''"
        '"""'                           # make etags happy.
        if st[0:3] == st[-3:None] and st[0:3] in [ '"""',
                                                   "'''" ]:        
            return st[3:-3]
        elif st[0] == st[-1] and st[0] in [ '"', "'" ]:
            return st[1:-1]
        else:
            return st
String.l3_string = l3_string

def l3_string(self):
    return "None"
aNone.l3_string = l3_string

def l3_string(self):
    return repr(self)
Native.l3_string = l3_string
# 
#**        py_string
# Simple string representations of Immediate()s.
# Use get_infix_string() for new code.

def py_string(self):
    return StringType.__str__(self._primary[0])
String.py_string = py_string

def py_string(self):
    return StringType.__str__(self._primary[0])
Symbol.py_string = py_string

def py_string(self):
    return repr(self._primary[0])
Native.py_string = py_string

def py_string(self):
    return ""
aNone.py_string = py_string

def py_string(self):
    # Static dependency restrictions: for a.b, both must be Symbols().
    # Get b (of a.b)
    first = self.deref(0)
    second = self.deref(1)
    if isinstance(first, Symbol):
        if isinstance(second, Symbol):
            mem_name = second.py_string()
        else:
            raise DataDagError, "In a.b, b is not a name: " + str(second)
    else:
        raise DataDagError, "In a.b, a is not a name: " + str(first)

    return "%s.%s" % (first.py_string(), second.py_string())
Member.py_string = py_string



#*    Interaction with program text, low level support

#         For the full program tree, recursive "painting" of character
#         ranges is a simple way to go from the hierachial information in
#         the code
#             def a(b,c): b + c
#             ~~~~~~~~~~~~~~~~~ , def
#                 ~             , name
#                   ~~~         , arg sequence
#                   ~ ~         , individual args
#                         ~   ~ , symbols
#                         ~~~~~ , expression
#
#         to the necessary "flat" information needed in the text sequence
#             def a(b,c): b + c
#             ddddnaiaiaddseees
#         A top-down painting is in the needed order.
#
def get_paint_array(code_str, max_val = 'inf'):
    """ Using the same string passed to reader.parse(),
    return a Program.paint_array() compatible structure.
    Direct use is DEPRECATED.
    """
    # E.g.:
    # >>> get_paint_array("first\nsecond")
    # [[0, 1, 2, 3, 4], [0, 1, 2, 3, 4, 5]]

    max_val = float(max_val)

    lines = code_str.split("\n")                # windows?
    lines_array = [max_val] * (len(lines))
    i = 0
    for line in lines:
        lines_array[i] = [max_val] * (len(line))
        i += 1
    return lines_array

def paint_array_start(self):
    '''
    Form the _id array used for identification of tree nodes.
    Node ids are always integer; positions not corresponding to any
    node are filled with float values.
    '''
    # Get largest id.
    largest = 0
    for node in self.top_down():
        largest = max(largest, node._id)
    # Choose larger
    largest *= 10.0
    # Finish the array
    paint_a = get_paint_array(self._source_string, max_val = largest)
    self.paint_array(paint_a)
    return paint_a
Nested.paint_array_start = paint_array_start

def generic_paint_array(self, arr):
    # Paint self.
    if (self._first_char != None and self._last_char != None):
        row1, col1 = self._first_char
        row2, col2 = self._last_char    # col2 is 1 past the last character
        if row2 > row1:
            # Paint only the first row.
            ll = len(arr[row1])
            arr[row1][col1 : ll] = [self._id] * (ll - col1)
        else:
            # Repaint the appropriate range with "color" self._id
            arr[row1][col1:col2] = [self._id] * (col2 - col1)

def paint_array(self, arr):
    generic_paint_array(self,arr)
    # Paint children.
    for child in self._primary:
        child.paint_array(arr)
Nested.paint_array = paint_array

def paint_array(self, arr):
    generic_paint_array(self, arr)
Immediate.paint_array = paint_array

def paint_array(self, arr):
    pass
aNone.paint_array = paint_array

def paint_array(self, arr):
    generic_paint_array(self,arr)
    # Paint children.
    for child in self._primary[0]:
        child.paint_array(arr)
aList.paint_array = paint_array

#*    Incremental evaluation
# Classes to use as status markers.

class IncEval:
    pass

class IEInvalidTime(exceptions.Exception):
    def __init__(self, args="INV"):
        self.args = args

    def __cmp__(self, other):
        raise self

# Time stamp ordering is ie_setup_time, ie_external_time, integers
ie_setup_time       = -22
ie_external_time    = -11
ie_unusable_time    = IEInvalidTime()

def __init__(self, initial_time = 1):
    assert (initial_time > 0 )

    # Simple time tracking.
    #     timestamp ::= int
    self._timestamp_dct = {}
    self._time = initial_time

    # Modified tree tracking.
    #     _replacements ::=  tree_id(new) -> (tree_id(orig), timestamp)
    self._replacements = {}

    # Function clone handling.
    #      id                          -> program
    #      (id, 'envs')                -> (env, env)
    #
    #      (id, call_count, arg_index) -> program
    #      ( (block_inv._id, ccount, arg_index) , 'envs' ) -> (env, env)
    # with types
    #      id         :: int,
    #      program    :: astType
    #      call_count :: int
    #      arg_index  :: int
    # and (env, env) == eval_env, arg_env
    self._block_clones = {}

    # Env handling.
    self._envs = {}
IncEval.__init__ = __init__

#
#**        General time stamping
def touch(self, id):
    stamp = self._timestamp_dct[id] = self.time()
    return stamp
IncEval.touch = touch

def touch_setup(self, id):
    self._timestamp_dct[id] = ie_setup_time
IncEval.touch_setup = touch_setup

def is_setup_only(self, id):
    return self._timestamp_dct[id] == ie_setup_time
IncEval.is_setup_only = is_setup_only

def touch_value(self):
    return self.time()
IncEval.touch_value = touch_value

def time(self):
    self._time += 1
    return self._time - 1
IncEval.time = time

def get_timestamp(self, tree_id):
    return self._timestamp_dct[tree_id]
IncEval.get_timestamp = get_timestamp

def set_timestamp(self, id, stamp):
    # id ::= int | (int, string)
    self._timestamp_dct[id] = stamp
IncEval.set_timestamp = set_timestamp

def newest(self, fst, snd):
    # fst, snd are timestamps
    #
    # For a compound result (list, tuple, etc.), changing a single
    # entry changes the compound.  Use this function via e.g.
    #       reduce(IncEval.newest, status_list)
    # to determine the compound's status.
    #
    return max(fst, snd)
IncEval.newest = newest

def tree_is_older(self, tree_id, val_time):
    # Compare the tree's and leaf's timestamp.
    # special case:
    #     tree        value
    #     ----------------------
    #     setup   <   setup

    # The remaining tested cases are
    #     tree        value
    #     ----------------------
    #     external <  int
    #     setup   <   external
    #     setup   <   int
    # and these correspond to the usual ordering; overall, use
    #   setup < external < integer

    tree_time = self._timestamp_dct[tree_id]

    return (tree_time < val_time)
IncEval.tree_is_older = tree_is_older

# def is_newer(self, fst, snd):
#     # The standard ordering relations <, >, = require care with the
#     # special values here, so is_newer() is left undefined.
# IncEval.is_newer = is_newer


#
#**        block clones
# Function clones' semantics under incremental evaluation differ from
# those of Call clones.
def clone_table(self):
    return self._block_clones
IncEval.clone_table = clone_table

def has_clone(self, src):
    return self._block_clones.has_key(src)
IncEval.has_clone = has_clone

#
#**        Env() handling
# Env() semantics under incremental evaluation differ from defaults.
# [ in at least Map.interpret() ]
def env_table(self):
    return self._envs
IncEval.env_table = env_table

def has_env_for(self, id):
    return self._envs.has_key(id)
IncEval.has_env_for = has_env_for


#*    modified tree evaluation
class ModifiedEval:
    pass

#
#**        modified tree attributes
def set_original_for(self, new_id, orig_id):
    pass
ModifiedEval.set_original_for = set_original_for

def original_for(self, tree_id):
    # Return the (id, timestamp) of the original tree replaced by
    # tree_id, or None.
    return self._replacements.get(tree_id)
ModifiedEval.original_for = original_for

def is_replacement(self, tree_id):
    # Return ACTIVE replacement status.
    return (self._replacements.has_key(tree_id) and
            not self._replacements_touched.has_key(tree_id) )

ModifiedEval.is_replacement = is_replacement

def not_replacement(self, tree_id):
    # Treat the tree_id as original from now on.
    self._replacements_touched[tree_id] = 1
ModifiedEval.not_replacement = not_replacement


#*    post-parsing  -- .setup()
#
#**        Nested types.
def setup(self, parent, def_env, storage):
    """ Set up post-parsing, pre-execution structures.
    """
    # Also see aList.setup
    self._parent = parent._id

    # Store in Memory()
    self._id = storage.store(self, def_env)
    child_id_list = [child.setup(self, def_env, storage)
                     for child in self._primary]

    self._primary = tuple([child for child, id in child_id_list ])

    # Incremental evaluation prep.
    storage.ie_.touch_setup(self._id)

    return self, self._id
Nested.setup = setup


def setup_if_for(self):
    # Replace macro-only identifiers for the special case
    #       if "for": ...
    # 
    # See also reader.py, rule
    #       expr : FOR expr IN expr COLON py_block
    # and l3if_chooser()
    #
    # Replace ITEMS, IDX, LEN, LOOP in
    # 
    # print reader.parse('''
    # if "for":
    #     ! ITEMS = ! SEQ
    #     ! IDX = 0
    #     ! LEN = len(! ITEMS)
    #     # orig. for
    #     def "LOOP"():
    #         if ! IDX < ! LEN: 
    #             ! IDX = ! IDX + 1
    #             # V in S.
    #             ! V = ! ITEMS[ ! IDX - 1 ]
    #             # Body B
    #             ! B
    #             # Iterate.
    #             return ! LOOP()
    #     ! LOOP()
    # ''')
    #
    # but keep original V, SEQ, B.
    # 
    # The following pattern is from above, with manual fix for "LOOP"().
    # 
    ma = Matcher()    
    if ma.match(
        self,
        If(String('for'), aList([Set(Marker('ITEMS'), Marker('SEQ')), Set(Marker('IDX'), Int(0)), Set(Marker('LEN'), Call(Symbol('len'), aList([Marker('ITEMS')]))), Set(Marker('LOOP'), Macro(aList([]), aList([If(Call(Symbol('<'), aList([Marker('IDX'), Marker('LEN')])), aList([Set(Marker('IDX'), Call(Symbol('+'), aList([Marker('IDX'), Int(1)]))), Set(Marker('V'), Call(Member(Symbol('operator'), Symbol('getitem')), aList([Marker('ITEMS'), Call(Symbol('-'), aList([Marker('IDX'), Int(1)]))]))), Marker('B'), Return(Call(Marker('LOOP'), aList([])))]), aList([]))]))), Call(Marker('LOOP'), aList([]))]), aList([]))):
        # 
        id_s = str(self._id)
        # 
        # One-time manual tree conversions:
        #     (query-replace "Marker('ITEMS')" "Symbol('ITEMS' + id_s)" )
        #     (query-replace "Marker('IDX')" "Symbol('IDX' + id_s)" )
        #     (query-replace "Marker('LEN')" "Symbol('LEN' + id_s)" )
        #     (query-replace "Marker('LOOP')" "Symbol('LOOP' + id_s)" )
        # 
        #     (query-replace "Marker('SEQ')" "ma['SEQ']" )
        #     (query-replace "Marker('V')" "ma['V']" )
        #     (query-replace "Marker('B')" "ma['B']" )
        # 
        foo = list(self._primary)
        foo[1] = aList([Set(Symbol('ITEMS' + id_s), ma['SEQ']), Set(Symbol('IDX' + id_s), Int(0)), Set(Symbol('LEN' + id_s), Call(Symbol('len'), aList([Symbol('ITEMS' + id_s)]))), Set(Symbol('LOOP' + id_s), Macro(aList([]), aList([If(Call(Symbol('<'), aList([Symbol('IDX' + id_s), Symbol('LEN' + id_s)])), aList([Set(Symbol('IDX' + id_s), Call(Symbol('+'), aList([Symbol('IDX' + id_s), Int(1)]))), Set(ma['V'], Call(Member(Symbol('operator'), Symbol('getitem')), aList([Symbol('ITEMS' + id_s), Call(Symbol('-'), aList([Symbol('IDX' + id_s), Int(1)]))]))), ma['B'], Return(Call(Symbol('LOOP' + id_s), aList([])))]), aList([]))]))), Call(Symbol('LOOP' + id_s), aList([]))])
        self._primary = tuple(foo)
If.setup_if_for = setup_if_for


def setup_if_while(self):
    # Replace macro-only identifiers for the special case
    #       if "while": ...
    # 
    # See also reader.py, rule
    #       expr : WHILE expr COLON py_block
    # and l3if_chooser()
    # 
    # Replace WLOOP in
    # 
    # print reader.parse('''
    # if "while":
    #     def "WLOOP"():
    #         if not !C:           # force boolean evaluation via not
    #             return 
    #         else:
    #             !B
    #         return !WLOOP()
    #     !WLOOP()
    # ''')
    #    
    # but keep original C and B.
    # 
    # The following pattern is from above, with
    #     Set(Symbol('WLOOP')...) -> Set(Marker('WLOOP')...)
    #     aList([Marker('B')]) -> Marker('B')
    #     
    ma = Matcher()    
    if ma.match(self,
                If(String('while'), aList([Set(Marker('WLOOP'), Macro(aList([]), aList([If(Call(Symbol('not'), aList([Marker('C')])), aList([Return(aNone())]), Marker('B')), Return(Call(Marker('WLOOP'), aList([])))]))), Call(Marker('WLOOP'), aList([]))]), aList([]))
                ):
        # 
        id_s = str(self._id)
        # 
        # One-time manual tree conversions:
        #     (query-replace "Marker('WLOOP')" "Symbol('WLOOP' + id_s)" )
        #     (query-replace "Marker('C')" "ma['C']")
        #     (query-replace "Marker('B')" "ma['B']")
        #
        foo = list(self._primary)
        foo[1] = aList([Set(Symbol('WLOOP' + id_s), Macro(aList([]), aList([If(Call(Symbol('not'), aList([ma['C']])), aList([Return(aNone())]), ma['B']), Return(Call(Symbol('WLOOP' + id_s), aList([])))]))), Call(Symbol('WLOOP' + id_s), aList([]))])
        self._primary = tuple(foo)
If.setup_if_while = setup_if_while


def setup(self, parent, def_env, storage):
    """ Set up post-parsing, pre-execution structures.
    """
    # Also see Nested.setup
    self._parent = parent._id

    # Store in Memory()
    self._id = storage.store(self, def_env)

    # Replace macro-only identifiers for the special case
    #       if "while": ...
    self.setup_if_while()

    # Replace macro-only identifiers for the special case
    #       if "for": ...
    self.setup_if_for()
            
    # Continue regular setup.
    child_id_list = [child.setup(self, def_env, storage)
                     for child in self._primary]

    self._primary = tuple([child for child, id in child_id_list ])

    # Incremental evaluation prep.
    storage.ie_.touch_setup(self._id)

    return self, self._id
If.setup = setup


def setup(self, parent, def_env, storage):
    """ Set up post-parsing, pre-execution structures.
    """
    # Also see Nested.setup
    self._parent = parent._id

    # Store in Memory()
    self._id = storage.store(self, def_env)

    child_id_list = [child.setup(self, def_env, storage)
                     for child in self]

    self._primary =     ([child for child, id in child_id_list ],)

    # Incremental evaluation prep.
    storage.ie_.touch_setup(self._id)

    return self, self._id
aList.setup = setup

def setup(self, parent, def_env, storage):
    # Macro arguments must be set up in their expansion, but Inline
    # has no expansion.
    return Nested.setup(self, parent, def_env, storage)
Inline.setup = setup


def setup(self, parent, def_env, storage):
    # Program()s are GIVEN the appropriate Env(), so
    # instead of self._block_env = def_env.new_child(self):
    self._block_env = def_env
    return Nested.setup(self, parent, self._block_env, storage)
Program.setup = setup

def setup(self, parent, def_env, storage):
    # Bindings in environments. 
    argument_env = def_env.new_child(self, name = "skel.arg")
    #       Positional arguments.
    for ba in self.positional_block_args():
        argument_env.bind(ba, None)     # static dependency bindings.
    #       Named arguments.
    for (argn, argv) in self.named_block_args():
        argument_env.bind(argn, argv)   # static dependency bindings.

    block_env = argument_env.new_child(self, name = "skel.blck")
    self._arg_env = argument_env
    self._block_env = block_env

    rv = Nested.setup(self, parent, block_env, storage)

    # Provide name->id bindings.
    block_arg_l = self.deref(0)
    ii = 0
    for ba in self.positional_block_args():
        argument_env.bind_id(ba, block_arg_l[ii]._id)
        ii += 1
    for argn, _ in self.named_block_args():
        # Use id of Set
        argument_env.bind_id(argn, block_arg_l[ii]._id)
        ii += 1
    return rv
Function.setup = setup


def setup(self, parent, def_env, storage):
    # Initialize internal tree.
    self.l_view_call.setup(parent, def_env, storage)

    rv = Nested.setup(self, parent, def_env, storage)
    return rv
Loop.setup = setup


def setup(self, parent, def_env, storage):
    # Environments
    self._arg_env = def_env
    self._block_env = def_env

    rv = Nested.setup(self, parent, def_env, storage)
    return rv
Macro.setup = setup


def setup(self, parent, def_env, storage):
    # extra store ??
    # self._stored_in = None
    self._matcher = Matcher()

    for name in self.arg_names():
        def_env.bind_df(name, None) # static dependency bindings.

    rv = Nested.setup(self, parent, def_env, storage)

    # .data_dag() preparation.
    arg_symbols = self.arg_names(raw_symbols = 1)
    ii = 0
    for name in self.arg_names():
        def_env.bind_id_df(name, arg_symbols[ii]._id)
        ii += 1

    # Check for
    #       def foo():
    #           ...
    #  and use the name 'foo' for the body's _binding_name.
    #
    # Pattern from
    #   import reader ;   reload(reader) ;
    #   reader.parse('!! def_name string = !! the_block {|bb| bb}')
    # and modified.
    if self._matcher.match(self,
                           Set(MarkerTyped(String('def_name'),
                                           Symbol('string')),
                               MarkerTyped(String('the_block'), Function()))):
        ma = self._matcher._matches
        ma['the_block']._binding_name = ma['def_name']

        # .data_dag() preparation --  also provide block binding
        def_env.bind_df(ma['def_name'].py_string(), ma['the_block'])

    # Check for
    #       foo = { ... }
    #           ...
    #  and use the name 'foo' for the Map()'s _binding_name.
    #
    # Pattern from
    #   import reader ;   reload(reader) ;
    #   reader.parse('!! def_name string = !! the_map { }')
    # and modified.
    if self._matcher.match(self,
                           Set(MarkerTyped(String('def_name'),
                                           Symbol('string')),
                               MarkerTyped(String('the_map'), Map()))):
        ma = self._matcher._matches
        ma['the_map']._binding_name = ma['def_name']

        # .data_dag() preparation --  also provide block binding
        def_env.bind_df(ma['def_name'].py_string(), ma['the_map'])

    return rv
Set.setup = setup

def setup(self, parent, def_env, storage):
    block_env = def_env.new_child(self, name = "skel.blck")
    self._block_env = block_env
    return Nested.setup(self, parent, block_env, storage)
Map.setup = setup

#
#**        Immediates.
def setup(self, parent, def_env, storage):
    """ Set up post-parsing, pre-execution structures.
    """
    self._parent = parent._id

    # Store in Memory()
    self._id = storage.store(self, def_env)

    # Incremental evaluation prep.
    storage.ie_.touch_setup(self._id)

    return self, self._id
Immediate.setup = setup

def setup(self, parent, def_env, storage):
    """ Set up post-parsing, pre-execution structures.
    """
    self._parent = parent._id

    # Store in Memory()
    self._id = storage.store(self, def_env)

    # Incremental evaluation prep.
    storage.ie_.touch_setup(self._id)

    return self, self._id
aNone.setup = setup
Native.setup = setup

#*    Interpretation -- .interpret()
# Incremental evaluation note:
#   After evaluation, a node's status is always 'evaluated', but the
#   .interpret() return status may be different -- to inform the
#   parent of appropriate action.

#
#**        external entry point
def interpret_start(self, env, storage):
    try:
        rv, ie_status = self.interpret(env, storage)
        return rv
    except Exception, e:
        print "Warning: Returning Exception"
        raise
        return e                        # ?? most useful info??
Program.interpret_start = interpret_start

#
#**        Nested types
def interpret(self, env, storage):
    raise InterfaceOnly
Nested.interpret = interpret


def interpret(self, env, storage):
    # Run the python code and import the resulting names into the
    # current environment.
    # 
    # The python fragment is ALWAYS interpreted, to avoid pickling
    # problems.  The values returned by the Python code must be
    # CONSTANT over repeated calls.
    # 
    # The Python code fragment is considered atomic; changes to the
    # String() holding it will re-evaluate.
    #
    # The Python string can use l3 values, but it cannot call l3
    # functions.
    # This is unlike the l3 call py_f(l3_g, x), for which special handling
    # allows calling l3 from python.

    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)
    py_string, ie_status = self.deref(0).interpret(env, storage)

    # Incremental evaluation check.
    if storage.ie_.tree_is_older(self._id, ie_status):

        # To
        #   - get useful error messages, and
        #   - allow pickling of executed inline code including functions
        # the string is written to a file, and that executed.
        # The file is kept. 

        fname = os.path.join(os.getcwd(),"_l3_inline-%d" % self._id)
        py_file = open(fname, "w")
        py_file.write(py_string)
        py_file.close()

        # Evaluate and store.
        #  -- Assignments are made in a local python dict [py_env];
        #     new names and overwritten names are imported back to [env];
        #  -- The [env] bindings are made available via globals() so
        #     they are not changed outside of L3 control.  

        # These name binding cases are illustrated via
        #     py_env = {}
        #     all_globals = {"aa" : 10}
        #     all_globals.update(globals())
        #     exec "aa = aa + 1; aa += 10" in all_globals, py_env
        #     exec "global aa; aa = 1" in all_globals, py_env

        py_env = {'def_env' : env}
        all_globals = env.all_lexical_bindings({})
        all_globals.update(globals())
        execfile(fname, all_globals, py_env)
        env.import_all_names(py_env)    # Uses bind_mem_only for
                                        # EXTERNAL time stamp.

        # Keeping py_env is a major pickle trap, so evaluate the
        # Python code body every time to get them.
        # # rv = py_env
        rv = None

        # Interpretation values.
        storage.id2tree(rv, self)
        storage.set_attributes(self._id,
                               "interp_result", None,
                               "interp_env", env)

        # Incremental evaluation data.
        ie_status = storage.ie_.touch(self._id)
        return rv, ie_status

    else:
        # Keeping py_env is a major pickle trap, so evaluate the
        # Python code body every time to get them.
        # The original evaluation's time stamp is used, so external
        # additions will not cause re-execution.
        fname = os.path.join(os.getcwd(),"_l3_inline-%d" % self._id)

        py_env = {'def_env' : env}
        all_globals = env.all_lexical_bindings({})
        all_globals.update(globals())
        execfile(fname, all_globals, py_env)
        env.import_all_names(py_env)    # Override all EXTERNAL time
                                        # stamp values.
        return ( py_env, storage.ie_.get_timestamp(self._id) )
Inline.interpret = interpret


def interpret(self, env, storage):
    # See also Map.interpret(), aList.interpret
    # Return last expr value.
    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    seq_expr = self.deref(0)
    if len(seq_expr) == 0:
        raise InterpreterError, "Empty program"
    else:
        rv_stat_l = [(expr).interpret(env, storage) for expr in seq_expr]

    self._eval_env = env
    rv, last_stamp = rv_stat_l[-1]

    # Incremental evaluation check.
    newest_stamp = reduce(storage.ie_.newest,
                          [status for _, status in rv_stat_l])
    if storage.ie_.tree_is_older(self._id, newest_stamp):
        # Interpretation values.
        storage.id2tree(rv, self)
        storage.set_attributes(self._id,
                               "interp_result", rv,
                               "interp_env", env)
        # Incremental evaluation data.
        storage.ie_.touch(self._id)
        storage.ie_.set_timestamp( (self._id, 'value'), last_stamp )

        return rv, last_stamp
    else:
        # ---- Nothing changed.
        return storage.get_attribute(self._id, "interp_result"),  \
               storage.ie_.get_timestamp( (self._id, 'value') )

Program.interpret = interpret

def interpret(self, env, storage):
    # Also see Call.interpret.

    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    # Incremental evaluation check.
    if storage.ie_.is_setup_only(self._id):
        self._def_env = env

        # Evaluate named arguments.
        for (arg_name, expr) in self.named_block_args():
            arg_val, status = expr.interpret(env, storage)
            self._arg_env.bind_ptr(arg_name, arg_val, self._id)
            self._arg_env.bind_time_stamp_ptr(arg_name, status, self._id)
            
        # Interpretation values.
        storage.id2tree(self, self)
        storage.set_attributes(self._id,
                               "interp_result", self,
                               "interp_env", env)
        # Incremental evaluation data.
        stamp = storage.ie_.touch(self._id)

        return self, stamp
    else:
        return self, storage.ie_.get_timestamp(self._id)
Function.interpret = interpret

def interpret(self, env, storage):
    # Also see Call.interpret.

    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    # Incremental evaluation check.
    if storage.ie_.is_setup_only(self._id):
        self._def_env = env

        # Evaluate named arguments.
            
        # Interpretation values.
        storage.id2tree(self, self)
        storage.set_attributes(self._id,
                               "interp_result", self,
                               "interp_env", env)
        # Incremental evaluation data.
        stamp = storage.ie_.touch(self._id)

        return self, stamp
    else:
        return self, storage.ie_.get_timestamp(self._id)
Macro.interpret = interpret

def interpret(self, env, storage, tail_finishing_progs = []):
    # Also see CallableFunction.__call__
    # This code is for tail call handling.
    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    fin_progs = []                      # Ensure NEW list.
    fin_progs.extend(tail_finishing_progs)
    while 1:
        try:
            # No Incremental evaluation data here.
            # # rv, ie_status = self._call_real_interpret(env, storage)
            rv, ie_status = self._dispatch(env, storage)
        except Interpret_tail_call, contin:
            self, env, _prog_l = contin.args
            fin_progs.extend(_prog_l)
            continue
        else:
            # Finish up after tail calls.
            fin_progs.reverse()
            for finish in fin_progs:
                finish(rv, ie_status)
            return rv, ie_status
Call.interpret = interpret


def _dispatch(self, env, storage):
    # Find block, ignore time stamp.
    try:
        block, _ = self.deref(0).interpret(env, storage)
    except UnboundSymbol:
        # No l3 binding found, check shell commands.
        block = self.deref(0)
        if isinstance(block, (String, Symbol)):
            if glbl.shell_cmds.exists( block.py_string() ):
                return self._interp_shell(block, env, storage)

    if not block:
        # Nothing found.
        raise InterpreterError, "Function/name not found: " + str(block)

    # Function / Macro
    # {|| ... }(a,b) or  [|| ... ](a,b)
    if isinstance(block, (Function, Macro)):
        return self._interp_func(block, env, storage)

    # Handle native Python
    elif callable(block):
        return self._interp_native(block, env, storage)

    else:
        raise InterpreterError, "Expected Function(), got " + str(block)
Call._dispatch = _dispatch


def _interp_shell(self, block, env, storage):
    # Verify argument count.

    #---- Bind named block arguments from Call().
    named_arg_status_l = [expr.interpret(env, storage)
                          for arg_name, expr in self.named_args()]

    # ---- Bind positional block arguments.
    pos_arg_status_l = [ba.interpret(env, storage)
                        for ba in self.positional_args() ]

    def new_call_new_val():
        #       Convert arguments to strings.
        # A list could be converted to different textual forms
        # requiring a much more complex setup, so ignore lists for
        # now. 
        # 
        # Positional args.
        pos_wrapped = []
        arg_index = 0
        for ba, _ in pos_arg_status_l:
            if isinstance(ba, Nested):
                raise InterpreterError("no nested shell arguments")

            elif isinstance(ba, String):
                pos_wrapped.append(ba.py_string())

            elif not isinstance(ba, StringType):
                raise InterpreterError("shell arguments must evaluate "
                                       "to simple strings.")
            else:
                pos_wrapped.append(str(ba))
            arg_index += 1

        # Named args.
        named_wrapped = []
        arg_index = 0
        for (arg_name, _) in self.named_args():
            arg, _ = named_arg_status_l[arg_index]
            if isinstance(arg, Nested):
                raise InterpreterError("shell arguments must evaluate "
                                       "to simple strings.")
            else:
                named_wrapped.append([arg_name, arg.py_string()])
            arg_index += 1


        # ---- Evaluate.
        try:
            rv = (self._run_process(block.py_string(),
                                    pos_wrapped, named_wrapped))
            ie_status = storage.ie_.time()
        except Interpret_tail_call:
            raise                   # not reached ?
        except Interpret_return, e:
            rv, ie_status = e.args  # not reached ?

        # Interpretation values.
        storage.id2tree(rv, self)
        storage.set_attributes(self._id,
                               "interp_result", rv, "interp_env", env)

        # Incremental evaluation data.
        storage.ie_.touch(self._id)
        storage.ie_.set_timestamp( (self._id, 'value'), ie_status)

        return rv, ie_status
        # -----------

    # ---- Incremental evaluation check.
    if (len(named_arg_status_l) + len(pos_arg_status_l)) == 0:
        if storage.ie_.is_setup_only(self._id):
            return new_call_new_val()
        else:
            return storage.get_attribute(self._id, "interp_result"),\
                   storage.ie_.get_timestamp(self._id)
    else:
        arg_eval_time = reduce(storage.ie_.newest,
                               [status for _, status in named_arg_status_l] +
                               [status for _, status in pos_arg_status_l])
        if storage.ie_.tree_is_older(self._id, arg_eval_time):
            return new_call_new_val()
        else:
            return storage.get_attribute(self._id, "interp_result"),\
                   storage.ie_.get_timestamp(self._id)
Call._interp_shell = _interp_shell


def _run_process(self, cmd, pos_arg_l, name_val_l):
    # This member function can be replaced by the gui for interactive
    # use. 
    return glbl.shell_cmds.system(cmd, pos_arg_l, name_val_l)
Call._run_process = _run_process


def _interp_native(self, py_func, env, storage):
    # Verify argument count.
    ## if func_.nargs() != call_.nargs():

    #---- Bind named block arguments from Call().
    named_arg_status_l = [expr.interpret(env, storage)
                          for arg_name, expr in self.named_args()]

    # ---- Bind positional block arguments.
    pos_arg_status_l = [ba.interpret(env, storage)
                        for ba in self.positional_args() ]

    def new_call_new_val():
        # ---- Check for any Function()s, and wrap them as callables.
        #       E.g., for the call foo {|| ... }, where foo is a
        #       Python function expecting a callable, the block is
        #       wrapped.
        # Positional args.
        pos_wrapped = []
        arg_index = 0
        for ba, _ in pos_arg_status_l:
            if isinstance(ba, Function):
                pos_wrapped.append(
                    CallableFunction(ba, env, storage, self, arg_index))
            else:
                pos_wrapped.append(ba)
            arg_index += 1

        # Named args.
        named_wrapped = {}
        arg_index = 0
        for (arg_name, _) in self.named_args():
            arg, _ = named_arg_status_l[arg_index]
            if isinstance(arg, Function):
                named_wrapped[arg_name] = (
                    # Note use of arg_name as index for CallableFunction.
                    CallableFunction(arg, env, storage, self, arg_name))
            else:
                named_wrapped[arg_name] = arg
            arg_index += 1


        # ---- Evaluate.
        try:
            if len(named_wrapped) > 0:
                rv = py_func(*pos_wrapped, **named_wrapped)
            else:
                rv = py_func(*pos_wrapped)
            ie_status = storage.ie_.time()

        except Interpret_tail_call:
            raise                   # not reached ?
        except Interpret_return, e:
            rv, ie_status = e.args  # not reached ?

        # Interpretation values.
        storage.id2tree(rv, self)
        storage.set_attributes(self._id,
                               "interp_result", rv, "interp_env", env)

        # Incremental evaluation data.
        storage.ie_.touch(self._id)
        storage.ie_.set_timestamp( (self._id, 'value'), ie_status)

        return rv, ie_status
        # -----------

    # ---- Incremental evaluation check.
    #     Functions with no arguments are usually called for side
    #     effects.
    #     Assuming those do not influence the results of the
    #     program, executing them on every pass is ok (but wasteful).
    #      
    #     Or, by viewing zero-argument calls as constants, they can be
    #     treated like Immediate()s -- and are only called one time.
    #      
    if (len(named_arg_status_l) + len(pos_arg_status_l)) == 0:
        if storage.ie_.is_setup_only(self._id):
            return new_call_new_val()
        else:
            return storage.get_attribute(self._id, "interp_result"),\
                   storage.ie_.get_timestamp(self._id)
    else:
        arg_eval_time = reduce(storage.ie_.newest,
                               [status for _, status in named_arg_status_l] +
                               [status for _, status in pos_arg_status_l])
        if storage.ie_.tree_is_older(self._id, arg_eval_time):
            return new_call_new_val()
        else:
            return storage.get_attribute(self._id, "interp_result"),\
                   storage.ie_.get_timestamp(self._id)
Call._interp_native = _interp_native

def _interp_func(self, block, env, storage):
    if isinstance(block, Function):
        is_new, program, eval_env, arg_env = \
                self.call_function_prep(env, storage, block)

    if isinstance(block, Macro):
        is_new, program, eval_env, arg_env = \
                self.call_macro_prep(env, storage, block)


    # ----------- Data for this block
    # Valid with tail call or without, so this MUST PRECEDE the
    # call to program.interpret(), below.
    #
    if is_new:
        storage.push_attributes(block._id, "interp_clone", program._id)
        storage.set_attributes(self._id,
                               "interp_program", program,
                               "interp_env", arg_env)
        storage.set_attributes(program._id,
                               # lexical information
                               "clone_of", block._id,
                               "interp_env", arg_env,
                               # dynamic information
                               "cloned_by", self._id
                               )

    # ----------- Evaluate
    # Affects: Program.interpret, Function_invo.interpret
    def finish(rv, ie_status):
        # Incremental evaluation check.
        if storage.ie_.tree_is_older(self._id, ie_status):
            # Interpretation values.
            storage.id2tree(rv, self)
            storage.set_attributes(self._id, "interp_result", rv)

            # Incremental evaluation data.
            storage.ie_.touch(self._id)
            storage.ie_.set_timestamp((self._id, 'value'), ie_status)
            return rv, ie_status

        else:
            return storage.get_attribute(self._id, "interp_result"),\
                   storage.ie_.get_timestamp(self._id)

    try:
        rv, ie_status = program.interpret(eval_env, storage)
    except Interpret_tail_call, contin:
        new_tree, _env, _prog_l = contin.args
        _prog_l.append(finish)
        raise
    except Interpret_return, e:
        rv, ie_status = e.args

    return finish(rv, ie_status)
Call._interp_func = _interp_func

def call_function_prep(call_, env, storage, func_):
    # Prepare the block, evaluate arguments, and provide
    # environments.
    # See callable_interpret_prep().

    # Also see Function.interpret, CallableFunction.__call__
    # Verify argument matching.
    if func_.nargs() != call_.nargs():
        raise InterpreterError, \
              ("Argument count mismatch: \n"
               "    %s\n"
               "called with \n"
               "    %s" % (func_.source_string(),
                           call_.source_string()))
    call_names = map(lambda (fst, _): fst, call_.named_args())
    func_names = map(lambda (fst, _): fst, func_.named_block_args())
    for cn in call_names:
        if cn not in func_names:
            raise InterpreterError, \
                  ("Named argument mismatch: \n"
                   "    %s\n"
                   "called with \n"
                   "    %s\n"
                   "Name %s is not in definition." % (func_.source_string(),
                                                      call_.source_string(),
                                                      cn))
    # Incremental evaluation check.
    if storage.ie_.has_clone( call_._id):
        ctab = storage.ie_.clone_table()
        program = ctab[call_._id]
        eval_env, arg_env = ctab[(call_._id, 'envs')]
        is_new = False

    else:
        #---- Turn block into executable.
        # Under incremental evaluation this copy must not be formed if
        # a prior version exists.

        newfunc_ = func_.block_copy(storage)
        program = Program(newfunc_.raw_seq_expr())

        #---- Set up argument environment.
        if func_._binding_name != None:
            arg_env = func_._def_env.new_child(
                program, name = func_._binding_name.py_string())
        else:
            arg_env = func_._def_env.new_child(program, name = "run.arg")

        #---- Bind named block arguments from Function() definition.
        for (arg_name, _) in func_.named_block_args():
            arg_val, status = func_._arg_env.ie_lookup_ptr(arg_name)
            arg_env.bind_ptr(arg_name, arg_val, call_._id)
            arg_env.bind_time_stamp_ptr(arg_name, status, call_._id)

        #---- Bind positional block arguments
        #   Get arguments' names.
        arg_names = func_.positional_block_args()

        ma = Matcher()
        position_index = 0
        for ba in call_.positional_args():
            arg_val, status = ba.interpret(env, storage)
            arg_env.bind_ptr(arg_names[position_index], arg_val, call_._id)
            # Incremental evaluation.
            arg_env.bind_time_stamp_ptr(arg_names[position_index],
                                        status, call_._id)
            position_index += 1

        #---- Bind named block arguments from Call().
        for arg_name, expr in call_.named_args():
            arg_val, status = expr.interpret(env, storage)
            arg_env.bind_ptr(arg_name, arg_val, call_._id)
            # Incremental evaluation.
            arg_env.bind_time_stamp_ptr(arg_name, status, call_._id)


        #---- Set up evaluation environment.
        eval_env = arg_env.new_child(program, name = "run.blck")

        # ---- Finish program.
        # program.setup(block, eval_env, storage)
        program.setup(empty_parent(), eval_env, storage)

        #---------------- later interaction
        cross_reference_trees(storage, func_, newfunc_)
        #----------------

        # Incremental evaluation data.
        ctab = storage.ie_.clone_table()
        ctab[call_._id] = program
        ctab[(call_._id, 'envs')] = eval_env, arg_env
        is_new = True

    return is_new, program, eval_env, arg_env
Call.call_function_prep = call_function_prep

def call_macro_prep(call_, env, storage, mac_):
    # Prepare the block, evaluate arguments, and provide
    # environments.
    if mac_.nargs() != 0:
        raise InterpreterError, \
              ("Macros do not take arguments yet:\n"
               "    %s\n"
               "called with \n"
               "    %s" % (mac_.source_string(),
                           call_.source_string()))

    # Incremental evaluation check.
    if storage.ie_.has_clone( call_._id):
        ctab = storage.ie_.clone_table()
        program = ctab[call_._id]
        eval_env, arg_env = ctab[(call_._id, 'envs')]
        is_new = False

    else:
        #---- Turn block into executable.
        # Under incremental evaluation this copy must not be formed if
        # a prior version exists.

        newmac_ = mac_.block_copy(storage)
        program = Program(newmac_.raw_seq_expr())

        #---- Set up argument environment.
        arg_env = env

        #---- Set up evaluation environment.
        eval_env = env

        # ---- Finish program.
        # program.setup(block, eval_env, storage)
        program.setup(empty_parent(), eval_env, storage)

        #---------------- later interaction
        cross_reference_trees(storage, mac_, newmac_)
        #----------------

        # Incremental evaluation data.
        ctab = storage.ie_.clone_table()
        ctab[call_._id] = program
        ctab[(call_._id, 'envs')] = eval_env, arg_env
        is_new = True

    return is_new, program, eval_env, arg_env
Call.call_macro_prep = call_macro_prep

def interpret(self, env, storage):
    # A 'return' in dml (likely) requires many function exits here in
    # the interpreter.
    # Hence the exception-only exit.
    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    tree = self.deref(0)
    if isinstance(tree, Call):
        # Tail call.
        # -----------
        # The current env is only used by Call.interpret()
        # to get the function body and argument evaluation; the
        # function body is evaluated in separate Env()s, preserving
        # lexical scope.

        def finish(rv, ie_status):
            ### these timestamps are obtained when?  They seem wrong
            ### under manual examination;
            ### As they are not used, make them invalid instead.
            # storage.ie_.set_timestamp( self._id, ie_unusable_time)
            # return

            # Incremental evaluation check.
            if storage.ie_.tree_is_older(self._id, ie_status):
                # Interpretation values.
                storage.id2tree(rv, self)
                storage.set_attributes(self._id,
                                       "interp_result", rv, "interp_env", env)

                # Incremental evaluation data.
                storage.ie_.touch(self._id)
                storage.ie_.set_timestamp( (self._id, 'value'), ie_status)

        _prog_l = [finish]              # ensure new list.
        raise Interpret_tail_call( (tree, env, _prog_l) )
    else:
        # Normal return.
        # -----------
        rv, ie_status = tree.interpret(env, storage)

        # Incremental evaluation check.
        if storage.ie_.tree_is_older(self._id, ie_status):
            # Interpretation values.
            storage.id2tree(rv, self)
            storage.set_attributes(self._id,
                                   "interp_result", rv, "interp_env", env)

            # Incremental evaluation data.
            storage.ie_.touch(self._id)
            storage.ie_.set_timestamp( (self._id, 'value'), ie_status)
            raise Interpret_return( (rv, ie_status) )

        else:
            raise Interpret_return( (
                storage.get_attribute(self._id, "interp_result"),
                storage.ie_.get_timestamp( (self._id, 'value') )
                ) )
Return.interpret = interpret


def interpret(self, env, storage):
    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    # -- Get a (of a.b)
    object, _ = self.deref(0).interpret(env, storage)

    # -- Get b (of a.b)
    #      In a.b, b is only evaluated if it is not a Symbol().
    #      This is done to avoid Symbol lookup in the regular
    #      environments,  as member access really has its own scoping
    #      rules.
    second = self.deref(1)
    if isinstance(second, Symbol):
        mem_name = second.py_string()
    else:
        mem_name, _ = second.interpret(env, storage)
        if not isinstance(mem_name, StringType):
            raise InterpreterError, "In a.b, b is not a name: " + str(mem_name)

    # -- Get (a.b).
    if isinstance(object, DictType):
        binding = dict_ie_lookup_ptr( object, mem_name )
        if binding is None:
            raise InterpreterError, "No member '%s' found." % (mem_name)
        binding, ie_mem_status = binding

    elif isinstance(object, Env):
        # See also symbol.interpret.
        binding = object.ie_lookup_ptr( mem_name )
        if binding is None:
            raise InterpreterError, "No member '%s' found." % (mem_name)
        binding, ie_mem_status = binding

    else:
        # Just evaluate; let exceptions propagate as usual.  Attribute
        # evaluation in Python differs for objects, functions, etc., so let
        # Python do the work.
        binding = eval('object.' + mem_name)

        # Incremental evaluation: external attributes cannot be controlled here.
        # If they are functions, their timestamps are ignored by Call(); if they
        # are values, they must be assumed constant.
        # 
        # Use external time for all member access.  This will access
        # external members repeatedly, so they MUST be constant.
        ie_mem_status = ie_external_time
        
        # Use external time for callable members only?

        # Use self's time stamp.  This will cause pickle failures for
        # callable external types.
        # # ie_mem_status = storage.ie_.get_timestamp(self._id)
        # # if ie_mem_status in [None, ie_setup_time]:
        # #    ie_mem_status = ie_external_time

    # Incremental evaluation check.
    #     Even for an unchanged a.b tree, the a.b value may have
    #     changed. Only the value's time stamp is propagated.
    def new_sym_new_val():
        # Interpretation values.
        storage.id2tree(binding, self)

        # Do not retain references to external objects.
        if ie_mem_status == ie_external_time:
            storage.set_attributes(self._id,
                                   "interp_result", "not_kept",
                                   "interp_env", env)
        else:
            storage.set_attributes(self._id,
                                   "interp_result", binding,
                                   "interp_env", env)

        # Incremental evaluation data.
        storage.ie_.touch(self._id)

        return binding, ie_mem_status

    if storage.ie_.is_setup_only(self._id):
        return new_sym_new_val()

    else:
        if storage.ie_.tree_is_older(self._id, ie_mem_status):
            return new_sym_new_val()
        else:
            return binding, ie_mem_status
Member.interpret = interpret


def interpret(self, env, storage):
    # See also Program.interpret

    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    seq_expr = self.deref(0)
    if len(seq_expr) == 0:
        raise InterpreterError, "Empty Loop"
    else:
        rv_stat_l = [(expr).interpret(env, storage) for expr in seq_expr]

    rv, last_stamp = rv_stat_l[-1]

    # Incremental evaluation check.
    newest_stamp = reduce(storage.ie_.newest,
                          [status for _, status in rv_stat_l])
    if storage.ie_.tree_is_older(self._id, newest_stamp):
        # Interpretation values.
        storage.id2tree(rv, self)
        storage.set_attributes(self._id,
                               "interp_result", rv,
                               "interp_env", env)
        # Incremental evaluation data.
        storage.ie_.touch(self._id)
        storage.ie_.set_timestamp( (self._id, 'value'), last_stamp )

        return rv, last_stamp
    else:
        # ---- Nothing changed.
        return storage.get_attribute(self._id, "interp_result"),  \
               storage.ie_.get_timestamp( (self._id, 'value') )
Loop.interpret = interpret


def interpret(self, env, storage):
    # 'if !condition !true else !false ;
    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    condi, ie_condi = self.deref(0).interpret(env, storage)
    if condi:
        rv, ie_status = self.deref(1).interpret(env, storage)
    else:
        # aNone() evaluates to None, so no special case is needed here.
        rv, ie_status = self.deref(2).interpret(env, storage)

    # Interpretation values.
    storage.id2tree(rv, self)
    storage.set_attributes(self._id,
                           "interp_result", rv,
                           "interp_env", env)

    # Incremental evaluation data.
    #   if's return timestamp is always that of its result; use time
    #   of first interpretation for If() itself.
    if storage.ie_.is_setup_only(self._id):
        storage.ie_.touch(self._id)

    return rv, ie_status
If.interpret = interpret
# 
#***            set.interpret
def interpret(self, env, storage):
    # Also see Set.arg_names

    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    # Get rhs value.
    value, ie_status = self.deref(1).interpret(env, storage)

    # name(s) to assign
    names = self.deref(0)
    # 
    #***            handle_tuples:
    def handle_tuples():
        name_list = names._primary[0]
        if len(name_list) != len(value):
            raise InterpreterError, "Tuple lengths don't match: " + \
                  str(name_list) + str(value)
        else:
            for ii in range(0, len(name_list)):
                nm = name_list[ii]
                #  self._matcher.match_exp_str(nm, '!! name symbol'):
                if not self._matcher.match(nm,
                                           MarkerTyped(String('name'),
                                                       Symbol('symbol'))):
                    raise InterpreterError, \
                          "Set: Invalid argument type: " + str(nm)
                # Add binding to env.
                lhs_symb = self._matcher.get('name')
                env.bind_ptr( lhs_symb.as_index(), value[ii], self._id)
                storage.id2tree(value[ii], nm)

                # Bind the values to the Symbol()s. ### TEST
                storage.set_attributes(lhs_symb._id,
                                       "interp_result", value[ii],
                                       "interp_env", env)

                # Incremental evaluation data.
                storage.ie_.touch(lhs_symb._id)
                env.bind_time_stamp_ptr(lhs_symb.as_index(), ie_status,
                                        self._id)

            storage.set_attributes(self._id,
                                   "interp_result", value,
                                   "interp_env", env)

            # Incremental evaluation data.
            storage.ie_.touch(self._id)
            storage.ie_.set_timestamp( (self._id, 'value'), ie_status )
            return value, ie_status
    #***            handle_single:
    def handle_single():
        #----- Single-name binding.
        # Get binding name.
        if not self._matcher.match(names,
                                   MarkerTyped(String('name'),
                                               Symbol('symbol'))):
            raise InterpreterError, "Set: Invalid first argument type: " + \
                  str(names)
        # Add binding to env.
        lhs_symb = self._matcher.get('name')
        env.bind_ptr( lhs_symb.as_index(), value, self._id)

        # Interpretation values.
        storage.id2tree(value, self)
        storage.set_attributes(self._id,
                               "interp_result", value,
                               "interp_env", env)

        # Bind the value to the Symbol().
        storage.set_attributes(lhs_symb._id,
                               "interp_result", value,
                               "interp_env", env)

        # Incremental evaluation data.
        storage.ie_.touch(lhs_symb._id)
        storage.ie_.touch(self._id)
        storage.ie_.set_timestamp( (self._id, 'value'), ie_status )
        env.bind_time_stamp_ptr(lhs_symb.as_index(), ie_status, self._id)
        return value, ie_status
    #***            ptr_single:
    def ptr_single():
        #----- Single-name binding.
        # Get binding name.
        if not self._matcher.match(names,
                                   MarkerTyped(String('name'),
                                               Symbol('symbol'))):
            raise InterpreterError, "Set: Invalid first argument type: " + \
                  str(names)
        # Add binding to env.
        lhs_symb = self._matcher.get('name')
        env.set_ptr( lhs_symb.as_index(), self._id )
    #***            ptr_tuples:
    def ptr_tuples():
        name_list = names._primary[0]
        if len(name_list) != len(value):
            raise InterpreterError, "Tuple lengths don't match: " + \
                  str(name_list) + str(value)
        else:
            for ii in range(0, len(name_list)):
                nm = name_list[ii]
                if not self._matcher.match(nm,
                                           MarkerTyped(String('name'),
                                                       Symbol('symbol'))):
                    raise InterpreterError, \
                          "Set: Invalid argument type: " + str(nm)
                # Add binding to env.
                lhs_symb = self._matcher.get('name')
                env.set_ptr( lhs_symb.as_index(), self._id )
    #***            body
    # Incremental evaluation check.
    if storage.ie_.tree_is_older(self._id, ie_status):
        #----- Destructuring binding for tuples.
        if isinstance(names, Tuple):
            if isinstance(value, (TupleType, ListType)):
                return handle_tuples()
            else:
                raise InterpreterError, \
                      "Expected tuple return value, got: " + str(value)
        else:
            return handle_single()

    else:
        # Update the name pointer unconditionally, to emulate the
        # effect of overwriting.
        if isinstance(names, Tuple):
            ptr_tuples()
        else:
            ptr_single()
        return storage.get_attribute(self._id, "interp_result"),  \
               storage.ie_.get_timestamp( (self._id, 'value') )
Set.interpret = interpret

def interpret(self, env, storage):
    # See also Program.interpret()

    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    # Incremental evaluation check.
    if storage.ie_.has_env_for(self._id):
        self._eval_env = storage.ie_.env_table()[self._id]

    else:
        # self._eval_env = Env(env.new_env_id(), env, self, storage)
        if self._binding_name != None:
            self._eval_env = env.new_child(
                self, name = self._binding_name.py_string())
        else:
            self._eval_env = env.new_child(self, name = "run.blck")

        # Incremental evaluation data.
        storage.ie_.env_table()[self._id] = self._eval_env

    # Evaluate body.
    seq_expr = self.deref(0)
    rv_stat_l = [(expr).interpret(self._eval_env, storage)
                 for expr in seq_expr]

    # If any bindings changed, self changed.
    if len(seq_expr) == 0:              # ?? use setup, previous time??
        ie_status = storage.ie_.time()
    elif len(seq_expr) == 1:
        _, ie_status = rv_stat_l[0]
    else:
        ie_status = reduce(storage.ie_.newest,
                           [status for _, status in rv_stat_l])

    # Incremental evaluation checks.
    if storage.ie_.tree_is_older(self._id, ie_status):
        # Return value.
        # # rv = self._eval_env._bindings
        rv = self._eval_env

        # Interpretation values.
        storage.id2tree(rv, self)
        storage.set_attributes(self._id,
                               "interp_result", rv,
                               "interp_env", env)

        # Incremental evaluation data.
        storage.ie_.touch(self._id)
        return rv, ie_status

    else:
        return storage.get_attribute(self._id, "interp_result"),  \
               storage.ie_.get_timestamp(self._id)
Map.interpret = interpret


def interpret(self, env, storage):
    # See also Program.interpret()

    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    # Incremental evaluation check.
    if storage.ie_.has_env_for(self._id):
        self._eval_env = storage.ie_.env_table()[self._id]
    else:
        # self._eval_env = Env(env.new_env_id(), env, self, storage)
        if self._binding_name != None:
            self._eval_env = env.new_child(
                self, name = self._binding_name.py_string())
        else:
            self._eval_env = env.new_child(self, name = "run.blck")

        # Incremental evaluation data.
        storage.ie_.env_table()[self._id] = self._eval_env

    # Form subdirectory.
    subdir = self._eval_env.into_directory() 

    # Evaluate body.
    seq_expr = self.deref(0)
    try:
        rv_stat_l = [(expr).interpret(self._eval_env, storage)
                     for expr in seq_expr]
    except:
        self._eval_env.outof_directory()
        raise
    self._eval_env.outof_directory()

    # If any bindings changed, self changed.
    if len(seq_expr) == 0:              # ?? use setup, previous time??
        ie_status = storage.ie_.time()
    elif len(seq_expr) == 1:
        _, ie_status = rv_stat_l[0]
    else:
        ie_status = reduce(storage.ie_.newest,
                           [status for _, status in rv_stat_l])

    # Incremental evaluation checks.
    if storage.ie_.tree_is_older(self._id, ie_status):
        # Return value.
        rv = self._eval_env

        # Interpretation values.
        storage.id2tree(rv, self)
        storage.set_attributes(self._id,
                               "interp_result", rv,
                               "interp_env", env)

        # Incremental evaluation data.
        storage.ie_.touch(self._id)
        return rv, ie_status

    else:
        return storage.get_attribute(self._id, "interp_result"),  \
               storage.ie_.get_timestamp(self._id)
Subdir.interpret = interpret

def l3_dirname(self):
    return self._eval_env.l3_dirname()
Subdir.l3_dirname = l3_dirname


def t_l_interpret(self, env, storage, converter = list):
    # Tuple and list interpretation common parts.

    # Also see Tuple.interpret, aList.interpret
    val_status_l = [ child.interpret(env, storage)
                     for child in self.deref(0) ]

    # Empty list
    if val_status_l == []:
        rv_l = converter([])
        stat_l = []

        # Incremental evaluation check.
        if storage.ie_.is_setup_only(self._id):
            # Interpretation values.
            storage.id2tree(rv_l, self)
            storage.set_attributes(self._id,
                                   "interp_result", rv_l,
                                   "interp_env", env)
            # Incremental evaluation data.
            ie_status = storage.ie_.touch(self._id)
            storage.ie_.set_timestamp( (self._id, 'value'), ie_status )
            return rv_l, ie_status

        else:
            # For Immediates(), the tree and value are one --
            #     the tree_is_older() test is replaced by the previous
            #     if cases
            return (storage.get_attribute(self._id, "interp_result"),
                    storage.ie_.get_timestamp((self._id, 'value')) )

    # Non-empty list.
    else:
        rv_l = converter([rv for rv, stat in val_status_l])
        stat_l = [stat for rv, stat in val_status_l]

        # Find "most needy" status and propagate that.
        ie_status = reduce(storage.ie_.newest, stat_l)

        # Incremental evaluation check.
        # # print "t_l_interpret"
        if (storage.ie_.tree_is_older(self._id, ie_status)):
            # Interpretation values.
            storage.id2tree(rv_l, self)
            storage.set_attributes(self._id,
                                   "interp_result", rv_l,
                                   "interp_env", env)

            # Incremental evaluation data.
            storage.ie_.touch(self._id)
            storage.ie_.set_timestamp( (self._id, 'value'), ie_status )
            return rv_l, ie_status

        else:
            return storage.get_attribute(self._id, "interp_result"),  \
                   storage.ie_.get_timestamp( (self._id, 'value') )

def interpret(self, env, storage):
    return t_l_interpret(self, env, storage, converter = list)
List.interpret = interpret

def interpret(self, env, storage):
    return t_l_interpret(self, env, storage, converter = tuple)
Tuple.interpret = interpret

#
#**        Immediate types
def interpret(self, env, storage):
    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    rv = self._primary[0]

    def new_sym_new_val():
        # Interpretation values.
        storage.id2tree(rv, self)
        storage.set_attributes(self._id,
                               "interp_result", rv,
                               "interp_env", env)
        # Incremental evaluation data.
        ie_status = storage.ie_.touch(self._id)
        return rv, ie_status

    # Incremental evaluation check.
    if storage.ie_.is_setup_only(self._id):
        return new_sym_new_val()

    else:
        # For Immediates(), the tree and value are one --
        #     the tree_is_older() test is replaced by the previous
        #     if cases
        return ( storage.get_attribute(self._id, "interp_result"),
                 storage.ie_.get_timestamp(self._id) )
Immediate.interpret = interpret
aNone.interpret = interpret
Native.interpret = interpret

# modified tree check
#     if storage.ie_.is_replacement(self._id):
#         o_id, o_status = storage.ie_.original_for(self._id)
#         if storage.load(o_id).eql(self):
#             # This Immediate() is new, but its value is unchanged.
#             # Use the original's meta data.
#             storage.ie_.set_timestamp( self._id, o_status )
#             return (storage.get_attribute(o_id, "interp_result"),
#                     o_status)
#         else:
#             bind, status = new_sym_new_val()
#             storage.ie_.not_replacement(self._id)
#             return bind, status


def interpret(self, env, storage):
    # Also see Set.interpret().

    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    # Incremental evaluation checks
    #
    # symbol timestamp
    #   replaced | setup      | value
    #
    # binding timestamp
    #   any      | any        | value
    # ---------------------------------
    # interpret, | interpret, | age
    # stamp      | stamp      | decides

    binding = env.ie_lookup_ptr( self.as_index() )
    if binding is None:
        # Unbound symbols may return themselves in the future...
        raise UnboundSymbol("No binding found for: " + self.as_index())
    binding, ie_status = binding

    def new_sym_new_val():
        # Also see BinaryOper, UnaryOper.

        # Interpretation values.
        storage.id2tree(binding, self)

        # Do not retain references to external objects.
        if ie_status == ie_external_time:
            storage.set_attributes(self._id,
                                   "interp_result", "not_kept",
                                   "interp_env", env)
        else:
            storage.set_attributes(self._id,
                                   "interp_result", binding,
                                   "interp_env", env)

        # Incremental evaluation data.
        storage.ie_.touch(self._id)

        return binding, ie_status

    if storage.ie_.is_setup_only(self._id):
        return new_sym_new_val()

    else:
        if storage.ie_.tree_is_older(self._id, ie_status):
            return new_sym_new_val()
        else:
            return binding, ie_status

Symbol.interpret = interpret

# modified tree check
#     if storage.ie_.is_replacement(self._id):
#         o_id, o_stamp = storage.ie_.original_for(self._id)
#         if storage.load(o_id).eql(self):
#             # This symbol is new, but its value is unchanged.
#             # ---------------------------------
#             storage.ie_.touch(self._id)
#             # ?? Symbol is newer than binding -- see Set.interpret()
#             # and below.
#             # This works correctly with tree_is_older().
#             storage.ie_.set_timestamp( (self._id, 'value'), o_stamp )
#             return storage.get_attribute(o_id, "interp_result"), o_stamp

#         else:
#             bind, status = new_sym_new_val()
#             storage.ie_.not_replacement(self._id)
#             return bind, status



def interpret(self, env, storage):
    # See also Program.interpret()

    if self._pre_interp_hook:
        self._pre_interp_hook(self, env, storage)

    # Return last expr value.
    seq_expr = self
    if len(seq_expr) == 0:
        # 
        # Imitate aNone.interpret()
        # 
        rv = None
        def new_sym_new_val():
            # Interpretation values.
            storage.id2tree(rv, self)
            storage.set_attributes(self._id,
                                   "interp_result", rv,
                                   "interp_env", env)
            # Incremental evaluation data.
            ie_status = storage.ie_.touch(self._id)
            return rv, ie_status

        # Incremental evaluation check.
        if storage.ie_.is_setup_only(self._id):
            return new_sym_new_val()
        else:
            return ( storage.get_attribute(self._id, "interp_result"),
                     storage.ie_.get_timestamp(self._id) )

    # 
    # List with content
    # 
    rv_stat_l = [(expr).interpret(env, storage) for expr in seq_expr]

    # This causes infinite recursions without __deepcopy__; but
    # __deepcopy__ of a list subclass works oddly.
    # # self._eval_env = env
    rv, last_stamp = rv_stat_l[-1]

    # Incremental evaluation check.
    newest_stamp = reduce(storage.ie_.newest,
                          [status for _, status in rv_stat_l])
    if storage.ie_.tree_is_older(self._id, newest_stamp):
        # Interpretation values.
        storage.id2tree(rv, self)
        storage.set_attributes(self._id,
                               "interp_result", rv,
                               "interp_env", env)
        # Incremental evaluation data.
        storage.ie_.touch(self._id)
        storage.ie_.set_timestamp( (self._id, 'value'), last_stamp )

        return rv, last_stamp
    else:
        # ---- Nothing changed.
        return storage.get_attribute(self._id, "interp_result"),  \
               storage.ie_.get_timestamp( (self._id, 'value') )
aList.interpret = interpret

#*    post-execution data viewing
# Support for retrieving "interesting" data.
#**     environments
def directory(self, dyn_tree):
    # Convert get_dynamic_subtrees()'s output (or compatible) into 
    # a l3 expression for display.
    # todo: FIXME:  add a real heading/content element, not "foo"(bar)
    # 
    dir, content = dyn_tree
    argl = []
    for itm in content:
        if isinstance(itm, StringType):
            argl.append(Symbol(itm))
        elif isinstance(itm, TupleType):
            argl.append(directory(self, itm))

    rv = List(aList(argl))
    rv.set_label(String(dir))
    return rv
Program.directory = directory

def directory_l3(self):
    # Produce a post-run directory containing only l3 named data.
    # This version works only for the topmost environment.
    # 
    
    # Get list of desirable names.
    (_, list_1) = self._block_env.get_tree()
    top_names = filter(lambda xx: isinstance(xx, StringType), list_1)
    
    # Compare against names present.
    (nm, list_2) = self._eval_env.get_dynamic_subtrees()
    def tuple_or_top(xx):
        if isinstance(xx, TupleType) or (xx in top_names):
            return True
        return False
    list_3 = filter(tuple_or_top, list_2)

    # Finish.
    return self.directory( (nm, list_3) )
Program.directory_l3 = directory_l3

# 
#**     python -> l3 conversion
def val2ast(val, file_contents = False, visited = None):
    '''
    Produce a raw astType from a Python value `val` (including list
    and dict).  This is analogous to the parser; the astType is not
    .setup().

    Unrecognized types are wrapped as a Native().

    l3 types are returned unchanged.

    Recursion is detected and recursive structures are returned as
    `recurse_to_ID` strings. 


    ARGS:
        file_contents   If True, return file reference instead of name.

    '''
    if visited is None:
        visited = {}

    # Already an l3 type?
    if  isinstance(val, (astType, aNone, aList, Native)):
        return val

    elif isinstance(val, Env):
        def filter_env():
            """ Return some bindings in this environment as a l3 Map.
            Only bindings of user interest are collected.
            """

            # Children.
            for child in val._children:
                if child._name in ["skel.arg", "skel.blck", "anonymous"]:
                    continue
                yield (child._name, "sub-env")

            # Local entries.
            for ky, vl in val.all_bindings().iteritems():
                if isinstance(ky, TupleType):
                    if len(ky) == 2 and ky[1] == 'ptr':
                        name, _ = ky 
                        yield (name, val.lookup_ptr_1(name))
                    else:
                        continue

        if visited.has_key(id(val)):
            return Symbol("recurse_to_" + str(id(val)))

        visited[id(val)] = 1

        return Map(aList([Set(val2ast(key, visited = visited,
                                      file_contents = file_contents), 
                              val2ast(entry, visited = visited,
                                      file_contents = file_contents)) 
                          for key, entry in filter_env()]))

    # A known python type?
    elif isinstance(val, (IntType, LongType)):   return Int(int(val))

    elif isinstance(val, FloatType):  return Float(val)

    elif isinstance(val, StringType):
        if file_contents:
            return Native(FilepathString(val))
        else:
            return FilepathString(val)

    elif isinstance(val, ListType):
        if visited.has_key(id(val)):
            return Symbol("recurse_to_" + str(id(val)))

        visited[id(val)] = 1

        return List(aList([val2ast(entry, visited = visited,
                                   file_contents = file_contents)
                           for entry in val])) 

    elif isinstance(val, TupleType):
        if visited.has_key(id(val)):
            return Symbol("recurse_to_" + str(id(val)))

        visited[id(val)] = 1

        return Tuple(aList([val2ast(entry, visited = visited,
                                    file_contents = file_contents) 
                            for entry in val]))

    elif isinstance(val, DictType):
        if visited.has_key(id(val)):
            return Symbol("recurse_to_" + str(id(val)))

        visited[id(val)] = 1

        return Map(aList([  Set(val2ast(key, visited = visited,
                                        file_contents = file_contents), 
                                val2ast(entry, visited = visited,
                                        file_contents = file_contents))
                            for key, entry in val.iteritems()]))
    # All others.
    else:
        return Native(val)

# 
#**     value retrieval
def get_values_list(self, w_):
    ''' Form and return ((id, value) list).
    The `id` is the expression producing `value`; for multi-valued
    expressions, the clone id is used.
    '''
    st = w_.state_.storage
    sid = self._id

    # Dynamic id(s).
    clone_l = st.get_attribute(sid, "interp_clone")
    if clone_l:
        # todo: unfiltered, this list could be huge. Limit size?  Or provide
        # iterator instead.
        val_l = []
        for cid in clone_l:
            val_l += st.load(cid).get_values_list(w_)
        return val_l
    else:
        # Toplevel/final id.
        return [ (sid, st.get_attribute(sid, 'interp_result')) ]
astType.get_values_list = get_values_list
aList.get_values_list = get_values_list

# 
#**     dirpath (disk location)
def dirpath(self, w_):
    tw = TreeWork(w_.state_.storage)
    paths = [par.l3_dirname()    for par in tw.find_all_parents(self, Subdir)]
    paths.reverse()
    return "/".join(paths)
astType.dirpath = dirpath
aList.dirpath = dirpath

        
#
#**     emphasis (special item properties)
# (l_emph : string)
# Emphasis may be used to distinguish special items.
#       l_emph should be a logical description, e.g. "filelist"
#       This member is only present when used.
# # self.l_emph = None              

def set_emphasis(self, emph):
    ''' Set emphasis for this node to `emph` 
    Emphasis may be used to distinguish special items.
    emph should be a logical description, e.g. "filelist".

    Any emphasis added here must have a corresponding entry in the
    deco.emph_color resource.
    '''
    self.l_emph = emph
Native.set_emphasis = set_emphasis
astType.set_emphasis = set_emphasis
aList.set_emphasis = set_emphasis
aNone.set_emphasis = set_emphasis

def get_emphasis(self):
    return self.__dict__.get('l_emph', None)
Native.get_emphasis = get_emphasis
astType.get_emphasis = get_emphasis
aList.get_emphasis = get_emphasis
aNone.get_emphasis = get_emphasis


#* tree attributes
# Mechanism for adding generic attributes to astType trees, without
# polluting the instance's dict, and with lexically obvious syntax:
#   foo.setthe(size = 10)
# [ introduced after set_emphasis / get_emphasis]
#   
# Some attributes must be set before .setup(), including those that
# need to be attached at tree-building time.
# 
def setthe(self, **dct):
    # Attach key = value pairs to self.  Using None as `value` is
    # meaningless. 
    self._attributes.update(dct)
    return self
astType.setthe = setthe
aList.setthe = setthe
aNone.setthe = setthe
Native.setthe = setthe

def getthe(self, key):
    # Return the value attached to `key`, or None.
    return self._attributes.get(key, None)
astType.getthe = getthe
aList.getthe = getthe
aNone.getthe = getthe
Native.getthe = getthe



#*    Data flow -- .data_dag()
class DataDagError(exceptions.Exception):
    def __init__(self, args=None):
        self.args = args

class ReturnBranch:
    # No-value indicator for back-propagation of Return() effect.
    pass

def __init__(self, gid):
    self._from_gid = [gid]
ReturnBranch.__init__ = __init__

def merge(self, other):
    # Combine targets.
    self._from_gid = self._from_gid + other._from_gid
    return self
ReturnBranch.merge = merge

#
#**        Functions for dicts of lists
# key -> val list

# push val onto the end of the dict's key entry.
def dl_push(dict, key, val):
    if dict.has_key(key):
        dict[key].append(val)
    else:
        dict[key] = [val]
    return dict

# return the most recently pushed value.
def dl_peek(dict, key):
    if dict.has_key(key):
        return dict[key][-1]
    else:
        raise Error, "No values."

def dl_items(dict_):
    for k, val_l in dict_.items():
        for v1 in val_l:
            yield k, v1

#
#**        misc fns.
def equal_leading(list_, tuple_):
    # Return true if  the leading entries of list_ and tuple_ are equal.
    for lv, rv in zip(list_, tuple_):
        if lv != rv:
            return 0
    return 1
#
#**        Dag handling class
class astDag:
    pass

def __init__(self, name, tree_id, starting_id):
    # tree_ids may map to several graph_ids; graph_id's are unique.
    #
    self._new_id = starting_id    # make ids easier to (string) search

    # tree_id's are usually the int (or long) associated with a tree
    # node.  Also possible:
    #   tree_id ::= int | (ident, name, real_tree_id)
    #
    # where ident is a logical identifier, e.g. "subgraph", and
    # real_tree_id is another int.
    self._graphid_2_treeid = {}         # graph_id -> tree_id
    self._treeid_2_graphid= {}          # tree_id  -> (graph_id list)
    self._nodes = {}                    # graph_id -> (attribute list)
    # where
    #   attribute ::= <(key, value), >*

    # self._edges = {}                    # graph_id -> graph_id list

    # _edges structure
    #    [logical structure]
    #       (node -> node) tuple -> attributes (via dict)
    #    [physical structure]
    #       (graph_id, graph_id) -> [ (key, val), * ]
    self._edges = {}
    self._new_id += 1
    self._graph_id = self._new_id

    # By including self in the _graph_stack, every node belongs to
    # a subgraph.
    #     graph       ::= [ graph_ident (, node)*]
    #     graph_ident ::= ( graph_id, name, tree_id )
    #     node        ::= id | graph
    self._graph_stack = []
    self._graph_now = [(self._graph_id, name, tree_id)
                       ]                # The above nested graph type.
    # graph_ids of the enclosing subgraphs
    self._subgraph_stack = []           # graph_id list
    self._subg_stack_of = {}            # graph_id -> graph_id tuple

    #
    # self._subgraph_nodes = {}           # (sub)graph_id -> graph_id list
    #
    self._call_stack = []               # For .data_dag() use
    #
    self._unique_names = {}   # nodes unique for a given external name

    # Function() / Return() interaction ids
    self._block_stack = []              # graph_id list

astDag.__init__ = __init__

#   s u b g r a p h s
#
# The subgraph is only a logical grouping; nodes in subgraphs are
# still global.

# These subgraphs are tracked using explicit start/end calls to get
# internal context switch.  Internally, just use stacks.
def start_subgraph(self, name, tree_id, attributes = []):
    # graph stack.
    self._graph_stack.append(self._graph_now)
    self._graph_now = []

    # content.
    self._new_id += 1
    self._graph_now.append( (self._new_id, name, tree_id) )
    if 0:
        # Physical node
        self._track(self._new_id, ("subgraph", name, tree_id),
                    attributes)
    self._subgraph_stack.append(self._new_id)
    return self._new_id
astDag.start_subgraph = start_subgraph

def end_subgraph(self):
    # graph stack.
    self._graph_stack[-1].append(self._graph_now)
    self._graph_now = self._graph_stack[-1]
    del self._graph_stack[-1]
    del self._subgraph_stack[-1]
astDag.end_subgraph = end_subgraph

def get_graph_id(self, tree_id):
    if self._treeid_2_graphid.has_key(tree_id):
        all = self._treeid_2_graphid.get(tree_id)
        if len(all) > 1:
            print "warning: multiple graph ids. Using most recent."
        return dl_peek(self._treeid_2_graphid, tree_id)
    else:
        return None
astDag.get_graph_id = get_graph_id

def _track(self, graph_id, id, attributes):
    # Add a new node with graph_id, and
    # track associations between graph_id and incoming id.
    self._nodes[graph_id] = attributes
    self._graphid_2_treeid[graph_id] = id
    dl_push(self._treeid_2_graphid, id, graph_id)

    # Subgraph tracking.
    self._graph_now.append(graph_id)
    self._subg_stack_of[graph_id] = tuple(self._subgraph_stack) # immutable
astDag._track = _track

def add_node(self, id, attributes = []):
    # id is the node's external identifier; a new node with unique
    # internal identifier is created on every call.
    # The internal identifier is returned.
    self._new_id += 1
    self._track(self._new_id, id, attributes)
    return self._new_id
astDag.add_node = add_node

def add_unique_node(self, name, attributes = []):
    # For a given name, always return the same graph_id.
    # name is the node's external and internal identifier.
    if self._unique_names.has_key(name):
        return self._unique_names[name]
    else:
        graph_id = self.add_node(name, attributes)
        self._unique_names[name] = graph_id
        return graph_id
astDag.add_unique_node = add_unique_node

def add_locally_unique_node(self, tree_id, attributes = []):
    # Within the current _subgraph_id and
    # for a given tree_id, always return the same graph_id .
    # tree_id is the node's external and internal identifier.

    graph_id = self.get_graph_id(tree_id)
    if graph_id == None:
        return self.add_node(tree_id, attributes)
    else:
        # In this or enclosing graph.
        if equal_leading(self._subgraph_stack,
                         self._subg_stack_of[graph_id]):
            return graph_id
        else:
            return self.add_node(tree_id, attributes)
astDag.add_locally_unique_node = add_locally_unique_node

def add_edge(self, id1, id2, attributes = []):
    # Usually, edges are  child -> parent
    if self._nodes.has_key(id1) and self._nodes.has_key(id2):
        self._edges[(id1, id2)] = attributes
    else:
        raise DataDagError, "Edges must use existing nodes."
    return None
astDag.add_edge = add_edge

def sanity_check(self):
    if self._graph_stack != []:
        raise DataDagError, "Unbalanced start_subgraph/end_subgraph() use."
astDag.sanity_check = sanity_check

def dump_dot(self, file):
    # Header.
    ##labeling
    file.write("""
    /* -*- c -*-
       Generated by astDag.dump_dot() */
    digraph graph0 {
        page = "8.5,11.0";            /* size of single physical page */
        size="7.5,10.0";              /* graph size */
        /* rotate=90; */
        ratio=fill;
        /* rankdir=LR; */
        fontpath="%(SPXROOT)s/l3gui/fonts";
        node [shape=box,fontname="Courier", fontsize=12,
              width="0.1cm",height="0.1cm", /* snug fit around labels */
              ];
        edge [fontname="Courier", fontsize=12] ;
        edge [arrowsize=0.71];
        fontsize=12;
        fontname="Courier";

        """ % os.environ)

    subgraph_color = ['white', 'beige']

    def dump_subgraph(graph_now, use_beige):
        # Use graph_now to put nodes into the appropriate subgraphs.
        (gid, name, _) = graph_now[0]

        if " " in name:
            raise Exception, """dump_dot: Received name containing spaces.
            %s
            Internal error.\n""" % name

        file.write(""" /* Subgraph header gid=%d */
        subgraph cluster_%s_%d {
            label = "%s";
            bgcolor= %s;
        """ % (gid,
               name, gid,
               name,
               subgraph_color[use_beige]))

        # When using the block itself as return value.
        # file.write(""" /* Subgraph id, to provide a real node for dot's use. */
        # %d [style=invis];\n """ % (gid))

        # Subgraph nodes
        for gnode in graph_now[1:]:
            if isinstance(gnode, ListType):
                dump_subgraph(gnode, not use_beige)
            else:
                file.write("%s [" % gnode) # Node.
                for key, val in self._nodes[gnode]:
                    file.write('%s = "%s",' % (key, val))
                file.write("];\n")

        # Subgraph trailer.
        file.write(""" }\n """)
    dump_subgraph(self._graph_now, 0)

    # Use _edges to connect nodes.
    for (src, dest), att_l in self._edges.items():
        file.write(""" %d -> %d [""" % (src, dest))
        for key, val in att_l:
            file.write('%s = "%s",' % (key, val))
        file.write("""];\n""" )
    # Trailer.
    file.write("}\n")
    file.flush()

    return file
astDag.dump_dot = dump_dot


def dump_dot_colored(self, file):
    # Use the graph_ids as colors.
    # Header.
    ##labeling
    file.write("""
    /* -*- c -*-
       Generated by astDag.dump_dot() */
    digraph graph0 {
        truecolor=1;                  /* needed for identification */
        page = "8.5,11.0";            /* size of single physical page */
        size="7.5,10.0";              /* graph size */
        /* rotate=90; */
        ratio=fill;
        /* rankdir=LR; */
        fontpath="%(SPXROOT)s/l3gui/fonts";
        node [shape=box,fontname="Courier", fontsize=12,
              width="0.1cm",height="0.1cm", /* snug fit around labels */
              ];
        edge [fontname="Courier", fontsize=12] ;
        edge [arrowsize=0.71];
        fontsize=12;
        fontname="Courier";

        """ % os.environ)

    def dump_subgraph(graph_now):
        # Use _graph_now to put nodes into the appropriate subgraphs.
        (gid, name, _) = graph_now[0]

        if " " in name:
            raise Exception, \
                  """dump_dot_colored: Received name containing spaces.
            %s
            Internal error.\n""" % name

        file.write(""" /* Subgraph header gid=%d */
        subgraph cluster_%s_%d {
            label = "%s";
            bgcolor= "#%.6x";
        """ % (gid,                #"
                   name, gid,
                   name,
                   gid))
        # coloring

        # When using the block itself as return value.
        # file.write(""" /* Subgraph id, to provide a real node for dot's use. */
        # %d [style=invis];\n """ % (gid))

        # Subgraph nodes
        for gnode in graph_now[1:]:
            if isinstance(gnode, ListType):
                dump_subgraph(gnode)
            else:
                file.write("%s [" % gnode) # Node.
                for key, val in self._nodes[gnode]:
                    file.write('%s = "%s",' % (key, val))
                # coloring
                file.write('style=filled, fillcolor= "#%.6x",' % gnode +
                           'fontcolor="#%.6x"' % gnode);
                file.write("];\n")

        # Subgraph trailer.
        file.write(""" }\n """)
    dump_subgraph(self._graph_now)

    # Use _edges to connect nodes.
    for (src, dest), att_l in self._edges.items():
        file.write(""" %d -> %d [""" % (src, dest))
        for key, val in att_l:
            file.write('%s = "%s",' % (key, val))
        # coloring
        file.write('color= "#%.6x",' % (src*dest,));
        file.write("""];\n""" )
    # Trailer.
    file.write("}\n")
    file.flush()

    return file
astDag.dump_dot_colored = dump_dot_colored

#
#**        Main external entry points.
#
#***            Form initial data_dag, containing ALL nodes.
def data_dag_start(self, name, storage, starting_id):
    # name:  name for the output graph
    # starting_id: starting id for the output graph nodes
    # Note:
    #       Run only *before* interpretation --
    #       not very flexible wrt. incremental evaluation.
    dagraph = astDag(name, self._id, starting_id)
    self.data_dag(self._block_env, dagraph, storage)
    dagraph.sanity_check()
    return dagraph
Program.data_dag_start = data_dag_start

#
#***            Form viewer data_dag, containing only names and subgraphs.
def get_reduced_dag(self):
    new_ = deepcopy(self)

    nodes, edges = new_._get_reduced_dag()

    new_._nodes = nodes
    new_._edges = edges

    def prune_graph(G):
        ngn = []
        for el in G:
            if isinstance(el, TupleType): # graph_ident
                ngn.append(el)

            elif isinstance(el, ListType): # graph
                ngn.append(prune_graph(el))

            elif isinstance(el, IntType): # node
                if nodes.has_key(el):
                    ngn.append(el)
            else:
                raise DataDagError, "Invalid subgraph entry."
        return ngn

    new_._graph_now = prune_graph(new_._graph_now)

    # Sufficient for dump_dot; others?
    return new_
astDag.get_reduced_dag = get_reduced_dag


#
#**        refiner
def _get_reduced_dag(self):
    #
    # Given the full data flow dag, find those nodes and edges
    # involving actual bound names.
    #
    # This prunes function calls and Immediate()s.

    # Find labeled node connections
    named_nodes = [key
                   for key, attr_l in self._nodes.iteritems()
                   if not (('label', '') in attr_l)]

    # Get edges in nested dict format.
    #   edges = { src : {dst1 : , dst2 : , }, ...}
    edges = {}
    for s in self._nodes.iterkeys(): # cover nodes w/o outgoing edges
        edges[s] = {}
    for s, d in self._edges.iterkeys():
        edges[s][d] = 1

    # Find all nodes connected to the start_node node by a path not crossing
    # other named nodes.
    def indirect_to(edges, start_node, distance, neighbors_of):
        # Skip leaves.
        if edges.has_key(neighbors_of):
            for neighbor in edges[neighbors_of].keys():
                edges[start_node][neighbor] = distance
                # Paths that require CROSSING of a named_node are NOT wanted.
                if neighbor in named_nodes:
                    continue
                else:
                    indirect_to(edges, start_node, distance + 1, neighbor)

    all_edges = deepcopy(edges)
    for start in named_nodes:
        indirect_to(all_edges, start, 1, start)

    # Get only name -> name edges.
    relevant_edges = {}
    for start in named_nodes:
        for dest in named_nodes:
            if start == dest: continue
            if all_edges[start].has_key(dest):
                relevant_edges[(start, dest)] = []

    # Use self._nodes format.
    relevant_nodes = dict([(ii, self._nodes[ii]) for ii in named_nodes])

    return  relevant_nodes, relevant_edges
astDag._get_reduced_dag = _get_reduced_dag


# Notes
# ================
# This grouping is by function, not class.
# Traversal is normal order, left-to-right.
# Relevant ids are returned by children; edges are formed by parents.

# valid graph_id s are None and the return values from .new_subgraph()
# and .add_*node()

# For at least Symbol(), Function() and Call(), single-type
# dispatch (on class) is inadequate for retrieving nested information.
# Hence, the nested if's, with recursive calls, below.

# These effectively implement
# multiple passes (one per nesting level).  This
# - allows viewing of increasingly more detailed graphs
# - simplifies the code
# - separates the block argument port handling (for the drawn graph)

#
#**        data_dag() member, nested types
def data_dag(self, env, dagraph, storage):
    raise InterfaceOnly("%s has no .data_dag() member" % self)
Nested.data_dag = data_dag

#
#***            introducing their own Env()s
def data_dag(self, env, dagraph, storage):
    sub_env = self._block_env
    seq_expr = self.deref(0)
    if len(seq_expr) == 0:
        raise DataDagError, "Empty program"
    else:
        for expr in seq_expr:
            rv = (expr).data_dag(sub_env, dagraph, storage)
            if isinstance(rv, ReturnBranch):# Rest is unreachable.
                break
    return rv
Program.data_dag = data_dag

def data_dag(self, env, dagraph, storage):
    # A function makes no data contribution unless executed, and every
    # distinct invocation provides its own expansion.
    return None
Function.data_dag = data_dag

def data_dag(self, env, dagraph, storage):
    # An Inline makes no data contribution until executed;
    # it is not parsed so only examination of the dictionary can show
    # what it contributed, and there is no simple way to know what it
    # read. 
    return None
Inline.data_dag = data_dag

def data_dag(self, env, dagraph, storage):
    seq_expr = self.deref(0)
    sub_env = self._block_env

    # Start subgraph.
    if self._binding_name != None:
        sub_graph_id = dagraph.start_subgraph(
            self._binding_name.py_string(), self._id)
    else:
        sub_graph_id = dagraph.start_subgraph("anonymous_map", self._id)

    # Fill subgraph.
    for expr in seq_expr:
        rv = expr.data_dag(sub_env, dagraph, storage)
        if isinstance(rv, ReturnBranch):# Rest is unreachable.
            break

    rv = dagraph.add_locally_unique_node(
        self._id,
        attributes = [('label', "ENV-%d" % self._id ),
                      ('shape', "text"),
                      ('color', 'black'),
                      # ('fillcolor', 'yellow'),
                      ])

    # finish subgraph
    dagraph.end_subgraph()

    return rv
    # return None       # original
    # return sub_graph_id   # subgraphs aren't nodes.
Map.data_dag = data_dag

#
#***            using given Env()s
def data_dag(self, env, dagraph, storage):
    # Find block.
    operator = self.deref(0)
    if isinstance(operator, (Symbol, Member)):
        bbinding = operator.data_dag_lookup(env)

        if isinstance(bbinding, Function):
            if bbinding._id in dagraph._call_stack:
                # Recursive call, use the name directly.
                ##labeling
                return self.data_dag_name(
                    env, dagraph, storage, operator,
                    [ ('label', operator.py_string()),
                      ('shape', "hexagon"),
                      ('color', 'black'),
                      ])
                ## old:
                ## return operator.data_dag(env, dagraph, storage)
            else:
                # Use the looked-up Function()
                dagraph._call_stack.append(bbinding._id)
                rv = self.data_dag_block(env, dagraph, storage, bbinding)
                del dagraph._call_stack[-1]
                return rv

        elif callable(bbinding) or (bbinding == "unknown_fn"):
            ##labeling
            if 1:                       # full name of functions
                return self.data_dag_name(
                    env, dagraph, storage, operator,
                    [('label', operator.py_string()),
                     ('shape', 'ellipse'),
                     ('color', 'red'),
                     ])
            else:                       # functions as circles
                return self.data_dag_name(
                    env, dagraph, storage, operator,
                    [('label', ""),
                     ('shape', 'circle'),
                     ('color', 'black'),
                     ('style', 'filled'),
                     ('width', '0.15cm'),
                     ('fixedsize', 'true')])
                

        elif bbinding == "unknown_member":
            # Binding is unclear.  Treat a.b(c) as b(a,c), without
            # attempting to lookup b.

            # Form new tree.
            ma = Matcher()
            # Pattern from reader.parse('! a . ! b( !c ) ') with mods
            ma.match(self,
                     Call(
                Member(Marker('a'), Marker('b')),
                Marker('c')))           # c == aList([])

            # Tree from reader.parse('b(a,c) ')
            # The original tree is not to be touched; as python
            # doesn't have true lists,  need a deepcopy here.
            new_args = deepcopy(ma['c']) # [ ... ]
            copy_attribute(ma['c'], new_args, '_id')
            new_args.insert(0, ma['a']) # [a, ...]
            tree = Call(ma['b'], new_args)
            return tree.data_dag(env, dagraph, storage)

        else:
            raise DataDagError, \
                  ("Line: %d:col %d: Unknown static binding. Internal error."
                   % operator._first_char)

    elif isinstance(operator, Function):
        return self.data_dag_block(env, dagraph, storage, operator)

    else:
        raise DataDagError, "Expected Function(), got " + str(operator)
Call.data_dag = data_dag

def data_dag_name(self, env, dagraph, storage, operator, attrib_list):
    # Get this invocation's arguments' dags. [a,b from f(a,b)]
    arg_seq = self.deref(1)
    arg_dags = []
    for expr in arg_seq:
        arg_dags.append(expr.data_dag(env, dagraph, storage))

    # Bind invocation arguments' dags to invoked function's name
    func_node = dagraph.add_node( operator._id, attributes = attrib_list)
    for ii in arg_dags:
        dagraph.add_edge(ii, func_node)
    return func_node
Call.data_dag_name = data_dag_name

def data_dag_block_body(env, dagraph, storage, block):
    # Get block dag via Program()
    # This includes references to argument names in _block_env, but no
    # connections are made to actual Function() arguments.

    # HERE. make proper function program_from_seq()
    program = Program()
    program.setup(empty_parent(), block._block_env, storage)
    program._primary = (block.raw_seq_expr(), )

    if block._binding_name != None:
        sg = dagraph.start_subgraph(block._binding_name.py_string(), block._id)
    else:
        sg = dagraph.start_subgraph("anonymous_block", block._id)
    #-- Special treatment for block argument names.
    for argname in block.positional_block_args():
        dagraph.add_locally_unique_node(
            block._block_env.lookup_symbol_id(argname),
            ##labeling
            attributes = [('label', "%s" % argname ),
                          ('shape', "ellipse"),])


    #-- Return() marker 
    return_mark = dagraph.add_locally_unique_node(
        block._id,
        attributes = [('label', ""),
                      ('shape', "house"),
                      ('color', 'black'),
                      ('style', 'filled'),
                      ('width', '0.15cm'),
                      ('fixedsize', 'true')])

    # The block BINDING ids in dagraph._call_stack are not useful
    # here; the actual BLOCK id is needed.
    dagraph._block_stack.append(return_mark)

    #-- Function body.
    graph_id = program.data_dag(block._block_env, dagraph, storage)

    if isinstance(graph_id, ReturnBranch):
        for src in graph_id._from_gid:
            dagraph.add_edge(src, return_mark,
                             attributes = [('color', 'blue'), ])
    else:
        dagraph.add_edge(graph_id, return_mark)
    #
    del dagraph._block_stack[-1]
    dagraph.end_subgraph()
    #
    return return_mark

def data_dag_block(self, env, dagraph, storage, block):
    # Also see Function.data_dag, Symbol.data_dag
    if block.nargs() != self.deref(1).__len__():
        raise DataDagError, \
              "Argument count mismatch: %s -- %s" % (block.source_string(),
                                                     self.source_string())

    last_value = data_dag_block_body(env, dagraph, storage, block)

    # Get this invocation's arguments' dags. [ a,b of f(a,b) ]
    arg_seq = self.deref(1)
    arg_dags = []
    for expr in arg_seq:
        arg_dags.append(expr.data_dag(env, dagraph, storage))
    # HERE. If f is a fnfn, certain arguments are Symbols() or
    # Function()s.  Neither expands by default, but should do so here.

    # OR: look for specialized patterns in the .data_dag() routine.

    # Bind block argument names to invocation arg dags.
    blck_arg_syms = block.positional_block_args(symbols = 1)
    for ii in range(len(arg_dags)):
        # For multiple values, use most recent.
        name_id = dagraph.get_graph_id(blck_arg_syms[ii]._id)
        if name_id == None:
            raise DataDagError, \
                  "No graph node found for tree_id %d" % blck_arg_syms[ii]._id
        dagraph.add_edge(arg_dags[ii], name_id)
    return last_value                   # The return value of the block.
    # return sg   # The block itself as return value (physical node)
Call.data_dag_block = data_dag_block

def data_dag_lookup(self, env):
    # Static dependency restrictions: for a.b, both must be Symbols();
    # otherwise, evaluation would be needed.

    # Also see Member.interpret.

    # Get b (of a.b)
    first = self.deref(0)
    second = self.deref(1)
    if isinstance(first, Symbol):
        if isinstance(second, Symbol):
            mem_name = second.py_string()
        else:
            raise DataDagError, "In a.b, b is not a name: " + str(second)
    else:
        raise DataDagError, "In a.b, a is not a name: " + str(first)

    # Get a (of a.b) -- the actual binding.
    object = env.lookup_ptr( first.as_index() )

    # To suppress modules from explicitly showing in the dag, first
    # check whether first.as_index() is a module.
    try:
        exec('import ' + first.as_index())
    except ImportError:
        pass
    else:
        object = eval(first.as_index())

    if isinstance(object, (Function, Map)):
        return object._block_env.lookup_ptr( mem_name )

    elif isinstance(object, DictType):
        return object[ mem_name ]

    elif isinstance(object, ModuleType):
        member = eval('object.' + mem_name)
        return member

    elif isinstance(object, Env):
        # Env()s have 2 possible member sources:
        #       the original Python class,
        # and   the Env() bindings.
        # To allow overriding, first try the bindings, then the
        # python 'built-ins'.
        stat, rv = object.lookup_status( mem_name )
        if stat:
            return rv
        return eval('object.' + mem_name)

    elif object == None:
        # W/o static typing, any member access' validity is unclear.
        return "unknown_member"

    elif callable(object):
        return object

    else:
        raise DataDagError, \
              ("Line: %d:col %d: Invalid reference found.  Internal error."
               % object._first_char)
Member.data_dag_lookup = data_dag_lookup

def data_dag(self, env, dagraph, storage):
    # For a.b, the dag references b -- b is treated like a single name.

    # Static dependency restrictions: for a.b, both must be Symbols();
    # otherwise, evaluation would be needed.

    first = self.deref(0)
    second = self.deref(1)
    if isinstance(first, Symbol):
        if isinstance(second, Symbol):
            # Get b (of a.b)
            mem_name = second.py_string()
        else:
            raise DataDagError, "In a.b, b is not a name: " + str(second)
    else:
        raise DataDagError, "In a.b, a is not a name: " + str(first)

# #     if first.as_index() in ['userdata']:
# #         pdb.set_trace()

    # Get a (of a.b) -- the actual binding.
    object = env.lookup_ptr( first.as_index() )

    if isinstance(object, Map):
        # In the Map() tree, find the Symbol() used in the
        # binding of b.
        tree_id = object._block_env.lookup_symbol_id( second.as_index() )
        if tree_id != None:
            return dagraph.get_graph_id(tree_id)
        else:
            raise DataDagError, ("Line: %d:col %d: " % object._first_char) + \
                  "Undefined map binding."

    #     return dagraph.add_locally_unique_node(
    #         tree_id,
    #         attributes = [('label', "%s" % second.as_index() )])
    elif isinstance(object, Function):
        raise DataDagError, ("Line: %d:col %d: " % first._first_char) + \
              "block bindings are not available " + \
              "outside block interpretation -- use a map instead."
    else:
        # Object is external. Link to the full name (a.b) instead.
        name = "%s.%s" % (first.py_string(), second.py_string())
        return dagraph.add_node(name, attributes = [('label', name)] )
Member.data_dag = data_dag

def data_dag(self, env, dagraph, storage):
    cond_gid = self.deref(0).data_dag(env, dagraph, storage)
    yes_gid = self.deref(1).data_dag(env, dagraph, storage)
    no_gid = self.deref(2).data_dag(env, dagraph, storage)
    #
    if isinstance(cond_gid, ReturnBranch):
        # Odd, but possible.
        return cond_gid

    # All branches Return()
    if isinstance(yes_gid, ReturnBranch) & isinstance(no_gid, ReturnBranch):
        return yes_gid.merge(no_gid)

    #
    # At least one real return value.  This (these) value(s) will be
    # propagated further, so the ReturnBranch edge is drawn here.
    #
    self_gid = dagraph.add_node(
        self._id,
        attributes = [('label', ''),
                      ('shape', 'circle'),
                      ('color', 'black'),
                      ('style', 'filled'),
                      ('width', '0.15cm'),
                      ('fixedsize', 'true')])
    #
    dagraph.add_edge(cond_gid, self_gid)

    if isinstance(yes_gid, ReturnBranch):
        for src in yes_gid._from_gid:
            dagraph.add_edge(src, dagraph._block_stack[-1],
                             attributes = [('color', 'blue'), ])
    else:
        dagraph.add_edge(yes_gid, self_gid,
                         attributes = [('color', '#00a000')]) # green


    if isinstance(no_gid, ReturnBranch):
        for src in no_gid._from_gid:
            dagraph.add_edge(src, dagraph._block_stack[-1],
                             attributes = [('color', 'blue'), ])
    else:
        dagraph.add_edge(no_gid, self_gid,
                         attributes = [('color', 'red')])

    return self_gid
If.data_dag = data_dag

def data_dag(self, env, dagraph, storage):
    # The real trick in Return() data flow is to ensure
    # never-reached parts are ignored.  This is done in the other
    # .data_dag()s
    arg_gid = self.deref(0).data_dag(env, dagraph, storage)
    return ReturnBranch(arg_gid)
Return.data_dag = data_dag

def data_dag(self, env, dagraph, storage):
    # Note on ReturnBranch:
    #   Assume no return occurs in the assigned expression.

    lhs = self.deref(0)
    rhs = self.deref(1)

    # Destructuring binding for tuples.
    if isinstance(lhs, Tuple):
        ii = 0
        name_ids = []
        names = lhs[0]                  # The list.
        for _ in self.arg_names():
            symbol = names[ii]
            name_ids.append(symbol.data_dag(env, dagraph, storage))
            ii += 1
        if isinstance(rhs, Tuple):
            values = rhs[0]
            if len(values) != len(names):
                raise DataDagError, \
                      ("Line: %d:col %d:Tuple sizes in assignment "
                       "don't match." % self._first_char)
            else:
                ii = 0
                for val in values:
                    val_id = val.data_dag(env, dagraph, storage)
                    # Must be local test below -- not in add_edge()
                    if val_id != None:
                        dagraph.add_edge(val_id, name_ids[ii])
                    ii += 1
                return name_ids[-1]
        else:
            # The check
            #   if isinstance(value, TupleType):
            # is not available w/o prior .interpret(); only a dag
            # making all binding names depend on all rhs contents can
            # be drawn.
            val_id = rhs.data_dag(env, dagraph, storage)
            if val_id != None:          # local test below.
                for name_id in name_ids:
                    dagraph.add_edge(val_id, name_id)
            return name_id

    # Plain symbol binding.
    elif isinstance(lhs, Symbol):
        val_id = rhs.data_dag(env, dagraph, storage)
        if val_id != None:          # local test.
            if isinstance(val_id, ReturnBranch):
                raise DataDagError, (
                    ("Line: %d:col %d:\n" %
                     self._first_char)
                    +
                    ("Return inside assignment: %s\n" %
                     self.source_substring())
                    )
            name_id = lhs.data_dag(env, dagraph, storage)
            dagraph.add_edge(val_id, name_id)
            return name_id
        else:
            return None

    else:
        raise DataDagError, \
              ("Line: %d:col %d: Invalid lhs in assignment "
               % self._first_char)
Set.data_dag = data_dag


def data_dag(self, env, dagraph, storage):
    # Note on ReturnBranch:
    #   Assume no return occurs in the list.

    self_id = dagraph.add_node(
        self._id,
        attributes = [('label', ""),
                      ('shape', 'box'),
                      ('color', 'black'),
                      # ('style', 'filled'),
                      ('width', '0.10cm'),
                      ('height', '0.10cm'),
                      ('fixedsize', 'true'),
                      ])
    children = [ child.data_dag(env, dagraph, storage)
                 for child in self.deref(0) ]
    for ch in children:
        dagraph.add_edge(ch, self_id)

    return self_id
List.data_dag = data_dag


def data_dag(self, env, dagraph, storage):
    # Note on ReturnBranch:
    #   Assume no return occurs in the tuple.
    self_id = dagraph.add_node(
        self._id,
        # # attributes = [('label', "TUPLE-%d" % self._id )]
        attributes = [('label', ""),
                      ('shape', 'box'),
                      ('color', 'black'),
                      # ('style', 'filled'),
                      ('width', '0.10cm'),
                      ('height', '0.10cm'),
                      ('fixedsize', 'true'),
                      ])
    children = [ child.data_dag(env, dagraph, storage)
                 for child in self.deref(0) ]
    for ch in children:
        dagraph.add_edge(ch, self_id)

    return self_id
Tuple.data_dag = data_dag

def data_dag(self, env, dagraph, storage):
    seq_expr = self
    if len(seq_expr) == 0:
        raise DataDagError, "Empty program"
    else:
        for expr in seq_expr:
            rv = (expr).data_dag(env, dagraph, storage)
            if isinstance(rv, ReturnBranch): # Rest is unreachable.
                break
    return rv
aList.data_dag = data_dag

#
#**        data_dag() member, Immediate() types
def data_dag(self, env, dagraph, storage):
    return dagraph.add_node(self._id)
aNone.data_dag = data_dag

def data_dag(self, env, dagraph, storage):
    return dagraph.add_node(
        self._id,
        ##labeling
        # attributes = [('label', "%s" % self.to_plain_python(storage))]
        attributes = [('label', ""),
                      ('shape', "diamond"),
                      ('color', 'black'),
                      ('width', '0.10cm'),
                      ('height', '0.10cm'),
                      ('fixedsize', 'true')]
        )
Immediate.data_dag = data_dag

def data_dag(self, env, dagraph, storage):
    tree_id = env.lookup_symbol_id(self.as_index())
    binding = env.lookup_ptr(self.as_index())
    if tree_id == None:
        # External (or undefined) symbol. Use as-is, globally.
        return dagraph.add_unique_node(
            self.py_string(),
            attributes = [('label', "%s" % self.as_index() )])

    elif isinstance(binding, Function):
        return data_dag_block_body(env, dagraph, storage, binding)

    else:
        return dagraph.add_locally_unique_node(
            tree_id,
            attributes = [('label', "%s" % self.as_index() )])
Symbol.data_dag = data_dag

def data_dag_lookup(self, env):
    rv = env.lookup_ptr(self.as_index())
    if rv == None:
        return "unknown_fn"
    else:
        return rv
Symbol.data_dag_lookup = data_dag_lookup

#

#*    Path access for trees
class InvalidPath(exceptions.Exception):
    def __init__(self, args=None):
        self.args = args

#
# The notion of paths in the gtk treeview is suitable for use here.
# It is defined as follows.
#
#     A path is a list of integer indices, 0-relative.
#     The column is a single integer index, again 0-relative.
#     
#     A path points to a value; the value may be indexed (by the column)
#     or simple (a None column index).
#     
#     For the structure
#         a
#           a1
#              b0, b1, ...
#           a2
#              b21
#              b22
#     the paths
#          ([], None) is 'a',
#          ([0, 1], None) is invalid,
#          ([0], 1) is 'b1'
#     
#     Thus, the path index runs down the tree, the column index across.
#     This means a node can be both a tree (have children), and a row
#     (have indices).
#     
#     Because the syntax is foo.element_at(), indexing starts at foo's
#     children.  Thus, foo.element_at([]) returns foo.
#
# Applied to ASTs, indices are logical and ignore intermediate
# structures (aList)

#
#**        Element at index

#
#***            testing expressions
"""
>>> pp =reader.parse('(a, b) = f(x,y)')

>>> pp.element_at([])
Program(aList([Set(Tuple(aList([Symbol('a'), Symbol('b')])), Call(Symbol('f'), aList([Symbol('x'), Symbol('y')])))]))

>>> pp.element_at([0])
Set(Tuple(aList([Symbol('a'), Symbol('b')])), Call(Symbol('f'), aList([Symbol('x'), Symbol('y')])))

>>> pp.element_at([0,0])
Tuple(aList([Symbol('a'), Symbol('b')]))

>>> pp.element_at([0,0,0])
Symbol('a')

>>> pp.element_at([0,1])
Call(Symbol('f'), aList([Symbol('x'), Symbol('y')]))

>>> pp.element_at([0,1,0])
Symbol('f')

"""
#
#***            Nested
def element_at(self, path):
    # See also aList.element_at.
    raise InterfaceOnly
Nested.element_at = element_at

def _element_path(self, path, func):
    if path == []:
        return self
    elif len(path) == 1:
        return func()
    else:
        return func().element_at(path[1:])
    
def element_at(self, path):
    return _element_path(self, path,
                         lambda : self._primary[0][ path[0] ] )
Tuple.element_at = element_at
Program.element_at = element_at
List.element_at = element_at
Map.element_at = element_at

def element_at(self, path):
    return _element_path(self, path,
                         lambda : self._primary[ path[0] ] )
Set.element_at = element_at
Macro.element_at = element_at
Inline.element_at = element_at
eTree.element_at = element_at


def element_at(self, path):
    # the aList in e.g.
    #     Call(Symbol('f'), aList([Symbol('x'), Symbol('y')]))
    #           0                   1           2
    # is transparent in PATH; indexing is as indicated.
    # 
    def _fun():
        if path[0] == 0:
            return self._primary[ 0 ]
        else:
            return self._primary[ 1 ][ path[0] - 1 ]
    return _element_path(self, path, _fun)
Call.element_at = element_at

#
#***            Immediate
def element_at(self, path):
    if path == []:
        return self                     # lvalue (via .deep_replace etc.)
    elif path == ['value']:
        return self._primary[0]         # Python rvalue.
    else:
        raise InvalidPath
Int.element_at = element_at

def element_at(self, path):
    raise InterfaceOnly
Immediate.element_at = element_at


#
#***            specials
def element_at(self, path):
    # See Nested.element_at
    raise Exception, \
          "internal error: aList() contents should be picked by parent."
aList.element_at = element_at


# 
#**        Form table of paths
def make_path_table(tree):
    # Input:
    #     TREE
    #         A selection_tree, constructed using eTree(), Macro(), etc.
    #
    # Return:
    #     TBL
    #         so that TBL[ path ] -> (name, macro)
    #                 TBL[ (path, 'num_leaves') ] -> int
    #
    #     A PATH is a tuple of indices, starting from 0
    #
    #     For trees, macro is None, for leaves the leaf itself.
    return tree._make_path_table((), {})


def _make_path_table(self, path, tbl):
    tbl[ path ] = ( self._label, self)
    # The leaves are l1, l2, ...
    leaves = len(self._primary) - 1
    tbl[ (path, 'num_leaves') ] = leaves
    for idx in range(0, leaves):
        leaf = self._primary[idx + 1] # for leaf in self._primary(1:):
        leaf._make_path_table(path + (idx,), tbl)
    return tbl
eTree._make_path_table = _make_path_table

def _make_path_table(self, path, tbl):
    # Input:
    #     TREE
    #         A selection_tree, constructed using eTree(), Macro(), etc.
    #
    #     PATH
    #         The path to TREE, as index tuple (a,b,...)
    #
    tbl[ path ] = (self)
    return tbl
Macro._make_path_table = _make_path_table
Macro.update_tree_table = _make_path_table
Inline._make_path_table = _make_path_table


def _make_path_table(self, path, tbl):
    print "Warning:  astType._make_path_table is deprecated."
    tbl[ path ] = (self, self)
    return tbl
astType._make_path_table = _make_path_table



#*    Tree work
#
#**        parent_id
def parent_id(self):
    return self.__dict__.get('_parent')
astType.parent_id = parent_id

def parent_id(self):
    return self.__dict__.get('_parent')
aList.parent_id = parent_id
Native.parent_id = parent_id

def has_parent(self):
    return self.parent_id() != None
astType.has_parent = has_parent
aList.has_parent = has_parent
cls_viewList.has_parent = has_parent
Native.has_parent = has_parent

# 
#**        misc
def placeholder(parent, storage):
    # Provide a valid (but meaningless) child.
    # Must be inserted in proper slot by parent. 
    zero_char = (0,0)
    child = (aNone() 
             .set_char_range(zero_char, zero_char) 
             .set_source_string('') )
    def_env = Env('dummy_env', None, None, storage)
    child.setup(parent, def_env, storage)
    return child

def empty_parent():
    return aNone(_id = None)

def body(self):
    return self._primary[0][0]
Program.body = body

def single_program(self):
    # In the case of a single program within this program, i.e.,
    # program:
    #   program:
    #       body
    # return the innermost program only (nothing is lost).
    if isinstance(self._primary[0][0], Program) and len(self._primary[0]) == 1:
        return self._primary[0][0].single_program()
    else:
        return self
Program.single_program = single_program

# 
#**        subtree replacement

class ReplacementError(exceptions.Exception):
    def __init__(self, args=None):
        self.args = args


def substitute(src, dst, tree):
    # Replace SRC with DST in tree.   SRC must match exactly.
    # The tree's source string is not replaced.
    lst = find_exact(tree, src)
    for elem in lst:
        elem.shallow_replace(deepcopy(dst).setup(empty_parent(),
                                                 def_env, storage)[0],
                             storage)
    return tree


def replacement_setup(self, new_val, storage):
    # Perform the .setup() action so that new_val can replace self.
    o_parent  = storage.load(self._parent)
    o_def_env = storage.get_attribute(self._id, "stored_from_env")
    new_val.setup(o_parent, o_def_env, storage)
    return new_val._id
astType.replacement_setup = replacement_setup


#
#***            deep  replacement
def deep_replace(self, new, storage, indent = 0):
    # Replace self with new in parent and all clones.
    self.shallow_replace(new, storage)
    sl = storage.load

    clone_l = storage.get_attribute(self._id, "interp_clone")
    if clone_l != None:
        print ' '*indent, "---------------------- clone data"
        for cid in clone_l:
            clone = sl(cid)
            # Set up subtree clone with appropriate parent.
            new_clone = deepcopy(new)
            clone.replacement_setup(new_clone, storage)
            clone.deep_replace(new_clone, storage)
astType.deep_replace = deep_replace
### Immediate.deep_replace = deep_replace

#
#***            shallow  replacement
def shallow_replace(self, new, storage, indent = 0):
    # Replace self in parent with 'new'.

    # Parent referring to self.
    parent_id = self.parent_id()
    if parent_id is None:
        raise ReplacementError, "no parent"

    parent = storage.load(parent_id)
    parent.replace_child(self._id, new)
astType.shallow_replace = shallow_replace
### Immediate.shallow_replace = shallow_replace


#
#***            Re-establish object graph structures after edit or copy.
# 
def _update_refs(self):
    pass
astType._update_refs = _update_refs

def _update_refs(self):
    ( self._python_init_string, ) = self._primary
Inline._update_refs = _update_refs    

# 
#***            child  replacement
def replace_child(self, orig_id, new_node):
    #
    assert isinstance(orig_id, IntType)
    idx = self.find_child_index(orig_id)
    if idx is None:
        raise ReplacementError("Child not found.")

    # Update direct references.
    foo = list(self._primary)
    foo[idx]._parent = None
    foo[idx] = new_node
    self._primary = tuple(foo)
    #
    self._update_refs()
    #
    new_node._parent = self._id
Nested.replace_child = replace_child


def replace_child(self, orig_id, new_node):
    return self._primary[0].replace_child(orig_id, new_node)
List.replace_child = replace_child

def replace_child(self, orig_id, new_node):
    # Also see Nested.replace_child()
    assert isinstance(orig_id, IntType)
    idx = self.find_child_index(orig_id)
    if idx is None:
        raise ReplacementError, "Child not found."

    # Update direct references.
    #
    foo = self._primary[0]
    foo[idx]._parent = None
    foo[idx] = new_node
    self._primary = (foo,)
    #
    self[idx] = new_node
    #
    new_node._parent = self._id
aList.replace_child = replace_child

# 
#**            insert / append child
def append_child(self, child):
    self.insert_child(len(self), child)
aList.append_child = append_child
List.append_child = append_child
Program.append_child = append_child

def insert_child(self, index, child):
    assert self._id != None
    # Also see Nested.insert_child()
    foo = self._primary[0]
    foo.insert(index, child)
    self._primary = (foo,)
    # 
    self.insert(index, child)
    #
    child._parent = self._id
aList.insert_child = insert_child

def insert_child(self, index, child):
    assert self._id != None
    # Also see Nested.insert_child()
    foo = list(self._primary)
    foo.insert(index, child)
    self._primary = tuple(foo)
    #
    child._parent = self._id
Nested.insert_child = insert_child

def insert_child(self, index, child):
    return self._primary[0].insert_child(index, child)
List.insert_child = insert_child
Program.insert_child = insert_child

def alist_replace(self, obj):
    assert isinstance(obj, aList)
    self._primary = (obj, )
cls_viewList.alist_replace = alist_replace

# 
#**            insert into all clones
def insert_child_rec(self, index, new, storage):
    load = storage.load

    # Insert 'new' in self and all clones.
    self.insert_child(index, new)
    clone_l = storage.get_attribute(self._id, "interp_clone")
    if clone_l != None:
        for cid in clone_l:
            self_cl = load(cid)
            # Set up subtree clone with appropriate parent.
            new_clone = deepcopy(new)
            copy_char_info(new, new_clone)
            new_clone.setup(
                self_cl,
                storage.get_attribute(self_cl._id, "stored_from_env"),
                storage)
            cross_ref_trees(storage, new, new_clone)
            self_cl.insert_child_rec(index, new_clone, storage)
astType.insert_child_rec = insert_child_rec
aList.insert_child_rec = insert_child_rec


# 
#**            detach (delete) child
def detach_child(self, orig_id, storage):
    # Detaching a child leaves the size unchanged.
    # Compare aList.detach_child()
    assert isinstance(orig_id, IntType)
    idx = self.find_child_index(orig_id)
    if idx is None:
        raise ReplacementError("Child not found.")

    # Update direct references.
    foo = list(self._primary)
    foo[idx]._parent = None
    ### del foo[idx]
    foo[idx] = placeholder(self, storage)
    self._primary = tuple(foo)
    #
    self._update_refs()
Nested.detach_child = detach_child

def detach_child(self, orig_id, storage):
    # Both the contained alist (the real child) and alist's children
    # are considered children of List. 
    # 
    assert isinstance(orig_id, IntType)

    if self._primary[0]._id == orig_id:
        idx = 0
        # Update direct references.
        foo = list(self._primary)
        foo[idx]._parent = None
        ### del foo[idx]
        foo[idx] = placeholder(self, storage)
        self._primary = tuple(foo)
        #
        self._update_refs()

    else:        
        return self._primary[0].detach_child(orig_id, storage)
List.detach_child = detach_child

def detach_child(self, orig_id, storage):
    # 
    # Detaching a child changes the size.
    # Compare Nested.detach_child()
    assert isinstance(orig_id, IntType)
    idx = self.find_child_index(orig_id)
    if idx is None:
        raise ReplacementError, "Child not found."

    # Update direct references.
    foo = self._primary[0]
    foo[idx]._parent = None
    del foo[idx]
    self._primary = (foo,)
    #
    del self[idx]
aList.detach_child = detach_child


def detach_from_parent(self, storage):
    # Parent referring to self.
    parent_id = self.parent_id()
    if parent_id is None:
        raise ReplacementError("No parent.")

    parent = storage.load(parent_id)
    parent.detach_child(self._id, storage)
astType.detach_from_parent = detach_from_parent
aList.detach_from_parent = detach_from_parent
Native.detach_from_parent = detach_from_parent


# # def detach_from_parent(self, storage):
# #     # Parent referring to self.
# #     parent_id = self.parent_id()
# #     if parent_id is None:
# #         raise ReplacementError("No parent.")

# #     parent = storage.load(parent_id)
# #     chid = self._real_tree._id          
# #     parent.detach_child(chid, storage)
# # cls_viewList.detach_from_parent = detach_from_parent

#
#**        deletion 
def delete(self, storage):
    # Remove from parent and storage.
    if self.parent_id():     self.detach_from_parent(storage)
    for ch in self.top_down():
        storage.remove(ch._id)
Nested.delete = delete
Immediate.delete = delete
aList.delete = delete
Native.delete = delete

# # def delete(self, storage):
# #     # Remove from storage.
# #     for ch in self.top_down():
# #         storage.remove(ch._id)
# # aList.delete = delete

#
#**        traversal
# 
#***            Tabular; clones, indentation -- grouped
def clones_grouped(id, storage, clone_level, indent):
    clone_l = storage.get_attribute(id, "interp_clone")
    if clone_l != None:
        for clone_id in clone_l:
            clone = storage.load(clone_id)
            # Recursive -- not too legible, but complete.
            yield None, '(', None
            for rv in clone.prefix_grpd(storage,
                                        clone_level = clone_level + 1,
                                        indent = indent):
                yield rv
            yield None, ')', None
            

def prefix_grpd(self, storage, clone_level = 0, indent = 0):
    # yield all tree nodes and their clones in
    # top-down, left-right, depth first form.
    # yielded are (tree, clone_level, indent_level)
    #
    # Clones are completed before children, so only uncloned trees are
    # returned uninterrupted.
    #
    yield self, clone_level, indent

    for clone in clones_grouped(self._id, storage, clone_level, indent):
        yield clone

    yield None, None, '('
    for child in self._primary:
        for rv in child.prefix_grpd(storage,
                                   clone_level = clone_level,
                                   indent = indent + 1):
            yield rv
    yield None, None, ')'
Nested.prefix_grpd = prefix_grpd

def prefix_grpd(self, storage, clone_level = 0, indent = 0):
    yield self, clone_level, indent

    for clone in clones_grouped(self._id, storage, clone_level, indent):
        yield clone

    yield None, None, '('
    for child in self._primary[0]:      # Only difference -- index.
        for rv in child.prefix_grpd(storage,
                                   clone_level = clone_level,
                                   indent = indent + 1):
            yield rv
    yield None, None, ')'
aList.prefix_grpd = prefix_grpd

def prefix_grpd(self, storage, clone_level = 0, indent = 0):
    yield self, clone_level, indent

    for clone in clones_grouped(self._id, storage, clone_level, indent):
        yield clone
Immediate.prefix_grpd = prefix_grpd

def prefix_grpd(self, storage, clone_level = 0, indent = 0):
    yield self, clone_level, indent

    for clone in clones_grouped(self._id, storage, clone_level, indent):
        yield clone
aNone.prefix_grpd = prefix_grpd

# 
#***            Tabular, including clones, with 'indentation'
def yield_clones(id, storage, clone_level, indent):
    clone_l = storage.get_attribute(id, "interp_clone")
    if clone_l != None:
        for clone_id in clone_l:
            clone = storage.load(clone_id)
            # Recursive -- not too legible, but complete.
            for rv in clone.prefix_all( storage,
                                        clone_level = clone_level + 1,
                                        indent = indent):
                yield rv


def prefix_all(self, storage, clone_level = 0, indent = 0):
    # yield all tree nodes and their clones in
    # top-down, left-right, depth first form.
    # yielded are (tree, clone_level, indent_level)
    #
    # Clones are completed before children, so only uncloned trees are
    # returned uninterrupted.
    #
    # This output is messy, but complete; displaying these
    # high-dimensional structures in a 1-D sequence is ALWAYS
    # messy...
    yield self, clone_level, indent

    for clone in yield_clones(self._id, storage, clone_level, indent):
        yield clone

    for child in self._primary:
        for rv in child.prefix_all(storage,
                                   clone_level = clone_level,
                                   indent = indent + 1):
            yield rv
Nested.prefix_all = prefix_all

def prefix_all(self, storage, clone_level = 0, indent = 0):
    yield self, clone_level, indent

    for clone in yield_clones(self._id, storage, clone_level, indent):
        yield clone

    for child in self._primary[0]:      # Only difference -- index.
        for rv in child.prefix_all(storage,
                                   clone_level = clone_level,
                                   indent = indent + 1):
            yield rv
aList.prefix_all = prefix_all

def prefix_all(self, storage, clone_level = 0, indent = 0):
    yield self, clone_level, indent
    for clone in yield_clones(self._id, storage, clone_level, indent):
        yield clone
Immediate.prefix_all = prefix_all

def prefix_all(self, storage, clone_level = 0, indent = 0):
    yield self, clone_level, indent
    for clone in yield_clones(self._id, storage, clone_level, indent):
        yield clone
aNone.prefix_all = prefix_all


#
#***            With 'indentation'
def top_down_indented(self, indent = 0):
    # top-down, left-right, depth first.
    yield self, indent
    for child in self._primary:
        for cc, cind in child.top_down_indented(indent = indent + 1):
            yield cc, cind
Nested.top_down_indented = top_down_indented

def top_down_indented(self, indent = 0):
    yield self, indent
Immediate.top_down_indented = top_down_indented

def top_down_indented(self, indent = 0):
    yield self, indent
aNone.top_down_indented = top_down_indented
Native.top_down_indented = top_down_indented

def top_down_indented(self, indent = 0):
    yield self, indent
    for child in self._primary[0]:
        for cc, cind in child.top_down_indented(indent = indent + 1):
            yield cc, cind
aList.top_down_indented = top_down_indented

#
#***            Outline elements only, with level
def outl_top_down(self, level = 0):
    # top-down, left-right, depth first.
    yield self, level
    for child in self._outl_children:
        for cc, cind in child.outl_top_down(level = level + 1):
            yield cc, cind
cls_viewList.outl_top_down = outl_top_down
Program.outl_top_down = outl_top_down

#
#***            Plain top-down 
# omit_children_of = [Function]
# def top_down(self, omit_children_of = []):
#     # top-down, left-right, depth first.
#     yield self
#     if self.__class__ in omit_children_of:
#         return
#     for child in self._primary:
#         for cc in child.top_down():
#             yield cc
# Nested.top_down = top_down

def top_down(self):
    # top-down, left-right, depth first.
    yield self
    for child in self._primary:
        for cc in child.top_down():
            yield cc
Nested.top_down = top_down

def top_down(self):
    yield self
Immediate.top_down = top_down

def top_down(self):
    yield self
aNone.top_down = top_down
Native.top_down = top_down

def top_down(self):
    yield self
    for child in self._primary[0]:
        for cc in child.top_down():
            yield cc
aList.top_down = top_down

# 
#***            Top-down, truncate subtrees of given type(s)
def top_down_truncate(self, omit_children_of):
    # Top-down, node-left-right, depth first traversal.  Instances of
    # classes in omit_children_of are returned but not traversed
    # further. 
    yield self
    if self.__class__ in omit_children_of:
        return
    for child in self._primary:
        for cc in child.top_down_truncate(omit_children_of):
            yield cc
Nested.top_down_truncate = top_down_truncate

def top_down_truncate(self, omit_children_of):
    yield self
Immediate.top_down_truncate = top_down_truncate

def top_down_truncate(self, omit_children_of):
    yield self
aNone.top_down_truncate = top_down_truncate
Native.top_down_truncate = top_down_truncate

def top_down_truncate(self, omit_children_of):
    yield self
    if self.__class__ in omit_children_of:
        return
    for child in self._primary[0]:
        for cc in child.top_down_truncate(omit_children_of):
            yield cc
aList.top_down_truncate = top_down_truncate

# 
#***            Flat, children only, generic callback interface
def visit_children(self, func, **kwds):
    # 
    # Call FUNC(CHILD, **kwds) for every CHILD.
    # 
    for child in self._primary:
        func(child, **kwds)
Nested.visit_children = visit_children

def visit_children(self, func, **kwds):
    pass
Immediate.visit_children = visit_children

def visit_children(self, func, **kwds):
    pass
aNone.visit_children = visit_children
Native.visit_children = visit_children

def visit_children(self, func, **kwds):
    for child in self._primary[0]:
        func(child, **kwds)
aList.visit_children = visit_children

# 
#***            Flat, editable subtrees only, iterator
# 
# For a given l3 type, yield the subtrees intended to be editable,
# bypassing containers (used by that type) they may be in.
# 

# Used for rendering of a textual program.
def subtrees(self):
    for child in self._primary:
        yield child
        for cc in child.subtrees():
            yield cc                    # iterator forwarding...
Nested.subtrees = subtrees

def subtrees(self):
    for child in self[0]:
        yield child
        for cc in child.subtrees():
            yield cc                    # iterator forwarding...
Program.subtrees = subtrees

def subtrees(self):
    # Arguments.
    for child in self[0]:
        yield child
        for cc in child.subtrees():
            yield cc                    # iterator forwarding...
    # Body.
    for child in self[1]:
        yield child
        for cc in child.subtrees():
            yield cc                    # iterator forwarding...
Function.subtrees = subtrees

def subtrees(self):
    # For a(b,c), return only b and c.
    # yield self[0]                       
    for child in self[1]:
        yield child
        for cc in child.subtrees():
            yield cc                    # iterator forwarding...
Call.subtrees = subtrees

def subtrees(self):
    yield self[0]
    for cc in self[0].subtrees():
        yield cc                    # iterator forwarding...
    yield self[1]
    for cc in self[1].subtrees():
        yield cc                    # iterator forwarding...
Member.subtrees = subtrees

def subtrees(self):
    yield self[0]
    for cc in self[0].subtrees():
        yield cc                    # iterator forwarding...
    for child in self[1]:
        yield child
        for cc in child.subtrees():
            yield cc                    # iterator forwarding...
    if not isinstance(self[2], aNone):
        for child in self[2]:
            yield child
            for cc in child.subtrees():
                yield cc                    # iterator forwarding...
If.subtrees = subtrees
## Set.subtrees = subtrees

def subtrees(self):
    for child in self[0]:
        yield child
        for cc in child.subtrees():
            yield cc                    # iterator forwarding...
List.subtrees = subtrees
Map.subtrees = subtrees
Tuple.subtrees = subtrees

def subtrees(self):
    if 0: yield None
    return 
Immediate.subtrees = subtrees

def subtrees(self):
    if 0: yield None
    return 
aNone.subtrees = subtrees
Native.subtrees = subtrees

def subtrees(self):
    for child in self._primary[0]:
        yield child
        for cc in child.subtrees():
            yield cc                    # iterator forwarding...
aList.subtrees = subtrees

# 
#***            Flat, no recursion, editable subtrees1 only, iterator
# 
# For a given l3 type, yield the IMMEDIATE subtrees1 intended to be editable,
# bypassing containers (used by that type) they may be in.
# 

# Used for rendering of a textual program.
def subtrees1(self):
    for child in self._primary:
        yield child
Nested.subtrees1 = subtrees1

def subtrees1(self):
    for child in self[0]:
        yield child
Program.subtrees1 = subtrees1

def subtrees1(self):
    # Arguments.
    for child in self[0]:
        yield child
    # Body.
    for child in self[1]:
        yield child
Function.subtrees1 = subtrees1

def subtrees1(self):
    # For a(b,c), return only b and c.
    # yield self[0]                       
    for child in self[1]:
        yield child
Call.subtrees1 = subtrees1

def subtrees1(self):
    yield self[0]
    yield self[1]
Member.subtrees1 = subtrees1

def subtrees1(self):
    yield self[0]
    for child in self[1]:
        yield child
    if not isinstance(self[2], aNone):
        for child in self[2]:
            yield child
If.subtrees1 = subtrees1
## Set.subtrees1 = subtrees1

def subtrees1(self):
    for child in self[0]:
        yield child
List.subtrees1 = subtrees1
Map.subtrees1 = subtrees1
Tuple.subtrees1 = subtrees1

def subtrees1(self):
    if 0: yield None
    return 
Immediate.subtrees1 = subtrees1

def subtrees1(self):
    if 0: yield None
    return 
aNone.subtrees1 = subtrees1
Native.subtrees1 = subtrees1

def subtrees1(self):
    for child in self._primary[0]:
        yield child
aList.subtrees1 = subtrees1


# 
#***            Flat traversal (node only).
def entries(self):
    # left-right
    for child in self._primary:
        yield child
Nested.entries = entries

def entries(self):
    yield self
Immediate.entries = entries

def entries(self):
    yield self
aNone.entries = entries
Native.entries = entries

def entries(self):
    for cc in self._primary[0]:
        yield cc
aList.entries = entries

def entries(self):
    for child in self._primary[0]:
        yield child
List.entries = entries
Program.entries = entries

def num_entries(self):
    return len(self._primary[0])
List.num_entries = num_entries

def get_child(self, idx):
    return (self._primary[0][idx])
List.get_child = get_child

#
#**        searching
def find_exact(tree, search_tree):
    matches = []
    for node in tree.top_down():
        if node.eql(search_tree):
            matches.append(node)
    return matches

def find_type(tree, search_class):
    matches = []
    for node in tree.top_down():
        if node.__class__ == search_class:
            matches.append(node)
    return matches

def find_non_nested_matches(tree, pattern):
    # Find matches of pattern in the outer tree, ie., those *not*
    # found inside Map(), Function()
    pass

def find_type_non_nested(tree, pattern):
    # Find matches of type in the outer tree, ie., those *not*
    # found inside Function()
    pass

def find_all_matches(tree, pattern):
    # Find *all* matches of pattern in tree, including *all* subtrees
    # of tree.
    pass


# A sample use may look like this:
#         seq_expr = object.seq_expr()
#         # Pattern from
#         #   import reader
#         #   reload(reader)
#         #   reader.parse('!! def_name string = ! foo')
#         # and modified.
#         match_list = find_non_nested_matches(
#             seq_expr,
#             Set( MarkerTyped( String('def_name'), Symbol('string')),
#                  Marker('foo')))
#         if len(match_list) == 0:
#             raise DataDagError, \
#                   ("In the reference %s.%s, %s has no member %s\n" %
#                    (first, second, first, second))
#         elif len(match_list) > 1:
#             raise DataDagError, \
#                   (("In the reference %s.%s, " +
#                     "%s has multiple bindings for %s\n") %
#                    (first, second, first, second))
#         else:

#
#**        verify tree structure
def verify_tree(node):
    for par, chld, idx in node.top_down_parent():
        if chld != None:
            if chld._parent != par._id:
                print "child (%s) has wrong parent (%s)"% chld, par

#
#**        parents
class TreeWork:
    def __init__(self, storage):
        self._storage = storage

    def parent(self, tree):
        return self._storage.load( tree._parent )

def all_parents(self, tree):
    while tree._parent:
        parent = self.parent(tree)
        if parent:
            yield parent
            tree = parent
        else:
            break
TreeWork.all_parents = all_parents

# Also useful: tree.top_down()
# tw = TreeWork(storage)

#
#**        enclosing elements
def find_first_parent(self, tree, type_t): 
    # Find first parent of type `type_t`
    for parent in self.all_parents(tree):
        if isinstance(parent, type_t):
            return parent
TreeWork.find_first_parent = find_first_parent

def find_all_parents(self, tree, type_t): 
    # Find all parents of type `type_t`
    for parent in self.all_parents(tree):
        if isinstance(parent, type_t):
            yield parent
TreeWork.find_all_parents = find_all_parents

def find_root(self, tree):
    parent = None
    for parent in self.all_parents(tree):
        pass
    return parent
TreeWork.find_root = find_root


#
#**        calling context
class ContextDispError(exceptions.Exception):
    def __init__(self, args=None):
        self.args = args

class CallContext:
    '''
    CallContext(K, C, O, J)

    The Call K occurs in the clone C of the tree O;
    C was made by Call J.
    ''' 
    pass

def __repr__(self):
    return "%s(%s, %s, %s, %s)" % (self.__class__.__name__,
                                   self.K,
                                   self.C,
                                   self.O,
                                   self.J)
CallContext.__repr__ = __repr__

#
#***            get lexical + 1 dynamic (old)
def get_calling_context(self, node):
    # prototype in v.1.1.2.10 of test-calc.py
    '''
    'node' is an integer.

    For a given node,
    return a nested list of (clone_src_id, clone_id) tuples.
    Full structure:
    rv   ::=  [ ]
          |=  [ path+ ]
    path ::=  [ (clone_src_id, clone_id) <, path>* ]

    This list represents (initial lexical + 1 dynamic) execution path
    leading to terminal (actually _used_*) copies of 'node'.

    clone_id:
        the current clone of node

    clone_src_id:
        the maker of the clone

    * In
        def A:
            def B:
                ...
            B()
        A()
      the first clone of B (CB1) is made by A(), but is never executed.
      This clone's parent tree is a Function(). '

      The second B clone is made by B() and executed.  Its parent is
      therefore a Program().

    '''
    # Rough outline:
    # starting tree
    # while 1:
    #     forward one clone (K)
    #     is K inside a
    #     Function():
    #         find first enclosing Program()
    #         add to context (cloned_by attribute)
    #         continue with K as starting tree
    #     Program():
    #         add to context (cloned_by attribute)
    #         break

    # Data possibilities:
    # node: []
    # node: clone / path -> clone / path -> 0
    # node: (clone / path -> (clone / path -> 0))
    node = self._storage.load(node)

    geta = self._storage.get_attribute
    clone_l = geta(node._id, "interp_clone")
    if clone_l:                         # int list
        clone_paths_l = []
        for clone_id in clone_l:
            K = self._storage.load(clone_id)
            cloned_by = -1
            # Is K inside a --
            parent = self.find_first_parent(K, (Function, Program))
            # -- Function?
            if isinstance(parent, Function):
                # Find enclosing Program()
                enclosing_prog = self.find_first_parent(parent, Program)
                if enclosing_prog == None:
                    raise ContextDispError, "Unexpected program structure."
                #
                # Get the context (cloning source)
                cloned_by = (geta(enclosing_prog._id,
                                  "cloned_by"), clone_id)
                if cloned_by[0] == None:
                    raise ContextDispError, "No clone source. "\
                          "Internal error"
                cloned_by = [cloned_by] + self.get_calling_context(K._id)

            # -- Program()?
            elif isinstance(parent, Program):
                #load = self._storage.load
                #print "program:cloned_by::", \
                #      load(geta(parent._id, "cloned_by")).calltree_str()
                #print "program:clone_of::", \
                #      load(geta(parent._id, "clone_of"))\
                #      ._binding_name.calltree_str()
                ###
                # Get the context (cloning source)
                cloned_by = [(geta(parent._id, "cloned_by"), clone_id)]
                if cloned_by[0][0] == None:
                    raise ContextDispError, "No clone source. "\
                          "Internal error"

            if cloned_by == -1:
                raise ContextDispError, "Unexpected program structure."
            clone_paths_l.append(cloned_by)
        return clone_paths_l
    else:
        return []
TreeWork.get_calling_context = get_calling_context
    
#
#***            get full dynamic
def get_call_ctxt(self, node):
    # Get all dynamic call paths reaching 'node'; these are in inverse
    # execution order; starting from an astType's clones, find the
    # execution paths that created them.

    # Returns a list of all traversal paths:
    #     CallContext list list
    #     list      follows the Call chain
    #     list      for all clones of node
    # 

    # This list could be merged to a single tree.
    # 
    def _loop(clone_id, first = 0):
        # loop clone_id
        K = self._storage.load(clone_id)
        # 
        # Is K inside a --
        # 
        K_par = self.find_first_parent(K, (Function, Program, Macro))
        #               -- Function?
        if isinstance(K_par, (Function, Macro)):
            # K is an inert clone (no value, not executable).
            if first:
                return [None]
            else:
                # There should be no intert nodes along an execution
                # path. 
                raise ContextDispError, "Unexpected program structure."

        #               -- Program()?
        elif isinstance(K_par, Program):
            # Get the context (cloning source).
            cc = CallContext()
            cc.K = K._id
            cc.C = K_par._id
            cc.O = geta(cc.C, "clone_of")
            cc.J = geta(cc.C, "cloned_by")
            if cc.J == None:
                return [cc]
            return [cc] + _loop(cc.J)
    node = self._storage.load(node)
    geta = self._storage.get_attribute
    clone_l = geta(node._id, "interp_clone")
    
    if clone_l :
        clone_paths_l = [_loop(clone_id, first = 1)[::-1]
                         for clone_id in clone_l]
        return filter(None, clone_paths_l)
    else:
        return []
    pass
TreeWork.get_call_ctxt = get_call_ctxt


#
#***            prune to selection
def prune_cctxt(self, cctxt_chains, must_include):
    # 
    # Find all chains containing the ids in must_include
    # must_include ::= (call id) list
    #                  [ id AND id ...]

    # The full case (not dealt with):
    #      must_include ::= (call id) list list
    #      where the meaning is  [ [id AND id ...] OR [id AND id ...] ]
    #      The ids must use the call chains' order.
    #       
    #      This is a full tree pattern match: multiple input lists,
    #      multiple match targets.
    #       
    #      The full calling context list is potentially huge; forming it
    #      just to prune it later is really ineffient... 
    #       
    #      The AND lists could differ only in their last entries, requiring
    #      either
    #        a. an advanced pruning algorithm
    #        b. brute force
    #       
    #      The case of brute force is likely sufficient for interactive
    #      use.  This simplifies must_include to
    #        must_include ::= (call id) list
    #                         [ id AND id ...]
    #                         
    if len(must_include) == 0:
        return copy(cctxt_chains)
    else:
        _kept_chains = []
        for call_chain in cctxt_chains:
            # Check if ALL entries of must_include are in ANY calling
            # context. 
            found = map( lambda _: 0, must_include )
            for cctxt in call_chain:
                # Horribly inefficient...
                if cctxt.K in must_include:
                    found[must_include.index(cctxt.K)] = 1
            if reduce(lambda x,y: x and y, found):
                # All there.
                _kept_chains.append(call_chain)

        return _kept_chains
TreeWork.prune_cctxt = prune_cctxt


#
#***            Get leaves and values.
def cctxt_leaves(self, cctxt_chains):
    stg = self._storage.get_attribute
    values = []
    for chain in cctxt_chains:
        cid = (chain[-1].K)
        values.append( (cid, stg(cid, 'interp_result')) )
    return values
TreeWork.cctxt_leaves = cctxt_leaves


#
#***            displaying
# Strings that taken together provide a meaningful display of the call
# path.
def calltree_str(self):
    return str(self._primary[0])
Immediate.calltree_str = calltree_str

def calltree_str(self):
    return str(self.__class__)
Nested.calltree_str = calltree_str

def calltree_str(self):
    return str(self.__class__)
aList.calltree_str = calltree_str

def calltree_str(self):
    operator = self.deref(0)
    if isinstance(operator, (Symbol, Member)):
        return operator.calltree_str()
    else:
        raise ContextDispError, "Invalid context: " + str(operator)
Call.calltree_str = calltree_str

def calltree_str(self):
    # For a.b, both a and b are assumed Symbols().
    return "%s.%s" % (self.deref(0).calltree_str(),
                      self.deref(1).calltree_str())
Member.calltree_str = calltree_str


#
#**        matching
class MatchFailure(Exception): pass

class Matcher:
    def __init__(self, matches = None):
        self._matches = matches or {}   # (string -> astType) dict
        self._matches_l = utils.ListDict() # (string -> astType list) dict

def _match_(self, tree, pattern):
    """
    Traverse tree and pattern, matching nodes.  The matcher nodes
    (! name) match any node, and what they match is bound to `name' in
    the Matcher instance.

    OLD:
    e.g.:
        def_env = Env(1, None, None)
        storage = RamMem('root_memory', 0)
        #
        ma = Matcher()
        tree = reader.parse(' hello [short ; list] ')
        tree.setup(None, def_env, storage)
        patt = reader.parse(' hello [!aha ; list] ')
        patt.setup(None, def_env, storage)

        res = ma.match(tree, patt)
        print ma._matches
    """
    #
    # Trees are assumed to have interface functions
    # __len__, __getitem__, and __class__
    # Thus, they are compatible with Python arrays
    #
    if pattern.__class__ == tree.__class__: # identical head
        # Test remaining tree
        nc = pattern.__len__()
        if nc != tree.__len__():
            raise MatchFailure
        # special case for childless types -- Immediate()s
        if nc == 0:
            # Immediate() match?
            if pattern.eql(tree): return True
            else:                 raise MatchFailure
        # Compare ALL children.
        for c in range(0,nc):
            self._match_(tree[c], pattern[c])
        return True

    elif pattern.__class__ == Marker:
        # Take subtree unconditionally
        self._matches[pattern.name()] = tree
        self._matches_l.push(pattern.name(), tree)
        return True

    elif pattern.__class__ == MarkerTyped:
        # Take subtree if it is of correct type.
        # !! name expr -> MarkerTyped(name, expr)
        expr = pattern.expr()
        if expr.__class__ == tree.__class__:
            self._matches[pattern.name()] = tree
            self._matches_l.push(pattern.name(), tree)
            return True
        else: raise MatchFailure

    else:                           # no match
        raise MatchFailure
# ast.Matcher.match = match
Matcher._match_ = _match_

def match(self, tree, pattern):
    """
    Traverse tree and pattern, matching nodes.  The matcher nodes
    (! name) match any node, and what they match is bound to `name' in
    the Matcher instance.
    """
    try:
        self._match_(tree, pattern)
        return self
    except MatchFailure:
        self._matches = {}
        self._matches_l = utils.ListDict()
        return False
Matcher.match = match

def match_exp_str(self, tree, pattern_str):
    """
    Match tree against a single expression given in pattern_str.
    For a sequence, uses the first expression.
    """
    from l3lang import reader
    full = reader.parse(pattern_str)
    patt = full._primary[0][0]
    return self.match(tree, patt)
Matcher.match_exp_str = match_exp_str

def get(self, name):
    return self._matches.get(name)
Matcher.get = get

def get_all(self, name):
    '''Return the list of matches for `name`.
    '''
    return self._matches_l.get(name)
Matcher.get_all = get_all

def __setitem__(self, name, val):
    self._matches[name] = val
    self._matches_l.push(name, val)
Matcher.__setitem__ = __setitem__

def __getitem__(self, name):
    return self.get(name)
Matcher.__getitem__ = __getitem__

# Interferes with class names, and caused the rather cryptic
#   TypeError: 'NoneType' object is not callable
# def __getattr__(self, name):
#     return self.get(name)
# Matcher.__getattr__ = __getattr__

def construct(self, tree):
    # HERE. add.
    # Construct a new tree from a string and using tree elements stored in
    # the Matcher instance.
    # new_tree = ma.construct("{ |a,b| !rest }")
    pass
Matcher.construct = construct

#*    Outline construction
# 
#**        set outline edges to viewList-containing tree
# set_outl_edges
#   clears existing state and sets new outline edges; can
#   be used after any tree updates or copies.
#   Outline edges are NOT needed for interpretation.
def set_outl_edges(self, w_, parent_outline):
    # Reset child outlines.
    self._outl_children = vaList([]).setup_valist(w_, self)

    # Link to/from outline parent.
    if parent_outline is None:
        self._outl_parent = None
    else:
        self._outl_parent = parent_outline
        parent_outline._outl_children.append_child(weakref.proxy(self))

    # Form edges to/from children.
    self._primary[0].set_outl_edges(w_, weakref.proxy(self))
    # 
    return self
cls_viewList.set_outl_edges = set_outl_edges

def set_outl_edges(self, w_, parent_outline):
    for child in self._primary:
        child.set_outl_edges(w_, parent_outline)
    return self
Nested.set_outl_edges = set_outl_edges

def set_outl_edges(self, w_, parent_outline):
    # Reset child outlines.
    self._outl_children = vaList([]).setup_valist(w_, self)

    # Link to/from outline parent.
    if parent_outline is None:
        self._outl_parent = None
    else:
        self._outl_parent = parent_outline
        parent_outline._outl_children.append_child(weakref.proxy(self))

    # Form edges to/from children.
    for child in self._primary:
        child.set_outl_edges(w_, weakref.proxy(self))
    # 
    return self
Program.set_outl_edges = set_outl_edges


def set_outl_edges(self, w_, parent_outline):
    for child in self._primary[0]:
        child.set_outl_edges(w_, parent_outline)
    return self
aList.set_outl_edges = set_outl_edges

def set_outl_edges(self, w_, parent_outline):
    return self
Immediate.set_outl_edges = set_outl_edges
aNone.set_outl_edges = set_outl_edges
Native.set_outl_edges = set_outl_edges

#
#**        util
def set_outline(self, outline_type):
    assert outline_type in ['nested', 'subtree', 'flat']
    self._outl_type = outline_type
    return self
cls_viewList.set_outline = set_outline
Program.set_outline = set_outline

def get_outline_type(self):
    return self._outl_type 
cls_viewList.get_outline_type = get_outline_type
Program.get_outline_type = get_outline_type

def setup_alist(self, w_, parallel_nd):
    # Return an empty alist, .setup() using the environment of
    # `parallel_nd`. 
    storage = w_.state_.storage
    parent = empty_parent()
    def_env = storage.get_attribute(parallel_nd._id, "stored_from_env")
    # Form the raw list.
    rv, _ = aList([]).setup(parent, def_env, storage)
    return rv
aList.setup_alist = setup_alist

#
#**        calculate outline heading index 
def heading_index(self):
    # Return (level, index) tuple, both starting from 0;
    # `level` is the depth in the outline,
    # `index` the position at that `level`.

    # Level.
    if self._outl_parent:
        par_l, _ = self._outl_parent.heading_index()
    else:
        par_l = -1
    level = par_l + 1

    # index.
    if self._outl_parent:
        index = self._outl_parent.outl_find_child(self)
    else:
        index = 0
    return (level, index)
cls_viewList.heading_index = heading_index
Program.heading_index = heading_index

def outl_find_child(self, chld):
    tmp = weakref.proxy(chld)
    return self._outl_children.index(tmp)
cls_viewList.outl_find_child = outl_find_child
Program.outl_find_child = outl_find_child

# 
#**     iterate top-down
def outl_iter(self, level = 0):
    'Iterate top-down, return (level, node)'
    yield (level, self)
    for sub in self._outl_children:
        for nd in sub.outl_iter(level = level + 1):
            yield nd
cls_viewList.outl_iter = outl_iter
Program.outl_iter = outl_iter

# 
#**     hide below 'level'
def outl_flat_display(self, level):
    for (lev, nd) in self.outl_iter():
        if lev >= level:
            nd.set_outline('flat')
cls_viewList.outl_flat_display = outl_flat_display
Program.outl_flat_display = outl_flat_display

# 
#**        copies
def __deepcopy__(self, memo):
    # A copy must set its own outline cross-references
    # (_outl_children) when needed, but the desired outline type
    # (_outl_type) can be kept. 
    op = self._outl_parent 
    oc = self._outl_children 
    self._outl_parent = None
    self._outl_children = None
    # 
    rv = Nested.__deepcopy__(self, memo)
    # The w_ is not available yet.
    # rv.set_outl_edges(w_, parent_outline) 
    self._outl_parent = op
    self._outl_children = oc
    return rv    
cls_viewList.__deepcopy__ = __deepcopy__
Program.__deepcopy__ = __deepcopy__

# 
#**        persistence
# The only safe persistent format is the ususal tree (no outline).
def __getstate__(self):
    rv = {}
    rv.update(self.__dict__)
    rv['_outl_parent'] = None
    rv['_outl_children'] = None
    rv['_pre_interp_hook'] = None
    return rv
cls_viewList.__getstate__ = __getstate__
Program.__getstate__ = __getstate__

def __setstate__(self, stuff):
    self.__dict__.update(stuff)
cls_viewList.__setstate__ = __setstate__
Program.__setstate__ = __setstate__


# Apparently (python 2.4), list pickling is special.  A python.list
# method
#   <built-in method __reduce_ex__ of vaList object at 0xb7da60cc>
# is used to get the tuple
#     (<function __newobj__ at 0xb7fb9e9c>,
#      (<class 'l3lang.ast.vaList'>,),
#      [],
#      <listiterator object at 0xb7cf9aec>,
#      None)
# and the listiterator is actually used to get the contents.  
# 
# See http://www.python.org/dev/peps/pep-0307
# 
# Thus, we must preempt this by providing __reduce_ex__
def valist_restore(*ignore):
    return vaList([])

def __reduce_ex__(self, protocol):
    return (valist_restore, ())
vaList.__reduce_ex__ = __reduce_ex__



#*    Python callback wrapper
class CallBackError:
    pass

class CallableFunction:
    pass

def __init__(self, block, env, storage, block_invocation, arg_index):
    # self._env            = env
    self._block            = block
    self._storage          = storage
    self._block_invocation = block_invocation

    # Incremental evaluation data
    # arg_index is the position of self in another call,
    # E.g., for f(a, self, b), arg_index is 1
    self._arg_index        = arg_index
    self._call_count       = 0
    # See also CallableFunction.__call__
    storage.ie_.set_timestamp(
        (block_invocation._id, self._call_count, arg_index),
        # ### which timestamp to use?
        storage.ie_.get_timestamp(block_invocation._id))
CallableFunction.__init__ = __init__

def callable_interpret_prep(call_block, args):
    # Prepare the block, evaluate arguments, and provide
    # environments.
    # See call_function_prep

    block     = call_block._block
    storage   = call_block._storage
    block_inv = call_block._block_invocation
    ccount    = call_block._call_count
    arg_index = call_block._arg_index

    # Incremental evaluation check.
    if storage.ie_.has_clone( (block_inv._id, ccount, arg_index) ):
        cc = storage.ie_.clone_table()
        program = cc[ (block_inv._id, ccount, arg_index) ]
        eval_env, arg_env = cc[( (block_inv._id, ccount, arg_index) , 'envs')]

    else:
        if block.nargs() != len(args):
            raise CallBackError, "Argument count mismatch: " + \
                  str(block) + str(args)

        # ---- Turn block into executable.
        newblock = block.block_copy(storage)
        program = Program(newblock.raw_seq_expr())

        # ---- Set up argument environment.
        if block._binding_name != None:
            arg_env = block._def_env.new_child(
                program, name = block._binding_name.py_string())
        else:
            arg_env = block._def_env.new_child(program, name = "run.arg")

        # ---- Get positional block arguments' names.
        ma = Matcher()
        arg_names = []
        for ba in block.block_args():
            # if not ma.match_exp_str(ba, '!! name symbol'):
            if not ma.match(ba, MarkerTyped(String('name'), Symbol('symbol'))):
                raise InterpreterError, "Invalid argument type: " + str(ba)
            arg_names.append(ma._matches['name'])

        # ---- Bind block argument names to actual arguments.
        ma = Matcher()
        position_index = 0
        for ba in args:
            # To account for repeated external calls, use the call_count as id
            # for the pointer.
            arg_env.bind_ptr(arg_names[position_index].as_index(),
                             ba,
                             ccount)
            # Incremental evaluation.
            arg_env.bind_time_stamp_ptr(arg_names[position_index].as_index(),
                                        ie_setup_time,
                                        ccount)
            position_index += 1

        # ---- Set up evaluation environment.
        eval_env = arg_env.new_child(program, name = "run.blck")

        # ---- Finish program.
        program.setup(empty_parent(), eval_env, storage)

        #---------------- later interaction
        cross_reference_trees(storage, block, newblock)
        #----------------

        # Incremental evaluation data.
        cc = storage.ie_.clone_table()
        cc[ (block_inv._id, ccount, arg_index) ] = program
        cc[( (block_inv._id, ccount, arg_index) , 'envs')] = eval_env, arg_env
    return program, eval_env, arg_env


def callable_call(self, *args):
    # incremental
    # Also see call_real_interpret
    #     if isinstance(block, Function):
    # section
    block     = self._block
    storage   = self._storage
    ccount    = self._call_count
    arg_index = self._arg_index
    block_inv = self._block_invocation

    program, eval_env, arg_env = callable_interpret_prep(self, args)

    # Note: CallableFunction has no _id, but corresponds to
    #       Call. Here, use the Program()'s _id

    # ----------- Data for this block
    # Valid with tail call or without, so this MUST PRECEDE the
    # call to program.interpret(), below.
    #
    storage.push_attributes(block._id, "interp_clone", program._id)
    storage.set_attributes(program._id,
                           "interp_program", program, "interp_env", arg_env)
    # lexical information
    storage.set_attributes(program._id,
                           # lexical information
                           "clone_of", block._id,
                           "interp_env", arg_env,
                           # dynamic information
                           "cloned_by", self._block_invocation._id
                           )


    # ---- Evaluate
    # Affects: Program.interpret, Call.interpret(, storage)
    def finish(rv, ie_status):
        # Incremental evaluation check.
        if storage.ie_.tree_is_older( (block_inv._id, ccount, arg_index),
                                      ie_status):
            # Interpretation values.
            storage.id2tree(rv, program)
            storage.set_attributes(program._id, "interp_result", rv)

            # Incremental evaluation data.
            storage.ie_.touch( (block_inv._id, ccount, arg_index) )
            storage.ie_.set_timestamp(((block_inv._id, ccount, arg_index),
                                       'value'),
                                       ie_status)
            return rv, ie_status

        else:
            return storage.get_attribute(program._id, "interp_result"),  \
                   storage.ie_.get_timestamp((block_inv._id, ccount,
                                              arg_index))
    try:
        # Interpretation
        rv, ie_status  = program.interpret(eval_env, storage)

    except Interpret_tail_call, contin:
        new_tree, _env, _prog_l = contin.args
        _prog_l.append(finish)
        raise
    except Interpret_return, e:
        rv, ie_status = e.args

    return finish(rv, ie_status)
    # -----------

#
def __call__(self, *args):
    # Also see Call.interpret
    try:
        try:
            rv, ie_status = callable_call(self, *args)
        finally:
            # Prepare for possible next call; similar to __init__ for
            # the first call.
            #
            # Incremental evaluation data.
            self._call_count += 1
            self._storage.ie_.set_timestamp(
                (  self._block_invocation._id,
                   self._call_count,
                   self._arg_index),
                # ?? use previous call's timestamp? '
                self._storage.ie_.get_timestamp(self._block_invocation._id))

    except Interpret_tail_call, contin:
        tree, env, _prog_l = contin.args
        rv, ie_status = Call.interpret(
            tree, env, self._storage, tail_finishing_progs = _prog_l)

    return rv
CallableFunction.__call__ = __call__



#*    I/O
class File_io(astType):
    pass

#*    Memory
class Unpickleable:
    pass

def __repr__(self):
    return "%s(%s,%r)" % (self.__class__.__name__,
                          self._problem_id,
                          self._problem_str)
Unpickleable.__repr__ = __repr__
                          

def __init__(self, problem_id, problem_str):
    '''
    Unpickleable indicates an unpickleable value.
    problem_id:     the value's generating expression
    problem_str:    the value's string representation
    '''
    self._problem_id = problem_id
    self._problem_str = problem_str
Unpickleable.__init__ = __init__


#*    Memory
class Memory:
    pass

class RamMem(Memory):
    pass

def __init__(self, unique_prefix, starting_index, initial_time = 1):
    # Memory is split into temporary and persistent, but lookup is
    # done identically.
    # Note:
    #       most types contain a reference to their Memory(), so
    #       CONTROLLED PICKLING OF Memory() TYPES IS REQUIRED -- via
    #       __getstate__ etc.
    self._store         = {}            # persistent
    self._store_memory  = {}            # temporary
    self._counter       = starting_index
    self._unique_prefix = unique_prefix
    ## self._main_programs = []            # type [program * ], persistent

    # Two-level storage for .interpret() use:
    # id -> key1 -> value1
    #            -> value2
    #               ...
    #    -> key2 -> value1
    #            -> value2
    # (key1 -> ( key2 -> value) dict) dict
    self._attr_tables   = {}
    self._id2tree       = {}

    # Incremental evaluation.
    self.ie_ = IncEval(initial_time = initial_time)

    # Pickle testing cache.
    self._pickle_tested = {}            # id() -> status dict.
                                        # status ::= None | "pickles"
                                        #            | "no_pickle"  

RamMem.__init__ = __init__


def display_text(self, out = sys.stdout, indent = 0, width = 80):
    # out is a stdout - compatible stream
    # NOTE:
    # Full, pretty-printed output is nice, but very tedious w/
    # "manual" indentation.  It also has no interaction possibilities.
    # Better to produce structurally marked-up output in the first
    # place.
    # So cheat here.
    import pprint
    pp = pprint.PrettyPrinter(stream = out, indent = indent, width = width)
    pp.pprint(self.__dict__)
RamMem.display_text = display_text

# def add_program(self, prog):
#     self._main_programs.append(prog)
# RamMem.add_program = add_program

#
#**        Persistence
# pickle/unpickle methods.
def __getstate__(self):
    return [self._store,
            {},
            self._counter,
            self._unique_prefix,
            self._attr_tables,
            self._id2tree,
            self.ie_,
            self._pickle_tested,
            ]
RamMem.__getstate__ = __getstate__
RamMem.__real_getstate__ = __getstate__


def __null_getstate__(self):
    ''' Suppress __getstate__ during pickle testing.
    This is faster, and also avoids re-reporting errors for previous
    values.  
    '''
    return "RamMem-null-state"
RamMem.__null_getstate__ = __null_getstate__
    

def __setstate__(self, stuff):
    (self._store,
     self._store_memory,
     self._counter,
     self._unique_prefix,
     self._attr_tables,
     self._id2tree,
     self.ie_,
     self._pickle_tested
     )   = stuff
RamMem.__setstate__ = __setstate__

#
#**        Value access
def store(self, val, env, persistent = True):
    # pathname = Path(self._unique_prefix,
    #                 env.full_path(), self._counter)
    self.set_attributes(self._counter, "stored_from_env", env)
    if persistent:
        self._store[ self._counter ] = val
    else:
        self._store_memory[ self._counter ] = val
    self._counter += 1
    return (self._counter - 1)
RamMem.store = store

def load(self, key):
    assert isinstance(key, (IntType, LongType))
    return self._store.get(key, self._store_memory.get(key))
RamMem.load = load

def remove(self, key):
    assert isinstance(key, (IntType, LongType))
    foo = self._store.get(key, self._store_memory.get(key))
    if self._store.has_key(key):
        del self._store[key]
    if self._store_memory.has_key(key):
        del self._store[key]
    return foo
RamMem.remove = remove


#
#**        id handling
def new_id(self):
    self._counter += 1
    return (self._counter - 1)
RamMem.new_id = new_id

def id2tree(self, value, tree):
    # the mapping from id(foo) -> <tree that created foo>
    self._id2tree[ id(value) ] = tree
RamMem.id2tree = id2tree

def generator_of(self, id):
    # Return the expression that produced `id`
    # SUBTLE PYTHON PROBLEM
    # Mapping id(val) may be wrong when val is a string.
    #     Python strings may be interned, so multiple distinct strings
    #     can have the same id, invalidating the id->tree mapping.
    return self._id2tree.get(id)
RamMem.generator_of = generator_of

#
#**        misc.
def get_type(self, key):
    # This can be optimized for real disk access.
    return self.deref(self, key).__class__
RamMem.get_type = get_type

def _set_counter(self, val):
    """
    Change the id counter to val.  This will break almost any L3 code.
    Useful only for experimentation. 
    """
    self._counter = val
RamMem._set_counter = _set_counter

#
#**        interpret() attributes
def set_attributes(self, nid, *args):
    # typical call:
    #  self._storage.set_attributes(self._id,
    #                               "interp_result", rv,
    #                               "interp_env", eval_env)
    if (len(args) % 2) != 0:
        raise InterpreterError, "expected key/value pairs, got " + \
              str(args)
    kvpairs = [(args[i], args[i+1]) for i in range(0, len(args),2)]
    dct = self._attr_tables.get(nid)
    if not dct:
        dct = {}
        self._attr_tables[nid] = dct
    if not isinstance(dct, DictType):
        raise InterpreterError, "storage key is already bound to non-dict."
    for kk, vv in kvpairs:
        #
        # Check pickleability.
        # For values that don't pickle,
        #   - issue a warning
        #   - substitute Unpickleable
        #
        if glbl.L3_PICKLE_IMMEDIATELY and (kk == 'interp_result'):
            # Tested already?
            stat = self._pickle_tested.get(id(vv))
            if stat == 'pickles':
                dct[kk] = vv
            elif stat == 'no_pickle':
                dct[kk] = Unpickleable(nid,
                                       self.load(nid).source_string(),
                                       )
                dct[kk] = vv   # Allow rest of program to run.
            else:
                ## import pickle
                import cPickle as pickle
                try:
                    RamMem.__getstate__ = RamMem.__null_getstate__
                    Env.__getstate__ = Env.__null_getstate__
                    try:
                        ps = pickle.dumps(vv, protocol=2)
                        if glbl.L3_PICKLE_SIZE:
                            glbl.logger.info("%d, %s: %d bytes" %
                                             (nid, kk, len(ps)))
                        del ps
                    except Exception, e:
                        glbl.logger.warn(
                            'Value from interpretation of %d does not pickle.'
                            '\n%d: %r'
                            % (nid, nid, self.load(nid).source_string()))
                        glbl.logger.warn('Message was: %s' % e)
                        dct[kk] = Unpickleable(nid,
                                               self.load(nid).source_string(),
                                               )
                        dct[kk] = vv   # Allow rest of program to run.
                        self._pickle_tested[id(vv)] = 'no_pickle'

                    else:
                        dct[kk] = vv
                        self._pickle_tested[id(vv)] = 'pickles'
                finally:
                    RamMem.__getstate__ = RamMem.__real_getstate__
                    Env.__getstate__ = Env.__real_getstate__
        else:
            dct[kk] = vv
RamMem.set_attributes = set_attributes

def get_attribute_table(self, id):
    dct = self._attr_tables.get(id)
    if not dct:
        dct = {}
        self._attr_tables[id] = dct
    return dct
RamMem.get_attribute_table = get_attribute_table

def get_attributes(self, id, key_list):
    # typical call:
    #  self._storage.get_attributes(self._id, ['foo'])
    assert type(key_list) == ListType
    dct = self._attr_tables.get(id)
    if not dct:
        dct = {}
        self._attr_tables[id] = dct
    return [dct.get(key)
            for key in key_list ]
RamMem.get_attributes = get_attributes

def get_attribute(self, id, key):
    dct = self._attr_tables.get(id)
    if not dct:
        dct = {}
        self._attr_tables[id] = dct
    return dct.get(key)
RamMem.get_attribute = get_attribute

def get_attribute_names(self, id):
    #  self._storage.get_attribute_names(self._id)
    dct = self._attr_tables.get(id)
    if not dct:
        dct = {}
        self._attr_tables[id] = dct
    return dct.keys()
RamMem.get_attribute_names = get_attribute_names

def push_attributes(self, id, key, val):
    # Append val to value list of
    #     id -> key -> value list
    # from self._attr_tables
    curr = self.get_attribute(id, key) # the entry, None or [val1,...]
    if curr:
        curr.append(val)
    else:
        self.set_attributes(id, key, [val])
RamMem.push_attributes = push_attributes

def get_clones(self, id):
    # Return a list of trees.
    return [self.load(tree_id)
            for tree_id in self.get_attribute(id, "interp_clone")]
RamMem.get_clones = get_clones

def get_leaf_clones(self, orig_id, leaves = []):
    # 
    # Find the outermost clones of orig_id.
    # Returns a list of clones for single functions/loops.
    # For functions/loops lexically nested N deep, returns list of
    # lists, nested N deep.
    # 
    clones = lambda oid : self.get_attribute(oid, "interp_clone")
    maybe = clones(orig_id)
    if maybe != None:
        if clones(maybe[0]) != None:
            return [self.get_leaf_clones(new_id, maybe) for new_id in maybe]
        else:
            return maybe
    else:
        return leaves
RamMem.get_leaf_clones = get_leaf_clones


#*        pds
# These interfaces may not be needed...
class PdsInterface:
    """ General PDS model interface.
    """

    def __init__(self,dirname="ast-test", create = 0):
        raise InterfaceOnly

    def set(self, key, val, overwrite = 0):
        raise InterfaceOnly

    def get(self, key, type=None):
        raise InterfaceOnly

    def delete(self, key):
        raise InterfaceOnly

    def commit(self):
        raise InterfaceOnly

    def abort(self):
        raise InterfaceOnly

class RamIO(PdsInterface):
    """ Simulated PDS interface in memory; fast and simple for
    experimentation.
    """
    def __init__(self, dirname="ast-test", create = 0):
        self._dirname = dirname
        self._dir = {}

    def set(self, key, val, overwrite = 0):
        if self._dir.has_key(key):
            raise OverwriteError
        self._dir[key] = val

    def get(self, key, type=None):
        return self._dir[key]

#*    Evaluation environment
class NoValue:
    '''Substitute for None inside class Env'''
    pass

class Env:
    pass

def __init__(self, id, definition_env, program, storage, name = "anonymous"):
    self._primary = (id, definition_env,  program)
    if definition_env != None:
        self._def_env_id       = definition_env._id
    else:
        self._def_env_id       = None
    self._env_subid     = id            # local id
    self._program       = program       # _id may not be available yet...

    # The Env() storage is a ( name -> val ) map, but with an indirection to 
    # get the "current" value:
    # 
    #     (name, 'ptr') -> set_id
    #     (name, set_id) -> val
    #     (name, 'ie_status', set_id) -> status
    # 
    # 
    # self._bindings:
    #     (name, 'ptr') -> set_id             # current index
    #     (name, set_id) ->  val              # values
    #     (name, 'ie_status', set_id) -> time # time stamps
    # 

    # (name -> val)
    # (name, 'ie_status') -> timestamp
    #   dict, accessed via Env.bind()
    self._bindings      = {}

    self._bindings_memory = {}
    self._sub_env_id_count = 0
    self._children      = []            # Env list, formed by new_child()

    # Directory linking support.
    self._dir_stack = []                # Working directory stack.
    self._dir_known = {}                # files already encountered.

    # (name -> tree_id) dict, accessed via Env.bind_id()
    #   tree_id is usually the Symbol's id in the Set(Symbol(), ...)
    #   tree making the assignment.
    self._bindings_ids  = {}

    #
    self._id            = storage.store(self, None) # global id
    self._storage       = storage
    self._name          = name
Env.__init__ =  __init__

#
#**        environment examination
def all_bindings(self):
    """ Return all bindings in this environment in a new dictionary.
    """
    bb = {}
    bb.update(self._bindings)
    bb.update(self._bindings_memory)
    return bb
Env.all_bindings = all_bindings

def all_lexical_bindings(self, dct):
    """ Put all bindings in this environment and all lexically
    enclosing ones into the given dictionary.

    Additions are made inwards from the outermost environment to
    preserve binding order.
    """
    if self._def_env_id !=  None:
        self._storage.load(self._def_env_id).all_lexical_bindings(dct)

    dct.update(self._bindings)
    dct.update(self._bindings_memory)
    return dct
Env.all_lexical_bindings = all_lexical_bindings

def children(self):
    return self._children
Env.children = children

def dump(self,
         show_prog = 1,
         show_vals = 1,
         ):
    rv = [('_name', self._name), 
          ('_id', self._id),
          ]

    if self._program and show_prog:
        rv.append( ('_program._id', self._program._id) )

    if show_vals:
        rv.append([
          ('_bindings', self._bindings),
          ('_bindings_ids', self._bindings_ids),
          ])

    rv.append([ dump(child, show_prog, show_vals)
                for child in self._children ])
    return rv
Env.dump = dump

def print_tree(self, indent = ""):
    # 
    # Print a nested view of this environment's entries, including only
    #   - key
    #   - Set() id

    # This Env.
    print indent, "%s-%d" % (self._name, self._id), '['

    # Local entries.
    indnt = indent + "    "
    for ky in self.all_bindings().iterkeys():
        if len(ky) == 2:
            if isinstance(ky[1], IntType):
                # (name, set_id)? Show name, set_id.
                #   Get fixed column for set_id
                tree_s = "%s %s" % (indnt, ky[0])
                print "%-40s %s" % (tree_s, ky[1]) 
    # Children.
    for child in self._children:
        child.print_tree(indent = indnt) 

    print indent, ']'
Env.print_tree = print_tree

def print_tree_tex(self, indent = "", out = sys.stdout, first = 1,
                   ignore_skel = 0):
    # FIXME: update for 'ptr' indirection!
    # 

    # Print a filtered view of this environment and its contents.
    # Filter:   - values
    #           - tuple keys 

    print self._name.startswith("skel"), \
          ignore_skel, \
          ignore_skel and self._name.startswith("skel")
    
    if ignore_skel and self._name.startswith("skel"):
        print "ignored"
        return 

    # This Env.
    if first:
        print >> out, indent, \
              r"""\begin{directory}[3in]{%s-%d}""" % (self._name, self._id) 
    else:
        print >> out, indent, \
              r"""\file{\begin{directory}{%s-%d}""" % \
              (self._name, self._id) 

    # Local entries.
    indnt = indent + "    "
    for ky in self.all_bindings().iterkeys():
        if isinstance(ky, TupleType):
            continue
        print >> out, indnt, r"\file{%s}" % ky

    # Children.
    for child in self._children:
        child.print_tree_tex(indent = indnt, out = out, first = 0,
                             ignore_skel = ignore_skel,
                             ) 

    if first:
        print >> out, indent, '\end{directory}'
    else:
        print >> out, indent, '\end{directory}}'
Env.print_tree_tex = print_tree_tex

def get_tree(self):
    # FIXME: update for 'ptr' indirection!
    # 

    # Return a FILTERED view of this environment and its contents.
    # Filtered out: - values (keys only)
    #               - tuple keys 
    
    # Local entries.
    subl = []
    for ky in self.all_bindings().iterkeys():
        if isinstance(ky, TupleType):
            continue
        subl.append(ky)

    # Children.
    for child in self._children:
        subl.append(child.get_tree())

    # Combine with this Env.
    return ("%s-%d" % (self._name, self._id), subl)
Env.get_tree = get_tree


def get_dynamic_subtrees(self):
    # FIXME: update for 'ptr' indirection!
    # 

    # Return a FILTERED view of this environment and its contents.
    # Filter:   - values (keys only)
    #           - tuple keys
    #           - anonymous envs
    #           - skel.arg
    #           - skel.blck
    # 
    # Structure:
    #     direc   ::= ( dirname, content )
    #     content ::= [ (name | direc)* ]
    # 
    # Note: - the first environment is always returned (even if anonymous)
    #       - Program.directory() can convert this structure.
    
    subl = []

    # Children.
    for child in self._children:
        if child._name in ["skel.arg", "skel.blck", "anonymous"]:
            continue
        subl.append(child.get_dynamic_subtrees())

    # Local entries.
    for ky in self.all_bindings().iterkeys():
        if isinstance(ky, TupleType):
            continue
        subl.append(ky)

    # Combine with this Env.
    return ("%s-%d" % (self._name, self._id), subl)
Env.get_dynamic_subtrees = get_dynamic_subtrees

def all_bindings_recursive(self, level = 0):
    # FIXME: update for 'ptr' indirection!
    # 

    # Return (key, value, Env()) tuples for all bindings in this Env()
    # and its children.
    for key, val in self._bindings.iteritems():
        yield key, val, self, level

    #     for key, val in self._bindings_ids.iteritems():
    #         yield key, val, self, level

    for child in self._children:
        for substuff in child.all_bindings_recursive(level + 1):
            yield substuff
Env.all_bindings_recursive = all_bindings_recursive

def new_child(self, program, name = "anonymous"):
    child = Env(self.new_env_id(), self, program, self._storage,
                name = name)
    self._children.append(child)
    return child
Env.new_child = new_child

#
#**        persistence
def __getstate__(self):
    from copy import copy
    dct = copy(self.__dict__)
    del dct['_bindings_memory']
    return dct
Env.__getstate__ = __getstate__
Env.__real_getstate__ = __getstate__

def __null_getstate__(self):
    ' Suppress __getstate__ during pickle testing. '
    return "Env-null-state"
Env.__null_getstate__ = __null_getstate__


def __setstate__(self, stuff):
    self.__dict__.update(stuff)
    self._bindings_memory = {}
Env.__setstate__ = __setstate__

# Give a new id for ENCLOSED environments (not self)
def new_env_id(self):
    self._sub_env_id_count += 1
    return self._sub_env_id_count
Env.new_env_id = new_env_id

def __repr__(self):
    def short_repr(obj):
        try:
            ss = "[Program at 0x%x, id %d]" % (id(obj), obj._id)
        except AttributeError:
            ss = str(obj)
            if len(ss) > 30:
                ss = ss[0:10] + ' ... ' + ss[-10:-1]
        return ss
    return self.__class__.__name__ + \
           ( '(%d, %s, %s)' %
             (self._id, self._primary[1], short_repr(self._primary[2])))
Env.__repr__ = __repr__

def __str__(self):
    return self.__class__.__name__ + \
           ( '-%d-%s' % (self._id, self._name))
Env.__str__ = __str__

# 
#**        Interpretation support
def _clr_wrn(self, name, val):
    if glbl.L3_TRACE_BIND:
        sys.stderr.write("trace: binding " + name + '\n')
        utils.callchain()

    def warn():
        val
        stuff = self.ie_lookup_1(name) 
        if stuff != None:
            if stuff[1] == ie_external_time:
                pass
            else:
                sys.stderr.write("warning: overriding definition of %(name)s:\n"
                                 "warning: original: %(stuff)s\n"
                                 "warning: new: %(val)s\n"
                                 % locals())
                sys.stderr.flush()

    if self._bindings.has_key(name):
        warn()
        del self._bindings[name]
        try:
            del self._bindings[ (name, 'ie_status') ]
        except KeyError:
            pass

    if self._bindings_memory.has_key(name):
        warn()
        del self._bindings_memory[name]
        try:
            del self._bindings[ (name, 'ie_status') ]
        except KeyError:
            pass
Env._clr_wrn = _clr_wrn

def bind(self, name, val):
    # Name
    #     bind(name, val)
    # Description
    #     Make VAL available under NAME in this Env.
    #
    #     This function should be used in conjunction with
    #     bind_time_stamp; see Env.import_names
    #
    assert name.__class__ == StringType # No subclasses allowed.
    # assert isinstance(name,  StringType) # Allows subclasses...
    self._clr_wrn(name, val)
    self._bindings[name] = val
Env.bind = bind

def bind_id(self, name, id):
    assert name.__class__ == StringType # No subclasses allowed.
    # assert isinstance(name,  StringType) # Allows subclasses...
    self._bindings_ids[name] = id
Env.bind_id = bind_id

def bind_mem_only(self, name, val):
    # # (probably) No longer needed.
    # # return self.bind(name, val)
    assert name.__class__ == StringType
    self._clr_wrn(name, val)
    self._bindings_memory[name] = val
Env.bind_mem_only = bind_mem_only

# HERE. the __hash__ and __cmp__ (p. 35) methods must work properly
# for Immediate()s

#
#**        data flow 
def bind_df(self, name, val):
    # Make VAL available under NAME in this Env, as dataflow
    # information only.  
    #
    assert name.__class__ == StringType # No subclasses allowed.
    self._clr_wrn((name, "df"), val)
    self._bindings[(name, "df")] = val
Env.bind_df = bind_df

def bind_id_df(self, name, id):
    assert name.__class__ == StringType # No subclasses allowed.
    self._bindings_ids[(name, "df")] = id
Env.bind_id_df = bind_id_df

#
#**        rebinding semantics (for Set())
# Allows multiple bindings to a single name, with an index to current
# binding.  
# 
ptr_external_id = -111

def bind_ptr(self, name, val, set_id):
    # 
    # Make `val` available under `name` in this Env,
    # - AND - 
    # set the pointer for `name` to this `val`.  Prior values are
    # kept, but this one is retrieved by default
    # 
    # This allows Set() and Symbol() to simulate imperative semantics.
    #
    assert name.__class__ == StringType # No subclasses allowed.
    # Add the new value.
    self._clr_wrn( (name, set_id), val)
    self._bindings[ (name, set_id) ] = val
    self.set_ptr(name, set_id)
Env.bind_ptr = bind_ptr

def bind_mem_only_ptr(self, name, val, set_id):
    # 
    # In-memory only version of bind_ptr; `val` is not retained
    # accross sessions.
    #
    assert name.__class__ == StringType # No subclasses allowed.
    # Add the new value.
    self._clr_wrn( (name, set_id), val)
    self._bindings_memory[ (name, set_id) ] = val
    self.set_ptr(name, set_id)
Env.bind_mem_only_ptr = bind_mem_only_ptr

def set_ptr(self, name, set_id):
    # Set the current pointer for `name` to `set_id`
    assert isinstance(set_id, (IntType, LongType)), "An l3 id must be integer."
    self._bindings[ (name, 'ptr') ] = set_id
Env.set_ptr = set_ptr

def lookup_ptr(self, name):
    '''
    Find the *current* `name` in self or any enclosing *defining* (not
    calling) environment.
    '''
    set_id = self.lookup( (name, 'ptr') )
    return self.lookup( (name, set_id) )
Env.lookup_ptr = lookup_ptr

def lookup_ptr_1(self, name):
    '''
    Find the *current* `name` in self or raise KeyError.
    '''
    set_id = self.lookup_1( (name, 'ptr') )
    return self.lookup_1( (name, set_id) )
Env.lookup_ptr_1 = lookup_ptr_1

def bind_time_stamp_ptr(self, name, time, set_id):
    'Set the time stamp for the `name` produced by Set with id `set_id`.'
    try:
        self.lookup_ptr_1(name)
    except KeyError:
        glbl.logger.error("Timestamping nonexistent name '" +
                          name + "'\n")
    self._bindings[ (name, 'ie_status', set_id) ] = time
Env.bind_time_stamp_ptr = bind_time_stamp_ptr

def ie_lookup_ptr(self, name):
    '''
    Incremental evaluation lookup.
    Find CURRENT name in self or any enclosing *defining* (not
    calling) environment. 
     Returns:
       None                when no binding is found
       (value, timestamp)  otherwise

    Export members starting with 'l3_'
    '''
    # Export members starting with l3_
    if name.startswith('l3_'):
        return getattr(self, name), ie_external_time

    # got pointer?
    if self._has_key( (name, 'ptr') ):  
        set_id = self._get_val( (name, 'ptr') )
        # got value for pointer?
        if self._has_key( (name, set_id) ):
            status = self._bindings.get( (name, 'ie_status', set_id) )
            if status is None:
                status = ie_external_time    # Force eval of parent
            return self._get_val((name, set_id)), status
        else:
            raise InterpreterError(
                "Found ptr to %s, but %s has no value -- internal error." %
                (name, name))
    else:
        if self._def_env_id is None:
            return None
        else:
            return self._storage.load(self._def_env_id).ie_lookup_ptr(name)
Env.ie_lookup_ptr = ie_lookup_ptr

def dict_ie_lookup_ptr(dct, name):
    set_id = dct.get( (name, 'ptr') )
    if set_id is not None:
        val = dct.get( (name, set_id) )
        assert (v is not None)          # ptr w/o value -- internal error.
        status = dct.get( (name, 'ie_status', set_id) )
        if status is None:
            status = ie_external_time    # Force eval of parent
        return v, status

    else:
        return (getattr(dct, name), ie_external_time)
        # Note:  Using 
        #       return (dct.get(name), ie_external_time)
        # fails; member functions are ignored.


#
#**        lookup functions
def _get_val(self, key):
    # (Internal) Lookup `key` in this Env only.
    if self._bindings.has_key( key ):
        return self._bindings.get( key )
    if self._bindings_memory.has_key( key ):
        return self._bindings_memory.get( key )
    raise KeyError("No value found for %s" % key)
Env._get_val = _get_val


def _has_key(self, key):
    # (Internal) Lookup `key` in this Env only.
    # Returns (gotvalue : Bool) 
    # A value can be retrieved via _get_val()
    if self._bindings.has_key( key ):
        return True
    if self._bindings_memory.has_key( key ):
        return True
    return False
Env._has_key = _has_key

def lookup(self, name):
    '''
    Find name in self or any enclosing *defining* (not calling) environment.
    Raise KeyError if no binding was found.
    '''
    if self._has_key(name):
        return self._get_val(name)
    else:
        if self._def_env_id is None:
            raise KeyError("No value found for %s" % name)
        else:
            return self._storage.load(self._def_env_id).lookup(name)
Env.lookup = lookup

def lookup_status(self, name):
    '''
    Find name in self or any enclosing *defining* (not calling)
    environment.
    Return (status, binding).
    status indicates whether the binding was found.
    '''
    if self._has_key(name):
        return (1, self._get_val(name))
    else:
        if self._def_env_id is None:
            return (0, None)
        else:
            return self._storage.load(self._def_env_id).lookup_status(name)
Env.lookup_status = lookup_status


def lookup_symbol_id(self, name):
    v = self._bindings_ids.get(name)
    if v != None:
        return v
    else:
        if self._def_env_id is None:
            return None
        else:
            return self._storage.load(self._def_env_id).lookup_symbol_id(name)
Env.lookup_symbol_id = lookup_symbol_id

def lookup_1(self, name):
    '''
    Find name in self only.
    '''
    if self._has_key(name):
        return self._get_val(name)
    raise KeyError("No value found for %s" % name)
Env.lookup_1 = lookup_1

def full_path(self, stack=[]):
    up = self._def_env_id
    if up != None:
        # [].append() returns None... Cute.
        # return up.full_path() + [(self._env_subid)]
        return self._storage.load(up).full_path() + [(self._env_subid)]
    else:
        return [self._env_subid]
Env.full_path = full_path

#
#**        Incremental evaluation
# Incremental evaluation.
def bind_time_stamp(self, name, time):
    # The (name, 'ie_status') binding is needed externally, hence
    # visible.
    try:
        self.lookup_1(name)
    except KeyError:
        glbl.logger.error("Timestamping nonexistent name '" +
                          name + "'\n")
    self._bindings[ (name, 'ie_status') ] = time
Env.bind_time_stamp = bind_time_stamp

# Time binding is separate from name binding to keep those program
# parts separated -- necessary when storing in dicts() and across
# multiple lists.

def ie_lookup(self, name):
    '''
    Incremental evaluation lookup.
    Find name in self or any enclosing *defining* (not calling) environment.
     Returns:
       None                when no binding is found
       (value, timestamp)  otherwise
    '''
    if glbl.L3_TRACE:
        l3_trace("ie_lookup", str(self))
    if self._has_key(name):
        status = self._bindings.get( (name, 'ie_status') )
        if status is None:
            status = ie_external_time    # Force eval of parent
        if glbl.L3_TRACE:
            l3_trace("ie_lookup", "found %s" % name)
        return self._get_val(name), status
    else:
        if self._def_env_id is None:
            return None
        else:
            return self._storage.load(self._def_env_id).ie_lookup(name)
Env.ie_lookup = ie_lookup


def ie_lookup_1(self, name):
    '''
    Find name in self only.
    Return:
       None                when no binding is found
       (value, timestamp)  otherwise
    '''
    if self._has_key(name):
        status = self._bindings.get( (name, 'ie_status') )
        if status is None:
            status = ie_external_time    # Force eval of parent
        return self._get_val(name), status
    else:
        return None
Env.ie_lookup_1 = ie_lookup_1


def find_unstamped(self):
    # Find bindings w/o time stamp.
    from types import TupleType
    dct = self._bindings
    unstamped = []
    for k, v in dct.iteritems():
        if isinstance(k, TupleType): continue
        if dct.has_key( (k, 'ie_status') ): continue
        unstamped.append( (k, v) )
    return unstamped
Env.find_unstamped = find_unstamped

#
#**        python connection
def import_all_names(self,  module):
    '''
    Import all Python names (not __...__  specials) from the named
    module into this environment.  All are given an "external" time stamp. 
    '''
    if isinstance(module, StringType):
        exec('import ' + module)
        for name in dir(eval(module)):
            if name.startswith('__'):
                continue
            self.bind_mem_only_ptr(name, eval(module + '.' + name),
                                   ptr_external_id)
            self.bind_time_stamp_ptr(name, ie_external_time, ptr_external_id)

    elif isinstance(module, DictType):
        for name in module.iterkeys():
            if name.startswith('__'):
                continue
            self.bind_mem_only_ptr(name, module[name], ptr_external_id)
            self.bind_time_stamp_ptr(name, ie_external_time, ptr_external_id)
    else:
        for name in dir(module):
            if name.startswith('__'):
                continue
            self.bind_mem_only_ptr(name, module.__dict__[name],
                                   ptr_external_id) 
            self.bind_time_stamp_ptr(name, ie_external_time,
                                     ptr_external_id) 
Env.import_all_names = import_all_names

def import_names(self,  module, name_list):
    '''
    Import specified Python names from the named module into this
    environment.
    '''
    if isinstance(module, StringType):
        exec('import ' + module)
        for name in dir(eval(module)):
            if name in name_list:
                self.bind_mem_only_ptr(name, eval(module + '.' + name),
                                       ptr_external_id) 
                self.bind_time_stamp_ptr(name, ie_external_time,
                                         ptr_external_id) 
    else:
        for name in dir(module):
            if name in name_list:
                self.bind_mem_only_ptr(name, eval(module + '.' + name),
                                       ptr_external_id) 
                self.bind_time_stamp_ptr(name, ie_external_time,
                                         ptr_external_id) 
Env.import_names = import_names

def import_module(self, module):
    '''
    Import the named Python module into this environment.
    '''
    assert isinstance(module, StringType)
    exec('import ' + module)
    lead_name = module.split(".")[0]
    self.bind_mem_only_ptr(lead_name, eval(lead_name), ptr_external_id) 
    self.bind_time_stamp_ptr(lead_name, ie_external_time,
                             ptr_external_id) 
Env.import_module = import_module


def import_def(self, name, py_global):
    '''
    Import the Python binding into this environment.
    '''
    assert isinstance(name, StringType)
    self.bind_mem_only_ptr(name, eval(name, py_global), ptr_external_id) 
    self.bind_time_stamp_ptr(name, ie_external_time, ptr_external_id) 
Env.import_def = import_def


def import_external(self, name, obj):
    '''
    Import the obj into this environment as a constant.
    '''
    self.bind_mem_only_ptr(name, obj, ptr_external_id) 
    self.bind_time_stamp_ptr(name, ie_external_time, ptr_external_id) 
Env.import_external = import_external
Env.import_constant = import_external

#
#**        shell connection
def into_directory(self):
    # os.chdir to the directory corresponding to `self`, collect file
    # information, and return the name of the directory.

    name = 'Subdir-' + str(self._id)
    # Create the directory if it doesn't exist yet.
    if not os.path.isdir(name):
        glbl.logger.info("Adding subdirectory %s\n" % name)
        os.mkdir(name)
    self._dir_stack.append(os.getcwd())
    os.chdir(name)
    self._dir_name = name
    return name
Env.into_directory = into_directory


def directory_name(self):
    return 'Subdir-' + str(self._id)
Env.directory_name = directory_name
Env.l3_dirname = directory_name


def outof_directory(self):
    # Collect new file information from current directory.
    # Change to the previous working directory.
    
    # Collect new file information from current directory.
    known = self._dir_known
    visited = {}

    # File names need to be accessible as l3 identifiers.  For this,
    # characters other than [A-Z][a-z][0-9]_ are mapped to the _;
    # [todo: name collisions are avoided via a number suffix if necessary.]

    # To get consistent renaming, file names could be traversed in
    # alphabetical order, but this would not help when using
    # incremental evaluation. 
    regex = re.compile(r'[^A-Za-z0-9_]', re.IGNORECASE)
    for name in os.listdir(os.getcwd()):
        id_name = regex.sub('_', name)
        if known.has_key(name): continue
        if known.has_key(id_name):
            glbl.logger.warn("File %s maps to already used identifier %s.",
                             (name, id_name))
        # Only include new files.  [todo: warn about modified files]
        self.bind_ptr(name, String(os.path.abspath(name)), self._id)
        self.bind_time_stamp_ptr(name, self._storage.ie_.time(), self._id)
        # Provide identifier bindings 
        self.bind_ptr(id_name, String(os.path.abspath(name)), self._id)
        self.bind_time_stamp_ptr(id_name, self._storage.ie_.time(), self._id)
        visited[name] = None
    known.update(visited)

    # Restore working directory. 
    prev = self._dir_stack.pop()
    os.chdir(prev)

    return
Env.outof_directory = outof_directory

#
#** interactive use shortcuts
# (file content) display a binding's value
Env.cat = Env.ie_lookup_ptr

# file listing 
Env.ls = Env.print_tree