deduxit 0.4.0

A collection of logic suites: decides, checks, proves step by step and exports sequents of linear logic and of classical, intuitionistic and minimal propositional logic, with checked proofs, Kripke countermodels and Rocq certificates.
Documentation
// deduxit © Fabian Lukas Grubmüller 2026
// Licensed under the EUPL

//! The inverse method's tests.

use crate::linear::search::generate::{self, IllRules, Rng, Rules};
use crate::linear::search::reference::{self, Answer};
use crate::linear::search::{Engine, Options, Verdict, prove_within};
use crate::{
    Limits,
    linear::{Mode, Sequent},
};

/// Decides a sequent with the inverse method within `polls` polls of its
/// stop.
fn decide(text: &str, mode: Mode, polls: u64) -> Verdict {
    let sequent: Sequent = text.parse().unwrap();
    let options = Options::default().with_engine(Some(Engine::Inverse));
    let mut left = polls;
    let stop = |_| {
        left = left.saturating_sub(1);
        left == 0
    };
    prove_within(&sequent, mode, &options, &Limits::default(), stop)
        .unwrap()
        .verdict
}

/// The inverse method proves and refutes a few sequents of each
/// fragment.
#[test]
fn decides_small_sequents() {
    for (text, provable) in [
        ("|- a, ~a", true),
        ("|- a * b, ~a, ~b", true),
        ("|- a * b, ~a", false),
        ("|- a + b, ~a", true),
        ("|- a & b, ~a", false),
        ("|- a & b, ~a + ~b", true),
        ("|- top, a", true),
        ("|- 1", true),
        ("|- bot", false),
        ("|- bot, 1", true),
        ("|- a par ~a", true),
        ("|- ?~a, !a", true),
        ("|- ?~a, a * a", true),
        // One kept sequent, the empty one, in both holes of one rule.
        ("|- ?a, ?~a, bot * bot", true),
    ] {
        let verdict = decide(text, Mode::CLASSICAL, 1 << 20);
        match (provable, &verdict) {
            (true, Verdict::Proved(_)) | (false, Verdict::Unprovable(_)) => {}
            _ => panic!("{text}: {verdict:?}"),
        }
    }
}

/// How many polls of its stop the inverse method gets on a generated
/// sequent. A poll comes at each sequent taken up and after about a
/// thousand rule applications.
const POLLS: u64 = 1 << 10;

/// Whether two verdicts contradict each other: a proof against a
/// refutation.
fn contradict(a: &Verdict, b: &Verdict) -> bool {
    matches!(
        (a, b),
        (Verdict::Proved(_), Verdict::Unprovable(_)) | (Verdict::Unprovable(_), Verdict::Proved(_))
    )
}

/// Whether a verdict contradicts the reference's answer.
fn against(verdict: &Verdict, reference: Answer) -> bool {
    match verdict {
        Verdict::Proved(_) => reference == Answer::Unprovable,
        Verdict::Unprovable(_) => reference == Answer::Proved,
        Verdict::Unknown(_) => false,
    }
}

/// Judges one generated sequent, and returns whether the inverse method
/// decided it.
///
/// The inverse method must not contradict the focused engine, run within
/// the copies the generator gives, nor the reference. Without
/// exponentials it must decide.
fn judge(text: &str, mode: Mode, copies: u32, reference: Answer, exponentials: bool) -> bool {
    let inverse = decide(text, mode, POLLS);
    let sequent: Sequent = text.parse().unwrap();
    let engine = if mode.is_intuitionistic() {
        Engine::TwoSided
    } else {
        Engine::Focus
    };
    let options = Options::default()
        .with_engine(Some(engine))
        .with_copies(Some(copies));
    let focused = prove_within(&sequent, mode, &options, &Limits::default(), |_| false)
        .unwrap()
        .verdict;
    assert!(
        !contradict(&inverse, &focused),
        "{text} in {mode} mode: inverse {inverse:?}, focused {focused:?}"
    );
    assert!(
        !against(&inverse, reference),
        "{text} in {mode} mode: inverse {inverse:?}, the reference {reference:?}"
    );
    let decided = !matches!(inverse, Verdict::Unknown(_));
    if !exponentials {
        assert!(decided, "{text} in {mode} mode: {inverse:?}");
    }
    decided
}

