deduxit 0.5.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

use super::notation::TEXT;
use super::{Sequent, TermId};
use std::fmt::{Display, Formatter, Result as FmtResult};

/// A formula of a sequent, as a value that `Display` prints in one-sided
/// notation. [`Sequent::formula`] returns one.
#[derive(Clone, Copy, Debug)]
pub struct Formula<'a> {
    /// The sequent whose arena and atom names the formula lives in.
    sequent: &'a Sequent,
    /// The formula's root term.
    id: TermId,
}

/// One stop of the walk over a formula that the crate's printers follow,
/// with what they need to place brackets.
#[derive(Clone, Copy, Debug)]
pub(crate) enum Stop<T> {
    /// A subformula is reached, before anything below it. The flag says
    /// whether it stands inside another formula, where a binary one is
    /// written in brackets. The formula the walk starts on has the flag
    /// the walk was given.
    Enter(T, bool),
    /// The place between the two subformulas of a binary formula.
    Between(T),
    /// A formula with subformulas is left, after the last of them, with
    /// the flag it was entered with.
    Exit(T, bool),
}

/// What a walk has yet to do with a formula.
#[derive(Clone, Copy, Debug)]
enum Step<T> {
    /// Enter it.
    Enter(T, bool),
    /// Its first subformula is done: go on to the second.
    Second(T, bool),
    /// Its last subformula is done: leave it.
    Exit(T, bool),
}

/// How many pending steps a walk holds before it allocates. A walk holds
/// about one for each formula it is inside of, so an ordinary formula is
/// written without an allocation.
const INLINE: usize = 16;

/// The stops of a formula in the order it is written: every subformula
/// when it is reached, a binary one again between its two subformulas,
/// and a compound one once more when it is left.
///
/// The walk keeps the formulas it is inside of in a stack of its own, so
/// a formula of any depth takes no more of the caller's stack than a
/// literal does.
pub(crate) struct Stops<T, F> {
    /// The first pending steps, the next one last.
    inline: [Step<T>; INLINE],
    /// How many entries of `inline` are pending.
    len: usize,
    /// The pending steps beyond `inline`, the next one last.
    spilled: Vec<Step<T>>,
    /// Returns the first and the second subformula of a formula, each if
    /// there is one, in the order they are written.
    operands: F,
}

impl<T: Copy, F: Fn(T) -> (Option<T>, Option<T>)> Stops<T, F> {
    /// Returns the walk over the formula `root`, whose subformulas are
    /// what `operands` returns; `nested` is the flag `root` is entered
    /// with.
    pub(crate) fn new(root: T, nested: bool, operands: F) -> Self {
        Self {
            inline: [Step::Enter(root, nested); INLINE],
            len: 1,
            spilled: Vec::new(),
            operands,
        }
    }

    /// Adds a step to take before the pending ones.
    fn push(&mut self, step: Step<T>) {
        if self.len < INLINE {
            self.inline[self.len] = step;
            self.len += 1;
        } else {
            self.spilled.push(step);
        }
    }
}

impl<T: Copy, F: Fn(T) -> (Option<T>, Option<T>)> Iterator for Stops<T, F> {
    type Item = Stop<T>;

    /// Returns the next stop, or `None` once the formula is left.
    fn next(&mut self) -> Option<Stop<T>> {
        let step = match self.spilled.pop() {
            Some(step) => step,
            None => {
                self.len = self.len.checked_sub(1)?;
                self.inline[self.len]
            }
        };
        Some(match step {
            Step::Enter(formula, nested) => {
                match (self.operands)(formula) {
                    (Some(first), Some(_)) => {
                        self.push(Step::Second(formula, nested));
                        self.push(Step::Enter(first, true));
                    }
                    (Some(only), None) | (None, Some(only)) => {
                        self.push(Step::Exit(formula, nested));
                        self.push(Step::Enter(only, true));
                    }
                    (None, None) => {}
                }
                Stop::Enter(formula, nested)
            }
            Step::Second(formula, nested) => {
                self.push(Step::Exit(formula, nested));
                if let (_, Some(second)) = (self.operands)(formula) {
                    self.push(Step::Enter(second, true));
                }
                Stop::Between(formula)
            }
            Step::Exit(formula, nested) => Stop::Exit(formula, nested),
        })
    }
}

