SymbolFileBreakpad: Add line table support

[labath]

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.

[labath]

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

150–151 ↗

(On Diff #181252)

Note that here i set file=column=line=0 for the terminal entry, which isn't consistent with the dwarf plugin for instance (it puts there whatever falls out of the state automaton, which most likely means the values from the previous entry). AFAICT, this shouldn't be a problem, because the terminal entry is there to just determine the range of the last real entry.

[clayborg]

So LLDB treats compile units special depending on the inline strategy. Because of this, I outlined some examples of how and why we should create a compile unit per "FUNC" token. Let me know if anything above was unclear

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

119 ↗

(On Diff #181252)

I would vote to make 1 compile unit for each "FUNC". The hard part will be to select the right source file for each function. I would just start by selecting the first line entry for the function. Compile units are expected to give a list of support files, and in this case, you would make a set of files that are in the line entries only. So if you had:

MODULE Linux x86_64 761550E08086333960A9074A9CE2895C0 a.out
INFO CODE_ID E05015768680393360A9074A9CE2895C
FILE 0 /tmp/a.c
FILE 1 /tmp/b.c
FILE 2 /usr/include/foo.h
FUNC b0 10 0 func1
b0 1 1 0
b1 1 2 0
b2 1 2 1
b4 1 3 1
FUNC b0 10 0 func2
b0 1 1 1
b1 1 2 1
b2 1 2 2

We would have a compile unit for "func1" with a cu for "/tmp/a.c" and with support files:
support_file[0] = "/tmp/a.c"
support_file[1] = "/usr/include/foo.h"

We would have a compile unit for "func2" with a cu for "/tmp/b.c" and with support files:

support_file[0] = "/tmp/b.c"
support_file[1] = "/usr/include/foo.h"

The main reason for make individual compile units, is LLDB treats a compile unit specially when settings breakpoints depending on if we ask for inline functions to be set. If we set the following setting:

(lldb) settings set target.inline-breakpoint-strategy never

Then we will check the name of the compile unit to ensure it matches. So if we did:

(lldb) b a.c:12

This would only work if the actual lldb_private::CompileUnit has a FileSpec that matches "a.c".

122 ↗

(On Diff #181252)

return the count of the number of "FUNC" objects

123–125 ↗

(On Diff #181252)

parse a compile unit per function. We might want to cache all "FILE" entries in a list inside the SymbolFileBreakpad so we can easily pull out the FileSpecs when creating each compile unit.

Also, each compile unit's ID can be the line number in the breakpad file to the "FUNC" entry. This allows easy access to each "FUNC" entry in the breakpad file when we are asked to parse more information about it (get compile unit support files, or any parsing of info for a compile unit.

158–179 ↗

(On Diff #181252)

It would be nice to put this parsing code into the lldb_private::breakpad::Line" class I talked about in the other patch?

It would be great if this code looked like:

lldb_private::breakpad::Line bp_line(line);
switch (bp_line.GetToken()) {
  case Token::Func:
    // Create the compile unit and store into cu_sp
    cu_sp = bp_line.CreateCompileUnit();
    break;
  case Token::Line: {
    addr_t address;
    size_t size;
    uint32_t line_num, file_num;
    if (bp_line.ParseLineEntry(address, size, line_num, file_num)) {
      // Discontiguous entries. Finish off the previous sequence and reset.
      if (next_addr && *next_addr != address)
        finish_sequence();
      line_table_up->AppendLineEntryToSequence(
          line_seq_up.get(), address, line_num, 0, file_num, true, false, false, false,  false);
    }

199 ↗

(On Diff #181252)

This function will need to populate support_files for a given FUNC as mentioned above

234 ↗

(On Diff #181252)

We need to search each compile unit to see which compile unit contains the address now.

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h

99 ↗

(On Diff #181252)

Remove whitespace only change

[labath]

I think I understand what you mean. I'll try to refactor this to create a compile unit for each function.

[labath]

It took me a while to get back to this, but I believe this version now does what
we want. It creates a compile unit for each function. The compile units are
created as soon as the symbol file is initialized (it's needed to get the number
of compile units). The global list of support files is also parsed at this time
(needed to get the compile unit name). The list of support files and line tables
is created lazily for those compile units that need them.

A new element here is the "bookmark" class, which allows us to efficiently go
back the to place where the line tables for a given function/compile unit are
defined and parse those.

I added a couple of new tests to exercise handling of odd or broken minidump
files.

Let me know what you think.

[labath]

Greg, what do you think about the new approach in this patch?

[clayborg]

I like the way you did the compile units and the line tables and support file list. It would be nice to change this to do things more lazily. Right now we are parsing all compile unit data into CompUnitData structures and then passing their info along to the lldb_private::CompileUnit when we need to. We can be more lazy, see inlined comments.

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

279 ↗

(On Diff #184103)

Do we need to iterate over the file multiple times here? We do it once here, and then once on line 260.

281–300 ↗

(On Diff #184103)

Seems like we should just populate the m_compile_units data with address range to character file offset here? When we are asked to create a compile unit, we do this work by going to the "lldb_private::CompileUnit::GetID()" which will return the file offset and we just head there and start parsing?

314 ↗

(On Diff #184103)

This seems like where we would do the heavy parsing code that are in the initialize object function. .Get the character file offset from m_compile_units and just parse what we need here? It will cause less work for us in the initialize object call then and we can be lazier

326 ↗

(On Diff #184103)

From the compile unit, if GetID() returns the character file offset to the FUNC or first LINE, then we don't need the preparsed CompUnitData? We can just parse the line table here if and only if we need to

332 ↗

(On Diff #184103)

Ditto above

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h

151–154 ↗

(On Diff #184103)

Why do we need more than just a file character offset here?

182–188 ↗

(On Diff #184103)

Seems like if we just pick the file character offset of the function or the function's line entries as the lldb_private::CompileUnit user ID (lldb::user_id_t) then we don't really need this class? We just create the compile unit as a lldb_private::CompileUnit and our symbol file parser will fill in the rest? Any reason we need this CompUnitData class?

212 ↗

(On Diff #184103)

Could this just be:

using CompUnitMap = RangeDataVector<lldb::addr_t, lldb::addr_t, lldb::offset_t>;

Where offset_t is the character fie offset for the first line of the FUNC entry? Any reason to use CompUnitData instead of just creating lldb_private::CompileUnit objects?

214 ↗

(On Diff #184103)

Use FileSpecList?

[labath]

Thanks for the review Greg. See my responses inline. I'm going to try incorporating the changes tomorrow.

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

279 ↗

(On Diff #184103)

The two loops iterate over different parts of the file. The first one goes through the FILE records, and this one does the FUNC records. So the iteration here is efficient because we already know where different kinds of records are located in the file.

(of course, to figure out where these records are located, we've had to go through it once already (in ObjectFileBreakpad), so we still have to make two passes over this data in general. However, that is pretty much unavoidable if we want to do lazy (i.e. random access) into the file as it doesn't have any kind of index to start with.)

281–300 ↗

(On Diff #184103)

I think I could avoid creating the CompileUnit object here. However, I will still need to do the parsing here, as I will need to figure out the number of compile units first (best I might be able to achieve is to delay this until GetNumCompileUnits() time).

326 ↗

(On Diff #184103)

That is pretty much what happens here. CompUnitData construct the line table (almost) lazily. It doesn't preparse. The reason I have this indirection, is that the creation of line tables is coupled with the creation of the support file list:

• in order to build the line table, I (obviously) need to go through the LINE records
• however, I also need to go through the LINE records in order to build the CU file list, because I need to know what files are actually used in this "CU"

It seemed like a good idea to me to avoid parsing the LINE records twice. So what I've done is that on the first call to (ReleaseLineTable|ReleaseSupportFiles), CompUnitData will parse both things. Then, the second call will return the already parsed data. That seems like a good tradeoff to me as these two items are generally used together (one is fairly useless without the other).

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h

151–154 ↗

(On Diff #184103)

That's because ObjectFileBreakpad breaks down the file into sections (so all FILE records would go into one section, PUBLIC records into another, etc.). This means that we don't need any "bookmarks" when we want to jump straight to the PUBLIC records for instance, but it does mean we need two coordinates (section, offset) when we want to jump to a specific record within a section.

182–188 ↗

(On Diff #184103)

I'd like the keep to enable the CompUnitData for conjugated parsing of line tables and support files. I think I can get rid of the compile unit field inside it, but that would mean relying on the SymbolVendor to conjure up the CompUnitSP when I need it, which is a bit of an odd dependency. (I need to conjure up the pointer from somewhere in the ResolveSymbolContext functions).

214 ↗

(On Diff #184103)

FileSpecList doesn't have the resize method. I use that to implement parsing of the FILE records, since the file records theoretically don't have to come in order, so I just resize the vector to fit the largest number I've encountered.

[lemo]

The latest version looks good to me. Please update the description (it still says it uses the one CU per symbols file)

include/lldb/Core/FileSpecList.h

72 ↗

(On Diff #184103)

nit: if you have move assignment-operator also add the move constructor

[labath]

Tried to make parsing as lazy as possible. GetNumSections() will count the
number of FUNC records, but will not create CompileUnit objects. FILE records
will be parsed when we create the first compile unit. The support files and line
tables will be parsed when the first of them is requested for a given CU.

I've removed the CU shared pointer from the CompUnitData structure. Instead, I go through the symbol vendor to fetch the CU SP.

Added the move constructor for FileSpecList.

Please take another look.

[clayborg]

Just bounds check "index" in parse compile unit and this is good to go

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

196 ↗

(On Diff #185533)

Validate "index" first? We will crash if someone iterates over too many CUs?

[labath]

Add a bounds check to the GetCompileUnitAtIndex method

lldb/trunk/include/lldb/Core/FileSpecList.h

 public:
   //------------------------------------------------------------------
   /// Default constructor.
   ///
   /// Initialize this object with an empty file list.
   //------------------------------------------------------------------
   FileSpecList();
 
-  //------------------------------------------------------------------
   /// Copy constructor.
-  ///
-  /// Initialize this object with a copy of the file list from \a rhs.
-  ///
-  /// @param[in] rhs
-  ///     A const reference to another file list object.
-  //------------------------------------------------------------------
-  FileSpecList(const FileSpecList &rhs);
+  FileSpecList(const FileSpecList &rhs) = default;
+
+  /// Move constructor
+  FileSpecList(FileSpecList &&rhs) = default;
+
+  /// Initialize this object from a vector of FileSpecs
+  FileSpecList(std::vector<FileSpec> &&rhs) : m_files(std::move(rhs)) {}
 
   //------------------------------------------------------------------
   /// Destructor.
   //------------------------------------------------------------------
   ~FileSpecList();
 
   //------------------------------------------------------------------
   /// Assignment operator.
   ///
   /// Replace the file list in this object with the file list from \a rhs.
   ///
   /// @param[in] rhs
   ///     A file list object to copy.
   ///
   /// @return
   ///     A const reference to this object.
   //------------------------------------------------------------------
-  const FileSpecList &operator=(const FileSpecList &rhs);
+  FileSpecList &operator=(const FileSpecList &rhs) = default;
+
+  /// Move-assignment operator.
+  FileSpecList &operator=(FileSpecList &&rhs) = default;
 
   //------------------------------------------------------------------
   /// Append a FileSpec object to the list.
   ///
   /// Appends \a file to the end of the file list.
   ///
   /// @param[in] file
   ///     A new file to append to this file list.

lldb/trunk/include/lldb/Core/RangeMap.h

#endif
   }
 
   Entry *GetMutableEntryAtIndex(size_t i) {
     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
   }
 
   // Clients must ensure that "i" is a valid index prior to calling this
   // function
+  Entry &GetEntryRef(size_t i) { return m_entries[i]; }
   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
 
   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
     return lhs.GetRangeBase() < rhs.GetRangeBase();
   }
 
   uint32_t FindEntryIndexThatContains(B addr) const {
     const Entry *entry = FindEntryThatContains(addr);

lldb/trunk/lit/SymbolFile/Breakpad/Inputs/line-table-discontinuous-file-ids.syms

+MODULE Linux x86_64 761550E08086333960A9074A9CE2895C0 a.out
+INFO CODE_ID E05015768680393360A9074A9CE2895C
+FILE 1 /tmp/a.c
+FILE 3 /tmp/c.c
+FUNC b0 10 0 func
+b0 1 1 1
+b1 1 2 1
+b2 1 2 3

lldb/trunk/lit/SymbolFile/Breakpad/Inputs/line-table-edgecases.syms

+MODULE Linux x86_64 761550E08086333960A9074A9CE2895C0 a.out
+INFO CODE_ID E05015768680393360A9074A9CE2895C
+FILE 0 /tmp/a.c
+a0 1 1 0
+FUNC b0 10 0 func
+FUNC c0 10 0 func2
+c0 2 2 0

lldb/trunk/lit/SymbolFile/Breakpad/Inputs/line-table-missing-file.syms

+MODULE Linux x86_64 761550E08086333960A9074A9CE2895C0 a.out
+INFO CODE_ID E05015768680393360A9074A9CE2895C
+FILE 0 /tmp/a.c
+FUNC b0 10 0 func
+b0 1 1 0
+b1 1 2 0
+b2 1 2 1

lldb/trunk/lit/SymbolFile/Breakpad/Inputs/line-table.syms

+MODULE Linux x86_64 761550E08086333960A9074A9CE2895C0 a.out
+INFO CODE_ID E05015768680393360A9074A9CE2895C
+FILE 0 /tmp/a.c
+FILE 1 /tmp/c.c
+FILE 2 /tmp/d.c
+FUNC b0 10 0 func
+b0 1 1 0
+b1 1 2 0
+b2 1 2 1
+b4 1 3 1
+FUNC c0 10 0 func2
+c0 2 1 1
+c2 2 2 0
+FUNC d0 10 0 func3
+d0 2 1 2
+FUNC e0 10 0 func4
+e0 2 2 2

lldb/trunk/lit/SymbolFile/Breakpad/line-table-discontinuous-file-ids.test

+# Test that we handle files which has gaps in the FILE record IDs.
+
+# RUN: yaml2obj %S/Inputs/basic-elf.yaml > %T/line-table-discontinuous-file-ids.out
+# RUN: %lldb %T/line-table-discontinuous-file-ids.out \
+# RUN:   -o "target symbols add -s line-table-discontinuous-file-ids.out %S/Inputs/line-table-discontinuous-file-ids.syms" \
+# RUN:   -s %s -o exit | FileCheck %s
+
+image dump line-table a.c
+# CHECK-LABEL: Line table for /tmp/a.c
+# CHECK-NEXT: 0x00000000004000b0: /tmp/a.c:1
+# CHECK-NEXT: 0x00000000004000b1: /tmp/a.c:2
+# CHECK-NEXT: 0x00000000004000b2: /tmp/c.c:2
+# CHECK-NEXT: 0x00000000004000b3: 

lldb/trunk/lit/SymbolFile/Breakpad/line-table-edgecases.test

+# Test handling of breakpad files with some unusual or erroneous constructs. The
+# input contains a LINE record which does not belong to any function as well as
+# a FUNC record without any LINE records.
+
+# RUN: yaml2obj %S/Inputs/basic-elf.yaml > %T/line-table-edgecases.out
+# RUN: %lldb %T/line-table-edgecases.out \
+# RUN:   -o "target symbols add -s line-table-edgecases.out %S/Inputs/line-table-edgecases.syms" \
+# RUN:   -s %s -o exit | FileCheck %s
+
+# Test that line table for func2 was parsed properly:
+image dump line-table a.c
+# CHECK-LABEL: Line table for /tmp/a.c
+# CHECK-NEXT: 0x00000000004000c0: /tmp/a.c:2
+# CHECK-NEXT: 0x00000000004000c2: 
+# CHECK-EMPTY: 
+
+# Looking up an address inside func should still work even if it does not result
+# in a line entry.
+image lookup -a 0x4000b2 -v
+# CHECK-LABEL: image lookup -a 0x4000b2 -v
+# CHECK: Summary: line-table-edgecases.out`func + 2

lldb/trunk/lit/SymbolFile/Breakpad/line-table-missing-file.test

+# Test that we do something reasonable if a LINE record references a
+# non-existing FILE record.
+# Right now, "something reasonable" means creating a line entry with an empty
+# file.
+
+# RUN: yaml2obj %S/Inputs/basic-elf.yaml > %T/line-table-missing-file.out
+# RUN: %lldb %T/line-table-missing-file.out \
+# RUN:   -o "target symbols add -s line-table-missing-file.out %S/Inputs/line-table-missing-file.syms" \
+# RUN:   -s %s -o exit | FileCheck %s
+
+image dump line-table a.c
+# CHECK-LABEL: Line table for /tmp/a.c
+# CHECK-NEXT: 0x00000000004000b0: /tmp/a.c:1
+# CHECK-NEXT: 0x00000000004000b1: /tmp/a.c:2
+# CHECK-NEXT: 0x00000000004000b2: :2
+# CHECK-NEXT: 0x00000000004000b3: 
+# CHECK-EMPTY: 

lldb/trunk/lit/SymbolFile/Breakpad/line-table.test

+# RUN: yaml2obj %S/Inputs/basic-elf.yaml > %T/line-table.out
+# RUN: %lldb %T/line-table.out -o "target symbols add -s line-table.out %S/Inputs/line-table.syms" \
+# RUN:   -s %s -o exit | FileCheck %s
+
+# We create a compile unit for each function. The compile unit name is the first
+# line table entry in that function.
+# This symbol file contains a single function in the "compile unit" a.c. This
+# function has two line table sequences.
+image dump line-table a.c
+# CHECK-LABEL: Line table for /tmp/a.c
+# CHECK-NEXT: 0x00000000004000b0: /tmp/a.c:1
+# CHECK-NEXT: 0x00000000004000b1: /tmp/a.c:2
+# CHECK-NEXT: 0x00000000004000b2: /tmp/c.c:2
+# CHECK-NEXT: 0x00000000004000b3: 
+# CHECK-EMPTY: 
+# CHECK-NEXT: 0x00000000004000b4: /tmp/c.c:3
+# CHECK-NEXT: 0x00000000004000b5: 
+# CHECK-EMPTY: 
+
+# Single compile unit for c.c with a single line sequence.
+image dump line-table c.c
+# CHECK-LABEL: Line table for /tmp/c.c
+# CHECK-NEXT: 0x00000000004000c0: /tmp/c.c:1
+# CHECK-NEXT: 0x00000000004000c2: /tmp/a.c:2
+# CHECK-NEXT: 0x00000000004000c4: 
+# CHECK-EMPTY: 
+
+# There are two compile units called "d.c". Hence, two line tables.
+image dump line-table d.c
+# CHECK-LABEL: Line table for /tmp/d.c
+# CHECK-NEXT: 0x00000000004000d0: /tmp/d.c:1
+# CHECK-NEXT: 0x00000000004000d2: 
+# CHECK-EMPTY: 
+# CHECK-LABEL: Line table for /tmp/d.c
+# CHECK-NEXT: 0x00000000004000e0: /tmp/d.c:2
+# CHECK-NEXT: 0x00000000004000e2: 
+# CHECK-EMPTY: 
+
+image lookup -a 0x4000b2 -v
+# CHECK-LABEL: image lookup -a 0x4000b2 -v
+# CHECK: Summary: line-table.out`func + 2
+
+breakpoint set -f c.c -l 2
+# CHECK-LABEL: breakpoint set -f c.c -l 2
+# CHECK: Breakpoint 1: where = line-table.out`func + 2, address = 0x00000000004000b2

lldb/trunk/source/Core/FileSpecList.cpp

 
 #include <stdint.h>
 
 using namespace lldb_private;
 using namespace std;
 
 FileSpecList::FileSpecList() : m_files() {}
 
-FileSpecList::FileSpecList(const FileSpecList &rhs) = default;
-
 FileSpecList::~FileSpecList() = default;
 
 //------------------------------------------------------------------
-// Assignment operator
-//------------------------------------------------------------------
-const FileSpecList &FileSpecList::operator=(const FileSpecList &rhs) {
-  if (this != &rhs)
-    m_files = rhs.m_files;
-  return *this;
-}
-
-//------------------------------------------------------------------
 // Append the "file_spec" to the end of the file spec list.
 //------------------------------------------------------------------
 void FileSpecList::Append(const FileSpec &file_spec) {
   m_files.push_back(file_spec);
 }
 
 //------------------------------------------------------------------
 // Only append the "file_spec" if this list doesn't already contain it.

lldb/trunk/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h

 //===-- SymbolFileBreakpad.h ------------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_PLUGINS_SYMBOLFILE_BREAKPAD_SYMBOLFILEBREAKPAD_H
 #define LLDB_PLUGINS_SYMBOLFILE_BREAKPAD_SYMBOLFILEBREAKPAD_H
 
+#include "Plugins/ObjectFile/Breakpad/BreakpadRecords.h"
+#include "lldb/Core/FileSpecList.h"
+#include "lldb/Symbol/LineTable.h"
 #include "lldb/Symbol/SymbolFile.h"
 
 namespace lldb_private {
 
 namespace breakpad {
 
 class SymbolFileBreakpad : public SymbolFile {
 public:
public:
 
   size_t ParseFunctions(CompileUnit &comp_unit) override;
 
   bool ParseLineTable(CompileUnit &comp_unit) override;
 
   bool ParseDebugMacros(CompileUnit &comp_unit) override { return false; }
 
   bool ParseSupportFiles(CompileUnit &comp_unit,
-                         FileSpecList &support_files) override {
-    return false;
-  }
+                         FileSpecList &support_files) override;
   size_t ParseTypes(CompileUnit &cu) override { return 0; }
 
   bool
   ParseImportedModules(const SymbolContext &sc,
                        std::vector<ConstString> &imported_modules) override {
     return false;
   }
 
llvm::Optional<ArrayInfo> GetDynamicArrayInfoForUID(
     return llvm::None;
   }
 
   bool CompleteType(CompilerType &compiler_type) override { return false; }
   uint32_t ResolveSymbolContext(const Address &so_addr,
                                 lldb::SymbolContextItem resolve_scope,
                                 SymbolContext &sc) override;
 
+  uint32_t ResolveSymbolContext(const FileSpec &file_spec, uint32_t line,
+                                bool check_inlines,
+                                lldb::SymbolContextItem resolve_scope,
+                                SymbolContextList &sc_list) override;
+
   size_t GetTypes(SymbolContextScope *sc_scope, lldb::TypeClass type_mask,
                   TypeList &type_list) override {
     return 0;
   }
 
   uint32_t FindFunctions(const ConstString &name,
                          const CompilerDeclContext *parent_decl_ctx,
                          lldb::FunctionNameType name_type_mask,
public:
   }
 
   void AddSymbols(Symtab &symtab) override;
 
   ConstString GetPluginName() override { return GetPluginNameStatic(); }
   uint32_t GetPluginVersion() override { return 1; }
 
 private:
+  // A class representing a position in the breakpad file. Useful for
+  // remembering the position so we can go back to it later and parse more data.
+  // Can be converted to/from a LineIterator, but it has a much smaller memory
+  // footprint.
+  struct Bookmark {
+    uint32_t section;
+    size_t offset;
+  };
+
+  // At iterator class for simplifying algorithms reading data from the breakpad
+  // file. It iterates over all records (lines) in the sections of a given type.
+  // It also supports saving a specific position (via the GetBookmark() method)
+  // and then resuming from it afterwards.
+  class LineIterator;
+
+  // Return an iterator range for all records in the given object file of the
+  // given type.
+  llvm::iterator_range<LineIterator> lines(Record::Kind section_type);
+
+  // Breakpad files do not contain sufficient information to correctly
+  // reconstruct compile units. The approach chosen here is to treat each
+  // function as a compile unit. The compile unit name is the name if the first
+  // line entry belonging to this function.
+  // This class is our internal representation of a compile unit. It stores the
+  // CompileUnit object and a bookmark pointing to the FUNC record of the
+  // compile unit function. It also lazily construct the list of support files
+  // and line table entries for the compile unit, when these are needed.
+  class CompUnitData {
+  public:
+    CompUnitData(Bookmark bookmark) : bookmark(bookmark) {}
+
+    CompUnitData() = default;
+    CompUnitData(const CompUnitData &rhs) : bookmark(rhs.bookmark) {}
+    CompUnitData &operator=(const CompUnitData &rhs) {
+      bookmark = rhs.bookmark;
+      support_files.reset();
+      line_table_up.reset();
+      return *this;
+    }
+    friend bool operator<(const CompUnitData &lhs, const CompUnitData &rhs) {
+      return std::tie(lhs.bookmark.section, lhs.bookmark.offset) <
+             std::tie(rhs.bookmark.section, rhs.bookmark.offset);
+    }
+
+    Bookmark bookmark;
+    llvm::Optional<FileSpecList> support_files;
+    std::unique_ptr<LineTable> line_table_up;
+
+  };
+
+  SymbolVendor &GetSymbolVendor();
+  lldb::addr_t GetBaseFileAddress();
+  void ParseFileRecords();
+  void ParseCUData();
+  void ParseLineTableAndSupportFiles(CompileUnit &cu, CompUnitData &data);
+
+  using CompUnitMap = RangeDataVector<lldb::addr_t, lldb::addr_t, CompUnitData>;
+
+  llvm::Optional<std::vector<FileSpec>> m_files;
+  llvm::Optional<CompUnitMap> m_cu_data;
 };
 
 } // namespace breakpad
 } // namespace lldb_private
 
 #endif

lldb/trunk/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

 //===-- SymbolFileBreakpad.cpp ----------------------------------*- C++ -*-===//
 //
 // 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 "Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h"
 #include "Plugins/ObjectFile/Breakpad/BreakpadRecords.h"
 #include "Plugins/ObjectFile/Breakpad/ObjectFileBreakpad.h"
 #include "lldb/Core/Module.h"
 #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"
 
 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() {
   PluginManager::RegisterPlugin(GetPluginNameStatic(),
                                 GetPluginDescriptionStatic(), CreateInstance,
                                 DebuggerInitialize);
 }
 
 void SymbolFileBreakpad::Terminate() {
   PluginManager::UnregisterPlugin(CreateInstance);
 }
 
 ConstString SymbolFileBreakpad::GetPluginNameStatic() {
   static ConstString g_name("breakpad");
   return g_name;
 }
 
 uint32_t SymbolFileBreakpad::CalculateAbilities() {
   if (!m_obj_file)
     return 0;
   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
+  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) {
   // TODO
   return 0;
 }
 
 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
+  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(
     const ConstString &name, const CompilerDeclContext *parent_decl_ctx,
     FunctionNameType name_type_mask, bool include_inlines, bool append,
     SymbolContextList &sc_list) {
   // TODO
   if (!append)
SymbolFileBreakpad::FindTypes(const std::vector<CompilerContext> &context,
   if (!append)
     types.Clear();
   return types.GetSize();
 }
 
 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.");
     return;
   }
 
   const SectionList &list = *module.GetSectionList();
   llvm::DenseMap<addr_t, Symbol> symbols;
symbols.try_emplace(
         address, /*symID*/ 0, Mangled(name, /*is_mangled*/ false),
         eSymbolTypeCode, /*is_global*/ true, /*is_debug*/ false,
         /*is_trampoline*/ false, /*is_artificial*/ false,
         AddressRange(section_sp, address - section_sp->GetFileAddress(),
                      size.getValueOr(0)),
         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
       LLDB_LOG(log, "Failed to parse: {0}. Skipping record.", line);
   }
 
   for (auto &KV : symbols)
     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);
+}