source/Symbol/LineTable.cpp

//===-- LineTable.cpp -----------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "lldb/Symbol/LineTable.h"
#include "lldb/Core/Address.h"
#include "lldb/Core/Module.h"
#include "lldb/Core/Section.h"
#include "lldb/Symbol/CompileUnit.h"
#include "lldb/Utility/Stream.h"
#include <algorithm>

using namespace lldb;
using namespace lldb_private;

// LineTable constructor
LineTable::LineTable(CompileUnit *comp_unit)
    : m_comp_unit(comp_unit), m_entries() {}

LineTable::LineTable(CompileUnit *comp_unit,
                     std::vector<std::unique_ptr<LineSequence>> &&sequences)
    : m_comp_unit(comp_unit), m_entries() {
  LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
  llvm::stable_sort(sequences, less_than_bp);
  for (const auto &sequence : sequences) {
    LineSequenceImpl *seq = static_cast<LineSequenceImpl *>(sequence.get());
    m_entries.insert(m_entries.end(), seq->m_entries.begin(),
                     seq->m_entries.end());
  }
}

// Destructor
LineTable::~LineTable() {}

void LineTable::InsertLineEntry(lldb::addr_t file_addr, uint32_t line,
                                uint16_t column, uint16_t file_idx,
                                bool is_start_of_statement,
                                bool is_start_of_basic_block,
                                bool is_prologue_end, bool is_epilogue_begin,
                                bool is_terminal_entry) {
  Entry entry(file_addr, line, column, file_idx, is_start_of_statement,
              is_start_of_basic_block, is_prologue_end, is_epilogue_begin,
              is_terminal_entry);

  LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
  entry_collection::iterator pos =
      llvm::upper_bound(m_entries, entry, less_than_bp);

  //  Stream s(stdout);
  //  s << "\n\nBefore:\n";
  //  Dump (&s, Address::DumpStyleFileAddress);
  m_entries.insert(pos, entry);
  //  s << "After:\n";
  //  Dump (&s, Address::DumpStyleFileAddress);
}

LineSequence::LineSequence() {}

void LineTable::LineSequenceImpl::Clear() { m_entries.clear(); }

std::unique_ptr<LineSequence> LineTable::CreateLineSequenceContainer() {
  return std::make_unique<LineTable::LineSequenceImpl>();
}

void LineTable::AppendLineEntryToSequence(
    LineSequence *sequence, lldb::addr_t file_addr, uint32_t line,
    uint16_t column, uint16_t file_idx, bool is_start_of_statement,
    bool is_start_of_basic_block, bool is_prologue_end, bool is_epilogue_begin,
    bool is_terminal_entry) {
  assert(sequence != nullptr);
  LineSequenceImpl *seq = reinterpret_cast<LineSequenceImpl *>(sequence);
  Entry entry(file_addr, line, column, file_idx, is_start_of_statement,
              is_start_of_basic_block, is_prologue_end, is_epilogue_begin,
              is_terminal_entry);
  entry_collection &entries = seq->m_entries;
  // Replace the last entry if the address is the same, otherwise append it. If
  // we have multiple line entries at the same address, this indicates illegal
  // DWARF so this "fixes" the line table to be correct. If not fixed this can
  // cause a line entry's address that when resolved back to a symbol context,
  // could resolve to a different line entry. We really want a
  // 1 to 1 mapping
  // here to avoid these kinds of inconsistencies. We will need tor revisit
  // this if the DWARF line tables are updated to allow multiple entries at the
  // same address legally.
  if (!entries.empty() && entries.back().file_addr == file_addr) {
    // GCC don't use the is_prologue_end flag to mark the first instruction
    // after the prologue.
    // Instead of it it is issuing a line table entry for the first instruction
    // of the prologue and one for the first instruction after the prologue. If
    // the size of the prologue is 0 instruction then the 2 line entry will
    // have the same file address. Removing it will remove our ability to
    // properly detect the location of the end of prologe so we set the
    // prologue_end flag to preserve this information (setting the prologue_end
    // flag for an entry what is after the prologue end don't have any effect)
    entry.is_prologue_end = entry.file_idx == entries.back().file_idx;
    entries.back() = entry;
  } else
    entries.push_back(entry);
}

