use std::cell::RefCell;
use std::collections::HashMap;
use std::fmt;
use std::rc::Rc;
use crate::Solver;
use crate::bv::Bv;
use crate::theory::{ModelView, Theory};
#[derive(Clone)]
enum Node {
Base {
constant: Option<Bv>,
index_width: u32,
elem_width: u32,
},
Store { parent: usize, index: Bv, value: Bv },
}
struct Select {
array: usize,
index: Bv,
result: Bv,
parent: Option<Bv>,
}
struct Inner {
nodes: RefCell<Vec<Node>>,
by_key: RefCell<HashMap<(usize, usize), usize>>,
store_key: RefCell<HashMap<(usize, usize, usize), usize>>,
selects: RefCell<Vec<Select>>,
}
impl fmt::Debug for Inner {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("ArrayTheory")
.field("arrays", &self.nodes.borrow().len())
.field("selects", &self.selects.borrow().len())
.finish()
}
}
impl Inner {
fn base(&self, constant: Option<Bv>, index_width: u32, elem_width: u32) -> usize {
let mut nodes = self.nodes.borrow_mut();
nodes.push(Node::Base {
constant,
index_width,
elem_width,
});
nodes.len() - 1
}
fn push_select(&self, array: usize, index: Bv, result: Bv, parent: Option<Bv>) -> usize {
let key = (array, index.ptr_key());
let i = {
let mut selects = self.selects.borrow_mut();
selects.push(Select {
array,
index,
result,
parent,
});
selects.len() - 1
};
self.by_key.borrow_mut().insert(key, i);
i
}
}
#[derive(Clone, Debug)]
pub struct ArrayTheory {
inner: Rc<Inner>,
}
impl Default for ArrayTheory {
fn default() -> Self {
Self::new()
}
}
impl ArrayTheory {
#[must_use]
pub fn new() -> Self {
Self {
inner: Rc::new(Inner {
nodes: RefCell::new(Vec::new()),
by_key: RefCell::new(HashMap::new()),
store_key: RefCell::new(HashMap::new()),
selects: RefCell::new(Vec::new()),
}),
}
}
#[must_use]
pub fn var(&self, _solver: &mut Solver, index_width: u32, elem_width: u32) -> Array {
assert!(
(1..=128).contains(&index_width),
"array index width must be 1..=128, got {index_width}"
);
assert!(
(1..=128).contains(&elem_width),
"array element width must be 1..=128, got {elem_width}"
);
let id = self.inner.base(None, index_width, elem_width);
Array {
inner: Rc::clone(&self.inner),
id,
}
}
#[must_use]
pub fn constant(&self, element: &Bv, index_width: u32) -> Array {
assert!(
(1..=128).contains(&index_width),
"array index width must be 1..=128, got {index_width}"
);
let id = self
.inner
.base(Some(element.clone()), index_width, element.width());
Array {
inner: Rc::clone(&self.inner),
id,
}
}
#[must_use]
pub fn arrays(&self) -> usize {
self.inner.nodes.borrow().len()
}
#[must_use]
pub fn selects(&self) -> usize {
self.inner.selects.borrow().len()
}
}
#[derive(Clone, Debug)]
pub struct Array {
inner: Rc<Inner>,
id: usize,
}
impl Array {
#[must_use]
pub fn shape(&self) -> (u32, u32) {
match &self.inner.nodes.borrow()[self.id] {
Node::Base {
index_width,
elem_width,
..
} => (*index_width, *elem_width),
Node::Store { parent, .. } => {
let shape = &self.inner.nodes.borrow()[*parent];
match shape {
Node::Base {
index_width,
elem_width,
..
} => (*index_width, *elem_width),
Node::Store { .. } => Array {
inner: Rc::clone(&self.inner),
id: *parent,
}
.shape(),
}
}
}
}
pub fn select(&self, solver: &mut Solver, index: &Bv) -> Bv {
let (iw, _) = self.shape();
assert_eq!(
index.width(),
iw,
"select index must be {iw} bits, got {}",
index.width()
);
self.select_at(solver, self.id, index)
}
fn select_at(&self, solver: &mut Solver, array: usize, index: &Bv) -> Bv {
let key = (array, index.ptr_key());
if let Some(&i) = self.inner.by_key.borrow().get(&key) {
return self.inner.selects.borrow()[i].result.clone();
}
match self.inner.nodes.borrow()[array].clone() {
Node::Base {
constant: Some(c), ..
} => c,
Node::Base {
constant: None,
elem_width,
..
} => {
let n = self.inner.selects.borrow().len();
let result = solver.var(&format!("arr#{array}[{n}]"), elem_width);
self.inner
.push_select(array, index.clone(), result.clone(), None);
result
}
Node::Store {
parent,
index: stored,
value,
} => {
if stored.ptr_eq(index) {
return value;
}
let parent_sel = self.select_at(solver, parent, index);
let n = self.inner.selects.borrow().len();
let result = solver.var(&format!("arr#{array}[{n}]"), value.width());
self.inner
.push_select(array, index.clone(), result.clone(), Some(parent_sel));
result
}
}
}
pub fn store(&self, _solver: &mut Solver, index: &Bv, value: &Bv) -> Array {
let (iw, ew) = self.shape();
assert_eq!(
index.width(),
iw,
"store index must be {iw} bits, got {}",
index.width()
);
assert_eq!(
value.width(),
ew,
"stored value must be {ew} bits, got {}",
value.width()
);
let key = (self.id, index.ptr_key(), value.ptr_key());
if let Some(&id) = self.inner.store_key.borrow().get(&key) {
return Array {
inner: Rc::clone(&self.inner),
id,
};
}
let id = {
let mut nodes = self.inner.nodes.borrow_mut();
nodes.push(Node::Store {
parent: self.id,
index: index.clone(),
value: value.clone(),
});
nodes.len() - 1
};
self.inner.store_key.borrow_mut().insert(key, id);
Array {
inner: Rc::clone(&self.inner),
id,
}
}
}
impl Theory for ArrayTheory {
fn name(&self) -> &'static str {
"arrays"
}
fn violated_lemmas(&self, model: &ModelView<'_>) -> Vec<Bv> {
let nodes = self.inner.nodes.borrow();
let selects = self.inner.selects.borrow();
let mut out = Vec::new();
for s in selects.iter() {
let Node::Store {
index: stored,
value,
..
} = &nodes[s.array]
else {
continue;
};
let (Some(sv), Some(iv)) = (model.eval128(stored), model.eval128(&s.index)) else {
continue;
};
if sv == iv {
if model.eval128(&s.result) != model.eval128(value) {
out.push(stored.eq(&s.index).implies(&s.result.eq(value)));
}
} else if let Some(parent) = &s.parent {
if model.eval128(&s.result) != model.eval128(parent) {
out.push(stored.ne(&s.index).implies(&s.result.eq(parent)));
}
}
}
for i in 0..selects.len() {
if !matches!(nodes[selects[i].array], Node::Base { constant: None, .. }) {
continue;
}
for j in (i + 1)..selects.len() {
if selects[j].array != selects[i].array {
continue;
}
let (Some(a), Some(b)) = (
model.eval128(&selects[i].index),
model.eval128(&selects[j].index),
) else {
continue;
};
if a != b {
continue;
}
let results_differ = match (
model.eval128(&selects[i].result),
model.eval128(&selects[j].result),
) {
(Some(x), Some(y)) => x != y,
_ => false,
};
if results_differ {
out.push(
selects[i]
.index
.eq(&selects[j].index)
.implies(&selects[i].result.eq(&selects[j].result)),
);
}
}
}
out
}
fn eager_lemmas(&self) -> Vec<Bv> {
let nodes = self.inner.nodes.borrow();
let selects = self.inner.selects.borrow();
let mut out = Vec::new();
for s in selects.iter() {
match &nodes[s.array] {
Node::Store {
index: stored,
value,
..
} => {
out.push(stored.eq(&s.index).implies(&s.result.eq(value)));
if let Some(parent) = &s.parent {
out.push(stored.ne(&s.index).implies(&s.result.eq(parent)));
}
}
Node::Base { .. } => {}
}
}
for i in 0..selects.len() {
if !matches!(nodes[selects[i].array], Node::Base { constant: None, .. }) {
continue;
}
for j in (i + 1)..selects.len() {
if selects[j].array != selects[i].array {
continue;
}
out.push(
selects[i]
.index
.eq(&selects[j].index)
.implies(&selects[i].result.eq(&selects[j].result)),
);
}
}
out
}
}