lambda-ref-cat 0.1.0

//! End-to-end interpreter and garbage-collector tests.
//!
//! Tests use `run` / `run_inspecting` for the integrated pipeline and call
//! `gc::collect` directly to verify mark-sweep behaviour against the heap
//! produced by evaluation.

use lambda_ref_cat::env::Env;
use lambda_ref_cat::error::Error;
use lambda_ref_cat::eval::{Fuel, eval};
use lambda_ref_cat::gc;
use lambda_ref_cat::heap::Heap;
use lambda_ref_cat::syntax::{Expr, VarName};
use lambda_ref_cat::value::Value;
use lambda_ref_cat::{DEFAULT_FUEL, run, run_inspecting, run_with_fuel};

#[derive(Debug)]
enum TestFailure {
    Interpreter(Error),
    Assertion {
        what: &'static str,
        actual: String,
        expected: String,
    },
}

impl From<Error> for TestFailure {
    fn from(value: Error) -> Self {
        Self::Interpreter(value)
    }
}

impl std::fmt::Display for TestFailure {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Interpreter(e) => write!(f, "interpreter error: {e}"),
            Self::Assertion {
                what,
                actual,
                expected,
            } => write!(
                f,
                "assertion {what:?} failed: expected {expected:?}, got {actual:?}"
            ),
        }
    }
}

fn check_displays(value: &Value, expected: &str, what: &'static str) -> Result<(), TestFailure> {
    let actual = format!("{value}");
    (actual == expected)
        .then_some(())
        .ok_or(TestFailure::Assertion {
            what,
            actual,
            expected: expected.to_owned(),
        })
}

fn check_error_matches<F: FnOnce(&Error) -> bool>(
    result: Result<Value, Error>,
    predicate: F,
    what: &'static str,
) -> Result<(), TestFailure> {
    match result {
        Err(e) => predicate(&e).then_some(()).ok_or(TestFailure::Assertion {
            what,
            actual: format!("{e}"),
            expected: "matching error variant".to_owned(),
        }),
        Ok(v) => Err(TestFailure::Assertion {
            what,
            actual: format!("{v}"),
            expected: "an error".to_owned(),
        }),
    }
}

fn check_heap_size(heap: &Heap, expected: usize, what: &'static str) -> Result<(), TestFailure> {
    let actual = heap.len();
    (actual == expected)
        .then_some(())
        .ok_or(TestFailure::Assertion {
            what,
            actual: actual.to_string(),
            expected: expected.to_string(),
        })
}

#[test]
fn ref_then_deref_roundtrip() -> Result<(), TestFailure> {
    let value = run(r"!ref (\x. x)").run()?;
    check_displays(&value, "\\x. x", "ref-then-deref returns the original")
}

#[test]
fn alloc_returns_reference_value() -> Result<(), TestFailure> {
    let (value, heap) = run_inspecting(r"ref (\x. x)", Fuel::new(100)).run()?;
    let is_ref = matches!(value, Value::Ref(_));
    is_ref.then_some(()).ok_or(TestFailure::Assertion {
        what: "ref returns Value::Ref",
        actual: format!("{value}"),
        expected: "ref(...)".to_owned(),
    })?;
    check_heap_size(&heap, 1, "single allocation")
}

#[test]
fn assign_updates_cell() -> Result<(), TestFailure> {
    let source = r"
        let r = ref (\x. x) in
        r := (\y. y) ;
        !r
    ";
    let value = run(source).run()?;
    check_displays(&value, "\\y. y", "assign then read returns the new value")
}

#[test]
fn sequence_returns_last_value() -> Result<(), TestFailure> {
    let source = r"(\x. x) ; (\y. y)";
    let value = run(source).run()?;
    check_displays(&value, "\\y. y", "seq returns the second's value")
}

#[test]
fn assign_returns_assigned_value() -> Result<(), TestFailure> {
    // `r := v` evaluates to v
    let source = r"let r = ref (\u. u) in r := (\y. y)";
    let value = run(source).run()?;
    check_displays(&value, "\\y. y", "assign returns the stored value")
}

#[test]
fn shadowed_outer_after_inner_let() -> Result<(), TestFailure> {
    // Ensure lexical scoping is preserved when ref cells are around.
    let source = r"
        let x = \a. a in
        let _r = ref x in
        let x = \b. b in
        x
    ";
    let value = run(source).run()?;
    check_displays(&value, "\\b. b", "inner shadowing survives ref cells")
}

#[test]
fn gc_keeps_reachable_through_closure_capture() -> Result<(), TestFailure> {
    let source = r"
        let r = ref (\u. u) in
        \w. r
    ";
    let (value, heap) = run_inspecting(source, Fuel::new(100)).run()?;
    check_heap_size(&heap, 1, "one cell before collection")?;
    let collected = gc::collect(&[&value], &Env::empty(), &heap);
    check_heap_size(&collected, 1, "captured cell survives collection")
}