void LineTable::InsertSequence(LineSequence *sequence) {
  assert(sequence != nullptr);
  LineSequenceImpl *seq = reinterpret_cast<LineSequenceImpl *>(sequence);
  if (seq->m_entries.empty())
    return;
  Entry &entry = seq->m_entries.front();

  // If the first entry address in this sequence is greater than or equal to
  // the address of the last item in our entry collection, just append.
  if (m_entries.empty() ||
      !Entry::EntryAddressLessThan(entry, m_entries.back())) {
    m_entries.insert(m_entries.end(), seq->m_entries.begin(),
                     seq->m_entries.end());
    return;
  }

  // Otherwise, find where this belongs in the collection
  entry_collection::iterator begin_pos = m_entries.begin();
  entry_collection::iterator end_pos = m_entries.end();
  LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
  entry_collection::iterator pos =
      upper_bound(begin_pos, end_pos, entry, less_than_bp);

  // We should never insert a sequence in the middle of another sequence
  if (pos != begin_pos) {
    while (pos < end_pos && !((pos - 1)->is_terminal_entry))
      pos++;
  }

#ifndef NDEBUG
  // If we aren't inserting at the beginning, the previous entry should
  // terminate a sequence.
  if (pos != begin_pos) {
    entry_collection::iterator prev_pos = pos - 1;
    assert(prev_pos->is_terminal_entry);
  }
#endif
  m_entries.insert(pos, seq->m_entries.begin(), seq->m_entries.end());
}

LineTable::Entry::LessThanBinaryPredicate::LessThanBinaryPredicate(
    LineTable *line_table)
    : m_line_table(line_table) {}

bool LineTable::Entry::LessThanBinaryPredicate::
operator()(const LineTable::Entry &a, const LineTable::Entry &b) const {
#define LT_COMPARE(a, b)                                                       \
  if (a != b)                                                                  \
  return a < b
  LT_COMPARE(a.file_addr, b.file_addr);
  // b and a reversed on purpose below.
  LT_COMPARE(b.is_terminal_entry, a.is_terminal_entry);
  LT_COMPARE(a.line, b.line);
  LT_COMPARE(a.column, b.column);
  LT_COMPARE(a.is_start_of_statement, b.is_start_of_statement);
  LT_COMPARE(a.is_start_of_basic_block, b.is_start_of_basic_block);
  // b and a reversed on purpose below.
  LT_COMPARE(b.is_prologue_end, a.is_prologue_end);
  LT_COMPARE(a.is_epilogue_begin, b.is_epilogue_begin);
  LT_COMPARE(a.file_idx, b.file_idx);
  return false;
#undef LT_COMPARE
}

bool LineTable::Entry::LessThanBinaryPredicate::
operator()(const std::unique_ptr<LineSequence> &sequence_a,
           const std::unique_ptr<LineSequence> &sequence_b) const {
  auto *seq_a = static_cast<const LineSequenceImpl *>(sequence_a.get());
  auto *seq_b = static_cast<const LineSequenceImpl *>(sequence_b.get());
  return (*this)(seq_a->m_entries.front(), seq_b->m_entries.front());
}

uint32_t LineTable::GetSize() const { return m_entries.size(); }

bool LineTable::GetLineEntryAtIndex(uint32_t idx, LineEntry &line_entry) {
  if (idx < m_entries.size()) {
    ConvertEntryAtIndexToLineEntry(idx, line_entry);
    return true;
  }
  line_entry.Clear();
  return false;
}

