conjure_cp_core/ast/

symbol_table.rs

//! The symbol table.
//!
//! See the item documentation for [`SymbolTable`] for more details.

/// Sentinel for an uncached symbol-table context hash.
const NO_CONTEXT_HASH: u64 = 0;

fn default_context_hash_cache() -> AtomicU64 {
    AtomicU64::new(NO_CONTEXT_HASH)
}

use crate::representation::ReprId;
use crate::representation::Representation;
use std::any::TypeId;

use std::collections::BTreeMap;
use std::collections::VecDeque;
use std::hash::{DefaultHasher, Hash, Hasher};
use std::sync::Arc;
use std::sync::atomic::{AtomicU32, AtomicU64, Ordering};

use super::comprehension::Comprehension;
use super::declaration::declaration_content_generation;
use super::serde::{AsId, DefaultWithId, HasId, IdPtr, ObjId, PtrAsInner};
use super::{
    DeclarationPtr, DomainPtr, Expression, GroundDomain, Model, Moo, Name, ReturnType, Typeable,
};
use itertools::{Itertools as _, izip};
use parking_lot::{RwLock, RwLockReadGuard, RwLockWriteGuard};
use serde::{Deserialize, Serialize};
use serde_with::serde_as;
use tracing::trace;
use uniplate::{Biplate, Tree, Uniplate};

use indexmap::IndexMap;
use indexmap::map::Entry;

/// Global counter of symbol tables.
/// Note that the counter is shared between all threads
/// Thus, when running multiple models in parallel, IDs may
/// be different with every run depending on scheduling order
static SYMBOL_TABLE_ID_COUNTER: AtomicU32 = const { AtomicU32::new(0) };

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct SymbolTablePtr
where
    Self: Send + Sync,
{
    inner: Arc<SymbolTablePtrInner>,
}

impl SymbolTablePtr {
    /// Create an empty new [SymbolTable] and return a shared pointer to it
    pub fn new() -> Self {
        Self::new_with_data(SymbolTable::new())
    }

    /// Create an empty new [SymbolTable] with the given parent and return a shared pointer to it
    pub fn with_parent(symbols: SymbolTablePtr) -> Self {
        Self::new_with_data(SymbolTable::with_parent(symbols))
    }

    fn new_with_data(data: SymbolTable) -> Self {
        let object_id = SYMBOL_TABLE_ID_COUNTER.fetch_add(1, Ordering::Relaxed);
        let id = ObjId {
            object_id,
            type_name: SymbolTablePtr::TYPE_NAME.into(),
        };
        Self::new_with_id_and_data(id, data)
    }

    fn new_with_id_and_data(id: ObjId, data: SymbolTable) -> Self {
        Self {
            inner: Arc::new(SymbolTablePtrInner {
                id,
                value: RwLock::new(data),
            }),
        }
    }

    /// Read the underlying symbol table.
    /// This will block the current thread until a read lock can be acquired.
    ///
    /// # WARNING
    ///
    /// - If the current thread already holds a lock over this table, this may deadlock.
    pub fn read(&self) -> RwLockReadGuard<'_, SymbolTable> {
        self.inner.value.read()
    }

    /// Mutate the underlying symbol table.
    /// This will block the current thread until an exclusive write lock can be acquired.
    ///
    /// # WARNING
    ///
    /// - If the current thread already holds a lock over this table, this may deadlock.
    /// - Trying to acquire any other lock until the write lock is released will cause a deadlock.
    /// - This will mutate the underlying data, which may be shared between other `SymbolTablePtr`s.
    ///   Make sure that this is what you want.
    ///
    /// To create a separate copy of the table, see [SymbolTablePtr::detach].
    ///
    pub fn write(&self) -> RwLockWriteGuard<'_, SymbolTable> {
        self.inner.value.write()
    }

    /// Create a new symbol table with the same contents as this one, but a new ID,
    /// and return a pointer to it.
    pub fn detach(&self) -> Self {
        Self::new_with_data(self.read().clone())
    }
}

impl Default for SymbolTablePtr {
    fn default() -> Self {
        Self::new()
    }
}

impl HasId for SymbolTablePtr {
    const TYPE_NAME: &'static str = "SymbolTable";

