use super::{NetError, ProofStructure, STOPPED, VertexId};
use crate::limits::{Phase, Progress};
use crate::linear::fragment::{Mode, Order};
use crate::linear::occurrences::{Forest, OccId, Reading, ShapeError, Side};
use crate::linear::sequents::Kind;
const NONE: u32 = u32::MAX;
const ESSENTIAL_BYTES: u64 = 8 + 4 + 4 + 4 + 2 * 16 + 2 * 4;
pub(crate) fn fixed_successors(
forest: &Forest,
reading: &Reading<'_>,
o: OccId,
) -> impl Iterator<Item = OccId> {
let output = reading.position(o) == Side::Output;
let parent = forest.parent(o).filter(|_| output);
let premises = forest
.children(o)
.filter(move |&c| !output && reading.position(c) == Side::Input);
parent.into_iter().chain(premises)
}
pub(crate) fn is_implication(forest: &Forest, reading: &Reading<'_>, o: OccId) -> bool {
forest.kind(o) == Kind::Par && reading.position(o) == Side::Output
}
impl ProofStructure {
pub fn reading(&self) -> Result<Reading<'_>, ShapeError> {
match self.criterion.order {
Order::Commutative => Reading::new(&self.forest),
Order::Cyclic => Reading::of_mode(&self.forest, Mode::LAMBEK.with_empty_antecedents()),
}
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
pub fn is_essential(&self, mut stop: impl FnMut(Progress) -> bool) -> Result<(), NetError> {
let forest = &self.forest;
if forest.is_empty() {
return Err(NetError::Empty);
}
if let Some(l) = self.unlinked().next() {
return Err(NetError::Unlinked { vertex: l });
}
let reading = self
.reading()
.map_err(|shape| NetError::NotIntuitionistic { shape })?;
if !self.is_cut_free() {
let mut plain = self.clone();
plain.criterion.mix = false;
return plain.is_correct(stop);
}
let n = forest.len();
let mut successors = vec![[NONE; 2]; n];
for o in forest.ids() {
let out = &mut successors[o.index()];
let fixed = fixed_successors(forest, &reading, o);
let link = self.mate(VertexId::of(o)).map(VertexId::occ);
let link = link.filter(|_| reading.position(o) == Side::Input);
for (slot, s) in out.iter_mut().zip(fixed.chain(link)) {
*slot = s.get();
}
}
let next = |v: u32| successors[v as usize].into_iter().filter(|&s| s != NONE);
let held_bytes = n as u64 * ESSENTIAL_BYTES;
let mut rounds = 0;
let mut poll = |stop: &mut dyn FnMut(Progress) -> bool| {
rounds += 1;
stop(Progress {
held_bytes,
..Progress::new(Phase::Net, 1, rounds)
})
};
const UNSEEN: u32 = NONE - 1;
let mut state = vec![UNSEEN; n];
let mut stack: Vec<(u32, usize)> = Vec::new();
for start in 0..n as u32 {
if state[start as usize] != UNSEEN {
continue;
}
state[start as usize] = 0;
stack.push((start, 0));
while let Some(&mut (v, ref mut i)) = stack.last_mut() {
let Some(w) = next(v).nth(*i) else {
state[v as usize] = NONE;
stack.pop();
continue;
};
*i += 1;
match state[w as usize] {
UNSEEN => {
state[w as usize] = stack.len() as u32;
stack.push((w, 0));
}
NONE => {}
place => {
let cycle = stack[place as usize..]
.iter()
.map(|&(u, _)| VertexId::new(u))
.collect();
return Err(NetError::DirectedCycle { cycle });
}
}
}
}
if poll(&mut stop) {
return Err(STOPPED);
}
let goal = reading.goal();
let mut seen = vec![0u32; n];
let mut from = vec![NONE; n];
let mut round = 0u32;
let mut queue = Vec::new();
for l in forest.ids() {
let Some((antecedent, _)) = reading
.implication(l)
.filter(|_| l != goal && is_implication(forest, &reading, l))
else {
continue;
};
if poll(&mut stop) {
return Err(STOPPED);
}
round += 1;
let antecedent = antecedent.get();
seen[l.index()] = round;
seen[antecedent as usize] = round;
queue.clear();
queue.push(antecedent);
let mut i = 0;
while let Some(&v) = queue.get(i) {
i += 1;
if v == goal.get() {
let mut path = vec![VertexId::new(v)];
let mut u = v;
while u != antecedent {
u = from[u as usize];
path.push(VertexId::new(u));
}
path.reverse();
return Err(NetError::NoDominator {
implication: VertexId::of(l),
path,
});
}
for w in next(v) {
if seen[w as usize] != round {
seen[w as usize] = round;
from[w as usize] = v;
queue.push(w);
}
}
}
}
Ok(())
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::super::{Criterion, NetError, ProofStructure, VertexId};
use super::{fixed_successors, is_implication};
use crate::linear::occurrences::{Forest, OccId, Side, Sign};
use crate::linear::search::generate::{self, IllRules, Rng};
use crate::linear::sequents::{Atom, Sequent};
const IMLL: IllRules = IllRules {
units: false,
additives: false,
zero: false,
exponentials: false,
};
fn forest(input: &str) -> Forest {
let s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
Forest::new(&s).unwrap()
}
type Links = [(VertexId, VertexId)];
fn linkings(forest: &Forest, most: usize, each: &mut dyn FnMut(&Links)) {
let atoms = forest.sequent().atom_names().len();
let mut count = 1usize;
for a in 0..atoms {
let n = forest.literals(Atom::new(a as u32), Sign::Atom).len();
if n != forest.literals(Atom::new(a as u32), Sign::Dual).len() {
return;
}
count = (1..=n).fold(count, |c, k| c.saturating_mul(k));
}
if count > most {
return;
}
let duals: Vec<OccId> = forest
.all_literals()
.iter()
.copied()
.filter(|&x| forest.sign(x) == Some(Sign::Dual))
.collect();
let mut links = Vec::new();
let mut used = vec![false; forest.len()];
fn go(
forest: &Forest,
duals: &[OccId],
used: &mut [bool],
links: &mut Vec<(VertexId, VertexId)>,
each: &mut dyn FnMut(&Links),
) {
let Some((&x, rest)) = duals.split_first() else {
each(links);
return;
};
for &y in forest.literals(forest.atom(x).unwrap(), Sign::Atom) {
if !used[y.index()] {
used[y.index()] = true;
links.push((VertexId::of(x), VertexId::of(y)));
go(forest, rest, used, links, each);
links.pop();
used[y.index()] = false;
}
}
}
go(forest, &duals, &mut used, &mut links, each);
}
fn successors(net: &ProofStructure, v: OccId) -> Vec<OccId> {
let forest = net.forest();
let reading = net.reading().unwrap();
let mut out: Vec<OccId> = fixed_successors(forest, &reading, v).collect();
if reading.position(v) == Side::Input
&& let Some(w) = net.partner(VertexId::of(v))
{
out.push(w.occ());
}
out
}
fn dominated_by_every_path(net: &ProofStructure) -> bool {
let forest = net.forest();
let reading = net.reading().unwrap();
let goal = reading.goal();
let mut paths = 0u32;
fn around(
net: &ProofStructure,
v: OccId,
l: OccId,
goal: OccId,
on: &mut Vec<OccId>,
paths: &mut u32,
) -> bool {
*paths += 1;
assert!(*paths < 1 << 20, "too many paths to enumerate");
if v == goal {
return !on.contains(&l);
}
on.push(v);
let found = successors(net, v)
.into_iter()
.any(|w| !on.contains(&w) && around(net, w, l, goal, on, paths));
on.pop();
found
}
forest
.ids()
.filter(|&l| is_implication(forest, &reading, l) && l != goal)
.all(|l| {
!around(
net,
forest.left(l).unwrap(),
l,
goal,
&mut Vec::new(),
&mut paths,
)
})
}
#[expect(
clippy::wildcard_enum_match_arm,
reason = "the criterion fails with these two witnesses only"
)]
fn check_witness(net: &ProofStructure, error: &NetError) {
let edge = |a: VertexId, b: VertexId| successors(net, a.occ()).contains(&b.occ());
match error {
NetError::DirectedCycle { cycle } => {
assert_ne!(*cycle, []);
for (i, &a) in cycle.iter().enumerate() {
assert!(edge(a, cycle[(i + 1) % cycle.len()]), "{cycle:?}");
}
}
NetError::NoDominator { implication, path } => {
let forest = net.forest();
let reading = net.reading().unwrap();
assert_eq!(path[0].occ(), forest.left(implication.occ()).unwrap());
assert_eq!(path.last().unwrap().occ(), reading.goal());
assert!(!path.contains(implication));
assert!(path.windows(2).all(|w| edge(w[0], w[1])), "{path:?}");
}
other => panic!("not a witness of the essential criterion: {other}"),
}
}
#[test]
#[expect(
clippy::wildcard_enum_match_arm,
reason = "the criterion fails with these two witnesses only"
)]
fn agrees_with_the_switchings() {
let mut rng = Rng::new(35);
let (mut structures, mut nets, mut cycles, mut dominators) = (0, 0, 0, 0);
for _ in 0..400 {
let budget = 2 + rng.below(9);
let generate::Ill {
mut hypotheses,
mut goal,
..
} = generate::ill(&mut rng, IMLL, 3, budget);
for mutated in [false, true] {
if mutated && !generate::mutate_two_sided(&mut rng, &mut hypotheses, &mut goal, 3) {
continue;
}
let text = generate::two_sided(&hypotheses, &goal);
let forest = forest(&text);
linkings(&forest, 120, &mut |links| {
let net =
ProofStructure::from_links(forest.clone(), Criterion::MLL, links).unwrap();
let switchings = net.is_correct(|_| false);
let essential = net.is_essential(|_| false);
assert_eq!(
switchings.is_ok(),
essential.is_ok(),
"{text:?} {links:?}: {switchings:?} against {essential:?}"
);
match &essential {
Ok(()) => nets += 1,
Err(error) => {
check_witness(&net, error);
match error {
NetError::DirectedCycle { .. } => cycles += 1,
_ => {
dominators += 1;
assert!(!dominated_by_every_path(&net), "{text:?} {links:?}");
}
}
}
}
if !matches!(essential, Err(NetError::DirectedCycle { .. })) {
assert_eq!(essential.is_ok(), dominated_by_every_path(&net));
}
structures += 1;
});
}
}
assert!(
nets > 300 && cycles > 300 && dominators > 100,
"{structures} structures: {nets} nets, {cycles} cycles, {dominators} without a dominator"
);
}
#[test]
fn witnesses() {
let links = |pairs: &[(u32, u32)]| -> Vec<(VertexId, VertexId)> {
pairs
.iter()
.map(|&(x, y)| (VertexId::new(x), VertexId::new(y)))
.collect()
};
let classical = ProofStructure::from_links(
forest("|- a par b, ~a, ~b"),
Criterion::MLL,
&links(&[(1, 3), (2, 4)]),
)
.unwrap();
assert!(matches!(
classical.is_essential(|_| false),
Err(NetError::NotIntuitionistic { .. })
));
let cycle = ProofStructure::from_links(
forest("a -o a |- b -o b"),
Criterion::MLL,
&links(&[(2, 1), (4, 5)]),
)
.unwrap();
let Err(error) = cycle.is_essential(|_| false) else {
panic!("a cycle is no net");
};
assert_eq!(
error.to_string(),
"a directed cycle of the essential net runs through 0, 2, 1"
);
let around = ProofStructure::from_links(
forest("|- (a -o b) * (b -o a)"),
Criterion::MLL,
&links(&[(2, 6), (5, 3)]),
)
.unwrap();
let Err(error) = around.is_essential(|_| false) else {
panic!("a hypothesis used outside its body is no net");
};
assert_eq!(
error.describe(&around).to_string(),
"the implication ~a ⅋ b[1] does not dominate its antecedent: the path ~a[2], a[6], ~b ⅋ a[4], (~a ⅋ b) ⊗ (~b ⅋ a)[0] reaches the goal around it"
);
assert!(matches!(
cycle.is_essential(|_| true),
Err(NetError::DirectedCycle { .. })
));
let net = ProofStructure::from_links(
forest("a -o b, a |- b"),
Criterion::MLL,
&links(&[(3, 1), (2, 4)]),
)
.unwrap();
assert_eq!(net.is_essential(|_| false), Ok(()));
}
}