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/c_types.h>
16 #include <util/invariant.h>
17 #include <util/namespace.h>
19 #include <util/std_expr.h>
20 #include <util/std_types.h>
21 #include <util/symbol_table.h>
22 
23 #include <regex>
24 
25 typedef std::unordered_map<irep_idt, std::pair<size_t, bool>> symbol_numbert;
26 
27 static std::string type2name(
28  const typet &type,
29  const namespacet &ns,
30  symbol_numbert &symbol_number);
31 
32 static std::string type2name_tag(
33  const tag_typet &type,
34  const namespacet &ns,
35  symbol_numbert &symbol_number)
36 {
37  const irep_idt &identifier = type.get_identifier();
38 
39  const symbolt *symbol;
40 
41  if(ns.lookup(identifier, symbol))
42  return "SYM#"+id2string(identifier)+"#";
43 
44  assert(symbol && symbol->is_type);
45 
46  if(symbol->type.id()!=ID_struct &&
47  symbol->type.id()!=ID_union)
48  return type2name(symbol->type, ns, symbol_number);
49 
50  // assign each symbol a number when seen for the first time
51  std::pair<symbol_numbert::iterator, bool> entry=
52  symbol_number.insert(std::make_pair(
53  identifier,
54  std::make_pair(symbol_number.size(), true)));
55 
56  std::string result = "SYM" +
58  '#' + std::to_string(entry.first->second.first);
59 
60  // new entry, add definition
61  if(entry.second)
62  {
63  result+="={";
64  result+=type2name(symbol->type, ns, symbol_number);
65  result+='}';
66 
67  entry.first->second.second=false;
68  }
69 
70  return result;
71 }
72 
73 static std::string pointer_offset_bits_as_string(
74  const typet &type,
75  const namespacet &ns)
76 {
77  auto bits = pointer_offset_bits(type, ns);
78  CHECK_RETURN(bits.has_value());
79  return integer2string(*bits);
80 }
81 
82 static std::string type2name(
83  const typet &type,
84  const namespacet &ns,
85  symbol_numbert &symbol_number)
86 {
87  std::string result;
88 
89  // qualifiers first
90  if(type.get_bool(ID_C_constant))
91  result+='c';
92 
93  if(type.get_bool(ID_C_restricted))
94  result+='r';
95 
96  if(type.get_bool(ID_C_volatile))
97  result+='v';
98 
99  if(type.get_bool(ID_C_transparent_union))
100  result+='t';
101 
102  if(type.get_bool(ID_C_noreturn))
103  result+='n';
104 
105  // this isn't really a qualifier, but the linker needs to
106  // distinguish these - should likely be fixed in the linker instead
107  if(!type.source_location().get_function().empty())
108  result+='l';
109 
110  if(type.id().empty())
111  throw "empty type encountered";
112  else if(type.id()==ID_empty)
113  result+='V';
114  else if(type.id()==ID_signedbv)
115  result+="S" + pointer_offset_bits_as_string(type, ns);
116  else if(type.id()==ID_unsignedbv)
117  result+="U" + pointer_offset_bits_as_string(type, ns);
118  else if(type.id()==ID_bool ||
119  type.id()==ID_c_bool)
120  result+='B';
121  else if(type.id()==ID_integer)
122  result+='I';
123  else if(type.id()==ID_real)
124  result+='R';
125  else if(type.id()==ID_complex)
126  result+='C';
127  else if(type.id()==ID_floatbv)
128  result+="F" + pointer_offset_bits_as_string(type, ns);
129  else if(type.id()==ID_fixedbv)
130  result+="X" + pointer_offset_bits_as_string(type, ns);
131  else if(type.id()==ID_natural)
132  result+='N';
133  else if(type.id()==ID_pointer)
134  {
135  if(type.get_bool(ID_C_reference))
136  result+='&';
137  else
138  result+='*';
139  }
140  else if(type.id()==ID_code)
141  {
142  const code_typet &t=to_code_type(type);
143  const code_typet::parameterst parameters=t.parameters();
144  result+=type2name(t.return_type(), ns, symbol_number)+"(";
145 
146  for(code_typet::parameterst::const_iterator
147  it=parameters.begin();
148  it!=parameters.end();
149  it++)
150  {
151  if(it!=parameters.begin())
152  result+='|';
153  result+=type2name(it->type(), ns, symbol_number);
154  }
155 
156  if(t.has_ellipsis())
157  {
158  if(!parameters.empty())
159  result+='|';
160  result+="...";
161  }
162 
163  result+=")->";
164  result+=type2name(t.return_type(), ns, symbol_number);
165  }
166  else if(type.id()==ID_array)
167  {
168  const exprt &size = to_array_type(type).size();
169 
170  if(size.id() == ID_symbol)
171  result += "ARR" + id2string(to_symbol_expr(size).get_identifier());
172  else
173  {
174  const auto size_int = numeric_cast<mp_integer>(size);
175 
176  if(!size_int.has_value())
177  result += "ARR?";
178  else
179  result += "ARR" + integer2string(*size_int);
180  }
181  }
182  else if(
183  type.id() == ID_c_enum_tag || type.id() == ID_struct_tag ||
184  type.id() == ID_union_tag)
185  {
186  result += type2name_tag(to_tag_type(type), ns, symbol_number);
187  }
188  else if(type.id()==ID_struct ||
189  type.id()==ID_union)
190  {
191  const auto &struct_union_type = to_struct_union_type(type);
192 
193  if(struct_union_type.is_incomplete())
194  {
195  if(type.id() == ID_struct)
196  result += "ST?";
197  else if(type.id() == ID_union)
198  result += "UN?";
199  }
200  else
201  {
202  if(type.id() == ID_struct)
203  result += "ST";
204  if(type.id() == ID_union)
205  result += "UN";
206  result += '[';
207  bool first = true;
208  for(const auto &c : struct_union_type.components())
209  {
210  if(!first)
211  result += '|';
212  else
213  first = false;
214 
215  result += type2name(c.type(), ns, symbol_number);
216  const irep_idt &component_name = c.get_name();
217  CHECK_RETURN(!component_name.empty());
218  result += "'" + id2string(component_name) + "'";
219  }
220  result += ']';
221  }
222  }
223  else if(type.id()==ID_c_enum)
224  {
225  const c_enum_typet &t=to_c_enum_type(type);
226 
227  if(t.is_incomplete())
228  result += "EN?";
229  else
230  {
231  result += "EN";
232  const c_enum_typet::memberst &members = t.members();
233  result += '[';
234  for(c_enum_typet::memberst::const_iterator it = members.begin();
235  it != members.end();
236  ++it)
237  {
238  if(it != members.begin())
239  result += '|';
240  result += id2string(it->get_value());
241  result += "'" + id2string(it->get_identifier()) + "'";
242  }
243  }
244  }
245  else if(type.id()==ID_c_bit_field)
246  result+="BF"+pointer_offset_bits_as_string(type, ns);
247  else if(type.id()==ID_vector)
248  result+="VEC"+type.get_string(ID_size);
249  else
250  throw "unknown type '"+type.id_string()+"' encountered";
251 
252  if(type.has_subtype())
253  {
254  result+='{';
255  result+=type2name(type.subtype(), ns, symbol_number);
256  result+='}';
257  }
258 
259  if(type.has_subtypes())
260  {
261  result+='$';
262  for(const typet &subtype : to_type_with_subtypes(type).subtypes())
263  {
264  result += type2name(subtype, ns, symbol_number);
265  result+='|';
266  }
267  result[result.size()-1]='$';
268  }
269 
270  return result;
271 }
272 
273 std::string type2name(const typet &type, const namespacet &ns)
274 {
275  symbol_numbert symbol_number;
276  return type2name(type, ns, symbol_number);
277 }
278 
283 std::string type_name2type_identifier(const std::string &name)
284 {
285  const auto replace_special_characters = [](const std::string &name) {
286  std::string result{};
287  for(char c : name)
288  {
289  switch(c)
290  {
291  case '*':
292  result += "_ptr_";
293  break;
294  case '{':
295  result += "_start_sub_";
296  break;
297  case '}':
298  result += "_end_sub_";
299  break;
300  default:
301  result += c;
302  break;
303  }
304  }
305  return result;
306  };
307  const auto replace_invalid_characters_with_underscore =
308  [](const std::string &identifier) {
309  static const std::regex non_alpha_numeric{"[^A-Za-z0-9\x80-\xff]+"};
310  return std::regex_replace(identifier, non_alpha_numeric, "_");
311  };
312  const auto strip_leading_digits = [](const std::string &identifier) {
313  static const std::regex identifier_regex{
314  "[A-Za-z\x80-\xff_][A-Za-z0-9_\x80-\xff]*"};
315  std::smatch match_results;
316  bool found = std::regex_search(identifier, match_results, identifier_regex);
317  POSTCONDITION(found);
318  return match_results.str(0);
319  };
320  return strip_leading_digits(replace_invalid_characters_with_underscore(
321  replace_special_characters(name)));
322 }
323 
324 std::string type_to_partial_identifier(const typet &type, const namespacet &ns)
325 {
326  return type_name2type_identifier(type2name(type, ns));
327 }
tag_typet::get_identifier
const irep_idt & get_identifier() const
Definition: std_types.h:404
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
pointer_offset_size.h
Pointer Logic.
source_locationt::get_function
const irep_idt & get_function() const
Definition: source_location.h:56
code_typet::has_ellipsis
bool has_ellipsis() const
Definition: std_types.h:605
symbol_numbert
std::unordered_map< irep_idt, std::pair< size_t, bool > > symbol_numbert
Definition: type2name.cpp:25
typet::subtype
const typet & subtype() const
Definition: type.h:47
c_enum_typet
The type of C enums.
Definition: c_types.h:204
c_enum_typet::is_incomplete
bool is_incomplete() const
enum types may be incomplete
Definition: c_types.h:248
arith_tools.h
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
CHECK_RETURN
#define CHECK_RETURN(CONDITION)
Definition: invariant.h:496
typet
The type of an expression, extends irept.
Definition: type.h:28
code_typet::parameterst
std::vector< parametert > parameterst
Definition: std_types.h:535
typet::has_subtype
bool has_subtype() const
Definition: type.h:65
symbolt::type
typet type
Type of symbol.
Definition: symbol.h:31
c_enum_typet::memberst
std::vector< c_enum_membert > memberst
Definition: c_types.h:240
to_c_enum_type
const c_enum_typet & to_c_enum_type(const typet &type)
Cast a typet to a c_enum_typet.
Definition: c_types.h:277
type2name.h
Type Naming for C.
typet::has_subtypes
bool has_subtypes() const
Definition: type.h:62
invariant.h
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
to_string
std::string to_string(const string_not_contains_constraintt &expr)
Used for debug printing.
Definition: string_constraint.cpp:55
namespace.h
type_name2type_identifier
std::string type_name2type_identifier(const std::string &name)
type2name generates strings that aren't valid C identifiers If we want utilities like dump_c to work ...
Definition: type2name.cpp:283
pointer_offset_bits_as_string
static std::string pointer_offset_bits_as_string(const typet &type, const namespacet &ns)
Definition: type2name.cpp:73
array_typet::size
const exprt & size() const
Definition: std_types.h:765
namespacet
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:92
namespacet::lookup
bool lookup(const irep_idt &name, const symbolt *&symbol) const override
See documentation for namespace_baset::lookup().
Definition: namespace.cpp:141
irept::get_bool
bool get_bool(const irep_namet &name) const
Definition: irep.cpp:64
struct_union_typet::get_tag
irep_idt get_tag() const
Definition: std_types.h:162
to_code_type
const code_typet & to_code_type(const typet &type)
Cast a typet to a code_typet.
Definition: std_types.h:738
messaget::result
mstreamt & result() const
Definition: message.h:409
to_tag_type
const tag_typet & to_tag_type(const typet &type)
Cast a typet to a tag_typet.
Definition: std_types.h:428
id2string
const std::string & id2string(const irep_idt &d)
Definition: irep.h:49
type2name
static std::string type2name(const typet &type, const namespacet &ns, symbol_numbert &symbol_number)
Definition: type2name.cpp:82
typet::source_location
const source_locationt & source_location() const
Definition: type.h:71
pointer_offset_bits
optionalt< mp_integer > pointer_offset_bits(const typet &type, const namespacet &ns)
Definition: pointer_offset_size.cpp:100
std_types.h
Pre-defined types.
irept::id_string
const std::string & id_string() const
Definition: irep.h:410
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:533
irept::id
const irep_idt & id() const
Definition: irep.h:407
dstringt::empty
bool empty() const
Definition: dstring.h:88
tag_typet
A tag-based type, i.e., typet with an identifier.
Definition: std_types.h:390
code_typet::parameters
const parameterst & parameters() const
Definition: std_types.h:649
type2name_tag
static std::string type2name_tag(const tag_typet &type, const namespacet &ns, symbol_numbert &symbol_number)
Definition: type2name.cpp:32
irept::get_string
const std::string & get_string(const irep_namet &name) const
Definition: irep.h:420
POSTCONDITION
#define POSTCONDITION(CONDITION)
Definition: invariant.h:480
symbolt
Symbol table entry.
Definition: symbol.h:28
symbolt::is_type
bool is_type
Definition: symbol.h:61
to_array_type
const array_typet & to_array_type(const typet &type)
Cast a typet to an array_typet.
Definition: std_types.h:807
type_to_partial_identifier
std::string type_to_partial_identifier(const typet &type, const namespacet &ns)
Constructs a string describing the given type, which can be used as part of a C identifier.
Definition: type2name.cpp:324
code_typet::return_type
const typet & return_type() const
Definition: std_types.h:639
symbol_table.h
Author: Diffblue Ltd.
std_expr.h
API to expression classes.
c_types.h
c_enum_typet::members
const memberst & members() const
Definition: c_types.h:242
integer2string
const std::string integer2string(const mp_integer &n, unsigned base)
Definition: mp_arith.cpp:106