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::new(Box::new(AllocCell{val:val})),
                             effect:Effect::Allocate,
                             dirty:false};
                    frame.succs.push((succ, None))
                }}} ;
            wf::check_dcg(self);
            AbsArt::Loc(loc)
        }

    fn set<T:'static+Eq+Debug> (self:&mut Self, cell:AbsArt<T,Self::Loc>, val:T) {
        wf::check_dcg(self);
        assert!( self.stack.is_empty() ); // => outer layer has control.
        set_(self, cell, val);
        wf::check_dcg(self);
    }

    fn thunk<Arg:Eq+Hash+Debug+Clone+'static,Spurious:'static+Clone,Res:Eq+Debug+Clone+Hash+'static>
        (self:&mut DCG,
         id:NameChoice,
         prog_pt:ProgPt,
         fn_box:Rc<Box<dyn Fn(Arg, Spurious) -> Res>>,
         arg:Arg, spurious:Spurious)
         -> AbsArt<Res,Self::Loc>
    {
        wf::check_dcg(self);
        let id =
        // Apply the logic of engine's flags:
            match id { NameChoice::Nominal(_)
                       if self.flags.ignore_nominal_use_structural
                       => NameChoice::Structural,
                       id => id } ;
        match id {
            // Eagerly do the computation now, and store the result.
            NameChoice::Eager => {
                AbsArt::Rc(Rc::new(fn_box(arg,spurious)))
            },

            NameChoice::Naive => {
                // TODO/XXX
                // Tried to implement this, but got stuck because of `Self::Loc`.
                // Perhaps now is the time to completely ditch this `Adapton` trait, and the `Self::Loc` type.
                unimplemented!()
            }
            
            // Name the computation structurally, based on the args and prog point.
            NameChoice::Structural => {
                wf::check_dcg(self);
                let hash = my_hash (&(&prog_pt, &arg)) ;
                let loc = loc_of_id(current_path(self),
                                    Rc::new(ArtId::Structural(hash)));
                {   // If the node exists, return early.
                    let node = self.table.get_mut(&loc);
                    match node { None    => { },
                                 Some(_) => { return AbsArt::Loc(loc) }, // Nothing to do; it already exists.
                    }
                } ;
                // assert: node does not exist.
                match self.stack.last_mut() {
                    None => (),
                    Some(frame) => {
                        let succ =
                            Succ{loc:loc.clone(),
                                 dep:Rc::new(Box::new(AllocStructuralThunk)),
                                 effect:Effect::Allocate,
                                 dirty:false};
                        frame.succs.push((succ, None))
                    }};
                let producer : Box<dyn Producer<Res>> =
                    Box::new(App{prog_pt:prog_pt,
                                 fn_box:fn_box,
                                 arg:arg.clone(),
                                 spurious:spurious.clone()})
                    ;
                let node : CompNode<Res> = CompNode{
                    preds:Vec::new(),
                    succs:Vec::new(),
                    producer:producer,
                    res:None,
                } ;
                //self.cnt.create += 1;
                self.table.insert(loc.clone(),
                                  Box::new(Node::Comp(node)));
                wf::check_dcg(self);
                AbsArt::Loc(loc)
            },

            // Name the thunk explicitly by `nm`
            NameChoice::Nominal(nm) => {
                wf::check_dcg(self);
                let loc = loc_of_id(current_path(self),
                                    Rc::new(ArtId::Nominal(nm)));
                let producer : App<Arg,Spurious,Res> =
                    App{prog_pt:prog_pt.clone(),
                        fn_box:fn_box,
                        arg:arg.clone(),
                        spurious:spurious.clone(),
                    }
                ;
                let top_loc = get_top_stack_loc( self );
                let (do_dirty, do_insert, is_fresh) = { match self.table.get_mut( &loc ) {
                    None => {
                        // do_dirty=false; do_insert=true
                        (false, true, true)
                    },
                    Some(node) => {
                        let node: &mut Box<dyn GraphNode> = node ;
                        assert_graphnode_res_type::<Res>(&loc, node, top_loc);
                        let res_nd: &mut Box<Node<Res>> = unsafe { transmute::<_,_>( node ) } ;
                        match ** res_nd {
                            Node::Pure(_)=> unreachable!(),
                            Node::Mut(_) => {
                                (true, true, false) // Todo: Do we need to preserve preds?
                            },
                            Node::Comp(ref mut comp_nd) => {
                                let equal_producer_prog_pts : bool =
                                    comp_nd.producer.prog_pt().eq( producer.prog_pt() ) ;
                                if equal_producer_prog_pts { // => safe cast to Box<Consumer<Arg>>
                                    let app: &mut Box<App<Arg,Spurious,Res>> =
                                    // TODO-Soon: Follow pattern above for assert_graphnode_res_type to dynamically check the safety of this cast
                                        unsafe { transmute::<_,_>( &mut comp_nd.producer ) }
                                    ;
                                    if app.get_arg() == arg {
                                        // Case: Same argument; Nothing else to do:
                                        // do_dirty=false; do_insert=false
                                        (false, false, false)
                                    }
                                    else { // Case: Not the same argument:
                                        app.consume(arg.clone()); // overwrite the old argument
                                        comp_nd.res = None ; // clear the cache
                                        // do_dirty=true; do_insert=false
                                        (true, false, false)
                                    }}
                                else {
                                    panic!("Memozied functions not equal!
                            Function was: {:?}
                           with Producer: {:?}

                            Function now: {:?}
                           with Producer: {:?}

                        Common location: {:?}

                        ** Hint: Consider using distinct namespaces, via `Adapton::ns`
                           (See: https://docs.rs/adapton/0/adapton/engine/fn.ns.html)
                        ",
                                           comp_nd.producer.prog_pt(), &comp_nd.producer,
                                           producer.prog_pt(), &producer,
                                           &loc,
                                    )
                                }
                            },
                        }
                    }
                } } ;

                dcg_effect_begin!(
                    reflect::trace::Effect::Alloc(
                        if is_fresh { reflect::trace::AllocCase::LocFresh }
                        else {
                            let cf =
                                if do_dirty { reflect::trace::ChangeFlag::ContentDiff }
                            else { reflect::trace::ChangeFlag::ContentSame };
                            reflect::trace::AllocCase::LocExists(cf) },
                        reflect::trace::AllocKind::Thunk
                    ),
                    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_dirty {dirty_alloc(self, &loc) };
                dcg_effect_end!();

                match self.stack.last_mut() { None => (), Some(frame) => {
                    let succ =
                        Succ{loc:loc.clone(),
                             dep:Rc::new(Box::new(AllocNominalThunk{val:arg.clone()})),
                             effect:Effect::Allocate,
                             dirty:false};
                    frame.succs.push((succ, None))
                }};
                if do_insert {
                    let node : CompNode<Res> = CompNode{
                        preds:Vec::new(),
                        succs:Vec::new(),
                        producer:Box::new(producer),
                        res:None,
                    } ;
                    self.table.insert(loc.clone(), Box::new(Node::Comp(node)));
                    wf::check_dcg(self);
                    AbsArt::Loc(loc)
                }
                else {
                    wf::check_dcg(self);
                    AbsArt::Loc(loc)
                }
            }
        }
    }

    fn force_map<T:'static+Eq+Debug+Clone+Hash,
                 S:'static+Eq+Debug+Clone+Hash,
                 F:'static>
        (g:&RefCell<DCG>,
         art:&AbsArt<T,Self::Loc>, mapf:F) -> S
        where F:Fn(&Art<T>, T) -> S
    {
        match *art {
            AbsArt::Rc(ref v) => mapf(&Art{art:EnumArt::Rc(v.clone())},
                                      (**v).clone()),
            AbsArt::Loc(ref loc) => {
                let cell_val : Option<T> = {
                    let st : &mut DCG = &mut *g.borrow_mut();
                    let node : &mut Node<T> = res_node_of_loc(st, &loc) ;
                    match *node {
                        Node::Comp(_) => { None }
                        Node::Pure(_) => { None }
                        Node::Mut(ref nd)  => { Some(nd.val.clone()) }
                    }
                } ;
                match cell_val {
                    None => {
                        mapf(&Art{art:EnumArt::Loc(loc.clone())},
                             <DCG as Adapton>::force(g, art, None))
                    },
                    Some(val) => {
                        // Case: We _are_ forcing a cell; so, we record
                        // the mapped value, and the mapping function,
                        // in the DCG.
                        dcg_effect!(
                            // TODO-Someday: Reflect the fact that we are doing a mapping here
                            reflect::trace::Effect::Force(reflect::trace::ForceCase::RefGet),
                            current_loc!(*g.borrow()),
                            reflect::Succ{
                                loc:loc.reflect(),
                                value:reflect::Val::ValTODO,
                                effect:reflect::Effect::Force,
                                dirty:false,
                                is_dup:false,
                            });
                        let st : &mut DCG = &mut *g.borrow_mut() ;
                        let res = mapf(&Art{art:EnumArt::Loc(loc.clone())}, val.clone());
                        match st.stack.last_mut() { None => (), Some(frame) => {
                            // `dep` records the mapping function
                            let dep : Rc<Box<dyn DCGDep>> = Rc::new(Box::new(ForceMapDep{
                                raw:PhantomData,
                                mapf:mapf,
                                res:res.clone()}));
                            let succ =
                                Succ{loc:loc.clone(),
                                     dep:dep.clone(),
                                     effect:Effect::Observe,
                                     dirty:false};
                            frame.succs.push((succ, Some(dep.clone())));
                        }};
                        res
                    }
                }
            }
        }
    }

    /// Demand & observe arts, through an abstracted mapping function (See `AbsMapFam` trait)
    ///
    /// (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
    {
        match *art {
            AbsArt::Rc(ref v) => absmapfam.map(arg, /*(&Art{art:EnumArt::Rc(v.clone())}),*/ (**v).clone()),
            AbsArt::Loc(ref loc) => {
                let cell_val : Option<T> = {
                    let st : &mut DCG = &mut *g.borrow_mut();
                    let node : &mut Node<T> = res_node_of_loc(st, &loc) ;
                    match *node {
                        Node::Comp(_) => { None }
                        Node::Pure(_) => { None }
                        Node::Mut(ref nd)  => { Some(nd.val.clone()) }
                    }
                } ;
                match cell_val {
                    None => {
                        /* &Art{art:EnumArt::Loc(loc.clone())} */
                        absmapfam.map(arg, /*(&Art{art:EnumArt::Rc(v.clone())}),*/
                                      <DCG as Adapton>::force(g, art, None))
                    },
                    Some(val) => {
                        // Case: We _are_ forcing a cell; so, we record
                        // the mapped value, and the mapping function,
                        // in the DCG.
                        dcg_effect!(
                            // TODO-Someday: Reflect the fact that we are doing a mapping here
                            reflect::trace::Effect::Force(reflect::trace::ForceCase::RefGet),
                            current_loc!(*g.borrow()),
                            reflect::Succ{
                                loc:loc.reflect(),
                                value:reflect::Val::ValTODO,
                                effect:reflect::Effect::Force,
                                dirty:false,
                                is_dup:false,
                            });
                        let st : &mut DCG = &mut *g.borrow_mut() ;
                        let res = absmapfam.map(arg.clone(),/*&Art{art:EnumArt::Loc(loc.clone())},*/val.clone());
                        match st.stack.last_mut() { None => (), Some(frame) => {
                            // `dep` records the mapping function
                            let dep : Rc<Box<dyn DCGDep>> = Rc::new(Box::new(ForceAbsDep{
                                phm:PhantomData,
                                map:(absmapfam.abs(arg), absmapfam),

                            }));
                            let succ =
                                Succ{loc:loc.clone(),
                                     dep:dep.clone(),
                                     effect:Effect::Observe,
                                     dirty:false};
                            frame.succs.push((succ, Some(dep.clone())));
                        }};
                        res
                    }
                }
            }
        }
    }

    fn force<T:'static+Eq+Debug+Clone+Hash> (g:&RefCell<DCG>,
                                             art:&AbsArt<T,Self::Loc>, cycle_out:Option<T>) -> T
    {
        {
            let st : &mut DCG = &mut *g.borrow_mut();
            wf::check_dcg(st);
            drop(st)
        }
        match *art {
            AbsArt::Rc(ref v) => (**v).clone(),
            AbsArt::Loc(ref loc) => {
                let (is_comp, is_dup, is_pure, is_cycle, cached_result) : (bool, bool, bool, bool, Option<T>) = {
                    let st : &mut DCG = &mut *g.borrow_mut();
                    let is_pure_opt : bool = st.flags.use_purity_optimization ;
                    let is_cycle = { let mut is_cycle = false;
                                     for frame in st.stack.iter() {
                                         if &frame.loc == loc {
                                             is_cycle = true ; break
                                         } else {  } }
                                     is_cycle
                    };
                    let is_dup : bool = match st.stack.last_mut() { None => false, Some(frame) => {
                        let mut is_dup = false;
                        for &(ref succ, ref _pred_dep) in frame.succs.iter() {
                            if &succ.loc == loc && succ.effect == Effect::Observe
                            { is_dup = true }
                        };
                        is_dup
                    }};
                    let node : &mut Node<T> = res_node_of_loc(st, &loc) ;
                    match *node {
                        Node::Pure(ref mut nd) => (false, is_dup, true, false, Some(nd.val.clone())),
                        Node::Mut(ref mut nd)  => (false, is_dup, false, false, Some(nd.val.clone())),
                        Node::Comp(ref mut nd) => {
                            let is_pure = match *loc.id {
                                ArtId::Structural(_) => nd.succs.len() == 0 && is_pure_opt,
                                ArtId::Nominal(_)    => false } ;
                            if is_cycle {
                                // Cycle detected; check cycle_out to see if the caller expected this
                                match cycle_out {
                                    // Caller did not expect a cycle; cycle is an error
                                    None => { panic!("unexpected cycle detected in DCG") }
                                    // Caller expected that there _could_ be a
                                    // cycle, use this special output value now
                                    // (in particular, in the case of a cycle,
                                    // we do not use the thunk's cached result)
                                    Some(out) => (true, is_dup, is_pure, true, Some(out)),
                                }
                            }
                            else {
                                // "Ordinary case": No cycle, so clone the result we have cached, if any.
                                (true, is_dup, is_pure, false, nd.res.clone())
                            }
                        }
                    }
                };
                let result = match cached_result {
                    None => {
                        assert!(is_comp);
                        assert!(!is_cycle);
                        dcg_effect_begin!(
                            reflect::trace::Effect::Force(reflect::trace::ForceCase::CompCacheMiss),
                            current_loc!(*g.borrow()),
                            reflect::Succ{
                                loc:loc.reflect(),
                                value:reflect::Val::ValTODO,
                                effect:reflect::Effect::Force,
                                dirty:false,
                                is_dup:is_dup,
                            }
                        );
                        assert_eq!(is_dup, false);
                        //println!("produce {:?}", loc);
                        let res = loc_produce(g, &loc);
                        dcg_effect_end!();
                        res
                    },
                    Some(res) => {
                        if is_comp {
                            dcg_effect_begin!(
                                reflect::trace::Effect::Force(reflect::trace::ForceCase::CompCacheHit),
                                current_loc!(*g.borrow()),
                                reflect::Succ{
                                    loc:loc.reflect(),
                                    value:reflect::Val::ValTODO,
                                    effect:reflect::Effect::Force,
                                    dirty:false,
                                    is_dup:is_dup,
                                }
                            );
                            if is_cycle {
                                // Todo-someday: Put something special in the reflected trace?
                                dcg_effect_end!();
                                // return the result that is special for cycles
                                res
                            }
                            else {
                                let _ = ForceDep{res:res.clone()}.clean(g, &loc) ;
                                dcg_effect_end!();
                                let st : &mut DCG = &mut *g.borrow_mut();
                                let node : &mut Node<T> = res_node_of_loc(st, &loc) ;
                                match *node {
                                    Node::Comp(ref nd) => match nd.res {
                                        None => unreachable!(),
                                        Some(ref res) =>
                                        // Testing: Reached by `pure_caching` tests
                                            res.clone()
                                    },
                                    _ => unreachable!(),
                                }}
                        }
                        else {
                            dcg_effect!(
                                reflect::trace::Effect::Force(reflect::trace::ForceCase::RefGet),
                                current_loc!(*g.borrow()),
                                reflect::Succ{
                                    loc:loc.reflect(),
                                    value:reflect::Val::ValTODO,
                                    effect:reflect::Effect::Force,
                                    dirty:false,
                                    is_dup:is_dup,
                                });
                            res.clone()
                        }
                    }
                } ;
                let st : &mut DCG = &mut *g.borrow_mut() ;
                if !is_dup && !is_pure { match st.stack.last_mut() { None => (), Some(frame) => {
                    let succ =
                        Succ{loc:loc.clone(),
                             dep:Rc::new(Box::new(ForceDep{res:result.clone()})),
                             effect:Effect::Observe,
                             dirty:false};
                    frame.succs.push((succ, None));
                }}} ;
                wf::check_dcg(st);
                result
            }
        }}
}

