Skip to main content

dive_syntax/
ops.rs

1//! Operator precedence and associativity.
2//!
3//! This is SANY's table (`tla2sany/parser/Operators.java`). Every operator
4//! has a precedence *range* `low..=high`. Two operators conflict unless one
5//! range lies wholly above the other. Synonyms such as `/\`, `\land` and `∧`
6//! share one entry.
7
8/// Associativity of an operator.
9#[derive(Debug, Clone, Copy, PartialEq, Eq)]
10pub enum Assoc {
11    /// Not associative: `a = b = c` is an error.
12    None,
13    /// Left-associative: `a + b + c` is `(a + b) + c`.
14    Left,
15}
16
17/// How an operator is applied.
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub enum Fixity {
20    /// `op e`.
21    Prefix,
22    /// `e op`.
23    Postfix,
24    /// `a op b`.
25    Infix,
26    /// `a op b op c` collected into one n-ary node (only `\X`).
27    Nfix,
28}
29
30/// Precedence information for one operator.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub struct OpInfo {
33    /// The canonical spelling; synonyms share it.
34    pub canonical: &'static str,
35    /// Lowest precedence in the operator's range.
36    pub low: u8,
37    /// Highest precedence in the operator's range.
38    pub high: u8,
39    /// Associativity.
40    pub assoc: Assoc,
41    /// Fixity.
42    pub fixity: Fixity,
43}
44
45impl OpInfo {
46    /// Whether the operator is prefix.
47    #[must_use]
48    pub fn is_prefix(&self) -> bool {
49        self.fixity == Fixity::Prefix
50    }
51
52    /// Whether the operator is infix (including n-ary `\X`).
53    #[must_use]
54    pub fn is_infix(&self) -> bool {
55        matches!(self.fixity, Fixity::Infix | Fixity::Nfix)
56    }
57
58    /// Whether the operator is postfix.
59    #[must_use]
60    pub fn is_postfix(&self) -> bool {
61        self.fixity == Fixity::Postfix
62    }
63
64    /// SANY's `Operator.succ(left, right)`: `left` binds tighter.
65    #[must_use]
66    pub fn succ(&self, right: &OpInfo) -> bool {
67        self.low > right.high
68    }
69
70    /// SANY's `Operator.prec(left, right)`: `right` binds tighter.
71    #[must_use]
72    pub fn prec(&self, right: &OpInfo) -> bool {
73        self.high < right.low
74    }
75
76    /// Identity in SANY's sense: synonyms are the same operator.
77    #[must_use]
78    pub fn same(&self, other: &OpInfo) -> bool {
79        self.canonical == other.canonical
80    }
81}
82
83const fn op(canonical: &'static str, low: u8, high: u8, assoc: Assoc, fixity: Fixity) -> OpInfo {
84    OpInfo {
85        canonical,
86        low,
87        high,
88        assoc,
89        fixity,
90    }
91}
92
93use Assoc::{Left as L, None as N};
94use Fixity::{Infix as I, Nfix as X, Postfix as Po, Prefix as Pr};
95
96/// The canonical operators (`Operators.CanonicalOperators`).
97const CANONICAL: &[OpInfo] = &[
98    op("[", 160, 160, L, Po),
99    op(".", 170, 170, L, I),
100    op("'", 150, 150, N, Po),
101    op("^", 140, 140, N, I),
102    op("/", 130, 130, N, I),
103    op("*", 130, 130, L, I),
104    op("-", 110, 110, L, I),
105    op("-.", 120, 120, N, Pr),
106    op("+", 100, 100, L, I),
107    op("=", 50, 50, N, I),
108    op("\\lnot", 40, 40, L, Pr),
109    op("\\land", 30, 30, L, I),
110    op("\\lor", 30, 30, L, I),
111    op("~>", 20, 20, N, I),
112    op("=>", 10, 10, N, I),
113    op("[]", 40, 150, N, Pr),
114    op("<>", 40, 150, N, Pr),
115    op("ENABLED", 40, 150, N, Pr),
116    op("UNCHANGED", 40, 150, N, Pr),
117    op("SUBSET", 100, 130, N, Pr),
118    op("UNION", 100, 130, N, Pr),
119    op("DOMAIN", 100, 130, N, Pr),
120    op("^+", 150, 150, N, Po),
121    op("^*", 150, 150, N, Po),
122    op("^#", 150, 150, N, Po),
123    op("\\cdot", 50, 140, L, I),
124    op("\\equiv", 20, 20, N, I),
125    op("-+->", 20, 20, N, I),
126    op("/=", 50, 50, N, I),
127    op("\\subseteq", 50, 50, N, I),
128    op("\\in", 50, 50, N, I),
129    op("\\notin", 50, 50, N, I),
130    op("<", 50, 50, N, I),
131    op("\\leq", 50, 50, N, I),
132    op(">", 50, 50, N, I),
133    op("\\geq", 50, 50, N, I),
134    op("\\times", 100, 130, L, X),
135    op("\\", 80, 80, N, I),
136    op("\\intersect", 80, 80, L, I),
137    op("\\union", 80, 80, L, I),
138    op("...", 90, 90, N, I),
139    op("..", 90, 90, N, I),
140    op("|", 100, 110, L, I),
141    op("||", 100, 110, L, I),
142    op("&&", 130, 130, L, I),
143    op("&", 130, 130, L, I),
144    op("$$", 90, 130, L, I),
145    op("$", 90, 130, L, I),
146    op("??", 90, 130, L, I),
147    op("%%", 100, 110, L, I),
148    op("%", 100, 110, N, I),
149    op("##", 90, 130, L, I),
150    op("++", 100, 100, L, I),
151    op("--", 110, 110, L, I),
152    op("**", 130, 130, L, I),
153    op("//", 130, 130, N, I),
154    op("^^", 140, 140, N, I),
155    op("@@", 60, 60, L, I),
156    op("!!", 90, 130, N, I),
157    op("|-", 50, 50, N, I),
158    op("|=", 50, 50, N, I),
159    op("-|", 50, 50, N, I),
160    op("=|", 50, 50, N, I),
161    op("<:", 70, 70, N, I),
162    op(":>", 70, 70, N, I),
163    op(":=", 50, 50, N, I),
164    op("::=", 50, 50, N, I),
165    op("\\oplus", 100, 100, L, I),
166    op("\\ominus", 110, 110, L, I),
167    op("\\odot", 130, 130, L, I),
168    op("\\oslash", 130, 130, N, I),
169    op("\\otimes", 130, 130, L, I),
170    op("\\uplus", 90, 130, L, I),
171    op("\\sqcap", 90, 130, L, I),
172    op("\\sqcup", 90, 130, L, I),
173    op("\\div", 130, 130, N, I),
174    op("\\wr", 90, 140, N, I),
175    op("\\star", 130, 130, L, I),
176    op("\\o", 130, 130, L, I),
177    op("\\bigcirc", 130, 130, L, I),
178    op("\\bullet", 130, 130, L, I),
179    op("\\prec", 50, 50, N, I),
180    op("\\succ", 50, 50, N, I),
181    op("\\preceq", 50, 50, N, I),
182    op("\\succeq", 50, 50, N, I),
183    op("\\sim", 50, 50, N, I),
184    op("\\simeq", 50, 50, N, I),
185    op("\\ll", 50, 50, N, I),
186    op("\\gg", 50, 50, N, I),
187    op("\\asymp", 50, 50, N, I),
188    op("\\subset", 50, 50, N, I),
189    op("\\supset", 50, 50, N, I),
190    op("\\supseteq", 50, 50, N, I),
191    op("\\approx", 50, 50, N, I),
192    op("\\cong", 50, 50, N, I),
193    op("\\sqsubset", 50, 50, N, I),
194    op("\\sqsubseteq", 50, 50, N, I),
195    op("\\sqsupset", 50, 50, N, I),
196    op("\\sqsupseteq", 50, 50, N, I),
197    op("\\doteq", 50, 50, N, I),
198    op("\\propto", 50, 50, N, I),
199];
200
201/// Synonyms (`Operators.OperatorSynonyms`): canonical spelling first.
202const SYNONYMS: &[&[&str]] = &[
203    &["\\lnot", "~", "\\neg", "¬"],
204    &["[]", "□"],
205    &["<>", "◇"],
206    &["\\land", "/\\", "∧"],
207    &["\\lor", "\\/", "∨"],
208    &["\\equiv", "<=>", "≡", "⇔"],
209    &["/=", "#", "≠"],
210    &["\\leq", "<=", "=<", "≤"],
211    &["\\geq", ">=", "≥"],
212    &["\\times", "\\X", "×"],
213    &["\\intersect", "\\cap", "∩"],
214    &["\\union", "\\cup", "∪"],
215    &["\\o", "\\circ", "∘"],
216    &["\\oplus", "(+)", "⊕"],
217    &["\\ominus", "(-)", "⊖"],
218    &["\\odot", "(.)", "⊙"],
219    &["\\oslash", "(/)", "⊘"],
220    &["\\otimes", "(\\X)", "⊗"],
221    &["\\approx", "≈"],
222    &[":=", "≔"],
223    &["\\asymp", "≍"],
224    &["\\bigcirc", "◯"],
225    &["::=", "⩴"],
226    &["\\bullet", "●"],
227    &["\\cdot", "⋅"],
228    &["\\cong", "≅"],
229    &["\\div", "÷"],
230    &["\\doteq", "≐"],
231    &["..", "‥"],
232    &["...", "…"],
233    &["!!", "‼"],
234    &["\\gg", "≫"],
235    &["=>", "⇒"],
236    &["\\in", "∈"],
237    &["=|", "⫤"],
238    &["~>", "↝"],
239    &["\\ll", "≪"],
240    &["-|", "⊣"],
241    &["\\notin", "∉"],
242    &["-+->", "⇸"],
243    &["\\prec", "≺"],
244    &["\\preceq", "⪯"],
245    &["\\propto", "∝"],
246    &["??", "⁇"],
247    &["|=", "⊨"],
248    &["|-", "⊢"],
249    &["\\sim", "∼"],
250    &["\\simeq", "≃"],
251    &["\\sqcap", "⊓"],
252    &["\\sqcup", "⊔"],
253    &["\\sqsubset", "⊏"],
254    &["\\sqsubseteq", "⊑"],
255    &["\\sqsupset", "⊐"],
256    &["\\sqsupseteq", "⊒"],
257    &["\\star", "⋆"],
258    &["\\subset", "⊂"],
259    &["\\subseteq", "⊆"],
260    &["\\succ", "≻"],
261    &["\\succeq", "⪰"],
262    &["\\supset", "⊃"],
263    &["\\supseteq", "⊇"],
264    &["\\uplus", "⊎"],
265    &["||", "‖"],
266    &["\\wr", "≀"],
267    &["^+", "⁺"],
268];
269
270/// Precomputed tables: spelling (canonical or synonym) to index in
271/// [`CANONICAL`], and each operator's mixfix form.
272struct Tables {
273    by_spelling: std::collections::HashMap<&'static str, usize>,
274    mixfix: Vec<Option<usize>>,
275}
276
277fn tables() -> &'static Tables {
278    static TABLES: std::sync::OnceLock<Tables> = std::sync::OnceLock::new();
279    TABLES.get_or_init(|| {
280        let mut by_spelling = std::collections::HashMap::new();
281        for (i, o) in CANONICAL.iter().enumerate() {
282            by_spelling.insert(o.canonical, i);
283        }
284        for group in SYNONYMS {
285            if let Some(&i) = group.first().and_then(|c| by_spelling.get(c)) {
286                for s in group.iter().skip(1) {
287                    by_spelling.insert(*s, i);
288                }
289            }
290        }
291        let mixfix = CANONICAL
292            .iter()
293            .enumerate()
294            .map(|(i, o)| {
295                if o.is_prefix() {
296                    Some(i)
297                } else {
298                    let name = format!("{}.", o.canonical);
299                    by_spelling.get(name.as_str()).copied()
300                }
301            })
302            .collect();
303        Tables {
304            by_spelling,
305            mixfix,
306        }
307    })
308}
309
310/// The canonical spelling of an operator symbol, resolving synonyms.
311#[must_use]
312pub fn canonical_spelling(symbol: &str) -> &str {
313    lookup(symbol).map_or(symbol, |o| o.canonical)
314}
315
316/// Looks up the precedence of an operator by its spelling.
317#[must_use]
318pub fn lookup(symbol: &str) -> Option<&'static OpInfo> {
319    tables()
320        .by_spelling
321        .get(symbol)
322        .and_then(|&i| CANONICAL.get(i))
323}
324
325/// The function-application pseudo-operator `[`.
326pub(crate) fn fcn_op() -> &'static OpInfo {
327    &CANONICAL[0]
328}
329
330/// SANY's `VoidOperator`, pushed to force the final reduction.
331pub(crate) const VOID: OpInfo = op("$$_void", 0, 0, N, I);
332
333/// SANY's `Operators.getMixfix`: a prefix operator is its own mixfix form;
334/// otherwise the operator named by appending `.` to the canonical spelling,
335/// if any. That gives `-` → `-.`, and (a SANY quirk) `..` → `...`.
336pub(crate) fn mixfix(o: &'static OpInfo) -> Option<&'static OpInfo> {
337    if o.is_prefix() {
338        return Some(o);
339    }
340    let t = tables();
341    let i = *t.by_spelling.get(o.canonical)?;
342    t.mixfix
343        .get(i)
344        .copied()
345        .flatten()
346        .and_then(|j| CANONICAL.get(j))
347}
348
349#[cfg(test)]
350mod tests {
351    use super::*;
352    use crate::lexer::OPERATORS;
353
354    #[test]
355    fn every_operator_token_has_precedence() {
356        for (text, _) in OPERATORS {
357            assert!(lookup(text).is_some(), "{text}");
358        }
359    }
360
361    #[test]
362    fn synonyms_share_an_entry() {
363        let a = lookup("/\\");
364        let b = lookup("∧");
365        assert!(a.is_some_and(|a| b.is_some_and(|b| a.same(b))));
366        assert_eq!(canonical_spelling("#"), "/=");
367    }
368
369    #[test]
370    fn ranges() {
371        let (Some(cdot), Some(eq)) = (lookup("\\cdot"), lookup("=")) else {
372            unreachable!("table entries exist")
373        };
374        assert!(!cdot.succ(eq) && !cdot.prec(eq));
375        assert!(mixfix(lookup("-").unwrap_or(&VOID)).is_some());
376        assert!(mixfix(lookup("+").unwrap_or(&VOID)).is_none());
377    }
378}