/// On generated sequents and their mutants, the inverse method never
/// contradicts the focused engine or the reference. It decides every
/// sequent without exponentials, and at least half of all of them.
///
/// The sequents are classical in every rule set (linear and affine, with
/// Mix where the rules use it) and intuitionistic in every rule set
/// (linear and affine).
#[test]
fn agrees_with_the_focused_engine_and_the_reference() {
    let (mut cases, mut decided) = (0, 0);
    for (i, rules) in Rules::ALL.into_iter().enumerate() {
        let mut rng = Rng::new(500 + i as u64);
        for _ in 0..6 {
            let budget = 2 + rng.below(8);
            let generate::Provable {
                mut formulas,
                copies,
            } = generate::provable(&mut rng, rules, 3, budget);
            let mut all = vec![formulas.clone()];
            if generate::mutate(&mut rng, &mut formulas, 3) {
                all.push(formulas);
            }
            for formulas in &all {
                let text = generate::sequent(formulas);
                let exponentials = text
                    .parse::<Sequent>()
                    .unwrap()
                    .fragment()
                    .has_exponentials();
                for affine in [false, true] {
                    let mut mode = if rules.mix {
                        Mode::CLASSICAL.with_mix()
                    } else {
                        Mode::CLASSICAL
                    };
                    if affine {
                        mode = mode.with_affine();
                    }
                    let answer = reference::classical(formulas, mode, copies);
                    cases += 1;
                    decided += usize::from(judge(&text, mode, copies, answer, exponentials));
                }
            }
        }
    }
    for (i, rules) in IllRules::ALL.into_iter().enumerate() {
        let mut rng = Rng::new(600 + i as u64);
        for _ in 0..6 {
            let budget = 2 + rng.below(8);
            let generate::Ill {
                mut hypotheses,
                mut goal,
                copies,
                ..
            } = generate::ill(&mut rng, rules, 3, budget);
            let mut all = vec![(hypotheses.clone(), goal.clone())];
            if generate::mutate_two_sided(&mut rng, &mut hypotheses, &mut goal, 3) {
                all.push((hypotheses, goal));
            }
            for (hypotheses, goal) in &all {
                let text = generate::two_sided(hypotheses, goal);
                let exponentials = text
                    .parse::<Sequent>()
                    .unwrap()
                    .fragment()
                    .has_exponentials();
                for mode in [Mode::INTUITIONISTIC, Mode::INTUITIONISTIC.with_affine()] {
                    let answer = reference::intuitionistic(hypotheses, goal, mode, copies);
                    cases += 1;
                    decided += usize::from(judge(&text, mode, copies, answer, exponentials));
                }
            }
        }
    }
    eprintln!("decided {decided} of {cases}");
    assert!(2 * decided >= cases, "decided {decided} of {cases}");
}

/// A goal with two members that no sequent of a proof holds together is
/// refused, since the search drops every sequent that holds such a pair.
/// A goal whose members can stand together is decided.
#[test]
fn refuses_an_incoherent_goal() {
    let options = Options::default().with_engine(Some(Engine::Inverse));
    let goal_of = |text: &str, members: &[u32], mode: Mode| {
        let forest = crate::linear::occurrences::Forest::new(&text.parse().unwrap()).unwrap();
        let members: Vec<_> = members
            .iter()
            .map(|&m| crate::linear::Member::new(m))
            .collect();
        let goal = crate::linear::search::Goal::new(&forest, &members).unwrap();
        crate::linear::search::prove_goal(goal, mode, &options, &Limits::default(), |_| false)
            .map(|outcome| outcome.verdict)
    };
    // The literals a `⊗` separates, and the two sides of a `&`.
    for (text, members) in [("|- a * ~a", &[1, 2][..]), ("|- a & ~a", &[1, 2])] {
        assert!(matches!(
            goal_of(text, members, Mode::CLASSICAL),
            Err(crate::Error::EngineRefused {
                because: crate::linear::search::NotTaken::Shape,
                ..
            })
        ));
    }
    // `a` of the tensor and `~a` of another root stand together.
    let verdict = goal_of("|- a * b, ~a, ~b", &[1, 3], Mode::CLASSICAL).unwrap();
    assert!(matches!(verdict, Verdict::Proved(_)), "{verdict:?}");
    // A `?` formula twice, as after a contraction, and beside its own
    // subformula, as after a dereliction. Both are goals of a derivation.
    for members in [&[0, 0, 2][..], &[0, 1, 2]] {
        let verdict = goal_of("|- ?~a, a * a", members, Mode::CLASSICAL).unwrap();
        assert!(
            matches!(verdict, Verdict::Proved(_)),
            "{members:?}: {verdict:?}"
        );
    }
}

/// Choices of `⊕` sides that a `0` ends are work the stop is told of,
/// however many there are. `0 ⊗ ((a₀ ⊕ b₀) ⊗ …)` has 2¹⁶ of them, and
/// none is a rule.
#[test]
fn choices_a_zero_ends_are_polled() {
    let mut factors = "(a0 + b0)".to_owned();
    for i in 1..16 {
        factors = format!("((a{i} + b{i}) * {factors})");
    }
    let sequent: Sequent = format!("|- 0 * {factors}").parse().unwrap();
    let options = Options::default().with_engine(Some(Engine::Inverse));
    let mut work = 0;
    let stop = |progress: crate::Progress| {
        work += progress.work;
        false
    };
    prove_within(
        &sequent,
        Mode::CLASSICAL,
        &options,
        &Limits::default(),
        stop,
    )
    .unwrap();
    assert!(work >= 1 << 16, "{work} units");
}