/// *Articulations:* for incrementally-changing data/computation.  
///
///  - Introduced by (produced by) `thunk`, `cell` and `put`
///
///  - Eliminated by (consumed by) `force` (and `set`).
///
/// The term *Art* stands for two things here:  
///
/// - _Adapton Reference / Thunk_, and
///
/// - _Articulation_, for naming and discretizing incrementally-changing data (and computations).
///
/// Each art has a unique identity, its `Name`.
/// Because this identity, each art permits efficient (O(1) time)
/// hashing and equality checks.
///
/// The concept of an art abstracts over whether the producer is
/// *eager* (like a ref `cell`) or *lazy* (like a `thunk`).  One uses
/// `force` to inspect both eager and lazy arts.  Consequently, code
/// that consumes structures with arts need only ever use `force` (not
/// two different functions, depending on whether the art is lazy or
/// eager).
///
#[derive(Clone,PartialEq,Eq,Hash,Debug)]
pub struct Art<T> {
    art:EnumArt<T>,
}

#[derive(Clone)]
enum EnumArt<T> {
    /// No entry in table. No dependency tracking.
    Rc(Rc<T>),
    /// Location in table.
    Loc(Rc<Loc>),
    /// A closure that is 'force-able'
    Force(Rc<dyn Force<T>>),
}