bool LineTable::FindLineEntryByAddress(const Address &so_addr,
                                       LineEntry &line_entry,
                                       uint32_t *index_ptr) {
  if (index_ptr != nullptr)
    *index_ptr = UINT32_MAX;

  bool success = false;

  if (so_addr.GetModule().get() == m_comp_unit->GetModule().get()) {
    Entry search_entry;
    search_entry.file_addr = so_addr.GetFileAddress();
    if (search_entry.file_addr != LLDB_INVALID_ADDRESS) {
      entry_collection::const_iterator begin_pos = m_entries.begin();
      entry_collection::const_iterator end_pos = m_entries.end();
      entry_collection::const_iterator pos = lower_bound(
          begin_pos, end_pos, search_entry, Entry::EntryAddressLessThan);
      if (pos != end_pos) {
        if (pos != begin_pos) {
          if (pos->file_addr != search_entry.file_addr)
            --pos;
          else if (pos->file_addr == search_entry.file_addr) {
            // If this is a termination entry, it shouldn't match since entries
            // with the "is_terminal_entry" member set to true are termination
            // entries that define the range for the previous entry.
            if (pos->is_terminal_entry) {
              // The matching entry is a terminal entry, so we skip ahead to
              // the next entry to see if there is another entry following this
              // one whose section/offset matches.
              ++pos;
              if (pos != end_pos) {
                if (pos->file_addr != search_entry.file_addr)
                  pos = end_pos;
              }
            }

            if (pos != end_pos) {
              // While in the same section/offset backup to find the first line
              // entry that matches the address in case there are multiple
              while (pos != begin_pos) {
                entry_collection::const_iterator prev_pos = pos - 1;
                if (prev_pos->file_addr == search_entry.file_addr &&
                    prev_pos->is_terminal_entry == false)
                  --pos;
                else
                  break;
              }
            }
          }
        }
        else
        {
          // There might be code in the containing objfile before the first
          // line table entry.  Make sure that does not get considered part of
          // the first line table entry.
          if (pos->file_addr > so_addr.GetFileAddress())
            return false;
        }

        // Make sure we have a valid match and that the match isn't a
        // terminating entry for a previous line...
        if (pos != end_pos && pos->is_terminal_entry == false) {
          uint32_t match_idx = std::distance(begin_pos, pos);
          success = ConvertEntryAtIndexToLineEntry(match_idx, line_entry);
          if (index_ptr != nullptr && success)
            *index_ptr = match_idx;
        }
      }
    }
  }
  return success;
}

bool LineTable::ConvertEntryAtIndexToLineEntry(uint32_t idx,
                                               LineEntry &line_entry) {
  if (idx >= m_entries.size())
    return false;

  const Entry &entry = m_entries[idx];
  ModuleSP module_sp(m_comp_unit->GetModule());
  if (!module_sp)
    return false;

  addr_t file_addr = entry.file_addr;

  // A terminal entry can point outside of a module or a section. Decrement the
  // address to ensure it resolves correctly.
  if (entry.is_terminal_entry)
    --file_addr;

  if (!module_sp->ResolveFileAddress(file_addr,
                                     line_entry.range.GetBaseAddress()))
    return false;

  // Now undo the decrement above.
  if (entry.is_terminal_entry)
    line_entry.range.GetBaseAddress().Slide(1);

  if (!entry.is_terminal_entry && idx + 1 < m_entries.size())
    line_entry.range.SetByteSize(m_entries[idx + 1].file_addr -
                                 entry.file_addr);
  else
    line_entry.range.SetByteSize(0);

  line_entry.file =
      m_comp_unit->GetSupportFiles().GetFileSpecAtIndex(entry.file_idx);
  line_entry.original_file =
      m_comp_unit->GetSupportFiles().GetFileSpecAtIndex(entry.file_idx);
  line_entry.line = entry.line;
  line_entry.column = entry.column;
  line_entry.is_start_of_statement = entry.is_start_of_statement;
  line_entry.is_start_of_basic_block = entry.is_start_of_basic_block;
  line_entry.is_prologue_end = entry.is_prologue_end;
  line_entry.is_epilogue_begin = entry.is_epilogue_begin;
  line_entry.is_terminal_entry = entry.is_terminal_entry;
  return true;
}

uint32_t LineTable::FindLineEntryIndexByFileIndex(
    uint32_t start_idx, const std::vector<uint32_t> &file_indexes,
    uint32_t line, bool exact, LineEntry *line_entry_ptr) {

  const size_t count = m_entries.size();
  size_t best_match = UINT32_MAX;

  for (size_t idx = start_idx; idx < count; ++idx) {
    // Skip line table rows that terminate the previous row (is_terminal_entry
    // is non-zero)
    if (m_entries[idx].is_terminal_entry)
      continue;

    if (!llvm::is_contained(file_indexes, m_entries[idx].file_idx))
      continue;

    // Exact match always wins.  Otherwise try to find the closest line > the
    // desired line.
    // FIXME: Maybe want to find the line closest before and the line closest
    // after and
    // if they're not in the same function, don't return a match.

    if (m_entries[idx].line < line) {
      continue;
    } else if (m_entries[idx].line == line) {
      if (line_entry_ptr)
        ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
      return idx;
    } else if (!exact) {
      if (best_match == UINT32_MAX)
        best_match = idx;
      else if (m_entries[idx].line < m_entries[best_match].line)
        best_match = idx;
    }
  }

  if (best_match != UINT32_MAX) {
    if (line_entry_ptr)
      ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr);
    return best_match;
  }
  return UINT32_MAX;
}

