Storm 1.10.0.1
A Modern Probabilistic Model Checker
Loading...
Searching...
No Matches
Z3SmtSolver.cpp
Go to the documentation of this file.
6
7namespace storm {
8namespace solver {
9#ifdef STORM_HAVE_Z3
10Z3SmtSolver::Z3ModelReference::Z3ModelReference(storm::expressions::ExpressionManager const& manager, z3::model const& model,
11 storm::adapters::Z3ExpressionAdapter& expressionAdapter)
12 : ModelReference(manager), model(model), expressionAdapter(expressionAdapter) {
13 // Intentionally left empty.
14}
15#endif
16
17bool Z3SmtSolver::Z3ModelReference::getBooleanValue(storm::expressions::Variable const& variable) const {
18#ifdef STORM_HAVE_Z3
19 STORM_LOG_ASSERT(variable.getManager() == this->getManager(), "Requested variable is managed by a different manager.");
20 z3::expr z3Expr = this->expressionAdapter.translateExpression(variable);
21 z3::expr z3ExprValuation = model.eval(z3Expr, true);
22 return this->expressionAdapter.translateExpression(z3ExprValuation).isTrue();
23#else
24 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
25#endif
26}
27
28int_fast64_t Z3SmtSolver::Z3ModelReference::getIntegerValue(storm::expressions::Variable const& variable) const {
29#ifdef STORM_HAVE_Z3
30 STORM_LOG_ASSERT(variable.getManager() == this->getManager(), "Requested variable is managed by a different manager.");
31 z3::expr z3Expr = this->expressionAdapter.translateExpression(variable);
32 z3::expr z3ExprValuation = model.eval(z3Expr, true);
33 return this->expressionAdapter.translateExpression(z3ExprValuation).evaluateAsInt();
34#else
35 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
36#endif
37}
38
39double Z3SmtSolver::Z3ModelReference::getRationalValue(storm::expressions::Variable const& variable) const {
40#ifdef STORM_HAVE_Z3
41 STORM_LOG_ASSERT(variable.getManager() == this->getManager(), "Requested variable is managed by a different manager.");
42 z3::expr z3Expr = this->expressionAdapter.translateExpression(variable);
43 z3::expr z3ExprValuation = model.eval(z3Expr, true);
44 return this->expressionAdapter.translateExpression(z3ExprValuation).evaluateAsDouble();
45#else
46 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
47#endif
48}
49
50std::string Z3SmtSolver::Z3ModelReference::toString() const {
51#ifdef STORM_HAVE_Z3
52 std::stringstream sstr;
53 sstr << model;
54 return sstr.str();
55#else
56 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
57#endif
58}
59
60Z3SmtSolver::Z3SmtSolver(storm::expressions::ExpressionManager& manager)
61 : SmtSolver(manager)
62#ifdef STORM_HAVE_Z3
63 ,
64 context(nullptr),
65 solver(nullptr),
66 expressionAdapter(nullptr),
67 lastCheckAssumptions(false),
68 lastResult(CheckResult::Unknown)
69#endif
70{
71#ifdef STORM_HAVE_Z3
72 z3::config config;
73 config.set("model", true);
74 context = std::unique_ptr<z3::context>(new z3::context(config));
75 solver = std::unique_ptr<z3::solver>(new z3::solver(*context));
76 expressionAdapter = std::unique_ptr<storm::adapters::Z3ExpressionAdapter>(new storm::adapters::Z3ExpressionAdapter(this->getManager(), *context));
77#endif
78}
79
81 // Intentionally left empty.
82}
83
85#ifdef STORM_HAVE_Z3
86 this->solver->push();
87#else
88 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
89#endif
90}
91
93#ifdef STORM_HAVE_Z3
94 this->solver->pop();
95#else
96 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
97#endif
98}
99
100void Z3SmtSolver::pop(uint_fast64_t n) {
101#ifdef STORM_HAVE_Z3
102 this->solver->pop(static_cast<unsigned int>(n));
103#else
104 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
105#endif
106}
107
109#ifdef STORM_HAVE_Z3
110 this->solver->reset();
111#else
112 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
113#endif
114}
115
117#ifdef STORM_HAVE_Z3
118 this->solver->add(expressionAdapter->translateExpression(assertion));
119#else
120 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
121#endif
122}
123
124void Z3SmtSolver::addNotCurrentModel(bool performSolverReset) {
125#ifdef STORM_HAVE_Z3
126 STORM_LOG_THROW(this->lastResult == SmtSolver::CheckResult::Sat, storm::exceptions::InvalidStateException,
127 "Unable to create model for formula that was not determined to be satisfiable.");
128
129 auto currentModel = this->solver->get_model();
130 z3::expr notThisModel = currentModel.ctx().bool_val(true);
131 for (auto const& variable : this->getManager().getVariables()) {
132 z3::expr var = this->expressionAdapter->translateExpression(variable);
133 auto value = currentModel.eval(var);
134 if (notThisModel.is_const()) {
135 notThisModel = var == value;
136 } else {
137 notThisModel = notThisModel && (var == value);
138 }
139 }
140 // https://stackoverflow.com/questions/78261966/z3-non-incremental-search-for-multiple-models-works-incremental-search-does-no
141 if (performSolverReset) {
142 auto const allAssertions = this->solver->assertions();
143 solver->reset();
144 for (auto const& assertion : allAssertions) {
145 solver->add(assertion);
146 }
147 }
148 this->solver->add(!notThisModel);
149#else
150 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
151#endif
152}
153
155#ifdef STORM_HAVE_Z3
156 lastCheckAssumptions = false;
157 switch (this->solver->check()) {
158 case z3::sat:
159 this->lastResult = SmtSolver::CheckResult::Sat;
160 break;
161 case z3::unsat:
162 this->lastResult = SmtSolver::CheckResult::Unsat;
163 break;
164 default:
165 this->lastResult = SmtSolver::CheckResult::Unknown;
166 break;
167 }
168 return this->lastResult;
169#else
170 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
171#endif
172}
173
174SmtSolver::CheckResult Z3SmtSolver::checkWithAssumptions(std::set<storm::expressions::Expression> const& assumptions) {
175#ifdef STORM_HAVE_Z3
176 lastCheckAssumptions = true;
177 z3::expr_vector z3Assumptions(*this->context);
178
179 for (storm::expressions::Expression assumption : assumptions) {
180 z3Assumptions.push_back(this->expressionAdapter->translateExpression(assumption));
181 }
182
183 switch (this->solver->check(z3Assumptions)) {
184 case z3::sat:
185 this->lastResult = SmtSolver::CheckResult::Sat;
186 break;
187 case z3::unsat:
188 this->lastResult = SmtSolver::CheckResult::Unsat;
189 break;
190 default:
191 this->lastResult = SmtSolver::CheckResult::Unknown;
192 break;
193 }
194 return this->lastResult;
195#else
196 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
197#endif
198}
199
200#ifndef WINDOWS
201SmtSolver::CheckResult Z3SmtSolver::checkWithAssumptions(std::initializer_list<storm::expressions::Expression> const& assumptions) {
202#ifdef STORM_HAVE_Z3
203 lastCheckAssumptions = true;
204 z3::expr_vector z3Assumptions(*this->context);
205
206 for (storm::expressions::Expression assumption : assumptions) {
207 z3Assumptions.push_back(this->expressionAdapter->translateExpression(assumption));
208 }
209
210 switch (this->solver->check(z3Assumptions)) {
211 case z3::sat:
212 this->lastResult = SmtSolver::CheckResult::Sat;
213 break;
214 case z3::unsat:
215 this->lastResult = SmtSolver::CheckResult::Unsat;
216 break;
217 default:
218 this->lastResult = SmtSolver::CheckResult::Unknown;
219 break;
220 }
221 return this->lastResult;
222#else
223 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
224#endif
225}
226#endif
228#ifdef STORM_HAVE_Z3
229 STORM_LOG_THROW(this->lastResult == SmtSolver::CheckResult::Sat, storm::exceptions::InvalidStateException,
230 "Unable to create model for formula that was not determined to be satisfiable.");
231 return this->convertZ3ModelToValuation(this->solver->get_model());
232#else
233 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
234#endif
235}
236
237std::shared_ptr<SmtSolver::ModelReference> Z3SmtSolver::getModel() {
238#ifdef STORM_HAVE_Z3
239 STORM_LOG_THROW(this->lastResult == SmtSolver::CheckResult::Sat, storm::exceptions::InvalidStateException,
240 "Unable to create model for formula that was not determined to be satisfiable.");
241 return std::shared_ptr<SmtSolver::ModelReference>(new Z3ModelReference(this->getManager(), this->solver->get_model(), *this->expressionAdapter));
242#else
243 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
244#endif
245}
246
247#ifdef STORM_HAVE_Z3
248storm::expressions::SimpleValuation Z3SmtSolver::convertZ3ModelToValuation(z3::model const& model) {
249 storm::expressions::SimpleValuation stormModel(this->getManager().getSharedPointer());
250
251 for (unsigned i = 0; i < model.num_consts(); ++i) {
252 z3::func_decl variableI = model.get_const_decl(i);
253 storm::expressions::Variable stormVariable = this->expressionAdapter->getVariable(variableI);
254 storm::expressions::Expression variableInterpretation = this->expressionAdapter->translateExpression(model.get_const_interp(variableI));
255
256 if (variableInterpretation.getType().isBooleanType()) {
257 stormModel.setBooleanValue(this->getManager().getVariable(variableI.name().str()), variableInterpretation.isTrue());
258 } else if (variableInterpretation.getType().isIntegerType()) {
259 stormModel.setIntegerValue(this->getManager().getVariable(variableI.name().str()), variableInterpretation.evaluateAsInt());
260 } else if (variableInterpretation.getType().isRationalType()) {
261 stormModel.setRationalValue(this->getManager().getVariable(variableI.name().str()), variableInterpretation.evaluateAsDouble());
262 } else {
263 STORM_LOG_ASSERT(false, "Variable interpretation in model is not of type bool, int or rational.");
264 }
265 }
266
267 return stormModel;
268}
269#endif
270
271std::vector<storm::expressions::SimpleValuation> Z3SmtSolver::allSat(std::vector<storm::expressions::Variable> const& important) {
272#ifdef STORM_HAVE_Z3
273 std::vector<storm::expressions::SimpleValuation> valuations;
274 this->allSat(important, static_cast<std::function<bool(storm::expressions::SimpleValuation&)>>(
275 [&valuations](storm::expressions::SimpleValuation const& valuation) -> bool {
276 valuations.push_back(valuation);
277 return true;
278 }));
279 return valuations;
280#else
281 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
282#endif
283}
284
285uint_fast64_t Z3SmtSolver::allSat(std::vector<storm::expressions::Variable> const& important,
286 std::function<bool(storm::expressions::SimpleValuation&)> const& callback) {
287#ifdef STORM_HAVE_Z3
288 for (storm::expressions::Variable const& variable : important) {
289 STORM_LOG_THROW(variable.hasBooleanType(), storm::exceptions::InvalidArgumentException, "The important atoms for AllSat must be boolean variables.");
290 }
291
292 uint_fast64_t numberOfModels = 0;
293 bool proceed = true;
294
295 // Save the current assertion stack, to be able to backtrack after the procedure.
296 this->push();
297
298 // Enumerate models as long as the conjunction is satisfiable and the callback has not aborted the enumeration.
299 while (proceed && this->check() == CheckResult::Sat) {
300 ++numberOfModels;
301 z3::model model = this->solver->get_model();
302
303 z3::expr modelExpr = this->context->bool_val(true);
304 storm::expressions::SimpleValuation valuation(this->getManager().getSharedPointer());
305
306 for (storm::expressions::Variable const& importantAtom : important) {
307 z3::expr z3ImportantAtom = this->expressionAdapter->translateExpression(importantAtom.getExpression());
308 z3::expr z3ImportantAtomValuation = model.eval(z3ImportantAtom, true);
309 modelExpr = modelExpr && (z3ImportantAtom == z3ImportantAtomValuation);
310 valuation.setBooleanValue(importantAtom, this->expressionAdapter->translateExpression(z3ImportantAtomValuation).isTrue());
311 }
312
313 // Check if we are required to proceed, and if so rule out the current model.
314 proceed = callback(valuation);
315 if (proceed) {
316 this->solver->add(!modelExpr);
317 }
318 }
319
320 // Restore the old assertion stack and return.
321 this->pop();
322 return numberOfModels;
323#else
324 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
325#endif
326}
327
328uint_fast64_t Z3SmtSolver::allSat(std::vector<storm::expressions::Variable> const& important, std::function<bool(SmtSolver::ModelReference&)> const& callback) {
329#ifdef STORM_HAVE_Z3
330 for (storm::expressions::Variable const& variable : important) {
331 STORM_LOG_THROW(variable.hasBooleanType(), storm::exceptions::InvalidArgumentException, "The important atoms for AllSat must be boolean variables.");
332 }
333
334 uint_fast64_t numberOfModels = 0;
335 bool proceed = true;
336
337 // Save the current assertion stack, to be able to backtrack after the procedure.
338 this->push();
339
340 // Enumerate models as long as the conjunction is satisfiable and the callback has not aborted the enumeration.
341 while (proceed && this->check() == CheckResult::Sat) {
342 ++numberOfModels;
343 z3::model model = this->solver->get_model();
344
345 z3::expr modelExpr = this->context->bool_val(true);
346 storm::expressions::SimpleValuation valuation(this->getManager().getSharedPointer());
347
348 for (storm::expressions::Variable const& importantAtom : important) {
349 z3::expr z3ImportantAtom = this->expressionAdapter->translateExpression(importantAtom.getExpression());
350 z3::expr z3ImportantAtomValuation = model.eval(z3ImportantAtom, true);
351 modelExpr = modelExpr && (z3ImportantAtom == z3ImportantAtomValuation);
352 }
353 Z3ModelReference modelRef(this->getManager(), model, *expressionAdapter);
354
355 // Check if we are required to proceed, and if so rule out the current model.
356 proceed = callback(modelRef);
357 if (proceed) {
358 this->solver->add(!modelExpr);
359 }
360 }
361
362 this->pop();
363 return numberOfModels;
364#else
365 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
366#endif
367}
368
369std::vector<storm::expressions::Expression> Z3SmtSolver::getUnsatAssumptions() {
370#ifdef STORM_HAVE_Z3
371 STORM_LOG_THROW(lastResult == SmtSolver::CheckResult::Unsat, storm::exceptions::InvalidStateException,
372 "Unable to generate unsatisfiable core of assumptions, because the last check did not determine the formulas to be unsatisfiable.");
373 STORM_LOG_THROW(lastCheckAssumptions, storm::exceptions::InvalidStateException,
374 "Unable to generate unsatisfiable core of assumptions, because the last check did not involve assumptions.");
375
376 z3::expr_vector z3UnsatAssumptions = this->solver->unsat_core();
377 std::vector<storm::expressions::Expression> unsatAssumptions;
378
379 for (unsigned int i = 0; i < z3UnsatAssumptions.size(); ++i) {
380 unsatAssumptions.push_back(this->expressionAdapter->translateExpression(z3UnsatAssumptions[i]));
381 }
382
383 return unsatAssumptions;
384#else
385 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
386#endif
387}
388
389bool Z3SmtSolver::setTimeout(uint_fast64_t milliseconds) {
390#ifdef STORM_HAVE_Z3
391 z3::params paramObject(*context);
392 paramObject.set(":timeout", static_cast<unsigned>(milliseconds));
393 solver->set(paramObject);
394 return true;
395#else
396 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
397#endif
398}
399
401#ifdef STORM_HAVE_Z3
402 z3::params paramObject(*context);
403 paramObject.set(":timeout", 0u);
404 solver->set(paramObject);
405 return true;
406#else
407 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
408#endif
409}
410
411std::string Z3SmtSolver::getSmtLibString() const {
412#ifdef STORM_HAVE_Z3
413 return solver->to_smt2();
414#else
415 STORM_LOG_THROW(false, storm::exceptions::NotSupportedException, "Storm is compiled without Z3 support.");
416#endif
417}
418
419} // namespace solver
420} // namespace storm
int_fast64_t evaluateAsInt(Valuation const *valuation=nullptr) const
Evaluates the expression under the valuation of variables given by the valuation and returns the resu...
double evaluateAsDouble(Valuation const *valuation=nullptr) const
Evaluates the expression under the valuation of variables given by the valuation and returns the resu...
Type const & getType() const
Retrieves the type of the expression.
bool isTrue() const
Checks if the expression is equal to the boolean literal true.
This class is responsible for managing a set of typed variables and all expressions using these varia...
std::set< Variable > const & getVariables() const
Retrieves the set of all variables known to this manager.
A simple implementation of the valuation interface.
virtual void setBooleanValue(Variable const &booleanVariable, bool value) override
Sets the value of the given boolean variable to the provided value.
bool isBooleanType() const
Checks whether this type is a boolean type.
Definition Type.cpp:178
bool isIntegerType() const
Checks whether this type is an integral type.
Definition Type.cpp:182
bool isRationalType() const
Checks whether this type is a rational type.
Definition Type.cpp:214
ExpressionManager const & getManager() const
Retrieves the manager responsible for this variable.
Definition Variable.cpp:54
The base class for all model references.
Definition SmtSolver.h:31
An interface that captures the functionality of an SMT solver.
Definition SmtSolver.h:22
storm::expressions::ExpressionManager const & getManager() const
Retrieves the expression manager associated with the solver.
Definition SmtSolver.cpp:79
CheckResult
possible check results
Definition SmtSolver.h:25
virtual void add(storm::expressions::Expression const &assertion) override
Adds an assertion to the solver's stack.
virtual bool unsetTimeout() override
If supported by the solver, this unsets a previous timeout.
virtual std::shared_ptr< SmtSolver::ModelReference > getModel() override
If the last call to check() or checkWithAssumptions() returned Sat, this method retrieves a model tha...
virtual storm::expressions::SimpleValuation getModelAsValuation() override
If the last call to check() or checkWithAssumptions() returned Sat, this method retrieves a model tha...
virtual CheckResult checkWithAssumptions(std::set< storm::expressions::Expression > const &assumptions) override
Checks whether the conjunction of assertions that are currently on the solver's stack together with t...
virtual std::string getSmtLibString() const override
If supported by the solver, this function returns the current assertions in the SMT-LIB format.
virtual std::vector< storm::expressions::SimpleValuation > allSat(std::vector< storm::expressions::Variable > const &important) override
Performs AllSat over the (provided) important atoms.
virtual void reset() override
Removes all assertions from the solver's stack.
virtual void push() override
Pushes a backtracking point on the solver's stack.
virtual std::vector< storm::expressions::Expression > getUnsatAssumptions() override
If the last call to checkWithAssumptions() returned Unsat, this function can be used to retrieve a su...
virtual bool setTimeout(uint_fast64_t milliseconds) override
If supported by the solver, this will limit all subsequent satisfiability queries to the given number...
virtual void addNotCurrentModel(bool performSolverReset=true) override
If supported by the solver, this function tells the SMT solver to produce a model different from the ...
virtual void pop() override
Pops a backtracking point from the solver's stack.
virtual CheckResult check() override
Checks whether the conjunction of assertions that are currently on the solver's stack is satisfiable.
#define STORM_LOG_ASSERT(cond, message)
Definition macros.h:11
#define STORM_LOG_THROW(cond, exception, message)
Definition macros.h:30
SettingsManager const & manager()
Retrieves the settings manager.
LabParser.cpp.
Definition cli.cpp:18