[NativePDB] Improved support for nested type reconstruction

[zturner]

Summary

In a previous patch, we pre-processed the TPI stream in order to build the reverse mapping from nested type -> parent type so that we could accurately reconstruct a DeclContext hierarchy.

However, there were some issues. An LF_NESTTYPE record is really just a typedef, so although it happens to be used to indicate the name of the nested type and referring to the global record which defines the type, it is also used for every other kind of nested typedef. When we rebuild the DeclContext hierarchy, we want it to be as accurate as possible, which means that if we have something like:

struct A {
  struct B {};
  using C = B;
};

We don't want to create two CXXRecordDecls in the AST each with the exact same definition. We just want to create one for B and then define C as an alias to B. Previously, however, it would not be able to distinguish between the two cases and it would treat A::B and A::C as being two classes each with separate definitions. We address the first half of improving the pre-processing logic so that only actual definitions are treated this way.

Later, in a followup patch, we can handle the case of nested typedefs since we're already going to be enumerating the field list anyway and this patch introduces the general framework for distinguishing between the two cases.

[aleksandr.urakov]

This change looks reasonable to me for solving the problem with the current LF_NESTTYPE approach. But I'm not sure... Now we all the same need to analyze mangled names and make a decision based on this. Does the current LF_NESTTYPE approach still has advantages over the "parse-scope" approach? I'm afraid that we will have to fully analyze a mangled name in the future for scoped types, so if the LF_NESTTYPE approach doesn't have a significant advantages over the "parse-scope" approach, do we really need to support them both?

lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp

560–576 ↗

