Skip to main content

smtlib/
solver.rs

1use indexmap::{map::Entry, IndexMap, IndexSet};
2use itertools::Itertools;
3use smtlib_lowlevel::{
4    ast::{self, Identifier, QualIdentifier},
5    backend,
6    lexicon::{Numeral, Symbol},
7    Driver, Logger, Storage,
8};
9
10use crate::{
11    funs, sorts,
12    terms::{qual_ident, Const, Dynamic, STerm},
13    Bool, Error, Logic, Model, SatResult, SatResultWithModel, Sorted,
14};
15
16/// The [`Solver`] type is the primary entrypoint to interaction with the
17/// solver. Checking for validity of a set of assertions requires:
18/// ```
19/// # use smtlib::{Int, prelude::*};
20/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
21/// // 1. Set up storage (TODO: document)
22/// let st = smtlib::Storage::new();
23/// // 2. Set up the backend (in this case z3)
24/// let backend = smtlib::backend::z3_binary::Z3Binary::new("z3")?;
25/// // 3. Set up the solver
26/// let mut solver = smtlib::Solver::new(&st, backend)?;
27/// // 4. Declare the necessary constants
28/// let x = Int::new_const(&st, "x");
29/// // 5. Add assertions to the solver
30/// solver.assert(x._eq(12))?;
31/// // 6. Check for validity, and optionally construct a model
32/// let sat_res = solver.check_sat_with_model()?;
33/// // 7. In this case we expect sat, and thus want to extract the model
34/// let model = sat_res.expect_sat()?;
35/// // 8. Interpret the result by extract the values of constants which
36/// //    satisfy the assertions.
37/// match model.eval(x) {
38///     Some(x) => println!("This is the value of x: {x}"),
39///     None => panic!("Oh no! This should never happen, as x was part of an assert"),
40/// }
41/// # Ok(())
42/// # }
43/// ```
44#[derive(Debug)]
45pub struct Solver<'st, B> {
46    driver: Driver<'st, B>,
47    push_pop_stack: Vec<StackSizes>,
48    decls: IndexMap<Identifier<'st>, ast::Sort<'st>>,
49    declared_sorts: IndexSet<ast::Sort<'st>>,
50}
51
52#[derive(Debug)]
53struct StackSizes {
54    decls: usize,
55    declared_sorts: usize,
56}
57
58impl<'st, B> Solver<'st, B>
59where
60    B: backend::Backend,
61{
62    /// Construct a new solver provided with the backend to use.
63    ///
64    /// The read more about which backends are available, check out the
65    /// documentation of the [`backend`] module.
66    pub fn new(st: &'st Storage, backend: B) -> Result<Self, Error> {
67        Ok(Self {
68            driver: Driver::new(st, backend)?,
69            push_pop_stack: Vec::new(),
70            decls: Default::default(),
71            declared_sorts: Default::default(),
72        })
73    }
74    /// Get the smtlib storage.
75    pub fn st(&self) -> &'st Storage {
76        self.driver.st()
77    }
78    /// Set the logger for the solver. This is useful for debugging or tracing
79    /// purposes.
80    pub fn set_logger(&mut self, logger: impl Logger) {
81        self.driver.set_logger(logger)
82    }
83    /// Set the timeout for the solver. The timeout is in milliseconds.
84    pub fn set_timeout(&mut self, ms: usize) -> Result<(), Error> {
85        let cmd = ast::Command::SetOption(ast::Option::Attribute(ast::Attribute::WithValue(
86            smtlib_lowlevel::lexicon::Keyword(":timeout"),
87            ast::AttributeValue::SpecConstant(ast::SpecConstant::Numeral(Numeral::from_usize(ms))),
88        )));
89        match self.driver.exec(cmd)? {
90            ast::GeneralResponse::Success => Ok(()),
91            ast::GeneralResponse::Error(e) => Err(Error::Smt(e.to_string(), cmd.to_string())),
92            ast::GeneralResponse::Unsupported => Err(Error::Unsupported),
93            _ => todo!(),
94        }
95    }
96    /// Set the :opt.priority option to the given value
97    pub fn set_opt_priority(&mut self, priority: ast::OptimizationPriority) -> Result<(), Error> {
98        let cmd = ast::Command::SetOption(ast::Option::OptPriority(priority));
99
100        match self.driver.exec(cmd)? {
101            ast::GeneralResponse::Success => Ok(()),
102            ast::GeneralResponse::Error(e) => Err(Error::Smt(e.to_string(), cmd.to_string())),
103            ast::GeneralResponse::Unsupported => Err(Error::Unsupported),
104            _ => todo!(),
105        }
106    }
107    /// Explicitly sets the logic for the solver. For some backends this is not
108    /// required, as they will infer what ever logic fits the current program.
109    ///
110    /// To read more about logics read the documentation of [`Logic`].
111    pub fn set_logic(&mut self, logic: Logic) -> Result<(), Error> {
112        let cmd = ast::Command::SetLogic(Symbol(self.st().alloc_str(&logic.name())));
113        match self.driver.exec(cmd)? {
114            ast::GeneralResponse::Success => Ok(()),
115            ast::GeneralResponse::SpecificSuccessResponse(_) => todo!(),
116            ast::GeneralResponse::Unsupported => todo!(),
117            ast::GeneralResponse::Error(_) => todo!(),
118        }
119    }
120    /// Runs the given command on the solver, and returns the result.
121    pub fn run_command(
122        &mut self,
123        cmd: ast::Command<'st>,
124    ) -> Result<ast::GeneralResponse<'st>, Error> {
125        Ok(self.driver.exec(cmd)?)
126    }
127    /// Adds the constraint of `b` as an assertion to the solver. To check for
128    /// satisfiability call [`Solver::check_sat`] or
129    /// [`Solver::check_sat_with_model`].
130    pub fn assert(&mut self, b: Bool<'st>) -> Result<(), Error> {
131        let term = b.term();
132
133        self.declare_all_consts(term)?;
134
135        let cmd = ast::Command::Assert(term);
136        match self.driver.exec(cmd)? {
137            ast::GeneralResponse::Success => Ok(()),
138            ast::GeneralResponse::Error(e) => Err(Error::Smt(e.to_string(), cmd.to_string())),
139            _ => todo!(),
140        }
141    }
142    /// Adds the optimization goal of `g` as a goal to the solver.
143    pub fn maximize<S>(&mut self, g: S) -> Result<(), Error>
144    where
145        S: Sorted<'st>,
146    {
147        let term = g.into().term();
148
149        self.declare_all_consts(term)?;
150
151        let cmd = ast::Command::Maximize(term);
152
153        match self.driver.exec(cmd)? {
154            ast::GeneralResponse::Success => Ok(()),
155            ast::GeneralResponse::Error(e) => Err(Error::Smt(e.to_string(), cmd.to_string())),
156            _ => unimplemented!(),
157        }
158    }
159    /// Adds soft-constraint `b` to the solver.
160    pub fn assert_soft(&mut self, b: Bool<'st>) -> Result<(), Error> {
161        let term = b.term();
162
163        self.declare_all_consts(term)?;
164
165        let cmd = ast::Command::AssertSoft(term, &[]);
166
167        match self.driver.exec(cmd)? {
168            ast::GeneralResponse::Success => Ok(()),
169            ast::GeneralResponse::Error(e) => Err(Error::Smt(e.to_string(), cmd.to_string())),
170            _ => unimplemented!(),
171        }
172    }
173    /// Adds the optimization goal of `g` as a goal to the solver.
174    pub fn minimize<S>(&mut self, g: S) -> Result<(), Error>
175    where
176        S: Sorted<'st>,
177    {
178        let term = g.into().term();
179
180        self.declare_all_consts(term)?;
181
182        let cmd = ast::Command::Minimize(term);
183
184        match self.driver.exec(cmd)? {
185            ast::GeneralResponse::Success => Ok(()),
186            ast::GeneralResponse::Error(e) => Err(Error::Smt(e.to_string(), cmd.to_string())),
187            _ => unimplemented!(),
188        }
189    }
190    /// Checks for satisfiability of the assertions sent to the solver using
191    /// [`Solver::assert`].
192    ///
193    /// If you are interested in producing a model satisfying the assertions
194    /// check out [`Solver::check_sat`].
195    pub fn check_sat(&mut self) -> Result<SatResult, Error> {
196        let cmd = ast::Command::CheckSat;
197        match self.driver.exec(cmd)? {
198            ast::GeneralResponse::SpecificSuccessResponse(
199                ast::SpecificSuccessResponse::CheckSatResponse(res),
200            ) => Ok(match res {
201                ast::CheckSatResponse::Sat => SatResult::Sat,
202                ast::CheckSatResponse::Unsat => SatResult::Unsat,
203                ast::CheckSatResponse::Unknown => SatResult::Unknown,
204            }),
205            ast::GeneralResponse::Error(msg) => Err(Error::Smt(msg.to_string(), format!("{cmd}"))),
206            res => todo!("{res:?}"),
207        }
208    }
209    /// Checks for satisfiability of the assertions sent to the solver using
210    /// [`Solver::assert`], and produces a [model](Model) in case of `sat`.
211    ///
212    /// If you are not interested in the produced model, check out
213    /// [`Solver::check_sat`].
214    pub fn check_sat_with_model(&mut self) -> Result<SatResultWithModel<'st>, Error> {
215        match self.check_sat()? {
216            SatResult::Unsat => Ok(SatResultWithModel::Unsat),
217            SatResult::Sat => Ok(SatResultWithModel::Sat(self.get_model()?)),
218            SatResult::Unknown => Ok(SatResultWithModel::Unknown),
219        }
220    }
221
222    /// Checks for satisfiability of the assertions sent to the solver using
223    /// [`Solver::assert`] as well as the ones provided in the assumptions.
224    /// A satisfying model can be fetched using [`Solver::get_model`] in case
225    /// of `sat`.
226    ///
227    /// `check_sat_assuming` preserves the context and the given assumptions do
228    /// not affect later calls to [`Solver::check_sat`].
229    pub fn check_sat_assuming(
230        &mut self,
231        assumptions: &[(Const<'st, Bool<'st>>, bool)],
232    ) -> Result<SatResult, Error> {
233        for (assumption, _) in assumptions {
234            self.declare_all_consts(assumption.term())?;
235        }
236        let prop_lits = assumptions
237            .iter()
238            .map(|(assumption, assume_true)| {
239                let symbol = Symbol(assumption.name());
240                match assume_true {
241                    true => ast::PropLiteral::Symbol(symbol),
242                    false => ast::PropLiteral::Not(symbol),
243                }
244            })
245            .collect_vec();
246        let prop_lits = self.st().alloc_slice(&prop_lits);
247        let cmd = ast::Command::CheckSatAssuming(prop_lits);
248        match self.driver.exec(cmd)? {
249            ast::GeneralResponse::SpecificSuccessResponse(
250                ast::SpecificSuccessResponse::CheckSatResponse(res),
251            ) => Ok(match res {
252                ast::CheckSatResponse::Sat => SatResult::Sat,
253                ast::CheckSatResponse::Unsat => SatResult::Unsat,
254                ast::CheckSatResponse::Unknown => SatResult::Unknown,
255            }),
256            ast::GeneralResponse::Error(msg) => Err(Error::Smt(msg.to_string(), format!("{cmd}"))),
257            res => todo!("{res:?}"),
258        }
259    }
260    /// Produces the model for satisfying the assertions. If you are looking to
261    /// retrieve a model after calling [`Solver::check_sat`], consider using
262    /// [`Solver::check_sat_with_model`] instead.
263    ///
264    /// > **NOTE:** This must only be called after having called
265    /// > [`Solver::check_sat`] and it returning [`SatResult::Sat`].
266    pub fn get_model(&mut self) -> Result<Model<'st>, Error> {
267        match self.driver.exec(ast::Command::GetModel)? {
268            ast::GeneralResponse::SpecificSuccessResponse(
269                ast::SpecificSuccessResponse::GetModelResponse(model),
270            ) => Ok(Model::new(self.st(), model)),
271            res => todo!("{res:?}"),
272        }
273    }
274    /// Declares a function to the solver. For more details refer to the
275    /// [`funs`] module.
276    pub fn declare_fun(&mut self, fun: &funs::Fun<'st>) -> Result<(), Error> {
277        for var in fun.vars {
278            self.declare_sort(&var.ast())?;
279        }
280        self.declare_sort(&fun.return_sort.ast())?;
281
282        if fun.vars.is_empty() {
283            return self.declare_const(&qual_ident(fun.name, Some(fun.return_sort.ast())));
284        }
285
286        let cmd = ast::Command::DeclareFun(
287            Symbol(fun.name),
288            self.st()
289                .alloc_slice(&fun.vars.iter().map(|s| s.ast()).collect_vec()),
290            fun.return_sort.ast(),
291        );
292        match self.driver.exec(cmd)? {
293            ast::GeneralResponse::Success => Ok(()),
294            ast::GeneralResponse::Error(e) => Err(Error::Smt(e.to_string(), cmd.to_string())),
295            _ => todo!(),
296        }
297    }
298    /// Evaluate the given term
299    pub fn eval<S>(&mut self, term: S) -> Result<S::Inner, Error>
300    where
301        S: Sorted<'st>,
302        S::Inner: From<STerm<'st>>,
303    {
304        let cmd = ast::Command::Eval(term.into().term());
305
306        match self.driver.exec(cmd)? {
307            ast::GeneralResponse::SpecificSuccessResponse(
308                ast::SpecificSuccessResponse::EvalResponse(ast::EvalResponse(t)),
309            ) => Ok(STerm::new_from_ref(self.st(), t).into()),
310            ast::GeneralResponse::Error(e) => Err(Error::Smt(e.to_string(), cmd.to_string())),
311            _ => unimplemented!(),
312        }
313    }
314    /// Simplifies the given term
315    pub fn simplify(
316        &mut self,
317        t: Dynamic<'st>,
318    ) -> Result<&'st smtlib_lowlevel::ast::Term<'st>, Error> {
319        self.declare_all_consts(t.term())?;
320
321        let cmd = ast::Command::Simplify(t.term());
322
323        match self.driver.exec(cmd)? {
324            ast::GeneralResponse::SpecificSuccessResponse(
325                ast::SpecificSuccessResponse::SimplifyResponse(t),
326            ) => Ok(t.0),
327            res => todo!("{res:?}"),
328        }
329    }
330
331    /// Start a new scope, execute the given closure, and then pop the scope.
332    ///
333    /// A scope is a way to group a set of assertions together, and then later
334    /// rollback all the assertions to the state before the scope was started.
335    pub fn scope<T>(
336        &mut self,
337        f: impl FnOnce(&mut Solver<'st, B>) -> Result<T, Error>,
338    ) -> Result<T, Error> {
339        self.push(1)?;
340        let res = f(self)?;
341        self.pop(1)?;
342        Ok(res)
343    }
344
345    fn push(&mut self, levels: usize) -> Result<(), Error> {
346        self.push_pop_stack.push(StackSizes {
347            decls: self.decls.len(),
348            declared_sorts: self.declared_sorts.len(),
349        });
350
351        let cmd = ast::Command::Push(Numeral::from_usize(levels));
352        match self.driver.exec(cmd)? {
353            ast::GeneralResponse::Success => {}
354            ast::GeneralResponse::Error(e) => {
355                return Err(Error::Smt(e.to_string(), cmd.to_string()));
356            }
357            _ => todo!(),
358        };
359        Ok(())
360    }
361
362    fn pop(&mut self, levels: usize) -> Result<(), Error> {
363        if let Some(sizes) = self.push_pop_stack.pop() {
364            self.decls.truncate(sizes.decls);
365            self.declared_sorts.truncate(sizes.declared_sorts);
366        }
367
368        let cmd = ast::Command::Pop(Numeral::from_usize(levels));
369        match self.driver.exec(cmd)? {
370            ast::GeneralResponse::Success => {}
371            ast::GeneralResponse::Error(e) => {
372                return Err(Error::Smt(e.to_string(), cmd.to_string()));
373            }
374            _ => todo!(),
375        };
376        Ok(())
377    }
378
379    fn declare_all_consts(&mut self, t: &'st ast::Term<'st>) -> Result<(), Error> {
380        for q in t.all_consts() {
381            self.declare_const(q)?;
382        }
383        Ok(())
384    }
385
386    fn declare_const(&mut self, q: &QualIdentifier<'st>) -> Result<(), Error> {
387        match q {
388            QualIdentifier::Identifier(_) => {}
389            QualIdentifier::Sorted(i, s) => {
390                self.declare_sort(s)?;
391
392                match self.decls.entry(*i) {
393                    Entry::Occupied(stored) => assert_eq!(s, stored.get()),
394                    Entry::Vacant(v) => {
395                        v.insert(*s);
396                        match i {
397                            Identifier::Simple(sym) => {
398                                self.driver.exec(ast::Command::DeclareConst(*sym, *s))?;
399                            }
400                            Identifier::Indexed(_, _) => todo!(),
401                        }
402                    }
403                }
404            }
405        };
406        Ok(())
407    }
408
409    fn declare_sort(&mut self, s: &ast::Sort<'st>) -> Result<(), Error> {
410        if self.declared_sorts.contains(s) {
411            return Ok(());
412        }
413        self.declared_sorts.insert(*s);
414
415        let cmd = match s {
416            ast::Sort::Sort(ident) => {
417                let sym = match ident {
418                    Identifier::Simple(sym) => sym,
419                    Identifier::Indexed(_, _) => {
420                        // TODO: is it correct that only sorts from theores can
421                        // be indexed, and thus does not need to be declared?
422                        return Ok(());
423                    }
424                };
425                if sorts::is_built_in_sort(sym.0) {
426                    return Ok(());
427                }
428                ast::Command::DeclareSort(*sym, Numeral::from_usize(0))
429            }
430            ast::Sort::Parametric(ident, params) => {
431                let sym = match ident {
432                    Identifier::Simple(sym) => sym,
433                    Identifier::Indexed(_, _) => {
434                        // TODO: is it correct that only sorts from theores can
435                        // be indexed, and thus does not need to be declared?
436                        return Ok(());
437                    }
438                };
439                if sorts::is_built_in_sort(sym.0) {
440                    return Ok(());
441                }
442                ast::Command::DeclareSort(*sym, Numeral::from_usize(params.len()))
443            }
444        };
445        match self.driver.exec(cmd)? {
446            ast::GeneralResponse::Success => Ok(()),
447            ast::GeneralResponse::Error(e) => Err(Error::Smt(e.to_string(), cmd.to_string())),
448            _ => todo!(),
449        }
450    }
451}
452
453#[cfg(test)]
454mod tests {
455    use smtlib_lowlevel::{backend::z3_binary::Z3Binary, Storage};
456
457    use super::Solver;
458    use crate::{terms::StaticSorted, Int, SatResult, Sorted};
459
460    #[test]
461    fn scope() -> Result<(), crate::Error> {
462        let st = Storage::new();
463        let mut solver = Solver::new(&st, Z3Binary::new("z3").unwrap())?;
464
465        let x = Int::new_const(&st, "x");
466
467        solver.assert(x._eq(10))?;
468
469        solver.scope(|solver| {
470            solver.assert(x._eq(20))?;
471
472            assert_eq!(solver.check_sat()?, SatResult::Unsat);
473
474            Ok(())
475        })?;
476
477        assert_eq!(solver.check_sat()?, SatResult::Sat);
478
479        Ok(())
480    }
481}