Package sxir/pkg/lint

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

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

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.

type Severity source

type Severity int

Severity tells how likely a finding is to be a mistake.

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.