use std::{
io::{BufWriter, Write},
mem::replace,
};
use anyhow::Error;
use varisat_checker::{CheckedProofStep, CheckerData, ProofProcessor};
use varisat_formula::Lit;
pub struct WriteLrat<'a> {
binary: bool,
target: BufWriter<Box<dyn Write + 'a>>,
delete_open: bool,
last_added_id: u64,
buffered_deletes: Vec<u64>,
}
impl<'a> ProofProcessor for WriteLrat<'a> {
fn process_step(&mut self, step: &CheckedProofStep, _data: CheckerData) -> Result<(), Error> {
match step {
CheckedProofStep::AddClause { .. } => (),
CheckedProofStep::DuplicatedClause { .. } => (),
_ => {
if !self.buffered_deletes.is_empty() {
let buffered_deletes = replace(&mut self.buffered_deletes, vec![]);
self.open_delete()?;
self.write_ids(&buffered_deletes)?;
}
}
}
match step {
&CheckedProofStep::AddClause { id, .. } => {
self.last_added_id = id;
}
&CheckedProofStep::DuplicatedClause { id, .. }
| &CheckedProofStep::TautologicalClause { id, .. } => {
self.last_added_id = id;
if self.binary {
self.open_delete()?;
self.write_ids(&[id])?;
} else {
self.buffered_deletes.push(id);
}
}
&CheckedProofStep::AtClause {
id,
clause,
propagations,
..
} => {
self.close_delete()?;
self.last_added_id = id;
self.write_add_step()?;
self.write_ids(&[id])?;
self.write_lits(clause)?;
self.write_sep()?;
self.write_ids(propagations)?;
self.write_end()?;
}
&CheckedProofStep::DeleteAtClause {
id,
keep_as_redundant,
..
}
| &CheckedProofStep::DeleteRatClause {
id,
keep_as_redundant,
..
} => {
if !keep_as_redundant {
self.open_delete()?;
self.write_ids(&[id])?;
}
}
&CheckedProofStep::DeleteClause { id, .. } => {
self.open_delete()?;
self.write_ids(&[id])?;
}
&CheckedProofStep::UserVar { .. }
| &CheckedProofStep::MakeIrredundant { .. }
| &CheckedProofStep::Model { .. }
| &CheckedProofStep::Assumptions { .. }
| &CheckedProofStep::FailedAssumptions { .. } => (),
}
Ok(())
}
}
impl<'a> WriteLrat<'a> {
pub fn new(target: impl Write + 'a, binary: bool) -> WriteLrat<'a> {
WriteLrat {
binary,
target: BufWriter::new(Box::new(target)),
delete_open: false,
last_added_id: 0,
buffered_deletes: vec![],
}
}
pub fn flush(&mut self) -> Result<(), Error> {
self.close_delete()?;
self.target.flush()?;
Ok(())
}
fn open_delete(&mut self) -> Result<(), Error> {
if !self.delete_open {
if !self.binary {
self.write_ids(&[self.last_added_id])?;
}
self.write_delete_step()?;
self.delete_open = true;
}
Ok(())
}
fn close_delete(&mut self) -> Result<(), Error> {
if self.delete_open {
self.write_end()?;
self.delete_open = false;
}
Ok(())
}
fn write_delete_step(&mut self) -> Result<(), Error> {
if self.binary {
self.target.write_all(b"d")?;
} else {
self.target.write_all(b"d ")?;
}
Ok(())
}
fn write_add_step(&mut self) -> Result<(), Error> {
if self.binary {
self.target.write_all(b"a")?;
}
Ok(())
}
fn write_ids(&mut self, ids: &[u64]) -> Result<(), Error> {
if self.binary {
for &id in ids {
leb128::write::unsigned(&mut self.target, (id + 1) * 2)?;
}
} else {
for &id in ids {
itoa::write(&mut self.target, id + 1)?;
self.target.write_all(b" ")?;
}
}
Ok(())
}
fn write_lits(&mut self, lits: &[Lit]) -> Result<(), Error> {
if self.binary {
for &lit in lits {
leb128::write::unsigned(&mut self.target, lit.code() as u64 + 2)?;
}
} else {
for &lit in lits {
itoa::write(&mut self.target, lit.to_dimacs())?;
self.target.write_all(b" ")?;
}
}
Ok(())
}
fn write_end(&mut self) -> Result<(), Error> {
if self.binary {
self.target.write_all(&[0])?
} else {
self.target.write_all(b"0\n")?
}
Ok(())
}
fn write_sep(&mut self) -> Result<(), Error> {
if self.binary {
self.target.write_all(&[0])?
} else {
self.target.write_all(b"0 ")?
}
Ok(())
}
}
impl<'a> Drop for WriteLrat<'a> {
fn drop(&mut self) {
let _ignore_errors = self.close_delete();
}
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
use std::{
fs::File,
path::PathBuf,
process::{Command, Stdio},
};
use tempfile::TempDir;
use varisat::{dimacs::write_dimacs, ProofFormat, Solver};
use varisat_checker::Checker;
use varisat_formula::{cnf_formula, test::sgen_unsat_formula, CnfFormula};
fn check_lrat(tool: &str, cnf_file: &PathBuf, proof_file: &PathBuf) -> Result<bool, Error> {
let mut child = Command::new(tool)
.stdin(Stdio::piped())
.stdout(Stdio::piped())
.spawn()?;
let mut stdin = child.stdin.as_mut().unwrap();
writeln!(&mut stdin, "(lrat-check {:?} {:?})", cnf_file, proof_file)?;
let output = child.wait_with_output()?;
let stdout = std::str::from_utf8(&output.stdout)?;
Ok(stdout.contains("s VERIFIED"))
}
fn solve_and_check_lrat(
formula: CnfFormula,
binary: bool,
direct: bool,
) -> Result<bool, Error> {
let tmp = TempDir::new()?;
let lrat_proof = tmp.path().join("proof.lrat");
let cnf_file = tmp.path().join("input.cnf");
let mut dimacs = vec![];
let mut proof = vec![];
let mut write_lrat = WriteLrat::new(File::create(&lrat_proof)?, binary);
write_dimacs(&mut File::create(&cnf_file)?, &formula)?;
let mut solver = Solver::new();
write_dimacs(&mut dimacs, &formula).unwrap();
if direct {
solver.add_proof_processor(&mut write_lrat);
} else {
solver.write_proof(&mut proof, ProofFormat::Varisat);
}
solver.add_dimacs_cnf(&mut &dimacs[..]).unwrap();
assert_eq!(solver.solve().ok(), Some(false));
solver.close_proof()?;
drop(solver);
if !direct {
let mut checker = Checker::new();
checker.add_processor(&mut write_lrat);
checker.add_dimacs_cnf(&mut &dimacs[..]).unwrap();
checker.check_proof(&mut &proof[..]).unwrap();
}
drop(write_lrat);
check_lrat(
if binary { "check-clrat" } else { "check-lrat" },
&cnf_file,
&lrat_proof,
)
}
#[cfg_attr(not(test_check_lrat), ignore)]
#[test]
fn duplicated_clause_lrat() {
for &binary in [false, true].iter() {
for &direct in [false, true].iter() {
assert!(
solve_and_check_lrat(
cnf_formula![
1, 2;
1, 2;
-1, -2;
3;
-3, -1, 2;
-4, 1, -2;
4;
],
binary,
direct
)
.unwrap(),
"binary: {:?} direct: {:?}",
binary,
direct
);
}
}
}
#[cfg_attr(not(test_check_lrat), ignore)]
#[test]
fn unit_conflict_lrat() {
for &binary in [false, true].iter() {
for &direct in [false, true].iter() {
assert!(
solve_and_check_lrat(
cnf_formula![
1;
2, 3;
-1;
4, 5;
],
binary,
direct
)
.unwrap(),
"binary: {:?} direct: {:?}",
binary,
direct
);
}
}
}
proptest! {
#[cfg_attr(not(test_check_lrat), ignore)]
#[test]
fn sgen_unsat_lrat(
formula in sgen_unsat_formula(1..7usize),
binary in proptest::bool::ANY,
direct in proptest::bool::ANY,
) {
prop_assert!(solve_and_check_lrat(formula, binary, direct).unwrap());
}
}
}