SymbolFileBreakpad: Add line table support

Summary:
This patch teaches SymbolFileBreakpad to parse the line information in
breakpad files and present it to lldb.

The trickiest question here was what kind of "compile units" to present
to lldb, as there really isn't enough information in breakpad files to
correctly reconstruct those.

A couple of options were considered
- have the entire file be one compile unit
- have one compile unit for each FILE record
- have one compile unit for each FUNC record

The main drawback of the first approach is that all of the files would
be considered "headers" by lldb, and so they wouldn't be searched if
target.inline-breakpoint-strategy=never. The single compile unit would
also be huge, and there isn't a good way to name it.

The second approach will create mostly correct compile units for cpp
files, but it will still be wrong for headers. However, the biggest
drawback here seemed to be the fact that this can cause a compile unit
to change mid-function (for example when a function from another file is
inlined or another file is #included into a function). While I don't
know of any specific thing that would break in this case, it does sound
like a thing that we should avoid.

In the end, we chose the third option, as it didn't seem to have any
major disadvantages, though it was not ideal either. One disadvantage
here is that this generates a large number of compile units, and there
is still a question on how to name it. We chose to simply name it after
the first line record in that function. This should be correct 99.99% of
the time, though it can produce somewhat strange results if the very
first line record comes from an #included file.

Reviewers: clayborg, zturner, lemo, markmentovai

Subscribers: lldb-commits

Differential Revision: https://reviews.llvm.org/D56595

llvm-svn: 353404

1 files changed, 288 insertions, 32 deletions

diff --git a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp
index 98d2e9296dc..198be6c4803 100644
--- a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp
+++ b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp
@@ -13,7 +13,9 @@
 #include "lldb/Core/PluginManager.h"
 #include "lldb/Core/Section.h"
 #include "lldb/Host/FileSystem.h"
+#include "lldb/Symbol/CompileUnit.h"
 #include "lldb/Symbol/ObjectFile.h"
+#include "lldb/Symbol/SymbolVendor.h"
 #include "lldb/Symbol/TypeMap.h"
 #include "lldb/Utility/Log.h"
 #include "llvm/ADT/StringExtras.h"
@@ -22,64 +24,141 @@ using namespace lldb;
 using namespace lldb_private;
 using namespace lldb_private::breakpad;
 
-namespace {
-class LineIterator {
+class SymbolFileBreakpad::LineIterator {
 public:
   // begin iterator for sections of given type
   LineIterator(ObjectFile &obj, Record::Kind section_type)
       : m_obj(&obj), m_section_type(toString(section_type)),
-        m_next_section_idx(0) {
+        m_next_section_idx(0), m_next_line(llvm::StringRef::npos) {
     ++*this;
   }
 
+  // An iterator starting at the position given by the bookmark.
+  LineIterator(ObjectFile &obj, Record::Kind section_type, Bookmark bookmark);
+
   // end iterator
   explicit LineIterator(ObjectFile &obj)
       : m_obj(&obj),
-        m_next_section_idx(m_obj->GetSectionList()->GetNumSections(0)) {}
+        m_next_section_idx(m_obj->GetSectionList()->GetNumSections(0)),
+        m_current_line(llvm::StringRef::npos),
+        m_next_line(llvm::StringRef::npos) {}
 
   friend bool operator!=(const LineIterator &lhs, const LineIterator &rhs) {
     assert(lhs.m_obj == rhs.m_obj);
     if (lhs.m_next_section_idx != rhs.m_next_section_idx)
       return true;
-    if (lhs.m_next_text.data() != rhs.m_next_text.data())
+    if (lhs.m_current_line != rhs.m_current_line)
       return true;
-    assert(lhs.m_current_text == rhs.m_current_text);
-    assert(rhs.m_next_text == rhs.m_next_text);
+    assert(lhs.m_next_line == rhs.m_next_line);
     return false;
   }
 
   const LineIterator &operator++();
-  llvm::StringRef operator*() const { return m_current_text; }
+  llvm::StringRef operator*() const {
+    return m_section_text.slice(m_current_line, m_next_line);
+  }
+
+  Bookmark GetBookmark() const {
+    return Bookmark{m_next_section_idx, m_current_line};
+  }
 
 private:
   ObjectFile *m_obj;
   ConstString m_section_type;
   uint32_t m_next_section_idx;
-  llvm::StringRef m_current_text;
-  llvm::StringRef m_next_text;
+  llvm::StringRef m_section_text;
+  size_t m_current_line;
+  size_t m_next_line;
+
+  void FindNextLine() {
+    m_next_line = m_section_text.find('\n', m_current_line);
+    if (m_next_line != llvm::StringRef::npos) {
+      ++m_next_line;
+      if (m_next_line >= m_section_text.size())
+        m_next_line = llvm::StringRef::npos;
+    }
+  }
 };
-} // namespace
 
-const LineIterator &LineIterator::operator++() {
+SymbolFileBreakpad::LineIterator::LineIterator(ObjectFile &obj,
+                                               Record::Kind section_type,
+                                               Bookmark bookmark)
+    : m_obj(&obj), m_section_type(toString(section_type)),
+      m_next_section_idx(bookmark.section), m_current_line(bookmark.offset) {
+  Section &sect =
+      *obj.GetSectionList()->GetSectionAtIndex(m_next_section_idx - 1);
+  assert(sect.GetName() == m_section_type);
+
+  DataExtractor data;
+  obj.ReadSectionData(&sect, data);
+  m_section_text = toStringRef(data.GetData());
+
+  assert(m_current_line < m_section_text.size());
+  FindNextLine();
+}
+
+const SymbolFileBreakpad::LineIterator &
+SymbolFileBreakpad::LineIterator::operator++() {
   const SectionList &list = *m_obj->GetSectionList();
   size_t num_sections = list.GetNumSections(0);
-  while (m_next_text.empty() && m_next_section_idx < num_sections) {
+  while (m_next_line != llvm::StringRef::npos ||
+         m_next_section_idx < num_sections) {
+    if (m_next_line != llvm::StringRef::npos) {
+      m_current_line = m_next_line;
+      FindNextLine();
+      return *this;
+    }
+
     Section &sect = *list.GetSectionAtIndex(m_next_section_idx++);
     if (sect.GetName() != m_section_type)
       continue;
     DataExtractor data;
     m_obj->ReadSectionData(&sect, data);
-    m_next_text =
-        llvm::StringRef(reinterpret_cast<const char *>(data.GetDataStart()),
-                        data.GetByteSize());
+    m_section_text = toStringRef(data.GetData());
+    m_next_line = 0;
   }
-  std::tie(m_current_text, m_next_text) = m_next_text.split('\n');
+  // We've reached the end.
+  m_current_line = m_next_line;
   return *this;
 }
 
-static llvm::iterator_range<LineIterator> lines(ObjectFile &obj,
-                                                Record::Kind section_type) {
-  return llvm::make_range(LineIterator(obj, section_type), LineIterator(obj));
+llvm::iterator_range<SymbolFileBreakpad::LineIterator>
+SymbolFileBreakpad::lines(Record::Kind section_type) {
+  return llvm::make_range(LineIterator(*m_obj_file, section_type),
+                          LineIterator(*m_obj_file));
+}
+
+namespace {
+// A helper class for constructing the list of support files for a given compile
+// unit.
+class SupportFileMap {
+public:
+  // Given a breakpad file ID, return a file ID to be used in the support files
+  // for this compile unit.
+  size_t operator[](size_t file) {
+    return m_map.try_emplace(file, m_map.size() + 1).first->second;
+  }
+
+  // Construct a FileSpecList containing only the support files relevant for
+  // this compile unit (in the correct order).
+  FileSpecList translate(const FileSpec &cu_spec,
+                         llvm::ArrayRef<FileSpec> all_files);
+
+private:
+  llvm::DenseMap<size_t, size_t> m_map;
+};
+} // namespace
+
+FileSpecList SupportFileMap::translate(const FileSpec &cu_spec,
+                                       llvm::ArrayRef<FileSpec> all_files) {
+  std::vector<FileSpec> result;
+  result.resize(m_map.size() + 1);
+  result[0] = cu_spec;
+  for (const auto &KV : m_map) {
+    if (KV.first < all_files.size())
+      result[KV.second] = all_files[KV.first];
+  }
+  return FileSpecList(std::move(result));
 }
 
 void SymbolFileBreakpad::Initialize() {
@@ -103,17 +182,42 @@ uint32_t SymbolFileBreakpad::CalculateAbilities() {
   if (m_obj_file->GetPluginName() != ObjectFileBreakpad::GetPluginNameStatic())
     return 0;
 
-  return CompileUnits | Functions;
+  return CompileUnits | Functions | LineTables;
 }
 
 uint32_t SymbolFileBreakpad::GetNumCompileUnits() {
-  // TODO
-  return 0;
+  ParseCUData();
+  return m_cu_data->GetSize();
 }
 
 CompUnitSP SymbolFileBreakpad::ParseCompileUnitAtIndex(uint32_t index) {
-  // TODO
-  return nullptr;
+  if (index >= m_cu_data->GetSize())
+    return nullptr;
+
+  CompUnitData &data = m_cu_data->GetEntryRef(index).data;
+
+  ParseFileRecords();
+
+  FileSpec spec;
+
+  // The FileSpec of the compile unit will be the file corresponding to the
+  // first LINE record.
+  LineIterator It(*m_obj_file, Record::Func, data.bookmark), End(*m_obj_file);
+  assert(Record::classify(*It) == Record::Func);
+  ++It; // Skip FUNC record.
+  if (It != End) {
+    auto record = LineRecord::parse(*It);
+    if (record && record->FileNum < m_files->size())
+      spec = (*m_files)[record->FileNum];
+  }
+
+  auto cu_sp = std::make_shared<CompileUnit>(m_obj_file->GetModule(),
+                                             /*user_data*/ nullptr, spec, index,
+                                             eLanguageTypeUnknown,
+                                             /*is_optimized*/ eLazyBoolNo);
+
+  GetSymbolVendor().SetCompileUnitAtIndex(index, cu_sp);
+  return cu_sp;
 }
 
 size_t SymbolFileBreakpad::ParseFunctions(CompileUnit &comp_unit) {
@@ -122,16 +226,63 @@ size_t SymbolFileBreakpad::ParseFunctions(CompileUnit &comp_unit) {
 }
 
 bool SymbolFileBreakpad::ParseLineTable(CompileUnit &comp_unit) {
-  // TODO
-  return 0;
+  CompUnitData &data = m_cu_data->GetEntryRef(comp_unit.GetID()).data;
+
+  if (!data.line_table_up)
+    ParseLineTableAndSupportFiles(comp_unit, data);
+
+  comp_unit.SetLineTable(data.line_table_up.release());
+  return true;
+}
+
+bool SymbolFileBreakpad::ParseSupportFiles(CompileUnit &comp_unit,
+                                           FileSpecList &support_files) {
+  CompUnitData &data = m_cu_data->GetEntryRef(comp_unit.GetID()).data;
+  if (!data.support_files)
+    ParseLineTableAndSupportFiles(comp_unit, data);
+
+  support_files = std::move(*data.support_files);
+  return true;
 }
 
 uint32_t
 SymbolFileBreakpad::ResolveSymbolContext(const Address &so_addr,
                                          SymbolContextItem resolve_scope,
                                          SymbolContext &sc) {
-  // TODO
-  return 0;
+  if (!(resolve_scope & (eSymbolContextCompUnit | eSymbolContextLineEntry)))
+    return 0;
+
+  ParseCUData();
+  uint32_t idx =
+      m_cu_data->FindEntryIndexThatContains(so_addr.GetFileAddress());
+  if (idx == UINT32_MAX)
+    return 0;
+
+  sc.comp_unit = GetSymbolVendor().GetCompileUnitAtIndex(idx).get();
+  SymbolContextItem result = eSymbolContextCompUnit;
+  if (resolve_scope & eSymbolContextLineEntry) {
+    if (sc.comp_unit->GetLineTable()->FindLineEntryByAddress(so_addr,
+                                                             sc.line_entry)) {
+      result |= eSymbolContextLineEntry;
+    }
+  }
+
+  return result;
+}
+
+uint32_t SymbolFileBreakpad::ResolveSymbolContext(
+    const FileSpec &file_spec, uint32_t line, bool check_inlines,
+    lldb::SymbolContextItem resolve_scope, SymbolContextList &sc_list) {
+  if (!(resolve_scope & eSymbolContextCompUnit))
+    return 0;
+
+  uint32_t old_size = sc_list.GetSize();
+  for (size_t i = 0, size = GetNumCompileUnits(); i < size; ++i) {
+    CompileUnit &cu = *GetSymbolVendor().GetCompileUnitAtIndex(i);
+    cu.ResolveSymbolContext(file_spec, line, check_inlines,
+                            /*exact*/ false, resolve_scope, sc_list);
+  }
+  return sc_list.GetSize() - old_size;
 }
 
 uint32_t SymbolFileBreakpad::FindFunctions(
@@ -173,7 +324,7 @@ SymbolFileBreakpad::FindTypes(const std::vector<CompilerContext> &context,
 void SymbolFileBreakpad::AddSymbols(Symtab &symtab) {
   Log *log = GetLogIfAllCategoriesSet(LIBLLDB_LOG_SYMBOLS);
   Module &module = *m_obj_file->GetModule();
-  addr_t base = module.GetObjectFile()->GetBaseAddress().GetFileAddress();
+  addr_t base = GetBaseFileAddress();
   if (base == LLDB_INVALID_ADDRESS) {
     LLDB_LOG(log, "Unable to fetch the base address of object file. Skipping "
                   "symtab population.");
@@ -202,12 +353,12 @@ void SymbolFileBreakpad::AddSymbols(Symtab &symtab) {
         size.hasValue(), /*contains_linker_annotations*/ false, /*flags*/ 0);
   };
 
-  for (llvm::StringRef line : lines(*m_obj_file, Record::Func)) {
+  for (llvm::StringRef line : lines(Record::Func)) {
     if (auto record = FuncRecord::parse(line))
       add_symbol(record->Address, record->Size, record->Name);
   }
 
-  for (llvm::StringRef line : lines(*m_obj_file, Record::Public)) {
+  for (llvm::StringRef line : lines(Record::Public)) {
     if (auto record = PublicRecord::parse(line))
       add_symbol(record->Address, llvm::None, record->Name);
     else
@@ -218,3 +369,108 @@ void SymbolFileBreakpad::AddSymbols(Symtab &symtab) {
     symtab.AddSymbol(std::move(KV.second));
   symtab.CalculateSymbolSizes();
 }
+
+SymbolVendor &SymbolFileBreakpad::GetSymbolVendor() {
+  return *m_obj_file->GetModule()->GetSymbolVendor();
+}
+
+addr_t SymbolFileBreakpad::GetBaseFileAddress() {
+  return m_obj_file->GetModule()
+      ->GetObjectFile()
+      ->GetBaseAddress()
+      .GetFileAddress();
+}
+
+// Parse out all the FILE records from the breakpad file. These will be needed
+// when constructing the support file lists for individual compile units.
+void SymbolFileBreakpad::ParseFileRecords() {
+  if (m_files)
+    return;
+  m_files.emplace();
+
+  Log *log = GetLogIfAllCategoriesSet(LIBLLDB_LOG_SYMBOLS);
+  for (llvm::StringRef line : lines(Record::File)) {
+    auto record = FileRecord::parse(line);
+    if (!record) {
+      LLDB_LOG(log, "Failed to parse: {0}. Skipping record.", line);
+      continue;
+    }
+
+    if (record->Number >= m_files->size())
+      m_files->resize(record->Number + 1);
+    (*m_files)[record->Number] = FileSpec(record->Name);
+  }
+}
+
+void SymbolFileBreakpad::ParseCUData() {
+  if (m_cu_data)
+    return;
+
+  m_cu_data.emplace();
+  Log *log = GetLogIfAllCategoriesSet(LIBLLDB_LOG_SYMBOLS);
+  addr_t base = GetBaseFileAddress();
+  if (base == LLDB_INVALID_ADDRESS) {
+    LLDB_LOG(log, "SymbolFile parsing failed: Unable to fetch the base address "
+                  "of object file.");
+  }
+
+  // We shall create one compile unit for each FUNC record. So, count the number
+  // of FUNC records, and store them in m_cu_data, together with their ranges.
+  for (LineIterator It(*m_obj_file, Record::Func), End(*m_obj_file); It != End;
+       ++It) {
+    if (auto record = FuncRecord::parse(*It)) {
+      m_cu_data->Append(CompUnitMap::Entry(base + record->Address, record->Size,
+                                           CompUnitData(It.GetBookmark())));
+    } else
+      LLDB_LOG(log, "Failed to parse: {0}. Skipping record.", *It);
+  }
+  m_cu_data->Sort();
+}
+
+// Construct the list of support files and line table entries for the given
+// compile unit.
+void SymbolFileBreakpad::ParseLineTableAndSupportFiles(CompileUnit &cu,
+                                                       CompUnitData &data) {
+  addr_t base = GetBaseFileAddress();
+  assert(base != LLDB_INVALID_ADDRESS &&
+         "How did we create compile units without a base address?");
+
+  SupportFileMap map;
+  data.line_table_up = llvm::make_unique<LineTable>(&cu);
+  std::unique_ptr<LineSequence> line_seq_up(
+      data.line_table_up->CreateLineSequenceContainer());
+  llvm::Optional<addr_t> next_addr;
+  auto finish_sequence = [&]() {
+    data.line_table_up->AppendLineEntryToSequence(
+        line_seq_up.get(), *next_addr, /*line*/ 0, /*column*/ 0,
+        /*file_idx*/ 0, /*is_start_of_statement*/ false,
+        /*is_start_of_basic_block*/ false, /*is_prologue_end*/ false,
+        /*is_epilogue_begin*/ false, /*is_terminal_entry*/ true);
+    data.line_table_up->InsertSequence(line_seq_up.get());
+    line_seq_up->Clear();
+  };
+
+  LineIterator It(*m_obj_file, Record::Func, data.bookmark), End(*m_obj_file);
+  assert(Record::classify(*It) == Record::Func);
+  for (++It; It != End; ++It) {
+    auto record = LineRecord::parse(*It);
+    if (!record)
+      break;
+
+    record->Address += base;
+
+    if (next_addr && *next_addr != record->Address) {
+      // Discontiguous entries. Finish off the previous sequence and reset.
+      finish_sequence();
+    }
+    data.line_table_up->AppendLineEntryToSequence(
+        line_seq_up.get(), record->Address, record->LineNum, /*column*/ 0,
+        map[record->FileNum], /*is_start_of_statement*/ true,
+        /*is_start_of_basic_block*/ false, /*is_prologue_end*/ false,
+        /*is_epilogue_begin*/ false, /*is_terminal_entry*/ false);
+    next_addr = record->Address + record->Size;
+  }
+  if (next_addr)
+    finish_sequence();
+  data.support_files = map.translate(cu, *m_files);
+}