Chapter 1

The Abstract Machine

The abstract machine is what every runtime of SyntaxIR hosts: the engine's backends and every generated parser. The Exec dialect of Code IR declares it: the features that a function can be specialized for, the abstract state of a parse, as state components and registers, and the handle types, in the declarations that The Module describes. The operations are in Operations and Values, and the functions over them are in Functions. The state is abstract: a contract talks about it, and a target chooses how to represent it. The types of values are those of The Module.

Features

A feature is a boolean constant of a build that a function can be specialized for (see Passes). An operation that belongs to features exists only in builds that have all of them.

Feature The build
budget Has budget controls: compute and memory limits, the input limit and cancellation
document Can parse a Document, reusing the results of an earlier parse after edits
observe Can observe a parse: tracing and profiling
missing Has missing-token insertion
stream Can parse a stream, delivering the elements of a #stream repetition as they complete
typed Makes typed values, as a typed parser does, instead of nodes

State

Components

A state component is a part of the abstract state that only the operations declaring it may write. The abstract machine has the following components.

Component Holds
memo The memo table: results of rule calls by key. A key is a rule, a position, a binding level and the values of the rule's variables.
seen The record of deferred memoization: which rules were called at which positions, and per rule the counts that decide when it is memoized eagerly. It is created with the number of rules whose memoization is deferred.
budget The work budget of the parse: the units charged so far and the limit, zero for none.
depth The nesting depth of rule calls and its limit.
env The variable environment: one current value for each declared variable, in a slot that the grammar fixes. An environment is persistent: a binding makes a new one and changes none that a backtracking point holds. Values handles stand for the values of a rule's variables, compared by the host's value equality.
host The host: values and nodes, which the abstract machine passes on without reading.
recovered The list of errors recovered so far in the parse.
rules The rules of the grammar: their descriptors and bodies.
expected The expectation record: the expectations at the farthest position.
call The call bookkeeping of the target outside the call protocol: the tracked path of Documents and observation.
observe The observation of a parse.
growth The left-recursion growths in progress with their seeds, the frames that record what the calls in their contexts depend on, and the tables of the results kept in each context (the dependency memo).
window The window of a stream parse: the input read and kept, the callback that receives the elements of the #stream repetition, the recovered errors delivered so far, and the memory that the delivered elements held.
runs The repetition runs of a Document: for each repetition of the last parse that a parse may resume, the positions, the examined input, the value and the expectations of its elements.
suspended The calls whose rule body runs between the begin and the end of the split call protocol, each with the state that its begin saved for its end in a record that its caller holds.
gathered The elements gathered for the lists and tuples that action expressions make: a stack, on which act.push and act.pushAll push, from which a list or a tuple takes its elements when it is made, and from which action.dropKids drops the elements of an action expression that the parser abandons.
made The values that action expressions and actions made: a list of the structs that act.made recorded, which the context of an action expression or an action marks when it is made. The struct that an action returns takes the range of the rule if the action recorded it, and what an action expression or an action recorded is forgotten when it ends.
frames The capture frames: the frame that captures write to, the slots of each frame and the trail of the writes that a reset undoes.
operators The bookkeeping of the Operators Rule loop: whether a candidate of the last longest match failed after a cut.
value The operations on the values of action expressions. They read and write no state.

Registers

A register is a scalar of the abstract state that functions read and assign directly.

Register Type Holds
pos int The position of the parse in the input.
silent int The depth of lookaheads, inside which expectations are not recorded.
cut bool The cut flag of the scope the parse entered last.

Handle Types

A handle type is a type of opaque values. Its component is the state component whose operations make its values. A handle type may be callable: its values are code that an application runs.

Handle type Component Stands for
Entry memo A memo entry: the result of a rule call with its outcome and end.
Values env The values of a rule's variables, as a memo key.
Value host The value of a rule's result: a node or a typed value.
Errs recovered The errors recovered in a rule call, kept with its memo entry.
Datum host A value that a variable holds or an action expression produces, which only the host reads.
Scope env A variable environment, which bindings replace and never change.
Rule rules A rule's descriptor.
FType value The type that a cast checks a value against.
NodeType value A named node type, to which a conversion converts a value.
Err recovered A syntax error that a recovery made.
Body rules The invocation of a rule's body that a generated call passes.
ExpMark expected The record that an isolation set aside.
ExpSet expected The expectations an isolation recorded, which a target may keep where the record grows next: valid as exp.setAt requires.
ExpID expected An expectation: the identifier of a description or message of the grammar.
ExpKept expected Expectations kept beyond the record, as a memo entry keeps them.
Ctx growth The context state of a memoized call: the growths of its rule's cycle at its position, their present set, and whether the call records its dependencies.
CtxResult growth A result that a context keeps (a seed, or the result of a call or a growth step that read a seed), or the last result of a growth.
Grow growth The state of the growth of a left-recursion leader.
EditLog memo The edits of a Document, in order.
Run runs A repetition run in progress in a Document parse.
Action host An action expression of a predicate or a binding, in the form the target holds: code that is applied to an Act, and returns a Datum and a Fail (Application).
CallState suspended The record of a suspended call, which its caller holds.
Frame frames A capture frame: the slots of the captures of a rule body or a line.
Mark frames A backtracking point: the position, the variable environment, the recovered errors and the length of the trail when it was taken.
Operators rules The prefix operators of an Operators Rule, or its other operators.
Operator rules An operator of an Operators Rule: its kind, binding power, associativity and line.
Line rules A line of an Operators Rule: an operand, or the expression of an operator.
Attempt operators A match of an operator: the operator, where it started and ended, its value, the frame of its captures, the environment after it, whether it cut, and the errors it recovered. The null attempt is no match.
LongestState suspended The record of a suspended longest match.
NudState suspended The record of the suspended start of an expression.
ExprState suspended The record of the suspended loop of an expression.
Seq value The elements of a list or a tuple, as seq.items returns them.
Fail value The failure of an action expression, as val.fail makes it: a value of the target that the caller reports.
Obj value A value that has members: a node, a list, a tuple or a struct, as node.of returns it.
Name value The name of a member: a string of the target.
Act value The context of the action expression being evaluated, in which a value is made.
Str value A string of the target that is not a value, as text returns it.
Elem value An element of a list or a tuple that an action expression makes, as a Seq holds it.

