[lldb][NFC] Refactor name to index maps in Symtab

[bulbazord]

Summary

The various maps in Symtab lead to some repetative code. This should
improve the situation somewhat.

[teemperor]

Only have some comments about the way FindFunctionSymbols is now implemented, but otherwise this LGTM.

lldb/include/lldb/Symbol/Symtab.h

177

/// Maps function names to symbol indices (grouped by FunctionNameTypes)
and maybe let's call this variable:
m_name_to_symbol_indizes

lldb/source/Symbol/Symtab.cpp

1031

Those large maps seem rather expensive to copy around. Could you just make this a for loop over the few types we care about? Then we can delete all the duplicated code.

for (lldb::FunctionNameType type : {lldb::eFunctionNameTypeBase, lldb::eFunctionNameTypeMethod, lldb::eFunctionNameTypeSelector}) {
  if (name_type_mask & type) {
    auto &map = GetFunctypeMap(type);
    [search map]
  }
}

[bulbazord]

Address feedback

[bulbazord]

Remove unused line of code that I forgot to remove previously

[teemperor]

Some small rename I forgot to point out, but LGTM modulo that rename. Thanks for cleaning this up!

lldb/include/lldb/Symbol/Symtab.h

184

GetNameToSymbolIndexMap might be more accurate now (I should have pointed out when changing the variable name).

[bulbazord]

Rename function :)

lldb/include/lldb/Symbol/Symtab.h

 //===-- Symtab.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_SYMBOL_SYMTAB_H
 #define LLDB_SYMBOL_SYMTAB_H
 
 #include "lldb/Core/UniqueCStringMap.h"
 #include "lldb/Symbol/Symbol.h"
 #include "lldb/Utility/RangeMap.h"
 #include "lldb/lldb-private.h"
