Chapter 5
Tracing and Profiling
A parse can report every rule call it makes to a caller-supplied function (tracing) and can accumulate the cost of each rule over many parses (profiling). Observation never changes the result of a parse. This chapter defines the engine API and the opt-in APIs of generated Go and TypeScript parsers.
Observation Options
The engine (package engine) and generated Go parsers select what a parse
reports with the same four parse options, which have the same meaning in both;
generated TypeScript parsers take them as fields of their parse options with
the same meaning
(Generated TypeScript Tracing and Profiling).
Generated parsers accept them only when generated with observability (see
Generated Go Batch Tracing).
| Option | Meaning |
|---|---|
WithTrace(f) |
Calls f with every event of the parse that the trace filter and the depth limit select |
WithProfile(prof) |
Adds every call of the parse to the Profile prof |
WithTraceFilter(rules...) |
Selects the calls of the named rules and the calls nested in them |
WithTraceMaxDepth(n) |
Selects the calls at most n deep; the start rule has depth 1 |
Several WithTrace options compose: each function receives every selected
event, a copy of its own, in the order of the options, and a function receives
an event only after the functions before it have returned; if one panics (in
TypeScript, throws), the parse ends with that panic and the functions after it
do not receive the event.
Several WithProfile
options compose too: each profile records the whole parse. A nil (in
TypeScript, null) function or profile is ignored.
Trace functions are callbacks of the caller, outside the budget. A cancellation of the parse's context that a trace function makes takes effect no later than the next observation of the context (Reservations and Interruptions). A parser with limit controls MAY observe the context earlier, including between two trace functions of the same event; the functions after that observation then do not receive the event.
WithTraceFilter and WithTraceMaxDepth select the events that the trace
functions receive; they apply to all of them. A call is selected by the filter
if its rule is one of the named rules or the call is nested in a selected call;
a skipped call (TraceSkipped) is selected in the same way, as if it were made
at its place. A name that is not a rule selects no call, and a filter with no
names selects every call. A call deeper than n is not selected; zero or a
negative n sets no limit. The enter and exit events of a call are both
selected or both not. If several WithTraceFilter or several WithTraceMaxDepth
options are given, the last of each applies. Neither option changes the parse,
the events' fields (Depth stays the depth in the whole parse) or what the
profiles record.
A Document keeps the options given when it is created as defaults for every
parse of the Document; the options given to one parse apply over those defaults
for that parse only. Trace functions and profiles given to a parse are added to
those of the defaults, so both receive the parse; a trace filter or depth limit
given to a parse replaces the default for that parse.
In Go, the trace filter and the depth limit of a parse are one
instrument.TraceSelection, whose Rules and MaxDepth the two options set; an
option replaces the selection rather than changing it. Two types of package
instrument serve the parsers that produce events, not their users: a parser gives
its events access to its state through an instrument.TraceSource
(TraceEvent.WithSource), which answers the line and column of a position, the
text of a range, and the failure and recovered errors of the current exit event;
and it records a profile through an instrument.ProfileRecorder
(Profile.Recorder), to which it passes every event of the parse in order
(Record, then Resume after the trace functions have handled it) and which it
closes when the parse returns (Close).
Engine Tracing
runtime.WithTrace(f) calls f at the start and at the end of every rule call of
the parse, in order, so that the events nest like the calls.
Tracing works with every backend, with Parse, ParsePrefix, recognition,
ParseStream and Document. The trace options of generated parsers are those of
their own package, with the same meaning
(Observation Options). The events are the TraceEvent
of the package instrument (syntaxir.dev/sxir/pkg/runtime/instrument), which every producer of events uses.
The engine reports the calls that its backend makes, as defined in
Reported Calls. It never reports TraceSkipped.
A TraceEvent has the following fields.
| Field | Meaning |
|---|---|
Kind |
TraceEnter, reported when a rule is called before the memo is consulted, or TraceExit, reported when the call returns |
Rule |
The name of the rule that is called |
Level |
The minimum binding level of the call: the number of levels looser than the one a level-restricted call level(e, name) names, which applies the operators of the named level and of the tighter ones, or 0 for a call without a level. A call restricted to the loosest level applies every level, as a call without a level does, so it is the same call, with Level 0, and shares its memo entries and growths |
Depth |
The nesting depth of the call; the start rule has depth 1 |
Pos |
The position at which the call starts, in the position unit |
Lookahead |
True if the call is made where failures record no expectations: inside a lookahead, or inside the skip expression of an Operators Rule, which is matched as in a lookahead. It has the same value on the call's exit |
An exit event also has the fields below.
| Field | Meaning |
|---|---|
Matched |
Whether the rule matched |
End |
The position after the match, or Pos if the rule failed |
Memo |
True if the result came from the memo table without evaluating the body |
Evals |
The number of times this call evaluated the rule body: 0 for a memo result, usually 1, and one more for each step that a left-recursive match grows. Bodies of nested calls are not included |
ReusedElements |
The number of repetition elements of a Document reused during this call, nested calls included. It measures resumption in this invocation, not work from the parse that built a memo result |
Examined |
The call's exact examined end, defined below |
Examined is the exact end h of the call's
examined range: one past the greatest slot that the
call, or a call within it, examined. Looking at a character to reject it counts,
and so does input examined inside a lookahead. It is at least the call's start
and its end, is one past the length of the input when the call tested the end of
the input, and never includes input examined by the caller before the call. A
memo hit reports the end stored with the result it reuses. A call that reuses a
growing left-recursive seed extends its end to the end stored with that seed, so
the Examined of a call depends on the seed it reuses as well as on its other
fields. The initial seed of a growth is a failure whose stored examined end is the
leader's start.
The operand of a prefix operator and the right operand of an infix operator are
parsed within the call of the Operators Rule that applies the operator, not by a
call of their own: they are not reported, and what they examine is part of the
Examined of that call.
A stream parse reads only the input that its calls and the
whole-input check examine. Let Needed(e) be the input
that a parse must have read to have examined the slots below e: in bytes, the
first e bytes, or the whole input and its end when e is one past its length; in
code points, for each slot below e, the bytes up to and including the one that
completes its character or makes it invalid, or the whole input and its end when
the input ends inside a valid prefix of a character, and for the end slot the
whole input and its end. Read from a reader that delivers one byte per read and
reports the end of the input only on a read after the last byte, a parse has read
Needed(Examined) of a call when the call's exit is reported, and when the parse
returns it has read exactly Needed(H), where H is the greater of the start
call's Examined and, when the start call matched and the parse requires the whole
input, its End plus one. A reader that delivers more in one read gives the parse
input beyond Needed(H), which is the buffering that
Streaming allows. The
whole-input check belongs to the parse, not to the start call, so the start call's
Examined does not include the slot that the check examines.
The methods LineCol(pos), Text(), Failure() and Recovered() read the
state of the parser and MUST be called only from the trace function, while it
handles the event. Text returns the input the call matched. Failure returns
the farthest failure recorded during the call as a *SyntaxError, or nil.
Recovered returns the errors that #recover recovered from during the call,
which Failure does not include. LineCol returns 0, 0 for a position in input
that a stream parse has discarded. The fields can be kept after the call.
Tracing does not change the result.
Reported Calls
Every producer of events, the engine with each backend and every generated
parser, reports the rule calls that it makes. A call that a producer does not
make because the next character cannot start the rule (first-character
dispatch, which Evaluations of Rules
limits) is not reported as a call; a generated parser MAY report it as
TraceSkipped. Producers do not skip the same calls, so the events of two
producers for the same parse, in the same position unit, agree on every call
that can match and MAY differ only in calls that cannot match: calls skipped by
dispatch, and calls that fail having examined no further than the character at
their position. On the calls that both make, every field of their events is
equal. The same holds for their profiles once the counts of those calls are
taken out. Document parses after an edit are the exception: the engine MAY
resume repetitions and reuse failed results of the previous parse, so the
producers report different calls. Of the calls that can match with the same
rule, position, level, depth, end and outcome, if both producers make any, both
make the same number; they pair one to one in the order they are made, and paired calls have
the same Examined. A producer can make such a call more
than once with different Examined, within the growth of a left-recursive
seed: Examined depends on the seed that the call reuses, which those fields
leave out.
Engine Profiling
runtime.WithProfile(prof) adds the cost of a parse to prof, an instrument.Profile,
which accumulates any number of parses of any producer. The profiled parse is traced. A
Profile is not safe for concurrent use and keeps nothing of a parse after it
returns. A stream parse keeps the memory of the profile bounded: the profile
forgets the positions that the stream has discarded, where no rule is evaluated
again.
The engine records each event in the profile before the trace functions receive it, so a snapshot taken by a trace function on an exit includes that call, and the times exclude the time of the trace functions. Times include the cost of measuring them and are comparable with each other only.
Profile.Snapshot() returns a ProfileSnapshot, an owned copy of the counts
with the rules sorted by name and each rule's skip reasons sorted by reason. It
has the totals Parses, Entered, Calls, Evals, MemoHits, Skipped,
ReusedElements (completed root calls only, counted once), Examined (over
completed root calls, the input from each call's position to its Examined),
Time (the time of the completed root calls) and Rules, a list of
RuleProfile. ProfileSnapshot.Hints() returns text that points at costly
rules. Entered counts calls that began, including calls interrupted before
their exit; the other counts and the times cover completed calls only. A
RuleProfile has the fields below.
| Field | Meaning |
|---|---|
Rule |
The rule name. Calls of a rule's value-free twin count as calls of the rule |
Entered |
The calls that began |
Calls, MemoHits, Matched, Failed |
Each completed call either evaluated the body or took the memoized result, and either matched or failed |
Evals |
Body evaluations: one per call not answered by the memo and one more for each growth step of a left-recursive match |
ReusedElements |
Repetition elements reused during the calls, nested calls included. A nested call can report the same reuse as its parent, so parent and child rows MUST NOT be summed |
Consumed |
The input matched by calls that matched |
Skipped, SkipReasons |
The calls reported as TraceSkipped, in all and by reason; always zero for the engine |
Examined |
The sum, over the calls, of Examined - Pos |
Wasted |
The same sum over the calls that evaluated the body and failed. It is inclusive of the calls they made |
LongestFail, LongestFailAt |
The most input one failed call that evaluated the body examined, and where |
Repeats |
The number of calls that evaluated the body at a position and level where an earlier call of the same parse had evaluated it |
MaxEvals, MaxEvalsAt |
The most evaluating calls at one position and level, and where |
Time, SelfTime |
The time spent in the calls, nested calls included (a call within a call of the same rule counts once), and excluding nested calls |
LongestFailAt and MaxEvalsAt are a CallSite: a Location (Pos, Line
and Col) with the Level of the call. Tied maxima keep the first location.
The line of a location is 0 when the producer has no line information, as for
generated parsers, or when the position lies in input that a stream parse has
discarded; such a location prints as position N. In JSON, the keys are the
camel-case field names, and Time and SelfTime are in nanoseconds.
Generated Go Batch Tracing
Standalone generated Go Node parsers may be generated with tracing enabled by
Observability of compiler.GoConfig or sxir gen -observability. This mode
supports batch Parse and ParseRule; it also supports Recognize when that
entry point is generated. With generated types, it additionally supports
ParseValue and ParseRuleValue, for both direct typed execution and Node-conversion
fallback. Typed events describe rule calls made by the selected route;
conversion itself is not a rule event, so Node and typed event streams may
differ. Typed methods use the same event fields, filter, depth, interruption
and callback-panic behavior as Node batch methods. Generated Go Node and typed
batch parsers also provide profiling through WithProfile.
A parser generated without observability does not observe: passing it the trace or
profile options (WithTrace, WithProfile, WithTraceFilter, WithTraceMaxDepth)
returns an error before the parse instead of delivering partial data. A parser
generated with observability gives them the meaning that
Observation Options defines.
The generated package re-exports the event types of the package instrument
(TraceEvent, TraceKind with TraceEnter, TraceExit and TraceSkipped,
SkipReason and SkipFirstCharacter) and the trace options.
Events observe actual generated execution, not an event-for-event replay of
engine parser calls. TraceEnter begins a rule call before its memo lookup or
body dispatch; TraceExit reports the call's result and end position. The start
rule has depth 1. An exit describes the rule call only: whole-input acceptance
can still fail because input remains after the rule returns. TraceSkipped is
unpaired; it is emitted only for identifiable first-character dispatch skips,
with the SkipReason SkipFirstCharacter ("first-character"), and is not an
entered call. A call aborted by a runtime error or callback panic may have no
exit event.
An event has the fields of the engine's TraceEvent above, plus SkipReason
on a skipped event. Event positions use the selected position unit.
Lookahead is true for a call made where failures record no expectations:
inside a lookahead, or inside the skip expression of an Operators Rule, which
is matched as in a lookahead. It has the same value on the call's exit. Memo=true means the
call reused an existing memo result without evaluating its body, so Evals is
zero. Calls that evaluate left-recursion growth attempts have Memo=false;
their Evals counts their own body attempts, including growth attempts.
Recursive calls that reuse the growing seed have Memo=true and Evals=0.
So does a leader call whose growth takes every step from the steps that the
parse memoized while another growth of its cycle was in progress at its
position: it evaluates no attempt and reuses memoized results, so it also
counts as a reuse in Document.Stats().Reused.
Generated parsers do not resume repetitions, so ReusedElements is always 0.
Every exit event MUST report in Examined the call's exact examined end, as
Engine Tracing defines it.
Trace callbacks receive a copied event synchronously. Generated events carry no
parser state: their LineCol returns 0, 0, Text returns the empty string, and
Failure and Recovered return nil. In JSON an event has the keys kind (the
string "enter", "exit" or "skipped"), rule, level, depth, pos,
lookahead, matched, end, memo, evals, reusedElements, examined
and skipReason. Callback panics propagate with their original value after
cleanup. Trace state is local to one invocation.
Generated Go Batch Profiling
Generated Go Node and typed batch packages generated with
Observability MUST expose WithProfile and re-export from the package instrument
Profile, ProfileSnapshot, RuleProfile, Location, CallSite and
SkipReasonCount. A Profile is opaque. The zero value of Profile MUST be
ready to use; a nil profile is ignored. A profile sink is not
safe for concurrent use. Reentrant parses on one goroutine MUST keep separate
per-invocation accounting, and a profile MUST NOT retain anything of a parse
after it returns. Snapshot() MUST return an owned copy with rules sorted by
name and each rule's skip reasons sorted by reason; callers may marshal the
snapshot for deterministic JSON, whose keys are the camel-case field names.
ProfileSnapshot.Hints() returns text that points at costly rules.
The snapshot and its rows are those of Engine Profiling.
The Line and Col of LongestFailAt and MaxEvalsAt are 0 because
generated events carry no line information.
Parses counts root invocations and Entered counts rule calls that began,
including calls interrupted before exit. Calls, Evals, MemoHits, match and
failure counts, consumed positions, and timing include only completed calls.
Evals counts body attempts, including left-recursive growth. Repeats and
MaxEvals count completed non-memo calls with Evals > 0 at the same
(rule, position, level) within an invocation; tied maximum locations retain
the first observed location. Skipped and per-rule skip reasons count
identifiable generated dispatch skips independently of trace filters; skips
are not entered calls. Position counts use each invocation's configured unit
and MUST NOT be treated as normalized when a sink accumulates multiple units.
Examined and Wasted are defined with Document profiling below; a rule with
no completed call reports them as zero. LongestFail is the most input one
completed failed call with Memo=false examined. Root Time sums completed
root rule calls and excludes input setup, whole-input end checks and
typed-result conversion. Per-rule Time counts recursive calls of the same
rule once within each invocation, while SelfTime excludes child time. Both
include instrumentation and exclude the time of trace callbacks. A call is
added to the profile before the trace callback receives its exit, so a
snapshot taken inside that callback includes it. Callback panics MUST propagate
unchanged after cleanup. A panic in an exit callback MUST still count that
completed call; a panic in an enter callback does not synthesize an exit.
Generated Go Document Tracing and Profiling
When generated Go observability and Document support are both enabled,
NewDocument MUST accept the observation options as retained defaults.
Construction MUST NOT emit parser events or profile counts. Document.Parse
and, with generated types, Document.ParseValue MUST accept them for one
invocation, combined with the defaults as
Observation Options defines; they MUST NOT change the
defaults for later calls. Edit does not parse and MUST NOT emit
rule events.
Events MUST report actual rule calls in the current invocation, including Node,
direct typed and Node-conversion fallback calls. Conversion itself MUST NOT
emit a rule event. A memoized whole-call reuse MUST report that call with
Memo=true and Evals=0; nested events from earlier parses MUST NOT be
replayed. Generated Documents do not resume repetition bodies, so their
ReusedElements is 0.
In a Document parse, an exit event's Examined, as
Engine Tracing defines it, is also the end against which a
later edit decides whether the call's memo result is reused. A call that
records a memo result MUST report the end stored with that result, and a memo
hit the end stored with the result it reuses. Results that reuse a growing
left-recursive seed are never reused after an edit.
A rule's profile Examined sums, over completed calls, Examined - Pos;
Wasted sums the same over completed failed calls with Memo=false. Batch and
Document parses of a rule accumulate into the same sums.
After a completed parse, the invocation's increases in profile Evals and
MemoHits MUST equal Document.Stats().Evaluated and .Reused, respectively.
Stats has no call counter. An
interrupted parse MAY leave statistics for calls that began but did not
complete. Temporary observer and profile state MUST be released after return
or panic; retained constructor defaults remain available for later calls.
While a Document generated with observability parses, its Parse,
ParseValue and Edit MUST return the generated ErrDocumentBusy, before
validating options and without changing the Document; this rejects calls a
callback makes on the same Document. The outer parse continues unaffected.
Callers SHOULD schedule later work or use another Document; parses of other
Documents and batch Parse calls remain allowed from callbacks.
Generated TypeScript Tracing and Profiling
Generated TypeScript parsers observe parses when generated with
Observability of compiler.TSConfig or sxir gen -lang ts -observability.
The observation options are fields of ParseOptions, accepted by
parseWithOptions, parseRuleWithOptions and, when generated,
recognizeWithOptions, by parseValueWithOptions with -types, and by
createDocument (as defaults) and a Document's parse and parseValue (for
one parse) with -document. The positional-unit APIs do not accept them, and
TypeScript has no named typed-rule entry point. A parser generated without
observability returns an error for any of these options instead of parsing.
trace?: TraceFunction | readonly (TraceFunction | null)[] | null;
profile?: Profile | readonly (Profile | null)[] | null;
traceRules?: readonly string[];
traceMaxDepth?: number;
They have the meaning that Observation Options
defines. An array of trace functions or profiles means what one WithTrace or
WithProfile for each of its entries, in order, means, and a single function
or profile what an array of it means; null and null entries are ignored.
traceRules is the list of names of WithTraceFilter and traceMaxDepth the
n of WithTraceMaxDepth, which MUST be a safe integer. Any other value of
these options is an error of the options. If a trace function throws, the
parse ends by throwing the original value after its cleanup, even when it is
not an Error, and the functions after it do not receive the event; an ended
parse may omit the exits of the calls in progress.
The generated module exports the types TraceEvent, TraceKind,
TraceFunction and SkipReason. Events and their fields are those of
Generated Go Batch Tracing, each named as its
JSON key there, so an event serializes with JSON.stringify as a Go event
does: kind is "enter", "exit" or "skipped", and skipReason is
"first-character" on a skipped event and "" otherwise. Positions use the
selected unit. Each trace function receives a copy of its own, which it may
keep or change without changing the parse or later events. Every exit event
MUST report in examined the call's exact examined end, as
Engine Tracing defines it, in the selected unit; an observed
parse therefore compares examined ranges where
Evaluations of Rules requires them. A
Document parse reports its calls as
Generated Go Document Tracing and Profiling
defines, and so does its Examined.
The generated module exports Profile and the types ProfileSnapshot,
RuleProfile, CallSite and SkipReasonCount. A Profile, made with
new Profile(), accumulates parses as
Generated Go Batch Profiling defines, keeps
nothing of a parse after it returns; a parse made by a trace function keeps
accounting separate from the parse in progress. snapshot() returns an owned copy whose fields are those of
instrument.ProfileSnapshot, each named as its JSON key, with rules sorted by name
and skip reasons sorted by reason, so that its JSON is deterministic and
matches the JSON of a Go snapshot except for the times: time and selfTime
are milliseconds from the host's monotonic performance.now() clock. The
times exclude input setup, whole-input end checks, typed-result conversion and
the time of the trace functions.
Profiling requires performance.now() and does not fall back to Date.now():
without it, a profiled parse returns an Error. Valid readings MAY have coarse
resolution and give zero durations. A clock that throws makes the parse throw
its original value; a non-finite or backward reading makes the parse fail with
an explicit error, and MAY leave a partial profile. If a trace function throws
and a later clock reading fails, the parse throws the value of the trace
function. The implementation does not require DOM type declarations.