use crate::backend::BV;
use crate::error::*;
use boolector::option::{BtorOption, ModelGen};
use boolector::{BVSolution, Btor, SolverResult};
use log::warn;
use std::collections::HashSet;
use std::hash::Hash;
use std::iter::FromIterator;
use std::ops::Deref;
pub fn sat(btor: &Btor) -> Result<bool> {
match btor.sat() {
SolverResult::Sat => Ok(true),
SolverResult::Unsat => Ok(false),
SolverResult::Unknown => Err(Error::SolverError(
"The query was interrupted, timed out, or otherwise failed".to_owned(),
)),
}
}
pub fn sat_with_extra_constraints<I, B>(
btor: &Btor,
constraints: impl IntoIterator<Item = I>,
) -> Result<bool>
where
I: Deref<Target = B>,
B: BV,
{
btor.push(1);
for constraint in constraints {
constraint.assert()?;
}
let retval = sat(btor);
btor.pop(1);
retval
}
pub fn bvs_must_be_equal<V: BV>(btor: &Btor, a: &V, b: &V) -> Result<bool> {
if sat_with_extra_constraints(btor, &[a._ne(&b)])? {
Ok(false)
} else {
Ok(true)
}
}
pub fn bvs_can_be_equal<V: BV>(btor: &Btor, a: &V, b: &V) -> Result<bool> {
if sat_with_extra_constraints(btor, &[a._eq(&b)])? {
Ok(true)
} else {
Ok(false)
}
}
#[derive(PartialEq, Eq, Clone, Debug)]
pub enum PossibleSolutions<V: Eq + Hash> {
Exactly(HashSet<V>),
AtLeast(HashSet<V>),
}
impl<V: Eq + Hash> PossibleSolutions<V> {
pub fn empty() -> Self {
Self::Exactly(HashSet::new())
}
pub fn exactly_one(sol: V) -> Self {
Self::from_iter(std::iter::once(sol))
}
pub fn exactly_two(sol1: V, sol2: V) -> Self {
if sol1 == sol2 {
panic!("expected two different solutions")
}
Self::from_iter(std::iter::once(sol1).chain(std::iter::once(sol2)))
}
}
impl PossibleSolutions<BVSolution> {
pub fn as_u64_solutions(&self) -> Option<PossibleSolutions<u64>> {
match self {
PossibleSolutions::Exactly(v) => {
let opt = v
.iter()
.map(|bvs| bvs.as_u64())
.collect::<Option<HashSet<u64>>>();
opt.map(PossibleSolutions::Exactly)
},
PossibleSolutions::AtLeast(v) => {
let opt = v
.iter()
.map(|bvs| bvs.as_u64())
.collect::<Option<HashSet<u64>>>();
opt.map(PossibleSolutions::AtLeast)
},
}
}
}
impl<V: Eq + Hash> FromIterator<V> for PossibleSolutions<V> {
fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
Self::Exactly(HashSet::from_iter(iter))
}
}
#[derive(PartialEq, Eq, Clone, Debug)]
pub enum SolutionCount {
Exactly(usize),
AtLeast(usize),
}
impl<V: Eq + Hash> PossibleSolutions<V> {
pub fn count(&self) -> SolutionCount {
match self {
PossibleSolutions::Exactly(v) => SolutionCount::Exactly(v.len()),
PossibleSolutions::AtLeast(v) => SolutionCount::AtLeast(v.len()),
}
}
}
pub fn get_possible_solutions_for_bv<V: BV>(
solver: V::SolverRef,
bv: &V,
n: usize,
) -> Result<PossibleSolutions<BVSolution>> {
let ps = if n == 0 {
warn!("A call to get_possible_solutions_for_bv() is resulting in a call to sat() with model generation enabled. Experimentally, these types of calls can be very slow. The BV is {:?}", bv);
solver.set_opt(BtorOption::ModelGen(ModelGen::All));
if sat(&solver)? {
PossibleSolutions::AtLeast(
std::iter::once(
bv.get_a_solution()?.disambiguate(),
)
.collect(),
)
} else {
PossibleSolutions::empty()
}
} else {
match bv.as_binary_str() {
Some(bstr) => PossibleSolutions::exactly_one(BVSolution::from_01x_str(bstr)),
None => {
let mut solutions = HashSet::new();
check_for_common_solutions(solver.clone(), bv, n, &mut solutions)?;
if solutions.len() > n {
PossibleSolutions::AtLeast(solutions)
} else {
solver.push(1);
for solution in solutions.iter() {
bv._ne(&BV::from_binary_str(solver.clone(), solution.as_01x_str()))
.assert()?;
}
warn!("A call to get_possible_solutions_for_bv() is resulting in a call to sat() with model generation enabled. Experimentally, these types of calls can be very slow. The BV is {:?}", bv);
solver.set_opt(BtorOption::ModelGen(ModelGen::All));
while solutions.len() <= n && sat(&solver)? {
let val = bv.get_a_solution()?.disambiguate();
solutions.insert(val.clone());
bv._ne(&BV::from_binary_str(solver.clone(), val.as_01x_str()))
.assert()?;
}
solver.pop(1);
if solutions.len() > n {
PossibleSolutions::AtLeast(solutions)
} else {
PossibleSolutions::Exactly(solutions)
}
}
},
}
};
solver.set_opt(BtorOption::ModelGen(ModelGen::Disabled));
Ok(ps)
}
fn check_for_common_solutions<V: BV>(
solver: V::SolverRef,
bv: &V,
n: usize,
solutions: &mut HashSet<BVSolution>,
) -> Result<()> {
let width = bv.get_width();
if solutions.len() <= n && bvs_can_be_equal(&solver, bv, &BV::zero(solver.clone(), width))? {
solutions.insert(BVSolution::from_01x_str("0".repeat(width as usize)));
}
if solutions.len() <= n && bvs_can_be_equal(&solver, bv, &BV::one(solver.clone(), width))? {
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
1,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 1
&& bvs_can_be_equal(&solver, bv, &BV::ones(solver.clone(), width))?
{
solutions.insert(BVSolution::from_01x_str("1".repeat(width as usize)));
}
if solutions.len() <= n
&& width > 1
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 2, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
2,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 2
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 4, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
4,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 3
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 8, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
8,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 4
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 16, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
16,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 5
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 32, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
32,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 6
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 64, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
64,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 7
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 128, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
128,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 8
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 256, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
256,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 9
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 512, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
512,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 10
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 1024, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
1024,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 11
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 2048, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
2048,
width = width as usize
)));
}
if solutions.len() <= n
&& width > 12
&& bvs_can_be_equal(&solver, bv, &BV::from_u32(solver.clone(), 4096, width))?
{
solutions.insert(BVSolution::from_01x_str(format!(
"{:0width$b}",
4096,
width = width as usize
)));
}
Ok(())
}
pub fn max_possible_solution_for_bv_as_u64<V: BV>(
solver: V::SolverRef,
bv: &V,
) -> Result<Option<u64>> {
let width = bv.get_width();
if width > 64 {
panic!("max_possible_solution_for_bv_as_u64 on a BV with width > 64");
}
if !sat(&solver)? {
return Ok(None);
}
if let Some(u) = bv.as_u64() {
return Ok(Some(u));
}
if bvs_can_be_equal(&solver, bv, &V::ones(solver.clone(), width))? {
if width == 64 {
return Ok(Some(std::u64::MAX));
} else {
return Ok(Some((1 << width) - 1));
}
}
let mut min: u64 = 0;
let mut max: u64 = if width == 64 {
std::u64::MAX
} else {
(1 << width) - 1
};
let mut pushes = 0;
while (max - min) > 1 {
let mid = (min / 2) + (max / 2) + (min % 2 + max % 2) / 2;
let mid = if mid / 2 > min { mid / 2 } else { mid };
solver.push(1);
pushes += 1;
bv.ugte(&V::from_u64(solver.clone(), mid, width)).assert()?;
if sat(&solver)? {
min = mid;
} else {
max = mid;
solver.pop(1);
pushes -= 1;
}
}
solver.pop(pushes);
assert_eq!(max - min, 1);
Ok(Some(min))
}
pub fn min_possible_solution_for_bv_as_u64<V: BV>(
solver: V::SolverRef,
bv: &V,
) -> Result<Option<u64>> {
let width = bv.get_width();
if width > 64 {
panic!("min_possible_solution_for_bv_as_u64 on a BV with width > 64");
}
if !sat(&solver)? {
return Ok(None);
}
if let Some(u) = bv.as_u64() {
return Ok(Some(u));
}
if bvs_can_be_equal(&solver, bv, &V::zero(solver.clone(), width))? {
return Ok(Some(0));
}
let mut min: u64 = 0;
let mut max: u64 = if width == 64 {
std::u64::MAX
} else {
(1 << width) - 1
};
let mut pushes = 0;
while (max - min) > 1 {
let mid = (min / 2) + (max / 2) + (min % 2 + max % 2) / 2;
let mid = if mid / 2 > min { mid / 2 } else { mid };
solver.push(1);
pushes += 1;
bv.ulte(&V::from_u64(solver.clone(), mid, width)).assert()?;
if sat(&solver)? {
max = mid;
} else {
min = mid;
solver.pop(1);
pushes -= 1;
}
}
solver.pop(pushes);
assert_eq!(max - min, 1);
Ok(Some(max))
}
pub fn max_possible_solution_for_bv_as_binary_str<V: BV>(
solver: V::SolverRef,
bv: &V,
) -> Result<Option<String>> {
let mut bv = bv.clone();
let total_width = bv.get_width();
let mut retval = String::with_capacity(total_width as usize);
solver.push(1);
loop {
let width = bv.get_width();
if width <= 64 {
let max_for_remaining_bits =
match max_possible_solution_for_bv_as_u64(solver.clone(), &bv)? {
Some(max) => max,
None => {
solver.pop(1);
return Ok(None);
},
};
retval.push_str(&format!(
"{val:0width$b}",
val = max_for_remaining_bits,
width = width as usize
));
break;
} else {
let top_bit = bv.get_width() - 1;
let high_bits = bv.slice(top_bit, top_bit - 63);
assert_eq!(high_bits.get_width(), 64);
bv = bv.slice(top_bit - 64, 0);
let max_for_high_bits =
match max_possible_solution_for_bv_as_u64(solver.clone(), &high_bits)? {
Some(max) => max,
None => {
solver.pop(1);
return Ok(None);
},
};
retval.push_str(&format!("{:064b}", max_for_high_bits));
high_bits
._eq(&V::from_u64(solver.clone(), max_for_high_bits, 64))
.assert()?;
}
}
solver.pop(1);
assert_eq!(
retval.len(),
total_width as usize,
"Should have a string of {} characters, but have one of {} characters: {:?}",
total_width,
retval.len(),
retval
);
Ok(Some(retval))
}
pub fn min_possible_solution_for_bv_as_binary_str<V: BV>(
solver: V::SolverRef,
bv: &V,
) -> Result<Option<String>> {
let mut bv = bv.clone();
let total_width = bv.get_width();
let mut retval = String::with_capacity(total_width as usize);
solver.push(1);
loop {
let width = bv.get_width();
if width <= 64 {
let min_for_remaining_bits =
match min_possible_solution_for_bv_as_u64(solver.clone(), &bv)? {
Some(max) => max,
None => {
solver.pop(1);
return Ok(None);
},
};
retval.push_str(&format!(
"{val:0width$b}",
val = min_for_remaining_bits,
width = width as usize
));
break;
} else {
let top_bit = bv.get_width() - 1;
let high_bits = bv.slice(top_bit, top_bit - 63);
assert_eq!(high_bits.get_width(), 64);
bv = bv.slice(top_bit - 64, 0);
let min_for_high_bits =
match min_possible_solution_for_bv_as_u64(solver.clone(), &high_bits)? {
Some(min) => min,
None => {
solver.pop(1);
return Ok(None);
},
};
retval.push_str(&format!("{:064b}", min_for_high_bits));
high_bits
._eq(&V::from_u64(solver.clone(), min_for_high_bits, 64))
.assert()?;
}
}
solver.pop(1);
assert_eq!(
retval.len(),
total_width as usize,
"Should have a string of {} characters, but have one of {} characters: {:?}",
total_width,
retval.len(),
retval
);
Ok(Some(retval))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::backend::SolverRef;
use std::rc::Rc;
type BV = <Rc<Btor> as SolverRef>::BV;
#[test]
fn basic_sat() {
let btor = <Rc<Btor> as SolverRef>::new();
assert_eq!(sat(&btor), Ok(true));
BV::from_bool(btor.clone(), true).assert();
assert_eq!(sat(&btor), Ok(true));
let x: BV = BV::new(btor.clone(), 64, Some("x"));
x.sgt(&BV::zero(btor.clone(), 64)).assert();
assert_eq!(sat(&btor), Ok(true));
}
#[test]
fn basic_unsat() {
let btor = <Rc<Btor> as SolverRef>::new();
BV::from_bool(btor.clone(), false).assert();
assert_eq!(sat(&btor), Ok(false));
}
#[test]
fn extra_constraints() {
let btor = <Rc<Btor> as SolverRef>::new();
let x: BV = BV::new(btor.clone(), 64, Some("x"));
x.ugt(&BV::from_u64(btor.clone(), 3, 64)).assert();
assert_eq!(sat(&btor), Ok(true));
let bad_constraint = x.ult(&BV::from_u64(btor.clone(), 3, 64));
assert_eq!(
sat_with_extra_constraints(&btor, std::iter::once(&bad_constraint)),
Ok(false)
);
assert_eq!(sat(&btor), Ok(true));
}
#[test]
fn can_or_must_be_equal() {
let btor = <Rc<Btor> as SolverRef>::new();
let two = BV::from_u64(btor.clone(), 2, 64);
let three = BV::from_u64(btor.clone(), 3, 64);
let four = BV::from_u64(btor.clone(), 4, 64);
let five = BV::from_u64(btor.clone(), 5, 64);
let seven = BV::from_u64(btor.clone(), 7, 64);
let x: BV = BV::new(btor.clone(), 64, Some("x"));
x.ugt(&three).assert();
assert_eq!(bvs_can_be_equal(&btor, &x, &seven), Ok(true));
assert_eq!(bvs_must_be_equal(&btor, &x, &seven), Ok(false));
assert_eq!(bvs_can_be_equal(&btor, &x, &two), Ok(false));
assert_eq!(bvs_must_be_equal(&btor, &x, &two), Ok(false));
x.ult(&five).assert();
assert_eq!(bvs_can_be_equal(&btor, &x, &four), Ok(true));
assert_eq!(bvs_must_be_equal(&btor, &x, &four), Ok(true));
}
#[test]
fn possible_solutions() {
let btor = <Rc<Btor> as SolverRef>::new();
let x: BV = BV::new(btor.clone(), 64, Some("x"));
x.ugt(&BV::from_u64(btor.clone(), 3, 64)).assert();
let num_solutions = get_possible_solutions_for_bv(btor.clone(), &x, 2)
.unwrap()
.count();
assert_eq!(num_solutions, SolutionCount::AtLeast(3));
x.ult(&BV::from_u64(btor.clone(), 6, 64)).assert();
let solutions = get_possible_solutions_for_bv(btor.clone(), &x, 2)
.unwrap()
.as_u64_solutions();
assert_eq!(solutions, Some([4, 5].iter().copied().collect()));
x.ult(&BV::from_u64(btor.clone(), 5, 64)).assert();
let solutions = get_possible_solutions_for_bv(btor.clone(), &x, 2)
.unwrap()
.as_u64_solutions();
assert_eq!(solutions, Some(PossibleSolutions::exactly_one(4)));
x.ult(&BV::from_u64(btor.clone(), 3, 64)).assert();
let solutions = get_possible_solutions_for_bv(btor.clone(), &x, 2)
.unwrap()
.as_u64_solutions();
assert_eq!(solutions, Some(PossibleSolutions::empty()));
}
#[test]
fn min_possible_solution() {
let btor = <Rc<Btor> as SolverRef>::new();
let x: BV = BV::new(btor.clone(), 64, Some("x"));
x.ugt(&BV::from_u64(btor.clone(), 3, 64)).assert();
assert_eq!(
min_possible_solution_for_bv_as_u64(btor.clone(), &x),
Ok(Some(4))
);
x.ult(&BV::from_u64(btor.clone(), 6, 64)).assert();
assert_eq!(
min_possible_solution_for_bv_as_u64(btor.clone(), &x),
Ok(Some(4))
);
x.ult(&BV::from_u64(btor.clone(), 3, 64)).assert();
assert_eq!(
min_possible_solution_for_bv_as_u64(btor.clone(), &x),
Ok(None)
);
}
#[test]
fn max_possible_solution() {
let btor = <Rc<Btor> as SolverRef>::new();
let x: BV = BV::new(btor.clone(), 64, Some("x"));
x.ult(&BV::from_u64(btor.clone(), 7, 64)).assert();
assert_eq!(
max_possible_solution_for_bv_as_u64(btor.clone(), &x),
Ok(Some(6))
);
assert_eq!(
min_possible_solution_for_bv_as_u64(btor.clone(), &x),
Ok(Some(0))
);
x.ugt(&BV::from_u64(btor.clone(), 3, 64)).assert();
assert_eq!(
max_possible_solution_for_bv_as_u64(btor.clone(), &x),
Ok(Some(6))
);
assert_eq!(
min_possible_solution_for_bv_as_u64(btor.clone(), &x),
Ok(Some(4))
);
x.ugt(&BV::from_u64(btor.clone(), 7, 64)).assert();
assert_eq!(
max_possible_solution_for_bv_as_u64(btor.clone(), &x),
Ok(None)
);
}
#[test]
fn min_possible_solution_str() {
let btor = <Rc<Btor> as SolverRef>::new();
let x: BV = BV::new(btor.clone(), 16, Some("x"));
x.ugt(&BV::from_u64(btor.clone(), 3, 16)).assert();
assert_eq!(
min_possible_solution_for_bv_as_binary_str(btor.clone(), &x),
Ok(Some("0000000000000100".into())),
);
let y: BV = BV::new(btor.clone(), 96, Some("y"));
y.ugt(&BV::from_binary_str(btor.clone(), "000100001010000010100001010000010100001010000000100011010000011100001010000000000101000010100010")).assert();
assert_eq!(
min_possible_solution_for_bv_as_binary_str(btor.clone(), &y),
Ok(Some("000100001010000010100001010000010100001010000000100011010000011100001010000000000101000010100011".into())),
);
assert!(bvs_can_be_equal(&btor, &y, &BV::ones(btor.clone(), 96)).unwrap());
}
#[test]
fn min_possible_solution_overflow() {
let btor = <Rc<Btor> as SolverRef>::new();
let x: BV = BV::new(btor.clone(), 64, Some("x"));
let zero = BV::zero(btor.clone(), 64);
x.slt(&zero).assert();
let minustwo = zero.sub(&BV::from_u64(btor.clone(), 2, 64));
x.sgte(&minustwo).assert();
assert_eq!(
min_possible_solution_for_bv_as_u64(btor.clone(), &x),
Ok(Some((-2_i64) as u64))
);
}
#[test]
fn max_possible_solution_overflow() {
let btor = <Rc<Btor> as SolverRef>::new();
let x: BV = BV::new(btor.clone(), 64, Some("x"));
let minustwo = BV::zero(btor.clone(), 64).sub(&BV::from_u64(btor.clone(), 2, 64));
x.slte(&minustwo).assert();
assert_eq!(
max_possible_solution_for_bv_as_u64(btor.clone(), &x),
Ok(Some((-2_i64) as u64))
);
}
}