smtlite 0.1.0

A small, pure-Rust QF_BV SMT solver: bitvector expressions bit-blasted to CNF and solved by a self-contained DPLL core.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
//! 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.
//!
//! # Width and threading limits
//!
//! Widths are 1..=64 bits, because [`Model::get`] reads a variable back as a `u64`. An
//! operation whose result or target width would fall outside 1..=64 **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.
#![cfg_attr(doctest, doc = include_str!("../README.md"))]

mod blast;
mod bv;
mod sat;

use std::collections::HashMap;

pub use bv::{Bv, mask};

use blast::Blaster;
use bv::Node;
use sat::SatResult::{Sat, Unknown, Unsat};

/// Default decision budget before a query degrades to [`Solution::Unknown`].
const DEFAULT_BUDGET: u64 = 4_000_000;

/// Default formula-size cap: a blasted formula larger than this is [`Solution::Unknown`] without
/// being solved at all.
///
/// `propagate` rescans every clause per fixpoint, so a huge circuit can burn minutes at a low
/// *decision* count. Every operation at 32 bits fits; a **64-bit division needs roughly
/// 110,000 clauses**, so a caller that needs one raises the cap via
/// [`Solver::with_max_clauses`].
const DEFAULT_MAX_CLAUSES: usize = 40_000;

/// The answer to a satisfiability query, three-valued.
///
/// The distinction that matters is [`Unknown`](Solution::Unknown) against the other two: `Sat`
/// and `Unsat` are verdicts about the formula, while `Unknown` says only that a configured
/// bound was reached first. Nothing may treat `Unknown` as "no solution exists" - it is the
/// absence of an answer, not a negative one.
#[derive(Debug)]
pub enum Solution {
    /// Satisfiable. The [`Model`] holds a concrete assignment under which every asserted
    /// constraint holds simultaneously.
    Sat(Model),
    /// Unsatisfiable - no assignment satisfies the constraints, proven within the bounds.
    Unsat,
    /// No verdict: the decision budget, the wall-clock deadline, or the clause cap was reached
    /// before the search finished.
    ///
    /// There is no partial model to salvage. Raise the bound that was hit
    /// ([`Solver::check_with_budget`], [`Solver::check_all_within`],
    /// [`Solver::with_max_clauses`]) and ask again, or treat the query as unresolved.
    Unknown,
}

/// The SMT context: named bitvector variables and asserted constraints.
#[derive(Debug)]
pub struct Solver {
    vars: Vec<(String, u32)>,
    asserts: Vec<Bv>,
    max_clauses: usize,
}

impl Default for Solver {
    fn default() -> Self {
        Self {
            vars: Vec::new(),
            asserts: Vec::new(),
            max_clauses: DEFAULT_MAX_CLAUSES,
        }
    }
}

impl Solver {
    /// An empty solver: no variables, no constraints.
    ///
    /// ```
    /// use smtlite::Solver;
    ///
    /// let mut s = Solver::new();
    /// let x = s.var("x", 32);
    /// assert_eq!(x.width(), 32);
    /// ```
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// Raise (or lower) the formula-size cap above which a query becomes [`Solution::Unknown`]
    /// without being solved - see `DEFAULT_MAX_CLAUSES`. The default fits every operation at 32
    /// bits; a 64-bit division needs roughly 110,000 clauses, and such a query should be paired
    /// with a wall-clock deadline via [`check_all_within`](Self::check_all_within).
    #[must_use]
    pub fn with_max_clauses(mut self, n: usize) -> Self {
        self.max_clauses = n;
        self
    }

    /// A fresh `width`-bit symbolic variable.
    ///
    /// The name is a label for [`Model::get`] readback and
    /// [`depends_on`](Self::depends_on) prefix matching, not an identity: reusing a name
    /// creates an independent variable that merely reads back under the same key.
    ///
    /// # Panics
    ///
    /// Panics unless `width` is 1..=64. A model is read back through a `u64`, so every width
    /// in the crate is bounded by that; a wider variable would be unreadable and could not
    /// hold a constant.
    pub fn var(&mut self, name: &str, width: u32) -> Bv {
        assert!(
            (1..=64).contains(&width),
            "variable width must be 1..=64, got {width}"
        );
        let id = self.vars.len();
        self.vars.push((name.to_string(), width));
        Bv::wrap(Node::Var(width, id))
    }

    /// Does `bv` reference any variable whose name starts with `prefix`?
    ///
    /// This is how a caller tells where a value came from without threading provenance
    /// through every operation: name the variables by origin - one prefix for data read from
    /// outside, another for values the caller started with - and ask which of them a
    /// subexpression actually depends on. Use [`ptr_eq`](Bv::ptr_eq) to ask whether two
    /// handles are the *same* value.
    ///
    /// ```
    /// use smtlite::{Bv, Solver};
    ///
    /// let mut s = Solver::new();
    /// let len = s.var("hdr.len", 16);
    /// let base = s.var("init.base", 16);
    ///
    /// assert!(s.depends_on(&len.add(&Bv::val(1, 16)), "hdr."));
    /// assert!(!s.depends_on(&base, "hdr."));
    /// ```
    #[must_use]
    pub fn depends_on(&self, bv: &Bv, prefix: &str) -> bool {
        bv.var_ids().into_iter().any(|id| {
            self.vars
                .get(id)
                .is_some_and(|(n, _)| n.starts_with(prefix))
        })
    }

