candela/compiler/

type_system.rs

// This file is derived from keel (https://github.com/horacehoff/keel),
// Copyright 2026 Horace Hoff, licensed under the Apache License, Version 2.0.
// It has been modified by the candela authors. See the NOTICE file.
use super::expr::Expr;
use super::expr::METHOD_SEP;
use super::expr::Span;
use super::expr::UNARY_MINUS_METHOD;
use super::expr::is_operator_method;
use super::expr::is_unary_operator_method;
use super::expr::mangle_method;
use super::expr::operator_method;
use super::expr::self_operator_method;
use super::expr::symbol_of_expr;
use crate::compiler::FileNamespaces;
use crate::compiler::Namespace;
use crate::compiler::SymbolKind;
use crate::compiler::compiler_data::Ctx;
use crate::compiler::compiler_data::EnumType;
use crate::compiler::compiler_data::EnumVariant;
use crate::compiler::compiler_data::FnGenerics;
use crate::compiler::compiler_data::Function;
use crate::compiler::compiler_data::Source;
use crate::compiler::compiler_data::State;
use crate::compiler::compiler_data::Struct;
use crate::compiler::compiler_data::TypeNames;
use crate::compiler::compiler_data::Variable;
use crate::compiler::compiler_errors::error_instantiation_depth;
use crate::compiler::compiler_errors::error_invalid_obj_type;
use crate::compiler::compiler_errors::error_invalid_type;
use crate::compiler::compiler_errors::error_missing_return;
use crate::compiler::compiler_errors::error_op;
use crate::compiler::compiler_errors::error_operator_method;
use crate::compiler::compiler_errors::error_struct_default_signature;
use crate::compiler::compiler_errors::error_struct_unknown_field;
use crate::compiler::compiler_errors::error_type_arg_count;
use crate::compiler::compiler_errors::error_type_args_on_plain_function;
use crate::compiler::compiler_errors::error_type_args_on_plain_type;
use crate::compiler::compiler_errors::error_type_not_indexable;
use crate::compiler::compiler_errors::error_unknown_function;
use crate::compiler::compiler_errors::error_unknown_function_in_namespace;
use crate::compiler::compiler_errors::error_unknown_namespace;
use crate::compiler::compiler_errors::error_unknown_struct;
use crate::compiler::compiler_errors::error_unknown_type;
use crate::compiler::compiler_errors::error_unknown_type_param;
use crate::compiler::compiler_errors::error_unknown_type_with_namespace;
use crate::compiler::compiler_errors::error_unknown_variable;
use crate::compiler::expr::closure_free_names;
use crate::compiler::functions::Callee;
use crate::compiler::functions::reject_default_default;
use crate::compiler::functions::resolve_callee;
use crate::compiler::methods::check_receiver;
use crate::compiler::methods::infer_operator_method;
use crate::compiler::methods::reject_block_dot_call;
use crate::compiler::resolve_enum_variant;
use crate::rt::FnValue;
use rustc_hash::FxHashMap;
use rustc_hash::FxHashSet;
use smol_strc::SmolStr;
use smol_strc::ToSmolStr;
use std::cell::RefCell;
use std::hint::cold_path;
use std::hint::unreachable_unchecked;
use std::rc::Rc;

pub use crate::rt::DataType;

/// Name prefix for the synthetic top-level function an anonymous function is
/// hoisted to. `<` is not a legal identifier character, so a hoisted name can
/// never collide with a user-written function.
///
/// Public because a frontend reading the function table has to tell the
/// entries a person wrote from the ones the compiler made: an outline lists
/// the first and leaves out the second.
pub const ANON_FN_PREFIX: &str = "<anon>";

// Tracks which user-defined functions are currently being analysed for their
// return type. Used to break mutual-recursion cycles in type inference
thread_local! {
    static RETURN_TYPE_INFERRING: RefCell<FxHashSet<usize>> =
        RefCell::new(FxHashSet::default());
}

/// Clears inference bookkeeping left behind when a previous compilation on
/// this thread was aborted by an error unwind (see `errors::collect_diagnostic`).
pub fn reset_inference_state() {
    RETURN_TYPE_INFERRING.with(|s| s.borrow_mut().clear());
}

/// A declared `-> Type` return annotation with the span it was written at.
///
/// `None` leaves the return type inferred. Boxed because a declaration is
/// carried inside [`Expr`], where the annotation is the rarest field.
pub type ReturnAnnotation = Option<Box<(TypeExpr, Span)>>;

/// The type parameters a declaration introduces (`struct Cell<T>`), in the
/// order they were written. Empty for a declaration that takes none.
pub type TypeParams = Box<[SmolStr]>;

#[derive(Debug, PartialEq, Eq, Clone)]
pub enum TypeExpr {
    Identifier(SmolStr, Span),
    NamespacedIdentifier(Box<[SmolStr]>, Span),
    /// A generic type applied to its arguments, `Cell<int>`, with or without
    /// a module path in front of the name (`g::Slot<int>`).
    Generic(Box<GenericType>),
    Array(Box<Self>),
    Map(Box<Self>, Box<Self>),
    Union(Box<[Self]>),
    /// `fn(A, B) -> R`: a position that holds a function of that shape rather
    /// than one particular function. The return type is `None` where the arrow
    /// is left off, which is a function that hands nothing back.
    Fn(Box<FnTypeExpr>),
}

/// The parameter types and return type a `fn(...)` annotation was written with.
#[derive(Debug, PartialEq, Eq, Clone)]
pub struct FnTypeExpr {
    pub args: Box<[TypeExpr]>,
    pub return_type: Option<TypeExpr>,
    pub span: Span,
}

/// A generic type and the arguments it is applied to. Boxed inside
/// [`TypeExpr`], which every declaration carries by value.
#[derive(Debug, PartialEq, Eq, Clone)]
pub struct GenericType {
    /// The module path the name was written behind, empty for a name written
    /// on its own. A module bound with `as` puts its alias here
    /// (`g::Slot<int>`).
    pub namespace: Box<[SmolStr]>,
    pub name: SmolStr,
    pub args: Box<[TypeExpr]>,
    pub span: Span,
}

impl TypeExpr {
    /// Whether this type mentions any of `params`.
    ///
    /// An annotation that does is left un-pinned when the call site supplies no
    /// type arguments: candela infers such a parameter from the argument, the
    /// same as an un-annotated one.
    #[must_use]
    pub fn mentions_any(&self, params: &[SmolStr]) -> bool {
        match self {
            Self::Identifier(name, _) => params.contains(name),
            Self::NamespacedIdentifier(_, _) => false,
            Self::Fn(sig) => {
                sig.args.iter().any(|a| a.mentions_any(params))
                    || sig
                        .return_type
                        .as_ref()
                        .is_some_and(|r| r.mentions_any(params))
            }
            Self::Generic(generic) => {
                // A name written behind a module path names that module's
                // generic type, never a type parameter of the body being
                // compiled.
                (generic.namespace.is_empty() && params.contains(&generic.name))
                    || generic.args.iter().any(|a| a.mentions_any(params))
            }
            Self::Array(inner) => inner.mentions_any(params),
            Self::Map(k, val) => k.mentions_any(params) || val.mentions_any(params),
            Self::Union(poly) => poly.iter().any(|t| t.mentions_any(params)),
        }
    }

    #[must_use]
    pub fn to_datatype(&self, ctx: &mut TypeCtx<'_>) -> DataType {
        match self {
            Self::Identifier(s, span) => match s.as_str() {
                "int" => DataType::Int,
                "float" => DataType::Float,
                "bool" => DataType::Bool,
                "string" => DataType::String,
                "null" => DataType::Null,
                // A dynamically-typed slot. Written `any`; modeled as `Unknown`,
                // which the type checker already treats permissively. Used for
                // enum payloads that hold a value of any type (option/result).
                "any" => DataType::Unknown,
                struct_name => {
                    if let Some(bound) = ctx.generics.bound(struct_name) {
                        bound
                    } else if let Some(struct_id) =
                        ctx.scope()
                            .find_struct(&[], struct_name, *span, ctx.file_idx, ctx.sources)
                    {
                        DataType::Struct(struct_id as u16)
                    } else if let Some(enum_id) = ctx.scope().find_enum(&[], struct_name) {
                        DataType::Enum(enum_id as u16)
                    } else if find_template(&[], struct_name, ctx.scope(), ctx.generics).is_some() {
                        // A generic type named without its arguments is the
                        // dynamic slot: candela never makes a missing type
                        // argument an error.
                        DataType::Unknown
                    } else if ctx.generics.in_generic_body() {
                        error_unknown_type_param(
                            *span,
                            ctx.file_idx,
                            struct_name,
                            &ctx.generics.bound_names(),
                            ctx.sources,
                        );
                    } else {
                        error_unknown_type(
                            *span,
                            ctx.file_idx,
                            struct_name,
                            ctx.sources,
                            ctx.scope(),
                        );
                    }
                }
            },
            Self::NamespacedIdentifier(s, span) => {
                if let Some(struct_id) = ctx.scope().find_struct(
                    &s[..s.len() - 1],
                    unsafe { s.last().unwrap_unchecked() },
                    *span,
                    ctx.file_idx,
                    ctx.sources,
                ) {
                    DataType::Struct(struct_id as u16)
                } else if let Some(enum_id) = ctx
                    .scope()
                    .find_enum(&s[..s.len() - 1], unsafe { s.last().unwrap_unchecked() })
                {
                    DataType::Enum(enum_id as u16)
                } else {
                    cold_path();
                    error_unknown_type_with_namespace(
                        *span,
                        ctx.file_idx,
                        unsafe { s.last().unwrap_unchecked() },
                        ctx.sources,
                        ctx.scope(),
                        &s[..s.len() - 1],
                    )
                }
            }
            Self::Generic(generic) => {
                // The path in front of the name says which module the type
                // comes from, so a path that names no module is reported here
                // rather than resolving to whatever declared the name.
                if !generic.namespace.is_empty()
                    && ctx.scope().resolve(&generic.namespace).is_none()
                {
                    cold_path();
                    error_unknown_namespace(
                        &generic.namespace,
                        generic.span,
                        ctx.scope(),
                        ctx.file_idx,
                        ctx.sources,
                    );
                }
                let args: Vec<DataType> = generic.args.iter().map(|a| a.to_datatype(ctx)).collect();
                instantiate(&generic.namespace, &generic.name, &args, generic.span, ctx)
            }
            Self::Array(inner_t) => DataType::Array(Some(Box::new(inner_t.to_datatype(ctx)))),
            Self::Map(k_t, v_t) => DataType::Map(Box::from((
                Some(k_t.to_datatype(ctx)),
                Some(v_t.to_datatype(ctx)),
            ))),
            Self::Union(poly) => {
                DataType::Union(poly.iter().map(|t| t.to_datatype(ctx)).collect()).check_poly()
            }
            Self::Fn(sig) => DataType::FnValue(Box::new(FnValue {
                sig: Some((
                    sig.args.iter().map(|a| a.to_datatype(ctx)).collect(),
                    sig.return_type
                        .as_ref()
                        .map_or(DataType::Null, |r| r.to_datatype(ctx)),
                )),
                candidates: Box::from([]),
                set: None,
            })),
        }
    }
}

/// How deep one generic type may be instantiated inside another before the
/// compiler stops. A type whose own fields name a deeper instantiation of
/// itself (`struct L<T> { next: L<L<T>> }`) has no finite set of
/// instantiations, and this is where that is reported instead of hanging.
const MAX_INSTANTIATION_DEPTH: u32 = 32;

/// What a declaration of a generic type keeps: its parameters and the field or
/// variant types they appear in, unresolved. Substituting the parameters and
/// resolving the result is what [`instantiate`] does.
#[derive(Debug)]
struct TypeTemplate {
    name: SmolStr,
    params: TypeParams,
    /// File the declaration was written in; its field types resolve against
    /// that file's namespace whatever file the instantiation is written in.
    file_idx: u16,
    body: TemplateBody,
    /// The `= value` each field of a struct template was declared with, empty
    /// when none was; handed to every instantiation.
    defaults: Box<[Option<(Expr, Span)>]>,
}

/// The `= value` a struct's fields were declared with, and the file the
/// declaration was written in, which is the scope the values compile in.
#[derive(Debug, Clone)]
pub struct StructDefaults {
    pub file_idx: u16,
    /// One entry per field, `None` for a field declared without a value, with
    /// the span the value was written at.
    pub values: Box<[Option<(Expr, Span)>]>,
}

/// One type made from a generic declaration: which declaration, the name it is
/// registered under, the type it became, and the arguments it was made with.
/// The arguments are what lets an instantiation left open (`Option<any>`) be
/// recognised as the same declaration as `Option<P>`.
#[derive(Debug)]
struct Instantiation {
    template: usize,
    name: SmolStr,
    instantiated: DataType,
    args: Box<[DataType]>,
}

#[derive(Debug, Clone)]
enum TemplateBody {
    Struct(Box<[(SmolStr, TypeExpr, Span)]>),
    Enum(Box<[(SmolStr, Box<[TypeExpr]>, Span)]>),
}

/// An `impl` block written against a generic type, kept until the type is
/// instantiated.
///
/// `args` is the header as written: `impl Cell<T>` applies to every
/// instantiation and binds `T`, `impl Cell<int>` applies to that one.
#[derive(Debug)]
pub struct ImplTemplate {
    pub type_name: SmolStr,
    pub args: Box<[TypeExpr]>,
    /// The methods, as [`Expr::FunctionDecl`] carrying the plain method name.
    /// The name is mangled per instantiated type when the block is lowered.
    pub methods: Box<[Expr]>,
    pub file_idx: u16,
    pub span: Span,
}

/// The type parameters in scope while one body is compiled.
///
/// `named` are the ones the call site's type arguments and the enclosing `impl`
/// block fixed. `unnamed` are the parameters neither of them mentions: they
/// stand for `any`, so a body that writes such a parameter in a type position
/// compiles instead of reporting a type that has no value yet. The two are kept
/// apart because an annotation mentioning an unnamed parameter stays un-pinned:
/// what the body returns is inferred rather than checked against `any`.
#[derive(Debug, Default)]
pub struct BindingFrame {
    named: Box<[(SmolStr, DataType)]>,
    unnamed: Box<[SmolStr]>,
}

impl BindingFrame {
    /// A frame in which every parameter is fixed to a type, which is what an
    /// `impl` block and a generic instantiation produce.
    #[must_use]
    pub fn all_named(named: Box<[(SmolStr, DataType)]>) -> Self {
        Self {
            named,
            unnamed: Box::from([]),
        }
    }

    fn is_empty(&self) -> bool {
        self.named.is_empty() && self.unnamed.is_empty()
    }
}

/// The generic declarations of a program, the instantiations made from them,
/// and the type parameters bound while a body is being compiled.
#[derive(Debug, Default)]
pub struct Generics {
    templates: Vec<TypeTemplate>,
    impls: Vec<ImplTemplate>,
    /// Instantiations by the declaration they came from, their rendered name
    /// and the arguments they were made with, so `Cell<int>` written twice is
    /// one struct and two modules each declaring `Cell<T>` keep their own.
    /// `<` and `>` cannot occur in an identifier, so a rendered name never
    /// collides with a user-written one.
    instantiations: Vec<Instantiation>,
    /// Type parameters bound for the body being compiled. Only the top frame is
    /// in scope: the parameters of a function never reach the body of a
    /// function it calls.
    bindings: Vec<BindingFrame>,
    depth: u32,
    /// The declared field values of every struct that has any, by struct id.
    /// Kept here because this table travels with every compile against a
    /// program, and an instantiation of a generic struct adds to it.
    struct_defaults: FxHashMap<u16, StructDefaults>,
    /// The templates the prelude registered. A program's own declaration of a
    /// name the prelude also declares is the one a bare name reaches, wherever
    /// the two were registered relative to each other.
    prelude_templates: std::ops::Range<usize>,
    /// The files that are prelude modules, whether the prelude loaded them or
    /// a program imported one by name first. Their templates are bare names
    /// everywhere.
    prelude_files: Vec<u16>,
}

impl Generics {
    /// How many generic declarations are registered.
    #[must_use]
    pub const fn template_count(&self) -> usize {
        self.templates.len()
    }

    /// Records that file `file_idx` is a prelude module.
    pub fn mark_prelude_file(&mut self, file_idx: u16) {
        self.prelude_files.push(file_idx);
    }

    /// Records which templates the prelude registered.
    pub const fn set_prelude_templates(&mut self, range: std::ops::Range<usize>) {
        self.prelude_templates = range;
    }

    /// The last-registered template `matches` accepts, a program's own before
    /// the prelude's.
    fn last_template_where(&self, matches: impl Fn(&TypeTemplate) -> bool) -> Option<usize> {
        let prelude = &self.prelude_templates;
        self.templates
            .iter()
            .enumerate()
            .rev()
            .find(|(i, t)| !prelude.contains(i) && matches(t))
            .or_else(|| {
                self.templates
                    .iter()
                    .enumerate()
                    .rev()
                    .find(|(i, t)| prelude.contains(i) && matches(t))
            })
            .map(|(i, _)| i)
    }

    /// The type this name is currently bound to, if it names a type parameter
    /// of the body being compiled. A parameter nothing named is `any`.
    #[must_use]
    pub fn bound(&self, name: &str) -> Option<DataType> {
        let frame = self.bindings.last()?;
        frame
            .named
            .iter()
            .find(|(param, _)| param == name)
            .map(|(_, t)| t.clone())
            .or_else(|| {
                frame
                    .unnamed
                    .iter()
                    .any(|param| param == name)
                    .then_some(DataType::Unknown)
            })
    }

    /// Whether the call site or an enclosing `impl` block fixed this type
    /// parameter to a type, as opposed to leaving it standing for `any`. An
    /// annotation that mentions a parameter nothing named stays un-pinned.
    #[must_use]
    pub fn names(&self, name: &str) -> bool {
        self.bindings
            .last()
            .is_some_and(|frame| frame.named.iter().any(|(param, _)| param == name))
    }

    /// Whether any type parameter is in scope, which is what makes an unknown
    /// type name worth reporting as a type parameter rather than a type.
    #[must_use]
    fn in_generic_body(&self) -> bool {
        self.bindings.last().is_some_and(|frame| !frame.is_empty())
    }

    fn bound_names(&self) -> Vec<SmolStr> {
        self.bindings
            .last()
            .map(|frame| {
                frame
                    .named
                    .iter()
                    .map(|(p, _)| p.clone())
                    .chain(frame.unnamed.iter().cloned())
                    .collect()
            })
            .unwrap_or_default()
    }

    /// The parameters of the generic declaration `name` names, for a caller
    /// with no scope to resolve it in: a mangled method name
    /// (`Cell<int>#get`) carries the type name and no module path. Takes the
    /// declaration registered last when two modules declare the name.
    #[must_use]
    pub fn params_of(&self, name: &str) -> Option<&[SmolStr]> {
        self.last_template_where(|t| t.name == name)
            .map(|i| &*self.templates[i].params)
    }

    /// Records the values the fields of struct `id` were declared with,
    /// replacing whatever an earlier struct of that id left, so an id reused
    /// after a rollback starts clean.
    pub fn set_struct_defaults(
        &mut self,
        id: u16,
        file_idx: u16,
        values: Box<[Option<(Expr, Span)>]>,
    ) {
        if values.iter().any(Option::is_some) {
            self.struct_defaults
                .insert(id, StructDefaults { file_idx, values });
        } else {
            self.struct_defaults.remove(&id);
        }
    }

    /// The value field `field` of struct `id` was declared with, and the file
    /// it was written in.
    #[must_use]
    pub fn struct_default(&self, id: u16, field: usize) -> Option<(u16, &Expr, Span)> {
        let defaults = self.struct_defaults.get(&id)?;
        defaults
            .values
            .get(field)
            .and_then(Option::as_ref)
            .map(|(value, span)| (defaults.file_idx, value, *span))
    }

    /// For each type parameter of a struct template, the field declared with
    /// that parameter as its type. A literal written without type arguments
    /// takes each parameter from the value in that field.
    #[must_use]
    pub fn param_fields(&self, template_idx: usize) -> Vec<Option<SmolStr>> {
        let Some(template) = self.templates.get(template_idx) else {
            return Vec::new();
        };
        let TemplateBody::Struct(fields) = &template.body else {
            return vec![None; template.params.len()];
        };
        template
            .params
            .iter()
            .map(|param| {
                fields
                    .iter()
                    .find(|(_, field_type, _)| {
                        matches!(field_type, TypeExpr::Identifier(t, _) if t == param)
                    })
                    .map(|(field_name, _, _)| field_name.clone())
            })
            .collect()
    }

