use super::refutation::{Basis, Marking, RefutationFault};
use crate::hash::HashMap;
use crate::linear::occurrences::{Forest, OccId, Sign};
use crate::linear::sequents::Kind;
const INVARIANT: &str = "basis of the coverable markings";
#[derive(Debug)]
pub(crate) enum Failed {
Fault(RefutationFault),
Stopped,
}
impl From<RefutationFault> for Failed {
fn from(fault: RefutationFault) -> Self {
Self::Fault(fault)
}
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
struct Arcs {
inputs: Vec<(usize, u64)>,
outputs: Vec<(usize, u64)>,
}
struct Net {
reusable: Vec<Arcs>,
once: Vec<(OccId, Arcs)>,
initial: Vec<u64>,
target: Vec<u64>,
}
fn counted(forest: &Forest, o: OccId, sign: Sign) -> Vec<(usize, u64)> {
let mut atoms: Vec<usize> = forest
.subtree(o)
.filter(|&x| forest.sign(x) == Some(sign))
.map(|x| forest.atom(x).expect("a literal has an atom").index())
.collect();
atoms.sort_unstable();
let mut counts: Vec<(usize, u64)> = Vec::new();
for a in atoms {
match counts.last_mut() {
Some((last, n)) if *last == a => *n += 1,
_ => counts.push((a, 1)),
}
}
counts
}
fn read(forest: &Forest, goal: &[OccId], body: Sign) -> Option<Net> {
let atoms = forest.sequent().atom_names().len();
let head = |o: OccId| {
forest.subtree(o).all(|x| match forest.kind(x) {
Kind::Par | Kind::Bot => true,
_ => forest.sign(x) == Some(!body),
})
};
let clause = |c: OccId| -> Option<(Arcs, bool)> {
let (mut inputs, mut found) = (Vec::new(), None);
let mut factors = vec![c];
while let Some(x) = factors.pop() {
match forest.kind(x) {
Kind::Tensor => factors.extend(forest.left(x).into_iter().chain(forest.right(x))),
Kind::One => {}
_ if forest.sign(x) == Some(body) => {
inputs.push(forest.atom(x).expect("a literal has an atom").index());
}
_ if found.is_none() && head(x) => found = Some(x),
_ => return None,
}
}
inputs.sort_unstable();
let mut counts: Vec<(usize, u64)> = Vec::new();
for a in inputs {
match counts.last_mut() {
Some((last, n)) if *last == a => *n += 1,
_ => counts.push((a, 1)),
}
}
let outputs = found.map_or_else(Vec::new, |h| counted(forest, h, !body));
Some((
Arcs {
inputs: counts,
outputs,
},
found.is_some(),
))
};
let mut net = Net {
reusable: Vec::new(),
once: Vec::new(),
initial: vec![0; atoms],
target: vec![0; atoms],
};
let mut goal_found = false;
for &member in goal {
if forest.kind(member) == Kind::Quest {
let (arcs, headed) = clause(forest.left(member)?)?;
if !headed {
return None;
}
net.reusable.push(arcs);
} else if head(member) {
for (a, n) in counted(forest, member, !body) {
net.initial[a] += n;
}
} else {
let (arcs, headed) = clause(member)?;
if headed {
net.once.push((member, arcs));
} else if goal_found {
return None;
} else {
goal_found = true;
for &(a, n) in &arcs.inputs {
net.target[a] = n;
}
}
}
}
goal_found.then_some(net)
}
fn entries(marking: &Marking, atoms: usize) -> impl Iterator<Item = (usize, u32)> + '_ {
marking.atoms.iter().map(|&(a, n)| (a.index(), n)).chain(
marking
.tickets
.iter()
.map(move |&(k, n)| (atoms + k as usize, n)),
)
}
fn at_most(marking: &Marking, atoms: usize, counts: &[u64]) -> bool {
entries(marking, atoms).all(|(p, n)| u64::from(n) <= counts[p])
}
fn live(initial: &[u64], transitions: &[Arcs]) -> Vec<bool> {
let mut marked: Vec<bool> = initial.iter().map(|&n| n > 0).collect();
let mut waiting: Vec<usize> = Vec::with_capacity(transitions.len());
let mut by_input: Vec<Vec<usize>> = vec![Vec::new(); initial.len()];
let mut ready = Vec::new();
for (t, arcs) in transitions.iter().enumerate() {
let mut unmarked = 0;
for &(p, _) in &arcs.inputs {
if !marked[p] {
unmarked += 1;
by_input[p].push(t);
}
}
waiting.push(unmarked);
if unmarked == 0 {
ready.push(t);
}
}
while let Some(t) = ready.pop() {
for &(p, _) in &transitions[t].outputs {
if !marked[p] {
marked[p] = true;
for &u in &by_input[p] {
waiting[u] -= 1;
if waiting[u] == 0 {
ready.push(u);
}
}
}
}
}
marked
}
pub(crate) fn check(
forest: &Forest,
goal: &[OccId],
basis: &Basis,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<(), Failed> {
if forest.has_binders() {
return Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "it is of propositional Horn programs, and the sequent has a quantifier",
}
.into());
}
let net = read(forest, goal, basis.body).ok_or(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "the goal is no Horn program with bodies of the sign stated",
})?;
let atoms = net.initial.len();
let places = atoms
.checked_add(basis.classes.len())
.ok_or(RefutationFault::Mismatch)?;
let mut transitions = net.reusable;
let mut index: HashMap<OccId, Vec<usize>> = HashMap::default();
for (i, &(o, _)) in net.once.iter().enumerate() {
index.entry(o).or_default().push(i);
}
for (k, class) in basis.classes.iter().enumerate() {
let mut arcs: Option<&Arcs> = None;
for o in class {
let i = index
.get_mut(o)
.and_then(Vec::pop)
.ok_or(RefutationFault::Mismatch)?;
if arcs.is_some_and(|arcs| *arcs != net.once[i].1) {
return Err(RefutationFault::Mismatch.into());
}
arcs = Some(&net.once[i].1);
}
let mut arcs = arcs.ok_or(RefutationFault::Mismatch)?.clone();
arcs.inputs.push((atoms + k, 1));
transitions.push(arcs);
}
if index.values().any(|left| !left.is_empty()) {
return Err(RefutationFault::Mismatch.into());
}
let mut initial = net.initial;
initial.extend(basis.classes.iter().map(|class| class.len() as u64));
let mut target = net.target;
target.resize(places, 0);
for marking in &basis.markings {
let atoms_in_order = marking.atoms.windows(2).all(|w| w[0].0 < w[1].0);
let tickets_in_order = marking.tickets.windows(2).all(|w| w[0].0 < w[1].0);
let counted = marking.atoms.iter().all(|&(_, n)| n > 0)
&& marking.tickets.iter().all(|&(_, n)| n > 0);
let in_range = marking.atoms.last().is_none_or(|&(a, _)| a.index() < atoms)
&& marking
.tickets
.last()
.is_none_or(|&(k, _)| (k as usize) < basis.classes.len());
if !(atoms_in_order && tickets_in_order && counted && in_range) {
return Err(RefutationFault::Mismatch.into());
}
}
let markings = &basis.markings;
if !markings.iter().any(|m| at_most(m, atoms, &target)) {
return Err(RefutationFault::Missed.into());
}
if markings.iter().any(|m| at_most(m, atoms, &initial)) {
return Err(RefutationFault::Reached.into());
}
let marked = live(&initial, &transitions);
let mut by_output: Vec<Vec<usize>> = vec![Vec::new(); places];
for (t, arcs) in transitions.iter().enumerate() {
if arcs.inputs.iter().all(|&(p, _)| marked[p]) {
for &(p, _) in &arcs.outputs {
by_output[p].push(t);
}
}
}
let sum = |counts: &mut dyn Iterator<Item = u64>| counts.fold(0u64, u64::saturating_add);
let sums: Vec<u64> = markings
.iter()
.map(|m| sum(&mut entries(m, atoms).map(|(_, n)| u64::from(n))))
.collect();
let mut probe = vec![0u64; places];
let mut touched: Vec<usize> = Vec::new();
let mut tried = vec![0usize; transitions.len()];
for (i, m) in markings.iter().enumerate() {
for (p, _) in entries(m, atoms) {
for &t in &by_output[p] {
if tried[t] == i + 1 {
continue;
}
tried[t] = i + 1;
let arcs = &transitions[t];
for (q, n) in entries(m, atoms) {
probe[q] = u64::from(n);
touched.push(q);
}
for &(q, w) in &arcs.outputs {
probe[q] = probe[q].saturating_sub(w);
}
for &(q, w) in &arcs.inputs {
probe[q] += w;
touched.push(q);
}
let needed = sum(&mut touched.iter().map(|&q| probe[q]));
let mut units: u64 = 1;
let found = markings.iter().zip(&sums).any(|(other, &s)| {
units = units.saturating_add(1);
if s > needed {
return false;
}
let counts = other.atoms.len() + other.tickets.len();
units = units.saturating_add(counts as u64);
at_most(other, atoms, &probe)
});
for &q in &touched {
probe[q] = 0;
}
touched.clear();
if !found {
return Err(RefutationFault::Open.into());
}
if stop(units) {
return Err(Failed::Stopped);
}
}
}
}
Ok(())
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::search::{Engine, Options, Refutation, Verdict, prove};
use crate::linear::{Mode, Sequent};
fn basis_of(text: &str) -> (Forest, Basis) {
let sequent: Sequent = text.parse().unwrap();
let options = Options::default().with_engine(Some(Engine::Horn));
let outcome = prove(&sequent, Mode::CLASSICAL.with_affine(), &options).unwrap();
let Verdict::Unprovable(disproof) = outcome.verdict else {
panic!("{text} is unprovable");
};
let Refutation::Basis(basis) = disproof.refutation().clone() else {
panic!("{text}: {:?}", disproof.refutation());
};
(Forest::new(&sequent).unwrap(), basis)
}
fn checked(forest: &Forest, basis: &Basis) -> Result<(), Failed> {
check(forest, forest.roots(), basis, &mut |_| false)
}
const SHORT: &str = "a, a -o b, !(a * b -o a * b * c) |- c";
#[test]
fn the_engine_s_basis_is_checked() {
let (forest, basis) = basis_of(SHORT);
assert!(checked(&forest, &basis).is_ok());
assert_eq!(basis.classes.len(), 1);
}
fn fault(forest: &Forest, basis: &Basis) -> RefutationFault {
match checked(forest, basis) {
Err(Failed::Fault(fault)) => fault,
other => panic!("{other:?}"),
}
}
#[test]
fn a_planted_wrong_basis_is_refused() {
let (forest, basis) = basis_of(SHORT);
let atom = |name: &str| forest.sequent().atom(name).unwrap();
let mut missed = basis.clone();
missed
.markings
.retain(|m| m.atoms != vec![(atom("c"), 1)] || !m.tickets.is_empty());
assert_eq!(fault(&forest, &missed), RefutationFault::Missed);
let mut reached = basis.clone();
reached
.markings
.push(Marking::new(vec![(atom("a"), 1)], Vec::new()));
assert_eq!(fault(&forest, &reached), RefutationFault::Reached);
let mut open = basis.clone();
open.markings
.retain(|m| m.atoms == vec![(atom("c"), 1)] && m.tickets.is_empty());
assert_eq!(open.markings.len(), 1);
assert_eq!(fault(&forest, &open), RefutationFault::Open);
let mut zero = basis.clone();
zero.markings[0].atoms.push((atom("c"), 0));
assert_eq!(fault(&forest, &zero), RefutationFault::Mismatch);
let mut past = basis.clone();
past.markings[0]
.atoms
.push((crate::linear::sequents::Atom::new(99), 1));
assert_eq!(fault(&forest, &past), RefutationFault::Mismatch);
let mut reversed = basis.clone();
reversed.markings[0].atoms = vec![(atom("c"), 1), (atom("a"), 1)];
assert_eq!(fault(&forest, &reversed), RefutationFault::Mismatch);
let mut class = basis.clone();
class.markings[0].tickets = vec![(1, 1)];
assert_eq!(fault(&forest, &class), RefutationFault::Mismatch);
let mut far = basis.clone();
far.markings[0].tickets = vec![(u32::MAX, 1)];
assert_eq!(fault(&forest, &far), RefutationFault::Mismatch);
let mut other = basis;
other.body = !other.body;
assert!(matches!(
fault(&forest, &other),
RefutationFault::NotApplicable { .. }
));
}
#[test]
fn classes_must_be_the_clauses_used_once() {
let (forest, basis) = basis_of("a, a -o b, a -o b, !(a * b -o a * b * c) |- c");
assert!(checked(&forest, &basis).is_ok());
assert_eq!(basis.classes.len(), 1);
assert_eq!(basis.classes[0].len(), 2);
let mut missing = basis.clone();
missing.classes[0].pop();
assert_eq!(fault(&forest, &missing), RefutationFault::Mismatch);
let mut twice = basis.clone();
let first = twice.classes[0][0];
twice.classes[0].push(first);
assert_eq!(fault(&forest, &twice), RefutationFault::Mismatch);
let mut stranger = basis.clone();
stranger.classes[0][0] = forest.roots()[0];
assert_eq!(fault(&forest, &stranger), RefutationFault::Mismatch);
let (forest, basis) = basis_of("a, a -o b, a * a -o b, !(a * b -o a * b * c) |- c");
assert_eq!(basis.classes.len(), 2);
let mut merged = basis;
merged.classes = vec![merged.classes.concat()];
merged.markings.clear();
assert_eq!(fault(&forest, &merged), RefutationFault::Mismatch);
}
#[test]
fn a_member_named_twice_is_two_clauses() {
let sequent: Sequent = SHORT.parse().unwrap();
let forest = Forest::new(&sequent).unwrap();
let roots = forest.roots();
let members = [0, 1, 1, 2, 3].map(|i| crate::linear::Member::from(roots[i]));
let goal = crate::linear::search::Goal::new(&forest, &members).unwrap();
let options = Options::default().with_engine(Some(Engine::Horn));
let outcome = crate::linear::search::prove_goal(
goal,
Mode::CLASSICAL.with_affine(),
&options,
&crate::Limits::default(),
|_| false,
)
.unwrap();
let Verdict::Unprovable(disproof) = outcome.verdict else {
panic!("{:?}", outcome.verdict);
};
let Refutation::Basis(basis) = disproof.refutation() else {
panic!("{:?}", disproof.refutation());
};
assert_eq!(basis.classes, vec![vec![roots[1], roots[1]]]);
assert_eq!(disproof.check(), Ok(()));
}
#[test]
fn the_check_asks_the_stop() {
let (forest, basis) = basis_of(SHORT);
let mut asked = 0;
let result = check(&forest, forest.roots(), &basis, &mut |_| {
asked += 1;
true
});
assert!(matches!(result, Err(Failed::Stopped)));
assert_eq!(asked, 1);
}
}