source/Symbol/LineTable.cpp - lldb - Git at Google

 //===-- LineTable.cpp -------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//

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

 using namespace lldb;
 using namespace lldb_private;

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

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

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

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

 LineSequence* LineTable::CreateLineSequenceContainer ()
 {
     return new 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)
         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);
 #ifdef LLDB_CONFIGURATION_DEBUG
     // 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
 }


 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 should'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;
                             }
                         }
                     }

                 }

                 // 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())
     {
         const Entry& entry = m_entries[idx];
         ModuleSP module_sp (m_comp_unit->GetModule());
         if (module_sp && module_sp->ResolveFileAddress(entry.file_addr, line_entry.range.GetBaseAddress()))
         {
             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.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;
         }
     }
     return false;
 }

 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();
     std::vector<uint32_t>::const_iterator begin_pos = file_indexes.begin();
     std::vector<uint32_t>::const_iterator end_pos = file_indexes.end();
     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 (find (begin_pos, end_pos, m_entries[idx].file_idx) == end_pos)
             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.file, style, fallback_style, show_line_ranges);
         s->EOL();
         prev_file = line_entry.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_ap (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 contguous 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 (!entry.is_terminal_entry &&
                 !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);
             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_ap->InsertSequence (&sequence);
             sequence.Clear();
             prev_entry_was_linked = false;
         }

         // 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_ap->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_ap->m_entries.empty())
         return nullptr;
     return line_table_ap.release();
 }
	//===-- LineTable.cpp -------------------------------------------- C++ --===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//

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

	using namespace lldb;
	using namespace lldb_private;

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

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

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

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

	LineSequence* LineTable::CreateLineSequenceContainer ()
	{
	return new 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)
	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);
	#ifdef LLDB_CONFIGURATION_DEBUG
	// 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
	}



	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 should'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;
	}
	}
	}

	}

	// 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())
	{
	const Entry& entry = m_entries[idx];
	ModuleSP module_sp (m_comp_unit->GetModule());
	if (module_sp && module_sp->ResolveFileAddress(entry.file_addr, line_entry.range.GetBaseAddress()))
	{
	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.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;
	}
	}
	return false;
	}

	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();
	std::vector<uint32_t>::const_iterator begin_pos = file_indexes.begin();
	std::vector<uint32_t>::const_iterator end_pos = file_indexes.end();
	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 (find (begin_pos, end_pos, m_entries[idx].file_idx) == end_pos)
	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.file, style, fallback_style, show_line_ranges);
	s->EOL();
	prev_file = line_entry.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_ap (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 contguous 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 (!entry.is_terminal_entry &&
	!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);
	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_ap->InsertSequence (&sequence);
	sequence.Clear();
	prev_entry_was_linked = false;
	}

	// 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_ap->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_ap->m_entries.empty())
	return nullptr;
	return line_table_ap.release();
	}