    /// The generic declaration the last-registered template under `name` is,
    /// which is what an unqualified name falls back to when the scope it was
    /// written in registers no template by that name.
    ///
    /// A template a program file declares is reached only through a scope,
    /// so a module's `Slot<T>` is not a bare name in a file that bound the
    /// module under a namespace. What is left is the prelude's, however its
    /// module was loaded, and any registered after it, while a body was being
    /// compiled.
    fn last_template_named(&self, name: &str) -> Option<usize> {
        let in_prelude = |i: usize| self.prelude_files.contains(&self.templates[i].file_idx);
        let reachable = |i: usize| {
            self.templates[i].name == name && (i >= self.prelude_templates.start || in_prelude(i))
        };
        (0..self.templates.len())
            .rev()
            .find(|&i| reachable(i) && !in_prelude(i))
            .or_else(|| (0..self.templates.len()).rev().find(|&i| reachable(i)))
    }

    /// The declaration an instantiated type came from and the arguments it was
    /// made with, for a type that came from one.
    #[must_use]
    pub fn instantiation_of(&self, t: &DataType) -> Option<(usize, &[DataType])> {
        if !matches!(t, DataType::Struct(_) | DataType::Enum(_)) {
            return None;
        }
        self.instantiations
            .iter()
            .find(|i| &i.instantiated == t)
            .map(|i| (i.template, &*i.args))
    }

    /// The generic enum declaration that declares a variant of this name, and
    /// the payload types the variant declares.
    ///
    /// A generic enum has no registered type until something names one, so a
    /// bare `Some(x)` is looked up here rather than among the enums already
    /// registered. The last declaration of the name wins, the same as
    /// [`find_template`] does for a type name.
    #[must_use]
    pub fn enum_template_with_variant(&self, variant: &str) -> Option<usize> {
        self.last_template_where(|t| match &t.body {
            TemplateBody::Enum(variants) => variants.iter().any(|(name, _, _)| name == variant),
            TemplateBody::Struct(_) => false,
        })
    }

    /// Whether the only generic enums declaring a variant called `variant` are
    /// the prelude's.
    #[must_use]
    pub fn only_the_prelude_declares(&self, variant: &str) -> bool {
        self.enum_template_with_variant(variant)
            .is_some_and(|template| self.prelude_templates.contains(&template))
    }

    /// The payload a variant of a generic enum declares, unresolved.
    #[must_use]
    fn variant_payload(&self, template: usize, variant: &str) -> Option<&[TypeExpr]> {
        let TemplateBody::Enum(variants) = &self.templates[template].body else {
            return None;
        };
        variants
            .iter()
            .find(|(name, _, _)| name == variant)
            .map(|(_, payload, _)| &**payload)
    }

    /// The parameters a generic declaration takes.
    #[must_use]
    fn params(&self, template: usize) -> &[SmolStr] {
        &self.templates[template].params
    }

    /// The name a generic declaration was written under.
    #[must_use]
    fn template_name(&self, template: usize) -> &SmolStr {
        &self.templates[template].name
    }

    /// The file a generic declaration was written in.
    #[must_use]
    fn template_file(&self, template: usize) -> u16 {
        self.templates[template].file_idx
    }

    /// Records a generic `struct` declaration and returns the index the
    /// declaring scope registers it under, which is what a name written
    /// behind a module path resolves to.
    pub fn add_struct_template(
        &mut self,
        name: SmolStr,
        params: TypeParams,
        file_idx: u16,
        fields: Box<[(SmolStr, TypeExpr, Span)]>,
        defaults: Box<[Option<(Expr, Span)>]>,
    ) -> u32 {
        self.templates.push(TypeTemplate {
            name,
            params,
            file_idx,
            body: TemplateBody::Struct(fields),
            defaults,
        });
        (self.templates.len() - 1) as u32
    }

    /// Records a generic `enum` declaration. Returns its index, as
    /// [`Generics::add_struct_template`] does.
    pub fn add_enum_template(
        &mut self,
        name: SmolStr,
        params: TypeParams,
        file_idx: u16,
        variants: Box<[(SmolStr, Box<[TypeExpr]>, Span)]>,
    ) -> u32 {
        self.templates.push(TypeTemplate {
            name,
            params,
            file_idx,
            body: TemplateBody::Enum(variants),
            defaults: Box::from([]),
        });
        (self.templates.len() - 1) as u32
    }

    /// Records the `impl` blocks a file declared against a generic type,
    /// stamping each with the file it came from.
    /// Whether any `impl` block the program has read defines an operator,
    /// which makes an operator on that type a call to candela code.
    #[must_use]
    pub fn defines_operator_methods(&self) -> bool {
        self.impls.iter().any(|block| {
            block.methods.iter().any(|method| {
                matches!(method, Expr::FunctionDecl(name, ..) if operator_method(name).is_some())
            })
        })
    }

    pub fn add_impls(&mut self, impls: Vec<ImplTemplate>, file_idx: u16) {
        self.impls.extend(impls.into_iter().map(|mut block| {
            block.file_idx = file_idx;
            block
        }));
    }

    /// The path a receiverless function `name` of generic declaration
    /// `template` is called by, `Set<T>::new()`, when an `impl` block on it
    /// declares one.
    #[must_use]
    pub fn path_fn_of_template(&self, template: usize, name: &str) -> Option<String> {
        let decl = &self.templates[template];
        self.impls
            .iter()
            .filter(|block| impl_base_name(&block.type_name) == decl.name.as_str())
            .flat_map(|block| block.methods.iter())
            .any(|method| {
                matches!(method, Expr::FunctionDecl(fn_name, args, ..)
                    if fn_name == name && args.is_empty())
            })
            .then(|| format!("{}<{}>::{name}()", decl.name, decl.params.join(", ")))
    }

    /// Binds `frame` for the body about to be compiled. Every body pushes a
    /// frame, an empty one when it has no type parameters, so the caller's
    /// parameters do not resolve inside it.
    pub fn push_bindings(&mut self, frame: Box<[(SmolStr, DataType)]>) {
        self.bindings.push(BindingFrame::all_named(frame));
    }

    /// Binds a frame that also carries the parameters nothing named, which a
    /// function specialisation has and an `impl` block does not.
    pub fn push_frame(&mut self, frame: BindingFrame) {
        self.bindings.push(frame);
    }

    pub fn pop_bindings(&mut self) {
        self.bindings.pop();
    }

    /// Snapshots the state a single generic instantiation (or a function
    /// specialization's own type-parameter frame) can grow or unbalance, so an
    /// aborted compile attempt can undo it with [`Generics::rollback_to`].
    ///
    /// `instantiations` and the structs/enums it names are a cache: an
    /// `instantiate` call registers the pair before the instantiation's own
    /// fields are resolved, so a type whose fields name itself resolves to the
    /// type being built instead of recursing. A diagnostic raised while
    /// resolving those fields (or while lowering an `impl` block against the
    /// instantiation, which pushes its lowered methods the same way a closure
    /// literal pushes an anonymous function) leaves the cache entry pointing at
    /// a struct or enum whose fields were never filled in. `bindings` and
    /// `depth` are pushed and incremented, respectively, before that same
    /// resolution and are only popped or decremented after it returns; a
    /// `push_bindings` without a matching `pop_bindings` (function
    /// specialization has its own such pair too, see
    /// `functions/user_functions.rs`) leaks a frame, and an unmatched `depth`
    /// increment eventually trips the instantiation-depth cap for programs
    /// nowhere near it.
    #[must_use]
    pub const fn checkpoint(&self) -> GenericsCheckpoint {
        GenericsCheckpoint {
            instantiations: self.instantiations.len(),
            bindings: self.bindings.len(),
            depth: self.depth,
        }
    }

    /// Undoes everything a failed compile attempt did to the instantiation
    /// cache and the binding/depth bookkeeping, back to `checkpoint`. The
    /// structs and enums an aborted `instantiate` call registered are not
    /// `Generics`' to remove; the caller truncates those (see
    /// `Program::rollback_to`) using the same pre-attempt lengths.
    pub fn rollback_to(&mut self, checkpoint: &GenericsCheckpoint) {
        self.instantiations.truncate(checkpoint.instantiations);
        self.bindings.truncate(checkpoint.bindings);
        self.depth = checkpoint.depth;
    }
}

/// A checkpoint of the [`Generics`] state taken by [`Generics::checkpoint`] and
/// undone by [`Generics::rollback_to`].
pub struct GenericsCheckpoint {
    instantiations: usize,
    bindings: usize,
    depth: u32,
}

/// What resolving a [`TypeExpr`] needs: the scope the type is written in, and
/// the registries an instantiation adds to.
pub struct TypeCtx<'a> {
    pub file_idx: u16,
    pub namespaces: &'a FileNamespaces,
    pub sources: &'a [Source],
    pub structs: &'a mut Vec<Struct>,
    pub enums: &'a mut Vec<EnumType>,
    pub fns: &'a mut Vec<Function>,
    pub generics: &'a mut Generics,
}

impl<'a> TypeCtx<'a> {
    /// The scope the type being resolved is written in.
    #[must_use]
    pub fn scope(&self) -> &'a Namespace {
        self.namespaces.get(self.file_idx)
    }
    /// The same registries, resolving names in another file's scope. A
    /// declaration resolves its own types where it was written, whatever file
    /// the use is written in.
    pub const fn reborrow(&mut self, file_idx: u16) -> TypeCtx<'_> {
        TypeCtx {
            file_idx,
            namespaces: self.namespaces,
            sources: self.sources,
            structs: self.structs,
            enums: self.enums,
            fns: self.fns,
            generics: self.generics,
        }
    }
}

/// Renders `t` as the name an instantiation is registered under.
///
/// The name comes from the resolved type, never from the source text, so two
/// spellings of one type give one instantiation and two types can never give
/// the same name.
#[must_use]
fn render_type(t: &DataType, structs: &[Struct], enums: &[EnumType]) -> SmolStr {
    match t {
        DataType::Int => SmolStr::new_static("int"),
        DataType::Float => SmolStr::new_static("float"),
        DataType::Bool => SmolStr::new_static("bool"),
        DataType::String => SmolStr::new_static("string"),
        DataType::Null => SmolStr::new_static("null"),
        DataType::Unknown => SmolStr::new_static("any"),
        DataType::FnValue(sig) => sig.to_smolstr(),
        DataType::Array(inner) => match inner {
            Some(inner) => format_args!("{}[]", render_type(inner, structs, enums)).to_smolstr(),
            None => SmolStr::new_static("any[]"),
        },
        DataType::Map(m) => format_args!(
            "{{{}: {}}}",
            m.0.as_ref().map_or_else(
                || SmolStr::new_static("any"),
                |k| render_type(k, structs, enums)
            ),
            m.1.as_ref().map_or_else(
                || SmolStr::new_static("any"),
                |val| render_type(val, structs, enums)
            )
        )
        .to_smolstr(),
        DataType::Union(poly) => poly
            .iter()
            .map(|t| render_type(t, structs, enums))
            .collect::<Vec<SmolStr>>()
            .join("|")
            .into(),
        DataType::Struct(id) => structs[*id as usize].name.clone(),
        DataType::Enum(id) => enums[*id as usize].name.clone(),
        DataType::Fn(id) => format_args!("fn:{id}").to_smolstr(),
    }
}

/// The name a generic type is registered under once its arguments are known.
///
/// `qualifier` is the module the declaration was written in, present only when
/// another module declares a generic type by the same name. Two such types are
/// separate types, and the name is what a diagnostic prints and what a method
/// on the type is mangled under, so both have to say which module they came
/// from.
#[must_use]
fn render_instantiation(
    qualifier: Option<&str>,
    base: &str,
    args: &[DataType],
    structs: &[Struct],
    enums: &[EnumType],
) -> SmolStr {
    let rendered = args
        .iter()
        .map(|a| render_type(a, structs, enums))
        .collect::<Vec<SmolStr>>()
        .join(", ");
    match qualifier {
        Some(module) => format_args!("{module}::{base}<{rendered}>").to_smolstr(),
        None => format_args!("{base}<{rendered}>").to_smolstr(),
    }
}

/// The path segments a file is known by: its path with the `.cdl` taken off,
/// split on the directory separator, which is what an `import` writes.
#[must_use]
fn module_segments(file_idx: u16, sources: &[Source]) -> Vec<&str> {
    let Some(source) = sources.get(file_idx as usize) else {
        return Vec::new();
    };
    let path: &str = source
        .filename
        .strip_suffix(".cdl")
        .unwrap_or(&source.filename);
    path.split(['/', '\\']).filter(|s| !s.is_empty()).collect()
}

/// The module prefix a type declared in `file_idx` takes when the modules in
/// `declarers` declare that name too: the fewest trailing path segments that
/// tell this file apart from the others. One `plain.cdl` gives `plain`; two of
/// them, one per package, give `strutil::plain` and `sqlite::plain`, so a
/// qualified name is one type and no more.
#[must_use]
fn module_qualifier(file_idx: u16, declarers: &[u16], sources: &[Source]) -> SmolStr {
    let mine = module_segments(file_idx, sources);
    let others: Vec<Vec<&str>> = declarers
        .iter()
        .filter(|other| **other != file_idx)
        .map(|other| module_segments(*other, sources))
        .collect();
    for take in 1..=mine.len() {
        let tail = &mine[mine.len() - take..];
        if others
            .iter()
            .all(|other| other.len() < take || &other[other.len() - take..] != tail)
        {
            return tail.join("::").into();
        }
    }
    mine.join("::").into()
}

/// Puts the declaring module in front of every plain `struct` or `enum` name
/// that more than one module declares, so a package's types never collide with
/// a consumer's types of the same name.
///
/// Plain types share one program-wide table keyed by name, and a method lowers
/// to a free function named after its type (`Plain#get`), so two modules each
/// declaring `Plain` leave one `Plain#get` answering calls on both. The name a
/// duplicate is registered under becomes `right::Plain`, which is what a
/// diagnostic prints and what a method on it is mangled under; a generic type
/// two modules declare is qualified the same way, see `render_instantiation`.
/// A name only one module declares is left as it was written.
///
/// Every `impl` method is re-mangled against the name its receiver ended up
/// with, resolved in the scope the `impl` block was written in, and so are the
/// calls a method makes on its own receiver, which the recursion check reads.
pub fn qualify_duplicate_type_names(
    structs: &mut [Struct],
    enums: &mut [EnumType],
    fns: &mut [Function],
    struct_files: &[(u16, u16)],
    enum_files: &[(u16, u16)],
    namespaces: &FileNamespaces,
    sources: &[Source],
) {
    // The modules that declare each name. A struct and an enum of one name are
    // as much two types as two structs are: both mangle their methods against
    // that one name.
    let mut declarers: FxHashMap<SmolStr, Vec<u16>> = FxHashMap::default();
    for (name, file_idx) in struct_files
        .iter()
        .filter_map(|(id, file_idx)| Some((&structs.get(*id as usize)?.name, *file_idx)))
        .chain(
            enum_files
                .iter()
                .filter_map(|(id, file_idx)| Some((&enums.get(*id as usize)?.name, *file_idx))),
        )
    {
        declarers.entry(name.clone()).or_default().push(file_idx);
    }
    if declarers.values().all(|files| files.len() <= 1) {
        return;
    }

    for &(struct_id, file_idx) in struct_files {
        let Some(declared) = structs.get_mut(struct_id as usize) else {
            continue;
        };
        if let Some(files) = declarers.get(&declared.name)
            && files.len() > 1
        {
            declared.name = qualified_type_name(file_idx, files, &declared.name, sources);
        }
    }
    for &(enum_id, file_idx) in enum_files {
        let Some(declared) = enums.get_mut(enum_id as usize) else {
            continue;
        };
        if let Some(files) = declarers.get(&declared.name)
            && files.len() > 1
        {
            declared.name = qualified_type_name(file_idx, files, &declared.name, sources);
        }
    }

    for func in fns.iter_mut() {
        let scope = namespaces.get(func.src_file);
        if let Some(mangled) = requalify_method(&func.name, scope, structs, enums) {
            func.name = mangled;
        }
        for callee in &mut func.direct_calls {
            if let Some(mangled) = requalify_method(callee, scope, structs, enums) {
                *callee = mangled;
            }
        }
    }
}

/// The name a type declared in `file_idx` is registered under once the modules
/// in `declarers` declare that name too.
#[must_use]
fn qualified_type_name(
    file_idx: u16,
    declarers: &[u16],
    name: &str,
    sources: &[Source],
) -> SmolStr {
    format_args!("{}::{name}", module_qualifier(file_idx, declarers, sources)).to_smolstr()
}

/// The mangled symbol a method ends up with, when the type its `impl` block
/// named was qualified. `None` when `name` is not a method, when the type it
/// names is not a plain type in `scope` (a builtin receiver, or a generic
/// instantiation, which carries its own qualifier already), or when that type
/// kept the name it was written with.
#[must_use]
fn requalify_method(
    name: &str,
    scope: &Namespace,
    structs: &[Struct],
    enums: &[EnumType],
) -> Option<SmolStr> {
    let (type_name, method) = name.split_once(METHOD_SEP)?;
    let declared = scope.symbols.iter().find_map(|(symbol, kind)| {
        if symbol.as_str() != type_name {
            return None;
        }
        match kind {
            SymbolKind::Struct(id) => structs.get(*id as usize).map(|s| &s.name),
            SymbolKind::Enum(id) => enums.get(*id as usize).map(|e| &e.name),
            SymbolKind::Fn(_) | SymbolKind::Template(_) => None,
        }
    })?;
    (declared != type_name).then(|| mangle_method(declared, method))
}

/// The generic declaration `namespace::name` names, as an index into
/// `Generics::templates`.
///
/// A name written behind a module path resolves only to the declaration that
/// module makes, so two modules each declaring `Slot<T>` stay apart. A name
/// written on its own resolves in the scope it was written in, which holds the
/// file's own declarations and the ones its bare imports merged in; when that
/// scope has none it falls back to the last declaration of the name anywhere
/// in the program, which is where a name reaches a template registered while a
/// body was being compiled.
#[must_use]
pub fn find_template(
    namespace: &[SmolStr],
    name: &str,
    scope: &Namespace,
    generics: &Generics,
) -> Option<usize> {
    scope.find_template(namespace, name).or_else(|| {
        namespace
            .is_empty()
            .then(|| generics.last_template_named(name))
            .flatten()
    })
}

/// Resolves `base<args>` to an ordinary struct or enum, registering it the
/// first time it is asked for.
///
/// Past this point nothing generic is left: the instantiation is a concrete
/// type with concrete field types, and every later stage (field access, method
/// dispatch, the artifact codec, the VM) treats it like any other.
pub fn instantiate(
    namespace: &[SmolStr],
    base: &str,
    args: &[DataType],
    span: Span,
    ctx: &mut TypeCtx<'_>,
) -> DataType {
    let Some(template_idx) = find_template(namespace, base, ctx.scope(), ctx.generics) else {
        if ctx
            .scope()
            .find_struct(namespace, base, span, ctx.file_idx, ctx.sources)
            .is_some()
            || ctx.scope().find_enum(namespace, base).is_some()
        {
            error_type_args_on_plain_type(span, ctx.file_idx, base, ctx.sources);
        }
        if !namespace.is_empty() {
            error_unknown_type_with_namespace(
                span,
                ctx.file_idx,
                base,
                ctx.sources,
                ctx.scope(),
                namespace,
            );
        }
        error_unknown_type(span, ctx.file_idx, base, ctx.sources, ctx.scope());
    };
    // Another module declaring the same name makes the two separate types, and
    // the name has to say so; see `render_instantiation`.
    let declarers: Vec<u16> = ctx
        .generics
        .templates
        .iter()
        .filter(|t| t.name == base)
        .map(|t| t.file_idx)
        .collect();
    let qualifier = (declarers.len() > 1).then(|| {
        module_qualifier(
            ctx.generics.templates[template_idx].file_idx,
            &declarers,
            ctx.sources,
        )
    });
    let name = render_instantiation(qualifier.as_deref(), base, args, ctx.structs, ctx.enums);
    if let Some(existing) = ctx
        .generics
        .instantiations
        .iter()
        .find(|i| i.template == template_idx && i.name == name)
    {
        return existing.instantiated.clone();
    }
    if ctx.generics.templates[template_idx].params.len() != args.len() {
        error_type_arg_count(
            span,
            ctx.file_idx,
            base,
            ctx.generics.templates[template_idx].params.len(),
            args.len(),
            ctx.sources,
        );
    }
    if ctx.generics.depth >= MAX_INSTANTIATION_DEPTH {
        error_instantiation_depth(span, ctx.file_idx, base, ctx.sources);
    }

    let template_file = ctx.generics.templates[template_idx].file_idx;
    let frame: Box<[(SmolStr, DataType)]> = ctx.generics.templates[template_idx]
        .params
        .iter()
        .cloned()
        .zip(args.iter().cloned())
        .collect();

    // The instantiation is registered and cached before its own field types are
    // resolved, so a type whose fields name it resolves to the type being built
    // instead of instantiating it again.
    let is_struct = matches!(
        ctx.generics.templates[template_idx].body,
        TemplateBody::Struct(_)
    );
    let instantiated = if is_struct {
        let id = ctx.structs.len() as u16;
        ctx.structs.push(Struct {
            name: name.clone(),
            fields: Box::from([]),
            id,
            name_span: span,
        });
        let defaults = ctx.generics.templates[template_idx].defaults.clone();
        ctx.generics
            .set_struct_defaults(id, template_file, defaults);
        DataType::Struct(id)
    } else {
        let id = ctx.enums.len() as u16;
        ctx.enums.push(EnumType {
            name: name.clone(),
            variants: Box::from([]),
            id,
            name_span: span,
        });
        DataType::Enum(id)
    };
    ctx.generics.instantiations.push(Instantiation {
        template: template_idx,
        name: name.clone(),
        instantiated: instantiated.clone(),
        args: args.into(),
    });

    let body = ctx.generics.templates[template_idx].body.clone();
    ctx.generics.depth += 1;
    ctx.generics.push_bindings(frame.clone());
    {
        let mut inner = ctx.reborrow(template_file);
        match body {
            TemplateBody::Struct(fields) => {
                let resolved = fields
                    .iter()
                    .map(|(field_name, field_type, field_span)| {
                        (
                            field_name.clone(),
                            field_type.to_datatype(&mut inner),
                            *field_span,
                        )
                    })
                    .collect();
                if let DataType::Struct(id) = instantiated {
                    inner.structs[id as usize].fields = resolved;
                }
            }
            TemplateBody::Enum(variants) => {
                let resolved = variants
                    .iter()
                    .map(|(variant_name, payload, name_span)| EnumVariant {
                        name: variant_name.clone(),
                        payload: payload.iter().map(|t| t.to_datatype(&mut inner)).collect(),
                        name_span: *name_span,
                    })
                    .collect();
                if let DataType::Enum(id) = instantiated {
                    inner.enums[id as usize].variants = resolved;
                }
            }
        }
    }
    ctx.generics.pop_bindings();

    lower_impls(template_idx, base, args, &name, &frame, ctx);
    ctx.generics.depth -= 1;

    instantiated
}