    fn id(&self) -> ObjId {
        self.inner.id.clone()
    }
}

impl DefaultWithId for SymbolTablePtr {
    fn default_with_id(id: ObjId) -> Self {
        Self::new_with_id_and_data(id, SymbolTable::default())
    }
}

impl IdPtr for SymbolTablePtr {
    type Data = SymbolTable;

    fn get_data(&self) -> Self::Data {
        self.read().clone()
    }

    fn with_id_and_data(id: ObjId, data: Self::Data) -> Self {
        Self::new_with_id_and_data(id, data)
    }
}

// TODO: this code is almost exactly copied from [DeclarationPtr].
//       It should be possible to eliminate the duplication...
//       Perhaps by merging SymbolTablePtr and DeclarationPtr together?
//       (Alternatively, a macro?)

impl Uniplate for SymbolTablePtr {
    fn uniplate(&self) -> (Tree<Self>, Box<dyn Fn(Tree<Self>) -> Self>) {
        let symtab = self.read();
        let (tree, recons) = Biplate::<SymbolTablePtr>::biplate(&symtab as &SymbolTable);

        let self2 = self.clone();
        (
            tree,
            Box::new(move |x| {
                let self3 = self2.clone();
                *(self3.write()) = recons(x);
                self3
            }),
        )
    }
}

impl<To> Biplate<To> for SymbolTablePtr
where
    SymbolTable: Biplate<To>,
    To: Uniplate,
{
    fn biplate(&self) -> (Tree<To>, Box<dyn Fn(Tree<To>) -> Self>) {
        if TypeId::of::<To>() == TypeId::of::<Self>() {
            unsafe {
                let self_as_to = std::mem::transmute::<&Self, &To>(self).clone();
                (
                    Tree::One(self_as_to),
                    Box::new(move |x| {
                        let Tree::One(x) = x else { panic!() };

                        let x_as_self = std::mem::transmute::<&To, &Self>(&x);
                        x_as_self.clone()
                    }),
                )
            }
        } else {
            // call biplate on the enclosed declaration
            let decl = self.read();
            let (tree, recons) = Biplate::<To>::biplate(&decl as &SymbolTable);

            let self2 = self.clone();
            (
                tree,
                Box::new(move |x| {
                    let self3 = self2.clone();
                    *(self3.write()) = recons(x);
                    self3
                }),
            )
        }
    }
}

#[derive(Debug)]
struct SymbolTablePtrInner {
    id: ObjId,
    value: RwLock<SymbolTable>,
}

impl Hash for SymbolTablePtrInner {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // Identity hash. Symbol table content is mutable and is hashed by `SymbolTable::context_hash`.
        self.id.hash(state);
    }
}

impl PartialEq for SymbolTablePtrInner {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id
    }
}

impl Eq for SymbolTablePtrInner {}

/// The global symbol table, mapping names to their definitions.
///
/// Names in the symbol table are unique, including between different types of object stored in the
/// symbol table. For example, you cannot have a letting and decision variable with the same name.
///
/// # Symbol Kinds
///
/// The symbol table tracks the following types of symbol:
///
/// ## Decision Variables
///
/// ```text
/// find NAME: DOMAIN
/// ```
///
/// See [`DecisionVariable`](super::DecisionVariable).
///
/// ## Lettings
///
/// Lettings define constants, of which there are two types:
///
///   + **Constant values**: `letting val be A`, where A is an [`Expression`].
///
///     A can be any integer, boolean, or matrix expression.
///     A can include references to other lettings, model parameters, and, unlike Savile Row,
///     decision variables.
///
///   + **Constant domains**: `letting Domain be domain D`, where D is a [`Domain`].
///
///     D can include references to other lettings and model parameters, and, unlike Savile Row,
///     decision variables.
///
/// Unless otherwise stated, these follow the semantics specified in section 2.2.2 of the Savile
/// Row manual (version 1.9.1 at time of writing).
#[serde_as]
#[derive(Debug, Serialize, Deserialize)]
pub struct SymbolTable {
    #[serde_as(as = "Vec<(_,PtrAsInner)>")]
    table: IndexMap<Name, DeclarationPtr>,

    #[serde_as(as = "Option<AsId>")]
    parent: Option<SymbolTablePtr>,

