conjure_cp_core/ast/

expressions.rs

use std::borrow::Cow;
use std::collections::{HashSet, VecDeque};
use std::fmt::{Display, Formatter};
use std::hash::{DefaultHasher, Hash, Hasher};
use std::sync::atomic::{AtomicU64, Ordering};

static HASH_HITS: AtomicU64 = AtomicU64::new(0);
static HASH_MISSES: AtomicU64 = AtomicU64::new(0);

pub fn print_hash_stats() {
    println!(
        "Expression content hash stats: hits={}, misses={}",
        HASH_HITS.load(Ordering::Relaxed),
        HASH_MISSES.load(Ordering::Relaxed)
    );
}
use tracing::trace;

use conjure_cp_enum_compatibility_macro::{document_compatibility, generate_discriminants};
use itertools::Itertools;
use serde::{Deserialize, Serialize};
use ustr::Ustr;

use polyquine::Quine;
use uniplate::{Biplate, Uniplate};

use crate::ast::metadata::NO_HASH;
use crate::bug;

use super::ac_operators::ACOperatorKind;
use super::categories::{Category, CategoryOf};
use super::collection_domains::{
    SetOperation, SizeBounds, bounded_set, collection_size, distinct_size, mset_size,
    set_operation_domain,
};
use super::comprehension::Comprehension;
use super::declaration::DeclarationKind;
use super::domains::HasDomain as _;
use super::eval::eval_constant;
use super::expression_domains::{
    absolute_integer_domain, binary_integer_domain,
    bounded_i32_domain_for_matrix_literal_monotonic, division_domain,
    empty_matrix_integer_element_domain, factorial_domain, get_function_codomain,
    matrix_element_domain, modulo_domain, mset_union_result_domain, power_integer_domain,
    sum_domain_of_child,
};
use super::function_domains::{
    defined_domain, function_size, image_set_domain, pre_image_domain, range_domain,
    restricted_domain,
};
use super::pretty::{pretty_expression_domain_annotation, pretty_expression_type_annotation};
use super::pretty::{pretty_expressions_as_top_level, pretty_vec};
use super::records::Field;
use super::sat_encoding::SATIntEncoding;
use super::{
    AbstractLiteral, Atom, DeclarationPtr, Domain, DomainPtr, GroundDomain, IntVal, Literal,
    MSetAttr, Metadata, Model, Moo, Name, PartialityAttr, Range, Reference, RelAttr, ReturnType,
    SetAttr, SymbolTable, SymbolTablePtr, Typeable, matrix,
};

// Ensure that this type doesn't get too big
//
// If you triggered this assertion, you either made a variant of this enum that is too big, or you
// made Name,Literal,AbstractLiteral,Atom bigger, which made this bigger! To fix this, put some
// stuff in boxes.
//
// Enums take the size of their largest variant, so an enum with mostly small variants and a few
// large ones wastes memory... A larger Expression type also slows down Oxide.
//
// For more information, and more details on type sizes and how to measure them, see the commit
// message for 6012de809 (perf: reduce size of AST types, 2025-06-18).
//
// You can also see type sizes in the rustdoc documentation, generated by ./tools/gen_docs.sh
//
// https://github.com/conjure-cp/conjure-oxide/commit/6012de8096ca491ded91ecec61352fdf4e994f2e

// TODO: box all usages of Metadata to bring this down a bit more - I have added variants to
// ReturnType, and Metadata contains ReturnType, so Metadata has got bigger. Metadata will get a
// lot bigger still when we start using it for memoisation, so it should really be
// boxed ~niklasdewally

// Metadata's mutex makes the exact layout platform-dependent, so enforce only the intended
// upper bound. The largest known layout is 152 bytes.
static_assertions::const_assert!(std::mem::size_of::<Expression>() <= 152);

/// Represents different types of expressions used to define rules and constraints in the model.
///
/// The `Expression` enum includes operations, constants, and variable references
/// used to build rules and conditions for the model.
#[generate_discriminants]
#[document_compatibility]
#[derive(Clone, Debug, Hash, PartialEq, Eq, Serialize, Deserialize, Uniplate, Quine)]
#[biplate(to=AbstractLiteral<Expression>)]
#[biplate(to=AbstractLiteral<Literal>)]
#[biplate(to=Atom)]
#[biplate(to=Comprehension)]
#[biplate(to=DeclarationPtr)]
#[biplate(to=DomainPtr)]
#[biplate(to=Literal)]
#[biplate(to=Metadata)]
#[biplate(to=Name)]
#[biplate(to=Option<Expression>)]
#[biplate(to=Field<Expression>)]
#[biplate(to=Field<Literal>)]
#[biplate(to=Reference)]
#[biplate(to=Model)]
#[biplate(to=SymbolTable)]
#[biplate(to=SymbolTablePtr)]
#[biplate(to=Vec<Expression>)]
#[path_prefix(conjure_cp::ast)]
pub enum Expression {
    AbstractLiteral(Metadata, AbstractLiteral<Expression>),
    /// The top of the model
    Root(Metadata, Vec<Expression>),

    /// An expression representing "A is valid as long as B is true"
    /// Turns into a conjunction when it reaches a boolean context
    Bubble(Metadata, Moo<Expression>, Moo<Expression>),

    /// A comprehension.
    ///
    /// The inside of the comprehension opens a new scope.
    // todo (gskorokhod): Comprehension contains a symbol table which contains a bunch of pointers.
    // This makes implementing Quine tricky (it doesnt support Rc, by design). Skip it for now.
    #[polyquine_skip]
    Comprehension(Metadata, Moo<Comprehension>),

    /// Defines dominance ("Solution A is preferred over Solution B")
    DominanceRelation(Metadata, Moo<Expression>),
    /// `fromSolution(name)` - Used in dominance relation definitions
    FromSolution(Metadata, Moo<Atom>),