impl<T:Hash> Hash for EnumArt<T> {
    fn hash<H>(&self, hasher:&mut H) where H:Hasher {
        match *self {
            EnumArt::Rc(ref rc)   => rc.hash( hasher ),
            EnumArt::Loc(ref loc) => loc.hash( hasher ),
            EnumArt::Force(ref f) => f.hash_u64().hash( hasher ),
        }
    }
}

impl<T:PartialEq> PartialEq for EnumArt<T> {
    fn eq(&self, other:&Self) -> bool {
        match *self {
            EnumArt::Rc(ref rc) =>
                if let EnumArt::Rc(ref rc2) = *other { rc == rc2 } else { false },
            EnumArt::Loc(ref loc) =>
                if let EnumArt::Loc(ref loc2) = *other { loc == loc2 } else { false },
            EnumArt::Force(ref f) =>
                if let EnumArt::Force(ref f2) = *other { f.eq(&**f2) } else { false },
        }
    }
}

impl<T:Debug> Debug for EnumArt<T> {
    fn fmt(&self, f:&mut Formatter) -> Result {
        match *self {
            EnumArt::Rc(ref rc)     => rc.fmt(f),
            EnumArt::Loc(ref loc)   => loc.fmt(f),
            EnumArt::Force(ref frc) => frc.fmt(f),
        }
    }
}

