Package sxir/pkg/runtime

import "syntaxir.dev/sxir/pkg/runtime"

Overview

Package runtime defines what a parse runs under and reports that every SyntaxIR parser shares: the limits of a parse and its limit errors, the stream iterator, and the statistics of a Document. The nodes a parse produces are in package value, the position unit and the edits of its input in package input, and traces and profiles in package instrument. Parsers loaded from compiled grammars (package vm), compiled from grammars (package compiler) and generated Go parsers return the same types, so errors.Is, errors.As and code written against these types work with all of them.

The runtime packages are stable in intent at v0.x: a change needs a reason and is announced. The library of generated Go parsers and the package value/impl are support for generated code; they are judged by the library protocol version and have no stable API.

Index

Constants

const Unlimited = math.MaxUint64

Unlimited is the value of a limit that disables it. Every field of Limits is a uint64 and takes it, so one constant serves them all.

Variables

var ErrLimit = errors.New("parse limit exceeded")

ErrLimit is matched by errors.Is for any LimitError.

var ErrSchemaUnavailable = errors.New("output schema unavailable")

ErrSchemaUnavailable reports that the grammar metadata a schema is exported from is unavailable. In particular, a parser loaded from a compiled grammar cannot export a schema.

var ErrStreamClosed = errors.New("stream iterator is closed")

ErrStreamClosed is returned after an iterator is abandoned before termination.

Types

type CacheStats source

type CacheStats struct {
	LiveMemoEntries    int
	RetiredMemoEntries int
	RepetitionElements int
	EstimatedBytes     uint64
}

CacheStats describes the incremental history a Document retains. EstimatedBytes includes backing buffers and run records, but excludes map buckets, allocator metadata, the document text, result trees, shared expectation, error and environment payloads, and strings shared with results the caller holds.

type Document source

type Document interface {
	// Text returns the current text.
	Text() string
	// Unit returns the position unit of the document, fixed at construction.
	Unit() input.PositionUnit
	// Edit replaces the range [start, end) of the text, in the document's position unit, with
	// text.
	Edit(start, end int, text string) error
	// Parse parses the current text. opts apply once over the construction defaults and may
	// change the context, limits, depth and trace, but not the unit.
	Parse(opts ...ParseOption) (*value.Node, error)
	// Stats returns the evaluation and reuse counts of the last Parse.
	Stats() ParseStats
	// CacheStats inspects the retained incremental history without changing it.
	CacheStats() CacheStats
	// ResetHistory discards the incremental reuse history while keeping the text, the
	// construction options, the version and the statistics of the last parse.
	ResetHistory()
}

Document is a text that is edited repeatedly. Parsing after an edit reuses the results of the previous parse that the edit did not affect (incremental parsing), as editors need. A Document is not safe for concurrent use.

Reused results are shared with the trees returned by earlier parses, and the nodes after an edit are moved to their new positions in place: an earlier tree changes when Parse runs again. Use value.Node.Clone to keep a tree as it was. The Document of a parser loaded from a compiled grammar (vm.Document) also offers versions, batch edits, snapshots and change notifications.

type LimitError source

type LimitError struct {
	Kind      LimitKind
	Limit     uint64
	Used      uint64
	Requested uint64
	Hotspot   string
}

LimitError reports a reservation that would exceed a limit. Used is the counter value before the rejected reservation; Requested is the complete atomic reservation that could not be made. For LimitInput, Limit is the Input limit, Used is zero and Requested is the length of the input in the position unit; for a stream it is the number of units the parser had asked for, or the length of the stream if that is shorter. For LimitDepth, Limit is the resolved Depth limit, Used is the depth reached (the limit) and Requested is one, the nested call that would exceed it. For LimitMemory, Used is the count of bytes at the check that failed and Requested is zero, since memory is checked at polls rather than reserved.

For LimitCompute, Hotspot is the rule that the Profile of the parse ranks first when the limit is exceeded (Profile.Hotspot: the most evaluations at one position and level, a tie going to the rule with more repeated evaluations, then to the first name). Every backend records the profile while the parse runs and ranks it this way. It is empty without a Profile and when no rule evaluated twice at a position. A parse without a Profile does not name one: run it again with WithProfile to find the hotspot.

func (*LimitError) Error source

func (e *LimitError) Error() string

func (*LimitError) Is source

