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#[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 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 pub fn st(&self) -> &'st Storage {
76 self.driver.st()
77 }
78 pub fn set_logger(&mut self, logger: impl Logger) {
81 self.driver.set_logger(logger)
82 }
83 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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}