Skip to main content

deduxit/linear/proofs/interactive/
invert.rs

1// deduxit © Fabian Lukas Grubmüller 2026
2// Licensed under the EUPL
3
4//! The invertible rules, applied by the session itself.
5//!
6//! A rule is invertible when its premises are provable whenever its
7//! conclusion is. Applying it never turns a provable goal into an
8//! unprovable one, so a session may take such steps without being asked,
9//! as the asynchronous phase of a focused search does.
10
11use super::expand::formula_at;
12use super::{GoalId, Interactive, Step, StepError, Witness};
13use crate::limits::{Limits, Phase, Refusal};
14use crate::linear::occurrences::{Member, OccId};
15use crate::linear::proofs::derivation::Inference;
16use crate::linear::proofs::multiset::Multiset;
17use crate::linear::proofs::{Named, Rule};
18use crate::linear::sequents::Kind;
19
20/// Whether a session takes steps of its own: a plain value a front end
21/// keeps with its other settings.
22///
23/// # JSON
24///
25/// With the feature `serialize`, `{"invertible": false}`. A missing field
26/// takes its default, and a misspelt one is refused.
27///
28/// Needs the cargo feature `interactive` (on by default).
29#[non_exhaustive]
30#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
31#[cfg_attr(
32    feature = "serialize",
33    derive(serde::Serialize, serde::Deserialize),
34    serde(default, deny_unknown_fields)
35)]
36pub struct Options {
37    /// Whether a front end applies every invertible rule
38    /// ([`Interactive::invert`]) to the goals each step opens and to the
39    /// sequent a session starts from.
40    pub invertible: bool,
41}
42
43impl Options {
44    /// Off, so that every step a newcomer sees is one they took, until
45    /// they ask for the invertible rules.
46    pub const DEFAULT_INVERTIBLE: bool = false;
47
48    /// Returns the options with another [`invertible`](Self::invertible).
49    #[must_use]
50    pub const fn with_invertible(self, invertible: bool) -> Self {
51        Self { invertible }
52    }
53}
54
55impl Default for Options {
56    /// Returns the options with
57    /// [`DEFAULT_INVERTIBLE`](Self::DEFAULT_INVERTIBLE).
58    fn default() -> Self {
59        Self {
60            invertible: Self::DEFAULT_INVERTIBLE,
61        }
62    }
63}
64
65/// What [`Interactive::invert`] did.
66///
67/// Needs the cargo feature `interactive` (on by default).
68#[non_exhaustive]
69#[derive(Clone, Debug, PartialEq, Eq)]
70pub struct Inverted {
71    /// How many steps it took. Each is an ordinary step of the session,
72    /// which [`undo`](Interactive::undo) takes back one at a time, the last
73    /// first.
74    pub steps: usize,
75    /// The goals it left open, from left to right: each goal it was given
76    /// and took no step on, and each goal its steps opened and it took no
77    /// step on.
78    pub open: Vec<GoalId>,
79    /// `Ok` when no invertible rule applies to any goal of
80    /// [`open`](Self::open). Otherwise the memory bound stopped it, and the
81    /// steps it took stand.
82    pub finished: Result<(), Refusal>,
83}
84
85impl Interactive {
86    /// Applies the rules invertible in the session's mode
87    /// ([`is_invertible`](Self::is_invertible)) to an open goal, and then
88    /// to every goal those steps open, until none applies.
89    ///
90    /// On each goal it takes a rule that closes the goal (`⊤`, the axiom,
91    /// `1`) first, and otherwise the rule on the first formula that has
92    /// one. Each application is an ordinary step. It always ends, since
93    /// every premise of these rules has fewer connectives, units and
94    /// literals than its conclusion. The bytes of the inferences it adds
95    /// are bounded by `limits.memory_bytes`: at the bound it stops, and
96    /// the steps it took stand ([`Inverted::finished`]).
97    ///
98    /// # Errors
99    ///
100    /// [`StepError::NoGoal`] for a goal that is not open.
101    pub fn invert(&mut self, goal: GoalId, limits: &Limits) -> Result<Inverted, StepError> {
102        self.goal(goal)?;
103        Ok(self.invert_goals(vec![goal], limits))
104    }
105
106    /// Applies the invertible rules to every open goal in turn, as
107    /// [`invert`](Self::invert) does to one, all within one memory bound.
108    pub fn invert_all(&mut self, limits: &Limits) -> Inverted {
109        let goals = self.goals().collect();
110        self.invert_goals(goals, limits)
111    }
112
113    /// Returns whether a step on a sequent of this session's forest (an
114    /// open goal, or an inference's conclusion) applies a rule invertible
115    /// in the session's mode, and is a valid step there.
116    ///
117    /// The invertible rules are:
118    /// - in every mode `⅋`, `⊥`, `&` and `⊤`, under any name the
119    ///   intuitionistic or the ordered reading gives them (`⊸R`, `⊗L`,
120    ///   `&R`, `⊕L`, `1L`, `⊤R`, `0L`, `\R`, `/R`), and `∀` (`∀R`, `∃L`);
121    /// - `!` when every other formula is a `?` formula (`!R` when every
122    ///   hypothesis is a `!`);
123    /// - `1` alone, the axiom on a literal and its dual alone, and `⊗`
124    ///   alone, with no context to split.
125    ///
126    /// No `?` rule is among them: dereliction and weakening are not
127    /// invertible, and contraction is, but applying it never ends.
128    pub fn is_invertible(&self, sequent: &[Member], step: &Step) -> bool {
129        let sequent: Vec<OccId> = sequent.iter().map(|&m| self.occurrence(m)).collect();
130        let Ok(left) = step.left_positions(sequent.len()) else {
131            return false;
132        };
133        let Ok(o) = formula_at(&sequent, step.position) else {
134            return false;
135        };
136        let rule = self.invertible_rule(&sequent, self.non_quests(&sequent), step.position);
137        if !left.is_empty() || rule != Some(step.rule.rule) {
138            return false;
139        }
140        let reading = self.reading();
141        let named = Named::applied(step.rule.rule, reading.as_ref(), o);
142        (step.rule.side.is_none() || step.rule == named)
143            && self
144                .expand(reading.as_ref(), &sequent, step.position, named, &[])
145                .is_ok()
146    }
147
148    /// Applies the invertible rules to the goals, depth first, within the
149    /// memory bound.
150    fn invert_goals(&mut self, goals: Vec<GoalId>, limits: &Limits) -> Inverted {
151        let mut todo: Vec<GoalId> = goals.into_iter().rev().collect();
152        let (mut steps, mut open) = (0, Vec::new());
153        // The bytes of the inferences added: per premise, an inference
154        // and its sequent's members. The sum saturates, but the bound
155        // stops the run long before that.
156        let mut held = 0u64;
157        while let Some(goal) = todo.pop() {
158            let Some((position, rule, premises)) = self.invertible_step(goal) else {
159                open.push(goal);
160                continue;
161            };
162            let needed = premises.iter().fold(0u64, |sum, premise| {
163                let members = premise.as_slice().len() * size_of::<Member>();
164                sum.saturating_add((size_of::<Inference>() + members) as u64)
165            });
166            if let Some(limit) = limits.memory_bytes
167                && held.saturating_add(needed) > limit
168            {
169                open.push(goal);
170                open.extend(todo.into_iter().rev());
171                return Inverted {
172                    steps,
173                    open,
174                    finished: Err(Refusal::Memory {
175                        phase: Phase::View,
176                        limit_bytes: limit,
177                        needed_bytes: Some(held.saturating_add(needed)),
178                    }),
179                };
180            }
181            held = held.saturating_add(needed);
182            let premises = if self.fo.is_some() {
183                match self.framed_premises(goal, position, rule.rule, &[], &Witness::Open) {
184                    Ok(premises) => premises,
185                    // Past the eigenvariables a `u32` numbers, or past
186                    // the session's bound on terms: the goal stays open.
187                    Err(_) => {
188                        open.push(goal);
189                        continue;
190                    }
191                }
192            } else {
193                premises.into_iter().map(Multiset::into_members).collect()
194            };
195            let opened = self.record(goal, position, rule, premises);
196            steps += 1;
197            todo.extend(opened.into_iter().rev());
198        }
199        Inverted {
200            steps,
201            open,
202            finished: Ok(()),
203        }
204    }
205
206    /// Returns the invertible step to take on an open goal, with its
207    /// premises, or `None` when no invertible rule applies. A step that
208    /// closes the goal comes first, and otherwise the first position's.
209    fn invertible_step(&self, goal: GoalId) -> Option<(usize, Named, Vec<Multiset>)> {
210        let sequent = self.open(goal).ok()?;
211        let reading = self.reading();
212        let closes = |rule: Rule| matches!(rule, Rule::Top | Rule::Ax | Rule::One);
213        let non_quests = self.non_quests(&sequent);
214        for closing in [true, false] {
215            for position in 0..sequent.len() {
216                let Some(rule) = self.invertible_rule(&sequent, non_quests, position) else {
217                    continue;
218                };
219                if closes(rule) != closing {
220                    continue;
221                }
222                let named = Named::applied(rule, reading.as_ref(), sequent[position]);
223                // A first-order axiom closes equal instances only: binding
224                // an open witness is a choice, not an invertible step.
225                if rule == Rule::Ax
226                    && let Some(q) = &self.fo
227                    && let Ok(&[x, y]) = self.goal(goal)
228                    && !q.same_atom(&self.forest, x, y)
229                {
230                    continue;
231                }
232                // The reading may still refuse the step: a premise without
233                // one formula on the right of ⊢, or without an antecedent.
234                if let Ok(premises) = self.expand(reading.as_ref(), &sequent, position, named, &[])
235                {
236                    return Some((position, named, premises));
237                }
238            }
239        }
240        None
241    }
242
243    /// Returns how many formulas of a sequent are not `?` formulas.
244    fn non_quests(&self, sequent: &[OccId]) -> usize {
245        (sequent.iter())
246            .filter(|&&o| self.forest.kind(o) != Kind::Quest)
247            .count()
248    }
249
250    /// Returns the invertible rule that acts on the formula at a position
251    /// of a sequent when its condition holds, or `None`. `non_quests` of
252    /// the sequent's formulas are not `?` formulas. Whether the mode and
253    /// the reading allow the step is for [`expand`](Self::expand) to say.
254    fn invertible_rule(
255        &self,
256        sequent: &[OccId],
257        non_quests: usize,
258        position: usize,
259    ) -> Option<Rule> {
260        let f = &self.forest;
261        let o = sequent[position];
262        let alone = sequent.len() == 1;
263        match f.kind(o) {
264            Kind::Par => Some(Rule::Par),
265            Kind::Bot => Some(Rule::Bot),
266            Kind::With => Some(Rule::With),
267            Kind::Top => Some(Rule::Top),
268            // The `!` itself is the only formula that is not a `?`.
269            Kind::Bang => (non_quests == 1).then_some(Rule::Promotion),
270            Kind::One => alone.then_some(Rule::One),
271            Kind::Tensor => alone.then_some(Rule::Tensor),
272            Kind::Atom | Kind::DualAtom => match sequent {
273                &[x, y] if f.dual_literals(x, y) => Some(Rule::Ax),
274                _ => None,
275            },
276            Kind::Forall => Some(Rule::Forall),
277            Kind::Plus | Kind::Zero | Kind::Quest | Kind::Exists => None,
278        }
279    }
280}
281
282#[cfg(all(test, feature = "parse"))]
283mod tests {
284    use super::*;
285    use crate::linear::fragment::Mode;
286    use crate::linear::search::generate::{self, IllRules, Rng, Rules};
287    use crate::linear::search::{self, Verdict};
288    use crate::linear::{Sequent, ViewOptions};
289
290    /// Starts a session of `input`, read in the mode's order.
291    fn start(input: &str, mode: Mode) -> Interactive {
292        let sequent = Sequent::parse_ordered(input, mode.order(), &Limits::default())
293            .unwrap_or_else(|e| panic!("{input:?}: {e}"));
294        Interactive::new(&sequent, mode).unwrap()
295    }
296
297    /// The rules of the steps a session took, in the arena's order.
298    fn taken(state: &Interactive) -> Vec<String> {
299        (state.inferences.iter())
300            .filter(|i| i.rule.rule != Rule::Open)
301            .map(|i| i.rule.to_string())
302            .collect()
303    }
304
305    /// Each invertible rule applies under its condition and only then. A
306    /// rule that closes the goal goes first, each application is a step
307    /// that undo takes back, and the reading names the rules.
308    #[test]
309    fn the_invertible_rules_under_their_conditions() {
310        let classical = Mode::CLASSICAL;
311        for (input, mode, rules) in [
312            ("|- a par ~a", classical, &["⅋", "ax"][..]),
313            ("|- bot, 1", classical, &["⊥", "1"]),
314            ("|- a & b, top", classical, &["⊤"]),
315            ("|- (a par ~a) & 1", classical, &["&", "⅋", "1", "ax"]),
316            ("|- !(a par ~a), ?b", classical, &["!", "⅋"]),
317            ("|- 1 * 1", classical, &["⊗", "1", "1"]),
318            ("|- 1, a", classical, &[]),
319            ("|- !a, b", classical, &[]),
320            ("|- a * b, c", classical, &[]),
321            ("|- a, ~a, b", classical.with_affine(), &[]),
322            ("|- a, ?b", classical, &[]),
323            ("|- a + b, ~a", classical.with_mix(), &[]),
324            ("a * b |- b * a", Mode::INTUITIONISTIC, &["⊗L"]),
325            ("!a |- !(a & a)", Mode::INTUITIONISTIC, &["!R", "&R"]),
326            ("|- a -o (b -o a * b)", Mode::INTUITIONISTIC, &["⊸R", "⊸R"]),
327            ("|- 1 * 1", Mode::INTUITIONISTIC, &["⊗R", "1R", "1R"]),
328            ("b |- (a \\ a) \\ b", Mode::LAMBEK, &["\\R"]),
329            (
330                "|- (a \\ a) * (b \\ b)",
331                Mode::LAMBEK.with_empty_antecedents(),
332                &["⊗R", "\\R", "\\R", "ax", "ax"],
333            ),
334            (
335                "|- (a \\ a) * (b \\ b)",
336                Mode::CYCLIC,
337                &["⊗", "⅋", "⅋", "ax", "ax"],
338            ),
339            ("a * b |- a * b", Mode::CYCLIC, &["⅋"]),
340        ] {
341            let mut state = start(input, mode);
342            let before = state.derivation().unwrap().to_string();
343            let inverted = state.invert_all(&Limits::default());
344            assert_eq!(taken(&state), rules, "{input} in {mode}");
345            assert_eq!(
346                (inverted.steps, state.steps(), inverted.finished.clone()),
347                (rules.len(), rules.len(), Ok(())),
348                "{input} in {mode}"
349            );
350            let mut open = inverted.open.clone();
351            open.sort_unstable();
352            assert_eq!(open, state.goals().collect::<Vec<_>>());
353            assert_eq!(state.invert_all(&Limits::default()).steps, 0);
354            if state.is_complete() {
355                state.proof(&Limits::default(), |_| false).unwrap();
356            }
357            for _ in 0..rules.len() {
358                state.undo().unwrap();
359            }
360            assert_eq!(state.derivation().unwrap().to_string(), before);
361        }
362        let mut state = start("|- a par b", classical);
363        state
364            .apply(GoalId::new(0), &Step::new(0, Rule::Par))
365            .unwrap();
366        assert_eq!(
367            state.invert(GoalId::new(0), &Limits::default()),
368            Err(StepError::NoGoal {
369                goal: GoalId::new(0)
370            })
371        );
372    }
373
374    /// Returns how many connectives, units and literals a sequent's
375    /// formulas have.
376    fn weight(forest: &crate::linear::Forest, sequent: &[Member]) -> usize {
377        let mut todo: Vec<OccId> = sequent.iter().map(|m| m.occ()).collect();
378        let mut weight = 0;
379        while let Some(o) = todo.pop() {
380            weight += 1;
381            todo.extend(forest.left(o));
382            todo.extend(forest.right(o));
383        }
384        weight
385    }
386
387    /// On generated provable sequents of every mode:
388    /// - the search proves every goal the invertible rules leave;
389    /// - every premise is lighter than its conclusion, and at the end no
390    ///   invertible rule is left to apply;
391    /// - the search closing the rest makes a proof the checker accepts.
392    #[test]
393    fn inverting_keeps_every_proof_and_ends() {
394        let mut cases: Vec<(String, Mode)> = Vec::new();
395        for (i, rules) in Rules::ALL.into_iter().enumerate() {
396            let mut rng = Rng::new(3800 + i as u64);
397            let base = if rules.mix {
398                Mode::CLASSICAL.with_mix()
399            } else {
400                Mode::CLASSICAL
401            };
402            for _ in 0..8 {
403                let budget = 2 + rng.below(10);
404                let text =
405                    generate::sequent(&generate::provable(&mut rng, rules, 3, budget).formulas);
406                cases.push((text.clone(), base));
407                cases.push((text, base.with_affine()));
408            }
409        }
410        for (i, rules) in IllRules::ALL.into_iter().enumerate() {
411            let mut rng = Rng::new(3900 + i as u64);
412            for _ in 0..8 {
413                let budget = 2 + rng.below(10);
414                let ill = generate::ill(&mut rng, rules, 3, budget);
415                let text = generate::two_sided(&ill.hypotheses, &ill.goal);
416                cases.push((text.clone(), Mode::INTUITIONISTIC));
417                cases.push((text, Mode::INTUITIONISTIC.with_affine()));
418            }
419        }
420        let mut rng = Rng::new(3999);
421        for k in 0..60 {
422            let star = k % 2 == 1;
423            let budget = 2 + rng.below(8);
424            let (hypotheses, goal) = generate::lambek(&mut rng, 3, budget, star);
425            let text = generate::lambek_text(&hypotheses, &goal);
426            let lambek = if star {
427                Mode::LAMBEK.with_empty_antecedents()
428            } else {
429                Mode::LAMBEK
430            };
431            cases.push((text.clone(), lambek));
432            cases.push((text, Mode::CYCLIC));
433        }
434        let options = search::Options::default();
435        let limits = Limits::default();
436        let (mut proved, mut steps) = (0, 0);
437        let mut used = std::collections::BTreeMap::<String, usize>::new();
438        for (text, mode) in cases {
439            let sequent = Sequent::parse_ordered(&text, mode.order(), &limits).unwrap();
440            let Ok(outcome) = search::prove(&sequent, mode, &options) else {
441                continue;
442            };
443            if !matches!(outcome.verdict, Verdict::Proved(_)) {
444                continue;
445            }
446            proved += 1;
447            let mut state = Interactive::new(&sequent, mode).unwrap();
448            let inverted = state.invert_all(&limits);
449            assert_eq!(inverted.finished, Ok(()), "{text} in {mode}");
450            assert_eq!(state.invert_all(&limits).steps, 0, "{text} in {mode}");
451            steps += inverted.steps;
452            for inference in state
453                .inferences
454                .iter()
455                .filter(|i| i.rule.rule != Rule::Open)
456            {
457                *used
458                    .entry(format!("{mode}: {}", inference.rule))
459                    .or_default() += 1;
460                let conclusion = weight(&state.forest, &inference.sequent);
461                for premise in &inference.premises {
462                    let premise = &state.inferences[premise.index()].sequent;
463                    assert!(
464                        weight(&state.forest, premise) < conclusion,
465                        "{text} in {mode}"
466                    );
467                }
468            }
469            for goal in inverted.open {
470                let members = state.goal(goal).unwrap();
471                let target = search::Goal::new(state.forest(), members).unwrap();
472                let verdict = search::prove_goal(target, mode, &options, &limits, |_| false)
473                    .unwrap()
474                    .verdict;
475                assert!(
476                    matches!(verdict, Verdict::Proved(_)),
477                    "{text} in {mode}: goal {} is {verdict:?}",
478                    goal.get()
479                );
480            }
481            for (goal, closed) in
482                state.close_all(&options, &ViewOptions::default(), &limits, |_| false)
483            {
484                let closed = closed.unwrap();
485                assert!(
486                    closed.grafted.is_ok(),
487                    "{text} in {mode}: goal {}",
488                    goal.get()
489                );
490            }
491            assert!(state.is_complete(), "{text} in {mode}");
492            state.proof(&limits, |_| false).unwrap();
493        }
494        assert!(
495            proved >= 500 && steps >= 600,
496            "{proved} proved, {steps} steps"
497        );
498        // Every rule fired in every classical mode, and the multiplicatives
499        // in every other.
500        for (mode, rules) in [
501            ("classical", &["⅋", "⊥", "&", "⊤", "!", "1", "⊗", "ax"][..]),
502            (
503                "classical with Mix",
504                &["⅋", "⊥", "&", "⊤", "!", "1", "⊗", "ax"],
505            ),
506            (
507                "classical affine",
508                &["⅋", "⊥", "&", "⊤", "!", "1", "⊗", "ax"],
509            ),
510            (
511                "intuitionistic",
512                &["⊸R", "⊗L", "&R", "⊕L", "1L", "⊤R", "0L", "!R", "1R", "ax"],
513            ),
514            (
515                "intuitionistic affine",
516                &["⊸R", "⊗L", "&R", "⊕L", "1L", "⊤R", "0L", "!R", "1R", "ax"],
517            ),
518            ("Lambek", &["\\R", "/R", "⊗L", "ax"]),
519            ("Lambek with empty antecedents", &["\\R", "/R", "⊗L", "ax"]),
520            ("cyclic", &["⅋", "ax"]),
521        ] {
522            for rule in rules {
523                assert!(
524                    used.contains_key(&format!("{mode}: {rule}")),
525                    "{mode}: {rule}"
526                );
527            }
528        }
529    }
530
531    /// A run past the memory bound stops there, its steps ordinary ones
532    /// that undo takes back, and the same run without the bound ends.
533    #[test]
534    fn inverting_stops_at_the_memory_bound() {
535        let input = "|- a & a, a & a, a & a, a & a, a & a, a & a";
536        let mut state = start(input, Mode::CLASSICAL);
537        let bounded = Limits::default().with_memory_bytes(Some(4096));
538        let inverted = state.invert_all(&bounded);
539        assert!(
540            matches!(
541                inverted.finished,
542                Err(Refusal::Memory {
543                    limit_bytes: 4096,
544                    needed_bytes: Some(needed),
545                    ..
546                }) if needed > 4096
547            ),
548            "{inverted:?}"
549        );
550        assert!(0 < inverted.steps && inverted.steps < 63, "{inverted:?}");
551        let mut open = inverted.open.clone();
552        open.sort_unstable();
553        assert_eq!(open, state.goals().collect::<Vec<_>>());
554        while state.undo().is_some() {}
555        let inverted = state.invert_all(&Limits::default().with_memory_bytes(None));
556        assert_eq!((inverted.steps, inverted.open.len()), (63, 64));
557    }
558}