rudb_parse/
ast.rs

1//! rudb's abstract syntax tree.
2//!
3//! The parse tree the matcher produces is DuckDB's grammar, faithfully. That is the point of it and
4//! it is also why nothing downstream should read it: a bump of the vendored grammar is allowed to
5//! rename `BetweenInLikeExpression`, and if the binder is matching on that name then the bump is a
6//! rewrite. This module is the boundary. It is ours, it changes when we decide it changes, and
7//! `transform` is the one place that knows both shapes.
8//!
9//! Everything is an arena with `u32` indices, per `spec/04-architecture.md` section 4.5. There is
10//! no `Box` and no `Vec` inside a node. A list of children is a [`Slice`] into a side vector, which
11//! means a node is a fixed size, the whole tree is a handful of allocations, and walking it is a
12//! sequential read rather than a pointer chase per node. It also means an `Ast` is `Clone` and
13//! `Send` without any thought, and that a subtree can be addressed by a `u32` in a plan or an
14//! error without borrowing anything.
15//!
16//! The one cost is that you cannot hold a reference to a node and index the arena at the same time,
17//! so the code reads a node out by value first. Nodes are small and `Copy`, so that is a register
18//! move.
19
20use crate::matcher::NONE;
21
22/// A run of items in one of the side vectors.
23///
24/// Empty is `len == 0`, and `start` is then meaningless rather than wrong. There is no `Option`
25/// wrapper because an absent list and an empty list are the same thing everywhere this is used.
26#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
27pub struct Slice {
28    /// The first item.
29    pub start: u32,
30    /// How many items.
31    pub len: u32,
32}
33
34impl Slice {
35    /// Whether the run is empty.
36    pub const fn is_empty(self) -> bool {
37        self.len == 0
38    }
39
40    /// The run as a range, for indexing the backing vector.
41    pub const fn range(self) -> std::ops::Range<usize> {
42        self.start as usize..(self.start + self.len) as usize
43    }
44}
45
46/// An index into `Ast::strings`.
47pub type StrRef = u32;
48/// An index into `Ast::exprs`.
49pub type ExprRef = u32;
50/// An index into `Ast::sources`.
51pub type SourceRef = u32;
52/// An index into `Ast::queries`.
53pub type QueryRef = u32;
54/// An index into `Ast::selects`.
55pub type SelectRef = u32;
56
57/// One statement.
58///
59/// Only `SELECT` is here, which is what M0 needs. The other twenty six statement kinds the grammar
60/// reaches are a transform error naming the rule rather than a variant that nothing fills in, so
61/// that adding one is a compile error somewhere useful rather than a silent `todo!()`.
62#[derive(Debug, Clone, Copy, PartialEq, Eq)]
63pub enum Statement {
64    /// A query, meaning a `SELECT` or a set operation over two of them.
65    Query(QueryRef),
66}
67
68/// A query: a body, plus the modifiers that apply to whatever the body produced.
69///
70/// The split is the grammar's, not an invention. `SelectStatementInternal <- WithClause?
71/// SelectSetOpChain ResultModifiers?` puts `ORDER BY` and `LIMIT` outside the set operator chain,
72/// which is the only place they can go and be right: `a UNION b ORDER BY x` sorts the union and not
73/// the second half of it. Hanging them off `Select` instead would have made that unrepresentable.
74#[derive(Debug, Clone, Copy, PartialEq, Eq)]
75pub struct Query {
76    /// What produces the rows.
77    pub body: QueryBody,
78    /// The `ORDER BY` list, as a run of [`OrderItem`].
79    pub order_by: Slice,
80    /// Whether the clause was `ORDER BY ALL`.
81    pub order_by_all: bool,
82    /// The `LIMIT` expression, or `NONE`.
83    pub limit: ExprRef,
84    /// Whether the limit was a percentage rather than a row count.
85    pub limit_percent: bool,
86    /// The `OFFSET` expression, or `NONE`.
87    pub offset: ExprRef,
88}
89
90impl Query {
91    /// A query with no modifiers on it.
92    pub const fn bare(body: QueryBody) -> Self {
93        Self {
94            body,
95            order_by: Slice { start: 0, len: 0 },
96            order_by_all: false,
97            limit: NONE,
98            limit_percent: false,
99            offset: NONE,
100        }
101    }
102}
103
104/// What produces the rows of a query.
105#[derive(Debug, Clone, Copy, PartialEq, Eq)]
106pub enum QueryBody {
107    /// One `SELECT ... FROM ... WHERE ...` block.
108    Select(SelectRef),
109    /// `UNION`, `EXCEPT` or `INTERSECT` over two queries.
110    SetOp {
111        /// Which operator.
112        op: SetOp,
113        /// Whether duplicates survive.
114        quantifier: Quantifier,
115        /// Whether the columns are matched up by name rather than by position.
116        by_name: bool,
117        /// The query on the left.
118        left: QueryRef,
119        /// The query on the right.
120        right: QueryRef,
121    },
122}
123
124/// Which set operator.
125#[derive(Debug, Clone, Copy, PartialEq, Eq)]
126pub enum SetOp {
127    /// `UNION`.
128    Union,
129    /// `EXCEPT`.
130    Except,
131    /// `INTERSECT`.
132    Intersect,
133}
134
135/// Whether a set operator or an aggregate keeps duplicates.
136///
137/// `Unstated` is not the same as `All` even though the two agree for `UNION`, because they disagree
138/// for `INTERSECT` in some dialects and because an error message that says what was written is
139/// better than one that says what it was taken to mean.
140#[derive(Debug, Clone, Copy, PartialEq, Eq)]
141pub enum Quantifier {
142    /// Neither word was written.
143    Unstated,
144    /// `ALL`.
145    All,
146    /// `DISTINCT`.
147    Distinct,
148}
149
150/// What the `DISTINCT` clause of a select said.
151#[derive(Debug, Clone, Copy, PartialEq, Eq)]
152pub enum Distinct {
153    /// No clause, or the no-op `SELECT ALL`.
154    No,
155    /// `SELECT DISTINCT`.
156    Yes,
157    /// `SELECT DISTINCT ON (a, b)`, holding the expressions in the parentheses.
158    On(Slice),
159}
160
161/// One select block.
162///
163/// Every optional expression is `NONE` when it is absent rather than an `Option<u32>`, which keeps
164/// the struct at forty bytes and keeps the absent case spelled the same way it is spelled in the
165/// parse tree arena.
166#[derive(Debug, Clone, Copy, PartialEq, Eq)]
167pub struct Select {
168    /// The `DISTINCT` clause.
169    pub distinct: Distinct,
170    /// The target list, as a run of [`Target`].
171    pub targets: Slice,
172    /// The `FROM` list, as a run of [`SourceRef`]. Several entries mean a cross product.
173    pub from: Slice,
174    /// The `WHERE` expression, or `NONE`.
175    pub filter: ExprRef,
176    /// The `GROUP BY` list, as a run of [`ExprRef`].
177    pub group_by: Slice,
178    /// Whether the clause was `GROUP BY ALL`.
179    pub group_by_all: bool,
180    /// The `HAVING` expression, or `NONE`.
181    pub having: ExprRef,
182}
183
184impl Select {
185    /// An empty select, which is what the transformer fills in from.
186    pub const fn empty() -> Self {
187        Self {
188            distinct: Distinct::No,
189            targets: Slice { start: 0, len: 0 },
190            from: Slice { start: 0, len: 0 },
191            filter: NONE,
192            group_by: Slice { start: 0, len: 0 },
193            group_by_all: false,
194            having: NONE,
195        }
196    }
197}
198
199/// One entry of a target list.
200#[derive(Debug, Clone, Copy, PartialEq, Eq)]
201pub struct Target {
202    /// What is being selected.
203    pub expr: ExprRef,
204    /// The alias, or `NONE`. The binder invents one when there is none, because what it invents
205    /// depends on the expression and that is a binder question rather than a parser question.
206    pub alias: StrRef,
207}
208
209/// One entry of an order by list.
210#[derive(Debug, Clone, Copy, PartialEq, Eq)]
211pub struct OrderItem {
212    /// What to sort on.
213    pub expr: ExprRef,
214    /// The direction.
215    pub order: Order,
216    /// Where nulls go.
217    pub nulls: Nulls,
218}
219
220/// Sort direction, with the unwritten case kept apart from the default it resolves to.
221#[derive(Debug, Clone, Copy, PartialEq, Eq)]
222pub enum Order {
223    /// Nothing was written.
224    Unstated,
225    /// `ASC` or `ASCENDING`.
226    Ascending,
227    /// `DESC` or `DESCENDING`.
228    Descending,
229}
230
231/// Null placement in a sort.
232#[derive(Debug, Clone, Copy, PartialEq, Eq)]
233pub enum Nulls {
234    /// Nothing was written, so the session default applies.
235    Unstated,
236    /// `NULLS FIRST`.
237    First,
238    /// `NULLS LAST`.
239    Last,
240}
241
242/// One entry in a `FROM` clause, which is a tree because joins nest.
243#[derive(Debug, Clone, Copy, PartialEq, Eq)]
244pub enum Source {
245    /// A named table, possibly qualified by schema and catalog.
246    Table {
247        /// The name, as a run of [`StrRef`] in `Ast::parts`, outermost first.
248        name: Slice,
249        /// The alias, or `NONE`.
250        alias: StrRef,
251        /// Column aliases from `AS t(a, b)`, as a run of [`StrRef`].
252        columns: Slice,
253    },
254    /// A parenthesised query in the `FROM` clause.
255    Subquery {
256        /// The query.
257        query: QueryRef,
258        /// The alias, or `NONE`.
259        alias: StrRef,
260        /// Column aliases, as a run of [`StrRef`].
261        columns: Slice,
262    },
263    /// Two sources joined.
264    Join {
265        /// The left side.
266        left: SourceRef,
267        /// The right side.
268        right: SourceRef,
269        /// Which join.
270        kind: JoinKind,
271        /// Whether it was written `NATURAL`.
272        natural: bool,
273        /// The `ON` expression, or `NONE`.
274        on: ExprRef,
275        /// The `USING` column list, as a run of [`StrRef`].
276        using: Slice,
277    },
278}
279
280/// Which join.
281#[derive(Debug, Clone, Copy, PartialEq, Eq)]
282pub enum JoinKind {
283    /// `[INNER] JOIN`.
284    Inner,
285    /// `LEFT [OUTER] JOIN`.
286    Left,
287    /// `RIGHT [OUTER] JOIN`.
288    Right,
289    /// `FULL [OUTER] JOIN`.
290    Full,
291    /// `SEMI JOIN`.
292    Semi,
293    /// `ANTI JOIN`.
294    Anti,
295    /// `CROSS JOIN`.
296    Cross,
297    /// `POSITIONAL JOIN`, which is DuckDB's own and pairs rows by ordinal.
298    Positional,
299}
300
301/// One expression.
302///
303/// Twenty four bytes, which is the widest variant rounded up. The precedence chain in the grammar
304/// does not survive into here: twenty levels of `X <- Y Tail*` become one [`Expr::Binary`] tree,
305/// because the levels exist to make the grammar unambiguous and mean nothing afterwards.
306#[derive(Debug, Clone, Copy, PartialEq, Eq)]
307pub enum Expr {
308    /// `*`, or `t.*` with a qualifier.
309    Star {
310        /// The qualifier, as a run of [`StrRef`], empty for a bare star.
311        qualifier: Slice,
312    },
313    /// A column reference, qualified or not.
314    Column {
315        /// The name, as a run of [`StrRef`], outermost first, so `s.t.a` is three parts.
316        name: Slice,
317    },
318    /// A literal, kept as the text that was written.
319    Literal {
320        /// Which kind.
321        kind: LiteralKind,
322        /// The text, with quotes stripped and escapes resolved for a string, `NONE` for a keyword
323        /// literal like `NULL` where the kind already says everything.
324        text: StrRef,
325    },
326    /// A prefix or postfix operator.
327    Unary {
328        /// Which operator.
329        op: UnaryOp,
330        /// What it applies to.
331        operand: ExprRef,
332    },
333    /// An infix operator.
334    Binary {
335        /// Which operator.
336        op: BinaryOp,
337        /// The left operand.
338        left: ExprRef,
339        /// The right operand.
340        right: ExprRef,
341    },
342    /// A function call.
343    Function {
344        /// The name, as a run of [`StrRef`], so `main.count` is two parts.
345        name: Slice,
346        /// The arguments, as a run of [`ExprRef`].
347        args: Slice,
348        /// Whether the call said `DISTINCT`.
349        distinct: bool,
350    },
351    /// `CAST(x AS t)` or `TRY_CAST(x AS t)`.
352    Cast {
353        /// What is being cast.
354        operand: ExprRef,
355        /// The target type, as the text it was written with. Parsing it is `rudb-common`'s job and
356        /// doing it here would put the type system in the parser.
357        ty: StrRef,
358        /// Whether a failure yields null rather than an error.
359        try_cast: bool,
360    },
361    /// `CASE`, searched or simple.
362    Case {
363        /// The operand of a simple `CASE x WHEN`, or `NONE` for a searched one.
364        operand: ExprRef,
365        /// The arms, as a run of [`CaseArm`].
366        arms: Slice,
367        /// The `ELSE`, or `NONE`.
368        otherwise: ExprRef,
369    },
370    /// `x BETWEEN a AND b`.
371    Between {
372        /// What is being tested.
373        operand: ExprRef,
374        /// The lower bound.
375        low: ExprRef,
376        /// The upper bound.
377        high: ExprRef,
378        /// Whether it was written `NOT BETWEEN`.
379        negated: bool,
380    },
381    /// `x IN (a, b, c)`.
382    In {
383        /// What is being tested.
384        operand: ExprRef,
385        /// The list, as a run of [`ExprRef`].
386        list: Slice,
387        /// Whether it was written `NOT IN`.
388        negated: bool,
389    },
390    /// A parenthesised list of more than one expression, which is a row value.
391    Row {
392        /// The items, as a run of [`ExprRef`].
393        items: Slice,
394    },
395    /// A scalar subquery, `(SELECT ...)` where an expression is expected.
396    Subquery {
397        /// The query.
398        query: QueryRef,
399    },
400}
401
402/// One `WHEN a THEN b`.
403#[derive(Debug, Clone, Copy, PartialEq, Eq)]
404pub struct CaseArm {
405    /// The `WHEN`.
406    pub when: ExprRef,
407    /// The `THEN`.
408    pub then: ExprRef,
409}
410
411/// Which literal.
412#[derive(Debug, Clone, Copy, PartialEq, Eq)]
413pub enum LiteralKind {
414    /// A number, kept as text because the width it wants depends on where it lands.
415    Number,
416    /// A string.
417    String,
418    /// `NULL`.
419    Null,
420    /// `TRUE`.
421    True,
422    /// `FALSE`.
423    False,
424}
425
426/// A prefix or postfix operator.
427#[derive(Debug, Clone, Copy, PartialEq, Eq)]
428pub enum UnaryOp {
429    /// `NOT x`.
430    Not,
431    /// `-x`.
432    Negate,
433    /// `+x`, which is a no-op that still has to survive to the binder so that `+'a'` errors.
434    Plus,
435    /// `~x`.
436    BitNot,
437    /// `x!`.
438    Factorial,
439    /// `x IS NULL` or `x ISNULL`.
440    IsNull,
441    /// `x IS NOT NULL` or `x NOTNULL`.
442    IsNotNull,
443    /// `x IS TRUE`.
444    IsTrue,
445    /// `x IS NOT TRUE`.
446    IsNotTrue,
447    /// `x IS FALSE`.
448    IsFalse,
449    /// `x IS NOT FALSE`.
450    IsNotFalse,
451    /// `x IS UNKNOWN`.
452    IsUnknown,
453    /// `x IS NOT UNKNOWN`.
454    IsNotUnknown,
455}
456
457/// An infix operator.
458///
459/// The list is the dialect and not a general idea of what operators are. `Named` is the one open
460/// door, because `OperatorLiteral` in the grammar takes any run of operator characters that is not
461/// already a token, and rejecting that here would reject SQL DuckDB accepts.
462#[derive(Debug, Clone, Copy, PartialEq, Eq)]
463pub enum BinaryOp {
464    /// `OR`.
465    Or,
466    /// `AND`.
467    And,
468    /// `=` or `==`.
469    Eq,
470    /// `!=` or `<>`.
471    NotEq,
472    /// `<`.
473    Lt,
474    /// `>`.
475    Gt,
476    /// `<=`.
477    LtEq,
478    /// `>=`.
479    GtEq,
480    /// `IS DISTINCT FROM`.
481    IsDistinctFrom,
482    /// `IS NOT DISTINCT FROM`.
483    IsNotDistinctFrom,
484    /// `+`.
485    Add,
486    /// `-`.
487    Subtract,
488    /// `*`.
489    Multiply,
490    /// `/`.
491    Divide,
492    /// `//`, integer division.
493    IntegerDivide,
494    /// `%`.
495    Modulo,
496    /// `^` or `**`.
497    Power,
498    /// `&`.
499    BitAnd,
500    /// `|`.
501    BitOr,
502    /// `<<`.
503    ShiftLeft,
504    /// `>>`.
505    ShiftRight,
506    /// `||`.
507    Concat,
508    /// `LIKE` or `~~`.
509    Like,
510    /// `NOT LIKE` or `!~~`.
511    NotLike,
512    /// `ILIKE` or `~~*`.
513    ILike,
514    /// `NOT ILIKE` or `!~~*`.
515    NotILike,
516    /// `GLOB` or `~~~`.
517    Glob,
518    /// `SIMILAR TO`.
519    SimilarTo,
520    /// `!~`, which the grammar calls the not-similar-to operator.
521    NotSimilarTo,
522    /// `~`, a regex match.
523    Regex,
524    /// `~*`, a case insensitive regex match.
525    RegexInsensitive,
526    /// `!~*`, a negated case insensitive regex match.
527    NotRegexInsensitive,
528    /// `COLLATE`.
529    Collate,
530    /// `AT TIME ZONE`.
531    AtTimeZone,
532    /// `->`.
533    Arrow,
534    /// `->>`.
535    LongArrow,
536    /// `@>`, contains.
537    Contains,
538    /// `<@`, contained by.
539    ContainedBy,
540    /// `&&`, overlaps.
541    Overlaps,
542    /// `^@`, starts with.
543    StartsWith,
544    /// `<<=`, an inet operator.
545    InetContainedByOrEq,
546    /// `>>=`, an inet operator.
547    InetContainsOrEq,
548    /// An operator the dialect does not name, which DuckDB resolves as a binary function of that
549    /// name. `a <=> b` is the shape.
550    Named(StrRef),
551}
552
553/// A parsed statement or script, with every arena it points into.
554///
555/// Cheap to clone, cheap to send, and self contained: no index in here refers to anything outside
556/// it, and nothing in here borrows the query text. The text is copied into `strings` on the way in,
557/// which costs one allocation per distinct identifier and buys an `Ast` that outlives the string it
558/// came from.
559#[derive(Debug, Clone, Default, PartialEq, Eq)]
560pub struct Ast {
561    /// The statements in the script, in order.
562    pub statements: Vec<Statement>,
563    /// The query arena.
564    pub queries: Vec<Query>,
565    /// The select arena.
566    pub selects: Vec<Select>,
567    /// The expression arena.
568    pub exprs: Vec<Expr>,
569    /// The from-item arena.
570    pub sources: Vec<Source>,
571    /// Interned text. Identifiers keep the case they were written in, because DuckDB does not fold
572    /// it at any point, including for quoted identifiers.
573    pub strings: Vec<String>,
574    /// Backing store for every [`Slice`] of names.
575    pub parts: Vec<StrRef>,
576    /// Backing store for every [`Slice`] of expressions.
577    pub expr_lists: Vec<ExprRef>,
578    /// Backing store for every [`Slice`] of from items.
579    pub source_lists: Vec<SourceRef>,
580    /// Backing store for every [`Slice`] of target list entries.
581    pub targets: Vec<Target>,
582    /// Backing store for every [`Slice`] of order by entries.
583    pub order_items: Vec<OrderItem>,
584    /// Backing store for every [`Slice`] of case arms.
585    pub case_arms: Vec<CaseArm>,
586}
587
588impl Ast {
589    /// The text behind a [`StrRef`], or the empty string for `NONE`.
590    pub fn string(&self, index: StrRef) -> &str {
591        if index == NONE { "" } else { &self.strings[index as usize] }
592    }
593
594    /// The parts of a name, outermost first.
595    pub fn name(&self, slice: Slice) -> impl Iterator<Item = &str> {
596        self.parts[slice.range()].iter().map(|&part| self.string(part))
597    }
598
599    /// A name written back out with dots between the parts, for error messages and tests.
600    pub fn name_text(&self, slice: Slice) -> String {
601        self.name(slice).collect::<Vec<_>>().join(".")
602    }
603
604    /// One expression.
605    pub fn expr(&self, index: ExprRef) -> Expr {
606        self.exprs[index as usize]
607    }
608
609    /// One from item.
610    pub fn source(&self, index: SourceRef) -> Source {
611        self.sources[index as usize]
612    }
613
614    /// One query.
615    pub fn query(&self, index: QueryRef) -> Query {
616        self.queries[index as usize]
617    }
618
619    /// One select block.
620    pub fn select(&self, index: SelectRef) -> Select {
621        self.selects[index as usize]
622    }
623
624    /// The expressions of a list.
625    pub fn expr_list(&self, slice: Slice) -> &[ExprRef] {
626        &self.expr_lists[slice.range()]
627    }
628
629    /// The from items of a list.
630    pub fn source_list(&self, slice: Slice) -> &[SourceRef] {
631        &self.source_lists[slice.range()]
632    }
633
634    /// The entries of a target list.
635    pub fn target_list(&self, slice: Slice) -> &[Target] {
636        &self.targets[slice.range()]
637    }
638
639    /// The entries of an order by list.
640    pub fn order_list(&self, slice: Slice) -> &[OrderItem] {
641        &self.order_items[slice.range()]
642    }
643
644    /// The arms of a case.
645    pub fn arm_list(&self, slice: Slice) -> &[CaseArm] {
646        &self.case_arms[slice.range()]
647    }
648
649    /// How many nodes the whole tree is, across every arena.
650    ///
651    /// The number to watch when the transformer changes. A parse tree of five thousand nodes that
652    /// becomes an AST of thirty is the twenty precedence levels being thrown away, which is the
653    /// whole reason this module exists.
654    pub fn node_count(&self) -> usize {
655        self.queries.len() + self.selects.len() + self.exprs.len() + self.sources.len()
656    }
657}
rudb_parse/ast.rs

rudb_parse/
ast.rs