impl<T:Eq> Eq for EnumArt<T> { }

trait Force<T> {
    fn force(&self) -> T;
    fn copy(self:&Self) -> Box<dyn Force<T>>;
    fn eq(self:&Self, other:&dyn Force<T>) -> bool;
    fn id<'r>(self:&'r Self) -> &'r NameChoice;
    fn prog_pt<'r>(self:&'r Self) -> &'r ProgPt;
    fn hash_u64(self:&Self) -> u64;
    fn fmt(&self, f:&mut Formatter) -> fmt::Result;
}

#[derive(Clone)]
struct NaiveThunk<Arg, Spurious, Res> {
    id:NameChoice,
    prog_pt:ProgPt,
    fn_box:Rc<Box< dyn Fn(Arg, Spurious) -> Res >>,
    arg:Arg,
    spurious:Spurious
}

impl<A:Hash+Clone+Eq+Debug+'static,S:Clone+'static,T:'static>
    Force<T>
    for NaiveThunk<A,S,T>
{
    fn force(&self) -> T {
        (*self.fn_box)(self.arg.clone(), self.spurious.clone())
    }
    fn copy(self:&Self) -> Box<dyn Force<T>> {
        Box::new(NaiveThunk{id:self.id.clone(),
                            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 id<'r>(self:&'r Self) -> &'r NameChoice {
        & self.id
    }
    fn hash_u64(&self) -> u64 {
        let mut hasher = DefaultHasher::new();
        self.id.hash( &mut hasher );
        self.prog_pt.hash( &mut hasher );
        self.arg.hash( &mut hasher );
        hasher.finish()
    }
    fn eq (&self, other:&dyn Force<T>) -> bool {
        if   &self.id      == other.id()
            && &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<NaiveThunk<A,S,T>> = unsafe { transmute::<_,_>( other ) } ;
            self.arg == other.arg
        } else {
            false
        }
    }
    fn fmt(&self, f:&mut Formatter) -> Result {
        write!(f,"NaiveThunk{{id:{:?},prog_pt:{:?},arg:{:?}}}",
               self.id, self.prog_pt, self.arg)
    }
}

impl<A:Hash,S,T> Hash for NaiveThunk<A,S,T> {
    fn hash<H:Hasher>(&self, hasher: &mut H) {
        self.prog_pt.hash( hasher );
        self.arg.hash( hasher );
    }
}
impl<A:Debug,S,T> Debug for NaiveThunk<A,S,T> {
    fn fmt(&self, f:&mut Formatter) -> fmt::Result {
        // TODO: Make this formatting better
        write!(f, "NaiveThunk({:?},{:?})", self.prog_pt, self.arg)
    }
}
impl<A:PartialEq,S,T> PartialEq for NaiveThunk<A,S,T> {
    fn eq(&self, other:&Self) -> bool {
        self.prog_pt == other.prog_pt &&
            self.arg == other.arg
    }
}





/// Create a name from unit, that is, create a "leaf" name.
pub fn name_unit () -> Name {
    UNIT_NAME.with(|r|r.clone())
}

/// Create one name from two (binary name composition)
pub fn name_pair (n1:Name, n2:Name) -> Name {
    let h = my_hash( &(n1.hash,n2.hash) ) ;
    let p = NameSym::Pair(n1.symbol, n2.symbol) ;
    Name{ hash:h, symbol:Rc::new(p) }
}

