surql_parser/upstream/syn/parser/

expression.rs

//! This module defines the pratt parser for operators.
use super::enter_query_recursion;
use super::mac::unexpected;
use crate::compat::types::PublicDuration;
use crate::upstream::sql::operator::{
	BindingPower, BooleanOperator, MatchesOperator, NearestNeighbor,
};
use crate::upstream::sql::{BinaryOperator, Expr, Literal, Part, PostfixOperator, PrefixOperator};
use crate::upstream::syn::error::bail;
use crate::upstream::syn::lexer::compound::Numeric;
use crate::upstream::syn::parser::mac::expected;
use crate::upstream::syn::parser::{ParseResult, Parser};
use crate::upstream::syn::token::{Span, Token, TokenKind, t};
use reblessive::Stk;
use surrealdb_types::ToSql;
impl Parser<'_> {
	/// Parse a generic expression without triggering the query depth and
	/// setting table_as_field.
	///
	/// Meant to be used when parsing an expression the first time to avoid
	/// having the depth limit be lowered unnecessarily.
	pub async fn parse_expr_start(&mut self, stk: &mut Stk) -> ParseResult<Expr> {
		self.table_as_field = true;
		self.pratt_parse_expr(stk, BindingPower::Base).await
	}
	/// Parsers a generic value.
	///
	/// A generic loose ident like `foo` in for example `foo.bar` can be two
	/// different values depending on context: a table or a field the current
	/// document. This function parses loose idents as a table, see
	/// [`parse_expr_field`] for parsing loose idents as fields
	pub async fn parse_expr_table(&mut self, stk: &mut Stk) -> ParseResult<Expr> {
		let old = self.table_as_field;
		self.table_as_field = false;
		let res = enter_query_recursion!(
			this = self => { this.pratt_parse_expr(stk, BindingPower::Base). await }
		);
		self.table_as_field = old;
		res
	}
	/// Parsers a generic value.
	///
	/// A generic loose ident like `foo` in for example `foo.bar` can be two
	/// different values depending on context: a table or a field the current
	/// document. This function parses loose idents as a field, see
	/// [`parse_expr_table`] for parsing loose idents as table
	pub async fn parse_expr_field(&mut self, stk: &mut Stk) -> ParseResult<Expr> {
		let old = self.table_as_field;
		self.table_as_field = true;
		let res = enter_query_recursion!(
			this = self => { this.pratt_parse_expr(stk, BindingPower::Base). await }
		);
		self.table_as_field = old;
		res
	}
	/// Parsers a generic value.
	///
	/// Inherits how loose identifiers are parsed from it's caller.
	pub(super) async fn parse_expr_inherit(&mut self, stk: &mut Stk) -> ParseResult<Expr> {
		enter_query_recursion!(
			this = self => { this.pratt_parse_expr(stk, BindingPower::Base). await }
		)
	}
	/// Returns the binding power of an infix operator.
	///
	/// Binding power is the opposite of precedence: a higher binding power
	/// means that a token is more like to operate directly on it's neighbours.
	/// Example `*` has a higher binding power than `-` resulting in 1 - 2 * 3
	/// being parsed as 1 - (2 * 3).
	///
	/// All operators in SurrealQL which are parsed by the functions in this
	/// module are left associative or have no defined associativity.
	fn infix_binding_power(&mut self, token: TokenKind) -> Option<BindingPower> {
		match token {
			t!("||") | t!("OR") => Some(BindingPower::Or),
			t!("&&") | t!("AND") => Some(BindingPower::And),
			t!("=") | t!("IS") | t!("==") | t!("!=") | t!("*=") | t!("?=") | t!("@") => {
				Some(BindingPower::Equality)
			}
			t!("<") => {
				if let Some(peek) = self.peek_whitespace1()
					&& let t!("-") | t!("~") | t!("->") | t!("..") = peek.kind
				{
					return None;
				}
				Some(BindingPower::Relation)
			}
			t!(">") => {
				if let Some(t!("..")) = self.peek_whitespace1().map(|x| x.kind) {
					return Some(BindingPower::Range);
				}
				Some(BindingPower::Relation)
			}
			t!("..") => Some(BindingPower::Range),
			t!("<=")
			| t!(">=")
			| t!("∋")
			| t!("CONTAINS")
			| t!("∌")
			| t!("CONTAINSNOT")
			| t!("∈")
			| t!("INSIDE")
			| t!("∉")
			| t!("NOTINSIDE")
			| t!("⊇")
			| t!("CONTAINSALL")
			| t!("⊃")
			| t!("CONTAINSANY")
			| t!("⊅")
			| t!("CONTAINSNONE")
			| t!("⊆")
			| t!("ALLINSIDE")
			| t!("⊂")
			| t!("ANYINSIDE")
			| t!("⊄")
			| t!("NONEINSIDE")
			| t!("OUTSIDE")
			| t!("INTERSECTS")
			| t!("NOT")
			| t!("IN")
			| t!("<|") => Some(BindingPower::Relation),
			t!("+") | t!("-") => Some(BindingPower::AddSub),
			t!("*") | t!("×") | t!("/") | t!("÷") | t!("%") => Some(BindingPower::MulDiv),
			t!("**") => Some(BindingPower::Power),
			t!("?:") | t!("?") => Some(BindingPower::Nullish),
			_ => None,
		}
	}
	fn prefix_binding_power(&mut self, token: TokenKind) -> Option<BindingPower> {
		match token {
			t!("!") | t!("+") | t!("-") => Some(BindingPower::Prefix),
			t!("..") => Some(BindingPower::Range),
			t!("<") => {
				if let Some(peek) = self.peek_whitespace1() {
					if peek.kind == t!("-") {
						let recover = self.last_span();
						if self.peek2().kind == TokenKind::Digits {
							self.backup_after(recover);
							return Some(BindingPower::Prefix);
						}
						return None;
					}
					if let t!("~") | t!("->") = peek.kind {
						return None;
					}
				}
				Some(BindingPower::Prefix)
			}
			_ => None,
		}
	}
	fn postfix_binding_power(&mut self, token: TokenKind) -> Option<BindingPower> {
		match token {
			t!(">") => {
				if let Some(peek) = self.peek_whitespace1()
					&& let t!("..") = peek.kind
				{
					if let Some(peek) = self.peek_whitespace2()
						&& (t!("=") == peek.kind || Self::kind_starts_expression(peek.kind))
					{
						return None;
					} else {
						return Some(BindingPower::Range);
					}
				}
				None
			}
			t!("..") => match self.peek_whitespace1().map(|x| x.kind) {
				Some(t!("=")) => None,
				Some(x) if Self::kind_starts_expression(x) => None,
				_ => Some(BindingPower::Range),
			},
			t!("(") => Some(BindingPower::Call),
			_ => None,
		}
	}
	async fn parse_prefix_op(&mut self, stk: &mut Stk, min_bp: BindingPower) -> ParseResult<Expr> {
		let token = self.peek();
		let operator = match token.kind {
			t!("+") => {
				if let Some(TokenKind::Digits) = self.peek_whitespace1().map(|x| x.kind) {
					self.pop_peek();
					let expr = match self.next_token_value::<Numeric>()? {
						Numeric::Float(f) => Expr::Literal(Literal::Float(f)),
						Numeric::Integer(i) => {
							Expr::Literal(Literal::Integer(i.into_int(self.recent_span())?))
						}
						Numeric::Decimal(d) => Expr::Literal(Literal::Decimal(d)),
						Numeric::Duration(d) => Expr::Prefix {
							op: PrefixOperator::Positive,
							expr: Box::new(Expr::Literal(Literal::Duration(PublicDuration::from(
								d,
							)))),
						},
					};
					if self.peek_continues_idiom() {
						return self
							.parse_remaining_value_idiom(stk, vec![Part::Start(expr)])
							.await;
					} else {
						return Ok(expr);
					}
				}
				self.pop_peek();
				PrefixOperator::Positive
			}
			t!("-") => {
				if let Some(TokenKind::Digits) = self.peek_whitespace1().map(|x| x.kind) {
					self.pop_peek();
					let expr = match self.next_token_value::<Numeric>()? {
						Numeric::Float(f) => Expr::Literal(Literal::Float(-f)),
						Numeric::Integer(i) => {
							Expr::Literal(Literal::Integer(i.into_neg_int(self.recent_span())?))
						}
						Numeric::Decimal(d) => Expr::Literal(Literal::Decimal(-d)),
						Numeric::Duration(d) => Expr::Prefix {
							op: PrefixOperator::Negate,
							expr: Box::new(Expr::Literal(Literal::Duration(PublicDuration::from(
								d,
							)))),
						},
					};
					if self.peek_continues_idiom() {
						return self
							.parse_remaining_value_idiom(stk, vec![Part::Start(expr)])
							.await;
					} else {
						return Ok(expr);
					}
				}
				self.pop_peek();
				PrefixOperator::Negate
			}
			t!("!") => {
				self.pop_peek();
				PrefixOperator::Not
			}
			t!("<") => {
				self.pop_peek();
				let kind = self.parse_kind(stk, token.span).await?;
				PrefixOperator::Cast(kind)
			}
			t!("..") => {
				self.pop_peek();
				if let Some(x) = self.peek_whitespace() {
					if let t!("=") = x.kind {
						self.pop_peek();
						PrefixOperator::RangeInclusive
					} else if !Self::kind_starts_prime_value(x.kind) {
						return Ok(Expr::Literal(Literal::UnboundedRange));
					} else {
						PrefixOperator::Range
					}
				} else {
					return Ok(Expr::Literal(Literal::UnboundedRange));
				}
			}
			_ => unreachable!(),
		};
		let v = stk.run(|stk| self.pratt_parse_expr(stk, min_bp)).await?;
		Ok(Expr::Prefix {
			op: operator,
			expr: Box::new(v),
		})
	}
	pub(super) fn parse_nearest_neighbor(&mut self, token: Token) -> ParseResult<NearestNeighbor> {
		let amount = self.next_token_value()?;
		let res = if self.eat(t!(",")) {
			let token = self.peek();
			match token.kind {
				TokenKind::Distance(_) => {
					let d = self.parse_distance()?;
					NearestNeighbor::K(amount, d)
				}
				TokenKind::Digits => {
					let ef = self.next_token_value()?;
					NearestNeighbor::Approximate(amount, ef)
				}
				_ => {
					bail!(
						"Unexpected token {} expected a distance of an integer", token
						.kind, @ token.span =>
						"The NN operator accepts either a distance or an EF value (integer)"
					)
				}
			}
		} else {
			NearestNeighbor::KTree(amount)
		};
		if !self.eat(t!("|")) || !self.eat_whitespace(t!(">")) {
			bail!(
				"Unexpected token `{}` expected delimiter `|>`", self.peek().kind, @ self
				.recent_span(), @ token.span => "expected this delimiter to close"
			);
		}
		Ok(res)
	}
	/// Returns if an operator has a defined associativity.
	/// For example: `a - b - c == (a - b) - c` so `-` is left associative.
	/// However `a == b == c` is not defined to be either `(a == b) == c` nor `a == (b == c)`.
	fn operator_has_associativity(operator: &BinaryOperator) -> bool {
		!matches!(
			operator,
			BinaryOperator::Equal
				| BinaryOperator::NotEqual
				| BinaryOperator::AllEqual
				| BinaryOperator::AnyEqual
				| BinaryOperator::LessThan
				| BinaryOperator::LessThanEqual
				| BinaryOperator::MoreThan
				| BinaryOperator::MoreThanEqual
				| BinaryOperator::Matches(_)
				| BinaryOperator::Contain
				| BinaryOperator::NotContain
				| BinaryOperator::ContainAll
				| BinaryOperator::ContainAny
				| BinaryOperator::ContainNone
				| BinaryOperator::Inside
				| BinaryOperator::NotInside
				| BinaryOperator::AllInside
				| BinaryOperator::AnyInside
				| BinaryOperator::NoneInside
				| BinaryOperator::Outside
				| BinaryOperator::Intersects
				| BinaryOperator::NearestNeighbor(_)
		)
	}
	fn expr_is_range(expr: &Expr) -> bool {
		match expr {
			Expr::Binary { op, .. } => {
				matches!(
					op,
					BinaryOperator::Range
						| BinaryOperator::RangeSkipInclusive
						| BinaryOperator::RangeSkip
						| BinaryOperator::RangeInclusive
				)
			}
			Expr::Prefix { op, .. } => {
				matches!(op, PrefixOperator::Range | PrefixOperator::RangeInclusive)
			}
			Expr::Postfix { op, .. } => {
				matches!(op, PostfixOperator::Range | PostfixOperator::RangeSkip)
			}
			_ => false,
		}
	}
	async fn parse_infix_op(
		&mut self,
		stk: &mut Stk,
		min_bp: BindingPower,
		lhs: Expr,
		lhs_prime: bool,
	) -> ParseResult<Expr> {
		let token = self.next();
		let operator = match token.kind {
			t!("||") | t!("OR") => BinaryOperator::Or,
			t!("&&") | t!("AND") => BinaryOperator::And,
			t!("?:") => BinaryOperator::TenaryCondition,
			t!("?") => {
				if !self.eat_whitespace(t!("?")) {
					unexpected!(self, token, "`??`")
				}
				BinaryOperator::NullCoalescing
			}
			t!("==") => BinaryOperator::ExactEqual,
			t!("!=") => BinaryOperator::NotEqual,
			t!("*=") => BinaryOperator::AllEqual,
			t!("?=") => BinaryOperator::AnyEqual,
			t!("=") => BinaryOperator::Equal,
			t!("@") => {
				let op = self.parse_matches()?;
				BinaryOperator::Matches(op)
			}
			t!("<=") => BinaryOperator::LessThanEqual,
			t!("<") => BinaryOperator::LessThan,
			t!(">=") => BinaryOperator::MoreThanEqual,
			t!("**") => BinaryOperator::Power,
			t!("+") => BinaryOperator::Add,
			t!("-") => BinaryOperator::Subtract,
			t!("*") | t!("×") => BinaryOperator::Multiply,
			t!("/") | t!("÷") => BinaryOperator::Divide,
			t!("%") => BinaryOperator::Remainder,
			t!("∋") | t!("CONTAINS") => BinaryOperator::Contain,
			t!("∌") | t!("CONTAINSNOT") => BinaryOperator::NotContain,
			t!("∈") | t!("INSIDE") => BinaryOperator::Inside,
			t!("∉") | t!("NOTINSIDE") => BinaryOperator::NotInside,
			t!("⊇") | t!("CONTAINSALL") => BinaryOperator::ContainAll,
			t!("⊃") | t!("CONTAINSANY") => BinaryOperator::ContainAny,
			t!("⊅") | t!("CONTAINSNONE") => BinaryOperator::ContainNone,
			t!("⊆") | t!("ALLINSIDE") => BinaryOperator::AllInside,
			t!("⊂") | t!("ANYINSIDE") => BinaryOperator::AnyInside,
			t!("⊄") | t!("NONEINSIDE") => BinaryOperator::NoneInside,
			t!("IS") => {
				if self.eat(t!("NOT")) {
					BinaryOperator::NotEqual
				} else {
					BinaryOperator::Equal
				}
			}
			t!("OUTSIDE") => BinaryOperator::Outside,
			t!("INTERSECTS") => BinaryOperator::Intersects,
			t!("NOT") => {
				expected!(self, t!("IN"));
				BinaryOperator::NotInside
			}
			t!("IN") => BinaryOperator::Inside,
			t!("<|") => {
				BinaryOperator::NearestNeighbor(Box::new(self.parse_nearest_neighbor(token)?))
			}
			t!(">") => {
				if let Some(t!("..")) = self.peek_whitespace().map(|x| x.kind) {
					self.pop_peek();
					if let Some(t!("=")) = self.peek_whitespace().map(|x| x.kind) {
						self.pop_peek();
						BinaryOperator::RangeSkipInclusive
					} else {
						BinaryOperator::RangeSkip
					}
				} else {
					BinaryOperator::MoreThan
				}
			}
			t!("..") => {
				if let Some(t!("=")) = self.peek_whitespace().map(|x| x.kind) {
					self.pop_peek();
					BinaryOperator::RangeInclusive
				} else {
					BinaryOperator::Range
				}
			}
			x => unreachable!("found non-operator token {x:?}"),
		};
		let rhs_covered = self.peek().kind == t!("(");
		let rhs = stk.run(|ctx| self.pratt_parse_expr(ctx, min_bp)).await?;
		let has_associatitivity = Self::operator_has_associativity(&operator);
		if !lhs_prime
			&& !has_associatitivity
			&& BindingPower::for_expr(&lhs) == BindingPower::for_binary_operator(&operator)
		{
			let span = token.span.covers(self.recent_span());
			if matches!(
				operator,
				BinaryOperator::Range
					| BinaryOperator::RangeSkipInclusive
					| BinaryOperator::RangeSkip
					| BinaryOperator::RangeInclusive
			) {
				bail!(
					"Chained range operators has no specified associativity", @ span =>
					"use parens, '()', to specify which operator must be evaluated first"
				)
			} else {
				bail!(
					"Chained relational operators have no defined associativity.", @ span
					=>
					"Use parens, '()', to specify which operator must be evaluated first"
				)
			}
		}
		if !rhs_covered
			&& !has_associatitivity
			&& BindingPower::for_expr(&rhs) == BindingPower::for_binary_operator(&operator)
		{
			let span = token.span.covers(self.recent_span());
			if matches!(
				operator,
				BinaryOperator::Range
					| BinaryOperator::RangeSkipInclusive
					| BinaryOperator::RangeSkip
					| BinaryOperator::RangeInclusive
			) {
				bail!(
					"Chained range operators have no defined associativity.", @ span =>
					"Use parens, '()', to specify which operator must be evaluated first"
				)
			} else {
				bail!(
					"Chained relational operators have no defined associativity.", @ span
					=>
					"Use parens, '()', to specify which operator must be evaluated first"
				)
			}
		}
		Ok(Expr::Binary {
			left: Box::new(lhs),
			op: operator,
			right: Box::new(rhs),
		})
	}
	fn parse_matches(&mut self) -> ParseResult<MatchesOperator> {
		let peek = self.peek();
		match peek.kind {
			TokenKind::Digits => {
				let number = self.next_token_value()?;
				let op = if self.eat(t!(",")) {
					let peek = self.next();
					let op = match peek.kind {
						t!("AND") => BooleanOperator::And,
						t!("OR") => BooleanOperator::Or,
						_ => unexpected!(self, peek, "either `AND` or `OR`"),
					};
					Some(op)
				} else {
					None
				};
				expected!(self, t!("@"));
				Ok(MatchesOperator {
					operator: op,
					rf: Some(number),
				})
			}
			t!("AND") => {
				self.pop_peek();
				expected!(self, t!("@"));
				Ok(MatchesOperator {
					operator: Some(BooleanOperator::And),
					rf: None,
				})
			}
			t!("OR") => {
				self.pop_peek();
				expected!(self, t!("@"));
				Ok(MatchesOperator {
					operator: Some(BooleanOperator::Or),
					rf: None,
				})
			}
			t!("@") => {
				self.pop_peek();
				Ok(MatchesOperator {
					operator: None,
					rf: None,
				})
			}
			_ => unexpected!(self, peek, "a match reference, operator or `@`"),
		}
	}
	async fn parse_postfix(
		&mut self,
		stk: &mut Stk,
		lhs: Expr,
		lhs_prime: bool,
	) -> ParseResult<Expr> {
		let token = self.next();
		let op = match token.kind {
			t!(">") => {
				assert!(self.eat_whitespace(t!("..")));
				if !lhs_prime && Self::expr_is_range(&lhs) {
					bail!(
						"Chaining range operators has no specified associativity", @
						token.span =>
						"use parens, '()', to specify which operator must be evaluated first"
					)
				}
				PostfixOperator::RangeSkip
			}
			t!("..") => {
				if !lhs_prime && Self::expr_is_range(&lhs) {
					bail!(
						"Chaining range operators has no specified associativity", @
						token.span =>
						"use parens, '()', to specify which operator must be evaluated first"
					)
				}
				PostfixOperator::Range
			}
			t!("(") => {
				let mut args = Vec::new();
				loop {
					if self.eat(t!(")")) {
						break;
					}
					let arg = stk.run(|ctx| self.parse_expr_inherit(ctx)).await?;
					args.push(arg);
					if !self.eat(t!(",")) {
						self.expect_closing_delimiter(t!(")"), token.span)?;
						break;
					}
				}
				PostfixOperator::Call(args)
			}
			t!(".") => {
				let name = self.parse_ident()?;
				expected!(self, t!("("));
				let mut args = Vec::new();
				loop {
					if self.eat(t!(")")) {
						break;
					}
					let arg = stk.run(|ctx| self.parse_expr_inherit(ctx)).await?;
					args.push(arg);
					if !self.eat(t!(",")) {
						self.expect_closing_delimiter(t!(")"), token.span)?;
						break;
					}
				}
				PostfixOperator::MethodCall(name, args)
			}
			x => unreachable!("found non-operator token {x:?}"),
		};
		Ok(Expr::Postfix {
			expr: Box::new(lhs),
			op,
		})
	}
	/// The pratt parsing loop.
	/// Parses expression according to binding power.
	async fn pratt_parse_expr(&mut self, stk: &mut Stk, min_bp: BindingPower) -> ParseResult<Expr> {
		let peek = self.peek();
		let (mut lhs, mut lhs_prime) = if let Some(bp) = self.prefix_binding_power(peek.kind) {
			(self.parse_prefix_op(stk, bp).await?, false)
		} else {
			(self.parse_prime_expr(stk).await?, true)
		};
		loop {
			let token = self.peek();
			if let Some(bp) = self.postfix_binding_power(token.kind) {
				if bp <= min_bp {
					break;
				}
				lhs = self.parse_postfix(stk, lhs, lhs_prime).await?;
				lhs_prime = false;
				continue;
			}
			if let t!("+=") | t!("-=") | t!("+?=") = token.kind {
				unexpected!(
					self, token, "an operator", =>
					"assignment operators are only allowed in SET and DUPLICATE KEY UPDATE clauses"
				)
			}
			let Some(bp) = self.infix_binding_power(token.kind) else {
				break;
			};
			if bp <= min_bp {
				break;
			}
			lhs = self.parse_infix_op(stk, bp, lhs, lhs_prime).await?;
			lhs_prime = false;
		}
		Ok(lhs)
	}
	pub fn reject_letless_let(expr: &Expr, span: Span) -> ParseResult<()> {
		let Expr::Binary { left, op, .. } = expr else {
			return Ok(());
		};
		let Expr::Param(p) = &**left else {
			return Ok(());
		};
		let BinaryOperator::Equal = op else {
			return Ok(());
		};
		bail!(
			"Parameter declarations without `let` are deprecated.", @ span =>
			"Replace with `let {} = ...` to keep the previous behavior.", p.to_sql()
		)
	}
}