clt_database/translate/expr/
walk.rs

1use super::*;
2use crate::function::{Deterministic, ExtFunc};
3
4pub enum WalkControl {
5    Continue,     // Visit children
6    SkipChildren, // Skip children but continue walking siblings
7}
8
9/// Recursively walks an immutable expression, applying a function to each sub-expression.
10pub fn walk_expr<'a, F>(expr: &'a ast::Expr, func: &mut F) -> Result<WalkControl>
11where
12    F: FnMut(&'a ast::Expr) -> Result<WalkControl>,
13{
14    enum WalkItem<'a> {
15        Expr(&'a ast::Expr),
16        FrameBound(&'a ast::FrameBound),
17    }
18
19    type Stack<'b> = smallvec::SmallVec<[WalkItem<'b>; 4]>;
20
21    let mut stack: Stack<'a> = smallvec::smallvec![WalkItem::Expr(expr)];
22    let push_over_clause_walk_items = |stack: &mut Stack<'a>, over_clause: &'a ast::Over| {
23        if let ast::Over::Window(window) = over_clause {
24            if let Some(frame_clause) = &window.frame_clause {
25                if let Some(end_bound) = &frame_clause.end {
26                    stack.push(WalkItem::FrameBound(end_bound));
27                }
28                stack.push(WalkItem::FrameBound(&frame_clause.start));
29            }
30            for sort_col in window.order_by.iter().rev() {
31                stack.push(WalkItem::Expr(&sort_col.expr));
32            }
33            for part_expr in window.partition_by.iter().rev() {
34                stack.push(WalkItem::Expr(part_expr));
35            }
36        }
37    };
38    while let Some(item) = stack.pop() {
39        match item {
40            WalkItem::Expr(expr) => {
41                if matches!(func(expr)?, WalkControl::SkipChildren) {
42                    continue;
43                }
44                match expr {
45                    ast::Expr::SubqueryResult { lhs, .. } => {
46                        if let Some(lhs) = lhs {
47                            stack.push(WalkItem::Expr(lhs));
48                        }
49                    }
50                    ast::Expr::Between {
51                        lhs, start, end, ..
52                    } => {
53                        stack.push(WalkItem::Expr(end));
54                        stack.push(WalkItem::Expr(start));
55                        stack.push(WalkItem::Expr(lhs));
56                    }
57                    ast::Expr::Binary(lhs, _, rhs) => {
58                        stack.push(WalkItem::Expr(rhs));
59                        stack.push(WalkItem::Expr(lhs));
60                    }
61                    ast::Expr::Case {
62                        base,
63                        when_then_pairs,
64                        else_expr,
65                    } => {
66                        if let Some(else_expr) = else_expr {
67                            stack.push(WalkItem::Expr(else_expr));
68                        }
69                        for (when_expr, then_expr) in when_then_pairs.iter().rev() {
70                            stack.push(WalkItem::Expr(then_expr));
71                            stack.push(WalkItem::Expr(when_expr));
72                        }
73                        if let Some(base_expr) = base {
74                            stack.push(WalkItem::Expr(base_expr));
75                        }
76                    }
77                    ast::Expr::Cast { expr, .. } | ast::Expr::Collate(expr, _) => {
78                        stack.push(WalkItem::Expr(expr));
79                    }
80                    ast::Expr::Exists(_select) | ast::Expr::Subquery(_select) => {
81                        // TODO: Walk through select statements if needed
82                    }
83                    ast::Expr::FunctionCall {
84                        args,
85                        order_by,
86                        within_group,
87                        filter_over,
88                        ..
89                    } => {
90                        if let Some(over_clause) = &filter_over.over_clause {
91                            push_over_clause_walk_items(&mut stack, over_clause);
92                        }
93                        if let Some(filter_clause) = &filter_over.filter_clause {
94                            stack.push(WalkItem::Expr(filter_clause));
95                        }
96                        for sort_col in within_group.iter().rev() {
97                            stack.push(WalkItem::Expr(&sort_col.expr));
98                        }
99                        for sort_col in order_by.iter().rev() {
100                            stack.push(WalkItem::Expr(&sort_col.expr));
101                        }
102                        for arg in args.iter().rev() {
103                            stack.push(WalkItem::Expr(arg));
104                        }
105                    }
106                    ast::Expr::FunctionCallStar { filter_over, .. } => {
107                        if let Some(over_clause) = &filter_over.over_clause {
108                            push_over_clause_walk_items(&mut stack, over_clause);
109                        }
110                        if let Some(filter_clause) = &filter_over.filter_clause {
111                            stack.push(WalkItem::Expr(filter_clause));
112                        }
113                    }
114                    ast::Expr::InList { lhs, rhs, .. } => {
115                        for expr in rhs.iter().rev() {
116                            stack.push(WalkItem::Expr(expr));
117                        }
118                        stack.push(WalkItem::Expr(lhs));
119                    }
120                    ast::Expr::InSelect { lhs, rhs: _, .. } => {
121                        stack.push(WalkItem::Expr(lhs));
122                        // TODO: Walk through select statements if needed
123                    }
124                    ast::Expr::InTable { lhs, args, .. } => {
125                        for expr in args.iter().rev() {
126                            stack.push(WalkItem::Expr(expr));
127                        }
128                        stack.push(WalkItem::Expr(lhs));
129                    }
130                    ast::Expr::IsNull(expr) | ast::Expr::NotNull(expr) => {
131                        stack.push(WalkItem::Expr(expr));
132                    }
133                    ast::Expr::Like {
134                        lhs, rhs, escape, ..
135                    } => {
136                        if let Some(esc_expr) = escape {
137                            stack.push(WalkItem::Expr(esc_expr));
138                        }
139                        stack.push(WalkItem::Expr(rhs));
140                        stack.push(WalkItem::Expr(lhs));
141                    }
142                    ast::Expr::Parenthesized(exprs) => {
143                        for expr in exprs.iter().rev() {
144                            stack.push(WalkItem::Expr(expr));
145                        }
146                    }
147                    ast::Expr::Raise(_, expr) => {
148                        if let Some(raise_expr) = expr {
149                            stack.push(WalkItem::Expr(raise_expr));
150                        }
151                    }
152                    ast::Expr::Unary(_, expr) => {
153                        stack.push(WalkItem::Expr(expr));
154                    }
155                    ast::Expr::Array { .. } | ast::Expr::Subscript { .. } => {
156                        unreachable!(
157                            "Array and Subscript are desugared into function calls by the parser"
158                        )
159                    }
160                    ast::Expr::Id(_)
161                    | ast::Expr::Column { .. }
162                    | ast::Expr::RowId { .. }
163                    | ast::Expr::Literal(_)
164                    | ast::Expr::DoublyQualified(..)
165                    | ast::Expr::Name(_)
166                    | ast::Expr::Qualified(..)
167                    | ast::Expr::Variable(_)
168                    | ast::Expr::Register(_)
169                    | ast::Expr::Default => {}
170                    ast::Expr::FieldAccess { base, .. } => {
171                        stack.push(WalkItem::Expr(base));
172                    }
173                }
174            }
175            WalkItem::FrameBound(bound) => match bound {
176                ast::FrameBound::Following(expr) | ast::FrameBound::Preceding(expr) => {
177                    stack.push(WalkItem::Expr(expr));
178                }
179                ast::FrameBound::CurrentRow
180                | ast::FrameBound::UnboundedFollowing
181                | ast::FrameBound::UnboundedPreceding => {}
182            },
183        }
184    }
185    Ok(WalkControl::Continue)
186}
187
188pub fn expr_references_subquery_id(expr: &ast::Expr, subquery_id: TableInternalId) -> bool {
189    let mut found = false;
190    let _ = walk_expr(expr, &mut |e: &ast::Expr| -> Result<WalkControl> {
191        if let ast::Expr::SubqueryResult {
192            subquery_id: sid, ..
193        } = e
194        {
195            if *sid == subquery_id {
196                found = true;
197                return Ok(WalkControl::SkipChildren);
198            }
199        }
200        Ok(WalkControl::Continue)
201    });
202    found
203}
204
205pub fn expr_references_any_subquery(expr: &ast::Expr) -> bool {
206    let mut found = false;
207    let _ = walk_expr(expr, &mut |e: &ast::Expr| -> Result<WalkControl> {
208        if matches!(e, ast::Expr::SubqueryResult { .. }) {
209            found = true;
210            return Ok(WalkControl::SkipChildren);
211        }
212        Ok(WalkControl::Continue)
213    });
214    found
215}
216
217/// Returns true if this expression calls a scalar function whose result can
218/// change between calls.
219///
220/// This is used when deciding whether two repeated window expressions can use
221/// one `WindowFunction` entry. For example, two copies of `sum(x) OVER w` can
222/// use one entry. Two copies of
223/// `sum(x) FILTER (WHERE random() % 2 = 0) OVER w` cannot share the filter
224/// value, because SQLite runs `random()` separately at each place it appears.
225///
226pub fn expr_contains_nondeterministic_scalar_function(
227    expr: &ast::Expr,
228    resolver: &Resolver<'_>,
229) -> Result<bool> {
230    fn is_nondeterministic_scalar_like_function(func: &Func) -> bool {
231        match func {
232            // Aggregate and window function calls themselves are not flagged
233            // at any nesting depth — their outputs are deterministic given the
234            // same input rows. The walker still descends into their args,
235            // FILTER, and OVER subexprs, so nondet scalars buried inside
236            // (e.g. `sum(random())`) are still caught. Note also that
237            // `AggFunc::is_deterministic` returns `false`, so the catch-all
238            // below would otherwise flag every aggregate call.
239            Func::Agg(_) | Func::Window(_) => false,
240
241            // User-defined scalar functions can do anything, so treat them
242            // like `random()`. User-defined aggregates are treated like
243            // built-in aggregates: two copies of `myagg(x) OVER w` should
244            // share one window entry when `x` and the FILTER/OVER clauses are
245            // stable.
246            Func::External(external) if matches!(external.func, ExtFunc::Aggregate { .. }) => false,
247
248            _ => !func.is_deterministic(),
249        }
250    }
251
252    let mut found = false;
253    crate::util::walk_expr_with_subqueries(expr, &mut |e| -> Result<WalkControl> {
254        if found {
255            return Ok(WalkControl::SkipChildren);
256        }
257
258        let func = match e {
259            ast::Expr::FunctionCall { name, args, .. } => {
260                resolver.resolve_function(name.as_str(), args.len())?
261            }
262            ast::Expr::FunctionCallStar { name, .. } => {
263                resolver.resolve_function(name.as_str(), 0)?
264            }
265            _ => None,
266        };
267
268        // If the name is unknown here, leave the error to the normal resolver.
269        // This helper only answers "may repeated copies share work?"
270        if func
271            .as_ref()
272            .is_some_and(is_nondeterministic_scalar_like_function)
273        {
274            found = true;
275            return Ok(WalkControl::SkipChildren);
276        }
277
278        Ok(WalkControl::Continue)
279    })?;
280
281    Ok(found)
282}
283
284/// Walks a mutable expression, applying a function to each sub-expression.
285pub fn walk_expr_mut<'a, F>(expr: &'a mut ast::Expr, func: &mut F) -> Result<WalkControl>
286where
287    F: FnMut(&mut ast::Expr) -> Result<WalkControl>,
288{
289    enum WalkItem<'a> {
290        Expr(&'a mut ast::Expr),
291        FrameBound(&'a mut ast::FrameBound),
292    }
293
294    type Stack<'a> = smallvec::SmallVec<[WalkItem<'a>; 4]>;
295
296    fn push_over_clause_walk_items<'a>(stack: &mut Stack<'a>, over_clause: &'a mut ast::Over) {
297        if let ast::Over::Window(window) = over_clause {
298            if let Some(frame_clause) = &mut window.frame_clause {
299                if let Some(end_bound) = &mut frame_clause.end {
300                    stack.push(WalkItem::FrameBound(end_bound));
301                }
302                stack.push(WalkItem::FrameBound(&mut frame_clause.start));
303            }
304            for sort_col in window.order_by.iter_mut().rev() {
305                stack.push(WalkItem::Expr(&mut sort_col.expr));
306            }
307            for part_expr in window.partition_by.iter_mut().rev() {
308                stack.push(WalkItem::Expr(part_expr));
309            }
310        }
311    }
312
313    let mut stack: Stack<'a> = smallvec::smallvec![WalkItem::Expr(expr)];
314    while let Some(item) = stack.pop() {
315        match item {
316            WalkItem::Expr(expr) => {
317                if matches!(func(expr)?, WalkControl::SkipChildren) {
318                    continue;
319                }
320                match expr {
321                    ast::Expr::SubqueryResult { lhs, .. } => {
322                        if let Some(lhs) = lhs {
323                            stack.push(WalkItem::Expr(lhs));
324                        }
325                    }
326                    ast::Expr::Between {
327                        lhs, start, end, ..
328                    } => {
329                        stack.push(WalkItem::Expr(end));
330                        stack.push(WalkItem::Expr(start));
331                        stack.push(WalkItem::Expr(lhs));
332                    }
333                    ast::Expr::Binary(lhs, _, rhs) => {
334                        stack.push(WalkItem::Expr(rhs));
335                        stack.push(WalkItem::Expr(lhs));
336                    }
337                    ast::Expr::Case {
338                        base,
339                        when_then_pairs,
340                        else_expr,
341                    } => {
342                        if let Some(else_expr) = else_expr {
343                            stack.push(WalkItem::Expr(else_expr));
344                        }
345                        for (when_expr, then_expr) in when_then_pairs.iter_mut().rev() {
346                            stack.push(WalkItem::Expr(then_expr));
347                            stack.push(WalkItem::Expr(when_expr));
348                        }
349                        if let Some(base_expr) = base {
350                            stack.push(WalkItem::Expr(base_expr));
351                        }
352                    }
353                    ast::Expr::Cast { expr, .. } | ast::Expr::Collate(expr, _) => {
354                        stack.push(WalkItem::Expr(expr));
355                    }
356                    ast::Expr::Exists(_) | ast::Expr::Subquery(_) => {
357                        // TODO: Walk through select statements if needed
358                    }
359                    ast::Expr::FunctionCall {
360                        args,
361                        order_by,
362                        within_group,
363                        filter_over,
364                        ..
365                    } => {
366                        if let Some(over_clause) = &mut filter_over.over_clause {
367                            push_over_clause_walk_items(&mut stack, over_clause);
368                        }
369                        if let Some(filter_clause) = &mut filter_over.filter_clause {
370                            stack.push(WalkItem::Expr(filter_clause));
371                        }
372                        for sort_col in within_group.iter_mut().rev() {
373                            stack.push(WalkItem::Expr(&mut sort_col.expr));
374                        }
375                        for sort_col in order_by.iter_mut().rev() {
376                            stack.push(WalkItem::Expr(&mut sort_col.expr));
377                        }
378                        for arg in args.iter_mut().rev() {
379                            stack.push(WalkItem::Expr(arg));
380                        }
381                    }
382                    ast::Expr::FunctionCallStar { filter_over, .. } => {
383                        if let Some(over_clause) = &mut filter_over.over_clause {
384                            push_over_clause_walk_items(&mut stack, over_clause);
385                        }
386                        if let Some(filter_clause) = &mut filter_over.filter_clause {
387                            stack.push(WalkItem::Expr(filter_clause));
388                        }
389                    }
390                    ast::Expr::InList { lhs, rhs, .. } => {
391                        for expr in rhs.iter_mut().rev() {
392                            stack.push(WalkItem::Expr(expr));
393                        }
394                        stack.push(WalkItem::Expr(lhs));
395                    }
396                    ast::Expr::InSelect { lhs, rhs: _, .. } => {
397                        stack.push(WalkItem::Expr(lhs));
398                        // TODO: Walk through select statements if needed
399                    }
400                    ast::Expr::InTable { lhs, args, .. } => {
401                        for expr in args.iter_mut().rev() {
402                            stack.push(WalkItem::Expr(expr));
403                        }
404                        stack.push(WalkItem::Expr(lhs));
405                    }
406                    ast::Expr::IsNull(expr) | ast::Expr::NotNull(expr) => {
407                        stack.push(WalkItem::Expr(expr));
408                    }
409                    ast::Expr::Like {
410                        lhs, rhs, escape, ..
411                    } => {
412                        if let Some(esc_expr) = escape {
413                            stack.push(WalkItem::Expr(esc_expr));
414                        }
415                        stack.push(WalkItem::Expr(rhs));
416                        stack.push(WalkItem::Expr(lhs));
417                    }
418                    ast::Expr::Parenthesized(exprs) => {
419                        for expr in exprs.iter_mut().rev() {
420                            stack.push(WalkItem::Expr(expr));
421                        }
422                    }
423                    ast::Expr::Raise(_, expr) => {
424                        if let Some(raise_expr) = expr {
425                            stack.push(WalkItem::Expr(raise_expr));
426                        }
427                    }
428                    ast::Expr::Unary(_, expr) => {
429                        stack.push(WalkItem::Expr(expr));
430                    }
431                    ast::Expr::Array { .. } | ast::Expr::Subscript { .. } => {
432                        unreachable!(
433                            "Array and Subscript are desugared into function calls by the parser"
434                        )
435                    }
436                    ast::Expr::Id(_)
437                    | ast::Expr::Column { .. }
438                    | ast::Expr::RowId { .. }
439                    | ast::Expr::Literal(_)
440                    | ast::Expr::DoublyQualified(..)
441                    | ast::Expr::Name(_)
442                    | ast::Expr::Qualified(..)
443                    | ast::Expr::Variable(_)
444                    | ast::Expr::Register(_)
445                    | ast::Expr::Default => {}
446                    ast::Expr::FieldAccess { base, .. } => {
447                        stack.push(WalkItem::Expr(base));
448                    }
449                }
450            }
451            WalkItem::FrameBound(bound) => match bound {
452                ast::FrameBound::Following(expr) | ast::FrameBound::Preceding(expr) => {
453                    stack.push(WalkItem::Expr(expr));
454                }
455                ast::FrameBound::CurrentRow
456                | ast::FrameBound::UnboundedFollowing
457                | ast::FrameBound::UnboundedPreceding => {}
458            },
459        }
460    }
461    Ok(WalkControl::Continue)
462}
clt_database/translate/expr/walk.rs

clt_database/translate/expr/
walk.rs