/// Create a name from a hash value.
///
/// Do not call this function directly; we introduced it in order to
/// get reflection to type-check.  We should think of ways to avoid
/// using this in the future.
pub fn name_of_hash64(h:u64) -> Name {
    // TODO: Get rid of need for Rc here;
    // Rc should be optional in names?
    Name{ hash:h, symbol:Rc::new(NameSym::Hash64) }
}

/// Create a name from a `usize`
pub fn name_of_usize (u:usize) -> Name {
    let h = my_hash(&u) ;
    let s = NameSym::Usize(u) ;
    Name{ hash:h, symbol:Rc::new(s) }
}

/// Create a name from a `isize`
pub fn name_of_isize (i:isize) -> Name {
    let h = my_hash(&i) ;
    let s = NameSym::Isize(i) ;
    Name{ hash:h, symbol:Rc::new(s) }
}

/// Create a name from a `string`
pub fn name_of_string (s:String) -> Name {
    let h = my_hash(&s);
    let s = NameSym::String(s) ;
    Name{ hash:h, symbol:Rc::new(s) }
}

/// Create a name from a `str`
pub fn name_of_str (s:&'static str) -> Name {
    let h = my_hash(&s);
    let s = NameSym::String(s.to_string()) ;
    Name{ hash:h, symbol:Rc::new(s) }
}

/// Create two names from one
pub fn name_fork (n:Name) -> (Name, Name) {
    let h1 = my_hash( &(&n, 11111111) ) ; // TODO-Later: make this hashing better.
    let h2 = my_hash( &(&n, 22222222) ) ;
    ( Name{ hash:h1,
            symbol:Rc::new(NameSym::ForkL(n.symbol.clone())) } ,
      Name{ hash:h2,
            symbol:Rc::new(NameSym::ForkR(n.symbol)) } )
}

/// Create three names from one
pub fn name_fork3 (n:Name)
                   -> (Name,Name,Name)
{
    let (n1,n)  = name_fork(n);
    let (n2,n3) = name_fork(n);
    (n1,n2,n3)
}

/// Create four names from one
pub fn name_fork4 (n:Name)
                   -> (Name,Name,Name,Name)
{
    let (n1,n)  = name_fork(n);
    let (n2,n)  = name_fork(n);
    let (n3,n4) = name_fork(n);
    (n1,n2,n3,n4)
}

/// Creates or re-enters a given namespace; performs the given computation there.
pub fn ns<T,F> (n:Name, body:F) -> T
    where F:FnOnce() -> T {
    GLOBALS.with(|g| {
        match g.borrow().engine {
            Engine::DCG(ref dcg) => <DCG as Adapton>::ns(dcg, n, body),
            Engine::Naive => (body)()
        }
    })
}

/// Enters a special "namespace" where all name uses are ignored; instead, Adapton uses structural identity.
pub fn structural<T,F> (body:F) -> T
    where F:FnOnce() -> T {
    GLOBALS.with(|g| {
        match g.borrow().engine {
            Engine::DCG(ref dcg) => <DCG as Adapton>::structural(dcg,body), // XXX borrow is too long
            Engine::Naive => (body)()
        }
    })
}

/// Creates an unnamed, immutable reference cell (an eager `Art<_>`)
/// whose content may not change over time.
pub fn put<T:Eq+Debug+Clone> (val:T) -> Art<T> {
    Art{art:EnumArt::Rc(Rc::new(val))}
}

/// Creates a named reference cell (an eager `Art<_>`) whose content
/// can change over time.
///
/// From the editor's perspective, this cell is mutable.  From the
/// archivist's perspective, this cell is a "one-shot" reference cell:
/// Once allocated, it is immutable.
pub fn cell<T:Hash+Eq+Debug+Clone+'static> (n:Name, val:T) -> Art<T> {
    GLOBALS.with(|g| {
        match g.borrow().engine {
            Engine::DCG(ref dcg) => {
                if
                    let AbsArt::Loc(loc) = (dcg.borrow_mut()).cell(n,val) {
                        Art{art:EnumArt::Loc(loc)} }
                else { unreachable!() } }
            Engine::Naive => Art{art:EnumArt::Rc(Rc::new(val))}
        }
    })
}

/// Mutates a mutable articulation.
pub fn set<T:'static+Eq+Debug+Clone> (a:&Art<T>, val:T) {
    match (*a).art {
        EnumArt::Rc(_)    => { panic!("set: Cannot mutate immutable Rc articulation; use an DCG cell instead") },
        EnumArt::Force(_) => { panic!("set: Cannot mutate immutable Force articulation; use an DCG cell instead") },
        EnumArt::Loc(ref l) => {
            GLOBALS.with(|g| {
                match g.borrow().engine {
                    Engine::Naive => unimplemented!(), // TODO: Think more about this case.
                    Engine::DCG(ref dcg) => {
                        (dcg.borrow_mut()).set(AbsArt::Loc(l.clone()), val)
                    }
                }
            })
        }
    }
}

