[lldb] add new overload for SymbolFile::FindTypes that accepts a scope

[lassefolger]

Summary

Searching for fully qualified types in a SymbolFile can be inefficient
if it contains many types with the same basename. This is because the
SymbolFile does not offer and an interface to search for qualified
types. To get qualified typed you first need to query all types with the
same basename and then filter based on the scope.

This change introduces a new overload that accepts a scope which the
SymbolFile implementations can use to return filtered by scope.

This change also includes an implementation for DWARF that uses this
scope for filtering. All other implementation use the overload without
scope and filter afterwards.

The motivation for this change is a performance issue when findings
types in targets that contain many types (>1000) with the same basename.
In the two scenarios I tested this change on, the change improves the
time it takes to find a time from 86s -> 12s and from 12s -> 2s,
respectively.

[lassefolger]

rebased on nfc

[werat]

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

2460

Can GetQualifiedName return NULL string?

2460–2461

We can skip this check altogether if the scope is empty.

2461

There's no need to calculate length on every iteration.

Also you can make sc an llvm::StringRef and do something like StringRef(s).startswith(sc).

[shafik]

Is there a specific use case that motivated this feature?

[lassefolger]

In D114627#3162109, @shafik wrote:

Is there a specific use case that motivated this feature?

The motivation is performance. If there are many (>1000) types with the same base name this implementation performs much better than the current implementation.
This is mostly important for the first access (because later ones use the caches results). In our scenarios it reduced the time for the first access from 86s to 6s and from 12s to 2s. And the access for subsequest accesses from 0.15 to 0.08 and 0.12 to 0.06.

The primary reason is that Type::GetQualifiedName is executed for every type with the same basename when the types are filtered at the end. This triggers type completion each type which is very expensive.

I'm still working on this commit.

[lassefolger]

rebased on nfc and completed implementation to expose function in API

[lassefolger]

lldb/source/Symbol/SymbolFile.cpp

147

I need to change this. This was correct in the first iteration but is no longer correct in the current iteration of this change.

[werat]

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

2451

nit: maybe call it scope_ref?

2462

llvm::StringRef(storage) is slightly more efficient here than llvm::StringRef(qn). The latter uses strlen in the constructor to calculate the length of the source string.

[lassefolger]

fixed comment

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

2462

I wasn't sure about the semantics of die.GetQualifiedName().
It does not document whether it's guaranteed that storage contains the results. FWIW, the current implementation does that.
I changed it to use the storage.

[lassefolger]

rebase patch

[werat]

Looks good to me, I'm going to land it soon unless there are objections from other reviewers.

[JDevlieghere]

lldb/include/lldb/Symbol/SymbolFile.h

237–239

241

Does the scope need to be a ConstString? These strings are kept in memory forever and we should be mindful of their use. Could this a StringRef?

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

2456

