cairn_core/

node.rs

//! The content-addressed AST node model.
//!
//! A node references its children by their content hash, so a node's own hash
//! covers the hashes of everything beneath it — the Merkle property the store
//! relies on (`docs/design.md` Section 7). Two structurally identical subtrees
//! therefore have the same hash and are stored once.
//!
//! This is the v0.1 seed model. It now carries the Section 4 function contract
//! (`given`/`produces`/`requires`/`on_failure`) so the checker can enforce it.
//! A signature is part of a function's identity, so `Param`/`Produces` are
//! inlined into the `Function` node rather than being separate nodes. Record
//! and variant *definitions*, generics, and operators are later slices.

use crate::ty::{Confidence, Effect, Type};
use serde::{Deserialize, Serialize};
use sha2::{Digest, Sha256};
use std::collections::BTreeSet;
use std::fmt;

/// A content hash: the lowercase hex SHA-256 of a node's canonical bytes.
#[derive(Clone, PartialEq, Eq, Hash, Debug, Serialize, Deserialize)]
pub struct NodeHash(String);

impl NodeHash {
    pub fn as_str(&self) -> &str {
        &self.0
    }

    /// Wrap an existing hash string. Used by the store when reading a ref back;
    /// not for constructing arbitrary hashes in normal code.
    pub(crate) fn from_raw(s: String) -> Self {
        NodeHash(s)
    }

    /// Reconstruct a hash identifier from its string form — for transports
    /// (MCP, CLI) that received it from a previous call. The string is treated
    /// as an opaque identifier; its content is not validated.
    pub fn parse(s: &str) -> Self {
        NodeHash(s.to_string())
    }
}

impl fmt::Display for NodeHash {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.0)
    }
}

/// One declared input: its name, type, and the minimum confidence a caller
/// must supply (the `given` clause).
#[derive(Clone, PartialEq, Eq, Debug, Serialize, Deserialize)]
pub struct Param {
    pub name: String,
    pub ty: Type,
    pub min_confidence: Confidence,
}

/// The `produces` clause: the output type and the confidence it carries.
#[derive(Clone, PartialEq, Eq, Debug, Serialize, Deserialize)]
pub struct Produces {
    pub ty: Type,
    pub confidence: Confidence,
}

/// A binary operator. Arithmetic operands and result are `Number`;
/// comparison operands share a type and the result is `Bool`; logical
/// operands and result are `Bool` (short-circuit). Deliberately small
/// (Principle 9): one canonical operator per operation.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Serialize, Deserialize)]
pub enum BinOp {
    Add,
    Sub,
    Mul,
    Div,
    /// Signed remainder (`a % b`); arithmetic, both operands `Number`.
    Mod,
    Eq,
    /// `a != b` — the negation of `Eq`, same operand rule.
    Neq,
    Lt,
    /// `a <= b`.
    Le,
    /// `a > b`.
    Gt,
    /// `a >= b`.
    Ge,
    /// Short-circuit boolean conjunction; both operands `Bool`.
    And,
    /// Short-circuit boolean disjunction; both operands `Bool`.
    Or,
}

impl BinOp {
    /// Comparisons yield `Bool` over two same-typed operands.
    pub fn is_comparison(self) -> bool {
        use BinOp::*;
        matches!(self, Eq | Neq | Lt | Le | Gt | Ge)
    }

    /// Logical operators take and yield `Bool` and short-circuit.
    pub fn is_logical(self) -> bool {
        matches!(self, BinOp::And | BinOp::Or)
    }

    /// The Section 5 infix symbol.
    pub fn symbol(self) -> &'static str {
        match self {
            BinOp::Add => "+",
            BinOp::Sub => "-",
            BinOp::Mul => "*",
            BinOp::Div => "/",
            BinOp::Mod => "%",
            BinOp::Eq => "==",
            BinOp::Neq => "!=",
            BinOp::Lt => "<",
            BinOp::Le => "<=",
            BinOp::Gt => ">",
            BinOp::Ge => ">=",
            BinOp::And => "&&",
            BinOp::Or => "||",
        }
    }
}

/// One arm of a `match`: a variant case, names bound to its payload fields
/// (in declaration order), and the body evaluated when that case matches.
#[derive(Clone, PartialEq, Eq, Debug, Serialize, Deserialize)]
pub struct MatchArm {
    pub case: String,
    pub bindings: Vec<String>,
    pub body: NodeHash,
}

