[NativePDB] Process virtual bases in the correct order

[aleksandr.urakov]

Summary

This patch makes virtual bases to be added in the correct order to the bases list. It is important because VTableContext (MicrosoftVTableContext in our case) uses then the order of virtual bases in the list to restore the virtual table indexes. These indexes are used then to resolve the layout of the virtual bases.

We haven't enough information about offsets of virtual bases regarding to the object (moreover, in a common case we can't rely on such information, see the example here: https://reviews.llvm.org/D53506#1272306 ), but there should be enough information to restore the layout of the virtual bases from the indexes in runtime. After D53506 this information is used whenever possible, so there should be no problems with virtual bases' fields reading.

I have some problems with the test, I'll describe them exactly in the test's text below. Do you have them too or is this a specific problem with my setup?

[aleksandr.urakov]

lit/SymbolFile/NativePDB/tag-types.cpp

5

Clang gives me an error about char16_t, char32_t etc., but if I use MSVC here, then the test compiles ok.

238–247

For both enums I have a "no type was found matching" error (both for Clang and MSVC).

[aleksandr.urakov]

Ping! Can you take a look, please?

[zturner]

The above suggestion is admittedly minor, but since it's both a minor performance improvement and a minor readability/maintainability improvement, I think it's probably worth doing.

lit/SymbolFile/NativePDB/tag-types.cpp

5

Usually this means clang cannot find your CRT headers. Can you run with -verbose? That should give you some insight into the environment we are running clang with, and might be a clue why it can't find the headers.

source/Plugins/SymbolFile/NativePDB/UdtRecordCompleter.cpp

54

Then, change this function to not pass is_virtual, only pass Optional<vtable_idx>.

60–63

vtable_idx.hasValue();

68–71

m_bases.push_back(std::make_pair(vtable_idx.getValueOr(0), std::move(base_spec)));

215

using vt = std::pair<uint64_t, std::unique_ptr<clang::CXXBaseSpecifier>>>;
std::stable_sort(m_bases, [](const vt &base1, const vt &base2) {
  return base1.first < base2.first;
  });

source/Plugins/SymbolFile/NativePDB/UdtRecordCompleter.h

54

I actually think it would be slightly better to use a vector<pair<>> here. The reason is that a) it will probably be slightly more efficient, because # of vbases is usually quite small (often just 1) and the overhead of a map is a net performance loss for small numbers of items. b) that people are often confused when seeing map instead of DenseMap and it might cause someone in the future to think they can change this to a DenseMap with no behavioral difference, even though the reason for using a map here is that it must be sorted.

How about just having this:

std::vector<std::pair<uint64_t, std::unique_ptr<clang::CXXBaseSpecifier>>> m_bases;

Comments on how to change the implementation below.

[zturner]

Sorry, due to the way Phabricator re-orders feedback across files when sending the email notification, if you're reading my comments in email you have to read the previous email from the bottom up.

[aleksandr.urakov]

Thanks for the comments, I think that they make sense. I've updated the patch.

[aleksandr.urakov]

lit/SymbolFile/NativePDB/tag-types.cpp

5

Can you give me little more hints on this, please? I've run the verbose build and it have given me the following:

compiling tag-types.cpp -> tag-types.cpp.tmp.exe-tag-types.obj
  Command Line: C:\Work\llvm\build_x64\bin\clang-cl.exe -m64 /Od /GS- /GR- /Z7 -Xclang -fkeep-static-consts /c /FoC:\Work\llvm\build_x64\tools\lldb\lit\SymbolFile\NativePDB\Output\tag-types.cpp.tmp.exe-tag-types.obj C:\Work\llvm\tools\lldb\lit\SymbolFile\NativePDB\tag-types.cpp
  Env:
    TMP = C:\Users\ALEKSA~1.URA\AppData\Local\Temp
    SystemRoot = C:\WINDOWS
    SystemDrive = C:
    INCLUDE = C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\VC\Tools\MSVC\14.16.27023\ATLMFC\include
              C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\VC\Tools\MSVC\14.16.27023\include
              C:\Program Files (x86)\Windows Kits\10\include\10.0.17763.0\ucrt
              C:\Program Files (x86)\Windows Kits\10\include\10.0.17763.0\shared
              C:\Program Files (x86)\Windows Kits\10\include\10.0.17763.0\um
              C:\Program Files (x86)\Windows Kits\10\include\10.0.17763.0\winrt
              C:\Program Files (x86)\Windows Kits\10\include\10.0.17763.0\cppwinrt
    TEMP = C:\Users\ALEKSA~1.URA\AppData\Local\Temp
  STDOUT:

  STDERR:
    C:\Work\llvm\tools\lldb\lit\SymbolFile\NativePDB\tag-types.cpp(16,3) :  error: unknown type name 'char16_t'
      char16_t            C16;
      ^
    C:\Work\llvm\tools\lldb\lit\SymbolFile\NativePDB\tag-types.cpp(17,3) :  error: unknown type name 'char32_t'
      char32_t            C32;
      ^
    C:\Work\llvm\tools\lldb\lit\SymbolFile\NativePDB\tag-types.cpp(41,3) :  error: unknown type name 'char16_t'
      char16_t            *PC16;
      ^
    C:\Work\llvm\tools\lldb\lit\SymbolFile\NativePDB\tag-types.cpp(42,3) :  error: unknown type name 'char32_t'
      char32_t            *PC32;
      ^
    C:\Work\llvm\tools\lldb\lit\SymbolFile\NativePDB\tag-types.cpp(64,9) :  error: unknown type name 'char16_t'
      const char16_t            *PC16;
            ^
    C:\Work\llvm\tools\lldb\lit\SymbolFile\NativePDB\tag-types.cpp(65,9) :  error: unknown type name 'char32_t'
      const char32_t            *PC32;
            ^
    6 errors generated.

