This improves the developer experience, especially with the new
gen_parser_oracle tool. My intent is for doc/langref/grammar.peg
to be the single source of truth, at least until we have an actual
language spec.
The separate copy in the separate zig-spec repo should not be considered
canonical as it is not tested against by CI.
This script parses a PEG grammar definition and generates a simple
recursive descent parser that recognizes that grammar.
The intent is to use this tool to generate an oracle against which
std.zig.Ast.parse() can be fuzz tested.
Unfortunately, generating a "smith" that can produce all possible valid
source code according to the PEG grammar definition does not seem
feasible due to PEG semantics. In particular, modeling the ordered
choice operator ('/') with a smith is problematic and seems to have
worst-case exponential runtime. Consider that `A / B` is equivalent to
`A / !A B`, it is not sufficient for a smith to choose an option from
the ordered choice at random and generate an input matched by that
sub-expression.
The current handwritten AstSmith.zig implementation does not match the
exact semantics of the PEG grammar. It has some hacks (see the `not_*`
variables) to work around specific instances of the general problem
with ordered choice described above but that is not an acceptable
long term solution in my opinion.
Generating the oracle for the fuzz test automatically from the PEG
makes the oracle correct by construction and gives us a single source of
truth: the PEG definition in the language spec.
(currently broken/failing)
The tokenizer does not yet perform UTF-8 validation. This violates the
language spec, but fixing it is out of scope for this branch. Leave
the intended language spec commented out in the grammar to be restored
when the tokenizer is fixed.
The tokenizer currently handles termination of comments/multiline string
literal lines differently from the grammar. The tokenizer forbids
e.g. tab characters at the end of comments before a newline and requires
\r to be directly followed by \n.
The tokenizer behavior here is intended, see c2b8afcac9.
The grammar needs to be fixed to match Parse.zig's "operator has
whitespace on one side but not the other" error, which is implemented
in Parse.zig using a constant lookbehind of 1.
However, standard PEG does not support lookbehind, which means our
approach to handling whitespace needs to be reworked.
Moving the `skip` non-terminal to be processed before each "token"
in the grammar rather than afterwards makes it possible to cleanly
match the Parse.zig operator whitespace handling, which will be
implemented in the next commit.
This commit is purely a refactor, no functional changes are intended.
Parse.zig requires whitespace to be either immediately before and after
a binary operator or neither before nor after the operator.
/// should not be parsed as a division operator followed by a comment
if it appears in a context where a division operator is accepted.
Add the missing negative lookahead to the SLASH token.
This matches the Parse.zig implementation, which has a special parse
error for this case:
> ambiguous use of '&&'; use 'and' for logical AND, or change whitespace
> to ' & &' for bitwise AND
This matches the behavior of Parse.zig
Original motivation: 95b95ea33e
Currently the grammar fails to enforce matching whitespace or lack of
whitespace around operators that are immediately preceded by a multiline
string literal and terminating newline.
Currently Parse.zig gives a parse error when the number of for loop
inputs does not match the number of for loop captures. This property
is however both overly complex to specify in the formal grammar and not
necessary to make further parsing possible.
This eliminates yet another discrepancy between the formal grammar
and Parse.zig implementation that has been discovered through fuzzing
with AFL++.
Commit 785fb1be11 made many redundant
changes to the grammar due to insufficient understanding of PEG
semantics. This commit reverts the most obviously redundant of those
changes.
The unbounded lookahead through e.g. !ExprSuffix still needs to be
reverted, but I want to do that in a future commit since that change
can't be reasoned about locally.
This unbounded lookahead is causing discrepancies between the Parse.zig
implementation and the PEG grammar. Also, unbounded lookahead should
never have been added to the PEG grammar in the first place.
It was added in 785fb1be11 which
demonstrated insufficient understanding of PEG semantics through many
redundant additions.
Whatever problem this unbounded lookahead attempted to solve needs to be
solved differently in any case.
This commit adds one test case found by AFL++ that fails before this
commit and now passes.
My attempt to handle this case in 6f151109b5fdf88eb8b has proven
insufficient, the test case added by this commit was failing.
Solve this with a "start of file" non-terminal in the PEG grammar,
which unfortunately isn't portable but much better reflects the actual
implementation and is much simpler.
It is not clear why this lookahead was added in the first place, but
it does not reflect the behavior of the Parse.zig implementation as
demonstrated with the new test case.
This is a first pass at consistency with Parse.zig on the statement
level, adding constant lookaheads to the grammar in several places
to match the behavior of Parse.zig.
This is a first pass at consistency with Parse.zig at the expression
level, adding constant lookaheads to the grammar in several places
to match the behavior of Parse.zig.
I also updated the comments in Parse.zig and refactored for clarity,
adding assertions in a few places but not intending any change in
behavior.
This commit also adds comments to the grammar and Parse.zig explaining
what needs to be done in practice to ensure that the grammar is LL(k)
and that the parser has worst-case linear runtime.
This is necessary to match the behavior of the parser. This is not a
complete list of of prefixes that cause the PEG to differ in behavior
from the parser, it is however difficult to determine this list by
reading the grammar alone and I plan to let the AFL++ fuzzer find
the missing items and fill it in while adding test cases to prevent
regression.
Eliminate unbounded lookahead, match Parse.zig behavior
Currently the grammar only allows exactly one pointer modifier order but
the Parse.zig implementation allows any order. However, the current
Parse.zig behavior of allowing any order while forbidding duplicate
modifiers would require a combinatorial explosion of grammar rules to
specify (currently 5! i.e. 120).
The simplest, most permissive grammar would remove the ordering
requirement and allow duplicate pointer modifiers. However, this would
unfortunately require a more complex AST data layout due to the child
nodes of align() and addrspace() modifiers. Since these are the only
pointer modifiers with child nodes and 2! is a perfectly reasonable
number, forbid duplicate align() and addrspace() modifiers to keep the
Ast data structure simple. In order to resolve the difference between
the formal grammar and parser implementation, allow duplicate
single-token modifiers (allowzero, const, volatile) in the grammar and
move the compile error for that case to AstGen.
Note that zig fmt will now silently remove duplicate single-token
modifiers, which I think is a nice little UX improvement.
This is useful to avoid unbounded recursion/iteration while fuzzing.
It's not interesting to learn that the parser hits a stack overflow when
fed a million open parens for example.
This now matches the behavior of Parse.zig
This is necessary for fuzz testing.
Consider the case where there is a parse error right at the beginning of
the file, followed by a valid declaration with a million nested parens.
The oracle will not skip this input due to the max depth being exceeded
since the oracle hits a parse error right away and does no recovery.
However, std.zig.Ast.parse() does recovery by default and will hit a
stack overflow rather than returning after the parser error.
Stack overflows are not interesting and we do not want the fuzzer to be
able to find them.
The tokenizer allows the unicode byte order mark (U+FEFF) to be present
at the start of the file, but the grammar currently does not.
Fixing the grammar requires some care due to how same-line doc comments
are forbidden in the grammar.
This is a case in which the grammar is currently not LL(k) and needs a
negative lookahead to prevent backtracking.
The new grammar is consistent with the Parse.zig implementation.
See the new test case for an example.
Currently the grammar doesn't forbid chained compare ops, see the new
test case which now passes.
The previous attempt to disable recovery was incomplete, consider for
example the recovery done when parsing an init list with a missing comma
.{a, b c}
The parser will currently add a warning about the missing comma and
continue parsing, which means that the fuzzer can hit stack overflows
.{a, b (((((((((((((((((((((((((((((((((((((((((((((((((((((((...
To fix this in general, make the warn functions return ParseError when
recovery is disabled.
Currently in a special case the parser will keep parsing after it has
been determined that there is a parse error in order to give a more
user-friendly error message.
However, this opens the parser up to stack overflow when fuzzing,
so skip the extra parsing and potentially better error message when
recovery is disabled.
To prevent the fuzzer from being able to reach stack overflows, we
need to give an error for invalid field/decl ordering before attempting
to parse the next field.
Currently the fuzzer is able to hit a stack overflow due to an invalid
bit align on a pointer type that is not a single item pointer:
[]align(a:(((((((((((((((((((((((((((((((((((((((...
To fix this, warn (and return error.ParseError if recovery is disabled)
before parsing the invalid bit align expression.
To prevent the fuzzer from being able to reach stack overflows, we
need to give an error for non-final varargs (...) before parsing the
next argument.
Currently the grammar doesn't function as intended and forbids
addrspace followed by align. Add the required negative lookaheads
to fix this as well as a test case.
Consider the new test case (found by AFL++):
test{for(0)|t|0,const w=0;}
Currently the grammar backtracks after failing to parse this with the
ForStatement rule and instead finds that the VarAssignStatement rule
is a match. This behavior is not LL(k) and inconsistent with the parser.
Add the required negative lookahead to eliminate this case and similar
cases.
No change in semantics intended
AFL++ is able to identify "hangs" as well as crashes and has found
several small inputs that take multiple seconds for the generated parser
to parse. This is because our PEG is not yet LL(k) despite recognizing
the same language as our handwritten LL(k) recursive descent parser.
Consider the PEG semantics for the following non-terminal:
ParamDeclList <- (ParamDecl COMMA)* (ParamDecl / DOT3 COMMA?)?
Here, the PEG checks twice if the last ParamDecl matches when
there is no trailing comma. Now, consider that the ParamDecl may
recursively contain a nested ParamDeclList, which in turn has ParamDecls
that contain further nested ParamDeclLists. It should be clear that this
results in worst-case exponential runtime.
This can be avoided by defining ParamDeclList using recursion instead of
the * operator.
This same pattern likely needs to be applied to other instances of this
pattern in the grammar.
The main motivation for fixing this is to improve fuzzer performance.
Additionally, using recursion rather than the * operator makes it easier
to translate from a PEG to a CFG, which I'm quite confident we will want
to do for the language specification eventually. A CFG would also allow
for smith-based fuzz testing to complement the oracle-based approach.
More rules are being made recursive for efficiency reasons, see the
previous commit.
For in depth reasoning, see commit 296b39c323
(grammar: fix ParamDeclList worst-case exponential time)
Currently these definitions do not result in an LL(k) generated parser.
For in depth reasoning, see commit 296b39c323
(grammar: fix ParamDeclList worst-case exponential time)
The current AstSmith is hand-written based on the formal PEG. However,
there is a significant impedance mismatch here since PEGs are a parser
specification not a language specification like CFGs. In other words,
it is not possible to directly translate an PEG into code that
efficiently generates all possible inputs recognized by the PEG.
Requirements for a new AstSmith:
1. Must be automatically generated based on the formal grammar
specification.
2. Must have linear runtime.
The current AstSmith is handwritten and unfortunately does not exactly
match the formal grammar. Tests like this need to have a single source
of truth and also need to be maintainable so I consider automatic
generation non-negotiable.
I did attempt to write a tool that takes a PEG as input and outputs an
AstSmith implementation. However, I no longer believe it is possible
to do a direct translation from an arbitrary PEG to an efficient
AstSmith, the lookahead and ordered choice features have worst-case
exponential runtime.
Conceptually, PEGs are simple to translate into parsers while CFGs
are simple to translate in to generators or smiths. I believe the
path forward is to translate our PEG into a CFG and generate a smith
based on that. I consider that task out of scope for this branch though.
This is a much cleaner way to expose the new option to disable recovery
added in 62720ad9f9. It also makes it possible to add further
options in the future without further breaking changes.