cprover
type2name.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Type Naming for C
4 
5 Author: Daniel Kroening, kroening@cs.cmu.edu
6 
7 \*******************************************************************/
8 
11 
12 #include "type2name.h"
13 
14 #include <util/arith_tools.h>
15 #include <util/invariant.h>
16 #include <util/namespace.h>
18 #include <util/std_expr.h>
19 #include <util/std_types.h>
20 #include <util/symbol_table.h>
21 
22 typedef std::unordered_map<irep_idt, std::pair<size_t, bool>> symbol_numbert;
23 
24 static std::string type2name(
25  const typet &type,
26  const namespacet &ns,
27  symbol_numbert &symbol_number);
28 
29 static std::string type2name_symbol(
30  const typet &type,
31  const namespacet &ns,
32  symbol_numbert &symbol_number)
33 {
34  const irep_idt &identifier=type.get(ID_identifier);
35 
36  const symbolt *symbol;
37 
38  if(ns.lookup(identifier, symbol))
39  return "SYM#"+id2string(identifier)+"#";
40 
41  assert(symbol && symbol->is_type);
42 
43  if(symbol->type.id()!=ID_struct &&
44  symbol->type.id()!=ID_union)
45  return type2name(symbol->type, ns, symbol_number);
46 
47  std::string result;
48 
49  // assign each symbol a number when seen for the first time
50  std::pair<symbol_numbert::iterator, bool> entry=
51  symbol_number.insert(std::make_pair(
52  identifier,
53  std::make_pair(symbol_number.size(), true)));
54 
55  // new entry, add definition
56  if(entry.second)
57  {
58  result="SYM#"+std::to_string(entry.first->second.first);
59  result+="={";
60  result+=type2name(symbol->type, ns, symbol_number);
61  result+='}';
62 
63  entry.first->second.second=false;
64  }
65 #if 0
66  // in recursion, print the shorthand only
67  else if(entry.first->second.second)
68  result="SYM#"+std::to_string(entry.first->second.first);
69  // entering recursion
70  else
71  {
72  entry.first->second.second=true;
73  result=type2name(symbol->type, ns, symbol_number);
74  entry.first->second.second=false;
75  }
76 #else
77  // shorthand only as structs/unions are always symbols
78  else
79  result="SYM#"+std::to_string(entry.first->second.first);
80 #endif
81 
82  return result;
83 }
84 
85 static std::string pointer_offset_bits_as_string(
86  const typet &type,
87  const namespacet &ns)
88 {
89  auto bits = pointer_offset_bits(type, ns);
90  CHECK_RETURN(bits.has_value());
91  return integer2string(*bits);
92 }
93 
94 static bool parent_is_sym_check=false;
95 static std::string type2name(
96  const typet &type,
97  const namespacet &ns,
98  symbol_numbert &symbol_number)
99 {
100  std::string result;
101 
102  // qualifiers first
103  if(type.get_bool(ID_C_constant))
104  result+='c';
105 
106  if(type.get_bool(ID_C_restricted))
107  result+='r';
108 
109  if(type.get_bool(ID_C_volatile))
110  result+='v';
111 
112  if(type.get_bool(ID_C_transparent_union))
113  result+='t';
114 
115  if(type.get_bool(ID_C_noreturn))
116  result+='n';
117 
118  // this isn't really a qualifier, but the linker needs to
119  // distinguish these - should likely be fixed in the linker instead
120  if(!type.source_location().get_function().empty())
121  result+='l';
122 
123  if(type.id().empty())
124  throw "empty type encountered";
125  else if(type.id()==ID_empty)
126  result+='V';
127  else if(type.id()==ID_signedbv)
128  result+="S" + pointer_offset_bits_as_string(type, ns);
129  else if(type.id()==ID_unsignedbv)
130  result+="U" + pointer_offset_bits_as_string(type, ns);
131  else if(type.id()==ID_bool ||
132  type.id()==ID_c_bool)
133  result+='B';
134  else if(type.id()==ID_integer)
135  result+='I';
136  else if(type.id()==ID_real)
137  result+='R';
138  else if(type.id()==ID_complex)
139  result+='C';
140  else if(type.id()==ID_floatbv)
141  result+="F" + pointer_offset_bits_as_string(type, ns);
142  else if(type.id()==ID_fixedbv)
143  result+="X" + pointer_offset_bits_as_string(type, ns);
144  else if(type.id()==ID_natural)
145  result+='N';
146  else if(type.id()==ID_pointer)
147  {
148  if(type.get_bool(ID_C_reference))
149  result+='&';
150  else
151  result+='*';
152  }
153  else if(type.id()==ID_code)
154  {
155  const code_typet &t=to_code_type(type);
156  const code_typet::parameterst parameters=t.parameters();
157  result+=type2name(t.return_type(), ns, symbol_number)+"(";
158 
159  for(code_typet::parameterst::const_iterator
160  it=parameters.begin();
161  it!=parameters.end();
162  it++)
163  {
164  if(it!=parameters.begin())
165  result+='|';
166  result+=type2name(it->type(), ns, symbol_number);
167  }
168 
169  if(t.has_ellipsis())
170  {
171  if(!parameters.empty())
172  result+='|';
173  result+="...";
174  }
175 
176  result+=")->";
177  result+=type2name(t.return_type(), ns, symbol_number);
178  }
179  else if(type.id()==ID_array)
180  {
181  const exprt &size = to_array_type(type).size();
182 
183  if(size.id() == ID_symbol)
184  result += "ARR" + id2string(to_symbol_expr(size).get_identifier());
185  else
186  {
187  const auto size_int = numeric_cast<mp_integer>(size);
188 
189  if(!size_int.has_value())
190  result += "ARR?";
191  else
192  result += "ARR" + integer2string(*size_int);
193  }
194  }
195  else if(
196  type.id() == ID_symbol_type || type.id() == ID_c_enum_tag ||
197  type.id() == ID_struct_tag || type.id() == ID_union_tag)
198  {
199  parent_is_sym_check=true;
200  result+=type2name_symbol(type, ns, symbol_number);
201  }
202  else if(type.id()==ID_struct ||
203  type.id()==ID_union)
204  {
205  assert(parent_is_sym_check);
206  parent_is_sym_check=false;
207  if(type.id()==ID_struct)
208  result+="ST";
209  if(type.id()==ID_union)
210  result+="UN";
211  result+='[';
212  bool first = true;
213  for(const auto &c : to_struct_union_type(type).components())
214  {
215  if(!first)
216  result+='|';
217  else
218  first = false;
219 
220  result += type2name(c.type(), ns, symbol_number);
221  const irep_idt &component_name = c.get_name();
222  CHECK_RETURN(!component_name.empty());
223  result+="'"+id2string(component_name)+"'";
224  }
225  result+=']';
226  }
227  else if(type.id()==ID_incomplete_struct)
228  result +="ST?";
229  else if(type.id()==ID_incomplete_union)
230  result +="UN?";
231  else if(type.id()==ID_c_enum)
232  {
233  result +="EN";
234  const c_enum_typet &t=to_c_enum_type(type);
235  const c_enum_typet::memberst &members=t.members();
236  result+='[';
237  for(c_enum_typet::memberst::const_iterator
238  it=members.begin();
239  it!=members.end();
240  ++it)
241  {
242  if(it!=members.begin())
243  result+='|';
244  result+=id2string(it->get_value());
245  result+="'"+id2string(it->get_identifier())+"'";
246  }
247  }
248  else if(type.id()==ID_incomplete_c_enum)
249  result +="EN?";
250  else if(type.id()==ID_c_bit_field)
251  result+="BF"+pointer_offset_bits_as_string(type, ns);
252  else if(type.id()==ID_vector)
253  result+="VEC"+type.get_string(ID_size);
254  else
255  throw "unknown type '"+type.id_string()+"' encountered";
256 
257  if(type.has_subtype())
258  {
259  result+='{';
260  result+=type2name(type.subtype(), ns, symbol_number);
261  result+='}';
262  }
263 
264  if(type.has_subtypes())
265  {
266  result+='$';
267  forall_subtypes(it, type)
268  {
269  result+=type2name(*it, ns, symbol_number);
270  result+='|';
271  }
272  result[result.size()-1]='$';
273  }
274 
275  return result;
276 }
277 
278 std::string type2name(const typet &type, const namespacet &ns)
279 {
280  parent_is_sym_check=true;
281  symbol_numbert symbol_number;
282  return type2name(type, ns, symbol_number);
283 }
284 
285 std::string type2name(const typet &type)
286 {
287  symbol_tablet symbol_table;
288  return type2name(type, namespacet(symbol_table));
289 }
static std::string type2name(const typet &type, const namespacet &ns, symbol_numbert &symbol_number)
Definition: type2name.cpp:95
The type of an expression, extends irept.
Definition: type.h:27
#define forall_subtypes(it, type)
Definition: type.h:216
bool has_subtypes() const
Definition: type.h:53
Base type of functions.
Definition: std_types.h:751
const std::string & id2string(const irep_idt &d)
Definition: irep.h:44
const std::string integer2string(const mp_integer &n, unsigned base)
Definition: mp_arith.cpp:106
bool has_subtype() const
Definition: type.h:56
std::string to_string(const string_not_contains_constraintt &expr)
Used for debug printing.
bool has_ellipsis() const
Definition: std_types.h:849
const code_typet & to_code_type(const typet &type)
Cast a typet to a code_typet.
Definition: std_types.h:982
const irep_idt & get_function() const
const irep_idt & get_identifier() const
Definition: std_expr.h:176
std::vector< parametert > parameterst
Definition: std_types.h:754
const componentst & components() const
Definition: std_types.h:205
const memberst & members() const
Definition: std_types.h:674
Symbol table entry.
Definition: symbol.h:27
#define CHECK_RETURN(CONDITION)
Definition: invariant.h:470
bool get_bool(const irep_namet &name) const
Definition: irep.cpp:239
const irep_idt & id() const
Definition: irep.h:259
API to expression classes.
The symbol table.
Definition: symbol_table.h:19
const irep_idt & get(const irep_namet &name) const
Definition: irep.cpp:212
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:93
static bool parent_is_sym_check
Definition: type2name.cpp:94
const exprt & size() const
Definition: std_types.h:1010
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
Definition: std_expr.h:251
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:35
Author: Diffblue Ltd.
std::unordered_map< irep_idt, std::pair< size_t, bool > > symbol_numbert
Definition: type2name.cpp:22
static std::string pointer_offset_bits_as_string(const typet &type, const namespacet &ns)
Definition: type2name.cpp:85
Pointer Logic.
const source_locationt & source_location() const
Definition: type.h:62
Type Naming for C.
static std::string type2name_symbol(const typet &type, const namespacet &ns, symbol_numbert &symbol_number)
Definition: type2name.cpp:29
typet type
Type of symbol.
Definition: symbol.h:31
Pre-defined types.
mstreamt & result() const
Definition: message.h:396
const array_typet & to_array_type(const typet &type)
Cast a typet to an array_typet.
Definition: std_types.h:1048
Base class for all expressions.
Definition: expr.h:54
const parameterst & parameters() const
Definition: std_types.h:893
const struct_union_typet & to_struct_union_type(const typet &type)
Cast a typet to a struct_union_typet.
Definition: std_types.h:260
const std::string & get_string(const irep_namet &name) const
Definition: irep.h:272
const std::string & id_string() const
Definition: irep.h:262
const c_enum_typet & to_c_enum_type(const typet &type)
Cast a typet to a c_enum_typet.
Definition: std_types.h:697
bool is_type
Definition: symbol.h:61
optionalt< mp_integer > pointer_offset_bits(const typet &type, const namespacet &ns)
const typet & subtype() const
Definition: type.h:38
std::vector< c_enum_membert > memberst
Definition: std_types.h:672
bool empty() const
Definition: dstring.h:75
The type of C enums.
Definition: std_types.h:647
const typet & return_type() const
Definition: std_types.h:883
bool lookup(const irep_idt &name, const symbolt *&symbol) const override
See documentation for namespace_baset::lookup().
Definition: namespace.cpp:166