/// One stop of a [`Walk`] over a formula, in the order the formula is
/// written.
///
/// A literal or a unit is one `Enter`. A formula with operands is an
/// `Enter`, its first operand, a `Between` before each further operand,
/// and an `Exit` after the last.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Visit<T> {
    /// A formula is reached, before anything below it.
    Enter(T),
    /// The place before an operand of the formula: the number is the
    /// operand's index, counted from 0, so 1 is the second operand of a
    /// binary formula.
    Between(T, u32),
    /// A formula with operands is left, after the last of them.
    Exit(T),
}

/// The stops of a formula in the order it is written (see [`Visit`]),
/// returned by [`Sequent::walk`] and
/// [`Reading::walk`](crate::linear::Reading::walk).
///
/// Use it to print a formula in a syntax of your own. The walk keeps the
/// formulas it is inside of in a stack of its own, so a printer that
/// follows it takes no more of its caller's stack for a formula of any
/// depth than for a literal.
pub struct Walk<'a, T> {
    /// The stops with the flags the crate's printers place brackets by.
    stops: Stops<T, Operands<'a, T>>,
}

/// Returns the first and the second operand of a formula, each if there is
/// one.
type Operands<'a, T> = Box<dyn Fn(T) -> (Option<T>, Option<T>) + 'a>;

impl<'a, T: Copy> Walk<'a, T> {
    /// Returns the walk over the formula `root`, whose operands are what
    /// `operands` returns.
    pub(crate) fn new(root: T, operands: impl Fn(T) -> (Option<T>, Option<T>) + 'a) -> Self {
        Self {
            stops: Stops::new(root, false, Box::new(operands)),
        }
    }
}

impl<T: Copy> Iterator for Walk<'_, T> {
    type Item = Visit<T>;

    /// Returns the next stop, or `None` once the formula is left.
    fn next(&mut self) -> Option<Visit<T>> {
        Some(match self.stops.next()? {
            Stop::Enter(formula, _) => Visit::Enter(formula),
            Stop::Between(formula) => Visit::Between(formula, 1),
            Stop::Exit(formula, _) => Visit::Exit(formula),
        })
    }
}

impl<T> std::fmt::Debug for Walk<'_, T> {
    /// Writes the walk's name alone: its stack is no part of what it is.
    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
        f.write_str("Walk")
    }
}

impl Sequent {
    /// Returns the walk over the formula rooted at `id`, which must belong
    /// to this sequent: the stops a printer of the formula in another
    /// syntax follows. Each stop names a term that [`Sequent::term`]
    /// returns.
    ///
    /// # Examples
    ///
    #[cfg_attr(feature = "parse", doc = "```")]
    #[cfg_attr(not(feature = "parse"), doc = "```ignore")]
    /// use deduxit::linear::sequents::Visit;
    /// use deduxit::linear::{Sequent, Term};
    ///
    /// let sequent: Sequent = "⊢ a ⊗ !b".parse().unwrap();
    /// let mut out = String::new();
    /// for visit in sequent.walk(sequent.roots()[0]) {
    ///     match visit {
    ///         Visit::Enter(id) => match sequent.term(id) {
    ///             Term::Atom(a) => out += sequent.atom_name(a),
    ///             Term::Tensor(..) => out += "(",
    ///             Term::Bang(_) => out += "!",
    ///             _ => unreachable!(),
    ///         },
    ///         Visit::Between(..) => out += " * ",
    ///         Visit::Exit(id) if sequent.term(id).kind().arity() == 2 => out += ")",
    ///         Visit::Exit(_) => {}
    ///     }
    /// }
    /// assert_eq!(out, "(a * !b)");
    /// ```
    ///
    /// # Panics
    ///
    /// The walk panics if `id` is past the end of the arena, as an id of
    /// another sequent can be.
    pub fn walk(&self, id: TermId) -> Walk<'_, TermId> {
        debug_assert!(id.index() < self.terms.len());
        Walk::new(id, |k| self.term(k).operands())
    }

    /// Returns the formula rooted at `id`, which must belong to this
    /// sequent, as a value that prints it.
    ///
    /// # Panics
    ///
    /// Printing it panics if `id` is past the end of the arena, as an id
    /// of another sequent can be.
    pub fn formula(&self, id: TermId) -> Formula<'_> {
        debug_assert!(id.index() < self.terms.len());
        Formula { sequent: self, id }
    }
}

impl Display for Formula<'_> {
    /// Writes the formula with brackets around every binary subformula and
    /// every quantifier inside another formula.
    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
        TEXT.term(f, self.sequent, self.id, false)
    }
}

impl Display for Sequent {
    /// Writes the sequent one-sided: `⊢` followed by its formulas,
    /// separated by commas.
    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
        TEXT.one_sided(f, self)
    }
}