adapton 0.3.31

/*! Adapton's core calculus, implemented as a runtime library.  We
implement two versions of this interface, which we refer to as
_engines_: The **naive engine** and the **DCG engine**,
implemented based on the algorithms from the Adapton papers.

 **See also:**
The [main module](https://docs.rs/adapton/0/adapton/index.html)
demonstrates the [Adapton programming model](https://docs.rs/adapton/0/adapton/index.html#adapton-programming-model) with examples.

 */

use core::any::TypeId;
use core::marker::PhantomData;

use std::cell::RefCell;
use std::collections::HashMap;
use std::env;
use std::fmt::Debug;
use std::fmt::{Formatter,Result};
use std::fmt;
use std::hash::{Hash,Hasher};
use std::collections::hash_map::DefaultHasher;
use std::mem::replace;
use std::mem::transmute;
use std::rc::Rc;
use std::fmt::Write;

use crate::macros::{ProgPt};
use crate::reflect;

thread_local!(static GLOBALS: RefCell<Globals> = RefCell::new(Globals{engine:Engine::Naive}));
thread_local!(static UNIT_NAME: Name = Name{ hash:0, symbol: Rc::new(NameSym::Unit) });

struct TraceSt { stack:Vec<Box<Vec<reflect::trace::Trace>>>, }

// When this option is set to some, the engine will record a trace of its DCG effects.
thread_local!(static TRACES: RefCell<Option<TraceSt>> = RefCell::new( None ));

fn my_hash<T>(obj: T) -> u64
    where T: Hash
{
    let mut hasher = DefaultHasher::new();
    obj.hash(&mut hasher);
    hasher.finish()
}

/// Reflects the DCG engine, including both the effects of the
/// programs running in it, and the internal effects of the engine
/// cleaning and dirtying the DCG.  For the latter effects, see the
/// `trace` module.
///
/// **Reflected Values**.  Notably, the values in the engine
/// (including the values of mutable and compute nodes, and the values
/// stored on edges between them) are reflected here into a special `Val`
/// type.  Primarily, the distinction between actual Rust values and
/// this reflected `Val` type is what makes the DCG engine "reflected"
/// by the definitions in this module, and not identical to them.
///
/// This module provides an interface used by Adapton Lab to produce
/// HTML visualizations of these internal structures, for
/// experimentation and debugging (namely, the `dcg_reflect_begin` and
/// `dcg_reflect_end` functions).  For the purposes of debugging,
/// visualization and design/exploration, we exploit the reflected
/// version of values to "walk" them, finding their articulations, and
/// walking their values, recursively.

pub mod reflect_dcg {
    use crate::reflect::*;
    pub use crate::parse_val;

    use std::fmt::{Write};
    use super::{TraceSt,TRACES,GLOBALS,Engine};
    use crate::adapton::engine::Name;

    /// Begin a debugging extent in the trace, with associated name and message.
    pub fn debug_begin(n:Option<Name>, msg:Option<String>) {
        super::debug_begin(n, msg)
    }
    /// End a debugging extent started with `debug_begin`.
    pub fn debug_end() {
        super::debug_end()
    }
    /// Insert an optional name and message in the `reflect::trace`
    pub fn debug_effect(n:Option<Name>, msg:Option<String>) {
        super::debug_effect(n, msg)
    }

    
    /// See doc for `write_name`. Returns this output as a string.
    pub fn string_of_name (n:&Name) -> String {
        let mut output = String::from("");  write_name(&mut output, n);  output
    }
    /// See doc for `write_path`. Returns this output as a string.
    pub fn string_of_path (p:&Path) -> String {
        let mut output = String::from("");  write_path(&mut output, &p); output
    }
    /// See doc for `write_loc`. Returns this output as a string.
    pub fn string_of_loc (l:&Loc) -> String {
        let mut output = String::from("");  write_loc (&mut output, &l); output
    }

    /// Write a concise human-readable version of the name (not the
    /// verbose, machine-parsable `Debug` version).
    pub fn write_name<W:Write> (w:&mut W, n:&Name) {
        super::write_namesym(w, &n.symbol).unwrap();
    }

    /// Write a concise human-readable version of the path (not the
    /// verbose, machine-parsable `Debug` version).
    pub fn write_path<W:Write> (w:&mut W, p:&Path) {
        write!(w, "__").unwrap(); // Underscores are valid in CSS class names
        for n in p.iter() {
            write_name(w, n);
            write!(w, "__").unwrap(); // Underscores are valid in CSS class names
        }
    }

    /// Write a concise human-readable version of the location (not the
    /// verbose, machine-parsable `Debug` version).
    pub fn write_loc<W:Write> (w:&mut W, l:&Loc)  {
        write_path(w, &l.path);
        write!(w, "_").unwrap(); // Underscores are valid in CSS class names
        write_name(w, &l.name);
    }
    
    /// Reflect the DCG's internal structure now.  Does not reflect any
    /// engine effects over this DCG (e.g., no cleaning or dirtying),
    /// just the _program effects_ recorded by the DCG's structure.
    /// Returns None if the engine is `Naive` and thus has no reflected
    /// state whatsoever.
    pub fn dcg_reflect_now() -> Option<DCG> {
        GLOBALS.with(|g| {
            match g.borrow().engine {
                Engine::DCG(ref dcg) => Some((*dcg.borrow()).reflect()),
                Engine::Naive => None,
            }
        })
    }

    /// Begin recording (reflections of) DCG effects.  See `dcg_reflect_end()`.
    pub fn dcg_reflect_begin() {
        TRACES.with(|tr| {
            let check = match *tr.borrow() {
                None => true,
                Some(_) => false };
            if check {
                *tr.borrow_mut() = Some(TraceSt{stack:vec![Box::new(vec![])]})
            } else {
                panic!("cannot currently nest calls to dcg_reflect_begin().")
            }
        })
    }

    /// Stop recording (reflections of) DCG effects, and return them as a
    /// forrest (of DCG traces).  See `dcg_reflect_begin()`.
    pub fn dcg_reflect_end() -> Vec<trace::Trace> {
        TRACES.with(|tr| {
            let traces = match *tr.borrow_mut() {
                None => panic!("dcg_reflect_end() without a corresponding dcg_reflect_begin()."),
                Some(ref mut tr) => {
                    // Assert that dcg_effect_(begin/end) are not mismatched.
                    assert_eq!(tr.stack.len(), 1);
                    tr.stack.pop()
                }
            };
            match traces {
                None => unreachable!(),
                Some(traces) => {
                    *tr.borrow_mut() = None;
                    *traces
                }
            }
        })
    }
}
use crate::reflect::Reflect;


//#[macro_export]
macro_rules! dcg_effect_begin {
    ( $eff:expr, $loc:expr, $succ:expr, $has_extent:expr ) => {{
        // The beginning of an effect, with an option extent (nested effects)
        TRACES.with(|tr| {
            match *tr.borrow_mut() {
                None => (),
                // Some ==> We are building a trace
                Some(ref mut ts) => {
                    match ts.stack.last_mut() {
                        None => unreachable!(),
                        Some(ref mut ts) => {
                            ts.push( reflect::trace::Trace{
                                extent: Box::new(vec![]),
                                effect:$eff,
                                edge: reflect::trace::EffectEdge::Fwd(
                                    reflect::trace::Edge{
                                        loc:  $loc.reflect(),
                                        succ: $succ.reflect(),
                                    })})}};
                    if $has_extent {
                        ts.stack.push(Box::new(vec![]))
                    } else { }
                }
            }})
    }}
    ;
    ( $eff:expr, $has_extent:expr ) => {{
        // The beginning of an effect, with an option extent (nested effects)
        TRACES.with(|tr| {
            match *tr.borrow_mut() {
                None => (),
                // Some ==> We are building a trace
                Some(ref mut ts) => {
                    match ts.stack.last_mut() {
                        None => unreachable!(),
                        Some(ref mut ts) => {
                            ts.push( reflect::trace::Trace{
                                extent: Box::new(vec![]),
                                effect:$eff,
                                edge: reflect::trace::EffectEdge::None,
                            })}};
                    if $has_extent {
                        ts.stack.push(Box::new(vec![]))
                    } else { }
                }
            }})
    }}
    ;
    ( $eff:expr, $loc:expr, $succ:expr ) => {{
        dcg_effect_begin!($eff, $loc, $succ, true)
    }}
}

