typeck-lang 0.3.0

Profile-driven type checking over HIR: dynamic, gradual, static (generics, traits, inference), and Hindley-Milner from one checker.
Documentation

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), and let x = null typed 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; impl blocks, generic ones included; interface methods resolved through bounds, dyn types, and implementations, with automatic receiver borrowing as a profile toggle; impl Trait parameters 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 match misses 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 for let from 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 (promote is rejected on statically typed results); calls with named, default, variadic, and spread arguments; fields and methods through impl blocks, classes, and base classes; if, match, loops, labelled blocks, closures, async/await/spawn, generators, try/catch with type tests, casts, and intrinsics.
  • dynamic (Python, Lua, Mox): every value is any; 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; Checker takes 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

[dependencies]

typeck-lang = "0.3"

Without the standard library:

[dependencies]

typeck-lang = { version = "0.3", default-features = false }

Quick start

use hir_lang::{Builder, Lit, Name, NodeRef, OpKind};
use intern_lang::Interner;
use typeck_lang::{check, Profile, TypeId};

let mut names = Interner::new();
let mut b = Builder::new();
// fn main() { let x = 1 + true; }
let one = b.int(1);
let yes = b.lit(Lit::Bool(true));
let sum = b.op(OpKind::Add, &[one, yes]);
let x = b.new_binder(Name::new(names.intern("x")), hir_lang::BinderKind::Local);
let pat = b.bind(x);
let stmt = b.let_stmt(pat, Some(sum));
let body = b.block(&[stmt], None);
let main = b.func(Name::new(names.intern("main")), &[], body);
let root = b.module(None, &[main]);
let hir = b.finish(root)?;

// Static: one diagnostic, at `true`; `x` is the error type, so nothing
// that uses it is reported again.
let typed = check(&hir, &Profile::static_explicit()).unwrap();
let d = typed.diagnostics()[0];
assert_eq!(d.node, NodeRef::Expr(yes));
assert_eq!(d.kind.code(), "T0018");
assert_eq!(typed.message(&d, &names), "`add` is not defined for `bool`");
assert_eq!(typed.binder(x), Some(TypeId::ERROR));

// Dynamic: no static errors; every value is `any`.
let typed = check(&hir, &Profile::dynamic()).unwrap();
assert!(typed.is_ok());
assert_eq!(typed.binder(x), Some(TypeId::ANY));
# Ok::<(), hir_lang::HirError>(())

Profiles start from a preset and adjust toggles:

use typeck_lang::{MonoPolicy, Profile, RecordTyping};

let kraken_like = Profile::static_inferred()
    .with_records(RecordTyping::Nominal)
    .with_subtyping(true)
    .with_string_add(true);
assert!(kraken_like.null_safety);
let iron_like = Profile::static_inferred().with_mono(MonoPolicy::Selective { max_nodes: 64 });
assert!(iron_like.method_autoref);

A generic function, its instantiation, and the plan:

use hir_lang::{Builder, Expr, FnDef, GenericParam, Generics, Item, ItemKind, Lit, Name, Ns, Param, ParamKind, Prim, Res, Ty};
use intern_lang::Interner;
use typeck_lang::{check, Profile, TypeId};

let mut names = Interner::new();
let mut b = Builder::new();
// fn id<T>(x: T) -> T { x }    fn main() { let y = id(true); }
let t = b.new_binder(Name::new(names.intern("T")), hir_lang::BinderKind::TypeParam);
let mut tp = |b: &mut Builder| {
    let p = b.resolved_path(Name::new(names.intern("T")), Ns::Type, Res::Local(t));
    b.ty(Ty::Path(p))
};
let (pt, rt) = (tp(&mut b), tp(&mut b));
let x = b.new_binder(Name::new(names.intern("x")), hir_lang::BinderKind::Param);
let pat = b.bind(x);
let param = b.param(Param { pat, ty: Some(pt), default: None, kind: ParamKind::Normal, by_ref: false });
let body = { let ux = b.use_binder(x); b.block(&[], Some(ux)) };
let generics = Generics { params: b.list(&[GenericParam::new(t)]), preds: hir_lang::List::EMPTY };
let params = b.list(&[param]);
let id = b.item(Item::new(
    Some(Name::new(names.intern("id"))),
    ItemKind::Fn(FnDef { generics, params, ret: Some(rt), body: Some(body), ..FnDef::default() }),
));
let def = b.def(hir_lang::Def::Item(id));
let path = b.resolved_path(Name::new(names.intern("id")), Ns::Value, Res::Def(def));
let callee = b.expr(Expr::Path(path));
let yes = b.lit(Lit::Bool(true));
let call = b.call(callee, &[yes]);
let y = b.new_binder(Name::new(names.intern("y")), hir_lang::BinderKind::Local);
let ypat = b.bind(y);
let stmt = b.let_stmt(ypat, Some(call));
let main_body = b.block(&[stmt], None);
let main = b.func(Name::new(names.intern("main")), &[], main_body);
let root = b.module(None, &[id, main]);
let hir = b.finish(root)?;

let typed = check(&hir, &Profile::static_inferred()).unwrap();
assert!(typed.is_ok());
assert_eq!(typed.binder(y), Some(TypeId::prim(Prim::Bool)));
let instance = typed.mono_plan().instances_of(id).next().unwrap();
assert_eq!(instance.args, &[TypeId::prim(Prim::Bool)]);
# Ok::<(), hir_lang::HirError>(())

Host declarations go through Checker:

use hir_lang::{Builder, Effects, Expr, Name, Ns, Prim, Res};
use intern_lang::Interner;
use typeck_lang::{Checker, Profile, TypeId};

let mut names = Interner::new();
let print = names.intern("print");
let mut b = Builder::new();
// fn main() { print("hi") }  -- `print` is bound by the host
let path = b.resolved_path(Name::new(print), Ns::Value, Res::Extern(print));
let callee = b.expr(Expr::Path(path));
let hi = b.str_lit("hi");
let call = b.call(callee, &[hi]);
let stmt = b.expr_stmt(call);
let body = b.block(&[stmt], None);
let main = b.func(Name::new(names.intern("main")), &[], body);
let root = b.module(None, &[main]);
let hir = b.finish(root)?;

let mut checker = Checker::new(&hir, Profile::static_explicit());
let print_ty = checker.types_mut().func(&[TypeId::prim(Prim::Str)], TypeId::UNIT, Effects::NONE);
checker.declare_extern(print, print_ty);
let typed = checker.check().unwrap();
assert!(typed.is_ok());
# Ok::<(), hir_lang::HirError>(())

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.