func (e *LimitError) Is(target error) bool

Is reports whether target is ErrLimit.

type LimitKind source

type LimitKind uint8

LimitKind identifies the limit that was exhausted.

const (
	// LimitCompute is the kind of an exhausted Compute limit.
	LimitCompute LimitKind = iota
	// LimitInput is the kind of an input longer than the Input limit.
	LimitInput
	// LimitDepth is the kind of a parse that nests recursive rule calls deeper than the Depth
	// limit.
	LimitDepth
	// LimitMemory is the kind of a parse whose storage passed the Memory limit.
	LimitMemory
)

type Limits source

type Limits struct {
	Compute uint64
	Memory  uint64
	Input   uint64
	Depth   uint64
}

Limits bounds one parse invocation. A zero limit selects the default of that limit, and Unlimited disables it.

Compute bounds the cumulative cost of the parse: every input unit inspected, every rule call and loop iteration, and every unit of value construction adds to one counter, so a bound on it bounds scanning, recursion and value building alike. The default grows with the length of the input.

Memory bounds the bytes of storage the parser holds for the parse, counted when the parser takes it into use and returned when it lets it go at a point it controls (a stream's commit, a Document's history reset). Storage dropped by backtracking is not returned. The default is Unlimited. The count is checked with the compute polls, so a parse can pass the limit by what it allocates between two polls before it fails with a LimitError of kind LimitMemory. A Document's count starts at the bytes it retains from earlier parses. What is counted depends on the parser and its version.

Input bounds the length of the input in the position unit of the parse. The default is Unlimited: the default compute budget already grows with the input. A parse of an input that is longer fails before any work, with a LimitError of kind LimitInput; a stream fails when the parser reaches a unit beyond the limit.

Depth bounds the nesting of recursive rule calls: the entries of rules on a cycle of calls and the operands of Operators Rules that nest like them. Zero selects the default of the parser (of the backend that runs the parse, or the default a generated parser was generated with). Unlimited disables it only where the call stack is on the heap, the engine's iterative bytecode VM; elsewhere it is an option error, because the goroutine stack would overflow first. A finite Depth above the largest int counts as the largest int. A deeper parse fails with a LimitError of kind LimitDepth.

type MissingTokenLimitError source

type MissingTokenLimitError struct {
	Limit, Position int
}

MissingTokenLimitError reports that a parse exhausted its budget of #missing insertions. Position is in the position unit of the parse. Exhaustion aborts parsing, including when an alternative that used the budget would otherwise be abandoned.

func (*MissingTokenLimitError) Error source

func (e *MissingTokenLimitError) Error() string

type ParseOption source

type ParseOption func(*ParseOptions)

ParseOption configures one parse, or the defaults of a Document.

func WithComputeReport source

func WithComputeReport(out *uint64) ParseOption

WithComputeReport stores in *out the compute units that the parse spent, when it ends: after a success, after a failure, and after a stop by a limit or a context. They are the units that the Compute limit counts, so a parse that succeeded with the report r is accepted by a Compute limit of r and rejected by one below it. A parse rejected before it starts (an invalid option, an input over the Input limit) stores zero. Every entry point that runs a parse reports, one that streams when its stream ends. A nil out disables the report. A generated Go parser takes the option only if it was generated with limit controls, as it does a Compute limit.

func WithContext source

func WithContext(ctx context.Context) ParseOption

WithContext selects invocation-local cooperative cancellation. Nil disables it.

func WithDiagnosticCallback source

func WithDiagnosticCallback(f func(*value.SyntaxError) error) ParseOption

WithDiagnosticCallback reports each committed #recover error during stream parsing, immediately before the corresponding stream element. Speculative recoveries are not reported. The callback receives an independent copy; returning an error stops parsing and suppresses that element. A nil callback disables delivery. Non-nil callbacks are invalid with whole-input parsing, prefix parsing and Documents. With or without this option, recovered errors remain available at stream completion.

func WithDiagnosticLimit source

func WithDiagnosticLimit(n int) ParseOption

WithDiagnosticLimit retains at most n committed stream recoveries, keeping the latest errors. Zero retains every error, as in an unconfigured stream parse. Negative values are invalid. This option is valid only with stream parsing, including when n is zero. When errors are dropped, the terminal error is *value.TruncatedSyntaxErrors.

func WithExpectations source