    #[polyquine_with(arm = (_, name) => {
        let ident = proc_macro2::Ident::new(name.as_str(), proc_macro2::Span::call_site());
        quote::quote! { #ident.clone().into() }
    })]
    Metavar(Metadata, Ustr),

    Atomic(Metadata, Atom),

    /// Type annotation expression: `expr :: type`.
    TypeAnnotation(Metadata, Moo<Expression>, DomainPtr),

    /// Domain annotation expression: `expr : domain`.
    DomainAnnotation(Metadata, Moo<Expression>, DomainPtr),

    /// Asserts that the given variant of a variant expression is in use.
    /// See also: [GroundDomain::Variant]
    #[compatible(JsonInput)]
    Active(Metadata, Moo<Expression>, Name),

    /// Indexing into a record expression, e.g `{foo = 1, bar = true}[foo]`
    /// See also: [GroundDomain::Record]
    #[compatible(JsonInput)]
    RecordField(Metadata, Moo<Expression>, Name),

    /// A matrix index.
    ///
    /// Defined iff the indices are within their respective index domains.
    #[compatible(JsonInput)]
    UnsafeIndex(Metadata, Moo<Expression>, Vec<Expression>),

    /// A safe matrix index.
    ///
    /// See [`Expression::UnsafeIndex`]
    #[compatible(SMT)]
    SafeIndex(Metadata, Moo<Expression>, Vec<Expression>),

    /// Internal total element definition. Outside the index domain, the value is unconstrained.
    /// Safe indexing introduces this before representation-specific comparisons finish lowering.
    #[polyquine_skip]
    SatElement(Metadata, Moo<Expression>, Moo<Expression>, Moo<Expression>),

    /// Whole-value distinctness after constructing representation-independent comparisons.
    SatAllDifferentComparisons(Metadata, Moo<Expression>),

    /// A matrix slice: `a[indices]`.
    ///
    /// One of the indicies may be `None`, representing the dimension of the matrix we want to take
    /// a slice of. For example, for some 3d matrix a, `a[1,..,2]` has the indices
    /// `Some(1),None,Some(2)`.
    ///
    /// It is assumed that the slice only has one "wild-card" dimension and thus is 1 dimensional.
    ///
    /// Defined iff the defined indices are within their respective index domains.
    #[compatible(JsonInput)]
    UnsafeSlice(Metadata, Moo<Expression>, Vec<Option<Expression>>),

    /// A safe matrix slice: `a[indices]`.
    ///
    /// See [`Expression::UnsafeSlice`].
    SafeSlice(Metadata, Moo<Expression>, Vec<Option<Expression>>),

    /// `inDomain(x,domain)` iff `x` is in the domain `domain`.
    ///
    /// This cannot be constructed from Essence input, nor passed to a solver: this expression is
    /// mainly used during the conversion of `UnsafeIndex` and `UnsafeSlice` to `SafeIndex` and
    /// `SafeSlice` respectively.
    InDomain(Metadata, Moo<Expression>, DomainPtr),

    /// `toInt(b)` casts boolean expression b to an integer.
    ///
    /// - If b is false, then `toInt(b) == 0`
    ///
    /// - If b is true, then `toInt(b) == 1`
    #[compatible(SMT)]
    ToInt(Metadata, Moo<Expression>),

    /// `|x|` - absolute value of `x`
    #[compatible(JsonInput, SMT)]
    Abs(Metadata, Moo<Expression>),

    /// `sum(<vec_expr>)`
    #[compatible(JsonInput, SMT)]
    Sum(Metadata, Moo<Expression>),

    /// `a * b * c * ...`
    #[compatible(JsonInput, SMT)]
    Product(Metadata, Moo<Expression>),

    /// `min(<vec_expr>)`
    #[compatible(JsonInput, SMT)]
    Min(Metadata, Moo<Expression>),

    /// `max(<vec_expr>)`
    #[compatible(JsonInput, SMT)]
    Max(Metadata, Moo<Expression>),

    /// `not(a)`
    #[compatible(JsonInput, SAT, SMT)]
    Not(Metadata, Moo<Expression>),

    /// `or(<vec_expr>)`
    #[compatible(JsonInput, SAT, SMT)]
    Or(Metadata, Moo<Expression>),

    /// `and(<vec_expr>)`
    #[compatible(JsonInput, SAT, SMT)]
    And(Metadata, Moo<Expression>),

    /// Ensures that `a->b` (material implication).
    #[compatible(JsonInput, SMT)]
    Imply(Metadata, Moo<Expression>, Moo<Expression>),

    /// `iff(a, b)` a <-> b
    #[compatible(JsonInput, SMT)]
    Iff(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    Union(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    In(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    Intersect(Metadata, Moo<Expression>, Moo<Expression>),

    /// Set difference, `a - b`.
    ///
    /// Spelled with minus in Essence, but kept apart from [`Expression::Minus`]: the two share a
    /// symbol and nothing else, and overloading one node for both made every arithmetic rule have
    /// to ask whether its operands were really sets.
    #[compatible(JsonInput)]
    Difference(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    Supset(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    SupsetEq(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    Subset(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    SubsetEq(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput, SMT)]
    Eq(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput, SMT)]
    Neq(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput, SMT)]
    Geq(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput, SMT)]
    Leq(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput, SMT)]
    Gt(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput, SMT)]
    Lt(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    Pred(Metadata, Moo<Expression>),

    #[compatible(JsonInput)]
    Succ(Metadata, Moo<Expression>),

    /// `s subsequence t` tests whether the list of values taken by s occurs in the same order
    /// in the list of values taken by t
    #[compatible(JsonInput)]
    Subsequence(Metadata, Moo<Expression>, Moo<Expression>),

    /// `s substring t` tests whether the list of values taken by s occurs in the same order
    /// and contiguously in the list of values taken by t
    #[compatible(JsonInput)]
    Substring(Metadata, Moo<Expression>, Moo<Expression>),

    /// `catchUndef(e, d)`: `e` where `e` is defined, `d` where it is not.
    ///
    /// Definedness is only known once the bubble rules have run, so this survives until then and
    /// is lowered against the bubble condition the inner expression produces.
    #[compatible(JsonInput)]
    CatchUndef(Metadata, Moo<Expression>, Moo<Expression>),

    /// Division after preventing division by zero, usually with a bubble
    #[compatible(SMT)]
    SafeDiv(Metadata, Moo<Expression>, Moo<Expression>),

    /// Division with a possibly undefined value (division by 0)
    #[compatible(JsonInput)]
    UnsafeDiv(Metadata, Moo<Expression>, Moo<Expression>),

    /// Modulo after preventing mod 0, usually with a bubble
    #[compatible(SMT)]
    SafeMod(Metadata, Moo<Expression>, Moo<Expression>),

    /// Modulo with a possibly undefined value (mod 0)
    #[compatible(JsonInput)]
    UnsafeMod(Metadata, Moo<Expression>, Moo<Expression>),

    /// Negation: `-x`
    #[compatible(JsonInput, SMT)]
    Neg(Metadata, Moo<Expression>),

    /// Factorial: `x!` or 'factorial(x)`
    #[compatible(JsonInput)]
    Factorial(Metadata, Moo<Expression>),

    /// Set of domain values function is defined for
    #[compatible(JsonInput)]
    Defined(Metadata, Moo<Expression>),

    /// Set of codomain values function is defined for
    #[compatible(JsonInput)]
    Range(Metadata, Moo<Expression>),

    #[compatible(JsonInput)]
    ToSet(Metadata, Moo<Expression>),

    #[compatible(JsonInput)]
    ToMSet(Metadata, Moo<Expression>),

    #[compatible(JsonInput)]
    ToRelation(Metadata, Moo<Expression>),

    /// Unsafe power`x**y` (possibly undefined)
    ///
    /// Defined when (X!=0 \\/ Y!=0) /\ Y>=0
    #[compatible(JsonInput)]
    UnsafePow(Metadata, Moo<Expression>, Moo<Expression>),

    /// `UnsafePow` after preventing undefinedness
    SafePow(Metadata, Moo<Expression>, Moo<Expression>),

    /// Flatten matrix operator
    /// `flatten(M)` or `flatten(n, M)`
    /// where M is a matrix and n is an optional integer argument indicating depth of flattening
    Flatten(Metadata, Option<Moo<Expression>>, Moo<Expression>),

    /// An attribute predicate used as a constraint, e.g. `reflexive(r)` or `size(s, 3)`.
    /// Lifted into the target's declaration domain attributes when possible (see
    /// `passes::attribute_as_constraint`); expanded in place to the equivalent formula otherwise.
    AttributeAsConstraint(Metadata, Moo<Expression>, Ustr, Option<Moo<Expression>>),

    /// `allDifferent(<vec_expr>)`
    #[compatible(JsonInput)]
    AllDiff(Metadata, Moo<Expression>),

    /// Z3's native `distinct` over the elements of `<vec_expr>`.
    ///
    /// This is emitted for the SMT backend only, and never appears in a model bound for any other
    /// solver. It exists so that "hand `allDifferent` to Z3 as `distinct`" and "encode
    /// `allDifferent` explicitly" are two rules competing at the same choice site, which is what
    /// lets the heuristics pick between them -- and what records the choice in the model, so it is
    /// not asked again every time the expression is visited.
    #[compatible(SMT)]
    SmtDistinct(Metadata, Moo<Expression>),

    /// `allDifferentExcept(<matrix>, <except>)`
    #[compatible(JsonInput)]
    AllDifferentExcept(Metadata, Moo<Expression>, Moo<Expression>),

    /// Select a scalar matrix entry, returning the index itself outside the index domain.
    ElementId(Metadata, Moo<Expression>, Moo<Expression>),

    /// Internal inverse lookup used to locate a function argument among its domain values.
    #[polyquine_skip]
    IndexOf(Metadata, Moo<Expression>, Moo<Expression>),

    /// `table(sequence(x1, x2, ...), {sequence(r11, r12, ...), sequence(r21, r22, ...), ...})`
    ///
    /// Represents a positive table constraint: the input sequence must match one of the
    /// allowed rows.
    #[compatible(JsonInput)]
    Table(Metadata, Moo<Expression>, Moo<Expression>),

    /// `negativeTable(sequence(x1, x2, ...), rows)` forbids the set of sequence rows.
    ///
    /// Represents a negative table constraint: the input sequence must NOT match any of the
    /// forbidden rows.
    #[compatible(JsonInput)]
    NegativeTable(Metadata, Moo<Expression>, Moo<Expression>),

    /// `shortTable(sequence(x1, x2, ...), {{(position, value), ...}, ...})` uses one-based positions.
    /// Omitted positions are wildcards; each sparse row and the relation itself are sets.
    ShortTable(Metadata, Moo<Expression>, Moo<Expression>),

    /// Minion table relation with scalar inputs and numeric rows; the flag forbids matching rows.
    #[polyquine_skip]
    FlatTable(Metadata, Vec<Atom>, Vec<Vec<i32>>, bool),

    /// Minion sparse table with zero-based positions and numeric values; omitted inputs are wildcards.
    #[polyquine_skip]
    FlatShortTable(Metadata, Vec<Atom>, Vec<Vec<(usize, i32)>>),

    /// `atleast(vars, counts, values)`
    ///
    /// For each `values[i]`, requires at least `counts[i]` occurrences in `vars`.
    #[compatible(JsonInput)]
    AtLeast(Metadata, Moo<Expression>, Moo<Expression>, Moo<Expression>),

    /// `atmost(vars, counts, values)`
    ///
    /// For each `values[i]`, requires at most `counts[i]` occurrences in `vars`.
    #[compatible(JsonInput)]
    AtMost(Metadata, Moo<Expression>, Moo<Expression>, Moo<Expression>),

    /// `gcc(vars, values, counts)`
    ///
    /// Global cardinality constraint. For each `values[i]`, requires exactly `counts[i]`
    /// occurrences in `vars`.
    #[compatible(JsonInput)]
    Gcc(Metadata, Moo<Expression>, Moo<Expression>, Moo<Expression>),

    /// Minion `gccweak(vars, values, counts)` — weaker propagation variant of `gcc`.
    #[compatible(Minion)]
    GccWeak(Metadata, Moo<Expression>, Moo<Expression>, Moo<Expression>),

    /// Binary subtraction operator
    ///
    /// This is a parser-level construct, and is immediately normalised to `Sum([a,-b])`.
    /// TODO: make this compatible with Set Difference calculations - need to change return type and domain for this expression and write a set comprehension rule.
    /// have already edited minus_to_sum to prevent this from applying to sets
    #[compatible(JsonInput)]
    Minus(Metadata, Moo<Expression>, Moo<Expression>),

    /// Partition Operator: test if a list of elements are not all contained in one part of the partition
    /// First Expr Arg is a list of elements
    /// Second Expr Arg is the partition
    #[compatible(JsonInput)]
    Apart(Metadata, Moo<Expression>, Moo<Expression>),

    /// Partition Operator: union of all parts of a partition
    /// Expr Arg is a partition
    #[compatible(JsonInput)]
    Participants(Metadata, Moo<Expression>),

    /// Partition Operator: part of partition that contains specified element
    /// First Expr Arg is an element that should be contained
    /// Second Expr Arg is the partition that should contain that element
    #[compatible(JsonInput)]
    Party(Metadata, Moo<Expression>, Moo<Expression>),

    /// Partition Operator: partition to its set of parts
    /// Expr Arg is the partition from which the parts come from
    #[compatible(JsonInput)]
    Parts(Metadata, Moo<Expression>),

    /// Partition Operator: test if a list of elements are all in the same part of the partition
    /// First Expr Arg is the list of elements to test with
    /// Second Expr Arg is the partition to test on
    #[compatible(JsonInput)]
    Together(Metadata, Moo<Expression>, Moo<Expression>),

    /// Ensures that x=|y| i.e. x is the absolute value of y.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#abs)
    #[compatible(Minion)]
    FlatAbsEq(Metadata, Moo<Atom>, Moo<Atom>),

    /// Ensures that `alldiff([a,b,...])`.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#alldiff)
    #[compatible(Minion)]
    FlatAllDiff(Metadata, Vec<Atom>),

    /// Ensures that `result = min(vars)`.
    ///
    /// Low-level Minion constraint. Prefer this over expanding [`Expression::Min`] into
    /// leq/or/eq constraints when targeting Minion.
    ///
    /// # See also
    ///
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#min)
    #[compatible(Minion)]
    FlatMinEq(Metadata, Vec<Atom>, Atom),

    /// Ensures that sum(vec) >= x.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#sumgeq)
    #[compatible(Minion)]
    FlatSumGeq(Metadata, Vec<Atom>, Atom),

    /// Ensures that sum(vec) <= x.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#sumleq)
    #[compatible(Minion)]
    FlatSumLeq(Metadata, Vec<Atom>, Atom),

    /// `ineq(x,y,k)` ensures that x <= y + k.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#ineq)
    #[compatible(Minion)]
    FlatIneq(Metadata, Moo<Atom>, Moo<Atom>, Box<Literal>),

    /// `w-literal(x,k)` ensures that x == k, where x is a variable and k a constant.
    ///
    /// Low-level Minion constraint.
    ///
    /// This is a low-level Minion constraint and you should probably use Eq instead. The main use
    /// of w-literal is to convert boolean variables to constraints so that they can be used inside
    /// watched-and and watched-or.
    ///
    /// # See also
    ///
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#minuseq)
    /// + `rules::minion::boolean_literal_to_wliteral`.
    #[compatible(Minion)]
    #[polyquine_skip]
    FlatWatchedLiteral(Metadata, Reference, Literal),

    /// `weightedsumleq(cs,xs,total)` ensures that cs.xs <= total, where cs.xs is the scalar dot
    /// product of cs and xs.
    ///
    /// Low-level Minion constraint.
    ///
    /// Represents a weighted sum of the form `ax + by + cz + ...`
    ///
    /// # See also
    ///
    /// + [Minion
    /// documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#weightedsumleq)
    FlatWeightedSumLeq(Metadata, Vec<Literal>, Vec<Atom>, Moo<Atom>),

    /// `weightedsumgeq(cs,xs,total)` ensures that cs.xs >= total, where cs.xs is the scalar dot
    /// product of cs and xs.
    ///
    /// Low-level Minion constraint.
    ///
    /// Represents a weighted sum of the form `ax + by + cz + ...`
    ///
    /// # See also
    ///
    /// + [Minion
    /// documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#weightedsumleq)
    FlatWeightedSumGeq(Metadata, Vec<Literal>, Vec<Atom>, Moo<Atom>),

    /// Ensures that x =-y, where x and y are atoms.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#minuseq)
    #[compatible(Minion)]
    FlatMinusEq(Metadata, Moo<Atom>, Moo<Atom>),

    /// Ensures that x*y=z.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#product)
    #[compatible(Minion)]
    FlatProductEq(Metadata, Moo<Atom>, Moo<Atom>, Moo<Atom>),

    /// Ensures that floor(x/y)=z. Always true when y=0.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#div_undefzero)
    #[compatible(Minion)]
    MinionDivEqUndefZero(Metadata, Moo<Atom>, Moo<Atom>, Moo<Atom>),

    /// Ensures that x%y=z. Always true when y=0.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#mod_undefzero)
    #[compatible(Minion)]
    MinionModuloEqUndefZero(Metadata, Moo<Atom>, Moo<Atom>, Moo<Atom>),

    /// Ensures that `x**y = z`.
    ///
    /// Low-level Minion constraint.
    ///
    /// This constraint is false when `y<0` except for `1**y=1` and `(-1)**y=z` (where z is 1 if y
    /// is odd and z is -1 if y is even).
    ///
    /// # See also
    ///
    /// + [Github comment about `pow` semantics](https://github.com/minion/minion/issues/40#issuecomment-2595914891)
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#pow)
    MinionPow(Metadata, Moo<Atom>, Moo<Atom>, Moo<Atom>),

    /// `reify(constraint,r)` ensures that r=1 iff `constraint` is satisfied, where r is a 0/1
    /// variable.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    ///  + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#reify)
    #[compatible(Minion)]
    MinionReify(Metadata, Moo<Expression>, Atom),

    /// `reifyimply(constraint,r)` ensures that `r->constraint`, where r is a 0/1 variable.
    /// variable.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    ///  + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#reifyimply)
    #[compatible(Minion)]
    MinionReifyImply(Metadata, Moo<Expression>, Atom),

    /// `w-inintervalset(x, [a1,a2, b1,b2, … ])` ensures that the value of x belongs to one of the
    /// intervals {a1,…,a2}, {b1,…,b2} etc.
    ///
    /// The list of intervals must be given in numerical order.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///>
    ///  + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#w-inintervalset)
    #[compatible(Minion)]
    MinionWInIntervalSet(Metadata, Atom, Vec<i32>),

    /// `w-inset(x, [v1, v2, … ])` ensures that the value of `x` is one of the explicitly given values `v1`, `v2`, etc.
    ///
    /// This constraint enforces membership in a specific set of discrete values rather than intervals.
    ///
    /// The list of values must be given in numerical order.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    ///  + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#w-inset)
    #[compatible(Minion)]
    MinionWInSet(Metadata, Atom, Vec<i32>),

    /// `element_one(vec, i, e)` specifies that `vec[i] = e`. This implies that i is
    /// in the range `[1..len(vec)]`.
    ///
    /// Low-level Minion constraint.
    ///
    /// # See also
    ///
    ///  + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#element_one)
    #[compatible(Minion)]
    MinionElementOne(Metadata, Vec<Atom>, Moo<Atom>, Moo<Atom>),

    /// Declaration of an auxiliary variable.
    ///
    /// As with Savile Row, we semantically distinguish this from `Eq`.
    #[compatible(Minion)]
    #[polyquine_skip]
    AuxDeclaration(Metadata, Reference, Moo<Expression>),

    /// This expression is for encoding ints for the SAT solver, it stores the encoding type, the vector of booleans and the min/max for the int.
    #[compatible(SAT)]
    SATInt(Metadata, SATIntEncoding, Moo<Expression>, (i32, i32)),
    /// Retain an optimisation objective until its actual-value SAT view is ready.
    #[compatible(SAT)]
    SatObjective(Metadata, bool, Moo<Expression>),

    /// Addition over a pair of expressions (i.e. a + b) rather than a vec-expr like Expression::Sum.
    /// This is for compatibility with backends that do not support addition over vectors.
    #[compatible(SMT)]
    PairwiseSum(Metadata, Moo<Expression>, Moo<Expression>),

    /// Multiplication over a pair of expressions (i.e. a * b) rather than a vec-expr like Expression::Product.
    /// This is for compatibility with backends that do not support multiplication over vectors.
    #[compatible(SMT)]
    PairwiseProduct(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    Image(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    ImageSet(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    PreImage(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    Inverse(Metadata, Moo<Expression>, Moo<Expression>),

    /// `permInverse(p)`: the inverse of permutation `p`, as a new permutation value. Not to be
    /// confused with [`Expression::Inverse`], which is a boolean predicate over a pair of
    /// permutations, not a value-returning operator.
    #[compatible(JsonInput)]
    PermInverse(Metadata, Moo<Expression>),

    /// `compose(g, h)`: the permutation obtained by applying `h` then `g`, as a new permutation
    /// value (`image(compose(g, h), i) = image(g, image(h, i))`).
    #[compatible(JsonInput)]
    Compose(Metadata, Moo<Expression>, Moo<Expression>),

    #[compatible(JsonInput)]
    Restrict(Metadata, Moo<Expression>, Moo<Expression>),

    /// Lexicographical < between two matrices.
    ///
    /// A <lex B iff: A[i] < B[i] for some i /\ (A[j] > B[j] for some j -> i < j)
    /// I.e. A must be less than B at some index i, and if it is greater than B at another index j,
    /// then j comes after i.
    /// I.e. A must be greater than B at the first index where they differ.
    ///
    /// E.g. [1, 1] <lex [2, 1] and [1, 1] <lex [1, 2]
    LexLt(Metadata, Moo<Expression>, Moo<Expression>),

    /// Lexicographical <= between two matrices
    LexLeq(Metadata, Moo<Expression>, Moo<Expression>),

    /// Lexicographical > between two matrices
    /// This is a parser-level construct, and is immediately normalised to LexLt(b, a)
    LexGt(Metadata, Moo<Expression>, Moo<Expression>),

    /// Lexicographical >= between two matrices
    /// This is a parser-level construct, and is immediately normalised to LexLeq(b, a)
    LexGeq(Metadata, Moo<Expression>, Moo<Expression>),

    /// Low-level minion constraint. See Expression::LexLt
    FlatLexLt(Metadata, Vec<Atom>, Vec<Atom>),

    /// Low-level minion constraint. See Expression::LexLeq
    FlatLexLeq(Metadata, Vec<Atom>, Vec<Atom>),

    /// Alters the shape of relations by projection
    #[compatible(JsonInput)]
    RelationProj(Metadata, Moo<Expression>, Vec<Option<Expression>>),

    /// Cardinality of a collection type
    #[compatible(JsonInput)]
    Card(Metadata, Moo<Expression>),
}

impl Expression {
    /// Returns the possible values of the expression, recursing to leaf expressions.
    ///
    /// Cached in this node's own `Metadata`: `domain_of_uncached` recomputes recursively from
    /// scratch with no memoisation of its own, so repeatedly calling `domain_of` on the same
    /// subtree (as rules that check "is this operand scalar/abstract" tend to, once per rule
    /// attempt) is quadratic in the worst case without a cache. The cache is invalidated when
    /// this expression or a descendant changes.
    pub fn domain_of(&self) -> Option<DomainPtr> {
        self.meta_ref().domain_or_init(|| self.domain_of_uncached())
    }

    /// Bypasses the cache in `domain_of`. Needed by callers that read an expression stored
    /// *inside a declaration* (e.g. `Declaration::domain`, for `ValueLetting`/`QuantifiedExpr`):
    /// such expressions live outside the tree the rewrite engine walks to invalidate
    /// `Metadata::domain`, the same "reference embedded outside the standard rewrite tree" gap
    /// documented for `Reference::get_repr_as` and comprehension `ExpressionGenerator` sources.
    pub(crate) fn domain_of_uncached(&self) -> Option<DomainPtr> {
        match self {
            Expression::Union(_, a, b) => {
                let lhs = a.domain_of()?;
                let rhs = b.domain_of()?;
                set_operation_domain(a, b, SetOperation::Union)
                    .or_else(|| mset_union_result_domain(a, b))
                    .or_else(|| lhs.union(&rhs).ok())
            }
            Expression::Intersect(_, a, b) => set_operation_domain(a, b, SetOperation::Intersect)
                .or_else(|| a.domain_of()?.intersect(&b.domain_of()?).ok()),
            Expression::Difference(_, a, b) => set_operation_domain(a, b, SetOperation::Difference),
            Expression::In(_, _, _) => Some(Domain::bool()),
            Expression::Supset(_, _, _) => Some(Domain::bool()),
            Expression::SupsetEq(_, _, _) => Some(Domain::bool()),
            Expression::Subset(_, _, _) => Some(Domain::bool()),
            Expression::SubsetEq(_, _, _) => Some(Domain::bool()),
            Expression::AbstractLiteral(_, abslit) => abslit.domain_of(),
            Expression::DominanceRelation(_, _) => Some(Domain::bool()),
            Expression::FromSolution(_, expr) => Some(expr.domain_of()),
            Expression::Metavar(_, _) => None,
            Expression::Comprehension(_, comprehension) => comprehension.domain_of(),
            Expression::RecordField(_, rec, field_name) => {
                let rec_ents = rec.domain_of()?.as_record()?;
                for ent in rec_ents {
                    if ent.name.eq(field_name) {
                        return Some(ent.value);
                    }
                }
                None
            }
            Expression::UnsafeIndex(_, matrix, index) | Expression::SafeIndex(_, matrix, index) => {
                let dom = matrix.domain_of()?;
                let resolved_dom = dom.resolve().ok().map(Domain::Ground);
                if dom.as_matrix().is_some()
                    || resolved_dom
                        .as_ref()
                        .is_some_and(|dom| dom.as_matrix().is_some())
                {
                    // A matrix domain may be written flat -- `Matrix(int, [d1, d2])` -- or nested
                    // -- `Matrix(Matrix(int, [d2]), [d1])` -- and both mean the same thing. Each
                    // level consumes as many indices as it declares, so peel a level at a time
                    // until the indices run out rather than assuming one level covers them all.
                    let mut current = dom;
                    let mut remaining = index.len();
                    while remaining > 0 {
                        let resolved = current.resolve().ok().map(Domain::Ground);
                        let Some((elem_domain, idx_domains)) = current
                            .as_matrix()
                            .or_else(|| resolved.as_ref()?.as_matrix())
                        else {
                            break;
                        };
                        // Fewer indices than this level declares is a partial index: what is left
                        // is a matrix over the dimensions that were not given.
                        if idx_domains.len() > remaining {
                            return Some(Domain::matrix(
                                elem_domain,
                                idx_domains[remaining..].to_vec(),
                            ));
                        }
                        remaining -= idx_domains.len();
                        current = elem_domain;
                    }
                    return Some(current);
                }

                // Indexing a tuple picks one component, so the domain is that component's --
                // known only when the position is a literal, as tuple components need not share
                // a domain.
                if let Some(components) =
                    dom.as_tuple().or_else(|| resolved_dom.as_ref()?.as_tuple())
                {
                    let Expression::Atomic(_, Atom::Literal(Literal::Int(index))) =
                        index.first()?
                    else {
                        return None;
                    };
                    let index: usize = (*index - 1).try_into().ok()?;
                    return components.get(index).cloned();
                }

                if let Some(doms) = dom.as_variant().or(dom.as_record()).or_else(|| {
                    let resolved_dom = resolved_dom.as_ref()?;
                    resolved_dom.as_variant().or(resolved_dom.as_record())
                }) {
                    let index_expr = index.first()?;
                    return match index_expr {
                        Expression::Atomic(_, Atom::Reference(reference)) => {
                            for inner_dom in doms {
                                if *reference.name() == inner_dom.name {
                                    return Some(inner_dom.value);
                                }
                            }
                            None
                        }
                        Expression::Atomic(_, Atom::Literal(Literal::Int(index))) => {
                            let index: usize = (*index - 1).try_into().ok()?;
                            doms.get(index).map(|inner_dom| inner_dom.value.clone())
                        }
                        _ => None,
                    };
                }

                bug!(
                    "subject of an index operation should support indexing, but got {matrix}: {dom}"
                )
            }
            Expression::UnsafeSlice(_, matrix, indices)
            | Expression::SafeSlice(_, matrix, indices) => {
                let sliced_dimension = indices.iter().position(Option::is_none);

                let dom = matrix.domain_of()?;
                let Some((elem_domain, index_domains)) = dom.as_matrix() else {
                    bug!("subject of an index operation should be a matrix");
                };

                match sliced_dimension {
                    Some(dimension) => Some(Domain::matrix(
                        elem_domain,
                        vec![index_domains[dimension].clone()],
                    )),

                    // same as index
                    None => Some(elem_domain),
                }
            }
            Expression::InDomain(_, _, _) => Some(Domain::bool()),
            Expression::Atomic(_, atom) => Some(atom.domain_of()),
            Expression::TypeAnnotation(_, expr, _) => expr.domain_of(),
            Expression::DomainAnnotation(_, _, domain) => Some(domain.clone()),
            Expression::Sum(_, e) => sum_domain_of_child(e).or_else(|| {
                // Fall back when corner products of bounds overflow i32.
                bounded_i32_domain_for_matrix_literal_monotonic(e, i32::checked_add)
            }),
            Expression::Product(_, e) => {
                // Grocery-style products (e.g. four int(0..711) factors) overflow i32;
                // return None so callers can omit a precise product domain rather than panic.
                bounded_i32_domain_for_matrix_literal_monotonic(e, i32::checked_mul)
            }
            Expression::Min(_, e) => {
                if empty_matrix_integer_element_domain(e).is_some() {
                    return Some(Domain::empty(ReturnType::Int));
                }
                bounded_i32_domain_for_matrix_literal_monotonic(e, |x, y| {
                    Some(if x < y { x } else { y })
                })
                .or_else(|| matrix_element_domain(e))
            }
            Expression::Max(_, e) => {
                if empty_matrix_integer_element_domain(e).is_some() {
                    return Some(Domain::empty(ReturnType::Int));
                }
                bounded_i32_domain_for_matrix_literal_monotonic(e, |x, y| {
                    Some(if x > y { x } else { y })
                })
                .or_else(|| matrix_element_domain(e))
            }
            Expression::Pred(_, operand) | Expression::Succ(_, operand) => {
                let domain = operand.domain_of()?.resolve().ok()?;
                if !matches!(domain.as_ref(), GroundDomain::EnumeratedType(_, _)) {
                    return None;
                }
                let values = domain
                    .values()
                    .ok()?
                    .filter_map(|value| {
                        let Literal::EnumVariant(value) = value else {
                            return None;
                        };
                        let neighbour = if matches!(self, Expression::Pred(_, _)) {
                            value.pred()
                        } else {
                            value.succ()
                        };
                        neighbour.map(Literal::EnumVariant)
                    })
                    .collect::<Vec<_>>();
                if values.is_empty() {
                    Some(Domain::empty(operand.return_type()))
                } else {
                    GroundDomain::from_literal_vec(&values)
                        .ok()
                        .map(DomainPtr::from)
                }
            }
            Expression::UnsafeDiv(_, a, b) => division_domain(a, b, false),
            // Either operand's value can survive, so the domain must cover both.
            Expression::CatchUndef(_, a, b) => {
                let inner = a.domain_of()?;
                let default = b.domain_of()?;
                inner.union(&default).ok()
            }
            Expression::SafeDiv(_, a, b) => division_domain(a, b, true),
            Expression::UnsafeMod(_, a, b) => modulo_domain(a, b, false),
            Expression::SafeMod(_, a, b) => modulo_domain(a, b, true),
            Expression::SafePow(_, a, b) | Expression::UnsafePow(_, a, b) => {
                power_integer_domain(a, b)
            }
            Expression::Root(_, _) => None,
            Expression::Bubble(_, inner, _) => inner.domain_of(),
            Expression::AuxDeclaration(_, _, _) => Some(Domain::bool()),
            Expression::And(_, _) => Some(Domain::bool()),
            Expression::Not(_, _) => Some(Domain::bool()),
            Expression::Or(_, _) => Some(Domain::bool()),
            Expression::Imply(_, _, _) => Some(Domain::bool()),
            Expression::Iff(_, _, _) => Some(Domain::bool()),
            Expression::Eq(_, _, _) => Some(Domain::bool()),
            Expression::Neq(_, _, _) => Some(Domain::bool()),
            Expression::Geq(_, _, _) => Some(Domain::bool()),
            Expression::Leq(_, _, _) => Some(Domain::bool()),
            Expression::Gt(_, _, _) => Some(Domain::bool()),
            Expression::Lt(_, _, _) => Some(Domain::bool()),
            Expression::Factorial(_, a) => factorial_domain(a),
            Expression::FlatAbsEq(_, _, _) => Some(Domain::bool()),
            Expression::FlatMinEq(_, _, _) => Some(Domain::bool()),
            Expression::FlatSumGeq(_, _, _) => Some(Domain::bool()),
            Expression::FlatSumLeq(_, _, _) => Some(Domain::bool()),
            Expression::MinionDivEqUndefZero(_, _, _, _) => Some(Domain::bool()),
            Expression::MinionModuloEqUndefZero(_, _, _, _) => Some(Domain::bool()),
            Expression::FlatIneq(_, _, _, _) => Some(Domain::bool()),
            Expression::Flatten(_, n, m) => {
                if let Some(expr) = n {
                    if expr.return_type() == ReturnType::Int {
                        // TODO: handle flatten with depth argument
                        return None;
                    }
                } else {
                    // TODO: currently only works for matrices
                    let dom = m.domain_of()?.resolve().ok()?;
                    let (val_dom, idx_doms) = match dom.as_ref() {
                        GroundDomain::Matrix(val, idx, _) => (val, idx),
                        _ => return None,
                    };
                    let num_elems = matrix::num_elements(idx_doms).ok()? as i32;

                    let new_index_domain = Domain::int(vec![Range::Bounded(1, num_elems)]);
                    return Some(Domain::matrix(
                        val_dom.clone().into(),
                        vec![new_index_domain],
                    ));
                }
                None
            }
            Expression::AllDiff(_, _) => Some(Domain::bool()),
            Expression::SmtDistinct(_, _) => Some(Domain::bool()),
            Expression::AllDifferentExcept(_, _, _) => Some(Domain::bool()),
            Expression::ElementId(_, matrix, index) => {
                let lookup = Expression::UnsafeIndex(
                    Metadata::new(),
                    matrix.clone(),
                    vec![(**index).clone()],
                );
                let numeric = |domain: DomainPtr| {
                    if domain.is_bool() {
                        Some(Domain::int(vec![Range::Bounded(0, 1)]))
                    } else if domain.is_int() {
                        Some(domain)
                    } else {
                        None
                    }
                };
                if matches!(matrix.as_ref(), Expression::Atomic(_, Atom::Literal(Literal::AbstractLiteral(AbstractLiteral::Matrix(entries, _)))) if entries.is_empty())
                    || matrix
                        .unwrap_matrix_unchecked_ref()
                        .is_some_and(|(entries, _)| entries.is_empty())
                {
                    return numeric(index.domain_of()?);
                }
                numeric(lookup.domain_of()?)?
                    .union(&numeric(index.domain_of()?)?)
                    .ok()
            }
            Expression::IndexOf(_, matrix, value) => {
                let dom = matrix.domain_of()?.resolve().ok()?;
                let idx_doms = match dom.as_ref() {
                    GroundDomain::Matrix(_, idx, _) => idx,
                    _ => return None,
                };
                if let [idx_dom] = idx_doms.as_slice() {
                    let index_domain = Domain::Ground(idx_dom.clone());
                    if let Some(n) = matrix.list_len() {
                        if n > 0 {
                            return Some(Domain::int(vec![Range::Bounded(1, n as i32)]));
                        }
                        Some(Moo::new(index_domain))
                    } else {
                        let matrix_is_literal = matches!(
                            matrix.as_ref(),
                            Expression::Atomic(_, Atom::Literal(_))
                                | Expression::AbstractLiteral(_, _)
                        );
                        if !matrix_is_literal || eval_constant(value.as_ref()).is_none() {
                            value
                                .domain_of()
                                .and_then(|value_domain| index_domain.union(&value_domain).ok())
                                .map(Moo::new)
                                .or_else(|| Some(Moo::new(index_domain)))
                        } else {
                            Some(Moo::new(index_domain))
                        }
                    }
                } else {
                    let num_elems = matrix::num_elements(idx_doms).ok()? as i32;
                    Some(Domain::int(vec![Range::Bounded(1, num_elems)]))
                }
            }
            Expression::SatElement(_, _, _, _) | Expression::SatAllDifferentComparisons(_, _) => {
                Some(Domain::bool())
            }
            Expression::Table(_, _, _)
            | Expression::FlatTable(..)
            | Expression::FlatShortTable(..)
            | Expression::NegativeTable(_, _, _)
            | Expression::ShortTable(_, _, _) => Some(Domain::bool()),
            Expression::AtLeast(_, _, _, _) => Some(Domain::bool()),
            Expression::AtMost(_, _, _, _) => Some(Domain::bool()),
            Expression::Gcc(_, _, _, _) | Expression::GccWeak(_, _, _, _) => Some(Domain::bool()),
            Expression::FlatWatchedLiteral(_, _, _) => Some(Domain::bool()),
            Expression::MinionReify(_, _, _) => Some(Domain::bool()),
            Expression::MinionReifyImply(_, _, _) => Some(Domain::bool()),
            Expression::MinionWInIntervalSet(_, _, _) => Some(Domain::bool()),
            Expression::MinionWInSet(_, _, _) => Some(Domain::bool()),
            Expression::MinionElementOne(_, _, _, _) => Some(Domain::bool()),
            Expression::Neg(_, x) => {
                let dom = x.domain_of()?;
                let mut ranges = dom.as_int()?;

                ranges = ranges
                    .into_iter()
                    .map(|r| match r {
                        Range::Single(x) => Range::Single(-x),
                        Range::Bounded(x, y) => Range::Bounded(-y, -x),
                        Range::UnboundedR(i) => Range::UnboundedL(-i),
                        Range::UnboundedL(i) => Range::UnboundedR(-i),
                        Range::Unbounded => Range::Unbounded,
                    })
                    .collect();

                Some(Domain::int(ranges))
            }
            Expression::Minus(_, a, b) => {
                let a_resolved = a.domain_of()?.resolve().ok()?;
                let b_resolved = b.domain_of()?.resolve().ok()?;
                if matches!(
                    a_resolved.as_ref(),
                    GroundDomain::Int(_, _) | GroundDomain::Empty(ReturnType::Int)
                ) && matches!(
                    b_resolved.as_ref(),
                    GroundDomain::Int(_, _) | GroundDomain::Empty(ReturnType::Int)
                ) {
                    binary_integer_domain(a, b, i32::checked_sub)
                } else if matches!(a_resolved.as_ref(), GroundDomain::Set(_, _))
                    && matches!(b_resolved.as_ref(), GroundDomain::Set(_, _))
                {
                    set_operation_domain(a, b, SetOperation::Difference)
                } else {
                    None
                }
            }
            Expression::FlatAllDiff(_, _) => Some(Domain::bool()),
            Expression::FlatMinusEq(_, _, _) => Some(Domain::bool()),
            Expression::FlatProductEq(_, _, _, _) => Some(Domain::bool()),
            Expression::FlatWeightedSumLeq(_, _, _, _) => Some(Domain::bool()),
            Expression::FlatWeightedSumGeq(_, _, _, _) => Some(Domain::bool()),
            Expression::Abs(_, a) => absolute_integer_domain(a),
            Expression::MinionPow(_, _, _, _) => Some(Domain::bool()),
            Expression::ToInt(_, _) => Some(Domain::int(vec![Range::Bounded(0, 1)])),
            Expression::SatObjective(..) => Some(Domain::bool()),
            Expression::SATInt(_, _, _, (low, high)) => {
                Some(Domain::int_ground(vec![Range::Bounded(*low, *high)]))
            }
            Expression::PairwiseSum(_, a, b) => binary_integer_domain(a, b, i32::checked_add),
            Expression::PairwiseProduct(_, a, b) => binary_integer_domain(a, b, i32::checked_mul),
            Expression::Defined(_, function) => defined_domain(function),
            Expression::Range(_, function) => range_domain(function),
            Expression::Image(_, function, _) => get_function_codomain(function),
            Expression::PermInverse(_, perm) => perm.domain_of(),
            Expression::Compose(_, g, _h) => g.domain_of(),
            Expression::ImageSet(_, function, argument) => image_set_domain(function, argument)
                .or_else(|| {
                    get_function_codomain(function)
                        .map(|inner| Domain::set(SetAttr::new(Range::Bounded(0, 1)), inner))
                }),
            Expression::PreImage(_, function, image) => pre_image_domain(function, image),
            Expression::Restrict(_, function, new_domain) => {
                restricted_domain(function, new_domain)
            }
            Expression::Subsequence(_, _, _) => Some(Domain::bool()),
            Expression::Substring(_, _, _) => Some(Domain::bool()),
            Expression::AttributeAsConstraint(_, _, _, _) => Some(Domain::bool()),
            Expression::Inverse(..) => Some(Domain::bool()),
            Expression::LexLt(..) => Some(Domain::bool()),
            Expression::LexLeq(..) => Some(Domain::bool()),
            Expression::LexGt(..) => Some(Domain::bool()),
            Expression::LexGeq(..) => Some(Domain::bool()),
            Expression::FlatLexLt(..) => Some(Domain::bool()),
            Expression::FlatLexLeq(..) => Some(Domain::bool()),
            Expression::Active(..) => Some(Domain::bool()),
            Expression::ToSet(_, other) => {
                if let Some((attrs, dom, codom)) = other.domain_of()?.as_function() {
                    Some(bounded_set(
                        function_size(&attrs, &dom, &codom),
                        Domain::tuple(vec![dom, codom]),
                    ))
                } else if let Some((_, doms)) = other.domain_of()?.as_relation() {
                    let size = collection_size(&other.domain_of()?)?;
                    Some(bounded_set(size, Domain::tuple(doms)))
                } else if let Some((attrs, dom)) = other.domain_of()?.as_mset() {
                    let size = mset_size(&attrs, &dom);
                    let occurrence = SizeBounds::from_size(&attrs.occurrence);
                    if size.range().is_none() || occurrence.range().is_none() {
                        return Some(Domain::empty(ReturnType::Set(Box::new(dom.return_type()))));
                    }
                    Some(bounded_set(distinct_size(size, occurrence), dom))
                } else if let Some((dom, dimensions)) = other.domain_of()?.as_matrix() {
                    // toSet consumes a list; higher-rank matrices need explicit flattening.
                    if dimensions.len() != 1 {
                        return None;
                    }
                    let size = collection_size(&other.domain_of()?)?;
                    Some(bounded_set(
                        distinct_size(size, SizeBounds::new(1, None)),
                        dom,
                    ))
                } else {
                    bug!(
                        "Domain of {self} needed to be a function, relation, mset, or matrix for ToSet"
                    )
                }
            }
            Expression::ToMSet(_, other) => {
                if let Some((attrs, dom, codom)) = other.domain_of()?.as_function() {
                    let set_attrs = MSetAttr {
                        size: function_size(&attrs, &dom, &codom).range()?.into(),
                        occurrence: Range::Single(IntVal::Const(1)),
                        representation: None,
                    };
                    Some(Domain::mset(set_attrs, Domain::tuple(vec![dom, codom])))
                } else if let Some((attrs, doms)) = other.domain_of()?.as_relation() {
                    let set_attrs = MSetAttr {
                        size: attrs.size,
                        occurrence: Range::Single(IntVal::Const(1)),
                        representation: None,
                    };
                    Some(Domain::mset(set_attrs, Domain::tuple(doms)))
                } else if let Some((attrs, dom)) = other.domain_of()?.as_set() {
                    let set_attrs = MSetAttr {
                        size: attrs.size,
                        occurrence: Range::Single(IntVal::Const(1)),
                        representation: None,
                    };
                    Some(Domain::mset(set_attrs, dom))
                } else {
                    bug!("Domain of {self} needed to be a function, relation, or set for ToMSet")
                }
            }
            Expression::ToRelation(_, function) => {
                let (attrs, domain, codomain) = function.domain_of()?.as_function()?;
                // Function attributes apply to the relation
                let rel_attrs = RelAttr {
                    size: function_size(&attrs, &domain, &codomain).range()?,
                    binary: vec![],
                    // The function's layout does not say how its relation view is laid out.
                    representation: None,
                };
                Some(Domain::relation(rel_attrs, vec![domain, codomain]))
            }
            Expression::RelationProj(_, relation, projections) => {
                let (_, domains) = relation.domain_of()?.as_relation()?;
                let new_doms = domains
                    .iter()
                    .zip(projections.iter())
                    .filter_map(|(domain, included)| {
                        if included.is_none() {
                            // The domains corresponding to projections which are None remain in the relation
                            Some(domain.clone())
                        } else {
                            None
                        }
                    })
                    .collect();
                Some(Domain::relation(RelAttr::<IntVal>::default(), new_doms))
            }
            Expression::Apart(_, _, _) => Some(Domain::bool()),
            Expression::Together(_, _, _) => Some(Domain::bool()),
            Expression::Participants(_, p) => {
                // Every single element of the domain _must_ be in the set, so fixed size on that.
                let (attr, inner) = p.domain_of()?.as_partition()?;
                let len = inner.length_signed().ok()?;

                let p_parts = attr.resolve().ok()?.num_parts;
                let p_card = attr.resolve().ok()?.part_len;

                // if
                match (p_parts.low(), p_parts.high(), p_card.low(), p_card.high()) {
                    (Some(p), Some(q), Some(r), Some(s)) => {
                        let lo = p * r;
                        let hi = q * s;
                        if len < lo || len > hi {
                            return Some(Domain::empty(ReturnType::Set(Box::new(
                                inner.return_type(),
                            ))));
                        }
                    }

                    (None, Some(q), None, Some(s)) => {
                        let hi = q * s;
                        if len > hi {
                            return Some(Domain::empty(ReturnType::Set(Box::new(
                                inner.return_type(),
                            ))));
                        }
                    }

                    (Some(p), None, Some(r), None) => {
                        let lo = p * r;
                        if len < lo {
                            return Some(Domain::empty(ReturnType::Set(Box::new(
                                inner.return_type(),
                            ))));
                        }
                    }

                    _ => {}
                }

                Some(Domain::set(
                    SetAttr::new_size(len),
                    Domain::int(inner.as_int()?),
                ))
            }
            Expression::Party(_, _, p) => {
                // Will pick a part, so set will share same attrs
                let (attr, inner) = p.domain_of()?.as_partition()?;

                Some(Domain::set(SetAttr::new(attr.part_len), inner))
            }
            Expression::Parts(_, p) => {
                let (attr, inner) = p.domain_of()?.as_partition()?;

                Some(Domain::set(
                    SetAttr::new(attr.num_parts.clone()),
                    Domain::set(SetAttr::new(attr.part_len), inner),
                ))
            }
            Expression::Card(_, collection) => {
                let domain = collection.domain_of()?;
                if matches!(domain.as_ground(), Some(GroundDomain::Empty(_))) {
                    Some(Domain::empty(ReturnType::Int))
                } else if let Some(bounds) = collection_size(&domain) {
                    Some(match bounds.range() {
                        Some(size) => Domain::int(vec![size]),
                        None => Domain::empty(ReturnType::Int),
                    })
                } else if let Some((attrs, dom, codom)) = domain.as_function() {
                    Some(match function_size(&attrs, &dom, &codom).range() {
                        Some(size) => Domain::int(vec![size]),
                        None => Domain::empty(ReturnType::Int),
                    })
                } else if let Some((_attrs, inner)) = domain.as_partition() {
                    // A partition always covers its whole "from" domain exactly (parts are
                    // disjoint and total), so |p| (== |participants(p)|, per the `partition-card`
                    // horizontal rule) is always exactly the inner domain's size, regardless of
                    // numParts/partSize attributes.
                    match inner.length_signed() {
                        Ok(length) => Some(Domain::int(vec![Range::Single(length)])),
                        Err(_) => None,
                    }
                } else {
                    bug!(
                        "Domain of {self} needed to be a matrix, set, mset, sequence, relation, function, or partition for cardinality"
                    )
                }
            }
        }
    }

    /// Returns a reference to this expression's metadata without cloning.
    pub fn meta_ref(&self) -> &Metadata {
        macro_rules! match_meta_ref {
            ($($variant:ident),* $(,)?) => {
                match self {
                    $(Expression::$variant(meta, ..) => meta,)*
                }
            };
        }
        match_meta_ref!(
            AbstractLiteral,
            Root,
            Bubble,
            Comprehension,
            DominanceRelation,
            TypeAnnotation,
            DomainAnnotation,
            FromSolution,
            Metavar,
            Atomic,
            RecordField,
            UnsafeIndex,
            SafeIndex,
            SatElement,
            SatAllDifferentComparisons,
            UnsafeSlice,
            SafeSlice,
            InDomain,
            ToInt,
            Abs,
            Sum,
            Product,
            Min,
            Max,
            Not,
            Or,
            And,
            Imply,
            Iff,
            Union,
            Difference,
            In,
            Intersect,
            Supset,
            SupsetEq,
            Subset,
            SubsetEq,
            Eq,
            Neq,
            Geq,
            Leq,
            Gt,
            Lt,
            CatchUndef,
            SafeDiv,
            UnsafeDiv,
            SafeMod,
            UnsafeMod,
            Apart,
            Together,
            Participants,
            Party,
            Parts,
            Neg,
            Defined,
            Range,
            UnsafePow,
            SafePow,
            Flatten,
            AttributeAsConstraint,
            AllDiff,
            SmtDistinct,
            AllDifferentExcept,
            ElementId,
            IndexOf,
            Minus,
            Factorial,
            FlatAbsEq,
            FlatAllDiff,
            FlatTable,
            FlatShortTable,
            FlatMinEq,
            FlatSumGeq,
            FlatSumLeq,
            FlatIneq,
            FlatWatchedLiteral,
            FlatWeightedSumLeq,
            FlatWeightedSumGeq,
            FlatMinusEq,
            FlatProductEq,
            MinionDivEqUndefZero,
            MinionModuloEqUndefZero,
            MinionPow,
            MinionReify,
            MinionReifyImply,
            MinionWInIntervalSet,
            MinionWInSet,
            MinionElementOne,
            AuxDeclaration,
            SATInt,
            SatObjective,
            PairwiseSum,
            PairwiseProduct,
            Image,
            ImageSet,
            PreImage,
            Inverse,
            PermInverse,
            Compose,
            Restrict,
            LexLt,
            LexLeq,
            LexGt,
            LexGeq,
            FlatLexLt,
            FlatLexLeq,
            NegativeTable,
            ShortTable,
            Table,
            AtLeast,
            AtMost,
            Gcc,
            GccWeak,
            Active,
            ToSet,
            ToMSet,
            ToRelation,
            RelationProj,
            Pred,
            Succ,
            Card,
            Subsequence,
            Substring,
        )
    }

    pub fn get_meta(&self) -> Metadata {
        let metas: VecDeque<Metadata> = self.children_bi();
        metas[0].clone()
    }

    pub fn set_meta(&self, meta: Metadata) {
        self.transform_bi(&|_| meta.clone());
    }

    /// Checks whether this expression is safe.
    ///
    /// An expression is unsafe if can be undefined, or if any of its children can be undefined.
    ///
    /// Unsafe expressions are (typically) prefixed with Unsafe in our AST, and can be made
    /// safe through the use of bubble rules.
    pub fn is_safe(&self) -> bool {
        // TODO: memoise in Metadata
        !self.any_expression(|expr| {
            matches!(
                expr,
                Expression::UnsafeDiv(_, _, _)
                    | Expression::UnsafeMod(_, _, _)
                    | Expression::UnsafePow(_, _, _)
                    | Expression::UnsafeIndex(_, _, _)
                    | Expression::Bubble(_, _, _)
                    | Expression::UnsafeSlice(_, _, _)
                    | Expression::Pred(_, _)
                    | Expression::Succ(_, _)
            ) || matches!(expr, Expression::Image(_, subject, argument)
                if image_can_be_undefined(subject, argument))
        })
    }

    /// True if the expression is an associative and commutative operator
    pub fn is_associative_commutative_operator(&self) -> bool {
        TryInto::<ACOperatorKind>::try_into(self).is_ok()
    }

    /// True if the expression is a matrix literal.
    ///
    /// This is true for both forms of matrix literals: those with elements of type [`Literal`] and
    /// [`Expression`].
    pub fn is_matrix_literal(&self) -> bool {
        matches!(
            self,
            Expression::AbstractLiteral(_, AbstractLiteral::Matrix(_, _))
                | Expression::Atomic(
                    _,
                    Atom::Literal(Literal::AbstractLiteral(AbstractLiteral::Matrix(_, _))),
                )
        )
    }

    /// True iff self and other are both atomic and identical.
    ///
    /// This method is useful to cheaply check equivalence. Assuming CSE is enabled, any unifiable
    /// expressions will be rewritten to a common variable. This is much cheaper than checking the
    /// entire subtrees of `self` and `other`.
    pub fn identical_atom_to(&self, other: &Expression) -> bool {
        let atom1: Result<&Atom, _> = self.try_into();
        let atom2: Result<&Atom, _> = other.try_into();

        if let (Ok(atom1), Ok(atom2)) = (atom1, atom2) {
            atom2 == atom1
        } else {
            false
        }
    }

    /// If the expression is a list, borrows the inner expressions.
    ///
    /// Prefer this over [`Expression::unwrap_list`] when the elements are only inspected: copying
    /// them costs the whole list, which matters on wide matrices that rules test on every visit.
    ///
    /// Unlike [`Expression::unwrap_list`], a matrix held as an [`Atom::Literal`] is not unwrapped,
    /// since its elements are literals with no `Expression` to borrow.
    pub fn unwrap_list_ref(&self) -> Option<&[Expression]> {
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
                expr.unwrap_list_ref()
            }
            Expression::AbstractLiteral(_, matrix @ AbstractLiteral::Matrix(_, _)) => {
                matrix.unwrap_list().map(Vec::as_slice)
            }
            _ => None,
        }
    }

    /// If the expression is a list, borrows the inner expressions where it can.
    ///
    /// This accepts exactly the same expressions as [`Expression::unwrap_list`], but avoids the
    /// copy in the common case. Only a matrix held as an [`Atom::Literal`] allocates, because its
    /// elements are literals that have to be materialised as `Expression`s; every other list
    /// borrows.
    ///
    /// Prefer this over [`Expression::unwrap_list`] when the elements are usually only inspected,
    /// and over [`Expression::unwrap_list_ref`] when the narrower set of accepted expressions
    /// would change behaviour.
    pub fn unwrap_list_cow(&self) -> Option<Cow<'_, [Expression]>> {
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
                expr.unwrap_list_cow()
            }
            Expression::AbstractLiteral(_, matrix @ AbstractLiteral::Matrix(_, _)) => matrix
                .unwrap_list()
                .map(|elems| Cow::Borrowed(elems.as_slice())),
            Expression::Atomic(
                _,
                Atom::Literal(Literal::AbstractLiteral(matrix @ AbstractLiteral::Matrix(_, _))),
            ) => matrix.unwrap_list().map(|elems| {
                Cow::Owned(
                    elems
                        .iter()
                        .cloned()
                        .map(|literal| Expression::Atomic(Metadata::new(), Atom::Literal(literal)))
                        .collect(),
                )
            }),
            _ => None,
        }
    }

    /// Returns the number of elements when this expression is a list, without cloning them.
    ///
    /// Unlike [`Expression::unwrap_list`], this never converts literal elements into expressions.
    /// Use it for length, emptiness, and list-shape checks.
    pub fn list_len(&self) -> Option<usize> {
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
                expr.list_len()
            }
            Expression::AbstractLiteral(_, matrix @ AbstractLiteral::Matrix(_, _)) => {
                matrix.unwrap_list().map(Vec::len)
            }
            Expression::Atomic(
                _,
                Atom::Literal(Literal::AbstractLiteral(matrix @ AbstractLiteral::Matrix(_, _))),
            ) => matrix.unwrap_list().map(Vec::len),
            _ => None,
        }
    }

    /// Whether this expression is a list, without cloning or materialising its elements.
    pub fn is_list(&self) -> bool {
        self.list_len().is_some()
    }

    /// If the expression is a list, returns a *copied* vector of the inner expressions.
    ///
    /// A list is any a matrix with the domain `int(1..)`. This includes matrix literals without
    /// any explicitly specified domain.
    ///
    /// The vector is owned: a matrix stored inside [`Atom::Literal`] holds [`Literal`]s that have
    /// to be materialised as [`Expression`]s, and callers that rewrite the elements need them by
    /// value. For inspection use [`Expression::unwrap_list_cow`]; for shape checks use
    /// [`Expression::list_len`] or [`Expression::is_list`].
    pub fn unwrap_list(&self) -> Option<Vec<Expression>> {
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
                expr.unwrap_list()
            }
            Expression::AbstractLiteral(_, matrix @ AbstractLiteral::Matrix(_, _)) => {
                matrix.unwrap_list().cloned()
            }
            Expression::Atomic(
                _,
                Atom::Literal(Literal::AbstractLiteral(matrix @ AbstractLiteral::Matrix(_, _))),
            ) => matrix.unwrap_list().map(|elems| {
                elems
                    .clone()
                    .into_iter()
                    .map(|x: Literal| Expression::Atomic(Metadata::new(), Atom::Literal(x)))
                    .collect_vec()
            }),
            _ => None,
        }
    }

    /// If the expression is a list, consumes it and returns its elements.
    ///
    /// Prefer this over [`Expression::unwrap_list`] when the expression is already owned: it moves
    /// expression elements out of the matrix rather than cloning the complete list.
    pub fn into_list(self) -> Option<Vec<Expression>> {
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
                Moo::unwrap_or_clone(expr).into_list()
            }
            Expression::AbstractLiteral(_, matrix @ AbstractLiteral::Matrix(_, _)) => {
                matrix.into_list()
            }
            Expression::Atomic(
                _,
                Atom::Literal(Literal::AbstractLiteral(matrix @ AbstractLiteral::Matrix(_, _))),
            ) => matrix.into_list().map(|elems| {
                elems
                    .into_iter()
                    .map(|literal| Expression::Atomic(Metadata::new(), Atom::Literal(literal)))
                    .collect()
            }),
            _ => None,
        }
    }

    /// If the expression is an expression-valued matrix, borrows its elements and index domain.
    ///
    /// As with [`Expression::unwrap_matrix_unchecked`], callers must preserve the relationship
    /// between the domain and element count. Literal-valued matrices are excluded because their
    /// elements cannot be borrowed as [`Expression`]s.
    pub fn unwrap_matrix_unchecked_ref(&self) -> Option<(&[Expression], &DomainPtr)> {
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
                expr.unwrap_matrix_unchecked_ref()
            }
            Expression::AbstractLiteral(_, AbstractLiteral::Matrix(elems, domain)) => {
                Some((elems, domain))
            }
            _ => None,
        }
    }

    /// If the expression is a matrix, gets it elements and index domain.
    ///
    /// **Consider using the safer [`Expression::unwrap_list`] instead.**
    ///
    /// It is generally undefined to edit the length of a matrix unless it is a list (as defined by
    /// [`Expression::unwrap_list`]). Users of this function should ensure that, if the matrix is
    /// reconstructed, the index domain and the number of elements in the matrix remain the same.
    pub fn unwrap_matrix_unchecked(self) -> Option<(Vec<Expression>, DomainPtr)> {
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
                Moo::unwrap_or_clone(expr).unwrap_matrix_unchecked()
            }
            Expression::AbstractLiteral(_, AbstractLiteral::Matrix(elems, domain)) => {
                Some((elems, domain))
            }
            Expression::Atomic(
                _,
                Atom::Literal(Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, domain))),
            ) => Some((
                elems
                    .into_iter()
                    .map(|x: Literal| Expression::Atomic(Metadata::new(), Atom::Literal(x)))
                    .collect_vec(),
                domain.into(),
            )),

            _ => None,
        }
    }

    /// For a Root expression, extends the inner vec with the given vec.
    ///
    /// # Panics
    /// Panics if the expression is not Root.
    pub fn extend_root(self, exprs: Vec<Expression>) -> Expression {
        match self {
            Expression::Root(meta, mut children) => {
                children.extend(exprs);
                Expression::Root(meta, children)
            }
            _ => panic!("extend_root called on a non-Root expression"),
        }
    }

    /// Converts the expression to a literal, if possible.
    pub fn into_literal(self) -> Option<Literal> {
        match self {
            Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),
            Expression::AbstractLiteral(_, abslit) => {
                Some(Literal::AbstractLiteral(abslit.into_literals()?))
            }
            Expression::Neg(_, e) => {
                let Literal::Int(i) = Moo::unwrap_or_clone(e).into_literal()? else {
                    bug!("negated literal should be an int");
                };

                Some(Literal::Int(-i))
            }

            _ => None,
        }
    }

    /// If this expression is an associative-commutative operator, return its [ACOperatorKind].
    pub fn to_ac_operator_kind(&self) -> Option<ACOperatorKind> {
        TryFrom::try_from(self).ok()
    }

    /// [`Typeable::return_type`], where the type can be worked out.
    ///
    /// `return_type` panics for a reference whose declaration has no domain yet -- a value letting
    /// whose body is not yet a constant, say. Parsers cannot rule those out while building the
    /// model, so they ask this instead and read `None` as "unknown".
    pub fn try_return_type(&self) -> Option<ReturnType> {
        let has_untyped_reference = self.any_expression(|expr| {
            matches!(expr, Expression::Atomic(_, Atom::Reference(reference))
                if reference.domain().is_none())
        });

        (!has_untyped_reference).then(|| self.return_type())
    }

    /// Returns the categories of all sub-expressions of self.
    pub fn universe_categories(&self) -> HashSet<Category> {
        let mut categories = HashSet::new();
        self.for_each_expression(&mut |expr| {
            categories.insert(expr.category_of());
        });
        categories
    }
}

