soft3/nox/rs/patterns/call.rs

//! pattern 16: call — non-deterministic witness injection
//! step 1: evaluate tag formula
//! step 2: call prover for witness (None -> Halt)
//! step 3: validate check(witness, object) = 0
//! step 4: return witness

use nebu::Goldilocks;
use crate::data::{Reduction, Order};
use crate::reduce::{Outcome, ErrorKind, pair_children, evaluate_unary, evaluate};
use crate::call::CallProvider;
use crate::trace::{Tracer, TraceRow};
use crate::data::NIL;
use crate::jets::registry::JetRegistry;

pub fn call_witness<const N: usize, T: Tracer>(
    reduction: &mut Reduction<N>, object: Order, body: Order, budget: u64,
    calls: &dyn CallProvider<N>, tracer: &mut T, depth: u64,
    row: &mut TraceRow, registry: &JetRegistry<N>,
) -> Outcome {
    let (tag_formula, check_formula) = match pair_children(reduction, body) {
        Some(p) => p,
        None => return Outcome::Error(ErrorKind::Malformed),
    };
    // Initial phase: tag is statically bounded — partitioned eval.
    let (tag_result, budget) = match evaluate_unary(reduction, object, tag_formula, budget, calls, tracer, depth, registry) {
        Ok(v) => v, Err(o) => return o,
    };
    let tag_value = match reduction.atom_value(tag_result) {
        Some(v) => v,
        None => return Outcome::Error(ErrorKind::TypeError),
    };
    let witness = match calls.provide(reduction, tag_value, object) {
        Some(w) => w,
        None => return Outcome::Halt(budget),
    };
    let witness_object = match reduction.pair(witness, object) {
        Some(c) => c,
        None => return Outcome::Error(ErrorKind::Unavailable),
    };
    // Continuation phase: check_f sees a prover-supplied witness. Witness
    // shape is unknown statically; cost is dynamic. Sequential threading.
    // propagate the actual error/halt from check formula evaluation —
    // a Malformed/TypeError/Unavailable in check_f is a bug in check_f
    // itself, NOT a witness rejection. only a finished check returning
    // non-zero counts as CallRejected (handled below).
    let (check_result, budget) = match evaluate(reduction, witness_object, check_formula, budget, calls, tracer, depth, registry) {
        Ok(v) => v,
        Err(o) => return o,
    };
    match reduction.atom_value(check_result) {
        Some(v) if v == Goldilocks::ZERO => {
            row.r[4] = tag_value.as_u64();
            row.r[5] = witness as u64;
            row.r[6] = check_result as u64;
            Outcome::Ok(witness, budget)
        }
        _ => {
            row.r[4] = tag_value.as_u64();
            row.r[5] = witness as u64;
            row.r[6] = NIL as u64;
            Outcome::Error(ErrorKind::CallRejected)
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::reduce::{reduce, Outcome, ErrorKind};
    use crate::call::{CallProvider, LookProvider, NullCalls};
    use crate::trace::NoTrace;
    use crate::data::{Reduction, Order};
    use nebu::Goldilocks;

    fn g(v: u64) -> Goldilocks { Goldilocks::new(v) }

    #[test]
    fn call_null_provider_halts() {
        let mut ar = Reduction::<1024>::new();
        let obj = ar.atom(g(0)).unwrap();
        // formula = [16 [[1 0] [1 [0 1]]]]
        // tag = quote(0), check = quote(identity = axis(1))
        let t16 = ar.atom(g(16)).unwrap();
        let t1 = ar.atom(g(1)).unwrap();
        let zero = ar.atom(g(0)).unwrap();
        let tag_formula = ar.pair(t1, zero).unwrap();
        let t0 = ar.atom(g(0)).unwrap();
        let axis1 = ar.pair(t0, t1).unwrap(); // [0 1] = axis(1)
        let check_formula = ar.pair(t1, axis1).unwrap(); // [1 [0 1]] = quote(axis(1))
        let body = ar.pair(tag_formula, check_formula).unwrap();
        let formula = ar.pair(t16, body).unwrap();
        match reduce(&mut ar, obj, formula, 1000, &NullCalls, &mut NoTrace) {
            Outcome::Halt(_) => {}
            o => panic!("expected Halt, got {:?}", o),
        }
    }

    #[test]
    fn call_rejected_on_bad_witness() {
        struct BadWitness;
        impl LookProvider for BadWitness {
            fn look(&self, _: Goldilocks, _: Goldilocks, _: Goldilocks) -> Option<Goldilocks> { None }
        }
        impl<const N: usize> CallProvider<N> for BadWitness {
            fn provide(&self, reduction: &mut Reduction<N>, _tag: Goldilocks, _object: Order) -> Option<Order> {
                // provide witness = 99, but check expects 0
                Some(reduction.atom(g(99)).unwrap())
            }
        }

        let mut ar = Reduction::<1024>::new();
        let obj = ar.atom(g(0)).unwrap();
        // formula = [16 [[1 0] [1 99]]]
        // tag=quote(0), check=quote(99) — check returns 99 ≠ 0 → CallRejected
        let t16 = ar.atom(g(16)).unwrap();
        let t1 = ar.atom(g(1)).unwrap();
        let zero = ar.atom(g(0)).unwrap();
        let tag_f = ar.pair(t1, zero).unwrap();
        let ninety_nine = ar.atom(g(99)).unwrap();
        let check_f = ar.pair(t1, ninety_nine).unwrap();
        let body = ar.pair(tag_f, check_f).unwrap();
        let formula = ar.pair(t16, body).unwrap();
        match reduce(&mut ar, obj, formula, 1000, &BadWitness, &mut NoTrace) {
            Outcome::Error(ErrorKind::CallRejected) => {}
            o => panic!("expected CallRejected, got {:?}", o),
        }
    }

    /// Provider injects witness=0, check formula `[1 0]` returns 0 (passes).
    /// Verifies a call succeeds when check reduces to 0 (zero means accepted).
    #[test]
    fn call_accepts_zero_check() {
        struct ZeroWitness;
        impl LookProvider for ZeroWitness {
            fn look(&self, _: Goldilocks, _: Goldilocks, _: Goldilocks) -> Option<Goldilocks> { None }
        }
        impl<const N: usize> CallProvider<N> for ZeroWitness {
            fn provide(&self, reduction: &mut Reduction<N>, _tag: Goldilocks, _object: Order) -> Option<Order> {
                Some(reduction.atom(g(0)).unwrap())
            }
        }

        let mut ar = Reduction::<1024>::new();
        let obj = ar.atom(g(0)).unwrap();
        // formula = [16 [[1 0] [1 0]]] — tag=quote(0), check=quote(0) (returns 0 → accepted)
        let t16 = ar.atom(g(16)).unwrap();
        let t1 = ar.atom(g(1)).unwrap();
        let zero = ar.atom(g(0)).unwrap();
        let tag_f = ar.pair(t1, zero).unwrap();
        let check_f = ar.pair(t1, zero).unwrap();
        let body = ar.pair(tag_f, check_f).unwrap();
        let formula = ar.pair(t16, body).unwrap();
        match reduce(&mut ar, obj, formula, 1000, &ZeroWitness, &mut NoTrace) {
            Outcome::Ok(result, _) => {
                let v = ar.atom_value(result).unwrap();
                assert_eq!(v, g(0), "zero witness accepted when check returns 0");
            }
            o => panic!("expected Ok when check returns 0, got {:?}", o),
        }
    }

    /// Provider injects witness=42, check formula `[1 0]` returns 0.
    /// Expected: Outcome::Ok with result Order equal to the injected witness.
    #[test]
    fn call_accepts_valid_witness() {
        struct GoodWitness;
        impl LookProvider for GoodWitness {
            fn look(&self, _: Goldilocks, _: Goldilocks, _: Goldilocks) -> Option<Goldilocks> { None }
        }
        impl<const N: usize> CallProvider<N> for GoodWitness {
            fn provide(&self, reduction: &mut Reduction<N>, _tag: Goldilocks, _object: Order) -> Option<Order> {
                Some(reduction.atom(g(42)).unwrap())
            }
        }

        let mut ar = Reduction::<1024>::new();
        let obj = ar.atom(g(0)).unwrap();
        // formula = [16 [[1 0] [1 0]]]  — tag=quote(0), check=quote(0) (always passes)
        let t16 = ar.atom(g(16)).unwrap();
        let t1 = ar.atom(g(1)).unwrap();
        let zero = ar.atom(g(0)).unwrap();
        let tag_f = ar.pair(t1, zero).unwrap();
        let check_f = ar.pair(t1, zero).unwrap();
        let body = ar.pair(tag_f, check_f).unwrap();
        let formula = ar.pair(t16, body).unwrap();
        match reduce(&mut ar, obj, formula, 1000, &GoodWitness, &mut NoTrace) {
            Outcome::Ok(result, _) => {
                let v = ar.atom_value(result).unwrap();
                assert_eq!(v, g(42), "result should be the injected witness");
            }
            o => panic!("expected Ok(witness=42), got {:?}", o),
        }
    }
}