pub mod array;
pub mod uf;
pub use array::{Array, ArrayTheory};
pub use uf::Uninterpreted;
use std::collections::HashMap;
use std::rc::Rc;
use crate::bv::{Bv, Cmp, eval_bin, mask128, rot_, shl_, shr_, signed};
use crate::{Model, Node, Solution, Solver};
#[derive(Debug)]
pub struct ModelView<'a> {
model: &'a Model,
}
impl<'a> ModelView<'a> {
#[must_use]
pub fn new(model: &'a Model) -> Self {
Self { model }
}
#[must_use]
pub fn get(&self, name: &str) -> Option<u64> {
self.model.get(name)
}
#[must_use]
pub fn eval(&self, bv: &Bv) -> Option<u64> {
if bv.width() > 64 {
return None;
}
self.eval128(bv).and_then(|v| u64::try_from(v).ok())
}
#[must_use]
pub fn eval128(&self, bv: &Bv) -> Option<u128> {
let mut memo: HashMap<usize, u128> = HashMap::new();
let key = |b: &Bv| Rc::as_ptr(&b.0) as usize;
let mut stack: Vec<(Bv, bool)> = vec![(bv.clone(), false)];
while let Some((cur, ready)) = stack.pop() {
if memo.contains_key(&key(&cur)) {
continue;
}
if !ready {
stack.push((cur.clone(), true));
for child in children_of(&cur.0) {
if !memo.contains_key(&key(&child)) {
stack.push((child, false));
}
}
continue;
}
let val = eval_node(&cur.0, &memo, self.model)?;
memo.insert(key(&cur), val);
}
memo.get(&key(bv)).copied()
}
}
fn children_of(n: &Node) -> Vec<Bv> {
match n {
Node::Const(_, _) | Node::Var(_, _) => Vec::new(),
Node::Not(a)
| Node::Neg(a)
| Node::ShlC(a, _)
| Node::ShrC(a, _, _)
| Node::RotC(a, _, _)
| Node::Zext(a, _)
| Node::Sext(a, _)
| Node::Extract(a, _, _) => vec![a.clone()],
Node::Bin(_, a, b)
| Node::Compare(_, a, b)
| Node::Concat(a, b)
| Node::ShlV(a, b)
| Node::ShrV(a, b, _)
| Node::RotV(a, b, _) => vec![a.clone(), b.clone()],
Node::Ite(a, b, c) => vec![a.clone(), b.clone(), c.clone()],
}
}
fn eval_node(n: &Node, memo: &HashMap<usize, u128>, model: &Model) -> Option<u128> {
let v = |b: &Bv| -> Option<u128> { memo.get(&(Rc::as_ptr(&b.0) as usize)).copied() };
Some(match n {
Node::Const(w, value) => mask128(*value, *w),
Node::Var(w, id) => mask128(model.value_of128(*id)?, *w),
Node::Not(a) => mask128(!v(a)?, a.width()),
Node::Neg(a) => mask128(0u128.wrapping_sub(v(a)?), a.width()),
Node::Bin(op, a, b) => eval_bin(*op, v(a)?, v(b)?, a.width()),
Node::ShlC(a, k) => shl_(v(a)?, u128::from(*k), a.width()),
Node::ShrC(a, k, arith) => shr_(v(a)?, u128::from(*k), a.width(), *arith),
Node::ShlV(a, k) => shl_(v(a)?, v(k)?, a.width()),
Node::ShrV(a, k, arith) => shr_(v(a)?, v(k)?, a.width(), *arith),
Node::RotC(a, k, left) => rot_(v(a)?, u128::from(*k), a.width(), *left),
Node::RotV(a, k, left) => rot_(v(a)?, v(k)?, a.width(), *left),
Node::Compare(c, a, b) => {
let (x, y, w) = (v(a)?, v(b)?, a.width());
let bit = match c {
Cmp::Eq => x == y,
Cmp::Ne => x != y,
Cmp::Ult => x < y,
Cmp::Ule => x <= y,
Cmp::Slt => signed(x, w) < signed(y, w),
Cmp::Sle => signed(x, w) <= signed(y, w),
};
u128::from(bit)
}
Node::Zext(a, _) => v(a)?,
Node::Sext(a, w) => mask128(signed(v(a)?, a.width()) as u128, *w),
Node::Extract(a, hi, lo) => mask128(v(a)? >> *lo, *hi - *lo + 1),
Node::Concat(hi, lo) => mask128((v(hi)? << lo.width()) | v(lo)?, hi.width() + lo.width()),
Node::Ite(c, t, e) => {
if v(c)? != 0 {
v(t)?
} else {
v(e)?
}
}
})
}
pub trait Theory {
fn name(&self) -> &'static str;
fn violated_lemmas(&self, model: &ModelView<'_>) -> Vec<Bv>;
fn eager_lemmas(&self) -> Vec<Bv> {
Vec::new()
}
}
#[derive(Debug, Default)]
pub struct Contradiction;
impl Theory for Contradiction {
fn name(&self) -> &'static str {
"contradiction"
}
fn violated_lemmas(&self, _model: &ModelView<'_>) -> Vec<Bv> {
vec![Bv::val(0, 1).eq(&Bv::val(1, 1))]
}
fn eager_lemmas(&self) -> Vec<Bv> {
vec![Bv::val(0, 1).eq(&Bv::val(1, 1))]
}
}
impl<T: Theory + ?Sized> Theory for Box<T> {
fn name(&self) -> &'static str {
(**self).name()
}
fn violated_lemmas(&self, model: &ModelView<'_>) -> Vec<Bv> {
(**self).violated_lemmas(model)
}
fn eager_lemmas(&self) -> Vec<Bv> {
(**self).eager_lemmas()
}
}
impl Solver {
pub fn register_theory(&mut self, theory: impl Theory + 'static) {
assert!(
!self.theories.iter().any(|t| t.name() == theory.name()),
"a theory named `{}` is already registered",
theory.name()
);
self.theories.push(Box::new(theory));
}
#[must_use]
pub fn with_theory_rounds(mut self, rounds: usize) -> Self {
self.theory_rounds = rounds;
self
}
#[must_use]
pub fn check_theories(&self, budget: u64, deadline: Option<std::time::Instant>) -> Solution {
self.solve_theory_rounds(&[], true, budget, deadline)
}
#[must_use]
pub fn check_assumptions_theories(
&self,
assumptions: &[Bv],
budget: u64,
deadline: Option<std::time::Instant>,
) -> Solution {
self.solve_theory_rounds(assumptions, true, budget, deadline)
}
#[must_use]
pub fn check_all_theories(
&self,
constraints: &[Bv],
budget: u64,
deadline: Option<std::time::Instant>,
) -> Solution {
self.solve_theory_rounds(constraints, false, budget, deadline)
}
#[must_use]
pub fn model_consistent(&self, model: &Model) -> bool {
let view = ModelView::new(model);
self.theories
.iter()
.all(|t| t.violated_lemmas(&view).is_empty())
}
#[must_use]
pub fn eager_theory_lemmas(&self) -> Vec<Bv> {
self.theories
.iter()
.flat_map(|t| t.eager_lemmas())
.collect()
}
fn solve_theory_rounds(
&self,
base: &[Bv],
assumptions: bool,
budget: u64,
deadline: Option<std::time::Instant>,
) -> Solution {
let solve = |lemmas: &[Bv]| {
let mut all: Vec<Bv> = base.to_vec();
all.extend(lemmas.iter().cloned());
if !assumptions {
return self.solve_constraints(&all, budget, deadline);
}
if lemmas.is_empty() {
return self.solve_assumptions(&all, budget, deadline);
}
let mut together: Vec<Bv> = self.asserts.clone();
together.extend(all);
self.solve_constraints(&together, budget, deadline)
};
if self.theories.is_empty() || self.theory_rounds == 0 {
return solve(&[]);
}
let mut lemmas: Vec<Bv> = Vec::new();
for _round in 0..self.theory_rounds {
if deadline.is_some_and(|d| std::time::Instant::now() >= d) {
return Solution::Unknown;
}
match solve(&lemmas) {
Solution::Sat(model) => {
let mut fresh: Vec<Bv> = Vec::new();
{
let view = ModelView::new(&model);
for t in &self.theories {
fresh.extend(t.violated_lemmas(&view));
}
}
for l in &fresh {
assert_eq!(
l.width(),
1,
"theory lemma must be 1 bit, got {}",
l.width()
);
}
if fresh.is_empty() {
return Solution::Sat(model);
}
lemmas.extend(fresh);
}
other => return other,
}
}
Solution::Unknown
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{Solution, Solver};
struct Even {
x: Bv,
}
impl Theory for Even {
fn name(&self) -> &'static str {
"even"
}
fn violated_lemmas(&self, model: &ModelView<'_>) -> Vec<Bv> {
match model.eval(&self.x) {
Some(v) if v % 2 == 1 => vec![self.x.and(&Bv::val(1, 8)).eq(&Bv::val(0, 8))],
_ => Vec::new(),
}
}
}
#[test]
fn eval_reads_the_model_the_way_the_folder_does() {
let mut s = Solver::new();
let x = s.var("x", 8);
let y = s.var("y", 8);
s.assert(x.eq(&Bv::val(0x37, 8)));
s.assert(y.eq(&Bv::val(0x9a, 8)));
let cond = x.add(&y).xor(&x.rotl(3)).ult(&Bv::val(0x20, 8));
let e = Bv::ite(&cond, &x.extract(3, 0), &y.extract(3, 0));
let Solution::Sat(m) = s.check() else {
panic!("expected SAT")
};
let view = ModelView::new(&m);
let (xv, yv) = (0x37u8, 0x9au8);
let rot = xv.rotate_left(3);
let expect = if (xv.wrapping_add(yv) ^ rot) < 0x20 {
xv & 0xf
} else {
yv & 0xf
};
assert_eq!(view.eval(&e), Some(u64::from(expect)));
assert_eq!(view.get("x"), Some(0x37));
assert_eq!(view.eval(&x), Some(0x37));
}
#[test]
fn a_model_is_validated_and_re_solved_until_consistent() {
let mut s = Solver::new();
let x = s.var("x", 8);
s.assert(x.add(&Bv::val(1, 8)).eq(&Bv::val(4, 8)));
s.register_theory(Even { x });
let Solution::Sat(m) = s.check() else {
panic!("expected SAT")
};
assert_eq!(m.get("x"), Some(3));
assert!(
!s.model_consistent(&m),
"plain check() ignores theories, and the violation is visible"
);
assert!(matches!(s.check_theories(100_000, None), Solution::Unsat));
let mut s2 = Solver::new();
let (x2, y2) = (s2.var("x", 8), s2.var("y", 8));
s2.assert(x2.add(&y2).eq(&Bv::val(4, 8)));
s2.register_theory(Even { x: x2 });
let Solution::Sat(m2) = s2.check_theories(100_000, None) else {
panic!("expected SAT")
};
assert_eq!(m2.get("x").map(|v| v % 2), Some(0));
assert!(s2.model_consistent(&m2));
}
#[test]
fn a_contradictory_theory_is_unsat_immediately() {
let mut s = Solver::new();
let x = s.var("x", 8);
s.assert(x.eq(&Bv::val(1, 8)));
s.register_theory(Contradiction);
assert!(matches!(s.check_theories(100_000, None), Solution::Unsat));
assert!(matches!(s.check(), Solution::Sat(_)));
}
#[test]
fn round_exhaustion_is_unknown_never_a_wrong_verdict() {
struct NotThisOne {
x: Bv,
}
impl Theory for NotThisOne {
fn name(&self) -> &'static str {
"not-this-one"
}
fn violated_lemmas(&self, m: &ModelView<'_>) -> Vec<Bv> {
let v = m.eval(&self.x).expect("8-bit term");
vec![self.x.ne(&Bv::val(v, 8))]
}
}
let mut s = Solver::new().with_theory_rounds(3);
let x = s.var("x", 8);
s.register_theory(NotThisOne { x });
assert!(matches!(s.check_theories(100_000, None), Solution::Unknown));
}
#[test]
fn no_theories_means_no_change() {
let mut s = Solver::new();
let x = s.var("x", 8);
s.assert(x.ult(&Bv::val(10, 8)));
assert!(matches!(
s.check_assumptions_theories(&[x.ugt(&Bv::val(5, 8))], 100_000, None),
Solution::Sat(_)
));
assert!(matches!(
s.check_all_theories(
&[x.ugt(&Bv::val(30, 8)), x.ult(&Bv::val(20, 8))],
100_000,
None
),
Solution::Unsat
));
}
#[test]
fn duplicate_registration_panics() {
let mut s = Solver::new();
let x = s.var("x", 8);
s.register_theory(Even { x: x.clone() });
let dup = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
s.register_theory(Even { x: x.clone() });
}));
assert!(dup.is_err(), "a duplicated theory name must be refused");
}
}