smtlite
A small, pure-Rust QF_BV SMT solver - quantifier-free bitvector formulas, solved by bit-blasting to CNF and running a self-contained DPLL core over it.
No external solver. No C. No unsafe. One dependency (bumpalo, an arena allocator).
It exists for one job: answering directed, single-function queries - "is there an input that makes this operation overflow?", "can this length field reach that copy?" - fast enough to sit inside a symbolic executor that asks thousands of them. It is deliberately not a general-purpose Z3 replacement.
use ;
let mut s = new;
let x = s.var;
s.assert; // x + 3 == 10
match s.check
What it does
- Bitvector variables of any width from 1 to 64 bits, plus constants.
- Boolean:
and,or,xor,not,land(logical and of two 1-bit values). - Arithmetic:
add,sub,mul,neg- all wraparound, as bitvectors are. - Division and remainder: unsigned
udiv/uremand signedsdiv/srem, with the SMT-LIB zero-divisor semantics -bvudivby zero is all-ones,bvuremby zero is the dividend,bvsdivby zero is all-ones for a non-negative dividend and1otherwise.sremtakes the sign of the dividend (C's%), not the divisor's asbvsmodwould. - Shifts:
shl,lshr,ashrby a constant amount, andshl_var,lshr_var,ashr_varby a symbolic one. Shifting at or past the width empties the value (zero-fill, or sign-fill forashr_var) - a shift is not a rotate. - Rotates:
rotl/rotrby a constant androtl_var/rotr_varby a symbolic amount. A rotate is a bit permutation, so it costs no gates at all and never empties the value. - Comparison:
eq,ne,ult,ule,ugt,uge,slt,sle,sgt,sge- each yields a 1-bit value you can feed into other operations. - Width:
zext,sext,extract(hi, lo),concat. ite(cond, then, else).- A model back out:
Model::get(name)returns the concreteu64a variable took, orNoneif no variable by that name was ever declared.
Solver::depends_on(&bv, "mem") answers a question a caller asks constantly - did this value
actually derive from the data read out of the input, or is it still something the caller started
with? Name variables by origin (mem..., init_...) and the prefix tells you which.
What it deliberately does not do
- Arrays, uninterpreted functions, or quantifiers. This is QF_BV only.
bvsmod, whose remainder takes the sign of the divisor.sremgives C's%, which is what compiled code actually emits.- Overflow-detection builtins (
bvuaddo,bvsaddo, ...). Derive them from the primitives:x.add(&y).ult(&x)is the unsigned-add overflow test. - Widths above 64 bits - a model is read back as a
u64, so 64 is the ceiling. It is enforced, not merely documented: building a value wider than that, or combining two of different widths, panics rather than quietly blasting the wrong bits. Every method whose inputs have to satisfy something says so under# Panics. - An SMT-LIB front-end. The name invites the assumption; the API is Rust only, there is no textual parser and no solver-on-a-pipe protocol.
Formulas are also single-threaded: a Bv is an Rc-shared node, so neither Bv nor Solver
is Send/Sync.
Cost
Bit-blasting is where the formula size lives, and it is not uniform across operations:
Operation (at width w) |
Rough cost |
|---|---|
| constant rotate | free - pure re-indexing, no gates, no clauses |
| bitwise, constant shifts, extend/extract/concat | O(w) literals |
add/sub, comparisons, ite |
O(w) gates, 2-4 clauses each |
mul |
O(w²) |
| symbolic shift | O(w log w) - a barrel shifter |
div/rem |
O(w²), a restoring divider |
So every operation at 32 bits lands under the default clause cap, but a 64-bit division reaches ~110,000 clauses and needs the cap raised deliberately - see below. A symbolic rotate at a power-of-two width never divides (the low bits of the amount already are the amount modulo the width); at any other width it needs a divider as wide as its amount, so a 64-bit amount against a 5-bit vector is the expensive combination, while a 5-bit amount is trivial.
How it works
Bv values form an Rc-shared expression DAG; a value used twice is one subgraph, not two. On
check, the DAG is bit-blasted - each bit of each node becomes a SAT literal, operations encoded
through Tseitin gates, arithmetic through ripple-carry adders, unsigned comparison through the
carry-out of a + ¬b + 1, division through a restoring divider (whose per-step adder yields the
subtraction and the rem >= b test in one pass), and symbolic shifts and rotates through barrel
shifters. Bitvectors are little-endian (index 0 is the least-significant bit). Shared subgraphs are
memoised on the Rc pointer, so a value appearing in several constraints is encoded once.
CNF clauses are arena-allocated (bumpalo): a query produces thousands of tiny, same-lifetime
clauses, so one arena reset frees the whole formula instead of freeing clause-by-clause.
The SAT core is iterative DPLL - unit propagation to a fixpoint, then chronological branch-and-flip backtracking. Correctness is preferred over raw speed, because the formulas a directed query produces are small - hundreds to a few thousand clauses, with division the notable exception (see Cost above).
Bounded by construction
A solver embedded in a batch job must never hang it. Three guards, all of which degrade to
Solution::Unknown - "not proven either way" - rather than stalling:
- a decision budget (
check_with_budget,check_all_with_budget), - a wall-clock deadline (
check_all_within), because a propagation-heavy formula can burn seconds between decisions, making a decision count a poor time proxy, - a formula-size cap (40,000 clauses by default): past that the instance is pathological and is
better left to a manual walk-through than allowed to stall a sweep. Every operation at 32 bits
fits under it; raise it with
Solver::with_max_clausesfor a 64-bit division, and pair that with a deadline.
Solution::Unknown is never a silent "unsat" - the three outcomes stay distinct so a caller can
tell a refutation from a timeout.
Requirements
- Rust 1.85 or newer (the 2024 edition).
- No Cargo features - the crate has a single dependency and no optional parts.
- No
unsafe(unsafe_code = "forbid") and no build script.
Licence
Apache-2.0. See LICENSE.