There is the file named uchar.h in the directory C:\Program Files (x86)\Windows Kits\10\include\10.0.17763.0\ucrt, and it contains the typedefs for char16_t and char32_t, but I can't figure out, how the compiler could see it.

An interesting thing is that the compilation with the same command in the same console completes successfully:

C:\Work\llvm\build_x64\bin\clang-cl.exe -m64 /Od /GS- /GR- /Z7 -Xclang -fkeep-static-consts /c /FoC:\Work\llvm\build_x64\tools\lldb\lit\SymbolFile\NativePDB\Output\tag-types.cpp.tmp.exe-tag-types.obj C:\Work\llvm\tools\lldb\lit\SymbolFile\NativePDB\tag-types.cpp

[aleksandr.urakov]

Ping! What do you think about it?

[zturner]

In D56904#1383148, @aleksandr.urakov wrote:

Ping! What do you think about it?

Generally the change looks good, but I'm not sure why the compiler can't properly compile the source file. I know it's something to do with the environment, but it's hard to say what.

One idea would be to add -### to the end of your command line when running the command manually, and then update the build.py script so that it also runs -### from the command line and prints the output. Then maybe compare the two command lines and see if there's a difference.

Another idea would be to hack up the code in the build.py script that modifies the child process's environment. Start with the child environment hardcoded to your terminal's environment, and then delete variables until the problem reproduces. That should tell you what environment variable is causing the problem.

[aleksandr.urakov]

Thanks for the reply! It seems that after your hint I've figured it out. It's the environment variable VCINSTALLDIR. I've added it to the defaultenv list of the _get_visual_studio_environment function and the test passes now. What do you think about this solution?

And do I understand right, it means, that clang-cl needs MSVC installation to work with these types?

[aleksandr.urakov]

Thanks for the help with the tests, it looks like they are ok now! So can we proceed with this patch?

lit/SymbolFile/NativePDB/Inputs/tag-types.lldbinit

 type lookup -- Struct
 type lookup -- Class
 type lookup -- Union
 type lookup -- Derived
 type lookup -- Derived2
+type lookup -- DerivedVirtual1
+type lookup -- DerivedVirtual2
 type lookup -- EnumInt
 type lookup -- EnumShort
 type lookup -- InvalidType

lit/SymbolFile/NativePDB/tag-types.cpp

 // clang-format off
 // REQUIRES: lld
 
 // Test that we can display tag types.