+#include <map>
 #include <mutex>
 #include <vector>
 
 namespace lldb_private {
 
 class Symtab {
 public:
   typedef std::vector<uint32_t> IndexCollection;
typedef RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t, 0,
                           FileRangeToIndexMapCompare>
       FileRangeToIndexMap;
   void InitNameIndexes();
   void InitAddressIndexes();
 
   ObjectFile *m_objfile;
   collection m_symbols;
   FileRangeToIndexMap m_file_addr_to_index;
-  UniqueCStringMap<uint32_t> m_name_to_index;
-  UniqueCStringMap<uint32_t> m_basename_to_index;
-  UniqueCStringMap<uint32_t> m_method_to_index;
-  UniqueCStringMap<uint32_t> m_selector_to_index;
+  std::map<lldb::FunctionNameType, UniqueCStringMap<uint32_t>>
+      m_functype_to_map;
   mutable std::recursive_mutex
       m_mutex; // Provide thread safety for this symbol table
   bool m_file_addr_to_index_computed : 1, m_name_indexes_computed : 1;
 
 private:
+  UniqueCStringMap<uint32_t> &GetFunctypeMap(lldb::FunctionNameType type) {
+    auto map = m_functype_to_map.find(type);
+    assert(map != m_functype_to_map.end());
+    return map->second;
+  }
   bool CheckSymbolAtIndex(size_t idx, Debug symbol_debug_type,
                           Visibility symbol_visibility) const {
     switch (symbol_debug_type) {
     case eDebugNo:
       if (m_symbols[idx].IsDebug())
         return false;
       break;
 

lldb/source/Symbol/Symtab.cpp

 //===-- Symtab.cpp --------------------------------------------------------===//
 //
 // 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 <map>
 #include <set>
 
 #include "Plugins/Language/ObjC/ObjCLanguage.h"
 
 #include "lldb/Core/Module.h"
 #include "lldb/Core/RichManglingContext.h"
 #include "lldb/Core/Section.h"
 #include "lldb/Symbol/ObjectFile.h"
 #include "lldb/Symbol/Symbol.h"
 #include "lldb/Symbol/SymbolContext.h"
 #include "lldb/Symbol/Symtab.h"
 #include "lldb/Utility/RegularExpression.h"
 #include "lldb/Utility/Stream.h"
 #include "lldb/Utility/Timer.h"
 
 #include "llvm/ADT/StringRef.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
 Symtab::Symtab(ObjectFile *objfile)
     : m_objfile(objfile), m_symbols(), m_file_addr_to_index(*this),
-      m_name_to_index(), m_mutex(), m_file_addr_to_index_computed(false),
-      m_name_indexes_computed(false) {}
+      m_functype_to_map(), m_mutex(), m_file_addr_to_index_computed(false),
+      m_name_indexes_computed(false) {
+  m_functype_to_map.emplace(std::make_pair(lldb::eFunctionNameTypeNone,
+                                           UniqueCStringMap<uint32_t>()));
+  m_functype_to_map.emplace(std::make_pair(lldb::eFunctionNameTypeBase,
+                                           UniqueCStringMap<uint32_t>()));
+  m_functype_to_map.emplace(std::make_pair(lldb::eFunctionNameTypeMethod,
+                                           UniqueCStringMap<uint32_t>()));
+  m_functype_to_map.emplace(std::make_pair(lldb::eFunctionNameTypeSelector,
+                                           UniqueCStringMap<uint32_t>()));
+}
 
 Symtab::~Symtab() {}
 
 void Symtab::Reserve(size_t count) {
   // Clients should grab the mutex from this symbol table and lock it manually
   // when calling this function to avoid performance issues.
   m_symbols.reserve(count);
 }
 
 Symbol *Symtab::Resize(size_t count) {
   // Clients should grab the mutex from this symbol table and lock it manually
   // when calling this function to avoid performance issues.
   m_symbols.resize(count);
   return m_symbols.empty() ? nullptr : &m_symbols[0];
 }
 
 uint32_t Symtab::AddSymbol(const Symbol &symbol) {
   // Clients should grab the mutex from this symbol table and lock it manually
   // when calling this function to avoid performance issues.
   uint32_t symbol_idx = m_symbols.size();
-  m_name_to_index.Clear();
+  auto &name_to_index = GetFunctypeMap(lldb::eFunctionNameTypeNone);
+  name_to_index.Clear();
   m_file_addr_to_index.Clear();
   m_symbols.push_back(symbol);
   m_file_addr_to_index_computed = false;
   m_name_indexes_computed = false;
   return symbol_idx;
 }
 
 size_t Symtab::GetNumSymbols() const {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   return m_symbols.size();
 }
 
 void Symtab::SectionFileAddressesChanged() {
-  m_name_to_index.Clear();
+  auto &name_to_index = GetFunctypeMap(lldb::eFunctionNameTypeNone);
+  name_to_index.Clear();
   m_file_addr_to_index_computed = false;
 }
 
 void Symtab::Dump(Stream *s, Target *target, SortOrder sort_order,
                   Mangled::NamePreference name_preference) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 
   //    s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
static bool lldb_skip_name(llvm::StringRef mangled,
   llvm_unreachable("unknown scheme!");
 }
 
 void Symtab::InitNameIndexes() {
   // Protected function, no need to lock mutex...
   if (!m_name_indexes_computed) {
     m_name_indexes_computed = true;
     LLDB_SCOPED_TIMER();
+
+    auto &name_to_index = GetFunctypeMap(lldb::eFunctionNameTypeNone);
+    auto &basename_to_index = GetFunctypeMap(lldb::eFunctionNameTypeBase);
+    auto &method_to_index = GetFunctypeMap(lldb::eFunctionNameTypeMethod);
+    auto &selector_to_index = GetFunctypeMap(lldb::eFunctionNameTypeSelector);
     // Create the name index vector to be able to quickly search by name
     const size_t num_symbols = m_symbols.size();
-    m_name_to_index.Reserve(num_symbols);
+    name_to_index.Reserve(num_symbols);
 
     // The "const char *" in "class_contexts" and backlog::value_type::second
     // must come from a ConstString::GetCString()
     std::set<const char *> class_contexts;
     std::vector<std::pair<NameToIndexMap::Entry, const char *>> backlog;
     backlog.reserve(num_symbols / 2);
 
     // Instantiation of the demangler is expensive, so better use a single one
     // for all entries during batch processing.
     RichManglingContext rmc;
     for (uint32_t value = 0; value < num_symbols; ++value) {
       Symbol *symbol = &m_symbols[value];
 
       // Don't let trampolines get into the lookup by name map If we ever need
       // the trampoline symbols to be searchable by name we can remove this and
       // then possibly add a new bool to any of the Symtab functions that
       // lookup symbols by name to indicate if they want trampolines.
       if (symbol->IsTrampoline())
         continue;
 
       // If the symbol's name string matched a Mangled::ManglingScheme, it is
       // stored in the mangled field.
       Mangled &mangled = symbol->GetMangled();
       if (ConstString name = mangled.GetMangledName()) {
-        m_name_to_index.Append(name, value);
+        name_to_index.Append(name, value);
 
         if (symbol->ContainsLinkerAnnotations()) {
           // If the symbol has linker annotations, also add the version without
           // the annotations.
           ConstString stripped = ConstString(
               m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef()));
-          m_name_to_index.Append(stripped, value);
+          name_to_index.Append(stripped, value);
         }
 
         const SymbolType type = symbol->GetType();
         if (type == eSymbolTypeCode || type == eSymbolTypeResolver) {
           if (mangled.DemangleWithRichManglingInfo(rmc, lldb_skip_name))
             RegisterMangledNameEntry(value, class_contexts, backlog, rmc);
         }
       }
 
       // Symbol name strings that didn't match a Mangled::ManglingScheme, are
       // stored in the demangled field.
       if (ConstString name = mangled.GetDemangledName()) {
-        m_name_to_index.Append(name, value);
+        name_to_index.Append(name, value);
 
         if (symbol->ContainsLinkerAnnotations()) {
           // If the symbol has linker annotations, also add the version without
           // the annotations.
           name = ConstString(
               m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef()));
-          m_name_to_index.Append(name, value);
+          name_to_index.Append(name, value);
         }
 
         // If the demangled name turns out to be an ObjC name, and is a category
         // name, add the version without categories to the index too.
         ObjCLanguage::MethodName objc_method(name.GetStringRef(), true);
         if (objc_method.IsValid(true)) {
-          m_selector_to_index.Append(objc_method.GetSelector(), value);
+          selector_to_index.Append(objc_method.GetSelector(), value);
 
           if (ConstString objc_method_no_category =
                   objc_method.GetFullNameWithoutCategory(true))
-            m_name_to_index.Append(objc_method_no_category, value);
+            name_to_index.Append(objc_method_no_category, value);
         }
       }
     }
 
     for (const auto &record : backlog) {
       RegisterBacklogEntry(record.first, record.second, class_contexts);
     }
 
-    m_name_to_index.Sort();
-    m_name_to_index.SizeToFit();
-    m_selector_to_index.Sort();
-    m_selector_to_index.SizeToFit();
-    m_basename_to_index.Sort();
-    m_basename_to_index.SizeToFit();
-    m_method_to_index.Sort();
-    m_method_to_index.SizeToFit();
+    name_to_index.Sort();
+    name_to_index.SizeToFit();
+    selector_to_index.Sort();
+    selector_to_index.SizeToFit();
+    basename_to_index.Sort();
+    basename_to_index.SizeToFit();
+    method_to_index.Sort();
+    method_to_index.SizeToFit();
   }
 }
 
 void Symtab::RegisterMangledNameEntry(
     uint32_t value, std::set<const char *> &class_contexts,
     std::vector<std::pair<NameToIndexMap::Entry, const char *>> &backlog,
     RichManglingContext &rmc) {
   // Only register functions that have a base name.
   rmc.ParseFunctionBaseName();
   llvm::StringRef base_name = rmc.GetBufferRef();
   if (base_name.empty())
     return;
 
   // The base name will be our entry's name.
   NameToIndexMap::Entry entry(ConstString(base_name), value);
 
   rmc.ParseFunctionDeclContextName();
   llvm::StringRef decl_context = rmc.GetBufferRef();
 
   // Register functions with no context.
   if (decl_context.empty()) {
     // This has to be a basename
-    m_basename_to_index.Append(entry);
+    auto &basename_to_index = GetFunctypeMap(lldb::eFunctionNameTypeBase);
+    basename_to_index.Append(entry);
     // If there is no context (no namespaces or class scopes that come before
     // the function name) then this also could be a fullname.
-    m_name_to_index.Append(entry);
+    auto &name_to_index = GetFunctypeMap(lldb::eFunctionNameTypeNone);
+    name_to_index.Append(entry);
     return;
   }
 
   // Make sure we have a pool-string pointer and see if we already know the
   // context name.
   const char *decl_context_ccstr = ConstString(decl_context).GetCString();
   auto it = class_contexts.find(decl_context_ccstr);
 
+  auto &method_to_index = GetFunctypeMap(lldb::eFunctionNameTypeMethod);
   // Register constructors and destructors. They are methods and create
   // declaration contexts.
   if (rmc.IsCtorOrDtor()) {
-    m_method_to_index.Append(entry);
+    method_to_index.Append(entry);
     if (it == class_contexts.end())
       class_contexts.insert(it, decl_context_ccstr);
     return;
   }
 
   // Register regular methods with a known declaration context.
   if (it != class_contexts.end()) {
-    m_method_to_index.Append(entry);
+    method_to_index.Append(entry);
     return;
   }
 
   // Regular methods in unknown declaration contexts are put to the backlog. We
   // will revisit them once we processed all remaining symbols.
   backlog.push_back(std::make_pair(entry, decl_context_ccstr));
 }
 
 void Symtab::RegisterBacklogEntry(
     const NameToIndexMap::Entry &entry, const char *decl_context,
     const std::set<const char *> &class_contexts) {
+  auto &method_to_index = GetFunctypeMap(lldb::eFunctionNameTypeMethod);
   auto it = class_contexts.find(decl_context);
   if (it != class_contexts.end()) {
-    m_method_to_index.Append(entry);
+    method_to_index.Append(entry);
   } else {
     // If we got here, we have something that had a context (was inside
     // a namespace or class) yet we don't know the entry
-    m_method_to_index.Append(entry);
-    m_basename_to_index.Append(entry);
+    method_to_index.Append(entry);
+    auto &basename_to_index = GetFunctypeMap(lldb::eFunctionNameTypeBase);
+    basename_to_index.Append(entry);
   }
 }
 
 void Symtab::PreloadSymbols() {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   InitNameIndexes();
 }
 
uint32_t Symtab::AppendSymbolIndexesWithName(ConstString symbol_name,
                                              std::vector<uint32_t> &indexes) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 
   LLDB_SCOPED_TIMER();
   if (symbol_name) {
     if (!m_name_indexes_computed)
       InitNameIndexes();
 
-    return m_name_to_index.GetValues(symbol_name, indexes);
+    auto &name_to_index = GetFunctypeMap(lldb::eFunctionNameTypeNone);
+    return name_to_index.GetValues(symbol_name, indexes);
   }
   return 0;
 }
 
 uint32_t Symtab::AppendSymbolIndexesWithName(ConstString symbol_name,
                                              Debug symbol_debug_type,
                                              Visibility symbol_visibility,
                                              std::vector<uint32_t> &indexes) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 
   LLDB_SCOPED_TIMER();
   if (symbol_name) {
     const size_t old_size = indexes.size();
     if (!m_name_indexes_computed)
       InitNameIndexes();
 
+    auto &name_to_index = GetFunctypeMap(lldb::eFunctionNameTypeNone);
     std::vector<uint32_t> all_name_indexes;
     const size_t name_match_count =
-        m_name_to_index.GetValues(symbol_name, all_name_indexes);
+        name_to_index.GetValues(symbol_name, all_name_indexes);
     for (size_t i = 0; i < name_match_count; ++i) {
       if (CheckSymbolAtIndex(all_name_indexes[i], symbol_debug_type,
                              symbol_visibility))
         indexes.push_back(all_name_indexes[i]);
     }
     return indexes.size() - old_size;
   }
   return 0;
for (size_t i = 0; i < num_indices; i++) {
         sc_list.AppendIfUnique(sc, merge_symbol_into_function);
     }
   }
 }
 
 void Symtab::FindFunctionSymbols(ConstString name, uint32_t name_type_mask,
                                  SymbolContextList &sc_list) {
   std::vector<uint32_t> symbol_indexes;
+  std::vector<UniqueCStringMap<uint32_t>> maps_to_search;
 
   // eFunctionNameTypeAuto should be pre-resolved by a call to
   // Module::LookupInfo::LookupInfo()
   assert((name_type_mask & eFunctionNameTypeAuto) == 0);
 
   if (name_type_mask & (eFunctionNameTypeBase | eFunctionNameTypeFull)) {
     std::vector<uint32_t> temp_symbol_indexes;
     FindAllSymbolsWithNameAndType(name, eSymbolTypeAny, temp_symbol_indexes);
if (temp_symbol_indexes_size > 0) {
             break;
           }
         }
       }
     }
   }
 
   if (name_type_mask & eFunctionNameTypeBase) {
-    // From mangled names we can't tell what is a basename and what is a method
-    // name, so we just treat them the same
-    if (!m_name_indexes_computed)
-      InitNameIndexes();
-
-    if (!m_basename_to_index.IsEmpty()) {
-      const UniqueCStringMap<uint32_t>::Entry *match;
-      for (match = m_basename_to_index.FindFirstValueForName(name);
-           match != nullptr;
-           match = m_basename_to_index.FindNextValueForName(match)) {
-        symbol_indexes.push_back(match->value);
-      }
-    }
+    maps_to_search.push_back(GetFunctypeMap(lldb::eFunctionNameTypeBase));
   }
 
   if (name_type_mask & eFunctionNameTypeMethod) {
-    if (!m_name_indexes_computed)
-      InitNameIndexes();
-
-    if (!m_method_to_index.IsEmpty()) {
-      const UniqueCStringMap<uint32_t>::Entry *match;
-      for (match = m_method_to_index.FindFirstValueForName(name);
-           match != nullptr;
-           match = m_method_to_index.FindNextValueForName(match)) {
-        symbol_indexes.push_back(match->value);
-      }
-    }
+    maps_to_search.push_back(GetFunctypeMap(lldb::eFunctionNameTypeMethod));
   }
 
   if (name_type_mask & eFunctionNameTypeSelector) {
-    if (!m_name_indexes_computed)
+    maps_to_search.push_back(GetFunctypeMap(lldb::eFunctionNameTypeSelector));
+  }
+
+  if (!maps_to_search.empty()) {
+    if (!m_name_indexes_computed) {
       InitNameIndexes();
+    }
 
-    if (!m_selector_to_index.IsEmpty()) {
+    for (auto map_to_search : maps_to_search) {
+      if (!map_to_search.IsEmpty()) {
         const UniqueCStringMap<uint32_t>::Entry *match;
-      for (match = m_selector_to_index.FindFirstValueForName(name);
+        for (match = map_to_search.FindFirstValueForName(name);
              match != nullptr;
-           match = m_selector_to_index.FindNextValueForName(match)) {
+             match = map_to_search.FindNextValueForName(match)) {
           symbol_indexes.push_back(match->value);
         }
       }
     }
+  }
 
   if (!symbol_indexes.empty()) {
     llvm::sort(symbol_indexes.begin(), symbol_indexes.end());
     symbol_indexes.erase(
         std::unique(symbol_indexes.begin(), symbol_indexes.end()),
         symbol_indexes.end());
     SymbolIndicesToSymbolContextList(symbol_indexes, sc_list);
   }