/// True when `image(subject, argument)` can be undefined.
///
/// A function is defined only on its own domain -- `total` means defined for every value *in* that
/// domain, not defined everywhere -- so an argument that can fall outside it has no image there. A
/// partial function may also be undefined inside its domain, and a sequence is defined only on
/// `1..|s|`. When the length varies, every member of the domain still has the prefix `1..minSize`;
/// positions past that prefix are not known until solving.
///
/// Anything this cannot work out counts as undefinable. Safety has to be conservative: treating a
/// partial application as total lets its definedness be reasoned away, and the constraint it sits
/// in then silently holds where it should not.
pub fn image_can_be_undefined(subject: &Expression, argument: &Expression) -> bool {
    let Some(domain) = subject.domain_of().and_then(|domain| domain.resolve().ok()) else {
        return true;
    };

    match domain.as_ref() {
        GroundDomain::Function(attr, from, _) => {
            !matches!(attr.partiality, PartialityAttr::Total) || !argument_always_in(argument, from)
        }
        // A permutation is total on its own domain, which is also where its image lands.
        GroundDomain::Permutation(_, inner) => !argument_always_in(argument, inner),
        GroundDomain::Sequence(attr, _) => {
            // Positions `1..=min_length` exist in every member of the domain. Anything past that
            // may sit in the allocated matrix and still be undefined if `|s|` is shorter.
            let min_length = attr.size.low().copied().unwrap_or(0);
            min_length <= 0
                || !argument_always_in(
                    argument,
                    &GroundDomain::Int(vec![Range::Bounded(1, min_length)], None),
                )
        }
        _ => true,
    }
}

