smtlite 0.2.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
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
//! 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.
#![cfg_attr(doctest, doc = include_str!("../README.md"))]

mod blast;
mod bv;
pub mod field;
mod sat;
pub mod set;
pub mod theory;

use std::cell::RefCell;
use std::collections::HashMap;

pub use bv::{Bv, mask};
pub use set::Set;
pub use theory::{Array, ArrayTheory, ModelView, Theory, Uninterpreted};

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

/// Default decision budget before a query degrades to [`Solution::Unknown`].
///
/// Public so a consumer that calls the `_theories` entry points - whose budget
/// is explicit, unlike [`Solver::check`]'s - can pass the same bound the
/// plain entry points use instead of hard-coding a number that drifts.
pub const DEFAULT_BUDGET: u64 = 4_000_000;

/// Default formula-size cap: the blaster stops generating clauses at this count, and a formula
/// that would exceed it is [`Solution::Unknown`] without being solved at all.
///
/// 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`], paired with a
/// wall-clock deadline.
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 query finished - during blasting, preprocessing, or the search itself.
    ///
    /// 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.
pub struct Solver {
    vars: Vec<(String, u32)>,
    asserts: Vec<Bv>,
    max_clauses: usize,
    cache: RefCell<Option<CacheState>>,
    /// The registered theories, consulted by the `check_*_theories` entry points only.
    theories: Vec<Box<dyn Theory>>,
    /// Model-check rounds allowed per theory query before `Unknown` - see
    /// [`Solver::with_theory_rounds`].
    theory_rounds: usize,
}

impl std::fmt::Debug for Solver {
    /// Hand-written because a registered [`Theory`] is a trait object: the summary reports the
    /// registered names (in registration order), not the boxed internals.
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Solver")
            .field("vars", &self.vars)
            .field("asserts", &self.asserts.len())
            .field("max_clauses", &self.max_clauses)
            .field("cached", &self.cache.borrow().is_some())
            .field(
                "theories",
                &self.theories.iter().map(|t| t.name()).collect::<Vec<_>>(),
            )
            .field("theory_rounds", &self.theory_rounds)
            .finish()
    }
}

/// Default model-check rounds for a theory query: enough for the theories that converge over a
/// few refinements, bounded so a query that would need unboundedly many answers `Unknown`
/// instead of looping.
const DEFAULT_THEORY_ROUNDS: usize = 8;

/// The blasted background of the stored constraints, kept so the per-path entry points can reuse
/// it instead of re-blasting the shared part for every query. Owned clause vectors, so it outlives
/// the arena it was blasted from.
#[derive(Debug)]
struct Cache {
    clauses: Vec<Vec<i32>>,
    nvars: usize,
    var_bits: HashMap<usize, Vec<i32>>,
}

/// The state of the cached background blast.
///
/// `None` at the `Option` level means there is nothing to reuse: either no blast has been
/// attempted yet, or the last attempt ran out of deadline - in both cases the next solve
/// rebuilds. [`Oversize`](CacheState::Oversize) is different: the stored constraints exceed the
/// clause cap, and since the cap never changes on its own, every solve against them answers
/// [`Solution::Unknown`] without re-blasting. `var` and `assert` reset the field to `None`, so a
/// mutation clears the marker along with any stale blast.
#[derive(Debug)]
enum CacheState {
    Ready(Cache),
    Oversize,
}

