CBMC
Loading...
Searching...
No Matches
smt2_conv.cpp
Go to the documentation of this file.
1/*******************************************************************\
2
3Module: SMT Backend
4
5Author: Daniel Kroening, kroening@kroening.com
6
7\*******************************************************************/
8
11
12#include "smt2_conv.h"
13
15#include <util/arith_tools.h>
16#include <util/bitvector_expr.h>
17#include <util/byte_operators.h>
18#include <util/c_types.h>
19#include <util/config.h>
21#include <util/expr_iterator.h>
22#include <util/expr_util.h>
23#include <util/find_symbols.h>
24#include <util/fixedbv.h>
25#include <util/floatbv_expr.h>
26#include <util/format_expr.h>
27#include <util/ieee_float.h>
28#include <util/invariant.h>
30#include <util/namespace.h>
33#include <util/prefix.h>
34#include <util/range.h>
35#include <util/rational.h>
36#include <util/rational_tools.h>
37#include <util/simplify_expr.h>
38#include <util/std_expr.h>
39#include <util/string2int.h>
41#include <util/threeval.h>
42
47
48#include "smt2_tokenizer.h"
49
50#include <cstdint>
51#include <map>
52
53// Mark different kinds of error conditions
54
55// Unexpected types and other combinations not implemented and not
56// expected to be needed
57#define UNEXPECTEDCASE(S) PRECONDITION_WITH_DIAGNOSTICS(false, S);
58
59// General todos
60#define SMT2_TODO(S) PRECONDITION_WITH_DIAGNOSTICS(false, "TODO: " S)
61
63 const namespacet &_ns,
64 const std::string &_benchmark,
65 const std::string &_notes,
66 const std::string &_logic,
67 solvert _solver,
68 std::ostream &_out)
69 : ns(_ns),
70 out(_out),
71 benchmark(_benchmark),
72 notes(_notes),
73 logic(_logic),
74 solver(_solver),
75 boolbv_width(_ns),
76 pointer_logic(_ns),
78{
79 // We set some defaults differently
80 // for some solvers.
81
82 switch(solver)
83 {
85 break;
86
88 use_FPA_theory = true;
89 use_array_of_bool = true;
90 use_as_const = true;
93 emit_set_logic = false;
94 break;
95
97 break;
98
100 use_FPA_theory = true;
101 use_array_of_bool = true;
102 use_as_const = true;
104 emit_set_logic = false;
105 break;
106
107 case solvert::CVC5:
108 logic = "ALL";
109 use_FPA_theory = true;
110 use_array_of_bool = true;
111 use_as_const = true;
113 use_datatypes = true;
114 break;
115
116 case solvert::MATHSAT:
117 break;
118
119 case solvert::YICES:
120 break;
121
122 case solvert::Z3:
123 use_array_of_bool = true;
124 // `as const` is disabled because of a soundness issue in Z3,
125 // see https://github.com/Z3Prover/z3/issues/9550. Revisit once
126 // the upstream bug is fixed and we can bump the minimum Z3
127 // version accordingly.
128 use_as_const = false;
131 emit_set_logic = false;
132 use_datatypes = true;
133 break;
134 }
135
136 write_header();
137}
138
140{
141 return "SMT2";
142}
143
144void smt2_convt::print_assignment(std::ostream &os) const
145{
146 // Boolean stuff
147
148 for(std::size_t v=0; v<boolean_assignment.size(); v++)
149 os << "b" << v << "=" << boolean_assignment[v] << "\n";
150
151 // others
152}
153
155{
156 if(l.is_true())
157 return tvt(true);
158 if(l.is_false())
159 return tvt(false);
160
161 INVARIANT(
162 l.var_no() < boolean_assignment.size(),
163 "variable number shall be within bounds");
164 return tvt(boolean_assignment[l.var_no()]^l.sign());
165}
166
168{
169 out << "; SMT 2" << "\n";
170
171 switch(solver)
172 {
173 // clang-format off
174 case solvert::GENERIC: break;
175 case solvert::BITWUZLA: out << "; Generated for Bitwuzla\n"; break;
176 case solvert::BOOLECTOR: out << "; Generated for Boolector\n"; break;
178 out << "; Generated for the CPROVER SMT2 solver\n"; break;
179 case solvert::CVC5: out << "; Generated for CVC 5\n"; break;
180 case solvert::MATHSAT: out << "; Generated for MathSAT\n"; break;
181 case solvert::YICES: out << "; Generated for Yices\n"; break;
182 case solvert::Z3: out << "; Generated for Z3\n"; break;
183 // clang-format on
184 }
185
186 out << "(set-info :source \"" << notes << "\")" << "\n";
187
188 out << "(set-option :produce-models true)" << "\n";
189
190 // We use a broad mixture of logics, so on some solvers
191 // its better not to declare here.
192 // set-logic should come after setting options
193 if(emit_set_logic && !logic.empty())
194 out << "(set-logic " << logic << ")" << "\n";
195}
196
198{
199 out << "\n";
200
201 // Output object size definitions
202 // Note: object_sizes is std::map, so iteration is deterministic (sorted by
203 // key)
204 for(const auto &object : object_sizes)
205 define_object_size(object.second, object.first);
206
207 if(use_check_sat_assuming && !assumptions.empty())
208 {
209 out << "(check-sat-assuming (";
210 for(const auto &assumption : assumptions)
211 convert_literal(assumption);
212 out << "))\n";
213 }
214 else
215 {
216 // add the assumptions, if any
217 if(!assumptions.empty())
218 {
219 out << "; assumptions\n";
220
221 for(const auto &assumption : assumptions)
222 {
223 out << "(assert ";
224 convert_literal(assumption);
225 out << ")"
226 << "\n";
227 }
228 }
229
230 out << "(check-sat)\n";
231 }
232
233 out << "\n";
234
236 {
237 // Output get-value commands for all identifiers
238 // Note: smt2_identifiers is std::set, so iteration is deterministic
239 // (sorted)
240 for(const auto &id : smt2_identifiers)
241 out << "(get-value (" << id << "))"
242 << "\n";
243 }
244
245 out << "\n";
246
247 out << "(exit)\n";
248
249 out << "; end of SMT2 file"
250 << "\n";
251}
252
254 const irep_idt &id,
255 const object_size_exprt &expr)
256{
257 const exprt &ptr = expr.pointer();
258 std::size_t pointer_width = boolbv_width(ptr.type());
259 std::size_t number = 0;
260 std::size_t h=pointer_width-1;
261 std::size_t l=pointer_width-config.bv_encoding.object_bits;
262
263 for(const auto &o : pointer_logic.objects)
264 {
265 const typet &type = o.type();
266 auto size_expr = size_of_expr(type, ns);
267
268 if(
269 (o.id() != ID_symbol && o.id() != ID_string_constant) ||
270 !size_expr.has_value())
271 {
272 ++number;
273 continue;
274 }
275
276 find_symbols(*size_expr);
277 out << "(assert (=> (= "
278 << "((_ extract " << h << " " << l << ") ";
279 convert_expr(ptr);
280 out << ") (_ bv" << number << " " << config.bv_encoding.object_bits << "))"
281 << "(= " << id << " ";
282 convert_expr(*size_expr);
283 out << ")))\n";
284
285 ++number;
286 }
287}
288
290{
291 if(assumption.is_nil())
292 write_footer();
293 else
294 {
295 assumptions.push_back(convert(assumption));
296 write_footer();
297 assumptions.pop_back();
298 }
299
300 out.flush();
302}
303
304exprt smt2_convt::get(const exprt &expr) const
305{
306 if(expr.id()==ID_symbol)
307 {
308 const irep_idt &id = to_symbol_expr(expr).identifier();
309
310 identifier_mapt::const_iterator it=identifier_map.find(id);
311
312 if(it!=identifier_map.end())
313 return it->second.value;
314 return expr;
315 }
316 else if(expr.id()==ID_nondet_symbol)
317 {
319
320 identifier_mapt::const_iterator it=identifier_map.find(id);
321
322 if(it!=identifier_map.end())
323 return it->second.value;
324 }
325 else if(expr.id() == ID_literal)
326 {
327 auto l = to_literal_expr(expr).get_literal();
328 if(l_get(l).is_true())
329 return true_exprt();
330 else
331 return false_exprt();
332 }
333 else if(expr.id() == ID_not)
334 {
335 auto op = get(to_not_expr(expr).op());
336 if(op == true)
337 return false_exprt();
338 else if(op == false)
339 return true_exprt();
340 }
341 else if(
342 expr.is_constant() || expr.id() == ID_empty_union ||
343 (!expr.has_operands() && (expr.id() == ID_struct || expr.id() == ID_array)))
344 {
345 return expr;
346 }
347 else if(expr.has_operands())
348 {
349 exprt copy = expr;
350 for(auto &op : copy.operands())
351 {
352 exprt eval_op = get(op);
353 if(eval_op.is_nil())
354 return nil_exprt{};
355 op = std::move(eval_op);
356 }
357 return copy;
358 }
359
360 return nil_exprt();
361}
362
364 const irept &src,
365 const typet &type)
366{
367 // See http://www.grammatech.com/resources/smt/SMTLIBTutorial.pdf for the
368 // syntax of SMTlib2 literals.
369 //
370 // A literal expression is one of the following forms:
371 //
372 // * Numeral -- this is a natural number in decimal and is of the form:
373 // 0|([1-9][0-9]*)
374 // * Decimal -- this is a decimal expansion of a real number of the form:
375 // (0|[1-9][0-9]*)[.]([0-9]+)
376 // * Binary -- this is a natural number in binary and is of the form:
377 // #b[01]+
378 // * Hex -- this is a natural number in hexadecimal and is of the form:
379 // #x[0-9a-fA-F]+
380 //
381 // Right now I'm not parsing decimals. It'd be nice if we had a real YACC
382 // parser here, but whatever.
383
384 mp_integer value;
385
386 if(!src.id().empty())
387 {
388 const std::string &s=src.id_string();
389
390 if(s.size()>=2 && s[0]=='#' && s[1]=='b')
391 {
392 // Binary #b010101
393 value=string2integer(s.substr(2), 2);
394 }
395 else if(s.size()>=2 && s[0]=='#' && s[1]=='x')
396 {
397 // Hex #x012345
398 value=string2integer(s.substr(2), 16);
399 }
400 else
401 {
402 std::size_t pos = s.find(".");
403 if(pos != std::string::npos)
404 {
405 // Decimal, return as rational or real
406 if(type.id() == ID_rational)
407 {
408 rationalt rational_value;
409 bool failed = to_rational(
410 constant_exprt{src.id(), rational_typet{}}, rational_value);
412 return from_rational(rational_value);
413 }
414 else if(type.id() == ID_real)
415 {
416 rationalt rational_value;
417 bool failed = to_rational(
418 constant_exprt{src.id(), rational_typet{}}, rational_value);
420 return algebraic_numbert{rational_value}.as_expr();
421 }
422 else
423 {
425 "smt2_convt::parse_literal parsed a number with a decimal point "
426 "as type " +
427 type.id_string());
428 }
429 }
430 // Numeral
431 value=string2integer(s);
432 }
433 }
434 else if(src.get_sub().size()==2 &&
435 src.get_sub()[0].id()=="-") // (- 100)
436 {
437 value=-string2integer(src.get_sub()[1].id_string());
438 }
439 else if(src.get_sub().size()==3 &&
440 src.get_sub()[0].id()=="_" &&
441 // (_ bvDECIMAL_VALUE SIZE)
442 src.get_sub()[1].id_string().substr(0, 2)=="bv")
443 {
444 value=string2integer(src.get_sub()[1].id_string().substr(2));
445 }
446 else if(
447 type.id() == ID_rational && src.get_sub().size() == 3 &&
448 src.get_sub()[0].id() == "/")
449 {
450 rationalt numerator;
451 rationalt denominator;
452 bool failed =
453 to_rational(parse_literal(src.get_sub()[1], type), numerator) ||
454 to_rational(parse_literal(src.get_sub()[2], type), denominator);
456 return from_rational(numerator / denominator);
457 }
458 else if(src.get_sub().size()==4 &&
459 src.get_sub()[0].id()=="fp") // (fp signbv exponentbv significandbv)
460 {
461 if(type.id()==ID_floatbv)
462 {
463 const floatbv_typet &floatbv_type=to_floatbv_type(type);
466 parse_literal(src.get_sub()[2], unsignedbv_typet(floatbv_type.get_e()));
467 constant_exprt s3 =
468 parse_literal(src.get_sub()[3], unsignedbv_typet(floatbv_type.get_f()));
469
470 const auto s1_int = numeric_cast_v<mp_integer>(s1);
471 const auto s2_int = numeric_cast_v<mp_integer>(s2);
472 const auto s3_int = numeric_cast_v<mp_integer>(s3);
473
474 // stitch the bits together
475 value = bitwise_or(
476 s1_int << (floatbv_type.get_e() + floatbv_type.get_f()),
477 bitwise_or((s2_int << floatbv_type.get_f()), s3_int));
478 }
479 else
480 value=0;
481 }
482 else if(src.get_sub().size()==4 &&
483 src.get_sub()[0].id()=="_" &&
484 src.get_sub()[1].id()=="+oo") // (_ +oo e s)
485 {
486 std::size_t e = unsafe_string2size_t(src.get_sub()[2].id_string());
487 std::size_t s = unsafe_string2size_t(src.get_sub()[3].id_string());
489 .to_expr();
490 }
491 else if(src.get_sub().size()==4 &&
492 src.get_sub()[0].id()=="_" &&
493 src.get_sub()[1].id()=="-oo") // (_ -oo e s)
494 {
495 std::size_t e = unsafe_string2size_t(src.get_sub()[2].id_string());
496 std::size_t s = unsafe_string2size_t(src.get_sub()[3].id_string());
498 .to_expr();
499 }
500 else if(src.get_sub().size()==4 &&
501 src.get_sub()[0].id()=="_" &&
502 src.get_sub()[1].id()=="NaN") // (_ NaN e s)
503 {
504 std::size_t e = unsafe_string2size_t(src.get_sub()[2].id_string());
505 std::size_t s = unsafe_string2size_t(src.get_sub()[3].id_string());
507 }
508 else if(
509 src.get_sub().size() == 3 &&
510 src.get_sub()[0].id() == "root-obj") // (root-obj (+ ...) <index>)
511 {
512 // Z3 emits these while there isn't an agreed-upon standard for representing
513 // algebraic numbers just yet. https://smt-comp.github.io/2023/model.html
514 // gave some proposals, but these don't seem to have been implemented.
515 // For now, we use DATA_INVARIANT as our parsing may be overly restrictive.
516 // Eventually, these should become proper, user-facing exceptions.
517 //
518 // The third element is the 1-based index identifying which real root of
519 // the polynomial Z3 chose for its model. We do not constrain its value
520 // because algebraic_numbert tracks only the polynomial, not the specific
521 // root, so any root of the same polynomial maps to the same expression.
523 src.get_sub()[1].id().empty() && src.get_sub()[1].get_sub().size() == 3 &&
524 src.get_sub()[1].get_sub()[0].id() == "+",
525 "unexpected root-obj expression",
526 src.pretty());
527 irept sum_rhs = src.get_sub()[1].get_sub()[2];
528 rationalt constant_coeff;
529 bool failed =
530 to_rational(parse_literal(sum_rhs, rational_typet{}), constant_coeff);
532 !failed, "failed to parse rational constant coefficient", src.pretty());
533 irept sum_lhs = src.get_sub()[1].get_sub()[1];
535 sum_lhs.id().empty() && sum_lhs.get_sub().size() == 3 &&
536 sum_lhs.get_sub()[0].id() == "^" && sum_lhs.get_sub()[1].id() == "x",
537 "unexpected first operand to root-obj",
538 src.pretty());
539 std::size_t degree = unsafe_string2size_t(sum_lhs.get_sub()[2].id_string());
541 degree > 0, "polynomial degree must be positive", src.pretty());
542 std::vector<rationalt> coefficients{degree + 1, rationalt{}};
543 coefficients.front() = constant_coeff;
544 coefficients.back() = rationalt{1};
545 algebraic_numbert a{coefficients};
546 return a.as_expr();
547 }
548
549 if(type.id()==ID_signedbv ||
550 type.id()==ID_unsignedbv ||
551 type.id()==ID_c_enum ||
552 type.id()==ID_c_bool)
553 {
554 return from_integer(value, type);
555 }
556 else if(type.id()==ID_c_enum_tag)
557 {
558 constant_exprt result =
559 from_integer(value, ns.follow_tag(to_c_enum_tag_type(type)));
560
561 // restore the c_enum_tag type
562 result.type() = type;
563 return result;
564 }
565 else if(type.id()==ID_fixedbv ||
566 type.id()==ID_floatbv)
567 {
568 std::size_t width=boolbv_width(type);
569 return constant_exprt(integer2bvrep(value, width), type);
570 }
571 else if(
572 type.id() == ID_integer || type.id() == ID_natural ||
573 type.id() == ID_rational || type.id() == ID_real)
574 {
575 return from_integer(value, type);
576 }
577 else if(type.id() == ID_range)
578 {
579 return from_integer(value + to_integer_range_type(type).from(), type);
580 }
581 else
583 "smt2_convt::parse_literal should not be of unsupported type " +
584 type.id_string());
585}
586
588 const irept &src,
589 const array_typet &type)
590{
591 std::unordered_map<int64_t, exprt> operands_map;
592 walk_array_tree(&operands_map, src, type);
593 exprt::operandst operands;
594 // Try to find the default value, if there is none then set it
595 auto maybe_default_op = operands_map.find(-1);
596 exprt default_op;
597 if(maybe_default_op == operands_map.end())
598 default_op = nil_exprt();
599 else
600 default_op = maybe_default_op->second;
601 int64_t i = 0;
602 auto maybe_size = numeric_cast<std::int64_t>(type.size());
603 if(maybe_size.has_value())
604 {
605 while(i < maybe_size.value())
606 {
607 auto found_op = operands_map.find(i);
608 if(found_op != operands_map.end())
609 operands.emplace_back(found_op->second);
610 else
611 operands.emplace_back(default_op);
612 i++;
613 }
614 }
615 else
616 {
617 // Array size is unknown, keep adding with known indexes in order
618 // until we fail to find one.
619 auto found_op = operands_map.find(i);
620 while(found_op != operands_map.end())
621 {
622 operands.emplace_back(found_op->second);
623 i++;
624 found_op = operands_map.find(i);
625 }
626 operands.emplace_back(default_op);
627 }
628 return array_exprt(operands, type);
629}
630
632 std::unordered_map<int64_t, exprt> *operands_map,
633 const irept &src,
634 const array_typet &type)
635{
636 if(src.get_sub().size()==4 && src.get_sub()[0].id()=="store")
637 {
638 // This is the SMT syntax being parsed here
639 // (store array index value)
640 // Recurse
641 walk_array_tree(operands_map, src.get_sub()[1], type);
642 const auto index_expr = parse_rec(src.get_sub()[2], type.size().type());
643 if(!index_expr.is_constant())
644 // The index in a (store array index value) term is not necessarily a
645 // constant: models for unbounded or non-integer-keyed arrays can carry
646 // a symbolic/non-constant index. Such an entry cannot be placed in the
647 // index-keyed operands map, so skip it during model reconstruction.
648 return;
649 const constant_exprt index_constant = to_constant_expr(index_expr);
650 mp_integer tempint;
651 bool failure = to_integer(index_constant, tempint);
652 if(failure)
653 return;
654 long index = tempint.to_long();
655 exprt value = parse_rec(src.get_sub()[3], type.element_type());
656 operands_map->emplace(index, value);
657 }
658 else if(src.get_sub().size()==2 &&
659 src.get_sub()[0].get_sub().size()==3 &&
660 src.get_sub()[0].get_sub()[0].id()=="as" &&
661 src.get_sub()[0].get_sub()[1].id()=="const")
662 {
663 // (as const type_info default_value)
664 exprt default_value = parse_rec(src.get_sub()[1], type.element_type());
665 operands_map->emplace(-1, default_value);
666 }
667 else
668 {
669 auto bindings_it = current_bindings.find(src.id());
670 if(bindings_it != current_bindings.end())
671 walk_array_tree(operands_map, bindings_it->second, type);
672 }
673}
674
676 const irept &src,
677 const union_typet &type)
678{
679 // these are always flat
680 PRECONDITION(!type.components().empty());
681 const union_typet::componentt &first=type.components().front();
682 std::size_t width=boolbv_width(type);
683 exprt value = parse_rec(src, unsignedbv_typet(width));
684 if(value.is_nil())
685 return nil_exprt();
686 const typecast_exprt converted(value, first.type());
687 return union_exprt(first.get_name(), converted, type);
688}
689
692{
693 const struct_typet::componentst &components =
694 type.components();
695
696 struct_exprt result(exprt::operandst(components.size(), nil_exprt()), type);
697
698 if(components.empty())
699 return result;
700
701 if(use_datatypes)
702 {
703 // Structs look like:
704 // (mk-struct.1 <component0> <component1> ... <componentN>)
705 std::size_t j = 1;
706 for(std::size_t i=0; i<components.size(); i++)
707 {
708 const struct_typet::componentt &c=components[i];
709 if(is_zero_width(components[i].type(), ns))
710 {
711 result.operands()[i] = nil_exprt{};
712 }
713 else
714 {
716 src.get_sub().size() > j, "insufficient number of component values");
717 result.operands()[i] = parse_rec(src.get_sub()[j], c.type());
718 ++j;
719 }
720 }
721 }
722 else
723 {
724 // These are just flattened, i.e., we expect to see a monster bit vector.
725 std::size_t total_width=boolbv_width(type);
726 const auto l = parse_literal(src, unsignedbv_typet(total_width));
727
728 const irep_idt binary =
730
731 CHECK_RETURN(binary.size() == total_width);
732
733 std::size_t offset=0;
734
735 for(std::size_t i=0; i<components.size(); i++)
736 {
737 if(is_zero_width(components[i].type(), ns))
738 continue;
739
740 std::size_t component_width=boolbv_width(components[i].type());
741
742 INVARIANT(
743 offset + component_width <= total_width,
744 "struct component bits shall be within struct bit vector");
745
746 std::string component_binary=
747 "#b"+id2string(binary).substr(
748 total_width-offset-component_width, component_width);
749
750 result.operands()[i]=
751 parse_rec(irept(component_binary), components[i].type());
752
753 offset+=component_width;
754 }
755 }
756
757 return result;
758}
759
760exprt smt2_convt::parse_rec(const irept &src, const typet &type)
761{
762 if(src.get_sub().size() == 3 && src.get_sub()[0].id() == ID_let)
763 {
764 // This is produced by Z3
765 // (let (....) (....))
766 auto previous_bindings = current_bindings;
767 for(const auto &binding : src.get_sub()[1].get_sub())
768 {
769 const irep_idt &name = binding.get_sub()[0].id();
770 current_bindings.emplace(name, binding.get_sub()[1]);
771 }
772 exprt result = parse_rec(src.get_sub()[2], type);
773 current_bindings = std::move(previous_bindings);
774 return result;
775 }
776
777 auto bindings_it = current_bindings.find(src.id());
778 if(bindings_it != current_bindings.end())
779 {
780 return parse_rec(bindings_it->second, type);
781 }
782
783 if(
784 type.id() == ID_signedbv || type.id() == ID_unsignedbv ||
785 type.id() == ID_integer || type.id() == ID_rational ||
786 type.id() == ID_natural || type.id() == ID_real || type.id() == ID_c_enum ||
787 type.id() == ID_c_enum_tag || type.id() == ID_fixedbv ||
788 type.id() == ID_floatbv || type.id() == ID_c_bool || type.id() == ID_range)
789 {
790 return parse_literal(src, type);
791 }
792 else if(type.id()==ID_bool)
793 {
794 if(src.id()==ID_1 || src.id()==ID_true)
795 return true_exprt();
796 else if(src.id()==ID_0 || src.id()==ID_false)
797 return false_exprt();
798 }
799 else if(type.id()==ID_pointer)
800 {
801 // these come in as bit-vector literals
802 std::size_t width=boolbv_width(type);
803 constant_exprt bv_expr = parse_literal(src, unsignedbv_typet(width));
804
806
807 // split into object and offset
808 mp_integer pow=power(2, width-config.bv_encoding.object_bits);
812 bv_expr.get_value(),
813 pointer_logic.pointer_expr(ptr, to_pointer_type(type)));
814 }
815 else if(type.id()==ID_struct)
816 {
817 return parse_struct(src, to_struct_type(type));
818 }
819 else if(type.id() == ID_struct_tag)
820 {
821 auto struct_expr =
822 parse_struct(src, ns.follow_tag(to_struct_tag_type(type)));
823 // restore the tag type
824 struct_expr.type() = type;
825 return std::move(struct_expr);
826 }
827 else if(type.id()==ID_union)
828 {
829 return parse_union(src, to_union_type(type));
830 }
831 else if(type.id() == ID_union_tag)
832 {
833 auto union_expr = parse_union(src, ns.follow_tag(to_union_tag_type(type)));
834 // restore the tag type
835 union_expr.type() = type;
836 return union_expr;
837 }
838 else if(type.id()==ID_array)
839 {
840 return parse_array(src, to_array_type(type));
841 }
842
843 return nil_exprt();
844}
845
847 const exprt &expr,
848 const pointer_typet &result_type)
849{
850 if(
851 expr.id() == ID_symbol || expr.is_constant() ||
852 expr.id() == ID_string_constant || expr.id() == ID_label)
853 {
854 const std::size_t object_bits = config.bv_encoding.object_bits;
855 const std::size_t max_objects = std::size_t(1) << object_bits;
856 const mp_integer object_id = pointer_logic.add_object(expr);
857
858 if(object_id >= max_objects)
859 {
861 "too many addressed objects: maximum number of objects is set to 2^n=" +
862 std::to_string(max_objects) +
863 " (with n=" + std::to_string(object_bits) + "); " +
864 "use the `--object-bits n` option to increase the maximum number"};
865 }
866
867 out << "(concat (_ bv" << object_id << " " << object_bits << ")"
868 << " (_ bv0 " << boolbv_width(result_type) - object_bits << "))";
869 }
870 else if(expr.id()==ID_index)
871 {
872 const index_exprt &index_expr = to_index_expr(expr);
873
874 const exprt &array = index_expr.array();
875 const exprt &index = index_expr.index();
876
877 if(index == 0)
878 {
879 if(array.type().id()==ID_pointer)
880 convert_expr(array);
881 else if(array.type().id()==ID_array)
882 convert_address_of_rec(array, result_type);
883 else
885 }
886 else
887 {
888 // this is really pointer arithmetic
889 index_exprt new_index_expr = index_expr;
890 new_index_expr.index() = from_integer(0, index.type());
891
892 address_of_exprt address_of_expr(
893 new_index_expr,
895
896 plus_exprt plus_expr{address_of_expr, index};
897
898 convert_expr(plus_expr);
899 }
900 }
901 else if(expr.id()==ID_member)
902 {
903 const member_exprt &member_expr=to_member_expr(expr);
904
905 const exprt &struct_op=member_expr.struct_op();
906 const typet &struct_op_type = struct_op.type();
907
909 struct_op_type.id() == ID_struct || struct_op_type.id() == ID_struct_tag,
910 "member expression operand shall have struct type");
911
912 const struct_typet &struct_type =
913 struct_op_type.id() == ID_struct_tag
914 ? ns.follow_tag(to_struct_tag_type(struct_op_type))
915 : to_struct_type(struct_op_type);
916
917 const irep_idt &component_name = member_expr.get_component_name();
918
919 const auto offset = member_offset(struct_type, component_name, ns);
920 CHECK_RETURN(offset.has_value() && *offset >= bytest{0});
921
922 unsignedbv_typet index_type(boolbv_width(result_type));
923
924 // pointer arithmetic
925 out << "(bvadd ";
926 convert_address_of_rec(struct_op, result_type);
927 convert_expr(from_integer(*offset, index_type));
928 out << ")"; // bvadd
929 }
930 else if(expr.id()==ID_if)
931 {
932 const if_exprt &if_expr = to_if_expr(expr);
933
934 out << "(ite ";
935 convert_expr(if_expr.cond());
936 out << " ";
937 convert_address_of_rec(if_expr.true_case(), result_type);
938 out << " ";
939 convert_address_of_rec(if_expr.false_case(), result_type);
940 out << ")";
941 }
942 else
943 INVARIANT(
944 false,
945 "operand of address of expression should not be of kind " +
946 expr.id_string());
947}
948
949static bool has_quantifier(const exprt &expr)
950{
951 bool result = false;
952 expr.visit_post([&result](const exprt &node) {
953 if(node.id() == ID_exists || node.id() == ID_forall)
954 result = true;
955 });
956 return result;
957}
958
960{
961 PRECONDITION(expr.is_boolean());
962
963 // Three cases where no new handle is needed.
964
965 if(expr == true)
966 return const_literal(true);
967 else if(expr == false)
968 return const_literal(false);
969 else if(expr.id()==ID_literal)
970 return to_literal_expr(expr).get_literal();
971
972 // Need a new handle
973
974 out << "\n";
975
976 exprt prepared_expr = prepare_for_convert_expr(expr);
977
980
981 out << "; convert\n";
982 out << "; Converting var_no " << l.var_no() << " with expr ID of "
983 << expr.id_string() << "\n";
984 // We're converting the expression, so store it in the defined_expressions
985 // store and in future we use the literal instead of the whole expression
986 // Note that here we are always converting, so we do not need to consider
987 // other literal kinds, only "|B###|"
988
989 // Z3 refuses get-value when a defined symbol contains a quantifier.
990 if(has_quantifier(prepared_expr))
991 {
992 out << "(declare-fun ";
994 out << " () Bool)\n";
995 out << "(assert (= ";
997 out << ' ';
998 convert_expr(prepared_expr);
999 out << "))\n";
1000 }
1001 else
1002 {
1003 auto identifier =
1004 convert_identifier(std::string{"B"} + std::to_string(l.var_no()));
1005 defined_expressions[expr] = identifier;
1006 smt2_identifiers.insert(identifier);
1007 out << "(define-fun " << identifier << " () Bool ";
1008 convert_expr(prepared_expr);
1009 out << ")\n";
1010 }
1011
1012 return l;
1013}
1014
1016{
1017 // We can only improve Booleans.
1018 if(!expr.is_boolean())
1019 return expr;
1020
1021 return literal_exprt(convert(expr));
1022}
1023
1025{
1026 if(l==const_literal(false))
1027 out << "false";
1028 else if(l==const_literal(true))
1029 out << "true";
1030 else
1031 {
1032 if(l.sign())
1033 out << "(not ";
1034
1035 const auto identifier =
1036 convert_identifier("B" + std::to_string(l.var_no()));
1037
1038 out << identifier;
1039
1040 if(l.sign())
1041 out << ")";
1042
1043 smt2_identifiers.insert(identifier);
1044 }
1045}
1046
1048{
1050}
1051
1052void smt2_convt::push(const std::vector<exprt> &_assumptions)
1053{
1054 INVARIANT(assumptions.empty(), "nested contexts are not supported");
1055
1056 assumptions.reserve(_assumptions.size());
1057 for(auto &assumption : _assumptions)
1058 assumptions.push_back(convert(assumption));
1059}
1060
1062{
1063 assumptions.clear();
1064}
1065
1066static bool is_smt2_simple_identifier(const std::string &identifier)
1067{
1068 if(identifier.empty())
1069 return false;
1070
1071 if(isdigit(identifier[0]))
1072 return false;
1073
1074 for(auto ch : id2string(identifier))
1075 {
1077 return false;
1078 }
1079
1080 return true;
1081}
1082
1083std::string smt2_convt::convert_identifier(const irep_idt &identifier)
1084{
1085 // Is this a "simple identifier"?
1086 if(is_smt2_simple_identifier(id2string(identifier)))
1087 return id2string(identifier);
1088
1089 // Backslashes are disallowed in quoted symbols just for simplicity.
1090 // Otherwise, for Common Lisp compatibility they would have to be treated
1091 // as escaping symbols.
1092
1093 std::string result = "|";
1094
1095 for(auto ch : identifier)
1096 {
1097 switch(ch)
1098 {
1099 case '|':
1100 case '\\':
1101 case '&': // we use the & for escaping
1102 result+='&';
1103 result+=std::to_string(ch);
1104 result+=';';
1105 break;
1106
1107 case '$': // $ _is_ allowed
1108 default:
1109 result+=ch;
1110 }
1111 }
1112
1113 result += '|';
1114
1115 return result;
1116}
1117
1124 const std::string &smt_typename,
1125 const irep_idt &component_name)
1126{
1127 return convert_identifier(smt_typename + "." + id2string(component_name));
1128}
1129
1134 const std::string &smt_typename,
1135 const irep_idt &component_name)
1136{
1137 return convert_identifier(
1138 "update-" + smt_typename + "." + id2string(component_name));
1139}
1140
1141std::string smt2_convt::type2id(const typet &type) const
1142{
1143 if(type.id()==ID_floatbv)
1144 {
1146 return "f"+std::to_string(spec.width())+"_"+std::to_string(spec.f);
1147 }
1148 else if(type.id() == ID_bv)
1149 {
1150 return "B" + std::to_string(to_bitvector_type(type).get_width());
1151 }
1152 else if(type.id()==ID_unsignedbv)
1153 {
1154 return "u"+std::to_string(to_unsignedbv_type(type).get_width());
1155 }
1156 else if(type.id()==ID_c_bool)
1157 {
1158 return "u"+std::to_string(to_c_bool_type(type).get_width());
1159 }
1160 else if(type.id()==ID_signedbv)
1161 {
1162 return "s"+std::to_string(to_signedbv_type(type).get_width());
1163 }
1164 else if(type.id()==ID_bool)
1165 {
1166 return "b";
1167 }
1168 else if(type.id()==ID_c_enum_tag)
1169 {
1170 return type2id(ns.follow_tag(to_c_enum_tag_type(type)).underlying_type());
1171 }
1172 else if(type.id() == ID_pointer)
1173 {
1174 return "p" + std::to_string(to_pointer_type(type).get_width());
1175 }
1176 else if(type.id() == ID_struct_tag)
1177 {
1178 if(use_datatypes)
1179 return datatype_map.at(type);
1180 else
1181 return "S" + std::to_string(boolbv_width(type));
1182 }
1183 else if(type.id() == ID_union_tag)
1184 {
1185 return "U" + std::to_string(boolbv_width(type));
1186 }
1187 else if(type.id() == ID_array)
1188 {
1189 return "A" + type2id(to_array_type(type).element_type());
1190 }
1191 else if(type.id() == ID_integer)
1192 {
1193 return "Int";
1194 }
1195 else if(type.id() == ID_real)
1196 {
1197 return "Real";
1198 }
1199 else if(type.id() == ID_string)
1200 {
1201 return "String";
1202 }
1203 else if(type.id() == ID_regex)
1204 {
1205 return "RegLan";
1206 }
1207 else if(type.id() == ID_mathematical_function)
1208 {
1209 std::string result = "MF";
1210 const auto &mf = to_mathematical_function_type(type);
1211 for(const auto &d : mf.domain())
1212 result += "_" + type2id(d);
1213 result += "_" + type2id(mf.codomain());
1214 return result;
1215 }
1216 else
1217 {
1219 }
1220}
1221
1222std::string smt2_convt::floatbv_suffix(const exprt &expr) const
1223{
1224 PRECONDITION(!expr.operands().empty());
1225 return "_" + type2id(to_multi_ary_expr(expr).op0().type()) + "->" +
1226 type2id(expr.type());
1227}
1228
1230{
1232
1233 if(expr.id()==ID_symbol)
1234 {
1235 const irep_idt &id = to_symbol_expr(expr).identifier();
1236 out << convert_identifier(id);
1237 return;
1238 }
1239
1240 if(expr.id()==ID_smt2_symbol)
1241 {
1242 const irep_idt &id = to_smt2_symbol(expr).get_identifier();
1243 out << id;
1244 return;
1245 }
1246
1247 INVARIANT(
1248 !expr.operands().empty(), "non-symbol expressions shall have operands");
1249
1250 out << '('
1252 "float_bv." + expr.id_string() + floatbv_suffix(expr));
1253
1254 for(const auto &op : expr.operands())
1255 {
1256 out << ' ';
1257 convert_expr(op);
1258 }
1259
1260 out << ')';
1261}
1262
1263void smt2_convt::convert_string_literal(const std::string &s)
1264{
1265 out << '"';
1266 for(auto ch : s)
1267 {
1268 // " is escaped by double-quoting
1269 if(ch == '"')
1270 out << '"';
1271 out << ch;
1272 }
1273 out << '"';
1274}
1275
1277{
1278 // try hash table first
1279 auto converter_result = converters.find(expr.id());
1280 if(converter_result != converters.end())
1281 {
1282 converter_result->second(expr);
1283 return; // done
1284 }
1285
1286 // huge monster case split over expression id
1287 if(expr.id()==ID_symbol)
1288 {
1289 const irep_idt &id = to_symbol_expr(expr).identifier();
1290 DATA_INVARIANT(!id.empty(), "symbol must have identifier");
1291 out << convert_identifier(id);
1292 }
1293 else if(expr.id()==ID_nondet_symbol)
1294 {
1295 const irep_idt &id = to_nondet_symbol_expr(expr).get_identifier();
1296 DATA_INVARIANT(!id.empty(), "nondet symbol must have identifier");
1297 out << convert_identifier("nondet_" + id2string(id));
1298 }
1299 else if(expr.id()==ID_smt2_symbol)
1300 {
1301 const irep_idt &id = to_smt2_symbol(expr).get_identifier();
1302 DATA_INVARIANT(!id.empty(), "smt2 symbol must have identifier");
1303 out << id;
1304 }
1305 else if(expr.id()==ID_typecast)
1306 {
1308 }
1309 else if(expr.id()==ID_floatbv_typecast)
1310 {
1312 }
1313 else if(expr.id() == ID_floatbv_round_to_integral)
1314 {
1316 }
1317 else if(expr.id()==ID_struct)
1318 {
1320 }
1321 else if(expr.id()==ID_union)
1322 {
1324 }
1325 else if(expr.is_constant())
1326 {
1328 }
1329 else if(expr.id() == ID_concatenation)
1330 {
1332 !expr.operands().empty(),
1333 "concatenation expression should have at least one operand",
1334 expr.id_string());
1335
1336 // collect non-zero-width operands (zero-width not allowed by SMT-LIB)
1337 exprt::operandst non_zero_width_ops;
1338 for(const auto &op : expr.operands())
1339 {
1340 if(!is_zero_width(op.type(), ns))
1341 non_zero_width_ops.push_back(op);
1342 }
1343
1345 !non_zero_width_ops.empty(),
1346 "concatenation must have at least one non-zero-width operand");
1347
1348 if(non_zero_width_ops.size() == 1)
1349 {
1350 // unary concat is not valid SMT-LIB; emit the operand directly
1351 flatten2bv(non_zero_width_ops.front());
1352 }
1353 else
1354 {
1355 out << "(concat";
1356
1357 for(const auto &op : non_zero_width_ops)
1358 {
1359 out << ' ';
1360 flatten2bv(op);
1361 }
1362
1363 out << ')';
1364 }
1365 }
1366 else if(
1367 expr.id() == ID_bitand || expr.id() == ID_bitor || expr.id() == ID_bitxor)
1368 {
1370 !expr.operands().empty(),
1371 "given expression should have at least one operand",
1372 expr.id_string());
1373
1374 if(expr.operands().size() == 1)
1375 {
1376 flatten2bv(expr.operands().front());
1377 }
1378 else // >= 2
1379 {
1380 out << '(';
1381
1382 if(expr.id() == ID_concatenation)
1383 out << "concat";
1384 else if(expr.id() == ID_bitand)
1385 out << "bvand";
1386 else if(expr.id() == ID_bitor)
1387 out << "bvor";
1388 else if(expr.id() == ID_bitxor)
1389 out << "bvxor";
1390
1391 for(const auto &op : expr.operands())
1392 {
1393 out << ' ';
1394 flatten2bv(op);
1395 }
1396
1397 out << ')';
1398 }
1399 }
1400 else if(
1401 expr.id() == ID_bitxnor || expr.id() == ID_bitnand ||
1402 expr.id() == ID_bitnor)
1403 {
1404 // SMT-LIB only has these as a binary expression,
1405 // owing to their ambiguity.
1406 if(expr.operands().size() == 2)
1407 {
1408 const auto &binary_expr = to_binary_expr(expr);
1409
1410 out << '(';
1411 if(binary_expr.id() == ID_bitxnor)
1412 out << "bvxnor";
1413 else if(binary_expr.id() == ID_bitnand)
1414 out << "bvnand";
1415 else if(binary_expr.id() == ID_bitnor)
1416 out << "bvnor";
1417 out << ' ';
1418 flatten2bv(binary_expr.op0());
1419 out << ' ';
1420 flatten2bv(binary_expr.op1());
1421 out << ')';
1422 }
1423 else if(expr.operands().size() == 1)
1424 {
1425 out << "(bvnot ";
1426 flatten2bv(to_unary_expr(expr).op());
1427 out << ')';
1428 }
1429 else if(expr.operands().size() >= 3)
1430 {
1431 out << "(bvnot (";
1432 if(expr.id() == ID_bitxnor)
1433 out << "bvxor";
1434 else if(expr.id() == ID_bitnand)
1435 out << "bvand";
1436 else if(expr.id() == ID_bitnor)
1437 out << "bvor";
1438
1439 for(const auto &op : expr.operands())
1440 {
1441 out << ' ';
1442 flatten2bv(op);
1443 }
1444
1445 out << "))"; // bvX, bvnot
1446 }
1447 else
1448 {
1450 expr.operands().size() >= 1,
1451 expr.id_string() + " should have at least one operand");
1452 }
1453 }
1454 else if(expr.id()==ID_bitnot)
1455 {
1456 const bitnot_exprt &bitnot_expr = to_bitnot_expr(expr);
1457
1458 out << "(bvnot ";
1459 convert_expr(bitnot_expr.op());
1460 out << ")";
1461 }
1462 else if(expr.id()==ID_unary_minus)
1463 {
1464 const unary_minus_exprt &unary_minus_expr = to_unary_minus_expr(expr);
1465 const auto &type = expr.type();
1466
1467 if(
1468 type.id() == ID_rational || type.id() == ID_integer ||
1469 type.id() == ID_real)
1470 {
1471 out << "(- ";
1472 convert_expr(unary_minus_expr.op());
1473 out << ")";
1474 }
1475 else if(type.id() == ID_range)
1476 {
1477 auto &range_type = to_integer_range_type(type);
1478 PRECONDITION(type == unary_minus_expr.op().type());
1479 // turn -x into 0-x
1480 auto minus_expr =
1481 minus_exprt{range_type.zero_expr(), unary_minus_expr.op()};
1482 convert_expr(minus_expr);
1483 }
1484 else if(type.id() == ID_floatbv)
1485 {
1486 // this has no rounding mode
1487 if(use_FPA_theory)
1488 {
1489 out << "(fp.neg ";
1490 convert_expr(unary_minus_expr.op());
1491 out << ")";
1492 }
1493 else
1494 convert_floatbv(unary_minus_expr);
1495 }
1496 else
1497 {
1498 PRECONDITION(type.id() != ID_natural);
1499 out << "(bvneg ";
1500 convert_expr(unary_minus_expr.op());
1501 out << ")";
1502 }
1503 }
1504 else if(expr.id()==ID_unary_plus)
1505 {
1506 // A no-op (apart from type promotion)
1507 convert_expr(to_unary_plus_expr(expr).op());
1508 }
1509 else if(expr.id()==ID_sign)
1510 {
1511 const sign_exprt &sign_expr = to_sign_expr(expr);
1512
1513 const typet &op_type = sign_expr.op().type();
1514
1515 if(op_type.id()==ID_floatbv)
1516 {
1517 if(use_FPA_theory)
1518 {
1519 out << "(fp.isNegative ";
1520 convert_expr(sign_expr.op());
1521 out << ")";
1522 }
1523 else
1524 convert_floatbv(sign_expr);
1525 }
1526 else if(op_type.id()==ID_signedbv)
1527 {
1528 std::size_t op_width=to_signedbv_type(op_type).get_width();
1529
1530 out << "(bvslt ";
1531 convert_expr(sign_expr.op());
1532 out << " (_ bv0 " << op_width << "))";
1533 }
1534 else
1536 false,
1537 "sign should not be applied to unsupported type",
1538 sign_expr.type().id_string());
1539 }
1540 else if(expr.id()==ID_if)
1541 {
1542 const if_exprt &if_expr = to_if_expr(expr);
1543
1544 out << "(ite ";
1545 convert_expr(if_expr.cond());
1546 out << " ";
1547 if(
1548 expr.type().id() == ID_array && !use_array_theory(if_expr.true_case()) &&
1549 use_array_theory(if_expr.false_case()))
1550 {
1551 unflatten(wheret::BEGIN, expr.type());
1552
1553 convert_expr(if_expr.true_case());
1554
1555 unflatten(wheret::END, expr.type());
1556 }
1557 else
1558 {
1559 convert_expr(if_expr.true_case());
1560 }
1561 out << " ";
1562 if(
1563 expr.type().id() == ID_array && use_array_theory(if_expr.true_case()) &&
1564 !use_array_theory(if_expr.false_case()))
1565 {
1566 unflatten(wheret::BEGIN, expr.type());
1567
1568 convert_expr(if_expr.false_case());
1569
1570 unflatten(wheret::END, expr.type());
1571 }
1572 else
1573 {
1574 convert_expr(if_expr.false_case());
1575 }
1576 out << ")";
1577 }
1578 else if(expr.id()==ID_and ||
1579 expr.id()==ID_or ||
1580 expr.id()==ID_xor)
1581 {
1583 expr.is_boolean(),
1584 "logical and, or, and xor expressions should have Boolean type");
1586 expr.operands().size() >= 2,
1587 "logical and, or, and xor expressions should have at least two operands");
1588
1589 out << "(" << expr.id();
1590 for(const auto &op : expr.operands())
1591 {
1592 out << " ";
1593 convert_expr(op);
1594 }
1595 out << ")";
1596 }
1597 else if(expr.id() == ID_nand || expr.id() == ID_nor || expr.id() == ID_xnor)
1598 {
1600 expr.is_boolean(),
1601 "logical nand, nor, xnor expressions should have Boolean type");
1603 expr.operands().size() >= 1,
1604 "logical nand, nor, xnor expressions should have at least one operand");
1605
1606 // SMT-LIB doesn't have nand, nor, xnor
1607 out << "(not ";
1608 if(expr.operands().size() == 1)
1609 convert_expr(to_multi_ary_expr(expr).op0());
1610 else
1611 {
1612 if(expr.id() == ID_nand)
1613 out << "(and";
1614 else if(expr.id() == ID_nor)
1615 out << "(or";
1616 else if(expr.id() == ID_xnor)
1617 out << "(xor";
1618 else
1619 DATA_INVARIANT(false, "unexpected expression");
1620 for(const auto &op : expr.operands())
1621 {
1622 out << ' ';
1623 convert_expr(op);
1624 }
1625 out << ')'; // or, and, xor
1626 }
1627 out << ')'; // not
1628 }
1629 else if(expr.id()==ID_implies)
1630 {
1631 const implies_exprt &implies_expr = to_implies_expr(expr);
1632
1634 implies_expr.is_boolean(), "implies expression should have Boolean type");
1635
1636 out << "(=> ";
1637 convert_expr(implies_expr.op0());
1638 out << " ";
1639 convert_expr(implies_expr.op1());
1640 out << ")";
1641 }
1642 else if(expr.id()==ID_not)
1643 {
1644 const not_exprt &not_expr = to_not_expr(expr);
1645
1647 not_expr.is_boolean(), "not expression should have Boolean type");
1648
1649 out << "(not ";
1650 convert_expr(not_expr.op());
1651 out << ")";
1652 }
1653 else if(expr.id() == ID_equal)
1654 {
1655 const equal_exprt &equal_expr = to_equal_expr(expr);
1656
1658 equal_expr.op0().type() == equal_expr.op1().type(),
1659 "operands of equal expression shall have same type");
1660
1661 if(is_zero_width(equal_expr.lhs().type(), ns))
1662 {
1664 }
1665 else
1666 {
1667 out << "(= ";
1668 convert_expr(equal_expr.op0());
1669 out << " ";
1670 convert_expr(equal_expr.op1());
1671 out << ")";
1672 }
1673 }
1674 else if(expr.id() == ID_notequal)
1675 {
1676 const notequal_exprt &notequal_expr = to_notequal_expr(expr);
1677
1679 notequal_expr.op0().type() == notequal_expr.op1().type(),
1680 "operands of not equal expression shall have same type");
1681
1682 out << "(not (= ";
1683 convert_expr(notequal_expr.op0());
1684 out << " ";
1685 convert_expr(notequal_expr.op1());
1686 out << "))";
1687 }
1688 else if(expr.id()==ID_ieee_float_equal ||
1689 expr.id()==ID_ieee_float_notequal)
1690 {
1691 // These are not the same as (= A B)
1692 // because of NaN and negative zero.
1693 const auto &rel_expr = to_binary_relation_expr(expr);
1694
1696 rel_expr.lhs().type() == rel_expr.rhs().type(),
1697 "operands of float equal and not equal expressions shall have same type");
1698
1699 // The FPA theory properly treats NaN and negative zero.
1700 if(use_FPA_theory)
1701 {
1702 if(rel_expr.id() == ID_ieee_float_notequal)
1703 out << "(not ";
1704
1705 out << "(fp.eq ";
1706 convert_expr(rel_expr.lhs());
1707 out << " ";
1708 convert_expr(rel_expr.rhs());
1709 out << ")";
1710
1711 if(rel_expr.id() == ID_ieee_float_notequal)
1712 out << ")";
1713 }
1714 else
1715 convert_floatbv(expr);
1716 }
1717 else if(expr.id()==ID_le ||
1718 expr.id()==ID_lt ||
1719 expr.id()==ID_ge ||
1720 expr.id()==ID_gt)
1721 {
1723 }
1724 else if(expr.id()==ID_plus)
1725 {
1727 }
1728 else if(expr.id()==ID_floatbv_plus)
1729 {
1731 }
1732 else if(expr.id()==ID_minus)
1733 {
1735 }
1736 else if(expr.id()==ID_floatbv_minus)
1737 {
1739 }
1740 else if(expr.id()==ID_div)
1741 {
1742 convert_div(to_div_expr(expr));
1743 }
1744 else if(expr.id()==ID_floatbv_div)
1745 {
1747 }
1748 else if(expr.id()==ID_mod)
1749 {
1750 convert_mod(to_mod_expr(expr));
1751 }
1752 else if(expr.id() == ID_euclidean_mod)
1753 {
1755 }
1756 else if(expr.id()==ID_mult)
1757 {
1759 }
1760 else if(expr.id()==ID_floatbv_mult)
1761 {
1763 }
1764 else if(expr.id() == ID_floatbv_rem)
1765 {
1767 }
1768 else if(expr.id() == ID_floatbv_fma)
1769 {
1771 }
1772 else if(expr.id()==ID_address_of)
1773 {
1774 const address_of_exprt &address_of_expr = to_address_of_expr(expr);
1776 address_of_expr.object(), to_pointer_type(address_of_expr.type()));
1777 }
1778 else if(expr.id() == ID_array_of)
1779 {
1780 const auto &array_of_expr = to_array_of_expr(expr);
1781
1783 array_of_expr.type().id() == ID_array,
1784 "array of expression shall have array type");
1785
1786 if(use_as_const)
1787 {
1788 out << "((as const ";
1789 convert_type(array_of_expr.type());
1790 out << ") ";
1791 convert_expr(array_of_expr.what());
1792 out << ")";
1793 }
1794 else
1795 {
1796 defined_expressionst::const_iterator it =
1797 defined_expressions.find(array_of_expr);
1798 CHECK_RETURN(it != defined_expressions.end());
1799 out << it->second;
1800 }
1801 }
1802 else if(expr.id() == ID_array_comprehension)
1803 {
1804 const auto &array_comprehension = to_array_comprehension_expr(expr);
1805
1807 array_comprehension.type().id() == ID_array,
1808 "array_comprehension expression shall have array type");
1809
1811 {
1812 out << "(lambda ((";
1813 convert_expr(array_comprehension.arg());
1814 out << " ";
1815 convert_type(array_comprehension.type().size().type());
1816 out << ")) ";
1817 convert_expr(array_comprehension.body());
1818 out << ")";
1819 }
1820 else
1821 {
1822 const auto &it = defined_expressions.find(array_comprehension);
1823 CHECK_RETURN(it != defined_expressions.end());
1824 out << it->second;
1825 }
1826 }
1827 else if(expr.id()==ID_index)
1828 {
1830 }
1831 else if(expr.id()==ID_ashr ||
1832 expr.id()==ID_lshr ||
1833 expr.id()==ID_shl)
1834 {
1835 const shift_exprt &shift_expr = to_shift_expr(expr);
1836 const typet &type = shift_expr.type();
1837
1838 if(type.id()==ID_unsignedbv ||
1839 type.id()==ID_signedbv ||
1840 type.id()==ID_bv)
1841 {
1842 if(shift_expr.id() == ID_ashr)
1843 out << "(bvashr ";
1844 else if(shift_expr.id() == ID_lshr)
1845 out << "(bvlshr ";
1846 else if(shift_expr.id() == ID_shl)
1847 out << "(bvshl ";
1848 else
1850
1851 convert_expr(shift_expr.op());
1852 out << " ";
1853
1854 // SMT2 requires the shift distance to have the same width as
1855 // the value that is shifted -- odd!
1856
1857 const auto &distance_type = shift_expr.distance().type();
1858 if(distance_type.id() == ID_integer || distance_type.id() == ID_natural)
1859 {
1860 const auto i =
1862
1863 // shift distance must be bit vector
1864 std::size_t width_op0 = boolbv_width(shift_expr.op().type());
1865 exprt tmp=from_integer(i, unsignedbv_typet(width_op0));
1866 convert_expr(tmp);
1867 }
1868 else if(
1869 distance_type.id() == ID_signedbv ||
1870 distance_type.id() == ID_unsignedbv ||
1871 distance_type.id() == ID_c_enum || distance_type.id() == ID_c_bool)
1872 {
1873 std::size_t width_op0 = boolbv_width(shift_expr.op().type());
1874 std::size_t width_op1 = boolbv_width(distance_type);
1875
1876 if(width_op0==width_op1)
1877 convert_expr(shift_expr.distance());
1878 else if(width_op0>width_op1)
1879 {
1880 out << "((_ zero_extend " << width_op0-width_op1 << ") ";
1881 convert_expr(shift_expr.distance());
1882 out << ")"; // zero_extend
1883 }
1884 else // width_op0<width_op1
1885 {
1886 out << "((_ extract " << width_op0-1 << " 0) ";
1887 convert_expr(shift_expr.distance());
1888 out << ")"; // extract
1889 }
1890 }
1891 else
1892 {
1894 "unsupported distance type for " + shift_expr.id_string() + ": " +
1895 distance_type.id_string());
1896 }
1897
1898 out << ")"; // bv*sh
1899 }
1900 else
1902 "unsupported type for " + shift_expr.id_string() + ": " +
1903 type.id_string());
1904 }
1905 else if(expr.id() == ID_rol || expr.id() == ID_ror)
1906 {
1907 const shift_exprt &shift_expr = to_shift_expr(expr);
1908 const typet &type = shift_expr.type();
1909
1910 if(
1911 type.id() == ID_unsignedbv || type.id() == ID_signedbv ||
1912 type.id() == ID_bv)
1913 {
1914 // SMT-LIB offers rotate_left and rotate_right, but these require a
1915 // constant distance.
1916 if(shift_expr.id() == ID_rol)
1917 out << "((_ rotate_left";
1918 else if(shift_expr.id() == ID_ror)
1919 out << "((_ rotate_right";
1920 else
1922
1923 out << ' ';
1924
1925 auto distance_int_op = numeric_cast<bitst>(shift_expr.distance());
1926
1927 if(distance_int_op.has_value())
1928 {
1929 out << distance_int_op.value();
1930 }
1931 else
1933 "distance type for " + shift_expr.id_string() + "must be constant");
1934
1935 out << ") ";
1936 convert_expr(shift_expr.op());
1937
1938 out << ")"; // rotate_*
1939 }
1940 else
1942 "unsupported type for " + shift_expr.id_string() + ": " +
1943 type.id_string());
1944 }
1945 else if(expr.id() == ID_named_term)
1946 {
1947 const auto &named_term_expr = to_named_term_expr(expr);
1948 out << "(! ";
1949 convert(named_term_expr.value());
1950 out << " :named "
1951 << convert_identifier(named_term_expr.symbol().identifier()) << ')';
1952 }
1953 else if(expr.id()==ID_with)
1954 {
1956 }
1957 else if(expr.id()==ID_update)
1958 {
1960 }
1961 else if(expr.id() == ID_update_bit)
1962 {
1964 }
1965 else if(expr.id() == ID_update_bits)
1966 {
1968 }
1969 else if(expr.id() == ID_object_address)
1970 {
1971 out << "(object-address ";
1973 id2string(to_object_address_expr(expr).object_identifier()));
1974 out << ')';
1975 }
1976 else if(expr.id() == ID_element_address)
1977 {
1978 // We turn this binary expression into a ternary expression
1979 // by adding the size of the array elements as third argument.
1980 const auto &element_address_expr = to_element_address_expr(expr);
1981
1982 auto element_size_expr_opt =
1983 ::size_of_expr(element_address_expr.element_type(), ns);
1984 CHECK_RETURN(element_size_expr_opt.has_value());
1985
1986 out << "(element-address-" << type2id(expr.type()) << ' ';
1987 convert_expr(element_address_expr.base());
1988 out << ' ';
1989 convert_expr(element_address_expr.index());
1990 out << ' ';
1992 *element_size_expr_opt, element_address_expr.index().type()));
1993 out << ')';
1994 }
1995 else if(expr.id() == ID_field_address)
1996 {
1997 const auto &field_address_expr = to_field_address_expr(expr);
1998 out << "(field-address-" << type2id(expr.type()) << ' ';
1999 convert_expr(field_address_expr.base());
2000 out << ' ';
2001 convert_string_literal(id2string(field_address_expr.component_name()));
2002 out << ')';
2003 }
2004 else if(expr.id()==ID_member)
2005 {
2007 }
2008 else if(expr.id()==ID_pointer_offset)
2009 {
2010 const auto &op = to_pointer_offset_expr(expr).pointer();
2011
2013 op.type().id() == ID_pointer,
2014 "operand of pointer offset expression shall be of pointer type");
2015
2016 std::size_t offset_bits =
2017 boolbv_width(op.type()) - config.bv_encoding.object_bits;
2018 std::size_t result_width=boolbv_width(expr.type());
2019
2020 // max extract width
2021 if(offset_bits>result_width)
2022 offset_bits=result_width;
2023
2024 // too few bits?
2025 if(result_width>offset_bits)
2026 out << "((_ zero_extend " << result_width-offset_bits << ") ";
2027
2028 out << "((_ extract " << offset_bits-1 << " 0) ";
2029 convert_expr(op);
2030 out << ")";
2031
2032 if(result_width>offset_bits)
2033 out << ")"; // zero_extend
2034 }
2035 else if(expr.id()==ID_pointer_object)
2036 {
2037 const auto &op = to_pointer_object_expr(expr).pointer();
2038
2040 op.type().id() == ID_pointer,
2041 "pointer object expressions should be of pointer type");
2042
2043 std::size_t ext=boolbv_width(expr.type())-config.bv_encoding.object_bits;
2044 std::size_t pointer_width = boolbv_width(op.type());
2045
2046 if(ext>0)
2047 out << "((_ zero_extend " << ext << ") ";
2048
2049 out << "((_ extract "
2050 << pointer_width-1 << " "
2051 << pointer_width-config.bv_encoding.object_bits << ") ";
2052 convert_expr(op);
2053 out << ")";
2054
2055 if(ext>0)
2056 out << ")"; // zero_extend
2057 }
2058 else if(expr.id() == ID_is_dynamic_object)
2059 {
2061 }
2062 else if(expr.id() == ID_is_invalid_pointer)
2063 {
2064 const auto &op = to_unary_expr(expr).op();
2065 std::size_t pointer_width = boolbv_width(op.type());
2066 out << "(= ((_ extract "
2067 << pointer_width-1 << " "
2068 << pointer_width-config.bv_encoding.object_bits << ") ";
2069 convert_expr(op);
2070 out << ") (_ bv" << pointer_logic.get_invalid_object()
2071 << " " << config.bv_encoding.object_bits << "))";
2072 }
2073 else if(expr.id()==ID_string_constant)
2074 {
2075 defined_expressionst::const_iterator it=defined_expressions.find(expr);
2076 CHECK_RETURN(it != defined_expressions.end());
2077 out << it->second;
2078 }
2079 else if(expr.id()==ID_extractbit)
2080 {
2081 const extractbit_exprt &extractbit_expr = to_extractbit_expr(expr);
2082
2083 if(extractbit_expr.index().is_constant())
2084 {
2085 const auto i =
2086 numeric_cast_v<bitst>(to_constant_expr(extractbit_expr.index()));
2087
2088 out << "(= ((_ extract " << i << " " << i << ") ";
2089 flatten2bv(extractbit_expr.src());
2090 out << ") #b1)";
2091 }
2092 else
2093 {
2094 // Shift the source right by the index, then check bit 0. The index is
2095 // a bit position: zero-extend both operands to the wider of the two
2096 // widths rather than using a typecast to the type of the source, which
2097 // would convert the value (e.g., scale for fixedbv, or map any non-zero
2098 // value to 1 for c_bool). Out-of-range indices then yield false.
2099 const std::size_t src_width = boolbv_width(extractbit_expr.src().type());
2100 const std::size_t idx_width =
2101 boolbv_width(extractbit_expr.index().type());
2102 const std::size_t width = std::max(src_width, idx_width);
2103
2104 out << "(= ((_ extract 0 0) ";
2105 out << "(bvlshr ";
2106 if(src_width < width)
2107 out << "((_ zero_extend " << width - src_width << ") ";
2108 flatten2bv(extractbit_expr.src());
2109 if(src_width < width)
2110 out << ')';
2111 out << ' ';
2112 if(idx_width < width)
2113 out << "((_ zero_extend " << width - idx_width << ") ";
2114 convert_expr(extractbit_expr.index());
2115 if(idx_width < width)
2116 out << ')';
2117 out << ")) #b1)"; // bvlshr, extract, =
2118 }
2119 }
2120 else if(expr.id() == ID_onehot)
2121 {
2122 convert_expr(to_onehot_expr(expr).lower());
2123 }
2124 else if(expr.id() == ID_onehot0)
2125 {
2126 convert_expr(to_onehot0_expr(expr).lower());
2127 }
2128 else if(expr.id()==ID_extractbits)
2129 {
2130 const extractbits_exprt &extractbits_expr = to_extractbits_expr(expr);
2131 auto width = boolbv_width(expr.type());
2132
2133 if(extractbits_expr.index().is_constant())
2134 {
2135 auto index_i =
2136 numeric_cast_v<bitst>(to_constant_expr(extractbits_expr.index()));
2137
2138 out << "((_ extract " << (bitst{width} + index_i - bitst{1}) << " "
2139 << index_i << ") ";
2140 flatten2bv(extractbits_expr.src());
2141 out << ")";
2142 }
2143 else
2144 {
2145 #if 0
2146 out << "(= ((_ extract 0 0) ";
2147 // the arguments of the shift need to have the same width
2148 out << "(bvlshr ";
2149 convert_expr(expr.op0());
2150 typecast_exprt tmp(expr.op0().type());
2151 tmp.op0()=expr.op1();
2152 convert_expr(tmp);
2153 out << ")) bin1)"; // bvlshr, extract, =
2154 #endif
2155 SMT2_TODO("smt2: extractbits with non-constant index");
2156 }
2157 }
2158 else if(expr.id()==ID_replication)
2159 {
2160 const replication_exprt &replication_expr = to_replication_expr(expr);
2161
2162 mp_integer times = numeric_cast_v<mp_integer>(replication_expr.times());
2163
2164 // SMT-LIB requires that repeat is given a number of repetitions that is at
2165 // least 1.
2166 PRECONDITION(times >= 1);
2167
2168 out << "((_ repeat " << times << ") ";
2169 flatten2bv(replication_expr.op());
2170 out << ")";
2171 }
2172 else if(expr.id()==ID_byte_extract_little_endian ||
2173 expr.id()==ID_byte_extract_big_endian)
2174 {
2175 INVARIANT(
2176 false, "byte_extract ops should be lowered in prepare_for_convert_expr");
2177 }
2178 else if(expr.id()==ID_byte_update_little_endian ||
2179 expr.id()==ID_byte_update_big_endian)
2180 {
2181 INVARIANT(
2182 false, "byte_update ops should be lowered in prepare_for_convert_expr");
2183 }
2184 else if(expr.id()==ID_abs)
2185 {
2186 const abs_exprt &abs_expr = to_abs_expr(expr);
2187
2188 const typet &type = abs_expr.type();
2189
2190 if(type.id()==ID_signedbv)
2191 {
2192 std::size_t result_width = to_signedbv_type(type).get_width();
2193
2194 out << "(ite (bvslt ";
2195 convert_expr(abs_expr.op());
2196 out << " (_ bv0 " << result_width << ")) ";
2197 out << "(bvneg ";
2198 convert_expr(abs_expr.op());
2199 out << ") ";
2200 convert_expr(abs_expr.op());
2201 out << ")";
2202 }
2203 else if(type.id()==ID_fixedbv)
2204 {
2205 std::size_t result_width=to_fixedbv_type(type).get_width();
2206
2207 out << "(ite (bvslt ";
2208 convert_expr(abs_expr.op());
2209 out << " (_ bv0 " << result_width << ")) ";
2210 out << "(bvneg ";
2211 convert_expr(abs_expr.op());
2212 out << ") ";
2213 convert_expr(abs_expr.op());
2214 out << ")";
2215 }
2216 else if(type.id()==ID_floatbv)
2217 {
2218 if(use_FPA_theory)
2219 {
2220 out << "(fp.abs ";
2221 convert_expr(abs_expr.op());
2222 out << ")";
2223 }
2224 else
2225 convert_floatbv(abs_expr);
2226 }
2227 else
2229 }
2230 else if(expr.id()==ID_isnan)
2231 {
2232 const isnan_exprt &isnan_expr = to_isnan_expr(expr);
2233
2234 const typet &op_type = isnan_expr.op().type();
2235
2236 if(op_type.id()==ID_fixedbv)
2237 out << "false";
2238 else if(op_type.id()==ID_floatbv)
2239 {
2240 if(use_FPA_theory)
2241 {
2242 out << "(fp.isNaN ";
2243 convert_expr(isnan_expr.op());
2244 out << ")";
2245 }
2246 else
2247 convert_floatbv(isnan_expr);
2248 }
2249 else
2251 }
2252 else if(expr.id()==ID_isfinite)
2253 {
2254 const isfinite_exprt &isfinite_expr = to_isfinite_expr(expr);
2255
2256 const typet &op_type = isfinite_expr.op().type();
2257
2258 if(op_type.id()==ID_fixedbv)
2259 out << "true";
2260 else if(op_type.id()==ID_floatbv)
2261 {
2262 if(use_FPA_theory)
2263 {
2264 out << "(and ";
2265
2266 out << "(not (fp.isNaN ";
2267 convert_expr(isfinite_expr.op());
2268 out << "))";
2269
2270 out << "(not (fp.isInfinite ";
2271 convert_expr(isfinite_expr.op());
2272 out << "))";
2273
2274 out << ")";
2275 }
2276 else
2277 convert_floatbv(isfinite_expr);
2278 }
2279 else
2281 }
2282 else if(expr.id()==ID_isinf)
2283 {
2284 const isinf_exprt &isinf_expr = to_isinf_expr(expr);
2285
2286 const typet &op_type = isinf_expr.op().type();
2287
2288 if(op_type.id()==ID_fixedbv)
2289 out << "false";
2290 else if(op_type.id()==ID_floatbv)
2291 {
2292 if(use_FPA_theory)
2293 {
2294 out << "(fp.isInfinite ";
2295 convert_expr(isinf_expr.op());
2296 out << ")";
2297 }
2298 else
2299 convert_floatbv(isinf_expr);
2300 }
2301 else
2303 }
2304 else if(expr.id()==ID_isnormal)
2305 {
2306 const isnormal_exprt &isnormal_expr = to_isnormal_expr(expr);
2307
2308 const typet &op_type = isnormal_expr.op().type();
2309
2310 if(op_type.id()==ID_fixedbv)
2311 out << "true";
2312 else if(op_type.id()==ID_floatbv)
2313 {
2314 if(use_FPA_theory)
2315 {
2316 out << "(fp.isNormal ";
2317 convert_expr(isnormal_expr.op());
2318 out << ")";
2319 }
2320 else
2321 convert_floatbv(isnormal_expr);
2322 }
2323 else
2325 }
2326 else if(
2329 expr.id() == ID_overflow_result_plus ||
2330 expr.id() == ID_overflow_result_minus)
2331 {
2332 const bool keep_result = can_cast_expr<overflow_result_exprt>(expr);
2333
2334 const auto &op0 = to_binary_expr(expr).op0();
2335 const auto &op1 = to_binary_expr(expr).op1();
2336
2338 keep_result || expr.is_boolean(),
2339 "overflow plus and overflow minus expressions shall be of Boolean type");
2340
2341 bool subtract = can_cast_expr<minus_overflow_exprt>(expr) ||
2342 expr.id() == ID_overflow_result_minus;
2343 const typet &op_type = op0.type();
2344 std::size_t width=boolbv_width(op_type);
2345
2346 if(op_type.id()==ID_signedbv)
2347 {
2348 // an overflow occurs if the top two bits of the extended sum differ
2349 out << "(let ((?sum (";
2350 out << (subtract?"bvsub":"bvadd");
2351 out << " ((_ sign_extend 1) ";
2352 convert_expr(op0);
2353 out << ")";
2354 out << " ((_ sign_extend 1) ";
2355 convert_expr(op1);
2356 out << ")))) "; // sign_extend, bvadd/sub
2357
2358 const std::string overflow_condition =
2359 "(not (= ((_ extract " + std::to_string(width) + " " +
2360 std::to_string(width) + ") ?sum) ((_ extract " +
2361 std::to_string(width - 1) + " " + std::to_string(width - 1) +
2362 ") ?sum)))";
2363
2364 if(keep_result)
2365 {
2366 const std::string result =
2367 "((_ extract " + std::to_string(width - 1) + " 0) ?sum)";
2368
2369 if(use_datatypes)
2370 {
2371 const std::string &smt_typename = datatype_map.at(expr.type());
2372
2373 // use the constructor for the Z3 datatype
2374 out << "(mk-" << smt_typename << ' ' << result << ' '
2375 << overflow_condition << ')';
2376 }
2377 else
2378 {
2379 // The struct is flattened into a bit-vector. The first component
2380 // (the result) occupies the least-significant bits, so the overflow
2381 // flag is the first operand of the concatenation -- cf. flatten2bv,
2382 // convert_struct and convert_member.
2383 out << "(concat (ite " << overflow_condition << " #b1 #b0) " << result
2384 << ')';
2385 }
2386 }
2387 else
2388 out << overflow_condition;
2389
2390 out << ")"; // let
2391 }
2392 else if(op_type.id()==ID_unsignedbv ||
2393 op_type.id()==ID_pointer)
2394 {
2395 // overflow is simply carry-out
2396 out << "(let ((?sum (" << (subtract ? "bvsub" : "bvadd");
2397 out << " ((_ zero_extend 1) ";
2398 convert_expr(op0);
2399 out << ")";
2400 out << " ((_ zero_extend 1) ";
2401 convert_expr(op1);
2402 out << "))))"; // zero_extend, bvsub/bvadd
2403 if(keep_result && !use_datatypes)
2404 {
2405 // ?sum is already the correct flattening of the struct: the result
2406 // occupies the least-significant `width` bits and the carry-out (the
2407 // overflow flag) is the most-significant bit.
2408 out << " ?sum";
2409 }
2410 else
2411 {
2412 if(keep_result && use_datatypes)
2413 {
2414 const std::string &smt_typename = datatype_map.at(expr.type());
2415
2416 // use the constructor for the Z3 datatype
2417 out << "(mk-" << smt_typename;
2418 out << " ((_ extract " << width - 1 << " 0) ?sum) ";
2419 }
2420
2421 out << "(= ";
2422 out << "((_ extract " << width << " " << width << ") ?sum)";
2423 out << "#b1)"; // =
2424
2425 if(keep_result && use_datatypes)
2426 out << ")"; // mk
2427 }
2428 out << ")"; // let
2429 }
2430 else
2432 false,
2433 "overflow check should not be performed on unsupported type",
2434 op_type.id_string());
2435 }
2436 else if(
2438 expr.id() == ID_overflow_result_mult)
2439 {
2440 const bool keep_result = can_cast_expr<overflow_result_exprt>(expr);
2441
2442 const auto &op0 = to_binary_expr(expr).op0();
2443 const auto &op1 = to_binary_expr(expr).op1();
2444
2446 keep_result || expr.is_boolean(),
2447 "overflow mult expression shall be of Boolean type");
2448
2449 // No better idea than to multiply with double the bits and then compare
2450 // with max value.
2451
2452 const typet &op_type = op0.type();
2453 std::size_t width=boolbv_width(op_type);
2454
2455 if(op_type.id()==ID_signedbv)
2456 {
2457 out << "(let ( (prod (bvmul ((_ sign_extend " << width << ") ";
2458 convert_expr(op0);
2459 out << ") ((_ sign_extend " << width << ") ";
2460 convert_expr(op1);
2461 out << ")) )) ";
2462
2463 const std::string bound = "(_ bv" + integer2string(power(2, width - 1)) +
2464 " " + std::to_string(width * 2) + ")";
2465 const std::string overflow_condition =
2466 "(or (bvsge prod " + bound + ") (bvslt prod (bvneg " + bound + ")))";
2467
2468 if(keep_result)
2469 {
2470 const std::string result =
2471 "((_ extract " + std::to_string(width - 1) + " 0) prod)";
2472
2473 if(use_datatypes)
2474 {
2475 const std::string &smt_typename = datatype_map.at(expr.type());
2476
2477 // use the constructor for the Z3 datatype
2478 out << "(mk-" << smt_typename << ' ' << result << ' '
2479 << overflow_condition << ')';
2480 }
2481 else
2482 {
2483 // The struct is flattened into a bit-vector. The first component
2484 // (the result) occupies the least-significant bits, so the overflow
2485 // flag is the first operand of the concatenation -- cf. flatten2bv,
2486 // convert_struct and convert_member.
2487 out << "(concat (ite " << overflow_condition << " #b1 #b0) " << result
2488 << ')';
2489 }
2490 }
2491 else
2492 out << overflow_condition;
2493
2494 out << ")"; // let
2495 }
2496 else if(op_type.id()==ID_unsignedbv)
2497 {
2498 out << "(let ((prod (bvmul ((_ zero_extend " << width << ") ";
2499 convert_expr(op0);
2500 out << ") ((_ zero_extend " << width << ") ";
2501 convert_expr(op1);
2502 out << ")))) ";
2503
2504 const std::string overflow_condition =
2505 "(bvuge prod (_ bv" + integer2string(power(2, width)) + " " +
2506 std::to_string(width * 2) + "))";
2507
2508 if(keep_result)
2509 {
2510 const std::string result =
2511 "((_ extract " + std::to_string(width - 1) + " 0) prod)";
2512
2513 if(use_datatypes)
2514 {
2515 const std::string &smt_typename = datatype_map.at(expr.type());
2516
2517 // use the constructor for the Z3 datatype
2518 out << "(mk-" << smt_typename << ' ' << result << ' '
2519 << overflow_condition << ')';
2520 }
2521 else
2522 {
2523 // The struct is flattened into a bit-vector. The first component
2524 // (the result) occupies the least-significant bits, so the overflow
2525 // flag is the first operand of the concatenation -- cf. flatten2bv,
2526 // convert_struct and convert_member.
2527 out << "(concat (ite " << overflow_condition << " #b1 #b0) " << result
2528 << ')';
2529 }
2530 }
2531 else
2532 out << overflow_condition;
2533
2534 out << ")"; // let
2535 }
2536 else
2538 false,
2539 "overflow check should not be performed on unsupported type",
2540 op_type.id_string());
2541 }
2542 else if(expr.id() == ID_saturating_plus || expr.id() == ID_saturating_minus)
2543 {
2544 const bool subtract = expr.id() == ID_saturating_minus;
2545 const auto &op_type = expr.type();
2546 const auto &op0 = to_binary_expr(expr).op0();
2547 const auto &op1 = to_binary_expr(expr).op1();
2548
2549 if(op_type.id() == ID_signedbv)
2550 {
2551 auto width = to_signedbv_type(op_type).get_width();
2552
2553 // compute sum with one extra bit
2554 out << "(let ((?sum (";
2555 out << (subtract ? "bvsub" : "bvadd");
2556 out << " ((_ sign_extend 1) ";
2557 convert_expr(op0);
2558 out << ")";
2559 out << " ((_ sign_extend 1) ";
2560 convert_expr(op1);
2561 out << ")))) "; // sign_extend, bvadd/sub
2562
2563 // pick one of MAX, MIN, or the sum
2564 out << "(ite (= "
2565 "((_ extract "
2566 << width << " " << width
2567 << ") ?sum) "
2568 "((_ extract "
2569 << (width - 1) << " " << (width - 1) << ") ?sum)";
2570 out << ") "; // =
2571
2572 // no overflow and no underflow case, return the sum
2573 out << "((_ extract " << width - 1 << " 0) ?sum) ";
2574
2575 // MAX
2576 out << "(ite (= ((_ extract " << width << " " << width << ") ?sum) #b0) ";
2577 convert_expr(to_signedbv_type(op_type).largest_expr());
2578
2579 // MIN
2580 convert_expr(to_signedbv_type(op_type).smallest_expr());
2581 out << ")))"; // ite, ite, let
2582 }
2583 else if(op_type.id() == ID_unsignedbv)
2584 {
2585 auto width = to_unsignedbv_type(op_type).get_width();
2586
2587 // compute sum with one extra bit
2588 out << "(let ((?sum (" << (subtract ? "bvsub" : "bvadd");
2589 out << " ((_ zero_extend 1) ";
2590 convert_expr(op0);
2591 out << ")";
2592 out << " ((_ zero_extend 1) ";
2593 convert_expr(op1);
2594 out << "))))"; // zero_extend, bvsub/bvadd
2595
2596 // pick one of MAX, MIN, or the sum
2597 out << "(ite (= ((_ extract " << width << " " << width << ") ?sum) #b0) ";
2598
2599 // no overflow and no underflow case, return the sum
2600 out << " ((_ extract " << width - 1 << " 0) ?sum) ";
2601
2602 // overflow when adding, underflow when subtracting
2603 if(subtract)
2604 convert_expr(to_unsignedbv_type(op_type).smallest_expr());
2605 else
2606 convert_expr(to_unsignedbv_type(op_type).largest_expr());
2607
2608 // MIN
2609 out << "))"; // ite, let
2610 }
2611 else
2613 false,
2614 "saturating_plus/minus on unsupported type",
2615 op_type.id_string());
2616 }
2617 else if(expr.id()==ID_array)
2618 {
2619 defined_expressionst::const_iterator it=defined_expressions.find(expr);
2620 CHECK_RETURN(it != defined_expressions.end());
2621 out << it->second;
2622 }
2623 else if(expr.id()==ID_literal)
2624 {
2625 convert_literal(to_literal_expr(expr).get_literal());
2626 }
2627 else if(expr.id()==ID_forall ||
2628 expr.id()==ID_exists)
2629 {
2630 const quantifier_exprt &quantifier_expr = to_quantifier_expr(expr);
2631
2633 // NOLINTNEXTLINE(readability/throw)
2634 throw "MathSAT does not support quantifiers";
2635
2636 if(quantifier_expr.id() == ID_forall)
2637 out << "(forall ";
2638 else if(quantifier_expr.id() == ID_exists)
2639 out << "(exists ";
2640
2641 out << '(';
2642 bool first = true;
2643 for(const auto &bound : quantifier_expr.variables())
2644 {
2645 if(first)
2646 first = false;
2647 else
2648 out << ' ';
2649 out << '(';
2650 convert_expr(bound);
2651 out << ' ';
2652 convert_type(bound.type());
2653 out << ')';
2654 }
2655 out << ") ";
2656
2657 convert_expr(quantifier_expr.where());
2658
2659 out << ')';
2660 }
2661 else if(
2663 {
2665 }
2666 else if(expr.id()==ID_let)
2667 {
2668 const let_exprt &let_expr=to_let_expr(expr);
2669 const auto &variables = let_expr.variables();
2670 const auto &values = let_expr.values();
2671
2672 out << "(let (";
2673 bool first = true;
2674
2675 for(auto &binding : make_range(variables).zip(values))
2676 {
2677 if(first)
2678 first = false;
2679 else
2680 out << ' ';
2681
2682 out << '(';
2683 convert_expr(binding.first);
2684 out << ' ';
2685 convert_expr(binding.second);
2686 out << ')';
2687 }
2688
2689 out << ") "; // bindings
2690
2691 convert_expr(let_expr.where());
2692 out << ')'; // let
2693 }
2694 else if(expr.id()==ID_constraint_select_one)
2695 {
2697 "smt2_convt::convert_expr: '" + expr.id_string() +
2698 "' is not yet supported");
2699 }
2700 else if(expr.id() == ID_bswap)
2701 {
2702 const bswap_exprt &bswap_expr = to_bswap_expr(expr);
2703
2705 bswap_expr.op().type() == bswap_expr.type(),
2706 "operand of byte swap expression shall have same type as the expression");
2707
2708 // first 'let' the operand
2709 out << "(let ((bswap_op ";
2710 convert_expr(bswap_expr.op());
2711 out << ")) ";
2712
2713 if(
2714 bswap_expr.type().id() == ID_signedbv ||
2715 bswap_expr.type().id() == ID_unsignedbv)
2716 {
2717 const std::size_t width =
2718 to_bitvector_type(bswap_expr.type()).get_width();
2719
2720 const std::size_t bits_per_byte = bswap_expr.get_bits_per_byte();
2721
2722 // width must be multiple of bytes
2724 width % bits_per_byte == 0,
2725 "bit width indicated by type of bswap expression should be a multiple "
2726 "of the number of bits per byte");
2727
2728 const std::size_t bytes = width / bits_per_byte;
2729
2730 if(bytes <= 1)
2731 out << "bswap_op";
2732 else
2733 {
2734 // do a parallel 'let' for each byte
2735 out << "(let (";
2736
2737 for(std::size_t byte = 0; byte < bytes; byte++)
2738 {
2739 if(byte != 0)
2740 out << ' ';
2741 out << "(bswap_byte_" << byte << ' ';
2742 out << "((_ extract " << (byte * bits_per_byte + (bits_per_byte - 1))
2743 << " " << (byte * bits_per_byte) << ") bswap_op)";
2744 out << ')';
2745 }
2746
2747 out << ") ";
2748
2749 // now stitch back together with 'concat'
2750 out << "(concat";
2751
2752 for(std::size_t byte = 0; byte < bytes; byte++)
2753 out << " bswap_byte_" << byte;
2754
2755 out << ')'; // concat
2756 out << ')'; // let bswap_byte_*
2757 }
2758 }
2759 else
2760 UNEXPECTEDCASE("bswap must get bitvector operand");
2761
2762 out << ')'; // let bswap_op
2763 }
2764 else if(expr.id() == ID_popcount)
2765 {
2767 }
2768 else if(expr.id() == ID_count_leading_zeros)
2769 {
2771 }
2772 else if(expr.id() == ID_count_trailing_zeros)
2773 {
2775 }
2776 else if(expr.id() == ID_find_first_set)
2777 {
2779 }
2780 else if(expr.id() == ID_bitreverse)
2781 {
2783 }
2784 else if(expr.id() == ID_zero_extend)
2785 {
2786 convert_expr(to_zero_extend_expr(expr).lower());
2787 }
2788 else if(expr.id() == ID_function_application)
2789 {
2790 const auto &function_application_expr = to_function_application_expr(expr);
2791
2792 // Front-ends such as Strata represent string and regex operations as
2793 // applications of the CPROVER string built-in functions
2794 // (ID_cprover_string_*_func / ID_cprover_regex_*_func). In the SMT-LIB
2795 // back-end these carry SMT-LIB-native operands (String / RegLan, and
2796 // scalar Int/bit-vector index arguments) -- as opposed to the
2797 // refined-string (length, char-array) representation that the SAT string
2798 // solver in src/solvers/strings consumes -- and we lower them directly to
2799 // the SMT-LIB theory-of-strings operators here.
2800 //
2801 // Operand contract (what a front-end must emit): arguments are SMT-LIB
2802 // native and in SMT-LIB operand order, so most built-ins lower to a flat
2803 // application (op arg0 arg1 ...). Specifically:
2804 // concat(s, t, ...) -> (str.++ s t ...)
2805 // length(s) -> (str.len s) : Int result
2806 // char_at(s, i) -> (str.at s i) : 1-char String
2807 // substring(s, off, len) -> (str.substr s off len) : offset+length
2808 // contains(haystack, needle) -> (str.contains haystack needle)
2809 // is_prefix(prefix, s) -> (str.prefixof prefix s)
2810 // is_suffix(suffix, s) -> (str.suffixof suffix s)
2811 // replace(s, old, new) -> (str.replace s old new) : first match
2812 // equal(s, t) -> (= s t)
2813 // index_of(s, sub[, off]) -> (str.indexof s sub off) : off defaults 0
2814 // startswith(s, prefix) -> (str.prefixof prefix s)
2815 // endswith(s, suffix) -> (str.suffixof suffix s)
2816 // is_empty(s) -> (= s "")
2817 // and the regex operators map to str.to_re / str.in_re and the re.* family
2818 // (re.range, re.++, re.*, re.+, re.opt, re.loop, re.union, re.inter,
2819 // re.comp, re.diff, re.all, re.allchar, re.none). Built-ins without an
2820 // exact SMT-LIB theory-of-strings counterpart (e.g. compare_to, of_int,
2821 // parse_int, format, case folding, trim) are intentionally not lowered and
2822 // fall through to the generic function-application handling below.
2823 //
2824 // Note: this lowering is specific to the (non-incremental) smt2_convt
2825 // back-end. The incremental SMT back-end uses a separate converter
2826 // (src/solvers/smt2_incremental) and does not support these built-ins.
2827 irep_idt fn_id;
2828 if(function_application_expr.function().id() == ID_symbol)
2829 fn_id =
2830 to_symbol_expr(function_application_expr.function()).get_identifier();
2831
2832 const auto &args = function_application_expr.arguments();
2833
2834 // Flat-application operators: lowered to (op arg0 arg1 ...) with operands
2835 // in the order given. The operands are interpreted in SMT-LIB order, which
2836 // can DIVERGE from the canonical SAT string solver's built-ins -- notably
2837 // substring is (string, offset, length) per SMT-LIB str.substr, NOT the
2838 // SAT solver's (string, start, end), and index_of's optional third operand
2839 // is a start offset. A front-end must emit these built-ins with SMT-LIB
2840 // operand semantics; the soundness guard below only catches refined-string
2841 // (array/pointer) operands, not a mismatched integer operand pair.
2842 static const std::map<irep_idt, std::string> flat_string_ops = {
2843 // string operators
2844 {ID_cprover_string_concat_func, "str.++"},
2845 {ID_cprover_string_length_func, "str.len"},
2846 {ID_cprover_string_substring_func, "str.substr"},
2847 {ID_cprover_string_char_at_func, "str.at"},
2848 {ID_cprover_string_contains_func, "str.contains"},
2849 {ID_cprover_string_is_prefix_func, "str.prefixof"},
2850 {ID_cprover_string_is_suffix_func, "str.suffixof"},
2851 {ID_cprover_string_replace_func, "str.replace"},
2852 {ID_cprover_string_equal_func, "="},
2853 // regex operators
2854 {ID_cprover_string_to_regex_func, "str.to_re"},
2855 {ID_cprover_string_in_regex_func, "str.in_re"},
2856 {ID_cprover_regex_range_func, "re.range"},
2857 {ID_cprover_regex_concat_func, "re.++"},
2858 {ID_cprover_regex_star_func, "re.*"},
2859 {ID_cprover_regex_plus_func, "re.+"},
2860 {ID_cprover_regex_opt_func, "re.opt"},
2861 {ID_cprover_regex_union_func, "re.union"},
2862 {ID_cprover_regex_inter_func, "re.inter"},
2863 {ID_cprover_regex_comp_func, "re.comp"},
2864 {ID_cprover_regex_diff_func, "re.diff"},
2865 {ID_cprover_regex_all_func, "re.all"},
2866 {ID_cprover_regex_allchar_func, "re.allchar"},
2867 {ID_cprover_regex_none_func, "re.none"}};
2868
2869 std::string smt_name;
2870 if(auto it = flat_string_ops.find(fn_id); it != flat_string_ops.end())
2871 smt_name = it->second;
2872
2873 // Operators needing a fixed operand rearrangement or wrapper.
2874 const bool is_index_of = fn_id == ID_cprover_string_index_of_func;
2875 const bool is_startswith = fn_id == ID_cprover_string_startswith_func;
2876 const bool is_endswith = fn_id == ID_cprover_string_endswith_func;
2877 const bool is_is_empty = fn_id == ID_cprover_string_is_empty_func;
2878 const bool is_regex_loop = fn_id == ID_cprover_regex_loop_func;
2879
2880 if(
2881 !smt_name.empty() || is_index_of || is_startswith || is_endswith ||
2882 is_is_empty || is_regex_loop)
2883 {
2884 // Soundness guard: this native lowering expects SMT-LIB-native operands.
2885 // The same cprover_string_*_func ids are also used with the
2886 // refined-string (length, char-array) representation consumed by the SAT
2887 // string solver; such an application carries array- or pointer-typed
2888 // operands and must NOT be lowered here, as doing so would be silently
2889 // unsound. Reject it with a clear message instead.
2890 for(const auto &arg : args)
2891 {
2892 if(arg.type().id() == ID_array || arg.type().id() == ID_pointer)
2893 {
2895 "string/regex built-in '" + id2string(fn_id) +
2896 "' reached the SMT-LIB string lowering with a refined-string "
2897 "(array/pointer) operand; the refined-string representation "
2898 "requires the SAT string solver (--refine-strings)");
2899 }
2900 }
2901
2902 if(is_index_of)
2903 {
2904 // str.indexof requires three operands; default the start offset to the
2905 // SMT-LIB Int 0 when the front-end omits it.
2906 PRECONDITION(args.size() == 2 || args.size() == 3);
2907 out << "(str.indexof ";
2908 convert_expr(args[0]);
2909 out << ' ';
2910 convert_expr(args[1]);
2911 out << ' ';
2912 if(args.size() == 3)
2913 convert_expr(args[2]);
2914 else
2915 out << '0';
2916 out << ')';
2917 }
2918 else if(is_startswith || is_endswith)
2919 {
2920 // startswith(s, prefix) / endswith(s, suffix): the affix is the second
2921 // argument, but SMT-LIB str.prefixof/str.suffixof take the affix first.
2922 PRECONDITION(args.size() == 2);
2923 out << (is_startswith ? "(str.prefixof " : "(str.suffixof ");
2924 convert_expr(args[1]);
2925 out << ' ';
2926 convert_expr(args[0]);
2927 out << ')';
2928 }
2929 else if(is_is_empty)
2930 {
2931 // is_empty(s) -> (= s "")
2932 PRECONDITION(args.size() == 1);
2933 out << "(= ";
2934 convert_expr(args[0]);
2935 out << " \"\")";
2936 }
2937 else if(is_regex_loop)
2938 {
2939 // re.loop is an indexed SMT-LIB operator: ((_ re.loop lo hi) r), where
2940 // lo and hi are numerals. Contract: loop(regex, lo, hi) with lo/hi
2941 // constant naturals.
2942 PRECONDITION(args.size() == 3);
2943 const auto lo = numeric_cast_v<mp_integer>(to_constant_expr(args[1]));
2944 const auto hi = numeric_cast_v<mp_integer>(to_constant_expr(args[2]));
2945 out << "((_ re.loop " << lo << ' ' << hi << ") ";
2946 convert_expr(args[0]);
2947 out << ')';
2948 }
2949 else if(args.empty())
2950 out << smt_name;
2951 else
2952 {
2953 out << '(' << smt_name;
2954 for(const auto &arg : args)
2955 {
2956 out << ' ';
2957 convert_expr(arg);
2958 }
2959 out << ')';
2960 }
2961 }
2962 // do not use parentheses if there function is a constant
2963 else if(function_application_expr.arguments().empty())
2964 {
2965 convert_expr(function_application_expr.function());
2966 }
2967 else
2968 {
2969 out << '(';
2970 convert_expr(function_application_expr.function());
2971 for(auto &op : function_application_expr.arguments())
2972 {
2973 out << ' ';
2974 convert_expr(op);
2975 }
2976 out << ')';
2977 }
2978 }
2979 else if(expr.id() == ID_cond)
2980 {
2981 // use the lowering
2982 convert_expr(to_cond_expr(expr).lower());
2983 }
2984 else if(expr.id() == ID_reduction_and)
2985 {
2986 convert_expr(to_reduction_and_expr(expr).lower());
2987 }
2988 else if(expr.id() == ID_reduction_nand)
2989 {
2990 convert_expr(to_reduction_nand_expr(expr).lower());
2991 }
2992 else if(expr.id() == ID_reduction_or)
2993 {
2994 convert_expr(to_reduction_or_expr(expr).lower());
2995 }
2996 else if(expr.id() == ID_reduction_nor)
2997 {
2998 convert_expr(to_reduction_nor_expr(expr).lower());
2999 }
3000 else if(expr.id() == ID_reduction_xor)
3001 {
3002 // This is the parity of the operand. No SMT-LIB 2 equivalent.
3003 // Do bit-wise. SMT-LIB 3.0 could do this with "fold bvxor".
3004 auto &op = to_reduction_xor_expr(expr).op();
3005 auto width = to_bitvector_type(op.type()).get_width();
3006 PRECONDITION(width >= 1);
3007
3008 if(width == 1)
3009 {
3010 out << "(= ";
3011 flatten2bv(op);
3012 out << " #b1)";
3013 }
3014 else
3015 {
3016 out << "(let ((?rop ";
3017 flatten2bv(op);
3018 out << ")) ";
3019
3020 // XOR all bits: extract each bit and use multi-ary bvxor
3021 out << "(= (bvxor";
3022 for(std::size_t i = 0; i < width; i++)
3023 out << " ((_ extract " << i << " " << i << ") ?rop)";
3024 out << ") #b1)";
3025
3026 out << ')'; // let
3027 }
3028 }
3029 else if(expr.id() == ID_reduction_xnor)
3030 {
3031 // This is the negation of "reduction xor"
3032 auto &op = to_reduction_xnor_expr(expr).op();
3034 }
3035 else
3037 false,
3038 "smt2_convt::convert_expr should not be applied to unsupported "
3039 "expression",
3040 expr.id_string());
3041}
3042
3044{
3045 const exprt &src = expr.op();
3046
3047 typet dest_type = expr.type();
3048
3049 if(dest_type == src.type()) // identity
3050 {
3051 convert_expr(src);
3052 return;
3053 }
3054
3055 if(dest_type.id()==ID_c_enum_tag)
3056 dest_type=ns.follow_tag(to_c_enum_tag_type(dest_type));
3057
3058 typet src_type = src.type();
3059 if(src_type.id()==ID_c_enum_tag)
3060 src_type=ns.follow_tag(to_c_enum_tag_type(src_type));
3061
3062 if(dest_type.id()==ID_bool)
3063 {
3064 // this is comparison with zero
3065 if(
3066 src_type.id() == ID_signedbv || src_type.id() == ID_unsignedbv ||
3067 src_type.id() == ID_c_bool || src_type.id() == ID_fixedbv ||
3068 src_type.id() == ID_pointer || src_type.id() == ID_integer ||
3069 src_type.id() == ID_natural || src_type.id() == ID_rational ||
3070 src_type.id() == ID_real)
3071 {
3072 out << "(not (= ";
3073 convert_expr(src);
3074 out << " ";
3075 convert_expr(from_integer(0, src_type));
3076 out << "))";
3077 }
3078 else if(src_type.id()==ID_floatbv)
3079 {
3080 if(use_FPA_theory)
3081 {
3082 out << "(not (fp.isZero ";
3083 convert_expr(src);
3084 out << "))";
3085 }
3086 else
3087 convert_floatbv(expr);
3088 }
3089 else
3090 {
3091 UNEXPECTEDCASE("TODO typecast1 "+src_type.id_string()+" -> bool");
3092 }
3093 }
3094 else if(dest_type.id()==ID_c_bool)
3095 {
3096 std::size_t to_width=boolbv_width(dest_type);
3097 out << "(ite ";
3098 out << "(not (= ";
3099 convert_expr(src);
3100 out << " ";
3101 convert_expr(from_integer(0, src_type));
3102 out << "))"; // not, =
3103 out << " (_ bv1 " << to_width << ")";
3104 out << " (_ bv0 " << to_width << ")";
3105 out << ")"; // ite
3106 }
3107 else if(dest_type.id()==ID_signedbv ||
3108 dest_type.id()==ID_unsignedbv ||
3109 dest_type.id()==ID_c_enum ||
3110 dest_type.id()==ID_bv)
3111 {
3112 std::size_t to_width=boolbv_width(dest_type);
3113
3114 if(src_type.id()==ID_signedbv || // from signedbv
3115 src_type.id()==ID_unsignedbv || // from unsigedbv
3116 src_type.id()==ID_c_bool ||
3117 src_type.id()==ID_c_enum ||
3118 src_type.id()==ID_bv)
3119 {
3120 std::size_t from_width=boolbv_width(src_type);
3121
3122 if(from_width==to_width)
3123 convert_expr(src); // ignore
3124 else if(from_width<to_width) // extend
3125 {
3126 if(
3127 src_type.id() == ID_signedbv ||
3128 (src_type.id() == ID_c_enum &&
3129 to_c_enum_type(src_type).underlying_type().id() == ID_signedbv))
3130 out << "((_ sign_extend ";
3131 else
3132 out << "((_ zero_extend ";
3133
3134 out << (to_width-from_width)
3135 << ") "; // ind
3136 convert_expr(src);
3137 out << ")";
3138 }
3139 else // chop off extra bits
3140 {
3141 out << "((_ extract " << (to_width-1) << " 0) ";
3142 convert_expr(src);
3143 out << ")";
3144 }
3145 }
3146 else if(src_type.id()==ID_fixedbv) // from fixedbv to int
3147 {
3148 const fixedbv_typet &fixedbv_type=to_fixedbv_type(src_type);
3149
3150 std::size_t from_width=fixedbv_type.get_width();
3151 std::size_t from_integer_bits=fixedbv_type.get_integer_bits();
3152 std::size_t from_fraction_bits=fixedbv_type.get_fraction_bits();
3153
3154 // we might need to round up in case of negative numbers
3155 // e.g., (int)(-1.00001)==1
3156
3157 out << "(let ((?tcop ";
3158 convert_expr(src);
3159 out << ")) ";
3160
3161 out << "(bvadd ";
3162
3163 if(to_width>from_integer_bits)
3164 {
3165 out << "((_ sign_extend "
3166 << (to_width-from_integer_bits) << ") ";
3167 out << "((_ extract " << (from_width-1) << " "
3168 << from_fraction_bits << ") ";
3169 convert_expr(src);
3170 out << "))";
3171 }
3172 else
3173 {
3174 out << "((_ extract " << (from_fraction_bits+to_width-1)
3175 << " " << from_fraction_bits << ") ";
3176 convert_expr(src);
3177 out << ")";
3178 }
3179
3180 out << " (ite (and ";
3181
3182 // some fraction bit is not zero
3183 if(from_fraction_bits == 0)
3184 out << "false";
3185 else
3186 {
3187 out << "(not (= ((_ extract " << (from_fraction_bits - 1)
3188 << " 0) ?tcop) (_ bv0 " << from_fraction_bits << ")))";
3189 }
3190
3191 // number negative
3192 out << " (= ((_ extract " << (from_width-1) << " " << (from_width-1)
3193 << ") ?tcop) #b1)";
3194
3195 out << ")"; // and
3196
3197 out << " (_ bv1 " << to_width << ") (_ bv0 " << to_width << "))"; // ite
3198 out << ")"; // bvadd
3199 out << ")"; // let
3200 }
3201 else if(src_type.id()==ID_floatbv) // from floatbv to int
3202 {
3203 if(dest_type.id()==ID_bv)
3204 {
3205 // this is _NOT_ a semantic conversion, but bit-wise
3206
3207 if(use_FPA_theory)
3208 {
3209 defined_expressionst::const_iterator it =
3210 defined_expressions.find(expr);
3211 CHECK_RETURN(it != defined_expressions.end());
3212 out << it->second;
3213 }
3214 else
3215 {
3216 // straight-forward if width matches
3217 convert_expr(src);
3218 }
3219 }
3220 else if(dest_type.id()==ID_signedbv)
3221 {
3222 // this should be floatbv_typecast, not typecast
3224 "typecast unexpected "+src_type.id_string()+" -> "+
3225 dest_type.id_string());
3226 }
3227 else if(dest_type.id()==ID_unsignedbv)
3228 {
3229 // this should be floatbv_typecast, not typecast
3231 "typecast unexpected "+src_type.id_string()+" -> "+
3232 dest_type.id_string());
3233 }
3234 }
3235 else if(src_type.id()==ID_bool) // from boolean to int
3236 {
3237 out << "(ite ";
3238 convert_expr(src);
3239
3240 if(dest_type.id()==ID_fixedbv)
3241 {
3242 fixedbv_spect spec(to_fixedbv_type(dest_type));
3243 out << " (concat (_ bv1 "
3244 << spec.integer_bits << ") " <<
3245 "(_ bv0 " << spec.get_fraction_bits() << ")) " <<
3246 "(_ bv0 " << spec.width << ")";
3247 }
3248 else
3249 {
3250 out << " (_ bv1 " << to_width << ")";
3251 out << " (_ bv0 " << to_width << ")";
3252 }
3253
3254 out << ")";
3255 }
3256 else if(src_type.id()==ID_pointer) // from pointer to int
3257 {
3258 std::size_t from_width=boolbv_width(src_type);
3259
3260 if(from_width<to_width) // extend
3261 {
3262 out << "((_ sign_extend ";
3263 out << (to_width-from_width)
3264 << ") ";
3265 convert_expr(src);
3266 out << ")";
3267 }
3268 else // chop off extra bits
3269 {
3270 out << "((_ extract " << (to_width-1) << " 0) ";
3271 convert_expr(src);
3272 out << ")";
3273 }
3274 }
3275 else if(src_type.id() == ID_integer || src_type.id() == ID_natural)
3276 {
3277 // from integer to bit-vector, must be constant
3278 if(src.is_constant())
3279 {
3281 out << "(_ bv" << i << " " << to_width << ")";
3282 }
3283 else
3284 SMT2_TODO("can't convert non-constant integer to bitvector");
3285 }
3286 else if(
3287 src_type.id() == ID_struct ||
3288 src_type.id() == ID_struct_tag) // flatten a struct to a bit-vector
3289 {
3290 if(use_datatypes)
3291 {
3292 INVARIANT(
3293 boolbv_width(src_type) == boolbv_width(dest_type),
3294 "bit vector with of source and destination type shall be equal");
3295 flatten2bv(src);
3296 }
3297 else
3298 {
3299 INVARIANT(
3300 boolbv_width(src_type) == boolbv_width(dest_type),
3301 "bit vector with of source and destination type shall be equal");
3302 convert_expr(src); // nothing else to do!
3303 }
3304 }
3305 else if(
3306 src_type.id() == ID_union ||
3307 src_type.id() == ID_union_tag) // flatten a union
3308 {
3309 INVARIANT(
3310 boolbv_width(src_type) == boolbv_width(dest_type),
3311 "bit vector with of source and destination type shall be equal");
3312 convert_expr(src); // nothing else to do!
3313 }
3314 else if(src_type.id()==ID_c_bit_field)
3315 {
3316 std::size_t from_width=boolbv_width(src_type);
3317
3318 if(from_width==to_width)
3319 convert_expr(src); // ignore
3320 else
3321 {
3323 typecast_exprt tmp(typecast_exprt(src, t), dest_type);
3324 convert_typecast(tmp);
3325 }
3326 }
3327 else
3328 {
3329 std::ostringstream e_str;
3330 e_str << src_type.id() << " -> " << dest_type.id()
3331 << " src == " << format(src);
3332 UNEXPECTEDCASE("TODO typecast2 " + e_str.str());
3333 }
3334 }
3335 else if(dest_type.id()==ID_fixedbv) // to fixedbv
3336 {
3337 const fixedbv_typet &fixedbv_type=to_fixedbv_type(dest_type);
3338 std::size_t to_fraction_bits=fixedbv_type.get_fraction_bits();
3339 std::size_t to_integer_bits=fixedbv_type.get_integer_bits();
3340
3341 if(
3342 src_type.id() == ID_unsignedbv || src_type.id() == ID_signedbv ||
3343 src_type.id() == ID_c_enum || src_type.id() == ID_c_bool)
3344 {
3345 // integer to fixedbv
3346
3347 std::size_t from_width = boolbv_width(src_type);
3348 out << "(concat ";
3349
3350 if(from_width==to_integer_bits)
3351 convert_expr(src);
3352 else if(from_width>to_integer_bits)
3353 {
3354 // too many integer bits
3355 out << "((_ extract " << (to_integer_bits-1) << " 0) ";
3356 convert_expr(src);
3357 out << ")";
3358 }
3359 else
3360 {
3361 // too few integer bits
3362 INVARIANT(
3363 from_width < to_integer_bits,
3364 "from_width should be smaller than to_integer_bits as other case "
3365 "have been handled above");
3366 if(
3367 src_type.id() == ID_unsignedbv || src_type.id() == ID_c_bool ||
3368 (src_type.id() == ID_c_enum &&
3369 to_c_enum_type(src_type).underlying_type().id() == ID_unsignedbv))
3370 {
3371 out << "((_ zero_extend " << (to_integer_bits - from_width) << ") ";
3372 convert_expr(src);
3373 out << ")";
3374 }
3375 else
3376 {
3377 out << "((_ sign_extend "
3378 << (to_integer_bits-from_width) << ") ";
3379 convert_expr(src);
3380 out << ")";
3381 }
3382 }
3383
3384 out << "(_ bv0 " << to_fraction_bits << ")";
3385 out << ")"; // concat
3386 }
3387 else if(src_type.id()==ID_bool) // bool to fixedbv
3388 {
3389 out << "(concat (concat"
3390 << " (_ bv0 " << (to_integer_bits-1) << ") ";
3391 flatten2bv(src); // produces #b0 or #b1
3392 out << ") (_ bv0 "
3393 << to_fraction_bits
3394 << "))";
3395 }
3396 else if(src_type.id()==ID_fixedbv) // fixedbv to fixedbv
3397 {
3398 const fixedbv_typet &from_fixedbv_type=to_fixedbv_type(src_type);
3399 std::size_t from_fraction_bits=from_fixedbv_type.get_fraction_bits();
3400 std::size_t from_integer_bits=from_fixedbv_type.get_integer_bits();
3401 std::size_t from_width=from_fixedbv_type.get_width();
3402
3403 out << "(let ((?tcop ";
3404 convert_expr(src);
3405 out << ")) ";
3406
3407 out << "(concat ";
3408
3409 if(to_integer_bits<=from_integer_bits)
3410 {
3411 out << "((_ extract "
3412 << (from_fraction_bits+to_integer_bits-1) << " "
3413 << from_fraction_bits
3414 << ") ?tcop)";
3415 }
3416 else
3417 {
3418 INVARIANT(
3419 to_integer_bits > from_integer_bits,
3420 "to_integer_bits should be greater than from_integer_bits as the"
3421 "other case has been handled above");
3422 out << "((_ sign_extend "
3423 << (to_integer_bits-from_integer_bits)
3424 << ") ((_ extract "
3425 << (from_width-1) << " "
3426 << from_fraction_bits
3427 << ") ?tcop))";
3428 }
3429
3430 out << " ";
3431
3432 if(to_fraction_bits<=from_fraction_bits)
3433 {
3434 out << "((_ extract "
3435 << (from_fraction_bits-1) << " "
3436 << (from_fraction_bits-to_fraction_bits)
3437 << ") ?tcop)";
3438 }
3439 else
3440 {
3441 INVARIANT(
3442 to_fraction_bits > from_fraction_bits,
3443 "to_fraction_bits should be greater than from_fraction_bits as the"
3444 "other case has been handled above");
3445 out << "(concat ((_ extract "
3446 << (from_fraction_bits-1) << " 0) ";
3447 convert_expr(src);
3448 out << ")"
3449 << " (_ bv0 " << to_fraction_bits-from_fraction_bits
3450 << "))";
3451 }
3452
3453 out << "))"; // concat, let
3454 }
3455 else
3456 UNEXPECTEDCASE("unexpected typecast to fixedbv");
3457 }
3458 else if(dest_type.id()==ID_pointer)
3459 {
3460 std::size_t to_width=boolbv_width(dest_type);
3461
3462 if(src_type.id()==ID_pointer) // pointer to pointer
3463 {
3464 // this just passes through
3465 convert_expr(src);
3466 }
3467 else if(
3468 src_type.id() == ID_unsignedbv || src_type.id() == ID_signedbv ||
3469 src_type.id() == ID_bv)
3470 {
3471 // integer to pointer
3472
3473 std::size_t from_width=boolbv_width(src_type);
3474
3475 if(from_width==to_width)
3476 convert_expr(src);
3477 else if(from_width<to_width)
3478 {
3479 out << "((_ sign_extend "
3480 << (to_width-from_width)
3481 << ") ";
3482 convert_expr(src);
3483 out << ")"; // sign_extend
3484 }
3485 else // from_width>to_width
3486 {
3487 out << "((_ extract " << to_width - 1 << " 0) ";
3488 convert_expr(src);
3489 out << ")"; // extract
3490 }
3491 }
3492 else
3493 UNEXPECTEDCASE("TODO typecast3 "+src_type.id_string()+" -> pointer");
3494 }
3495 else if(dest_type.id()==ID_range)
3496 {
3497 auto &dest_range_type = to_integer_range_type(dest_type);
3498 const auto dest_width = address_bits(dest_range_type.size());
3499 if(src_type.id() == ID_range)
3500 {
3501 // Range values are stored as (value - from). A cast between range
3502 // types must add (src_from - dest_from) to adjust the offset,
3503 // matching the SAT backend (boolbv_typecast.cpp).
3504 auto &src_range_type = to_integer_range_type(src_type);
3505 const auto src_width = address_bits(src_range_type.size());
3506 const mp_integer offset = src_range_type.from() - dest_range_type.from();
3507
3508 // First, bring the source to dest_width.
3509 const bool need_extend = src_width < dest_width;
3510 const bool need_extract = src_width > dest_width;
3511 const bool need_offset = offset != 0;
3512
3513 if(need_offset)
3514 out << "(bvadd ";
3515
3516 if(need_extend)
3517 {
3518 out << "((_ zero_extend " << dest_width - src_width << ") ";
3519 convert_expr(src);
3520 out << ')'; // zero_extend
3521 }
3522 else if(need_extract)
3523 {
3524 out << "((_ extract " << dest_width - 1 << " 0) ";
3525 convert_expr(src);
3526 out << ')'; // extract
3527 }
3528 else
3529 {
3530 convert_expr(src);
3531 }
3532
3533 if(need_offset)
3534 {
3535 // the offset may exceed the bit width, reduce it modulo 2^dest_width
3536 const mp_integer modulus = power(2, dest_width);
3537 mp_integer offset_bits = offset % modulus;
3538 if(offset_bits < 0)
3539 offset_bits += modulus;
3540 out << " (_ bv" << integer2string(offset_bits) << " " << dest_width
3541 << "))"; // bvadd
3542 }
3543 }
3544 else
3545 SMT2_TODO("typecast from " + src_type.id_string() + " to range");
3546 }
3547 else if(dest_type.id()==ID_floatbv)
3548 {
3549 // Typecast from integer to floating-point should have be been
3550 // converted to ID_floatbv_typecast during symbolic execution,
3551 // adding the rounding mode. See
3552 // smt2_convt::convert_floatbv_typecast.
3553 // The exception is bool and c_bool to float.
3554 const auto &dest_floatbv_type = to_floatbv_type(dest_type);
3555
3556 if(src_type.id()==ID_bool)
3557 {
3558 out << "(ite ";
3559 convert_expr(src);
3560 out << ' ';
3561 convert_constant(ieee_floatt::one(dest_floatbv_type).to_expr());
3562 out << ' ';
3563 convert_constant(ieee_floatt::zero(dest_floatbv_type).to_expr());
3564 out << ')';
3565 }
3566 else if(src_type.id()==ID_c_bool)
3567 {
3568 // turn into proper bool
3569 const typecast_exprt tmp(src, bool_typet());
3570 convert_typecast(typecast_exprt(tmp, dest_type));
3571 }
3572 else if(src_type.id() == ID_bv)
3573 {
3574 if(to_bv_type(src_type).get_width() != dest_floatbv_type.get_width())
3575 {
3576 UNEXPECTEDCASE("Typecast bv -> float with wrong width");
3577 }
3578
3579 if(use_FPA_theory)
3580 {
3581 out << "((_ to_fp " << dest_floatbv_type.get_e() << " "
3582 << dest_floatbv_type.get_f() + 1 << ") ";
3583 convert_expr(src);
3584 out << ')';
3585 }
3586 else
3587 convert_expr(src);
3588 }
3589 else
3590 UNEXPECTEDCASE("Unknown typecast "+src_type.id_string()+" -> float");
3591 }
3592 else if(dest_type.id() == ID_integer || dest_type.id() == ID_natural)
3593 {
3594 if(src_type.id()==ID_bool)
3595 {
3596 out << "(ite ";
3597 convert_expr(src);
3598 out <<" 1 0)";
3599 }
3600 else
3601 UNEXPECTEDCASE("Unknown typecast "+src_type.id_string()+" -> integer");
3602 }
3603 else if(dest_type.id()==ID_c_bit_field)
3604 {
3605 std::size_t from_width=boolbv_width(src_type);
3606 std::size_t to_width=boolbv_width(dest_type);
3607
3608 if(from_width==to_width)
3609 convert_expr(src); // ignore
3610 else
3611 {
3613 typecast_exprt tmp(typecast_exprt(src, t), dest_type);
3614 convert_typecast(tmp);
3615 }
3616 }
3617 else if(dest_type.id() == ID_rational)
3618 {
3619 if(src_type.id() == ID_signedbv)
3620 {
3621 // TODO: negative numbers
3622 out << "(/ ";
3623 convert_expr(src);
3624 out << " 1)";
3625 }
3626 else
3628 "Unknown typecast " + src_type.id_string() + " -> rational");
3629 }
3630 else
3632 "TODO typecast8 "+src_type.id_string()+" -> "+dest_type.id_string());
3633}
3634
3636{
3637 const exprt &src=expr.op();
3638 // const exprt &rounding_mode=expr.rounding_mode();
3639 const typet &src_type=src.type();
3640 const typet &dest_type=expr.type();
3641
3642 if(dest_type.id()==ID_floatbv)
3643 {
3644 if(src_type.id()==ID_floatbv)
3645 {
3646 // float to float
3647
3648 /* ISO 9899:1999
3649 * 6.3.1.5 Real floating types
3650 * 1 When a float is promoted to double or long double, or a
3651 * double is promoted to long double, its value is unchanged.
3652 *
3653 * 2 When a double is demoted to float, a long double is
3654 * demoted to double or float, or a value being represented in
3655 * greater precision and range than required by its semantic
3656 * type (see 6.3.1.8) is explicitly converted to its semantic
3657 * type, if the value being converted can be represented
3658 * exactly in the new type, it is unchanged. If the value
3659 * being converted is in the range of values that can be
3660 * represented but cannot be represented exactly, the result
3661 * is either the nearest higher or nearest lower representable
3662 * value, chosen in an implementation-defined manner. If the
3663 * value being converted is outside the range of values that
3664 * can be represented, the behavior is undefined.
3665 */
3666
3667 const floatbv_typet &dst=to_floatbv_type(dest_type);
3668
3669 if(use_FPA_theory)
3670 {
3671 out << "((_ to_fp " << dst.get_e() << " "
3672 << dst.get_f() + 1 << ") ";
3674 out << " ";
3675 convert_expr(src);
3676 out << ")";
3677 }
3678 else
3679 convert_floatbv(expr);
3680 }
3681 else if(src_type.id()==ID_unsignedbv)
3682 {
3683 // unsigned to float
3684
3685 /* ISO 9899:1999
3686 * 6.3.1.4 Real floating and integer
3687 * 2 When a value of integer type is converted to a real
3688 * floating type, if the value being converted can be
3689 * represented exactly in the new type, it is unchanged. If the
3690 * value being converted is in the range of values that can be
3691 * represented but cannot be represented exactly, the result is
3692 * either the nearest higher or nearest lower representable
3693 * value, chosen in an implementation-defined manner. If the
3694 * value being converted is outside the range of values that can
3695 * be represented, the behavior is undefined.
3696 */
3697
3698 const floatbv_typet &dst=to_floatbv_type(dest_type);
3699
3700 if(use_FPA_theory)
3701 {
3702 out << "((_ to_fp_unsigned " << dst.get_e() << " "
3703 << dst.get_f() + 1 << ") ";
3705 out << " ";
3706 convert_expr(src);
3707 out << ")";
3708 }
3709 else
3710 convert_floatbv(expr);
3711 }
3712 else if(src_type.id()==ID_signedbv)
3713 {
3714 // signed to float
3715
3716 const floatbv_typet &dst=to_floatbv_type(dest_type);
3717
3718 if(use_FPA_theory)
3719 {
3720 out << "((_ to_fp " << dst.get_e() << " "
3721 << dst.get_f() + 1 << ") ";
3723 out << " ";
3724 convert_expr(src);
3725 out << ")";
3726 }
3727 else
3728 convert_floatbv(expr);
3729 }
3730 else if(src_type.id()==ID_c_enum_tag)
3731 {
3732 // enum to float
3733
3734 // We first convert to 'underlying type'
3735 floatbv_typecast_exprt tmp=expr;
3736 tmp.op() = typecast_exprt(
3737 src, ns.follow_tag(to_c_enum_tag_type(src_type)).underlying_type());
3739 }
3740 else
3742 "TODO typecast11 "+src_type.id_string()+" -> "+dest_type.id_string());
3743 }
3744 else if(dest_type.id()==ID_signedbv)
3745 {
3746 if(use_FPA_theory)
3747 {
3748 std::size_t dest_width=to_signedbv_type(dest_type).get_width();
3749 out << "((_ fp.to_sbv " << dest_width << ") ";
3751 out << " ";
3752 convert_expr(src);
3753 out << ")";
3754 }
3755 else
3756 convert_floatbv(expr);
3757 }
3758 else if(dest_type.id()==ID_unsignedbv)
3759 {
3760 if(use_FPA_theory)
3761 {
3762 std::size_t dest_width=to_unsignedbv_type(dest_type).get_width();
3763 out << "((_ fp.to_ubv " << dest_width << ") ";
3765 out << " ";
3766 convert_expr(src);
3767 out << ")";
3768 }
3769 else
3770 convert_floatbv(expr);
3771 }
3772 else
3773 {
3775 "TODO typecast12 "+src_type.id_string()+" -> "+dest_type.id_string());
3776 }
3777}
3778
3781{
3782 PRECONDITION(expr.type().id() == ID_floatbv);
3783
3784 if(use_FPA_theory)
3785 {
3786 out << "(fp.roundToIntegral ";
3788 out << ' ';
3789 convert_expr(expr.op());
3790 out << ")";
3791 }
3792 else
3793 UNEXPECTEDCASE("TODO floatbv_round_to_integral without FPA");
3794}
3795
3797{
3798 const struct_typet &struct_type =
3799 expr.type().id() == ID_struct_tag
3800 ? ns.follow_tag(to_struct_tag_type(expr.type()))
3801 : to_struct_type(expr.type());
3802
3803 const struct_typet::componentst &components=
3804 struct_type.components();
3805
3807 components.size() == expr.operands().size(),
3808 "number of struct components as indicated by the struct type shall be equal"
3809 "to the number of operands of the struct expression");
3810
3811 DATA_INVARIANT(!components.empty(), "struct shall have struct components");
3812
3813 if(use_datatypes)
3814 {
3815 const std::string &smt_typename = datatype_map.at(struct_type);
3816
3817 // use the constructor for the Z3 datatype
3818 out << "(mk-" << smt_typename;
3819
3820 std::size_t i=0;
3821 for(struct_typet::componentst::const_iterator
3822 it=components.begin();
3823 it!=components.end();
3824 it++, i++)
3825 {
3826 if(is_zero_width(it->type(), ns))
3827 continue;
3828 out << " ";
3829 convert_expr(expr.operands()[i]);
3830 }
3831
3832 out << ")";
3833 }
3834 else
3835 {
3836 auto convert_operand = [this](const exprt &op) {
3837 // may need to flatten array-theory arrays in there
3838 if(op.type().id() == ID_array && use_array_theory(op))
3839 flatten_array(op);
3840 else if(op.type().id() == ID_bool)
3841 flatten2bv(op);
3842 else
3843 convert_expr(op);
3844 };
3845
3846 // SMT-LIB 2 concat is binary only
3847 std::size_t n_concat = 0;
3848 for(std::size_t i = components.size(); i > 1; i--)
3849 {
3850 if(is_zero_width(components[i - 1].type(), ns))
3851 continue;
3852 else if(i > 2 || !is_zero_width(components[0].type(), ns))
3853 {
3854 ++n_concat;
3855 out << "(concat ";
3856 }
3857
3858 convert_operand(expr.operands()[i - 1]);
3859
3860 out << " ";
3861 }
3862
3863 if(!is_zero_width(components[0].type(), ns))
3864 convert_operand(expr.op0());
3865
3866 out << std::string(n_concat, ')');
3867 }
3868}
3869
3872{
3873 const array_typet &array_type = to_array_type(expr.type());
3874 const auto &size_expr = array_type.size();
3875 // Flattening an array to a bit-vector requires a concrete size. Arrays of
3876 // unknown or non-constant size (e.g. those indexed by a mathematical
3877 // integer) can only be encoded with the SMT-LIB array theory, not
3878 // bit-blasted; report that clearly rather than aborting an invariant.
3879 if(!size_expr.is_constant())
3880 {
3882 "cannot flatten an array of non-constant size to a bit-vector; such an "
3883 "array can only be encoded with the SMT-LIB array theory");
3884 }
3885
3887 CHECK_RETURN_WITH_DIAGNOSTICS(size != 0, "can't convert zero-sized array");
3888
3889 out << "(let ((?far ";
3890 convert_expr(expr);
3891 out << ")) ";
3892
3893 for(mp_integer i=size; i!=0; --i)
3894 {
3895 if(i!=1)
3896 out << "(concat ";
3897 out << "(select ?far ";
3898 convert_expr(from_integer(i - 1, array_type.index_type()));
3899 out << ")";
3900 if(i!=1)
3901 out << " ";
3902 }
3903
3904 // close the many parentheses
3905 for(mp_integer i=size; i>1; --i)
3906 out << ")";
3907
3908 out << ")"; // let
3909}
3910
3912{
3913 const exprt &op=expr.op();
3914
3915 std::size_t total_width = boolbv_width(expr.type());
3916
3917 std::size_t member_width=boolbv_width(op.type());
3918
3919 if(total_width==member_width)
3920 {
3921 flatten2bv(op);
3922 }
3923 else
3924 {
3925 // we will pad with zeros, but non-det would be better
3926 INVARIANT(
3927 total_width > member_width,
3928 "total_width should be greater than member_width as member_width can be"
3929 "at most as large as total_width and the other case has been handled "
3930 "above");
3931 out << "(concat ";
3932 out << "(_ bv0 "
3933 << (total_width-member_width) << ") ";
3934 flatten2bv(op);
3935 out << ")";
3936 }
3937}
3938
3940{
3941 const typet &expr_type=expr.type();
3942
3943 if(expr_type.id()==ID_unsignedbv ||
3944 expr_type.id()==ID_signedbv ||
3945 expr_type.id()==ID_bv ||
3946 expr_type.id()==ID_c_enum ||
3947 expr_type.id()==ID_c_enum_tag ||
3948 expr_type.id()==ID_c_bool ||
3949 expr_type.id()==ID_c_bit_field)
3950 {
3951 const std::size_t width = boolbv_width(expr_type);
3952
3953 const mp_integer value = bvrep2integer(expr.get_value(), width, false);
3954
3955 out << "(_ bv" << value
3956 << " " << width << ")";
3957 }
3958 else if(expr_type.id()==ID_fixedbv)
3959 {
3960 const fixedbv_spect spec(to_fixedbv_type(expr_type));
3961
3962 const mp_integer v = bvrep2integer(expr.get_value(), spec.width, false);
3963
3964 out << "(_ bv" << v << " " << spec.width << ")";
3965 }
3966 else if(expr_type.id()==ID_floatbv)
3967 {
3968 const floatbv_typet &floatbv_type=
3969 to_floatbv_type(expr_type);
3970
3971 if(use_FPA_theory)
3972 {
3973 /* CBMC stores floating point literals in the most
3974 computationally useful form; biased exponents and
3975 significands including the hidden bit. Thus some encoding
3976 is needed to get to IEEE-754 style representations. */
3977
3979 size_t e=floatbv_type.get_e();
3980 size_t f=floatbv_type.get_f()+1;
3981
3982 /* Should be sufficient, but not currently supported by mathsat */
3983 #if 0
3984 mp_integer binary = v.pack();
3985
3986 out << "((_ to_fp " << e << " " << f << ")"
3987 << " #b" << integer2binary(v.pack(), v.spec.width()) << ")";
3988 #endif
3989
3990 if(v.is_NaN())
3991 {
3992 out << "(_ NaN " << e << " " << f << ")";
3993 }
3994 else if(v.is_infinity())
3995 {
3996 if(v.get_sign())
3997 out << "(_ -oo " << e << " " << f << ")";
3998 else
3999 out << "(_ +oo " << e << " " << f << ")";
4000 }
4001 else
4002 {
4003 // Zero, normal or subnormal
4004
4005 mp_integer binary = v.pack();
4006 std::string binaryString(integer2binary(v.pack(), v.spec.width()));
4007
4008 out << "(fp "
4009 << "#b" << binaryString.substr(0, 1) << " "
4010 << "#b" << binaryString.substr(1, e) << " "
4011 << "#b" << binaryString.substr(1+e, f-1) << ")";
4012 }
4013 }
4014 else
4015 {
4016 // produce corresponding bit-vector
4017 const ieee_float_spect spec(floatbv_type);
4018 const mp_integer v = bvrep2integer(expr.get_value(), spec.width(), false);
4019 out << "(_ bv" << v << " " << spec.width() << ")";
4020 }
4021 }
4022 else if(expr_type.id()==ID_pointer)
4023 {
4024 if(expr.is_null_pointer())
4025 {
4026 out << "(_ bv0 " << boolbv_width(expr_type)
4027 << ")";
4028 }
4029 else
4030 {
4031 // just treat the pointer as a bit vector
4032 const std::size_t width = boolbv_width(expr_type);
4033
4034 const mp_integer value = bvrep2integer(expr.get_value(), width, false);
4035
4036 out << "(_ bv" << value << " " << width << ")";
4037 }
4038 }
4039 else if(expr_type.id()==ID_bool)
4040 {
4041 if(expr == true)
4042 out << "true";
4043 else if(expr == false)
4044 out << "false";
4045 else
4046 UNEXPECTEDCASE("unknown Boolean constant");
4047 }
4048 else if(expr_type.id()==ID_array)
4049 {
4050 defined_expressionst::const_iterator it=defined_expressions.find(expr);
4051 CHECK_RETURN(it != defined_expressions.end());
4052 out << it->second;
4053 }
4054 else if(expr_type.id()==ID_rational)
4055 {
4056 std::string value=id2string(expr.get_value());
4057 const bool negative = has_prefix(value, "-");
4058
4059 if(negative)
4060 {
4061 out << "(- ";
4062 value = value.substr(1);
4063 }
4064
4065 size_t pos=value.find("/");
4066
4067 if(pos==std::string::npos)
4068 out << value << ".0";
4069 else
4070 {
4071 out << "(/ " << value.substr(0, pos) << ".0 "
4072 << value.substr(pos+1) << ".0)";
4073 }
4074
4075 if(negative)
4076 out << ')';
4077 }
4078 else if(expr_type.id() == ID_real)
4079 {
4080 const std::string &value = id2string(expr.get_value());
4081 out << value;
4082 if(value.find('.') == std::string::npos)
4083 out << ".0";
4084 }
4085 else if(expr_type.id()==ID_integer)
4086 {
4087 const auto value = id2string(expr.get_value());
4088
4089 // SMT2 has no negative integer literals
4090 if(has_prefix(value, "-"))
4091 out << "(- " << value.substr(1, std::string::npos) << ')';
4092 else
4093 out << value;
4094 }
4095 else if(expr_type.id() == ID_natural)
4096 {
4097 out << expr.get_value();
4098 }
4099 else if(expr_type.id() == ID_range)
4100 {
4101 auto &range_type = to_integer_range_type(expr_type);
4102 const auto width = address_bits(range_type.size());
4103 const auto value_int = numeric_cast_v<mp_integer>(expr);
4104 out << "(_ bv" << (value_int - range_type.from()) << " " << width << ")";
4105 }
4106 else if(expr_type.id() == ID_string)
4107 {
4108 // SMT-LIB 2.6 string literal. The only in-string escape is "" for a double
4109 // quote (backslash is literal). Only printable ASCII may appear verbatim;
4110 // control and non-ASCII bytes are encoded with the \u{...} hex escape.
4111 const std::string &value = id2string(expr.get_value());
4112 out << '"';
4113 for(char ch : value)
4114 {
4115 const auto c = static_cast<unsigned char>(ch);
4116 if(c == '"')
4117 out << "\"\"";
4118 else if(c >= 0x20 && c <= 0x7e)
4119 out << ch;
4120 else
4121 out << "\\u{" << std::hex << static_cast<unsigned>(c) << std::dec
4122 << '}';
4123 }
4124 out << '"';
4125 }
4126 else
4127 UNEXPECTEDCASE("unknown constant: "+expr_type.id_string());
4128}
4129
4131{
4132 if(expr.type().id() == ID_integer)
4133 {
4134 out << "(mod ";
4135 convert_expr(expr.op0());
4136 out << ' ';
4137 convert_expr(expr.op1());
4138 out << ')';
4139 }
4140 else
4142 "unsupported type for euclidean_mod: " + expr.type().id_string());
4143}
4144
4146{
4147 if(expr.type().id()==ID_unsignedbv ||
4148 expr.type().id()==ID_signedbv)
4149 {
4150 if(expr.type().id()==ID_unsignedbv)
4151 out << "(bvurem ";
4152 else
4153 out << "(bvsrem ";
4154
4155 convert_expr(expr.op0());
4156 out << " ";
4157 convert_expr(expr.op1());
4158 out << ")";
4159 }
4160 else if(expr.type().id() == ID_integer)
4161 {
4162 // Mathematical integers (mp_integer) truncate toward zero, so the
4163 // remainder takes the sign of the dividend; SMT-LIB mod is always
4164 // non-negative. Take the remainder of the magnitudes and re-apply the
4165 // dividend's sign.
4166 out << "(let ((?ma ";
4167 convert_expr(expr.op0());
4168 out << ") (?mb ";
4169 convert_expr(expr.op1());
4170 out << ")) (let ((?mr (mod (ite (< ?ma 0) (- ?ma) ?ma)";
4171 out << " (ite (< ?mb 0) (- ?mb) ?mb)))) (ite (< ?ma 0) (- ?mr) ?mr)))";
4172 }
4173 else if(expr.type().id() == ID_natural)
4174 {
4175 // Naturals are non-negative, so SMT-LIB mod already matches mp_integer.
4176 out << "(mod ";
4177 convert_expr(expr.op0());
4178 out << " ";
4179 convert_expr(expr.op1());
4180 out << ")";
4181 }
4182 else
4183 UNEXPECTEDCASE("unsupported type for mod: "+expr.type().id_string());
4184}
4185
4187{
4188 std::vector<mp_integer> dynamic_objects;
4189 pointer_logic.get_dynamic_objects(dynamic_objects);
4190
4191 if(dynamic_objects.empty())
4192 out << "false";
4193 else
4194 {
4195 std::size_t pointer_width = boolbv_width(expr.op().type());
4196
4197 out << "(let ((?obj ((_ extract "
4198 << pointer_width-1 << " "
4199 << pointer_width-config.bv_encoding.object_bits << ") ";
4200 convert_expr(expr.op());
4201 out << "))) ";
4202
4203 if(dynamic_objects.size()==1)
4204 {
4205 out << "(= (_ bv" << dynamic_objects.front()
4206 << " " << config.bv_encoding.object_bits << ") ?obj)";
4207 }
4208 else
4209 {
4210 out << "(or";
4211
4212 for(const auto &object : dynamic_objects)
4213 out << " (= (_ bv" << object
4214 << " " << config.bv_encoding.object_bits << ") ?obj)";
4215
4216 out << ")"; // or
4217 }
4218
4219 out << ")"; // let
4220 }
4221}
4222
4224{
4225 const typet &op_type=expr.op0().type();
4226
4227 if(
4228 op_type.id() == ID_unsignedbv || op_type.id() == ID_bv ||
4229 op_type.id() == ID_range)
4230 {
4231 // The range type is encoded in binary
4232 out << "(";
4233 if(expr.id()==ID_le)
4234 out << "bvule";
4235 else if(expr.id()==ID_lt)
4236 out << "bvult";
4237 else if(expr.id()==ID_ge)
4238 out << "bvuge";
4239 else if(expr.id()==ID_gt)
4240 out << "bvugt";
4241
4242 out << " ";
4243 convert_expr(expr.op0());
4244 out << " ";
4245 convert_expr(expr.op1());
4246 out << ")";
4247 }
4248 else if(op_type.id()==ID_signedbv ||
4249 op_type.id()==ID_fixedbv)
4250 {
4251 out << "(";
4252 if(expr.id()==ID_le)
4253 out << "bvsle";
4254 else if(expr.id()==ID_lt)
4255 out << "bvslt";
4256 else if(expr.id()==ID_ge)
4257 out << "bvsge";
4258 else if(expr.id()==ID_gt)
4259 out << "bvsgt";
4260
4261 out << " ";
4262 convert_expr(expr.op0());
4263 out << " ";
4264 convert_expr(expr.op1());
4265 out << ")";
4266 }
4267 else if(op_type.id()==ID_floatbv)
4268 {
4269 if(use_FPA_theory)
4270 {
4271 out << "(";
4272 if(expr.id()==ID_le)
4273 out << "fp.leq";
4274 else if(expr.id()==ID_lt)
4275 out << "fp.lt";
4276 else if(expr.id()==ID_ge)
4277 out << "fp.geq";
4278 else if(expr.id()==ID_gt)
4279 out << "fp.gt";
4280
4281 out << " ";
4282 convert_expr(expr.op0());
4283 out << " ";
4284 convert_expr(expr.op1());
4285 out << ")";
4286 }
4287 else
4288 convert_floatbv(expr);
4289 }
4290 else if(
4291 op_type.id() == ID_rational || op_type.id() == ID_integer ||
4292 op_type.id() == ID_natural || op_type.id() == ID_real)
4293 {
4294 out << "(";
4295 out << expr.id();
4296
4297 out << " ";
4298 convert_expr(expr.op0());
4299 out << " ";
4300 convert_expr(expr.op1());
4301 out << ")";
4302 }
4303 else if(op_type.id() == ID_pointer)
4304 {
4305 const exprt same_object = ::same_object(expr.op0(), expr.op1());
4306
4307 out << "(and ";
4309
4310 out << " (";
4311 if(expr.id() == ID_le)
4312 out << "bvsle";
4313 else if(expr.id() == ID_lt)
4314 out << "bvslt";
4315 else if(expr.id() == ID_ge)
4316 out << "bvsge";
4317 else if(expr.id() == ID_gt)
4318 out << "bvsgt";
4319
4320 out << ' ';
4322 out << ' ';
4324 out << ')';
4325
4326 out << ')';
4327 }
4328 else
4330 "unsupported type for "+expr.id_string()+": "+op_type.id_string());
4331}
4332
4334{
4335 if(
4336 expr.type().id() == ID_rational || expr.type().id() == ID_integer ||
4337 expr.type().id() == ID_natural || expr.type().id() == ID_real)
4338 {
4339 // these are multi-ary in SMT-LIB2
4340 out << "(+";
4341
4342 for(const auto &op : expr.operands())
4343 {
4344 out << ' ';
4345 convert_expr(op);
4346 }
4347
4348 out << ')';
4349 }
4350 else if(
4351 expr.type().id() == ID_unsignedbv || expr.type().id() == ID_signedbv ||
4352 expr.type().id() == ID_fixedbv)
4353 {
4354 // These could be chained, i.e., need not be binary,
4355 // but at least MathSat doesn't like that.
4356 if(expr.operands().size() == 2)
4357 {
4358 out << "(bvadd ";
4359 convert_expr(expr.op0());
4360 out << " ";
4361 convert_expr(expr.op1());
4362 out << ")";
4363 }
4364 else
4365 {
4367 }
4368 }
4369 else if(expr.type().id() == ID_range)
4370 {
4371 auto &range_type = to_integer_range_type(expr.type());
4372
4373 // These could be chained, i.e., need not be binary,
4374 // but at least MathSat doesn't like that.
4375 if(expr.operands().size() == 2)
4376 {
4377 // add: lhs + from + rhs + from - from = lhs + rhs + from
4378 const auto width = address_bits(range_type.size());
4379
4380 out << "(bvadd ";
4381 convert_expr(expr.op0());
4382 out << " (bvadd ";
4383 convert_expr(expr.op1());
4384 out << " (_ bv" << range_type.from() << ' ' << width
4385 << ")))"; // bv, bvadd, bvadd
4386 }
4387 else
4388 {
4390 }
4391 }
4392 else if(expr.type().id() == ID_floatbv)
4393 {
4394 // Floating-point additions should have be been converted
4395 // to ID_floatbv_plus during symbolic execution, adding
4396 // the rounding mode. See smt2_convt::convert_floatbv_plus.
4398 }
4399 else if(expr.type().id() == ID_pointer)
4400 {
4401 if(expr.operands().size() == 2)
4402 {
4403 exprt p = expr.op0(), i = expr.op1();
4404
4405 if(p.type().id() != ID_pointer)
4406 p.swap(i);
4407
4409 p.type().id() == ID_pointer,
4410 "one of the operands should have pointer type");
4411
4412 const auto &base_type = to_pointer_type(expr.type()).base_type();
4414 base_type.id() != ID_empty, "no pointer arithmetic over void pointers");
4415
4416 auto element_size_opt = pointer_offset_size(base_type, ns);
4418 element_size_opt.has_value() && *element_size_opt >= bytest{0});
4419 bytest element_size = *element_size_opt;
4420
4421 // First convert the pointer operand
4422 out << "(let ((?pointerop ";
4423 convert_expr(p);
4424 out << ")) ";
4425
4426 // The addition is done on the offset part only.
4427 const std::size_t pointer_width = boolbv_width(p.type());
4428 const std::size_t offset_bits =
4429 pointer_width - config.bv_encoding.object_bits;
4430
4431 out << "(concat ";
4432 out << "((_ extract " << pointer_width - 1 << ' ' << offset_bits
4433 << ") ?pointerop) ";
4434 out << "(bvadd ((_ extract " << offset_bits - 1 << " 0) ?pointerop) ";
4435
4436 if(element_size >= bytest{2})
4437 {
4438 out << "(bvmul ((_ extract " << offset_bits - 1 << " 0) ";
4439 convert_expr(i);
4440 out << ") (_ bv" << element_size << " " << offset_bits << "))";
4441 }
4442 else
4443 {
4444 out << "((_ extract " << offset_bits - 1 << " 0) ";
4445 convert_expr(i);
4446 out << ')'; // extract
4447 }
4448
4449 out << ")))"; // bvadd, concat, let
4450 }
4451 else
4452 {
4454 }
4455 }
4456 else
4457 UNEXPECTEDCASE("unsupported type for +: " + expr.type().id_string());
4458}
4459
4464{
4466
4467 /* CProver uses the x86 numbering of the rounding-mode
4468 * 0 == FE_TONEAREST
4469 * 1 == FE_DOWNWARD
4470 * 2 == FE_UPWARD
4471 * 3 == FE_TOWARDZERO
4472 * These literal values must be used rather than the macros
4473 * the macros from fenv.h to avoid portability problems.
4474 */
4475
4476 if(expr.is_constant())
4477 {
4478 const constant_exprt &cexpr=to_constant_expr(expr);
4479
4481
4482 if(value==0)
4483 out << "roundNearestTiesToEven";
4484 else if(value==1)
4485 out << "roundTowardNegative";
4486 else if(value==2)
4487 out << "roundTowardPositive";
4488 else if(value==3)
4489 out << "roundTowardZero";
4490 else if(value == 4)
4491 out << "roundNearestTiesToAway";
4492 else
4494 false,
4495 "Rounding mode should have value 0, 1, 2, 3, or 4",
4496 id2string(cexpr.get_value()));
4497 }
4498 else
4499 {
4500 std::size_t width=to_bitvector_type(expr.type()).get_width();
4501
4502 // Need to make the choice above part of the model
4503 out << "(ite (= (_ bv0 " << width << ") ";
4504 convert_expr(expr);
4505 out << ") roundNearestTiesToEven ";
4506
4507 out << "(ite (= (_ bv1 " << width << ") ";
4508 convert_expr(expr);
4509 out << ") roundTowardNegative ";
4510
4511 out << "(ite (= (_ bv2 " << width << ") ";
4512 convert_expr(expr);
4513 out << ") roundTowardPositive ";
4514
4515 out << "(ite (= (_ bv3 " << width << ") ";
4516 convert_expr(expr);
4517 out << ") roundTowardZero ";
4518
4519 // TODO: add some kind of error checking here
4520 out << "roundNearestTiesToAway";
4521
4522 out << "))))";
4523 }
4524}
4525
4527{
4528 const typet &type=expr.type();
4529
4531 type.id() == ID_floatbv ||
4532 (type.id() == ID_complex &&
4533 to_complex_type(type).subtype().id() == ID_floatbv));
4534
4535 if(use_FPA_theory)
4536 {
4537 if(type.id()==ID_floatbv)
4538 {
4539 out << "(fp.add ";
4541 out << " ";
4542 convert_expr(expr.lhs());
4543 out << " ";
4544 convert_expr(expr.rhs());
4545 out << ")";
4546 }
4547 else if(type.id()==ID_complex)
4548 {
4549 SMT2_TODO("+ for floatbv complex");
4550 }
4551 else
4553 false,
4554 "type should not be one of the unsupported types",
4555 type.id_string());
4556 }
4557 else
4558 convert_floatbv(expr);
4559}
4560
4562{
4563 if(
4564 expr.type().id() == ID_integer || expr.type().id() == ID_natural ||
4565 expr.type().id() == ID_rational || expr.type().id() == ID_real)
4566 {
4567 out << "(- ";
4568 convert_expr(expr.op0());
4569 out << " ";
4570 convert_expr(expr.op1());
4571 out << ")";
4572 }
4573 else if(expr.type().id()==ID_unsignedbv ||
4574 expr.type().id()==ID_signedbv ||
4575 expr.type().id()==ID_fixedbv)
4576 {
4577 if(expr.op0().type().id()==ID_pointer &&
4578 expr.op1().type().id()==ID_pointer)
4579 {
4580 // Pointer difference
4581 const auto &base_type = to_pointer_type(expr.op0().type()).base_type();
4583 base_type.id() != ID_empty, "no pointer arithmetic over void pointers");
4584 auto element_size_opt = pointer_offset_size(base_type, ns);
4586 element_size_opt.has_value() && *element_size_opt >= bytest{1});
4587 bytest element_size = *element_size_opt;
4588
4589 if(element_size >= bytest{2})
4590 out << "(bvsdiv ";
4591
4592 INVARIANT(
4593 boolbv_width(expr.op0().type()) == boolbv_width(expr.type()),
4594 "bitvector width of operand shall be equal to the bitvector width of "
4595 "the expression");
4596
4597 out << "(bvsub ";
4598 convert_expr(expr.op0());
4599 out << " ";
4600 convert_expr(expr.op1());
4601 out << ")";
4602
4603 if(element_size >= bytest{2})
4604 out << " (_ bv" << element_size << " " << boolbv_width(expr.type())
4605 << "))";
4606 }
4607 else
4608 {
4609 out << "(bvsub ";
4610 convert_expr(expr.op0());
4611 out << " ";
4612 convert_expr(expr.op1());
4613 out << ")";
4614 }
4615 }
4616 else if(expr.type().id()==ID_floatbv)
4617 {
4618 // Floating-point subtraction should have be been converted
4619 // to ID_floatbv_minus during symbolic execution, adding
4620 // the rounding mode. See smt2_convt::convert_floatbv_minus.
4622 }
4623 else if(expr.type().id()==ID_pointer)
4624 {
4625 if(
4626 expr.op0().type().id() == ID_pointer &&
4627 (expr.op1().type().id() == ID_unsignedbv ||
4628 expr.op1().type().id() == ID_signedbv))
4629 {
4630 // rewrite p-o to p+(-o)
4631 return convert_plus(
4632 plus_exprt(expr.op0(), unary_minus_exprt(expr.op1())));
4633 }
4634 else
4636 "unsupported operand types for -: " + expr.op0().type().id_string() +
4637 " and " + expr.op1().type().id_string());
4638 }
4639 else if(expr.type().id() == ID_range)
4640 {
4641 auto &range_type = to_integer_range_type(expr.type());
4642
4643 // sub: lhs + from - (rhs + from) - from = lhs - rhs - from
4644 const auto width = address_bits(range_type.size());
4645
4646 out << "(bvsub (bvsub ";
4647 convert_expr(expr.op0());
4648 out << ' ';
4649 convert_expr(expr.op1());
4650 out << ") (_ bv" << range_type.from() << ' ' << width << "))"; // bv, bvsub
4651 }
4652 else
4653 UNEXPECTEDCASE("unsupported type for -: "+expr.type().id_string());
4654}
4655
4657{
4659 expr.type().id() == ID_floatbv,
4660 "type of ieee floating point expression shall be floatbv");
4661
4662 if(use_FPA_theory)
4663 {
4664 out << "(fp.sub ";
4666 out << " ";
4667 convert_expr(expr.lhs());
4668 out << " ";
4669 convert_expr(expr.rhs());
4670 out << ")";
4671 }
4672 else
4673 convert_floatbv(expr);
4674}
4675
4677{
4678 if(expr.type().id()==ID_unsignedbv ||
4679 expr.type().id()==ID_signedbv)
4680 {
4681 if(expr.type().id()==ID_unsignedbv)
4682 out << "(bvudiv ";
4683 else
4684 out << "(bvsdiv ";
4685
4686 convert_expr(expr.op0());
4687 out << " ";
4688 convert_expr(expr.op1());
4689 out << ")";
4690 }
4691 else if(expr.type().id()==ID_fixedbv)
4692 {
4693 fixedbv_spect spec(to_fixedbv_type(expr.type()));
4694 std::size_t fraction_bits=spec.get_fraction_bits();
4695
4696 out << "((_ extract " << spec.width-1 << " 0) ";
4697 out << "(bvsdiv ";
4698
4699 out << "(concat ";
4700 convert_expr(expr.op0());
4701 out << " (_ bv0 " << fraction_bits << ")) ";
4702
4703 out << "((_ sign_extend " << fraction_bits << ") ";
4704 convert_expr(expr.op1());
4705 out << ")";
4706
4707 out << "))";
4708 }
4709 else if(expr.type().id()==ID_floatbv)
4710 {
4711 // Floating-point division should have be been converted
4712 // to ID_floatbv_div during symbolic execution, adding
4713 // the rounding mode. See smt2_convt::convert_floatbv_div.
4715 }
4716 else if(
4717 expr.type().id() == ID_rational || expr.type().id() == ID_integer ||
4718 expr.type().id() == ID_natural || expr.type().id() == ID_real)
4719 {
4720 if(expr.type().id() == ID_integer)
4721 {
4722 // Mathematical integers (mp_integer) truncate division toward zero,
4723 // whereas SMT-LIB div floors. Encode truncation: divide the magnitudes
4724 // and make the quotient negative iff the operands have opposite signs.
4725 out << "(let ((?da ";
4726 convert_expr(expr.op0());
4727 out << ") (?db ";
4728 convert_expr(expr.op1());
4729 out << ")) (let ((?dq (div (ite (< ?da 0) (- ?da) ?da)";
4730 out << " (ite (< ?db 0) (- ?db) ?db))))";
4731 out << " (ite (= (< ?da 0) (< ?db 0)) ?dq (- ?dq))))";
4732 }
4733 else
4734 {
4735 // Naturals are non-negative (SMT-LIB div already truncates); rationals
4736 // and reals use real division.
4737 if(expr.type().id() == ID_natural)
4738 out << "(div ";
4739 else
4740 out << "(/ ";
4741 convert_expr(expr.op0());
4742 out << " ";
4743 convert_expr(expr.op1());
4744 out << ")";
4745 }
4746 }
4747 else
4748 UNEXPECTEDCASE("unsupported type for /: "+expr.type().id_string());
4749}
4750
4752{
4754 expr.type().id() == ID_floatbv,
4755 "type of ieee floating point expression shall be floatbv");
4756
4757 if(use_FPA_theory)
4758 {
4759 out << "(fp.div ";
4761 out << " ";
4762 convert_expr(expr.lhs());
4763 out << " ";
4764 convert_expr(expr.rhs());
4765 out << ")";
4766 }
4767 else
4768 convert_floatbv(expr);
4769}
4770
4772{
4773 // re-write to binary if needed
4774 if(expr.operands().size()>2)
4775 {
4776 // strip last operand
4777 exprt tmp=expr;
4778 tmp.operands().pop_back();
4779
4780 // recursive call
4781 return convert_mult(mult_exprt(tmp, expr.operands().back()));
4782 }
4783
4784 INVARIANT(
4785 expr.operands().size() == 2,
4786 "expression should have been converted to a variant with two operands");
4787
4788 if(expr.type().id()==ID_unsignedbv ||
4789 expr.type().id()==ID_signedbv)
4790 {
4791 // Note that bvmul is really unsigned,
4792 // but this is irrelevant as we chop-off any extra result
4793 // bits.
4794 out << "(bvmul ";
4795 convert_expr(expr.op0());
4796 out << " ";
4797 convert_expr(expr.op1());
4798 out << ")";
4799 }
4800 else if(expr.type().id()==ID_floatbv)
4801 {
4802 // Floating-point multiplication should have be been converted
4803 // to ID_floatbv_mult during symbolic execution, adding
4804 // the rounding mode. See smt2_convt::convert_floatbv_mult.
4806 }
4807 else if(expr.type().id()==ID_fixedbv)
4808 {
4809 fixedbv_spect spec(to_fixedbv_type(expr.type()));
4810 std::size_t fraction_bits=spec.get_fraction_bits();
4811
4812 out << "((_ extract "
4813 << spec.width+fraction_bits-1 << " "
4814 << fraction_bits << ") ";
4815
4816 out << "(bvmul ";
4817
4818 out << "((_ sign_extend " << fraction_bits << ") ";
4819 convert_expr(expr.op0());
4820 out << ") ";
4821
4822 out << "((_ sign_extend " << fraction_bits << ") ";
4823 convert_expr(expr.op1());
4824 out << ")";
4825
4826 out << "))"; // bvmul, extract
4827 }
4828 else if(
4829 expr.type().id() == ID_rational || expr.type().id() == ID_integer ||
4830 expr.type().id() == ID_natural || expr.type().id() == ID_real)
4831 {
4832 out << "(*";
4833
4834 for(const auto &op : expr.operands())
4835 {
4836 out << " ";
4837 convert_expr(op);
4838 }
4839
4840 out << ")";
4841 }
4842 else
4843 UNEXPECTEDCASE("unsupported type for *: "+expr.type().id_string());
4844}
4845
4847{
4849 expr.type().id() == ID_floatbv,
4850 "type of ieee floating point expression shall be floatbv");
4851
4852 if(use_FPA_theory)
4853 {
4854 out << "(fp.mul ";
4856 out << " ";
4857 convert_expr(expr.lhs());
4858 out << " ";
4859 convert_expr(expr.rhs());
4860 out << ")";
4861 }
4862 else
4863 convert_floatbv(expr);
4864}
4865
4867{
4869 expr.type().id() == ID_floatbv,
4870 "type of ieee floating point expression shall be floatbv");
4871
4872 if(use_FPA_theory)
4873 {
4874 // Note that these do not have a rounding mode
4875 out << "(fp.rem ";
4876 convert_expr(expr.lhs());
4877 out << " ";
4878 convert_expr(expr.rhs());
4879 out << ")";
4880 }
4881 else
4882 {
4883 SMT2_TODO(
4884 "smt2_convt::convert_floatbv_rem to be implemented when not using "
4885 "FPA_theory");
4886 }
4887}
4888
4890{
4892 expr.type().id() == ID_floatbv,
4893 "type of ieee floating point expression shall be floatbv");
4894
4895 if(use_FPA_theory)
4896 {
4897 out << "(fp.fma ";
4899 out << " ";
4901 out << " ";
4903 out << " ";
4904 convert_expr(expr.op_add());
4905 out << ")";
4906 }
4907 else
4908 convert_floatbv(expr);
4909}
4910
4912{
4913 INVARIANT(
4914 expr.operands().size() == 3,
4915 "with expression should have exactly three operands");
4916
4917 const typet &expr_type = expr.type();
4918
4919 if(expr_type.id()==ID_array)
4920 {
4921 const array_typet &array_type=to_array_type(expr_type);
4922
4923 if(use_array_theory(expr))
4924 {
4925 out << "(store ";
4926 convert_expr(expr.old());
4927 out << " ";
4928 convert_expr(typecast_exprt(expr.where(), array_type.index_type()));
4929 out << " ";
4930 convert_expr(expr.new_value());
4931 out << ")";
4932 }
4933 else
4934 {
4935 // fixed-width
4936 std::size_t array_width=boolbv_width(array_type);
4937 std::size_t sub_width = boolbv_width(array_type.element_type());
4938 std::size_t index_width=boolbv_width(expr.where().type());
4939
4940 // We mask out the updated bits with AND,
4941 // and then OR-in the shifted new value.
4942
4943 out << "(let ((distance? ";
4944 out << "(bvmul (_ bv" << sub_width << " " << array_width << ") ";
4945
4946 // SMT2 says that the shift distance needs to be as wide
4947 // as the stuff we are shifting.
4948 if(array_width>index_width)
4949 {
4950 out << "((_ zero_extend " << array_width-index_width << ") ";
4951 convert_expr(expr.where());
4952 out << ")";
4953 }
4954 else
4955 {
4956 out << "((_ extract " << array_width-1 << " 0) ";
4957 convert_expr(expr.where());
4958 out << ")";
4959 }
4960
4961 out << "))) "; // bvmul, distance?
4962
4963 out << "(bvor ";
4964 out << "(bvand ";
4965 out << "(bvnot ";
4966 out << "(bvshl (_ bv" << power(2, sub_width) - 1 << " " << array_width
4967 << ") ";
4968 out << "distance?)) "; // bvnot, bvlshl
4969 convert_expr(expr.old());
4970 out << ") "; // bvand
4971 out << "(bvshl ";
4972 out << "((_ zero_extend " << array_width-sub_width << ") ";
4973 convert_expr(expr.new_value());
4974 out << ") distance?)))"; // zero_extend, bvshl, bvor, let
4975 }
4976 }
4977 else if(expr_type.id() == ID_struct || expr_type.id() == ID_struct_tag)
4978 {
4979 const struct_typet &struct_type =
4980 expr_type.id() == ID_struct_tag
4981 ? ns.follow_tag(to_struct_tag_type(expr_type))
4982 : to_struct_type(expr_type);
4983
4984 const exprt &index = expr.where();
4985 const exprt &value = expr.new_value();
4986
4987 const irep_idt &component_name=index.get(ID_component_name);
4988
4989 INVARIANT(
4990 struct_type.has_component(component_name),
4991 "struct should have accessed component");
4992
4993 if(use_datatypes)
4994 {
4995 const std::string &smt_typename = datatype_map.at(expr_type);
4996
4997 out << "(" << datatype_update_name(smt_typename, component_name) << " ";
4998 convert_expr(expr.old());
4999 out << " ";
5000 convert_expr(value);
5001 out << ")";
5002 }
5003 else
5004 {
5005 auto convert_operand = [this](const exprt &op)
5006 {
5007 // may need to flatten array-theory arrays in there
5008 if(op.type().id() == ID_array && use_array_theory(op))
5009 flatten_array(op);
5010 else if(op.type().id() == ID_bool)
5011 flatten2bv(op);
5012 else
5013 convert_expr(op);
5014 };
5015
5016 std::size_t struct_width=boolbv_width(struct_type);
5017
5018 // figure out the offset and width of the member
5019 const boolbv_widtht::membert &m =
5020 boolbv_width.get_member(struct_type, component_name);
5021
5022 if(m.width==struct_width)
5023 {
5024 // the struct is the same as the member, no concat needed
5025 convert_operand(value);
5026 }
5027 else
5028 {
5029 out << "(let ((?withop ";
5030 convert_operand(expr.old());
5031 out << ")) ";
5032
5033 if(m.offset == 0)
5034 {
5035 // the member is at the beginning
5036 out << "(concat "
5037 << "((_ extract " << (struct_width - 1) << " " << m.width
5038 << ") ?withop) ";
5039 convert_operand(value);
5040 out << ")"; // concat
5041 }
5042 else if(m.offset + m.width == struct_width)
5043 {
5044 // the member is at the end
5045 out << "(concat ";
5046 convert_operand(value);
5047 out << " ((_ extract " << (m.offset - 1) << " 0) ?withop))";
5048 }
5049 else
5050 {
5051 // most general case, need two concat-s
5052 out << "(concat (concat "
5053 << "((_ extract " << (struct_width - 1) << " "
5054 << (m.offset + m.width) << ") ?withop) ";
5055 convert_operand(value);
5056 out << ") ((_ extract " << (m.offset - 1) << " 0) ?withop)";
5057 out << ")"; // concat
5058 }
5059
5060 out << ")"; // let ?withop
5061 }
5062 }
5063 }
5064 else if(expr_type.id() == ID_union || expr_type.id() == ID_union_tag)
5065 {
5066 const exprt &value = expr.new_value();
5067
5068 std::size_t total_width = boolbv_width(expr_type);
5069
5070 std::size_t member_width=boolbv_width(value.type());
5071
5072 if(total_width==member_width)
5073 {
5074 flatten2bv(value);
5075 }
5076 else
5077 {
5078 INVARIANT(
5079 total_width > member_width,
5080 "total width should be greater than member_width as member_width is at "
5081 "most as large as total_width and the other case has been handled "
5082 "above");
5083 out << "(concat ";
5084 out << "((_ extract "
5085 << (total_width-1)
5086 << " " << member_width << ") ";
5087 convert_expr(expr.old());
5088 out << ") ";
5089 flatten2bv(value);
5090 out << ")";
5091 }
5092 }
5093 else if(expr_type.id()==ID_bv ||
5094 expr_type.id()==ID_unsignedbv ||
5095 expr_type.id()==ID_signedbv)
5096 {
5097 if(expr.new_value().type().id() == ID_bool)
5098 {
5100 update_bit_exprt(expr.old(), expr.where(), expr.new_value()));
5101 }
5102 else
5103 {
5105 update_bits_exprt(expr.old(), expr.where(), expr.new_value()));
5106 }
5107 }
5108 else
5110 "with expects struct, union, or array type, but got "+
5111 expr.type().id_string());
5112}
5113
5115{
5116 PRECONDITION(expr.operands().size() == 3);
5117
5118 SMT2_TODO("smt2_convt::convert_update to be implemented");
5119}
5120
5122{
5123 return convert_expr(expr.lower());
5124}
5125
5127{
5128 return convert_expr(expr.lower());
5129}
5130
5132{
5133 const typet &array_op_type = expr.array().type();
5134
5135 if(array_op_type.id()==ID_array)
5136 {
5137 const array_typet &array_type=to_array_type(array_op_type);
5138
5139 if(use_array_theory(expr.array()))
5140 {
5141 if(expr.is_boolean() && !use_array_of_bool)
5142 {
5143 out << "(= ";
5144 out << "(select ";
5145 convert_expr(expr.array());
5146 out << " ";
5147 convert_expr(typecast_exprt(expr.index(), array_type.index_type()));
5148 out << ")";
5149 out << " #b1)";
5150 }
5151 else
5152 {
5153 out << "(select ";
5154 convert_expr(expr.array());
5155 out << " ";
5156 convert_expr(typecast_exprt(expr.index(), array_type.index_type()));
5157 out << ")";
5158 }
5159 }
5160 else
5161 {
5162 // fixed size
5163 std::size_t array_width=boolbv_width(array_type);
5164
5165 unflatten(wheret::BEGIN, array_type.element_type());
5166
5167 std::size_t sub_width = boolbv_width(array_type.element_type());
5168 std::size_t index_width=boolbv_width(expr.index().type());
5169
5170 out << "((_ extract " << sub_width-1 << " 0) ";
5171 out << "(bvlshr ";
5172 convert_expr(expr.array());
5173 out << " ";
5174 out << "(bvmul (_ bv" << sub_width << " " << array_width << ") ";
5175
5176 // SMT2 says that the shift distance must be the same as
5177 // the width of what we shift.
5178 if(array_width>index_width)
5179 {
5180 out << "((_ zero_extend " << array_width-index_width << ") ";
5181 convert_expr(expr.index());
5182 out << ")"; // zero_extend
5183 }
5184 else
5185 {
5186 out << "((_ extract " << array_width-1 << " 0) ";
5187 convert_expr(expr.index());
5188 out << ")"; // extract
5189 }
5190
5191 out << ")))"; // mult, bvlshr, extract
5192
5193 unflatten(wheret::END, array_type.element_type());
5194 }
5195 }
5196 else
5197 INVARIANT(
5198 false, "index with unsupported array type: " + array_op_type.id_string());
5199}
5200
5202{
5203 const member_exprt &member_expr=to_member_expr(expr);
5204 const exprt &struct_op=member_expr.struct_op();
5205 const typet &struct_op_type = struct_op.type();
5206 const irep_idt &name=member_expr.get_component_name();
5207
5208 if(struct_op_type.id() == ID_struct || struct_op_type.id() == ID_struct_tag)
5209 {
5210 const struct_typet &struct_type =
5211 struct_op_type.id() == ID_struct_tag
5212 ? ns.follow_tag(to_struct_tag_type(struct_op_type))
5213 : to_struct_type(struct_op_type);
5214
5215 INVARIANT(
5216 struct_type.has_component(name), "struct should have accessed component");
5217
5218 if(use_datatypes)
5219 {
5220 const std::string &smt_typename = datatype_map.at(struct_type);
5221
5222 out << "("
5224 smt_typename, struct_type.get_component(name).get_name())
5225 << " ";
5226 convert_expr(struct_op);
5227 out << ")";
5228 }
5229 else
5230 {
5231 // we extract
5232 const auto &member_offset = boolbv_width.get_member(struct_type, name);
5233
5234 if(expr.type().id() == ID_bool)
5235 out << "(= ";
5236 out << "((_ extract " << (member_offset.offset + member_offset.width - 1)
5237 << " " << member_offset.offset << ") ";
5238 convert_expr(struct_op);
5239 out << ")";
5240 if(expr.type().id() == ID_bool)
5241 out << " #b1)";
5242 }
5243 }
5244 else if(
5245 struct_op_type.id() == ID_union || struct_op_type.id() == ID_union_tag)
5246 {
5247 std::size_t width=boolbv_width(expr.type());
5249 width != 0, "failed to get union member width");
5250
5251 if(use_datatypes)
5252 {
5253 unflatten(wheret::BEGIN, expr.type());
5254
5255 out << "((_ extract " << (width - 1) << " 0) ";
5256 convert_expr(struct_op);
5257 out << ")";
5258
5259 unflatten(wheret::END, expr.type());
5260 }
5261 else
5262 {
5263 out << "((_ extract " << (width - 1) << " 0) ";
5264 convert_expr(struct_op);
5265 out << ")";
5266 }
5267 }
5268 else
5270 "convert_member on an unexpected type "+struct_op_type.id_string());
5271}
5272
5274{
5275 const typet &type = expr.type();
5276
5277 if(type.id()==ID_bool)
5278 {
5279 out << "(ite ";
5280 convert_expr(expr); // this returns a Bool
5281 out << " #b1 #b0)"; // this is a one-bit bit-vector
5282 }
5283 else if(type.id()==ID_array)
5284 {
5285 if(use_array_theory(expr))
5286 {
5287 // concatenate elements
5288 const array_typet &array_type = to_array_type(type);
5289
5290 mp_integer size =
5292
5293 // SMT-LIB 2 concat is binary only
5294 std::size_t n_concat = 0;
5295 for(mp_integer i = size; i > 1; --i)
5296 {
5297 ++n_concat;
5298 out << "(concat ";
5299
5300 flatten2bv(
5301 index_exprt{expr, from_integer(i - 1, array_type.index_type())});
5302
5303 out << " ";
5304 }
5305
5306 flatten2bv(index_exprt{expr, from_integer(0, array_type.index_type())});
5307
5308 out << std::string(n_concat, ')'); // concat
5309 }
5310 else
5311 convert_expr(expr);
5312 }
5313 else if(type.id() == ID_struct || type.id() == ID_struct_tag)
5314 {
5315 if(use_datatypes)
5316 {
5317 // concatenate elements
5318 const struct_typet &struct_type =
5319 type.id() == ID_struct_tag ? ns.follow_tag(to_struct_tag_type(type))
5320 : to_struct_type(type);
5321
5322 const struct_typet::componentst &components=
5323 struct_type.components();
5324
5325 // SMT-LIB 2 concat is binary only
5326 std::size_t n_concat = 0;
5327 for(std::size_t i=components.size(); i>1; i--)
5328 {
5329 if(is_zero_width(components[i - 1].type(), ns))
5330 continue;
5331 else if(i > 2 || !is_zero_width(components[0].type(), ns))
5332 {
5333 ++n_concat;
5334 out << "(concat ";
5335 }
5336
5337 flatten2bv(member_exprt{expr, components[i - 1]});
5338
5339 out << " ";
5340 }
5341
5342 if(!is_zero_width(components[0].type(), ns))
5343 {
5344 flatten2bv(member_exprt{expr, components[0]});
5345 }
5346
5347 out << std::string(n_concat, ')'); // concat
5348 }
5349 else
5350 convert_expr(expr);
5351 }
5352 else if(type.id()==ID_floatbv)
5353 {
5354 if(use_FPA_theory)
5355 {
5356 // A floatbv constant's IEEE-754 interchange bit pattern is exactly its
5357 // bit-vector representation, so it is emitted as a literal bit-vector.
5358 // This is the only shape that reaches flatten2bv under FPA: a
5359 // non-constant float whose bits are read is lowered by
5360 // lower_byte_operators into a float typecast, which is handled by the
5361 // bvfromfloat round-trip in find_symbols and never reaches here.
5362 if(expr.is_constant())
5363 {
5364 const ieee_float_spect spec(to_floatbv_type(type));
5365 const mp_integer value = bvrep2integer(
5366 to_constant_expr(expr).get_value(), spec.width(), false);
5367 out << "(_ bv" << value << " " << spec.width() << ")";
5368 }
5369 else
5370 {
5372 "flatten2bv of a non-constant FPA-encoded float is unsupported");
5373 }
5374 }
5375 else
5376 convert_expr(expr);
5377 }
5378 else
5379 convert_expr(expr);
5380}
5381
5383 wheret where,
5384 const typet &type,
5385 unsigned nesting)
5386{
5387 if(type.id()==ID_bool)
5388 {
5389 if(where==wheret::BEGIN)
5390 out << "(= "; // produces a bool
5391 else
5392 out << " #b1)";
5393 }
5394 else if(type.id() == ID_array)
5395 {
5397
5398 if(where == wheret::BEGIN)
5399 out << "(let ((?ufop" << nesting << " ";
5400 else
5401 {
5402 out << ")) ";
5403
5404 const array_typet &array_type = to_array_type(type);
5405
5406 std::size_t subtype_width = boolbv_width(array_type.element_type());
5407
5409 array_type.size().is_constant(),
5410 "cannot unflatten arrays of non-constant size");
5411 mp_integer size =
5413
5414 for(mp_integer i = 1; i < size; ++i)
5415 out << "(store ";
5416
5417 // Build a constant array filled with element 0 as the base, then
5418 // overwrite indices 1..N-1 via (store ...).
5419 if(use_as_const)
5420 {
5421 out << "((as const ";
5422 convert_type(array_type);
5423 out << ") ";
5424 }
5425 else
5426 {
5427 INVARIANT(
5429 "unflatten relies on `(lambda ...)` for constant arrays "
5430 "when `(as const ...)` is unavailable");
5431 // Note: lambda is a Z3/Bitwuzla extension; not part of the
5432 // SMT-LIB 2.6 standard. The bound variable `?ufidx<n>` is
5433 // intentionally unused -- the body returns the element-0 value
5434 // regardless of its argument, making this semantically
5435 // equivalent to `(as const ...)`.
5436 out << "(lambda ((?ufidx" << nesting << " ";
5437 convert_type(array_type.index_type());
5438 out << ")) ";
5439 }
5440 // use element at index 0 as default value
5441 unflatten(wheret::BEGIN, array_type.element_type(), nesting + 1);
5442 out << "((_ extract " << subtype_width - 1 << " "
5443 << "0) ?ufop" << nesting << ")";
5444 unflatten(wheret::END, array_type.element_type(), nesting + 1);
5445 out << ") ";
5446
5447 std::size_t offset = subtype_width;
5448 for(mp_integer i = 1; i < size; ++i, offset += subtype_width)
5449 {
5450 convert_expr(from_integer(i, array_type.index_type()));
5451 out << ' ';
5452 unflatten(wheret::BEGIN, array_type.element_type(), nesting + 1);
5453 out << "((_ extract " << offset + subtype_width - 1 << " " << offset
5454 << ") ?ufop" << nesting << ")";
5455 unflatten(wheret::END, array_type.element_type(), nesting + 1);
5456 out << ")"; // store
5457 }
5458
5459 out << ")"; // let
5460 }
5461 }
5462 else if(type.id() == ID_struct || type.id() == ID_struct_tag)
5463 {
5464 if(use_datatypes)
5465 {
5466 // extract members
5467 if(where==wheret::BEGIN)
5468 out << "(let ((?ufop" << nesting << " ";
5469 else
5470 {
5471 out << ")) ";
5472
5473 const std::string &smt_typename = datatype_map.at(type);
5474
5475 out << "(mk-" << smt_typename;
5476
5477 const struct_typet &struct_type =
5478 type.id() == ID_struct_tag ? ns.follow_tag(to_struct_tag_type(type))
5479 : to_struct_type(type);
5480
5481 const struct_typet::componentst &components=
5482 struct_type.components();
5483
5484 std::size_t offset=0;
5485
5486 for(struct_typet::componentst::const_iterator it = components.begin();
5487 it != components.end();
5488 it++)
5489 {
5490 if(is_zero_width(it->type(), ns))
5491 continue;
5492
5493 std::size_t member_width=boolbv_width(it->type());
5494
5495 out << " ";
5496 unflatten(wheret::BEGIN, it->type(), nesting+1);
5497 out << "((_ extract " << offset+member_width-1 << " "
5498 << offset << ") ?ufop" << nesting << ")";
5499 unflatten(wheret::END, it->type(), nesting+1);
5500 offset+=member_width;
5501 }
5502
5503 out << "))"; // mk-, let
5504 }
5505 }
5506 else
5507 {
5508 // nop, already a bv
5509 }
5510 }
5511 else
5512 {
5513 // nop
5514 }
5515}
5516
5517void smt2_convt::set_to(const exprt &expr, bool value)
5518{
5519 PRECONDITION(expr.is_boolean());
5520
5521 if(expr.id()==ID_and && value)
5522 {
5523 for(const auto &op : expr.operands())
5524 set_to(op, true);
5525 return;
5526 }
5527
5528 if(expr.id()==ID_or && !value)
5529 {
5530 for(const auto &op : expr.operands())
5531 set_to(op, false);
5532 return;
5533 }
5534
5535 if(expr.id()==ID_not)
5536 {
5537 return set_to(to_not_expr(expr).op(), !value);
5538 }
5539
5540 out << "\n";
5541
5542 // special treatment for "set_to(a=b, true)" where
5543 // a is a new symbol
5544
5545 if(expr.id() == ID_equal && value)
5546 {
5547 const equal_exprt &equal_expr=to_equal_expr(expr);
5548 if(is_zero_width(equal_expr.lhs().type(), ns))
5549 {
5550 // ignore equality checking over expressions with empty (void) type
5551 return;
5552 }
5553
5554 if(equal_expr.lhs().id()==ID_symbol)
5555 {
5556 const irep_idt &identifier =
5557 to_symbol_expr(equal_expr.lhs()).identifier();
5558
5559 // A symbol that is not yet declared and that is equated to an
5560 // expression is defined by that expression. This is not possible
5561 // when the expression refers to the symbol itself, e.g.,
5562 // x == (x & y) | z: such an equality is a constraint on x, and is
5563 // asserted below.
5564 if(
5565 identifier_map.find(identifier) == identifier_map.end() &&
5566 equal_expr.lhs() != equal_expr.rhs() &&
5567 !has_symbol_expr(equal_expr.rhs(), identifier, true))
5568 {
5569 auto id_entry = identifier_map.insert(
5570 {identifier, identifiert{equal_expr.lhs().type(), false}});
5571 CHECK_RETURN(id_entry.second);
5572
5573 find_symbols(id_entry.first->second.type);
5574 exprt prepared_rhs = prepare_for_convert_expr(equal_expr.rhs());
5575
5576 std::string smt2_identifier=convert_identifier(identifier);
5577 smt2_identifiers.insert(smt2_identifier);
5578
5579 out << "; set_to true (equal)\n";
5580
5581 // Helper: emit the body of a definition for `smt2_identifier`
5582 // -- either a direct `convert_expr(prepared_rhs)` for non-array
5583 // or array-theory cases, or a `unflatten ... convert_expr ...
5584 // unflatten` reconstruction for array RHSes. Used twice below
5585 // to keep the `declare-fun + assert` and `define-fun` paths in
5586 // sync.
5587 auto emit_definition_body = [&]()
5588 {
5589 if(
5590 equal_expr.lhs().type().id() != ID_array ||
5591 use_array_theory(prepared_rhs))
5592 {
5593 convert_expr(prepared_rhs);
5594 }
5595 else
5596 {
5597 unflatten(wheret::BEGIN, equal_expr.lhs().type());
5598 convert_expr(prepared_rhs);
5599 unflatten(wheret::END, equal_expr.lhs().type());
5600 }
5601 };
5602
5603 if(equal_expr.lhs().type().id() == ID_mathematical_function)
5604 {
5605 // We avoid define-fun, since it has been reported to cause
5606 // trouble with Z3's parser.
5607 out << "(declare-fun " << smt2_identifier;
5608
5609 auto &mathematical_function_type =
5610 to_mathematical_function_type(equal_expr.lhs().type());
5611
5612 out << " (";
5613 bool first = true;
5614
5615 for(auto &t : mathematical_function_type.domain())
5616 {
5617 if(first)
5618 first = false;
5619 else
5620 out << ' ';
5621
5622 convert_type(t);
5623 }
5624
5625 out << ") ";
5626 convert_type(mathematical_function_type.codomain());
5627 out << ")\n";
5628
5629 out << "(assert (= " << smt2_identifier << ' ';
5630 convert_expr(prepared_rhs);
5631 out << ')' << ')' << '\n';
5632 }
5633 else if(use_lambda_for_array)
5634 {
5635 // The body emitted below may contain a `(lambda ...)` from
5636 // `unflatten` (used as a stand-in for `(as const ...)` for
5637 // back-ends with `use_as_const = false`). Z3 rejects
5638 // `get-value` on symbols whose `define-fun` body contains
5639 // a lambda, so we use `declare-fun` + `assert (= ...)` here.
5640 // Back-ends with `use_lambda_for_array = false` (the
5641 // default, currently every back-end other than Z3) keep
5642 // using the `define-fun` form below, so their SMT2 output
5643 // is unaffected.
5644 out << "(declare-fun " << smt2_identifier;
5645 out << " () ";
5646 convert_type(equal_expr.lhs().type());
5647 out << ")\n";
5648 out << "(assert (= " << smt2_identifier << ' ';
5649 emit_definition_body();
5650 out << "))\n";
5651 }
5652 else
5653 {
5654 out << "(define-fun " << smt2_identifier;
5655 out << " () ";
5656 convert_type(equal_expr.lhs().type());
5657 out << ' ';
5658 emit_definition_body();
5659 out << ')' << '\n';
5660 }
5661
5662 return; // done
5663 }
5664 }
5665 }
5666
5667 exprt prepared_expr = prepare_for_convert_expr(expr);
5668
5669#if 0
5670 out << "; CONV: "
5671 << format(expr) << "\n";
5672#endif
5673
5674 out << "; set_to " << (value?"true":"false") << "\n"
5675 << "(assert ";
5676 if(!value)
5677 {
5678 out << "(not ";
5679 }
5680 const auto found_literal = defined_expressions.find(expr);
5681 if(!(found_literal == defined_expressions.end()))
5682 {
5683 // This is a converted expression, we can just assert the literal name
5684 // since the expression is already defined
5685 out << found_literal->second;
5686 set_values[found_literal->second] = value;
5687 }
5688 else
5689 {
5690 convert_expr(prepared_expr);
5691 }
5692 if(!value)
5693 {
5694 out << ")";
5695 }
5696 out << ")\n";
5697 return;
5698}
5699
5707{
5708 exprt lowered_expr = expr;
5709
5710 for(auto it = lowered_expr.depth_begin(), itend = lowered_expr.depth_end();
5711 it != itend;
5712 ++it)
5713 {
5714 if(
5715 it->id() == ID_byte_extract_little_endian ||
5716 it->id() == ID_byte_extract_big_endian)
5717 {
5718 it.mutate() = lower_byte_extract(to_byte_extract_expr(*it), ns);
5719 }
5720 else if(
5721 it->id() == ID_byte_update_little_endian ||
5722 it->id() == ID_byte_update_big_endian)
5723 {
5724 it.mutate() = lower_byte_update(to_byte_update_expr(*it), ns);
5725 }
5726 }
5727
5728 return lowered_expr;
5729}
5730
5739{
5740 // First, replace byte operators, because they may introduce new array
5741 // expressions that must be seen by find_symbols:
5742 exprt lowered_expr = lower_byte_operators(expr);
5743 INVARIANT(
5744 !has_byte_operator(lowered_expr),
5745 "lower_byte_operators should remove all byte operators");
5746
5747 // Perform rewrites that may introduce new symbols
5748 for(auto it = lowered_expr.depth_begin(), itend = lowered_expr.depth_end();
5749 it != itend;) // no ++it
5750 {
5751 if(
5752 auto prophecy_r_or_w_ok =
5754 {
5755 exprt lowered = simplify_expr(prophecy_r_or_w_ok->lower(ns), ns);
5756 it.mutate() = lowered;
5757 it.next_sibling_or_parent();
5758 }
5759 else if(
5760 auto prophecy_pointer_in_range =
5762 {
5763 exprt lowered = simplify_expr(prophecy_pointer_in_range->lower(ns), ns);
5764 it.mutate() = lowered;
5765 it.next_sibling_or_parent();
5766 }
5767 else
5768 ++it;
5769 }
5770
5771 // Now create symbols for all composite expressions present in lowered_expr:
5772 find_symbols(lowered_expr);
5773
5774 return lowered_expr;
5775}
5776
5787{
5788 if(is_zero_width(expr.type(), ns))
5789 return;
5790
5791 // recursive call on type
5792 find_symbols(expr.type());
5793
5794 if(expr.id() == ID_exists || expr.id() == ID_forall)
5795 {
5796 std::unordered_map<irep_idt, std::optional<identifiert>> shadowed_syms;
5797
5798 // do not declare the quantified symbol, but record
5799 // as 'bound symbol'
5800 const auto &q_expr = to_quantifier_expr(expr);
5801 for(const auto &symbol : q_expr.variables())
5802 {
5803 const auto identifier = symbol.identifier();
5804 auto id_entry =
5805 identifier_map.insert({identifier, identifiert{symbol.type(), true}});
5806 shadowed_syms.insert(
5807 {identifier,
5808 id_entry.second ? std::nullopt
5809 : std::optional{id_entry.first->second}});
5810 }
5811 find_symbols(q_expr.where());
5812 for(const auto &[id, shadowed_val] : shadowed_syms)
5813 {
5814 auto previous_entry = identifier_map.find(id);
5815 if(!shadowed_val.has_value())
5816 identifier_map.erase(previous_entry);
5817 else
5818 previous_entry->second = std::move(*shadowed_val);
5819 }
5820 return;
5821 }
5822
5823 // recursive call on operands
5824 for(const auto &op : expr.operands())
5825 find_symbols(op);
5826
5827 if(expr.id()==ID_symbol ||
5828 expr.id()==ID_nondet_symbol)
5829 {
5830 // we don't track function-typed symbols
5831 if(expr.type().id()==ID_code)
5832 return;
5833
5834 irep_idt identifier;
5835
5836 if(expr.id()==ID_symbol)
5837 identifier = to_symbol_expr(expr).identifier();
5838 else
5839 identifier="nondet_"+
5840 id2string(to_nondet_symbol_expr(expr).get_identifier());
5841
5842 auto id_entry =
5843 identifier_map.insert({identifier, identifiert{expr.type(), false}});
5844
5845 if(id_entry.second)
5846 {
5847 std::string smt2_identifier=convert_identifier(identifier);
5848 smt2_identifiers.insert(smt2_identifier);
5849
5850 out << "; find_symbols\n";
5851 out << "(declare-fun " << smt2_identifier;
5852
5853 if(expr.type().id() == ID_mathematical_function)
5854 {
5855 auto &mathematical_function_type =
5857 out << " (";
5858 bool first = true;
5859
5860 for(auto &type : mathematical_function_type.domain())
5861 {
5862 if(first)
5863 first = false;
5864 else
5865 out << ' ';
5866 convert_type(type);
5867 }
5868
5869 out << ") ";
5870 convert_type(mathematical_function_type.codomain());
5871 }
5872 else
5873 {
5874 out << " () ";
5875 convert_type(expr.type());
5876 }
5877
5878 out << ')' << '\n';
5879
5880 // We need an additional constraint for range-typed symbols,
5881 // or otherwise we get satisfying assignments with values
5882 // outside of the range when the size of the range isn't
5883 // a power of two.
5884 if(expr.type().id() == ID_range)
5885 {
5886 auto &range_type = to_integer_range_type(expr.type());
5887 if(!is_power_of_two(range_type.size()))
5888 {
5889 out << "(assert (bvule " << smt2_identifier << ' ';
5890 convert_expr(from_integer(range_type.to(), range_type));
5891 out << "))\n"; // bvule, assert
5892 }
5893 }
5894 }
5895 }
5896 else if(expr.id() == ID_array_of)
5897 {
5898 if(!use_as_const)
5899 {
5900 if(defined_expressions.find(expr) == defined_expressions.end())
5901 {
5902 const auto &array_of = to_array_of_expr(expr);
5903 const auto &array_type = array_of.type();
5904
5905 const irep_idt id =
5906 "array_of." + std::to_string(defined_expressions.size());
5907 out << "; the following is a substitute for lambda i. x\n";
5908 out << "(declare-fun " << id << " () ";
5909 convert_type(array_type);
5910 out << ")\n";
5911
5912 if(!is_zero_width(array_type.element_type(), ns))
5913 {
5914 // use a quantifier-based initialization instead of lambda
5915 out << "(assert (forall ((i ";
5916 convert_type(array_type.index_type());
5917 out << ")) (= (select " << id << " i) ";
5918 if(array_type.element_type().id() == ID_bool && !use_array_of_bool)
5919 {
5920 out << "(ite ";
5921 convert_expr(array_of.what());
5922 out << " #b1 #b0)";
5923 }
5924 else
5925 {
5926 convert_expr(array_of.what());
5927 }
5928 out << ")))\n";
5929 }
5930
5931 defined_expressions[expr] = id;
5932 }
5933 }
5934 }
5935 else if(expr.id() == ID_array_comprehension)
5936 {
5938 {
5939 if(defined_expressions.find(expr) == defined_expressions.end())
5940 {
5941 const auto &array_comprehension = to_array_comprehension_expr(expr);
5942 const auto &array_type = array_comprehension.type();
5943 const auto &array_size = array_type.size();
5944
5945 const irep_idt id =
5946 "array_comprehension." + std::to_string(defined_expressions.size());
5947 out << "(declare-fun " << id << " () ";
5948 convert_type(array_type);
5949 out << ")\n";
5950
5951 out << "; the following is a substitute for lambda i . x(i)\n";
5952 out << "; universally quantified initialization of the array\n";
5953 out << "(assert (forall ((";
5954 convert_expr(array_comprehension.arg());
5955 out << " ";
5956 convert_type(array_size.type());
5957 out << ")) (=> (and (bvule (_ bv0 " << boolbv_width(array_size.type())
5958 << ") ";
5959 convert_expr(array_comprehension.arg());
5960 out << ") (bvult ";
5961 convert_expr(array_comprehension.arg());
5962 out << " ";
5963 convert_expr(array_size);
5964 out << ")) (= (select " << id << " ";
5965 convert_expr(array_comprehension.arg());
5966 out << ") ";
5967 if(array_type.element_type().id() == ID_bool && !use_array_of_bool)
5968 {
5969 out << "(ite ";
5970 convert_expr(array_comprehension.body());
5971 out << " #b1 #b0)";
5972 }
5973 else
5974 {
5975 convert_expr(array_comprehension.body());
5976 }
5977 out << "))))\n";
5978
5979 defined_expressions[expr] = id;
5980 }
5981 }
5982 }
5983 else if(expr.id()==ID_array)
5984 {
5985 if(defined_expressions.find(expr)==defined_expressions.end())
5986 {
5987 const array_typet &array_type=to_array_type(expr.type());
5988
5989 const irep_idt id = "array." + std::to_string(defined_expressions.size());
5990 out << "; the following is a substitute for an array constructor" << "\n";
5991 out << "(declare-fun " << id << " () ";
5992 convert_type(array_type);
5993 out << ")" << "\n";
5994
5995 if(!is_zero_width(array_type.element_type(), ns))
5996 {
5997 for(std::size_t i = 0; i < expr.operands().size(); i++)
5998 {
5999 out << "(assert (= (select " << id << " ";
6000 convert_expr(from_integer(i, array_type.index_type()));
6001 out << ") "; // select
6002 if(array_type.element_type().id() == ID_bool && !use_array_of_bool)
6003 {
6004 out << "(ite ";
6005 convert_expr(expr.operands()[i]);
6006 out << " #b1 #b0)";
6007 }
6008 else
6009 {
6010 convert_expr(expr.operands()[i]);
6011 }
6012 out << "))"
6013 << "\n"; // =, assert
6014 }
6015 }
6016
6017 defined_expressions[expr]=id;
6018 }
6019 }
6020 else if(expr.id()==ID_string_constant)
6021 {
6022 if(defined_expressions.find(expr)==defined_expressions.end())
6023 {
6024 // introduce a temporary array.
6026 const array_typet &array_type=to_array_type(tmp.type());
6027
6028 const irep_idt id =
6029 "string." + std::to_string(defined_expressions.size());
6030 out << "; the following is a substitute for a string" << "\n";
6031 out << "(declare-fun " << id << " () ";
6032 convert_type(array_type);
6033 out << ")" << "\n";
6034
6035 for(std::size_t i=0; i<tmp.operands().size(); i++)
6036 {
6037 out << "(assert (= (select " << id << ' ';
6038 convert_expr(from_integer(i, array_type.index_type()));
6039 out << ") "; // select
6040 convert_expr(tmp.operands()[i]);
6041 out << "))" << "\n";
6042 }
6043
6044 defined_expressions[expr]=id;
6045 }
6046 }
6047 else if(
6049 {
6050 if(object_sizes.find(*object_size) == object_sizes.end())
6051 {
6052 const irep_idt id = convert_identifier(
6053 "object_size." + std::to_string(object_sizes.size()));
6054 out << "(declare-fun " << id << " () ";
6055 convert_type(object_size->type());
6056 out << ")"
6057 << "\n";
6058
6060 }
6061 }
6062 // clang-format off
6063 else if(!use_FPA_theory &&
6064 expr.operands().size() >= 1 &&
6065 (expr.id() == ID_floatbv_plus ||
6066 expr.id() == ID_floatbv_minus ||
6067 expr.id() == ID_floatbv_mult ||
6068 expr.id() == ID_floatbv_div ||
6069 expr.id() == ID_floatbv_fma ||
6070 expr.id() == ID_floatbv_typecast ||
6071 expr.id() == ID_ieee_float_equal ||
6072 expr.id() == ID_ieee_float_notequal ||
6073 ((expr.id() == ID_lt ||
6074 expr.id() == ID_gt ||
6075 expr.id() == ID_le ||
6076 expr.id() == ID_ge ||
6077 expr.id() == ID_isnan ||
6078 expr.id() == ID_isnormal ||
6079 expr.id() == ID_isfinite ||
6080 expr.id() == ID_isinf ||
6081 expr.id() == ID_sign ||
6082 expr.id() == ID_unary_minus ||
6083 expr.id() == ID_typecast ||
6084 expr.id() == ID_abs) &&
6085 to_multi_ary_expr(expr).op0().type().id() == ID_floatbv)))
6086 // clang-format on
6087 {
6088 irep_idt function =
6089 convert_identifier("float_bv." + expr.id_string() + floatbv_suffix(expr));
6090
6091 if(bvfp_set.insert(function).second)
6092 {
6093 out << "; this is a model for " << expr.id() << " : "
6094 << type2id(to_multi_ary_expr(expr).op0().type()) << " -> "
6095 << type2id(expr.type()) << "\n"
6096 << "(define-fun " << function << " (";
6097
6098 for(std::size_t i = 0; i < expr.operands().size(); i++)
6099 {
6100 if(i!=0)
6101 out << " ";
6102 out << "(op" << i << ' ';
6103 convert_type(expr.operands()[i].type());
6104 out << ')';
6105 }
6106
6107 out << ") ";
6108 convert_type(expr.type()); // return type
6109 out << ' ';
6110
6111 exprt tmp1=expr;
6112 for(std::size_t i = 0; i < tmp1.operands().size(); i++)
6113 tmp1.operands()[i]=
6114 smt2_symbolt("op"+std::to_string(i), tmp1.operands()[i].type());
6115
6116 exprt tmp2=float_bv(tmp1);
6117 tmp2=letify(tmp2);
6118 CHECK_RETURN(!tmp2.is_nil());
6119
6120 convert_expr(tmp2);
6121
6122 out << ")\n"; // define-fun
6123 }
6124 }
6125 else if(
6126 use_FPA_theory && expr.id() == ID_typecast &&
6127 to_typecast_expr(expr).op().type().id() == ID_floatbv &&
6128 expr.type().id() == ID_bv)
6129 {
6130 // This is _NOT_ a semantic conversion, but bit-wise.
6131 if(defined_expressions.find(expr) == defined_expressions.end())
6132 {
6133 // This conversion is non-trivial as it requires creating a
6134 // new bit-vector variable and then asserting that it converts
6135 // to the required floating-point number.
6136 const irep_idt id =
6137 "bvfromfloat." + std::to_string(defined_expressions.size());
6138 out << "(declare-fun " << id << " () ";
6139 convert_type(expr.type());
6140 out << ')' << '\n';
6141
6142 const typecast_exprt &tc = to_typecast_expr(expr);
6143 const auto &floatbv_type = to_floatbv_type(tc.op().type());
6144 out << "(assert (= ";
6145 out << "((_ to_fp " << floatbv_type.get_e() << " "
6146 << floatbv_type.get_f() + 1 << ") " << id << ')';
6147 convert_expr(tc.op());
6148 out << ')'; // =
6149 out << ')' << '\n';
6150
6151 defined_expressions[expr] = id;
6152 }
6153 }
6154 else if(expr.id() == ID_initial_state)
6155 {
6156 irep_idt function = "initial-state";
6157
6158 if(state_fkt_declared.insert(function).second)
6159 {
6160 out << "(declare-fun " << function << " (";
6161 convert_type(to_unary_expr(expr).op().type());
6162 out << ") ";
6163 convert_type(expr.type()); // return type
6164 out << ")\n"; // declare-fun
6165 }
6166 }
6167 else if(expr.id() == ID_evaluate)
6168 {
6169 irep_idt function = "evaluate-" + type2id(expr.type());
6170
6171 if(state_fkt_declared.insert(function).second)
6172 {
6173 out << "(declare-fun " << function << " (";
6174 convert_type(to_binary_expr(expr).op0().type());
6175 out << ' ';
6176 convert_type(to_binary_expr(expr).op1().type());
6177 out << ") ";
6178 convert_type(expr.type()); // return type
6179 out << ")\n"; // declare-fun
6180 }
6181 }
6182 else if(
6183 expr.id() == ID_state_is_cstring ||
6184 expr.id() == ID_state_is_dynamic_object ||
6185 expr.id() == ID_state_live_object || expr.id() == ID_state_writeable_object)
6186 {
6187 irep_idt function =
6188 expr.id() == ID_state_is_cstring ? "state-is-cstring"
6189 : expr.id() == ID_state_is_dynamic_object ? "state-is-dynamic-object"
6190 : expr.id() == ID_state_live_object ? "state-live-object"
6191 : "state-writeable-object";
6192
6193 if(state_fkt_declared.insert(function).second)
6194 {
6195 out << "(declare-fun " << function << " (";
6196 convert_type(to_binary_expr(expr).op0().type());
6197 out << ' ';
6198 convert_type(to_binary_expr(expr).op1().type());
6199 out << ") ";
6200 convert_type(expr.type()); // return type
6201 out << ")\n"; // declare-fun
6202 }
6203 }
6204 else if(
6205 expr.id() == ID_state_r_ok || expr.id() == ID_state_w_ok ||
6206 expr.id() == ID_state_rw_ok)
6207 {
6208 irep_idt function = expr.id() == ID_state_r_ok ? "state-r-ok"
6209 : expr.id() == ID_state_w_ok ? "state-w-ok"
6210 : "state-rw-ok";
6211
6212 if(state_fkt_declared.insert(function).second)
6213 {
6214 out << "(declare-fun " << function << " (";
6215 convert_type(to_ternary_expr(expr).op0().type());
6216 out << ' ';
6217 convert_type(to_ternary_expr(expr).op1().type());
6218 out << ' ';
6219 convert_type(to_ternary_expr(expr).op2().type());
6220 out << ") ";
6221 convert_type(expr.type()); // return type
6222 out << ")\n"; // declare-fun
6223 }
6224 }
6225 else if(expr.id() == ID_update_state)
6226 {
6227 irep_idt function =
6228 "update-state-" + type2id(to_multi_ary_expr(expr).op2().type());
6229
6230 if(state_fkt_declared.insert(function).second)
6231 {
6232 out << "(declare-fun " << function << " (";
6233 convert_type(to_multi_ary_expr(expr).op0().type());
6234 out << ' ';
6235 convert_type(to_multi_ary_expr(expr).op1().type());
6236 out << ' ';
6237 convert_type(to_multi_ary_expr(expr).op2().type());
6238 out << ") ";
6239 convert_type(expr.type()); // return type
6240 out << ")\n"; // declare-fun
6241 }
6242 }
6243 else if(expr.id() == ID_enter_scope_state)
6244 {
6245 irep_idt function =
6246 "enter-scope-state-" + type2id(to_binary_expr(expr).op1().type());
6247
6248 if(state_fkt_declared.insert(function).second)
6249 {
6250 out << "(declare-fun " << function << " (";
6251 convert_type(to_binary_expr(expr).op0().type());
6252 out << ' ';
6253 convert_type(to_binary_expr(expr).op1().type());
6254 out << ' ';
6256 out << ") ";
6257 convert_type(expr.type()); // return type
6258 out << ")\n"; // declare-fun
6259 }
6260 }
6261 else if(expr.id() == ID_exit_scope_state)
6262 {
6263 irep_idt function =
6264 "exit-scope-state-" + type2id(to_binary_expr(expr).op1().type());
6265
6266 if(state_fkt_declared.insert(function).second)
6267 {
6268 out << "(declare-fun " << function << " (";
6269 convert_type(to_binary_expr(expr).op0().type());
6270 out << ' ';
6271 convert_type(to_binary_expr(expr).op1().type());
6272 out << ") ";
6273 convert_type(expr.type()); // return type
6274 out << ")\n"; // declare-fun
6275 }
6276 }
6277 else if(expr.id() == ID_allocate)
6278 {
6279 irep_idt function = "allocate";
6280
6281 if(state_fkt_declared.insert(function).second)
6282 {
6283 out << "(declare-fun " << function << " (";
6284 convert_type(to_binary_expr(expr).op0().type());
6285 out << ' ';
6286 convert_type(to_binary_expr(expr).op1().type());
6287 out << ") ";
6288 convert_type(expr.type()); // return type
6289 out << ")\n"; // declare-fun
6290 }
6291 }
6292 else if(expr.id() == ID_reallocate)
6293 {
6294 irep_idt function = "reallocate";
6295
6296 if(state_fkt_declared.insert(function).second)
6297 {
6298 out << "(declare-fun " << function << " (";
6299 convert_type(to_ternary_expr(expr).op0().type());
6300 out << ' ';
6301 convert_type(to_ternary_expr(expr).op1().type());
6302 out << ' ';
6303 convert_type(to_ternary_expr(expr).op2().type());
6304 out << ") ";
6305 convert_type(expr.type()); // return type
6306 out << ")\n"; // declare-fun
6307 }
6308 }
6309 else if(expr.id() == ID_deallocate_state)
6310 {
6311 irep_idt function = "deallocate";
6312
6313 if(state_fkt_declared.insert(function).second)
6314 {
6315 out << "(declare-fun " << function << " (";
6316 convert_type(to_binary_expr(expr).op0().type());
6317 out << ' ';
6318 convert_type(to_binary_expr(expr).op1().type());
6319 out << ") ";
6320 convert_type(expr.type()); // return type
6321 out << ")\n"; // declare-fun
6322 }
6323 }
6324 else if(expr.id() == ID_object_address)
6325 {
6326 irep_idt function = "object-address";
6327
6328 if(state_fkt_declared.insert(function).second)
6329 {
6330 out << "(declare-fun " << function << " (String) ";
6331 convert_type(expr.type()); // return type
6332 out << ")\n"; // declare-fun
6333 }
6334 }
6335 else if(expr.id() == ID_field_address)
6336 {
6337 irep_idt function = "field-address-" + type2id(expr.type());
6338
6339 if(state_fkt_declared.insert(function).second)
6340 {
6341 out << "(declare-fun " << function << " (";
6342 convert_type(to_field_address_expr(expr).op().type());
6343 out << ' ';
6344 out << "String";
6345 out << ") ";
6346 convert_type(expr.type()); // return type
6347 out << ")\n"; // declare-fun
6348 }
6349 }
6350 else if(expr.id() == ID_element_address)
6351 {
6352 irep_idt function = "element-address-" + type2id(expr.type());
6353
6354 if(state_fkt_declared.insert(function).second)
6355 {
6356 out << "(declare-fun " << function << " (";
6357 convert_type(to_element_address_expr(expr).base().type());
6358 out << ' ';
6359 convert_type(to_element_address_expr(expr).index().type());
6360 out << ' '; // repeat, for the element size
6361 convert_type(to_element_address_expr(expr).index().type());
6362 out << ") ";
6363 convert_type(expr.type()); // return type
6364 out << ")\n"; // declare-fun
6365 }
6366 }
6367}
6368
6370{
6371 const typet &type = expr.type();
6372 PRECONDITION(type.id()==ID_array);
6373
6374 // arrays inside structs get flattened, unless we have datatypes
6375 if(expr.id() == ID_with)
6376 return use_array_theory(to_with_expr(expr).old());
6377 else if(expr.id() == ID_if)
6378 {
6379 // For an array-typed if-then-else, the SMT sort produced by
6380 // convert_expr (see the ID_if branch above) is determined by the
6381 // sorts chosen for its two operands:
6382 // - if both branches are bit-vector-encoded, i.e. neither uses array
6383 // theory (typically because both are array-typed members of a
6384 // struct that has been flattened to a bit-vector), the resulting
6385 // ite is a bit-vector;
6386 // - if both branches use array theory, the ite is an SMT array;
6387 // - if exactly one branch uses array theory, the ID_if handler in
6388 // convert_expr unflattens the bit-vector branch back to an SMT
6389 // array (see the wheret::BEGIN/wheret::END unflatten calls), so
6390 // the ite is again an SMT array.
6391 // The ite therefore "uses array theory" iff at least one branch
6392 // does. Without this clause, the fall-through below would
6393 // unconditionally return true for ID_if (since ID_if != ID_member),
6394 // which is wrong in the symmetric bit-vector case: callers like
6395 // convert_index, convert_with, flatten2bv, and the array-typed
6396 // define-fun path would then emit array-theory operators -- e.g.
6397 // (select <ite> ...) or (store <ite> ...) -- on a bit-vector
6398 // operand, producing ill-typed SMT-LIB 2 that is rejected by
6399 // conforming solvers (cf. issue #9008). The asymmetric case was
6400 // already handled, for ID_with branches, in the ID_if conversion
6401 // logic of convert_expr; the present clause makes use_array_theory
6402 // consistent with that conversion in all four combinations.
6403 const if_exprt &if_expr = to_if_expr(expr);
6404 return use_array_theory(if_expr.true_case()) ||
6405 use_array_theory(if_expr.false_case());
6406 }
6407 else
6408 return use_datatypes || expr.id() != ID_member;
6409}
6410
6412{
6413 if(type.id()==ID_array)
6414 {
6415 const array_typet &array_type = to_array_type(type);
6416
6417 // we always use array theory for top-level arrays
6418 const typet &subtype = array_type.element_type();
6419
6420 // Arrays map the index type to the element type.
6421 out << "(Array ";
6422 convert_type(array_type.index_type());
6423 out << " ";
6424
6425 if(subtype.id()==ID_bool && !use_array_of_bool)
6426 out << "(_ BitVec 1)";
6427 else
6428 convert_type(array_type.element_type());
6429
6430 out << ")";
6431 }
6432 else if(type.id()==ID_bool)
6433 {
6434 out << "Bool";
6435 }
6436 else if(type.id() == ID_struct || type.id() == ID_struct_tag)
6437 {
6438 if(use_datatypes)
6439 {
6440 out << datatype_map.at(type);
6441 }
6442 else
6443 {
6444 std::size_t width=boolbv_width(type);
6445
6446 out << "(_ BitVec " << width << ")";
6447 }
6448 }
6449 else if(type.id()==ID_code)
6450 {
6451 // These may appear in structs.
6452 // We replace this by "Bool" in order to keep the same
6453 // member count.
6454 out << "Bool";
6455 }
6456 else if(type.id() == ID_union || type.id() == ID_union_tag)
6457 {
6458 std::size_t width=boolbv_width(type);
6459 const union_typet &union_type = type.id() == ID_union_tag
6460 ? ns.follow_tag(to_union_tag_type(type))
6461 : to_union_type(type);
6463 union_type.components().empty() || width != 0,
6464 "failed to get width of union");
6465
6466 out << "(_ BitVec " << width << ")";
6467 }
6468 else if(type.id()==ID_pointer)
6469 {
6470 out << "(_ BitVec "
6471 << boolbv_width(type) << ")";
6472 }
6473 else if(type.id()==ID_bv ||
6474 type.id()==ID_fixedbv ||
6475 type.id()==ID_unsignedbv ||
6476 type.id()==ID_signedbv ||
6477 type.id()==ID_c_bool)
6478 {
6479 out << "(_ BitVec "
6480 << to_bitvector_type(type).get_width() << ")";
6481 }
6482 else if(type.id()==ID_c_enum)
6483 {
6484 // these have an underlying type
6485 out << "(_ BitVec "
6486 << to_bitvector_type(to_c_enum_type(type).underlying_type()).get_width()
6487 << ")";
6488 }
6489 else if(type.id()==ID_c_enum_tag)
6490 {
6491 convert_type(ns.follow_tag(to_c_enum_tag_type(type)));
6492 }
6493 else if(type.id()==ID_floatbv)
6494 {
6495 const floatbv_typet &floatbv_type=to_floatbv_type(type);
6496
6497 if(use_FPA_theory)
6498 out << "(_ FloatingPoint "
6499 << floatbv_type.get_e() << " "
6500 << floatbv_type.get_f() + 1 << ")";
6501 else
6502 out << "(_ BitVec "
6503 << floatbv_type.get_width() << ")";
6504 }
6505 else if(type.id()==ID_rational ||
6506 type.id()==ID_real)
6507 out << "Real";
6508 else if(type.id()==ID_integer)
6509 out << "Int";
6510 else if(type.id() == ID_natural)
6511 out << "Nat";
6512 else if(type.id()==ID_complex)
6513 {
6514 if(use_datatypes)
6515 {
6516 out << datatype_map.at(type);
6517 }
6518 else
6519 {
6520 std::size_t width=boolbv_width(type);
6521
6522 out << "(_ BitVec " << width << ")";
6523 }
6524 }
6525 else if(type.id()==ID_c_bit_field)
6526 {
6528 }
6529 else if(type.id() == ID_state)
6530 {
6531 out << "state";
6532 }
6533 else if(type.id() == ID_range)
6534 {
6535 auto &range_type = to_integer_range_type(type);
6536 if(range_type.empty())
6537 UNEXPECTEDCASE("unsupported range type");
6538 out << "(_ BitVec " << address_bits(range_type.size()) << ")";
6539 }
6540 else if(type.id() == ID_string)
6541 out << "String";
6542 else if(type.id() == ID_regex)
6543 out << "RegLan";
6544 else
6545 {
6546 UNEXPECTEDCASE("unsupported type: "+type.id_string());
6547 }
6548}
6549
6551{
6552 std::set<irep_idt> recstack;
6553 find_symbols_rec(type, recstack);
6554}
6555
6557 const typet &type,
6558 std::set<irep_idt> &recstack)
6559{
6560 if(type.id()==ID_array)
6561 {
6562 const array_typet &array_type=to_array_type(type);
6563 find_symbols(array_type.size());
6564 find_symbols_rec(array_type.element_type(), recstack);
6565 }
6566 else if(type.id()==ID_complex)
6567 {
6568 find_symbols_rec(to_complex_type(type).subtype(), recstack);
6569
6570 if(use_datatypes &&
6571 datatype_map.find(type)==datatype_map.end())
6572 {
6573 const std::string smt_typename =
6574 "complex." + std::to_string(datatype_map.size());
6575 datatype_map[type] = smt_typename;
6576
6577 out << "(declare-datatypes ((" << smt_typename << " 0)) "
6578 << "(((mk-" << smt_typename;
6579
6580 out << " (" << smt_typename << ".imag ";
6581 convert_type(to_complex_type(type).subtype());
6582 out << ")";
6583
6584 out << " (" << smt_typename << ".real ";
6585 convert_type(to_complex_type(type).subtype());
6586 out << ")";
6587
6588 out << "))))\n";
6589 }
6590 }
6591 else if(type.id() == ID_struct)
6592 {
6593 // Cater for mutually recursive struct types
6594 bool need_decl=false;
6595 if(use_datatypes &&
6596 datatype_map.find(type)==datatype_map.end())
6597 {
6598 const std::string smt_typename =
6599 "struct." + std::to_string(datatype_map.size());
6600 datatype_map[type] = smt_typename;
6601 need_decl=true;
6602 }
6603
6604 const struct_typet::componentst &components =
6605 to_struct_type(type).components();
6606
6607 for(const auto &component : components)
6608 find_symbols_rec(component.type(), recstack);
6609
6610 // Declare the corresponding SMT type if we haven't already.
6611 if(need_decl)
6612 {
6613 const std::string &smt_typename = datatype_map.at(type);
6614
6615 // We're going to create a datatype named something like `struct.0'.
6616 // It's going to have a single constructor named `mk-struct.0' with an
6617 // argument for each member of the struct. The declaration that
6618 // creates this type looks like:
6619 //
6620 // (declare-datatypes ((struct.0 0)) (((mk-struct.0
6621 // (struct.0.component1 type1)
6622 // ...
6623 // (struct.0.componentN typeN)))))
6624 out << "(declare-datatypes ((" << smt_typename << " 0)) "
6625 << "(((mk-" << smt_typename << " ";
6626
6627 for(const auto &component : components)
6628 {
6629 if(is_zero_width(component.type(), ns))
6630 continue;
6631
6632 out << "(" << datatype_selector_name(smt_typename, component.get_name())
6633 << " ";
6634 convert_type(component.type());
6635 out << ") ";
6636 }
6637
6638 out << "))))" << "\n";
6639
6640 // Let's also declare convenience functions to update individual
6641 // members of the struct whil we're at it. The functions are
6642 // named like `update-struct.0.component1'. Their declarations
6643 // look like:
6644 //
6645 // (declare-fun update-struct.0.component1
6646 // ((s struct.0) ; first arg -- the struct to update
6647 // (v type1)) ; second arg -- the value to update
6648 // struct.0 ; the output type
6649 // (mk-struct.0 ; build the new struct...
6650 // v ; the updated value
6651 // (struct.0.component2 s) ; retain the other members
6652 // ...
6653 // (struct.0.componentN s)))
6654
6655 for(struct_union_typet::componentst::const_iterator
6656 it=components.begin();
6657 it!=components.end();
6658 ++it)
6659 {
6660 if(is_zero_width(it->type(), ns))
6661 continue;
6662
6664 out << "(define-fun "
6665 << datatype_update_name(smt_typename, component.get_name()) << " "
6666 << "((s " << smt_typename << ") "
6667 << "(v ";
6668 convert_type(component.type());
6669 out << ")) " << smt_typename << " "
6670 << "(mk-" << smt_typename
6671 << " ";
6672
6673 for(struct_union_typet::componentst::const_iterator
6674 it2=components.begin();
6675 it2!=components.end();
6676 ++it2)
6677 {
6678 if(it==it2)
6679 out << "v ";
6680 else if(!is_zero_width(it2->type(), ns))
6681 {
6682 out << "(" << datatype_selector_name(smt_typename, it2->get_name())
6683 << " s) ";
6684 }
6685 }
6686
6687 out << "))" << "\n";
6688 }
6689
6690 out << "\n";
6691 }
6692 }
6693 else if(type.id() == ID_union)
6694 {
6695 const union_typet::componentst &components =
6696 to_union_type(type).components();
6697
6698 for(const auto &component : components)
6699 find_symbols_rec(component.type(), recstack);
6700 }
6701 else if(type.id()==ID_code)
6702 {
6703 const code_typet::parameterst &parameters=
6704 to_code_type(type).parameters();
6705 for(const auto &param : parameters)
6706 find_symbols_rec(param.type(), recstack);
6707
6708 find_symbols_rec(to_code_type(type).return_type(), recstack);
6709 }
6710 else if(type.id()==ID_pointer)
6711 {
6712 find_symbols_rec(to_pointer_type(type).base_type(), recstack);
6713 }
6714 else if(type.id() == ID_struct_tag)
6715 {
6716 const auto &struct_tag = to_struct_tag_type(type);
6717 const irep_idt &id = struct_tag.get_identifier();
6718
6719 if(recstack.find(id) == recstack.end())
6720 {
6721 const auto &base_struct = ns.follow_tag(struct_tag);
6722 recstack.insert(id);
6723 find_symbols_rec(base_struct, recstack);
6724 datatype_map[type] = datatype_map[base_struct];
6725 }
6726 }
6727 else if(type.id() == ID_union_tag)
6728 {
6729 const auto &union_tag = to_union_tag_type(type);
6730 const irep_idt &id = union_tag.get_identifier();
6731
6732 if(recstack.find(id) == recstack.end())
6733 {
6734 recstack.insert(id);
6735 find_symbols_rec(ns.follow_tag(union_tag), recstack);
6736 }
6737 }
6738 else if(type.id() == ID_state)
6739 {
6740 if(datatype_map.find(type) == datatype_map.end())
6741 {
6742 datatype_map[type] = "state";
6743 out << "(declare-sort state 0)\n";
6744 }
6745 }
6746 else if(type.id() == ID_mathematical_function)
6747 {
6748 const auto &mathematical_function_type =
6750 for(auto &d_type : mathematical_function_type.domain())
6751 find_symbols_rec(d_type, recstack);
6752
6753 find_symbols_rec(mathematical_function_type.codomain(), recstack);
6754 }
6755}
6756
6758{
6760}
configt config
Definition config.cpp:26
mp_integer bvrep2integer(const irep_idt &src, std::size_t width, bool is_signed)
convert a bit-vector representation (possibly signed) to integer
constant_exprt from_integer(const mp_integer &int_value, const typet &type)
std::size_t address_bits(const mp_integer &size)
ceil(log2(size))
bool to_integer(const constant_exprt &expr, mp_integer &int_value)
Convert a constant expression expr to an arbitrary-precision integer.
bool is_power_of_two(const mp_integer &n)
irep_idt integer2bvrep(const mp_integer &src, std::size_t width)
convert an integer to bit-vector representation with given width This uses two's complement for negat...
mp_integer power(const mp_integer &base, const mp_integer &exponent)
A multi-precision implementation of the power operator.
Target numeric_cast_v(const mp_integer &arg)
Convert an mp_integer to integral type Target An invariant will fail if the conversion is not possibl...
std::optional< Target > numeric_cast(const exprt &arg)
Converts an expression to any integral type.
API to expression classes for bitvectors.
const onehot0_exprt & to_onehot0_expr(const exprt &expr)
Cast an exprt to a onehot0_exprt.
const replication_exprt & to_replication_expr(const exprt &expr)
Cast an exprt to a replication_exprt.
const reduction_xnor_exprt & to_reduction_xnor_expr(const exprt &expr)
Cast an exprt to a reduction_xnor_exprt.
const reduction_nand_exprt & to_reduction_nand_expr(const exprt &expr)
Cast an exprt to a reduction_nand_exprt.
const shift_exprt & to_shift_expr(const exprt &expr)
Cast an exprt to a shift_exprt.
const reduction_and_exprt & to_reduction_and_expr(const exprt &expr)
Cast an exprt to a reduction_and_exprt.
const reduction_or_exprt & to_reduction_or_expr(const exprt &expr)
Cast an exprt to a reduction_or_exprt.
const popcount_exprt & to_popcount_expr(const exprt &expr)
Cast an exprt to a popcount_exprt.
const update_bits_exprt & to_update_bits_expr(const exprt &expr)
Cast an exprt to an update_bits_exprt.
const extractbits_exprt & to_extractbits_expr(const exprt &expr)
Cast an exprt to an extractbits_exprt.
const onehot_exprt & to_onehot_expr(const exprt &expr)
Cast an exprt to a onehot_exprt.
bool can_cast_expr< minus_overflow_exprt >(const exprt &base)
const find_first_set_exprt & to_find_first_set_expr(const exprt &expr)
Cast an exprt to a find_first_set_exprt.
bool can_cast_expr< overflow_result_exprt >(const exprt &base)
const update_bit_exprt & to_update_bit_expr(const exprt &expr)
Cast an exprt to an update_bit_exprt.
const bitnot_exprt & to_bitnot_expr(const exprt &expr)
Cast an exprt to a bitnot_exprt.
const bswap_exprt & to_bswap_expr(const exprt &expr)
Cast an exprt to a bswap_exprt.
const count_leading_zeros_exprt & to_count_leading_zeros_expr(const exprt &expr)
Cast an exprt to a count_leading_zeros_exprt.
const reduction_xor_exprt & to_reduction_xor_expr(const exprt &expr)
Cast an exprt to a reduction_xor_exprt.
const bitreverse_exprt & to_bitreverse_expr(const exprt &expr)
Cast an exprt to a bitreverse_exprt.
const extractbit_exprt & to_extractbit_expr(const exprt &expr)
Cast an exprt to an extractbit_exprt.
const reduction_nor_exprt & to_reduction_nor_expr(const exprt &expr)
Cast an exprt to a reduction_nor_exprt.
const zero_extend_exprt & to_zero_extend_expr(const exprt &expr)
Cast an exprt to a zero_extend_exprt.
const count_trailing_zeros_exprt & to_count_trailing_zeros_expr(const exprt &expr)
Cast an exprt to a count_trailing_zeros_exprt.
const bv_typet & to_bv_type(const typet &type)
Cast a typet to a bv_typet.
const fixedbv_typet & to_fixedbv_type(const typet &type)
Cast a typet to a fixedbv_typet.
const bitvector_typet & to_bitvector_type(const typet &type)
Cast a typet to a bitvector_typet.
const floatbv_typet & to_floatbv_type(const typet &type)
Cast a typet to a floatbv_typet.
const unsignedbv_typet & to_unsignedbv_type(const typet &type)
Cast a typet to an unsignedbv_typet.
const signedbv_typet & to_signedbv_type(const typet &type)
Cast a typet to a signedbv_typet.
bool has_byte_operator(const exprt &src)
Return true iff src or one of its operands contain a byte extract or byte update expression.
Expression classes for byte-level operators.
const byte_update_exprt & to_byte_update_expr(const exprt &expr)
exprt lower_byte_extract(const byte_extract_exprt &src, const namespacet &ns)
Rewrite a byte extract expression to more fundamental operations.
const byte_extract_exprt & to_byte_extract_expr(const exprt &expr)
exprt lower_byte_update(const byte_update_exprt &src, const namespacet &ns)
Rewrite a byte update expression to more fundamental operations.
int16_t s2
int8_t s1
typet c_bit_field_replacement_type(const c_bit_field_typet &src, const namespacet &ns)
pointer_typet pointer_type(const typet &subtype)
Definition c_types.cpp:235
const c_bit_field_typet & to_c_bit_field_type(const typet &type)
Cast a typet to a c_bit_field_typet.
Definition c_types.h:80
const c_enum_typet & to_c_enum_type(const typet &type)
Cast a typet to a c_enum_typet.
Definition c_types.h:335
const c_enum_tag_typet & to_c_enum_tag_type(const typet &type)
Cast a typet to a c_enum_tag_typet.
Definition c_types.h:377
const union_typet & to_union_type(const typet &type)
Cast a typet to a union_typet.
Definition c_types.h:184
const c_bool_typet & to_c_bool_type(const typet &type)
Cast a typet to a c_bool_typet.
Definition c_types.h:128
const union_tag_typet & to_union_tag_type(const typet &type)
Cast a typet to a union_tag_typet.
Definition c_types.h:224
Absolute value.
Definition std_expr.h:440
Operator to return the address of an object.
Represents real numbers as roots (zeros) of a polynomial with rational coefficients.
constant_exprt as_expr() const
Thrown when an unexpected error occurs during the analysis (e.g., when the SAT solver returns an erro...
Pointer-typed bitvector constant annotated with the pointer expression that the bitvector is the nume...
Array constructor from list of elements.
Definition std_expr.h:1570
Arrays with given size.
Definition std_types.h:806
typet index_type() const
The type of the index expressions into any instance of this type.
Definition std_types.cpp:34
const exprt & size() const
Definition std_types.h:839
const typet & element_type() const
The type of the elements of the array.
Definition std_types.h:826
A base class for binary expressions.
Definition std_expr.h:649
exprt & lhs()
Definition std_expr.h:679
exprt & rhs()
Definition std_expr.h:689
exprt & op0()
Definition expr.h:134
exprt & op1()
Definition expr.h:137
A base class for relations, i.e., binary predicates whose two operands have the same type.
Definition std_expr.h:784
exprt & where()
Definition std_expr.h:3201
variablest & variables()
Definition std_expr.h:3191
Bit-wise negation of bit-vectors.
std::size_t get_width() const
The Boolean type.
Definition std_types.h:35
The byte swap expression.
std::size_t get_bits_per_byte() const
std::vector< parametert > parameterst
Definition std_types.h:585
const parameterst & parameters() const
Definition std_types.h:698
A constant literal expression.
Definition std_expr.h:3007
const irep_idt & get_value() const
Definition std_expr.h:3015
bool is_null_pointer() const
Returns true if expr has a pointer type and a value NULL; it also returns true when expr has value ze...
Definition std_expr.cpp:171
resultt
Result of running the decision procedure.
Division.
Definition std_expr.h:1152
bool empty() const
Definition dstring.h:101
Equality.
Definition std_expr.h:1339
Boute's Euclidean definition of Modulo – to match SMT-LIB2.
Definition std_expr.h:1277
exprt & op0()
Definition expr.h:134
Base class for all expressions.
Definition expr.h:57
std::vector< exprt > operandst
Definition expr.h:59
bool has_operands() const
Return true if there is at least one operand.
Definition expr.h:92
depth_iteratort depth_end()
Definition expr.cpp:170
bool is_boolean() const
Return whether the expression represents a Boolean.
Definition expr.h:229
depth_iteratort depth_begin()
Definition expr.cpp:168
exprt & op0()
Definition expr.h:134
exprt & op1()
Definition expr.h:137
bool is_constant() const
Return whether the expression is a constant.
Definition expr.h:213
typet & type()
Return the type of the expression.
Definition expr.h:85
void visit_post(std::function< void(exprt &)>)
These are post-order traversal visitors, i.e., the visitor is executed on a node after its children h...
Definition expr.cpp:119
operandst & operands()
Definition expr.h:95
Extracts a single bit of a bit-vector operand.
Extracts a sub-range of a bit-vector operand.
The Boolean constant false.
Definition std_expr.h:3135
std::size_t integer_bits
Definition fixedbv.h:22
std::size_t width
Definition fixedbv.h:22
std::size_t get_fraction_bits() const
Definition fixedbv.h:35
Fixed-width bit-vector with signed fixed-point interpretation.
std::size_t get_fraction_bits() const
std::size_t get_integer_bits() const
Fused multiply-add expression: round(op0 * op1 + op2) with a single rounding.
exprt & op_multiply_lhs()
exprt & op_multiply_rhs()
exprt & rounding_mode()
Round a floating-point number to an integral value considering the given rounding mode.
Semantic type conversion from/to floating-point formats.
Fixed-width bit-vector with IEEE floating-point interpretation.
std::size_t get_f() const
std::size_t get_e() const
IEEE floating-point operations These have two data operands (op0 and op1) and one rounding mode (op2)...
std::size_t f
Definition ieee_float.h:26
std::size_t width() const
Definition ieee_float.h:50
An IEEE 754 floating-point value, including specificiation.
Definition ieee_float.h:117
static ieee_float_valuet minus_infinity(const ieee_float_spect &_spec)
Definition ieee_float.h:209
bool is_NaN() const
Definition ieee_float.h:259
static ieee_float_valuet one(const floatbv_typet &)
ieee_float_spect spec
Definition ieee_float.h:119
constant_exprt to_expr() const
mp_integer pack() const
bool get_sign() const
Definition ieee_float.h:254
static ieee_float_valuet zero(const floatbv_typet &type)
Definition ieee_float.h:172
static ieee_float_valuet NaN(const ieee_float_spect &_spec)
Definition ieee_float.h:195
static ieee_float_valuet plus_infinity(const ieee_float_spect &_spec)
Definition ieee_float.h:202
bool is_infinity() const
Definition ieee_float.h:260
The trinary if-then-else operator.
Definition std_expr.h:2426
exprt & cond()
Definition std_expr.h:2443
exprt & false_case()
Definition std_expr.h:2463
exprt & true_case()
Definition std_expr.h:2453
Boolean implication.
Definition std_expr.h:2154
Array index operator.
Definition std_expr.h:1431
exprt & index()
Definition std_expr.h:1471
exprt & array()
Definition std_expr.h:1461
There are a large number of kinds of tree structured or tree-like data in CPROVER.
Definition irep.h:366
std::string pretty(unsigned indent=0, unsigned max_indent=0) const
Definition irep.cpp:482
const irep_idt & get(const irep_idt &name) const
Definition irep.cpp:44
const std::string & id_string() const
Definition irep.h:393
subt & get_sub()
Definition irep.h:450
void swap(irept &irep)
Definition irep.h:436
const irep_idt & id() const
Definition irep.h:390
bool is_nil() const
Definition irep.h:370
Evaluates to true if the operand is finite.
Evaluates to true if the operand is infinite.
Evaluates to true if the operand is NaN.
Evaluates to true if the operand is a normal number.
A let expression.
Definition std_expr.h:3259
binding_exprt::variablest & variables()
convenience accessor for binding().variables()
Definition std_expr.h:3340
operandst & values()
Definition std_expr.h:3329
exprt & where()
convenience accessor for binding().where()
Definition std_expr.h:3352
literalt get_literal() const
bool is_true() const
Definition literal.h:156
bool sign() const
Definition literal.h:88
var_not var_no() const
Definition literal.h:83
bool is_false() const
Definition literal.h:161
Extract member of struct or union.
Definition std_expr.h:2866
const exprt & struct_op() const
Definition std_expr.h:2904
irep_idt get_component_name() const
Definition std_expr.h:2888
Binary minus.
Definition std_expr.h:1065
Modulo defined as lhs-(rhs * truncate(lhs/rhs)).
Definition std_expr.h:1216
Binary multiplication Associativity is not specified.
Definition std_expr.h:1104
exprt & op1()
Definition std_expr.h:942
exprt & op0()
Definition std_expr.h:936
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition namespace.h:91
The NIL expression.
Definition std_expr.h:3144
const irep_idt & get_identifier() const
Definition std_expr.h:323
Boolean negation.
Definition std_expr.h:2388
Disequality.
Definition std_expr.h:1393
Expression for finding the size (in bytes) of the object a pointer points to.
The plus expression Associativity is not specified.
Definition std_expr.h:1006
The pointer type These are both 'bitvector_typet' (they have a width) and 'type_with_subtypet' (they ...
const typet & base_type() const
The type of the data what we point to.
A base class for quantifier expressions.
Unbounded, signed rational numbers.
Boolean reduction: XOR (parity) of all bits in the operand.
Bit-vector replication.
constant_exprt & times()
A base class for shift and rotate operators.
exprt & distance()
Sign of an expression Predicate is true if _op is negative, false otherwise.
Definition std_expr.h:612
const irep_idt & get_identifier() const
Definition smt2_conv.h:225
void convert_relation(const binary_relation_exprt &)
bool use_lambda_for_array
Definition smt2_conv.h:71
void convert_type(const typet &)
void unflatten(wheret, const typet &, unsigned nesting=0)
bool use_array_theory(const exprt &)
void find_symbols(const exprt &expr)
Find and declare symbols used in an expression This function traverses the expression tree and create...
std::size_t number_of_solver_calls
Definition smt2_conv.h:116
void convert_typecast(const typecast_exprt &expr)
void write_footer()
Writes the end of the SMT file to the smt_convt::out stream.
tvt l_get(literalt l) const
std::string benchmark
Definition smt2_conv.h:107
void convert_floatbv_rem(const binary_exprt &expr)
std::unordered_map< irep_idt, irept > current_bindings
Definition smt2_conv.h:206
bool use_FPA_theory
Definition smt2_conv.h:66
resultt dec_solve(const exprt &) override
Implementation of the decision procedure.
std::set< irep_idt > bvfp_set
Definition smt2_conv.h:212
void convert_address_of_rec(const exprt &expr, const pointer_typet &result_type)
void push() override
Unimplemented.
void convert_is_dynamic_object(const unary_exprt &)
void convert_literal(const literalt)
void convert_floatbv_div(const ieee_float_op_exprt &expr)
void convert_string_literal(const std::string &)
std::size_t get_number_of_solver_calls() const override
Return the number of incremental solver calls.
const namespacet & ns
Definition smt2_conv.h:105
void convert_floatbv_mult(const ieee_float_op_exprt &expr)
boolbv_widtht boolbv_width
Definition smt2_conv.h:114
void convert_constant(const constant_exprt &expr)
std::string floatbv_suffix(const exprt &) const
void flatten2bv(const exprt &)
std::string notes
Definition smt2_conv.h:107
void convert_floatbv_fma(const floatbv_fma_exprt &expr)
void convert_div(const div_exprt &expr)
std::ostream & out
Definition smt2_conv.h:106
exprt lower_byte_operators(const exprt &expr)
Lower byte_update and byte_extract operations within expr.
std::string type2id(const typet &) const
bool emit_set_logic
Definition smt2_conv.h:72
void convert_rounding_mode_FPA(const exprt &expr)
Converting a constant or symbolic rounding mode to SMT-LIB.
void convert_floatbv_typecast(const floatbv_typecast_exprt &expr)
struct_exprt parse_struct(const irept &s, const struct_typet &type)
std::string logic
Definition smt2_conv.h:107
void convert_mult(const mult_exprt &expr)
void convert_update_bit(const update_bit_exprt &)
exprt prepare_for_convert_expr(const exprt &expr)
Perform steps necessary before an expression is passed to convert_expr.
exprt get(const exprt &expr) const override
Return expr with variables replaced by values from satisfying assignment if available.
std::string decision_procedure_text() const override
Return a textual description of the decision procedure.
void convert_floatbv_minus(const ieee_float_op_exprt &expr)
bool use_check_sat_assuming
Definition smt2_conv.h:69
std::map< object_size_exprt, irep_idt > object_sizes
Definition smt2_conv.h:293
void define_object_size(const irep_idt &id, const object_size_exprt &expr)
bool use_datatypes
Definition smt2_conv.h:70
datatype_mapt datatype_map
Definition smt2_conv.h:278
void convert_mod(const mod_exprt &expr)
static std::string convert_identifier(const irep_idt &identifier)
void convert_floatbv_plus(const ieee_float_op_exprt &expr)
void convert_struct(const struct_exprt &expr)
std::unordered_map< irep_idt, bool > set_values
The values which boolean identifiers have been smt2_convt::set_to or in other words those which are a...
Definition smt2_conv.h:291
smt2_convt(const namespacet &_ns, const std::string &_benchmark, const std::string &_notes, const std::string &_logic, solvert _solver, std::ostream &_out)
Definition smt2_conv.cpp:62
void convert_member(const member_exprt &expr)
void convert_euclidean_mod(const euclidean_mod_exprt &expr)
void convert_index(const index_exprt &expr)
converterst converters
Definition smt2_conv.h:111
pointer_logict pointer_logic
Definition smt2_conv.h:246
exprt handle(const exprt &expr) override
Generate a handle, which is an expression that has the same value as the argument in any model that i...
void print_assignment(std::ostream &out) const override
Print satisfying assignment to out.
void walk_array_tree(std::unordered_map< int64_t, exprt > *operands_map, const irept &src, const array_typet &type)
This function walks the SMT output and populates a map with index/value pairs for the array.
void convert_floatbv_round_to_integral(const floatbv_round_to_integral_exprt &)
void set_to(const exprt &expr, bool value) override
For a Boolean expression expr, add the constraint 'expr' if value is true, otherwise add 'not expr'.
static std::string datatype_update_name(const std::string &smt_typename, const irep_idt &component_name)
Build the name of the function that updates component component_name of a value of the datatype named...
bool use_as_const
Definition smt2_conv.h:68
exprt parse_rec(const irept &s, const typet &type)
void convert_union(const union_exprt &expr)
exprt parse_union(const irept &s, const union_typet &type)
exprt parse_array(const irept &s, const array_typet &type)
This function is for parsing array output from SMT solvers when "(get-value |???|)" returns an array ...
std::vector< bool > boolean_assignment
Definition smt2_conv.h:300
void flatten_array(const exprt &)
produce a flat bit-vector for a given array of fixed size
void convert_with(const with_exprt &expr)
letifyt letify
Definition smt2_conv.h:183
bool use_array_of_bool
Definition smt2_conv.h:67
std::vector< literalt > assumptions
Definition smt2_conv.h:113
static std::string datatype_selector_name(const std::string &smt_typename, const irep_idt &component_name)
Build the name of the field selector for component component_name of the datatype named smt_typename.
void convert_plus(const plus_exprt &expr)
defined_expressionst defined_expressions
Definition smt2_conv.h:287
void pop() override
Currently, only implements a single stack element (no nested contexts).
void convert_update_bits(const update_bits_exprt &)
void find_symbols_rec(const typet &type, std::set< irep_idt > &recstack)
void convert_update(const update_exprt &)
void write_header()
std::set< irep_idt > state_fkt_declared
Definition smt2_conv.h:216
solvert solver
Definition smt2_conv.h:108
identifier_mapt identifier_map
Definition smt2_conv.h:271
void convert_minus(const minus_exprt &expr)
void convert_expr(const exprt &)
constant_exprt parse_literal(const irept &, const typet &type)
const smt2_symbolt & to_smt2_symbol(const exprt &expr)
Definition smt2_conv.h:231
std::size_t no_boolean_variables
Definition smt2_conv.h:299
smt2_identifierst smt2_identifiers
Definition smt2_conv.h:296
void convert_floatbv(const exprt &expr)
literalt convert(const exprt &expr)
array_exprt to_array_expr() const
convert string into array constant
Struct constructor from list of elements.
Definition std_expr.h:1820
Structure type, corresponds to C style structs.
Definition std_types.h:230
const irep_idt & get_name() const
Definition std_types.h:78
const componentst & components() const
Definition std_types.h:146
const componentt & get_component(const irep_idt &component_name) const
Get the reference to a component with given name.
Definition std_types.cpp:64
bool has_component(const irep_idt &component_name) const
Definition std_types.h:156
std::vector< componentt > componentst
Definition std_types.h:139
const irep_idt & get_identifier() const
Definition std_expr.h:166
void identifier(const irep_idt &identifier)
Definition std_expr.h:160
The Boolean constant true.
Definition std_expr.h:3126
Definition threeval.h:20
Semantic type conversion.
Definition std_expr.h:1995
static exprt conditional_cast(const exprt &expr, const typet &type)
Definition std_expr.h:2003
The type of an expression, extends irept.
Definition type.h:29
Generic base class for unary expressions.
Definition std_expr.h:364
const exprt & op() const
Definition std_expr.h:394
The unary minus expression.
Definition std_expr.h:477
Union constructor from single element.
Definition std_expr.h:1724
The union type.
Definition c_types.h:147
Fixed-width bit-vector with unsigned binary interpretation.
Thrown when we encounter an instruction, parameters to an instruction etc.
Replaces a sub-range of a bit-vector operand.
exprt lower() const
A lowering to masking, shifting, or.
Replaces a sub-range of a bit-vector operand.
exprt lower() const
A lowering to masking, shifting, or.
Operator to update elements in structs and arrays.
Definition std_expr.h:2679
Operator to update elements in structs and arrays.
Definition std_expr.h:2520
exprt & new_value()
Definition std_expr.h:2550
exprt & where()
Definition std_expr.h:2540
exprt & old()
Definition std_expr.h:2530
bool has_prefix(const std::string &s, const std::string &prefix)
Definition converter.cpp:13
int isdigit(int c)
Definition ctype.c:24
bool can_cast_expr(const exprt &base)
Check whether a reference to a generic exprt is of a specific derived class.
auto expr_try_dynamic_cast(TExpr &base) -> typename detail::expr_try_dynamic_cast_return_typet< T, TExpr >::type
Try to cast a reference to a generic exprt to a specific derived class.
Definition expr_cast.h:81
Forward depth-first search iterators These iterators' copy operations are expensive,...
exprt make_binary(const exprt &expr)
splits an expression with >=3 operands into nested binary expressions
Definition expr_util.cpp:38
Deprecated expression utility functions.
bool has_symbol_expr(const exprt &src, const irep_idt &identifier, bool include_bound_symbols)
Returns true if one of the symbol expressions in src has identifier identifier; if include_bound_symb...
exprt float_bv(const exprt &src)
Definition float_bv.h:202
API to expression classes for floating-point arithmetic.
const ieee_float_op_exprt & to_ieee_float_op_expr(const exprt &expr)
Cast an exprt to an ieee_float_op_exprt.
const floatbv_fma_exprt & to_floatbv_fma_expr(const exprt &expr)
const floatbv_round_to_integral_exprt & to_floatbv_round_to_integral_expr(const exprt &expr)
Cast an exprt to a floatbv_round_to_integral_exprt.
const isnormal_exprt & to_isnormal_expr(const exprt &expr)
Cast an exprt to a isnormal_exprt.
const isinf_exprt & to_isinf_expr(const exprt &expr)
Cast an exprt to a isinf_exprt.
const isfinite_exprt & to_isfinite_expr(const exprt &expr)
Cast an exprt to a isfinite_exprt.
const isnan_exprt & to_isnan_expr(const exprt &expr)
Cast an exprt to a isnan_exprt.
const floatbv_typecast_exprt & to_floatbv_typecast_expr(const exprt &expr)
Cast an exprt to a floatbv_typecast_exprt.
static format_containert< T > format(const T &o)
Definition format.h:37
const std::string & id2string(const irep_idt &d)
Definition irep.h:44
static std::string binary(const constant_exprt &src)
exprt to_expr(const namespacet &ns, const irep_idt &identifier, const std::string &src)
bool is_true(const literalt &l)
Definition literal.h:198
literalt const_literal(bool value)
Definition literal.h:188
literalt pos(literalt a)
Definition literal.h:194
const literal_exprt & to_literal_expr(const exprt &expr)
Cast a generic exprt to a literal_exprt.
double pow(double x, double y)
Definition math.c:3026
API to expression classes for 'mathematical' expressions.
const quantifier_exprt & to_quantifier_expr(const exprt &expr)
Cast an exprt to a quantifier_exprt.
const function_application_exprt & to_function_application_expr(const exprt &expr)
Cast an exprt to a function_application_exprt.
const integer_range_typet & to_integer_range_type(const typet &type)
Cast a typet to a integer_range_typet.
const mathematical_function_typet & to_mathematical_function_type(const typet &type)
Cast a typet to a mathematical_function_typet.
const mp_integer string2integer(const std::string &n, unsigned base)
Definition mp_arith.cpp:54
const std::string integer2string(const mp_integer &n, unsigned base)
Definition mp_arith.cpp:103
mp_integer bitwise_or(const mp_integer &a, const mp_integer &b)
bitwise 'or' of two nonnegative integers
Definition mp_arith.cpp:215
const std::string integer2binary(const mp_integer &n, std::size_t width)
Definition mp_arith.cpp:64
named_mp_integert< bits_tagt > bitst
Definition mp_arith.h:179
named_mp_integert< bytes_tagt > bytest
Definition mp_arith.h:184
const element_address_exprt & to_element_address_expr(const exprt &expr)
Cast an exprt to an element_address_exprt.
const object_address_exprt & to_object_address_expr(const exprt &expr)
Cast an exprt to an object_address_exprt.
const address_of_exprt & to_address_of_expr(const exprt &expr)
Cast an exprt to an address_of_exprt.
const pointer_typet & to_pointer_type(const typet &type)
Cast a typet to a pointer_typet.
const pointer_offset_exprt & to_pointer_offset_expr(const exprt &expr)
Cast an exprt to a pointer_offset_exprt.
const pointer_object_exprt & to_pointer_object_expr(const exprt &expr)
Cast an exprt to a pointer_object_exprt.
const field_address_exprt & to_field_address_expr(const exprt &expr)
Cast an exprt to an field_address_exprt.
bool is_zero_width(const typet &type, const namespacet &ns)
Returns true iff type has effective width of zero bits.
std::optional< exprt > size_of_expr(const typet &type, const namespacet &ns)
std::optional< bytest > member_offset(const struct_typet &type, const irep_idt &member, const namespacet &ns)
std::optional< bytest > pointer_offset_size(const typet &type, const namespacet &ns)
Compute the size of a type in bytes, rounding up to full bytes.
Pointer Logic.
exprt pointer_offset(const exprt &pointer)
exprt object_size(const exprt &pointer)
exprt same_object(const exprt &p1, const exprt &p2)
Various predicates over pointers in programs.
Ranges: pair of begin and end iterators, which can be initialized from containers,...
ranget< iteratort > make_range(iteratort begin, iteratort end)
Definition range.h:522
bool to_rational(const exprt &expr, rationalt &rational_value)
constant_exprt from_rational(const rationalt &a)
exprt simplify_expr(exprt src, const namespacet &ns)
static bool has_quantifier(const exprt &expr)
#define SMT2_TODO(S)
Definition smt2_conv.cpp:60
static bool is_smt2_simple_identifier(const std::string &identifier)
#define UNEXPECTEDCASE(S)
Definition smt2_conv.cpp:57
bool is_smt2_simple_symbol_character(char ch)
Tokenizer for the SMT-LIB v2.6 syntax.
BigInt mp_integer
Definition smt_terms.h:17
#define CHECK_RETURN(CONDITION)
Definition invariant.h:495
#define UNREACHABLE
This should be used to mark dead code.
Definition invariant.h:525
#define DATA_INVARIANT(CONDITION, REASON)
This condition should be used to document that assumptions that are made on goto_functions,...
Definition invariant.h:534
#define PRECONDITION(CONDITION)
Definition invariant.h:463
#define UNIMPLEMENTED
Definition invariant.h:558
#define INVARIANT_WITH_DIAGNOSTICS(CONDITION, REASON,...)
Same as invariant, with one or more diagnostics attached Diagnostics can be of any type that has a sp...
Definition invariant.h:437
#define INVARIANT(CONDITION, REASON)
This macro uses the wrapper function 'invariant_violated_string'.
Definition invariant.h:423
#define CHECK_RETURN_WITH_DIAGNOSTICS(CONDITION,...)
Definition invariant.h:496
#define DATA_INVARIANT_WITH_DIAGNOSTICS(CONDITION, REASON,...)
Definition invariant.h:535
#define UNREACHABLE_BECAUSE(REASON)
Definition invariant.h:526
auto component(T &struct_expr, const irep_idt &name, const namespacet &ns) -> decltype(struct_expr.op0())
Definition std_expr.cpp:292
API to expression classes.
const struct_exprt & to_struct_expr(const exprt &expr)
Cast an exprt to a struct_exprt.
Definition std_expr.h:1843
const array_of_exprt & to_array_of_expr(const exprt &expr)
Cast an exprt to an array_of_exprt.
Definition std_expr.h:1552
const binary_relation_exprt & to_binary_relation_expr(const exprt &expr)
Cast an exprt to a binary_relation_exprt.
Definition std_expr.h:828
const unary_plus_exprt & to_unary_plus_expr(const exprt &expr)
Cast an exprt to a unary_plus_exprt.
Definition std_expr.h:539
const index_exprt & to_index_expr(const exprt &expr)
Cast an exprt to an index_exprt.
Definition std_expr.h:1494
const mod_exprt & to_mod_expr(const exprt &expr)
Cast an exprt to a mod_exprt.
Definition std_expr.h:1260
const mult_exprt & to_mult_expr(const exprt &expr)
Cast an exprt to a mult_exprt.
Definition std_expr.h:1134
const array_comprehension_exprt & to_array_comprehension_expr(const exprt &expr)
Cast an exprt to a array_comprehension_exprt.
Definition std_expr.h:3542
const ternary_exprt & to_ternary_expr(const exprt &expr)
Cast an exprt to a ternary_exprt.
Definition std_expr.h:117
const named_term_exprt & to_named_term_expr(const exprt &expr)
Cast an exprt to a named_term_exprt.
Definition std_expr.h:3715
const cond_exprt & to_cond_expr(const exprt &expr)
Cast an exprt to a cond_exprt.
Definition std_expr.h:3456
const typecast_exprt & to_typecast_expr(const exprt &expr)
Cast an exprt to a typecast_exprt.
Definition std_expr.h:2024
const div_exprt & to_div_expr(const exprt &expr)
Cast an exprt to a div_exprt.
Definition std_expr.h:1196
const binary_exprt & to_binary_expr(const exprt &expr)
Cast an exprt to a binary_exprt.
Definition std_expr.h:721
const plus_exprt & to_plus_expr(const exprt &expr)
Cast an exprt to a plus_exprt.
Definition std_expr.h:1045
const notequal_exprt & to_notequal_expr(const exprt &expr)
Cast an exprt to an notequal_exprt.
Definition std_expr.h:1413
const unary_exprt & to_unary_expr(const exprt &expr)
Cast an exprt to a unary_exprt.
Definition std_expr.h:424
const multi_ary_exprt & to_multi_ary_expr(const exprt &expr)
Cast an exprt to a multi_ary_exprt.
Definition std_expr.h:991
const let_exprt & to_let_expr(const exprt &expr)
Cast an exprt to a let_exprt.
Definition std_expr.h:3396
const abs_exprt & to_abs_expr(const exprt &expr)
Cast an exprt to a abs_exprt.
Definition std_expr.h:459
const if_exprt & to_if_expr(const exprt &expr)
Cast an exprt to an if_exprt.
Definition std_expr.h:2501
const member_exprt & to_member_expr(const exprt &expr)
Cast an exprt to a member_exprt.
Definition std_expr.h:2953
const minus_exprt & to_minus_expr(const exprt &expr)
Cast an exprt to a minus_exprt.
Definition std_expr.h:1085
const union_exprt & to_union_expr(const exprt &expr)
Cast an exprt to a union_exprt.
Definition std_expr.h:1765
const constant_exprt & to_constant_expr(const exprt &expr)
Cast an exprt to a constant_exprt.
Definition std_expr.h:3078
const not_exprt & to_not_expr(const exprt &expr)
Cast an exprt to an not_exprt.
Definition std_expr.h:2408
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition std_expr.h:221
const with_exprt & to_with_expr(const exprt &expr)
Cast an exprt to a with_exprt.
Definition std_expr.h:2573
const implies_exprt & to_implies_expr(const exprt &expr)
Cast an exprt to a implies_exprt.
Definition std_expr.h:2174
const update_exprt & to_update_expr(const exprt &expr)
Cast an exprt to an update_exprt.
Definition std_expr.h:2762
const unary_minus_exprt & to_unary_minus_expr(const exprt &expr)
Cast an exprt to a unary_minus_exprt.
Definition std_expr.h:502
const equal_exprt & to_equal_expr(const exprt &expr)
Cast an exprt to an equal_exprt.
Definition std_expr.h:1375
const nondet_symbol_exprt & to_nondet_symbol_expr(const exprt &expr)
Cast an exprt to a nondet_symbol_exprt.
Definition std_expr.h:346
const sign_exprt & to_sign_expr(const exprt &expr)
Cast an exprt to a sign_exprt.
Definition std_expr.h:632
const euclidean_mod_exprt & to_euclidean_mod_expr(const exprt &expr)
Cast an exprt to a euclidean_mod_exprt.
Definition std_expr.h:1321
const code_typet & to_code_type(const typet &type)
Cast a typet to a code_typet.
Definition std_types.h:787
const struct_typet & to_struct_type(const typet &type)
Cast a typet to a struct_typet.
Definition std_types.h:307
const struct_tag_typet & to_struct_tag_type(const typet &type)
Cast a typet to a struct_tag_typet.
Definition std_types.h:517
const complex_typet & to_complex_type(const typet &type)
Cast a typet to a complex_typet.
Definition std_types.h:1048
const array_typet & to_array_type(const typet &type)
Cast a typet to an array_typet.
Definition std_types.h:887
std::size_t unsafe_string2size_t(const std::string &str, int base)
const string_constantt & to_string_constant(const exprt &expr)
static bool failed(bool error_indicator)
#define size_type
Definition unistd.c:186
dstringt irep_idt