Expand description
smtlite - a small, pure-Rust QF_BV SMT solver.
Quantifier-free bitvector formulas only: build expressions with Solver::var and the
Bv combinators, Solver::assert the 1-bit constraints, and call Solver::check.
A satisfying answer comes back as a Model you can read concrete values out of; the
alternative answers are Unsat and a budget-limited Unknown, and the three are kept
distinct so a caller can tell a proof from a timeout (Solution).
It is scoped to directed queries - “is there an input that makes this operation overflow?”, “can this length reach that copy?” - asked many times over, rather than to general theorem proving. See the README for what that costs and what it rules out.
Under the hood the expression DAG is bit-blasted to CNF and solved by a self-contained
DPLL core. There is no external solver, no C, and no unsafe; bumpalo is the only
dependency, and it is an allocator.
use smtlite::{Bv, Solution, Solver};
let mut s = Solver::new();
let x = s.var("x", 64);
s.assert(x.add(&Bv::val(3, 64)).eq(&Bv::val(10, 64))); // x + 3 == 10
match s.check() {
Solution::Sat(m) => assert_eq!(m.get("x"), Some(7)),
other => panic!("expected SAT, got {other:?}"),
}§Bounded by construction
Three bounds, any of which yields Solution::Unknown rather than a wrong verdict:
Solver::check_with_budget caps decisions, Solver::check_all_within adds a
wall-clock deadline, and Solver::with_max_clauses caps the formula size. The bounds are
best-effort - checked periodically, not preemptively, so they bound the work rather than the
latency to the microsecond - but they cover the whole query, from API entry to return: the
deadline and the clause cap govern the bit-blast that produces the CNF, not only the search
over it.
§Width and threading limits
Widths are 1..=128 bits. Model::get reads a variable back as a u64, so a value wider
than 64 bits reads back through Model::get128 instead. An operation whose result or
target width would fall outside 1..=128 panics, as does one given two operands of
different widths; each such method says so under # Panics.
A Bv is an Rc-shared node, so neither Bv nor Solver is Send or Sync - one
solve runs on one thread.
Re-exports§
pub use set::Set;pub use theory::Array;pub use theory::ArrayTheory;pub use theory::ModelView;pub use theory::Theory;pub use theory::Uninterpreted;
Modules§
- field
- Finite-field arithmetic over a prime modulus, encoded as bit-vectors.
- set
- Finite sets of at most 64 elements, lowered to one bitvector.
- theory
- The theory layer: lemmas over the blasted bitvector core.
Structs§
- Bv
- A bitvector value: a handle onto a shared expression node.
- Model
- A satisfying assignment, queryable by variable name.
- Solver
- The SMT context: named bitvector variables and asserted constraints.
Enums§
- Solution
- The answer to a satisfiability query, three-valued.
Constants§
- DEFAULT_
BUDGET - Default decision budget before a query degrades to
Solution::Unknown.
Functions§
- mask
- Truncate
vto its lowwbits.wat or above 64 leavesvunchanged, since there are no more bits to drop.