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/// An index into `Ast::create_tables`.
57pub type CreateTableRef = u32;
58/// An index into `Ast::create_views`.
59pub type CreateViewRef = u32;
60/// An index into `Ast::drop_tables`.
61pub type DropTableRef = u32;
62/// An index into `Ast::inserts`.
63pub type InsertRef = u32;
64
65/// One statement.
66///
67/// Five of the twenty seven the grammar reaches. The rest are a transform error naming the rule
68/// rather than a variant that nothing fills in, so that adding one is a compile error somewhere
69/// useful rather than a silent `todo!()`.
70#[derive(Debug, Clone, Copy, PartialEq, Eq)]
71pub enum Statement {
72 /// A query, meaning a `SELECT` or a set operation over two of them.
73 Query(QueryRef),
74 /// `CREATE TABLE`.
75 CreateTable(CreateTableRef),
76 /// `CREATE VIEW`.
77 CreateView(CreateViewRef),
78 /// `DROP TABLE` or `DROP VIEW`, which are one rule in the grammar and one statement here.
79 DropTable(DropTableRef),
80 /// `INSERT INTO`.
81 Insert(InsertRef),
82}
83
84/// `CREATE TABLE name (columns)` or `CREATE TABLE name AS query`.
85///
86/// Exactly one of `columns` and `query` says what the table is. A column list is the ordinary form
87/// and `query` is `CREATE TABLE AS`, where the columns come from what the query produced and the
88/// only thing the syntax contributes is optionally renaming them, which is `columns` with the types
89/// left as `NONE`.
90#[derive(Debug, Clone, Copy, PartialEq, Eq)]
91pub struct CreateTable {
92 /// The table name, as a run of [`Slice`] parts, outermost first.
93 pub name: Slice,
94 /// The column definitions, as a run of [`ColumnDef`].
95 pub columns: Slice,
96 /// The `AS` query, or `NONE`.
97 pub query: QueryRef,
98 /// Whether `IF NOT EXISTS` was written.
99 pub if_not_exists: bool,
100 /// Whether `OR REPLACE` was written.
101 pub or_replace: bool,
102 /// Whether `TEMP` or `TEMPORARY` was written.
103 pub temporary: bool,
104}
105
106/// One column of a `CREATE TABLE`.
107///
108/// The type is the text as written rather than a resolved type, because resolving a type is the
109/// binder's job and this crate is syntax. `VARCHAR(10)` and `STRUCT(a INTEGER)` reach the binder
110/// as themselves.
111#[derive(Debug, Clone, Copy, PartialEq, Eq)]
112pub struct ColumnDef {
113 /// The column name.
114 pub name: StrRef,
115 /// The type as written, or `NONE` when the definition had none, which only `CREATE TABLE AS`
116 /// allows.
117 pub ty: StrRef,
118 /// Whether `NOT NULL` was written.
119 pub not_null: bool,
120}
121
122/// `CREATE VIEW name (columns) AS query`.
123///
124/// The body is kept twice over, as a bound reference into this same arena and as the text that was
125/// written. Both are needed and they are needed for different things. The reference is what binds
126/// the body at creation, which is where a view over a table that is not there is refused. The text
127/// is what the catalog keeps, because a view is bound again at every reference rather than frozen
128/// at creation: a view over `SELECT * FROM t` follows `t` when a column is added to it, which was
129/// measured, and the only way to follow it is to have the query to bind again.
130#[derive(Debug, Clone, Copy, PartialEq, Eq)]
131pub struct CreateView {
132 /// The view name, as a run of [`Slice`] parts, outermost first.
133 pub name: Slice,
134 /// The column aliases, as a run of parts, empty when the statement wrote no list.
135 pub columns: Slice,
136 /// The body.
137 pub query: QueryRef,
138 /// The body as it was written, which is what the catalog keeps.
139 pub sql: StrRef,
140 /// Whether `IF NOT EXISTS` was written.
141 pub if_not_exists: bool,
142 /// Whether `OR REPLACE` was written.
143 pub or_replace: bool,
144 /// Whether `TEMP` or `TEMPORARY` was written.
145 pub temporary: bool,
146}
147
148/// `DROP TABLE a, b` or `DROP VIEW a, b`.
149#[derive(Debug, Clone, Copy, PartialEq, Eq)]
150pub struct DropTable {
151 /// The names, as a run of [`Slice`] into `Ast::name_lists`, each of which is a run of parts.
152 pub names: Slice,
153 /// Whether `IF EXISTS` was written.
154 pub if_exists: bool,
155 /// Whether `VIEW` was written where `TABLE` could have been. Dropping one as the other is an
156 /// error rather than a synonym, so which word was written has to survive the transform.
157 pub view: bool,
158}
159
160/// `INSERT INTO name (columns) query`.
161#[derive(Debug, Clone, Copy, PartialEq, Eq)]
162pub struct Insert {
163 /// The table name, as a run of parts, outermost first.
164 pub name: Slice,
165 /// The column list, as a run of parts, empty when the statement did not write one.
166 pub columns: Slice,
167 /// What produces the rows, which is a `VALUES` clause or any other query.
168 pub source: QueryRef,
169}
170
171/// A query: a body, plus the modifiers that apply to whatever the body produced.
172///
173/// The split is the grammar's, not an invention. `SelectStatementInternal <- WithClause?
174/// SelectSetOpChain ResultModifiers?` puts `ORDER BY` and `LIMIT` outside the set operator chain,
175/// which is the only place they can go and be right: `a UNION b ORDER BY x` sorts the union and not
176/// the second half of it. Hanging them off `Select` instead would have made that unrepresentable.
177#[derive(Debug, Clone, Copy, PartialEq, Eq)]
178pub struct Query {
179 /// What produces the rows.
180 pub body: QueryBody,
181 /// The `ORDER BY` list, as a run of [`OrderItem`].
182 pub order_by: Slice,
183 /// Whether the clause was `ORDER BY ALL`.
184 pub order_by_all: bool,
185 /// The `LIMIT` expression, or `NONE`.
186 pub limit: ExprRef,
187 /// Whether the limit was a percentage rather than a row count.
188 pub limit_percent: bool,
189 /// The `OFFSET` expression, or `NONE`.
190 pub offset: ExprRef,
191}
192
193impl Query {
194 /// A query with no modifiers on it.
195 pub const fn bare(body: QueryBody) -> Self {
196 Self {
197 body,
198 order_by: Slice { start: 0, len: 0 },
199 order_by_all: false,
200 limit: NONE,
201 limit_percent: false,
202 offset: NONE,
203 }
204 }
205}
206
207/// What produces the rows of a query.
208#[derive(Debug, Clone, Copy, PartialEq, Eq)]
209pub enum QueryBody {
210 /// One `SELECT ... FROM ... WHERE ...` block.
211 Select(SelectRef),
212 /// `UNION`, `EXCEPT` or `INTERSECT` over two queries.
213 SetOp {
214 /// Which operator.
215 op: SetOp,
216 /// Whether duplicates survive.
217 quantifier: Quantifier,
218 /// Whether the columns are matched up by name rather than by position.
219 by_name: bool,
220 /// The query on the left.
221 left: QueryRef,
222 /// The query on the right.
223 right: QueryRef,
224 },
225 /// `VALUES (1, 'a'), (2, 'b')`, as a run of [`Slice`] in `Ast::rows`.
226 ///
227 /// A row count and a column count and nothing else, so it is a query body rather than a
228 /// statement of its own. That is also what makes `INSERT INTO t VALUES (1)` and
229 /// `INSERT INTO t SELECT 1` the same shape by the time anything downstream sees them, which is
230 /// the reason the insert walker does not have two arms.
231 Values(Slice),
232}
233
234/// Which set operator.
235#[derive(Debug, Clone, Copy, PartialEq, Eq)]
236pub enum SetOp {
237 /// `UNION`.
238 Union,
239 /// `EXCEPT`.
240 Except,
241 /// `INTERSECT`.
242 Intersect,
243}
244
245/// Whether a set operator or an aggregate keeps duplicates.
246///
247/// `Unstated` is not the same as `All` even though the two agree for `UNION`, because they disagree
248/// for `INTERSECT` in some dialects and because an error message that says what was written is
249/// better than one that says what it was taken to mean.
250#[derive(Debug, Clone, Copy, PartialEq, Eq)]
251pub enum Quantifier {
252 /// Neither word was written.
253 Unstated,
254 /// `ALL`.
255 All,
256 /// `DISTINCT`.
257 Distinct,
258}
259
260/// What the `DISTINCT` clause of a select said.
261#[derive(Debug, Clone, Copy, PartialEq, Eq)]
262pub enum Distinct {
263 /// No clause, or the no-op `SELECT ALL`.
264 No,
265 /// `SELECT DISTINCT`.
266 Yes,
267 /// `SELECT DISTINCT ON (a, b)`, holding the expressions in the parentheses.
268 On(Slice),
269}
270
271/// One select block.
272///
273/// Every optional expression is `NONE` when it is absent rather than an `Option<u32>`, which keeps
274/// the struct at forty bytes and keeps the absent case spelled the same way it is spelled in the
275/// parse tree arena.
276#[derive(Debug, Clone, Copy, PartialEq, Eq)]
277pub struct Select {
278 /// The `DISTINCT` clause.
279 pub distinct: Distinct,
280 /// The target list, as a run of [`Target`].
281 pub targets: Slice,
282 /// The `FROM` list, as a run of [`SourceRef`]. Several entries mean a cross product.
283 pub from: Slice,
284 /// The `WHERE` expression, or `NONE`.
285 pub filter: ExprRef,
286 /// The `GROUP BY` list, as a run of [`ExprRef`].
287 pub group_by: Slice,
288 /// Whether the clause was `GROUP BY ALL`.
289 pub group_by_all: bool,
290 /// The `HAVING` expression, or `NONE`.
291 pub having: ExprRef,
292}
293
294impl Select {
295 /// An empty select, which is what the transformer fills in from.
296 pub const fn empty() -> Self {
297 Self {
298 distinct: Distinct::No,
299 targets: Slice { start: 0, len: 0 },
300 from: Slice { start: 0, len: 0 },
301 filter: NONE,
302 group_by: Slice { start: 0, len: 0 },
303 group_by_all: false,
304 having: NONE,
305 }
306 }
307}
308
309/// One entry of a target list.
310#[derive(Debug, Clone, Copy, PartialEq, Eq)]
311pub struct Target {
312 /// What is being selected.
313 pub expr: ExprRef,
314 /// The alias, or `NONE`. The binder invents one when there is none, because what it invents
315 /// depends on the expression and that is a binder question rather than a parser question.
316 pub alias: StrRef,
317}
318
319/// One entry of an order by list.
320#[derive(Debug, Clone, Copy, PartialEq, Eq)]
321pub struct OrderItem {
322 /// What to sort on.
323 pub expr: ExprRef,
324 /// The direction.
325 pub order: Order,
326 /// Where nulls go.
327 pub nulls: Nulls,
328}
329
330/// Sort direction, with the unwritten case kept apart from the default it resolves to.
331#[derive(Debug, Clone, Copy, PartialEq, Eq)]
332pub enum Order {
333 /// Nothing was written.
334 Unstated,
335 /// `ASC` or `ASCENDING`.
336 Ascending,
337 /// `DESC` or `DESCENDING`.
338 Descending,
339}
340
341/// Null placement in a sort.
342#[derive(Debug, Clone, Copy, PartialEq, Eq)]
343pub enum Nulls {
344 /// Nothing was written, so the session default applies.
345 Unstated,
346 /// `NULLS FIRST`.
347 First,
348 /// `NULLS LAST`.
349 Last,
350}
351
352/// One entry in a `FROM` clause, which is a tree because joins nest.
353#[derive(Debug, Clone, Copy, PartialEq, Eq)]
354pub enum Source {
355 /// A named table, possibly qualified by schema and catalog.
356 Table {
357 /// The name, as a run of [`StrRef`] in `Ast::parts`, outermost first.
358 name: Slice,
359 /// The alias, or `NONE`.
360 alias: StrRef,
361 /// Column aliases from `AS t(a, b)`, as a run of [`StrRef`].
362 columns: Slice,
363 },
364 /// A parenthesised query in the `FROM` clause.
365 Subquery {
366 /// The query.
367 query: QueryRef,
368 /// The alias, or `NONE`.
369 alias: StrRef,
370 /// Column aliases, as a run of [`StrRef`].
371 columns: Slice,
372 },
373 /// A function call where a table goes, such as `range(10)`.
374 ///
375 /// Held with the name as a qualified run rather than a single string, because `main.range(10)`
376 /// is legal and a function in a schema that does not exist has to say so rather than being
377 /// looked up unqualified and found.
378 Function {
379 /// The name, as a run of [`StrRef`] in `Ast::parts`, outermost first.
380 name: Slice,
381 /// The arguments, as a run of [`Target`] where the alias is the parameter name and is
382 /// `NONE` for a positional one.
383 args: Slice,
384 /// The alias, or `NONE`.
385 alias: StrRef,
386 /// Column aliases from `AS t(a, b)`, as a run of [`StrRef`].
387 columns: Slice,
388 },
389 /// A `VALUES` in the `FROM` clause.
390 Values {
391 /// The rows, as a run of [`Slice`] in `Ast::rows`.
392 rows: Slice,
393 /// The alias, or `NONE`.
394 alias: StrRef,
395 /// Column aliases, as a run of [`StrRef`].
396 columns: Slice,
397 },
398 /// Two sources joined.
399 Join {
400 /// The left side.
401 left: SourceRef,
402 /// The right side.
403 right: SourceRef,
404 /// Which join.
405 kind: JoinKind,
406 /// Whether it was written `NATURAL`.
407 natural: bool,
408 /// The `ON` expression, or `NONE`.
409 on: ExprRef,
410 /// The `USING` column list, as a run of [`StrRef`].
411 using: Slice,
412 },
413}
414
415/// Which join.
416#[derive(Debug, Clone, Copy, PartialEq, Eq)]
417pub enum JoinKind {
418 /// `[INNER] JOIN`.
419 Inner,
420 /// `LEFT [OUTER] JOIN`.
421 Left,
422 /// `RIGHT [OUTER] JOIN`.
423 Right,
424 /// `FULL [OUTER] JOIN`.
425 Full,
426 /// `SEMI JOIN`.
427 Semi,
428 /// `ANTI JOIN`.
429 Anti,
430 /// `CROSS JOIN`.
431 Cross,
432 /// `POSITIONAL JOIN`, which is DuckDB's own and pairs rows by ordinal.
433 Positional,
434}
435
436/// One expression.
437///
438/// Twenty four bytes, which is the widest variant rounded up. The precedence chain in the grammar
439/// does not survive into here: twenty levels of `X <- Y Tail*` become one [`Expr::Binary`] tree,
440/// because the levels exist to make the grammar unambiguous and mean nothing afterwards.
441#[derive(Debug, Clone, Copy, PartialEq, Eq)]
442pub enum Expr {
443 /// `*`, or `t.*` with a qualifier.
444 Star {
445 /// The qualifier, as a run of [`StrRef`], empty for a bare star.
446 qualifier: Slice,
447 /// `REPLACE (expression AS column)`, as a run of [`Target`] where the alias is the column
448 /// being replaced, empty for a star with no replace list.
449 ///
450 /// A [`Target`] rather than a type of its own because a replacement is an expression and a
451 /// name, which is exactly what a target is, and because that puts it in the arena every
452 /// other expression and name pair already lives in.
453 replacements: Slice,
454 },
455 /// A column reference, qualified or not.
456 Column {
457 /// The name, as a run of [`StrRef`], outermost first, so `s.t.a` is three parts.
458 name: Slice,
459 },
460 /// A literal, kept as the text that was written.
461 Literal {
462 /// Which kind.
463 kind: LiteralKind,
464 /// The text, with quotes stripped and escapes resolved for a string, `NONE` for a keyword
465 /// literal like `NULL` where the kind already says everything.
466 text: StrRef,
467 },
468 /// A prefix or postfix operator.
469 Unary {
470 /// Which operator.
471 op: UnaryOp,
472 /// What it applies to.
473 operand: ExprRef,
474 },
475 /// An infix operator.
476 Binary {
477 /// Which operator.
478 op: BinaryOp,
479 /// The left operand.
480 left: ExprRef,
481 /// The right operand.
482 right: ExprRef,
483 },
484 /// A function call.
485 Function {
486 /// The name, as a run of [`StrRef`], so `main.count` is two parts.
487 name: Slice,
488 /// The arguments, as a run of [`ExprRef`].
489 args: Slice,
490 /// Whether the call said `DISTINCT`.
491 distinct: bool,
492 },
493 /// `CAST(x AS t)` or `TRY_CAST(x AS t)`.
494 Cast {
495 /// What is being cast.
496 operand: ExprRef,
497 /// The target type, as the text it was written with. Parsing it is `rudb-common`'s job and
498 /// doing it here would put the type system in the parser.
499 ty: StrRef,
500 /// Whether a failure yields null rather than an error.
501 try_cast: bool,
502 },
503 /// `CASE`, searched or simple.
504 Case {
505 /// The operand of a simple `CASE x WHEN`, or `NONE` for a searched one.
506 operand: ExprRef,
507 /// The arms, as a run of [`CaseArm`].
508 arms: Slice,
509 /// The `ELSE`, or `NONE`.
510 otherwise: ExprRef,
511 },
512 /// `x BETWEEN a AND b`.
513 Between {
514 /// What is being tested.
515 operand: ExprRef,
516 /// The lower bound.
517 low: ExprRef,
518 /// The upper bound.
519 high: ExprRef,
520 /// Whether it was written `NOT BETWEEN`.
521 negated: bool,
522 },
523 /// `x IN (a, b, c)`.
524 In {
525 /// What is being tested.
526 operand: ExprRef,
527 /// The list, as a run of [`ExprRef`].
528 list: Slice,
529 /// Whether it was written `NOT IN`.
530 negated: bool,
531 },
532 /// A prepared statement parameter, written `?`, `?1`, `$1` or `$name`.
533 Parameter {
534 /// The identifier, which is the number for a positional one and the word for a named one.
535 /// A bare `?` is numbered by where it was written, so the identifier is there either way.
536 name: StrRef,
537 },
538 /// A bracketed list of expressions, `[a, b, c]`, which is a LIST value.
539 List {
540 /// The items, as a run of [`ExprRef`], in the order they were written.
541 items: Slice,
542 },
543 /// A parenthesised list of more than one expression, which is a row value.
544 Row {
545 /// The items, as a run of [`ExprRef`].
546 items: Slice,
547 },
548 /// A scalar subquery, `(SELECT ...)` where an expression is expected.
549 Subquery {
550 /// The query.
551 query: QueryRef,
552 },
553}
554
555/// One `WHEN a THEN b`.
556#[derive(Debug, Clone, Copy, PartialEq, Eq)]
557pub struct CaseArm {
558 /// The `WHEN`.
559 pub when: ExprRef,
560 /// The `THEN`.
561 pub then: ExprRef,
562}
563
564/// Which literal.
565#[derive(Debug, Clone, Copy, PartialEq, Eq)]
566pub enum LiteralKind {
567 /// A number, kept as text because the width it wants depends on where it lands.
568 Number,
569 /// A string.
570 String,
571 /// `NULL`.
572 Null,
573 /// `TRUE`.
574 True,
575 /// `FALSE`.
576 False,
577}
578
579/// A prefix or postfix operator.
580#[derive(Debug, Clone, Copy, PartialEq, Eq)]
581pub enum UnaryOp {
582 /// `NOT x`.
583 Not,
584 /// `-x`.
585 Negate,
586 /// `+x`, which is a no-op that still has to survive to the binder so that `+'a'` errors.
587 Plus,
588 /// `~x`.
589 BitNot,
590 /// `x!`.
591 Factorial,
592 /// `x IS NULL` or `x ISNULL`.
593 IsNull,
594 /// `x IS NOT NULL` or `x NOTNULL`.
595 IsNotNull,
596 /// `x IS TRUE`.
597 IsTrue,
598 /// `x IS NOT TRUE`.
599 IsNotTrue,
600 /// `x IS FALSE`.
601 IsFalse,
602 /// `x IS NOT FALSE`.
603 IsNotFalse,
604 /// `x IS UNKNOWN`.
605 IsUnknown,
606 /// `x IS NOT UNKNOWN`.
607 IsNotUnknown,
608}
609
610/// An infix operator.
611///
612/// The list is the dialect and not a general idea of what operators are. `Named` is the one open
613/// door, because `OperatorLiteral` in the grammar takes any run of operator characters that is not
614/// already a token, and rejecting that here would reject SQL DuckDB accepts.
615#[derive(Debug, Clone, Copy, PartialEq, Eq)]
616pub enum BinaryOp {
617 /// `OR`.
618 Or,
619 /// `AND`.
620 And,
621 /// `=` or `==`.
622 Eq,
623 /// `!=` or `<>`.
624 NotEq,
625 /// `<`.
626 Lt,
627 /// `>`.
628 Gt,
629 /// `<=`.
630 LtEq,
631 /// `>=`.
632 GtEq,
633 /// `IS DISTINCT FROM`.
634 IsDistinctFrom,
635 /// `IS NOT DISTINCT FROM`.
636 IsNotDistinctFrom,
637 /// `+`.
638 Add,
639 /// `-`.
640 Subtract,
641 /// `*`.
642 Multiply,
643 /// `/`.
644 Divide,
645 /// `//`, integer division.
646 IntegerDivide,
647 /// `%`.
648 Modulo,
649 /// `^` or `**`.
650 Power,
651 /// `&`.
652 BitAnd,
653 /// `|`.
654 BitOr,
655 /// `<<`.
656 ShiftLeft,
657 /// `>>`.
658 ShiftRight,
659 /// `||`.
660 Concat,
661 /// `LIKE` or `~~`.
662 Like,
663 /// `NOT LIKE` or `!~~`.
664 NotLike,
665 /// `ILIKE` or `~~*`.
666 ILike,
667 /// `NOT ILIKE` or `!~~*`.
668 NotILike,
669 /// `GLOB` or `~~~`.
670 Glob,
671 /// `SIMILAR TO`.
672 SimilarTo,
673 /// `!~`, which the grammar calls the not-similar-to operator.
674 NotSimilarTo,
675 /// `~`, a regex match.
676 Regex,
677 /// `~*`, a case insensitive regex match.
678 RegexInsensitive,
679 /// `!~*`, a negated case insensitive regex match.
680 NotRegexInsensitive,
681 /// `COLLATE`.
682 Collate,
683 /// `AT TIME ZONE`.
684 AtTimeZone,
685 /// `->`.
686 Arrow,
687 /// `->>`.
688 LongArrow,
689 /// `@>`, contains.
690 Contains,
691 /// `<@`, contained by.
692 ContainedBy,
693 /// `&&`, overlaps.
694 Overlaps,
695 /// `^@`, starts with.
696 StartsWith,
697 /// `<<=`, an inet operator.
698 InetContainedByOrEq,
699 /// `>>=`, an inet operator.
700 InetContainsOrEq,
701 /// An operator the dialect does not name, which DuckDB resolves as a binary function of that
702 /// name. `a <=> b` is the shape.
703 Named(StrRef),
704}
705
706/// A parsed statement or script, with every arena it points into.
707///
708/// Cheap to clone, cheap to send, and self contained: no index in here refers to anything outside
709/// it, and nothing in here borrows the query text. The text is copied into `strings` on the way in,
710/// which costs one allocation per distinct identifier and buys an `Ast` that outlives the string it
711/// came from.
712#[derive(Debug, Clone, Default, PartialEq, Eq)]
713pub struct Ast {
714 /// The statements in the script, in order.
715 pub statements: Vec<Statement>,
716 /// The query arena.
717 pub queries: Vec<Query>,
718 /// The select arena.
719 pub selects: Vec<Select>,
720 /// The expression arena.
721 pub exprs: Vec<Expr>,
722 /// The from-item arena.
723 pub sources: Vec<Source>,
724 /// Interned text. Identifiers keep the case they were written in, because DuckDB does not fold
725 /// it at any point, including for quoted identifiers.
726 pub strings: Vec<String>,
727 /// Backing store for every [`Slice`] of names.
728 pub parts: Vec<StrRef>,
729 /// Backing store for every [`Slice`] of expressions.
730 pub expr_lists: Vec<ExprRef>,
731 /// Backing store for every [`Slice`] of from items.
732 pub source_lists: Vec<SourceRef>,
733 /// Backing store for every [`Slice`] of target list entries.
734 pub targets: Vec<Target>,
735 /// Backing store for every [`Slice`] of order by entries.
736 pub order_items: Vec<OrderItem>,
737 /// Backing store for every [`Slice`] of case arms.
738 pub case_arms: Vec<CaseArm>,
739 /// The `CREATE TABLE` arena.
740 pub create_tables: Vec<CreateTable>,
741 /// The `CREATE VIEW` arena.
742 pub create_views: Vec<CreateView>,
743 /// The `DROP TABLE` arena.
744 pub drop_tables: Vec<DropTable>,
745 /// The `INSERT` arena.
746 pub inserts: Vec<Insert>,
747 /// Backing store for every [`Slice`] of column definitions.
748 pub column_defs: Vec<ColumnDef>,
749 /// Backing store for every [`Slice`] of names, which is a name list rather than a name.
750 pub name_lists: Vec<Slice>,
751 /// Backing store for the rows of a `VALUES`, each of which is a run of expressions.
752 pub rows: Vec<Slice>,
753}
754
755impl Ast {
756 /// The text behind a [`StrRef`], or the empty string for `NONE`.
757 pub fn string(&self, index: StrRef) -> &str {
758 if index == NONE { "" } else { &self.strings[index as usize] }
759 }
760
761 /// Every parameter identifier the statement uses, once each, in the order they were written.
762 ///
763 /// The arena is built as the walk goes, so its order is the written order, and a parameter used
764 /// twice is one identifier here because it is one value to provide.
765 pub fn parameters(&self) -> Vec<&str> {
766 let mut found: Vec<&str> = Vec::new();
767 for expr in &self.exprs {
768 if let Expr::Parameter { name } = *expr {
769 let name = self.string(name);
770 if !found.contains(&name) {
771 found.push(name);
772 }
773 }
774 }
775 found
776 }
777
778 /// The parts of a name, outermost first.
779 pub fn name(&self, slice: Slice) -> impl Iterator<Item = &str> {
780 self.parts[slice.range()].iter().map(|&part| self.string(part))
781 }
782
783 /// A name written back out with dots between the parts, for error messages and tests.
784 pub fn name_text(&self, slice: Slice) -> String {
785 self.name(slice).collect::<Vec<_>>().join(".")
786 }
787
788 /// One expression.
789 pub fn expr(&self, index: ExprRef) -> Expr {
790 self.exprs[index as usize]
791 }
792
793 /// One from item.
794 pub fn source(&self, index: SourceRef) -> Source {
795 self.sources[index as usize]
796 }
797
798 /// One query.
799 pub fn query(&self, index: QueryRef) -> Query {
800 self.queries[index as usize]
801 }
802
803 /// One select block.
804 pub fn select(&self, index: SelectRef) -> Select {
805 self.selects[index as usize]
806 }
807
808 /// The expressions of a list.
809 pub fn expr_list(&self, slice: Slice) -> &[ExprRef] {
810 &self.expr_lists[slice.range()]
811 }
812
813 /// The from items of a list.
814 pub fn source_list(&self, slice: Slice) -> &[SourceRef] {
815 &self.source_lists[slice.range()]
816 }
817
818 /// The entries of a target list.
819 pub fn target_list(&self, slice: Slice) -> &[Target] {
820 &self.targets[slice.range()]
821 }
822
823 /// The entries of an order by list.
824 pub fn order_list(&self, slice: Slice) -> &[OrderItem] {
825 &self.order_items[slice.range()]
826 }
827
828 /// The arms of a case.
829 pub fn arm_list(&self, slice: Slice) -> &[CaseArm] {
830 &self.case_arms[slice.range()]
831 }
832
833 /// One `CREATE TABLE`.
834 pub fn create_table(&self, index: CreateTableRef) -> CreateTable {
835 self.create_tables[index as usize]
836 }
837
838 /// One `CREATE VIEW`.
839 pub fn create_view(&self, index: CreateViewRef) -> CreateView {
840 self.create_views[index as usize]
841 }
842
843 /// One `DROP TABLE`.
844 pub fn drop_table(&self, index: DropTableRef) -> DropTable {
845 self.drop_tables[index as usize]
846 }
847
848 /// One `INSERT`.
849 pub fn insert(&self, index: InsertRef) -> Insert {
850 self.inserts[index as usize]
851 }
852
853 /// The column definitions of a `CREATE TABLE`.
854 pub fn column_defs(&self, slice: Slice) -> &[ColumnDef] {
855 &self.column_defs[slice.range()]
856 }
857
858 /// The names of a name list, each of which is itself a run of parts.
859 pub fn name_list(&self, slice: Slice) -> &[Slice] {
860 &self.name_lists[slice.range()]
861 }
862
863 /// The rows of a `VALUES`, each of which is itself a run of expressions.
864 pub fn rows(&self, slice: Slice) -> &[Slice] {
865 &self.rows[slice.range()]
866 }
867
868 /// How many nodes the whole tree is, across every arena.
869 ///
870 /// The number to watch when the transformer changes. A parse tree of five thousand nodes that
871 /// becomes an AST of thirty is the twenty precedence levels being thrown away, which is the
872 /// whole reason this module exists.
873 pub fn node_count(&self) -> usize {
874 self.queries.len() + self.selects.len() + self.exprs.len() + self.sources.len()
875 }
876}