/// Lowers every `impl` block that applies to a freshly instantiated type.
///
/// A generic block (`impl Cell<T>`) binds its parameters from the
/// instantiation's arguments; a concrete one (`impl Cell<int>`) applies only
/// when the arguments match. Each method becomes an ordinary free function
/// named `Cell<int>#get`, exactly as a method on a plain type does.
fn lower_impls(
    template_idx: usize,
    base: &str,
    args: &[DataType],
    type_name: &SmolStr,
    type_frame: &[(SmolStr, DataType)],
    ctx: &mut TypeCtx<'_>,
) {
    let applicable: Vec<usize> = ctx
        .generics
        .impls
        .iter()
        .enumerate()
        .filter(|(_, block)| block.type_name == base && block.args.len() == args.len())
        .map(|(i, _)| i)
        .collect();
    for idx in applicable {
        let impl_file = ctx.generics.impls[idx].file_idx;
        // The header names a type in the scope of the file the block was
        // written in, so a block in one module never attaches to another
        // module's declaration of the same name.
        if find_template(&[], base, ctx.namespaces.get(impl_file), ctx.generics)
            != Some(template_idx)
        {
            continue;
        }
        let header = ctx.generics.impls[idx].args.clone();
        let mut frame: Vec<(SmolStr, DataType)> = Vec::with_capacity(header.len());
        let mut applies = true;
        for (header_arg, arg) in header.iter().zip(args) {
            match header_arg {
                // A bare name that is not a type of its own is a parameter the
                // header introduces, bound to whatever this instantiation
                // passes. Anything else is a concrete type the header pins, and
                // the block applies only when the argument is that type.
                TypeExpr::Identifier(pname, _) if is_type_parameter(pname, impl_file, ctx) => {
                    frame.push((pname.clone(), arg.clone()));
                }
                other => {
                    let mut inner = ctx.reborrow(impl_file);
                    inner.generics.push_bindings(Box::from(type_frame));
                    let pinned = other.to_datatype(&mut inner);
                    ctx.generics.pop_bindings();
                    if &pinned != arg {
                        applies = false;
                        break;
                    }
                }
            }
        }
        if !applies {
            continue;
        }
        let methods = ctx.generics.impls[idx].methods.clone();
        let bindings: Box<[(SmolStr, DataType)]> = Box::from(frame);
        for method in methods {
            lower_method(&method, type_name, &bindings, impl_file, ctx);
        }
    }
}

/// Whether a name written as a type argument in an `impl` header introduces a
/// type parameter rather than naming a type.
fn is_type_parameter(name: &SmolStr, file_idx: u16, ctx: &TypeCtx<'_>) -> bool {
    if matches!(
        name.as_str(),
        "int" | "float" | "bool" | "string" | "null" | "any"
    ) {
        return false;
    }
    find_template(&[], name, ctx.namespaces.get(file_idx), ctx.generics).is_none()
        && !ctx
            .namespaces
            .get(file_idx)
            .symbols
            .iter()
            .any(|(symbol, kind)| {
                symbol == name && matches!(kind, SymbolKind::Struct(_) | SymbolKind::Enum(_))
            })
}

/// The bare name of the type an `impl` block attaches to, with the module
/// qualifier and the type arguments taken off: `g::Cell<int>` reads `Cell`.
fn impl_base_name(type_name: &str) -> &str {
    let without_args = type_name.split('<').next().unwrap_or(type_name);
    without_args.rsplit("::").next().unwrap_or(without_args)
}

/// The name an annotation is written with, for the comparison that keeps a
/// receiver's declared type the one its `impl` block names.
fn annotation_base_name(annotation: &TypeExpr) -> Option<&SmolStr> {
    match annotation {
        TypeExpr::Identifier(name, _) => Some(name),
        TypeExpr::NamespacedIdentifier(path, _) => path.last(),
        TypeExpr::Generic(generic) => Some(&generic.name),
        TypeExpr::Array(_) | TypeExpr::Map(_, _) | TypeExpr::Union(_) | TypeExpr::Fn(_) => None,
    }
}

/// Checks a method named by an operator symbol where it is declared.
///
/// `mangled` carries both halves of the declaration, the type the `impl` block
/// names and the operator, so one call covers the whole rule: the built-in
/// types settle their own operators and take none, an operator takes exactly
/// the operands it has, and the first parameter is the receiver. A method
/// named with an identifier passes straight through.
pub fn check_operator_method(
    mangled: &str,
    args: &[(SmolStr, Option<TypeExpr>)],
    name_span: Span,
    file_idx: u16,
    sources: &[Source],
) {
    let Some((type_name, method)) = mangled.split_once(METHOD_SEP) else {
        return;
    };
    if !is_operator_method(method) {
        return;
    }
    let symbol = if method == UNARY_MINUS_METHOD {
        "-"
    } else {
        method
    };
    if matches!(
        type_name,
        "int" | "float" | "string" | "bool" | "list" | "map"
    ) {
        cold_path();
        error_operator_method(
            "Operator on a built-in type",
            &format!("{type_name} does not take a {symbol} method"),
            "What an operator means on a built-in type is part of the language. Put the value in a struct of your own and define the operator there.",
            "operator_method_on_builtin",
            name_span,
            file_idx,
            sources,
        );
    }
    let wanted = usize::from(!is_unary_operator_method(method)) + 1;
    if args.len() != wanted {
        cold_path();
        error_operator_method(
            "Operator method takes the wrong number of parameters",
            &format!(
                "{symbol} on {type_name} is declared with {} parameter{}",
                args.len(),
                if args.len() == 1 { "" } else { "s" }
            ),
            if symbol == "-" {
                "- takes the receiver and the value to subtract, or the receiver alone to negate it."
            } else if wanted == 1 {
                "A unary operator takes the receiver and nothing else."
            } else {
                "A binary operator takes the receiver and the other operand."
            },
            "operator_method_arity",
            name_span,
            file_idx,
            sources,
        );
    }
    if let Some((_, Some(annotation))) = args.first() {
        let base = impl_base_name(type_name);
        if annotation_base_name(annotation).is_none_or(|written| written != base) {
            cold_path();
            error_operator_method(
                "Operator method receives another type",
                &format!("The first parameter of {symbol} is not a {base}"),
                "The first parameter of a method is the receiver, and its type is the one the impl block names. Leave it un-annotated or annotate it with that type.",
                "operator_method_receiver",
                name_span,
                file_idx,
                sources,
            );
        }
    }
}

/// The name a struct's own default is declared under in its `impl` block.
pub const STRUCT_DEFAULT_METHOD: &str = "default";

/// The struct whose `impl` block declares the function named `fn_name` as its
/// `default`, when it names one.
#[must_use]
pub fn struct_of_default_fn(fn_name: &str, structs: &[Struct]) -> Option<u16> {
    let (type_name, method) = fn_name.split_once(METHOD_SEP)?;
    if method != STRUCT_DEFAULT_METHOD {
        return None;
    }
    structs.iter().rfind(|s| s.name == type_name).map(|s| s.id)
}

/// Checks the `default` function an `impl` block on struct `struct_id`
/// declares.
///
/// Every path that builds the struct's default calls it with nothing and takes
/// the struct from what it hands back, so it declares no parameters and
/// returns the struct.
///
/// `returns` is the type it hands back and the span that says so, when that is
/// known: the `-> Type` annotation where the function is declared, or what its
/// body returns once a default is built from it.
pub fn check_struct_default_fn(
    func: &Function,
    struct_id: u16,
    returns: Option<(&DataType, Span)>,
    sources: &[Source],
    types: TypeNames<'_>,
) {
    let struct_type = DataType::Struct(struct_id);
    let struct_name = types.of(&struct_type).to_string();
    if !func.args.is_empty() {
        cold_path();
        error_struct_default_signature(
            "Default function takes parameters",
            &format!(
                "default in impl {struct_name} is declared with {} parameter{}",
                func.args.len(),
                if func.args.len() == 1 { "" } else { "s" }
            ),
            &format!(
                "{struct_name}::default() and {struct_name} {{ .. }} call it with nothing, so it takes no parameters. A method that takes the value needs another name."
            ),
            func.name_span,
            func.src_file,
            sources,
        );
    }
    if let Some((returned, span)) = returns
        && *returned != struct_type
    {
        cold_path();
        error_struct_default_signature(
            "Default function returns another type",
            &format!(
                "default in impl {struct_name} returns {}, not {struct_name}",
                types.of(returned)
            ),
            &format!(
                "It builds the default of {struct_name}, so its return type is {struct_name}."
            ),
            span,
            func.src_file,
            sources,
        );
    }
}

/// Registers one method of an instantiated `impl` block as the mangled free
/// function its call sites resolve to.
fn lower_method(
    method: &Expr,
    type_name: &SmolStr,
    bindings: &[(SmolStr, DataType)],
    file_idx: u16,
    ctx: &mut TypeCtx<'_>,
) {
    let Expr::FunctionDecl(method_name, args, code, name_span, return_type, params) = method else {
        return;
    };
    let mangled = mangle_method(type_name, method_name);
    check_operator_method(&mangled, args, *name_span, file_idx, ctx.sources);
    if let Some(existing) = ctx.fns.iter().find(|f| f.name == mangled) {
        crate::compiler::compiler_errors::error_function_already_defined(
            existing,
            *name_span,
            file_idx,
            ctx.sources,
        );
    }
    let mut inner = ctx.reborrow(file_idx);
    inner.generics.push_bindings(Box::from(bindings));
    let resolved_args: Box<[(SmolStr, Option<DataType>)]> = args
        .iter()
        .map(|(arg_name, arg_type)| {
            (
                arg_name.clone(),
                arg_type
                    .as_ref()
                    .filter(|t| !t.mentions_any(params))
                    .map(|t| t.to_datatype(&mut inner)),
            )
        })
        .collect();
    let resolved_return = return_type
        .as_deref()
        .filter(|(t, _)| !t.mentions_any(params))
        .map(|(t, t_span)| (t.to_datatype(&mut inner), *t_span));
    ctx.generics.pop_bindings();

    let mut callees = Vec::new();
    collect_direct_fn_calls(code, Some(type_name.as_str()), &mut callees);
    ctx.fns.push(Function {
        name: mangled,
        args: resolved_args,
        code: Rc::clone(code),
        impls: Vec::new(),
        is_recursive: None,
        returns_null: check_if_returns_void(code),
        src_file: file_idx,
        return_type_cache: Vec::new(),
        direct_calls: callees.into_boxed_slice(),
        name_span: *name_span,
        return_type: resolved_return,
        captures: Box::from([]),
        generics: Some(Box::new(FnGenerics {
            params: params.clone(),
            arg_types: args.iter().map(|(_, t)| t.clone()).collect(),
            return_type: return_type.clone(),
            bindings: Box::from(bindings),
            file_idx,
        })),
        entry_register: None,
    });
    let func = &ctx.fns[ctx.fns.len() - 1];
    if let Some(struct_id) = struct_of_default_fn(&func.name, ctx.structs) {
        check_struct_default_fn(
            func,
            struct_id,
            func.return_type.as_ref().map(|(t, span)| (t, *span)),
            ctx.sources,
            TypeNames {
                structs: ctx.structs,
                enums: ctx.enums,
            },
        );
    }
}

/// Resolves the struct a literal names, instantiating the generic type when the
/// literal carries type arguments.
///
/// A literal of a generic type written without them takes each type parameter
/// from the value in the field declared with that parameter as its type, so
/// `Cell{ value: 3 }` is a `Cell<int>`. A parameter no field pins is `any`.
pub fn struct_literal_id(
    namespace: &[SmolStr],
    fields: &[(SmolStr, Expr, Span, Span)],
    type_args: &[TypeExpr],
    span: Span,
    v: &mut Vec<Variable>,
    ctx: Ctx,
    state: &mut State<'_>,
) -> u16 {
    let name = namespace[namespace.len() - 1].clone();
    let path = &namespace[..namespace.len() - 1];
    if !type_args.is_empty() {
        let args = resolve_type_args(type_args, ctx, state);
        return instantiated_struct_id(path, &name, &args, span, ctx, state);
    }
    if let Some(template_idx) =
        find_template(path, &name, state.scope(ctx.file_idx), state.generics)
    {
        let param_fields = state.generics.param_fields(template_idx);
        let mut args: Vec<DataType> = Vec::with_capacity(param_fields.len());
        for field_name in param_fields {
            args.push(
                field_name
                    .and_then(|f| fields.iter().find(|(n, _, _, _)| *n == f))
                    .map_or(DataType::Unknown, |(_, value, _, _)| {
                        value.infer_type(v, ctx, state)
                    }),
            );
        }
        return instantiated_struct_id(path, &name, &args, span, ctx, state);
    }
    state
        .scope(ctx.file_idx)
        .find_struct(path, &name, span, ctx.file_idx, state.sources)
        .unwrap_or_else(|| {
            error_unknown_struct(
                &name,
                span,
                state.scope(ctx.file_idx),
                state.sources,
                ctx.file_idx,
            );
        }) as u16
}

/// Resolves the struct a literal names.
///
/// This is [`struct_literal_id`] with one more source for a generic type's
/// arguments: a literal that writes none and takes its other fields from a
/// `..base` of that type is the base's instantiation.
pub fn literal_struct_id(
    namespace: &[SmolStr],
    fields: &[(SmolStr, Expr, Span, Span)],
    type_args: &[TypeExpr],
    base: Option<&Expr>,
    span: Span,
    v: &mut Vec<Variable>,
    ctx: Ctx,
    state: &mut State<'_>,
) -> u16 {
    if type_args.is_empty()
        && let Some(base) = base
        && let Some((name, path)) = namespace.split_last()
        && let Some(template_idx) =
            find_template(path, name, state.scope(ctx.file_idx), state.generics)
        && let DataType::Struct(id) = base.infer_type(v, ctx, state)
        && state
            .generics
            .instantiation_of(&DataType::Struct(id))
            .is_some_and(|(template, _)| template == template_idx)
    {
        return id;
    }
    struct_literal_id(namespace, fields, type_args, span, v, ctx, state)
}

/// The struct `S::default()` names.
///
/// `path` is a struct (or a generic struct, instantiated at `type_args`)
/// followed by `default`, and the call passes nothing. `None` leaves the path
/// to the function lookups.
pub fn struct_default_target(
    path: &[SmolStr],
    args: &[Expr],
    type_args: &[TypeExpr],
    span: Span,
    ctx: Ctx,
    state: &mut State<'_>,
) -> Option<u16> {
    let [module @ .., type_name, method] = path else {
        return None;
    };
    if method != "default" || !args.is_empty() {
        return None;
    }
    let scope = state.scope(ctx.file_idx);
    let is_struct = scope.resolve(module).is_some_and(|ns| {
        ns.symbols
            .iter()
            .any(|(name, kind)| name == type_name && matches!(kind, SymbolKind::Struct(_)))
    });
    let is_template = find_template(module, type_name, scope, state.generics)
        .is_some_and(|idx| matches!(state.generics.templates[idx].body, TemplateBody::Struct(_)));
    if !is_struct && !is_template {
        return None;
    }
    let mut type_path = module.to_vec();
    type_path.push(type_name.clone());
    Some(struct_literal_id(
        &type_path,
        &[],
        type_args,
        span,
        &mut Vec::new(),
        ctx,
        state,
    ))
}

/// The type a path call names in front of its function: the second-to-last
/// segment of `Point::origin()` or `Set<int>::new()`, behind whatever module
/// path precedes it. A generic type is instantiated at `type_args`, or at
/// `any` for each parameter when the call writes none. `None` when the
/// segment names no struct or enum, or names a plain one while the call
/// carries type arguments, which then belong to a generic function.
fn path_call_type(
    module: &[SmolStr],
    type_name: &SmolStr,
    type_args: &[TypeExpr],
    span: Span,
    ctx: Ctx,
    state: &mut State<'_>,
) -> Option<DataType> {
    let scope = state.scope(ctx.file_idx);
    if let Some(template) = find_template(module, type_name, scope, state.generics) {
        let args = if type_args.is_empty() {
            vec![DataType::Unknown; state.generics.params(template).len()]
        } else {
            resolve_type_args(type_args, ctx, state)
        };
        return Some(instantiate(
            module,
            type_name,
            &args,
            span,
            &mut state.type_ctx(ctx.file_idx),
        ));
    }
    if !type_args.is_empty() {
        return None;
    }
    scope
        .resolve(module)?
        .symbols
        .iter()
        .rev()
        .find_map(|(name, kind)| match kind {
            SymbolKind::Struct(id) if name == type_name => Some(DataType::Struct(*id)),
            SymbolKind::Enum(id) if name == type_name => Some(DataType::Enum(*id)),
            _ => None,
        })
}

/// The `impl` function a call written by its path names.
///
/// `Point::origin()`, `Set<int>::new()` and `shapes::Point::origin()` are such
/// calls: `path` is a struct or an enum followed by the name of a function its
/// `impl` block declares, and the answer is that function's id. `None` leaves
/// the path to the other lookups: a variant of the enum, a module function, a
/// generic function.
///
/// A function declared with no parameters is the only one a path reaches. One
/// that declares a receiver is a method, and a path call to it is reported
/// here with the dot call it needs.
pub fn path_call_target(
    path: &[SmolStr],
    type_args: &[TypeExpr],
    span: Span,
    ctx: Ctx,
    state: &mut State<'_>,
) -> Option<usize> {
    let [module @ .., type_name, method] = path else {
        return None;
    };
    let ty = path_call_type(module, type_name, type_args, span, ctx, state)?;
    let registered = match ty {
        DataType::Struct(id) => state.structs[id as usize].name.clone(),
        DataType::Enum(id) => {
            let e = &state.enums[id as usize];
            if e.variants.iter().any(|variant| variant.name == *method) {
                return None;
            }
            e.name.clone()
        }
        _ => return None,
    };
    let mangled = mangle_method(&registered, method);
    let fn_id = state.fns.iter().position(|f| f.name == mangled)?;
    if !state.fns[fn_id].args.is_empty() {
        cold_path();
        crate::compiler::compiler_errors::error_path_call_with_receiver(
            method,
            &registered,
            span,
            (state.fns[fn_id].name_span, state.fns[fn_id].src_file),
            ctx.file_idx,
            state.sources,
        );
    }
    Some(fn_id)
}

fn instantiated_struct_id(
    namespace: &[SmolStr],
    name: &SmolStr,
    args: &[DataType],
    span: Span,
    ctx: Ctx,
    state: &mut State<'_>,
) -> u16 {
    match instantiate(
        namespace,
        name,
        args,
        span,
        &mut state.type_ctx(ctx.file_idx),
    ) {
        DataType::Struct(id) => id,
        _ => error_unknown_struct(
            name,
            span,
            state.scope(ctx.file_idx),
            state.sources,
            ctx.file_idx,
        ),
    }
}