-// RUN: %build --compiler=clang-cl --nodefaultlib -o %t.exe -- %s 
+// RUN: %build --compiler=clang-cl --nodefaultlib -o %t.exe -- %s
 // RUN: env LLDB_USE_NATIVE_PDB_READER=1 %lldb -f %t.exe -s \
 // RUN:     %p/Inputs/tag-types.lldbinit | FileCheck %s
 
 // Test struct
 struct Struct {
   // Test builtin types, which are represented by special CodeView type indices.
   bool                B;
   char                C;

 class Derived2 : protected Class, private Struct {
 public:
   // Test static data members
   static unsigned StaticDataMember;
 };
 
 unsigned Derived2::StaticDataMember = 0;
 
+// Test virtual inheritance.
+class DerivedVirtual1 : public virtual Class {};
+
+// Test the correctness of the virtual bases order.
+class DerivedVirtual2 : public DerivedVirtual1, public virtual OneMember {};
+
 // Test scoped enums and unscoped enums.
 enum class EnumInt {
   A = 1,
   B = 2
 };
 
 // Test explicit underlying types
 enum EnumShort : short {
   ES_A = 2,
   ES_B = 3
 };
 
 int main(int argc, char **argv) {
   Struct S;
   Class C;
   Union U;
   Derived D;
   Derived2 D2;
+  DerivedVirtual1 DV1;
+  DerivedVirtual2 DV2;
   EnumInt EI;
   EnumShort ES;
   
   return 0;
 }
 
 // CHECK:      (lldb) target create "{{.*}}tag-types.cpp.tmp.exe"
 // CHECK-NEXT: Current executable set to '{{.*}}tag-types.cpp.tmp.exe'

 // CHECK-NEXT:     OneMember *PtrMember;
 // CHECK-NEXT:     OneMember &RefMember;
 // CHECK-NEXT:     OneMember &&RValueRefMember;
 // CHECK:      }
 // CHECK-NEXT: (lldb) type lookup -- Derived2
 // CHECK-NEXT: class Derived2 : protected Class, private Struct {
 // CHECK-NEXT:     static unsigned int StaticDataMember;
 // CHECK-NEXT: }
+// CHECK-NEXT: (lldb) type lookup -- DerivedVirtual1
+// CHECK-NEXT: class DerivedVirtual1 : virtual public Class {
+// CHECK-NEXT: }
+// CHECK-NEXT: (lldb) type lookup -- DerivedVirtual2
+// CHECK-NEXT: class DerivedVirtual2 : public DerivedVirtual1, virtual public Class, virtual public OneMember {
+// CHECK-NEXT: }
 // CHECK-NEXT: (lldb) type lookup -- EnumInt
 // CHECK-NEXT: enum EnumInt {
 // CHECK-NEXT:     A,
 // CHECK-NEXT:     B
 // CHECK-NEXT: }
 // CHECK-NEXT: (lldb) type lookup -- EnumShort
 // CHECK-NEXT: enum EnumShort {
 // CHECK-NEXT:     ES_A,
 // CHECK-NEXT:     ES_B
 // CHECK-NEXT: }
 // CHECK-NEXT: (lldb) type lookup -- InvalidType
 // CHECK-NEXT: no type was found matching 'InvalidType'

source/Plugins/SymbolFile/NativePDB/UdtRecordCompleter.h

 
 namespace lldb_private {
 class Type;
 class CompilerType;
 namespace npdb {
 class PdbAstBuilder;
 
 class UdtRecordCompleter : public llvm::codeview::TypeVisitorCallbacks {
+  using IndexedBase =
+      std::pair<uint64_t, std::unique_ptr<clang::CXXBaseSpecifier>>;
+
   union UdtTagRecord {
     UdtTagRecord() {}
     llvm::codeview::UnionRecord ur;
     llvm::codeview::ClassRecord cr;
     llvm::codeview::EnumRecord er;
   } m_cvr;
 
   PdbTypeSymId m_id;
   CompilerType &m_derived_ct;
   clang::TagDecl &m_tag_decl;
   PdbAstBuilder &m_ast_builder;
   llvm::pdb::TpiStream &m_tpi;
-  std::vector<std::unique_ptr<clang::CXXBaseSpecifier>> m_bases;
+  std::vector<IndexedBase> m_bases;
   ClangASTImporter::LayoutInfo m_layout;
 
 public:
   UdtRecordCompleter(PdbTypeSymId id, CompilerType &derived_ct,
                      clang::TagDecl &tag_decl, PdbAstBuilder &ast_builder,
                      llvm::pdb::TpiStream &tpi);
 
 #define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
   llvm::Error visitKnownMember(llvm::codeview::CVMemberRecord &CVR,            \
                                llvm::codeview::Name##Record &Record) override;
 #define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
 #include "llvm/DebugInfo/CodeView/CodeViewTypes.def"
 
   void complete();
 
 private:
-  clang::QualType AddBaseClassForTypeIndex(llvm::codeview::TypeIndex ti,
-                                           llvm::codeview::MemberAccess access);
+  clang::QualType AddBaseClassForTypeIndex(
+      llvm::codeview::TypeIndex ti, llvm::codeview::MemberAccess access,
+      llvm::Optional<uint64_t> vtable_idx = llvm::Optional<uint64_t>());
   void AddMethod(llvm::StringRef name, llvm::codeview::TypeIndex type_idx,
                  llvm::codeview::MemberAccess access,
                  llvm::codeview::MethodOptions options,
                  llvm::codeview::MemberAttributes attrs);
 };
 
 } // namespace npdb
 } // namespace lldb_private
 
 #endif // LLDB_PLUGINS_SYMBOLFILE_NATIVEPDB_UDTRECORDCOMPLETER_H

source/Plugins/SymbolFile/NativePDB/UdtRecordCompleter.cpp

case LF_STRUCTURE:
     llvm::cantFail(TypeDeserializer::deserializeAs<ClassRecord>(cvt, m_cvr.cr));
     break;
   default:
     llvm_unreachable("unreachable!");
   }
 }
 
 clang::QualType UdtRecordCompleter::AddBaseClassForTypeIndex(
-    llvm::codeview::TypeIndex ti, llvm::codeview::MemberAccess access) {
+    llvm::codeview::TypeIndex ti, llvm::codeview::MemberAccess access,
+    llvm::Optional<uint64_t> vtable_idx) {
   PdbTypeSymId type_id(ti);
   clang::QualType qt = m_ast_builder.GetOrCreateType(type_id);
 
   CVType udt_cvt = m_tpi.getType(ti);
 
   std::unique_ptr<clang::CXXBaseSpecifier> base_spec =
       m_ast_builder.clang().CreateBaseClassSpecifier(
-          qt.getAsOpaquePtr(), TranslateMemberAccess(access), false,
-          udt_cvt.kind() == LF_CLASS);
+          qt.getAsOpaquePtr(), TranslateMemberAccess(access),
+          vtable_idx.hasValue(), udt_cvt.kind() == LF_CLASS);
   lldbassert(base_spec);