    next_machine_name: i32,

    #[serde(default, skip_serializing)]
    local_bindings_xor: u64,

    #[serde(default, skip_serializing)]
    /// Declaration generation represented by `local_bindings_xor`.
    local_bindings_generation: u64,

    #[serde(default = "default_context_hash_cache", skip_serializing)]
    context_hash_cache: AtomicU64,

    #[serde(default = "default_context_hash_cache", skip_serializing)]
    /// Declaration generation represented by `context_hash_cache`.
    context_hash_generation: AtomicU64,
}

impl Clone for SymbolTable {
    fn clone(&self) -> Self {
        Self {
            table: self.table.clone(),
            parent: self.parent.clone(),
            next_machine_name: self.next_machine_name,
            local_bindings_xor: self.local_bindings_xor,
            local_bindings_generation: self.local_bindings_generation,
            context_hash_cache: AtomicU64::new(NO_CONTEXT_HASH),
            context_hash_generation: AtomicU64::new(0),
        }
    }
}

impl PartialEq for SymbolTable {
    fn eq(&self, other: &Self) -> bool {
        self.table == other.table
            && self.parent == other.parent
            && self.next_machine_name == other.next_machine_name
    }
}

impl Eq for SymbolTable {}

impl SymbolTable {
    /// Creates an empty symbol table.
    pub fn new() -> SymbolTable {
        SymbolTable::new_inner(None)
    }

    /// Creates an empty symbol table with the given parent.
    pub fn with_parent(parent: SymbolTablePtr) -> SymbolTable {
        SymbolTable::new_inner(Some(parent))
    }

    fn new_inner(parent: Option<SymbolTablePtr>) -> SymbolTable {
        let id = SYMBOL_TABLE_ID_COUNTER.fetch_add(1, Ordering::Relaxed);
        trace!(
            "new symbol table: id = {id}  parent_id = {}",
            parent
                .as_ref()
                .map(|x| x.id().to_string())
                .unwrap_or(String::from("none"))
        );
        SymbolTable {
            table: IndexMap::new(),
            next_machine_name: 0,
            parent,
            local_bindings_xor: 0,
            local_bindings_generation: declaration_content_generation(),
            context_hash_cache: AtomicU64::new(NO_CONTEXT_HASH),
            context_hash_generation: AtomicU64::new(0),
        }
    }

    fn binding_contribution(name: &Name, declaration: &DeclarationPtr) -> u64 {
        let mut hasher = DefaultHasher::new();
        (name.clone(), declaration.content_hash()).hash(&mut hasher);
        hasher.finish()
    }

    fn finalize_context_hash(bindings_xor: u64, binding_count: usize) -> u64 {
        let mut hasher = DefaultHasher::new();
        binding_count.hash(&mut hasher);
        bindings_xor.hash(&mut hasher);
        hasher.finish()
    }

    fn recompute_local_bindings_xor(&mut self) {
        self.local_bindings_xor = self.table.iter().fold(0u64, |acc, (name, declaration)| {
            acc ^ Self::binding_contribution(name, declaration)
        });
        self.local_bindings_generation = declaration_content_generation();
    }

    /// Recomputes the incremental binding hash after shared declaration mutation.
    fn ensure_local_binding_hashes_current(&mut self) {
        if self.local_bindings_generation != declaration_content_generation() {
            self.recompute_local_bindings_xor();
        }
    }

    pub(crate) fn refresh_local_binding_hashes(&mut self) {
        self.recompute_local_bindings_xor();
        self.invalidate_context_hash_cache();
    }

    fn xor_binding_in(&mut self, name: &Name, declaration: &DeclarationPtr) {
        self.local_bindings_xor ^= Self::binding_contribution(name, declaration);
    }

    fn xor_binding_out(&mut self, name: &Name, declaration: &DeclarationPtr) {
        self.local_bindings_xor ^= Self::binding_contribution(name, declaration);
    }

    pub(crate) fn invalidate_context_hash_cache(&mut self) {
        self.context_hash_cache
            .store(NO_CONTEXT_HASH, Ordering::Relaxed);
        self.context_hash_generation.store(0, Ordering::Relaxed);
    }

