lang::typecheck::dropck

lang/src/typecheck/dropck.mo

Drop-point analysis — where a value must be released, along each control-flow path, because the enclosing scope still owns it there.

Milestone 3 of the affine-by-default experiment (Design B: Viability Experiment). This module decides WHERE a monad_release call would go; it does not emit one. Codegen wiring (codegen/emit.mo) and the runtime's real free (runtime/src/runtime.c) are deliberately separate, unstarted work — see the design's own M3 section for why: this module is pure and safely testable in isolation, emit.mo is the central, historically fragile codegen file this experiment has stayed clear of touching until the analysis feeding it is solid.

The rule, and why it needs no new primitive

[[lang/typecheck/usage.mo]] already answers exactly the question this needs, per use: owning_at classifies each use of a binder as either a READ (a call argument, a match scrutinee, a callee — the owner is not moved) or an OWNING use (stored into a constructor, or produced as a scope's own value — ownership transfers out). A binder with zero owning uses along a given path was never given away on that path, so the scope that bound it still owns it when that path returns, and must release it there. That is the entire rule: release iff owning count on this path is 0.

Not yet implemented — requirements for whoever wires this module into codegen (invariants I1/I2 of the memory-safety review recorded in plans/bootstrapping/ownership-regions-memory.md). The rule below is still the data-owning one; these two cases need extra work before the first release is emitted:

  • A borrowed view (BinderUse.view, a Shared.get result or an alias of one) must never get a drop point. Releasing it would free a payload its Shared handle still points at.
  • A function-typed binder transfers ownership when it is passed, stored or returned, even though owning_at counts a call argument as a read. Its release decision must use usage.mo's function_moves notion, not the data-owning count, or a closure moved into a callee is freed twice. The collector's view environment (ViewEnv) and its beta-redex arm also need mirroring here.

Why this needs a NEW walk, not owning_uses as-is

usage.mo's own owning_uses/uses_of deliberately combine branches by MAX — one worst-case number, because M2's usage rule asks "is this binder ever over-used on ANY path" and a single number is exactly the right answer to THAT question. M3 asks a different question — "on EACH path, was it consumed, and if not, where does the release go" — and max-combining throws away exactly the per-branch information that needs. If a binder's global (maxed) owning count is 1, that could mean every branch transfers ownership (no releases needed anywhere) OR it could mean ONE branch does and the others still don't (those still need one). The two situations look identical after max-combining and must not.

So drop_leaves below mirrors owning_at's own branch structure exactly — same if_/match_ cases, same depth bookkeeping — but where owning_at combines branches with i64_max, this CONCATENATES them: one boolean per real leaf (tail position) of the term, in left-to-right order, computed by calling the EXISTING, already-tested owning_at on each leaf's own whole subtree rather than re-deriving what counts as an owning use.

A measured cost, not a silent one

List.append at every branch point is O(length of the first list) per call — cheap for i64_max's O(1), real once it compounds across a binder near a deeply/widely branching root. bench/src/ dropck_probe.mo measured this over the compiler's own closure: 22,416 binders, 32,104 total leaves (a 100-leaf worst case), 92.6s for the walk alone on the Rust host's tree-walking evaluator (elaboration excluded) — 19.4s under the compiled self-hosted runner, same stats both ways. That is genuinely slower than usage.mo's comparable per-binder walk over the SAME term set, and the List.append-per-branch shape is the reason. Not fixed here: nothing consumes this module's output yet (see this file's own header — codegen wiring is deliberately unstarted), so there is no real workload this cost is currently paid against, and the standard fix (thread an accumulator through the branches instead of appending, matching every other O(n) list-builder in this codebase — codegen/decls.mo's extract_defs, qualify.mo's ambiguous_declared_names) is well understood and small when the time comes. Recorded here so it is a known, deliberate deferral rather than a surprise the next person to touch this file has to rediscover.

defdrop_leaves#
pub def drop_leaves (ctors : HashMap String Bool) (borrows : HashMap String Bool) (target : I64) (t : Term) : List Bool

One entry per LEAF (tail position) reachable from t, in the same left-to-right order a reader would encounter them: true means target still needs releasing there (owning count 0 on that path), false means it was already consumed (owning count ≥ 1) on that path. List.length of the result is the number of distinct control-flow paths through t — 1 for anything that doesn't branch, more for nested if/match.

borrows is threaded for the same reason usage.mo threads it: a real Shared.of x misread as a constructor store would count x as consumed here, and a consumed binder gets no release — a leak, not just a miscount.

structDropInfo#
pub struct DropInfo {
    name : Identifier,
    /// One entry per leaf of this binder's OWN body — see `drop_leaves`.
    leaves : List Bool,
}

One binder found in a def's body, and where it needs releasing.

defDropInfo.name#
pub def DropInfo.name (d : DropInfo) : Identifier
defDropInfo.leaves#
pub def DropInfo.leaves (d : DropInfo) : List Bool
defDropInfo.always_drop#
pub def DropInfo.always_drop (d : DropInfo) : Bool

Needs releasing on every path it can take — the common case: no branching at all, or dropped alike wherever control goes.

defDropInfo.never_drop#
pub def DropInfo.never_drop (d : DropInfo) : Bool

Needs releasing on no path — ownership was transferred everywhere this binder's body can return. Nothing to emit for it.

defcollect_drop_info#
pub def collect_drop_info (ctors : HashMap String Bool) (borrows : HashMap String Bool) (t : Term) : List DropInfo

Every binder t introduces (lam/match-arm), with its own drop_leaves. Mirrors usage.mo's collect_binder_uses traversal (same cases, same order of descent) — but NOTE that usage.mo has since gained a beta-redex arm and a view environment, which this walk has not; keep the two in step when this module is wired.

Accumulator-passing, like every corpus-scale walker in this codebase (codegen/decls.mo's extract_defs, codegen/qualify.mo's ambiguous_declared_names, usage.mo's own collect_binder_uses): the natural List.cons x (recurse rest) shape holds one native frame per node, which those files' own doc comments document as a real stack-depth hazard at whole-program scale.