//#[macro_export]
macro_rules! dcg_effect_end {
    () => {{
        // The end of an effects' extent. Operationally, the traces at
        // the top of the stack are popped; they become the extent of the
        // trace at the end (top) of the second top-most sequence of
        // traces.
        TRACES.with(|tr| {
            match *tr.borrow_mut() {
                None => (),
                Some(ref mut tr) => {
                    let trs = tr.stack.pop();
                    match (trs, tr.stack.last_mut()) {
                        (None, _) => unreachable!(),
                        (_, None) => unreachable!(),
                        (Some(parent_extent), Some(trs)) =>
                            match trs.last_mut() {
                                None => unreachable!(),
                                Some(parent) => { assert_eq!(parent.extent.len(), 0);
                                                  parent.extent = parent_extent }
                            }
                    }
                }
            }
        })
    }}
}

macro_rules! dcg_effect {
    ( $eff:expr, $loc:expr, $succ:expr ) => {{
        /// An effect without an extent (without nested effects)
        dcg_effect_begin!($eff, $loc, $succ, false)
    }}
}

macro_rules! current_loc {
    ( $st:expr ) => {{
        match ($st).stack.last() {
            None => None,
            Some(frame) => Some(&frame.loc),
        }
    }}
}


/// Begin a debugging extent in the trace, with associated name and message.
fn debug_begin(n:Option<Name>, msg:Option<String>) {
    dcg_effect_begin!(reflect::trace::Effect::Debug(n, msg), true);
}
/// End a debugging extent started with `debug_begin`.
fn debug_end() {
    dcg_effect_end!();
}
/// Insert an optional name and message in the `reflect::trace`
fn debug_effect(n:Option<Name>, msg:Option<String>) {
    dcg_effect_begin!(reflect::trace::Effect::Debug(n, msg), false);
}

/// *Names*: First-class data that identifies a mutable cell (see
/// `cell`) or a thunk (see `thunk`).  When a name identifies
/// different content over time, it describes *where* incremental
/// changing is occurring, relative to other (unaffected) parts of
/// data structures or computations.
#[derive(PartialEq,Eq,Clone)]
pub struct Name {
    hash : u64, // hash of symbol
    symbol : Rc<NameSym>,
}
impl Debug for Name {
    fn fmt(&self, f:&mut Formatter) -> Result { self.symbol.fmt(f) }
}
impl Hash for Name {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        self.hash.hash(state)
    }
}

// Each location identifies a node in the DCG.
#[derive(PartialEq,Eq,Clone)]
struct Loc {
    hash : u64, // hash of (path,id)
    path : Rc<Path>,
    id   : Rc<ArtId>,
}
impl Debug for Loc {
    fn fmt(&self, f:&mut Formatter) -> Result {
        //write!(f,"{:?}*{:?}",self.path,self.id)
        write!(f,"Loc {{ path:[{:?}], id:{:?} }}", self.path, self.id)
    }
}
impl Hash for Loc {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        self.hash.hash(state)
    }
}
impl reflect::Reflect<reflect::Loc> for Loc {
    fn reflect(&self) -> reflect::Loc {
        reflect::Loc {
            path:self.path.reflect(),
            name:match *self.id {
                ArtId::Structural(ref hash) => name_of_hash64(*hash),
                ArtId::Nominal(ref name) => name.clone(),
            }
        }
    }
}

#[derive(Hash,PartialEq,Eq,Clone)]
enum ArtId {
    /// Identifies an `Art` structurally, based on hashing content.
    Structural(u64),
    /// Identifies an `Art` nominally, based on a programmer-chosen `Name`.
    Nominal(Name),
}

impl Debug for ArtId {
    fn fmt(&self, f:&mut Formatter) -> Result {
        match *self {
            ArtId::Structural(ref hash) => write!(f, "{}", hash),
            ArtId::Nominal(ref name) => write!(f, "{:?}", name),
        }
    }
}

/// Flags control runtime behavior of the DCG.
#[derive(Debug)]
pub struct Flags {
    pub use_purity_optimization : bool,
    /// Ignore the `Nominal` `NameChoice`, and use `Structural` behavior instead
    pub ignore_nominal_use_structural : bool,
    /// After each Adapton operation, check that the DCG is well-formed
    pub check_dcg_is_wf : bool,
    /// Within each well-formedness check, write the DCG to the local filesystem
    pub write_dcg : bool,
    /// Deprecated: At certain points in the Engine's code, write state changes as graph-movie output
    /// TODO: To be replaced with DCG reflection, and reflection-to-filesystem logic.
    pub gmlog_dcg : bool,
}

struct Globals {
    engine: Engine,
}

/// The engine API works in two modes: `Naive` and `DCG`. A `Naive` engine is stateless, whereas the `DCG` is stateful.
#[derive(Debug,Clone)]
pub enum Engine {
    DCG(RefCell<DCG>),
    Naive
}

/// *(DCG) Demanded Computation Graph*: The cache of past computation.
///
/// The DCG consists of private state (a memo table of DCG nodes, a
/// stack of DCG nodes, edges among these nodes, the current
/// namespace, etc.).
#[derive(Debug)]
pub struct DCG {
    pub flags : Flags, // public because I dont want to write / design abstract accessors
    table : HashMap<Rc<Loc>, Box<dyn GraphNode>>,
    stack : Vec<Frame>,
    path  : Rc<Path>,
    //cnt   : Cnt,
    dcg_count : usize,
    dcg_hash  : u64,
}

impl reflect::Reflect<reflect::DCG> for DCG {
    fn reflect(&self) -> reflect::DCG {
        reflect::DCG{
            table:{
                let mut table = HashMap::new();
                for (loc, gn) in self.table.iter() {
                    let _ = table.insert(loc.reflect(), gn.reflect());
                }; table
            },
            stack:self.stack.iter()
                .map(|ref frame| frame.reflect() )
                .collect::<Vec<_>>(),
            path:self.path.reflect(),
        }
    }
}

impl Hash  for     DCG { fn hash<H>(&self, _state: &mut H) where H: Hasher { unimplemented!() }}
impl Eq    for     DCG { }
impl PartialEq for DCG { fn eq(&self, _other:&Self) -> bool { unimplemented!() } }
impl Clone for     DCG { fn clone(&self) -> Self { unimplemented!() } }

/// Name symbols.
///
/// For a core-calculus of names in this context, see this document:
/// https://arxiv.org/abs/1610.00097 (Typed Adapton: Refinement types
/// for nominal memoization).
///
/// For a general semantics of symbols, see Chapter 31 of PFPL 2nd
/// Edition. Harper 2016: http://www.cs.cmu.edu/~rwh/pfpl
#[derive(Hash,PartialEq,Eq,Clone,Debug)]
enum NameSym {
    Unit,           // Unit value for name symbols
    Hash64,        // Hashes (for structural names); hash stored in name struct
    String(String), // Strings encode globally-unique symbols.
    Usize(usize),   // USizes encode globally-unique symbols.
    Isize(isize),   // USizes encode globally-unique symbols.
    Pair(Rc<NameSym>,Rc<NameSym>), // A pair of unique symbols, interpeted as a symbol, is unique
    ForkL(Rc<NameSym>), // Left projection of a unique symbol is unique
    ForkR(Rc<NameSym>), // Right projection of a unique symbol is unique
}

fn write_namesym<W:Write>(w:&mut W, n:&NameSym) -> Result {
    match *n {
        NameSym::Unit => write!(w, "▲"),
        NameSym::Hash64 => write!(w, "(Hash64)"),
        NameSym::String(ref s) => write!(w, "{}", s),
        NameSym::Usize(ref n) => write!(w, "{}", n),
        NameSym::Isize(ref n) => write!(w, "{}", n),
        NameSym::Pair(ref l, ref r) => { write_namesym(w, l).unwrap(); write!(w, "-").unwrap(); write_namesym(w, r) },
        NameSym::ForkL(ref s) => { write_namesym(w, s).unwrap(); write!(w, "-l") },
        NameSym::ForkR(ref s) => { write_namesym(w, s).unwrap(); write!(w, "-r") },
    }
}

