//===-- 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<Sequence> &&sequences)
    : m_comp_unit(comp_unit), m_entries() {
  LessThanBinaryPredicate less_than_bp(this);
  llvm::stable_sort(sequences, less_than_bp);
  for (const Sequence &seq : sequences) {
    m_entries.insert(m_entries.end(), seq.m_entries.begin(),
                     seq.m_entries.end());
  }
}

// Destructor
LineTable::~LineTable() = default;

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);

  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);
}

void LineTable::AppendLineEntryToSequence(
    Sequence &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) {
  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 = sequence.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 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(Sequence sequence) {
  if (sequence.m_entries.empty())
    return;
  const Entry &entry = sequence.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(), sequence.m_entries.begin(),
                     sequence.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();
  LessThanBinaryPredicate less_than_bp(this);
  entry_collection::iterator pos =
      std::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, sequence.m_entries.begin(), sequence.m_entries.end());
}

bool LineTable::LessThanBinaryPredicate::operator()(const Entry &a,
                                                    const 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::LessThanBinaryPredicate::operator()(
    const Sequence &seq_a, const Sequence &seq_b) const {
  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;
}

uint32_t LineTable::lower_bound(const Address &so_addr) const {
  if (so_addr.GetModule() != m_comp_unit->GetModule())
    return GetSize();

  Entry search_entry;
  search_entry.file_addr = so_addr.GetFileAddress();
  if (search_entry.file_addr == LLDB_INVALID_ADDRESS)
    return GetSize();

  // This is not a typo. upper_bound returns the first entry which definitely
  // does not contain this address, which means the entry before it *might*
  // contain it -- if it is not a termination entry.
  auto pos =
      llvm::upper_bound(m_entries, search_entry, Entry::EntryAddressLessThan);

  if (pos != m_entries.begin() && !std::prev(pos)->is_terminal_entry)
    --pos;

  return std::distance(m_entries.begin(), pos);
}

std::pair<uint32_t, uint32_t>
LineTable::GetLineEntryIndexRange(const AddressRange &range) const {
  uint32_t first = lower_bound(range.GetBaseAddress());
  if (first >= GetSize() || range.GetByteSize() == 0)
    return {first, first};

  Entry search_entry;
  search_entry.file_addr =
      range.GetBaseAddress().GetFileAddress() + range.GetByteSize();

  // lower_bound returns the first entry which starts on or after the given
  // address, which is exactly what we want -- *except* if the entry is a
  // termination entry (in that case, we want the one after it).
  auto pos =
      std::lower_bound(std::next(m_entries.begin(), first), m_entries.end(),
                       search_entry, Entry::EntryAddressLessThan);
  if (pos != m_entries.end() && pos->file_addr == search_entry.file_addr &&
      pos->is_terminal_entry)
    ++pos;

  return {first, std::distance(m_entries.begin(), pos)};
}

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

  uint32_t idx = lower_bound(so_addr);
  if (idx >= GetSize())
    return false;

  addr_t file_addr = so_addr.GetFileAddress();
  if (m_entries[idx].file_addr > file_addr)
    return false;

  bool success = ConvertEntryAtIndexToLineEntry(idx, line_entry);
  if (index_ptr != nullptr && success)
    *index_ptr = 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_sp =
      m_comp_unit->GetSupportFiles().GetSupportFileAtIndex(entry.file_idx);
  line_entry.original_file_sp =
      m_comp_unit->GetSupportFiles().GetSupportFileAtIndex(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, uint32_t file_idx,
    const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) {
  auto file_idx_matcher = [](uint32_t file_index, uint16_t entry_file_idx) {
    return file_index == entry_file_idx;
  };
  return FindLineEntryIndexByFileIndexImpl<uint32_t>(

      start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher);
}

uint32_t LineTable::FindLineEntryIndexByFileIndex(
    uint32_t start_idx, const std::vector<uint32_t> &file_idx,
    const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) {
  auto file_idx_matcher = [](const std::vector<uint32_t> &file_indexes,
                             uint16_t entry_file_idx) {
    return llvm::is_contained(file_indexes, entry_file_idx);
  };

  return FindLineEntryIndexByFileIndexImpl<std::vector<uint32_t>>(
      start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher);
}

size_t LineTable::FindLineEntriesForFileIndex(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;
  SupportFileNSP prev_file = std::make_shared<SupportFile>();
  for (size_t idx = 0; idx < count; ++idx) {
    ConvertEntryAtIndexToLineEntry(idx, line_entry);
    line_entry.Dump(s, target, !prev_file->Equal(*line_entry.original_file_sp),
                    style, fallback_style, show_line_ranges);
    s->EOL();
    prev_file = line_entry.original_file_sp;
  }
}

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));
  Sequence 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(std::move(sequence));
    }

    // 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(std::move(sequence));
      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();
}