lldb/source/Symbol/LineTable.cpp - third_party/llvm-project - Git at Google

 //===-- 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;
   SupportFileSP prev_file;
   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();
 }
	//===-- 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;
	SupportFileSP prev_file;
	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();
	}