/// Resolves each type argument of a call, struct literal or variant path in the
/// scope it was written in.
#[must_use]
pub fn resolve_type_args(type_args: &[TypeExpr], ctx: Ctx, state: &mut State<'_>) -> Vec<DataType> {
    type_args
        .iter()
        .map(|t| t.to_datatype(&mut state.type_ctx(ctx.file_idx)))
        .collect()
}

/// Whether a call path written with type arguments names an enum variant
/// rather than a generic function.
///
/// The list is written on the segment before the variant
/// (`Slot<int>::Filled`, `g::Slot<int>::Filled`) and on the last segment for a
/// function (`first<int>`, `m::first<int>`), so whether that earlier segment
/// names a type is what tells the two apart. A non-generic enum counts too, so
/// `Color::Red<int>(1)` still reports type arguments on a plain type instead of
/// looking for a function in a namespace called `Color`.
#[must_use]
pub fn type_args_name_a_variant(path: &[SmolStr], ctx: Ctx, state: &State<'_>) -> bool {
    let Some(base_idx) = path.len().checked_sub(2) else {
        return false;
    };
    let base = &path[base_idx];
    find_template(
        &path[..base_idx],
        base,
        state.scope(ctx.file_idx),
        state.generics,
    )
    .is_some()
        || state
            .scope(ctx.file_idx)
            .find_enum(&path[..base_idx], base)
            .is_some()
}

/// Resolves a variant constructor to the enum it names and the index of the
/// variant, instantiating a generic enum at the types its payload names.
///
/// A plain enum resolves by name, the way it always has. A generic enum has no
/// registered type until something names one, so the constructor makes it: the
/// arguments bind the parameters the variant declares, and a parameter the
/// payload does not mention stands for `any`. `Ok(2)` is therefore a
/// `Result<int, any>` and `None` on its own an `Option<any>`, and
/// [`param_type_matches`] is what lets those go where a fully named
/// instantiation is expected.
///
/// Returns `None` when no generic enum declares a variant of that name, which
/// is what leaves plain enums and ordinary calls to the paths that follow.
/// The enum and variant a constructor names, at the types its payload is
/// given: a generic enum instantiated at what the payload binds, or a plain
/// enum resolved by name.
pub fn variant_constructor_at(
    path: &[SmolStr],
    arg_types: &[DataType],
    span: Span,
    ctx: Ctx,
    state: &mut State<'_>,
) -> Option<(u16, u16)> {
    // A program's own enum declaring a bare variant the prelude also declares
    // (`Some`) is the one the name reaches.
    if let [variant] = path
        && state.generics.only_the_prelude_declares(variant)
        && let Some(own) = state.enums.iter().find_map(|e| {
            let idx = e.variants.iter().position(|vt| vt.name == *variant)?;
            state
                .generics
                .instantiation_of(&DataType::Enum(e.id))
                .is_none()
                .then_some((e.id, idx as u16))
        })
    {
        return Some(own);
    }
    resolve_variant_constructor(path, arg_types, span, ctx, state)
        .or_else(|| resolve_enum_variant(path, ctx.file_idx, state))
}

pub fn resolve_variant_constructor(
    path: &[SmolStr],
    arg_types: &[DataType],
    span: Span,
    ctx: Ctx,
    state: &mut State<'_>,
) -> Option<(u16, u16)> {
    let variant = path.last()?.clone();
    let (namespace, template) = if path.len() >= 2 {
        let namespace = &path[..path.len() - 2];
        let base = &path[path.len() - 2];
        let template = find_template(namespace, base, state.scope(ctx.file_idx), state.generics)?;
        (namespace, template)
    } else {
        (
            &path[..0],
            state.generics.enum_template_with_variant(&variant)?,
        )
    };
    let params: Vec<SmolStr> = state.generics.params(template).to_vec();
    let payload: Vec<TypeExpr> = state.generics.variant_payload(template, &variant)?.to_vec();
    let mut bound: Vec<Option<DataType>> = vec![None; params.len()];
    for (declared, found) in payload.iter().zip(arg_types) {
        bind_params_from_payload(declared, found, &params, &mut bound);
    }
    let args: Vec<DataType> = bound
        .into_iter()
        .map(|b| b.unwrap_or(DataType::Unknown))
        .collect();
    let base = state.generics.template_name(template).clone();
    let namespace: Box<[SmolStr]> = namespace.into();
    let DataType::Enum(enum_id) = instantiate(
        &namespace,
        &base,
        &args,
        span,
        &mut state.type_ctx(ctx.file_idx),
    ) else {
        return None;
    };
    let variant_idx = state.enums[enum_id as usize]
        .variants
        .iter()
        .position(|vt| vt.name == variant)? as u16;
    Some((enum_id, variant_idx))
}

/// Binds the type parameters a variant's declared payload mentions to the types
/// the constructor was handed. A parameter the payload does not mention, and one
/// whose argument carries no type of its own, is left for the caller to fill
/// with `any`.
fn bind_params_from_payload(
    declared: &TypeExpr,
    found: &DataType,
    params: &[SmolStr],
    bound: &mut [Option<DataType>],
) {
    match declared {
        TypeExpr::Identifier(name, _) => {
            if *found != DataType::Unknown
                && let Some(i) = params.iter().position(|p| p == name)
                && bound[i].is_none()
            {
                bound[i] = Some(found.clone());
            }
        }
        TypeExpr::Array(inner) => {
            if let DataType::Array(Some(element)) = found {
                bind_params_from_payload(inner, element, params, bound);
            }
        }
        TypeExpr::Map(key, value) => {
            if let DataType::Map(entry) = found {
                if let Some(t) = &entry.0 {
                    bind_params_from_payload(key, t, params, bound);
                }
                if let Some(t) = &entry.1 {
                    bind_params_from_payload(value, t, params, bound);
                }
            }
        }
        _ => {}
    }
}

/// Resolves a variant of a generic enum named with its arguments
/// (`Slot<int>::Empty`) to the instantiated enum and the variant's index.
pub fn resolve_generic_variant(
    path: &[SmolStr],
    type_args: &[TypeExpr],
    span: Span,
    ctx: Ctx,
    state: &mut State<'_>,
) -> (u16, u16) {
    let variant = path[path.len() - 1].clone();
    let base = path[path.len() - 2].clone();
    let namespace = &path[..path.len() - 2];
    let args = resolve_type_args(type_args, ctx, state);
    let DataType::Enum(enum_id) = instantiate(
        namespace,
        &base,
        &args,
        span,
        &mut state.type_ctx(ctx.file_idx),
    ) else {
        crate::compiler::compiler_errors::error_enum(
            "Unknown enum",
            &format!("{base} does not name an enum"),
            span,
            ctx.file_idx,
            state.sources,
        );
    };
    let Some(variant_idx) = state.enums[enum_id as usize]
        .variants
        .iter()
        .position(|vt| vt.name == variant)
    else {
        crate::compiler::compiler_errors::error_enum(
            "Unknown enum variant",
            &format!("{} does not name an enum variant", path.join("::")),
            span,
            ctx.file_idx,
            state.sources,
        );
    };
    (enum_id, variant_idx as u16)
}

/// Resolves a call written with type arguments to the function it names and
/// the arguments bound to its type parameters.
///
/// `namespace` is the path in front of the name, empty for a call the file
/// writes unqualified (`first<int>(nums)`) and the module alias for one it
/// reaches through an import (`m::first<int>(nums)`).
pub fn resolve_generic_call(
    namespace: &[SmolStr],
    fn_name: &SmolStr,
    type_args: &[TypeExpr],
    span: Span,
    ctx: Ctx,
    state: &mut State<'_>,
) -> (usize, Vec<DataType>) {
    let Some(fn_id) = state.scope(ctx.file_idx).find_function(namespace, fn_name) else {
        if !namespace.is_empty() {
            error_unknown_function_in_namespace(fn_name, namespace, span, ctx.file_idx, state);
        }
        error_unknown_function(
            fn_name,
            span,
            state.scope(ctx.file_idx),
            ctx.file_idx,
            state.sources,
        );
    };
    let args = resolve_call_type_args(fn_id, fn_name, type_args, span, ctx, state);
    (fn_id, args)
}

/// Checks the type arguments a call is written with against the parameters the
/// function it resolves to declares, and resolves them to types.
///
/// `name` is the spelling to report against, which for a method is the method
/// name rather than the mangled symbol the call reaches.
pub fn resolve_call_type_args(
    fn_id: usize,
    name: &str,
    type_args: &[TypeExpr],
    span: Span,
    ctx: Ctx,
    state: &mut State<'_>,
) -> Vec<DataType> {
    let params_len = state.fns[fn_id]
        .generics
        .as_ref()
        .map_or(0, |g| g.params.len());
    if params_len == 0 {
        error_type_args_on_plain_function(span, ctx.file_idx, name, state.sources);
    }
    if params_len != type_args.len() {
        error_type_arg_count(
            span,
            ctx.file_idx,
            name,
            params_len,
            type_args.len(),
            state.sources,
        );
    }
    resolve_type_args(type_args, ctx, state)
}

/// The return type a `host` or `dylib` block declares for a namespaced call,
/// or `None` when the path names no declared function.
///
/// The path is resolved whole, the way the call is compiled: the leading
/// element selects the block and the last element the function in it. A `host`
/// declaration wins over a `dylib` one of the same name, matching the order the
/// two are bound in.
fn declared_return_type(namespace: &[SmolStr], state: &State<'_>) -> Option<DataType> {
    let fn_name = namespace.last()?;
    let block = &namespace[0];
    let declared = |is_host: bool| {
        state
            .dyn_libs
            .iter()
            .find(|lib| lib.is_host == is_host && lib.name == *block)
            .and_then(|lib| lib.fns.iter().find(|f| f.name == *fn_name))
            .map(|f| f.return_type.clone())
    };
    declared(true).or_else(|| declared(false))
}

/// The type an unqualified built-in call yields, or `None` when no built-in
/// takes that name.
///
/// Keep in step with the match in `builtin_functions`, which lowers these
/// calls: a name that lowers there and is missing here is reported as an
/// unknown function, and a name here that does not lower there types a call
/// that never reaches a built-in. `in_std` says the call is written in a
/// standard library module, the only place the [`std_primitive_return_type`]
/// names resolve.
fn builtin_fn_return_type(name: &str, in_std: bool) -> Option<DataType> {
    if in_std && let Some(t) = std_primitive_return_type(name) {
        return Some(t);
    }
    Some(match name {
        "print" | "exit" | "throw" => DataType::Null,
        "type" | "string" | "input" => DataType::String,
        "float" => DataType::Float,
        "int" | "the_answer" => DataType::Int,
        "bool" | "[int text]" | "[float text]" => DataType::Bool,
        "range" => DataType::Array(Some(Box::from(DataType::Int))),
        "argv" => DataType::Array(Some(Box::from(DataType::String))),
        _ => return None,
    })
}

/// The type a native primitive of the standard library yields, or `None` when
/// none takes that name.
///
/// These are what `std/json` and `std/fs` are written on; only a standard
/// library module reaches them, so a program has one spelling of each, the
/// module's. Keep in step with `builtin_functions`.
#[must_use]
pub fn std_primitive_return_type(name: &str) -> Option<DataType> {
    Some(match name {
        "json_stringify" | "fs_read" => DataType::String,
        // json::parse yields a fully dynamic value.
        "json_parse" => DataType::Unknown,
        "fs_exists" => DataType::Bool,
        "fs_write" | "fs_append" | "fs_delete" | "fs_delete_dir" => DataType::Null,
        _ => return None,
    })
}

/// Renders a [`DataType`] the way a program spells it.
///
/// This is what the `type` builtin hands back, so its output is a string the
/// program can read, and every part of it is written the way the same type
/// would be written in source: `any` for the dynamic slot, a struct or an enum
/// by the name it was declared under, and a function as `fn(int) -> int`.
///
/// Names are resolved against the compiler `State` by `Struct`/`Fn` id. The
/// plain `Display` impl (in `candela-vm`) has no `State`, so it renders those
/// variants opaquely; a diagnostic names them through [`TypeNames`] instead.
#[must_use]
pub fn format_detailed(t: &DataType, state: &State<'_>) -> SmolStr {
    match t {
        DataType::Float => SmolStr::new_static("float"),
        DataType::Int => SmolStr::new_static("int"),
        DataType::Bool => SmolStr::new_static("bool"),
        DataType::String => SmolStr::new_static("string"),
        DataType::Array(array_type) => match array_type {
            Some(array_type) => {
                format_args!("{}[]", format_detailed(array_type, state)).to_smolstr()
            }
            None => SmolStr::new_static("any[]"),
        },
        DataType::Null => SmolStr::new_static("null"),
        DataType::Unknown => SmolStr::new_static("any"),
        // A position that says what it holds is written the way it was
        // declared. One whose functions the compiler collected names no
        // signature, since the functions in it need not agree on one.
        DataType::FnValue(fn_type) => match &fn_type.sig {
            Some((params, returned)) => format_signature(params, returned, state),
            None => SmolStr::new_static("function"),
        },
        DataType::Union(types) => format_args!(
            "{}",
            types
                .into_iter()
                .map(|x| format_detailed(x, state))
                .collect::<Vec<SmolStr>>()
                .join("|")
        )
        .to_smolstr(),
        DataType::Struct(s) => state.structs[*s as usize].name.clone(),
        DataType::Enum(e) => state.enums[*e as usize].name.clone(),
        // Both halves are rendered through this same function, so a map of a
        // user type names that type the way a list of it does. Reaching for
        // `Display` here is what made `type({"a": Value::Num(1)})` answer
        // `{string: enum}`.
        DataType::Map(m) => format_args!(
            "{{{}: {}}}",
            m.0.as_ref()
                .map_or_else(|| SmolStr::new_static("any"), |k| format_detailed(k, state)),
            m.1.as_ref().map_or_else(
                || SmolStr::new_static("any"),
                |val| format_detailed(val, state)
            )
        )
        .to_smolstr(),
        // A declaration is what a function's type says: a parameter with no
        // annotation takes `any`, and so does a return the declaration left to
        // the body. A function that hands nothing back is written without the
        // arrow, the way `fn()` is written in source.
        DataType::Fn(id) => {
            let f = &state.fns[*id as usize];
            let params: Box<[DataType]> = f
                .args
                .iter()
                .map(|(_, declared)| declared.clone().unwrap_or(DataType::Unknown))
                .collect();
            let returned = match &f.return_type {
                Some((declared, _)) => declared.clone(),
                None if f.returns_null => DataType::Null,
                None => DataType::Unknown,
            };
            format_signature(&params, &returned, state)
        }
    }
}

/// A function type written the way a declaration writes it: `fn(int) -> int`,
/// and `fn()` where it hands nothing back.
fn format_signature(params: &[DataType], returned: &DataType, state: &State<'_>) -> SmolStr {
    let params = params
        .iter()
        .map(|param| format_detailed(param, state))
        .collect::<Vec<SmolStr>>()
        .join(", ");
    if matches!(returned, DataType::Null) {
        format_args!("fn({params})").to_smolstr()
    } else {
        format_args!("fn({params}) -> {}", format_detailed(returned, state)).to_smolstr()
    }
}

/// Whether a value of type `received` fits a field declared `expected`.
///
/// `null` fits every field, because it is what an absent value carries.
/// Everything else is [`param_type_matches`], the rule a parameter uses: a
/// field declared `any` is a dynamic slot and holds a value of any type, and
/// two instantiations of one generic declaration line up when their arguments
/// do.
///
/// The one place a field is stricter than a parameter is a dynamic value put
/// into a typed field. A field is read back at the type it declares and used
/// without a run-time test, so a `string` stored in an `int` field would be
/// reported from inside the arithmetic that later read it, or not at all. It
/// is reported at the line that wrote it instead; name the type with `as int`
/// or another downcast to store one.
#[inline(always)]
#[must_use]
pub fn struct_field_type_matches(
    expected: &DataType,
    received: &DataType,
    generics: &Generics,
) -> bool {
    if *received == DataType::Unknown {
        return *expected == DataType::Unknown;
    }
    received == &DataType::Null || param_type_matches(expected, received, generics)
}

/// Whether an argument of type `received` satisfies a parameter declared as
/// `expected`.
///
/// `Unknown` is the `any` slot and the type of a value the checker cannot pin
/// down (a `json::parse` result, for instance). It stands in for every type on
/// either side, so annotating a parameter `any` keeps the parameter dynamic and
/// passing a dynamic value to a typed parameter is still allowed. Every other
/// pair uses the ordinary type equality.
///
/// The same rule reaches inside an instantiation: a constructor names only the
/// parameters its payload mentions, so `Ok(2)` is a `Result<int, any>` and
/// `None` is an `Option<any>`. Two instantiations of one declaration line up
/// when every pair of arguments does, which is what lets those values be
/// passed and returned where a fully named instantiation is expected.
#[inline(always)]
#[must_use]
pub fn param_type_matches(expected: &DataType, received: &DataType, generics: &Generics) -> bool {
    *expected == DataType::Unknown
        || *received == DataType::Unknown
        || expected == received
        || instantiations_line_up(expected, received, generics)
}

/// Whether a body returning `body` satisfies a function declared to return
/// `declared`.
///
/// Every pair [`param_type_matches`] accepts fits. A return also fits where the
/// body hands back something narrower than a declaration that names `any`
/// inside it: an `int[]` fits `any[]` and a `{string: string}` fits
/// `{any: any}`, because the call site reads the declared type and every value
/// is one an `any` slot holds. A union fits when every member does, and a
/// member fits a declared union when it fits one of its members. Parameters
/// keep the stricter rule: an `int[]` a callee may push a string into is not
/// an `any[]`.
#[must_use]
pub fn return_type_fits(declared: &DataType, body: &DataType, generics: &Generics) -> bool {
    if param_type_matches(declared, body, generics) {
        return true;
    }
    match (declared, body) {
        (_, DataType::Union(members)) => members
            .iter()
            .all(|member| return_type_fits(declared, member, generics)),
        (DataType::Union(members), _) => members
            .iter()
            .any(|member| return_type_fits(member, body, generics)),
        (DataType::Array(Some(declared)), DataType::Array(Some(body))) => {
            return_type_fits(declared, body, generics)
        }
        (DataType::Map(declared), DataType::Map(body)) => {
            slot_fits(declared.0.as_ref(), body.0.as_ref(), generics)
                && slot_fits(declared.1.as_ref(), body.1.as_ref(), generics)
        }
        _ => false,
    }
}

/// Whether a value of type `value` may be written into a variable whose `let`
/// declares `declared`.
///
/// A declared variable is read at its declared type without a run-time test,
/// so a dynamic value goes in only through a downcast (`as int`), the rule a
/// struct field follows, and a union goes in only when every member fits.
/// `fresh` marks a list or map literal, which nothing else holds yet: it may
/// be widened into a declaration that names `any` inside it, the way a return
/// may, since no other holder sees what is put into it afterwards.
#[must_use]
pub fn let_type_fits(
    declared: &DataType,
    value: &DataType,
    fresh: bool,
    generics: &Generics,
) -> bool {
    match value {
        DataType::Unknown => matches!(declared, DataType::Unknown),
        DataType::Union(members) => members
            .iter()
            .all(|member| let_type_fits(declared, member, fresh, generics)),
        _ if fresh => return_type_fits(declared, value, generics),
        _ => param_type_matches(declared, value, generics),
    }
}

/// Whether one half of a returned map's type fits the declared half. A half
/// either side leaves open fits, the way map equality treats it.
fn slot_fits(declared: Option<&DataType>, body: Option<&DataType>, generics: &Generics) -> bool {
    match (declared, body) {
        (Some(declared), Some(body)) => return_type_fits(declared, body, generics),
        _ => true,
    }
}

/// Whether two instantiations come from one declaration and every pair of their
/// type arguments lines up.
#[must_use]
pub(crate) fn instantiations_line_up(a: &DataType, b: &DataType, generics: &Generics) -> bool {
    let (Some((ta, args_a)), Some((tb, args_b))) =
        (generics.instantiation_of(a), generics.instantiation_of(b))
    else {
        return false;
    };
    ta == tb
        && args_a.len() == args_b.len()
        && args_a
            .iter()
            .zip(args_b)
            .all(|(x, y)| param_type_matches(x, y, generics))
}

/// Fills in element types a value left open, taking them from the type that was
/// declared for it.
///
/// An empty array literal has no element type: it is `Array(None)`, so indexing
/// it yields `null` and a body specialised on it cannot match on its elements.
/// An empty map literal is `Map(None, None)`, so reading a key out of it yields
/// nothing the body can match on either. Where the declaration says what the
/// collection holds, the declaration wins and the specialisation compiles at the
/// declared types. Only an open position is filled, so a collection that does
/// name what it holds still has to match what was declared. The walk descends
/// through arrays and through both halves of a map, so an empty literal nested
/// inside one is pinned too.
fn pin_open_element_types(inferred: &mut DataType, declared: &DataType) {
    match (inferred, declared) {
        (DataType::Array(element), DataType::Array(Some(declared_element))) => match element {
            None => *element = Some(declared_element.clone()),
            Some(element) => pin_open_element_types(element, declared_element),
        },
        (DataType::Map(entry), DataType::Map(declared_entry)) => {
            pin_open_slot(&mut entry.0, declared_entry.0.as_ref());
            pin_open_slot(&mut entry.1, declared_entry.1.as_ref());
        }
        _ => {}
    }
}

