use super::graph::Scratch;
use super::{MellStructure, SCRATCH_BYTES, VERTEX_BYTES};
use crate::Error;
use crate::limits::{Limits, Phase, Progress};
use crate::linear::fragment::Mode;
use crate::linear::nets::{NONE, STOPPED, VertexId, afford};
use crate::linear::occurrences::{Member, OccId};
use crate::linear::proofs::{Node, NodeId, Proof};
use crate::linear::sequents::Kind;
#[derive(Clone, Copy, Debug)]
enum Open {
Par(OccId),
Quest(OccId),
Copy(OccId),
}
enum Step {
Prove(Vec<u32>),
Mix,
Tensor(OccId),
Cut(OccId),
Bang(OccId),
Opened(Vec<Open>),
}
impl MellStructure {
#[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 vertices = self.graph.vertex_count() as u64;
let bytes = vertices.saturating_mul(VERTEX_BYTES + SCRATCH_BYTES + 8);
afford(bytes, limits)?;
self.is_correct(|progress| {
stop(Progress {
held_bytes: bytes,
..progress
})
})?;
let mut run = Sequentialization {
net: self,
scratch: Scratch::new(&self.graph),
nodes: Vec::with_capacity(self.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 mut roots: Vec<u32> = (0..self.forest.roots().len() as u32).collect();
roots.extend(self.graph.cuts_in(NONE));
let Some(root) = run.sequentialize(roots, &mut stop) else {
return Err(STOPPED.into());
};
let mode = if self.criterion.mix {
Mode::CLASSICAL.with_mix()
} else {
Mode::CLASSICAL
};
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(()));
debug_assert!(
self.criterion.mix
|| self.reading().is_err()
|| proof.check(Mode::INTUITIONISTIC).is_ok()
);
Ok(proof)
}
}
struct Sequentialization<'a> {
net: &'a MellStructure,
scratch: Scratch,
nodes: Vec<Node>,
steps: Vec<Step>,
proved: Vec<NodeId>,
}
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 member(&self, v: u32) -> Member {
Member::from(self.net.occurrence[v as usize])
}
fn sequentialize(
&mut self,
gamma: Vec<u32>,
stop: &mut dyn FnMut(u64) -> bool,
) -> Option<NodeId> {
self.steps.push(Step::Prove(gamma));
while let Some(step) = self.steps.pop() {
let node = match step {
Step::Prove(gamma) => {
if stop(1) {
return None;
}
self.stage(gamma);
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::Bang(b) => {
let premise = self.premise();
self.push(Node::Bang(Member::from(b), premise))
}
Step::Opened(rules) => {
let mut node = self.premise();
for &rule in rules.iter().rev() {
node = self.push(match rule {
Open::Par(o) => Node::Par(Member::from(o), node),
Open::Quest(o) => Node::Quest(Member::from(o), node),
Open::Copy(o) => Node::Copy(Member::from(o), node),
});
}
node
}
};
self.proved.push(node);
}
Some(self.premise())
}
fn copies(&self, source: u32, gamma: &mut Vec<u32>, rules: &mut Vec<Open>) {
let graph = &self.net.graph;
for w in graph.wires(source) {
if w < graph.vertex_offset() && graph.parent_edge(w) == source {
rules.push(Open::Copy(self.net.occurrence[w as usize]));
gamma.push(w);
}
}
}
fn stage(&mut self, mut gamma: Vec<u32>) {
let net = self.net;
let graph = &net.graph;
let n = graph.vertex_offset();
let first_cut = graph.first_cut();
let mut rules = Vec::new();
let mut i = 0;
while i < gamma.len() {
let c = gamma[i];
if c >= first_cut {
i += 1;
continue;
}
if c >= n {
gamma[i] = NONE;
i += 1;
self.scratch.delete(c);
self.copies(c, &mut gamma, &mut rules);
continue;
}
match net.kind(c) {
Kind::Par => {
let mut premises = net.premises(VertexId::new(c));
let (l, r) = (premises.next().unwrap(), premises.next().unwrap());
self.scratch.delete(c);
rules.push(Open::Par(net.occurrence[c as usize]));
gamma[i] = l.get();
gamma.push(r.get());
}
Kind::Quest => {
gamma[i] = NONE;
i += 1;
self.scratch.delete(c);
rules.push(Open::Quest(net.occurrence[c as usize]));
self.copies(c, &mut gamma, &mut rules);
}
Kind::Atom
| Kind::DualAtom
| Kind::Tensor
| Kind::Bang
| Kind::One
| Kind::Bot
| Kind::Top
| Kind::Zero
| Kind::With
| Kind::Plus
| Kind::Forall
| Kind::Exists => i += 1,
}
}
gamma.retain(|&c| c != NONE);
if !rules.is_empty() {
self.steps.push(Step::Opened(rules));
}
let parts = graph.search(&mut self.scratch, gamma.iter().copied());
if parts > 1 {
debug_assert!(net.criterion.mix, "a proof net without Mix is connected");
let mut first: Vec<(u32, usize)> = gamma
.iter()
.enumerate()
.map(|(i, &c)| (self.scratch.component(c), i))
.collect();
first.sort_unstable();
first.dedup_by_key(|&mut (label, _)| label);
let labels: Vec<u32> = first.iter().map(|&(label, _)| label).collect();
first.sort_unstable_by_key(|&(_, i)| i);
let mut parts: Vec<Vec<u32>> = vec![Vec::new(); labels.len()];
for &c in &gamma {
let label = self.scratch.component(c);
let j = labels.binary_search(&label).expect("every label is listed");
parts[j].push(c);
}
for (i, &(label, _)) in first.iter().enumerate().rev() {
if i > 0 {
self.steps.push(Step::Mix);
}
let j = labels.binary_search(&label).expect("every label is listed");
self.steps.push(Step::Prove(std::mem::take(&mut parts[j])));
}
} else if gamma
.iter()
.all(|&c| c < n && net.forest.is_literal(net.occurrence[c as usize]))
{
debug_assert!(
gamma.len() == 2 && net.partner[gamma[0] as usize] == gamma[1],
"a connected sub-net of literals is one link"
);
let (x, y) = (self.member(gamma[0]), self.member(gamma[1]));
let axiom = self.push(Node::Ax(x.min(y), x.max(y)));
self.proved.push(axiom);
} else if let [bang] = gamma[..]
&& bang < n
&& net.kind(bang) == Kind::Bang
{
self.scratch.delete(bang);
let premise = net.premises(VertexId::new(bang)).next().unwrap().get();
let mut contents = vec![premise];
contents.extend(graph.doors_in(bang));
contents.extend(graph.cuts_in(bang));
self.steps.push(Step::Bang(net.occurrence[bang as usize]));
self.steps.push(Step::Prove(contents));
} else {
let tensor = gamma
.iter()
.copied()
.filter(|&c| c < n && net.kind(c) == Kind::Tensor)
.filter(|&c| {
let l = net.premises(VertexId::new(c)).next().unwrap().get();
self.scratch.is_bridge(c, l)
})
.min();
let cut = || {
gamma
.iter()
.copied()
.filter(|&c| c >= first_cut)
.filter(|&c| self.scratch.is_bridge(c, graph.cut_ends(c).0))
.min()
};
let (split, l, r) = match tensor {
Some(t) => {
let mut premises = net.premises(VertexId::new(t));
let (l, r) = (
premises.next().unwrap().get(),
premises.next().unwrap().get(),
);
(t, l, r)
}
None => {
let c = cut().expect(
"a connected proof net that is no link and no box has a splitting ⊗ or \
cut link",
);
let (a, d) = graph.cut_ends(c);
(c, a, d)
}
};
self.scratch.delete(split);
graph.search(&mut self.scratch, [l]);
let (mut left, mut right) = (vec![l], vec![r]);
for &c in &gamma {
if c == split {
continue;
}
if self.scratch.reached(c) {
left.push(c);
} else {
right.push(c);
}
}
let occurrence = net.occurrence[l as usize];
self.steps.push(if split < n {
Step::Tensor(net.occurrence[split as usize])
} else {
Step::Cut(occurrence)
});
self.steps.push(Step::Prove(right));
self.steps.push(Step::Prove(left));
}
}
}