Skip to main content

Errors

A type checker for an editor runs on code that's wrong most of the time. The checker is built to report each mistake once, at the place that caused it, and to keep checking the rest.

Where an error is reported​

Every constraint carries an Origin (in solve.rs):

  • body: the body it's in;
  • node: the expression or pattern that must have the expected type. The error is reported there;
  • reason: why that type is expected, so that the error can point at it as well.

The reasons are:

ReasonExampleWhat the error points at
Nonethe Bool of a conditionnothing more
Annotationlet x: i32 = ...the annotation
ReturnTypea function's declared return typethe return type
ConstTypea const's declared typethe type
Argumentthe indexth parameter of a callthe parameter
Fielda field of a struct literalthe field's declaration
SameAsthe other branch of an ifthe other expression

Several expressions that must have the same type, like the arms of a match, are checked against one type. The first arm gets the reason of the whole match, and the others SameAs the first, so the error at a wrong arm can point at the first arm as the reason for the expected type:

fn g(c: i32) = match c { 1 => 1, _ => "x" };
error at `"x"`: expected {integer}, found String

Pushing expectations down​

With plain Algorithm W, an error is found wherever unification happens to fail, which is often far from the mistake. The checker pushes expected types into expressions instead, the strategy of the "folklore" algorithm M [Lee & Yi 1998]. An if, a match or a block checks its branches and its tail against the expected type, rather than unifying its own type afterwards. So in

fn f(c: Bool) -> i32 = if c { 1 } else { "no" };

the error is reported at "no", with the return type as the reason, not at the whole if.

This only moves errors to better places. Which constraint fails first still depends on the order constraints are generated in, a bias every unification-based checker has. Constraint-based approaches that look at all the constraints before blaming one exist [Heeren 2005, Wand 1986], but they need the constraints of a whole group up front, which conflicts with solving equalities eagerly.

A mismatch is reported with the whole expected and found types of the constraint, resolved as far as inference got, rather than the innermost types that differ. "expected Option[i32], found Option[String]" says more than "expected i32, found String".

Keeping errors from cascading​

Once an error is reported, its consequences shouldn't be reported too.

  • The error type ⊥\bot unifies with everything (see Never and error). An unresolved name, an unknown field or an unsupported expression has type ⊥\bot, so nothing that uses it reports a mismatch.
  • set_error makes a variable ⊥\bot after an error about it. For example, the field variable of an unknown field.
  • A class constraint with ⊥\bot in it is considered solved, and calling a value of type ⊥\bot still infers the arguments, but reports nothing about the call.
  • A variable that only met an error isn't bound right away, because later constraints may still decide it. It becomes ⊥\bot at the end if nothing did (error_unknowns). That also keeps it from being generalized into a type parameter.
  • Errors are resolved before the unknown variables become ⊥\bot. Otherwise an error whose type contains such a variable would look like a consequence of another error.

How types are shown​

Ty::display shows types as Bolt code. Two details make errors readable:

  • Unknown types get names. TyNames names the inference and bound variables of a message a, b, ... in the order they appear, skipping names that type parameters in the same message already use. So "expected fn(a) -> T" and not "expected fn(?17) -> T".
  • Defaulted literals are numbers. resolve_error shows a literal whose type only came from defaulting as {integer} or {float} in a mismatch. In let a: f64 = 1; the error is "expected f64, found {integer}", since nobody wrote an i32. Other errors, like a missing instance, are about the default type, which is what the program will use.

Diagnostics​

Inference collects InferenceDiagnostics in the InferenceResult of each body. Some come from constraint generation, like an unresolved name or a wrong number of arguments. Others are the TypeErrors of the solver, and others still are LowerDiagnostics from type annotations in the body. The boltlang-ide-diagnostics crate turns all of them into diagnostics with a code, a range and labels, for the CLI and the language server.

Errors in the files a file uses​

A file's diagnostics are about the file itself. The files it uses, through its prelude and its imports (files_used_by), have their own, and what's in a file with errors can't be relied on: a program over a broken prelude could fail when it runs in ways the checker rules out. So they're shown once, where they are:

  • The CLI adds one error (E0112) to the diagnostics of the file it checks, runs or builds for each file it uses that has errors (dependency_diagnostics). It's at the import that brings the file in, or at the start of the file for the prelude's, and its label is at the first error of the broken file:

    [E0112] Error: `std/__prelude__/vec.bolt`, which this file uses through the prelude, has 2 errors; fix them first

    So bolt run and bolt build stop, and bolt check fails. A file that bolt check is given too isn't counted twice. bolt run --no-check runs anyway. The tests in tests/run fail the same way.

  • The language server doesn't repeat them in every document. It answers workspace/diagnostic with the diagnostics of the files the open documents use that aren't open, so that the editor lists them where they are without opening them, and clears a file once no open document uses it. For an editor that doesn't ask, it shows one warning with window/showMessage when such a file gets errors, which is given again only once they're fixed.

References​

  • O. Lee and K. Yi. Proofs about a Folklore Let-Polymorphic Type Inference Algorithm. TOPLAS 20(4), 1998.
  • B. Heeren. Top Quality Type Error Messages. PhD thesis, Utrecht University, 2005.
  • M. Wand. Finding the Source of Type Errors. POPL 1986.