/// A stored AST node. Compound variants reference children by [`NodeHash`].
#[derive(Clone, PartialEq, Eq, Debug, Serialize, Deserialize)]
pub enum Node {
    /// An integer literal. (A single unified numeric type is the language
    /// direction; the seed model only needs a concrete numeric leaf.)
    Lit(i64),
    /// An IEEE-754 double, stored as its bit pattern so the node stays
    /// `Eq`/hashable and content-addresses deterministically. The uniform
    /// i64 slot *is* these bits; only `FloatOp`/conversions reinterpret.
    FloatLit(u64),
    /// Arithmetic or comparison on two `Float`s. `op` is restricted to
    /// `+ - * /` and `== < <= > >=` (no `% != && ||` on Float).
    FloatOp {
        op: BinOp,
        lhs: NodeHash,
        rhs: NodeHash,
    },
    /// `Number` → `Float`.
    IntToFloat(NodeHash),
    /// `Float` → `Number`: truncates toward zero; traps on NaN/overflow
    /// (a clean trap, not silent UB — like the bounds checks).
    FloatToInt(NodeHash),
    /// A `Decimal` literal: the value pre-scaled by 10_000 (so `1.25` is
    /// `12500`). Exact; no rounding at use.
    DecimalLit(i64),
    /// Arithmetic or comparison on two `Decimal`s. `+ -` are plain i64;
    /// `*` is `(a*b)/10000`, `/` is `(a*10000)/b` (rescaling). All six
    /// comparisons are exact. `% && ||` are rejected by the checker.
    DecimalOp {
        op: BinOp,
        lhs: NodeHash,
        rhs: NodeHash,
    },
    /// `Number` → `Decimal` (multiplies by 10_000).
    IntToDecimal(NodeHash),
    /// `Decimal` → `Number` (integer part; truncates toward zero).
    DecimalToInt(NodeHash),
    /// `Decimal` → `Number`: the raw scaled mantissa (the value ×10_000,
    /// `Decimal`'s documented representation). Identity at runtime; the
    /// seam that lets `decimal_to_str` be written in Cairn.
    DecimalRaw(NodeHash),
    /// A boolean literal. Bool was previously only producible by a
    /// comparison; the literal makes `Bool` a first-class value the
    /// logical operators can stand on.
    Bool(bool),
    /// Logical negation of a `Bool`, yielding `Bool`. The one unary
    /// operator (Principle 9); `&&`/`||` are the binary `BinOp`s.
    Not(NodeHash),
    /// A UTF-8 string literal.
    Str(String),
    /// Length (in bytes) of a string. The first string operation; more
    /// follow with the stdlib.
    StrLen(NodeHash),
    /// ASCII-lowercase a string (`A`–`Z` → `a`–`z`, other bytes
    /// unchanged). The minimal primitive for case-insensitive
    /// matching — needed because some platforms (e.g. Cloudflare)
    /// lowercase HTTP header names, so the `header`/`cookie` lookup
    /// cannot be case-sensitive (design.md §9).
    StrLower(NodeHash),
    /// A one-byte string from a code point 0–255 (the low byte of the
    /// Number; the inverse of indexing a byte out). The minimal
    /// primitive for percent-decoding — added when a real HTML form
    /// (the shipped blog's create) forced `form_value` to URL-decode
    /// `%XX`/`+`, which is otherwise inexpressible in pure Cairn
    /// (design.md §9; Principle 10 — a real need, not speculation).
    StrFromCode(NodeHash),
    /// `a ++ b` — concatenate two strings.
    StrConcat(NodeHash, NodeHash),
    /// Byte substring `s[start .. start+len]`. Bounds-checked: a
    /// negative index/length or `start+len > len(s)` traps (not silent
    /// UB), proven by `out_of_bounds_list_get_and_str_slice_trap`.
    /// **Byte-indexed by design** (decided, not a gap): a Cairn `String`
    /// is byte-addressable for predictable, AI-author-friendly indexing;
    /// codepoint-aware slicing is a stdlib concern, not a core operator
    /// (Principle 9). Slicing across a UTF-8 boundary therefore yields
    /// bytes the host renders lossily — the documented, intended
    /// semantics of a byte slice.
    StrSlice {
        s: NodeHash,
        start: NodeHash,
        len: NodeHash,
    },
    /// Content equality of two strings, yielding `Bool`.
    StrEq(NodeHash, NodeHash),
    /// Whether `needle` occurs in `haystack`, yielding `Bool`.
    StrContains {
        haystack: NodeHash,
        needle: NodeHash,
    },
    /// Whether `s` begins with `prefix`, yielding `Bool`. With
    /// `StrSlice`/`StrLen` this is enough for prefix routing and
    /// path-parameter extraction (e.g. `/customers/{id}`).
    StrStartsWith {
        s: NodeHash,
        prefix: NodeHash,
    },
    /// 0-based byte index of the first occurrence of `needle` in
    /// `haystack`, or `-1` if absent (an empty needle is at 0). Yields
    /// `Number`. With `StrSlice` this is enough to split a delimited
    /// string — e.g. parsing `db_query` rows into typed records.
    StrIndexOf {
        haystack: NodeHash,
        needle: NodeHash,
    },
    /// Decimal rendering of a `Number` as a `String` (e.g. for HTML
    /// output). Correct over the full i64 range, including `i64::MIN`
    /// (rendered in the non-positive domain — no magnitude overflow).
    NumberToStr(NodeHash),
    /// Parse a `String` to a `Number`, leniently: an optional leading `-`
    /// then the leading decimal digits; a non-numeric/empty string yields
    /// 0. The unchecked fast path (cf. `StrToNumberOpt`).
    StrToNumber(NodeHash),
    /// Checked parse: `Some(n)` only if the whole string is a valid
    /// integer (optional `-` then ≥1 digits, nothing else), else `None`.
    /// The handle-able counterpart to `StrToNumber`, paralleling
    /// `ListGet`/`ListTryGet`.
    StrToNumberOpt(NodeHash),
    /// Read the clock (milliseconds). The first effectful primitive: it
    /// performs the `Time` effect and yields a `Number` at `external`
    /// confidence (the value comes from outside the program). Lowers to a
    /// host import; other effects follow the same pattern.
    Now,
    /// A non-empty list literal. Elements share a type `T`; the list's type
    /// is `List<T>`. (Empty literals need a type annotation — unsupported in
    /// v0.3.)
    List(Vec<NodeHash>),
    /// The empty `List<elem>`. The typed counterpart to a `List` literal,
    /// needed because the element type can't be inferred with no elements.
    /// With `ListCons` this lets a recursive function build a list of
    /// runtime length.
    ListEmpty { elem: Type },
    /// Prepend `head` to `tail` (a `List<T>`), yielding a new `List<T>`.
    /// v0.3: an O(n) fresh-array copy — immutable, no structural sharing,
    /// consistent with the bump allocator's documented simplicity.
    ListCons { head: NodeHash, tail: NodeHash },
    /// `Some(value)` — a present `Option<T>` where `T` is the value's
    /// type. The typed result for operations that may have no answer.
    OptionSome(NodeHash),
    /// `None : Option<elem>` — the absent case (element type can't be
    /// inferred with no value, like `ListEmpty`).
    OptionNone { elem: Type },
    /// Eliminate an `Option<T>`: the contained value if `Some`, else
    /// `default`. Both arms share `T`, the expression's type. This is the
    /// noise-free recovery path — no `on_failure` threading.
    OptionElse { opt: NodeHash, default: NodeHash },
    /// Case analysis over an `Option<T>`: bind the payload to
    /// `some_bind` in `some_body`, else evaluate `none_body`. Both bodies
    /// share a type (the expression's type). Unlike `OptionElse` (value
    /// or default) this runs different logic per case — the construct
    /// that makes a returned `Option` usable for control flow.
    OptionMatch {
        opt: NodeHash,
        some_bind: String,
        some_body: NodeHash,
        none_body: NodeHash,
    },
    /// Checked indexing: `Some(elem)` if `index` is in bounds, else
    /// `None`. The handle-able counterpart to `ListGet` (which traps);
    /// neither pollutes signatures with a failure.
    ListTryGet { list: NodeHash, index: NodeHash },
    /// Number of elements in a list.
    ListLen(NodeHash),
    /// Element of a list at a (0-based `Number`) index. No runtime bounds
    /// check in v0.3 (a known simplification, like the bump allocator).
    ListGet { list: NodeHash, index: NodeHash },
    /// A non-empty map literal of key/value pairs. Keys share a type `K`,
    /// values a type `V`; the type is `Map<K, V>`.
    Map(Vec<(NodeHash, NodeHash)>),
    /// Value for a key (linear scan). Key equality is i64/identity —
    /// **exact for `Number` keys, which is `Map`'s decided domain**
    /// (Principle 9: one canonical form). A missing key yields 0;
    /// `MapTryGet` is the handle-able form. Structural keying of any
    /// type (incl. `String`) is *not* a second mechanism here — it is
    /// `find` over a `List` of key/value records (stdlib, first-class
    /// functions), which is structural for any `K`. Decided, not
    /// deferred: adding key-kind dispatch to `Map` would be the
    /// speculative generality Principle 10 forbids when `find` already
    /// covers it (see `string_keyed_lookup_is_find_over_a_list`).
    MapGet { map: NodeHash, key: NodeHash },
    /// Checked lookup: `Some(V)` for the first matching key, else
    /// `None` — the handle-able counterpart to `MapGet` (which yields 0
    /// on a miss, indistinguishable from a real 0). Same decided
    /// Number/identity key domain as `MapGet`.
    MapTryGet { map: NodeHash, key: NodeHash },
    /// Number of entries in a map.
    MapLen(NodeHash),
    /// Observe a value for diagnostics (the `Log` effect), passing it
    /// through unchanged (same type and confidence as the argument). Lowers
    /// to a `host::log` import.
    Log(NodeHash),
    /// Announce that `topic` (a `String`) changed — the `Live` effect
    /// (design.md §10). The live runtime re-renders and pushes to every
    /// connection subscribed to that topic. Yields `Number` (0). Lowers
    /// to a `host::publish` import. Liveness is *this*, explicit and
    /// effect-typed — never an implicit default.
    Publish(NodeHash),
    /// Emit an extra HTTP response header — the `Resp` effect. `name`
    /// and `value` are `String`s (e.g. `"Set-Cookie"`,
    /// `"sid=abc; HttpOnly; Path=/"`); the host buffers it per request
    /// and writes it after the standard headers. Yields `Number` (0),
    /// so it sequences in a step like `publish`. Lowers to a
    /// `host::set_header` import. Response headers are *this*, explicit
    /// and effect-typed — not a hidden `Response` field.
    SetHeader { name: NodeHash, value: NodeHash },
    /// Draw a random `Number` (the `Rand` effect), at `external` confidence
    /// (it comes from outside the program). Lowers to a `host::rand` import.
    Rand,
    /// Allocate a mutable cell holding `value` (the `Mut` effect). Type is
    /// `Cell<T>` where `T` is the value's type.
    MutNew(NodeHash),
    /// Read a mutable cell's current value.
    MutGet(NodeHash),
    /// Write `value` into a cell (the `Mut` effect); passes `value` through.
    MutSet { cell: NodeHash, value: NodeHash },
    /// Write a `String` to a path (the `Disk` effect); returns the number of
    /// bytes written.
    DiskWrite { path: NodeHash, content: NodeHash },
    /// Read the file at a `String` path (the `Disk` effect), returning its
    /// contents as a `String` (host→wasm allocation). A missing file yields
    /// the empty string in v0.3.
    DiskRead(NodeHash),
    /// HTTP(S) GET a `String` URL (the `Net` effect), returning the
    /// HTTP status as a `Number` (`-1` on transport error). Backed by a
    /// real `ureq` + TLS client — no stub path exists (proven by
    /// `real_net_get_returns_the_http_status`).
    NetGet(NodeHash),
    /// Run a SQL statement (the `Db` effect), returning the result as a
    /// `String` at `persisted` confidence (read back from the system of
    /// record). `params` is a `List<String>` bound to the statement's `?`
    /// placeholders by the driver — the *only* query form, so user input
    /// never reaches SQL by concatenation (use an empty list for static
    /// SQL). Backed by **real embedded SQLite only** (rusqlite —
    /// in-memory by default, a file when a path is given). There is **no
    /// canned/stub path**: every query hits the engine (`wasm::run_sql`;
    /// the v0.3 removal of the old canned path is complete).
    DbQuery {
        sql: NodeHash,
        params: NodeHash,
    },
    /// A reference to an in-scope binding, by name.
    Ref(String),
    /// A call: a callee function name plus argument nodes.
    Call { func: String, args: Vec<NodeHash> },
    /// A named module function used as a first-class value. Its type is the
    /// function's signature as a `Fn`. Anonymous lambdas with transitive
    /// closure capture are **shipped** (K2 — see `Lambda`/`CallValue`; the
    /// stdlib `map`/`filter`/`fold` and every app pass closures). `FuncRef`
    /// is the named-function value form; `Lambda` is the anonymous/closure
    /// form — both lower through the funcref table + `call_indirect`.
    FuncRef(String),
    /// Apply a function *value* to arguments. `callee` evaluates to a
    /// `Fn`; `args` are checked against its parameter types and its
    /// effects union into the caller. Lowers to `call_indirect`.
    CallValue {
        callee: NodeHash,
        args: Vec<NodeHash>,
    },
    /// An anonymous closure. `params` are its inputs (typed, like a
    /// function's); `body` is a single result expression. Names it
    /// references that are neither its params nor module functions are
    /// *captured* by value from the enclosing scope at creation. Its type
    /// is a `Fn`; its body's effects live in that `Fn` (a closure's
    /// effects fire when it is *called*, not when it is made). v0.4: a
    /// single-expression body and no uncaught `Fail` (documented — write a
    /// named function and `FuncRef` it for step bodies or failures).
    Lambda {
        params: Vec<Param>,
        body: NodeHash,
    },
    /// A typed hole: an unfilled position carrying what it expects.
    Hole { expects: String },
    /// A binary operation over two sub-expressions.
    BinOp {
        op: BinOp,
        lhs: NodeHash,
        rhs: NodeHash,
    },
    /// Raise a typed failure, short-circuiting the reasoning chain. Its type
    /// is `Never`. The named variant must be covered by the enclosing
    /// function's `on_failure` unless a `Handle` catches it.
    Fail(String),
    /// Run `body`; if it raises one of the handled failure variants, evaluate
    /// that handler's `recover` expression instead. A handled failure does not
    /// propagate. `handlers` maps a failure-variant name to its recovery
    /// expression (which yields the value, or itself `fail`s).
    Handle {
        body: NodeHash,
        handlers: Vec<(String, NodeHash)>,
    },
    /// A conditional expression. `cond` must be `Bool`; the two branches
    /// share a type, which is the expression's type. There is no statement
    /// form — Cairn has expressions and reasoning-chain steps, not imperative
    /// control flow.
    If {
        cond: NodeHash,
        then_branch: NodeHash,
        else_branch: NodeHash,
    },
    /// A reasoning-chain step: `binding = value`.
    Step { binding: String, value: NodeHash },
    /// A function: the full Section 4 contract plus an ordered body and a
    /// result expression.
    Function {
        name: String,
        /// Declared generic type parameters (e.g. `["T"]`). Empty = monomorphic.
        type_params: Vec<String>,
        params: Vec<Param>,
        produces: Produces,
        requires: BTreeSet<Effect>,
        on_failure: Vec<String>,
        body: Vec<NodeHash>,
        result: NodeHash,
    },
    /// A module: named type definitions and function definitions, referenced
    /// by hash. The unit a checker resolves calls and type names within.
    Module {
        name: String,
        types: Vec<NodeHash>,
        functions: Vec<NodeHash>,
    },
    /// A record (product) type definition: named fields, each with a type.
    RecordDef {
        name: String,
        fields: Vec<(String, Type)>,
    },
    /// Construct a record value of a named record type.
    Record {
        type_name: String,
        fields: Vec<(String, NodeHash)>,
    },
    /// Access a field of a record value. `type_name` is the record type the
    /// base must have; it makes the node self-describing for type-directed
    /// lowering (the checker verifies it; the projection elides it).
    Field {
        base: NodeHash,
        type_name: String,
        field: String,
    },
    /// A variant (sum) type definition: named cases, each with named payload
    /// fields (an empty payload is a nullary case).
    VariantDef {
        name: String,
        cases: Vec<(String, Vec<(String, Type)>)>,
    },
    /// Construct a value of a named variant type, in one of its cases.
    Variant {
        type_name: String,
        case: String,
        fields: Vec<(String, NodeHash)>,
    },
    /// Case analysis over a variant value. Must be exhaustive. `type_name`
    /// is the scrutinee's variant type (self-describing for type-directed
    /// lowering; the checker verifies it, the projection elides it).
    Match {
        scrutinee: NodeHash,
        type_name: String,
        arms: Vec<MatchArm>,
    },
}

impl Node {
    /// Canonical bytes used for both hashing and storage.
    ///
    /// v0.1 uses `serde_json`; struct and enum field order is stable and the
    /// effect set is a `BTreeSet`, so the bytes are deterministic. A canonical
    /// binary encoding is a later refinement.
    pub(crate) fn canonical_bytes(&self) -> Vec<u8> {
        serde_json::to_vec(self).expect("Node serialization is infallible")
    }

    /// This node's content hash. Because children are referenced by hash, this
    /// transitively covers the entire subtree (the Merkle property).
    pub fn hash(&self) -> NodeHash {
        let mut hasher = Sha256::new();
        hasher.update(self.canonical_bytes());
        NodeHash(hex(&hasher.finalize()))
    }
}

fn hex(bytes: &[u8]) -> String {
    use std::fmt::Write;
    let mut s = String::with_capacity(bytes.len() * 2);
    for b in bytes {
        write!(s, "{:02x}", b).expect("writing to a String cannot fail");
    }
    s
}