[CodeView] Add support for random access type visitors.

Previously type visitation was done strictly sequentially, and
TypeIndexes were computed by incrementing the TypeIndex of the
last visited record.  This works fine for situations like dumping,
but not when you want to visit types in random order.  For example,
in a debug session someone might lookup a symbol by name, find that
it has TypeIndex 10,000 and then want to go straight to TypeIndex
10,000.

In order to make this work, the visitation framework needs a mode
where it can plumb TypeIndices through the callback pipeline.  This
patch adds such a mode.  In doing so, it is necessary to provide
an alternative implementation of TypeDatabase that supports random
access, so that is done as well.

Nothing actually uses these random access capabilities yet, but
this will be done in subsequent patches.

Differential Revision: https://reviews.llvm.org/D32928

llvm-svn: 302454

3 files changed, 136 insertions, 31 deletions

diff --git a/llvm/lib/DebugInfo/CodeView/CVTypeVisitor.cpp b/llvm/lib/DebugInfo/CodeView/CVTypeVisitor.cpp
index 0069ee3cc90..23f2c40543a 100644
--- a/llvm/lib/DebugInfo/CodeView/CVTypeVisitor.cpp
+++ b/llvm/lib/DebugInfo/CodeView/CVTypeVisitor.cpp
@@ -76,7 +76,7 @@ void CVTypeVisitor::addTypeServerHandler(TypeServerHandler &Handler) {
   Handlers.push_back(&Handler);
 }
 
