use super::{BUILD_BYTES, MOST, MellStructure, Parts, Placed, VERTEX_BYTES};
use crate::Error;
use crate::limits::{Limits, Phase, Progress, Refusal, Space};
use crate::linear::fragment::Mode;
use crate::linear::nets::{Criterion, NONE, NetError, STOPPED, VertexId, afford};
use crate::linear::occurrences::OccId;
use crate::linear::proofs::{Node, NodeId, Proof};
const UNFOLD_BYTES: u64 = 8 + 28 + 8 + 12 + 16;
impl MellStructure {
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 mode = if criterion.mix {
Mode::CLASSICAL.with_mix()
} else {
Mode::CLASSICAL
};
Self::exist(proof.sequent().fragment(), mode)?;
proof.check_within(mode, limits, &mut stop)?;
let vertices = unfolded(proof);
if vertices > MOST {
return Err(Error::Refused(Refusal::Index {
what: Space::Vertex,
count: vertices,
most: MOST,
}));
}
let bytes = vertices.saturating_mul(VERTEX_BYTES + BUILD_BYTES + UNFOLD_BYTES);
afford(bytes, limits)?;
let mut unfolding = Unfolding::new(proof, vertices as usize);
unfolding.run(&mut |done| {
stop(Progress {
held_bytes: bytes,
..Progress::new(Phase::Net, 1, done)
})
})?;
let parts = unfolding.parts();
let structure = Self::from_parts(proof.forest().clone(), criterion, &parts, limits)?;
structure.is_correct(|progress| {
stop(Progress {
held_bytes: bytes,
..progress
})
})?;
Ok(structure)
}
}
fn unfolded(proof: &Proof) -> u64 {
let nodes = proof.nodes();
let mut uses = vec![0u64; nodes.len()];
let root = proof.root().index();
uses[root] = 1;
let mut total = 0u64;
for i in (0..=root).rev() {
let made = match nodes[i] {
Node::Ax(..) => 2,
Node::Copy(..) | Node::Mix(..) | Node::Cut(..) => 0,
Node::Tensor(..)
| Node::Par(..)
| Node::Bang(..)
| Node::Quest(..)
| Node::Weaken(..)
| Node::One(_)
| Node::Bot(..)
| Node::With(..)
| Node::Plus(..)
| Node::Top(_) => 1,
Node::Forall(..) | Node::Exists(..) => unreachable!("a MELL proof has no binder"),
};
total = total.saturating_add(uses[i].saturating_mul(made));
for p in nodes[i].premises() {
uses[p.index()] = uses[p.index()].saturating_add(uses[i]);
}
}
total
}
struct Frame {
node: NodeId,
read: u8,
start: u32,
middle: u32,
links: u32,
}
struct Unfolding<'a> {
proof: &'a Proof,
occurrence: Vec<OccId>,
boxed: Vec<u32>,
premises: Vec<Vec<u32>>,
doors: Vec<u32>,
open_boxes: Vec<u32>,
open: Vec<Vec<u32>>,
waiting: Vec<Vec<u32>>,
links: Vec<(u32, u32)>,
cuts: Vec<(u32, u32)>,
weakenings: Vec<(u32, u32)>,
}
impl<'a> Unfolding<'a> {
fn new(proof: &'a Proof, vertices: usize) -> Self {
let n = proof.forest().len();
Self {
proof,
occurrence: Vec::with_capacity(vertices),
boxed: Vec::with_capacity(vertices),
premises: Vec::with_capacity(vertices),
doors: Vec::new(),
open_boxes: Vec::new(),
open: vec![Vec::new(); n],
waiting: vec![Vec::new(); n],
links: Vec::new(),
cuts: Vec::new(),
weakenings: Vec::new(),
}
}
fn make(&mut self, o: OccId, premises: Vec<u32>) -> u32 {
let v = self.occurrence.len() as u32;
self.occurrence.push(o);
self.boxed
.push(self.open_boxes.last().copied().unwrap_or(NONE));
self.premises.push(premises);
self.open[o.index()].push(v);
v
}
fn take(&mut self, o: OccId, from: u32, to: u32) -> u32 {
let list = &mut self.open[o.index()];
let i = list.partition_point(|&v| v < to);
assert!(
i > 0 && list[i - 1] >= from,
"a checked premise holds its rule's subformula"
);
list.remove(i - 1)
}
fn run(&mut self, stop: &mut dyn FnMut(u64) -> bool) -> Result<(), NetError> {
let nodes = self.proof.nodes();
let mut frames = vec![self.enter(self.proof.root())];
let mut read = 0u64;
while let Some(frame) = frames.last_mut() {
let node = nodes[frame.node.index()];
let premise = node.premises().nth(frame.read as usize);
if let Some(p) = premise {
if frame.read == 1 {
frame.middle = self.occurrence.len() as u32;
}
frame.read += 1;
read += 1;
if stop(read) {
return Err(STOPPED);
}
let entered = self.enter(p);
frames.push(entered);
continue;
}
let frame = frames.pop().expect("the frame just looked at");
self.exit(node, &frame);
}
Ok(())
}
fn enter(&mut self, id: NodeId) -> Frame {
let node = self.proof.node(id);
let mut middle = self.occurrence.len() as u32;
match node {
Node::Bang(..) => {
self.open_boxes.push(self.doors.len() as u32);
self.doors.push(NONE);
}
Node::Quest(q, _) => {
let a = self.child(q.occ());
middle = self.waiting[a.index()].len() as u32;
}
Node::Ax(..)
| Node::Tensor(..)
| Node::Par(..)
| Node::One(_)
| Node::Bot(..)
| Node::With(..)
| Node::Plus(..)
| Node::Top(_)
| Node::Copy(..)
| Node::Weaken(..)
| Node::Mix(..)
| Node::Cut(..)
| Node::Forall(..)
| Node::Exists(..) => {}
}
Frame {
node: id,
read: 0,
start: self.occurrence.len() as u32,
middle,
links: self.links.len() as u32,
}
}
fn child(&self, o: OccId) -> OccId {
self.proof
.forest()
.left(o)
.expect("a unary connective has a subformula")
}
fn exit(&mut self, node: Node, frame: &Frame) {
let f = self.proof.forest();
let end = self.occurrence.len() as u32;
match node {
Node::Ax(x, y) => {
let vx = self.make(x.occ(), Vec::new());
let vy = self.make(y.occ(), Vec::new());
self.links.push((vx, vy));
}
Node::Tensor(o, _, _) => {
let o = o.occ();
let l = self.take(f.left(o).unwrap(), frame.start, frame.middle);
let r = self.take(f.right(o).unwrap(), frame.middle, end);
self.make(o, vec![l, r]);
}
Node::Par(o, _) => {
let o = o.occ();
let l = self.take(f.left(o).unwrap(), frame.start, end);
let r = self.take(f.right(o).unwrap(), frame.start, end);
self.make(o, vec![l, r]);
}
Node::Bang(o, _) => {
let o = o.occ();
let a = self.take(self.child(o), frame.start, end);
let b = self.open_boxes.pop().expect("the box its entry opened");
let door = self.make(o, vec![a]);
self.doors[b as usize] = door;
}
Node::Quest(o, _) => {
let o = o.occ();
let a = self.child(o);
let copies = self.waiting[a.index()].split_off(frame.middle as usize);
let q = self.make(o, copies);
if self.premises[q as usize].is_empty() {
self.weakenings
.push((q, self.links[frame.links as usize].0));
}
}
Node::Weaken(o, _) => {
let q = self.make(o.occ(), Vec::new());
self.weakenings
.push((q, self.links[frame.links as usize].0));
}
Node::Copy(a, _) => {
let a = a.occ();
let copy = self.take(a, frame.start, end);
self.waiting[a.index()].push(copy);
}
Node::Mix(..) => {}
Node::One(_)
| Node::Bot(..)
| Node::With(..)
| Node::Plus(..)
| Node::Top(_)
| Node::Forall(..)
| Node::Exists(..) => {
unreachable!("a checked proof of unit-free MELL has no such rule")
}
Node::Cut(a, _, _) => {
let a = a.occ();
let d = f.dual(a).expect("a checked cut is on a cut formula's tree");
let x = self.take(a, frame.start, frame.middle);
let y = self.take(d, frame.middle, end);
self.cuts.push((x, y));
}
}
}
fn parts(self) -> Parts {
let f = self.proof.forest();
let roots: Vec<u32> = f
.roots()
.iter()
.map(|r| {
let list = &self.open[r.index()];
debug_assert_eq!(list.len(), 1, "a proof concludes each root once");
list[0]
})
.collect();
let n = self.occurrence.len();
let mut new = vec![NONE; n];
let mut order = Vec::with_capacity(n);
for &r in &roots {
new[r as usize] = order.len() as u32;
order.push(r);
}
let mut stack = Vec::new();
let ends: Vec<u32> = self.cuts.iter().flat_map(|&(x, y)| [x, y]).collect();
for &r in roots.iter().chain(&ends) {
stack.push(r);
while let Some(v) = stack.pop() {
if new[v as usize] == NONE {
new[v as usize] = order.len() as u32;
order.push(v);
}
stack.extend(self.premises[v as usize].iter().rev());
}
}
let mut parent = vec![NONE; n];
for v in 0..n {
for &w in &self.premises[v] {
parent[w as usize] = v as u32;
}
}
let renamed = |v: u32| VertexId::new(new[v as usize]);
let vertices = order[roots.len()..]
.iter()
.map(|&v| {
let b = self.boxed[v as usize];
let inside = (b != NONE).then(|| renamed(self.doors[b as usize]));
match parent[v as usize] {
NONE => Placed::cut(self.occurrence[v as usize], inside),
p => Placed::new(self.occurrence[v as usize], renamed(p), inside),
}
})
.collect();
Parts {
vertices,
cuts: self
.cuts
.iter()
.map(|&(x, y)| (renamed(x), renamed(y)))
.collect(),
links: self
.links
.iter()
.map(|&(x, y)| (renamed(x), renamed(y)))
.collect(),
weakenings: self
.weakenings
.iter()
.map(|&(q, l)| (renamed(q), renamed(l)))
.collect(),
}
}
}