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/// Every comparison, and the quasi-comparisons that share its level.
42pub const COMPARISON: Power = Power(4);
43/// `&`, `|`, `<<`, `>>`.
44pub const BITWISE: Power = Power(5);
45/// `<->`, `<=>`, `<#>`, `<+>`, `<~>`, `<%>`.
46///
47/// **The same level as the bitwise operators, which is where PostgreSQL puts
48/// them.** pgvector's distances are ordinary user-defined operators there, and
49/// PostgreSQL gives "any other operator" a slot that binds tighter than a
50/// comparison and looser than `+`. That is the slot that makes
51/// `WHERE v <=> q < 0.5` and `ORDER BY v <=> q` parse the way anybody writing
52/// them means, and it is the only property of the level that matters: nothing
53/// mixes a distance with a shift.
54pub const DISTANCE: Power = Power(5);
55/// `+` and `-`.
56pub const ADDITIVE: Power = Power(6);
57/// `*`, `/`, `%`.
58pub const MULTIPLICATIVE: Power = Power(7);
59/// `||`, `->`, `->>`.
60pub const CONCAT: Power = Power(8);
61/// Postfix `COLLATE`.
62pub const COLLATE: Power = Power(9);
63/// Prefix `~`, `+`, `-`.
64pub const UNARY: Power = Power(10);
65
66/// Returns the binding power of an infix punctuator, when it has one.
67pub fn infix_power(punctuator: Punctuator) -> Option<Power> {
68    let power = match punctuator {
69        Punctuator::Equal
70        | Punctuator::NotEqual
71        | Punctuator::Less
72        | Punctuator::LessEqual
73        | Punctuator::Greater
74        | Punctuator::GreaterEqual => COMPARISON,
75        Punctuator::BitAnd | Punctuator::BitOr | Punctuator::ShiftLeft | Punctuator::ShiftRight => {
76            BITWISE
77        }
78        Punctuator::L2Distance
79        | Punctuator::CosineDistance
80        | Punctuator::NegativeInnerProduct
81        | Punctuator::L1Distance
82        | Punctuator::HammingDistance
83        | Punctuator::JaccardDistance => DISTANCE,
84        Punctuator::Plus | Punctuator::Minus => ADDITIVE,
85        Punctuator::Star | Punctuator::Slash | Punctuator::Percent => MULTIPLICATIVE,
86        Punctuator::Concat | Punctuator::Arrow | Punctuator::DoubleArrow => CONCAT,
87        _ => return None,
88    };
89    Some(power)
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95
96    /// The published order, weakest first. A change to the table that does not
97    /// change this list has changed how SQL parses.
98    #[test]
99    fn the_levels_are_in_the_published_order() {
100        let levels = [
101            LOWEST,
102            OR,
103            AND,
104            NOT,
105            COMPARISON,
106            BITWISE,
107            ADDITIVE,
108            MULTIPLICATIVE,
109            CONCAT,
110            COLLATE,
111            UNARY,
112        ];
113        for pair in levels.windows(2) {
114            let (weaker, stronger) = (pair.first().copied(), pair.get(1).copied());
115            assert!(weaker < stronger, "{weaker:?} !< {stronger:?}");
116        }
117    }
118
119    /// Every comparison shares one level. This is the rule that decides how
120    /// `a = b IS NULL` parses, and separating them is the usual mistake.
121    #[test]
122    fn every_comparison_shares_one_level() {
123        for punctuator in [
124            Punctuator::Equal,
125            Punctuator::NotEqual,
126            Punctuator::Less,
127            Punctuator::LessEqual,
128            Punctuator::Greater,
129            Punctuator::GreaterEqual,
130        ] {
131            assert_eq!(infix_power(punctuator), Some(COMPARISON), "{punctuator:?}");
132        }
133    }
134
135    /// Concatenation binds tighter than arithmetic, which is not the rule most
136    /// languages use and is the rule SQLite uses.
137    #[test]
138    fn concatenation_binds_tighter_than_arithmetic() {
139        assert!(infix_power(Punctuator::Concat) > infix_power(Punctuator::Star));
140        assert!(infix_power(Punctuator::Star) > infix_power(Punctuator::Plus));
141        assert!(infix_power(Punctuator::Plus) > infix_power(Punctuator::BitOr));
142    }
143
144    /// Punctuation that is not an operator has no power at all, so the Pratt
145    /// loop stops on it rather than treating it as a weak operator.
146    #[test]
147    fn non_operators_have_no_power() {
148        for punctuator in [
149            Punctuator::LeftParen,
150            Punctuator::RightParen,
151            Punctuator::Comma,
152            Punctuator::Semicolon,
153            Punctuator::Dot,
154            Punctuator::BitNot,
155        ] {
156            assert_eq!(infix_power(punctuator), None, "{punctuator:?}");
157        }
158    }
159}
inillucent_sql/precedence.rs

inillucent_sql/
precedence.rs
