Skip to main content

logicaffeine_proof/
crush.rs

1//! `crush` — the grind-style closer: E-match quantified equality lemmas into
2//! the ground e-graph, then discharge the goal by certified congruence closure.
3//!
4//! Lean's `grind` fuses an e-graph, E-matching of annotated lemmas, and theory
5//! solvers. This is the congruence+instantiation core of that, built entirely
6//! on machinery that already certifies: the ground equality graph and its
7//! transitive/congruence explanations (`crate::engine::cert_congruence_path`),
8//! and the one-sided matcher that fires a `∀`-lemma at a ground subterm
9//! ([`crate::unify::match_term_pattern`]). Each instantiation is a
10//! [`InferenceRule::UniversalInstTerm`] chain from the lemma; the final goal
11//! closes by rewriting a known atom through the congruence-derived equalities.
12//! The whole result is one kernel-checked derivation — unlike `grind`, whose
13//! core is trusted.
14//!
15//! Signature demo (which plain `auto` cannot do): `∀x. f(x)=g(x)`, `a=b`,
16//! `P(g(b))` ⊢ `P(f(a))`.
17
18use 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
24/// Prove `goal` from `premises` by E-matching the `∀`-equality lemmas among
25/// them and closing by congruence. Returns a kernel-checkable derivation, or
26/// `None` when this fragment cannot close the goal.
27pub(crate) fn crush_prove(premises: &[ProofExpr], goal: &ProofExpr) -> Option<DerivationTree> {
28    // Ground facts (with PremiseMatch proofs) and the `∀`-equality lemmas.
29    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    // The ground term universe: every subterm of a ground fact or the goal.
43    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    // E-match each lemma's LHS against ground subterms; add the instances.
51    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; // trigger did not pin every variable
60            }
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, &params, &subst) {
67                known.push(inst);
68            }
69        }
70    }
71
72    // Close.
73    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
82/// Prove `P(s̄)` from a known atom `P(t̄)` and the equalities in `known`: rewrite
83/// each argument `tᵢ ⇝ sᵢ` (justified by a congruence path) one at a time,
84/// starting from the known atom.
85fn 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        // Rewrite kargs → goal_args argument by argument.
109        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            // A proof `cur[i] = goal_args[i]` from the e-graph.
117            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            // Forward Leibniz: the equality proves `from = to`, the source proves `P(cur)`,
124            // the conclusion is `P(next)`. The motive's POSITION matters — two arguments can
125            // converge on one term (`P(a, cc)` closing `P(b, b)`), and the all-occurrences
126            // motive `λz. P(z, z)` then asks for a source `P(cc, cc)` nobody proved, so the
127            // tactic would report success and the kernel would refuse the tree.
128            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
144/// Expand the `∀`-equality steps of a named chain into their GROUND instances at the terms
145/// the chain actually mentions.
146///
147/// Lean writes a `calc` step as `h₂ b` — the lemma APPLIED at the waypoint — so the
148/// instantiation is part of the source text. A LOGOS `calc` block names its steps, so the
149/// application has to be FOUND: each `∀x̄. lhs = rhs` is E-matched (both sides, since a chain
150/// may enter the step from either end) against every subterm of the goal and of the chain's
151/// ground steps, and each firing becomes a [`InferenceRule::UniversalInstTerm`] chain built
152/// on the step's own derivation. A step that is already ground travels through unchanged.
153///
154/// This is the same E-matching [`crush_prove`] performs over everything in scope, restricted
155/// to the steps a `calc` block NAMED — which is the distinction between the two tactics.
156pub(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, &params, &subst) else {
188                    continue;
189                };
190                if fired.insert(format!("{}", inst.0)) {
191                    out.push(inst);
192                }
193            }
194        }
195    }
196    out
197}
198
199/// A premise of shape `∀xs. lhs = rhs`.
200fn is_forall_eq_lemma(e: &ProofExpr) -> bool {
201    peel_eq_lemma(e).is_some()
202}
203
204/// Peel `∀xs. lhs = rhs` into `(xs, lhs, rhs)`; `None` if it is not that shape
205/// (must have at least one binder and an equational body).
206fn 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
226/// Instantiate `∀xs. body` at `subst`, producing the ground fact and its
227/// `UniversalInstTerm`-chain proof built on top of `base` — the derivation that already
228/// proves the quantified lemma (a `PremiseMatch` leaf for a premise, whatever a named `calc`
229/// step carries for a hypothesis).
230fn 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}