use super::{ProofStructure, SEQUENTIALIZE_BYTES, STOPPED, Scratch, VertexId, afford};
use crate::Error;
use crate::limits::{Limits, Phase, Progress};
use crate::linear::occurrences::{Member, OccId};
use crate::linear::proofs::{Node, NodeId, Proof};
use crate::linear::sequents::Kind;
impl ProofStructure {
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[expect(
clippy::missing_panics_doc,
reason = "the expect states that a sequentialization keeps premises before conclusions, which the stages establish"
)]
pub fn sequentialize(
&self,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Proof, Error> {
let forest = &self.forest;
let arena = forest.sequent().terms().len() as u64
* size_of::<crate::linear::sequents::Term>() as u64;
let bytes = (forest.len() as u64 * SEQUENTIALIZE_BYTES).saturating_add(arena);
afford(bytes, limits)?;
self.is_correct(|progress| {
stop(Progress {
held_bytes: bytes,
..progress
})
})?;
let mut run = Sequentialization {
net: self,
scratch: self.scratch(),
nodes: Vec::with_capacity(self.forest.len()),
steps: Vec::new(),
proved: Vec::new(),
};
let mut stages = 0;
let mut stop = |stage: u64| {
stages += stage;
stop(Progress {
held_bytes: bytes,
..Progress::new(Phase::Net, stage, stages)
})
};
let cuts = self.cuts.iter().map(|&(x, _)| x.occ()).collect();
let root = run.sequentialize(self.forest.roots().to_vec(), cuts, &mut stop);
let Some(root) = root else {
return Err(STOPPED.into());
};
let mode = self.criterion.mode();
let proof = Proof::new(self.forest.clone(), run.nodes, root)
.expect("premises precede conclusions and every occurrence is the forest's")
.with_mode(mode);
debug_assert_eq!(proof.check(mode), Ok(()));
Ok(proof)
}
}
struct Sequentialization<'a> {
net: &'a ProofStructure,
scratch: Scratch,
nodes: Vec<Node>,
steps: Vec<Step>,
proved: Vec<NodeId>,
}
enum Step {
Prove(Vec<OccId>, Vec<OccId>),
Mix,
Tensor(OccId),
Cut(OccId),
Pars(Vec<OccId>),
}
impl Sequentialization<'_> {
fn push(&mut self, node: Node) -> NodeId {
self.nodes.push(node);
NodeId::new(self.nodes.len() as u32 - 1)
}
fn premise(&mut self) -> NodeId {
self.proved
.pop()
.expect("a sub-net proved for every premise")
}
fn sequentialize(
&mut self,
gamma: Vec<OccId>,
cuts: Vec<OccId>,
stop: &mut dyn FnMut(u64) -> bool,
) -> Option<NodeId> {
self.steps.push(Step::Prove(gamma, cuts));
while let Some(step) = self.steps.pop() {
let node = match step {
Step::Prove(gamma, cuts) => {
if stop(1) {
return None;
}
self.stage(gamma, cuts);
continue;
}
Step::Mix => {
let other = self.premise();
let node = self.premise();
self.push(Node::Mix(node, other))
}
Step::Tensor(t) => {
let right = self.premise();
let left = self.premise();
self.push(Node::Tensor(Member::from(t), left, right))
}
Step::Cut(a) => {
let right = self.premise();
let left = self.premise();
self.push(Node::Cut(Member::from(a), left, right))
}
Step::Pars(pars) => {
let mut node = self.premise();
for &p in pars.iter().rev() {
node = self.push(Node::Par(Member::from(p), node));
}
node
}
};
self.proved.push(node);
}
Some(self.premise())
}
fn stage(&mut self, mut gamma: Vec<OccId>, cuts: Vec<OccId>) {
let f = self.net.forest();
let graph = &self.net.graph;
let child = |o: OccId, left: bool| if left { f.left(o) } else { f.right(o) }.unwrap();
let across = |a: OccId| f.dual(a).expect("a cut link's end in a cut formula");
let mut pars = Vec::new();
let mut i = 0;
while i < gamma.len() {
let c = gamma[i];
if f.kind(c) == Kind::Par {
gamma[i] = child(c, true);
gamma.push(child(c, false));
self.scratch.delete(c);
pars.push(c);
} else {
i += 1;
}
}
if !pars.is_empty() {
self.steps.push(Step::Pars(pars));
}
let roots = gamma.iter().chain(&cuts).map(|o| o.get());
let parts = graph.search(&mut self.scratch, roots);
if parts > 1 {
debug_assert!(
self.net.criterion.mix,
"a proof net without Mix is connected"
);
let mut labels: Vec<OccId> = Vec::new();
for &c in gamma.iter().chain(&cuts) {
let label = self.scratch.component(c);
if !labels.contains(&label) {
labels.push(label);
}
}
for (i, &label) in labels.iter().enumerate().rev() {
if i > 0 {
self.steps.push(Step::Mix);
}
let of = |list: &[OccId]| {
list.iter()
.copied()
.filter(|&c| self.scratch.component(c) == label)
.collect()
};
let part = Step::Prove(of(&gamma), of(&cuts));
self.steps.push(part);
}
} else if cuts.is_empty() && gamma.iter().all(|&c| f.is_literal(c)) {
debug_assert!(
gamma.len() == 2
&& self.net.partner(VertexId::of(gamma[0])) == Some(VertexId::of(gamma[1]))
);
let (x, y) = (gamma[0].min(gamma[1]), gamma[0].max(gamma[1]));
let axiom = self.push(Node::Ax(x.into(), y.into()));
self.proved.push(axiom);
} else {
let tensor = gamma
.iter()
.copied()
.filter(|&c| f.kind(c) == Kind::Tensor)
.filter(|&c| self.scratch.is_bridge(c.get(), child(c, true).get()))
.min();
let cut = || {
cuts.iter()
.copied()
.filter(|&a| self.scratch.is_bridge(a.get(), across(a).get()))
.min()
};
let (split, left_end, right_end) = match tensor {
Some(t) => {
self.scratch.delete(t);
(Step::Tensor(t), child(t, true), child(t, false))
}
None => {
let a = cut().expect(
"a connected proof net whose conclusions are not all literals has a \
splitting ⊗ or cut link",
);
graph.remove_cut(&mut self.scratch, a.get());
(Step::Cut(a), a, across(a))
}
};
graph.search(&mut self.scratch, [left_end.get()]);
let (mut left, mut right) = (vec![left_end], vec![right_end]);
let (mut left_cuts, mut right_cuts) = (Vec::new(), Vec::new());
for &c in &gamma {
if matches!(split, Step::Tensor(t) if t == c) {
continue;
}
if self.scratch.reached(c) {
left.push(c);
} else {
right.push(c);
}
}
for &a in &cuts {
if matches!(split, Step::Cut(b) if b == a) {
continue;
}
if self.scratch.reached(a) {
left_cuts.push(a);
} else {
right_cuts.push(a);
}
}
self.steps.push(split);
self.steps.push(Step::Prove(right, right_cuts));
self.steps.push(Step::Prove(left, left_cuts));
}
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::super::{Criterion, ProofStructure, VertexId};
use crate::limits::Limits;
use crate::linear::fragment::Mode;
use crate::linear::occurrences::{Forest, Member, OccId};
#[cfg(feature = "parse")]
use crate::linear::proofs::{Node, NodeId};
use crate::linear::sequents::Sequent;
#[cfg(feature = "parse")]
const fn o(id: u32) -> OccId {
OccId::new(id)
}
#[cfg(feature = "parse")]
fn net(input: &str, mix: bool, links: &[(u32, u32)]) -> ProofStructure {
let s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
let links: Vec<(VertexId, VertexId)> = links
.iter()
.map(|&(x, y)| (VertexId::new(x), VertexId::new(y)))
.collect();
ProofStructure::from_links(
Forest::new(&s).unwrap(),
Criterion {
mix,
..Criterion::MLL
},
&links,
)
.unwrap()
}
#[test]
fn a_high_derivation_needs_no_stack() {
use crate::linear::occurrences::Sign;
use crate::linear::sequents::{Atom, Term, TermId};
const PAIRS: u32 = 2048;
let mut terms: Vec<Term> = (0..PAIRS)
.map(Atom::new)
.flat_map(|a| [Term::Atom(a), Term::DualAtom(a)])
.collect();
let mut chain = TermId::new(2 * (PAIRS - 1));
for a in (0..PAIRS - 1).rev() {
terms.push(Term::Tensor(TermId::new(2 * a), chain));
chain = TermId::new(terms.len() as u32 - 1);
}
let mut roots = vec![chain];
roots.extend((0..PAIRS).map(|a| TermId::new(2 * a + 1)));
let atoms = (0..PAIRS).map(|a| format!("a{a}")).collect();
let forest = Forest::new(&Sequent {
terms,
roots,
atoms,
antecedents: None,
cuts: vec![],
fo: Default::default(),
})
.unwrap();
let literal = |a, sign| forest.literals(Atom::new(a), sign)[0];
let links: Vec<(VertexId, VertexId)> = (0..PAIRS)
.map(|a| {
let (x, y) = (literal(a, Sign::Atom), literal(a, Sign::Dual));
(VertexId::new(x.get()), VertexId::new(y.get()))
})
.collect();
let net = ProofStructure::from_links(forest, Criterion::MLL, &links).unwrap();
let thread = std::thread::Builder::new().stack_size(128 * 1024);
let proof = thread
.spawn(move || net.sequentialize(&Limits::default(), |_| false))
.unwrap();
let proof = proof.join().unwrap().unwrap();
assert_eq!(proof.nodes().len(), 2 * PAIRS as usize - 1);
assert_eq!(proof.check(Mode::CLASSICAL), Ok(()));
}
#[cfg(feature = "parse")]
#[test]
fn classic_nets() {
use Node::*;
let n = NodeId::new;
let proof = net("|- A * B, ~A par ~B", false, &[(1, 4), (2, 5)])
.sequentialize(&Limits::default(), |_| false)
.unwrap();
assert_eq!(
proof.nodes(),
[
Ax(o(1).into(), o(4).into()),
Ax(o(2).into(), o(5).into()),
Tensor(Member::from(o(0)), n(0), n(1)),
Par(Member::from(o(3)), n(2)),
]
);
let proof = net("|- A par B, ~A, ~B", true, &[(1, 3), (2, 4)])
.sequentialize(&Limits::default(), |_| false)
.unwrap();
assert_eq!(
proof.nodes(),
[
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))
]
);
assert_eq!(proof.check(Mode::CLASSICAL.with_mix()), Ok(()));
let proof = net(
"|- A * B, C * (~A par ~B), ~C",
false,
&[(1, 6), (2, 7), (4, 8)],
)
.sequentialize(&Limits::default(), |_| false)
.unwrap();
assert_eq!(
proof.nodes(),
[
Ax(o(4).into(), o(8).into()),
Ax(o(1).into(), o(6).into()),
Ax(o(2).into(), o(7).into()),
Tensor(Member::from(o(0)), n(1), n(2)),
Par(Member::from(o(5)), n(3)),
Tensor(Member::from(o(3)), n(0), n(4)),
]
);
assert!(
net("|- A par B, ~A, ~B", false, &[(1, 3), (2, 4)])
.sequentialize(&Limits::default(), |_| false)
.is_err()
);
}
}