Chapter 9

Grammar Lint

The linter reads a grammar and reports likely mistakes that the compiler accepts: an alternative that can never match, a capture that is never read, a rule that nothing calls. It does not parse input. This chapter defines the entry points, the severities, each check and the comment directives that suppress findings.

Scope and Terminology

A finding is one report of the linter. It has a position (Pos, the line and column of the construct, zero for a grammar without source positions), a severity, the name of a check, the name of the rule that contains the construct, a message and, when one exists, a suggested fix. A check is one rule of the linter, identified by a name.

Contract

Entry Points

Command line Go
Lint a grammar sxir lint -g g.sxir lint.Config.Run(ctx, g, start)
Machine-readable output -f json []lint.Finding
Turn checks off -disable check,... (or the flag repeated) lint.Config.Disable
Classify the cost -classify lint.Config.Classify
Fail on warnings too -strict Check Finding.Severity
List the checks -list lint.Checks()
  • lint.Config.Run takes a context, a grammar AST and the start rule and returns the findings. If the grammar does not compile, it returns compiler.GrammarErrors and no findings; if the start rule is not a start rule of the grammar, it returns an error and no findings. Cancelling the context stops the compilation and the checks and discards all findings. An empty start rule selects the default start rule.
  • sxir lint accepts SyntaxIR source and grammar JSON; a compiled grammar holds no grammar and is an error. The start rule is the one -s names, otherwise the default start rule of the grammar. A grammar that does not compile is reported with its compile errors.
  • Each finding prints on one line as file:line:col: severity: message [check], followed by a line fix: ... when there is a suggested fix. A run that exits with status 1 ends with the error line sxir: lint: N errors, N warnings, N hints on the standard error, where each count is written as 1 error, 1 warning or 1 hint when it is one and in the plural otherwise; a run that exits with status 0 prints no summary.
  • -f json prints one JSON document with the members grammar, start and findings; each finding has line, col, severity, check, rule, message and, if present, fix.
  • -classify requests the classification of the cost from the start rule, and with it the super-linear check, which reports nothing otherwise. After the findings, the text output prints file: the cost from start rule main is class, where the class is linear, linear (K <= N) when the bound on K that the classification reports is N greater than 1, linear-env, polynomial (n^k), unknown, unknown (witnessed n^k) when the class unknown has polynomial causes of witnessed degree k, or exponential, followed by the first three polynomial or exponential witnesses and the first three reasons for the class unknown, each on a line witness: file:line:col: message or reason: file:line:col: message, and a line ... and N more for those not shown. The line after the class of a linear class is budget: at most c * n + k compute units for an input of n position units, with the derived constants. With -f json the document has a member classification with class, degree (for a polynomial class), witnessedDegree (the witnessed degree of a class unknown, when it has polynomial causes), combinations (the bound N on K of a class linear, when it is greater than 1), budget (for the class linear only: perUnit and fixed, the constants of the budget perUnit * n + fixed), and every witness and reason in witnesses and reasons, each with line, col, rule and message.
  • sxir lint exits with status 1 if there is a finding of severity error, and with 0 otherwise. With -strict, a warning also gives status 1. A hint never does.
  • A grammar decoded from JSON has no source positions: its findings have the zero Pos and name the rule they are in. Such a grammar has no comments, so it cannot carry directives.

Go API

The package lint (syntaxir.dev/sxir/pkg/lint) is the Go form of the linter. It works on a grammar AST (ast.Grammar, see Grammar Representations), not on text, and it reports positions as ast.Pos.

Element Meaning
lint.Severity lint.Hint, lint.Warning and lint.Error, in increasing order of certainty and with the values 1, 2 and 3; the zero value is no severity. String, MarshalText and UnmarshalText use the names hint, warning and error, and UnmarshalText fails on any other name
lint.Finding Pos, Severity, Check (the name of the check), Rule, Message and Fix. Fix is empty when there is no single obvious fix. String is line:col: severity: message [check], without the position when Pos is not valid
lint.Check Name, Severity (the highest severity that the check reports) and Summary
lint.Checks() Every check in the order of the table of checks
lint.CheckUnreachableRule, ... One constant for each check, with the name of the check as its value
lint.Config Disable, the names of the checks not to run, and Classify. The zero value runs every check except super-linear
Config.Run(ctx, g, start) The findings sorted by position, as described above