(On Diff #173447)

May be it would be a good idea to make the demangler (or to implement a mangler) more flexible to hide these details there? I do not mean to do it exactly in this commit, but what do you think about this at all?

881–887 ↗

(On Diff #173447)

Is this a clang only bug, or MSVC also does so? I do not have anything against this solution for now, I just mean, may be we'll replace it with an assert when the bug will be fixed?

lldb/trunk/lit/SymbolFile/NativePDB/Inputs/nested-types.lldbinit

+settings set auto-one-line-summaries false
+
+target variable -T GlobalA
+target variable -T GlobalB
+target variable -T GlobalC
+target variable -T GlobalD
+target variable -T GlobalE
+target variable -T GlobalF
+target variable -T GlobalG
+target variable -T GlobalH
+
+target modules dump ast

lldb/trunk/lit/SymbolFile/NativePDB/nested-types.cpp

+// clang-format off
+// REQUIRES: lld
+
+// Test various interesting cases for AST reconstruction.
+// RUN: clang-cl /Z7 /GS- /GR- -Xclang -fkeep-static-consts /c /Fo%t.obj -- %s
+// RUN: lld-link /DEBUG /nodefaultlib /entry:main /OUT:%t.exe /PDB:%t.pdb -- %t.obj
+// RUN: env LLDB_USE_NATIVE_PDB_READER=1 lldb -f %t.exe -s \
+// RUN:     %p/Inputs/nested-types.lldbinit 2>&1 | FileCheck %s
+
+struct S {
+  struct NestedStruct {
+    int A = 0;
+    int B = 1;
+  };
+  int C = 2;
+  int D = 3;
+};
+struct T {
+  using NestedTypedef = int;
+  using NestedTypedef2 = S;
+
+  struct NestedStruct {
+    int E = 4;
+    int F = 5;
+  };
+
+  using NestedStructAlias = NestedStruct;
+  using NST = S::NestedStruct;
+
+  NestedTypedef NT = 4;
+
+  using U = struct {
+    int G = 6;
+    int H = 7;
+  };
+};
+
+template<typename Param>
+class U {
+public:
+  // See llvm.org/pr39607.  clang-cl currently doesn't emit an important debug
+  // info record for nested template instantiations, so we can't reconstruct
+  // a proper DeclContext hierarchy for these.  As such, U<X>::V<Y> will show up
+  // in the global namespace.
+  template<typename Param>
+  struct V {
+    Param I = 8;
+    Param J = 9;
+
+    using W = T::NestedTypedef;
+    using X = U<int>;
+  };
+
+  struct W {
+    Param M = 12;
+    Param N = 13;
+  };
+  Param K = 10;
+  Param L = 11;
+  using Y = V<int>;
+  using Z = V<T>;
+};
+
+constexpr S GlobalA;
+constexpr S::NestedStruct GlobalB;
+constexpr T GlobalC;
+constexpr T::NestedStruct GlobalD;
+constexpr T::U GlobalE;
+constexpr U<int> GlobalF;
+constexpr U<int>::V<int> GlobalG;
+constexpr U<int>::W GlobalH;
+
+
+int main(int argc, char **argv) {
+  return 0;
+}
+
+
+
+// CHECK: (lldb) target variable -T GlobalA
+// CHECK: (const S) GlobalA = {
+// CHECK:   (int) C = 2
+// CHECK:   (int) D = 3
+// CHECK: }
+// CHECK: (lldb) target variable -T GlobalB
+// CHECK: (const S::NestedStruct) GlobalB = {
+// CHECK:   (int) A = 0
+// CHECK:   (int) B = 1
+// CHECK: }
+// CHECK: (lldb) target variable -T GlobalC
+// CHECK: (const T) GlobalC = {
+// CHECK:   (int) NT = 4
+// CHECK: }
+// CHECK: (lldb) target variable -T GlobalD
+// CHECK: (const T::NestedStruct) GlobalD = {
+// CHECK:   (int) E = 4
+// CHECK:   (int) F = 5
+// CHECK: }
+// CHECK: (lldb) target variable -T GlobalE
+// CHECK: (const T::U) GlobalE = {
+// CHECK:   (int) G = 6
+// CHECK:   (int) H = 7
+// CHECK: }
+// CHECK: (lldb) target variable -T GlobalF
+// CHECK: (const U<int>) GlobalF = {
+// CHECK:   (int) K = 10
+// CHECK:   (int) L = 11
+// CHECK: }
+// CHECK: (lldb) target variable -T GlobalG
+// CHECK: (const U<int>::V<int>) GlobalG = {
+// CHECK:   (int) I = 8
+// CHECK:   (int) J = 9
+// CHECK: }
+// CHECK: (lldb) target modules dump ast
+// CHECK: Dumping clang ast for 1 modules.
+// CHECK: TranslationUnitDecl {{.*}}
+// CHECK: |-CXXRecordDecl {{.*}} struct S definition
+// CHECK: | |-FieldDecl {{.*}} C 'int'
+// CHECK: | |-FieldDecl {{.*}} D 'int'
+// CHECK: | `-CXXRecordDecl {{.*}} struct NestedStruct definition
+// CHECK: |   |-FieldDecl {{.*}} A 'int'
+// CHECK: |   `-FieldDecl {{.*}} B 'int'
+// CHECK: |-CXXRecordDecl {{.*}} struct T definition
+// CHECK: | |-FieldDecl {{.*}} NT 'int'
+// CHECK: | |-CXXRecordDecl {{.*}} struct NestedStruct definition
+// CHECK: | | |-FieldDecl {{.*}} E 'int'
+// CHECK: | | `-FieldDecl {{.*}} F 'int'
+// CHECK: | `-CXXRecordDecl {{.*}} struct U definition
+// CHECK: |   |-FieldDecl {{.*}} G 'int'
+// CHECK: |   `-FieldDecl {{.*}} H 'int'
+// CHECK: |-CXXRecordDecl {{.*}} class U<int> definition
+// CHECK: | |-FieldDecl {{.*}} K 'int'
+// CHECK: | |-FieldDecl {{.*}} L 'int'
+// CHECK: | `-CXXRecordDecl {{.*}} struct W definition
+// CHECK: |   |-FieldDecl {{.*}} M 'int'
+// CHECK: |   `-FieldDecl {{.*}} N 'int'
+// CHECK: |-CXXRecordDecl {{.*}} struct U<int>::V<int> definition
+// CHECK: | |-FieldDecl {{.*}} I 'int'
+// CHECK: | `-FieldDecl {{.*}} J 'int'

lldb/trunk/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp

void SymbolFileNativePDB::InitializeObject() {
   TypeSystem *ts = GetTypeSystemForLanguage(eLanguageTypeC_plus_plus);
   m_clang = llvm::dyn_cast_or_null<ClangASTContext>(ts);
   m_importer = llvm::make_unique<ClangASTImporter>();
 
   PreprocessTpiStream();
   lldbassert(m_clang);
 }
 
+static llvm::Optional<CVTagRecord>
+GetNestedTagRecord(const NestedTypeRecord &Record, const CVTagRecord &parent,
+                   TpiStream &tpi) {
+  // An LF_NESTTYPE is essentially a nested typedef / using declaration, but it
+  // is also used to indicate the primary definition of a nested class.  That is
+  // to say, if you have:
+  // struct A {
+  //   struct B {};
+  //   using C = B;
+  // };
+  // Then in the debug info, this will appear as:
+  // LF_STRUCTURE `A::B` [type index = N]
+  // LF_STRUCTURE `A`
+  //   LF_NESTTYPE [name = `B`, index = N]
+  //   LF_NESTTYPE [name = `C`, index = N]
+  // In order to accurately reconstruct the decl context hierarchy, we need to
+  // know which ones are actual definitions and which ones are just aliases.
+
+  // If it's a simple type, then this is something like `using foo = int`.
+  if (Record.Type.isSimple())
+    return llvm::None;
+
+  // If it's an inner definition, then treat whatever name we have here as a
+  // single component of a mangled name.  So we can inject it into the parent's
+  // mangled name to see if it matches.
+  CVTagRecord child = CVTagRecord::create(tpi.getType(Record.Type));
+  std::string qname = parent.asTag().getUniqueName();
+  if (qname.size() < 4 || child.asTag().getUniqueName().size() < 4)
+    return llvm::None;
+
+  // qname[3] is the tag type identifier (struct, class, union, etc).  Since the
+  // inner tag type is not necessarily the same as the outer tag type, re-write
+  // it to match the inner tag type.
+  qname[3] = child.asTag().getUniqueName()[3];
+  std::string piece = Record.Name;
+  piece.push_back('@');
+  qname.insert(4, std::move(piece));
+  if (qname != child.asTag().UniqueName)
+    return llvm::None;
+
+  return std::move(child);
+}
+
 void SymbolFileNativePDB::PreprocessTpiStream() {
   LazyRandomTypeCollection &types = m_index->tpi().typeCollection();
 
   for (auto ti = types.getFirst(); ti; ti = types.getNext(*ti)) {
     CVType type = types.getType(*ti);
     if (!IsTagRecord(type))
       continue;
 
     CVTagRecord tag = CVTagRecord::create(type);
     // We're looking for LF_NESTTYPE records in the field list, so ignore
     // forward references (no field list), and anything without a nested class
     // (since there won't be any LF_NESTTYPE records).
     if (tag.asTag().isForwardRef() || !tag.asTag().containsNestedClass())
       continue;
 
     struct ProcessTpiStream : public TypeVisitorCallbacks {
       ProcessTpiStream(PdbIndex &index, TypeIndex parent,
+                       const CVTagRecord &parent_cvt,
                        llvm::DenseMap<TypeIndex, TypeIndex> &parents)
-          : index(index), parents(parents), parent(parent) {}
+          : index(index), parents(parents), parent(parent),
+            parent_cvt(parent_cvt) {}
 
       PdbIndex &index;
       llvm::DenseMap<TypeIndex, TypeIndex> &parents;
       TypeIndex parent;
+      const CVTagRecord &parent_cvt;
 
       llvm::Error visitKnownMember(CVMemberRecord &CVR,
                                    NestedTypeRecord &Record) override {
+        llvm::Optional<CVTagRecord> tag =
+            GetNestedTagRecord(Record, parent_cvt, index.tpi());
+        if (!tag)
+          return llvm::ErrorSuccess();
+
         parents[Record.Type] = parent;
-        CVType child = index.tpi().getType(Record.Type);
-        if (!IsForwardRefUdt(child))
+        if (!tag->asTag().isForwardRef())
           return llvm::ErrorSuccess();
+
         llvm::Expected<TypeIndex> full_decl =
             index.tpi().findFullDeclForForwardRef(Record.Type);
         if (!full_decl) {
           llvm::consumeError(full_decl.takeError());
           return llvm::ErrorSuccess();
         }
         parents[*full_decl] = parent;
         return llvm::ErrorSuccess();
       }
     };
 
     CVType field_list = m_index->tpi().getType(tag.asTag().FieldList);
-    ProcessTpiStream process(*m_index, *ti, m_parent_types);
+    ProcessTpiStream process(*m_index, *ti, tag, m_parent_types);
     llvm::Error error = visitMemberRecordStream(field_list.data(), process);
     if (error)
       llvm::consumeError(std::move(error));
   }
 }
 
 uint32_t SymbolFileNativePDB::GetNumCompileUnits() {
   const DbiModuleList &modules = m_index->dbi().modules();

 static std::string RenderDemanglerNode(llvm::ms_demangle::Node *n) {
   OutputStream OS;
   initializeOutputStream(nullptr, nullptr, OS, 1024);
   n->output(OS, llvm::ms_demangle::OF_Default);
   OS << '\0';
   return {OS.getBuffer()};
 }
 
+static bool
+AnyScopesHaveTemplateParams(llvm::ArrayRef<llvm::ms_demangle::Node *> scopes) {
+  for (llvm::ms_demangle::Node *n : scopes) {
+    auto *idn = static_cast<llvm::ms_demangle::IdentifierNode *>(n);
+    if (idn->TemplateParams)
+      return true;
+  }
+  return false;
+}
+
 std::pair<clang::DeclContext *, std::string>
 SymbolFileNativePDB::CreateDeclInfoForType(const TagRecord &record,
                                            TypeIndex ti) {
   llvm::ms_demangle::Demangler demangler;
   StringView sv(record.UniqueName.begin(), record.UniqueName.size());
   llvm::ms_demangle::TagTypeNode *ttn = demangler.parseTagUniqueName(sv);
   llvm::ms_demangle::IdentifierNode *idn =
       ttn->QualifiedName->getUnqualifiedIdentifier();
SymbolFileNativePDB::CreateDeclInfoForType(const TagRecord &record,
   // If this type doesn't have a parent type in the debug info, then the best we
   // can do is to say that it's either a series of namespaces (if the scope is
   // non-empty), or the translation unit (if the scope is empty).
   auto parent_iter = m_parent_types.find(ti);
   if (parent_iter == m_parent_types.end()) {
     if (scopes.empty())
       return {context, uname};
 
+    // If there is no parent in the debug info, but some of the scopes have
+    // template params, then this is a case of bad debug info.  See, for
+    // example, llvm.org/pr39607.  We don't want to create an ambiguity between
+    // a NamespaceDecl and a CXXRecordDecl, so instead we create a class at
+    // global scope with the fully qualified name.
+    if (AnyScopesHaveTemplateParams(scopes))
+      return {context, record.Name};
+
     for (llvm::ms_demangle::Node *scope : scopes) {
       auto *nii = static_cast<llvm::ms_demangle::NamedIdentifierNode *>(scope);
       std::string str = RenderDemanglerNode(nii);
       context = m_clang->GetUniqueNamespaceDeclaration(str.c_str(), context);
     }
     return {context, uname};
   }
 

llvm/trunk/lib/DebugInfo/CodeView/LazyRandomTypeCollection.cpp

 uint32_t LazyRandomTypeCollection::getOffsetOfType(TypeIndex Index) {
   error(ensureTypeExists(Index));
   assert(contains(Index));
 
   return Records[Index.toArrayIndex()].Offset;
 }
 
 CVType LazyRandomTypeCollection::getType(TypeIndex Index) {
+  assert(!Index.isSimple());
+
   auto EC = ensureTypeExists(Index);
   error(std::move(EC));
   assert(contains(Index));
 
   return Records[Index.toArrayIndex()].Type;
 }
 
 Optional<CVType> LazyRandomTypeCollection::tryGetType(TypeIndex Index) {
+  if (Index.isSimple())
+    return None;
+
   if (auto EC = ensureTypeExists(Index)) {
     consumeError(std::move(EC));
     return None;
   }
 
   assert(contains(Index));
   return Records[Index.toArrayIndex()].Type;
 }

 Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
   if (contains(TI))
     return Error::success();
 
   return visitRangeForType(TI);
 }
 
 void LazyRandomTypeCollection::ensureCapacityFor(TypeIndex Index) {
+  assert(!Index.isSimple());
   uint32_t MinSize = Index.toArrayIndex() + 1;
 
   if (MinSize <= capacity())
     return;
 
   uint32_t NewCapacity = MinSize * 3 / 2;
 
   assert(NewCapacity > capacity());
   Records.resize(NewCapacity);
 }
 
 Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
+  assert(!TI.isSimple());
   if (PartialOffsets.empty())
     return fullScanForType(TI);
 
   auto Next = std::upper_bound(PartialOffsets.begin(), PartialOffsets.end(), TI,
                                [](TypeIndex Value, const TypeIndexOffset &IO) {
                                  return Value < IO.Type;
                                });
 
if (auto EC = ensureTypeExists(Prev + 1)) {
     consumeError(std::move(EC));
     return None;
   }
 
   return Prev + 1;
 }
 
 Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
+  assert(!TI.isSimple());
   assert(PartialOffsets.empty());
 
   TypeIndex CurrentTI = TypeIndex::fromArrayIndex(0);
   auto Begin = Types.begin();
 
   if (Count > 0) {
     // In the case of type streams which we don't know the number of records of,
     // it's possible to search for a type index triggering a full scan, but then

llvm/trunk/lib/DebugInfo/PDB/Native/TpiStream.cpp

if (!FullTR.hasUniqueName())
       continue;
     if (ForwardTR.getUniqueName() == FullTR.getUniqueName())
       return TI;
   }
   return ForwardRefTI;
 }
 
 codeview::CVType TpiStream::getType(codeview::TypeIndex Index) {
+  assert(!Index.isSimple());
   return Types->getType(Index);
 }
 
 BinarySubstreamRef TpiStream::getTypeRecordsSubstream() const {
   return TypeRecordsSubstream;
 }
 
 FixedStreamArray<support::ulittle32_t> TpiStream::getHashValues() const {