#![deny(clippy::wildcard_enum_match_arm)]
pub mod cut;
pub(crate) mod essential;
mod graph;
mod mell;
mod sequentialize;
mod skeleton;
pub use graph::Scratch;
pub use mell::{MellStructure, Parts, Placed, Placement};
use crate::Error;
use crate::errors::describe::{Budget, Limit, Names, cut as clipped};
use crate::errors::{Described, Owner, Subject};
use crate::limits::{Limits, Phase, Progress, Refusal, Space};
use crate::linear::fragment::{Fragment, Mode, Order};
use crate::linear::occurrences::{Forest, OccId, OccSet, ShapeError};
use crate::linear::proofs::{Node, NodeId, Proof};
use crate::linear::sequents::{Kind, Sequent, Term};
use graph::Graph;
use skeleton::Skeleton;
use std::fmt::{Display, Formatter, Result as FmtResult, Write};
const NONE: u32 = u32::MAX;
const MOST: u64 = (u32::MAX / 3 - 1) as u64;
pub(crate) const fn fits(occurrences: usize) -> Result<(), Error> {
if occurrences as u64 > MOST {
Err(Error::Refused(Refusal::Index {
what: Space::Vertex,
count: occurrences as u64,
most: MOST,
}))
} else {
Ok(())
}
}
pub fn exist(fragment: Fragment, mode: Mode) -> Result<(), NetError> {
has_nets(fragment)?;
Criterion::of(mode).map(|_| ())
}
fn has_nets(fragment: Fragment) -> Result<(), NetError> {
if fragment.has_nets() {
Ok(())
} else {
Err(NetError::Fragment { fragment })
}
}
const STRUCTURE_BYTES: u64 = 25 + 4 + 4 + 12 + 5 + 4;
const SCRATCH_BYTES: u64 = 3 + 16 + 1 + 8 + 1;
const SEQUENTIALIZE_BYTES: u64 = 25 + 16 + SCRATCH_BYTES + 8;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct VertexId(u32);
impl VertexId {
pub const fn new(index: u32) -> Self {
Self(index)
}
pub const fn get(self) -> u32 {
self.0
}
pub const fn index(self) -> usize {
self.0 as usize
}
pub(crate) const fn of(o: OccId) -> Self {
Self(o.get())
}
pub(crate) const fn occ(self) -> OccId {
OccId::new(self.0)
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
pub struct Criterion {
pub mix: bool,
pub order: Order,
}
impl Criterion {
pub const MLL: Self = Self {
mix: false,
order: Order::Commutative,
};
pub const CYCLIC: Self = Self {
mix: false,
order: Order::Cyclic,
};
#[must_use]
pub const fn with_mix(self) -> Self {
Self { mix: true, ..self }
}
pub fn of(mode: Mode) -> Result<Self, NetError> {
if mode.is_affine() || (mode.is_ordered() && mode.check().is_err()) {
return Err(NetError::Mode { mode });
}
Ok(Self {
mix: mode.has_mix(),
order: mode.order(),
})
}
const fn mode(self) -> Mode {
match (self.order, self.mix) {
(Order::Cyclic, _) => Mode::CYCLIC,
(Order::Commutative, true) => Mode::CLASSICAL.with_mix(),
(Order::Commutative, false) => Mode::CLASSICAL,
}
}
}
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum NetError {
#[non_exhaustive]
NoVertex {
vertex: u32,
vertices: u32,
},
#[non_exhaustive]
NotLiteral {
vertex: VertexId,
},
#[non_exhaustive]
NotDual {
x: VertexId,
y: VertexId,
},
#[non_exhaustive]
LinkedTwice {
vertex: VertexId,
},
#[non_exhaustive]
Unlinked {
vertex: VertexId,
},
Empty,
#[non_exhaustive]
SwitchingCycle {
cycle: Vec<VertexId>,
},
#[non_exhaustive]
Disconnected {
parts: Vec<Vec<VertexId>>,
},
#[non_exhaustive]
DirectedCycle {
cycle: Vec<VertexId>,
},
#[non_exhaustive]
NoDominator {
implication: VertexId,
path: Vec<VertexId>,
},
#[non_exhaustive]
Crossing {
links: [(VertexId, VertexId); 2],
},
#[non_exhaustive]
NotIntuitionistic {
shape: ShapeError,
},
#[non_exhaustive]
Fragment {
fragment: Fragment,
},
#[non_exhaustive]
Mode {
mode: Mode,
},
#[non_exhaustive]
Rule {
node: NodeId,
rule: &'static str,
},
#[non_exhaustive]
Placement {
vertex: VertexId,
fault: Placement,
},
#[non_exhaustive]
Unattached {
vertex: VertexId,
},
#[non_exhaustive]
InBox {
door: VertexId,
error: Box<NetError>,
},
#[non_exhaustive]
NotMell {
fragment: Fragment,
mode: Mode,
},
#[non_exhaustive]
NoCut {
vertex: Option<VertexId>,
},
#[non_exhaustive]
Reduction {
error: Box<NetError>,
},
#[non_exhaustive]
Refused {
refusal: Refusal,
},
}
impl NetError {
pub fn kind(&self) -> crate::ErrorKind {
use crate::ErrorKind::*;
match self {
Self::NoVertex { .. }
| Self::NotLiteral { .. }
| Self::NotDual { .. }
| Self::LinkedTwice { .. }
| Self::Placement { .. } => Malformed,
Self::InBox { error, .. } => error.kind(),
Self::Unlinked { .. }
| Self::Unattached { .. }
| Self::Empty
| Self::SwitchingCycle { .. }
| Self::Disconnected { .. }
| Self::DirectedCycle { .. }
| Self::NoDominator { .. }
| Self::Crossing { .. } => Invalid,
Self::Fragment { .. }
| Self::Mode { .. }
| Self::Rule { .. }
| Self::NotMell { .. }
| Self::NotIntuitionistic { .. }
| Self::NoCut { .. } => Unsupported,
Self::Reduction { .. } => crate::ErrorKind::Defect,
Self::Refused { refusal } => crate::errors::refusal_kind(refusal),
}
}
pub fn code(&self) -> &'static str {
match self {
Self::Fragment { .. }
| Self::Mode { .. }
| Self::Rule { .. }
| Self::NotMell { .. } => "no_nets",
Self::InBox { error, .. } => error.code(),
Self::NotIntuitionistic { .. } => "not_intuitionistic",
Self::NoCut { .. } => "no_cut",
Self::Reduction { .. } => "reduction_rejected",
Self::Refused { refusal } => refusal.code(),
Self::NoVertex { .. }
| Self::NotLiteral { .. }
| Self::NotDual { .. }
| Self::LinkedTwice { .. }
| Self::Placement { .. }
| Self::Unlinked { .. }
| Self::Unattached { .. }
| Self::Empty
| Self::SwitchingCycle { .. }
| Self::Disconnected { .. }
| Self::DirectedCycle { .. }
| Self::NoDominator { .. }
| Self::Crossing { .. } => "invalid_net",
}
}
pub fn describe<'a>(&'a self, owner: &'a impl Owner) -> Described<'a> {
Described::new(Subject::Net(self), owner)
}
pub(crate) fn write(
&self,
f: &mut Formatter<'_>,
names: Option<Names<'_>>,
limit: Limit,
) -> FmtResult {
self.write_over(f, names, None, limit)
}
pub(crate) fn write_over(
&self,
f: &mut Formatter<'_>,
names: Option<Names<'_>>,
vertices: Option<&[OccId]>,
limit: Limit,
) -> FmtResult {
let vertex = |v: &VertexId| {
let o = match vertices {
Some(table) => table.get(v.index()).copied(),
None => names.and_then(|n| (v.index() < n.forest.len()).then(|| v.occ())),
};
match (names, o) {
(Some(names), Some(o)) => {
let mut formula = String::new();
clipped(&mut formula, Some(names), o.into(), limit).unwrap();
format!("{formula}[{}]", v.get())
}
_ => v.get().to_string(),
}
};
let list = |vs: &[VertexId]| {
let mut text = String::new();
let mut budget = Budget::new(&mut text, limit);
let cut_short = vs.iter().enumerate().any(|(i, v)| {
let separator = if i == 0 { "" } else { ", " };
budget
.write_str(separator)
.and_then(|()| budget.write_str(&vertex(v)))
.is_err()
});
if cut_short {
write!(text, "… ({} vertices)", vs.len()).unwrap();
}
text
};
use NetError::*;
match self {
NoVertex { vertex, vertices } => write!(
f,
"a link names vertex {vertex}, but the structure has {}",
crate::errors::counted(*vertices, "vertex", "vertices")
),
NotLiteral { vertex: v } => write!(f, "vertex {} is not a literal", vertex(v)),
NotDual { x, y } => {
write!(
f,
"the literals {} and {} are not dual",
vertex(x),
vertex(y)
)
}
LinkedTwice { vertex: v } => write!(f, "literal {} is linked twice", vertex(v)),
Unlinked { vertex: v } => write!(f, "literal {} has no axiom link", vertex(v)),
Empty => f.write_str("the structure is empty, and no rule concludes the empty sequent"),
SwitchingCycle { cycle } => write!(f, "a switching cycle runs through {}", list(cycle)),
Disconnected { parts } => {
let parts: Vec<String> = parts.iter().map(|p| format!("{{{}}}", list(p))).collect();
write!(
f,
"every switching falls into {} parts; keeping every left premise, they are {}",
parts.len(),
parts.join(" and ")
)
}
DirectedCycle { cycle } => write!(
f,
"a directed cycle of the essential net runs through {}",
list(cycle)
),
NoDominator { implication, path } => write!(
f,
"the implication {} does not dominate its antecedent: the path {} reaches the \
goal around it",
vertex(implication),
list(path)
),
Crossing {
links: [(x, y), (u, v)],
} => write!(
f,
"the links {} — {} and {} — {} cross in the cyclic order",
vertex(x),
vertex(y),
vertex(u),
vertex(v)
),
NotIntuitionistic { shape } => {
f.write_str("essential nets exist for intuitionistic sequents only: ")?;
shape.write(f, names, limit)
}
Fragment { fragment } => write!(
f,
"proof nets exist for MLL without units only, not for {fragment}"
),
Mode { mode } => write!(
f,
"proof nets exist in linear mode only, with or without Mix, not in {mode} mode"
),
Rule { node, rule } => write!(
f,
"node {} applies {rule}, which a proof net of MLL without units has no place for",
node.get()
),
NetError::Placement { vertex: v, fault } => {
write!(f, "vertex {} {}", vertex(v), fault.clause())
}
Unattached { vertex: v } => {
write!(f, "the weakening {} hangs on no axiom link", vertex(v))
}
InBox { door, error } => {
write!(f, "inside the box of {}, ", vertex(door))?;
error.write_over(f, names, vertices, limit)
}
NotMell { fragment, mode } => write!(
f,
"proof nets with boxes exist for MELL without units in classical mode, with or \
without Mix, and in intuitionistic mode, only, not for {fragment} in {mode} mode"
),
NoCut { vertex: Some(v) } => write!(f, "vertex {} is no end of a cut link", vertex(v)),
NoCut { vertex: None } => f.write_str("the net has no cut link"),
Reduction { error } => {
f.write_str("a step of cut elimination made a net the criterion refuses: ")?;
error.write_over(f, names, vertices, limit)
}
Refused { refusal } => write!(f, "{refusal}"),
}
}
}
impl Display for NetError {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.write(f, None, None)
}
}
impl std::error::Error for NetError {}
fn afford(bytes: u64, limits: &Limits) -> Result<(), NetError> {
match limits.memory_bytes {
Some(limit) if bytes > limit => Err(NetError::Refused {
refusal: Refusal::Memory {
phase: Phase::Net,
limit_bytes: limit,
needed_bytes: Some(bytes),
},
}),
_ => Ok(()),
}
}
type CutsPlaced = (Vec<(VertexId, VertexId)>, Option<OccSet>);
fn misplaced(vertex: VertexId, fault: Placement) -> Error {
NetError::Placement { vertex, fault }.into()
}
const STOPPED: NetError = NetError::Refused {
refusal: Refusal::Stopped { phase: Phase::Net },
};
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug)]
pub struct ProofStructure {
forest: Forest,
criterion: Criterion,
partner: Box<[u32]>,
links: Vec<(VertexId, VertexId)>,
cuts: Vec<(VertexId, VertexId)>,
live: Option<OccSet>,
literals: usize,
graph: Graph,
skeleton: Skeleton,
}
impl ProofStructure {
pub fn new(forest: Forest, criterion: Criterion) -> Result<Self, Error> {
Self::build(forest, criterion, &[])
}
pub fn from_links(
forest: Forest,
criterion: Criterion,
links: &[(VertexId, VertexId)],
) -> Result<Self, Error> {
Self::with_cuts(forest, criterion, &[], links)
}
pub fn with_cuts(
forest: Forest,
criterion: Criterion,
cuts: &[(VertexId, VertexId)],
links: &[(VertexId, VertexId)],
) -> Result<Self, Error> {
let mut net = Self::build(forest, criterion, cuts)?;
for &(x, y) in links {
net.link(x, y)?;
}
Ok(net)
}
fn build(
forest: Forest,
criterion: Criterion,
cuts: &[(VertexId, VertexId)],
) -> Result<Self, Error> {
has_nets(forest.sequent().fragment())?;
if criterion.order != Order::Commutative && (criterion.mix || !cuts.is_empty()) {
let mode = if criterion.mix {
Mode::CYCLIC.with_mix()
} else {
Mode::CYCLIC
};
return Err(NetError::Mode { mode }.into());
}
let n = forest.len();
fits(n)?;
let (cuts, live) = Self::place_cuts(&forest, cuts)?;
let alive = |o: OccId| live.as_ref().is_none_or(|live| live.contains(o));
let mut skeleton = Skeleton::new(n);
for o in forest.ids().filter(|&o| alive(o)) {
if let Some(p) = forest.parent(o)
&& forest.kind(p) == Kind::Tensor
&& alive(p)
{
skeleton.union(p.get(), o.get());
}
}
for &(x, y) in &cuts {
skeleton.union(x.get(), y.get());
}
let literals = match &live {
None => forest.all_literals().len(),
Some(live) => forest
.all_literals()
.iter()
.filter(|&&l| live.contains(l))
.count(),
};
skeleton.commit(literals / 2);
Ok(Self {
graph: Graph::new(&forest, live.as_ref(), &cuts),
forest,
criterion,
partner: vec![NONE; n].into_boxed_slice(),
links: Vec::with_capacity(literals / 2),
cuts,
live,
literals,
skeleton,
})
}
fn place_cuts(forest: &Forest, cuts: &[(VertexId, VertexId)]) -> Result<CutsPlaced, Error> {
if !forest.has_cuts() {
if let Some(&(x, _)) = cuts.first() {
return Err(misplaced(x, Placement::Cut));
}
return Ok((Vec::new(), None));
}
let n = forest.len();
let conclusions = forest.ids().take_while(|&o| forest.is_conclusion(o));
let mut live = OccSet::of(n, conclusions);
let mut placed = Vec::with_capacity(cuts.len());
for &(x, y) in cuts {
for v in [x, y] {
if v.index() >= n {
return Err(NetError::NoVertex {
vertex: v.get(),
vertices: n as u32,
}
.into());
}
}
let (a, d) = match (forest.dual(x.occ()), forest.dual(y.occ())) {
(Some(dx), _) if dx == y.occ() && x < y => (x, y),
(_, Some(dy)) if dy == x.occ() && y < x => (y, x),
_ => return Err(misplaced(x, Placement::Cut)),
};
for end in [a, d] {
for o in forest.subtree(end.occ()) {
if !live.insert(o) {
return Err(misplaced(end, Placement::Cut));
}
}
}
placed.push((a, d));
}
Ok((placed, Some(live)))
}
pub fn from_proof(
proof: &Proof,
criterion: Criterion,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Self, Error> {
if proof.goal().is_some() {
return Err(Error::GoalProof);
}
let forest = proof.forest();
let bytes = Self::bytes(forest);
afford(bytes, limits)?;
let mut links = Vec::with_capacity(forest.all_literals().len() / 2);
let mut cuts = Vec::new();
for (i, &node) in proof.nodes().iter().enumerate() {
let done = i as u64 + 1;
let progress = Progress {
held_bytes: bytes,
..Progress::new(Phase::Net, 1, done)
};
if stop(progress) {
return Err(STOPPED.into());
}
match node {
Node::Ax(x, y) => links.push((VertexId::of(x.occ()), VertexId::of(y.occ()))),
Node::Tensor(..) | Node::Par(..) | Node::Mix(..) => {}
Node::Cut(a, ..) => {
let d = forest.dual(a.occ()).unwrap_or(a.occ());
cuts.push((VertexId::of(a.occ()), VertexId::of(d)));
}
Node::One(_)
| Node::Bot(..)
| Node::With(..)
| Node::Plus(..)
| Node::Top(_)
| Node::Bang(..)
| Node::Quest(..)
| Node::Copy(..)
| Node::Weaken(..)
| Node::Forall(..)
| Node::Exists(..) => {
return Err(NetError::Rule {
node: NodeId::new(i as u32),
rule: node.name(),
}
.into());
}
}
}
let net = Self::with_cuts(forest.clone(), criterion, &cuts, &links)?;
net.is_correct(|progress| {
stop(Progress {
held_bytes: bytes,
..progress
})
})?;
Ok(net)
}
fn bytes(forest: &Forest) -> u64 {
let arena = forest.sequent().terms().len() as u64 * size_of::<Term>() as u64;
(forest.len() as u64 * (STRUCTURE_BYTES + SCRATCH_BYTES)).saturating_add(arena)
}
fn check_link(&self, x: VertexId, y: VertexId) -> Result<(), NetError> {
let f = &self.forest;
for v in [x, y] {
if v.index() >= f.len() {
return Err(NetError::NoVertex {
vertex: v.get(),
vertices: f.len() as u32,
});
}
if !f.is_literal(v.occ()) {
return Err(NetError::NotLiteral { vertex: v });
}
if !self.is_vertex(v.occ()) {
return Err(NetError::Placement {
vertex: v,
fault: Placement::Uncut,
});
}
}
if !self.dual(x, y) {
return Err(NetError::NotDual { x, y });
}
for v in [x, y] {
if self.partner(v).is_some() {
return Err(NetError::LinkedTwice { vertex: v });
}
}
Ok(())
}
fn dual(&self, x: VertexId, y: VertexId) -> bool {
self.forest.dual_literals(x.occ(), y.occ())
}
pub fn forest(&self) -> &Forest {
&self.forest
}
pub fn sequent(&self) -> &Sequent {
self.forest.sequent()
}
pub fn criterion(&self) -> Criterion {
self.criterion
}
fn is_vertex(&self, o: OccId) -> bool {
self.live.as_ref().is_none_or(|live| live.contains(o))
}
pub fn vertex(&self, o: OccId) -> Option<VertexId> {
(o.index() < self.forest.len() && self.is_vertex(o)).then_some(VertexId::of(o))
}
pub fn occurrence(&self, v: VertexId) -> Option<OccId> {
self.vertex(v.occ()).map(VertexId::occ)
}
pub fn vertices(&self) -> impl Iterator<Item = VertexId> + '_ {
self.forest
.ids()
.filter(|&o| self.is_vertex(o))
.map(VertexId::of)
}
pub fn cuts(&self) -> &[(VertexId, VertexId)] {
&self.cuts
}
pub fn cut_partner(&self, v: VertexId) -> Option<VertexId> {
self.cuts.iter().find_map(|&(x, y)| match v {
v if v == x => Some(y),
v if v == y => Some(x),
_ => None,
})
}
pub fn is_cut_free(&self) -> bool {
self.cuts.is_empty()
}
pub fn partner(&self, v: VertexId) -> Option<VertexId> {
match self.partner.get(v.index()) {
None | Some(&NONE) => None,
Some(&p) => Some(VertexId(p)),
}
}
pub(crate) fn mate(&self, v: VertexId) -> Option<VertexId> {
match self.partner[v.index()] {
NONE => None,
p => Some(VertexId(p)),
}
}
pub fn links(&self) -> &[(VertexId, VertexId)] {
&self.links
}
pub fn is_complete(&self) -> bool {
2 * self.links.len() == self.literals
}
pub fn unlinked(&self) -> impl Iterator<Item = VertexId> {
self.forest
.all_literals()
.iter()
.filter(|&&l| self.partner[l.index()] == NONE && self.is_vertex(l))
.map(|&l| VertexId::of(l))
}
pub fn link(&mut self, x: VertexId, y: VertexId) -> Result<(), NetError> {
self.check_link(x, y)?;
self.link_unchecked(x, y);
Ok(())
}
pub(crate) fn link_unchecked(&mut self, x: VertexId, y: VertexId) {
debug_assert!(
self.check_link(x, y).is_ok(),
"{x:?} and {y:?} cannot be linked"
);
self.partner[x.index()] = y.get();
self.partner[y.index()] = x.get();
self.links.push((x, y));
self.skeleton.union(x.get(), y.get());
self.graph.link(x.get(), y.get());
}
pub fn unlink(&mut self) -> Option<(VertexId, VertexId)> {
let (x, y) = self.links.pop()?;
self.partner[x.index()] = NONE;
self.partner[y.index()] = NONE;
self.skeleton.undo();
self.graph.unlink(x.get(), y.get());
Some((x, y))
}
pub fn same_component(&self, x: VertexId, y: VertexId) -> bool {
let n = self.forest.len();
x.index() < n && y.index() < n && self.joined(x, y)
}
pub(crate) fn joined(&self, x: VertexId, y: VertexId) -> bool {
self.skeleton.same(x.get(), y.get())
}
pub(crate) fn component(&self, v: VertexId) -> u32 {
self.skeleton.find(v.get())
}
pub fn scratch(&self) -> Scratch {
self.graph.scratch()
}
pub fn is_acyclic(&self, scratch: &mut Scratch) -> bool {
if !self.cuts.is_empty() && self.looped().is_some() {
return false;
}
if !scratch.fits(&self.graph) {
*scratch = self.scratch();
}
scratch.restore();
self.graph
.acyclic(&self.forest, scratch, &mut |_| false)
.unwrap_or(false)
}
pub fn is_correct(&self, mut stop: impl FnMut(Progress) -> bool) -> Result<(), NetError> {
if self.forest.is_empty() {
return Err(NetError::Empty);
}
if let Some(l) = self.unlinked().next() {
return Err(NetError::Unlinked { vertex: l });
}
if let Some((x, y)) = self.looped() {
return Err(NetError::SwitchingCycle { cycle: vec![x, y] });
}
let mut scratch = self.scratch();
let held_bytes = self.forest.len() as u64 * SCRATCH_BYTES;
let mut rounds = 0;
let mut stop = |round: u64| {
rounds += round;
stop(Progress {
held_bytes,
..Progress::new(Phase::Net, round, rounds)
})
};
match self.graph.acyclic(&self.forest, &mut scratch, &mut stop) {
None => return Err(STOPPED),
Some(false) => {
return match self.graph.cycle(&self.forest, &mut scratch, &mut stop) {
Some(cycle) => Err(NetError::SwitchingCycle { cycle }),
None => Err(STOPPED),
};
}
Some(true) => {}
}
if !self.criterion.mix
&& self.graph.switched_edges(self.links.len()) + 1 != self.graph.vertices()
{
return Err(NetError::Disconnected {
parts: self.graph.parts(&self.forest, &mut scratch),
});
}
if self.criterion.order != Order::Commutative {
self.is_planar()?;
}
Ok(())
}
fn looped(&self) -> Option<(VertexId, VertexId)> {
self.cuts
.iter()
.copied()
.find(|&(x, y)| self.partner(x) == Some(y))
}
#[expect(
clippy::missing_panics_doc,
reason = "the expect and the unreachable state that a link's two literals name each other, which linking keeps"
)]
pub fn is_planar(&self) -> Result<(), NetError> {
let mut open: Vec<VertexId> = Vec::new();
for o in self.forest.ids() {
let v = VertexId::of(o);
let Some(partner) = self.partner(v) else {
continue;
};
if partner > v {
open.push(v);
continue;
}
match open.pop() {
Some(top) if top == partner => {}
Some(top) => {
let inner = self.partner(top).expect("an open literal is linked");
return Err(NetError::Crossing {
links: [(partner, v), (top, inner)],
});
}
None => unreachable!("the partner of a later literal was passed and is open"),
}
}
Ok(())
}
}
impl Display for ProofStructure {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.write(f, None)
}
}
impl ProofStructure {
pub fn written_in(&self, mode: crate::linear::Mode) -> impl Display + '_ {
In {
structure: self,
mode,
}
}
fn write(&self, f: &mut Formatter<'_>, mode: Option<crate::linear::Mode>) -> FmtResult {
let reading = mode
.filter(|mode| mode.is_intuitionistic())
.and_then(|_| self.reading().ok());
let reading = reading.as_ref();
match reading {
Some(reading) => writeln!(f, "{reading}")?,
None => writeln!(f, "{}", self.sequent())?,
}
let mut links: Vec<(VertexId, VertexId)> = self
.links
.iter()
.map(|&(x, y)| (x.min(y), x.max(y)))
.collect();
links.sort_unstable();
let formula = |v: VertexId| match reading {
Some(reading) => reading.formula(v.occ()).to_string(),
None => self.forest.formula(v.occ()).to_string(),
};
for &(x, y) in &self.cuts {
writeln!(
f,
"cut {}[{}] — {}[{}]",
formula(x),
x.get(),
formula(y),
y.get()
)?;
}
for (x, y) in links {
writeln!(
f,
"{}[{}] — {}[{}]",
formula(x),
x.get(),
formula(y),
y.get()
)?;
}
match self.is_correct(|_| false) {
Ok(()) if self.criterion.mix => f.write_str("proof net with Mix"),
Ok(()) if self.criterion.order != Order::Commutative => f.write_str("planar proof net"),
Ok(()) => f.write_str("proof net"),
Err(e) => match mode {
Some(mode) => write!(
f,
"not a proof net: {}",
e.describe(&self.forest).in_mode(mode)
),
None => write!(f, "not a proof net: {}", e.describe(&self.forest)),
},
}
}
}
pub(crate) struct In<'a, S> {
pub(crate) structure: &'a S,
pub(crate) mode: crate::linear::Mode,
}
impl Display for In<'_, ProofStructure> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.structure.write(f, Some(self.mode))
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
#[cfg(feature = "parse")]
use crate::linear::fragment::Mode;
#[cfg(feature = "parse")]
use crate::linear::occurrences::Member;
#[cfg(feature = "parse")]
use crate::linear::proofs::NodeId;
const fn o(id: u32) -> OccId {
OccId::new(id)
}
const fn v(id: u32) -> VertexId {
VertexId::new(id)
}
#[test]
fn a_forest_past_the_vertices_is_refused() {
let most = usize::try_from(MOST).unwrap();
assert!(fits(most).is_ok());
assert!(matches!(
fits(most + 1),
Err(Error::Refused(Refusal::Index {
what: Space::Vertex,
count,
most: MOST,
})) if count == MOST + 1
));
}
const fn criterion(mix: bool) -> Criterion {
Criterion {
mix,
..Criterion::MLL
}
}
#[cfg(feature = "parse")]
fn forest(input: &str) -> Forest {
let s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
Forest::new(&s).unwrap()
}
#[cfg(feature = "parse")]
#[test]
fn link_and_unlink() {
let mut net = ProofStructure::new(forest("A, A -o B |- B"), criterion(false)).unwrap();
assert!(!net.is_complete());
assert_eq!(net.unlinked().collect::<Vec<_>>(), [v(2), v(0), v(4), v(3)]);
assert!(net.same_component(v(2), v(3)), "the ⊗ joins its premises");
assert!(!net.same_component(v(0), v(2)));
net.link(v(0), v(2)).unwrap();
assert_eq!(net.partner(v(2)), Some(v(0)));
assert_eq!(net.partner(v(1)), None);
assert!(net.same_component(v(0), v(3)), "through the link and the ⊗");
net.link(v(4), v(3)).unwrap();
assert!(net.is_complete());
assert_eq!(net.links(), [(v(0), v(2)), (v(4), v(3))]);
assert_eq!(net.unlink(), Some((v(4), v(3))));
assert_eq!(net.partner(v(4)), None);
assert!(!net.same_component(v(4), v(0)));
assert_eq!(net.unlink(), Some((v(0), v(2))));
assert!(!net.same_component(v(0), v(3)));
assert_eq!(net.unlink(), None);
assert_eq!(net.unlinked().count(), 4);
}
#[cfg(feature = "parse")]
#[test]
fn desequentialize() {
use Node::*;
let (n, mode) = (NodeId::new, Mode::CLASSICAL);
let f = forest("|- A * B, ~A, ~B * C, ~C");
let first_tensor_first = Proof::new(
f.clone(),
vec![
Ax(o(1).into(), o(3).into()),
Ax(o(2).into(), o(5).into()),
Ax(o(6).into(), o(7).into()),
Tensor(Member::from(o(4)), n(1), n(2)),
Tensor(Member::from(o(0)), n(0), n(3)),
],
n(4),
)
.unwrap();
let second_tensor_first = Proof::new(
f.clone(),
vec![
Ax(o(1).into(), o(3).into()),
Ax(o(2).into(), o(5).into()),
Tensor(Member::from(o(0)), n(0), n(1)),
Ax(o(6).into(), o(7).into()),
Tensor(Member::from(o(4)), n(2), n(3)),
],
n(4),
)
.unwrap();
assert_eq!(first_tensor_first.check(mode), Ok(()));
assert_eq!(second_tensor_first.check(mode), Ok(()));
let a = ProofStructure::from_proof(
&first_tensor_first,
criterion(false),
&Limits::default(),
|_| false,
)
.unwrap();
let b = ProofStructure::from_proof(
&second_tensor_first,
criterion(false),
&Limits::default(),
|_| false,
)
.unwrap();
assert_eq!(links(&a), links(&b));
assert_eq!(links(&a), [(v(1), v(3)), (v(2), v(5)), (v(6), v(7))]);
let f = forest("|- A par B, ~A, ~B");
let with_mix = Proof::new(
f,
vec![
Ax(o(1).into(), o(3).into()),
Ax(o(2).into(), o(4).into()),
Mix(n(0), n(1)),
Par(Member::from(o(0)), n(2)),
],
n(3),
)
.unwrap();
assert!(
ProofStructure::from_proof(&with_mix, criterion(true), &Limits::default(), |_| false)
.is_ok()
);
assert!(matches!(
ProofStructure::from_proof(&with_mix, criterion(false), &Limits::default(), |_| false),
Err(Error::Net(e)) if matches!(*e, NetError::Disconnected { .. })
));
let f = forest("|- A & A, ~A");
let additive = Proof::new(
f,
vec![
Ax(o(1).into(), o(3).into()),
Ax(o(2).into(), o(3).into()),
With(Member::from(o(0)), n(0), n(1)),
],
n(2),
)
.unwrap();
assert!(matches!(
ProofStructure::from_proof(&additive, criterion(false), &Limits::default(), |_| false),
Err(Error::Net(e)) if matches!(*e, NetError::Rule { node, rule: "&" } if node == n(2))
));
let f = forest("|- A, ~A, B");
let weakened = Proof::new(
f,
vec![Ax(o(0).into(), o(1).into()), Weaken(o(2).into(), n(0))],
n(1),
)
.unwrap();
assert!(matches!(
ProofStructure::from_proof(&weakened, criterion(false), &Limits::default(), |_| false),
Err(Error::Net(e)) if matches!(*e, NetError::Rule { rule: "wk", .. })
));
}
#[cfg(feature = "parse")]
#[test]
fn round_trip_random_derivations() {
use crate::linear::search::generate::{self, Rng, Rules};
use crate::linear::search::{Options, prove};
for (seed, mix) in [(3, false), (4, true)] {
let rules = Rules {
units: false,
additives: false,
mix,
exponentials: false,
};
let mode = if mix {
Mode::CLASSICAL.with_mix()
} else {
Mode::CLASSICAL
};
let mut rng = Rng::new(seed);
for _ in 0..60 {
let budget = 2 + rng.below(14);
let formulas = generate::provable(&mut rng, rules, 3, budget).formulas;
let text = generate::sequent(&formulas);
let s: Sequent = text.parse().unwrap();
let outcome = prove(&s, mode, &Options::default()).unwrap();
let proof = outcome.verdict.proof().expect("the sequent is provable");
assert_eq!(proof.check(mode), Ok(()), "{text:?}");
let net =
ProofStructure::from_proof(proof, criterion(mix), &Limits::default(), |_| {
false
})
.unwrap_or_else(|e| panic!("{text:?}: {e}"));
let back = net
.sequentialize(&Limits::default(), |_| false)
.unwrap_or_else(|e| panic!("{text:?}: {e}"));
assert_eq!(back.check(mode), Ok(()), "{text:?}");
let again =
ProofStructure::from_proof(&back, criterion(mix), &Limits::default(), |_| {
false
})
.unwrap();
assert_eq!(links(&again), links(&net), "{text:?}");
}
}
}
#[test]
fn planarity() {
use crate::linear::occurrences::Sign;
use crate::linear::search::generate::{self, Rng, Rules};
use crate::linear::sequents::Atom;
fn cross((x, y): (VertexId, VertexId), (u, v): (VertexId, VertexId)) -> bool {
let (x, y) = (x.min(y), x.max(y));
let (u, v) = (u.min(v), u.max(v));
(x < u && u < y && y < v) || (u < x && x < v && v < y)
}
fn every(net: &mut ProofStructure, positives: &[OccId], mll: &mut ProofStructure) -> u32 {
let Some((&x, rest)) = positives.split_first() else {
let pairwise = net
.links()
.iter()
.all(|&l| net.links().iter().all(|&m| !cross(l, m)));
match net.is_planar() {
Ok(()) => assert!(pairwise, "{net}"),
Err(NetError::Crossing { links: [l, m] }) => {
assert!(!pairwise && cross(l, m), "{net}");
assert!(l.0 < l.1 && m.0 < m.1 && l.0 < m.0, "{l:?} {m:?}");
}
Err(e) => panic!("{e}"),
}
let cyclic = net.is_correct(|_| false).is_ok();
assert_eq!(
cyclic,
pairwise && mll.is_correct(|_| false).is_ok(),
"{net}"
);
if cyclic {
let proof = net.sequentialize(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(Mode::CYCLIC), Ok(()), "{net}");
let back = ProofStructure::from_proof(
&proof,
Criterion::CYCLIC,
&Limits::default(),
|_| false,
)
.unwrap();
assert_eq!(links(&back), links(net), "{net}");
}
return u32::from(cyclic);
};
let forest = net.forest().clone();
let mut nets = 0;
for &y in forest.literals(forest.atom(x).unwrap(), Sign::Dual) {
if net.partner(VertexId::of(y)).is_none() {
net.link(VertexId::of(x), VertexId::of(y)).unwrap();
mll.link(VertexId::of(x), VertexId::of(y)).unwrap();
nets += every(net, rest, mll);
net.unlink();
mll.unlink();
}
}
nets
}
let rules = Rules {
units: false,
additives: false,
mix: false,
exponentials: false,
};
let mut rng = Rng::new(36);
let (mut sequents, mut nets) = (0, 0);
for round in 0..300 {
let formulas = if round % 2 == 0 {
let budget = 2 + rng.below(8);
generate::provable(&mut rng, rules, 2, budget).formulas
} else {
let (atoms, pairs) = (1 + rng.below(2) as u8, 1 + rng.below(5));
generate::balanced(&mut rng, atoms, pairs, false)
};
let s: Sequent = generate::sequent(&formulas).parse().unwrap();
let forest = Forest::new(&s).unwrap();
let positives: Vec<OccId> = (0..s.atom_names().len() as u32)
.flat_map(|a| forest.literals(Atom::new(a), Sign::Atom).to_vec())
.collect();
let balanced = (0..s.atom_names().len() as u32).all(|a| {
let a = Atom::new(a);
let n = forest.literals(a, Sign::Atom).len();
n == forest.literals(a, Sign::Dual).len() && n <= 5
});
if !balanced {
continue;
}
let mut net = ProofStructure::new(forest.clone(), Criterion::CYCLIC).unwrap();
let mut mll = ProofStructure::new(forest, Criterion::MLL).unwrap();
sequents += 1;
nets += every(&mut net, &positives, &mut mll);
}
assert!(
sequents > 150 && nets > 100,
"{sequents} sequents, {nets} planar nets"
);
}
#[cfg(feature = "parse")]
#[test]
fn text_form() {
let net = ProofStructure::from_links(
forest("A, A -o B |- B"),
criterion(false),
&[(v(2), v(0)), (v(3), v(4))],
)
.unwrap();
assert_eq!(
net.to_string(),
"⊢ ~A, A ⊗ ~B, B\n~A[0] — A[2]\n~B[3] — B[4]\nproof net"
);
let mut net = ProofStructure::new(forest("|- A par B, ~A, ~B"), criterion(true)).unwrap();
net.link(v(1), v(3)).unwrap();
assert_eq!(
net.to_string(),
"⊢ A ⅋ B, ~A, ~B\nA[1] — ~A[3]\nnot a proof net: literal B[2] has no axiom link"
);
net.link(v(2), v(4)).unwrap();
assert!(net.to_string().ends_with("\nproof net with Mix"));
let net =
ProofStructure::from_links(forest("|- A * ~A"), criterion(false), &[(v(1), v(2))])
.unwrap();
assert!(
net.to_string().ends_with(
"not a proof net: a switching cycle runs through A ⊗ ~A[0], A[1], ~A[2]"
)
);
let net = ProofStructure::from_links(
forest("|- A par B, ~A, ~B"),
criterion(false),
&[(v(1), v(3)), (v(2), v(4))],
)
.unwrap();
assert!(net.to_string().ends_with(
"not a proof net: every switching falls into 2 parts; keeping every left premise, \
they are {A â…‹ B[0], ~A[3]} and {B[2], ~B[4]}"
));
}
fn links(net: &ProofStructure) -> Vec<(VertexId, VertexId)> {
let mut links: Vec<(VertexId, VertexId)> = net
.links()
.iter()
.map(|&(x, y)| (x.min(y), x.max(y)))
.collect();
links.sort();
links
}
#[cfg(feature = "parse")]
#[test]
fn validation() {
let f = || forest("A, A -o B |- B, A");
let net = ProofStructure::from_links(f(), criterion(false), &[(v(0), v(5))]).unwrap();
assert!(!net.is_complete());
for (links, error) in [
(
vec![(v(0), v(9))],
NetError::NoVertex {
vertex: 9,
vertices: 6,
},
),
(vec![(v(1), v(0))], NetError::NotLiteral { vertex: v(1) }),
(vec![(v(0), v(3))], NetError::NotDual { x: v(0), y: v(3) }),
(vec![(v(5), v(2))], NetError::NotDual { x: v(5), y: v(2) }),
(
vec![(v(0), v(5)), (v(0), v(2))],
NetError::LinkedTwice { vertex: v(0) },
),
] {
match ProofStructure::from_links(f(), criterion(false), &links) {
Err(Error::Net(e)) => assert_eq!(*e, error, "{links:?}"),
other => panic!("{links:?}: {other:?}"),
}
let mut net = ProofStructure::new(f(), criterion(false)).unwrap();
let (&(x, y), made) = links.split_last().unwrap();
for &(x, y) in made {
net.link(x, y).unwrap();
}
assert_eq!(net.link(x, y), Err(error), "{links:?}");
assert_eq!(net.links(), made, "{links:?}");
assert_eq!(net.partner(v(2)), None, "{links:?}");
}
let outside = NetError::NoVertex {
vertex: u32::MAX,
vertices: 6,
};
assert_eq!(
outside.describe(net.forest()).to_string(),
"a link names vertex 4294967295, but the structure has 6 vertices"
);
for input in ["|- 1", "|- A & B", "|- !A"] {
assert!(
matches!(
ProofStructure::new(forest(input), criterion(true)),
Err(Error::Net(e)) if matches!(*e, NetError::Fragment { .. })
),
"{input}"
);
}
assert!(ProofStructure::new(forest("|-"), criterion(true)).is_ok());
}
#[cfg(feature = "parse")]
#[test]
fn foreign_ids_and_scratches() {
let small = ProofStructure::from_links(forest("a |- a"), criterion(false), &[(v(0), v(1))])
.unwrap();
assert_eq!(small.partner(v(99)), None);
assert!(!small.same_component(v(0), v(99)));
assert_eq!(small.occurrence(v(2)), None);
assert_eq!(small.vertex(o(1)), Some(v(1)));
let cyclic = ProofStructure::from_links(
forest("|- A * ~A, B, ~B"),
criterion(true),
&[(v(1), v(2)), (v(3), v(4))],
)
.unwrap();
let mut scratch = small.scratch();
assert!(!cyclic.is_acyclic(&mut scratch));
assert!(small.is_acyclic(&mut scratch));
}
#[test]
fn exist_refuses_as_the_constructors() {
let additive = forest("|- a & b, ~a");
let fragment = additive.sequent().fragment();
let refused = exist(fragment, Mode::CLASSICAL).unwrap_err();
let built = ProofStructure::new(additive, Criterion::MLL).unwrap_err();
assert_eq!(Error::Net(Box::new(refused)), built);
assert_eq!(built.code(), "no_nets");
let affine = Mode::CLASSICAL.with_affine();
assert_eq!(
exist(Fragment::MLL, affine),
Criterion::of(affine).map(|_| ())
);
}
#[cfg(feature = "parse")]
#[test]
#[expect(
clippy::wildcard_enum_match_arm,
reason = "a test's other arm is its failure"
)]
fn refusals() {
use crate::linear::search::{Options, prove};
let s: Sequent = "A * B |- B * A".parse().unwrap();
let outcome = prove(&s, Mode::CLASSICAL, &Options::default()).unwrap();
let proof = outcome.verdict.proof().unwrap();
let tiny = Limits::default().with_memory_bytes(Some(100));
let refused = |error: Error| match error {
Error::Net(e) => match *e {
NetError::Refused { refusal } => refusal,
other => panic!("{other:?}"),
},
other => panic!("{other:?}"),
};
let memory = refused(
ProofStructure::from_proof(proof, Criterion::MLL, &tiny, |_| false).unwrap_err(),
);
assert!(matches!(
memory,
Refusal::Memory {
phase: Phase::Net,
..
}
));
let stopped = Refusal::Stopped { phase: Phase::Net };
let error = ProofStructure::from_proof(proof, Criterion::MLL, &Limits::default(), |_| true);
assert_eq!(refused(error.unwrap_err()), stopped);
let mut held = Vec::new();
let net = ProofStructure::from_proof(proof, Criterion::MLL, &Limits::default(), |p| {
held.push(p.held_bytes);
false
})
.unwrap();
assert!(!held.is_empty() && held.iter().all(|&bytes| bytes > 0));
let mut scratch = Vec::new();
net.is_correct(|p| {
scratch.push(p.held_bytes);
false
})
.unwrap();
assert!(!scratch.is_empty() && scratch.iter().all(|&bytes| bytes > 0));
assert_eq!(
net.is_correct(|_| true),
Err(NetError::Refused {
refusal: stopped.clone()
})
);
assert_eq!(
refused(net.sequentialize(&Limits::default(), |_| true).unwrap_err()),
stopped
);
let memory = refused(net.sequentialize(&tiny, |_| false).unwrap_err());
assert!(matches!(
memory,
Refusal::Memory {
phase: Phase::Net,
..
}
));
let back = net.sequentialize(&Limits::default(), |_| false).unwrap();
assert_eq!(back.mode(), Some(Mode::CLASSICAL));
}
}
impl Display for In<'_, crate::linear::MellStructure> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.structure.write(f, Some(self.mode))
}
}