lang::typecheck::usage
lang/src/typecheck/usage.mo
Runtime-position USE COUNTING over the canonical de-Bruijn Term.
Milestone 1 of the affine-by-default viability experiment (section Design B: Viability Experiment). This module decides nothing and rejects nothing: it answers "how many times does each binder get used at run time?" so the experiment can size the migration before any semantics change.
The judgement it implements is the design's R1: Γ, x :ₘ A ⊢ t
holds iff Σ(x, t) ≤ m, where Σ counts runtime-position uses.
Three rules make Σ what it is, and each is a way to get this wrong:
- Branches combine by MAX, not sum.
if c then x else xusesxonce — only one arm runs. So does amatchwhose every arm uses it once. Summing them would report every well-formed two-armed match as a double use and make the whole measurement meaningless. - Type positions count 0. A
Term.pi's argument and aTerm.lam's own annotation are compile-time positions. A variable mentioned there is erased before run time and consumes nothing. - Binder depth must match the tree. Crossing
lam/forall/piadds one to the body; aMatchCaseaddsList.length args. Both conventions are spelled out and tested in [[lang/typecheck/traverse.mo]] — this module mirrors them rather than re-deriving them, and the match-arm case is the onelang/typecheck/subst.mo'stest_match_case_binder_depth_shiftexists to catch.
Not a use, deliberately:
- A top-level def reference is a free global, not a binder. Only
Term.varindices that resolve to a local binder are counted, and a free reference carriesidx = sentinel(-1), which no binder depth ever equals. - A quoted term (
Term.quote_) is syntax as data. Nothing inside it runs, so nothing inside it consumes. Term.ctxis a transparent wrapper (term_map_children_at_depth's own arm passes depth 0 through it) — peel, never count.
Known conservatism, recorded rather than silently assumed: a use
inside a closure body counts ONCE even though the closure may be
called many times. That is correct for an affine binder — the closure
owns the capture, and calling a closure does not consume its captures
— but it is NOT correct for a linear one, where a closure capturing
a linear value must itself be linear. That rule belongs to Milestone
3 (drop points), and it is noted here because this module is where
someone will look for it first.
That conservatism is about a closure's CAPTURES. The closure VALUE's own
uses are measured separately, by function_moves: calling it is a read,
while passing, storing or returning it is a transfer, and exactly one
transfer is allowed. That is why higher-order code needs no
Copy (A -> B) instance — the closure is never duplicated, so its
captured environment is never double-owned.
pub def captured_uses_of (target : I64) (t : Term) : I64pub def captured_uses_of_with_free (free : I64) (target : I64) (t : Term) : I64free is the number of leading Term.lam binders in t that are still
the def's own parameter chain, not closures. A def parameter's body
starts with its remaining sibling parameters; those lambdas must not
count as captures (see collect_binder_uses_with_params).
pub type UsePos {
/// Callee of an application -- calling a closure reads it.
up_app_head,
/// Argument of an ordinary (non-constructor) application. A read
/// **if** the callee does not retain it; see the caveat above. For a
/// FUNCTION-typed binder this is a MOVE: passing a closure on hands
/// the callee its captured environment (`function_moves`).
up_app_arg,
/// Direct argument of a `Shared.of` call — a borrow, never a move,
/// whatever the binder's type: the handle names the payload again
/// rather than transferring it.
up_shared_arg,
/// Scrutinee of a `match`, or an `if`'s condition. Always a read:
/// matching inspects a value, it does not consume it.
up_scrutinee,
/// Stored into a constructor, a struct literal, or a struct update.
/// An OWNING use -- the value outlives the expression.
up_con_field,
/// The value a scope produces: a bare body, a branch result, a
/// match arm's result. An OWNING use -- it is moved out.
up_value,
}Where a use of a binder sits, which is what says whether it could be a borrow.
pub def owning_uses (ctors : HashMap String Bool) (borrows : HashMap String Bool) (target : I64) (t : Term) : I64Owning uses of target in t — the up_con_field and up_value
ones. 0 or 1 means the binder is borrowable as written.
pub def owning_at (ctors : HashMap String Bool) (borrows : HashMap String Bool) (ctx : UsePos) (target : I64) (t : Term) : I64Owning uses of target in position ctx, under the DATA notion of a
call argument (a read — the callee may borrow it). The function-typed
variant is function_moves, which counts an argument as a transfer;
dropck.mo and every other data caller use this one.
pub def function_moves (ctors : HashMap String Bool) (borrows : HashMap String Bool) (target : I64) (t : Term) : I64Moves of a FUNCTION-typed binder. Calling it (up_app_head) and
matching on it are reads; passing it on (up_app_arg), storing it
(up_con_field) or producing it as a value (up_value) transfers the
closure, and exactly one transfer is allowed. This is why function
values need no Copy (A -> B): List.map f tail calls f and passes
it on once, and the closure is never duplicated — so its captured
environment is never double-owned.
pub def typ_is_function (t : Term) : BoolA binder whose type is a function: an explicit pi. Implicit ({})
binders are type variables, never runtime function values.
pub def ctor_name_set (s : Scope) : HashMap String BoolThe set of names that refer to a constructor, for
head_is_ctor. Built once per report run and threaded down.
This exists because testing for Term.con does not work. A probe
over the compiler's own elaborated closure found 44,609 application
nodes, of which zero had a Term.con spine head, against 19,738
with a dotted name — elaboration leaves a constructor reference as an
ordinary named Term.var (there are only 212 Term.con nodes in the
whole tree). A Term.con test therefore never fires, and every
constructor store silently reads as a call argument. That produced a
"99.9% of over-uses are borrowable" figure which was an artifact of
the blind classifier, not a property of the corpus.
A dotted-name test alone would be just as wrong in the other
direction: most of those 19,738 heads are ordinary qualified calls
(String.concat, List.map), not constructors. So the names are
resolved against the real inductives in scope.
Each constructor goes in twice: under its bare name (cons) and
under its rendered path (List.cons), so a head resolves whichever
spelling its DebugName carries.
pub def borrow_aware_uses (borrows : HashMap String Bool) (target : I64) (t : Term) : I64Uses of target in t that count against the affine budget:
uses_of minus the occurrences that are the DIRECT argument of a
real Shared.of call (per head_is_shared_of).
borrowed_here says this subterm IS that direct argument, and only
a Term.var under it is excused. Anything nested deeper resets:
Shared.of (f x) runs f x to produce the borrowed value, which is
a real use of x, so excusing it would hide a genuine double-use.
The asymmetry is deliberate in the same direction as everything else
here — a missed borrow costs one advisory copy_required (fail
closed); a wrongly excused use would be a false negative.
Combination rules are uses_of's EXACTLY — same sums, same
per-branch maxes — so uses_of - borrow_aware_uses is a
branch-consistent borrowed count. That is why BinderUse.borrowed
is computed as the difference rather than by a separate borrowed
walk: two walks that each take their own max across match arms
would subtract a borrow in one arm from a use in another, and the
gate would let a binder through that one arm genuinely over-uses.
pub type BinderKind {
bk_lam,
bk_match,
}Where a binder came from. Enough to read a report by; deliberately
NOT enough to reconstruct the binding site, which the report does not
need and which Term cannot supply anyway (a let is already
desugared to app (lam ...) value by the time it gets here, so a
let-bound name is indistinguishable from a lambda parameter).
pub struct BinderUse {
name : Identifier,
kind : BinderKind,
typ : Term,
count : I64,
/// For a `bk_match` binder, the constructor whose pattern bound it;
/// `Identifier.id ""` for a `bk_lam` one. Paired with `pos`, this is
/// everything `attribute_binder_types` needs to look the real type
/// up later, without this walk taking a `Scope`.
ctor : Identifier := Identifier.id "",
/// Owning uses of this binder — `owning_uses` on its body. `0` or
/// `1` means it is borrowable as written (one move, the rest
/// reads); `2` or more means it genuinely needs duplication.
owning : I64 := 0,
/// Borrowed uses — `count` minus `borrow_aware_uses` on this
/// binder's body: the occurrences that are the direct argument of a
/// real `Shared.of` call. Computed as a difference because the two
/// walks share branch-combination rules, which keeps it exact where
/// one match arm borrows what another arm consumes; a separately
/// borrowed-per-branch-maxed count would under-count there. The
/// affine gate in `affine.mo` compares `count - borrowed`, not
/// `count`.
borrowed : I64 := 0,
/// Position of this binder within that constructor's arguments, in
/// written order, 0-based. `-1` for a `bk_lam` binder.
///
/// NOT the de-Bruijn index -- pattern binders are pushed left to
/// right, so the binder at written position `i` of `n` sits at index
/// `n - 1 - i` inside the body. `collect_case_args` computes both.
pos : I64 := 0 - 1,
/// Moves of a FUNCTION-typed binder — `function_moves` on its body.
/// `0` or `1` is affine-legal; a second move is a second transfer of
/// the closure. Zero for every non-function binder, which uses
/// `owning` instead.
moves : I64 := 0,
/// This binder holds a **borrowed view** of a `Shared` payload: it was
/// bound from `Shared.get _` (or aliased from one, or bound by matching
/// on one). A view may be read, matched, called and passed to another
/// `Shared` parameter, but it is not an owner — storing it, returning
/// it, or passing it to an owning parameter is `borrowed_value_escapes`
/// (`affine.mo`), and it never gets a drop point (`dropck.mo`).
///
/// Deliberately NOT defaulted. A field default whose value is a
/// CONSTRUCTOR (`false`) breaks the Rust host's lowering
/// (`lower: UnresolvedAtom`): the default is spliced into every
/// literal that omits the field, and a constructor's atom is not in
/// the spliced def's `atom_paths`. Defaults that name a DEF (like
/// `ctor`'s `Identifier.id ""`) are fine. Every literal supplies it.
view : Bool,
/// The binder's `declared` multiplicity (`Param.mult`). Always
/// `Multiplicity.many` since the `!`/`?`/`%` prefix syntax was
/// removed from the grammar — the field stays because the runtime
/// matches `Param` positionally. `collect_binder_uses_with_params`
/// fills a def's leading binders from `Def.params`; a match binder takes
/// the constructor field's `Param.mult`. The affine judgement
/// (`affine.mo`'s `check_binders_go`) reads this instead of hardcoding
/// `many`.
///
/// No default, for the same constructor-valued-default reason as
/// `view` above. Every literal supplies it.
declared : Multiplicity,
/// For a binder whose written annotation is a hole, the INITIALIZER it
/// was bound from, when the collector can see one (`let x <- m` /
/// `app (app bind m) (lam x => ...)`). `attribute_one` uses it to
/// recover the binder's type through the callee's declared return type,
/// so a `Cell` bound by a do-block is not left unattributable -- the
/// fail-open exemption would otherwise make every `let c <- Cell.new`
/// unenforced. `Option.none` everywhere else.
init : Option Term,
/// Uses of this binder UNDER a nested `lam` -- a closure capture.
/// A closure body counts its captures once but may run many times
/// (and, with eager fibers, on another thread), so a linear or proof
/// value may not be captured. `0` is an ordinary literal default and
/// is safe to omit.
captured : I64 := 0,
}One binder and how many times its body uses it.
typ is Term.hole when unknown. That is the honest state for a
match-arm binder here: its type comes from the matched constructor's
InductConstructor.params, which needs the scrutinee's inductive
resolved, which needs a Scope this module deliberately does not
take (it stays a pure function of the term). The report's driver
fills those in where it can.
pub def BinderUse.count (u : BinderUse) : I64Typed accessors, one per field this module's own tests read.
NOT redundant with the struct's field syntax: a #[test] def whose
body is a bare struct field access takes the FIELD's LLVM type as its
own return type in the self-hosted backend (i1/i64 mismatch at
llc, or an undefined @P.mk), and only the compiled runner shows
it. Reading through an ordinary def is the documented workaround, and
Def.name (lang/types.mo:1021) is the existing precedent for the
name-shadows-field spelling.
pub def BinderUse.name (u : BinderUse) : Identifierpub def BinderUse.typ (u : BinderUse) : Termpub def BinderUse.kind (u : BinderUse) : BinderKindpub def BinderUse.ctor (u : BinderUse) : Identifierpub def BinderUse.pos (u : BinderUse) : I64pub def BinderUse.owning (u : BinderUse) : I64pub def BinderUse.borrowed (u : BinderUse) : I64pub def BinderUse.view (u : BinderUse) : Boolpub def BinderUse.moves (u : BinderUse) : I64pub def BinderUse.declared (u : BinderUse) : Multiplicitypub def BinderUse.captured (u : BinderUse) : I64pub def BinderUse.init (u : BinderUse) : Option Termpub struct ViewEnv {
/// One flag per binder scope, innermost first (`flags[0]` is the
/// innermost binder).
flags : List Bool := List.empty,
inherit : Bool := false,
}pub def expr_is_view (shareds : HashMap String Bool) (e : ViewEnv) (t : Term) : BoolIs t a term that yields a borrowed view?
True for a Shared.get application, a Shared.of whose argument is
itself a view (a re-wrap names the same payload), a variable whose
binder is a view, and a shape that COMBINES one: the result of an
if/match arm or a constructed value. Anywhere else — notably an
ordinary function call, which produces a fresh value — the answer is
false. The residual hole is a def that returns a field of its argument
without saying so (the plan's R8 family).
#[terminating]: the Term.elim arm descends through
expr_is_view_minors (a #[partial] list walk) back into this function
with a minor's peeled body, which the positional decrease check cannot see
as a structural subterm of t -- the same weak-check case the attribute
documents. The walk is well-founded: each recursion strips a constructor
node or a list cell.
pub def collect_binder_uses (ctors : HashMap String Bool) (borrows : HashMap String Bool) (t : Term) : List BinderUseEvery binder in t, with its use count.
Accumulator-passing, and every walker below it likewise: this runs
over whole modules -- 3,817 defs for the compiler itself -- and the
natural List.cons x (recurse rest) shape holds one native frame per
node, which is the exact pathology codegen/decls.mo's
extract_defs and codegen/qualify.mo's
ambiguous_declared_names document (and which Boehm then pays for
again on every collection, since it marks conservatively from the
whole stack).
Order is unspecified -- the accumulator reverses, and the report sorts by count anyway.
pub def collect_binder_uses_with_params (params : List Param) (ctors : HashMap String Bool) (borrows : HashMap String Bool) (t : Term) : List BinderUseCollect a def's binders with its DECLARED parameter list in hand.
The leading lambda chain is not a flat list of Def.params: the
elaborator prepends one __dict_<Class> lambda per qualifying
constraint AFTER Def.params was built (scope.mo's
add_constraint_dict_params), and a parameter's own body begins with
its remaining sibling parameters. Walking that chain here gives each
declared binder:
- its
declaredmultiplicity (Param.mult) — alwaysmanysince the!/?/%prefix syntax was removed from the grammar; - a
capturedcount that does NOT treat the remaining parameter lambdas as closures (captured_uses_of_with_free).
Nested binders (closures, let-bound values, match arms) are collected
afterwards by the ordinary walker, whose captured rule is correct
for them.
pub def view_env_empty : ViewEnvpub struct Redex {
binder : Binder,
typ : Term,
body : Term,
}The lam behind a beta-redex (app (lam ...) arg), peeled of ctx. A
let elaborates to exactly this shape, so it is where a binder's
view-ness is decided from its initializer.
pub struct BindCont {
initializer : Term,
binder : Binder,
typ : Term,
body : Term,
}The shape of a do-bind's continuation: app (app bind m) (lam x => rest).
initializer is m, the term attribute_one resolves x's type from.
pub def spine_head_name (t : Term) : Option StringThe head name of a call spine, peeling ctx and applications.
pub def is_bind_head (t : Term) : BoolA Monad.bind application. The parser's do-lowering spells the head
Monad.bind; IO.bind/RawIO.bind are accepted for a hand-written
bind. Deliberately NOT a bare bind: a user function of that name
could call its continuation any number of times, and the capture
exemption below is only sound for a once-per-execution bind.
pub def attribute_binder_types (s : Scope) (us : List BinderUse) : List BinderUseFill in typ for every bk_match binder whose constructor resolves
unambiguously. Leaves the rest at Term.hole.