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 List walk anyway. The partition is identical to the reference's.
  • Diagnostics accumulate instead of failing fast. The reference returns Err at the first bad def (?); this returns one message per bad def, which is the convention check_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's Display output character for character, down to its em dash; render_diag below adds the error: prefix that every other diagnostic in that walk gets from render_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 :, so show_identifier/show_name_path are injective, and comparing on them sidesteps Identifier/NamePath identity entirely. This is also what the reference does -- recursion_name takes 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> binders add_constraint_dict_params prepends (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 implicit Par::I parameters. extract_params and drop_leading_dict_args below 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.

defcheck_termination_all#
pub def check_termination_all (decls : List Decl) : List String

Termination-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.