func WithExpectations() ParseOption

WithExpectations records what a syntax error expects. A syntax error then lists the expectations at the farthest failure and carries the messages of @error. Without it the error reports the farthest failure position, an empty Expected list and no Messages, and parsing does not record expectations. A Document fixes it at construction.

func WithLimits source

func WithLimits(l Limits) ParseOption

WithLimits sets the invocation-local limits field by field: a nonzero field overrides the value of an earlier WithLimits, including the construction defaults of a Document, and a zero field leaves it unchanged. A field that no option sets takes its default; Unlimited disables a limit.

func WithMissingTokens source

func WithMissingTokens(limit int) ParseOption

WithMissingTokens bounds attempted #missing literal insertions in one parse. Zero disables insertion; negative limits are invalid. Only whole-input parsing and recognition on the reference parser support insertion; positive limits are invalid with prefix parsing, even without #missing in the grammar. Options resolve in order.

func WithProfile source

func WithProfile(prof *instrument.Profile) ParseOption

WithProfile adds the cost of the parse to prof. It traces the parse (see WithTrace), so the parse is several times slower, and the times in prof are meaningful relative to each other only; they do not include the time of the functions given WithTrace. prof records every call, whatever WithTraceFilter and WithTraceMaxDepth select. With several WithProfile options, each profile records the parse. A nil prof is ignored.

func WithTrace source

func WithTrace(f func(instrument.TraceEvent)) ParseOption

WithTrace 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 (the depth of an event is in TraceEvent.Depth). It reports the calls the parser makes: a call skipped because the next character cannot start the rule is not reported. Tracing does not change the result, but it makes the parse several times slower. The event's methods (LineCol, Text, Failure) read the parser's state, so call them from f; its fields can be kept. A generated Go parser keeps no such state in its events: their methods return zero values, and only the fields carry information. With several WithTrace options, each function receives every event, in the order of the options. A nil f is ignored. WithTraceFilter and WithTraceMaxDepth select the events the functions receive. Generated Go parsers take these options and give them the same meaning.

func WithTraceFilter source

func WithTraceFilter(rules ...string) ParseOption

WithTraceFilter limits the events that the trace functions receive to the calls of the named rules and the calls nested in them. A name that is not a rule matches no call; with no names, every call is selected. The last WithTraceFilter of a parse applies. It does not change the parse or what WithProfile records.

func WithTraceMaxDepth source

func WithTraceMaxDepth(n int) ParseOption

WithTraceMaxDepth limits the events that the trace functions receive to the calls at most n deep, counting the start rule as 1. Zero or a negative n sets no limit. The last WithTraceMaxDepth of a parse applies. It does not change the parse or what WithProfile records.

func WithUnit source

func WithUnit(u input.PositionUnit) ParseOption

WithUnit selects the position unit. Matching always proceeds by code point, whatever the unit.

type ParseOptions source

type ParseOptions struct {
	// Context cooperatively interrupts this invocation. Nil means no cancellation.
	Context context.Context
	// Limits bound the cost of the parse, the length of its input and the nesting of its
	// recursive rule calls.
	Limits Limits
	// MissingTokens bounds attempted #missing insertions. Zero disables insertion.
	MissingTokens int
	// Expectations records what a syntax error expects (see WithExpectations).
	Expectations bool
	// Unit is the position unit. Matching is done per code point regardless of the unit.
	Unit input.PositionUnit
	// Traces receive an event at the start and at the end of every rule call, each function
	// every event, in order. A parser checks for interruption between the functions.
	Traces []func(instrument.TraceEvent)
	// TraceSelection, if not nil, limits the events that the Traces receive. Options replace it
	// instead of changing it, so a Document's defaults can share theirs with each parse.
	TraceSelection *instrument.TraceSelection
	// Profiles record the rule calls of the parse; each records an event before the Traces
	// receive it.
	Profiles []*instrument.Profile
	// DiagnosticCallback receives committed recoveries during stream parsing, immediately
	// before the corresponding element.
	DiagnosticCallback func(*value.SyntaxError) error
	// DiagnosticLimit retains only the latest committed stream recoveries when positive.
	// DiagnosticLimitSet records that a limit was given, an explicit zero included.
	DiagnosticLimit    int
	DiagnosticLimitSet bool
	// ComputeReport, if not nil, receives the compute units that the parse spent when it ends
	// (see WithComputeReport).
	ComputeReport *uint64
}

