Lines
81.85 %
Functions
43.33 %
Branches
100 %
//! Shared types and helpers across the DO/DO*/DOLIST family.
//!
//! Three concerns live here:
//! - parsing the form's surface syntax (`parse_do_vars`,
//! `parse_end_clause`, `DoVar`, `DoLoop`);
//! - static-time termination + type inference
//! (`static_loop_terminates`, `infer_wasm_type`,
//! `infer_result_pair_element`, `step_pair_element`);
//! - the codegen-side setf-target machinery shared by all three
//! constructs (`collect_setf_targets`, `promote_to_wasm_local`).
//! Everything is `pub(super)` so the sibling `do_loop` and `dolist`
//! modules can use it; nothing escapes to the broader codebase.
use crate::ast::{Expr, PairElement, WasmType};
use crate::compiler::context::CompileContext;
use crate::compiler::emit::FunctionEmitter;
use crate::compiler::expr::{compile_for_stack, eval_value};
use crate::error::{Error, Result};
use crate::runtime::{Symbol, SymbolKind, SymbolTable};
/// Per-binding spec parsed from the variable list of a DO/DO* form.
/// `(name init step)` — both `init` and `step` are optional in source
/// syntax; the runtime treats absent init as `nil` and absent step as
/// "leave the binding alone for this iteration."
pub(super) struct DoVar {
pub(super) name: String,
pub(super) init: Option<Expr>,
pub(super) step: Option<Expr>,
}
/// Owns the raw shape of a do-loop after the surface form has been
/// validated. Reused by both the runtime codegen entry points
/// (`compile_do_runtime{,_for_effect,_for_stack}`) and the iterators
/// inside each variant.
pub(super) struct DoLoop<'a> {
pub(super) vars: &'a [DoVar],
pub(super) end_test: &'a Expr,
pub(super) result_forms: &'a [Expr],
pub(super) body: &'a [Expr],
/// True for DO* (sequential steps), false for DO (parallel).
pub(super) sequential: bool,
pub(super) const MAX_STATIC_LOOP_ITERS: usize = 64;
pub(super) fn parse_do_vars(context: &str, expr: &Expr) -> Result<Vec<DoVar>> {
let list = expr.as_list().ok_or_else(|| {
Error::Compile(format!("{context}: expected variable list, got {expr:?}"))
})?;
list.iter()
.map(|spec| match spec {
Expr::Symbol(name) => Ok(DoVar {
name: name.clone(),
init: None,
step: None,
}),
Expr::List(elems) if !elems.is_empty() && elems.len() <= 3 => {
let name = elems[0].as_symbol().ok_or_else(|| {
Error::Compile(format!(
"{context}: variable name must be a symbol, got {:?}",
elems[0]
))
Ok(DoVar {
name: name.to_string(),
init: elems.get(1).cloned(),
step: elems.get(2).cloned(),
})
_ => Err(Error::Compile(format!(
"{context}: malformed variable spec: {spec:?}"
))),
.collect()
pub(super) fn parse_end_clause<'a>(
context: &str,
expr: &'a Expr,
) -> Result<(&'a Expr, &'a [Expr])> {
let elems = expr.as_list().ok_or_else(|| {
"{context}: end clause must be a list, got {expr:?}"
if elems.is_empty() {
return Err(Error::Compile(format!(
"{context}: end clause must have a test form"
)));
Ok((&elems[0], &elems[1..]))
pub(super) fn infer_wasm_type(
expr: &Expr,
step_hint: Option<&Expr>,
symbols: &SymbolTable,
) -> WasmType {
// A `nil` DO-var init whose step builds a `(cons V acc)` accumulator is
// sized from the cons car's element — checked before the shared classifier
// (which would type a bare nil as `Bool`).
if let Expr::Nil = expr
&& let Some(step) = step_hint
&& let Some(elem) = step_pair_element(step, symbols)
{
return WasmType::PairRef(elem);
// A `nil`-init var whose step assigns a runtime value of some OTHER type —
// e.g. `(setf out (get-input-entities))` (PairRef) or `(setf out (some-
// ratio))` — must be sized from the step's actual produced type, not the
// `Bool` a bare nil classifies to. Otherwise the local is sized i32-shaped
// while the step pushes a ref, and the emitted wasm fails validation. Only
// a pure-native step is probed (eval on a CLONE — no live-table mutation,
// no recursion into user code), matching `resolve_pair_element_from_expr`.
&& is_pure_native_expr(step, symbols)
&& let Ok(resolved) = eval_value(&mut symbols.clone(), step)
&& let Some(ty) = crate::compiler::expr::classify_stack_type(&resolved)
return ty;
// Bytes share StringRef's representation but aren't a `compile_for_stack`
// literal, so they're classified here rather than in `classify_stack_type`.
if let Expr::Bytes(_) = expr {
return WasmType::StringRef;
// Everything else mirrors `compile_for_stack` via the shared classifier;
// List / Quote / Symbol / Lambda fall back to `I32` (the historical
// integer-counter default — the do-var's own `compile_for_stack` declares
// its actual type and a mismatch surfaces as a hard emit error).
crate::compiler::expr::classify_stack_type(expr).unwrap_or(WasmType::I32)
/// Looks for an accumulator `(cons V <result-name>)` that determines
/// the runtime `PairElement` of the do's result. Two patterns: body
/// `(setf acc (cons V acc))` and step `(acc nil (cons V acc))` (or
/// nested via if/cond). Without inspecting the step path, a do whose
/// accumulator lives in its var-step gets the placeholder I32, and
/// consumer dolists downcast to i31 — runtime cast trap.
pub(super) fn infer_result_pair_element(
result_form: &Expr,
body: &[Expr],
stepped: &[(String, Option<Expr>)],
) -> Option<PairElement> {
let Expr::Symbol(target) = result_form else {
return None;
};
let from_body = collect_setf_targets(body)
.into_iter()
.find_map(|(name, rhs)| {
(name == *target)
.then_some(rhs)
.flatten()
.as_ref()
.and_then(|r| step_pair_element(r, symbols))
});
if from_body.is_some() {
return from_body;
stepped.iter().find_map(|(name, step)| {
if name != target {
step.as_ref().and_then(|s| step_pair_element(s, symbols))
/// If `step` is (or contains) a `(CONS car cdr)` whose car has a
/// derivable wasm type, returns the corresponding `PairElement`. Used by
/// nil-init type inference so a let-bound accumulator like
/// `(setf result (cons i result))` picks up `i`'s element type rather
/// than defaulting to a placeholder.
fn step_pair_element(expr: &Expr, symbols: &SymbolTable) -> Option<PairElement> {
let Expr::List(elems) = expr else {
if let Some(Expr::Symbol(name)) = elems.first()
&& name == "CONS"
&& elems.len() == 3
&& let Some(elem) = resolve_pair_element_from_expr(&elems[1], symbols)
return Some(elem);
elems.iter().find_map(|e| step_pair_element(e, symbols))
fn resolve_pair_element_from_expr(expr: &Expr, symbols: &SymbolTable) -> Option<PairElement> {
match expr {
Expr::WasmRuntime(ty) | Expr::WasmLocal(_, ty) => PairElement::from_wasm_type(*ty),
Expr::Number(_) => crate::compiler::native::literal_pair_element(expr),
Expr::T => Some(PairElement::Bool),
Expr::Symbol(name) => {
let sym = symbols.lookup(name)?;
let value = sym.value()?;
resolve_pair_element_from_expr(value, symbols)
// A host-fn / form car (e.g. `(transaction-tag-count i)`) hasn't been
// reduced to a runtime placeholder yet. Eval it on a CLONE (pure — no
// live-table mutation) so the accumulator's element type matches what
// codegen will push, instead of falling through to the scalar default.
// Gated on a native/operator head: those reduce to a runtime
// placeholder without executing user code, so this can't recurse into
// a (possibly non-terminating) user lambda during type inference.
Expr::List(_) if is_pure_native_expr(expr, symbols) => {
let resolved = eval_value(&mut symbols.clone(), expr).ok()?;
match resolved {
Expr::List(_) => None,
other => resolve_pair_element_from_expr(&other, symbols),
_ => None,
/// Whether `expr` is safe to `eval_value` purely for type inference — i.e.
/// it contains NO user-callable anywhere in its tree. Native eval handlers
/// (e.g. `+`) recurse into their arguments, and higher-order natives
/// (MAP/FILTER/FOLD) invoke a function-valued argument, so checking only the
/// outer head is insufficient: `(+ 1 (user-recursive i))` or
/// `(map (function user-recursive) xs)` could still execute user code and
/// non-terminate. This walks the WHOLE expression and admits it only when
/// every call head AND every operand is itself pure-native. A bare symbol is
/// admitted only when it does not name a user function/lambda value (a
/// fn-valued symbol could be dereferenced+called by a HOF native); literals
/// and runtime placeholders are always inert. Conservative by construction —
/// any shape not explicitly inert (Lambda, Quote, FUNCTION-forms, …) is
/// rejected. Mirrored in `binding::infer`.
fn is_pure_native_expr(expr: &Expr, symbols: &SymbolTable) -> bool {
Expr::Number(_)
| Expr::T
| Expr::Nil
| Expr::String(_)
| Expr::Bytes(_)
| Expr::Keyword(_)
| Expr::Quote(_)
| Expr::WasmRuntime(_)
| Expr::WasmLocal(_, _) => true,
Expr::Symbol(name) => !names_user_callable(name, symbols),
Expr::List(elems) => match elems.first() {
Some(Expr::Symbol(head)) => {
head_is_native(head, symbols)
&& elems[1..].iter().all(|e| is_pure_native_expr(e, symbols))
_ => false,
},
fn head_is_native(head: &str, symbols: &SymbolTable) -> bool {
match symbols.lookup(head) {
Some(sym) => {
sym.function().is_none()
&& matches!(sym.kind(), SymbolKind::Native | SymbolKind::Operator)
None => false,
/// Whether `name` resolves to a user function / lambda value — such a symbol,
/// passed to a higher-order native, would be dereferenced and called during
/// `eval_value`, so it is NOT inert for purity purposes.
fn names_user_callable(name: &str, symbols: &SymbolTable) -> bool {
match symbols.lookup(name) {
sym.function().is_some()
|| matches!(sym.value(), Some(Expr::Lambda(_, _)))
|| matches!(sym.kind(), SymbolKind::Function | SymbolKind::Macro)
pub(in crate::compiler::special) fn collect_setf_targets(
exprs: &[Expr],
) -> Vec<(String, Option<Expr>)> {
let mut targets = Vec::new();
for expr in exprs {
collect_setf_targets_inner(expr, &mut targets);
targets
fn collect_setf_targets_inner(expr: &Expr, targets: &mut Vec<(String, Option<Expr>)>) {
if let Expr::List(elems) = expr {
&& name == "SETF"
for pair in elems[1..].chunks(2) {
if let Some(Expr::Symbol(var)) = pair.first()
&& !targets.iter().any(|(n, _)| n == var)
targets.push((var.clone(), pair.get(1).cloned()));
for elem in elems {
collect_setf_targets_inner(elem, targets);
/// Eval-path mirror of [`promote_to_wasm_local`]: when a *runtime* loop body
/// `setf`s an OUTER variable, the loop's runtime iteration mutates it, but the
/// eval (const-fold) surface never runs that body, so the variable keeps its
/// stale const init. Mark each such target as a `WasmRuntime` placeholder of
/// its codegen-inferred type so the enclosing eval (an IF-test classification,
/// a defun's tail value) sees it as runtime — exactly what codegen's
/// accumulator promotion does. Idempotent: re-marking an already-runtime
/// target is a no-op, keeping the two-surface re-eval design sound.
pub(in crate::compiler::special) fn mark_runtime_setf_targets(
symbols: &mut SymbolTable,
exclude: &[&str],
) {
for (name, rhs) in collect_setf_targets(body) {
if exclude.contains(&name.as_str()) {
continue;
// Only re-type a var that is ALREADY bound in this scope — never
// synthesize a missing one. A `setf` to an undefined / nested-bound
// name is codegen's concern (`promote_to_wasm_local` errors on it); the
// eval mirror must not mask that by defining a spurious outer symbol.
let Some(current) = symbols.lookup(&name).and_then(|s| s.value().cloned()) else {
if matches!(current, Expr::WasmRuntime(_) | Expr::WasmLocal(_, _)) {
let ty = infer_wasm_type(¤t, rhs.as_ref(), symbols);
symbols.define(Symbol::new(&name, SymbolKind::Variable).with_value(Expr::WasmRuntime(ty)));
pub(in crate::compiler::special) fn promote_to_wasm_local(
ctx: &mut CompileContext,
emit: &mut FunctionEmitter,
name: &str,
) -> Result<()> {
let sym = symbols
.lookup(name)
.ok_or_else(|| Error::UndefinedSymbol(name.to_string()))?;
if matches!(
sym.value(),
Some(Expr::WasmLocal(_, _) | Expr::WasmRuntime(_))
return Ok(());
let val = sym.value().cloned().unwrap_or(Expr::Nil);
let ty = infer_wasm_type(&val, step_hint, symbols);
let idx = ctx.alloc_local(ty)?;
if matches!(ty, WasmType::PairRef(_)) && matches!(val, Expr::Nil) {
emit.ref_null(ctx.ids.ty_pair);
} else {
compile_for_stack(ctx, emit, symbols, &val)?;
emit.local_set(idx);
symbols.define(Symbol::new(name, SymbolKind::Variable).with_value(Expr::WasmLocal(idx, ty)));
Ok(())
pub(super) fn static_loop_terminates(
local: &SymbolTable,
end_test: &Expr,
sequential: bool,
) -> bool {
let mut sim = local.clone();
for _ in 0..MAX_STATIC_LOOP_ITERS {
match eval_value(&mut sim, end_test) {
Ok(test) if !test.is_nil() => return true,
Ok(_) => {}
Err(_) => return false,
if sequential {
for (name, step) in stepped {
let Some(s) = step else { continue };
match eval_value(&mut sim, s) {
Ok(val) => {
if let Some(sym) = sim.lookup_mut(name) {
sym.set_value(val);
let new_vals: Vec<_> = stepped
.iter()
.filter_map(|(name, step)| {
step.as_ref()
.and_then(|s| eval_value(&mut sim, s).ok().map(|v| (name.clone(), v)))
.collect();
for (name, val) in new_vals {
if let Some(sym) = sim.lookup_mut(&name) {
false