#![cfg_attr(doctest, doc = include_str!("../README.md"))]
mod blast;
mod bv;
pub mod field;
mod sat;
pub mod set;
pub mod theory;
use std::cell::RefCell;
use std::collections::HashMap;
pub use bv::{Bv, mask};
pub use set::Set;
pub use theory::{Array, ArrayTheory, ModelView, Theory, Uninterpreted};
use blast::Blaster;
use bv::Node;
use sat::SatResult::{Sat, Unknown, Unsat};
pub const DEFAULT_BUDGET: u64 = 4_000_000;
const DEFAULT_MAX_CLAUSES: usize = 40_000;
#[derive(Debug)]
pub enum Solution {
Sat(Model),
Unsat,
Unknown,
}
pub struct Solver {
vars: Vec<(String, u32)>,
asserts: Vec<Bv>,
max_clauses: usize,
cache: RefCell<Option<CacheState>>,
theories: Vec<Box<dyn Theory>>,
theory_rounds: usize,
}
impl std::fmt::Debug for Solver {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("Solver")
.field("vars", &self.vars)
.field("asserts", &self.asserts.len())
.field("max_clauses", &self.max_clauses)
.field("cached", &self.cache.borrow().is_some())
.field(
"theories",
&self.theories.iter().map(|t| t.name()).collect::<Vec<_>>(),
)
.field("theory_rounds", &self.theory_rounds)
.finish()
}
}
const DEFAULT_THEORY_ROUNDS: usize = 8;
#[derive(Debug)]
struct Cache {
clauses: Vec<Vec<i32>>,
nvars: usize,
var_bits: HashMap<usize, Vec<i32>>,
}
#[derive(Debug)]
enum CacheState {
Ready(Cache),
Oversize,
}
impl Default for Solver {
fn default() -> Self {
Self {
vars: Vec::new(),
asserts: Vec::new(),
max_clauses: DEFAULT_MAX_CLAUSES,
cache: RefCell::new(None),
theories: Vec::new(),
theory_rounds: DEFAULT_THEORY_ROUNDS,
}
}
}
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..=128).contains(&width),
"variable width must be 1..=128, got {width}"
);
let id = self.vars.len();
self.vars.push((name.to_string(), width));
self.cache.replace(None);
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);
self.cache.replace(None);
}
#[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_assumptions(&[], budget, None)
}
#[must_use]
pub fn check_assumptions(&self, assumptions: &[Bv]) -> Solution {
self.check_assumptions_with_budget(assumptions, DEFAULT_BUDGET)
}
#[must_use]
pub fn check_assumptions_with_budget(&self, assumptions: &[Bv], budget: u64) -> Solution {
self.solve_assumptions(assumptions, budget, None)
}
#[must_use]
pub fn check_assumptions_within(
&self,
assumptions: &[Bv],
budget: u64,
deadline: std::time::Instant,
) -> Solution {
self.solve_assumptions(assumptions, budget, Some(deadline))
}
#[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);
b.deadline = deadline;
b.cnf.cap = Some(self.max_clauses);
for (id, (_, width)) in self.vars.iter().enumerate() {
b.declare_var(id, *width);
}
for c in constraints {
b.assert_true(c);
}
if b.cnf.full
|| b.cnf.clauses.len() > self.max_clauses
|| deadline.is_some_and(|d| std::time::Instant::now() >= d)
{
return Solution::Unknown;
}
match b.cnf.solve_within(budget, deadline) {
Sat(assignment) => Solution::Sat(Model {
assignment,
var_bits: b.var_bits,
name_to_id: self.name_to_id(),
}),
Unsat => Solution::Unsat,
Unknown => Solution::Unknown,
}
}
fn solve_assumptions(
&self,
assumptions: &[Bv],
budget: u64,
deadline: Option<std::time::Instant>,
) -> Solution {
if !self.ensure_cache(deadline) {
return Solution::Unknown;
}
let cache = self.cache.borrow();
let cache = match cache.as_ref() {
Some(CacheState::Ready(cache)) => cache,
_ => return Solution::Unknown,
};
let bump = bumpalo::Bump::new();
let mut b = Blaster::new(&bump);
b.deadline = deadline;
b.cnf.cap = Some(self.max_clauses.saturating_sub(cache.clauses.len()));
b.var_bits = cache.var_bits.clone();
b.cnf.nvars = cache.nvars;
for c in assumptions {
b.assert_true(c);
}
let mut clauses: Vec<&[i32]> = cache.clauses.iter().map(|c| c.as_slice()).collect();
clauses.extend(b.cnf.clauses.iter().copied());
if b.cnf.full
|| clauses.len() > self.max_clauses
|| deadline.is_some_and(|d| std::time::Instant::now() >= d)
{
return Solution::Unknown;
}
match sat::solve(&clauses, b.cnf.nvars, budget, deadline) {
Sat(assignment) => Solution::Sat(Model {
assignment,
var_bits: b.var_bits,
name_to_id: self.name_to_id(),
}),
Unsat => Solution::Unsat,
Unknown => Solution::Unknown,
}
}
fn ensure_cache(&self, deadline: Option<std::time::Instant>) -> bool {
let mut cache = self.cache.borrow_mut();
if cache.is_none() {
let (built, over) = self.blast_background(deadline);
if over {
*cache = Some(CacheState::Oversize);
return false;
}
if deadline.is_some_and(|d| std::time::Instant::now() >= d) {
return false;
}
*cache = Some(CacheState::Ready(built));
return true;
}
matches!(cache.as_ref(), Some(CacheState::Ready(_)))
}
fn blast_background(&self, deadline: Option<std::time::Instant>) -> (Cache, bool) {
let bump = bumpalo::Bump::new();
let mut b = Blaster::new(&bump);
b.deadline = deadline;
b.cnf.cap = Some(self.max_clauses);
for (id, (_, width)) in self.vars.iter().enumerate() {
b.declare_var(id, *width);
}
for c in &self.asserts {
b.assert_true(c);
}
let over = b.cnf.full || b.cnf.clauses.len() > self.max_clauses;
(
Cache {
clauses: b.cnf.clauses.iter().map(|c| c.to_vec()).collect(),
nvars: b.cnf.nvars,
var_bits: b.var_bits,
},
over,
)
}
fn name_to_id(&self) -> HashMap<String, usize> {
self.vars
.iter()
.enumerate()
.map(|(id, (n, _))| (n.clone(), id))
.collect()
}
}
#[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> {
self.value_of(*self.name_to_id.get(name)?)
}
#[must_use]
pub fn get128(&self, name: &str) -> Option<u128> {
self.value_of128(*self.name_to_id.get(name)?)
}
pub(crate) fn value_of(&self, id: usize) -> Option<u64> {
let bits = self.var_bits.get(&id)?;
if bits.len() > 64 {
return None;
}
self.value_of128(id).and_then(|v| u64::try_from(v).ok())
}
pub(crate) fn value_of128(&self, id: usize) -> Option<u128> {
let bits = self.var_bits.get(&id)?;
let mut v = 0u128;
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 |= 1u128 << 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"
);
}
#[test]
fn test_unused_variable_still_reads_back() {
let mut s = Solver::new();
let x = s.var("x", 8);
let _unused = s.var("unused", 16);
s.assert(x.eq(&Bv::val(5, 8)));
let m = sat(&s);
assert_eq!(m.get("x"), Some(5));
let u = m.get("unused").expect("a declared variable reads back");
assert!(u <= 0xffff, "unused value {u} exceeds its 16-bit width");
}
#[test]
fn test_variables_read_back_with_no_constraints() {
let mut s = Solver::new();
let _a = s.var("a", 1);
let _b = s.var("b", 64);
let m = sat(&s);
assert!(m.get("a").is_some());
assert!(m.get("b").is_some());
}
}