Chapter 4

Type System

PEGO is statically typed. Types describe the values that rules produce (see Nodes and Values) and the shape of the values that actions build. This chapter defines the types, how they are declared, their names and when a value of one type may be used where another is expected. How the type of an expression is determined, and the errors that the checker reports, are defined in Type Checking. Type errors are reported when the grammar is compiled, with the position of the offending construct.

#Built-In Types

The built-in types are named by these reserved names:

Other types are formed from types T, U, ... by these forms, or named by Type Declaration Statements:

Every value has a static type. The value of a rule, the result of an action, an element of a tuple or list and a field of a struct are nodes, tuples, lists, structs, int, string and bool values, errors or nil; a function is not a value. Variables hold int, string and bool values. node[_] is a node whose value is not known statically: it is the last resort, and a precise node[T] is preferred wherever the value is known.

A Type Expression is written with the following syntax. [] and * apply to the type that follows, & forms a meet and binds tighter than |, which forms a join, parentheses with commas form a tuple, and parentheses without a comma group.

type Example = {
    Items  []Item                       // a list
    Maybe  *Item                        // an Item or nil
    Either Item | Other                 // a join
    Many   [](Item | Other)
    Count  int
    Pair   (node[string], node[string]) // a tuple
    Call   node[(Name, []Arg)]          // the node of a sequence
    Digits node[[]node[string]]         // the node of a repetition
}

type LongJoin ~ (
    Item
    | Other
)

Parentheses group a Type Expression and allow it to continue across physical newlines. The source AST retains an explicit parenthesized type as a source-only TypeGroup node implementing TypeExpr; compilation and generation lower the wrapper transparently, so grouping does not change type meaning. See Parenthesized Groups in the Public AST for source metadata, JSON and formatter behavior. Outside such a group, a Type Expression follows the normal hard newline Declaration Statement boundary.

#Node Types

node[T] is the type of a node whose value, .Value, has type T, for any value type T. A node also has its input range .Start and .End. The nodes that Rule Expressions produce have these types:

So "(" items:(item ("," item)*) ")" has a value of type node[(node[string], node[(item, node[[]node[(node[string], item)]])], node[string])], where item stands for the type of the rule item: a captured group is one element, while the elements of a group that is not captured are elements of the enclosing sequence (see Sequences). node[T] can be written for any T. The value of a node that a Rule Expression produces is a string, a tuple or a list, so a cast to a type such as node[int] or node[Item] admits no node.

Diagnostics and RuleType show the captures of a node beside its value, as in node[(node[string], item), {"items": 1}], which locates the capture items at element 1 of the tuple. A node type written in a grammar has no captures; a node with captures is assignable to it when their values are.

node takes exactly one type argument: a bare node is an error ("node takes a type argument"), and node[A, B] is the error "node takes one type argument, got 2". The type argument follows node directly, without a space. No other type takes type arguments.

#Tuple Types

A tuple type is written in parentheses with commas: () is the unit type, (T,) has one element and (T, U) two; a trailing comma is optional after two or more elements. Parentheses around a single type without a comma group it. The value of a sequence node is a tuple, so x.Value of an x of type node[(A, B)] has type (A, B) and x.Value[0] type A. Tuple types may be used wherever a type may: in fields, aliases, rule types, casts, list constructors and type arguments.

#Reserved Forms

These forms are reserved: they parse, format and convert to JSON, but do not compile, also when types are otherwise not checked.

• An unnamed struct type is written with the braces and fields of a struct definition, as in type T ~ { Key node[string]; Value node[string] } or a field of type { Line int }. It is the error "unnamed struct types are not supported yet"; type T = {...} defines a struct type.

#Top, Bottom, Join and Meet

_ is the top type: every value is a _, and _ | T is _. A value of type _ is assignable only to _; a cast such as x.(T) checks it at run time and narrows it. No type is written any: the name is not a type, and the compiler asks for _. _|_ is the bottom type, which has no values: _|_ | T is T, and []_|_ and *_|_ are _|_. A struct field, a rule, a list element or a cast whose type resolves to _|_ is an error, also when types are otherwise not checked.

T | U is the join of T and U: its values are the values of either (see Join Types). The type of a choice is the join of the types of its alternatives.

T & U is the meet of T and U, the largest type assignable to both: the one assignable to the other, []V & []W is [](V & W), node[V] & node[W] is node[V & W], and for joins and optional types it is the join of the meets of their members. A meet of unrelated types is _|_. So (node[string] | int) & node[_] is node[string], and int & string is an error where a location has that type.

For a named node type N, (N | int) & node[_] is N, and N & M is _|_ for a distinct named node type M. For a struct type Num, (Num | int) & node[_] is _|_, since a struct is not a node.

#Node Type Names

The values that Rule Expressions produce have the shapes defined in Nodes and Values. Node.Type(), the type member of the JSON form and generated code name the nodes that are not structs by their kind:

The kind names in the first column are names of node kinds, not types: diagnostics name these values by the types in the third column, which are as precise as the expression that produced the value. missing is a kind of error: a value of type missing is assignable to error.

A named node type N (see Named Node Types) is not a kind and has no row here. A node converted to N reports the name N in place of its underlying kind, in Node.Type(), in the type member of the JSON form and in generated code.

#Names

User-defined type names and field names MUST begin with an uppercase ASCII letter. Identifiers that begin with a lowercase ASCII letter are reserved for the built-in types (int, string, bool, node[T], error, missing), and _ and _|_ name the top and bottom types. Each type name MUST be defined at most once, and types and rules have separate namespaces (see Names).

#Type Declaration Statements

