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/std_expr.h>
17 #include <util/byte_operators.h>
18 
19 #if !HASH_CODE
21 #endif
22 
23 #include <solvers/prop/prop_conv.h>
26 
27 #include "letify.h"
28 
29 class typecast_exprt;
30 class constant_exprt;
31 class index_exprt;
32 class member_exprt;
33 
35 {
36 public:
37  enum class solvert
38  {
39  GENERIC,
40  BOOLECTOR,
42  CVC3,
43  CVC4,
44  MATHSAT,
45  YICES,
46  Z3
47  };
48 
49  smt2_convt(
50  const namespacet &_ns,
51  const std::string &_benchmark,
52  const std::string &_notes,
53  const std::string &_logic,
54  solvert _solver,
55  std::ostream &_out);
56 
57  ~smt2_convt() override = default;
58 
63 
64  exprt handle(const exprt &expr) override;
65  void set_to(const exprt &expr, bool value) override;
66  exprt get(const exprt &expr) const override;
67  std::string decision_procedure_text() const override;
68  void print_assignment(std::ostream &out) const override;
69 
71  void push() override;
72 
74  void push(const std::vector<exprt> &_assumptions) override;
75 
77  void pop() override;
78 
79  std::size_t get_number_of_solver_calls() const override;
80 
81 protected:
82  const namespacet &ns;
83  std::ostream &out;
84  std::string benchmark, notes, logic;
86 
87  std::vector<exprt> assumptions;
89 
90  std::size_t number_of_solver_calls = 0;
91 
92  resultt dec_solve() override;
93 
94  void write_header();
95  void write_footer(std::ostream &);
96 
97  // tweaks for arrays
98  bool use_array_theory(const exprt &);
99  void flatten_array(const exprt &);
100 
101  // specific expressions go here
102  void convert_typecast(const typecast_exprt &expr);
104  void convert_struct(const struct_exprt &expr);
105  void convert_union(const union_exprt &expr);
106  void convert_constant(const constant_exprt &expr);
109  void convert_plus(const plus_exprt &expr);
110  void convert_minus(const minus_exprt &expr);
111  void convert_div(const div_exprt &expr);
112  void convert_mult(const mult_exprt &expr);
113  void convert_rounding_mode_FPA(const exprt &expr);
114  void convert_floatbv_plus(const ieee_float_op_exprt &expr);
115  void convert_floatbv_minus(const ieee_float_op_exprt &expr);
116  void convert_floatbv_div(const ieee_float_op_exprt &expr);
117  void convert_floatbv_mult(const ieee_float_op_exprt &expr);
118  void convert_mod(const mod_exprt &expr);
119  void convert_index(const index_exprt &expr);
120  void convert_member(const member_exprt &expr);
121 
122  void convert_with(const with_exprt &expr);
123  void convert_update(const exprt &expr);
124 
125  std::string convert_identifier(const irep_idt &identifier);
126 
127  void convert_expr(const exprt &);
128  void convert_type(const typet &);
129  void convert_literal(const literalt);
130 
131  literalt convert(const exprt &expr);
132  tvt l_get(literalt l) const;
133 
134  // auxiliary methods
135  exprt prepare_for_convert_expr(const exprt &expr);
136  exprt lower_byte_operators(const exprt &expr);
137  void find_symbols(const exprt &expr);
138  void find_symbols(const typet &type);
139  void find_symbols_rec(const typet &type, std::set<irep_idt> &recstack);
140 
141  // letification
143 
144  // Parsing solver responses
145  constant_exprt parse_literal(const irept &, const typet &type);
146  struct_exprt parse_struct(const irept &s, const struct_typet &type);
147  exprt parse_union(const irept &s, const union_typet &type);
148  exprt parse_array(const irept &s, const array_typet &type);
149  exprt parse_rec(const irept &s, const typet &type);
150 
151  // we use this to build a bit-vector encoding of the FPA theory
152  void convert_floatbv(const exprt &expr);
153  std::string type2id(const typet &) const;
154  std::string floatbv_suffix(const exprt &) const;
155  std::set<irep_idt> bvfp_set; // already converted
156 
158  {
159  public:
160  smt2_symbolt(const irep_idt &_identifier, const typet &_type)
161  : nullary_exprt(ID_smt2_symbol, _type)
162  { set(ID_identifier, _identifier); }
163 
164  const irep_idt &get_identifier() const
165  {
166  return get(ID_identifier);
167  }
168  };
169 
170  const smt2_symbolt &to_smt2_symbol(const exprt &expr)
171  {
172  assert(expr.id()==ID_smt2_symbol && !expr.has_operands());
173  return static_cast<const smt2_symbolt&>(expr);
174  }
175 
176  // flattens any non-bitvector type into a bitvector,
177  // e.g., booleans, vectors, structs, arrays but also
178  // floats when using the FPA theory.
179  // unflatten() does the opposite.
180  enum class wheret { BEGIN, END };
181  void flatten2bv(const exprt &);
182  void unflatten(wheret, const typet &, unsigned nesting=0);
183 
184  // pointers
187  const exprt &expr, const pointer_typet &result_type);
188 
189  void define_object_size(const irep_idt &id, const exprt &expr);
190 
191  // keeps track of all non-Boolean symbols and their value
192  struct identifiert
193  {
194  bool is_bound;
197 
199  {
200  type.make_nil();
201  value.make_nil();
202  }
203  };
204 
205  typedef std::unordered_map<irep_idt, identifiert> identifier_mapt;
206 
208 
209  // for modeling structs as Z3 datatype, enabled when
210  // use_datatype is set
211  typedef std::map<typet, std::string> datatype_mapt;
213 
214  // for replacing various defined expressions:
215  //
216  // ID_array_of
217  // ID_array
218  // ID_string_constant
219 
220  typedef std::map<exprt, irep_idt> defined_expressionst;
222 
224 
225  typedef std::set<std::string> smt2_identifierst;
227 
228  // Boolean part
229  std::size_t no_boolean_variables;
230  std::vector<bool> boolean_assignment;
231 };
232 
233 #endif // CPROVER_SOLVERS_SMT2_SMT2_CONV_H
with_exprt
Operator to update elements in structs and arrays.
Definition: std_expr.h:3050
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:4132
smt2_convt::convert_typecast
void convert_typecast(const typecast_exprt &expr)
Definition: smt2_conv.cpp:1955
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:85
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:110
letifyt
Introduce LET for common subexpressions.
Definition: letify.h:17
smt2_convt::wheret
wheret
Definition: smt2_conv.h:180
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:4847
smt2_convt::wheret::END
@ END
smt2_convt::letify
letifyt letify
Definition: smt2_conv.h:142
smt2_convt::convert_type
void convert_type(const typet &)
Definition: smt2_conv.cpp:4502
irept::make_nil
void make_nil()
Definition: irep.h:475
typet
The type of an expression, extends irept.
Definition: type.h:29
smt2_convt::pop
void pop() override
Currently, only implements a single stack element (no nested contexts)
Definition: smt2_conv.cpp:771
smt2_convt::datatype_map
datatype_mapt datatype_map
Definition: smt2_conv.h:212
smt2_convt::parse_array
exprt parse_array(const irept &s, const array_typet &type)
Definition: smt2_conv.cpp:437
smt2_convt::use_array_theory
bool use_array_theory(const exprt &)
Definition: smt2_conv.cpp:4481
smt2_convt::convert_floatbv
void convert_floatbv(const exprt &expr)
Definition: smt2_conv.cpp:851
smt2_convt::use_datatypes
bool use_datatypes
Definition: smt2_conv.h:60
smt2_convt::convert
literalt convert(const exprt &expr)
Definition: smt2_conv.cpp:698
smt2_convt::smt2_symbolt::smt2_symbolt
smt2_symbolt(const irep_idt &_identifier, const typet &_type)
Definition: smt2_conv.h:160
smt2_convt::solvert::MATHSAT
@ MATHSAT
smt2_convt::convert_update
void convert_update(const exprt &expr)
Definition: smt2_conv.cpp:3773
union_exprt
Union constructor from single element.
Definition: std_expr.h:1567
smt2_convt::convert_plus
void convert_plus(const plus_exprt &expr)
Definition: smt2_conv.cpp:3032
plus_exprt
The plus expression Associativity is not specified.
Definition: std_expr.h:881
smt2_convt::convert_floatbv_plus
void convert_floatbv_plus(const ieee_float_op_exprt &expr)
Definition: smt2_conv.cpp:3211
exprt
Base class for all expressions.
Definition: expr.h:53
unary_exprt
Generic base class for unary expressions.
Definition: std_expr.h:269
smt2_convt::convert_expr
void convert_expr(const exprt &)
Definition: smt2_conv.cpp:885
smt2_convt::identifier_mapt
std::unordered_map< irep_idt, identifiert > identifier_mapt
Definition: smt2_conv.h:205
smt2_convt::convert_constant
void convert_constant(const constant_exprt &expr)
Definition: smt2_conv.cpp:2762
smt2_convt::convert_literal
void convert_literal(const literalt)
Definition: smt2_conv.cpp:739
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:730
pointer_logict
Definition: pointer_logic.h:23
stack_decision_proceduret
Definition: stack_decision_procedure.h:58
div_exprt
Division.
Definition: std_expr.h:1031
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:807
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:2698
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:2912
smt2_convt::convert_index
void convert_index(const index_exprt &expr)
Definition: smt2_conv.cpp:3780
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:3154
struct_exprt
Struct constructor from list of elements.
Definition: std_expr.h:1633
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:84
nullary_exprt
An expression without operands.
Definition: std_expr.h:24
smt2_convt::to_smt2_symbol
const smt2_symbolt & to_smt2_symbol(const exprt &expr)
Definition: smt2_conv.h:170
smt2_convt::number_of_solver_calls
std::size_t number_of_solver_calls
Definition: smt2_conv.h:90
pointer_logic.h
Pointer Logic.
smt2_convt::convert_mult
void convert_mult(const mult_exprt &expr)
Definition: smt2_conv.cpp:3431
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:776
smt2_convt::convert_floatbv_div
void convert_floatbv_div(const ieee_float_op_exprt &expr)
Definition: smt2_conv.cpp:3411
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:4256
smt2_convt::push
void push() override
Unimplemented.
Definition: smt2_conv.cpp:759
smt2_convt::parse_literal
constant_exprt parse_literal(const irept &, const typet &type)
Definition: smt2_conv.cpp:299
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:92
smt2_convt::convert_relation
void convert_relation(const binary_relation_exprt &)
Definition: smt2_conv.cpp:2949
floatbv_typecast_exprt
Semantic type conversion from/to floating-point formats.
Definition: std_expr.h:2067
smt2_convt::identifier_map
identifier_mapt identifier_map
Definition: smt2_conv.h:207
smt2_convt::convert_mod
void convert_mod(const mod_exprt &expr)
Definition: smt2_conv.cpp:2893
smt2_convt::smt2_symbolt::get_identifier
const irep_idt & get_identifier() const
Definition: smt2_conv.h:164
smt2_convt::convert_floatbv_mult
void convert_floatbv_mult(const ieee_float_op_exprt &expr)
Definition: smt2_conv.cpp:3506
mult_exprt
Binary multiplication Associativity is not specified.
Definition: std_expr.h:986
smt2_convt::convert_struct
void convert_struct(const struct_exprt &expr)
Definition: smt2_conv.cpp:2634
smt2_convt::out
std::ostream & out
Definition: smt2_conv.h:83
irept::id
const irep_idt & id() const
Definition: irep.h:418
smt2_convt::define_object_size
void define_object_size(const irep_idt &id, const exprt &expr)
Definition: smt2_conv.cpp:204
smt2_convt::object_sizes
defined_expressionst object_sizes
Definition: smt2_conv.h:223
smt2_convt::bvfp_set
std::set< irep_idt > bvfp_set
Definition: smt2_conv.h:155
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:3367
smt2_convt::use_array_of_bool
bool use_array_of_bool
Definition: smt2_conv.h:61
smt2_convt::datatype_mapt
std::map< typet, std::string > datatype_mapt
Definition: smt2_conv.h:211
smt2_convt::convert_minus
void convert_minus(const minus_exprt &expr)
Definition: smt2_conv.cpp:3250
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:940
smt2_convt::boolbv_width
boolbv_widtht boolbv_width
Definition: smt2_conv.h:88
smt2_convt
Definition: smt2_conv.h:35
smt2_convt::find_symbols_rec
void find_symbols_rec(const typet &type, std::set< irep_idt > &recstack)
Definition: smt2_conv.cpp:4643
smt2_convt::convert_with
void convert_with(const with_exprt &expr)
Definition: smt2_conv.cpp:3526
member_exprt
Extract member of struct or union.
Definition: std_expr.h:3405
boolbv_widtht
Definition: boolbv_width.h:17
smt2_convt::use_FPA_theory
bool use_FPA_theory
Definition: smt2_conv.h:59
smt2_convt::write_header
void write_header()
Definition: smt2_conv.cpp:133
struct_typet
Structure type, corresponds to C style structs.
Definition: std_types.h:226
smt2_convt::logic
std::string logic
Definition: smt2_conv.h:84
array_typet
Arrays with given size.
Definition: std_types.h:965
smt2_convt::smt2_symbolt
Definition: smt2_conv.h:158
boolbv_width.h
smt2_convt::defined_expressionst
std::map< exprt, irep_idt > defined_expressionst
Definition: smt2_conv.h:220
smt2_convt::write_footer
void write_footer(std::ostream &)
Definition: smt2_conv.cpp:163
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:542
smt2_convt::dec_solve
resultt dec_solve() override
Run the decision procedure to solve the problem.
Definition: smt2_conv.cpp:242
smt2_convt::floatbv_suffix
std::string floatbv_suffix(const exprt &) const
Definition: smt2_conv.cpp:844
smt2_convt::identifiert::identifiert
identifiert()
Definition: smt2_conv.h:198
irept::set
void set(const irep_namet &name, const irep_idt &value)
Definition: irep.h:442
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:46
smt2_convt::assumptions
std::vector< exprt > assumptions
Definition: smt2_conv.h:87
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:4224
binary_relation_exprt
A base class for relations, i.e., binary predicates whose two operands have the same type.
Definition: std_expr.h:725
smt2_convt::benchmark
std::string benchmark
Definition: smt2_conv.h:84
smt2_convt::parse_struct
struct_exprt parse_struct(const irept &s, const struct_typet &type)
Definition: smt2_conv.cpp:483
smt2_convt::no_boolean_variables
std::size_t no_boolean_variables
Definition: smt2_conv.h:229
literalt
Definition: literal.h:26
smt2_convt::convert_union
void convert_union(const union_exprt &expr)
Definition: smt2_conv.cpp:2729
smt2_convt::ns
const namespacet & ns
Definition: smt2_conv.h:82
smt2_convt::solvert::GENERIC
@ GENERIC
smt2_convt::emit_set_logic
bool emit_set_logic
Definition: smt2_conv.h:62
smt2_convt::pointer_logic
pointer_logict pointer_logic
Definition: smt2_conv.h:185
smt2_convt::convert_address_of_rec
void convert_address_of_rec(const exprt &expr, const pointer_typet &result_type)
Definition: smt2_conv.cpp:606
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:249
ieee_float_op_exprt
IEEE floating-point operations These have two data operands (op0 and op1) and one rounding mode (op2)...
Definition: std_expr.h:3790
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:394
smt2_convt::l_get
tvt l_get(literalt l) const
Definition: smt2_conv.cpp:120
smt2_convt::smt2_identifierst
std::set< std::string > smt2_identifierst
Definition: smt2_conv.h:225
smt2_convt::identifiert
Definition: smt2_conv.h:193
smt2_convt::find_symbols
void find_symbols(const exprt &expr)
Definition: smt2_conv.cpp:4271
letify.h
smt2_convt::solvert
solvert
Definition: smt2_conv.h:38
index_exprt
Array index operator.
Definition: std_expr.h:1293
smt2_convt::boolean_assignment
std::vector< bool > boolean_assignment
Definition: smt2_conv.h:230
smt2_convt::identifiert::type
typet type
Definition: smt2_conv.h:195
typecast_exprt
Semantic type conversion.
Definition: std_expr.h:2013
pointer_typet
The pointer type These are both 'bitvector_typet' (they have a width) and 'type_with_subtypet' (they ...
Definition: std_types.h:1488
constant_exprt
A constant literal expression.
Definition: std_expr.h:3906
std_expr.h
API to expression classes.
smt2_convt::unflatten
void unflatten(wheret, const typet &, unsigned nesting=0)
Definition: smt2_conv.cpp:4028
smt2_convt::parse_union
exprt parse_union(const irept &s, const union_typet &type)
Definition: smt2_conv.cpp:467
smt2_convt::convert_floatbv_minus
void convert_floatbv_minus(const ieee_float_op_exprt &expr)
Definition: smt2_conv.cpp:3347
smt2_convt::flatten2bv
void flatten2bv(const exprt &)
Definition: smt2_conv.cpp:3939
smt2_convt::smt2_identifiers
smt2_identifierst smt2_identifiers
Definition: smt2_conv.h:226
smt2_convt::convert_floatbv_typecast
void convert_floatbv_typecast(const floatbv_typecast_exprt &expr)
Definition: smt2_conv.cpp:2488
smt2_convt::identifiert::value
exprt value
Definition: smt2_conv.h:196
smt2_convt::identifiert::is_bound
bool is_bound
Definition: smt2_conv.h:194
mod_exprt
Modulo.
Definition: std_expr.h:1100
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:105
smt2_convt::convert_member
void convert_member(const member_exprt &expr)
Definition: smt2_conv.cpp:3878
smt2_convt::defined_expressions
defined_expressionst defined_expressions
Definition: smt2_conv.h:221