Skip to main content

Crate smtlite

Crate smtlite 

Source
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 v to its low w bits. w at or above 64 leaves v unchanged, since there are no more bits to drop.