    /// Returns a cached hash of all declarations visible from this scope.
    ///
    /// This hashes declaration values, not pointer identity, so rewrite caches remain valid across
    /// equivalent symbol states.
    pub fn context_hash(&self) -> u64 {
        let declaration_generation = declaration_content_generation();
        let cached_generation = self.context_hash_generation.load(Ordering::Acquire);
        let cached = self.context_hash_cache.load(Ordering::Relaxed);
        if cached != NO_CONTEXT_HASH && cached_generation == declaration_generation {
            return cached;
        }

        loop {
            let generation_before = declaration_content_generation();
            let hash = if self.parent.is_none() {
                let bindings_xor = if self.local_bindings_generation == generation_before {
                    self.local_bindings_xor
                } else {
                    self.table.iter().fold(0u64, |acc, (name, declaration)| {
                        acc ^ Self::binding_contribution(name, declaration)
                    })
                };
                Self::finalize_context_hash(bindings_xor, self.table.len())
            } else {
                self.compute_scoped_context_hash()
            };
            let generation_after = declaration_content_generation();
            if generation_before == generation_after {
                self.context_hash_cache.store(hash, Ordering::Relaxed);
                self.context_hash_generation
                    .store(generation_after, Ordering::Release);
                break hash;
            }
        }
    }

    fn compute_scoped_context_hash(&self) -> u64 {
        let mut hasher = DefaultHasher::new();
        let mut declarations: BTreeMap<Name, u64> = BTreeMap::new();

        for (name, declaration) in self.iter_local() {
            declarations.insert(name.clone(), declaration.content_hash());
        }

        let mut parent = self.parent.clone();
        while let Some(parent_ptr) = parent.take() {
            let guard = parent_ptr.read();
            for (name, declaration) in guard.iter_local() {
                declarations
                    .entry(name.clone())
                    .or_insert_with(|| declaration.content_hash());
            }
            parent.clone_from(guard.parent());
        }

        declarations.len().hash(&mut hasher);
        for declaration in declarations {
            declaration.hash(&mut hasher);
        }
        hasher.finish()
    }

    /// Looks up the declaration with the given name in the current scope only.
    ///
    /// Returns `None` if there is no declaration with that name in the current scope.
    pub fn lookup_local(&self, name: &Name) -> Option<DeclarationPtr> {
        self.table.get(name).cloned()
    }

    /// Looks up the declaration with the given name, checking all enclosing scopes.
    ///
    /// Returns `None` if there is no declaration with that name in scope.
    pub fn lookup(&self, name: &Name) -> Option<DeclarationPtr> {
        self.lookup_local(name).or_else(|| {
            self.parent
                .as_ref()
                .and_then(|parent| parent.read().lookup(name))
        })
    }

    /// Inserts a declaration into the symbol table.
    ///
    /// Returns `None` if there is already a symbol with this name in the local scope.
    pub fn insert(&mut self, declaration: DeclarationPtr) -> Option<()> {
        self.ensure_local_binding_hashes_current();
        let name = declaration.name().clone();
        let contribution = Self::binding_contribution(&name, &declaration);
        if let Entry::Vacant(e) = self.table.entry(name) {
            self.local_bindings_xor ^= contribution;
            e.insert(declaration);
            self.invalidate_context_hash_cache();
            Some(())
        } else {
            None
        }
    }

    /// Updates or adds a declaration in the immediate local scope.
    pub fn update_insert(&mut self, declaration: DeclarationPtr) {
        self.ensure_local_binding_hashes_current();
        let name = declaration.name().clone();
        if let Some(existing) = self.table.get(&name).cloned() {
            self.xor_binding_out(&name, &existing);
        }
        self.xor_binding_in(&name, &declaration);
        self.table.insert(name, declaration);
        self.invalidate_context_hash_cache();
    }

    /// Looks up the return type for name if it has one and is in scope.
    pub fn return_type(&self, name: &Name) -> Option<ReturnType> {
        self.lookup(name).map(|x| x.return_type())
    }

    /// Looks up the return type for name if has one and is in the local scope.
    pub fn return_type_local(&self, name: &Name) -> Option<ReturnType> {
        self.lookup_local(name).map(|x| x.return_type())
    }

