#![cfg_attr(doctest, doc = include_str!("../README.md"))]
mod blast;
mod bv;
mod sat;
use std::collections::HashMap;
pub use bv::{Bv, mask};
use blast::Blaster;
use bv::Node;
use sat::SatResult::{Sat, Unknown, Unsat};
const DEFAULT_BUDGET: u64 = 4_000_000;
const DEFAULT_MAX_CLAUSES: usize = 40_000;
#[derive(Debug)]
pub enum Solution {
Sat(Model),
Unsat,
Unknown,
}
#[derive(Debug)]
pub struct Solver {
vars: Vec<(String, u32)>,
asserts: Vec<Bv>,
max_clauses: usize,
}
impl Default for Solver {
fn default() -> Self {
Self {
vars: Vec::new(),
asserts: Vec::new(),
max_clauses: DEFAULT_MAX_CLAUSES,
}
}
}
impl Solver {
#[must_use]
pub fn new() -> Self {
Self::default()
}
#[must_use]
pub fn with_max_clauses(mut self, n: usize) -> Self {
self.max_clauses = n;
self
}
pub fn var(&mut self, name: &str, width: u32) -> Bv {
assert!(
(1..=64).contains(&width),
"variable width must be 1..=64, got {width}"
);
let id = self.vars.len();
self.vars.push((name.to_string(), width));
Bv::wrap(Node::Var(width, id))
}
#[must_use]
pub fn depends_on(&self, bv: &Bv, prefix: &str) -> bool {
bv.var_ids().into_iter().any(|id| {
self.vars
.get(id)
.is_some_and(|(n, _)| n.starts_with(prefix))
})
}
pub fn assert(&mut self, constraint: Bv) {
assert_eq!(
constraint.width(),
1,
"a constraint must be 1 bit, got {}",
constraint.width()
);
self.asserts.push(constraint);
}
#[must_use]
pub fn check(&self) -> Solution {
self.check_with_budget(DEFAULT_BUDGET)
}
#[must_use]
pub fn check_with_budget(&self, budget: u64) -> Solution {
self.solve_constraints(&self.asserts, budget, None)
}
#[must_use]
pub fn check_all(&self, constraints: &[Bv]) -> Solution {
self.solve_constraints(constraints, DEFAULT_BUDGET, None)
}
#[must_use]
pub fn check_all_with_budget(&self, constraints: &[Bv], budget: u64) -> Solution {
self.solve_constraints(constraints, budget, None)
}
#[must_use]
pub fn check_all_within(
&self,
constraints: &[Bv],
budget: u64,
deadline: std::time::Instant,
) -> Solution {
self.solve_constraints(constraints, budget, Some(deadline))
}
fn solve_constraints(
&self,
constraints: &[Bv],
budget: u64,
deadline: Option<std::time::Instant>,
) -> Solution {
let bump = bumpalo::Bump::new();
let mut b = Blaster::new(&bump);
for c in constraints {
b.assert_true(c);
}
if b.cnf.clauses.len() > self.max_clauses {
return Solution::Unknown;
}
match b.cnf.solve_within(budget, deadline) {
Sat(assignment) => {
let name_to_id = self
.vars
.iter()
.enumerate()
.map(|(id, (n, _))| (n.clone(), id))
.collect();
Solution::Sat(Model {
assignment,
var_bits: b.var_bits,
name_to_id,
})
}
Unsat => Solution::Unsat,
Unknown => Solution::Unknown,
}
}
}
#[derive(Debug)]
pub struct Model {
assignment: Vec<bool>,
var_bits: HashMap<usize, Vec<i32>>,
name_to_id: HashMap<String, usize>,
}
impl Model {
#[must_use]
pub fn get(&self, name: &str) -> Option<u64> {
let id = *self.name_to_id.get(name)?;
let bits = self.var_bits.get(&id)?;
if bits.len() > 64 {
return None;
}
let mut v = 0u64;
for (i, &lit) in bits.iter().enumerate() {
let base = self.assignment[(lit.unsigned_abs() - 1) as usize];
if if lit > 0 { base } else { !base } {
v |= 1u64 << i;
}
}
Some(v)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn sat(s: &Solver) -> Model {
match s.check() {
Solution::Sat(m) => m,
other => panic!("expected SAT, got {other:?}"),
}
}
#[test]
fn test_linear_add() {
let mut s = Solver::new();
let x = s.var("x", 64);
s.assert(x.add(&Bv::val(3, 64)).eq(&Bv::val(10, 64)));
assert_eq!(sat(&s).get("x"), Some(7));
}
#[test]
fn test_multiply_by_const() {
let mut s = Solver::new();
let x = s.var("x", 32);
s.assert(x.mul(&Bv::val(2, 32)).eq(&Bv::val(10, 32)));
let v = sat(&s).get("x").unwrap();
assert_eq!(v.wrapping_mul(2) & 0xffff_ffff, 10, "got x={v}");
}
#[test]
fn test_contradiction_is_unsat() {
let mut s = Solver::new();
let x = s.var("x", 16);
s.assert(x.eq(&Bv::val(5, 16)));
s.assert(x.eq(&Bv::val(6, 16)));
assert!(matches!(s.check(), Solution::Unsat));
}
#[test]
fn test_range_model() {
let mut s = Solver::new();
let x = s.var("x", 32);
s.assert(x.ugt(&Bv::val(5, 32)));
s.assert(x.ult(&Bv::val(10, 32)));
let v = sat(&s).get("x").unwrap();
assert!((6..=9).contains(&v), "got {v}");
}
#[test]
fn test_unsigned_add_overflow() {
let mut s = Solver::new();
let x = s.var("x", 8);
s.assert(x.add(&Bv::val(1, 8)).ult(&x));
assert_eq!(sat(&s).get("x"), Some(255));
}
#[test]
fn test_signed_vs_unsigned_compare() {
let mut s = Solver::new();
s.assert(Bv::val(0xff, 8).slt(&Bv::val(0, 8)));
assert!(matches!(s.check(), Solution::Sat(_)));
let mut u = Solver::new();
u.assert(Bv::val(0xff, 8).ult(&Bv::val(0, 8)));
assert!(matches!(u.check(), Solution::Unsat));
}
#[test]
fn test_overflow_in_size_math() {
let mut s = Solver::new();
let count = s.var("count", 32);
let elem = Bv::val(0x10, 32);
let size = count.mul(&elem);
s.assert(size.ult(&elem)); s.assert(count.ugt(&Bv::val(0, 32)));
let c = sat(&s).get("count").unwrap();
assert!(
c.wrapping_mul(0x10) & 0xffff_ffff < 0x10,
"count={c} should overflow"
);
}
}