pub mod enc;
mod ranges;
pub mod rup;
pub mod sat;
use crate::verify::term::{COp, Term};
use crate::verify::ty::Ty;
use ranges::Ranges;
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Answer {
Valid,
Candidate(Vec<(String, i128)>),
Unknown(String),
}
pub const MAX_WIDTH: usize = 192;
pub const BUDGET: u64 = 30_000;
fn conjuncts<'t>(t: &'t Term, out: &mut Vec<&'t Term>) {
match t {
Term::And(a, b) => {
conjuncts(a, out);
conjuncts(b, out);
}
other => out.push(other),
}
}
pub(crate) fn stated_bounds(hyps: &[Term]) -> HashMap<Term, (i128, i128)> {
let mut out: HashMap<Term, (i128, i128)> = HashMap::new();
let mut cs = Vec::new();
for h in hyps {
conjuncts(h, &mut cs);
}
for c in cs {
let Term::Cmp(op, a, b) = c else { continue };
let (t, k, op) = match (&**a, &**b) {
(t @ (Term::App(..) | Term::Var(..)), Term::Int(k)) => (t, *k, *op),
(Term::Int(k), t @ (Term::App(..) | Term::Var(..))) => (
t,
*k,
match op {
COp::Lt => COp::Gt,
COp::Le => COp::Ge,
COp::Gt => COp::Lt,
COp::Ge => COp::Le,
o => *o,
},
),
_ => continue,
};
let e = out.entry(t.clone()).or_insert((i128::MIN, i128::MAX));
match op {
COp::Ge => e.0 = e.0.max(k),
COp::Gt => e.0 = e.0.max(k.saturating_add(1)),
COp::Le => e.1 = e.1.min(k),
COp::Lt => e.1 = e.1.min(k.saturating_sub(1)),
COp::Eq => {
e.0 = e.0.max(k);
e.1 = e.1.min(k);
}
COp::Ne => {}
}
}
out
}
fn bits_for(v: i128) -> usize {
let m = if v < 0 { !v } else { v };
(128 - m.leading_zeros() as usize) + 1
}
pub fn decide(hyps: &[Term], goal: &Term, plant_drop_carry: bool) -> Answer {
let mut ranges = Ranges {
stated: stated_bounds(hyps),
memo: HashMap::new(),
atoms: HashMap::new(),
max_ty_bits: 1,
products: HashMap::new(),
};
for t in hyps.iter().chain(std::iter::once(goal)) {
if let Err(why) = ranges.boolean(t) {
return Answer::Unknown(why);
}
}
let need = ranges
.memo
.values()
.map(|r| bits_for(r.0).max(bits_for(r.1)))
.max()
.unwrap_or(1)
.max(ranges.max_ty_bits as usize + 1);
let w = need + 2;
if w > MAX_WIDTH {
return Answer::Unknown(format!("needs {w}-bit vectors (limit {MAX_WIDTH})"));
}
let mut e = enc::Enc::new(w);
e.plant_drop_carry = plant_drop_carry;
if !e.self_check() {
return Answer::Unknown("the encoder failed its self-check".into());
}
e.bounds = std::mem::take(&mut ranges.atoms);
for (t, (lo, hi)) in &ranges.products {
let b = Term::And(
Box::new(Term::Cmp(
COp::Ge,
Box::new(t.clone()),
Box::new(Term::Int(*lo)),
)),
Box::new(Term::Cmp(
COp::Le,
Box::new(t.clone()),
Box::new(Term::Int(*hi)),
)),
);
match e.boolean(&b) {
Ok(l) => e.s.add(vec![l]),
Err(why) => return Answer::Unknown(why),
}
}
for h in hyps {
match e.boolean(h) {
Ok(l) => e.s.add(vec![l]),
Err(why) => return Answer::Unknown(why),
}
}
match e.boolean(goal) {
Ok(l) => e.s.add(vec![sat::neg(l)]),
Err(why) => return Answer::Unknown(why),
}
let original = e.s.clauses.clone();
let nvars = e.s.num_vars();
match e.s.solve(BUDGET) {
sat::Answer::Unsat => {
if rup::check(&original, &e.s.learned, nvars, 400_000_000) {
Answer::Valid
} else {
Answer::Unknown("the UNSAT answer did not replay".into())
}
}
sat::Answer::Sat(model) => {
let mut out = Vec::new();
for (t, v) in &e.int_atoms {
if let Term::Var(n, _) = t {
out.push((n.clone(), e.read(v, &model)));
}
}
for (t, l) in &e.bool_atoms {
if let Term::Var(n, Ty::Bool) = t {
out.push((n.clone(), e.bit(*l, &model) as i128));
}
}
Answer::Candidate(out)
}
sat::Answer::Unknown => Answer::Unknown(format!("no answer in {BUDGET} conflicts")),
}
}
#[cfg(test)]
mod tests;