#![cfg_attr(feature = "parse", doc = "```")]
#![cfg_attr(not(feature = "parse"), doc = "```ignore")]
#![deny(clippy::wildcard_enum_match_arm)]
mod cut;
mod expand;
mod handover;
mod invert;
mod quantified;
#[cfg(feature = "serialize")]
mod replay;
mod terms;
mod witness;
pub use cut::CutFormula;
#[cfg(all(test, feature = "parse"))]
pub(crate) use cut::with_cuts;
pub use invert::{Inverted, Options};
#[cfg(feature = "serialize")]
pub(crate) use quantified::{PartTerm, Parts};
use crate::Error;
use crate::limits::{Limits, Phase, Progress, Refusal};
use crate::linear::fragment::Mode;
use crate::linear::occurrences::{ClassicalSequent, Forest, Member, OccId, Reading, Side, Written};
use crate::linear::proofs::derivation::{Derivation, InfId, Inference, ViewOptions};
use crate::linear::proofs::size::Size;
use crate::linear::proofs::{Named, Rule};
use crate::linear::search::Outcome;
use crate::linear::sequents::{Eigen, Sequent, Symbol};
use quantified::Quantified;
use std::fmt::{Display, Formatter, Result as FmtResult};
#[derive(Clone, Debug, PartialEq, Eq)]
#[cfg_attr(
feature = "serialize",
derive(serde::Serialize),
serde(tag = "kind", rename_all = "snake_case")
)]
#[non_exhaustive]
pub enum StepError {
#[non_exhaustive]
NoGoal {
goal: GoalId,
},
#[non_exhaustive]
NoFormula {
position: usize,
len: usize,
},
#[non_exhaustive]
Rule {
rule: Named,
position: usize,
formula: Box<str>,
},
#[non_exhaustive]
Mode {
rule: Named,
mode: Mode,
},
#[non_exhaustive]
NotAlone {
rule: Named,
position: usize,
},
#[non_exhaustive]
NoDual {
position: usize,
},
#[non_exhaustive]
NotQuest {
position: usize,
},
#[non_exhaustive]
Split {
position: usize,
},
#[non_exhaustive]
NoSplit {
rule: Named,
},
#[non_exhaustive]
Succedents {
count: usize,
},
#[non_exhaustive]
Output {
position: usize,
},
EmptyPremise,
#[non_exhaustive]
Exchange {
position: usize,
},
EmptyAntecedent,
#[non_exhaustive]
NoWitness {
rule: Named,
},
#[non_exhaustive]
Witness {
reason: String,
},
#[non_exhaustive]
Eigenvariable {
name: String,
},
#[non_exhaustive]
CutSymbol {
name: String,
},
}
impl Display for StepError {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
match self {
StepError::NoGoal { goal: id } => write!(f, "there is no open goal {}", id.get()),
StepError::NoFormula { position, len } => {
write!(
f,
"the goal has no formula {position}: it has {}",
crate::errors::counted(*len, "formula", "formulas")
)
}
StepError::Rule {
rule,
position,
formula,
} => write!(
f,
"the rule {rule} does not act on formula {position}, {formula}"
),
StepError::Mode { rule, mode } => {
write!(f, "the rule {rule} is not available in {mode} mode")
}
StepError::NotAlone { rule, position } => write!(
f,
"the rule {rule} needs formula {position} without other formulas in the goal"
),
StepError::NoDual { position } => write!(
f,
"the axiom needs formula {position} together with its dual literal and nothing else"
),
StepError::NotQuest { position } => write!(
f,
"promotion needs every other formula to be a ? formula, and formula {position} is not"
),
StepError::Split { position } => write!(
f,
"position {position} cannot go to the left premise: it is out of range, repeated, or the formula the rule acts on"
),
StepError::NoSplit { rule } => write!(f, "the rule {rule} takes no split"),
StepError::Succedents { count: n } => write!(
f,
"a premise would have {n} formulas right of ⊢ instead of one"
),
StepError::Output { position } => write!(
f,
"formula {position} is the one right of ⊢ and cannot be weakened"
),
StepError::EmptyPremise => {
f.write_str("the split leaves a premise without a formula, which no rule concludes")
}
StepError::EmptyAntecedent => f.write_str(
"a premise would have no formula left of ⊢, which the Lambek calculus without \
empty antecedents forbids",
),
StepError::NoWitness { rule } => write!(f, "the rule {rule} takes no witness"),
StepError::Witness { reason } => write!(f, "the witness is not a term here: {reason}"),
StepError::Eigenvariable { name } => write!(
f,
"the eigenvariable {name} cannot be used here: either no step below this goal \
introduced it (a ∀ step, or ∀R or ∃L two-sided), or it was made after the \
open witness it would fill"
),
StepError::CutSymbol { name } => write!(
f,
"the cut formula names {name}, which the sequent does not have with this arity \
and role: in a session with quantifiers, a cut formula may use only the \
sequent's symbols and the goal's eigenvariables"
),
StepError::Exchange { position } => write!(
f,
"formula {position} goes left but comes before a formula that goes right, which \
would need an exchange: the left premise takes the formulas just before the ⊗, \
going round"
),
}
}
}
impl std::error::Error for StepError {}
impl StepError {
const SHOWN: usize = 1 << 12;
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize), serde(transparent))]
pub struct GoalId(u32);
impl GoalId {
pub const fn new(raw: u32) -> Self {
Self(raw)
}
pub const fn get(self) -> u32 {
self.0
}
pub const fn index(self) -> usize {
self.0 as usize
}
const fn inf(self) -> InfId {
InfId::new(self.0)
}
const fn of(id: InfId) -> Self {
Self(id.get())
}
}
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Step {
pub position: usize,
pub rule: Named,
pub split: Split,
pub witness: Witness,
}
impl Step {
pub fn new(position: usize, rule: impl Into<Named>) -> Self {
Self {
position,
rule: rule.into(),
split: Split::None,
witness: Witness::Open,
}
}
#[must_use]
pub fn with_witness(self, witness: Witness) -> Self {
Self { witness, ..self }
}
#[must_use]
pub fn left(self, positions: &[usize]) -> Self {
Self {
split: Split::Left {
positions: positions.to_vec(),
},
..self
}
}
#[must_use]
pub fn at(self, position: usize) -> Self {
Self {
split: Split::At { position },
..self
}
}
fn left_positions(&self, len: usize) -> Result<Vec<usize>, StepError> {
match &self.split {
Split::None => Ok(Vec::new()),
Split::Left { positions } => Ok(positions.clone()),
&Split::At { position } if position >= len => Err(StepError::Split { position }),
&Split::At { position } => Ok((position..len)
.chain(0..position)
.take_while(|&p| p != self.position)
.collect()),
}
}
}
#[non_exhaustive]
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub enum Split {
#[default]
None,
#[non_exhaustive]
Left {
positions: Vec<usize>,
},
#[non_exhaustive]
At {
position: usize,
},
}
#[non_exhaustive]
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub enum Witness {
#[default]
Open,
Term(Vec<TermNode>),
}
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum TermNode {
App(Symbol, Vec<u32>),
Eigen(Eigen),
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Applicable {
pub rule: Named,
pub needs: Needs,
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Closed {
pub outcome: Outcome,
pub grafted: Result<(), Refusal>,
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Needs {
Nothing,
Split,
Witness,
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug)]
pub struct Interactive {
forest: Forest,
mode: Mode,
reading: Option<(Box<[Side]>, OccId)>,
writing: Option<Box<[Written]>>,
inferences: Vec<Inference>,
history: Vec<InfId>,
fo: Option<Box<Quantified>>,
}
impl Interactive {
pub fn new(sequent: &Sequent, mode: Mode) -> Result<Self, Error> {
Self::within(sequent, mode, &Limits::default())
}
pub fn within(sequent: &Sequent, mode: Mode, limits: &Limits) -> Result<Self, Error> {
if !sequent.cuts().is_empty() {
let mut conclusion = sequent.clone();
while !conclusion.cuts().is_empty() {
conclusion.pop_cut();
}
return Self::within(&conclusion, mode, limits);
}
let forest = Forest::within(sequent, limits)?;
let mut state = Self::from_forest(forest, mode)?;
if let Some(q) = state.fo.as_mut() {
q.limit = limits.terms;
}
Ok(state)
}
fn from_forest(forest: Forest, mode: Mode) -> Result<Self, Error> {
mode.check()?;
let fragment = forest.sequent().fragment();
if mode.is_ordered() && !crate::linear::Fragment::MLL.contains(fragment) {
return Err(Error::OrderedFragment { fragment, mode });
}
let reading = if mode.intuitionistic {
let reading = Reading::of_mode(&forest, mode).map_err(Error::NotIntuitionistic)?;
Some(reading.into_parts())
} else {
None
};
let root = Inference {
sequent: forest.roots().iter().copied().map(Member::from).collect(),
rule: Rule::Open.into(),
principal: None,
premises: vec![],
times: 1,
cut: None,
node: None,
};
let fo = forest
.has_binders()
.then(|| Box::new(Quantified::new(&forest)));
Ok(Self {
forest,
mode,
reading,
writing: None,
inferences: vec![root],
history: vec![],
fo,
})
}
pub fn of_classical(
sequent: &ClassicalSequent,
mode: Mode,
limits: &Limits,
) -> Result<Self, Error> {
let mut state = Self::within(sequent.sequent(), mode, limits)?;
state.writing = Some(sequent.writing().into());
Ok(state)
}
pub fn writing(&self) -> Option<&[Written]> {
self.writing.as_deref()
}
pub fn formula_as_written(&self, member: Member) -> Option<impl Display + '_> {
use crate::linear::occurrences::written;
let writing = self.writing.as_deref()?;
let o = member.occurrence(&self.forest)?;
Some(written::Shown {
forest: &self.forest,
writing,
o,
negated: written::negated(&self.forest, writing, o),
})
}
#[cfg(feature = "serialize")]
pub(crate) fn keep_writing(&mut self, writing: Box<[Written]>) -> Result<(), Error> {
if let Some(reason) = crate::linear::occurrences::written::fault(&self.forest, &writing) {
return Err(Error::InconsistentSession { reason });
}
self.writing = Some(writing);
Ok(())
}
pub fn forest(&self) -> &Forest {
&self.forest
}
pub fn occurrence(&self, member: Member) -> OccId {
match &self.fo {
Some(fo) => fo.instance(member).0,
None => member.occ(),
}
}
pub fn formula(&self, member: Member) -> impl Display + '_ {
if let Some(fo) = &self.fo
&& member.index() >= self.forest.len()
{
let framing = crate::linear::occurrences::instances::Framing::new(
&self.forest.sequent().fo,
&fo.shown,
);
let mut text = String::new();
crate::linear::sequents::notation::TEXT
.instance(
&mut text,
&self.forest,
self.reading().as_ref(),
&framing,
member,
None,
)
.expect("writing into a string cannot fail");
return text;
}
match self.reading() {
Some(reading) => reading.formula(member.occ()).to_string(),
None => self.forest.formula(member.occ()).to_string(),
}
}
pub fn sequent(&self) -> &Sequent {
self.forest.sequent()
}
pub fn mode(&self) -> Mode {
self.mode
}
pub fn reading(&self) -> Option<Reading<'_>> {
let (position, goal) = self.reading.as_ref()?;
Some(Reading::of_parts(
&self.forest,
position,
*goal,
self.mode.is_ordered(),
))
}
#[cfg(feature = "serialize")]
pub(crate) fn inferences(&self) -> &[Inference] {
&self.inferences
}
pub fn goals(&self) -> impl Iterator<Item = GoalId> + '_ {
self.inferences
.iter()
.enumerate()
.filter(|(_, inference)| inference.rule.rule == Rule::Open)
.map(|(i, _)| GoalId(i as u32))
}
pub fn goal(&self, id: GoalId) -> Result<&[Member], StepError> {
self.inferences
.get(id.index())
.filter(|inference| inference.rule.rule == Rule::Open)
.map(|inference| inference.sequent.as_slice())
.ok_or(StepError::NoGoal { goal: id })
}
pub fn is_complete(&self) -> bool {
self.goals().next().is_none()
}
pub fn steps(&self) -> usize {
self.history.len()
}
#[cfg(feature = "serialize")]
pub(crate) fn history(&self) -> &[InfId] {
&self.history
}
#[cfg(feature = "serialize")]
pub(crate) fn parts(&self) -> Option<Parts> {
self.fo.as_ref().map(|q| q.parts(&self.forest))
}
pub fn derivation(&self) -> Result<Derivation<'_>, Error> {
self.derivation_within(&ViewOptions::default(), &Limits::default(), |_| false)
}
pub fn derivation_within(
&self,
view: &ViewOptions,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Derivation<'_>, Error> {
let _ = view;
let weights =
super::size::Weights::of_members(&self.forest, self.fo.as_ref().map(|q| &q.shown));
let estimate = self.inferences.iter().fold(0u64, |sum, inference| {
let characters = inference.sequent.iter().fold(0u64, |sum, m| {
sum.saturating_add(u64::from(weights.get(*m)))
});
sum.saturating_add(Size::BYTES_PER_INFERENCE)
.saturating_add(characters.saturating_mul(Size::BYTES_PER_CHARACTER))
});
if let Some(limit) = limits.derivation_bytes
&& estimate > limit
{
return Err(Error::Refused(Refusal::Output {
what: "derivation",
estimate_bytes: estimate,
limit_bytes: limit,
least_bytes: None,
}));
}
if stop(Progress::new(Phase::View, 0, 0)) {
return Err(Error::Refused(Refusal::Stopped { phase: Phase::View }));
}
let order = self.postorder();
let mut new_id = vec![InfId::new(u32::MAX); self.inferences.len()];
for (i, id) in order.iter().enumerate() {
new_id[id.index()] = InfId::new(i as u32);
}
let inferences = order
.iter()
.map(|&id| {
let inference = &self.inferences[id.index()];
Inference {
sequent: inference.sequent.clone(),
rule: inference.rule,
principal: inference.principal,
cut: inference.cut,
node: None,
premises: inference
.premises
.iter()
.map(|&p| new_id[p.index()])
.collect(),
times: inference.times,
}
})
.collect();
let derivation =
Derivation::from_parts(&self.forest, self.reading(), inferences, self.mode);
Ok(match &self.fo {
Some(q) => derivation.with_framing(&q.shown),
None => derivation,
})
}
pub fn derivation_ids(&self) -> Vec<GoalId> {
self.postorder().into_iter().map(GoalId::of).collect()
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::proofs::{Node, NodeId, Proof};
use crate::linear::search::{self, Options, Reason, Verdict};
fn sequent(input: &str) -> Sequent {
input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"))
}
fn names(rules: Vec<Applicable>) -> Vec<Named> {
rules.into_iter().map(|a| a.rule).collect()
}
fn named(name: &str) -> Named {
name.parse().unwrap()
}
fn start(input: &str, mode: Mode) -> (Interactive, GoalId) {
let state = Interactive::new(&sequent(input), mode).unwrap();
let goal = state.goals().next().unwrap();
(state, goal)
}
#[test]
fn a_high_derivation_needs_no_stack() {
const DEPTH: usize = 20_000;
let text = format!("|- {}1{}", "bot | (".repeat(DEPTH), ")".repeat(DEPTH));
let proved = std::thread::Builder::new()
.stack_size(256 * 1024)
.spawn(move || {
let (mut state, mut goal) = start(&text, Mode::CLASSICAL);
for _ in 0..DEPTH {
goal = state.apply(goal, &Step::new(0, Rule::Par)).unwrap()[0];
goal = state.apply(goal, &Step::new(0, Rule::Bot)).unwrap()[0];
}
assert_eq!(state.apply(goal, &Step::new(0, Rule::One)).unwrap(), []);
state
.proof(&Limits::default(), |_| false)
.unwrap()
.nodes()
.len()
})
.unwrap()
.join()
.unwrap();
assert_eq!(proved, 2 * DEPTH + 1);
}
fn at(state: &Interactive, goal: GoalId, text: &str) -> usize {
let sequent = state.goal(goal).unwrap();
sequent
.iter()
.position(|&o| state.forest().formula(o.occ()).to_string() == text)
.unwrap_or_else(|| panic!("no {text} in goal {}", goal.get()))
}
fn step(
state: &mut Interactive,
goal: GoalId,
text: &str,
rule: Rule,
left: &[&str],
) -> Vec<GoalId> {
let position = at(state, goal, text);
let left: Vec<usize> = left.iter().map(|t| at(state, goal, t)).collect();
state
.apply(goal, &Step::new(position, rule).left(&left))
.unwrap_or_else(|e| panic!("{rule} on {text}: {e}"))
}
#[test]
fn every_rule_once() {
use Rule::*;
let classical = Mode::CLASSICAL;
let (mut s, g) = start("|- ~a par ~b, a * b", classical);
let [g] = step(&mut s, g, "~a ⅋ ~b", Par, &[])[..] else {
panic!()
};
let [l, r] = step(&mut s, g, "a ⊗ b", Tensor, &["~a"])[..] else {
panic!()
};
assert_eq!(s.goals().collect::<Vec<_>>(), [l, r]);
step(&mut s, l, "a", Ax, &[]);
assert_eq!(names(s.rules(r, 0).unwrap()), [Named::from(Ax)]);
step(&mut s, r, "b", Ax, &[]);
assert!(s.is_complete());
let proof = s.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.nodes().len(), 4);
assert_eq!(
s.derivation().unwrap().to_string(),
proof.derivation().unwrap().to_string()
);
let (mut s, g) = start("|- bot, 1", classical);
let [g] = step(&mut s, g, "⊥", Bot, &[])[..] else {
panic!()
};
step(&mut s, g, "1", One, &[]);
s.proof(&Limits::default(), |_| false).unwrap();
let (mut s, g) = start("|- a & b, ~a + ~b", classical);
let [l, r] = step(&mut s, g, "a & b", With, &[])[..] else {
panic!()
};
let [l] = step(&mut s, l, "~a ⊕ ~b", PlusLeft, &[])[..] else {
panic!()
};
step(&mut s, l, "a", Ax, &[]);
let [r] = step(&mut s, r, "~a ⊕ ~b", PlusRight, &[])[..] else {
panic!()
};
step(&mut s, r, "~b", Ax, &[]);
s.proof(&Limits::default(), |_| false).unwrap();
let (mut s, g) = start("|- top, 0", classical);
assert_eq!(names(s.rules(g, at(&s, g, "0")).unwrap()), []);
step(&mut s, g, "⊤", Top, &[]);
s.proof(&Limits::default(), |_| false).unwrap();
let (mut s, g) = start("!a |- a * a", classical);
let [g] = step(&mut s, g, "?~a", Contraction, &[])[..] else {
panic!()
};
let [l, r] = step(&mut s, g, "a ⊗ a", Tensor, &["?~a"])[..] else {
panic!()
};
for g in [l, r] {
let [g] = step(&mut s, g, "?~a", Dereliction, &[])[..] else {
panic!()
};
step(&mut s, g, "~a", Ax, &[]);
}
let proof = s.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(
proof.derivation().unwrap().to_string(),
"─────── ax ─────── ax\n\
⊢ ~a, a ⊢ ~a, a\n\
──────── ?d ──────── ?d\n\
⊢ ?~a, a ⊢ ?~a, a\n\
────────────────────── ⊗\n\
\x20 ⊢ ?~a, ?~a, a ⊗ a\n\
\x20 ───────────────── ?c\n\
\x20 ⊢ ?~a, a ⊗ a"
);
let (mut s, g) = start("!a |- !a", classical);
let [g] = step(&mut s, g, "!a", Promotion, &[])[..] else {
panic!()
};
let [g] = step(&mut s, g, "?~a", Dereliction, &[])[..] else {
panic!()
};
step(&mut s, g, "~a", Ax, &[]);
s.proof(&Limits::default(), |_| false).unwrap();
let (mut s, g) = start("|- ?a, 1", classical);
let [g] = step(&mut s, g, "?a", Weakening, &[])[..] else {
panic!()
};
step(&mut s, g, "1", One, &[]);
s.proof(&Limits::default(), |_| false).unwrap();
let (mut s, g) = start("a, b |- a", classical.with_affine());
assert_eq!(
names(s.rules(g, at(&s, g, "~b")).unwrap()),
[Named::from(Ax), Named::from(AffineWeakening)]
);
let [g] = step(&mut s, g, "~b", AffineWeakening, &[])[..] else {
panic!()
};
step(&mut s, g, "~a", Ax, &[]);
s.proof(&Limits::default(), |_| false).unwrap();
let (mut s, g) = start("|- a, ~a, b, ~b", classical.with_mix());
assert_eq!(
names(s.rules(g, 0).unwrap()),
[Named::from(Ax), Named::from(Mix)]
);
let [l, r] = step(&mut s, g, "a", Mix, &["~a"])[..] else {
panic!()
};
step(&mut s, l, "a", Ax, &[]);
step(&mut s, r, "b", Ax, &[]);
assert_eq!(s.steps(), 3);
s.proof(&Limits::default(), |_| false).unwrap();
}
#[test]
fn rejections() {
use Rule::*;
let (mut s, g) = start("|- ~a par ~b, a * b, 1, !c, ?d, top", Mode::CLASSICAL);
let before = s.clone();
let p = |s: &Interactive, text: &str| at(s, g, text);
let cases: Vec<(&str, Named, Vec<usize>, StepError)> = vec![
(
"~a ⅋ ~b",
Named::from(Tensor),
vec![],
StepError::Rule {
rule: Named::from(Tensor),
position: p(&s, "~a ⅋ ~b"),
formula: "~a ⅋ ~b".into(),
},
),
(
"1",
Named::from(AffineWeakening),
vec![],
StepError::Mode {
rule: Named::from(AffineWeakening),
mode: Mode::CLASSICAL,
},
),
(
"1",
Named::from(Mix),
vec![],
StepError::Mode {
rule: Named::from(Mix),
mode: Mode::CLASSICAL,
},
),
(
"1",
Named::from(One),
vec![],
StepError::NotAlone {
rule: Named::from(One),
position: p(&s, "1"),
},
),
(
"!c",
Named::from(Promotion),
vec![],
StepError::NotQuest { position: 0 },
),
(
"~a ⅋ ~b",
Named::from(Par),
vec![1],
StepError::NoSplit {
rule: Named::from(Par),
},
),
(
"a ⊗ b",
Named::from(Tensor),
vec![9],
StepError::Split { position: 9 },
),
(
"a ⊗ b",
Named::from(Tensor),
vec![0, 0],
StepError::Split { position: 0 },
),
(
"a ⊗ b",
Named::from(Tensor),
vec![p(&s, "a ⊗ b")],
StepError::Split {
position: p(&s, "a ⊗ b"),
},
),
(
"1",
named("⊸L"),
vec![],
StepError::Rule {
rule: named("⊸L"),
position: p(&s, "1"),
formula: "1".into(),
},
),
];
for (text, rule, left, refusal) in cases {
let position = p(&s, text);
assert_eq!(
s.apply(g, &Step::new(position, rule).left(&left)),
Err(refusal),
"{rule} on {text}"
);
}
assert_eq!(
s.apply(g, &Step::new(99, Par)),
Err(StepError::NoFormula {
position: 99,
len: 6
})
);
assert_eq!(
s.apply(GoalId::new(7), &Step::new(0, Par)),
Err(StepError::NoGoal {
goal: GoalId::new(7)
})
);
assert_eq!(
s.rules(GoalId::new(7), 0),
Err(StepError::NoGoal {
goal: GoalId::new(7)
})
);
assert_eq!(s.inferences(), before.inferences());
assert_eq!(s.steps(), 0);
let (mut s, g) = start("|- a, ~a, b", Mode::CLASSICAL);
assert_eq!(
s.apply(g, &Step::new(0, Ax)),
Err(StepError::NotAlone {
rule: Named::from(Ax),
position: 0
})
);
let (mut s, g) = start("|- a, b", Mode::CLASSICAL);
assert_eq!(
s.apply(g, &Step::new(0, Ax)),
Err(StepError::NoDual { position: 0 })
);
assert_eq!(
s.apply(g, &Step::new(0, Ax)).unwrap_err().to_string(),
"the axiom needs formula 0 together with its dual literal and nothing else"
);
let i = Mode::INTUITIONISTIC;
let (mut s, g) = start("a, a -o b |- b", i);
let imp = at(&s, g, "a ⊗ ~b");
assert_eq!(names(s.rules(g, imp).unwrap()), [named("⊸L")]);
assert_eq!(
s.apply(g, &Step::new(imp, named("⊗R"))),
Err(StepError::Rule {
rule: named("⊗R"),
position: imp,
formula: "a ⊸ b".into(),
})
);
let b = at(&s, g, "b");
assert_eq!(
s.apply(g, &Step::new(imp, named("⊸L")).left(&[b])),
Err(StepError::Succedents { count: 2 })
);
let (mut s, g) = start("a, b |- a", i.with_affine());
let goal = at(&s, g, "a");
assert_eq!(
s.apply(g, &Step::new(goal, AffineWeakening)),
Err(StepError::Output { position: goal })
);
assert!(Interactive::new(&sequent("|- a par b"), i).is_err());
assert!(matches!(
Interactive::new(&sequent("a |- a"), i.with_mix()),
Err(Error::IntuitionisticMix)
));
}
#[test]
fn intuitionistic() {
use Rule::*;
let i = Mode::INTUITIONISTIC;
let (mut s, g) = start("a, a -o b |- b", i);
let imp = at(&s, g, "a ⊗ ~b");
let a = at(&s, g, "~a");
let [l, r] = s.apply(g, &Step::new(imp, Tensor).left(&[a])).unwrap()[..] else {
panic!()
};
assert_eq!(s.inferences()[g.index()].rule, named("⊸L"));
assert_eq!(
s.derivation().unwrap().to_string(),
"a ⊢ a b ⊢ b\n\
───────────── ⊸L\n\
a, a ⊸ b ⊢ b"
);
s.apply(l, &Step::new(0, Ax)).unwrap();
s.apply(r, &Step::new(0, Ax)).unwrap();
let proof = s.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(i), Ok(()));
assert_eq!(
s.derivation().unwrap().to_string(),
proof.two_sided().unwrap().to_string()
);
let (mut s, g) = start("!a |- !(a * a)", i);
let [g] = s
.apply(g, &Step::new(at(&s, g, "!(a ⊗ a)"), named("!R")))
.unwrap()[..]
else {
panic!()
};
let [g] = s
.apply(g, &Step::new(at(&s, g, "?~a"), named("!c")))
.unwrap()[..]
else {
panic!()
};
assert_eq!(
names(s.rules(g, at(&s, g, "?~a")).unwrap()),
[named("!L"), named("!c"), named("!w")]
);
let [l, r] = s
.apply(
g,
&Step::new(at(&s, g, "a ⊗ a"), named("⊗R")).left(&[at(&s, g, "?~a")]),
)
.unwrap()[..]
else {
panic!()
};
for g in [l, r] {
let [g] = s
.apply(g, &Step::new(at(&s, g, "?~a"), named("!L")))
.unwrap()[..]
else {
panic!()
};
s.apply(g, &Step::new(0, Ax)).unwrap();
}
assert_eq!(
s.proof(&Limits::default(), |_| false).unwrap().check(i),
Ok(())
);
}
#[test]
fn search_closes_repeated_and_affine_goals() {
use Rule::*;
let close_all = |s: &mut Interactive| {
let outcomes = s.close_all(
&Options::default(),
&ViewOptions::default(),
&Limits::default(),
|_| false,
);
assert!(s.is_complete(), "{outcomes:?}");
s.proof(&Limits::default(), |_| false).unwrap()
};
let (mut s, g) = start("|- ?(a par ~a)", Mode::CLASSICAL);
let [repeated] = step(&mut s, g, "?(a ⅋ ~a)", Contraction, &[])[..] else {
panic!()
};
assert_eq!(s.goal(repeated).unwrap().len(), 2);
assert_eq!(close_all(&mut s).check(Mode::CLASSICAL), Ok(()));
let affine = Mode::CLASSICAL.with_affine();
let (mut s, g) = start("|- a * b, ~a, ~b, c", affine);
step(&mut s, g, "a ⊗ b", Tensor, &["~a"]);
assert_eq!(close_all(&mut s).check(affine), Ok(()));
}
#[test]
fn search_closes_goals() {
use Rule::*;
let options = Options::default();
let (mut s, g) = start("|- (a & b) * c, ~a + ~b, ~c", Mode::CLASSICAL);
let t = at(&s, g, "(a & b) ⊗ c");
let [l, r] = s
.apply(g, &Step::new(t, Tensor).left(&[at(&s, g, "~a ⊕ ~b")]))
.unwrap()[..]
else {
panic!()
};
let outcome = s
.close(
l,
&options,
&ViewOptions::default(),
&crate::Limits::default(),
|_| false,
)
.unwrap()
.outcome;
assert!(matches!(outcome.verdict, Verdict::Proved(_)));
assert_eq!(outcome.engine, crate::linear::search::Engine::Additive);
assert_eq!(s.goals().collect::<Vec<_>>(), [r]);
assert_eq!(s.steps(), 2);
let outcomes = s.close_all(
&options,
&ViewOptions::default(),
&crate::Limits::default(),
|_| false,
);
assert_eq!(outcomes.len(), 1);
assert_eq!(outcomes[0].0, r);
assert!(s.is_complete());
let proof = s.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(Mode::CLASSICAL), Ok(()));
assert!(s.derivation().unwrap().to_string().contains("⊕₂"));
let (mut s, g) = start("|- a * b, ~a, ~b", Mode::CLASSICAL);
let [l, r] = s
.apply(
g,
&Step::new(at(&s, g, "a ⊗ b"), Tensor).left(&[at(&s, g, "~b")]),
)
.unwrap()[..]
else {
panic!()
};
let outcome = s
.close(
l,
&options,
&ViewOptions::default(),
&crate::Limits::default(),
|_| false,
)
.unwrap()
.outcome;
assert!(matches!(outcome.verdict, Verdict::Unprovable(_)));
let outcome = s
.close(
r,
&options,
&ViewOptions::default(),
&crate::Limits::default(),
|_| true,
)
.unwrap()
.outcome;
assert!(matches!(outcome.verdict, Verdict::Unknown(Reason::Stopped)));
assert_eq!(s.goals().collect::<Vec<_>>(), [l, r]);
assert!(matches!(
s.proof(&Limits::default(), |_| false),
Err(Error::OpenGoals { count: 2 })
));
assert!(matches!(
s.close(
g,
&options,
&ViewOptions::default(),
&crate::Limits::default(),
|_| false
),
Err(Error::Step(StepError::NoGoal { .. }))
));
let (mut s, g) = start("a & b, !(a -o c) |- c", Mode::INTUITIONISTIC);
let [g] = s
.apply(g, &Step::new(at(&s, g, "~a ⊕ ~b"), named("&L₁")))
.unwrap()[..]
else {
panic!()
};
let outcome = s
.close(
g,
&options,
&ViewOptions::default(),
&crate::Limits::default(),
|_| false,
)
.unwrap()
.outcome;
assert!(matches!(outcome.verdict, Verdict::Proved(_)));
assert!(s.derivation().unwrap().to_string().contains("!L"));
assert_eq!(
s.proof(&Limits::default(), |_| false)
.unwrap()
.check(Mode::INTUITIONISTIC),
Ok(())
);
}
#[test]
fn cyclic() {
let cyclic = Mode::CYCLIC;
let (mut s, g) = start("|- (a * b) * c, ~c, ~b, ~a", cyclic);
assert_eq!(
s.apply(g, &Step::new(0, Rule::Tensor).left(&[1])),
Err(StepError::Exchange { position: 1 })
);
let goals = s.apply(g, &Step::new(0, Rule::Tensor).at(2)).unwrap();
let (left, right) = (goals[0], goals[1]);
let members = |s: &Interactive, g| {
s.goal(g)
.unwrap()
.iter()
.map(|m| m.get())
.collect::<Vec<_>>()
};
assert_eq!(
(members(&s, left), members(&s, right)),
(vec![1, 6, 7], vec![4, 5])
);
s.apply(right, &Step::new(0, Rule::Ax)).unwrap();
let options = Options::default();
let closed = s
.close(
left,
&options,
&ViewOptions::default(),
&Limits::default(),
|_| false,
)
.unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Proved(_)) && closed.grafted.is_ok());
assert_eq!(s.goals().count(), 0);
let proof = s.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(cyclic), Ok(()));
let (mut s, g) = start("|- a * (~a par b), ~b", cyclic);
let goals = s.apply(g, &Step::new(0, Rule::Tensor).at(0)).unwrap();
assert_eq!(members(&s, goals[0]), [1]);
assert!(matches!(
Interactive::new(&sequent("|- a & b, ~a"), cyclic),
Err(Error::OrderedFragment { .. })
));
}
#[test]
fn lambek() {
let ordered = |input: &str| {
Sequent::parse_ordered(input, crate::linear::Order::Cyclic, &Limits::default()).unwrap()
};
let lambek = Mode::LAMBEK;
let mut s = Interactive::new(&ordered("b / a, a |- b"), lambek).unwrap();
let g = s.goals().next().unwrap();
let slash = "/L".parse::<Named>().unwrap();
assert_eq!(names(s.rules(g, 1).unwrap()), [slash]);
assert!(matches!(
s.apply(g, &Step::new(1, "⊸L".parse::<Named>().unwrap()).at(0)),
Err(StepError::Rule { .. })
));
let goals = s.apply(g, &Step::new(1, slash).at(0)).unwrap();
assert_eq!(
goals
.iter()
.map(|&g| s.goal(g).unwrap().len())
.collect::<Vec<_>>(),
[2, 2]
);
s.apply(goals[0], &Step::new(0, Rule::Ax)).unwrap();
let options = Options::default();
let closed = s
.close(
goals[1],
&options,
&ViewOptions::default(),
&Limits::default(),
|_| false,
)
.unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Proved(_)) && closed.grafted.is_ok());
let proof = s.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(lambek), Ok(()));
assert_eq!(
s.derivation().unwrap().to_string(),
"───── ax ───── ax\n\
a ⊢ a b ⊢ b\n\
──────────────── /L\n \
b / a, a ⊢ b"
);
let sequent = ordered("e |- e * (a \\ a)");
let step = Step::new(1, Rule::Tensor).at(0);
let (mut s, mut star) = (
Interactive::new(&sequent, lambek).unwrap(),
Interactive::new(&sequent, lambek.with_empty_antecedents()).unwrap(),
);
let (g, h) = (s.goals().next().unwrap(), star.goals().next().unwrap());
assert_eq!(s.apply(g, &step), Err(StepError::EmptyAntecedent));
assert_eq!(star.apply(h, &step).map(|goals| goals.len()), Ok(2));
assert!(matches!(
Interactive::new(&ordered("|- a \\ a"), lambek),
Err(Error::NotIntuitionistic(_))
));
}
#[test]
fn fill_carries_a_proof_of_an_equal_sequent() {
let (view, limits) = (ViewOptions::default(), Limits::default());
let proof_of = |input: &str, mode: Mode| {
let outcome = search::prove(&sequent(input), mode, &Options::default()).unwrap();
let Verdict::Proved(proof) = outcome.verdict else {
panic!("{input}: {:?}", outcome.verdict)
};
proof
};
let after_par = || {
let (mut s, g) = start("A * B |- B * A", Mode::CLASSICAL);
let par = at(&s, g, "~A ⅋ ~B");
let goal = s.apply(g, &Step::new(par, Rule::Par)).unwrap()[0];
(s, goal)
};
let (mut s, goal) = after_par();
let elsewhere = proof_of("|- B * A, ~A, ~B", Mode::CLASSICAL);
s.fill(goal, &elsewhere, &view, &limits, |_| false).unwrap();
assert!(s.is_complete());
s.proof(&limits, |_| false).unwrap();
let (mut s, goal) = after_par();
let other = proof_of("|- A * B, ~A, ~B", Mode::CLASSICAL);
let refused = s.fill(goal, &other, &view, &limits, |_| false).unwrap_err();
let Error::SequentMismatch { proof, goal: held } = &refused else {
panic!("{refused:?}")
};
assert_eq!(
(proof, held),
(&vec!["A ⊗ B".to_owned()], &vec!["B ⊗ A".to_owned()])
);
assert_eq!(refused.code(), "sequent_mismatch");
let fewer = proof_of("|- ~A, A", Mode::CLASSICAL);
let refused = s.fill(goal, &fewer, &view, &limits, |_| false).unwrap_err();
let Error::SequentMismatch { proof, goal: held } = &refused else {
panic!("{refused:?}")
};
assert_eq!((proof.len(), held.len()), (1, 2), "{refused}");
assert_eq!(s.goals().collect::<Vec<_>>(), [goal]);
let (mut s, g) = start("|- A, ~A, B, ~B", Mode::CLASSICAL);
let mixed = proof_of("|- B, ~B, A, ~A", Mode::CLASSICAL.with_mix());
assert!(matches!(
s.fill(g, &mixed, &view, &limits, |_| false),
Err(Error::Check(crate::linear::proofs::CheckError::Invalid(_)))
));
assert_eq!(s.goals().collect::<Vec<_>>(), [g]);
let past = Member::new(u32::try_from(s.forest().len()).unwrap());
assert!(matches!(
mixed.onto(s.forest().clone(), &[past]),
Err(Error::IndexOutOfBounds { .. })
));
}
#[test]
fn close_with_refuses_a_foreign_proof() {
let view = ViewOptions::default();
let (mut s, g) = start("A, A -o B |- B", Mode::CLASSICAL);
for other in ["|- A, B, C, D, top", "|- top"] {
let forest = Forest::new(&sequent(other)).unwrap();
let top = *forest.roots().last().unwrap();
let proof =
Proof::new(forest, vec![Node::Top(Member::from(top))], NodeId::new(0)).unwrap();
assert!(matches!(
s.close_with(g, &proof, &view, &crate::Limits::default(), |_| false),
Err(Error::ForeignProof)
));
}
assert_eq!(s.goals().collect::<Vec<_>>(), [g]);
let (mut s, g) = start("A, B |- A", Mode::CLASSICAL);
let affine = search::prove_goal(
search::Goal::new(s.forest(), s.goal(g).unwrap()).unwrap(),
Mode::CLASSICAL.with_affine(),
&Options::default(),
&Limits::default(),
|_| false,
)
.unwrap();
let Verdict::Proved(proof) = affine.verdict else {
panic!("{:?}", affine.verdict)
};
assert!(matches!(
s.close_with(g, &proof, &view, &crate::Limits::default(), |_| false),
Err(Error::Check(crate::linear::proofs::CheckError::Invalid(_)))
));
assert_eq!(s.goals().collect::<Vec<_>>(), [g]);
let (mut s, g) = start("A, B |- A * B", Mode::CLASSICAL);
let outcome = search::prove(s.sequent(), Mode::CLASSICAL, &Options::default()).unwrap();
let Verdict::Proved(whole) = outcome.verdict else {
panic!("{:?}", outcome.verdict)
};
let tensor = at(&s, g, "A ⊗ B");
let premises = s
.apply(g, &Step::new(tensor, Rule::Tensor).left(&[at(&s, g, "~A")]))
.unwrap();
assert!(matches!(
s.close_with(premises[0], &whole, &view, &Limits::default(), |_| false),
Err(Error::GoalMismatch)
));
}
#[test]
fn split_helper() {
let (s, g) = start("|- a * b, ~a, ~b", Mode::CLASSICAL);
let t = at(&s, g, "a ⊗ b");
assert!(
s.split_passes(g, &Step::new(t, Rule::Tensor).left(&[at(&s, g, "~a")]))
.unwrap()
);
assert!(
!s.split_passes(g, &Step::new(t, Rule::Tensor).left(&[at(&s, g, "~b")]))
.unwrap()
);
assert!(
!s.split_passes(g, &Step::new(t, Rule::Tensor).left(&[]))
.unwrap()
);
assert_eq!(
s.split_passes(g, &Step::new(t, Rule::Tensor).left(&[t])),
Err(StepError::Split { position: t })
);
let (s, g) = start("|- a, ~a, b, ~b", Mode::CLASSICAL.with_mix());
assert!(
s.split_passes(g, &Step::new(0, Rule::Tensor).left(&[at(&s, g, "~a")]))
.unwrap()
);
assert!(
!s.split_passes(g, &Step::new(0, Rule::Tensor).left(&[at(&s, g, "b")]))
.unwrap()
);
}
#[test]
fn undo_restores_goals() {
use Rule::*;
let (mut s, g) = start("|- ~a par ~b, a * b", Mode::CLASSICAL);
assert_eq!(s.undo(), None);
let start_state = s.clone();
let [g1] = s.apply(g, &Step::new(at(&s, g, "~a ⅋ ~b"), Par)).unwrap()[..] else {
panic!()
};
let after_par = s.clone();
let [l, _] = s
.apply(
g1,
&Step::new(at(&s, g1, "a ⊗ b"), Tensor).left(&[at(&s, g1, "~a")]),
)
.unwrap()[..]
else {
panic!()
};
s.close(
l,
&Options::default(),
&ViewOptions::default(),
&crate::Limits::default(),
|_| false,
)
.unwrap();
assert_eq!(s.undo(), Some(l));
assert_eq!(s.goals().count(), 2);
assert_eq!(s.undo(), Some(g1));
assert_eq!(s.inferences(), after_par.inferences());
assert_eq!(s.undo(), Some(g));
assert_eq!(s.inferences(), start_state.inferences());
assert_eq!(s.undo(), None);
let outcome = s
.close(
g,
&Options::default(),
&ViewOptions::default(),
&crate::Limits::default(),
|_| false,
)
.unwrap()
.outcome;
assert!(matches!(outcome.verdict, Verdict::Proved(_)));
assert!(s.is_complete());
assert_eq!(s.undo(), Some(g));
assert_eq!(s.inferences(), start_state.inferences());
}
#[test]
fn open_goals_render() {
use Rule::*;
let (mut s, g) = start("|- ~a par ~b, a * b", Mode::CLASSICAL);
let [g] = s.apply(g, &Step::new(at(&s, g, "~a ⅋ ~b"), Par)).unwrap()[..] else {
panic!()
};
s.apply(
g,
&Step::new(at(&s, g, "a ⊗ b"), Tensor).left(&[at(&s, g, "~a")]),
)
.unwrap();
assert_eq!(
s.derivation().unwrap().to_string(),
"⊢ ~a, a ⊢ ~b, b\n\
───────────────── ⊗\n\
\x20⊢ ~a, ~b, a ⊗ b\n\
\x20──────────────── ⅋\n\
\x20⊢ ~a ⅋ ~b, a ⊗ b"
);
let d = s.derivation().unwrap();
assert_eq!(d.inference(d.root()).rule, Named::from(Par));
assert_eq!(d.inference(InfId::new(0)).rule, Named::from(Open));
}
#[test]
fn mix_keeps_repeated_formulas() {
use Rule::*;
let (mut s, g) = start("|- ?(a par ~a)", Mode::CLASSICAL.with_mix());
let [g] = step(&mut s, g, "?(a ⅋ ~a)", Contraction, &[])[..] else {
panic!()
};
let [g] = step(&mut s, g, "?(a ⅋ ~a)", Dereliction, &[])[..] else {
panic!()
};
let [g] = step(&mut s, g, "?(a ⅋ ~a)", Dereliction, &[])[..] else {
panic!()
};
let [l, r] = step(&mut s, g, "a ⅋ ~a", Mix, &[])[..] else {
panic!()
};
assert_eq!(s.goal(l), s.goal(r));
assert_eq!(s.goal(l).map(<[Member]>::len), Ok(1));
assert_eq!(s.apply(l, &Step::new(0, Mix)), Err(StepError::EmptyPremise));
let closed = s.close_all(
&Options::default(),
&ViewOptions::default(),
&crate::Limits::default(),
|_| false,
);
assert_eq!(closed.iter().map(|(g, _)| *g).collect::<Vec<_>>(), [l, r]);
assert!(
closed
.iter()
.all(|(_, c)| c.as_ref().is_ok_and(|c| c.grafted.is_ok()))
);
assert!(s.is_complete());
}
}