cprover
smt2_conv.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module:
4 
5 Author: Daniel Kroening, kroening@kroening.com
6 
7 \*******************************************************************/
8 
9 
10 #ifndef CPROVER_SOLVERS_SMT2_SMT2_CONV_H
11 #define CPROVER_SOLVERS_SMT2_SMT2_CONV_H
12 
13 #include <sstream>
14 #include <set>
15 
16 #include <util/byte_operators.h>
17 #include <util/floatbv_expr.h>
18 #include <util/std_expr.h>
19 
20 #if !HASH_CODE
22 #endif
23 
24 #include <solvers/prop/prop_conv.h>
27 
28 #include "letify.h"
29 
30 class typecast_exprt;
31 class constant_exprt;
32 class index_exprt;
33 class member_exprt;
34 
36 {
37 public:
38  enum class solvert
39  {
40  GENERIC,
41  BOOLECTOR,
43  CVC3,
44  CVC4,
45  MATHSAT,
46  YICES,
47  Z3
48  };
49 
50  smt2_convt(
51  const namespacet &_ns,
52  const std::string &_benchmark,
53  const std::string &_notes,
54  const std::string &_logic,
55  solvert _solver,
56  std::ostream &_out);
57 
58  ~smt2_convt() override = default;
59 
64 
65  exprt handle(const exprt &expr) override;
66  void set_to(const exprt &expr, bool value) override;
67  exprt get(const exprt &expr) const override;
68  std::string decision_procedure_text() const override;
69  void print_assignment(std::ostream &out) const override;
70 
72  void push() override;
73 
75  void push(const std::vector<exprt> &_assumptions) override;
76 
78  void pop() override;
79 
80  std::size_t get_number_of_solver_calls() const override;
81 
82 protected:
83  const namespacet &ns;
84  std::ostream &out;
85  std::string benchmark, notes, logic;
87 
88  std::vector<exprt> assumptions;
90 
91  std::size_t number_of_solver_calls = 0;
92 
93  resultt dec_solve() override;
94 
95  void write_header();
96  void write_footer(std::ostream &);
97 
98  // tweaks for arrays
99  bool use_array_theory(const exprt &);
100  void flatten_array(const exprt &);
101 
102  // specific expressions go here
103  void convert_typecast(const typecast_exprt &expr);
105  void convert_struct(const struct_exprt &expr);
106  void convert_union(const union_exprt &expr);
107  void convert_constant(const constant_exprt &expr);
110  void convert_plus(const plus_exprt &expr);
111  void convert_minus(const minus_exprt &expr);
112  void convert_div(const div_exprt &expr);
113  void convert_mult(const mult_exprt &expr);
114  void convert_rounding_mode_FPA(const exprt &expr);
115  void convert_floatbv_plus(const ieee_float_op_exprt &expr);
116  void convert_floatbv_minus(const ieee_float_op_exprt &expr);
117  void convert_floatbv_div(const ieee_float_op_exprt &expr);
118  void convert_floatbv_mult(const ieee_float_op_exprt &expr);
119  void convert_mod(const mod_exprt &expr);
120  void convert_index(const index_exprt &expr);
121  void convert_member(const member_exprt &expr);
122 
123  void convert_with(const with_exprt &expr);
124  void convert_update(const exprt &expr);
125 
126  std::string convert_identifier(const irep_idt &identifier);
127 
128  void convert_expr(const exprt &);
129  void convert_type(const typet &);
130  void convert_literal(const literalt);
131 
132  literalt convert(const exprt &expr);
133  tvt l_get(literalt l) const;
134 
135  // auxiliary methods
136  exprt prepare_for_convert_expr(const exprt &expr);
137  exprt lower_byte_operators(const exprt &expr);
138  void find_symbols(const exprt &expr);
139  void find_symbols(const typet &type);
140  void find_symbols_rec(const typet &type, std::set<irep_idt> &recstack);
141 
142  // letification
144 
145  // Parsing solver responses
146  constant_exprt parse_literal(const irept &, const typet &type);
147  struct_exprt parse_struct(const irept &s, const struct_typet &type);
148  exprt parse_union(const irept &s, const union_typet &type);
149  exprt parse_array(const irept &s, const array_typet &type);
150  exprt parse_rec(const irept &s, const typet &type);
151 
152  // we use this to build a bit-vector encoding of the FPA theory
153  void convert_floatbv(const exprt &expr);
154  std::string type2id(const typet &) const;
155  std::string floatbv_suffix(const exprt &) const;
156  std::set<irep_idt> bvfp_set; // already converted
157 
159  {
160  public:
161  smt2_symbolt(const irep_idt &_identifier, const typet &_type)
162  : nullary_exprt(ID_smt2_symbol, _type)
163  { set(ID_identifier, _identifier); }
164 
165  const irep_idt &get_identifier() const
166  {
167  return get(ID_identifier);
168  }
169  };
170 
171  const smt2_symbolt &to_smt2_symbol(const exprt &expr)
172  {
173  assert(expr.id()==ID_smt2_symbol && !expr.has_operands());
174  return static_cast<const smt2_symbolt&>(expr);
175  }
176 
177  // flattens any non-bitvector type into a bitvector,
178  // e.g., booleans, vectors, structs, arrays but also
179  // floats when using the FPA theory.
180  // unflatten() does the opposite.
181  enum class wheret { BEGIN, END };
182  void flatten2bv(const exprt &);
183  void unflatten(wheret, const typet &, unsigned nesting=0);
184 
185  // pointers
188  const exprt &expr, const pointer_typet &result_type);
189 
190  void define_object_size(const irep_idt &id, const exprt &expr);
191 
192  // keeps track of all non-Boolean symbols and their value
193  struct identifiert
194  {
195  bool is_bound;
198 
200  {
201  type.make_nil();
202  value.make_nil();
203  }
204  };
205 
206  typedef std::unordered_map<irep_idt, identifiert> identifier_mapt;
207 
209 
210  // for modeling structs as Z3 datatype, enabled when
211  // use_datatype is set
212  typedef std::map<typet, std::string> datatype_mapt;
214 
215  // for replacing various defined expressions:
216  //
217  // ID_array_of
218  // ID_array
219  // ID_string_constant
220 
221  typedef std::map<exprt, irep_idt> defined_expressionst;
223 
225 
226  typedef std::set<std::string> smt2_identifierst;
228 
229  // Boolean part
230  std::size_t no_boolean_variables;
231  std::vector<bool> boolean_assignment;
232 };
233 
234 #endif // CPROVER_SOLVERS_SMT2_SMT2_CONV_H
with_exprt
Operator to update elements in structs and arrays.
Definition: std_expr.h:2173
smt2_convt::set_to
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'.
Definition: smt2_conv.cpp:4174
smt2_convt::convert_typecast
void convert_typecast(const typecast_exprt &expr)
Definition: smt2_conv.cpp:1997
smt2_convt::solvert::CVC4
@ CVC4
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
smt2_convt::solver
solvert solver
Definition: smt2_conv.h:86
smt2_convt::solvert::CPROVER_SMT2
@ CPROVER_SMT2
smt2_convt::print_assignment
void print_assignment(std::ostream &out) const override
Print satisfying assignment to out.
Definition: smt2_conv.cpp:112
letifyt
Introduce LET for common subexpressions.
Definition: letify.h:17
smt2_convt::wheret
wheret
Definition: smt2_conv.h:181
smt2_convt::get_number_of_solver_calls
std::size_t get_number_of_solver_calls() const override
Return the number of incremental solver calls.
Definition: smt2_conv.cpp:4889
smt2_convt::wheret::END
@ END
smt2_convt::letify
letifyt letify
Definition: smt2_conv.h:143
smt2_convt::convert_type
void convert_type(const typet &)
Definition: smt2_conv.cpp:4544
irept::make_nil
void make_nil()
Definition: irep.h:464
typet
The type of an expression, extends irept.
Definition: type.h:28
smt2_convt::pop
void pop() override
Currently, only implements a single stack element (no nested contexts)
Definition: smt2_conv.cpp:773
smt2_convt::datatype_map
datatype_mapt datatype_map
Definition: smt2_conv.h:213
smt2_convt::parse_array
exprt parse_array(const irept &s, const array_typet &type)
Definition: smt2_conv.cpp:439
smt2_convt::use_array_theory
bool use_array_theory(const exprt &)
Definition: smt2_conv.cpp:4523
smt2_convt::convert_floatbv
void convert_floatbv(const exprt &expr)
Definition: smt2_conv.cpp:853
smt2_convt::use_datatypes
bool use_datatypes
Definition: smt2_conv.h:61
smt2_convt::convert
literalt convert(const exprt &expr)
Definition: smt2_conv.cpp:700
smt2_convt::smt2_symbolt::smt2_symbolt
smt2_symbolt(const irep_idt &_identifier, const typet &_type)
Definition: smt2_conv.h:161
smt2_convt::solvert::MATHSAT
@ MATHSAT
smt2_convt::convert_update
void convert_update(const exprt &expr)
Definition: smt2_conv.cpp:3815
union_exprt
Union constructor from single element.
Definition: std_expr.h:1517
smt2_convt::convert_plus
void convert_plus(const plus_exprt &expr)
Definition: smt2_conv.cpp:3074
plus_exprt
The plus expression Associativity is not specified.
Definition: std_expr.h:831
smt2_convt::convert_floatbv_plus
void convert_floatbv_plus(const ieee_float_op_exprt &expr)
Definition: smt2_conv.cpp:3253
exprt
Base class for all expressions.
Definition: expr.h:54
unary_exprt
Generic base class for unary expressions.
Definition: std_expr.h:282
smt2_convt::convert_expr
void convert_expr(const exprt &)
Definition: smt2_conv.cpp:887
smt2_convt::identifier_mapt
std::unordered_map< irep_idt, identifiert > identifier_mapt
Definition: smt2_conv.h:206
smt2_convt::convert_constant
void convert_constant(const constant_exprt &expr)
Definition: smt2_conv.cpp:2804
smt2_convt::convert_literal
void convert_literal(const literalt)
Definition: smt2_conv.cpp:741
smt2_convt::handle
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...
Definition: smt2_conv.cpp:732
pointer_logict
Definition: pointer_logic.h:23
stack_decision_proceduret
Definition: stack_decision_procedure.h:58
div_exprt
Division.
Definition: std_expr.h:981
smt2_convt::~smt2_convt
~smt2_convt() override=default
smt2_convt::solvert::CVC3
@ CVC3
smt2_convt::type2id
std::string type2id(const typet &) const
Definition: smt2_conv.cpp:809
smt2_convt::flatten_array
void flatten_array(const exprt &)
produce a flat bit-vector for a given array of fixed size
Definition: smt2_conv.cpp:2740
irep_hash_container.h
IREP Hash Container.
smt2_convt::solvert::BOOLECTOR
@ BOOLECTOR
smt2_convt::convert_is_dynamic_object
void convert_is_dynamic_object(const unary_exprt &)
Definition: smt2_conv.cpp:2954
smt2_convt::convert_index
void convert_index(const index_exprt &expr)
Definition: smt2_conv.cpp:3822
smt2_convt::convert_rounding_mode_FPA
void convert_rounding_mode_FPA(const exprt &expr)
Converting a constant or symbolic rounding mode to SMT-LIB.
Definition: smt2_conv.cpp:3196
struct_exprt
Struct constructor from list of elements.
Definition: std_expr.h:1583
namespacet
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:92
smt2_convt::notes
std::string notes
Definition: smt2_conv.h:85
nullary_exprt
An expression without operands.
Definition: std_expr.h:23
smt2_convt::to_smt2_symbol
const smt2_symbolt & to_smt2_symbol(const exprt &expr)
Definition: smt2_conv.h:171
smt2_convt::number_of_solver_calls
std::size_t number_of_solver_calls
Definition: smt2_conv.h:91
pointer_logic.h
Pointer Logic.
smt2_convt::convert_mult
void convert_mult(const mult_exprt &expr)
Definition: smt2_conv.cpp:3473
byte_operators.h
Expression classes for byte-level operators.
smt2_convt::convert_identifier
std::string convert_identifier(const irep_idt &identifier)
Definition: smt2_conv.cpp:778
smt2_convt::convert_floatbv_div
void convert_floatbv_div(const ieee_float_op_exprt &expr)
Definition: smt2_conv.cpp:3453
smt2_convt::prepare_for_convert_expr
exprt prepare_for_convert_expr(const exprt &expr)
Perform steps necessary before an expression is passed to convert_expr.
Definition: smt2_conv.cpp:4298
smt2_convt::push
void push() override
Unimplemented.
Definition: smt2_conv.cpp:761
smt2_convt::parse_literal
constant_exprt parse_literal(const irept &, const typet &type)
Definition: smt2_conv.cpp:301
prop_conv.h
smt2_convt::solvert::YICES
@ YICES
exprt::has_operands
bool has_operands() const
Return true if there is at least one operand.
Definition: expr.h:93
smt2_convt::convert_relation
void convert_relation(const binary_relation_exprt &)
Definition: smt2_conv.cpp:2991
floatbv_typecast_exprt
Semantic type conversion from/to floating-point formats.
Definition: floatbv_expr.h:19
smt2_convt::identifier_map
identifier_mapt identifier_map
Definition: smt2_conv.h:208
smt2_convt::convert_mod
void convert_mod(const mod_exprt &expr)
Definition: smt2_conv.cpp:2935
smt2_convt::smt2_symbolt::get_identifier
const irep_idt & get_identifier() const
Definition: smt2_conv.h:165
smt2_convt::convert_floatbv_mult
void convert_floatbv_mult(const ieee_float_op_exprt &expr)
Definition: smt2_conv.cpp:3548
mult_exprt
Binary multiplication Associativity is not specified.
Definition: std_expr.h:936
smt2_convt::convert_struct
void convert_struct(const struct_exprt &expr)
Definition: smt2_conv.cpp:2676
smt2_convt::out
std::ostream & out
Definition: smt2_conv.h:84
irept::id
const irep_idt & id() const
Definition: irep.h:407
smt2_convt::define_object_size
void define_object_size(const irep_idt &id, const exprt &expr)
Definition: smt2_conv.cpp:206
smt2_convt::object_sizes
defined_expressionst object_sizes
Definition: smt2_conv.h:224
smt2_convt::bvfp_set
std::set< irep_idt > bvfp_set
Definition: smt2_conv.h:156
floatbv_expr.h
API to expression classes for floating-point arithmetic.
union_typet
The union type.
Definition: std_types.h:393
smt2_convt::convert_div
void convert_div(const div_exprt &expr)
Definition: smt2_conv.cpp:3409
smt2_convt::use_array_of_bool
bool use_array_of_bool
Definition: smt2_conv.h:62
smt2_convt::datatype_mapt
std::map< typet, std::string > datatype_mapt
Definition: smt2_conv.h:212
smt2_convt::convert_minus
void convert_minus(const minus_exprt &expr)
Definition: smt2_conv.cpp:3292
tvt
Definition: threeval.h:20
decision_proceduret::resultt
resultt
Result of running the decision procedure.
Definition: decision_procedure.h:44
minus_exprt
Binary minus.
Definition: std_expr.h:890
smt2_convt::boolbv_width
boolbv_widtht boolbv_width
Definition: smt2_conv.h:89
smt2_convt
Definition: smt2_conv.h:36
smt2_convt::find_symbols_rec
void find_symbols_rec(const typet &type, std::set< irep_idt > &recstack)
Definition: smt2_conv.cpp:4685
smt2_convt::convert_with
void convert_with(const with_exprt &expr)
Definition: smt2_conv.cpp:3568
member_exprt
Extract member of struct or union.
Definition: std_expr.h:2528
boolbv_widtht
Definition: boolbv_width.h:18
smt2_convt::use_FPA_theory
bool use_FPA_theory
Definition: smt2_conv.h:60
smt2_convt::write_header
void write_header()
Definition: smt2_conv.cpp:135
struct_typet
Structure type, corresponds to C style structs.
Definition: std_types.h:226
smt2_convt::logic
std::string logic
Definition: smt2_conv.h:85
array_typet
Arrays with given size.
Definition: std_types.h:968
smt2_convt::smt2_symbolt
Definition: smt2_conv.h:159
boolbv_width.h
smt2_convt::defined_expressionst
std::map< exprt, irep_idt > defined_expressionst
Definition: smt2_conv.h:221
smt2_convt::write_footer
void write_footer(std::ostream &)
Definition: smt2_conv.cpp:165
irept::get
const irep_idt & get(const irep_namet &name) const
Definition: irep.cpp:51
smt2_convt::parse_rec
exprt parse_rec(const irept &s, const typet &type)
Definition: smt2_conv.cpp:544
smt2_convt::dec_solve
resultt dec_solve() override
Run the decision procedure to solve the problem.
Definition: smt2_conv.cpp:244
smt2_convt::floatbv_suffix
std::string floatbv_suffix(const exprt &) const
Definition: smt2_conv.cpp:846
smt2_convt::identifiert::identifiert
identifiert()
Definition: smt2_conv.h:199
irept::set
void set(const irep_namet &name, const irep_idt &value)
Definition: irep.h:431
smt2_convt::smt2_convt
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:48
smt2_convt::assumptions
std::vector< exprt > assumptions
Definition: smt2_conv.h:88
smt2_convt::lower_byte_operators
exprt lower_byte_operators(const exprt &expr)
Lower byte_update and byte_extract operations within expr.
Definition: smt2_conv.cpp:4266
binary_relation_exprt
A base class for relations, i.e., binary predicates whose two operands have the same type.
Definition: std_expr.h:675
smt2_convt::benchmark
std::string benchmark
Definition: smt2_conv.h:85
smt2_convt::parse_struct
struct_exprt parse_struct(const irept &s, const struct_typet &type)
Definition: smt2_conv.cpp:485
smt2_convt::no_boolean_variables
std::size_t no_boolean_variables
Definition: smt2_conv.h:230
literalt
Definition: literal.h:26
smt2_convt::convert_union
void convert_union(const union_exprt &expr)
Definition: smt2_conv.cpp:2771
smt2_convt::ns
const namespacet & ns
Definition: smt2_conv.h:83
smt2_convt::solvert::GENERIC
@ GENERIC
smt2_convt::emit_set_logic
bool emit_set_logic
Definition: smt2_conv.h:63
smt2_convt::pointer_logic
pointer_logict pointer_logic
Definition: smt2_conv.h:186
smt2_convt::convert_address_of_rec
void convert_address_of_rec(const exprt &expr, const pointer_typet &result_type)
Definition: smt2_conv.cpp:608
smt2_convt::get
exprt get(const exprt &expr) const override
Return expr with variables replaced by values from satisfying assignment if available.
Definition: smt2_conv.cpp:251
ieee_float_op_exprt
IEEE floating-point operations These have two data operands (op0 and op1) and one rounding mode (op2)...
Definition: floatbv_expr.h:364
smt2_convt::solvert::Z3
@ Z3
irept
There are a large number of kinds of tree structured or tree-like data in CPROVER.
Definition: irep.h:383
smt2_convt::l_get
tvt l_get(literalt l) const
Definition: smt2_conv.cpp:122
smt2_convt::smt2_identifierst
std::set< std::string > smt2_identifierst
Definition: smt2_conv.h:226
smt2_convt::identifiert
Definition: smt2_conv.h:194
smt2_convt::find_symbols
void find_symbols(const exprt &expr)
Definition: smt2_conv.cpp:4313
letify.h
smt2_convt::solvert
solvert
Definition: smt2_conv.h:39
index_exprt
Array index operator.
Definition: std_expr.h:1243
smt2_convt::boolean_assignment
std::vector< bool > boolean_assignment
Definition: smt2_conv.h:231
smt2_convt::identifiert::type
typet type
Definition: smt2_conv.h:196
typecast_exprt
Semantic type conversion.
Definition: std_expr.h:1781
pointer_typet
The pointer type These are both 'bitvector_typet' (they have a width) and 'type_with_subtypet' (they ...
Definition: std_types.h:1495
constant_exprt
A constant literal expression.
Definition: std_expr.h:2668
std_expr.h
API to expression classes.
smt2_convt::unflatten
void unflatten(wheret, const typet &, unsigned nesting=0)
Definition: smt2_conv.cpp:4070
smt2_convt::parse_union
exprt parse_union(const irept &s, const union_typet &type)
Definition: smt2_conv.cpp:469
smt2_convt::convert_floatbv_minus
void convert_floatbv_minus(const ieee_float_op_exprt &expr)
Definition: smt2_conv.cpp:3389
smt2_convt::flatten2bv
void flatten2bv(const exprt &)
Definition: smt2_conv.cpp:3981
smt2_convt::smt2_identifiers
smt2_identifierst smt2_identifiers
Definition: smt2_conv.h:227
smt2_convt::convert_floatbv_typecast
void convert_floatbv_typecast(const floatbv_typecast_exprt &expr)
Definition: smt2_conv.cpp:2530
smt2_convt::identifiert::value
exprt value
Definition: smt2_conv.h:197
smt2_convt::identifiert::is_bound
bool is_bound
Definition: smt2_conv.h:195
mod_exprt
Modulo.
Definition: std_expr.h:1050
smt2_convt::wheret::BEGIN
@ BEGIN
smt2_convt::decision_procedure_text
std::string decision_procedure_text() const override
Return a textual description of the decision procedure.
Definition: smt2_conv.cpp:107
smt2_convt::convert_member
void convert_member(const member_exprt &expr)
Definition: smt2_conv.cpp:3920
smt2_convt::defined_expressions
defined_expressionst defined_expressions
Definition: smt2_conv.h:222