1use std::collections::HashSet;
19
20use crate::engine::cert_congruence_path;
21use crate::unify::{apply_subst_to_expr, instantiate_expr, match_term_pattern, Substitution};
22use crate::{DerivationTree, InferenceRule, ProofExpr, ProofTerm};
23
24pub(crate) fn crush_prove(premises: &[ProofExpr], goal: &ProofExpr) -> Option<DerivationTree> {
28 let mut known: Vec<(ProofExpr, DerivationTree)> = Vec::new();
30 let mut eq_lemmas: Vec<&ProofExpr> = Vec::new();
31 for prem in premises {
32 if is_forall_eq_lemma(prem) {
33 eq_lemmas.push(prem);
34 } else {
35 known.push((
36 prem.clone(),
37 DerivationTree::leaf(prem.clone(), InferenceRule::PremiseMatch),
38 ));
39 }
40 }
41
42 let mut universe: Vec<ProofTerm> = Vec::new();
44 for (prop, _) in &known {
45 collect_expr_terms(prop, &mut universe);
46 }
47 collect_expr_terms(goal, &mut universe);
48 dedup_terms(&mut universe);
49
50 for lemma in &eq_lemmas {
52 let (params, lhs, _rhs) = peel_eq_lemma(lemma).expect("checked by is_forall_eq_lemma");
53 let mut fired: HashSet<String> = HashSet::new();
54 for g in &universe {
55 let Some(subst) = match_term_pattern(&lhs, g) else {
56 continue;
57 };
58 if !params.iter().all(|p| subst.contains_key(p)) {
59 continue; }
61 let key = format!("{g}");
62 if !fired.insert(key) {
63 continue;
64 }
65 let base = DerivationTree::leaf((*lemma).clone(), InferenceRule::PremiseMatch);
66 if let Some(inst) = instantiate_eq_lemma(lemma, &base, ¶ms, &subst) {
67 known.push(inst);
68 }
69 }
70 }
71
72 match goal {
74 ProofExpr::Identity(a, b) => cert_congruence_path(a, b, &known),
75 ProofExpr::Predicate { name, args, world } => {
76 close_predicate(name, args, world.as_deref(), &known)
77 }
78 _ => None,
79 }
80}
81
82fn close_predicate(
86 name: &str,
87 goal_args: &[ProofTerm],
88 world: Option<&str>,
89 known: &[(ProofExpr, DerivationTree)],
90) -> Option<DerivationTree> {
91 let pred = |args: &[ProofTerm]| ProofExpr::Predicate {
92 name: name.to_string(),
93 args: args.to_vec(),
94 world: world.map(str::to_string),
95 };
96 for (prop, atom_proof) in known {
97 let ProofExpr::Predicate {
98 name: kn,
99 args: kargs,
100 world: kw,
101 } = prop
102 else {
103 continue;
104 };
105 if kn != name || kargs.len() != goal_args.len() || kw.as_deref() != world {
106 continue;
107 }
108 let mut cur = kargs.clone();
110 let mut proof = atom_proof.clone();
111 let mut ok = true;
112 for i in 0..goal_args.len() {
113 if cur[i] == goal_args[i] {
114 continue;
115 }
116 let Some(eq) = cert_congruence_path(&cur[i], &goal_args[i], known) else {
118 ok = false;
119 break;
120 };
121 let mut next = cur.clone();
122 next[i] = goal_args[i].clone();
123 let Some(step) =
129 crate::engine::leibniz_step(pred(&next), &cur[i], &goal_args[i], eq, proof.clone())
130 else {
131 ok = false;
132 break;
133 };
134 proof = step;
135 cur = next;
136 }
137 if ok && cur == goal_args {
138 return Some(proof);
139 }
140 }
141 None
142}
143
144pub(crate) fn instantiate_steps(
157 steps: &[(ProofExpr, DerivationTree)],
158 goal: &ProofExpr,
159) -> Vec<(ProofExpr, DerivationTree)> {
160 if !steps.iter().any(|(p, _)| is_forall_eq_lemma(p)) {
161 return steps.to_vec();
162 }
163 let mut universe: Vec<ProofTerm> = Vec::new();
164 collect_expr_terms(goal, &mut universe);
165 for (prop, _) in steps {
166 if !is_forall_eq_lemma(prop) {
167 collect_expr_terms(prop, &mut universe);
168 }
169 }
170 dedup_terms(&mut universe);
171
172 let mut out: Vec<(ProofExpr, DerivationTree)> = Vec::new();
173 for (prop, proof) in steps {
174 let Some((params, lhs, rhs)) = peel_eq_lemma(prop) else {
175 out.push((prop.clone(), proof.clone()));
176 continue;
177 };
178 let mut fired: HashSet<String> = HashSet::new();
179 for pattern in [&lhs, &rhs] {
180 for g in &universe {
181 let Some(subst) = match_term_pattern(pattern, g) else {
182 continue;
183 };
184 if !params.iter().all(|p| subst.contains_key(p)) {
185 continue;
186 }
187 let Some(inst) = instantiate_eq_lemma(prop, proof, ¶ms, &subst) else {
188 continue;
189 };
190 if fired.insert(format!("{}", inst.0)) {
191 out.push(inst);
192 }
193 }
194 }
195 }
196 out
197}
198
199fn is_forall_eq_lemma(e: &ProofExpr) -> bool {
201 peel_eq_lemma(e).is_some()
202}
203
204fn peel_eq_lemma(e: &ProofExpr) -> Option<(Vec<String>, ProofTerm, ProofTerm)> {
207 let mut params = Vec::new();
208 let mut body = e;
209 while let ProofExpr::ForAll {
210 variable,
211 body: inner,
212 } = body
213 {
214 params.push(variable.clone());
215 body = inner;
216 }
217 if params.is_empty() {
218 return None;
219 }
220 match body {
221 ProofExpr::Identity(l, r) => Some((params, l.clone(), r.clone())),
222 _ => None,
223 }
224}
225
226fn instantiate_eq_lemma(
231 lemma: &ProofExpr,
232 base: &DerivationTree,
233 params: &[String],
234 subst: &Substitution,
235) -> Option<(ProofExpr, DerivationTree)> {
236 let mut tree = base.clone();
237 let mut expr = lemma.clone();
238 for param in params {
239 let witness = subst.get(param)?.clone();
240 let ProofExpr::ForAll { variable, body } = expr else {
241 return None;
242 };
243 debug_assert_eq!(&variable, param);
244 let inst = instantiate_expr(&body, param, &witness);
245 tree = DerivationTree::new(
246 inst.clone(),
247 InferenceRule::UniversalInstTerm(witness),
248 vec![tree],
249 );
250 expr = inst;
251 }
252 Some((expr, tree))
253}
254
255fn collect_expr_terms(e: &ProofExpr, out: &mut Vec<ProofTerm>) {
256 match e {
257 ProofExpr::Predicate { args, .. } => {
258 for a in args {
259 collect_term(a, out);
260 }
261 }
262 ProofExpr::Identity(l, r) => {
263 collect_term(l, out);
264 collect_term(r, out);
265 }
266 ProofExpr::And(l, r)
267 | ProofExpr::Or(l, r)
268 | ProofExpr::Implies(l, r)
269 | ProofExpr::Iff(l, r) => {
270 collect_expr_terms(l, out);
271 collect_expr_terms(r, out);
272 }
273 ProofExpr::Not(p) => collect_expr_terms(p, out),
274 ProofExpr::ForAll { body, .. } | ProofExpr::Exists { body, .. } => {
275 collect_expr_terms(body, out)
276 }
277 _ => {}
278 }
279}
280
281fn collect_term(t: &ProofTerm, out: &mut Vec<ProofTerm>) {
282 out.push(t.clone());
283 if let ProofTerm::Function(_, args) | ProofTerm::Group(args) = t {
284 for a in args {
285 collect_term(a, out);
286 }
287 }
288}
289
290fn dedup_terms(v: &mut Vec<ProofTerm>) {
291 let mut seen = HashSet::new();
292 v.retain(|t| seen.insert(format!("{t}")));
293}