1use logicaffeine_kernel::{Context, Literal, Term};
18
19use crate::discrimination::DiscTree;
20use crate::unify::{
21 apply_subst_to_expr, instantiate_expr, match_expr_pattern, match_term_pattern, Substitution,
22};
23use crate::{DerivationTree, InferenceRule, ProofExpr, ProofTerm};
24
25fn proof_term_of_kernel(t: &Term) -> Option<ProofTerm> {
33 match t {
34 Term::Var(name) => Some(ProofTerm::Variable(name.clone())),
35 Term::Global(name) => Some(ProofTerm::Constant(name.clone())),
36 Term::Lit(Literal::Int(n)) => Some(ProofTerm::Constant(n.to_string())),
37 Term::Lit(Literal::BigInt(n)) => Some(ProofTerm::Constant(n.to_string())),
38 Term::App(..) => {
39 let mut args = Vec::new();
40 let mut head = t;
41 while let Term::App(f, a) = head {
42 args.push(proof_term_of_kernel(a)?);
43 head = f;
44 }
45 args.reverse();
46 let Term::Global(name) = head else {
47 return None;
48 };
49 Some(ProofTerm::Function(name.clone(), args))
50 }
51 _ => None,
52 }
53}
54
55enum RuleCore {
58 TermEq { lhs: ProofTerm, rhs: ProofTerm },
59 PropIff { lhs: ProofExpr, rhs: ProofExpr },
60}
61
62struct CompiledRule {
66 #[allow(dead_code)]
67 name: String,
68 params: Vec<String>,
69 conds: Vec<ProofExpr>,
70 core: RuleCore,
71 lemma: ProofExpr,
72 base: DerivationTree,
73}
74
75#[derive(Default)]
77pub struct SimpSet {
78 rules: Vec<CompiledRule>,
79 term_index: DiscTree<usize>,
80 iff_index: DiscTree<usize>,
81}
82
83pub(crate) struct RewriteStep {
85 pub eq: DerivationTree,
86 pub from: ProofTerm,
87 pub to: ProofTerm,
88}
89
90pub(crate) struct IffStep {
93 pub imp: DerivationTree,
94 pub rhs: ProofExpr,
95}
96
97impl SimpSet {
98 pub fn new() -> Self {
99 Self::default()
100 }
101
102 pub fn len(&self) -> usize {
103 self.rules.len()
104 }
105
106 pub fn is_empty(&self) -> bool {
107 self.rules.is_empty()
108 }
109
110 pub fn register_context_lemmas(&mut self, ctx: &Context) -> usize {
130 let mut added = 0;
131 for rule in ctx.simp_rules() {
132 let (Some(lhs), Some(rhs)) = (
133 proof_term_of_kernel(&rule.lhs),
134 proof_term_of_kernel(&rule.rhs),
135 ) else {
136 continue;
137 };
138 let mut lemma = ProofExpr::Identity(lhs, rhs);
139 for (binder, _) in rule.binders.iter().rev() {
140 lemma = ProofExpr::ForAll {
141 variable: binder.clone(),
142 body: Box::new(lemma),
143 };
144 }
145 if self.register_lemma(&rule.name, &lemma) {
146 added += 1;
147 }
148 }
149 added
150 }
151
152 pub fn register_lemma(&mut self, name: &str, lemma: &ProofExpr) -> bool {
160 let mut params: Vec<String> = Vec::new();
162 let mut body = lemma;
163 while let ProofExpr::ForAll {
164 variable,
165 body: inner,
166 } = body
167 {
168 if params.contains(variable) {
169 return false; }
171 params.push(variable.clone());
172 body = inner;
173 }
174 let mut conds: Vec<ProofExpr> = Vec::new();
176 while let ProofExpr::Implies(c, rest) = body {
177 conds.push((**c).clone());
178 body = rest;
179 }
180 let core = match body {
181 ProofExpr::Identity(l, r) => {
182 if matches!(l, ProofTerm::Variable(_)) {
183 return false; }
185 RuleCore::TermEq {
186 lhs: l.clone(),
187 rhs: r.clone(),
188 }
189 }
190 ProofExpr::Iff(l, r) => RuleCore::PropIff {
191 lhs: (**l).clone(),
192 rhs: (**r).clone(),
193 },
194 _ => return false,
195 };
196 let lhs_vars = match &core {
199 RuleCore::TermEq { lhs, .. } => term_vars(lhs),
200 RuleCore::PropIff { lhs, .. } => expr_vars(lhs),
201 };
202 let rhs_vars = match &core {
203 RuleCore::TermEq { rhs, .. } => term_vars(rhs),
204 RuleCore::PropIff { rhs, .. } => expr_vars(rhs),
205 };
206 if !rhs_vars.iter().all(|v| lhs_vars.contains(v)) {
207 return false;
208 }
209 for c in &conds {
210 if !expr_vars(c).iter().all(|v| lhs_vars.contains(v)) {
211 return false;
212 }
213 }
214 if !params.iter().all(|p| lhs_vars.contains(p)) {
216 return false;
217 }
218
219 let idx = self.rules.len();
220 match &core {
221 RuleCore::TermEq { lhs, .. } => self.term_index.insert_term(lhs, idx),
222 RuleCore::PropIff { lhs, .. } => self.iff_index.insert_expr(lhs, idx),
223 }
224 self.rules.push(CompiledRule {
225 name: name.to_string(),
226 params,
227 conds,
228 core,
229 lemma: lemma.clone(),
230 base: DerivationTree::leaf(lemma.clone(), InferenceRule::PremiseMatch),
231 });
232 true
233 }
234
235 pub(crate) fn find_term_step(
239 &self,
240 goal: &ProofExpr,
241 hyps: &[(&ProofExpr, &DerivationTree)],
242 ) -> Option<RewriteStep> {
243 let mut subterms = Vec::new();
244 collect_goal_terms(goal, &mut subterms);
245 for t in subterms {
246 let mut cand: Vec<usize> = self
247 .term_index
248 .candidates_term(t)
249 .into_iter()
250 .copied()
251 .collect();
252 cand.sort_unstable();
253 cand.dedup();
254 for idx in cand {
255 if let Some(step) = self.try_term_rule(idx, t, hyps) {
256 return Some(step);
257 }
258 }
259 }
260 None
261 }
262
263 pub(crate) fn find_iff_step(
266 &self,
267 goal: &ProofExpr,
268 hyps: &[(&ProofExpr, &DerivationTree)],
269 ) -> Option<IffStep> {
270 let mut cand: Vec<usize> = self
271 .iff_index
272 .candidates_expr(goal)
273 .into_iter()
274 .copied()
275 .collect();
276 cand.sort_unstable();
277 cand.dedup();
278 for idx in cand {
279 let rule = &self.rules[idx];
280 let RuleCore::PropIff { lhs, .. } = &rule.core else {
281 continue;
282 };
283 let Some(subst) = match_expr_pattern(lhs, goal) else {
284 continue;
285 };
286 let Some((tree, concl)) = instantiate_rule(rule, &subst, hyps) else {
287 continue;
288 };
289 let ProofExpr::Iff(l, r) = &concl else {
290 continue;
291 };
292 if l.as_ref() != goal {
293 continue;
294 }
295 let imp = DerivationTree::new(
297 ProofExpr::Implies(r.clone(), l.clone()),
298 InferenceRule::ConjunctionElim,
299 vec![tree],
300 );
301 return Some(IffStep {
302 imp,
303 rhs: (**r).clone(),
304 });
305 }
306 None
307 }
308
309 fn try_term_rule(
310 &self,
311 idx: usize,
312 t: &ProofTerm,
313 hyps: &[(&ProofExpr, &DerivationTree)],
314 ) -> Option<RewriteStep> {
315 let rule = &self.rules[idx];
316 let RuleCore::TermEq { lhs, rhs } = &rule.core else {
317 return None;
318 };
319 let subst = match_term_pattern(lhs, t)?;
320 let (tree, concl) = instantiate_rule(rule, &subst, hyps)?;
321 let ProofExpr::Identity(from, to) = concl else {
322 return None;
323 };
324 if &from != t {
325 return None;
326 }
327 if from == to {
329 return None;
330 }
331 Some(RewriteStep { eq: tree, from, to })
332 }
333}
334
335fn instantiate_rule(
340 rule: &CompiledRule,
341 subst: &Substitution,
342 hyps: &[(&ProofExpr, &DerivationTree)],
343) -> Option<(DerivationTree, ProofExpr)> {
344 let mut tree = rule.base.clone();
345 let mut expr = rule.lemma.clone();
346 for param in &rule.params {
347 let witness = subst.get(param)?.clone();
348 let ProofExpr::ForAll { variable, body } = expr else {
349 return None;
350 };
351 debug_assert_eq!(&variable, param);
352 let inst = instantiate_expr(&body, param, &witness);
353 tree = DerivationTree::new(
354 inst.clone(),
355 InferenceRule::UniversalInstTerm(witness),
356 vec![tree],
357 );
358 expr = inst;
359 }
360 for _ in 0..rule.conds.len() {
361 let ProofExpr::Implies(cond, rest) = expr else {
362 return None;
363 };
364 let cond_proof = discharge_condition(&cond, hyps)?;
365 tree = DerivationTree::new(
366 (*rest).clone(),
367 InferenceRule::ModusPonens,
368 vec![tree, cond_proof],
369 );
370 expr = *rest;
371 }
372 Some((tree, expr))
373}
374
375fn discharge_condition(
379 cond: &ProofExpr,
380 hyps: &[(&ProofExpr, &DerivationTree)],
381) -> Option<DerivationTree> {
382 if let Some((_, proof)) = hyps.iter().find(|(prop, _)| *prop == cond) {
383 return Some((*proof).clone());
384 }
385 if let ProofExpr::Identity(l, r) = cond {
386 if ground_int(l).is_some() && ground_int(r).is_some() {
387 return Some(DerivationTree::leaf(
388 cond.clone(),
389 InferenceRule::ArithDecision,
390 ));
391 }
392 }
393 None
394}
395
396pub(crate) fn find_ground_fold(goal: &ProofExpr) -> Option<RewriteStep> {
400 let mut subterms = Vec::new();
401 collect_goal_terms(goal, &mut subterms);
402 for t in subterms {
403 let ProofTerm::Function(op, args) = t else {
404 continue;
405 };
406 if args.len() != 2 {
407 continue;
408 }
409 let (Some(a), Some(b)) = (ground_int(&args[0]), ground_int(&args[1])) else {
410 continue;
411 };
412 let result = match op.as_str() {
413 "add" => a.checked_add(b),
414 "sub" => a.checked_sub(b),
415 "mul" => a.checked_mul(b),
416 _ => None,
417 }?;
418 let to = ProofTerm::Constant(result.to_string());
419 if &to == t {
420 continue;
421 }
422 let eq = DerivationTree::leaf(
423 ProofExpr::Identity(t.clone(), to.clone()),
424 InferenceRule::ArithDecision,
425 );
426 return Some(RewriteStep {
427 eq,
428 from: t.clone(),
429 to,
430 });
431 }
432 None
433}
434
435fn ground_int(t: &ProofTerm) -> Option<i64> {
436 match t {
437 ProofTerm::Constant(s) => s.parse::<i64>().ok(),
438 _ => None,
439 }
440}
441
442fn collect_goal_terms<'a>(e: &'a ProofExpr, out: &mut Vec<&'a ProofTerm>) {
444 fn walk_term<'a>(t: &'a ProofTerm, out: &mut Vec<&'a ProofTerm>) {
445 match t {
446 ProofTerm::Function(_, args) | ProofTerm::Group(args) => {
447 for a in args {
448 walk_term(a, out);
449 }
450 }
451 _ => {}
452 }
453 if !out.contains(&t) {
454 out.push(t);
455 }
456 }
457 match e {
458 ProofExpr::Predicate { args, .. } => {
459 for a in args {
460 walk_term(a, out);
461 }
462 }
463 ProofExpr::Identity(l, r) => {
464 walk_term(l, out);
465 walk_term(r, out);
466 }
467 ProofExpr::And(l, r)
468 | ProofExpr::Or(l, r)
469 | ProofExpr::Implies(l, r)
470 | ProofExpr::Iff(l, r) => {
471 collect_goal_terms(l, out);
472 collect_goal_terms(r, out);
473 }
474 ProofExpr::Not(p) => collect_goal_terms(p, out),
475 ProofExpr::ForAll { body, .. } | ProofExpr::Exists { body, .. } => {
476 collect_goal_terms(body, out)
477 }
478 _ => {}
479 }
480}
481
482fn term_vars(t: &ProofTerm) -> Vec<String> {
483 let mut out = Vec::new();
484 collect_term_vars(t, &mut out);
485 out
486}
487
488fn collect_term_vars(t: &ProofTerm, out: &mut Vec<String>) {
489 match t {
490 ProofTerm::Variable(n) => {
491 if !out.contains(n) {
492 out.push(n.clone());
493 }
494 }
495 ProofTerm::Function(_, args) | ProofTerm::Group(args) => {
496 for a in args {
497 collect_term_vars(a, out);
498 }
499 }
500 _ => {}
501 }
502}
503
504fn expr_vars(e: &ProofExpr) -> Vec<String> {
505 let mut out = Vec::new();
506 collect_expr_vars(e, &mut out);
507 out
508}
509
510fn collect_expr_vars(e: &ProofExpr, out: &mut Vec<String>) {
511 match e {
512 ProofExpr::Predicate { args, .. } => {
513 for a in args {
514 collect_term_vars(a, out);
515 }
516 }
517 ProofExpr::Identity(l, r) => {
518 collect_term_vars(l, out);
519 collect_term_vars(r, out);
520 }
521 ProofExpr::And(l, r)
522 | ProofExpr::Or(l, r)
523 | ProofExpr::Implies(l, r)
524 | ProofExpr::Iff(l, r) => {
525 collect_expr_vars(l, out);
526 collect_expr_vars(r, out);
527 }
528 ProofExpr::Not(p) => collect_expr_vars(p, out),
529 ProofExpr::ForAll { variable, body } | ProofExpr::Exists { variable, body } => {
530 let mut inner = Vec::new();
531 collect_expr_vars(body, &mut inner);
532 for v in inner {
533 if v != *variable && !out.contains(&v) {
534 out.push(v);
535 }
536 }
537 }
538 _ => {}
539 }
540}