Module matcher 

Walking the rule table over a token vector, producing a parse tree.

This is a PEG matcher and nothing more. It decides where every rule in the grammar started and stopped, and it does not know what any of them mean. Turning the tree into an AST is the transformer’s job, and keeping the two apart is what lets the grammar be vendored: a grammar bump changes the table and this file does not move.

Three things about it are worth knowing before reading it.

It has no Rust stack recursion. A PEG over a grammar with a thousand rules nests as deep as the query does, and a + (b + (c + ...)) nests as deep as the user cares to type. A recursive matcher blows the thread stack on input that is merely rude rather than adversarial, and it does it with a segfault rather than an error, so the recursion is an explicit Vec of frames with a cap on it and the cap reports a parser error like any other.

Failure does not truncate the arena. A choice that tries thirty alternatives builds and abandons tree nodes for twenty nine of them, and the obvious cleanup is to roll the arena back to where the alternative started. That is wrong here, because a memoized rule that succeeded inside a failed alternative keeps its memo entry, and the entry points at nodes in the arena. So abandoned nodes stay, unreferenced, and the arena is a bump allocator that is freed all at once. For a query that parses, the waste is small; for one that does not, it does not matter.

The FIRST filter is a superset test and only its negative answer is used. Statement is a choice of thirty six alternatives and upstream descends into each one far enough to fail. Here an alternative whose FIRST set does not contain the token in hand is skipped on one AND. A nullable node is never skipped, because it can match without looking at the token at all, which is why the guard tests the nullable bit before it tests the set. Both live in the node, so the guard and the work it guards read the same twenty four bytes.

spec/20-the-grammar.md sections 3, 5 and 6.

Structs

Children

The children of one node.

ParseNode

One node of the parse tree. Twenty bytes.

Tree

A parsed query.

Constants

NONE

No node.

Functions

parse

Parse a whole script.

parse_from

Parse from a named rule, for tests and for the differential harness.

parse_tokens

Parse tokens that have already been produced.