Can this go into if (has_scope) {?

[shafik]

LGTM after addressing Jonas's comments.

[lassefolger]

update according to comments

lldb/include/lldb/Symbol/SymbolFile.h

241

I don't think it has to be a ConstString. I used a ConstString for consistency with name.
Let me change it to StringRef

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

2456

I don't mind putting it in there but thought reusing the same storage would avoid allocations.
Moving it into the function will lead to an allocation each time the function is called and the qualified name is too long for small string optimization.

[clayborg]

Sorry I am late to making comments on this patch.

This patch wants to add "llvm::StringRef scope" to the FindTypes calls, but this is what "const CompilerDeclContext &parent_decl_ctx" is actually for. If "parent_decl_ctx" is set, it is a declaration context that each type must exist in. So the CompilerDeclContext might be something like "namespace foo" and it might have a parent decl context of "namespace bar". This is currently how filtering types that exist in a decl context works.

The "scope" seems redundant in light of this no? Also, a string based "scope" isn't accurate enough to correctly identify the exact scoping of a type as "a:🅱️:some_type" might be "namespace a -> class b -> some_type" or "namespace a -> namespace b -> some_type".

The one difficult thing about this is currently the "parent_decl_ctx" that is a parameter only works if the decl context comes from the current module. Each module creates types using its own TypeSystem subclass. Those types are vended as CompilerType objects which contain the TypeSystem pointer and a void * for the type. This allows each TypeSystem to create types. For clang compiled code we use lldb_private::TypeSystemClang and we create types as types in a clang::ASTContext. We can also specify declaration contexts by using CompilerDeclContext objects. Each CompilerDeclContext object has a "TypeSystem *" and a "void *" inside of it. Each expression makes its own TypeSystem as well, and one for each expression and one in the target. It should be possible to fix the issue of needing the compiler decl context to come from the current module by having the code that compares the decl context make by using:

ConstString CompilerDeclContext::GetScopeQualifiedName() const;

Or we can modify the CompilerDeclContext class to get the current name:

ConstString CompilerDeclContext::GetName() const;

And then also add an API to return an enumeration for the kind of the declaration context (Namespace, Class, Struct, Union, etc).

[lassefolger]

In D114627#3306300, @clayborg wrote:

Sorry I am late to making comments on this patch.

This patch wants to add "llvm::StringRef scope" to the FindTypes calls, but this is what "const CompilerDeclContext &parent_decl_ctx" is actually for. If "parent_decl_ctx" is set, it is a declaration context that each type must exist in. So the CompilerDeclContext might be something like "namespace foo" and it might have a parent decl context of "namespace bar". This is currently how filtering types that exist in a decl context works.

The "scope" seems redundant in light of this no? Also, a string based "scope" isn't accurate enough to correctly identify the exact scoping of a type as "a:🅱️:some_type" might be "namespace a -> class b -> some_type" or "namespace a -> namespace b -> some_type".

The one difficult thing about this is currently the "parent_decl_ctx" that is a parameter only works if the decl context comes from the current module. Each module creates types using its own TypeSystem subclass. Those types are vended as CompilerType objects which contain the TypeSystem pointer and a void * for the type. This allows each TypeSystem to create types. For clang compiled code we use lldb_private::TypeSystemClang and we create types as types in a clang::ASTContext. We can also specify declaration contexts by using CompilerDeclContext objects. Each CompilerDeclContext object has a "TypeSystem *" and a "void *" inside of it. Each expression makes its own TypeSystem as well, and one for each expression and one in the target. It should be possible to fix the issue of needing the compiler decl context to come from the current module by having the code that compares the decl context make by using:

ConstString CompilerDeclContext::GetScopeQualifiedName() const;

Or we can modify the CompilerDeclContext class to get the current name:

ConstString CompilerDeclContext::GetName() const;

And then also add an API to return an enumeration for the kind of the declaration context (Namespace, Class, Struct, Union, etc).

The idea is that the scope is a hint which implementations can use to improve the performance.
However, I see that this redundancy might be confusing. I have not looked to much into the ComplierDeclContext.
I'll try to take another look later this week.

FWIW there has been a discussion between werat@ and teemperor@ about this on Discord about this topic in general. The results was to use a string rather than a CompilerDeclContext. Although the discussion didn't go into detail why this is:
https://discord.com/channels/636084430946959380/636732809708306432/849218944581632001

[lassefolger]

I'm still planning to look into this just couldn't find the time this week and the last. Sorry for the delay.

[lassefolger]

Sorry for the very late response.

I looked into using the CompilerDeclContext().

This does not work in this case because the context is not set in this specific use case and I'm not sure if it case be set.
It is initialized with an invalid context when the function is called.

The entry point in our use case is lldb::SBTarget::FindTypes(const char *). A stacktrace looks like this:
SymbolFileDWARF::FindTypes()
lldb_private::Module::FindTypes_Impl()
lldb_private::ModuleList::FindTypes()
lldb::SBTarget::FindTypes()

Given that the input is just a C-string, I'm not sure how to derive a CompilerDeclContext() from that.
What we are trying to optimize is a call like:
lldb.target.FindTypes("Some::Namespace::Type")

lldb/include/lldb/Core/Module.h

private:
   Module(); // Only used internally by CreateJITModule ()
 
   void FindTypes_Impl(
       ConstString name, const CompilerDeclContext &parent_decl_ctx,
       size_t max_matches,
       llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
       TypeMap &types);
 
+  void FindTypes_Impl(
+      ConstString name, llvm::StringRef scope,
+      const CompilerDeclContext &parent_decl_ctx, size_t max_matches,
+      llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
+      TypeMap &types);
+
   Module(const Module &) = delete;
   const Module &operator=(const Module &) = delete;
 };
 
 } // namespace lldb_private
 
 #endif // LLDB_CORE_MODULE_H

lldb/include/lldb/Symbol/SymbolFile.h

public:
   virtual void FindFunctions(const RegularExpression &regex,
                              bool include_inlines, SymbolContextList &sc_list);
   virtual void
   FindTypes(ConstString name, const CompilerDeclContext &parent_decl_ctx,
             uint32_t max_matches,
             llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
             TypeMap &types);
 
+  /// Find types in a specific scope.
+  /// \param scope
+  ///     Must be either the scope prefix (with leading ::) or empty
+  virtual void
+  FindTypes(ConstString name, llvm::StringRef scope,
+            const CompilerDeclContext &parent_decl_ctx, uint32_t max_matches,
+            llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
+            TypeMap &types);
+
   /// Find types specified by a CompilerContextPattern.
   /// \param languages
   ///     Only return results in these languages.
   /// \param searched_symbol_files
   ///     Prevents one file from being visited multiple times.
   virtual void
   FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
             llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,