Config.Run compiles the grammar first and lints what the front end checked. It returns an error and no findings if g does not compile, if start is not empty and not a start rule of g, if Disable names an unknown check or if the context ends. unreachable-rule reports the rules that no start rule reaches, whichever start rule start names.

Classification in Go

lint.Classify(ctx, g, start) returns a *lint.Classification, the classification of the cost of g from the start rule, the one that Config.Classify asks a run for. It returns an error if g does not compile, if start is not empty and not a start rule of g, or if the context ends.

Element Meaning
lint.Class lint.Linear, lint.LinearEnv, lint.Polynomial, lint.Unknown and lint.Exponential, from the strongest claim to the weakest. String gives linear, linear given an environment bound, polynomial, unknown and exponential
lint.Classification The Class of the grammar, with what decides it
Degree The largest degree of the polynomial causes of the class Polynomial, and 0 for any other class
WitnessedDegree The largest degree of the polynomial causes of the class Unknown, and 0 for any other class. It is an estimate from the witnesses, not a bound
Causes The polynomial and exponential causes, sorted by position. A grammar of the class Unknown or Exponential can have them
Reasons The reasons for the class Unknown, sorted by position. A grammar of the class Exponential can have them too
Env The causes that bound the cost only given an environment bound, of the kind CauseDivergingBinding. The class is LinearEnv when Env is not empty and there are no causes and no reasons; a grammar of a worse class can have entries too
Combinations The product of the numbers of values of the variables with finitely many values, and 1 when there are none. For the class Linear it bounds the number of combinations of values that memoized rules read at one position
Budget The budget of the class Linear, a *lint.Budget with PerUnit and Fixed (units at most PerUnit * n + Fixed for n position units), and nil for any other class. It is a report and not a limit
lint.Cause Kind, Class (Polynomial or Exponential for a cause, Unknown for a reason, LinearEnv for an entry of Env), Degree (k of a polynomial cause), Rule, Pos, and Message, which names the class and the witness, or for a reason the reason
lint.CauseKind The pattern of grammar that a cause comes from: CauseRestartedRepetition, CauseLookaheadScan, CauseRecoverySkip, CauseRegrowth, CauseDivergingBinding and CauseSelfGrowingValue, and CauseOther for a reason and for a cause that no pattern covers. String gives restarted repetition, lookahead scan, recovery skip, regrowth, diverging binding, self-growing value and other

Rewrites

A lint.Rewrite is a change to the source of a grammar that fixes a finding without changing what the grammar matches or the values that it builds. Start and End delimit the source to replace, with End exclusive, and NewText replaces it. IsValid reports whether the rewrite holds a change; the zero Rewrite holds none.

lint.Rewrites(ctx, g, start, findings) returns one Rewrite for each finding, in the order of findings, which MUST come from Config.Run on the same g and start. A finding without a rewrite, and a finding without a valid position, has the zero Rewrite. It returns an error and no rewrites if g does not compile, if start is not empty and not a start rule of g, or if the context ends. Only three kinds of findings have a rewrite, each when the condition holds that makes the change safe; a tool that applies a rewrite still checks the result.

Finding Rewrite Condition
char-class for ranges that overlap or repeat The class with merged ranges Both classes contain the same code points, and negation is unchanged. A class that also matches the 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 The lookahead removed The lookahead is an item of a sequence of at least three items, so that the sequence keeps at least two and stays a tuple; it is not under a discard (-), a label or an operator; and it holds only literals, character classes, any-character, groups, sequences, choices, options and repetitions, so it holds no capture, cut, call, predicate, recovery or attribute
unreachable-rule The whole definition, with its attributes, removed No start rule reaches the rule, directly or through an inline action

Severities

Severity Meaning
error Certain: part of the grammar can never take effect
warning The fact is certain, but the grammar may still do what was meant
hint A suggestion about performance, mostly for incremental parsing; the grammar is correct as written

An error or a warning is proven from the grammar alone; when the linter cannot be sure, it reports nothing. The linter assumes that rule calls do not nest deeper than the nesting limit, which can make any call fail.

Checks