/// Allocates a thunk, an `Art<T>` that consists of a suspended
/// computation that produces a value of type `T`.
///
/// Use the macros `thunk!`, `memo!` and `eager!` to create and force
/// thunks with less typing.
///
/// A full invocation of `thunk` consists of the following:
///
///  - It has an `id` of type `NameChoice`, either giving a `Name`,
///    requesting structural identity, or requesting no caching
///    whatsoever.
///
///  - Its code resides at a _program point_, of type `ProgPt`.  This
///    uniquely identifies the static elements of the suspended
///    computation (the code, but not the closing environment).
///
///  - It has a function for this code, of type
///    `Rc<Box<Fn(Art,Spurious) -> Res >>`.  The `Rc<_>` is required
///    for cloning this function, which we generally want to do.  We
///    divide the arguments into the ordinary arguments of type `Arg`,
///    and additional "spurious" arguments.  When we judge whether a
///    thunk's closing environment is equal to another, we use the
///    type `Arg`.  When we judge whether the result of a thunk has
///    changed or not, we use the type `Res`.
///
///  - Spurious arguments are not compared for equality, and are
///    ignored during the memo-matching process.  They are, however,
///    saved in the thunk and supplied to the suspended computation
///    when it runs.  Typically, these arguments consist of
///    higher-order functions that parameterize the thunk; we make
///    them spurious because (1) we cannot, and do not wish to compare
///    them for equality and (2) the triple of type (`ProgPt`,
///    `NameChoice`, `Arg`) should determine these spurious
///    arguments, if any.  Because some arguments have no equality
///    relation, the presence of these arguments is sometimes a
///    necessary hack.
pub fn thunk<Arg:Hash+Eq+Debug+Clone+'static,Spurious:Clone+'static,Res:Hash+Eq+Debug+Clone+'static>
    (id:NameChoice,
     prog_pt:ProgPt,
     fn_box:Rc<Box< dyn Fn(Arg, Spurious) -> Res >>,
     arg:Arg, spurious:Spurious)
     -> Art<Res>
{
    GLOBALS.with(|g| {
        match g.borrow().engine {
            Engine::DCG(ref dcg) => {
                Art{art:EnumArt::Loc({
                    if let AbsArt::Loc(loc) =
                        (dcg.borrow_mut()).thunk(id, prog_pt, fn_box, arg, spurious)
                    { loc } else { unreachable!() }})}
            },
            Engine::Naive => {
                Art{art:EnumArt::Force(
                    Rc::new(NaiveThunk{
                        id:id,prog_pt:prog_pt,
                        fn_box:fn_box,arg:arg,
                        spurious:spurious} ))}}}
    })
}

/// Map a given `thunk` by a mapping function `map_fn`, yielding a new
/// thunk.
///
/// Under the hood, this operation is "cheap" (but sound), in that it
/// uses a "naive", native Rust thunk that does not cache its output,
/// or represent itself in the trace.
pub fn thunk_map<Res1:Hash+Eq+Debug+Clone+'static,
                 Res2:Hash+Eq+Debug+Clone+'static>
    (thunk:Art<Res1>, map_fn:Rc<dyn Fn(Res1) -> Res2>) -> Art<Res2>
{
    Art{art:EnumArt::Force(
        Rc::new(NaiveThunk{
            id:NameChoice::Naive,
            prog_pt:ProgPt{symbol:"engine::thunk_map"},
            fn_box:{Rc::new(Box::new(move |_,_| {
                let res1 = force(&thunk);
                let res2 = map_fn(res1);
                res2
            }))},
            arg:(),
            spurious:()
        }))
    }
    
}
    
/// Demands and observes the value of an `&Art<T>`, returning a (cloned) value of type `T`.
pub fn force<T:Hash+Eq+Debug+Clone+'static> (a:&Art<T>) -> T {
    match a.art {
        EnumArt::Force(ref f) => f.force(),
        EnumArt::Rc(ref rc) => (&**rc).clone(),
        EnumArt::Loc(ref loc) => {
            GLOBALS.with(|g| {
                match g.borrow().engine {
                    Engine::DCG(ref dcg_refcell) =>
                        <DCG as Adapton>::force(dcg_refcell, &AbsArt::Loc(loc.clone()), None),
                    Engine::Naive => panic!("cannot force a non-naive location with the naive engine")
                }})
        }
    }
}

/// Demands and observes the value of an `&Art<T>`, returning a
/// (cloned) value of type `T`, or the value of `cycle_out` if the
/// force edge forms a cycle in the DCG.
///
/// Note that if the articulation `a` is not a thunk, then `cycle_out`
/// will not be used (cycles in the DCG are formed by thunks forcing
/// one another, not by reference cells).
pub fn force_cycle<T:Hash+Eq+Debug+Clone+'static> (a:&Art<T>, cycle_out:Option<T>) -> T {
    match a.art {
        EnumArt::Force(ref f) => f.force(),
        EnumArt::Rc(ref rc) => (&**rc).clone(),
        EnumArt::Loc(ref loc) => {
            GLOBALS.with(|g| {
                match g.borrow().engine {
                    Engine::DCG(ref dcg_refcell) =>
                        <DCG as Adapton>::force(dcg_refcell, &AbsArt::Loc(loc.clone()), cycle_out),
                    Engine::Naive => panic!("cannot force a non-naive location with the naive engine")
                }})
        }
    }
}

/// Demands and observes the value of an `&Art<T>`, returning a
/// (cloned) value of type `S`, mapped by function `mapf`.
///
/// The _pure_ map function `mapf` transforms the value before
/// `force_map` returns.  For correctness, it is critical that `mapf`
/// does not itself allocate or observe any DCG nodes.  When the given
/// `Art` is a cell, this mapping function enables the engine to prune
/// otherwise-dirtied dependencies; consequently, the map function
/// permits finer-grained dependency tracking without additional,
/// fine-grained `Art`s.
pub fn force_map<T:Hash+Eq+Debug+Clone+'static,
                 S:Hash+Eq+Debug+Clone+'static,
                 MapF:'static>
    (a:&Art<T>, mapf:MapF) -> S
    where MapF:Fn(&Art<T>, T) -> S
{
    match a.art {
        EnumArt::Force(ref f) => mapf(a, f.force()),
        EnumArt::Rc(ref rc) => mapf(a, (&**rc).clone()),
        EnumArt::Loc(ref loc) => {
            GLOBALS.with(|g| {
                match g.borrow().engine {
                    Engine::DCG(ref dcg_refcell) =>
                        <DCG as Adapton>::force_map(dcg_refcell, &AbsArt::Loc(loc.clone()), mapf),
                    Engine::Naive => panic!("cannot force a non-naive location with the naive engine")
                }
            })
        }
    }
}

