#![deny(clippy::wildcard_enum_match_arm)]
mod desequentialize;
mod graph;
mod sequentialize;
#[cfg(all(test, feature = "parse"))]
pub(in crate::linear::nets) mod tests;
use super::{Criterion, NONE, NetError, VertexId, afford};
use crate::Error;
use crate::limits::{Limits, Progress, Refusal, Space};
use crate::linear::fragment::{Fragment, Mode, Order};
use crate::linear::occurrences::{Forest, OccId, Reading, ShapeError};
use crate::linear::sequents::Kind;
use graph::Graph;
const MOST: u64 = (u32::MAX / 2 - 1) as u64;
const VERTEX_BYTES: u64 = 20 + 8 + 16;
const BUILD_BYTES: u64 = 16 + 40 + 40;
const DOOR_BYTES: u64 = 16;
const SCRATCH_BYTES: u64 = 16 + 2 + 2 + 8;
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Placed {
pub occurrence: OccId,
pub parent: Option<VertexId>,
pub inside: Option<VertexId>,
}
impl Placed {
pub const fn new(occurrence: OccId, parent: VertexId, inside: Option<VertexId>) -> Self {
Self {
occurrence,
parent: Some(parent),
inside,
}
}
pub const fn cut(occurrence: OccId, inside: Option<VertexId>) -> Self {
Self {
occurrence,
parent: None,
inside,
}
}
}
#[non_exhaustive]
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct Parts {
pub vertices: Vec<Placed>,
pub cuts: Vec<(VertexId, VertexId)>,
pub links: Vec<(VertexId, VertexId)>,
pub weakenings: Vec<(VertexId, VertexId)>,
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Placement {
Outside,
Premise,
Premises,
Box,
Nesting,
Link,
Weakening,
Cut,
Uncut,
}
impl Placement {
pub(crate) const fn clause(self) -> &'static str {
match self {
Self::Outside => "names an occurrence, a parent or a box outside the structure",
Self::Premise => "stands for no premise of its parent",
Self::Premises => "has a premise missing or twice",
Self::Box => "lies in another box than its parent allows",
Self::Nesting => "lies in boxes that nest in a cycle",
Self::Link => "is linked out of its box",
Self::Weakening => {
"is not a weakening: a ? without copies that hangs once on a literal of its box"
}
Self::Cut => {
"is not the end of one cut link between a cut formula's occurrence and its dual in \
one box"
}
Self::Uncut => {
"lies in a cut formula above no cut link, so it is not a vertex, yet a link names it"
}
}
}
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug)]
pub struct MellStructure {
forest: Forest,
criterion: Criterion,
occurrence: Box<[OccId]>,
parent: Box<[u32]>,
inside: Box<[u32]>,
start: Box<[u32]>,
premises: Box<[u32]>,
partner: Box<[u32]>,
links: Vec<(VertexId, VertexId)>,
cuts: Vec<(VertexId, VertexId)>,
hangs: Box<[u32]>,
graph: Graph,
}
impl MellStructure {
pub fn exist(fragment: Fragment, mode: Mode) -> Result<(), NetError> {
let unit_free = Fragment::MLL.union(Fragment::EXPONENTIALS);
if unit_free.contains(fragment) && !mode.is_affine() && !mode.is_ordered() {
Ok(())
} else {
Err(NetError::NotMell { fragment, mode })
}
}
pub fn from_parts(
forest: Forest,
criterion: Criterion,
parts: &Parts,
limits: &Limits,
) -> Result<Self, Error> {
let mode = if criterion.mix {
Mode::CLASSICAL.with_mix()
} else {
Mode::CLASSICAL
};
Self::exist(forest.sequent().fragment(), mode)?;
if criterion.order != Order::Commutative {
return Err(NetError::Mode { mode: Mode::CYCLIC }.into());
}
let roots = forest.roots().len();
let n = roots as u64 + parts.vertices.len() as u64;
if n > MOST {
return Err(Error::Refused(Refusal::Index {
what: Space::Vertex,
count: n,
most: MOST,
}));
}
afford(n * (VERTEX_BYTES + BUILD_BYTES), limits)?;
let n = n as usize;
let mut occurrence = Vec::with_capacity(n);
let mut parent = Vec::with_capacity(n);
let mut inside = Vec::with_capacity(n);
occurrence.extend(forest.roots().iter().copied());
parent.resize(roots, NONE);
inside.resize(roots, NONE);
for (i, placed) in parts.vertices.iter().enumerate() {
let v = VertexId::new((roots + i) as u32);
let outside = |w: VertexId| w.index() >= n;
if placed.occurrence.index() >= forest.len()
|| placed.parent.is_some_and(outside)
|| placed.inside.is_some_and(outside)
{
return Err(misplaced(v, Placement::Outside));
}
occurrence.push(placed.occurrence);
parent.push(placed.parent.map_or(NONE, VertexId::get));
inside.push(placed.inside.map_or(NONE, VertexId::get));
}
let (start, premises) = premises(&forest, &occurrence, &parent)?;
let cuts = place_cuts(&forest, &occurrence, &parent, &inside, roots, &parts.cuts)?;
check_boxes(&forest, &occurrence, &parent, &inside, roots)?;
let mut structure = Self {
criterion,
occurrence: occurrence.into_boxed_slice(),
parent: parent.into_boxed_slice(),
inside: inside.into_boxed_slice(),
start,
premises,
partner: vec![NONE; n].into_boxed_slice(),
links: Vec::with_capacity(parts.links.len()),
cuts,
hangs: vec![NONE; n].into_boxed_slice(),
graph: Graph::default(),
forest,
};
let boxes = Nesting::new(&structure);
structure.check_copies(&boxes)?;
for &(x, y) in &parts.links {
structure.link(x, y, &boxes)?;
}
for &(q, l) in &parts.weakenings {
structure.hang(q, l, &boxes)?;
}
structure.graph = Graph::new(&structure, &boxes, limits)?;
Ok(structure)
}
fn link(&mut self, x: VertexId, y: VertexId, boxes: &Nesting) -> Result<(), NetError> {
let n = self.len();
for v in [x, y] {
if v.index() >= n {
return Err(NetError::NoVertex {
vertex: v.get(),
vertices: n as u32,
});
}
if !self.forest.is_literal(self.occurrence[v.index()]) {
return Err(NetError::NotLiteral { vertex: v });
}
}
let (ox, oy) = (self.occurrence[x.index()], self.occurrence[y.index()]);
if !self.forest.dual_literals(ox, oy) {
return Err(NetError::NotDual { x, y });
}
for v in [x, y] {
if self.partner[v.index()] != NONE {
return Err(NetError::LinkedTwice { vertex: v });
}
}
if boxes.of(x) != boxes.of(y) {
return Err(NetError::Placement {
vertex: x,
fault: Placement::Link,
});
}
self.partner[x.index()] = y.get();
self.partner[y.index()] = x.get();
self.links.push((x, y));
Ok(())
}
fn hang(&mut self, q: VertexId, l: VertexId, boxes: &Nesting) -> Result<(), NetError> {
let n = self.len();
let fault = NetError::Placement {
vertex: q,
fault: Placement::Weakening,
};
if q.index() >= n || l.index() >= n {
return Err(fault);
}
let weakening = self.forest.kind(self.occurrence[q.index()]) == Kind::Quest
&& self.premises(q).next().is_none()
&& self.hangs[q.index()] == NONE;
let literal = self.forest.is_literal(self.occurrence[l.index()]);
if !weakening || !literal || !boxes.within(boxes.of(l), boxes.of(q)) {
return Err(fault);
}
self.hangs[q.index()] = l.get();
Ok(())
}
pub fn forest(&self) -> &Forest {
&self.forest
}
pub fn criterion(&self) -> Criterion {
self.criterion
}
pub fn reading(&self) -> Result<Reading<'_>, ShapeError> {
Reading::new(&self.forest)
}
pub fn len(&self) -> usize {
self.occurrence.len()
}
pub fn is_empty(&self) -> bool {
self.occurrence.is_empty()
}
pub fn vertices(&self) -> impl ExactSizeIterator<Item = VertexId> {
(0..self.len() as u32).map(VertexId::new)
}
pub fn occurrence(&self, v: VertexId) -> Option<OccId> {
self.occurrence.get(v.index()).copied()
}
pub(crate) fn occurrences(&self) -> &[OccId] {
&self.occurrence
}
pub fn parent(&self, v: VertexId) -> Option<VertexId> {
some(*self.parent.get(v.index())?)
}
pub fn premises(&self, v: VertexId) -> impl Iterator<Item = VertexId> + '_ {
let range = if v.index() < self.len() {
self.start[v.index()] as usize..self.start[v.index() + 1] as usize
} else {
0..0
};
self.premises[range].iter().map(|&w| VertexId::new(w))
}
pub fn inside(&self, v: VertexId) -> Option<VertexId> {
some(*self.inside.get(v.index())?)
}
pub fn boxes(&self) -> impl Iterator<Item = VertexId> + '_ {
self.vertices()
.filter(|&v| self.forest.kind(self.occurrence[v.index()]) == Kind::Bang)
}
pub fn auxiliary_doors(&self, door: VertexId) -> Vec<VertexId> {
self.graph.doors(door)
}
pub fn partner(&self, v: VertexId) -> Option<VertexId> {
some(*self.partner.get(v.index())?)
}
pub fn links(&self) -> &[(VertexId, VertexId)] {
&self.links
}
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 hangs_on(&self, v: VertexId) -> Option<VertexId> {
some(*self.hangs.get(v.index())?)
}
pub fn parts(&self) -> Parts {
let roots = self.forest.roots().len();
let vertices = (roots..self.len())
.map(|v| Placed {
occurrence: self.occurrence[v],
parent: some(self.parent[v]),
inside: some(self.inside[v]),
})
.collect();
let weakenings = self
.vertices()
.filter_map(|q| Some((q, self.hangs_on(q)?)))
.collect();
Parts {
vertices,
cuts: self.cuts.clone(),
links: self.links.clone(),
weakenings,
}
}
fn kind(&self, v: u32) -> Kind {
self.forest.kind(self.occurrence[v as usize])
}
pub fn is_correct(&self, stop: impl FnMut(Progress) -> bool) -> Result<(), NetError> {
if self.is_empty() {
return Err(NetError::Empty);
}
for v in self.vertices() {
let kind = self.kind(v.get());
if matches!(kind, Kind::Atom | Kind::DualAtom) && self.partner[v.index()] == NONE {
return Err(NetError::Unlinked { vertex: v });
}
if kind == Kind::Quest
&& self.premises(v).next().is_none()
&& self.hangs[v.index()] == NONE
{
return Err(NetError::Unattached { vertex: v });
}
}
self.graph.correct(self.criterion.mix, stop)
}
}
impl std::fmt::Display for MellStructure {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.write(f, None)
}
}
impl MellStructure {
pub fn written_in(&self, mode: crate::linear::Mode) -> impl std::fmt::Display + '_ {
crate::linear::nets::In {
structure: self,
mode,
}
}
pub(crate) fn write(
&self,
f: &mut std::fmt::Formatter<'_>,
mode: Option<crate::linear::Mode>,
) -> std::fmt::Result {
let reading = mode
.filter(|mode| mode.is_intuitionistic())
.and_then(|_| self.reading().ok());
let vertex = |f: &mut std::fmt::Formatter<'_>, v: VertexId| {
let o = self.occurrence[v.index()];
match &reading {
Some(reading) => write!(f, "{}[{}]", reading.formula(o), v.get()),
None => write!(f, "{}[{}]", self.forest.formula(o), v.get()),
}
};
match &reading {
Some(reading) => writeln!(f, "{reading}")?,
None => writeln!(f, "{}", self.forest.sequent())?,
}
for q in self
.vertices()
.filter(|&q| self.kind(q.get()) == Kind::Quest)
{
vertex(f, q)?;
f.write_str(":")?;
let mut copies = self.premises(q).peekable();
if copies.peek().is_none() {
f.write_str(" no copy")?;
if let Some(l) = self.hangs_on(q) {
f.write_str(", hangs on ")?;
vertex(f, l)?;
}
}
let mut first = true;
for c in copies {
f.write_str(if first { " " } else { ", " })?;
first = false;
vertex(f, c)?;
if let Some(d) = self.inside(c).filter(|&d| Some(d) != self.inside(q)) {
f.write_str(" in ")?;
vertex(f, d)?;
}
}
f.write_str("\n")?;
}
for &(x, y) in &self.cuts {
f.write_str("cut ")?;
vertex(f, x)?;
f.write_str(" — ")?;
vertex(f, y)?;
f.write_str("\n")?;
}
let mut links: Vec<(VertexId, VertexId)> = self
.links
.iter()
.map(|&(x, y)| (x.min(y), x.max(y)))
.collect();
links.sort_unstable();
for (x, y) in links {
vertex(f, x)?;
f.write_str(" — ")?;
vertex(f, y)?;
f.write_str("\n")?;
}
match self.is_correct(|_| false) {
Ok(()) if self.criterion.mix => {
f.write_str("proof net with Mix (the correctness criterion with Mix holds)")
}
Ok(()) => f.write_str("proof net (the correctness criterion holds)"),
Err(e) => match mode {
Some(mode) => write!(f, "not a proof net: {}", e.describe(self).in_mode(mode)),
None => write!(f, "not a proof net: {}", e.describe(self)),
},
}
}
}
fn some(raw: u32) -> Option<VertexId> {
(raw != NONE).then_some(VertexId::new(raw))
}
fn misplaced(vertex: VertexId, fault: Placement) -> Error {
NetError::Placement { vertex, fault }.into()
}
type Csr = (Box<[u32]>, Box<[u32]>);
fn premises(forest: &Forest, occurrence: &[OccId], parent: &[u32]) -> Result<Csr, Error> {
let n = occurrence.len();
let mut count = vec![0u32; n + 1];
for (v, &p) in parent.iter().enumerate() {
if p == NONE {
continue;
}
let o = occurrence[v];
if forest.parent(o) != Some(occurrence[p as usize]) {
return Err(misplaced(VertexId::new(v as u32), Placement::Premise));
}
count[p as usize] += 1;
}
let mut start = Vec::with_capacity(n + 1);
let mut total = 0;
for &c in &count[..n] {
start.push(total);
total += c;
}
start.push(total);
let mut fill = start.clone();
let mut list = vec![0u32; total as usize];
for (v, &p) in parent.iter().enumerate() {
if p != NONE {
list[fill[p as usize] as usize] = v as u32;
fill[p as usize] += 1;
}
}
for p in 0..n {
let o = occurrence[p];
let premises = &mut list[start[p] as usize..start[p + 1] as usize];
let expected = match forest.kind(o) {
Kind::Tensor | Kind::Par => 2,
Kind::Bang => 1,
Kind::Quest | Kind::Atom | Kind::DualAtom => continue,
Kind::One
| Kind::Bot
| Kind::Top
| Kind::Zero
| Kind::With
| Kind::Plus
| Kind::Forall
| Kind::Exists => {
unreachable!("a unit-free MELL sequent has no such occurrence")
}
};
if expected == 2
&& premises.len() == 2
&& occurrence[premises[0] as usize] != forest.left(o).unwrap()
{
premises.swap(0, 1);
}
let distinct = expected == 1
|| premises.len() != 2
|| occurrence[premises[0] as usize] != occurrence[premises[1] as usize];
if premises.len() != expected || !distinct {
return Err(misplaced(VertexId::new(p as u32), Placement::Premises));
}
}
Ok((start.into_boxed_slice(), list.into_boxed_slice()))
}
fn place_cuts(
forest: &Forest,
occurrence: &[OccId],
parent: &[u32],
inside: &[u32],
roots: usize,
cuts: &[(VertexId, VertexId)],
) -> Result<Vec<(VertexId, VertexId)>, Error> {
let n = occurrence.len();
let mut ended = vec![false; n];
let mut placed = Vec::with_capacity(cuts.len());
for &(x, y) in cuts {
let end = |v: VertexId| v.index() < n && v.index() >= roots && parent[v.index()] == NONE;
if !end(x) || !end(y) || inside[x.index()] != inside[y.index()] {
return Err(misplaced(x, Placement::Cut));
}
let (ox, oy) = (occurrence[x.index()], occurrence[y.index()]);
let (a, d) = match (forest.dual(ox), forest.dual(oy)) {
(Some(dx), _) if dx == oy && ox < oy => (x, y),
(_, Some(dy)) if dy == ox && oy < ox => (y, x),
_ => return Err(misplaced(x, Placement::Cut)),
};
for v in [a, d] {
if std::mem::replace(&mut ended[v.index()], true) {
return Err(misplaced(v, Placement::Cut));
}
}
placed.push((a, d));
}
if let Some(v) = (roots..n).find(|&v| parent[v] == NONE && !ended[v]) {
return Err(misplaced(VertexId::new(v as u32), Placement::Cut));
}
Ok(placed)
}
const VISITING: u32 = NONE - 1;
fn check_boxes(
forest: &Forest,
occurrence: &[OccId],
parent: &[u32],
inside: &[u32],
roots: usize,
) -> Result<(), Error> {
let n = occurrence.len();
let is_bang = |b: u32| b == NONE || forest.kind(occurrence[b as usize]) == Kind::Bang;
for v in 0..n {
let (p, b) = (parent[v], inside[v]);
let fits = match p {
NONE if v < roots => b == NONE,
NONE => is_bang(b),
p => match forest.kind(occurrence[p as usize]) {
Kind::Bang => b == p,
Kind::Quest => is_bang(b),
Kind::Tensor | Kind::Par => b == inside[p as usize],
Kind::Atom
| Kind::DualAtom
| Kind::One
| Kind::Bot
| Kind::Top
| Kind::Zero
| Kind::With
| Kind::Plus
| Kind::Forall
| Kind::Exists => false,
},
};
if !fits {
return Err(misplaced(VertexId::new(v as u32), Placement::Box));
}
}
let mut depth = vec![NONE; n];
let mut path = Vec::new();
for d in 0..n as u32 {
if !is_bang(d) || depth[d as usize] != NONE {
continue;
}
let mut b = d;
while b != NONE && depth[b as usize] == NONE {
depth[b as usize] = VISITING;
path.push(b);
b = inside[b as usize];
}
if b != NONE && depth[b as usize] == VISITING {
return Err(misplaced(VertexId::new(d), Placement::Nesting));
}
let below = if b == NONE { 0 } else { depth[b as usize] + 1 };
for (d, &c) in (below..).zip(path.iter().rev()) {
depth[c as usize] = d;
}
path.clear();
}
Ok(())
}
pub(super) struct Nesting {
inside: Box<[u32]>,
interval: Box<[(u32, u32)]>,
}
impl Nesting {
fn new(s: &MellStructure) -> Self {
let n = s.len();
let mut children = vec![Vec::new(); n + 1];
for d in s.boxes() {
let outer = s.inside[d.index()];
let slot = if outer == NONE { n } else { outer as usize };
children[slot].push(d.get());
}
let mut interval = vec![(0, 0); n];
let mut time = 0;
let mut stack = vec![(n as u32, 0usize)];
while let Some(&mut (b, ref mut next)) = stack.last_mut() {
let slot = if b as usize == n { n } else { b as usize };
if let Some(&c) = children[slot].get(*next) {
*next += 1;
interval[c as usize].0 = time;
time += 1;
stack.push((c, 0));
} else {
if (b as usize) < n {
interval[b as usize].1 = time;
}
stack.pop();
}
}
Self {
inside: s.inside.clone(),
interval: interval.into_boxed_slice(),
}
}
pub(super) fn of(&self, v: VertexId) -> u32 {
self.inside[v.index()]
}
pub(super) fn within(&self, b: u32, outer: u32) -> bool {
if outer == NONE || b == outer {
return true;
}
if b == NONE {
return false;
}
let (i, o) = (self.interval[b as usize], self.interval[outer as usize]);
o.0 < i.0 && i.0 < o.1
}
}
impl MellStructure {
fn check_copies(&self, boxes: &Nesting) -> Result<(), Error> {
for v in self.vertices() {
let p = self.parent[v.index()];
if p != NONE
&& self.kind(p) == Kind::Quest
&& !boxes.within(self.inside[v.index()], self.inside[p as usize])
{
return Err(misplaced(v, Placement::Box));
}
}
Ok(())
}
}