// Paths are built implicitly via the Adapton::ns command.
#[derive(Hash,PartialEq,Eq,Clone)]
enum Path {
    Empty,
    Child(Rc<Path>,Name),
}
impl reflect::Reflect<reflect::Path> for Path {
    fn reflect(&self) -> reflect::Path {
        match *self {
            Path::Empty => vec![],
            Path::Child(ref path, ref name) => {
                let mut p = path.reflect();
                p.push(name.clone());
                p
            }
        }
    }
}

impl Debug for Path {
    fn fmt(&self, f:&mut Formatter) -> Result {
        match *self {
            Path::Empty => write!(f, ""),
            Path::Child(ref p, ref n) => write!(f, "{:?},{:?}", p, n),
        }
    }
}

// The DCG structure consists of `GraphNode`s:
trait GraphNode : Debug + reflect::Reflect<reflect::Node> {
    fn res_typeid      (self:&Self) -> TypeId ;
    fn preds_alloc<'r> (self:&Self) -> Vec<Rc<Loc>> ;
    fn preds_obs<'r>   (self:&Self) -> Vec<(Rc<Loc>, Option<Rc<Box<dyn DCGDep>>>)> ;
    fn preds_insert<'r>(self:&'r mut Self, _: Effect, _: &Rc<Loc>, _: Option<Rc<Box<dyn DCGDep>>>) -> () ;
    fn preds_remove<'r>(self:&'r mut Self, _: &Rc<Loc>) -> () ;
    fn succs_def<'r>   (self:&Self) -> bool ;
    fn succs_mut<'r>   (self:&'r mut Self) -> &'r mut Vec<Succ> ;
    fn succs<'r>       (self:&'r Self) -> &'r Vec<Succ> ;
    fn hash_seeded     (self:&Self, _: u64) -> u64 ;
}

#[derive(Debug,Clone)]
struct Frame {
    loc   : Rc<Loc>,    // The currently-executing node
    succs : Vec<(Succ, Option<Rc<Box<dyn DCGDep>>>)>,  // The currently-executing node's effects (viz., the nodes it demands)
}

impl reflect::Reflect<reflect::Frame> for Frame {
    fn reflect(&self) -> reflect::Frame {
        reflect::Frame{
            loc:self.loc.reflect(),
            succs:self.succs.reflect(),
        }
    }
}

#[derive(Debug,Clone)]
struct Succ {
    dirty  : bool,    // mutated to dirty when loc changes, or any of its successors change
    loc    : Rc<Loc>, // Target of the effect, aka, the successor, by this edge
    effect : Effect,
    dep    : Rc<Box<dyn DCGDep>>, // Abstracted dependency information (e.g., for Observe Effect, the prior observed value)
}

#[derive(Debug,Clone)]
struct Pred {
    loc    : Rc<Loc>, // Source of the effect, aka, the predecessor, by this edge
    effect : Effect,
    /// This `dep` field is None when the predecessor (loc field) is
    /// observing a thunk, and None when the predecessor is _fully_
    /// observing a mutable cell.  When the predecessor partially
    /// observes a mutable cell, this field is Some(dep), where
    /// `dep.dirty(...)` permits the dirtying algorithm of the engine to
    /// check whether the observed value has changed, and whether
    /// dirtying should continue to the predecessors of `loc` .
    dep    : Option<Rc<Box<dyn DCGDep>>>,
}

impl reflect::Reflect<reflect::Succ> for Succ {
    fn reflect(&self) -> reflect::Succ {
        reflect::Succ {
            dirty:self.dirty,
            loc:self.loc.reflect(),
            effect:self.effect.reflect(),
            value:reflect::Val::ValTODO,
            is_dup:false, // XXX -- Actually: Not checked here.
        }
    }
}

impl reflect::Reflect<Vec<reflect::Succ>> for Vec<Succ> {
    fn reflect(&self) -> Vec<reflect::Succ> {
        self.iter().map(|ref x| x.reflect()).collect::<Vec<_>>()
    }
}

impl reflect::Reflect<Vec<reflect::Succ>> for Vec<(Succ, Option<Rc<Box<dyn DCGDep>>>)> {
    fn reflect(&self) -> Vec<reflect::Succ> {
        self.iter().map(|ref x| x.0.reflect()).collect::<Vec<_>>()
    }
}

#[derive(PartialEq,Eq,Debug,Clone,Hash)]
enum Effect {
    Observe,
    Allocate,
}
impl reflect::Reflect<reflect::Effect> for Effect {
    fn reflect(&self) -> reflect::Effect {
        match *self {
            // TODO-Someday: Too many names for the same thing
            // (force/observe/consume, and allocate/alloc/produce).
            Effect::Observe  => reflect::Effect::Force,
            Effect::Allocate => reflect::Effect::Alloc,
        }
    }
}


struct DCGRes {
    // It is always "sound" to set changed=true.  However, when
    // changed=false, dirtying or cleaning can short-circuit further
    // dirtying or reevaluation, respectively.
    changed : bool,
}
// DCGDep abstracts over the value produced by a dependency, as
// well as mechanisms to update and/or re-produce it.
trait DCGDep : Debug {
    fn is_absmap(self:&Self) -> Option<TypeId> ;
    fn dirty (self:&Self, g:&mut DCG,      loc:&Rc<Loc>) -> DCGRes ;
    fn clean (self:&Self, g:&RefCell<DCG>, loc:&Rc<Loc>) -> DCGRes ;
}

impl Hash for Succ {
    fn hash<H>(&self, hasher: &mut H) where H: Hasher {
        self.dirty.hash( hasher );
        self.loc.hash( hasher );
        self.effect.hash( hasher );
    }
}

impl Hash for Pred {
    fn hash<H>(&self, hasher: &mut H) where H: Hasher {
        self.loc.hash( hasher );
        self.effect.hash( hasher );
    }
}


// Structureful (Non-opaque) nodes:
#[allow(dead_code)] // Pure case: not introduced currently.
#[derive(Debug,Hash)]
enum Node<Res> {
    Comp(CompNode<Res>),
    Pure(PureNode<Res>),
    Mut(MutNode<Res>),
}
impl<X:Debug> reflect::Reflect<reflect::Node> for Node<X> {
    fn reflect(&self) -> reflect::Node {
        use crate::parse_val::parse_val;
        match *self {
            Node::Comp(ref n) => {
                reflect::Node::Comp(
                    reflect::CompNode{
                        preds:n.preds.reflect(),
                        succs:n.succs.reflect(),
                        prog_pt:n.producer.prog_pt().clone(),
                        value:match n.res {
                            Some(ref v) => Some( parse_val(v) ),
                            None => None
                        }
                    })
            },
            Node::Pure(ref n) => {
                reflect::Node::Pure(
                    reflect::PureNode {
                        value:parse_val( &n.val ),
                    })
            },
            Node::Mut(ref n) => {
                reflect::Node::Ref(
                    reflect::RefNode {
                        preds:n.preds.reflect(),
                        value:parse_val( &n.val ),
                    })
            },
        }
    }
}

// PureNode<T> for pure hash-consing of T's.
// Location in table never changes value.
#[derive(Debug,Hash)]
struct PureNode<T> {
    val : T,
}

// MutNode<T> for mutable content of type T.
// The set operation mutates a MutNode; set may only be called by *outer* Rust environment.
// Its notable that the CompNodes' producers do not directly change the value of MutNodes with set.
// They may indirectly mutate these nodes by performing nominal allocation; mutation is limited to "one-shot" changes.
#[derive(Debug,Hash)]
struct MutNode<T> {
    preds : Vec<Pred>,
    val   : T,
}

