[lldb] Make symbol list output from `image dump symtab` not depend on internal ordering of DenseMap

[teemperor]

Summary

image dump symtab seems to output the symbols in whatever order they appear in the DenseMap
that is used to filter out symbols with non-unique addresses. As DenseMap is a hash map this order
can change at any time so the output of this command is pretty unstable. This
also causes the Breakpad/symtab.test to fail with enabled reverse iteration (which reverses the DenseMap
order to find issues like this).

This patch makes the DenseMap a std::vector and uses a separate DenseSet to do the address filtering.
The output order is now dependent on the order in which the symbols are read (which should be
deterministic). It might also avoid a bit of work as all the work for creating the Symbol constructor
parameters is only done when we can actually emplace a new Symbol.

[teemperor]

This should also avoid changing the test all the time when someone touches one of the symbols (as in D68533 )

[labath]

Looks good.

In D87036#2252346, @teemperor wrote:

This should also avoid changing the test all the time when someone touches one of the symbols (as in D68533 )

AFAICT, that patch modified the test because it actually introduced a new symbol -- the order of the existing symbols was not changed.

[teemperor]

In D87036#2254108, @labath wrote:

Looks good.

In D87036#2252346, @teemperor wrote:

This should also avoid changing the test all the time when someone touches one of the symbols (as in D68533 )

AFAICT, that patch modified the test because it actually introduced a new symbol -- the order of the existing symbols was not changed.

Oh true, somehow phab is just highlighting the function names as if they have changed. My bad!

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

void SymbolFileBreakpad::AddSymbols(Symtab &symtab) {
   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;
+  llvm::DenseSet<addr_t> found_symbol_addresses;
+  std::vector<Symbol> symbols;
   auto add_symbol = [&](addr_t address, llvm::Optional<addr_t> size,
                         llvm::StringRef name) {
     address += base;
     SectionSP section_sp = list.FindSectionContainingFileAddress(address);
     if (!section_sp) {
       LLDB_LOG(log,
                "Ignoring symbol {0}, whose address ({1}) is outside of the "
                "object file. Mismatched symbol file?",
                name, address);
       return;
     }
-    symbols.try_emplace(
-        address, /*symID*/ 0, Mangled(name), eSymbolTypeCode,
+    // Keep track of what addresses were already added so far and only add
+    // the symbol with the first address.
+    if (!found_symbol_addresses.insert(address).second)
+      return;
+    symbols.emplace_back(
+        /*symID*/ 0, Mangled(name), 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(Record::Func)) {
     if (auto record = FuncRecord::parse(line))
       add_symbol(record->Address, record->Size, record->Name);
   }
 
   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));
+  for (Symbol &symbol : symbols)
+    symtab.AddSymbol(std::move(symbol));
   symtab.CalculateSymbolSizes();
 }
 
 llvm::Expected<lldb::addr_t>
 SymbolFileBreakpad::GetParameterStackSize(Symbol &symbol) {
   ParseUnwindData();
   if (auto *entry = m_unwind_data->win.FindEntryThatContains(
           symbol.GetAddress().GetFileAddress())) {

lldb/test/Shell/SymbolFile/Breakpad/symtab.test

 # RUN: yaml2obj %S/Inputs/basic-elf.yaml -o %T/symtab.out
 # RUN: %lldb %T/symtab.out -o "target symbols add -s symtab.out %S/Inputs/symtab.syms" \
 # RUN:   -s %s | FileCheck %s
 
 # CHECK-LABEL: (lldb) image dump symtab symtab.out
 # CHECK: Symtab, file = {{.*}}symtab.out, num_symbols = 5:
 # CHECK: Index   UserID DSX Type            File Address/Value Load Address       Size               Flags      Name
 # CHECK: [    0]      0  SX Code            0x0000000000400000                    0x00000000000000b0 0x00000000 ___lldb_unnamed_symbol{{[0-9]*}}$$symtab.out
-# CHECK: [    1]      0   X Code            0x00000000004000c0                    0x0000000000000010 0x00000000 f2
-# CHECK: [    2]      0   X Code            0x00000000004000d0                    0x0000000000000022 0x00000000 _start
-# CHECK: [    3]      0   X Code            0x00000000004000a0                    0x000000000000000d 0x00000000 func_only
-# CHECK: [    4]      0   X Code            0x00000000004000b0                    0x000000000000000c 0x00000000 f1_func
+# CHECK: [    1]      0   X Code            0x00000000004000b0                    0x000000000000000c 0x00000000 f1_func
+# CHECK: [    2]      0   X Code            0x00000000004000a0                    0x000000000000000d 0x00000000 func_only
+# CHECK: [    3]      0   X Code            0x00000000004000c0                    0x0000000000000010 0x00000000 f2
+# CHECK: [    4]      0   X Code            0x00000000004000d0                    0x0000000000000022 0x00000000 _start
 
 # CHECK-LABEL: (lldb) image lookup -a 0x4000b0 -v
 # CHECK: Address: symtab.out[0x00000000004000b0] (symtab.out.PT_LOAD[0]..text2 + 0)
 # CHECK: Symbol: id = {0x00000000}, range = [0x00000000004000b0-0x00000000004000bc), name="f1_func"
 
 # CHECK-LABEL: (lldb) image lookup -n f2 -v
 # CHECK: Address: symtab.out[0x00000000004000c0] (symtab.out.PT_LOAD[0]..text2 + 16)
 # CHECK: Symbol: id = {0x00000000}, range = [0x00000000004000c0-0x00000000004000d0), name="f2"
 
 image dump symtab symtab.out
 image lookup -a 0x4000b0 -v
 image lookup -n f2 -v
 exit