inillucent_sql/bind/
cte.rs

1//! Common table expressions: what a `WITH` binds, and how a recursive one is
2//! filled.
3//!
4//! Invariant: **a CTE is bound once per reference and never bound inside
5//! itself.** Two references to one CTE are two independent scans with their
6//! own FROM-term numbers, which is why a binding holds an AST id rather than a
7//! bound block; and a definition already being bound is a cycle, which is
8//! answered rather than followed.
9//!
10//! ## Why this is its own module
11//!
12//! `bind.rs` was at its recorded ceiling and task-1913 added ninety-nine lines
13//! to it, so the ratchet in `policy.rs` asked for an extraction rather than a
14//! raised number. This is one question - what a name in a `WITH` stands for -
15//! and the ten items here were the only ones asking it. Nothing moved changed
16//! in the move.
17
18use super::{subquery_table, unsupported, Binder, BoundSource, RecursiveBody, SourceRows};
19use crate::ast::{self, CompoundOp, JoinKind, SelectId};
20use crate::catalog_view::TableInfo;
21use crate::diagnostic::{ParseError, ParseErrorKind};
22use crate::lexer::Span;
23
24/// One common table expression visible to a block.
25///
26/// The definition is kept as an AST id rather than a bound block because two
27/// references to the same CTE are two independent scans: each gets its own
28/// FROM-term numbers and its own materialisation. Binding once and cloning
29/// would give both references the same source ids, and the second scan would
30/// then read the first one's cursors.
31#[derive(Clone, Debug, PartialEq, Eq)]
32pub struct CteBinding {
33    /// The folded name a FROM term matches against.
34    pub folded: Vec<u8>,
35    /// The name as written, which the expansion is aliased to.
36    pub name: Vec<u8>,
37    /// The explicit column list, when the `WITH` wrote one.
38    pub columns: Vec<Vec<u8>>,
39    /// The query the name stands for.
40    pub select: SelectId,
41    /// Whether the `WITH` said `RECURSIVE`.
42    pub recursive: bool,
43}
44
45/// One recursive CTE whose definition is being bound.
46#[derive(Clone, Debug)]
47pub(super) struct RecursiveTarget {
48    /// The CTE's folded name.
49    pub(super) folded: Vec<u8>,
50    /// The statement-wide number of the FROM term that will hold its store.
51    id: usize,
52    /// The columns a reference to it exposes, taken from the seed arm.
53    table: TableInfo,
54    /// Whether any arm bound so far referred to it.
55    referenced: bool,
56}
57
58impl Binder<'_> {
59    /// Pushes the CTEs of a `WITH` prefix, returning whether it pushed any.
60    pub(crate) fn push_ctes(&mut self, with: &ast::With) -> Result<bool, ParseError> {
61        if with.ctes.is_empty() {
62            return Ok(false);
63        }
64        let mut bindings = Vec::with_capacity(with.ctes.len());
65        for cte in &with.ctes {
66            bindings.push(CteBinding {
67                folded: self.ast.folded(cte.name).to_vec(),
68                name: self.ast.text(cte.name).to_vec(),
69                columns: cte
70                    .columns
71                    .iter()
72                    .map(|name| self.ast.text(*name).to_vec())
73                    .collect(),
74                select: cte.select,
75                recursive: with.recursive,
76            });
77        }
78        self.ctes.push(bindings);
79        Ok(true)
80    }
81
82    /// Drops the innermost level of CTE bindings.
83    pub(crate) fn pop_ctes(&mut self) {
84        self.ctes.pop();
85    }
86
87    /// Returns the innermost CTE a folded name matches.
88    pub(super) fn find_cte(&self, folded: &[u8]) -> Option<CteBinding> {
89        for level in self.ctes.iter().rev() {
90            if let Some(found) = level.iter().find(|cte| cte.folded == folded) {
91                return Some(found.clone());
92            }
93        }
94        None
95    }
96
97    /// Reports whether a CTE's own query names it in a FROM clause.
98    ///
99    /// **What makes a CTE recursive is the self-reference, not the keyword.**
100    /// SQLite accepts `WITH c AS (SELECT 1 UNION ALL SELECT ... FROM c)` with
101    /// no `RECURSIVE` written and answers it; this binder read only the
102    /// keyword, so the same query bound `c`'s definition inside `c`'s
103    /// definition until the process ran out of stack (task-1913).
104    ///
105    /// An inner `WITH` that binds the same name shadows the outer one, so
106    /// nothing under it can be the recursion - which is why this stops there
107    /// rather than reporting every mention of the name.
108    ///
109    /// @param select - the CTE's query
110    /// @param folded - the CTE's folded name
111    pub(super) fn select_names_itself(&self, select: ast::SelectId, folded: &[u8]) -> bool {
112        let Some(query) = self.ast.select(select) else {
113            return false;
114        };
115        if query
116            .with
117            .ctes
118            .iter()
119            .any(|inner| self.ast.folded(inner.name) == folded)
120        {
121            return false;
122        }
123        if self.core_names_cte(query.first, folded) {
124            return true;
125        }
126        query
127            .compounds
128            .iter()
129            .any(|(_, arm)| self.core_names_cte(*arm, folded))
130    }
131
132    /// Reports whether one arm of a compound names a CTE in its FROM clause.
133    ///
134    /// @param core - the arm
135    /// @param folded - the CTE's folded name
136    pub(super) fn core_names_cte(&self, core: ast::SelectCoreId, folded: &[u8]) -> bool {
137        let Some(arm) = self.ast.core(core) else {
138            return false;
139        };
140        let ast::SelectBody::Select { from, .. } = &arm.body else {
141            return false;
142        };
143        self.terms_name_cte(from, folded)
144    }
145
146    /// Reports whether any FROM term names a CTE.
147    ///
148    /// @param terms - the FROM terms
149    /// @param folded - the CTE's folded name
150    pub(super) fn terms_name_cte(&self, terms: &[ast::FromTermId], folded: &[u8]) -> bool {
151        terms.iter().any(|id| match self.ast.from_term(*id) {
152            Some(term) => match &term.source {
153                ast::FromSource::Table { database, name, .. } => {
154                    database.is_none() && self.ast.folded(*name) == folded
155                }
156                ast::FromSource::Subquery(select) => self.select_names_itself(*select, folded),
157                ast::FromSource::Join(inner) => self.terms_name_cte(inner, folded),
158            },
159            None => false,
160        })
161    }
162
163    /// Registers a reference to the recursive CTE currently being bound.
164    pub(super) fn push_recursive_self(
165        &mut self,
166        position: usize,
167        alias: Option<ast::NameId>,
168        join: JoinKind,
169    ) -> Result<(), ParseError> {
170        let Some(target) = self.recursing.get_mut(position) else {
171            return Err(unsupported("unknown recursive reference", Span::default()));
172        };
173        target.referenced = true;
174        let cte = target.id;
175        let table = target.table.clone();
176        let alias = match alias {
177            Some(alias) => self.ast.text(alias).to_vec(),
178            None => table.name.clone(),
179        };
180        let id = self.sources.len();
181        self.sources.push(BoundSource {
182            index_hint: crate::bind::IndexChoice::Any,
183            id,
184            rows: SourceRows::RecursiveSelf { cte },
185            table: std::rc::Rc::new(table),
186            alias,
187            join,
188            constraint: None,
189            suppressed: Vec::new(),
190            index_exprs: Vec::new(),
191        });
192        if let Some(scope) = self.scopes.last_mut() {
193            scope.push(id);
194        }
195        Ok(())
196    }
197
198    /// Binds a `WITH RECURSIVE` CTE reference.
199    ///
200    /// The seed arm is bound first, alone, because until it is bound nothing
201    /// knows what columns the CTE has - and the step arm cannot be bound until
202    /// a reference to the CTE has columns to resolve against. A CTE declared
203    /// `RECURSIVE` that turns out not to reference itself is an ordinary
204    /// compound, and is rebuilt as one rather than run through a queue that
205    /// would never be fed.
206    pub(super) fn bind_recursive_cte(
207        &mut self,
208        cte: &CteBinding,
209        alias: Vec<u8>,
210        join: JoinKind,
211        span: Span,
212    ) -> Result<(), ParseError> {
213        let Some(select) = self.ast.select(cte.select) else {
214            return Err(unsupported("missing select", span));
215        };
216        if select.compounds.is_empty() {
217            return self.bind_subquery_term(
218                cte.select,
219                Some(alias),
220                cte.columns.clone(),
221                join,
222                span,
223            );
224        }
225        let arms: Vec<(CompoundOp, ast::SelectCoreId)> = select.compounds.clone();
226        let order_by = select.order_by.clone();
227        let limit = select.limit;
228        let offset = select.offset;
229        let first = select.first;
230        if !order_by.is_empty() || limit.is_some() || offset.is_some() {
231            return Err(ParseError::new(
232                ParseErrorKind::Unsupported(
233                    "ORDER BY and LIMIT are not allowed on a recursive CTE",
234                ),
235                span,
236            ));
237        }
238
239        let id = self.sources.len();
240        // The store's FROM-term number is reserved before anything is bound, so
241        // that a self-reference inside the step arm can name the store it will
242        // read without the two being bound in an impossible order.
243        self.sources.push(BoundSource {
244            index_hint: crate::bind::IndexChoice::Any,
245            id,
246            rows: SourceRows::Table,
247            table: std::rc::Rc::new(TableInfo::subquery(alias.clone(), 0, Vec::new())),
248            alias: alias.clone(),
249            join,
250            constraint: None,
251            suppressed: Vec::new(),
252            index_exprs: Vec::new(),
253        });
254
255        let seed = self.bind_isolated_arm(first)?;
256        let table = subquery_table(&alias, &cte.columns, &seed);
257        if !cte.columns.is_empty() && cte.columns.len() != seed.columns.len() {
258            return Err(ParseError::new(
259                ParseErrorKind::Unsupported("the named column list does not match the query"),
260                span,
261            ));
262        }
263        self.recursing.push(RecursiveTarget {
264            folded: cte.folded.clone(),
265            id,
266            table: table.clone(),
267            referenced: false,
268        });
269        let mut seeds = vec![(CompoundOp::UnionAll, seed)];
270        let mut steps = Vec::new();
271        let mut outcome = Ok(());
272        for (op, arm) in &arms {
273            if !matches!(op, CompoundOp::Union | CompoundOp::UnionAll) {
274                outcome = Err(ParseError::new(
275                    ParseErrorKind::Unsupported("recursive query does not use UNION or UNION ALL"),
276                    span,
277                ));
278                break;
279            }
280            if let Some(target) = self.recursing.last_mut() {
281                target.referenced = false;
282            }
283            let bound = match self.bind_isolated_arm(*arm) {
284                Ok(bound) => bound,
285                Err(reason) => {
286                    outcome = Err(reason);
287                    break;
288                }
289            };
290            let referenced = self
291                .recursing
292                .last()
293                .is_some_and(|target| target.referenced);
294            if referenced {
295                steps.push((*op, bound));
296            } else {
297                seeds.push((*op, bound));
298            }
299        }
300        self.recursing.pop();
301        outcome?;
302
303        let mut source = BoundSource {
304            index_hint: crate::bind::IndexChoice::Any,
305            id,
306            rows: SourceRows::Recursive(Box::new(RecursiveBody { seeds, steps })),
307            table: std::rc::Rc::new(table),
308            alias,
309            join,
310            constraint: None,
311            suppressed: Vec::new(),
312            index_exprs: Vec::new(),
313        };
314        if let SourceRows::Recursive(body) = &mut source.rows {
315            if body.steps.is_empty() {
316                // Declared recursive, never refers to itself: an ordinary
317                // compound wearing the keyword.
318                let mut arms = core::mem::take(&mut body.seeds);
319                if arms.is_empty() {
320                    return Err(unsupported("missing select core", span));
321                }
322                let mut head = arms.remove(0).1;
323                head.compounds = arms;
324                source.rows = SourceRows::Subquery(Box::new(head));
325            }
326        }
327        if let Some(slot) = self.sources.get_mut(id) {
328            *slot = source;
329        }
330        if let Some(scope) = self.scopes.last_mut() {
331            scope.push(id);
332        }
333        Ok(())
334    }
335}
inillucent_sql/bind/cte.rs

inillucent_sql/bind/
cte.rs
