Make UniqueCStringMap work with non-default-constructible types and other improvements/cleanups

[labath]

Summary

The motivation for this was me wanting to make the validity of dwarf
DIERefs explicit (via llvm::Optional<DIERef>). This meant that the class
would no longer have a default constructor. As the DIERef was being
stored in a UniqueCStringMap, this meant that this container (like all
standard containers) needed to work with non-default-constructible types
too.

This part is achieved by removing die default constructors for the map
entry types, and providing appropriate comparison overloads so that we
can search for map entries without constructing a dummy entry. While
doing that, I took the opportunity to modernize the code, and add some
tests. Functions that were completely unused are deleted.

This required also some changes in the Symtab code, as it was default
constructing map entries, which was not impossible even though its
value type was default-constructible. Technically, these changes could
be avoided with some SFINAE on the entry type, but I felt that the code
is cleaner this way anyway.

[clayborg]

include/lldb/Core/UniqueCStringMap.h

87 ↗

(On Diff #204537)

What benefits does llvm::lower_bound offer here? With std::lower_bound and std::upper_bound you can write a comparison static functions that take a "const T &" on one side and a ConstString on the other. Lower bound will use one flavor ("static bool operator <(const T&, ConstString);") and upper_bound will use the other ("static bool operator <(ConstString, const T&);"). No need to specify a Compare() object. So the code would be:

T Find(ConstString unique_cstr, T fail_value) const {
  const_iterator end = m_map.end();
  const_iterator pos = std::lower_bound(m_map.begin(), end, unique_cstr);
  if (pos != end && pos->cstring == unique_cstr)
    return pos->value;
  return fail_value;
}

[labath]

include/lldb/Core/UniqueCStringMap.h

87 ↗

(On Diff #204537)

The only benefit of using llvm lower/upper bound is that operates on ranges -- you don't need to pass the begin/end iterator pairs, you can just pass the container. Under the hood, it just delegates to the std version.

The issue of using the compare object is completely orthogonal to that. I could define appropriate operator<s on the Entry class directly, and thereby avoid the need for comparison objects. The reason I did not do that is because the Entry class is public (and other parts of the code use and manipulate it), and having a (ConstString, Entry) operator< on the Entry class would mean exposing it to the outside world.. It's not a strong reason, it seemed to me like this is the kind of thing that users outside of this class should not be able to do implicitly/accidentally, so I tried to hide it a bit.

[stella.stamenova]

It looks like this broke the Windows bot. I am no longer receiving emails when the bot fails (as bot owner I used to always get the failure emails), so I am assuming for some reason notifications aren't working correctly.

Can you have a look at the failure?

http://lab.llvm.org:8011/buildslaves/win-py3-buildbot

[labath]

Thanks for the heads up. This should be fixed with r363653.

[stella.stamenova]

Thanks!

lldb/trunk/include/lldb/Core/UniqueCStringMap.h

 //
 // This map is useful for mapping unique C string names to values of type T.
 // Each "const char *" name added must be unique for a given
 // C string value. ConstString::GetCString() can provide such strings.
 // Any other string table that has guaranteed unique values can also be used.
 template <typename T> class UniqueCStringMap {
 public:
   struct Entry {
-    Entry() {}
-
-    Entry(ConstString cstr) : cstring(cstr), value() {}
-
     Entry(ConstString cstr, const T &v) : cstring(cstr), value(v) {}
 
-    // This is only for uniqueness, not lexicographical ordering, so we can
-    // just compare pointers.
-    bool operator<(const Entry &rhs) const {
-      return cstring.GetCString() < rhs.cstring.GetCString();
+    friend bool operator<(const Entry &lhs, const Entry &rhs) {
+      return Compare()(lhs, rhs);
     }
 
     ConstString cstring;
     T value;
   };
 
   // Call this function multiple times to add a bunch of entries to this map,
   // then later call UniqueCStringMap<T>::Sort() before doing any searches by
   // name.
   void Append(ConstString unique_cstr, const T &value) {
     m_map.push_back(typename UniqueCStringMap<T>::Entry(unique_cstr, value));
   }
 
   void Append(const Entry &e) { m_map.push_back(e); }
 
   void Clear() { m_map.clear(); }
 
-  // Call this function to always keep the map sorted when putting entries into
-  // the map.
-  void Insert(ConstString unique_cstr, const T &value) {
-    typename UniqueCStringMap<T>::Entry e(unique_cstr, value);
-    m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e);
-  }
-
-  void Insert(const Entry &e) {
-    m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e);
-  }
-
   // Get an entries by index in a variety of forms.
   //
   // The caller is responsible for ensuring that the collection does not change
   // during while using the returned values.
   bool GetValueAtIndex(uint32_t idx, T &value) const {
     if (idx < m_map.size()) {
       value = m_map[idx].value;
       return true;
public:
 
   // Find the value for the unique string in the map.
   //
   // Return the value for \a unique_cstr if one is found, return \a fail_value
   // otherwise. This method works well for simple type
   // T values and only if there is a sensible failure value that can
   // be returned and that won't match any existing values.
   T Find(ConstString unique_cstr, T fail_value) const {
-    Entry search_entry(unique_cstr);
-    const_iterator end = m_map.end();
-    const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry);
-    if (pos != end) {
-      if (pos->cstring == unique_cstr)
-        return pos->value;
-    }
+    auto pos = llvm::lower_bound(m_map, unique_cstr, Compare());
+    if (pos != m_map.end() && pos->cstring == unique_cstr)
     return fail_value;
   }
 
   // Get a pointer to the first entry that matches "name". nullptr will be
   // returned if there is no entry that matches "name".
   //
   // The caller is responsible for ensuring that the collection does not change
   // during while using the returned pointer.
   const Entry *FindFirstValueForName(ConstString unique_cstr) const {
-    Entry search_entry(unique_cstr);
-    const_iterator end = m_map.end();
-    const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry);
-    if (pos != end && pos->cstring == unique_cstr)
+    auto pos = llvm::lower_bound(m_map, unique_cstr, Compare());
+    if (pos != m_map.end() && pos->cstring == unique_cstr)
       return &(*pos);
     return nullptr;
   }
 
   // Get a pointer to the next entry that matches "name" from a previously
   // returned Entry pointer. nullptr will be returned if there is no subsequent
   // entry that matches "name".
   //
if (!m_map.empty()) {
       }
     }
     return nullptr;
   }
 
   size_t GetValues(ConstString unique_cstr, std::vector<T> &values) const {
     const size_t start_size = values.size();
 
-    Entry search_entry(unique_cstr);
-    const_iterator pos, end = m_map.end();
-    for (pos = std::lower_bound(m_map.begin(), end, search_entry); pos != end;
-         ++pos) {
-      if (pos->cstring == unique_cstr)
-        values.push_back(pos->value);
-      else
-        break;
-    }
+    for (const Entry &entry : llvm::make_range(std::equal_range(
+             m_map.begin(), m_map.end(), unique_cstr, Compare())))
+      values.push_back(entry.value);
 
     return values.size() - start_size;
   }
 
   size_t GetValues(const RegularExpression &regex,
                    std::vector<T> &values) const {
     const size_t start_size = values.size();
 
public:
   // exact size needed as part of the finalization of the string map.
   void SizeToFit() {
     if (m_map.size() < m_map.capacity()) {
       collection temp(m_map.begin(), m_map.end());
       m_map.swap(temp);
     }
   }
 
-  size_t Erase(ConstString unique_cstr) {
-    size_t num_removed = 0;
-    Entry search_entry(unique_cstr);
-    iterator end = m_map.end();
-    iterator begin = m_map.begin();
-    iterator lower_pos = std::lower_bound(begin, end, search_entry);
-    if (lower_pos != end) {
-      if (lower_pos->cstring == unique_cstr) {
-        iterator upper_pos = std::upper_bound(lower_pos, end, search_entry);
-        if (lower_pos == upper_pos) {
-          m_map.erase(lower_pos);
-          num_removed = 1;
-        } else {
-          num_removed = std::distance(lower_pos, upper_pos);
-          m_map.erase(lower_pos, upper_pos);
-        }
-      }
+protected:
+  struct Compare {
+    bool operator()(const Entry &lhs, const Entry &rhs) {
+      return operator()(lhs.cstring, rhs.cstring);
+
+    bool operator()(const Entry &lhs, ConstString rhs) {
+      return operator()(lhs.cstring, rhs);
     }
-    return num_removed;
+
+    bool operator()(ConstString lhs, const Entry &rhs) {
+      return operator()(lhs, rhs.cstring);
     }
 
-protected:
+    // This is only for uniqueness, not lexicographical ordering, so we can
+    // just compare pointers. *However*, comparing pointers from different
+    // allocations is UB, so we need compare their integral values instead.
+    bool operator()(ConstString lhs, ConstString rhs) {
+      return uintptr_t(lhs.GetCString()) < uintptr_t(rhs.GetCString());
+    }
+  };
   typedef std::vector<Entry> collection;
   typedef typename collection::iterator iterator;
   typedef typename collection::const_iterator const_iterator;
   collection m_map;
 };
 
 } // namespace lldb_private
 
 #endif // liblldb_UniqueCStringMap_h_

lldb/trunk/include/lldb/Symbol/Symtab.h

bool CheckSymbolAtIndex(size_t idx, Debug symbol_debug_type,
     }
     return false;
   }
 
   void SymbolIndicesToSymbolContextList(std::vector<uint32_t> &symbol_indexes,
                                         SymbolContextList &sc_list);
 
   void RegisterMangledNameEntry(
-      NameToIndexMap::Entry &entry, std::set<const char *> &class_contexts,
+      uint32_t value, std::set<const char *> &class_contexts,
       std::vector<std::pair<NameToIndexMap::Entry, const char *>> &backlog,
       RichManglingContext &rmc);
 
   void RegisterBacklogEntry(const NameToIndexMap::Entry &entry,
                             const char *decl_context,
                             const std::set<const char *> &class_contexts);
 
   DISALLOW_COPY_AND_ASSIGN(Symtab);
 };
 
 } // namespace lldb_private
 
 #endif // liblldb_Symtab_h_