/// Demand & observe arts, through an abstracted mapping function (See `AbsMapFam` trait)
///
/// (e.g., interval-based projections, using the abstract domain of intervals)
pub 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>
    (absmapfam:Box<dyn AbsMapFam<Arg,Abs,T,DiffT,S>>, arg:Arg, a:Art<T>) -> S
{
    match a.art {
        EnumArt::Force(ref f) => absmapfam.map(arg, f.force()),
        EnumArt::Rc(ref rc) => absmapfam.map(arg, (&**rc).clone()),
        EnumArt::Loc(ref loc) => {
            GLOBALS.with(|g| {
                match g.borrow().engine {
                    Engine::DCG(ref dcg_refcell) =>
                        <DCG as Adapton>::force_abs(dcg_refcell, absmapfam, arg, &AbsArt::Loc(loc.clone())),
                    Engine::Naive => panic!("cannot force a non-naive location with the naive engine")
                }
            })
        }
    }
}

/// Operations that monitor and alter the active engine.  Incremental
/// applications should not use these operations directly.
pub mod manage {
    use super::*;


    /// Initializes global state with a fresh DCG-based engine; returns the old engine.
    /// The DCG is the central implementation structure behind Adapton.
    /// At a high level, it consists of a data dependence graph (the "demanded computation graph"), and an associated memoization table.
    pub fn init_dcg () -> Engine { init_engine(Engine::DCG(RefCell::new(DCG::new()))) }

    /// Initializes global state with a ("fresh") Naive engine; returns the old engine.
    /// The naive engine is stateless, and performs no memoization and builds no dependence graphs.
    /// (Since the naive engine is stateless, every instance of the naive engine is equivalent to a "fresh" one).
    pub fn init_naive () -> Engine { init_engine(Engine::Naive) }

    /// Switch to using the given `Engine`; returns the `Engine` that was in use.
    pub fn use_engine (engine: Engine) -> Engine {
        use std::mem;
        let mut engine = engine;
        GLOBALS.with(|g| {
            mem::swap(&mut g.borrow_mut().engine, &mut engine);
        });
        return engine
    }

    /// alias for `use_engine`
    pub fn init_engine (engine: Engine) -> Engine {
        use_engine(engine)
    }

    /// True iff the current engine is `Naive`
    pub fn engine_is_naive () -> bool {
        GLOBALS.with(|g| {
            match g.borrow().engine {
                Engine::DCG(_) => false,
                Engine::Naive  => true
            }})
    }

    /// True iff the current engine is a `DCG`
    pub fn engine_is_dcg () -> bool {
        GLOBALS.with(|g| {
            match g.borrow().engine {
                Engine::DCG(_) => true,
                Engine::Naive  => false
            }})
    }
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
///
/// Well-formedness tests; for documentation and for debugging.
///
mod wf {
    use std::collections::HashMap;
    use std::rc::Rc;
    use std::io::BufWriter;
    use std::io::Write;
    use std::fs::File;
    //use macros::{ProgPt};

    use super::*;

    #[derive(Eq,PartialEq,Clone)]
    enum NodeStatus {
        Dirty, Clean, Unknown
    }

    type Cs = HashMap<Rc<Loc>, NodeStatus> ;

    fn add_constraint (cs:&mut Cs, loc:&Rc<Loc>, new_status: NodeStatus)
    {
        let old_status = match
            cs.get(loc) { None => NodeStatus::Unknown,
                          Some(x) => (*x).clone() } ;
        match (old_status, new_status) {
            (NodeStatus::Clean, NodeStatus::Dirty) |
            (NodeStatus::Dirty, NodeStatus::Clean) => {
                panic!("{:?}: Constrained to be both clean and dirty: Inconsistent status => DCG is not well-formed.")
            },
            (NodeStatus::Unknown, new_status) => { cs.insert(loc.clone(), new_status); () },
            (old_status, NodeStatus::Unknown) => { cs.insert(loc.clone(), old_status); () },
            (ref old_status, ref new_status) if old_status == new_status => { },
            _ => unreachable!(),
        }
    }

    // Constrains loc and all predecessors (transitive) to be dirty
    fn dirty (st:&DCG, cs:&mut Cs, loc:&Rc<Loc>) {
        add_constraint(cs, loc, NodeStatus::Dirty) ;
        let node = match st.table.get(loc) { Some(x) => x, None => panic!("") } ;
        for (pred,_) in node.preds_obs () {
            // Todo: Assert that pred has a dirty succ edge that targets loc
            let succ = super::get_succ(st, &pred, super::Effect::Observe, loc) ;
            if succ.dirty {} else {
                debug_dcg(st);
                write_next_dcg(st, None);
                panic!("Expected dirty edge, but found clean edge: {:?} --Observe--dirty:!--> {:?}", &pred, loc);
            } ; // The edge is dirty.
            dirty(st, cs, &pred)
        }
    }

    // Constrains loc and all successors (transitive) to be clean
    fn clean (st:&DCG, cs:&mut Cs, loc:&Rc<Loc>) {
        add_constraint(cs, loc, NodeStatus::Clean) ;
        let node = match st.table.get(loc) {
            Some(x) => x,
            None => { panic!("dangling: {:?}", loc) }
        } ;
        if ! node.succs_def () { return } ;
        for succ in node.succs () {
            let succ = super::get_succ(st, loc, super::Effect::Observe, &succ.loc) ;
            assert!( ! succ.dirty ); // The edge is clean.
            clean(st, cs, &succ.loc)
        }
    }

