logicaffeine_proof/
lemma_index.rs1use crate::discrimination::DiscTree;
19use crate::unify::{apply_subst_to_expr, match_expr_pattern, Substitution};
20use crate::{ProofExpr, ProofTerm};
21
22#[derive(Debug, Clone)]
25pub struct Suggestion {
26 pub lemma: String,
27 pub tactic_text: String,
28 pub subst: Substitution,
29 pub remaining: Vec<ProofExpr>,
30}
31
32struct CompiledLemma {
34 name: String,
35 conclusion: ProofExpr,
36 premises: Vec<ProofExpr>,
37}
38
39pub struct LemmaIndex {
41 lemmas: Vec<CompiledLemma>,
42 concl_index: DiscTree<usize>,
43}
44
45impl LemmaIndex {
46 pub fn build(named: &[(String, ProofExpr)]) -> Self {
48 let mut lemmas = Vec::new();
49 let mut concl_index = DiscTree::new();
50 for (name, formula) in named {
51 let (premises, conclusion) = peel(formula);
52 let idx = lemmas.len();
53 concl_index.insert_expr(&conclusion, idx);
54 lemmas.push(CompiledLemma {
55 name: name.clone(),
56 conclusion,
57 premises,
58 });
59 }
60 LemmaIndex {
61 lemmas,
62 concl_index,
63 }
64 }
65
66 pub fn find_exact(&self, goal: &ProofExpr) -> Vec<Suggestion> {
69 let mut out = self.matches(goal, "exact");
70 out.sort_by_key(|s| s.subst.len());
71 out
72 }
73
74 pub fn find_apply(&self, goal: &ProofExpr) -> Vec<Suggestion> {
77 let mut out: Vec<Suggestion> = self
78 .matches(goal, "apply")
79 .into_iter()
80 .filter(|s| !s.remaining.is_empty())
81 .collect();
82 out.sort_by_key(|s| (s.remaining.len(), s.subst.len()));
83 out
84 }
85
86 pub fn select_premises(&self, goal: &ProofExpr, k: usize) -> Vec<String> {
91 let goal_syms = expr_symbols(goal);
92 let matching: std::collections::HashSet<usize> = self
93 .concl_index
94 .candidates_expr(goal)
95 .into_iter()
96 .copied()
97 .collect();
98
99 let mut scored: Vec<(i64, usize)> = self
100 .lemmas
101 .iter()
102 .enumerate()
103 .filter_map(|(i, lem)| {
104 let overlap = expr_symbols(&lem.conclusion)
105 .intersection(&goal_syms)
106 .count() as i64;
107 if overlap == 0 && !matching.contains(&i) {
108 return None; }
110 let mut score = overlap;
111 if matching.contains(&i) {
112 score += 100; }
114 Some((score, i))
115 })
116 .collect();
117 scored.sort_by(|a, b| b.0.cmp(&a.0));
118 scored.truncate(k);
119 scored
120 .into_iter()
121 .map(|(_, i)| self.lemmas[i].name.clone())
122 .collect()
123 }
124
125 fn matches(&self, goal: &ProofExpr, verb: &str) -> Vec<Suggestion> {
126 let mut out = Vec::new();
127 let mut cand: Vec<usize> = self
128 .concl_index
129 .candidates_expr(goal)
130 .into_iter()
131 .copied()
132 .collect();
133 cand.sort_unstable();
134 cand.dedup();
135 for i in cand {
136 let lem = &self.lemmas[i];
137 if let Some(subst) = match_expr_pattern(&lem.conclusion, goal) {
138 let remaining = lem
139 .premises
140 .iter()
141 .map(|p| apply_subst_to_expr(p, &subst))
142 .collect();
143 out.push(Suggestion {
144 lemma: lem.name.clone(),
145 tactic_text: format!("{verb} {}", lem.name),
146 subst,
147 remaining,
148 });
149 }
150 }
151 out
152 }
153}
154
155fn peel(formula: &ProofExpr) -> (Vec<ProofExpr>, ProofExpr) {
157 let mut body = formula;
158 while let ProofExpr::ForAll { body: inner, .. } = body {
159 body = inner;
160 }
161 let mut premises = Vec::new();
162 while let ProofExpr::Implies(a, rest) = body {
163 premises.push((**a).clone());
164 body = rest;
165 }
166 (premises, body.clone())
167}
168
169fn expr_symbols(e: &ProofExpr) -> std::collections::HashSet<String> {
172 let mut out = std::collections::HashSet::new();
173 collect_expr_symbols(e, &mut out);
174 out
175}
176
177fn collect_expr_symbols(e: &ProofExpr, out: &mut std::collections::HashSet<String>) {
178 match e {
179 ProofExpr::Predicate { name, args, .. } => {
180 out.insert(format!("p:{name}"));
181 for a in args {
182 collect_term_symbols(a, out);
183 }
184 }
185 ProofExpr::Atom(s) => {
186 out.insert(format!("a:{s}"));
187 }
188 ProofExpr::Identity(l, r) => {
189 out.insert("=".to_string());
190 collect_term_symbols(l, out);
191 collect_term_symbols(r, out);
192 }
193 ProofExpr::And(l, r)
194 | ProofExpr::Or(l, r)
195 | ProofExpr::Implies(l, r)
196 | ProofExpr::Iff(l, r) => {
197 collect_expr_symbols(l, out);
198 collect_expr_symbols(r, out);
199 }
200 ProofExpr::Not(p) => collect_expr_symbols(p, out),
201 ProofExpr::ForAll { body, .. } | ProofExpr::Exists { body, .. } => {
202 collect_expr_symbols(body, out)
203 }
204 _ => {}
205 }
206}
207
208fn collect_term_symbols(t: &ProofTerm, out: &mut std::collections::HashSet<String>) {
209 match t {
210 ProofTerm::Constant(s) => {
211 out.insert(format!("c:{s}"));
212 }
213 ProofTerm::Function(name, args) => {
214 out.insert(format!("f:{name}"));
215 for a in args {
216 collect_term_symbols(a, out);
217 }
218 }
219 _ => {}
221 }
222}