Lines
82.56 %
Functions
29.33 %
Branches
100 %
//! Runtime-type inference for the let-body's tail value.
//!
//! `infer_runtime_type_with_body` walks the body for an accumulator
//! `(setf <name> (cons V <name>))` and reads the cons car's
//! `PairElement` so the promoted runtime type matches what the codegen
//! path emits. The walker tracks `DOLIST` / `DO` / `LET` loop-var
//! bindings so nested setfs resolve their car symbol against the
//! right type. Without this, a wrong-shape fallback surfaces as a
//! `ref.cast` mismatch in downstream consumers.
use crate::ast::{Expr, PairElement, WasmType};
use crate::compiler::expr::eval_value;
use crate::runtime::{Symbol, SymbolKind, SymbolTable};
/// `elems[from..]`, never panicking on a malformed/short binder form: a `(do)`
/// / `(dolist)` / `(let)` with fewer than `from` elements yields an empty slice
/// rather than an out-of-range slice index. This walk is a best-effort
/// accumulator-type inference hint, so a too-short form simply has no body to
/// scan; the malformed form is rejected by the real binding-compile path later.
fn tail(elems: &[Expr], from: usize) -> &[Expr] {
elems.get(from..).unwrap_or(&[])
}
pub(super) fn infer_runtime_type(expr: &Expr) -> WasmType {
// Bytes share StringRef's `i8_array` representation but aren't a
// `compile_for_stack` literal, so they're classified here, not in the
// shared `classify_stack_type`.
if let Expr::Bytes(_) = expr {
return WasmType::StringRef;
match crate::compiler::expr::classify_stack_type(expr) {
Some(ty) => ty,
// For any remaining shape (List, Symbol, Quote, etc.) fall
// back to a generic PairRef. PairElement::I32 is the
// least-restrictive guess; downstream consumers refuse it
// explicitly when wrong, so a disagreement surfaces as a
// compile error rather than a runtime trap.
None => WasmType::PairRef(PairElement::I32),
/// Runtime local type for a let-var the body MUTATES via `setf`/`set!`, or
/// `None` if the var is never assigned. A const-initialized accumulator
/// (`(let ((acc 0)) … (setf acc …))` / `(let ((r nil)) … (setf r (cons …)))`)
/// must become a real wasm local so `setf` emits `local.set` — otherwise the
/// assignment takes the const eval-rebind path (no runtime wasm) and is lost
/// across loop scopes (a DO/dolist accumulator silently stays at its init). The
/// element type of a cons accumulator comes from the same setf walk the eval
/// path uses; any other assigned var sizes from its init value.
pub(super) fn assigned_var_runtime_type(
body: &[Expr],
name: &str,
init_val: &Expr,
symbols: &SymbolTable,
) -> Option<WasmType> {
if !body.iter().any(|form| form_assigns_var(form, name)) {
return None;
let mut env = symbols.clone();
if let Some(elem) = walk_for_setf_pair_element(body, name, &mut env) {
return Some(WasmType::PairRef(elem));
// The rhs isn't a CONS accumulator. Size the local from the FIRST `setf`
// rhs that resolves to a concrete RUNTIME type (e.g. `(setf out
// (get-input-entities))` or `(setf out (a-user-fn))` → PairRef) so it
// matches what the setf stores — a `nil` init / a `(setf out nil)` first
// store would otherwise size it as the falsy `Bool` (i32) and the later ref
// store would fail wasm validation. Each rhs is resolved on a CLONE — the
// same depth-guarded const-fold/inline the compiler uses for type inference
// everywhere, so a user-fn rhs is typed by its body's result type (not
// skipped) and a non-terminating recursion surfaces as an `Err` (skipped via
// `.ok()`), never a hang. Const / nil rhs (no runtime type) are skipped; if
// NO store yields a runtime type we fall back to the init's type. A
// genuinely conflicting second runtime store is left for codegen to reject
// (it owns the single local's type).
collect_setf_rhs(body, name)
.into_iter()
.find_map(|rhs| {
eval_value(&mut env.clone(), rhs)
.ok()
.and_then(|v| v.wasm_type())
})
.or_else(|| Some(infer_runtime_type(init_val)))
/// Every `(setf <name> rhs)` / `(set! <name> rhs)` rhs anywhere in `body`, in
/// source order (recursing into nested forms). Used by
/// [`assigned_var_runtime_type`] to size a setf-mutated local from its first
/// runtime-typed store when it is not a CONS accumulator.
fn collect_setf_rhs<'a>(body: &'a [Expr], name: &str) -> Vec<&'a Expr> {
let mut out = Vec::new();
collect_setf_rhs_into(body, name, &mut out);
out
fn collect_setf_rhs_into<'a>(body: &'a [Expr], name: &str, out: &mut Vec<&'a Expr>) {
for form in body {
let Expr::List(elems) = form else { continue };
if let Some(Expr::Symbol(head)) = elems.first()
&& (head == "SETF" || head == "SET!")
{
for pair in elems[1..].chunks(2) {
if let (Some(Expr::Symbol(place)), Some(rhs)) = (pair.first(), pair.get(1))
&& place == name
out.push(rhs);
// Don't descend into a binder that rebinds `name` — its body's setfs
// target a DIFFERENT (shadowing) variable.
if !binder_rebinds(elems, name) {
collect_setf_rhs_into(elems, name, out);
/// Recursively detects a `(setf <name> …)` / `(set! <name> …)` targeting
/// `name` anywhere in `form`, NOT descending into a sub-form that rebinds
/// `name` (its inner setfs target a shadowing variable).
fn form_assigns_var(form: &Expr, name: &str) -> bool {
let Expr::List(elems) = form else {
return false;
};
if let Some(Expr::Symbol(place)) = pair.first()
return true;
if binder_rebinds(elems, name) {
elems.iter().any(|e| form_assigns_var(e, name))
/// Whether the list form headed by `elems` binds `name` (a lambda param, or a
/// `let`/`let*`/`do`/`do*`/`dolist` variable), shadowing an enclosing binding.
/// Used to keep the setf-promotion scans from attributing a shadowed inner
/// assignment to the outer binding. Mirrors `lambda::param_infer`'s sibling.
fn binder_rebinds(elems: &[Expr], name: &str) -> bool {
let Some(Expr::Symbol(head)) = elems.first() else {
let in_specs = |spec: Option<&Expr>| {
matches!(spec, Some(Expr::List(items)) if items.iter().any(|b| match b {
Expr::Symbol(s) => s == name,
Expr::List(parts) => matches!(parts.first(), Some(Expr::Symbol(s)) if s == name),
_ => false,
}))
match head.to_ascii_uppercase().as_str() {
"LAMBDA" | "LET" | "LET*" | "DO" | "DO*" => in_specs(elems.get(1)),
"DOLIST" => matches!(
elems.get(1),
Some(Expr::List(spec)) if matches!(spec.first(), Some(Expr::Symbol(s)) if s == name)
),
/// When the body's tail returns a Symbol whose value flows from a
/// `(setf <name> (cons V <name>))` accumulator earlier in the body,
/// resolve the inferred runtime type by walking the body for that
/// setf and reading the cons car's PairElement. The walker tracks
/// dolist/do loop-var bindings so a setf nested inside a dolist
/// resolves the loop var's element type (e.g. `tag` inside `(dolist
/// (tag (entities-for ...)) ...)` resolves via the dolist's list
/// expression's PairElement). Without this, the cons car's symbol
/// would be unbound in the eval-time symbol table.
pub(super) fn infer_runtime_type_with_body(
val: &Expr,
result_expr: &Expr,
) -> WasmType {
if let Expr::Symbol(name) = result_expr {
return WasmType::PairRef(elem);
infer_runtime_type(val)
/// Walks `body` for `(setf <name> <rhs>)` and infers the matching
/// PairElement from the cons car of the rhs. Tracks DOLIST/DO/LET
/// loop-var bindings into `env` so nested setfs resolve their car
/// symbol against the right type.
fn walk_for_setf_pair_element(
target: &str,
env: &mut SymbolTable,
) -> Option<PairElement> {
if let Some(elem) = walk_form(form, target, env) {
return Some(elem);
None
fn walk_form(form: &Expr, target: &str, env: &mut SymbolTable) -> Option<PairElement> {
// A binder that rebinds `target` shadows it: any `(setf target …)` inside
// refers to the inner variable, not the accumulator we're typing.
if binder_rebinds(elems, target) {
let head = elems.first().and_then(|e| match e {
Expr::Symbol(s) => Some(s.as_str()),
_ => None,
});
match head {
Some("SETF") => {
if let Some(Expr::Symbol(var)) = pair.first()
&& var == target
&& let Some(rhs) = pair.get(1)
&& let Some(elem) = step_pair_element(rhs, env)
for e in &elems[1..] {
if let Some(found) = walk_form(e, target, env) {
return Some(found);
Some("DOLIST") => {
if let Some(Expr::List(var_spec)) = elems.get(1)
&& let Some(Expr::Symbol(var_name)) = var_spec.first()
&& let Some(list_expr) = var_spec.get(1)
let mut probe = env.clone();
if let Ok(list_val) = eval_value(&mut probe, list_expr)
&& let Some(WasmType::PairRef(elem)) = list_val.wasm_type()
env.define(
Symbol::new(var_name, SymbolKind::Variable)
.with_value(Expr::WasmRuntime(elem.as_wasm_type())),
);
for e in tail(elems, 2) {
Some("DO") | Some("DO*") => {
if let Some(Expr::List(vars)) = elems.get(1) {
for v in vars {
if let Expr::List(vparts) = v
&& let Some(Expr::Symbol(vname)) = vparts.first()
&& let Some(init) = vparts.get(1)
if let Ok(init_val) = eval_value(&mut probe, init) {
// A DO var is a RUNTIME value of the init's stack
// type, not the const init itself: an integer init
// (`(i 0 …)`) makes `i` a runtime Index (I32), so
// `(cons i …)` is an I32 cell. Binding the const `0`
// would resolve its pair element as Ratio (the
// numeric-literal cell slot) and mis-size the
// accumulator → a CAR ref.cast trap.
Symbol::new(vname, SymbolKind::Variable)
.with_value(Expr::WasmRuntime(infer_runtime_type(&init_val))),
for e in tail(elems, 3) {
Some("LET") | Some("LET*") => {
if let Some(Expr::List(bindings)) = elems.get(1) {
for b in bindings {
if let Expr::List(parts) = b
&& let Some(Expr::Symbol(bname)) = parts.first()
let init_val = match parts.get(1) {
Some(init) => {
eval_value(&mut probe, init).unwrap_or(Expr::Nil)
None => Expr::Nil,
env.define(Symbol::new(bname, SymbolKind::Variable).with_value(init_val));
_ => {
for e in elems {
/// Inline copy of `iteration::common::step_pair_element` to avoid a
/// cyclic `pub(super)` exposure. Same semantics: peeks at a CONS
/// expression's car and resolves the corresponding PairElement.
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(&elems[1], symbols)
elems.iter().find_map(|e| step_pair_element(e, symbols))
fn resolve_pair_element(expr: &Expr, symbols: &SymbolTable) -> Option<PairElement> {
match expr {
Expr::WasmRuntime(ty) | Expr::WasmLocal(_, ty) => PairElement::from_wasm_type(*ty),
// A numeric literal is a dimensionless Ratio (never a count), matching
// `list::infer::literal_pair_element` and `infer_runtime_type`.
Expr::Number(_) => Some(PairElement::Ratio),
Expr::Bool(_) => Some(PairElement::Bool),
Expr::Symbol(name) => {
let sym = symbols.lookup(name)?;
let value = sym.value()?;
resolve_pair_element(value, symbols)
// A host-fn / form car hasn't reduced to a runtime placeholder yet;
// eval on a CLONE so the accumulator element matches codegen. Admitted
// only when the whole car subtree is pure-native (no user-callable
// anywhere), so inference can't recurse into a (possibly
// non-terminating) user lambda — native handlers eval their args, so a
// top-level-head check alone wouldn't be enough.
Expr::List(_) if is_pure_native_expr(expr, symbols) => {
match eval_value(&mut symbols.clone(), expr).ok()? {
Expr::List(_) => None,
other => resolve_pair_element(&other, symbols),
/// Whether `expr` is safe to `eval_value` purely for type inference: it
/// contains NO user-callable anywhere. Native eval handlers recurse into their
/// args, and higher-order natives (MAP/FILTER/FOLD) invoke a function-valued
/// argument, so the check spans the whole tree — every call head must be a
/// native/operator (no user shadow) and every operand pure-native, and a bare
/// symbol is admitted only when it doesn't name a user function/lambda value.
/// Conservative: any non-inert shape is rejected. Mirrors
/// `iteration::common::is_pure_native_expr`.
fn is_pure_native_expr(expr: &Expr, symbols: &SymbolTable) -> bool {
Expr::Number(_)
| Expr::Bool(_)
| 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))
},
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 — passed to a
/// higher-order native it would be dereferenced and called during
/// `eval_value`, so it is NOT inert. Mirrors `iteration::common`'s sibling.
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)