uint32_t LineTable::FindLineEntryIndexByFileIndex(uint32_t start_idx,
                                                  uint32_t file_idx,
                                                  uint32_t line, bool exact,
                                                  LineEntry *line_entry_ptr) {
  const size_t count = m_entries.size();
  size_t best_match = UINT32_MAX;

  for (size_t idx = start_idx; idx < count; ++idx) {
    // Skip line table rows that terminate the previous row (is_terminal_entry
    // is non-zero)
    if (m_entries[idx].is_terminal_entry)
      continue;

    if (m_entries[idx].file_idx != file_idx)
      continue;

    // Exact match always wins.  Otherwise try to find the closest line > the
    // desired line.
    // FIXME: Maybe want to find the line closest before and the line closest
    // after and
    // if they're not in the same function, don't return a match.

    if (m_entries[idx].line < line) {
      continue;
    } else if (m_entries[idx].line == line) {
      if (line_entry_ptr)
        ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
      return idx;
    } else if (!exact) {
      if (best_match == UINT32_MAX)
        best_match = idx;
      else if (m_entries[idx].line < m_entries[best_match].line)
        best_match = idx;
    }
  }

  if (best_match != UINT32_MAX) {
    if (line_entry_ptr)
      ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr);
    return best_match;
  }
  return UINT32_MAX;
}

size_t LineTable::FineLineEntriesForFileIndex(uint32_t file_idx, bool append,
                                              SymbolContextList &sc_list) {

  if (!append)
    sc_list.Clear();

  size_t num_added = 0;
  const size_t count = m_entries.size();
  if (count > 0) {
    SymbolContext sc(m_comp_unit);

    for (size_t idx = 0; idx < count; ++idx) {
      // Skip line table rows that terminate the previous row
      // (is_terminal_entry is non-zero)
      if (m_entries[idx].is_terminal_entry)
        continue;

      if (m_entries[idx].file_idx == file_idx) {
        if (ConvertEntryAtIndexToLineEntry(idx, sc.line_entry)) {
          ++num_added;
          sc_list.Append(sc);
        }
      }
    }
  }
  return num_added;
}

void LineTable::Dump(Stream *s, Target *target, Address::DumpStyle style,
                     Address::DumpStyle fallback_style, bool show_line_ranges) {
  const size_t count = m_entries.size();
  LineEntry line_entry;
  FileSpec prev_file;
  for (size_t idx = 0; idx < count; ++idx) {
    ConvertEntryAtIndexToLineEntry(idx, line_entry);
    line_entry.Dump(s, target, prev_file != line_entry.original_file, style,
                    fallback_style, show_line_ranges);
    s->EOL();
    prev_file = line_entry.original_file;
  }
}

void LineTable::GetDescription(Stream *s, Target *target,
                               DescriptionLevel level) {
  const size_t count = m_entries.size();
  LineEntry line_entry;
  for (size_t idx = 0; idx < count; ++idx) {
    ConvertEntryAtIndexToLineEntry(idx, line_entry);
    line_entry.GetDescription(s, level, m_comp_unit, target, true);
    s->EOL();
  }
}

size_t LineTable::GetContiguousFileAddressRanges(FileAddressRanges &file_ranges,
                                                 bool append) {
  if (!append)
    file_ranges.Clear();
  const size_t initial_count = file_ranges.GetSize();

  const size_t count = m_entries.size();
  LineEntry line_entry;
  FileAddressRanges::Entry range(LLDB_INVALID_ADDRESS, 0);
  for (size_t idx = 0; idx < count; ++idx) {
    const Entry &entry = m_entries[idx];

    if (entry.is_terminal_entry) {
      if (range.GetRangeBase() != LLDB_INVALID_ADDRESS) {
        range.SetRangeEnd(entry.file_addr);
        file_ranges.Append(range);
        range.Clear(LLDB_INVALID_ADDRESS);
      }
    } else if (range.GetRangeBase() == LLDB_INVALID_ADDRESS) {
      range.SetRangeBase(entry.file_addr);
    }
  }
  return file_ranges.GetSize() - initial_count;
}

