elly_core/

value.rs

//! Runtime [`Value`] and payload types: [`ObjectData`] and [`HostFn`].
//! Includes value equality, hashing, and human-readable rendering. Split from
//! `eval.rs`; the evaluator drives these via `apply1`/`apply_n` and owns the
//! environment types ([`EnvNode`], [`ModuleData`], [`Ctx`], [`Raised`]).

use alloc::boxed::Box;
use alloc::rc::Rc;
use alloc::string::{String, ToString};
use alloc::vec::Vec;
use core::hash::{Hash, Hasher};

use num_bigint::BigInt;
use rpds::{HashTrieMap, Vector};

use crate::ast::{json_str, Lambda, Text};

use super::{Builtin, Ctx, Env, EnvNode, EnvRef, ModuleData, Raised};

/// An object: a payload and the prototype that defines its type.
/// A [`Value::Object`] is an `Rc` pointer to `ObjectData`.
///
/// `proto` is the [`Module`](EnvNode::Module) terminal that is the instance; methods
/// dispatched on the object run in this environment. This is also the handle
/// used by [`Value::Iota`]'s `home`.
///
/// `data` is a single-slot payload. Records with named fields are not yet implemented;
/// maps are the current idiom. Only the module's own code can access this via
/// [`__value`](crate::HomeLeaf::Value).
#[derive(Debug)]
pub struct ObjectData {
    pub(crate) proto: EnvRef,
    pub(crate) data: Value,
}

impl ObjectData {
    /// The object's prototype, as the module value it is.
    pub fn proto(&self) -> Value {
        Value::Module(self.proto.clone())
    }

    /// The object's payload. Public to Rust because a debugger and an embedding
    /// host sit outside the language's module scope; no *builtin* hands it out,
    /// so Elly code cannot reach it except through its own module's `__value`.
    pub fn data(&self) -> &Value {
        &self.data
    }
}

