Unification
The Unifier in unify.rs solves equalities by
binding inference variables. It's syntactic, first-order unification
[Robinson 1965], with a direction for the few places where a type can fit
where another is expected (Where a value is received),
and it knows nothing about where types come from. It returns a UnifyError, and the solver turns
that into a diagnostic with an origin.
The variable table
Variables are indices into a table, where each entry is either
Unbound(kind) or Bound(ty). A variable can be bound to another variable,
so the table is a union-find structure [Tarjan 1975],
which is the usual way to implement unification efficiently
[Huet 1976]:
shallow_resolvefollows bound variables until it reaches a type that isn't a bound variable. It's the find operation, without path compression.resolvereplaces every bound variable inside a type, recursively. It's used when a type has to be shown or stored, like in anInferenceResult.
The unifier never substitutes into types eagerly. A type stays as it was built, with variables in it, and is resolved when someone looks at it.
The algorithm
unify(a, b) first resolves both sides shallowly, then matches on them:
Applications of type parameters and variables, like F[A], are unified by
their last arguments first; Kinds explains how.
Equalities are unified the moment they're emitted, so the order of constraint generation decides which mismatch is reported when a program has several. See Errors for how errors are attributed.
The occurs check
Binding when contains would make an
infinite type. In fn f(x) = f([x]);, x has type and the
recursive call needs . bind resolves fully and checks that isn't in
it. If it is, it returns UnifyError::Occurs, which becomes an "infinite
type" error.
Numeric variables
Each variable has a VarKind, and binding respects it:
| Kind | Can be bound to |
|---|---|
General | Any type. |
Int | Integer types, like i32 or u8. |
Float | f32 and f64. |
Unifying two variables joins their kinds. General joined with Int gives
Int, but Int joined with Float is a mismatch. So in
fn inc(y) = y + 1;, the variable of y meets the Int variable of 1
and becomes an Int variable, which later defaults: inc has type
fn(i32) -> i32.
When a body is done, default_numeric_vars binds the Int and Float
variables that are still unbound to i32 and f64, and remembers which
variables were defaulted. Error messages use that to show a literal as
{integer} rather than i32: in let a: f64 = 1;, nobody wrote an i32.
These kinds are a small case of what the type class literature calls
defaulting; Haskell does the same with Num and Fractional
[Peyton Jones 2003].
Mutabilities
A mutability is a type of its own kind:
Ty::Mutability(Mut), Imm or ReadOnly, a variable of kind
VarKind::Mutability, a parameter, or the error type. Arrays, structs
and function types unify their mutabilities like any other argument, and
Mut only unifies with Mut. A mutability variable can only be bound to
a mutability, or to a parameter or bound variable that stands for one.
When a body is done, default_mutability_vars makes the mutability
variables that nothing decided Imm.
A mutability that a function's parameter doesn't write is decided with
the body, and one that nothing decides is generalized, so each use of the
function instantiates it with a new variable, and a caller can pass
either kind. In a function whose type comes from its class or impl, or
that has no body, it's a hidden parameter of the function instead: inside
the body a Ty::Param, which only unifies with itself. This table shows whether
two parameter types unify once their functions are instantiated, which
is how the checker finds overloads that a call could fit both of
(overlap.rs):
| A | B | Unify? |
|---|---|---|
mut Vec[i32] | imm Vec[i32] | no: Mut and Imm don't unify |
Vec[i32], with a hidden mutability | mut Vec[i32] | yes: the hidden mutability's variable becomes Mut |
Vec[T], with T a type parameter | Vec[i32] | yes: T's variable becomes i32 |
(Vec[i32], String) | (Vec[i32], i32) | no: String and i32 don't unify |
Where a value is received
unify(a, b) has a direction: a receives what b gives, like a
parameter receiving an argument. Inside the parameters of a function type
it's the other way round, which flipped says (Unifier::reversed). Most
types are the same either way. Three rules aren't:
ro: a place that receivesrotakes any mutability, soro [i32]takes amut [i32]and animm [i32]. What amutarray, struct or tuple holds is unified both ways (share_if_mut), since it's written as well as read.- A struct's or enum's arguments are unified as its variance says
(
variance.rs): as they are, the other way round, or both ways. In a struct that'smut, or whose mutability isn't known yet, they're always unified both ways, as what's in amutarray. - Effects: when the rows of two function types are both known, the
given one only has to fit in the received one (
Ty::row_fit), so a function that does less fits where one that does more is expected. When either is still a variable, they're made the same row.
Whether impls overlap (overlap.rs) is about equality, so it unifies with
Unifier::new(), where a struct's arguments are always unified both ways.
Never and error
Two types are special:
! fits everywhere. A diverging expression has type !, and Bolt has no
subtyping or coercions, so the unifier accepts ! against any type. It
doesn't bind a variable to !. In if c { return 1 } else { 2 }, the
branches have types ! and , and the if gets the
integer type, not !.
The error type fits everywhere, so that an error doesn't cause others. Here too the variable isn't bound, because later constraints may still decide it:
match s { Nope(x) => x, _ => 0.0 }
If Nope doesn't exist, the first arm has type , but the second arm
still makes the match a float. Instead of binding, the unifier records in
met_error that the variable met an error. When inference is done,
error_unknowns binds the variables that met an error and are still
unknown to . Otherwise a variable that's only unknown because of an
error would be generalized: fn h() = 1..2 would get the type
forall a. fn() -> a, which is wrong and causes confusing errors at its
callers.
Tests
The unit tests at the bottom of unify.rs cover binding, mismatches, the
occurs check, numeric kinds and the special types.
References
- J. A. Robinson. A Machine-Oriented Logic Based on the Resolution Principle. Journal of the ACM 12(1), 1965.
- R. Tarjan. Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM 22(2), 1975.
- G. Huet. Résolution d'équations dans des langages d'ordre 1, 2, ..., ω. PhD thesis, Université Paris VII, 1976.
- S. Peyton Jones (editor). Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003. Section 4.3.4, "Ambiguous Types, and Defaults for Overloaded Numeric Operations".