/// Whether every value `argument` can take lies in `domain`.
///
/// Answers false whenever that cannot be established, including for domains that are equivalent
/// but not written the same way -- callers use this to decide whether they may reason about
/// definedness, where saying "no" only costs them the chance to simplify.
fn argument_always_in(argument: &Expression, domain: &GroundDomain) -> bool {
    let Some(argument_domain) = argument.domain_of().and_then(|d| d.resolve().ok()) else {
        return false;
    };

    argument_domain
        .intersect(domain)
        .is_ok_and(|intersection| intersection == *argument_domain.as_ref())
}

impl TryFrom<&Expression> for i32 {
    type Error = ();

    fn try_from(value: &Expression) -> Result<Self, Self::Error> {
        let Expression::Atomic(_, atom) = value else {
            return Err(());
        };

        let Atom::Literal(lit) = atom else {
            return Err(());
        };

        let Literal::Int(i) = lit else {
            return Err(());
        };

        Ok(*i)
    }
}

impl TryFrom<Expression> for i32 {
    type Error = ();

    fn try_from(value: Expression) -> Result<Self, Self::Error> {
        TryFrom::<&Expression>::try_from(&value)
    }
}
impl From<i32> for Expression {
    fn from(i: i32) -> Self {
        Expression::Atomic(Metadata::new(), Atom::Literal(Literal::Int(i)))
    }
}