/// A runtime value.
///
/// On 64-bit targets `Value` is aligned to 16 bytes: it is already 32 bytes
/// wide, so this costs it nothing, and its 16-byte halves never straddle a
/// cache line. The `EnvNode` cons cell grows from 40 to 48 bytes (its `Rc`
/// allocation from 56 to 64, which the system allocator rounds 56 up to
/// anyway), for 3–7% on the environment-heavy benches. On wasm32 `Value` is 24
/// bytes, and the alignment would pad it to 32 and cost 5–16%, so it is left off.
#[derive(Debug, Clone)]
#[cfg_attr(target_pointer_width = "64", repr(align(16)))]
pub enum Value {
    /// Machine-word integer: the canonical representation for any integer fitting
    /// in `i64`. Stored inline to avoid allocation on common arithmetic paths.
    /// The invariant "an integer is [`Value::BigInt`] iff it does not fit `i64`"
    /// ensures well-defined equality and hashing.
    I64(i64),
    /// Arbitrary-precision integer for magnitudes outside `i64`. Stored behind
    /// an `Rc` to keep `Value` width small and make cloning a refcount bump.
    /// Always `|n| > i64::MAX` per the canonical invariant.
    BigInt(Rc<BigInt>),
    /// A symbol literal (stored without the leading dot) as owned [`Text`].
    /// Rendered with a leading dot.
    Symbol(Text),
    /// An owned, immutable UTF-8 string ([`Text`]). Equality and order follow
    /// Rust's `&str` (lexicographic byte order). Rendered quoted and re-escaped.
    Str(Text),
    /// The unit value `()`. A nullary variant that does not widen `Value`.
    /// Distinct from the empty list.
    Unit,
    /// A runtime list backed by an immutable `rpds::Vector` (O(log n) access,
    /// cheap structural-sharing clone/append). The empty list is a `List` of
    /// arity zero, not `Unit`.
    List(Vector<Value>),
    /// A closure capturing its environment over shared `code`. `id` is a
    /// per-runtime unique identity minted at creation; closures compare by
    /// identity rather than structure. `code` is the `Lambda` (patterns and body);
    /// `applied` tracks bound parameters, so remaining ones are `code.head[applied..]`.
    /// Partial application extends `env` and increments `applied` without
    /// re-allocating the `Lambda`.
    Closure {
        id: u64,
        code: Rc<Lambda>,
        applied: u8,
        env: Env,
    },
    /// An immutable, persistent, unordered map from keys to values, backed by
    /// `rpds::HashTrieMap`. Keys are identified by structural value equality.
    /// See `docs/elly-spec.md` § maps.
    Map(HashTrieMap<Value, Value>),
    /// A partially-applied builtin: a native `__…` operation and its
    /// gathered arguments. Invoked when `args.len()` reaches the op's arity.
    Builtin { op: Builtin, args: Vec<Value> },
    /// A partially-applied host function: a callback provided by the embedder
    /// ([`HostFn`]) and its gathered arguments. This is the primary FFI boundary
    /// in the calling direction.
    ///
    /// It is a `Value` rather than an `Expr` so it retains meaning regardless of
    /// the context it is handed. Identity is the `Rc` pointer plus applied
    /// arguments.
    ///
    /// Applied arguments use `Box<[Value]>` instead of `Vec` to keep `Value`
    /// width at four words, as pinned by `tests/sizes.rs`. Both are one
    /// allocation per curried step.
    HostFn {
        code: Rc<HostFn>,
        args: Box<[Value]>,
    },
    /// A module instance: the module's [`Module`](EnvNode::Module) terminal.
    /// The value is the terminal itself, ensuring the module's code and its
    /// instantiation environment are linked. Applying a symbol materializes
    /// the item. Identity is the `Rc` pointer.
    Module(EnvRef),
    /// An iota: an atomic identity declared with `const`. Equal only to itself.
    /// Identity is the pair (instance, position), where `home` is the instance's
    /// [`Module`](EnvNode::Module) terminal and `index` is the position in
    /// [`ModuleData::iota_names`]. Derived upon reference; two references to the
    /// same iota of one instance are equal.
    Iota { home: EnvRef, index: u32 },
    /// An object: a payload plus the prototype module defining its type
    /// (see [`ObjectData`]). Built by the [`__new`](crate::HomeLeaf::New) leaf
    /// of the owning module. Applying a symbol dispatches the name by materializing
    /// it from the prototype and applying it to the object. Compared by payload
    /// contents and prototype identity.
    Object(Rc<ObjectData>),
}

/// Structural value equality used by `__eq`. Data compares structurally
/// (integers mathematically, symbols/strings by text, lists elementwise, maps by
/// content); callables compare by identity (builtins by operation and arguments,
/// closures by unique id). Different variants are never equal. Total order is not
/// defined; `<` / `>` only compare `Int` / `Str`.
impl PartialEq for Value {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Value::I64(a), Value::I64(b)) => a == b,
            (Value::BigInt(a), Value::BigInt(b)) => a == b,
            // An `I64` and a `BigInt` never compare equal: by the canonical
            // invariant they partition the integers (a `BigInt` never fits `i64`),
            // so they cannot denote the same number.
            (Value::Symbol(a), Value::Symbol(b)) => a == b,
            (Value::Str(a), Value::Str(b)) => a == b,
            // Unit is a singleton — one value, so any two are equal.
            (Value::Unit, Value::Unit) => true,
            (Value::List(a), Value::List(b)) => a == b,
            // `HashTrieMap`'s own `PartialEq` is content-based (order-independent).
            (Value::Map(a), Value::Map(b)) => a == b,
            // Same operation and equal applied arguments.
            (Value::Builtin { op: o1, args: a1 }, Value::Builtin { op: o2, args: a2 }) => {
                o1 == o2 && a1 == a2
            }
            // The same reading for a host callback, with the allocation standing
            // in for the operation: a `HostFn` has no structure to compare, so
            // two of one name are two functions.
            (
                Value::HostFn {
                    code: c1, args: a1, ..
                },
                Value::HostFn {
                    code: c2, args: a2, ..
                },
            ) => Rc::ptr_eq(c1, c2) && a1 == a2,
            (Value::Closure { id: i1, .. }, Value::Closure { id: i2, .. }) => i1 == i2,
            // A module value is its instance's identity: the terminal's `Rc`
            // pointer, not the item contents (mirrors the closure "compare by
            // identity" precedent).
            (Value::Module(a), Value::Module(b)) => EnvRef::ptr_eq(a, b),
            // An iota is the instance it was declared by plus its position, so
            // two iotas of one instance differ and one iota of two instantiations
            // does too.
            (
                Value::Iota {
                    home: a, index: i, ..
                },
                Value::Iota {
                    home: b, index: j, ..
                },
            ) => i == j && EnvRef::ptr_eq(a, b),
            // An object is its prototype by *identity* and its payload by
            // *contents* — the nominal/structural mix objects are for. The payload
            // half is what makes two accesses of one data item compare equal, and
            // what lets an object be a map key.
            (Value::Object(a), Value::Object(b)) => {
                EnvRef::ptr_eq(&a.proto, &b.proto) && a.data == b.data
            }
            _ => false,
        }
    }
}

