cprover
cover_basic_blocks.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Coverage Instrumentation
4 
5 Author: Peter Schrammel
6 
7 \*******************************************************************/
8 
11 
12 #include "cover_basic_blocks.h"
13 
15 #include <util/message.h>
16 #include <util/string2int.h>
17 
19  const goto_programt::const_targett &instruction,
21 {
22  if(instruction->incoming_edges.size() != 1)
23  return {};
24 
25  const goto_programt::targett in_t = *instruction->incoming_edges.cbegin();
26  if(in_t->is_goto() && !in_t->is_backwards_goto() && in_t->guard.is_true())
27  return block_map[in_t];
28 
29  return {};
30 }
31 
33 {
34  bool next_is_target = true;
35  std::size_t current_block = 0;
36 
37  forall_goto_program_instructions(it, goto_program)
38  {
39  // Is it a potential beginning of a block?
40  if(next_is_target || it->is_target())
41  {
42  if(auto block_number = continuation_of_block(it, block_map))
43  {
44  current_block = *block_number;
45  }
46  else
47  {
48  block_infos.emplace_back();
49  block_infos.back().representative_inst = it;
50  block_infos.back().source_location = source_locationt::nil();
51  current_block = block_infos.size() - 1;
52  }
53  }
54 
55  INVARIANT(
56  current_block < block_infos.size(), "current block number out of range");
57  block_infot &block_info = block_infos.at(current_block);
58 
59  block_map[it] = current_block;
60 
61  add_block_lines(block_info, *it);
62 
63  // set representative program location to instrument
64  if(
65  !it->source_location.is_nil() &&
66  !it->source_location.get_file().empty() &&
67  !it->source_location.get_line().empty() &&
68  block_info.source_location.is_nil())
69  {
70  block_info.representative_inst = it; // update
71  block_info.source_location = it->source_location;
72  }
73 
74  next_is_target =
75 #if 0
76  // Disabled for being too messy
77  it->is_goto() || it->is_function_call() || it->is_assume();
78 #else
79  it->is_goto() || it->is_function_call();
80 #endif
81  }
82 
83  for(auto &block_info : block_infos)
84  {
85  update_covered_lines(block_info);
86  update_source_lines(block_info);
87  }
88 }
89 
91 {
92  const auto it = block_map.find(t);
93  INVARIANT(it != block_map.end(), "instruction must be part of a block");
94  return it->second;
95 }
96 
98 cover_basic_blockst::instruction_of(const std::size_t block_nr) const
99 {
100  INVARIANT(block_nr < block_infos.size(), "block number out of range");
101  return block_infos[block_nr].representative_inst;
102 }
103 
104 const source_locationt &
105 cover_basic_blockst::source_location_of(const std::size_t block_nr) const
106 {
107  INVARIANT(block_nr < block_infos.size(), "block number out of range");
108  return block_infos[block_nr].source_location;
109 }
110 
112  const irep_idt &function_id,
113  const goto_programt &goto_program,
114  message_handlert &message_handler)
115 {
116  messaget msg(message_handler);
117  std::set<std::size_t> blocks_seen;
118  forall_goto_program_instructions(it, goto_program)
119  {
120  const std::size_t block_nr = block_of(it);
121  const block_infot &block_info = block_infos.at(block_nr);
122 
123  if(
124  blocks_seen.insert(block_nr).second &&
125  block_info.representative_inst == goto_program.instructions.end())
126  {
127  msg.warning() << "Ignoring block " << (block_nr + 1) << " location "
128  << it->location_number << " " << it->source_location
129  << " (bytecode-index already instrumented)"
130  << messaget::eom;
131  }
132  else if(
133  block_info.representative_inst == it &&
134  block_info.source_location.is_nil())
135  {
136  msg.warning() << "Ignoring block " << (block_nr + 1) << " location "
137  << it->location_number << " " << function_id
138  << " (missing source location)" << messaget::eom;
139  }
140  // The location numbers printed here are those
141  // before the coverage instrumentation.
142  }
143 }
144 
145 void cover_basic_blockst::output(std::ostream &out) const
146 {
147  for(const auto &block_pair : block_map)
148  out << block_pair.first->source_location << " -> " << block_pair.second
149  << '\n';
150 }
151 
154  const goto_programt::instructiont &instruction)
155 {
156  const auto &add_location = [&](const source_locationt &location) {
157  const irep_idt &line = location.get_line();
158  if(!line.empty())
159  {
160  block.lines.insert(unsafe_string2unsigned(id2string(line)));
161  block.source_lines.insert(location);
162  }
163  };
164  add_location(instruction.source_location);
165  instruction.get_code().visit_pre(
166  [&](const exprt &expr) { add_location(expr.source_location()); });
167 }
168 
170 {
171  if(block_info.source_location.is_nil())
172  return;
173 
174  const auto &cover_set = block_info.lines;
175  INVARIANT(!cover_set.empty(), "covered lines set must not be empty");
176  std::vector<unsigned> line_list(cover_set.begin(), cover_set.end());
177 
178  std::string covered_lines = format_number_range(line_list);
179  block_info.source_location.set_basic_block_covered_lines(covered_lines);
180 }
181 
183 {
184  if(block_info.source_location.is_nil())
185  return;
186 
187  const auto &source_lines = block_info.source_lines;
188  std::string str = source_lines.to_string();
189  INVARIANT(!str.empty(), "source lines set must not be empty");
191 }
192 
194  const goto_programt &_goto_program)
195 {
196  std::set<std::size_t> source_lines_requiring_update;
197 
198  forall_goto_program_instructions(it, _goto_program)
199  {
200  const auto &location = it->source_location;
201  const auto &bytecode_index = location.get_java_bytecode_index();
202  auto entry = index_to_block.emplace(bytecode_index, block_infos.size());
203  if(entry.second)
204  {
205  block_infos.push_back(it);
206  block_locations.push_back(location);
207  block_locations.back().set_basic_block_covered_lines(location.get_line());
208  block_source_lines.emplace_back(location);
209  source_lines_requiring_update.insert(entry.first->second);
210  }
211  else
212  {
213  block_source_lines[entry.first->second].insert(location);
214  source_lines_requiring_update.insert(entry.first->second);
215  }
216  }
217 
218  for(std::size_t i : source_lines_requiring_update)
219  {
220  block_locations.at(i).set_basic_block_source_lines(
221  block_source_lines.at(i).to_string());
222  }
223 }
224 
225 std::size_t
227 {
228  const auto &bytecode_index = t->source_location.get_java_bytecode_index();
229  const auto it = index_to_block.find(bytecode_index);
230  INVARIANT(it != index_to_block.end(), "instruction must be part of a block");
231  return it->second;
232 }
233 
235 cover_basic_blocks_javat::instruction_of(const std::size_t block_nr) const
236 {
237  PRECONDITION(block_nr < block_infos.size());
238  return block_infos[block_nr];
239 }
240 
241 const source_locationt &
242 cover_basic_blocks_javat::source_location_of(const std::size_t block_nr) const
243 {
244  PRECONDITION(block_nr < block_locations.size());
245  return block_locations[block_nr];
246 }
247 
248 void cover_basic_blocks_javat::output(std::ostream &out) const
249 {
250  for(std::size_t i = 0; i < block_locations.size(); ++i)
251  out << block_locations[i] << " -> " << i << '\n';
252 }
messaget
Class that provides messages with a built-in verbosity 'level'.
Definition: message.h:155
cover_basic_blockst::instruction_of
optionalt< goto_programt::const_targett > instruction_of(std::size_t block_nr) const override
Definition: cover_basic_blocks.cpp:98
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
cover_basic_blocks_javat::index_to_block
std::unordered_map< irep_idt, std::size_t > index_to_block
Definition: cover_basic_blocks.h:152
goto_programt::instructiont::source_location
source_locationt source_location
The location of the instruction in the source file.
Definition: goto_program.h:431
cover_basic_blockst::add_block_lines
static void add_block_lines(cover_basic_blockst::block_infot &block, const goto_programt::instructiont &instruction)
Adds the lines which instruction spans to block.
Definition: cover_basic_blocks.cpp:152
cover_basic_blocks_javat::cover_basic_blocks_javat
cover_basic_blocks_javat(const goto_programt &_goto_program)
Definition: cover_basic_blocks.cpp:193
source_locationt::nil
static const source_locationt & nil()
Definition: source_location.h:187
cover_basic_blockst::block_infot::source_location
source_locationt source_location
the source location representative for this block (we need a separate copy of source locations becaus...
Definition: cover_basic_blocks.h:110
cover_basic_blocks_javat::block_source_lines
std::vector< source_linest > block_source_lines
Definition: cover_basic_blocks.h:154
exprt
Base class for all expressions.
Definition: expr.h:54
source_locationt::set_basic_block_source_lines
void set_basic_block_source_lines(const irep_idt &source_lines)
Definition: source_location.h:161
cover_basic_blockst::report_block_anomalies
void report_block_anomalies(const irep_idt &function_id, const goto_programt &goto_program, message_handlert &message_handler) override
Output warnings about ignored blocks.
Definition: cover_basic_blocks.cpp:111
messaget::eom
static eomt eom
Definition: message.h:297
source_linest::to_string
std::string to_string() const
Construct a string representing the set of lines.
Definition: source_lines.cpp:38
cover_basic_blockst::block_infot::source_lines
source_linest source_lines
the set of source code lines belonging to this block
Definition: cover_basic_blocks.h:116
cover_basic_blockst::block_of
std::size_t block_of(goto_programt::const_targett t) const override
Definition: cover_basic_blocks.cpp:90
source_linest::insert
void insert(const source_locationt &loc)
Insert a line (a source location) into the set of lines.
Definition: source_lines.cpp:22
goto_programt::instructiont::get_code
const codet & get_code() const
Get the code represented by this instruction.
Definition: goto_program.h:185
string2int.h
cover_basic_blockst::block_map
block_mapt block_map
map program locations to block numbers
Definition: cover_basic_blocks.h:120
id2string
const std::string & id2string(const irep_idt &d)
Definition: irep.h:49
messaget::mstreamt::source_location
source_locationt source_location
Definition: message.h:247
cover_basic_blockst::continuation_of_block
static optionalt< std::size_t > continuation_of_block(const goto_programt::const_targett &instruction, block_mapt &block_map)
If this block is a continuation of a previous block through unconditional forward gotos,...
Definition: cover_basic_blocks.cpp:18
cover_basic_blockst::block_infos
std::vector< block_infot > block_infos
map block numbers to block information
Definition: cover_basic_blocks.h:122
PRECONDITION
#define PRECONDITION(CONDITION)
Definition: invariant.h:463
cover_basic_blockst::source_location_of
const source_locationt & source_location_of(std::size_t block_nr) const override
Definition: cover_basic_blocks.cpp:105
cover_basic_blocks_javat::block_of
std::size_t block_of(goto_programt::const_targett t) const override
Definition: cover_basic_blocks.cpp:226
cover_basic_blockst::update_source_lines
static void update_source_lines(block_infot &block_info)
create a string representing source lines and set as a property of source location of basic block
Definition: cover_basic_blocks.cpp:182
cover_basic_blocks_javat::block_locations
std::vector< source_locationt > block_locations
Definition: cover_basic_blocks.h:150
irept::is_nil
bool is_nil() const
Definition: irep.h:387
message_handlert
Definition: message.h:28
dstringt::empty
bool empty() const
Definition: dstring.h:88
format_number_range
std::string format_number_range(const std::vector< unsigned > &input_numbers)
create shorter representation for output
Definition: format_number_range.cpp:25
cover_basic_blocks_javat::block_infos
std::vector< goto_programt::const_targett > block_infos
Definition: cover_basic_blocks.h:148
optionalt
nonstd::optional< T > optionalt
Definition: optional.h:35
source_locationt
Definition: source_location.h:19
goto_programt::instructions
instructionst instructions
The list of instructions in the goto program.
Definition: goto_program.h:652
cover_basic_blocks_javat::source_location_of
const source_locationt & source_location_of(std::size_t block_number) const override
Definition: cover_basic_blocks.cpp:242
cover_basic_blocks_javat::instruction_of
optionalt< goto_programt::const_targett > instruction_of(std::size_t block_number) const override
Definition: cover_basic_blocks.cpp:235
cover_basic_blockst::block_mapt
std::map< goto_programt::const_targett, std::size_t > block_mapt
Definition: cover_basic_blocks.h:100
cover_basic_blockst::block_infot::lines
std::unordered_set< std::size_t > lines
the set of lines belonging to this block
Definition: cover_basic_blocks.h:113
cover_basic_blocks_javat::output
void output(std::ostream &out) const override
Outputs the list of blocks.
Definition: cover_basic_blocks.cpp:248
unsafe_string2unsigned
unsigned unsafe_string2unsigned(const std::string &str, int base)
Definition: string2int.cpp:35
cover_basic_blockst::output
void output(std::ostream &out) const override
Outputs the list of blocks.
Definition: cover_basic_blocks.cpp:145
exprt::visit_pre
void visit_pre(std::function< void(exprt &)>)
Definition: expr.cpp:245
cover_basic_blocks.h
Basic blocks detection for Coverage Instrumentation.
goto_programt
A generic container class for the GOTO intermediate representation of one function.
Definition: goto_program.h:71
goto_programt::const_targett
instructionst::const_iterator const_targett
Definition: goto_program.h:647
INVARIANT
#define INVARIANT(CONDITION, REASON)
This macro uses the wrapper function 'invariant_violated_string'.
Definition: invariant.h:423
source_locationt::set_basic_block_covered_lines
void set_basic_block_covered_lines(const irep_idt &covered_lines)
Definition: source_location.h:156
message.h
messaget::warning
mstreamt & warning() const
Definition: message.h:404
goto_programt::instructiont
This class represents an instruction in the GOTO intermediate representation.
Definition: goto_program.h:178
exprt::source_location
const source_locationt & source_location() const
Definition: expr.h:230
format_number_range.h
Format vector of numbers into a compressed range.
cover_basic_blockst::update_covered_lines
static void update_covered_lines(block_infot &block_info)
create list of covered lines as CSV string and set as property of source location of basic block,...
Definition: cover_basic_blocks.cpp:169
cover_basic_blockst::block_infot::representative_inst
optionalt< goto_programt::const_targett > representative_inst
the program location to instrument for this block
Definition: cover_basic_blocks.h:105
cover_basic_blockst::block_infot
Definition: cover_basic_blocks.h:103
goto_programt::targett
instructionst::iterator targett
Definition: goto_program.h:646
forall_goto_program_instructions
#define forall_goto_program_instructions(it, program)
Definition: goto_program.h:1255
cover_basic_blockst::cover_basic_blockst
cover_basic_blockst(const goto_programt &goto_program)
Definition: cover_basic_blocks.cpp:32