in src/common/dwarf_cu_to_module.cc [970:1162]
void DwarfCUToModule::AssignLinesToFunctions() {
vector<Module::Function *> *functions = &cu_context_->functions;
WarningReporter *reporter = cu_context_->reporter;
// This would be simpler if we assumed that source line entries
// don't cross function boundaries. However, there's no real reason
// to assume that (say) a series of function definitions on the same
// line wouldn't get coalesced into one line number entry. The
// DWARF spec certainly makes no such promises.
//
// So treat the functions and lines as peers, and take the trouble
// to compute their ranges' intersections precisely. In any case,
// the hair here is a constant factor for performance; the
// complexity from here on out is linear.
// Put both our functions and lines in order by address.
std::sort(functions->begin(), functions->end(),
Module::Function::CompareByAddress);
std::sort(lines_.begin(), lines_.end(), Module::Line::CompareByAddress);
// The last line that we used any piece of. We use this only for
// generating warnings.
const Module::Line *last_line_used = NULL;
// The last function and line we warned about --- so we can avoid
// doing so more than once.
const Module::Function *last_function_cited = NULL;
const Module::Line *last_line_cited = NULL;
// Prepare a sorted list of ranges with range-to-function mapping
vector<FunctionRange> sorted_ranges;
FillSortedFunctionRanges(sorted_ranges, functions);
// Make a single pass through both the range and line vectors from lower to
// higher addresses, populating each range's function lines vector with lines
// from our lines_ vector that fall within the range.
vector<FunctionRange>::iterator range_it = sorted_ranges.begin();
vector<Module::Line>::const_iterator line_it = lines_.begin();
Module::Address current;
// Pointers to the referents of func_it and line_it, or NULL if the
// iterator is at the end of the sequence.
FunctionRange *range;
const Module::Line *line;
// Start current at the beginning of the first line or function,
// whichever is earlier.
if (range_it != sorted_ranges.end() && line_it != lines_.end()) {
range = &*range_it;
line = &*line_it;
current = std::min(range->address, line->address);
} else if (line_it != lines_.end()) {
range = NULL;
line = &*line_it;
current = line->address;
} else if (range_it != sorted_ranges.end()) {
range = &*range_it;
line = NULL;
current = range->address;
} else {
return;
}
while (range || line) {
// This loop has two invariants that hold at the top.
//
// First, at least one of the iterators is not at the end of its
// sequence, and those that are not refer to the earliest
// range or line that contains or starts after CURRENT.
//
// Note that every byte is in one of four states: it is covered
// or not covered by a range, and, independently, it is
// covered or not covered by a line.
//
// The second invariant is that CURRENT refers to a byte whose
// state is different from its predecessor, or it refers to the
// first byte in the address space. In other words, CURRENT is
// always the address of a transition.
//
// Note that, although each iteration advances CURRENT from one
// transition address to the next in each iteration, it might
// not advance the iterators. Suppose we have a range that
// starts with a line, has a gap, and then a second line, and
// suppose that we enter an iteration with CURRENT at the end of
// the first line. The next transition address is the start of
// the second line, after the gap, so the iteration should
// advance CURRENT to that point. At the head of that iteration,
// the invariants require that the line iterator be pointing at
// the second line. But this is also true at the head of the
// next. And clearly, the iteration must not change the range
// iterator. So neither iterator moves.
// Assert the first invariant (see above).
assert(!range || current < range->address || within(*range, current));
assert(!line || current < line->address || within(*line, current));
// The next transition after CURRENT.
Module::Address next_transition;
// Figure out which state we're in, add lines or warn, and compute
// the next transition address.
if (range && current >= range->address) {
if (line && current >= line->address) {
// Covered by both a line and a range.
Module::Address range_left = range->size - (current - range->address);
Module::Address line_left = line->size - (current - line->address);
// This may overflow, but things work out.
next_transition = current + std::min(range_left, line_left);
Module::Line l = *line;
l.address = current;
l.size = next_transition - current;
range->AddLine(l);
last_line_used = line;
} else {
// Covered by a range, but no line.
if (range->function != last_function_cited) {
reporter->UncoveredFunction(*(range->function));
last_function_cited = range->function;
}
if (line && within(*range, line->address))
next_transition = line->address;
else
// If this overflows, we'll catch it below.
next_transition = range->address + range->size;
}
} else {
if (line && current >= line->address) {
// Covered by a line, but no range.
//
// If GCC emits padding after one function to align the start
// of the next, then it will attribute the padding
// instructions to the last source line of function (to reduce
// the size of the line number info), but omit it from the
// DW_AT_{low,high}_pc range given in .debug_info (since it
// costs nothing to be precise there). If we did use at least
// some of the line we're about to skip, and it ends at the
// start of the next function, then assume this is what
// happened, and don't warn.
if (line != last_line_cited
&& !(range
&& line == last_line_used
&& range->address - line->address == line->size)) {
reporter->UncoveredLine(*line);
last_line_cited = line;
}
if (range && within(*line, range->address))
next_transition = range->address;
else
// If this overflows, we'll catch it below.
next_transition = line->address + line->size;
} else {
// Covered by neither a range nor a line. By the invariant,
// both range and line begin after CURRENT. The next transition
// is the start of the next range or next line, whichever
// is earliest.
assert(range || line);
if (range && line)
next_transition = std::min(range->address, line->address);
else if (range)
next_transition = range->address;
else
next_transition = line->address;
}
}
// If a function or line abuts the end of the address space, then
// next_transition may end up being zero, in which case we've completed
// our pass. Handle that here, instead of trying to deal with it in
// each place we compute next_transition.
if (!next_transition)
break;
// Advance iterators as needed. If lines overlap or functions overlap,
// then we could go around more than once. We don't worry too much
// about what result we produce in that case, just as long as we don't
// hang or crash.
while (range_it != sorted_ranges.end()
&& next_transition >= range_it->address
&& !within(*range_it, next_transition))
range_it++;
range = (range_it != sorted_ranges.end()) ? &(*range_it) : NULL;
while (line_it != lines_.end()
&& next_transition >= line_it->address
&& !within(*line_it, next_transition))
line_it++;
line = (line_it != lines_.end()) ? &*line_it : NULL;
// We must make progress.
assert(next_transition > current);
current = next_transition;
}
}