Expand description
Writing statements out of the rule table, which is the matcher run in the other direction.
The matcher walks the table over a token vector and decides where each rule started and stopped. This walks the same table with no tokens in hand and makes them up: at a choice it picks an alternative, at a repeat it picks a count, at an identifier it asks a catalog for a name. What comes out is a statement the grammar can produce, which is a much larger set than the statements anybody has written down.
It lives in the library rather than in a test because two things outside this crate need it. The
compatibility harness generates statements and runs them through both engines, and it depends on
rudb and on nothing else, so anything it cannot reach through the facade is a hole in the
facade. spec/sql/duckdb/10-generation-and-fuzzing.md section 10.2 is the argument for building
it at all.
Three things keep it from producing either a novel or the same four tokens forever.
Every node has a cost, which is the smallest number of tokens it can be written down in, and it is a fixpoint over the table computed once for the process. A choice weights its alternatives by that cost, so the cheap ones are picked more often and the expression grammar does not run away down its own left hand side. It is also what guarantees termination: once a statement is over budget or a rule has come round too often, every choice takes its cheapest alternative, every optional is skipped and every repeat goes round once, and the cheapest expansion of anything is finite by construction.
The recursion bound counts how many times one rule is on the path rather than how long the path
is, which is not the same thing in this grammar and the difference is not subtle. The expression
rules are a chain of about twenty, one per precedence level, and a plain a + b walks the whole
chain, so a depth bound tight enough to stop nesting is spent before it reaches a leaf and every
leaf comes out as the cheapest literal there is. The first version of this had one and wrote
several hundred expressions without a single column reference in any of them.
Names come from a catalog rather than from a pool of letters, and one statement draws its columns from one table. Neither of those makes the statement mean anything, since a PEG walk has no idea what a scope is, but both of them mean a generated statement has a real chance of binding rather than dying on the first name, and a statement that dies on the first name tests the tokenizer and nothing else.
What it does not promise is that everything it writes parses. Ordered choice is the reason: this
can pick the fifth alternative of a choice and write text the matcher settles on the second
alternative of, and then the rest of the sequence has nothing to match against. That is a
property of every PEG generator and not a bug here. The share that parses is measured rather
than assumed, by the_generator_writes_statements_that_parse, and the interesting inputs are
the ones that do not, because our answer and DuckDB’s answer on those is exactly the level two
statement number the harness reports.