mod mell;
#[cfg(all(test, feature = "parse"))]
mod tests;
use super::{NetError, ProofStructure, VertexId, afford};
use crate::Error;
use crate::limits::{Bound, Limits, Phase, Progress, Refusal};
use crate::linear::proofs::cut::{Case, End, Options, Strategy};
use crate::linear::sequents::Kind;
pub trait Net: Clone + crate::sealed::Net {}
impl Net for ProofStructure {}
impl Net for super::MellStructure {}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Step {
pub cut: (VertexId, VertexId),
pub case: Case,
pub above: Option<VertexId>,
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Reduction<N> {
pub net: N,
pub step: Step,
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Elimination<N> {
pub net: N,
pub steps: Vec<Step>,
pub end: End,
}
fn pick<N: Net>(
net: &N,
at: Option<VertexId>,
strategy: Strategy,
) -> Result<(VertexId, VertexId), NetError> {
let cuts = net.cut_links();
match at {
Some(v) => cuts
.iter()
.copied()
.find(|&(x, y)| x == v || y == v)
.ok_or(NetError::NoCut { vertex: Some(v) }),
None => match strategy {
Strategy::Topmost => cuts
.first()
.copied()
.ok_or(NetError::NoCut { vertex: None }),
},
}
}
fn rejected(error: NetError) -> Error {
if matches!(error, NetError::Refused { .. }) {
return error.into();
}
NetError::Reduction {
error: Box::new(error),
}
.into()
}
fn refusal(error: &Error) -> Option<&Refusal> {
if let Error::Refused(refusal) = error {
return Some(refusal);
}
if let Error::Net(net) = error
&& let NetError::Refused { refusal } = net.as_ref()
{
return Some(refusal);
}
None
}
pub fn step<N: Net>(
net: &N,
at: Option<VertexId>,
options: &Options,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Reduction<N>, Error> {
net.check(&mut stop)?;
let cut = pick(net, at, options.strategy)?;
let (made, step) = net.reduce(cut, options, limits)?;
made.check(&mut stop).map_err(rejected)?;
Ok(Reduction { net: made, step })
}
pub fn eliminate<N: Net>(
net: &N,
options: &Options,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
mut each: impl FnMut(&N, &Step),
) -> Result<Elimination<N>, Error> {
let mut steps: Vec<Step> = Vec::new();
let mut current = net.clone();
let mut checked: Option<N> = None;
loop {
let ended = |net: N, steps: Vec<Step>, refusal: Refusal| Elimination {
net,
steps,
end: End::Refused(refusal),
};
match current.check(&mut stop) {
Ok(()) => {}
Err(NetError::Refused { refusal }) => {
let Some(checked) = checked else {
return Err(NetError::Refused { refusal }.into());
};
steps.pop();
return Ok(ended(checked, steps, refusal));
}
Err(invalid) if checked.is_none() => return Err(invalid.into()),
Err(invalid) => return Err(rejected(invalid)),
}
if let (Some(before), Some(last)) = (&checked, steps.last()) {
each(before, last);
}
let Ok(cut) = pick(¤t, None, options.strategy) else {
return Ok(Elimination {
net: current,
steps,
end: End::CutFree,
});
};
if let Some(limit) = options.steps
&& steps.len() as u64 >= limit
{
let refusal = Refusal::Elimination {
what: Bound::Steps,
limit,
};
return Ok(ended(current, steps, refusal));
}
if stop(Progress::new(Phase::Eliminate, 1, steps.len() as u64)) {
let refusal = Refusal::Stopped {
phase: Phase::Eliminate,
};
return Ok(ended(current, steps, refusal));
}
match current.reduce(cut, options, limits) {
Ok((made, step)) => {
steps.push(step);
checked = Some(std::mem::replace(&mut current, made));
}
Err(error) => match refusal(&error) {
Some(refusal) => {
let refusal = refusal.clone();
return Ok(ended(current, steps, refusal));
}
None => return Err(error),
},
}
}
}
fn within(vertices: usize, options: &Options) -> Result<(), Error> {
match options.nodes {
Some(limit) if vertices as u64 > limit => Err(Error::Refused(Refusal::Elimination {
what: Bound::Vertices,
limit,
})),
_ => Ok(()),
}
}
impl crate::sealed::Net for ProofStructure {
fn cut_links(&self) -> &[(VertexId, VertexId)] {
self.cuts()
}
fn check(&self, stop: &mut dyn FnMut(Progress) -> bool) -> Result<(), NetError> {
self.is_correct(stop)
}
fn reduce(
&self,
(x, y): (VertexId, VertexId),
options: &Options,
limits: &Limits,
) -> Result<(Self, Step), Error> {
let forest = self.forest();
let at = self
.cuts()
.iter()
.position(|&cut| cut == (x, y))
.expect("a cut link of the net");
let mut cuts = self.cuts().to_vec();
let mut links = self.links().to_vec();
let case = match forest.kind(x.occ()) {
Kind::Atom | Kind::DualAtom => {
let (px, py) = (
self.partner(x).expect("a proof net links every literal"),
self.partner(y).expect("a proof net links every literal"),
);
let ends =
|&(u, v): &(VertexId, VertexId)| [x, y].contains(&u) || [x, y].contains(&v);
let first = links.iter().position(ends).expect("the literal's link");
links[first] = (px, py);
links.retain(|link| !ends(link));
cuts.remove(at);
Case::Axiom
}
Kind::Tensor | Kind::Par => {
let child = |v: VertexId, left: bool| {
let o = v.occ();
VertexId::of(
if left {
forest.left(o)
} else {
forest.right(o)
}
.unwrap(),
)
};
cuts.splice(
at..=at,
[
(child(x, true), child(y, true)),
(child(x, false), child(y, false)),
],
);
Case::TensorPar
}
Kind::One
| Kind::Bot
| Kind::Top
| Kind::Zero
| Kind::With
| Kind::Plus
| Kind::Bang
| Kind::Quest
| Kind::Forall
| Kind::Exists => unreachable!("a proof structure is of unit-free MLL"),
};
within(self.vertices().count() - 2, options)?;
afford(Self::bytes(forest), limits)?;
let made = Self::with_cuts(forest.clone(), self.criterion(), &cuts, &links)?;
let step = Step {
cut: (x, y),
case,
above: None,
};
Ok((made, step))
}
}