/// Pins a caller's binding that still holds an empty literal to the type the
/// parameter it is passed to declares.
///
/// `let` takes no annotation, so a binding that starts out as `[]` or `{}`
/// holds nothing until something says what it holds. The first `push` or
/// `insert` on it is one such statement; handing it to a parameter that
/// declares a collection type is another, and it is often the first one the
/// caller writes, because the callee is what fills the collection. Pinning it
/// here gives the caller's later reads the element or value type the callee
/// put in.
///
/// Only a binding that is still the empty-literal placeholder is pinned. One
/// that already names what it holds keeps its type, so a parameter declaring
/// something else stays the argument mismatch the call site reports.
pub(crate) fn pin_empty_literal_bindings(
    args: &[Expr],
    declared_arg_types: &[Option<DataType>],
    v: &mut [Variable],
) {
    for (arg, declared) in args.iter().zip(declared_arg_types) {
        let (Expr::Var(name, _), Some(declared)) = (arg, declared) else {
            continue;
        };
        let Some(var) = v.iter_mut().rfind(|var| &var.name == name) else {
            continue;
        };
        if is_empty_literal_type(&var.var_type) {
            pin_open_element_types(&mut var.var_type, declared);
        }
    }
}

/// Pins a binding that still holds an empty array literal to what the first
/// `push` puts in it.
///
/// Only an array with no element type at all upgrades: an array of `any`
/// compares equal to `Array(None)` and keeps its dynamic element type.
pub(crate) fn pin_pushed_element(obj: &Expr, element: &DataType, v: &mut [Variable]) {
    let Expr::Var(var_name, _) = obj else {
        return;
    };
    if let Some(var) = v.iter_mut().rfind(|var| &var.name == var_name)
        && matches!(var.var_type, DataType::Array(None))
    {
        var.var_type = DataType::Array(Some(Box::new(element.clone())));
    }
}

/// Pins a binding that still holds an empty map literal to what the first
/// `m[k] = v` puts in it, so later reads and iteration see concrete types.
///
/// The test is on missing key and value types, not on `== Map((None, None))`:
/// a map of `any` compares equal to it and keeps taking entries of any type,
/// which is what a downcast (`as {any: any}`) hands back.
pub(crate) fn pin_inserted_entry(obj: &Expr, key: &DataType, value: &DataType, v: &mut [Variable]) {
    let Expr::Var(var_name, _) = obj else {
        return;
    };
    if let Some(var) = v.iter_mut().rfind(|var| &var.name == var_name)
        && matches!(&var.var_type, DataType::Map(m) if m.0.is_none() && m.1.is_none())
    {
        var.var_type = DataType::Map(Box::from((Some(key.clone()), Some(value.clone()))));
    }
}

/// Whether a type is what an empty literal leaves behind: an array with no
/// element type, or a map with neither a key nor a value type. A downcast
/// (`as {any: any}`) hands back entries of `any`, which names a type and is left
/// alone.
#[must_use]
fn is_empty_literal_type(ty: &DataType) -> bool {
    match ty {
        DataType::Array(element) => element.is_none(),
        DataType::Map(entry) => entry.0.is_none() && entry.1.is_none(),
        _ => false,
    }
}

/// One half of a map's type: its keys or its values. An open slot takes the
/// declared type, a slot that names a type is descended into so a nested empty
/// literal is pinned as well, and a declaration that is itself open leaves the
/// slot alone.
fn pin_open_slot(inferred: &mut Option<DataType>, declared: Option<&DataType>) {
    let Some(declared) = declared else {
        return;
    };
    match inferred {
        None => *inferred = Some(declared.clone()),
        Some(inferred) => pin_open_element_types(inferred, declared),
    }
}

/// Equality for monomorphization and return-type cache keys.
///
/// Identical to the loose type `==` except that function-typed arguments compare
/// by exact `Fn` id, so each distinct function passed to a higher-order function
/// keys its own specialization. Function references are always top-level
/// arguments (a function is passed directly, never nested inside an array or
/// map), so only the top-level `Fn` case needs the stricter rule.
#[must_use]
pub fn arg_types_specialize_equal(a: &[DataType], b: &[DataType]) -> bool {
    a.len() == b.len()
        && a.iter().zip(b).all(|(x, y)| match (x, y) {
            (DataType::Fn(i), DataType::Fn(j)) => i == j,
            (DataType::Fn(_), _) | (_, DataType::Fn(_)) => false,
            _ => x == y,
        })
}

/// Collects the functions the given code calls by name.
///
/// `self_type` is the type a method's body is compiled against, so a call the
/// body makes on its own receiver (`self.down(n - 1)`) is recorded under the
/// mangled name that method resolves to (`Box#down`). It is `None` for an
/// ordinary function, whose `self` names no receiver. A call on any other
/// receiver is left out: which function it reaches depends on the receiver's
/// type, which only the call site knows.
///
/// What this list is for is recursion: a function that can reach itself
/// through it is compiled as a call rather than inlined, so a method that
/// calls itself is compiled the way a recursive function is.
///
/// # Panics
///
/// Panics when a `FunctionCall` node carries an empty namespace path, which
/// the parser never produces.
pub fn collect_direct_fn_calls(
    content: &[Expr],
    self_type: Option<&str>,
    calls: &mut Vec<SmolStr>,
) {
    let mut expr_stack: Vec<&Expr> = content.iter().collect();
    while let Some(expression) = expr_stack.pop() {
        // An operator on `self` is a call of the method the receiver's type
        // defines for it, so it counts the same as `self.method(...)` does.
        if let Some(type_name) = self_type
            && let Some(method) = self_operator_method(expression)
        {
            calls.push(mangle_method(type_name, method));
        }
        match expression {
            Expr::FunctionCall(args, namespace, _, _, _) => {
                let (name, path) = namespace.split_last().unwrap();
                // `Type::f()` reaches the function `Type`'s `impl` block
                // declares, which inside that block is the type the body is
                // compiled for.
                if let Some(type_name) = path.last() {
                    match self_type {
                        Some(self_type) if impl_base_name(self_type) == type_name.as_str() => {
                            calls.push(mangle_method(self_type, name));
                        }
                        _ => calls.push(mangle_method(type_name, name)),
                    }
                }
                calls.push(name.clone());
                expr_stack.extend(args.iter());
            }
            Expr::Condition(x, y, _, _)
            | Expr::InlineCondition(x, y, _, _)
            | Expr::ElseIfBlock(x, y, _)
            | Expr::WhileBlock(x, y, _) => {
                expr_stack.push(x);
                expr_stack.extend(y.iter());
            }
            Expr::ObjFunctionCall(obj, args, namespace, _, _, _, _) => {
                if let Some(type_name) = self_type
                    && matches!(&**obj, Expr::Var(name, _) if name == "self")
                    && let Some(method) = namespace.last()
                {
                    calls.push(mangle_method(type_name, method));
                }
                expr_stack.push(obj);
                expr_stack.extend(args.iter());
            }
            Expr::CallValue(callee, args, _, _) => {
                expr_stack.push(callee);
                expr_stack.extend(args.iter());
            }
            Expr::ElseBlock(x) | Expr::EvalBlock(x) | Expr::LoopBlock(x) => {
                expr_stack.extend(x.iter());
            }
            Expr::ReturnVal(code) => {
                if let Some(code) = code.as_ref() {
                    expr_stack.push(code);
                }
            }
            Expr::FunctionDecl(_, _, x, _, _, _) => expr_stack.extend(x.iter()),
            Expr::ArrayGetSlice(x, y, z, _) => {
                expr_stack.push(x);
                expr_stack.push(y);
                if let Some(z) = z {
                    expr_stack.push(z);
                }
            }
            Expr::VarDeclare(_, x, _)
            | Expr::VarAssign(_, x, _, _)
            | Expr::Propagate(x, _)
            | Expr::Is(x, _, _, _)
            | Expr::Cast(x, _, _, _)
            | Expr::Neg(x, _, _)
            | Expr::BitNot(x, _, _)
            | Expr::BoolNeg(x, _, _) => expr_stack.push(x),
            Expr::ForLoop(_, _, code, _) => expr_stack.extend(code.iter()),
            Expr::IntForLoop(_, start, end, code, _, _) => {
                expr_stack.push(start);
                expr_stack.push(end);
                expr_stack.extend(code.iter());
            }
            Expr::ArrayModify(array, index, value, _, _) => {
                expr_stack.push(array);
                expr_stack.push(index);
                expr_stack.push(value);
            }
            Expr::Array(elems, _) => expr_stack.extend(elems.iter()),
            Expr::Struct(_, fields, _, _, base) => {
                expr_stack.extend(fields.iter().map(|(_, expr, _, _)| expr));
                if let Some(base) = base.as_ref().and_then(|b| b.0.base()) {
                    expr_stack.push(base);
                }
            }
            Expr::GetStructField(expr, _, _, _) => expr_stack.push(expr),
            Expr::SetStructField(expr, _, value, _, _, _) => {
                expr_stack.push(expr);
                expr_stack.push(value);
            }
            Expr::TryCatchBlock(try_code, _, catch_code) => {
                expr_stack.extend(try_code.iter());
                expr_stack.extend(catch_code.iter());
            }
            Expr::Match(scrutinee, arms, wildcard, _, _) => {
                expr_stack.push(scrutinee);
                for (patterns, body) in arms {
                    expr_stack.extend(patterns.iter());
                    expr_stack.extend(body.iter());
                }
                if let Some(w) = wildcard {
                    expr_stack.extend(w.iter());
                }
            }
            Expr::ArrayGetIndex(x, y, _)
            | Expr::Mul(x, y, _, _)
            | Expr::Div(x, y, _, _)
            | Expr::Add(x, y, _, _)
            | Expr::Sub(x, y, _, _)
            | Expr::Mod(x, y, _, _)
            | Expr::Pow(x, y, _, _)
            | Expr::BitAnd(x, y, _, _)
            | Expr::BitOr(x, y, _, _)
            | Expr::BitXor(x, y, _, _)
            | Expr::Shl(x, y, _, _)
            | Expr::Shr(x, y, _, _)
            | Expr::Eq(x, y, _, _)
            | Expr::NotEq(x, y, _, _)
            | Expr::Sup(x, y, _, _)
            | Expr::SupEq(x, y, _, _)
            | Expr::Inf(x, y, _, _)
            | Expr::InfEq(x, y, _, _)
            | Expr::BoolAnd(x, y, _, _)
            | Expr::BoolOr(x, y, _, _) => {
                expr_stack.push(x);
                expr_stack.push(y);
            }
            _ => {}
        }
    }
}

/// Check if the function src_fn can call target_fn
pub fn can_reach<S: std::hash::BuildHasher>(
    src_fn: &str,
    target_fn: &str,
    fns: &[Function],
    visited: &mut std::collections::HashSet<SmolStr, S>,
) -> bool {
    if let Some(from_fn) = fns.iter().find(|f| f.name.as_str() == src_fn) {
        for callee in &from_fn.direct_calls {
            if callee == target_fn {
                return true;
            }
            if visited.insert(callee.clone()) && can_reach(callee, target_fn, fns, visited) {
                return true;
            }
        }
    }
    false
}

/// Which kinds of `return` a body writes, closures left out.
#[derive(Default)]
struct ReturnShapes {
    /// A `return expr;` somewhere in the body.
    value: bool,
    /// A bare `return;` somewhere in the body.
    bare: bool,
}

fn collect_return_shapes(content: &[Expr], shapes: &mut ReturnShapes) {
    for content in content {
        match content {
            Expr::ElseIfBlock(_, code, _)
            | Expr::ElseBlock(code)
            | Expr::Condition(_, code, _, _)
            | Expr::InlineCondition(_, code, _, _)
            | Expr::WhileBlock(_, code, _)
            | Expr::ForLoop(_, _, code, _)
            | Expr::EvalBlock(code)
            | Expr::LoopBlock(code)
            | Expr::IntForLoop(_, _, _, code, _, _) => collect_return_shapes(code, shapes),
            Expr::TryCatchBlock(try_code, _, catch_code) => {
                collect_return_shapes(try_code, shapes);
                collect_return_shapes(catch_code, shapes);
            }
            Expr::Match(_, arms, wildcard, _, _) => {
                for (_, body) in arms {
                    collect_return_shapes(body, shapes);
                }
                if let Some(w) = wildcard {
                    collect_return_shapes(w, shapes);
                }
            }
            Expr::ReturnVal(value) => {
                if value.is_some() {
                    shapes.value = true;
                } else {
                    shapes.bare = true;
                }
            }
            _ => {}
        }
    }
}

#[must_use]
pub fn check_if_returns_void(content: &[Expr]) -> bool {
    let mut shapes = ReturnShapes::default();
    collect_return_shapes(content, &mut shapes);
    !shapes.value
}

macro_rules! extend_return_types {
    ($return_types: expr, $new_types: expr, $ctx: expr, $state: expr) => {
        for return_type in $new_types {
            add_return_type($return_types, return_type, $ctx, $state);
        }
    };
}

/// Adds one of a body's return types to the set the function produces.
///
/// `any` says nothing about what comes back and is dropped. Two instantiations
/// of one generic declaration merge instead of making a union: a constructor
/// names only the parameters its payload mentions, so a body that returns
/// `Ok(2)` on one path and `Err("no")` on another produces a `Result<int, any>`
/// and a `Result<any, string>`, and those are the one type `Result<int,
/// string>`.
fn add_return_type(
    return_types: &mut Vec<DataType>,
    return_type: DataType,
    ctx: Ctx,
    state: &mut State<'_>,
) {
    if return_type == DataType::Unknown {
        return;
    }
    // Two functions handed back by one body make one value the caller calls
    // through, so the two types join: both bodies are compiled and the call
    // dispatches on the one that came back. Keeping only the first would leave
    // the second with no body to jump to.
    if matches!(return_type, DataType::Fn(_) | DataType::FnValue(_))
        && let Some(i) = return_types
            .iter()
            .position(|held| matches!(held, DataType::Fn(_) | DataType::FnValue(_)))
    {
        if let Some(merged) = merge_fn_types(&[return_types[i].clone(), return_type]) {
            return_types[i] = merged;
        }
        return;
    }
    if return_types.contains(&return_type) {
        return;
    }
    let mut replacement = None;
    for (i, existing) in return_types.iter().enumerate() {
        if let Some(merged) = merge_instantiations(existing, &return_type, ctx, state) {
            replacement = Some((i, merged));
            break;
        }
    }
    if let Some((i, merged)) = replacement {
        return_types[i] = merged;
        return;
    }
    return_types.push(return_type);
}

/// What a `?` reads out of an enum shaped like `Option` or `Result`.
///
/// `Option` is `Some(T)` and `None`, `Result` is `Ok(T)` and `Err(E)`. Answers
/// the type `?` reads out of the success variant and the index of the failure
/// variant, which is the one it hands back to the caller; `None` for any other
/// type.
#[must_use]
pub fn propagation_sides(t: &DataType, state: &State<'_>) -> Option<(DataType, u16)> {
    let DataType::Enum(enum_id) = t else {
        return None;
    };
    let variants = &state.enums[*enum_id as usize].variants;
    let [first, second] = &**variants else {
        return None;
    };
    let (success, failure, failure_idx) = match (first.name.as_str(), second.name.as_str()) {
        ("Some", "None") | ("Ok", "Err") => (first, second, 1),
        ("None", "Some") | ("Err", "Ok") => (second, first, 0),
        _ => return None,
    };
    let failure_arity = usize::from(failure.name == "Err");
    if success.payload.len() != 1 || failure.payload.len() != failure_arity {
        return None;
    }
    Some((success.payload[0].clone(), failure_idx))
}

/// The type a `?` on a value of type `operand` hands back to the caller: the
/// same declaration with the success side left open, `Option<any>` for an
/// `Option` and `Result<any, E>` for a `Result<T, E>`. The value it returns is
/// the operand's `None` or `Err`, which holds no `T`.
fn propagated_failure_type(operand: &DataType, state: &mut State<'_>) -> Option<DataType> {
    let (template, args) = state.generics.instantiation_of(operand)?;
    let mut args: Vec<DataType> = args.to_vec();
    // `Option<T>` and `Result<T, E>` both declare the success side's parameter
    // first.
    *args.first_mut()? = DataType::Unknown;
    let base = state.generics.template_name(template).clone();
    let file_idx = state.generics.template_file(template);
    Some(instantiate(
        &[],
        &base,
        &args,
        (0u32, 0u32).into(),
        &mut state.type_ctx(file_idx),
    ))
}

/// The one type two instantiations of a declaration make, when every pair of
/// their arguments lines up. An argument left at `any` takes the other side's
/// type. Answers `None` for anything else, which keeps two unrelated types the
/// union they are.
fn merge_instantiations(
    a: &DataType,
    b: &DataType,
    ctx: Ctx,
    state: &mut State<'_>,
) -> Option<DataType> {
    let (template, args_a) = state.generics.instantiation_of(a)?;
    let args_a: Vec<DataType> = args_a.to_vec();
    let (template_b, args_b) = state.generics.instantiation_of(b)?;
    if template != template_b || args_a.len() != args_b.len() {
        return None;
    }
    let mut merged = Vec::with_capacity(args_a.len());
    for (x, y) in args_a.iter().zip(args_b) {
        merged.push(match (x, y) {
            (DataType::Unknown, other) | (other, DataType::Unknown) => other.clone(),
            (x, y) if x == y => x.clone(),
            _ => return None,
        });
    }
    let base = state.generics.template_name(template).clone();
    Some(instantiate(
        &[],
        &base,
        &merged,
        (0u32, 0u32).into(),
        &mut state.type_ctx(ctx.file_idx),
    ))
}

/// The types a function body hands back.
///
/// A body that returns a value on one path has to return one on every path: a
/// call that reaches the end of the body, or leaves through a bare `return;`,
/// has nothing to hand back, and the value the caller would read is whatever
/// the last call left behind. That is reported at the function rather than
/// folded in as a `null` the caller cannot tell from one the body wrote.
pub fn track_returns(
    content: &[Expr],
    v: &mut Vec<Variable>,
    ctx: Ctx,
    state: &mut State<'_>,
    fn_name: &str,
    fn_id: usize,
) -> Vec<DataType> {
    // A `?` the walk types is a return of the `None` or the `Err` its operand
    // can hold; see `Expr::Propagate`.
    state.propagations.push(Vec::new());
    let mut flow = track_return_flow(content, v, ctx, state, fn_name);
    let propagated = state.propagations.pop().unwrap_or_default();
    // A declared return type is what the caller reads, and each `?` is checked
    // against it where it is compiled, which names the `?` in the report.
    let declared = state.fns[fn_id].return_type.is_some()
        || state.fns[fn_id]
            .generics
            .as_ref()
            .is_some_and(|g| g.return_type.is_some());
    for operand in propagated.into_iter().filter(|_| !declared) {
        if let Some(failure) = propagated_failure_type(&operand, state) {
            add_return_type(&mut flow.types, failure, ctx, state);
        }
    }
    let mut shapes = ReturnShapes::default();
    collect_return_shapes(content, &mut shapes);
    if shapes.value && (shapes.bare || !flow.always_returns) {
        // The report names the function as it was declared: a closure has no
        // name of its own, whatever the call site bound it to.
        let func = &state.fns[fn_id];
        let declared = (!func.name.starts_with(ANON_FN_PREFIX)).then_some(func.name.as_str());
        error_missing_return(declared, func.name_span, ctx.file_idx, state.sources);
    }
    flow.types
}

struct FnReturnFlow {
    types: Vec<DataType>,
    always_returns: bool,
}

fn track_scoped_returns(
    code: &[Expr],
    v: &mut Vec<Variable>,
    ctx: Ctx,
    state: &mut State<'_>,
    fn_name: &str,
) -> FnReturnFlow {
    let v_len = v.len();
    let flow = track_return_flow(code, v, ctx, state, fn_name);
    v.truncate(v_len);
    flow
}