lldb/source/Core/Module.cpp

 #include "lldb/Utility/LLDBAssert.h"
 #include "lldb/Utility/Log.h"
 #include "lldb/Utility/Logging.h"
 #include "lldb/Utility/RegularExpression.h"
 #include "lldb/Utility/Status.h"
 #include "lldb/Utility/Stream.h"
 #include "lldb/Utility/StreamString.h"
 #include "lldb/Utility/Timer.h"
+#include "llvm/ADT/StringRef.h"
 
 #if defined(_WIN32)
 #include "lldb/Host/windows/PosixApi.h"
 #endif
 
 #include "Plugins/Language/CPlusPlus/CPlusPlusLanguage.h"
 #include "Plugins/Language/ObjC/ObjCLanguage.h"
 
void Module::FindTypes_Impl(
     size_t max_matches,
     llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
     TypeMap &types) {
   if (SymbolFile *symbols = GetSymbolFile())
     symbols->FindTypes(name, parent_decl_ctx, max_matches,
                        searched_symbol_files, types);
 }
 
+void Module::FindTypes_Impl(
+    ConstString name, llvm::StringRef scope,
+    const CompilerDeclContext &parent_decl_ctx, size_t max_matches,
+    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
+    TypeMap &types) {
+  LLDB_SCOPED_TIMER();
+  if (SymbolFile *symbols = GetSymbolFile())
+    symbols->FindTypes(name, scope, parent_decl_ctx, max_matches,
+                       searched_symbol_files, types);
+}
+
 void Module::FindTypesInNamespace(ConstString type_name,
                                   const CompilerDeclContext &parent_decl_ctx,
                                   size_t max_matches, TypeList &type_list) {
   TypeMap types_map;
   llvm::DenseSet<lldb_private::SymbolFile *> searched_symbol_files;
   FindTypes_Impl(type_name, parent_decl_ctx, max_matches, searched_symbol_files,
                  types_map);
   if (types_map.GetSize()) {
void Module::FindTypes(
   const char *type_name_cstr = name.GetCString();
   llvm::StringRef type_scope;
   llvm::StringRef type_basename;
   TypeClass type_class = eTypeClassAny;
   TypeMap typesmap;
 
   if (Type::GetTypeScopeAndBasename(type_name_cstr, type_scope, type_basename,
                                     type_class)) {
+
+    ConstString type_basename_const_str(type_basename);
+    FindTypes_Impl(type_basename_const_str, type_scope, CompilerDeclContext(),
+                   max_matches, searched_symbol_files, typesmap);
+
     // Check if "name" starts with "::" which means the qualified type starts
     // from the root namespace and implies and exact match. The typenames we
     // get back from clang do not start with "::" so we need to strip this off
     // in order to get the qualified names to match
     exact_match = type_scope.consume_front("::");
-
-    ConstString type_basename_const_str(type_basename);
-    FindTypes_Impl(type_basename_const_str, CompilerDeclContext(), max_matches,
-                   searched_symbol_files, typesmap);
     if (typesmap.GetSize())
       typesmap.RemoveMismatchedTypes(std::string(type_scope),
                                      std::string(type_basename), type_class,
                                      exact_match);
   } else {
     // The type is not in a namespace/class scope, just search for it by
     // basename
     if (type_class != eTypeClassAny && !type_basename.empty()) {

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

 #include <list>
 #include <map>
 #include <mutex>
 #include <unordered_map>
 #include <vector>
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Threading.h"
 
 #include "lldb/Core/UniqueCStringMap.h"
 #include "lldb/Core/dwarf.h"
 #include "lldb/Symbol/DebugMacros.h"
 #include "lldb/Symbol/SymbolContext.h"
 #include "lldb/Symbol/SymbolFile.h"
 #include "lldb/Target/Statistics.h"
void FindFunctions(const lldb_private::RegularExpression &regex,
                      bool include_inlines,
                      lldb_private::SymbolContextList &sc_list) override;
 
   void GetMangledNamesForFunction(
       const std::string &scope_qualified_name,
       std::vector<lldb_private::ConstString> &mangled_names) override;
 
   void
+  FindTypes(lldb_private::ConstString name, llvm::StringRef scope,
+            const lldb_private::CompilerDeclContext &parent_decl_ctx,
+            uint32_t max_matches,
+            llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
+            lldb_private::TypeMap &types) override;
+
+  void
   FindTypes(lldb_private::ConstString name,
             const lldb_private::CompilerDeclContext &parent_decl_ctx,
             uint32_t max_matches,
             llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
             lldb_private::TypeMap &types) override;
 
   void FindTypes(llvm::ArrayRef<lldb_private::CompilerContext> pattern,
                  lldb_private::LanguageSet languages,

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

 //===-- SymbolFileDWARF.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 "SymbolFileDWARF.h"
 
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Threading.h"
 
 #include "lldb/Core/Module.h"
 #include "lldb/Core/ModuleList.h"
 #include "lldb/Core/ModuleSpec.h"
 #include "lldb/Core/PluginManager.h"
 #include "lldb/Core/Progress.h"
 #include "lldb/Core/Section.h"
 #include "lldb/Core/StreamFile.h"
 #include "lldb/Core/Value.h"
 #include "lldb/Utility/ArchSpec.h"
+#include "lldb/Utility/ConstString.h"
 #include "lldb/Utility/RegularExpression.h"
 #include "lldb/Utility/Scalar.h"
 #include "lldb/Utility/StreamString.h"
 #include "lldb/Utility/Timer.h"
 
 #include "Plugins/ExpressionParser/Clang/ClangModulesDeclVendor.h"
 #include "Plugins/Language/CPlusPlus/CPlusPlusLanguage.h"
 
void SymbolFileDWARF::GetMangledNamesForFunction(
   }
 }
 
 void SymbolFileDWARF::FindTypes(
     ConstString name, const CompilerDeclContext &parent_decl_ctx,
     uint32_t max_matches,
     llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
     TypeMap &types) {
+  FindTypes(name, llvm::StringRef(), parent_decl_ctx, max_matches,
+            searched_symbol_files, types);
+}
+
+void SymbolFileDWARF::FindTypes(
+    ConstString name, llvm::StringRef scope,
+    const CompilerDeclContext &parent_decl_ctx, uint32_t max_matches,
+    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
+    TypeMap &types) {
   std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
   // Make sure we haven't already searched this SymbolFile before.
   if (!searched_symbol_files.insert(this).second)
     return;
 
   Log *log(LogChannelDWARF::GetLogIfAll(DWARF_LOG_LOOKUPS));
 
   if (log) {
else
           "SymbolFileDWARF::FindTypes (sc, name=\"%s\", parent_decl_ctx = "
           "NULL, max_matches=%u, type_list)",
           name.GetCString(), max_matches);
   }
 
   if (!DeclContextMatchesThisSymbolFile(parent_decl_ctx))
     return;
 
+  // prepare string to check against in case this is a fully qualified search
+  bool has_scope = !scope.empty();
+  if (scope.size() != 2) {
+    // DWARFDIE prefixes only variables in global scope with '::'
+    scope.consume_front("::");
+  }
+
   m_index->GetTypes(name, [&](DWARFDIE die) {
     if (!DIEInDeclContext(parent_decl_ctx, die))
       return true; // The containing decl contexts don't match
 
+    if (has_scope) {
+      std::string storage;
+      die.GetQualifiedName(storage);
+      if (!storage.empty() && !llvm::StringRef(storage).startswith(scope))
+        return true;
+    }
+
     Type *matching_type = ResolveType(die, true, true);
     if (!matching_type)
       return true;
 
     // We found a type pointer, now find the shared pointer form our type
     // list
     types.InsertUnique(matching_type->shared_from_this());
     return types.GetSize() < max_matches;

lldb/source/Symbol/SymbolFile.cpp

 #include "lldb/Symbol/CompileUnit.h"
 #include "lldb/Symbol/ObjectFile.h"
 #include "lldb/Symbol/TypeMap.h"
 #include "lldb/Symbol/TypeSystem.h"
 #include "lldb/Symbol/VariableList.h"
 #include "lldb/Utility/Log.h"
 #include "lldb/Utility/StreamString.h"
 #include "lldb/lldb-private.h"
+#include "llvm/ADT/StringRef.h"
 
 #include <future>
 
 using namespace lldb_private;
 using namespace lldb;
 
 char SymbolFile::ID;
 
void SymbolFile::GetMangledNamesForFunction(
     std::vector<ConstString> &mangled_names) {}
 
 void SymbolFile::FindTypes(
     ConstString name, const CompilerDeclContext &parent_decl_ctx,
     uint32_t max_matches,
     llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
     TypeMap &types) {}
 
+void SymbolFile::FindTypes(
+    ConstString basename, llvm::StringRef scope,
+    const CompilerDeclContext &parent_decl_ctx, uint32_t max_matches,
+    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
+    TypeMap &types) {
+  FindTypes(basename, parent_decl_ctx, max_matches, searched_symbol_files,
+            types);
+  TypeClass type_class = eTypeClassAny;
+  types.RemoveMismatchedTypes(std::string(basename.GetCString()), scope.str(),
+                              type_class, scope.startswith("::"));
+}
+
 void SymbolFile::FindTypes(llvm::ArrayRef<CompilerContext> pattern,
                            LanguageSet languages,
                            llvm::DenseSet<SymbolFile *> &searched_symbol_files,
                            TypeMap &types) {}
 
 void SymbolFile::AssertModuleLock() {
   // The code below is too expensive to leave enabled in release builds. It's
   // enabled in debug builds or when the correct macro is set.