use super::{DOOR_BYTES, MOST, MellStructure, Nesting};
use crate::Error;
use crate::limits::{Limits, Phase, Progress, Refusal, Space};
use crate::linear::nets::{NONE, NetError, STOPPED, VertexId, afford};
use crate::linear::sequents::Kind;
#[derive(Clone, Debug, Default)]
pub(super) struct Graph {
start: Box<[u32]>,
to: Box<[u32]>,
switched: Box<[bool]>,
level: Box<[u32]>,
n: u32,
door_of: Box<[u32]>,
cut_of: Box<[(u32, u32)]>,
depths: Box<[Depth]>,
}
#[derive(Clone, Copy, Debug)]
struct Depth {
level: u32,
vertices: u64,
kept: u64,
}
struct Builder<'a> {
s: &'a MellStructure,
parent: Vec<u32>,
extra: Vec<(u32, u32)>,
doors: Vec<(u32, u32)>,
stamp: Vec<(u32, u32)>,
limits: &'a Limits,
}
impl Builder<'_> {
fn door(&mut self, q: u32, b: u32) -> Result<(u32, bool), Error> {
let (stamped, door) = self.stamp[b as usize];
if stamped == q {
return Ok((door, false));
}
let id = self.s.len() as u64 + self.doors.len() as u64;
if id >= MOST {
return Err(Error::Refused(Refusal::Index {
what: Space::Vertex,
count: id + 1,
most: MOST,
}));
}
let bytes = (self.doors.len() as u64 + 1) * DOOR_BYTES + self.extra.len() as u64 * 8;
afford(bytes, self.limits)?;
self.doors.push((b, q));
self.parent.push(NONE);
self.stamp[b as usize] = (q, id as u32);
Ok((id as u32, true))
}
fn wire(&mut self, q: u32, end: u32, copy: bool, boxes: &Nesting) -> Result<(), Error> {
let home = self.s.inside[q as usize];
let mut current = boxes.of(VertexId::new(end));
let source = if current == home {
q
} else {
let (door, fresh) = self.door(q, current)?;
if !fresh {
self.attach(door, end, copy);
return Ok(());
}
door
};
self.attach(source, end, copy);
while current != home {
let bang = current;
let outer = self.s.inside[bang as usize];
let (source, fresh) = if outer == home {
(q, true)
} else {
self.door(q, outer)?
};
if self.s.parent[bang as usize] != q {
self.extra.push((source, bang));
}
if !fresh {
break;
}
current = outer;
}
Ok(())
}
fn attach(&mut self, source: u32, end: u32, copy: bool) {
if copy {
self.parent[end as usize] = source;
} else {
self.extra.push((source, end));
}
}
}
impl Graph {
pub(super) fn new(s: &MellStructure, boxes: &Nesting, limits: &Limits) -> Result<Self, Error> {
let n = s.len();
let mut b = Builder {
s,
parent: vec![NONE; n],
extra: Vec::new(),
doors: Vec::new(),
stamp: vec![(NONE, NONE); n],
limits,
};
for v in 0..n as u32 {
let p = s.parent[v as usize];
if p == NONE {
continue;
}
match s.kind(p) {
Kind::Tensor | Kind::Par => b.parent[v as usize] = p,
Kind::Bang | Kind::Quest => {}
Kind::Atom
| Kind::DualAtom
| Kind::One
| Kind::Bot
| Kind::Top
| Kind::Zero
| Kind::With
| Kind::Plus
| Kind::Forall
| Kind::Exists => unreachable!("only the structure's connectives have premises"),
}
}
for q in 0..n as u32 {
if s.kind(q) != Kind::Quest {
continue;
}
for c in s.premises(VertexId::new(q)) {
b.wire(q, c.get(), true, boxes)?;
}
if let Some(l) = s.hangs_on(VertexId::new(q)) {
b.wire(q, l.get(), false, boxes)?;
}
}
for &(x, y) in s.links() {
b.extra.push((x.get(), y.get()));
}
let first_cut = n as u64 + b.doors.len() as u64;
if first_cut + s.cuts.len() as u64 > MOST {
return Err(Error::Refused(Refusal::Index {
what: Space::Vertex,
count: first_cut + s.cuts.len() as u64,
most: MOST,
}));
}
for (i, &(x, y)) in s.cuts.iter().enumerate() {
let c = (first_cut + i as u64) as u32;
b.parent.push(NONE);
b.parent[x.index()] = c;
b.parent[y.index()] = c;
}
let total = n + b.doors.len() + s.cuts.len();
for v in 0..total {
if b.parent[v] != NONE {
b.extra.push((b.parent[v], v as u32));
}
}
let slots = total as u64 + 2 * b.extra.len() as u64
- (b.parent.iter().filter(|&&p| p != NONE).count() as u64);
if slots >= u64::from(u32::MAX) {
return Err(Error::Refused(Refusal::Index {
what: Space::Vertex,
count: slots,
most: u64::from(u32::MAX) - 1,
}));
}
afford(slots * 4 + total as u64 * super::VERTEX_BYTES, limits)?;
let mut degree = vec![1u32; total];
for &(x, y) in &b.extra {
if b.parent[y as usize] != x {
degree[y as usize] += 1;
}
degree[x as usize] += 1;
}
let mut start = Vec::with_capacity(total + 1);
let mut sum = 0u32;
for &d in °ree {
start.push(sum);
sum += d;
}
start.push(sum);
let mut to = vec![NONE; sum as usize];
let mut fill: Vec<u32> = start[..total].iter().map(|&s| s + 1).collect();
for &(x, y) in &b.extra {
if b.parent[y as usize] == x {
to[start[y as usize] as usize] = x;
} else {
to[fill[y as usize] as usize] = x;
fill[y as usize] += 1;
}
to[fill[x as usize] as usize] = y;
fill[x as usize] += 1;
}
let mut switched = Vec::with_capacity(total);
let mut level = Vec::with_capacity(total);
for v in 0..n as u32 {
switched.push(matches!(s.kind(v), Kind::Par | Kind::Quest));
level.push(s.inside[v as usize]);
}
let mut door_of = Vec::with_capacity(b.doors.len());
for &(depth, q) in &b.doors {
switched.push(true);
level.push(depth);
door_of.push(q);
}
for &(x, _) in &s.cuts {
switched.push(false);
level.push(s.inside[x.index()]);
}
let mut graph = Self {
start: start.into_boxed_slice(),
to: to.into_boxed_slice(),
switched: switched.into_boxed_slice(),
level: level.into_boxed_slice(),
n: n as u32,
door_of: door_of.into_boxed_slice(),
cut_of: s.cuts.iter().map(|&(x, y)| (x.get(), y.get())).collect(),
depths: Box::default(),
};
graph.depths = graph.count(s);
Ok(graph)
}
fn count(&self, s: &MellStructure) -> Box<[Depth]> {
let n = self.n as usize;
let slot = |level: u32| if level == NONE { n } else { level as usize };
let mut vertices = vec![0u64; n + 1];
let mut ends = vec![0u64; n + 1];
let mut dropped = vec![0u64; n + 1];
for v in 0..self.len() {
let d = slot(self.level[v]);
vertices[d] += 1;
let present = self.slots(v as u32).filter(|&i| self.to[i] != NONE).count() as u64;
ends[d] += present;
if self.switched[v] {
let class = self.slots(v as u32).skip(1).count() as u64;
dropped[d] += class.saturating_sub(1);
}
}
let kept = |d: usize| ends[d] / 2 - dropped[d];
let mut depths = vec![Depth {
level: NONE,
vertices: vertices[n],
kept: kept(n),
}];
depths.extend(s.boxes().map(|d| Depth {
level: d.get(),
vertices: vertices[d.index()],
kept: kept(d.index()),
}));
depths.into_boxed_slice()
}
fn len(&self) -> usize {
self.switched.len()
}
pub(super) fn vertex_count(&self) -> usize {
self.len()
}
pub(super) fn vertex_offset(&self) -> u32 {
self.n
}
pub(super) fn wires(&self, v: u32) -> impl Iterator<Item = u32> + '_ {
self.slots(v).skip(1).map(|s| self.to[s])
}
pub(super) fn parent_edge(&self, v: u32) -> u32 {
self.to[self.start[v as usize] as usize]
}
pub(super) fn doors_in(&self, bang: u32) -> impl Iterator<Item = u32> + '_ {
(self.n..self.first_cut()).filter(move |&g| self.level[g as usize] == bang)
}
pub(super) fn cuts_in(&self, level: u32) -> impl Iterator<Item = u32> + '_ {
(self.first_cut()..self.len() as u32).filter(move |&g| self.level[g as usize] == level)
}
pub(super) fn first_cut(&self) -> u32 {
(self.len() - self.cut_of.len()) as u32
}
pub(super) fn cut_ends(&self, c: u32) -> (u32, u32) {
self.cut_of[(c - self.first_cut()) as usize]
}
fn slots(&self, v: u32) -> std::ops::Range<usize> {
self.start[v as usize] as usize..self.start[v as usize + 1] as usize
}
pub(super) fn doors(&self, bang: VertexId) -> Vec<VertexId> {
let n = self.n as usize;
let mut doors: Vec<VertexId> = (n..self.first_cut() as usize)
.filter(|&g| self.level[g] == bang.get())
.map(|g| VertexId::new(self.door_of[g - n]))
.collect();
doors.sort_unstable();
doors
}
fn named(&self, g: u32) -> VertexId {
if g < self.n {
VertexId::new(g)
} else if g < self.first_cut() {
VertexId::new(self.door_of[(g - self.n) as usize])
} else {
VertexId::new(self.cut_ends(g).0)
}
}
fn at(level: u32, error: NetError) -> NetError {
if level == NONE {
error
} else {
NetError::InBox {
door: VertexId::new(level),
error: Box::new(error),
}
}
}
pub(super) fn correct(
&self,
mix: bool,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<(), NetError> {
let mut scratch = Scratch::new(self);
let held_bytes = self.len() as u64 * super::SCRATCH_BYTES;
let mut rounds = 0;
let mut stop = |round: u64| {
rounds += round;
stop(Progress {
held_bytes,
..Progress::new(Phase::Net, round, rounds)
})
};
match self.acyclic(&mut scratch, &mut stop) {
None => return Err(STOPPED),
Some(false) => {
let Some(cycle) = self.cycle(&mut scratch, &mut stop) else {
return Err(STOPPED);
};
let level = self.level[cycle[0] as usize];
let first_cut = self.first_cut();
let cycle = cycle
.into_iter()
.filter(|&g| g < first_cut)
.map(|g| self.named(g))
.collect();
return Err(Self::at(level, NetError::SwitchingCycle { cycle }));
}
Some(true) => {}
}
if mix {
return Ok(());
}
for depth in &self.depths {
if depth.kept + 1 != depth.vertices {
let parts = self.parts(&mut scratch, depth.level);
return Err(Self::at(depth.level, NetError::Disconnected { parts }));
}
}
Ok(())
}
pub(super) fn search(
&self,
scratch: &mut Scratch,
roots: impl IntoIterator<Item = u32>,
) -> u32 {
scratch.disc.fill(NONE);
let mut time = 0;
let mut trees = 0;
for r in roots {
if scratch.deleted[r as usize] || scratch.disc[r as usize] != NONE {
continue;
}
trees += 1;
self.discover(scratch, r, NONE, r, &mut time);
while let Some(&(v, next)) = scratch.stack.last() {
if next < self.start[v as usize + 1] {
scratch.stack.last_mut().unwrap().1 = next + 1;
let w = self.to[next as usize];
if w == NONE
|| scratch.removed[next as usize]
|| scratch.deleted[w as usize]
|| w == scratch.dfs_parent[v as usize]
{
continue;
}
if scratch.disc[w as usize] == NONE {
self.discover(scratch, w, v, r, &mut time);
} else {
let (lv, dw) = (scratch.low[v as usize], scratch.disc[w as usize]);
scratch.low[v as usize] = lv.min(dw);
}
} else {
scratch.stack.pop();
let p = scratch.dfs_parent[v as usize];
if p != NONE {
let (lp, lv) = (scratch.low[p as usize], scratch.low[v as usize]);
scratch.low[p as usize] = lp.min(lv);
scratch.bridge[v as usize] = lv > scratch.disc[p as usize];
}
}
}
}
trees
}
fn discover(&self, scratch: &mut Scratch, v: u32, parent: u32, root: u32, time: &mut u32) {
scratch.disc[v as usize] = *time;
scratch.low[v as usize] = *time;
*time += 1;
scratch.dfs_parent[v as usize] = parent;
scratch.component[v as usize] = root;
scratch.bridge[v as usize] = false;
scratch.stack.push((v, self.start[v as usize]));
}
fn present(&self, scratch: &Scratch, slot: usize) -> bool {
let w = self.to[slot];
w != NONE && !scratch.removed[slot] && !scratch.deleted[w as usize]
}
fn deletable(&self, scratch: &Scratch, v: u32) -> bool {
let mut slots = self.slots(v);
if self.switched[v as usize] {
slots.end = slots.start + 1;
}
slots.all(|i| !self.present(scratch, i) || scratch.is_bridge(v, self.to[i]))
}
fn acyclic(&self, scratch: &mut Scratch, stop: &mut dyn FnMut(u64) -> bool) -> Option<bool> {
let n = self.len();
let mut remaining = scratch.deleted.iter().filter(|&&d| !d).count();
while remaining > 0 {
if stop(1) {
return None;
}
self.search(scratch, 0..n as u32);
let before = remaining;
for v in 0..n as u32 {
if !scratch.deleted[v as usize] && self.deletable(scratch, v) {
scratch.deleted[v as usize] = true;
remaining -= 1;
}
}
if remaining == before {
return Some(false);
}
}
Some(true)
}
fn twin(&self, v: u32, w: u32) -> usize {
self.slots(w)
.find(|&s| self.to[s] == v)
.expect("the edge exists at both ends")
}
fn cycle(&self, scratch: &mut Scratch, stop: &mut dyn FnMut(u64) -> bool) -> Option<Vec<u32>> {
let n = self.len();
scratch.stuck.clone_from(&scratch.deleted);
for v in 0..n as u32 {
for s in self.slots(v) {
let w = self.to[s];
if w == NONE
|| w < v
|| scratch.removed[s]
|| scratch.stuck[v as usize]
|| scratch.stuck[w as usize]
{
continue;
}
let t = self.twin(v, w);
scratch.removed[s] = true;
scratch.removed[t] = true;
scratch.deleted.clone_from(&scratch.stuck);
let acyclic = self.acyclic(scratch, stop)?;
if acyclic {
scratch.removed[s] = false;
scratch.removed[t] = false;
} else {
scratch.stuck.clone_from(&scratch.deleted);
}
}
}
let first = (0..n as u32)
.find(|&v| !scratch.stuck[v as usize])
.expect("a switching cycle is left");
let mut cycle = Vec::new();
let (mut previous, mut current) = (NONE, first);
loop {
cycle.push(current);
let next = self
.slots(current)
.map(|s| (s, self.to[s]))
.find(|&(s, w)| {
w != NONE && w != previous && !scratch.removed[s] && !scratch.stuck[w as usize]
})
.map(|(_, w)| w)
.expect("every vertex of the cycle has two edges on it");
if next == first {
break;
}
(previous, current) = (current, next);
}
Some(cycle)
}
fn parts(&self, scratch: &mut Scratch, level: u32) -> Vec<Vec<VertexId>> {
let n = self.len();
scratch.deleted.fill(false);
scratch.removed.fill(false);
for v in 0..n as u32 {
if self.switched[v as usize] {
for s in self.slots(v).skip(2) {
let w = self.to[s];
scratch.removed[s] = true;
scratch.removed[self.twin(v, w)] = true;
}
}
}
let at = (0..n as u32).filter(|&v| self.level[v as usize] == level);
self.search(scratch, at.clone());
let mut index = vec![NONE; n];
let mut parts: Vec<(u32, Vec<VertexId>)> = Vec::new();
for v in at {
let first = self.start[v as usize] as usize;
if self.to[first] != NONE && !scratch.removed[first] {
continue;
}
let label = scratch.component[v as usize];
if index[label as usize] == NONE {
index[label as usize] = parts.len() as u32;
parts.push((label, Vec::new()));
}
parts[index[label as usize] as usize].1.push(self.named(v));
}
scratch.removed.fill(false);
parts.sort_by_key(|(label, _)| *label);
parts.into_iter().map(|(_, part)| part).collect()
}
}
pub(super) struct Scratch {
deleted: Vec<bool>,
stuck: Vec<bool>,
removed: Vec<bool>,
disc: Vec<u32>,
low: Vec<u32>,
dfs_parent: Vec<u32>,
bridge: Vec<bool>,
component: Vec<u32>,
stack: Vec<(u32, u32)>,
}
impl Scratch {
pub(super) fn new(graph: &Graph) -> Self {
let n = graph.len();
Self {
deleted: vec![false; n],
stuck: vec![false; n],
removed: vec![false; graph.to.len()],
disc: vec![NONE; n],
low: vec![NONE; n],
dfs_parent: vec![NONE; n],
bridge: vec![false; n],
component: vec![NONE; n],
stack: Vec::with_capacity(n),
}
}
pub(super) fn delete(&mut self, v: u32) {
self.deleted[v as usize] = true;
}
pub(super) fn reached(&self, v: u32) -> bool {
self.disc[v as usize] != NONE
}
pub(super) fn component(&self, v: u32) -> u32 {
self.component[v as usize]
}
pub(super) fn is_bridge(&self, v: u32, w: u32) -> bool {
(self.dfs_parent[w as usize] == v && self.bridge[w as usize])
|| (self.dfs_parent[v as usize] == w && self.bridge[v as usize])
}
}