#[test]
fn gc_frees_unreachable_cell() -> Result<(), TestFailure> {
    // outer is defined before the allocation, so its closure captures an env
    // that does not contain unused.  Returning outer drops the only path to
    // the allocated cell.
    let source = r"
        let outer = \u. u in
        let _unused = ref (\v. v) in
        outer
    ";
    let (value, heap) = run_inspecting(source, Fuel::new(100)).run()?;
    check_heap_size(&heap, 1, "one cell before collection")?;
    let collected = gc::collect(&[&value], &Env::empty(), &heap);
    check_heap_size(&collected, 0, "unreachable cell freed")
}

#[test]
fn gc_collects_cycles() -> Result<(), TestFailure> {
    // Build two cells that point to each other, then return a value that does
    // not capture them.  Defining outer before the lets ensures its closure
    // env does not include a or b.
    let source = r"
        let outer = \u. u in
        let a = ref outer in
        let b = ref outer in
        a := b ;
        b := a ;
        outer
    ";
    let (value, heap) = run_inspecting(source, Fuel::new(100)).run()?;
    check_heap_size(&heap, 2, "two cells before collection")?;
    let collected = gc::collect(&[&value], &Env::empty(), &heap);
    check_heap_size(&collected, 0, "cycle of unreachable cells freed")
}

#[test]
fn gc_transitively_keeps_cells() -> Result<(), TestFailure> {
    // a holds Ref(b), b holds outer.  Returning a should keep both alive.
    let source = r"
        let outer = \u. u in
        let b = ref outer in
        let a = ref b in
        a
    ";
    let (value, heap) = run_inspecting(source, Fuel::new(100)).run()?;
    check_heap_size(&heap, 2, "two cells before collection")?;
    let collected = gc::collect(&[&value], &Env::empty(), &heap);
    check_heap_size(&collected, 2, "transitive chain survives collection")
}

#[test]
fn dangling_reference_after_collection_errors() -> Result<(), TestFailure> {
    let (value, heap) = run_inspecting(r"ref (\x. x)", Fuel::new(100)).run()?;
    let collected = gc::collect(&[], &Env::empty(), &heap);
    check_heap_size(&collected, 0, "GC with no roots empties heap")?;
    // Re-bind the now-dangling ref and try to deref it.
    let env = Env::empty().extend(VarName::from("r"), value);
    let result = eval(
        &Expr::deref(Expr::var("r")),
        &env,
        collected,
        Fuel::new(100),
    );
    check_error_matches(
        result.map(|(v, _, _)| v),
        |e| matches!(e, Error::DanglingReference { .. }),
        "deref against swept heap is DanglingReference",
    )
}

#[test]
fn deref_non_reference_errors() -> Result<(), TestFailure> {
    let result = run(r"!(\x. x)").run();
    check_error_matches(
        result,
        |e| matches!(e, Error::NotAReference { .. }),
        "deref of closure is NotAReference",
    )
}

#[test]
fn assign_to_non_reference_errors() -> Result<(), TestFailure> {
    let result = run(r"(\x. x) := (\y. y)").run();
    check_error_matches(
        result,
        |e| matches!(e, Error::NotAReference { .. }),
        "assignment LHS must be a reference",
    )
}

#[test]
fn apply_reference_errors() -> Result<(), TestFailure> {
    let result = run(r"(ref (\x. x)) (\y. y)").run();
    check_error_matches(
        result,
        |e| matches!(e, Error::NotAFunction { .. }),
        "applying a ref is NotAFunction",
    )
}

#[test]
fn unbound_variable_errors() -> Result<(), TestFailure> {
    let result = run(r"(\x. y) (\u. u)").run();
    check_error_matches(
        result,
        |e| matches!(e, Error::UnboundVariable { .. }),
        "free variable surfaces as UnboundVariable",
    )
}

#[test]
fn omega_diverges_into_fuel_exhaustion() -> Result<(), TestFailure> {
    let result = run_with_fuel(r"(\x. x x) (\x. x x)", Fuel::new(64)).run();
    check_error_matches(
        result,
        |e| matches!(e, Error::FuelExhausted { .. }),
        "omega still exhausts fuel with refs in the language",
    )
}

#[test]
fn bare_colon_is_parse_error() -> Result<(), TestFailure> {
    let result = run(r":x").run();
    check_error_matches(
        result,
        |e| {
            matches!(
                e,
                Error::UnexpectedChar { .. } | Error::UnexpectedEnd { .. }
            )
        },
        "bare colon rejected by lexer",
    )
}

#[test]
fn fix_still_works_with_state() -> Result<(), TestFailure> {
    // Spike 1's fix logic should be unchanged.
    let source = r"(fix f. \n. n) (\x. x)";
    let value = run(source).run()?;
    check_displays(
        &value,
        "\\x. x",
        "fix continues to reduce when body ignores f",
    )
}

#[test]
fn default_fuel_constant_visible() -> Result<(), TestFailure> {
    (DEFAULT_FUEL == 10_000)
        .then_some(())
        .ok_or(TestFailure::Assertion {
            what: "DEFAULT_FUEL constant",
            actual: DEFAULT_FUEL.to_string(),
            expected: "10000".to_owned(),
        })
}