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, aShared.getresult or an alias of one) must never get a drop point. Releasing it would free a payload itsSharedhandle still points at. - A function-typed binder transfers ownership when it is passed,
stored or returned, even though
owning_atcounts a call argument as a read. Its release decision must useusage.mo'sfunction_movesnotion, 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.
pub def drop_leaves (ctors : HashMap String Bool) (borrows : HashMap String Bool) (target : I64) (t : Term) : List BoolOne 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.
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.
pub def DropInfo.name (d : DropInfo) : Identifierpub def DropInfo.leaves (d : DropInfo) : List Boolpub def DropInfo.always_drop (d : DropInfo) : BoolNeeds releasing on every path it can take — the common case: no branching at all, or dropped alike wherever control goes.
pub def DropInfo.never_drop (d : DropInfo) : BoolNeeds releasing on no path — ownership was transferred everywhere this binder's body can return. Nothing to emit for it.
pub def collect_drop_info (ctors : HashMap String Bool) (borrows : HashMap String Bool) (t : Term) : List DropInfoEvery 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.