cprover
find_symbols.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 "find_symbols.h"
10 
11 #include "expr_iterator.h"
12 #include "range.h"
13 #include "std_expr.h"
14 #include "std_types.h"
15 
17 
19 {
20  find_symbols(src, dest, true, true);
21 }
22 
24  const exprt &src,
25  find_symbols_sett &dest,
26  bool current,
27  bool next)
28 {
29  src.visit_pre([&dest, current, next](const exprt &e) {
30  if(e.id() == ID_symbol && current)
31  dest.insert(to_symbol_expr(e).get_identifier());
32  else if(e.id() == ID_next_symbol && next)
33  dest.insert(e.get(ID_identifier));
34  });
35 }
36 
38  const exprt &src,
39  const find_symbols_sett &symbols,
40  bool current,
41  bool next)
42 {
43  if(src.id() == ID_symbol && current)
44  return symbols.count(to_symbol_expr(src).get_identifier()) != 0;
45  else if(src.id() == ID_next_symbol && next)
46  return symbols.count(src.get(ID_identifier))!=0;
47  else
48  {
49  forall_operands(it, src)
50  if(has_symbol(*it, symbols, current, next))
51  return true;
52  }
53 
54  return false;
55 }
56 
58  const exprt &src,
59  const find_symbols_sett &symbols)
60 {
61  return has_symbol(src, symbols, true, true);
62 }
63 
65  const exprt &src,
66  std::set<exprt> &dest)
67 {
68  src.visit_pre([&dest](const exprt &e) {
69  if(e.id() == ID_symbol || e.id() == ID_next_symbol)
70  dest.insert(e);
71  });
72 }
73 
75  const exprt &src,
76  std::set<symbol_exprt> &dest)
77 {
78  src.visit_pre([&dest](const exprt &e) {
79  if(e.id() == ID_symbol)
80  dest.insert(to_symbol_expr(e));
81  });
82 }
83 
84 std::set<symbol_exprt> find_symbols(const exprt &src)
85 {
86  return make_range(src.depth_begin(), src.depth_end())
87  .filter([](const exprt &e) { return e.id() == ID_symbol; })
88  .map([](const exprt &e) { return to_symbol_expr(e); });
89 }
90 
91 std::unordered_set<irep_idt> find_symbol_identifiers(const exprt &src)
92 {
93  std::unordered_set<irep_idt> result;
94  src.visit_pre([&](const exprt &e) {
95  if(e.id() == ID_symbol)
96  result.insert(to_symbol_expr(e).get_identifier());
97  });
98  return result;
99 }
100 
101 void find_symbols(kindt kind, const typet &src, find_symbols_sett &dest);
102 
103 void find_symbols(kindt kind, const exprt &src, find_symbols_sett &dest)
104 {
105  forall_operands(it, src)
106  find_symbols(kind, *it, dest);
107 
108  find_symbols(kind, src.type(), dest);
109 
110  if(kind==kindt::F_BOTH || kind==kindt::F_EXPR)
111  {
112  if(src.id() == ID_symbol)
113  dest.insert(to_symbol_expr(src).get_identifier());
114  else if(src.id() == ID_next_symbol)
115  dest.insert(src.get(ID_identifier));
116  }
117 
118  const irept &c_sizeof_type=src.find(ID_C_c_sizeof_type);
119 
120  if(c_sizeof_type.is_not_nil())
121  find_symbols(kind, static_cast<const typet &>(c_sizeof_type), dest);
122 
123  const irept &va_arg_type=src.find(ID_C_va_arg_type);
124 
125  if(va_arg_type.is_not_nil())
126  find_symbols(kind, static_cast<const typet &>(va_arg_type), dest);
127 }
128 
129 void find_symbols(kindt kind, const typet &src, find_symbols_sett &dest)
130 {
131  if(kind!=kindt::F_TYPE_NON_PTR ||
132  src.id()!=ID_pointer)
133  {
134  if(src.has_subtype())
135  find_symbols(kind, to_type_with_subtype(src).subtype(), dest);
136 
137  forall_subtypes(it, src)
138  find_symbols(kind, *it, dest);
139 
140  const irep_idt &typedef_name=src.get(ID_C_typedef);
141  if(!typedef_name.empty())
142  dest.insert(typedef_name);
143  }
144 
145  if(src.id()==ID_struct ||
146  src.id()==ID_union)
147  {
148  const struct_union_typet &struct_union_type=to_struct_union_type(src);
149 
150  for(const auto &c : struct_union_type.components())
151  find_symbols(kind, c, dest);
152  }
153  else if(src.id()==ID_code)
154  {
155  const code_typet &code_type=to_code_type(src);
156  find_symbols(kind, code_type.return_type(), dest);
157 
158  for(const auto &p : code_type.parameters())
159  {
160  find_symbols(kind, p, dest);
161 
162  // irep_idt identifier=it->get_identifier();
163  // if(!identifier.empty() && (kind==F_TYPE || kind==F_BOTH))
164  // dest.insert(identifier);
165  }
166  }
167  else if(src.id()==ID_array)
168  {
169  // do the size -- the subtype is already done
170  find_symbols(kind, to_array_type(src).size(), dest);
171  }
172  else if(src.id()==ID_c_enum_tag)
173  {
174  dest.insert(to_c_enum_tag_type(src).get_identifier());
175  }
176  else if(src.id()==ID_struct_tag)
177  {
178  dest.insert(to_struct_tag_type(src).get_identifier());
179  }
180  else if(src.id()==ID_union_tag)
181  {
182  dest.insert(to_union_tag_type(src).get_identifier());
183  }
184 }
185 
187 {
188  find_symbols(kindt::F_TYPE, src, dest);
189 }
190 
192 {
193  find_symbols(kindt::F_TYPE, src, dest);
194 }
195 
197  const exprt &src,
198  find_symbols_sett &dest)
199 {
201 }
202 
204  const typet &src,
205  find_symbols_sett &dest)
206 {
208 }
209 
211 {
212  find_symbols(kindt::F_BOTH, src, dest);
213 }
214 
216 {
217  find_symbols(kindt::F_BOTH, src, dest);
218 }
struct_union_typet::components
const componentst & components() const
Definition: std_types.h:142
to_union_tag_type
const union_tag_typet & to_union_tag_type(const typet &type)
Cast a typet to a union_tag_typet.
Definition: std_types.h:555
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
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: std_types.h:721
find_type_and_expr_symbols
void find_type_and_expr_symbols(const exprt &src, find_symbols_sett &dest)
Definition: find_symbols.cpp:210
exprt::depth_begin
depth_iteratort depth_begin()
Definition: expr.cpp:331
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:209
typet
The type of an expression, extends irept.
Definition: type.h:29
find_symbols_or_nexts
void find_symbols_or_nexts(const exprt &src, find_symbols_sett &dest)
Add to the set dest the sub-expressions of src with id ID_symbol or ID_next_symbol.
Definition: find_symbols.cpp:18
typet::has_subtype
bool has_subtype() const
Definition: type.h:65
struct_union_typet
Base type for structs and unions.
Definition: std_types.h:57
find_non_pointer_type_symbols
void find_non_pointer_type_symbols(const exprt &src, find_symbols_sett &dest)
Definition: find_symbols.cpp:196
find_symbol_identifiers
std::unordered_set< irep_idt > find_symbol_identifiers(const exprt &src)
Find identifiers of the sub expressions with id ID_symbol.
Definition: find_symbols.cpp:91
kindt::F_EXPR
@ F_EXPR
irept::find
const irept & find(const irep_namet &name) const
Definition: irep.cpp:103
to_type_with_subtype
const type_with_subtypet & to_type_with_subtype(const typet &type)
Definition: type.h:162
exprt
Base class for all expressions.
Definition: expr.h:53
kindt
kindt
Definition: find_symbols.cpp:16
exprt::type
typet & type()
Return the type of the expression.
Definition: expr.h:81
irept::is_not_nil
bool is_not_nil() const
Definition: irep.h:402
to_code_type
const code_typet & to_code_type(const typet &type)
Cast a typet to a code_typet.
Definition: std_types.h:946
find_symbols.h
forall_operands
#define forall_operands(it, expr)
Definition: expr.h:18
std_types.h
Pre-defined types.
find_type_symbols
void find_type_symbols(const exprt &src, find_symbols_sett &dest)
Definition: find_symbols.cpp:186
kindt::F_TYPE
@ F_TYPE
kindt::F_TYPE_NON_PTR
@ F_TYPE_NON_PTR
to_symbol_expr
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition: std_expr.h:177
code_typet
Base type of functions.
Definition: std_types.h:736
irept::id
const irep_idt & id() const
Definition: irep.h:418
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:515
range.h
Ranges: pair of begin and end iterators, which can be initialized from containers,...
dstringt::empty
bool empty() const
Definition: dstring.h:88
find_symbols
void find_symbols(const exprt &src, find_symbols_sett &dest, bool current, bool next)
Add to the set dest the sub-expressions of src with id ID_symbol if current is true,...
Definition: find_symbols.cpp:23
code_typet::parameters
const parameterst & parameters() const
Definition: std_types.h:857
forall_subtypes
#define forall_subtypes(it, type)
Definition: type.h:216
has_symbol
bool has_symbol(const exprt &src, const find_symbols_sett &symbols, bool current, bool next)
Definition: find_symbols.cpp:37
kindt::F_BOTH
@ F_BOTH
expr_iterator.h
Forward depth-first search iterators These iterators' copy operations are expensive,...
find_symbols_sett
std::unordered_set< irep_idt > find_symbols_sett
Definition: find_symbols.h:22
irept::get
const irep_idt & get(const irep_namet &name) const
Definition: irep.cpp:51
to_array_type
const array_typet & to_array_type(const typet &type)
Cast a typet to an array_typet.
Definition: std_types.h:1011
exprt::visit_pre
void visit_pre(std::function< void(exprt &)>)
Definition: expr.cpp:311
code_typet::return_type
const typet & return_type() const
Definition: std_types.h:847
irept
There are a large number of kinds of tree structured or tree-like data in CPROVER.
Definition: irep.h:394
exprt::depth_end
depth_iteratort depth_end()
Definition: expr.cpp:333
std_expr.h
API to expression classes.
make_range
ranget< iteratort > make_range(iteratort begin, iteratort end)
Definition: range.h:524