[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

5 files changed, 61 insertions, 4 deletions

diff --git a/llvm/include/llvm/DebugInfo/CodeView/CVTypeVisitor.h b/llvm/include/llvm/DebugInfo/CodeView/CVTypeVisitor.h
index e9012db7602..f3122f0bf7f 100644
--- a/llvm/include/llvm/DebugInfo/CodeView/CVTypeVisitor.h
+++ b/llvm/include/llvm/DebugInfo/CodeView/CVTypeVisitor.h
@@ -26,6 +26,7 @@ public:
 
   void addTypeServerHandler(TypeServerHandler &Handler);
 
+  Error visitTypeRecord(CVType &Record, TypeIndex Index);
   Error visitTypeRecord(CVType &Record);
   Error visitMemberRecord(CVMemberRecord &Record);
 
@@ -37,6 +38,9 @@ public:
   Error visitFieldListMemberStream(BinaryStreamReader Reader);
 
 private:
+  Expected<bool> handleTypeServer(CVType &Record);
+  Error finishVisitation(CVType &Record);
+
   /// The interface to the class that gets notified of each visitation.
   TypeVisitorCallbacks &Callbacks;
 
diff --git a/llvm/include/llvm/DebugInfo/CodeView/TypeDatabase.h b/llvm/include/llvm/DebugInfo/CodeView/TypeDatabase.h
index be7b19e7df0..c4fb63628ee 100644
--- a/llvm/include/llvm/DebugInfo/CodeView/TypeDatabase.h
+++ b/llvm/include/llvm/DebugInfo/CodeView/TypeDatabase.h
@@ -10,6 +10,7 @@
 #ifndef LLVM_DEBUGINFO_CODEVIEW_TYPEDATABASE_H
 #define LLVM_DEBUGINFO_CODEVIEW_TYPEDATABASE_H
 
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
@@ -20,6 +21,8 @@
 namespace llvm {
 namespace codeview {
 class TypeDatabase {
+  friend class RandomAccessTypeVisitor;
+
 public:
   explicit TypeDatabase(uint32_t ExpectedSize);
 
@@ -41,7 +44,9 @@ public:
 
   uint32_t size() const;
 
-private:
+protected:
+  uint32_t toArrayIndex(TypeIndex Index) const;
+
   BumpPtrAllocator Allocator;
 
   /// All user defined type records in .debug$T live in here. Type indices
@@ -52,6 +57,28 @@ private:
 
   StringSaver TypeNameStorage;
 };
+
+class RandomAccessTypeDatabase : private TypeDatabase {
+public:
+  explicit RandomAccessTypeDatabase(uint32_t ExpectedSize);
+
+  /// Records the name of a type, and reserves its type index.
+  void recordType(StringRef Name, TypeIndex Index, const CVType &Data);
+
+  using TypeDatabase::saveTypeName;
+
+  StringRef getTypeName(TypeIndex Index) const;
+
+  const CVType &getTypeRecord(TypeIndex Index) const;
+  CVType &getTypeRecord(TypeIndex Index);
+
+  bool containsTypeIndex(TypeIndex Index) const;
+
+  uint32_t size() const;
+
+private:
+  BitVector ValidRecords;
+};
 }
 }
 
diff --git a/llvm/include/llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h b/llvm/include/llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h
index 39d234cf981..cbb509693a4 100644
--- a/llvm/include/llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h
+++ b/llvm/include/llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h
@@ -10,6 +10,8 @@
 #ifndef LLVM_DEBUGINFO_CODEVIEW_TYPEDATABASEVISITOR_H
 #define LLVM_DEBUGINFO_CODEVIEW_TYPEDATABASEVISITOR_H
 
+#include "llvm/ADT/PointerUnion.h"
+
 #include "llvm/DebugInfo/CodeView/TypeDatabase.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
@@ -21,11 +23,14 @@ namespace codeview {
 /// Dumper for CodeView type streams found in COFF object files and PDB files.
 class TypeDatabaseVisitor : public TypeVisitorCallbacks {
 public:
-  explicit TypeDatabaseVisitor(TypeDatabase &TypeDB) : TypeDB(TypeDB) {}
+  explicit TypeDatabaseVisitor(TypeDatabase &TypeDB) : TypeDB(&TypeDB) {}
+  explicit TypeDatabaseVisitor(RandomAccessTypeDatabase &TypeDB)
+      : TypeDB(&TypeDB) {}
 
   /// Paired begin/end actions for all types. Receives all record data,
   /// including the fixed-length record prefix.
   Error visitTypeBegin(CVType &Record) override;
+  Error visitTypeBegin(CVType &Record, TypeIndex Index) override;
   Error visitTypeEnd(CVType &Record) override;
   Error visitMemberBegin(CVMemberRecord &Record) override;
   Error visitMemberEnd(CVMemberRecord &Record) override;
@@ -39,12 +44,18 @@ public:
 #include "TypeRecords.def"
 
 private:
+  StringRef getTypeName(TypeIndex Index) const;
+  StringRef saveTypeName(StringRef Name);
+
   bool IsInFieldList = false;
 
   /// Name of the current type. Only valid before visitTypeEnd.
   StringRef Name;
+  /// Current type index.  Only valid before visitTypeEnd, and if we are
+  /// visiting a random access type database.
+  TypeIndex CurrentTypeIndex;
 
-  TypeDatabase &TypeDB;
+  PointerUnion<TypeDatabase *, RandomAccessTypeDatabase *> TypeDB;
 };
 
 } // end namespace codeview
diff --git a/llvm/include/llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h b/llvm/include/llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h
index f2512969104..ed48df33249 100644
--- a/llvm/include/llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h
+++ b/llvm/include/llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h
@@ -47,6 +47,14 @@ public:
     return Error::success();
   }
 
+  Error visitTypeBegin(CVType &Record, TypeIndex Index) override {
+    for (auto Visitor : Pipeline) {
+      if (auto EC = Visitor->visitTypeBegin(Record, Index))
+        return EC;
+    }
+    return Error::success();
+  }
+
   Error visitTypeEnd(CVType &Record) override {
     for (auto Visitor : Pipeline) {
       if (auto EC = Visitor->visitTypeEnd(Record))
diff --git a/llvm/include/llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h b/llvm/include/llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h
index 5e27df346b0..2950c7d27cb 100644
--- a/llvm/include/llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h
+++ b/llvm/include/llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h
@@ -26,8 +26,15 @@ public:
   virtual Error visitUnknownType(CVType &Record) { return Error::success(); }
   /// Paired begin/end actions for all types. Receives all record data,
   /// including the fixed-length record prefix.  visitTypeBegin() should return
-  /// the type of the Record, or an error if it cannot be determined.
+  /// the type of the Record, or an error if it cannot be determined.  Exactly
+  /// one of the two visitTypeBegin methods will be called, depending on whether
+  /// records are being visited sequentially or randomly.  An implementation
+  /// should be prepared to handle both (or assert if it can't handle random
+  /// access visitation).
   virtual Error visitTypeBegin(CVType &Record) { return Error::success(); }
+  virtual Error visitTypeBegin(CVType &Record, TypeIndex Index) {
+    return Error::success();
+  }
   virtual Error visitTypeEnd(CVType &Record) { return Error::success(); }
 
   virtual Error visitUnknownMember(CVMemberRecord &Record) {