impl Eq for Value {}

/// A `Hash` consistent with structural `PartialEq`. A per-variant discriminant
/// prevents collisions between different types (e.g. symbol `.0` and integer `0`).
/// `Map` keys hash order-independently by summing the hash of entries.
impl Hash for Value {
    fn hash<H: Hasher>(&self, state: &mut H) {
        core::mem::discriminant(self).hash(state);
        match self {
            Value::I64(n) => n.hash(state),
            Value::BigInt(n) => n.hash(state),
            Value::Symbol(s) => s.hash(state),
            Value::Str(s) => s.hash(state),
            // Unit carries no payload; the discriminant above is its whole hash.
            Value::Unit => {}
            Value::List(vs) => {
                for v in vs.iter() {
                    v.hash(state);
                }
            }
            Value::Map(m) => {
                let mut acc: u64 = 0;
                for (k, v) in m.iter() {
                    let mut h = FnvHasher::new();
                    k.hash(&mut h);
                    v.hash(&mut h);
                    acc = acc.wrapping_add(h.finish());
                }
                acc.hash(state);
            }
            Value::Builtin { op, args } => {
                op.hash(state);
                for a in args {
                    a.hash(state);
                }
            }
            Value::HostFn { code, args } => {
                (Rc::as_ptr(code) as usize).hash(state);
                for a in args {
                    a.hash(state);
                }
            }
            Value::Closure { id, .. } => id.hash(state),
            // Hash by the same identity used for equality: the terminal's pointer.
            Value::Module(home) => (EnvRef::as_ptr(home) as usize).hash(state),
            Value::Iota { home, index } => {
                (EnvRef::as_ptr(home) as usize).hash(state);
                index.hash(state);
            }
            // Mirrors the equality above: the prototype's pointer, the payload's
            // contents.
            Value::Object(obj) => {
                (EnvRef::as_ptr(&obj.proto) as usize).hash(state);
                obj.data.hash(state);
            }
        }
    }
}

/// A deterministic no_std FNV-1a `Hasher` used for order-independent map
/// hashing (see `impl Hash for Value`). Not the hasher used by `HashTrieMap`.
struct FnvHasher(u64);

impl FnvHasher {
    fn new() -> Self {
        FnvHasher(0xcbf2_9ce4_8422_2325)
    }
}

impl Hasher for FnvHasher {
    fn finish(&self) -> u64 {
        self.0
    }
    fn write(&mut self, bytes: &[u8]) {
        for &b in bytes {
            self.0 ^= u64::from(b);
            self.0 = self.0.wrapping_mul(0x0000_0100_0000_01b3);
        }
    }
}

/// A host function: a native callback provided by the embedder, behind the `Rc`
/// a [`Value::HostFn`] carries.
///
/// It includes a name, arity, and code. The evaluator gathers arguments according
/// to `arity` before calling the function, making it strict and curried.
///
/// `Ctx` is passed to allow the callback to call Elly functions ([`apply_with`](crate::apply_with))
/// using the same ID source, preventing identity collisions for minted closures.
///
/// Arity must be at least 1; zero-argument constants are supplied as values.
pub struct HostFn {
    pub(crate) name: Text,
    pub(crate) arity: usize,
    pub(crate) f: Box<HostCall>,
}

