use super::refutation::RefutationFault;
use crate::linear::occurrences::{Forest, OccId, Sign};
use crate::linear::sequents::Kind;
const INVARIANT: &str = "weighted count";
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Low {
Never,
From(i128),
Unbounded,
}
impl Low {
fn sum(self, other: Self) -> Option<Self> {
Some(match (self, other) {
(Low::Never, _) | (_, Low::Never) => Low::Never,
(Low::From(a), Low::From(b)) => Low::From(a.checked_add(b)?),
_ => Low::Unbounded,
})
}
fn min(self, other: Self) -> Self {
match (self, other) {
(Low::Never, z) | (z, Low::Never) => z,
(Low::From(a), Low::From(b)) => Low::From(a.min(b)),
_ => Low::Unbounded,
}
}
const fn star(self) -> Self {
match self {
Low::Never => Low::From(0),
Low::From(z) if z >= 0 => Low::From(0),
Low::From(_) | Low::Unbounded => Low::Unbounded,
}
}
const fn positive(self) -> bool {
match self {
Low::Never => true,
Low::From(z) => z > 0,
Low::Unbounded => false,
}
}
const fn reaches(self, absorbs: bool) -> bool {
absorbs || !matches!(self, Low::Never)
}
}
pub(crate) struct Weights<'a> {
pub(crate) weight: &'a dyn Fn(OccId) -> i128,
pub(crate) dead: &'a dyn Fn(OccId) -> bool,
pub(crate) sign: Sign,
pub(crate) weakening: bool,
}
#[derive(Clone, Copy)]
struct Node {
least: Low,
absorbs: bool,
outputs: i64,
shaped: bool,
}
pub(crate) fn overweight(
forest: &Forest,
goal: &[OccId],
weights: &Weights<'_>,
) -> Result<(), RefutationFault> {
let overflow = RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "a sum leaves 128 bits",
};
let positive = weights.sign == Sign::Atom;
let mut nodes: Vec<Option<Node>> = vec![None; forest.len()];
let (mut total, mut outputs, mut shaped, mut absorbs) = (Low::From(0), 0i64, true, false);
for &member in goal {
for o in forest.subtree(member).rev() {
let side = |side: Option<OccId>| side.and_then(|s| nodes[s.index()]);
let (l, r) = (side(forest.left(o)), side(forest.right(o)));
let both = || l.zip(r).expect("a binary connective has two operands");
let one = || l.expect("a unary connective has an operand");
let kind = forest.kind(o);
let outputs = match kind {
Kind::Atom => i64::from(positive),
Kind::DualAtom => i64::from(!positive),
Kind::One | Kind::Top | Kind::Bang => 1,
Kind::Bot | Kind::Zero | Kind::Quest => 0,
Kind::Tensor => both().0.outputs + both().1.outputs - 1,
Kind::Par => both().0.outputs + both().1.outputs,
Kind::With | Kind::Plus => both().0.outputs.max(both().1.outputs),
Kind::Forall | Kind::Exists => one().outputs,
};
let shaped = outputs >= 0
&& match kind {
Kind::Tensor | Kind::Par | Kind::With | Kind::Plus => {
both().0.shaped && both().1.shaped
}
Kind::Bang | Kind::Forall | Kind::Exists => one().shaped,
Kind::Quest => one().outputs == 0 && one().shaped,
Kind::Atom
| Kind::DualAtom
| Kind::One
| Kind::Bot
| Kind::Top
| Kind::Zero => true,
};
let literal = |negated: bool| {
if (weights.dead)(o) {
Low::Never
} else {
let w = (weights.weight)(o);
Low::From(if negated { -w } else { w })
}
};
let least = match kind {
Kind::Atom => literal(false),
Kind::DualAtom => literal(true),
Kind::One | Kind::Bot | Kind::Bang => Low::From(0),
Kind::Top | Kind::Zero => Low::Never,
Kind::Tensor | Kind::Par => both().0.least.sum(both().1.least).ok_or(overflow)?,
Kind::With | Kind::Plus => both().0.least.min(both().1.least),
Kind::Quest => one().least.star(),
Kind::Forall | Kind::Exists => one().least,
};
let least = if weights.weakening && outputs == 0 {
Low::From(0).min(least)
} else {
least
};
let absorbs = match kind {
Kind::Atom => (weights.dead)(o) && !positive,
Kind::DualAtom => (weights.dead)(o) && positive,
Kind::Top => true,
Kind::Tensor => {
let (a, b) = both();
a.absorbs && b.least.reaches(b.absorbs)
|| b.absorbs && a.least.reaches(a.absorbs)
}
Kind::Par | Kind::With | Kind::Plus => both().0.absorbs || both().1.absorbs,
Kind::Quest | Kind::Forall | Kind::Exists => one().absorbs,
Kind::One | Kind::Bot | Kind::Zero | Kind::Bang => false,
};
nodes[o.index()] = Some(Node {
least,
absorbs,
outputs,
shaped,
});
}
let node = nodes[member.index()].expect("the member was just visited");
total = total.sum(node.least).ok_or(overflow)?;
outputs = outputs.saturating_add(node.outputs);
shaped &= node.shaped;
absorbs |= node.absorbs;
}
if weights.weakening && !(shaped && outputs == 1) {
return Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "with weakening it counts goals of shaped formulas with one output, which this one is not",
});
}
if absorbs {
return Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "a formula may absorb any count: a ⊤, or a dead atom's literal of the other sign",
});
}
if total.positive() {
Ok(())
} else {
Err(RefutationFault::Holds)
}
}
pub(crate) fn dead_atoms(forest: &Forest, goal: &[OccId], body: Sign) -> Option<Vec<bool>> {
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 atom = |o: OccId| forest.atom(o).expect("a literal").index();
let literals = |o: OccId| forest.subtree(o).filter(|&x| forest.sign(x).is_some());
let mut named = vec![false; atoms];
let mut live = vec![false; atoms];
let mut missing: Vec<usize> = Vec::new();
let mut heads: Vec<Option<OccId>> = Vec::new();
let mut waiting: Vec<Vec<usize>> = vec![Vec::new(); atoms];
for &member in goal {
for x in literals(member) {
named[atom(x)] = true;
}
let clause = match forest.kind(member) {
Kind::Quest => forest.left(member).expect("a `?` has an operand"),
_ if head(member) => {
for x in literals(member) {
live[atom(x)] = true;
}
continue;
}
_ => member,
};
let c = heads.len();
let (mut inputs, mut found) = (Vec::new(), None);
let mut factors = vec![clause];
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(atom(x)),
_ if found.is_none() && head(x) => found = Some(x),
_ => return None,
}
}
for &a in &inputs {
waiting[a].push(c);
}
missing.push(inputs.len());
heads.push(found);
}
let mut ready: Vec<usize> = Vec::new();
for a in 0..atoms {
if live[a] {
for &c in &waiting[a] {
missing[c] -= 1;
}
}
}
ready.extend((0..heads.len()).filter(|&c| missing[c] == 0));
while let Some(c) = ready.pop() {
let Some(h) = heads[c] else { continue };
for x in literals(h) {
let a = atom(x);
if !live[a] {
live[a] = true;
for &d in &waiting[a] {
missing[d] -= 1;
if missing[d] == 0 {
ready.push(d);
}
}
}
}
}
Some((0..atoms).map(|a| named[a] && !live[a]).collect())
}
pub(crate) struct Deaths {
#[cfg_attr(
not(feature = "rocq"),
expect(dead_code, reason = "the Rocq certificate writes the reading")
)]
pub(crate) body: Sign,
#[cfg_attr(
not(feature = "rocq"),
expect(dead_code, reason = "the Rocq certificate writes the reading")
)]
pub(crate) dead: Vec<bool>,
}
pub(crate) fn state_equation(
forest: &Forest,
goal: &[OccId],
mode: crate::linear::Mode,
equation: &super::StateEquation,
) -> Result<Deaths, RefutationFault> {
const INVARIANT: &str = "state equation";
if forest.has_binders() {
return Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "it is of propositional Horn programs, and the sequent has a quantifier",
});
}
let atoms = forest.sequent().atom_names().len();
let ordered = equation
.atoms
.windows(2)
.all(|pair| pair[0].0.index() < pair[1].0.index());
let occurrences = equation
.clauses
.iter()
.map(|&(o, _)| o)
.chain(equation.dropped.iter().copied());
if !ordered
|| equation.atoms.iter().any(|&(a, _)| a.index() >= atoms)
|| occurrences.into_iter().any(|o| o.index() >= forest.len())
{
return Err(RefutationFault::Mismatch);
}
let mut weight = vec![0i128; atoms];
for &(a, w) in &equation.atoms {
weight[a.index()] = i128::from(w);
}
let atom = |o: OccId| forest.atom(o).expect("a literal").index();
let mut fault = None;
for body in [Sign::Atom, Sign::Dual] {
let Some(dead) = dead_atoms(forest, goal, body) else {
continue;
};
let negated = body == Sign::Dual;
let weights = Weights {
weight: &|o| {
let w = weight[atom(o)];
if negated { -w } else { w }
},
dead: &|o| dead[atom(o)],
sign: body,
weakening: mode.affine,
};
match overweight(forest, goal, &weights) {
Ok(()) => return Ok(Deaths { body, dead }),
Err(found) => {
fault.get_or_insert(found);
}
}
}
Err(fault.unwrap_or(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "the goal is no Horn program",
}))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_sum_past_128_bits_is_refused() {
let top = Low::From(i128::MAX);
assert_eq!(top.sum(Low::From(1)), None);
assert_eq!(Low::From(i128::MIN).sum(Low::From(-1)), None);
assert_eq!(top.sum(Low::From(-1)), Some(Low::From(i128::MAX - 1)));
assert_eq!(top.sum(Low::Never), Some(Low::Never));
}
#[cfg(feature = "parse")]
#[test]
fn the_test_refuses_a_sum_past_128_bits() {
let weights = Weights {
weight: &|_| i128::MAX,
dead: &|_| false,
sign: Sign::Atom,
weakening: false,
};
for input in ["|- a * a", "|- a, a"] {
let sequent: crate::linear::Sequent = input.parse().unwrap();
let forest = Forest::new(&sequent).unwrap();
assert_eq!(
overweight(&forest, forest.roots(), &weights),
Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "a sum leaves 128 bits",
}),
"{input}"
);
}
}
}