cprover
symex_coverage.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Record and print code coverage of symbolic execution
4 
5 Author: Michael Tautschnig
6 
7 Date: March 2016
8 
9 \*******************************************************************/
10 
13 
14 #include "symex_coverage.h"
15 
16 #include <chrono>
17 #include <ctime>
18 #include <fstream>
19 #include <iostream>
20 
21 #include <util/string2int.h>
22 #include <util/xml.h>
23 
24 #include <langapi/language_util.h>
25 
28 
30 
32 {
33 public:
34  explicit coverage_recordt(const std::string &node_id)
35  : xml(node_id),
36  lines_covered(0),
37  lines_total(0),
40  {
41  }
42 
44  std::size_t lines_covered;
45  std::size_t lines_total;
46  std::size_t branches_covered;
47  std::size_t branches_total;
48 };
49 
51 {
52 public:
54  const namespacet &ns,
55  goto_functionst::function_mapt::const_iterator gf_it,
56  const symex_coveraget::coveraget &coverage);
57 
58  const irep_idt &get_file() const
59  {
60  return file_name;
61  }
62 
63 protected:
65 
67  {
69  {
70  }
71 
73  bool true_taken;
74  };
75 
77  {
79  {
80  }
81 
82  unsigned hits;
83  std::map<goto_programt::const_targett, coverage_conditiont> conditions;
84  };
85 
86  typedef std::map<unsigned, coverage_linet> coverage_lines_mapt;
87 
89  const goto_programt &goto_program,
90  const symex_coveraget::coveraget &coverage,
91  coverage_lines_mapt &dest);
92 };
93 
94 static std::string
95 rate(std::size_t covered, std::size_t total, bool per_cent = false)
96 {
97  std::ostringstream oss;
98 
99 #if 1
100  float fraction;
101 
102  if(total == 0)
103  fraction = 1.0;
104  else
105  fraction = static_cast<float>(covered) / static_cast<float>(total);
106 
107  if(per_cent)
108  oss << fraction * 100.0 << '%';
109  else
110  oss << fraction;
111 #else
112  oss << covered << " of " << total;
113 #endif
114 
115  return oss.str();
116 }
117 
118 static std::string
119 rate_detailed(std::size_t covered, std::size_t total, bool per_cent = false)
120 {
121  std::ostringstream oss;
122  oss << rate(covered, total, per_cent) << " (" << covered << '/' << total
123  << ')';
124  return oss.str();
125 }
126 
128  const namespacet &ns,
129  goto_functionst::function_mapt::const_iterator gf_it,
130  const symex_coveraget::coveraget &coverage)
131  : coverage_recordt("method")
132 {
133  PRECONDITION(gf_it->second.body_available());
134 
135  // identify the file name, inlined functions aren't properly
136  // accounted for
137  goto_programt::const_targett end_function =
138  --gf_it->second.body.instructions.end();
140  end_function->is_end_function(),
141  "last instruction in a function body is end function");
142  file_name = end_function->source_location.get_file();
143  DATA_INVARIANT(!file_name.empty(), "should have a valid source location");
144 
145  // compute the maximum coverage of individual source-code lines
146  coverage_lines_mapt coverage_lines_map;
147  compute_coverage_lines(gf_it->second.body, coverage, coverage_lines_map);
148 
149  // <method name="foo" signature="int(int)" line-rate="1.0" branch-rate="1.0">
150  // <lines>
151  // <line number="23" hits="1" branch="false"/>
152  // <line number="24" hits="1" branch="false"/>
153  // <line number="25" hits="1" branch="false"/>
154  // <line number="26" hits="1" branch="false"/>
155  // <line number="27" hits="1" branch="false"/>
156  // <line number="28" hits="1" branch="false"/>
157  // <line number="29" hits="1" branch="false"/>
158  // <line number="30" hits="1" branch="false"/>
159  // </lines>
160  // </method>
161  xml.set_attribute("name", id2string(gf_it->first));
162 
164  "signature", from_type(ns, gf_it->first, gf_it->second.type));
165 
168 
169  xmlt &lines = xml.new_element("lines");
170 
171  for(const auto &cov_line : coverage_lines_map)
172  {
173  xmlt &line = lines.new_element("line");
174 
175  line.set_attribute("number", std::to_string(cov_line.first));
176  line.set_attribute("hits", std::to_string(cov_line.second.hits));
177  if(cov_line.second.conditions.empty())
178  line.set_attribute("branch", "false");
179  else
180  {
181  line.set_attribute("branch", "true");
182 
183  xmlt &conditions = line.new_element("conditions");
184 
185  std::size_t number = 0, total_taken = 0;
186  for(const auto &c : cov_line.second.conditions)
187  {
188  // <condition number="0" type="jump" coverage="50%"/>
189  xmlt &condition = conditions.new_element("condition");
190  condition.set_attribute("number", std::to_string(number++));
191  condition.set_attribute("type", "jump");
192  unsigned taken = c.second.false_taken + c.second.true_taken;
193  total_taken += taken;
194  condition.set_attribute("coverage", rate(taken, 2, true));
195  }
196 
197  line.set_attribute(
198  "condition-coverage", rate_detailed(total_taken, number * 2, true));
199  }
200  }
201 }
202 
204  const goto_programt &goto_program,
205  const symex_coveraget::coveraget &coverage,
206  coverage_lines_mapt &dest)
207 {
208  forall_goto_program_instructions(it, goto_program)
209  {
210  if(
211  it->source_location.is_nil() ||
212  it->source_location.get_file() != file_name || it->is_dead() ||
213  it->is_end_function())
214  continue;
215 
216  const bool is_branch = it->is_goto() && !it->guard.is_constant();
217 
218  unsigned l =
219  safe_string2unsigned(id2string(it->source_location.get_line()));
220  std::pair<coverage_lines_mapt::iterator, bool> entry =
221  dest.insert(std::make_pair(l, coverage_linet()));
222 
223  if(entry.second)
224  ++lines_total;
225 
226  // mark as branch if any instruction in this source code line is
227  // a branching instruction
228  if(is_branch)
229  {
230  branches_total += 2;
231  if(!entry.first->second.conditions.insert({it, coverage_conditiont()})
232  .second)
233  UNREACHABLE;
234  }
235 
236  symex_coveraget::coveraget::const_iterator c_entry = coverage.find(it);
237  if(c_entry != coverage.end())
238  {
239  if(!(c_entry->second.size() == 1 || is_branch))
240  {
241  std::cerr << it->location_number << '\n';
242  for(const auto &cov : c_entry->second)
243  std::cerr << cov.second.succ->location_number << '\n';
244  }
246  c_entry->second.size() == 1 || is_branch,
247  "instructions other than branch instructions have exactly 1 successor");
248 
249  for(const auto &cov : c_entry->second)
250  {
252  cov.second.num_executions > 0,
253  "coverage entries can only exist with at least one execution");
254 
255  if(entry.first->second.hits == 0)
256  ++lines_covered;
257 
258  if(cov.second.num_executions > entry.first->second.hits)
259  entry.first->second.hits = cov.second.num_executions;
260 
261  if(is_branch)
262  {
263  auto cond_entry = entry.first->second.conditions.find(it);
264  INVARIANT(
265  cond_entry != entry.first->second.conditions.end(),
266  "branch should have condition");
267 
268  if(it->get_target() == cov.second.succ)
269  {
270  if(!cond_entry->second.false_taken)
271  {
272  cond_entry->second.false_taken = true;
274  }
275  }
276  else
277  {
278  if(!cond_entry->second.true_taken)
279  {
280  cond_entry->second.true_taken = true;
282  }
283  }
284  }
285  }
286  }
287  }
288 }
289 
291  const goto_functionst &goto_functions,
292  coverage_recordt &dest) const
293 {
294  typedef std::map<irep_idt, coverage_recordt> file_recordst;
295  file_recordst file_records;
296 
297  forall_goto_functions(gf_it, goto_functions)
298  {
299  if(
300  !gf_it->second.body_available() ||
301  gf_it->first == goto_functions.entry_point() ||
302  gf_it->first == INITIALIZE_FUNCTION)
303  continue;
304 
305  goto_program_coverage_recordt func_cov(ns, gf_it, coverage);
306 
307  std::pair<file_recordst::iterator, bool> entry = file_records.insert(
308  std::make_pair(func_cov.get_file(), coverage_recordt("class")));
309  coverage_recordt &file_record = entry.first->second;
310 
311  if(entry.second)
312  {
313  file_record.xml.new_element("methods");
314  file_record.xml.new_element("lines");
315  }
316 
317  // copy the "method" node
318  file_record.xml.elements.front().new_element(func_cov.xml);
319 
320  // copy any lines
321  for(xmlt::elementst::const_iterator it =
322  func_cov.xml.elements.front().elements.begin();
323  it != func_cov.xml.elements.front().elements.end();
324  ++it)
325  file_record.xml.elements.back().new_element(*it);
326 
327  // merge line/branch info
328  file_record.lines_covered += func_cov.lines_covered;
329  file_record.lines_total += func_cov.lines_total;
330  file_record.branches_covered += func_cov.branches_covered;
331  file_record.branches_total += func_cov.branches_total;
332  }
333 
334  xmlt &classes = dest.xml.new_element("classes");
335 
336  // <class name="MyProject.GameRules" filename="MyProject/GameRules.java"
337  // line-rate="1.0" branch-rate="1.0" complexity="1.4">
338  for(file_recordst::const_iterator it = file_records.begin();
339  it != file_records.end();
340  ++it)
341  {
343  continue;
344 
345  const coverage_recordt &f_cov = it->second;
346 
347  xmlt &class_xml = classes.new_element(f_cov.xml);
348  class_xml.set_attribute("name", id2string(it->first));
349  class_xml.set_attribute("filename", id2string(it->first));
350  class_xml.set_attribute(
351  "line-rate", rate(f_cov.lines_covered, f_cov.lines_total));
352  class_xml.set_attribute(
353  "branch-rate", rate(f_cov.branches_covered, f_cov.branches_total));
354  class_xml.set_attribute("complexity", "0.0");
355 
356  // merge line/branch info
357  dest.lines_covered += f_cov.lines_covered;
358  dest.lines_total += f_cov.lines_total;
359  dest.branches_covered += f_cov.branches_covered;
360  dest.branches_total += f_cov.branches_total;
361  }
362 }
363 
365  const goto_functionst &goto_functions,
366  xmlt &xml_coverage) const
367 {
368  coverage_recordt overall_cov("package");
369  compute_overall_coverage(goto_functions, overall_cov);
370 
371  std::string overall_line_rate_str =
372  rate(overall_cov.lines_covered, overall_cov.lines_total);
373  std::string overall_branch_rate_str =
374  rate(overall_cov.branches_covered, overall_cov.branches_total);
375 
376  auto now = std::chrono::system_clock::now();
377  auto current_time = std::chrono::time_point_cast<std::chrono::seconds>(now);
378  std::time_t tt = std::chrono::system_clock::to_time_t(current_time);
379 
380  // <coverage line-rate="0.0" branch-rate="0.0" lines-covered="1"
381  // lines-valid="1" branches-covered="1"
382  // branches-valid="1" complexity="0.0"
383  // version="2.1.1" timestamp="0">
384  xml_coverage.set_attribute("line-rate", overall_line_rate_str);
385  xml_coverage.set_attribute("branch-rate", overall_branch_rate_str);
386  xml_coverage.set_attribute(
387  "lines-covered", std::to_string(overall_cov.lines_covered));
388  xml_coverage.set_attribute(
389  "lines-valid", std::to_string(overall_cov.lines_total));
390  xml_coverage.set_attribute(
391  "branches-covered", std::to_string(overall_cov.branches_covered));
392  xml_coverage.set_attribute(
393  "branches-valid", std::to_string(overall_cov.branches_total));
394  xml_coverage.set_attribute("complexity", "0.0");
395  xml_coverage.set_attribute("version", "2.1.1");
396  xml_coverage.set_attribute("timestamp", std::to_string(tt));
397 
398  xmlt &packages = xml_coverage.new_element("packages");
399 
400  // <package name="" line-rate="0.0" branch-rate="0.0" complexity="0.0">
401  xmlt &package = packages.new_element(overall_cov.xml);
402  package.set_attribute("name", "");
403  package.set_attribute("line-rate", overall_line_rate_str);
404  package.set_attribute("branch-rate", overall_branch_rate_str);
405  package.set_attribute("complexity", "0.0");
406 }
407 
409  const goto_functionst &goto_functions,
410  std::ostream &os) const
411 {
412  xmlt xml_coverage("coverage");
413  build_cobertura(goto_functions, xml_coverage);
414 
415  os << "<?xml version=\"1.0\"?>\n";
416  os << "<!DOCTYPE coverage SYSTEM \""
417  << "http://cobertura.sourceforge.net/xml/coverage-04.dtd\">\n";
418  os << xml_coverage;
419 
420  return !os.good();
421 }
422 
424  const goto_functionst &goto_functions,
425  const std::string &path) const
426 {
427  PRECONDITION(!path.empty());
428 
429  if(path == "-")
430  return output_report(goto_functions, std::cout);
431  else
432  {
433  std::ofstream out(path.c_str());
434  return output_report(goto_functions, out);
435  }
436 }
coverage_recordt::branches_covered
std::size_t branches_covered
Definition: symex_coverage.cpp:46
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
symex_coveraget::compute_overall_coverage
void compute_overall_coverage(const goto_functionst &goto_functions, coverage_recordt &dest) const
Definition: symex_coverage.cpp:290
xmlt::elements
elementst elements
Definition: xml.h:42
goto_program_coverage_recordt::coverage_linet
Definition: symex_coverage.cpp:77
rate
static std::string rate(std::size_t covered, std::size_t total, bool per_cent=false)
Definition: symex_coverage.cpp:95
coverage_recordt::coverage_recordt
coverage_recordt(const std::string &node_id)
Definition: symex_coverage.cpp:34
goto_program_coverage_recordt::coverage_conditiont::coverage_conditiont
coverage_conditiont()
Definition: symex_coverage.cpp:68
symex_coveraget::coveraget
std::map< goto_programt::const_targett, coverage_innert > coveraget
Definition: symex_coverage.h:69
goto_program_coverage_recordt::get_file
const irep_idt & get_file() const
Definition: symex_coverage.cpp:58
from_type
std::string from_type(const namespacet &ns, const irep_idt &identifier, const typet &type)
Definition: language_util.cpp:33
source_locationt::is_built_in
bool is_built_in() const
Definition: source_location.h:179
to_string
std::string to_string(const string_not_contains_constraintt &expr)
Used for debug printing.
Definition: string_constraint.cpp:55
symex_coveraget::build_cobertura
void build_cobertura(const goto_functionst &goto_functions, xmlt &xml_coverage) const
Definition: symex_coverage.cpp:364
xml.h
symex_coveraget::coverage
coveraget coverage
Definition: symex_coverage.h:70
goto_program_coverage_recordt::compute_coverage_lines
void compute_coverage_lines(const goto_programt &goto_program, const symex_coveraget::coveraget &coverage, coverage_lines_mapt &dest)
Definition: symex_coverage.cpp:203
namespacet
A namespacet is essentially one or two symbol tables bound together, to allow for symbol lookups in t...
Definition: namespace.h:92
string2int.h
goto_program_coverage_recordt::coverage_conditiont::false_taken
bool false_taken
Definition: symex_coverage.cpp:72
DATA_INVARIANT
#define DATA_INVARIANT(CONDITION, REASON)
This condition should be used to document that assumptions that are made on goto_functions,...
Definition: invariant.h:511
id2string
const std::string & id2string(const irep_idt &d)
Definition: irep.h:44
symex_coverage.h
Record and print code coverage of symbolic execution.
language_util.h
PRECONDITION
#define PRECONDITION(CONDITION)
Definition: invariant.h:464
symex_coveraget::output_report
bool output_report(const goto_functionst &goto_functions, std::ostream &os) const
Definition: symex_coverage.cpp:408
symex_coveraget::generate_report
bool generate_report(const goto_functionst &goto_functions, const std::string &path) const
Definition: symex_coverage.cpp:423
INITIALIZE_FUNCTION
#define INITIALIZE_FUNCTION
Definition: static_lifetime_init.h:23
goto_program_coverage_recordt::coverage_lines_mapt
std::map< unsigned, coverage_linet > coverage_lines_mapt
Definition: symex_coverage.cpp:86
coverage_recordt::lines_total
std::size_t lines_total
Definition: symex_coverage.cpp:45
dstringt::empty
bool empty() const
Definition: dstring.h:88
goto_program_coverage_recordt::coverage_conditiont
Definition: symex_coverage.cpp:67
xmlt
Definition: xml.h:21
safe_string2unsigned
unsigned safe_string2unsigned(const std::string &str, int base)
Definition: string2int.cpp:19
remove_returns.h
Replace function returns by assignments to global variables.
coverage_recordt::branches_total
std::size_t branches_total
Definition: symex_coverage.cpp:47
goto_functionst
A collection of goto functions.
Definition: goto_functions.h:23
goto_program_coverage_recordt::coverage_linet::conditions
std::map< goto_programt::const_targett, coverage_conditiont > conditions
Definition: symex_coverage.cpp:83
symex_coveraget::ns
const namespacet & ns
Definition: symex_coverage.h:50
xmlt::set_attribute
void set_attribute(const std::string &attribute, unsigned value)
Definition: xml.cpp:175
goto_program_coverage_recordt::coverage_linet::hits
unsigned hits
Definition: symex_coverage.cpp:82
coverage_recordt::lines_covered
std::size_t lines_covered
Definition: symex_coverage.cpp:44
goto_functions.h
Goto Programs with Functions.
goto_programt
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:73
coverage_recordt::xml
xmlt xml
Definition: symex_coverage.cpp:43
forall_goto_functions
#define forall_goto_functions(it, functions)
Definition: goto_functions.h:122
goto_programt::const_targett
instructionst::const_iterator const_targett
Definition: goto_program.h:580
goto_program_coverage_recordt::goto_program_coverage_recordt
goto_program_coverage_recordt(const namespacet &ns, goto_functionst::function_mapt::const_iterator gf_it, const symex_coveraget::coveraget &coverage)
Definition: symex_coverage.cpp:127
goto_functionst::entry_point
static irep_idt entry_point()
Get the identifier of the entry point to a goto model.
Definition: goto_functions.h:90
goto_program_coverage_recordt::file_name
irep_idt file_name
Definition: symex_coverage.cpp:64
rate_detailed
static std::string rate_detailed(std::size_t covered, std::size_t total, bool per_cent=false)
Definition: symex_coverage.cpp:119
static_lifetime_init.h
coverage_recordt
Definition: symex_coverage.cpp:32
goto_program_coverage_recordt
Definition: symex_coverage.cpp:51
goto_program_coverage_recordt::coverage_conditiont::true_taken
bool true_taken
Definition: symex_coverage.cpp:73
goto_program_coverage_recordt::coverage_linet::coverage_linet
coverage_linet()
Definition: symex_coverage.cpp:78
forall_goto_program_instructions
#define forall_goto_program_instructions(it, program)
Definition: goto_program.h:1196
validation_modet::INVARIANT
@ INVARIANT
xmlt::new_element
xmlt & new_element(const std::string &key)
Definition: xml.h:95