impl From<bool> for Expression {
    fn from(b: bool) -> Self {
        Expression::Atomic(Metadata::new(), Atom::Literal(Literal::Bool(b)))
    }
}

impl From<Atom> for Expression {
    fn from(value: Atom) -> Self {
        Expression::Atomic(Metadata::new(), value)
    }
}

impl From<Literal> for Expression {
    fn from(value: Literal) -> Self {
        Expression::Atomic(Metadata::new(), value.into())
    }
}

impl From<AbstractLiteral<Expression>> for Expression {
    fn from(value: AbstractLiteral<Expression>) -> Self {
        Expression::AbstractLiteral(Metadata::new(), value)
    }
}

impl From<Moo<Expression>> for Expression {
    fn from(val: Moo<Expression>) -> Self {
        val.as_ref().clone()
    }
}

impl CategoryOf for Expression {
    fn category_of(&self) -> Category {
        // take highest category of all the expressions children
        let category = self.cata(&move |x,children| {

            if let Some(max_category) = children.iter().max() {
                // if this expression contains subexpressions, return the maximum category of the
                // subexpressions
                *max_category
            } else {
                // this expression has no children
                let mut max_category = Category::Bottom;

                // calculate the category by looking at all atoms, submodels, comprehensions, and
                // declarationptrs inside this expression

                // this should generically cover all leaf types we currently have in oxide.

                // if x contains submodels (including comprehensions)
                if !Biplate::<Model>::universe_bi(&x).is_empty() {
                    // assume that the category is decision
                    return Category::Decision;
                }

                // if x contains atoms
                if let Some(max_atom_category) = Biplate::<Atom>::universe_bi(&x).iter().map(|x| x.category_of()).max()
                // and those atoms have a higher category than we already know about
                && max_atom_category > max_category{
                    // update category
                    max_category = max_atom_category;
                }

                // if x contains declarationPtrs
                if let Some(max_declaration_category) = Biplate::<DeclarationPtr>::universe_bi(&x).iter().map(|x| x.category_of()).max()
                // and those pointers have a higher category than we already know about
                && max_declaration_category > max_category{
                    // update category
                    max_category = max_declaration_category;
                }
                max_category

            }
        });

        if cfg!(debug_assertions) {
            trace!(
                category= %category,
                expression= %self,
                "Called Expression::category_of()"
            );
        };
        category
    }
}

impl Display for Expression {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match &self {
            Expression::Union(_, box1, box2) => {
                write!(f, "({} union {})", box1.clone(), box2.clone())
            }
            Expression::Difference(_, box1, box2) => {
                write!(f, "({} - {})", box1.clone(), box2.clone())
            }
            Expression::In(_, e1, e2) => {
                write!(f, "{e1} in {e2}")
            }
            Expression::Intersect(_, box1, box2) => {
                write!(f, "({} intersect {})", box1.clone(), box2.clone())
            }
            Expression::Supset(_, box1, box2) => {
                write!(f, "({} supset {})", box1.clone(), box2.clone())
            }
            Expression::SupsetEq(_, box1, box2) => {
                write!(f, "({} supsetEq {})", box1.clone(), box2.clone())
            }
            Expression::Subset(_, box1, box2) => {
                write!(f, "({} subset {})", box1.clone(), box2.clone())
            }
            Expression::SubsetEq(_, box1, box2) => {
                write!(f, "({} subsetEq {})", box1.clone(), box2.clone())
            }

            Expression::AbstractLiteral(_, l) => l.fmt(f),
            Expression::Comprehension(_, c) => c.fmt(f),
            Expression::UnsafeIndex(_, e1, e2) => write!(f, "{e1}{}", pretty_vec(e2)),
            Expression::RecordField(_, r, fld) => {
                write!(f, "{r}[{fld}]")
            }
            Expression::SafeIndex(_, e1, e2) => write!(f, "SafeIndex({e1},{})", pretty_vec(e2)),
            Expression::UnsafeSlice(_, e1, es) => {
                let args = es
                    .iter()
                    .map(|x| match x {
                        Some(x) => format!("{x}"),
                        None => "..".into(),
                    })
                    .join(",");

                write!(f, "{e1}[{args}]")
            }
            Expression::SafeSlice(_, e1, es) => {
                let args = es
                    .iter()
                    .map(|x| match x {
                        Some(x) => format!("{x}"),
                        None => "..".into(),
                    })
                    .join(",");

                write!(f, "SafeSlice({e1},[{args}])")
            }
            Expression::InDomain(_, e, domain) => {
                write!(f, "__inDomain({e},{domain})")
            }
            Expression::Root(_, exprs) => {
                write!(f, "{}", pretty_expressions_as_top_level(exprs))
            }
            Expression::DominanceRelation(_, expr) => write!(f, "DominanceRelation({expr})"),
            Expression::FromSolution(_, expr) => write!(f, "FromSolution({expr})"),
            Expression::Metavar(_, name) => write!(f, "&{name}"),
            Expression::Atomic(_, atom) => atom.fmt(f),
            Expression::TypeAnnotation(_, expr, domain) => {
                write!(
                    f,
                    "{}",
                    pretty_expression_type_annotation(expr, domain.as_type_string())
                )
            }
            Expression::DomainAnnotation(_, expr, domain) => {
                write!(f, "{}", pretty_expression_domain_annotation(expr, domain))
            }
            Expression::Abs(_, a) | Expression::Card(_, a) => write!(f, "|{a}|"),
            Expression::Sum(_, e) => {
                write!(f, "sum({e})")
            }
            Expression::Product(_, e) => {
                write!(f, "product({e})")
            }
            Expression::Min(_, e) => {
                write!(f, "min({e})")
            }
            Expression::Max(_, e) => {
                write!(f, "max({e})")
            }
            Expression::Not(_, expr_box) => {
                write!(f, "!({})", expr_box.clone())
            }
            Expression::Or(_, e) => {
                write!(f, "or({e})")
            }
            Expression::And(_, e) => {
                write!(f, "and({e})")
            }
            Expression::Imply(_, box1, box2) => {
                write!(f, "({box1}) -> ({box2})")
            }
            Expression::Iff(_, box1, box2) => {
                write!(f, "({box1}) <-> ({box2})")
            }
            Expression::Eq(_, box1, box2) => {
                write!(f, "{box1} = {box2}")
            }
            Expression::Neq(_, box1, box2) => {
                write!(f, "{box1} != {box2}")
            }
            Expression::Geq(_, box1, box2) => {
                write!(f, "{box1} >= {box2}")
            }
            Expression::Leq(_, box1, box2) => {
                write!(f, "{box1} <= {box2}")
            }
            Expression::Gt(_, box1, box2) => {
                write!(f, "{box1} > {box2}")
            }
            Expression::Lt(_, box1, box2) => {
                write!(f, "{box1} < {box2}")
            }
            Expression::Apart(_, list, partition) => {
                write!(f, "apart({list}, {partition})")
            }
            Expression::Together(_, list, partition) => {
                write!(f, "together({list}, {partition})")
            }
            Expression::Participants(_, partition) => {
                write!(f, "participants({partition})")
            }
            Expression::Party(_, element, partition) => {
                write!(f, "party({element}, {partition})")
            }
            Expression::Parts(_, partition) => {
                write!(f, "parts({partition})")
            }
            Expression::FlatMinEq(_, vars, result) => {
                write!(f, "FlatMinEq({}, {})", pretty_vec(vars), result.clone())
            }
            Expression::FlatSumGeq(_, box1, box2) => {
                write!(f, "SumGeq({}, {})", pretty_vec(box1), box2.clone())
            }
            Expression::FlatSumLeq(_, box1, box2) => {
                write!(f, "SumLeq({}, {})", pretty_vec(box1), box2.clone())
            }
            Expression::FlatIneq(_, box1, box2, box3) => write!(
                f,
                "Ineq({}, {}, {})",
                box1.clone(),
                box2.clone(),
                box3.clone()
            ),
            Expression::Flatten(_, n, m) => {
                if let Some(n) = n {
                    write!(f, "flatten({n}, {m})")
                } else {
                    write!(f, "flatten({m})")
                }
            }
            Expression::AttributeAsConstraint(_, target, attr, val) => {
                if let Some(val) = val {
                    write!(f, "{attr}({target}, {val})")
                } else {
                    write!(f, "{attr}({target})")
                }
            }
            Expression::AllDiff(_, e) => {
                write!(f, "allDifferent({e})")
            }
            Expression::SmtDistinct(_, e) => {
                write!(f, "smtDistinct({e})")
            }
            Expression::AllDifferentExcept(_, matrix, except) => {
                write!(f, "allDifferentExcept({matrix}, {except})")
            }
            Expression::ElementId(_, matrix, value) => {
                write!(f, "elementId({matrix}, {value})")
            }
            Expression::IndexOf(_, matrix, value) => write!(f, "indexOf({matrix}, {value})"),
            Expression::SatAllDifferentComparisons(_, conditions) => {
                write!(f, "sat-allDifferent-comparisons({conditions})")
            }
            Expression::SatElement(_, matrix, index, value) => {
                write!(f, "satElement({matrix}, {index}, {value})")
            }
            Expression::FlatShortTable(_, inputs, rows) => {
                write!(f, "FlatShortTable({}, {rows:?})", pretty_vec(inputs))
            }
            Expression::FlatTable(_, inputs, rows, negative) => {
                write!(f, "FlatTable({}, {rows:?}, {negative})", pretty_vec(inputs))
            }
            Expression::Table(_, tuple_expr, rows_expr) => {
                write!(f, "table({tuple_expr}, {rows_expr})")
            }
            Expression::ShortTable(_, tuple_expr, rows_expr) => {
                write!(f, "shortTable({tuple_expr}, {rows_expr})")
            }
            Expression::NegativeTable(_, tuple_expr, rows_expr) => {
                write!(f, "negativeTable({tuple_expr}, {rows_expr})")
            }
            Expression::AtLeast(_, vars, counts, values) => {
                write!(f, "atLeast({vars}, {counts}, {values})")
            }
            Expression::AtMost(_, vars, counts, values) => {
                write!(f, "atMost({vars}, {counts}, {values})")
            }
            Expression::Gcc(_, vars, values, counts) => {
                write!(f, "globalCardinality({vars}, {values}, {counts})")
            }
            Expression::GccWeak(_, vars, values, counts) => {
                write!(f, "gccweak({vars}, {values}, {counts})")
            }
            Expression::Bubble(_, box1, box2) => {
                write!(f, "{{{} @ {}}}", box1.clone(), box2.clone())
            }
            Expression::CatchUndef(_, box1, box2) => {
                write!(f, "catchUndef({box1}, {box2})")
            }
            Expression::SafeDiv(_, box1, box2) => {
                write!(f, "SafeDiv({}, {})", box1.clone(), box2.clone())
            }
            Expression::UnsafeDiv(_, box1, box2) => {
                write!(f, "({} / {})", box1.clone(), box2.clone())
            }
            Expression::UnsafePow(_, box1, box2) => {
                write!(f, "({} ** {})", box1.clone(), box2.clone())
            }
            Expression::SafePow(_, box1, box2) => {
                write!(f, "SafePow({}, {})", box1.clone(), box2.clone())
            }
            Expression::Subsequence(_, s, t) => {
                write!(f, "{} subsequence {}", s.clone(), t.clone())
            }
            Expression::Substring(_, s, t) => {
                write!(f, "{} substring {}", s.clone(), t.clone())
            }
            Expression::MinionDivEqUndefZero(_, box1, box2, box3) => {
                write!(
                    f,
                    "DivEq({}, {}, {})",
                    box1.clone(),
                    box2.clone(),
                    box3.clone()
                )
            }
            Expression::MinionModuloEqUndefZero(_, box1, box2, box3) => {
                write!(
                    f,
                    "ModEq({}, {}, {})",
                    box1.clone(),
                    box2.clone(),
                    box3.clone()
                )
            }
            Expression::FlatWatchedLiteral(_, x, l) => {
                write!(f, "WatchedLiteral({x},{l})")
            }
            Expression::MinionReify(_, box1, box2) => {
                write!(f, "Reify({}, {})", box1.clone(), box2.clone())
            }
            Expression::MinionReifyImply(_, box1, box2) => {
                write!(f, "ReifyImply({}, {})", box1.clone(), box2.clone())
            }
            Expression::MinionWInIntervalSet(_, atom, intervals) => {
                let intervals = intervals.iter().join(",");
                write!(f, "__minion_w_inintervalset({atom},[{intervals}])")
            }
            Expression::MinionWInSet(_, atom, values) => {
                let values = values.iter().join(",");
                write!(f, "__minion_w_inset({atom},[{values}])")
            }
            Expression::AuxDeclaration(_, reference, e) => {
                write!(f, "{} =aux {}", reference, e.clone())
            }
            Expression::UnsafeMod(_, a, b) => {
                write!(f, "{} % {}", a.clone(), b.clone())
            }
            Expression::SafeMod(_, a, b) => {
                write!(f, "SafeMod({},{})", a.clone(), b.clone())
            }
            Expression::Neg(_, a) => {
                write!(f, "-({})", a.clone())
            }
            Expression::Factorial(_, a) => {
                write!(f, "({})!", a.clone())
            }
            Expression::Minus(_, a, b) => {
                write!(f, "({} - {})", a.clone(), b.clone())
            }
            Expression::FlatAllDiff(_, es) => {
                write!(f, "__flat_alldiff({})", pretty_vec(es))
            }
            Expression::FlatAbsEq(_, a, b) => {
                write!(f, "AbsEq({},{})", a.clone(), b.clone())
            }
            Expression::FlatMinusEq(_, a, b) => {
                write!(f, "MinusEq({},{})", a.clone(), b.clone())
            }
            Expression::FlatProductEq(_, a, b, c) => {
                write!(
                    f,
                    "FlatProductEq({},{},{})",
                    a.clone(),
                    b.clone(),
                    c.clone()
                )
            }
            Expression::FlatWeightedSumLeq(_, cs, vs, total) => {
                write!(
                    f,
                    "FlatWeightedSumLeq({},{},{})",
                    pretty_vec(cs),
                    pretty_vec(vs),
                    total.clone()
                )
            }
            Expression::FlatWeightedSumGeq(_, cs, vs, total) => {
                write!(
                    f,
                    "FlatWeightedSumGeq({},{},{})",
                    pretty_vec(cs),
                    pretty_vec(vs),
                    total.clone()
                )
            }
            Expression::MinionPow(_, atom, atom1, atom2) => {
                write!(f, "MinionPow({atom},{atom1},{atom2})")
            }
            Expression::MinionElementOne(_, atoms, atom, atom1) => {
                let atoms = atoms.iter().join(",");
                write!(f, "__minion_element_one([{atoms}],{atom},{atom1})")
            }

