What it does
static-inferred(Kraken, Iron): everything below, plus closures whose parameter and result types come from the expected function type (or from use), andlet x = nulltyped as a nullable inferred from later uses.- Generics and interfaces (both static disciplines): generic functions and types with bounds, where clauses, defaults, and constant parameters; interfaces (traits) with methods, default methods, constants, associated types (
T::Item,<T as I>::Item,I<Item = u8>), and supertraits;implblocks, generic ones included; interface methods resolved through bounds,dyntypes, and implementations, with automatic receiver borrowing as a profile toggle;impl Traitparameters and results (the hidden type is reported); overlapping implementations and missing, extra, or mistyped members are reported. Checking mode flows through generic calls: an expected result type reaches the arguments, so a wrong argument is reported at itself. - Unions and intersections (
int|string,A & B) from HIR v3, with injections and type tests. - Exhaustiveness through match-lang: the values a
matchmisses are reported as patterns (non-exhaustive match: Some(false) not covered); unreachable arms and redundant or-alternatives are warnings. - Monomorphization plan: every reachable instance of a generic function, with a copy-or-share policy per profile (copy all, share all, or Iron's selective policy: copy small or attributed items) and interface calls on placeholders resolved per instance.
?through a profile hook: a?lowered as a template is ordinary code; one kept as a named intrinsic is typed against nullable and two-variant carrier types, with an optional conversion interface for failure values.static-explicit(C, Go, Zero): declared types on parameters, returns, fields, constants, and globals; local inference forletfrom initializers and for unsuffixed literals; primitive, tuple, array, slice, reference, pointer, function, nullable, map, record, sum, and class types; every OPS operation typed by its operand types, with policy legality (promoteis rejected on statically typed results); calls with named, default, variadic, and spread arguments; fields and methods throughimplblocks, classes, and base classes;if,match, loops, labelled blocks, closures,async/await/spawn, generators,try/catchwith type tests, casts, and intrinsics.dynamic(Python, Lua, Mox): every value isany; only the errors that are certain whatever the run-time values are reported (wrong argument count to a known function, unknown named arguments, constructor patterns of the wrong length, unknown record fields).- Host declarations: a language's library lives outside the unit;
Checkertakes the types of extern names, other units' definitions, named intrinsics, members of host types, and attributes that force a monomorphization strategy.
Not in this release: the gradual and hm disciplines (0.5.0), associated types with parameters of their own, and multi-segment associated paths (T::Assoc::f), both reported as Unsupported. Not this crate's job: name resolution (resolve-lang), compiling patterns into decision trees, orphan rules (they depend on crate boundaries a unit does not see), and mutability and ownership (capabilities over typed HIR).
What each guarantee rests on:
| Guarantee | How it is checked |
|---|---|
| Well-typed programs check clean, with exactly the types they should have. | A typed generator builds random well-typed programs (arithmetic, comparisons, if, blocks, calls, tuples, arrays, records, sums with match, constructor calls, method calls, field access, indexing); property tests require no diagnostic, the generated type for every expression, and the right method for every method call. |
| One mistake, one diagnostic, at the mistake. | Property: replacing one numeric literal of a well-typed program with true yields exactly one diagnostic, on that literal. Property: replacing any leaf with an error node yields none. |
| Checking never panics and always terminates. | Property: random HIR of every form, repaired by hir-lang's lenient validation, checks without panicking under three profiles, types every live expression and pattern, and is deterministic; under any step budget it finishes or returns BudgetExceeded. |
| Generic programs check clean, with exactly the types, dispatch, and instances they should have. | A second typed generator builds programs over a generic record with a generic impl, a generic sum, an interface with a default method, an interface with an associated type and a bounded generic impl, bounded generic functions, and closures passed to generics; property tests require no diagnostic, the exact type (generic arguments included) of every expression, the exact method of every method call, and a plan instance with the exact arguments for every generic call. A corpus of Kraken-like programs (generic containers, interface dispatch by bound and by dyn, closures, ?, an iterator interface, match exhaustiveness) checks expected types, dispatch, plans, and diagnostics. |
| One mistake in a generic program, one diagnostic, at the mistake. | Property: replacing a numeric literal that an expectation reaches (through generic calls by checking mode, record literals, constructors, closure operands) with true yields exactly one diagnostic, on that literal; replacing any leaf with an error node yields none. |
| Interface resolution terminates. | impl<T: Tr> Tr for T and an impl whose where clause needs ever-larger types are budget errors (Limit::TraitDepth), not hangs; supertrait cycles, cyclic generic aliases and defaults, and cyclic associated types terminate (the last two on a 1 MiB stack). Random HIR with generics, interfaces, impls, dyn, impl Trait, unions, and the v3 forms checks without panicking under five profiles. |
| Shared type structure is never expanded (type-lang's ISSUES M39). | Types are hash-consed terms in a union-find store. Unifying two Pair(v, v) doubling chains is linear: step counts are compared at 2,000 and 4,000 levels, and 50,000 levels check in a test. |
| Work is linear in the program. | Step counts at 2,000 and 20,000 functions differ by the size factor; so do 10,000 and 20,000 nested generic calls, and 2,000 and 4,000 interface implementations each called once. Deep input is checked on an explicit stack: tests cover 100,000-deep expressions, 50,000 nested blocks and ifs, 30,000-deep types, generic arguments, and patterns, 20,000-long alias chains, and 5,000-deep inheritance. |
Installation
[]
= "0.3"
Without the standard library:
[]
= { = "0.3", = false }
Quick start
use ;
use Interner;
use ;
let mut names = new;
let mut b = new;
// fn main() { let x = 1 + true; }
let one = b.int;
let yes = b.lit;
let sum = b.op;
let x = b.new_binder;
let pat = b.bind;
let stmt = b.let_stmt;
let body = b.block;
let main = b.func;
let root = b.module;
let hir = b.finish?;
// Static: one diagnostic, at `true`; `x` is the error type, so nothing
// that uses it is reported again.
let typed = check.unwrap;
let d = typed.diagnostics;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
// Dynamic: no static errors; every value is `any`.
let typed = check.unwrap;
assert!;
assert_eq!;
# Ok::
Profiles start from a preset and adjust toggles:
use ;
let kraken_like = static_inferred
.with_records
.with_subtyping
.with_string_add;
assert!;
let iron_like = static_inferred.with_mono;
assert!;
A generic function, its instantiation, and the plan:
use ;
use Interner;
use ;
let mut names = new;
let mut b = new;
// fn id<T>(x: T) -> T { x } fn main() { let y = id(true); }
let t = b.new_binder;
let mut tp = ;
let = ;
let x = b.new_binder;
let pat = b.bind;
let param = b.param;
let body = ;
let generics = Generics ;
let params = b.list;
let id = b.item;
let def = b.def;
let path = b.resolved_path;
let callee = b.expr;
let yes = b.lit;
let call = b.call;
let y = b.new_binder;
let ypat = b.bind;
let stmt = b.let_stmt;
let main_body = b.block;
let main = b.func;
let root = b.module;
let hir = b.finish?;
let typed = check.unwrap;
assert!;
assert_eq!;
let instance = typed.mono_plan.instances_of.next.unwrap;
assert_eq!;
# Ok::
Host declarations go through Checker:
use ;
use Interner;
use ;
let mut names = new;
let print = names.intern;
let mut b = new;
// fn main() { print("hi") } -- `print` is bound by the host
let path = b.resolved_path;
let callee = b.expr;
let hi = b.str_lit;
let call = b.call;
let stmt = b.expr_stmt;
let body = b.block;
let main = b.func;
let root = b.module;
let hir = b.finish?;
let mut checker = new;
let print_ty = checker.types_mut.func;
checker.declare_extern;
let typed = checker.check.unwrap;
assert!;
# Ok::
Runnable programs: cargo run --example quickstart, cargo run --example host, cargo run --example generics.
Performance
cargo bench --bench bench, release profile, Windows x86_64, 0.3.0. Library only: the HIR is built before timing starts. Measured on a machine shared with concurrent builds, so treat these as upper bounds and re-measure on an idle machine before quoting them. The generic programs call a generic function, a method of a generic impl, a bounded generic function on a nested generic record (resolving an interface method through a bounded generic impl), and a generic function with a closure whose signature is inferred, in every function of about 50 nodes.
| Benchmark | Time | Throughput |
|---|---|---|
static-explicit, 100k HIR nodes |
9.7–10.5 ms | 9.2–10.0 M nodes/s |
static-explicit, 1M HIR nodes |
131–137 ms | 7.1–7.4 M nodes/s |
static-inferred, same 100k program |
10.5–11.7 ms | 8.3–9.2 M nodes/s |
static-inferred, same 1M program |
132–145 ms | 6.7–7.3 M nodes/s |
static-inferred, generic program, 100k nodes |
35–37 ms | 2.7–2.9 M nodes/s |
static-inferred, generic program, 1M nodes |
332–348 ms | 2.9–3.1 M nodes/s |
dynamic, 100k HIR nodes |
3.0–3.2 ms | 31–32 M nodes/s |
dynamic, 1M HIR nodes |
41–46 ms | 21–24 M nodes/s |
| Doubling chain, 100k levels (1.4M nodes) | 143–149 ms | 9.4–9.8 M nodes/s |
Platforms
Linux, macOS, and Windows. The crate uses no operating-system facilities: a program checks the same way, with the same type ids and diagnostics, on every platform.
Contributing
See REPS.md for the engineering standards every change is held to, dev/DIRECTIVES.md for the definition of done, and dev/ROADMAP.md for the plan. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.