// CompNode<Res> for a suspended computation whose resulting value of
// type T.  The result of the CompNode is affected in two ways: the
// (1) producer may change, which may affect the result and (2) the
// values produced by the successors may change, indirectly
// influencing how the producer produces its resulting value.
struct CompNode<Res> {
    preds    : Vec<Pred>,
    succs    : Vec<Succ>,
    producer : Box<dyn Producer<Res>>, // Producer can be App<Arg,Res>, where type Arg is hidden.
    res      : Option<Res>,
}

impl reflect::Reflect<Vec<reflect::Pred>> for Vec<Pred> {
    fn reflect(&self) -> Vec<reflect::Pred> {
        self.iter().map(|pred|
                        reflect::Pred{
                            effect:pred.effect.reflect(),
                            loc:pred.loc.reflect()
                        }).collect::<Vec<_>>()
    }
}

impl reflect::Reflect<Vec<reflect::Loc>> for Vec<Rc<Loc>> {
    fn reflect(&self) -> Vec<reflect::Loc> {
        self.iter().map(|loc| loc.reflect()).collect::<Vec<_>>()
    }
}


/// A `NameChoice` chooses between `Native`, `Structural` and
/// `Nominal` identities for articulation points introduced by
/// `thunk`.
#[derive(Hash,Debug,PartialEq,Eq,Clone)]
pub enum NameChoice {
    /// Naive: Native Rust thunk, with no caching/reuse of the thunk representation, or its result.
    Naive,
    /// Eager: Special case of `Naive`, with no suspension of the thunk -- the function is called immediately.
    Eager,    
    /// Structurally identify an `Art` based on hashing its content (e.g., `prog_pt` and argument(s)).
    Structural,
    /// Explicitly names an `Art` based on a programmer-chosen name, of type `Name`.
    Nominal(Name),
}

// Produce a value of type Res.
trait Producer<Res> : Debug {
    //  fn produce(self:&Self, st:&mut DCG) -> Res;
    fn produce(self:&Self) -> Res;
    fn copy(self:&Self) -> Box<dyn Producer<Res>>;
    fn eq(self:&Self, other:&dyn Producer<Res>) -> bool;
    fn prog_pt<'r>(self:&'r Self) -> &'r ProgPt;
}
// Consume a value of type Arg.
trait Consumer<Arg> : Debug {
    fn consume(self:&mut Self, _: Arg);
    fn get_arg(self:&mut Self) -> Arg;
}
// struct App is hidden by traits Comp<Res> and CompWithArg<Res>, below.
#[derive(Clone)]
struct App<Arg:Debug,Spurious,Res> {
    prog_pt: ProgPt,
    fn_box:   Rc<Box<dyn Fn(Arg, Spurious) -> Res>>,
    arg:      Arg,
    spurious: Spurious,
}

impl<Arg:Debug,Spurious,Res>
    Debug for
    App<Arg,Spurious,Res>
{
    fn fmt(&self, f: &mut Formatter) -> Result {
        write!(f,"App({:?} {:?})", self.prog_pt, self.arg)
    }
}

impl<Arg:Hash+Debug,Spurious,Res>
    Hash for
    App<Arg,Spurious,Res>
{
    fn hash<H>(&self, state: &mut H) where H: Hasher { (&self.prog_pt,&self.arg).hash(state) }
}

impl<Arg:'static+PartialEq+Eq+Clone+Debug,Spurious:'static+Clone,Res:'static+Debug+Hash>
    Producer<Res> for
    App<Arg,Spurious,Res>
{
    fn produce(self:&Self) -> Res {
        let f = self.fn_box.clone() ;
        let res = f (self.arg.clone(),self.spurious.clone()) ;
        res
    }
    fn copy(self:&Self) -> Box<dyn Producer<Res>> {
        Box::new(App{
            prog_pt:self.prog_pt.clone(),
            fn_box:self.fn_box.clone(),
            arg:self.arg.clone(),
            spurious:self.spurious.clone(),
        })
    }
    fn prog_pt<'r>(self:&'r Self) -> &'r ProgPt {
        & self.prog_pt
    }
    fn eq (&self, other:&dyn Producer<Res>) -> bool {
        if &self.prog_pt == other.prog_pt() {
            let other = Box::new(other) ;
            // This is safe if the prog_pt implies unique Arg and Res types.
            // TODO-Soon: Program points should store argument + result types; we should check these dynamically here
            let other : &Box<App<Arg,Spurious,Res>> = unsafe { transmute::<_,_>( other ) } ;
            self.arg == other.arg
        } else {
            false
        }
    }
}
impl<Arg:Clone+PartialEq+Eq+Debug,Spurious,Res>
    Consumer<Arg> for
    App<Arg,Spurious,Res>
{
    fn consume(self:&mut Self, arg:Arg) { self.arg = arg; }
    fn get_arg(self:&mut Self) -> Arg   { self.arg.clone() }
}

// ----------- Location resolution:

fn lookup_abs<'r>(st:&'r mut DCG, loc:&Rc<Loc>) -> &'r mut Box<dyn GraphNode> {
    match st.table.get_mut( loc ) {
        None => panic!("dangling pointer: {:?}", loc),
        Some(node) => node.be_node() // This is a weird workaround; TODO-Later: Investigate.
    }
}

fn get_top_stack_loc(st:&DCG) -> Option<Rc<Loc>> {
    if st.stack.len() > 0 {
        Some(st.stack.get(st.stack.len() - 1).unwrap().loc.clone())
    } else {
        None
    }
}

fn assert_graphnode_res_type<Res:'static> (loc:&Loc, node:&Box<dyn GraphNode>, top_stack:Option<Rc<Loc>>) {
    let res_typeid = TypeId::of::<Res>();
    let node_res_typeid = node.res_typeid();
    if node_res_typeid != res_typeid {
        let alloc_preds = node.preds_alloc().reflect();
        panic!("\
            Adapton engine: Detected a dynamic type error, possibly due to an ambiguous name:
\t              at location: {:?}
\t    existing allocator(s): {:?}
\tcontext/current allocator: {:?}

\t location has result type: {:?}
\tbut context expected type: {:?}",
               loc, alloc_preds, top_stack.reflect(), node_res_typeid, res_typeid
        );
    }
}

// This function uses 'unsafe' to transmute pointer types. Unintended
// double-uses of names and hashes will cause dynamic type errors, via
// assert_graphnode_res_type.
fn res_node_of_loc<'r,Res:'static> (st:&'r mut DCG, loc:&Rc<Loc>) -> &'r mut Box<Node<Res>> {
    let top_loc = get_top_stack_loc(st) ;
    let abs_node = lookup_abs(st, loc) ;
    assert_graphnode_res_type::<Res>(&*loc, abs_node, top_loc);
    unsafe { transmute::<_,_>(abs_node) }
}

// ---------- Node implementation:

impl <Res:'static+Debug+Hash> GraphNode for Node<Res> {

    fn res_typeid(self:&Self) -> TypeId {
        return TypeId::of::<Res>()
    }

    fn preds_alloc(self:&Self) -> Vec<Rc<Loc>> {
        match *self { Node::Mut(ref nd) => nd.preds.iter().filter_map(|pred| if pred.effect == Effect::Allocate { Some(pred.loc.clone()) } else { None } ).collect::<Vec<_>>(),
                      Node::Comp(ref nd) => nd.preds.iter().filter_map(|pred| if pred.effect == Effect::Allocate { Some(pred.loc.clone()) } else { None } ).collect::<Vec<_>>(),
                      Node::Pure(_) => unreachable!(),
        }}

    fn preds_obs(self:&Self) -> Vec<(Rc<Loc>, Option<Rc<Box<dyn DCGDep>>>)> {
        match *self {
            Node::Mut(ref nd) =>
                nd.preds.iter().filter_map(
                    |pred|
                    if pred.effect == Effect::Observe { Some((pred.loc.clone(), pred.dep.clone())) }
                    else { None }
                ).collect::<Vec<_>>(),

            Node::Comp(ref nd) =>
                nd.preds.iter().filter_map(
                    |pred|
                    if pred.effect == Effect::Observe { Some((pred.loc.clone(), None)) }
                    else { None }
                ).collect::<Vec<_>>(),

            Node::Pure(_) => unreachable!(),
        }}
    fn preds_insert (self:&mut Self, eff:Effect, loc:&Rc<Loc>, dep:Option<Rc<Box<dyn DCGDep>>>) -> () {
        match *self { Node::Mut(ref mut nd) => nd.preds.push (Pred{effect:eff,loc:loc.clone(),dep:dep.clone()}),
                      Node::Comp(ref mut nd) => nd.preds.push (Pred{effect:eff,loc:loc.clone(),dep:dep.clone()}),
                      Node::Pure(_) => unreachable!(),
        }}
    fn preds_remove (self:&mut Self, loc:&Rc<Loc>) -> () {
        match *self { Node::Mut(ref mut nd) => nd.preds.retain (|pred|{ &pred.loc != loc}),
                      Node::Comp(ref mut nd) => nd.preds.retain (|pred|{ &pred.loc != loc}),
                      Node::Pure(_) => unreachable!(),
        }}
    fn succs_def(self:&Self) -> bool {
        match *self { Node::Comp(_) => true, _ => false
        }}
    fn succs_mut<'r>(self:&'r mut Self) -> &'r mut Vec<Succ> {
        match *self { Node::Comp(ref mut n) => &mut n.succs,
                      _ => panic!("undefined"),
        }
    }
    fn succs<'r>(self:&'r Self) -> &'r Vec<Succ> {
        match *self { Node::Comp(ref n) => &n.succs,
                      _ => panic!("undefined"),
        }
    }
    fn hash_seeded(self:&Self, seed:u64) -> u64 {
        let mut hasher = DefaultHasher::new();
        seed.hash(&mut hasher);
        self.hash(&mut hasher);
        hasher.finish()
    }
}

