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

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