1use fsqlite_ast::{
22 BinaryOp, ColumnRef, CompoundOp, Cte, CteMaterialized, Distinctness, Expr, FrameBound,
23 FrameExclude, FrameSpec, FrameType, FromClause, FunctionArgs, InSet, JoinClause,
24 JoinConstraint, JoinKind, JoinType, JsonArrow, LikeOp, LimitClause, Literal, NullsOrder,
25 OrderingTerm, PlaceholderType, QualifiedName, RaiseAction, ResultColumn, SelectBody,
26 SelectCore, SelectStatement, SortDirection, Span, TableOrSubquery, TypeName, UnaryOp,
27 ValuesClause, WindowDef, WindowReference, WindowSpec, WithClause,
28};
29#[cfg(test)]
30use std::cell::Cell;
31use std::sync::Arc;
32
33use crate::parser::{
34 HeightTracked, MAX_PARSE_DEPTH, ParseError, Parser, is_nonreserved_kw, kw_to_str,
35 starts_bare_window_name, starts_post_dot_identifier, starts_table_star_qualifier,
36 starts_window_base_name,
37};
38use crate::token::{Token, TokenKind};
39
40pub(crate) struct ParsedExpr {
41 pub(crate) expr: Expr,
42 pub(crate) height: u32,
43 is_constant: bool,
44 has_function: bool,
45 root: CachedRoot,
46}
47
48#[derive(Clone, Copy, Debug, PartialEq, Eq)]
49enum CachedRoot {
50 Other,
51 UnaryPlus,
52 Vector,
53 ScalarSubquery,
54}
55
56fn vector_in_list_arity_error(lhs: &Expr, items: &[ParsedExpr]) -> Option<String> {
57 let expected = match lhs {
58 Expr::RowValue(lhs_terms, _) => lhs_terms.len(),
59 _ => return None,
64 };
65 for item in items {
66 let actual = match &item.expr {
67 Expr::RowValue(element_terms, _) => element_terms.len(),
68 Expr::Subquery(..) if items.len() == 1 => continue,
73 _ => 1,
74 };
75 if actual == expected {
76 continue;
77 }
78 let term_suffix = if actual == 1 { "" } else { "s" };
79 return Some(format!(
80 "IN(...) element has {actual} term{term_suffix} - expected {expected}"
81 ));
82 }
83 None
84}
85
86#[cfg(test)]
87enum DeepExprFrame {
88 Unary {
89 op: UnaryOp,
90 span: Span,
91 right_bp: u8,
92 },
93 Parenthesis {
94 span: Span,
95 },
96}
97
98struct InlineStack<T, const N: usize> {
99 inline: [Option<T>; N],
100 inline_len: usize,
101 spill: Vec<T>,
102}
103
104impl<T, const N: usize> InlineStack<T, N> {
105 fn new() -> Self {
106 Self {
107 inline: [const { None }; N],
108 inline_len: 0,
109 spill: Vec::new(),
110 }
111 }
112
113 fn push(&mut self, value: T) {
114 if self.inline_len < N && self.spill.is_empty() {
115 self.inline[self.inline_len] = Some(value);
116 self.inline_len += 1;
117 } else {
118 #[cfg(test)]
119 if self.spill.is_empty() {
120 PARSE_MACHINE_STACK_SPILLS.set(PARSE_MACHINE_STACK_SPILLS.get().saturating_add(1));
121 }
122 self.spill.push(value);
123 }
124 }
125
126 fn pop(&mut self) -> Option<T> {
127 if let Some(value) = self.spill.pop() {
128 return Some(value);
129 }
130 if self.inline_len == 0 {
131 return None;
132 }
133 self.inline_len -= 1;
134 self.inline[self.inline_len].take()
135 }
136}
137
138struct FunctionBuild {
139 name: String,
140 start: Span,
141 args: FunctionArgs,
142 distinct: bool,
143 height: u32,
144 order_by: Vec<OrderingTerm>,
145 filter: Option<Box<Expr>>,
146 over: Option<WindowSpec>,
147 end: Span,
148}
149
150struct CaseBuild {
151 start: Span,
152 operand: Option<ParsedExpr>,
153 whens: Vec<(ParsedExpr, ParsedExpr)>,
154}
155
156struct SelectBuild {
157 with: Option<WithClause>,
158 first: SelectCore,
159 compounds: Vec<(CompoundOp, SelectCore)>,
160 height: u32,
161 order_by: Vec<OrderingTerm>,
162}
163
164struct CoreBuild {
165 distinct: Distinctness,
166 columns: Vec<ResultColumn>,
167 height: u32,
168 from: Option<FromClause>,
169 where_clause: Option<Box<Expr>>,
170 group_by: Vec<Expr>,
171 having: Option<Box<Expr>>,
172 windows: Vec<WindowDef>,
173}
174
175struct FromBuild {
176 source: TableOrSubquery,
177 joins: Vec<JoinClause>,
178}
179
180struct WindowBuild {
181 base_window: Option<String>,
182 partition_by: Vec<Expr>,
183 order_by: Vec<OrderingTerm>,
184}
185
186pub(crate) struct ParsedFrameBound {
187 pub(crate) value: FrameBound,
188 pub(crate) origin: Token,
189}
190
191fn frame_bound_rank(bound: &FrameBound) -> u8 {
192 match bound {
193 FrameBound::UnboundedPreceding => 0,
194 FrameBound::Preceding(_) => 1,
195 FrameBound::CurrentRow => 2,
196 FrameBound::Following(_) => 3,
197 FrameBound::UnboundedFollowing => 4,
198 }
199}
200
201pub(crate) fn validate_frame_start(
202 start: &ParsedFrameBound,
203 has_explicit_end: bool,
204) -> Result<(), ParseError> {
205 if matches!(start.value, FrameBound::UnboundedFollowing) {
206 return Err(ParseError::at(
207 "window frame starting bound must not be UNBOUNDED FOLLOWING",
208 Some(&start.origin),
209 ));
210 }
211 if !has_explicit_end && frame_bound_rank(&start.value) > 2 {
212 return Err(ParseError::at(
213 "single-bound window frame must not start after CURRENT ROW",
214 Some(&start.origin),
215 ));
216 }
217 Ok(())
218}
219
220pub(crate) fn validate_frame_end(
221 start: &ParsedFrameBound,
222 end: &ParsedFrameBound,
223) -> Result<(), ParseError> {
224 if matches!(end.value, FrameBound::UnboundedPreceding) {
225 return Err(ParseError::at(
226 "window frame ending bound must not be UNBOUNDED PRECEDING",
227 Some(&end.origin),
228 ));
229 }
230 if frame_bound_rank(&end.value) < frame_bound_rank(&start.value) {
231 return Err(ParseError::at(
232 "window frame ending bound must not precede its starting bound",
233 Some(&end.origin),
234 ));
235 }
236 Ok(())
237}
238
239#[allow(clippy::large_enum_variant)]
242enum MachineValue {
243 Expr(ParsedExpr),
244 Select(HeightTracked<SelectStatement>),
245 Core(HeightTracked<SelectCore>),
246 From(FromClause),
247 Table(TableOrSubquery),
248 Ordering(HeightTracked<OrderingTerm>),
249 Window(WindowSpec),
250 FrameBound(ParsedFrameBound),
251 With(WithClause),
252}
253
254#[allow(clippy::large_enum_variant)]
257enum ParseControl {
258 ExprStart {
259 min_bp: u8,
260 },
261 ExprTail {
262 min_bp: u8,
263 },
264 UnaryDone {
265 outer_min_bp: u8,
266 op: UnaryOp,
267 span: Span,
268 },
269 CastDone {
270 outer_min_bp: u8,
271 start: Span,
272 },
273 GroupFirstDone {
274 outer_min_bp: u8,
275 start: Span,
276 },
277 RowItemDone {
278 outer_min_bp: u8,
279 start: Span,
280 values: Vec<Expr>,
281 is_constant: bool,
282 has_function: bool,
283 },
284 CaseOperandDone {
285 outer_min_bp: u8,
286 start: Span,
287 },
288 CaseWhenStart {
289 outer_min_bp: u8,
290 build: CaseBuild,
291 },
292 CaseConditionDone {
293 outer_min_bp: u8,
294 build: CaseBuild,
295 },
296 CaseResultDone {
297 outer_min_bp: u8,
298 build: CaseBuild,
299 condition: ParsedExpr,
300 },
301 CaseElseDone {
302 outer_min_bp: u8,
303 build: CaseBuild,
304 },
305 FunctionArgDone {
306 outer_min_bp: u8,
307 build: FunctionBuild,
308 },
309 FunctionOrderStart {
310 outer_min_bp: u8,
311 build: FunctionBuild,
312 },
313 FunctionOrderDone {
314 outer_min_bp: u8,
315 build: FunctionBuild,
316 },
317 FunctionClose {
318 outer_min_bp: u8,
319 build: FunctionBuild,
320 },
321 FunctionFilterDone {
322 outer_min_bp: u8,
323 build: FunctionBuild,
324 has_filter: bool,
325 },
326 FunctionOverDone {
327 outer_min_bp: u8,
328 build: FunctionBuild,
329 },
330 BinaryDone {
331 outer_min_bp: u8,
332 lhs: ParsedExpr,
333 op: BinaryOp,
334 },
335 JsonDone {
336 outer_min_bp: u8,
337 lhs: ParsedExpr,
338 arrow: JsonArrow,
339 },
340 IsDone {
341 outer_min_bp: u8,
342 lhs: ParsedExpr,
343 not: bool,
344 },
345 LikePatternDone {
346 outer_min_bp: u8,
347 lhs: ParsedExpr,
348 op: LikeOp,
349 not: bool,
350 },
351 LikeEscapeDone {
352 outer_min_bp: u8,
353 lhs: ParsedExpr,
354 pattern: ParsedExpr,
355 op: LikeOp,
356 not: bool,
357 },
358 BetweenLowDone {
359 outer_min_bp: u8,
360 lhs: ParsedExpr,
361 not: bool,
362 },
363 BetweenHighDone {
364 outer_min_bp: u8,
365 lhs: ParsedExpr,
366 low: ParsedExpr,
367 not: bool,
368 },
369 InItemDone {
370 outer_min_bp: u8,
371 lhs: ParsedExpr,
372 not: bool,
373 items: Vec<ParsedExpr>,
374 start: Span,
375 },
376 InSelectDone {
377 outer_min_bp: u8,
378 lhs: ParsedExpr,
379 not: bool,
380 start: Span,
381 },
382 ExistsDone {
383 outer_min_bp: u8,
384 not: bool,
385 start: Span,
386 },
387 ScalarSelectDone {
388 outer_min_bp: u8,
389 start: Span,
390 },
391 OrderingStart,
392 OrderingDone,
393 WindowStart,
394 WindowPartitionDone {
395 build: WindowBuild,
396 },
397 WindowOrderStart {
398 build: WindowBuild,
399 },
400 WindowOrderDone {
401 build: WindowBuild,
402 },
403 WindowFrameStart {
404 build: WindowBuild,
405 },
406 WindowFirstBoundDone {
407 build: WindowBuild,
408 frame_type: FrameType,
409 between: bool,
410 },
411 WindowSecondBoundDone {
412 build: WindowBuild,
413 frame_type: FrameType,
414 start: ParsedFrameBound,
415 },
416 FrameBoundStart,
417 FrameBoundExprDone {
418 origin: Token,
419 },
420 SubqueryStart,
421 SubqueryWithDone,
422 SelectStart {
423 with: Option<WithClause>,
424 },
425 SelectFirstCoreDone {
426 with: Option<WithClause>,
427 },
428 SelectCompoundDone {
429 build: SelectBuild,
430 op: CompoundOp,
431 },
432 SelectOrderStart {
433 build: SelectBuild,
434 },
435 SelectOrderDone {
436 build: SelectBuild,
437 },
438 SelectLimitFirstDone {
439 build: SelectBuild,
440 },
441 SelectLimitSecondDone {
442 build: SelectBuild,
443 first: ParsedExpr,
444 comma_form: bool,
445 },
446 CoreStart,
447 CoreColumnStart {
448 build: CoreBuild,
449 },
450 CoreColumnDone {
451 build: CoreBuild,
452 },
453 CoreAfterColumns {
454 build: CoreBuild,
455 },
456 CoreFromDone {
457 build: CoreBuild,
458 },
459 CoreWhereDone {
460 build: CoreBuild,
461 },
462 CoreGroupDone {
463 build: CoreBuild,
464 },
465 CoreHavingDone {
466 build: CoreBuild,
467 },
468 CoreWindowStart {
469 build: CoreBuild,
470 },
471 CoreWindowDone {
472 build: CoreBuild,
473 name: String,
474 },
475 ValuesRowStart {
476 rows: Vec<Vec<Expr>>,
477 height: u32,
478 force_union_all_from: Option<usize>,
479 },
480 ValuesItemDone {
481 rows: Vec<Vec<Expr>>,
482 row: Vec<Expr>,
483 height: u32,
484 force_union_all_from: Option<usize>,
485 },
486 FromStart,
487 FromSourceDone,
488 FromTableDone {
489 build: FromBuild,
490 join_type: JoinType,
491 },
492 FromJoinConstraintDone {
493 build: FromBuild,
494 join_type: JoinType,
495 table: TableOrSubquery,
496 },
497 TableStart,
498 TableSubqueryDone,
499 TableParenJoinDone,
500 TableFunctionArgDone {
501 name: String,
502 args: Vec<Expr>,
503 },
504 WithStart,
505 CteQueryDone {
506 recursive: bool,
507 ctes: Vec<Cte>,
508 name: String,
509 columns: Vec<String>,
510 materialized: Option<CteMaterialized>,
511 },
512}
513
514impl ParsedExpr {
515 fn leaf(expr: Expr) -> Self {
516 let (is_constant, has_function) = match &expr {
517 Expr::Literal(
518 Literal::CurrentTime | Literal::CurrentDate | Literal::CurrentTimestamp,
519 _,
520 ) => (false, true),
521 Expr::Literal(..) | Expr::BoundOuterValue { .. } => (true, false),
522 _ => (false, false),
523 };
524 Self {
525 expr,
526 height: 1,
527 is_constant,
528 has_function,
529 root: CachedRoot::Other,
530 }
531 }
532}
533
534#[cfg(test)]
535enum CachedHeightTask<'a> {
536 Expr(&'a Expr),
537 Select(&'a SelectStatement),
538 SelectCore(&'a SelectCore),
539 Limit(&'a fsqlite_ast::LimitClause),
540 Finish(CachedFinish),
541}
542
543#[cfg(test)]
544#[derive(Clone, Copy)]
545enum CachedFinish {
546 Generic(usize),
547 Unary(UnaryOp),
548 Vector(usize),
549 Like { children: usize, not: bool },
550 Between { not: bool },
551 InList { items: usize, not: bool },
552 InSubquery { not: bool },
553 InTable { not: bool },
554 Exists { not: bool },
555 Subquery,
556 Function { args: usize },
557 Select { expressions: usize },
558 Limit { expressions: usize },
559}
560
561#[cfg(test)]
562#[derive(Clone, Copy)]
563struct CachedFacts {
564 height: u32,
565 is_constant: bool,
566 has_function: bool,
567 root: CachedRoot,
568}
569
570#[cfg(test)]
571impl CachedFacts {
572 const fn leaf(is_constant: bool, has_function: bool) -> Self {
573 Self {
574 height: 1,
575 is_constant,
576 has_function,
577 root: CachedRoot::Other,
578 }
579 }
580}
581
582#[cfg(test)]
583thread_local! {
584 static HEIGHT_WALK_VISITS: Cell<usize> = const { Cell::new(0) };
585 static PARSE_MACHINE_STEPS: Cell<usize> = const { Cell::new(0) };
586 static PARSE_MACHINE_STACK_SPILLS: Cell<usize> = const { Cell::new(0) };
587}
588
589#[cfg(test)]
590fn aggregate_cached_facts(values: &mut Vec<CachedFacts>, count: usize) -> CachedFacts {
591 let start = values.len().saturating_sub(count);
592 let mut facts = CachedFacts {
593 height: 0,
594 is_constant: true,
595 has_function: false,
596 root: CachedRoot::Other,
597 };
598 for child in &values[start..] {
599 facts.height = facts.height.max(child.height);
600 facts.is_constant &= child.is_constant;
601 facts.has_function |= child.has_function;
602 }
603 if count == 1 {
604 facts.root = values[start].root;
605 }
606 values.truncate(start);
607 facts
608}
609
610#[cfg(test)]
611fn cached_facts_from_tasks(mut pending: Vec<CachedHeightTask<'_>>) -> CachedFacts {
612 let mut values = Vec::new();
613 while let Some(task) = pending.pop() {
614 #[cfg(test)]
615 HEIGHT_WALK_VISITS.set(HEIGHT_WALK_VISITS.get() + 1);
616 match task {
617 CachedHeightTask::Expr(current) => match current {
618 Expr::BinaryOp { left, right, .. } => {
619 pending.push(CachedHeightTask::Finish(CachedFinish::Generic(2)));
620 pending.push(CachedHeightTask::Expr(left));
621 pending.push(CachedHeightTask::Expr(right));
622 }
623 Expr::UnaryOp { op, expr, .. } => {
624 pending.push(CachedHeightTask::Finish(CachedFinish::Unary(*op)));
625 pending.push(CachedHeightTask::Expr(expr));
626 }
627 Expr::Cast { expr, .. }
628 | Expr::Collate { expr, .. }
629 | Expr::IsNull { expr, .. } => {
630 pending.push(CachedHeightTask::Finish(CachedFinish::Generic(1)));
631 pending.push(CachedHeightTask::Expr(expr));
632 }
633 Expr::Between {
634 expr,
635 low,
636 high,
637 not,
638 ..
639 } => {
640 pending.push(CachedHeightTask::Finish(CachedFinish::Between {
641 not: *not,
642 }));
643 pending.push(CachedHeightTask::Expr(expr));
644 pending.push(CachedHeightTask::Expr(low));
645 pending.push(CachedHeightTask::Expr(high));
646 }
647 Expr::In { expr, set, not, .. } => match set {
648 InSet::List(values) => {
649 pending.push(CachedHeightTask::Finish(CachedFinish::InList {
650 items: values.len(),
651 not: *not,
652 }));
653 pending.push(CachedHeightTask::Expr(expr));
654 pending.extend(values.iter().map(CachedHeightTask::Expr));
655 }
656 InSet::Subquery(select) => {
657 pending.push(CachedHeightTask::Finish(CachedFinish::InSubquery {
658 not: *not,
659 }));
660 pending.push(CachedHeightTask::Expr(expr));
661 pending.push(CachedHeightTask::Select(select));
662 }
663 InSet::Table(_) => {
664 pending.push(CachedHeightTask::Finish(CachedFinish::InTable {
665 not: *not,
666 }));
667 pending.push(CachedHeightTask::Expr(expr));
668 }
669 },
670 Expr::Like {
671 expr,
672 pattern,
673 escape,
674 not,
675 ..
676 } => {
677 pending.push(CachedHeightTask::Finish(CachedFinish::Like {
678 children: 2 + usize::from(escape.is_some()),
679 not: *not,
680 }));
681 pending.push(CachedHeightTask::Expr(expr));
682 pending.push(CachedHeightTask::Expr(pattern));
683 if let Some(escape) = escape {
684 pending.push(CachedHeightTask::Expr(escape));
685 }
686 }
687 Expr::Case {
688 operand,
689 whens,
690 else_expr,
691 ..
692 } => {
693 let children = usize::from(operand.is_some())
694 + whens.len().saturating_mul(2)
695 + usize::from(else_expr.is_some());
696 pending.push(CachedHeightTask::Finish(CachedFinish::Generic(children)));
697 if let Some(operand) = operand {
698 pending.push(CachedHeightTask::Expr(operand));
699 }
700 for (condition, result) in whens {
701 pending.push(CachedHeightTask::Expr(condition));
702 pending.push(CachedHeightTask::Expr(result));
703 }
704 if let Some(else_expr) = else_expr {
705 pending.push(CachedHeightTask::Expr(else_expr));
706 }
707 }
708 Expr::Exists { subquery, not, .. } => {
709 pending.push(CachedHeightTask::Finish(CachedFinish::Exists { not: *not }));
710 pending.push(CachedHeightTask::Select(subquery));
711 }
712 Expr::Subquery(subquery, _) => {
713 pending.push(CachedHeightTask::Finish(CachedFinish::Subquery));
714 pending.push(CachedHeightTask::Select(subquery));
715 }
716 Expr::FunctionCall { args, .. } => {
717 let FunctionArgs::List(args) = args else {
718 values.push(CachedFacts {
719 height: 1,
720 is_constant: false,
721 has_function: true,
722 root: CachedRoot::Other,
723 });
724 continue;
725 };
726 pending.push(CachedHeightTask::Finish(CachedFinish::Function {
727 args: args.len(),
728 }));
729 pending.extend(args.iter().map(CachedHeightTask::Expr));
730 }
731 Expr::JsonAccess { expr, path, .. } => {
732 pending.push(CachedHeightTask::Finish(CachedFinish::Like {
733 children: 2,
734 not: false,
735 }));
736 pending.push(CachedHeightTask::Expr(expr));
737 pending.push(CachedHeightTask::Expr(path));
738 }
739 Expr::RowValue(items, _) => {
740 pending.push(CachedHeightTask::Finish(CachedFinish::Vector(items.len())));
741 pending.extend(items.iter().map(CachedHeightTask::Expr));
742 }
743 Expr::Literal(
744 Literal::CurrentTime | Literal::CurrentDate | Literal::CurrentTimestamp,
745 _,
746 ) => values.push(CachedFacts::leaf(false, true)),
747 Expr::Literal(..) | Expr::BoundOuterValue { .. } => {
748 values.push(CachedFacts::leaf(true, false));
749 }
750 Expr::Column(column, _) if column.table.is_some() => {
751 values.push(CachedFacts {
752 height: 2,
753 is_constant: false,
754 has_function: false,
755 root: CachedRoot::Other,
756 });
757 }
758 Expr::Column(..) | Expr::Raise { .. } | Expr::Placeholder(..) => {
759 values.push(CachedFacts::leaf(false, false));
760 }
761 },
762 CachedHeightTask::Select(select) => {
763 let expressions = 1
764 + select.body.compounds.len()
765 + select.order_by.len()
766 + usize::from(select.limit.is_some());
767 pending.push(CachedHeightTask::Finish(CachedFinish::Select {
768 expressions,
769 }));
770 pending.push(CachedHeightTask::SelectCore(&select.body.select));
771 pending.extend(
772 select
773 .body
774 .compounds
775 .iter()
776 .map(|(_, core)| CachedHeightTask::SelectCore(core)),
777 );
778 pending.extend(
779 select
780 .order_by
781 .iter()
782 .map(|term| CachedHeightTask::Expr(&term.expr)),
783 );
784 if let Some(limit) = &select.limit {
785 pending.push(CachedHeightTask::Limit(limit));
786 }
787 }
788 CachedHeightTask::SelectCore(core) => match core {
789 SelectCore::Select {
790 columns,
791 where_clause,
792 group_by,
793 having,
794 ..
795 } => {
796 let expressions = columns
797 .iter()
798 .filter(|column| matches!(column, ResultColumn::Expr { .. }))
799 .count()
800 + usize::from(where_clause.is_some())
801 + group_by.len()
802 + usize::from(having.is_some());
803 pending.push(CachedHeightTask::Finish(CachedFinish::Select {
804 expressions,
805 }));
806 pending.extend(columns.iter().filter_map(|column| match column {
807 ResultColumn::Expr { expr, .. } => Some(CachedHeightTask::Expr(expr)),
808 ResultColumn::Star | ResultColumn::TableStar(_) => None,
809 }));
810 if let Some(where_clause) = where_clause {
811 pending.push(CachedHeightTask::Expr(where_clause));
812 }
813 pending.extend(group_by.iter().map(CachedHeightTask::Expr));
814 if let Some(having) = having {
815 pending.push(CachedHeightTask::Expr(having));
816 }
817 }
818 SelectCore::Values(rows) => {
819 let expressions = rows.iter().map(Vec::len).sum();
820 pending.push(CachedHeightTask::Finish(CachedFinish::Select {
821 expressions,
822 }));
823 pending.extend(rows.iter().flatten().map(CachedHeightTask::Expr));
824 }
825 },
826 CachedHeightTask::Limit(limit) => {
827 let expressions = 1 + usize::from(limit.offset.is_some());
828 pending.push(CachedHeightTask::Finish(CachedFinish::Limit {
829 expressions,
830 }));
831 pending.push(CachedHeightTask::Expr(&limit.limit));
832 if let Some(offset) = &limit.offset {
833 pending.push(CachedHeightTask::Expr(offset));
834 }
835 }
836 CachedHeightTask::Finish(finish) => match finish {
837 CachedFinish::Generic(children) => {
838 let mut facts = aggregate_cached_facts(&mut values, children);
839 facts.height = facts.height.saturating_add(1);
840 facts.root = CachedRoot::Other;
841 values.push(facts);
842 }
843 CachedFinish::Unary(op) => {
844 let mut child = values.pop().expect("unary cached-height child");
845 if !(matches!(op, UnaryOp::Plus | UnaryOp::Negate)
846 && child.root == CachedRoot::UnaryPlus)
847 {
848 child.height = child.height.saturating_add(1);
849 }
850 child.root = if op == UnaryOp::Plus {
851 CachedRoot::UnaryPlus
852 } else {
853 CachedRoot::Other
854 };
855 values.push(child);
856 }
857 CachedFinish::Vector(children) => {
858 let mut facts = aggregate_cached_facts(&mut values, children);
859 facts.height = 1;
860 facts.root = CachedRoot::Vector;
861 values.push(facts);
862 }
863 CachedFinish::Like { children, not } => {
864 let mut facts = aggregate_cached_facts(&mut values, children);
865 facts.height = facts
866 .height
867 .saturating_add(1)
868 .saturating_add(u32::from(not));
869 facts.is_constant = false;
870 facts.has_function = true;
871 facts.root = CachedRoot::Other;
872 values.push(facts);
873 }
874 CachedFinish::Between { not } => {
875 let mut facts = aggregate_cached_facts(&mut values, 3);
876 facts.height = facts
877 .height
878 .saturating_add(1)
879 .saturating_add(u32::from(not));
880 facts.root = CachedRoot::Other;
881 values.push(facts);
882 }
883 CachedFinish::InList { items, not } => {
884 let lhs = values.pop().expect("IN cached-height lhs");
885 let item_facts = aggregate_cached_facts(&mut values, items);
886 if items == 0 {
887 values.push(if lhs.has_function {
888 CachedFacts {
889 height: lhs.height.saturating_add(1),
890 is_constant: false,
891 has_function: true,
892 root: CachedRoot::Other,
893 }
894 } else {
895 CachedFacts::leaf(true, false)
896 });
897 continue;
898 }
899 let cached_child_height =
900 if items == 1 && item_facts.is_constant && lhs.root != CachedRoot::Vector {
901 lhs.height.max(item_facts.height.saturating_add(1))
902 } else if items == 1 && item_facts.root == CachedRoot::ScalarSubquery {
903 lhs.height.max(item_facts.height.saturating_sub(1))
904 } else {
905 lhs.height.max(item_facts.height)
906 };
907 values.push(CachedFacts {
908 height: cached_child_height
909 .saturating_add(1)
910 .saturating_add(u32::from(not)),
911 is_constant: lhs.is_constant && item_facts.is_constant,
912 has_function: lhs.has_function || item_facts.has_function,
913 root: CachedRoot::Other,
914 });
915 }
916 CachedFinish::InSubquery { not } => {
917 let lhs = values.pop().expect("IN-subquery cached-height lhs");
918 let select = values.pop().expect("IN-subquery cached-height SELECT");
919 values.push(CachedFacts {
920 height: lhs
921 .height
922 .max(select.height)
923 .saturating_add(1)
924 .saturating_add(u32::from(not)),
925 is_constant: false,
926 has_function: lhs.has_function,
927 root: CachedRoot::Other,
928 });
929 }
930 CachedFinish::InTable { not } => {
931 let lhs = values.pop().expect("IN-table cached-height lhs");
932 values.push(CachedFacts {
933 height: lhs.height.saturating_add(1).saturating_add(u32::from(not)),
934 is_constant: false,
935 has_function: lhs.has_function,
936 root: CachedRoot::Other,
937 });
938 }
939 CachedFinish::Exists { not } => {
940 let select = values.pop().expect("EXISTS cached-height SELECT");
941 values.push(CachedFacts {
942 height: select
943 .height
944 .saturating_add(1)
945 .saturating_add(u32::from(not)),
946 is_constant: false,
947 has_function: false,
948 root: CachedRoot::Other,
949 });
950 }
951 CachedFinish::Subquery => {
952 let select = values.pop().expect("scalar-subquery cached-height SELECT");
953 values.push(CachedFacts {
954 height: select.height.saturating_add(1),
955 is_constant: false,
956 has_function: false,
957 root: CachedRoot::ScalarSubquery,
958 });
959 }
960 CachedFinish::Function { args } => {
961 let facts = aggregate_cached_facts(&mut values, args);
962 values.push(CachedFacts {
963 height: facts.height.saturating_add(1),
964 is_constant: false,
965 has_function: true,
966 root: CachedRoot::Other,
967 });
968 }
969 CachedFinish::Select { expressions } => {
970 let facts = aggregate_cached_facts(&mut values, expressions);
971 values.push(CachedFacts {
972 height: facts.height,
973 is_constant: false,
974 has_function: false,
975 root: CachedRoot::Other,
976 });
977 }
978 CachedFinish::Limit { expressions } => {
979 let mut facts = aggregate_cached_facts(&mut values, expressions);
980 facts.height = facts.height.saturating_add(1);
981 facts.root = CachedRoot::Other;
982 values.push(facts);
983 }
984 },
985 }
986 }
987 values.pop().unwrap_or(CachedFacts {
988 height: 0,
989 is_constant: false,
990 has_function: false,
991 root: CachedRoot::Other,
992 })
993}
994
995#[cfg(test)]
1000#[must_use]
1001fn normalized_ast_expr_height(expr: &Expr) -> u32 {
1002 cached_facts_from_tasks(vec![CachedHeightTask::Expr(expr)]).height
1003}
1004
1005#[cfg(test)]
1010#[must_use]
1011fn normalized_ast_select_height(select: &SelectStatement) -> u32 {
1012 cached_facts_from_tasks(vec![CachedHeightTask::Select(select)]).height
1013}
1014
1015mod bp {
1018 pub const OR: (u8, u8) = (1, 2);
1020 pub const AND: (u8, u8) = (3, 4);
1021 pub const NOT_PREFIX: u8 = 5;
1023 pub const EQUALITY: (u8, u8) = (7, 8);
1025 pub const COMPARISON: (u8, u8) = (9, 10);
1027 pub const BITWISE: (u8, u8) = (13, 14);
1029 pub const ADD: (u8, u8) = (15, 16);
1031 pub const MUL: (u8, u8) = (17, 18);
1033 pub const CONCAT: (u8, u8) = (19, 20);
1035 pub const COLLATE: u8 = 21;
1037 pub const UNARY: u8 = 23;
1039 pub const JSON: (u8, u8) = (19, 20);
1041}
1042
1043struct ParseMachine<'a> {
1044 parser: &'a mut Parser,
1045 controls: InlineStack<ParseControl, 8>,
1046 values: InlineStack<MachineValue, 8>,
1047}
1048
1049impl<'a> ParseMachine<'a> {
1050 fn for_expr(parser: &'a mut Parser) -> Self {
1051 let mut controls = InlineStack::new();
1052 controls.push(ParseControl::ExprStart { min_bp: 0 });
1053 Self {
1054 parser,
1055 controls,
1056 values: InlineStack::new(),
1057 }
1058 }
1059
1060 fn for_select(parser: &'a mut Parser, with: Option<WithClause>) -> Self {
1061 let mut controls = InlineStack::new();
1062 controls.push(ParseControl::SelectStart { with });
1063 Self {
1064 parser,
1065 controls,
1066 values: InlineStack::new(),
1067 }
1068 }
1069
1070 fn for_with(parser: &'a mut Parser) -> Self {
1071 let mut controls = InlineStack::new();
1072 controls.push(ParseControl::WithStart);
1073 Self {
1074 parser,
1075 controls,
1076 values: InlineStack::new(),
1077 }
1078 }
1079
1080 fn for_from(parser: &'a mut Parser) -> Self {
1081 let mut controls = InlineStack::new();
1082 controls.push(ParseControl::FromStart);
1083 Self {
1084 parser,
1085 controls,
1086 values: InlineStack::new(),
1087 }
1088 }
1089
1090 fn run_expr(mut self) -> Result<ParsedExpr, ParseError> {
1091 self.run()?;
1092 self.pop_expr()
1093 }
1094
1095 fn run_select(mut self) -> Result<HeightTracked<SelectStatement>, ParseError> {
1096 self.run()?;
1097 self.pop_select()
1098 }
1099
1100 fn run_with(mut self) -> Result<WithClause, ParseError> {
1101 self.run()?;
1102 self.pop_with()
1103 }
1104
1105 fn run_from(mut self) -> Result<FromClause, ParseError> {
1106 self.run()?;
1107 self.pop_from()
1108 }
1109
1110 fn run(&mut self) -> Result<(), ParseError> {
1111 while let Some(control) = self.controls.pop() {
1112 #[cfg(test)]
1113 PARSE_MACHINE_STEPS.set(PARSE_MACHINE_STEPS.get().saturating_add(1));
1114 self.step(control)?;
1115 }
1116 Ok(())
1117 }
1118
1119 fn pop_expr(&mut self) -> Result<ParsedExpr, ParseError> {
1120 match self.values.pop() {
1121 Some(MachineValue::Expr(expr)) => Ok(expr),
1122 _ => Err(self
1123 .parser
1124 .err_here("internal expression parser state mismatch")),
1125 }
1126 }
1127
1128 fn pop_select(&mut self) -> Result<HeightTracked<SelectStatement>, ParseError> {
1129 match self.values.pop() {
1130 Some(MachineValue::Select(select)) => Ok(select),
1131 _ => Err(self
1132 .parser
1133 .err_here("internal SELECT parser state mismatch")),
1134 }
1135 }
1136
1137 fn pop_core(&mut self) -> Result<HeightTracked<SelectCore>, ParseError> {
1138 match self.values.pop() {
1139 Some(MachineValue::Core(core)) => Ok(core),
1140 _ => Err(self
1141 .parser
1142 .err_here("internal SELECT-core parser state mismatch")),
1143 }
1144 }
1145
1146 fn pop_from(&mut self) -> Result<FromClause, ParseError> {
1147 match self.values.pop() {
1148 Some(MachineValue::From(from)) => Ok(from),
1149 _ => Err(self.parser.err_here("internal FROM parser state mismatch")),
1150 }
1151 }
1152
1153 fn pop_table(&mut self) -> Result<TableOrSubquery, ParseError> {
1154 match self.values.pop() {
1155 Some(MachineValue::Table(table)) => Ok(table),
1156 _ => Err(self.parser.err_here("internal table parser state mismatch")),
1157 }
1158 }
1159
1160 fn pop_ordering(&mut self) -> Result<HeightTracked<OrderingTerm>, ParseError> {
1161 match self.values.pop() {
1162 Some(MachineValue::Ordering(term)) => Ok(term),
1163 _ => Err(self
1164 .parser
1165 .err_here("internal ORDER BY parser state mismatch")),
1166 }
1167 }
1168
1169 fn pop_window(&mut self) -> Result<WindowSpec, ParseError> {
1170 match self.values.pop() {
1171 Some(MachineValue::Window(window)) => Ok(window),
1172 _ => Err(self
1173 .parser
1174 .err_here("internal WINDOW parser state mismatch")),
1175 }
1176 }
1177
1178 fn pop_frame_bound(&mut self) -> Result<ParsedFrameBound, ParseError> {
1179 match self.values.pop() {
1180 Some(MachineValue::FrameBound(bound)) => Ok(bound),
1181 _ => Err(self
1182 .parser
1183 .err_here("internal frame-bound parser state mismatch")),
1184 }
1185 }
1186
1187 fn pop_with(&mut self) -> Result<WithClause, ParseError> {
1188 match self.values.pop() {
1189 Some(MachineValue::With(with)) => Ok(with),
1190 _ => Err(self.parser.err_here("internal WITH parser state mismatch")),
1191 }
1192 }
1193
1194 fn push_expr_tail(&mut self, expr: ParsedExpr, min_bp: u8) {
1195 self.values.push(MachineValue::Expr(expr));
1196 self.controls.push(ParseControl::ExprTail { min_bp });
1197 }
1198
1199 fn finish_function(
1200 &mut self,
1201 outer_min_bp: u8,
1202 build: FunctionBuild,
1203 ) -> Result<(), ParseError> {
1204 let span = build.start.merge(build.end);
1205 let parsed = self.parser.checked_expr(
1206 Expr::FunctionCall {
1207 name: build.name,
1208 args: build.args,
1209 distinct: build.distinct,
1210 order_by: build.order_by,
1211 filter: build.filter,
1212 over: build.over,
1213 span,
1214 },
1215 build.height,
1216 false,
1217 true,
1218 )?;
1219 self.push_expr_tail(parsed, outer_min_bp);
1220 Ok(())
1221 }
1222
1223 #[allow(clippy::too_many_lines)]
1224 fn step(&mut self, control: ParseControl) -> Result<(), ParseError> {
1225 match control {
1226 ParseControl::ExprStart { min_bp } => self.expr_start(min_bp),
1227 ParseControl::ExprTail { min_bp } => self.expr_tail(min_bp),
1228 ParseControl::UnaryDone {
1229 outer_min_bp,
1230 op,
1231 span,
1232 } => {
1233 let inner = self.pop_expr()?;
1234 let span = span.merge(inner.expr.span());
1235 let parsed = self.parser.finish_unary(op, inner, span)?;
1236 self.push_expr_tail(parsed, outer_min_bp);
1237 Ok(())
1238 }
1239 ParseControl::CastDone {
1240 outer_min_bp,
1241 start,
1242 } => {
1243 let inner = self.pop_expr()?;
1244 self.parser.expect_kind(&TokenKind::KwAs)?;
1245 let type_name = self.parser.parse_type_name()?;
1246 let end = self.parser.expect_kind(&TokenKind::RightParen)?;
1247 let height = inner.height;
1248 let is_constant = inner.is_constant;
1249 let has_function = inner.has_function;
1250 let parsed = self.parser.checked_expr(
1251 Expr::Cast {
1252 expr: Box::new(inner.expr),
1253 type_name,
1254 span: start.merge(end),
1255 },
1256 height,
1257 is_constant,
1258 has_function,
1259 )?;
1260 self.push_expr_tail(parsed, outer_min_bp);
1261 Ok(())
1262 }
1263 ParseControl::GroupFirstDone {
1264 outer_min_bp,
1265 start,
1266 } => {
1267 let first = self.pop_expr()?;
1268 if self.parser.eat_kind(&TokenKind::Comma) {
1269 let is_constant = first.is_constant;
1270 let has_function = first.has_function;
1271 self.controls.push(ParseControl::RowItemDone {
1272 outer_min_bp,
1273 start,
1274 values: vec![first.expr],
1275 is_constant,
1276 has_function,
1277 });
1278 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
1279 } else {
1280 self.parser.expect_kind(&TokenKind::RightParen)?;
1281 self.push_expr_tail(first, outer_min_bp);
1282 }
1283 Ok(())
1284 }
1285 ParseControl::RowItemDone {
1286 outer_min_bp,
1287 start,
1288 mut values,
1289 mut is_constant,
1290 mut has_function,
1291 } => {
1292 let parsed = self.pop_expr()?;
1293 is_constant &= parsed.is_constant;
1294 has_function |= parsed.has_function;
1295 values.push(parsed.expr);
1296 if self.parser.eat_kind(&TokenKind::Comma) {
1297 self.controls.push(ParseControl::RowItemDone {
1298 outer_min_bp,
1299 start,
1300 values,
1301 is_constant,
1302 has_function,
1303 });
1304 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
1305 } else {
1306 let end = self.parser.expect_kind(&TokenKind::RightParen)?;
1307 let parsed = self.parser.finish_expr(
1308 Expr::RowValue(values, start.merge(end)),
1309 1,
1310 is_constant,
1311 has_function,
1312 )?;
1313 self.push_expr_tail(parsed, outer_min_bp);
1314 }
1315 Ok(())
1316 }
1317 ParseControl::CaseOperandDone {
1318 outer_min_bp,
1319 start,
1320 } => {
1321 let operand = self.pop_expr()?;
1322 self.controls.push(ParseControl::CaseWhenStart {
1323 outer_min_bp,
1324 build: CaseBuild {
1325 start,
1326 operand: Some(operand),
1327 whens: Vec::new(),
1328 },
1329 });
1330 Ok(())
1331 }
1332 ParseControl::CaseWhenStart {
1333 outer_min_bp,
1334 build,
1335 } => {
1336 if self.parser.eat_kind(&TokenKind::KwWhen) {
1337 self.controls.push(ParseControl::CaseConditionDone {
1338 outer_min_bp,
1339 build,
1340 });
1341 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
1342 return Ok(());
1343 }
1344 if build.whens.is_empty() {
1345 return Err(self
1346 .parser
1347 .err_here("CASE requires at least one WHEN clause"));
1348 }
1349 if self.parser.eat_kind(&TokenKind::KwElse) {
1350 self.controls.push(ParseControl::CaseElseDone {
1351 outer_min_bp,
1352 build,
1353 });
1354 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
1355 return Ok(());
1356 }
1357 self.finish_case(outer_min_bp, build, None)
1358 }
1359 ParseControl::CaseConditionDone {
1360 outer_min_bp,
1361 build,
1362 } => {
1363 let condition = self.pop_expr()?;
1364 if !self.parser.eat_kind(&TokenKind::KwThen) {
1365 return Err(self.parser.err_here("expected THEN in CASE expression"));
1366 }
1367 self.controls.push(ParseControl::CaseResultDone {
1368 outer_min_bp,
1369 build,
1370 condition,
1371 });
1372 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
1373 Ok(())
1374 }
1375 ParseControl::CaseResultDone {
1376 outer_min_bp,
1377 mut build,
1378 condition,
1379 } => {
1380 let result = self.pop_expr()?;
1381 build.whens.push((condition, result));
1382 self.controls.push(ParseControl::CaseWhenStart {
1383 outer_min_bp,
1384 build,
1385 });
1386 Ok(())
1387 }
1388 ParseControl::CaseElseDone {
1389 outer_min_bp,
1390 build,
1391 } => {
1392 let else_expr = self.pop_expr()?;
1393 self.finish_case(outer_min_bp, build, Some(else_expr))
1394 }
1395 ParseControl::FunctionArgDone {
1396 outer_min_bp,
1397 mut build,
1398 } => {
1399 let arg = self.pop_expr()?;
1400 build.height = build.height.max(arg.height);
1401 let FunctionArgs::List(args) = &mut build.args else {
1402 return Err(self
1403 .parser
1404 .err_here("internal function argument state mismatch"));
1405 };
1406 args.push(arg.expr);
1407 if self.parser.eat_kind(&TokenKind::Comma) {
1408 self.controls.push(ParseControl::FunctionArgDone {
1409 outer_min_bp,
1410 build,
1411 });
1412 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
1413 } else {
1414 self.controls.push(ParseControl::FunctionOrderStart {
1415 outer_min_bp,
1416 build,
1417 });
1418 }
1419 Ok(())
1420 }
1421 ParseControl::FunctionOrderStart {
1422 outer_min_bp,
1423 build,
1424 } => {
1425 if self.parser.eat_kind(&TokenKind::KwOrder) {
1426 self.parser.expect_kind(&TokenKind::KwBy)?;
1427 self.controls.push(ParseControl::FunctionOrderDone {
1428 outer_min_bp,
1429 build,
1430 });
1431 self.controls.push(ParseControl::OrderingStart);
1432 } else {
1433 self.controls.push(ParseControl::FunctionClose {
1434 outer_min_bp,
1435 build,
1436 });
1437 }
1438 Ok(())
1439 }
1440 ParseControl::FunctionOrderDone {
1441 outer_min_bp,
1442 mut build,
1443 } => {
1444 let term = self.pop_ordering()?;
1445 build.order_by.push(term.value);
1446 if self.parser.eat_kind(&TokenKind::Comma) {
1447 self.controls.push(ParseControl::FunctionOrderDone {
1448 outer_min_bp,
1449 build,
1450 });
1451 self.controls.push(ParseControl::OrderingStart);
1452 } else {
1453 self.controls.push(ParseControl::FunctionClose {
1454 outer_min_bp,
1455 build,
1456 });
1457 }
1458 Ok(())
1459 }
1460 ParseControl::FunctionClose {
1461 outer_min_bp,
1462 mut build,
1463 } => {
1464 build.end = self.parser.expect_kind(&TokenKind::RightParen)?;
1465 if matches!(self.parser.peek_kind(), TokenKind::KwFilter)
1466 && self
1467 .parser
1468 .tokens
1469 .get(self.parser.pos + 1)
1470 .is_some_and(|token| token.kind == TokenKind::LeftParen)
1471 {
1472 self.parser.advance_token();
1473 self.parser.expect_kind(&TokenKind::LeftParen)?;
1474 self.parser.expect_kind(&TokenKind::KwWhere)?;
1475 self.controls.push(ParseControl::FunctionFilterDone {
1476 outer_min_bp,
1477 build,
1478 has_filter: true,
1479 });
1480 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
1481 } else {
1482 self.controls.push(ParseControl::FunctionFilterDone {
1483 outer_min_bp,
1484 build,
1485 has_filter: false,
1486 });
1487 }
1488 Ok(())
1489 }
1490 ParseControl::FunctionFilterDone {
1491 outer_min_bp,
1492 mut build,
1493 has_filter,
1494 } => {
1495 if has_filter {
1496 let filter = self.pop_expr()?;
1497 let end = self.parser.expect_kind(&TokenKind::RightParen)?;
1498 build.end = build.end.merge(end);
1499 build.filter = Some(Box::new(filter.expr));
1500 }
1501 if matches!(self.parser.peek_kind(), TokenKind::KwOver)
1502 && self
1503 .parser
1504 .tokens
1505 .get(self.parser.pos + 1)
1506 .is_some_and(|token| {
1507 matches!(token.kind, TokenKind::LeftParen)
1508 || starts_bare_window_name(&token.kind)
1509 })
1510 {
1511 self.parser.advance_token();
1512 if self.parser.eat_kind(&TokenKind::LeftParen) {
1513 self.controls.push(ParseControl::FunctionOverDone {
1514 outer_min_bp,
1515 build,
1516 });
1517 self.controls.push(ParseControl::WindowStart);
1518 } else {
1519 let base_window = self.parser.parse_window_name()?;
1520 let base_span = self.parser.tokens[self.parser.pos.saturating_sub(1)].span;
1521 build.end = build.end.merge(base_span);
1522 build.over = Some(WindowSpec {
1523 window_ref: Some(WindowReference::Direct(base_window)),
1524 partition_by: Vec::new(),
1525 order_by: Vec::new(),
1526 frame: None,
1527 });
1528 self.finish_function(outer_min_bp, build)?;
1529 }
1530 } else {
1531 self.finish_function(outer_min_bp, build)?;
1532 }
1533 Ok(())
1534 }
1535 ParseControl::FunctionOverDone {
1536 outer_min_bp,
1537 mut build,
1538 } => {
1539 build.over = Some(self.pop_window()?);
1540 let end = self.parser.expect_kind(&TokenKind::RightParen)?;
1541 build.end = build.end.merge(end);
1542 self.finish_function(outer_min_bp, build)
1543 }
1544 ParseControl::BinaryDone {
1545 outer_min_bp,
1546 lhs,
1547 op,
1548 } => {
1549 let rhs = self.pop_expr()?;
1550 let span = lhs.expr.span().merge(rhs.expr.span());
1551 let height = lhs.height.max(rhs.height);
1552 let is_constant = lhs.is_constant && rhs.is_constant;
1553 let has_function = lhs.has_function || rhs.has_function;
1554 let parsed = self.parser.checked_expr(
1555 Expr::BinaryOp {
1556 left: Box::new(lhs.expr),
1557 op,
1558 right: Box::new(rhs.expr),
1559 span,
1560 },
1561 height,
1562 is_constant,
1563 has_function,
1564 )?;
1565 self.push_expr_tail(parsed, outer_min_bp);
1566 Ok(())
1567 }
1568 ParseControl::JsonDone {
1569 outer_min_bp,
1570 lhs,
1571 arrow,
1572 } => {
1573 let rhs = self.pop_expr()?;
1574 let span = lhs.expr.span().merge(rhs.expr.span());
1575 let height = lhs.height.max(rhs.height);
1576 let parsed = self.parser.checked_expr(
1577 Expr::JsonAccess {
1578 expr: Box::new(lhs.expr),
1579 path: Box::new(rhs.expr),
1580 arrow,
1581 span,
1582 },
1583 height,
1584 false,
1585 true,
1586 )?;
1587 self.push_expr_tail(parsed, outer_min_bp);
1588 Ok(())
1589 }
1590 ParseControl::IsDone {
1591 outer_min_bp,
1592 lhs,
1593 not,
1594 } => {
1595 let rhs = self.pop_expr()?;
1596 let span = lhs.expr.span().merge(rhs.expr.span());
1597 let parsed = if matches!(&rhs.expr, Expr::Literal(Literal::Null, _)) {
1598 self.parser.checked_expr(
1599 Expr::IsNull {
1600 expr: Box::new(lhs.expr),
1601 not,
1602 span,
1603 },
1604 lhs.height,
1605 lhs.is_constant,
1606 lhs.has_function,
1607 )?
1608 } else {
1609 let height = lhs.height.max(rhs.height);
1610 let is_constant = lhs.is_constant && rhs.is_constant;
1611 let has_function = lhs.has_function || rhs.has_function;
1612 self.parser.checked_expr(
1613 Expr::BinaryOp {
1614 left: Box::new(lhs.expr),
1615 op: if not { BinaryOp::IsNot } else { BinaryOp::Is },
1616 right: Box::new(rhs.expr),
1617 span,
1618 },
1619 height,
1620 is_constant,
1621 has_function,
1622 )?
1623 };
1624 self.push_expr_tail(parsed, outer_min_bp);
1625 Ok(())
1626 }
1627 ParseControl::LikePatternDone {
1628 outer_min_bp,
1629 lhs,
1630 op,
1631 not,
1632 } => {
1633 let pattern = self.pop_expr()?;
1634 if self.parser.eat_kind(&TokenKind::KwEscape) {
1635 self.controls.push(ParseControl::LikeEscapeDone {
1636 outer_min_bp,
1637 lhs,
1638 pattern,
1639 op,
1640 not,
1641 });
1642 self.controls.push(ParseControl::ExprStart {
1643 min_bp: bp::EQUALITY.1,
1644 });
1645 return Ok(());
1646 }
1647 self.finish_like(outer_min_bp, lhs, pattern, None, op, not)
1648 }
1649 ParseControl::LikeEscapeDone {
1650 outer_min_bp,
1651 lhs,
1652 pattern,
1653 op,
1654 not,
1655 } => {
1656 let escape = self.pop_expr()?;
1657 self.finish_like(outer_min_bp, lhs, pattern, Some(escape), op, not)
1658 }
1659 ParseControl::BetweenLowDone {
1660 outer_min_bp,
1661 lhs,
1662 not,
1663 } => {
1664 let low = self.pop_expr()?;
1665 if !self.parser.eat_kind(&TokenKind::KwAnd) {
1666 return Err(self.parser.err_here("expected AND in BETWEEN expression"));
1667 }
1668 self.controls.push(ParseControl::BetweenHighDone {
1669 outer_min_bp,
1670 lhs,
1671 low,
1672 not,
1673 });
1674 self.controls.push(ParseControl::ExprStart {
1675 min_bp: bp::EQUALITY.1,
1676 });
1677 Ok(())
1678 }
1679 ParseControl::BetweenHighDone {
1680 outer_min_bp,
1681 lhs,
1682 low,
1683 not,
1684 } => {
1685 let high = self.pop_expr()?;
1686 let span = lhs.expr.span().merge(high.expr.span());
1687 let height = lhs.height.max(low.height).max(high.height);
1688 let is_constant = lhs.is_constant && low.is_constant && high.is_constant;
1689 let has_function = lhs.has_function || low.has_function || high.has_function;
1690 let parsed = self.parser.checked_expr(
1691 Expr::Between {
1692 expr: Box::new(lhs.expr),
1693 low: Box::new(low.expr),
1694 high: Box::new(high.expr),
1695 not,
1696 span,
1697 },
1698 height,
1699 is_constant,
1700 has_function,
1701 )?;
1702 let parsed = if not {
1703 self.parser.add_cached_parent(parsed)?
1704 } else {
1705 parsed
1706 };
1707 self.push_expr_tail(parsed, outer_min_bp);
1708 Ok(())
1709 }
1710 ParseControl::InItemDone {
1711 outer_min_bp,
1712 lhs,
1713 not,
1714 mut items,
1715 start,
1716 } => {
1717 let item = self.pop_expr()?;
1718 items.push(item);
1719 if self.parser.eat_kind(&TokenKind::Comma) {
1720 self.controls.push(ParseControl::InItemDone {
1721 outer_min_bp,
1722 lhs,
1723 not,
1724 items,
1725 start,
1726 });
1727 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
1728 } else {
1729 let end = self.parser.expect_kind(&TokenKind::RightParen)?;
1730 self.finish_in_list(outer_min_bp, lhs, not, items, start.merge(end))?;
1731 }
1732 Ok(())
1733 }
1734 ParseControl::InSelectDone {
1735 outer_min_bp,
1736 lhs,
1737 not,
1738 start,
1739 } => {
1740 let select = self.pop_select()?;
1741 let end = self.parser.expect_kind(&TokenKind::RightParen)?;
1742 let height = lhs.height.max(select.height);
1743 let has_function = lhs.has_function;
1744 let parsed = self.parser.checked_expr(
1745 Expr::In {
1746 expr: Box::new(lhs.expr),
1747 set: InSet::Subquery(Box::new(select.value)),
1748 not,
1749 span: start.merge(end),
1750 },
1751 height,
1752 false,
1753 has_function,
1754 )?;
1755 let parsed = if not {
1756 self.parser.add_cached_parent(parsed)?
1757 } else {
1758 parsed
1759 };
1760 self.push_expr_tail(parsed, outer_min_bp);
1761 Ok(())
1762 }
1763 ParseControl::ExistsDone {
1764 outer_min_bp,
1765 not,
1766 start,
1767 } => {
1768 let select = self.pop_select()?;
1769 let end = self.parser.expect_kind(&TokenKind::RightParen)?;
1770 let parsed = self.parser.checked_expr(
1771 Expr::Exists {
1772 subquery: Box::new(select.value),
1773 not,
1774 span: start.merge(end),
1775 },
1776 select.height,
1777 false,
1778 false,
1779 )?;
1780 let parsed = if not {
1781 self.parser.add_cached_parent(parsed)?
1782 } else {
1783 parsed
1784 };
1785 self.push_expr_tail(parsed, outer_min_bp);
1786 Ok(())
1787 }
1788 ParseControl::ScalarSelectDone {
1789 outer_min_bp,
1790 start,
1791 } => {
1792 let select = self.pop_select()?;
1793 let end = self.parser.expect_kind(&TokenKind::RightParen)?;
1794 let parsed = self.parser.checked_expr(
1795 Expr::Subquery(Box::new(select.value), start.merge(end)),
1796 select.height,
1797 false,
1798 false,
1799 )?;
1800 self.push_expr_tail(parsed, outer_min_bp);
1801 Ok(())
1802 }
1803 ParseControl::OrderingStart => {
1804 self.controls.push(ParseControl::OrderingDone);
1805 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
1806 Ok(())
1807 }
1808 ParseControl::OrderingDone => {
1809 let expr = self.pop_expr()?;
1810 let direction = if self.parser.eat_kind(&TokenKind::KwAsc) {
1811 Some(SortDirection::Asc)
1812 } else if self.parser.eat_kind(&TokenKind::KwDesc) {
1813 Some(SortDirection::Desc)
1814 } else {
1815 None
1816 };
1817 let nulls = if self.parser.eat_kind(&TokenKind::KwNulls) {
1818 if self.parser.eat_kind(&TokenKind::KwFirst) {
1819 Some(NullsOrder::First)
1820 } else {
1821 self.parser.expect_kw(&TokenKind::KwLast)?;
1822 Some(NullsOrder::Last)
1823 }
1824 } else {
1825 None
1826 };
1827 self.values.push(MachineValue::Ordering(HeightTracked {
1828 height: expr.height,
1829 value: OrderingTerm {
1830 expr: expr.expr,
1831 direction,
1832 nulls,
1833 },
1834 }));
1835 Ok(())
1836 }
1837 ParseControl::WindowStart => self.window_start(),
1838 ParseControl::WindowPartitionDone { mut build } => {
1839 build.partition_by.push(self.pop_expr()?.expr);
1840 if self.parser.eat_kind(&TokenKind::Comma) {
1841 self.controls
1842 .push(ParseControl::WindowPartitionDone { build });
1843 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
1844 } else {
1845 self.controls.push(ParseControl::WindowOrderStart { build });
1846 }
1847 Ok(())
1848 }
1849 ParseControl::WindowOrderStart { build } => {
1850 if self.parser.eat_kind(&TokenKind::KwOrder) {
1851 self.parser.expect_kw(&TokenKind::KwBy)?;
1852 self.controls.push(ParseControl::WindowOrderDone { build });
1853 self.controls.push(ParseControl::OrderingStart);
1854 } else {
1855 self.controls.push(ParseControl::WindowFrameStart { build });
1856 }
1857 Ok(())
1858 }
1859 ParseControl::WindowOrderDone { mut build } => {
1860 build.order_by.push(self.pop_ordering()?.value);
1861 if self.parser.eat_kind(&TokenKind::Comma) {
1862 self.controls.push(ParseControl::WindowOrderDone { build });
1863 self.controls.push(ParseControl::OrderingStart);
1864 } else {
1865 self.controls.push(ParseControl::WindowFrameStart { build });
1866 }
1867 Ok(())
1868 }
1869 ParseControl::WindowFrameStart { build } => {
1870 self.window_frame_start(build);
1871 Ok(())
1872 }
1873 ParseControl::WindowFirstBoundDone {
1874 build,
1875 frame_type,
1876 between,
1877 } => {
1878 let start = self.pop_frame_bound()?;
1879 validate_frame_start(&start, between)?;
1880 if between {
1881 self.parser.expect_kw(&TokenKind::KwAnd)?;
1882 self.controls.push(ParseControl::WindowSecondBoundDone {
1883 build,
1884 frame_type,
1885 start,
1886 });
1887 self.controls.push(ParseControl::FrameBoundStart);
1888 } else {
1889 let frame = self.finish_frame(frame_type, start.value, None)?;
1890 self.values.push(MachineValue::Window(WindowSpec {
1891 window_ref: build.base_window.map(WindowReference::Base),
1892 partition_by: build.partition_by,
1893 order_by: build.order_by,
1894 frame: Some(frame),
1895 }));
1896 }
1897 Ok(())
1898 }
1899 ParseControl::WindowSecondBoundDone {
1900 build,
1901 frame_type,
1902 start,
1903 } => {
1904 let end = self.pop_frame_bound()?;
1905 validate_frame_end(&start, &end)?;
1906 let frame = self.finish_frame(frame_type, start.value, Some(end.value))?;
1907 self.values.push(MachineValue::Window(WindowSpec {
1908 window_ref: build.base_window.map(WindowReference::Base),
1909 partition_by: build.partition_by,
1910 order_by: build.order_by,
1911 frame: Some(frame),
1912 }));
1913 Ok(())
1914 }
1915 ParseControl::FrameBoundStart => self.frame_bound_start(),
1916 ParseControl::FrameBoundExprDone { origin } => {
1917 let expr = self.pop_expr()?.expr;
1918 let bound = if self.parser.eat_kind(&TokenKind::KwPreceding) {
1919 FrameBound::Preceding(Box::new(expr))
1920 } else {
1921 self.parser.expect_kw(&TokenKind::KwFollowing)?;
1922 FrameBound::Following(Box::new(expr))
1923 };
1924 self.values.push(MachineValue::FrameBound(ParsedFrameBound {
1925 value: bound,
1926 origin,
1927 }));
1928 Ok(())
1929 }
1930 ParseControl::SubqueryStart => {
1931 if self.parser.at_kind(&TokenKind::KwWith) {
1932 self.controls.push(ParseControl::SubqueryWithDone);
1933 self.controls.push(ParseControl::WithStart);
1934 } else {
1935 self.controls.push(ParseControl::SelectStart { with: None });
1936 }
1937 Ok(())
1938 }
1939 ParseControl::SubqueryWithDone => {
1940 let with = self.pop_with()?;
1941 self.controls
1942 .push(ParseControl::SelectStart { with: Some(with) });
1943 Ok(())
1944 }
1945 other => self.step_select(other),
1946 }
1947 }
1948
1949 #[allow(clippy::too_many_lines)]
1950 fn expr_start(&mut self, min_bp: u8) -> Result<(), ParseError> {
1951 let Token {
1952 kind,
1953 span: token_span,
1954 line,
1955 col,
1956 } = self.parser.advance_token();
1957 if self.parser.at_kind(&TokenKind::Dot) && starts_table_star_qualifier(&kind) {
1958 let name = match &kind {
1959 TokenKind::Id(name) | TokenKind::QuotedId(name, _) => Arc::clone(name),
1960 TokenKind::String(name) => Arc::<str>::from(name.as_str()),
1961 keyword => Arc::<str>::from(kw_to_str(keyword)),
1962 };
1963 return self.identifier_or_function(name, token_span, min_bp);
1964 }
1965 let parsed = match kind {
1966 TokenKind::Integer(value) => {
1967 ParsedExpr::leaf(Expr::Literal(Literal::Integer(value), token_span))
1968 }
1969 TokenKind::OversizedInt(value) => match value.parse::<f64>() {
1970 Ok(value) => ParsedExpr::leaf(Expr::Literal(Literal::Float(value), token_span)),
1971 Err(_) => {
1972 return Err(ParseError {
1973 kind: crate::parser::ParseErrorKind::Syntax,
1974 message: "integer out of range".to_owned(),
1975 span: token_span,
1976 line,
1977 col,
1978 });
1979 }
1980 },
1981 TokenKind::Float(value) => {
1982 ParsedExpr::leaf(Expr::Literal(Literal::Float(value), token_span))
1983 }
1984 TokenKind::String(value) if self.parser.at_kind(&TokenKind::Dot) => {
1985 return self.identifier_or_function(Arc::<str>::from(value), token_span, min_bp);
1986 }
1987 TokenKind::String(value) => {
1988 ParsedExpr::leaf(Expr::Literal(Literal::String(value), token_span))
1989 }
1990 TokenKind::Blob(value) => {
1991 ParsedExpr::leaf(Expr::Literal(Literal::Blob(value), token_span))
1992 }
1993 TokenKind::KwNull => ParsedExpr::leaf(Expr::Literal(Literal::Null, token_span)),
1994 TokenKind::KwTrue => ParsedExpr::leaf(Expr::Literal(Literal::True, token_span)),
1995 TokenKind::KwFalse => ParsedExpr::leaf(Expr::Literal(Literal::False, token_span)),
1996 TokenKind::KwCurrentTime => {
1997 ParsedExpr::leaf(Expr::Literal(Literal::CurrentTime, token_span))
1998 }
1999 TokenKind::KwCurrentDate => {
2000 ParsedExpr::leaf(Expr::Literal(Literal::CurrentDate, token_span))
2001 }
2002 TokenKind::KwCurrentTimestamp => {
2003 ParsedExpr::leaf(Expr::Literal(Literal::CurrentTimestamp, token_span))
2004 }
2005 TokenKind::Question => {
2006 ParsedExpr::leaf(Expr::Placeholder(PlaceholderType::Anonymous, token_span))
2007 }
2008 TokenKind::QuestionNum(value) => ParsedExpr::leaf(Expr::Placeholder(
2009 PlaceholderType::Numbered(value),
2010 token_span,
2011 )),
2012 TokenKind::ColonParam(value) => ParsedExpr::leaf(Expr::Placeholder(
2013 PlaceholderType::ColonNamed(value),
2014 token_span,
2015 )),
2016 TokenKind::AtParam(value) => ParsedExpr::leaf(Expr::Placeholder(
2017 PlaceholderType::AtNamed(value),
2018 token_span,
2019 )),
2020 TokenKind::DollarParam(value) => ParsedExpr::leaf(Expr::Placeholder(
2021 PlaceholderType::DollarNamed(value),
2022 token_span,
2023 )),
2024 TokenKind::Minus => {
2025 if let TokenKind::OversizedInt(value) = self.parser.peek_kind()
2026 && value == "9223372036854775808"
2027 {
2028 let number_span = self.parser.advance_token().span;
2029 let parsed = self.parser.finish_expr(
2030 Expr::Literal(Literal::Integer(i64::MIN), token_span.merge(number_span)),
2031 1,
2032 true,
2033 false,
2034 )?;
2035 self.push_expr_tail(parsed, min_bp);
2036 return Ok(());
2037 }
2038 self.controls.push(ParseControl::UnaryDone {
2039 outer_min_bp: min_bp,
2040 op: UnaryOp::Negate,
2041 span: token_span,
2042 });
2043 self.controls
2044 .push(ParseControl::ExprStart { min_bp: bp::UNARY });
2045 return Ok(());
2046 }
2047 TokenKind::Plus => {
2048 self.controls.push(ParseControl::UnaryDone {
2049 outer_min_bp: min_bp,
2050 op: UnaryOp::Plus,
2051 span: token_span,
2052 });
2053 self.controls
2054 .push(ParseControl::ExprStart { min_bp: bp::UNARY });
2055 return Ok(());
2056 }
2057 TokenKind::Tilde => {
2058 self.controls.push(ParseControl::UnaryDone {
2059 outer_min_bp: min_bp,
2060 op: UnaryOp::BitNot,
2061 span: token_span,
2062 });
2063 self.controls
2064 .push(ParseControl::ExprStart { min_bp: bp::UNARY });
2065 return Ok(());
2066 }
2067 TokenKind::KwNot => {
2068 if self.parser.eat_kind(&TokenKind::KwExists) {
2069 self.parser.expect_kind(&TokenKind::LeftParen)?;
2070 self.controls.push(ParseControl::ExistsDone {
2071 outer_min_bp: min_bp,
2072 not: true,
2073 start: token_span,
2074 });
2075 self.controls.push(ParseControl::SubqueryStart);
2076 } else {
2077 self.controls.push(ParseControl::UnaryDone {
2078 outer_min_bp: min_bp,
2079 op: UnaryOp::Not,
2080 span: token_span,
2081 });
2082 self.controls.push(ParseControl::ExprStart {
2083 min_bp: bp::NOT_PREFIX,
2084 });
2085 }
2086 return Ok(());
2087 }
2088 TokenKind::KwExists => {
2089 self.parser.expect_kind(&TokenKind::LeftParen)?;
2090 self.controls.push(ParseControl::ExistsDone {
2091 outer_min_bp: min_bp,
2092 not: false,
2093 start: token_span,
2094 });
2095 self.controls.push(ParseControl::SubqueryStart);
2096 return Ok(());
2097 }
2098 TokenKind::KwCast => {
2099 self.parser.expect_kind(&TokenKind::LeftParen)?;
2100 self.controls.push(ParseControl::CastDone {
2101 outer_min_bp: min_bp,
2102 start: token_span,
2103 });
2104 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
2105 return Ok(());
2106 }
2107 TokenKind::KwCase => {
2108 if self.parser.at_kind(&TokenKind::KwWhen) {
2109 self.controls.push(ParseControl::CaseWhenStart {
2110 outer_min_bp: min_bp,
2111 build: CaseBuild {
2112 start: token_span,
2113 operand: None,
2114 whens: Vec::new(),
2115 },
2116 });
2117 } else {
2118 self.controls.push(ParseControl::CaseOperandDone {
2119 outer_min_bp: min_bp,
2120 start: token_span,
2121 });
2122 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
2123 }
2124 return Ok(());
2125 }
2126 TokenKind::KwRaise => {
2127 self.parser.expect_kind(&TokenKind::LeftParen)?;
2128 let (action, message) = self.parser.parse_raise_args()?;
2129 let end = self.parser.expect_kind(&TokenKind::RightParen)?;
2130 ParsedExpr::leaf(Expr::Raise {
2131 action,
2132 message,
2133 span: token_span.merge(end),
2134 })
2135 }
2136 TokenKind::LeftParen => {
2137 if matches!(
2138 self.parser.peek_kind(),
2139 TokenKind::KwSelect | TokenKind::KwWith | TokenKind::KwValues
2140 ) {
2141 self.controls.push(ParseControl::ScalarSelectDone {
2142 outer_min_bp: min_bp,
2143 start: token_span,
2144 });
2145 self.controls.push(ParseControl::SubqueryStart);
2146 } else {
2147 self.controls.push(ParseControl::GroupFirstDone {
2148 outer_min_bp: min_bp,
2149 start: token_span,
2150 });
2151 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
2152 }
2153 return Ok(());
2154 }
2155 TokenKind::Id(name) | TokenKind::QuotedId(name, _) => {
2156 return self.identifier_or_function(name, token_span, min_bp);
2157 }
2158 TokenKind::KwReplace if self.parser.at_kind(&TokenKind::LeftParen) => {
2159 return self.start_function("replace".to_owned(), token_span, min_bp);
2160 }
2161 TokenKind::KwLike if self.parser.at_kind(&TokenKind::LeftParen) => {
2162 return self.start_function("like".to_owned(), token_span, min_bp);
2163 }
2164 TokenKind::KwGlob if self.parser.at_kind(&TokenKind::LeftParen) => {
2165 return self.start_function("glob".to_owned(), token_span, min_bp);
2166 }
2167 TokenKind::KwRegexp if self.parser.at_kind(&TokenKind::LeftParen) => {
2168 return self.start_function("regexp".to_owned(), token_span, min_bp);
2169 }
2170 TokenKind::KwMatch if self.parser.at_kind(&TokenKind::LeftParen) => {
2171 return self.start_function("match".to_owned(), token_span, min_bp);
2172 }
2173 kind if is_nonreserved_kw(&kind) => {
2174 let name = Arc::<str>::from(kw_to_str(&kind));
2175 return self.identifier_or_function(name, token_span, min_bp);
2176 }
2177 kind => {
2178 return Err(ParseError {
2179 kind: crate::parser::ParseErrorKind::Syntax,
2180 message: format!("unexpected token in expression: {kind:?}"),
2181 span: token_span,
2182 line,
2183 col,
2184 });
2185 }
2186 };
2187 self.push_expr_tail(parsed, min_bp);
2188 Ok(())
2189 }
2190
2191 fn identifier_or_function(
2192 &mut self,
2193 name: Arc<str>,
2194 start: Span,
2195 min_bp: u8,
2196 ) -> Result<(), ParseError> {
2197 if self.parser.at_kind(&TokenKind::LeftParen) {
2198 return self.start_function(name.to_string(), start, min_bp);
2199 }
2200 let parsed = if self.parser.at_kind(&TokenKind::Dot) {
2201 let Some(column_token) = self.parser.tokens.get(self.parser.pos + 1).cloned() else {
2202 return Err(self.parser.err_here("expected column name after '.'"));
2203 };
2204 let column = match &column_token.kind {
2205 TokenKind::Id(column) | TokenKind::QuotedId(column, _) => Arc::clone(column),
2206 TokenKind::String(column) => Arc::<str>::from(column.as_str()),
2207 kind if starts_post_dot_identifier(kind) => Arc::<str>::from(kw_to_str(kind)),
2208 _ => {
2209 return Err(ParseError::at(
2210 format!(
2211 "expected column name after '.', got {:?}",
2212 column_token.kind
2213 ),
2214 Some(&column_token),
2215 ));
2216 }
2217 };
2218 self.parser.pos = self.parser.pos.saturating_add(2);
2219 self.parser.finish_expr(
2220 Expr::Column(
2221 ColumnRef::qualified(name, column),
2222 start.merge(column_token.span),
2223 ),
2224 2,
2225 false,
2226 false,
2227 )?
2228 } else {
2229 ParsedExpr::leaf(Expr::Column(ColumnRef::bare(name), start))
2230 };
2231 self.push_expr_tail(parsed, min_bp);
2232 Ok(())
2233 }
2234
2235 fn start_function(
2236 &mut self,
2237 name: String,
2238 start: Span,
2239 outer_min_bp: u8,
2240 ) -> Result<(), ParseError> {
2241 self.parser.expect_kind(&TokenKind::LeftParen)?;
2242 let mut build = FunctionBuild {
2243 name,
2244 start,
2245 args: FunctionArgs::List(Vec::new()),
2246 distinct: false,
2247 height: 0,
2248 order_by: Vec::new(),
2249 filter: None,
2250 over: None,
2251 end: start,
2252 };
2253 if self.parser.eat_kind(&TokenKind::Star) {
2254 if !build.name.eq_ignore_ascii_case("count") {
2255 return Err(self
2256 .parser
2257 .err_here("'*' can only be used with count() function"));
2258 }
2259 build.args = FunctionArgs::Star;
2260 self.controls.push(ParseControl::FunctionClose {
2261 outer_min_bp,
2262 build,
2263 });
2264 } else {
2265 build.distinct = self.parser.eat_kind(&TokenKind::KwDistinct);
2266 if self.parser.at_kind(&TokenKind::RightParen) {
2267 if build.distinct {
2268 return Err(self
2269 .parser
2270 .err_here("DISTINCT requires at least one argument"));
2271 }
2272 self.controls.push(ParseControl::FunctionOrderStart {
2273 outer_min_bp,
2274 build,
2275 });
2276 } else {
2277 self.controls.push(ParseControl::FunctionArgDone {
2278 outer_min_bp,
2279 build,
2280 });
2281 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
2282 }
2283 }
2284 Ok(())
2285 }
2286
2287 #[allow(clippy::too_many_lines)]
2288 fn expr_tail(&mut self, min_bp: u8) -> Result<(), ParseError> {
2289 let lhs = self.pop_expr()?;
2290 if let Some(left_bp) = self.parser.postfix_bp()
2291 && left_bp >= min_bp
2292 {
2293 let parsed = self.parser.parse_postfix(lhs)?;
2294 self.push_expr_tail(parsed, min_bp);
2295 return Ok(());
2296 }
2297 let Some((left_bp, right_bp)) = self.parser.infix_bp() else {
2298 self.values.push(MachineValue::Expr(lhs));
2299 return Ok(());
2300 };
2301 if left_bp < min_bp {
2302 self.values.push(MachineValue::Expr(lhs));
2303 return Ok(());
2304 }
2305
2306 let token = self.parser.advance_token();
2307 let simple = match &token.kind {
2308 TokenKind::Plus => Some(BinaryOp::Add),
2309 TokenKind::Minus => Some(BinaryOp::Subtract),
2310 TokenKind::Star => Some(BinaryOp::Multiply),
2311 TokenKind::Slash => Some(BinaryOp::Divide),
2312 TokenKind::Percent => Some(BinaryOp::Modulo),
2313 TokenKind::Concat => Some(BinaryOp::Concat),
2314 TokenKind::Eq | TokenKind::EqEq => Some(BinaryOp::Eq),
2315 TokenKind::Ne | TokenKind::LtGt => Some(BinaryOp::Ne),
2316 TokenKind::Lt => Some(BinaryOp::Lt),
2317 TokenKind::Le => Some(BinaryOp::Le),
2318 TokenKind::Gt => Some(BinaryOp::Gt),
2319 TokenKind::Ge => Some(BinaryOp::Ge),
2320 TokenKind::Ampersand => Some(BinaryOp::BitAnd),
2321 TokenKind::Pipe => Some(BinaryOp::BitOr),
2322 TokenKind::ShiftLeft => Some(BinaryOp::ShiftLeft),
2323 TokenKind::ShiftRight => Some(BinaryOp::ShiftRight),
2324 TokenKind::KwOr => Some(BinaryOp::Or),
2325 TokenKind::KwAnd => Some(BinaryOp::And),
2326 _ => None,
2327 };
2328 if let Some(op) = simple {
2329 self.controls.push(ParseControl::BinaryDone {
2330 outer_min_bp: min_bp,
2331 lhs,
2332 op,
2333 });
2334 self.controls
2335 .push(ParseControl::ExprStart { min_bp: right_bp });
2336 return Ok(());
2337 }
2338 match &token.kind {
2339 TokenKind::KwIs => {
2340 let not = self.parser.eat_kind(&TokenKind::KwNot);
2341 if self.parser.eat_kind(&TokenKind::KwDistinct) {
2342 self.parser.expect_kind(&TokenKind::KwFrom)?;
2343 self.controls.push(ParseControl::BinaryDone {
2344 outer_min_bp: min_bp,
2345 lhs,
2346 op: if not { BinaryOp::Is } else { BinaryOp::IsNot },
2347 });
2348 } else {
2349 self.controls.push(ParseControl::IsDone {
2350 outer_min_bp: min_bp,
2351 lhs,
2352 not,
2353 });
2354 }
2355 self.controls
2356 .push(ParseControl::ExprStart { min_bp: right_bp });
2357 }
2358 TokenKind::KwLike | TokenKind::KwGlob | TokenKind::KwMatch | TokenKind::KwRegexp => {
2359 let op = match &token.kind {
2360 TokenKind::KwLike => LikeOp::Like,
2361 TokenKind::KwGlob => LikeOp::Glob,
2362 TokenKind::KwMatch => LikeOp::Match,
2363 TokenKind::KwRegexp => LikeOp::Regexp,
2364 _ => unreachable!(),
2365 };
2366 self.controls.push(ParseControl::LikePatternDone {
2367 outer_min_bp: min_bp,
2368 lhs,
2369 op,
2370 not: false,
2371 });
2372 self.controls.push(ParseControl::ExprStart {
2373 min_bp: bp::EQUALITY.1,
2374 });
2375 }
2376 TokenKind::KwBetween => {
2377 self.controls.push(ParseControl::BetweenLowDone {
2378 outer_min_bp: min_bp,
2379 lhs,
2380 not: false,
2381 });
2382 self.controls.push(ParseControl::ExprStart {
2383 min_bp: bp::NOT_PREFIX,
2384 });
2385 }
2386 TokenKind::KwIn => self.start_in(lhs, false, min_bp)?,
2387 TokenKind::Arrow => {
2388 self.controls.push(ParseControl::JsonDone {
2389 outer_min_bp: min_bp,
2390 lhs,
2391 arrow: JsonArrow::Arrow,
2392 });
2393 self.controls
2394 .push(ParseControl::ExprStart { min_bp: right_bp });
2395 }
2396 TokenKind::DoubleArrow => {
2397 self.controls.push(ParseControl::JsonDone {
2398 outer_min_bp: min_bp,
2399 lhs,
2400 arrow: JsonArrow::DoubleArrow,
2401 });
2402 self.controls
2403 .push(ParseControl::ExprStart { min_bp: right_bp });
2404 }
2405 TokenKind::KwNot => {
2406 let next = self.parser.advance_token();
2407 match &next.kind {
2408 TokenKind::KwLike
2409 | TokenKind::KwGlob
2410 | TokenKind::KwMatch
2411 | TokenKind::KwRegexp => {
2412 let op = match &next.kind {
2413 TokenKind::KwLike => LikeOp::Like,
2414 TokenKind::KwGlob => LikeOp::Glob,
2415 TokenKind::KwMatch => LikeOp::Match,
2416 TokenKind::KwRegexp => LikeOp::Regexp,
2417 _ => unreachable!(),
2418 };
2419 self.controls.push(ParseControl::LikePatternDone {
2420 outer_min_bp: min_bp,
2421 lhs,
2422 op,
2423 not: true,
2424 });
2425 self.controls.push(ParseControl::ExprStart {
2426 min_bp: bp::EQUALITY.1,
2427 });
2428 }
2429 TokenKind::KwBetween => {
2430 self.controls.push(ParseControl::BetweenLowDone {
2431 outer_min_bp: min_bp,
2432 lhs,
2433 not: true,
2434 });
2435 self.controls.push(ParseControl::ExprStart {
2436 min_bp: bp::NOT_PREFIX,
2437 });
2438 }
2439 TokenKind::KwIn => self.start_in(lhs, true, min_bp)?,
2440 _ => {
2441 return Err(ParseError::at(
2442 format!(
2443 "expected LIKE/GLOB/MATCH/REGEXP/BETWEEN/IN after NOT, got {:?}",
2444 next.kind
2445 ),
2446 Some(&next),
2447 ));
2448 }
2449 }
2450 }
2451 other => {
2452 return Err(ParseError::at(
2453 format!("unexpected infix token: {other:?}"),
2454 Some(&token),
2455 ));
2456 }
2457 }
2458 Ok(())
2459 }
2460
2461 fn start_in(&mut self, lhs: ParsedExpr, not: bool, outer_min_bp: u8) -> Result<(), ParseError> {
2462 let start = lhs.expr.span();
2463 if !self.parser.eat_kind(&TokenKind::LeftParen) {
2464 let table = self.parser.parse_qualified_name()?;
2465 let end = self.parser.tokens[self.parser.pos.saturating_sub(1)].span;
2466 let height = lhs.height;
2467 let has_function = lhs.has_function;
2468 let parsed = self.parser.checked_expr(
2469 Expr::In {
2470 expr: Box::new(lhs.expr),
2471 set: InSet::Table(table),
2472 not,
2473 span: start.merge(end),
2474 },
2475 height,
2476 false,
2477 has_function,
2478 )?;
2479 let parsed = if not {
2480 self.parser.add_cached_parent(parsed)?
2481 } else {
2482 parsed
2483 };
2484 self.push_expr_tail(parsed, outer_min_bp);
2485 } else if matches!(
2486 self.parser.peek_kind(),
2487 TokenKind::KwSelect | TokenKind::KwWith | TokenKind::KwValues
2488 ) {
2489 self.controls.push(ParseControl::InSelectDone {
2490 outer_min_bp,
2491 lhs,
2492 not,
2493 start,
2494 });
2495 self.controls.push(ParseControl::SubqueryStart);
2496 } else if self.parser.at_kind(&TokenKind::RightParen) {
2497 let end = self.parser.expect_kind(&TokenKind::RightParen)?;
2498 self.finish_in_list(outer_min_bp, lhs, not, Vec::new(), start.merge(end))?;
2499 } else {
2500 self.controls.push(ParseControl::InItemDone {
2501 outer_min_bp,
2502 lhs,
2503 not,
2504 items: Vec::new(),
2505 start,
2506 });
2507 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
2508 }
2509 Ok(())
2510 }
2511
2512 fn finish_case(
2513 &mut self,
2514 outer_min_bp: u8,
2515 build: CaseBuild,
2516 else_expr: Option<ParsedExpr>,
2517 ) -> Result<(), ParseError> {
2518 if !self.parser.eat_kind(&TokenKind::KwEnd) {
2519 return Err(self.parser.err_here("expected END for CASE expression"));
2520 }
2521 let end = self.parser.tokens[self.parser.pos.saturating_sub(1)].span;
2522 let mut height = build.operand.as_ref().map_or(0, |expr| expr.height);
2523 let mut is_constant = build.operand.as_ref().is_none_or(|expr| expr.is_constant);
2524 let mut has_function = build.operand.as_ref().is_some_and(|expr| expr.has_function);
2525 for (condition, result) in &build.whens {
2526 height = height.max(condition.height).max(result.height);
2527 is_constant &= condition.is_constant && result.is_constant;
2528 has_function |= condition.has_function || result.has_function;
2529 }
2530 if let Some(expr) = &else_expr {
2531 height = height.max(expr.height);
2532 is_constant &= expr.is_constant;
2533 has_function |= expr.has_function;
2534 }
2535 let parsed = self.parser.checked_expr(
2536 Expr::Case {
2537 operand: build.operand.map(|expr| Box::new(expr.expr)),
2538 whens: build
2539 .whens
2540 .into_iter()
2541 .map(|(condition, result)| (condition.expr, result.expr))
2542 .collect(),
2543 else_expr: else_expr.map(|expr| Box::new(expr.expr)),
2544 span: build.start.merge(end),
2545 },
2546 height,
2547 is_constant,
2548 has_function,
2549 )?;
2550 self.push_expr_tail(parsed, outer_min_bp);
2551 Ok(())
2552 }
2553
2554 fn finish_like(
2555 &mut self,
2556 outer_min_bp: u8,
2557 lhs: ParsedExpr,
2558 pattern: ParsedExpr,
2559 escape: Option<ParsedExpr>,
2560 op: LikeOp,
2561 not: bool,
2562 ) -> Result<(), ParseError> {
2563 let end = escape
2564 .as_ref()
2565 .map_or_else(|| pattern.expr.span(), |expr| expr.expr.span());
2566 let height = escape.as_ref().map_or_else(
2567 || lhs.height.max(pattern.height),
2568 |expr| lhs.height.max(pattern.height).max(expr.height),
2569 );
2570 let span = lhs.expr.span().merge(end);
2571 let parsed = self.parser.checked_expr(
2572 Expr::Like {
2573 expr: Box::new(lhs.expr),
2574 pattern: Box::new(pattern.expr),
2575 escape: escape.map(|expr| Box::new(expr.expr)),
2576 op,
2577 not,
2578 span,
2579 },
2580 height,
2581 false,
2582 true,
2583 )?;
2584 let parsed = if not {
2585 self.parser.add_cached_parent(parsed)?
2586 } else {
2587 parsed
2588 };
2589 self.push_expr_tail(parsed, outer_min_bp);
2590 Ok(())
2591 }
2592
2593 fn finish_in_list(
2594 &mut self,
2595 outer_min_bp: u8,
2596 lhs: ParsedExpr,
2597 not: bool,
2598 items: Vec<ParsedExpr>,
2599 span: Span,
2600 ) -> Result<(), ParseError> {
2601 if let Some(message) = vector_in_list_arity_error(&lhs.expr, &items) {
2602 return Err(self.parser.err_here(message));
2603 }
2604 let item_height = items.iter().map(|item| item.height).max().unwrap_or(0);
2605 let items_are_constant = items.iter().all(|item| item.is_constant);
2606 let item_has_function = items.iter().any(|item| item.has_function);
2607 let singleton_constant = matches!(items.as_slice(), [item] if item.is_constant)
2608 && lhs.root != CachedRoot::Vector;
2609 let singleton_subquery =
2610 matches!(items.as_slice(), [item] if item.root == CachedRoot::ScalarSubquery);
2611 let lhs_height = lhs.height;
2612 let lhs_is_constant = lhs.is_constant;
2613 let lhs_has_function = lhs.has_function;
2614 let expr = Expr::In {
2615 expr: Box::new(lhs.expr),
2616 set: InSet::List(items.into_iter().map(|item| item.expr).collect()),
2617 not,
2618 span,
2619 };
2620 let parsed = if item_height == 0 {
2621 if lhs_has_function {
2622 self.parser
2623 .finish_expr(expr, lhs_height.saturating_add(1), false, true)?
2624 } else {
2625 self.parser.finish_expr(expr, 1, true, false)?
2626 }
2627 } else {
2628 let cached_child_height = if singleton_constant {
2629 lhs_height.max(item_height.saturating_add(1))
2630 } else if singleton_subquery {
2631 lhs_height.max(item_height.saturating_sub(1))
2632 } else {
2633 lhs_height.max(item_height)
2634 };
2635 let parsed = self.parser.checked_expr(
2636 expr,
2637 cached_child_height,
2638 lhs_is_constant && items_are_constant,
2639 lhs_has_function || item_has_function,
2640 )?;
2641 if not {
2642 self.parser.add_cached_parent(parsed)?
2643 } else {
2644 parsed
2645 }
2646 };
2647 self.push_expr_tail(parsed, outer_min_bp);
2648 Ok(())
2649 }
2650
2651 fn window_start(&mut self) -> Result<(), ParseError> {
2652 let has_base_window = starts_window_base_name(self.parser.peek_kind());
2653 let build = WindowBuild {
2654 base_window: if has_base_window {
2655 Some(self.parser.parse_window_name()?)
2656 } else {
2657 None
2658 },
2659 partition_by: Vec::new(),
2660 order_by: Vec::new(),
2661 };
2662 if self.parser.eat_kind(&TokenKind::KwPartition) {
2663 self.parser.expect_kw(&TokenKind::KwBy)?;
2664 self.controls
2665 .push(ParseControl::WindowPartitionDone { build });
2666 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
2667 } else {
2668 self.controls.push(ParseControl::WindowOrderStart { build });
2669 }
2670 Ok(())
2671 }
2672
2673 fn window_frame_start(&mut self, build: WindowBuild) {
2674 let frame_type = if self.parser.eat_kind(&TokenKind::KwRows) {
2675 Some(FrameType::Rows)
2676 } else if self.parser.eat_kind(&TokenKind::KwRange) {
2677 Some(FrameType::Range)
2678 } else if self.parser.eat_kind(&TokenKind::KwGroups) {
2679 Some(FrameType::Groups)
2680 } else {
2681 None
2682 };
2683 let Some(frame_type) = frame_type else {
2684 self.values.push(MachineValue::Window(WindowSpec {
2685 window_ref: build.base_window.map(WindowReference::Base),
2686 partition_by: build.partition_by,
2687 order_by: build.order_by,
2688 frame: None,
2689 }));
2690 return;
2691 };
2692 let between = self.parser.eat_kind(&TokenKind::KwBetween);
2693 self.controls.push(ParseControl::WindowFirstBoundDone {
2694 build,
2695 frame_type,
2696 between,
2697 });
2698 self.controls.push(ParseControl::FrameBoundStart);
2699 }
2700
2701 fn frame_bound_start(&mut self) -> Result<(), ParseError> {
2702 let origin = self
2703 .parser
2704 .peek_token()
2705 .cloned()
2706 .ok_or_else(|| self.parser.err_here("expected window frame bound"))?;
2707 if self.parser.eat_kind(&TokenKind::KwUnbounded) {
2708 let bound = if self.parser.eat_kind(&TokenKind::KwPreceding) {
2709 FrameBound::UnboundedPreceding
2710 } else {
2711 self.parser.expect_kw(&TokenKind::KwFollowing)?;
2712 FrameBound::UnboundedFollowing
2713 };
2714 self.values.push(MachineValue::FrameBound(ParsedFrameBound {
2715 value: bound,
2716 origin,
2717 }));
2718 } else if matches!(
2719 self.parser.peek_kind(),
2720 TokenKind::Id(value) if value.eq_ignore_ascii_case("CURRENT")
2721 ) {
2722 self.parser.advance_token();
2723 self.parser.expect_kw(&TokenKind::KwRow)?;
2724 self.values.push(MachineValue::FrameBound(ParsedFrameBound {
2725 value: FrameBound::CurrentRow,
2726 origin,
2727 }));
2728 } else {
2729 self.controls
2730 .push(ParseControl::FrameBoundExprDone { origin });
2731 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
2732 }
2733 Ok(())
2734 }
2735
2736 fn finish_frame(
2737 &mut self,
2738 frame_type: FrameType,
2739 start: FrameBound,
2740 end: Option<FrameBound>,
2741 ) -> Result<FrameSpec, ParseError> {
2742 let exclude = if self.parser.eat_kind(&TokenKind::KwExclude) {
2743 if self.parser.eat_kind(&TokenKind::KwNo) {
2744 let others = self.parser.parse_identifier()?;
2745 if !others.eq_ignore_ascii_case("OTHERS") {
2746 return Err(self.parser.err_here("expected OTHERS"));
2747 }
2748 Some(FrameExclude::NoOthers)
2749 } else if self.parser.eat_kind(&TokenKind::KwTies) {
2750 Some(FrameExclude::Ties)
2751 } else if self.parser.eat_kind(&TokenKind::KwGroup) {
2752 Some(FrameExclude::Group)
2753 } else if matches!(
2754 self.parser.peek_kind(),
2755 TokenKind::Id(value) if value.eq_ignore_ascii_case("CURRENT")
2756 ) {
2757 self.parser.advance_token();
2758 self.parser.expect_kw(&TokenKind::KwRow)?;
2759 Some(FrameExclude::CurrentRow)
2760 } else {
2761 return Err(self
2762 .parser
2763 .err_here("expected NO OTHERS, TIES, GROUP, or CURRENT ROW after EXCLUDE"));
2764 }
2765 } else {
2766 None
2767 };
2768 Ok(FrameSpec {
2769 frame_type,
2770 start,
2771 end,
2772 exclude,
2773 })
2774 }
2775
2776 fn step_select(&mut self, control: ParseControl) -> Result<(), ParseError> {
2777 match control {
2778 ParseControl::SelectStart { with } => {
2779 self.controls
2780 .push(ParseControl::SelectFirstCoreDone { with });
2781 self.controls.push(ParseControl::CoreStart);
2782 Ok(())
2783 }
2784 ParseControl::SelectFirstCoreDone { with } => {
2785 let core = self.pop_core()?;
2786 self.continue_select_body(SelectBuild {
2787 with,
2788 height: core.height,
2789 first: core.value,
2790 compounds: Vec::new(),
2791 order_by: Vec::new(),
2792 });
2793 Ok(())
2794 }
2795 ParseControl::SelectCompoundDone { mut build, op } => {
2796 let core = self.pop_core()?;
2797 build.height = build.height.max(core.height);
2798 build.compounds.push((op, core.value));
2799 self.continue_select_body(build);
2800 Ok(())
2801 }
2802 ParseControl::SelectOrderStart { build } => {
2803 let final_core = build
2804 .compounds
2805 .last()
2806 .map_or(&build.first, |(_, core)| core);
2807 if matches!(final_core, SelectCore::Values(_))
2808 && matches!(
2809 self.parser.peek_kind(),
2810 TokenKind::KwOrder | TokenKind::KwLimit
2811 )
2812 {
2813 return Err(self
2814 .parser
2815 .err_here("ORDER BY / LIMIT clause is not allowed after a VALUES term"));
2816 }
2817 if self.parser.eat_kind(&TokenKind::KwOrder) {
2818 self.parser.expect_kw(&TokenKind::KwBy)?;
2819 self.controls.push(ParseControl::SelectOrderDone { build });
2820 self.controls.push(ParseControl::OrderingStart);
2821 } else {
2822 self.start_select_limit(build)?;
2823 }
2824 Ok(())
2825 }
2826 ParseControl::SelectOrderDone { mut build } => {
2827 let term = self.pop_ordering()?;
2828 build.height = build.height.max(term.height);
2829 build.order_by.push(term.value);
2830 if self.parser.eat_kind(&TokenKind::Comma) {
2831 self.controls.push(ParseControl::SelectOrderDone { build });
2832 self.controls.push(ParseControl::OrderingStart);
2833 } else {
2834 self.start_select_limit(build)?;
2835 }
2836 Ok(())
2837 }
2838 ParseControl::SelectLimitFirstDone { build } => {
2839 let first = self.pop_expr()?;
2840 if self.parser.eat_kind(&TokenKind::KwOffset) {
2841 self.controls.push(ParseControl::SelectLimitSecondDone {
2842 build,
2843 first,
2844 comma_form: false,
2845 });
2846 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
2847 } else if self.parser.eat_kind(&TokenKind::Comma) {
2848 self.controls.push(ParseControl::SelectLimitSecondDone {
2849 build,
2850 first,
2851 comma_form: true,
2852 });
2853 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
2854 } else {
2855 let height = self.parser.checked_cached_parent_height(first.height)?;
2856 self.finish_select(
2857 build,
2858 HeightTracked {
2859 value: Some(LimitClause {
2860 limit: first.expr,
2861 offset: None,
2862 }),
2863 height,
2864 },
2865 )?;
2866 }
2867 Ok(())
2868 }
2869 ParseControl::SelectLimitSecondDone {
2870 build,
2871 first,
2872 comma_form,
2873 } => {
2874 let second = self.pop_expr()?;
2875 let height = self
2876 .parser
2877 .checked_cached_parent_height(first.height.max(second.height))?;
2878 let limit = if comma_form {
2879 LimitClause {
2880 limit: second.expr,
2881 offset: Some(first.expr),
2882 }
2883 } else {
2884 LimitClause {
2885 limit: first.expr,
2886 offset: Some(second.expr),
2887 }
2888 };
2889 self.finish_select(
2890 build,
2891 HeightTracked {
2892 value: Some(limit),
2893 height,
2894 },
2895 )
2896 }
2897 ParseControl::CoreStart => self.core_start(),
2898 ParseControl::CoreColumnStart { build } => self.core_column_start(build),
2899 ParseControl::CoreColumnDone { mut build } => {
2900 let expr = self.pop_expr()?;
2901 build.height = build.height.max(expr.height);
2902 build.columns.push(ResultColumn::Expr {
2903 expr: expr.expr,
2904 alias: self.parser.try_result_alias()?,
2905 });
2906 if self.parser.eat_kind(&TokenKind::Comma) {
2907 self.controls.push(ParseControl::CoreColumnStart { build });
2908 } else {
2909 self.controls.push(ParseControl::CoreAfterColumns { build });
2910 }
2911 Ok(())
2912 }
2913 ParseControl::CoreAfterColumns { build } => {
2914 if self.parser.eat_kind(&TokenKind::KwFrom) {
2915 self.controls.push(ParseControl::CoreFromDone { build });
2916 self.controls.push(ParseControl::FromStart);
2917 } else {
2918 self.continue_core_where(build)?;
2919 }
2920 Ok(())
2921 }
2922 ParseControl::CoreFromDone { mut build } => {
2923 build.from = Some(self.pop_from()?);
2924 self.continue_core_where(build)
2925 }
2926 ParseControl::CoreWhereDone { mut build } => {
2927 let expr = self.pop_expr()?;
2928 build.height = build.height.max(expr.height);
2929 build.where_clause = Some(Box::new(expr.expr));
2930 self.continue_core_group(build)
2931 }
2932 ParseControl::CoreGroupDone { mut build } => {
2933 let expr = self.pop_expr()?;
2934 build.height = build.height.max(expr.height);
2935 build.group_by.push(expr.expr);
2936 if self.parser.eat_kind(&TokenKind::Comma) {
2937 self.controls.push(ParseControl::CoreGroupDone { build });
2938 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
2939 } else {
2940 self.continue_core_having(build);
2941 }
2942 Ok(())
2943 }
2944 ParseControl::CoreHavingDone { mut build } => {
2945 let expr = self.pop_expr()?;
2946 build.height = build.height.max(expr.height);
2947 build.having = Some(Box::new(expr.expr));
2948 self.continue_core_windows(build);
2949 Ok(())
2950 }
2951 ParseControl::CoreWindowStart { build } => {
2952 let name = self.parser.parse_window_name()?;
2953 self.parser.expect_kw(&TokenKind::KwAs)?;
2954 self.parser.expect_token(&TokenKind::LeftParen)?;
2955 self.controls
2956 .push(ParseControl::CoreWindowDone { build, name });
2957 self.controls.push(ParseControl::WindowStart);
2958 Ok(())
2959 }
2960 ParseControl::CoreWindowDone { mut build, name } => {
2961 let spec = self.pop_window()?;
2962 self.parser.expect_token(&TokenKind::RightParen)?;
2963 build.windows.push(WindowDef { name, spec });
2964 if self.parser.eat_kind(&TokenKind::Comma) {
2965 self.controls.push(ParseControl::CoreWindowStart { build });
2966 } else {
2967 self.finish_core(build);
2968 }
2969 Ok(())
2970 }
2971 ParseControl::ValuesRowStart {
2972 rows,
2973 height,
2974 force_union_all_from,
2975 } => {
2976 self.parser.expect_token(&TokenKind::LeftParen)?;
2977 self.controls.push(ParseControl::ValuesItemDone {
2978 rows,
2979 row: Vec::new(),
2980 height,
2981 force_union_all_from,
2982 });
2983 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
2984 Ok(())
2985 }
2986 ParseControl::ValuesItemDone {
2987 mut rows,
2988 mut row,
2989 mut height,
2990 mut force_union_all_from,
2991 } => {
2992 let expr = self.pop_expr()?;
2993 height = height.max(expr.height);
2994 row.push(expr.expr);
2995 if self.parser.eat_kind(&TokenKind::Comma) {
2996 self.controls.push(ParseControl::ValuesItemDone {
2997 rows,
2998 row,
2999 height,
3000 force_union_all_from,
3001 });
3002 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
3003 } else {
3004 self.parser.expect_token(&TokenKind::RightParen)?;
3005 if force_union_all_from.is_none() && self.parser.has_with {
3006 force_union_all_from = Some(rows.len());
3007 }
3008 rows.push(row);
3009 if self.parser.eat_kind(&TokenKind::Comma) {
3010 self.controls.push(ParseControl::ValuesRowStart {
3011 rows,
3012 height,
3013 force_union_all_from,
3014 });
3015 } else {
3016 self.values.push(MachineValue::Core(HeightTracked {
3017 value: SelectCore::Values(ValuesClause::parsed(
3018 rows,
3019 force_union_all_from,
3020 )),
3021 height,
3022 }));
3023 }
3024 }
3025 Ok(())
3026 }
3027 ParseControl::FromStart => {
3028 self.controls.push(ParseControl::FromSourceDone);
3029 self.controls.push(ParseControl::TableStart);
3030 Ok(())
3031 }
3032 ParseControl::FromSourceDone => {
3033 let source = self.pop_table()?;
3034 self.continue_from(FromBuild {
3035 source,
3036 joins: Vec::new(),
3037 })
3038 }
3039 ParseControl::FromTableDone { build, join_type } => {
3040 let table = self.pop_table()?;
3041 if self.parser.eat_kind(&TokenKind::KwOn) {
3042 self.controls.push(ParseControl::FromJoinConstraintDone {
3043 build,
3044 join_type,
3045 table,
3046 });
3047 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
3048 return Ok(());
3049 }
3050 let constraint = if self.parser.eat_kind(&TokenKind::KwUsing) {
3051 self.parser.expect_token(&TokenKind::LeftParen)?;
3052 let mut columns = vec![self.parser.parse_identifier()?];
3053 while self.parser.eat_kind(&TokenKind::Comma) {
3054 columns.push(self.parser.parse_identifier()?);
3055 }
3056 self.parser.expect_token(&TokenKind::RightParen)?;
3057 Some(JoinConstraint::Using(columns))
3058 } else {
3059 None
3060 };
3061 self.append_join(build, join_type, table, constraint)
3062 }
3063 ParseControl::FromJoinConstraintDone {
3064 build,
3065 join_type,
3066 table,
3067 } => {
3068 let expr = self.pop_expr()?;
3069 self.append_join(build, join_type, table, Some(JoinConstraint::On(expr.expr)))
3070 }
3071 ParseControl::TableStart => self.table_start(),
3072 ParseControl::TableSubqueryDone => {
3073 let select = self.pop_select()?;
3074 self.parser.expect_token(&TokenKind::RightParen)?;
3075 self.values
3076 .push(MachineValue::Table(TableOrSubquery::Subquery {
3077 query: Box::new(select.value),
3078 alias: self.parser.try_table_alias()?,
3079 }));
3080 Ok(())
3081 }
3082 ParseControl::TableParenJoinDone => {
3083 let from = self.pop_from()?;
3084 self.parser.expect_token(&TokenKind::RightParen)?;
3085 self.values
3086 .push(MachineValue::Table(TableOrSubquery::ParenJoin(Box::new(
3087 from,
3088 ))));
3089 Ok(())
3090 }
3091 ParseControl::TableFunctionArgDone { name, mut args } => {
3092 args.push(self.pop_expr()?.expr);
3093 if self.parser.eat_kind(&TokenKind::Comma) {
3094 self.controls
3095 .push(ParseControl::TableFunctionArgDone { name, args });
3096 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
3097 } else {
3098 self.parser.expect_token(&TokenKind::RightParen)?;
3099 self.values
3100 .push(MachineValue::Table(TableOrSubquery::TableFunction {
3101 name,
3102 args,
3103 alias: self.parser.try_table_alias()?,
3104 }));
3105 }
3106 Ok(())
3107 }
3108 ParseControl::WithStart => self.with_start(),
3109 ParseControl::CteQueryDone {
3110 recursive,
3111 mut ctes,
3112 name,
3113 columns,
3114 materialized,
3115 } => {
3116 let query = self.pop_select()?;
3117 self.parser.expect_token(&TokenKind::RightParen)?;
3118 ctes.push(Cte {
3119 name,
3120 columns,
3121 materialized,
3122 query: query.value,
3123 });
3124 if self.parser.eat_kind(&TokenKind::Comma) {
3125 self.start_cte(recursive, ctes)?;
3126 } else {
3127 self.values
3128 .push(MachineValue::With(WithClause { recursive, ctes }));
3129 }
3130 Ok(())
3131 }
3132 _ => Err(self
3133 .parser
3134 .err_here("internal expression parser control reached SELECT dispatcher")),
3135 }
3136 }
3137
3138 fn continue_select_body(&mut self, build: SelectBuild) {
3139 let op = if self.parser.eat_kind(&TokenKind::KwUnion) {
3140 Some(if self.parser.eat_kind(&TokenKind::KwAll) {
3141 CompoundOp::UnionAll
3142 } else {
3143 CompoundOp::Union
3144 })
3145 } else if self.parser.eat_kind(&TokenKind::KwIntersect) {
3146 Some(CompoundOp::Intersect)
3147 } else if self.parser.eat_kind(&TokenKind::KwExcept) {
3148 Some(CompoundOp::Except)
3149 } else {
3150 None
3151 };
3152 if let Some(op) = op {
3153 self.controls
3154 .push(ParseControl::SelectCompoundDone { build, op });
3155 self.controls.push(ParseControl::CoreStart);
3156 } else {
3157 self.controls.push(ParseControl::SelectOrderStart { build });
3158 }
3159 }
3160
3161 fn start_select_limit(&mut self, build: SelectBuild) -> Result<(), ParseError> {
3162 if self.parser.eat_kind(&TokenKind::KwLimit) {
3163 self.controls
3164 .push(ParseControl::SelectLimitFirstDone { build });
3165 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
3166 } else {
3167 self.finish_select(
3168 build,
3169 HeightTracked {
3170 value: None,
3171 height: 0,
3172 },
3173 )?;
3174 }
3175 Ok(())
3176 }
3177
3178 fn finish_select(
3179 &mut self,
3180 mut build: SelectBuild,
3181 limit: HeightTracked<Option<LimitClause>>,
3182 ) -> Result<(), ParseError> {
3183 build.height = build.height.max(limit.height);
3184 let final_core = build
3185 .compounds
3186 .last()
3187 .map_or(&build.first, |(_, core)| core);
3188 if matches!(final_core, SelectCore::Values(_))
3189 && (!build.order_by.is_empty() || limit.value.is_some())
3190 {
3191 return Err(self
3192 .parser
3193 .err_here("ORDER BY / LIMIT clause is not allowed after a VALUES term"));
3194 }
3195 self.values.push(MachineValue::Select(HeightTracked {
3196 value: SelectStatement {
3197 with: build.with,
3198 body: SelectBody {
3199 select: build.first,
3200 compounds: build.compounds,
3201 },
3202 order_by: build.order_by,
3203 limit: limit.value,
3204 },
3205 height: build.height,
3206 }));
3207 Ok(())
3208 }
3209
3210 fn core_start(&mut self) -> Result<(), ParseError> {
3211 if self.parser.eat_kind(&TokenKind::KwValues) {
3212 self.controls.push(ParseControl::ValuesRowStart {
3213 rows: Vec::new(),
3214 height: 0,
3215 force_union_all_from: None,
3216 });
3217 return Ok(());
3218 }
3219 self.parser.expect_kw(&TokenKind::KwSelect)?;
3220 let distinct = if self.parser.eat_kind(&TokenKind::KwDistinct) {
3221 Distinctness::Distinct
3222 } else {
3223 let _ = self.parser.eat_kind(&TokenKind::KwAll);
3224 Distinctness::All
3225 };
3226 self.controls.push(ParseControl::CoreColumnStart {
3227 build: CoreBuild {
3228 distinct,
3229 columns: Vec::new(),
3230 height: 0,
3231 from: None,
3232 where_clause: None,
3233 group_by: Vec::new(),
3234 having: None,
3235 windows: Vec::new(),
3236 },
3237 });
3238 Ok(())
3239 }
3240
3241 fn core_column_start(&mut self, mut build: CoreBuild) -> Result<(), ParseError> {
3242 if self.parser.eat_kind(&TokenKind::Star) {
3243 build.columns.push(ResultColumn::Star);
3244 if self.parser.eat_kind(&TokenKind::Comma) {
3245 self.controls.push(ParseControl::CoreColumnStart { build });
3246 } else {
3247 self.controls.push(ParseControl::CoreAfterColumns { build });
3248 }
3249 return Ok(());
3250 }
3251 if starts_table_star_qualifier(self.parser.peek_kind())
3252 && self
3253 .parser
3254 .tokens
3255 .get(self.parser.pos + 1)
3256 .is_some_and(|token| token.kind == TokenKind::Dot)
3257 {
3258 let table_star = self
3259 .parser
3260 .tokens
3261 .get(self.parser.pos + 2)
3262 .is_some_and(|token| token.kind == TokenKind::Star);
3263 let schema_table_star = self
3264 .parser
3265 .tokens
3266 .get(self.parser.pos + 2)
3267 .is_some_and(|token| starts_table_star_qualifier(&token.kind))
3268 && self
3269 .parser
3270 .tokens
3271 .get(self.parser.pos + 3)
3272 .is_some_and(|token| token.kind == TokenKind::Dot)
3273 && self
3274 .parser
3275 .tokens
3276 .get(self.parser.pos + 4)
3277 .is_some_and(|token| token.kind == TokenKind::Star);
3278 if table_star || schema_table_star {
3279 let first = self.parser.parse_table_star_qualifier()?;
3280 self.parser.expect_token(&TokenKind::Dot)?;
3281 let name = if schema_table_star {
3282 let second = self.parser.parse_table_star_qualifier()?;
3283 self.parser.expect_token(&TokenKind::Dot)?;
3284 QualifiedName::qualified(first, second)
3285 } else {
3286 QualifiedName::bare(first)
3287 };
3288 self.parser.expect_token(&TokenKind::Star)?;
3289 build.columns.push(ResultColumn::TableStar(name));
3290 if self.parser.eat_kind(&TokenKind::Comma) {
3291 self.controls.push(ParseControl::CoreColumnStart { build });
3292 } else {
3293 self.controls.push(ParseControl::CoreAfterColumns { build });
3294 }
3295 return Ok(());
3296 }
3297 }
3298 self.controls.push(ParseControl::CoreColumnDone { build });
3299 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
3300 Ok(())
3301 }
3302
3303 fn continue_core_where(&mut self, build: CoreBuild) -> Result<(), ParseError> {
3304 if self.parser.eat_kind(&TokenKind::KwWhere) {
3305 self.controls.push(ParseControl::CoreWhereDone { build });
3306 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
3307 } else {
3308 self.continue_core_group(build)?;
3309 }
3310 Ok(())
3311 }
3312
3313 fn continue_core_group(&mut self, build: CoreBuild) -> Result<(), ParseError> {
3314 if self.parser.eat_kind(&TokenKind::KwGroup) {
3315 self.parser.expect_kw(&TokenKind::KwBy)?;
3316 self.controls.push(ParseControl::CoreGroupDone { build });
3317 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
3318 } else {
3319 self.continue_core_having(build);
3320 }
3321 Ok(())
3322 }
3323
3324 fn continue_core_having(&mut self, build: CoreBuild) {
3325 if self.parser.eat_kind(&TokenKind::KwHaving) {
3326 self.controls.push(ParseControl::CoreHavingDone { build });
3327 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
3328 } else {
3329 self.continue_core_windows(build);
3330 }
3331 }
3332
3333 fn continue_core_windows(&mut self, build: CoreBuild) {
3334 if self.parser.eat_kind(&TokenKind::KwWindow) {
3335 self.controls.push(ParseControl::CoreWindowStart { build });
3336 } else {
3337 self.finish_core(build);
3338 }
3339 }
3340
3341 fn finish_core(&mut self, build: CoreBuild) {
3342 self.values.push(MachineValue::Core(HeightTracked {
3343 value: SelectCore::Select {
3344 distinct: build.distinct,
3345 columns: build.columns,
3346 from: build.from,
3347 where_clause: build.where_clause,
3348 group_by: build.group_by,
3349 having: build.having,
3350 windows: build.windows,
3351 },
3352 height: build.height,
3353 }));
3354 }
3355
3356 fn continue_from(&mut self, build: FromBuild) -> Result<(), ParseError> {
3357 let join_type = if let Some(join_type) = self.parser.try_join_type()? {
3358 Some(join_type)
3359 } else if self.parser.eat_kind(&TokenKind::Comma) {
3360 Some(JoinType {
3361 natural: false,
3362 kind: JoinKind::Cross,
3363 })
3364 } else {
3365 None
3366 };
3367 if let Some(join_type) = join_type {
3368 self.controls
3369 .push(ParseControl::FromTableDone { build, join_type });
3370 self.controls.push(ParseControl::TableStart);
3371 } else {
3372 self.values.push(MachineValue::From(FromClause {
3373 source: build.source,
3374 joins: build.joins,
3375 }));
3376 }
3377 Ok(())
3378 }
3379
3380 fn append_join(
3381 &mut self,
3382 mut build: FromBuild,
3383 join_type: JoinType,
3384 table: TableOrSubquery,
3385 constraint: Option<JoinConstraint>,
3386 ) -> Result<(), ParseError> {
3387 if join_type.natural && constraint.is_some() {
3388 return Err(self
3389 .parser
3390 .err_here("a NATURAL join may not have an ON or USING clause"));
3391 }
3392 build.joins.push(JoinClause {
3393 join_type,
3394 table,
3395 constraint,
3396 });
3397 self.continue_from(build)
3398 }
3399
3400 fn table_start(&mut self) -> Result<(), ParseError> {
3401 if self.parser.eat_kind(&TokenKind::LeftParen) {
3402 if matches!(
3403 self.parser.peek_kind(),
3404 TokenKind::KwSelect | TokenKind::KwWith | TokenKind::KwValues
3405 ) {
3406 self.controls.push(ParseControl::TableSubqueryDone);
3407 self.controls.push(ParseControl::SubqueryStart);
3408 } else {
3409 self.controls.push(ParseControl::TableParenJoinDone);
3410 self.controls.push(ParseControl::FromStart);
3411 }
3412 return Ok(());
3413 }
3414 let name = self.parser.parse_qualified_name()?;
3415 if name.schema.is_none() && self.parser.eat_kind(&TokenKind::LeftParen) {
3416 if self.parser.eat_kind(&TokenKind::RightParen) {
3417 self.values
3418 .push(MachineValue::Table(TableOrSubquery::TableFunction {
3419 name: name.name,
3420 args: Vec::new(),
3421 alias: self.parser.try_table_alias()?,
3422 }));
3423 } else {
3424 self.controls.push(ParseControl::TableFunctionArgDone {
3425 name: name.name,
3426 args: Vec::new(),
3427 });
3428 self.controls.push(ParseControl::ExprStart { min_bp: 0 });
3429 }
3430 return Ok(());
3431 }
3432 self.values
3433 .push(MachineValue::Table(TableOrSubquery::Table {
3434 name,
3435 alias: self.parser.try_table_alias()?,
3436 index_hint: self.parser.parse_index_hint()?,
3437 time_travel: self.parser.parse_time_travel_clause()?,
3438 }));
3439 Ok(())
3440 }
3441
3442 fn with_start(&mut self) -> Result<(), ParseError> {
3443 self.parser.expect_kw(&TokenKind::KwWith)?;
3444 self.parser.has_with = true;
3445 let recursive = self.parser.eat_kind(&TokenKind::KwRecursive);
3446 self.start_cte(recursive, Vec::new())
3447 }
3448
3449 fn start_cte(&mut self, recursive: bool, ctes: Vec<Cte>) -> Result<(), ParseError> {
3450 let name = self.parser.parse_identifier()?;
3451 let columns = if self.parser.eat_kind(&TokenKind::LeftParen) {
3452 let mut columns = vec![self.parser.parse_identifier()?];
3453 while self.parser.eat_kind(&TokenKind::Comma) {
3454 columns.push(self.parser.parse_identifier()?);
3455 }
3456 self.parser.expect_token(&TokenKind::RightParen)?;
3457 columns
3458 } else {
3459 Vec::new()
3460 };
3461 self.parser.expect_kw(&TokenKind::KwAs)?;
3462 let materialized = if self.parser.eat_kind(&TokenKind::KwNot) {
3463 self.parser.expect_kw(&TokenKind::KwMaterialized)?;
3464 Some(CteMaterialized::NotMaterialized)
3465 } else if self.parser.eat_kind(&TokenKind::KwMaterialized) {
3466 Some(CteMaterialized::Materialized)
3467 } else {
3468 None
3469 };
3470 self.parser.expect_token(&TokenKind::LeftParen)?;
3471 self.controls.push(ParseControl::CteQueryDone {
3472 recursive,
3473 ctes,
3474 name,
3475 columns,
3476 materialized,
3477 });
3478 self.controls.push(ParseControl::SubqueryStart);
3479 Ok(())
3480 }
3481}
3482
3483impl Parser {
3484 pub fn parse_expr(&mut self) -> Result<Expr, ParseError> {
3486 self.parse_expr_tracked().map(|parsed| parsed.expr)
3487 }
3488
3489 pub(crate) fn parse_expr_tracked(&mut self) -> Result<ParsedExpr, ParseError> {
3490 ParseMachine::for_expr(self).run_expr()
3491 }
3492
3493 pub(crate) fn parse_select_tracked_machine(
3494 &mut self,
3495 with: Option<WithClause>,
3496 ) -> Result<HeightTracked<SelectStatement>, ParseError> {
3497 ParseMachine::for_select(self, with).run_select()
3498 }
3499
3500 pub(crate) fn parse_with_clause_machine(&mut self) -> Result<WithClause, ParseError> {
3501 ParseMachine::for_with(self).run_with()
3502 }
3503
3504 pub(crate) fn parse_from_clause_machine(&mut self) -> Result<FromClause, ParseError> {
3505 ParseMachine::for_from(self).run_from()
3506 }
3507
3508 fn finish_expr(
3509 &self,
3510 expr: Expr,
3511 height: u32,
3512 is_constant: bool,
3513 has_function: bool,
3514 ) -> Result<ParsedExpr, ParseError> {
3515 if height > MAX_PARSE_DEPTH {
3516 return Err(ParseError::expression_too_deep(
3517 MAX_PARSE_DEPTH,
3518 self.peek_token(),
3519 ));
3520 }
3521 let root = match &expr {
3522 Expr::UnaryOp {
3523 op: UnaryOp::Plus, ..
3524 } => CachedRoot::UnaryPlus,
3525 Expr::RowValue(..) => CachedRoot::Vector,
3526 Expr::Subquery(..) => CachedRoot::ScalarSubquery,
3527 _ => CachedRoot::Other,
3528 };
3529 Ok(ParsedExpr {
3530 expr,
3531 height,
3532 is_constant,
3533 has_function,
3534 root,
3535 })
3536 }
3537
3538 fn checked_expr(
3539 &self,
3540 expr: Expr,
3541 max_child_height: u32,
3542 is_constant: bool,
3543 has_function: bool,
3544 ) -> Result<ParsedExpr, ParseError> {
3545 let height = max_child_height.saturating_add(1);
3546 self.finish_expr(expr, height, is_constant, has_function)
3547 }
3548
3549 fn add_cached_parent(&self, mut parsed: ParsedExpr) -> Result<ParsedExpr, ParseError> {
3550 parsed.height = parsed.height.saturating_add(1);
3551 if parsed.height > MAX_PARSE_DEPTH {
3552 return Err(ParseError::expression_too_deep(
3553 MAX_PARSE_DEPTH,
3554 self.peek_token(),
3555 ));
3556 }
3557 parsed.root = CachedRoot::Other;
3558 Ok(parsed)
3559 }
3560
3561 fn finish_unary(
3562 &self,
3563 op: UnaryOp,
3564 mut inner: ParsedExpr,
3565 span: Span,
3566 ) -> Result<ParsedExpr, ParseError> {
3567 if matches!(op, UnaryOp::Plus | UnaryOp::Negate)
3568 && inner.root == CachedRoot::UnaryPlus
3569 && let Expr::UnaryOp {
3570 op: inner_op,
3571 span: inner_span,
3572 ..
3573 } = &mut inner.expr
3574 {
3575 *inner_op = op;
3576 *inner_span = span;
3577 inner.root = if op == UnaryOp::Plus {
3578 CachedRoot::UnaryPlus
3579 } else {
3580 CachedRoot::Other
3581 };
3582 return Ok(inner);
3583 }
3584
3585 let height = inner.height;
3586 let is_constant = inner.is_constant;
3587 let has_function = inner.has_function;
3588 self.checked_expr(
3589 Expr::UnaryOp {
3590 op,
3591 expr: Box::new(inner.expr),
3592 span,
3593 },
3594 height,
3595 is_constant,
3596 has_function,
3597 )
3598 }
3599
3600 #[cfg(test)]
3603 fn parse_expr_bp(&mut self, min_bp: u8) -> Result<ParsedExpr, ParseError> {
3604 self.with_recursion_guard(|p| p.parse_expr_bp_inner(min_bp))
3605 }
3606
3607 #[cfg(test)]
3608 fn parse_expr_bp_inner(&mut self, min_bp: u8) -> Result<ParsedExpr, ParseError> {
3609 let prefixes = self.collect_prefix_frames();
3610 let mut lhs = self.parse_prefix()?;
3611
3612 for prefix in prefixes.into_iter().rev() {
3613 match prefix {
3614 DeepExprFrame::Unary { op, span, right_bp } => {
3615 lhs = self.parse_expr_tail(lhs, right_bp)?;
3616 let span = span.merge(lhs.expr.span());
3617 lhs = self.finish_unary(op, lhs, span)?;
3618 }
3619 DeepExprFrame::Parenthesis { span } => {
3620 lhs = self.finish_parenthesized_frame(lhs, span)?;
3621 }
3622 }
3623 }
3624
3625 self.parse_expr_tail(lhs, min_bp)
3626 }
3627
3628 #[cfg(test)]
3629 fn parse_expr_tail(
3630 &mut self,
3631 mut lhs: ParsedExpr,
3632 min_bp: u8,
3633 ) -> Result<ParsedExpr, ParseError> {
3634 loop {
3635 if let Some(l_bp) = self.postfix_bp() {
3637 if l_bp < min_bp {
3638 break;
3639 }
3640 lhs = self.parse_postfix(lhs)?;
3641 continue;
3642 }
3643
3644 if let Some((l_bp, r_bp)) = self.infix_bp() {
3646 if l_bp < min_bp {
3647 break;
3648 }
3649 lhs = self.parse_infix(lhs, r_bp)?;
3650 continue;
3651 }
3652
3653 break;
3654 }
3655
3656 Ok(lhs)
3657 }
3658
3659 #[cfg(test)]
3660 fn collect_prefix_frames(&mut self) -> Vec<DeepExprFrame> {
3661 let mut prefixes = Vec::new();
3662 loop {
3663 let unary = match self.peek_kind() {
3664 TokenKind::Minus => {
3665 let folds_i64_min = matches!(
3666 self.tokens.get(self.pos + 1).map(|token| &token.kind),
3667 Some(TokenKind::OversizedInt(value)) if value == "9223372036854775808"
3668 );
3669 if folds_i64_min {
3670 break;
3671 }
3672 Some((UnaryOp::Negate, bp::UNARY))
3673 }
3674 TokenKind::Plus => Some((UnaryOp::Plus, bp::UNARY)),
3675 TokenKind::Tilde => Some((UnaryOp::BitNot, bp::UNARY)),
3676 TokenKind::KwNot => {
3677 if matches!(
3678 self.tokens.get(self.pos + 1).map(|token| &token.kind),
3679 Some(TokenKind::KwExists)
3680 ) {
3681 break;
3682 }
3683 Some((UnaryOp::Not, bp::NOT_PREFIX))
3684 }
3685 TokenKind::LeftParen => {
3686 let starts_subquery = matches!(
3687 self.tokens.get(self.pos + 1).map(|token| &token.kind),
3688 Some(TokenKind::KwSelect | TokenKind::KwWith | TokenKind::KwValues)
3689 );
3690 if starts_subquery {
3691 break;
3692 }
3693 let token = self.advance_token();
3694 prefixes.push(DeepExprFrame::Parenthesis { span: token.span });
3695 continue;
3696 }
3697 _ => break,
3698 };
3699 let Some((op, right_bp)) = unary else {
3700 break;
3701 };
3702 let token = self.advance_token();
3703 prefixes.push(DeepExprFrame::Unary {
3704 op,
3705 span: token.span,
3706 right_bp,
3707 });
3708 }
3709 prefixes
3710 }
3711
3712 #[cfg(test)]
3713 fn finish_parenthesized_frame(
3714 &mut self,
3715 mut first: ParsedExpr,
3716 start: Span,
3717 ) -> Result<ParsedExpr, ParseError> {
3718 first = self.parse_expr_tail(first, 0)?;
3719 if self.eat_kind(&TokenKind::Comma) {
3720 let mut is_constant = first.is_constant;
3721 let mut has_function = first.has_function;
3722 let mut exprs = vec![first.expr];
3723 loop {
3724 let parsed = self.parse_expr_bp(0)?;
3725 is_constant &= parsed.is_constant;
3726 has_function |= parsed.has_function;
3727 exprs.push(parsed.expr);
3728 if !self.eat_kind(&TokenKind::Comma) {
3729 break;
3730 }
3731 }
3732 let end = self.expect_kind(&TokenKind::RightParen)?;
3733 return self.finish_expr(
3734 Expr::RowValue(exprs, start.merge(end)),
3735 1,
3736 is_constant,
3737 has_function,
3738 );
3739 }
3740 self.expect_kind(&TokenKind::RightParen)?;
3741 Ok(first)
3742 }
3743
3744 fn peek_kind(&self) -> &TokenKind {
3747 self.tokens
3748 .get(self.pos)
3749 .map_or(&TokenKind::Eof, |t| &t.kind)
3750 }
3751
3752 fn peek_token(&self) -> Option<&Token> {
3753 self.tokens.get(self.pos)
3754 }
3755
3756 #[cfg(test)]
3757 fn peek_nth_token(&self, offset: usize) -> Option<&Token> {
3758 self.tokens.get(self.pos + offset)
3759 }
3760
3761 fn advance_token(&mut self) -> Token {
3762 let tok = self.tokens[self.pos].clone();
3763 if tok.kind != TokenKind::Eof {
3764 self.pos += 1;
3765 }
3766 tok
3767 }
3768
3769 fn at_kind(&self, kind: &TokenKind) -> bool {
3770 std::mem::discriminant(self.peek_kind()) == std::mem::discriminant(kind)
3771 }
3772
3773 fn eat_kind(&mut self, kind: &TokenKind) -> bool {
3774 if self.at_kind(kind) {
3775 self.advance_token();
3776 true
3777 } else {
3778 false
3779 }
3780 }
3781
3782 fn expect_kind(&mut self, expected: &TokenKind) -> Result<Span, ParseError> {
3783 if self.at_kind(expected) {
3784 Ok(self.advance_token().span)
3785 } else {
3786 Err(self.err_here(format!("expected {expected:?}, got {:?}", self.peek_kind())))
3787 }
3788 }
3789
3790 fn err_here(&self, message: impl Into<String>) -> ParseError {
3791 ParseError::at(message, self.peek_token())
3792 }
3793
3794 #[cfg(test)]
3797 #[allow(clippy::too_many_lines)]
3798 fn parse_prefix(&mut self) -> Result<ParsedExpr, ParseError> {
3799 let Token {
3800 kind,
3801 span: token_span,
3802 line,
3803 col,
3804 } = self.advance_token();
3805 if self.at_kind(&TokenKind::Dot) && starts_table_star_qualifier(&kind) {
3806 let name = match &kind {
3807 TokenKind::Id(name) | TokenKind::QuotedId(name, _) => Arc::clone(name),
3808 TokenKind::String(name) => Arc::<str>::from(name.as_str()),
3809 keyword => Arc::<str>::from(kw_to_str(keyword)),
3810 };
3811 return self.parse_ident_expr(name, token_span);
3812 }
3813 match kind {
3814 TokenKind::Integer(i) => Ok(ParsedExpr::leaf(Expr::Literal(
3816 Literal::Integer(i),
3817 token_span,
3818 ))),
3819 TokenKind::OversizedInt(s) => match s.parse::<f64>() {
3823 Ok(v) => Ok(ParsedExpr::leaf(Expr::Literal(
3824 Literal::Float(v),
3825 token_span,
3826 ))),
3827 Err(_) => Err(ParseError {
3828 kind: crate::parser::ParseErrorKind::Syntax,
3829 message: "integer out of range".to_owned(),
3830 span: token_span,
3831 line,
3832 col,
3833 }),
3834 },
3835 TokenKind::Float(f) => Ok(ParsedExpr::leaf(Expr::Literal(
3836 Literal::Float(f),
3837 token_span,
3838 ))),
3839 TokenKind::String(s) if matches!(self.peek_kind(), TokenKind::Dot) => {
3840 self.parse_ident_expr(s, token_span)
3841 }
3842 TokenKind::String(s) => Ok(ParsedExpr::leaf(Expr::Literal(
3843 Literal::String(s),
3844 token_span,
3845 ))),
3846 TokenKind::Blob(b) => Ok(ParsedExpr::leaf(Expr::Literal(
3847 Literal::Blob(b),
3848 token_span,
3849 ))),
3850 TokenKind::KwNull => Ok(ParsedExpr::leaf(Expr::Literal(Literal::Null, token_span))),
3851 TokenKind::KwTrue => Ok(ParsedExpr::leaf(Expr::Literal(Literal::True, token_span))),
3852 TokenKind::KwFalse => Ok(ParsedExpr::leaf(Expr::Literal(Literal::False, token_span))),
3853 TokenKind::KwCurrentTime => Ok(ParsedExpr::leaf(Expr::Literal(
3854 Literal::CurrentTime,
3855 token_span,
3856 ))),
3857 TokenKind::KwCurrentDate => Ok(ParsedExpr::leaf(Expr::Literal(
3858 Literal::CurrentDate,
3859 token_span,
3860 ))),
3861 TokenKind::KwCurrentTimestamp => Ok(ParsedExpr::leaf(Expr::Literal(
3862 Literal::CurrentTimestamp,
3863 token_span,
3864 ))),
3865
3866 TokenKind::Question => Ok(ParsedExpr::leaf(Expr::Placeholder(
3868 PlaceholderType::Anonymous,
3869 token_span,
3870 ))),
3871 TokenKind::QuestionNum(n) => Ok(ParsedExpr::leaf(Expr::Placeholder(
3872 PlaceholderType::Numbered(n),
3873 token_span,
3874 ))),
3875 TokenKind::ColonParam(s) => Ok(ParsedExpr::leaf(Expr::Placeholder(
3876 PlaceholderType::ColonNamed(s),
3877 token_span,
3878 ))),
3879 TokenKind::AtParam(s) => Ok(ParsedExpr::leaf(Expr::Placeholder(
3880 PlaceholderType::AtNamed(s),
3881 token_span,
3882 ))),
3883 TokenKind::DollarParam(s) => Ok(ParsedExpr::leaf(Expr::Placeholder(
3884 PlaceholderType::DollarNamed(s),
3885 token_span,
3886 ))),
3887
3888 TokenKind::Minus => {
3890 if let TokenKind::OversizedInt(s) = self.peek_kind()
3894 && s == "9223372036854775808"
3895 {
3896 let num_span = self.advance_token().span;
3897 let span = token_span.merge(num_span);
3898 return self.finish_expr(
3899 Expr::Literal(Literal::Integer(i64::MIN), span),
3900 1,
3901 true,
3902 false,
3903 );
3904 }
3905 let inner = self.parse_expr_bp(bp::UNARY)?;
3906 let span = token_span.merge(inner.expr.span());
3907 self.finish_unary(UnaryOp::Negate, inner, span)
3908 }
3909 TokenKind::Plus => {
3910 let inner = self.parse_expr_bp(bp::UNARY)?;
3911 let span = token_span.merge(inner.expr.span());
3912 self.finish_unary(UnaryOp::Plus, inner, span)
3913 }
3914 TokenKind::Tilde => {
3915 let inner = self.parse_expr_bp(bp::UNARY)?;
3916 let span = token_span.merge(inner.expr.span());
3917 self.finish_unary(UnaryOp::BitNot, inner, span)
3918 }
3919
3920 TokenKind::KwNot => {
3922 if matches!(self.peek_kind(), TokenKind::KwExists) {
3924 self.advance_token();
3925 self.expect_kind(&TokenKind::LeftParen)?;
3926 let subquery = self.parse_subquery_minimal()?;
3927 let end = self.expect_kind(&TokenKind::RightParen)?;
3928 let span = token_span.merge(end);
3929 let height = subquery.height;
3930 let exists = self.checked_expr(
3931 Expr::Exists {
3932 subquery: Box::new(subquery.value),
3933 not: true,
3934 span,
3935 },
3936 height,
3937 false,
3938 false,
3939 )?;
3940 return self.add_cached_parent(exists);
3941 }
3942 let inner = self.parse_expr_bp(bp::NOT_PREFIX)?;
3943 let span = token_span.merge(inner.expr.span());
3944 self.finish_unary(UnaryOp::Not, inner, span)
3945 }
3946
3947 TokenKind::KwExists => {
3949 self.expect_kind(&TokenKind::LeftParen)?;
3950 let subquery = self.parse_subquery_minimal()?;
3951 let end = self.expect_kind(&TokenKind::RightParen)?;
3952 let span = token_span.merge(end);
3953 let height = subquery.height;
3954 self.checked_expr(
3955 Expr::Exists {
3956 subquery: Box::new(subquery.value),
3957 not: false,
3958 span,
3959 },
3960 height,
3961 false,
3962 false,
3963 )
3964 }
3965
3966 TokenKind::KwCast => {
3968 self.expect_kind(&TokenKind::LeftParen)?;
3969 let inner = self.parse_expr_bp(0)?;
3970 self.expect_kind(&TokenKind::KwAs)?;
3971 let type_name = self.parse_type_name()?;
3972 let end = self.expect_kind(&TokenKind::RightParen)?;
3973 let span = token_span.merge(end);
3974 let height = inner.height;
3975 let is_constant = inner.is_constant;
3976 let has_function = inner.has_function;
3977 self.checked_expr(
3978 Expr::Cast {
3979 expr: Box::new(inner.expr),
3980 type_name,
3981 span,
3982 },
3983 height,
3984 is_constant,
3985 has_function,
3986 )
3987 }
3988
3989 TokenKind::KwCase => self.parse_case_expr(token_span),
3991
3992 TokenKind::KwRaise => {
3994 self.expect_kind(&TokenKind::LeftParen)?;
3995 let (action, message) = self.parse_raise_args()?;
3996 let end = self.expect_kind(&TokenKind::RightParen)?;
3997 let span = token_span.merge(end);
3998 Ok(ParsedExpr::leaf(Expr::Raise {
3999 action,
4000 message,
4001 span,
4002 }))
4003 }
4004
4005 TokenKind::LeftParen => {
4007 if matches!(
4008 self.peek_kind(),
4009 TokenKind::KwSelect | TokenKind::KwWith | TokenKind::KwValues
4010 ) {
4011 let subquery = self.parse_subquery_minimal()?;
4012 let end = self.expect_kind(&TokenKind::RightParen)?;
4013 let span = token_span.merge(end);
4014 return self.checked_expr(
4015 Expr::Subquery(Box::new(subquery.value), span),
4016 subquery.height,
4017 false,
4018 false,
4019 );
4020 }
4021 let first = self.parse_expr_bp(0)?;
4022 if self.eat_kind(&TokenKind::Comma) {
4023 let mut is_constant = first.is_constant;
4024 let mut has_function = first.has_function;
4025 let mut exprs = vec![first.expr];
4026 loop {
4027 let parsed = self.parse_expr_bp(0)?;
4028 is_constant &= parsed.is_constant;
4029 has_function |= parsed.has_function;
4030 exprs.push(parsed.expr);
4031 if !self.eat_kind(&TokenKind::Comma) {
4032 break;
4033 }
4034 }
4035 let end = self.expect_kind(&TokenKind::RightParen)?;
4036 let span = token_span.merge(end);
4037 self.finish_expr(Expr::RowValue(exprs, span), 1, is_constant, has_function)
4038 } else {
4039 self.expect_kind(&TokenKind::RightParen)?;
4040 Ok(first)
4041 }
4042 }
4043
4044 TokenKind::Id(name) | TokenKind::QuotedId(name, _) => {
4046 self.parse_ident_expr(name, token_span)
4047 }
4048
4049 TokenKind::KwReplace if matches!(self.peek_kind(), TokenKind::LeftParen) => {
4051 self.parse_function_call("replace".to_owned(), token_span)
4052 }
4053 TokenKind::KwLike if matches!(self.peek_kind(), TokenKind::LeftParen) => {
4059 self.parse_function_call("like".to_owned(), token_span)
4060 }
4061 TokenKind::KwGlob if matches!(self.peek_kind(), TokenKind::LeftParen) => {
4062 self.parse_function_call("glob".to_owned(), token_span)
4063 }
4064 TokenKind::KwRegexp if matches!(self.peek_kind(), TokenKind::LeftParen) => {
4065 self.parse_function_call("regexp".to_owned(), token_span)
4066 }
4067 TokenKind::KwMatch if matches!(self.peek_kind(), TokenKind::LeftParen) => {
4068 self.parse_function_call("match".to_owned(), token_span)
4069 }
4070
4071 k if is_nonreserved_kw(&k) => {
4075 let name = kw_to_str(&k);
4076 self.parse_ident_expr(name, token_span)
4077 }
4078
4079 kind => Err(ParseError {
4080 kind: crate::parser::ParseErrorKind::Syntax,
4081 message: format!("unexpected token in expression: {kind:?}"),
4082 span: token_span,
4083 line,
4084 col,
4085 }),
4086 }
4087 }
4088
4089 #[cfg(test)]
4091 fn parse_ident_expr<S>(&mut self, name: S, start: Span) -> Result<ParsedExpr, ParseError>
4092 where
4093 S: AsRef<str> + Into<Arc<str>>,
4094 {
4095 if matches!(self.peek_kind(), TokenKind::LeftParen) {
4097 return self.parse_function_call(name.as_ref().to_owned(), start);
4098 }
4099 let name = name.into();
4100 if matches!(self.peek_kind(), TokenKind::Dot) {
4102 let Some(col_tok) = self.peek_nth_token(1) else {
4103 return Err(self.err_here("expected column name after '.'"));
4104 };
4105 let col_name = match &col_tok.kind {
4106 TokenKind::Id(c) | TokenKind::QuotedId(c, _) => Arc::clone(c),
4107 TokenKind::String(c) => Arc::<str>::from(c.as_str()),
4108 k if starts_post_dot_identifier(k) => Arc::<str>::from(kw_to_str(k)),
4109 _ => {
4110 return Err(ParseError::at(
4111 format!("expected column name after '.', got {:?}", col_tok.kind),
4112 Some(col_tok),
4113 ));
4114 }
4115 };
4116 let span = start.merge(col_tok.span);
4117 self.pos = self.pos.saturating_add(2);
4118 return self.finish_expr(
4119 Expr::Column(ColumnRef::qualified(name, col_name), span),
4120 2,
4121 false,
4122 false,
4123 );
4124 }
4125 Ok(ParsedExpr::leaf(Expr::Column(ColumnRef::bare(name), start)))
4126 }
4127
4128 fn postfix_bp(&self) -> Option<u8> {
4131 match self.peek_kind() {
4132 TokenKind::KwCollate => Some(bp::COLLATE),
4133 TokenKind::KwIsnull | TokenKind::KwNotnull => Some(bp::EQUALITY.0),
4134 TokenKind::KwNot => {
4135 if let Some(next) = self.tokens.get(self.pos + 1)
4136 && matches!(next.kind, TokenKind::KwNull)
4137 {
4138 return Some(bp::EQUALITY.0);
4139 }
4140 None
4141 }
4142 _ => None,
4143 }
4144 }
4145
4146 fn parse_postfix(&mut self, lhs: ParsedExpr) -> Result<ParsedExpr, ParseError> {
4147 let tok = self.advance_token();
4148 match &tok.kind {
4149 TokenKind::KwCollate => {
4150 let collation = match self.parse_identifier() {
4151 Ok(s) => s,
4152 Err(_) => {
4153 return Err(self.err_here("expected collation name after COLLATE"));
4154 }
4155 };
4156 let name_span = self.tokens[self.pos.saturating_sub(1)].span;
4157 let span = lhs.expr.span().merge(name_span);
4158 let height = lhs.height;
4159 let is_constant = lhs.is_constant;
4160 let has_function = lhs.has_function;
4161 self.checked_expr(
4162 Expr::Collate {
4163 expr: Box::new(lhs.expr),
4164 collation,
4165 span,
4166 },
4167 height,
4168 is_constant,
4169 has_function,
4170 )
4171 }
4172 TokenKind::KwIsnull => {
4173 let span = lhs.expr.span().merge(tok.span);
4174 let height = lhs.height;
4175 let is_constant = lhs.is_constant;
4176 let has_function = lhs.has_function;
4177 self.checked_expr(
4178 Expr::IsNull {
4179 expr: Box::new(lhs.expr),
4180 not: false,
4181 span,
4182 },
4183 height,
4184 is_constant,
4185 has_function,
4186 )
4187 }
4188 TokenKind::KwNotnull => {
4189 let span = lhs.expr.span().merge(tok.span);
4190 let height = lhs.height;
4191 let is_constant = lhs.is_constant;
4192 let has_function = lhs.has_function;
4193 self.checked_expr(
4194 Expr::IsNull {
4195 expr: Box::new(lhs.expr),
4196 not: true,
4197 span,
4198 },
4199 height,
4200 is_constant,
4201 has_function,
4202 )
4203 }
4204 TokenKind::KwNot => {
4205 let null_tok = self.advance_token(); let span = lhs.expr.span().merge(null_tok.span);
4207 let height = lhs.height;
4208 let is_constant = lhs.is_constant;
4209 let has_function = lhs.has_function;
4210 self.checked_expr(
4211 Expr::IsNull {
4212 expr: Box::new(lhs.expr),
4213 not: true,
4214 span,
4215 },
4216 height,
4217 is_constant,
4218 has_function,
4219 )
4220 }
4221 other => Err(ParseError::at(
4222 format!("unexpected postfix token: {other:?}"),
4223 Some(&tok),
4224 )),
4225 }
4226 }
4227
4228 fn infix_bp(&self) -> Option<(u8, u8)> {
4231 match self.peek_kind() {
4232 TokenKind::KwOr => Some(bp::OR),
4233 TokenKind::KwAnd => Some(bp::AND),
4234
4235 TokenKind::Eq
4236 | TokenKind::EqEq
4237 | TokenKind::Ne
4238 | TokenKind::LtGt
4239 | TokenKind::KwIs
4240 | TokenKind::KwLike
4241 | TokenKind::KwGlob
4242 | TokenKind::KwMatch
4243 | TokenKind::KwRegexp
4244 | TokenKind::KwBetween
4245 | TokenKind::KwIn => Some(bp::EQUALITY),
4246
4247 TokenKind::KwNot => {
4249 let next = self.tokens.get(self.pos + 1).map(|t| &t.kind);
4250 match next {
4251 Some(
4252 TokenKind::KwLike
4253 | TokenKind::KwGlob
4254 | TokenKind::KwMatch
4255 | TokenKind::KwRegexp
4256 | TokenKind::KwBetween
4257 | TokenKind::KwIn,
4258 ) => Some(bp::EQUALITY),
4259 _ => None,
4260 }
4261 }
4262
4263 TokenKind::Lt | TokenKind::Le | TokenKind::Gt | TokenKind::Ge => Some(bp::COMPARISON),
4264
4265 TokenKind::Ampersand
4266 | TokenKind::Pipe
4267 | TokenKind::ShiftLeft
4268 | TokenKind::ShiftRight => Some(bp::BITWISE),
4269
4270 TokenKind::Plus | TokenKind::Minus => Some(bp::ADD),
4271 TokenKind::Star | TokenKind::Slash | TokenKind::Percent => Some(bp::MUL),
4272 TokenKind::Concat => Some(bp::CONCAT),
4273 TokenKind::Arrow | TokenKind::DoubleArrow => Some(bp::JSON),
4274
4275 _ => None,
4276 }
4277 }
4278
4279 #[cfg(test)]
4280 #[allow(clippy::too_many_lines)]
4281 fn parse_infix(&mut self, lhs: ParsedExpr, r_bp: u8) -> Result<ParsedExpr, ParseError> {
4282 let tok = self.advance_token();
4283 match &tok.kind {
4284 TokenKind::Plus => self.make_binop(lhs, BinaryOp::Add, r_bp),
4286 TokenKind::Minus => self.make_binop(lhs, BinaryOp::Subtract, r_bp),
4287 TokenKind::Star => self.make_binop(lhs, BinaryOp::Multiply, r_bp),
4288 TokenKind::Slash => self.make_binop(lhs, BinaryOp::Divide, r_bp),
4289 TokenKind::Percent => self.make_binop(lhs, BinaryOp::Modulo, r_bp),
4290 TokenKind::Concat => self.make_binop(lhs, BinaryOp::Concat, r_bp),
4291 TokenKind::Eq | TokenKind::EqEq => self.make_binop(lhs, BinaryOp::Eq, r_bp),
4292 TokenKind::Ne | TokenKind::LtGt => self.make_binop(lhs, BinaryOp::Ne, r_bp),
4293 TokenKind::Lt => self.make_binop(lhs, BinaryOp::Lt, r_bp),
4294 TokenKind::Le => self.make_binop(lhs, BinaryOp::Le, r_bp),
4295 TokenKind::Gt => self.make_binop(lhs, BinaryOp::Gt, r_bp),
4296 TokenKind::Ge => self.make_binop(lhs, BinaryOp::Ge, r_bp),
4297 TokenKind::Ampersand => self.make_binop(lhs, BinaryOp::BitAnd, r_bp),
4298 TokenKind::Pipe => self.make_binop(lhs, BinaryOp::BitOr, r_bp),
4299 TokenKind::ShiftLeft => self.make_binop(lhs, BinaryOp::ShiftLeft, r_bp),
4300 TokenKind::ShiftRight => self.make_binop(lhs, BinaryOp::ShiftRight, r_bp),
4301 TokenKind::KwOr => self.make_binop(lhs, BinaryOp::Or, r_bp),
4302 TokenKind::KwAnd => self.make_binop(lhs, BinaryOp::And, r_bp),
4303
4304 TokenKind::KwIs => {
4306 let not = self.eat_kind(&TokenKind::KwNot);
4307 if self.eat_kind(&TokenKind::KwDistinct) {
4308 self.expect_kind(&TokenKind::KwFrom)?;
4309 let rhs = self.parse_expr_bp(r_bp)?;
4310 let span = lhs.expr.span().merge(rhs.expr.span());
4311 let height = lhs.height.max(rhs.height);
4312 let is_constant = lhs.is_constant && rhs.is_constant;
4313 let has_function = lhs.has_function || rhs.has_function;
4314 let op = if not { BinaryOp::Is } else { BinaryOp::IsNot };
4317 return self.checked_expr(
4318 Expr::BinaryOp {
4319 left: Box::new(lhs.expr),
4320 op,
4321 right: Box::new(rhs.expr),
4322 span,
4323 },
4324 height,
4325 is_constant,
4326 has_function,
4327 );
4328 }
4329 let rhs = self.parse_expr_bp(r_bp)?;
4330 let span = lhs.expr.span().merge(rhs.expr.span());
4331 if matches!(&rhs.expr, Expr::Literal(Literal::Null, _)) {
4339 let height = lhs.height;
4340 let is_constant = lhs.is_constant;
4341 let has_function = lhs.has_function;
4342 return self.checked_expr(
4343 Expr::IsNull {
4344 expr: Box::new(lhs.expr),
4345 not,
4346 span,
4347 },
4348 height,
4349 is_constant,
4350 has_function,
4351 );
4352 }
4353 let op = if not { BinaryOp::IsNot } else { BinaryOp::Is };
4354 let height = lhs.height.max(rhs.height);
4355 let is_constant = lhs.is_constant && rhs.is_constant;
4356 let has_function = lhs.has_function || rhs.has_function;
4357 self.checked_expr(
4358 Expr::BinaryOp {
4359 left: Box::new(lhs.expr),
4360 op,
4361 right: Box::new(rhs.expr),
4362 span,
4363 },
4364 height,
4365 is_constant,
4366 has_function,
4367 )
4368 }
4369
4370 TokenKind::KwLike => self.parse_like(lhs, LikeOp::Like, false),
4372 TokenKind::KwGlob => self.parse_like(lhs, LikeOp::Glob, false),
4373 TokenKind::KwMatch => self.parse_like(lhs, LikeOp::Match, false),
4374 TokenKind::KwRegexp => self.parse_like(lhs, LikeOp::Regexp, false),
4375
4376 TokenKind::KwBetween => self.parse_between(lhs, false),
4378
4379 TokenKind::KwIn => self.parse_in(lhs, false),
4381
4382 TokenKind::Arrow => {
4384 let rhs = self.parse_expr_bp(r_bp)?;
4385 let span = lhs.expr.span().merge(rhs.expr.span());
4386 let height = lhs.height.max(rhs.height);
4387 let is_constant = false;
4388 let has_function = true;
4389 self.checked_expr(
4390 Expr::JsonAccess {
4391 expr: Box::new(lhs.expr),
4392 path: Box::new(rhs.expr),
4393 arrow: JsonArrow::Arrow,
4394 span,
4395 },
4396 height,
4397 is_constant,
4398 has_function,
4399 )
4400 }
4401 TokenKind::DoubleArrow => {
4402 let rhs = self.parse_expr_bp(r_bp)?;
4403 let span = lhs.expr.span().merge(rhs.expr.span());
4404 let height = lhs.height.max(rhs.height);
4405 let is_constant = false;
4406 let has_function = true;
4407 self.checked_expr(
4408 Expr::JsonAccess {
4409 expr: Box::new(lhs.expr),
4410 path: Box::new(rhs.expr),
4411 arrow: JsonArrow::DoubleArrow,
4412 span,
4413 },
4414 height,
4415 is_constant,
4416 has_function,
4417 )
4418 }
4419
4420 TokenKind::KwNot => {
4422 let next = self.advance_token();
4423 match &next.kind {
4424 TokenKind::KwLike => self.parse_like(lhs, LikeOp::Like, true),
4425 TokenKind::KwGlob => self.parse_like(lhs, LikeOp::Glob, true),
4426 TokenKind::KwMatch => self.parse_like(lhs, LikeOp::Match, true),
4427 TokenKind::KwRegexp => self.parse_like(lhs, LikeOp::Regexp, true),
4428 TokenKind::KwBetween => self.parse_between(lhs, true),
4429 TokenKind::KwIn => self.parse_in(lhs, true),
4430 _ => Err(ParseError::at(
4431 format!(
4432 "expected LIKE/GLOB/MATCH/REGEXP/BETWEEN/IN \
4433 after NOT, got {:?}",
4434 next.kind
4435 ),
4436 Some(&next),
4437 )),
4438 }
4439 }
4440
4441 other => Err(ParseError::at(
4442 format!("unexpected infix token: {other:?}"),
4443 Some(&tok),
4444 )),
4445 }
4446 }
4447
4448 #[cfg(test)]
4449 fn make_binop(
4450 &mut self,
4451 lhs: ParsedExpr,
4452 op: BinaryOp,
4453 r_bp: u8,
4454 ) -> Result<ParsedExpr, ParseError> {
4455 let rhs = self.parse_expr_bp(r_bp)?;
4456 let span = lhs.expr.span().merge(rhs.expr.span());
4457 let height = lhs.height.max(rhs.height);
4458 let is_constant = lhs.is_constant && rhs.is_constant;
4459 let has_function = lhs.has_function || rhs.has_function;
4460 self.checked_expr(
4461 Expr::BinaryOp {
4462 left: Box::new(lhs.expr),
4463 op,
4464 right: Box::new(rhs.expr),
4465 span,
4466 },
4467 height,
4468 is_constant,
4469 has_function,
4470 )
4471 }
4472
4473 #[cfg(test)]
4476 fn parse_like(
4477 &mut self,
4478 lhs: ParsedExpr,
4479 op: LikeOp,
4480 not: bool,
4481 ) -> Result<ParsedExpr, ParseError> {
4482 let pattern = self.parse_expr_bp(bp::EQUALITY.1)?;
4483 let escape = if self.eat_kind(&TokenKind::KwEscape) {
4484 Some(self.parse_expr_bp(bp::EQUALITY.1)?)
4487 } else {
4488 None
4489 };
4490 let end = escape
4491 .as_ref()
4492 .map_or_else(|| pattern.expr.span(), |e| e.expr.span());
4493 let span = lhs.expr.span().merge(end);
4494 let height = escape.as_ref().map_or_else(
4495 || lhs.height.max(pattern.height),
4496 |parsed| lhs.height.max(pattern.height).max(parsed.height),
4497 );
4498 let parsed = self.checked_expr(
4499 Expr::Like {
4500 expr: Box::new(lhs.expr),
4501 pattern: Box::new(pattern.expr),
4502 escape: escape.map(|parsed| Box::new(parsed.expr)),
4503 op,
4504 not,
4505 span,
4506 },
4507 height,
4508 false,
4509 true,
4510 )?;
4511 if not {
4512 self.add_cached_parent(parsed)
4513 } else {
4514 Ok(parsed)
4515 }
4516 }
4517
4518 #[cfg(test)]
4519 fn parse_between(&mut self, lhs: ParsedExpr, not: bool) -> Result<ParsedExpr, ParseError> {
4520 let low = self.parse_expr_bp(bp::NOT_PREFIX)?;
4522 if !self.eat_kind(&TokenKind::KwAnd) {
4523 return Err(self.err_here("expected AND in BETWEEN expression"));
4524 }
4525 let high = self.parse_expr_bp(bp::EQUALITY.1)?;
4526 let span = lhs.expr.span().merge(high.expr.span());
4527 let height = lhs.height.max(low.height).max(high.height);
4528 let is_constant = lhs.is_constant && low.is_constant && high.is_constant;
4529 let has_function = lhs.has_function || low.has_function || high.has_function;
4530 let parsed = self.checked_expr(
4531 Expr::Between {
4532 expr: Box::new(lhs.expr),
4533 low: Box::new(low.expr),
4534 high: Box::new(high.expr),
4535 not,
4536 span,
4537 },
4538 height,
4539 is_constant,
4540 has_function,
4541 )?;
4542 if not {
4543 self.add_cached_parent(parsed)
4544 } else {
4545 Ok(parsed)
4546 }
4547 }
4548
4549 #[cfg(test)]
4550 fn parse_in(&mut self, lhs: ParsedExpr, not: bool) -> Result<ParsedExpr, ParseError> {
4551 let start = lhs.expr.span();
4552
4553 if !self.at_kind(&TokenKind::LeftParen) {
4555 let table = self.parse_qualified_name()?;
4556 let end = self.tokens[self.pos.saturating_sub(1)].span;
4557 let span = start.merge(end);
4558 let height = lhs.height;
4559 let has_function = lhs.has_function;
4560 let parsed = self.checked_expr(
4561 Expr::In {
4562 expr: Box::new(lhs.expr),
4563 set: InSet::Table(table),
4564 not,
4565 span,
4566 },
4567 height,
4568 false,
4569 has_function,
4570 )?;
4571 return if not {
4572 self.add_cached_parent(parsed)
4573 } else {
4574 Ok(parsed)
4575 };
4576 }
4577
4578 self.expect_kind(&TokenKind::LeftParen)?;
4579
4580 if matches!(
4581 self.peek_kind(),
4582 TokenKind::KwSelect | TokenKind::KwWith | TokenKind::KwValues
4583 ) {
4584 let subquery = self.parse_subquery_minimal()?;
4585 let end = self.expect_kind(&TokenKind::RightParen)?;
4586 let span = start.merge(end);
4587 let height = lhs.height.max(subquery.height);
4588 let has_function = lhs.has_function;
4589 let parsed = self.checked_expr(
4590 Expr::In {
4591 expr: Box::new(lhs.expr),
4592 set: InSet::Subquery(Box::new(subquery.value)),
4593 not,
4594 span,
4595 },
4596 height,
4597 false,
4598 has_function,
4599 )?;
4600 return if not {
4601 self.add_cached_parent(parsed)
4602 } else {
4603 Ok(parsed)
4604 };
4605 }
4606
4607 let mut parsed_items = Vec::new();
4608 if !self.at_kind(&TokenKind::RightParen) {
4609 let item = self.parse_expr_bp(0)?;
4610 parsed_items.push(item);
4611 while self.eat_kind(&TokenKind::Comma) {
4612 let item = self.parse_expr_bp(0)?;
4613 parsed_items.push(item);
4614 }
4615 }
4616 let end = self.expect_kind(&TokenKind::RightParen)?;
4617 if let Some(message) = vector_in_list_arity_error(&lhs.expr, &parsed_items) {
4618 return Err(self.err_here(message));
4619 }
4620 let span = start.merge(end);
4621 let item_height = parsed_items
4622 .iter()
4623 .map(|item| item.height)
4624 .max()
4625 .unwrap_or(0);
4626 let items_are_constant = parsed_items.iter().all(|item| item.is_constant);
4627 let item_has_function = parsed_items.iter().any(|item| item.has_function);
4628 let singleton_constant = matches!(parsed_items.as_slice(), [item] if item.is_constant)
4629 && lhs.root != CachedRoot::Vector;
4630 let singleton_subquery =
4631 matches!(parsed_items.as_slice(), [item] if item.root == CachedRoot::ScalarSubquery);
4632 let exprs = parsed_items.into_iter().map(|parsed| parsed.expr).collect();
4633 let lhs_height = lhs.height;
4634 let lhs_is_constant = lhs.is_constant;
4635 let lhs_has_function = lhs.has_function;
4636 let expr = Expr::In {
4637 expr: Box::new(lhs.expr),
4638 set: InSet::List(exprs),
4639 not,
4640 span,
4641 };
4642
4643 if item_height == 0 {
4644 if lhs_has_function {
4645 return self.finish_expr(expr, lhs_height.saturating_add(1), false, true);
4646 }
4647 return self.finish_expr(expr, 1, true, false);
4648 }
4649
4650 let cached_child_height = if singleton_constant {
4651 lhs_height.max(item_height.saturating_add(1))
4652 } else if singleton_subquery {
4653 lhs_height.max(item_height.saturating_sub(1))
4654 } else {
4655 lhs_height.max(item_height)
4656 };
4657 let parsed = self.checked_expr(
4658 expr,
4659 cached_child_height,
4660 lhs_is_constant && items_are_constant,
4661 lhs_has_function || item_has_function,
4662 )?;
4663 if not {
4664 self.add_cached_parent(parsed)
4665 } else {
4666 Ok(parsed)
4667 }
4668 }
4669
4670 #[cfg(test)]
4671 fn parse_case_expr(&mut self, start: Span) -> Result<ParsedExpr, ParseError> {
4672 let operand = if matches!(self.peek_kind(), TokenKind::KwWhen) {
4673 None
4674 } else {
4675 Some(self.parse_expr_bp(0)?)
4676 };
4677
4678 let mut whens = Vec::new();
4679 while self.eat_kind(&TokenKind::KwWhen) {
4680 let condition = self.parse_expr_bp(0)?;
4681 if !self.eat_kind(&TokenKind::KwThen) {
4682 return Err(self.err_here("expected THEN in CASE expression"));
4683 }
4684 let result = self.parse_expr_bp(0)?;
4685 whens.push((condition, result));
4686 }
4687 if whens.is_empty() {
4688 return Err(self.err_here("CASE requires at least one WHEN clause"));
4689 }
4690
4691 let else_expr = if self.eat_kind(&TokenKind::KwElse) {
4692 Some(self.parse_expr_bp(0)?)
4693 } else {
4694 None
4695 };
4696
4697 if !self.eat_kind(&TokenKind::KwEnd) {
4698 return Err(self.err_here("expected END for CASE expression"));
4699 }
4700 let end = self.tokens[self.pos.saturating_sub(1)].span;
4701 let span = start.merge(end);
4702 let mut height = operand.as_ref().map_or(0, |parsed| parsed.height);
4703 let mut is_constant = operand.as_ref().is_none_or(|parsed| parsed.is_constant);
4704 let mut has_function = operand.as_ref().is_some_and(|parsed| parsed.has_function);
4705 for (condition, result) in &whens {
4706 height = height.max(condition.height).max(result.height);
4707 is_constant &= condition.is_constant && result.is_constant;
4708 has_function |= condition.has_function || result.has_function;
4709 }
4710 if let Some(parsed) = &else_expr {
4711 height = height.max(parsed.height);
4712 is_constant &= parsed.is_constant;
4713 has_function |= parsed.has_function;
4714 }
4715 self.checked_expr(
4716 Expr::Case {
4717 operand: operand.map(|parsed| Box::new(parsed.expr)),
4718 whens: whens
4719 .into_iter()
4720 .map(|(condition, result)| (condition.expr, result.expr))
4721 .collect(),
4722 else_expr: else_expr.map(|parsed| Box::new(parsed.expr)),
4723 span,
4724 },
4725 height,
4726 is_constant,
4727 has_function,
4728 )
4729 }
4730
4731 #[cfg(test)]
4732 fn parse_function_call(&mut self, name: String, start: Span) -> Result<ParsedExpr, ParseError> {
4733 self.expect_kind(&TokenKind::LeftParen)?;
4734
4735 let (args, distinct, height) = if matches!(self.peek_kind(), TokenKind::Star) {
4736 if !name.eq_ignore_ascii_case("count") {
4737 return Err(self.err_here("'*' can only be used with count() function"));
4738 }
4739 self.advance_token();
4740 (FunctionArgs::Star, false, 0)
4741 } else {
4742 let distinct = self.eat_kind(&TokenKind::KwDistinct);
4743 let (args, height) = if matches!(self.peek_kind(), TokenKind::RightParen) {
4744 if distinct {
4745 return Err(self.err_here("DISTINCT requires at least one argument"));
4746 }
4747 (FunctionArgs::List(Vec::new()), 0)
4748 } else {
4749 let first = self.parse_expr_bp(0)?;
4750 let mut height = first.height;
4751 let mut list = vec![first.expr];
4752 while self.eat_kind(&TokenKind::Comma) {
4753 let parsed = self.parse_expr_bp(0)?;
4754 height = height.max(parsed.height);
4755 list.push(parsed.expr);
4756 }
4757 (FunctionArgs::List(list), height)
4758 };
4759 (args, distinct, height)
4760 };
4761
4762 let order_by =
4764 if matches!(&args, FunctionArgs::List(_)) && self.eat_kind(&TokenKind::KwOrder) {
4765 self.expect_kind(&TokenKind::KwBy)?;
4766 self.parse_comma_sep(Self::parse_ordering_term)?
4767 } else {
4768 vec![]
4769 };
4770
4771 let mut end = self.expect_kind(&TokenKind::RightParen)?;
4772 let filter = if matches!(self.peek_kind(), TokenKind::KwFilter)
4775 && self
4776 .tokens
4777 .get(self.pos + 1)
4778 .is_some_and(|t| t.kind == TokenKind::LeftParen)
4779 {
4780 self.advance_token(); self.expect_kind(&TokenKind::LeftParen)?;
4782 self.expect_kind(&TokenKind::KwWhere)?;
4783 let predicate = self.parse_expr()?;
4784 let filter_end = self.expect_kind(&TokenKind::RightParen)?;
4785 end = end.merge(filter_end);
4786 Some(Box::new(predicate))
4787 } else {
4788 None
4789 };
4790 let over = if matches!(self.peek_kind(), TokenKind::KwOver)
4793 && self.tokens.get(self.pos + 1).is_some_and(|t| {
4794 matches!(t.kind, TokenKind::LeftParen) || starts_bare_window_name(&t.kind)
4795 }) {
4796 self.advance_token(); if self.eat_kind(&TokenKind::LeftParen) {
4798 let spec = self.parse_window_spec()?;
4799 let over_end = self.expect_kind(&TokenKind::RightParen)?;
4800 end = end.merge(over_end);
4801 Some(spec)
4802 } else {
4803 let base_window = self.parse_window_name()?;
4804 let base_span = self.tokens[self.pos.saturating_sub(1)].span;
4805 end = end.merge(base_span);
4806 Some(WindowSpec {
4807 window_ref: Some(WindowReference::Direct(base_window)),
4808 partition_by: Vec::new(),
4809 order_by: Vec::new(),
4810 frame: None,
4811 })
4812 }
4813 } else {
4814 None
4815 };
4816
4817 let span = start.merge(end);
4818 self.checked_expr(
4819 Expr::FunctionCall {
4820 name,
4821 args,
4822 distinct,
4823 order_by,
4824 filter,
4825 over,
4826 span,
4827 },
4828 height,
4829 false,
4830 true,
4831 )
4832 }
4833
4834 fn parse_raise_args(&mut self) -> Result<(RaiseAction, Option<String>), ParseError> {
4835 let action_tok = self.advance_token();
4836 let action = match &action_tok.kind {
4837 TokenKind::KwIgnore => RaiseAction::Ignore,
4838 TokenKind::KwRollback => RaiseAction::Rollback,
4839 TokenKind::KwAbort => RaiseAction::Abort,
4840 TokenKind::KwFail => RaiseAction::Fail,
4841 _ => {
4842 return Err(ParseError::at(
4843 "expected IGNORE, ROLLBACK, ABORT, or FAIL in RAISE",
4844 Some(&action_tok),
4845 ));
4846 }
4847 };
4848 if matches!(action, RaiseAction::Ignore) {
4849 return Ok((action, None));
4850 }
4851 self.expect_kind(&TokenKind::Comma)?;
4852 let msg_tok = self.advance_token();
4853 let message = match &msg_tok.kind {
4854 TokenKind::String(s) => s.clone(),
4855 _ => {
4856 return Err(ParseError::at(
4857 "expected string message in RAISE",
4858 Some(&msg_tok),
4859 ));
4860 }
4861 };
4862 Ok((action, Some(message)))
4863 }
4864
4865 fn parse_type_name(&mut self) -> Result<TypeName, ParseError> {
4866 let mut parts = Vec::new();
4867 loop {
4868 match self.peek_kind() {
4869 TokenKind::Id(_) | TokenKind::QuotedId(_, _) => {
4870 let tok = self.advance_token();
4871 if let TokenKind::Id(s) | TokenKind::QuotedId(s, _) = &tok.kind {
4872 parts.push(s.to_string());
4873 } else {
4874 unreachable!();
4875 }
4876 }
4877 k if is_nonreserved_kw(k) => {
4878 let tok = self.advance_token();
4879 parts.push(kw_to_str(&tok.kind));
4880 }
4881 _ => break,
4882 }
4883 }
4884 if parts.is_empty() {
4885 return Err(self.err_here("expected type name"));
4886 }
4887 let name = parts.join(" ");
4888
4889 let (arg1, arg2) = if self.eat_kind(&TokenKind::LeftParen) {
4890 let a1 = self.parse_type_arg()?;
4891 let a2 = if self.eat_kind(&TokenKind::Comma) {
4892 Some(self.parse_type_arg()?)
4893 } else {
4894 None
4895 };
4896 self.expect_kind(&TokenKind::RightParen)?;
4897 (Some(a1), a2)
4898 } else {
4899 (None, None)
4900 };
4901
4902 Ok(TypeName { name, arg1, arg2 })
4903 }
4904
4905 fn parse_type_arg(&mut self) -> Result<String, ParseError> {
4906 let tok = self.advance_token();
4907 match &tok.kind {
4908 TokenKind::Integer(i) => Ok(i.to_string()),
4909 TokenKind::Float(f) => Ok(f.to_string()),
4910 TokenKind::Minus => {
4911 let next = self.advance_token();
4912 match &next.kind {
4913 TokenKind::Integer(i) => Ok(format!("-{i}")),
4914 TokenKind::OversizedInt(s) => Ok(format!("-{s}")),
4915 TokenKind::Float(f) => Ok(format!("-{f}")),
4916 _ => Err(ParseError::at(
4917 "expected number in type argument",
4918 Some(&next),
4919 )),
4920 }
4921 }
4922 TokenKind::Plus => {
4923 let next = self.advance_token();
4924 match &next.kind {
4925 TokenKind::Integer(i) => Ok(format!("+{i}")),
4926 TokenKind::OversizedInt(s) => Ok(format!("+{s}")),
4927 TokenKind::Float(f) => Ok(format!("+{f}")),
4928 _ => Err(ParseError::at(
4929 "expected number in type argument",
4930 Some(&next),
4931 )),
4932 }
4933 }
4934 TokenKind::OversizedInt(s) => Ok(s.clone()),
4935 TokenKind::Id(s) | TokenKind::QuotedId(s, _) => Ok(s.to_string()),
4936 _ => Err(ParseError::at("expected type argument", Some(&tok))),
4937 }
4938 }
4939
4940 #[cfg(test)]
4942 fn parse_subquery_minimal(&mut self) -> Result<HeightTracked<SelectStatement>, ParseError> {
4943 let with = if self.at_kind(&TokenKind::KwWith) {
4944 Some(ParseMachine::for_with(self).run_with()?)
4945 } else {
4946 None
4947 };
4948 ParseMachine::for_select(self, with).run_select()
4949 }
4950}
4951
4952pub fn parse_expr(sql: &str) -> Result<Expr, ParseError> {
4954 let mut parser = Parser::from_sql(sql);
4955 let expr = parser.parse_expr()?;
4956 let _ = parser.eat(&TokenKind::Semicolon);
4957 if !parser.at_eof() {
4958 return Err(parser.err_here(format!(
4959 "unexpected token after expression: {:?}",
4960 parser.peek_kind()
4961 )));
4962 }
4963 Ok(expr)
4964}
4965
4966#[cfg(test)]
4967mod tests {
4968 use super::*;
4969 use crate::parser::ParseErrorKind;
4970 use fsqlite_ast::{BoundCollation, SelectCore, TableOrSubquery};
4971 use fsqlite_types::{SqliteValue, TypeAffinity};
4972
4973 fn parse(sql: &str) -> Expr {
4974 match parse_expr(sql) {
4975 Ok(expr) => expr,
4976 Err(err) => unreachable!("parse error for `{sql}`: {err}"),
4977 }
4978 }
4979
4980 fn repeated_infix_expression(term_count: usize, operator: &str) -> String {
4981 std::iter::repeat_n("1", term_count)
4982 .collect::<Vec<_>>()
4983 .join(operator)
4984 }
4985
4986 fn assert_expression_depth_error(sql: &str) {
4987 let error = parse_expr(sql).expect_err("expression height 1001 must fail closed");
4988 assert_eq!(
4989 error.kind,
4990 ParseErrorKind::ExpressionTooDeep {
4991 max: MAX_PARSE_DEPTH
4992 }
4993 );
4994 assert_eq!(
4995 error.message,
4996 format!(
4997 "Expression tree is too large (maximum depth {})",
4998 MAX_PARSE_DEPTH
4999 )
5000 );
5001 assert!(error.is_expression_too_deep());
5002 }
5003
5004 fn right_deep_binary_expression(height: usize) -> String {
5005 format!("{}1{}", "1 + (".repeat(height - 1), ")".repeat(height - 1))
5006 }
5007
5008 fn single_arg_function_expression(height: usize) -> String {
5009 format!("{}1{}", "abs(".repeat(height - 1), ")".repeat(height - 1))
5010 }
5011
5012 fn scalar_subquery_expression(height: usize) -> String {
5013 format!(
5014 "{}1{}",
5015 "(SELECT ".repeat(height - 1),
5016 ")".repeat(height - 1)
5017 )
5018 }
5019
5020 fn on_one_mib_stack<T: Send + 'static>(task: impl FnOnce() -> T + Send + 'static) -> T {
5021 std::thread::Builder::new()
5022 .stack_size(1024 * 1024)
5023 .spawn(task)
5024 .expect("1 MiB parser thread must spawn")
5025 .join()
5026 .expect("parser task must not overflow or panic")
5027 }
5028
5029 fn parsed_select_height(sql: &str) -> u32 {
5030 let mut parser = Parser::from_sql(sql);
5031 let select = parser
5032 .parse_subquery_minimal()
5033 .expect("SELECT fixture must parse");
5034 assert_eq!(
5035 select.height,
5036 normalized_ast_select_height(&select.value),
5037 "tracked SELECT height diverged from the normalized AST test oracle"
5038 );
5039 select.height
5040 }
5041
5042 fn parsed_expr_height(sql: &str) -> u32 {
5043 let mut parser = Parser::from_sql(sql);
5044 let parsed = parser
5045 .parse_expr_tracked()
5046 .expect("expression fixture must parse");
5047 assert!(
5048 matches!(parser.peek_kind(), TokenKind::Eof | TokenKind::Semicolon),
5049 "expression fixture left an unparsed token: {sql}"
5050 );
5051 assert_eq!(
5052 parsed.height,
5053 normalized_ast_expr_height(&parsed.expr),
5054 "tracked expression height diverged from the normalized AST test oracle: {sql}"
5055 );
5056 parsed.height
5057 }
5058
5059 #[test]
5060 fn bound_outer_value_has_constant_leaf_facts() {
5061 let expr = Expr::BoundOuterValue {
5062 value: SqliteValue::Integer(42),
5063 collation: BoundCollation::Named("NOCASE".to_owned()),
5064 affinity: Some(TypeAffinity::Integer),
5065 span: Span::ZERO,
5066 };
5067
5068 let parsed = ParsedExpr::leaf(expr.clone());
5069 assert_eq!(parsed.height, 1);
5070 assert!(parsed.is_constant);
5071 assert!(!parsed.has_function);
5072
5073 let facts = cached_facts_from_tasks(vec![CachedHeightTask::Expr(&expr)]);
5074 assert_eq!(facts.height, 1);
5075 assert!(facts.is_constant);
5076 assert!(!facts.has_function);
5077 }
5078
5079 fn mixed_deep_expression(height: usize) -> String {
5080 let mut prefix = String::new();
5081 let mut closing_count = 0;
5082 for index in 1..height {
5083 if index % 7 == 0 {
5084 prefix.push('(');
5085 closing_count += 1;
5086 }
5087 match index % 4 {
5088 0 => prefix.push('~'),
5089 1 => {
5090 prefix.push_str("abs(");
5091 closing_count += 1;
5092 }
5093 2 => {
5094 prefix.push_str("(SELECT ");
5095 closing_count += 1;
5096 }
5097 _ => {
5098 prefix.push_str("1 + (");
5099 closing_count += 1;
5100 }
5101 }
5102 }
5103 prefix.push('1');
5104 prefix.push_str(&")".repeat(closing_count));
5105 prefix
5106 }
5107
5108 fn assert_machine_matches_recursive_oracle(sql: &str) {
5109 let mut machine = Parser::from_sql(sql);
5110 let machine_result = machine.parse_expr_tracked();
5111 let machine_pos = machine.pos;
5112 let machine_tail = machine.peek_kind().clone();
5113
5114 let mut oracle = Parser::from_sql(sql);
5115 let oracle_result = oracle.parse_expr_bp(0);
5116 let oracle_pos = oracle.pos;
5117 let oracle_tail = oracle.peek_kind().clone();
5118
5119 assert_eq!(
5120 machine_pos, oracle_pos,
5121 "parser tail position differs: {sql}"
5122 );
5123 assert_eq!(
5124 machine_tail, oracle_tail,
5125 "parser tail token differs: {sql}"
5126 );
5127 match (machine_result, oracle_result) {
5128 (Ok(machine), Ok(oracle)) => {
5129 assert_eq!(machine.expr, oracle.expr, "AST or spans differ: {sql}");
5130 assert_eq!(machine.height, oracle.height, "height differs: {sql}");
5131 assert_eq!(
5132 machine.is_constant, oracle.is_constant,
5133 "constant fact differs: {sql}"
5134 );
5135 assert_eq!(
5136 machine.has_function, oracle.has_function,
5137 "function fact differs: {sql}"
5138 );
5139 assert_eq!(machine.root, oracle.root, "root fact differs: {sql}");
5140 }
5141 (Err(machine), Err(oracle)) => {
5142 assert_eq!(machine, oracle, "diagnostic differs: {sql}");
5143 }
5144 (Ok(_), Err(_)) | (Err(_), Ok(_)) => {
5145 panic!("machine/oracle result class differs for `{sql}`");
5146 }
5147 }
5148 }
5149
5150 fn assert_select_machine_matches_recursive_oracle(sql: &str) {
5151 let mut machine = Parser::from_sql(sql);
5152 let machine_result = machine.parse_select_stmt_tracked(None);
5153 let machine_pos = machine.pos;
5154 let machine_tail = machine.peek_kind().clone();
5155
5156 let mut oracle = Parser::from_sql(sql);
5157 let oracle_result = oracle.parse_select_stmt_inner_tracked(None);
5158 let oracle_pos = oracle.pos;
5159 let oracle_tail = oracle.peek_kind().clone();
5160
5161 assert_eq!(
5162 machine_pos, oracle_pos,
5163 "SELECT parser tail position differs: {sql}"
5164 );
5165 assert_eq!(
5166 machine_tail, oracle_tail,
5167 "SELECT parser tail token differs: {sql}"
5168 );
5169 match (machine_result, oracle_result) {
5170 (Ok(machine), Ok(oracle)) => {
5171 assert_eq!(machine.value, oracle.value, "SELECT AST differs: {sql}");
5172 assert_eq!(
5173 machine.height, oracle.height,
5174 "SELECT height differs: {sql}"
5175 );
5176 }
5177 (Err(machine), Err(oracle)) => {
5178 assert_eq!(machine, oracle, "SELECT diagnostic differs: {sql}");
5179 }
5180 (Ok(_), Err(_)) | (Err(_), Ok(_)) => {
5181 panic!("SELECT machine/oracle result class differs for `{sql}`");
5182 }
5183 }
5184 }
5185
5186 fn bitnot_depth(mut expr: &Expr) -> usize {
5187 let mut depth = 0;
5188 while let Expr::UnaryOp {
5189 op: UnaryOp::BitNot,
5190 expr: inner,
5191 ..
5192 } = expr
5193 {
5194 depth += 1;
5195 expr = inner;
5196 }
5197 depth
5198 }
5199
5200 fn wrap_function_to_height(base: &str, target_height: usize) -> String {
5201 let base_height = parsed_expr_height(base) as usize;
5202 assert!(base_height <= target_height);
5203 let wrappers = target_height - base_height;
5204 format!("{}{base}{}", "abs(".repeat(wrappers), ")".repeat(wrappers))
5205 }
5206
5207 #[test]
5208 fn test_explicit_machine_matches_recursive_oracle_for_shallow_valid_expressions() {
5209 for sql in [
5210 "1",
5211 "-9223372036854775808",
5212 "a.b + c * 2",
5213 "'a'.b + a.'b'",
5214 "attach.x",
5215 "filter.x",
5216 "true.x",
5217 "with.x",
5218 "a.current_date",
5219 "NOT a = b",
5220 "x IS NULL < 2",
5221 "x IS NOT DISTINCT FROM y",
5222 "CAST(x + 1 AS DECIMAL(10, 2))",
5223 "CASE x WHEN 1 THEN y ELSE z END",
5224 "x NOT BETWEEN 1 AND 2",
5225 "x IN (1, 2 + 3)",
5226 "(SELECT 1, 2) IN ((1, 2))",
5227 "(a, b) IN ((SELECT 1))",
5228 "(a, b) IN ((SELECT 1, 2, 3))",
5229 "(SELECT * FROM t) IN (1)",
5230 "x IN (SELECT y FROM t WHERE z > 0 ORDER BY y LIMIT 1)",
5231 "EXISTS (SELECT 1 FROM t WHERE x = y)",
5232 "(1, 2 + 3)",
5233 "value COLLATE \"my col\"",
5234 "doc -> '$.x' || suffix",
5235 "sum(DISTINCT x ORDER BY y DESC) FILTER (WHERE z > 0) OVER (PARTITION BY p ORDER BY q ROWS BETWEEN 1 PRECEDING AND CURRENT ROW)",
5236 ] {
5237 assert_machine_matches_recursive_oracle(sql);
5238 }
5239 }
5240
5241 #[test]
5242 fn test_explicit_machine_matches_recursive_oracle_for_shallow_malformed_expressions() {
5243 for sql in [
5244 "+",
5245 "CASE END",
5246 "CASE WHEN 1 2 END",
5247 "CASE WHEN 1 THEN 2",
5248 "CAST(1 INTEGER)",
5249 "f(DISTINCT)",
5250 "(1,)",
5251 "a.",
5252 "a.select",
5253 "a.nothing",
5254 "cast.x",
5255 "current_date.x",
5256 "raise.x",
5257 "transaction.x",
5258 "a BETWEEN 1 2",
5259 "a IN (1,)",
5260 "(a, b) IN (1)",
5261 "(a, b) IN (+(SELECT 1, 2))",
5262 "(a, b) IN ((SELECT 1), (SELECT 2))",
5263 "(a, b) IN ((1, 2), 3)",
5264 "(a, b) NOT IN ((1, 2, 3))",
5265 "(SELECT 1, 2) IN (1)",
5266 "(SELECT 1, 2) IN ((1, 2), 3)",
5267 "(SELECT 1, 2) NOT IN ((1, 2, 3))",
5268 "a LIKE",
5269 "EXISTS (SELECT)",
5270 "count(* ORDER BY x)",
5271 "t.*",
5272 ] {
5273 assert_machine_matches_recursive_oracle(sql);
5274 }
5275 }
5276
5277 #[test]
5278 fn public_parse_expr_requires_eof_after_one_optional_terminator() {
5279 assert_eq!(
5280 parse_expr("1;")
5281 .expect("one trailing expression terminator must remain valid")
5282 .to_string(),
5283 "1"
5284 );
5285
5286 for (sql, unexpected) in [("1; 2", "2"), ("1; SELECT 2", "SELECT"), ("1;;", ";")] {
5287 let error = parse_expr(sql)
5288 .expect_err("tokens after the optional expression terminator must be rejected");
5289 assert_eq!(error.kind, ParseErrorKind::Syntax);
5290 assert!(
5291 error.message.contains("unexpected token after expression"),
5292 "unexpected diagnostic for `{sql}`: {error:?}"
5293 );
5294 assert_eq!(
5295 &sql[error.span.start as usize..error.span.end as usize],
5296 unexpected,
5297 "the diagnostic for `{sql}` must point at the first forbidden token"
5298 );
5299 }
5300 }
5301
5302 #[test]
5303 fn test_explicit_select_machine_matches_recursive_shallow_oracle() {
5304 for sql in [
5305 "SELECT 1",
5306 "SELECT DISTINCT t.x AS y, count(*) FROM t INNER JOIN u ON t.id = u.id WHERE t.x > 0 GROUP BY t.x HAVING count(*) > 1 WINDOW w AS (PARTITION BY t.p ORDER BY t.q ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) ORDER BY t.x DESC NULLS LAST LIMIT 5 OFFSET 1",
5307 "SELECT * FROM a CROSS JOIN b ON a.id = b.id",
5308 "SELECT * FROM a, b",
5309 "SELECT * FROM a, b ON a.id = b.id",
5310 "SELECT * FROM a, b USING(id)",
5311 "SELECT filter.* FROM t AS filter",
5312 "SELECT attach.* FROM t AS \"attach\"",
5313 "SELECT attach.x FROM (SELECT 1 AS x) AS \"attach\"",
5314 "SELECT filter.x FROM (SELECT 1 AS x) AS \"filter\"",
5315 "SELECT 't'.*, t.'select' FROM t",
5316 "SELECT 1 'single quoted'",
5317 "SELECT 1 attach",
5318 "SELECT 1 window",
5319 "SELECT * FROM (SELECT 1) 'single quoted'",
5320 "SELECT * FROM (SELECT 1) match",
5321 "SELECT sum(1) OVER attach WINDOW attach AS ()",
5322 "SELECT sum(1) OVER (attach) WINDOW attach AS ()",
5323 "SELECT sum(x) OVER (ROWS BETWEEN 1 PRECEDING AND 2 PRECEDING) FROM t",
5324 "SELECT sum(x) OVER (RANGE BETWEEN CURRENT ROW AND 1 FOLLOWING) FROM t",
5325 "VALUES (1, 2), (3, 4)",
5326 "VALUES (1) ORDER BY 1",
5327 "VALUES (1) LIMIT 1",
5328 "VALUES (1) UNION SELECT 2 ORDER BY 1 LIMIT 1",
5329 "SELECT 1 UNION ALL SELECT 2 INTERSECT SELECT 3",
5330 "SELECT 1 UNION VALUES (2), (3) ORDER BY 1",
5331 "SELECT FROM t",
5332 "SELECT nothing.* FROM t AS \"nothing\"",
5333 "SELECT sum(1) OVER filter",
5334 "SELECT sum(x) OVER (ROWS 1 FOLLOWING) FROM t",
5335 "SELECT sum(x) OVER (ROWS BETWEEN CURRENT ROW AND 1 PRECEDING) FROM t",
5336 "VALUES 1",
5337 ] {
5338 assert_select_machine_matches_recursive_oracle(sql);
5339 }
5340 }
5341
5342 #[test]
5343 fn test_threshold_unary_precedence_associativity_and_spans_are_stable() {
5344 for unary_count in [63_u32, 64] {
5345 let sql = format!("{}1 + (1)", "~".repeat(unary_count as usize));
5346 let parsed = parse_expr(&sql).expect("threshold unary-plus expression must parse");
5347 assert_eq!(
5348 parsed.span(),
5349 Span::new(0, unary_count + 6),
5350 "grouping delimiters must not change the established root span"
5351 );
5352 let Expr::BinaryOp {
5353 left,
5354 op: BinaryOp::Add,
5355 right,
5356 ..
5357 } = &parsed
5358 else {
5359 panic!("unary prefix must not capture the lower-precedence addition");
5360 };
5361 assert_eq!(bitnot_depth(left), unary_count as usize);
5362 assert!(matches!(
5363 right.as_ref(),
5364 Expr::Literal(Literal::Integer(1), _)
5365 ));
5366
5367 let subtraction = format!("{}10 - 3 - 2", "~".repeat(unary_count as usize));
5368 let subtraction =
5369 parse_expr(&subtraction).expect("threshold subtraction expression must parse");
5370 assert!(matches!(
5371 subtraction,
5372 Expr::BinaryOp {
5373 op: BinaryOp::Subtract,
5374 left,
5375 ..
5376 } if matches!(
5377 left.as_ref(),
5378 Expr::BinaryOp {
5379 op: BinaryOp::Subtract,
5380 ..
5381 }
5382 )
5383 ));
5384
5385 let precedence = format!("{}1 + 2 * 3", "~".repeat(unary_count as usize));
5386 let precedence =
5387 parse_expr(&precedence).expect("threshold precedence expression must parse");
5388 assert!(matches!(
5389 precedence,
5390 Expr::BinaryOp {
5391 op: BinaryOp::Add,
5392 right,
5393 ..
5394 } if matches!(
5395 right.as_ref(),
5396 Expr::BinaryOp {
5397 op: BinaryOp::Multiply,
5398 ..
5399 }
5400 )
5401 ));
5402
5403 let parenthesized = format!(
5404 "{}1{}",
5405 "(".repeat(unary_count as usize),
5406 ")".repeat(unary_count as usize)
5407 );
5408 let parenthesized =
5409 parse_expr(&parenthesized).expect("threshold parentheses must parse");
5410 assert_eq!(
5411 parenthesized.span(),
5412 Span::new(unary_count, unary_count + 1)
5413 );
5414 }
5415 }
5416
5417 #[test]
5418 fn test_shallow_machine_uses_only_inline_control_and_value_storage() {
5419 PARSE_MACHINE_STACK_SPILLS.set(0);
5420 let expr = parse_expr("a + b * 2").expect("shallow expression must parse");
5421 assert_eq!(expr.to_string(), "a + b * 2");
5422 assert_eq!(
5423 PARSE_MACHINE_STACK_SPILLS.get(),
5424 0,
5425 "representative shallow parsing must not allocate parser stack spill storage"
5426 );
5427 }
5428
5429 #[test]
5430 fn test_formatter_precedence_associativity_and_migration_scale_stability() {
5431 for (sql, expected) in [
5432 ("a + b * 2", "a + b * 2"),
5433 ("a * (b + c)", "a * (b + c)"),
5434 ("(a - b) - c", "a - b - c"),
5435 ("a - (b - c)", "a - (b - c)"),
5436 ("a / (b / c)", "a / (b / c)"),
5437 ] {
5438 let expr = parse_expr(sql).expect("precedence fixture must parse");
5439 let rendered = expr.to_string();
5440 assert_eq!(rendered, expected);
5441 let reparsed = parse_expr(&rendered).expect("formatted fixture must reparse");
5442 assert_eq!(reparsed.to_string(), rendered);
5443 }
5444
5445 const TERM_COUNT: usize = MAX_PARSE_DEPTH as usize;
5446 for operator in ["AND", "OR"] {
5447 let mut sql = String::new();
5448 for _ in 1..TERM_COUNT {
5449 sql.push_str("flag ");
5450 sql.push_str(operator);
5451 sql.push_str(" (");
5452 }
5453 sql.push_str("flag");
5454 sql.push_str(&")".repeat(TERM_COUNT - 1));
5455
5456 let expr = parse_expr(&sql).expect("migration-scale associative chain must parse");
5457 let rendered = expr.to_string();
5458 assert_eq!(rendered.matches(operator).count(), TERM_COUNT - 1);
5459 assert!(
5460 !rendered.contains('('),
5461 "associative {operator} chain must have a flat canonical form"
5462 );
5463 let reparsed = parse_expr(&rendered).expect("flat migration-scale chain must reparse");
5464 assert_eq!(
5465 reparsed.to_string(),
5466 rendered,
5467 "format-parse-format must be byte-stable for {operator}"
5468 );
5469 }
5470 }
5471
5472 #[test]
5473 fn test_expression_height_exact_1000_1001_flat_infix_boundary() {
5474 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5475 let at_limit = repeated_infix_expression(LIMIT, " + ");
5476 let expr = parse_expr(&at_limit).expect("1000-term left-associated tree has height 1000");
5477 let rendered = expr.to_string();
5478 parse_expr(&rendered).expect("formatted height-1000 expression must remain parseable");
5479
5480 let over_limit = repeated_infix_expression(LIMIT + 1, " + ");
5481 assert_expression_depth_error(&over_limit);
5482 }
5483
5484 #[test]
5485 fn test_expression_height_exact_1000_1001_unary_boundary() {
5486 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5487 let at_limit = format!("{}1", "~".repeat(LIMIT - 1));
5488 parse_expr(&at_limit).expect("999 unary nodes plus one leaf have height 1000");
5489
5490 let over_limit = format!("{}1", "~".repeat(LIMIT));
5491 assert_expression_depth_error(&over_limit);
5492 }
5493
5494 #[test]
5495 fn test_expression_height_exact_1000_1001_not_boundary() {
5496 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5497 let at_limit = format!("{}1", "NOT ".repeat(LIMIT - 1));
5498 parse_expr(&at_limit).expect("999 NOT nodes plus one leaf have height 1000");
5499
5500 let over_limit = format!("{}1", "NOT ".repeat(LIMIT));
5501 assert_expression_depth_error(&over_limit);
5502 }
5503
5504 #[test]
5505 fn test_expression_parenthesis_chain_is_stack_safe() {
5506 const PAREN_PAIRS: usize = MAX_PARSE_DEPTH as usize * 2;
5507 let deeply_parenthesized =
5508 format!("{}1{}", "(".repeat(PAREN_PAIRS), ")".repeat(PAREN_PAIRS));
5509 parse_expr(&deeply_parenthesized)
5510 .expect("parentheses do not add AST height or consume the native call stack");
5511 }
5512
5513 #[test]
5514 fn test_expression_prefix_frames_preserve_grouping_and_row_values() {
5515 let grouped = parse_expr("-((1 + 2)) * 3").expect("grouped unary expression must parse");
5516 assert!(matches!(
5517 grouped,
5518 Expr::BinaryOp {
5519 left,
5520 op: BinaryOp::Multiply,
5521 ..
5522 } if matches!(
5523 left.as_ref(),
5524 Expr::UnaryOp {
5525 op: UnaryOp::Negate,
5526 ..
5527 }
5528 )
5529 ));
5530
5531 let row = parse_expr("((1), 2)").expect("nested row value must parse");
5532 assert!(matches!(row, Expr::RowValue(values, _) if values.len() == 2));
5533 }
5534
5535 #[test]
5536 fn test_expression_iterative_prefix_frames_preserve_minimum_integer_literal() {
5537 let mut parser = Parser::from_sql("-9223372036854775808");
5538 let parsed = parser
5539 .parse_expr_tracked()
5540 .expect("minimum signed integer literal must parse");
5541 assert!(matches!(
5542 &parsed.expr,
5543 Expr::Literal(Literal::Integer(i64::MIN), _)
5544 ));
5545 assert_eq!(parsed.height, 1);
5546 assert_eq!(parsed.expr.to_string(), "-9223372036854775808");
5547 }
5548
5549 #[test]
5550 fn test_serializer_regression_double_negated_minimum_integer_round_trips() {
5551 let expr = parse_expr("- -9223372036854775808")
5552 .expect("double-negated minimum integer must parse");
5553 let rendered = expr.to_string();
5554 assert_eq!(rendered, "-(-9223372036854775808)");
5555 let reparsed = parse_expr(&rendered).expect("rendered double negation must remain SQL");
5556 assert_eq!(expr, reparsed);
5557 }
5558
5559 #[test]
5560 fn test_serializer_regression_quoted_collation_name_round_trips() {
5561 let expr =
5562 parse_expr("value COLLATE \"my col\"").expect("quoted collation name must parse");
5563 let rendered = expr.to_string();
5564 assert_eq!(rendered, "value COLLATE \"my col\"");
5565 let reparsed = parse_expr(&rendered).expect("rendered collation must remain SQL");
5566 assert_eq!(expr, reparsed);
5567 }
5568
5569 #[test]
5570 fn test_expression_height_mixed_prefix_and_flat_reductions() {
5571 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5572 const PREFIX_COUNT: usize = 499;
5573 let at_limit = format!(
5574 "{}{}",
5575 "~".repeat(PREFIX_COUNT),
5576 repeated_infix_expression(LIMIT - PREFIX_COUNT, " - ")
5577 );
5578 parse_expr(&at_limit)
5579 .expect("mixed unary and left-associated reductions have exact height 1000");
5580
5581 let over_limit = format!(
5582 "{}{}",
5583 "~".repeat(PREFIX_COUNT),
5584 repeated_infix_expression(LIMIT - PREFIX_COUNT + 1, " - ")
5585 );
5586 assert_expression_depth_error(&over_limit);
5587 }
5588
5589 #[test]
5590 fn test_expression_height_container_adds_one_level() {
5591 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5592 let at_limit = format!("abs({})", repeated_infix_expression(LIMIT - 1, " + "));
5593 parse_expr(&at_limit).expect("function node over height-999 argument has height 1000");
5594
5595 let over_limit = format!("abs({})", repeated_infix_expression(LIMIT, " + "));
5596 assert_expression_depth_error(&over_limit);
5597 }
5598
5599 #[test]
5600 fn test_right_deep_binary_exact_1000_1001_boundary_on_one_mib_stack() {
5601 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5602 let at_limit = right_deep_binary_expression(LIMIT);
5603 let expr = on_one_mib_stack(move || {
5604 parse_expr(&at_limit).expect("right-deep height-1000 expression must parse")
5605 });
5606 assert_expression_depth_error(&right_deep_binary_expression(LIMIT + 1));
5607 drop(expr);
5608 }
5609
5610 #[test]
5611 fn test_single_arg_function_exact_1000_1001_boundary_on_one_mib_stack() {
5612 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5613 let at_limit = single_arg_function_expression(LIMIT);
5614 let expr = on_one_mib_stack(move || {
5615 parse_expr(&at_limit).expect("nested function height-1000 expression must parse")
5616 });
5617 assert_expression_depth_error(&single_arg_function_expression(LIMIT + 1));
5618 drop(expr);
5619 }
5620
5621 #[test]
5622 fn test_scalar_subquery_exact_1000_1001_boundary_on_one_mib_stack() {
5623 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5624 let at_limit = scalar_subquery_expression(LIMIT);
5625 let rendered_selects = on_one_mib_stack(move || {
5626 let expr =
5627 parse_expr(&at_limit).expect("scalar subquery height-1000 expression must parse");
5628 let rendered = expr.to_string();
5629 let select_count = rendered.matches("(SELECT ").count();
5630 drop(rendered);
5631 drop(expr);
5632 select_count
5633 });
5634 assert_eq!(rendered_selects, LIMIT - 1);
5635 assert_expression_depth_error(&scalar_subquery_expression(LIMIT + 1));
5636 }
5637
5638 #[test]
5639 fn test_signed_minimum_and_qualified_bases_round_trip_on_one_mib_stack() {
5640 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5641 for (base, canonical_base) in [
5642 ("-9223372036854775808", "-9223372036854775808"),
5643 ("schema.column", "schema.\"column\""),
5644 ] {
5645 let at_limit = wrap_function_to_height(base, LIMIT);
5646 let (height, rendered) = on_one_mib_stack(move || {
5647 let expr = parse_expr(&at_limit).expect("height-1000 base expression must parse");
5648 let height = normalized_ast_expr_height(&expr);
5649 let rendered = expr.to_string();
5650 let reparsed =
5651 parse_expr(&rendered).expect("formatted height-1000 base must reparse");
5652 assert_eq!(normalized_ast_expr_height(&reparsed), MAX_PARSE_DEPTH);
5653 assert_eq!(rendered, reparsed.to_string());
5654 drop(reparsed);
5655 drop(expr);
5656 (height, rendered)
5657 });
5658 assert_eq!(height, MAX_PARSE_DEPTH);
5659 assert!(rendered.contains(canonical_base));
5660
5661 let over_limit = wrap_function_to_height(base, LIMIT + 1);
5662 let error = on_one_mib_stack(move || {
5663 parse_expr(&over_limit).expect_err("height-1001 base must fail closed")
5664 });
5665 assert_eq!(
5666 error.kind,
5667 ParseErrorKind::ExpressionTooDeep {
5668 max: MAX_PARSE_DEPTH
5669 }
5670 );
5671 }
5672 }
5673
5674 #[test]
5675 fn test_mixed_deep_height_1000_parse_walk_format_and_drop_on_one_mib_stack() {
5676 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5677 let at_limit = mixed_deep_expression(LIMIT);
5678 let (height, rendered_len, walk_visits) = on_one_mib_stack(move || {
5679 let expr = parse_expr(&at_limit)
5680 .expect("mixed unary/function/subquery/binary height-1000 expression must parse");
5681 HEIGHT_WALK_VISITS.set(0);
5682 let height = normalized_ast_expr_height(&expr);
5683 let walk_visits = HEIGHT_WALK_VISITS.get();
5684 let rendered = expr.to_string();
5685 let rendered_len = rendered.len();
5686 drop(rendered);
5687 drop(expr);
5688 (height, rendered_len, walk_visits)
5689 });
5690 assert_eq!(height, MAX_PARSE_DEPTH);
5691 assert!(rendered_len > LIMIT);
5692 assert!(
5693 walk_visits <= at_limit_token_bound(LIMIT),
5694 "heap-backed cached-height walk must remain linear: {walk_visits} visits"
5695 );
5696
5697 let over_limit = mixed_deep_expression(LIMIT + 1);
5698 let error = on_one_mib_stack(move || {
5699 parse_expr(&over_limit).expect_err("mixed height-1001 expression must fail closed")
5700 });
5701 assert_eq!(
5702 error.kind,
5703 ParseErrorKind::ExpressionTooDeep {
5704 max: MAX_PARSE_DEPTH
5705 }
5706 );
5707 }
5708
5709 #[test]
5710 fn test_mixed_select_shape_round_trips_and_drops_on_one_mib_stack_at_exact_limit() {
5711 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5712 let base = "CASE WHEN 5 BETWEEN 1 AND 9 THEN 3 IN (WITH c AS (SELECT x FROM t) SELECT sum(c.x) OVER (PARTITION BY u.p ORDER BY u.q ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) FROM c INNER JOIN u ON c.x = u.x WHERE u.x > 0 GROUP BY c.x HAVING count(*) > 0 ORDER BY c.x LIMIT 1) ELSE 0 END";
5713 let at_limit = wrap_function_to_height(base, LIMIT);
5714 let (height, rendered_len) = on_one_mib_stack(move || {
5715 let expr = parse_expr(&at_limit)
5716 .expect("mixed CASE/BETWEEN/IN/CTE/JOIN/window height-1000 expression must parse");
5717 assert_eq!(normalized_ast_expr_height(&expr), MAX_PARSE_DEPTH);
5718 let rendered = expr.to_string();
5719 let reparsed =
5720 parse_expr(&rendered).expect("formatted mixed height-1000 expression must reparse");
5721 assert_eq!(normalized_ast_expr_height(&reparsed), MAX_PARSE_DEPTH);
5722 let rerendered = reparsed.to_string();
5723 assert_eq!(rendered, rerendered);
5724 let rendered_len = rendered.len();
5725 drop(rerendered);
5726 drop(reparsed);
5727 drop(rendered);
5728 drop(expr);
5729 (MAX_PARSE_DEPTH, rendered_len)
5730 });
5731 assert_eq!(height, MAX_PARSE_DEPTH);
5732 assert!(rendered_len > LIMIT);
5733
5734 let over_limit = wrap_function_to_height(base, LIMIT + 1);
5735 let error = on_one_mib_stack(move || {
5736 parse_expr(&over_limit).expect_err("mixed height-1001 expression must fail closed")
5737 });
5738 assert_eq!(
5739 error.kind,
5740 ParseErrorKind::ExpressionTooDeep {
5741 max: MAX_PARSE_DEPTH
5742 }
5743 );
5744 assert_eq!(
5745 error.message,
5746 format!(
5747 "Expression tree is too large (maximum depth {})",
5748 MAX_PARSE_DEPTH
5749 )
5750 );
5751 }
5752
5753 const fn at_limit_token_bound(height: usize) -> usize {
5754 height * 12
5755 }
5756
5757 #[test]
5758 fn test_998_wrapper_aggregate_filter_machine_steps_are_linear() {
5759 const WRAPPERS: usize = 998;
5760 let sql = format!(
5761 "{}1{} FILTER (WHERE 1)",
5762 "abs(".repeat(WRAPPERS),
5763 ")".repeat(WRAPPERS)
5764 );
5765 let token_count = Parser::from_sql(&sql).tokens.len();
5766 PARSE_MACHINE_STEPS.set(0);
5767 let expr = parse_expr(&sql).expect("near-match aggregate FILTER expression must parse");
5768 let visits = PARSE_MACHINE_STEPS.get();
5769 assert!(
5770 visits <= token_count.saturating_mul(8),
5771 "explicit parser machine revisited tokens superlinearly: {visits} steps for {token_count} tokens"
5772 );
5773 drop(expr);
5774 }
5775
5776 #[test]
5777 fn test_aggregate_order_by_auxiliary_roots_do_not_rescan_descendants() {
5778 let mut sql = "1".to_owned();
5779 for _ in 0..64 {
5780 sql = format!("f(0 ORDER BY {sql})");
5781 }
5782
5783 HEIGHT_WALK_VISITS.set(0);
5784 parse_expr(&sql).expect("nested aggregate ORDER BY expression must parse");
5785 assert_eq!(
5786 HEIGHT_WALK_VISITS.get(),
5787 0,
5788 "independent aggregate ORDER BY roots must not walk completed ASTs"
5789 );
5790 }
5791
5792 #[test]
5793 fn test_subquery_height_contract_matches_sqlite_height_of_select_fields() {
5794 for (sql, expected_height) in [
5795 ("SELECT 1 + 2 + 3", 3),
5796 ("SELECT 0 WHERE 1 + 2 + 3", 3),
5797 ("SELECT 0 GROUP BY 1 + 2 + 3 HAVING 1 + 2 + 3", 3),
5798 (
5799 "SELECT 0 ORDER BY 1 + 2 + 3 LIMIT 1 + 2 + 3 OFFSET 1 + 2 + 3",
5800 4,
5801 ),
5802 ("VALUES (1 + 2 + 3)", 3),
5803 ("SELECT 0 UNION ALL SELECT 1 + 2 + 3", 3),
5804 ] {
5805 assert_eq!(
5806 parsed_select_height(sql),
5807 expected_height,
5808 "official SELECT expression-height field was omitted: {sql}"
5809 );
5810 }
5811
5812 for sql in [
5813 "WITH c AS (SELECT 1 + 2 + 3) SELECT 0",
5814 "SELECT 0 FROM (SELECT 1 + 2 + 3)",
5815 "SELECT 0 FROM json_each(1 + 2 + 3)",
5816 "SELECT 0 FROM a JOIN b ON 1 + 2 + 3",
5817 "SELECT 0 WINDOW w AS (PARTITION BY 1 + 2 + 3 ORDER BY 1 + 2 + 3)",
5818 ] {
5819 assert_eq!(
5820 parsed_select_height(sql),
5821 1,
5822 "independent SQL root was incorrectly charged to its enclosing SELECT: {sql}"
5823 );
5824 }
5825 }
5826
5827 #[test]
5828 fn test_cached_height_matches_sqlite_grammar_rewrites() {
5829 for (sql, expected_height) in [
5830 ("NOT 1", 2),
5831 ("NOT EXISTS (SELECT 1)", 3),
5832 ("1 BETWEEN 2 AND 3", 2),
5833 ("1 NOT BETWEEN 2 AND 3", 3),
5834 ("1 LIKE 2", 2),
5835 ("1 NOT LIKE 2", 3),
5836 ("1 IN ()", 1),
5837 ("1 NOT IN ()", 1),
5838 ("abs(1) IN ()", 3),
5839 ("abs(1) NOT IN ()", 3),
5840 ("1 IN (2)", 3),
5841 ("1 IN (+2)", 4),
5842 ("1 NOT IN (2)", 4),
5843 ("1 IN (2, 3)", 2),
5844 ("1 NOT IN (2, 3)", 3),
5845 ("1 IN (SELECT 1 + 2)", 3),
5846 ("1 IN ((SELECT 1 + 2))", 3),
5847 ("(1, 2) IN ((3, 4))", 2),
5848 ("+1", 2),
5849 ("++1", 2),
5850 ("-+1", 2),
5851 ("(1 + 2 + 3, 4)", 1),
5852 ("(1 + 2 + 3, 4) + 5", 2),
5853 ] {
5854 assert_eq!(
5855 parsed_expr_height(sql),
5856 expected_height,
5857 "cached grammar height mismatch: {sql}"
5858 );
5859 }
5860 }
5861
5862 #[test]
5863 fn test_function_cached_height_excludes_auxiliary_expression_roots() {
5864 for (sql, expected_height) in [
5865 ("sum(1 + 2 + 3)", 4),
5866 ("sum(1 ORDER BY 1 + 2 + 3)", 2),
5867 ("sum(1) FILTER (WHERE 1 + 2 + 3)", 2),
5868 ("sum(1) OVER (ORDER BY 1 + 2 + 3)", 2),
5869 (
5870 "sum(1 ORDER BY 1 + 2 + 3) FILTER (WHERE 1 + 2 + 3) \
5871 OVER (ORDER BY 1 + 2 + 3)",
5872 2,
5873 ),
5874 ] {
5875 assert_eq!(
5876 parsed_expr_height(sql),
5877 expected_height,
5878 "auxiliary root leaked into the aggregate argument height: {sql}"
5879 );
5880 }
5881 }
5882
5883 #[test]
5884 fn test_function_auxiliary_roots_have_independent_1000_1001_boundaries() {
5885 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5886 let at_limit = repeated_infix_expression(LIMIT, " + ");
5887 let over_limit = repeated_infix_expression(LIMIT + 1, " + ");
5888 for sql in [
5889 format!("sum(1) FILTER (WHERE {at_limit})"),
5890 format!("row_number() OVER (ORDER BY {at_limit})"),
5891 format!("group_concat(1 ORDER BY {at_limit})"),
5892 ] {
5893 parse_expr(&sql).expect("height-1000 auxiliary root must remain independently valid");
5894 }
5895 for sql in [
5896 format!("sum(1) FILTER (WHERE {over_limit})"),
5897 format!("row_number() OVER (ORDER BY {over_limit})"),
5898 format!("group_concat(1 ORDER BY {over_limit})"),
5899 ] {
5900 assert_expression_depth_error(&sql);
5901 }
5902 }
5903
5904 #[test]
5905 fn test_select_auxiliary_roots_have_independent_1000_1001_boundaries() {
5906 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5907 let at_limit = repeated_infix_expression(LIMIT, " + ");
5908 let over_limit = repeated_infix_expression(LIMIT + 1, " + ");
5909 for sql in [
5910 format!("(WITH c AS (SELECT {at_limit}) SELECT 0)"),
5911 format!("(SELECT 0 FROM (SELECT {at_limit}))"),
5912 format!("(SELECT 0 FROM json_each({at_limit}))"),
5913 format!("(SELECT 0 FROM a JOIN b ON {at_limit})"),
5914 format!("(SELECT 0 WINDOW w AS (ORDER BY {at_limit}))"),
5915 ] {
5916 parse_expr(&sql).expect("height-1000 independent SELECT root must remain valid");
5917 }
5918 for sql in [
5919 format!("(WITH c AS (SELECT {over_limit}) SELECT 0)"),
5920 format!("(SELECT 0 FROM (SELECT {over_limit}))"),
5921 format!("(SELECT 0 FROM json_each({over_limit}))"),
5922 format!("(SELECT 0 FROM a JOIN b ON {over_limit})"),
5923 format!("(SELECT 0 WINDOW w AS (ORDER BY {over_limit}))"),
5924 ] {
5925 assert_expression_depth_error(&sql);
5926 }
5927 }
5928
5929 #[test]
5930 fn test_nested_subquery_height_is_threaded_without_ast_rescans() {
5931 let sql = scalar_subquery_expression(63);
5932 HEIGHT_WALK_VISITS.set(0);
5933 parse_expr(&sql).expect("tracked nested scalar-subquery height must parse");
5934 assert_eq!(
5935 HEIGHT_WALK_VISITS.get(),
5936 0,
5937 "nested subqueries must return tracked SELECT height in O(1) per parent"
5938 );
5939 }
5940
5941 #[test]
5942 fn test_subquery_height_contract_exact_1000_1001_boundary() {
5943 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
5944 let inner_at_limit = repeated_infix_expression(LIMIT - 1, " + ");
5945 for sql in [
5946 format!("(SELECT {inner_at_limit})"),
5947 format!("EXISTS (SELECT {inner_at_limit})"),
5948 format!("1 IN (SELECT {inner_at_limit})"),
5949 ] {
5950 parse_expr(&sql).expect("height-999 SELECT under one expression node must be accepted");
5951 }
5952
5953 let inner_over_limit = repeated_infix_expression(LIMIT, " + ");
5954 for sql in [
5955 format!("(SELECT {inner_over_limit})"),
5956 format!("EXISTS (SELECT {inner_over_limit})"),
5957 format!("1 IN (SELECT {inner_over_limit})"),
5958 ] {
5959 assert_expression_depth_error(&sql);
5960 }
5961 }
5962
5963 #[test]
5966 fn test_not_lower_precedence_than_comparison() {
5967 let expr = parse("NOT x = y");
5969 match &expr {
5970 Expr::UnaryOp {
5971 op: UnaryOp::Not,
5972 expr: inner,
5973 ..
5974 } => match inner.as_ref() {
5975 Expr::BinaryOp {
5976 op: BinaryOp::Eq, ..
5977 } => {}
5978 other => unreachable!("expected Eq inside NOT, got {other:?}"),
5979 },
5980 other => unreachable!("expected NOT(Eq), got {other:?}"),
5981 }
5982 }
5983
5984 #[test]
5985 fn test_unary_binds_tighter_than_collate() {
5986 let expr = parse("-x COLLATE NOCASE");
5988 match &expr {
5989 Expr::Collate {
5990 expr: inner,
5991 collation,
5992 ..
5993 } => {
5994 assert_eq!(collation, "NOCASE");
5995 assert!(matches!(
5996 inner.as_ref(),
5997 Expr::UnaryOp {
5998 op: UnaryOp::Negate,
5999 ..
6000 }
6001 ));
6002 }
6003 other => unreachable!("expected COLLATE(Negate), got {other:?}"),
6004 }
6005 }
6006
6007 #[test]
6008 fn test_arithmetic_precedence() {
6009 let expr = parse("1 + 2 * 3");
6011 match &expr {
6012 Expr::BinaryOp {
6013 op: BinaryOp::Add,
6014 left,
6015 right,
6016 ..
6017 } => {
6018 assert!(matches!(
6019 left.as_ref(),
6020 Expr::Literal(Literal::Integer(1), _)
6021 ));
6022 assert!(matches!(
6023 right.as_ref(),
6024 Expr::BinaryOp {
6025 op: BinaryOp::Multiply,
6026 ..
6027 }
6028 ));
6029 }
6030 other => unreachable!("expected Add(1, Mul(2,3)), got {other:?}"),
6031 }
6032 }
6033
6034 #[test]
6035 fn test_and_higher_than_or() {
6036 let expr = parse("a OR b AND c");
6038 match &expr {
6039 Expr::BinaryOp {
6040 op: BinaryOp::Or,
6041 right,
6042 ..
6043 } => {
6044 assert!(matches!(
6045 right.as_ref(),
6046 Expr::BinaryOp {
6047 op: BinaryOp::And,
6048 ..
6049 }
6050 ));
6051 }
6052 other => unreachable!("expected Or(a, And(b,c)), got {other:?}"),
6053 }
6054 }
6055
6056 #[test]
6059 fn test_cast_expression() {
6060 let expr = parse("CAST(42 AS INTEGER)");
6061 match &expr {
6062 Expr::Cast {
6063 expr: inner,
6064 type_name,
6065 ..
6066 } => {
6067 assert!(matches!(
6068 inner.as_ref(),
6069 Expr::Literal(Literal::Integer(42), _)
6070 ));
6071 assert_eq!(type_name.name, "INTEGER");
6072 }
6073 other => unreachable!("expected Cast, got {other:?}"),
6074 }
6075 }
6076
6077 #[test]
6078 fn test_cast_float_argument() {
6079 let expr = parse("CAST(x AS DECIMAL(10.5, -2.5))");
6081 match &expr {
6082 Expr::Cast { type_name, .. } => {
6083 assert_eq!(type_name.name, "DECIMAL");
6084 assert_eq!(type_name.arg1.as_deref(), Some("10.5"));
6085 assert_eq!(type_name.arg2.as_deref(), Some("-2.5"));
6086 }
6087 other => unreachable!("expected Cast with float args, got {other:?}"),
6088 }
6089 }
6090
6091 #[test]
6092 fn test_cast_signed_args() {
6093 let expr = parse("CAST(x AS NUMERIC(+5, -5))");
6095 match &expr {
6096 Expr::Cast { type_name, .. } => {
6097 assert_eq!(type_name.name, "NUMERIC");
6098 assert_eq!(type_name.arg1.as_deref(), Some("+5"));
6099 assert_eq!(type_name.arg2.as_deref(), Some("-5"));
6100 }
6101 other => unreachable!("expected Cast with signed args, got {other:?}"),
6102 }
6103 }
6104
6105 #[test]
6108 fn test_case_when_simple() {
6109 let expr = parse(
6110 "CASE x WHEN 1 THEN 'one' WHEN 2 THEN 'two' \
6111 ELSE 'other' END",
6112 );
6113 match &expr {
6114 Expr::Case {
6115 operand: Some(op),
6116 whens,
6117 else_expr: Some(_),
6118 ..
6119 } => {
6120 assert!(matches!(op.as_ref(), Expr::Column(..)));
6121 assert_eq!(whens.len(), 2);
6122 }
6123 other => unreachable!("expected simple CASE, got {other:?}"),
6124 }
6125 }
6126
6127 #[test]
6128 fn test_case_when_searched() {
6129 let expr = parse(
6130 "CASE WHEN x > 0 THEN 'pos' WHEN x < 0 THEN 'neg' \
6131 ELSE 'zero' END",
6132 );
6133 match &expr {
6134 Expr::Case {
6135 operand: None,
6136 whens,
6137 else_expr: Some(_),
6138 ..
6139 } => {
6140 assert_eq!(whens.len(), 2);
6141 assert!(matches!(
6142 &whens[0].0,
6143 Expr::BinaryOp {
6144 op: BinaryOp::Gt,
6145 ..
6146 }
6147 ));
6148 }
6149 other => unreachable!("expected searched CASE, got {other:?}"),
6150 }
6151 }
6152
6153 #[test]
6156 fn test_exists_subquery() {
6157 let expr = parse("EXISTS (SELECT 1)");
6158 assert!(matches!(expr, Expr::Exists { not: false, .. }));
6159 }
6160
6161 #[test]
6162 fn test_not_exists_subquery() {
6163 let expr = parse("NOT EXISTS (SELECT 1)");
6164 assert!(matches!(expr, Expr::Exists { not: true, .. }));
6165 }
6166
6167 #[test]
6168 fn test_exists_subquery_supports_qualified_table_with_alias() {
6169 let expr = parse("EXISTS (SELECT 1 FROM main.users AS u WHERE u.id = 1)");
6170 match expr {
6171 Expr::Exists { subquery, .. } => match subquery.body.select {
6172 SelectCore::Select {
6173 from: Some(from), ..
6174 } => match from.source {
6175 TableOrSubquery::Table { name, alias, .. } => {
6176 assert_eq!(name.schema.as_deref(), Some("main"));
6177 assert_eq!(name.name, "users");
6178 assert_eq!(alias.as_deref(), Some("u"));
6179 }
6180 other => unreachable!("expected table source, got {other:?}"),
6181 },
6182 other => unreachable!("expected SELECT core with FROM, got {other:?}"),
6183 },
6184 other => unreachable!("expected EXISTS subquery, got {other:?}"),
6185 }
6186 }
6187
6188 #[test]
6191 fn test_in_expr_list() {
6192 let expr = parse("x IN (1, 2, 3)");
6193 match &expr {
6194 Expr::In {
6195 not: false,
6196 set: InSet::List(items),
6197 ..
6198 } => assert_eq!(items.len(), 3),
6199 other => unreachable!("expected IN list, got {other:?}"),
6200 }
6201 }
6202
6203 #[test]
6204 fn test_explicit_row_value_in_list_rejects_mismatched_element_arities() {
6205 for (sql, expected_message) in [
6206 (
6207 "(a, b, c) IN ((1, 2))",
6208 "IN(...) element has 2 terms - expected 3",
6209 ),
6210 (
6211 "(a, b) IN ((1, 2, 3))",
6212 "IN(...) element has 3 terms - expected 2",
6213 ),
6214 ("(a, b) IN (1)", "IN(...) element has 1 term - expected 2"),
6215 (
6216 "(a, b) IN ((1, 2), 3)",
6217 "IN(...) element has 1 term - expected 2",
6218 ),
6219 (
6220 "(a, b) NOT IN ((1, 2), (3, 4, 5))",
6221 "IN(...) element has 3 terms - expected 2",
6222 ),
6223 (
6224 "0 AND (a, b) IN (1)",
6225 "IN(...) element has 1 term - expected 2",
6226 ),
6227 (
6228 "(a, b) IN (+(SELECT 1, 2))",
6229 "IN(...) element has 1 term - expected 2",
6230 ),
6231 (
6232 "(a, b) IN ((SELECT 1), (SELECT 2))",
6233 "IN(...) element has 1 term - expected 2",
6234 ),
6235 ] {
6236 let error = parse_expr(sql).expect_err("mismatched vector IN arity must fail parsing");
6237 assert_eq!(
6238 error.kind,
6239 ParseErrorKind::Syntax,
6240 "unexpected kind for `{sql}`"
6241 );
6242 assert_eq!(
6243 error.message, expected_message,
6244 "unexpected error for `{sql}`"
6245 );
6246 }
6247 }
6248
6249 #[test]
6250 fn test_subquery_lhs_defers_in_list_arity_to_semantic_resolution() {
6251 for sql in [
6252 "(SELECT 1, 2) IN (1)",
6253 "(SELECT 1, 2) IN ((1, 2, 3))",
6254 "(VALUES (1, 2, 3)) IN ((1, 2))",
6255 "(SELECT 1, 2 UNION ALL SELECT 3, 4) NOT IN (5)",
6256 "0 AND (SELECT 1, 2) IN (1)",
6257 "(SELECT 1, 2) IN (nosuch_vector_function())",
6258 ] {
6259 let expr = parse_expr(sql).unwrap_or_else(|error| {
6260 panic!("subquery-expression IN semantics must be deferred for `{sql}`: {error}")
6261 });
6262 assert!(
6263 matches!(expr, Expr::In { .. } | Expr::BinaryOp { .. }),
6264 "unexpected AST for `{sql}`"
6265 );
6266 }
6267 }
6268
6269 #[test]
6270 fn test_vector_in_list_accepts_matching_empty_and_singleton_subquery_forms() {
6271 for sql in [
6272 "(a, b) IN ((1, 2), (3, 4))",
6273 "(a, b) NOT IN ((1, 2), (3, 4))",
6274 "(a, b) IN ()",
6275 "(a, b) IN ((SELECT 1, 2))",
6276 "(a, b) IN ((SELECT 1))",
6277 "(a, b) IN ((SELECT 1, 2, 3))",
6278 "(SELECT 1, 2) IN ((1, 2), (3, 4))",
6279 "(VALUES (1, 2), (3, 4)) NOT IN ((1, 2))",
6280 "(SELECT 1, 2 UNION ALL SELECT 3, 4) IN ((1, 2))",
6281 "(SELECT * FROM t) IN (1)",
6283 "(SELECT t.* FROM t) IN ((1, 2, 3))",
6284 "(SELECT 1, 2) IN ((SELECT 1))",
6286 "(SELECT 1, 2) IN (SELECT 1)",
6287 ] {
6288 let expr = parse_expr(sql).unwrap_or_else(|error| {
6289 panic!("matching vector IN list must parse for `{sql}`: {error}")
6290 });
6291 assert!(
6292 matches!(expr, Expr::In { .. }),
6293 "unexpected AST for `{sql}`"
6294 );
6295 }
6296 }
6297
6298 #[test]
6299 fn test_vector_in_list_trailing_comma_syntax_error_precedes_arity() {
6300 let error = parse_expr("(a, b) IN (1,)")
6301 .expect_err("a trailing comma in an IN list must fail parsing");
6302 assert_eq!(error.kind, ParseErrorKind::Syntax);
6303 assert_eq!(error.message, "unexpected token in expression: RightParen");
6304 }
6305
6306 #[test]
6307 fn test_statement_parsers_reject_vector_in_list_arity_mismatches() {
6308 for (sql, expected_message) in [
6309 (
6310 "SELECT (a, b) IN (1) FROM t",
6311 "IN(...) element has 1 term - expected 2",
6312 ),
6313 (
6314 "UPDATE t SET flag = (a, b) IN ((1, 2, 3))",
6315 "IN(...) element has 3 terms - expected 2",
6316 ),
6317 (
6318 "DELETE FROM t WHERE (a, b) NOT IN ((1, 2), 3)",
6319 "IN(...) element has 1 term - expected 2",
6320 ),
6321 ] {
6322 let error = Parser::from_sql(sql)
6323 .parse_statement()
6324 .expect_err("statement parser must reject mismatched vector IN arity");
6325 assert_eq!(
6326 error.kind,
6327 ParseErrorKind::Syntax,
6328 "unexpected kind for `{sql}`"
6329 );
6330 assert_eq!(
6331 error.message, expected_message,
6332 "unexpected error for `{sql}`"
6333 );
6334 }
6335 }
6336
6337 #[test]
6338 fn test_statement_parsers_defer_subquery_in_list_arity() {
6339 for sql in [
6340 "SELECT (SELECT 1, 2) IN (1)",
6341 "UPDATE t SET flag = (SELECT 1, 2) IN ((1, 2, 3))",
6342 "DELETE FROM t WHERE 0 AND (SELECT 1, 2) NOT IN ((1, 2), 3)",
6343 ] {
6344 Parser::from_sql(sql)
6345 .parse_statement()
6346 .unwrap_or_else(|error| {
6347 panic!("statement semantics must be deferred for `{sql}`: {error}")
6348 });
6349 }
6350 }
6351
6352 #[test]
6353 fn test_in_subquery() {
6354 let expr = parse("x IN (SELECT y FROM t)");
6355 assert!(matches!(
6356 expr,
6357 Expr::In {
6358 not: false,
6359 set: InSet::Subquery(_),
6360 ..
6361 }
6362 ));
6363 }
6364
6365 #[test]
6366 fn test_in_subquery_with_order_by_and_limit() {
6367 let expr =
6369 parse("id NOT IN (SELECT id FROM search_recipes ORDER BY updated_ts DESC LIMIT 5)");
6370 match &expr {
6371 Expr::In {
6372 not: true,
6373 set: InSet::Subquery(stmt),
6374 ..
6375 } => {
6376 assert_eq!(stmt.order_by.len(), 1, "ORDER BY should be parsed");
6377 assert!(stmt.limit.is_some(), "LIMIT should be parsed");
6378 }
6379 other => unreachable!("expected NOT IN subquery, got {other:?}"),
6380 }
6381 }
6382
6383 #[test]
6384 fn test_in_subquery_supports_group_by_and_having() {
6385 let expr = parse("x IN (SELECT y FROM t GROUP BY y HAVING COUNT(*) > 1)");
6386 match expr {
6387 Expr::In {
6388 set: InSet::Subquery(stmt),
6389 ..
6390 } => match stmt.body.select {
6391 SelectCore::Select {
6392 group_by, having, ..
6393 } => {
6394 assert_eq!(group_by.len(), 1, "GROUP BY should be parsed");
6395 assert!(having.is_some(), "HAVING should be parsed");
6396 }
6397 SelectCore::Values(_) => unreachable!("expected SELECT core"),
6398 },
6399 other => unreachable!("expected IN subquery, got {other:?}"),
6400 }
6401 }
6402
6403 #[test]
6404 fn test_not_in() {
6405 let expr = parse("x NOT IN (1, 2)");
6406 assert!(matches!(expr, Expr::In { not: true, .. }));
6407 }
6408
6409 #[test]
6410 fn test_in_table_name() {
6411 let expr = parse("x IN t");
6412 assert!(matches!(
6413 expr,
6414 Expr::In {
6415 not: false,
6416 set: InSet::Table(_),
6417 ..
6418 }
6419 ));
6420 }
6421
6422 #[test]
6423 fn test_not_in_table_name() {
6424 let expr = parse("x NOT IN t");
6425 assert!(matches!(
6426 expr,
6427 Expr::In {
6428 not: true,
6429 set: InSet::Table(_),
6430 ..
6431 }
6432 ));
6433 }
6434
6435 #[test]
6436 fn test_in_schema_table_name() {
6437 let expr = parse("x IN main.t");
6438 match expr {
6439 Expr::In {
6440 set: InSet::Table(name),
6441 ..
6442 } => {
6443 assert_eq!(name.schema.as_deref(), Some("main"));
6444 assert_eq!(name.name, "t");
6445 }
6446 other => unreachable!("expected IN table form, got {other:?}"),
6447 }
6448 }
6449
6450 #[test]
6453 fn test_between_and() {
6454 let expr = parse("x BETWEEN 1 AND 10");
6455 assert!(matches!(expr, Expr::Between { not: false, .. }));
6456 }
6457
6458 #[test]
6459 fn test_not_between() {
6460 let expr = parse("x NOT BETWEEN 1 AND 10");
6461 assert!(matches!(expr, Expr::Between { not: true, .. }));
6462 }
6463
6464 #[test]
6465 fn test_between_does_not_consume_outer_and() {
6466 let expr = parse("x BETWEEN 1 AND 10 AND y = 1");
6468 match &expr {
6469 Expr::BinaryOp {
6470 op: BinaryOp::And,
6471 left,
6472 ..
6473 } => assert!(matches!(left.as_ref(), Expr::Between { .. })),
6474 other => unreachable!("expected AND(BETWEEN, Eq), got {other:?}"),
6475 }
6476 }
6477
6478 #[test]
6481 fn test_like_pattern() {
6482 let expr = parse("name LIKE '%foo%'");
6483 assert!(matches!(
6484 expr,
6485 Expr::Like {
6486 op: LikeOp::Like,
6487 not: false,
6488 escape: None,
6489 ..
6490 }
6491 ));
6492 }
6493
6494 #[test]
6495 fn test_like_escape() {
6496 let expr = parse("name LIKE '%\\%%' ESCAPE '\\'");
6497 assert!(matches!(
6498 expr,
6499 Expr::Like {
6500 op: LikeOp::Like,
6501 escape: Some(_),
6502 ..
6503 }
6504 ));
6505 }
6506
6507 #[test]
6508 fn test_glob_pattern() {
6509 let expr = parse("path GLOB '*.rs'");
6510 assert!(matches!(
6511 expr,
6512 Expr::Like {
6513 op: LikeOp::Glob,
6514 not: false,
6515 ..
6516 }
6517 ));
6518 }
6519
6520 #[test]
6521 fn test_glob_character_class() {
6522 let expr = parse("name GLOB '[a-z]*'");
6523 match &expr {
6524 Expr::Like {
6525 op: LikeOp::Glob,
6526 pattern,
6527 ..
6528 } => assert!(matches!(
6529 pattern.as_ref(),
6530 Expr::Literal(Literal::String(s), _) if s == "[a-z]*"
6531 )),
6532 other => unreachable!("expected GLOB, got {other:?}"),
6533 }
6534 }
6535
6536 #[test]
6539 fn test_collate_override() {
6540 let expr = parse("name COLLATE NOCASE");
6541 match &expr {
6542 Expr::Collate { collation, .. } => {
6543 assert_eq!(collation, "NOCASE");
6544 }
6545 other => unreachable!("expected COLLATE, got {other:?}"),
6546 }
6547 }
6548
6549 #[test]
6552 fn test_json_arrow_operator() {
6553 let expr = parse("data -> 'key'");
6554 assert!(matches!(
6555 expr,
6556 Expr::JsonAccess {
6557 arrow: JsonArrow::Arrow,
6558 ..
6559 }
6560 ));
6561 }
6562
6563 #[test]
6564 fn test_json_double_arrow_operator() {
6565 let expr = parse("data ->> 'key'");
6566 assert!(matches!(
6567 expr,
6568 Expr::JsonAccess {
6569 arrow: JsonArrow::DoubleArrow,
6570 ..
6571 }
6572 ));
6573 }
6574
6575 #[test]
6578 fn test_is_null() {
6579 assert!(matches!(
6580 parse("42"),
6581 Expr::Literal(Literal::Integer(42), _)
6582 ));
6583 assert!(matches!(parse("3.14"), Expr::Literal(Literal::Float(_), _)));
6584 assert!(matches!(
6585 parse("'hello'"),
6586 Expr::Literal(Literal::String(_), _)
6587 ));
6588 assert!(matches!(parse("NULL"), Expr::Literal(Literal::Null, _)));
6589 assert!(matches!(parse("TRUE"), Expr::Literal(Literal::True, _)));
6590 assert!(matches!(parse("FALSE"), Expr::Literal(Literal::False, _)));
6591 }
6592
6593 #[test]
6600 fn test_isnull_eq_isnull_unparenthesized_left_associative() {
6601 let expr = parse("a IS NULL = b IS NULL");
6602 match &expr {
6603 Expr::IsNull {
6604 expr: inner,
6605 not: false,
6606 ..
6607 } => match inner.as_ref() {
6608 Expr::BinaryOp {
6609 op: BinaryOp::Eq,
6610 left,
6611 right,
6612 ..
6613 } => {
6614 assert!(
6615 matches!(left.as_ref(), Expr::IsNull { not: false, .. }),
6616 "expected (a IS NULL) on the left, got {left:?}"
6617 );
6618 assert!(
6619 matches!(right.as_ref(), Expr::Column(..)),
6620 "expected bare column b on the right, got {right:?}"
6621 );
6622 }
6623 other => unreachable!("expected Eq inside IsNull, got {other:?}"),
6624 },
6625 other => unreachable!("expected IsNull(Eq(IsNull(a), b)), got {other:?}"),
6626 }
6627 }
6628
6629 #[test]
6634 fn test_isnull_eq_isnull_parenthesized_round_trip() {
6635 let assert_shape = |expr: &Expr| match expr {
6636 Expr::BinaryOp {
6637 op: BinaryOp::Eq,
6638 left,
6639 right,
6640 ..
6641 } => {
6642 assert!(
6643 matches!(left.as_ref(), Expr::IsNull { not: false, .. }),
6644 "expected IsNull on the left, got {left:?}"
6645 );
6646 assert!(
6647 matches!(right.as_ref(), Expr::IsNull { not: false, .. }),
6648 "expected IsNull on the right, got {right:?}"
6649 );
6650 }
6651 other => unreachable!("expected Eq(IsNull, IsNull), got {other:?}"),
6652 };
6653 let expr = parse("(a IS NULL) = (b IS NULL)");
6654 assert_shape(&expr);
6655 let rendered = expr.to_string();
6656 assert_eq!(rendered, "a IS NULL = (b IS NULL)");
6657 let reparsed = parse(&rendered);
6658 assert_shape(&reparsed);
6659 assert_eq!(reparsed.to_string(), rendered, "round-trip not idempotent");
6660 }
6661
6662 #[test]
6667 fn test_is_null_followed_by_tighter_operator_binds_to_null() {
6668 let expr = parse("1 IS NULL < 2");
6669 match &expr {
6670 Expr::BinaryOp {
6671 op: BinaryOp::Is,
6672 right,
6673 ..
6674 } => assert!(
6675 matches!(
6676 right.as_ref(),
6677 Expr::BinaryOp {
6678 op: BinaryOp::Lt,
6679 ..
6680 }
6681 ),
6682 "expected Lt(NULL, 2) on the right of IS, got {right:?}"
6683 ),
6684 other => unreachable!("expected Is(1, Lt(NULL, 2)), got {other:?}"),
6685 }
6686 }
6687
6688 #[test]
6692 fn test_is_parenthesized_null_folds_to_isnull() {
6693 assert!(matches!(
6694 parse("x IS (NULL)"),
6695 Expr::IsNull { not: false, .. }
6696 ));
6697 assert!(matches!(
6698 parse("x IS NOT (NULL)"),
6699 Expr::IsNull { not: true, .. }
6700 ));
6701 }
6702
6703 #[test]
6704 fn test_placeholders() {
6705 assert!(matches!(
6706 parse("?"),
6707 Expr::Placeholder(PlaceholderType::Anonymous, _)
6708 ));
6709 assert!(matches!(
6710 parse("?1"),
6711 Expr::Placeholder(PlaceholderType::Numbered(1), _)
6712 ));
6713 assert!(matches!(
6714 parse(":name"),
6715 Expr::Placeholder(PlaceholderType::ColonNamed(_), _)
6716 ));
6717 }
6718
6719 #[test]
6722 fn test_column_bare() {
6723 match &parse("x") {
6724 Expr::Column(
6725 ColumnRef {
6726 table: None,
6727 column,
6728 },
6729 _,
6730 ) => assert_eq!(column.as_ref(), "x"),
6731 other => unreachable!("expected bare column, got {other:?}"),
6732 }
6733 }
6734
6735 #[test]
6736 fn test_column_qualified() {
6737 match &parse("t.x") {
6738 Expr::Column(
6739 ColumnRef {
6740 table: Some(t),
6741 column,
6742 },
6743 _,
6744 ) => {
6745 assert_eq!(t.as_ref(), "t");
6746 assert_eq!(column.as_ref(), "x");
6747 }
6748 other => unreachable!("expected qualified column, got {other:?}"),
6749 }
6750 }
6751
6752 #[test]
6753 fn test_qualified_column_retains_dot_height_and_exact_boundary() {
6754 assert_eq!(parsed_expr_height("x"), 1);
6755 assert_eq!(parsed_expr_height("t.x"), 2);
6756
6757 const LIMIT: usize = MAX_PARSE_DEPTH as usize;
6758 let at_limit = format!("{}t.x", "~".repeat(LIMIT - 2));
6759 parse_expr(&at_limit).expect("998 unary nodes plus qualified column have height 1000");
6760
6761 let over_limit = format!("{}t.x", "~".repeat(LIMIT - 1));
6762 assert_expression_depth_error(&over_limit);
6763 }
6764
6765 #[test]
6768 fn test_concat_higher_than_add() {
6769 let expr = parse("a + b || c");
6771 match &expr {
6772 Expr::BinaryOp {
6773 op: BinaryOp::Add,
6774 right,
6775 ..
6776 } => assert!(matches!(
6777 right.as_ref(),
6778 Expr::BinaryOp {
6779 op: BinaryOp::Concat,
6780 ..
6781 }
6782 )),
6783 other => unreachable!("expected Add(a, Concat(b,c)), got {other:?}"),
6784 }
6785 }
6786
6787 #[test]
6790 fn test_parenthesized() {
6791 let expr = parse("(1 + 2) * 3");
6793 match &expr {
6794 Expr::BinaryOp {
6795 op: BinaryOp::Multiply,
6796 left,
6797 ..
6798 } => assert!(matches!(
6799 left.as_ref(),
6800 Expr::BinaryOp {
6801 op: BinaryOp::Add,
6802 ..
6803 }
6804 )),
6805 other => unreachable!("expected Mul(Add, 3), got {other:?}"),
6806 }
6807 }
6808
6809 #[test]
6812 fn test_is_operator() {
6813 assert!(matches!(
6814 parse("a IS b"),
6815 Expr::BinaryOp {
6816 op: BinaryOp::Is,
6817 ..
6818 }
6819 ));
6820 }
6821
6822 #[test]
6823 fn test_is_not_operator() {
6824 assert!(matches!(
6825 parse("a IS NOT b"),
6826 Expr::BinaryOp {
6827 op: BinaryOp::IsNot,
6828 ..
6829 }
6830 ));
6831 }
6832
6833 #[test]
6836 fn test_bitwise_ops() {
6837 let expr = parse("a & b | c");
6839 match &expr {
6840 Expr::BinaryOp {
6841 op: BinaryOp::BitOr,
6842 left,
6843 ..
6844 } => assert!(
6845 matches!(
6846 left.as_ref(),
6847 Expr::BinaryOp {
6848 op: BinaryOp::BitAnd,
6849 ..
6850 }
6851 ),
6852 "bitwise operators should be left-associative"
6853 ),
6854 other => unreachable!("expected BitOr(BitAnd, c), got {other:?}"),
6855 }
6856 }
6857
6858 #[test]
6859 fn test_bitnot() {
6860 assert!(matches!(
6861 parse("~x"),
6862 Expr::UnaryOp {
6863 op: UnaryOp::BitNot,
6864 ..
6865 }
6866 ));
6867 }
6868
6869 #[test]
6872 fn test_complex_where_clause() {
6873 let expr = parse("a > 1 AND b LIKE '%test%' OR NOT c IS NULL");
6874 assert!(matches!(
6875 expr,
6876 Expr::BinaryOp {
6877 op: BinaryOp::Or,
6878 ..
6879 }
6880 ));
6881 }
6882
6883 #[test]
6884 fn test_not_like_pattern() {
6885 assert!(matches!(
6886 parse("name NOT LIKE '%foo'"),
6887 Expr::Like {
6888 op: LikeOp::Like,
6889 not: true,
6890 ..
6891 }
6892 ));
6893 }
6894
6895 #[test]
6896 fn test_subquery_expr() {
6897 assert!(matches!(parse("(SELECT 1)"), Expr::Subquery(..)));
6898 }
6899
6900 #[test]
6908 fn test_pratt_level1_or_left_assoc() {
6909 let expr = parse("a OR b OR c");
6911 match &expr {
6912 Expr::BinaryOp {
6913 op: BinaryOp::Or,
6914 left,
6915 ..
6916 } => assert!(
6917 matches!(
6918 left.as_ref(),
6919 Expr::BinaryOp {
6920 op: BinaryOp::Or,
6921 ..
6922 }
6923 ),
6924 "OR should be left-associative"
6925 ),
6926 other => unreachable!("expected Or(Or(a,b), c), got {other:?}"),
6927 }
6928 }
6929
6930 #[test]
6932 fn test_pratt_level2_and_left_assoc() {
6933 let expr = parse("a AND b AND c");
6935 match &expr {
6936 Expr::BinaryOp {
6937 op: BinaryOp::And,
6938 left,
6939 ..
6940 } => assert!(
6941 matches!(
6942 left.as_ref(),
6943 Expr::BinaryOp {
6944 op: BinaryOp::And,
6945 ..
6946 }
6947 ),
6948 "AND should be left-associative"
6949 ),
6950 other => unreachable!("expected And(And(a,b), c), got {other:?}"),
6951 }
6952 }
6953
6954 #[test]
6956 fn test_pratt_level3_not_higher_than_and() {
6957 let expr = parse("NOT a AND b");
6959 match &expr {
6960 Expr::BinaryOp {
6961 op: BinaryOp::And,
6962 left,
6963 ..
6964 } => assert!(
6965 matches!(
6966 left.as_ref(),
6967 Expr::UnaryOp {
6968 op: UnaryOp::Not,
6969 ..
6970 }
6971 ),
6972 "NOT should bind tighter than AND"
6973 ),
6974 other => unreachable!("expected And(Not(a), b), got {other:?}"),
6975 }
6976 }
6977
6978 #[test]
6980 fn test_pratt_level4_equality_left_assoc() {
6981 let expr = parse("a = b != c");
6983 match &expr {
6984 Expr::BinaryOp {
6985 op: BinaryOp::Ne,
6986 left,
6987 ..
6988 } => assert!(
6989 matches!(
6990 left.as_ref(),
6991 Expr::BinaryOp {
6992 op: BinaryOp::Eq,
6993 ..
6994 }
6995 ),
6996 "equality operators should be left-associative at same level"
6997 ),
6998 other => unreachable!("expected Ne(Eq(a,b), c), got {other:?}"),
6999 }
7000 }
7001
7002 #[test]
7006 fn test_pratt_level4_vs_level5_eq_lt_boundary() {
7007 let expr = parse("a = b < c");
7010 match &expr {
7011 Expr::BinaryOp {
7012 op: BinaryOp::Eq,
7013 right,
7014 ..
7015 } => assert!(
7016 matches!(
7017 right.as_ref(),
7018 Expr::BinaryOp {
7019 op: BinaryOp::Lt,
7020 ..
7021 }
7022 ),
7023 "a = b < c MUST parse as a = (b < c): relational binds tighter"
7024 ),
7025 other => unreachable!("expected Eq(a, Lt(b,c)), got {other:?}"),
7026 }
7027 }
7028
7029 #[test]
7031 fn test_pratt_level4_vs_level5_ne_ge_boundary() {
7032 let expr = parse("a != b >= c");
7034 match &expr {
7035 Expr::BinaryOp {
7036 op: BinaryOp::Ne,
7037 right,
7038 ..
7039 } => assert!(
7040 matches!(
7041 right.as_ref(),
7042 Expr::BinaryOp {
7043 op: BinaryOp::Ge,
7044 ..
7045 }
7046 ),
7047 "a != b >= c must parse as a != (b >= c)"
7048 ),
7049 other => unreachable!("expected Ne(Ge(b,c)), got {other:?}"),
7050 }
7051 }
7052
7053 #[test]
7055 fn test_pratt_level5_relational_left_assoc() {
7056 let expr = parse("a < b >= c");
7058 match &expr {
7059 Expr::BinaryOp {
7060 op: BinaryOp::Ge,
7061 left,
7062 ..
7063 } => assert!(
7064 matches!(
7065 left.as_ref(),
7066 Expr::BinaryOp {
7067 op: BinaryOp::Lt,
7068 ..
7069 }
7070 ),
7071 "relational operators should be left-associative"
7072 ),
7073 other => unreachable!("expected Ge(Lt(a,b), c), got {other:?}"),
7074 }
7075 }
7076
7077 #[test]
7079 fn test_pratt_level6_bitwise_tighter_than_comparison() {
7080 let expr = parse("a < b & c");
7082 match &expr {
7083 Expr::BinaryOp {
7084 op: BinaryOp::Lt,
7085 right,
7086 ..
7087 } => assert!(
7088 matches!(
7089 right.as_ref(),
7090 Expr::BinaryOp {
7091 op: BinaryOp::BitAnd,
7092 ..
7093 }
7094 ),
7095 "bitwise should bind tighter than relational"
7096 ),
7097 other => unreachable!("expected Lt(a, BitAnd(b,c)), got {other:?}"),
7098 }
7099 }
7100
7101 #[test]
7103 fn test_pratt_level6_shifts_left_assoc() {
7104 let expr = parse("a << b >> c");
7106 match &expr {
7107 Expr::BinaryOp {
7108 op: BinaryOp::ShiftRight,
7109 left,
7110 ..
7111 } => assert!(
7112 matches!(
7113 left.as_ref(),
7114 Expr::BinaryOp {
7115 op: BinaryOp::ShiftLeft,
7116 ..
7117 }
7118 ),
7119 "shift operators should be left-associative"
7120 ),
7121 other => unreachable!("expected ShiftRight(ShiftLeft(a,b), c), got {other:?}"),
7122 }
7123 }
7124
7125 #[test]
7127 fn test_pratt_level7_add_sub_left_assoc() {
7128 let expr = parse("a + b - c");
7130 match &expr {
7131 Expr::BinaryOp {
7132 op: BinaryOp::Subtract,
7133 left,
7134 ..
7135 } => assert!(
7136 matches!(
7137 left.as_ref(),
7138 Expr::BinaryOp {
7139 op: BinaryOp::Add,
7140 ..
7141 }
7142 ),
7143 "add/sub should be left-associative"
7144 ),
7145 other => unreachable!("expected Sub(Add(a,b), c), got {other:?}"),
7146 }
7147 }
7148
7149 #[test]
7150 fn test_pratt_level7_add_sub_left_assoc_reverse() {
7151 let expr = parse("a - b + c");
7153 match &expr {
7154 Expr::BinaryOp {
7155 op: BinaryOp::Add,
7156 left,
7157 ..
7158 } => assert!(
7159 matches!(
7160 left.as_ref(),
7161 Expr::BinaryOp {
7162 op: BinaryOp::Subtract,
7163 ..
7164 }
7165 ),
7166 "add/sub should be left-associative"
7167 ),
7168 other => unreachable!("expected Add(Sub(a,b), c), got {other:?}"),
7169 }
7170 }
7171
7172 #[test]
7173 fn test_pratt_level9_concat_tighter_than_mul() {
7174 let expr = parse("a * b || c");
7176 match &expr {
7177 Expr::BinaryOp {
7178 op: BinaryOp::Multiply,
7179 right,
7180 ..
7181 } => assert!(
7182 matches!(
7183 right.as_ref(),
7184 Expr::BinaryOp {
7185 op: BinaryOp::Concat,
7186 ..
7187 }
7188 ),
7189 "concat should bind tighter than multiply"
7190 ),
7191 other => unreachable!("expected Mul(a, Concat(b,c)), got {other:?}"),
7192 }
7193 }
7194
7195 #[test]
7197 fn test_pratt_level8_mul_div_left_assoc() {
7198 let expr = parse("a * b / c");
7200 match &expr {
7201 Expr::BinaryOp {
7202 op: BinaryOp::Divide,
7203 left,
7204 ..
7205 } => assert!(
7206 matches!(
7207 left.as_ref(),
7208 Expr::BinaryOp {
7209 op: BinaryOp::Multiply,
7210 ..
7211 }
7212 ),
7213 "mul/div should be left-associative"
7214 ),
7215 other => unreachable!("expected Div(Mul(a,b), c), got {other:?}"),
7216 }
7217 }
7218
7219 #[test]
7220 fn test_pratt_level8_modulo() {
7221 let expr = parse("a * b % c");
7223 match &expr {
7224 Expr::BinaryOp {
7225 op: BinaryOp::Modulo,
7226 left,
7227 ..
7228 } => assert!(
7229 matches!(
7230 left.as_ref(),
7231 Expr::BinaryOp {
7232 op: BinaryOp::Multiply,
7233 ..
7234 }
7235 ),
7236 "modulo and multiply at same level, left-associative"
7237 ),
7238 other => unreachable!("expected Mod(Mul(a,b), c), got {other:?}"),
7239 }
7240 }
7241
7242 #[test]
7244 fn test_pratt_level9_concat_left_assoc() {
7245 let expr = parse("a || b || c");
7247 match &expr {
7248 Expr::BinaryOp {
7249 op: BinaryOp::Concat,
7250 left,
7251 ..
7252 } => assert!(
7253 matches!(
7254 left.as_ref(),
7255 Expr::BinaryOp {
7256 op: BinaryOp::Concat,
7257 ..
7258 }
7259 ),
7260 "concatenation should be left-associative"
7261 ),
7262 other => unreachable!("expected Concat(Concat(a,b), c), got {other:?}"),
7263 }
7264 }
7265
7266 #[test]
7267 fn test_pratt_level9_concat_left_assoc_reverse() {
7268 let expr = parse("a || b || c");
7270 match &expr {
7271 Expr::BinaryOp {
7272 op: BinaryOp::Concat,
7273 left,
7274 ..
7275 } => assert!(
7276 matches!(
7277 left.as_ref(),
7278 Expr::BinaryOp {
7279 op: BinaryOp::Concat,
7280 ..
7281 }
7282 ),
7283 "concatenation should be left-associative"
7284 ),
7285 other => unreachable!("expected Concat(Concat(a,b), c), got {other:?}"),
7286 }
7287 }
7288
7289 #[test]
7291 fn test_pratt_level10_collate_tighter_than_concat() {
7292 let expr = parse("a || b COLLATE NOCASE");
7294 match &expr {
7295 Expr::BinaryOp {
7296 op: BinaryOp::Concat,
7297 right,
7298 ..
7299 } => assert!(
7300 matches!(right.as_ref(), Expr::Collate { .. }),
7301 "COLLATE should bind tighter than concat"
7302 ),
7303 other => unreachable!("expected Concat(a, Collate(b)), got {other:?}"),
7304 }
7305 }
7306
7307 #[test]
7309 fn test_pratt_level11_unary_negate_tightest() {
7310 let expr = parse("-a * b");
7312 match &expr {
7313 Expr::BinaryOp {
7314 op: BinaryOp::Multiply,
7315 left,
7316 ..
7317 } => assert!(
7318 matches!(
7319 left.as_ref(),
7320 Expr::UnaryOp {
7321 op: UnaryOp::Negate,
7322 ..
7323 }
7324 ),
7325 "unary minus should bind tighter than multiply"
7326 ),
7327 other => unreachable!("expected Mul(Negate(a), b), got {other:?}"),
7328 }
7329 }
7330
7331 #[test]
7332 fn test_pratt_level11_bitnot_tightest() {
7333 let expr = parse("~a + b");
7335 match &expr {
7336 Expr::BinaryOp {
7337 op: BinaryOp::Add,
7338 left,
7339 ..
7340 } => assert!(
7341 matches!(
7342 left.as_ref(),
7343 Expr::UnaryOp {
7344 op: UnaryOp::BitNot,
7345 ..
7346 }
7347 ),
7348 "bitwise NOT should bind tighter than addition"
7349 ),
7350 other => unreachable!("expected Add(BitNot(a), b), got {other:?}"),
7351 }
7352 }
7353
7354 #[test]
7356 fn test_pratt_escape_not_infix_operator() {
7357 let expr = parse("a LIKE b ESCAPE c");
7359 match &expr {
7360 Expr::Like {
7361 escape: Some(esc), ..
7362 } => assert!(
7363 matches!(esc.as_ref(), Expr::Column(_, _)),
7364 "ESCAPE should be parsed as suffix of LIKE, not standalone infix"
7365 ),
7366 other => unreachable!("expected Like with escape, got {other:?}"),
7367 }
7368 }
7369
7370 #[test]
7371 fn test_pratt_escape_glob_not_infix() {
7372 let expr = parse("a GLOB b ESCAPE c");
7374 match &expr {
7375 Expr::Like {
7376 op: LikeOp::Glob,
7377 escape: Some(_),
7378 ..
7379 } => {}
7380 other => unreachable!("expected Glob with escape, got {other:?}"),
7381 }
7382 }
7383
7384 #[test]
7386 fn test_pratt_error_recovery_multiple_errors() {
7387 use crate::parser::Parser;
7388 let mut p = Parser::from_sql("SELECT +; SELECT *; SELECT 1");
7389 let (stmts, errs) = p.parse_all();
7390 assert!(
7393 !stmts.is_empty(),
7394 "should recover and parse at least one valid statement"
7395 );
7396 assert!(
7397 !errs.is_empty(),
7398 "should collect at least one error from malformed statements"
7399 );
7400 }
7401
7402 #[test]
7404 fn test_pratt_complex_mixed_all_levels() {
7405 let expr = parse("NOT a = b + c * -d OR e < f AND g LIKE h");
7408 match &expr {
7410 Expr::BinaryOp {
7411 op: BinaryOp::Or,
7412 left,
7413 right,
7414 ..
7415 } => {
7416 assert!(
7418 matches!(
7419 left.as_ref(),
7420 Expr::UnaryOp {
7421 op: UnaryOp::Not,
7422 ..
7423 }
7424 ),
7425 "left of OR should be NOT(...)"
7426 );
7427 match right.as_ref() {
7429 Expr::BinaryOp {
7430 op: BinaryOp::And,
7431 left: and_left,
7432 right: and_right,
7433 ..
7434 } => {
7435 assert!(
7436 matches!(
7437 and_left.as_ref(),
7438 Expr::BinaryOp {
7439 op: BinaryOp::Lt,
7440 ..
7441 }
7442 ),
7443 "left of AND should be Lt(e,f)"
7444 );
7445 assert!(
7446 matches!(and_right.as_ref(), Expr::Like { .. }),
7447 "right of AND should be Like(g,h)"
7448 );
7449 }
7450 other => unreachable!("expected And(Lt, Like), got {other:?}"),
7451 }
7452
7453 if let Expr::UnaryOp {
7456 expr: not_inner, ..
7457 } = left.as_ref()
7458 {
7459 if let Expr::BinaryOp {
7460 op: BinaryOp::Eq,
7461 right: eq_right,
7462 ..
7463 } = not_inner.as_ref()
7464 {
7465 if let Expr::BinaryOp {
7466 op: BinaryOp::Add,
7467 right: add_right,
7468 ..
7469 } = eq_right.as_ref()
7470 {
7471 if let Expr::BinaryOp {
7472 op: BinaryOp::Multiply,
7473 right: mul_right,
7474 ..
7475 } = add_right.as_ref()
7476 {
7477 assert!(
7478 matches!(
7479 mul_right.as_ref(),
7480 Expr::UnaryOp {
7481 op: UnaryOp::Negate,
7482 ..
7483 }
7484 ),
7485 "deepest: negate"
7486 );
7487 } else {
7488 unreachable!("expected Mul in add_right");
7489 }
7490 } else {
7491 unreachable!("expected Add in eq_right");
7492 }
7493 } else {
7494 unreachable!("expected Eq inside NOT");
7495 }
7496 }
7497 }
7498 other => unreachable!("expected Or(Not(...), And(...)), got {other:?}"),
7499 }
7500 }
7501
7502 #[test]
7504 fn test_pratt_json_same_precedence_as_concat() {
7505 let expr = parse("a || b -> c");
7507 match &expr {
7508 Expr::JsonAccess {
7509 expr: left,
7510 path: right,
7511 arrow: JsonArrow::Arrow,
7512 ..
7513 } => {
7514 assert!(
7515 matches!(
7516 left.as_ref(),
7517 Expr::BinaryOp {
7518 op: BinaryOp::Concat,
7519 ..
7520 }
7521 ),
7522 "left side should be concat expression"
7523 );
7524 assert!(
7525 matches!(right.as_ref(), Expr::Column(_, _)),
7526 "path should remain the right-hand expression"
7527 );
7528 }
7529 other => unreachable!("expected JsonAccess(Concat(a,b), c), got {other:?}"),
7530 }
7531 }
7532
7533 #[test]
7534 fn test_pratt_double_arrow_same_precedence_as_concat() {
7535 let expr = parse("a || b ->> c");
7536 assert!(
7537 matches!(
7538 expr,
7539 Expr::JsonAccess {
7540 arrow: JsonArrow::DoubleArrow,
7541 ..
7542 }
7543 ),
7544 "double-arrow should parse as JsonAccess at the same precedence level as concat"
7545 );
7546 }
7547}