/// The contract a host callback signs: a whole call's arguments — exactly
/// [`arity`](HostFn::arity) of them, since the evaluator gathers before it fires
/// — plus the [`Ctx`], answering a value or a [`Raised`].
pub type HostCall = dyn Fn(&[Value], &Ctx) -> Result<Value, Raised>;

impl HostFn {
    /// A host function taking `arity` arguments.
    ///
    /// Name is for diagnostics; identity is the allocation. Panics on `arity == 0`.
    pub fn new(
        name: impl Into<Text>,
        arity: usize,
        f: impl Fn(&[Value], &Ctx) -> Result<Value, Raised> + 'static,
    ) -> HostFn {
        assert!(arity > 0, "a host function takes at least one argument");
        HostFn {
            name: name.into(),
            arity,
            f: Box::new(f),
        }
    }

    /// The name the function renders under.
    pub fn name(&self) -> &Text {
        &self.name
    }

    /// How many arguments it is called with.
    pub fn arity(&self) -> usize {
        self.arity
    }
}

/// The callback is not `Debug`, so the derive cannot apply; the shape a
/// `Value::HostFn` shows is its name and arity, which is what identifies it in a
/// dump anyway.
impl core::fmt::Debug for HostFn {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("HostFn")
            .field("name", &self.name)
            .field("arity", &self.arity)
            .finish_non_exhaustive()
    }
}

impl Value {
    /// Builds an integer value from a `BigInt`, demoting to [`Value::I64`] if it
    /// fits. This maintains the canonical invariant that a `BigInt` is used only
    /// when the value does not fit `i64`, ensuring consistent equality and hashing.
    pub fn from_bigint(n: BigInt) -> Value {
        match i64::try_from(&n) {
            Ok(i) => Value::I64(i),
            Err(_) => Value::BigInt(Rc::new(n)),
        }
    }

    /// [`from_bigint`](Value::from_bigint) for a `BigInt` reference. Demotion
    /// to `i64` is decided before cloning to avoid unnecessary allocations
    /// for literals fitting in `i64`.
    pub fn from_bigint_ref(n: &BigInt) -> Value {
        match i64::try_from(n) {
            Ok(i) => Value::I64(i),
            Err(_) => Value::BigInt(Rc::new(n.clone())),
        }
    }

    /// Creates a `Value::HostFn` from a callback. Unapplied, so the first
    /// argument begins the currying process. Panics on `arity == 0`.
    pub fn host_fn(
        name: impl Into<Text>,
        arity: usize,
        f: impl Fn(&[Value], &Ctx) -> Result<Value, Raised> + 'static,
    ) -> Value {
        Value::HostFn {
            code: Rc::new(HostFn::new(name, arity, f)),
            args: Box::new([]),
        }
    }

    /// Creates a list value from its elements. Hides the backing `rpds::Vector`
    /// to avoid version/feature mismatches between the core and the host.
    pub fn list(elems: impl IntoIterator<Item = Value>) -> Value {
        Value::List(elems.into_iter().collect())
    }

    /// Creates a map value from its entries; later entries overwrite equal keys.
    /// Hides `rpds` implementation details.
    pub fn map(entries: impl IntoIterator<Item = (Value, Value)>) -> Value {
        let mut m = HashTrieMap::new();
        for (k, v) in entries {
            m.insert_mut(k, v);
        }
        Value::Map(m)
    }

    /// Returns the elements of a list value, or `None` otherwise. Hides
    /// `rpds` implementation details.
    pub fn list_items(&self) -> Option<impl ExactSizeIterator<Item = &Value>> {
        match self {
            Value::List(elems) => Some(elems.iter()),
            _ => None,
        }
    }

