Package sxir/pkg/lint
import "syntaxir.dev/sxir/pkg/lint"
Generated from the source of this version. Also on pkg.go.dev.
Overview
Package lint reports likely mistakes in SyntaxIR grammars: rules and alternatives that can never match, expressions that have no effect, captures that are never read, and grammar shapes that defeat incremental parsing.
Config.Run checks a grammar with the front end before it lints it. The checks work on the grammar AST, with the rule facts of the front end. Each check reports only what it can prove from the grammar (the exceptions are the performance hints, which have the severity Hint); see docs/design/records/018-grammar-linting.md for the reasoning behind each one.
Index
Constantstype Budgettype Causetype CauseKindtype Checktype Classtype Classificationtype Configtype Findingtype Rewritetype Severity
Constants
const (
CheckUnreachableRule = "unreachable-rule"
CheckShadowedAlt = "shadowed-alternative"
CheckNeverMatches = "never-matches"
CheckUselessLookahead = "useless-lookahead"
CheckNullableRepetition = "nullable-repetition"
CheckRedundantOptional = "redundant-optional"
CheckGrowingVariable = "growing-variable"
CheckUnusedCapture = "unused-capture"
CheckDuplicateCapture = "duplicate-capture"
CheckCharClass = "char-class"
CheckRightRecursion = "right-recursion"
CheckPositions = "positions"
CheckLongLookahead = "long-lookahead"
CheckSuperLinear = "super-linear"
CheckCaseInsensitive = "case-insensitive-literal"
CheckDirective = "lint-directive"
)
Names of the checks.
Types
type Budget source
type Budget struct {
PerUnit, Fixed uint64
}
Budget bounds the compute units of a parse of a grammar of the class Linear: a parse of n position units of the input costs at most PerUnit * n + Fixed units, where n counts bytes for the position unit Bytes and code points for CodePoints. The units are the logical events of the compute limit. The constants wait for the proof of linear cost to confirm them, so the bound is a report and is not the default of Limits.Compute.
type Cause source
type Cause struct {
// Kind is the pattern the cause comes from; CauseOther for a reason.
Kind CauseKind
Class Class
// Degree is k of a polynomial cause.
Degree int
// Rule is the rule that holds Pos.
Rule string
Pos ast.Pos
// Message names the class and the witness (or, for the class Unknown, the reason).
Message string
}
Cause is one polynomial or exponential cause, at the scanning source, binding or operation that causes it, or one reason for the class Unknown.
type CauseKind source
type CauseKind uint8
CauseKind is the pattern of grammar that a cause comes from. Each kind but CauseOther is a pattern that the recipe of linear rewrites in the cookbook shows a rewrite for.
const (
// CauseOther is a reason for the class Unknown, or a cause of a pattern that no rewrite covers.
CauseOther CauseKind = iota
// CauseRestartedRepetition is a repetition that a failed alternative restarts inside the input
// it examined.
CauseRestartedRepetition
// CauseLookaheadScan is a lookahead whose scan restarts at every iteration of a repetition.
CauseLookaheadScan
// CauseRecoverySkip is a #recover skip expression walked again after the recovery fails.
CauseRecoverySkip
// CauseRegrowth is a left-recursive rule or an Operators Rule that grows again over the same
// input, or a construct evaluated in each step of such a growth.
CauseRegrowth
// CauseDivergingBinding is a binding of a variable that reads its earlier value, or that makes
// the number of values of the variables unbounded.
CauseDivergingBinding
// CauseSelfGrowingValue is a value built from its own earlier value, or copied more often than
// the input bounds.
CauseSelfGrowingValue
)
func (CauseKind) String source
func (k CauseKind) String() string
String returns the name of the kind, such as "restarted repetition".
type Check source
type Check struct {
Name string
// Severity is the highest severity the check reports.
Severity Severity
Summary string
}
Check describes a check.
func Checks source
func Checks() []Check
Checks returns every check, in the order of the documentation.
type Class source
type Class int
Class is the class of the cost of a parse from a start rule (see "Classification" in the parsing specification). The classes are ordered from the strongest claim to the weakest: Linear and LinearEnv are guarantees, Polynomial estimates a bound, Unknown is no bound, and Exponential is an estimate of growth that no polynomial bounds.
const (
// Linear promises a cost of at most c · (n + 1).
Linear Class = iota
// LinearEnv promises a cost of at most c · K · (L + 1) · (n + 1).
LinearEnv
// Polynomial estimates a cost that grows as n^Degree: every condition for linear cost that
// fails has a witnessed cause, and Degree bounds them all.
Polynomial
// Unknown makes no claim: a condition for linear cost fails that no cause accounts for.
Unknown
// Exponential estimates a cost that can double when n grows by a constant.
Exponential
)
func (Class) String source
func (c Class) String() string
String returns the name of the class, such as "linear" or "polynomial".
type Classification source
type Classification struct {
Class Class
// Degree is the largest degree of the causes of the class Polynomial, and zero for any other
// class.
Degree int
// WitnessedDegree is the largest degree of the polynomial causes of the class Unknown, and zero
// for any other class. It is a lower estimate from the witnesses, not a bound.
WitnessedDegree int
// Causes are the polynomial and exponential causes, sorted by position. A grammar of the class
// Unknown can have them too.
Causes []Cause
// Reasons are the reasons for the class Unknown, sorted by position. Only an exponential
// grammar has them besides.
Reasons []Cause
// Env says why the class is at least linear given an environment bound, or is empty.
Env []Cause
// Combinations is the product of the numbers of values of the variables with finite values,
// 1 when there are none. For the class Linear it bounds the number of combinations of the
// values of the variables that memoized rules read at one position.
Combinations int
// Budget is the bound on the compute units of a parse that the classification derives, for the
// class Linear only, and nil for any other class. It is reported and is not applied as a
// default limit.
Budget *Budget
}
Classification is the class of the cost of a grammar from one start rule, with what decides it.
func Classify source
func Classify(ctx context.Context, g *ast.Grammar, start string) (*Classification, error)
Classify classifies the cost of parsing with the grammar g from its start rule start, the classification that Config.Classify asks a lint run for. An empty start selects the default start rule. Classify returns an error if g does not compile, if start is not a start rule of g, or if ctx ends.
type Config source
type Config struct {
// Disable holds the names of the checks not to run (see Checks).
Disable []string
// Classify requests the classification of the cost of the grammar from the start rule, and
// with it the super-linear check, which reports nothing without it.
Classify bool
}
Config configures a lint run. The zero value runs every check except super-linear.
func (Config) Run source
func (c Config) Run(ctx context.Context, g *ast.Grammar, start string) ([]Finding, error)
Run lints the grammar g from its start rule start: it reports rules the start rules never use, alternatives and expressions that can never match or have no effect, captures that are never read, variables that can grow exponentially, grammar shapes that slow down incremental parsing and, when c.Classify is set, the causes of a cost that can grow faster than the input. The findings are sorted by position. unreachable-rule reports the rules that neither start nor another @start rule reaches. Comments of the form "// lint:ignore check reason" in the source suppress findings (see the directive syntax in docs/guide/linting.md).
An empty start selects the default start rule. Run returns an error, and no findings, if g does not compile (compiler.GrammarErrors), if start is not a start rule of g, if c.Disable names an unknown check, or if ctx ends; cancellation stops both the compilation and the checks and discards all findings.
type Finding source
type Finding struct {
// Pos is where the problem is in the source. It is the zero Pos for a grammar without
// positions (decoded from JSON, or loaded from a compiled grammar).
Pos ast.Pos
Severity Severity
// Check is the name of the check that reported the finding (see Checks).
Check string
// Rule is the rule the finding is in, if any.
Rule string
Message string
// Fix is a suggested change, or "" if there is no single obvious one.
Fix string
}
Finding is a problem found in a grammar.
func (Finding) String source
func (f Finding) String() string
String formats the finding for display: position, severity, message and check.
type Rewrite source
type Rewrite struct {
Start, End ast.Pos
NewText string
}
A Rewrite is a change to the source of a grammar that fixes a finding without changing what the grammar matches or the values it builds. Only three findings have one, each when the proof for its kind holds, and a tool that applies a Rewrite still checks the result:
- char-class, for ranges that overlap or repeat: the class is replaced by one with merged ranges. The proof is that both classes contain the same code points, checked at the ends of every range, and that negation is unchanged. A class that also matches punctuation between letters, such as [A-z], has no Rewrite, because the writer must say which characters were meant.
- useless-lookahead, for a lookahead that always succeeds: it is removed, but only where it is itself an item of a sequence of at least three items, so that the sequence keeps at least two and stays a tuple. Under a discard "-", a label or any operator it is not removed, because the "-" would move onto the next item and change the values. The proof is that the lookahead matches only a combination of literals, character classes, any-character, groups, sequences, choices, options and repetitions, so it holds no capture, cut, call, predicate, recovery or attribute, and a lookahead consumes nothing and has no value.
- unreachable-rule: the rule is removed. The proof is that no start rule reaches it, directly or through an inline action, so nothing calls it and no parse starts at it.
Start and End delimit the source to replace by NewText, with End exclusive. For a rule the span is the whole definition including its attributes.
func Rewrites source
func Rewrites(ctx context.Context, g *ast.Grammar, start string, findings []Finding) ([]Rewrite, error)
Rewrites returns, for each finding of the lint run of g from start, its Rewrite or the zero Rewrite. The findings must come from Config.Run on the same g and start. Rewrites returns an error, and no rewrites, if g does not compile or start is not a start rule of g. Cancellation discards the result.
func (Rewrite) IsValid source
func (r Rewrite) IsValid() bool
IsValid reports whether the Rewrite holds a change.
const (
// Hint is a suggestion, usually about performance; the grammar is correct as written.
Hint Severity = iota + 1
// Warning is a likely mistake, or an expression that has no effect.
Warning
// Error is a certain mistake: part of the grammar can never take effect.
Error
)
func (Severity) MarshalText source
func (s Severity) MarshalText() ([]byte, error)
MarshalText encodes the severity as its name.
func (Severity) String source
func (s Severity) String() string
String returns the name of the severity: hint, warning or error.
func (*Severity) UnmarshalText source
func (s *Severity) UnmarshalText(text []byte) error
UnmarshalText decodes the name of a severity.