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, Debug)]
struct App {
args: Vec<Bv>,
result: Bv,
}
struct Inner {
name: &'static str,
arg_widths: Vec<u32>,
result_width: u32,
apps: RefCell<Vec<App>>,
by_args: RefCell<HashMap<Vec<usize>, usize>>,
}
impl fmt::Debug for Inner {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Uninterpreted")
.field("name", &self.name)
.field("arg_widths", &self.arg_widths)
.field("result_width", &self.result_width)
.field("applications", &self.apps.borrow().len())
.field("distinct_argument_tuples", &self.by_args.borrow().len())
.finish()
}
}
#[derive(Clone, Debug)]
pub struct Uninterpreted {
inner: Rc<Inner>,
}
impl Uninterpreted {
#[must_use]
pub fn new(name: &'static str, arg_widths: &[u32], result_width: u32) -> Self {
assert!(!name.is_empty(), "an uninterpreted function needs a name");
for &w in arg_widths {
assert!(
(1..=64).contains(&w),
"argument width must be 1..=64, got {w}"
);
}
assert!(
(1..=64).contains(&result_width),
"result width must be 1..=64, got {result_width}"
);
Self {
inner: Rc::new(Inner {
name,
arg_widths: arg_widths.to_vec(),
result_width,
apps: RefCell::new(Vec::new()),
by_args: RefCell::new(HashMap::new()),
}),
}
}
#[must_use]
pub fn name(&self) -> &'static str {
self.inner.name
}
pub fn apply(&self, solver: &mut Solver, args: &[Bv]) -> Bv {
assert_eq!(
args.len(),
self.inner.arg_widths.len(),
"`{}` takes {} argument(s), got {}",
self.inner.name,
self.inner.arg_widths.len(),
args.len()
);
for (k, (arg, &want)) in args.iter().zip(&self.inner.arg_widths).enumerate() {
assert_eq!(
arg.width(),
want,
"`{}` argument {k} must be {want} bits, got {}",
self.inner.name,
arg.width()
);
}
let key: Vec<usize> = args.iter().map(Bv::ptr_key).collect();
if let Some(&i) = self.inner.by_args.borrow().get(&key) {
return self.inner.apps.borrow()[i].result.clone();
}
let result = solver.var(
&format!("uf:{}#{}", self.inner.name, self.inner.apps.borrow().len()),
self.inner.result_width,
);
let i = {
let mut apps = self.inner.apps.borrow_mut();
apps.push(App {
args: args.to_vec(),
result: result.clone(),
});
apps.len() - 1
};
self.inner.by_args.borrow_mut().insert(key, i);
result
}
#[must_use]
pub fn len(&self) -> usize {
self.inner.apps.borrow().len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
fn congruence(&self, apps: &[App], i: usize, j: usize) -> Bv {
let (a, b) = (&apps[i], &apps[j]);
debug_assert_eq!(a.args.len(), b.args.len());
let mut antecedent: Option<Bv> = None;
for (x, y) in a.args.iter().zip(&b.args) {
let eq = x.eq(y);
antecedent = Some(match antecedent {
None => eq,
Some(acc) => acc.land(&eq),
});
}
let consequent = a.result.eq(&b.result);
match antecedent {
None => consequent,
Some(a) => a.implies(&consequent),
}
}
}
impl Theory for Uninterpreted {
fn name(&self) -> &'static str {
self.inner.name
}
fn violated_lemmas(&self, model: &ModelView<'_>) -> Vec<Bv> {
let apps = self.inner.apps.borrow();
let mut out = Vec::new();
for i in 0..apps.len() {
for j in (i + 1)..apps.len() {
let args_equal = apps[i].args.iter().zip(&apps[j].args).all(|(x, y)| {
match (model.eval(x), model.eval(y)) {
(Some(xv), Some(yv)) => xv == yv,
_ => false,
}
});
if !args_equal {
continue;
}
let results_differ =
match (model.eval(&apps[i].result), model.eval(&apps[j].result)) {
(Some(xv), Some(yv)) => xv != yv,
_ => false,
};
if results_differ {
out.push(self.congruence(&apps, i, j));
}
}
}
out
}
fn eager_lemmas(&self) -> Vec<Bv> {
let apps = self.inner.apps.borrow();
let mut out = Vec::new();
for i in 0..apps.len() {
for j in (i + 1)..apps.len() {
out.push(self.congruence(&apps, i, j));
}
}
out
}
}