06 — Type System (the ty crate)
Hindley-Milner inference for Sky, rebuilt on the arena + integer-id idioms. This
is where L3 pays off most concretely: type-variable identity stops being a
pointer and becomes a TyVarId — "the one real design task" the self-host
analysis named (docs/self-host/00-feasibility-and-architecture.md:112), solved
for free by the arena. The crate owns HM inference, arena union-find,
generalisation/instantiation, records + row polymorphism, exhaustiveness, and the
per-region type table that drives type-directed lowering (07).
Depends on base (ids, interners, arena), hir (name-resolved IR), and
diagnostics. Depended on by skydb (which exposes infer as a query) and
lower. #![forbid(unsafe_code)].
What the current design gets right (and we keep)
The Haskell Sky.Type.* tree is a competent elm/compiler-derived HM engine. Four
behaviours are load-bearing soundness and we reproduce them exactly, then make
them cheaper or safer by construction:
- The wildcard-
anyper-occurrence gate —any (/= "any") freeVars(Constrain/Expression.hs:472,1122,1201;Instantiate.hs:43). Mis-gating silently accepts wrong return types (CLAUDE.md "Wildcard-anysoundness gate"). - The FFI interface-satisfaction axiom —
isFfiInterfacePair/implementsInterface(Unify.hs:108-121,349-381). This is the soundness theany-boxed self-host lacked (CLAUDE.md Limitation #6). - Strict-HM arity gate (E2007) —
declaredArity+SlotShape+maybeEmit{Arity,ValueSlot}Mismatch(Constrain/Expression.hs:1114-1208,4127). - Exhaustiveness stronger than GHC-as-configured —
Exhaustiveness.hs. A real win; kept and, per L6, applied to the compiler's own IR.
Two things the Haskell code does that violate our laws, fixed here:
rowExtCounteris a globalunsafePerformIOIORef (Unify.hs:42-50) naming fresh row-extension vars. That is L1 (global mutable) and L4 (nondeterministic across runs / interleavings). It becomes a counter on the inference context, seeded deterministically (L4).Descriptor._rank/_mark/_copy(Type.hs:42-47) are vestigial elm/compiler let-generalisation-pool machinery — unused in Sky, which generalises via annotations, not by rank (docs/self-host/00-feasibility-and-architecture.md:112-114). We drop them. Let bindings DO generalise (v0.27.0), but by an explicitftv(τ) \ ftv(Γ)computation over the union-find, not by rank pools — see Let-generalisation. The only rank we keep is the union-by-rank weight (UnionFind.hs:33,Word32inPointInfo).
Two levels of type, exactly as today
The Haskell code has two representations and we mirror the split — it is the right one:
| Level | Haskell | Rust | Mutability |
|---|---|---|---|
| Canonical / immutable | T.Type (Sky.AST.Canonical) | Ty (interned) | frozen, Copy id |
| Solver / inference | Variable = UF.Point Descriptor (Type.hs:38) | TyVarId (arena slot) | in-place union-find |
Ty is the interned HM type — what flows on constraints, what a region maps to,
what sky doc/hover render. TyVarId is the transient union-find variable used
only during one infer query. "Read back" (variableToType, Solve.hs:1428)
walks the settled arena into an interned Ty.
Ty — interned canonical type (base/ty)
Structural, hash-consed once, compared by 32-bit id (L3). Mirrors
Sky.AST.Canonical.Type.
/// Interned handle. `==` is an integer compare.
#[derive(Copy, Clone, PartialEq, Eq, Hash)]
pub struct Ty(InternId);
/// The interned payload (one per distinct structural type).
#[derive(PartialEq, Eq, Hash)]
pub enum TyData {
/// Rigid / flexible type variable *name* at the canonical level
/// (`T.TVar name`). `"any"` is the wildcard — see the gate below.
Var(Name),
/// `a -> b` (`T.TLambda`)
Fun(Ty, Ty),
/// Nominal application `Home.Name a b …` (`T.TType home name args`).
/// Home is a `ModuleId`; the empty-home sentinel (`Canonical ""`,
/// Unify.hs:341) becomes `ModuleId::EMPTY`.
App { home: ModuleId, name: Name, args: Box<[Ty]> },
/// Row-polymorphic record: sorted fields + optional extension var.
/// Fields carry `_fieldIndex` for deterministic emission (L4).
Record { fields: Box<[(Name, Ty)]>, ext: Option<Name> },
Unit,
/// 2- or 3-tuple (`T.Tuple1` is 2-or-3; keep the shape).
Tuple(Ty, Ty, Option<Ty>),
/// Transparent alias carrying its arg bindings + expansion
/// (`T.TAlias home name pairs real`).
Alias { home: ModuleId, name: Name, args: Box<[(Name, Ty)]>, real: Ty },
/// L7 error-recovery sentinel. Unifies with anything, suppresses
/// cascades. Replaces the scattered `T.TVar "_lit"/"_ambig"/…`
/// magic strings (`Solve.hs:379` `Unresolved` scaffold) with ONE
/// typed node (L6).
Error,
}
fields is a sorted boxed slice, not a HashMap — the Haskell Record1
uses Map String Variable (Type.hs:76) and every emission path already has to
"sort by _fieldIndex". Sorting at the interning site makes L4 structural.
The arena union-find (the L3 centrepiece)
The Haskell UnionFind.hs is Point a = Pt (IORef (PointInfo a)) with pointer
identity for Eq (UnionFind.hs:61-62) and weighted-union + path-compression
over IORef links. Every soundness argument that says "these two variables are
the same" is a pointer comparison today. We replace pointer identity with a
dense integer index into an arena Vec, and the links become indices.
/// Type-variable identity. Replaces `UF.Point` pointer-eq (UnionFind.hs:61).
/// Allocation order is deterministic (L4) because it is drawn from the
/// InferCtx counter, not from hashmap order.
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct TyVarId(u32);
enum Slot {
/// Root: carries the descriptor + union-by-rank weight.
Root { content: Content, rank: u32 },
/// Non-root: points at its parent (was `PointInfo::Link`, UnionFind.hs:34).
Link(TyVarId),
}
/// The union-find store. Local to ONE `infer` query; never global (L1).
/// This is the "honest scoped-mutation sweet spot" of 01-architecture.
pub struct UnionFind {
slots: Vec<Slot>,
}
Content mirrors Type.hs:51 — minus the dead _rank/_mark/_copy:
enum Content {
Flex(Option<Name>), // FlexVar
FlexSuper(SuperType, Option<Name>), // Number/Comparable/Appendable/CompAppend
Rigid(Name), // from a user annotation; won't unify w/ concrete
RigidSuper(SuperType, Name),
Structure(FlatTy), // resolved concrete shape
Alias { home: ModuleId, name: Name, args: Vec<(Name, TyVarId)>, real: TyVarId },
Error, // recovery
}
/// `Type.hs:71` FlatType, over TyVarId instead of Variable.
enum FlatTy {
App { home: ModuleId, name: Name, args: Vec<TyVarId> },
Fun(TyVarId, TyVarId),
EmptyRecord,
Record { fields: BTreeMap<Name, TyVarId>, ext: TyVarId },
Unit,
Tuple(TyVarId, TyVarId, Option<TyVarId>),
}
enum SuperType { Number, Comparable, Appendable, CompAppend } // Type.hs:62
find — path compression, by index
Direct translation of repr (UnionFind.hs:47-58); the only change is
IORef-write → Vec-write:
impl UnionFind {
fn find(&mut self, mut v: TyVarId) -> TyVarId {
// Collect the chain, then point every node at the root (compression).
let root = {
let mut r = v;
while let Slot::Link(p) = self.slots[r.0 as usize] { r = p; }
r
};
while let Slot::Link(p) = self.slots[v.0 as usize] {
self.slots[v.0 as usize] = Slot::Link(root);
v = p;
}
root
}
}
union — by rank, carrying merged content
merge (Unify.hs:520-525) unions with newRank = min(rank1, rank2); the
weighted link itself is UnionFind.hs:106-129. In the arena the higher-rank root
wins the parent slot; equal ranks bump the survivor (union-by-rank):
fn union(&mut self, a: TyVarId, b: TyVarId, content: Content) {
let (ra, rb) = (self.find(a), self.find(b));
if ra == rb { self.set_content(ra, content); return; }
let (rank_a, rank_b) = (self.rank(ra), self.rank(rb));
let (root, child, mut rank) =
if rank_a >= rank_b { (ra, rb, rank_a) } else { (rb, ra, rank_b) };
if rank_a == rank_b { rank += 1; }
self.slots[child.0 as usize] = Slot::Link(root);
self.slots[root.0 as usize] = Slot::Root { content, rank };
}
occurs-check — a TyVarId set, not UF.equivalent scans
Occurs.hs:90-94 walks a [Variable] seen-list calling UF.equivalent
(O(n) representative compares per step). With integer ids the seen-set is a
FxHashSet<TyVarId> of representatives (internal cache; never emitted, so
HashSet is fine per L4's carve-out). Membership is O(1); the whole check is
linear in the visited graph. The check gates the Flex ↔ Structure merge
(Unify.hs:192-223) that otherwise builds an infinite type and OOMs the host
(the >3 GB blow-up in a downstream app documented there).
fn occurs(&mut self, target: TyVarId) -> bool {
let root = self.find(target);
let mut seen = FxHashSet::default();
self.occurs_in(root, root, &mut seen) // reject if root reachable from its own structure
}
As built (UnionFind::occurs, rust/crates/ty/src/unify.rs), the walk runs on
an explicit stack and reads each root's children in place: it copies no record
field map per node, and its depth does not depend on the thread's stack. The
visited set is not a fresh hash set per call: it is a mark per variable on the
UnionFind, valid for one call through an epoch counter, and the stack is
reused too, so a check allocates nothing.
Binding a variable moves, it does not copy. In unify_vars the Error and
Flex cases read the two roots by kind only, and the bound side's content
moves into the merged root (union overwrites both slots). Only the rigid,
bounded and structured cases take owned copies, because unify_flat and
satisfy may read either root while they run.
A field access or a record update on a closed record does not unify the
whole record. model.f and { model | f = x } unify the base with a fresh
constraint { f | ρ }. When the base is a closed record holding the fields,
UnionFind::unify_closed_record_fresh_row reaches the state the general
unify_records leaves on every live node, with the same variables allocated in
the same order: it links the constraint under the base, unifies (for an access,
links) each shared field in field order and stops at the first clash, and
allocates the variable for the row's record of remaining fields without copying
the base's map into it or walking it for the occurs check. Nothing live refers
to that row once the constraint is a link, so its content is never read. An
access costs O(log fields) instead of O(size of the record). The
infer_readback_tests differential runs every corpus def with this fast form on
and off and compares errors, variables allocated, every recorded type, the
obligations and the whole World.
The #166 / D2 close is skipped when it is a no-op. On the lowering path an
update of a record param (or of a record def) closes its row by unifying the
base with a fresh instance of the declared record. Once the base IS that record
(every node reachable along the declared type is a structure of the same shape:
identical nominal names, closed records with the same field names, no type
variable and no Error in the declared type), that unify only links fresh
nodes under the base's nodes and re-sets each root to an equal content.
Infer::skip_ground_close checks this with one read-only walk
(UnionFind::ground_instance_nodes) and then only reserves the same number of
variables, so every later id, and every t<id> name, is unchanged. The other
effect of the skipped unify, a rank rising from 0 to 1 on a structured class,
only decides which member of a non-Flex class is its root; a structured class
never becomes Flex again and only Flex / FlexSuper roots are printed. The
infer_readback_tests differential runs every corpus def with the skip on and
off (ground_close_is_skipped_and_changes_nothing pins that it fires).
The #166 call-site harvest is demanded only when it is read, and is linear.
When a param's declared type gives no closed record, the close of an update of
that param reads the closed record its callers pass (callsite_param_records_query).
ty::declared_param_record is the one signature walk: the close reads it first,
and the lowering infer_query demands the harvest only when it is None for
some updated param (ty::wants_callsite_harvest). So an annotated
set : String -> Model -> Model infers no caller. When the harvest is needed,
each caller is inferred once (caller_record_args_query, which summarises its
calls to every def that wants a harvest), the callers come from a syntactic
reverse-call index (direct_callers_query), and the per-caller summaries are
folded. The fold keeps, per position, the record every call agrees on, or
None once two differ. That does not depend on order, and read-back does not
depend on which other entries are read back, so the result equals the
per-callee ty::callsite_param_records_for. The differentials
skydb/tests/callsite_harvest_identity.rs and
project/src/harvest_identity_tests.rs (every example) compare the two, and
skydb/tests/typed_table_growth.rs pins linear growth for annotated and
unannotated helpers.
Still quadratic (known): binding an instantiated scheme variable to a large
structure walks the structure for the occurs check (a Codec.field step binds
r to the record and b to the rest of the constructor arrow), and the
skipped close still walks the declared record once per update (no allocation
and no unify, but O(size)). The ignored test
unifier_work_is_linear_in_record_size (skydb/tests/typed_table_growth.rs)
measures the unifier's part.
Go-FFI references — typed on the Result wrapper (v0.27.0)
Until v0.27.0 every Res::Foreign reference (a sky add binding) inferred to a
fresh flexible variable (infer.rs, the old leniency contract). So
probe : Int / probe = Pkg.read "x" 0 0 type-checked, the lowering narrowed
the wrapper's SkyResult with rt.AsInt, and the program crashed at run time.
The Haskell oracle typed FFI calls from the pinned surface; the Rust port had
dropped the signature (build_ffi_table kept only symbols), an untracked
divergence. It is closed as follows.
- Delivery through the database, not a check-only parameter. The pinned
skyTypestrings (sky-ffi/<pkg>.kernel.json) are projected by the driver into ahir::FfiSurfaceand installed on the db: a salsa input (skydb::FfiSurfaceInput) onSkyDatabase, an eager field onSourceDb.SkyDb::ffi_fn(package, name)serves it, andInferconsults it at theRes::Foreignarm. Every inference run sees it — the checker, the signature pass that infers each UNANNOTATED def (soreadIt s = Pkg.read s 0 0carries theResultinto its callers), the lowering'scompute_body_types, the Sky.Spa partition and the LSP.tydoes not depend on thefficrate. - Lazy parsing.
ty::ffi_sigparses one skyType when a reference to it is first instantiated, memoised per(package, name)per inference run. A surface is never parsed whole (a payment SDK pins more than 80,000 bindings). - What is strict: the
Result Errorwrapper, the arity (the top-level arrow count must equal the inspector's arity), primitives (with Go residue normalised:int*/uint*/byte/rune/uintptr/untyped int→Int,float*→Float,string→String,bool→Bool),List,Maybe, tuples and a callback parameter's arrows. The error type is emitted qualified (Sky.Core.Error.Error), so a dependency's owntype Errornever unifies with it (nominal::same). - What is the wildcard
any: Go-opaque types (Name@pkg, unknown or lower-case names), a callback's result, a zero-parameter callback, any other function-typed position,Bytes,Dict(the generator renders every Go map asDict String Vwhatever its key),error, a legacy 2-tuple payload ending inBool(older surfaces render the comma-okMaybe Tthat way), Go array residue andcomplex*. A single capital letter is a type variable. - Fallback. A missing or unreadable skyType (18 of 81,639 bindings across
the example surfaces have none; none is unreadable) gets the arity-only
scheme
any -> … -> Result Error any: the wrapper stays enforced. - Leniency that remains. A package whose surface is not loaded at all keeps
the fresh flexible variable; lowering refuses the reference (
sky install) andsky checkruns the same path, so no unsound binary results. Sky.Ffi.Ffi.kernel/call/callPure/callTaskare stdlib-only: app code gets[E1011](ty::check, theSTDLIB_ONLY_FFIscan).Ffi.call*are by-name calls with a free result type;Ffi.kernelis typed only by the def's own annotation, which the checker cannot compare with the kernel's real signature. No module is exempt by its name. The build'shir::FfiTrustgrants the only exceptions (project::ffi_trust): modules whose text is the compiler's bundled-app source, andSpa_*kernels in a Sky.Spa-generated project.- Lowering. A partially applied FFI function eta-expands into a closure
(
ffi_partial), and a fully applied call whose type is neitheranynorSkyResultis a hard lowering error (the backstop). - Future tier: payload soundness. Go-opaque payloads are wildcards. Typing them needs nominal opaque types plus the implements axiom described below.
infer(DefId) — inference as a salsa query (target)
Implementation status. HM inference is built (M3: arena union-find, generalisation, exhaustiveness, per-expression types; 39/39 non-FFI typecheck-match + reject-parity), and
inferis a real#[salsa::tracked]query —infer_query,rust/crates/skydb/src/lib.rs:304, demanded through the database the build driver constructs (01status). This note used to say the salsa framing was target-only and that inference "is invoked value-threaded overhir::db::SourceDb, not as memoised salsa queries"; that stopped being true when the resolve/infer/lower stages landed.Three things in this section are still not what the code does, and each is marked where it appears rather than covered by a blanket disclaimer:
- the solver budget (see "Budget" below) — not built at all;
- the
RegionTableshape (see "The per-region type table") — the real table isHashMap<ExprId, Ty>, notBTreeMap<Span, Ty>;exhaustiveness(DefId)is not a separate tracked query, and the#![deny(non_exhaustive_omitted_patterns)]"L6 turned inward" lint is not applied in any crate (grep -rn 'non_exhaustive_omitted_patterns' rust/cratesis empty; only#![forbid(unsafe_code)]is in force).
Today constraint generation is a whole-module IO pass (constrainModule,
Constrain/Module.hs:17) feeding one solve (Solve.hs:803); the LSP had to
bolt a 5-round canonicalise+solve fixpoint on top to see cross-module types
(CLAUDE.md v0.17.3 note). In the query core that fixpoint disappears: infer is
per-DefId, and cross-module signatures arrive by depending on the callee's
infer, memoised by salsa (L2). No manual rounds, no 8 LSP IORefs.
/// skydb query. Returns partial results + diagnostics — never throws (L7).
#[salsa::tracked]
pub fn infer(db: &dyn Db, def: DefId) -> InferResult {
let mut cx = InferCtx::new(db, def);
let hir = db.def_body(def);
let want = cx.instantiate_signature(def); // annotation → fresh vars
cx.constrain(&hir, want); // generate + solve, interleaved
cx.finish() // read back env + region table + diags
}
pub struct InferResult {
pub scheme: Ty, // generalised type of `def`
pub regions: RegionTable, // per-region types → lowering (07)
// NOTE: an earlier sketch carried `instances: Vec<CallInstance>` here as
// "monomorphisation keys". There is no monomorphiser and no `CallInstance`
// — see 07 §5.1. Nothing collects call instances.
pub diagnostics: Vec<Diagnostic>,
}
The current solver already is value-threaded — solveHelp :: SolverState -> Constraint -> IO (Maybe String, SolverState) (Solve.hs:1217) returns errors as
values and threads state. That is exactly the shape L1/L7 want; we drop the IO
and the residual global IORefs (rowExtCounter) into InferCtx.
struct InferCtx<'db> {
db: &'db dyn Db,
uf: UnionFind,
/// L4 deterministic fresh supply. Seeded from a pre-order traversal
/// index of `def`, NOT from allocation happenstance. Replaces the
/// `Counter = IORef Int` (Constrain/Expression.hs:133) AND the global
/// `rowExtCounter` (Unify.hs:42). `fresh_row_ext()` draws from the
/// same counter so merged records read back OPEN with a unique name
/// (Unify.hs:499) — now deterministic.
next_var: u32,
/// name → var, the solver `_env` (Solve.hs:506). Scoped push/pop for
/// let/lambda/case shadowing (Solve.hs:1375-1401), not a global leak.
env: ScopedMap<Name, TyVarId>,
/// region → var; frozen to `RegionTable` at the end (Solve.hs:762).
region_vars: FxHashMap<Span, TyVarId>,
/// FFI interface-satisfaction registry (see below). A pinned salsa
/// input, not a mutable global (replaces `_ffiImplements`, Solve.hs:509
/// + the deleted `ffiImplementsRef`).
ffi_implements: &'db ImplementsMap,
/// NOT BUILT — see "Budget" below. The Rust `ty` crate has no step
/// counter and no cap; these two fields do not exist.
steps: u64,
budget: u64,
diagnostics: Vec<Diagnostic>,
}
Fresh-var determinism (L4)
fresh() returns TyVarId(self.next_var); self.next_var += 1; and pushes a
Slot::Root { Flex(name), rank: 0 }. The critical rule, straight from
01-architecture-overview.md:88-93: the counter is advanced at the collection
(constraint-generation) site in a fixed pre-order walk of the HIR, never at an
emission site keyed by hashmap order. Same source ⇒ same TyVarIds ⇒ same read-
back ⇒ byte-identical Go (the reproducibility gate).
Budget — NOT BUILT
This is the one section here that is target, not description, and it is called out because the rest of this doc is not. The section header used to read "Keep the structural budget verbatim" in the imperative-plan voice, next to a
budget: u64field in theInferCtxsketch above, under a status note (:219-227) saying the inference logic described here "is what the code does". A reader could reasonably conclude the fence exists. It does not:$ grep -rn 'bump_step\|budget' rust/crates/ty/src $ # nothingNo
budgetfield, nobump_step, and neitherSKY_SOLVER_BUDGETnorSKY_SOLVER_BUDGET_FACTORis read anywhere inrust/. A constraint-explosion module OOMs the host rather than aborting with a diagnostic. Seedocs/KNOWN_LIMITATIONS.md#5.
The intended design, carried over from the retired Haskell solver
(Solve.hs:708-746): max(5_000_000, constraint_count × 200),
env-overridable via SKY_SOLVER_BUDGET / SKY_SOLVER_BUDGET_FACTOR, 0
disables. It is the fence against constraint-explosion OOM (Limitation #17).
bump_step() returns Err(budget_msg) past the cap; the caller
short-circuits with a diagnostic. Per-DefId inference would make the
per-query budget naturally smaller than the old whole-module one.
Unification (the soundness core)
unify(a, b) -> Result<(), TypeError> mirrors actuallyUnify
(Unify.hs:171-435) arm-for-arm. The arms that pin soundness:
- Flex ↔ Structure/Alias guard with
occursbefore merging (Unify.hs:192-223) — infinite-type rejection. - Rigid unifies only with Flex or Error (
Unify.hs:263-267) — a user-annotated rigid var never silently unifies with a concrete type. The annotation gate (infer_def_against,ty/src/infer.rs) skolemises EVERY quantifier of a top-level annotation exceptany(since v0.29.2; before, an argument-only quantifier stayed flex and could be pinned, socoerce : a -> bwas accepted). A rigid against a bounded flex whose bound its name does not spell is refused at the end of the definition (UnionFind::rigid_missing), so a later clash with a type gives the clearer message. Let annotations are checked after the group (check_let_anno_generality). FlexSuper(Number/Comparable/Appendable/CompAppend) matched viasuperMatches/combineSuper(Unify.hs:529-554) — keep theisSkyCorehome guard so(5).fieldis still rejected.- App ↔ App exact + the two axioms below (
Unify.hs:330-381). - App ↔ Alias same-name unfold-and-match (
Unify.hs:282-308) for recursive parametric aliases.
Wildcard-any, per occurrence — preserve EXACTLY
Sky's "any" is a per-occurrence wildcard: each textual any gets its own
fresh var so destructuring one occurrence never constrains another (the
AttrA String | AttrB any cross-branch example, Instantiate.hs:58-66). Two
halves, both mandatory:
- Instantiation drops
"any"from the shared env so each occurrence is fresh (Instantiate.hs:43filter (/= "any");buildEnvreturns the env unchanged forTVar "any",Instantiate.hs:69-72). In Rust,instantiate(scheme)builds the shared substitution overfree_vars \ {"any"}and callsfresh()at everyTy::Var("any")leaf. - The polymorphism gate is
free.iter().any(|v| v != "any"), never!free.is_empty()— reproduced at all three sites: the same-module CForeign/CLocal choice (Constrain/Expression.hs:472), the arity gate (:1122), the value-slot gate (:1201). ACfg -> msgwith onlyanyfree is not polymorphic; treating it as polymorphic would diverge the body↔caller vars under per-call-site re-instantiation and accept wrong return types.
/// The one true polymorphism predicate. Do NOT replace with `!free.is_empty()`.
fn is_polymorphic(free: &[Name]) -> bool {
free.iter().any(|n| n.as_str() != "any")
}
A ty unit test asserts is_polymorphic(&["any"]) == false and
is_polymorphic(&["msg"]) == true, mirroring
Sky.Type.StrictHmArityGateSpec's wa-a / wp-a cases.
FFI interface-satisfaction axiom — the self-host's missing soundness
When two nullary Apps have different names and the pinned FFI registry says
one implements the other (Go structural interface satisfaction), unify succeeds
as a widening (Unify.hs:358 inside the App↔App arm). This closes the Fyne
Label ↔ CanvasObject and Stripe Iter ↔ Token cases (CLAUDE.md Limitation #6)
and is precisely the check the any-boxed self-host could not make.
// Unify.hs:108-121 — one-way relation, symmetric probe.
fn implements(&self, q: &Name, iface: &Name) -> bool {
self.ffi_implements.get(q).map_or(false, |is| is.contains(iface))
}
fn ffi_interface_pair(&self, n1: &Name, n2: &Name) -> bool {
self.implements(n1, n2) || self.implements(n2, n1) // isFfiInterfacePair
}
// inside unify's App↔App arm, AFTER exact-match fails (Unify.hs:358):
if a.args.is_empty() && b.args.is_empty() && self.ffi_interface_pair(&a.name, &b.name) {
return self.commit(va, vb, FlatTy::App(a)); // widen; principal type preserved
}
ImplementsMap is a pinned salsa input built once from the deterministic FFI
surface (09), replacing both the _us_ffiImplements thread and the deleted
ffiImplementsRef global (Unify.hs:53-60). Empty map ⇒ strict nominal equality
(the safe default). Keep the sibling Value ↔ qualified bridge
(Unify.hs:377-380) for hand-coded kernel sigs, one-way (hasQualifiedMarker
guards the _at_ mangled form only).
Records + row polymorphism
unify_records reproduces Unify.hs:468-502 — the closed/open discipline is a
real soundness fix (the takesRecord { wrong fields } panic class,
Unify.hs:449-460):
- shared fields unify pairwise;
- a closed side forbids extras on the other side (
extras{1,2}Illegal,Unify.hs:486-489) — reject; - both closed ⇒ exact field-set match;
- both open ⇒ row-poly merge under a freshly-named extension var
(
Unify.hs:499) — nowcx.fresh_row_ext(), deterministic (L4).
Keep the open-record ↔ empty-home FFI-opaque arm (Unify.hs:421-433): an
expr.field open-row pattern satisfies an opaque FFI nominal (getter-backed) but
a closed literal does not.
Generalisation & instantiation
Sky does not generalise by rank (why the Elm _rank/_mark/_copy pool is
dead). Generalisation is: solve the def, read back its var, then rename residual
flex vars to Forall quantifiers — generaliseToAnnotation :: Ty -> Annotation
(Compile.hs:11292). Instantiation is fromAnnotation (Instantiate.hs:39):
fresh flex var per quantifier except "any".
fn generalize(&mut self, root: TyVarId) -> Scheme {
let ty = self.read_back(root); // variableToType (Solve.hs:1428)
let free = free_vars(ty).into_iter()
.filter(|v| v.as_str() != "any") // Instantiate.hs:43
.collect::<Vec<_>>();
Scheme { vars: free, ty }
}
fn instantiate(&mut self, s: &Scheme) -> TyVarId {
// one shared fresh var per non-`any` quantifier …
let sub: FxHashMap<Name, TyVarId> =
s.vars.iter().map(|v| (*v, self.fresh(Some(*v)))).collect();
// … but `Ty::Var("any")` leaves call `fresh()` fresh EACH time (buildEnv, Instantiate.hs:69)
self.ty_to_var(&s.ty, &sub)
}
Same-module polymorphic re-instantiation
A sibling reference to a polymorphic annotated same-module def emits CForeign
and α-renames per call site, so f : Cfg msg -> msg used at msg=Int and
msg=Bool in one module both work (Constrain/Expression.hs:466-526). The choice
is: home == current_module && same_mod_annots[name] is polymorphic (the gate
above) ⇒ CForeign + fresh instantiation; else ⇒ CLocal (shared env
var). Non-polymorphic / wildcard-only sigs must stay on the shared path —
identity-based unification on nominal aliases and wildcard-any binding both need
the shared body↔caller var chain (CLAUDE.md "Same-module polymorphic
re-instantiation"). In the query world, same_mod_annots is just
db.module_signatures(module); cross-module externals are
db.def_scheme(callee) — both memoised, no fixpoint.
Each polymorphic def's quantifiers are α-renamed with fresh_name per def
(Constrain/Expression.hs:1337-1346) so sibling defs' as don't unify.
Let-generalisation
Implemented in v0.27.0 (rust/crates/ty/src/infer.rs, the Expr::Let arm and
generalise_let_group). Before it, every let binder was ONE shared type var,
so a local helper could be used at one type only, and
docs/language/types.md over-promised "full HM, including generalisation".
Order. A let's defs are split into strongly connected components of
their references to each other (let_def_groups, Tarjan) and inferred
callees-first, so y = twice 1 beside twice x = … sees twice's scheme.
Recursion inside a group stays monomorphic, as at top level.
Quantifiers. After a group is inferred, each binder's quantifiers are the
unbound Flex / FlexSuper roots reachable from its type that are NOT
reachable from Γ. Γ is every local typed so far EXCEPT the ones bound inside
the group (its binders, their parameters, and every lambda / case / nested-let
binder in their bodies). That rule matters on the check path, which types a
def's parameters lazily at their first reference: an outer parameter first
typed inside the group is still Γ. Rigid annotation vars never generalise.
Instantiation. A reference to a generalised binder copies its type graph
(instantiate_local), replacing each quantifier with a fresh var (a super-var
keeps its constraint) and sharing every sub-graph that holds no quantifier.
The value restriction. Only a binding whose right-hand side is a function
(f x = …) or a syntactic value (lambda, literal, reference, constructor
applied to values, list / tuple / record of values) generalises. An
application stays monomorphic. Sky is pure, so this is not the ML reference
problem; it is the erased Go ABI. A value is computed ONCE, at one erased Go
type, and a lenient kernel signature whose result is an unconstrained var
could otherwise hand the same computed value to two slots of incompatible
types — a runtime narrowing failure instead of a type error. A function is
re-entered per call, so each call narrows its own result, exactly as a
polymorphic top-level def does. Pinned by
ty/tests/reject/corpus/let_application_not_generalised.sky.
Lowering. There is no specialisation (07 §5.1). At the end of a def
(collapse_let_poly), a generalised binder whose every instance read back to
the SAME type is unified with that instance: it is used monomorphically, and
it lowers to the same typed closure it always did (coerce-floor unchanged
across the corpus). A binder used at two types stays generic; its closure
lowers once with any for its quantifiers (doc 14 R12, as for a polymorphic
top-level def) and each call site narrows the result at R1. For that, a call
of a non-Def callee reports its real Go result type (lower_call), not the
use site's inferred type. Collapsing identical instances binds only the
quantifiers, which nothing outside the binder mentions, so no type in the
enclosing scope changes.
Strict-HM arity gate (E2007, Limitation #7) — keep
Two surfaces, one diagnostic. declared_arity counts leading arrows
(Constrain/Expression.hs:4127-4131):
fn declared_arity(scheme: &Scheme) -> u32 {
let mut n = 0; let mut t = scheme.ty;
while let TyData::Fun(_, to) = db.lookup(t) { n += 1; t = to; }
n
}
- Call site (
arityGateCall,:1066): calling a0-arg binding with()firesCArityMismatch{declared:0, supplied:1}— but only when the arg is unit and the binding is non-polymorphic (maybeEmitArityMismatch,:1114-1131). - Value slot (
valueSlotGate*,:1171): a bare reference of a() -> Xbinding into a concrete (non-arrow, non-var) slot firesCArityMismatch{declared:d, supplied:0}(:1206-1207). Classification bySlotShape(:1233):Var → skip(defer to normal unify),Arrow → skip(slot wants a function),Value → fire when d ≥ 1.
Both gates are guarded by the wildcard-polymorphism predicate (:1122,:1201)
so real polymorphism is never mis-flagged. Represent the mismatch as its own
constraint (Type.hs:104 CArityMismatch), solved to a Diagnostic with code
E2007 (Diagnostic.hs:206) — no exception, continue.
Exhaustiveness — keep it strong (L6)
Exhaustiveness.hs is deliberately conservative-but-real: for an ADT case it
requires every constructor of the subject's union to appear (or a
wildcard/var/alias head), warning E3001 (Diagnostic.hs:211) on any miss
(Exhaustiveness.hs:100-119). Bool needs both True/False; unit is trivially
covered; infinite-domain literals (Int/String/Float/Char) require a wildcard arm.
This is stronger than GHC-as-configured and it is a keeper.
Port checkBranches (:100) + classify (:129) verbatim into ty as a query
exhaustiveness(DefId) -> Vec<Diagnostic> fed by resolved constructor sets from
hir. Two upgrades the Rust setting affords:
- Run it over a column matrix (Maranget-style) so nested patterns and
literal ranges get the same rigor without false positives — the current checker
analyses only top-level arm heads (
Exhaustiveness.hs:8-13); widening it is additive and never weakens the guarantee. - L6 turned inward: the compiler's own IR/AST enums carry
#![deny(non_exhaustive_omitted_patterns)]; no_ =>catch-alls on our own types. The self-host'sgetDeclNamepanic (33-gap audit) is unrepresentable.
The per-region type table (the output that drives lowering)
Every solved CEqual/CLocal/CForeign records its actual var against the
constraint's source region (recordRegionVar, Solve.hs:762-766, skipping the
(0,0) synthetic sentinel); at solve-end the map is frozen to concrete types
(freezeRegionTypes, :772). This RegionTypes = Map Region Ty (Solve.hs:358)
is what type-directed lowering reads to pick a typed Go shape per sub-expression
(07; CLAUDE.md "Type-directed lowering").
What was built is ExprId-keyed, and there is no RegionTable type. The
sketch below described pub struct RegionTable(BTreeMap<Span, Ty>) "keyed by
Span (interned FileId + range), iterated in id/BTree order (L4)". No such type
exists — grep -rn 'RegionTable\|region_ty' rust/crates is empty — and the L4
justification does not describe the shipped structure, which is a HashMap.
// The real shape — Infer::infer_def_tables, rust/crates/ty/src/infer.rs
pub(crate) fn infer_def_tables(&mut self, body: &Body) -> TypedTables;
// TypedTables { result, signature, exprs: HashMap<ExprId, TyRef>,
// locals: HashMap<LocalId, TyRef>, table: TyTable }
The shared type table
A def's recorded types are read straight out of the solved union-find into one
hash-consed TyTable (rust/crates/ty/src/tytable.rs): Infer::read_back_ref
builds each node from its children's references (TyTableBuilder::intern_node),
so no owned Ty tree is built per expression, and a sub-tree shared by many
types is stored and read once. BodyTypes keeps the API it had (expr, local
return the owned Ty) and adds expr_ref / local_ref / table for readers
that work per reference.
The read-back memo maps a union-find root to its reference and lives for ONE
drain (ReadBackSink: infer_def_tables, the checker's
recorded_expr_table), never on Infer: earlier read-backs (the E2007 arity
gate, the value restriction, collapse_let_poly) run before later
unifications. It stores only UNTAINTED results. A frame is tainted when it, or
any frame below it, met the cycle guard (a root already on the path, read back
as Error); a tainted value depends on the path that reached it. An untainted
value met no node on its path, so its root is on no cycle, and reading it from
any other path gives the same value. Cycles are real: satisfy binds a bounded
variable without an occurs check, and normalize_record follows recursive
rows. cyclic_subroot_is_not_shared pins the rule on N = Fun(A, P),
A = List N, P = Maybe N.
The checker drains its table with recorded_expr_table: entries in push order,
with duplicates, which the [E2008] first-seen dedup depends on.
dictkey::unsupported_keys_ref computes each distinct type's offending keys
once (first-occurrence order, deduplicated by render, as walk), and the
[E2009]/[E2010]/[E2011]/[E2013] scans read types through
tytable::ExprTypes, a last-wins lookup that rebuilds only what a scan asks
for.
The owned read-back stays as the test oracle (infer_def_typed and
recorded_expr_types, #[cfg(test)]). The differential tests in
rust/crates/ty/src/infer_readback_tests.rs drain the same solved union-find
both ways for every def of the stdlib, every example, the accept and reject
corpora and generated large-record programs, in the lowering, tooling and
checker modes. The work counters (ty::counters) and the growth ratchet
type_table_work_is_linear_in_record_size hold read-back, owned rebuilds, the
key scan, interning and goty linear in the size of a record.
ExprId is the HIR arena index, and rust/crates/ty/src/check.rs:202-205
states why it was preferred: it is "the stable per-expression identity in this
HIR, a cleaner key than a source span for an arena-based IR". Determinism (L4)
therefore does not come from BTree iteration order here — the table is
lookup-only during lowering, so its iteration order never reaches the output
(see 07 §5.2 for the same argument about used_types).
This replaces the historical scopeStateRef/_lc_regionTypes IORef read that
was "the load-bearing reason the LowerCtx cascade couldn't migrate"
(Solve.hs:88-108). Here it is a pure value returned by the query — the
per-module ledger machinery (_stPerModuleRegions, Solve.hs:143) that patched
cross-module region collisions is unnecessary: regions are (FileId, range) and
each DefId's table is its own, keyed by an interned FileId that cannot
collide across modules.
Error recovery — type error → Error node + diagnostic, continue (L7)
unify never aborts the query. On a genuine mismatch it: (1) pushes a structured
Diagnostic (rich record-diff for TEA-cfg shapes, Solve.hs:1276-1298), and (2)
commits both vars to Content::Error, which unifies with anything
(Unify.hs:236-242) and reads back as the Ty::Error sentinel
(variableToTypeSeen … Error, Solve.hs:1474). Cascades are suppressed; one
mistake yields one diagnostic, and inference produces a partial InferResult
the LSP can still hover over. The read-back's own cycle guard
(anyEquivSeen, Solve.hs:1449-1451) returns an Error-class sentinel rather
than looping on a pre-existing cyclic graph.
fn unify(&mut self, a: TyVarId, b: TyVarId) -> Result<(), ()> {
match self.try_unify(a, b) {
Ok(()) => Ok(()),
Err(mismatch) => {
self.diagnostics.push(mismatch.into_diagnostic());
self.commit(a, b, Content::Error); // suppress cascade (Unify.hs:236)
Err(())
}
}
}
What we delete (and why it is safe)
| Dropped | Why | Cite |
|---|---|---|
Descriptor._rank / _mark / _copy | Elm let-generalisation pool; Sky generalises via annotations, never used | Type.hs:42-47; self-host :112-114 |
rowExtCounter global IORef | L1 + L4 violation; becomes InferCtx.next_var | Unify.hs:42-50 |
ffiImplementsRef / _ffiImplements thread | pinned salsa input instead | Unify.hs:53-60; Solve.hs:509 |
_stPerModule{Env,Regions} + _stCurrentModule | per-DefId queries + interned FileId regions can't collide | Solve.hs:125-165 |
| LSP 5-round canonicalise+solve fixpoint | salsa memoisation of infer dependencies | CLAUDE.md v0.17.3 |
Unresolved magic-string sentinels (18 strings) | one typed Ty::Error (L6) | Solve.hs:361-399 |
Test obligations (differential + property)
- Wildcard gate:
is_polymorphic(["any"]) == false; portStrictHmArityGateSpec(wa-a,wp-a,k-a,k-b,u-a,u-b). - FFI axiom: Fyne
Label→CanvasObjectand StripeIter→Tokenaccept; unrelated nullary pair rejects. - Records:
takesRecord { wrong fields }rejects (closed-record extras); open-record merge accepts. - Occurs:
a = List ashape rejects, no hang. - Exhaustiveness: missing-
Nothingarm warnsE3001; wildcard suppresses. - Determinism (L4): infer a def twice, assert identical
TyVarIdallocation and identicalRegionTable(the reproducibility gate,xtask). - Oracle: for every corpus def, the read-back
Tymatches the Haskell compiler'sgeneraliseToAnnotationoutput (accept/reject parity,11).