Make SymbolFileDWARF::ParseLineTable use std::sort instead of insertion sort

[unnar]

Summary

Motivation: When setting breakpoints in certain projects line sequences are frequently being inserted out of order.

Rather than inserting sequences one at a time into a sorted line table, store all the line sequences as we're building them up and sort and flatten afterwards.

[labath]

Thanks for the patch. I've been wondering how to improve this, and this solution is pretty neat.

I have just one request. Instead of the ReplaceLineTableWithSequences thingy, could you just create a LineTable constructor, which takes an ArrayRef<LineSequence *> or similar. It looks like all it takes is to make CreateLineSequenceContainer static, so you can invoke it without a LineTable instance. (There are other possible cleanups here too, but I don't think its your job do fix all of those...)

[unnar]

In D72909#1826110, @labath wrote:

Thanks for the patch. I've been wondering how to improve this, and this solution is pretty neat.

I have just one request. Instead of the ReplaceLineTableWithSequences thingy, could you just create a LineTable constructor, which takes an ArrayRef<LineSequence *> or similar. It looks like all it takes is to make CreateLineSequenceContainer static, so you can invoke it without a LineTable instance. (There are other possible cleanups here too, but I don't think its your job do fix all of those...)

Thanks for the quick review!

It also requires AppendLineEntryToSequence to be static but I assume that should also be just fine.

[teemperor]

lldb/source/Symbol/LineTable.cpp

172

Nit pick, this would also work without the reinterpret_cast and const arguments. E.g.:

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

[unnar]

@labath

Can you take another look and see if this matches what you had in mind?

[labath]

Yes, that's looks pretty much like it, but it seems you uploaded the diff incorrectly -- it looks like its based on the previous version of your patch and not master (you should always upload the full set of changes not just the recent additions).

Also, when I asked for an ArrayRef, I forgot that you are sorting the thing -- a vector does seem reasonable in that case (sorry).

Do you have commit access? If not, I can land this for you (as soon as I get the correct diff).

[unnar]

Switched back to std::vector and uploaded the full diff.

I don't have commit access so it would be appreciated if you could land this for me, thanks!

[grimar]

lldb/source/Symbol/LineTable.cpp

27

I wonder if this have to be std::stable_sort?
For std::sort the order of equal elements is not guaranteed to be preserved.

nit: you could also probably use the llvm::sort (it would be a bit shorter):
llvm::sort(sequences, less_than_bp);

[teemperor]

lldb/source/Symbol/LineTable.cpp

27

I think we should change this to llvm::sort just because of the additional checks we get there (I think the shuffle/sort<->stable_sort checks are only in llvm::sort).

[labath]

lldb/source/Symbol/LineTable.cpp

27

I've changed this to llvm::stable_sort in 9a52ea5cf9c. I went for a stable sort because it's possible (though probably not very useful) for the debug info to contain two line sequences for the same address (and I've just today found a flaky test due to nondeterminism in lldb).

lldb/include/lldb/Symbol/LineTable.h

 class LineTable {
 public:
   /// Construct with compile unit.
   ///
   /// \param[in] comp_unit
   ///     The compile unit to which this line table belongs.
   LineTable(CompileUnit *comp_unit);
 
+  /// Construct with entries found in \a sequences.
+  ///
+  /// \param[in] sequences
+  ///     Unsorted list of line sequences.
+  LineTable(CompileUnit *comp_unit, std::vector<LineSequence *> &sequences);
+
   /// Destructor.
   ~LineTable();
 
   /// Adds a new line entry to this line table.
   ///
   /// All line entries are maintained in file address order.
   ///
   /// \param[in] line_entry
   ///     A const reference to a new line_entry to add to this line
   ///     table.
   ///
   /// \see Address::DumpStyle
   //  void
   //  AddLineEntry (const LineEntry& line_entry);
 
   // Called when you can't guarantee the addresses are in increasing order
   void 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);
 
   // Used to instantiate the LineSequence helper class
-  LineSequence *CreateLineSequenceContainer();
+  static LineSequence *CreateLineSequenceContainer();
 
   // Append an entry to a caller-provided collection that will later be
   // inserted in this line table.
-  void AppendLineEntryToSequence(LineSequence *sequence, lldb::addr_t file_addr,
+  static void 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);
 
   // Insert a sequence of entries into this line table.
   void InsertSequence(LineSequence *sequence);

 #undef SCALAR_COMPARE
       return 0;
     }
 
     class LessThanBinaryPredicate {
     public:
       LessThanBinaryPredicate(LineTable *line_table);
       bool operator()(const LineTable::Entry &, const LineTable::Entry &) const;
+      bool operator()(const LineSequence*, const LineSequence*) const;
 
     protected:
       LineTable *m_line_table;
     };
 
     static bool EntryAddressLessThan(const Entry &lhs, const Entry &rhs) {
       return lhs.file_addr < rhs.file_addr;
     }

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

const llvm::DWARFDebugLine::LineTable *line_table = ParseLLVMLineTable(
       m_context, line, cu_line_offset, dwarf_cu->GetOffset());
 
   if (!line_table)
     return false;
 
   // FIXME: Rather than parsing the whole line table and then copying it over
   // into LLDB, we should explore using a callback to populate the line table
   // while we parse to reduce memory usage.
-  std::unique_ptr<LineTable> line_table_up =
-      std::make_unique<LineTable>(&comp_unit);
-  LineSequence *sequence = line_table_up->CreateLineSequenceContainer();
+  LineSequence *sequence = LineTable::CreateLineSequenceContainer();
+  std::vector<LineSequence *> sequences;
   for (auto &row : line_table->Rows) {
-    line_table_up->AppendLineEntryToSequence(
+    LineTable::AppendLineEntryToSequence(
         sequence, row.Address.Address, row.Line, row.Column, row.File,
         row.IsStmt, row.BasicBlock, row.PrologueEnd, row.EpilogueBegin,
         row.EndSequence);
     if (row.EndSequence) {
-      line_table_up->InsertSequence(sequence);
-      sequence = line_table_up->CreateLineSequenceContainer();
+      sequences.push_back(sequence);
+      sequence = LineTable::CreateLineSequenceContainer();
     }
   }
 
+  std::unique_ptr<LineTable> line_table_up =
+      std::make_unique<LineTable>(&comp_unit, sequences);
+
   if (SymbolFileDWARFDebugMap *debug_map_symfile = GetDebugMapSymfile()) {
     // We have an object file that has a line table with addresses that are not
     // linked. We need to link the line table and convert the addresses that
     // are relative to the .o file into addresses for the main executable.
     comp_unit.SetLineTable(
         debug_map_symfile->LinkOSOLineTable(this, line_table_up.get()));
   } else {
     comp_unit.SetLineTable(line_table_up.release());

lldb/source/Symbol/LineTable.cpp

 
 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<LineSequence *> &sequences)
+    : m_comp_unit(comp_unit), m_entries() {
+  LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
+  std::sort(sequences.begin(), sequences.end(), less_than_bp);
+  for (auto *sequence : sequences) {
+    LineSequenceImpl *seq = reinterpret_cast<LineSequenceImpl *>(sequence);
+    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,
#define LT_COMPARE(a, b)                                                       \
   // 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 LineSequence *sequence_a, const LineSequence *sequence_b) const {
+  auto *seq_a = static_cast<const LineSequenceImpl *>(sequence_a);
+  auto *seq_b = static_cast<const LineSequenceImpl *>(sequence_b);
+  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();