fn track_condition_returns(
    condition: &Expr,
    code: &[Expr],
    v: &mut Vec<Variable>,
    ctx: Ctx,
    state: &mut State<'_>,
    fn_name: &str,
) -> FnReturnFlow {
    let mut return_types = Vec::new();
    let first_branch_end = code
        .iter()
        .position(|expr| matches!(expr, Expr::ElseIfBlock(_, _, _) | Expr::ElseBlock(_)))
        .unwrap_or(code.len());

    // Each branch is walked with what its condition proved in scope.
    let v_len = v.len();
    crate::compiler::type_test::declare_condition_facts(condition, v, ctx, state);
    let first_flow = track_scoped_returns(&code[..first_branch_end], v, ctx, state, fn_name);
    v.truncate(v_len);
    let mut all_branches_return = first_flow.always_returns;
    let mut has_else = false;
    extend_return_types!(&mut return_types, first_flow.types, ctx, state);

    for expr in &code[first_branch_end..] {
        match expr {
            Expr::ElseIfBlock(condition, branch_code, _) => {
                crate::compiler::type_test::declare_condition_facts(condition, v, ctx, state);
                let flow = track_scoped_returns(branch_code, v, ctx, state, fn_name);
                v.truncate(v_len);
                all_branches_return &= flow.always_returns;
                extend_return_types!(&mut return_types, flow.types, ctx, state);
            }
            Expr::ElseBlock(branch_code) => {
                has_else = true;
                let flow = track_scoped_returns(branch_code, v, ctx, state, fn_name);
                all_branches_return &= flow.always_returns;
                extend_return_types!(&mut return_types, flow.types, ctx, state);
            }
            _ => {}
        }
    }

    FnReturnFlow {
        types: return_types,
        always_returns: has_else && all_branches_return,
    }
}

fn track_return_flow(
    content: &[Expr],
    v: &mut Vec<Variable>,
    ctx: Ctx,
    state: &mut State<'_>,
    fn_name: &str,
) -> FnReturnFlow {
    let mut return_types: Vec<DataType> = Vec::new();
    let mut threw = false;
    for expr in content {
        match expr {
            Expr::Condition(condition, code, _, _)
            | Expr::InlineCondition(condition, code, _, _) => {
                let flow = track_condition_returns(condition, code, v, ctx, state, fn_name);
                extend_return_types!(&mut return_types, flow.types, ctx, state);
                if flow.always_returns {
                    return FnReturnFlow {
                        types: return_types,
                        always_returns: true,
                    };
                }
            }
            Expr::ElseIfBlock(_, code, _) | Expr::ElseBlock(code) | Expr::EvalBlock(code) => {
                let flow = track_scoped_returns(code, v, ctx, state, fn_name);
                extend_return_types!(&mut return_types, flow.types, ctx, state);
                if flow.always_returns {
                    return FnReturnFlow {
                        types: return_types,
                        always_returns: true,
                    };
                }
            }
            // A `loop` is left through a `break` or a `return`, so one with no
            // break of its own never falls through to what follows it. A body
            // that returns at its end still leaves through a break written
            // before that return, so the break alone decides.
            Expr::LoopBlock(code) => {
                let flow = track_scoped_returns(code, v, ctx, state, fn_name);
                extend_return_types!(&mut return_types, flow.types, ctx, state);
                if !block_breaks(code) {
                    return FnReturnFlow {
                        types: return_types,
                        always_returns: true,
                    };
                }
            }
            Expr::VarDeclare(name, expr, annotation) => {
                let declared = annotation
                    .as_ref()
                    .map(|a| a.ty.to_datatype(&mut state.type_ctx(ctx.file_idx)));
                let var_type = match &declared {
                    Some(declared) => declared.clone(),
                    None => expr.infer_type(v, ctx, state),
                };
                v.push(Variable {
                    declared,
                    name: name.clone(),
                    register_id: 0,
                    cell: false,
                    var_type,
                });
            }
            Expr::VarAssign(name, expr, _, _) => {
                if v.iter()
                    .rfind(|var| &var.name == name)
                    .is_some_and(|var| var.declared.is_none())
                {
                    let var_type = expr.infer_type(v, ctx, state);
                    if let Some(var) = v.iter_mut().rfind(|var| &var.name == name) {
                        var.var_type = var_type;
                    }
                }
            }
            // A `while true` is a `loop` under another spelling and is left
            // the same way.
            Expr::WhileBlock(condition, code, _) => {
                let v_len = v.len();
                crate::compiler::type_test::declare_condition_facts(condition, v, ctx, state);
                let flow = track_scoped_returns(code, v, ctx, state, fn_name);
                v.truncate(v_len);
                extend_return_types!(&mut return_types, flow.types, ctx, state);
                if matches!(**condition, Expr::Bool(true)) && !block_breaks(code) {
                    return FnReturnFlow {
                        types: return_types,
                        always_returns: true,
                    };
                }
            }
            Expr::IntForLoop(var_name, _, _, code, _, _) => {
                let v_len = v.len();
                v.push(Variable {
                    declared: None,
                    name: var_name.clone(),
                    register_id: 0,
                    cell: false,
                    var_type: DataType::Int,
                });
                let flow = track_return_flow(code, v, ctx, state, fn_name);
                extend_return_types!(&mut return_types, flow.types, ctx, state);
                v.truncate(v_len);
            }
            Expr::ForLoop(var_name, array_expr, array_code, span) => {
                let inferred_collection_type = array_expr.infer_type(v, ctx, state);
                let elem_type = match inferred_collection_type {
                    DataType::Array(inner) => inner.map_or(DataType::Unknown, |t| *t),
                    DataType::String => DataType::String,
                    DataType::Unknown => DataType::Unknown,
                    // A map iterates its keys.
                    DataType::Map(m) => m.0.unwrap_or(DataType::Unknown),
                    // A function whose return type is inferred has its body
                    // walked before the loop is compiled, so a loop over a
                    // value nothing can iterate arrives here first and reports
                    // what the compile stage would have.
                    t => error_type_not_indexable(
                        &t,
                        *span,
                        true,
                        ctx.file_idx,
                        state.sources,
                        state.type_names(),
                    ),
                };
                let v_len = v.len();
                if var_name.as_str() != "_" {
                    v.push(Variable {
                        declared: None,
                        name: var_name.clone(),
                        register_id: 0,
                        cell: false,
                        var_type: elem_type,
                    });
                }
                let flow = track_return_flow(array_code, v, ctx, state, fn_name);
                extend_return_types!(&mut return_types, flow.types, ctx, state);
                v.truncate(v_len);
            }
            // The statements that say what a collection a `let` left empty
            // holds. This walk runs over the body before the compile walk
            // lowers it, so it applies the same pins; without them a read
            // written in a `return` sees the empty-literal placeholder while
            // the same read written anywhere else sees the pinned type.
            Expr::ObjFunctionCall(obj, args, namespace, _, _, _, _)
                if namespace.last().unwrap().as_str() == "push" && args.len() == 1 =>
            {
                let element = args[0].infer_type(v, ctx, state);
                pin_pushed_element(obj, &element, v);
            }
            Expr::ArrayModify(obj, key, value, _, _)
                if matches!(obj.infer_type(v, ctx, state), DataType::Map(_)) =>
            {
                let key = key.infer_type(v, ctx, state);
                let value = value.infer_type(v, ctx, state);
                pin_inserted_entry(obj, &key, &value, v);
            }
            // A `throw` or an `exit` never comes back, so the path it ends is
            // one the function returns on: a match arm or a catch that only
            // raises leaves the other arms to answer. The walk goes on past
            // it, since a return written after the throw still says what the
            // function hands back. This comes before the arm that pins a
            // call's empty-literal arguments, which matches every call.
            Expr::FunctionCall(_, namespace, _, _, _)
                if namespace.len() == 1 && matches!(namespace[0].as_str(), "throw" | "exit") =>
            {
                threw = true;
            }
            Expr::FunctionCall(args, namespace, _, _, type_args) if type_args.is_empty() => {
                let (fn_name, path) = namespace.split_last().unwrap();
                if let Some(fn_id) = state.scope(ctx.file_idx).find_function(path, fn_name) {
                    let declared = specialized_arg_types(fn_id, &[], ctx, state);
                    pin_empty_literal_bindings(args, &declared, v);
                }
            }
            Expr::Match(scrutinee, arms, wildcard, span, _) => {
                let scrut_type = scrutinee.infer_type(v, ctx, state);
                let is_enum = matches!(scrut_type, DataType::Enum(_));
                if !is_enum {
                    crate::compiler::check_match_scrutinee_is_enum(
                        &scrut_type,
                        arms,
                        *span,
                        v,
                        ctx,
                        state,
                    );
                }
                let mut all_return = true;
                for (patterns, body) in arms {
                    let v_len = v.len();
                    if let DataType::Enum(enum_id) = scrut_type {
                        crate::compiler::declare_arm_bindings(
                            enum_id, patterns, *span, v, ctx, state,
                        );
                    }
                    let flow = track_return_flow(body, v, ctx, state, fn_name);
                    v.truncate(v_len);
                    all_return &= flow.always_returns;
                    extend_return_types!(&mut return_types, flow.types, ctx, state);
                }
                let exhaustive = if wildcard.is_some() {
                    if let Some(w) = wildcard {
                        let flow = track_scoped_returns(w, v, ctx, state, fn_name);
                        all_return &= flow.always_returns;
                        extend_return_types!(&mut return_types, flow.types, ctx, state);
                    }
                    true
                } else {
                    // An enum match with no wildcard is compile-time exhaustive.
                    is_enum
                };
                if exhaustive && all_return {
                    return FnReturnFlow {
                        types: return_types,
                        always_returns: true,
                    };
                }
            }
            // A try block and its catch are two paths out of the statement,
            // and the function returns on every path when both do. The catch
            // sees the error kind under the name the block binds.
            Expr::TryCatchBlock(try_code, err_var, catch_code) => {
                let try_flow = track_scoped_returns(try_code, v, ctx, state, fn_name);
                extend_return_types!(&mut return_types, try_flow.types, ctx, state);
                let v_len = v.len();
                v.push(Variable {
                    declared: None,
                    name: err_var.clone(),
                    register_id: 0,
                    cell: false,
                    var_type: DataType::String,
                });
                let catch_flow = track_return_flow(catch_code, v, ctx, state, fn_name);
                v.truncate(v_len);
                extend_return_types!(&mut return_types, catch_flow.types, ctx, state);
                if try_flow.always_returns && catch_flow.always_returns {
                    return FnReturnFlow {
                        types: return_types,
                        always_returns: true,
                    };
                }
            }
            Expr::ReturnVal(return_val) => {
                if let Some(val) = return_val.as_ref() {
                    let infered = val.infer_type(v, ctx, state);
                    // A returned name hands the function on as a value, and the
                    // caller has no declaration to read it against, so the type
                    // carries the signature the function was declared with.
                    let infered = if matches!(infered, DataType::Fn(_)) {
                        bare_fn_value_type(val, v, ctx, state).unwrap_or(infered)
                    } else {
                        infered
                    };
                    add_return_type(&mut return_types, infered, ctx, state);
                } else {
                    add_return_type(&mut return_types, DataType::Null, ctx, state);
                }
                return FnReturnFlow {
                    types: return_types,
                    always_returns: true,
                };
            }
            _ => {}
        }
    }
    FnReturnFlow {
        types: return_types,
        always_returns: threw,
    }
}

/// Whether a `break` written in `code` leaves the loop it belongs to. A break
/// inside a nested loop leaves that loop only, so nested loops are not
/// searched.
fn block_breaks(code: &[Expr]) -> bool {
    code.iter().any(|expr| match expr {
        Expr::Break => true,
        Expr::Condition(_, body, _, _)
        | Expr::InlineCondition(_, body, _, _)
        | Expr::ElseIfBlock(_, body, _)
        | Expr::ElseBlock(body)
        | Expr::EvalBlock(body) => block_breaks(body),
        Expr::TryCatchBlock(try_code, _, catch_code) => {
            block_breaks(try_code) || block_breaks(catch_code)
        }
        Expr::Match(_, arms, wildcard, _, _) => {
            arms.iter().any(|(_, body)| block_breaks(body))
                || wildcard.as_ref().is_some_and(|w| block_breaks(w))
        }
        _ => false,
    })
}

/// Infers the return type of a user function specialised for
/// `infered_arg_types`, caching the result on the function.
///
/// Shared by direct `FunctionCall`s and by `impl` method calls (which resolve
/// to a mangled free function with the receiver as argument 0).
/// `function_name` is only used for diagnostics inside `track_returns`.
///
/// `type_args` are the arguments a generic call named. They are part of the
/// specialisation key because a type parameter no argument mentions still
/// changes what the body builds.
/// Declares a closure's captures in `v`, ahead of its parameters, which shadow
/// a capture of the same name. A closure body reads what the closure captured,
/// so those names are in scope both while its return type is worked out and
/// while its body compiles.
pub fn push_capture_scope(
    v: &mut Vec<Variable>,
    captures: &[(SmolStr, DataType, Option<DataType>)],
) {
    for (name, capture_type, declared) in captures {
        v.push(Variable {
            declared: declared.clone(),
            name: name.clone(),
            register_id: 0,
            cell: true,
            var_type: capture_type.clone(),
        });
    }
}

pub fn infer_user_fn_return_type(
    fn_id: usize,
    infered_arg_types: &[DataType],
    type_args: &[DataType],
    function_name: &str,
    v: &mut Vec<Variable>,
    ctx: Ctx,
    state: &mut State<'_>,
) -> DataType {
    // The body is compiled at the types `handle_user_function` specialises on,
    // which pin an argument's open element type to what the parameter declares.
    // Infer against the same types, or the caller reads a return type from a
    // body that was never compiled that way. Reading the declarations costs a
    // clone, so the arguments are asked first whether any left one open.
    let pinned = if infered_arg_types.iter().any(has_open_element_type) {
        let declared_arg_types = specialized_arg_types(fn_id, type_args, ctx, state);
        pinned_arg_types(infered_arg_types, &declared_arg_types)
    } else {
        None
    };
    let infered_arg_types = pinned.as_deref().unwrap_or(infered_arg_types);

    let key = specialization_key(type_args, infered_arg_types);
    // Check the return type cache
    if let Some((_, ret)) = state.fns[fn_id]
        .return_type_cache
        .iter()
        .find(|(args, _)| arg_types_specialize_equal(args, &key))
    {
        return ret.clone();
    }

    let fn_ctx = Ctx {
        file_idx: state.fns[fn_id].src_file,
        ..ctx
    };
    // A declared return type is what the call hands back, read with this call's
    // type arguments bound so a generic `-> T[]` resolves to what it names. An
    // annotation naming a type parameter the call left unbound stays unread,
    // and the body says what comes back.
    state
        .generics
        .push_frame(fn_bindings(fn_id, type_args, state));
    let declared_return = specialized_return_type(fn_id, fn_ctx, state).map(|(t, _)| t);
    state.generics.pop_bindings();

    // Mutual-recursion cycle guard: a call reached while this function's return
    // type is still being worked out gets the declaration, or `Unknown` when
    // there is none, which breaks the cycle.
    let already_inferring = RETURN_TYPE_INFERRING.with(|s| s.borrow().contains(&fn_id));
    if already_inferring {
        return declared_return.unwrap_or(DataType::Unknown);
    }
    // A call can reach inference before anything checks how many arguments it
    // passes. The body cannot be walked with a parameter left unbound or an
    // argument bound to no parameter, so the call takes the declared type and
    // compiling it reports the count.
    if infered_arg_types.len() != state.fns[fn_id].args.len() {
        return declared_return.unwrap_or(DataType::Unknown);
    }

    let func = &state.fns[fn_id];
    let fn_args = func.args.clone();
    let fn_code = func.code.clone();
    let fn_captures = func.captures.clone();
    let v_len_before_args = v.len();
    push_capture_scope(v, &fn_captures);
    for (i, infered_type) in infered_arg_types.iter().cloned().enumerate() {
        // 0 => placeholder id, it's never used
        v.push(Variable {
            declared: None,
            name: fn_args[i].0.clone(),
            register_id: 0,
            cell: false,
            var_type: infered_type,
        });
    }

    RETURN_TYPE_INFERRING.with(|s| s.borrow_mut().insert(fn_id));

    // The body is walked whether or not a type is declared: the errors it holds
    // are reported here, in the same order either way.
    state
        .generics
        .push_frame(fn_bindings(fn_id, type_args, state));
    let fn_type = track_returns(&fn_code, v, fn_ctx, state, function_name, fn_id);
    state.generics.pop_bindings();

    RETURN_TYPE_INFERRING.with(|s| s.borrow_mut().remove(&fn_id));

    v.truncate(v_len_before_args);

    let body_type = if fn_type.is_empty() {
        // No tracked type means either no value is returned at all, or every
        // returned value was itself dynamic (return-type tracking records no
        // type for `Unknown`). A function handing back an `any` payload is
        // dynamic, not null.
        if check_if_returns_void(&fn_code) {
            DataType::Null
        } else {
            DataType::Unknown
        }
    } else {
        // If function returns anything, check if it returns the same thing each time
        DataType::Union(Box::from(fn_type)).check_poly()
    };
    let to_return = call_return_type(declared_return, body_type);

    // Cache the result
    state.fns[fn_id]
        .return_type_cache
        .push((key, to_return.clone()));

    to_return
}

/// The type a call to a function hands back, from what the function declares
/// and what its body returns.
///
/// A declared type wins: the call has the type the signature names, even where
/// the body returns something narrower. Only an element type the declaration
/// leaves open is taken from the body. With nothing declared, the body's type
/// is the call's.
#[must_use]
pub(crate) fn call_return_type(declared: Option<DataType>, body_type: DataType) -> DataType {
    match declared {
        Some(mut declared) => {
            pin_open_element_types(&mut declared, &body_type);
            declared
        }
        None => body_type,
    }
}

/// The `-> Type` annotation as it reads for the specialisation being compiled,
/// with the type parameters currently bound.
///
/// An annotation naming a parameter the call left unbound stays un-pinned, so
/// what the body returns is inferred rather than checked against a type that
/// has no value yet.
pub(crate) fn specialized_return_type(
    fn_id: usize,
    ctx: Ctx,
    state: &mut State<'_>,
) -> Option<(DataType, Span)> {
    let Some(generics) = state.fns[fn_id].generics.as_ref() else {
        return state.fns[fn_id].return_type.clone();
    };
    let unbound: Vec<SmolStr> = generics
        .params
        .iter()
        .filter(|param| !state.generics.names(param))
        .cloned()
        .collect();
    let generics = state.fns[fn_id].generics.as_ref()?;
    let annotation = generics.return_type.as_deref()?;
    if annotation.0.mentions_any(&unbound) {
        return state.fns[fn_id].return_type.clone();
    }
    let (return_type, return_span) = annotation.clone();
    let file_idx = generics.file_idx;
    let mut base = state.type_ctx(ctx.file_idx);
    let mut type_ctx = base.reborrow(file_idx);
    Some((return_type.to_datatype(&mut type_ctx), return_span))
}

/// The parameter types this call specialises on.
///
/// Without type arguments these are the function's own declared types, where an
/// annotation naming a type parameter was left un-pinned. A call that names its
/// type arguments resolves the annotations again with them bound, which is what
/// makes `first<int>(xs)` reject a `float[]`.
pub(crate) fn specialized_arg_types(
    fn_id: usize,
    type_args: &[DataType],
    ctx: Ctx,
    state: &mut State<'_>,
) -> Vec<Option<DataType>> {
    let declared = state.fns[fn_id]
        .args
        .iter()
        .map(|(_, t)| t.clone())
        .collect::<Vec<Option<DataType>>>();
    if type_args.is_empty() {
        return declared;
    }
    let Some(generics) = state.fns[fn_id].generics.as_ref() else {
        return declared;
    };
    let arg_types = generics.arg_types.clone();
    let file_idx = generics.file_idx;
    let frame = fn_bindings(fn_id, type_args, state);
    let mut base = state.type_ctx(ctx.file_idx);
    let mut type_ctx = base.reborrow(file_idx);
    type_ctx.generics.push_frame(frame);
    let resolved = arg_types
        .iter()
        .map(|t| t.as_ref().map(|t| t.to_datatype(&mut type_ctx)))
        .collect();
    type_ctx.generics.pop_bindings();
    resolved
}

/// The argument types a call specialises on: what its arguments infer to, with
/// any element type they left open filled in from `declared_arg_types`, the
/// parameter declarations as [`specialized_arg_types`] reads them.
///
/// Answers `None` when no argument left an element type open, which is every
/// call that passes no empty collection literal.
pub(crate) fn pinned_arg_types(
    infered_arg_types: &[DataType],
    declared_arg_types: &[Option<DataType>],
) -> Option<Vec<DataType>> {
    if !infered_arg_types.iter().any(has_open_element_type) {
        return None;
    }
    let mut pinned = infered_arg_types.to_vec();
    for (inferred, declared) in pinned.iter_mut().zip(declared_arg_types) {
        if let Some(declared) = declared {
            pin_open_element_types(inferred, declared);
        }
    }
    Some(pinned)
}

/// Whether this type leaves an element type open, which is what an empty array
/// or map literal produces.
#[must_use]
fn has_open_element_type(ty: &DataType) -> bool {
    match ty {
        DataType::Array(None) => true,
        DataType::Array(Some(element)) => has_open_element_type(element),
        DataType::Map(entry) => has_open_slot(entry.0.as_ref()) || has_open_slot(entry.1.as_ref()),
        _ => false,
    }
}

