Skip to main content

logicaffeine_proof/
tactic_script.rs

1//! A tiny proof-script language over the [`crate::tactic`] combinators — proofs as
2//! TEXT, the way a Lean/Coq proof reads. This is the self-contained seam toward a
3//! full English vernacular: it has no dependency on the surface language, so it
4//! compiles a script string straight into a composed [`Tactic`].
5//!
6//! Grammar (precedence low → high):
7//!
8//! ```text
9//! script  := seq
10//! seq     := chain (';' chain)*          // run in order
11//! chain   := atom ('<;>' atom)*          // `t1 <;> t2`: t2 on the goals t1 spawned
12//! atom    := '(' script ')'
13//!          | 'first' '[' script ('|' script)* ']'   // first that applies (backtracks)
14//!          | 'try' atom                              // run if it applies, else no-op
15//!          | 'repeat' atom                           // apply until it stops applying
16//!          | 'all_goals' atom | 'any_goals' atom     // every / at least one open goal
17//!          | 'focus' atom                            // Lean's bullet: must close its goal
18//!          | NAME ARG*                               // a primitive tactic
19//! term    := factor (('+'|'-') factor)*  // the argument of exact/use/have/refine
20//! factor  := app ('*' app)*
21//! app     := primary primary*            // juxtaposition: application
22//! primary := NAME | '?' NAME? | '(' term (',' term)* ')'
23//! ```
24//!
25//! Primitive tactics: `intro a b`, `exact <term>`, `apply h`, `rfl`, `cases h with a b`,
26//! `rewrite h [at <k> | at <hyp> [<k>]]`, `exists <term>`, `assumption`, `simp only [h]`,
27//! `decide`, `omega`, `linarith`, `ring`, `crush`, `calc h1 h2 …`, `by_rule <Rule>`, `split`,
28//! `left`, `right`, `auto`, `induction n`, `by_contra h`, `have h from <term>`,
29//! `refine <term>`.
30//!
31//! `rewrite`'s `at` clause carries both aspects of positional rewriting: `at <k>` is Lean's
32//! `nth_rewrite` (the POSITION, in the goal) and `at <hyp>` is Lean's `rw … at h` (the
33//! LOCATION); `at <hyp> <k>` is both.
34
35use std::collections::HashMap;
36
37use crate::tactic::combinators as c;
38use crate::tactic::{PTerm, ProofState, Tactic};
39use crate::verify::{citation_order, LibraryResult, LibraryTheorem};
40use crate::ProofExpr;
41
42/// A script parse error, with a human-readable reason.
43#[derive(Debug, Clone, PartialEq)]
44pub struct ScriptError(pub String);
45
46impl std::fmt::Display for ScriptError {
47    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
48        write!(f, "tactic script error: {}", self.0)
49    }
50}
51
52#[derive(Debug, Clone, PartialEq)]
53enum Tok {
54    Word(String),
55    Semi,
56    ThenAll,
57    LParen,
58    RParen,
59    LBracket,
60    RBracket,
61    Bar,
62    /// An arithmetic infix operator, by the `ProofTerm` function it builds.
63    Op(&'static str),
64    /// The `?` that opens a `refine` hole.
65    Question,
66}
67
68fn lex(src: &str) -> Result<Vec<Tok>, ScriptError> {
69    let mut toks = Vec::new();
70    let bytes = src.as_bytes();
71    let mut i = 0;
72    while i < bytes.len() {
73        let ch = bytes[i] as char;
74        match ch {
75            c if c.is_whitespace() => i += 1,
76            // Sentence punctuation reads as a step separator, so prose flows: a proof
77            // can be written `Assume h. By cases on h, …` and parse the same as `;`.
78            ';' | '.' | ',' => {
79                toks.push(Tok::Semi);
80                i += 1;
81            }
82            '(' => {
83                toks.push(Tok::LParen);
84                i += 1;
85            }
86            ')' => {
87                toks.push(Tok::RParen);
88                i += 1;
89            }
90            '[' => {
91                toks.push(Tok::LBracket);
92                i += 1;
93            }
94            ']' => {
95                toks.push(Tok::RBracket);
96                i += 1;
97            }
98            '|' => {
99                toks.push(Tok::Bar);
100                i += 1;
101            }
102            '<' if src[i..].starts_with("<;>") => {
103                toks.push(Tok::ThenAll);
104                i += 3;
105            }
106            // Arithmetic, so a witness can be a compound term (`use (n + 1)`) rather than
107            // only a bare name.
108            '+' => {
109                toks.push(Tok::Op("add"));
110                i += 1;
111            }
112            '-' => {
113                toks.push(Tok::Op("sub"));
114                i += 1;
115            }
116            '*' => {
117                toks.push(Tok::Op("mul"));
118                i += 1;
119            }
120            '?' => {
121                toks.push(Tok::Question);
122                i += 1;
123            }
124            c if c.is_alphanumeric() || c == '_' => {
125                let start = i;
126                while i < bytes.len() {
127                    let cc = bytes[i] as char;
128                    if cc.is_alphanumeric() || cc == '_' {
129                        i += 1;
130                    } else {
131                        break;
132                    }
133                }
134                toks.push(Tok::Word(src[start..i].to_string()));
135            }
136            other => return Err(ScriptError(format!("unexpected character {other:?}"))),
137        }
138    }
139    Ok(toks)
140}
141
142/// A registry of USER-DEFINED tactics (M) — the metaprogramming seam. A user names a
143/// composite tactic (built from primitives and combinators) with [`TacticEnv::define`], and
144/// may then reference it BY NAME in any later script, including from within other
145/// user-defined tactics. This is "write your own tactic in the language", without Rust —
146/// the definitions are stored as source and re-expanded (depth-bounded, so a recursive
147/// definition is rejected rather than looping) wherever the name appears.
148#[derive(Clone, Default)]
149pub struct TacticEnv {
150    defs: std::collections::HashMap<String, String>,
151}
152
153impl TacticEnv {
154    pub fn new() -> Self {
155        Self::default()
156    }
157    /// Define a named tactic from a script source. Names are case-insensitive.
158    pub fn define(&mut self, name: &str, script: &str) {
159        self.defs
160            .insert(name.to_ascii_lowercase(), script.to_string());
161    }
162    fn get(&self, name: &str) -> Option<&String> {
163        self.defs.get(&name.to_ascii_lowercase())
164    }
165}
166
167/// Depth bound on user-tactic expansion — a recursive definition (`t := … t …`) is refused
168/// at this depth rather than looping forever.
169const MAX_TACTIC_DEPTH: usize = 128;
170
171struct Parser {
172    toks: Vec<Tok>,
173    pos: usize,
174    env: TacticEnv,
175    depth: usize,
176}
177
178impl Parser {
179    fn peek(&self) -> Option<&Tok> {
180        self.toks.get(self.pos)
181    }
182    fn bump(&mut self) -> Option<Tok> {
183        let t = self.toks.get(self.pos).cloned();
184        if t.is_some() {
185            self.pos += 1;
186        }
187        t
188    }
189    fn expect(&mut self, t: &Tok) -> Result<(), ScriptError> {
190        match self.bump() {
191            Some(got) if &got == t => Ok(()),
192            other => Err(ScriptError(format!("expected {t:?}, found {other:?}"))),
193        }
194    }
195
196    /// True if the next token ends a step: `;`/`.`/`,` (lexed to `Semi`) or the word
197    /// `then`. Lets prose read `Assume h, then by cases on h.`
198    fn at_separator(&self) -> bool {
199        matches!(self.peek(), Some(Tok::Semi))
200            || matches!(self.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case("then"))
201    }
202
203    /// Skip purely connective filler words (`by`, `the`, `on`, …) so a tactic can be
204    /// stated as `by cases on h` and mean `cases h`.
205    fn skip_filler(&mut self) {
206        while matches!(self.peek(), Some(Tok::Word(w)) if is_filler(w)) {
207            self.bump();
208        }
209    }
210
211    /// Read one IDENTIFIER, looking past connective filler — but never past the last word.
212    ///
213    /// `skip_filler` used to run unconditionally inside the argument reader, so thirteen
214    /// ordinary identifiers (`a`, `an`, `it`, `we`, `on`, `of`, `to`, `the`, `that`, `now`,
215    /// `with`, `by`, `and`) were swallowed before the tactic ever saw them: `exists A` and
216    /// `cases it` were unspellable, and the reported error blamed the tactic for having no
217    /// argument rather than the vocabulary for eating it. A filler word is filler only when
218    /// ANOTHER word still follows to be the argument; the last word standing is the
219    /// argument, whatever it is spelled.
220    fn ident(&mut self) -> Option<String> {
221        let mut i = self.pos;
222        while matches!(self.toks.get(i), Some(Tok::Word(w)) if is_filler(w)) {
223            if matches!(self.toks.get(i + 1), Some(Tok::Word(_))) {
224                i += 1;
225            } else {
226                break;
227            }
228        }
229        match self.toks.get(i) {
230            Some(Tok::Word(w)) => {
231                let w = w.clone();
232                self.pos = i + 1;
233                Some(w)
234            }
235            _ => None,
236        }
237    }
238
239    /// True if the next token could start ANOTHER name in a list (`intro hp hq`,
240    /// `cases h with hp hq`). A word that names a tactic ends the list instead, so a script
241    /// that omits a separator still reads the way it always did.
242    fn at_extra_name(&self) -> bool {
243        match self.peek() {
244            Some(Tok::Word(w)) => {
245                !self.at_separator() && canonical(w).is_none() && !is_combinator_word(w)
246            }
247            _ => false,
248        }
249    }
250
251    /// The rest of a name list, after its first name has been read.
252    fn extra_names(&mut self) -> Vec<String> {
253        let mut names = Vec::new();
254        while self.at_extra_name() {
255            match self.bump() {
256                Some(Tok::Word(w)) => names.push(w),
257                _ => unreachable!("at_extra_name saw a word"),
258            }
259        }
260        names
261    }
262
263    /// An optional `at k` clause naming ONE occurrence to rewrite (0-based). Consumed only
264    /// when both words are there and the second is a number, so `rewrite h` and a following
265    /// step are untouched.
266    fn occurrence_clause(&mut self) -> Option<usize> {
267        match self.where_clause() {
268            Some(RewriteWhere::Goal(k)) => Some(k),
269            _ => None,
270        }
271    }
272
273    /// An optional `at …` clause saying WHERE a rewrite lands.
274    ///
275    /// Positional rewriting has two aspects and Lean spells them separately — `nth_rewrite 2 [h]`
276    /// picks the POSITION, `rw [h] at hp` picks the LOCATION — so this one clause reads both:
277    ///
278    /// * `at 2` — the goal, at occurrence 2. A number is never a hypothesis name in practice.
279    /// * `at hp` — the hypothesis `hp`, at its first occurrence.
280    /// * `at hp 2` — the hypothesis `hp`, at occurrence 2.
281    ///
282    /// `at` is not a filler word and `rewrite` takes no second name of its own, so the position
283    /// is unambiguous; anything else after the equation is left for the next step.
284    fn where_clause(&mut self) -> Option<RewriteWhere> {
285        if !matches!(self.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case("at")) {
286            return None;
287        }
288        let Some(Tok::Word(first)) = self.toks.get(self.pos + 1).cloned() else {
289            return None;
290        };
291        if let Ok(index) = first.parse::<usize>() {
292            self.pos += 2;
293            return Some(RewriteWhere::Goal(index));
294        }
295        // `at <name>` — a hypothesis, with an optional occurrence after it.
296        let index = match self.toks.get(self.pos + 2) {
297            Some(Tok::Word(w)) => w.parse::<usize>().ok(),
298            _ => None,
299        };
300        self.pos += if index.is_some() { 3 } else { 2 };
301        Some(RewriteWhere::Hyp(first, index.unwrap_or(0)))
302    }
303
304    /// An optional `with a b …` clause naming what an elimination binds.
305    fn with_clause(&mut self) -> Vec<String> {
306        if !matches!(self.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case("with")) {
307            return Vec::new();
308        }
309        self.bump();
310        let mut names = Vec::new();
311        if let Some(first) = self.ident() {
312            names.push(first);
313            names.extend(self.extra_names());
314        }
315        names
316    }
317
318    /// `term := factor (('+'|'-') factor)*` — the argument of `exact`/`use`/`have`/`refine`.
319    fn parse_term(&mut self) -> Result<PTerm, ScriptError> {
320        let mut lhs = self.parse_factor()?;
321        while let Some(Tok::Op(op)) = self.peek() {
322            if *op == "mul" {
323                break;
324            }
325            let op = *op;
326            self.bump();
327            let rhs = self.parse_factor()?;
328            lhs = PTerm::Op(op, Box::new(lhs), Box::new(rhs));
329        }
330        Ok(lhs)
331    }
332
333    /// `factor := application ('*' application)*`
334    fn parse_factor(&mut self) -> Result<PTerm, ScriptError> {
335        let mut lhs = self.parse_application()?;
336        while matches!(self.peek(), Some(Tok::Op("mul"))) {
337            self.bump();
338            let rhs = self.parse_application()?;
339            lhs = PTerm::Op("mul", Box::new(lhs), Box::new(rhs));
340        }
341        Ok(lhs)
342    }
343
344    /// `application := primary primary*` — juxtaposition, as in Lean.
345    fn parse_application(&mut self) -> Result<PTerm, ScriptError> {
346        let head = self.parse_primary()?;
347        let mut args = Vec::new();
348        while self.at_primary() {
349            args.push(self.parse_primary()?);
350        }
351        Ok(if args.is_empty() {
352            head
353        } else {
354            PTerm::App(Box::new(head), args)
355        })
356    }
357
358    fn at_primary(&self) -> bool {
359        match self.peek() {
360            Some(Tok::LParen) | Some(Tok::Question) => true,
361            Some(Tok::Word(_)) => !self.at_separator(),
362            _ => false,
363        }
364    }
365
366    /// `primary := NAME | '?' NAME? | '(' term (',' term)* ')'`
367    fn parse_primary(&mut self) -> Result<PTerm, ScriptError> {
368        match self.peek() {
369            Some(Tok::Question) => {
370                self.bump();
371                // `?_` and `?h` name the same thing — a goal the block leaves open.
372                if matches!(self.peek(), Some(Tok::Word(_))) {
373                    self.bump();
374                }
375                Ok(PTerm::Hole)
376            }
377            Some(Tok::LParen) => {
378                self.bump();
379                let mut items = vec![self.parse_term()?];
380                // `,` lexes as a step separator everywhere else; INSIDE a term it is the
381                // anonymous constructor's comma.
382                while matches!(self.peek(), Some(Tok::Semi)) {
383                    self.bump();
384                    if matches!(self.peek(), Some(Tok::RParen)) {
385                        break;
386                    }
387                    items.push(self.parse_term()?);
388                }
389                self.expect(&Tok::RParen)?;
390                Ok(if items.len() == 1 {
391                    items.into_iter().next().expect("one item")
392                } else {
393                    PTerm::Tuple(items)
394                })
395            }
396            Some(Tok::Word(_)) => self
397                .ident()
398                .map(PTerm::Ident)
399                .ok_or_else(|| ScriptError("expected a term".to_string())),
400            other => Err(ScriptError(format!("expected a term, found {other:?}"))),
401        }
402    }
403
404    /// `script := chain (sep+ chain)*` — a *run* of separators (`.`/`,`/`;`/`then`,
405    /// e.g. the `, then` in `Assume h, then …`) counts as one.
406    fn parse_seq(&mut self) -> Result<Tactic, ScriptError> {
407        let mut steps = vec![self.parse_chain()?];
408        loop {
409            let mut consumed = false;
410            while self.at_separator() {
411                self.bump();
412                consumed = true;
413            }
414            if !consumed {
415                break;
416            }
417            // Allow a trailing separator (a closing `.`) before `)`/`]`/`|`/EOF.
418            if matches!(
419                self.peek(),
420                None | Some(Tok::RParen) | Some(Tok::RBracket) | Some(Tok::Bar)
421            ) {
422                break;
423            }
424            steps.push(self.parse_chain()?);
425        }
426        Ok(if steps.len() == 1 {
427            steps.into_iter().next().unwrap()
428        } else {
429            c::seq(steps)
430        })
431    }
432
433    /// `chain := atom ('<;>' atom)*` — left-associative `then_all`.
434    fn parse_chain(&mut self) -> Result<Tactic, ScriptError> {
435        let mut acc = self.parse_atom()?;
436        while matches!(self.peek(), Some(Tok::ThenAll)) {
437            self.bump();
438            let rhs = self.parse_atom()?;
439            acc = c::then_all(acc, rhs);
440        }
441        Ok(acc)
442    }
443
444    fn parse_atom(&mut self) -> Result<Tactic, ScriptError> {
445        self.skip_filler();
446        match self.peek() {
447            Some(Tok::LParen) => {
448                self.bump();
449                let inner = self.parse_seq()?;
450                self.expect(&Tok::RParen)?;
451                Ok(inner)
452            }
453            Some(Tok::Word(w)) if w == "first" => {
454                self.bump();
455                self.expect(&Tok::LBracket)?;
456                let mut alts = vec![self.parse_seq()?];
457                while matches!(self.peek(), Some(Tok::Bar)) {
458                    self.bump();
459                    alts.push(self.parse_seq()?);
460                }
461                self.expect(&Tok::RBracket)?;
462                Ok(c::first(alts))
463            }
464            Some(Tok::Word(w)) if w == "try" => {
465                self.bump();
466                Ok(c::try_(self.parse_atom()?))
467            }
468            Some(Tok::Word(w)) if w == "repeat" => {
469                self.bump();
470                Ok(c::repeat(self.parse_atom()?))
471            }
472            // `all_goals <tactic>` — a tactic-TAKING combinator, so it parses like `try`/`repeat`
473            // rather than through `parse_primitive`. `combinators::all_goals` has existed and
474            // certified all along; it simply had no spelling.
475            Some(Tok::Word(w)) if w == "all_goals" || w == "everywhere" => {
476                self.bump();
477                Ok(c::all_goals(self.parse_atom()?))
478            }
479            Some(Tok::Word(w)) if w == "any_goals" || w == "somewhere" => {
480                self.bump();
481                Ok(c::any_goals(self.parse_atom()?))
482            }
483            // Lean's bullet. A focused block must CLOSE the goal it opened, which is the
484            // whole capability: without it the blocks of a flat script silently misalign.
485            Some(Tok::Word(w)) if w == "focus" || w == "next" || w == "bullet" => {
486                self.bump();
487                Ok(c::focus(self.parse_atom()?))
488            }
489            Some(Tok::Word(_)) => self.parse_primitive(),
490            other => Err(ScriptError(format!("expected a tactic, found {other:?}"))),
491        }
492    }
493
494    fn parse_primitive(&mut self) -> Result<Tactic, ScriptError> {
495        let raw = match self.bump() {
496            Some(Tok::Word(w)) => w,
497            other => {
498                return Err(ScriptError(format!(
499                    "expected a tactic name, found {other:?}"
500                )))
501            }
502        };
503        // A USER-DEFINED tactic (M) takes PRECEDENCE — an explicit `define` is authoritative,
504        // so a user tactic may even shadow a built-in alias (`both`, `split`, …). Expand its
505        // stored source in place, one level deeper (recursion is depth-bounded).
506        if let Some(src) = self.env.get(&raw).cloned() {
507            if self.depth >= MAX_TACTIC_DEPTH {
508                return Err(ScriptError(format!(
509                    "user tactic `{raw}` expands too deeply (recursive definition?)"
510                )));
511            }
512            return parse_with_env(&src, &self.env, self.depth + 1);
513        }
514        let name = canonical(&raw).ok_or_else(|| ScriptError(format!("unknown tactic `{raw}`")))?;
515        // Filler may sit between the verb and its object: `cases on h`, `rewrite with eq`.
516        macro_rules! arg {
517            () => {
518                self.ident()
519                    .ok_or_else(|| ScriptError(format!("tactic `{name}` expects an argument")))?
520            };
521        }
522        match name {
523            // Lean's `intro a b c` introduces three binders in ONE step; the one-argument
524            // atom read `b` as the next tactic name and killed the whole script at parse
525            // time, discarding the proof before any step ran.
526            "intro" => {
527                let first = arg!();
528                let rest = self.extra_names();
529                Ok(if rest.is_empty() {
530                    c::intro(&first)
531                } else {
532                    c::seq(
533                        std::iter::once(first)
534                            .chain(rest)
535                            .map(|n| c::intro(&n))
536                            .collect(),
537                    )
538                })
539            }
540            "exact" => Ok(c::exact_term(self.parse_term()?)),
541            "apply" => Ok(c::apply(&arg!())),
542            "rfl" => Ok(c::rfl()),
543            "cases" => {
544                let target = arg!();
545                let names = self.with_clause();
546                Ok(if names.is_empty() {
547                    c::cases(&target)
548                } else {
549                    c::cases_with(&target, names)
550                })
551            }
552            "rewrite" => {
553                let hypothesis = arg!();
554                // `rewrite h at 2` is Lean's occurrence argument and `rewrite h at hp` is its
555                // `rw [h] at hp` — the POSITION and the LOCATION, the two aspects `conv`
556                // exists to express. See `Parser::where_clause`.
557                match self.where_clause() {
558                    Some(RewriteWhere::Goal(k)) => Ok(c::rewrite_at(&hypothesis, k)),
559                    Some(RewriteWhere::Hyp(target, k)) => {
560                        Ok(c::rewrite_hyp_at(&hypothesis, &target, k))
561                    }
562                    None => Ok(c::rewrite(&hypothesis)),
563                }
564            }
565            "exists" => Ok(c::exists_term(self.parse_term()?)),
566            "assumption" => Ok(c::assumption()),
567            "simp" => {
568                // `simp only [h₁, h₂]` names its rule set exactly; a bare `simp` uses the
569                // whole scope. A list WITHOUT `only` is Lean's "these as well", and since
570                // our default set is already the whole scope, naming them adds nothing —
571                // but the names are still checked, so a typo is not silently ignored.
572                let only =
573                    matches!(self.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case("only"));
574                if only {
575                    self.bump();
576                }
577                let names = self.bracketed_names()?;
578                Ok(match (only, names) {
579                    (_, None) => c::simp(),
580                    (true, Some(names)) => c::simp_only(names),
581                    (false, Some(names)) => c::simp_with(names),
582                })
583            }
584            // `calc h1 h2 …` — the chain, by the names of its steps. The relation may CHANGE
585            // along it (`=` then `≤`), which is what `calc` and Lean's `Trans` are for.
586            "calc" => {
587                let first = arg!();
588                let mut names = vec![first];
589                names.extend(self.extra_names());
590                Ok(c::calc(names))
591            }
592            // `by_rule R` — the goal is discharged by the NAMED inference rule, in one step.
593            // This is the script spelling of the language AST's `ProofStrategy::ByRule`,
594            // whose documented example (`Proof: ModusPonens.`) had no image in the proof
595            // layer at all.
596            "by_rule" | "byrule" => Ok(c::by_rule(&arg!())),
597            "decide" => Ok(c::decide()),
598            "omega" => Ok(c::omega()),
599            "linarith" => Ok(c::linarith()),
600            "ring" => Ok(c::ring()),
601            "crush" => Ok(c::crush()),
602            "split" => Ok(c::split()),
603            "left" => Ok(c::left()),
604            "right" => Ok(c::right()),
605            "auto" => Ok(c::auto()),
606            "by_contra" => Ok(c::by_contra(&arg!())),
607            "have" => {
608                let bound = arg!();
609                // `have h from e` / `have h by e` — the connective is optional.
610                if matches!(self.peek(), Some(Tok::Word(w)) if is_have_connective(w)) {
611                    self.bump();
612                }
613                Ok(c::have(&bound, self.parse_term()?))
614            }
615            "refine" => {
616                let term = self.parse_term()?;
617                if term == PTerm::Hole {
618                    return Err(ScriptError(
619                        "refine with a bare hole leaves the goal exactly as it was".to_string(),
620                    ));
621                }
622                Ok(c::refine(term))
623            }
624            // `induction n` NAMES its target, the way Lean's does. Argumentless, it inducts
625            // on whatever binder happens to be outermost — which against `∀ m n, Q m n`
626            // proves a DIFFERENT theorem, certified, with nothing downstream able to tell.
627            "induction" => Ok(match self.at_extra_name().then(|| self.ident()).flatten() {
628                Some(variable) => c::induction_on(&variable),
629                None => c::induction(),
630            }),
631            _ => Err(ScriptError(format!("unknown tactic `{name}`"))),
632        }
633    }
634
635    /// An optional `[a, b, c]` name list.
636    fn bracketed_names(&mut self) -> Result<Option<Vec<String>>, ScriptError> {
637        if !matches!(self.peek(), Some(Tok::LBracket)) {
638            return Ok(None);
639        }
640        self.bump();
641        let mut names = Vec::new();
642        loop {
643            while matches!(self.peek(), Some(Tok::Semi)) {
644                self.bump();
645            }
646            if matches!(self.peek(), Some(Tok::RBracket)) {
647                break;
648            }
649            match self.bump() {
650                Some(Tok::Word(w)) => names.push(w),
651                other => {
652                    return Err(ScriptError(format!(
653                        "expected a lemma name, found {other:?}"
654                    )))
655                }
656            }
657        }
658        self.expect(&Tok::RBracket)?;
659        Ok(Some(names))
660    }
661}
662
663/// Words that may stand between a `have`'s name and its proof.
664fn is_have_connective(w: &str) -> bool {
665    matches!(
666        w.to_ascii_lowercase().as_str(),
667        "from" | "by" | "using" | "via" | "proved"
668    )
669}
670
671/// Words that introduce a tactic-TAKING combinator rather than naming a binder.
672fn is_combinator_word(w: &str) -> bool {
673    matches!(
674        w,
675        "first"
676            | "try"
677            | "repeat"
678            | "all_goals"
679            | "everywhere"
680            | "any_goals"
681            | "somewhere"
682            | "focus"
683            | "next"
684            | "bullet"
685    )
686}
687
688/// Connective filler words that carry no tactic meaning — skipped so a step can be
689/// phrased as prose (`by cases on h`, `then by assumption`).
690fn is_filler(w: &str) -> bool {
691    matches!(
692        w.to_ascii_lowercase().as_str(),
693        "by" | "the"
694            | "on"
695            | "that"
696            | "now"
697            | "with"
698            | "we"
699            | "it"
700            | "a"
701            | "an"
702            | "of"
703            | "to"
704            | "and"
705    )
706}
707
708/// Where a `rewrite` lands — see [`Parser::where_clause`].
709enum RewriteWhere {
710    /// The goal, at this occurrence.
711    Goal(usize),
712    /// This hypothesis, at this occurrence.
713    Hyp(String, usize),
714}
715
716/// Map an English-esque verb to its canonical tactic name. `Suppose`/`assume`/`let`
717/// all mean `intro`; `automatically`/`trivially` mean `auto`; and so on — the
718/// vocabulary that lets a proof read like prose. Case-insensitive. Public so an editor
719/// highlights exactly the words the engine accepts.
720pub fn canonical(word: &str) -> Option<&'static str> {
721    match word.to_ascii_lowercase().as_str() {
722        "intro" | "assume" | "suppose" | "let" | "introduce" | "given" | "fix" => Some("intro"),
723        "exact" | "from" | "because" => Some("exact"),
724        // `apply` reaches `ProofState::apply_named`; the capability is modus ponens against a
725        // named rule and has always certified — only the spelling was missing.
726        "apply" | "via" => Some("apply"),
727        // `rfl` names the reflexivity closer that previously only `simp` could reach.
728        "rfl" | "reflexivity" => Some("rfl"),
729        "cases" | "destruct" | "consider" | "casework" => Some("cases"),
730        "rewrite" | "rw" | "substitute" | "subst" => Some("rewrite"),
731        "exists" | "use" | "witness" | "choose" | "provide" => Some("exists"),
732        "assumption" | "done" | "trivial" | "established" | "hypothesis" => Some("assumption"),
733        "simp" | "simplify" | "normalize" | "simplification" => Some("simp"),
734        "decide" | "compute" | "evaluate" | "calculate" => Some("decide"),
735        // `linarith` is NO LONGER an alias for `omega`. `omega` tightens `a < b` to `a + 1 ≤ b`,
736        // which is sound over ℤ and unsound over an ordered field — and `ProofExpr` is untyped, so
737        // nothing records the carrier. They are different tactics and now have different names.
738        "omega" | "arithmetic" | "integers" => Some("omega"),
739        "linarith" | "rationals" => Some("linarith"),
740        "crush" | "grind" | "blast" => Some("crush"),
741        "split" | "constructor" | "both" | "conjunction" => Some("split"),
742        "left" => Some("left"),
743        "right" => Some("right"),
744        "auto" | "tauto" | "automatically" | "automation" | "trivially" | "directly" => {
745            Some("auto")
746        }
747        "induction" | "induct" => Some("induction"),
748        // `by_contra h` is a STEP that assumes ¬G and leaves ⊥, so the twenty steps of a
749        // classical proof can be written; the classical reductio was reachable only as one
750        // opaque call inside `auto`'s search before.
751        "by_contra" | "bycontra" | "contra" | "contradiction" => Some("by_contra"),
752        // `ring` was reachable only from the literate kernel surface; the same
753        // commutative-ring oracle now has a name on this one.
754        "ring" | "polynomial" => Some("ring"),
755        // `calc` — a chain whose relation may change along it. Named steps, like
756        // `simp only [h]` names its rule set. ONE spelling deliberately: a canonical word
757        // stops an argument list (`at_extra_name`), so every alias added here is an ordinary
758        // identifier taken out of a user's hands — and `chain`/`compose` are ordinary words.
759        "calc" => Some("calc"),
760        // `by_rule R` — one step, by the name of the rule that takes it.
761        "by_rule" | "byrule" => Some("by_rule"),
762        "have" | "note" | "observe" => Some("have"),
763        "refine" | "partially" => Some("refine"),
764        _ => None,
765    }
766}
767
768/// Compile a proof-script string into a composed [`Tactic`] (no user-defined tactics).
769pub fn parse_script(src: &str) -> Result<Tactic, ScriptError> {
770    parse_with_env(src, &TacticEnv::new(), 0)
771}
772
773/// Compile a proof-script string with USER-DEFINED tactics resolved from `env` (M).
774pub fn parse_script_with_env(src: &str, env: &TacticEnv) -> Result<Tactic, ScriptError> {
775    parse_with_env(src, env, 0)
776}
777
778fn parse_with_env(src: &str, env: &TacticEnv, depth: usize) -> Result<Tactic, ScriptError> {
779    let toks = lex(src)?;
780    if toks.is_empty() {
781        return Err(ScriptError("empty script".to_string()));
782    }
783    let mut p = Parser {
784        toks,
785        pos: 0,
786        env: env.clone(),
787        depth,
788    };
789    let t = p.parse_seq()?;
790    if p.pos != p.toks.len() {
791        return Err(ScriptError(format!(
792            "trailing tokens after the script: {:?}",
793            &p.toks[p.pos..]
794        )));
795    }
796    Ok(t)
797}
798
799impl ProofState {
800    /// Parse and run a proof script against this state. The state is unchanged on a
801    /// parse error; a tactic that fails mid-run leaves whatever it had committed.
802    pub fn run_script(&mut self, src: &str) -> Result<&mut Self, ScriptError> {
803        let tactic = parse_script(src)?;
804        tactic(self).map_err(|e| ScriptError(format!("{e:?}")))?;
805        Ok(self)
806    }
807
808    /// Parse and run a proof script that may reference USER-DEFINED tactics from `env` (M).
809    pub fn run_script_with_env(
810        &mut self,
811        src: &str,
812        env: &TacticEnv,
813    ) -> Result<&mut Self, ScriptError> {
814        let tactic = parse_script_with_env(src, env)?;
815        tactic(self).map_err(|e| ScriptError(format!("{e:?}")))?;
816        Ok(self)
817    }
818}
819
820// =============================================================================
821// The certified scripted library (ROOT R6) — a Mathlib-analog seam: theorems
822// proved BY TACTIC SCRIPTS accumulate into a dependency-ordered library, each
823// proved lemma becoming a citable premise for later ones, every step kernel-checked.
824// =============================================================================
825
826/// One theorem of a scripted library: proved from its own `premises` plus the
827/// conclusions of the theorems it `cites`, by running `script` to a kernel-checked
828/// proof. The unit the [`prove_scripted_library`] driver discharges in citation order.
829pub struct ScriptedTheorem {
830    pub name: String,
831    pub premises: Vec<ProofExpr>,
832    pub goal: ProofExpr,
833    /// An English-esque proof script (see [`parse_script`]).
834    pub script: String,
835    /// Names of earlier theorems whose conclusions this proof relies on.
836    pub cites: Vec<String>,
837    /// `[simp]`-tagged: once proved, this conclusion joins the simp pool and
838    /// is in scope for every LATER theorem's `simp` even without a citation.
839    pub simp: bool,
840}
841
842/// Discharge a library of scripted theorems in citation order, on a shared `axioms`
843/// base. Each theorem is proved by its [`ScriptedTheorem::script`] from its premises,
844/// the axioms, and the conclusions of the theorems it cites (already proved); a proved
845/// conclusion becomes a citable lemma for later theorems — the scraped-Euclid-graph
846/// discipline, now driven by tactic scripts. Results come back in INPUT order.
847pub fn prove_scripted_library(
848    axioms: &[ProofExpr],
849    theorems: &[ScriptedTheorem],
850) -> Vec<LibraryResult> {
851    // `citation_order` works off names + cites; stub the rest.
852    let stubs: Vec<LibraryTheorem> = theorems
853        .iter()
854        .map(|t| LibraryTheorem {
855            name: t.name.clone(),
856            premises: Vec::new(),
857            goal: t.goal.clone(),
858            cites: t.cites.clone(),
859        })
860        .collect();
861
862    let mut proved: HashMap<String, ProofExpr> = HashMap::new();
863    let mut by_name: HashMap<String, LibraryResult> = HashMap::new();
864    // Conclusions of proved `[simp]`-tagged theorems, in proof order: in scope
865    // for every later theorem without an explicit citation.
866    let mut simp_pool: Vec<ProofExpr> = Vec::new();
867
868    for &i in &citation_order(&stubs) {
869        let t = &theorems[i];
870        let mut premises = axioms.to_vec();
871        premises.extend(t.premises.iter().cloned());
872        for cite in &t.cites {
873            if let Some(goal) = proved.get(cite) {
874                premises.push(goal.clone());
875            }
876        }
877        for lemma in &simp_pool {
878            if !premises.contains(lemma) {
879                premises.push(lemma.clone());
880            }
881        }
882
883        let mut st = ProofState::start(premises, t.goal.clone());
884        let (verified, error) = match st.run_script(&t.script).err() {
885            Some(e) => (false, Some(e.0)),
886            None => match st.qed() {
887                Ok(vp) => (vp.verified, vp.verification_error),
888                Err(e) => (false, Some(format!("{e:?}"))),
889            },
890        };
891        if verified {
892            proved.insert(t.name.clone(), t.goal.clone());
893            if t.simp {
894                simp_pool.push(t.goal.clone());
895            }
896        }
897        by_name.insert(
898            t.name.clone(),
899            LibraryResult {
900                name: t.name.clone(),
901                verified,
902                verification_error: error,
903            },
904        );
905    }
906
907    theorems
908        .iter()
909        .map(|t| {
910            by_name
911                .remove(&t.name)
912                .expect("every theorem produces a result")
913        })
914        .collect()
915}