trait ShapeShifter {
    fn be_node<'r> (self:&'r mut Self) -> &'r mut Box<dyn GraphNode> ;
}

impl <Res> ShapeShifter for Box<Node<Res>> {
    fn be_node<'r>(self:&'r mut Self) -> &'r mut Box<dyn GraphNode> {
        // TODO-Later: Why is this transmute needed here ??
        unsafe { transmute::<_,_>(self) }
    }
}

impl ShapeShifter for Box<dyn GraphNode> {
    fn be_node<'r>(self:&'r mut Self) -> &'r mut Box<dyn GraphNode> {
        // TODO-Later: Why is this transmute needed here ??
        unsafe { transmute::<_,_>(self) }
    }
}

impl<Res> fmt::Debug for CompNode<Res> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        //write!(f, "(CompNode)")
        write!(f, "{:?}", self.producer)
    }
}

impl<Res:Hash> Hash for CompNode<Res> {
    fn hash<H:Hasher>(&self, h: &mut H) {
        self.preds.hash(h);
        self.succs.hash(h);
        self.res.hash(h);
        (format!("{:?}",self.producer)).hash(h); // Todo-Later: This defines hash value based on debug string for producer.
    }
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
/// CLEANING and DIRTYING (aka "CHANGE PROPAGATION"), including
/// re-evaluation.
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

/// Re-evaluation: `loc_produce` performs the computation at `loc`,
/// and produces a result of type `Res`.  Error if `loc` is not a
/// `Node::Comp`.
fn loc_produce<Res:'static+Debug+PartialEq+Eq+Clone+Hash>(g:&RefCell<DCG>, loc:&Rc<Loc>) -> Res
{
    let (producer, prev_path) = {
        let st : &mut DCG = &mut *g.borrow_mut() ;
        let succs : Vec<Succ> = {
            let succs : Vec<Succ> = Vec::new();
            let node : &mut Node<Res> = res_node_of_loc( st, loc ) ;
            replace(node.succs_mut(), succs)
        } ;
        revoke_succs( st, loc, &succs );
        st.stack.push ( Frame{loc:loc.clone(), succs:Vec::new(), } );
        //st.cnt.stack = if st.cnt.stack > st.stack.len() { st.cnt.stack } else { st.stack.len() } ;
        let prev_path = st.path.clone () ;
        st.path = loc.path.clone() ;
        let producer : Box<dyn Producer<Res>> = {
            let node : &mut Node<Res> = res_node_of_loc( st, loc ) ;
            match *node {
                Node::Comp(ref nd) => nd.producer.copy(),
                _ => panic!("internal error"),
            }
        } ;
        //st.cnt.eval += 1 ;
        drop(st);  // End mutable borrow of global RefCell
        (producer, prev_path)
    };
    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    // Invoke producer: Run the user's code, and get a result.
    // Critical note: This call will generally call back into this
    // engine library.  That's why we end the mutable borrow of `g`
    // above, before making this call.  We re-borrow `g` below, when
    // the call is complete.
    let res = producer.produce() ;
    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    let st = &mut * g.borrow_mut() ;
    st.path = prev_path ;
    let frame = match st.stack.pop() {
        None => panic!("expected Some _: stack invariants are broken"),
        Some(frame) => frame
    } ;
    assert!( &frame.loc == loc );
    for succ in &frame.succs {
        if succ.0.dirty {
            // This case witnesses an illegal use of nominal side effects
            panic!("invariants broken: newly-built DCG edge should be clean, but is dirty.")
        } ;
        let succ_node = lookup_abs( st, &succ.0.loc );
        succ_node.preds_insert( succ.0.effect.clone(), loc, succ.1.clone() );
    } ;
    {
        let node : &mut Node<Res> = res_node_of_loc( st, loc ) ;
        match *node {
            Node::Comp(ref mut node) => {
                replace(&mut node.succs, frame.succs.into_iter().map(|(succ,_)|succ).collect() ) ;
                replace(&mut node.res, Some(res.clone()))
            },
            _ => panic!("internal error"),
        }
    } ;
    res
}

fn clean_comp<Res:'static+Sized+Debug+PartialEq+Clone+Eq+Hash>
    (g:&RefCell<DCG>,
     this_dep:&ForceDep<Res>,
     loc:&Rc<Loc>, cache:Res, succs:Vec<Succ>) -> DCGRes
{
    for succ in succs.iter() {
        let dirty = {
            let st = &mut *g.borrow_mut();
            get_succ_mut(st, loc, succ.effect.clone(), &succ.loc).dirty
        } ;
        if dirty {
            dcg_effect_begin!(reflect::trace::Effect::CleanRec, Some(loc), succ);
            let succ_dep = & succ.dep ;
            let res = succ_dep.clean(g, &succ.loc) ;
            if res.changed {
                dcg_effect_begin!(reflect::trace::Effect::CleanEval, Some(loc), succ);
                let result : Res = loc_produce( g, loc ) ;
                dcg_effect_end!();
                let changed = result != this_dep.res ;
                dcg_effect_end!();
                return DCGRes{changed:changed}
            }
            else {
                let st : &mut DCG = &mut *g.borrow_mut();
                //st.cnt.clean += 1 ;
                get_succ_mut(st, loc, succ.effect.clone(), &succ.loc).dirty = false ;
                dcg_effect!(reflect::trace::Effect::CleanEdge, Some(loc), succ);
            }
            dcg_effect_end!();
        }
    } ;
    let changed = this_dep.res != cache ;
    DCGRes{changed:changed}
}

#[derive(Debug)]
struct AllocStructuralThunk;
impl DCGDep for AllocStructuralThunk {
    fn is_absmap (&self) -> Option<TypeId> { None }
    fn dirty (self:&Self, _g:&mut DCG,      _loc:&Rc<Loc>) -> DCGRes { DCGRes{changed:true} }
    fn clean (self:&Self, _g:&RefCell<DCG>, _loc:&Rc<Loc>) -> DCGRes { DCGRes{changed:false} }
}

#[derive(Debug)]
struct AllocNominalThunk<T> { val:T }
impl<T:Debug> DCGDep for AllocNominalThunk<T> {
    fn is_absmap (&self) -> Option<TypeId> { None }
    fn dirty (self:&Self, _g:&mut DCG,      _loc:&Rc<Loc>) -> DCGRes { DCGRes{changed:true} }
    fn clean (self:&Self, _g:&RefCell<DCG>, _loc:&Rc<Loc>) -> DCGRes { DCGRes{changed:true} } // TODO-Later: Make this a little better.
}

#[derive(Debug)]
struct AllocCell<T> { val:T }
impl<T:Debug> DCGDep for AllocCell<T> {
    fn is_absmap (&self) -> Option<TypeId> { None }
    fn dirty (self:&Self, _g:&mut DCG,      _loc:&Rc<Loc>) -> DCGRes { DCGRes{changed:true} }
    fn clean (self:&Self, _g:&RefCell<DCG>, _loc:&Rc<Loc>) -> DCGRes { DCGRes{changed:true} } // TODO-Later: Make this a little better.
}

/// The structure implements DCGDep, caching a value of type `T` to
/// compare against future values.
#[derive(Debug)]
struct ForceDep<T:Debug> { res:T }

/// The structure implements DCGDep, caching a value of type `S` to
/// compare against future values (note that values of type `S`
/// typically have less information than their preimages of type `T`).
struct ForceMapDep<T,S,F:Fn(&Art<T>, T)->S> { raw:PhantomData<T>, mapf:F, res:S }

/// A family of mappings, with a notion of member subsets via abstract
/// mappings.  These abstractions _compress_ sequences of observations
/// into a single DCG force edge. See also: `force_abs`.
///
/// Specifically, we abstract sets of edges when the source thunk and
/// target cell are the same two nodes, and the same abstract mapping
/// family is used throughout.
///
/// Each mapping family uses several type parameters in its definition:
///
///   - The family maps values of type `T` to values of type `S`
///   - Each mapping in the family is identified by a distinct `Arg` value.
///   - Each _abstract_ mapping in the family is identified by a
///     distinct `Abs` value; this `Abs` value represents _a set of_
///     `Arg` values, and likewise, a set of mappings in the family.
///   - The family represents (possibly abstracted) _differences_ in
///     type `T` as values of type `DiffT`.
///
/// Based on these types, the family defines:
///
///   - mappings (`fn map`),
///   - mapping abstraction (`fn abs`),
///   - joins over abstract mappings (`fn join`),
///   - differencing mapping inputs (`fn diff`),
///   - and intersecting differenced inputs and abstracted mappings (`fn is_dirty`).
///
///
/// TODO: What conditions should hold for an implementation of AbsMap to be sound?
///
pub trait AbsMapFam<Arg,Abs,T,DiffT,S> {
    /// using an `Arg`, map a value of type `T` into one of type `S`
    fn map (&self, arg:Arg, inp:T) -> S;