            Expression::ToInt(_, expr) => {
                write!(f, "toInt({expr})")
            }

            Expression::SatObjective(_, minimise, value) => {
                write!(f, "optimise(minimise={minimise}, value={value})")
            }
            Expression::SATInt(_, encoding, bits, (min, max)) => {
                write!(f, "SATInt({encoding:?}, {bits} [{min}, {max}])")
            }

            Expression::PairwiseSum(_, a, b) => write!(f, "PairwiseSum({a}, {b})"),
            Expression::PairwiseProduct(_, a, b) => write!(f, "PairwiseProduct({a}, {b})"),

            Expression::Defined(_, function) => write!(f, "defined({function})"),
            Expression::Range(_, function) => write!(f, "range({function})"),
            Expression::Image(_, function, elems) => write!(f, "image({function},{elems})"),
            Expression::ImageSet(_, function, elems) => write!(f, "imageSet({function},{elems})"),
            Expression::PreImage(_, function, elems) => write!(f, "preImage({function},{elems})"),
            Expression::Inverse(_, a, b) => write!(f, "inverse({a},{b})"),
            Expression::PermInverse(_, p) => write!(f, "permInverse({p})"),
            Expression::Compose(_, g, h) => write!(f, "compose({g},{h})"),
            Expression::Restrict(_, function, domain) => write!(f, "restrict({function},{domain})"),

            Expression::LexLt(_, a, b) => write!(f, "({a} <lex {b})"),
            Expression::LexLeq(_, a, b) => write!(f, "({a} <=lex {b})"),
            Expression::LexGt(_, a, b) => write!(f, "({a} >lex {b})"),
            Expression::LexGeq(_, a, b) => write!(f, "({a} >=lex {b})"),
            Expression::FlatLexLt(_, a, b) => {
                write!(f, "FlatLexLt({}, {})", pretty_vec(a), pretty_vec(b))
            }
            Expression::FlatLexLeq(_, a, b) => {
                write!(f, "FlatLexLeq({}, {})", pretty_vec(a), pretty_vec(b))
            }
            Expression::Active(_, variant, field_name) => {
                write!(f, "active({variant}, {field_name})")
            }
            Expression::ToSet(_, other) => write!(f, "toSet({other})"),
            Expression::ToMSet(_, other) => write!(f, "toMSet({other})"),
            Expression::ToRelation(_, function) => write!(f, "toRelation({function})"),
            Expression::RelationProj(_, relation, projections) => {
                let projections_str = projections
                    .iter()
                    .map(|x| {
                        if let Some(x) = x {
                            x.to_string()
                        } else {
                            String::from("_")
                        }
                    })
                    .join(", ");
                write!(f, "{relation}({projections_str})")
            }
            Expression::Pred(_, ev) => write!(f, "Pred({})", ev),
            Expression::Succ(_, ev) => write!(f, "Succ({})", ev),
        }
    }
}

fn minus_operand_return_type(expr: &Expression) -> ReturnType {
    match expr {
        Expression::Atomic(_, Atom::Reference(reference)) => {
            let decl_kind = reference.ptr.kind().clone();
            match decl_kind {
                DeclarationKind::Find(var) | DeclarationKind::FindAuxiliary(var) => {
                    var.return_type()
                }
                DeclarationKind::EnumeratedType(ty) => ReturnType::EnumeratedType(ty),
                DeclarationKind::UnnamedType(_) => reference.ptr.return_type(),
                DeclarationKind::Given(domain)
                | DeclarationKind::DomainLetting(domain) => domain.return_type(),
                DeclarationKind::Quantified(inner) => inner.domain().return_type(),
                DeclarationKind::QuantifiedExpr(inner)
                | DeclarationKind::TemporaryValueLetting(inner)
                // not sure if i should ever be looking at the domain ptr but seems to work
                | DeclarationKind::ValueLetting(inner, _) => inner.return_type(),
            }
        }
        _ => expr.return_type(),
    }
}

impl Typeable for Expression {
    fn return_type(&self) -> ReturnType {
        match self {
            Expression::Union(_, subject, _)
            | Expression::Intersect(_, subject, _)
            | Expression::Difference(_, subject, _) => subject.return_type(),
            Expression::In(_, _, _) => ReturnType::Bool,
            Expression::Supset(_, _, _) => ReturnType::Bool,
            Expression::SupsetEq(_, _, _) => ReturnType::Bool,
            Expression::Subset(_, _, _) => ReturnType::Bool,
            Expression::SubsetEq(_, _, _) => ReturnType::Bool,
            Expression::AbstractLiteral(_, lit) => lit.return_type(),
            Expression::RecordField(_, rec, field_name) => {
                if let ReturnType::Record(ents) = rec.return_type() {
                    for Field { name, value } in ents {
                        if name.eq(field_name) {
                            return value;
                        }
                    }
                }
                ReturnType::Unknown
            }
            Expression::UnsafeIndex(_, subject, idx) | Expression::SafeIndex(_, subject, idx) => {
                let mut indexed_ty = subject.return_type();
                for index in idx {
                    indexed_ty = match indexed_ty {
                        ReturnType::Tuple(field_types) => {
                            let Expression::Atomic(_, Atom::Literal(Literal::Int(index))) = index
                            else {
                                return ReturnType::Unknown;
                            };
                            let Some(zero_based_index) = index
                                .checked_sub(1)
                                .and_then(|index| usize::try_from(index).ok())
                            else {
                                return ReturnType::Unknown;
                            };
                            field_types
                                .get(zero_based_index)
                                .cloned()
                                .unwrap_or(ReturnType::Unknown)
                        }
                        // Declared matrix types are flat, whereas matrix literals can have one
                        // nested Matrix return type per dimension. Continue through nested
                        // matrices, but stop once the declared element type is reached.
                        ReturnType::Matrix(element_type) => {
                            let element_type = *element_type;
                            if !matches!(element_type, ReturnType::Matrix(_)) {
                                return element_type;
                            }
                            element_type
                        }
                        // Record and variant indices need their field-name context to determine a
                        // result type. Unknown can likewise be resolved by later typechecking.
                        ReturnType::Record(_) | ReturnType::Variant(_) | ReturnType::Unknown => {
                            return ReturnType::Unknown;
                        }
                        subject_ty => bug!(
                            "Invalid indexing operation: expected the operand to be a collection, got {self}: {subject_ty}"
                        ),
                    };
                }
                indexed_ty
            }
            Expression::UnsafeSlice(_, subject, _) | Expression::SafeSlice(_, subject, _) => {
                let mut element_type = subject.return_type();
                while let ReturnType::Matrix(inner) = element_type {
                    element_type = *inner;
                }
                ReturnType::Matrix(Box::new(element_type))
            }
            Expression::InDomain(_, _, _) => ReturnType::Bool,
            Expression::Comprehension(_, comp) => comp.return_type(),
            Expression::Root(_, _) => ReturnType::Bool,
            Expression::DominanceRelation(_, _) => ReturnType::Bool,
            Expression::FromSolution(_, expr) => expr.return_type(),
            Expression::Metavar(_, _) => ReturnType::Unknown,
            Expression::Atomic(_, atom) => atom.return_type(),
            Expression::TypeAnnotation(_, _, domain) => domain.return_type(),
            Expression::DomainAnnotation(_, _, domain) => domain.return_type(),
            Expression::Abs(_, _) => ReturnType::Int,
            Expression::Sum(_, _) => ReturnType::Int,
            Expression::Product(_, _) => ReturnType::Int,
            Expression::Min(_, _) => ReturnType::Int,
            Expression::Max(_, _) => ReturnType::Int,
            Expression::Not(_, _) => ReturnType::Bool,
            Expression::Or(_, _) => ReturnType::Bool,
            Expression::Imply(_, _, _) => ReturnType::Bool,
            Expression::Iff(_, _, _) => ReturnType::Bool,
            Expression::And(_, _) => ReturnType::Bool,
            Expression::Eq(_, _, _) => ReturnType::Bool,
            Expression::Neq(_, _, _) => ReturnType::Bool,
            Expression::Geq(_, _, _) => ReturnType::Bool,
            Expression::Leq(_, _, _) => ReturnType::Bool,
            Expression::Gt(_, _, _) => ReturnType::Bool,
            Expression::Lt(_, _, _) => ReturnType::Bool,
            Expression::Apart(_, _, _) => ReturnType::Bool,
            Expression::Together(_, _, _) => ReturnType::Bool,
            Expression::Party(_, _, subject) => ReturnType::Set(Box::new(subject.return_type())),
            Expression::Participants(_, subject) => {
                ReturnType::Set(Box::new(subject.return_type()))
            }
            Expression::Parts(_, subject) => {
                ReturnType::Set(Box::new(ReturnType::Set(Box::new(subject.return_type()))))
            }
            Expression::CatchUndef(_, value, _) => value.return_type(),
            Expression::SafeDiv(_, _, _) => ReturnType::Int,
            Expression::UnsafeDiv(_, _, _) => ReturnType::Int,
            Expression::FlatAllDiff(_, _) => ReturnType::Bool,
            Expression::FlatMinEq(_, _, _) => ReturnType::Bool,
            Expression::FlatSumGeq(_, _, _) => ReturnType::Bool,
            Expression::FlatSumLeq(_, _, _) => ReturnType::Bool,
            Expression::MinionDivEqUndefZero(_, _, _, _) => ReturnType::Bool,
            Expression::FlatIneq(_, _, _, _) => ReturnType::Bool,
            Expression::Flatten(_, _, matrix) => {
                let matrix_type = matrix.return_type();
                match matrix_type {
                    ReturnType::Matrix(_) => {
                        // unwrap until we get to innermost element
                        let mut elem_type = matrix_type;
                        while let ReturnType::Matrix(new_elem_type) = &elem_type {
                            elem_type = *new_elem_type.clone();
                        }
                        ReturnType::Matrix(Box::new(elem_type))
                    }
                    _ => bug!(
                        "Invalid indexing operation: expected the operand to be a collection, got {self}: {matrix_type}"
                    ),
                }
            }
            Expression::AllDiff(_, _) => ReturnType::Bool,
            Expression::SmtDistinct(_, _) => ReturnType::Bool,
            Expression::AllDifferentExcept(_, _, _) => ReturnType::Bool,
            Expression::ElementId(_, _, _) | Expression::IndexOf(_, _, _) => ReturnType::Int,
            Expression::SatElement(_, _, _, _) | Expression::SatAllDifferentComparisons(_, _) => {
                ReturnType::Bool
            }
            Expression::Table(_, _, _)
            | Expression::FlatTable(..)
            | Expression::FlatShortTable(..) => ReturnType::Bool,
            Expression::NegativeTable(_, _, _) | Expression::ShortTable(_, _, _) => {
                ReturnType::Bool
            }
            Expression::AtLeast(_, _, _, _) => ReturnType::Bool,
            Expression::AtMost(_, _, _, _) => ReturnType::Bool,
            Expression::Gcc(_, _, _, _) | Expression::GccWeak(_, _, _, _) => ReturnType::Bool,
            Expression::Bubble(_, inner, _) => inner.return_type(),
            Expression::FlatWatchedLiteral(_, _, _) => ReturnType::Bool,
            Expression::MinionReify(_, _, _) => ReturnType::Bool,
            Expression::MinionReifyImply(_, _, _) => ReturnType::Bool,
            Expression::MinionWInIntervalSet(_, _, _) => ReturnType::Bool,
            Expression::MinionWInSet(_, _, _) => ReturnType::Bool,
            Expression::MinionElementOne(_, _, _, _) => ReturnType::Bool,
            Expression::AuxDeclaration(_, _, _) => ReturnType::Bool,
            Expression::UnsafeMod(_, _, _) => ReturnType::Int,
            Expression::SafeMod(_, _, _) => ReturnType::Int,
            Expression::MinionModuloEqUndefZero(_, _, _, _) => ReturnType::Bool,
            Expression::Neg(_, _) => ReturnType::Int,
            Expression::Factorial(_, _) => ReturnType::Int,
            Expression::UnsafePow(_, _, _) => ReturnType::Int,
            Expression::SafePow(_, _, _) => ReturnType::Int,
            Expression::Minus(_, a, b) => {
                // rather than calling .return_type on a and b which sometimes errors on references that don't have domains
                // use custom function that extracts return type from atomic references based on each declaration variant
                let a_type = minus_operand_return_type(a);
                let b_type = minus_operand_return_type(b);

                if a_type == ReturnType::Int && b_type == ReturnType::Int {
                    ReturnType::Int
                } else if let ReturnType::Set(a_inner) = a_type
                    && let ReturnType::Set(b_inner) = b_type
                    && a_inner == b_inner
                {
                    ReturnType::Set(a_inner)
                } else {
                    bug!(
                        "Invalid minus operation: operands are of different or invalid types for this operation"
                    )
                }
            }
            Expression::FlatAbsEq(_, _, _) => ReturnType::Bool,
            Expression::FlatMinusEq(_, _, _) => ReturnType::Bool,
            Expression::FlatProductEq(_, _, _, _) => ReturnType::Bool,
            Expression::FlatWeightedSumLeq(_, _, _, _) => ReturnType::Bool,
            Expression::FlatWeightedSumGeq(_, _, _, _) => ReturnType::Bool,
            Expression::MinionPow(_, _, _, _) => ReturnType::Bool,
            Expression::ToInt(_, _) => ReturnType::Int,
            Expression::SATInt(..) => ReturnType::Int,
            Expression::SatObjective(..) => ReturnType::Bool,
            Expression::PairwiseSum(_, _, _) => ReturnType::Int,
            Expression::PairwiseProduct(_, _, _) => ReturnType::Int,
            Expression::Defined(_, function) => {
                let subject = function.return_type();
                match subject {
                    ReturnType::Function(domain, _) => ReturnType::Set(Box::new(*domain)),
                    _ => bug!(
                        "Invalid defined operation: expected the operand to be a function, got {self}: {subject}"
                    ),
                }
            }
            Expression::Range(_, function) => {
                let subject = function.return_type();
                match subject {
                    ReturnType::Function(_, codomain) => ReturnType::Set(Box::new(*codomain)),
                    _ => bug!(
                        "Invalid range operation: expected the operand to be a function, got {self}: {subject}"
                    ),
                }
            }
            Expression::Image(_, function, _) => {
                let subject = function.return_type();
                match subject {
                    ReturnType::Function(_, codomain) => *codomain,
                    ReturnType::Permutation(inner) => *inner,
                    // A sequence is a function from int, so applying it is an image too.
                    ReturnType::Sequence(inner) => *inner,
                    _ => bug!(
                        "Invalid image operation: expected the operand to be a function or permutation, got {self}: {subject}"
                    ),
                }
            }
            Expression::ImageSet(_, function, _) => {
                let subject = function.return_type();
                match subject {
                    ReturnType::Function(_, codomain) => ReturnType::Set(Box::new(*codomain)),
                    ReturnType::Permutation(inner) => ReturnType::Set(inner),
                    _ => bug!(
                        "Invalid imageSet operation: expected the operand to be a function or permutation, got {self}: {subject}"
                    ),
                }
            }
            Expression::PreImage(_, function, _) => {
                let subject = function.return_type();
                match subject {
                    ReturnType::Function(domain, _) => ReturnType::Set(Box::new(*domain)),
                    _ => bug!(
                        "Invalid preImage operation: expected the operand to be a function, got {self}: {subject}"
                    ),
                }
            }
            Expression::Restrict(_, function, new_domain) => {
                let subject = function.return_type();
                match subject {
                    ReturnType::Function(_, codomain) => {
                        ReturnType::Function(Box::new(new_domain.return_type()), codomain)
                    }
                    _ => bug!(
                        "Invalid preImage operation: expected the operand to be a function, got {self}: {subject}"
                    ),
                }
            }
            Expression::Inverse(..) => ReturnType::Bool,
            Expression::PermInverse(_, p) => p.return_type(),
            Expression::Compose(_, g, _h) => g.return_type(),
            Expression::LexLt(..) => ReturnType::Bool,
            Expression::LexGt(..) => ReturnType::Bool,
            Expression::LexLeq(..) => ReturnType::Bool,
            Expression::LexGeq(..) => ReturnType::Bool,
            Expression::FlatLexLt(..) => ReturnType::Bool,
            Expression::FlatLexLeq(..) => ReturnType::Bool,
            Expression::Active(..) => ReturnType::Bool,
            Expression::ToSet(_, other) => {
                let subject = other.return_type();
                match subject {
                    ReturnType::Matrix(domain) => ReturnType::Set(Box::new(*domain)),
                    ReturnType::MSet(domain) => ReturnType::Set(Box::new(*domain)),
                    ReturnType::Function(domain, codomain) => {
                        ReturnType::Set(Box::new(ReturnType::Tuple(vec![*domain, *codomain])))
                    }
                    ReturnType::Relation(domains) => {
                        ReturnType::Set(Box::new(ReturnType::Tuple(domains)))
                    }
                    _ => bug!(
                        "Invalid toSet operation: expected the operand to be a mset, matrix, relation, or function, got {self}: {subject}"
                    ),
                }
            }
            Expression::ToMSet(_, other) => {
                let subject = other.return_type();
                match subject {
                    ReturnType::Set(domain) => ReturnType::MSet(Box::new(*domain)),
                    ReturnType::Function(domain, codomain) => {
                        ReturnType::MSet(Box::new(ReturnType::Tuple(vec![*domain, *codomain])))
                    }
                    ReturnType::Relation(domains) => {
                        ReturnType::MSet(Box::new(ReturnType::Tuple(domains)))
                    }
                    _ => bug!(
                        "Invalid toMSet operation: expected the operand to be a set, relation, or function, got {self}: {subject}"
                    ),
                }
            }
            Expression::ToRelation(_, function) => {
                let subject = function.return_type();
                match subject {
                    ReturnType::Function(domain, codomain) => {
                        ReturnType::Relation(vec![*domain, *codomain])
                    }
                    _ => bug!(
                        "Invalid toRelation operation: expected the operand to be a function, got {self}: {subject}"
                    ),
                }
            }
            Expression::RelationProj(_, relation, projections) => {
                let subject = relation.return_type();
                match subject {
                    ReturnType::Relation(domains) => {
                        let new_doms = domains
                            .iter()
                            .zip(projections.iter())
                            .filter_map(|(domain, included)| {
                                if included.is_none() {
                                    // The domains corresponding to projections which are None remain in the relation
                                    Some(domain.clone())
                                } else {
                                    None
                                }
                            })
                            .collect();
                        ReturnType::Relation(new_doms)
                    }
                    _ => bug!(
                        "Invalid RelationProj operation: expected the operand to be a relation, got {self}: {subject}"
                    ),
                }
            }
            Expression::Pred(_, ev) => ev.return_type(),
            Expression::Succ(_, ev) => ev.return_type(),
            Expression::Card(..) => ReturnType::Int,
            Expression::Subsequence(_, _, _) => ReturnType::Bool,
            Expression::Substring(_, _, _) => ReturnType::Bool,
            Expression::AttributeAsConstraint(_, _, _, _) => ReturnType::Bool,
        }
    }
}