-  m_bases.push_back(std::move(base_spec));
+
+  m_bases.push_back(
+      std::make_pair(vtable_idx.getValueOr(0), std::move(base_spec)));
+
   return qt;
 }
 
 void UdtRecordCompleter::AddMethod(llvm::StringRef name, TypeIndex type_idx,
                                    MemberAccess access, MethodOptions options,
                                    MemberAttributes attrs) {
   clang::QualType method_qt =
       m_ast_builder.GetOrCreateType(PdbTypeSymId(type_idx));
   m_ast_builder.CompleteType(method_qt);
 
   lldb::AccessType access_type = TranslateMemberAccess(access);
Error UdtRecordCompleter::visitKnownMember(CVMemberRecord &cvr,
   auto offset = clang::CharUnits::fromQuantity(base.getBaseOffset());
   m_layout.base_offsets.insert(std::make_pair(decl, offset));
 
   return llvm::Error::success();
 }
 
 Error UdtRecordCompleter::visitKnownMember(CVMemberRecord &cvr,
                                            VirtualBaseClassRecord &base) {
-  AddBaseClassForTypeIndex(base.BaseType, base.getAccess());
+  AddBaseClassForTypeIndex(base.BaseType, base.getAccess(), base.VTableIndex);
 
-  // FIXME: Handle virtual base offsets.
   return Error::success();
 }
 
 Error UdtRecordCompleter::visitKnownMember(CVMemberRecord &cvr,
                                            ListContinuationRecord &cont) {
   return Error::success();
 }
 
Error UdtRecordCompleter::visitKnownMember(CVMemberRecord &cvr,
   llvm::StringRef name = DropNameScope(enumerator.getName());
 
   m_ast_builder.clang().AddEnumerationValueToEnumerationType(
       m_derived_ct, decl, name.str().c_str(), enumerator.Value);
   return Error::success();
 }
 
 void UdtRecordCompleter::complete() {
+  // Ensure the correct order for virtual bases.
+  std::stable_sort(m_bases.begin(), m_bases.end(),
+                   [](const IndexedBase &lhs, const IndexedBase &rhs) {
+                     return lhs.first < rhs.first;
+                   });
+
+  std::vector<std::unique_ptr<clang::CXXBaseSpecifier>> bases;
+  bases.reserve(m_bases.size());
+  for (auto &ib : m_bases)
+    bases.push_back(std::move(ib.second));
+
   ClangASTContext &clang = m_ast_builder.clang();
-  clang.TransferBaseClasses(m_derived_ct.GetOpaqueQualType(),
-                            std::move(m_bases));
+  clang.TransferBaseClasses(m_derived_ct.GetOpaqueQualType(), std::move(bases));
 
   clang.AddMethodOverridesForCXXRecordType(m_derived_ct.GetOpaqueQualType());
   ClangASTContext::BuildIndirectFields(m_derived_ct);
   ClangASTContext::CompleteTagDeclarationDefinition(m_derived_ct);
 
   if (auto *record_decl = llvm::dyn_cast<clang::CXXRecordDecl>(&m_tag_decl)) {
     m_ast_builder.importer().InsertRecordDecl(record_decl, m_layout);
   }
 }