Skip to main content

logicaffeine_proof/
lib.rs

1#![cfg_attr(docsrs, feature(doc_cfg))]
2#![doc = include_str!("../README.md")]
3
4// Number-theory / cryptanalysis substrate — factoring, elliptic/isogeny, lattice, order-finding.
5// These are prover tools (the hardness lens behind isogeny/ait/oracle), not runtime crypto; they
6// depend only on `logicaffeine_base::numeric`.
7pub mod cyclotomic;
8pub mod elliptic;
9pub mod factor;
10pub mod fp2;
11pub mod hyperelliptic;
12pub mod lattice;
13pub mod period;
14
15pub mod arith;
16// Independent replay checker for the analog lane's range-safety certificates (the PR/RUP-checker
17// pattern applied to voltage bounds): dependency-free, fail-closed, trusted over the producer.
18pub mod affine;
19pub mod affine_gfp;
20pub mod aig;
21pub mod ait;
22pub mod bmc;
23pub mod cardinality;
24pub mod cdcl;
25pub mod certifier;
26pub mod cnf;
27pub mod coalgebra;
28pub mod complexity;
29pub mod counterexample;
30pub mod counting_principle;
31pub mod crush;
32pub mod cubical;
33pub mod cycle_ratio;
34pub mod decide;
35pub mod development;
36pub mod dimacs;
37pub mod discrimination;
38pub mod eilenberg_maclane;
39pub mod engine;
40pub mod error;
41pub mod families;
42pub mod formula;
43pub mod fraig;
44pub mod gf2;
45pub mod grid_solver;
46pub mod grounding;
47pub mod groupoid;
48pub mod hints;
49pub mod hornsat;
50pub mod hypercube;
51pub mod inprocess;
52pub mod interval_replay;
53pub mod interval_sched;
54pub mod isogeny;
55pub mod kan_complex;
56pub mod lemma_index;
57pub mod linalg;
58pub mod linalg_certify;
59pub mod linarith_solve;
60pub mod lll;
61pub mod lrat;
62pub mod lyapunov;
63pub mod macaulay;
64pub mod matching;
65pub mod min_cost_flow;
66pub mod modm;
67pub mod modp;
68mod numeral;
69pub mod omega_solve;
70pub mod optimize;
71pub mod ordering;
72pub mod parity_cardinality;
73pub mod permgroup;
74pub mod pigeonhole;
75pub mod polycalc;
76pub mod postnikov;
77pub mod pr;
78pub mod progress_complex;
79pub mod proof;
80pub mod proof_emit;
81pub mod proof_rewrite;
82pub mod pseudo_boolean;
83pub mod rainbow;
84pub mod register_alloc;
85pub mod relax_replay;
86pub mod revgate;
87pub mod rule_search;
88pub mod rup;
89pub mod sat;
90pub mod satcli;
91pub mod sdcl;
92pub mod seq_equiv;
93pub mod simp;
94pub mod solve;
95pub mod sos;
96pub mod steenrod;
97pub mod sweep;
98pub mod sym_break;
99pub mod sym_certify;
100pub mod sym_dynamic;
101mod symbols;
102pub mod symmetry;
103pub mod symmetry_detect;
104pub mod tactic;
105pub mod tactic_cert;
106pub mod tactic_script;
107pub mod thermal_replay;
108pub mod trace_determinism;
109pub mod two_group;
110pub mod two_type;
111pub mod twosat;
112pub mod unify;
113pub mod units;
114pub mod streams;
115pub mod verify;
116pub mod xl;
117pub mod xor_drat;
118pub mod xor_engine;
119pub mod xorsat;
120
121#[cfg(feature = "verification")]
122mod modal_translation;
123#[cfg(feature = "verification")]
124pub mod oracle;
125
126pub use engine::{BackwardChainer, PremiseVariables};
127pub use error::ProofError;
128pub use hints::{suggest_hint, SocraticHint, SuggestedTactic};
129pub use unify::Substitution;
130
131use std::fmt;
132
133// =============================================================================
134// PROOF TERM - Owned representation of logical terms
135// =============================================================================
136
137/// Owned term representation for proof manipulation.
138///
139/// Decoupled from arena-allocated `Term<'a>` to allow proof trees to persist
140/// beyond the lifetime of the parsing arena.
141///
142/// # See Also
143///
144/// * [`ProofExpr`] - Expression-level representation containing `ProofTerm`s
145/// * [`unify::unify_terms`] - Unification algorithm for terms
146/// * [`unify::Substitution`] - Maps variables to terms
147/// * [`certifier::certify`] - Converts proof trees to kernel terms
148#[derive(Debug, Clone, PartialEq, Eq, Hash)]
149pub enum ProofTerm {
150    /// A constant symbol (e.g., "Socrates", "42")
151    Constant(String),
152
153    /// A variable symbol (e.g., "x", "y")
154    Variable(String),
155
156    /// A function application (e.g., "father(x)", "add(1, 2)")
157    Function(String, Vec<ProofTerm>),
158
159    /// A group/tuple of terms (e.g., "(x, y)")
160    Group(Vec<ProofTerm>),
161
162    /// Reference to a bound variable in a pattern context.
163    /// Distinct from Variable (unification var) and Constant (global name).
164    /// Prevents variable capture bugs during alpha-conversion.
165    BoundVarRef(String),
166}
167
168impl fmt::Display for ProofTerm {
169    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
170        match self {
171            ProofTerm::Constant(s) => write!(f, "{}", s),
172            ProofTerm::Variable(s) => write!(f, "{}", s),
173            ProofTerm::Function(name, args) => {
174                write!(f, "{}(", name)?;
175                for (i, arg) in args.iter().enumerate() {
176                    if i > 0 {
177                        write!(f, ", ")?;
178                    }
179                    write!(f, "{}", arg)?;
180                }
181                write!(f, ")")
182            }
183            ProofTerm::Group(terms) => {
184                write!(f, "(")?;
185                for (i, t) in terms.iter().enumerate() {
186                    if i > 0 {
187                        write!(f, ", ")?;
188                    }
189                    write!(f, "{}", t)?;
190                }
191                write!(f, ")")
192            }
193            ProofTerm::BoundVarRef(s) => write!(f, "#{}", s),
194        }
195    }
196}
197
198// =============================================================================
199// PROOF EXPRESSION - Owned representation of logical expressions
200// =============================================================================
201
202/// Owned expression representation for proof manipulation.
203///
204/// Supports all `LogicExpr` variants to enable full language coverage.
205/// This is the "proposition" side of the Curry-Howard correspondence.
206///
207/// # See Also
208///
209/// * [`ProofTerm`] - Terms embedded within expressions (predicate arguments)
210/// * [`unify::unify_exprs`] - Expression-level unification with alpha-equivalence
211/// * [`unify::beta_reduce`] - Normalizes lambda applications
212/// * [`certifier::certify`] - Converts expressions to kernel types
213/// * [`DerivationTree`] - Proof trees conclude with a `ProofExpr`
214#[derive(Debug, Clone, PartialEq)]
215pub enum ProofExpr {
216    // --- Core FOL ---
217    /// Atomic predicate: P(t1, t2, ...)
218    Predicate {
219        name: String,
220        args: Vec<ProofTerm>,
221        world: Option<String>,
222    },
223
224    /// Identity: t1 = t2
225    Identity(ProofTerm, ProofTerm),
226
227    /// Propositional atom
228    Atom(String),
229
230    // --- Logical Connectives ---
231    /// Conjunction: P ∧ Q
232    And(Box<ProofExpr>, Box<ProofExpr>),
233
234    /// Disjunction: P ∨ Q
235    Or(Box<ProofExpr>, Box<ProofExpr>),
236
237    /// Implication: P → Q
238    Implies(Box<ProofExpr>, Box<ProofExpr>),
239
240    /// Biconditional: P ↔ Q
241    Iff(Box<ProofExpr>, Box<ProofExpr>),
242
243    /// Negation: ¬P
244    Not(Box<ProofExpr>),
245
246    // --- Quantifiers ---
247    /// Universal quantification: ∀x P(x)
248    ForAll {
249        variable: String,
250        body: Box<ProofExpr>,
251    },
252
253    /// Existential quantification: ∃x P(x)
254    Exists {
255        variable: String,
256        body: Box<ProofExpr>,
257    },
258
259    // --- Modal Logic ---
260    /// Modal operator: □P or ◇P (with world semantics)
261    Modal {
262        domain: String,
263        force: f32,
264        flavor: String,
265        body: Box<ProofExpr>,
266    },
267
268    /// Counterfactual conditional: P □→ Q. Quantifies the consequent over the
269    /// closest antecedent-worlds (a similarity ordering), so it is strictly
270    /// distinct from material implication in both directions.
271    Counterfactual {
272        antecedent: Box<ProofExpr>,
273        consequent: Box<ProofExpr>,
274    },
275
276    // --- Temporal Logic ---
277    /// Temporal operator: Past(P), Future(P), Always(P), Eventually(P), Next(P)
278    Temporal {
279        operator: String,
280        body: Box<ProofExpr>,
281    },
282
283    /// Binary temporal operator: Until(P,Q), Release(P,Q), WeakUntil(P,Q)
284    TemporalBinary {
285        operator: String,
286        left: Box<ProofExpr>,
287        right: Box<ProofExpr>,
288    },
289
290    // --- Lambda Calculus (CIC extension) ---
291    /// Lambda abstraction: λx.P
292    Lambda {
293        variable: String,
294        body: Box<ProofExpr>,
295    },
296
297    /// Function application: (f x)
298    App(Box<ProofExpr>, Box<ProofExpr>),
299
300    // --- Event Semantics ---
301    /// Neo-Davidsonian event: ∃e(Verb(e) ∧ Agent(e,x) ∧ ...)
302    NeoEvent {
303        event_var: String,
304        verb: String,
305        roles: Vec<(String, ProofTerm)>,
306    },
307
308    // --- Peano / Inductive Types (CIC Extension) ---
309    /// Data Constructor: Zero, Succ(n), Cons(h, t), etc.
310    /// The building blocks of inductive types.
311    Ctor { name: String, args: Vec<ProofExpr> },
312
313    /// Pattern Matching: match n { Zero => A, Succ(k) => B }
314    /// Eliminates inductive types by case analysis.
315    Match {
316        scrutinee: Box<ProofExpr>,
317        arms: Vec<MatchArm>,
318    },
319
320    /// Recursive Function (Fixpoint): fix f. λn. ...
321    /// Defines recursive functions over inductive types.
322    Fixpoint { name: String, body: Box<ProofExpr> },
323
324    /// Typed Variable: n : Nat
325    /// Signals to the prover that induction may be applicable.
326    TypedVar { name: String, typename: String },
327
328    // --- Higher-Order Pattern Unification ---
329    /// Meta-variable (unification hole) to be solved during proof search.
330    /// Represents an unknown expression, typically a function or predicate.
331    /// Example: Hole("P") in ?P(x) = Body, to be solved as P = λx.Body
332    Hole(String),
333
334    /// Embedded term (lifts ProofTerm into ProofExpr context).
335    /// Used when a term appears where an expression is expected.
336    /// Example: App(Hole("P"), Term(BoundVarRef("x")))
337    Term(ProofTerm),
338
339    // --- Fallback ---
340    /// Unsupported construct (with description for debugging)
341    Unsupported(String),
342}
343
344// =============================================================================
345// MATCH ARM - A single case in pattern matching
346// =============================================================================
347
348/// A single arm in a match expression.
349/// Example: Succ(k) => Add(k, m)
350#[derive(Debug, Clone, PartialEq)]
351pub struct MatchArm {
352    /// The constructor being matched: "Zero", "Succ", "Cons", etc.
353    pub ctor: String,
354
355    /// Variable bindings for constructor arguments: ["k"] for Succ(k)
356    pub bindings: Vec<String>,
357
358    /// The expression to evaluate when this arm matches
359    pub body: ProofExpr,
360}
361
362impl fmt::Display for ProofExpr {
363    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
364        match self {
365            ProofExpr::Predicate { name, args, world } => {
366                write!(f, "{}", name)?;
367                if !args.is_empty() {
368                    write!(f, "(")?;
369                    for (i, arg) in args.iter().enumerate() {
370                        if i > 0 {
371                            write!(f, ", ")?;
372                        }
373                        write!(f, "{}", arg)?;
374                    }
375                    write!(f, ")")?;
376                }
377                if let Some(w) = world {
378                    write!(f, " @{}", w)?;
379                }
380                Ok(())
381            }
382            ProofExpr::Identity(left, right) => write!(f, "{} = {}", left, right),
383            ProofExpr::Atom(s) => write!(f, "{}", s),
384            ProofExpr::And(left, right) => write!(f, "({} ∧ {})", left, right),
385            ProofExpr::Or(left, right) => write!(f, "({} ∨ {})", left, right),
386            ProofExpr::Implies(left, right) => write!(f, "({} → {})", left, right),
387            ProofExpr::Iff(left, right) => write!(f, "({} ↔ {})", left, right),
388            ProofExpr::Not(inner) => write!(f, "¬{}", inner),
389            ProofExpr::ForAll { variable, body } => write!(f, "∀{} {}", variable, body),
390            ProofExpr::Exists { variable, body } => write!(f, "∃{} {}", variable, body),
391            ProofExpr::Modal {
392                domain,
393                force,
394                flavor,
395                body,
396            } => {
397                write!(f, "□[{}/{}/{}]{}", domain, force, flavor, body)
398            }
399            ProofExpr::Counterfactual {
400                antecedent,
401                consequent,
402            } => {
403                write!(f, "({} □→ {})", antecedent, consequent)
404            }
405            ProofExpr::Temporal { operator, body } => write!(f, "{}({})", operator, body),
406            ProofExpr::TemporalBinary {
407                operator,
408                left,
409                right,
410            } => {
411                write!(f, "TemporalBinary({}, {}, {})", operator, left, right)
412            }
413            ProofExpr::Lambda { variable, body } => write!(f, "λ{}.{}", variable, body),
414            ProofExpr::App(func, arg) => write!(f, "({} {})", func, arg),
415            ProofExpr::NeoEvent {
416                event_var,
417                verb,
418                roles,
419            } => {
420                write!(f, "∃{}({}({})", event_var, verb, event_var)?;
421                for (role, term) in roles {
422                    write!(f, " ∧ {}({}, {})", role, event_var, term)?;
423                }
424                write!(f, ")")
425            }
426            ProofExpr::Ctor { name, args } => {
427                write!(f, "{}", name)?;
428                if !args.is_empty() {
429                    write!(f, "(")?;
430                    for (i, arg) in args.iter().enumerate() {
431                        if i > 0 {
432                            write!(f, ", ")?;
433                        }
434                        write!(f, "{}", arg)?;
435                    }
436                    write!(f, ")")?;
437                }
438                Ok(())
439            }
440            ProofExpr::Match { scrutinee, arms } => {
441                write!(f, "match {} {{ ", scrutinee)?;
442                for (i, arm) in arms.iter().enumerate() {
443                    if i > 0 {
444                        write!(f, ", ")?;
445                    }
446                    write!(f, "{}", arm.ctor)?;
447                    if !arm.bindings.is_empty() {
448                        write!(f, "({})", arm.bindings.join(", "))?;
449                    }
450                    write!(f, " => {}", arm.body)?;
451                }
452                write!(f, " }}")
453            }
454            ProofExpr::Fixpoint { name, body } => write!(f, "fix {}.{}", name, body),
455            ProofExpr::TypedVar { name, typename } => write!(f, "{}:{}", name, typename),
456            ProofExpr::Unsupported(desc) => write!(f, "⟨unsupported: {}⟩", desc),
457            ProofExpr::Hole(name) => write!(f, "?{}", name),
458            ProofExpr::Term(term) => write!(f, "{}", term),
459        }
460    }
461}
462
463// =============================================================================
464// INFERENCE RULE - The logical moves available to the prover
465// =============================================================================
466
467/// The "Lever" - The specific logical move made at each proof step.
468///
469/// This enum captures HOW we moved from premises to conclusion. Each variant
470/// corresponds to a different proof strategy or logical rule.
471///
472/// # See Also
473///
474/// * [`DerivationTree`] - Each node contains an `InferenceRule`
475/// * [`certifier::certify`] - Maps inference rules to kernel terms
476/// * [`hints::suggest_hint`] - Suggests applicable rules when stuck
477/// * [`BackwardChainer`] - The engine that selects and applies rules
478///
479/// One constructor's case in a generic induction scheme
480/// ([`InferenceRule::InductionScheme`]). The derivation's premises align 1:1 with
481/// the cases, in the inductive's constructor-registration order.
482#[derive(Debug, Clone, PartialEq)]
483pub struct InductionCase {
484    /// The constructor this case eliminates (e.g. `"Succ"`, `"Node"`).
485    pub constructor: String,
486    /// The constructor's arguments, in order — each bound in the case body.
487    pub args: Vec<InductionArg>,
488}
489
490/// One argument of a constructor in an [`InductionCase`].
491#[derive(Debug, Clone, PartialEq)]
492pub struct InductionArg {
493    /// The name bound for this argument in the case body.
494    pub name: String,
495    /// Whether this argument is itself of the inductive type — a recursive
496    /// position, which therefore carries an induction hypothesis.
497    pub recursive: bool,
498}
499
500/// `ModusPonens` → `modus_ponens`. The script spelling of a rule name: a capital starts a new
501/// word, and a run of capitals (`EqualityTransitivity` has none, but a future `LHS` would) stays
502/// one word, so the transformation is a bijection on the names it is applied to.
503fn snake_case(name: &str) -> String {
504    let mut out = String::with_capacity(name.len() + 4);
505    let chars: Vec<char> = name.chars().collect();
506    for (i, c) in chars.iter().enumerate() {
507        if c.is_ascii_uppercase() && i > 0 {
508            let prev_lower = chars[i - 1].is_ascii_lowercase() || chars[i - 1].is_ascii_digit();
509            let next_lower = chars.get(i + 1).is_some_and(|n| n.is_ascii_lowercase());
510            if prev_lower || next_lower {
511                out.push('_');
512            }
513        }
514        out.push(c.to_ascii_lowercase());
515    }
516    out
517}
518
519#[derive(Debug, Clone, PartialEq)]
520pub enum InferenceRule {
521    // --- Basic FOL ---
522    /// Direct match with a known fact in the Context/KnowledgeBase.
523    /// Logic: Γ, P ⊢ P
524    PremiseMatch,
525
526    /// Logic: P → Q, P ⊢ Q
527    ModusPonens,
528
529    /// Logic: ¬Q, P → Q ⊢ ¬P
530    ModusTollens,
531
532    /// Logic: P, Q ⊢ P ∧ Q
533    ConjunctionIntro,
534
535    /// Logic: P ∧ Q ⊢ P (or Q)
536    ConjunctionElim,
537
538    /// Logic: P ⊢ P ∨ Q
539    DisjunctionIntro,
540
541    /// Logic: P ∨ Q, P → R, Q → R ⊢ R
542    DisjunctionElim,
543
544    /// Logic: ⊥ ⊢ anything (ex falso quodlibet). The single premise concludes `False`.
545    ExFalso,
546
547    /// Logic: assume P, derive Q ⊢ P → Q (implication introduction / →I). The
548    /// single premise proves Q with P bound as a local hypothesis.
549    ImpliesIntro,
550
551    /// Logic: prove P → Q and Q → P ⊢ P ↔ Q (biconditional introduction / ↔I).
552    BicondIntro,
553
554    /// Logic: ¬¬P ⊢ P (and P ⊢ ¬¬P)
555    DoubleNegation,
556
557    /// Logic: classical reductio (proof by contradiction) — assume ¬G, derive ⊥ ⊢ G,
558    /// discharged through the `dne` axiom. The single premise concludes `False` with
559    /// ¬G bound as a local hypothesis.
560    ClassicalReductio,
561
562    // --- Quantifiers ---
563    /// Logic: ∀x P(x) ⊢ P(c)
564    /// Stores the specific term 'c' used to instantiate the universal.
565    UniversalInst(String),
566
567    /// Logic: ∀x P(x) ⊢ P(t) at an arbitrary witness TERM (a compound like
568    /// `add(a, Zero)`, not just a name). `UniversalInst` keeps the name-only
569    /// fast path; this carries the full term for instantiations that
570    /// `simp`/`crush` produce by matching.
571    UniversalInstTerm(ProofTerm),
572
573    /// Logic: Γ, x:T ⊢ P(x) implies Γ ⊢ ∀x:T. P(x)
574    /// Stores variable name and type name for Lambda construction.
575    UniversalIntro { variable: String, var_type: String },
576
577    /// Logic: P(w) ⊢ ∃x.P(x)
578    /// Carries the witness and its type for kernel certification.
579    ExistentialIntro {
580        witness: String,
581        witness_type: String,
582    },
583
584    /// Logic: P(t) ⊢ ∃x.P(x) at an arbitrary witness TERM — `use (n + 1)`, `use (f x)`,
585    /// the compound witnesses Lean's `exists`/`use` takes. [`InferenceRule::ExistentialIntro`]
586    /// carries its witness as a `String`, which the certifier can only resolve as one NAME, so
587    /// `add(n, 1)` certified to a global literally called `"add(n, 1)"` that no context
588    /// declares. This carries the term, exactly as [`InferenceRule::UniversalInstTerm`] sits
589    /// beside [`InferenceRule::UniversalInst`] for the dual quantifier.
590    ///
591    /// `witness_type` is the ∃-binder's DOMAIN, not the witness's own type name: it must be
592    /// the domain `certifier::proof_expr_to_type` gives the same `Exists`, or the certified
593    /// term's type and the goal type disagree. Both sides read it from one function,
594    /// `certifier::existential_domain`.
595    ExistentialIntroTerm {
596        witness: ProofTerm,
597        witness_type: String,
598    },
599
600    // --- Modal Logic (World Moves) ---
601    /// Logic: □P (in w0), Accessible(w0, w1) ⊢ P (in w1)
602    /// "Necessity Elimination" / "Distribution"
603    ModalAccess,
604
605    /// Logic: If P is true in ALL accessible worlds ⊢ □P
606    /// "Necessity Introduction"
607    ModalGeneralization,
608
609    // --- Temporal Logic ---
610    /// Logic: t1 < t2, t2 < t3 ⊢ t1 < t3
611    TemporalTransitivity,
612
613    /// Logic: P(s₀), ∀s(P(s) → P(next(s))) ⊢ G(P)
614    /// Standard k-induction for hardware safety properties.
615    TemporalInduction,
616
617    /// Logic: G(P) ⊢ P ∧ X(G(P))
618    /// Fixpoint unfolding of Always.
619    TemporalUnfolding,
620
621    /// Logic: P(w) ⊢ F(P) for witness world w
622    /// Prove Eventually by exhibiting a reachable witness.
623    EventualityProgress,
624
625    /// Logic: Induction on trace length for P U Q
626    UntilInduction,
627
628    // --- Peano / Inductive Reasoning (CIC seed) ---
629    /// Logic: P(0), ∀k(P(k) → P(S(k))) ⊢ ∀n P(n)
630    /// Stores the variable name, its inductive type, and the step variable used.
631    StructuralInduction {
632        variable: String, // "n" - the induction variable
633        ind_type: String, // "Nat" - the inductive type
634        step_var: String, // "k" - the predecessor variable (for IH matching)
635    },
636
637    /// Logic: generic structural induction over ANY inductive type. Generalizes
638    /// [`InferenceRule::StructuralInduction`] (fixed to the nullary-base + unary-step
639    /// Nat shape) to an arbitrary constructor set — one premise per constructor, in
640    /// registration order, each recursive argument carrying its own induction
641    /// hypothesis. Certifies to a `Fix` over an N-ary `Match`: the dependent
642    /// eliminator the kernel re-checks for coverage, case types, and termination.
643    InductionScheme {
644        variable: String,          // the induction variable, e.g. "t"
645        ind_type: String,          // the inductive type, e.g. "Tree"
646        cases: Vec<InductionCase>, // one per constructor, in registration order
647    },
648
649    // --- Linear arithmetic (order) ---
650    /// `a ≤ b`, `b ≤ c` ⊢ `a ≤ c` over `Int`. The middle term is recovered from
651    /// the first premise's conclusion. Certifies to `le_trans a b c p₀ p₁`.
652    /// Inequalities are encoded as the Prop `Eq Bool (le a b) true`.
653    LeTrans,
654
655    /// `⊢ a ≤ a` over `Int`. Certifies to `le_refl a`.
656    LeRefl,
657
658    /// `a ≤ b`, `c ≤ d` ⊢ `a + c ≤ b + d` over `Int`. The four operands are read
659    /// from the conclusion `le(add a c, add b d) = true`; `premise[0]` proves
660    /// `a ≤ b`, `premise[1]` proves `c ≤ d`. Certifies to `le_add_mono a b c d p₀ p₁`.
661    LeAddMono,
662
663    /// Linear contradiction: `premise[0]` proves `le(m, n) = true` for ground `m > n`
664    /// (so `le m n ⇝ false`, the Prop is `Eq Bool false true`). Concludes `⊥` via the
665    /// `Bool` no-confusion discriminator. Lets contradictory bounds prove anything.
666    LinFalse,
667
668    /// `0 ≤ k`, `a ≤ b` ⊢ `k·a ≤ k·b` — scale an inequality by a non-negative `k`.
669    /// Operands from the conclusion `le(mul k a, mul k b) = true`; `premise[0]` proves
670    /// `0 ≤ k`, `premise[1]` proves `a ≤ b`. Certifies to `le_mul_nonneg k a b p₀ p₁`.
671    /// A Farkas-reconstruction primitive.
672    LeMulNonneg,
673
674    /// `a ≤ b` ⊢ `0 ≤ b - a` — move an inequality to one side. Operands from the
675    /// conclusion `le(0, sub b a) = true`; `premise[0]` proves `a ≤ b`. Certifies to
676    /// `le_sub a b p₀`. The Farkas "collect to a single side" primitive.
677    LeSub,
678
679    /// `a < b` ⊢ `(a + 1) ≤ b` — integer DISCRETENESS. Operands from the conclusion
680    /// `le(add a 1, b) = true`; `premise[0]` proves `a < b` (`lt(a,b) = true`).
681    /// Certifies to `lt_succ_le a b p₀`. This is the one step rational Fourier-Motzkin
682    /// lacks — the `omega` primitive that refutes strict systems the rational solver
683    /// reports satisfiable.
684    LtSuccLe,
685
686    /// `a < (b + 1)` ⊢ `a ≤ b` — the upper-side discreteness companion. Operands
687    /// from the conclusion `le(a, b) = true`; `premise[0]` proves `a < b+1`
688    /// (`lt(a, add b 1) = true`). Certifies to `lt_add1_le a b p₀`. Preferred over
689    /// `LtSuccLe` when the strict bound is already `b+1`, since it cancels the
690    /// constant instead of propagating it into the Farkas reconstruction.
691    LtAdd1Le,
692
693    /// `(a + 1) ≤ b` ⊢ `a < b` — the CONVERSE of [`InferenceRule::LtSuccLe`], and the only
694    /// way to CONCLUDE a strict inequality about symbolic operands. Operands are read from the
695    /// conclusion `lt(a, b) = true`; `premise[0]` proves `le(add a 1, b) = true`. Certifies to
696    /// `le_succ_lt a b p₀`.
697    ///
698    /// **It needs a prelude axiom that is not registered yet.** Of the `Int` order axioms in
699    /// the trusted base, NONE concludes a `lt`: `lt_succ_le` and `lt_add1_le` both take one as
700    /// a PREMISE, so a relation chain can compose a strict step but can only state its result
701    /// in the tightened form `a + 1 ≤ d`. Adding `le_succ_lt : Π a b. (a + 1) ≤ b → a < b`
702    /// closes that, and it is a ledger decision (`tcb_ledger_lock`'s `DEFINABLE_CEILING`), not
703    /// a tactic one — Lean PROVES this, because its `Int` is an inductive.
704    ///
705    /// The strictly better move, which costs no axiom at all and REMOVES two, is to make `lt`
706    /// a DEFINITION (`lt a b := le (add a 1) b`) instead of an opaque primitive: `lt_succ_le`
707    /// and `lt_add1_le` then hold by conversion and leave the ledger, and `a < b` becomes
708    /// definitionally `a + 1 ≤ b`, so this rule is not needed either.
709    ///
710    /// Until one of those lands, nothing CONSTRUCTS this rule: every producer asks
711    /// `engine::strict_conclusions_available` first, so no tree is ever built that the
712    /// kernel would have to refuse.
713    LeSuccLt,
714
715    /// `⊢ (a ≤ b) ∨ (b ≤ a)` over `Int` — LINEAR-ORDER TOTALITY, a leaf (no premises).
716    /// Certifies to `le_total a b`, whose operands are read from the conclusion
717    /// `Or (le(a,b) = true) (le(b,a) = true)`.
718    ///
719    /// This is the GOAL-DIRECTED half of `omega`. A refutation engine only ever proves `⊥`;
720    /// a decision procedure proves the goal, and the way it does that is to assume the goal
721    /// false and refute. Totality is the sound, axiom-free approximation of that assumption
722    /// for a `≤` goal: split on `le_total a b`, take the goal itself in the left branch, and
723    /// refute the hypotheses together with `b ≤ a` in the right. It reaches every goal whose
724    /// negation-by-totality is refutable; the strictly larger fragment (`¬(a ≤ b) ⟹ b+1 ≤ a`)
725    /// needs an axiom the trusted base does not have, and is deliberately NOT assumed here.
726    LeTotal,
727
728    // --- Equality ---
729    /// Leibniz's Law / Substitution of Equals
730    /// Logic: a = b, P(a) ⊢ P(b)
731    /// The equality proof is in `premise\[0\]`, the P(a) proof is in `premise\[1\]`.
732    /// Carries the original term and replacement term for certification.
733    Rewrite { from: ProofTerm, to: ProofTerm },
734
735    /// POSITIONAL Leibniz: like [`InferenceRule::Rewrite`], but abstracting exactly ONE
736    /// occurrence of `to` in the conclusion — the `occurrence`-th, counted left-to-right in
737    /// the same pre-order walk the tactic layer uses.
738    ///
739    /// `Rewrite` carries no position, and the `Eq_rec` motive it builds abstracts EVERY
740    /// occurrence, so `P(a, a)` rewritten by `a = b` could only ever become `P(b, b)`. That
741    /// is why Lean has `conv` and occurrence arguments at all: `P(b, a)` is a different (and
742    /// frequently the only provable) goal. A caller that rewrote one occurrence had nowhere
743    /// to record which, so the trust door could not follow it.
744    ///
745    /// The kernel is the check on the index: `Eq_rec` demands the source premise prove
746    /// `P from`, so an index that abstracted the wrong occurrence yields a motive the source
747    /// subgoal does not inhabit and the proof is REFUSED. A wrong position cannot be unsound,
748    /// only unprovable.
749    RewriteAt {
750        from: ProofTerm,
751        to: ProofTerm,
752        occurrence: usize,
753    },
754
755    /// Symmetry of Equality: a = b ⊢ b = a
756    EqualitySymmetry,
757
758    /// Transitivity of Equality: a = b, b = c ⊢ a = c
759    EqualityTransitivity,
760
761    /// Reflexivity of Equality: a = a (after normalization)
762    /// Used when both sides of an identity reduce to the same normal form.
763    Reflexivity,
764
765    /// Arithmetic decision: an `Int` equality discharged by the proof-producing
766    /// arithmetic oracle ([`crate::arith::prove_int_eq`]) into a kernel-checked
767    /// proof (computation + the ring axioms). The conclusion is the `Identity`.
768    ArithDecision,
769
770    /// Proof by kernel evaluation: a closed decidable proposition (a ground
771    /// comparison or Bool/Nat equality) discharged via `native_decide`. The
772    /// leaf carries only the claim; certification re-runs the evaluator and
773    /// the kernel checks the resulting `of_decide_eq_true`/`ofReduceBool`
774    /// term, so a lying leaf is rejected.
775    NativeDecide,
776
777    /// Proof by ground REFUTATION: the conclusion is `¬P` for a closed `P` that COMPUTES
778    /// FALSE. A leaf — like [`InferenceRule::NativeDecide`], it carries only the claim, and
779    /// certification re-runs the computation, so a lying leaf certifies to nothing.
780    ///
781    /// The dual `NativeDecide` lacks is the reason `decide` had no `ProofExpr::Not` arm at
782    /// all: a `Decidable` instance decides `P` true through `of_decide_eq_true`, and the
783    /// false direction needs `of_decide_eq_false`, which the trusted base does not register.
784    /// No axiom is needed, because `Bool` is an inductive with two constructors and its
785    /// no-confusion discriminator is already how a ground-false inequality becomes `⊥`
786    /// ([`InferenceRule::LinFalse`]): a ground `Int` disequality transports `le a a` (true by
787    /// computation) along the assumed equality into `le a b` (false by computation) with
788    /// `Eq_rec`, and a ground `Bool` disequality is that contradiction already.
789    GroundRefutation,
790
791    // --- Fallbacks ---
792    /// "The User Said So." Used for top-level axioms.
793    Axiom,
794
795    /// "The Machine Said So." (Z3 Oracle)
796    /// The string contains the solver's justification.
797    OracleVerification(String),
798
799    /// Proof by Contradiction (Reductio ad Absurdum)
800    /// Logic: Assume ¬C, derive P ∧ ¬P (contradiction), conclude C
801    /// Or: Assume P, derive Q ∧ ¬Q, conclude ¬P
802    ReductioAdAbsurdum,
803
804    /// Contradiction detected in premises: P and ¬P both hold
805    /// Logic: P, ¬P ⊢ ⊥ (ex falso quodlibet)
806    Contradiction,
807
808    // --- Quantifier Elimination ---
809    /// Existential Elimination (Skolemization in a proof context)
810    /// Logic: ∃x.P(x), [c fresh] P(c) ⊢ Goal implies ∃x.P(x) ⊢ Goal
811    /// The witness c must be fresh (not appearing in Goal).
812    ExistentialElim { witness: String },
813
814    /// Case Analysis on a formula `C` whose two cases both reach absurdity.
815    /// Logic: (C → ⊥), (¬C → ⊥) ⊢ ⊥ — note this is the *intuitionistic* form
816    /// (build `¬C` and `¬¬C`, then apply), so certifying it needs no excluded
817    /// middle. Used for self-referential paradoxes like the Barber Paradox.
818    ///
819    /// `case_formula` carries the actual proposition `C` (not a rendered string)
820    /// so the certifier can build the case lambdas' parameter types and bind `C`
821    /// / `¬C` as local hypotheses in each branch.
822    CaseAnalysis { case_formula: Box<ProofExpr> },
823
824    /// Logic: `A ∨ B`, `A ⊢ C`, `B ⊢ C` ⊢ `C` — disjunction elimination to a common
825    /// conclusion (here always `⊥`, for the grounded-grid contradiction prover).
826    /// Premises: `[A∨B, left-branch (C assuming A), right-branch (C assuming B)]`.
827    /// Unlike `DisjunctionElim` (disjunctive syllogism, which needs a refuted
828    /// disjunct) this eliminates BOTH disjuncts by case analysis — the move a grid's
829    /// of-pair / either-or / closure clause needs. The disjuncts (and, when a disjunct
830    /// is a conjunction, each of its conjuncts) are bound as local hypotheses in the
831    /// respective branch, so a branch may reference them directly.
832    DisjunctionCases,
833}
834
835impl InferenceRule {
836    /// Why [`certifier::certify`] cannot turn this rule into a kernel term —
837    /// `None` when it can.
838    ///
839    /// **This is the list a proof PRODUCER must consult before it emits a tree.**
840    /// A [`DerivationTree`] is an ordinary Rust value: it can be built with any
841    /// variant, it passes every Rust type check, and a rule with no certifier arm
842    /// fails only at [`verify::check_derivation`] — surfacing as a
843    /// `verification_error` that reads like a kernel limitation rather than what
844    /// it is, a tree that was never certifiable. Selecting a rule by NAME is how
845    /// that happens: `TemporalTransitivity` looks exactly right for `t₁ < t₂`,
846    /// `t₂ < t₃` ⊢ `t₁ < t₃`, and it is dead.
847    ///
848    /// Existence in this enum is not evidence of implementation. The match below
849    /// is EXHAUSTIVE and so is `certify`'s — adding a variant without deciding
850    /// both is a compile error, which is the only thing that keeps the enum and
851    /// the certifier from drifting apart.
852    pub fn uncertifiable_reason(&self) -> Option<&'static str> {
853        match self {
854            // --- Modal and temporal: DECLARED, never implemented. -------------
855            // Nothing in any engine constructs these, `certify` has no arm for
856            // any of them, and each names a proof shape with a perfectly good
857            // translation into live rules. Each reason states that translation,
858            // so a producer that reached for the name can rebuild the tree.
859            InferenceRule::ModalAccess => Some(
860                "no certifier arm: modal necessity-elimination is unimplemented. Express \
861                 `□P` as `∀v. Accessible(w, v) → P(v)` and use UniversalInst + ModusPonens",
862            ),
863            InferenceRule::ModalGeneralization => Some(
864                "no certifier arm: modal necessity-introduction is unimplemented. Express \
865                 `□P` as `∀v. Accessible(w, v) → P(v)` and use UniversalIntro",
866            ),
867            InferenceRule::TemporalTransitivity => Some(
868                "no certifier arm: temporal-order transitivity is unimplemented. A time \
869                 order is an ordinary order — use LeTrans on `≤`, or the `<` chain it \
870                 tightens to",
871            ),
872            InferenceRule::TemporalInduction => Some(
873                "no certifier arm: k-induction over a trace is unimplemented. Induct on \
874                 the trace index with StructuralInduction / InductionScheme",
875            ),
876            InferenceRule::TemporalUnfolding => Some(
877                "no certifier arm: fixpoint unfolding of `Always` is unimplemented. \
878                 Express `G P` as `∀n. P n` and use ConjunctionIntro over its \
879                 instantiations",
880            ),
881            InferenceRule::EventualityProgress => Some(
882                "no certifier arm: `Eventually` by witness is unimplemented. Express \
883                 `F P` as `∃n. P n` and use ExistentialIntro",
884            ),
885            InferenceRule::UntilInduction => Some(
886                "no certifier arm: induction for `P U Q` is unimplemented. Express it as \
887                 `∃k. Q k ∧ ∀j < k. P j` and use ExistentialIntro + ConjunctionIntro",
888            ),
889
890            // --- Deliberately outside the trusted base. ----------------------
891            InferenceRule::OracleVerification(_) => Some(
892                "refused by design: an SMT oracle attests satisfiability but hands back no \
893                 checkable proof term, so it can never become a kernel certificate. For \
894                 arithmetic, ArithDecision is the proof-producing route",
895            ),
896
897            // --- Everything below has a real arm in `certifier::certify`. ----
898            InferenceRule::PremiseMatch
899            | InferenceRule::ModusPonens
900            | InferenceRule::ModusTollens
901            | InferenceRule::ConjunctionIntro
902            | InferenceRule::ConjunctionElim
903            | InferenceRule::DisjunctionIntro
904            | InferenceRule::DisjunctionElim
905            | InferenceRule::ExFalso
906            | InferenceRule::ImpliesIntro
907            | InferenceRule::BicondIntro
908            | InferenceRule::DoubleNegation
909            | InferenceRule::ClassicalReductio
910            | InferenceRule::UniversalInst(_)
911            | InferenceRule::UniversalInstTerm(_)
912            | InferenceRule::UniversalIntro { .. }
913            | InferenceRule::ExistentialIntro { .. }
914            | InferenceRule::ExistentialIntroTerm { .. }
915            | InferenceRule::StructuralInduction { .. }
916            | InferenceRule::InductionScheme { .. }
917            | InferenceRule::LeTrans
918            | InferenceRule::LeRefl
919            | InferenceRule::LeAddMono
920            | InferenceRule::LinFalse
921            | InferenceRule::LeMulNonneg
922            | InferenceRule::LeSub
923            | InferenceRule::LtSuccLe
924            | InferenceRule::LtAdd1Le
925            | InferenceRule::LeSuccLt
926            | InferenceRule::LeTotal
927            | InferenceRule::Rewrite { .. }
928            | InferenceRule::RewriteAt { .. }
929            | InferenceRule::EqualitySymmetry
930            | InferenceRule::EqualityTransitivity
931            | InferenceRule::Reflexivity
932            | InferenceRule::ArithDecision
933            | InferenceRule::NativeDecide
934            | InferenceRule::GroundRefutation
935            | InferenceRule::Axiom
936            | InferenceRule::ReductioAdAbsurdum
937            | InferenceRule::Contradiction
938            | InferenceRule::ExistentialElim { .. }
939            | InferenceRule::CaseAnalysis { .. }
940            | InferenceRule::DisjunctionCases => None,
941        }
942    }
943
944    /// Rewrite every NAME, TERM and PROPOSITION this rule carries in its PAYLOAD.
945    ///
946    /// Two places in this crate rename a rigid eigen-CONSTANT back to the variable it stands
947    /// for, and a renaming that reaches a node's conclusion but not the payload of the rule
948    /// that justifies it produces a tree whose motive, witness or case formula is about a name
949    /// the conclusion no longer mentions — the certifier then computes against one proposition
950    /// and checks another, and refuses a correct proof. Each of the two walkers had its own
951    /// `match` with an `other => other.clone()` catch-all, and each caught a DIFFERENT subset:
952    /// `engine::rewrite_tree_const_to_var` covered `UniversalInst`, `ExistentialIntro`,
953    /// `ExistentialElim`, `Rewrite` and `CaseAnalysis`; `tactic::eigen_to_var_tree` covered
954    /// `Rewrite` alone. NEITHER covered `RewriteAt`, `UniversalInstTerm` or
955    /// `ExistentialIntroTerm` — the three payload-carrying rules added after they were written,
956    /// which is exactly what a catch-all guarantees will happen again.
957    ///
958    /// This is that decision, once, and the match is EXHAUSTIVE: a rule variant added later
959    /// cannot silently keep a stale name in its payload, because adding one without deciding
960    /// its arm here is a compile error.
961    ///
962    /// Binder names a rule INTRODUCES (`UniversalIntro`'s variable, `StructuralInduction`'s
963    /// induction and step variables, `InductionScheme`'s case arguments) are deliberately left
964    /// alone: they are not references to anything outside the node, and renaming one would
965    /// change which variable the eliminator abstracts.
966    pub fn map_payload(
967        &self,
968        name: &dyn Fn(&str) -> String,
969        term: &dyn Fn(&ProofTerm) -> ProofTerm,
970        expr: &dyn Fn(&ProofExpr) -> ProofExpr,
971    ) -> InferenceRule {
972        match self {
973            // --- Payloads that NAME a term the surrounding proof also mentions. ----------
974            InferenceRule::UniversalInst(witness) => InferenceRule::UniversalInst(name(witness)),
975            InferenceRule::ExistentialIntro { witness, witness_type } => {
976                InferenceRule::ExistentialIntro {
977                    witness: name(witness),
978                    witness_type: witness_type.clone(),
979                }
980            }
981            InferenceRule::ExistentialElim { witness } => {
982                InferenceRule::ExistentialElim { witness: name(witness) }
983            }
984
985            // --- Payloads that ARE terms. ------------------------------------------------
986            InferenceRule::UniversalInstTerm(witness) => {
987                InferenceRule::UniversalInstTerm(term(witness))
988            }
989            InferenceRule::ExistentialIntroTerm { witness, witness_type } => {
990                InferenceRule::ExistentialIntroTerm {
991                    witness: term(witness),
992                    witness_type: witness_type.clone(),
993                }
994            }
995            InferenceRule::Rewrite { from, to } => {
996                InferenceRule::Rewrite { from: term(from), to: term(to) }
997            }
998            InferenceRule::RewriteAt { from, to, occurrence } => InferenceRule::RewriteAt {
999                from: term(from),
1000                to: term(to),
1001                occurrence: *occurrence,
1002            },
1003
1004            // --- The one payload that is a PROPOSITION. ----------------------------------
1005            InferenceRule::CaseAnalysis { case_formula } => {
1006                InferenceRule::CaseAnalysis { case_formula: Box::new(expr(case_formula)) }
1007            }
1008
1009            // --- Binders the rule introduces, type NAMES, and the oracle's justification
1010            //     string: nothing here refers outward, so nothing here is renamed.
1011            InferenceRule::UniversalIntro { .. }
1012            | InferenceRule::StructuralInduction { .. }
1013            | InferenceRule::InductionScheme { .. }
1014            | InferenceRule::OracleVerification(_)
1015            // --- …and every payload-free rule.
1016            | InferenceRule::PremiseMatch
1017            | InferenceRule::ModusPonens
1018            | InferenceRule::ModusTollens
1019            | InferenceRule::ConjunctionIntro
1020            | InferenceRule::ConjunctionElim
1021            | InferenceRule::DisjunctionIntro
1022            | InferenceRule::DisjunctionElim
1023            | InferenceRule::ExFalso
1024            | InferenceRule::ImpliesIntro
1025            | InferenceRule::BicondIntro
1026            | InferenceRule::DoubleNegation
1027            | InferenceRule::ClassicalReductio
1028            | InferenceRule::ModalAccess
1029            | InferenceRule::ModalGeneralization
1030            | InferenceRule::TemporalTransitivity
1031            | InferenceRule::TemporalInduction
1032            | InferenceRule::TemporalUnfolding
1033            | InferenceRule::EventualityProgress
1034            | InferenceRule::UntilInduction
1035            | InferenceRule::LeTrans
1036            | InferenceRule::LeRefl
1037            | InferenceRule::LeAddMono
1038            | InferenceRule::LinFalse
1039            | InferenceRule::LeMulNonneg
1040            | InferenceRule::LeSub
1041            | InferenceRule::LtSuccLe
1042            | InferenceRule::LtAdd1Le
1043            | InferenceRule::LeSuccLt
1044            | InferenceRule::LeTotal
1045            | InferenceRule::EqualitySymmetry
1046            | InferenceRule::EqualityTransitivity
1047            | InferenceRule::Reflexivity
1048            | InferenceRule::ArithDecision
1049            | InferenceRule::NativeDecide
1050            | InferenceRule::GroundRefutation
1051            | InferenceRule::Axiom
1052            | InferenceRule::ReductioAdAbsurdum
1053            | InferenceRule::Contradiction
1054            | InferenceRule::DisjunctionCases => self.clone(),
1055        }
1056    }
1057
1058    /// Every rule that can be applied from a NAME alone — the payload-free variants, whose
1059    /// application is fixed by the goal and the facts in scope.
1060    ///
1061    /// A rule carrying an argument is deliberately absent: `Rewrite` needs its equation,
1062    /// `UniversalInstTerm` its witness, `StructuralInduction` its variable, and a name cannot
1063    /// supply any of them. Those have their own tactics (`rewrite`, `exists`, `induction`),
1064    /// and reporting the absence is more useful than guessing the argument.
1065    ///
1066    /// The seven declared-but-unimplemented rules ARE here. `by_rule` looks them up, finds
1067    /// [`InferenceRule::uncertifiable_reason`] and reports that reason — which is the whole
1068    /// point of the list: a producer that reached for a dead name learns it is dead, instead
1069    /// of watching a search fail for no stated cause.
1070    pub const NAMEABLE: &'static [InferenceRule] = &[
1071        InferenceRule::PremiseMatch,
1072        InferenceRule::ModusPonens,
1073        InferenceRule::ModusTollens,
1074        InferenceRule::ConjunctionIntro,
1075        InferenceRule::ConjunctionElim,
1076        InferenceRule::DisjunctionIntro,
1077        InferenceRule::DisjunctionElim,
1078        InferenceRule::DisjunctionCases,
1079        InferenceRule::ExFalso,
1080        InferenceRule::ImpliesIntro,
1081        InferenceRule::BicondIntro,
1082        InferenceRule::DoubleNegation,
1083        InferenceRule::ClassicalReductio,
1084        InferenceRule::ReductioAdAbsurdum,
1085        InferenceRule::Contradiction,
1086        InferenceRule::Axiom,
1087        InferenceRule::EqualitySymmetry,
1088        InferenceRule::EqualityTransitivity,
1089        InferenceRule::Reflexivity,
1090        InferenceRule::LeTrans,
1091        InferenceRule::LeRefl,
1092        InferenceRule::LeAddMono,
1093        InferenceRule::LeMulNonneg,
1094        InferenceRule::LeSub,
1095        InferenceRule::LinFalse,
1096        InferenceRule::LtSuccLe,
1097        InferenceRule::LtAdd1Le,
1098        InferenceRule::LeSuccLt,
1099        InferenceRule::LeTotal,
1100        InferenceRule::ArithDecision,
1101        InferenceRule::NativeDecide,
1102        InferenceRule::GroundRefutation,
1103        InferenceRule::ModalAccess,
1104        InferenceRule::ModalGeneralization,
1105        InferenceRule::TemporalTransitivity,
1106        InferenceRule::TemporalInduction,
1107        InferenceRule::TemporalUnfolding,
1108        InferenceRule::EventualityProgress,
1109        InferenceRule::UntilInduction,
1110    ];
1111
1112    /// Resolve a rule NAME, as a proof script or a translator spells it: the variant's own
1113    /// name (`ModusPonens`) or its snake_case form (`modus_ponens`). Nothing else — a
1114    /// case-insensitive or punctuation-insensitive match would quietly accept `MODUSPONENS`
1115    /// and make a typo indistinguishable from a rule that does not exist.
1116    pub fn from_name(name: &str) -> Option<InferenceRule> {
1117        InferenceRule::NAMEABLE
1118            .iter()
1119            .find(|r| {
1120                let canonical = r.canonical_name();
1121                name == canonical || name == snake_case(&canonical)
1122            })
1123            .cloned()
1124    }
1125
1126    /// This rule's canonical name. A payload-free variant renders as its bare variant name —
1127    /// the spelling [`InferenceRule::from_name`] accepts; a payload-carrying one renders with
1128    /// its payload, which is what a derivation dump wants and what `from_name` deliberately
1129    /// cannot read back.
1130    pub fn canonical_name(&self) -> String {
1131        format!("{self:?}")
1132    }
1133
1134    /// Whether [`certifier::certify`] has an arm that builds a kernel term for
1135    /// this rule. The negation of [`InferenceRule::uncertifiable_reason`].
1136    pub fn is_certifiable(&self) -> bool {
1137        self.uncertifiable_reason().is_none()
1138    }
1139}
1140
1141// =============================================================================
1142// DERIVATION TREE - The recursive proof structure
1143// =============================================================================
1144
1145/// The "Euclidean Structure" - A recursive tree representing the proof.
1146///
1147/// This is the object returned by the Prover. It allows the UI to render
1148/// a step-by-step explanation (Natural Language Generation).
1149///
1150/// # Structure
1151///
1152/// Each node contains:
1153/// - `conclusion`: The proposition proved at this step
1154/// - `rule`: The logical rule applied (how we know the conclusion)
1155/// - `premises`: Sub-proofs justifying the rule's requirements
1156/// - `substitution`: Variable bindings from unification
1157///
1158/// # See Also
1159///
1160/// * [`BackwardChainer::prove`] - Creates derivation trees
1161/// * [`InferenceRule`] - The rules that justify each step
1162/// * [`ProofExpr`] - The conclusion type
1163/// * [`certifier::certify`] - Converts trees to kernel terms
1164/// * [`hints::suggest_hint`] - Suggests next steps when stuck
1165#[derive(Debug, Clone)]
1166pub struct DerivationTree {
1167    /// The logical statement proved at this node.
1168    pub conclusion: ProofExpr,
1169
1170    /// The rule applied to justify this conclusion.
1171    pub rule: InferenceRule,
1172
1173    /// The sub-proofs that validate the requirements of the rule.
1174    /// Example: ModusPonens will have 2 children (The Implication, The Antecedent).
1175    pub premises: Vec<DerivationTree>,
1176
1177    /// The depth of the tree (used for complexity limits).
1178    pub depth: usize,
1179
1180    /// The bindings unification discovered at this step — SEARCH TELEMETRY, not part of the
1181    /// claim.
1182    ///
1183    /// Ten sites in [`BackwardChainer`] write it and NOTHING in the repository reads it: not
1184    /// [`certifier::certify`], not [`verify::check_derivation`], not the derivation-document writer. Only the two
1185    /// eigenconstant-renaming walkers touch it, and they only carry it along. So a rule that
1186    /// recorded a substitution INSTEAD of instantiating its own conclusion would be believed by
1187    /// nobody and checked by nobody — the certified term would prove one proposition while the
1188    /// node claimed another, and every rule that computes from its own conclusion (a motive, a
1189    /// rewrite's endpoints) would compute from the stale one.
1190    ///
1191    /// What keeps that from happening is an invariant, not a checker: **a node's conclusion is a
1192    /// fixed point of its own substitution.** Every writer either applies it to the conclusion
1193    /// first or binds only variables the conclusion does not carry. It is locked by
1194    /// `T_tactics_extra::no_certified_node_records_a_substitution_its_conclusion_has_not_taken`,
1195    /// which sweeps the chainer and checks it directly — keep that green, or give the field a
1196    /// reader.
1197    pub substitution: unify::Substitution,
1198}
1199
1200impl DerivationTree {
1201    /// Constructs a new Proof Node.
1202    /// Automatically calculates depth based on children.
1203    pub fn new(conclusion: ProofExpr, rule: InferenceRule, premises: Vec<DerivationTree>) -> Self {
1204        let max_depth = premises.iter().map(|p| p.depth).max().unwrap_or(0);
1205        Self {
1206            conclusion,
1207            rule,
1208            premises,
1209            depth: max_depth + 1,
1210            substitution: unify::Substitution::new(),
1211        }
1212    }
1213
1214    /// A leaf node (usually a Premise, Axiom, or Oracle result).
1215    pub fn leaf(conclusion: ProofExpr, rule: InferenceRule) -> Self {
1216        Self::new(conclusion, rule, vec![])
1217    }
1218
1219    /// Set the substitution for this derivation step.
1220    pub fn with_substitution(mut self, subst: unify::Substitution) -> Self {
1221        self.substitution = subst;
1222        self
1223    }
1224
1225    /// Every node of this tree whose rule [`certifier::certify`] cannot build, as
1226    /// `(rule, why)` pairs in pre-order — empty when the whole tree is certifiable.
1227    ///
1228    /// **A proof PRODUCER runs this before handing the tree to
1229    /// [`verify::check_derivation`].** A `DerivationTree` is an ordinary Rust value:
1230    /// any rule can be put in any node, the result type-checks, and a dead rule is
1231    /// discovered only when certification reaches it — as a `verification_error`
1232    /// that reads like the kernel refusing a proof. Asking here instead makes the
1233    /// answer structural and keeps it where the producer can act on it: rebuild the
1234    /// node out of live rules, or reject the input.
1235    ///
1236    /// The dead rule is usually not at the root. A root of `ExFalso` over a subtree
1237    /// justified by `TemporalUnfolding` is well-formed everywhere except the one
1238    /// node that matters, which is why this walks the whole tree rather than
1239    /// answering about `self.rule`.
1240    pub fn uncertifiable_rules(&self) -> Vec<(String, &'static str)> {
1241        let mut out = Vec::new();
1242        self.collect_uncertifiable(&mut out);
1243        out
1244    }
1245
1246    fn collect_uncertifiable(&self, out: &mut Vec<(String, &'static str)>) {
1247        if let Some(why) = self.rule.uncertifiable_reason() {
1248            out.push((format!("{:?}", self.rule), why));
1249        }
1250        for premise in &self.premises {
1251            premise.collect_uncertifiable(out);
1252        }
1253    }
1254
1255    /// Renders the proof as a text-based tree (for debugging/CLI).
1256    pub fn display_tree(&self) -> String {
1257        self.display_recursive(0)
1258    }
1259
1260    fn display_recursive(&self, indent: usize) -> String {
1261        let prefix = "  ".repeat(indent);
1262
1263        let rule_name = match &self.rule {
1264            InferenceRule::UniversalInst(var) => format!("UniversalInst({})", var),
1265            InferenceRule::UniversalInstTerm(term) => format!("UniversalInst({})", term),
1266            InferenceRule::UniversalIntro { variable, var_type } => {
1267                format!("UniversalIntro({}:{})", variable, var_type)
1268            }
1269            InferenceRule::ExistentialIntro {
1270                witness,
1271                witness_type,
1272            } => {
1273                format!("∃Intro({}:{})", witness, witness_type)
1274            }
1275            InferenceRule::ExistentialIntroTerm {
1276                witness,
1277                witness_type,
1278            } => {
1279                format!("∃Intro({}:{})", witness, witness_type)
1280            }
1281            InferenceRule::StructuralInduction {
1282                variable,
1283                ind_type,
1284                step_var,
1285            } => {
1286                format!("Induction({}:{}, step={})", variable, ind_type, step_var)
1287            }
1288            InferenceRule::OracleVerification(s) => format!("Oracle({})", s),
1289            InferenceRule::Rewrite { from, to } => format!("Rewrite({} → {})", from, to),
1290            InferenceRule::RewriteAt {
1291                from,
1292                to,
1293                occurrence,
1294            } => {
1295                format!("Rewrite({} → {} @{})", from, to, occurrence)
1296            }
1297            InferenceRule::EqualitySymmetry => "EqSymmetry".to_string(),
1298            InferenceRule::EqualityTransitivity => "EqTransitivity".to_string(),
1299            r => format!("{:?}", r),
1300        };
1301
1302        let mut output = format!("{}└─ [{}] {}\n", prefix, rule_name, self.conclusion);
1303
1304        for premise in &self.premises {
1305            output.push_str(&premise.display_recursive(indent + 1));
1306        }
1307        output
1308    }
1309}
1310
1311impl fmt::Display for DerivationTree {
1312    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1313        write!(f, "{}", self.display_tree())
1314    }
1315}
1316
1317// =============================================================================
1318// PROOF GOAL - The target state for backward chaining
1319// =============================================================================
1320
1321/// The Goal State for the Backward Chainer.
1322///
1323/// Represents a "hole" in the proof that needs to be filled. During backward
1324/// chaining, goals are decomposed into subgoals until they match known facts.
1325///
1326/// # Fields
1327///
1328/// * `target` - What we are trying to prove
1329/// * `context` - Local assumptions (e.g., antecedents of implications we've entered)
1330///
1331/// # See Also
1332///
1333/// * [`BackwardChainer::prove`] - Takes a goal and produces a derivation tree
1334/// * [`DerivationTree`] - The result of successfully proving a goal
1335/// * [`ProofExpr`] - The target type
1336#[derive(Debug, Clone)]
1337pub struct ProofGoal {
1338    /// What we are trying to prove right now.
1339    pub target: ProofExpr,
1340
1341    /// The local assumptions available (e.g., inside an implication).
1342    pub context: Vec<ProofExpr>,
1343}
1344
1345impl ProofGoal {
1346    pub fn new(target: ProofExpr) -> Self {
1347        Self {
1348            target,
1349            context: Vec::new(),
1350        }
1351    }
1352
1353    pub fn with_context(target: ProofExpr, context: Vec<ProofExpr>) -> Self {
1354        Self { target, context }
1355    }
1356}