-Error CVTypeVisitor::visitTypeRecord(CVType &Record) {
+Expected<bool> CVTypeVisitor::handleTypeServer(CVType &Record) {
   if (Record.Type == TypeLeafKind::LF_TYPESERVER2 && !Handlers.empty()) {
     auto TS = deserializeTypeServerRecord(Record);
     if (!TS)
@@ -90,16 +90,16 @@ Error CVTypeVisitor::visitTypeRecord(CVType &Record) {
 
       // If the handler processed the record, return success.
       if (*ExpectedResult)
-        return Error::success();
+        return true;
 
       // Otherwise keep searching for a handler, eventually falling out and
       // using the default record handler.
     }
   }
+  return false;
+}
 
-  if (auto EC = Callbacks.visitTypeBegin(Record))
-    return EC;
-
+Error CVTypeVisitor::finishVisitation(CVType &Record) {
   switch (Record.Type) {
   default:
     if (auto EC = Callbacks.visitUnknownType(Record))
@@ -124,6 +124,32 @@ Error CVTypeVisitor::visitTypeRecord(CVType &Record) {
   return Error::success();
 }
 
+Error CVTypeVisitor::visitTypeRecord(CVType &Record, TypeIndex Index) {
+  auto ExpectedResult = handleTypeServer(Record);
+  if (!ExpectedResult)
+    return ExpectedResult.takeError();
+  if (*ExpectedResult)
+    return Error::success();
+
+  if (auto EC = Callbacks.visitTypeBegin(Record, Index))
+    return EC;
+
+  return finishVisitation(Record);
+}
+
+Error CVTypeVisitor::visitTypeRecord(CVType &Record) {
+  auto ExpectedResult = handleTypeServer(Record);
+  if (!ExpectedResult)
+    return ExpectedResult.takeError();
+  if (*ExpectedResult)
+    return Error::success();
+
+  if (auto EC = Callbacks.visitTypeBegin(Record))
+    return EC;
+
+  return finishVisitation(Record);
+}
+
 static Error visitMemberRecord(CVMemberRecord &Record,
                                TypeVisitorCallbacks &Callbacks) {
   if (auto EC = Callbacks.visitMemberBegin(Record))
diff --git a/llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp b/llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp
index 5b8841041f8..1f2a5d7b333 100644
--- a/llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp
+++ b/llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp
@@ -112,16 +112,61 @@ StringRef TypeDatabase::getTypeName(TypeIndex Index) const {
 }
 
 const CVType &TypeDatabase::getTypeRecord(TypeIndex Index) const {
-  return TypeRecords[Index.getIndex() - TypeIndex::FirstNonSimpleIndex];
+  return TypeRecords[toArrayIndex(Index)];
 }
 
 CVType &TypeDatabase::getTypeRecord(TypeIndex Index) {
-  return TypeRecords[Index.getIndex() - TypeIndex::FirstNonSimpleIndex];
+  return TypeRecords[toArrayIndex(Index)];
 }
 
 bool TypeDatabase::containsTypeIndex(TypeIndex Index) const {
-  uint32_t I = Index.getIndex() - TypeIndex::FirstNonSimpleIndex;
-  return I < CVUDTNames.size();
+  return toArrayIndex(Index) < CVUDTNames.size();
 }
 
 uint32_t TypeDatabase::size() const { return CVUDTNames.size(); }
+
+uint32_t TypeDatabase::toArrayIndex(TypeIndex Index) const {
+  assert(Index.getIndex() >= TypeIndex::FirstNonSimpleIndex);
+  return Index.getIndex() - TypeIndex::FirstNonSimpleIndex;
+}
+
+RandomAccessTypeDatabase::RandomAccessTypeDatabase(uint32_t ExpectedSize)
+    : TypeDatabase(ExpectedSize) {
+  ValidRecords.resize(ExpectedSize);
+  CVUDTNames.resize(ExpectedSize);
+  TypeRecords.resize(ExpectedSize);
+}
+
+void RandomAccessTypeDatabase::recordType(StringRef Name, TypeIndex Index,
+                                          const CVType &Data) {
+  assert(!containsTypeIndex(Index));
+  uint32_t ZI = Index.getIndex() - TypeIndex::FirstNonSimpleIndex;
+
+  CVUDTNames[ZI] = Name;
+  TypeRecords[ZI] = Data;
+  ValidRecords.set(ZI);
+}
+
+StringRef RandomAccessTypeDatabase::getTypeName(TypeIndex Index) const {
+  assert(containsTypeIndex(Index));
+  return TypeDatabase::getTypeName(Index);
+}
+
+const CVType &RandomAccessTypeDatabase::getTypeRecord(TypeIndex Index) const {
+  assert(containsTypeIndex(Index));
+  return TypeDatabase::getTypeRecord(Index);
+}
+
+CVType &RandomAccessTypeDatabase::getTypeRecord(TypeIndex Index) {
+  assert(containsTypeIndex(Index));
+  return TypeDatabase::getTypeRecord(Index);
+}
+
+bool RandomAccessTypeDatabase::containsTypeIndex(TypeIndex Index) const {
+  if (Index.isSimple())
+    return true;
+
+  return ValidRecords.test(toArrayIndex(Index));
+}
+
+uint32_t RandomAccessTypeDatabase::size() const { return ValidRecords.count(); }
diff --git a/llvm/lib/DebugInfo/CodeView/TypeDatabaseVisitor.cpp b/llvm/lib/DebugInfo/CodeView/TypeDatabaseVisitor.cpp
index c234afd2288..8c1a651b653 100644
--- a/llvm/lib/DebugInfo/CodeView/TypeDatabaseVisitor.cpp
+++ b/llvm/lib/DebugInfo/CodeView/TypeDatabaseVisitor.cpp
@@ -15,7 +15,9 @@ using namespace llvm;
 
 using namespace llvm::codeview;
 
-Error TypeDatabaseVisitor::visitTypeBegin(CVRecord<TypeLeafKind> &Record) {
+Error TypeDatabaseVisitor::visitTypeBegin(CVType &Record) {
+  assert(TypeDB.is<TypeDatabase *>());
+
   assert(!IsInFieldList);
   // Reset Name to the empty string. If the visitor sets it, we know it.
   Name = "";
@@ -28,6 +30,34 @@ Error TypeDatabaseVisitor::visitTypeBegin(CVRecord<TypeLeafKind> &Record) {
   return Error::success();
 }
 
+StringRef TypeDatabaseVisitor::getTypeName(TypeIndex Index) const {
+  if (auto DB = TypeDB.get<TypeDatabase *>())
+    return DB->getTypeName(Index);
+  else if (auto DB = TypeDB.get<RandomAccessTypeDatabase *>())
+    return DB->getTypeName(Index);
+
+  llvm_unreachable("Invalid TypeDB Kind!");
+}
+
+StringRef TypeDatabaseVisitor::saveTypeName(StringRef Name) {
+  if (auto DB = TypeDB.get<TypeDatabase *>())
+    return DB->saveTypeName(Name);
+  else if (auto DB = TypeDB.get<RandomAccessTypeDatabase *>())
+    return DB->saveTypeName(Name);
+
+  llvm_unreachable("Invalid TypeDB Kind!");
+}
+
+Error TypeDatabaseVisitor::visitTypeBegin(CVType &Record, TypeIndex Index) {
+  assert(TypeDB.is<RandomAccessTypeDatabase *>());
+
+  if (auto EC = visitTypeBegin(Record))
+    return EC;
+
+  CurrentTypeIndex = Index;
+  return Error::success();
+}
+
 Error TypeDatabaseVisitor::visitTypeEnd(CVType &CVR) {
   if (CVR.Type == LF_FIELDLIST) {
     assert(IsInFieldList);
@@ -39,7 +69,11 @@ Error TypeDatabaseVisitor::visitTypeEnd(CVType &CVR) {
   // CVUDTNames is indexed by type index, and must have one entry for every
   // type.  Field list members are not recorded, and are only referenced by
   // their containing field list record.
-  TypeDB.recordType(Name, CVR);
+  if (auto DB = TypeDB.get<TypeDatabase *>())
+    DB->recordType(Name, CVR);
+  else if (auto DB = TypeDB.get<RandomAccessTypeDatabase *>())
+    DB->recordType(Name, CurrentTypeIndex, CVR);
+
   return Error::success();
 }
 
@@ -73,13 +107,13 @@ Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR, ArgListRecord &Args) {
   uint32_t Size = Indices.size();
   SmallString<256> TypeName("(");
   for (uint32_t I = 0; I < Size; ++I) {
-    StringRef ArgTypeName = TypeDB.getTypeName(Indices[I]);
+    StringRef ArgTypeName = getTypeName(Indices[I]);
     TypeName.append(ArgTypeName);
     if (I + 1 != Size)
       TypeName.append(", ");
   }
   TypeName.push_back(')');
-  Name = TypeDB.saveTypeName(TypeName);
+  Name = saveTypeName(TypeName);
   return Error::success();
 }
 
@@ -89,13 +123,13 @@ Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR,
   uint32_t Size = Indices.size();
   SmallString<256> TypeName("\"");
   for (uint32_t I = 0; I < Size; ++I) {
-    StringRef ArgTypeName = TypeDB.getTypeName(Indices[I]);
+    StringRef ArgTypeName = getTypeName(Indices[I]);
     TypeName.append(ArgTypeName);
     if (I + 1 != Size)
       TypeName.append("\" \"");
   }
   TypeName.push_back('\"');
-  Name = TypeDB.saveTypeName(TypeName);
+  Name = saveTypeName(TypeName);
   return Error::success();
 }
 
@@ -132,26 +166,26 @@ Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR,
 
 Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR,
                                             ProcedureRecord &Proc) {
-  StringRef ReturnTypeName = TypeDB.getTypeName(Proc.getReturnType());
-  StringRef ArgListTypeName = TypeDB.getTypeName(Proc.getArgumentList());
+  StringRef ReturnTypeName = getTypeName(Proc.getReturnType());
+  StringRef ArgListTypeName = getTypeName(Proc.getArgumentList());
   SmallString<256> TypeName(ReturnTypeName);
   TypeName.push_back(' ');
   TypeName.append(ArgListTypeName);
-  Name = TypeDB.saveTypeName(TypeName);
+  Name = saveTypeName(TypeName);
   return Error::success();
 }
 
 Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR,
                                             MemberFunctionRecord &MF) {
-  StringRef ReturnTypeName = TypeDB.getTypeName(MF.getReturnType());
-  StringRef ClassTypeName = TypeDB.getTypeName(MF.getClassType());
-  StringRef ArgListTypeName = TypeDB.getTypeName(MF.getArgumentList());
+  StringRef ReturnTypeName = getTypeName(MF.getReturnType());
+  StringRef ClassTypeName = getTypeName(MF.getClassType());
+  StringRef ArgListTypeName = getTypeName(MF.getArgumentList());
   SmallString<256> TypeName(ReturnTypeName);
   TypeName.push_back(' ');
   TypeName.append(ClassTypeName);
   TypeName.append("::");
   TypeName.append(ArgListTypeName);
-  Name = TypeDB.saveTypeName(TypeName);
+  Name = saveTypeName(TypeName);
   return Error::success();
 }
 
@@ -171,13 +205,13 @@ Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR, PointerRecord &Ptr) {
   if (Ptr.isPointerToMember()) {
     const MemberPointerInfo &MI = Ptr.getMemberInfo();
 
-    StringRef PointeeName = TypeDB.getTypeName(Ptr.getReferentType());
-    StringRef ClassName = TypeDB.getTypeName(MI.getContainingType());
+    StringRef PointeeName = getTypeName(Ptr.getReferentType());
+    StringRef ClassName = getTypeName(MI.getContainingType());
     SmallString<256> TypeName(PointeeName);
     TypeName.push_back(' ');
     TypeName.append(ClassName);
     TypeName.append("::*");
-    Name = TypeDB.saveTypeName(TypeName);
+    Name = saveTypeName(TypeName);
   } else {
     SmallString<256> TypeName;
     if (Ptr.isConst())
@@ -187,7 +221,7 @@ Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR, PointerRecord &Ptr) {
     if (Ptr.isUnaligned())
       TypeName.append("__unaligned ");
 
-    TypeName.append(TypeDB.getTypeName(Ptr.getReferentType()));
+    TypeName.append(getTypeName(Ptr.getReferentType()));
 
     if (Ptr.getMode() == PointerMode::LValueReference)
       TypeName.append("&");
@@ -197,7 +231,7 @@ Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR, PointerRecord &Ptr) {
       TypeName.append("*");
 
     if (!TypeName.empty())
-      Name = TypeDB.saveTypeName(TypeName);
+      Name = saveTypeName(TypeName);
   }
   return Error::success();
 }
@@ -205,7 +239,7 @@ Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR, PointerRecord &Ptr) {
 Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR, ModifierRecord &Mod) {
   uint16_t Mods = static_cast<uint16_t>(Mod.getModifiers());
 
-  StringRef ModifiedName = TypeDB.getTypeName(Mod.getModifiedType());
+  StringRef ModifiedName = getTypeName(Mod.getModifiedType());
   SmallString<256> TypeName;
   if (Mods & uint16_t(ModifierOptions::Const))
     TypeName.append("const ");
@@ -214,14 +248,14 @@ Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR, ModifierRecord &Mod) {
   if (Mods & uint16_t(ModifierOptions::Unaligned))
     TypeName.append("__unaligned ");
   TypeName.append(ModifiedName);
-  Name = TypeDB.saveTypeName(TypeName);
+  Name = saveTypeName(TypeName);
   return Error::success();
 }
 
 Error TypeDatabaseVisitor::visitKnownRecord(CVType &CVR,
                                             VFTableShapeRecord &Shape) {
-  Name = TypeDB.saveTypeName("<vftable " + utostr(Shape.getEntryCount()) +
-                             " methods>");
+  Name =
+      saveTypeName("<vftable " + utostr(Shape.getEntryCount()) + " methods>");
   return Error::success();
 }