use super::translate::{Core, Image, pattern};
use super::{Formulas, Logic, Node, NodeId, Translation};
use crate::limits::{Limits, Phase, Progress, Refusal};
use crate::linear::occurrences::OccId;
use crate::linear::proofs::style::Drawn;
use crate::linear::proofs::{
Compact, InfId, Labels, Rule as Linear, Sides, Structural, TextOptions, ViewOptions,
};
#[cfg(any(feature = "latex", feature = "typst", feature = "svg"))]
use crate::linear::sequents::notation::Notation;
use crate::linear::sequents::notation::TEXT;
use crate::{Error, linear::Proof};
use std::borrow::Cow;
use std::fmt::{Display, Formatter, Result as FmtResult, Write};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serialize", serde(rename_all = "lowercase"))]
pub enum Side {
Left,
Right,
}
impl Side {
pub(crate) const fn flip(self) -> Self {
match self {
Self::Left => Self::Right,
Self::Right => Self::Left,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum Rule {
Axiom,
WeakenLeft,
WeakenRight,
ContractLeft,
ContractRight,
AndLeft,
AndLeft1,
AndLeft2,
AndRight,
OrLeft,
OrRight,
OrRight1,
OrRight2,
ImpliesLeft,
ImpliesRight,
NotLeft,
NotRight,
IffLeft,
IffLeft1,
IffLeft2,
IffRight,
FalseLeft,
FalseRight,
TrueLeft,
TrueRight,
Open,
}
const LABELS: [(&str, &str); Rule::ALL.len()] = [
("ax", "ax"),
("WL", "W_L"),
("WR", "W_R"),
("CL", "C_L"),
("CR", "C_R"),
("∧L", "∧_L"),
("∧L_1", "∧_{L1}"),
("∧L_2", "∧_{L2}"),
("∧R", "∧_R"),
("∨L", "∨_L"),
("∨R", "∨_R"),
("∨R_1", "∨_{R1}"),
("∨R_2", "∨_{R2}"),
("→L", "→_L"),
("→R", "→_R"),
("¬L", "¬_L"),
("¬R", "¬_R"),
("↔L", "↔_L"),
("↔L_1", "↔_{L1}"),
("↔L_2", "↔_{L2}"),
("↔R", "↔_R"),
("⊥L", "⊥_L"),
("⊥R", "⊥_R"),
("⊤L", "⊤_L"),
("⊤R", "⊤_R"),
("open", "open"),
];
impl Rule {
pub(crate) const ALL: [Self; 26] = {
use Rule::*;
[
Axiom,
WeakenLeft,
WeakenRight,
ContractLeft,
ContractRight,
AndLeft,
AndLeft1,
AndLeft2,
AndRight,
OrLeft,
OrRight,
OrRight1,
OrRight2,
ImpliesLeft,
ImpliesRight,
NotLeft,
NotRight,
IffLeft,
IffLeft1,
IffLeft2,
IffRight,
FalseLeft,
FalseRight,
TrueLeft,
TrueRight,
Open,
]
};
pub const fn name(self) -> &'static str {
use Rule::*;
match self {
Axiom => "ax",
WeakenLeft => "WL",
WeakenRight => "WR",
ContractLeft => "CL",
ContractRight => "CR",
AndLeft => "∧L",
AndLeft1 => "∧L₁",
AndLeft2 => "∧L₂",
AndRight => "∧R",
OrLeft => "∨L",
OrRight => "∨R",
OrRight1 => "∨R₁",
OrRight2 => "∨R₂",
ImpliesLeft => "→L",
ImpliesRight => "→R",
NotLeft => "¬L",
NotRight => "¬R",
IffLeft => "↔L",
IffLeft1 => "↔L₁",
IffLeft2 => "↔L₂",
IffRight => "↔R",
FalseLeft => "⊥L",
FalseRight => "⊥R",
TrueLeft => "⊤L",
TrueRight => "⊤R",
Open => "open",
}
}
pub const fn is_structural(self) -> bool {
matches!(
self,
Self::WeakenLeft | Self::WeakenRight | Self::ContractLeft | Self::ContractRight
)
}
pub(crate) const fn markup(self, subscript: bool) -> &'static str {
let (upright, lowered) = LABELS[self as usize];
if subscript { lowered } else { upright }
}
}
impl Display for Rule {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
f.write_str(self.name())
}
}
const ASCII: [(&str, Rule); 36] = [
("/\\L", Rule::AndLeft),
("/\\L1", Rule::AndLeft1),
("/\\L2", Rule::AndLeft2),
("/\\R", Rule::AndRight),
("\\/L", Rule::OrLeft),
("\\/R", Rule::OrRight),
("\\/R1", Rule::OrRight1),
("\\/R2", Rule::OrRight2),
("->L", Rule::ImpliesLeft),
("->R", Rule::ImpliesRight),
("~L", Rule::NotLeft),
("~R", Rule::NotRight),
("<->L", Rule::IffLeft),
("<->L1", Rule::IffLeft1),
("<->L2", Rule::IffLeft2),
("<->R", Rule::IffRight),
("andL", Rule::AndLeft),
("andL1", Rule::AndLeft1),
("andL2", Rule::AndLeft2),
("andR", Rule::AndRight),
("orL", Rule::OrLeft),
("orR", Rule::OrRight),
("orR1", Rule::OrRight1),
("orR2", Rule::OrRight2),
("impL", Rule::ImpliesLeft),
("impR", Rule::ImpliesRight),
("notL", Rule::NotLeft),
("notR", Rule::NotRight),
("iffL", Rule::IffLeft),
("iffL1", Rule::IffLeft1),
("iffL2", Rule::IffLeft2),
("iffR", Rule::IffRight),
("falseL", Rule::FalseLeft),
("falseR", Rule::FalseRight),
("trueL", Rule::TrueLeft),
("trueR", Rule::TrueRight),
];
const NAMES: [&str; Rule::ALL.len() - 1] = {
let mut names = [""; Rule::ALL.len() - 1];
let mut i = 0;
while i < names.len() {
names[i] = Rule::ALL[i].name();
i += 1;
}
names
};
impl std::str::FromStr for Rule {
type Err = Error;
fn from_str(text: &str) -> Result<Self, Error> {
let digits = text.replace('1', "₁").replace('2', "₂");
NAMES
.iter()
.position(|&name| name == text || name == digits)
.map(|i| Self::ALL[i])
.or_else(|| {
ASCII
.iter()
.find(|(name, _)| *name == text)
.map(|&(_, rule)| rule)
})
.ok_or_else(|| Error::UnknownName {
what: "rule of LK or LJ",
name: text.into(),
known: &NAMES,
})
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct Inference {
pub(crate) left: Vec<NodeId>,
pub(crate) right: Vec<NodeId>,
pub(crate) rule: Rule,
pub(crate) principal: Option<(Side, usize)>,
pub(crate) premises: Vec<InfId>,
}
impl Inference {
pub fn left(&self) -> &[NodeId] {
&self.left
}
pub fn right(&self) -> &[NodeId] {
&self.right
}
pub const fn rule(&self) -> Rule {
self.rule
}
pub const fn principal(&self) -> Option<(Side, usize)> {
self.principal
}
pub fn premises(&self) -> &[InfId] {
&self.premises
}
pub(crate) fn side(&self, side: Side) -> &[NodeId] {
match side {
Side::Left => &self.left,
Side::Right => &self.right,
}
}
}
#[derive(Clone, Debug)]
pub struct Derivation {
logic: Logic,
formulas: Formulas,
left: Vec<NodeId>,
right: Vec<NodeId>,
inferences: Vec<Inference>,
}
impl Derivation {
pub fn logic(&self) -> Logic {
self.logic
}
pub fn formulas(&self) -> &Formulas {
&self.formulas
}
pub fn inferences(&self) -> &[Inference] {
&self.inferences
}
pub fn term(
&self,
limits: &crate::Limits,
stop: impl FnMut(crate::Progress) -> bool,
) -> Result<crate::lambda::Term, Error> {
crate::lambda::simple::read(self, limits, stop)
}
pub fn inference(&self, id: InfId) -> &Inference {
&self.inferences[id.index()]
}
pub fn root(&self) -> InfId {
InfId::new(self.inferences.len() as u32 - 1)
}
#[cfg(any(feature = "interactive", feature = "serialize"))]
pub(crate) fn from_parts(
logic: Logic,
formulas: Formulas,
(left, right): (Vec<NodeId>, Vec<NodeId>),
inferences: Vec<Inference>,
) -> Self {
Self {
logic,
formulas,
left,
right,
inferences,
}
}
pub fn sequent(&self) -> (&[NodeId], &[NodeId]) {
(&self.left, &self.right)
}
pub fn shown(&self, structural: Structural) -> Cow<'_, Self> {
match structural {
Structural::Explicit => Cow::Borrowed(self),
Structural::Admissible => Cow::Owned(self.admissible().0),
}
}
pub(crate) fn admissible(&self) -> (Self, Vec<InfId>) {
let mut out: Vec<Inference> = Vec::with_capacity(self.inferences.len());
let mut shown: Vec<(InfId, bool)> = Vec::with_capacity(self.inferences.len());
let mut origin = Vec::with_capacity(self.inferences.len());
for (n, inference) in self.inferences.iter().enumerate() {
if inference.rule.is_structural()
&& let [premise] = inference.premises[..]
&& let (above, true) = shown[premise.index()]
&& let Some(principal) = out[above.index()].principal.map_or(Some(None), |(side, at)| {
let id = out[above.index()].side(side)[at];
let found = inference.side(side).iter().position(|&x| x == id);
found.map(|at| Some((side, at)))
})
{
let target = &mut out[above.index()];
target.left.clone_from(&inference.left);
target.right.clone_from(&inference.right);
target.principal = principal;
shown.push((above, true));
continue;
}
let premises = inference
.premises
.iter()
.map(|p| shown[p.index()].0)
.collect();
let id = InfId::new(out.len() as u32);
out.push(Inference {
premises,
..inference.clone()
});
origin.push(InfId::new(n as u32));
let closes = inference.rule != Rule::Open
&& inference.premises.iter().all(|p| shown[p.index()].1);
shown.push((id, closes));
}
let derivation = Self {
logic: self.logic,
formulas: self.formulas.clone(),
left: self.left.clone(),
right: self.right.clone(),
inferences: out,
};
(derivation, origin)
}
pub fn check(
&self,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<(), Error> {
if let Some(limit) = limits.work
&& self.inferences.len() as u64 > limit
{
return Err(Error::Refused(Refusal::Work { limit }));
}
let calculus = self.logic.calculus();
let fail = |n: usize, why: String| Error::ReadBack {
calculus,
reason: format!("inference {n} ({}): {why}", self.inferences[n].rule),
};
let root = self
.inferences
.len()
.checked_sub(1)
.ok_or(Error::ReadBack {
calculus,
reason: "no inference".to_owned(),
})?;
let root_inference = &self.inferences[root];
if !same(&root_inference.left, &self.left) || !same(&root_inference.right, &self.right) {
return Err(fail(
root,
"the root does not conclude the sequent".to_owned(),
));
}
for (n, inference) in self.inferences.iter().enumerate() {
if stop(Progress::new(Phase::Check, 1, n as u64 + 1)) {
return Err(Error::Refused(Refusal::Stopped {
phase: Phase::Check,
}));
}
if inference.premises.iter().any(|p| p.index() >= n) {
return Err(fail(n, "a premise does not precede it".to_owned()));
}
let premises: Vec<&Inference> = inference
.premises
.iter()
.map(|&p| &self.inferences[p.index()])
.collect();
check_inference(&self.formulas, self.logic, inference, &premises)
.map_err(|why| fail(n, why))?;
}
Ok(())
}
}
pub(super) fn check_inference(
formulas: &Formulas,
logic: Logic,
inference: &Inference,
premises: &[&Inference],
) -> Result<(), String> {
use Rule::*;
use Side::{Left, Right};
if inference.rule == Open {
return Err("an open goal".to_owned());
}
if logic != Logic::Classical && inference.right.len() > 1 {
return Err("more than one formula right of ⊢".to_owned());
}
if logic == Logic::Minimal && inference.right.is_empty() {
return Err("no formula right of ⊢ in minimal logic".to_owned());
}
let f = formulas;
let count = |n: usize| {
if premises.len() == n {
Ok(())
} else {
Err(format!("{} premises instead of {n}", premises.len()))
}
};
if inference.rule == Axiom {
count(0)?;
return match (&inference.left[..], &inference.right[..]) {
([a], [b]) if a == b && inference.principal.is_none() => Ok(()),
_ => Err("not a sequent A ⊢ A".to_owned()),
};
}
let Some((side, at)) = inference.principal else {
return Err("no principal formula".to_owned());
};
let principal = *inference
.side(side)
.get(at)
.ok_or("the principal position lies outside the sequent")?;
let node = f.node(principal);
let mut context = (inference.left.clone(), inference.right.clone());
match side {
Left => context.0.remove(at),
Right => context.1.remove(at),
};
let with = |added: &[(Side, NodeId)]| {
let mut sequent = context.clone();
for &(side, id) in added {
match side {
Left => sequent.0.push(id),
Right => sequent.1.push(id),
}
}
sequent
};
let unary = |added: &[(Side, NodeId)]| {
count(1)?;
if is(premises[0], &with(added)) {
Ok(())
} else {
Err("the premise is not what the rule makes of the conclusion".to_owned())
}
};
let binary = |first: &[(Side, NodeId)], second: &[(Side, NodeId)]| {
count(2)?;
if is(premises[0], &with(first)) && is(premises[1], &with(second)) {
return Ok(());
}
let rest = |p: &Inference, added: &[(Side, NodeId)]| {
let mut left = p.left.clone();
let mut right = p.right.clone();
for &(side, id) in added {
let list = if side == Left { &mut left } else { &mut right };
let i = list.iter().position(|&x| x == id)?;
list.remove(i);
}
Some((left, right))
};
if let (Some(mut a), Some(b)) = (rest(premises[0], first), rest(premises[1], second)) {
a.0.extend(b.0);
a.1.extend(b.1);
if same(&a.0, &context.0) && same(&a.1, &context.1) {
return Ok(());
}
}
Err("the premises do not share or split the context".to_owned())
};
let leaf = || count(0);
match (inference.rule, side, node) {
(WeakenLeft, Left, _) | (WeakenRight, Right, _) => unary(&[]),
(ContractLeft, Left, _) => unary(&[(Left, principal), (Left, principal)]),
(ContractRight, Right, _) => unary(&[(Right, principal), (Right, principal)]),
(AndLeft, Left, Node::And(a, b)) => unary(&[(Left, a), (Left, b)]),
(AndLeft1, Left, Node::And(a, _)) => unary(&[(Left, a)]),
(AndLeft2, Left, Node::And(_, b)) => unary(&[(Left, b)]),
(AndRight, Right, Node::And(a, b)) => binary(&[(Right, a)], &[(Right, b)]),
(OrLeft, Left, Node::Or(a, b)) => binary(&[(Left, a)], &[(Left, b)]),
(OrRight, Right, Node::Or(a, b)) => unary(&[(Right, a), (Right, b)]),
(OrRight1, Right, Node::Or(a, _)) => unary(&[(Right, a)]),
(OrRight2, Right, Node::Or(_, b)) => unary(&[(Right, b)]),
(ImpliesLeft, Left, Node::Implies(a, b)) => binary(&[(Right, a)], &[(Left, b)]),
(ImpliesRight, Right, Node::Implies(a, b)) => unary(&[(Left, a), (Right, b)]),
(NotRight, Right, Node::Not(a)) if logic == Logic::Classical => unary(&[(Left, a)]),
(NotLeft, Left, Node::Not(_)) if logic == Logic::Classical && premises.len() != 1 => {
Err("LK's ¬L has one premise".to_owned())
}
(NotRight, Right, Node::Not(a)) => unary(&[(Left, a)]).or_else(|_| {
let falsity = formulas.ids.get(&Node::False).copied();
unary(&[
(Left, a),
(Right, falsity.ok_or("no ⊥ for the form of →R")?),
])
}),
(NotLeft, Left, Node::Not(a)) if premises.len() == 1 => unary(&[(Right, a)]),
(NotLeft, Left, Node::Not(a)) => {
let falsity = formulas.ids.get(&Node::False).copied();
let falsity = falsity.ok_or("no ⊥ for the form of →L")?;
binary(&[(Right, a)], &[(Left, falsity)])
}
(IffLeft | IffLeft1 | IffLeft2 | IffRight, _, Node::Iff(a, b)) => {
let forward = formulas.ids.get(&Node::Implies(a, b)).copied();
let backward = formulas.ids.get(&Node::Implies(b, a)).copied();
let (Some(forward), Some(backward)) = (forward, backward) else {
return Err("the implications of the equivalence are missing".to_owned());
};
match (inference.rule, side) {
(IffLeft, Left) => unary(&[(Left, forward), (Left, backward)]),
(IffLeft1, Left) => unary(&[(Left, forward)]),
(IffLeft2, Left) => unary(&[(Left, backward)]),
(IffRight, Right) => binary(&[(Right, forward)], &[(Right, backward)]),
_ => Err("the rule does not apply on this side".to_owned()),
}
}
(FalseLeft, Left, Node::False) if logic != Logic::Minimal => leaf(),
(FalseLeft, ..) if logic == Logic::Minimal => {
Err("minimal logic has no ex falso".to_owned())
}
(FalseRight, Right, Node::False) | (TrueLeft, Left, Node::True) => unary(&[]),
(TrueRight, Right, Node::True) => leaf(),
_ => Err("the rule does not apply to the principal formula".to_owned()),
}
}
impl Derivation {
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),
)
}
pub fn write_steps(
&self,
out: &mut impl Write,
stop: impl FnMut(crate::limits::Progress) -> bool,
) -> Result<(), Error> {
crate::linear::proofs::fmt::write_steps(
self,
out,
crate::limits::counting(stop, crate::limits::Phase::Write),
)
}
}
impl Display for Derivation {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.write_text(&TextOptions::default(), f, |_| false)
.map_err(|_| std::fmt::Error)
}
}
impl Drawn for Derivation {
const RULES: usize = Rule::ALL.len();
const OPEN: Option<usize> = Some(Rule::Open as usize);
fn markup(rule: usize, labels: &Labels) -> Option<&str> {
let rule = Rule::ALL[rule];
match labels {
_ if rule == Rule::Open => None,
Labels::Upright | Labels::Table(_) => Some(rule.markup(false)),
Labels::Subscript => Some(rule.markup(true)),
Labels::Off => None,
}
}
fn len(&self) -> usize {
self.inferences.len()
}
fn root(&self) -> InfId {
Derivation::root(self)
}
fn premises(&self, id: InfId) -> &[InfId] {
&self.inference(id).premises
}
fn rule(&self, id: InfId) -> usize {
self.inference(id).rule as usize
}
fn name(&self, id: InfId) -> &'static str {
self.inference(id).rule.name()
}
fn times(&self, _: InfId) -> u32 {
1
}
fn write_sequent(&self, out: &mut impl Write, id: InfId) -> FmtResult {
let inference = self.inference(id);
let sides = (&inference.left[..], &inference.right[..]);
TEXT.ordinary(out, &self.formulas, sides, false, false)
}
#[cfg(any(feature = "latex", feature = "typst", feature = "svg"))]
fn sequent(
&self,
out: &mut String,
notation: &Notation,
id: InfId,
aligned: bool,
marks: bool,
) {
let inference = self.inference(id);
let sides = (&inference.left[..], &inference.right[..]);
notation
.ordinary(out, &self.formulas, sides, aligned, marks)
.unwrap();
}
#[cfg(feature = "svg")]
fn positions(&self, id: InfId) -> Vec<usize> {
let inference = self.inference(id);
(0..inference.left.len() + inference.right.len()).collect()
}
}
pub(super) fn same(a: &[NodeId], b: &[NodeId]) -> bool {
const SHORT: usize = 16;
if a.len() != b.len() {
return false;
}
if a == b {
return true;
}
if a.len() <= SHORT {
let count = |list: &[NodeId], x: NodeId| list.iter().filter(|&&y| y == x).count();
return a.iter().all(|&x| count(a, x) == count(b, x));
}
let (mut a, mut b) = (a.to_vec(), b.to_vec());
a.sort_unstable();
b.sort_unstable();
a == b
}
fn is(inference: &Inference, sequent: &(Vec<NodeId>, Vec<NodeId>)) -> bool {
same(&inference.left, &sequent.0) && same(&inference.right, &sequent.1)
}
struct Unwound {
chain: Vec<(NodeId, Side)>,
core: (NodeId, u8, Side),
}
#[derive(Clone, Copy, Debug)]
struct Tag {
node: NodeId,
function: u8,
bangs: u8,
side: Side,
}
impl Image {
pub(crate) fn linear_derivation<'p>(
&self,
proof: &'p Proof,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<crate::linear::Derivation<'p>, Error> {
let sides = if self.mode.intuitionistic {
Sides::Two
} else {
Sides::One
};
let view = ViewOptions::default()
.with_compact(Compact::Never)
.with_sides(sides);
proof.derivation_within(&view, limits, stop)
}
#[expect(
clippy::missing_panics_doc,
reason = "the expects state that the forest's preorder tags a parent before its children, which the walk establishes"
)]
pub fn read_back(
&self,
proof: &Proof,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Derivation, Error> {
if proof.goal().is_some() {
return Err(Error::GoalProof);
}
let linear = &self.linear_derivation(proof, limits, &mut stop)?;
let calculus = self.logic.calculus();
let fail = |reason: String| Error::ReadBack { calculus, reason };
let forest = linear.forest();
if forest.sequent() != &self.sequent {
return Err(fail("the proof is not of the image".to_owned()));
}
let formulas = &self.ordinary.formulas;
let mut tags: Vec<Option<Tag>> = vec![None; forest.len()];
for (&root, info) in forest.roots().iter().zip(&self.roots) {
tags[root.index()] = Some(Tag {
node: info.node,
function: info.function,
bangs: info.bangs,
side: info.side,
});
}
for o in forest.ids() {
let tag = tags[o.index()].expect("a parent is tagged before its children");
if tag.bangs > 0 {
if let Some(child) = forest.left(o) {
tags[child.index()] = Some(Tag {
bangs: tag.bangs - 1,
..tag
});
}
continue;
}
let (node, function, side) = self.unwind(tag.node, tag.function, tag.side).core;
let p = pattern(
formulas,
&self.extra,
self.translation,
self.logic,
node,
function,
);
for (k, child) in forest.children(o).enumerate() {
let Some((x, fx, extra)) = p.operands[k] else {
return Err(fail(format!("occurrence {} has no operand {k}", o.index())));
};
let px = pattern(formulas, &self.extra, self.translation, self.logic, x, fx);
let flips = match p.core {
Core::Lollipop => k == 0,
Core::Atom
| Core::Unit(_)
| Core::Tensor
| Core::Par
| Core::With
| Core::Plus
| Core::Pass => false,
};
let side = if self.translation == Translation::Affine {
if fx == 0 { Side::Right } else { Side::Left }
} else if flips {
side.flip()
} else {
side
};
tags[child.index()] = Some(Tag {
node: x,
function: fx,
bangs: px.bangs + extra,
side,
});
}
}
let tag = |o: OccId| tags[o.index()].expect("every occurrence is tagged");
let mut out = Vec::new();
let mut mapped: Vec<InfId> = Vec::with_capacity(linear.inferences().len());
for (i, inference) in linear.inferences().iter().enumerate() {
if stop(Progress::new(Phase::ReadBack, 1, i as u64 + 1)) {
return Err(Error::Refused(Refusal::Stopped {
phase: Phase::ReadBack,
}));
}
let members: Vec<(NodeId, Side)> = inference
.sequent
.iter()
.map(|&o| (tag(o.occ()).node, tag(o.occ()).side))
.collect();
let premises: Vec<InfId> = inference
.premises
.iter()
.map(|p| mapped[p.index()])
.collect();
let rule = inference.rule.rule;
let next = match rule {
Linear::Promotion | Linear::Dereliction => premises[0],
Linear::Contraction | Linear::Weakening | Linear::AffineWeakening => {
let at = inference
.principal
.expect("a structural rule has a principal formula");
let (_, side) = members[at];
let rule = match (rule, side) {
(Linear::Contraction, Side::Left) => Rule::ContractLeft,
(Linear::Contraction, Side::Right) => Rule::ContractRight,
(_, Side::Left) => Rule::WeakenLeft,
(_, Side::Right) => Rule::WeakenRight,
};
push(&mut out, &members, at, rule, premises)
}
Linear::Forall | Linear::Exists => {
return Err(fail(
"a quantifier, which the read-back has no rule for".to_owned(),
));
}
Linear::Cut => {
return Err(fail(
"a cut, which the read-back has no rule for".to_owned(),
));
}
Linear::Ax => {
let mut members = members;
let chains: Vec<_> = (0..2)
.map(|at| {
let (node, side) = members[at];
let Unwound { chain, core } = self.unwind(node, 0, side);
members[at] = (core.0, core.2);
(at, chain)
})
.collect();
let mut id = push(&mut out, &members, usize::MAX, Rule::Axiom, premises);
for (at, chain) in chains {
id = negations(&mut out, &mut members, at, chain, id);
}
id
}
rule @ Linear::Tensor
| rule @ Linear::Par
| rule @ Linear::One
| rule @ Linear::Bot
| rule @ Linear::With
| rule @ Linear::PlusLeft
| rule @ Linear::PlusRight
| rule @ Linear::Top
| rule @ Linear::Mix
| rule @ Linear::Open => {
let at = inference
.principal
.ok_or_else(|| fail("no principal formula".to_owned()))?;
let mut members = members;
let (node, side) = members[at];
let Unwound { chain, core } = self.unwind(node, 0, side);
members[at] = (core.0, core.2);
let ordinary = self
.rule_of(formulas.node(core.0), core.2, rule)
.ok_or_else(|| {
fail(format!(
"the linear rule {rule} on {} has no reading",
formulas.formula(core.0)
))
})?;
let id = push(&mut out, &members, at, ordinary, premises);
negations(&mut out, &mut members, at, chain, id)
}
};
mapped.push(next);
}
Ok(Derivation {
logic: self.logic,
formulas: self.ordinary.formulas.clone(),
left: self.ordinary.left.clone(),
right: self.ordinary.right.clone(),
inferences: out,
})
}
fn unwind(&self, mut node: NodeId, mut function: u8, mut side: Side) -> Unwound {
let mut chain = Vec::new();
if self.translation == Translation::Affine {
while let Node::Not(a) = self.ordinary.formulas.node(node) {
chain.push((node, side));
node = a;
side = side.flip();
function = 1 - function;
}
}
Unwound {
chain,
core: (node, function, side),
}
}
fn rule_of(&self, node: Node, side: Side, rule: Linear) -> Option<Rule> {
use Linear as L;
use Side::{Left, Right};
Some(match (node, side, rule) {
(Node::And(..), Right, L::With | L::Tensor) => Rule::AndRight,
(Node::And(..), Left, L::Par) => Rule::AndLeft,
(Node::And(..), Left, L::PlusLeft) => Rule::AndLeft1,
(Node::And(..), Left, L::PlusRight) => Rule::AndLeft2,
(Node::Or(..), Right, L::Par) => Rule::OrRight,
(Node::Or(..), Right, L::PlusLeft) => Rule::OrRight1,
(Node::Or(..), Right, L::PlusRight) => Rule::OrRight2,
(Node::Or(..), Left, L::With) => Rule::OrLeft,
(Node::Implies(..), Right, L::Par) => Rule::ImpliesRight,
(Node::Implies(..), Left, L::Tensor | L::With) => Rule::ImpliesLeft,
(Node::Not(_), Right, L::Par) => Rule::NotRight,
(Node::Not(_), Left, L::Tensor) => Rule::NotLeft,
(Node::Iff(..), Right, L::With | L::Tensor) => Rule::IffRight,
(Node::Iff(..), Left, L::Par) => Rule::IffLeft,
(Node::Iff(..), Left, L::PlusLeft) => Rule::IffLeft1,
(Node::Iff(..), Left, L::PlusRight) => Rule::IffLeft2,
(Node::True, Right, L::Top | L::One) => Rule::TrueRight,
(Node::True, Left, L::Bot) => Rule::TrueLeft,
(Node::False, Left, L::Top) => Rule::FalseLeft,
(Node::False, Right, L::Bot) => Rule::FalseRight,
_ => return None,
})
}
}
fn push(
out: &mut Vec<Inference>,
members: &[(NodeId, Side)],
at: usize,
rule: Rule,
premises: Vec<InfId>,
) -> InfId {
let lefts = members
.iter()
.filter(|&&(_, side)| side == Side::Left)
.count();
let (mut left, mut right) = (
Vec::with_capacity(lefts),
Vec::with_capacity(members.len() - lefts),
);
let mut principal = None;
for (i, &(node, side)) in members.iter().enumerate() {
let list = if side == Side::Left {
&mut left
} else {
&mut right
};
if i == at {
principal = Some((side, list.len()));
}
list.push(node);
}
out.push(Inference {
left,
right,
rule,
principal,
premises,
});
InfId::new(out.len() as u32 - 1)
}
fn negations(
out: &mut Vec<Inference>,
members: &mut [(NodeId, Side)],
at: usize,
chain: Vec<(NodeId, Side)>,
mut id: InfId,
) -> InfId {
for (node, side) in chain.into_iter().rev() {
members[at] = (node, side);
let rule = match side {
Side::Left => Rule::NotLeft,
Side::Right => Rule::NotRight,
};
id = push(out, members, at, rule, vec![id]);
}
id
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::super::{Sequent, translate};
use super::*;
use crate::linear::{Options, Verdict, prove};
#[test]
fn text_tree() {
let sequent: Sequent = "a -> b, b -> c |- a -> c".parse().unwrap();
let image = translate(
&sequent,
Logic::Intuitionistic,
Translation::CallByName,
&crate::Limits::default(),
)
.unwrap();
let outcome = prove(image.sequent(), image.mode(), &Options::default()).unwrap();
let Verdict::Proved(proof) = &outcome.verdict else {
panic!("provable");
};
let derivation = image
.read_back(proof, &crate::Limits::default(), |_| false)
.unwrap();
let tree = derivation.to_string();
assert_eq!(
tree,
"───── ax ───── ax\n\
a ⊢ a b ⊢ b\n\
──────────────── →L ───── ax\n\
\x20 a → b, a ⊢ b c ⊢ c\n\
\x20 ───────────────────────── →L\n\
\x20 a → b, b → c, a ⊢ c\n\
\x20 ──────────────────── →R\n\
\x20 a → b, b → c ⊢ a → c"
);
let width = tree.lines().map(|l| l.chars().count()).max();
let size = derivation.text_size(&crate::linear::proofs::TextOptions::default());
assert_eq!(Some(size), width.map(|w| (w, tree.lines().count())));
let root = derivation.inferences().last().unwrap();
assert_eq!(root.rule(), Rule::ImpliesRight);
assert_eq!((root.left().len(), root.right().len()), (2, 1));
assert_eq!(root.principal(), Some((Side::Right, 0)));
assert_eq!(root.premises(), [InfId::new(4)]);
let mut steps = String::new();
derivation.write_steps(&mut steps, |_| false).unwrap();
assert_eq!(steps.lines().count(), 6);
assert_eq!(
steps.lines().last(),
Some("6. a → b, b → c ⊢ a → c, by →R from 5.")
);
}
#[test]
fn minimal_logic_refuses_an_empty_right_side() {
let sequent: Sequent = "a, ~a |- b".parse().unwrap();
let f = sequent.formulas();
let (a, not_a, b) = (sequent.left()[0], sequent.left()[1], sequent.right()[0]);
let inference = |left: Vec<NodeId>, right, rule, principal, premises: &[u32]| Inference {
left,
right,
rule,
principal,
premises: premises.iter().map(|&p| InfId::new(p)).collect(),
};
let forged = |logic| Derivation {
logic,
formulas: f.clone(),
left: vec![a, not_a],
right: vec![b],
inferences: vec![
inference(vec![a], vec![a], Rule::Axiom, None, &[]),
inference(
vec![a, not_a],
vec![],
Rule::NotLeft,
Some((Side::Left, 1)),
&[0],
),
inference(
vec![a, not_a],
vec![b],
Rule::WeakenRight,
Some((Side::Right, 0)),
&[1],
),
],
};
let unbounded = crate::Limits::default();
assert!(
forged(Logic::Intuitionistic)
.check(&unbounded, |_| false)
.is_ok()
);
assert!(matches!(
forged(Logic::Minimal).check(&unbounded, |_| false),
Err(Error::ReadBack { .. })
));
}
#[test]
fn labels_are_the_names() {
use crate::linear::proofs::style::plain;
for (i, rule) in Rule::ALL.into_iter().enumerate() {
assert_eq!(rule as usize, i, "{rule}");
assert_eq!(plain(rule.markup(false)), rule.name(), "{rule}");
assert_eq!(plain(rule.markup(true)), rule.name(), "{rule}");
}
}
#[test]
fn rules_read_from_their_names() {
for rule in &Rule::ALL[..Rule::ALL.len() - 1] {
assert_eq!(rule.name().parse::<Rule>().unwrap(), *rule);
}
for (name, rule) in super::ASCII {
assert_eq!(name.parse::<Rule>().unwrap(), rule, "{name}");
}
assert_eq!("∨R2".parse::<Rule>().unwrap(), Rule::OrRight2);
for refused in ["open", "⊗", "and", "-oL"] {
assert!(matches!(
refused.parse::<Rule>(),
Err(Error::UnknownName { .. })
));
}
}
#[test]
fn a_goal_proof_reads_back_as_nothing() {
let sequent: Sequent = "a, b |- a".parse().unwrap();
let image = translate(
&sequent,
Logic::Intuitionistic,
Translation::CallByName,
&crate::Limits::default(),
)
.unwrap();
let forest = crate::linear::Forest::new(image.sequent()).unwrap();
let roots = forest.roots();
let goal = [
crate::linear::Member::from(roots[0]),
crate::linear::Member::from(roots[2]),
];
let limits = crate::Limits::default();
let outcome = crate::linear::search::prove_goal(
crate::linear::search::Goal::new(&forest, &goal).unwrap(),
image.mode(),
&Options::default(),
&limits,
|_| false,
)
.unwrap();
let Verdict::Proved(proof) = &outcome.verdict else {
panic!("a ⊢ a is provable");
};
assert_eq!(
image.read_back(proof, &limits, |_| false).unwrap_err(),
Error::GoalProof
);
}
#[test]
fn same_compares_multisets() {
let ids = |list: &[u32]| list.iter().map(|&i| NodeId(i)).collect::<Vec<_>>();
let long: Vec<u32> = (0..40).map(|i| i % 7).collect();
let reversed: Vec<u32> = long.iter().rev().copied().collect();
let mut other = long.clone();
other[0] = 6;
for (a, b, equal) in [
(&[1, 2, 2][..], &[2, 1, 2][..], true),
(&[1, 2, 2], &[1, 1, 2], false),
(&[1, 2], &[1, 2, 2], false),
(&long, &reversed, true),
(&long, &other, false),
] {
assert_eq!(same(&ids(a), &ids(b)), equal, "{a:?} {b:?}");
}
}
#[test]
fn the_checker_refuses_each_break() {
let sequent: Sequent = "a -> b, b -> c |- a -> c".parse().unwrap();
let image = translate(
&sequent,
Logic::Intuitionistic,
Translation::CallByName,
&crate::Limits::default(),
)
.unwrap();
let outcome = prove(image.sequent(), image.mode(), &Options::default()).unwrap();
let Verdict::Proved(proof) = &outcome.verdict else {
panic!("provable");
};
let unbounded = crate::Limits::default();
let derivation = image.read_back(proof, &unbounded, |_| false).unwrap();
assert_eq!(derivation.check(&unbounded, |_| false), Ok(()));
let rules: Vec<Rule> = derivation.inferences.iter().map(|i| i.rule).collect();
let at = |rule| rules.iter().position(|&r| r == rule).unwrap();
let (axiom, left, right) = (
at(Rule::Axiom),
at(Rule::ImpliesLeft),
at(Rule::ImpliesRight),
);
let root = rules.len() - 1;
type Break = (&'static str, Box<dyn Fn(&mut Derivation)>);
let broken: [Break; 12] = [
(
"an open goal",
Box::new(move |d| d.inferences[axiom].rule = Rule::Open),
),
("the root does not conclude", Box::new(|d| d.right.clear())),
(
"not a sequent A ⊢ A",
Box::new(move |d| d.inferences[axiom].principal = Some((Side::Left, 0))),
),
(
"a premise does not precede",
Box::new(move |d| {
d.inferences[left].premises[0] = InfId::new(root as u32);
}),
),
(
"more than one formula right",
Box::new(move |d| {
let extra = d.inferences[axiom].left[0];
d.inferences[axiom].right.push(extra);
}),
),
(
"not a sequent A ⊢ A",
Box::new(move |d| {
let other = d.inferences[right].right[0];
d.inferences[axiom].right[0] = other;
}),
),
(
"no principal formula",
Box::new(move |d| d.inferences[left].principal = None),
),
(
"lies outside the sequent",
Box::new(move |d| {
d.inferences[left].principal = Some((Side::Left, 9));
}),
),
(
"premises instead of 2",
Box::new(move |d| {
d.inferences[left].premises.pop();
}),
),
(
"do not share or split",
Box::new(move |d| d.inferences[left].premises.reverse()),
),
(
"does not apply to the principal",
Box::new(move |d| {
d.inferences[right].rule = Rule::AndRight;
}),
),
(
"not what the rule makes",
Box::new(move |d| {
d.inferences[right].premises[0] = InfId::new(axiom as u32);
}),
),
];
for (why, mutate) in &broken {
let mut d = derivation.clone();
mutate(&mut d);
match d.check(&unbounded, |_| false) {
Err(Error::ReadBack { reason, .. }) => {
assert!(reason.contains(why), "{why}: {reason}")
}
other => panic!("{why}: {other:?}"),
}
}
let read = |input: &str, logic, translation| {
let sequent: Sequent = input.parse().unwrap();
let image = translate(&sequent, logic, translation, &crate::Limits::default()).unwrap();
let outcome = prove(image.sequent(), image.mode(), &Options::default()).unwrap();
let Verdict::Proved(proof) = &outcome.verdict else {
panic!("{input} is provable");
};
let derivation = image.read_back(proof, &unbounded, |_| false).unwrap();
assert_eq!(derivation.check(&unbounded, |_| false), Ok(()), "{input}");
derivation
};
let reason = |d: &Derivation| match d.check(&unbounded, |_| false) {
Err(Error::ReadBack { reason, .. }) => reason,
other => panic!("{other:?}"),
};
let cbn = Translation::CallByName;
let mut shared = read("a, b |- a /\\ b", Logic::Intuitionistic, cbn);
let and = shared
.inferences
.iter()
.position(|i| i.rule == Rule::AndRight)
.unwrap();
let first = shared.inferences[and].premises[0];
shared.inferences[and].premises[1] = first;
assert!(reason(&shared).contains("do not share or split"));
let mut minimal = read("a -> b, b -> c |- a -> c", Logic::Minimal, cbn);
let leaf = minimal
.inferences
.iter()
.position(|i| i.rule == Rule::Axiom)
.unwrap();
minimal.inferences[leaf].rule = Rule::FalseLeft;
minimal.inferences[leaf].principal = Some((Side::Left, 0));
assert!(reason(&minimal).contains("minimal logic has no ex falso"));
let falsity = read("a |- a, false", Logic::Classical, Translation::Affine);
assert!(
falsity
.inferences
.iter()
.any(|i| i.rule == Rule::FalseRight)
);
let mut split = derivation.clone();
let extra = split.inferences[axiom].left[0];
split.inferences[left].left.push(extra);
let at_split = format!("inference {left} (→L): the premises do not share or split");
assert!(reason(&split).starts_with(&at_split), "{}", reason(&split));
let base = read("a -> b, a |- b", Logic::Classical, Translation::Affine);
let atom = |i| base.formulas.ids[&Node::Atom(i)];
let (a, b) = (atom(0), atom(1));
let sides = [
(Rule::ContractLeft, Rule::WeakenLeft, Side::Left),
(Rule::ContractRight, Rule::WeakenRight, Side::Right),
];
for (contract, weaken, side) in sides {
let with_b = match side {
Side::Left => (vec![a, b], vec![a]),
Side::Right => (vec![a], vec![a, b]),
};
let make = |rule, premises: Vec<InfId>| Inference {
left: with_b.0.clone(),
right: with_b.1.clone(),
rule,
principal: Some((side, 1)),
premises,
};
let axiom = Inference {
left: vec![a],
right: vec![a],
rule: Rule::Axiom,
principal: None,
premises: Vec::new(),
};
let once = make(weaken, vec![InfId::new(0)]);
for inferences in [
vec![axiom.clone(), make(contract, vec![InfId::new(0)])],
vec![axiom, once, make(contract, vec![InfId::new(1)])],
] {
let mut contracted = base.clone();
let root = inferences.len() - 1;
contracted.inferences = inferences;
(contracted.left, contracted.right) = with_b.clone();
let expected = format!("inference {root} ({contract}): the premise is not what");
assert!(reason(&contracted).starts_with(&expected), "{contract}");
}
}
let one = unbounded.with_work(Some(1));
assert_eq!(
derivation.check(&one, |_| false),
Err(Error::Refused(Refusal::Work { limit: 1 }))
);
let enough = unbounded.with_work(Some(derivation.inferences.len() as u64));
assert_eq!(derivation.check(&enough, |_| false), Ok(()));
assert_eq!(
derivation.check(&unbounded, |_| true),
Err(Error::Refused(Refusal::Stopped {
phase: Phase::Check
}))
);
assert_eq!(
image
.read_back(proof, &unbounded, |p| p.phase == Phase::ReadBack)
.unwrap_err(),
Error::Refused(Refusal::Stopped {
phase: Phase::ReadBack
})
);
}
}