Types and schemes
Types
The checker's types are the Ty enum in ty.rs. Unlike the TypeRefs of
hir-def, which are types as written, a Ty points at definitions: a struct
is its StructId, not its name.
A few of these need explaining.
Inference variables are TyVar(u32), indices into the unifier's table
(see Unification). Each also has a VarKind:
Generalvariables can become any type.IntandFloatvariables come from number literals without a suffix, like1or2.5. They can only become integer or float types, and they default toi32andf64when nothing else decides them.
VarKinds have nothing to do with the kinds of types.
This replaces Haskell's Num and Fractional classes and their defaulting
rules with something much simpler. There's no class for numbers, so
arithmetic operators only require both sides to have the same type.
Type parameters and bound variables are both "type variables" in the literature, but the checker keeps them apart:
Paramis a parameter someone declared, like theToffn id[T](x: T) -> T. Inside the item that declares it, it's rigid: it stands for an unknown type and only equals itself. In the literature this is a skolem constant. When the item is used, its parameters are replaced by fresh inference variables.Bound(i)is a variable that generalization introduced in the scheme of a function without a complete signature. These are thea,b, ... inforall a. fn(a) -> a.
Never, written !, is the type of return, break, continue, a
loop that's never left, and a match without arms. It fits wherever any
type is expected. Bolt has no subtyping, so the checker handles this in
unification: ! unifies with every type without binding anything. See
Unification.
The error type is what a type becomes once an error has been reported about it, like an unresolved name. It also unifies with everything, so that one error doesn't cause more. See Errors.
There's also Number, which only appears in diagnostics. It shows a literal
that got its type from defaulting as {integer} or {float}.
Lowering written types
lower.rs turns TypeRefs into Tys with a TyLoweringContext, which
resolves paths with hir-def's Resolver. Signatures are lowered by their
own queries, so they're computed once and shared:
| Query | Result |
|---|---|
fn_sig | The parameter and return types of a function. Each is None where no type is written. |
struct_field_types, enum_field_types | Field types in terms of the type's own parameters. |
generic_predicates | The class constraints of [T: Show] bounds and where clauses. For a class, these are its superclasses. |
impl_header | The instance an impl provides, like Show[Option[T]]. |
type_alias_ty | The type an alias stands for. A cycle is caught with Salsa's cycle recovery and reported as a recursive alias. |
const_ty | The declared type of a const. |
Type aliases are expanded during lowering by substituting their arguments, so later stages never see them. Lowering also checks the kind of every type, which includes that type constructors get the right number of arguments.
Type schemes
A function has a type scheme (Scheme in scheme.rs). It's a type with
quantified variables and the constraints that must hold wherever the
function is used:
A constraint is one of:
-
A class constraint (a
ClassConstraint): the types have an instance of class , like . These are the predicates of Jones's qualified types [Jones 1994]. -
A field constraint (a
FieldConstraint): values of type have a field of type . A function that uses a field of a value whose type it doesn't decide keeps the constraint:fn norm(p) = p.x * p.x;norm: forall a b. a.x: b => fn(a) -> bnormthen works on any struct with a fieldx. This is close to the kinded record types of Ohori's polymorphic record calculus [Ohori 1995]. In GHC's terms, it's aHasField "x" a bconstraint.
Scheme stores the declared parameters and the number of bound
variables separately. Its display prints both after one
forall.
Instantiation
Using a function instantiates its scheme (Scheme::instantiate). Every
parameter and bound variable is replaced by a fresh inference variable, and
the constraints are added to the solver with those variables:
This is the only way polymorphism enters a body. Each use of id gets its
own copy of its type, so id(1) and id(True) don't interfere.
Tuples with names and packs
A tuple has positional fields, like (i32, Bool), or named ones, like
(x: i32, y: Bool), not both. The first is a Ty::Tuple, the second a
Ty::Record, with the named fields in the order of their names, so that
(x: 1, y: 2) and (y: 2, x: 1) have one type. () has no fields of
either kind, so it's both: the unit type. In an expression, *e spreads
the fields of a tuple with positional ones, and **e those of a tuple with
named ones.
A function can take any number of fields with a pack parameter: [*Ts]
stands for positional fields and [**R] for named ones, of the kinds
*Pack and **Pack. In a tuple type, a pack is a Ty::Spread, like the
*Ts of (T, *Ts) or the **R of (name: String, **R). At a use, a
pack parameter becomes a pack variable, which becomes a Ty::Tuple of the
types it stands for, or a Ty::Record of the named fields: a tuple whose
spread is solved has them spliced in when it's rebuilt.
Unifying two tuples with spreads (Unifier::unify_tuples):
- Positional fields are matched from the start and from the end, until
a spread. What's left on one side is what a single pack variable on the
other stands for:
(T, *Ts)with(i32, Bool, u8)makesTsthe(Bool, u8). Two spreads in the same places, like(*As, *Bs)on both sides, are matched pairwise. Anything else, like(*As, *Bs)with(i32, Bool), could be split in more than one way, and is a mismatch, so a pack must be alone where it's solved. - Named fields are matched by name. A named pack variable on one side takes the fields only the other side has. When both sides have one, each gets the other side's fields and a new variable for the rest, as in row rewriting (Rémy, Leijen).
A tuple with named fields and a named pack, like (id: i32, **R), needs
R not to give an id: instantiating a scheme adds a Lacks constraint
for that, which is checked once R is known.
What a body can do with a value whose type has a pack: pass it on, read a
positional field before the first spread or a named field, and match it
with ... Monomorphization knows each pack, so MIR reads a field after a
spread from the end (Ctor::TupleEnd) and a named one by its name
(Ctor::TupleNamed), which the code generator turns into indices. Spreading
such a value, like (**p, y: 1) in a generic body, type-checks but isn't
lowered yet (#405).
Parameters of functions
A function's parameters are positional, keyword-only, or rests:
fn push(xs: [T], /, x: T) // `xs` only by position
fn split(s: String, *, at: Char) // `at` only by name
fn print[*Ts](*args: *Ts, sep: String) // the other positional arguments
fn call[*Ts, **Ks](f: F, *args: *Ts, **opts: **Ks)
Before a /, parameters can only be passed by position, after a * or
*args only by name, and **opts comes last, so a positional pack is
never followed by positional parameters. In the body, args is the tuple (*Ts) and opts the tuple
(**Ks).
Ty::Fn holds a Params: the positional parameters, a positional pack,
the keyword-only ones in the order of their names, and a named pack, shown
as fn(String, *, at: Char) or fn(*Ts, sep: String, **Ks). A pack that's
solved is spliced in, so a function type has one form. Two functions with
only positional parameters unify parameter by parameter. Otherwise the
parameters unify as tuples (Params::as_tuple), so positions, names and
packs work as they do for tuples.
A call f(1, *xs, sep: ",", **opts) is checked the same way: its arguments
make a tuple, through the spread constraint when there are spreads, which
must be the parameters as a tuple. A name given twice is E0259. Neither
tuple is a value, so neither has a mutability (Ty::Unwritten), and what's
spread in the arguments isn't required to be at most anything.
Monomorphization lays the parameters out flat (MonoTy::Fn): the
positional ones, then those of the positional pack, then the keyword ones
together with those of the named pack, in the order of their names, whose
names it keeps. MIR passes a call's arguments in that order, after
evaluating them into temporaries in the order they're written. A function
with keyword parameters or rests binds its parameters from the flat ones
(bind_params in the code generator), building args and opts.
Names of positional parameters
A positional parameter can be passed by name too: f(y: 2, x: 1) for
fn f(x: i32, y: i32). The names are in the function's type, as
fn(x: i32, y: i32), and a function type can be written with them. Each
positional parameter in Params has a name slot in Params::names: a
Ty::ParamName, which is None for one without a name, like a pattern
that isn't a name, or a variable of kind VarKind::Name while it's
inferred. At runtime nothing changes: a name only decides a position, which
the checker and MIR find the same way (place_args), and monomorphization
drops the names.
Only a call by name checks a name (the reasons are in
Arguments and parameter names). A name in a function
type says how whoever holds a value of that type can call it by name, so
names never make unification fail, and instance matching ignores them. A
written function type renames the parameters of what it's given:
apply(f) for fn apply(k: fn(item: i32) -> i32) checks whatever f
calls its parameter, and inside apply, k(item: 1) uses apply's
names.
A slot stands for the set of names its parameter can be called by: one
name, none, or any, for a variable that nothing decided yet. When a type
variable is bound to a function type (Unifier::bind_freshened), its
slots become new variables. On the side that's expected, the given
function's slots flow into them (NameEdge), and when the unifier meets
two function types, the actual one's slots flow into the expected one's
too, the other way around inside parameters. A written slot doesn't
receive anything, which is the renaming. A variable's set is the
intersection of what flowed into it (Unifier::name_set), so the type of
if c { f } else { g } has the names that f and g share: with f(x, y) and g(x, z), it's fn(x: i32, i32). A variable on the other side,
like k in apply(k) for a k without an annotation, gets open slots.
A call with a named argument looks at what the callee's slots are now
(Unifier::slots_now). A name that no slot has takes the first open one
after the positional arguments, in the order the call writes them, and the
call claims the slot (Unifier::claim), along with the open slots that
flowed into it, so that what's given there can be called by that name. So
fn pick(c, f, g) = { let k = if c { f } else { g }; k(x: 1) } names the
parameters of both f and g x. A call by name of a function that isn't
known yet makes its arguments positional parameters, with open slots that
the call claims: fn r(k) = k(item: 2) has type fn(k: fn(item: i32) -> a) -> a. A slot that's claimed has one name, so k(x: 1); k(y: 1) is an
error. A function that flows into a claimed slot after the call must have
its name, or unifying it fails.
Names normally flow from what's read into what reads it: a pattern takes
the names of what it matches (Solver::equal_into). A place shares its
slots with what it denotes (Solver::equal_shared): a field access with
the field, and an associated type, like the Index.Item of xs[i], with
what the impl gives. What's in a mut array, struct or tuple shares its
slots on both sides when the two are unified (Unifier::share_if_mut),
since either side can write to it: after put(ks, |y: i32| y) for fn put[T](xs: mut [T], x: T), the elements of ks can't be called x
anymore.
Before generalizing, the solver settles the names
(Solver::settle_names): a claimed slot has its claim, one whose set is a
single name has that name, and every other slot has none.
Since a written type renames, copy(|dst, src| ...) for fn copy(f: fn(src: Path, dst: Path)) checks, and passes src to the lambda's dst.
So the unifier records each function type that it finds given for
another (Unifier::given_fns), in the case of two function types and when
a variable takes a function's shape, and the solver keeps where
(Solver::unify_at). Once the names are settled, it warns where a name of
the given function is the name of another position in the type it was
given for (TypeError::SwappedNames, W0005).
A parameter before a / has no name (ParamData::name is None), so
its type is the same as if the name were left out: fn f(x: i32, /, y: i32) has type fn(i32, y: i32). A function type has no / for that
reason, since leaving the names out says the same.
A lambda's parameters have the names of its patterns, whatever it's checked against. A method of a class impl can name its parameters otherwise than the class: calls through the class use the class's names.
Default values
A parameter can have a default, like fn f(a: i32, b: i32 = a * 2, *, c: i32 = 0). The defaults are part of the function's body (Body::defaults),
each in a scope that has the parameters before it, and they're checked
with the body, against their parameters' types, so fn g(x = 1) takes an
i32. A default is evaluated where the function is called, so what it
does, the function does: its effects are the function's. A positional
parameter without a default after one with a default is E0260, and a
default on a method of a class impl is E0261, since calls through the
class use the class's defaults, as they use its names.
Function types have no defaults (#408), so only a call that the checker
knows the function of can leave parameters out: a call by its name, a
method call, or one of a class method. ParamDefaults says which
parameters have one, and place_args passes over the positional ones
that no argument is for. The arguments are then checked against the
parameters that are left, and InferenceResult::defaults has, for the
call, the function and the declared parameters that get their defaults.
In MIR, each default is a body of its own (BodyOwner::Default), a
function of the parameters before it, after the lambdas in MirBodies. A
call evaluates its arguments into temporaries in the order they're
written, then calls the default of each parameter it leaves out, in the
order of the parameters, with the values of those before it, through an
ItemRef::Default. Its of is the type the call uses the function at,
which decides the instance of the default: InstanceDef::Default is
generic over what its function is, with the default's own type. A class
method's defaults work the same way, since its declaration has a scheme.
A default with a lambda or a handler in it isn't lowered yet.
What's left: lambdas with keyword parameters, and
passing a pack on, like f(*args) in a generic body.
References
- M. P. Jones. Qualified Types: Theory and Practice. Cambridge University Press, 1994.
- A. Ohori. A Polymorphic Record Calculus and Its Compilation. TOPLAS 17(6), 1995.