    /// Assert that a 1-bit constraint must hold.
    ///
    /// Constraints accumulate; the next solve has to satisfy all of them at once. A
    /// contradiction between two of them is a legitimate way to get [`Solution::Unsat`], not
    /// an error.
    ///
    /// ```
    /// use smtlite::{Bv, Solution, Solver};
    ///
    /// let mut s = Solver::new();
    /// let x = s.var("x", 8);
    /// s.assert(x.eq(&Bv::val(0, 8)));
    /// s.assert(x.eq(&Bv::val(1, 8))); // contradicts the line above
    /// assert!(matches!(s.check(), Solution::Unsat));
    /// ```
    ///
    /// # Panics
    ///
    /// Panics if `constraint` is not 1 bit wide. A multi-bit value is not a proposition;
    /// blasting one bit of it would answer a question the caller did not ask.
    pub fn assert(&mut self, constraint: Bv) {
        assert_eq!(
            constraint.width(),
            1,
            "a constraint must be 1 bit, got {}",
            constraint.width()
        );
        self.asserts.push(constraint);
    }

    /// Solve the accumulated constraints with the default budget.
    ///
    /// ```
    /// use smtlite::{Bv, Solution, Solver};
    ///
    /// let mut s = Solver::new();
    /// let n = s.var("n", 8);
    /// s.assert(n.mul(&Bv::val(4, 8)).ult(&n)); // n*4 wrapped: an overflow exists
    ///
    /// assert!(matches!(s.check(), Solution::Sat(_)));
    /// ```
    #[must_use]
    pub fn check(&self) -> Solution {
        self.check_with_budget(DEFAULT_BUDGET)
    }

    /// Solve, spending at most `budget` decisions.
    #[must_use]
    pub fn check_with_budget(&self, budget: u64) -> Solution {
        self.solve_constraints(&self.asserts, budget, None)
    }

    /// Solve an explicit set of constraints *without* storing them, against the variables
    /// already declared.
    ///
    /// The constraints passed here are the whole formula: nothing previously
    /// [`assert`](Self::assert)ed takes part. That makes this the entry point for asking many
    /// independent questions against one shared variable namespace - where each question
    /// carries its own set of constraints (one path's assumptions, say) and none of them
    /// should leak into the next.
    #[must_use]
    pub fn check_all(&self, constraints: &[Bv]) -> Solution {
        self.solve_constraints(constraints, DEFAULT_BUDGET, None)
    }

    /// [`check_all`](Self::check_all) with an explicit decision budget.
    ///
    /// A sweep over many queries uses a small budget, so one hard instance degrades to
    /// [`Solution::Unknown`] instead of dominating the batch's wall-clock.
    #[must_use]
    pub fn check_all_with_budget(&self, constraints: &[Bv], budget: u64) -> Solution {
        self.solve_constraints(constraints, budget, None)
    }

    /// [`check_all_with_budget`](Self::check_all_with_budget) plus a wall-clock `deadline`.
    ///
    /// The budget bounds decisions, not time. A batch that has to finish inside a wall-clock
    /// bound passes a deadline here, so the slowest query degrades rather than stalling the
    /// rest.
    #[must_use]
    pub fn check_all_within(
        &self,
        constraints: &[Bv],
        budget: u64,
        deadline: std::time::Instant,
    ) -> Solution {
        self.solve_constraints(constraints, budget, Some(deadline))
    }

    fn solve_constraints(
        &self,
        constraints: &[Bv],
        budget: u64,
        deadline: Option<std::time::Instant>,
    ) -> Solution {
        // One arena per solve holds every clause and drops when this function returns. The
        // `Model` we hand back copies its bits out, so it never borrows the arena.
        let bump = bumpalo::Bump::new();
        let mut b = Blaster::new(&bump);
        for c in constraints {
            b.assert_true(c);
        }
        if b.cnf.clauses.len() > self.max_clauses {
            return Solution::Unknown;
        }
        match b.cnf.solve_within(budget, deadline) {
            Sat(assignment) => {
                let name_to_id = self
                    .vars
                    .iter()
                    .enumerate()
                    .map(|(id, (n, _))| (n.clone(), id))
                    .collect();
                Solution::Sat(Model {
                    assignment,
                    var_bits: b.var_bits,
                    name_to_id,
                })
            }
            Unsat => Solution::Unsat,
            Unknown => Solution::Unknown,
        }
    }
}

/// A satisfying assignment, queryable by variable name.
///
/// Only [`Solution::Sat`] carries one. The assignment is total - every variable the solver
/// knows about has a value here, whether or not a given constraint mentioned it - but
/// [`get`](Model::get) reports only the variables this model was actually built with.
#[derive(Debug)]
pub struct Model {
    assignment: Vec<bool>,
    var_bits: HashMap<usize, Vec<i32>>,
    name_to_id: HashMap<String, usize>,
}