    /// Returns the number of arguments a function-shaped value needs before it
    /// runs. `None` for non-functions, including applicable values like lists
    /// or modules (which use projection, not calls).
    ///
    /// Runners use this to detect under-application (see `docs/done/2026-08-14_elly-run.md`).
    pub fn remaining_arity(&self) -> Option<usize> {
        match self {
            Value::Closure { code, applied, .. } => Some(code.head.len() - *applied as usize),
            Value::Builtin { op, args } => Some(op.arity() - args.len()),
            Value::HostFn { code, args } => Some(code.arity - args.len()),
            _ => None,
        }
    }

    /// Returns the [`ModuleData`] of a [`Value::Module`], or `None`. A module
    /// value holds the [`Module`](EnvNode::Module) terminal; this provides access
    /// to the item table without matching the environment shape.
    pub fn module_data(&self) -> Option<&Rc<ModuleData>> {
        match self {
            Value::Module(home) => match &**home {
                EnvNode::Module { data, .. } => Some(data),
                _ => unreachable!("a module value always holds a module terminal"),
            },
            _ => None,
        }
    }

    /// Returns the [`ObjectData`] of a [`Value::Object`], or `None`. Provides
    /// access to the payload and prototype.
    pub fn object_data(&self) -> Option<&Rc<ObjectData>> {
        match self {
            Value::Object(obj) => Some(obj),
            _ => None,
        }
    }

    /// Returns a human-readable rendering for golden tests.
    pub fn to_display(&self) -> String {
        let mut out = String::new();
        self.write_display(&mut out);
        out
    }

    fn write_display(&self, out: &mut String) {
        match self {
            Value::I64(n) => out.push_str(&n.to_string()),
            Value::BigInt(n) => out.push_str(&n.to_string()),
            Value::Symbol(s) => {
                out.push('.');
                out.push_str(s);
            }
            // A string renders as a quoted, re-escaped literal (`"foo"`),
            // distinguishing it from symbols and names.
            Value::Str(s) => json_str(s, out),
            // Unit renders `()`, distinct from the empty list `[]`.
            Value::Unit => out.push_str("()"),
            // Lists render with brackets (`[]`, `[.a]`, `[.a, .b]`).
            Value::List(vs) => {
                out.push('[');
                for (i, v) in vs.iter().enumerate() {
                    if i > 0 {
                        out.push_str(", ");
                    }
                    v.write_display(out);
                }
                out.push(']');
            }
            // Maps render sorted by rendered key text (ties broken by value)
            // for stable dumps: `{}` or `{ .a: 1, .b: 2 }`.
            Value::Map(m) => {
                if m.is_empty() {
                    out.push_str("{}");
                } else {
                    let mut entries: Vec<(String, String)> = m
                        .iter()
                        .map(|(k, v)| {
                            let mut ks = String::new();
                            k.write_display(&mut ks);
                            let mut vs = String::new();
                            v.write_display(&mut vs);
                            (ks, vs)
                        })
                        .collect();
                    entries.sort();
                    out.push('{');
                    for (i, (ks, vs)) in entries.iter().enumerate() {
                        out.push_str(if i > 0 { ", " } else { " " });
                        out.push_str(ks);
                        out.push_str(": ");
                        out.push_str(vs);
                    }
                    out.push_str(" }");
                }
            }
            Value::Closure { .. } => out.push_str("<closure>"),
            Value::Builtin { op, .. } => {
                out.push_str("<builtin ");
                out.push_str(op.name());
                out.push('>');
            }
            // Host functions render by name and arity.
            Value::HostFn { code, .. } => {
                out.push_str("<hostfn ");
                out.push_str(code.name.as_str());
                out.push('>');
            }
            Value::Module(_) => out.push_str("<module>"),
            // Iotas render as `<const .name>`. The module instance is not
            // named to avoid dependence on host-defined resolver paths.
            Value::Iota { home, index } => {
                out.push_str("<const .");
                if let EnvNode::Module { data, .. } = &**home {
                    if let Some(name) = data.iota(*index) {
                        out.push_str(name);
                    }
                }
                out.push('>');
            }
            // Objects render as `<object payload>`. The prototype is not
            // named for the same reason as modules. The payload is shown to support
            // debugging by hosts.
            Value::Object(obj) => {
                out.push_str("<object ");
                obj.data.write_display(out);
                out.push('>');
            }
        }
    }
}