    /// make a concrete mapping argument of type `Arg` into an abstracted one of type `Abs`
    fn abs (&self, arg:Arg) -> Abs;
    /// lattice join operation over two abstracted mappings (intersect `fst` and `snd`)
    fn join (&self, fst:Abs, snd:Abs) -> Abs;
    /// represent the difference between two values of type `T`, perhaps abstractly, as a value of type `DiffT`.
    fn diff(&self, fst:&T, snd:&T) -> DiffT;
    /// intersect the difference in `T` values (of type `DiffT`) with the abstract mapping; return true if non-empty.
    fn is_dirty(&self, diff:DiffT, abs:&Abs) -> bool;
}

/// The engine uses trait `AbsDiff` to hide the type arguments of
/// AbsMapFam, except for the input type, `T`, which we expose to
/// define a notion of differences.
trait AbsDiff<T> {
    fn is_diff_dirty(&self, fst:&T, snd:&T) -> bool ;
}

/// The structure implements DCGDep, caching a value of type `S`, the
/// result of applying a (possibly merged, and thus abstracted)
/// mapping function `abs`.
struct ForceAbsDep<Arg,Abs,T,DiffT,S> {
    /// types that we do not instantiate here; we only store an `Abs` here
    phm:PhantomData<(Arg,T,DiffT,S)>,
    /// abstract mapping, so we can re-map via `map.1.map(map.0,_)`
    map:(Abs, Box<dyn AbsMapFam<Arg,Abs,T,DiffT,S>>),
}

impl<Arg,Abs,T:'static,DiffT,S> AbsDiff<T> for ForceAbsDep<Arg,Abs,T,DiffT,S> {
    fn is_diff_dirty(self:&Self, fst:&T, snd:&T) -> bool {
        let diff = self.map.1.diff(fst, snd);
        self.map.1.is_dirty(diff, &self.map.0)
    }
}

impl<Arg:'static,   // identifies a concrete mapping in the family
     Abs:'static,   // identifies an abstract mapping: a _set_ of concrete mappings
     T:'static,     // the mapping input
     DiffT:'static, // differences in the mapping input
     S:'static      // the mapping output
     >
    DCGDep for
    ForceAbsDep<Arg,Abs,T,DiffT,S>
{
    fn is_absmap(self:&Self) -> Option<TypeId> {
        Some(TypeId::of::<Self>())
    }
    fn dirty (self:&Self, _g:&mut DCG, _loc:&Rc<Loc>) -> DCGRes {
        unimplemented!()
    }
    fn clean (self:&Self, _g:&RefCell<DCG>, _loc:&Rc<Loc>) -> DCGRes {
        // the edge is dirty because we've already determined it
        // should be, via an abstract test (`fn is_dirty` on the
        // AbsMapFam trait).  We could try to re-run this test _now_,
        // but we don't have the old value of the observation in hand,
        // and would like to avoid storing it on the edge.
        DCGRes{ changed: true }
    }
}

impl <Arg,Abs,T,DiffT,S> Debug for ForceAbsDep<Arg,Abs,T,DiffT,S>
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        // TODO-Later: We dont print the mapping function here
        write!(f, "ForceAbsDep(?)")
    }
}


fn check_force_map_dep
    <T:'static+Sized+Debug+PartialEq+Eq+Clone+Hash,
     S:'static+Sized+Debug+PartialEq+Eq+Clone+Hash,
     F:Fn(&Art<T>, T)->S>
    (st:&mut DCG, dep:&ForceMapDep<T,S,F>, loc:&Rc<Loc>) -> DCGRes
{
    let node : &mut Node<T> = res_node_of_loc(st, loc) ;
    match *node {
        Node::Mut(ref nd) =>
            DCGRes{changed:dep.res != (dep.mapf)
                   (&Art{art:EnumArt::Loc(loc.clone())},
                    nd.val.clone())},

        Node::Comp(_) | Node::Pure(_) =>
            unreachable!()
    }
}

impl <T:'static+Sized+Debug+PartialEq+Eq+Clone+Hash,
      S:'static+Sized+Debug+PartialEq+Eq+Clone+Hash, F:Fn(&Art<T>, T)->S>
    DCGDep for ForceMapDep<T,S,F>
{
    fn is_absmap(self:&Self) -> Option<TypeId> {
        None
    }
    fn dirty(self:&Self, g:&mut DCG, loc:&Rc<Loc>) -> DCGRes {
        check_force_map_dep(g, self, loc)
    }
    fn clean(self:&Self, g:&RefCell<DCG>, loc:&Rc<Loc>) -> DCGRes {
        check_force_map_dep(&mut *g.borrow_mut(), self, loc)
    }
}

impl <T:'static+Sized+Debug+PartialEq+Eq+Clone+Hash,
      S:'static+Sized+Debug+PartialEq+Eq+Clone+Hash, F:Fn(&Art<T>, T)->S>
    Debug for ForceMapDep<T,S,F>
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        // TODO-Later: We dont print the mapping function here
        write!(f, "ForceMapDep({:?})", self.res)
    }
}