    /// Looks up the domain of name if it has one and is in scope.
    ///
    /// This method can return domain references: if a ground domain is always required, use
    /// [`SymbolTable::resolve_domain`].
    pub fn domain(&self, name: &Name) -> Option<DomainPtr> {
        if let Name::WithRepresentation(name, _) = name {
            self.lookup(name)?.domain()
        } else {
            self.lookup(name)?.domain()
        }
    }

    /// Looks up the domain of name, resolving domain references to ground domains.
    ///
    /// See [`SymbolTable::domain`].
    pub fn resolve_domain(&self, name: &Name) -> Option<Moo<GroundDomain>> {
        self.domain(name)?.resolve().ok()
    }

    /// Iterates over entries in the LOCAL symbol table.
    pub fn into_iter_local(self) -> impl Iterator<Item = (Name, DeclarationPtr)> {
        self.table.into_iter()
    }

    /// Iterates over entries in the LOCAL symbol table, by reference.
    pub fn iter_local(&self) -> impl Iterator<Item = (&Name, &DeclarationPtr)> {
        self.table.iter()
    }

    /// Iterates over entries in the LOCAL symbol table, by reference.
    pub fn iter_local_mut(&mut self) -> impl Iterator<Item = (&Name, &mut DeclarationPtr)> {
        self.table.iter_mut()
    }

    /// Extends the symbol table with the given symbol table, updating the gensym counter if
    /// necessary.
    pub fn extend(&mut self, other: SymbolTable) {
        self.ensure_local_binding_hashes_current();
        self.next_machine_name = self.next_machine_name.max(other.next_machine_name);

        for (name, declaration) in &other.table {
            if let Some(existing) = self.table.get(name).cloned() {
                self.xor_binding_out(name, &existing);
            }
            self.xor_binding_in(name, declaration);
        }
        self.table.extend(other.table);
        self.invalidate_context_hash_cache();
    }

    /// Retains only local bindings that are new or changed relative to `baseline`.
    ///
    /// Rules traditionally build their effects by cloning the model symbol table and mutating the
    /// clone. Compacting that snapshot before application turns it into a small effect delta, so
    /// impact analysis and `extend` do not repeatedly process every unchanged declaration.
    pub(crate) fn retain_local_changes_from(&mut self, baseline: &SymbolTable) {
        self.table.retain(|name, declaration| {
            baseline
                .table
                .get(name)
                .is_none_or(|old| !declaration.content_eq(old))
        });
        self.recompute_local_bindings_xor();
        self.invalidate_context_hash_cache();
    }

    /// Creates a new [`DeclarationKind::Find`] declaration in this symbol table with a unique name.
    ///
    /// Prefer [`Self::gen_find_auxiliary`] for rewriter-introduced auxiliaries that must not be
    /// branched on. Use this only when a generated searchable find is intentionally required.
    pub fn gen_find(&mut self, domain: &DomainPtr) -> DeclarationPtr {
        let decl = DeclarationPtr::new_find(self.gen_sym(), domain.clone());
        self.insert(decl.clone());
        decl
    }

    /// Creates a new auxiliary find declaration in this symbol table with a unique name.
    ///
    /// See [`DeclarationPtr::new_find_auxiliary`].
    pub fn gen_find_auxiliary(&mut self, domain: &DomainPtr) -> DeclarationPtr {
        let decl = DeclarationPtr::new_find_auxiliary(self.gen_sym(), domain.clone());
        self.insert(decl.clone());
        decl
    }

    // Reserves a unique machine name in the symbol table
    pub fn gen_sym(&mut self) -> Name {
        let num = self.next_machine_name;
        self.next_machine_name += 1;
        Name::Machine(num)
    }

    /// Gets the parent of this symbol table as a mutable reference.
    ///
    /// This function provides no sanity checks.
    pub fn parent_mut_unchecked(&mut self) -> &mut Option<SymbolTablePtr> {
        &mut self.parent
    }

    /// Gets the parent of this symbol table.
    pub fn parent(&self) -> &Option<SymbolTablePtr> {
        &self.parent
    }