/// Whether one half of a map's type is open: either the map names no type there
/// at all, or what it names holds an open element type itself.
#[must_use]
fn has_open_slot(slot: Option<&DataType>) -> bool {
    slot.is_none_or(has_open_element_type)
}

/// The key one specialisation of a function is found by: the type arguments the
/// call named, then the argument types it passed.
#[must_use]
pub fn specialization_key(type_args: &[DataType], arg_types: &[DataType]) -> Box<[DataType]> {
    let mut key: Vec<DataType> = Vec::with_capacity(type_args.len() + arg_types.len());
    key.extend(type_args.iter().cloned());
    key.extend(arg_types.iter().cloned());
    key.into_boxed_slice()
}

/// The type parameters bound while a function's body is compiled: what its
/// enclosing `impl` block fixed, plus what the call site named.
///
/// A parameter neither of them mentions is recorded as unnamed, which stands
/// for `any`. A call never has to name its type arguments, so `signal("x")` and
/// `signal<any>("x")` compile the same body; without this the body could not
/// write `T` in a type position at all.
#[must_use]
pub fn fn_bindings(fn_id: usize, type_args: &[DataType], state: &State<'_>) -> BindingFrame {
    let Some(generics) = state.fns[fn_id].generics.as_ref() else {
        return BindingFrame::default();
    };
    let mut named: Vec<(SmolStr, DataType)> = generics.bindings.to_vec();
    for (param, arg) in generics.params.iter().zip(type_args) {
        named.push((param.clone(), arg.clone()));
    }
    let unnamed: Box<[SmolStr]> = generics
        .params
        .iter()
        .filter(|param| !named.iter().any(|(bound, _)| bound == *param))
        .cloned()
        .collect();
    BindingFrame {
        named: named.into_boxed_slice(),
        unnamed,
    }
}

/// The type a builtin method returns for a receiver, applied across a union
/// the way the compile-time receiver check does: a union is accepted only when
/// every member is, so the answer is the union of the per-member answers.
///
/// `rule` gives the return type for one receiver type and `None` for a receiver
/// the method does not take, which is the set `builtin_methods` rejects.
fn builtin_method_return(
    obj_type: &DataType,
    rule: fn(&DataType) -> Option<DataType>,
) -> Option<DataType> {
    let DataType::Union(members) = obj_type else {
        return rule(obj_type);
    };
    let mut types: Vec<DataType> = Vec::with_capacity(members.len());
    for member in members {
        let member_type = rule(member)?;
        if !types.contains(&member_type) {
            types.push(member_type);
        }
    }
    Some(DataType::Union(types.into_boxed_slice()).check_poly())
}

/// Whether a struct field holds a function.
///
/// A field whose type names one function lets `obj.field(x)` lower to the same
/// direct call `fs[0](x)` does. A field declared `fn(...)` holds a function
/// value instead, and the call through it dispatches on what the value carries.
#[must_use]
pub(crate) fn struct_field_holds_fn(struct_id: u16, field: &str, state: &State<'_>) -> bool {
    state.structs[struct_id as usize]
        .fields
        .iter()
        .find(|(name, _, _)| name == field)
        .is_some_and(|(_, field_type, _)| {
            matches!(field_type, DataType::Fn(_) | DataType::FnValue(_))
        })
}

/// The type an operator produces on operands the built-in rules do not accept.
///
/// A struct or an enum reaches the method its type defines for that operator;
/// anything else is the operator error it has always been. A unary operator is
/// reported against its one operand, which is the shape [`error_op`] reads from
/// a `null` left type.
#[allow(clippy::too_many_arguments)]
fn operator_result_type(
    symbol: &str,
    l: &Expr,
    r: Option<&Expr>,
    t_l: &DataType,
    t_r: &DataType,
    span_l: Span,
    span_r: Span,
    v: &mut Vec<Variable>,
    ctx: Ctx,
    state: &mut State<'_>,
) -> DataType {
    if let Some(result) =
        infer_operator_method(symbol, l, r, t_l, t_r, span_l, span_r, v, ctx, state)
    {
        return result;
    }
    let reported = if symbol == UNARY_MINUS_METHOD {
        "-"
    } else {
        symbol
    };
    let (report_l, report_r) = if r.is_none() {
        (&DataType::Null, t_l)
    } else {
        (t_l, t_r)
    };
    error_op(
        report_l,
        report_r,
        reported,
        span_l,
        span_r,
        ctx.file_idx,
        state.sources,
        state.type_names(),
    );
}

impl Expr {
    /// Infers this expression's static [`DataType`] without emitting code.
    ///
    /// # Panics
    ///
    /// Panics when a call node carries an empty namespace path, which the
    /// parser never produces.
    pub fn infer_type(&self, v: &mut Vec<Variable>, ctx: Ctx, state: &mut State<'_>) -> DataType {
        match self {
            Self::Var(name, span) => {
                if let Some(var) = v.iter().rfind(|x| &x.name == name) {
                    var.var_type.clone()
                } else if let Some(fn_id) = state.scope(ctx.file_idx).find_function(&[], name) {
                    // A bare identifier that names a function is a function
                    // reference (a compile-time value passed to a higher-order
                    // function). Its static type is the callee's Fn id.
                    DataType::Fn(fn_id as u16)
                } else if let Some((enum_id, _)) =
                    variant_constructor_at(std::slice::from_ref(name), &[], *span, ctx, state)
                {
                    DataType::Enum(enum_id)
                } else {
                    error_unknown_variable(name, *span, v, ctx.file_idx, state.sources);
                }
            }
            Self::Float(_) => DataType::Float,
            Self::Int(_) => DataType::Int,
            Self::String(_) => DataType::String,
            Self::Bool(_) | Self::Eq(..) | Self::NotEq(..) => DataType::Bool,
            // A statement match has no value. One used as a value has the
            // type its arms give, each read with the names its pattern binds.
            Self::Null | Self::Match(_, _, _, _, false) => DataType::Null,
            Self::Array(x, _) => DataType::Array(if x.is_empty() {
                None
            } else {
                let elem_types = x
                    .iter()
                    .map(|elem| elem.infer_type(v, ctx, state))
                    .collect::<Vec<DataType>>();
                let elem_type = merge_fn_types(&elem_types).unwrap_or_else(|| {
                    elem_types
                        .into_iter()
                        .find(|elem_type| *elem_type != DataType::Unknown)
                        .unwrap_or(DataType::Unknown)
                });
                Some(Box::from(elem_type))
            }),
            Self::Map(kv_pairs, _) => {
                if kv_pairs.is_empty() {
                    // An empty map literal has no key/value types yet, like an
                    // empty array (`Array(None)`); `insert` fills them in.
                    DataType::Map(Box::from((None, None)))
                } else {
                    let entry_types = kv_pairs
                        .iter()
                        .map(|(key, _, value, _)| {
                            (
                                key.infer_type(v, ctx, state),
                                value.infer_type(v, ctx, state),
                            )
                        })
                        .collect::<Vec<(DataType, DataType)>>();
                    let value_types = entry_types
                        .iter()
                        .map(|(_, val_t)| val_t.clone())
                        .collect::<Vec<DataType>>();
                    let kv_type = entry_types
                        .into_iter()
                        .find(|(key_t, val_t)| {
                            key_t != &DataType::Unknown || val_t != &DataType::Unknown
                        })
                        .map_or(
                            (Some(DataType::Unknown), Some(DataType::Unknown)),
                            |(key_t, val_t)| (Some(key_t), Some(val_t)),
                        );
                    // A map whose values are two different functions holds a
                    // function value, the same as a list does.
                    let kv_type = match merge_fn_types(&value_types) {
                        Some(merged) => (kv_type.0, Some(merged)),
                        None => kv_type,
                    };
                    DataType::Map(Box::from(kv_type))
                }
            }
            Self::Add(x, y, span_l, span_r) => {
                match (x.infer_type(v, ctx, state), y.infer_type(v, ctx, state)) {
                    (DataType::Unknown, t) | (t, DataType::Unknown) => t,
                    (DataType::Float, DataType::Float) => DataType::Float,
                    (DataType::Int, DataType::Int) => DataType::Int,
                    (DataType::String, DataType::String) => DataType::String,
                    (DataType::Array(t1), DataType::Array(t2)) => DataType::Array(t1.or(t2)),
                    (l, r) => operator_result_type(
                        "+",
                        x,
                        Some(&**y),
                        &l,
                        &r,
                        *span_l,
                        *span_r,
                        v,
                        ctx,
                        state,
                    ),
                }
            }
            Self::Mul(x, y, span_l, span_r)
            | Self::Div(x, y, span_l, span_r)
            | Self::Sub(x, y, span_l, span_r)
            | Self::Mod(x, y, span_l, span_r)
            | Self::Pow(x, y, span_l, span_r) => {
                match (x.infer_type(v, ctx, state), y.infer_type(v, ctx, state)) {
                    (DataType::Unknown, t) | (t, DataType::Unknown)
                        if matches!(t, DataType::Float | DataType::Int | DataType::Unknown) =>
                    {
                        t
                    }
                    (DataType::Float, DataType::Float) => DataType::Float,
                    (DataType::Int, DataType::Int) => DataType::Int,
                    (l, r) => operator_result_type(
                        symbol_of_expr(self),
                        x,
                        Some(&**y),
                        &l,
                        &r,
                        *span_l,
                        *span_r,
                        v,
                        ctx,
                        state,
                    ),
                }
            }
            Self::BitAnd(x, y, span_l, span_r)
            | Self::BitOr(x, y, span_l, span_r)
            | Self::BitXor(x, y, span_l, span_r)
            | Self::Shl(x, y, span_l, span_r)
            | Self::Shr(x, y, span_l, span_r) => {
                match (x.infer_type(v, ctx, state), y.infer_type(v, ctx, state)) {
                    (DataType::Unknown, t) | (t, DataType::Unknown)
                        if matches!(t, DataType::Int | DataType::Unknown) =>
                    {
                        t
                    }
                    (DataType::Int, DataType::Int) => DataType::Int,
                    (l, r) => operator_result_type(
                        symbol_of_expr(self),
                        x,
                        Some(&**y),
                        &l,
                        &r,
                        *span_l,
                        *span_r,
                        v,
                        ctx,
                        state,
                    ),
                }
            }
            Self::Sup(x, y, span_l, span_r)
            | Self::SupEq(x, y, span_l, span_r)
            | Self::Inf(x, y, span_l, span_r)
            | Self::InfEq(x, y, span_l, span_r) => {
                match (x.infer_type(v, ctx, state), y.infer_type(v, ctx, state)) {
                    (DataType::Unknown, DataType::Float | DataType::Int)
                    | (DataType::Float | DataType::Int, DataType::Unknown)
                    | (DataType::Float, DataType::Float)
                    | (DataType::Int, DataType::Int)
                    | (DataType::String, DataType::String) => DataType::Bool,
                    (l, r) => operator_result_type(
                        symbol_of_expr(self),
                        x,
                        Some(&**y),
                        &l,
                        &r,
                        *span_l,
                        *span_r,
                        v,
                        ctx,
                        state,
                    ),
                }
            }
            // `is` answers a bool; resolving its right side reports a test the
            // operand's type rules out, or a name that is neither a type nor
            // a variant.
            Self::Is(operand, target, operand_span, target_span) => {
                let have = operand.infer_type(v, ctx, state);
                crate::compiler::type_test::resolve_test(
                    &have,
                    target,
                    *operand_span,
                    *target_span,
                    ctx,
                    state,
                );
                DataType::Bool
            }
            Self::Cast(_, target, _, target_span) => {
                crate::compiler::type_test::resolve_type(target, *target_span, ctx, state)
            }
            Self::BoolAnd(x, y, span_l, span_r) | Self::BoolOr(x, y, span_l, span_r) => {
                // The right of an `&&` runs only where the left held, so it
                // sees what an `is` on the left proved.
                let x_type = x.infer_type(v, ctx, state);
                let v_len = v.len();
                if matches!(self, Self::BoolAnd(..)) {
                    crate::compiler::type_test::declare_condition_facts(x, v, ctx, state);
                }
                let y_type = y.infer_type(v, ctx, state);
                v.truncate(v_len);
                match (x_type, y_type) {
                    (DataType::Unknown | DataType::Bool, DataType::Bool)
                    | (DataType::Bool, DataType::Unknown) => DataType::Bool,
                    (l, r) => {
                        error_op(
                            &l,
                            &r,
                            "&&",
                            *span_l,
                            *span_r,
                            ctx.file_idx,
                            state.sources,
                            state.type_names(),
                        );
                    }
                }
            }
            Self::Neg(e, span_l, span_r) => match e.infer_type(v, ctx, state) {
                DataType::Float => DataType::Float,
                DataType::Int => DataType::Int,
                DataType::Unknown => DataType::Unknown,
                operand_type => operator_result_type(
                    UNARY_MINUS_METHOD,
                    e,
                    None,
                    &operand_type,
                    &operand_type,
                    *span_l,
                    *span_r,
                    v,
                    ctx,
                    state,
                ),
            },
            Self::BitNot(e, span_l, span_r) => match e.infer_type(v, ctx, state) {
                DataType::Int => DataType::Int,
                DataType::Unknown => DataType::Unknown,
                operand_type => operator_result_type(
                    "~",
                    e,
                    None,
                    &operand_type,
                    &operand_type,
                    *span_l,
                    *span_r,
                    v,
                    ctx,
                    state,
                ),
            },
            Self::BoolNeg(e, span_l, span_r) => match e.infer_type(v, ctx, state) {
                DataType::Bool => DataType::Bool,
                operand_type => error_op(
                    &DataType::Null,
                    &operand_type,
                    "!",
                    *span_l,
                    *span_r,
                    ctx.file_idx,
                    state.sources,
                    state.type_names(),
                ),
            },
            Self::Propagate(operand, span) => {
                let operand_type = operand.infer_type(v, ctx, state);
                let Some((success, _)) = propagation_sides(&operand_type, state) else {
                    crate::compiler::compiler_errors::error_propagate_operand(
                        &operand_type,
                        *span,
                        ctx.file_idx,
                        state.sources,
                        state.type_names(),
                    );
                };
                if let Some(frame) = state.propagations.last_mut()
                    && !frame.contains(&operand_type)
                {
                    frame.push(operand_type);
                }
                success
            }
            Self::ArrayGetIndex(array, _, span) => match array.infer_type(v, ctx, state) {
                DataType::Array(array_type) => array_type.map_or(DataType::Null, |t| *t),
                // `m[k]` reads the value stored under `k`.
                DataType::Map(m) => m.1.unwrap_or(DataType::Unknown),
                DataType::String => DataType::String,
                DataType::Unknown => DataType::Unknown,
                t => error_type_not_indexable(
                    &t,
                    *span,
                    false,
                    ctx.file_idx,
                    state.sources,
                    state.type_names(),
                ),
            },
            Self::GetStructField(s, field, struct_span, field_span) => {
                let s = s.infer_type(v, ctx, state);
                if let DataType::Struct(s_id) = s {
                    state.structs[s_id as usize]
                        .fields
                        .iter()
                        .find(|x| &x.0 == field)
                        .unwrap_or_else(|| {
                            let s = &state.structs[s_id as usize];
                            error_struct_unknown_field(
                                ctx.file_idx,
                                *field_span,
                                field,
                                &s.name,
                                &s.fields,
                                state.sources,
                            )
                        })
                        .1
                        .clone()
                } else {
                    error_invalid_type(
                        &DataType::Struct(0),
                        &s,
                        *struct_span,
                        None,
                        None,
                        ctx.file_idx,
                        state.sources,
                        TypeNames {
                            structs: state.structs,
                            enums: state.enums,
                        },
                    );
                }
            }
            Self::ArrayGetSlice(array, _, _, span) => match array.infer_type(v, ctx, state) {
                DataType::Array(array_type) => DataType::Array(array_type),
                DataType::String => DataType::String,
                DataType::Unknown => DataType::Unknown,
                t => error_type_not_indexable(
                    &t,
                    *span,
                    false,
                    ctx.file_idx,
                    state.sources,
                    state.type_names(),
                ),
            },
            // The return type of an indirect call is the return type of the
            // function the callee's type names, at the argument types this
            // call site passes.
            Self::CallValue(callee, args, span, _) => {
                match resolve_callee(callee, *span, v, ctx, state) {
                    Callee::Direct(fn_id) => {
                        let infered_arg_types = args
                            .iter()
                            .map(|x| x.infer_type(v, ctx, state))
                            .collect::<Vec<DataType>>();
                        let fn_name = state.fns[fn_id].name.clone();
                        infer_user_fn_return_type(
                            fn_id,
                            &infered_arg_types,
                            &[],
                            &fn_name,
                            v,
                            ctx,
                            state,
                        )
                    }
                    Callee::Indirect(fn_type) => {
                        indirect_return_type(&fn_type, args, v, ctx, state)
                    }
                }
            }
            Self::FunctionCall(args, namespace, span, _, type_args) => {
                // `S::default()` is the struct's default; see
                // `handle_functions`, which lowers it in the same order.
                if let Some(struct_id) =
                    struct_default_target(namespace, args, type_args, *span, ctx, state)
                {
                    return DataType::Struct(struct_id);
                }
                reject_default_default(namespace, *span, ctx, state);
                if let Some(fn_id) = path_call_target(namespace, type_args, *span, ctx, state) {
                    let arg_types: Vec<DataType> =
                        args.iter().map(|a| a.infer_type(v, ctx, state)).collect();
                    let fn_name = state.fns[fn_id].name.clone();
                    return infer_user_fn_return_type(
                        fn_id,
                        &arg_types,
                        &[],
                        &fn_name,
                        v,
                        ctx,
                        state,
                    );
                }
                // A call written with type arguments names either a variant of a
                // generic enum (`Slot<int>::Filled(x)`) or a generic function,
                // which may itself sit behind a module alias
                // (`m::first<int>(xs)`).
                if !type_args.is_empty() {
                    if type_args_name_a_variant(namespace, ctx, state) {
                        let (enum_id, _) =
                            resolve_generic_variant(namespace, type_args, *span, ctx, state);
                        return DataType::Enum(enum_id);
                    }
                    let len = namespace.len() - 1;
                    let fn_name = namespace[len].clone();
                    let (fn_id, call_type_args) = resolve_generic_call(
                        &namespace[..len],
                        &fn_name,
                        type_args,
                        *span,
                        ctx,
                        state,
                    );
                    let infered_arg_types = args
                        .iter()
                        .map(|x| x.infer_type(v, ctx, state))
                        .collect::<Vec<DataType>>();
                    return infer_user_fn_return_type(
                        fn_id,
                        &infered_arg_types,
                        &call_type_args,
                        &fn_name,
                        v,
                        ctx,
                        state,
                    );
                }
                // A qualified enum-variant construction (`Color::Red(x)`) has an
                // enum type; intercept before the function paths, which is where
                // `handle_functions` intercepts it too.
                if namespace.len() >= 2 {
                    let arg_types = args
                        .iter()
                        .map(|x| x.infer_type(v, ctx, state))
                        .collect::<Vec<DataType>>();
                    if let Some((enum_id, _)) =
                        variant_constructor_at(namespace, &arg_types, *span, ctx, state)
                    {
                        return DataType::Enum(enum_id);
                    }
                }
                // What follows resolves the name in the order `handle_functions`
                // lowers it: the path picks the family, and inside a family a
                // function in scope wins over a built-in of the same name. One
                // flat table of built-in names, read before the scope, is what
                // typed a program's own `read` as the string `fs::read` returns.
                let (fn_name, path) = namespace.split_last().unwrap();
                let infered_args = |v: &mut Vec<Variable>, state: &mut State<'_>| {
                    args.iter()
                        .map(|x| x.infer_type(v, ctx, state))
                        .collect::<Vec<DataType>>()
                };
                if !path.is_empty() {
                    // A call into a `host` or `dylib` block takes its type from
                    // the declaration: `gpio::read` is whatever its block says it
                    // is, not the `read` that returns a string.
                    if let Some(declared) = declared_return_type(namespace, state) {
                        return declared;
                    }
                    let Some(fn_id) = state.scope(ctx.file_idx).find_function(path, fn_name) else {
                        error_unknown_function_in_namespace(
                            fn_name,
                            path,
                            *span,
                            ctx.file_idx,
                            state,
                        );
                    };
                    let infered_arg_types = infered_args(v, state);
                    return infer_user_fn_return_type(
                        fn_id,
                        &infered_arg_types,
                        &[],
                        fn_name,
                        v,
                        ctx,
                        state,
                    );
                }
                // A call to a function-typed parameter (a higher-order function
                // calling the function it was handed): the callee comes from the
                // parameter's static Fn type. Lowering reads the same function
                // off the scope symbol `handle_user_function` declares for that
                // parameter, which inference has not run yet.
                // A name that holds a function value: what it hands back is
                // what the type says, since no one function is what it names.
                if let Some(DataType::FnValue(fn_type)) = v
                    .iter()
                    .rfind(|var| var.name.as_str() == fn_name.as_str())
                    .map(|var| var.var_type.clone())
                {
                    return indirect_return_type(&fn_type, args, v, ctx, state);
                }
                if let Some(DataType::Fn(fn_id)) = v
                    .iter()
                    .rfind(|var| var.name.as_str() == fn_name.as_str())
                    .map(|var| var.var_type.clone())
                {
                    let infered_arg_types = infered_args(v, state);
                    return infer_user_fn_return_type(
                        fn_id as usize,
                        &infered_arg_types,
                        &[],
                        fn_name,
                        v,
                        ctx,
                        state,
                    );
                }
                if let Some(fn_id) = state.scope(ctx.file_idx).find_function(&[], fn_name) {
                    let infered_arg_types = infered_args(v, state);
                    return infer_user_fn_return_type(
                        fn_id,
                        &infered_arg_types,
                        &[],
                        fn_name,
                        v,
                        ctx,
                        state,
                    );
                }
                if let Some(return_type) =
                    builtin_fn_return_type(fn_name, state.namespaces.is_std(ctx.file_idx))
                {
                    return return_type;
                }
                // An unqualified call whose name is an enum variant (`Some(x)`)
                // constructs that variant. Functions above keep priority.
                let arg_types = infered_args(v, state);
                if let Some((enum_id, _)) =
                    variant_constructor_at(namespace, &arg_types, *span, ctx, state)
                {
                    return DataType::Enum(enum_id);
                }
                error_unknown_function(
                    fn_name,
                    *span,
                    state.scope(ctx.file_idx),
                    ctx.file_idx,
                    state.sources,
                )
            }
            Self::ObjFunctionCall(
                obj,
                args,
                namespace,
                obj_span,
                fn_span,
                args_indexes,
                type_args,
            ) => {
                let method = namespace.last().unwrap().as_str();
                // A block's name is a namespace, not a value, so a dot call on
                // one is refused before the receiver is typed, which would
                // report the name as an unknown variable.
                if namespace.len() == 1 {
                    reject_block_dot_call(obj, method, v, ctx, state);
                }
                let obj_type = obj.infer_type(v, ctx, state);
                // A user-defined impl method resolves by the receiver's static
                // struct type to the mangled free function `Type#method`; its
                // return type is inferred exactly like any free function's. This
                // is checked before the builtin-method table so a struct method
                // that happens to share a name with a builtin (e.g. `len`) uses
                // its own return type rather than the builtin's.
                if let DataType::Struct(struct_id) = obj_type {
                    let struct_name = state.structs[struct_id as usize].name.clone();
                    let mangled = mangle_method(&struct_name, method);
                    if let Some(fn_id) = state.fns.iter().position(|f| f.name == mangled) {
                        check_receiver(fn_id, method, *fn_span, ctx, state);
                        let mut arg_types: Vec<DataType> = Vec::with_capacity(args.len() + 1);
                        arg_types.push(DataType::Struct(struct_id));
                        for a in args {
                            arg_types.push(a.infer_type(v, ctx, state));
                        }
                        let call_type_args = if type_args.is_empty() {
                            Vec::new()
                        } else {
                            resolve_call_type_args(fn_id, method, type_args, *fn_span, ctx, state)
                        };
                        return infer_user_fn_return_type(
                            fn_id,
                            &arg_types,
                            &call_type_args,
                            &mangled,
                            v,
                            ctx,
                            state,
                        );
                    }
                    // No method of that name: a field holding a function is
                    // called through the same dot, so `obj.field(x)` calls what
                    // the field holds. A method wins, which is why this comes
                    // second.
                    if struct_field_holds_fn(struct_id, method, state) {
                        let callee = Self::GetStructField(
                            Box::new(obj.as_ref().clone()),
                            SmolStr::new(method),
                            *obj_span,
                            *fn_span,
                        );
                        return Self::CallValue(
                            Box::new(callee),
                            Box::from(args.to_vec()),
                            *fn_span,
                            Box::from(args_indexes.to_vec()),
                        )
                        .infer_type(v, ctx, state);
                    }
                    // Neither: mirror the compile-time error path so inference
                    // does not hit the builtin arms with a struct type.
                    crate::compiler::compiler_errors::error_no_such_method(
                        method,
                        &struct_name,
                        *fn_span,
                        ctx.file_idx,
                        state.sources,
                    );
                }
                if let DataType::Enum(enum_id) = obj_type {
                    let enum_name = state.enums[enum_id as usize].name.clone();
                    let mangled = mangle_method(&enum_name, method);
                    if let Some(fn_id) = state.fns.iter().position(|f| f.name == mangled) {
                        check_receiver(fn_id, method, *fn_span, ctx, state);
                        let mut arg_types: Vec<DataType> = Vec::with_capacity(args.len() + 1);
                        arg_types.push(DataType::Enum(enum_id));
                        for a in args {
                            arg_types.push(a.infer_type(v, ctx, state));
                        }
                        let call_type_args = if type_args.is_empty() {
                            Vec::new()
                        } else {
                            resolve_call_type_args(fn_id, method, type_args, *fn_span, ctx, state)
                        };
                        return infer_user_fn_return_type(
                            fn_id,
                            &arg_types,
                            &call_type_args,
                            &mangled,
                            v,
                            ctx,
                            state,
                        );
                    }
                    crate::compiler::compiler_errors::error_no_such_method(
                        method,
                        &enum_name,
                        *fn_span,
                        ctx.file_idx,
                        state.sources,
                    );
                }
                if method == "parse" && obj_type == DataType::String {
                    let parsed =
                        crate::compiler::methods::parse_call(args, type_args, *fn_span, ctx, state);
                    let v_len = v.len();
                    crate::compiler::methods::declare_parse_text(v, 0);
                    let parsed_type = parsed.infer_type(v, ctx, state);
                    v.truncate(v_len);
                    return parsed_type;
                }
                // A builtin-typed receiver resolving to an `impl` method
                // (`impl list { fn sum(self) ... }` -> `list#sum`) infers its
                // return type from that method, specialized for the receiver
                // and argument types.
                if let Some(fn_id) = crate::compiler::methods::impl_method_on_builtin(
                    method, &obj_type, args, *fn_span, v, ctx, state,
                ) {
                    check_receiver(fn_id, method, *fn_span, ctx, state);
                    let mut arg_types: Vec<DataType> = Vec::with_capacity(args.len() + 1);
                    arg_types.push(obj_type.clone());
                    for a in args {
                        arg_types.push(a.infer_type(v, ctx, state));
                    }
                    let call_type_args = if type_args.is_empty() {
                        Vec::new()
                    } else {
                        resolve_call_type_args(fn_id, method, type_args, *fn_span, ctx, state)
                    };
                    return infer_user_fn_return_type(
                        fn_id,
                        &arg_types,
                        &call_type_args,
                        method,
                        v,
                        ctx,
                        state,
                    );
                }
                // Each arm below answers for a receiver the compile stage
                // accepts. A call whose value is used reaches inference before
                // anything compiles it, so a receiver or a name the compile
                // stage would reject has to be rejected here, with the same
                // diagnostic it would have raised.
                macro_rules! receiver_type {
                    ($rule:expr, $expected:expr) => {
                        builtin_method_return(&obj_type, $rule).unwrap_or_else(|| {
                            error_invalid_obj_type(
                                $expected,
                                &obj_type,
                                method,
                                *obj_span,
                                state.sources,
                                ctx.file_idx,
                                state.type_names(),
                            )
                        })
                    };
                }
                match method {
                    "uppercase" | "lowercase" | "replace" | "trim" | "trim_start" | "trim_end"
                    | "trim_chars" | "trim_start_chars" | "trim_end_chars" | "join" => {
                        DataType::String
                    }
                    "starts_with" | "ends_with" | "contains" => DataType::Bool,
                    "len" => DataType::Int,
                    "index_of" => {
                        receiver_type!(
                            |t| matches!(t, DataType::String | DataType::Array(_))
                                .then_some(DataType::Null),
                            &[DataType::String, DataType::Array(None)]
                        );
                        let v_len = v.len();
                        crate::compiler::methods::declare_index_found(v, 0);
                        let found = crate::compiler::methods::index_of_value(*fn_span)
                            .infer_type(v, ctx, state);
                        v.truncate(v_len);
                        found
                    }
                    "repeat" => receiver_type!(
                        |t| match t {
                            DataType::String => Some(DataType::String),
                            DataType::Array(element) => Some(DataType::Array(element.clone())),
                            _ => None,
                        },
                        &[DataType::String, DataType::Array(None)]
                    ),
                    // A string's reverse is a new string; a list's reverses
                    // the list in place and, like every method that changes
                    // its receiver, returns nothing.
                    "reverse" => receiver_type!(
                        |t| match t {
                            DataType::String => Some(DataType::String),
                            DataType::Array(_) => Some(DataType::Null),
                            _ => None,
                        },
                        &[DataType::String, DataType::Array(None)]
                    ),
                    "push" | "sort" | "remove" => DataType::Null,
                    "sqrt" | "round" | "floor" => DataType::Float,
                    "abs" => receiver_type!(
                        |t| match t {
                            DataType::Float => Some(DataType::Float),
                            DataType::Int => Some(DataType::Int),
                            _ => None,
                        },
                        &[DataType::Int, DataType::Float]
                    ),
                    "split" => receiver_type!(
                        |t| match t {
                            DataType::String =>
                                Some(DataType::Array(Some(Box::from(DataType::String)))),
                            DataType::Array(element) => Some(DataType::Array(Some(Box::from(
                                DataType::Array(element.clone())
                            )))),
                            _ => None,
                        },
                        &[DataType::String, DataType::Array(None)]
                    ),
                    "keys" => receiver_type!(
                        |t| match t {
                            DataType::Map(m) => Some(DataType::Array(m.0.clone().map(Box::new))),
                            _ => None,
                        },
                        &[DataType::Map(Box::from((None, None)))]
                    ),
                    "values" => receiver_type!(
                        |t| match t {
                            DataType::Map(m) => Some(DataType::Array(m.1.clone().map(Box::new))),
                            _ => None,
                        },
                        &[DataType::Map(Box::from((None, None)))]
                    ),
                    // No builtin takes this name, and the impl-method and
                    // struct/enum lookups above already missed, so the call
                    // names nothing. The report names the module that
                    // declares the method, or the spelling that replaced it.
                    _ => crate::compiler::compiler_errors::error_unknown_builtin_method(
                        method,
                        crate::compiler::methods::builtin_receiver_name(&obj_type),
                        *fn_span,
                        ctx.file_idx,
                        state.sources,
                    ),
                }
            }
            Self::Match(scrutinee, arms, wildcard, span, true) => {
                let scrut_type = scrutinee.infer_type(v, ctx, state);
                let mut types: Vec<DataType> = Vec::with_capacity(arms.len() + 1);
                for (patterns, body) in arms {
                    let v_len = v.len();
                    if let DataType::Enum(enum_id) = scrut_type {
                        crate::compiler::declare_arm_bindings(
                            enum_id, patterns, *span, v, ctx, state,
                        );
                    }
                    types.push(body[body.len() - 1].infer_type(v, ctx, state));
                    v.truncate(v_len);
                }
                if let Some(w) = wildcard {
                    types.push(w[w.len() - 1].infer_type(v, ctx, state));
                }
                branch_value_type(types, ctx, state)
            }
            Self::InlineCondition(condition, code, _, _) => {
                // Each branch is typed with what its condition proved.
                let mut types: Vec<DataType> = Vec::with_capacity(code.len());
                let v_len = v.len();
                crate::compiler::type_test::declare_condition_facts(condition, v, ctx, state);
                types.push(code[0].infer_type(v, ctx, state));
                v.truncate(v_len);
                for t in &code[0..] {
                    if let Self::ElseIfBlock(condition, code, _) = t {
                        crate::compiler::type_test::declare_condition_facts(
                            condition, v, ctx, state,
                        );
                        types.push(code[0].infer_type(v, ctx, state));
                        v.truncate(v_len);
                    } else if let Self::ElseBlock(code) = t {
                        types.push(code[0].infer_type(v, ctx, state));
                    }
                }
                branch_value_type(types, ctx, state)
            }
            Self::NamespacedRef(path, span, type_args) => {
                if !type_args.is_empty() {
                    let (enum_id, _) = resolve_generic_variant(path, type_args, *span, ctx, state);
                    return DataType::Enum(enum_id);
                }
                if let Some((enum_id, _)) = variant_constructor_at(path, &[], *span, ctx, state) {
                    DataType::Enum(enum_id)
                } else {
                    crate::compiler::compiler_errors::error_enum(
                        "Unknown enum variant",
                        &format!("{} does not name an enum variant", path.join("::")),
                        *span,
                        ctx.file_idx,
                        state.sources,
                    );
                }
            }
            Self::Struct(namespace, fields, span, type_args, base) => {
                DataType::Struct(literal_struct_id(
                    namespace,
                    fields,
                    type_args,
                    base.as_ref().and_then(|b| b.0.base()),
                    *span,
                    v,
                    ctx,
                    state,
                ))
            }
            Self::StructDefault(struct_id, _) => DataType::Struct(*struct_id),
            Self::AnonymousFunction(args, code, span) => {
                // An anonymous function is hoisted to a synthetic non-capturing
                // top-level function and referred to by its Fn id, exactly like a
                // named function reference. Inference runs many times, so the
                // hoist is keyed by the file and span the literal was written at
                // and reused: the first encounter registers the function, later
                // ones resolve to the same id, and two files whose closures sit
                // at the same offset stay apart.
                let fn_name = format_args!(
                    "{ANON_FN_PREFIX}{}:{}:{}",
                    ctx.file_idx, span.start, span.end
                )
                .to_smolstr();
                if let Some(id) = state.fns.iter().rposition(|f| f.name == fn_name) {
                    return DataType::Fn(id as u16);
                }
                let returns_null = check_if_returns_void(code);
                let mut callees = Vec::new();
                collect_direct_fn_calls(code, None, &mut callees);
                // The scope the literal is written in is the one its body
                // reads, and this is where that scope is in hand: the body
                // itself compiles later, at the first call, which can sit in
                // another function entirely. A free name that resolves to no
                // variable here names a declared function, which the body
                // reaches the same way any other code does.
                let captures: Box<[(SmolStr, DataType, Option<DataType>)]> =
                    closure_free_names(args, code)
                        .into_iter()
                        .filter_map(|name| {
                            v.iter()
                                .rfind(|var| var.name == name)
                                .map(|var| (name, var.var_type.clone(), var.declared.clone()))
                        })
                        .collect();
                let id = state.fns.len() as u16;
                state.fns.push(Function {
                    name: fn_name,
                    args: args.iter().map(|a| (a.clone(), None)).collect(),
                    code: Rc::from(code.clone()),
                    impls: Vec::new(),
                    is_recursive: None,
                    returns_null,
                    src_file: ctx.file_idx,
                    return_type_cache: Vec::new(),
                    direct_calls: callees.into_boxed_slice(),
                    name_span: *span,
                    // An anonymous function takes no return annotation.
                    return_type: None,
                    generics: None,
                    captures,
                    entry_register: None,
                });
                DataType::Fn(id)
            }
            _ => unsafe { unreachable_unchecked() },
        }
    }
}

