1#![allow(dead_code)]
21
22use crate::{DerivationTree, InferenceRule, ProofExpr};
23
24fn leaf(e: ProofExpr) -> DerivationTree {
27 DerivationTree::leaf(e, InferenceRule::PremiseMatch)
28}
29
30fn neg(e: &ProofExpr) -> ProofExpr {
31 match e {
32 ProofExpr::Not(inner) => (**inner).clone(),
33 _ => ProofExpr::Not(Box::new(e.clone())),
34 }
35}
36
37fn falsum() -> ProofExpr {
38 ProofExpr::Atom("⊥".into())
39}
40
41fn modus_ponens(
43 c: ProofExpr,
44 impl_tree: DerivationTree,
45 ante_tree: DerivationTree,
46) -> DerivationTree {
47 DerivationTree::new(c, InferenceRule::ModusPonens, vec![impl_tree, ante_tree])
48}
49
50fn disjunction_elim(
52 survivor: ProofExpr,
53 or_tree: DerivationTree,
54 neg_tree: DerivationTree,
55) -> DerivationTree {
56 DerivationTree::new(
57 survivor,
58 InferenceRule::DisjunctionElim,
59 vec![or_tree, neg_tree],
60 )
61}
62
63fn conj_intro(a: ProofExpr, b: ProofExpr, l: DerivationTree, r: DerivationTree) -> DerivationTree {
65 DerivationTree::new(
66 ProofExpr::And(Box::new(a), Box::new(b)),
67 InferenceRule::ConjunctionIntro,
68 vec![l, r],
69 )
70}
71
72fn contradiction(p: DerivationTree, np: DerivationTree) -> DerivationTree {
74 DerivationTree::new(falsum(), InferenceRule::Contradiction, vec![p, np])
75}
76
77fn reductio(assumed: ProofExpr, falsum_tree: DerivationTree) -> DerivationTree {
79 let concl = ProofExpr::Not(Box::new(assumed.clone()));
80 DerivationTree::new(
81 concl,
82 InferenceRule::ReductioAdAbsurdum,
83 vec![leaf(assumed), falsum_tree],
84 )
85}
86
87fn eq_sym(a: crate::ProofTerm, b: crate::ProofTerm, tree: DerivationTree) -> DerivationTree {
89 DerivationTree::new(
90 ProofExpr::Identity(b, a),
91 InferenceRule::EqualitySymmetry,
92 vec![tree],
93 )
94}
95
96fn disjunction_cases(
100 goal: ProofExpr,
101 or_tree: DerivationTree,
102 left: DerivationTree,
103 right: DerivationTree,
104) -> DerivationTree {
105 DerivationTree::new(
106 goal,
107 InferenceRule::DisjunctionCases,
108 vec![or_tree, left, right],
109 )
110}
111
112fn conj_elim(conjunct: ProofExpr, and_tree: DerivationTree) -> DerivationTree {
114 DerivationTree::new(conjunct, InferenceRule::ConjunctionElim, vec![and_tree])
115}
116
117use crate::ProofTerm;
120use std::collections::HashMap;
121
122type Var = usize;
123
124#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
125struct Lit {
126 var: Var,
127 pos: bool,
128}
129
130impl Lit {
131 fn negate(self) -> Lit {
132 Lit {
133 var: self.var,
134 pos: !self.pos,
135 }
136 }
137}
138
139fn term_key(t: &ProofTerm) -> String {
140 t.to_string()
141}
142
143fn atom_key(e: &ProofExpr) -> Option<String> {
146 match e {
147 ProofExpr::Predicate { name, args, .. } => {
148 let parts: Vec<String> = args.iter().map(term_key).collect();
149 Some(format!("P:{}({})", name, parts.join(",")))
150 }
151 ProofExpr::Identity(a, b) => {
152 let (ka, kb) = (term_key(a), term_key(b));
153 let (lo, hi) = if ka <= kb { (ka, kb) } else { (kb, ka) };
154 Some(format!("=:{}|{}", lo, hi))
155 }
156 ProofExpr::Atom(s) => Some(format!("A:{}", s)),
157 _ => None,
158 }
159}
160
161fn is_atomish(e: &ProofExpr) -> bool {
162 matches!(
163 e,
164 ProofExpr::Predicate { .. } | ProofExpr::Identity(..) | ProofExpr::Atom(_)
165 )
166}
167
168fn is_literal(e: &ProofExpr) -> bool {
169 match e {
170 ProofExpr::Not(inner) => is_atomish(inner),
171 _ => is_atomish(e),
172 }
173}
174
175fn is_clause_disjunct(e: &ProofExpr) -> bool {
179 match e {
180 ProofExpr::And(l, r) | ProofExpr::Or(l, r) => {
181 is_clause_disjunct(l) && is_clause_disjunct(r)
182 }
183 _ => is_literal(e),
184 }
185}
186
187fn flatten_and(e: &ProofExpr, out: &mut Vec<ProofExpr>) {
188 match e {
189 ProofExpr::And(l, r) => {
190 flatten_and(l, out);
191 flatten_and(r, out);
192 }
193 _ => out.push(e.clone()),
194 }
195}
196
197fn flatten_or(e: &ProofExpr, out: &mut Vec<ProofExpr>) {
198 match e {
199 ProofExpr::Or(l, r) => {
200 flatten_or(l, out);
201 flatten_or(r, out);
202 }
203 _ => out.push(e.clone()),
204 }
205}
206
207fn intern_all(table: &mut AtomTable, e: &ProofExpr) {
210 match e {
211 ProofExpr::And(l, r)
212 | ProofExpr::Or(l, r)
213 | ProofExpr::Implies(l, r)
214 | ProofExpr::Iff(l, r) => {
215 intern_all(table, l);
216 intern_all(table, r);
217 }
218 ProofExpr::Not(inner) => intern_all(table, inner),
219 _ if is_atomish(e) => {
220 table.intern(e);
221 }
222 _ => {}
223 }
224}
225
226#[derive(Default)]
227struct AtomTable {
228 by_key: HashMap<String, Var>,
229 atoms: Vec<ProofExpr>,
230}
231
232impl AtomTable {
233 fn intern(&mut self, atom: &ProofExpr) -> Option<Var> {
234 let k = atom_key(atom)?;
235 if let Some(&v) = self.by_key.get(&k) {
236 return Some(v);
237 }
238 let v = self.atoms.len();
239 self.atoms.push(atom.clone());
240 self.by_key.insert(k, v);
241 Some(v)
242 }
243
244 fn lit(&mut self, e: &ProofExpr) -> Option<Lit> {
245 match e {
246 ProofExpr::Not(inner) => Some(Lit {
247 var: self.intern(inner)?,
248 pos: false,
249 }),
250 _ => Some(Lit {
251 var: self.intern(e)?,
252 pos: true,
253 }),
254 }
255 }
256}
257
258enum ClauseSrc {
261 Bare(ProofExpr),
263 FromRule(usize),
265 Assumed(ProofExpr),
268}
269
270struct Clause {
274 or_expr: ProofExpr,
275 disjuncts: Vec<ProofExpr>,
276 lits: Option<Vec<Lit>>,
277 src: ClauseSrc,
278}
279
280enum RuleCons {
281 Lit(Lit),
282 Disj(Vec<Lit>),
283}
284
285#[derive(Clone, Copy, PartialEq, Eq)]
287enum Tri {
288 True,
289 False,
290 Live,
291}
292
293struct Rule {
294 ante: Vec<Lit>,
295 cons: RuleCons,
296 src: ProofExpr,
298}
299
300#[derive(Clone)]
303enum Reason {
304 Premise(ProofExpr),
306 Rule(usize),
308 Exclude(usize),
311 Clause(usize),
313 CompoundClause { clause: usize, disjunct: usize },
319 Assumption,
321}
322
323struct Solver {
326 table: AtomTable,
327 clauses: Vec<Clause>,
328 rules: Vec<Rule>,
329 assign: Vec<Option<bool>>,
330 reason: Vec<Option<Reason>>,
331 trail: Vec<Var>,
332 pos: Vec<usize>,
336 fired_disj: Vec<bool>,
337 deciding: std::collections::HashSet<usize>,
340 at_root: bool,
347}
348
349enum Conflict {
350 Rule(usize),
352 Clause(usize),
354}
355
356fn compile(premises: &[ProofExpr]) -> Option<Solver> {
360 let mut table = AtomTable::default();
361 let mut clauses = Vec::new();
362 let mut rules = Vec::new();
363 let mut units: Vec<(Lit, ProofExpr)> = Vec::new();
364
365 let mut flat: Vec<ProofExpr> = Vec::new();
368 for p in premises {
369 flatten_and(p, &mut flat);
370 }
371
372 for p in &flat {
377 match p {
378 ProofExpr::Or(..) => {
379 let mut ds = Vec::new();
380 flatten_or(p, &mut ds);
381 if !ds.iter().all(is_clause_disjunct) {
382 continue;
383 }
384 intern_all(&mut table, p);
385 let lits = if ds.iter().all(is_literal) {
386 ds.iter()
387 .map(|d| table.lit(d))
388 .collect::<Option<Vec<Lit>>>()
389 } else {
390 None
391 };
392 clauses.push(Clause {
393 or_expr: p.clone(),
394 disjuncts: ds,
395 lits,
396 src: ClauseSrc::Bare(p.clone()),
397 });
398 }
399 ProofExpr::Implies(ante, cons) => {
400 let mut as_ = Vec::new();
401 flatten_and(ante, &mut as_);
402 if !as_.iter().all(is_literal) {
403 continue;
404 }
405 let cons_form = if is_literal(cons) {
406 intern_all(&mut table, p);
407 RuleCons::Lit(table.lit(cons).unwrap())
408 } else if matches!(cons.as_ref(), ProofExpr::Or(..)) {
409 let mut ds = Vec::new();
410 flatten_or(cons, &mut ds);
411 if !ds.iter().all(is_literal) {
412 continue;
413 }
414 intern_all(&mut table, p);
415 RuleCons::Disj(ds.iter().map(|d| table.lit(d).unwrap()).collect())
416 } else {
417 continue;
418 };
419 let ante_lits = as_.iter().map(|a| table.lit(a).unwrap()).collect();
420 rules.push(Rule {
421 ante: ante_lits,
422 cons: cons_form,
423 src: p.clone(),
424 });
425 }
426 _ if is_literal(p) => {
427 intern_all(&mut table, p);
428 units.push((table.lit(p).unwrap(), p.clone()));
429 }
430 _ => continue,
431 }
432 }
433
434 let n = table.atoms.len();
435 let fired_disj = vec![false; rules.len()];
436 let mut solver = Solver {
437 table,
438 clauses,
439 rules,
440 assign: vec![None; n],
441 reason: vec![None; n],
442 trail: Vec::new(),
443 pos: vec![usize::MAX; n],
444 fired_disj,
445 deciding: std::collections::HashSet::new(),
446 at_root: false,
447 };
448 for (l, expr) in units {
449 let _ = solver.set(l, Reason::Premise(expr));
450 }
451 Some(solver)
452}
453
454impl Solver {
455 fn value(&self, l: Lit) -> Option<bool> {
457 self.assign[l.var].map(|b| b == l.pos)
458 }
459
460 fn var_of_atom(&self, atom: &ProofExpr) -> Option<Var> {
461 self.table.by_key.get(&atom_key(atom)?).copied()
462 }
463
464 fn lit_of(&self, e: &ProofExpr) -> Option<Lit> {
465 match e {
466 ProofExpr::Not(inner) => Some(Lit {
467 var: self.var_of_atom(inner)?,
468 pos: false,
469 }),
470 _ => Some(Lit {
471 var: self.var_of_atom(e)?,
472 pos: true,
473 }),
474 }
475 }
476
477 fn lit_expr(&self, l: Lit) -> ProofExpr {
478 let atom = self.table.atoms[l.var].clone();
479 if l.pos {
480 atom
481 } else {
482 ProofExpr::Not(Box::new(atom))
483 }
484 }
485
486 fn set(&mut self, l: Lit, r: Reason) -> Result<(), ()> {
487 match self.assign[l.var] {
488 Some(b) => {
489 if b == l.pos {
490 Ok(())
491 } else {
492 Err(())
493 }
494 }
495 None => {
496 self.assign[l.var] = Some(l.pos);
497 self.reason[l.var] = Some(r);
498 self.pos[l.var] = self.trail.len();
499 self.trail.push(l.var);
500 Ok(())
501 }
502 }
503 }
504
505 fn propagate(&mut self) -> Result<(), Conflict> {
509 loop {
510 let mut changed = false;
511
512 for ri in 0..self.rules.len() {
513 let mut n_nonsat = 0usize;
515 let mut the_nonsat: Option<Lit> = None;
516 let mut any_false = false;
517 for i in 0..self.rules[ri].ante.len() {
518 let a = self.rules[ri].ante[i];
519 match self.value(a) {
520 Some(true) => {}
521 Some(false) => {
522 any_false = true;
523 n_nonsat += 1;
524 the_nonsat = Some(a);
525 }
526 None => {
527 n_nonsat += 1;
528 the_nonsat = Some(a);
529 }
530 }
531 }
532
533 if any_false {
535 continue;
536 }
537
538 if n_nonsat == 0 {
539 match &self.rules[ri].cons {
541 RuleCons::Lit(l) => {
542 let l = *l;
543 match self.value(l) {
544 Some(true) => {}
545 Some(false) => return Err(Conflict::Rule(ri)),
546 None => {
547 let _ = self.set(l, Reason::Rule(ri));
548 changed = true;
549 }
550 }
551 }
552 RuleCons::Disj(lits) => {
553 if !self.fired_disj[ri] {
554 let lits = lits.clone();
555 self.fired_disj[ri] = true;
556 let (_, cons_form) = Self::split_implies(&self.rules[ri].src);
557 let mut ds = Vec::new();
558 flatten_or(&cons_form, &mut ds);
559 self.clauses.push(Clause {
560 or_expr: cons_form,
561 disjuncts: ds,
562 lits: Some(lits),
563 src: ClauseSrc::FromRule(ri),
564 });
565 changed = true;
566 }
567 }
568 }
569 } else if n_nonsat == 1 {
570 if let RuleCons::Lit(l) = &self.rules[ri].cons {
573 if self.value(*l) == Some(false) {
574 let open = the_nonsat.unwrap();
575 if self.value(open).is_none() {
576 let _ = self.set(open.negate(), Reason::Exclude(ri));
577 changed = true;
578 }
579 }
580 }
581 }
582 }
583
584 for ci in 0..self.clauses.len() {
585 let (has_true, live) = self.clause_status(ci);
586 if has_true {
587 continue;
588 }
589 if live.is_empty() {
590 return Err(Conflict::Clause(ci));
591 }
592 if self.clauses[ci].lits.is_some() && live.len() == 1 {
594 if let Some(l) = self.lit_of(&self.clauses[ci].disjuncts[live[0]]) {
595 if self.set(l, Reason::Clause(ci)).is_ok() {
596 changed = true;
597 }
598 }
599 }
600 if self.at_root && self.clauses[ci].lits.is_none() && live.len() == 1 {
608 let di = live[0];
609 let mut conjs = Vec::new();
610 flatten_and(&self.clauses[ci].disjuncts[di].clone(), &mut conjs);
611 for conj in &conjs {
612 if !is_literal(conj) {
615 continue;
616 }
617 let Some(l) = self.lit_of(conj) else { continue };
618 match self.value(l) {
619 Some(true) => {}
620 Some(false) => return Err(Conflict::Clause(ci)),
621 None => {
622 let _ = self.set(
623 l,
624 Reason::CompoundClause {
625 clause: ci,
626 disjunct: di,
627 },
628 );
629 changed = true;
630 }
631 }
632 }
633 }
634 }
635
636 if !changed {
637 break;
638 }
639 }
640 Ok(())
641 }
642
643 fn prove_var(&self, v: Var) -> DerivationTree {
647 let val = self.assign[v].expect("prove_var on unassigned variable");
648 match self.reason[v]
649 .as_ref()
650 .expect("assigned variable lacks a reason")
651 {
652 Reason::Premise(expr) => leaf(expr.clone()),
653 Reason::Assumption => leaf(self.lit_expr(Lit { var: v, pos: val })),
654 Reason::Rule(ri) => self.emit_rule_forward(*ri),
655 Reason::Exclude(ri) => self.emit_rule_exclude(*ri, v),
656 Reason::Clause(ci) => self.emit_clause_survivor(*ci, Lit { var: v, pos: val }),
657 Reason::CompoundClause { clause, disjunct } => {
658 self.emit_compound_clause(*clause, *disjunct, Lit { var: v, pos: val })
659 }
660 }
661 }
662
663 fn emit_compound_clause(&self, ci: usize, di: usize, want: Lit) -> DerivationTree {
668 let or_expr = self.clauses[ci].or_expr.clone();
669 let or_tree = self.materialize_clause(ci);
670 let survivor = self.clauses[ci].disjuncts[di].clone();
671 let before = self.pos[want.var];
672 let surv_tree = self.extract_survivor(&or_expr, or_tree, &survivor, before);
673 let proj = self.project_conjunct(&survivor, surv_tree, want);
674 align_to(proj, &self.lit_expr(want))
675 }
676
677 fn project_conjunct(
680 &self,
681 conj: &ProofExpr,
682 conj_tree: DerivationTree,
683 want: Lit,
684 ) -> DerivationTree {
685 match conj {
686 ProofExpr::And(l, r) => {
687 if self.conjunct_has(l, want) {
688 let lt = conj_elim((**l).clone(), conj_tree);
689 self.project_conjunct(l, lt, want)
690 } else {
691 let rt = conj_elim((**r).clone(), conj_tree);
692 self.project_conjunct(r, rt, want)
693 }
694 }
695 _ => conj_tree,
696 }
697 }
698
699 fn conjunct_has(&self, e: &ProofExpr, want: Lit) -> bool {
701 match e {
702 ProofExpr::And(l, r) => self.conjunct_has(l, want) || self.conjunct_has(r, want),
703 _ => self.lit_of(e) == Some(want),
704 }
705 }
706
707 fn prove_lit_expr(&self, want: &ProofExpr) -> DerivationTree {
709 let lit = self
710 .lit_of(want)
711 .expect("prove_lit_expr on an un-interned atom");
712 let base = self.prove_var(lit.var);
713 align_to(base, want)
714 }
715
716 fn split_implies(src: &ProofExpr) -> (ProofExpr, ProofExpr) {
717 match src {
718 ProofExpr::Implies(a, c) => ((**a).clone(), (**c).clone()),
719 _ => unreachable!("rule src is always an implication"),
720 }
721 }
722
723 fn prove_ante(&self, form: &ProofExpr, forced: Option<Var>) -> DerivationTree {
726 match form {
727 ProofExpr::And(l, r) => conj_intro(
728 (**l).clone(),
729 (**r).clone(),
730 self.prove_ante(l, forced),
731 self.prove_ante(r, forced),
732 ),
733 _ => {
734 if let (Some(fv), Some(lit)) = (forced, self.lit_of(form)) {
735 if lit.var == fv {
736 return leaf(form.clone());
737 }
738 }
739 self.prove_lit_expr(form)
740 }
741 }
742 }
743
744 fn emit_rule_forward(&self, ri: usize) -> DerivationTree {
745 let src = self.rules[ri].src.clone();
746 let (ante_form, cons_form) = Self::split_implies(&src);
747 let ante_proof = self.prove_ante(&ante_form, None);
748 modus_ponens(cons_form, leaf(src), ante_proof)
749 }
750
751 fn emit_rule_exclude(&self, ri: usize, forced_v: Var) -> DerivationTree {
752 let src = self.rules[ri].src.clone();
753 let (ante_form, cons_form) = Self::split_implies(&src);
754 let assumed = self.table.atoms[forced_v].clone();
755 let ante_proof = self.prove_ante(&ante_form, Some(forced_v));
756 let cons_tree = modus_ponens(cons_form.clone(), leaf(src), ante_proof);
757 let cons_lit = self
758 .lit_of(&cons_form)
759 .expect("exclusion consequent must be a literal");
760 let neg_cons = self.prove_var(cons_lit.var);
761 let bot = make_contradiction(cons_tree, neg_cons);
764 reductio(assumed, bot)
765 }
766
767 fn materialize_clause(&self, ci: usize) -> DerivationTree {
768 match &self.clauses[ci].src {
769 ClauseSrc::Bare(or_expr) | ClauseSrc::Assumed(or_expr) => leaf(or_expr.clone()),
770 ClauseSrc::FromRule(ri) => {
771 let src = self.rules[*ri].src.clone();
772 let (ante_form, cons_form) = Self::split_implies(&src);
773 let ante_proof = self.prove_ante(&ante_form, None);
774 modus_ponens(cons_form, leaf(src), ante_proof)
775 }
776 }
777 }
778
779 fn emit_clause_survivor(&self, ci: usize, survivor: Lit) -> DerivationTree {
780 let or_tree = self.materialize_clause(ci);
781 let or_expr = or_tree.conclusion.clone();
782 let survivor_expr = self.lit_expr(survivor);
783 let before = self.pos[survivor.var];
784 self.extract_survivor(&or_expr, or_tree, &survivor_expr, before)
785 }
786
787 fn extract_survivor(
791 &self,
792 or_expr: &ProofExpr,
793 or_tree: DerivationTree,
794 target: &ProofExpr,
795 before: usize,
796 ) -> DerivationTree {
797 match or_expr {
798 ProofExpr::Or(l, r) => {
799 if r.as_ref() == target {
800 let lneg = self.prove_neg_disjunct(l, before);
801 disjunction_elim(target.clone(), or_tree, lneg)
802 } else {
803 let rneg = self.prove_neg_disjunct(r, before);
804 let l_tree = disjunction_elim((**l).clone(), or_tree, rneg);
805 self.extract_survivor(l, l_tree, target, before)
806 }
807 }
808 _ => or_tree,
809 }
810 }
811
812 fn prove_neg_disjunct(&self, e: &ProofExpr, before: usize) -> DerivationTree {
816 if is_literal(e) {
817 let lit = self.lit_of(e).expect("disjunct atom must be interned");
818 let proof = self.prove_var(lit.var);
819 align_to(proof, &neg_of(e))
820 } else {
821 let bot = self.falsum_from_disj(e, leaf(e.clone()), before);
822 reductio(e.clone(), bot)
823 }
824 }
825
826 fn falsum_from_disj(
829 &self,
830 e: &ProofExpr,
831 e_tree: DerivationTree,
832 before: usize,
833 ) -> DerivationTree {
834 match e {
835 ProofExpr::Or(l, r) => {
836 let lb = self.falsum_from_disj(l, leaf((**l).clone()), before);
837 let rb = self.falsum_from_disj(r, leaf((**r).clone()), before);
838 disjunction_cases(falsum(), e_tree, lb, rb)
839 }
840 ProofExpr::And(l, r) => {
841 let key = |x: &ProofExpr| {
848 self.false_at(x, before)
849 .map(|p| (0u8, p))
850 .or_else(|| self.false_at(x, usize::MAX).map(|p| (1u8, p)))
851 };
852 let pick_left = match (key(l), key(r)) {
853 (Some(a), Some(b)) => a <= b,
854 (Some(_), None) => true,
855 (None, Some(_)) => false,
856 (None, None) => true,
857 };
858 let (conjunct, proj) = if pick_left {
859 ((**l).clone(), conj_elim((**l).clone(), e_tree))
860 } else {
861 ((**r).clone(), conj_elim((**r).clone(), e_tree))
862 };
863 self.falsum_from_disj(&conjunct, proj, before)
864 }
865 _ => {
866 let lit = self.lit_of(e).expect("disjunct atom must be interned");
867 let neg = self.prove_var(lit.var);
868 contra_align(e_tree, neg)
869 }
870 }
871 }
872
873 fn false_at(&self, e: &ProofExpr, before: usize) -> Option<usize> {
880 match e {
881 ProofExpr::And(l, r) => match (self.false_at(l, before), self.false_at(r, before)) {
882 (Some(a), Some(b)) => Some(a.min(b)),
883 (a, b) => a.or(b),
884 },
885 ProofExpr::Or(l, r) => match (self.false_at(l, before), self.false_at(r, before)) {
886 (Some(a), Some(b)) => Some(a.max(b)),
887 _ => None,
888 },
889 _ => match self.lit_of(e) {
890 Some(l) if self.value(l) == Some(false) && self.pos[l.var] < before => {
891 Some(self.pos[l.var])
892 }
893 _ => None,
894 },
895 }
896 }
897
898 fn eval_disjunct(&self, e: &ProofExpr) -> Tri {
901 match e {
902 ProofExpr::And(l, r) => match (self.eval_disjunct(l), self.eval_disjunct(r)) {
903 (Tri::False, _) | (_, Tri::False) => Tri::False,
904 (Tri::True, Tri::True) => Tri::True,
905 _ => Tri::Live,
906 },
907 ProofExpr::Or(l, r) => match (self.eval_disjunct(l), self.eval_disjunct(r)) {
908 (Tri::True, _) | (_, Tri::True) => Tri::True,
909 (Tri::False, Tri::False) => Tri::False,
910 _ => Tri::Live,
911 },
912 _ => match self.lit_of(e).and_then(|l| self.value(l)) {
913 Some(true) => Tri::True,
914 Some(false) => Tri::False,
915 None => Tri::Live,
916 },
917 }
918 }
919
920 fn clause_status(&self, ci: usize) -> (bool, Vec<usize>) {
922 let mut has_true = false;
923 let mut live = Vec::new();
924 for (i, d) in self.clauses[ci].disjuncts.iter().enumerate() {
925 match self.eval_disjunct(d) {
926 Tri::True => has_true = true,
927 Tri::Live => live.push(i),
928 Tri::False => {}
929 }
930 }
931 (has_true, live)
932 }
933
934 fn pick_split(&self) -> Option<usize> {
938 (0..self.clauses.len())
944 .filter(|&ci| {
945 if self.deciding.contains(&ci) {
946 return false;
947 }
948 let (has_true, live) = self.clause_status(ci);
949 if has_true || live.is_empty() {
950 return false;
951 }
952 !(self.clauses[ci].lits.is_some() && live.len() < 2)
954 })
955 .min_by_key(|&ci| self.clause_status(ci).1.len())
956 }
957
958 fn derive_falsum(&mut self, depth: usize) -> Option<DerivationTree> {
961 if depth > MAX_DEPTH {
962 return None;
963 }
964 if let Err(c) = self.propagate() {
965 return Some(self.emit_conflict(c));
966 }
967 let ci = self.pick_split()?;
968 let or_expr = self.clauses[ci].or_expr.clone();
969 let or_tree = self.materialize_clause(ci);
970 self.deciding.insert(ci);
971 let result = self.split_to_falsum(&or_expr, or_tree, depth);
972 self.deciding.remove(&ci);
973 result
974 }
975
976 fn split_to_falsum(
977 &mut self,
978 or_expr: &ProofExpr,
979 or_tree: DerivationTree,
980 depth: usize,
981 ) -> Option<DerivationTree> {
982 match or_expr {
983 ProofExpr::Or(l, r) => {
984 let lb = self.branch(l, depth)?;
985 let rb = self.branch(r, depth)?;
986 Some(disjunction_cases(falsum(), or_tree, lb, rb))
987 }
988 single => self.branch(single, depth),
989 }
990 }
991
992 fn branch(&mut self, disjunct: &ProofExpr, depth: usize) -> Option<DerivationTree> {
995 let trail_snap = self.trail.len();
996 let clause_snap = self.clauses.len();
997 let fired_snap = self.fired_disj.clone();
998 let result = match self.assume_disjunct(disjunct) {
999 Some(info) => Some(self.emit_conflict_info(info)),
1000 None => self.derive_falsum(depth + 1),
1001 };
1002 self.backtrack(trail_snap, clause_snap, fired_snap);
1003 result
1004 }
1005
1006 fn assume_disjunct(&mut self, d: &ProofExpr) -> Option<ConflictInfo> {
1009 match d {
1010 ProofExpr::And(l, r) => self.assume_disjunct(l).or_else(|| self.assume_disjunct(r)),
1011 ProofExpr::Or(..) => {
1012 let mut ds = Vec::new();
1013 flatten_or(d, &mut ds);
1014 let lits = if ds.iter().all(is_literal) {
1015 ds.iter()
1016 .map(|x| self.lit_of(x))
1017 .collect::<Option<Vec<Lit>>>()
1018 } else {
1019 None
1020 };
1021 self.clauses.push(Clause {
1022 or_expr: d.clone(),
1023 disjuncts: ds,
1024 lits,
1025 src: ClauseSrc::Assumed(d.clone()),
1026 });
1027 None
1028 }
1029 _ => {
1030 let lit = self.lit_of(d).expect("assumed atom must be interned");
1031 if self.set(lit, Reason::Assumption).is_err() {
1032 Some(ConflictInfo::Clash { assumed: d.clone() })
1033 } else {
1034 None
1035 }
1036 }
1037 }
1038 }
1039
1040 fn backtrack(&mut self, trail_snap: usize, clause_snap: usize, fired_snap: Vec<bool>) {
1041 while self.trail.len() > trail_snap {
1042 let v = self.trail.pop().unwrap();
1043 self.assign[v] = None;
1044 self.reason[v] = None;
1045 }
1046 self.clauses.truncate(clause_snap);
1047 self.fired_disj = fired_snap;
1048 }
1049
1050 fn emit_conflict(&self, c: Conflict) -> DerivationTree {
1051 match c {
1052 Conflict::Rule(ri) => {
1053 let src = self.rules[ri].src.clone();
1054 let (ante_form, cons_form) = Self::split_implies(&src);
1055 let ante_proof = self.prove_ante(&ante_form, None);
1056 let cons_tree = modus_ponens(cons_form.clone(), leaf(src), ante_proof);
1057 let cons_lit = self
1058 .lit_of(&cons_form)
1059 .expect("rule consequent is a literal");
1060 let opp = self.prove_var(cons_lit.var);
1061 make_contradiction(cons_tree, opp)
1062 }
1063 Conflict::Clause(ci) => {
1064 let or_expr = self.clauses[ci].or_expr.clone();
1065 let or_tree = self.materialize_clause(ci);
1066 self.falsum_from_disj(&or_expr, or_tree, usize::MAX)
1067 }
1068 }
1069 }
1070
1071 fn emit_conflict_info(&self, info: ConflictInfo) -> DerivationTree {
1072 match info {
1073 ConflictInfo::Clash { assumed } => {
1074 let lit = self
1075 .lit_of(&assumed)
1076 .expect("clashing atom must be interned");
1077 let existing = self.prove_var(lit.var);
1078 make_contradiction(leaf(assumed), existing)
1079 }
1080 ConflictInfo::Rule(ri) => self.emit_conflict(Conflict::Rule(ri)),
1081 ConflictInfo::Clause(ci) => self.emit_conflict(Conflict::Clause(ci)),
1082 }
1083 }
1084
1085 fn prove_positive_by_closure(&mut self, goal: &ProofExpr) -> Option<DerivationTree> {
1091 let goal_lit = self.lit_of(goal)?;
1092 let mut candidates: Vec<usize> = (0..self.clauses.len())
1100 .filter(|&ci| {
1101 self.clauses[ci]
1102 .lits
1103 .as_ref()
1104 .map_or(false, |ls| ls.contains(&goal_lit) && ls.len() >= 2)
1105 })
1106 .collect();
1107 candidates.sort_by_key(|&ci| self.clause_status(ci).1.len());
1108 for ci in candidates {
1109 let or_expr = self.clauses[ci].or_expr.clone();
1110 let or_tree = self.materialize_clause(ci);
1111 if let Some(tree) = self.extract_by_search(&or_expr, or_tree, goal) {
1112 return Some(tree);
1113 }
1114 }
1115 None
1116 }
1117
1118 fn extract_by_search(
1121 &mut self,
1122 or_expr: &ProofExpr,
1123 or_tree: DerivationTree,
1124 target: &ProofExpr,
1125 ) -> Option<DerivationTree> {
1126 debug_assert!(
1127 &or_tree.conclusion == or_expr,
1128 "extract_by_search mismatch:\n tree={:?}\n expr={:?}",
1129 or_tree.conclusion,
1130 or_expr
1131 );
1132 match or_expr {
1133 ProofExpr::Or(l, r) => {
1134 if r.as_ref() == target {
1135 let lneg = self.prove_neg_by_search(l)?;
1136 Some(disjunction_elim(target.clone(), or_tree, lneg))
1137 } else {
1138 let rneg = self.prove_neg_by_search(r)?;
1139 let l_tree = disjunction_elim((**l).clone(), or_tree, rneg);
1140 self.extract_by_search(l, l_tree, target)
1141 }
1142 }
1143 _ => Some(or_tree),
1144 }
1145 }
1146
1147 fn prove_neg_by_search(&mut self, e: &ProofExpr) -> Option<DerivationTree> {
1155 if let ProofExpr::Or(..) = e {
1156 let bot = self.disj_to_falsum(e)?;
1157 return Some(reductio(e.clone(), bot));
1158 }
1159 let lit = self.lit_of(e)?;
1160 match self.value(lit) {
1161 Some(false) => Some(align_to(self.prove_var(lit.var), &neg_of(e))),
1162 Some(true) => None,
1163 None => {
1164 let trail_snap = self.trail.len();
1165 let clause_snap = self.clauses.len();
1166 let fired_snap = self.fired_disj.clone();
1167 let _ = self.set(lit, Reason::Assumption);
1168 let bot = self.derive_falsum(0);
1169 let result = bot.map(|b| reductio(e.clone(), b));
1170 self.backtrack(trail_snap, clause_snap, fired_snap);
1171 result
1172 }
1173 }
1174 }
1175
1176 fn disj_to_falsum(&mut self, e: &ProofExpr) -> Option<DerivationTree> {
1181 if let ProofExpr::Or(l, r) = e {
1182 let lb = self.disj_to_falsum(l)?;
1183 let rb = self.disj_to_falsum(r)?;
1184 return Some(disjunction_cases(falsum(), leaf(e.clone()), lb, rb));
1185 }
1186 let neg = self.prove_neg_by_search(e)?;
1188 Some(make_contradiction(leaf(e.clone()), neg))
1189 }
1190}
1191
1192const MAX_DEPTH: usize = 64;
1193
1194enum ConflictInfo {
1195 Clash {
1197 assumed: ProofExpr,
1198 },
1199 Rule(usize),
1200 Clause(usize),
1201}
1202
1203fn make_contradiction(a: DerivationTree, b: DerivationTree) -> DerivationTree {
1205 if matches!(a.conclusion, ProofExpr::Not(_)) {
1206 contra_align(b, a)
1207 } else {
1208 contra_align(a, b)
1209 }
1210}
1211
1212fn neg_of(e: &ProofExpr) -> ProofExpr {
1214 match e {
1215 ProofExpr::Not(inner) => (**inner).clone(),
1216 _ => ProofExpr::Not(Box::new(e.clone())),
1217 }
1218}
1219
1220fn align_to(tree: DerivationTree, want: &ProofExpr) -> DerivationTree {
1224 if &tree.conclusion == want {
1225 return tree;
1226 }
1227 match (&tree.conclusion, want) {
1228 (ProofExpr::Identity(a, b), ProofExpr::Identity(c, d)) if a == d && b == c => {
1229 eq_sym(a.clone(), b.clone(), tree)
1230 }
1231 (ProofExpr::Not(ti), ProofExpr::Not(wi)) => match (ti.as_ref(), wi.as_ref()) {
1232 (ProofExpr::Identity(a, b), ProofExpr::Identity(c, d)) if a == d && b == c => {
1233 let assumed = ProofExpr::Identity(c.clone(), d.clone());
1234 let flipped = eq_sym(c.clone(), d.clone(), leaf(assumed.clone()));
1235 let bot = contradiction(flipped, tree);
1236 reductio(assumed, bot)
1237 }
1238 _ => tree,
1239 },
1240 _ => tree,
1241 }
1242}
1243
1244fn contra_align(pos_tree: DerivationTree, neg_tree: DerivationTree) -> DerivationTree {
1247 let inner = match &neg_tree.conclusion {
1248 ProofExpr::Not(i) => (**i).clone(),
1249 other => other.clone(),
1250 };
1251 let aligned = align_to(pos_tree, &inner);
1252 contradiction(aligned, neg_tree)
1253}
1254
1255pub fn grid_prove(premises: &[ProofExpr], goal: &ProofExpr) -> Option<DerivationTree> {
1260 let mut solver = compile(premises)?;
1261 solver.at_root = true;
1266 let root = solver.propagate();
1267 solver.at_root = false;
1268 if root.is_err() {
1269 return None;
1270 }
1271 if let Some(lit) = solver.lit_of(goal) {
1273 if solver.value(lit) == Some(true) {
1274 return Some(align_to(solver.prove_var(lit.var), goal));
1275 }
1276 }
1277 if !matches!(goal, ProofExpr::Not(_)) && solver.lit_of(goal).is_some() {
1280 if let Some(tree) = solver.prove_positive_by_closure(goal) {
1281 return Some(align_to(tree, goal));
1282 }
1283 }
1284 if let ProofExpr::Not(inner) = goal {
1286 let x_lit = solver.lit_of(inner)?;
1287 match solver.value(x_lit) {
1288 Some(false) => return Some(align_to(solver.prove_var(x_lit.var), goal)),
1289 Some(true) => return None,
1290 None => {
1291 let _ = solver.set(x_lit, Reason::Assumption);
1292 let bot = solver.derive_falsum(0)?;
1293 return Some(reductio((**inner).clone(), bot));
1294 }
1295 }
1296 }
1297 None
1298}
1299
1300#[cfg(test)]
1301#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/grid_solver/tests.rs"]
1302mod tests;