cprover
expr_util.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module:
4 
5 Author: Daniel Kroening, kroening@kroening.com
6 
7 \*******************************************************************/
8 
9 #include "expr_util.h"
10 
11 #include <algorithm>
12 #include <unordered_set>
13 
14 #include "arith_tools.h"
15 #include "c_types.h"
16 #include "expr.h"
17 #include "expr_iterator.h"
18 #include "fixedbv.h"
19 #include "ieee_float.h"
20 #include "namespace.h"
21 #include "pointer_expr.h"
22 #include "std_expr.h"
23 #include "symbol.h"
24 
25 bool is_lvalue(const exprt &expr)
26 {
27  if(expr.id() == ID_index)
28  return is_lvalue(to_index_expr(expr).array());
29  else if(expr.id() == ID_member)
30  return is_lvalue(to_member_expr(expr).compound());
31  else if(expr.id() == ID_dereference)
32  return true;
33  else if(expr.id() == ID_symbol)
34  return true;
35  else
36  return false;
37 }
38 exprt make_binary(const exprt &expr)
39 {
40  const exprt::operandst &operands=expr.operands();
41 
42  if(operands.size()<=2)
43  return expr;
44 
45  // types must be identical for make_binary to be safe to use
46  const typet &type=expr.type();
47 
48  exprt previous=operands.front();
49  PRECONDITION(previous.type()==type);
50 
51  for(exprt::operandst::const_iterator
52  it=++operands.begin();
53  it!=operands.end();
54  ++it)
55  {
56  PRECONDITION(it->type()==type);
57 
58  exprt tmp=expr;
59  tmp.operands().clear();
60  tmp.operands().resize(2);
61  to_binary_expr(tmp).op0().swap(previous);
62  to_binary_expr(tmp).op1() = *it;
63  previous.swap(tmp);
64  }
65 
66  return previous;
67 }
68 
70 {
71  const exprt::operandst &designator=src.designator();
72  PRECONDITION(!designator.empty());
73 
74  with_exprt result{exprt{}, exprt{}, exprt{}};
75  exprt *dest=&result;
76 
77  for(const auto &expr : designator)
78  {
79  with_exprt tmp{exprt{}, exprt{}, exprt{}};
80 
81  if(expr.id() == ID_index_designator)
82  {
83  tmp.where() = to_index_designator(expr).index();
84  }
85  else if(expr.id() == ID_member_designator)
86  {
87  // irep_idt component_name=
88  // to_member_designator(*it).get_component_name();
89  }
90  else
92 
93  *dest=tmp;
94  dest=&to_with_expr(*dest).new_value();
95  }
96 
97  return result;
98 }
99 
101  const exprt &src,
102  const namespacet &ns)
103 {
104  // We frequently need to check if a numerical type is not zero.
105  // We replace (_Bool)x by x!=0; use ieee_float_notequal for floats.
106  // Note that this returns a proper bool_typet(), not a C/C++ boolean.
107  // To get a C/C++ boolean, add a further typecast.
108 
109  const typet &src_type = src.type().id() == ID_c_enum_tag
110  ? ns.follow_tag(to_c_enum_tag_type(src.type()))
111  : src.type();
112 
113  if(src_type.id()==ID_bool) // already there
114  return src; // do nothing
115 
116  irep_idt id=
117  src_type.id()==ID_floatbv?ID_ieee_float_notequal:ID_notequal;
118 
119  exprt zero=from_integer(0, src_type);
120  // Use tag type if applicable:
121  zero.type() = src.type();
122 
123  binary_relation_exprt comparison(src, id, std::move(zero));
124  comparison.add_source_location()=src.source_location();
125 
126  return std::move(comparison);
127 }
128 
130 {
131  if(src.id() == ID_not)
132  return to_not_expr(src).op();
133  else if(src.is_true())
134  return false_exprt();
135  else if(src.is_false())
136  return true_exprt();
137  else
138  return not_exprt(src);
139 }
140 
142  const exprt &expr,
143  const std::function<bool(const exprt &)> &pred)
144 {
145  const auto it = std::find_if(expr.depth_begin(), expr.depth_end(), pred);
146  return it != expr.depth_end();
147 }
148 
149 bool has_subexpr(const exprt &src, const irep_idt &id)
150 {
151  return has_subexpr(
152  src, [&](const exprt &subexpr) { return subexpr.id() == id; });
153 }
154 
156  const typet &type,
157  const std::function<bool(const typet &)> &pred,
158  const namespacet &ns)
159 {
160  std::vector<std::reference_wrapper<const typet>> stack;
161  std::unordered_set<typet, irep_hash> visited;
162 
163  const auto push_if_not_visited = [&](const typet &t) {
164  if(visited.insert(t).second)
165  stack.emplace_back(t);
166  };
167 
168  push_if_not_visited(type);
169  while(!stack.empty())
170  {
171  const typet &top = stack.back().get();
172  stack.pop_back();
173 
174  if(pred(top))
175  return true;
176  else if(top.id() == ID_c_enum_tag)
177  push_if_not_visited(ns.follow_tag(to_c_enum_tag_type(top)));
178  else if(top.id() == ID_struct_tag)
179  push_if_not_visited(ns.follow_tag(to_struct_tag_type(top)));
180  else if(top.id() == ID_union_tag)
181  push_if_not_visited(ns.follow_tag(to_union_tag_type(top)));
182  else if(top.id() == ID_struct || top.id() == ID_union)
183  {
184  for(const auto &comp : to_struct_union_type(top).components())
185  push_if_not_visited(comp.type());
186  }
187  else
188  {
189  for(const auto &subtype : to_type_with_subtypes(top).subtypes())
190  push_if_not_visited(subtype);
191  }
192  }
193 
194  return false;
195 }
196 
197 bool has_subtype(const typet &type, const irep_idt &id, const namespacet &ns)
198 {
199  return has_subtype(
200  type, [&](const typet &subtype) { return subtype.id() == id; }, ns);
201 }
202 
203 if_exprt lift_if(const exprt &src, std::size_t operand_number)
204 {
205  PRECONDITION(operand_number<src.operands().size());
206  PRECONDITION(src.operands()[operand_number].id()==ID_if);
207 
208  const if_exprt if_expr=to_if_expr(src.operands()[operand_number]);
209  const exprt true_case=if_expr.true_case();
210  const exprt false_case=if_expr.false_case();
211 
212  if_exprt result(if_expr.cond(), src, src);
213  result.true_case().operands()[operand_number]=true_case;
214  result.false_case().operands()[operand_number]=false_case;
215 
216  return result;
217 }
218 
219 const exprt &skip_typecast(const exprt &expr)
220 {
221  if(expr.id()!=ID_typecast)
222  return expr;
223 
224  return skip_typecast(to_typecast_expr(expr).op());
225 }
226 
229 bool is_constantt::is_constant(const exprt &expr) const
230 {
231  if(expr.is_constant())
232  return true;
233 
234  if(expr.id() == ID_address_of)
235  {
236  return is_constant_address_of(to_address_of_expr(expr).object());
237  }
238  else if(
239  expr.id() == ID_typecast || expr.id() == ID_array_of ||
240  expr.id() == ID_plus || expr.id() == ID_mult || expr.id() == ID_array ||
241  expr.id() == ID_with || expr.id() == ID_struct || expr.id() == ID_union ||
242  // byte_update works, byte_extract may be out-of-bounds
243  expr.id() == ID_byte_update_big_endian ||
244  expr.id() == ID_byte_update_little_endian)
245  {
246  return std::all_of(
247  expr.operands().begin(), expr.operands().end(), [this](const exprt &e) {
248  return is_constant(e);
249  });
250  }
251 
252  return false;
253 }
254 
257 {
258  if(expr.id() == ID_symbol)
259  {
260  return true;
261  }
262  else if(expr.id() == ID_index)
263  {
264  const index_exprt &index_expr = to_index_expr(expr);
265 
266  return is_constant_address_of(index_expr.array()) &&
267  is_constant(index_expr.index());
268  }
269  else if(expr.id() == ID_member)
270  {
271  return is_constant_address_of(to_member_expr(expr).compound());
272  }
273  else if(expr.id() == ID_dereference)
274  {
275  const dereference_exprt &deref = to_dereference_expr(expr);
276 
277  return is_constant(deref.pointer());
278  }
279  else if(expr.id() == ID_string_constant)
280  return true;
281 
282  return false;
283 }
284 
286 {
287  if(value)
288  return true_exprt();
289  else
290  return false_exprt();
291 }
292 
294 {
295  PRECONDITION(a.type().id() == ID_bool && b.type().id() == ID_bool);
296  if(b.is_constant())
297  {
298  if(b.get(ID_value) == ID_false)
299  return false_exprt{};
300  return a;
301  }
302  if(a.is_constant())
303  {
304  if(a.get(ID_value) == ID_false)
305  return false_exprt{};
306  return b;
307  }
308  if(b.id() == ID_and)
309  {
310  b.add_to_operands(std::move(a));
311  return b;
312  }
313  return and_exprt{std::move(a), std::move(b)};
314 }
with_exprt
Operator to update elements in structs and arrays.
Definition: std_expr.h:2172
to_union_tag_type
const union_tag_typet & to_union_tag_type(const typet &type)
Cast a typet to a union_tag_typet.
Definition: c_types.h:189
UNREACHABLE
#define UNREACHABLE
This should be used to mark dead code.
Definition: invariant.h:504
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
make_and
exprt make_and(exprt a, exprt b)
Conjunction of two expressions.
Definition: expr_util.cpp:293
skip_typecast
const exprt & skip_typecast(const exprt &expr)
find the expression nested inside typecasts, if any
Definition: expr_util.cpp:219
has_subexpr
bool has_subexpr(const exprt &expr, const std::function< bool(const exprt &)> &pred)
returns true if the expression has a subexpression that satisfies pred
Definition: expr_util.cpp:141
arith_tools.h
exprt::depth_begin
depth_iteratort depth_begin()
Definition: expr.cpp:292
to_struct_union_type
const struct_union_typet & to_struct_union_type(const typet &type)
Cast a typet to a struct_union_typet.
Definition: std_types.h:208
to_dereference_expr
const dereference_exprt & to_dereference_expr(const exprt &expr)
Cast an exprt to a dereference_exprt.
Definition: pointer_expr.h:442
typet
The type of an expression, extends irept.
Definition: type.h:28
to_index_expr
const index_exprt & to_index_expr(const exprt &expr)
Cast an exprt to an index_exprt.
Definition: std_expr.h:1296
to_if_expr
const if_exprt & to_if_expr(const exprt &expr)
Cast an exprt to an if_exprt.
Definition: std_expr.h:2151
dereference_exprt
Operator to dereference a pointer.
Definition: pointer_expr.h:386
if_exprt
The trinary if-then-else operator.
Definition: std_expr.h:2086
is_constantt::is_constant_address_of
virtual bool is_constant_address_of(const exprt &) const
this function determines which reference-typed expressions are constant
Definition: expr_util.cpp:256
with_exprt::new_value
exprt & new_value()
Definition: std_expr.h:2202
fixedbv.h
and_exprt
Boolean AND.
Definition: std_expr.h:1834
to_type_with_subtypes
const type_with_subtypest & to_type_with_subtypes(const typet &type)
Definition: type.h:198
exprt
Base class for all expressions.
Definition: expr.h:54
namespace_baset::follow_tag
const union_typet & follow_tag(const union_tag_typet &) const
Follow type tag of union type.
Definition: namespace.cpp:66
lift_if
if_exprt lift_if(const exprt &src, std::size_t operand_number)
lift up an if_exprt one level
Definition: expr_util.cpp:203
exprt::is_true
bool is_true() const
Return whether the expression is a constant representing true.
Definition: expr.cpp:60
make_binary
exprt make_binary(const exprt &expr)
splits an expression with >=3 operands into nested binary expressions
Definition: expr_util.cpp:38
namespace.h
if_exprt::false_case
exprt & false_case()
Definition: std_expr.h:2123
exprt::is_false
bool is_false() const
Return whether the expression is a constant representing false.
Definition: expr.cpp:69
to_binary_expr
const binary_exprt & to_binary_expr(const exprt &expr)
Cast an exprt to a binary_exprt.
Definition: std_expr.h:627
expr.h
namespacet
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:92
is_constantt::is_constant
virtual bool is_constant(const exprt &) const
This function determines what expressions are to be propagated as "constants".
Definition: expr_util.cpp:229
exprt::type
typet & type()
Return the type of the expression.
Definition: expr.h:82
to_c_enum_tag_type
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:317
PRECONDITION
#define PRECONDITION(CONDITION)
Definition: invariant.h:464
has_subtype
bool has_subtype(const typet &type, const std::function< bool(const typet &)> &pred, const namespacet &ns)
returns true if any of the contained types satisfies pred
Definition: expr_util.cpp:155
dereference_exprt::pointer
exprt & pointer()
Definition: pointer_expr.h:399
boolean_negate
exprt boolean_negate(const exprt &src)
negate a Boolean expression, possibly removing a not_exprt, and swapping false and true
Definition: expr_util.cpp:129
index_designatort::index
const exprt & index() const
Definition: std_expr.h:2259
pointer_expr.h
API to expression classes for Pointers.
index_exprt::index
exprt & index()
Definition: std_expr.h:1268
index_exprt::array
exprt & array()
Definition: std_expr.h:1258
irept::swap
void swap(irept &irep)
Definition: irep.h:453
symbol.h
Symbol table entry.
irept::id
const irep_idt & id() const
Definition: irep.h:407
to_struct_tag_type
const struct_tag_typet & to_struct_tag_type(const typet &type)
Cast a typet to a struct_tag_typet.
Definition: std_types.h:468
exprt::operandst
std::vector< exprt > operandst
Definition: expr.h:56
false_exprt
The Boolean constant false.
Definition: std_expr.h:2725
unary_exprt::op
const exprt & op() const
Definition: std_expr.h:293
to_with_expr
const with_exprt & to_with_expr(const exprt &expr)
Cast an exprt to a with_exprt.
Definition: std_expr.h:2234
update_exprt
Operator to update elements in structs and arrays.
Definition: std_expr.h:2356
update_exprt::designator
exprt::operandst & designator()
Definition: std_expr.h:2382
expr_util.h
Deprecated expression utility functions.
expr_iterator.h
Forward depth-first search iterators These iterators' copy operations are expensive,...
if_exprt::true_case
exprt & true_case()
Definition: std_expr.h:2113
to_not_expr
const not_exprt & to_not_expr(const exprt &expr)
Cast an exprt to an not_exprt.
Definition: std_expr.h:2066
irept::get
const irep_idt & get(const irep_namet &name) const
Definition: irep.cpp:51
is_not_zero
exprt is_not_zero(const exprt &src, const namespacet &ns)
converts a scalar/float expression to C/C++ Booleans
Definition: expr_util.cpp:100
from_integer
constant_exprt from_integer(const mp_integer &int_value, const typet &type)
Definition: arith_tools.cpp:100
to_typecast_expr
const typecast_exprt & to_typecast_expr(const exprt &expr)
Cast an exprt to a typecast_exprt.
Definition: std_expr.h:1814
ieee_float.h
exprt::is_constant
bool is_constant() const
Return whether the expression is a constant.
Definition: expr.cpp:53
if_exprt::cond
exprt & cond()
Definition: std_expr.h:2103
binary_relation_exprt
A base class for relations, i.e., binary predicates whose two operands have the same type.
Definition: std_expr.h:674
exprt::add_to_operands
void add_to_operands(const exprt &expr)
Add the given argument to the end of exprt's operands.
Definition: expr.h:144
to_member_expr
const member_exprt & to_member_expr(const exprt &expr)
Cast an exprt to a member_exprt.
Definition: std_expr.h:2611
make_boolean_expr
constant_exprt make_boolean_expr(bool value)
returns true_exprt if given true and false_exprt otherwise
Definition: expr_util.cpp:285
make_with_expr
with_exprt make_with_expr(const update_exprt &src)
converts an update expr into a (possibly nested) with expression
Definition: expr_util.cpp:69
to_address_of_expr
const address_of_exprt & to_address_of_expr(const exprt &expr)
Cast an exprt to an address_of_exprt.
Definition: pointer_expr.h:367
exprt::operands
operandst & operands()
Definition: expr.h:96
index_exprt
Array index operator.
Definition: std_expr.h:1242
exprt::add_source_location
source_locationt & add_source_location()
Definition: expr.h:243
true_exprt
The Boolean constant true.
Definition: std_expr.h:2716
constant_exprt
A constant literal expression.
Definition: std_expr.h:2667
exprt::depth_end
depth_iteratort depth_end()
Definition: expr.cpp:294
binary_exprt::op1
exprt & op1()
Definition: expr.h:106
std_expr.h
API to expression classes.
exprt::source_location
const source_locationt & source_location() const
Definition: expr.h:238
c_types.h
binary_exprt::op0
exprt & op0()
Definition: expr.h:103
to_index_designator
const index_designatort & to_index_designator(const exprt &expr)
Cast an exprt to an index_designatort.
Definition: std_expr.h:2287
is_lvalue
bool is_lvalue(const exprt &expr)
Returns true iff the argument is (syntactically) an lvalue.
Definition: expr_util.cpp:25
not_exprt
Boolean negation.
Definition: std_expr.h:2041