Skip to main content

logicaffeine_proof/
tactic.rs

1//! A tactic framework with a first-class goal state — the interactive proof
2//! interface (ROOT R5 of the Lean-competitive architecture).
3//!
4//! A [`ProofState`] holds the open [`Goal`]s; a *tactic* transforms the focused
5//! goal, replacing it with zero or more subgoals and recording the inference rule
6//! used. When no goals remain, [`ProofState::qed`] assembles the recorded steps
7//! into a single [`DerivationTree`] and runs it through the SAME trust door as
8//! every other proof ([`check_derivation`]): the certifier turns it into a kernel
9//! term and the kernel re-checks that term against the goal. So a tactic proof is
10//! exactly as trusted as an automated one — the tactics only *build* the
11//! derivation the kernel validates, they are never themselves trusted.
12//!
13//! The backward chainer is hosted here as the [`ProofState::auto`] tactic, so the
14//! existing automation is one tactic among many rather than the whole story.
15
16use std::collections::VecDeque;
17
18use logicaffeine_kernel::prelude::StandardLibrary;
19
20use crate::engine::BackwardChainer;
21use crate::unify::{
22    apply_subst_to_expr, apply_subst_to_term, instantiate_expr, unify_exprs, Substitution,
23};
24use crate::verify::{check_derivation, VerifiedProof};
25use crate::{DerivationTree, InductionArg, InductionCase, InferenceRule, ProofExpr, ProofTerm};
26
27/// A local hypothesis: its `name`, its proposition `prop`, and `proof` — a
28/// derivation that proves `prop` in the current local context. For a hypothesis
29/// that is directly in scope (a premise, an `intro`-discharged antecedent, or a
30/// branch hypothesis bound by `cases`) the proof is a `PremiseMatch` leaf the
31/// certifier resolves against the bound/registered hypothesis. For a conjunct
32/// extracted by `cases` from `A ∧ B`, the proof is the `ConjunctionElim`
33/// PROJECTION of the parent — so using the conjunct emits the projection, not a
34/// dangling reference. This is what lets elimination compose with the rest.
35#[derive(Debug, Clone)]
36pub struct Hyp {
37    pub name: String,
38    pub prop: ProofExpr,
39    proof: DerivationTree,
40}
41
42/// One constructor of an inductive, as given to [`ProofState::induction_over`]: its
43/// name and, per positional argument, whether that argument is itself of the
44/// inductive type — a recursive position that carries an induction hypothesis.
45/// `Nil` is `CtorSpec { constructor: "Nil", recursive: vec![] }`; `Cons` (head then
46/// tail) is `CtorSpec { constructor: "Cons", recursive: vec![false, true] }`.
47#[derive(Debug, Clone)]
48pub struct CtorSpec {
49    /// The constructor's name, as registered in the kernel (e.g. `"Cons"`).
50    pub constructor: String,
51    /// One flag per argument, in order: `true` iff that argument is recursive.
52    pub recursive: Vec<bool>,
53}
54
55/// A term as a proof SCRIPT writes it — the argument of `exact`, `have`, `refine`, `use`.
56///
57/// One syntax serves two languages, because Lean's does: the same `⟨a, b⟩` is a conjunction
58/// proof against `p ∧ q` and a witness-and-proof pair against `∃x. φ`, and the same bare
59/// name is a hypothesis in a proof position and a variable in a value position. Which
60/// language a term is read in is decided by the position, never by the term
61/// ([`ProofState::exact_term`] checks it as a proof, [`ProofState::value_term`] as a value).
62#[derive(Debug, Clone, PartialEq)]
63pub enum PTerm {
64    /// A bare name: a hypothesis, a bound variable, or a constant.
65    Ident(String),
66    /// Juxtaposition — `f a b`. Modus ponens over an implication, instantiation over a
67    /// universal, a function application in a value position.
68    App(Box<PTerm>, Vec<PTerm>),
69    /// The anonymous constructor `(a, b)` / `⟨a, b⟩`.
70    Tuple(Vec<PTerm>),
71    /// A `?_` / `?name` hole — a subgoal under `refine`, and an error anywhere else.
72    Hole,
73    /// An infix arithmetic operator, by its `ProofTerm` function name (`add`/`sub`/`mul`).
74    Op(&'static str, Box<PTerm>, Box<PTerm>),
75}
76
77/// Elaborate a script term as a VALUE, resolving each bare name against `bound` — the
78/// variables the surrounding proof has in scope.
79fn value_of(
80    term: &PTerm,
81    bound: &std::collections::BTreeSet<String>,
82) -> Result<ProofTerm, TacticError> {
83    match term {
84        PTerm::Ident(name) => Ok(if bound.contains(name) {
85            ProofTerm::Variable(name.clone())
86        } else {
87            ProofTerm::Constant(name.clone())
88        }),
89        PTerm::App(head, args) => {
90            let PTerm::Ident(name) = head.as_ref() else {
91                return Err(TacticError::DoesNotApply(
92                    "only a named function can be applied in a term position".to_string(),
93                ));
94            };
95            let args = args
96                .iter()
97                .map(|a| value_of(a, bound))
98                .collect::<Result<Vec<_>, _>>()?;
99            Ok(ProofTerm::Function(name.clone(), args))
100        }
101        PTerm::Op(op, l, r) => Ok(ProofTerm::Function(
102            (*op).to_string(),
103            vec![value_of(l, bound)?, value_of(r, bound)?],
104        )),
105        PTerm::Tuple(items) => Ok(ProofTerm::Group(
106            items
107                .iter()
108                .map(|a| value_of(a, bound))
109                .collect::<Result<Vec<_>, _>>()?,
110        )),
111        PTerm::Hole => Err(TacticError::DoesNotApply(
112            "a hole is not a value — there is nothing for it to stand for".to_string(),
113        )),
114    }
115}
116
117/// Instantiate a `∀`-quantified proposition until it IS the target, extending `proof` with
118/// the `UniversalInstTerm` chain that justifies each step.
119///
120/// This is what lets `exact h` close `P n` from `h : ∀m. P m`, which is ordinary Lean and
121/// the reason a `have` need not restate what it proves.
122fn instantiate_to(
123    prop: &ProofExpr,
124    target: &ProofExpr,
125    proof: DerivationTree,
126) -> Option<DerivationTree> {
127    let (vars, body) = peel_foralls(prop);
128    if vars.is_empty() {
129        return None;
130    }
131    let mut subst = Substitution::new();
132    if !match_expr_with(&body, target, &vars, &mut subst) {
133        return None;
134    }
135    let mut concl = prop.clone();
136    let mut tree = proof;
137    for v in &vars {
138        // A binder the body never pins down could be anything; refusing is the only honest
139        // answer, since picking a witness would prove a different theorem.
140        let witness = subst.get(v)?.clone();
141        concl = instantiate_forall(&concl, &witness)?;
142        tree = DerivationTree::new(
143            concl.clone(),
144            InferenceRule::UniversalInstTerm(witness),
145            vec![tree],
146        );
147    }
148    (concl == *target).then_some(tree)
149}
150
151/// One-sided match of a proposition `pattern` against `target`, where exactly `vars` are
152/// pattern variables.
153fn match_expr_with(
154    pattern: &ProofExpr,
155    target: &ProofExpr,
156    vars: &[String],
157    subst: &mut Substitution,
158) -> bool {
159    let term =
160        |p: &ProofTerm, t: &ProofTerm, s: &mut Substitution| match_term_with(p, t, vars, &[], s);
161    match (pattern, target) {
162        (
163            ProofExpr::Predicate {
164                name: n1,
165                args: a1,
166                world: w1,
167            },
168            ProofExpr::Predicate {
169                name: n2,
170                args: a2,
171                world: w2,
172            },
173        ) => {
174            n1 == n2
175                && w1 == w2
176                && a1.len() == a2.len()
177                && a1.iter().zip(a2).all(|(p, t)| term(p, t, subst))
178        }
179        (ProofExpr::Identity(l1, r1), ProofExpr::Identity(l2, r2)) => {
180            term(l1, l2, subst) && term(r1, r2, subst)
181        }
182        (ProofExpr::And(a, b), ProofExpr::And(c, d))
183        | (ProofExpr::Or(a, b), ProofExpr::Or(c, d))
184        | (ProofExpr::Implies(a, b), ProofExpr::Implies(c, d))
185        | (ProofExpr::Iff(a, b), ProofExpr::Iff(c, d)) => {
186            match_expr_with(a, c, vars, subst) && match_expr_with(b, d, vars, subst)
187        }
188        (ProofExpr::Not(a), ProofExpr::Not(b)) => match_expr_with(a, b, vars, subst),
189        (
190            ProofExpr::ForAll {
191                variable: v1,
192                body: b1,
193            },
194            ProofExpr::ForAll {
195                variable: v2,
196                body: b2,
197            },
198        )
199        | (
200            ProofExpr::Exists {
201                variable: v1,
202                body: b1,
203            },
204            ProofExpr::Exists {
205                variable: v2,
206                body: b2,
207            },
208        ) => v1 == v2 && match_expr_with(b1, b2, vars, subst),
209        (a, b) => a == b,
210    }
211}
212
213/// A single proof obligation: prove `target` under the local `hyps`.
214#[derive(Debug, Clone)]
215pub struct Goal {
216    /// Named local hypotheses in scope (introduced by `intro`/`cases`, or premises).
217    pub hyps: Vec<Hyp>,
218    /// The proposition to prove.
219    pub target: ProofExpr,
220}
221
222/// What went wrong applying a tactic.
223#[derive(Debug, Clone, PartialEq)]
224pub enum TacticError {
225    /// No focused goal — the proof state is already complete.
226    NoOpenGoals,
227    /// The tactic does not apply to the focused goal's shape (e.g. `intro` on an atom).
228    DoesNotApply(String),
229    /// No hypothesis (or premise) matches the goal for `assumption`/`exact`.
230    NoSuchHypothesis(String),
231    /// The backward chainer could not close the goal.
232    AutoFailed,
233    /// `qed` was called with goals still open.
234    GoalsRemain(usize),
235}
236
237/// A child of a refinement: either an already-complete proof or a fresh subgoal.
238enum Child {
239    Closed(DerivationTree),
240    Sub(Goal),
241}
242
243/// A node in the proof under construction.
244#[derive(Clone)]
245enum Node {
246    /// An unproved goal (a metavariable / hole).
247    Hole(Goal),
248    /// A complete sub-derivation (closed by `exact`/`assumption`/`auto`).
249    Done(DerivationTree),
250    /// A refinement: `rule` applied with the given children (indices into `nodes`).
251    Filled {
252        conclusion: ProofExpr,
253        rule: InferenceRule,
254        children: Vec<usize>,
255    },
256}
257
258/// The interactive proof state: the partial derivation plus the queue of open
259/// goals (front = focused). Tactics consume the focused goal and push any subgoals
260/// they create back to the front, so the proof is built depth-first, first-subgoal
261/// first — the order a reader expects. `Clone` is cheap relative to a proof and is
262/// what lets the backtracking combinators (`first`/`try`/`repeat`) speculate.
263#[derive(Clone)]
264pub struct ProofState {
265    premises: Vec<ProofExpr>,
266    goal: ProofExpr,
267    nodes: Vec<Node>,
268    root: usize,
269    open: VecDeque<usize>,
270    fresh: usize,
271}
272
273/// Replace every occurrence of the term `from` with `to` inside a term.
274fn replace_in_term(t: &ProofTerm, from: &ProofTerm, to: &ProofTerm) -> ProofTerm {
275    if t == from {
276        return to.clone();
277    }
278    match t {
279        ProofTerm::Function(n, args) => ProofTerm::Function(
280            n.clone(),
281            args.iter().map(|a| replace_in_term(a, from, to)).collect(),
282        ),
283        ProofTerm::Group(args) => {
284            ProofTerm::Group(args.iter().map(|a| replace_in_term(a, from, to)).collect())
285        }
286        other => other.clone(),
287    }
288}
289
290/// Replace every occurrence of the term `from` with `to` throughout an expression,
291/// IGNORING binding structure.
292///
293/// This is de-Skolemization, not substitution: [`eigen_to_var_tree`] uses it to turn a
294/// freshly-generated eigen-`Constant` back into the `Variable` the certifier's `Match` arm
295/// binds, across a whole derivation whose quantifier structure must survive untouched.
296/// Substituting INTO a scoped proposition is [`substitute_in_expr`], which is
297/// capture-avoiding; nothing else may use this one.
298fn replace_in_expr_raw(e: &ProofExpr, from: &ProofTerm, to: &ProofTerm) -> ProofExpr {
299    let re = |x: &ProofExpr| Box::new(replace_in_expr_raw(x, from, to));
300    let rt = |x: &ProofTerm| replace_in_term(x, from, to);
301    match e {
302        ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
303            name: name.clone(),
304            args: args.iter().map(rt).collect(),
305            world: world.clone(),
306        },
307        ProofExpr::Identity(l, r) => ProofExpr::Identity(rt(l), rt(r)),
308        ProofExpr::Atom(s) => ProofExpr::Atom(s.clone()),
309        ProofExpr::And(l, r) => ProofExpr::And(re(l), re(r)),
310        ProofExpr::Or(l, r) => ProofExpr::Or(re(l), re(r)),
311        ProofExpr::Implies(l, r) => ProofExpr::Implies(re(l), re(r)),
312        ProofExpr::Iff(l, r) => ProofExpr::Iff(re(l), re(r)),
313        ProofExpr::Not(p) => ProofExpr::Not(re(p)),
314        ProofExpr::ForAll { variable, body } => ProofExpr::ForAll {
315            variable: variable.clone(),
316            body: re(body),
317        },
318        ProofExpr::Exists { variable, body } => ProofExpr::Exists {
319            variable: variable.clone(),
320            body: re(body),
321        },
322        other => other.clone(),
323    }
324}
325
326/// The variable leaves of a term. `Constant` is a GLOBAL name and binds to nothing; only
327/// `Variable`/`BoundVarRef` are what a `ForAll`/`Exists` binder captures.
328fn term_vars(t: &ProofTerm, out: &mut std::collections::BTreeSet<String>) {
329    match t {
330        ProofTerm::Variable(n) | ProofTerm::BoundVarRef(n) => {
331            out.insert(n.clone());
332        }
333        ProofTerm::Function(_, args) | ProofTerm::Group(args) => {
334            for a in args {
335                term_vars(a, out);
336            }
337        }
338        ProofTerm::Constant(_) => {}
339    }
340}
341
342fn vars_of_term(t: &ProofTerm) -> std::collections::BTreeSet<String> {
343    let mut out = std::collections::BTreeSet::new();
344    term_vars(t, &mut out);
345    out
346}
347
348/// The FREE variables of an expression — binders remove their own variable.
349fn free_vars(e: &ProofExpr, out: &mut std::collections::BTreeSet<String>) {
350    match e {
351        ProofExpr::Predicate { args, .. } => {
352            for a in args {
353                term_vars(a, out);
354            }
355        }
356        ProofExpr::Identity(l, r) => {
357            term_vars(l, out);
358            term_vars(r, out);
359        }
360        ProofExpr::And(l, r)
361        | ProofExpr::Or(l, r)
362        | ProofExpr::Implies(l, r)
363        | ProofExpr::Iff(l, r) => {
364            free_vars(l, out);
365            free_vars(r, out);
366        }
367        ProofExpr::Not(p) => free_vars(p, out),
368        ProofExpr::ForAll { variable, body } | ProofExpr::Exists { variable, body } => {
369            let mut inner = std::collections::BTreeSet::new();
370            free_vars(body, &mut inner);
371            inner.remove(variable);
372            out.extend(inner);
373        }
374        ProofExpr::Term(t) => term_vars(t, out),
375        _ => {}
376    }
377}
378
379/// Every variable name the expression MENTIONS, bound ones included — the set a fresh
380/// binder name must avoid.
381fn all_vars(e: &ProofExpr, out: &mut std::collections::BTreeSet<String>) {
382    match e {
383        ProofExpr::ForAll { variable, body } | ProofExpr::Exists { variable, body } => {
384            out.insert(variable.clone());
385            all_vars(body, out);
386        }
387        ProofExpr::And(l, r)
388        | ProofExpr::Or(l, r)
389        | ProofExpr::Implies(l, r)
390        | ProofExpr::Iff(l, r) => {
391            all_vars(l, out);
392            all_vars(r, out);
393        }
394        ProofExpr::Not(p) => all_vars(p, out),
395        other => free_vars(other, out),
396    }
397}
398
399/// The CONSTANT names an expression mentions — the global symbols, as distinct from the
400/// variables [`all_vars`] collects.
401fn constants_of(e: &ProofExpr, out: &mut std::collections::BTreeSet<String>) {
402    fn term(t: &ProofTerm, out: &mut std::collections::BTreeSet<String>) {
403        match t {
404            ProofTerm::Constant(n) => {
405                out.insert(n.clone());
406            }
407            ProofTerm::Function(n, args) => {
408                out.insert(n.clone());
409                for a in args {
410                    term(a, out);
411                }
412            }
413            ProofTerm::Group(args) => {
414                for a in args {
415                    term(a, out);
416                }
417            }
418            _ => {}
419        }
420    }
421    match e {
422        ProofExpr::Predicate { args, .. } => {
423            for a in args {
424                term(a, out);
425            }
426        }
427        ProofExpr::Identity(l, r) => {
428            term(l, out);
429            term(r, out);
430        }
431        ProofExpr::Term(t) => term(t, out),
432        ProofExpr::And(l, r)
433        | ProofExpr::Or(l, r)
434        | ProofExpr::Implies(l, r)
435        | ProofExpr::Iff(l, r) => {
436            constants_of(l, out);
437            constants_of(r, out);
438        }
439        ProofExpr::Not(p) => constants_of(p, out),
440        ProofExpr::ForAll { body, .. } | ProofExpr::Exists { body, .. } => constants_of(body, out),
441        _ => {}
442    }
443}
444
445/// A name close to `base` that no name in `taken` uses.
446fn fresh_name(base: &str, taken: &std::collections::BTreeSet<String>) -> String {
447    for i in 1.. {
448        let candidate = format!("{base}_{i}");
449        if !taken.contains(&candidate) {
450            return candidate;
451        }
452    }
453    unreachable!("the integers are not exhausted")
454}
455
456/// α-rename the free occurrences of the variable `old` to `new` inside `e`, stopping at any
457/// binder that re-binds `old`. `new` must be fresh for `e` (see [`fresh_name`]), which is
458/// what makes this rename itself capture-free.
459fn rename_free_var(e: &ProofExpr, old: &str, new: &str) -> ProofExpr {
460    match e {
461        ProofExpr::ForAll { variable, .. } | ProofExpr::Exists { variable, .. }
462            if variable == old =>
463        {
464            e.clone()
465        }
466        ProofExpr::ForAll { variable, body } => ProofExpr::ForAll {
467            variable: variable.clone(),
468            body: Box::new(rename_free_var(body, old, new)),
469        },
470        ProofExpr::Exists { variable, body } => ProofExpr::Exists {
471            variable: variable.clone(),
472            body: Box::new(rename_free_var(body, old, new)),
473        },
474        other => replace_in_expr_shallow(other, old, new),
475    }
476}
477
478/// One non-quantifier layer of [`rename_free_var`].
479fn replace_in_expr_shallow(e: &ProofExpr, old: &str, new: &str) -> ProofExpr {
480    let from = ProofTerm::Variable(old.to_string());
481    let to = ProofTerm::Variable(new.to_string());
482    let rt = |x: &ProofTerm| replace_in_term(x, &from, &to);
483    let re = |x: &ProofExpr| Box::new(rename_free_var(x, old, new));
484    match e {
485        ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
486            name: name.clone(),
487            args: args.iter().map(rt).collect(),
488            world: world.clone(),
489        },
490        ProofExpr::Identity(l, r) => ProofExpr::Identity(rt(l), rt(r)),
491        ProofExpr::And(l, r) => ProofExpr::And(re(l), re(r)),
492        ProofExpr::Or(l, r) => ProofExpr::Or(re(l), re(r)),
493        ProofExpr::Implies(l, r) => ProofExpr::Implies(re(l), re(r)),
494        ProofExpr::Iff(l, r) => ProofExpr::Iff(re(l), re(r)),
495        ProofExpr::Not(p) => ProofExpr::Not(re(p)),
496        ProofExpr::Term(t) => ProofExpr::Term(rt(t)),
497        other => other.clone(),
498    }
499}
500
501/// CAPTURE-AVOIDING substitution: replace every FREE occurrence of the term `from` with
502/// `to` throughout a scoped expression. This is the Leibniz substitution `rewrite` and
503/// `simp` perform on a goal, and it is the only substitution either may use.
504///
505/// Two hazards, both handled here rather than by a caller-side refusal:
506///
507/// * **Shadowing.** A binder that re-binds one of `from`'s free variables introduces a
508///   DIFFERENT variable of the same spelling, so the pattern has no occurrence beneath it;
509///   the quantifier is left alone and the free occurrences beside it are still rewritten. A
510///   patch that refused the whole rewrite instead would silently under-rewrite.
511/// * **Capture.** A binder that binds one of `to`'s free variables would capture the
512///   replacement, turning a claim about one entity into a claim about the quantified one.
513///   The binder is α-renamed away first, so the replacement's variable stays free and stays
514///   distinct.
515pub(crate) fn substitute_in_expr(e: &ProofExpr, from: &ProofTerm, to: &ProofTerm) -> ProofExpr {
516    let re = |x: &ProofExpr| Box::new(substitute_in_expr(x, from, to));
517    let rt = |x: &ProofTerm| replace_in_term(x, from, to);
518    match e {
519        ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
520            name: name.clone(),
521            args: args.iter().map(rt).collect(),
522            world: world.clone(),
523        },
524        ProofExpr::Identity(l, r) => ProofExpr::Identity(rt(l), rt(r)),
525        ProofExpr::And(l, r) => ProofExpr::And(re(l), re(r)),
526        ProofExpr::Or(l, r) => ProofExpr::Or(re(l), re(r)),
527        ProofExpr::Implies(l, r) => ProofExpr::Implies(re(l), re(r)),
528        ProofExpr::Iff(l, r) => ProofExpr::Iff(re(l), re(r)),
529        ProofExpr::Not(p) => ProofExpr::Not(re(p)),
530        ProofExpr::Term(t) => ProofExpr::Term(rt(t)),
531        ProofExpr::ForAll { .. } | ProofExpr::Exists { .. } => substitute_under_binder(e, from, to),
532        other => other.clone(),
533    }
534}
535
536fn substitute_under_binder(e: &ProofExpr, from: &ProofTerm, to: &ProofTerm) -> ProofExpr {
537    let (variable, body, is_forall) = match e {
538        ProofExpr::ForAll { variable, body } => (variable.clone(), (**body).clone(), true),
539        ProofExpr::Exists { variable, body } => (variable.clone(), (**body).clone(), false),
540        other => return other.clone(),
541    };
542    // Shadowing: beneath this binder `variable` is a different variable, so the pattern
543    // simply does not occur there.
544    if vars_of_term(from).contains(&variable) {
545        return e.clone();
546    }
547    // Capture: α-rename the binder out of the replacement's way first.
548    let (variable, body) = if vars_of_term(to).contains(&variable) {
549        let mut taken = vars_of_term(to);
550        taken.extend(vars_of_term(from));
551        all_vars(&body, &mut taken);
552        let fresh = fresh_name(&variable, &taken);
553        let renamed = rename_free_var(&body, &variable, &fresh);
554        (fresh, renamed)
555    } else {
556        (variable, body)
557    };
558    let body = Box::new(substitute_in_expr(&body, from, to));
559    if is_forall {
560        ProofExpr::ForAll { variable, body }
561    } else {
562        ProofExpr::Exists { variable, body }
563    }
564}
565
566/// POSITIONAL substitution: replace the `target`-th FREE occurrence of `from` with `to`,
567/// leaving every other occurrence alone, and report how many free occurrences there were.
568///
569/// [`substitute_in_expr`] rewrites them all, which is why `rewrite` could only ever turn
570/// `P(a, a)` into `P(b, b)` — and `P(b, a)` is a different goal, frequently the only provable
571/// one. That is the whole reason Lean has `conv` and occurrence arguments.
572///
573/// The binder discipline is EXACTLY [`substitute_under_binder`]'s, and that is load-bearing
574/// in both directions: an occurrence the goal BINDS is not an occurrence of the pattern (so
575/// it is not counted either — the indices a caller passes must mean the same thing as the
576/// ones this counts), and a binder that would capture the replacement's free variable is
577/// α-renamed away first. Counting only free occurrences keeps the index stable under the
578/// α-renaming the capture case performs.
579struct OccurrenceSubst<'a> {
580    from: &'a ProofTerm,
581    to: &'a ProofTerm,
582    target: usize,
583    seen: usize,
584}
585
586impl OccurrenceSubst<'_> {
587    fn term(&mut self, t: &ProofTerm) -> ProofTerm {
588        if t == self.from {
589            let here = self.seen;
590            self.seen += 1;
591            return if here == self.target {
592                self.to.clone()
593            } else {
594                t.clone()
595            };
596        }
597        match t {
598            ProofTerm::Function(n, args) => {
599                let mut out = Vec::with_capacity(args.len());
600                for a in args {
601                    out.push(self.term(a));
602                }
603                ProofTerm::Function(n.clone(), out)
604            }
605            ProofTerm::Group(args) => {
606                let mut out = Vec::with_capacity(args.len());
607                for a in args {
608                    out.push(self.term(a));
609                }
610                ProofTerm::Group(out)
611            }
612            other => other.clone(),
613        }
614    }
615
616    fn expr(&mut self, e: &ProofExpr) -> ProofExpr {
617        match e {
618            ProofExpr::Predicate { name, args, world } => {
619                let mut out = Vec::with_capacity(args.len());
620                for a in args {
621                    out.push(self.term(a));
622                }
623                ProofExpr::Predicate {
624                    name: name.clone(),
625                    args: out,
626                    world: world.clone(),
627                }
628            }
629            ProofExpr::Identity(l, r) => {
630                let l2 = self.term(l);
631                let r2 = self.term(r);
632                ProofExpr::Identity(l2, r2)
633            }
634            ProofExpr::And(l, r) => {
635                let l2 = self.expr(l);
636                let r2 = self.expr(r);
637                ProofExpr::And(Box::new(l2), Box::new(r2))
638            }
639            ProofExpr::Or(l, r) => {
640                let l2 = self.expr(l);
641                let r2 = self.expr(r);
642                ProofExpr::Or(Box::new(l2), Box::new(r2))
643            }
644            ProofExpr::Implies(l, r) => {
645                let l2 = self.expr(l);
646                let r2 = self.expr(r);
647                ProofExpr::Implies(Box::new(l2), Box::new(r2))
648            }
649            ProofExpr::Iff(l, r) => {
650                let l2 = self.expr(l);
651                let r2 = self.expr(r);
652                ProofExpr::Iff(Box::new(l2), Box::new(r2))
653            }
654            ProofExpr::Not(p) => ProofExpr::Not(Box::new(self.expr(p))),
655            ProofExpr::Term(t) => ProofExpr::Term(self.term(t)),
656            ProofExpr::ForAll { .. } | ProofExpr::Exists { .. } => self.under_binder(e),
657            other => other.clone(),
658        }
659    }
660
661    fn under_binder(&mut self, e: &ProofExpr) -> ProofExpr {
662        let (variable, body, is_forall) = match e {
663            ProofExpr::ForAll { variable, body } => (variable.clone(), (**body).clone(), true),
664            ProofExpr::Exists { variable, body } => (variable.clone(), (**body).clone(), false),
665            other => return other.clone(),
666        };
667        // Shadowing: beneath this binder the pattern's variable is a DIFFERENT variable, so
668        // the pattern does not occur here and nothing beneath is counted.
669        if vars_of_term(self.from).contains(&variable) {
670            return e.clone();
671        }
672        // Capture: α-rename the binder out of the replacement's way first.
673        let (variable, body) = if vars_of_term(self.to).contains(&variable) {
674            let mut taken = vars_of_term(self.to);
675            taken.extend(vars_of_term(self.from));
676            all_vars(&body, &mut taken);
677            let fresh = fresh_name(&variable, &taken);
678            let renamed = rename_free_var(&body, &variable, &fresh);
679            (fresh, renamed)
680        } else {
681            (variable, body)
682        };
683        let body = Box::new(self.expr(&body));
684        if is_forall {
685            ProofExpr::ForAll { variable, body }
686        } else {
687            ProofExpr::Exists { variable, body }
688        }
689    }
690}
691
692/// `(rewritten, free occurrences seen)` for the `occurrence`-th free match of `from`.
693/// `occurrence >= seen` means there is no such occurrence and nothing was replaced.
694/// Pass `usize::MAX` to COUNT without replacing anything.
695pub(crate) fn substitute_occurrence_in_expr(
696    e: &ProofExpr,
697    from: &ProofTerm,
698    to: &ProofTerm,
699    occurrence: usize,
700) -> (ProofExpr, usize) {
701    let mut subst = OccurrenceSubst {
702        from,
703        to,
704        target: occurrence,
705        seen: 0,
706    };
707    let out = subst.expr(e);
708    (out, subst.seen)
709}
710
711/// Strip a `∀` prefix, returning the binder names in order and the body beneath them.
712/// The binders are exactly the pattern variables of a quantified rule.
713fn peel_foralls(e: &ProofExpr) -> (Vec<String>, ProofExpr) {
714    let mut vars = Vec::new();
715    let mut cur = e.clone();
716    while let ProofExpr::ForAll { variable, body } = cur {
717        vars.push(variable);
718        cur = *body;
719    }
720    (vars, cur)
721}
722
723/// Move the `∀` binder named `variable` to the FRONT of the goal's quantifier prefix,
724/// keeping the other binders in their relative order. `∀m n. Q m n` at `n` becomes
725/// `∀n m. Q m n` — the same theorem (independent universals commute), stated so that the
726/// variable to induct on is the one a structural-induction motive can abstract.
727fn reorder_forall_prefix(e: &ProofExpr, variable: &str) -> Option<ProofExpr> {
728    let (prefix, body) = peel_foralls(e);
729    if !prefix.iter().any(|v| v == variable) {
730        return None;
731    }
732    let mut order: Vec<&String> = prefix.iter().filter(|v| *v != variable).collect();
733    let moved = variable.to_string();
734    order.insert(0, &moved);
735    let mut out = body;
736    for v in order.into_iter().rev() {
737        out = ProofExpr::ForAll {
738            variable: v.clone(),
739            body: Box::new(out),
740        };
741    }
742    Some(out)
743}
744
745/// Recover the inductive type and its constructor set for a goal `∀x. body` from the
746/// hypotheses in scope — the induction PRINCIPLE stated as premises, which is how a
747/// structural-induction goal reaches the tactic layer in an untyped `ProofExpr`.
748///
749/// A hypothesis `body[x := C]` names the nullary constructor `C`; a hypothesis
750/// `∀a₁…aₙ. body[x := aᵢ] → … → body[x := C(a₁…aₙ)]` names `C`, with a recursive position
751/// at every `aᵢ` that carries an induction hypothesis. Constructors come back in the order
752/// their hypotheses appear, which is the order the subgoals are then presented in. `None`
753/// when the scope names no constructor at all, or names constructors of two different types.
754fn infer_ctors(variable: &str, body: &ProofExpr, hyps: &[Hyp]) -> Option<(String, Vec<CtorSpec>)> {
755    let at = |t: ProofTerm| -> ProofExpr { instantiate_expr(body, variable, &t) };
756    let mut ind_type: Option<String> = None;
757    let mut ctors: Vec<CtorSpec> = Vec::new();
758    for h in hyps {
759        let Some((ctor, recursive)) = constructor_case(&h.prop, &at) else {
760            continue;
761        };
762        let owner = inductive_of_constructor(&ctor)?;
763        match &ind_type {
764            Some(t) if t != &owner => return None,
765            _ => ind_type = Some(owner),
766        }
767        if ctors.iter().any(|c| c.constructor == ctor) {
768            continue;
769        }
770        ctors.push(CtorSpec {
771            constructor: ctor,
772            recursive,
773        });
774    }
775    match ind_type {
776        Some(t) if !ctors.is_empty() => Some((t, ctors)),
777        _ => None,
778    }
779}
780
781/// Read one hypothesis as one constructor case of an induction principle: its constructor
782/// and, per argument position, whether that argument carries an induction hypothesis.
783///
784/// How many of the hypothesis's leading `∀`s are the CONSTRUCTOR's arguments is not known in
785/// advance — the motive may itself be quantified (`∀m. Q(m, Zero)` is the whole base case,
786/// where `∀h t. P(t) → P(ECons h t)` binds two constructor arguments). So each prefix length
787/// is tried in turn and the shortest that yields a confirmed constructor application wins.
788fn constructor_case(
789    prop: &ProofExpr,
790    at: &dyn Fn(ProofTerm) -> ProofExpr,
791) -> Option<(String, Vec<bool>)> {
792    let (prefix, base) = peel_foralls(prop);
793    for depth in 0..=prefix.len() {
794        // Re-wrap the binders this reading does NOT treat as constructor arguments.
795        let mut rest = base.clone();
796        for v in prefix[depth..].iter().rev() {
797            rest = ProofExpr::ForAll {
798                variable: v.clone(),
799                body: Box::new(rest),
800            };
801        }
802        let mut antecedents = Vec::new();
803        while let ProofExpr::Implies(a, b) = rest {
804            antecedents.push(*a);
805            rest = *b;
806        }
807        let Some((ctor, ctor_args)) = constructor_application(&rest, at) else {
808            continue;
809        };
810        // Every argument must be one of the binders this reading claimed, or the conclusion
811        // is some other fact that merely mentions the same symbol.
812        let args = &prefix[..depth];
813        if !ctor_args.iter().all(
814            |a| matches!(a, ProofTerm::Variable(n) | ProofTerm::Constant(n) if args.contains(n)),
815        ) {
816            continue;
817        }
818        let recursive = ctor_args
819            .iter()
820            .map(|arg| antecedents.iter().any(|ant| *ant == at(arg.clone())))
821            .collect();
822        return Some((ctor, recursive));
823    }
824    None
825}
826
827/// If `conclusion` is `body[x := C]` or `body[x := C(ā)]` for some symbol `C`, return `C`
828/// and its arguments. `at` re-substitutes so the guess is CONFIRMED rather than pattern-
829/// matched out of the shape.
830fn constructor_application(
831    conclusion: &ProofExpr,
832    at: &dyn Fn(ProofTerm) -> ProofExpr,
833) -> Option<(String, Vec<ProofTerm>)> {
834    let mut candidates = Vec::new();
835    collect_head_terms(conclusion, &mut candidates);
836    candidates.into_iter().find_map(|candidate| {
837        let (name, args) = match &candidate {
838            ProofTerm::Constant(n) => (n.clone(), Vec::new()),
839            ProofTerm::Function(n, a) => (n.clone(), a.clone()),
840            _ => return None,
841        };
842        (at(candidate) == *conclusion).then_some((name, args))
843    })
844}
845
846/// Every term the expression carries, outermost first — the candidates for "the term the
847/// induction variable was replaced by".
848fn collect_head_terms(e: &ProofExpr, out: &mut Vec<ProofTerm>) {
849    match e {
850        ProofExpr::Predicate { args, .. } => out.extend(args.iter().cloned()),
851        ProofExpr::Identity(l, r) => {
852            out.push(l.clone());
853            out.push(r.clone());
854        }
855        ProofExpr::Term(t) => out.push(t.clone()),
856        ProofExpr::And(l, r)
857        | ProofExpr::Or(l, r)
858        | ProofExpr::Implies(l, r)
859        | ProofExpr::Iff(l, r) => {
860            collect_head_terms(l, out);
861            collect_head_terms(r, out);
862        }
863        ProofExpr::Not(p) => collect_head_terms(p, out),
864        ProofExpr::ForAll { body, .. } | ProofExpr::Exists { body, .. } => {
865            collect_head_terms(body, out)
866        }
867        _ => {}
868    }
869}
870
871/// Instantiate the outermost `∀` of `e` at `witness`, or `None` if `e` is not quantified.
872fn instantiate_forall(e: &ProofExpr, witness: &ProofTerm) -> Option<ProofExpr> {
873    match e {
874        ProofExpr::ForAll { variable, body } => {
875            // Instantiating a binder AT ITSELF is the identity. It must be taken as one:
876            // `apply_subst_to_term` chases `{z ↦ z}` forever, which is why `intro` skips the
877            // rename in exactly this case.
878            if matches!(
879                witness,
880                ProofTerm::Variable(n) | ProofTerm::BoundVarRef(n) if n == variable
881            ) {
882                return Some((**body).clone());
883            }
884            Some(instantiate_expr(body, variable, witness))
885        }
886        _ => None,
887    }
888}
889
890/// One-sided match of `pattern` against `target`, where exactly the names in `vars` are
891/// pattern variables. Every other `Variable` is rigid and matches only itself. A binding
892/// that mentions a name in `rigid` (a variable the GOAL binds at the match site) is
893/// rejected: the instantiation would escape its scope.
894fn match_term_with(
895    pattern: &ProofTerm,
896    target: &ProofTerm,
897    vars: &[String],
898    rigid: &[String],
899    subst: &mut Substitution,
900) -> bool {
901    match pattern {
902        ProofTerm::Variable(n) if vars.iter().any(|v| v == n) => {
903            if vars_of_term(target)
904                .iter()
905                .any(|t| rigid.iter().any(|r| r == t))
906            {
907                return false;
908            }
909            match subst.get(n) {
910                Some(bound) => bound == target,
911                None => {
912                    subst.insert(n.clone(), target.clone());
913                    true
914                }
915            }
916        }
917        ProofTerm::Function(name, args) => match target {
918            ProofTerm::Function(n2, a2) if name == n2 && args.len() == a2.len() => args
919                .iter()
920                .zip(a2.iter())
921                .all(|(p, t)| match_term_with(p, t, vars, rigid, subst)),
922            _ => false,
923        },
924        ProofTerm::Group(args) => match target {
925            ProofTerm::Group(a2) if args.len() == a2.len() => args
926                .iter()
927                .zip(a2.iter())
928                .all(|(p, t)| match_term_with(p, t, vars, rigid, subst)),
929            _ => false,
930        },
931        other => other == target,
932    }
933}
934
935/// The first subterm of `t` (outermost, then left to right) that `pattern` matches.
936fn first_match_in_term(
937    t: &ProofTerm,
938    pattern: &ProofTerm,
939    vars: &[String],
940    rigid: &[String],
941) -> Option<Substitution> {
942    let mut subst = Substitution::new();
943    if match_term_with(pattern, t, vars, rigid, &mut subst) {
944        return Some(subst);
945    }
946    match t {
947        ProofTerm::Function(_, args) | ProofTerm::Group(args) => args
948            .iter()
949            .find_map(|a| first_match_in_term(a, pattern, vars, rigid)),
950        _ => None,
951    }
952}
953
954/// The first subterm of the EXPRESSION `e` that `pattern` matches, in the reading order a
955/// proof has — outermost before inner, left before right. Beneath a `ForAll`/`Exists` the
956/// binder joins `rigid`, so a match may not bind a pattern variable to something the goal
957/// binds (that instantiation would escape the quantifier).
958fn first_match_in_expr(
959    e: &ProofExpr,
960    pattern: &ProofTerm,
961    vars: &[String],
962) -> Option<Substitution> {
963    fn go(
964        e: &ProofExpr,
965        pattern: &ProofTerm,
966        vars: &[String],
967        rigid: &mut Vec<String>,
968    ) -> Option<Substitution> {
969        let term = |t: &ProofTerm| first_match_in_term(t, pattern, vars, rigid);
970        match e {
971            ProofExpr::Predicate { args, .. } => args.iter().find_map(term),
972            ProofExpr::Identity(l, r) => term(l).or_else(|| term(r)),
973            ProofExpr::Term(t) => term(t),
974            ProofExpr::And(l, r)
975            | ProofExpr::Or(l, r)
976            | ProofExpr::Implies(l, r)
977            | ProofExpr::Iff(l, r) => {
978                go(l, pattern, vars, rigid).or_else(|| go(r, pattern, vars, rigid))
979            }
980            ProofExpr::Not(p) => go(p, pattern, vars, rigid),
981            ProofExpr::ForAll { variable, body } | ProofExpr::Exists { variable, body } => {
982                // A binder that re-binds one of the pattern's OWN rigid variables shadows it:
983                // the pattern does not occur beneath it at all.
984                if vars_of_term(pattern).contains(variable) && !vars.iter().any(|v| v == variable) {
985                    return None;
986                }
987                rigid.push(variable.clone());
988                let found = go(body, pattern, vars, rigid);
989                rigid.pop();
990                found
991            }
992            _ => None,
993        }
994    }
995    go(e, pattern, vars, &mut Vec::new())
996}
997
998/// Rewrite the eigen-`Constant` `name` back to `Variable(name)` throughout a
999/// derivation — the generalization step for `induction`'s step case, turning the
1000/// rigid search variable into the one the certifier's `Match` arm binds.
1001fn eigen_to_var_tree(tree: &DerivationTree, name: &str) -> DerivationTree {
1002    let from = ProofTerm::Constant(name.to_string());
1003    let to = ProofTerm::Variable(name.to_string());
1004    // Every payload this rule carries, through the ONE exhaustive mapper — a rule whose
1005    // witness or motive still named the eigenconstant while the conclusion around it was
1006    // renamed is a tree the certifier computes one proposition from and checks another.
1007    let rule = tree.rule.map_payload(
1008        &|n: &str| n.to_string(),
1009        &|t: &ProofTerm| replace_in_term(t, &from, &to),
1010        &|e: &ProofExpr| replace_in_expr_raw(e, &from, &to),
1011    );
1012    DerivationTree {
1013        conclusion: replace_in_expr_raw(&tree.conclusion, &from, &to),
1014        rule,
1015        premises: tree
1016            .premises
1017            .iter()
1018            .map(|p| eigen_to_var_tree(p, name))
1019            .collect(),
1020        depth: tree.depth,
1021        substitution: tree.substitution.clone(),
1022    }
1023}
1024
1025/// A hypothesis directly in scope (premise / `intro` / `cases`-branch): its proof
1026/// is a `PremiseMatch` leaf the certifier resolves against the bound or registered
1027/// hypothesis of the same proposition.
1028/// The ∃-introduction rule for a witness: the NAME-carrying
1029/// [`InferenceRule::ExistentialIntro`] for a bare `Constant`, the TERM-carrying
1030/// [`InferenceRule::ExistentialIntroTerm`] for everything else.
1031///
1032/// The split is not a fast path, it is a FAITHFULNESS one. `ExistentialIntro`'s witness is a
1033/// `String` that the certifier resolves as a local `Var` or a global `Global` by asking
1034/// whether the surrounding traversal has bound that name — which is right for a constant and
1035/// wrong for a `Variable`, whose lowering is unconditionally `Term::Var`: a proof-level
1036/// variable free in the THEOREM (not bound by any `intro`) would resolve to a `Global` while
1037/// the goal type mentions the `Var`, and the two would not match. Carrying the term lowers it
1038/// once, the same way everywhere.
1039fn witness_rule(witness: &ProofTerm, witness_type: String) -> InferenceRule {
1040    match witness {
1041        ProofTerm::Constant(name) => InferenceRule::ExistentialIntro {
1042            witness: name.clone(),
1043            witness_type,
1044        },
1045        other => InferenceRule::ExistentialIntroTerm {
1046            witness: other.clone(),
1047            witness_type,
1048        },
1049    }
1050}
1051
1052fn direct_hyp(name: String, prop: ProofExpr) -> Hyp {
1053    let proof = DerivationTree::leaf(prop.clone(), InferenceRule::PremiseMatch);
1054    Hyp { name, prop, proof }
1055}
1056
1057/// `¬p` and `p → False` are the SAME proposition — `certifier::proof_expr_to_type` lowers both to
1058/// `Π(_:p). False`. The tactic layer compared `ProofExpr`s structurally, so it alone told them
1059/// apart: `intro` had no image on a negation goal, and `assumption` could not see a `¬p` hypothesis
1060/// discharging a `p → False` target or vice versa. Normalising at every comparison point keeps the
1061/// two layers agreeing about what a proposition IS, rather than patching each tactic separately.
1062fn unfold_not(e: &ProofExpr) -> ProofExpr {
1063    match e {
1064        ProofExpr::Not(p) => ProofExpr::Implies(
1065            Box::new(unfold_not(p)),
1066            Box::new(ProofExpr::Atom(FALSUM.to_string())),
1067        ),
1068        // The falsum has three spellings in the wild and `certifier.rs` accepts all three, so a
1069        // comparison that does not canonicalise them tells apart two propositions the kernel
1070        // cannot. Recurse into implications so `¬¬p` and `(p → ⊥) → False` agree too.
1071        ProofExpr::Atom(n) if is_falsum(n) => ProofExpr::Atom(FALSUM.to_string()),
1072        ProofExpr::Implies(a, b) => {
1073            ProofExpr::Implies(Box::new(unfold_not(a)), Box::new(unfold_not(b)))
1074        }
1075        other => other.clone(),
1076    }
1077}
1078
1079/// The canonical spelling of falsum inside [`unfold_not`].
1080const FALSUM: &str = "⊥";
1081
1082/// The three spellings `certifier.rs` treats as falsum.
1083fn is_falsum(name: &str) -> bool {
1084    name == "⊥" || name == "False" || name == "false"
1085}
1086
1087/// Is this proposition the absurdity, under any of its spellings?
1088fn is_falsum_expr(e: &ProofExpr) -> bool {
1089    matches!(e, ProofExpr::Atom(n) if is_falsum(n))
1090}
1091
1092/// Do `l` and `r` denote the same polynomial over the commutative-ring vocabulary?
1093///
1094/// Asks the arithmetic oracle that `InferenceRule::ArithDecision` certifies through, on a
1095/// context carrying the ring axioms — so the tactic's YES and the kernel's YES are the same
1096/// question, put to the same decision procedure, rather than two implementations that can
1097/// drift apart.
1098/// Is `l = r` a formal identity of the commutative ring — the question `ring` and
1099/// `ArithDecision` both answer? Exposed for [`crate::omega_solve`], whose goal-directed half
1100/// discharges an `Int` EQUALITY goal (`n + 0 = n`, an `omega` goal in Lean) through the same
1101/// oracle rather than a second copy of the decision.
1102pub(crate) fn int_identity_holds(l: &ProofTerm, r: &ProofTerm) -> bool {
1103    ring_identity_holds(l, r)
1104}
1105
1106/// Is this term BOOL-valued — a comparison in the canonical `le(a, b) = true` encoding, or a
1107/// Bool literal — rather than an `Int` term?
1108///
1109/// [`crate::arith::prove_int_eq`] answers about VALUES, and `le(2, 3)` computes to `true`, so
1110/// it cheerfully agrees that `le(2, 3) = true` is an identity. The PROPOSITION is true; the
1111/// certificate `ring` would emit is not, because [`InferenceRule::ArithDecision`] lowers to an
1112/// `Eq Int` fact and the kernel then reports "expected Int, found Bool" about a correct
1113/// statement — a tactic reporting success and the trust door refusing it. Comparisons belong
1114/// to `decide` (ground) and `omega` (symbolic), both of which certify them properly.
1115fn is_bool_valued(t: &ProofTerm) -> bool {
1116    match t {
1117        ProofTerm::Constant(c) => c == "true" || c == "false",
1118        ProofTerm::Function(name, _) => {
1119            matches!(
1120                name.as_str(),
1121                "le" | "lt" | "ge" | "gt" | "eq" | "and" | "or" | "not"
1122            )
1123        }
1124        _ => false,
1125    }
1126}
1127
1128fn ring_identity_holds(l: &ProofTerm, r: &ProofTerm) -> bool {
1129    let (Ok(kl), Ok(kr)) = (
1130        crate::certifier::proof_term_to_kernel_term(l),
1131        crate::certifier::proof_term_to_kernel_term(r),
1132    ) else {
1133        return false;
1134    };
1135    crate::arith::prove_int_eq(StandardLibrary::context(), &kl, &kr).is_some()
1136}
1137
1138/// The first NULLARY constructor of a prelude inductive — its closed base point, read off the
1139/// registered constructor signatures rather than a table (`Nat ↦ Zero`, `EList ↦ ENil`).
1140///
1141/// Used by `ProofState::induction_generalizing` to land back on the original goal after a
1142/// VACUOUS generalization: when the induction variable occurs nowhere, `∀v:T. G ⊢ G` needs an
1143/// inhabitant of `T` and nothing else. An inductive with no nullary constructor has no such
1144/// closed point at this layer, and the caller says so instead of guessing one.
1145fn nullary_constructor(ind_type: &str) -> Option<String> {
1146    use logicaffeine_kernel::Term;
1147    StandardLibrary::context()
1148        .get_constructors(ind_type)
1149        .into_iter()
1150        .find(|(_, ty)| !matches!(ty, Term::Pi { .. }))
1151        .map(|(name, _)| name.to_string())
1152}
1153
1154/// The inductive type a prelude CONSTRUCTOR belongs to, read off its registered kernel
1155/// signature (`Π…. Ind`) rather than a table this file would have to keep in step.
1156fn inductive_of_constructor(ctor: &str) -> Option<String> {
1157    use logicaffeine_kernel::Term;
1158    let mut ty = StandardLibrary::context().get_global(ctor)?.clone();
1159    while let Term::Pi { body_type, .. } = ty {
1160        ty = *body_type;
1161    }
1162    match ty {
1163        Term::Global(name) => Some(name),
1164        _ => None,
1165    }
1166}
1167
1168impl ProofState {
1169    /// Begin proving `goal` from `premises`, naming the hypotheses `hp0`, `hp1`, ….
1170    pub fn start(premises: Vec<ProofExpr>, goal: ProofExpr) -> Self {
1171        Self::start_with_names(premises, &[], goal)
1172    }
1173
1174    /// Begin proving `goal` from `premises`, using the given `names` for the
1175    /// hypotheses where present (parallel to `premises`), falling back to the
1176    /// positional `hp{i}` otherwise. Lets a surface `Given (h): …` name a premise so a
1177    /// `Proof:` script can say `cases h` instead of `cases hp0`.
1178    pub fn start_with_names(
1179        premises: Vec<ProofExpr>,
1180        names: &[Option<String>],
1181        goal: ProofExpr,
1182    ) -> Self {
1183        let hyps = premises
1184            .iter()
1185            .enumerate()
1186            .map(|(i, p)| {
1187                let name = names
1188                    .get(i)
1189                    .and_then(|n| n.as_ref())
1190                    .cloned()
1191                    .unwrap_or_else(|| format!("hp{i}"));
1192                direct_hyp(name, p.clone())
1193            })
1194            .collect();
1195        let root_goal = Goal {
1196            hyps,
1197            target: goal.clone(),
1198        };
1199        ProofState {
1200            premises,
1201            goal,
1202            nodes: vec![Node::Hole(root_goal)],
1203            root: 0,
1204            open: VecDeque::from([0]),
1205            fresh: 0,
1206        }
1207    }
1208
1209    /// A fresh entity-constant name for an `∃`-elimination witness. Uppercase-leading
1210    /// so the verifier reads it as a constant, not a variable.
1211    fn fresh_witness(&mut self) -> String {
1212        self.fresh += 1;
1213        format!("W{}", self.fresh)
1214    }
1215
1216    /// Replace the focused hole's goal in place (used by `cases` on `∧`, which
1217    /// enriches the hypotheses without splitting the goal).
1218    fn set_focused_goal(&mut self, goal: Goal) {
1219        if let Some(&idx) = self.open.front() {
1220            self.nodes[idx] = Node::Hole(goal);
1221        }
1222    }
1223
1224    /// The focused goal, or `None` if the proof is complete.
1225    pub fn focus(&self) -> Option<&Goal> {
1226        let idx = *self.open.front()?;
1227        match &self.nodes[idx] {
1228            Node::Hole(g) => Some(g),
1229            _ => None,
1230        }
1231    }
1232
1233    /// Number of still-open goals.
1234    pub fn open_goals(&self) -> usize {
1235        self.open.len()
1236    }
1237
1238    /// The focused goal's target, if any goal is open — the tactic-script and
1239    /// IDE surface for inspecting where a proof stands.
1240    pub fn focused_target(&self) -> Option<&ProofExpr> {
1241        self.focus().map(|g| &g.target)
1242    }
1243
1244    /// A [`crate::simp::SimpSet`] compiled from every in-scope hypothesis that
1245    /// orients as a rewrite rule — the default rule set for the script-level
1246    /// `simp` (a premise or cited lemma of rule shape is automatically a rule).
1247    pub fn scope_simp_set(&self) -> crate::simp::SimpSet {
1248        let mut set = crate::simp::SimpSet::new();
1249        if let Some(g) = self.focus() {
1250            for h in &g.hyps {
1251                set.register_lemma(&h.name, &h.prop);
1252            }
1253        }
1254        set
1255    }
1256
1257    /// A [`crate::simp::SimpSet`] combining the in-scope hypotheses with every `@[simp]`
1258    /// lemma REGISTERED in a kernel context — the script-level `simp` of a development whose
1259    /// attribute set is available.
1260    ///
1261    /// The scope set alone is a per-goal accident: a lemma is a rule because it happens to be
1262    /// a hypothesis here. `@[simp]` is the opposite — a declaration, made once, that says this
1263    /// equation is how the simplifier should normalise from now on. Both feed the same
1264    /// rewriter, which is the point: one notion of a rule, two ways to reach it.
1265    pub fn context_simp_set(&self, ctx: &logicaffeine_kernel::Context) -> crate::simp::SimpSet {
1266        let mut set = self.scope_simp_set();
1267        set.register_context_lemmas(ctx);
1268        set
1269    }
1270
1271    /// A [`crate::simp::SimpSet`] built from EXACTLY the named hypotheses — the rule set of
1272    /// Lean's `simp only [h₁, h₂]`.
1273    ///
1274    /// Selection is the whole point of `only`: the default set is every in-scope hypothesis
1275    /// that orients, so two `simp only` calls meant to stop at different normal forms
1276    /// collapse into one, and the collapse runs in the dangerous direction (MORE rules than
1277    /// the source asked for). An unknown name, or one that does not orient as a rewrite
1278    /// rule, is an error rather than a silently empty set.
1279    pub fn named_simp_set(&self, names: &[String]) -> Result<crate::simp::SimpSet, TacticError> {
1280        let g = self.focus().ok_or(TacticError::NoOpenGoals)?;
1281        let mut set = crate::simp::SimpSet::new();
1282        for name in names {
1283            let h = g
1284                .hyps
1285                .iter()
1286                .find(|h| &h.name == name)
1287                .ok_or_else(|| TacticError::NoSuchHypothesis(name.clone()))?;
1288            if !set.register_lemma(&h.name, &h.prop) {
1289                return Err(TacticError::DoesNotApply(format!(
1290                    "simp only [{name}]: `{name}` does not orient as a rewrite rule"
1291                )));
1292            }
1293        }
1294        Ok(set)
1295    }
1296
1297    fn focused_goal(&self) -> Result<Goal, TacticError> {
1298        self.focus().cloned().ok_or(TacticError::NoOpenGoals)
1299    }
1300
1301    /// Every NAME a goal is already committed to — hypothesis names, the variables the
1302    /// target and its scope mention (bound ones included), and the constants they name.
1303    /// A fresh eigen-constant must avoid all of them.
1304    fn scope_names(&self, g: &Goal) -> std::collections::BTreeSet<String> {
1305        let mut taken = std::collections::BTreeSet::new();
1306        let absorb = |e: &ProofExpr, taken: &mut std::collections::BTreeSet<String>| {
1307            all_vars(e, taken);
1308            constants_of(e, taken);
1309        };
1310        absorb(&g.target, &mut taken);
1311        for h in &g.hyps {
1312            taken.insert(h.name.clone());
1313            absorb(&h.prop, &mut taken);
1314        }
1315        taken
1316    }
1317
1318    /// The names free in the focused goal that stand for TERM VARIABLES rather than global
1319    /// constants — what an `intro`-bound `n` is, and what a witness spelled `n` must BE.
1320    fn scope_free_vars(&self) -> std::collections::BTreeSet<String> {
1321        let mut vars = std::collections::BTreeSet::new();
1322        if let Some(g) = self.focus() {
1323            free_vars(&g.target, &mut vars);
1324            for h in &g.hyps {
1325                free_vars(&h.prop, &mut vars);
1326            }
1327        }
1328        vars
1329    }
1330
1331    /// Replace the focused hole with a refinement node whose children are the given
1332    /// closed proofs / subgoals (in order). New subgoals are focused next, in order.
1333    fn refine(&mut self, conclusion: ProofExpr, rule: InferenceRule, children: Vec<Child>) {
1334        let idx = self.open.pop_front().expect("a focused goal");
1335        let mut child_indices = Vec::with_capacity(children.len());
1336        let mut new_holes = Vec::new();
1337        for child in children {
1338            let cidx = self.nodes.len();
1339            match child {
1340                Child::Closed(tree) => self.nodes.push(Node::Done(tree)),
1341                Child::Sub(goal) => {
1342                    self.nodes.push(Node::Hole(goal));
1343                    new_holes.push(cidx);
1344                }
1345            }
1346            child_indices.push(cidx);
1347        }
1348        // Focus the new subgoals next, first one at the front.
1349        for &h in new_holes.iter().rev() {
1350            self.open.push_front(h);
1351        }
1352        self.nodes[idx] = Node::Filled {
1353            conclusion,
1354            rule,
1355            children: child_indices,
1356        };
1357    }
1358
1359    /// Close the focused goal with an already-complete derivation.
1360    ///
1361    /// Every closer commits through here — `auto`'s engine tree, `crush`, the decision
1362    /// procedures, a hypothesis's proof — so this is where "prove it or decline it" is held:
1363    /// a derivation holding a node [`certifier::certify`](crate::certifier::certify) cannot
1364    /// build (an SMT oracle's verdict, a dead modal or temporal rule) is refused BEFORE the
1365    /// goal is consumed. The tactic declines with the offending rule and the reason, and the
1366    /// proof state is left exactly as it was, instead of reporting a success that `qed` would
1367    /// later refuse.
1368    fn close(&mut self, tree: DerivationTree) -> Result<(), TacticError> {
1369        if let Some((rule, why)) = tree.uncertifiable_rules().into_iter().next() {
1370            return Err(TacticError::DoesNotApply(format!(
1371                "the derivation for {} contains {rule}, which cannot be certified: {why}",
1372                tree.conclusion
1373            )));
1374        }
1375        let idx = self.open.pop_front().expect("a focused goal");
1376        self.nodes[idx] = Node::Done(tree);
1377        Ok(())
1378    }
1379
1380    // === Tactics ===
1381
1382    /// `intro name`: for a goal `P → Q`, assume `P` as hypothesis `name` and reduce
1383    /// to `Q`; for `∀x. φ(x)`, introduce the bound variable under `name` and reduce
1384    /// to `φ(name)`. Mirrors Lean's `intro`.
1385    pub fn intro(&mut self, name: &str) -> Result<&mut Self, TacticError> {
1386        let g = self.focused_goal()?;
1387        match &unfold_not(&g.target) {
1388            ProofExpr::Implies(p, q) => {
1389                let mut hyps = g.hyps.clone();
1390                hyps.push(direct_hyp(name.to_string(), (**p).clone()));
1391                let sub = Goal {
1392                    hyps,
1393                    target: (**q).clone(),
1394                };
1395                self.refine(
1396                    g.target.clone(),
1397                    InferenceRule::ImpliesIntro,
1398                    vec![Child::Sub(sub)],
1399                );
1400                Ok(self)
1401            }
1402            ProofExpr::ForAll { variable, body } => {
1403                // Introduce the bound variable under `name`. When `name` already IS the
1404                // binder, skip the rename — substituting `{z ↦ z}` would chase its own
1405                // chain forever in `apply_subst_to_term`. The eigenvariable soundness
1406                // worry of search does not apply here: the user constructs the proof,
1407                // they never *instantiate* the introduced variable.
1408                let (conclusion, renamed) = if name == variable {
1409                    (g.target.clone(), (**body).clone())
1410                } else {
1411                    let renamed =
1412                        instantiate_expr(body, variable, &ProofTerm::Variable(name.to_string()));
1413                    let conclusion = ProofExpr::ForAll {
1414                        variable: name.to_string(),
1415                        body: Box::new(renamed.clone()),
1416                    };
1417                    (conclusion, renamed)
1418                };
1419                let sub = Goal {
1420                    hyps: g.hyps.clone(),
1421                    target: renamed,
1422                };
1423                self.refine(
1424                    conclusion,
1425                    InferenceRule::UniversalIntro {
1426                        variable: name.to_string(),
1427                        var_type: "Entity".to_string(),
1428                    },
1429                    vec![Child::Sub(sub)],
1430                );
1431                Ok(self)
1432            }
1433            other => Err(TacticError::DoesNotApply(format!(
1434                "intro expects → or ∀, got {other:?}"
1435            ))),
1436        }
1437    }
1438
1439    /// `assumption`: close the goal with any hypothesis whose proposition is exactly
1440    /// the target, emitting THAT hypothesis's proof (a direct reference, or a
1441    /// `ConjunctionElim` projection for a conjunct extracted by `cases`).
1442    pub fn assumption(&mut self) -> Result<&mut Self, TacticError> {
1443        let g = self.focused_goal()?;
1444        let want = unfold_not(&g.target);
1445        if let Some(h) = g
1446            .hyps
1447            .iter()
1448            .find(|h| h.prop == g.target || unfold_not(&h.prop) == want)
1449        {
1450            let proof = h.proof.clone();
1451            self.close(proof)?;
1452            Ok(self)
1453        } else {
1454            Err(TacticError::NoSuchHypothesis(format!(
1455                "no hypothesis proves {:?}",
1456                g.target
1457            )))
1458        }
1459    }
1460
1461    /// `exact name`: close the goal with the specifically-named hypothesis, which
1462    /// must prove the target.
1463    pub fn exact(&mut self, name: &str) -> Result<&mut Self, TacticError> {
1464        let g = self.focused_goal()?;
1465        match g.hyps.iter().find(|h| h.name == name) {
1466            Some(h) if h.prop == g.target || unfold_not(&h.prop) == unfold_not(&g.target) => {
1467                let proof = h.proof.clone();
1468                self.close(proof)?;
1469                Ok(self)
1470            }
1471            Some(h) => Err(TacticError::DoesNotApply(format!(
1472                "hypothesis {name} : {:?} does not prove {:?}",
1473                h.prop, g.target
1474            ))),
1475            None => Err(TacticError::NoSuchHypothesis(name.to_string())),
1476        }
1477    }
1478
1479    /// `constructor` / `split`: for a goal `A ∧ B`, reduce to the two subgoals `A`
1480    /// and `B`.
1481    pub fn split(&mut self) -> Result<&mut Self, TacticError> {
1482        let g = self.focused_goal()?;
1483        match &g.target {
1484            ProofExpr::And(a, b) => {
1485                let ga = Goal {
1486                    hyps: g.hyps.clone(),
1487                    target: (**a).clone(),
1488                };
1489                let gb = Goal {
1490                    hyps: g.hyps.clone(),
1491                    target: (**b).clone(),
1492                };
1493                self.refine(
1494                    g.target.clone(),
1495                    InferenceRule::ConjunctionIntro,
1496                    vec![Child::Sub(ga), Child::Sub(gb)],
1497                );
1498                Ok(self)
1499            }
1500            // `A ↔ B` splits into its two implications. `InferenceRule::BicondIntro` and its
1501            // certifier arm (certifier.rs) have existed all along — no tactic ever CONSTRUCTED
1502            // one, so the rule was reachable only by hand-building a `DerivationTree`. Lean spells
1503            // this `constructor`, which is already one of `split`'s aliases.
1504            ProofExpr::Iff(a, b) => {
1505                let fwd = Goal {
1506                    hyps: g.hyps.clone(),
1507                    target: ProofExpr::Implies(a.clone(), b.clone()),
1508                };
1509                let bwd = Goal {
1510                    hyps: g.hyps.clone(),
1511                    target: ProofExpr::Implies(b.clone(), a.clone()),
1512                };
1513                self.refine(
1514                    g.target.clone(),
1515                    InferenceRule::BicondIntro,
1516                    vec![Child::Sub(fwd), Child::Sub(bwd)],
1517                );
1518                Ok(self)
1519            }
1520            other => Err(TacticError::DoesNotApply(format!(
1521                "split expects ∧ or ↔, got {other:?}"
1522            ))),
1523        }
1524    }
1525
1526    /// `left`: prove `A ∨ B` by proving `A`.
1527    pub fn left(&mut self) -> Result<&mut Self, TacticError> {
1528        self.disjunct(true)
1529    }
1530
1531    /// `right`: prove `A ∨ B` by proving `B`.
1532    pub fn right(&mut self) -> Result<&mut Self, TacticError> {
1533        self.disjunct(false)
1534    }
1535
1536    fn disjunct(&mut self, take_left: bool) -> Result<&mut Self, TacticError> {
1537        let g = self.focused_goal()?;
1538        match &g.target {
1539            ProofExpr::Or(a, b) => {
1540                let chosen = if take_left {
1541                    (**a).clone()
1542                } else {
1543                    (**b).clone()
1544                };
1545                let sub = Goal {
1546                    hyps: g.hyps.clone(),
1547                    target: chosen,
1548                };
1549                self.refine(
1550                    g.target.clone(),
1551                    InferenceRule::DisjunctionIntro,
1552                    vec![Child::Sub(sub)],
1553                );
1554                Ok(self)
1555            }
1556            other => Err(TacticError::DoesNotApply(format!(
1557                "left/right expects ∨, got {other:?}"
1558            ))),
1559        }
1560    }
1561
1562    /// `exists w`: prove `∃x. φ(x)` by exhibiting the witness `w` and reducing to
1563    /// `φ(w)`.
1564    ///
1565    /// The witness is an arbitrary TERM — `use (n + 1)`, `use (f x)` — which is what Lean's
1566    /// `exists`/`use` takes. A compound witness used to be REFUSED here, because
1567    /// `InferenceRule::ExistentialIntro` carries its witness as a `String` that the certifier
1568    /// resolves as one name: `add(n, 1)` certified to a global literally called
1569    /// `"add(n, 1)"`, which no context declares, so the kernel rejected the artefact at
1570    /// `qed` — a failure arriving so far from the mistake that it read as "the theorem is
1571    /// false". The rule now carries the term ([`InferenceRule::ExistentialIntroTerm`],
1572    /// exactly as `UniversalInstTerm` sits beside `UniversalInst` for the dual quantifier),
1573    /// so the honest answer is to take the step.
1574    ///
1575    /// A bare NAME still emits `ExistentialIntro`, which is not a fast path but a
1576    /// COMPATIBILITY one: producers and consumers of that rule (including the eigenconstant
1577    /// renaming in `engine::rewrite_tree_const_to_var`) match on its `String` witness.
1578    ///
1579    /// The ∃-binder's DOMAIN is computed, not assumed: `certifier::existential_domain` reads
1580    /// it off the body, and `proof_expr_to_type` builds the goal type with the same function,
1581    /// so an arithmetic existential is `Ex Int (λm:Int. …)` on both sides of the trust door.
1582    /// Stamping the FOL default `Entity` on `∃m. m = n + 1` produced `Eq Int m` with
1583    /// `m : Entity`, which is not well-typed at all.
1584    pub fn exists(&mut self, witness: ProofTerm) -> Result<&mut Self, TacticError> {
1585        if matches!(witness, ProofTerm::Group(_)) {
1586            return Err(TacticError::DoesNotApply(format!(
1587                "exists {witness}: a tuple is not one witness — supply the components with \
1588                 the anonymous constructor `exact (w, h)`, which nests the ∃-introductions"
1589            )));
1590        }
1591        let g = self.focused_goal()?;
1592        match &g.target {
1593            ProofExpr::Exists { variable, body } => {
1594                let instantiated = instantiate_expr(body, variable, &witness);
1595                let sub = Goal {
1596                    hyps: g.hyps.clone(),
1597                    target: instantiated,
1598                };
1599                let witness_type = crate::certifier::existential_domain(variable, body);
1600                let rule = witness_rule(&witness, witness_type);
1601                self.refine(g.target.clone(), rule, vec![Child::Sub(sub)]);
1602                Ok(self)
1603            }
1604            other => Err(TacticError::DoesNotApply(format!(
1605                "exists expects ∃, got {other:?}"
1606            ))),
1607        }
1608    }
1609
1610    /// `rfl`: close a goal `t = t` by reflexivity.
1611    ///
1612    /// The closer itself is not new — `simp` has always ended with it — but it had no name of its
1613    /// own, so a script could only reach reflexivity by asking for simplification and hoping. One
1614    /// closer, two names: `simp` now delegates here rather than carrying a second copy.
1615    pub fn rfl(&mut self) -> Result<&mut Self, TacticError> {
1616        let g = self.focused_goal()?;
1617        if let ProofExpr::Identity(l, r) = &g.target {
1618            if l == r {
1619                let target = g.target.clone();
1620                self.close(DerivationTree::leaf(target, InferenceRule::Reflexivity))?;
1621                return Ok(self);
1622            }
1623            return Err(TacticError::DoesNotApply(format!(
1624                "rfl: the two sides differ — {l:?} vs {r:?}"
1625            )));
1626        }
1627        Err(TacticError::DoesNotApply(format!(
1628            "rfl expects an equality goal, got {:?}",
1629            g.target
1630        )))
1631    }
1632
1633    // === Proof TERMS ===
1634
1635    /// `exact e`: close the goal with a proof TERM, not merely a hypothesis name.
1636    ///
1637    /// `exact (hpq hp)`, `exact (hp, hq)`, `exact h` where `h : ∀m. P m` against `P n` — all
1638    /// ordinary Lean, and all of them elaborate here against the goal. A term carrying a
1639    /// hole is refused: leaving goals open is [`refine`](Self::refine_term)'s job, and an
1640    /// `exact` that quietly did that would report a proof it had not finished.
1641    pub fn exact_term(&mut self, term: &PTerm) -> Result<&mut Self, TacticError> {
1642        self.build_from_term(term, false)
1643    }
1644
1645    /// `refine e`: elaborate a proof term against the goal, and leave one SUBGOAL per hole,
1646    /// in the order the holes appear.
1647    ///
1648    /// The holes are proof-state goals (`Node::Hole`), never kernel term holes: the kernel's
1649    /// `types_equal` matches `Term::Hole` against ANYTHING, so a term with a hole in it
1650    /// typechecks and the resulting certificate is indistinguishable from a real one. A hole
1651    /// that is the WHOLE term is refused — it leaves the goal exactly as it was, so it is a
1652    /// step that claims to have done something and has not.
1653    pub fn refine_term(&mut self, term: &PTerm) -> Result<&mut Self, TacticError> {
1654        self.build_from_term(term, true)
1655    }
1656
1657    /// `have h from e`: add `h`, proved by the term `e`, to the local scope.
1658    ///
1659    /// Nothing among the primitives introduced a hypothesis with an accompanying proof:
1660    /// `intro` takes one from the goal's antecedent, `cases` from an existing hypothesis's
1661    /// shape, and that was the complete set of ways a name entered a goal's scope. The
1662    /// hypothesis carries the elaborated derivation itself, so each USE emits that proof —
1663    /// no new rule, no lifted theorem, and a `have` whose statement mentions an
1664    /// `intro`-bound variable works like any other.
1665    pub fn have_term(&mut self, name: &str, term: &PTerm) -> Result<&mut Self, TacticError> {
1666        let g = self.focused_goal()?;
1667        let (prop, proof) = self.synthesize(term, &g.hyps)?;
1668        let mut hyps = g.hyps.clone();
1669        hyps.push(Hyp {
1670            name: name.to_string(),
1671            prop,
1672            proof,
1673        });
1674        self.set_focused_goal(Goal {
1675            hyps,
1676            target: g.target,
1677        });
1678        Ok(self)
1679    }
1680
1681    fn build_from_term(
1682        &mut self,
1683        term: &PTerm,
1684        allow_holes: bool,
1685    ) -> Result<&mut Self, TacticError> {
1686        let g = self.focused_goal()?;
1687        if allow_holes && matches!(term, PTerm::Hole) {
1688            return Err(TacticError::DoesNotApply(
1689                "refine: a bare hole leaves the goal exactly as it was".to_string(),
1690            ));
1691        }
1692        let (node, holes) = self.elaborate(term, &g.hyps, &g.target, allow_holes)?;
1693        let idx = self.open.pop_front().expect("a focused goal");
1694        self.nodes[idx] = node;
1695        for &h in holes.iter().rev() {
1696            self.open.push_front(h);
1697        }
1698        Ok(self)
1699    }
1700
1701    /// CHECK a proof term against an expected proposition, pushing its children into the
1702    /// node arena. Returns the root node (not yet placed) and the indices of the holes it
1703    /// spawned, in source order.
1704    fn elaborate(
1705        &mut self,
1706        term: &PTerm,
1707        hyps: &[Hyp],
1708        target: &ProofExpr,
1709        allow_holes: bool,
1710    ) -> Result<(Node, Vec<usize>), TacticError> {
1711        match term {
1712            PTerm::Hole => {
1713                if !allow_holes {
1714                    return Err(TacticError::DoesNotApply(
1715                        "a hole is only meaningful under `refine`".to_string(),
1716                    ));
1717                }
1718                Ok((
1719                    Node::Hole(Goal {
1720                        hyps: hyps.to_vec(),
1721                        target: target.clone(),
1722                    }),
1723                    Vec::new(),
1724                ))
1725            }
1726            // The anonymous constructor: which introduction rule it is comes from the
1727            // expected proposition, exactly as Lean's `⟨…⟩` does.
1728            PTerm::Tuple(items) => self.elaborate_anonymous(items, hyps, target, allow_holes),
1729            _ => {
1730                let (prop, tree) = self.synthesize(term, hyps)?;
1731                if prop == *target || unfold_not(&prop) == unfold_not(target) {
1732                    Ok((Node::Done(tree), Vec::new()))
1733                } else {
1734                    match instantiate_to(&prop, target, tree.clone()) {
1735                        Some(instantiated) => Ok((Node::Done(instantiated), Vec::new())),
1736                        None => Err(TacticError::DoesNotApply(format!(
1737                            "the term proves {prop:?}, which is not the goal {target:?}"
1738                        ))),
1739                    }
1740                }
1741            }
1742        }
1743    }
1744
1745    fn elaborate_anonymous(
1746        &mut self,
1747        items: &[PTerm],
1748        hyps: &[Hyp],
1749        target: &ProofExpr,
1750        allow_holes: bool,
1751    ) -> Result<(Node, Vec<usize>), TacticError> {
1752        if items.len() < 2 {
1753            return Err(TacticError::DoesNotApply(
1754                "an anonymous constructor needs at least two components".to_string(),
1755            ));
1756        }
1757        // `⟨a, b, c⟩` against a right-nested shape is `⟨a, ⟨b, c⟩⟩`.
1758        let (head, rest) = items.split_first().expect("at least two components");
1759        let tail = if rest.len() == 1 {
1760            rest[0].clone()
1761        } else {
1762            PTerm::Tuple(rest.to_vec())
1763        };
1764        let (rule, left, right) = match target {
1765            ProofExpr::And(a, b) => (
1766                InferenceRule::ConjunctionIntro,
1767                (**a).clone(),
1768                (**b).clone(),
1769            ),
1770            ProofExpr::Iff(a, b) => (
1771                InferenceRule::BicondIntro,
1772                ProofExpr::Implies(a.clone(), b.clone()),
1773                ProofExpr::Implies(b.clone(), a.clone()),
1774            ),
1775            // `⟨w, hw⟩` for an existential: the first component is the WITNESS TERM, not a
1776            // proof, so it elaborates through the value language.
1777            ProofExpr::Exists { variable, body } => {
1778                let witness = self.value_term(head)?;
1779                let instantiated = instantiate_expr(body, variable, &witness);
1780                let (child, holes) =
1781                    self.elaborate_child(&tail, hyps, &instantiated, allow_holes)?;
1782                let witness_type = crate::certifier::existential_domain(variable, body);
1783                let rule = witness_rule(&witness, witness_type);
1784                return Ok((
1785                    Node::Filled {
1786                        conclusion: target.clone(),
1787                        rule,
1788                        children: vec![child],
1789                    },
1790                    holes,
1791                ));
1792            }
1793            other => {
1794                return Err(TacticError::DoesNotApply(format!(
1795                    "an anonymous constructor expects ∧, ↔ or ∃, got {other:?}"
1796                )))
1797            }
1798        };
1799        let (left_idx, mut holes) = self.elaborate_child(head, hyps, &left, allow_holes)?;
1800        let (right_idx, right_holes) = self.elaborate_child(&tail, hyps, &right, allow_holes)?;
1801        holes.extend(right_holes);
1802        Ok((
1803            Node::Filled {
1804                conclusion: target.clone(),
1805                rule,
1806                children: vec![left_idx, right_idx],
1807            },
1808            holes,
1809        ))
1810    }
1811
1812    /// [`elaborate`](Self::elaborate) into a fresh arena slot, reporting its index.
1813    fn elaborate_child(
1814        &mut self,
1815        term: &PTerm,
1816        hyps: &[Hyp],
1817        target: &ProofExpr,
1818        allow_holes: bool,
1819    ) -> Result<(usize, Vec<usize>), TacticError> {
1820        let (node, holes) = self.elaborate(term, hyps, target, allow_holes)?;
1821        let is_hole = matches!(node, Node::Hole(_));
1822        let idx = self.nodes.len();
1823        self.nodes.push(node);
1824        Ok((idx, if is_hole { vec![idx] } else { holes }))
1825    }
1826
1827    /// SYNTHESIZE a proof term's proposition. Terms whose type is determined by the term
1828    /// itself — a name, or an application of one — go this way; the anonymous constructor
1829    /// and the hole do not, because only the expected proposition decides what they mean.
1830    fn synthesize(
1831        &mut self,
1832        term: &PTerm,
1833        hyps: &[Hyp],
1834    ) -> Result<(ProofExpr, DerivationTree), TacticError> {
1835        match term {
1836            PTerm::Ident(name) => hyps
1837                .iter()
1838                .find(|h| &h.name == name)
1839                .map(|h| (h.prop.clone(), h.proof.clone()))
1840                .ok_or_else(|| TacticError::NoSuchHypothesis(name.clone())),
1841            PTerm::App(head, args) => {
1842                let (mut prop, mut proof) = self.synthesize(head, hyps)?;
1843                for arg in args {
1844                    let (next_prop, next_proof) = match unfold_not(&prop) {
1845                        // A universal applied to a term is INSTANTIATION; an implication
1846                        // applied to a proof is modus ponens. The head's own shape decides.
1847                        ProofExpr::Implies(ant, con) => {
1848                            let (node, holes) = self.elaborate(arg, hyps, &ant, false)?;
1849                            debug_assert!(holes.is_empty(), "checked without holes");
1850                            let Node::Done(arg_proof) = node else {
1851                                return Err(TacticError::DoesNotApply(
1852                                    "an applied argument must be a complete proof".to_string(),
1853                                ));
1854                            };
1855                            (
1856                                (*con).clone(),
1857                                DerivationTree::new(
1858                                    (*con).clone(),
1859                                    InferenceRule::ModusPonens,
1860                                    vec![proof, arg_proof],
1861                                ),
1862                            )
1863                        }
1864                        ProofExpr::ForAll { .. } => {
1865                            let witness = self.value_term(arg)?;
1866                            let instantiated = instantiate_forall(&prop, &witness)
1867                                .expect("the proposition is universally quantified");
1868                            (
1869                                instantiated.clone(),
1870                                DerivationTree::new(
1871                                    instantiated,
1872                                    InferenceRule::UniversalInstTerm(witness),
1873                                    vec![proof],
1874                                ),
1875                            )
1876                        }
1877                        other => {
1878                            return Err(TacticError::DoesNotApply(format!(
1879                                "{other:?} is neither an implication nor a universal, so it \
1880                                 cannot be applied"
1881                            )))
1882                        }
1883                    };
1884                    prop = next_prop;
1885                    proof = next_proof;
1886                }
1887                Ok((prop, proof))
1888            }
1889            PTerm::Hole => Err(TacticError::DoesNotApply(
1890                "a hole's proposition cannot be inferred — it is only meaningful where the \
1891                 goal supplies one"
1892                    .to_string(),
1893            )),
1894            PTerm::Tuple(_) => Err(TacticError::DoesNotApply(
1895                "an anonymous constructor's proposition cannot be inferred — it is only \
1896                 meaningful against a known goal"
1897                    .to_string(),
1898            )),
1899            PTerm::Op(op, _, _) => Err(TacticError::DoesNotApply(format!(
1900                "`{op}` builds a VALUE, not a proof"
1901            ))),
1902        }
1903    }
1904
1905    /// Elaborate a script term as a VALUE — an `∃` witness, or the argument of a universal.
1906    ///
1907    /// A bare name is the `Variable` the surrounding proof bound if the goal's scope has one
1908    /// of that name, and a `Constant` otherwise. That distinction is invisible in every
1909    /// diagnostic a user sees (both `Display` as the bare name) and decides whether the
1910    /// instantiated goal matches its context at all, so it is READ OFF the scope rather than
1911    /// guessed: `intro n . exists n` must produce the `n` that `intro` bound.
1912    pub fn value_term(&self, term: &PTerm) -> Result<ProofTerm, TacticError> {
1913        let bound = self.scope_free_vars();
1914        value_of(term, &bound)
1915    }
1916
1917    /// `by_contra h`: assume the goal is FALSE under the name `h` and leave `⊥` to derive.
1918    ///
1919    /// Lean's `by_contra` is a STEP, and that is the whole point: a proof shaped
1920    /// `intro x; by_contra h; <twenty steps>` needs the twenty steps to be writable. The
1921    /// classical reductio itself is not new — `auto`'s search reaches it — but only as one
1922    /// opaque call with no way to help it along. Certified as `ClassicalReductio`, which
1923    /// discharges through the single classical axiom `dne`, so the axiom footprint of the
1924    /// theorem still records that it went classical.
1925    pub fn by_contra(&mut self, name: &str) -> Result<&mut Self, TacticError> {
1926        let g = self.focused_goal()?;
1927        if is_falsum_expr(&g.target) {
1928            return Err(TacticError::DoesNotApply(
1929                "by_contra: the goal is already ⊥, so there is nothing to negate".to_string(),
1930            ));
1931        }
1932        let mut hyps = g.hyps.clone();
1933        hyps.push(direct_hyp(
1934            name.to_string(),
1935            ProofExpr::Not(Box::new(g.target.clone())),
1936        ));
1937        let sub = Goal {
1938            hyps,
1939            target: ProofExpr::Atom(FALSUM.to_string()),
1940        };
1941        self.refine(
1942            g.target.clone(),
1943            InferenceRule::ClassicalReductio,
1944            vec![Child::Sub(sub)],
1945        );
1946        Ok(self)
1947    }
1948
1949    /// `ring`: close a polynomial identity over the commutative-ring vocabulary
1950    /// (`add`/`sub`/`mul` over literals and opaque atoms).
1951    ///
1952    /// The normaliser is not new — it is [`crate::arith::prove_int_eq`], the same
1953    /// proof-PRODUCING oracle `InferenceRule::ArithDecision` certifies through, whose
1954    /// trusted base is the seven registered ring axioms. What was missing was a name on the
1955    /// tactic-script surface: `ring` was reachable only from the literate kernel surface,
1956    /// and the three vernacular surfaces did not interoperate.
1957    ///
1958    /// The oracle is consulted HERE, not only at `qed`: its polynomial layer is a COMPLETE
1959    /// negative decision, so a goal that is not a formal ring identity is declined by the
1960    /// tactic rather than accepted and blown up at the trust door.
1961    pub fn ring(&mut self) -> Result<&mut Self, TacticError> {
1962        let g = self.focused_goal()?;
1963        let ProofExpr::Identity(l, r) = &g.target else {
1964            return Err(TacticError::DoesNotApply(format!(
1965                "ring expects an equality goal, got {:?}",
1966                g.target
1967            )));
1968        };
1969        if is_bool_valued(l) || is_bool_valued(r) {
1970            return Err(TacticError::DoesNotApply(format!(
1971                "ring proves a RING identity over `Int`; `{}` is a Bool fact — a ground one is                  `decide`'s and a symbolic one is `omega`'s",
1972                g.target
1973            )));
1974        }
1975        if !ring_identity_holds(l, r) {
1976            return Err(TacticError::DoesNotApply(
1977                "ring: the two sides are not the same polynomial".to_string(),
1978            ));
1979        }
1980        let target = g.target.clone();
1981        self.close(DerivationTree::leaf(target, InferenceRule::ArithDecision))?;
1982        Ok(self)
1983    }
1984
1985    /// `apply h`: look the rule up by hypothesis NAME, then reduce the goal by modus ponens.
1986    ///
1987    /// [`ProofState::apply`] takes the rule as a `ProofExpr`, which a proof script has no way to
1988    /// write — that is the whole reason `apply` was unreachable from script text despite working.
1989    /// This is the name-taking door, mirroring [`ProofState::exact`].
1990    pub fn apply_named(&mut self, name: &str) -> Result<&mut Self, TacticError> {
1991        let g = self.focused_goal()?;
1992        let rule = match g.hyps.iter().find(|h| h.name == name) {
1993            Some(h) => h.prop.clone(),
1994            None => return Err(TacticError::NoSuchHypothesis(name.to_string())),
1995        };
1996        self.apply(&rule)
1997    }
1998
1999    /// `apply rule`: `rule` is `P → Goal` (a hypothesis or premise). Reduce the goal
2000    /// to its antecedent `P` by modus ponens.
2001    pub fn apply(&mut self, rule: &ProofExpr) -> Result<&mut Self, TacticError> {
2002        let g = self.focused_goal()?;
2003        if let ProofExpr::Implies(ant, con) = rule {
2004            if unify_exprs(&g.target, con).is_ok() {
2005                let rule_leaf = DerivationTree::leaf(rule.clone(), InferenceRule::PremiseMatch);
2006                let sub = Goal {
2007                    hyps: g.hyps.clone(),
2008                    target: (**ant).clone(),
2009                };
2010                self.refine(
2011                    g.target.clone(),
2012                    InferenceRule::ModusPonens,
2013                    vec![Child::Closed(rule_leaf), Child::Sub(sub)],
2014                );
2015                return Ok(self);
2016            }
2017        }
2018        Err(TacticError::DoesNotApply(format!(
2019            "apply: {rule:?} is not an implication whose conclusion is the goal"
2020        )))
2021    }
2022
2023    /// `cases h` / `destruct h`: eliminate a hypothesis by its shape.
2024    /// - `A ∧ B`: add `h_1 : A` and `h_2 : B` to the goal, each backed by the
2025    ///   `ConjunctionElim` projection of `h` — so using a conjunct emits the
2026    ///   projection, never a dangling reference.
2027    /// - `A ∨ B`: split into two goals, one assuming `A`, one assuming `B`
2028    ///   (`DisjunctionCases`).
2029    /// - `∃x. φ`: introduce a fresh witness `c` and the hypothesis `φ(c)`
2030    ///   (`ExistentialElim`); the goal must not mention `c`, which holds since it is
2031    ///   fresh.
2032    pub fn cases(&mut self, name: &str) -> Result<&mut Self, TacticError> {
2033        self.cases_with(name, &[])
2034    }
2035
2036    /// `cases h with a b` / `obtain ⟨a, b⟩ := h`: [`cases`](Self::cases), with the components
2037    /// bound under the names the PROOF chose instead of the generated
2038    /// `h_1`/`h_2`/`h_l`/`h_r`/`h_w`.
2039    ///
2040    /// A Lean proof names what it destructures and every later step cites those names; a
2041    /// translator forced to renumber them is rewriting the proof. The arity is checked
2042    /// against the shape, because `cases h with hp` on a conjunction is a mistake about what
2043    /// `h` IS, not a shorthand.
2044    ///
2045    /// The ∃ branch takes `with w hw`: `w` names the fresh eigen-constant and `hw` the
2046    /// instantiated body. A chosen witness name is REFUSED when it is already in play in the
2047    /// goal or its scope — the eigenvariable condition is what makes ∃-elimination sound,
2048    /// and a name the surrounding proof already uses is not fresh.
2049    pub fn cases_with(&mut self, name: &str, names: &[String]) -> Result<&mut Self, TacticError> {
2050        let g = self.focused_goal()?;
2051        let hyp = g
2052            .hyps
2053            .iter()
2054            .find(|h| h.name == name)
2055            .cloned()
2056            .ok_or_else(|| TacticError::NoSuchHypothesis(name.to_string()))?;
2057        let want = |n: usize, shape: &str| -> Result<(), TacticError> {
2058            if names.is_empty() || names.len() == n {
2059                Ok(())
2060            } else {
2061                Err(TacticError::DoesNotApply(format!(
2062                    "cases {name} with …: {shape} binds {n} name(s), {} given",
2063                    names.len()
2064                )))
2065            }
2066        };
2067        let pick =
2068            |i: usize, fallback: String| -> String { names.get(i).cloned().unwrap_or(fallback) };
2069        match &hyp.prop {
2070            ProofExpr::And(a, b) => {
2071                want(2, "a conjunction")?;
2072                let proj_a = DerivationTree::new(
2073                    (**a).clone(),
2074                    InferenceRule::ConjunctionElim,
2075                    vec![hyp.proof.clone()],
2076                );
2077                let proj_b = DerivationTree::new(
2078                    (**b).clone(),
2079                    InferenceRule::ConjunctionElim,
2080                    vec![hyp.proof.clone()],
2081                );
2082                let mut hyps = g.hyps.clone();
2083                hyps.push(Hyp {
2084                    name: pick(0, format!("{name}_1")),
2085                    prop: (**a).clone(),
2086                    proof: proj_a,
2087                });
2088                hyps.push(Hyp {
2089                    name: pick(1, format!("{name}_2")),
2090                    prop: (**b).clone(),
2091                    proof: proj_b,
2092                });
2093                self.set_focused_goal(Goal {
2094                    hyps,
2095                    target: g.target.clone(),
2096                });
2097                Ok(self)
2098            }
2099            ProofExpr::Or(a, b) => {
2100                want(2, "a disjunction")?;
2101                let mut ha = g.hyps.clone();
2102                ha.push(direct_hyp(pick(0, format!("{name}_l")), (**a).clone()));
2103                let ga = Goal {
2104                    hyps: ha,
2105                    target: g.target.clone(),
2106                };
2107                let mut hb = g.hyps.clone();
2108                hb.push(direct_hyp(pick(1, format!("{name}_r")), (**b).clone()));
2109                let gb = Goal {
2110                    hyps: hb,
2111                    target: g.target.clone(),
2112                };
2113                self.refine(
2114                    g.target.clone(),
2115                    InferenceRule::DisjunctionCases,
2116                    vec![
2117                        Child::Closed(hyp.proof.clone()),
2118                        Child::Sub(ga),
2119                        Child::Sub(gb),
2120                    ],
2121                );
2122                Ok(self)
2123            }
2124            ProofExpr::Exists { variable, body } => {
2125                want(2, "an existential")?;
2126                let witness = match names.first() {
2127                    Some(chosen) => {
2128                        if self.scope_names(&g).contains(chosen) {
2129                            return Err(TacticError::DoesNotApply(format!(
2130                                "cases {name} with {chosen} …: `{chosen}` is already in scope, \
2131                                 so it is not a fresh witness"
2132                            )));
2133                        }
2134                        self.fresh += 1;
2135                        chosen.clone()
2136                    }
2137                    None => self.fresh_witness(),
2138                };
2139                let phi_c = instantiate_expr(body, variable, &ProofTerm::Constant(witness.clone()));
2140                let mut hyps = g.hyps.clone();
2141                hyps.push(direct_hyp(pick(1, format!("{name}_w")), phi_c));
2142                let gbody = Goal {
2143                    hyps,
2144                    target: g.target.clone(),
2145                };
2146                self.refine(
2147                    g.target.clone(),
2148                    InferenceRule::ExistentialElim { witness },
2149                    vec![Child::Closed(hyp.proof.clone()), Child::Sub(gbody)],
2150                );
2151                Ok(self)
2152            }
2153            other => Err(TacticError::DoesNotApply(format!(
2154                "cases expects ∧/∨/∃ hypothesis, got {other:?}"
2155            ))),
2156        }
2157    }
2158
2159    /// `induction`: structural induction on the goal's OUTERMOST `∀` binder.
2160    ///
2161    /// The scheme is READ OFF the scope rather than hard-wired: a hypothesis `P(C)` names a
2162    /// nullary constructor and a hypothesis `∀ā. (P(aᵢ) → …) → P(C ā)` names a constructor
2163    /// with induction hypotheses at the `aᵢ`, so a goal over a list whose ENil/ECons
2164    /// premises are in scope splits on ENil and ECons — where the hard-wired Peano scheme
2165    /// substituted `Zero`/`Succ k` into a list-valued position and produced syntactically
2166    /// well-formed nonsense that the automation would then happily "prove". Nat keeps the
2167    /// specialised path, whose `Fix`/`Match` certifies over the kernel's own `Nat` recursor;
2168    /// everything else routes to the dependent [`induction_over`](Self::induction_over).
2169    pub fn induction(&mut self) -> Result<&mut Self, TacticError> {
2170        let g = self.focused_goal()?;
2171        let (variable, body) = match &g.target {
2172            ProofExpr::ForAll { variable, body } => (variable.clone(), (**body).clone()),
2173            other => {
2174                return Err(TacticError::DoesNotApply(format!(
2175                    "induction expects a ∀ goal, got {other:?}"
2176                )))
2177            }
2178        };
2179        // A scheme recovered from the scope wins, unless it IS the Peano scheme — for which
2180        // the specialised Nat recursor below is the better certified object.
2181        if let Some((ind_type, ctors)) = infer_ctors(&variable, &body, &g.hyps) {
2182            if ind_type != "Nat" {
2183                return self.induction_over(&ind_type, ctors);
2184            }
2185        }
2186        self.fresh += 1;
2187        // Uppercase so the search treats the step variable as a rigid eigen-CONSTANT
2188        // (never a unifiable metavariable, which the backward chainer would either
2189        // ground to `Zero` or expand into an infinite `P(Succ^n k)` chain). It is
2190        // remapped back to a bound `Variable` when the proof is assembled (see
2191        // `assemble`), which is what the certifier's `Match` arm binds.
2192        let step_var = format!("K{}", self.fresh);
2193        let subst_to = |term: ProofTerm| instantiate_expr(&body, &variable, &term);
2194        let base_target = subst_to(ProofTerm::Constant("Zero".to_string()));
2195        let succ_k = ProofTerm::Function(
2196            "Succ".to_string(),
2197            vec![ProofTerm::Constant(step_var.clone())],
2198        );
2199        let step_target = subst_to(succ_k);
2200        let ih_prop = subst_to(ProofTerm::Constant(step_var.clone()));
2201
2202        let base_goal = Goal {
2203            hyps: g.hyps.clone(),
2204            target: base_target,
2205        };
2206        // Put the induction hypothesis FIRST so `auto`/`assumption` discharge the step's
2207        // recursive obligation `P(k)` against the IH (keeping `k` symbolic) rather than
2208        // against a base fact like `P(Zero)` (which would unsoundly ground `k := Zero`).
2209        let mut step_hyps = vec![direct_hyp("ih".to_string(), ih_prop)];
2210        step_hyps.extend(g.hyps.clone());
2211        let step_goal = Goal {
2212            hyps: step_hyps,
2213            target: step_target,
2214        };
2215
2216        self.refine(
2217            g.target.clone(),
2218            InferenceRule::StructuralInduction {
2219                variable,
2220                ind_type: "Nat".to_string(),
2221                step_var,
2222            },
2223            vec![Child::Sub(base_goal), Child::Sub(step_goal)],
2224        );
2225        Ok(self)
2226    }
2227
2228    /// `induction n`: structural induction on the NAMED variable, wherever it sits in the
2229    /// goal's `∀` prefix.
2230    ///
2231    /// The argumentless [`induction`](Self::induction) takes whatever binder happens to be
2232    /// outermost, so against `∀m n. Q m n` it and Lean's `induction n` prove DIFFERENT
2233    /// theorems — both certified, and nothing downstream can tell. Naming the variable is
2234    /// how a translator says which one it meant.
2235    ///
2236    /// For an inner variable the goal is first GENERALIZED: `∀ō. ∀v. body` is proved from
2237    /// `∀v. ∀ō. body` — the motive `λv. ∀ō. body`, which is the strengthened induction
2238    /// hypothesis a proof by induction on an inner variable needs. The bridge between the
2239    /// two orders is built from `UniversalIntro` and `UniversalInst` alone (introduce the
2240    /// prefix, then instantiate the reordered theorem at the introduced variables), so it
2241    /// certifies through rules that already existed — no new axiom, no new rule.
2242    ///
2243    /// When the prefix does not bind `v` at all the tactic does NOT refuse: it takes Lean's
2244    /// reading and generalizes — see `induction_generalizing`.
2245    pub fn induction_on(&mut self, variable: &str) -> Result<&mut Self, TacticError> {
2246        let g = self.focused_goal()?;
2247        let (prefix, _) = peel_foralls(&g.target);
2248        let Some(position) = prefix.iter().position(|v| v == variable) else {
2249            return self.induction_generalizing(variable);
2250        };
2251        if position == 0 {
2252            return self.induction();
2253        }
2254        // The reordered statement `∀v. ∀ō. body`, and the bridge down to the body.
2255        let outer: Vec<String> = prefix[..position].to_vec();
2256        let reordered = reorder_forall_prefix(&g.target, variable).ok_or_else(|| {
2257            TacticError::DoesNotApply(format!(
2258                "induction {variable}: the goal's ∀ prefix could not be reordered"
2259            ))
2260        })?;
2261
2262        // The induction variable's DOMAIN: the structural-induction node below types its
2263        // binder as the inductive, so the λ that binds `v` above must agree or the
2264        // application the bridge builds does not typecheck.
2265        let reordered_body = match &reordered {
2266            ProofExpr::ForAll { body, .. } => (**body).clone(),
2267            _ => unreachable!("reorder_forall_prefix returns a universal"),
2268        };
2269        let ind_type = infer_ctors(variable, &reordered_body, &g.hyps)
2270            .map(|(t, _)| t)
2271            .unwrap_or_else(|| "Nat".to_string());
2272
2273        // Downward: introduce ō, then v at the inductive's domain, landing on the bare body.
2274        for name in &outer {
2275            self.intro(name)?;
2276        }
2277        let focused = self.focused_goal()?;
2278        let ProofExpr::ForAll { body, .. } = &focused.target else {
2279            return Err(TacticError::DoesNotApply(format!(
2280                "induction {variable}: the prefix did not strip down to the binder"
2281            )));
2282        };
2283        let sub = Goal {
2284            hyps: focused.hyps.clone(),
2285            target: (**body).clone(),
2286        };
2287        self.refine(
2288            focused.target.clone(),
2289            InferenceRule::UniversalIntro {
2290                variable: variable.to_string(),
2291                var_type: ind_type,
2292            },
2293            vec![Child::Sub(sub)],
2294        );
2295        // Upward: the body follows from the reordered theorem instantiated at v, then at
2296        // each ō in turn. `witnesses[i]` justifies `conclusions[i]` from `conclusions[i-1]`,
2297        // with the reordered theorem itself below the bottom of the chain.
2298        let witnesses: Vec<String> = std::iter::once(variable.to_string())
2299            .chain(outer.iter().cloned())
2300            .collect();
2301        let mut conclusions = Vec::with_capacity(witnesses.len());
2302        let mut concl = reordered.clone();
2303        for name in &witnesses {
2304            concl = instantiate_forall(&concl, &ProofTerm::Variable(name.clone())).ok_or_else(
2305                || {
2306                    TacticError::DoesNotApply(
2307                        "induction: the reordered goal lost a binder".to_string(),
2308                    )
2309                },
2310            )?;
2311            conclusions.push(concl.clone());
2312        }
2313        // The derivation nests the other way round: the focused hole IS the last
2314        // conclusion, and each refinement exposes the one below it.
2315        let hyps = self.focused_goal()?.hyps;
2316        for i in (0..witnesses.len()).rev() {
2317            let below = if i == 0 {
2318                reordered.clone()
2319            } else {
2320                conclusions[i - 1].clone()
2321            };
2322            self.refine(
2323                conclusions[i].clone(),
2324                InferenceRule::UniversalInst(witnesses[i].clone()),
2325                vec![Child::Sub(Goal {
2326                    hyps: hyps.clone(),
2327                    target: below,
2328                })],
2329            );
2330        }
2331        self.induction()
2332    }
2333
2334    /// `induction n` where the goal's `∀` prefix does not bind `n`.
2335    ///
2336    /// Three readings are possible and they are told apart by what `n` can be TALKING about —
2337    /// which is the same question Lean answers with its local context, and all an untyped
2338    /// `ProofExpr` can answer without one:
2339    ///
2340    /// * **`n` is a free local** of the goal or of a hypothesis. This is Lean's `induction n` on
2341    ///   a local: REVERT every hypothesis that mentions `n`, generalize the goal over `n`, apply
2342    ///   the eliminator, and re-introduce what was reverted in each branch.
2343    /// * **`n` is nothing at all, and the goal QUANTIFIES.** Then a binder was plainly meant and
2344    ///   this one is not it; taking a different binder is how two theorems get proved under one
2345    ///   name, so this REFUSES and says which binders exist.
2346    /// * **`n` is nothing at all, and the goal does not quantify.** There is no binder that could
2347    ///   have been meant, and the generalization is vacuous: `n ∉ FV(G)`, so `∀n:T. G ⊢ G` needs
2348    ///   only an inhabitant of `T`. This is the case our own `ProofStrategy::Induction` doc
2349    ///   comment teaches verbatim (`Proof: Induction on n.` against `Given: Bob is happy. Prove:
2350    ///   Bob is happy.`), and refusing it left the documentation teaching a spelling that does
2351    ///   not work — worse than an undocumented gap, because a producer copies it.
2352    ///
2353    /// Nothing new is assumed anywhere in this. The reverted hypotheses come back by one
2354    /// `ModusPonens` against the leaf each already carried, and the generalization descends by
2355    /// `UniversalInstTerm` — at `n` itself when `n` is a local, and at the inductive's closed
2356    /// base point when it is vacuous.
2357    ///
2358    /// The revert is not bookkeeping. A hypothesis stated about the LOCAL `n` left in scope would
2359    /// sit under the eliminator's own `λn`, which SHADOWS that local: the branch would be reading
2360    /// a hypothesis about a different `n` than the one it was stated about.
2361    ///
2362    /// The two live cases differ in what they must KNOW. A vacuous generalization binds a variable
2363    /// the motive never mentions, so any inhabited inductive serves and `Nat` is taken. A
2364    /// generalization over a local COMMITS the eliminator to that local's domain, and `ProofExpr`
2365    /// carries no types — so the domain has to come from the scope, via the induction principle
2366    /// stated as premises ([`infer_ctors`]). When the scope does not say, this refuses rather than
2367    /// guess `Nat`: the guess would build a tree naming a domain nothing supports, and a tactic
2368    /// that returns `Ok` with an object the kernel must refuse is a claim, not a tactic.
2369    fn induction_generalizing(&mut self, variable: &str) -> Result<&mut Self, TacticError> {
2370        let g = self.focused_goal()?;
2371        let mentions = |e: &ProofExpr| {
2372            let mut fv = std::collections::BTreeSet::new();
2373            free_vars(e, &mut fv);
2374            fv.contains(variable)
2375        };
2376        let (reverted, kept): (Vec<Hyp>, Vec<Hyp>) =
2377            g.hyps.iter().cloned().partition(|h| mentions(&h.prop));
2378        let is_local = mentions(&g.target) || !reverted.is_empty();
2379        if !is_local {
2380            let (prefix, _) = peel_foralls(&g.target);
2381            if !prefix.is_empty() {
2382                return Err(TacticError::DoesNotApply(format!(
2383                    "induction {variable}: the goal's ∀ prefix binds {prefix:?}, not `{variable}` \
2384                     — a goal that quantifies has a binder this tactic was meant for, and taking \
2385                     a different one proves a different theorem under the same name"
2386                )));
2387            }
2388        }
2389        // The scheme is read off the ORIGINAL goal: the reverted form below is an implication,
2390        // and a constructor case stated as a premise matches the goal's shape, not that one.
2391        let scheme = infer_ctors(variable, &g.target, &g.hyps);
2392        let ind_type = match (&scheme, is_local) {
2393            (Some((t, _)), _) => t.clone(),
2394            (None, false) => "Nat".to_string(),
2395            (None, true) => {
2396                return Err(TacticError::DoesNotApply(format!(
2397                    "induction {variable}: `{variable}` is a free local, not a bound variable, \
2398                     and nothing in scope says what it ranges over — state the induction \
2399                     principle for its type as premises (`P(C)` and `∀ā. P(aᵢ) → P(C ā)`) and \
2400                     the domain is read off them"
2401                )));
2402            }
2403        };
2404
2405        // REVERT: `Γ, r̄ ⊢ G` becomes `Γ ⊢ r̄ → G`.
2406        let mut reverted_target = g.target.clone();
2407        for h in reverted.iter().rev() {
2408            reverted_target =
2409                ProofExpr::Implies(Box::new(h.prop.clone()), Box::new(reverted_target));
2410        }
2411        let generalized = ProofExpr::ForAll {
2412            variable: variable.to_string(),
2413            body: Box::new(reverted_target.clone()),
2414        };
2415        // Where to land back on the original goal. A local is instantiated at ITSELF; a vacuous
2416        // variable at the inductive's closed base point.
2417        let witness = if is_local {
2418            ProofTerm::Variable(variable.to_string())
2419        } else {
2420            let base = nullary_constructor(&ind_type).ok_or_else(|| {
2421                TacticError::DoesNotApply(format!(
2422                    "induction {variable}: `{variable}` occurs nowhere in the goal, and \
2423                     `{ind_type}` has no nullary constructor to instantiate the generalization \
2424                     back down at"
2425                ))
2426            })?;
2427            ProofTerm::Constant(base)
2428        };
2429
2430        // Downward, innermost first: the focused hole is `G`, discharged by one `ModusPonens`
2431        // per reverted hypothesis (the implication is the SUBGOAL, the hypothesis is the leaf it
2432        // already carried), and the last of those holes is `r̄ → G`, discharged by instantiating
2433        // the generalization.
2434        let mut concl = g.target.clone();
2435        for h in reverted.iter().rev() {
2436            let imp = ProofExpr::Implies(Box::new(h.prop.clone()), Box::new(concl.clone()));
2437            self.refine(
2438                concl,
2439                InferenceRule::ModusPonens,
2440                vec![
2441                    Child::Sub(Goal {
2442                        hyps: kept.clone(),
2443                        target: imp.clone(),
2444                    }),
2445                    Child::Closed(h.proof.clone()),
2446                ],
2447            );
2448            concl = imp;
2449        }
2450        self.refine(
2451            concl,
2452            InferenceRule::UniversalInstTerm(witness),
2453            vec![Child::Sub(Goal {
2454                hyps: kept.clone(),
2455                target: generalized,
2456            })],
2457        );
2458
2459        // The eliminator. `induction` re-reads the scheme from the goal it is handed, and the
2460        // reverted goal no longer has the shape a premise-stated constructor case matches, so a
2461        // non-Nat scheme is dispatched here from what was read off the original.
2462        let before: std::collections::BTreeSet<usize> = self.open.iter().copied().collect();
2463        match scheme {
2464            Some((t, ctors)) if t != "Nat" => self.induction_over(&t, ctors)?,
2465            _ => self.induction()?,
2466        };
2467
2468        // …then every branch it produced gets its reverted hypotheses back, under their
2469        // ORIGINAL names, so a script written before the revert still reads.
2470        if reverted.is_empty() {
2471            return Ok(self);
2472        }
2473        let produced: VecDeque<usize> = self.open.clone();
2474        let mut new_open = VecDeque::new();
2475        for idx in produced {
2476            if before.contains(&idx) {
2477                new_open.push_back(idx);
2478                continue;
2479            }
2480            self.open = VecDeque::from([idx]);
2481            for h in &reverted {
2482                self.intro(&h.name)?;
2483            }
2484            new_open.extend(self.open.iter().copied());
2485        }
2486        self.open = new_open;
2487        Ok(self)
2488    }
2489
2490    /// `induction_over`: generic structural induction over ANY inductive `ind_type`,
2491    /// one subgoal per constructor. On a goal `∀x. P(x)`, each constructor `C a₀…aₙ`
2492    /// yields the subgoal `P(C a₀ … aₙ)`; every recursive argument `aᵢ` (one of the
2493    /// inductive type) contributes an induction hypothesis `P(aᵢ)`, placed FIRST so
2494    /// `auto`/`assumption` discharge the recursive obligation against the IH rather
2495    /// than a base fact. Generalizes [`induction`](Self::induction) (fixed to the
2496    /// nullary-base + unary-step Nat shape) to constructors with several — or zero —
2497    /// recursive positions (`Nil`/`Cons`, `Leaf`/`Node`, an N-way enum). Assembled as
2498    /// the dependent `InductionScheme` eliminator (`fix rec. λx. match x { … }`), which
2499    /// the kernel re-checks for coverage, case types, and termination.
2500    ///
2501    /// The constructor arguments run the search as rigid eigen-CONSTANTS (so the
2502    /// backward chainer neither grounds nor unrolls them); `assemble`
2503    /// remaps each back to the bound `Variable` the certifier's `match` arm binds.
2504    pub fn induction_over(
2505        &mut self,
2506        ind_type: &str,
2507        ctors: Vec<CtorSpec>,
2508    ) -> Result<&mut Self, TacticError> {
2509        let g = self.focused_goal()?;
2510        let (variable, body) = match &g.target {
2511            ProofExpr::ForAll { variable, body } => (variable.clone(), (**body).clone()),
2512            other => {
2513                return Err(TacticError::DoesNotApply(format!(
2514                    "induction expects a ∀ goal, got {other:?}"
2515                )))
2516            }
2517        };
2518        let subst_to = |term: ProofTerm| instantiate_expr(&body, &variable, &term);
2519
2520        let mut cases = Vec::with_capacity(ctors.len());
2521        let mut children = Vec::with_capacity(ctors.len());
2522        for ctor in &ctors {
2523            // A fresh rigid eigenconstant per constructor argument.
2524            let arg_names: Vec<String> = ctor
2525                .recursive
2526                .iter()
2527                .map(|_| {
2528                    self.fresh += 1;
2529                    format!("K{}", self.fresh)
2530                })
2531                .collect();
2532
2533            // The constructor applied to its eigenconstant arguments — `C` (a bare
2534            // `Constant`) when nullary, else `C(a₀, …, aₙ)`.
2535            let ctor_term = if arg_names.is_empty() {
2536                ProofTerm::Constant(ctor.constructor.clone())
2537            } else {
2538                ProofTerm::Function(
2539                    ctor.constructor.clone(),
2540                    arg_names
2541                        .iter()
2542                        .map(|n| ProofTerm::Constant(n.clone()))
2543                        .collect(),
2544                )
2545            };
2546            let case_target = subst_to(ctor_term);
2547
2548            // IHs for the recursive arguments, FIRST (see the Nat induction rationale).
2549            let mut hyps = Vec::new();
2550            for (arg, &is_rec) in arg_names.iter().zip(ctor.recursive.iter()) {
2551                if is_rec {
2552                    let ih_prop = subst_to(ProofTerm::Constant(arg.clone()));
2553                    hyps.push(direct_hyp(format!("ih_{arg}"), ih_prop));
2554                }
2555            }
2556            hyps.extend(g.hyps.clone());
2557            children.push(Child::Sub(Goal {
2558                hyps,
2559                target: case_target,
2560            }));
2561
2562            cases.push(InductionCase {
2563                constructor: ctor.constructor.clone(),
2564                args: arg_names
2565                    .iter()
2566                    .zip(ctor.recursive.iter())
2567                    .map(|(name, &recursive)| InductionArg {
2568                        name: name.clone(),
2569                        recursive,
2570                    })
2571                    .collect(),
2572            });
2573        }
2574
2575        self.refine(
2576            g.target.clone(),
2577            InferenceRule::InductionScheme {
2578                variable,
2579                ind_type: ind_type.to_string(),
2580                cases,
2581            },
2582            children,
2583        );
2584        Ok(self)
2585    }
2586
2587    /// `rewrite h`: rewrite the goal left-to-right by the equation `h`.
2588    ///
2589    /// `h` may be GROUND (`lhs = rhs`) or ∀-QUANTIFIED (`∀x̄. lhs = rhs`), which is the
2590    /// commonest kind in real mathematics and had no image at all before. A quantified
2591    /// equation is instantiated the way Lean's `rw` instantiates it: the first (outermost,
2592    /// leftmost) subterm of the goal that matches `lhs` fixes the pattern variables, and the
2593    /// rewrite then replaces that INSTANTIATED left-hand side — so `∀x. f x = g x` against
2594    /// `f 1 = g 1 ∧ f 2 = g 2` touches the `f 1` and leaves the `f 2` alone.
2595    ///
2596    /// Substitution is capture-avoiding (`substitute_in_expr`), so an occurrence the goal
2597    /// BINDS is not an occurrence of the pattern and a replacement mentioning a free
2598    /// variable is not captured by a binder that happens to share its spelling.
2599    ///
2600    /// Certified by `Eq_rec` (Leibniz): the node concludes the original goal, its equality
2601    /// premise proves `rhs = lhs` (the ∀-instantiation chain over `h`, then symmetry), and
2602    /// its source premise is the rewritten subgoal. Fails if the pattern does not occur.
2603    ///
2604    /// ONE occurrence — the first. `rw` used to rewrite every structural match, so a goal
2605    /// `P(a, a)` with `h : a = b` could only become `P(b, b)`, and the frequently-provable
2606    /// `P(b, a)` was unreachable from any surface: `InferenceRule::Rewrite` carried no
2607    /// position either, so even a Rust caller had nowhere to say which one it meant. Use
2608    /// [`ProofState::rewrite_at`] to name another occurrence; `repeat (rewrite h)` recovers
2609    /// the all-occurrences sweep, one certified step per occurrence.
2610    pub fn rewrite(&mut self, name: &str) -> Result<&mut Self, TacticError> {
2611        self.rewrite_at(name, 0)
2612    }
2613
2614    /// `rewrite h at k`: [`ProofState::rewrite`] aimed at the `k`-th (0-based) FREE
2615    /// occurrence of the equation's left-hand side, counted left to right. Lean's `conv`
2616    /// and its occurrence arguments exist for exactly this, and the occurrence travels all
2617    /// the way to the trust door as `InferenceRule::RewriteAt` — the `Eq_rec` motive
2618    /// abstracts that one position, so the kernel re-checks the choice rather than taking
2619    /// the tactic's word for it.
2620    pub fn rewrite_at(&mut self, name: &str, occurrence: usize) -> Result<&mut Self, TacticError> {
2621        let g = self.focused_goal()?;
2622        let hyp = g
2623            .hyps
2624            .iter()
2625            .find(|h| h.name == name)
2626            .cloned()
2627            .ok_or_else(|| TacticError::NoSuchHypothesis(name.to_string()))?;
2628        let (pattern_vars, equation) = peel_foralls(&hyp.prop);
2629        let (lhs, rhs) = match equation {
2630            ProofExpr::Identity(l, r) => (l, r),
2631            other => {
2632                return Err(TacticError::DoesNotApply(format!(
2633                    "rewrite expects an equality hypothesis, got {other:?}"
2634                )))
2635            }
2636        };
2637
2638        // Instantiate a quantified equation at its first match in the goal.
2639        let mut instantiation = Vec::new();
2640        let (lhs, rhs) = if pattern_vars.is_empty() {
2641            (lhs, rhs)
2642        } else {
2643            let subst = first_match_in_expr(&g.target, &lhs, &pattern_vars).ok_or_else(|| {
2644                TacticError::DoesNotApply(format!("rewrite: no subterm of the goal matches {lhs}"))
2645            })?;
2646            for v in &pattern_vars {
2647                match subst.get(v) {
2648                    Some(t) => instantiation.push(t.clone()),
2649                    // A variable the left-hand side never mentions is undetermined, so the
2650                    // instantiated right-hand side would carry a free metavariable.
2651                    None => {
2652                        return Err(TacticError::DoesNotApply(format!(
2653                            "rewrite: the match does not determine `{v}`"
2654                        )))
2655                    }
2656                }
2657            }
2658            (
2659                apply_subst_to_term(&lhs, &subst),
2660                apply_subst_to_term(&rhs, &subst),
2661            )
2662        };
2663
2664        let (subgoal_target, occurrences) =
2665            substitute_occurrence_in_expr(&g.target, &lhs, &rhs, occurrence);
2666        if occurrences == 0 {
2667            return Err(TacticError::DoesNotApply(format!(
2668                "rewrite: {lhs} does not occur FREE in the goal"
2669            )));
2670        }
2671        if occurrence >= occurrences {
2672            return Err(TacticError::DoesNotApply(format!(
2673                "rewrite: the goal has {occurrences} free occurrence(s) of {lhs}, so there is \
2674                 no occurrence {occurrence}"
2675            )));
2676        }
2677        if subgoal_target == g.target {
2678            return Err(TacticError::DoesNotApply(format!(
2679                "rewrite: replacing occurrence {occurrence} of {lhs} by {rhs} leaves the goal \
2680                 unchanged, so the step proves nothing"
2681            )));
2682        }
2683
2684        // The equality premise: instantiate the rule at the matched terms, then symmetrise —
2685        // the premise must conclude `rhs = lhs`.
2686        let mut eq_proof = hyp.proof.clone();
2687        let mut concl = hyp.prop.clone();
2688        for witness in instantiation {
2689            concl = instantiate_forall(&concl, &witness).ok_or_else(|| {
2690                TacticError::DoesNotApply(
2691                    "rewrite: the equation has fewer binders than the match".to_string(),
2692                )
2693            })?;
2694            eq_proof = DerivationTree::new(
2695                concl.clone(),
2696                InferenceRule::UniversalInstTerm(witness),
2697                vec![eq_proof],
2698            );
2699        }
2700        let eq_sym = DerivationTree::new(
2701            ProofExpr::Identity(rhs.clone(), lhs.clone()),
2702            InferenceRule::EqualitySymmetry,
2703            vec![eq_proof],
2704        );
2705        let sub = Goal {
2706            hyps: g.hyps.clone(),
2707            target: subgoal_target,
2708        };
2709        self.refine(
2710            g.target.clone(),
2711            InferenceRule::RewriteAt {
2712                from: rhs,
2713                to: lhs,
2714                occurrence,
2715            },
2716            vec![Child::Closed(eq_sym), Child::Sub(sub)],
2717        );
2718        Ok(self)
2719    }
2720
2721    /// `rewrite h at hp`: rewrite the HYPOTHESIS `hp` with the equation `h` — Lean's
2722    /// `rw [h] at hp`, and the LOCATION half of positional rewriting.
2723    ///
2724    /// [`ProofState::rewrite_at`] reads and writes the GOAL only, so a Lean proof that
2725    /// normalises a hypothesis before using it had no image at all. The corpus case for `conv`
2726    /// makes the point sharply: positional rewriting has two aspects, the POSITION and the
2727    /// LOCATION, and "a translator that fixes only one of them has fixed nothing".
2728    ///
2729    /// The step runs FORWARD, where the goal rewrite runs backward: the hypothesis's own
2730    /// derivation is the SOURCE premise and the rewritten proposition is the conclusion, so the
2731    /// goal is untouched and only the context moves. Nothing is ASSUMED — the new hypothesis
2732    /// carries a complete `Eq_rec` derivation built from the old one, which `assumption` and
2733    /// `exact` splice in and which `qed` re-checks like any other step. That is why no
2734    /// refinement node is needed: a hypothesis in this proof state is a proposition WITH its
2735    /// proof, and this replaces both at once.
2736    ///
2737    /// The motive's position is CHOSEN by `crate::engine::leibniz_step` rather than taken
2738    /// from the caller's index: the tactic layer counts occurrences in a `ProofExpr` and the
2739    /// kernel counts them in a `Term`, the two agree on the leftmost and can differ deeper, and
2740    /// the kernel is the one that decides.
2741    pub fn rewrite_hyp_at(
2742        &mut self,
2743        eq_name: &str,
2744        hyp_name: &str,
2745        occurrence: usize,
2746    ) -> Result<&mut Self, TacticError> {
2747        let g = self.focused_goal()?;
2748        if eq_name == hyp_name {
2749            return Err(TacticError::DoesNotApply(format!(
2750                "rewrite {eq_name} at {hyp_name}: an equation cannot rewrite itself"
2751            )));
2752        }
2753        let eq_hyp = g
2754            .hyps
2755            .iter()
2756            .find(|h| h.name == eq_name)
2757            .cloned()
2758            .ok_or_else(|| TacticError::NoSuchHypothesis(eq_name.to_string()))?;
2759        let target_hyp = g
2760            .hyps
2761            .iter()
2762            .find(|h| h.name == hyp_name)
2763            .cloned()
2764            .ok_or_else(|| TacticError::NoSuchHypothesis(hyp_name.to_string()))?;
2765        let (pattern_vars, equation) = peel_foralls(&eq_hyp.prop);
2766        let ProofExpr::Identity(lhs, rhs) = equation else {
2767            return Err(TacticError::DoesNotApply(format!(
2768                "rewrite expects an equality hypothesis, got {:?}",
2769                eq_hyp.prop
2770            )));
2771        };
2772
2773        // Instantiate a quantified equation at its first match IN THE HYPOTHESIS — the
2774        // location decides where the pattern is looked for, not just where it is replaced.
2775        let mut instantiation = Vec::new();
2776        let (lhs, rhs) = if pattern_vars.is_empty() {
2777            (lhs, rhs)
2778        } else {
2779            let subst =
2780                first_match_in_expr(&target_hyp.prop, &lhs, &pattern_vars).ok_or_else(|| {
2781                    TacticError::DoesNotApply(format!(
2782                        "rewrite: no subterm of `{hyp_name}` matches {lhs}"
2783                    ))
2784                })?;
2785            for v in &pattern_vars {
2786                match subst.get(v) {
2787                    Some(t) => instantiation.push(t.clone()),
2788                    None => {
2789                        return Err(TacticError::DoesNotApply(format!(
2790                            "rewrite: the match does not determine `{v}`"
2791                        )))
2792                    }
2793                }
2794            }
2795            (
2796                apply_subst_to_term(&lhs, &subst),
2797                apply_subst_to_term(&rhs, &subst),
2798            )
2799        };
2800
2801        let (new_prop, occurrences) =
2802            substitute_occurrence_in_expr(&target_hyp.prop, &lhs, &rhs, occurrence);
2803        if occurrences == 0 {
2804            return Err(TacticError::DoesNotApply(format!(
2805                "rewrite: {lhs} does not occur FREE in `{hyp_name}`"
2806            )));
2807        }
2808        if occurrence >= occurrences {
2809            return Err(TacticError::DoesNotApply(format!(
2810                "rewrite: `{hyp_name}` has {occurrences} free occurrence(s) of {lhs}, so there \
2811                 is no occurrence {occurrence}"
2812            )));
2813        }
2814        if new_prop == target_hyp.prop {
2815            return Err(TacticError::DoesNotApply(format!(
2816                "rewrite: replacing occurrence {occurrence} of {lhs} by {rhs} leaves \
2817                 `{hyp_name}` unchanged, so the step proves nothing"
2818            )));
2819        }
2820
2821        // The equality premise, instantiated at the match. FORWARD, so — unlike the goal
2822        // rewrite — it is NOT symmetrised: the hypothesis travels from `lhs` to `rhs`.
2823        let mut eq_proof = eq_hyp.proof.clone();
2824        let mut concl = eq_hyp.prop.clone();
2825        for witness in instantiation {
2826            concl = instantiate_forall(&concl, &witness).ok_or_else(|| {
2827                TacticError::DoesNotApply(
2828                    "rewrite: the equation has fewer binders than the match".to_string(),
2829                )
2830            })?;
2831            eq_proof = DerivationTree::new(
2832                concl.clone(),
2833                InferenceRule::UniversalInstTerm(witness),
2834                vec![eq_proof],
2835            );
2836        }
2837        let proof = crate::engine::leibniz_step(
2838            new_prop.clone(),
2839            &lhs,
2840            &rhs,
2841            eq_proof,
2842            target_hyp.proof.clone(),
2843        )
2844        .ok_or_else(|| {
2845            TacticError::DoesNotApply(format!(
2846                "rewrite {eq_name} at {hyp_name}: no `Eq_rec` motive abstracts exactly the \
2847                 occurrence this step carried, so there is no certificate to build and the \
2848                 step is refused rather than left for the trust door"
2849            ))
2850        })?;
2851
2852        let idx = *self.open.front().ok_or(TacticError::NoOpenGoals)?;
2853        if let Node::Hole(goal) = &mut self.nodes[idx] {
2854            if let Some(h) = goal.hyps.iter_mut().find(|h| h.name == hyp_name) {
2855                h.prop = new_prop;
2856                h.proof = proof;
2857            }
2858        }
2859        Ok(self)
2860    }
2861
2862    /// `rewrite h at hp` at the FIRST occurrence — the spelling a script writes.
2863    pub fn rewrite_hyp(&mut self, eq_name: &str, hyp_name: &str) -> Result<&mut Self, TacticError> {
2864        self.rewrite_hyp_at(eq_name, hyp_name, 0)
2865    }
2866
2867    /// `simp`: normalize the focused goal by the rule set, left-to-right to a
2868    /// fixpoint, then close it if it became trivial (reflexivity or an exact
2869    /// hypothesis). Mirrors Lean's `simp`.
2870    ///
2871    /// Each rewrite is one certified `Rewrite` refinement — the instantiated
2872    /// rule equality (a `UniversalInstTerm` chain over the lemma, conditions
2873    /// discharged by `ModusPonens`) is the closed premise, the rewritten goal
2874    /// the open one — so `qed` re-checks every step in the kernel. Loop
2875    /// protection is a step budget plus a seen-goal set (commuting rules like
2876    /// `a = b, b = a` terminate instead of ping-ponging). Fails only if it
2877    /// neither rewrote nor closed anything.
2878    pub fn simp(&mut self, set: &crate::simp::SimpSet) -> Result<&mut Self, TacticError> {
2879        const BUDGET: usize = 1000;
2880        let mut progress = false;
2881        let mut seen: std::collections::HashSet<String> = std::collections::HashSet::new();
2882        seen.insert(self.focused_goal()?.target.to_string());
2883
2884        for _ in 0..BUDGET {
2885            let g = self.focused_goal()?;
2886            let hyp_view: Vec<(&ProofExpr, &DerivationTree)> =
2887                g.hyps.iter().map(|h| (&h.prop, &h.proof)).collect();
2888
2889            // One term rewrite (rule step or ground arithmetic fold).
2890            let step = set
2891                .find_term_step(&g.target, &hyp_view)
2892                .or_else(|| crate::simp::find_ground_fold(&g.target));
2893            if let Some(step) = step {
2894                let new_target = substitute_in_expr(&g.target, &step.from, &step.to);
2895                if new_target == g.target || !seen.insert(new_target.to_string()) {
2896                    break;
2897                }
2898                // Same shape as `rewrite`: the equality premise proves
2899                // `to = from` (the symmetric of the step equality).
2900                let eq_sym = DerivationTree::new(
2901                    ProofExpr::Identity(step.to.clone(), step.from.clone()),
2902                    InferenceRule::EqualitySymmetry,
2903                    vec![step.eq],
2904                );
2905                let sub = Goal {
2906                    hyps: g.hyps.clone(),
2907                    target: new_target,
2908                };
2909                self.refine(
2910                    g.target.clone(),
2911                    InferenceRule::Rewrite {
2912                        from: step.to,
2913                        to: step.from,
2914                    },
2915                    vec![Child::Closed(eq_sym), Child::Sub(sub)],
2916                );
2917                progress = true;
2918                continue;
2919            }
2920
2921            // A top-level propositional step: an iff rule matching the whole
2922            // goal reduces it to the rule's right-hand side via ModusPonens.
2923            if let Some(iff) = set.find_iff_step(&g.target, &hyp_view) {
2924                if !seen.insert(iff.rhs.to_string()) {
2925                    break;
2926                }
2927                let sub = Goal {
2928                    hyps: g.hyps.clone(),
2929                    target: iff.rhs,
2930                };
2931                self.refine(
2932                    g.target.clone(),
2933                    InferenceRule::ModusPonens,
2934                    vec![Child::Closed(iff.imp), Child::Sub(sub)],
2935                );
2936                progress = true;
2937                continue;
2938            }
2939
2940            break;
2941        }
2942
2943        // Closing attempts on the normalized goal.
2944        if self.rfl().is_ok() {
2945            return Ok(self);
2946        }
2947        if self.assumption().is_ok() {
2948            return Ok(self);
2949        }
2950        if progress {
2951            Ok(self)
2952        } else {
2953            Err(TacticError::DoesNotApply(
2954                "simp: no rule rewrites the goal and it is not closable".to_string(),
2955            ))
2956        }
2957    }
2958
2959    /// `decide`: close the focused goal by evaluation, if it is a closed decidable
2960    /// proposition that evaluates TRUE — ground arithmetic (at ARBITRARY precision, the
2961    /// kernel's own), comparisons, `Bool` equalities, a ground DISEQUALITY, and ∧/∨/→/¬ over
2962    /// them. Mirrors Lean's `decide`. A false or open goal is declined.
2963    ///
2964    /// The two ways this declines are now two different messages. They used to be one — "not
2965    /// a closed decidable goal (or it is false)" — and that conflation is dangerous in one
2966    /// direction: a caller that reads `DoesNotApply` as "try another tactic" keeps searching
2967    /// past a goal that is actually FALSE, and may eventually close it from an unrelated
2968    /// contradiction by ex falso, producing a certified proof of a statement nobody asserted.
2969    /// `decide` knows the difference; now it says it.
2970    pub fn decide(&mut self) -> Result<&mut Self, TacticError> {
2971        let g = self.focused_goal()?;
2972        match crate::decide::decide_verdict(&g.target) {
2973            crate::decide::Verdict::True(tree) => {
2974                self.close(tree)?;
2975                Ok(self)
2976            }
2977            crate::decide::Verdict::False => Err(TacticError::DoesNotApply(format!(
2978                "decide: the goal is closed and decidable, and it is FALSE — `{}` evaluates \
2979                 false, so no tactic can prove it and a search that keeps going is searching \
2980                 for a proof of something untrue",
2981                g.target
2982            ))),
2983            crate::decide::Verdict::Undecided => Err(TacticError::DoesNotApply(format!(
2984                "decide: `{}` is not a CLOSED goal in the decidable fragment (ground Int/Bool \
2985                 arithmetic, comparisons, and ¬/∧/∨/→ over them) — its truth was not \
2986                 determined either way",
2987                g.target
2988            ))),
2989        }
2990    }
2991
2992    /// `omega`: linear INTEGER arithmetic. When the in-scope `≤`/`<` hypotheses
2993    /// are jointly unsatisfiable over ℤ — using discreteness (`a < b ⟹ a+1 ≤ b`),
2994    /// the fact rational solvers lack — refute them and discharge ANY goal by
2995    /// ex-falso. Proves `x < y ∧ y < x+1 ⊢ Q`, which `linarith` cannot (that
2996    /// system is rationally satisfiable). Mirrors the refutation half of Lean's
2997    /// `omega`. Declines when the hypotheses have an integer model.
2998    /// `linarith`: refute the arithmetic hypotheses over the RATIONALS, by Fourier-Motzkin with
2999    /// a Farkas certificate — and decline anything that needs integrality.
3000    ///
3001    /// `linarith` was an ALIAS for `omega`, which tightens `a < b` to `a + 1 ≤ b`. That is sound
3002    /// over ℤ and **unsound over an ordered field**: `ProofExpr` is untyped, so nothing records the
3003    /// carrier, and a goal false over ℚ could be certified because the integer step found a
3004    /// refutation the rationals do not have. Routing here — `engine::cert_farkas`, the same
3005    /// rational core the backward chainer already uses, *without* the discreteness step — makes
3006    /// `linarith` mean what its name means. `omega` keeps the integer reasoning under its own name.
3007    pub fn linarith(&mut self) -> Result<&mut Self, TacticError> {
3008        let g = self.focused_goal()?;
3009        let known: Vec<(ProofExpr, DerivationTree)> = g
3010            .hyps
3011            .iter()
3012            .map(|h| (h.prop.clone(), h.proof.clone()))
3013            .collect();
3014        if !crate::omega_solve::has_arith_facts(&known) {
3015            return Err(TacticError::DoesNotApply(
3016                "linarith: no arithmetic (≤ / <) hypotheses in scope".to_string(),
3017            ));
3018        }
3019        match crate::engine::cert_farkas(&known) {
3020            Some(bot) => {
3021                let tree =
3022                    DerivationTree::new(g.target.clone(), InferenceRule::ExFalso, vec![bot]);
3023                self.close(tree)?;
3024                Ok(self)
3025            }
3026            None => Err(TacticError::DoesNotApply(
3027                "linarith: no rational Farkas certificate — the hypotheses are satisfiable over an \
3028                 ordered field. If the refutation needs integrality, that is `omega`, not `linarith`"
3029                    .to_string(),
3030            )),
3031        }
3032    }
3033
3034    /// A DECISION PROCEDURE for the goal, not only a refutation of the hypotheses.
3035    ///
3036    /// Lean's `omega` negates the goal, adds it to the hypothesis set, and refutes; ours
3037    /// only ever refuted `g.hyps`, so `x ≤ 3 ⊢ x ≤ 4` — the shape most real uses have —
3038    /// was DECLINED with a message ("the integer hypotheses are satisfiable") that described
3039    /// the hypotheses when the problem was that there was no way to attack the goal at all.
3040    /// Three halves now, in order:
3041    ///
3042    /// 1. **Refute the hypotheses.** Unchanged, and still first: contradictory bounds
3043    ///    discharge ANY goal by ex falso.
3044    /// 2. **Prove the goal directly.** A ground comparison by computation; a `≤` goal by
3045    ///    chaining the in-scope `≤` facts (`le_trans`/`le_refl`); an `Int` EQUALITY goal
3046    ///    through the ring oracle, which is how `n + 0 = n` — an `omega` goal in Lean with no
3047    ///    hypotheses whatever — gets proved.
3048    /// 3. **Split on totality and refute the other side.** `le_total a b` is already in the
3049    ///    trusted base, and its own comment names this use. For a `≤` goal, take the goal
3050    ///    itself in the left branch and refute `hyps ∪ {b ≤ a}` in the right.
3051    ///
3052    /// Half 3 is deliberately the SOUND, axiom-free approximation of "negate the goal":
3053    /// `¬(a ≤ b)` is `b + 1 ≤ a` over ℤ, one unit stronger than the `b ≤ a` totality gives,
3054    /// and the extra unit needs an axiom (`¬(a ≤ b) → b + 1 ≤ a`, or antisymmetry) that the
3055    /// trusted base does not have. Adding one to widen a tactic would trade a visible
3056    /// capability gap for an invisible trust cost, so it is NOT done here; the fragment this
3057    /// reaches is "every goal whose negation-by-totality is refutable", which covers every
3058    /// goal with slack. The gate is likewise relaxed: an arithmetic GOAL admits the tactic
3059    /// even with no arithmetic hypothesis in scope, which is the no-hypothesis Lean case.
3060    pub fn omega(&mut self) -> Result<&mut Self, TacticError> {
3061        let g = self.focused_goal()?;
3062        let known: Vec<(ProofExpr, DerivationTree)> = g
3063            .hyps
3064            .iter()
3065            .map(|h| (h.prop.clone(), h.proof.clone()))
3066            .collect();
3067        let arith_goal = crate::omega_solve::is_arith_goal(&g.target);
3068        if !crate::omega_solve::has_arith_facts(&known) && !arith_goal {
3069            return Err(TacticError::DoesNotApply(format!(
3070                "omega: no arithmetic (≤ / <) hypotheses in scope and `{}` is not an \
3071                 arithmetic goal either, so there is nothing linear to decide",
3072                g.target
3073            )));
3074        }
3075        // 1. The rational core FIRST. `omega_close` returns `None` unless it tightened at
3076        // least one STRICT hypothesis, on the assumption that its caller already tried the
3077        // rationals — so a PURELY non-strict contradiction (`5 ≤ x`, `x ≤ 3`) was declined
3078        // with the message "the integer hypotheses are satisfiable" about a system that is
3079        // not. Integrality is a strengthening of the rational theory, never a weakening:
3080        // anything Farkas refutes over ℚ is refuted over ℤ too.
3081        if let Some(bot) =
3082            crate::engine::cert_farkas(&known).or_else(|| crate::omega_solve::omega_close(&known))
3083        {
3084            let tree = DerivationTree::new(g.target.clone(), InferenceRule::ExFalso, vec![bot]);
3085            self.close(tree)?;
3086            return Ok(self);
3087        }
3088        // 2 + 3. Goal-directed.
3089        if let Some(tree) = crate::omega_solve::omega_prove(&known, &g.target) {
3090            self.close(tree)?;
3091            return Ok(self);
3092        }
3093        Err(TacticError::DoesNotApply(format!(
3094            "omega: the hypotheses have an integer model, and `{}` does not follow from them \
3095             — neither directly nor by refuting its negation-by-totality",
3096            g.target
3097        )))
3098    }
3099
3100    /// `calc h₁ h₂ …`: compose the NAMED order/equality facts into the goal — Lean's `calc`,
3101    /// whose job is a chain whose RELATION CHANGES along it.
3102    ///
3103    /// `calc` existed on no LOGOS surface. The pure-`=` chain had an expansion (three
3104    /// `rewrite`s), but a MIXED chain did not: the order graph walked `≤` edges alone, with no
3105    /// arm that could consume an equality, so a single `=` step anywhere made the chain
3106    /// unreachable. The composition now lives in `engine::cert_le_chain` — `≤` edges,
3107    /// discreteness-tightened `<` edges, and equality edges including their CONGRUENT images
3108    /// (`a = b` bridging `a + 1` to `b + 1`) — and this is its name on the surface.
3109    ///
3110    /// Naming the facts is the point, exactly as `simp only [h]` names its rule set: `auto`
3111    /// searches everything in scope, while a `calc` block says which steps, in which order,
3112    /// and fails if they do not compose. A goal `a ≤ d` composes through the chain; an
3113    /// equality goal composes through congruence closure over the named equations.
3114    ///
3115    /// The relation the chain CONCLUDES is `=` or `≤`. A strict `<` conclusion is not
3116    /// certifiable at all: of the eight `Int` order axioms none concludes a `lt` (`lt_succ_le`
3117    /// and `lt_add1_le` both take one as a premise), so the composition can state its result
3118    /// only in the tightened form `a + 1 ≤ d`. The missing primitive is the converse
3119    /// `le_succ_lt : Π a b. (a + 1) ≤ b → a < b`, one new `Int` axiom — named here rather than
3120    /// assumed, because widening a tactic by growing the trusted base is the one trade this
3121    /// campaign forbids.
3122    pub fn calc(&mut self, names: &[String]) -> Result<&mut Self, TacticError> {
3123        let g = self.focused_goal()?;
3124        let mut steps: Vec<(ProofExpr, DerivationTree)> = Vec::new();
3125        for name in names {
3126            let hyp = g
3127                .hyps
3128                .iter()
3129                .find(|h| &h.name == name)
3130                .ok_or_else(|| TacticError::NoSuchHypothesis(name.clone()))?;
3131            steps.push((hyp.prop.clone(), hyp.proof.clone()));
3132        }
3133        if steps.is_empty() {
3134            return Err(TacticError::DoesNotApply(
3135                "calc: name the steps of the chain — `calc h1 h2 h3`".to_string(),
3136            ));
3137        }
3138        // A step may be a QUANTIFIED equation. Lean writes the application into the block
3139        // (`_ = g b := h₂ b`); a named block has to find it, so each `∀x̄. lhs = rhs` is
3140        // E-matched at the chain's own terms and travels on as its ground instances.
3141        let steps = crate::crush::instantiate_steps(&steps, &g.target);
3142        if let Some((a, b)) = crate::engine::as_le_pair(&g.target) {
3143            if let Some(tree) = crate::engine::cert_le_chain(&steps, &a, &b) {
3144                self.close(tree)?;
3145                return Ok(self);
3146            }
3147            return Err(TacticError::DoesNotApply(format!(
3148                "calc: the named steps do not compose into `{}`",
3149                g.target
3150            )));
3151        }
3152        if let Some((a, b)) = crate::omega_solve::as_lt_pair(&g.target) {
3153            if let Some(tree) = crate::engine::cert_lt_chain(&steps, &a, &b) {
3154                self.close(tree)?;
3155                return Ok(self);
3156            }
3157            if !crate::engine::strict_conclusions_available() {
3158                return Err(TacticError::DoesNotApply(format!(
3159                    "calc: a STRICT conclusion `{}` has no certifiable image — of the `Int` \
3160                     order axioms none concludes a `lt` (`lt_succ_le` and `lt_add1_le` both \
3161                     take one as a premise). The chain composes; only the last step is \
3162                     missing, and it is the axiom `le_succ_lt : Π a b. (a + 1) ≤ b → a < b` \
3163                     (or, better, DEFINING `lt a b := le (add a 1) b`, which removes two \
3164                     axioms instead of adding one). State the goal as `a + 1 ≤ b` meanwhile",
3165                    g.target
3166                )));
3167            }
3168            return Err(TacticError::DoesNotApply(format!(
3169                "calc: the named steps do not compose into `{}`",
3170                g.target
3171            )));
3172        }
3173        if let ProofExpr::Identity(l, r) = &g.target {
3174            if let Some(tree) = crate::engine::cert_equality_chain(&steps, l, r) {
3175                self.close(tree)?;
3176                return Ok(self);
3177            }
3178            return Err(TacticError::DoesNotApply(format!(
3179                "calc: the named equations do not chain into `{}`",
3180                g.target
3181            )));
3182        }
3183        Err(TacticError::DoesNotApply(format!(
3184            "calc composes an `=` or `≤` chain; `{}` is neither",
3185            g.target
3186        )))
3187    }
3188
3189    /// `by_rule R`: discharge the focused goal in ONE step with the NAMED inference rule,
3190    /// from the facts already in scope.
3191    ///
3192    /// The language AST has carried a public `ProofStrategy::ByRule(name)` variant — with
3193    /// `Proof: ModusPonens.` as its own documented example — that nothing in the workspace
3194    /// constructs and no driver has an arm for, because the proof layer offered no way to
3195    /// apply a rule by its name. This is that door.
3196    ///
3197    /// It is a real tactic and not a label, and three things make it one:
3198    ///
3199    /// * A name that is not a rule is a NAME error, listing the rules that are — a translator
3200    ///   handing us a Lean rule name needs to know which of the two kinds of failure it hit.
3201    /// * A rule that is declared but has no certifier arm reports
3202    ///   [`InferenceRule::uncertifiable_reason`] — the list exists precisely so a PRODUCER can
3203    ///   consult it before emitting a tree, and this is the one place in the crate that does.
3204    /// * The node is certified BEFORE success is reported. `by_rule R` succeeds only when the
3205    ///   kernel agrees that R, applied to facts in scope, proves this goal — so it can never
3206    ///   hand `qed` a derivation the trust door must refuse.
3207    ///
3208    /// The premises are drawn from the hypotheses in scope and nowhere else: `by_rule` is one
3209    /// step, not a search. A goal needing a subproof is `auto`'s, or is written out.
3210    pub fn by_rule(&mut self, name: &str) -> Result<&mut Self, TacticError> {
3211        /// The widest rule in the enum takes three premises (`DisjunctionElim`: the
3212        /// disjunction and one implication per side), so a one-step application never needs
3213        /// a longer tuple.
3214        const BY_RULE_MAX_ARITY: usize = 3;
3215        let g = self.focused_goal()?;
3216        let Some(rule) = InferenceRule::from_name(name) else {
3217            let known: Vec<String> = InferenceRule::NAMEABLE
3218                .iter()
3219                .map(|r| r.canonical_name())
3220                .collect();
3221            return Err(TacticError::DoesNotApply(format!(
3222                "by_rule: `{name}` is not an inference rule that can be applied from a name \
3223                 alone. A rule carrying an ARGUMENT (a rewrite's equation, an instantiation's \
3224                 witness, an induction's variable) has its own tactic — `rewrite`, `exists`, \
3225                 `induction`. The nameable rules are: {}",
3226                known.join(", ")
3227            )));
3228        };
3229        if let Some(reason) = rule.uncertifiable_reason() {
3230            return Err(TacticError::DoesNotApply(format!(
3231                "by_rule {}: {reason}",
3232                rule.canonical_name()
3233            )));
3234        }
3235        let props: Vec<ProofExpr> = g.hyps.iter().map(|h| h.prop.clone()).collect();
3236        let pool: Vec<DerivationTree> = g.hyps.iter().map(|h| h.proof.clone()).collect();
3237        let checker = crate::verify::ScopedChecker::new(&props, &g.target);
3238        // Candidate premise tuples, shortest first: a leaf rule is one question, and a rule
3239        // that needs two facts is not asked about until the cheaper readings are exhausted.
3240        // The budget bounds the cubic tier, which is the only one that can grow.
3241        const BUDGET: usize = 512;
3242        let mut asked = 0usize;
3243        let mut arity_tuples: Vec<Vec<DerivationTree>> = vec![Vec::new()];
3244        for _ in 0..=BY_RULE_MAX_ARITY {
3245            for combo in &arity_tuples {
3246                if asked >= BUDGET {
3247                    break;
3248                }
3249                asked += 1;
3250                let tree = DerivationTree::new(g.target.clone(), rule.clone(), combo.clone());
3251                if checker.certifies(tree.clone()) {
3252                    self.close(tree)?;
3253                    return Ok(self);
3254                }
3255            }
3256            arity_tuples = arity_tuples
3257                .iter()
3258                .flat_map(|combo| {
3259                    pool.iter().map(move |p| {
3260                        let mut next = combo.clone();
3261                        next.push(p.clone());
3262                        next
3263                    })
3264                })
3265                .collect();
3266            if arity_tuples.len() > BUDGET {
3267                arity_tuples.truncate(BUDGET);
3268            }
3269        }
3270        Err(TacticError::DoesNotApply(format!(
3271            "by_rule {}: that rule does not discharge `{}` from the {} hypothes{} in scope",
3272            rule.canonical_name(),
3273            g.target,
3274            pool.len(),
3275            if pool.len() == 1 { "is" } else { "es" }
3276        )))
3277    }
3278
3279    /// `crush`: the grind-style closer. E-matches the in-scope `∀`-equality
3280    /// lemmas at the goal's ground terms, then discharges the goal by certified
3281    /// congruence closure. Proves goals plain `auto` cannot — e.g.
3282    /// `∀x. f(x)=g(x), a=b, P(g(b)) ⊢ P(f(a))` — and every step is kernel-checked.
3283    pub fn crush(&mut self) -> Result<&mut Self, TacticError> {
3284        let g = self.focused_goal()?;
3285        let premises: Vec<ProofExpr> = g.hyps.iter().map(|h| h.prop.clone()).collect();
3286        match crate::crush::crush_prove(&premises, &g.target) {
3287            Some(tree) => {
3288                self.close(tree)?;
3289                Ok(self)
3290            }
3291            None => Err(TacticError::DoesNotApply(
3292                "crush: could not close the goal by e-matching + congruence".to_string(),
3293            )),
3294        }
3295    }
3296
3297    /// `auto`: discharge the focused goal with the backward chainer (the existing
3298    /// automation, hosted as one tactic). Its hypotheses and the premises are the
3299    /// available knowledge base.
3300    ///
3301    /// With the `verification` feature the chainer's last resort is the Z3 oracle, whose
3302    /// `OracleVerification` leaf attests a goal without a proof term. The chainer reaches
3303    /// it only after every certifiable strategy failed, so such a tree means `auto` found
3304    /// no proof: `close` refuses it and `auto` declines.
3305    pub fn auto(&mut self) -> Result<&mut Self, TacticError> {
3306        let g = self.focused_goal()?;
3307        let mut engine = BackwardChainer::new();
3308        // A tactic's hypotheses ARE kernel hypotheses: the trust door registers each as a
3309        // declaration whose type mentions the statement's free variables as context LOCALS.
3310        // So a step that used one AT AN INSTANCE would cite a proposition no context carries,
3311        // and `qed` would refuse a tree `auto` had already called a proof. Saying so here is
3312        // what makes the honest answer STRUCTURAL — in this reading the search cannot build
3313        // the step at all, so there is nothing for a later check to catch.
3314        engine.set_premise_variables(crate::PremiseVariables::Local);
3315        for h in &g.hyps {
3316            engine.add_axiom(h.prop.clone());
3317        }
3318        match engine.prove(g.target.clone()) {
3319            Ok(tree) => {
3320                self.close(tree)?;
3321                Ok(self)
3322            }
3323            Err(_) => Err(TacticError::AutoFailed),
3324        }
3325    }
3326
3327    fn assemble(&self, idx: usize) -> Result<DerivationTree, TacticError> {
3328        match &self.nodes[idx] {
3329            Node::Done(tree) => Ok(tree.clone()),
3330            Node::Filled {
3331                conclusion,
3332                rule,
3333                children,
3334            } => {
3335                let mut kids = children
3336                    .iter()
3337                    .map(|&c| self.assemble(c))
3338                    .collect::<Result<Vec<_>, _>>()?;
3339                // Generalize the step case: the eigenconstant the search ran under
3340                // becomes the `Variable` the certifier's `Match` binds.
3341                if let InferenceRule::StructuralInduction { step_var, .. } = rule {
3342                    if kids.len() == 2 {
3343                        kids[1] = eigen_to_var_tree(&kids[1], step_var);
3344                    }
3345                }
3346                // Generic induction: each case ran under its own rigid eigenconstants
3347                // (one per constructor argument); remap each back to the bound
3348                // `Variable` the certifier's `match` arm binds and the IH cites.
3349                if let InferenceRule::InductionScheme { cases, .. } = rule {
3350                    for (kid, case) in kids.iter_mut().zip(cases.iter()) {
3351                        for arg in &case.args {
3352                            *kid = eigen_to_var_tree(kid, &arg.name);
3353                        }
3354                    }
3355                }
3356                Ok(DerivationTree::new(conclusion.clone(), rule.clone(), kids))
3357            }
3358            Node::Hole(_) => Err(TacticError::GoalsRemain(1)),
3359        }
3360    }
3361
3362    /// Assemble the current proof tree, if every goal is closed (for inspection/debug).
3363    pub fn assembled(&self) -> Option<DerivationTree> {
3364        if self.open.is_empty() {
3365            self.assemble(self.root).ok()
3366        } else {
3367            None
3368        }
3369    }
3370
3371    /// Run a composed [`Tactic`] against this state, for fluent chaining with the
3372    /// primitive methods.
3373    pub fn run(&mut self, t: &Tactic) -> Result<&mut Self, TacticError> {
3374        t(self)?;
3375        Ok(self)
3376    }
3377
3378    /// Finish the proof: every goal must be closed. Assembles the recorded tactic
3379    /// steps into one derivation and runs it through the kernel trust door — the
3380    /// returned [`VerifiedProof`] is `verified` only if the kernel accepts the term.
3381    pub fn qed(&self) -> Result<VerifiedProof, TacticError> {
3382        if !self.open.is_empty() {
3383            return Err(TacticError::GoalsRemain(self.open.len()));
3384        }
3385        let tree = self.assemble(self.root)?;
3386        Ok(check_derivation(&self.premises, &self.goal, tree))
3387    }
3388}
3389
3390/// A first-class tactic: a transformation of the proof state that either makes
3391/// progress (`Ok`) or does not apply (`Err`). Tactics are values, so they compose
3392/// with the [`combinators`].
3393pub type Tactic = Box<dyn Fn(&mut ProofState) -> Result<(), TacticError>>;
3394
3395/// Tactic *values* and the combinators that compose them — the language layer over
3396/// the primitive [`ProofState`] methods. The backtracking combinators (`first`,
3397/// `try_`, `repeat`) speculate on a clone of the state and commit only on success,
3398/// so a partial failure never corrupts the proof.
3399pub mod combinators {
3400    use super::{ProofState, ProofTerm, Tactic, TacticError};
3401
3402    /// `intro name` as a tactic value.
3403    pub fn intro(name: &str) -> Tactic {
3404        let name = name.to_string();
3405        Box::new(move |st: &mut ProofState| st.intro(&name).map(|_| ()))
3406    }
3407    /// `assumption` as a tactic value.
3408    pub fn assumption() -> Tactic {
3409        Box::new(|st: &mut ProofState| st.assumption().map(|_| ()))
3410    }
3411    /// `simp` as a tactic value, its rule set drawn from everything in scope
3412    /// (premises, intro'd hypotheses, cited lemmas) — the script-level default.
3413    pub fn simp() -> Tactic {
3414        Box::new(|st: &mut ProofState| {
3415            let set = st.scope_simp_set();
3416            st.simp(&set).map(|_| ())
3417        })
3418    }
3419    /// `decide` as a tactic value.
3420    pub fn decide() -> Tactic {
3421        Box::new(|st: &mut ProofState| st.decide().map(|_| ()))
3422    }
3423    /// `omega` as a tactic value.
3424    /// `linarith` (rational Fourier-Motzkin with a Farkas certificate) as a tactic value.
3425    pub fn linarith() -> Tactic {
3426        Box::new(|st: &mut ProofState| st.linarith().map(|_| ()))
3427    }
3428    pub fn omega() -> Tactic {
3429        Box::new(|st: &mut ProofState| st.omega().map(|_| ()))
3430    }
3431    /// `crush` as a tactic value.
3432    pub fn crush() -> Tactic {
3433        Box::new(|st: &mut ProofState| st.crush().map(|_| ()))
3434    }
3435    /// `exact name` as a tactic value.
3436    pub fn exact(name: &str) -> Tactic {
3437        let name = name.to_string();
3438        Box::new(move |st: &mut ProofState| st.exact(&name).map(|_| ()))
3439    }
3440    /// `split` (∧I) as a tactic value.
3441    pub fn split() -> Tactic {
3442        Box::new(|st: &mut ProofState| st.split().map(|_| ()))
3443    }
3444    /// `left` (∨I) as a tactic value.
3445    pub fn left() -> Tactic {
3446        Box::new(|st: &mut ProofState| st.left().map(|_| ()))
3447    }
3448    /// `right` (∨I) as a tactic value.
3449    pub fn right() -> Tactic {
3450        Box::new(|st: &mut ProofState| st.right().map(|_| ()))
3451    }
3452    /// `exists witness` (∃I) as a tactic value.
3453    pub fn exists(witness: ProofTerm) -> Tactic {
3454        Box::new(move |st: &mut ProofState| st.exists(witness.clone()).map(|_| ()))
3455    }
3456    /// `cases name` (∧/∨/∃ elimination) as a tactic value.
3457    pub fn cases(name: &str) -> Tactic {
3458        let name = name.to_string();
3459        Box::new(move |st: &mut ProofState| st.cases(&name).map(|_| ()))
3460    }
3461    /// `rewrite name` (Leibniz substitution by an equality) as a tactic value.
3462    /// `rewrite h at k` as a tactic value — the `k`-th occurrence, 0-based.
3463    pub fn rewrite_at(name: &str, occurrence: usize) -> Tactic {
3464        let name = name.to_string();
3465        Box::new(move |st: &mut ProofState| st.rewrite_at(&name, occurrence).map(|_| ()))
3466    }
3467    pub fn rewrite(name: &str) -> Tactic {
3468        let name = name.to_string();
3469        Box::new(move |st: &mut ProofState| st.rewrite(&name).map(|_| ()))
3470    }
3471    /// `rewrite h at hp` — the LOCATION form, rewriting a HYPOTHESIS rather than the goal.
3472    pub fn rewrite_hyp_at(eq: &str, hyp: &str, occurrence: usize) -> Tactic {
3473        let (eq, hyp) = (eq.to_string(), hyp.to_string());
3474        Box::new(move |st: &mut ProofState| st.rewrite_hyp_at(&eq, &hyp, occurrence).map(|_| ()))
3475    }
3476    /// `apply name` (modus ponens against a named rule) as a tactic value.
3477    pub fn apply(name: &str) -> Tactic {
3478        let name = name.to_string();
3479        Box::new(move |st: &mut ProofState| st.apply_named(&name).map(|_| ()))
3480    }
3481    /// `rfl` (close `t = t` by reflexivity) as a tactic value.
3482    pub fn rfl() -> Tactic {
3483        Box::new(|st: &mut ProofState| st.rfl().map(|_| ()))
3484    }
3485    /// `induction` (structural induction over `Nat`) as a tactic value.
3486    pub fn induction() -> Tactic {
3487        Box::new(|st: &mut ProofState| st.induction().map(|_| ()))
3488    }
3489    /// `induction_over` (generic structural induction over `ind_type`) as a tactic value.
3490    pub fn induction_over(ind_type: &str, ctors: Vec<super::CtorSpec>) -> Tactic {
3491        let ind_type = ind_type.to_string();
3492        Box::new(move |st: &mut ProofState| st.induction_over(&ind_type, ctors.clone()).map(|_| ()))
3493    }
3494    /// `auto` (the backward chainer) as a tactic value.
3495    pub fn auto() -> Tactic {
3496        Box::new(|st: &mut ProofState| st.auto().map(|_| ()))
3497    }
3498
3499    /// `t1; t2; …`: run each tactic in turn; fail (without committing the rest) at
3500    /// the first that does not apply.
3501    pub fn seq(tactics: Vec<Tactic>) -> Tactic {
3502        Box::new(move |st: &mut ProofState| {
3503            for t in &tactics {
3504                t(st)?;
3505            }
3506            Ok(())
3507        })
3508    }
3509
3510    /// `first [t1, t2, …]`: try each tactic on a speculative copy and commit the
3511    /// first that succeeds; fail only if none apply.
3512    pub fn first(tactics: Vec<Tactic>) -> Tactic {
3513        Box::new(move |st: &mut ProofState| {
3514            for t in &tactics {
3515                let mut trial = st.clone();
3516                if t(&mut trial).is_ok() {
3517                    *st = trial;
3518                    return Ok(());
3519                }
3520            }
3521            Err(TacticError::DoesNotApply(
3522                "first: no alternative applied".to_string(),
3523            ))
3524        })
3525    }
3526
3527    /// `try t`: run `t` if it applies, otherwise leave the state unchanged. Always
3528    /// succeeds.
3529    pub fn try_(t: Tactic) -> Tactic {
3530        Box::new(move |st: &mut ProofState| {
3531            let mut trial = st.clone();
3532            if t(&mut trial).is_ok() {
3533                *st = trial;
3534            }
3535            Ok(())
3536        })
3537    }
3538
3539    /// `repeat t`: apply `t` as long as it keeps applying (committing each success),
3540    /// then stop. Always succeeds. Bounded to avoid a non-progressing tactic looping
3541    /// forever.
3542    pub fn repeat(t: Tactic) -> Tactic {
3543        Box::new(move |st: &mut ProofState| {
3544            for _ in 0..100_000 {
3545                let mut trial = st.clone();
3546                if t(&mut trial).is_ok() {
3547                    *st = trial;
3548                } else {
3549                    break;
3550                }
3551                if st.open.is_empty() {
3552                    break;
3553                }
3554            }
3555            Ok(())
3556        })
3557    }
3558
3559    /// `t1 <;> t2`-style: apply `t` to EVERY goal currently open (not just the
3560    /// focused one). Each goal is focused in turn; the subgoals `t` produces for it
3561    /// become the new open set, in original goal order.
3562    /// `any_goals t`: run `t` on every open goal, keeping the goals it left and the goals it
3563    /// declined alike, and succeed iff it succeeded on AT LEAST ONE.
3564    ///
3565    /// The permissive sibling of [`all_goals`], and the one Lean scripts actually reach for after a
3566    /// `constructor` splits a goal into branches only some of which `t` can discharge. Unlike
3567    /// `all_goals` it does not abort the whole combinator when `t` fails on one branch — that
3568    /// branch is simply carried forward unchanged.
3569    pub fn any_goals(t: Tactic) -> Tactic {
3570        Box::new(move |st: &mut ProofState| {
3571            let current: Vec<usize> = st.open.iter().copied().collect();
3572            let mut new_open = std::collections::VecDeque::new();
3573            let mut any_succeeded = false;
3574            for goal_idx in current {
3575                st.open = std::collections::VecDeque::from([goal_idx]);
3576                match t(st) {
3577                    Ok(()) => {
3578                        any_succeeded = true;
3579                        new_open.extend(st.open.iter().copied());
3580                    }
3581                    // `t` declined this branch: keep the goal exactly as it was and move on.
3582                    Err(_) => new_open.push_back(goal_idx),
3583                }
3584            }
3585            st.open = new_open;
3586            if any_succeeded {
3587                Ok(())
3588            } else {
3589                Err(TacticError::DoesNotApply(
3590                    "any_goals: the tactic applied to no open goal".to_string(),
3591                ))
3592            }
3593        })
3594    }
3595
3596    pub fn all_goals(t: Tactic) -> Tactic {
3597        Box::new(move |st: &mut ProofState| {
3598            let current: Vec<usize> = st.open.iter().copied().collect();
3599            let mut new_open = std::collections::VecDeque::new();
3600            for goal_idx in current {
3601                st.open = std::collections::VecDeque::from([goal_idx]);
3602                t(st)?;
3603                new_open.extend(st.open.iter().copied());
3604            }
3605            st.open = new_open;
3606            Ok(())
3607        })
3608    }
3609
3610    /// `t1 <;> t2`: run `t1` on the focused goal, then `t2` on exactly the goals `t1`
3611    /// PRODUCED — not on every goal that happens to be open.
3612    ///
3613    /// The difference is invisible when `<;>` is the first branching step, which almost every
3614    /// textbook use is, and that is why running `all_goals` here survived a large test suite.
3615    /// It is not invisible after an earlier step left a goal waiting: `split . left <;>
3616    /// assumption` must leave the `split`'s right conjunct alone. When `t2` happened to
3617    /// discharge that goal too, the script succeeded one goal further along than the proof
3618    /// believed; when it did not, the failure was reported for a goal the source never asked
3619    /// it to look at. A goal `t1` produced is one that was not open before it ran — node
3620    /// indices only ever grow, so the two sets are told apart exactly.
3621    pub fn then_all(t1: Tactic, t2: Tactic) -> Tactic {
3622        Box::new(move |st: &mut ProofState| {
3623            let before: std::collections::HashSet<usize> = st.open.iter().copied().collect();
3624            t1(st)?;
3625            let after: Vec<usize> = st.open.iter().copied().collect();
3626            let mut new_open = std::collections::VecDeque::new();
3627            for goal_idx in after {
3628                if before.contains(&goal_idx) {
3629                    new_open.push_back(goal_idx);
3630                    continue;
3631                }
3632                st.open = std::collections::VecDeque::from([goal_idx]);
3633                t2(st)?;
3634                new_open.extend(st.open.iter().copied());
3635            }
3636            st.open = new_open;
3637            Ok(())
3638        })
3639    }
3640
3641    /// `· t` / `focus t` / `next t`: run `t` on the focused goal ALONE, and make it an error
3642    /// for the block to leave that goal open.
3643    ///
3644    /// A script is otherwise a flat list of chains, and because subgoals are pushed to the
3645    /// front, stripping Lean's bullets and concatenating the blocks WORKS — right up until a
3646    /// block leaves a goal open or closes two, at which point the blocks silently misalign
3647    /// and, with generic enough tactics, the proof still succeeds having proved the goals in
3648    /// a pairing the source never specified. The bullet is what makes that impossible, so it
3649    /// is the ERROR, not the focusing, that is the capability here.
3650    pub fn focus(t: Tactic) -> Tactic {
3651        Box::new(move |st: &mut ProofState| {
3652            let original: std::collections::VecDeque<usize> = st.open.clone();
3653            let Some(&idx) = st.open.front() else {
3654                return Err(TacticError::NoOpenGoals);
3655            };
3656            let rest: std::collections::VecDeque<usize> = st.open.iter().skip(1).copied().collect();
3657            st.open = std::collections::VecDeque::from([idx]);
3658            match t(st) {
3659                Ok(()) if st.open.is_empty() => {
3660                    st.open = rest;
3661                    Ok(())
3662                }
3663                Ok(()) => {
3664                    let left = st.open.len();
3665                    st.open = original;
3666                    Err(TacticError::DoesNotApply(format!(
3667                        "focus: the block left {left} goal(s) open — a focused block must \
3668                         close exactly the goal it opened"
3669                    )))
3670                }
3671                Err(e) => {
3672                    st.open = original;
3673                    Err(e)
3674                }
3675            }
3676        })
3677    }
3678
3679    /// `by_contra h` as a tactic value.
3680    pub fn by_contra(name: &str) -> Tactic {
3681        let name = name.to_string();
3682        Box::new(move |st: &mut ProofState| st.by_contra(&name).map(|_| ()))
3683    }
3684    /// `ring` (commutative-ring normalisation) as a tactic value.
3685    pub fn ring() -> Tactic {
3686        Box::new(|st: &mut ProofState| st.ring().map(|_| ()))
3687    }
3688    /// `exact <term>` as a tactic value.
3689    pub fn exact_term(term: super::PTerm) -> Tactic {
3690        Box::new(move |st: &mut ProofState| st.exact_term(&term).map(|_| ()))
3691    }
3692    /// `refine <term>` as a tactic value.
3693    pub fn refine(term: super::PTerm) -> Tactic {
3694        Box::new(move |st: &mut ProofState| st.refine_term(&term).map(|_| ()))
3695    }
3696    /// `have name from <term>` as a tactic value.
3697    pub fn have(name: &str, term: super::PTerm) -> Tactic {
3698        let name = name.to_string();
3699        Box::new(move |st: &mut ProofState| st.have_term(&name, &term).map(|_| ()))
3700    }
3701    /// `exists <term>` as a tactic value, with the witness resolved against the goal's scope.
3702    pub fn exists_term(term: super::PTerm) -> Tactic {
3703        Box::new(move |st: &mut ProofState| {
3704            let witness = st.value_term(&term)?;
3705            st.exists(witness).map(|_| ())
3706        })
3707    }
3708    /// `cases name with a b` as a tactic value.
3709    pub fn cases_with(name: &str, names: Vec<String>) -> Tactic {
3710        let name = name.to_string();
3711        Box::new(move |st: &mut ProofState| st.cases_with(&name, &names).map(|_| ()))
3712    }
3713    /// `by_rule R` as a tactic value — discharge the goal with the NAMED inference rule.
3714    pub fn by_rule(name: &str) -> Tactic {
3715        let name = name.to_string();
3716        Box::new(move |st: &mut ProofState| st.by_rule(&name).map(|_| ()))
3717    }
3718
3719    /// `calc h1 h2 …` as a tactic value — compose the named chain.
3720    pub fn calc(names: Vec<String>) -> Tactic {
3721        Box::new(move |st: &mut ProofState| st.calc(&names).map(|_| ()))
3722    }
3723    /// `induction name` as a tactic value.
3724    pub fn induction_on(name: &str) -> Tactic {
3725        let name = name.to_string();
3726        Box::new(move |st: &mut ProofState| st.induction_on(&name).map(|_| ()))
3727    }
3728    /// `simp only [a, b]` as a tactic value — the rule set is exactly the named hypotheses.
3729    pub fn simp_only(names: Vec<String>) -> Tactic {
3730        Box::new(move |st: &mut ProofState| {
3731            let set = st.named_simp_set(&names)?;
3732            st.simp(&set).map(|_| ())
3733        })
3734    }
3735    /// `simp [a, b]` as a tactic value — Lean's "these AS WELL", which for a default set
3736    /// that is already the whole scope adds nothing. The names are still resolved, so a
3737    /// typo is an error rather than a silently ignored rule.
3738    pub fn simp_with(names: Vec<String>) -> Tactic {
3739        Box::new(move |st: &mut ProofState| {
3740            st.named_simp_set(&names)?;
3741            let set = st.scope_simp_set();
3742            st.simp(&set).map(|_| ())
3743        })
3744    }
3745}