LineTable *LineTable::LinkLineTable(const FileRangeMap &file_range_map) {
  std::unique_ptr<LineTable> line_table_up(new LineTable(m_comp_unit));
  LineSequenceImpl sequence;
  const size_t count = m_entries.size();
  LineEntry line_entry;
  const FileRangeMap::Entry *file_range_entry = nullptr;
  const FileRangeMap::Entry *prev_file_range_entry = nullptr;
  lldb::addr_t prev_file_addr = LLDB_INVALID_ADDRESS;
  bool prev_entry_was_linked = false;
  bool range_changed = false;
  for (size_t idx = 0; idx < count; ++idx) {
    const Entry &entry = m_entries[idx];

    const bool end_sequence = entry.is_terminal_entry;
    const lldb::addr_t lookup_file_addr =
        entry.file_addr - (end_sequence ? 1 : 0);
    if (file_range_entry == nullptr ||
        !file_range_entry->Contains(lookup_file_addr)) {
      prev_file_range_entry = file_range_entry;
      file_range_entry = file_range_map.FindEntryThatContains(lookup_file_addr);
      range_changed = true;
    }

    lldb::addr_t prev_end_entry_linked_file_addr = LLDB_INVALID_ADDRESS;
    lldb::addr_t entry_linked_file_addr = LLDB_INVALID_ADDRESS;

    bool terminate_previous_entry = false;
    if (file_range_entry) {
      entry_linked_file_addr = entry.file_addr -
                               file_range_entry->GetRangeBase() +
                               file_range_entry->data;
      // Determine if we need to terminate the previous entry when the previous
      // entry was not contiguous with this one after being linked.
      if (range_changed && prev_file_range_entry) {
        prev_end_entry_linked_file_addr =
            std::min<lldb::addr_t>(entry.file_addr,
                                   prev_file_range_entry->GetRangeEnd()) -
            prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data;
        if (prev_end_entry_linked_file_addr != entry_linked_file_addr)
          terminate_previous_entry = prev_entry_was_linked;
      }
    } else if (prev_entry_was_linked) {
      // This entry doesn't have a remapping and it needs to be removed. Watch
      // out in case we need to terminate a previous entry needs to be
      // terminated now that one line entry in a sequence is not longer valid.
      if (!sequence.m_entries.empty() &&
          !sequence.m_entries.back().is_terminal_entry) {
        terminate_previous_entry = true;
      }
    }

    if (terminate_previous_entry && !sequence.m_entries.empty()) {
      assert(prev_file_addr != LLDB_INVALID_ADDRESS);
      UNUSED_IF_ASSERT_DISABLED(prev_file_addr);
      sequence.m_entries.push_back(sequence.m_entries.back());
      if (prev_end_entry_linked_file_addr == LLDB_INVALID_ADDRESS)
        prev_end_entry_linked_file_addr =
            std::min<lldb::addr_t>(entry.file_addr,
                                   prev_file_range_entry->GetRangeEnd()) -
            prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data;
      sequence.m_entries.back().file_addr = prev_end_entry_linked_file_addr;
      sequence.m_entries.back().is_terminal_entry = true;

      // Append the sequence since we just terminated the previous one
      line_table_up->InsertSequence(&sequence);
      sequence.Clear();
    }

    // Now link the current entry
    if (file_range_entry) {
      // This entry has an address remapping and it needs to have its address
      // relinked
      sequence.m_entries.push_back(entry);
      sequence.m_entries.back().file_addr = entry_linked_file_addr;
    }

    // If we have items in the sequence and the last entry is a terminal entry,
    // insert this sequence into our new line table.
    if (!sequence.m_entries.empty() &&
        sequence.m_entries.back().is_terminal_entry) {
      line_table_up->InsertSequence(&sequence);
      sequence.Clear();
      prev_entry_was_linked = false;
    } else {
      prev_entry_was_linked = file_range_entry != nullptr;
    }
    prev_file_addr = entry.file_addr;
    range_changed = false;
  }
  if (line_table_up->m_entries.empty())
    return nullptr;
  return line_table_up.release();
}