/// The type of a construct used as a value, an `if` or a `match`, from the
/// types its branches give, in order.
///
/// Branches that give different functions give a function value, which a call
/// dispatches on, so every branch's type is kept for that test: `Fn` types
/// compare equal whichever function they name. Otherwise the branches give a
/// union of their distinct types.
///
/// Two instantiations of one generic declaration merge the way two returns of
/// a body do (see [`add_return_type`]): `if c { Some(x) } else { None }` is an
/// `Option<int>`, not a union of it with the `Option<any>` the bare `None`
/// names.
fn branch_value_type(types: Vec<DataType>, ctx: Ctx, state: &mut State<'_>) -> DataType {
    if let Some(fn_value) = merge_fn_types(&types) {
        return fn_value;
    }
    let mut distinct: Vec<DataType> = Vec::with_capacity(types.len());
    for t in types {
        if distinct.contains(&t) {
            continue;
        }
        if let Some((i, merged)) = distinct
            .iter()
            .enumerate()
            .find_map(|(i, held)| merge_instantiations(held, &t, ctx, state).map(|m| (i, m)))
        {
            distinct[i] = merged;
            continue;
        }
        distinct.push(t);
    }
    DataType::Union(Box::from(distinct)).check_poly()
}

/// The type a declared function has where a value holds it.
///
/// A function whose parameters and return are annotated says its own signature,
/// so a call through the value is checked against what the declaration names.
/// One the compiler infers says only which function it holds, and the first
/// call through the value settles the types its body is compiled at. The
/// function is a candidate of the type either way, which is what compiles the
/// body a call through the value jumps to.
#[must_use]
pub fn declared_fn_value_type(fn_id: u16, state: &State<'_>) -> DataType {
    let function = &state.fns[fn_id as usize];
    let params: Option<Vec<DataType>> = function
        .generics
        .is_none()
        .then(|| function.args.iter().map(|(_, arg)| arg.clone()).collect())
        .flatten();
    let return_type = function
        .return_type
        .as_ref()
        .map(|(declared, _)| declared.clone())
        .or_else(|| function.returns_null.then_some(DataType::Null));
    let sig = match (params, return_type) {
        (Some(params), Some(return_type)) => Some((params.into_boxed_slice(), return_type)),
        _ => None,
    };
    DataType::FnValue(Box::new(FnValue {
        sig,
        candidates: Box::from([fn_id]),
        set: None,
    }))
}

/// The type of `expr` where it is a bare name that means a declared function
/// and the position holds the function rather than calls it.
///
/// `None` for anything else, which leaves a closure bound to a name and a call
/// through a name the compiler can settle lowering to the jump they were.
#[must_use]
pub fn bare_fn_value_type(
    expr: &Expr,
    v: &[Variable],
    ctx: Ctx,
    state: &State<'_>,
) -> Option<DataType> {
    let Expr::Var(name, _) = expr else {
        return None;
    };
    if v.iter().any(|var| var.name == *name) {
        return None;
    }
    let fn_id = state.scope(ctx.file_idx).find_function(&[], name)?;
    Some(declared_fn_value_type(fn_id as u16, state))
}

/// The one function type that holds every type in `types`, where more than one
/// function can land in the same position.
///
/// A position every function in it agrees on stays pinned to that function, so
/// a list of one closure and a call through it resolve at compile time exactly
/// as they did. Two different functions make the position a function value: no
/// function is the one it holds, so the call dispatches on what the value
/// carries. `None` where the types name no function, which leaves the position
/// to the ordinary rules.
#[must_use]
pub fn merge_fn_types(types: &[DataType]) -> Option<DataType> {
    let mut candidates: Vec<u16> = Vec::new();
    let mut sig = None;
    let mut saw_fn = false;
    for t in types {
        match t {
            DataType::Fn(id) => {
                saw_fn = true;
                if !candidates.contains(id) {
                    candidates.push(*id);
                }
            }
            DataType::FnValue(fn_type) => {
                saw_fn = true;
                if sig.is_none() {
                    sig.clone_from(&fn_type.sig);
                }
                for id in &fn_type.candidates {
                    if !candidates.contains(id) {
                        candidates.push(*id);
                    }
                }
            }
            _ => {}
        }
    }
    if !saw_fn || (sig.is_none() && candidates.len() < 2) {
        return None;
    }
    Some(DataType::FnValue(Box::new(FnValue {
        sig,
        candidates: candidates.into_boxed_slice(),
        set: None,
    })))
}

/// What a call through a function value hands back.
///
/// A declared `fn(...) -> R` says it. A type inferred from the functions
/// written into the position asks each of them, at the argument types this call
/// passes, and they have to agree.
pub fn indirect_return_type(
    fn_type: &FnValue,
    args: &[Expr],
    v: &mut Vec<Variable>,
    ctx: Ctx,
    state: &mut State<'_>,
) -> DataType {
    if let Some((_, return_type)) = &fn_type.sig {
        return return_type.clone();
    }
    let infered_arg_types = args
        .iter()
        .map(|arg| arg.infer_type(v, ctx, state))
        .collect::<Vec<DataType>>();
    let return_types = state
        .fn_value_candidates(fn_type)
        .into_iter()
        .map(|fn_id| {
            let fn_id = fn_id as usize;
            let fn_name = state.fns[fn_id].name.clone();
            infer_user_fn_return_type(fn_id, &infered_arg_types, &[], &fn_name, v, ctx, state)
        })
        .collect::<Vec<DataType>>();
    let mut return_types = return_types.into_iter();
    match return_types.next() {
        None => DataType::Unknown,
        Some(first) if return_types.len() == 0 => first,
        Some(first) => {
            let all = std::iter::once(first).chain(return_types).collect();
            DataType::Union(all).check_poly()
        }
    }
}