lang::termination
lang/src/termination.mo
Structural termination checking for recursive definitions.
A port of the reference implementation in rust/core/src/eval/termination.rs
(the host's check_termination_all), reached from the same point in the
pipeline: once a module's declarations have been checked, each of that
module's own defs is verified to recurse only on a structural subterm of
one of its formal parameters. A recursive call that cannot be shown to
decrease something is an error unless the def carries #[terminating],
#[partial] or #[decreasing ...].
Before this module, both attributes parsed and were ignored self-hosted --
#[terminating] def loop (x : I64) : I64 := loop x checked clean while the
host rejected it. The two compilers now agree, and both attributes mean here
exactly what they mean there.
Four things about this port are worth knowing before reading it, because three are deviations from the reference and all four are load-bearing:
- Mutual groups come from mutual reachability, not Tarjan. A group is
the set of defs that all reach each other, which is exactly a strongly
connected component of more than one member -- mutual reachability is an
equivalence relation, so its classes are the SCCs. Computing them
directly costs one transitive closure per def and threads no mutable
index/lowlink state, which a pure language cannot carry through a
Listwalk anyway. The partition is identical to the reference's. - Diagnostics accumulate instead of failing fast. The reference returns
Errat the first bad def (?); this returns one message per bad def, which is the conventioncheck_module_with_scope's own per-decl walk already follows. The set of failing defs is the same either way. The message text is the reference'sDisplayoutput character for character, down to its em dash;render_diagbelow adds theerror:prefix that every other diagnostic in that walk gets fromrender_type_error, so the two compilers' output for the same bad def is line for line the same. - Names are compared as rendered strings. Identifiers cannot contain
.or:, soshow_identifier/show_name_pathare injective, and comparing on them sidestepsIdentifier/NamePathidentity entirely. This is also what the reference does --recursion_nametakes a qualified name's name half and compares that, deliberately over-approximating so the check errs toward rejecting rather than accepting. - A constrained def's term is not shaped like its call sites. Its
leading
Term.lams include the__dict_<Class>bindersadd_constraint_dict_paramsprepends (lib::scope), while a recursive call site passes no dictionary -- those are inserted far later, in codegen. The reference has the mirror-image problem and solves it by skipping implicitPar::Iparameters.extract_paramsanddrop_leading_dict_argsbelow drop that same leading run from both sides, so a def's declared parameters line up with its call sites' arguments exactly as they do there.
One residual hole is inherited rather than introduced, and is left as the
reference leaves it: neither walk descends into a Literal.struct_lit /
struct_update's field values, so a recursive call written only inside a
struct literal is invisible to the checker. Struct literals are desugared
before this runs, so nothing in the corpus reaches that shape.
The comparison on name halves is safe specifically because this runs on ONE
module's own declarations, before any qualification: check_module_with_scope
is reached from elaborate_loaded_modules, whose target_decls is
main_module.decl_list (lang/module.mo), and the pass that rewrites names
to module.path::name is qualify_modules in codegen/qualify.mo -- a
codegen pass, downstream of every check. Within one module no two defs share a
name, so discarding the qualifier (as recursion_name does) cannot conflate
two of them.
That precondition is load-bearing, and one caller can violate it:
elaborate_loaded_modules with check_deps=true passes the whole
dependency closure. Measured 2026-09-23, that reports 188 spurious No recursive parameters found for '__Dict_...' diagnostics across 7 of 18
slow_tests/typecheck_init_tests.mo tests -- the promoted dictionary
defs of every module in the closure collide on their bare names, and a
group of two with no formal parameters is an error by the reference's
own rule. check_deps stays false everywhere; see
plans/bootstrapping/check-deps-memory-blowup.md.
pub def check_termination_all (decls : List Decl) : List StringTermination-check a module's own defs, returning one diagnostic per failing
def. This is the entry point check_module_with_scope (lang/src/module.mo)
calls, which is where the host calls its own check_termination_all
(rust/core/src/core_check_module.rs): once, per checked module, over that
module's own top-level defs.