Quantities

The cost of an operation (see Costs) is bounded in terms of quantities. A quantity is an abstract measure of the state before the call, which the reference model of the component computes. The quantities are the following.

Quantity Measures
body The units that the evaluation of a rule's body that the call runs, and of the rule's action, charge, as the operations they call declare them.
covered The number of positions the memo covers from its floor: the slots that a target keeps per position pays for when it prunes them, moves the rest and drops the indexes of crowded positions.
deps The number of dependencies that the call passes to the enclosing evaluation or stores: those that the frame of the evaluation it ends recorded, and those stored with the results, steps and jumps it reuses, with the observations they lead to.
dropped The number of the entries above the mark of the call, which it drops: elements gathered (action.dropKids) or values made (action.dropCreated).
env_path The number of nodes on the path to a slot of a persistent vector of the variables with 16 children for each node: the levels above the leaves, and the leaf. It is the same for every slot.
env_rebind env_path when the value of the call differs from the one the slot holds, and 0 when they are equal: the nodes that a rebind copies.
error_parts The number of fragments of the text of a failure: the fixed pieces and the values between them, which a target that bounds the work assembles piece by piece, charging each.
errs The number of recovered errors that the call copies: those of its argument, or those recovered after its mark.
fields_read The number of fields of a value that a read of one of them scans.
key_bytes The sum of the lengths, in bytes of UTF-8, of the string values that the variables a rule reads hold: the bytes of the memo key of a call of the rule that budget.chargeKey pays for.
merge The units that the compositions over the expectation record (keep, mergeKept, mergeExpected, and the calls of expect they make) charge for the sets that the call keeps or merges.
move_edits The edits that the call replays to learn how far a node moves that another result moved since the entry's value was made: for each generation of the value's nodes other than the entry's, the edits since that generation. It is zero for a target that keeps no generations.
moved The size of the value of the entry that the call moves: for each distinct node in it, one and the number of its children and fields.
n The argument n of budget.charge.
pending_edits The number of edits since the entry under the call's key was stored or last found, counting an entry that memo.splice removed and a target may still hold: the edits that a target which applies them to an entry when it finds it has yet to apply.
present The work of naming the present set of the call's context when a leader in it has no bit in a word of bits: one for each growth of the context, and one more when no operation named that set since the first growth in progress began; 0 when every leader of the context has a bit. Which leaders of a cycle have a bit depends on the target, because the width of the word of bits does: 63 in the engine and 31 in the generated Go and TypeScript parsers and the model, so the quantity is the one of the target that runs.
pruned The number of memo entries stored before the call's position argument.
run For each step of the run of the growth that the call records as jumps (the steps since the last step that read another seed): one, one for each jump recorded before from its seed, and the expectations of its set when its farthest position is that of the steps after it.
segs The number of entries of the recovered-error list after the mark of the call, or for grow.adopt and grow.keepStep after the mark that the growth took when it began: errors that rec.push recorded and lists that rec.add recorded or rec.since put in their place.
seq_len The number of elements of the Seq argument of a primitive, which it copies.
set The number of expectations of the set that the call takes.
steps The number of memoized steps and jumps that the call takes.
stream_frames The number of capture frames that the scratch of the stream holds. A target may visit each twice: a scan for the frame in use, which may lie outside the scratch, and a clear of those after it.
stream_inactive The capacity of the trail and the inactive capacity of a target's value stack.
stream_scan The number of input elements that the call copies when it compacts the buffer, and of those it scans for line starts: every loaded element when the whole input is loaded from its first element and no table of its lines exists yet, otherwise those before its argument that no call scanned.
table The work of the call's lookups and stores in the context tables at its position: one for each lookup or store; one for each dependency set of the head it scans, each result under the values the set selects and each key value those results compare, a string counting two for each byte compared; and one for each jump it scans for a seed. A lookup that the outcome of an observation leads to counts again on each path through the observations that outcomes depend on.
tokens The number of missing tokens that the call removes (those inserted after its mark, or for rule.invokePlain those that its failed body inserted), copies (for opr.attemptMissing those inserted after its mark) or records again (those that the call of its entry or the match inserted).
value_bytes The number of bytes of the string operands of a primitive, which it reads and, for a concatenation, copies.
value_compare What comparing the value of the call with the one the slot holds inspects: two for each byte of two strings of the same length that are not the same bytes of the same memory, one for two such strings that are (the comparison reads none of them), and 0 for anything else.
vars The number of variables of the rule's memo key.
zero_parts The number of values of which a zero value is made, and, in a target that looks the field up among the declared ones, the declared fields it scans.