impl <Res:'static+Sized+Debug+PartialEq+Eq+Clone+Hash>
    DCGDep for ForceDep<Res>
{
    fn is_absmap(self:&Self) -> Option<TypeId> {
        None
    }

    fn dirty(self:&Self, _g:&mut DCG, _loc:&Rc<Loc>) -> DCGRes {
        DCGRes{changed:true}
    }

    fn clean(self:&Self, g:&RefCell<DCG>, loc:&Rc<Loc>) -> DCGRes {
        let res_succs = { // Handle cases where there is no internal computation to re-compute:
            let st = &mut *g.borrow_mut();
            let node : &mut Node<Res> = res_node_of_loc(st, loc) ;
            match *node {
                Node::Comp(ref nd) => {
                    match nd.res {
                        Some(ref res) => Some((res.clone(), nd.succs.clone ())),
                        None => None
                    }},
                Node::Pure(_) => {
                    return DCGRes{changed:false}
                },
                Node::Mut(ref nd) => {
                    return DCGRes{changed:nd.val != self.res}
                },
            }
        } ;
        let none : Option<Loc> = None ;
        match res_succs {
            Some((res,succs)) => clean_comp(g, self, loc, res, succs),
            None => {
                dcg_effect_begin!(
                    reflect::trace::Effect::CleanEval,
                    none,
                    reflect::Succ{
                        loc:loc.reflect(),
                        dirty:true,
                        effect:reflect::Effect::Force,
                        value:reflect::Val::ValTODO,
                        is_dup:false, // XXX -- Actually: Not checked here.
                    }
                );
                let res = loc_produce( g, loc );
                let changed = self.res != res ;
                // TODO: changed to reflect::trace somehow?
                dcg_effect_end!();
                DCGRes{changed:changed}
            }
        }
    }
}

// ---------- Node implementation:

fn revoke_succs<'x> (st:&mut DCG, src:&Rc<Loc>, succs:&Vec<Succ>) {
    //let mut succ_idx = 0;
    for succ in succs.iter() {
        dcg_effect!(reflect::trace::Effect::Remove, Some(src), succ);
        let succ_node : &mut Box<dyn GraphNode> = lookup_abs(st, &succ.loc) ;
        succ_node.preds_remove(src)
    }
}

fn loc_of_id(path:Rc<Path>,id:Rc<ArtId>) -> Rc<Loc> {
    let hash = my_hash(&(&path,&id));
    Rc::new(Loc{path:path,id:id,hash:hash})
}

fn get_succ<'r>(st:&'r DCG, src_loc:&Rc<Loc>, eff:Effect, tgt_loc:&Rc<Loc>) -> &'r Succ {
    let nd = st.table.get(src_loc);
    let nd = match nd {
        None => panic!(""),
        Some(nd) => nd
    } ;
    for succ in nd.succs() {
        if (succ.effect == eff) && (&succ.loc == tgt_loc) {
            return succ
        } else {}
    } ;
    panic!("tgt_loc is dangling in src_node.dem_succs")
}

// Implement "sharing" of the dirty bit.
// The succ edge is returned as a mutable borrow, to permit checking
// and mutating the dirty bit.
fn get_succ_mut<'r>(st:&'r mut DCG, src_loc:&Rc<Loc>, eff:Effect, tgt_loc:&Rc<Loc>) -> &'r mut Succ {
    let nd = lookup_abs( st, src_loc );
    for succ in nd.succs_mut().iter_mut() {
        if (succ.effect == eff) && (&succ.loc == tgt_loc) {
            return succ
        } else {}
    } ;
    panic!("tgt_loc is dangling in src_node.dem_succs")
}

fn dirty_pred_observers(st:&mut DCG, loc:&Rc<Loc>) {
    let pred_locs : Vec<(Rc<Loc>, Option<Rc<Box<dyn DCGDep>>>)> = lookup_abs( st, loc ).preds_obs() ;
    for (pred_loc, dep) in pred_locs {
        let stop : bool = match dep {
            None => false,
            Some(dep) => dep.is_absmap() != None || dep.dirty(st, loc).changed == false
        };
        let stop : bool = if stop { true } else {
            // The stop bit communicates information from st for use below.
            let succ = get_succ_mut(st, &pred_loc, Effect::Observe, &loc) ;
            if succ.dirty { true } else {
                assert!(&pred_loc != loc);
                dcg_effect_begin!(reflect::trace::Effect::Dirty, Some(&pred_loc), succ);
                replace(&mut succ.dirty, true);
                false
            }}
        ;
        if !stop {
            dirty_pred_observers(st,&pred_loc);
            dcg_effect_end!();
        } else { }
    }
}

fn dirty_alloc(st:&mut DCG, loc:&Rc<Loc>) {
    dirty_pred_observers(st, loc);
    let pred_locs : Vec<Rc<Loc>> = lookup_abs(st, loc).preds_alloc() ;
    for pred_loc in pred_locs {
        let stop : bool = {
            // The stop bit communicates information from st for use below.
            let succ = get_succ_mut(st, &pred_loc, Effect::Allocate, &loc) ;
            if succ.dirty { true } else {
                replace(&mut succ.dirty, true);
                assert!(&pred_loc != loc);
                dcg_effect_begin!(reflect::trace::Effect::Dirty, Some(&pred_loc), succ);
                false
            }} ;
        if !stop {
            dirty_pred_observers(st,&pred_loc);
            dcg_effect_end!();
        } else {  }
    }
    if false /* XXX Check make this better, as a statically/dynamically-set flag? */ {
        wf::check_stack_is_clean(st)
    }
}

/// Returns true if changed, false if unchanged.
fn check_cell_change<T:'static+Eq+Debug> (st:&mut DCG, cell:AbsArt<T,Loc>, val:&T) -> bool {
    if let AbsArt::Loc(ref loc) = cell {
        let node = res_node_of_loc::<T>( st, loc ) ;
        match **node {
            Node::Mut(ref mut nd) => { &nd.val != val }
            _ => { /* the location was previously _not_ a cell, so yes */ true }
        }
    }
    else { panic!("{:?} is not a cell", cell) }
}

/// Returns true if changed, false if unchanged.
fn set_<T:'static+Eq+Debug> (st:&mut DCG, cell:AbsArt<T,Loc>, val:T) {
    if let AbsArt::Loc(ref loc) = cell {
        let changed : bool = {
            let node = res_node_of_loc( st, loc ) ;
            match **node {
                Node::Mut(ref mut nd) => {
                    if nd.val == val {
                        false
                    } else {
                        replace(&mut nd.val, val) ;
                        // know types: T.
                        // Don't know: Arg, Abs, DiffT, S
                        // ==> need a new dep operation
                        //
                        // XXX: For each predecessor that is an abstract map,
                        // diff nd.val and val using its diff function, and call
                        // is_dirty to determine a boolean.  If true, mark the
                        // edge dirty and call dirty_pred_observers on the
                        // source. Otherwise, if false, mark the edge clean (not
                        // dirty).
                        true
                    }},
                _ => unreachable!(),
            }
        };
        if changed {
            // TODO: Dirtying isn't quite necessary for *all* allocations.
            // Only those that allocated a different value than the present
            // one--- we should check this, but we do not (we are *too
            // conservative* at present).
            dirty_alloc(st, loc);
        }
    }
    else { panic!("{:?} is not a cell", cell) }
}


fn current_path (st:&DCG) -> Rc<Path> {
    st.path.clone()
}

/// The term "Art" stands for two things here: "Adapton ref/thunk",
/// and "Articulation point, for 'articulating' incremental change".
/// The concept of an "Art" also abstracts over whether the producer
/// is eager (like a ref cell) or lazy (like a thunk).
#[derive(Hash,Debug,PartialEq,Eq,Clone)]
enum AbsArt<T,Loc> {
    Rc(Rc<T>),    // No entry in table. No dependency tracking.
    Loc(Rc<Loc>), // Location in table.
}

/// The `Adapton` trait provides a language of
/// dependence-graph-building operations based on the core calculus
/// described in ["Incremental Computation with Names", 2015](http://arxiv.org/abs/1503.07792)
trait Adapton : Debug+PartialEq+Eq+Hash+Clone {
    type Loc  : Debug+PartialEq+Eq+Hash+Clone;

    fn new () -> Self ;

    /// Creates or re-enters a given namespace; performs the given computation there.
    fn ns<T,F> (g: &RefCell<DCG>, _: Name, body:F) -> T where F:FnOnce() -> T;

    /// Enters a special "namespace" where all name uses are ignored; instead, Adapton uses structural identity.
    fn structural<T,F> (g: &RefCell<DCG>, body:F) -> T where F:FnOnce() -> T;

