Skip to main content

logicaffeine_proof/
simp.rs

1//! `simp` rule sets: oriented rewrite rules compiled from proved lemmas,
2//! indexed for fast lookup, instantiated by matching.
3//!
4//! A simp rule is a lemma of shape `∀x₁…xₙ. C₁ → … → Cₖ → lhs = rhs` (or
5//! `… lhs ↔ rhs`), oriented left-to-right. Orientation is enforced at
6//! registration: `vars(rhs) ⊆ vars(lhs)`, `vars(Cᵢ) ⊆ vars(lhs)`, and `lhs`
7//! is not a bare variable — so matching the `lhs` against a goal subterm
8//! determines the entire instantiation.
9//!
10//! The tactic layer ([`crate::tactic::ProofState::simp`]) drives the rewrite
11//! loop; this module finds one certified step at a time. Each step's equality
12//! carries its own derivation — `PremiseMatch` on the ∀-lemma, a
13//! [`InferenceRule::UniversalInstTerm`] chain for the instantiation,
14//! `ModusPonens` per discharged condition — so the kernel re-checks every
15//! rewrite like any hand-written proof. Nothing here is trusted.
16
17use 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
25/// Lower a kernel `Term` back into the proof layer's first-order `ProofTerm`.
26///
27/// The inverse of `certifier::proof_term_to_kernel_term` over the fragment a rewrite rule can
28/// live in: variables, globals, literals, and applications with a global head. Anything else —
29/// a binder, a `Match`, a partially-applied variable head — has no first-order image and the
30/// rule is simply not available to this layer, which is a capability gap and never a silent
31/// mis-lowering.
32fn 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
55/// The rewriting core of a rule: a term equation or a propositional
56/// equivalence.
57enum RuleCore {
58    TermEq { lhs: ProofTerm, rhs: ProofTerm },
59    PropIff { lhs: ProofExpr, rhs: ProofExpr },
60}
61
62/// A compiled simp rule: the peeled binder list, pending conditions, oriented
63/// core, and the derivation of the un-instantiated lemma (a `PremiseMatch`
64/// leaf — valid whenever the lemma is a premise or an in-scope hypothesis).
65struct 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/// An indexed set of simp rules.
76#[derive(Default)]
77pub struct SimpSet {
78    rules: Vec<CompiledRule>,
79    term_index: DiscTree<usize>,
80    iff_index: DiscTree<usize>,
81}
82
83/// One rewrite step found in a goal: `eq` proves `Identity(from, to)`.
84pub(crate) struct RewriteStep {
85    pub eq: DerivationTree,
86    pub from: ProofTerm,
87    pub to: ProofTerm,
88}
89
90/// One top-level propositional step: `imp` proves `rhs → goal`, so refining
91/// with `ModusPonens` reduces the goal to `rhs`.
92pub(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    /// Compile every `@[simp]` lemma REGISTERED in a kernel context into this rule set.
111    ///
112    /// [`Context::simp_rules`] is the one door a simplifier consults — `@[simp]`, a `local
113    /// simp` inside a section, and an equational `auto` hint all arrive through it — and it
114    /// holds its rules as kernel `Term`s. The proof layer rewrites `ProofExpr`s, so each rule
115    /// is lowered back into the shape [`SimpSet::register_lemma`] orients:
116    /// `Π(x̄). Eq A lhs rhs` becomes `∀x̄. lhs = rhs`.
117    ///
118    /// Registration makes a lemma a RULE; it does not make it true. The compiled rule's
119    /// derivation base is a `PremiseMatch` on the lemma, so a rewrite fires into a certificate
120    /// only where the lemma is also in scope — as a premise, a hypothesis, or a declaration the
121    /// certifier can find. That separation is deliberate: a `@[simp]` attribute is an
122    /// instruction to the simplifier, never an assumption.
123    ///
124    /// Returns how many rules were added. A registry rule that does not lower is one whose
125    /// terms are outside the proof layer's first-order fragment (a `Π`, a `Match`, a `Lambda`
126    /// inside the pattern), not one the registry let through: the shapes that would make a
127    /// rewriter WRONG — a bare-variable left-hand side, an undetermined right-hand-side
128    /// variable, a self-rewrite — are already refused, loudly and by name, at the door.
129    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    /// Compile and index `lemma` as a rewrite rule. Returns `false` (and
153    /// registers nothing) if the lemma is not an oriented rule: no equational
154    /// or iff core, a bare-variable lhs, rhs/condition variables the lhs does
155    /// not bind, or shadowed binder names.
156    ///
157    /// The rule's derivation base is a `PremiseMatch` leaf, so the lemma must
158    /// be in scope (a premise or hypothesis) wherever the rule fires.
159    pub fn register_lemma(&mut self, name: &str, lemma: &ProofExpr) -> bool {
160        // Peel the ∀-prefix.
161        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; // shadowed binder — instantiation would be ambiguous
170            }
171            params.push(variable.clone());
172            body = inner;
173        }
174        // Peel the condition chain.
175        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; // a bare-variable lhs matches everything
184                }
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        // Orientation: everything the rhs and the conditions mention, the lhs
197        // must bind — matching the lhs then determines the instantiation.
198        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        // Every parameter must actually be determined by the lhs.
215        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    /// Find one term-rewrite step in `goal`, innermost subterms first.
236    /// `hyps` are the in-scope facts (proposition + its derivation), used to
237    /// discharge rule conditions.
238    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    /// Find a top-level propositional step: an iff rule whose lhs matches the
264    /// whole goal.
265    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            // Project the right-to-left implication (Iff ≡ And(→, ←)).
296            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        // A no-op rewrite (t = t) makes no progress and would loop.
328        if from == to {
329            return None;
330        }
331        Some(RewriteStep { eq: tree, from, to })
332    }
333}
334
335/// Instantiate a compiled rule under `subst`: chain `UniversalInstTerm` for
336/// each parameter, then discharge each condition by `ModusPonens` against the
337/// in-scope facts (or ground arithmetic). Returns the derivation and its
338/// conclusion (the instantiated core).
339fn 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
375/// Discharge an instantiated condition: an in-scope fact that matches it
376/// exactly, or a ground arithmetic identity. Depth-1 by design — conditions
377/// do not recursively invoke the rewriter.
378fn 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
396/// Find one ground arithmetic fold (`add(2, 3) ⇝ 5`), innermost first. The
397/// equality is an `ArithDecision` leaf — the certifier re-runs the arithmetic
398/// oracle and the kernel checks the resulting term.
399pub(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
442/// The subterms of a goal in post-order (innermost first), without duplicates.
443fn 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}