[LLDB][NativePDB] Allow type lookup in namespaces (#149876)

Previously, `type lookup` for types in namespaces didn't work with the
native PDB plugin, because `FindTypes` would only look for types whose
base name was equal to their full name. PDB/CodeView does not store the
base names in the TPI stream, but the types have their full name (e.g.
`std::thread` instead of `thread`). So `findRecordsByName` would only
return types in the top level namespace.

This PR changes the lookup to go through all types and check their base
name. As that could be a bit expensive, the names are first cached
(similar to the function lookup in the DIA PDB plugin). Potential types
are checked with `TypeQuery::ContextMatches`.

To be able to handle anonymous namespaces, I changed
`TypeQuery::ContextMatches`. The [`TypeQuery`
constructor](https://github.com/llvm/llvm-project/blob/9ad7edef4276207ca4cefa6b39d11145f4145a72/lldb/source/Symbol/Type.cpp#L76-L79)
inserts all name components as `CompilerContextKind::AnyDeclContext`. To
skip over anonymous namespaces, `ContextMatches` checked if a component
was empty and exactly of kind `Namespace`. For our query, the last check
was always false, so we never skipped anonymous namespaces. DWARF
doesn't have this problem, as it [constructs the context
outside](https://github.com/llvm/llvm-project/blob/abe93d9d7e891a2a6596ddb0c6324280137c89dc/lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.cpp#L154-L160)
and has proper information about namespaces. I'm not fully sure if my
change is correct and that it doesn't break other users of `TypeQuery`.

This enables `type lookup <type>` to work on types in namespaces.
However, expressions don't work with this yet, because `FindNamespace`
is unimplemented for native PDB.

1 files changed, 73 insertions, 12 deletions

diff --git a/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp b/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp
index 20d8c1acf9c4..7af53e16ce9d 100644
--- a/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp
+++ b/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp
@@ -1720,18 +1720,22 @@ void SymbolFileNativePDB::FindTypes(const lldb_private::TypeQuery &query,
 
   std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
 
-  std::vector<TypeIndex> matches =
-      m_index->tpi().findRecordsByName(query.GetTypeBasename().GetStringRef());
-
-  for (TypeIndex type_idx : matches) {
-    TypeSP type_sp = GetOrCreateType(type_idx);
-    if (!type_sp)
+  // We can't query for the full name because the type might reside
+  // in an anonymous namespace. Search for the basename in our map and check the
+  // matching types afterwards.
+  std::vector<uint32_t> matches;
+  m_type_base_names.GetValues(query.GetTypeBasename(), matches);
+
+  for (uint32_t match_idx : matches) {
+    std::vector context = GetContextForType(TypeIndex(match_idx));
+    if (context.empty())
       continue;
 
-    // We resolved a type. Get the fully qualified name to ensure it matches.
-    ConstString name = type_sp->GetQualifiedName();
-    TypeQuery type_match(name.GetStringRef(), TypeQueryOptions::e_exact_match);
-    if (query.ContextMatches(type_match.GetContextRef())) {
+    if (query.ContextMatches(context)) {
+      TypeSP type_sp = GetOrCreateType(TypeIndex(match_idx));
+      if (!type_sp)
+        continue;
+
       results.InsertUnique(type_sp);
       if (results.Done(query))
         return;
@@ -2201,11 +2205,15 @@ void SymbolFileNativePDB::BuildParentMap() {
     CVTagRecord tag = CVTagRecord::create(type);
 
     RecordIndices &indices = record_indices[tag.asTag().getUniqueName()];
-    if (tag.asTag().isForwardRef())
+    if (tag.asTag().isForwardRef()) {
       indices.forward = *ti;
-    else
+    } else {
       indices.full = *ti;
 
+      auto base_name = MSVCUndecoratedNameParser::DropScope(tag.name());
+      m_type_base_names.Append(ConstString(base_name), ti->getIndex());
+    }
+
     if (indices.full != TypeIndex::None() &&
         indices.forward != TypeIndex::None()) {
       forward_to_full[indices.forward] = indices.full;
@@ -2261,6 +2269,10 @@ void SymbolFileNativePDB::BuildParentMap() {
       llvm::consumeError(std::move(error));
   }
 
+  // After calling Append(), the type-name map needs to be sorted again to be
+  // able to look up a type by its name.
+  m_type_base_names.Sort();
+
   // Now that we know the forward -> full mapping of all type indices, we can
   // re-write all the indices.  At the end of this process, we want a mapping
   // consisting of fwd -> full and full -> full for all child -> parent indices.
@@ -2353,3 +2365,52 @@ SymbolFileNativePDB::GetParentType(llvm::codeview::TypeIndex ti) {
     return std::nullopt;
   return parent_iter->second;
 }
+
+std::vector<CompilerContext>
+SymbolFileNativePDB::GetContextForType(TypeIndex ti) {
+  CVType type = m_index->tpi().getType(ti);
+  if (!IsTagRecord(type))
+    return {};
+
+  CVTagRecord tag = CVTagRecord::create(type);
+
+  std::optional<Type::ParsedName> parsed_name =
+      Type::GetTypeScopeAndBasename(tag.name());
+  if (!parsed_name)
+    return {{tag.contextKind(), ConstString(tag.name())}};
+
+  std::vector<CompilerContext> ctx;
+  // assume everything is a namespace at first
+  for (llvm::StringRef scope : parsed_name->scope) {
+    ctx.emplace_back(CompilerContextKind::Namespace, ConstString(scope));
+  }
+  // we know the kind of our own type
+  ctx.emplace_back(tag.contextKind(), ConstString(parsed_name->basename));
+
+  // try to find the kind of parents
+  for (auto &el : llvm::reverse(llvm::drop_end(ctx))) {
+    std::optional<TypeIndex> parent = GetParentType(ti);
+    if (!parent)
+      break;
+
+    ti = *parent;
+    type = m_index->tpi().getType(ti);
+    switch (type.kind()) {
+    case LF_CLASS:
+    case LF_STRUCTURE:
+    case LF_INTERFACE:
+      el.kind = CompilerContextKind::ClassOrStruct;
+      continue;
+    case LF_UNION:
+      el.kind = CompilerContextKind::Union;
+      continue;
+    case LF_ENUM:
+      el.kind = CompilerContextKind::Enum;
+      continue;
+    default:
+      break;
+    }
+    break;
+  }
+  return ctx;
+}