use crate::bv::Bv;
#[derive(Clone, Debug)]
pub struct Set<const N: u32> {
bits: Bv,
}
impl<const N: u32> Set<N> {
#[must_use]
pub fn empty() -> Self {
Self {
bits: Bv::val(0, N),
}
}
#[must_use]
pub fn full() -> Self {
Self {
bits: Bv::val(u64::MAX, N),
}
}
#[must_use]
pub fn singleton(element: u32) -> Self {
Self::empty().insert_const(element)
}
#[must_use]
pub fn from_bits(bits: Bv) -> Self {
Self { bits }
}
#[must_use]
pub fn bits(&self) -> &Bv {
&self.bits
}
#[must_use]
pub fn universe(&self) -> u32 {
self.bits.width()
}
#[must_use]
pub fn contains(&self, index: &Bv) -> Bv {
self.bits.lshr_var(index).extract(0, 0)
}
#[must_use]
pub fn contains_const(&self, index: u32) -> Bv {
assert!(
index < self.universe(),
"element {index} is outside a {}-element universe",
self.universe()
);
self.bits.extract(index, index)
}
#[must_use]
pub fn insert(&self, index: &Bv) -> Self {
let bit = Bv::val(1, self.universe()).shl_var(index);
Self {
bits: self.bits.or(&bit),
}
}
#[must_use]
pub fn insert_const(&self, index: u32) -> Self {
assert!(
index < self.universe(),
"element {index} is outside a {}-element universe",
self.universe()
);
let bit = Bv::val(1, self.universe()).shl(index);
Self {
bits: self.bits.or(&bit),
}
}
#[must_use]
pub fn remove(&self, index: &Bv) -> Self {
let bit = Bv::val(1, self.universe()).shl_var(index);
Self {
bits: self.bits.and(&bit.not()),
}
}
#[must_use]
pub fn remove_const(&self, index: u32) -> Self {
assert!(
index < self.universe(),
"element {index} is outside a {}-element universe",
self.universe()
);
let bit = Bv::val(1, self.universe()).shl(index);
Self {
bits: self.bits.and(&bit.not()),
}
}
#[must_use]
pub fn insert_if(&self, when: &Bv, index: &Bv) -> Self {
assert_eq!(when.width(), 1, "the condition must be 1 bit");
let bit = Bv::val(1, self.universe()).shl_var(index);
let mask = Bv::ite(when, &bit, &Bv::val(0, self.universe()));
Self {
bits: self.bits.or(&mask),
}
}
#[must_use]
pub fn union(&self, other: &Self) -> Self {
Self {
bits: self.bits.or(&other.bits),
}
}
#[must_use]
pub fn intersection(&self, other: &Self) -> Self {
Self {
bits: self.bits.and(&other.bits),
}
}
#[must_use]
pub fn difference(&self, other: &Self) -> Self {
Self {
bits: self.bits.and(&other.bits.not()),
}
}
#[must_use]
pub fn symmetric_difference(&self, other: &Self) -> Self {
Self {
bits: self.bits.xor(&other.bits),
}
}
#[must_use]
pub fn complement(&self) -> Self {
Self {
bits: self.bits.not(),
}
}
#[must_use]
pub fn is_subset(&self, other: &Self) -> Bv {
self.difference(other).is_empty()
}
#[must_use]
pub fn same(&self, other: &Self) -> Bv {
self.bits.eq(&other.bits)
}
#[must_use]
pub fn is_empty(&self) -> Bv {
self.bits.eq(&Bv::val(0, self.universe()))
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{Solution, Solver};
fn subsets() -> impl Iterator<Item = u64> {
0u64..16
}
fn set(mask: u64) -> Set<4> {
Set::from_bits(Bv::val(mask, 4))
}
fn assert_bits(actual: &Bv, want: u64, label: &str) {
let mut s = Solver::new();
s.assert(actual.eq(&Bv::val(want, actual.width())));
assert!(
matches!(s.check(), Solution::Sat(_)),
"{label}: expected {want:#x}, term is not that constant"
);
}
#[test]
fn set_algebra_matches_bitmask_algebra_exhaustively() {
for a in subsets() {
for b in subsets() {
let (sa, sb) = (set(a), set(b));
let cases: [(&str, u64, Bv); 6] = [
("union", a | b, sa.union(&sb).bits().clone()),
("intersection", a & b, sa.intersection(&sb).bits().clone()),
("difference", a & !b, sa.difference(&sb).bits().clone()),
(
"symmetric",
a ^ b,
sa.symmetric_difference(&sb).bits().clone(),
),
("complement", !a & 0xf, sa.complement().bits().clone()),
("same", u64::from(a == b), sa.same(&sb)),
];
for (label, want, got) in cases {
let mut s = Solver::new();
s.assert(got.eq(&Bv::val(want, got.width())));
assert!(
matches!(s.check(), Solution::Sat(_)),
"{label}: a={a:#x} b={b:#x} differs from the bitmask answer"
);
}
let mut s = Solver::new();
let want = u64::from(a & !b == 0);
s.assert(sa.is_subset(&sb).eq(&Bv::val(want, 1)));
assert!(
matches!(s.check(), Solution::Sat(_)),
"subset: a={a:#x} b={b:#x}"
);
}
for e in 0u32..4 {
let mut s = Solver::new();
s.assert(set(a).contains_const(e).eq(&Bv::val((a >> e) & 1, 1)));
assert!(matches!(s.check(), Solution::Sat(_)));
}
}
}
#[test]
fn insert_and_remove_const_match_the_mask() {
for a in subsets() {
for e in 0u32..4 {
assert_bits(
set(a).insert_const(e).bits(),
a | 1 << e,
&format!("insert {e} into {a:#x}"),
);
assert_bits(
set(a).remove_const(e).bits(),
a & !(1 << e),
&format!("remove {e} from {a:#x}"),
);
}
}
}
#[test]
fn a_symbolic_index_behaves_like_the_constant_it_takes() {
for a in subsets() {
for e in 0u32..5 {
let mut s = Solver::new();
let i = s.var("i", 3);
s.assert(i.eq(&Bv::val(u64::from(e), 3)));
let sa = set(a);
let want = if e < 4 { (a >> e) & 1 } else { 0 };
s.assert(sa.contains(&i).eq(&Bv::val(want, 1)));
let inserted = if e < 4 { a | 1 << e } else { a };
s.assert(sa.insert(&i).bits().eq(&Bv::val(inserted, 4)));
let removed = if e < 4 { a & !(1 << e) } else { a };
s.assert(sa.remove(&i).bits().eq(&Bv::val(removed, 4)));
assert!(matches!(s.check(), Solution::Sat(_)), "a={a:#x} e={e}");
}
}
}
#[test]
fn singleton_full_and_empty() {
assert_bits(Set::<4>::singleton(2).bits(), 4, "singleton 2");
assert_bits(Set::<4>::full().bits(), 0xf, "full");
assert_bits(Set::<4>::empty().bits(), 0, "empty");
let mut s = Solver::new();
s.assert(Set::<4>::empty().is_empty().eq(&Bv::val(1, 1)));
s.assert(Set::<4>::singleton(1).is_empty().eq(&Bv::val(0, 1)));
s.assert(
Set::<4>::full()
.is_subset(&Set::<4>::full())
.eq(&Bv::val(1, 1)),
);
assert!(matches!(s.check(), Solution::Sat(_)));
}
}