Chapter 9

Type Checking

Every rule has a type, and the checker verifies, when a grammar is compiled, that the values flowing through the grammar are of the types they are used as. This chapter defines the type of each Rule Expression, how the type of a rule without an explicit Type Expression is inferred, and the errors that the checker reports. The types themselves and the relation "assignable" are defined in the Type System.

#Rule Expression Types

A node type also records the captures made in the node, which x.$y reads; diagnostics show them after the value, as in node[(node[string], num), {"k": 1}].

#Types of Captures

The type of a capture name:a is the type of a. If the capture is made only in some alternatives of a choice, or inside an optional expression, it may not match, and its type is *T instead. A name captured more than once in a match has the join of the types of its captures, since the last capture that matches gives its value; when at least one of those captures is always made, the join is taken without nil, and otherwise each capture that may not be made contributes nil, so the type is optional, *T.

rule r = x:"a"? y:("b" / z:"c") // $x: *node[string], $y: node[string], $z: *node[string]
rule s = k:num "=" k:("x" "y")  // $k: num | node[(node[string], node[string])]

#Action Expression Types

Action Expressions in Value Actions and Predicate Actions have the following types.

The list functions treat nil as an empty list, which contributes no element Type: concat(nil, l) has the Type of concat(l), and filter(nil, f) is assignable to every list Type.

For []T{...}, the checker validates every element against the explicit element Type T. It reports non-assignable elements and elements whose Type is unknown, including unknown values nested in a typed list. An empty literal still has the declared []T Type. Nil is allowed only if T permits nil.

A struct field value whose Type is unknown (_, or a list with elements of such a Type) is reported when the field's Type is more specific: cannot use _ as Ident in field Name of Decl: the type of the value is not known; convert it with a cast, as in value.(Ident). The same holds for a value of Type _, which fits only _. A cast (see Casts) is the check that runs; see Values and Constructors. A value whose Type is known and assignable needs no check, and a constructor checks nothing when it runs.

Likewise, a rule value whose Type is unknown, from an action, a called rule or an Operators Rule line, is reported when the rule declares a Type it does not fit: rule term produces _, which is not assignable to Expr: the type of the value is not known; convert it with a cast, as in value.(Expr) (see Types and Errors). In an Operators Rule with a declared Type, the captures lhs and rhs have that Type.

Diagnostics print a type as written in a grammar: node[string] for a string node, node[(node[string], node[string])] for a tuple node of two string nodes, (node[string], node[string]) for its value and []node[string] for a list value. A reference to a rule without a declared type prints the rule's name, also where a recursive type refers to itself, as in []*expr. Run-time errors name a value the same way, writing _ for elements they do not examine: node[(_, _)] for a tuple node of two elements, node[[]_] for a list node and error for an error value.

A named node type is printed by its name, as Num, and cannot convert X to N names both types.

A cast tests a value as the value types describe it. node[T] takes a node whose value T takes, so node[string] takes a string node, node[(A, B)] a tuple node of two elements of types A and B, and node[[]A] a list node of elements of type A; node[_] takes every node; a tuple Type takes a tuple value of as many elements; a list Type takes a list value, such as one an action builds, and not the node of a repetition, whose list is its Value; []_ and []any take every list value; and an error value from recovery fits only a Type that admits error. A cast in a predicate that fails makes the predicate fail.

The argument of len and text MUST be a string or a node (possibly nil); the list arguments of foldl, foldr, map and concat MUST be lists, and an error value (from error recovery) counts as an empty list. A function ((acc, item) => ...) can appear only as an argument of foldl, foldr or map, and it has the number of parameters those functions require.

#Type Inference

The type of a rule without a declared type is inferred from its body, or from its action if it has one. Dependencies are inferred before their callers, so finite acyclic chains do not depend on definition order or an iteration cap. Recursive dependency groups are iterated until their types no longer change; join-member ordering does not count as a type change. Operators Rule operator actions also depend on their rule's type through the lhs and rhs values.

The implementation bounds changing recursive types conservatively. After an initial inferred result, further growth beyond 2,048 bytes in the written type or 50 increases in structural nesting depth widens that rule to a type that is not known for the rest of inference. Repeating non-stable type states widen only the rules that vary in the cycle. Stable peers, acyclic rules and stable oversized recursive types retain their types. These are resource limits, not proofs of infinite growth: a finite recursive type can also reach them. Declare recursive result types when precise checking is required.

rule num = [0-9]+ #atomic // node[string]
rule pair = k:num "=" v:num // node[(num, node[string], num), {"k": 0, "v": 2}]

The type of the accumulator of foldl and foldr is widened to the join of the type of the initial value and the type of the result of the function. The checker widens three times; if the result of the function still does not fit the accumulator, the call is a compile-time error (the accumulator type does not converge), and the result of the function must be cast.

#Checked Errors

The type checker reports the following errors:

• an undefined type, a type alias that refers to itself, and a duplicate field;
• a field that the struct type does not declare, in a struct constructor or a field access, and a field value that is not assignable to the type of the field;
• a typed-list element that is unknown or not assignable to its explicit element Type;
• a rule whose value is not assignable to its declared type;
• a constructor N{...} of a named node type with other than one positional argument, or a positional argument to a struct type;
• a value that cannot be converted to a named node type where a conversion is required (N{x} or a rule's declared type), including _, node[_], error, nil and scalars;
• a cast to a named node type that the static types rule out (see Casts).
• a field access on a value that may be nil;
• an operand of an operator or an argument of a built-in function with an invalid type;
• a variable that is read or bound without a declaration, a binding whose value is not assignable to the declared type of the variable, and a variable declaration with an unsupported type or an initial value of another type (see Variables).

A variable has the type its var declaration gives it, so a read of a variable is checked like any other value of that type: x + 1 and V{N: x} are checked when the grammar is compiled. A binding is checked only statically: it is a compile-time error unless the Type of the value is known to be assignable to the declared type of the variable, cannot use <value type> as <type> in the binding of variable <name>. A value whose Type the checker does not know, such as a rule value of unknown Type, is rejected too, with a hint to convert it explicitly: x := $d.(int). The cast is an ordinary cast (see Casts); when it fails, that is an evaluation error of the binding, which makes the predicate fail. Nothing is checked when a binding runs, so a variable always holds a value of its declared type.