lang::types
lang/src/types.mo
pub type Identifier {
id String
}pub def id_eq (a : Identifier) (b : Identifier) : BoolCompare two identifiers for equality (by string value).
pub instance Copy Identifier {
def copy (a : Identifier) : Pair Identifier Identifier := Pair.pair a a
}Identifier is an immutable String wrapper, so sharing one is a
pointer copy -- the same argument Copy String makes (init/copy.mo).
Deliberately NOT extended to NamePath/ModulePath: those hold a
List, and Copy for heap-allocated inductives stays withheld there.
pub instance BEq Identifier {
def beq (a b : Identifier) : Bool := id_eq a b
}pub def union_ids (a : List Identifier) (b : List Identifier) : List IdentifierUnion two lists of identifiers (deduplicated, left-biased order).
pub type AttrArg {
ident (id : Identifier),
str (value : String),
num (value : I64),
named (name : Identifier) (value : AttrArg),
group (items : List AttrArg),
}An argument to a #[name arg1 arg2 ...] attribute. Mirrors the Rust
reference's AttrArg (rust/core/src/term.rs) exactly, including the
named/group shapes ({name := value} / [item, ...]) even
though no real corpus attribute uses either yet — the combinator
cost of supporting them now is near-zero and avoids a later
breaking retype of Attribute.args once one does.
pub struct Attribute {
name : Identifier,
args : List AttrArg,
}A single #[name arg1 arg2 ...] declaration/param annotation, e.g.
#[derive BEq BOrd Debug Lens] — one Attribute with FOUR bare-
ident args (confirmed against the reference grammar: attribute
args are whitespace-separated and flattened onto the one attribute,
not four stacked attributes). Deliberately has no source_location
field (unlike the Rust reference's Attribute, whose own
PartialEq ignores that field anyway) — no sibling decl-level type
here (Def, Inductive, ...) carries source-location data, and
nothing downstream would read it.
pub def empty_attrs : List AttributeThe empty attribute list, under both names the corpus already uses
for it. Declared here, beside Attribute itself, because each was
previously declared TWICE -- empty_attrs in
lang/typecheck/macro_queue.mo and codegen/emit.mo,
no_attrs in codegen/test_driver.mo and
lang/typecheck/meta_reflect.mo -- so each was two definitions of
one LLVM symbol, of which the emitted binary silently kept one.
Both spellings are kept rather than picking a winner: the two names
read differently at their call sites (no_attrs for a synthesized
decl that HAS no attributes, empty_attrs for an accumulator's
zero) and unifying them is a rename sweep with no correctness value.
pub def no_attrs : List Attributepub instance BEq Attribute {
def beq (a b : Attribute) : Bool := attr_eq a b
}pub def has_attr (name : Identifier) (attrs : List Attribute) : BoolWhether attrs contains an attribute named name, e.g.
has_attr (Identifier.id "derive") ind_attrs. Mirrors the Rust
reference's Inductive::has_attr/Def::has_test_attr
(rust/core/src/term.rs).
pub def attr_args (name : Identifier) (attrs : List Attribute) : Option (List AttrArg)The ARGUMENTS of the first attribute named name -- has_attr's
args-reading sibling (has_attr matches Attribute.mk n _ and
drops them). Option.none when no attribute of that name is
present, which is distinct from Option.some List.empty for an
argument-less attribute like #[partial].
Exists for #[decreasing x] (lang/termination.mo), the
one corpus attribute whose args carry meaning: the parser already
produces AttrArg.ident for it (attr_arg_parser,
lang/parser.mo), so what was missing was only a way to read them
back out. codegen reuses it as the one implementation behind its
string-keyed attrs::find_attr_args.
pub struct Operator {
symbol : String,
}pub struct ModulePath {
segments : List Identifier,
}pub def module_mote_of (mp : ModulePath) : Option StringThe mote a canonical module path belongs to: its first segment.
lang::scope -> lang, init::prelude -> init. Every stored module
path is mote-qualified (lib:: is rewritten at load), so this needs no
manifest read and has no IO.
pub def module_path_is_empty (mp : ModulePath) : BoolAn empty module path is not a module: codegen and the unit harness build whole-program scopes with one. Visibility rules treat it as "no boundary", so every caller must ask this before comparing motes.
pub struct NamePath {
segments : List Identifier,
}A term-level dotted name path (Foo.bar.baz) — a DECL name or a
legacy dotted reference. Distinct from ModulePath (a FILE path,
used with ::) since the qualified-names split; see
plans/implementations/qualified-names.md.
pub struct QualifiedName {
qmod : ModulePath,
qname : NamePath,
}A module-qualified term reference (std::list::List.cons) — the
::-separated module half names a real loaded module, the
.-separated name half a decl inside it. Rendered with the module
segments ::-joined, so the string is disjoint from any NamePath
rendering (: can't occur in an identifier).
pub def show_identifier (id : Identifier) : Stringpub def char_to_string (c : Char) : StringA Char's source text -- its UTF-8 bytes back as a String.
Char is of_bytes (List U8) (init/prelude.mo) and carries one
codepoint's worth of them, so this is total and round-trips whatever
char_literal (lang/parser/string.mo) sliced out.
pub def show_module_path (mp : ModulePath) : Stringpub def show_name_path (np : NamePath) : StringA NamePath rendered .-joined (Foo.bar). The RENDERING matches
show_module_path's — the two types differ in role (name vs file
path), not in this one spelling — while use module paths render
::-joined in source (module_path_to_string, lang/parser.mo).
pub def show_qualified_name (qn : QualifiedName) : Stringstd::list::List.cons — module half ::-joined, then ::, then
name half .-joined. Matches the Rust host's Display for
QualifiedName (rust/core/src/term.rs) so DebugName strings stay
compiler-consistent.
pub def qualified_symbol_name (qn : QualifiedName) : StringThe def-side SYMBOL spelling of a qualified name: the module half
dotted, then ::, then the name half dotted (std.process::process_id).
This is not the source spelling (show_qualified_name, whose module
half is ::-joined): it is the convention codegen emits and the
parser lowers a qualified reference to, and the two must agree byte for
byte or a reference cannot find its definition.
pub def module_path_as_npath (mp : ModulePath) : NamePathA module path in NamePath form: the same segments, used where a
table is keyed by a spelling and a use/open path is one of the
keys (the use-completeness gate's own set, an outline's decl name).
pub def qn_of (m : ModulePath) (n : NamePath) : QualifiedNameBuild a qualified name from its two halves. Mirrors the struct
constructor, so call sites that already have a ModulePath and a
NamePath do not have to spell QualifiedName.mk.
pub def npath_last (np : NamePath) : Option IdentifierThe last segment of a name path (List.cons -> cons), if any.
This is the structural form of "the bare name" that scope resolution
and bare-alias bookkeeping need; it replaces slicing the rendered
string at the last dot.
pub def npath_extend (np : NamePath) (id : Identifier) : NamePathAppend one segment to a name path (Foo + bar -> Foo.bar).
pub def module_path_to_string_colon (mp : ModulePath) : StringA module path spelled the way SOURCE spells it: ::-joined
(std::process). This is the right rendering for anything a user
reads -- diagnostics, verbose progress lines, use decls -- because
:: is what they wrote. show_module_path's dot-joined form is the
INTERNAL spelling (symbol names, map keys) and should not surface.
Distinct from the general module_path_to_string (lang/parser.mo)
only to avoid a circular parser->types import; the two agree.
pub type NameMap V {
name_map (HashMap String V)
}pub def name_map_empty {V : Type} : NameMap Vpub def name_map_insert {V : Type} (key : NamePath) (val : V) (m : NameMap V) : NameMap Vpub def name_map_lookup {V : Type} (key : NamePath) (m : NameMap V) : Option Vpub def name_map_values {V : Type} (m : NameMap V) : List VEvery value, in no particular order. Consumers look an entry up by name and then scan the values for a match on the entry's OWN recorded name, so the rendered key is not part of the read surface.
pub def name_map_merge {V : Type} (a : NameMap V) (b : NameMap V) : NameMap VBucket-wise union. a's entries come first, so a wins a duplicate
key -- the same "first argument wins" precedence merge_scope_data
already relies on (HashMap.merge_buckets' own note).
pub type BareNameMap {
bare_name_map (HashMap String (List NamePath))
}A bare-spelling -> owner-paths table (ScopeData.bare_aliases): the
last ::-separated spelling of a registration key against the full
NamePaths that end in it. A bare name is one segment, so the key is
an Identifier; the owners stay NamePaths, so the miss fallback
looks a real name up instead of re-splitting a rendered string.
pub def bare_name_map_empty : BareNameMappub def bare_name_map_lookup (key : Identifier) (m : BareNameMap) : Option (List NamePath)pub def bare_name_map_lookup_spelling (spelling : String) (m : BareNameMap) : Option (List NamePath)Lookup by the bare SPELLING itself (the map's keys are spellings, not parsed names). This is the entry point for a caller holding the text a bare reference was written as.
pub def bare_name_map_insert (key : Identifier) (owners : List NamePath) (m : BareNameMap) : BareNameMappub def bare_name_map_add (bare : Identifier) (owner : NamePath) (m : BareNameMap) : BareNameMappub def bare_name_map_note (owner : NamePath) (m : BareNameMap) : BareNameMapNote owner under its bare spelling. A registration whose rendered
key has no :: is reachable by the exact lookup that always runs
first, and noting it would phantom-ambiguate a qualified owner of the
same name -- so it is skipped.
pub def bare_name_map_merge (a : BareNameMap) (b : BareNameMap) : BareNameMappub type NameSet {
name_set (HashMap String Bool)
}An Identifier-keyed SET (presence only): ScopeData.dict_classes's
type. The table it replaces stored List String values that were
never filled -- every consumer only asks whether a bare class spelling
carries a dictionary -- so the value list encoded nothing.
pub def name_set_empty : NameSetpub def name_set_insert (key : Identifier) (s : NameSet) : NameSetpub def name_set_member (key : Identifier) (s : NameSet) : Boolpub def name_set_union (a : NameSet) (b : NameSet) : NameSetpub type ModuleMap V {
module_map (HashMap String V)
}A ModulePath-keyed map, keyed by the .-joined rendering for the
same reason NameMap is (lang/scope.mo's measured note).
pub def module_map_empty {V : Type} : ModuleMap Vpub def module_map_insert {V : Type} (key : ModulePath) (val : V) (m : ModuleMap V) : ModuleMap Vpub def module_map_values {V : Type} (m : ModuleMap V) : List VEvery value, in no particular order (see name_map_values).
pub def module_map_lookup {V : Type} (key : ModulePath) (m : ModuleMap V) : Option Vpub type ModuleSet {
module_set (HashMap String Bool)
}A ModulePath-keyed set, presence only (the ambient-module table).
pub def module_set_empty : ModuleSetpub def module_set_insert (key : ModulePath) (s : ModuleSet) : ModuleSetpub def module_set_member (key : ModulePath) (s : ModuleSet) : Boolpub def module_set_union (a : ModuleSet) (b : ModuleSet) : ModuleSetpub type NamePathSet {
name_path_set (HashMap String Bool)
}A NamePath-keyed set, presence only: the use gate's own,
open, and per-name "already reported" tables.
pub def name_path_set_empty : NamePathSetpub def name_path_set_insert (key : NamePath) (s : NamePathSet) : NamePathSetpub def name_path_set_member (key : NamePath) (s : NamePathSet) : Boolpub type QualifiedNameSet {
qualified_name_set (HashMap String Bool)
}A QualifiedName-keyed set, presence only: the qualified-reference
de-duplication table.
pub def qualified_name_set_empty : QualifiedNameSetpub def qualified_name_set_insert (key : QualifiedName) (s : QualifiedNameSet) : QualifiedNameSetpub def qualified_name_set_member (key : QualifiedName) (s : QualifiedNameSet) : Boolpub instance Show ModulePath {
def show (mp : ModulePath) : String := show_module_path mp
}pub instance Show NamePath {
def show (np : NamePath) : String := show_name_path np
}The NamePath twin of the ModulePath instance above -- mirrors the
Rust host's own impl Display for NamePath (rust/core/src/term.rs). The
two render identically (.-joined); the instances exist separately
because the two types are no longer interchangeable.
pub instance Show QualifiedName {
def show (qn : QualifiedName) : String := show_qualified_name qn
}A qualified name renders as mod::sub::Name.path; the rendering is
disjoint from every other name shape (: cannot occur in an
identifier), so it is also the equality/order/hash key below.
pub instance BOrd Identifier {
def lt (a b : Identifier) : Bool := BOrd.lt (show_identifier a) (show_identifier b)
def gt (a b : Identifier) : Bool := BOrd.gt (show_identifier a) (show_identifier b)
def lte (a b : Identifier) : Bool := Bool.not (BOrd.gt (show_identifier a) (show_identifier b))
def gte (a b : Identifier) : Bool := Bool.not (BOrd.lt (show_identifier a) (show_identifier b))
}Identifiers can't contain ".", so the dotted-string-join used by show_identifier/show_module_path is collision-free as an ordering key.
pub instance BOrd ModulePath {
def lt (a b : ModulePath) : Bool := BOrd.lt (show_module_path a) (show_module_path b)
def gt (a b : ModulePath) : Bool := BOrd.gt (show_module_path a) (show_module_path b)
def lte (a b : ModulePath) : Bool := Bool.not (BOrd.gt (show_module_path a) (show_module_path b))
def gte (a b : ModulePath) : Bool := Bool.not (BOrd.lt (show_module_path a) (show_module_path b))
}pub instance Hashable Identifier {
def hash (a : Identifier) : U64 := String.hash (show_identifier a)
}Same "collision-free as a string key" property BOrd's own
delegation above already relies on — hash the dotted-string join
rather than writing a separate combining hash over the segment list.
The key that NameMap's backing HashMap String _ hashes, so a
name-keyed map needs no separate combining hash (see
bench/scope_lookup.mo for why HashMap rather than a list or
BTreeMap for scope's lookup-heavy access pattern).
pub instance Hashable ModulePath {
def hash (mp : ModulePath) : U64 := String.hash (show_module_path mp)
}pub instance Hashable NamePath {
def hash (np : NamePath) : U64 := String.hash (show_name_path np)
}pub instance BEq ModulePath {
def beq (a : ModulePath) (b : ModulePath) : Bool :=
String.beq (show_module_path a) (show_module_path b)
}The three structural name types' equality/order/hash instances. The
rendered forms are disjoint (: cannot occur in an identifier, and
the module half is ::-joined while the name half is dot-joined), so
delegating to the renderers is collision-free; Similar stays
structural where it exists (see name_path_similar).
pub instance BEq NamePath {
def beq (a : NamePath) (b : NamePath) : Bool :=
String.beq (show_name_path a) (show_name_path b)
}pub instance BEq QualifiedName {
def beq (a : QualifiedName) (b : QualifiedName) : Bool :=
String.beq (show_qualified_name a) (show_qualified_name b)
}pub instance BOrd NamePath {
def lt (a : NamePath) (b : NamePath) : Bool := BOrd.lt (show_name_path a) (show_name_path b)
def gt (a : NamePath) (b : NamePath) : Bool := BOrd.gt (show_name_path a) (show_name_path b)
def lte (a : NamePath) (b : NamePath) : Bool := Bool.not (BOrd.gt (show_name_path a) (show_name_path b))
def gte (a : NamePath) (b : NamePath) : Bool := Bool.not (BOrd.lt (show_name_path a) (show_name_path b))
}pub instance BOrd QualifiedName {
def lt (a : QualifiedName) (b : QualifiedName) : Bool := BOrd.lt (show_qualified_name a) (show_qualified_name b)
def gt (a : QualifiedName) (b : QualifiedName) : Bool := BOrd.gt (show_qualified_name a) (show_qualified_name b)
def lte (a : QualifiedName) (b : QualifiedName) : Bool := Bool.not (BOrd.gt (show_qualified_name a) (show_qualified_name b))
def gte (a : QualifiedName) (b : QualifiedName) : Bool := Bool.not (BOrd.lt (show_qualified_name a) (show_qualified_name b))
}pub instance Hashable QualifiedName {
def hash (qn : QualifiedName) : U64 := String.hash (show_qualified_name qn)
}pub type NameRef {
nid (Identifier),
/// A dotted name path (`Foo.bar`) — legacy flat spelling or a
/// constructor-owner style name.
nnp (NamePath),
/// An explicit module-qualified reference (`std::list::List.cons`).
nqn (QualifiedName),
nop (Operator),
}pub type Multiplicity {
zero,
many,
linear,
affine,
}pub because Binder/Param are pub and carry one, and tools
outside the lang mote (bench/src/affine_report.mo) construct
binders with an explicit multiplicity.
pub struct Location {
offset : I64,
line : I64,
column : I64,
}pub struct SourceRange {
start : Location,
end : Location,
path : Option Path,
}pub struct LocatedSpan {
fragment : String,
location : Location,
}pub struct Param {
name : Identifier,
type_ : Term,
mult : Multiplicity,
default : Option Term,
attrs : List Attribute,
}pub def param_many (name : Identifier) (type_ : Term) : ParamCanonical sibling of parse_param_many, for code that already holds
a lowered Term.
pub def mk_param (name : Identifier) (type_ : Term) (mult : Multiplicity) : ParamCreate a canonical Param with explicit multiplicity, no default value, and no attributes.
pub def param_with_attrs (name : Identifier) (type_ : Term) (attrs : List Attribute) : ParamCreate a canonical Param with multiplicity=Many, no default value,
and explicit attrs — the one constructor/def-param path that
actually needs a non-empty attrs list (e.g. #[arg]).
pub struct MatchCase {
name : Identifier,
args : List Identifier,
body : Term,
field_pattern : Option FieldPattern,
typ_name : Option NamePath,
}pub struct FieldPattern {
fields : List FieldPatternEntry,
rest : Bool,
}One { field, other := binder, .. } pattern -- mirrors the Rust
reference's FieldPattern (rust/core/src/term.rs). fields is
(field_name, binder) in the order written; binder equals
field_name when punned ({ x }). rest is true when a trailing
.. is present (unlisted fields are discarded, not brought into
scope).
pub struct FieldPatternEntry {
field : Identifier,
binder : Identifier,
}One field or field := binder entry inside a FieldPattern --
a dedicated named-pair type (mirroring StructLitField's own
name/value shape) rather than a generic Pair, so this file
doesn't need a cross-module dependency on init/prelude.mo's Pair
for its own canonical AST.
pub def field_access_chain (scrutinee : Term) (fields : List Identifier) : TermNested bare-form field-pattern Match chain desugaring a dotted-path
field access (p.first, vzero.x) into ordinary struct-field
destructuring -- mirrors the Rust reference's
lower_core.rs::lower_field_access_chain.
Lives here, beside the two types it builds, because it has two callers
that must not drift: the parser's lower_path_ids (a subject that IS a
local binder) and the checker's try_global_field_access
(lang/src/typecheck/infer.mo, a subject that is a top-level def, the
case lower_path_ids cannot settle at parse time). lang::types is the
lowest module both already depend on.
The binder list is [field] inline rather than via
field_pattern_binder_names: the pattern built here has exactly one
entry whose binder IS field, so calling that helper would only add a
dependency back on lang/parser.mo, which the parser's copy of this
module exists without.
pub type NumSuffix {
i8, i16, i32, i64, u8, u16, u32, u64, f32, f64,
}pub type Literal {
str (value : String),
/// A `'c'` literal. Carries a real `Char` -- one Unicode codepoint,
/// mirroring the Rust reference's `Literal::Char(char)` and feeding
/// `IrLit.ir_char` (`lang/core_ir.mo`), which has always wanted a
/// `Char`, unchanged. NOT the source text: `Char`'s own declared
/// shape (`init/prelude.mo`, `of_bytes (List U8)`) holds the
/// codepoint's UTF-8 bytes, and the parser slices exactly one
/// codepoint (`utf8_char_width`) before building it.
char (value : Char),
num (value : I64) (suffix : NumSuffix),
/// A literal written with a decimal point (`3.0`, `3.14f32`). Kept as
/// the exact source text rather than a numeric value: self-hosted
/// Monad code has no native bridge to parse a decimal string into an
/// actual float bit pattern (unlike the Rust reference's
/// `Literal::Float { value: F64Wrap, .. }`, rust/core/src/term.rs), so
/// `text` is the only representation available here — sufficient for
/// round-tripping through `show_term`/parsing back, though genuine
/// float codegen (`codegen/emit.mo` has no float `LLVMValue`
/// variant at all yet) remains a separate, unstarted piece of work.
flt (text : String) (suffix : NumSuffix),
if_ (one : Term) (two : Term) (three : Term),
match_ (value : Term) (cases : List MatchCase),
/// DEPRECATED: never constructed on purpose. Both typechecking
/// (`type_check_struct_lit`, `lang/typecheck/infer.mo`) and codegen
/// (`desugar_struct_lits_decls`, `codegen/emit.mo`) rewrite an
/// annotated struct literal to a real `Term.con` before use; this
/// variant survives only when best-effort elaboration fails, and
/// every survivor is rejected fail-fast by
/// `validate_no_undesugared_struct_lits` (compile path) or
/// `lower_literal`'s `le_struct_lit_survived` (eval path). New code
/// should not add consumers for it.
/// A struct-literal expression (`{ field := value, ... }`),
/// optionally self-annotated with which struct it builds
/// (`{ field := value, ... : StructName }`) — lets the checker
/// resolve the struct name directly without needing an ambient
/// expected type from context (a struct literal doesn't always have
/// one, e.g. passed to a generic function). Mirrors the Rust
/// reference's `CoreLit::StructLit` (rust/core/src/core_term.rs).
struct_lit (fields : List StructLitField) (type_name : Option Term),
/// DEPRECATED: never constructed on purpose. Both typechecking
/// (`type_check_struct_update`, `lang/typecheck/infer.mo`) and
/// codegen (`desugar_struct_lits_decls`, `codegen/emit.mo`)
/// rewrite a struct update away before use; this variant survives
/// only when best-effort elaboration fails, and every survivor is
/// rejected fail-fast by `validate_no_undesugared_struct_lits`
/// (compile path) or `lower_literal`'s `le_struct_lit_survived`
/// (eval path). New code should not add consumers for it.
/// `{ base with field := value, ... }` — a copy of `base` (an
/// existing struct VALUE, not a type name) with the listed fields
/// replaced. `base` is a resolved `Term` (typically `Term.var`) here
/// rather than a bare `Identifier`, unlike the Rust reference's own
/// SOURCE-level `term::Literal::StructUpdate` — this checker has no
/// separate parse-then-lower stage the way the reference's
/// `Literal` (pre-lowering) vs `CoreLit` (post-lowering,
/// `base: Box<CoreTerm>`) split does, so the parser resolves `base`
/// directly, matching every other variable reference elsewhere in
/// this file (`Term.var`/`variable`). Mirrors the Rust reference's
/// `CoreLit::StructUpdate`.
struct_update (base : Term) (fields : List StructLitField),
}pub struct StructLitField {
name : Identifier,
value : Term,
}A single name := value field inside a struct-literal EXPRESSION
({ x := 1, y := 2 }) — as distinct from StructField's
DECLARATION shape (x : T := default). Mirrors one entry of the
Rust reference's CoreLit::StructLit's fields: Map<Identifier, CoreTerm>; order here doesn't matter (fields are matched by name)
— the struct's own declared field order (from its registered
Param list, see build_scope_struct) is what determines the
final constructor-argument order once type_check_lit resolves
this into a Term.con.
pub struct Con {
name : Identifier,
typ_name : NamePath,
num_args : I64,
args : List (Option Term),
}pub struct Native {
native_name : Identifier,
num_args : I64,
args : List (Option Term),
}pub type CubicalPrim {
/// The interval type `I`. Not a `Sort`, and deliberately NOT an
/// inductive: a two-constructor `I` would make `match` on a dimension
/// admissible, which destroys univalence.
interval,
/// The two endpoints, `i0 : I` and `i1 : I`.
i0,
i1,
/// De Morgan interval operations: `ineg i`, `imeet i j`, `ijoin i j`.
/// Spelled as names rather than `~`/`/\`/`\/` because `op_chars`
/// (`lang/parser/core.mo`) is maximal-munch, so adding an operator
/// character retokenizes the compiler's own source.
ineg,
imeet,
ijoin,
/// The heterogeneous path former `PathP A a b`, over a line
/// `A : I -> Sort l` (Stage 2, plans/type-system/univalence.md).
/// The one primitive whose arguments are NOT dimensions: a line of
/// types and the two endpoint values. A path abstraction is an
/// ordinary `Term.lam` with an `I`-typed binder, so this primitive is
/// never a binder either.
pathp,
/// Transport along a line of types: `transp A a : A i1` for
/// `A : I -> Sort l` and `a : A i0` (Stage 3,
/// plans/type-system/univalence.md). `transp` rather than CCHM's
/// `comp` so the stage can land before the face lattice exists --
/// it takes no cofibration. Like `pathp`, its arguments are not
/// dimensions.
transp,
/// The two cofibration generators `face_eq0 i` / `face_eq1 i` --
/// the constraints `i = 0` / `i = 1` -- and the truth predicate
/// `is_one φ : Sort 1` (Stage 4). Cofibrations are INTERVAL terms:
/// `∧`/`∨` are the existing `imeet`/`ijoin` and `0`/`1` the
/// endpoints, so these three are the only new formers the face
/// lattice needs. A partial element over `φ` is then an ordinary
/// function `is_one φ -> A` -- Agda's encoding, no new syntax. Note
/// `is_one`'s result is a SORT: it is a former of types, like
/// `pathp`, and unlike everything else in this list its arguments
/// are still dimensions.
face_eq0,
face_eq1,
is_one,
/// Kan composition: `hcomp A φ u u0 : A` for a type `A`, a
/// cofibration `φ`, a system `u : I -> is_one φ -> A`, and a base
/// `u0 : A` (Stage 5, plans/type-system/univalence.md). The
/// arguments are not dimensions (`A` and the two elements) and not
/// all of the same shape, which is why this prim gets its own
/// typing rule rather than the generic `check_cubical_args_then`.
///
/// The BOUNDARY law is CCHM's: on `φ` the composite IS the system's
/// top, `hcomp A φ u u0 ≡ u i1`. Note what that does NOT say: `u0`
/// is the system's BOTTOM (`u i0 = u0` on `φ`), so `hcomp A i1 u u0`
/// is `u i1`, never `u0`; that asymmetry is why the two decided
/// cases get different answers. When `face_decide` refutes `φ` the
/// system constrains nothing and `whnf_hcomp` answers the base
/// (`hcomp A i0 u u0 ≡ u0`, the empty box's composition); when `φ`
/// is the LITERAL `i1` the answer is the system's top `u i1`
/// applied to `it_is_one` below. `whnf_hcomp`
/// (`lang/typecheck/whnf.mo`) is the reducer and states both.
hcomp,
/// The canonical inhabitant of `is_one i1` (Stage 6b,
/// plans/type-system/univalence.md) -- Agda's `itIsOne`, and the
/// term Stage 4's `is_one` and Stage 5's `hcomp` both recorded as
/// missing. `is_one φ` is inhabited by construction only when `φ` IS
/// `i1`, which is why the one-argument-at-a-time reduction rules that
/// consume it (`whnf_hcomp`, and `Glue`'s in Stage 6b-ii) trigger on
/// the literal endpoint rather than on `face_decide`'s
/// `some true`: the decider answers a FACT about `φ`, this term is a
/// PROOF of `is_one i1`, and reduction has no conversion check that
/// could move one to the other.
///
/// Zero arguments and not a former: its result type is the fixed
/// `is_one i1`, so it needs no rule of its own -- `cubical_result_type`
/// (`lang/typecheck/infer.mo`) states it and both typing paths a
/// zero-arity primitive can take already read that table.
it_is_one,
/// The `Glue` type former (Stage 6b-ii,
/// plans/type-system/univalence.md): `Glue A φ T w` for a type `A`, a
/// cofibration `φ`, a partial type `T : is_one φ -> Type`, and a
/// partial equivalence `w : (u : is_one φ) -> Equiv (T u) A`. The
/// partial pair is `hcomp`'s own "function out of `is_one φ`"
/// encoding, so no new syntax.
///
/// `w`'s type is why the rule is bespoke: it names `Equiv`, which
/// lives in `proofs` -- above this checker -- so the rule builds the
/// `Sigma`/`Pi`/`PathP` unfolding itself. `univalence.md`'s 6b-ii
/// measurement records why the alternative (moving `Equiv` down into
/// the prelude so the rule could name it) is blocked, and that the pin
/// meant to tie this unfolding to the library's `Equiv` is not
/// expressible yet -- library drift is a recorded OPEN risk, not a
/// controlled one.
glue,
/// The `Glue` introduction. Six arguments, not the two of Agda's
/// `glue t a`: the reduction `glue ... t a ≡ t it_is_one` fires at the
/// literal `i1`, and `whnf` has no expected type to read φ from, so φ
/// (and the rest of the formation's arguments) has to be carried.
/// A two-argument form could only reduce unconditionally, which is
/// subject reduction-unsound for `φ ≠ i1`.
glue_intro,
/// `unglue g : A` for `g : Glue A φ T w`, computed by iota on the
/// introduction: `unglue (glue A φ T w t a) ≡ a` for EVERY `φ`. That
/// unconditional iota is the half of CCHM's rule that needs no
/// boundary condition; the `Sigma.fst (w witness) g` half needs
/// `w t = a`, which nothing enforces (the same unenforced shape as
/// `hcomp`'s `u i0 = u0`), so a neutral `unglue` stays stuck.
glue_elim,
/// A two-clause partial SYSTEM: `system φ1 u1 φ2 u2` is the partial
/// element that is `u1` on the face `φ1` and `u2` on `φ2`. It is typed as
/// the function `is_one (ijoin φ1 φ2) -> A` (the clauses' common type),
/// and its application rule selects a clause when the face decides at a
/// literal endpoint. This is what `ua` needs and `is_one φ -> Type`
/// cannot express: `∂ i` is true at BOTH endpoints, so a total function
/// out of the proposition cannot say which clause applies.
system,
}pub struct Cubical {
prim : CubicalPrim,
args : List Term,
}One cubical primitive applied to args, whose length is its arity.
pub instance Copy CubicalPrim {
def copy (p : CubicalPrim) : Pair CubicalPrim CubicalPrim := Pair.pair p p
}pub type DebugName {
named (id : Identifier),
unnamed,
}pub def sentinel : I64Free-variable sentinel de Bruijn index: >= 0 means bound, -1
means free/unresolved. The parser emits it for every not-yet-
resolved Term.var, and lang.scope/lang.typecheck compare
against it to decide whether a variable still needs resolving.
Declared here, in the module that owns Term/DebugName, because
it is part of that representation's contract rather than any one
pass's private constant. It previously existed as five byte-
identical copies (lang/parser.mo, lang/elaborate.mo,
lang/lower_core_ir.mo, lang/typecheck/infer.mo,
lang/typecheck/meta_reflect.mo); since codegen mangles a top-
level def to its BARE name, those five were five definitions of
one LLVM symbol @sentinel, of which the emitted binary silently
kept one -- see validate_no_colliding_def_symbols
(codegen/emit.mo), which now rejects that shape outright.
pub type Visibility {
pub_,
priv_,
package_private,
}Visibility of a declaration. Mirrors the Rust reference's
core::term::Visibility exactly: priv is enforced immediately
(module boundaries already exist), pub vs. the default
package_private is a no-op until a package system exists. Applies to
def/type/class/struct/instance/infix — NOT use (which
gets its own separate public: Bool field directly on Decl.use_d,
since priv use isn't a real form) or open (no visibility concept
at all).
pub type AffineMode {
affine_error,
affine_warn,
}How strictly a mote enforces the affine-by-default usage rule, from
its [affine] mode manifest key (lang/src/mote.mo reads it,
lang/src/module.mo classifies diagnostics by it).
affine_error is the default and the intended end state: an
over-used binder fails the build exactly like a type error.
affine_warn exists only for a mote that has not reached zero
violations yet -- it reports the same diagnostics through the
warning channel, so the rule is still computed and visible. A mote
deletes the key (returning to error) when its count reaches zero.
There is deliberately no off: the rule is always computed.
pub struct ParseSpan {
start_rem : I64,
end_rem : I64,
}Where a ParseTerm came from, recorded as the LENGTH OF THE REMAINING
INPUT at the start and end of the construct.
Not an absolute offset, because no parser def sees the whole file --
each one is handed only the unconsumed remainder, and the whole file
exists nowhere in the grammar at all -- only build_loc_table, which
runs after the parse, ever holds it. Both
numbers here are available locally and for free: String.length input
before a parser runs and String.length rem after it succeeds, each
an O(1) read on the SharedStr window the remainder actually is.
Recording an absolute offset instead would mean threading the file
(or its length) through all ~235 grammar defs -- re-adding exactly
the threading that dropping the de Bruijn ctx removes.
Converted to a real SourceRange only at the top level, where the
file IS known: offset = total_length - start_rem, then
lang/parser/position.mo's divide-and-conquer scan for line/column.
Note the ordering is inverted from an offset -- a LARGER start_rem
means EARLIER in the file.
pub struct ParseTerm {
span : ParseSpan,
kind : ParseTermKind,
}pub struct ParseParam {
name : Identifier,
type_ : ParseTerm,
mult : Multiplicity,
default : Option ParseTerm,
attrs : List Attribute,
}pub struct ParseStructField {
name : Identifier,
typ : ParseTerm,
default : Option ParseTerm,
mult : Multiplicity,
}pub struct ParseInductConstructor {
name : NamePath,
params : List ParseParam,
typ : ParseTerm,
}pub struct ParseClassDef {
name : Identifier,
typ : ParseTerm,
default : Option ParseTerm,
}pub struct ParseDef {
name : NamePath,
typ : ParseTerm,
term : ParseTerm,
constraints : List TypeConstraint,
attrs : List Attribute,
vis : Visibility,
params : List ParseParam
}pub struct ParseInductive {
name : NamePath,
params : List ParseParam,
typ : ParseTerm,
constructors : List ParseInductConstructor,
attrs : List Attribute,
vis : Visibility,
}pub struct ParseClass {
name : Identifier,
params : List ParseParam,
constraints : List TypeConstraint,
methods : List ParseClassDef,
vis : Visibility,
/// The declared result sort (`: Sort (max 1 u)`, `: Prop`), or `None`
/// when the class head omits it. Lowered into `Class.sort`.
sort : Option ParseTerm,
/// The head's `{S : Type}` binders. Lowered into `Class.determined`.
determined : List ParseParam,
}pub struct ParseInstance {
name : Identifier,
cls : NamePath,
constraints : List TypeConstraint,
args : List ParseTerm,
vis : Visibility,
implicit_params : List ParseParam,
defs : List ParseDef,
}pub struct ParseStruct {
name : Identifier,
fields : List ParseStructField,
/// `#[...]` attributes stacked above the `struct` keyword — the same
/// slot `ParseInductive` has carried since `#[derive_cli]` had to
/// survive `type` (see `lang/parser.mo`'s `type_try_attrs`). Needed
/// for `#[derive BEq BOrd Debug Lens] struct Point {...}`
/// (`examples/derive.mo`), which the bridge in
/// `lang/typecheck/macro_queue.mo` reads back off the lowered
/// `Struct`.
attrs : List Attribute,
vis : Visibility,
}pub struct ParseDecl {
span : ParseSpan,
kind : ParseDeclKind,
}A declaration plus the span it was parsed from.
The span is what collapsed the two parallel top-level parsers into
one. A second parser (decls_skip_with_locs) used to re-derive each
declaration's position by threading the whole file alongside the
shrinking input; positions became a projection over the span recorded
here instead -- at the top level the total length IS available, so
offset = total_length - span.start_rem, then
lang/parser/position.mo's scan for line/column. Same arithmetic,
one parser instead of two, and no way for the two to disagree about
where a declaration starts.
pub type ParseDeclKind {
def_d (ParseDef),
inductive_d (ParseInductive),
struct_d (ParseStruct),
class_d (ParseClass),
instance_d (ParseInstance),
infix_d (op : Operator) (path : NamePath) (vis : Visibility),
use_d (path : ModulePath) (filter : UseFilter) (public : Bool),
open_d (path : NamePath) (filter : OpenFilter),
scoped_open_d (path : NamePath) (filter : OpenFilter) (decl : ParseDecl),
def_macro_d (ParseDef),
decl_gen_d (name : NamePath) (params : List ParseParam) (decl_list : List ParseDecl) (attrs : List Attribute),
macro_call_d (name : Identifier) (args : List ParseTerm),
/// `with Dotted.Name { <decls> }` — a name-prefixing decl block
/// that is OPEN inside its own body: every named declaration inside
/// gets `Dotted.Name.` prepended to its name (`with Cubical { def i0
/// : I }` declares `Cubical.i0`), and a bare reference inside the
/// block that names a sibling declaration lowers to the sibling's
/// prefixed spelling (`I` -> `Cubical.I`) unless a local binder
/// shadows it. Names the block does not declare stay bare, and a
/// fully-qualified spelling is unchanged. `prefix` is the header's
/// dotted name as one identifier ("Dotted.Name"), the same
/// `join_dotted_identifiers` shape `dotted_def_name` gives a def's
/// own dotted name (`lang/parser.mo`).
with_d (prefix : Identifier) (decl_list : List ParseDecl),
/// `#![mote { ... }]` — the file-level INNER attribute, carried until
/// lowering as `Decl.mote_d`. Appended LAST deliberately: these are
/// constructor-named variants, so nothing is positional, but a
/// variant's TAG is its declaration order and appending is what
/// guarantees no existing tag moves.
mote_d (attr : Attribute),
/// `#[...]` attributes ahead of a `use`/`open`, which carry no
/// attribute slot of their own. Parser-internal: every entry point
/// runs `cfg_filter_parse_decls` (`lang/src/parser/lower_parse.mo`),
/// which drops it or unwraps it to `decl` before lowering.
attrs_d (attrs : List Attribute) (decl : ParseDecl),
}pub type ParseTermKind {
var (name : NameRef),
/// Term-position `name!`. Kept a separate variant rather than a
/// tagged `var` for the same reason `Term.var_macro` is (see its own
/// doc comment): macro names resolve in a separate namespace.
var_macro (name : NameRef),
lam (name : Identifier) (typ : ParseTerm) (body : ParseTerm),
forall (name : Identifier) (typ : ParseTerm) (body : ParseTerm),
/// `arg_name` is `some` for a written dependent arrow
/// (`(n : T) -> body`, which binds `n` over `body`) AND, since R2a',
/// for each parameter `build_param_pi_chain` folds out of a `def`'s
/// parameter list — a declared signature is dependent whenever it
/// says it is. It is `none` only for the genuinely non-dependent
/// chains `build_pi_chain` folds (class-method parameter types, which
/// carry no names at all). Mirrors the Rust reference's `Term::Pi { arg_name:
/// Option<Name>, .. }` (`rust/core/src/term.rs`), whose `lower_core.rs`
/// arm likewise pushes `arg_name` into scope only when it is `Some`.
///
/// The distinction is load-bearing, not cosmetic: `Term.pi` has no
/// field to carry a binder name, so a name dropped here is gone for
/// good and every use of it inside `ret` resolves to `sentinel`.
/// This branch shipped exactly that regression once.
pi (arg_name : Option Identifier) (arg : ParseTerm) (ret : ParseTerm),
app (fun : ParseTerm) (arg : ParseTerm),
lit (value : ParseLiteral),
// `forall`, `ntv` and `con` were spelled here to mirror the old
// `Term`; no syntax produces one: there is no `forall` keyword in the
// grammar,
// natives arrive through an attribute rather than a term, and the
// parser has never built a `Term.con` (constructor applications are
// ordinary `app`s of a `var` until the type checker resolves them).
// `Term.forall` itself is gone -- R2b folded it into `Term.pi` -- but
// this parse-tree variant stays because deleting it would mean
// touching the lowering arms for no gain. They carry no `pt_*` smart
// constructor for that reason -- only the lowering arms and
// exhaustive matches name them.
ntv (native : ParseNative),
con (c : ParseCon),
/// A sort, as a `SortLevel` -- which covers a concrete numeral exactly as
/// well as a level VARIABLE or a computed `max`/`succ`. The sole sort
/// spelling: a sibling `type_ (universe: I64)` used to carry the concrete
/// levels, which meant every level could be written two ways and every
/// match site had to absorb both shapes.
sort (level : SortLevel),
quote_ (term : ParseTerm),
/// A `do { }` block, kept as STATEMENTS rather than desugared during
/// parsing. Do-notation is syntax, so it belongs in the parse AST;
/// Preserved as syntax and desugared by `lower_parse_do` once the
/// binder context is known. The grammar used to desugar inline,
/// which is only possible while it also threads `ctx`.
do_ (stmts : List DoStmt),
/// `f #Named.Instance args`'s instance hint -- the parsed `#` marker.
/// Only ever appears as the FIRST argument of an application
/// (`pt_dict_hint` is emitted by `dict_hint_term`, lang/src/parser.mo,
/// as `app <callee> (dict_hint ...)`), never free-standing. Lowering
/// turns it into the `Term.var` marker argument the dict-resolution
/// pass strips back off; it survives lowering ONLY as that marker.
dict_hint (name : Identifier),
hole,
}pub struct ParseMatchCase {
name : Identifier,
args : List Identifier,
body : ParseTerm,
field_pattern : Option FieldPattern,
}pub struct ParseStructLitField {
name : Identifier,
value : ParseTerm,
}pub struct ParseCon {
name : Identifier,
typ_name : NamePath,
num_args : I64,
args : List (Option ParseTerm),
}pub struct ParseNative {
native_name : Identifier,
num_args : I64,
args : List (Option ParseTerm),
}pub type SortLevel {
concrete (level : I64),
var (name : Identifier),
max (left : SortLevel) (right : SortLevel),
succ (inner : SortLevel),
}pub type BinderInfo {
/// `(x : T) -> U` — an ordinary explicit parameter. Every `lam`'s
/// binder, and the only kind `pi` had before R2.
explicit,
/// A quantified type variable, whose domain is a real type —
/// `{A : Type} -> …`. This is what a `Term.forall` became when R2b folded
/// it into `pi`; `binder_binder` above is its sole constructor.
binder,
/// A universe-LEVEL binder, whose domain is a level rather than a type.
/// This was `forall`'s marker, recognised before R2b by
/// `is_level_binder_kind` testing whether the binder's `kind` term was a
/// sort at level 0 — a shape test on a term standing in for a property of
/// the binder. That test is now the tag it was always describing (see
/// `binder_is_level` below), which is what removes the hazard the old
/// comment recorded: the marker was only collision-free because the
/// grammar has no `forall` keyword.
level,
}How a binder BEHAVES — everything about a binder that is not its name.
This type exists so that a binder's name and its behaviour travel as one
unit rather than as two parameters. They always co-occur (pi and lam
are the only binders, and every binder has both), so carrying them
separately would mean two fields that are only ever written together.
pub struct Binder {
name : DebugName,
info : BinderInfo,
mult : Multiplicity,
}A binder: what it is called, how it behaves, and its declared multiplicity.
name is a DebugName, which is error-message metadata and NEVER
identity — de Bruijn indices determine identity, and this field changes
no index. BinderInfo is what the checker actually discriminates on.
mult is the source's !/?/% prefix (or many, the parser's
spelling for "none written"). It is carried on the binder rather than on
Term.lam/Term.pi because those variants are matched positionally
across the corpus and an arity change fails at runtime, not at compile
time. It is NOT part of de Bruijn identity and Similar Binder
deliberately ignores it.
The helper defs below default it to Multiplicity.many; the affine
checker fills in a def's declared Def.params multiplicities with
usage.mo's collect_binder_uses_with_params before it counts uses.
pub def binder_explicit (d : DebugName) : BinderA binder from a DebugName the caller already holds, under the
behaviour lam always wants. binder_anon and binder_named below
are its two shorthand spellings -- they cover the construction site
that has no name to give and the one that has an Identifier -- and
this is the one for a DebugName in hand, which is what a Term.lam
carries and why R2c needed it.
pub def binder_anon : BinderThe binder an anonymous construction site wants: nothing for the error message, an ordinary explicit parameter. A named def rather than an inline literal because a bare struct literal in argument position is a known miscompile, and because one spelling makes the hundred-odd call sites that have no name to give read identically.
pub, with Binder/BinderInfo above it, because proofs/ is a
separate mote and builds anonymous Term.pis in
proofs/src/checker/sort_props.mo. That mote's harness.mo records
keeping lang's export surface at zero as a deliberate constraint;
this is the third deliberate widening (after DebugName for W1.2 and
level_const for W1.4), and the alternative -- spelling the struct
literal at each site -- is the miscompile trap the line above names.
pub def binder_named (n : Identifier) : BinderThe binder a NAMED arrow carries — (n : T) -> body puts n in scope
over body. Same construction discipline as binder_anon above, and
for the same reason.
This is the half of R2 that makes a declared dependent signature mean
something. build_param_pi_chain folds a def's parameter list into a
pi chain, and before R2a' it had no name to pass, so every parameter
type and the return type were lowered at the SAME depth while
type_check_pi checked the codomain under List.cons arg local_types
and term_map_children_at_depth walked ret at depth 1. Threading the
name moves the producer onto the consumers' side: a mention of an
earlier parameter now binds instead of resolving to sentinel.
pub def binder_named_mult (n : Identifier) (m : Multiplicity) : Binderbinder_named, with an explicit declared multiplicity. The
def-parameter path reads Param.mult directly (collect_binder_uses_with_params);
this is the constructor for a binder that already carries one (tests,
and the future expression-lambda plumbing).
pub def binder_binder (n : Identifier) : BinderThe binder wrap_forall (lang/elaborate.mo) puts on a quantified type
variable — forall's term-level flavour, {A : Type} -> …. Built here
rather than at the wrap site for the same reason as the two above, and
because R2b's fold needs exactly one place that says what a former
forall lowers to.
The Term side of that fold is the dom: wrap_forall writes
Term.sort (SortLevel.concrete 1), which is Type, and that is right —
the binder's domain really is the type its variable ranges over. Only the
discriminator moved, from "is the kind a sort at level 0?" to this tag.
pub def binder_level (n : Identifier) : BinderThe binder wrap_level_forall puts on a universe level — Sort u in a
signature, bound by the enclosing def. Same discipline as binder_binder
above; wrap_level_forall writes Term.sort (SortLevel.concrete 0) as the
domain, which is the marker the old is_level_binder_kind read.
pub def binder_info_tag (i : BinderInfo) : I64Every BinderInfo, as a number. Same purpose as cubical_prim_tag: the
type is payload-free, so equality IS tag equality, and a spelled-out 3×3
cross product is nine places to get the answer wrong for the same result.
Read by binder_info_eq and by the Similar instance below it.
pub def binder_info_eq (a : BinderInfo) (b : BinderInfo) : Boolpub def binder_info_of (b : Binder) : BinderInfoWhat a binder's behaviour is, for a caller holding a whole Binder.
A named def rather than a field read because reading a struct field
inside a recursive walk defeats the termination checker where a
pattern binder does not (AGENTS.md).
pub def binder_is_explicit (b : Binder) : BoolIs this an ordinary arrow's binder -- (x : T) -> U?
The question a walker asks when it has to decide whether a pi is a
REAL function type or one of the two former forall flavours. It was
never asked before R2b: forall and pi were different constructors,
so a walker that cared told them apart by shape. Now they share an arm
and info is the only thing that separates them, which is why this
exists as a named predicate rather than a field read at each site.
pub def binder_is_level (b : Binder) : BoolIs this a LEVEL binder rather than a type-variable binder?
This was a SHAPE test on the binder's kind term until R2b: a
Term.forall carried wrap_level_forall's marker
(Term.sort (SortLevel.concrete 0)) as its kind, where wrap_forall
used level 1, so "is a sort at level 0" was the whole discriminator --
a property of the binder read off a term standing in for it. The fold
deleted the kind term and made the property the tag it always was.
That is also why this lives here now: the old test walked a Term and
so had to sit beside term_map_children in lang/typecheck/levels.mo;
a tag comparison has no such dependency.
The collision the old test reasoned about is gone rather than
mitigated: no term is a binder's info, so nothing a program writes
can be mistaken for a level marker.
pub def binder_name (b : Binder) : DebugNameWhat a binder is called, for a caller holding a whole Binder.
Companion to binder_info_of and a named def for the same reason:
b.name by field access inside a recursive walk loses the
termination proof.
pub struct Elim {
inductive : NamePath,
levels : List SortLevel,
params : List Term,
indices : List Term,
motive : Term,
minors : List Term,
scrutinee : Term,
}The one elimination form -- core-term-simplification.md R3. if c t e
is an Elim on Bool with a constant motive and minors := [t, e];
match is an Elim whose minors are the arm bodies as lambda chains
(one per constructor, binding its fields left to right), which is why
MatchCase's simultaneous multi-level substitution has no counterpart
here -- a lambda chain binds one level at a time, so beta_reduce/
term_shift need no special case for it. motive : P : … -> T … -> Sort l is what makes an arm's expected type motive (K args) by
construction, which is what delivers dependent elimination (R4);
elaboration without an expected type falls back to a constant motive,
reproducing today's non-dependent behaviour exactly.
levels/params are the inductive's own universe/type arguments (so a
polymorphic List's Elim carries which A this one eliminates
over); levels : List SortLevel needs no Term-walking of its own --
SortLevel is closed over I64/Identifier/itself, never Term.
indices (R4c, core-term-simplification.md) are the CONCRETE index
values for an indexed family (Eq A a b's b) -- the same role
scrutinee plays for the thing being eliminated itself, not a count or
a type. params ++ indices together reconstruct the scrutinee's own
full type application spine. Empty for a non-indexed inductive (every
Bool/Shape/Sigma-shaped Elim so far) -- R3b's elaboration
functions only ever build those, so this list is List.empty
everywhere one is actually constructed today.
R3c wired the pipeline: type_check_if/type_check_match now RETURN a
Term.elim, and both backends lower it back to a Literal before codegen
(lang/src/elim_lower.mo). Every walker's elim arm is therefore live, not
unreachable.
pub type Term {
var (idx : I64) (dbg : DebugName),
/// The lambda, and the ONLY binder over a term. Its binder is an
/// ANNOTATION, exactly as `pi`'s below is, and its `info` is ALWAYS
/// `explicit` -- a lambda's argument is written, never implicit -- so
/// nothing discriminates on it. R2c gave it the `Binder` `pi` already
/// had, for uniformity; `binder_is_explicit` answering `true` for a
/// lambda is the contract that buys.
lam (b : Binder) (typ : Term) (body : Term),
/// A function type, and the ONLY binder over a type. `forall` used to sit
/// beside it as a second spelling; R2b folded it in, so `b`'s `info` is
/// now what tells a quantified type variable (`binder`), a universe level
/// (`level`) and an ordinary arrow (`explicit`) apart, and `arg` carries a
/// former `forall`'s `kind` unchanged (a `Term.sort`, which is exactly the
/// domain its variable ranges over).
///
/// The binder is an ANNOTATION, exactly as `lam`'s `dbg` is: the name never
/// affects an index, because the parser already binds it before `Term`
/// exists (`lower_parse.mo`'s `pi_ret_ctx` extends the lowering context by
/// the arrow's own binder -- the anonymous case included, under a name no
/// source can spell), and
/// `term_map_children_at_depth` already walks `ret` at depth 1. R2a stopped
/// `pi` from DROPPING the name it was given; R2a' made the grammar actually
/// give it one for a `def`'s parameter list (`binder_named` above).
pi (b : Binder) (arg : Term) (ret : Term),
app (fun : Term) (arg : Term),
lit (value : Literal),
ntv (native : Native),
con (c : Con),
hole,
/// `quote { <term> }` -- syntax as data. Mirrors the Rust reference's
/// `Term::Quote { term: Box<Term> }` (rust/core/src/term.rs). Named
/// `quote_`, not `quote` -- `quote` is a reserved keyword in the
/// self-hosted grammar's own identifier parser too (same reason
/// `type_`/`if_`/`match_` above are suffixed, not bare). Parsing/
/// representation only in this codebase so far -- no expansion pass
/// exists yet to resolve `unquote`/`,(expr)` inside the quoted body
/// (see plans/bootstrapping/self-hosted-compiler.md); `unquote`
/// itself needs no special grammar at all, since it's just an
/// ordinary identifier at parse time (recognized as magic only at
/// expansion time, mirroring the reference exactly).
quote_ (term : Term),
/// Term-position `name!` (`foo!`, `foo! 1 2`). Structurally
/// identical to `Term.var` (`idx`/`dbg`) -- `idx` is always
/// `sentinel` in practice, since macro names are resolved in a
/// separate namespace at expansion time, never via de Bruijn lookup
/// against a local `ctx` the way an ordinary bound variable is.
/// A separate sibling variant, not a tagged `Term.var`, because
/// self-hosted has no `NameRef` at the canonical term level to add
/// a `Macro` case to the way the Rust reference's
/// `Term::Var{name: NameRef::Macro(_)}` does (a qualified/dotted
/// name here is just one joined `Identifier` string, not a
/// structured `NameRef`) -- see
/// plans/bootstrapping/self-hosted-compiler.md for the alternatives
/// considered and rejected (baking `!` into the identifier string;
/// a 3rd `DebugName` variant, ruled out as live-regression-risky
/// since `DebugName` is matched exhaustively in several real
/// hot-path files).
var_macro (idx : I64) (dbg : DebugName),
/// A source position attached to the term it wraps. Mirrors the Rust
/// reference's `Term::Ctx { loc, module, term }` (`rust/core/src/term.rs`),
/// minus the module -- DWARF needs a point, and the file is known at
/// emission.
///
/// A WRAPPER rather than a field on each variant: a field changes all
/// twelve constructor arities, and every positional match on them
/// breaks at RUNTIME with `expected N constructor fields, got N+1`,
/// no location, across ~2262 occurrence sites. A wrapper leaves every
/// existing pattern working.
///
/// It is also NOT a side table, which would be the cheaper-looking
/// option: `Term` has no node identity to key one by. `var.idx` is
/// positional and rewritten by `term_shift`/`term_permute`, and
/// `DebugName` is documented as explicitly not identity and is
/// rewritten by `resolve_infix_term`, `qualify_modules` and
/// `infer.mo`'s mangling. Nothing stable exists to point at.
///
/// **Semantically transparent.** A wrapper may change what the
/// compiler ANNOTATES and must never change what it DECIDES, so every
/// site that inspects a term's SHAPE peels first (`term_peel`), and
/// every site that rebuilds preserves (`Term.ctx loc (f inner)`).
/// `tools/debug_transparency_oracle.sh` is what enforces this: strip
/// `!dbg` from a `--debug` build and it must be byte-identical to the
/// non-debug build.
///
/// Constructed on EVERY path, not only under `compile --debug`. The
/// located entry point is the one production parse site:
/// `parse_all_decls` (`lang/src/module.mo`) is written against
/// `decls_parser_located`, so `check`, `test`, `compile` and `pretty`
/// all see wrappers, and the corpus exercises transparency
/// continuously rather than only in a debug build. (Corrected
/// 2026-09-29: this said the opposite -- "constructed ONLY by the
/// located parser entry point, so `check`, `test` and a non-debug
/// `compile` never see one" -- and believing it is exactly what makes
/// a reader conclude a new tool must switch the check path to the
/// located parser. It must not; it is already there.) Not every node
/// carries one: `kind_wants_loc` (`lang/src/parser/lower_parse.mo`)
/// excludes the kinds whose position is not worth recording, and a
/// located def's BODY carries one by construction
/// (`codegen/src/ctx.mo`).
ctx (loc : Location) (term : Term),
/// A sort, at a level that may be a plain numeral or a level expression
/// (`var`/`max`/`succ`). The ONLY sort spelling at the canonical term
/// level: `Term.type_ n` was deleted in favour of it, so there is no
/// longer anything to reconcile. `sort_level_of` below is how a
/// shape-inspecting site asks "is this a sort, and at what level".
///
/// Declared last, which no longer means anything. It was put here because
/// "adding a variant leaves every existing constructor tag where it is" --
/// an argument that was already wrong (a tag is assigned per compile from
/// declaration order, `build_constructor_tag_map` in `codegen/ctors.mo`,
/// and every consumer looks one up by NAME), and that this deletion
/// disproves: no numeric tag is read, assigned, compared or serialized
/// anywhere. A FIELD would still be wrong -- see `ctx` above for the
/// arity breakage that causes.
sort (level : SortLevel),
/// A cubical primitive application -- see `CubicalPrim`/`Cubical` above.
/// One variant rather than one per primitive, for the reason recorded
/// there: `similar_term_go` is a hand-expanded cross product over this
/// type's variants and nothing checks it for exhaustiveness.
cubical (c : Cubical),
/// The one eliminator -- see `Elim` above. R3c: `if`/`match` elaborate
/// into this; the backends lower it via `lang/src/elim_lower.mo`.
elim (e : Elim),
}pub def term_peel (t : Term) : TermStrip location wrappers, exposing the term a shape test wants.
Call this at the ENTRY of anything that matches on a term's shape --
flatten_call_spine, class_method_ref, collect_db_params,
term_has_struct_lit -- rather than adding a ctx arm to each. A
shape probe that forgets does not fail loudly; it silently stops
matching, and the call it was meant to resolve quietly does not.
pub def term_loc (t : Term) : Option LocationThe OUTERMOST recorded position of a term, if it carries one: the
wrapper chain is only ever entered from outside, so the first ctx
met is returned and any inner one is dropped. (This said "innermost"
until 2026-09-29, which was simply wrong.)
pub type TypeError {
mismatch (expected : Term) (actual : Term),
unknown_var (name : NameRef),
unknown_type (name : NameRef),
unknown_constructor (name : NameRef),
not_a_function (term : Term),
not_a_type (term : Term),
infinite_type (term : Term),
custom (msg : String),
/// A binder used more than once where a borrow or a `Copy`
/// instance would make it legal — at most ONE of those uses takes
/// ownership, so the value is never actually moved twice.
/// Milestone 2 of the affine-by-default experiment.
///
/// Produced as a WARNING today: nothing rejects a program for it.
/// Warn-versus-error is the driver's decision, not this type's,
/// which is exactly why these live on `TypeError` rather than in a
/// separate warning type — promotion becomes a caller-side switch
/// instead of new plumbing.
copy_required (name : Identifier) (typ : Term) (uses : I64),
/// A binder whose value is genuinely moved twice — two or more
/// OWNING uses (stored into a constructor, or produced as a
/// scope's value). No borrow discipline rescues this one; it needs
/// `Copy`, `Clone`, or a rewrite.
value_used_after_move (name : Identifier) (typ : Term) (owning : I64),
/// A `!x` binder that is never used. The one case affine's
/// weakening does not excuse: linear means exactly once, so
/// dropping it is as wrong as using it twice.
linear_unused (name : Identifier) (typ : Term),
/// A borrowed view of a `Shared` payload used where an OWNER is
/// required: stored into a constructor/struct, returned from the def,
/// or passed to an owning parameter. A view aliases the payload its
/// `Shared` handle points at; handing it out as an owner would give
/// two owners to one value. Read it, pass the `Shared` handle on, or
/// make an explicit copy with `Clone.clone`.
borrowed_value_escapes (name : Identifier) (typ : Term),
/// A call to a def declaring `[C A]` where every constraint variable
/// is solved to a concrete type, and no instance of `C` matches it.
/// Without this the dictionary is silently defaulted (and a
/// dict-generating constraint leaves the call a parameter short).
missing_instance (cls : NamePath) (typ : Term),
/// A `Copy` (or `Clone`) instance declared for a `#[linear]` or
/// `#[proof]` type. Linear and proof values must never be duplicated;
/// `is_copy` also refuses to grant ω to their carriers, so this is the
/// declaration-site diagnostic.
proof_copied (typ : Term),
/// A proof-typed binder annotated `?` or `%`. A proof is forced
/// linear (`view-types` rule 1) and has no run-time representation, so
/// neither relaxation is legal.
proof_erased_binder (name : Identifier) (typ : Term),
/// A proof-typed value used where a run-time value is required: a
/// user def binding or returning one, or storing one. v1 proofs are
/// phantom (no constructors, no values); real erasure is deferred.
proof_at_runtime_position (name : Identifier) (typ : Term),
/// A linear or proof value captured by a closure. The closure body
/// counts the capture once but may run many times (and, with eager
/// fibers, on another thread), which would duplicate the value.
view_captured (name : Identifier) (typ : Term),
/// A linear or proof value passed to `Shared.of` (or another
/// re-readable container). `Shared` is `Copy`, so it could hand out
/// two handles to one allocation.
view_stored_in_container (name : Identifier) (typ : Term),
/// A signature or field whose type is `Shared`/`Ref`/`Array` applied
/// to a linear or proof type. Those containers are re-readable, so
/// the value could be extracted more than once.
view_in_container (typ : Term),
/// A `#[linear]`-typed binder annotated `%` (erased). A linear value
/// has a run-time representation, so it cannot be erased.
linear_erased_binder (name : Identifier) (typ : Term),
/// An instance method whose written signature is not the class's
/// declared one at this instance (ISSUE-14). `expected` is the class
/// signature with the instance's arguments substituted.
instance_method_signature (cls : NamePath) (method : Identifier) (expected : Term) (found : Term),
/// An instance defines a method its class does not declare.
instance_method_not_in_class (cls : NamePath) (method : Identifier),
}Canonical TypeError uses de Bruijn Term. TypeErrorV0 is the legacy V0 variant.
pub def dict_hint_marker_prefix : Stringf #Named.Instance args's lowered marker argument: a sentinel Term.var
named __hint_<instance name> (lowered at ParseTermKind.dict_hint's
arm, lang/parser/lower_parse.mo). The prefix is shared knowledge between
that lowering arm, dict_hint_name's recognizer (lang/scope.mo), and
the two consumers that strip the markers back off -- the checker's app
path and the dict-resolution pass -- so it lives here rather than being
spelled twice. Never a name anything else can produce: identifiers may
not contain _-prefixed words the parser hands out, and no user binder
can shadow a sentinel (global) index.
pub struct TypeConstraint {
cls : NamePath,
vars : List Identifier,
}pub struct Def {
name : NamePath,
typ : Term,
term : Term,
constraints : List TypeConstraint,
attrs : List Attribute,
vis : Visibility,
params : List Param
}Canonical Def uses de Bruijn Term. DefV0 is the legacy V0 variant.
pub def Def.name (d : Def) : NamePathpub struct InductConstructor {
name : NamePath,
params : List Param,
typ : Term,
}pub struct Inductive {
name : NamePath,
params : List Param,
typ : Term,
constructors : List InductConstructor,
attrs : List Attribute,
vis : Visibility,
}pub struct ClassDef {
name : Identifier,
typ : Term,
default : Option Term,
}pub struct Class {
name : Identifier,
params : List Param,
constraints : List TypeConstraint,
methods : List ClassDef,
vis : Visibility,
/// The class's declared RESULT SORT — the `: Sort (max 1 u)` / `: Prop`
/// clause after the params, or `None` when the head omits it (default
/// `Sort 1`). Kept because the class is checked as a type former; the
/// host represents the same clause in its `Inductive.typ`'s codomain.
sort : Option Term,
/// Variables each instance fixes, written `{S : Type}` in the class
/// head (`class MonadState {S : Type} (M : Type -> Type)`). The methods
/// mention `S` free, but an instance chooses it once, so it is not an
/// argument and not quantified per method.
determined : List Param,
}pub struct StructField {
/// `mult` mirrors the Rust reference's `StructField.mult`
/// (rust/core/src/term.rs): `!name : T` (Linear, must be consumed exactly
/// once), `?name : T` (Affine, at most once), `%name : T` (Zero /
/// Erased), or no prefix at all (Many, the default — the common
/// case). See examples/structs.mo's `Buffer.data` for a live `!` use.
name : Identifier,
typ : Term,
default : Option Term,
mult : Multiplicity,
}pub struct Struct {
/// `attrs` mirrors `Inductive`'s own slot: the `#[...]` attributes
/// written above the declaration, preserved through lowering so the
/// macro-expansion pass can still see a `#[derive ...]`
/// request at the point where decl-gen macros are
/// resolved (`lang/typecheck/macro_queue.mo`) — the attribute itself
/// is not a term or a type, so nothing else could carry it.
name : Identifier,
fields : List StructField,
attrs : List Attribute,
vis : Visibility,
}pub type UseItem {
use_name (name : Identifier),
use_rename (name : Identifier) (alias : Identifier),
use_glob,
use_sub (name : Identifier) (items : List UseItem),
use_sub_rename (name : Identifier) (alias : Identifier) (items : List UseItem),
}A single item inside a use Module { ... } brace filter. Mirrors the
Rust host's UseItem (rust/core/src/term.rs).
pub type UseFilter {
use_bare,
use_items (items : List UseItem),
}What names a use declaration imports. Bare use Module (no braces)
is deprecated but still parses. Mirrors Rust's UseFilter.
pub type Decl {
def_d (Def),
inductive_d (Inductive),
struct_d (Struct),
class_d (Class),
instance_d (Instance),
infix_d (op : Operator) (path : NamePath) (vis : Visibility),
use_d (path : ModulePath) (filter : UseFilter) (public : Bool),
open_d (path : NamePath) (filter : OpenFilter),
/// `open ModulePath [{filter}] in <decl>` — the module is opened only
/// for the scope of the wrapped declaration (def/type/struct/class/
/// instance). Mirrors Rust's `Decl::ScopedOpen`.
scoped_open_d (path : NamePath) (filter : OpenFilter) (decl : Decl),
/// `defmacro name params := <term>` — mirrors the Rust reference's
/// `Decl::DefMacro(Def)` (rust/core/src/term.rs): literally reuses `Def`
/// (`typ` forced to `Term.hole`, `term` wrapped in one lambda per
/// param when `params` is non-empty via the existing `lam_params`
/// helper, lang/parser.mo — no new lambda-building logic needed).
/// Parsing/representation only — nothing expands or invokes this
/// yet (see plans/bootstrapping/self-hosted-compiler.md).
def_macro_d (Def),
/// `defmacro name params := decls { ... }` — the sibling
/// declaration-generating form. Mirrors the Rust reference's
/// `Decl::DeclGen(DeclGenDef)`, but with `DeclGenDef`'s fields
/// inlined directly here (matching this type's own `infix_d`/
/// `scoped_open_d` convention of inline fields over a separate
/// wrapper struct) rather than introduced as its own named type.
/// `decl_list` is the literal, unexpanded list of declarations parsed
/// out of the `decls { ... }` body.
decl_gen_d (name : NamePath) (params : List Param) (decl_list : List Decl) (attrs : List Attribute),
/// Declaration-position `name! arg1 arg2 ...` (e.g. `derive_beq!
/// Point`, `reflect_type_info! T some_meta`). `name` is a bare
/// `Identifier`, NOT a `ModulePath` — differs from `defmacro`'s own
/// name shape, mirroring the Rust reference's `Decl::MacroCall`
/// exactly (rust/core/src/term.rs). `args` are whitespace-separated
/// terms, not a comma/paren-delimited call.
macro_call_d (name : Identifier) (args : List Term),
/// `#![mote { name := "x", deps := [init, std] }]` — a file-level
/// INNER attribute declaring this file's mote inline, so a module
/// with no `mote.toml` above it is a mote rather than "script mode"
/// (`Mote.discover`'s own `Option.none`). This is what takes
/// `examples/` out of the untracked state the plan's item G records,
/// and what makes `validate_module_deps` apply to it.
///
/// Valid ONLY as the first declaration of a file, and the diagnostic
/// for a misplaced one comes from `validate_mote_attr_position`
/// (lang/module.mo) rather than from the parser — see that def's
/// comment for why the parser is the wrong place to reject it.
///
/// Appended LAST for the same reason as `ParseDeclKind.mote_d`.
mote_d (attr : Attribute),
}pub struct Instance {
/// `implicit_params` holds any `{Name : Type}` binders written right
/// after `instance` (before the optional `[constraints]` and the class
/// name), e.g. `instance {A : Type} Show A { ... }`. Mirrors the Rust
/// reference's `Instance.params` (rust/core/src/term.rs) — load-bearing for
/// instance resolution there (substitution-based matching against a
/// lookup key's args), not just documentation. Empty for the common
/// case of a fully-concrete instance like `instance Show Bool { ... }`.
///
/// `defs` holds the instance's own concrete method `Def`s (`def m :=
/// ...` entries inside the `instance ... { }` body) — mirrors the
/// Rust reference's `Instance.impls_map: Map<Identifier, Def>`
/// (rust/core/src/term.rs), and mirrors this very module's own `Class`
/// type, which already retains its method defs the same way
/// (`Class.mk`'s `methods` field). Until this field existed,
/// `instance_parser`/`instance_close` (lang/parser.mo) fully parsed
/// an instance's own methods and then discarded them outright —
/// `resolve_class_method`/`derive_instance_key`
/// (lang/typecheck/infer.mo) could find a matching `Instance` but
/// never its concrete implementation, always falling back to the
/// class method's own abstract signature. See
/// plans/bootstrapping/self-hosted-compiler.md's dictionary-passing
/// plan (Phase 1) for the full context.
name : Identifier,
cls : NamePath,
constraints : List TypeConstraint,
args : List Term,
vis : Visibility,
implicit_params : List Param,
defs : List Def,
}pub class Similar A {
def similar (a : A) (b : A) : Bool
}pub instance Similar Identifier {
def similar (a : Identifier) (b : Identifier) : Bool :=
match a {
id s1 => match b {
id s2 => String.beq s1 s2
}
}
}pub instance Similar Operator {
def similar (a : Operator) (b : Operator) : Bool :=
match a {
Operator.mk s1 => match b {
Operator.mk s2 => String.beq s1 s2
}
}
}pub instance Similar ModulePath {
def similar (a : ModulePath) (b : ModulePath) : Bool :=
match a {
ModulePath.mk ids1 => match b {
ModulePath.mk ids2 => id_list_similar ids1 ids2,
_ => false
},
_ => false
}
}pub instance Similar NamePath {
def similar (a : NamePath) (b : NamePath) : Bool :=
name_path_similar a b
}Similar ModulePath's twin, for the positions the qualified-names
split moved to the def-name role (Infix.name, ScopeDef.name,
Inductive.name ...). Delegates to name_path_similar below so the
segment-wise rule has one home.
pub instance Similar QualifiedName {
def similar (a : QualifiedName) (b : QualifiedName) : Bool :=
Similar.similar a.qmod b.qmod && name_path_similar a.qname b.qname
}Structural comparison of the two halves; the module half already has
a Similar instance and the name half delegates to the segment-wise
rule above.
pub instance Similar NameRef {
def similar (a : NameRef) (b : NameRef) : Bool :=
match a {
NameRef.nid id1 => match b {
NameRef.nid id2 => Similar.similar id1 id2,
NameRef.nnp _ => false,
NameRef.nqn _ => false,
NameRef.nop _ => false
},
NameRef.nnp np1 => match b {
NameRef.nnp np2 => name_path_similar np1 np2,
NameRef.nid _ => false,
NameRef.nqn _ => false,
NameRef.nop _ => false
},
NameRef.nqn qn1 => match b {
NameRef.nqn qn2 =>
Similar.similar qn1.qmod qn2.qmod
&& name_path_similar qn1.qname qn2.qname,
NameRef.nid _ => false,
NameRef.nnp _ => false,
NameRef.nop _ => false
},
NameRef.nop op1 => match b {
NameRef.nop op2 => Similar.similar op1 op2,
NameRef.nid _ => false,
NameRef.nnp _ => false,
NameRef.nqn _ => false
}
}
}pub def name_path_similar (a : NamePath) (b : NamePath) : BoolSegment-wise Similar over a NamePath — the NameRef.nnp/nqn
arms above delegate here rather than keying ScopeData's maps on the
rendered string (the string comparison BOrd ModulePath relies on
would conflate nothing here, but segment-wise keeps Similar
structural like id_list_similar).
pub instance Similar NumSuffix {
def similar (a : NumSuffix) (b : NumSuffix) : Bool :=
match a {
i8 => match b {
i8 => true, i16 => false, i32 => false, i64 => false,
u8 => false, u16 => false, u32 => false, u64 => false,
f32 => false, f64 => false
},
i16 => match b {
i8 => false, i16 => true, i32 => false, i64 => false,
u8 => false, u16 => false, u32 => false, u64 => false,
f32 => false, f64 => false
},
i32 => match b {
i8 => false, i16 => false, i32 => true, i64 => false,
u8 => false, u16 => false, u32 => false, u64 => false,
f32 => false, f64 => false
},
i64 => match b {
i8 => false, i16 => false, i32 => false, i64 => true,
u8 => false, u16 => false, u32 => false, u64 => false,
f32 => false, f64 => false
},
u8 => match b {
i8 => false, i16 => false, i32 => false, i64 => false,
u8 => true, u16 => false, u32 => false, u64 => false,
f32 => false, f64 => false
},
u16 => match b {
i8 => false, i16 => false, i32 => false, i64 => false,
u8 => false, u16 => true, u32 => false, u64 => false,
f32 => false, f64 => false
},
u32 => match b {
i8 => false, i16 => false, i32 => false, i64 => false,
u8 => false, u16 => false, u32 => true, u64 => false,
f32 => false, f64 => false
},
u64 => match b {
i8 => false, i16 => false, i32 => false, i64 => false,
u8 => false, u16 => false, u32 => false, u64 => true,
f32 => false, f64 => false
},
f32 => match b {
i8 => false, i16 => false, i32 => false, i64 => false,
u8 => false, u16 => false, u32 => false, u64 => false,
f32 => true, f64 => false
},
f64 => match b {
i8 => false, i16 => false, i32 => false, i64 => false,
u8 => false, u16 => false, u32 => false, u64 => false,
f32 => false, f64 => true
}
}
}pub instance Similar Con {
def similar (a : Con) (b : Con) : Bool :=
match a {
mk name1 typ1 nargs1 args1 => match b {
mk name2 typ2 nargs2 args2 =>
Similar.similar name1 name2 && Similar.similar typ1 typ2 && I64.beq nargs1 nargs2 && opt_db_term_list_similar args1 args2
}
}
}pub instance Similar Native {
def similar (a : Native) (b : Native) : Bool :=
match a {
mk name1 nargs1 args1 => match b {
mk name2 nargs2 args2 =>
Similar.similar name1 name2 && I64.beq nargs1 nargs2 && opt_db_term_list_similar args1 args2
}
}
}pub instance Similar MatchCase {
def similar (a : MatchCase) (b : MatchCase) : Bool :=
match a {
MatchCase.mk name1 args1 body1 _ _ => match b {
MatchCase.mk name2 args2 body2 _ _ =>
Similar.similar name1 name2 && id_list_similar args1 args2 && Similar.similar body1 body2
}
}
}pub instance Similar Multiplicity {
def similar (a : Multiplicity) (b : Multiplicity) : Bool :=
match a {
zero => match b { zero => true, many => false, linear => false, affine => false },
many => match b { zero => false, many => true, linear => false, affine => false },
linear => match b { zero => false, many => false, linear => true, affine => false },
affine => match b { zero => false, many => false, linear => false, affine => true }
}
}pub instance Similar Param {
def similar (a : Param) (b : Param) : Bool :=
match a {
mk name1 typ1 mult1 def1 _attrs1 => match b {
mk name2 typ2 mult2 def2 _attrs2 =>
Similar.similar name1 name2 && Similar.similar typ1 typ2
&& Similar.similar mult1 mult2 && opt_db_term_similar def1 def2
}
}
}pub instance Similar Location {
def similar (a : Location) (b : Location) : Bool :=
match a {
mk off1 line1 col1 => match b {
mk off2 line2 col2 =>
I64.beq off1 off2 && I64.beq line1 line2 && I64.beq col1 col2
}
}
}pub instance Similar SourceRange {
def similar (a : SourceRange) (b : SourceRange) : Bool :=
match a {
mk start1 end1 path1 => match b {
mk start2 end2 path2 =>
Similar.similar start1 start2 && Similar.similar end1 end2 && opt_path_similar path1 path2
}
}
}pub instance Similar Literal {
def similar (a : Literal) (b : Literal) : Bool :=
match a {
str s1 => match b {
str s2 => String.beq s1 s2,
num _ _ => false, if_ _ _ _ => false, match_ _ _ => false,
char _ => false, flt _ _ => false,
struct_lit _ _ => false, struct_update _ _ => false
},
num v1 s1 => match b {
num v2 s2 => I64.beq v1 v2 && Similar.similar s1 s2,
str _ => false, if_ _ _ _ => false, match_ _ _ => false,
char _ => false, flt _ _ => false,
struct_lit _ _ => false, struct_update _ _ => false
},
if_ o1 t1 th1 => match b {
if_ o2 t2 th2 => Similar.similar o1 o2 && Similar.similar t1 t2 && Similar.similar th1 th2,
str _ => false, num _ _ => false, match_ _ _ => false,
char _ => false, flt _ _ => false,
struct_lit _ _ => false, struct_update _ _ => false
},
match_ v1 cs1 => match b {
match_ v2 cs2 => Similar.similar v1 v2 && mc_list_similar cs1 cs2,
str _ => false, num _ _ => false, if_ _ _ _ => false,
char _ => false, flt _ _ => false,
struct_lit _ _ => false, struct_update _ _ => false
},
// `char`/`flt` are ordinary literals, present in every normal
// parsed program -- this instance predates both being added to
// `Literal`. `struct_lit`/`struct_update` are the same survivor
// state `similar_term_go`'s neighbours document: a literal that
// never desugared because best-effort elaboration failed on its
// def, which this comparator (used by structural test pinning)
// must still be able to compare rather than crash on.
char c1 => match b {
char c2 => String.beq (char_to_string c1) (char_to_string c2),
str _ => false, num _ _ => false, if_ _ _ _ => false, match_ _ _ => false,
flt _ _ => false, struct_lit _ _ => false, struct_update _ _ => false
},
flt t1 s1 => match b {
flt t2 s2 => String.beq t1 t2 && Similar.similar s1 s2,
str _ => false, num _ _ => false, if_ _ _ _ => false, match_ _ _ => false,
char _ => false, struct_lit _ _ => false, struct_update _ _ => false
},
struct_lit fields1 tn1 => match b {
struct_lit fields2 tn2 => struct_lit_fields_similar fields1 fields2 && opt_term_similar tn1 tn2,
str _ => false, num _ _ => false, if_ _ _ _ => false, match_ _ _ => false,
char _ => false, flt _ _ => false, struct_update _ _ => false
},
struct_update base1 fields1 => match b {
struct_update base2 fields2 => Similar.similar base1 base2 && struct_lit_fields_similar fields1 fields2,
str _ => false, num _ _ => false, if_ _ _ _ => false, match_ _ _ => false,
char _ => false, flt _ _ => false, struct_lit _ _ => false
}
}
}pub instance Similar BinderInfo {
/// Dense tag comparison, not a cross product -- the `cubical_prim_eq`
/// pattern, and for the same reason.
def similar (a : BinderInfo) (b : BinderInfo) : Bool := binder_info_eq a b
}pub instance Similar Binder {
def similar (a : Binder) (b : Binder) : Bool :=
binder_info_eq (binder_info_of a) (binder_info_of b)
}The NAME is deliberately not compared. Binder's own doc comment says the
name is error-message metadata and NEVER identity; two binders differing
only in what an error message would call them are the same binder. info
is the half the checker discriminates on, so it is the half this compares.
That distinction became load-bearing with R2b. Before the fold every
pi's binder was binder_anon, so ignoring it was free. After, a level
binder at level 0 and an explicit (x : Prop) binder have the SAME domain
(Term.sort (SortLevel.concrete 0)) and can have the same codomain — so a
similar_term_go that ignored info would call forall u. C and
(x : Prop) -> C convertible, and pi_arity counts one of those as a value
parameter and not the other.
pub instance Similar DebugName {
def similar (a : DebugName) (b : DebugName) : Bool :=
match a {
named id1 => match b {
named id2 => Similar.similar id1 id2,
unnamed => false
},
unnamed => match b {
unnamed => true,
named _ => false
}
}
}pub def level_const (l : SortLevel) : Option I64The concrete value of a level, when it has one.
succ/max of concrete levels ARE evaluated -- succ (concrete 1) is
2. That is load-bearing rather than tidy: type_check_sort_full infers
the type of a sort at level l as the sort at succ l, so a Pi's
universe or a cumulativity check routinely meets a succ that has to
count as a number.
A level variable answers Option.none, and so does any succ/max
containing one. An unresolved level is deliberately NOT given a number --
the comparisons below all refuse it, which is the sound direction (an
unresolved level costs completeness, never soundness), and W1.5's
normalizing comparison is what resolves these structurally.
pub def sort_level_of (t : Term) : Option SortLevelThe sort level of a term, if that term is a sort.
pub for the checker's own declaration-kind rules (module.mo's class and
inductive kind validation), which ask "is this term a sort" the same way
unify_sort already does.
pub def sort_n (n : I64) : TermA sort at a concrete level, in the one remaining spelling.
A FIXTURE SHORTHAND, not a layer. Every hand-written sort in the test
suite used to say Term.type_ n; this is what that becomes, so ~640 sites
do not each spell out Term.sort (SortLevel.concrete n). Production code
writes the constructor directly.
It is also what keeps SortLevel out of sixteen test files: a call site
writes sort_n 3 and never names the level type at all. Nothing about the
level rules depends on the difference -- level_const/sort_level_of fold
a concrete built either way to the same answer.
Deliberately NOT pub: proofs/ writes the explicit constructor instead,
so a test convenience never becomes part of lang's public surface.
pub def cub (prim : CubicalPrim) (args : List Term) : TermBuild a cubical term. Binds an annotated local before wrapping because a BARE struct literal in argument position miscompiles through the self-hosted backend (AGENTS.md); this is the established shape for it.
pub def cub_interval : TermThe interval type I.
pub def cub_i0 : Termi0 : I.
pub def cub_i1 : Termi1 : I.
pub def cub_ineg (i : Term) : Termineg i -- interval negation.
pub def cub_imeet (i : Term) (j : Term) : Termimeet i j -- the De Morgan meet.
pub def cub_ijoin (i : Term) (j : Term) : Termijoin i j -- the De Morgan join.
pub def cub_pathp (a_line : Term) (a_left : Term) (a_right : Term) : TermPathP A a b -- a path over the line A from a to b. The line is
checked to be I -> Sort l and the endpoints to live at A i0/A i1
by type_check_pathp (lang/src/typecheck/infer.mo).
pub def cub_transp (a_line : Term) (a_elem : Term) : Termtransp A a -- the element a : A i0 transported to A i1. The
line is checked to be I -> Sort l and the element to live at
A i0 by type_check_transp (lang/src/typecheck/infer.mo); the
constant-family reduction to the element itself lives in
whnf_transp (lang/src/typecheck/whnf.mo).
pub def cub_face_eq0 (i : Term) : Termface_eq0 i -- the cofibration i = 0. Reduces to i1 exactly at
i0 and to i0 at i1 (whnf_face,
lang/src/typecheck/whnf.mo); face_eq0 (ineg i) is face_eq1 i.
pub def cub_face_eq1 (i : Term) : Termface_eq1 i -- the cofibration i = 1. Reduces to i1 exactly at
i1 and to i0 at i0; face_eq1 (ineg i) is face_eq0 i.
pub def cub_is_one (i : Term) : Termis_one φ -- the proposition that the cofibration φ is i1. A
former of types (result Sort 1); its proofs are what a partial
element (is_one φ -> A) consumes, and hcomp below is the one
consumer of a whole system. is_one itself stays rigid -- nothing
in the checker fabricates a proof of is_one φ for a VARIABLE φ.
The one proof it does have is cub_it_is_one, and it is a proof of
is_one i1 alone, which is what lets hcomp's satisfied-face case
reduce at the literal i1 and nowhere else (see
CubicalPrim.hcomp).
pub def cub_it_is_one : TermThe canonical inhabitant of is_one i1 (Stage 6b,
plans/type-system/univalence.md) -- Agda's itIsOne. The only proof
term of an is_one type the checker has, and the reason
whnf_hcomp can compute hcomp A i1 u u0 to u i1 it_is_one.
pub def cub_hcomp (a_typ : Term) (a_face : Term) (a_sys : Term) (a_base : Term) : Termhcomp A φ u u0 -- Kan composition. whnf_hcomp
(lang/src/typecheck/whnf.mo) answers u0 when face_decide REFUTES
the cofibration and u i1 it_is_one when it is the LITERAL i1; any
other cofibration stays stuck. See CubicalPrim.hcomp for why the two
decided cases answer differently.
pub def cub_glue (a_typ : Term) (a_face : Term) (a_partial : Term) (a_equiv : Term) : TermGlue A φ T w -- the Glue type former (Stage 6b-ii,
plans/type-system/univalence.md). whnf_glue answers T it_is_one at
the LITERAL i1 and stays stuck everywhere else.
pub def cub_glue_intro (a_typ : Term) (a_face : Term) (a_partial : Term)
(a_equiv : Term) (a_sys : Term) (a_base : Term) : Termglue A φ T w t a -- the Glue introduction, carrying the formation's
arguments so the reduction can see φ. whnf_glue_intro answers
t it_is_one at the literal i1.
pub def cub_glue_elim (a_glued : Term) : Termunglue g -- projection out of a Glue type. whnf_glue_elim fires
iota on a glue introduction for every φ.
pub def cub_system (a_face1 : Term) (a_val1 : Term) (a_face2 : Term) (a_val2 : Term) : Termsystem φ1 u1 φ2 u2 -- a two-clause partial element. Its type is
is_one (ijoin φ1 φ2) -> A, and whnf's application rule selects the
clause whose face is true when the face decides.
pub def cubical_arity (prim : CubicalPrim) : I64How many arguments a primitive takes. args is positional and this is
the only statement of its expected length; type_check_cubical is what
rejects a mismatch, exactly as type_check_con does for Con.num_args.
Keeping it as a total function over CubicalPrim rather than a field on
Cubical means a new primitive cannot be added without answering it.
pub def cubical_is_endpoint (prim : CubicalPrim) : BoolIs this primitive one of the two interval ENDPOINTS? The reducer and the path-application rule both ask, and asking through one predicate keeps the two from drifting.
pub def cubical_prim_tag (prim : CubicalPrim) : I64A dense tag per primitive. Total over CubicalPrim, so a primitive added
later cannot be left without one.
Equality goes through this rather than through a hand-expanded 6x6 cross
product of constructor pairs. The cross product is what similar_term_go
below does for Term, where it is forced -- those variants carry payloads
that have to be compared arm by arm. CubicalPrim carries none, so the
only thing a cross product would add here is 36 places to omit a pair,
and an omitted pair answers "different" for two equal primitives. One
comparison over six literals is checkable by reading it.
pub def cubical_prim_eq (a : CubicalPrim) (b : CubicalPrim) : Boolpub def cubical_prim_name (prim : CubicalPrim) : StringThe primitive's surface name. One table, shared by the printer
(lang/pretty.mo) and the checker's diagnostics, so the two cannot drift.
pub def cubical_prims_all : List CubicalPrimEvery primitive, in cubical_prim_tag order. Exists as one list so the
decoder below can be derived from cubical_marker_key by scanning,
not keyed by a second copy of the same strings.
pub def cubical_marker_key (prim : CubicalPrim) : StringThe string a #[cubical "..."] MARKER names a primitive by -- the
marker key, which is NOT the surface name cubical_prim_name returns:
the interval's surface name is I (what a user writes, what the
printer shows) but its marker is interval, because the marker names
the PRIMITIVE, and the def the marker sits on already carries its own
name on the same line. Distinct tables by exactly that one entry;
total over CubicalPrim so a primitive added later cannot be left
without a marker key silently.
pub def cubical_prim_of_name (s : String) : Option CubicalPrimDecode a #[cubical "..."] marker's string back to the primitive it
names -- the inverse of cubical_marker_key, derived from that same
table by scanning cubical_prims_all, so a primitive added with a
marker key cannot leave the decoder behind (an if-chain keyed by its
own copy of the strings could). Option, not a panic: the marker is
authored in user source, so an unknown string must answer "binds
nothing" and the def then stays an ordinary def -- the same answer as
no marker at all.
pub def cubical_prim_of (t : Term) : Option CubicalPrimRead a cubical term's primitive, past any location wrapper.
pub instance Similar Term {
/// Peels BOTH sides before comparing, so a location wrapper never
/// makes two otherwise-identical terms compare unequal. Without this,
/// `--debug` would change what the type checker decides, not just what
/// it annotates -- and `term_matches_carrier` (`lang/scope.mo`) reaches
/// here on instance-carrier matching, so the effect would be a
/// silently unresolved instance.
///
/// A pre-existing gap it does NOT fix: the inner matches below omit
/// `quote_` and `var_macro`, so comparing either is a
/// non-exhaustive-match crash waiting on a caller that constructs one.
/// `term_peel` does not strip those two, so routing through one entry
/// point that peels only keeps that gap at one place instead of eleven.
///
/// `Term.sort` had to be added to EVERY inner match below, not just to a
/// new outer arm: a sort compared against a non-sort lands in the other
/// arm's inner match, and an unlisted variant there is a runtime
/// non-exhaustive-match crash, not a type error. Two sorts are similar
/// when their levels are -- `level_eq`, which folds a concrete level back
/// to the `I64.beq` this comparison always was.
def similar (a : Term) (b : Term) : Bool :=
similar_term_go (term_peel a) (term_peel b)
}pub struct Infix {
operator : Operator,
name : NamePath,
}pub struct InstanceKey {
cls : NamePath,
constraints : List TypeConstraint,
args : List Param,
}pub struct ScopeDef {
name : NamePath,
module : ModulePath,
sig : Term,
body : Term,
vis : Visibility,
}pub struct ScopeClassDef {
class_name : NamePath,
full_name : NamePath,
name : Identifier,
sig : Term,
}pub struct OwnedInstance {
owner : ModulePath,
ins : Instance,
}An instance together with the module that declared it. The registry groups instances by class, and ONE group collects instances from every module that declares one, so the owner has to travel per instance -- it is what the visibility rule compares against the consumer's mote.
pub struct ScopeInstance {
class_name : NamePath,
instances : List OwnedInstance,
}pub struct ScopeConflict {
name : NamePath,
candidates : List NamePath,
}pub struct LocalVar {
name : Identifier,
typ : Term,
multiplicity : Multiplicity,
}pub type ClassIndex {
class_index (HashMap String (List Class))
}Classes by the BARE spelling of their rendered name -- the text after
the last ::, what unqualify_def_name keeps. Every match
class_name_eq accepts has equal bare spellings on both sides, so a
lookup only has to compare the classes in one bucket. Each bucket keeps
the order of the List Class it mirrors, so the first match is the one
a scan of the whole list would find.
pub def class_index_empty : ClassIndexpub def class_index_bucket (bare : String) (idx : ClassIndex) : List Classpub def class_index_add (cls : Class) (idx : ClassIndex) : ClassIndexPrepend cls to its bucket: the mirror of List.cons cls classes.
pub def class_index_of (classes : List Class) : ClassIndexThe index of classes, built back to front so every bucket keeps the
list's order.
pub struct ScopeData {
def_refs : NameMap ScopeDef,
class_defs : List ScopeClassDef,
instances : List ScopeInstance,
// `HashMap`, not `List` -- mirrors `def_refs` (see bench/scope_lookup.mo):
// every consumer looks this up by name (`scope_find_inductive`), never
// iterates it, so a linear scan over every inductive in the merged
// scope (~218+ corpus-wide) on every match-case/struct-literal check
// was pure waste. `classes`, the sibling field just below, stays a
// `List` (by-name lookup is now `scope_find_class`, lower corpus
// cardinality than inductives, no measured need for a HashMap yet).
inductives : NameMap Inductive,
// Full `Class` values (params/constraints/ordered methods), not a
// synthetic zero-method `Inductive` stand-in -- `build_scope_class`
// used to throw the real `Class` away and register a `dummy_ind`
// instead, which is why `resolve_class_method`'s own class lookup
// (`lang/typecheck/infer.mo`) could never actually resolve a class's
// own declared params/methods. `scope_find_class`/`scope_data_classes`
// (below) are the real by-name reader this field never had before.
classes : List Class,
/// `classes` by bare spelling (`ClassIndex`); kept in step with it at
/// every site that changes `classes`.
class_index : ClassIndex := class_index_empty,
infixes : List Infix,
conflicts : List ScopeConflict,
// `name_map_empty` (an ordinary def over `HashMap.map
// HashMap.empty_buckets`), not `Map.empty`: the latter is a CLASS
// method (`instance [Hashable K, BOrd K] Map HashMap`, `std/map.mo`)
// needing type-directed dispatch that a struct field's
// default-value expression doesn't get the same way an ordinary call
// site does (confirmed: `Map.empty` here fails at evaluation with
// "unresolved global: Map.empty").
def_params : NameMap (List Param) := name_map_empty,
// A def's own DECLARED return type (the final non-`Pi`/`Forall` type
// at the end of its signature's own Pi-chain, `Def.typ` -- NOT its
// body's inferred type, and NOT `ScopeDef.sig`, which stays
// unconditionally `Term.hole` by its own load-bearing design, see
// `build_scope_def`'s doc comment). Lets `find_inductive_for_cases`
// (`lang/typecheck/infer.mo`) resolve a match's scrutinee type when
// it's a bare call to a known def (`match fresh_temp c { ... }`) --
// pure INFER-mode type-checking a call otherwise can't recover a
// return type at all (`ScopeDef.sig` is hole), so it fell through to
// an ambiguous constructor-NAME-only scan across every inductive in
// scope; every `struct`'s auto-generated constructor is named `mk`
// (`build_scope_struct`), so that scan is ambiguous between ANY two
// structs the moment either is matched directly on a call result --
// confirmed to silently return the WRONG field's value, not just
// fail loudly. Mirrors `def_params`'s own precedent exactly (added
// for the analogous "recover param types without touching the
// load-bearing `sig`/`body` hole sentinel" need).
def_return_types : NameMap Term := name_map_empty,
// A def's own FULL declared signature (`Def.typ` itself, e.g.
// `forall V. Pi (xs : List V) (Option V)` for `def get_first {V :
// Type} ...`) -- unlike `def_return_types` just above (the Pi-chain
// STRIPPED final return type) this keeps the implicit-binder and
// parameter types too, so a call site can check each argument
// against the parameter's real declared type and solve the
// signature's type variables from the arguments' actual types.
// Same side-table pattern (and same never-touch-the-load-bearing-
// `sig`-hole rule) as `def_params`/`def_return_types`; populated by
// `build_scope_def`, consumed by `type_check_app`'s signature-driven
// path (`lang/typecheck/infer.mo`).
def_sigs : NameMap Term := name_map_empty,
// A def's own BODY (`Def.term`), kept for DELTA REDUCTION --
// unfolding a global reference during conversion checking
// (`lang/typecheck/whnf.mo`). Without it there is no name -> body
// lookup reachable from inference at all: `build_scope_def` stores
// `Term.hole` in `ScopeDef.body` unconditionally, and that sentinel
// is load-bearing for dozens of call sites, so this follows the
// same side-table pattern as `def_params`/`def_return_types`/
// `def_sigs` above rather than filling the hole in.
//
// Note what is stored is the body as `build_scope_def` sees it --
// PRE-elaboration, and still `Term.lam`-chain shaped for a def with
// parameters, which is exactly what beta reduction then consumes
// one argument at a time.
def_bodies : NameMap Term := name_map_empty,
// A def marked `#[cubical "..."]` (the `with Cubical` block in
// `init/src/prelude.mo`) bound to
// the `CubicalPrim` the marker names -- the name-binding half of the
// cubical design (the checker rewrite is in `lang/typecheck/infer.mo`:
// `type_check_free_var` for bare primitives, `type_check_app`'s
// cubical probe for applications). The MARKER, not the bare spelling,
// binds, so a user's own `def I : Type` stays an ordinary def.
// Keyed by the resolved `ScopeDef.name` exactly like `def_bodies`
// above, and for the same reason: the lookup happens after
// `scope_resolve_name`, under the qualified name it returns.
cubical_prims : NameMap CubicalPrim := name_map_empty,
// A def's declared `[Class V]` constraints (`Def.constraints`) -- the
// `#Named.Instance` hint checker (`validate_dict_hints`,
// lang/scope.mo) validates each hint against the callee's class
// constraints, so the checker needs them by name. Side-table pattern
// of `def_params`/`def_sigs` above; keyed by the resolved name.
def_constraints : NameMap (List TypeConstraint) := name_map_empty,
// The subset of `def_constraints` that became dictionary PARAMETERS
// (`qualifying_dict_constraints`, computed once at registration from
// the same declaration Phase 3 read). The checker's
// ordinary-call reification reads this instead of re-walking the
// callee's body at every call site.
def_dict_constraints : NameMap (List TypeConstraint) := name_map_empty,
// Every class that carries a dictionary (has at least one method), by
// bare name (`collect_dict_classes`, lang/scope.mo) -- the class half
// of `qualifying_dict_constraints`. Seeded once per whole-graph scope
// build, from the same decl list Phase 3 reads, so the callee's arity
// and every call site agree.
dict_classes : NameSet := name_set_empty,
// Every registered name's BARE spelling (`prelude::Monad` ->
// `Monad`) -> the qualified keys that own it. The read side of
// item 5.1's bare-vs-qualified tolerance: `scope_data_find_
// inductive`'s and `resolve_free_var_def`'s miss fallbacks consult
// this map (one O(1) lookup) instead of scanning every
// inductive/def key per miss -- post-qualification a bare miss is
// the COMMON case, and the scans were a measured ~20x blowup of
// `elaborate_module_decls`. One owner key resolves the miss; an
// empty or 2+-owner list is a genuine miss/ambiguity (never a
// guess), the same policy the per-miss scans already used.
// Populated by `scope_data_note_bare` at every registration site
// (`scope_data_add_def`/`_inductive`/`_class`/`_class_def`).
bare_aliases : BareNameMap := bare_name_map_empty,
}pub struct Scope {
module_id : ModulePath,
scope : ScopeData,
parent : Option Scope,
// Read by `validate_match_coverage` (`lang/typecheck/infer.mo`), set by
// `lang/module.mo`'s def-body sites from `has_incomplete_match_exemption`;
// `false` means "checked", the safe default.
//
// Spell it at EVERY `Scope` literal -- all 69 in the tree do. Leaving it
// to the default sends the Rust host into an unbounded missing-field fill
// (`desugar_struct_literals`, `rust/core/src/core_check.rs`) that OOMs the
// whole-corpus check, so the pre-commit hook can never pass.
incomplete_match_ok : Bool := false,
}pub struct Module {
path : ModulePath,
inductives : List Inductive,
defs : List ScopeDef,
infixs : List Infix,
instances : List ScopeInstance,
}pub struct DeclGroup {
path : ModulePath,
decls : List Decl,
}pub struct ModuleRegistry {
modules : List Module,
}pub struct LocalScope {
vars : List LocalVar,
parent : Option LocalScope,
}