    /// Gets the representation `representation` for `name`.
    ///
    /// # Returns
    ///
    /// + `None` if `name` does not exist, is not a decision variable, or does not have that representation.
    pub fn get_representation(
        &self,
        name: &Name,
        representation: &[ReprId],
    ) -> Option<Vec<Box<dyn Representation>>> {
        // TODO: move representation stuff to declaration / variable to avoid cloning? (we have to
        // move inside of an rc here, so cannot return borrows)
        //
        // Also would prevent constant "does exist" "is var" checks.
        //
        // The reason it is not there now is because I'm getting serde issues...
        //
        // Also might run into issues putting get_or_add into declaration/variable, as that
        // requires us to mutably borrow both the symbol table, and the variable inside the symbol
        // table..

        let decl = self.lookup(name)?;
        let var = &decl.as_find()?;

        var.representations
            .iter()
            .find(|x| &x.iter().map(|r| r.repr_id()).collect_vec()[..] == representation)
            .cloned()
    }

    /// Gets all initialised representations for `name`.
    ///
    /// # Returns
    ///
    /// + `None` if `name` does not exist, or is not a decision variable.
    pub fn representations_for(&self, name: &Name) -> Option<Vec<Vec<Box<dyn Representation>>>> {
        let decl = self.lookup(name)?;
        decl.as_find().map(|x| x.representations.clone())
    }
}

impl IntoIterator for SymbolTable {
    type Item = (Name, DeclarationPtr);

    type IntoIter = SymbolTableIter;

    /// Iterates over symbol table entries in scope.
    fn into_iter(self) -> Self::IntoIter {
        SymbolTableIter {
            inner: self.table.into_iter(),
            parent: self.parent,
        }
    }
}

/// Iterator over all symbol table entries in scope.
pub struct SymbolTableIter {
    // iterator over the current scopes' btreemap
    inner: indexmap::map::IntoIter<Name, DeclarationPtr>,

    // the parent scope
    parent: Option<SymbolTablePtr>,
}

impl Iterator for SymbolTableIter {
    type Item = (Name, DeclarationPtr);

    fn next(&mut self) -> Option<Self::Item> {
        let mut val = self.inner.next();

        // Go up the tree until we find a parent symbol table with declarations to iterate over.
        //
        // Note that the parent symbol table may be empty - this is why this is a loop!
        while val.is_none() {
            let parent = self.parent.clone()?;

            let guard = parent.read();
            self.inner = guard.table.clone().into_iter();
            self.parent.clone_from(&guard.parent);

            val = self.inner.next();
        }

        val
    }
}

impl Default for SymbolTable {
    fn default() -> Self {
        Self::new_inner(None)
    }
}

// TODO: if we could override `Uniplate` impl but still derive `Biplate` instances,
//       we could remove some of this manual code
impl Uniplate for SymbolTable {
    fn uniplate(&self) -> (Tree<Self>, Box<dyn Fn(Tree<Self>) -> Self>) {
        // do not recurse up parents, that would be weird?
        let self2 = self.clone();
        (Tree::Zero, Box::new(move |_| self2.clone()))
    }
}

impl Biplate<SymbolTablePtr> for SymbolTable {
    fn biplate(
        &self,
    ) -> (
        Tree<SymbolTablePtr>,
        Box<dyn Fn(Tree<SymbolTablePtr>) -> Self>,
    ) {
        let self2 = self.clone();
        (Tree::Zero, Box::new(move |_| self2.clone()))
    }
}

impl Biplate<Expression> for SymbolTable {
    fn biplate(&self) -> (Tree<Expression>, Box<dyn Fn(Tree<Expression>) -> Self>) {
        let (child_trees, ctxs): (VecDeque<_>, Vec<_>) = self
            .table
            .values()
            .map(Biplate::<Expression>::biplate)
            .unzip();

        let tree = Tree::Many(child_trees);

        let self2 = self.clone();
        let ctx = Box::new(move |tree| {
            let Tree::Many(exprs) = tree else {
                panic!("unexpected children structure");
            };

            let mut self3 = self2.clone();
            let self3_iter = self3.table.iter_mut();
            for (ctx, tree, (_, decl)) in izip!(&ctxs, exprs, self3_iter) {
                // update declaration inside the pointer instead of creating a new one, so all
                // things referencing this keep referencing this.
                *decl = ctx(tree)
            }

            self3
        });

        (tree, ctx)
    }
}

