use std::cell::{Cell, RefCell};
use batsat::interface::SolverInterface;
use batsat::{Callbacks, ClauseKind, Lit as BatLit, SolverOpts, Var, lbool};
use super::drup::Step;
use crate::limits::{Phase, Progress};
use crate::linear::search::Reason;
use crate::linear::search::memory::Account;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub(crate) struct Lit {
var: u32,
positive: bool,
}
impl Lit {
pub(crate) const fn positive(var: u32) -> Self {
Self {
var,
positive: true,
}
}
pub(crate) const fn negative(var: u32) -> Self {
Self {
var,
positive: false,
}
}
pub(crate) const fn var(self) -> u32 {
self.var
}
pub(crate) const fn is_positive(self) -> bool {
self.positive
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Answer {
Satisfiable,
Unsatisfiable,
Stopped(Reason),
}
pub(crate) trait Solver {
fn new_var(&mut self) -> u32;
fn add_clause(&mut self, clause: &[Lit]);
fn solve(&mut self, assumptions: &[Lit]) -> Answer;
fn value(&self, literal: Lit) -> bool;
fn failed(&self) -> Vec<Lit>;
fn poll(&mut self, work: u64) -> Option<Reason>;
fn calls(&self) -> u64;
fn conflicts(&self) -> u64;
}
const fn clause_bytes(len: usize) -> usize {
len * size_of::<BatLit>() + 32
}
const VARIABLE_BYTES: usize = 128;
pub(crate) struct Bridge<'s> {
stop: RefCell<&'s mut dyn FnMut(Progress) -> bool>,
account: &'s Account,
calls: Cell<u64>,
done: Cell<u64>,
work: u64,
why: Cell<Option<Reason>>,
proof: Option<Vec<Step>>,
}
impl Callbacks for Bridge<'_> {
fn on_new_clause(&mut self, clause: &[BatLit], _kind: ClauseKind) {
self.done.set(self.done.get().saturating_add(1));
self.account.charge(clause_bytes(clause.len()));
self.record(clause, Step::Add);
}
fn on_delete_clause(&mut self, clause: &[BatLit]) {
self.account.release(clause_bytes(clause.len()));
self.record(clause, Step::Delete);
}
fn stop(&self) -> bool {
self.ask(1)
}
}
impl Bridge<'_> {
fn record(&mut self, clause: &[BatLit], step: fn(Box<[Lit]>) -> Step) {
if let Some(proof) = &mut self.proof {
self.account.charge(Step::bytes(clause.len()));
proof.push(step(clause.iter().map(|&l| Batsat::ours(l)).collect()));
}
}
fn ask(&self, work: u64) -> bool {
if self.why.get().is_some() {
return true;
}
let done = self.done.get();
let why = if done > self.work {
Some(Reason::WorkLimit { limit: self.work })
} else if self.account.over() {
Some(Reason::MemoryLimit {
limit_bytes: self.account.limit(),
})
} else if (self.stop.borrow_mut())(Progress::new(Phase::Search, work, done)) {
Some(Reason::Stopped)
} else {
None
};
self.why.set(why);
why.is_some()
}
}
pub(crate) struct Batsat<'s> {
solver: batsat::Solver<Bridge<'s>>,
}
impl<'s> Batsat<'s> {
pub(crate) fn new(
work: u64,
account: &'s Account,
stop: &'s mut dyn FnMut(Progress) -> bool,
) -> Self {
let bridge = Bridge {
stop: RefCell::new(stop),
account,
calls: Cell::new(0),
done: Cell::new(0),
work,
why: Cell::new(None),
proof: None,
};
Self {
solver: batsat::Solver::new(SolverOpts::default(), bridge),
}
}
pub(crate) fn recording(
work: u64,
account: &'s Account,
stop: &'s mut dyn FnMut(Progress) -> bool,
) -> Self {
let mut solver = Self::new(work, account, stop);
solver.solver.cb_mut().proof = Some(Vec::new());
solver
}
pub(crate) fn proof(&mut self) -> Option<Vec<Step>> {
let proof = self.solver.cb_mut().proof.as_mut()?;
Some(std::mem::take(proof))
}
fn lit(literal: Lit) -> BatLit {
BatLit::new(Var::unsafe_from_idx(literal.var), literal.positive)
}
fn ours(literal: BatLit) -> Lit {
Lit {
var: literal.var().idx(),
positive: literal.sign(),
}
}
}
pub(crate) const MOST_VARIABLES: u32 = u32::MAX / 2 - 1;
impl Solver for Batsat<'_> {
fn new_var(&mut self) -> u32 {
self.solver.cb().account.charge(VARIABLE_BYTES);
self.solver.new_var_default().idx()
}
fn add_clause(&mut self, clause: &[Lit]) {
let mut literals: Vec<BatLit> = clause.iter().map(|&l| Self::lit(l)).collect();
self.solver
.cb()
.account
.charge(clause_bytes(literals.len()));
self.solver.add_clause_reuse(&mut literals);
}
fn solve(&mut self, assumptions: &[Lit]) -> Answer {
let bridge = self.solver.cb();
bridge.calls.set(bridge.calls.get().saturating_add(1));
bridge.done.set(bridge.done.get().saturating_add(1));
if bridge.stop() {
return Answer::Stopped(self.why());
}
let assumptions: Vec<BatLit> = assumptions.iter().map(|&l| Self::lit(l)).collect();
let answer = self.solver.solve_limited(&assumptions);
if answer == lbool::TRUE {
Answer::Satisfiable
} else if answer == lbool::FALSE {
let core = self.solver.unsat_core().len();
if core > 0 {
let bridge = self.solver.cb_mut();
bridge.account.release(clause_bytes(core));
if let Some(proof) = &mut bridge.proof {
proof.pop();
bridge.account.release(Step::bytes(core));
}
}
Answer::Unsatisfiable
} else {
Answer::Stopped(self.why())
}
}
fn poll(&mut self, work: u64) -> Option<Reason> {
self.solver.cb().ask(work).then(|| self.why())
}
fn value(&self, literal: Lit) -> bool {
self.solver.value_lit(Self::lit(literal)) == lbool::TRUE
}
fn failed(&self) -> Vec<Lit> {
self.solver
.unsat_core()
.iter()
.map(|&l| Self::ours(!l))
.collect()
}
fn calls(&self) -> u64 {
self.solver.cb().calls.get()
}
fn conflicts(&self) -> u64 {
self.solver.num_conflicts()
}
}
impl Batsat<'_> {
fn why(&self) -> Reason {
self.solver.cb().why.get().unwrap_or(Reason::Stopped)
}
}