use super::view::{Derivation, InfId, Inference};
use crate::Error;
use crate::limits::{Limits, Refusal, Space};
use crate::linear::occurrences::written::{self, Written};
use crate::linear::occurrences::{Forest, Member, OccId, Side};
use crate::linear::proofs::size::Weights;
use crate::linear::proofs::style::{Drawn, Labels};
use crate::linear::proofs::{Rule, Size, TextOptions};
use std::fmt::{Display, Formatter, Result as FmtResult, Write};
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum ClassicalRule {
Axiom,
TensorLeft,
TensorRight,
ParLeft,
ParRight,
LollipopLeft,
LollipopRight,
OneLeft,
OneRight,
BotLeft,
BotRight,
WithLeft1,
WithLeft2,
WithRight,
PlusLeft,
PlusRight1,
PlusRight2,
TopRight,
ZeroLeft,
BangLeft,
BangRight,
BangContraction,
BangWeakening,
QuestLeft,
QuestRight,
QuestContraction,
QuestWeakening,
ForallLeft,
ForallRight,
ExistsLeft,
ExistsRight,
Mix,
Weakening,
Cut,
NegationLeft,
NegationRight,
Open,
}
impl ClassicalRule {
pub(crate) const ALL: [Self; 37] = {
use ClassicalRule::*;
[
Axiom,
TensorLeft,
TensorRight,
ParLeft,
ParRight,
LollipopLeft,
LollipopRight,
OneLeft,
OneRight,
BotLeft,
BotRight,
WithLeft1,
WithLeft2,
WithRight,
PlusLeft,
PlusRight1,
PlusRight2,
TopRight,
ZeroLeft,
BangLeft,
BangRight,
BangContraction,
BangWeakening,
QuestLeft,
QuestRight,
QuestContraction,
QuestWeakening,
ForallLeft,
ForallRight,
ExistsLeft,
ExistsRight,
Mix,
Weakening,
Cut,
NegationLeft,
NegationRight,
Open,
]
};
const UPRIGHT: [&'static str; 37] = [
"ax", "⊗L", "⊗R", "⅋L", "⅋R", "⊸L", "⊸R", "1L", "1R", "⊥L", "⊥R", "&L_1", "&L_2", "&R",
"⊕L", "⊕R_1", "⊕R_2", "⊤R", "0L", "!L", "!R", "!c", "!w", "?L", "?R", "?c", "?w", "∀L",
"∀R", "∃L", "∃R", "mix", "wk", "cut", "~L", "~R", "",
];
const SUBSCRIPT: [&'static str; 37] = [
"ax", "⊗_L", "⊗_R", "⅋_L", "⅋_R", "⊸_L", "⊸_R", "1_L", "1_R", "⊥_L", "⊥_R", "&_{L1}",
"&_{L2}", "&_R", "⊕_L", "⊕_{R1}", "⊕_{R2}", "⊤_R", "0_L", "!_L", "!_R", "!_c", "!_w",
"?_L", "?_R", "?_c", "?_w", "∀_L", "∀_R", "∃_L", "∃_R", "mix", "wk", "cut", "~_L", "~_R",
"",
];
pub const fn name(self) -> &'static str {
use ClassicalRule::*;
match self {
Axiom => "ax",
TensorLeft => "⊗L",
TensorRight => "⊗R",
ParLeft => "⅋L",
ParRight => "⅋R",
LollipopLeft => "⊸L",
LollipopRight => "⊸R",
OneLeft => "1L",
OneRight => "1R",
BotLeft => "⊥L",
BotRight => "⊥R",
WithLeft1 => "&L₁",
WithLeft2 => "&L₂",
WithRight => "&R",
PlusLeft => "⊕L",
PlusRight1 => "⊕R₁",
PlusRight2 => "⊕R₂",
TopRight => "⊤R",
ZeroLeft => "0L",
BangLeft => "!L",
BangRight => "!R",
BangContraction => "!c",
BangWeakening => "!w",
QuestLeft => "?L",
QuestRight => "?R",
QuestContraction => "?c",
QuestWeakening => "?w",
ForallLeft => "∀L",
ForallRight => "∀R",
ExistsLeft => "∃L",
ExistsRight => "∃R",
Mix => "mix",
Weakening => "wk",
Cut => "cut",
NegationLeft => "~L",
NegationRight => "~R",
Open => "open",
}
}
pub const fn rule(self) -> Option<Rule> {
use ClassicalRule::*;
Some(match self {
Axiom => Rule::Ax,
TensorRight | ParLeft | LollipopLeft => Rule::Tensor,
TensorLeft | ParRight | LollipopRight => Rule::Par,
OneRight | BotLeft => Rule::One,
OneLeft | BotRight => Rule::Bot,
WithRight | PlusLeft => Rule::With,
PlusRight1 | WithLeft1 => Rule::PlusLeft,
PlusRight2 | WithLeft2 => Rule::PlusRight,
TopRight | ZeroLeft => Rule::Top,
BangRight | QuestLeft => Rule::Promotion,
BangLeft | QuestRight => Rule::Dereliction,
BangContraction | QuestContraction => Rule::Contraction,
BangWeakening | QuestWeakening => Rule::Weakening,
ForallRight | ExistsLeft => Rule::Forall,
ExistsRight | ForallLeft => Rule::Exists,
Mix => Rule::Mix,
Weakening => Rule::AffineWeakening,
Cut => Rule::Cut,
Open => Rule::Open,
NegationLeft | NegationRight => return None,
})
}
pub const fn side(self) -> Option<Side> {
use ClassicalRule::*;
match self {
TensorLeft | ParLeft | LollipopLeft | OneLeft | BotLeft | WithLeft1 | WithLeft2
| PlusLeft | ZeroLeft | BangLeft | BangContraction | BangWeakening | QuestLeft
| ForallLeft | ExistsLeft | NegationLeft => Some(Side::Input),
TensorRight | ParRight | LollipopRight | OneRight | BotRight | WithRight
| PlusRight1 | PlusRight2 | TopRight | BangRight | QuestRight | QuestContraction
| QuestWeakening | ForallRight | ExistsRight | NegationRight => Some(Side::Output),
Axiom | Mix | Weakening | Cut | Open => None,
}
}
fn applied(rule: Rule, written: Written) -> Self {
use ClassicalRule::*;
let left = written.side() == Side::Input;
let pick = |input, output| if left { input } else { output };
match rule {
Rule::Forall => pick(ExistsLeft, ForallRight),
Rule::Exists => pick(ForallLeft, ExistsRight),
Rule::Ax => Axiom,
Rule::Tensor if written.is_implication() => LollipopLeft,
Rule::Tensor => pick(ParLeft, TensorRight),
Rule::Par if written.is_implication() => LollipopRight,
Rule::Par => pick(TensorLeft, ParRight),
Rule::One => pick(BotLeft, OneRight),
Rule::Bot => pick(OneLeft, BotRight),
Rule::With => pick(PlusLeft, WithRight),
Rule::PlusLeft => pick(WithLeft1, PlusRight1),
Rule::PlusRight => pick(WithLeft2, PlusRight2),
Rule::Top => pick(ZeroLeft, TopRight),
Rule::Promotion => pick(QuestLeft, BangRight),
Rule::Dereliction => pick(BangLeft, QuestRight),
Rule::Contraction => pick(BangContraction, QuestContraction),
Rule::Weakening => pick(BangWeakening, QuestWeakening),
Rule::Mix => Mix,
Rule::AffineWeakening => Weakening,
Rule::Cut => Cut,
Rule::Open => Open,
}
}
const fn negation(side: Side) -> Self {
match side {
Side::Input => Self::NegationLeft,
Side::Output => Self::NegationRight,
}
}
pub(crate) const fn markup(self, subscript: bool) -> &'static str {
if subscript {
Self::SUBSCRIPT[self as usize]
} else {
Self::UPRIGHT[self as usize]
}
}
}
impl Display for ClassicalRule {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
f.write_str(self.name())
}
}
#[derive(Clone, Debug)]
struct Shown {
base: InfId,
pending: Vec<usize>,
hidden: Vec<usize>,
rule: ClassicalRule,
premises: Vec<InfId>,
times: u32,
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug)]
pub struct TwoSided<'a> {
derivation: &'a Derivation<'a>,
writing: &'a [Written],
inferences: Vec<Shown>,
}
impl<'a> TwoSided<'a> {
pub fn new(
derivation: &'a Derivation<'a>,
writing: &'a [Written],
limits: &Limits,
) -> Result<Self, Error> {
let forest = derivation.forest();
if let Some(fault) = written::fault(forest, writing) {
panic!("the record is not one of the derivation's sequent: {fault}");
}
let view = Self {
derivation,
writing,
inferences: Vec::new(),
};
let mut counted = Counted::new(derivation);
view.walk(&mut counted);
if counted.inferences > Derivation::MOST {
return Err(Error::Refused(Refusal::Index {
what: Space::Inference,
count: counted.inferences,
most: Derivation::MOST,
}));
}
if let Some(bound) = limits.derivation_bytes
&& counted.bytes > bound
{
return Err(Error::Refused(Refusal::Output {
what: "derivation",
estimate_bytes: counted.bytes,
limit_bytes: bound,
least_bytes: None,
}));
}
let mut made = Vec::with_capacity(usize::try_from(counted.inferences).unwrap_or(0));
view.walk(&mut made);
Ok(Self {
inferences: made,
..view
})
}
fn walk(&self, sink: &mut impl Sink) {
let derivation = self.derivation;
let forest = derivation.forest();
let mut ids = Vec::with_capacity(derivation.inferences().len());
for (index, inference) in derivation.inferences().iter().enumerate() {
let rule = inference.rule().rule;
let principal = inference
.principal()
.map(|position| inference.sequent()[position]);
let body = matches!(rule, Rule::Forall | Rule::Exists);
let mut premises = Vec::with_capacity(inference.premises().len());
for (j, &premise) in inference.premises().iter().enumerate() {
let top: InfId = ids[premise.index()];
let exposed = match (inference.cut(), principal) {
(Some(a), _) => {
let o = derivation.occurrence(a);
let c = if j == 0 { o } else { forest.dual(o).unwrap() };
Some((a, [Some(c), None]))
}
(None, Some(p)) => {
Some((p, exposed(forest, rule, derivation.occurrence(p), j)))
}
(None, None) => None,
};
let negated = exposed
.into_iter()
.flat_map(|(of, children)| children.into_iter().flatten().map(move |c| (of, c)))
.filter(|&(_, c)| written::negated(forest, self.writing, c))
.map(|(of, c)| (self.exposed_at(inference, premise, of, c, body), c));
premises.push(self.negations(sink, premise, negated, top));
}
let written = principal.map_or(Written::new(Side::Output, false), |p| {
self.writing[derivation.occurrence(p).index()]
});
let shown = Shown {
base: InfId::new(index as u32),
pending: Vec::new(),
hidden: Vec::new(),
rule: ClassicalRule::applied(rule, written),
premises,
times: inference.times(),
};
ids.push(self.by_side(sink, shown, rule, inference.premises()));
}
let root = derivation.root();
if !derivation.is_of_goal() {
let sequent = derivation.inference(root).sequent();
let roots = sequent
.iter()
.map(|&m| derivation.occurrence(m))
.filter(|&o| {
forest.parent(o).is_none() && written::negated(forest, self.writing, o)
})
.map(|o| (sequent.partition_point(|&m| m < Member::from(o)), o));
self.negations(sink, root, roots, ids[root.index()]);
}
}
fn by_side(
&self,
sink: &mut impl Sink,
mut shown: Shown,
rule: Rule,
below: &[InfId],
) -> InfId {
let derivation = self.derivation;
let (Rule::Weakening | Rule::Contraction, &[premise]) = (rule, below) else {
return sink.take(shown);
};
let conclusion = derivation.inference(shown.base).sequent();
let above = derivation.inference(premise).sequent();
let (larger, extra) = if rule == Rule::Weakening {
(shown.base, difference(conclusion, above))
} else {
(premise, difference(above, conclusion))
};
let larger_sequent = derivation.inference(larger).sequent();
let side =
|&p: &usize| self.writing[derivation.occurrence(larger_sequent[p]).index()].side();
let (input, output): (Vec<usize>, Vec<usize>) =
extra.iter().partition(|p| side(p) == Side::Input);
if input.is_empty() || output.is_empty() {
return sink.take(shown);
}
let named = |side| ClassicalRule::applied(rule, Written::new(side, false));
let count = |positions: &[usize]| u32::try_from(positions.len()).unwrap_or(u32::MAX);
let upper = sink.take(Shown {
base: larger,
pending: Vec::new(),
hidden: if rule == Rule::Weakening {
input.clone()
} else {
output.clone()
},
rule: named(Side::Output),
premises: shown.premises.clone(),
times: count(&output),
});
shown.rule = named(Side::Input);
shown.premises = vec![upper];
shown.times = count(&input);
sink.take(shown)
}
fn negations(
&self,
sink: &mut impl Sink,
base: InfId,
negated: impl Iterator<Item = (usize, OccId)>,
mut top: InfId,
) -> InfId {
let forest = self.derivation.forest();
let mut pending = Vec::new();
for (position, c) in negated {
debug_assert_eq!(
self.derivation
.occurrence(self.derivation.inference(base).sequent()[position]),
c
);
pending.push(position);
let side = written::context(forest, self.writing, c);
top = sink.take(Shown {
base,
pending: pending.clone(),
hidden: Vec::new(),
rule: ClassicalRule::negation(side),
premises: vec![top],
times: 1,
});
}
top
}
fn exposed_at(
&self,
below: &Inference,
premise: InfId,
of: Member,
c: OccId,
body: bool,
) -> usize {
let sequent = self.derivation.inference(premise).sequent();
let Some(framing) = self.derivation.framing() else {
let position = sequent.partition_point(|&m| m < Member::from(c));
debug_assert_eq!(sequent[position].occ(), c);
return position;
};
let table = framing.table;
let frame = |m: Member| table.instance(m).map(|(_, f)| f);
let wanted = frame(of);
let fits = |m: Member| {
framing.occurrence(m) == c
&& if body {
frame(m).is_some_and(|f| table.frame_parts(f).0 == wanted)
} else {
frame(m) == wanted
}
};
let count = |s: &[Member], m: Member| {
s.partition_point(|&x| x <= m) - s.partition_point(|&x| x < m)
};
let mut first = None;
for (position, &m) in sequent.iter().enumerate().filter(|&(_, &m)| fits(m)) {
if count(sequent, m) > count(below.sequent(), m) {
return position;
}
first.get_or_insert(position);
}
first.expect("a premise holds what its rule exposes")
}
pub fn derivation(&self) -> &'a Derivation<'a> {
self.derivation
}
pub fn len(&self) -> usize {
self.inferences.len()
}
pub fn is_empty(&self) -> bool {
self.inferences.is_empty()
}
pub fn root(&self) -> InfId {
InfId::new(self.inferences.len() as u32 - 1)
}
pub fn rule(&self, id: InfId) -> ClassicalRule {
self.inferences[id.index()].rule
}
pub fn premises(&self, id: InfId) -> &[InfId] {
&self.inferences[id.index()].premises
}
pub fn shows(&self, id: InfId) -> InfId {
self.inferences[id.index()].base
}
pub fn sides(&self, id: InfId) -> impl Iterator<Item = (Member, Side, bool)> + '_ {
let shown = &self.inferences[id.index()];
let derivation = self.derivation;
let forest = derivation.forest();
let sequent = derivation.inference(shown.base).sequent();
let shown_at = move |&(position, _): &(usize, &Member)| !shown.hidden.contains(&position);
sequent
.iter()
.enumerate()
.filter(shown_at)
.map(move |(position, &m)| {
let o = derivation.occurrence(m);
if shown.pending.contains(&position) {
(m, written::context(forest, self.writing, o), true)
} else {
(m, self.writing[o.index()].side(), false)
}
})
}
pub fn sequent(&self, id: InfId) -> impl Display + '_ {
Sequent { view: self, id }
}
fn write(
&self,
out: &mut impl Write,
notation: &crate::linear::sequents::notation::Notation,
id: InfId,
aligned: bool,
marks: bool,
) -> FmtResult {
let shown = |side: Side| {
self.sides(id)
.filter(move |&(_, s, _)| s == side)
.map(|(m, _, negated)| (m, negated))
};
notation.classical(
out,
self.derivation.forest(),
self.writing,
self.derivation.framing(),
shown(Side::Input),
shown(Side::Output),
aligned,
marks,
)
}
pub fn text_size(&self, options: &TextOptions) -> (usize, usize) {
crate::linear::proofs::fmt::text_size(self, options)
}
pub fn write_text(
&self,
options: &TextOptions,
out: &mut impl Write,
stop: impl FnMut(crate::limits::Progress) -> bool,
) -> Result<(), Error> {
crate::linear::proofs::fmt::write_text(
self,
options,
out,
crate::limits::counting(stop, crate::limits::Phase::Write),
)
}
}
impl Drawn for TwoSided<'_> {
const RULES: usize = ClassicalRule::ALL.len();
const OPEN: Option<usize> = Some(ClassicalRule::Open as usize);
fn markup(rule: usize, labels: &Labels) -> Option<&str> {
let rule = ClassicalRule::ALL[rule];
let label = match labels {
Labels::Upright | Labels::Table(_) => rule.markup(false),
Labels::Subscript => rule.markup(true),
Labels::Off => return None,
};
(!label.is_empty()).then_some(label)
}
fn len(&self) -> usize {
self.inferences.len()
}
fn root(&self) -> InfId {
TwoSided::root(self)
}
fn premises(&self, id: InfId) -> &[InfId] {
&self.inferences[id.index()].premises
}
fn rule(&self, id: InfId) -> usize {
self.inferences[id.index()].rule as usize
}
fn name(&self, id: InfId) -> &'static str {
self.inferences[id.index()].rule.name()
}
fn times(&self, id: InfId) -> u32 {
self.inferences[id.index()].times
}
fn write_sequent(&self, out: &mut impl Write, id: InfId) -> FmtResult {
self.write(
out,
&crate::linear::sequents::notation::TEXT,
id,
false,
false,
)
}
#[cfg(any(feature = "latex", feature = "typst", feature = "svg"))]
fn sequent(
&self,
out: &mut String,
notation: &crate::linear::sequents::notation::Notation,
id: InfId,
aligned: bool,
marks: bool,
) {
self.write(out, notation, id, aligned, marks).unwrap();
}
#[cfg(feature = "svg")]
fn positions(&self, id: InfId) -> Vec<usize> {
let sides: Vec<Side> = self.sides(id).map(|(_, side, _)| side).collect();
let (left, right): (Vec<usize>, Vec<usize>) =
(0..sides.len()).partition(|&p| sides[p] == Side::Input);
left.into_iter().chain(right).collect()
}
}
struct Sequent<'v, 'a> {
view: &'v TwoSided<'a>,
id: InfId,
}
impl Display for Sequent<'_, '_> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
let notation = &crate::linear::sequents::notation::TEXT;
self.view.write(f, notation, self.id, false, false)
}
}
impl Display for TwoSided<'_> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.write_text(&TextOptions::default(), f, |_| false)
.map_err(|_| std::fmt::Error)
}
}
fn difference(larger: &[Member], smaller: &[Member]) -> Vec<usize> {
let mut extra = Vec::new();
let mut k = 0;
for (position, m) in larger.iter().enumerate() {
if smaller.get(k) == Some(m) {
k += 1;
} else {
extra.push(position);
}
}
extra
}
fn exposed(forest: &Forest, rule: Rule, p: OccId, j: usize) -> [Option<OccId>; 2] {
match (rule, j) {
(Rule::Par, _) => [forest.left(p), forest.right(p)],
(Rule::Tensor | Rule::With, 1) | (Rule::PlusRight, _) => [forest.right(p), None],
(
Rule::Tensor
| Rule::With
| Rule::PlusLeft
| Rule::Promotion
| Rule::Dereliction
| Rule::Forall
| Rule::Exists,
_,
) => [forest.left(p), None],
(
Rule::Ax
| Rule::One
| Rule::Bot
| Rule::Top
| Rule::Contraction
| Rule::Weakening
| Rule::Mix
| Rule::AffineWeakening
| Rule::Cut
| Rule::Open,
_,
) => [None, None],
}
}
trait Sink {
fn take(&mut self, shown: Shown) -> InfId;
}
impl Sink for Vec<Shown> {
fn take(&mut self, shown: Shown) -> InfId {
self.push(shown);
InfId::new(self.len() as u32 - 1)
}
}
struct Counted<'d> {
derivation: &'d Derivation<'d>,
weights: Weights,
characters: Vec<Option<u64>>,
inferences: u64,
bytes: u64,
}
impl<'d> Counted<'d> {
fn new(derivation: &'d Derivation<'d>) -> Self {
Self {
derivation,
weights: Weights::of_members(
derivation.forest(),
derivation.framing().map(|framing| framing.table),
),
characters: vec![None; derivation.inferences().len()],
inferences: 0,
bytes: 0,
}
}
}
impl Sink for Counted<'_> {
fn take(&mut self, shown: Shown) -> InfId {
let characters = *self.characters[shown.base.index()].get_or_insert_with(|| {
let sequent = self.derivation.inference(shown.base).sequent();
sequent.iter().fold(0u64, |sum, m| {
sum.saturating_add(self.weights.get(*m).into())
})
});
self.inferences = self.inferences.saturating_add(1);
self.bytes = self.bytes.saturating_add(
characters
.saturating_mul(Size::BYTES_PER_CHARACTER)
.saturating_add(Size::BYTES_PER_INFERENCE),
);
InfId::new(u32::try_from(self.inferences).unwrap_or(u32::MAX))
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::occurrences::ClassicalSequent;
use crate::linear::proofs::{Compact, ViewOptions};
use crate::linear::search::generate::{self, Rng, Rules};
use crate::linear::{Mode, Options, Proof};
fn proved(written: &ClassicalSequent, mode: Mode) -> Proof {
let outcome = crate::linear::prove(written.sequent(), mode, &Options::default()).unwrap();
outcome.verdict.proof().expect("provable").clone()
}
#[cfg(feature = "interactive")]
fn cut_written(
written: &ClassicalSequent,
mode: Mode,
rng: &mut Rng,
) -> Option<(Proof, Vec<Written>)> {
use crate::linear::{CutFormula, InputOptions, Interactive};
let limits = Limits::default();
let mut session = Interactive::of_classical(written, mode, &limits).unwrap();
let root = session.goals().next().unwrap();
let roots = written.forest().roots();
let p = rng.below(roots.len());
let text = written.formula(roots[p]).to_string();
let antecedents = written.sequent().antecedents().unwrap_or(0) as usize;
let left: Vec<usize> = if p < antecedents {
vec![p]
} else {
(0..roots.len()).filter(|&q| q != p).collect()
};
let formula =
CutFormula::parse_within(&text, mode, &InputOptions::default(), &limits).unwrap();
session.cut(root, &formula, &left, &limits).unwrap();
let options = Options::default();
let view = ViewOptions::default();
for (_, closed) in session.close_all(&options, &view, &limits, |_| false) {
closed.ok()?.grafted.ok()?;
}
let proof = session.proof(&limits, |_| false).ok()?;
Some((proof, session.writing().unwrap().to_vec()))
}
#[cfg(not(feature = "interactive"))]
fn cut_written(_: &ClassicalSequent, _: Mode, _: &mut Rng) -> Option<(Proof, Vec<Written>)> {
None
}
fn drawn(text: &str) -> String {
let written: ClassicalSequent = text.parse().unwrap();
let proof = proved(&written, Mode::CLASSICAL);
let options = ViewOptions::default().with_compact(Compact::Always);
let limits = Limits::default();
let derivation = proof
.derivation_within(&options, &limits, |_| false)
.unwrap();
TwoSided::new(&derivation, written.writing(), &limits)
.unwrap()
.to_string()
}
#[test]
fn rules_by_side_and_negation_steps() {
let cases = [
(
"A -o B, A |- B",
"───── ax ───── ax\n\
A ⊢ A B ⊢ B\n\
──────────────── ⊸L\n \
A ⊸ B, A ⊢ B",
),
(
"|- ~(A * B), A * B",
"───── ax ───── ax\n\
A ⊢ A B ⊢ B\n\
──────────────── ⊗R\n \
A, B ⊢ A ⊗ B\n \
───────────── ⊗L\n \
A ⊗ B ⊢ A ⊗ B\n\
───────────────── ~R\n\
⊢ ~(A ⊗ B), A ⊗ B",
),
(
"A par B |- ~(~A * ~B)",
"───── ax ───── ax\n\
A ⊢ A B ⊢ B\n\
──────────────── ⅋L\n \
A ⅋ B ⊢ A, B\n \
───────────── ~L\n \
A ⅋ B, ~A ⊢ B\n \
─────────────── ~L\n \
A ⅋ B, ~A, ~B ⊢\n \
──────────────── ⊗L\n \
A ⅋ B, ~A ⊗ ~B ⊢\n\
────────────────── ~R\n\
A ⅋ B ⊢ ~(~A ⊗ ~B)",
),
(
"!b, a |- a, ?c",
" ───── ax\n \
a ⊢ a\n \
───────── ?w\n \
a ⊢ a, ?c\n\
───────────── !w\n\
!b, a ⊢ a, ?c",
),
(
"!A |- ?(A + B) * 1",
" ───── ax\n \
A ⊢ A\n \
───────── ⊕R₁\n \
A ⊢ A ⊕ B\n\
──────────── ?R\n\
A ⊢ ?(A ⊕ B)\n\
───────────── !L ─── 1R\n\
!A ⊢ ?(A ⊕ B) ⊢ 1\n\
────────────────────── ⊗R\n \
!A ⊢ ?(A ⊕ B) ⊗ 1",
),
(
"exists y. forall x. r(x, y) |- forall x. exists y. r(x, y)",
" ───────────────── ax\n \
r(b, a) ⊢ r(b, a)\n \
───────────────────── ∃R\n \
r(b, a) ⊢ ∃y. r(b, y)\n \
───────────────────────── ∀L\n \
∀x. r(x, a) ⊢ ∃y. r(b, y)\n \
─────────────────────────────── ∀R\n \
∀x. r(x, a) ⊢ ∀x. (∃y. r(x, y))\n\
───────────────────────────────────── ∃L\n\
∃y. (∀x. r(x, y)) ⊢ ∀x. (∃y. r(x, y))",
),
];
for (text, tree) in cases {
assert_eq!(drawn(text), tree, "{text}");
}
}
#[test]
fn a_view_past_the_bound_is_refused() {
let written: ClassicalSequent = "A par B |- ~(~A * ~B)".parse().unwrap();
let proof = proved(&written, Mode::CLASSICAL);
let derivation = proof.derivation().unwrap();
let shown = derivation.inferences().len() as u64 * Size::BYTES_PER_INFERENCE;
let limits = Limits::default().with_derivation_bytes(Some(shown));
let refused = TwoSided::new(&derivation, written.writing(), &limits).unwrap_err();
assert!(matches!(
refused,
Error::Refused(Refusal::Output { estimate_bytes, limit_bytes, .. })
if estimate_bytes > limit_bytes && limit_bytes == shown
));
}
fn shown(view: &TwoSided<'_>, id: InfId) -> Vec<(Member, Side, bool)> {
let all: Vec<_> = view.sides(id).collect();
let on = |side| all.iter().copied().filter(move |&(_, s, _)| s == side);
on(Side::Input).chain(on(Side::Output)).collect()
}
#[derive(Default)]
struct Tally {
inferences: usize,
negations: usize,
split: usize,
cuts: usize,
rules: std::collections::BTreeSet<ClassicalRule>,
}
fn reads_as_its_term(proof: &Proof, writing: &[Written], text: &str, tally: &mut Tally) {
let limits = Limits::default();
let written: ClassicalSequent = text.parse().unwrap();
for compact in [Compact::Never, Compact::Always] {
let options = ViewOptions::default().with_compact(compact);
let derivation = proof
.derivation_within(&options, &limits, |_| false)
.unwrap();
let view = TwoSided::new(&derivation, writing, &limits).unwrap();
let forest = derivation.forest();
let occurrence = |m: Member| derivation.occurrence(m);
let root = view.root();
assert_eq!(
view.sequent(root).to_string(),
written.to_string(),
"{text}"
);
for k in 0..view.len() {
let id = InfId::new(k as u32);
let printed = view.sequent(id).to_string();
let parsed: ClassicalSequent = printed.parse().unwrap();
let members = shown(&view, id);
let left = members.iter().filter(|m| m.1 == Side::Input).count();
let (pf, pw) = (parsed.forest(), parsed.writing());
assert_eq!(
parsed.sequent().antecedents(),
Some(left as u32),
"{printed}"
);
assert_eq!(pf.roots().len(), members.len(), "{printed}");
for (&r, &(m, _, negated)) in pf.roots().iter().zip(&members) {
let o = occurrence(m);
assert_eq!(pf.size(r), forest.size(o), "{printed}");
assert_eq!(
pf.formula(r).to_string(),
derivation.formula(m).to_string(),
"{printed}"
);
for d in 0..forest.size(o) {
let (p, q) = (OccId::new(r.get() + d), OccId::new(o.get() + d));
assert_eq!(pf.kind(p), forest.kind(q), "{printed}");
assert_eq!(pw[p.index()], writing[q.index()], "{printed}");
if m.occurrence(forest).is_some() {
let name = |f: &Forest, x| {
f.atom(x).map(|a| f.sequent().atom_name(a).to_owned())
};
assert_eq!(name(pf, p), name(forest, q), "{printed}");
}
}
assert_eq!(parsed.is_negated(r), negated, "{printed}");
}
let base = derivation.inference(view.shows(id));
let rule = view.rule(id);
match rule.rule() {
None => {
let &[premise] = view.premises(id) else {
panic!("a negation step has one premise");
};
assert_eq!(view.shows(premise), view.shows(id));
let above: Vec<_> = view.sides(premise).collect();
let below: Vec<_> = view.sides(id).collect();
let moved: Vec<_> =
(0..below.len()).filter(|&p| above[p] != below[p]).collect();
let &[p] = &moved[..] else {
panic!("a negation step moves one formula: {printed}");
};
let (m, side, negated) = below[p];
assert!(negated && !above[p].2, "{printed}");
assert_eq!(above[p].1, writing[occurrence(m).index()].side());
assert_eq!(Some(side), rule.side(), "{printed}");
assert_ne!(side, above[p].1, "{printed}");
tally.negations += 1;
}
Some(one_sided) if one_sided.is_structural() => {
assert_eq!(one_sided, base.rule().rule, "{printed}");
let &[premise] = view.premises(id) else {
panic!("a structural rule has one premise");
};
let key = |s: &(Member, Side, bool)| (s.0, s.1 == Side::Input, s.2);
let mut below: Vec<_> = view.sides(id).map(|s| key(&s)).collect();
let mut above: Vec<_> = view.sides(premise).map(|s| key(&s)).collect();
below.sort_unstable();
above.sort_unstable();
let (larger, smaller) = if one_sided == Rule::Contraction {
(&above, &below)
} else {
(&below, &above)
};
let mut moved = larger.clone();
for s in smaller {
let at = moved.iter().position(|m| m == s).expect("a sub-multiset");
moved.remove(at);
}
assert_eq!(moved.len() as u32, view.inferences[k].times, "{printed}");
if let Some(named) = rule.side() {
let input = named == Side::Input;
assert!(moved.iter().all(|m| m.1 == input), "{printed} by {rule}");
}
}
Some(one_sided) => {
assert_eq!(one_sided, base.rule().rule, "{printed}");
assert_eq!(view.premises(id).len(), base.premises().len());
if let Some(position) = base.principal() {
let (m, side, negated) = view.sides(id).nth(position).unwrap();
assert!(!negated, "a rule acts on a formula as written");
if let Some(named) = rule.side() {
assert_eq!(side, named, "{printed} by {rule}");
}
let implication = writing[occurrence(m).index()].is_implication();
let lollipop = matches!(
rule,
ClassicalRule::LollipopLeft | ClassicalRule::LollipopRight
);
assert_eq!(implication, lollipop, "{printed} by {rule}");
}
}
}
tally.split += usize::from(!view.inferences[k].hidden.is_empty());
tally.cuts += usize::from(rule == ClassicalRule::Cut);
tally.rules.insert(rule);
tally.inferences += 1;
}
}
}
#[test]
fn every_inference_parses_back_and_reads_as_its_term() {
let mut tally = Tally::default();
let mut cut_rng = Rng::new(41);
for (i, rules) in Rules::ALL.into_iter().enumerate() {
let mode = if rules.mix {
Mode::CLASSICAL.with_mix()
} else {
Mode::CLASSICAL
};
let mut rng = Rng::new(400 + i as u64);
for _ in 0..10 {
let budget = 2 + rng.below(10);
let provable = generate::provable(&mut rng, rules, 3, budget);
let (text, _) = generate::written(&mut rng, &provable.formulas);
let written: ClassicalSequent = text.parse().unwrap();
let plain = (proved(&written, mode), written.writing().to_vec());
let cut = cut_written(&written, mode, &mut cut_rng);
for (proof, writing) in [Some(plain), cut].into_iter().flatten() {
reads_as_its_term(&proof, &writing, &text, &mut tally);
}
}
}
let Tally {
inferences,
negations,
split,
..
} = tally;
assert!(
inferences > 1000 && negations > 100 && split > 0,
"{inferences} {negations} {split}"
);
#[cfg(feature = "interactive")]
assert!(tally.cuts > 50, "{} cuts", tally.cuts);
}
#[test]
fn a_first_order_view_reads_as_its_term() {
let mut tally = Tally::default();
for text in [
"forall x. p(x) |- p(a)",
"exists y. forall x. r(x, y) |- forall x. exists y. r(x, y)",
"p(a) & p(b), q(b) |- exists x. (p(x) * q(x))",
"|- ~(forall x. p(x)), p(a)",
"exists x. ~p(x) |- ~(forall x. p(x))",
"|- forall x. ~(p(x) * q(x)), exists x. (p(x) * q(x))",
"!forall x. p(x), !q(c) |- p(a) * p(b), ?q(c)",
"!forall x. ~p(x), p(a) par p(b) |-",
] {
let written: ClassicalSequent = text.parse().unwrap();
let proof = proved(&written, Mode::CLASSICAL);
assert!(proof.instances().is_some(), "{text}");
reads_as_its_term(&proof, written.writing(), text, &mut tally);
}
let quantifiers = [
ClassicalRule::ForallLeft,
ClassicalRule::ForallRight,
ClassicalRule::ExistsLeft,
ClassicalRule::ExistsRight,
];
assert!(
quantifiers.iter().all(|r| tally.rules.contains(r)),
"{:?}",
tally.rules
);
assert!(tally.negations >= 3, "{} negations", tally.negations);
}
#[test]
fn rules_are_labelled_in_declaration_order() {
use ClassicalRule::*;
for (i, rule) in ClassicalRule::ALL.into_iter().enumerate() {
assert_eq!(rule as usize, i, "{rule}");
}
for (rule, name, upright, subscript, side, one_sided) in [
(ForallLeft, "∀L", "∀L", "∀_L", Side::Input, Rule::Exists),
(ForallRight, "∀R", "∀R", "∀_R", Side::Output, Rule::Forall),
(ExistsLeft, "∃L", "∃L", "∃_L", Side::Input, Rule::Forall),
(ExistsRight, "∃R", "∃R", "∃_R", Side::Output, Rule::Exists),
] {
assert_eq!(rule.name(), name);
assert_eq!(rule.markup(false), upright);
assert_eq!(rule.markup(true), subscript);
assert_eq!(rule.side(), Some(side));
assert_eq!(rule.rule(), Some(one_sided));
assert_eq!(
ClassicalRule::applied(one_sided, Written::new(side, false)),
rule
);
}
}
}