Skip to main content

logicaffeine_proof/
discrimination.rs

1//! First-order discrimination tree: the shared pattern index under `simp`
2//! rule lookup, `exact?`/`apply?` library search, and `crush`'s E-matching.
3//!
4//! # How it works
5//!
6//! A pattern is flattened to its preorder key sequence — head symbols carrying
7//! their arity, with `*` at each pattern-variable position — and inserted into
8//! a trie. Retrieval walks the trie in step with the query's own flattening:
9//! a symbol edge must match the query symbol exactly; a `*` edge skips one
10//! complete query subterm (the arity annotations make subterm extents
11//! computable without re-walking the term).
12//!
13//! # The contract
14//!
15//! Retrieval NEVER MISSES: every inserted pattern that one-sided matches the
16//! query (per [`crate::unify::match_term_pattern`]) is among the candidates.
17//! It may over-approximate — variable positions are treated independently, so
18//! the non-linear pattern `f(x, x)` is retrieved for `f(a, b)` — and the
19//! matcher is the arbiter. The value of the tree is pruning: a query touches
20//! only patterns sharing its head structure, not the whole rule set.
21//!
22//! Quantified subexpressions flatten to `*` on both sides (opaque), which
23//! preserves never-miss at the cost of extra candidates — the conservative
24//! choice for shapes the matcher itself treats conservatively.
25
26use std::collections::BTreeMap;
27
28use crate::{ProofExpr, ProofTerm};
29
30/// One symbol in a flattened pattern/query.
31#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
32enum Key {
33    /// A head symbol with its arity. The `String` is namespaced by kind
34    /// (predicate/function/constant/connective) so same-named symbols of
35    /// different kinds never collide.
36    Sym(String, usize),
37    /// A variable position — spans one complete subterm.
38    Star,
39}
40
41struct Node<T> {
42    children: BTreeMap<Key, Node<T>>,
43    /// Values whose pattern's key sequence ends exactly here.
44    values: Vec<T>,
45}
46
47impl<T> Default for Node<T> {
48    fn default() -> Self {
49        Node {
50            children: BTreeMap::new(),
51            values: Vec::new(),
52        }
53    }
54}
55
56/// A discrimination tree mapping term/expression patterns to payloads.
57///
58/// Term and expression patterns share one tree — their key alphabets are
59/// disjoint by construction, so they never cross-match.
60pub struct DiscTree<T> {
61    root: Node<T>,
62}
63
64impl<T> Default for DiscTree<T> {
65    fn default() -> Self {
66        Self::new()
67    }
68}
69
70impl<T> DiscTree<T> {
71    pub fn new() -> Self {
72        DiscTree {
73            root: Node::default(),
74        }
75    }
76
77    /// Index a term pattern (its `Variable`s are the wildcard positions).
78    pub fn insert_term(&mut self, pattern: &ProofTerm, value: T) {
79        let mut keys = Vec::new();
80        flatten_term(pattern, &mut keys);
81        self.insert_keys(&keys, value);
82    }
83
84    /// Index an expression pattern (its `Variable`s are the wildcard positions).
85    pub fn insert_expr(&mut self, pattern: &ProofExpr, value: T) {
86        let mut keys = Vec::new();
87        flatten_expr(pattern, &mut keys);
88        self.insert_keys(&keys, value);
89    }
90
91    /// Every pattern that could one-sided match the query term (superset —
92    /// confirm with [`crate::unify::match_term_pattern`]).
93    pub fn candidates_term(&self, query: &ProofTerm) -> Vec<&T> {
94        let mut keys = Vec::new();
95        flatten_term(query, &mut keys);
96        self.candidates_keys(&keys)
97    }
98
99    /// Every pattern that could one-sided match the query expression
100    /// (superset — confirm with [`crate::unify::match_expr_pattern`]).
101    pub fn candidates_expr(&self, query: &ProofExpr) -> Vec<&T> {
102        let mut keys = Vec::new();
103        flatten_expr(query, &mut keys);
104        self.candidates_keys(&keys)
105    }
106
107    fn insert_keys(&mut self, keys: &[Key], value: T) {
108        let mut node = &mut self.root;
109        for key in keys {
110            node = node.children.entry(key.clone()).or_default();
111        }
112        node.values.push(value);
113    }
114
115    fn candidates_keys(&self, keys: &[Key]) -> Vec<&T> {
116        let jump = subterm_jumps(keys);
117        let mut out = Vec::new();
118        retrieve(&self.root, keys, &jump, 0, &mut out);
119        out
120    }
121}
122
123/// `jump[i]` = the index one past the subterm that starts at position `i`.
124fn subterm_jumps(keys: &[Key]) -> Vec<usize> {
125    let mut jump = vec![0usize; keys.len()];
126    fill_jumps(keys, 0, &mut jump);
127    jump
128}
129
130fn fill_jumps(keys: &[Key], i: usize, jump: &mut [usize]) -> usize {
131    let end = match &keys[i] {
132        Key::Star => i + 1,
133        Key::Sym(_, arity) => {
134            let mut j = i + 1;
135            for _ in 0..*arity {
136                j = fill_jumps(keys, j, jump);
137            }
138            j
139        }
140    };
141    jump[i] = end;
142    end
143}
144
145fn retrieve<'a, T>(
146    node: &'a Node<T>,
147    keys: &[Key],
148    jump: &[usize],
149    i: usize,
150    out: &mut Vec<&'a T>,
151) {
152    if i == keys.len() {
153        out.extend(node.values.iter());
154        return;
155    }
156    match &keys[i] {
157        sym @ Key::Sym(..) => {
158            // A pattern with the same head continues in lockstep.
159            if let Some(child) = node.children.get(sym) {
160                retrieve(child, keys, jump, i + 1, out);
161            }
162            // A pattern variable here swallows this whole query subterm.
163            if let Some(star) = node.children.get(&Key::Star) {
164                retrieve(star, keys, jump, jump[i], out);
165            }
166        }
167        Key::Star => {
168            // The query is opaque here (a query variable or a shape flattened
169            // conservatively): any complete pattern subterm may align with it.
170            let mut landings = Vec::new();
171            skip_pattern_subterm(node, 1, &mut landings);
172            for landing in landings {
173                retrieve(landing, keys, jump, i + 1, out);
174            }
175        }
176    }
177}
178
179/// All trie nodes exactly one complete pattern subterm below `node`.
180fn skip_pattern_subterm<'a, T>(node: &'a Node<T>, pending: usize, out: &mut Vec<&'a Node<T>>) {
181    if pending == 0 {
182        out.push(node);
183        return;
184    }
185    for (key, child) in &node.children {
186        let need = pending - 1
187            + match key {
188                Key::Sym(_, arity) => *arity,
189                Key::Star => 0,
190            };
191        skip_pattern_subterm(child, need, out);
192    }
193}
194
195fn flatten_term(t: &ProofTerm, out: &mut Vec<Key>) {
196    match t {
197        ProofTerm::Variable(_) => out.push(Key::Star),
198        ProofTerm::Constant(s) => out.push(Key::Sym(format!("c:{s}"), 0)),
199        ProofTerm::BoundVarRef(s) => out.push(Key::Sym(format!("b:{s}"), 0)),
200        ProofTerm::Function(name, args) => {
201            out.push(Key::Sym(format!("f:{name}"), args.len()));
202            for a in args {
203                flatten_term(a, out);
204            }
205        }
206        ProofTerm::Group(args) => {
207            out.push(Key::Sym("(,)".to_string(), args.len()));
208            for a in args {
209                flatten_term(a, out);
210            }
211        }
212    }
213}
214
215fn flatten_expr(e: &ProofExpr, out: &mut Vec<Key>) {
216    match e {
217        ProofExpr::Predicate { name, args, .. } => {
218            out.push(Key::Sym(format!("p:{name}"), args.len()));
219            for a in args {
220                flatten_term(a, out);
221            }
222        }
223        ProofExpr::Identity(l, r) => {
224            out.push(Key::Sym("=".to_string(), 2));
225            flatten_term(l, out);
226            flatten_term(r, out);
227        }
228        ProofExpr::Atom(s) => out.push(Key::Sym(format!("a:{s}"), 0)),
229        ProofExpr::And(l, r) => {
230            out.push(Key::Sym("∧".to_string(), 2));
231            flatten_expr(l, out);
232            flatten_expr(r, out);
233        }
234        ProofExpr::Or(l, r) => {
235            out.push(Key::Sym("∨".to_string(), 2));
236            flatten_expr(l, out);
237            flatten_expr(r, out);
238        }
239        ProofExpr::Implies(l, r) => {
240            out.push(Key::Sym("→".to_string(), 2));
241            flatten_expr(l, out);
242            flatten_expr(r, out);
243        }
244        ProofExpr::Iff(l, r) => {
245            out.push(Key::Sym("↔".to_string(), 2));
246            flatten_expr(l, out);
247            flatten_expr(r, out);
248        }
249        ProofExpr::Not(p) => {
250            out.push(Key::Sym("¬".to_string(), 1));
251            flatten_expr(p, out);
252        }
253        // Binders and every other shape are opaque: `*` preserves never-miss
254        // (the matcher treats them conservatively too).
255        _ => out.push(Key::Star),
256    }
257}