S2. The AST, the transformer and the refusal table
- Dominant language
- Mojo
- Stars
- 1
- Forks
- 0
- Avg merge
- 1h 31m
- Merged PRs (30d)
- 640
Description
Part of #304. Depends on S1.
The stage that turns a generic parse tree into something with SQL meaning, and the stage where the grammar's totality meets our partiality. S0 and S1 buy a parser that accepts everything DuckDB accepts. This issue decides what happens to the statements we cannot execute, and the answer has to be better than a syntax error and better than silence.
### Why there is a stage here at all
The parse tree has one node per grammar rule, which for an ordinary SELECT is dozens of nodes of pure syntax. Binding against that directly would tie the binder to grammar rule names, and a grammar bump would then break the binder rather than a small translation layer. The transformer is the shock absorber that keeps the S0 bump procedure a one day job.
For a sense of size, DuckDB's own transformer is 46 files and 2,817,088 bytes, of which about 2.3 MB is generated boilerplate for serialization, copy and equality, leaving roughly 500 KB hand written with `transform_expression.cpp` alone at 132 KB. We write less because we transform less, and the tier list below says how much less.
### Scope
- [x] The AST: three arenas for statements, table references and expressions, fixed size index referenced nodes, a token position on every node
- [x] The transformer, total over the grammar, dispatching on rule index through a jump table
- [x] Precedence flattening, collapsing the sixteen level rule chain into a binary tree with the right shape
- [x] The refusal table in `firepanda/sql/unsupported.mojo`
- [x] `firepanda.sql_support()`, which enumerates the refusals
- [x] The AST printer, written now rather than later
### The refusal
This is the most important part of the compatibility story and it is one paragraph.
When the transformer hits a rule it cannot represent, the result is not a syntax error and not a silent no-op. It is a not implemented error naming the feature, giving the position with a caret, saying what firepanda is instead, and linking the tracking issue. All four parts are mandatory and the third is the one that gets dropped, which is the one that stops the user filing the bug.
Every refusal is a table entry rather than a scattered raise, which means the refusal set can be enumerated. `sql_support()` returns it, the README compatibility table is generated from it, and the conformance harness can assert that a corpus failure outside the target directories failed for a refusal rather than for a crash or a wrong answer.
The prohibition that makes it work is that no statement may be parsed and then ignored. A `CREATE INDEX` that succeeds and does nothing is worse than one that refuses, because the user's next query is silently slow and they have no way to find out why.
### What transforms
Tier one is the analytical SELECT surface. WITH including RECURSIVE, FROM with every join type, WHERE, GROUP BY including ALL and GROUPING SETS and CUBE and ROLLUP, HAVING, QUALIFY, window specs, ORDER BY including ALL and null placement, LIMIT and OFFSET, set operations including UNION BY NAME, DISTINCT ON, subqueries in every position, LATERAL, VALUES, table functions, the whole expression grammar, star with EXCLUDE and REPLACE and RENAME, COLUMNS(), lateral column aliases and trailing commas.
Tier two is the frame shaped statements, each of which maps onto something a dataframe already does. CREATE TABLE AS, CREATE OR REPLACE VIEW, INSERT INTO SELECT, COPY TO, DESCRIBE, SUMMARIZE, EXPLAIN, PREPARE and EXECUTE, SET and RESET for the settings we honour, PIVOT and UNPIVOT.
Tier three parses and refuses by name. ATTACH and DETACH, BEGIN and COMMIT and ROLLBACK, CREATE INDEX, constraints, ALTER, CREATE SEQUENCE, CREATE MACRO, CREATE SECRET, INSTALL and LOAD, CALL, CHECKPOINT, EXPORT and IMPORT DATABASE, CONNECT.
UPDATE and DELETE sit awkwardly and stay refused for now. They are expressible over an immutable frame as a rewrite, they are not what a dataframe user reaches for, and half implementing them is worse than refusing.
### The printer pays for itself three times
Round trip is the transformer's main test, and parse then print then reparse over 4,046 files catches precedence bugs that nothing else catches. It is the fuzzer's oracle, since a random AST can be printed, parsed and compared. And it is how EXPLAIN shows filter and projection expressions, which is how a user debugs a pushdown that did not happen.
It is not a formatter and does not preserve the user's text. It prints fully parenthesized wherever precedence is involved, because a printer that minimizes parentheses is a second implementation of precedence and therefore a second place to get it wrong.
### Exit criteria
- [x] Parse, print, reparse is structurally stable across the whole corpus
- [x] Every rule index has a transformer case, enforced when the jump table is built rather than by a runtime fallthrough
- [x] Every tier three statement refuses by name with a position and a link, and none of them is silently accepted
- [x] `sql_support()` output matches the refusal table, and the README table is generated from it
### Depends on
S1.
Contributor guide
Research direction
Start with S1 and the checked scope in this issue, especially firepanda/sql/unsupported.mojo and the transformer, AST, printer, and sql_support() entry points. Validate parse-print-reparse stability across the 4,046-file corpus and confirm every tier-three statement refuses by name with a position and tracking link, with sql_support() and the generated README table matching the refusal table.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- sql
- Domain
- data-engineering, databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100