Check Severity Reports
shadowed-alternative error An alternative that can never match because an earlier one matches first
never-matches error Anchors that contradict their neighbors in a sequence; recursion without a base case
useless-lookahead error, warning !x that never succeeds (error), &x or !x that always succeeds (warning)
nullable-repetition warning A repetition whose element can match without consuming input
redundant-optional warning x? where x always succeeds
growing-variable warning A binding that can at least double the size of its variable on each recursion or iteration
unused-capture warning A capture whose value nothing reads
duplicate-capture warning A name captured twice in one match
char-class warning Overlapping ranges in a class; ranges such as [A-z] that include punctuation
unreachable-rule warning A rule that the start rule never calls, directly or indirectly
right-recursion hint A list written as right recursion
positions hint .Start or .End read in a rule that is used repeatedly
long-lookahead hint A lookahead that repeats . or a class that admits line breaks
super-linear hint A cause of cost that can grow faster than the input from the start rule, when the classification is requested
case-insensitive-literal hint A run of [sS]-style classes that spells a word
lint-directive warning A directive that names an unknown check or suppresses nothing

shadowed-alternative

An alternative of an ordered choice can never match if an earlier alternative matches wherever it could. It is reported in three cases:

  1. An earlier alternative always succeeds, so later ones are never tried: "+"? / "-".
  2. An earlier alternative is a prefix of a later one: "=" / "==", word / "true", ident / ident "(" args ")", [0-9]+ / "0x" hex+.
  3. An alternative is the same as an earlier one.

The same reasoning applies to the operand items of an Operators Rule, which form an ordered choice, and to its operators: the longest operator part wins, and among operators that match the same text the one declared first wins, so a second infix left "+" in one level is never selected.

Removing a dead alternative removes what it added to the expected items of a syntax error. In a left-recursive rule, the engine decides how to grow the recursion from the rules that each rule can call first, excluding bodies of zero-count repetitions and choice suffixes whose earlier alternative is proven to succeed on every input; possible recovery skip calls also take part. The linter does not prove every input-dependent dead branch, so removing or moving such a branch MAY change a parse if the branch calls a left-recursive rule before consuming input.

never-matches

A sequence that cannot match: items $$ "\n" (nothing follows the end of the input), header ^^ body (after header consumed input, this is not the beginning), text $ "x" ($ is followed by a line break or the end) and "a" ^ "b". A rule that can match only by matching itself first has no base case: rule list = item "," list, rule expr = expr "+" term. A rule that fails only because it calls such a rule is not reported. An explicit _|_ is never reported.

useless-lookahead

!"x"? never succeeds because "x"? always does (error). &ws* has no effect and !_|_ always succeeds (warnings).

nullable-repetition

item?*, word*+ and line* where line can match nothing. The engine ends a repetition at the first iteration that consumes no input, so it does not loop, but that iteration still adds an element to the list. A rule such as !$$ [^\n]* ("\n" / $$) cannot match nothing and is not reported.

redundant-optional

"x"*?. An optional lookahead (&x)? is not reported, because it adds a nil element that &x does not have.

growing-variable

A binding of a string variable whose expression joins the variable's own value at least twice, as in s := s + s, when the variable can hold a non-empty value and the bound value reaches a later evaluation of the same binding. That is so, outside a negative lookahead, when a sequence of the rule body has the binding in one element and a call that can reach its rule again in a later element, each at any depth of groups, options and choices, or when the binding is part of the element of a repetition in its rule. Captures, discards, #atomic, attributes and positive lookaheads, which keep the bindings made in them, do not change this, as groups do not. Each evaluation can then at least double the size of the variable, so that its size can grow exponentially with the input:

var s string = "a"

@start
rule R = "x" {s := s + s} R / ""

A variable can hold a non-empty value at the binding when its initial value is not empty, or when a binding of a non-empty value is visible there: one that precedes it in the same rule body, or in a rule that calls its rule, directly or indirectly, before the call. A binding in a rule that has already returned, such as one in T for R in main = T R, is not visible, because bindings in a called rule are not visible to its caller. A binding that extends the variable by a bounded piece, such as indent := indent + " ", is not reported. Nor is a binding after the recursive call, whose value no later evaluation of it sees, nor one in a different alternative of a choice from the call, as in R = {s := s + s} "q" / "x" R / "", because a failed alternative undoes its bindings before the next is tried. Bindings of int and bool variables are not reported; their effect on the number of combinations of values is a matter of cost, which super-linear reports. A fold accumulator that doubles, as acc + acc or concat(acc, acc) does in the lambda of foldl over a list that is not bounded, is not a binding (and a variable never holds a list); super-linear reports it as exponential, as it reports every growing binding.

