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. |