impl Expression {
    /// Visit each direct `Expression` child by reference, without cloning.
    pub fn for_each_expr_child<'a>(&'a self, f: &mut impl FnMut(&'a Expression)) {
        match self {
            // Special Case
            Expression::AbstractLiteral(_, alit) => match alit {
                AbstractLiteral::Set(v) | AbstractLiteral::MSet(v) | AbstractLiteral::Tuple(v) => {
                    for expr in v {
                        f(expr);
                    }
                }
                AbstractLiteral::Partition(two_d_v) => {
                    for part in two_d_v {
                        for expr in part {
                            f(expr);
                        }
                    }
                }
                AbstractLiteral::Matrix(v, _domain) => {
                    for expr in v {
                        f(expr);
                    }
                }
                AbstractLiteral::Record(rs) => {
                    for r in rs {
                        f(&r.value);
                    }
                }
                AbstractLiteral::Sequence(v) => {
                    for expr in v {
                        f(expr);
                    }
                }
                AbstractLiteral::Function(vs) => {
                    for (a, b) in vs {
                        f(a);
                        f(b);
                    }
                }
                AbstractLiteral::Variant(v) => {
                    f(&v.value);
                }
                AbstractLiteral::Relation(vs) => {
                    for exprs in vs {
                        for expr in exprs {
                            f(expr);
                        }
                    }
                }
                AbstractLiteral::Permutation(cycles) => {
                    for cycle in cycles {
                        for expr in cycle {
                            f(expr);
                        }
                    }
                }
            },
            Expression::Root(_, vs) => {
                for expr in vs {
                    f(expr);
                }
            }

            // Moo<Expression>
            Expression::DominanceRelation(_, m1)
            | Expression::TypeAnnotation(_, m1, _)
            | Expression::DomainAnnotation(_, m1, _)
            | Expression::ToInt(_, m1)
            | Expression::Abs(_, m1)
            | Expression::Sum(_, m1)
            | Expression::Product(_, m1)
            | Expression::Min(_, m1)
            | Expression::Max(_, m1)
            | Expression::Not(_, m1)
            | Expression::Or(_, m1)
            | Expression::And(_, m1)
            | Expression::Neg(_, m1)
            | Expression::PermInverse(_, m1)
            | Expression::Defined(_, m1)
            | Expression::AllDiff(_, m1)
            | Expression::SatAllDifferentComparisons(_, m1)
            | Expression::SmtDistinct(_, m1)
            | Expression::Factorial(_, m1)
            | Expression::Range(_, m1)
            | Expression::Participants(_, m1)
            | Expression::Parts(_, m1)
            | Expression::ToSet(_, m1)
            | Expression::ToMSet(_, m1)
            | Expression::ToRelation(_, m1)
            | Expression::Pred(_, m1)
            | Expression::Succ(_, m1)
            | Expression::Card(_, m1)
            | Expression::RecordField(_, m1, _)
            | Expression::Active(_, m1, _) => {
                f(m1);
            }

            // Moo<Expression> + Moo<Expression>
            Expression::Table(_, m1, m2)
            | Expression::NegativeTable(_, m1, m2)
            | Expression::ShortTable(_, m1, m2)
            | Expression::Bubble(_, m1, m2)
            | Expression::Imply(_, m1, m2)
            | Expression::Iff(_, m1, m2)
            | Expression::Difference(_, m1, m2)
            | Expression::Union(_, m1, m2)
            | Expression::In(_, m1, m2)
            | Expression::Intersect(_, m1, m2)
            | Expression::Supset(_, m1, m2)
            | Expression::SupsetEq(_, m1, m2)
            | Expression::Subset(_, m1, m2)
            | Expression::SubsetEq(_, m1, m2)
            | Expression::Eq(_, m1, m2)
            | Expression::Neq(_, m1, m2)
            | Expression::Geq(_, m1, m2)
            | Expression::Leq(_, m1, m2)
            | Expression::Gt(_, m1, m2)
            | Expression::Lt(_, m1, m2)
            | Expression::CatchUndef(_, m1, m2)
            | Expression::SafeDiv(_, m1, m2)
            | Expression::UnsafeDiv(_, m1, m2)
            | Expression::SafeMod(_, m1, m2)
            | Expression::UnsafeMod(_, m1, m2)
            | Expression::UnsafePow(_, m1, m2)
            | Expression::SafePow(_, m1, m2)
            | Expression::Minus(_, m1, m2)
            | Expression::PairwiseSum(_, m1, m2)
            | Expression::PairwiseProduct(_, m1, m2)
            | Expression::Image(_, m1, m2)
            | Expression::ImageSet(_, m1, m2)
            | Expression::PreImage(_, m1, m2)
            | Expression::Inverse(_, m1, m2)
            | Expression::Compose(_, m1, m2)
            | Expression::Restrict(_, m1, m2)
            | Expression::Apart(_, m1, m2)
            | Expression::Together(_, m1, m2)
            | Expression::Party(_, m1, m2)
            | Expression::LexLt(_, m1, m2)
            | Expression::LexLeq(_, m1, m2)
            | Expression::LexGt(_, m1, m2)
            | Expression::LexGeq(_, m1, m2)
            | Expression::Subsequence(_, m1, m2)
            | Expression::Substring(_, m1, m2) => {
                f(m1);
                f(m2);
            }

            // Moo<Expression> + Vec<Expression>
            Expression::UnsafeIndex(_, m, vs) | Expression::SafeIndex(_, m, vs) => {
                f(m);
                for v in vs {
                    f(v);
                }
            }
            // Moo<Expression> + Vec<Option<Expression>>
            Expression::UnsafeSlice(_, m, vs)
            | Expression::SafeSlice(_, m, vs)
            | Expression::RelationProj(_, m, vs) => {
                f(m);
                for e in vs.iter().flatten() {
                    f(e);
                }
            }

            // Moo<Expression> + Moo<Expression> + Moo<Expression>
            Expression::SatElement(_, m1, m2, m3)
            | Expression::AtLeast(_, m1, m2, m3)
            | Expression::AtMost(_, m1, m2, m3)
            | Expression::Gcc(_, m1, m2, m3)
            | Expression::GccWeak(_, m1, m2, m3) => {
                f(m1);
                f(m2);
                f(m3);
            }

            // Moo<Expression> + Moo<Expression> (two-arg globals)
            Expression::AllDifferentExcept(_, m1, m2)
            | Expression::ElementId(_, m1, m2)
            | Expression::IndexOf(_, m1, m2) => {
                f(m1);
                f(m2);
            }

            // Moo<Expression> + DomainPtr
            Expression::InDomain(_, m, _) => {
                f(m);
            }

            // Option<Moo<Expression>> + Moo<Expression>
            Expression::Flatten(_, opt, m) => {
                if let Some(e) = opt {
                    f(e);
                }
                f(m);
            }

            // Moo<Expression> + AttrName + Option<Moo<Expression>>
            Expression::AttributeAsConstraint(_, target, _, val) => {
                f(target);
                if let Some(v) = val {
                    f(v);
                }
            }

            // Moo<Expression> + Atom
            Expression::MinionReify(_, m, _) | Expression::MinionReifyImply(_, m, _) => {
                f(m);
            }

            // Reference + Moo<Expression>
            Expression::AuxDeclaration(_, _, m) => {
                f(m);
            }

            // SATIntEncoding + Moo<Expression> + (i32, i32)
            Expression::SatObjective(_, _, m) | Expression::SATInt(_, _, m, _) => {
                f(m);
            }

            // No Expression children
            Expression::Comprehension(_, _)
            | Expression::Atomic(_, _)
            | Expression::FromSolution(_, _)
            | Expression::Metavar(_, _)
            | Expression::FlatAbsEq(_, _, _)
            | Expression::FlatMinusEq(_, _, _)
            | Expression::FlatProductEq(_, _, _, _)
            | Expression::MinionDivEqUndefZero(_, _, _, _)
            | Expression::MinionModuloEqUndefZero(_, _, _, _)
            | Expression::MinionPow(_, _, _, _)
            | Expression::FlatAllDiff(_, _)
            | Expression::FlatTable(..)
            | Expression::FlatShortTable(..)
            | Expression::FlatMinEq(_, _, _)
            | Expression::FlatSumGeq(_, _, _)
            | Expression::FlatSumLeq(_, _, _)
            | Expression::FlatIneq(_, _, _, _)
            | Expression::FlatWatchedLiteral(_, _, _)
            | Expression::FlatWeightedSumLeq(_, _, _, _)
            | Expression::FlatWeightedSumGeq(_, _, _, _)
            | Expression::MinionWInIntervalSet(_, _, _)
            | Expression::MinionWInSet(_, _, _)
            | Expression::MinionElementOne(_, _, _, _)
            | Expression::FlatLexLt(_, _, _)
            | Expression::FlatLexLeq(_, _, _) => {}
        }
    }

    /// Visits this expression and all of its expression descendants by reference.
    pub fn for_each_expression<'a>(&'a self, f: &mut impl FnMut(&'a Expression)) {
        f(self);
        self.for_each_expr_child(&mut |child| child.for_each_expression(f));
    }