lldb/trunk/source/Symbol/Symtab.cpp

#endif
     // 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;
-    NameToIndexMap::Entry entry;
-
-    for (entry.value = 0; entry.value < num_symbols; ++entry.value) {
-      Symbol *symbol = &m_symbols[entry.value];
+    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();
-      entry.cstring = mangled.GetMangledName();
-      if (entry.cstring) {
-        m_name_to_index.Append(entry);
+      if (ConstString name = mangled.GetMangledName()) {
+        m_name_to_index.Append(name, value);
 
         if (symbol->ContainsLinkerAnnotations()) {
           // If the symbol has linker annotations, also add the version without
           // the annotations.
-          entry.cstring = ConstString(m_objfile->StripLinkerSymbolAnnotations(
-                                        entry.cstring.GetStringRef()));
-          m_name_to_index.Append(entry);
+          ConstString stripped = ConstString(
+              m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef()));
+          m_name_to_index.Append(stripped, value);
         }
 
         const SymbolType type = symbol->GetType();
         if (type == eSymbolTypeCode || type == eSymbolTypeResolver) {
           if (mangled.DemangleWithRichManglingInfo(rmc, lldb_skip_name))
-            RegisterMangledNameEntry(entry, class_contexts, backlog, rmc);
+            RegisterMangledNameEntry(value, class_contexts, backlog, rmc);
         }
       }
 
       // Symbol name strings that didn't match a Mangled::ManglingScheme, are
       // stored in the demangled field.
-      entry.cstring = mangled.GetDemangledName(symbol->GetLanguage());
-      if (entry.cstring) {
-        m_name_to_index.Append(entry);
+      if (ConstString name = mangled.GetDemangledName(symbol->GetLanguage())) {
+        m_name_to_index.Append(name, value);
 
         if (symbol->ContainsLinkerAnnotations()) {
           // If the symbol has linker annotations, also add the version without
           // the annotations.
-          entry.cstring = ConstString(m_objfile->StripLinkerSymbolAnnotations(
-                                        entry.cstring.GetStringRef()));
-          m_name_to_index.Append(entry);
-        }
+          name = ConstString(
+              m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef()));
+          m_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(entry.cstring.GetStringRef(), true);
+        ObjCLanguage::MethodName objc_method(name.GetStringRef(), true);
         if (objc_method.IsValid(true)) {
-        entry.cstring = objc_method.GetSelector();
-        m_selector_to_index.Append(entry);
+          m_selector_to_index.Append(objc_method.GetSelector(), value);
 
-        ConstString objc_method_no_category(
-            objc_method.GetFullNameWithoutCategory(true));
-        if (objc_method_no_category) {
-          entry.cstring = objc_method_no_category;
-          m_name_to_index.Append(entry);
+          if (ConstString objc_method_no_category =
+                  objc_method.GetFullNameWithoutCategory(true))
+            m_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();
   }
 }
 
 void Symtab::RegisterMangledNameEntry(
-    NameToIndexMap::Entry &entry, std::set<const char *> &class_contexts,
+    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.
-  entry.cstring = ConstString(base_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);
void Symtab::AppendSymbolNamesToMap(const IndexCollection &indexes,
                                     bool add_demangled, bool add_mangled,
                                     NameToIndexMap &name_to_index_map) const {
   if (add_demangled || add_mangled) {
     static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
     Timer scoped_timer(func_cat, "%s", LLVM_PRETTY_FUNCTION);
     std::lock_guard<std::recursive_mutex> guard(m_mutex);
 
     // Create the name index vector to be able to quickly search by name
-    NameToIndexMap::Entry entry;
     const size_t num_indexes = indexes.size();
     for (size_t i = 0; i < num_indexes; ++i) {
-      entry.value = indexes[i];
+      uint32_t value = indexes[i];
       assert(i < m_symbols.size());
-      const Symbol *symbol = &m_symbols[entry.value];
+      const Symbol *symbol = &m_symbols[value];
 
       const Mangled &mangled = symbol->GetMangled();
       if (add_demangled) {
-        entry.cstring = mangled.GetDemangledName(symbol->GetLanguage());
-        if (entry.cstring)
-          name_to_index_map.Append(entry);
+        if (ConstString name = mangled.GetDemangledName(symbol->GetLanguage()))
+          name_to_index_map.Append(name, value);
       }
 
       if (add_mangled) {
-        entry.cstring = mangled.GetMangledName();
-        if (entry.cstring)
-          name_to_index_map.Append(entry);
+        if (ConstString name = mangled.GetMangledName())
+          name_to_index_map.Append(name, value);
       }
     }
   }
 }
 
 uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
                                              std::vector<uint32_t> &indexes,
                                              uint32_t start_idx,

lldb/trunk/unittests/Core/CMakeLists.txt

 add_lldb_unittest(LLDBCoreTests
   MangledTest.cpp
   RichManglingContextTest.cpp
   StreamCallbackTest.cpp
+  UniqueCStringMapTest.cpp
 
   LINK_LIBS
     lldbCore
     lldbHost
     lldbSymbol
     lldbPluginObjectFileELF
     lldbPluginSymbolVendorELF
     lldbUtilityHelpers

lldb/trunk/unittests/Core/UniqueCStringMapTest.cpp

+//===-- UniqueCStringMapTest.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 "lldb/Core/UniqueCStringMap.h"
+#include "gmock/gmock.h"
+
+using namespace lldb_private;
+
+namespace {
+struct NoDefault {
+  int x;
+
+  NoDefault(int x) : x(x) {}
+  NoDefault() = delete;
+
+  friend bool operator==(NoDefault lhs, NoDefault rhs) {
+    return lhs.x == rhs.x;
+  }
+
+  friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                                       NoDefault x) {
+    return OS << "NoDefault{" << x.x << "}";
+  }
+};
+} // namespace
+
+TEST(UniqueCStringMap, NoDefaultConstructor) {
+  using MapT = UniqueCStringMap<NoDefault>;
+  using EntryT = MapT::Entry;
+
+  MapT Map;
+  ConstString Foo("foo"), Bar("bar");
+
+  Map.Append(Foo, NoDefault(42));
+  EXPECT_THAT(Map.Find(Foo, NoDefault(47)), NoDefault(42));
+  EXPECT_THAT(Map.Find(Bar, NoDefault(47)), NoDefault(47));
+  EXPECT_THAT(Map.FindFirstValueForName(Foo),
+              testing::Pointee(testing::Field(&EntryT::value, NoDefault(42))));
+  EXPECT_THAT(Map.FindFirstValueForName(Bar), nullptr);
+
+  std::vector<NoDefault> Values;
+  EXPECT_THAT(Map.GetValues(Foo, Values), 1);
+  EXPECT_THAT(Values, testing::ElementsAre(NoDefault(42)));
+
+  Values.clear();
+  EXPECT_THAT(Map.GetValues(Bar, Values), 0);
+  EXPECT_THAT(Values, testing::IsEmpty());
+}