Storm 1.10.0.1
A Modern Probabilistic Model Checker
Loading...
Searching...
No Matches
Z3ExpressionAdapter.cpp
Go to the documentation of this file.
2
3#include <cstdint>
4
12
13namespace storm {
14namespace adapters {
15
16#ifdef STORM_HAVE_Z3
17
18#ifdef STORM_Z3_API_USES_STANDARD_INTEGERS
19typedef int64_t Z3_SIGNED_INTEGER;
20typedef uint64_t Z3_UNSIGNED_INTEGER;
21#else
22typedef long long Z3_SIGNED_INTEGER;
23typedef unsigned long long Z3_UNSIGNED_INTEGER;
24#endif
25
26Z3ExpressionAdapter::Z3ExpressionAdapter(storm::expressions::ExpressionManager& manager, z3::context& context)
27 : manager(manager), context(context), additionalAssertions(), variableToExpressionMapping() {
28 // Intentionally left empty.
29}
30
31z3::expr Z3ExpressionAdapter::translateExpression(storm::expressions::Expression const& expression) {
32 STORM_LOG_ASSERT(expression.getManager() == this->manager, "Invalid expression for solver.");
33
34 z3::expr result = boost::any_cast<z3::expr>(expression.getBaseExpression().accept(*this, boost::none));
35 expressionCache.clear();
36
37 for (z3::expr const& assertion : additionalAssertions) {
38 result = result && assertion;
39 }
40 additionalAssertions.clear();
41 return result.simplify();
42}
43
44z3::expr Z3ExpressionAdapter::translateExpression(storm::expressions::Variable const& variable) {
45 STORM_LOG_ASSERT(variable.getManager() == this->manager, "Invalid expression for solver.");
46
47 auto const& variableExpressionPair = variableToExpressionMapping.find(variable);
48 if (variableExpressionPair == variableToExpressionMapping.end()) {
49 return createVariable(variable);
50 }
51
52 return variableExpressionPair->second;
53}
54
55storm::expressions::Variable const& Z3ExpressionAdapter::getVariable(z3::func_decl z3Declaration) {
56 auto const& declarationVariablePair = declarationToVariableMapping.find(z3Declaration);
57 STORM_LOG_ASSERT(declarationVariablePair != declarationToVariableMapping.end(), "Unable to find declaration.");
58 return declarationVariablePair->second;
59}
60
61storm::expressions::Expression Z3ExpressionAdapter::translateExpression(z3::expr const& expr) {
62 if (expr.is_app()) {
63 switch (expr.decl().decl_kind()) {
64 case Z3_OP_TRUE:
65 return manager.boolean(true);
66 case Z3_OP_FALSE:
67 return manager.boolean(false);
68 case Z3_OP_EQ:
69 return this->translateExpression(expr.arg(0)) == this->translateExpression(expr.arg(1));
70 case Z3_OP_DISTINCT: {
71 unsigned args = expr.num_args();
72 STORM_LOG_THROW(args != 0, storm::exceptions::ExpressionEvaluationException,
73 "Failed to convert Z3 expression. DISTINCT (mutual != ) operator with 0-arity is assumed to be an error.");
74 if (args == 1) {
75 return manager.boolean(true);
76 } else {
77 storm::expressions::Expression retVal = this->translateExpression(expr.arg(0)) != this->translateExpression(expr.arg(1));
78 for (unsigned arg2 = 2; arg2 < args; ++arg2) {
79 retVal = retVal && (this->translateExpression(expr.arg(0)) != this->translateExpression(expr.arg(arg2)));
80 }
81 for (unsigned arg1 = 1; arg1 < args; ++arg1) {
82 for (unsigned arg2 = arg1 + 1; arg2 < args; ++arg2) {
83 retVal = retVal && (this->translateExpression(expr.arg(arg1)) != this->translateExpression(expr.arg(arg2)));
84 }
85 }
86 return retVal;
87 }
88 }
89 case Z3_OP_ITE:
90 return storm::expressions::ite(this->translateExpression(expr.arg(0)), this->translateExpression(expr.arg(1)),
91 this->translateExpression(expr.arg(2)));
92 case Z3_OP_AND: {
93 unsigned args = expr.num_args();
94 STORM_LOG_THROW(args != 0, storm::exceptions::ExpressionEvaluationException,
95 "Failed to convert Z3 expression. 0-ary AND is assumed to be an error.");
96 if (args == 1) {
97 return this->translateExpression(expr.arg(0));
98 } else {
99 storm::expressions::Expression retVal = this->translateExpression(expr.arg(0));
100 for (unsigned i = 1; i < args; i++) {
101 retVal = retVal && this->translateExpression(expr.arg(i));
102 }
103 return retVal;
104 }
105 }
106 case Z3_OP_OR: {
107 unsigned args = expr.num_args();
108 STORM_LOG_THROW(args != 0, storm::exceptions::ExpressionEvaluationException,
109 "Failed to convert Z3 expression. 0-ary OR is assumed to be an error.");
110 if (args == 1) {
111 return this->translateExpression(expr.arg(0));
112 } else {
113 storm::expressions::Expression retVal = this->translateExpression(expr.arg(0));
114 for (unsigned i = 1; i < args; i++) {
115 retVal = retVal || this->translateExpression(expr.arg(i));
116 }
117 return retVal;
118 }
119 }
120 case Z3_OP_IFF:
121 return storm::expressions::iff(this->translateExpression(expr.arg(0)), this->translateExpression(expr.arg(1)));
122 case Z3_OP_XOR:
123 return storm::expressions::xclusiveor(this->translateExpression(expr.arg(0)), this->translateExpression(expr.arg(1)));
124 case Z3_OP_NOT:
125 return !this->translateExpression(expr.arg(0));
126 case Z3_OP_IMPLIES:
127 return storm::expressions::implies(this->translateExpression(expr.arg(0)), this->translateExpression(expr.arg(1)));
128 case Z3_OP_LE:
129 return this->translateExpression(expr.arg(0)) <= this->translateExpression(expr.arg(1));
130 case Z3_OP_GE:
131 return this->translateExpression(expr.arg(0)) >= this->translateExpression(expr.arg(1));
132 case Z3_OP_LT:
133 return this->translateExpression(expr.arg(0)) < this->translateExpression(expr.arg(1));
134 case Z3_OP_GT:
135 return this->translateExpression(expr.arg(0)) > this->translateExpression(expr.arg(1));
136 case Z3_OP_ADD:
137 return this->translateExpression(expr.arg(0)) + this->translateExpression(expr.arg(1));
138 case Z3_OP_SUB:
139 return this->translateExpression(expr.arg(0)) - this->translateExpression(expr.arg(1));
140 case Z3_OP_UMINUS:
141 return -this->translateExpression(expr.arg(0));
142 case Z3_OP_MUL:
143 return this->translateExpression(expr.arg(0)) * this->translateExpression(expr.arg(1));
144 case Z3_OP_DIV:
145 return this->translateExpression(expr.arg(0)) / this->translateExpression(expr.arg(1));
146 case Z3_OP_IDIV:
147 return this->translateExpression(expr.arg(0)) / this->translateExpression(expr.arg(1));
148 case Z3_OP_ANUM:
149 // Arithmetic numeral.
150 if (expr.is_int() && expr.is_const()) {
151 Z3_SIGNED_INTEGER value;
152 if (Z3_get_numeral_int64(expr.ctx(), expr, &value)) {
153 return manager.integer(value);
154 } else {
155 STORM_LOG_THROW(false, storm::exceptions::ExpressionEvaluationException,
156 "Failed to convert Z3 expression. Expression is constant integer and value does not fit into 64-bit integer.");
157 }
158 } else {
159 STORM_LOG_ASSERT(expr.is_real() && expr.is_const(), "Cannot handle numerical expression");
160 Z3_SIGNED_INTEGER num;
161 Z3_SIGNED_INTEGER den;
162 if (Z3_get_numeral_rational_int64(expr.ctx(), expr, &num, &den)) {
163 return manager.rational(storm::utility::convertNumber<storm::RationalNumber>(static_cast<int_fast64_t>(num)) /
164 storm::utility::convertNumber<storm::RationalNumber>(static_cast<int_fast64_t>(den)));
165 } else {
166 return manager.rational(storm::utility::convertNumber<storm::RationalNumber>(std::string(Z3_get_numeral_string(expr.ctx(), expr))));
167 }
168 }
169 case Z3_OP_AGNUM:
170 STORM_LOG_WARN("Interpreting algebraic numbers as rational numbers. This is not an exact computation.");
171 // Get the value of an algebraic number, converted to a rational, with precision 1/10^16.
172 return manager.rational(storm::utility::convertNumber<storm::RationalNumber>(
173 std::string(Z3_get_numeral_string(expr.ctx(), Z3_get_algebraic_number_lower(expr.ctx(), expr, 16)))));
174 case Z3_OP_UNINTERPRETED:
175 // Currently, we only support uninterpreted constant functions.
176 STORM_LOG_THROW(expr.is_const(), storm::exceptions::ExpressionEvaluationException,
177 "Failed to convert Z3 expression. Encountered non-constant uninterpreted function.");
178 return manager.getVariable(expr.decl().name().str()).getExpression();
179 default:
180 STORM_LOG_THROW(false, storm::exceptions::ExpressionEvaluationException,
181 "Failed to convert Z3 expression. Encountered unhandled Z3_decl_kind " << expr.decl().decl_kind() << ".");
182 break;
183 }
184 } else {
185 STORM_LOG_THROW(false, storm::exceptions::ExpressionEvaluationException, "Failed to convert Z3 expression. Encountered unknown expression type.");
186 }
187}
188
189boost::any Z3ExpressionAdapter::visit(storm::expressions::BinaryBooleanFunctionExpression const& expression, boost::any const& data) {
190 auto cacheIt = expressionCache.find(&expression);
191 if (cacheIt != expressionCache.end()) {
192 return cacheIt->second;
193 }
194
195 z3::expr leftResult = boost::any_cast<z3::expr>(expression.getFirstOperand()->accept(*this, data));
196 z3::expr rightResult = boost::any_cast<z3::expr>(expression.getSecondOperand()->accept(*this, data));
197
198 z3::expr result(context);
199 switch (expression.getOperatorType()) {
201 result = leftResult && rightResult;
202 break;
204 result = leftResult || rightResult;
205 break;
207 result = z3::expr(context, Z3_mk_xor(context, leftResult, rightResult));
208 break;
210 result = z3::expr(context, Z3_mk_implies(context, leftResult, rightResult));
211 break;
213 result = z3::expr(context, Z3_mk_iff(context, leftResult, rightResult));
214 break;
215 default:
216 STORM_LOG_THROW(false, storm::exceptions::ExpressionEvaluationException,
217 "Cannot evaluate expression: unknown boolean binary operator '" << static_cast<int>(expression.getOperatorType())
218 << "' in expression " << expression << ".");
219 }
220
221 expressionCache.emplace(&expression, result);
222 return result;
223}
224
225boost::any Z3ExpressionAdapter::visit(storm::expressions::BinaryNumericalFunctionExpression const& expression, boost::any const& data) {
226 auto cacheIt = expressionCache.find(&expression);
227 if (cacheIt != expressionCache.end()) {
228 return cacheIt->second;
229 }
230
231 z3::expr leftResult = boost::any_cast<z3::expr>(expression.getFirstOperand()->accept(*this, data));
232 z3::expr rightResult = boost::any_cast<z3::expr>(expression.getSecondOperand()->accept(*this, data));
233
234 z3::expr result(context);
235 switch (expression.getOperatorType()) {
237 result = leftResult + rightResult;
238 break;
240 result = leftResult - rightResult;
241 break;
243 result = leftResult * rightResult;
244 break;
246 if (leftResult.is_int() && rightResult.is_int()) {
247 leftResult = z3::expr(context, Z3_mk_int2real(context, leftResult));
248 }
249 result = leftResult / rightResult;
250 break;
252 result = ite(leftResult <= rightResult, leftResult, rightResult);
253 break;
255 result = ite(leftResult >= rightResult, leftResult, rightResult);
256 break;
258 result = pw(leftResult, rightResult);
259 break;
260 default:
261 STORM_LOG_THROW(false, storm::exceptions::ExpressionEvaluationException,
262 "Cannot evaluate expression: unknown numerical binary operator '" << static_cast<int>(expression.getOperatorType())
263 << "' in expression " << expression << ".");
264 }
265
266 expressionCache.emplace(&expression, result);
267 return result;
268}
269
270boost::any Z3ExpressionAdapter::visit(storm::expressions::BinaryRelationExpression const& expression, boost::any const& data) {
271 auto cacheIt = expressionCache.find(&expression);
272 if (cacheIt != expressionCache.end()) {
273 return cacheIt->second;
274 }
275
276 z3::expr leftResult = boost::any_cast<z3::expr>(expression.getFirstOperand()->accept(*this, data));
277 z3::expr rightResult = boost::any_cast<z3::expr>(expression.getSecondOperand()->accept(*this, data));
278
279 z3::expr result(context);
280 switch (expression.getRelationType()) {
282 result = leftResult == rightResult;
283 break;
285 result = leftResult != rightResult;
286 break;
288 result = leftResult < rightResult;
289 break;
291 result = leftResult <= rightResult;
292 break;
294 result = leftResult > rightResult;
295 break;
297 result = leftResult >= rightResult;
298 break;
299 default:
300 STORM_LOG_THROW(false, storm::exceptions::ExpressionEvaluationException,
301 "Cannot evaluate expression: unknown boolean binary operator '" << static_cast<int>(expression.getRelationType())
302 << "' in expression " << expression << ".");
303 }
304
305 expressionCache.emplace(&expression, result);
306 return result;
307}
308
309boost::any Z3ExpressionAdapter::visit(storm::expressions::BooleanLiteralExpression const& expression, boost::any const&) {
310 auto cacheIt = expressionCache.find(&expression);
311 if (cacheIt != expressionCache.end()) {
312 return cacheIt->second;
313 }
314
315 z3::expr result = context.bool_val(expression.getValue());
316
317 expressionCache.emplace(&expression, result);
318 return result;
319}
320
321boost::any Z3ExpressionAdapter::visit(storm::expressions::RationalLiteralExpression const& expression, boost::any const&) {
322 auto cacheIt = expressionCache.find(&expression);
323 if (cacheIt != expressionCache.end()) {
324 return cacheIt->second;
325 }
326
327 std::stringstream fractionStream;
328 fractionStream << expression.getValue();
329 z3::expr result = context.real_val(fractionStream.str().c_str());
330
331 expressionCache.emplace(&expression, result);
332 return result;
333}
334
335boost::any Z3ExpressionAdapter::visit(storm::expressions::IntegerLiteralExpression const& expression, boost::any const&) {
336 auto cacheIt = expressionCache.find(&expression);
337 if (cacheIt != expressionCache.end()) {
338 return cacheIt->second;
339 }
340
341 z3::expr result = context.int_val(static_cast<Z3_SIGNED_INTEGER>(expression.getValue()));
342
343 expressionCache.emplace(&expression, result);
344 return result;
345}
346
347boost::any Z3ExpressionAdapter::visit(storm::expressions::UnaryBooleanFunctionExpression const& expression, boost::any const& data) {
348 auto cacheIt = expressionCache.find(&expression);
349 if (cacheIt != expressionCache.end()) {
350 return cacheIt->second;
351 }
352
353 z3::expr result = boost::any_cast<z3::expr>(expression.getOperand()->accept(*this, data));
354
355 switch (expression.getOperatorType()) {
357 result = !result;
358 break;
359 default:
360 STORM_LOG_THROW(false, storm::exceptions::ExpressionEvaluationException,
361 "Cannot evaluate expression: unknown boolean binary operator '" << static_cast<int>(expression.getOperatorType())
362 << "' in expression " << expression << ".");
363 }
364
365 expressionCache.emplace(&expression, result);
366 return result;
367}
368
369boost::any Z3ExpressionAdapter::visit(storm::expressions::UnaryNumericalFunctionExpression const& expression, boost::any const& data) {
370 auto cacheIt = expressionCache.find(&expression);
371 if (cacheIt != expressionCache.end()) {
372 return cacheIt->second;
373 }
374
375 z3::expr result = boost::any_cast<z3::expr>(expression.getOperand()->accept(*this, data));
376
377 switch (expression.getOperatorType()) {
379 result = 0 - result;
380 break;
382 storm::expressions::Variable freshAuxiliaryVariable = manager.declareFreshVariable(manager.getIntegerType(), true);
383 z3::expr floorVariable = context.int_const(freshAuxiliaryVariable.getName().c_str());
384 additionalAssertions.push_back(z3::expr(context, Z3_mk_int2real(context, floorVariable)) <= result &&
385 result < (z3::expr(context, Z3_mk_int2real(context, floorVariable)) + 1));
386 result = floorVariable;
387 break;
388 }
390 storm::expressions::Variable freshAuxiliaryVariable = manager.declareFreshVariable(manager.getIntegerType(), true);
391 z3::expr ceilVariable = context.int_const(freshAuxiliaryVariable.getName().c_str());
392 additionalAssertions.push_back(z3::expr(context, Z3_mk_int2real(context, ceilVariable)) - 1 < result &&
393 result <= z3::expr(context, Z3_mk_int2real(context, ceilVariable)));
394 result = ceilVariable;
395 break;
396 }
397 default:
398 STORM_LOG_THROW(false, storm::exceptions::ExpressionEvaluationException,
399 "Cannot evaluate expression: unknown numerical unary operator '" << static_cast<int>(expression.getOperatorType()) << "'.");
400 }
401
402 expressionCache.emplace(&expression, result);
403 return result;
404}
405
406boost::any Z3ExpressionAdapter::visit(storm::expressions::IfThenElseExpression const& expression, boost::any const& data) {
407 auto cacheIt = expressionCache.find(&expression);
408 if (cacheIt != expressionCache.end()) {
409 return cacheIt->second;
410 }
411
412 z3::expr conditionResult = boost::any_cast<z3::expr>(expression.getCondition()->accept(*this, data));
413 z3::expr thenResult = boost::any_cast<z3::expr>(expression.getThenExpression()->accept(*this, data));
414 z3::expr elseResult = boost::any_cast<z3::expr>(expression.getElseExpression()->accept(*this, data));
415 z3::expr result = z3::expr(context, Z3_mk_ite(context, conditionResult, thenResult, elseResult));
416
417 expressionCache.emplace(&expression, result);
418 return result;
419}
420
421boost::any Z3ExpressionAdapter::visit(storm::expressions::VariableExpression const& expression, boost::any const&) {
422 return this->translateExpression(expression.getVariable());
423}
424
425z3::expr Z3ExpressionAdapter::createVariable(storm::expressions::Variable const& variable) {
426 z3::expr z3Variable(context);
427 if (variable.getType().isBooleanType()) {
428 z3Variable = context.bool_const(variable.getName().c_str());
429 } else if (variable.getType().isIntegerType()) {
430 z3Variable = context.int_const(variable.getName().c_str());
431 } else if (variable.getType().isBitVectorType()) {
432 z3Variable = context.bv_const(variable.getName().c_str(), variable.getType().getWidth());
433 } else if (variable.getType().isRationalType()) {
434 z3Variable = context.real_const(variable.getName().c_str());
435 } else {
436 STORM_LOG_THROW(false, storm::exceptions::InvalidTypeException,
437 "Encountered variable '" << variable.getName() << "' with unknown type while trying to create solver variables.");
438 }
439 variableToExpressionMapping.insert(std::make_pair(variable, z3Variable));
440 declarationToVariableMapping.insert(std::make_pair(z3Variable.decl(), variable));
441 return z3Variable;
442}
443
444#endif
445} // namespace adapters
446} // namespace storm
virtual boost::any accept(ExpressionVisitor &visitor, boost::any const &data) const =0
Accepts the given visitor by calling its visit method.
OperatorType getOperatorType() const
Retrieves the operator associated with the expression.
std::shared_ptr< BaseExpression const > const & getSecondOperand() const
Retrieves the second operand of the expression.
std::shared_ptr< BaseExpression const > const & getFirstOperand() const
Retrieves the first operand of the expression.
OperatorType getOperatorType() const
Retrieves the operator associated with the expression.
RelationType getRelationType() const
Retrieves the relation associated with the expression.
bool getValue() const
Retrieves the value of the boolean literal.
BaseExpression const & getBaseExpression() const
Retrieves the base expression underlying this expression object.
ExpressionManager const & getManager() const
Retrieves the manager responsible for this expression.
This class is responsible for managing a set of typed variables and all expressions using these varia...
std::shared_ptr< BaseExpression const > getElseExpression() const
Retrieves the else expression of the if-then-else expression.
std::shared_ptr< BaseExpression const > getCondition() const
Retrieves the condition expression of the if-then-else expression.
std::shared_ptr< BaseExpression const > getThenExpression() const
Retrieves the then expression of the if-then-else expression.
int_fast64_t getValue() const
Retrieves the value of the integer literal.
storm::RationalNumber getValue() const
Retrieves the value of the double literal.
bool isBooleanType() const
Checks whether this type is a boolean type.
Definition Type.cpp:178
std::size_t getWidth() const
Retrieves the bit width of the type, provided that it is a bitvector type.
Definition Type.cpp:206
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
bool isBitVectorType() const
Checks whether this type is a bitvector type.
Definition Type.cpp:186
OperatorType getOperatorType() const
Retrieves the operator associated with this expression.
virtual std::shared_ptr< BaseExpression const > getOperand(uint_fast64_t operandIndex) const override
Retrieves the given operand from the expression.
OperatorType getOperatorType() const
Retrieves the operator associated with this expression.
Variable const & getVariable() const
Retrieves the variable associated with this expression.
ExpressionManager const & getManager() const
Retrieves the manager responsible for this variable.
Definition Variable.cpp:54
Type const & getType() const
Retrieves the type of the variable.
Definition Variable.cpp:50
std::string const & getName() const
Retrieves the name of the variable.
Definition Variable.cpp:46
#define STORM_LOG_WARN(message)
Definition logging.h:30
#define STORM_LOG_ASSERT(cond, message)
Definition macros.h:11
#define STORM_LOG_THROW(cond, exception, message)
Definition macros.h:30
Expression ite(Expression const &condition, Expression const &thenExpression, Expression const &elseExpression)
Expression iff(Expression const &first, Expression const &second)
Expression xclusiveor(Expression const &first, Expression const &second)
Expression implies(Expression const &first, Expression const &second)
SettingsManager const & manager()
Retrieves the settings manager.
LabParser.cpp.
Definition cli.cpp:18