1use std::collections::BTreeMap;
27
28use crate::{ProofExpr, ProofTerm};
29
30#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
32enum Key {
33 Sym(String, usize),
37 Star,
39}
40
41struct Node<T> {
42 children: BTreeMap<Key, Node<T>>,
43 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
56pub 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 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 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 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 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
123fn 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 if let Some(child) = node.children.get(sym) {
160 retrieve(child, keys, jump, i + 1, out);
161 }
162 if let Some(star) = node.children.get(&Key::Star) {
164 retrieve(star, keys, jump, jump[i], out);
165 }
166 }
167 Key::Star => {
168 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
179fn 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 _ => out.push(Key::Star),
256 }
257}