    /// Returns whether this expression or any expression below it satisfies `predicate`.
    ///
    /// Unlike [`Uniplate::universe`], this does not construct an owned copy of the traversed tree.
    pub fn any_expression(&self, mut predicate: impl FnMut(&Expression) -> bool) -> bool {
        fn visit(expr: &Expression, predicate: &mut impl FnMut(&Expression) -> bool) -> bool {
            if predicate(expr) {
                return true;
            }

            let mut found = false;
            expr.for_each_expr_child(&mut |child| {
                if !found {
                    found = visit(child, predicate);
                }
            });
            found
        }

        visit(self, &mut predicate)
    }

    /// Returns whether any expression strictly below this one satisfies `predicate`.
    pub fn any_expression_descendant(
        &self,
        mut predicate: impl FnMut(&Expression) -> bool,
    ) -> bool {
        let mut found = false;
        self.for_each_expr_child(&mut |child| {
            if !found {
                found = child.any_expression(&mut predicate);
            }
        });
        found
    }
}

impl Expression {
    /// Invalidates the cached content hash on this expression only.
    pub(crate) fn invalidate_cached_content_hash(&self) {
        let metadata = self.meta_ref();
        metadata
            .cached_content_hash
            .store(NO_HASH, Ordering::Relaxed);
    }

    /// Returns the cached expression content hash, computing and storing it when absent.
    pub(crate) fn cached_content_hash(&self) -> u64 {
        let stored = self.meta_ref().cached_content_hash.load(Ordering::Relaxed);
        if stored != NO_HASH {
            HASH_HITS.fetch_add(1, Ordering::Relaxed);
            return stored;
        }
        HASH_MISSES.fetch_add(1, Ordering::Relaxed);
        self.calculate_content_hash()
    }

    /// Computes an expression content hash from precomputed child node hashes.
    ///
    /// Child hashes must be supplied in the same order as [`Uniplate::children`] for this
    /// expression.
    #[allow(unused_variables)]
    pub(crate) fn content_hash_from_child_hashes(
        &self,
        child_hashes: &mut impl Iterator<Item = u64>,
    ) -> u64 {
        fn child_hash(child_hashes: &mut impl Iterator<Item = u64>) -> u64 {
            child_hashes
                .next()
                .expect("expression content hash missing child hash")
        }

        let mut hasher = DefaultHasher::new();
        std::mem::discriminant(self).hash(&mut hasher);
        match self {
            // Special Case
            Expression::AbstractLiteral(_, alit) => match alit {
                AbstractLiteral::Set(v)
                | AbstractLiteral::MSet(v)
                | AbstractLiteral::Tuple(v)
                | AbstractLiteral::Sequence(v) => {
                    for expr in v {
                        child_hash(child_hashes).hash(&mut hasher);
                    }
                }
                AbstractLiteral::Matrix(v, domain) => {
                    domain.hash(&mut hasher);
                    for expr in v {
                        child_hash(child_hashes).hash(&mut hasher);
                    }
                }
                AbstractLiteral::Record(rs) => {
                    for r in rs {
                        r.name.hash(&mut hasher);
                        child_hash(child_hashes).hash(&mut hasher);
                    }
                }
                AbstractLiteral::Function(vs) => {
                    for (a, b) in vs {
                        child_hash(child_hashes).hash(&mut hasher);
                        child_hash(child_hashes).hash(&mut hasher);
                    }
                }
                AbstractLiteral::Variant(v) => {
                    v.name.hash(&mut hasher);
                    child_hash(child_hashes).hash(&mut hasher);
                }
                AbstractLiteral::Relation(v) => {
                    for exprs in v {
                        for expr in exprs {
                            child_hash(child_hashes).hash(&mut hasher);
                        }
                    }
                }
                AbstractLiteral::Partition(v) => {
                    for exprs in v {
                        for expr in exprs {
                            child_hash(child_hashes).hash(&mut hasher);
                        }
                    }
                }
                AbstractLiteral::Permutation(v) => {
                    for exprs in v {
                        for expr in exprs {
                            child_hash(child_hashes).hash(&mut hasher);
                        }
                    }
                }
            },
            Expression::Root(_, vs) => {
                for expr in vs {
                    child_hash(child_hashes).hash(&mut hasher);
                }
            }

            // Moo<Expression>
            Expression::DominanceRelation(_, m1)
            | Expression::ToInt(_, m1)
            | Expression::Abs(_, m1)
            | Expression::Sum(_, m1)
            | Expression::Product(_, m1)
            | Expression::Min(_, m1)
            | Expression::Max(_, m1)
            | Expression::Not(_, m1)
            | Expression::Or(_, m1)
            | Expression::And(_, m1)
            | Expression::Neg(_, m1)
            | Expression::PermInverse(_, m1)
            | Expression::Defined(_, m1)
            | Expression::AllDiff(_, m1)
            | Expression::SatAllDifferentComparisons(_, m1)
            | Expression::SmtDistinct(_, m1)
            | Expression::Factorial(_, m1)
            | Expression::Participants(_, m1)
            | Expression::Parts(_, m1)
            | Expression::Range(_, m1)
            | Expression::ToSet(_, m1)
            | Expression::ToMSet(_, m1)
            | Expression::ToRelation(_, m1)
            | Expression::Pred(_, m1)
            | Expression::Succ(_, m1)
            | Expression::Card(_, m1) => {
                child_hash(child_hashes).hash(&mut hasher);
            }
            Expression::TypeAnnotation(_, m1, domain) => {
                child_hash(child_hashes).hash(&mut hasher);
                domain.hash(&mut hasher);
            }
            Expression::DomainAnnotation(_, m1, domain) => {
                child_hash(child_hashes).hash(&mut hasher);
                domain.hash(&mut hasher);
            }

            // Moo<Expression> + Moo<Expression>
            Expression::Table(_, m1, m2)
            | Expression::NegativeTable(_, m1, m2)
            | Expression::ShortTable(_, m1, m2)
            | Expression::Bubble(_, m1, m2)
            | Expression::Imply(_, m1, m2)
            | Expression::Iff(_, m1, m2)
            | Expression::Difference(_, m1, m2)
            | Expression::Union(_, m1, m2)
            | Expression::In(_, m1, m2)
            | Expression::Intersect(_, m1, m2)
            | Expression::Supset(_, m1, m2)
            | Expression::SupsetEq(_, m1, m2)
            | Expression::Subset(_, m1, m2)
            | Expression::SubsetEq(_, m1, m2)
            | Expression::Eq(_, m1, m2)
            | Expression::Neq(_, m1, m2)
            | Expression::Geq(_, m1, m2)
            | Expression::Leq(_, m1, m2)
            | Expression::Gt(_, m1, m2)
            | Expression::Lt(_, m1, m2)
            | Expression::Apart(_, m1, m2)
            | Expression::Together(_, m1, m2)
            | Expression::Party(_, m1, m2)
            | Expression::CatchUndef(_, m1, m2)
            | Expression::SafeDiv(_, m1, m2)
            | Expression::UnsafeDiv(_, m1, m2)
            | Expression::SafeMod(_, m1, m2)
            | Expression::UnsafeMod(_, m1, m2)
            | Expression::UnsafePow(_, m1, m2)
            | Expression::SafePow(_, m1, m2)
            | Expression::Minus(_, m1, m2)
            | Expression::PairwiseSum(_, m1, m2)
            | Expression::PairwiseProduct(_, m1, m2)
            | Expression::Image(_, m1, m2)
            | Expression::ImageSet(_, m1, m2)
            | Expression::PreImage(_, m1, m2)
            | Expression::Inverse(_, m1, m2)
            | Expression::Compose(_, m1, m2)
            | Expression::Restrict(_, m1, m2)
            | Expression::LexLt(_, m1, m2)
            | Expression::LexLeq(_, m1, m2)
            | Expression::LexGt(_, m1, m2)
            | Expression::LexGeq(_, m1, m2)
            | Expression::Subsequence(_, m1, m2)
            | Expression::Substring(_, m1, m2) => {
                child_hash(child_hashes).hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
            }
            // Moo<Expression> + Vec<Expression>
            Expression::UnsafeIndex(_, m, vs) | Expression::SafeIndex(_, m, vs) => {
                child_hash(child_hashes).hash(&mut hasher);
                for v in vs {
                    child_hash(child_hashes).hash(&mut hasher);
                }
            }

            // Moo<Expression> + Vec<Option<Expression>>
            Expression::UnsafeSlice(_, m, vs)
            | Expression::SafeSlice(_, m, vs)
            | Expression::RelationProj(_, m, vs) => {
                child_hash(child_hashes).hash(&mut hasher);
                for v in vs {
                    match v {
                        Some(e) => child_hash(child_hashes).hash(&mut hasher),
                        None => 0u64.hash(&mut hasher),
                    }
                }
            }

            // Moo<Expression> + Moo<Expression> + Moo<Expression>
            Expression::SatElement(_, m1, m2, m3)
            | Expression::AtLeast(_, m1, m2, m3)
            | Expression::AtMost(_, m1, m2, m3)
            | Expression::Gcc(_, m1, m2, m3)
            | Expression::GccWeak(_, m1, m2, m3) => {
                child_hash(child_hashes).hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
            }

            // Moo<Expression> + Moo<Expression> (two-arg globals)
            Expression::AllDifferentExcept(_, m1, m2)
            | Expression::ElementId(_, m1, m2)
            | Expression::IndexOf(_, m1, m2) => {
                child_hash(child_hashes).hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
            }

            // Moo<Expression> + Name
            Expression::RecordField(_, m, n) | Expression::Active(_, m, n) => {
                child_hash(child_hashes).hash(&mut hasher);
                n.hash(&mut hasher);
            }

            // Moo<Expression> + DomainPtr
            Expression::InDomain(_, m, d) => {
                child_hash(child_hashes).hash(&mut hasher);
                d.hash(&mut hasher);
            }

            // Option<Moo<Expression>> + Moo<Expression>
            Expression::Flatten(_, opt, m) => {
                if let Some(e) = opt {
                    child_hash(child_hashes).hash(&mut hasher);
                }
                child_hash(child_hashes).hash(&mut hasher);
            }

            // Moo<Expression> + AttrName + Option<Moo<Expression>>
            Expression::AttributeAsConstraint(_, target, attr, val) => {
                child_hash(child_hashes).hash(&mut hasher);
                attr.hash(&mut hasher);
                if let Some(v) = val {
                    child_hash(child_hashes).hash(&mut hasher);
                }
            }

            // Moo<Expression> + Atom
            Expression::MinionReify(_, m, a) | Expression::MinionReifyImply(_, m, a) => {
                child_hash(child_hashes).hash(&mut hasher);
                a.hash(&mut hasher);
            }

            // Reference + Moo<Expression>
            Expression::AuxDeclaration(_, r, m) => {
                r.hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
            }

            // SATIntEncoding + Moo<Expression> + (i32, i32)
            Expression::SatObjective(_, minimise, _) => {
                minimise.hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
            }
            Expression::SATInt(_, enc, m, bounds) => {
                enc.hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
                bounds.hash(&mut hasher);
            }

            // Non-Expression Moo types - hash normally
            Expression::Comprehension(_, c) => c.hash(&mut hasher),

            // Leaf types - no Expression children
            Expression::Atomic(_, a) => a.hash(&mut hasher),
            Expression::FromSolution(_, a) => a.hash(&mut hasher),
            Expression::Metavar(_, u) => u.hash(&mut hasher),

            // Two Moo<Atom>
            Expression::FlatAbsEq(_, a1, a2) | Expression::FlatMinusEq(_, a1, a2) => {
                a1.hash(&mut hasher);
                a2.hash(&mut hasher);
            }

            // Three Moo<Atom>
            Expression::FlatProductEq(_, a1, a2, a3)
            | Expression::MinionDivEqUndefZero(_, a1, a2, a3)
            | Expression::MinionModuloEqUndefZero(_, a1, a2, a3)
            | Expression::MinionPow(_, a1, a2, a3) => {
                a1.hash(&mut hasher);
                a2.hash(&mut hasher);
                a3.hash(&mut hasher);
            }

            Expression::FlatShortTable(_, inputs, rows) => {
                inputs.hash(&mut hasher);
                rows.hash(&mut hasher);
            }
            Expression::FlatTable(_, inputs, rows, negative) => {
                inputs.hash(&mut hasher);
                rows.hash(&mut hasher);
                negative.hash(&mut hasher);
            }

            // Vec<Atom>
            Expression::FlatAllDiff(_, vs) => {
                for v in vs {
                    v.hash(&mut hasher);
                }
            }

            // Vec<Atom> + Atom
            Expression::FlatMinEq(_, vs, a)
            | Expression::FlatSumGeq(_, vs, a)
            | Expression::FlatSumLeq(_, vs, a) => {
                for v in vs {
                    v.hash(&mut hasher);
                }
                a.hash(&mut hasher);
            }

            // Moo<Atom> + Moo<Atom> + Box<Literal>
            Expression::FlatIneq(_, a1, a2, lit) => {
                a1.hash(&mut hasher);
                a2.hash(&mut hasher);
                lit.hash(&mut hasher);
            }

            // Reference + Literal
            Expression::FlatWatchedLiteral(_, r, l) => {
                r.hash(&mut hasher);
                l.hash(&mut hasher);
            }

            // Vec<Literal> + Vec<Atom> + Moo<Atom>
            Expression::FlatWeightedSumLeq(_, lits, atoms, a)
            | Expression::FlatWeightedSumGeq(_, lits, atoms, a) => {
                for l in lits {
                    l.hash(&mut hasher);
                }
                for at in atoms {
                    at.hash(&mut hasher);
                }
                a.hash(&mut hasher);
            }

            // Atom + Vec<i32>
            Expression::MinionWInIntervalSet(_, a, vs) | Expression::MinionWInSet(_, a, vs) => {
                a.hash(&mut hasher);
                for v in vs {
                    v.hash(&mut hasher);
                }
            }

            // Vec<Atom> + Moo<Atom> + Moo<Atom>
            Expression::MinionElementOne(_, vs, a1, a2) => {
                for v in vs {
                    v.hash(&mut hasher);
                }
                a1.hash(&mut hasher);
                a2.hash(&mut hasher);
            }

            // Vec<Atom> + Vec<Atom>
            Expression::FlatLexLt(_, v1, v2) | Expression::FlatLexLeq(_, v1, v2) => {
                for v in v1 {
                    v.hash(&mut hasher);
                }
                for v in v2 {
                    v.hash(&mut hasher);
                }
            }
        };

        hasher.finish()
    }

    /// Computes an expression content hash that ignores metadata except for child content hashes.
    pub(crate) fn calculate_content_hash(&self) -> u64 {
        let mut hashes = Vec::new();
        self.for_each_expr_child(&mut |child| hashes.push(child.cached_content_hash()));
        let mut child_hashes = hashes.into_iter();
        let result = self.content_hash_from_child_hashes(&mut child_hashes);
        self.meta_ref()
            .cached_content_hash
            .store(result, Ordering::Relaxed);
        result
    }
}

#[cfg(test)]
mod tests {
    use crate::matrix_expr;

    use super::*;

    #[test]
    fn list_inspection_borrows_expression_elements_without_cloning_the_list() {
        let list = matrix_expr![
            Expression::from(Literal::Int(1)),
            Expression::from(Literal::Int(2))
        ];

        assert_eq!(list.list_len(), Some(2));
        assert!(list.is_list());
        assert!(matches!(list.unwrap_list_cow(), Some(Cow::Borrowed(_))));
    }

    #[test]
    fn list_inspection_materialises_literal_elements_only_when_they_are_requested() {
        let list = Expression::Atomic(
            Metadata::new(),
            Atom::Literal(Literal::AbstractLiteral(
                AbstractLiteral::matrix_implied_indices(vec![Literal::Int(1), Literal::Int(2)]),
            )),
        );

        assert_eq!(list.list_len(), Some(2));
        assert!(list.is_list());
        assert!(matches!(list.unwrap_list_cow(), Some(Cow::Owned(_))));
        assert_eq!(
            list.unwrap_list_cow().map(Cow::into_owned),
            list.unwrap_list()
        );
    }

    #[test]
    fn list_length_looks_through_annotations() {
        let list = Expression::DomainAnnotation(
            Metadata::new(),
            Moo::new(matrix_expr![Expression::from(Literal::Int(1))]),
            Domain::int(vec![Range::Bounded(0, 1)]),
        );

        assert_eq!(list.list_len(), Some(1));
        assert!(matches!(list.unwrap_list_cow(), Some(Cow::Borrowed(_))));
    }
}