A Type Declaration Statement type ... declares a type name. Type Declaration Statements and Rule Declaration Statements are the Declaration Statements of a grammar file. A Type Declaration Statement is one of two distinct declarations:

#Type Definitions

A Type Definition type T = S defines a new type T from the type specification S. S is a struct type or a node type node[U], with U any type, including _ and T itself; type T = node[U] defines a named node type. Any other right-hand side is an error, and an alias is written type T ~ U.

#Struct Types

A struct type is a type of values with named fields. A struct is a value that an action builds, not a node of the parse, so a struct type is not assignable to node[_]. Fields are separated by newlines or semicolons. Field names MUST be unique within a struct. Constructor fields and function arguments remain comma-separated.

type MyNode = {
    Field1 SomeType
    Field2 AnotherType
}
type Pair = { Key node[string]; Value node[string] }

A value of a struct type is created with a constructor such as T{Field: value} in an action.

[]T{value, ...} constructs a list value with explicit element Type T, including an empty list. Every element must have a known static type assignable to T; nil requires an optional element type, and nested lists are checked recursively, so []int{1, 2} and [](node[string], Item){} are list values. Constructor fields and arguments use commas.

#Named Node Types

A Type Definition type N = node[U] defines a named node type N whose underlying type is node[U]. Its values are nodes whose value has type U, and each carries the name N at run time. U may be any type, including _, as in type N = node[_], and N itself. A named node type is not an alias: it is distinct from node[U] and from every other named node type, even one with the same underlying type. U may refer to N or to other types, as in a recursive definition:

type Num = node[int]
type Ident = node[string]
type Tree = node[[]Tree]

Assignability to and from a named node type N:

• N is assignable to N, to node[U] whenever the underlying node[W] of N has W assignable to U, and to node[_]. A join whose members are all assignable to a location is assignable to it, as for any join.
• Nothing else converts implicitly to N: a node[U], a _, or a value of another named node type M is not assignable to N. Two distinct named node types never meet implicitly.
• A rule converts its value only when its declared Type is exactly N, also through aliases. A declared join, even one of named node types, does not convert: its value is checked by assignability. An Operators Rule declared with exactly N converts the value of every operator, as described there.

A value becomes a value of N by a conversion, which has two forms:

• a constructor N{x} with exactly one positional argument x;
• a rule whose declared Type is exactly N (also through aliases) converts the value that the rule produces, as in rule a Num = "a";
• an Operators Rule whose declared Type is exactly N converts the value of each prefix, infix and postfix operator it applies.

The conversion applies when every alternative of the static type of x (or of the rule's value) is a node, named or unnamed, whose underlying type is assignable to the underlying type of N. So a value of type M, whose underlying type fits, converts to N. An Operators Rule declared with exactly N converts the value of each operator, not the values of its operands, by the same rule. The following are rejected at compile time with cannot convert X to N (for N{x}) or rule r produces X, which cannot be converted to N (for a rule): _, node[_], error, nil and the scalar types. Cast first, as in $x.(node[string]).

A conversion keeps the range and the content of the node, and the converted node has no rule name. Its Node.Type() and the type member of its JSON form report N.

Constructor arity: a named node type takes exactly one positional argument, so N{x, y} and N{Field: x} are errors. A struct type's constructor names its fields, so a positional argument to a struct type is an error ("a struct constructor names its fields"). Mixing positional and named arguments in one constructor is a syntax error.

A named node type has the members .Start, .End and .Value, and len and text accept it, as for its underlying node[U]. Its .Value has type U.

#Type Aliases

A Type Alias type T ~ U declares T as another name for the type U. With |, the right-hand side is a join type, whose values are the values of any of its members, much like an interface type in Go.

type Node ~ Expression | Statement | Declaration
type Entry ~ (node[string], Value)
type Words ~ node[[]node[string]]

A type alias MUST NOT refer to itself, directly or indirectly. Joins are normalized: nested joins are flattened and duplicate members are removed (so T | T is T), and a join with an optional member is optional (A | *B is *(A | B)).

#Join Types

A join type A | B is written on the right-hand side of an alias or wherever a Type Expression is expected. An alias that resolves to a single struct type preserves that type's identity. A constructor accepts aliases of struct types and produces a node of the underlying struct type. This also applies to joins normalized to a single type, such as T | T.

#Assignability

A value of type V is assignable to a location of type T (a struct field, the declared type of a rule, and so on) if any of the following holds:

• V and T are the same type.
• T is _, or V is _|_.
• V is a join type and every member of V is assignable to T.
• T is a join type and V is assignable to one of its members.
• T is *U, and V is nil, or V is *W with W assignable to U, or V is assignable to U.
• T is node[_] and V is node[W] for any W: every node is a node[_].
• T is node[U] and V is node[W] with W assignable to U, whatever captures the node has.
• V is a named node type N with underlying node[W], and T is node[U] with W assignable to U, whatever captures the node has.
• T is a named node type N and V is any other type except N itself: not assignable; a conversion is required (see Named Node Types).
• V and T are distinct named node types: not assignable.
• T is []U and V is []W with W assignable to U.
• T is (U1, ..., Un) and V is (W1, ..., Wn), with the same number of elements and each Wi assignable to Ui.
• T is error and V is missing.

An error value from error recovery is assignable only to a type that admits error, such as T | error. A struct is not a node, and a node is not a tuple or a list: node[(A, B)] is not assignable to (A, B), whose values are the values of the node.

A value of type *T is not assignable to a location of type T, and accessing a field of a value that may be nil is an error. A value of type _ is assignable only to _.