    pub fn check_dcg (st:&mut DCG) {
        if st.flags.write_dcg {
            let dcg_hash = my_hash(format!("{:?}",st.table)); // XXX: This assumes that the table's debugging string identifies it uniquely
            if dcg_hash != st.dcg_hash {
                println!("adapton: dcg #{} hash: {:?}", st.dcg_count, dcg_hash);
                st.dcg_hash = dcg_hash;
                let dcg_count = st.dcg_count;
                st.dcg_count += 1;
                write_next_dcg(st, Some(dcg_count));
            }
        } ;
        if st.flags.check_dcg_is_wf {
            let mut cs = HashMap::new() ;
            for frame in st.stack.iter() {
                clean(st, &mut cs, &frame.loc)
            }
            for (loc, node) in &st.table {
                if ! node.succs_def () { continue } ;
                for succ in node.succs () {
                    if succ.dirty {
                        dirty(st, &mut cs, loc)
                    }
                }
            }
        }}

    pub fn write_next_dcg (st:&DCG, num:Option<usize>) {
        let name = match num {
            None => format!("adapton-dcg.dot"),
            Some(n) => format!("adapton-dcg-{:08}.dot", n),
        } ;
        let mut file = File::create(name).unwrap() ;
        write_dcg_file(st, &mut file);
    }

    pub fn write_dcg_file (st:&DCG, file:&mut File) {
        let mut writer = BufWriter::new(file);
        writeln!(&mut writer, "digraph {{\n").unwrap();
        writeln!(&mut writer, "ordering=out;").unwrap();
        for frame in st.stack.iter() {
            writeln!(&mut writer, "\"{:?}\" [color=blue,penwidth=10];", frame.loc).unwrap();
            for succ in frame.succs.iter() {
                writeln!(&mut writer, "\"{:?}\" -> \"{:?}\" [color=blue,weight=10,penwidth=10];", &frame.loc, &succ.0.loc).unwrap();
            }
        };
        for (loc, node) in &st.table {
            if ! node.succs_def () {
                writeln!(&mut writer, "\"{:?}\" [shape=box];", loc).unwrap();
                continue;
            } ;
            for succ in node.succs () {
                if succ.dirty {
                    writeln!(&mut writer, "\"{:?}\" -> \"{:?}\" [color=red,weight=5,penwidth=5];", &loc, &succ.loc).unwrap();
                } else {
                    let (weight, penwidth, color) =
                        match succ.effect {
                            super::Effect::Observe => (0.1, 1, "grey"),
                            super::Effect::Allocate => (2.0, 3, "darkgreen") } ;
                    writeln!(&mut writer, "\"{:?}\" -> \"{:?}\" [weight={},penwidth={},color={}];",
                             &loc, &succ.loc, weight, penwidth, color).unwrap();
                }
            }
        }
        writeln!(&mut writer, "}}\n").unwrap();
    }

    pub fn debug_dcg (st:&DCG) {
        let prefix = "debug_dcg::stack: " ;
        let mut frame_num = 0;
        for frame in st.stack.iter() {
            println!("{} frame {}: {:?}", prefix, frame_num, frame.loc);
            for succ in frame.succs.iter() {
                println!("{} frame {}: \t\t {:?}", prefix, frame_num, &succ);
            }
            frame_num += 1;
        }
        let prefix = "debug_dcg::table: " ;
        for (loc, node) in &st.table {
            println!("{} {:?} ==> {:?}", prefix, loc, node);
            if ! node.succs_def () { continue } ;
            for succ in node.succs () {
                println!("{}\t\t{:?}", prefix, succ);
            }
        }
    }

    // XXX Does not catch errors in IC_Edit that I expected it would
    // XXX Not sure if it works as I expected
    pub fn check_stack_is_clean (st:&DCG) {
        let stack = st.stack.clone() ;
        for frame in stack.iter() {
            let node = match st.table.get(&frame.loc) {
                Some(x) => x,
                None => { panic!("dangling: {:?}", &frame.loc) }
            } ;
            if ! node.succs_def () { return } ;
            for succ in node.succs () {
                let succ = super::get_succ(st, &frame.loc, succ.effect.clone(), &succ.loc) ;
                assert!( succ.dirty ); // The edge is clean.
            }
        }
    }
}


#[test]
fn test_cycles () -> () {
    fn adjs (n:usize) -> (usize, usize) {
        match n {
            0 => (1, 0),
            1 => (2, 3),
            2 => (3, 0),
            3 => (3, 1),
            _ => unimplemented!()
        }
    }

    // This version will diverge on all of the cycles (e.g., 3 --> 3)
    #[warn(unconditional_recursion)]
    fn explore_rec(cur_n:usize) -> Vec<usize> {
        println!("explore {}", cur_n);
        let (a,b) = adjs(cur_n);
        let mut av = explore_rec(a);
        let mut bv = explore_rec(b);
        let mut res = vec![cur_n];
        res.append(&mut av);
        res.append(&mut bv);
        res
    }

    // This version will not diverge; it gives an empty vector value
    // as "cycle output" when it performs each `get!`.  Hence, when
    // Adapton detects a cycle, it will not re-force this thunk
    // cyclicly, but rather return this predetermined "cycle output"
    // value. For non-cyclic calls, the `get!` ignores this value, and
    // works in the usual way.
    fn explore_thunk(cur_n:usize) -> Art<Vec<usize>> {
        thunk!([Some(name_of_usize(cur_n))]? explore ; n:cur_n)
    }
    fn explore(cur_n:usize) -> Vec<usize> {
        println!("explore {}", cur_n);
        let (a,b) = adjs(cur_n);
        let at = explore_thunk(a);
        let bt = explore_thunk(b);
        println!("  explore {} goes to {:?} and {:?}", cur_n, at, bt);
        let mut av = get!(at, vec![]);
        let mut bv = get!(bt, vec![]);
        let mut res = vec![cur_n];
        res.append(&mut av);
        res.append(&mut bv);
        println!("  res={:?}", res);
        res
    }
    super::engine::manage::init_dcg();
    assert_eq!(get!(explore_thunk(0)), vec![0,1,2,3,3])
}