    /// Creates immutable, eager articulation.
    fn put<T:Eq+Debug+Clone> (self:&mut Self, _: T) -> AbsArt<T,Self::Loc> ;

    /// Creates a mutable articulation.
    fn cell<T:Eq+Debug+Clone+Hash+'static> (self:&mut Self, _: Name, _: T) -> AbsArt<T,Self::Loc> ;

    /// Mutates a mutable articulation.
    fn set<T:'static+Eq+Debug+Clone> (self:&mut Self, _: AbsArt<T,Self::Loc>, _: T) ;

    /// Creates an articulated computation.
    fn thunk <Arg:Eq+Hash+Debug+Clone+'static,
              Spurious:Clone+'static,
              Res:Eq+Debug+Clone+Hash+'static
              >
        (self:&mut Self,
         id:NameChoice,
         prog_pt:ProgPt,
         fn_box:Rc<Box< dyn Fn(Arg, Spurious) -> Res >>,
         arg:Arg, spurious:Spurious)
         -> AbsArt<Res,Self::Loc> ;

    /// Demand and observe arts (both thunks and cells)
    ///
    /// cycle_out gives an optional return value for cycles; None means no cycles are permitted
    fn force<T:Eq+Debug+Clone+Hash+'static> (g:&RefCell<DCG>, _: &AbsArt<T,Self::Loc>, _: Option<T>) -> T ;

    /// Demand & observe arts, through a mapping function (e.g., for projections)
    fn force_map<T:Eq+Debug+Clone+Hash+'static,
                 S:Eq+Debug+Clone+Hash+'static,
                 F:'static>
        (g:&RefCell<DCG>, _: &AbsArt<T,Self::Loc>, _: F) -> S
        where F:Fn(&Art<T>, T) -> S
        ;

    /// Demand & observe arts through a family of mappings whose abstractions _compress_ DCG edges.
    ///
    /// (e.g., interval-based projections, using the abstract domain of intervals)
    fn force_abs
        <Arg:'static+Eq+Debug+Clone+Hash,
         Abs:'static+Eq+Debug+Clone+Hash,
         T:'static+Eq+Debug+Clone+Hash,
         DiffT:'static+Eq+Debug+Clone+Hash,
         S:'static+Eq+Debug+Clone+Hash>
        (g:&RefCell<DCG>,
         absmapfam:Box<dyn AbsMapFam<Arg,Abs,T,DiffT,S>>,
         arg:Arg, art:&AbsArt<T,Self::Loc>) -> S ;

}

impl Adapton for DCG {
    type Loc  = Loc;

    fn new () -> DCG {
        let path = Rc::new(Path::Empty);
        let stack = Vec::new() ;
        let table = HashMap::new ();
        DCG {
            flags : Flags {
                use_purity_optimization       : { match env::var("ADAPTON_NO_PURITY")  { Ok(_) => false, _ => true } },
                ignore_nominal_use_structural : { match env::var("ADAPTON_STRUCTURAL") { Ok(_) => true,  _ => false } },
                check_dcg_is_wf               : { match env::var("ADAPTON_CHECK_DCG")  { Ok(_) => true,  _ => false } },
                write_dcg                     : { match env::var("ADAPTON_WRITE_DCG")  { Ok(_) => true,  _ => false } },
                gmlog_dcg                     : { match env::var("ADAPTON_GMLOG_DCG")  { Ok(_) => true,  _ => false } },
            },
            table : table,
            stack : stack,
            path  : path,
            dcg_count : 0,
            dcg_hash : 0, // XXX This makes assumptions about hashing implementation
        }
    }

    fn structural<T,F> (g: &RefCell<DCG>, body:F) -> T
        where F:FnOnce() -> T
    {
        let saved = {
            let st = &mut *g.borrow_mut();
            let saved = st.flags.ignore_nominal_use_structural ;
            st.flags.ignore_nominal_use_structural = true ;
            saved
        } ;
        let x = body() ;
        g.borrow_mut().flags.ignore_nominal_use_structural = saved;
        x
    }

    fn ns<T,F> (g: &RefCell<DCG>, nm:Name, body:F) -> T
        where F:FnOnce() -> T
    {
        let saved = {
            let st = &mut *g.borrow_mut();
            let saved = st.path.clone();
            st.path = Rc::new(Path::Child(st.path.clone(), nm)) ; // Todo-Minor: Avoid this clone.
            saved
        };
        let x = body() ;
        g.borrow_mut().path = saved ;
        x
    }

    fn put<T:Eq> (self:&mut DCG, x:T) -> AbsArt<T,Self::Loc> { AbsArt::Rc(Rc::new(x)) }

    fn cell<T:Eq+Debug+Clone+Hash
            +'static // TODO-Later: Needed on T because of lifetime issues.
            >
        (self:&mut DCG, nm:Name, val:T) -> AbsArt<T,Self::Loc> {
            wf::check_dcg(self);
            let path = current_path(self) ;
            let (id, is_pure) = {
                if ! self.flags.ignore_nominal_use_structural {
                    (Rc::new(ArtId::Nominal(nm)), false) // Ordinary case: Use provided name.
                } else {
                    let hash = my_hash (&val) ;
                    (Rc::new(ArtId::Structural(hash)), self.flags.use_purity_optimization) // Ignore the name; do hash-consing instead.
                }
            };
            let hash = my_hash(&(&path,&id));
            let loc  = Rc::new(Loc{path:path,id:id,hash:hash})
                ;
            let (do_dirty, do_set, succs, do_insert, is_fresh) =
                if self.table.contains_key(&loc) {
                    let node : &Box<Node<T>> = res_node_of_loc(self, &loc) ;
                    match **node {
                        Node::Mut(_)       => { (false, true,  None, false, false) }
                        Node::Comp(ref nd) => { (true,  false, Some(nd.succs.clone()),  false, false ) }
                        Node::Pure(_)      => { (false, false, None, false, false) }
                    }} else                 { (false, false, None, true, true ) }
            ;
            // - - - - - - - - - -
            // Begin an allocation.  Because this allocation may require
            // dirtying some allocation edges. (See value of bit
            // `do_dirty`, which is true when we are overwriting what was
            // once a computation with a value). This allocation may also
            // require dirtying some observers, when the new value is
            // different from the one that they last observed. (Similarly,
            // allocations that allocated a different value need to be
            // dirtied too).  Hence, this effect may contain other effects
            // to the DCG, namely, those dirtying steps.
            // - - - - - - -
            dcg_effect_begin!(
                reflect::trace::Effect::Alloc(
                    if is_fresh { reflect::trace::AllocCase::LocFresh }
                    else {
                        let changed =
                            if check_cell_change(self, AbsArt::Loc(loc.clone()), &val) {
                                reflect::trace::ChangeFlag::ContentDiff
                            } else {
                                reflect::trace::ChangeFlag::ContentSame
                            };
                        reflect::trace::AllocCase::LocExists(changed)
                    },
                    reflect::trace::AllocKind::RefCell,
                ),
                current_loc!(self),
                reflect::Succ{
                    loc:loc.reflect(),
                    effect:reflect::Effect::Alloc,
                    value:reflect::Val::ValTODO,
                    dirty:false,
                    is_dup:false, // XXX -- Actually: Not checked here.
                }
            );
            if do_set   { set_(self, AbsArt::Loc(loc.clone()), val.clone()) };
            if do_dirty { dirty_alloc(self, &loc) } ;
            match succs { Some(succs) => revoke_succs(self, &loc, &succs), None => () } ;
            dcg_effect_end!();

            if do_insert {
                let node = if is_pure { Node::Pure(PureNode{val:val.clone()}) } else {
                    Node::Mut(MutNode{
                        preds:Vec::new(),
                        val:val.clone(),
                    })} ;
                self.table.insert(loc.clone(), Box::new(node));
            } ;
            if ! is_pure { match self.stack.last_mut() {
                None => (),
                Some(frame) => {
                    let succ =
                        Succ{loc:loc.clone(),
                             dep:Rc