impl Default for Solver {
    fn default() -> Self {
        Self {
            vars: Vec::new(),
            asserts: Vec::new(),
            max_clauses: DEFAULT_MAX_CLAUSES,
            cache: RefCell::new(None),
            theories: Vec::new(),
            theory_rounds: DEFAULT_THEORY_ROUNDS,
        }
    }
}

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..=128 - the term ceiling. A variable wider than 64 bits is
    /// still readable, through [`Model::get128`].
    pub fn var(&mut self, name: &str, width: u32) -> Bv {
        assert!(
            (1..=128).contains(&width),
            "variable width must be 1..=128, got {width}"
        );
        let id = self.vars.len();
        self.vars.push((name.to_string(), width));
        self.cache.replace(None);
        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);
        self.cache.replace(None);
    }

    /// 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.
    ///
    /// The stored constraints are blasted once and cached, so repeated checks against an
    /// unchanged background only pay for the blast on the first one.
    #[must_use]
    pub fn check_with_budget(&self, budget: u64) -> Solution {
        self.solve_assumptions(&[], budget, None)
    }

    /// Solve the stored constraints together with an extra, per-call set of 1-bit constraints,
    /// with the default budget.
    ///
    /// Each element of `assumptions` is asserted just for this call and dropped after, so the
    /// next solve sees only the stored constraints. This is the "background once, many paths"
    /// pattern: a caller asserts the shared part once, then asks one question per path with that
    /// path's branch conditions on top.
    ///
    /// The background is blasted once and reused; each call only blasts its assumptions. See
    /// [`check_all`](Self::check_all) for the other mode, where the passed constraints are the
    /// whole formula and nothing stored takes part.
    ///
    /// ```
    /// use smtlite::{Bv, Solution, Solver};
    ///
    /// let mut s = Solver::new();
    /// let x = s.var("x", 8);
    /// s.assert(x.ult(&Bv::val(10, 8))); // background: x < 10
    ///
    /// assert!(matches!(s.check_assumptions(&[x.ugt(&Bv::val(5, 8))]), Solution::Sat(_)));
    /// // The assumption did not leak: x < 10 and x < 5 still have a solution.
    /// assert!(matches!(s.check_assumptions(&[x.ult(&Bv::val(5, 8))]), Solution::Sat(_)));
    /// // x < 10 and x > 20 is unsat.
    /// assert!(matches!(s.check_assumptions(&[x.ugt(&Bv::val(20, 8))]), Solution::Unsat));
    /// ```
    #[must_use]
    pub fn check_assumptions(&self, assumptions: &[Bv]) -> Solution {
        self.check_assumptions_with_budget(assumptions, DEFAULT_BUDGET)
    }

    /// [`check_assumptions`](Self::check_assumptions) with an explicit decision budget.
    #[must_use]
    pub fn check_assumptions_with_budget(&self, assumptions: &[Bv], budget: u64) -> Solution {
        self.solve_assumptions(assumptions, budget, None)
    }

    /// [`check_assumptions_with_budget`](Self::check_assumptions_with_budget) plus a wall-clock
    /// `deadline`, covering the whole query: the (cached) blast of the background, the blast of
    /// the assumptions, and the search itself. A background whose first blast the deadline cut
    /// short is rebuilt on the next call, so one slow build does not poison later queries.
    #[must_use]
    pub fn check_assumptions_within(
        &self,
        assumptions: &[Bv],
        budget: u64,
        deadline: std::time::Instant,
    ) -> Solution {
        self.solve_assumptions(assumptions, budget, Some(deadline))
    }

    /// 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. The deadline covers the whole query - the blast of the constraints, the
    /// preprocessing pass, and the search - not just the search.
    #[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);
        // The deadline and the clause cap bound the blast itself, not only the search: once
        // either trips, the blaster hands back dummy literals and stops emitting clauses.
        b.deadline = deadline;
        b.cnf.cap = Some(self.max_clauses);
        // Every declared variable gets its SAT bits up front, so a model is total over the
        // declaration: `Model::get` reads back a variable no constraint happened to mention.
        for (id, (_, width)) in self.vars.iter().enumerate() {
            b.declare_var(id, *width);
        }
        for c in constraints {
            b.assert_true(c);
        }
        // A bound tripped during the blast leaves dummy literals in the formula, so bail to
        // Unknown before the solver can see them. The count check is not redundant with `full`:
        // the pinned-true clause predates the cap being set, so a zero cap alone never trips
        // `full` (and `full` implies exactly `cap` clauses, so it would miss a truncation).
        if b.cnf.full
            || b.cnf.clauses.len() > self.max_clauses
            || deadline.is_some_and(|d| std::time::Instant::now() >= d)
        {
            return Solution::Unknown;
        }
        match b.cnf.solve_within(budget, deadline) {
            Sat(assignment) => Solution::Sat(Model {
                assignment,
                var_bits: b.var_bits,
                name_to_id: self.name_to_id(),
            }),
            Unsat => Solution::Unsat,
            Unknown => Solution::Unknown,
        }
    }

    fn solve_assumptions(
        &self,
        assumptions: &[Bv],
        budget: u64,
        deadline: Option<std::time::Instant>,
    ) -> Solution {
        // Build (or reuse) the cached blast under the same bounds. An over-cap background or a
        // deadline cut short both answer Unknown here; the latter leaves nothing cached, so the
        // next call retries the build.
        if !self.ensure_cache(deadline) {
            return Solution::Unknown;
        }
        let cache = self.cache.borrow();
        let cache = match cache.as_ref() {
            Some(CacheState::Ready(cache)) => cache,
            _ => return Solution::Unknown,
        };

        // A fresh arena and blaster for this call's clauses. Seed it with the background's
        // literals for every declared variable and continue the variable counter after them, so
        // the assumption gates never collide with the cached bits. The per-call cap is whatever
        // headroom the background left, so the two blasts together respect the cap, and the
        // per-call deadline bounds this blast just as it bound the background's.
        let bump = bumpalo::Bump::new();
        let mut b = Blaster::new(&bump);
        b.deadline = deadline;
        b.cnf.cap = Some(self.max_clauses.saturating_sub(cache.clauses.len()));
        b.var_bits = cache.var_bits.clone();
        b.cnf.nvars = cache.nvars;
        for c in assumptions {
            b.assert_true(c);
        }

        // Background clauses first, then the assumption clauses that borrow this call's arena.
        let mut clauses: Vec<&[i32]> = cache.clauses.iter().map(|c| c.as_slice()).collect();
        clauses.extend(b.cnf.clauses.iter().copied());

        // A bound tripped during the assumption blast leaves dummy literals in the clauses, so
        // bail to Unknown before the solver can see them; the count check catches a background
        // that alone exactly fills the cap, leaving the assumption blast no headroom.
        if b.cnf.full
            || clauses.len() > self.max_clauses
            || deadline.is_some_and(|d| std::time::Instant::now() >= d)
        {
            return Solution::Unknown;
        }
        match sat::solve(&clauses, b.cnf.nvars, budget, deadline) {
            Sat(assignment) => Solution::Sat(Model {
                assignment,
                var_bits: b.var_bits,
                name_to_id: self.name_to_id(),
            }),
            Unsat => Solution::Unsat,
            Unknown => Solution::Unknown,
        }
    }

    /// Build the cached blast of the stored constraints if it is not already there, bounding the
    /// build by `deadline`.
    ///
    /// Returns whether a usable cache is in place. `false` means either the background exceeds
    /// the clause cap - remembered as [`Oversize`](CacheState::Oversize), so every later call
    /// answers the same way without re-blasting - or the deadline cut the build short, which is
    /// remembered as nothing, so the next call (with a fresh deadline, say) retries it.
    fn ensure_cache(&self, deadline: Option<std::time::Instant>) -> bool {
        let mut cache = self.cache.borrow_mut();
        if cache.is_none() {
            let (built, over) = self.blast_background(deadline);
            if over {
                *cache = Some(CacheState::Oversize);
                return false;
            }
            if deadline.is_some_and(|d| std::time::Instant::now() >= d) {
                // The deadline cut the build short: do not cache a formula full of dummy
                // literals, and do not remember the failure either - retrying is cheap and
                // correct, while a poisoned cache would fail every later query.
                return false;
            }
            *cache = Some(CacheState::Ready(built));
            return true;
        }
        matches!(cache.as_ref(), Some(CacheState::Ready(_)))
    }

    /// Blast the stored constraints once, copying the clauses out of the arena so they outlive
    /// it. The `bool` reports whether the build was cut off: the clause cap tripped (`full`), or
    /// the count exceeds it - the pinned-true clause predates the cap being set, so a zero cap
    /// needs the count, not `full`.
    fn blast_background(&self, deadline: Option<std::time::Instant>) -> (Cache, bool) {
        let bump = bumpalo::Bump::new();
        let mut b = Blaster::new(&bump);
        b.deadline = deadline;
        b.cnf.cap = Some(self.max_clauses);
        for (id, (_, width)) in self.vars.iter().enumerate() {
            b.declare_var(id, *width);
        }
        for c in &self.asserts {
            b.assert_true(c);
        }
        let over = b.cnf.full || b.cnf.clauses.len() > self.max_clauses;
        (
            Cache {
                clauses: b.cnf.clauses.iter().map(|c| c.to_vec()).collect(),
                nvars: b.cnf.nvars,
                var_bits: b.var_bits,
            },
            over,
        )
    }

    fn name_to_id(&self) -> HashMap<String, usize> {
        self.vars
            .iter()
            .enumerate()
            .map(|(id, (n, _))| (n.clone(), id))
            .collect()
    }
}