impl Model {
    /// The concrete value of a variable, or `None` if the model has no such variable.
    ///
    /// `None` means the name was never declared on the [`Solver`] that produced this model -
    /// not that the value is unknown. A declared variable always reads back, including one no
    /// constraint mentioned (the solver still assigns it a value).
    ///
    /// ```
    /// use smtlite::{Bv, Solution, Solver};
    ///
    /// let mut s = Solver::new();
    /// let x = s.var("x", 64);
    /// s.assert(x.and(&Bv::val(0xf, 64)).eq(&Bv::val(0xc, 64)));
    ///
    /// let Solution::Sat(m) = s.check() else { unreachable!() };
    /// assert_eq!(m.get("x").map(|v| v & 0xf), Some(0xc));
    /// assert_eq!(m.get("never_declared"), None);
    /// ```
    ///
    /// A model reads back as a `u64`, so a value wider than that has no representation and
    /// reads back as `None`. Widths are capped at 64 throughout ([`Solver::var`]), so this is
    /// unreachable through the public API; it is checked rather than assumed so the readback
    /// can never shift a bit off the end of the word.
    #[must_use]
    pub fn get(&self, name: &str) -> Option<u64> {
        let id = *self.name_to_id.get(name)?;
        let bits = self.var_bits.get(&id)?;
        if bits.len() > 64 {
            return None;
        }
        let mut v = 0u64;
        for (i, &lit) in bits.iter().enumerate() {
            let base = self.assignment[(lit.unsigned_abs() - 1) as usize];
            if if lit > 0 { base } else { !base } {
                v |= 1u64 << i;
            }
        }
        Some(v)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn sat(s: &Solver) -> Model {
        match s.check() {
            Solution::Sat(m) => m,
            other => panic!("expected SAT, got {other:?}"),
        }
    }

    #[test]
    fn test_linear_add() {
        let mut s = Solver::new();
        let x = s.var("x", 64);
        s.assert(x.add(&Bv::val(3, 64)).eq(&Bv::val(10, 64)));
        assert_eq!(sat(&s).get("x"), Some(7));
    }

    #[test]
    fn test_multiply_by_const() {
        // 2*x == 10 (mod 2^32) has two solutions (5 and 0x80000005) - check the property,
        // not a specific root.
        let mut s = Solver::new();
        let x = s.var("x", 32);
        s.assert(x.mul(&Bv::val(2, 32)).eq(&Bv::val(10, 32)));
        let v = sat(&s).get("x").unwrap();
        assert_eq!(v.wrapping_mul(2) & 0xffff_ffff, 10, "got x={v}");
    }

    #[test]
    fn test_contradiction_is_unsat() {
        let mut s = Solver::new();
        let x = s.var("x", 16);
        s.assert(x.eq(&Bv::val(5, 16)));
        s.assert(x.eq(&Bv::val(6, 16)));
        assert!(matches!(s.check(), Solution::Unsat));
    }

    #[test]
    fn test_range_model() {
        // 5 <u x <u 10  ==>  a value strictly between.
        let mut s = Solver::new();
        let x = s.var("x", 32);
        s.assert(x.ugt(&Bv::val(5, 32)));
        s.assert(x.ult(&Bv::val(10, 32)));
        let v = sat(&s).get("x").unwrap();
        assert!((6..=9).contains(&v), "got {v}");
    }

    #[test]
    fn test_unsigned_add_overflow() {
        // x + 1 <u x is only true on wraparound: x must be all-ones (255 at width 8).
        let mut s = Solver::new();
        let x = s.var("x", 8);
        s.assert(x.add(&Bv::val(1, 8)).ult(&x));
        assert_eq!(sat(&s).get("x"), Some(255));
    }

    #[test]
    fn test_signed_vs_unsigned_compare() {
        // -1 <s 0 holds; 0xff <u 0 does not.
        let mut s = Solver::new();
        s.assert(Bv::val(0xff, 8).slt(&Bv::val(0, 8)));
        assert!(matches!(s.check(), Solution::Sat(_)));

        let mut u = Solver::new();
        u.assert(Bv::val(0xff, 8).ult(&Bv::val(0, 8)));
        assert!(matches!(u.check(), Solution::Unsat));
    }

    #[test]
    fn test_overflow_in_size_math() {
        // `count * elem` overflows a 32-bit size, so the product wraps below `elem`.
        let mut s = Solver::new();
        let count = s.var("count", 32);
        let elem = Bv::val(0x10, 32);
        let size = count.mul(&elem);
        s.assert(size.ult(&elem)); // wrapped
        s.assert(count.ugt(&Bv::val(0, 32)));
        let c = sat(&s).get("count").unwrap();
        assert!(
            c.wrapping_mul(0x10) & 0xffff_ffff < 0x10,
            "count={c} should overflow"
        );
    }
}