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:

  1. Branches combine by MAX, not sum. if c then x else x uses x once — only one arm runs. So does a match whose 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.
  2. Type positions count 0. A Term.pi's argument and a Term.lam's own annotation are compile-time positions. A variable mentioned there is erased before run time and consumes nothing.
  3. Binder depth must match the tree. Crossing lam/forall/pi adds one to the body; a MatchCase adds List.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 one lang/typecheck/subst.mo's test_match_case_binder_depth_shift exists to catch.

Not a use, deliberately:

  • A top-level def reference is a free global, not a binder. Only Term.var indices that resolve to a local binder are counted, and a free reference carries idx = 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.ctx is 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.

defcaptured_uses_of#
pub def captured_uses_of (target : I64) (t : Term) : I64
defcaptured_uses_of_with_free#
pub def captured_uses_of_with_free (free : I64) (target : I64) (t : Term) : I64

free 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).

typeUsePos#
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.

defowning_uses#
pub def owning_uses (ctors : HashMap String Bool) (borrows : HashMap String Bool) (target : I64) (t : Term) : I64

Owning uses of target in t — the up_con_field and up_value ones. 0 or 1 means the binder is borrowable as written.

defowning_at#
pub def owning_at (ctors : HashMap String Bool) (borrows : HashMap String Bool) (ctx : UsePos) (target : I64) (t : Term) : I64

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

deffunction_moves#
pub def function_moves (ctors : HashMap String Bool) (borrows : HashMap String Bool) (target : I64) (t : Term) : I64

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

deftyp_is_function#
pub def typ_is_function (t : Term) : Bool

A binder whose type is a function: an explicit pi. Implicit ({}) binders are type variables, never runtime function values.

defctor_name_set#
pub def ctor_name_set (s : Scope) : HashMap String Bool

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

defshared_inductive#
pub def shared_inductive (s : Scope) : Option Inductive

The ONE inductive carrying #[shared], if there is exactly one.

The marker travels with the declaration, so renaming the type cannot silently disable shared-aware counting the way a literal spelling can — this module used to compare show_name_path name to "Borrow", and a rename that missed that literal would have quietly turned every shared read into an owning use. Fail closed: zero candidates, or more than one, means no shared type; a missed real shared reference costs one advisory copy_required.

defshared_name_set#
pub def shared_name_set (s : Scope) : HashMap String Bool

The set head_is_shared_of/head_is_shared_get check a spine head's rendered name against — like ctor_name_set, but scoped to exactly the #[shared] inductive, not every registered constructor. Built once per caller, same as ctors.

Both spellings are DERIVED from that inductive's own rendered name (<Ind>.of and <Ind>.get), so they are correct whatever the type is called. The bare spelling ("of") is registered ONLY when the shared inductive is the SOLE inductive in scope declaring a constructor by that name — failing closed on exactly the ambiguity ctor_field_type above already fails closed on, so a same-named of on some other type is not counted as a shared read. The bare "get" is never registered: get is an ordinary def name (std/path.mo declares one).

defborrow_aware_uses#
pub def borrow_aware_uses (borrows : HashMap String Bool) (target : I64) (t : Term) : I64

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

typeBinderKind#
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).

structBinderUse#
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.

defBinderUse.count#
pub def BinderUse.count (u : BinderUse) : I64

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

defBinderUse.name#
pub def BinderUse.name (u : BinderUse) : Identifier
defBinderUse.typ#
pub def BinderUse.typ (u : BinderUse) : Term
defBinderUse.kind#
pub def BinderUse.kind (u : BinderUse) : BinderKind
defBinderUse.ctor#
pub def BinderUse.ctor (u : BinderUse) : Identifier
defBinderUse.pos#
pub def BinderUse.pos (u : BinderUse) : I64
defBinderUse.owning#
pub def BinderUse.owning (u : BinderUse) : I64
defBinderUse.borrowed#
pub def BinderUse.borrowed (u : BinderUse) : I64
defBinderUse.view#
pub def BinderUse.view (u : BinderUse) : Bool
defBinderUse.moves#
pub def BinderUse.moves (u : BinderUse) : I64
defBinderUse.declared#
pub def BinderUse.declared (u : BinderUse) : Multiplicity
defBinderUse.captured#
pub def BinderUse.captured (u : BinderUse) : I64
defBinderUse.init#
pub def BinderUse.init (u : BinderUse) : Option Term
structViewEnv#
pub struct ViewEnv {
    /// One flag per binder scope, innermost first (`flags[0]` is the
    /// innermost binder).
    flags : List Bool := List.empty,
    inherit : Bool := false,
}
defexpr_is_view#
pub def expr_is_view (shareds : HashMap String Bool) (e : ViewEnv) (t : Term) : Bool

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

defcollect_binder_uses#
pub def collect_binder_uses (ctors : HashMap String Bool) (borrows : HashMap String Bool) (t : Term) : List BinderUse

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

defcollect_binder_uses_with_params#
pub def collect_binder_uses_with_params (params : List Param) (ctors : HashMap String Bool) (borrows : HashMap String Bool) (t : Term) : List BinderUse

Collect 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 declared multiplicity (Param.mult) — always many since the !/?/% prefix syntax was removed from the grammar;
  • a captured count 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.

defbinder_is_hidden_param#
pub def binder_is_hidden_param (b : Binder) : Bool

A binder that is not one of a def's declared parameters: an implicit {A : Type} binder (BinderInfo.binder/level) or a generated __dict_<Class> dictionary parameter, both of which the elaborator inserts around the declared chain.

defview_env_empty#
pub def view_env_empty : ViewEnv
structRedex#
pub 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.

structBindCont#
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.

defspine_head_name#
pub def spine_head_name (t : Term) : Option String

The head name of a call spine, peeling ctx and applications.

defis_bind_head#
pub def is_bind_head (t : Term) : Bool

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

defattribute_binder_types#
pub def attribute_binder_types (s : Scope) (us : List BinderUse) : List BinderUse

Fill in typ for every bk_match binder whose constructor resolves unambiguously. Leaves the rest at Term.hole.