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 "c_types.h"
12 #include "expr_iterator.h"
13 #include "range.h"
14 #include "std_expr.h"
15 
16 enum class kindt { F_TYPE, F_TYPE_NON_PTR, F_EXPR, F_BOTH };
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<symbol_exprt> &dest)
67 {
68  src.visit_pre([&dest](const exprt &e) {
69  if(e.id() == ID_symbol)
70  dest.insert(to_symbol_expr(e));
71  });
72 }
73 
74 std::set<symbol_exprt> find_symbols(const exprt &src)
75 {
76  return make_range(src.depth_begin(), src.depth_end())
77  .filter([](const exprt &e) { return e.id() == ID_symbol; })
78  .map([](const exprt &e) { return to_symbol_expr(e); });
79 }
80 
81 std::unordered_set<irep_idt> find_symbol_identifiers(const exprt &src)
82 {
83  std::unordered_set<irep_idt> result;
84  src.visit_pre([&](const exprt &e) {
85  if(e.id() == ID_symbol)
86  result.insert(to_symbol_expr(e).get_identifier());
87  });
88  return result;
89 }
90 
91 void find_symbols(kindt kind, const typet &src, find_symbols_sett &dest);
92 
93 void find_symbols(kindt kind, const exprt &src, find_symbols_sett &dest)
94 {
95  forall_operands(it, src)
96  find_symbols(kind, *it, dest);
97 
98  find_symbols(kind, src.type(), dest);
99 
100  if(kind==kindt::F_BOTH || kind==kindt::F_EXPR)
101  {
102  if(src.id() == ID_symbol)
103  dest.insert(to_symbol_expr(src).get_identifier());
104  else if(src.id() == ID_next_symbol)
105  dest.insert(src.get(ID_identifier));
106  }
107 
108  const irept &c_sizeof_type=src.find(ID_C_c_sizeof_type);
109 
110  if(c_sizeof_type.is_not_nil())
111  find_symbols(kind, static_cast<const typet &>(c_sizeof_type), dest);
112 
113  const irept &va_arg_type=src.find(ID_C_va_arg_type);
114 
115  if(va_arg_type.is_not_nil())
116  find_symbols(kind, static_cast<const typet &>(va_arg_type), dest);
117 }
118 
119 void find_symbols(kindt kind, const typet &src, find_symbols_sett &dest)
120 {
121  if(kind!=kindt::F_TYPE_NON_PTR ||
122  src.id()!=ID_pointer)
123  {
124  if(src.has_subtype())
125  find_symbols(kind, to_type_with_subtype(src).subtype(), dest);
126 
127  for(const typet &subtype : to_type_with_subtypes(src).subtypes())
128  find_symbols(kind, subtype, dest);
129 
130  const irep_idt &typedef_name=src.get(ID_C_typedef);
131  if(!typedef_name.empty())
132  dest.insert(typedef_name);
133  }
134 
135  if(src.id()==ID_struct ||
136  src.id()==ID_union)
137  {
138  const struct_union_typet &struct_union_type=to_struct_union_type(src);
139 
140  for(const auto &c : struct_union_type.components())
141  find_symbols(kind, c, dest);
142  }
143  else if(src.id()==ID_code)
144  {
145  const code_typet &code_type=to_code_type(src);
146  find_symbols(kind, code_type.return_type(), dest);
147 
148  for(const auto &p : code_type.parameters())
149  {
150  find_symbols(kind, p, dest);
151 
152  // irep_idt identifier=it->get_identifier();
153  // if(!identifier.empty() && (kind==F_TYPE || kind==F_BOTH))
154  // dest.insert(identifier);
155  }
156  }
157  else if(src.id()==ID_array)
158  {
159  // do the size -- the subtype is already done
160  find_symbols(kind, to_array_type(src).size(), dest);
161  }
162  else if(src.id()==ID_c_enum_tag)
163  {
164  dest.insert(to_c_enum_tag_type(src).get_identifier());
165  }
166  else if(src.id()==ID_struct_tag)
167  {
168  dest.insert(to_struct_tag_type(src).get_identifier());
169  }
170  else if(src.id()==ID_union_tag)
171  {
172  dest.insert(to_union_tag_type(src).get_identifier());
173  }
174 }
175 
177 {
178  find_symbols(kindt::F_TYPE, src, dest);
179 }
180 
182 {
183  find_symbols(kindt::F_TYPE, src, dest);
184 }
185 
187  const exprt &src,
188  find_symbols_sett &dest)
189 {
190  find_symbols(kindt::F_TYPE_NON_PTR, src, dest);
191 }
192 
194  const typet &src,
195  find_symbols_sett &dest)
196 {
197  find_symbols(kindt::F_TYPE_NON_PTR, src, dest);
198 }
199 
201 {
202  find_symbols(kindt::F_BOTH, src, dest);
203 }
204 
206 {
207  find_symbols(kindt::F_BOTH, src, dest);
208 }
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
struct_union_typet::components
const componentst & components() const
Definition: std_types.h:147
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
find_type_and_expr_symbols
void find_type_and_expr_symbols(const exprt &src, find_symbols_sett &dest)
Definition: find_symbols.cpp:200
exprt::depth_begin
depth_iteratort depth_begin()
Definition: expr.cpp:265
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:214
typet
The type of an expression, extends irept.
Definition: type.h:28
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:62
find_non_pointer_type_symbols
void find_non_pointer_type_symbols(const exprt &src, find_symbols_sett &dest)
Definition: find_symbols.cpp:186
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:81
irept::find
const irept & find(const irep_namet &name) const
Definition: irep.cpp:106
to_type_with_subtype
const type_with_subtypet & to_type_with_subtype(const typet &type)
Definition: type.h:154
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
kindt
kindt
Definition: find_symbols.cpp:16
exprt::type
typet & type()
Return the type of the expression.
Definition: expr.h:82
irept::is_not_nil
bool is_not_nil() const
Definition: irep.h:391
to_code_type
const code_typet & to_code_type(const typet &type)
Cast a typet to a code_typet.
Definition: std_types.h:744
find_symbols.h
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
forall_operands
#define forall_operands(it, expr)
Definition: expr.h:18
find_type_symbols
void find_type_symbols(const exprt &src, find_symbols_sett &dest)
Definition: find_symbols.cpp:176
kindt::F_TYPE
@ F_TYPE
to_symbol_expr
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition: std_expr.h:189
code_typet
Base type of functions.
Definition: std_types.h:539
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:474
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:655
has_symbol
bool has_symbol(const exprt &src, const find_symbols_sett &symbols, bool current, bool next)
Definition: find_symbols.cpp:37
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:21
irept::get
const irep_idt & get(const irep_namet &name) const
Definition: irep.cpp:45
to_array_type
const array_typet & to_array_type(const typet &type)
Cast a typet to an array_typet.
Definition: std_types.h:813
exprt::visit_pre
void visit_pre(std::function< void(exprt &)>)
Definition: expr.cpp:245
code_typet::return_type
const typet & return_type() const
Definition: std_types.h:645
irept
There are a large number of kinds of tree structured or tree-like data in CPROVER.
Definition: irep.h:383
exprt::depth_end
depth_iteratort depth_end()
Definition: expr.cpp:267
std_expr.h
API to expression classes.
make_range
ranget< iteratort > make_range(iteratort begin, iteratort end)
Definition: range.h:524
c_types.h