lang::typecheck::ctor_refine

lang/src/typecheck/ctor_refine.mo

Constructor index inversion for indexed families (plans/type-system/dependent-elimination-refinement.md).

Inductive.params mixes uniform parameters and indices: type Vec (len : Nat) A { nil : Vec Nat.zero A, cons ... : Vec (Nat.succ len) A } declares len as a header binder, but each constructor fixes it in its declared return. A header position is an INDEX when some constructor's declared return argument there is not the bare header binder.

Matching a constructor against a scrutinee type solves the constructor's index variables from the scrutinee's index (cons against Vec (succ n) A gives len := n), proves it impossible (nil against Vec (succ n) A: two constructor heads clash), or refines a bound-variable index (cons against Vec m A with m a local: inside the arm, m is succ len@d for a fresh skolem len@d). Anything else is unknown, and every caller then keeps its old behaviour: this module only ever adds information.

Pure: no infer import, so infer can use it without a cycle.

structIndexSolution#
pub struct IndexSolution {
    /// The constructor's index variables, bound to scrutinee subterms or to
    /// fresh skolems.
    subst : List (Pair Identifier Term),
    /// Bound-variable indices of the scrutinee (outer de Bruijn index) and the
    /// constructor index that replaces each inside the arm.
    refine : List (Pair I64 Term),
    /// The same for an index that is a LOCAL binder written by name (an
    /// implicit `{m : Nat}` appears in a parameter's type as the free name `m`).
    refine_named : List (Pair Identifier Term),
}

What a constructor's declared indices tell us about one arm.

typeIndexMatch#
pub type IndexMatch {
    solved (s : IndexSolution),
    /// Two constructor heads clash: the arm can never run.
    impossible,
    /// Nothing safe can be concluded.
    unknown,
}
defindex_positions#
pub def index_positions (ind : Inductive) : List I64

The header positions that some constructor fixes in its declared return. Vec -> [0]; Option, List, Sigma, Eq (whose index is outside the header) -> [], which makes every rule below a no-op for them.

defctor_index_patterns#
pub def ctor_index_patterns (ind : Inductive) (c : InductConstructor) (positions : List I64) : List Term

This constructor's declared index patterns, one per index position. An unannotated constructor's pattern is the header binder itself.

defindex_locals#
pub def index_locals (ind : Inductive) (positions : List I64) : List Identifier

The header binders at the index positions: the names a constructor's index pattern and field types may use as its own variables.

structMatchEnv#
pub struct MatchEnv {
    locals : List Identifier,
    /// The enclosing local binders' names: a free variable spelled with one of
    /// them is a local, not a global, and may be refined by name.
    binders : List Identifier,
    scope : Scope,
    skolem_suffix : String,
}

The matching context: which names are the constructor's index variables, the scope that says which heads are constructors, and the suffix that makes this arm's skolems distinct from any other arm's.

defempty_solution#
pub def empty_solution : IndexSolution
defsolve_ctor#
pub def solve_ctor (env : MatchEnv) (ind : Inductive) (c : InductConstructor) (sc_typ : Term) : IndexMatch

Solve c against the scrutinee type sc_typ. impossible wins over unknown, which wins over solved.

defmatch_index#
pub def match_index (env : MatchEnv) (pattern : Term) (target : Term) (acc : IndexSolution) : IndexMatch

One-way structural match of a declared index pattern against a scrutinee index target. Binds the RAW target subterms (their spelling is the caller's); constructor heads are compared by canonical name only.

defhas_refinement#
pub def has_refinement (s : IndexSolution) : Bool
defrefine_field_types#
pub def refine_field_types (ind : Inductive) (sc_typ : Term) (s : IndexSolution) (field_types : List Term)
: List Term

Field types for an arm. The uniform header params are substituted from the scrutinee's spine by name (exactly as before); the index variables take the solution's bindings instead of the scrutinee's raw index.

defrefine_expected#
pub def refine_expected (s : IndexSolution) (expected : Term) : Term

expected with each refined local (by index or by name) replaced by its constructor index, in the scrutinee's (outer) context.

defapply_subst#
pub def apply_subst (subst : List (Pair Identifier Term)) (t : Term) : Term
defpresent_args#
pub def present_args (args : List (Option Term)) : List Term
defnat_literal_bound#
pub def nat_literal_bound : I64

The largest Nat literal unfolded to a constructor chain; larger ones stay as written and match nothing (unknown).

defnat_literal_term#
pub def nat_literal_term (n : I64) : Term

A small Nat literal as its canonical unary constructor chain. Vec 3 must compare with Vec (succ (succ (succ zero))); Nat.of_i64 3 cannot reduce in the checker (its body tests a native I64.lt).

structIntroCtor#
pub struct IntroCtor {
    ind : Inductive,
    ctor : InductConstructor,
    args : List Term,
}

A constructor application of an indexed family, saturated: one argument per constructor field.

defintro_ctor#
pub def intro_ctor (scope : Scope) (t : Term) : Option IntroCtor

t as a saturated constructor application of an indexed family, if it is one. A constructor two families share, or a partial application, is none.

defnames_constructor#
pub def names_constructor (scope : Scope) (id : Identifier) : Bool

Does id name a constructor in scope: Nat.zero through its owner, or a bare zero owned by some family?

defsame_constructor_ref#
pub def same_constructor_ref (scope : Scope) (a : Identifier) (b : Identifier) : Bool

Do a and b name the same constructor in two spellings (false and Bool.false)? The tails must agree and the two spellings must share an owning family.

defintro_index_bindings#
pub def intro_index_bindings (scope : Scope) (ind : Inductive) (c : InductConstructor) (expected : Term)
: Option (List (Pair Identifier Term))

The bindings for a constructor's index variables when it is checked against expected: the solved values (cons : Vec 1 A gives len := zero, so the tail is checked at Vec zero A), or none when the solution is not plain (unknown, impossible, or a refinement of a variable index).

defintro_indices#
pub def intro_indices (scope : Scope) (arg_type : Term -> Option Term) (ic : IntroCtor) : Option (List Term)

The indices a constructor application produces, one per index position: the constructor's declared index patterns with its index variables solved from the arguments. A field typed by the same family supplies its argument's indices -- a nested constructor application's own, or what arg_type reports for anything else (a typed local). None when an index variable stays unsolved.

defintro_clash#
pub def intro_clash (scope : Scope) (arg_type : Term -> Option Term) (ic : IntroCtor) (expected : Term) : Option Term

Whether an indexed constructor application can have type expected: some found (the application's type, spelled with expected's uniform arguments) when a computed index's constructor head clashes with expected's; none when it fits or nothing safe can be concluded. A variable index on either side is never a clash: it may be refined by an enclosing match the checker does not track.

defwith_indices#
pub def with_indices (t : Term) (positions : List I64) (idx : List Term) : Term

t's spine with the arguments at positions replaced, in order.