inillucent_sql/precedence.rs
1//! The operator precedence table, as data.
2//!
3//! Invariant: precedence lives in one table that tests read, not in the shape
4//! of a hand-written descent. A table can be checked against the published
5//! order in a loop; a nest of functions can only be checked by reading it.
6//!
7//! The order is SQLite's own, weakest binding first:
8//!
9//! ```text
10//! OR
11//! AND
12//! NOT (unary, prefix)
13//! = == <> != > >= < <= IS IS NOT IN LIKE GLOB MATCH REGEXP BETWEEN ISNULL NOTNULL
14//! & | << >>
15//! + -
16//! * / %
17//! || -> ->>
18//! COLLATE (postfix)
19//! ~ + - (unary, prefix)
20//! ```
21//!
22//! SQLite gives every comparison and quasi-comparison the same precedence,
23//! which is why `a = b IS NULL` parses as `(a = b) IS NULL` rather than as
24//! `a = (b IS NULL)`. Splitting them into separate levels is the most common
25//! way to get this wrong.
26
27use crate::lexer::Punctuator;
28
29/// A binding power: the precedence a parser compares against.
30#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
31pub struct Power(pub u8);
32
33/// Below every operator; where a fresh expression starts.
34pub const LOWEST: Power = Power(0);
35/// `OR`.
36pub const OR: Power = Power(1);
37/// `AND`.
38pub const AND: Power = Power(2);
39/// Prefix `NOT`.
40pub const NOT: Power = Power(3);
41/// `=`, `<>`, `IS`, `IN`, `LIKE`, `BETWEEN` and the other quasi-comparisons.
42pub const COMPARISON: Power = Power(4);
43/// `<`, `<=`, `>`, `>=`.
44///
45/// **One level tighter than `=`, as SQLite's grammar declares them.** Lemon's
46/// table lists `IS MATCH LIKE BETWEEN IN ISNULL NOTNULL NE EQ` on one line and
47/// `GT LE LT GE` on the next, so `2 = 1 < 3` is `2 = (1 < 3)`, which is false,
48/// and `1 BETWEEN 0 AND x <= 3` takes `x <= 3` as its upper bound. Sharing one
49/// level read both from the left and answered 1 for each.
50pub const RELATIONAL: Power = Power(5);
51/// `&`, `|`, `<<`, `>>`.
52pub const BITWISE: Power = Power(6);
53/// `<->`, `<=>`, `<#>`, `<+>`, `<~>`, `<%>`.
54///
55/// **The same level as the bitwise operators, which is where PostgreSQL puts
56/// them.** pgvector's distances are ordinary user-defined operators there, and
57/// PostgreSQL gives "any other operator" a slot that binds tighter than a
58/// comparison and looser than `+`. That is the slot that makes
59/// `WHERE v <=> q < 0.5` and `ORDER BY v <=> q` parse the way anybody writing
60/// them means, and it is the only property of the level that matters: nothing
61/// mixes a distance with a shift.
62pub const DISTANCE: Power = Power(6);
63/// `+` and `-`.
64pub const ADDITIVE: Power = Power(7);
65/// `*`, `/`, `%`.
66pub const MULTIPLICATIVE: Power = Power(8);
67/// `||`, `->`, `->>`.
68pub const CONCAT: Power = Power(9);
69/// Postfix `COLLATE`.
70pub const COLLATE: Power = Power(10);
71/// Prefix `~`, `+`, `-`.
72pub const UNARY: Power = Power(11);
73
74/// Returns the binding power of an infix punctuator, when it has one.
75pub fn infix_power(punctuator: Punctuator) -> Option<Power> {
76 let power = match punctuator {
77 Punctuator::Equal | Punctuator::NotEqual => COMPARISON,
78 Punctuator::Less
79 | Punctuator::LessEqual
80 | Punctuator::Greater
81 | Punctuator::GreaterEqual => RELATIONAL,
82 Punctuator::BitAnd | Punctuator::BitOr | Punctuator::ShiftLeft | Punctuator::ShiftRight => {
83 BITWISE
84 }
85 Punctuator::L2Distance
86 | Punctuator::CosineDistance
87 | Punctuator::NegativeInnerProduct
88 | Punctuator::L1Distance
89 | Punctuator::HammingDistance
90 | Punctuator::JaccardDistance => DISTANCE,
91 Punctuator::Plus | Punctuator::Minus => ADDITIVE,
92 Punctuator::Star | Punctuator::Slash | Punctuator::Percent => MULTIPLICATIVE,
93 Punctuator::Concat | Punctuator::Arrow | Punctuator::DoubleArrow => CONCAT,
94 _ => return None,
95 };
96 Some(power)
97}
98
99#[cfg(test)]
100mod tests {
101 use super::*;
102
103 /// The published order, weakest first. A change to the table that does not
104 /// change this list has changed how SQL parses.
105 #[test]
106 fn the_levels_are_in_the_published_order() {
107 let levels = [
108 LOWEST,
109 OR,
110 AND,
111 NOT,
112 COMPARISON,
113 RELATIONAL,
114 BITWISE,
115 ADDITIVE,
116 MULTIPLICATIVE,
117 CONCAT,
118 COLLATE,
119 UNARY,
120 ];
121 for pair in levels.windows(2) {
122 let (weaker, stronger) = (pair.first().copied(), pair.get(1).copied());
123 assert!(weaker < stronger, "{weaker:?} !< {stronger:?}");
124 }
125 }
126
127 /// `=` and `<>` share the level of `IS`, which decides how `a = b IS NULL`
128 /// parses, and the ordering comparisons bind one level tighter, which
129 /// decides how `a = b < c` parses. Both are SQLite's grammar.
130 #[test]
131 fn equality_and_ordering_comparisons_have_their_own_levels() {
132 for punctuator in [Punctuator::Equal, Punctuator::NotEqual] {
133 assert_eq!(infix_power(punctuator), Some(COMPARISON), "{punctuator:?}");
134 }
135 for punctuator in [
136 Punctuator::Less,
137 Punctuator::LessEqual,
138 Punctuator::Greater,
139 Punctuator::GreaterEqual,
140 ] {
141 assert_eq!(infix_power(punctuator), Some(RELATIONAL), "{punctuator:?}");
142 }
143 }
144
145 /// Concatenation binds tighter than arithmetic, which is not the rule most
146 /// languages use and is the rule SQLite uses.
147 #[test]
148 fn concatenation_binds_tighter_than_arithmetic() {
149 assert!(infix_power(Punctuator::Concat) > infix_power(Punctuator::Star));
150 assert!(infix_power(Punctuator::Star) > infix_power(Punctuator::Plus));
151 assert!(infix_power(Punctuator::Plus) > infix_power(Punctuator::BitOr));
152 }
153
154 /// Punctuation that is not an operator has no power at all, so the Pratt
155 /// loop stops on it rather than treating it as a weak operator.
156 #[test]
157 fn non_operators_have_no_power() {
158 for punctuator in [
159 Punctuator::LeftParen,
160 Punctuator::RightParen,
161 Punctuator::Comma,
162 Punctuator::Semicolon,
163 Punctuator::Dot,
164 Punctuator::BitNot,
165 ] {
166 assert_eq!(infix_power(punctuator), None, "{punctuator:?}");
167 }
168 }
169}