use super::solver::Lit;
use crate::hash::HashMap;
use crate::limits::{Limits, Phase, Progress, Refusal};
use crate::linear::search::memory::Account;
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum Step {
Add(Box<[Lit]>),
Delete(Box<[Lit]>),
}
impl Step {
pub(crate) const fn bytes(len: usize) -> usize {
size_of::<Self>() + len * size_of::<Lit>()
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Flaw {
Variable {
step: Option<usize>,
},
NotRup {
step: usize,
},
NoEmptyClause,
}
impl std::fmt::Display for Flaw {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Variable { step: None } => {
write!(f, "a clause of the formula names no variable of it")
}
Self::Variable { step: Some(step) } => {
write!(f, "step {step} names no variable of the formula")
}
Self::NotRup { step } => write!(
f,
"the clause of step {step} does not follow by unit propagation"
),
Self::NoEmptyClause => write!(f, "the proof never adds the empty clause"),
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum Rejection {
Flaw(Flaw),
Refused(Refusal),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize))]
pub struct ClausalProof {
variables: u32,
clauses: u64,
steps: u64,
}
impl ClausalProof {
pub(super) fn checked(
variables: u32,
formula: &[Vec<Lit>],
proof: &[Step],
limits: &Limits,
account: &Account,
stop: impl FnMut(Progress) -> bool,
) -> Result<Self, Rejection> {
check(variables, formula, proof, limits, account, stop)?;
Ok(Self {
variables,
clauses: formula.len() as u64,
steps: proof.len() as u64,
})
}
pub const fn variables(&self) -> u32 {
self.variables
}
pub const fn clauses(&self) -> u64 {
self.clauses
}
pub const fn steps(&self) -> u64 {
self.steps
}
}
impl std::fmt::Display for ClausalProof {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let plural = |n: u64| if n == 1 { "" } else { "s" };
write!(
f,
"a checked clausal proof of {} step{} against the {} clause{} of the sequent's \
negation",
self.steps,
plural(self.steps),
self.clauses,
plural(self.clauses)
)
}
}
const POLL: u64 = 1 << 12;
const CLAUSE_BYTES: usize = 224;
struct Clause {
literals: Box<[u32]>,
live: bool,
}
const fn code(literal: Lit) -> u32 {
literal.var() * 2 + !literal.is_positive() as u32
}
struct Checker<'a> {
clauses: Vec<Clause>,
index: HashMap<Box<[u32]>, Vec<usize>>,
watches: Vec<Vec<usize>>,
units: Vec<usize>,
empty: usize,
holds: Vec<bool>,
trail: Vec<u32>,
variables: u32,
account: &'a Account,
ticks: u64,
steps: u64,
}
pub(crate) fn check(
variables: u32,
formula: &[Vec<Lit>],
proof: &[Step],
limits: &Limits,
account: &Account,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<(), Rejection> {
let codes = 2 * variables as usize;
account.charge(codes.saturating_mul(size_of::<Vec<usize>>() + size_of::<bool>()));
if account.over() {
return Err(over(account));
}
let mut checker = Checker {
clauses: Vec::new(),
index: HashMap::default(),
watches: vec![Vec::new(); codes],
units: Vec::new(),
empty: 0,
holds: vec![false; codes],
trail: Vec::new(),
variables,
account,
ticks: 0,
steps: 0,
};
for clause in formula {
checker.tick(1, &mut stop)?;
let literals = checker
.normal(clause)
.ok_or(Rejection::Flaw(Flaw::Variable { step: None }))?;
checker.keep(literals)?;
}
for (n, step) in proof.iter().enumerate() {
checker.steps += 1;
if limits.work.is_some_and(|work| checker.steps > work) {
return Err(Rejection::Refused(Refusal::Work {
limit: limits.work.unwrap_or(u64::MAX),
}));
}
checker.tick(1, &mut stop)?;
let (Step::Add(clause) | Step::Delete(clause)) = step;
let literals = checker
.normal(clause)
.ok_or(Rejection::Flaw(Flaw::Variable { step: Some(n) }))?;
match step {
Step::Add(_) => {
if !checker.conflicts(clause, &mut stop)? {
return Err(Rejection::Flaw(Flaw::NotRup { step: n }));
}
if clause.is_empty() {
return Ok(());
}
checker.keep(literals)?;
}
Step::Delete(_) => checker.delete(literals),
}
}
Err(Rejection::Flaw(Flaw::NoEmptyClause))
}
impl Checker<'_> {
#[expect(
clippy::option_option,
reason = "a clause of a missing variable, a tautology and a clause are three answers"
)]
fn normal(&self, clause: &[Lit]) -> Option<Option<Box<[u32]>>> {
if clause.iter().any(|l| l.var() >= self.variables) {
return None;
}
let mut literals: Vec<u32> = clause.iter().map(|&l| code(l)).collect();
literals.sort_unstable();
literals.dedup();
let tautology = literals.windows(2).any(|w| w[0] ^ 1 == w[1]);
Some((!tautology).then(|| literals.into_boxed_slice()))
}
fn keep(&mut self, literals: Option<Box<[u32]>>) -> Result<(), Rejection> {
let Some(literals) = literals else {
return Ok(());
};
let id = self.clauses.len();
self.account
.charge(2 * literals.len() * size_of::<u32>() + CLAUSE_BYTES);
match literals.len() {
0 => self.empty += 1,
1 => self.units.push(id),
_ => {
self.watches[literals[0] as usize].push(id);
self.watches[literals[1] as usize].push(id);
}
}
self.index.entry(literals.clone()).or_default().push(id);
self.clauses.push(Clause {
literals,
live: true,
});
if self.account.over() {
return Err(over(self.account));
}
Ok(())
}
fn delete(&mut self, literals: Option<Box<[u32]>>) {
let Some(literals) = literals else {
return;
};
let Some(ids) = self.index.get_mut(&literals) else {
return;
};
let Some(id) = ids.pop() else {
return;
};
if ids.is_empty() {
self.index.remove(&literals);
}
self.clauses[id].live = false;
if literals.is_empty() {
self.empty -= 1;
}
}
fn tick(&mut self, n: u64, stop: &mut impl FnMut(Progress) -> bool) -> Result<(), Rejection> {
self.ticks += n;
if self.ticks >= POLL {
let ticks = std::mem::take(&mut self.ticks);
if stop(Progress::new(Phase::Check, ticks, self.steps)) {
return Err(Rejection::Refused(Refusal::Stopped {
phase: Phase::Check,
}));
}
}
Ok(())
}
fn assign(&mut self, literal: u32) -> bool {
if self.holds[(literal ^ 1) as usize] {
return false;
}
if !self.holds[literal as usize] {
self.holds[literal as usize] = true;
self.trail.push(literal);
}
true
}
fn conflicts(
&mut self,
clause: &[Lit],
stop: &mut impl FnMut(Progress) -> bool,
) -> Result<bool, Rejection> {
let found = self.propagate(clause, stop);
for &literal in &self.trail {
self.holds[literal as usize] = false;
}
self.trail.clear();
found
}
fn propagate(
&mut self,
clause: &[Lit],
stop: &mut impl FnMut(Progress) -> bool,
) -> Result<bool, Rejection> {
if self.empty > 0 {
return Ok(true);
}
for &literal in clause {
if !self.assign(code(literal) ^ 1) {
return Ok(true);
}
}
let mut units = std::mem::take(&mut self.units);
units.retain(|&id| self.clauses[id].live);
let mut conflict = Ok(false);
for &id in &units {
if let Err(refused) = self.tick(1, stop) {
conflict = Err(refused);
break;
}
if !self.assign(self.clauses[id].literals[0]) {
conflict = Ok(true);
break;
}
}
self.units = units;
if conflict != Ok(false) {
return conflict;
}
let mut head = 0;
while let Some(&holds) = self.trail.get(head) {
head += 1;
self.tick(1, stop)?;
let falsified = holds ^ 1;
let mut watching = std::mem::take(&mut self.watches[falsified as usize]);
let mut kept = 0;
let mut at = 0;
let mut conflict = false;
while at < watching.len() {
let id = watching[at];
at += 1;
if let Err(refused) = self.tick(1, stop) {
watching.drain(kept..at - 1);
self.watches[falsified as usize] = watching;
return Err(refused);
}
let clause = &mut self.clauses[id];
if !clause.live {
continue;
}
if clause.literals[0] == falsified {
clause.literals.swap(0, 1);
}
let first = clause.literals[0];
if self.holds[first as usize] {
watching[kept] = id;
kept += 1;
continue;
}
let other = clause.literals[2..]
.iter()
.position(|&l| !self.holds[(l ^ 1) as usize]);
if let Some(k) = other {
clause.literals.swap(1, k + 2);
let watched = clause.literals[1];
self.watches[watched as usize].push(id);
continue;
}
watching[kept] = id;
kept += 1;
if !self.assign(first) {
conflict = true;
break;
}
}
watching.drain(kept..at);
self.watches[falsified as usize] = watching;
if conflict {
return Ok(true);
}
}
Ok(false)
}
}
fn over(account: &Account) -> Rejection {
Rejection::Refused(Refusal::Memory {
phase: Phase::Check,
limit_bytes: account.limit(),
needed_bytes: None,
})
}
#[cfg(all(test, feature = "parse"))]
pub(crate) fn dimacs(variables: u32, formula: &[Vec<Lit>], proof: &[Step]) -> (String, String) {
use std::fmt::Write;
let number = |l: Lit| {
let n = i64::from(l.var()) + 1;
if l.is_positive() { n } else { -n }
};
let mut cnf = format!("p cnf {variables} {}\n", formula.len());
for clause in formula {
for &l in clause {
write!(cnf, "{} ", number(l)).unwrap();
}
cnf.push_str("0\n");
}
let mut drup = String::new();
for step in proof {
let (Step::Add(clause) | Step::Delete(clause)) = step;
if matches!(step, Step::Delete(_)) {
drup.push_str("d ");
}
for &l in clause.iter() {
write!(drup, "{} ", number(l)).unwrap();
}
drup.push_str("0\n");
}
(cnf, drup)
}
#[cfg(test)]
mod tests {
use super::{Flaw, Rejection, Step, check};
use crate::limits::{Limits, Refusal};
use crate::linear::search::memory::Account;
use crate::ordinary::sat::solver::Lit;
fn lit(n: i32) -> Lit {
let var = n.unsigned_abs() - 1;
if n > 0 {
Lit::positive(var)
} else {
Lit::negative(var)
}
}
fn clauses(numbers: &[&[i32]]) -> Vec<Vec<Lit>> {
numbers
.iter()
.map(|c| c.iter().map(|&n| lit(n)).collect())
.collect()
}
fn add(numbers: &[i32]) -> Step {
Step::Add(numbers.iter().map(|&n| lit(n)).collect())
}
fn delete(numbers: &[i32]) -> Step {
Step::Delete(numbers.iter().map(|&n| lit(n)).collect())
}
fn run(variables: u32, formula: &[&[i32]], proof: &[Step]) -> Result<(), Rejection> {
let limits = Limits::default();
let account = Account::holding(limits.memory_bytes, 0);
check(
variables,
&clauses(formula),
proof,
&limits,
&account,
|_| false,
)
}
const SQUARE: &[&[i32]] = &[&[1, 2], &[1, -2], &[-1, 2], &[-1, -2]];
#[test]
fn a_planted_wrong_step_is_refused() {
assert_eq!(run(2, SQUARE, &[add(&[1]), add(&[])]), Ok(()));
let ignored = [delete(&[1, 2, -2]), delete(&[2]), add(&[1]), add(&[])];
assert_eq!(run(2, SQUARE, &ignored), Ok(()));
let wrong = [add(&[2]), add(&[1]), add(&[])];
let partial: &[&[i32]] = &[&[1, 2], &[1, -2], &[-1, -2]];
assert_eq!(
run(2, partial, &wrong),
Err(Rejection::Flaw(Flaw::NotRup { step: 0 }))
);
assert_eq!(
run(2, SQUARE, &[add(&[1])]),
Err(Rejection::Flaw(Flaw::NoEmptyClause))
);
let deleted = [add(&[1]), delete(&[-1, 2]), add(&[])];
assert_eq!(
run(2, SQUARE, &deleted),
Err(Rejection::Flaw(Flaw::NotRup { step: 2 }))
);
assert_eq!(
run(2, SQUARE, &[add(&[3]), add(&[])]),
Err(Rejection::Flaw(Flaw::Variable { step: Some(0) }))
);
assert_eq!(
run(1, SQUARE, &[add(&[])]),
Err(Rejection::Flaw(Flaw::Variable { step: None }))
);
}
#[test]
fn the_bounds_refuse_a_check() {
let proof = [add(&[1]), add(&[])];
let limits = Limits::default().with_work(Some(1));
let account = Account::holding(limits.memory_bytes, 0);
let formula = clauses(SQUARE);
assert_eq!(
check(2, &formula, &proof, &limits, &account, |_| false),
Err(Rejection::Refused(Refusal::Work { limit: 1 }))
);
let limits = Limits::default().with_memory_bytes(Some(64));
let account = Account::holding(limits.memory_bytes, 0);
assert!(matches!(
check(2, &formula, &proof, &limits, &account, |_| false),
Err(Rejection::Refused(Refusal::Memory { .. }))
));
let n = 3 * super::POLL as i32;
let mut chain: Vec<Vec<i32>> = (1..n).map(|i| vec![-i, i + 1]).collect();
chain.push(vec![1]);
chain.push(vec![-n]);
let chain: Vec<&[i32]> = chain.iter().map(Vec::as_slice).collect();
let limits = Limits::default();
let account = Account::holding(limits.memory_bytes, 0);
let mut asked = 0;
let result = check(
n as u32,
&clauses(&chain),
&[add(&[])],
&limits,
&account,
|_| {
asked += 1;
asked > 1
},
);
assert_eq!(
result,
Err(Rejection::Refused(Refusal::Stopped {
phase: crate::limits::Phase::Check
}))
);
assert_eq!(run(n as u32, &chain, &[add(&[])]), Ok(()));
let n = super::POLL as i32;
let mut units: Vec<Vec<i32>> = (2..=n).map(|i| vec![i]).collect();
units.push(vec![1]);
let units: Vec<&[i32]> = units.iter().map(Vec::as_slice).collect();
let steps = 8;
let proof: Vec<Step> = (0..steps).map(|_| add(&[1, n + 1])).collect();
let mut asked = 0;
let result = check(
n as u32 + 1,
&clauses(&units),
&proof,
&limits,
&account,
|_| {
asked += 1;
false
},
);
assert_eq!(result, Err(Rejection::Flaw(Flaw::NoEmptyClause)));
assert!(asked >= steps, "{asked} polls for {steps} checks");
}
}