ParseOptions holds the settings of one parse, which ParseOption functions set. Parsers read it after applying the options in order; programs set it through the options.

type ParseStats source

type ParseStats struct {
	Evaluated       int // rule body evaluations
	Reused          int // memo hits and resumed repetition elements
	MemoHits        int // memo results reused
	ResumedElements int // repetition elements reused
}

ParseStats counts the rule evaluations and reuses of the last parse. Reused is MemoHits plus ResumedElements.

type Parser source

type Parser interface {
	// Parse parses the whole input and returns the value of the start rule. If the input does
	// not match, it returns a *value.SyntaxError. If the parse recovered from errors with
	// #recover, it returns both the node and the value.SyntaxErrors.
	Parse(input string, opts ...ParseOption) (*value.Node, error)
	// Recognize decides whether the input matches the grammar without building a tree. It
	// returns the same success, failure and syntax errors as Parse, recovered errors included.
	// Predicates, and the actions they read, run; the run-time errors of other actions and
	// typed conversions are not checked.
	Recognize(input string, opts ...ParseOption) error
	// ParseStream parses input read from r and passes each element of the #stream repetition at
	// the top level of the start rule to emit as soon as it matches. Emitted elements and the
	// input before them are not retained. If emit returns an error, parsing stops and ParseStream
	// returns that error.
	ParseStream(r io.Reader, emit func(*value.Node) error, opts ...ParseOption) error
	// NewDocument creates a Document for text. opts select its fixed unit and the defaults of
	// later parses.
	NewDocument(text string, opts ...ParseOption) (Document, error)
	// OutputSchema exports the types of the values that the parser returns. A parser loaded
	// from a compiled grammar has no grammar metadata and returns ErrSchemaUnavailable.
	OutputSchema(opts ...SchemaOption) (*schema.Output, error)
}

Parser parses inputs with one grammar from one start rule. A parser compiled from a grammar (package compiler) and one loaded from a compiled grammar (package vm) implement it; the concrete types offer more, such as a choice of start rule or prefix parsing. A Parser is safe for concurrent use; the Documents it creates are not.

type SchemaOption source

type SchemaOption func(*SchemaOptions)

SchemaOption configures one output schema export.

func WithAllSchemaRules source

func WithAllSchemaRules() SchemaOption

WithAllSchemaRules includes unreachable rules and declared types in the schema. By default, the export starts at the parser's start rule.

type SchemaOptions source

type SchemaOptions struct {
	// AllRules includes the rules the start rule does not reach and every declared type.
	AllRules bool
}

SchemaOptions are the settings of one output schema export, which SchemaOption functions set.

type SnapshotCaptureError source

type SnapshotCaptureError struct {
	Path       string
	ValueType  reflect.Type
	ParseError error
}

SnapshotCaptureError reports a field value of a type that a snapshot cannot capture. It retains the type and the parse error, never the value.

func (*SnapshotCaptureError) Error source

func (e *SnapshotCaptureError) Error() string

func (*SnapshotCaptureError) Unwrap source

func (e *SnapshotCaptureError) Unwrap() error

Unwrap returns the parse error.

type StreamIterator source

type StreamIterator struct {
	// contains filtered or unexported fields
}

StreamIterator advances synchronously to one committed element at a time. It is single-owner: Next and Close must not overlap, including callbacks. Close releases parser state but never closes or interrupts its reader. The standard library pull coroutine has no independently scheduled producer.

func NewStreamIterator source

func NewStreamIterator(run func(yield func(*value.Node) bool) error) *StreamIterator

NewStreamIterator returns an iterator over the elements that run yields. run parses a stream, passes each committed element to yield, and returns the error that ends the parse, or nil; once yield returns false it must stop and return. run starts with the first call of Next. Parsers use it to offer an iterator; programs get one from a parser.

func (*StreamIterator) Close source

func (it *StreamIterator) Close()

Close abandons unfinished parsing and is idempotent. It cannot interrupt a Read already blocked in caller code, and must not overlap a call to Next.

func (*StreamIterator) Next source

func (it *StreamIterator) Next() (n *value.Node, ok bool, err error)

Next returns (node,true,nil), even for a successful discarded nil value. Clean EOF is (nil,false,nil); terminal errors remain stable on later calls.