1//===-- LineTable.cpp -----------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "lldb/Symbol/LineTable.h"
10#include "lldb/Core/Address.h"
11#include "lldb/Core/Module.h"
12#include "lldb/Core/Section.h"
13#include "lldb/Symbol/CompileUnit.h"
14#include "lldb/Utility/Stream.h"
15#include <algorithm>
16
17using namespace lldb;
18using namespace lldb_private;
19
20// LineTable constructor
21LineTable::LineTable(CompileUnit *comp_unit)
22 : m_comp_unit(comp_unit), m_entries() {}
23
24LineTable::LineTable(CompileUnit *comp_unit,
25 std::vector<std::unique_ptr<LineSequence>> &&sequences)
26 : m_comp_unit(comp_unit), m_entries() {
27 LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
28 llvm::stable_sort(Range&: sequences, C: less_than_bp);
29 for (const auto &sequence : sequences) {
30 LineSequenceImpl *seq = static_cast<LineSequenceImpl *>(sequence.get());
31 m_entries.insert(position: m_entries.end(), first: seq->m_entries.begin(),
32 last: seq->m_entries.end());
33 }
34}
35
36// Destructor
37LineTable::~LineTable() = default;
38
39void LineTable::InsertLineEntry(lldb::addr_t file_addr, uint32_t line,
40 uint16_t column, uint16_t file_idx,
41 bool is_start_of_statement,
42 bool is_start_of_basic_block,
43 bool is_prologue_end, bool is_epilogue_begin,
44 bool is_terminal_entry) {
45 Entry entry(file_addr, line, column, file_idx, is_start_of_statement,
46 is_start_of_basic_block, is_prologue_end, is_epilogue_begin,
47 is_terminal_entry);
48
49 LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
50 entry_collection::iterator pos =
51 llvm::upper_bound(Range&: m_entries, Value&: entry, C: less_than_bp);
52
53 // Stream s(stdout);
54 // s << "\n\nBefore:\n";
55 // Dump (&s, Address::DumpStyleFileAddress);
56 m_entries.insert(position: pos, x: entry);
57 // s << "After:\n";
58 // Dump (&s, Address::DumpStyleFileAddress);
59}
60
61LineSequence::LineSequence() = default;
62
63void LineTable::LineSequenceImpl::Clear() { m_entries.clear(); }
64
65std::unique_ptr<LineSequence> LineTable::CreateLineSequenceContainer() {
66 return std::make_unique<LineTable::LineSequenceImpl>();
67}
68
69void LineTable::AppendLineEntryToSequence(
70 LineSequence *sequence, lldb::addr_t file_addr, uint32_t line,
71 uint16_t column, uint16_t file_idx, bool is_start_of_statement,
72 bool is_start_of_basic_block, bool is_prologue_end, bool is_epilogue_begin,
73 bool is_terminal_entry) {
74 assert(sequence != nullptr);
75 LineSequenceImpl *seq = reinterpret_cast<LineSequenceImpl *>(sequence);
76 Entry entry(file_addr, line, column, file_idx, is_start_of_statement,
77 is_start_of_basic_block, is_prologue_end, is_epilogue_begin,
78 is_terminal_entry);
79 entry_collection &entries = seq->m_entries;
80 // Replace the last entry if the address is the same, otherwise append it. If
81 // we have multiple line entries at the same address, this indicates illegal
82 // DWARF so this "fixes" the line table to be correct. If not fixed this can
83 // cause a line entry's address that when resolved back to a symbol context,
84 // could resolve to a different line entry. We really want a
85 // 1 to 1 mapping
86 // here to avoid these kinds of inconsistencies. We will need tor revisit
87 // this if the DWARF line tables are updated to allow multiple entries at the
88 // same address legally.
89 if (!entries.empty() && entries.back().file_addr == file_addr) {
90 // GCC don't use the is_prologue_end flag to mark the first instruction
91 // after the prologue.
92 // Instead of it is issuing a line table entry for the first instruction
93 // of the prologue and one for the first instruction after the prologue. If
94 // the size of the prologue is 0 instruction then the 2 line entry will
95 // have the same file address. Removing it will remove our ability to
96 // properly detect the location of the end of prologe so we set the
97 // prologue_end flag to preserve this information (setting the prologue_end
98 // flag for an entry what is after the prologue end don't have any effect)
99 entry.is_prologue_end = entry.file_idx == entries.back().file_idx;
100 entries.back() = entry;
101 } else
102 entries.push_back(x: entry);
103}
104
105void LineTable::InsertSequence(LineSequence *sequence) {
106 assert(sequence != nullptr);
107 LineSequenceImpl *seq = reinterpret_cast<LineSequenceImpl *>(sequence);
108 if (seq->m_entries.empty())
109 return;
110 Entry &entry = seq->m_entries.front();
111
112 // If the first entry address in this sequence is greater than or equal to
113 // the address of the last item in our entry collection, just append.
114 if (m_entries.empty() ||
115 !Entry::EntryAddressLessThan(lhs: entry, rhs: m_entries.back())) {
116 m_entries.insert(position: m_entries.end(), first: seq->m_entries.begin(),
117 last: seq->m_entries.end());
118 return;
119 }
120
121 // Otherwise, find where this belongs in the collection
122 entry_collection::iterator begin_pos = m_entries.begin();
123 entry_collection::iterator end_pos = m_entries.end();
124 LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
125 entry_collection::iterator pos =
126 upper_bound(first: begin_pos, last: end_pos, val: entry, comp: less_than_bp);
127
128 // We should never insert a sequence in the middle of another sequence
129 if (pos != begin_pos) {
130 while (pos < end_pos && !((pos - 1)->is_terminal_entry))
131 pos++;
132 }
133
134#ifndef NDEBUG
135 // If we aren't inserting at the beginning, the previous entry should
136 // terminate a sequence.
137 if (pos != begin_pos) {
138 entry_collection::iterator prev_pos = pos - 1;
139 assert(prev_pos->is_terminal_entry);
140 }
141#endif
142 m_entries.insert(position: pos, first: seq->m_entries.begin(), last: seq->m_entries.end());
143}
144
145LineTable::Entry::LessThanBinaryPredicate::LessThanBinaryPredicate(
146 LineTable *line_table)
147 : m_line_table(line_table) {}
148
149bool LineTable::Entry::LessThanBinaryPredicate::
150operator()(const LineTable::Entry &a, const LineTable::Entry &b) const {
151#define LT_COMPARE(a, b) \
152 if (a != b) \
153 return a < b
154 LT_COMPARE(a.file_addr, b.file_addr);
155 // b and a reversed on purpose below.
156 LT_COMPARE(b.is_terminal_entry, a.is_terminal_entry);
157 LT_COMPARE(a.line, b.line);
158 LT_COMPARE(a.column, b.column);
159 LT_COMPARE(a.is_start_of_statement, b.is_start_of_statement);
160 LT_COMPARE(a.is_start_of_basic_block, b.is_start_of_basic_block);
161 // b and a reversed on purpose below.
162 LT_COMPARE(b.is_prologue_end, a.is_prologue_end);
163 LT_COMPARE(a.is_epilogue_begin, b.is_epilogue_begin);
164 LT_COMPARE(a.file_idx, b.file_idx);
165 return false;
166#undef LT_COMPARE
167}
168
169bool LineTable::Entry::LessThanBinaryPredicate::
170operator()(const std::unique_ptr<LineSequence> &sequence_a,
171 const std::unique_ptr<LineSequence> &sequence_b) const {
172 auto *seq_a = static_cast<const LineSequenceImpl *>(sequence_a.get());
173 auto *seq_b = static_cast<const LineSequenceImpl *>(sequence_b.get());
174 return (*this)(seq_a->m_entries.front(), seq_b->m_entries.front());
175}
176
177uint32_t LineTable::GetSize() const { return m_entries.size(); }
178
179bool LineTable::GetLineEntryAtIndex(uint32_t idx, LineEntry &line_entry) {
180 if (idx < m_entries.size()) {
181 ConvertEntryAtIndexToLineEntry(idx, line_entry);
182 return true;
183 }
184 line_entry.Clear();
185 return false;
186}
187
188bool LineTable::FindLineEntryByAddress(const Address &so_addr,
189 LineEntry &line_entry,
190 uint32_t *index_ptr) {
191 if (index_ptr != nullptr)
192 *index_ptr = UINT32_MAX;
193
194 bool success = false;
195
196 if (so_addr.GetModule().get() == m_comp_unit->GetModule().get()) {
197 Entry search_entry;
198 search_entry.file_addr = so_addr.GetFileAddress();
199 if (search_entry.file_addr != LLDB_INVALID_ADDRESS) {
200 entry_collection::const_iterator begin_pos = m_entries.begin();
201 entry_collection::const_iterator end_pos = m_entries.end();
202 entry_collection::const_iterator pos = lower_bound(
203 first: begin_pos, last: end_pos, val: search_entry, comp: Entry::EntryAddressLessThan);
204 if (pos != end_pos) {
205 if (pos != begin_pos) {
206 if (pos->file_addr != search_entry.file_addr)
207 --pos;
208 else if (pos->file_addr == search_entry.file_addr) {
209 // If this is a termination entry, it shouldn't match since entries
210 // with the "is_terminal_entry" member set to true are termination
211 // entries that define the range for the previous entry.
212 if (pos->is_terminal_entry) {
213 // The matching entry is a terminal entry, so we skip ahead to
214 // the next entry to see if there is another entry following this
215 // one whose section/offset matches.
216 ++pos;
217 if (pos != end_pos) {
218 if (pos->file_addr != search_entry.file_addr)
219 pos = end_pos;
220 }
221 }
222
223 if (pos != end_pos) {
224 // While in the same section/offset backup to find the first line
225 // entry that matches the address in case there are multiple
226 while (pos != begin_pos) {
227 entry_collection::const_iterator prev_pos = pos - 1;
228 if (prev_pos->file_addr == search_entry.file_addr &&
229 prev_pos->is_terminal_entry == false)
230 --pos;
231 else
232 break;
233 }
234 }
235 }
236 }
237 else
238 {
239 // There might be code in the containing objfile before the first
240 // line table entry. Make sure that does not get considered part of
241 // the first line table entry.
242 if (pos->file_addr > so_addr.GetFileAddress())
243 return false;
244 }
245
246 // Make sure we have a valid match and that the match isn't a
247 // terminating entry for a previous line...
248 if (pos != end_pos && pos->is_terminal_entry == false) {
249 uint32_t match_idx = std::distance(first: begin_pos, last: pos);
250 success = ConvertEntryAtIndexToLineEntry(idx: match_idx, line_entry);
251 if (index_ptr != nullptr && success)
252 *index_ptr = match_idx;
253 }
254 }
255 }
256 }
257 return success;
258}
259
260bool LineTable::ConvertEntryAtIndexToLineEntry(uint32_t idx,
261 LineEntry &line_entry) {
262 if (idx >= m_entries.size())
263 return false;
264
265 const Entry &entry = m_entries[idx];
266 ModuleSP module_sp(m_comp_unit->GetModule());
267 if (!module_sp)
268 return false;
269
270 addr_t file_addr = entry.file_addr;
271
272 // A terminal entry can point outside of a module or a section. Decrement the
273 // address to ensure it resolves correctly.
274 if (entry.is_terminal_entry)
275 --file_addr;
276
277 if (!module_sp->ResolveFileAddress(vm_addr: file_addr,
278 so_addr&: line_entry.range.GetBaseAddress()))
279 return false;
280
281 // Now undo the decrement above.
282 if (entry.is_terminal_entry)
283 line_entry.range.GetBaseAddress().Slide(offset: 1);
284
285 if (!entry.is_terminal_entry && idx + 1 < m_entries.size())
286 line_entry.range.SetByteSize(m_entries[idx + 1].file_addr -
287 entry.file_addr);
288 else
289 line_entry.range.SetByteSize(0);
290
291 line_entry.file_sp = std::make_shared<SupportFile>(
292 args: m_comp_unit->GetSupportFiles().GetFileSpecAtIndex(idx: entry.file_idx));
293 line_entry.original_file_sp =
294 m_comp_unit->GetSupportFiles().GetSupportFileAtIndex(idx: entry.file_idx);
295 line_entry.line = entry.line;
296 line_entry.column = entry.column;
297 line_entry.is_start_of_statement = entry.is_start_of_statement;
298 line_entry.is_start_of_basic_block = entry.is_start_of_basic_block;
299 line_entry.is_prologue_end = entry.is_prologue_end;
300 line_entry.is_epilogue_begin = entry.is_epilogue_begin;
301 line_entry.is_terminal_entry = entry.is_terminal_entry;
302 return true;
303}
304
305uint32_t LineTable::FindLineEntryIndexByFileIndex(
306 uint32_t start_idx, uint32_t file_idx,
307 const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) {
308 auto file_idx_matcher = [](uint32_t file_index, uint16_t entry_file_idx) {
309 return file_index == entry_file_idx;
310 };
311 return FindLineEntryIndexByFileIndexImpl<uint32_t>(
312
313 start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher);
314}
315
316uint32_t LineTable::FindLineEntryIndexByFileIndex(
317 uint32_t start_idx, const std::vector<uint32_t> &file_idx,
318 const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) {
319 auto file_idx_matcher = [](const std::vector<uint32_t> &file_indexes,
320 uint16_t entry_file_idx) {
321 return llvm::is_contained(Range: file_indexes, Element: entry_file_idx);
322 };
323
324 return FindLineEntryIndexByFileIndexImpl<std::vector<uint32_t>>(
325 start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher);
326}
327
328size_t LineTable::FindLineEntriesForFileIndex(uint32_t file_idx, bool append,
329 SymbolContextList &sc_list) {
330
331 if (!append)
332 sc_list.Clear();
333
334 size_t num_added = 0;
335 const size_t count = m_entries.size();
336 if (count > 0) {
337 SymbolContext sc(m_comp_unit);
338
339 for (size_t idx = 0; idx < count; ++idx) {
340 // Skip line table rows that terminate the previous row
341 // (is_terminal_entry is non-zero)
342 if (m_entries[idx].is_terminal_entry)
343 continue;
344
345 if (m_entries[idx].file_idx == file_idx) {
346 if (ConvertEntryAtIndexToLineEntry(idx, line_entry&: sc.line_entry)) {
347 ++num_added;
348 sc_list.Append(sc);
349 }
350 }
351 }
352 }
353 return num_added;
354}
355
356void LineTable::Dump(Stream *s, Target *target, Address::DumpStyle style,
357 Address::DumpStyle fallback_style, bool show_line_ranges) {
358 const size_t count = m_entries.size();
359 LineEntry line_entry;
360 SupportFileSP prev_file;
361 for (size_t idx = 0; idx < count; ++idx) {
362 ConvertEntryAtIndexToLineEntry(idx, line_entry);
363 line_entry.Dump(s, target, show_file: *prev_file != *line_entry.original_file_sp,
364 style, fallback_style, show_range: show_line_ranges);
365 s->EOL();
366 prev_file = line_entry.original_file_sp;
367 }
368}
369
370void LineTable::GetDescription(Stream *s, Target *target,
371 DescriptionLevel level) {
372 const size_t count = m_entries.size();
373 LineEntry line_entry;
374 for (size_t idx = 0; idx < count; ++idx) {
375 ConvertEntryAtIndexToLineEntry(idx, line_entry);
376 line_entry.GetDescription(s, level, cu: m_comp_unit, target, show_address_only: true);
377 s->EOL();
378 }
379}
380
381size_t LineTable::GetContiguousFileAddressRanges(FileAddressRanges &file_ranges,
382 bool append) {
383 if (!append)
384 file_ranges.Clear();
385 const size_t initial_count = file_ranges.GetSize();
386
387 const size_t count = m_entries.size();
388 LineEntry line_entry;
389 FileAddressRanges::Entry range(LLDB_INVALID_ADDRESS, 0);
390 for (size_t idx = 0; idx < count; ++idx) {
391 const Entry &entry = m_entries[idx];
392
393 if (entry.is_terminal_entry) {
394 if (range.GetRangeBase() != LLDB_INVALID_ADDRESS) {
395 range.SetRangeEnd(entry.file_addr);
396 file_ranges.Append(entry: range);
397 range.Clear(LLDB_INVALID_ADDRESS);
398 }
399 } else if (range.GetRangeBase() == LLDB_INVALID_ADDRESS) {
400 range.SetRangeBase(entry.file_addr);
401 }
402 }
403 return file_ranges.GetSize() - initial_count;
404}
405
406LineTable *LineTable::LinkLineTable(const FileRangeMap &file_range_map) {
407 std::unique_ptr<LineTable> line_table_up(new LineTable(m_comp_unit));
408 LineSequenceImpl sequence;
409 const size_t count = m_entries.size();
410 LineEntry line_entry;
411 const FileRangeMap::Entry *file_range_entry = nullptr;
412 const FileRangeMap::Entry *prev_file_range_entry = nullptr;
413 lldb::addr_t prev_file_addr = LLDB_INVALID_ADDRESS;
414 bool prev_entry_was_linked = false;
415 bool range_changed = false;
416 for (size_t idx = 0; idx < count; ++idx) {
417 const Entry &entry = m_entries[idx];
418
419 const bool end_sequence = entry.is_terminal_entry;
420 const lldb::addr_t lookup_file_addr =
421 entry.file_addr - (end_sequence ? 1 : 0);
422 if (file_range_entry == nullptr ||
423 !file_range_entry->Contains(r: lookup_file_addr)) {
424 prev_file_range_entry = file_range_entry;
425 file_range_entry = file_range_map.FindEntryThatContains(addr: lookup_file_addr);
426 range_changed = true;
427 }
428
429 lldb::addr_t prev_end_entry_linked_file_addr = LLDB_INVALID_ADDRESS;
430 lldb::addr_t entry_linked_file_addr = LLDB_INVALID_ADDRESS;
431
432 bool terminate_previous_entry = false;
433 if (file_range_entry) {
434 entry_linked_file_addr = entry.file_addr -
435 file_range_entry->GetRangeBase() +
436 file_range_entry->data;
437 // Determine if we need to terminate the previous entry when the previous
438 // entry was not contiguous with this one after being linked.
439 if (range_changed && prev_file_range_entry) {
440 prev_end_entry_linked_file_addr =
441 std::min<lldb::addr_t>(a: entry.file_addr,
442 b: prev_file_range_entry->GetRangeEnd()) -
443 prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data;
444 if (prev_end_entry_linked_file_addr != entry_linked_file_addr)
445 terminate_previous_entry = prev_entry_was_linked;
446 }
447 } else if (prev_entry_was_linked) {
448 // This entry doesn't have a remapping and it needs to be removed. Watch
449 // out in case we need to terminate a previous entry needs to be
450 // terminated now that one line entry in a sequence is not longer valid.
451 if (!sequence.m_entries.empty() &&
452 !sequence.m_entries.back().is_terminal_entry) {
453 terminate_previous_entry = true;
454 }
455 }
456
457 if (terminate_previous_entry && !sequence.m_entries.empty()) {
458 assert(prev_file_addr != LLDB_INVALID_ADDRESS);
459 UNUSED_IF_ASSERT_DISABLED(prev_file_addr);
460 sequence.m_entries.push_back(x: sequence.m_entries.back());
461 if (prev_end_entry_linked_file_addr == LLDB_INVALID_ADDRESS)
462 prev_end_entry_linked_file_addr =
463 std::min<lldb::addr_t>(a: entry.file_addr,
464 b: prev_file_range_entry->GetRangeEnd()) -
465 prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data;
466 sequence.m_entries.back().file_addr = prev_end_entry_linked_file_addr;
467 sequence.m_entries.back().is_terminal_entry = true;
468
469 // Append the sequence since we just terminated the previous one
470 line_table_up->InsertSequence(sequence: &sequence);
471 sequence.Clear();
472 }
473
474 // Now link the current entry
475 if (file_range_entry) {
476 // This entry has an address remapping and it needs to have its address
477 // relinked
478 sequence.m_entries.push_back(x: entry);
479 sequence.m_entries.back().file_addr = entry_linked_file_addr;
480 }
481
482 // If we have items in the sequence and the last entry is a terminal entry,
483 // insert this sequence into our new line table.
484 if (!sequence.m_entries.empty() &&
485 sequence.m_entries.back().is_terminal_entry) {
486 line_table_up->InsertSequence(sequence: &sequence);
487 sequence.Clear();
488 prev_entry_was_linked = false;
489 } else {
490 prev_entry_was_linked = file_range_entry != nullptr;
491 }
492 prev_file_addr = entry.file_addr;
493 range_changed = false;
494 }
495 if (line_table_up->m_entries.empty())
496 return nullptr;
497 return line_table_up.release();
498}
499

source code of lldb/source/Symbol/LineTable.cpp