unused-capture

A capture is reported when nothing can read its value: it is not referred to by the action or a predicate of its scope, and the rule has no action: the capture of a rule without an action names an element of the rule's value, and the list of a repetition whose action discards it is not read. A map or foldl parameter is not a capture.

duplicate-capture

The same name captured twice in one match, as in a:key "=" a:value. For nested captures the inner capture is stored first and the outer capture then overwrites it; the finding points to the outer capture and identifies the inner one. Alternatives of a choice exclude each other (a:x / a:y is not reported), and each iteration of a repetition is a scope of its own.

char-class

[a-zA-Za-f_] (overlap) and [A-z] (matches the characters between Z and a). The fix shows the class without the overlap or the punctuation.

unreachable-rule

A rule that the start rule never calls. The finding can be suppressed for a rule or disabled as a check, which is the way to declare further entry points.

right-recursion

rule lines = line lines? and rule args = expr ("," args)?: a list of n items nests n calls, and an edit of a Document evaluates again every call that begins before the edit. A prefix operator ("-" unary) is not reported; a right-associative binary operator written this way is.

positions

A rule that reads .Start or .End and is used repeatedly (in the element of a repetition or on a recursion cycle): a Document cannot shift its results past an edit, nor those of the rules that call it.

long-lookahead

A lookahead that repeats . or a negated class that admits line breaks, such as &([^!]* ($$ / "!")), can examine any amount of input. Lookaheads through other rules are not reported.

super-linear

A cause of a cost that can grow faster than the length of the input, found by the classification of the start rule. There is one finding per cause, at the scanning source, binding or operation that causes it. Its message names the class and the witness path, as positions of the rules and expressions on it. In

@start
rule main = (A / "a")* $$

rule A = "a"* "c"

the finding is at "a"* in A and says that the cost can grow as n²: when "c" fails, the repetition in main evaluates A again inside the input that "a"* examined.

Only polynomial and exponential causes are reported, whatever the class: a witness that the cost can grow faster than the input, such as a growing variable, a copy of a value of its own recursion, or a scan that can start again inside the input that it examined. The finding is a hint because these causes can be pessimistic: no slow input need exist. A reason for the class unknown is not reported, because it is no such witness, only a condition for linear cost that the classifier cannot establish; the reasons are shown with the classification.

The check runs only when the classification is requested, with -classify or lint.Config.Classify; otherwise it reports nothing, whatever the class. The bindings that growing-variable reports are also exponential causes here; that warning needs no request.

case-insensitive-literal

Two or more consecutive classes in a sequence that each match one ASCII letter in both cases, such as [sS] [eE] [lL] [eE] [cC] [tT], spell a word case-insensitively. Write "select"i (or "select" #ignorecase). Any other item between classes ends the run.

Suppressing Findings

A comment that starts with lint:ignore followed by check names separated by commas, and an optional reason, suppresses their findings.

Placement Scope
In the comments before a definition The whole rule
Elsewhere The line of the comment, if the comment ends the line, and the next line
// lint:file-ignore check reason The whole grammar

A directive that names an unknown check, or that suppresses nothing, is reported as lint-directive.

Validation and Errors

Condition Result
The grammar does not compile lint.Config.Run returns compiler.GrammarErrors and no findings
-disable or Config.Disable names an unknown check An error
A compiled grammar Error: lint needs the grammar source (.sxir or .json)

Compatibility and Support

The linter is available from the Go API and the sxir command. Generated parsers do not include it. The linter does not find what it cannot prove (a choice whose alternatives start with overlapping characters, shadowing through predicates, an Operators Rule with level-restricted calls, or left-recursive rules), mistakes the compiler already rejects, anchors that conflict across rules, or the performance of a grammar on real input.

Conformance

The lint tests of the repository establish each check on positive and negative grammars, including that the checks do not report the grammars that they must not.