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(sequences, less_than_bp);
29  for (const auto &sequence : sequences) {
30    LineSequenceImpl *seq = static_cast<LineSequenceImpl *>(sequence.get());
31    m_entries.insert(m_entries.end(), seq->m_entries.begin(),
32                     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(m_entries, entry, less_than_bp);
52
53  //  Stream s(stdout);
54  //  s << "\n\nBefore:\n";
55  //  Dump (&s, Address::DumpStyleFileAddress);
56  m_entries.insert(pos, 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(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(entry, m_entries.back())) {
116    m_entries.insert(m_entries.end(), seq->m_entries.begin(),
117                     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(begin_pos, end_pos, entry, 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(pos, seq->m_entries.begin(), 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          begin_pos, end_pos, search_entry, 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(begin_pos, pos);
250          success = ConvertEntryAtIndexToLineEntry(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(file_addr,
278                                     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(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 =
292      m_comp_unit->GetSupportFiles().GetFileSpecAtIndex(entry.file_idx);
293  line_entry.original_file_sp =
294      m_comp_unit->GetSupportFiles().GetSupportFileAtIndex(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(file_indexes, 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, 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, *prev_file != *line_entry.original_file_sp,
364                    style, fallback_style, 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, m_comp_unit, target, 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(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(lookup_file_addr)) {
424      prev_file_range_entry = file_range_entry;
425      file_range_entry = file_range_map.FindEntryThatContains(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>(entry.file_addr,
442                                   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(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>(entry.file_addr,
464                                   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);
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(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);
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