/// A satisfying assignment, queryable by variable name.
///
/// Only [`Solution::Sat`] carries one. The assignment is total over the variables declared on
/// the [`Solver`]: [`get`](Model::get) reads back any declared variable, whether or not a
/// constraint mentioned it, so a query that constrains only some of the declared variables
/// still hands back a value for every one.
#[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 here
    /// and reads back as `None`; use [`get128`](Model::get128) for the full value. It is
    /// checked rather than assumed so the readback can never shift a bit off the end of a
    /// word.
    #[must_use]
    pub fn get(&self, name: &str) -> Option<u64> {
        self.value_of(*self.name_to_id.get(name)?)
    }

    /// The value a variable took at the crate's full 128-bit width.
    #[must_use]
    pub fn get128(&self, name: &str) -> Option<u128> {
        self.value_of128(*self.name_to_id.get(name)?)
    }

    /// The value a variable *id* took - [`get`](Model::get) without the name lookup, for a
    /// caller walking terms rather than reading labels (the theory layer's evaluator). `None`
    /// means the id is not in this model, or the variable is wider than a `u64`.
    pub(crate) fn value_of(&self, id: usize) -> Option<u64> {
        let bits = self.var_bits.get(&id)?;
        if bits.len() > 64 {
            return None;
        }
        self.value_of128(id).and_then(|v| u64::try_from(v).ok())
    }

    /// The value a variable id took at 128 bits - the readback the theory layer's evaluator
    /// uses so a wide term can still be checked against a model.
    pub(crate) fn value_of128(&self, id: usize) -> Option<u128> {
        let bits = self.var_bits.get(&id)?;
        let mut v = 0u128;
        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 |= 1u128 << 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"
        );
    }

    #[test]
    fn test_unused_variable_still_reads_back() {
        // The model is total over the declaration: a variable no constraint mentions is still
        // assigned, so `get` returns a value rather than the `None` that means "never declared".
        let mut s = Solver::new();
        let x = s.var("x", 8);
        let _unused = s.var("unused", 16);
        s.assert(x.eq(&Bv::val(5, 8)));

        let m = sat(&s);
        assert_eq!(m.get("x"), Some(5));
        let u = m.get("unused").expect("a declared variable reads back");
        assert!(u <= 0xffff, "unused value {u} exceeds its 16-bit width");
    }

    #[test]
    fn test_variables_read_back_with_no_constraints() {
        // Even an empty constraint set yields a total model over the declared variables.
        let mut s = Solver::new();
        let _a = s.var("a", 1);
        let _b = s.var("b", 64);

        let m = sat(&s);
        assert!(m.get("a").is_some());
        assert!(m.get("b").is_some());
    }
}