impl Biplate<Comprehension> for SymbolTable {
    fn biplate(
        &self,
    ) -> (
        Tree<Comprehension>,
        Box<dyn Fn(Tree<Comprehension>) -> Self>,
    ) {
        let (expr_tree, expr_ctx) = <SymbolTable as Biplate<Expression>>::biplate(self);

        let (exprs, recons_expr_tree) = expr_tree.list();

        let (comprehension_tree, comprehension_ctx) =
            <VecDeque<Expression> as Biplate<Comprehension>>::biplate(&exprs);

        let ctx = Box::new(move |x| {
            // 1. turn comprehension tree into a list of expressions
            let exprs = comprehension_ctx(x);

            // 2. turn list of expressions into an expression tree
            let expr_tree = recons_expr_tree(exprs);

            // 3. turn expression tree into a symbol table
            expr_ctx(expr_tree)
        });

        (comprehension_tree, ctx)
    }
}

impl Biplate<Model> for SymbolTable {
    // walk into expressions
    fn biplate(&self) -> (Tree<Model>, Box<dyn Fn(Tree<Model>) -> Self>) {
        let (expr_tree, expr_ctx) = <SymbolTable as Biplate<Expression>>::biplate(self);

        let (exprs, recons_expr_tree) = expr_tree.list();

        let (submodel_tree, submodel_ctx) =
            <VecDeque<Expression> as Biplate<Model>>::biplate(&exprs);

        let ctx = Box::new(move |x| {
            // 1. turn submodel tree into a list of expressions
            let exprs = submodel_ctx(x);

            // 2. turn list of expressions into an expression tree
            let expr_tree = recons_expr_tree(exprs);

            // 3. turn expression tree into a symbol table
            expr_ctx(expr_tree)
        });
        (submodel_tree, ctx)
    }
}

#[cfg(test)]
mod tests {
    use std::hash::{DefaultHasher, Hash, Hasher};

    use super::*;
    use crate::ast::{Domain, Range, Reference};

    #[test]
    fn reference_observes_in_place_domain_update() {
        let old_domain = Domain::int(vec![Range::Bounded(1, 3)]);
        let new_domain = Domain::int(vec![Range::Bounded(1, 2)]);
        let mut declaration = DeclarationPtr::new_find(Name::user("x"), old_domain);
        let reference = Reference::new(declaration.clone());
        let original_id = reference.id();

        declaration.as_find_mut().unwrap().domain = new_domain.clone();

        assert_eq!(reference.id(), original_id);
        assert_eq!(reference.domain(), Some(new_domain));
    }

    #[test]
    fn context_hash_observes_shared_declaration_update() {
        let mut symbols = SymbolTable::new();
        let mut declaration =
            DeclarationPtr::new_find(Name::user("x"), Domain::int(vec![Range::Bounded(1, 3)]));
        symbols.insert(declaration.clone()).unwrap();
        let before = symbols.context_hash();

        declaration.as_find_mut().unwrap().domain = Domain::int(vec![Range::Bounded(1, 2)]);

        assert_ne!(symbols.context_hash(), before);
    }

    #[test]
    fn child_context_hash_observes_parent_declaration_update() {
        let parent = SymbolTablePtr::new();
        let mut declaration =
            DeclarationPtr::new_find(Name::user("x"), Domain::int(vec![Range::Bounded(1, 3)]));
        parent.write().insert(declaration.clone()).unwrap();
        let child = SymbolTable::with_parent(parent);
        let before = child.context_hash();

        declaration.as_find_mut().unwrap().domain = Domain::int(vec![Range::Bounded(1, 2)]);

        assert_ne!(child.context_hash(), before);
    }

    #[test]
    fn symbol_table_pointer_equality_and_hash_are_identity_based() {
        let left = SymbolTablePtr::new();
        let right = SymbolTablePtr::new();
        assert_ne!(left, right);

        let mut left_hasher = DefaultHasher::new();
        left.hash(&mut left_hasher);
        let mut clone_hasher = DefaultHasher::new();
        left.clone().hash(&mut clone_hasher);
        assert_eq!(left_hasher.finish(), clone_hasher.finish());
    }
}