Provide a common interface for all collections of types.

[zturner]

Summary

Right now we have multiple notions of things that represent collections of types. Most commonly used are TypeDatabase, which is supposed to keep mappings from TypeIndex to type name when reading a type stream, which happens when reading PDBs. And also TypeTableBuilder, which is used to build up a collection of types dynamically which we will later serialize (i.e. when writing PDBs).

But often you just want to do some operation on a collection of types, and you may want to do the same operation on any kind of collection. For example, you might want to merge two TypeTableBuilders or you might want to merge two type streams that you loaded from various files.

This dichotomy between reading and writing is responsible for a lot of the existing code duplication and overlapping responsibilities in the existing CodeView library classes. For example, after building up a TypeTableBuilder with a bunch of type records, if we want to dump it we have to re-invent a bunch of extra glue because our dumper takes a TypeDatabase or a CVTypeArray, which are both incompatible with TypeTableBuilder.

This patch introduces an abstract base class called TypeCollection which is shared between the various type collection like things. Wherever we previously stored a TypeDatabase& in some common class, we now store a TypeCollection&.

The advantage of this is that all the details of how the collection are implemented, such as lazy deserialization of partial type streams, is completely transparent and you can just treat any collection of types the same regardless of where it came from.

This is a large patch, but I cannot come up with a way to make it smaller. I have D33229 in the queue for review, and D33245 already submitted which themselves were already broken off from this to make it smaller, so I think this may be the best I can do.

[rnk]

Do you think all these TypeCollections should eventually just be the same thing? So, I could read a TypeCollection from a PDB, and then add more type records to it like I would with TypeTableBuilder. Then we would have a full read/write/edit API for types, which is something we seem to want for incremental PDB writing.

llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h

48

I feel like LazyRandom is really implementation-detail oriented. Basically, this is a TypeCollection that's efficient for PDBs. "Random" also suggests that it generates random results, which would be weird.

Maybe call it PDBTypeCollection? Or TypeStreamCollection? It seems awkward to have a class starting with PDB in DebugInfo/CodeView.

[zturner]

In D33293#757740, @rnk wrote:

Do you think all these TypeCollections should eventually just be the same thing? So, I could read a TypeCollection from a PDB, and then add more type records to it like I would with TypeTableBuilder. Then we would have a full read/write/edit API for types, which is something we seem to want for incremental PDB writing.

Maybe, it's something that I've been thinking about, but it's not entirely obvious how it would work. The reading side is optimized around memory usage, meaning that since we already have the entire PDB file mapped into memory, we don't really want to allocate hundreds of megabytes more memory just to copy the data from some type records. On the other hand, When you're writing you have no choice but to allocate records individually on the fly as you determine what kind of records you're going to need.

It's not entirely obvious how to merge these into one class that doesn't sacrifice memory efficiency on the reading side, but still allows each record to be allocated from private storage

llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h

48

I don't think it's only efficient for PDBs. It's just most efficient for PDBs. It's still very useful when all you have is a .degug$T section from an object file. Even though you don't have any partial offsets, random access is still a very useful feature.

Heck, we could even put a TypeIndexOffset array into the object file in a magic section, and get all the benefits of lazy deserialization even without a PDB at all.

[zturner]

doh, I didn't actually submit this. I attached the wrong review to the commit message in Phabricator.

[rnk]

I don't think you uploaded the right patch

lld/COFF/PDB.cpp

 //===- PDB.cpp ------------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "PDB.h"
 #include "Chunks.h"
 #include "Config.h"
 #include "Error.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "llvm/DebugInfo/CodeView/CVDebugRecord.h"
-#include "llvm/DebugInfo/CodeView/CVTypeDumper.h"
+#include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
+#include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
 #include "llvm/DebugInfo/CodeView/SymbolDumper.h"
 #include "llvm/DebugInfo/CodeView/TypeDatabase.h"
 #include "llvm/DebugInfo/CodeView/TypeDumpVisitor.h"
 #include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
 #include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
 #include "llvm/DebugInfo/MSF/MSFCommon.h"
 #include "llvm/DebugInfo/PDB/Native/DbiStream.h"

 }
 
 static void dumpDebugT(ScopedPrinter &W, ObjectFile *File) {
   ListScope LS(W, "DebugT");
   ArrayRef<uint8_t> Data = getDebugSection(File, ".debug$T");
   if (Data.empty())
     return;
 
-  TypeDatabase TDB(0);
-  TypeDumpVisitor TDV(TDB, &W, false);
+  LazyRandomTypeCollection Types(Data, 100);
+  TypeDumpVisitor TDV(Types, &W, false);
   // Use a default implementation that does not follow type servers and instead
   // just dumps the contents of the TypeServer2 record.
-  CVTypeDumper TypeDumper(TDB);
-  if (auto EC = TypeDumper.dump(Data, TDV))
+  if (auto EC = codeview::visitTypeStream(Types, TDV))
     fatal(EC, "CVTypeDumper::dump failed");
 }
 
 static void dumpDebugS(ScopedPrinter &W, ObjectFile *File) {
   ListScope LS(W, "DebugS");
   ArrayRef<uint8_t> Data = getDebugSection(File, ".debug$S");
   if (Data.empty())
     return;

llvm/include/llvm/DebugInfo/CodeView/CVRecord.h

 template <typename Kind> class CVRecord {
 public:
   CVRecord() = default;
   CVRecord(Kind K, ArrayRef<uint8_t> Data) : Type(K), RecordData(Data) {}
 
   uint32_t length() const { return RecordData.size(); }
   Kind kind() const { return Type; }
   ArrayRef<uint8_t> data() const { return RecordData; }
+  StringRef str_data() const {
+    return StringRef(reinterpret_cast<const char *>(RecordData.data()),
+                     RecordData.size());
+  }
 
   ArrayRef<uint8_t> content() const {
     return RecordData.drop_front(sizeof(RecordPrefix));
   }
 
   Optional<uint32_t> hash() const { return Hash; }
 
   void setHash(uint32_t Value) { Hash = Value; }

llvm/include/llvm/DebugInfo/CodeView/CVTypeDumper.h

-//===-- CVTypeDumper.h - CodeView type info dumper --------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_DEBUGINFO_CODEVIEW_CVTYPEDUMPER_H
-#define LLVM_DEBUGINFO_CODEVIEW_CVTYPEDUMPER_H
-
-#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/StringSet.h"
-#include "llvm/DebugInfo/CodeView/TypeDatabase.h"
-#include "llvm/DebugInfo/CodeView/TypeIndex.h"
-#include "llvm/DebugInfo/CodeView/TypeRecord.h"
-#include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
-#include "llvm/Support/ScopedPrinter.h"
-
-namespace llvm {
-
-namespace codeview {
-
-class TypeServerHandler;
-
-/// Dumper for CodeView type streams found in COFF object files and PDB files.
-class CVTypeDumper {
-public:
-  explicit CVTypeDumper(TypeDatabase &TypeDB,
-                        TypeServerHandler *Handler = nullptr)
-      : TypeDB(TypeDB), Handler(Handler) {}
-
-  /// Dumps one type record.  Returns false if there was a type parsing error,
-  /// and true otherwise.  This should be called in order, since the dumper
-  /// maintains state about previous records which are necessary for cross
-  /// type references.
-  Error dump(const CVType &Record, TypeVisitorCallbacks &Dumper);
-
-  /// Dumps the type records in Types. Returns false if there was a type stream
-  /// parse error, and true otherwise.
-  Error dump(const CVTypeArray &Types, TypeVisitorCallbacks &Dumper);
-
-  /// Dumps the type records in Data. Returns false if there was a type stream
-  /// parse error, and true otherwise. Use this method instead of the
-  /// CVTypeArray overload when type records are laid out contiguously in
-  /// memory.
-  Error dump(ArrayRef<uint8_t> Data, TypeVisitorCallbacks &Dumper);
-
-  static void printTypeIndex(ScopedPrinter &Printer, StringRef FieldName,
-                             TypeIndex TI, TypeDatabase &DB);
-
-private:
-  TypeDatabase &TypeDB;
-  TypeServerHandler *Handler;
-};
-
-} // end namespace codeview
-} // end namespace llvm
-
-#endif // LLVM_DEBUGINFO_CODEVIEW_TYPEDUMPER_H

llvm/include/llvm/DebugInfo/CodeView/CVTypeVisitor.h

 //===- CVTypeVisitor.h ------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_CODEVIEW_CVTYPEVISITOR_H
 #define LLVM_DEBUGINFO_CODEVIEW_CVTYPEVISITOR_H
 
-#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/DebugInfo/CodeView/CVRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
-#include "llvm/DebugInfo/CodeView/TypeServerHandler.h"
-#include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
 #include "llvm/Support/Error.h"
 
 namespace llvm {
 namespace codeview {
-
-class CVTypeVisitor {
-public:
-  explicit CVTypeVisitor(TypeVisitorCallbacks &Callbacks);
-
-  void addTypeServerHandler(TypeServerHandler &Handler);
-
-  Error visitTypeRecord(CVType &Record, TypeIndex Index);
-  Error visitTypeRecord(CVType &Record);
-  Error visitMemberRecord(CVMemberRecord Record);
-
-  /// Visits the type records in Data. Sets the error flag on parse failures.
-  Error visitTypeStream(const CVTypeArray &Types);
-  Error visitTypeStream(CVTypeRange Types);
-
-  Error visitFieldListMemberStream(ArrayRef<uint8_t> FieldList);
-  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;
-
-  TinyPtrVector<TypeServerHandler *> Handlers;
-};
+class TypeCollection;
+class TypeServerHandler;
+class TypeVisitorCallbacks;
 
 enum VisitorDataSource {
   VDS_BytesPresent, // The record bytes are passed into the the visitation
                     // function.  The algorithm should first deserialize them
                     // before passing them on through the pipeline.
   VDS_BytesExternal // The record bytes are not present, and it is the
                     // responsibility of the visitor callback interface to
                     // supply the bytes.

 
 Error visitMemberRecordStream(ArrayRef<uint8_t> FieldList,
                               TypeVisitorCallbacks &Callbacks);
 
 Error visitTypeStream(const CVTypeArray &Types, TypeVisitorCallbacks &Callbacks,
                       TypeServerHandler *TS = nullptr);
 Error visitTypeStream(CVTypeRange Types, TypeVisitorCallbacks &Callbacks,
                       TypeServerHandler *TS = nullptr);
+Error visitTypeStream(TypeCollection &Types, TypeVisitorCallbacks &Callbacks,
+                      TypeServerHandler *TS = nullptr);
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_CVTYPEVISITOR_H

llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h

+//===- LazyRandomTypeCollection.h ---------------------------- *- C++ --*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
+#define LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
+
+#include "llvm/DebugInfo/CodeView/TypeCollection.h"
+#include "llvm/DebugInfo/CodeView/TypeDatabase.h"
+#include "llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h"
+#include "llvm/DebugInfo/CodeView/TypeIndex.h"
+#include "llvm/DebugInfo/CodeView/TypeRecord.h"
+#include "llvm/Support/Error.h"
+
+namespace llvm {
+namespace codeview {
+
+class TypeDatabase;
+class TypeVisitorCallbacks;
+
+/// \brief Provides amortized O(1) random access to a CodeView type stream.
+/// Normally to access a type from a type stream, you must know its byte
+/// offset into the type stream, because type records are variable-lengthed.
+/// However, this is not the way we prefer to access them.  For example, given
+/// a symbol record one of the fields may be the TypeIndex of the symbol's
+/// type record.  Or given a type record such as an array type, there might
+/// be a TypeIndex for the element type.  Sequential access is perfect when
+/// we're just dumping every entry, but it's very poor for real world usage.
+///
+/// Type streams in PDBs contain an additional field which is a list of pairs
+/// containing indices and their corresponding offsets, roughly every ~8KB of
+/// record data.  This general idea need not be confined to PDBs though.  By
+/// supplying such an array, the producer of a type stream can allow the
+/// consumer much better access time, because the consumer can find the nearest
+/// index in this array, and do a linear scan forward only from there.
+///
+/// LazyRandomTypeCollection implements this algorithm, but additionally goes
+/// one step further by caching offsets of every record that has been visited at
+/// least once.  This way, even repeated visits of the same record will never
+/// require more than one linear scan.  For a type stream of N elements divided
+/// into M chunks of roughly equal size, this yields a worst case lookup time
+/// of O(N/M) and an amortized time of O(1).
+class LazyRandomTypeCollection : public TypeCollection {
+  typedef FixedStreamArray<TypeIndexOffset> PartialOffsetArray;
+
+public:
+  explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
+  LazyRandomTypeCollection(StringRef Data, uint32_t RecordCountHint);
+  LazyRandomTypeCollection(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
+  LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint,
+                           PartialOffsetArray PartialOffsets);
+  LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint);
+
+  void reset(ArrayRef<uint8_t> Data);
+  void reset(StringRef Data);
+
+  CVType getType(TypeIndex Index) override;
+  StringRef getTypeName(TypeIndex Index) override;
+  bool contains(TypeIndex Index) override;
+  uint32_t size() override;
+  uint32_t capacity() override;
+  TypeIndex getFirst() override;
+  Optional<TypeIndex> getNext(TypeIndex Prev) override;
+
+private:
+  const TypeDatabase &database() const { return Database; }
+  Error ensureTypeExists(TypeIndex Index);
+
+  Error visitRangeForType(TypeIndex TI);
+  Error fullScanForType(TypeIndex TI);
+  Error visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End);
+  Error visitOneRecord(TypeIndex TI, uint32_t Offset, CVType &Record);
+
+  /// Visited records get automatically added to the type database.
+  TypeDatabase Database;
+
+  /// The type array to allow random access visitation of.
+  CVTypeArray Types;
+
+  /// The database visitor which adds new records to the database.
+  TypeDatabaseVisitor DatabaseVisitor;
+
+  /// A vector mapping type indices to type offset.  For every record that has
+  /// been visited, contains the absolute offset of that record in the record
+  /// array.
+  std::vector<uint32_t> KnownOffsets;
+
+  /// An array of index offsets for the given type stream, allowing log(N)
+  /// lookups of a type record by index.  Similar to KnownOffsets but only
+  /// contains offsets for some type indices, some of which may not have
+  /// ever been visited.
+  PartialOffsetArray PartialOffsets;
+};
+
+} // end namespace codeview
+} // end namespace llvm
+
+#endif // LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H

llvm/include/llvm/DebugInfo/CodeView/RandomAccessTypeVisitor.h

-//===- RandomAccessTypeVisitor.h ------------------------------ *- C++ --*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_DEBUGINFO_CODEVIEW_RANDOMACCESSTYPEVISITOR_H
-#define LLVM_DEBUGINFO_CODEVIEW_RANDOMACCESSTYPEVISITOR_H
-
-#include "llvm/ADT/TinyPtrVector.h"
-#include "llvm/DebugInfo/CodeView/TypeDatabase.h"
-#include "llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h"
-#include "llvm/DebugInfo/CodeView/TypeIndex.h"
-#include "llvm/DebugInfo/CodeView/TypeRecord.h"
-#include "llvm/Support/Error.h"
-
-namespace llvm {
-namespace codeview {
-
-class TypeDatabase;
-class TypeServerHandler;
-class TypeVisitorCallbacks;
-
-/// \brief Provides amortized O(1) random access to a CodeView type stream.
-/// Normally to access a type from a type stream, you must know its byte
-/// offset into the type stream, because type records are variable-lengthed.
-/// However, this is not the way we prefer to access them.  For example, given
-/// a symbol record one of the fields may be the TypeIndex of the symbol's
-/// type record.  Or given a type record such as an array type, there might
-/// be a TypeIndex for the element type.  Sequential access is perfect when
-/// we're just dumping every entry, but it's very poor for real world usage.
-///
-/// Type streams in PDBs contain an additional field which is a list of pairs
-/// containing indices and their corresponding offsets, roughly every ~8KB of
-/// record data.  This general idea need not be confined to PDBs though.  By
-/// supplying such an array, the producer of a type stream can allow the
-/// consumer much better access time, because the consumer can find the nearest
-/// index in this array, and do a linear scan forward only from there.
-///
-/// RandomAccessTypeVisitor implements this algorithm, but additionally goes one
-/// step further by caching offsets of every record that has been visited at
-/// least once.  This way, even repeated visits of the same record will never
-/// require more than one linear scan.  For a type stream of N elements divided
-/// into M chunks of roughly equal size, this yields a worst case lookup time
-/// of O(N/M) and an amortized time of O(1).
-class RandomAccessTypeVisitor {
-  typedef FixedStreamArray<TypeIndexOffset> PartialOffsetArray;
-
-public:
-  RandomAccessTypeVisitor(const CVTypeArray &Types, uint32_t NumRecords,
-                          PartialOffsetArray PartialOffsets);
-
-  Error visitTypeIndex(TypeIndex Index, TypeVisitorCallbacks &Callbacks);
-
-  const TypeDatabase &database() const { return Database; }
-
-private:
-  Error visitRangeForType(TypeIndex TI);
-  Error visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End);
-
-  /// Visited records get automatically added to the type database.
-  TypeDatabase Database;
-
-  /// The type array to allow random access visitation of.
-  const CVTypeArray &Types;
-
-  /// The database visitor which adds new records to the database.
-  TypeDatabaseVisitor DatabaseVisitor;
-
-  /// A vector mapping type indices to type offset.  For every record that has
-  /// been visited, contains the absolute offset of that record in the record
-  /// array.
-  std::vector<uint32_t> KnownOffsets;
-
-  /// An array of index offsets for the given type stream, allowing log(N)
-  /// lookups of a type record by index.  Similar to KnownOffsets but only
-  /// contains offsets for some type indices, some of which may not have
-  /// ever been visited.
-  PartialOffsetArray PartialOffsets;
-};
-
-} // end namespace codeview
-} // end namespace llvm
-
-#endif // LLVM_DEBUGINFO_CODEVIEW_RANDOMACCESSTYPEVISITOR_H

llvm/include/llvm/DebugInfo/CodeView/SymbolDumper.h

 #include "llvm/DebugInfo/CodeView/SymbolDumpDelegate.h"
 #include "llvm/DebugInfo/CodeView/SymbolRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 
 namespace llvm {
 class ScopedPrinter;
 
 namespace codeview {
-class TypeDatabase;
+class TypeCollection;
 
 /// Dumper for CodeView symbol streams found in COFF object files and PDB files.
 class CVSymbolDumper {
 public:
-  CVSymbolDumper(ScopedPrinter &W, TypeDatabase &TypeDB,
+  CVSymbolDumper(ScopedPrinter &W, TypeCollection &Types,
                  std::unique_ptr<SymbolDumpDelegate> ObjDelegate,
                  bool PrintRecordBytes)
-      : W(W), TypeDB(TypeDB), ObjDelegate(std::move(ObjDelegate)),
+      : W(W), Types(Types), ObjDelegate(std::move(ObjDelegate)),
         PrintRecordBytes(PrintRecordBytes) {}
 
   /// Dumps one type record.  Returns false if there was a type parsing error,
   /// and true otherwise.  This should be called in order, since the dumper
   /// maintains state about previous records which are necessary for cross
   /// type references.
   Error dump(CVRecord<SymbolKind> &Record);
 
   /// Dumps the type records in Data. Returns false if there was a type stream
   /// parse error, and true otherwise.
   Error dump(const CVSymbolArray &Symbols);
 
 private:
   ScopedPrinter &W;
-  TypeDatabase &TypeDB;
+  TypeCollection &Types;
   std::unique_ptr<SymbolDumpDelegate> ObjDelegate;
 
   bool PrintRecordBytes;
 };
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_SYMBOLDUMPER_H

llvm/include/llvm/DebugInfo/CodeView/TypeCollection.h

+//===- TypeCollection.h - A collection of CodeView type records -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_CODEVIEW_TYPECOLLECTION_H
+#define LLVM_DEBUGINFO_CODEVIEW_TYPECOLLECTION_H
+
+#include "llvm/ADT/StringRef.h"
+
+#include "llvm/DebugInfo/CodeView/TypeIndex.h"
+#include "llvm/DebugInfo/CodeView/TypeRecord.h"
+
+namespace llvm {
+namespace codeview {
+class TypeCollection {
+public:
+  virtual ~TypeCollection() = default;
+
+  bool empty() { return size() == 0; }
+
+  virtual TypeIndex getFirst() = 0;
+  virtual Optional<TypeIndex> getNext(TypeIndex Prev) = 0;
+
+  virtual CVType getType(TypeIndex Index) = 0;
+  virtual StringRef getTypeName(TypeIndex Index) = 0;
+  virtual bool contains(TypeIndex Index) = 0;
+  virtual uint32_t size() = 0;
+  virtual uint32_t capacity() = 0;
+};
+}
+}
+
+#endif

llvm/include/llvm/DebugInfo/CodeView/TypeDatabase.h

 //===- TypeDatabase.h - A collection of CodeView type records ---*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #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/TypeCollection.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/StringSaver.h"
 
 namespace llvm {
 namespace codeview {
-class TypeDatabase {
+class TypeDatabase : public TypeCollection {
   friend class RandomAccessTypeVisitor;
 
 public:
   explicit TypeDatabase(uint32_t Capacity);
 
   /// Records the name of a type, and reserves its type index.
   TypeIndex appendType(StringRef Name, const CVType &Data);
 
   /// Records the name of a type, and reserves its type index.
   void recordType(StringRef Name, TypeIndex Index, const CVType &Data);
 
   /// Saves the name in a StringSet and creates a stable StringRef.
   StringRef saveTypeName(StringRef TypeName);
 
   StringRef getTypeName(TypeIndex Index) const;
 
   const CVType &getTypeRecord(TypeIndex Index) const;
   CVType &getTypeRecord(TypeIndex Index);
 
   bool contains(TypeIndex Index) const;
-
   uint32_t size() const;
   uint32_t capacity() const;
   bool empty() const;
 
-  TypeIndex getAppendIndex() const;
+  CVType getType(TypeIndex Index) override;
+  StringRef getTypeName(TypeIndex Index) override;
+  bool contains(TypeIndex Index) override;
+  uint32_t size() override;
+  uint32_t capacity() override;
+
+  TypeIndex getFirst() override;
+  Optional<TypeIndex> getNext(TypeIndex Prev) override;
+
+  Optional<TypeIndex> largestTypeIndexLessThan(TypeIndex TI) const;
 
 private:
+  TypeIndex getAppendIndex() const;
+
   void grow();
+  void grow(TypeIndex Index);
 
   BumpPtrAllocator Allocator;
 
   uint32_t Count = 0;
+  TypeIndex LargestTypeIndex;
 
   /// All user defined type records in .debug$T live in here. Type indices
   /// greater than 0x1000 are user defined. Subtract 0x1000 from the index to
   /// index into this vector.
   SmallVector<StringRef, 10> CVUDTNames;
   SmallVector<CVType, 10> TypeRecords;
 
   StringSaver TypeNameStorage;
 
   BitVector ValidRecords;
 };
 }
 }
 
 #endif
 No newline at end of file

llvm/include/llvm/DebugInfo/CodeView/TypeDumpVisitor.h

 //===-- TypeDumpVisitor.h - CodeView type info dumper -----------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_CODEVIEW_TYPEDUMPVISITOR_H
 #define LLVM_DEBUGINFO_CODEVIEW_TYPEDUMPVISITOR_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringSet.h"
-#include "llvm/DebugInfo/CodeView/TypeDatabase.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
 
 namespace llvm {
 class ScopedPrinter;
 
 namespace codeview {
 
+class TypeCollection;
+
 /// Dumper for CodeView type streams found in COFF object files and PDB files.
 class TypeDumpVisitor : public TypeVisitorCallbacks {
 public:
-  TypeDumpVisitor(TypeDatabase &TypeDB, ScopedPrinter *W, bool PrintRecordBytes)
-      : W(W), PrintRecordBytes(PrintRecordBytes), TypeDB(TypeDB) {}
+  TypeDumpVisitor(TypeCollection &TpiTypes, ScopedPrinter *W,
+                  bool PrintRecordBytes)
+      : W(W), PrintRecordBytes(PrintRecordBytes), TpiTypes(TpiTypes) {}
 
   /// When dumping types from an IPI stream in a PDB, a type index may refer to
   /// a type or an item ID. The dumper will lookup the "name" of the index in
   /// the item database if appropriate. If ItemDB is null, it will use TypeDB,
   /// which is correct when dumping types from an object file (/Z7).
-  void setItemDB(TypeDatabase &DB) { ItemDB = &DB; }
+  void setIpiTypes(TypeCollection &Types) { IpiTypes = &Types; }
 
   void printTypeIndex(StringRef FieldName, TypeIndex TI) const;
 
   void printItemIndex(StringRef FieldName, TypeIndex TI) const;
 
   /// Action to take on unknown types. By default, they are ignored.
   Error visitUnknownType(CVType &Record) override;
   Error visitUnknownMember(CVMemberRecord &Record) override;

 private:
   void printMemberAttributes(MemberAttributes Attrs);
   void printMemberAttributes(MemberAccess Access, MethodKind Kind,
                              MethodOptions Options);
 
   /// Get the database of indices for the stream that we are dumping. If ItemDB
   /// is set, then we must be dumping an item (IPI) stream. This will also
   /// always get the appropriate DB for printing item names.
-  TypeDatabase &getSourceDB() const { return ItemDB ? *ItemDB : TypeDB; }
+  TypeCollection &getSourceTypes() const {
+    return IpiTypes ? *IpiTypes : TpiTypes;
+  }
 
   ScopedPrinter *W;
 
   bool PrintRecordBytes = false;
 
-  TypeDatabase &TypeDB;
-  TypeDatabase *ItemDB = nullptr;
+  TypeCollection &TpiTypes;
+  TypeCollection *IpiTypes = nullptr;
 };
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif

llvm/include/llvm/DebugInfo/CodeView/TypeIndex.h

 #ifndef LLVM_DEBUGINFO_CODEVIEW_TYPEINDEX_H
 #define LLVM_DEBUGINFO_CODEVIEW_TYPEINDEX_H
 
 #include "llvm/Support/Endian.h"
 #include <cassert>
 #include <cinttypes>
 
 namespace llvm {
+
+class ScopedPrinter;
+
 namespace codeview {
 
+class TypeCollection;
+
 enum class SimpleTypeKind : uint32_t {
   None = 0x0000,          // uncharacterized type (no type)
   Void = 0x0003,          // void
   NotTranslated = 0x0007, // type not translated by cvpack
   HResult = 0x0008,       // OLE/COM HRESULT
 
   SignedCharacter = 0x0010,   // 8 bit signed
   UnsignedCharacter = 0x0020, // 8 bit unsigned
public:
 
   friend inline TypeIndex operator-(const TypeIndex &A, uint32_t N) {
     assert(A.getIndex() >= N);
     TypeIndex Result(A);
     Result -= N;
     return Result;
   }
 
+  friend inline uint32_t operator-(const TypeIndex &A, const TypeIndex &B) {
+    assert(A >= B);
+    return A.toArrayIndex() - B.toArrayIndex();
+  }
+
 private:
   support::ulittle32_t Index;
 };
 
 // Used for pseudo-indexing an array of type records.  An array of such records
 // sorted by TypeIndex can allow log(N) lookups even though such a type record
 // stream does not provide random access.
 struct TypeIndexOffset {
   TypeIndex Type;
   support::ulittle32_t Offset;
 };
+
+void printTypeIndex(ScopedPrinter &Printer, StringRef FieldName, TypeIndex TI,
+                    TypeCollection &Types);
 }
 }
 
 #endif

llvm/include/llvm/DebugInfo/CodeView/TypeTableCollection.h

+//===- TypeTableCollection.h ---------------------------------- *- C++ --*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_CODEVIEW_TYPETABLECOLLECTION_H
+#define LLVM_DEBUGINFO_CODEVIEW_TYPETABLECOLLECTION_H
+
+#include "llvm/DebugInfo/CodeView/TypeCollection.h"
+#include "llvm/DebugInfo/CodeView/TypeDatabase.h"
+
+namespace llvm {
+namespace codeview {
+
+class TypeTableCollection : public TypeCollection {
+public:
+  explicit TypeTableCollection(ArrayRef<MutableArrayRef<uint8_t>> Records);
+
+  TypeIndex getFirst() override;
+  Optional<TypeIndex> getNext(TypeIndex Prev) override;
+
+  CVType getType(TypeIndex Index) override;
+  StringRef getTypeName(TypeIndex Index) override;
+  bool contains(TypeIndex Index) override;
+  uint32_t size() override;
+  uint32_t capacity() override;
+
+private:
+  bool hasCapacityFor(TypeIndex Index) const;
+  void ensureTypeExists(TypeIndex Index);
+
+  ArrayRef<MutableArrayRef<uint8_t>> Records;
+  TypeDatabase Database;
+};
+}
+}
+
+#endif

llvm/include/llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h

 
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/Support/Error.h"
 
 namespace llvm {
 namespace codeview {
 
 class TypeVisitorCallbacks {
-  friend class CVTypeVisitor;
-
 public:
   virtual ~TypeVisitorCallbacks() = default;
 
   /// Action to take on unknown types. By default, they are ignored.
   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.  Exactly

llvm/include/llvm/DebugInfo/PDB/Native/PDBTypeServerHandler.h

 //===- PDBTypeServerHandler.h -----------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_PDB_PDBTYPESERVERHANDLER_H
 #define LLVM_DEBUGINFO_PDB_PDBTYPESERVERHANDLER_H
 
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
-#include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeServerHandler.h"
 #include "llvm/DebugInfo/PDB/Native/NativeSession.h"
 #include "llvm/DebugInfo/PDB/PDBTypes.h"
 
 #include <memory>
 #include <string>
 

llvm/lib/CodeGen/AsmPrinter/CodeViewDebug.cpp

 //===-- llvm/lib/CodeGen/AsmPrinter/CodeViewDebug.cpp --*- C++ -*--===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains support for writing Microsoft CodeView debug info.
 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeViewDebug.h"
 #include "llvm/ADT/TinyPtrVector.h"
-#include "llvm/DebugInfo/CodeView/CVTypeDumper.h"
 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 #include "llvm/DebugInfo/CodeView/CodeView.h"
 #include "llvm/DebugInfo/CodeView/Line.h"
 #include "llvm/DebugInfo/CodeView/ModuleDebugInlineeLinesFragment.h"
 #include "llvm/DebugInfo/CodeView/SymbolRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeDatabase.h"
 #include "llvm/DebugInfo/CodeView/TypeDumpVisitor.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
+#include "llvm/DebugInfo/CodeView/TypeTableCollection.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCSectionCOFF.h"
 #include "llvm/MC/MCSymbol.h"
 #include "llvm/Support/BinaryByteStream.h"
 #include "llvm/Support/BinaryStreamReader.h"
void CodeViewDebug::emitTypeInformation() {
 
   SmallString<8> CommentPrefix;
   if (OS.isVerboseAsm()) {
     CommentPrefix += '\t';
     CommentPrefix += Asm->MAI->getCommentString();
     CommentPrefix += ' ';
   }
 
-  TypeDatabase TypeDB(TypeTable.records().size());
-  CVTypeDumper CVTD(TypeDB);
-  TypeTable.ForEachRecord([&](TypeIndex Index, ArrayRef<uint8_t> Record) {
+  TypeTableCollection Table(TypeTable.records());
+  Optional<TypeIndex> B = Table.getFirst();
+  do {
+    // This will fail if the record data is invalid.
+    CVType Record = Table.getType(*B);
+
     if (OS.isVerboseAsm()) {
       // Emit a block comment describing the type record for readability.
       SmallString<512> CommentBlock;
       raw_svector_ostream CommentOS(CommentBlock);
       ScopedPrinter SP(CommentOS);
       SP.setPrefix(CommentPrefix);
-      TypeDumpVisitor TDV(TypeDB, &SP, false);
-      Error E = CVTD.dump(Record, TDV);
+      TypeDumpVisitor TDV(Table, &SP, false);
+
+      Error E = codeview::visitTypeRecord(Record, *B, TDV);
       if (E) {
         logAllUnhandledErrors(std::move(E), errs(), "error: ");
         llvm_unreachable("produced malformed type record");
       }
       // emitRawComment will insert its own tab and comment string before
       // the first line, so strip off our first one. It also prints its own
       // newline.
       OS.emitRawComment(
           CommentOS.str().drop_front(CommentPrefix.size() - 1).rtrim());
-    } else {
-#ifndef NDEBUG
-      // Assert that the type data is valid even if we aren't dumping
-      // comments. The MSVC linker doesn't do much type record validation,
-      // so the first link of an invalid type record can succeed while
-      // subsequent links will fail with LNK1285.
-      BinaryByteStream Stream(Record, llvm::support::little);
-      CVTypeArray Types;
-      BinaryStreamReader Reader(Stream);
-      Error E = Reader.readArray(Types, Reader.getLength());
-      if (!E) {
-        TypeVisitorCallbacks C;
-        E = codeview::visitTypeStream(Types, C);
-      }
-      if (E) {
-        logAllUnhandledErrors(std::move(E), errs(), "error: ");
-        llvm_unreachable("produced malformed type record");
-      }
-#endif
-    }
-    StringRef S(reinterpret_cast<const char *>(Record.data()), Record.size());
-    OS.EmitBinaryData(S);
-  });
+    OS.EmitBinaryData(Record.str_data());
+  } while (B = Table.getNext(*B));
 }
 
 namespace {
 
 static SourceLanguage MapDWLangToCVLang(unsigned DWLang) {
   switch (DWLang) {
   case dwarf::DW_LANG_C:
   case dwarf::DW_LANG_C89:

llvm/lib/DebugInfo/CodeView/CMakeLists.txt

 add_llvm_library(LLVMDebugInfoCodeView
   CodeViewError.cpp
   CodeViewRecordIO.cpp
   CVSymbolVisitor.cpp
-  CVTypeDumper.cpp
   CVTypeVisitor.cpp
   EnumTables.cpp
   Formatters.cpp
+  LazyRandomTypeCollection.cpp
   Line.cpp
   ModuleDebugFileChecksumFragment.cpp
   ModuleDebugFragment.cpp
   ModuleDebugFragmentRecord.cpp
   ModuleDebugFragmentVisitor.cpp
   ModuleDebugInlineeLinesFragment.cpp
   ModuleDebugLineFragment.cpp
-  RandomAccessTypeVisitor.cpp
   RecordSerialization.cpp
   StringTable.cpp
   SymbolRecordMapping.cpp
   SymbolDumper.cpp
   SymbolSerializer.cpp
   TypeDatabase.cpp
   TypeDatabaseVisitor.cpp
   TypeDumpVisitor.cpp
+  TypeIndex.cpp
   TypeRecordMapping.cpp
   TypeSerializer.cpp
   TypeStreamMerger.cpp
+  TypeTableCollection.cpp
   
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo/CodeView
   )

llvm/lib/DebugInfo/CodeView/CVTypeDumper.cpp

-//===-- CVTypeDumper.cpp - CodeView type info dumper ------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/DebugInfo/CodeView/CVTypeDumper.h"
-#include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
-#include "llvm/DebugInfo/CodeView/TypeDatabase.h"
-#include "llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h"
-#include "llvm/DebugInfo/CodeView/TypeRecord.h"
-#include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h"
-#include "llvm/Support/BinaryByteStream.h"
-
-using namespace llvm;
-using namespace llvm::codeview;
-
-Error CVTypeDumper::dump(const CVType &Record, TypeVisitorCallbacks &Dumper) {
-  TypeDatabaseVisitor DBV(TypeDB);
-  TypeVisitorCallbackPipeline Pipeline;
-  Pipeline.addCallbackToPipeline(DBV);
-  Pipeline.addCallbackToPipeline(Dumper);
-
-  CVType RecordCopy = Record;
-  return codeview::visitTypeRecord(RecordCopy, Pipeline, VDS_BytesPresent,
-                                   Handler);
-}
-
-Error CVTypeDumper::dump(const CVTypeArray &Types,
-                         TypeVisitorCallbacks &Dumper) {
-  TypeDatabaseVisitor DBV(TypeDB);
-  TypeVisitorCallbackPipeline Pipeline;
-  Pipeline.addCallbackToPipeline(DBV);
-  Pipeline.addCallbackToPipeline(Dumper);
-
-  return codeview::visitTypeStream(Types, Pipeline, Handler);
-}
-
-Error CVTypeDumper::dump(ArrayRef<uint8_t> Data, TypeVisitorCallbacks &Dumper) {
-  BinaryByteStream Stream(Data, llvm::support::little);
-  CVTypeArray Types;
-  BinaryStreamReader Reader(Stream);
-  if (auto EC = Reader.readArray(Types, Reader.getLength()))
-    return EC;
-
-  return dump(Types, Dumper);
-}
-
-void CVTypeDumper::printTypeIndex(ScopedPrinter &Printer, StringRef FieldName,
-                                  TypeIndex TI, TypeDatabase &DB) {
-  StringRef TypeName;
-  if (!TI.isNoneType())
-    TypeName = DB.getTypeName(TI);
-  if (!TypeName.empty())
-    Printer.printHex(FieldName, TypeName, TI.getIndex());
-  else
-    Printer.printHex(FieldName, TI.getIndex());
-}

llvm/lib/DebugInfo/CodeView/CVTypeVisitor.cpp

 //===- CVTypeVisitor.cpp ----------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 
+#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/DebugInfo/CodeView/CodeViewError.h"
+#include "llvm/DebugInfo/CodeView/TypeCollection.h"
 #include "llvm/DebugInfo/CodeView/TypeDatabase.h"
 #include "llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h"
 #include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeRecordMapping.h"
 #include "llvm/DebugInfo/CodeView/TypeServerHandler.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h"
 #include "llvm/Support/BinaryByteStream.h"
 #include "llvm/Support/BinaryStreamReader.h"
 
 using namespace llvm;
 using namespace llvm::codeview;
 
-CVTypeVisitor::CVTypeVisitor(TypeVisitorCallbacks &Callbacks)
-    : Callbacks(Callbacks) {}
 
 template <typename T>
 static Error visitKnownRecord(CVType &Record, TypeVisitorCallbacks &Callbacks) {
   TypeRecordKind RK = static_cast<TypeRecordKind>(Record.Type);
   T KnownRecord(RK);
   if (auto EC = Callbacks.visitKnownRecord(Record, KnownRecord))
     return EC;
   return Error::success();
static Expected<TypeServer2Record> deserializeTypeServerRecord(CVType &Record) {
   TypeServer2Record R(TypeRecordKind::TypeServer2);
   StealTypeServerVisitor Thief(R);
   if (auto EC = visitTypeRecord(Record, Thief))
     return std::move(EC);
 
   return R;
 }
 
+static Error visitMemberRecord(CVMemberRecord &Record,
+                               TypeVisitorCallbacks &Callbacks) {
+  if (auto EC = Callbacks.visitMemberBegin(Record))
+    return EC;
+
+  switch (Record.Kind) {
+  default:
+    if (auto EC = Callbacks.visitUnknownMember(Record))
+      return EC;
+    break;
+#define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
+  case EnumName: {                                                             \
+    if (auto EC = visitKnownMember<Name##Record>(Record, Callbacks))           \
+      return EC;                                                               \
+    break;                                                                     \
+  }
+#define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)                \
+  MEMBER_RECORD(EnumVal, EnumVal, AliasName)
+#define TYPE_RECORD(EnumName, EnumVal, Name)
+#define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
+#include "llvm/DebugInfo/CodeView/TypeRecords.def"
+  }
+
+  if (auto EC = Callbacks.visitMemberEnd(Record))
+    return EC;
+
+  return Error::success();
+}
+
+namespace {
+
+class CVTypeVisitor {
+public:
+  explicit CVTypeVisitor(TypeVisitorCallbacks &Callbacks);
+
+  void addTypeServerHandler(TypeServerHandler &Handler);
+
+  Error visitTypeRecord(CVType &Record, TypeIndex Index);
+  Error visitTypeRecord(CVType &Record);
+
+  /// Visits the type records in Data. Sets the error flag on parse failures.
+  Error visitTypeStream(const CVTypeArray &Types);
+  Error visitTypeStream(CVTypeRange Types);
+  Error visitTypeStream(TypeCollection &Types);
+
+  Error visitMemberRecord(CVMemberRecord Record);
+  Error visitFieldListMemberStream(BinaryStreamReader &Stream);
+
+private:
+  Expected<bool> handleTypeServer(CVType &Record);
+  Error finishVisitation(CVType &Record);
+
+  /// The interface to the class that gets notified of each visitation.
+  TypeVisitorCallbacks &Callbacks;
+
+  TinyPtrVector<TypeServerHandler *> Handlers;
+};
+
+CVTypeVisitor::CVTypeVisitor(TypeVisitorCallbacks &Callbacks)
+    : Callbacks(Callbacks) {}
+
 void CVTypeVisitor::addTypeServerHandler(TypeServerHandler &Handler) {
   Handlers.push_back(&Handler);
 }
 
 Expected<bool> CVTypeVisitor::handleTypeServer(CVType &Record) {
   if (Record.Type == TypeLeafKind::LF_TYPESERVER2 && !Handlers.empty()) {
     auto TS = deserializeTypeServerRecord(Record);
     if (!TS)
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))
-    return EC;
-
-  switch (Record.Kind) {
-  default:
-    if (auto EC = Callbacks.visitUnknownMember(Record))
-      return EC;
-    break;
-#define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
-  case EnumName: {                                                             \
-    if (auto EC = visitKnownMember<Name##Record>(Record, Callbacks))           \
-      return EC;                                                               \
-    break;                                                                     \
-  }
-#define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)                \
-  MEMBER_RECORD(EnumVal, EnumVal, AliasName)
-#define TYPE_RECORD(EnumName, EnumVal, Name)
-#define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
-#include "llvm/DebugInfo/CodeView/TypeRecords.def"
-  }
-
-  if (auto EC = Callbacks.visitMemberEnd(Record))
-    return EC;
-
-  return Error::success();
-}
-
 Error CVTypeVisitor::visitMemberRecord(CVMemberRecord Record) {
   return ::visitMemberRecord(Record, Callbacks);
 }
 
 /// Visits the type records in Data. Sets the error flag on parse failures.
 Error CVTypeVisitor::visitTypeStream(const CVTypeArray &Types) {
   for (auto I : Types) {
     if (auto EC = visitTypeRecord(I))
       return EC;
   }
   return Error::success();
 }
 
 Error CVTypeVisitor::visitTypeStream(CVTypeRange Types) {
   for (auto I : Types) {
     if (auto EC = visitTypeRecord(I))
       return EC;
   }
   return Error::success();
 }
 
-Error CVTypeVisitor::visitFieldListMemberStream(BinaryStreamReader Reader) {
-  FieldListDeserializer Deserializer(Reader);
-  TypeVisitorCallbackPipeline Pipeline;
-  Pipeline.addCallbackToPipeline(Deserializer);
-  Pipeline.addCallbackToPipeline(Callbacks);
+Error CVTypeVisitor::visitTypeStream(TypeCollection &Types) {
+  Optional<TypeIndex> I = Types.getFirst();
+  do {
+    CVType Type = Types.getType(*I);
+    if (auto EC = visitTypeRecord(Type, *I))
+      return EC;
+  } while (I = Types.getNext(*I));
+  return Error::success();
+}
 
+Error CVTypeVisitor::visitFieldListMemberStream(BinaryStreamReader &Reader) {
   TypeLeafKind Leaf;
   while (!Reader.empty()) {
     if (auto EC = Reader.readEnum(Leaf))
       return EC;
 
     CVMemberRecord Record;
     Record.Kind = Leaf;
-    if (auto EC = ::visitMemberRecord(Record, Pipeline))
+    if (auto EC = ::visitMemberRecord(Record, Callbacks))
       return EC;
   }
 
   return Error::success();
 }
 
-Error CVTypeVisitor::visitFieldListMemberStream(ArrayRef<uint8_t> Data) {
-  BinaryByteStream S(Data, llvm::support::little);
-  BinaryStreamReader SR(S);
-  return visitFieldListMemberStream(SR);
-}
-
-namespace {
 struct FieldListVisitHelper {
   FieldListVisitHelper(TypeVisitorCallbacks &Callbacks, ArrayRef<uint8_t> Data,
                        VisitorDataSource Source)
       : Stream(Data, llvm::support::little), Reader(Stream),
         Deserializer(Reader),
         Visitor((Source == VDS_BytesPresent) ? Pipeline : Callbacks) {
     if (Source == VDS_BytesPresent) {
       Pipeline.addCallbackToPipeline(Deserializer);
       Pipeline.addCallbackToPipeline(Callbacks);
     }
   }
 
   BinaryByteStream Stream;
   BinaryStreamReader Reader;
   FieldListDeserializer Deserializer;
   TypeVisitorCallbackPipeline Pipeline;
   CVTypeVisitor Visitor;
 };
 
 struct VisitHelper {
-  VisitHelper(TypeVisitorCallbacks &Callbacks, VisitorDataSource Source,
-              TypeServerHandler *TS)
+  VisitHelper(TypeVisitorCallbacks &Callbacks, VisitorDataSource Source)
       : Visitor((Source == VDS_BytesPresent) ? Pipeline : Callbacks) {
-    if (TS)
-      Visitor.addTypeServerHandler(*TS);
     if (Source == VDS_BytesPresent) {
       Pipeline.addCallbackToPipeline(Deserializer);
       Pipeline.addCallbackToPipeline(Callbacks);
     }
   }
 
   TypeDeserializer Deserializer;
   TypeVisitorCallbackPipeline Pipeline;
   CVTypeVisitor Visitor;
 };
 }
 
 Error llvm::codeview::visitTypeRecord(CVType &Record, TypeIndex Index,
                                       TypeVisitorCallbacks &Callbacks,
                                       VisitorDataSource Source,
                                       TypeServerHandler *TS) {
-  VisitHelper Helper(Callbacks, Source, TS);
-  return Helper.Visitor.visitTypeRecord(Record, Index);
+  VisitHelper V(Callbacks, Source);
+  if (TS)
+    V.Visitor.addTypeServerHandler(*TS);
+  return V.Visitor.visitTypeRecord(Record, Index);
 }
 
 Error llvm::codeview::visitTypeRecord(CVType &Record,
                                       TypeVisitorCallbacks &Callbacks,
                                       VisitorDataSource Source,
                                       TypeServerHandler *TS) {
-  VisitHelper Helper(Callbacks, Source, TS);
-  return Helper.Visitor.visitTypeRecord(Record);
+  VisitHelper V(Callbacks, Source);
+  if (TS)
+    V.Visitor.addTypeServerHandler(*TS);
+  return V.Visitor.visitTypeRecord(Record);
 }
 
-Error llvm::codeview::visitMemberRecordStream(ArrayRef<uint8_t> FieldList,
-                                              TypeVisitorCallbacks &Callbacks) {
-  CVTypeVisitor Visitor(Callbacks);
-  return Visitor.visitFieldListMemberStream(FieldList);
+Error llvm::codeview::visitTypeStream(const CVTypeArray &Types,
+                                      TypeVisitorCallbacks &Callbacks,
+                                      TypeServerHandler *TS) {
+  VisitHelper V(Callbacks, VDS_BytesPresent);
+  if (TS)
+    V.Visitor.addTypeServerHandler(*TS);
+  return V.Visitor.visitTypeStream(Types);
+}
+
+Error llvm::codeview::visitTypeStream(CVTypeRange Types,
+                                      TypeVisitorCallbacks &Callbacks,
+                                      TypeServerHandler *TS) {
+  VisitHelper V(Callbacks, VDS_BytesPresent);
+  if (TS)
+    V.Visitor.addTypeServerHandler(*TS);
+  return V.Visitor.visitTypeStream(Types);
+}
+
+Error llvm::codeview::visitTypeStream(TypeCollection &Types,
+                                      TypeVisitorCallbacks &Callbacks,
+                                      TypeServerHandler *TS) {
+  // When the internal visitor calls Types.getType(Index) the interface is
+  // required to return a CVType with the bytes filled out.  So we can assume
+  // that the bytes will be present when individual records are visited.
+  VisitHelper V(Callbacks, VDS_BytesPresent);
+  if (TS)
+    V.Visitor.addTypeServerHandler(*TS);
+  return V.Visitor.visitTypeStream(Types);
 }
 
 Error llvm::codeview::visitMemberRecord(CVMemberRecord Record,
                                         TypeVisitorCallbacks &Callbacks,
                                         VisitorDataSource Source) {
-  FieldListVisitHelper Helper(Callbacks, Record.Data, Source);
-  return Helper.Visitor.visitMemberRecord(Record);
+  FieldListVisitHelper V(Callbacks, Record.Data, Source);
+  return V.Visitor.visitMemberRecord(Record);
 }
 
 Error llvm::codeview::visitMemberRecord(TypeLeafKind Kind,
                                         ArrayRef<uint8_t> Record,
                                         TypeVisitorCallbacks &Callbacks) {
   CVMemberRecord R;
   R.Data = Record;
   R.Kind = Kind;
   return visitMemberRecord(R, Callbacks, VDS_BytesPresent);
 }
 
-Error llvm::codeview::visitTypeStream(const CVTypeArray &Types,
-                                      TypeVisitorCallbacks &Callbacks,
-                                      TypeServerHandler *TS) {
-  VisitHelper Helper(Callbacks, VDS_BytesPresent, TS);
-  return Helper.Visitor.visitTypeStream(Types);
-}
-
-Error llvm::codeview::visitTypeStream(CVTypeRange Types,
-                                      TypeVisitorCallbacks &Callbacks,
-                                      TypeServerHandler *TS) {
-  VisitHelper Helper(Callbacks, VDS_BytesPresent, TS);
-  return Helper.Visitor.visitTypeStream(Types);
+Error llvm::codeview::visitMemberRecordStream(ArrayRef<uint8_t> FieldList,
+                                              TypeVisitorCallbacks &Callbacks) {
+  FieldListVisitHelper V(Callbacks, FieldList, VDS_BytesPresent);
+  return V.Visitor.visitFieldListMemberStream(V.Reader);
 }

llvm/lib/DebugInfo/CodeView/LazyRandomTypeCollection.cpp

+//===- LazyRandomTypeCollection.cpp ---------------------------- *- C++--*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
+
+#include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
+#include "llvm/DebugInfo/CodeView/CodeViewError.h"
+#include "llvm/DebugInfo/CodeView/TypeDatabase.h"
+#include "llvm/DebugInfo/CodeView/TypeServerHandler.h"
+#include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
+
+using namespace llvm;
+using namespace llvm::codeview;
+
+static void error(Error &&EC) {
+  assert(!static_cast<bool>(EC));
+  if (EC)
+    consumeError(std::move(EC));
+}
+
+LazyRandomTypeCollection::LazyRandomTypeCollection(uint32_t RecordCountHint)
+    : LazyRandomTypeCollection(CVTypeArray(), RecordCountHint,
+                               PartialOffsetArray()) {}
+
+LazyRandomTypeCollection::LazyRandomTypeCollection(
+    const CVTypeArray &Types, uint32_t RecordCountHint,
+    PartialOffsetArray PartialOffsets)
+    : Database(RecordCountHint), Types(Types), DatabaseVisitor(Database),
+      PartialOffsets(PartialOffsets) {
+  KnownOffsets.resize(Database.capacity());
+}
+
+LazyRandomTypeCollection::LazyRandomTypeCollection(ArrayRef<uint8_t> Data,
+                                                   uint32_t RecordCountHint)
+    : LazyRandomTypeCollection(RecordCountHint) {
+  reset(Data);
+}
+
+LazyRandomTypeCollection::LazyRandomTypeCollection(StringRef Data,
+                                                   uint32_t RecordCountHint)
+    : LazyRandomTypeCollection(
+          makeArrayRef(Data.bytes_begin(), Data.bytes_end()), RecordCountHint) {
+}
+
+LazyRandomTypeCollection::LazyRandomTypeCollection(const CVTypeArray &Types,
+                                                   uint32_t NumRecords)
+    : LazyRandomTypeCollection(Types, NumRecords, PartialOffsetArray()) {}
+
+void LazyRandomTypeCollection::reset(StringRef Data) {
+  reset(makeArrayRef(Data.bytes_begin(), Data.bytes_end()));
+}
+
+void LazyRandomTypeCollection::reset(ArrayRef<uint8_t> Data) {
+  PartialOffsets = PartialOffsetArray();
+
+  BinaryStreamReader Reader(Data, support::little);
+  error(Reader.readArray(Types, Reader.getLength()));
+
+  KnownOffsets.resize(Database.capacity());
+}
+
+CVType LazyRandomTypeCollection::getType(TypeIndex Index) {
+  error(ensureTypeExists(Index));
+  return Database.getTypeRecord(Index);
+}
+
+StringRef LazyRandomTypeCollection::getTypeName(TypeIndex Index) {
+  if (!Index.isSimple()) {
+    // Try to make sure the type exists.  Even if it doesn't though, it may be
+    // because we're dumping a symbol stream with no corresponding type stream
+    // present, in which case we still want to be able to print <unknown UDT>
+    // for the type names.
+    consumeError(ensureTypeExists(Index));
+  }
+
+  return Database.getTypeName(Index);
+}
+
+bool LazyRandomTypeCollection::contains(TypeIndex Index) {
+  return Database.contains(Index);
+}
+
+uint32_t LazyRandomTypeCollection::size() { return Database.size(); }
+
+uint32_t LazyRandomTypeCollection::capacity() { return Database.capacity(); }
+
+Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
+  if (!Database.contains(TI)) {
+    if (auto EC = visitRangeForType(TI))
+      return EC;
+  }
+  return Error::success();
+}
+
+Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
+  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;
+                               });
+
+  assert(Next != PartialOffsets.begin());
+  auto Prev = std::prev(Next);
+
+  TypeIndex TIB = Prev->Type;
+  if (Database.contains(TIB)) {
+    // They've asked us to fetch a type index, but the entry we found in the
+    // partial offsets array has already been visited.  Since we visit an entire
+    // block every time, that means this record should have been previously
+    // discovered.  Ultimately, this means this is a request for a non-existant
+    // type index.
+    return make_error<CodeViewError>("Invalid type index");
+  }
+
+  TypeIndex TIE;
+  if (Next == PartialOffsets.end()) {
+    TIE = TypeIndex::fromArrayIndex(Database.capacity());
+  } else {
+    TIE = Next->Type;
+  }
+
+  if (auto EC = visitRange(TIB, Prev->Offset, TIE))
+    return EC;
+  return Error::success();
+}
+
+TypeIndex LazyRandomTypeCollection::getFirst() {
+  TypeIndex TI = TypeIndex::fromArrayIndex(0);
+  error(ensureTypeExists(TI));
+  return TI;
+}
+
+Optional<TypeIndex> LazyRandomTypeCollection::getNext(TypeIndex Prev) {
+  // We can't be sure how long this type stream is, given that the initial count
+  // given to the constructor is just a hint.  So just try to make sure the next
+  // record exists, and if anything goes wrong, we must be at the end.
+  if (auto EC = ensureTypeExists(Prev + 1)) {
+    consumeError(std::move(EC));
+    return None;
+  }
+
+  return Prev + 1;
+}
+
+Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
+  assert(PartialOffsets.empty());
+
+  TypeIndex CurrentTI = TypeIndex::fromArrayIndex(0);
+  uint32_t Offset = 0;
+  auto Begin = Types.begin();
+
+  if (!Database.empty()) {
+    // 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
+    // later additional records are added since we didn't know how many there
+    // would be until we did a full visitation, then you try to access the new
+    // type triggering another full scan.  To avoid this, we assume that if the
+    // database has some records, this must be what's going on.  So we ask the
+    // database for the largest type index less than the one we're searching for
+    // and only do the forward scan from there.
+    auto Prev = Database.largestTypeIndexLessThan(TI);
+    assert(Prev.hasValue() && "Empty database with valid types?");
+    Offset = KnownOffsets[Prev->toArrayIndex()];
+    CurrentTI = *Prev;
+    ++CurrentTI;
+    Begin = Types.at(Offset);
+    ++Begin;
+    Offset = Begin.offset();
+  }
+
+  auto End = Types.end();
+  while (Begin != End) {
+    if (auto EC = visitOneRecord(CurrentTI, Offset, *Begin))
+      return EC;
+
+    Offset += Begin.getRecordLength();
+    ++Begin;
+    ++CurrentTI;
+  }
+  if (CurrentTI <= TI) {
+    return make_error<CodeViewError>("Type Index does not exist!");
+  }
+  return Error::success();
+}
+
+Error LazyRandomTypeCollection::visitRange(TypeIndex Begin,
+                                           uint32_t BeginOffset,
+                                           TypeIndex End) {
+
+  auto RI = Types.at(BeginOffset);
+  assert(RI != Types.end());
+
+  while (Begin != End) {
+    if (auto EC = visitOneRecord(Begin, BeginOffset, *RI))
+      return EC;
+
+    BeginOffset += RI.getRecordLength();
+    ++Begin;
+    ++RI;
+  }
+
+  return Error::success();
+}
+
+Error LazyRandomTypeCollection::visitOneRecord(TypeIndex TI, uint32_t Offset,
+                                               CVType &Record) {
+  assert(!Database.contains(TI));
+  if (auto EC = codeview::visitTypeRecord(Record, TI, DatabaseVisitor))
+    return EC;
+  // Keep the KnownOffsets array the same size as the Database's capacity. Since
+  // we don't always know how many records are in the type stream, we need to be
+  // prepared for the database growing and receicing a type index that can't fit
+  // in our current buffer.
+  if (KnownOffsets.size() < Database.capacity())
+    KnownOffsets.resize(Database.capacity());
+  KnownOffsets[TI.toArrayIndex()] = Offset;
+  return Error::success();
+}

llvm/lib/DebugInfo/CodeView/RandomAccessTypeVisitor.cpp

-//===- RandomAccessTypeVisitor.cpp ---------------------------- *- C++ --*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/DebugInfo/CodeView/RandomAccessTypeVisitor.h"
-
-#include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
-#include "llvm/DebugInfo/CodeView/TypeDatabase.h"
-#include "llvm/DebugInfo/CodeView/TypeServerHandler.h"
-#include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
-
-using namespace llvm;
-using namespace llvm::codeview;
-
-RandomAccessTypeVisitor::RandomAccessTypeVisitor(
-    const CVTypeArray &Types, uint32_t NumRecords,
-    PartialOffsetArray PartialOffsets)
-    : Database(NumRecords), Types(Types), DatabaseVisitor(Database),
-      PartialOffsets(PartialOffsets) {
-
-  KnownOffsets.resize(Database.capacity());
-}
-
-Error RandomAccessTypeVisitor::visitTypeIndex(TypeIndex TI,
-                                              TypeVisitorCallbacks &Callbacks) {
-  assert(TI.toArrayIndex() < Database.capacity());
-
-  if (!Database.contains(TI)) {
-    if (auto EC = visitRangeForType(TI))
-      return EC;
-  }
-
-  assert(Database.contains(TI));
-  auto &Record = Database.getTypeRecord(TI);
-  return codeview::visitTypeRecord(Record, TI, Callbacks);
-}
-
-Error RandomAccessTypeVisitor::visitRangeForType(TypeIndex TI) {
-  if (PartialOffsets.empty()) {
-    TypeIndex TIB(TypeIndex::FirstNonSimpleIndex);
-    TypeIndex TIE = TIB + Database.capacity();
-    return visitRange(TIB, 0, TIE);
-  }
-
-  auto Next = std::upper_bound(PartialOffsets.begin(), PartialOffsets.end(), TI,
-                               [](TypeIndex Value, const TypeIndexOffset &IO) {
-                                 return Value < IO.Type;
-                               });
-
-  assert(Next != PartialOffsets.begin());
-  auto Prev = std::prev(Next);
-
-  TypeIndex TIB = Prev->Type;
-  TypeIndex TIE;
-  if (Next == PartialOffsets.end()) {
-    TIE = TypeIndex::fromArrayIndex(Database.capacity());
-  } else {
-    TIE = Next->Type;
-  }
-
-  if (auto EC = visitRange(TIB, Prev->Offset, TIE))
-    return EC;
-  return Error::success();
-}
-
-Error RandomAccessTypeVisitor::visitRange(TypeIndex Begin, uint32_t BeginOffset,
-                                          TypeIndex End) {
-
-  auto RI = Types.at(BeginOffset);
-  assert(RI != Types.end());
-
-  while (Begin != End) {
-    assert(!Database.contains(Begin));
-    if (auto EC = codeview::visitTypeRecord(*RI, Begin, DatabaseVisitor))
-      return EC;
-    KnownOffsets[Begin.toArrayIndex()] = BeginOffset;
-
-    BeginOffset += RI.getRecordLength();
-    ++Begin;
-    ++RI;
-  }
-
-  return Error::success();
-}

llvm/lib/DebugInfo/CodeView/SymbolDumper.cpp

 //===-- SymbolDumper.cpp - CodeView symbol info dumper ----------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/CodeView/SymbolDumper.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/DebugInfo/CodeView/CVSymbolVisitor.h"
-#include "llvm/DebugInfo/CodeView/CVTypeDumper.h"
 #include "llvm/DebugInfo/CodeView/EnumTables.h"
 #include "llvm/DebugInfo/CodeView/StringTable.h"
 #include "llvm/DebugInfo/CodeView/SymbolDeserializer.h"
 #include "llvm/DebugInfo/CodeView/SymbolDumpDelegate.h"
 #include "llvm/DebugInfo/CodeView/SymbolRecord.h"
 #include "llvm/DebugInfo/CodeView/SymbolVisitorCallbackPipeline.h"
 #include "llvm/DebugInfo/CodeView/SymbolVisitorCallbacks.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ScopedPrinter.h"
 
 #include <system_error>
 
 using namespace llvm;
 using namespace llvm::codeview;
 
 namespace {
 /// Use this private dumper implementation to keep implementation details about
 /// the visitor out of SymbolDumper.h.
 class CVSymbolDumperImpl : public SymbolVisitorCallbacks {
 public:
-  CVSymbolDumperImpl(TypeDatabase &TypeDB, SymbolDumpDelegate *ObjDelegate,
+  CVSymbolDumperImpl(TypeCollection &Types, SymbolDumpDelegate *ObjDelegate,
                      ScopedPrinter &W, bool PrintRecordBytes)
-      : TypeDB(TypeDB), ObjDelegate(ObjDelegate), W(W),
+      : Types(Types), ObjDelegate(ObjDelegate), W(W),
         PrintRecordBytes(PrintRecordBytes), InFunctionScope(false) {}
 
 /// CVSymbolVisitor overrides.
 #define SYMBOL_RECORD(EnumName, EnumVal, Name)                                 \
   Error visitKnownRecord(CVSymbol &CVR, Name &Record) override;
 #define SYMBOL_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
 #include "llvm/DebugInfo/CodeView/CVSymbolTypes.def"
 
   Error visitSymbolBegin(CVSymbol &Record) override;
   Error visitSymbolEnd(CVSymbol &Record) override;
   Error visitUnknownSymbol(CVSymbol &Record) override;
 
 private:
   void printLocalVariableAddrRange(const LocalVariableAddrRange &Range,
                                    uint32_t RelocationOffset);
   void printLocalVariableAddrGap(ArrayRef<LocalVariableAddrGap> Gaps);
   void printTypeIndex(StringRef FieldName, TypeIndex TI);
 
-  TypeDatabase &TypeDB;
+  TypeCollection &Types;
   SymbolDumpDelegate *ObjDelegate;
   ScopedPrinter &W;
 
   bool PrintRecordBytes;
   bool InFunctionScope;
 };
 }
 
void CVSymbolDumperImpl::printLocalVariableAddrGap(
   for (auto &Gap : Gaps) {
     ListScope S(W, "LocalVariableAddrGap");
     W.printHex("GapStartOffset", Gap.GapStartOffset);
     W.printHex("Range", Gap.Range);
   }
 }
 
 void CVSymbolDumperImpl::printTypeIndex(StringRef FieldName, TypeIndex TI) {
-  CVTypeDumper::printTypeIndex(W, FieldName, TI, TypeDB);
+  codeview::printTypeIndex(W, FieldName, TI, Types);
 }
 
 Error CVSymbolDumperImpl::visitSymbolBegin(CVSymbol &CVR) {
   return Error::success();
 }
 
 Error CVSymbolDumperImpl::visitSymbolEnd(CVSymbol &CVR) {
   if (PrintRecordBytes && ObjDelegate)
Error CVSymbolDumperImpl::visitUnknownSymbol(CVSymbol &CVR) {
   W.printEnum("Kind", uint16_t(CVR.kind()), getSymbolTypeNames());
   W.printNumber("Length", CVR.length());
   return Error::success();
 }
 
 Error CVSymbolDumper::dump(CVRecord<SymbolKind> &Record) {
   SymbolVisitorCallbackPipeline Pipeline;
   SymbolDeserializer Deserializer(ObjDelegate.get());
-  CVSymbolDumperImpl Dumper(TypeDB, ObjDelegate.get(), W, PrintRecordBytes);
+  CVSymbolDumperImpl Dumper(Types, ObjDelegate.get(), W, PrintRecordBytes);
 
   Pipeline.addCallbackToPipeline(Deserializer);
   Pipeline.addCallbackToPipeline(Dumper);
   CVSymbolVisitor Visitor(Pipeline);
   return Visitor.visitSymbolRecord(Record);
 }
 
 Error CVSymbolDumper::dump(const CVSymbolArray &Symbols) {
   SymbolVisitorCallbackPipeline Pipeline;
   SymbolDeserializer Deserializer(ObjDelegate.get());
-  CVSymbolDumperImpl Dumper(TypeDB, ObjDelegate.get(), W, PrintRecordBytes);
+  CVSymbolDumperImpl Dumper(Types, ObjDelegate.get(), W, PrintRecordBytes);
 
   Pipeline.addCallbackToPipeline(Deserializer);
   Pipeline.addCallbackToPipeline(Dumper);
   CVSymbolVisitor Visitor(Pipeline);
   return Visitor.visitSymbolStream(Symbols);
 }

llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp

 
 TypeDatabase::TypeDatabase(uint32_t Capacity) : TypeNameStorage(Allocator) {
   CVUDTNames.resize(Capacity);
   TypeRecords.resize(Capacity);
   ValidRecords.resize(Capacity);
 }
 
 TypeIndex TypeDatabase::appendType(StringRef Name, const CVType &Data) {
-  TypeIndex TI;
-  TI = getAppendIndex();
-  if (TI.toArrayIndex() >= capacity())
+  LargestTypeIndex = getAppendIndex();
+  if (LargestTypeIndex.toArrayIndex() >= capacity())
     grow();
-  recordType(Name, TI, Data);
-  return TI;
+  recordType(Name, LargestTypeIndex, Data);
+  return LargestTypeIndex;
 }
 
 void TypeDatabase::recordType(StringRef Name, TypeIndex Index,
                               const CVType &Data) {
+  LargestTypeIndex = empty() ? Index : std::max(Index, LargestTypeIndex);
+
+  if (LargestTypeIndex.toArrayIndex() >= capacity())
+    grow(Index);
+
   uint32_t AI = Index.toArrayIndex();
 
   assert(!contains(Index));
   assert(AI < capacity());
 
   CVUDTNames[AI] = Name;
   TypeRecords[AI] = Data;
   ValidRecords.set(AI);
bool TypeDatabase::contains(TypeIndex Index) const {
 
   return ValidRecords.test(AI);
 }
 
 uint32_t TypeDatabase::size() const { return Count; }
 
 uint32_t TypeDatabase::capacity() const { return TypeRecords.size(); }
 
-void TypeDatabase::grow() {
-  TypeRecords.emplace_back();
-  CVUDTNames.emplace_back();
-  ValidRecords.resize(ValidRecords.size() + 1);
+CVType TypeDatabase::getType(TypeIndex Index) { return getTypeRecord(Index); }
+
+StringRef TypeDatabase::getTypeName(TypeIndex Index) {
+  return static_cast<const TypeDatabase *>(this)->getTypeName(Index);
+}
+
+bool TypeDatabase::contains(TypeIndex Index) {
+  return static_cast<const TypeDatabase *>(this)->contains(Index);
+}
+
+uint32_t TypeDatabase::size() {
+  return static_cast<const TypeDatabase *>(this)->size();
+}
+
+uint32_t TypeDatabase::capacity() {
+  return static_cast<const TypeDatabase *>(this)->capacity();
+}
+
+void TypeDatabase::grow() { grow(LargestTypeIndex + 1); }
+
+void TypeDatabase::grow(TypeIndex NewIndex) {
+  uint32_t NewSize = NewIndex.toArrayIndex() + 1;
+
+  if (NewSize <= capacity())
+    return;
+
+  uint32_t NewCapacity = NewSize * 3 / 2;
+
+  TypeRecords.resize(NewCapacity);
+  CVUDTNames.resize(NewCapacity);
+  ValidRecords.resize(NewCapacity);
 }
 
 bool TypeDatabase::empty() const { return size() == 0; }
 
+Optional<TypeIndex> TypeDatabase::largestTypeIndexLessThan(TypeIndex TI) const {
+  uint32_t AI = TI.toArrayIndex();
+  int N = ValidRecords.find_prev(AI);
+  if (N == -1)
+    return None;
+  return TypeIndex::fromArrayIndex(N);
+}
+
 TypeIndex TypeDatabase::getAppendIndex() const {
   if (empty())
     return TypeIndex::fromArrayIndex(0);
 
-  int Index = ValidRecords.find_last();
-  assert(Index != -1);
-  return TypeIndex::fromArrayIndex(Index) + 1;
+  return LargestTypeIndex + 1;
+}
+
+TypeIndex TypeDatabase::getFirst() {
+  int N = ValidRecords.find_first();
+  assert(N != -1);
+  return TypeIndex::fromArrayIndex(N);
+}
+
+Optional<TypeIndex> TypeDatabase::getNext(TypeIndex Prev) {
+  int N = ValidRecords.find_next(Prev.toArrayIndex());
+  if (N == -1)
+    return None;
+  return TypeIndex::fromArrayIndex(N);
 }

llvm/lib/DebugInfo/CodeView/TypeDumpVisitor.cpp

 //===-- TypeDumpVisitor.cpp - CodeView type info dumper ----------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/CodeView/TypeDumpVisitor.h"
 
 #include "llvm/ADT/SmallString.h"
-#include "llvm/DebugInfo/CodeView/CVTypeDumper.h"
 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 #include "llvm/DebugInfo/CodeView/Formatters.h"
+#include "llvm/DebugInfo/CodeView/TypeCollection.h"
 #include "llvm/DebugInfo/CodeView/TypeDatabase.h"
 #include "llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h"
-#include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
-#include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h"
 #include "llvm/Support/BinaryByteStream.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/ScopedPrinter.h"
 
 using namespace llvm;
 using namespace llvm::codeview;
 
 static const EnumEntry<TypeLeafKind> LeafTypeNames[] = {

 #include "llvm/DebugInfo/CodeView/TypeRecords.def"
   default:
     break;
   }
   return "UnknownLeaf";
 }
 
 void TypeDumpVisitor::printTypeIndex(StringRef FieldName, TypeIndex TI) const {
-  CVTypeDumper::printTypeIndex(*W, FieldName, TI, TypeDB);
+  codeview::printTypeIndex(*W, FieldName, TI, TpiTypes);
 }
 
 void TypeDumpVisitor::printItemIndex(StringRef FieldName, TypeIndex TI) const {
-  CVTypeDumper::printTypeIndex(*W, FieldName, TI, getSourceDB());
+  codeview::printTypeIndex(*W, FieldName, TI, getSourceTypes());
 }
 
 Error TypeDumpVisitor::visitTypeBegin(CVType &Record) {
-  TypeIndex TI = getSourceDB().getAppendIndex();
-  return visitTypeBegin(Record, TI);
+  return visitTypeBegin(Record, TypeIndex::fromArrayIndex(TpiTypes.size()));
 }
 
 Error TypeDumpVisitor::visitTypeBegin(CVType &Record, TypeIndex Index) {
   W->startLine() << getLeafTypeName(Record.Type);
   W->getOStream() << " (" << HexNumber(Index.getIndex()) << ")";
   W->getOStream() << " {\n";
   W->indent();
   W->printEnum("TypeLeafKind", unsigned(Record.Type),

llvm/lib/DebugInfo/CodeView/TypeIndex.cpp

+//===-- TypeIndex.cpp - CodeView type index ---------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/CodeView/TypeIndex.h"
+
+#include "llvm/DebugInfo/CodeView/TypeCollection.h"
+#include "llvm/Support/ScopedPrinter.h"
+
+using namespace llvm;
+using namespace llvm::codeview;
+
+void llvm::codeview::printTypeIndex(ScopedPrinter &Printer, StringRef FieldName,
+                                    TypeIndex TI, TypeCollection &Types) {
+  StringRef TypeName;
+  if (!TI.isNoneType())
+    TypeName = Types.getTypeName(TI);
+  if (!TypeName.empty())
+    Printer.printHex(FieldName, TypeName, TI.getIndex());
+  else
+    Printer.printHex(FieldName, TI.getIndex());
+}

llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

 //===-- TypeStreamMerger.cpp ------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
-#include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
-#include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ScopedPrinter.h"
 
 using namespace llvm;
 using namespace llvm::codeview;
 
 namespace {

llvm/lib/DebugInfo/CodeView/TypeTableCollection.cpp

+//===- TypeTableCollection.cpp -------------------------------- *- C++ --*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/CodeView/TypeTableCollection.h"
+
+#include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
+#include "llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h"
+#include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
+#include "llvm/Support/BinaryByteStream.h"
+#include "llvm/Support/BinaryStreamReader.h"
+
+using namespace llvm;
+using namespace llvm::codeview;
+
+static void error(Error &&EC) {
+  assert(!static_cast<bool>(EC));
+  if (EC)
+    consumeError(std::move(EC));
+}
+
+TypeTableCollection::TypeTableCollection(
+    ArrayRef<MutableArrayRef<uint8_t>> Records)
+    : Records(Records), Database(Records.size()) {}
+
+TypeIndex TypeTableCollection::getFirst() {
+  assert(!empty());
+  return TypeIndex::fromArrayIndex(0);
+}
+
+Optional<TypeIndex> TypeTableCollection::getNext(TypeIndex Prev) {
+  ++Prev;
+  assert(Prev.toArrayIndex() <= size());
+  if (Prev.toArrayIndex() == size())
+    return None;
+  return Prev;
+}
+
+void TypeTableCollection::ensureTypeExists(TypeIndex Index) {
+  assert(hasCapacityFor(Index));
+
+  if (Database.contains(Index))
+    return;
+
+  BinaryByteStream Bytes(Records[Index.toArrayIndex()], support::little);
+
+  CVType Type;
+  uint32_t Len;
+  error(VarStreamArrayExtractor<CVType>::extract(Bytes, Len, Type));
+
+  TypeDatabaseVisitor DBV(Database);
+  error(codeview::visitTypeRecord(Type, Index, DBV));
+  assert(Database.contains(Index));
+}
+
+CVType TypeTableCollection::getType(TypeIndex Index) {
+  ensureTypeExists(Index);
+  return Database.getTypeRecord(Index);
+}
+
+StringRef TypeTableCollection::getTypeName(TypeIndex Index) {
+  if (!Index.isSimple())
+    ensureTypeExists(Index);
+  return Database.getTypeName(Index);
+}
+
+bool TypeTableCollection::contains(TypeIndex Index) {
+  return Database.contains(Index);
+}
+
+uint32_t TypeTableCollection::size() { return Records.size(); }
+
+uint32_t TypeTableCollection::capacity() { return Records.size(); }
+
+bool TypeTableCollection::hasCapacityFor(TypeIndex Index) const {
+  return Index.toArrayIndex() < Records.size();
+}

llvm/lib/DebugInfo/PDB/Native/PDBTypeServerHandler.cpp

 // encounters the same TypeServer multiple times (for example reusing one
 // PDBTypeServerHandler across multiple visitations of distinct object files or
 // PDB files), PDBTypeServerHandler will optionally revisit all the records
 // again, or simply consume the record and do nothing.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/PDB/Native/PDBTypeServerHandler.h"
 
+#include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 #include "llvm/DebugInfo/CodeView/CodeViewError.h"
 #include "llvm/DebugInfo/PDB/GenericError.h"
 #include "llvm/DebugInfo/PDB/Native/InfoStream.h"
 #include "llvm/DebugInfo/PDB/Native/NativeSession.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFile.h"
 #include "llvm/DebugInfo/PDB/Native/TpiStream.h"
 #include "llvm/DebugInfo/PDB/PDB.h"
 #include "llvm/Support/FileSystem.h"

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

 //===- TpiStream.cpp - PDB Type Info (TPI) Stream 2 Access ----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/PDB/Native/TpiStream.h"
 #include "llvm/ADT/iterator_range.h"
-#include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
-#include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
-#include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h"
 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFile.h"
 #include "llvm/DebugInfo/PDB/Native/PDBTypeServerHandler.h"
 #include "llvm/DebugInfo/PDB/Native/RawConstants.h"
 #include "llvm/DebugInfo/PDB/Native/RawError.h"
 #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
 #include "llvm/DebugInfo/PDB/Native/TpiHashing.h"
 #include "llvm/Support/BinaryStreamReader.h"

llvm/tools/llvm-pdbdump/Analyze.cpp

 //===- Analyze.cpp - PDB analysis functions ---------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Analyze.h"
 
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 #include "llvm/DebugInfo/CodeView/TypeDatabase.h"
 #include "llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h"
-#include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFile.h"
 #include "llvm/DebugInfo/PDB/Native/RawError.h"
 #include "llvm/DebugInfo/PDB/Native/TpiStream.h"
 
 #include "llvm/Support/FormatVariadic.h"

llvm/tools/llvm-pdbdump/CompactTypeDumpVisitor.h

 
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
 
 namespace llvm {
 class ScopedPrinter;
 namespace codeview {
-class TypeDatabase;
+class TypeCollection;
 }
 
 namespace pdb {
 
 /// Dumper for CodeView type streams found in COFF object files and PDB files.
 /// Dumps records on a single line, and ignores member records.
 class CompactTypeDumpVisitor : public codeview::TypeVisitorCallbacks {
 public:
-  CompactTypeDumpVisitor(codeview::TypeDatabase &TypeDB, ScopedPrinter *W);
-  CompactTypeDumpVisitor(codeview::TypeDatabase &TypeDB,
+  CompactTypeDumpVisitor(codeview::TypeCollection &Types, ScopedPrinter *W);
+  CompactTypeDumpVisitor(codeview::TypeCollection &Types,
                          codeview::TypeIndex FirstTI, ScopedPrinter *W);
 
   /// Paired begin/end actions for all types. Receives all record data,
   /// including the fixed-length record prefix.
   Error visitTypeBegin(codeview::CVType &Record) override;
   Error visitTypeEnd(codeview::CVType &Record) override;
 
 private:
   ScopedPrinter *W;
 
   codeview::TypeIndex TI;
   uint32_t Offset;
-  codeview::TypeDatabase &TypeDB;
+  codeview::TypeCollection &Types;
 };
 
 } // end namespace pdb
 } // end namespace llvm
 
 #endif

llvm/tools/llvm-pdbdump/CompactTypeDumpVisitor.cpp

 static StringRef getLeafName(TypeLeafKind K) {
   for (const auto &E : LeafTypeNames) {
     if (E.Value == K)
       return E.Name;
   }
   return StringRef();
 }
 
-CompactTypeDumpVisitor::CompactTypeDumpVisitor(TypeDatabase &TypeDB,
+CompactTypeDumpVisitor::CompactTypeDumpVisitor(TypeCollection &Types,
                                                ScopedPrinter *W)
-    : CompactTypeDumpVisitor(TypeDB, TypeIndex(TypeIndex::FirstNonSimpleIndex),
+    : CompactTypeDumpVisitor(Types, TypeIndex(TypeIndex::FirstNonSimpleIndex),
                              W) {}
 
-CompactTypeDumpVisitor::CompactTypeDumpVisitor(TypeDatabase &TypeDB,
+CompactTypeDumpVisitor::CompactTypeDumpVisitor(TypeCollection &Types,
                                                TypeIndex FirstTI,
                                                ScopedPrinter *W)
-    : W(W), TI(FirstTI), Offset(0), TypeDB(TypeDB) {}
+    : W(W), TI(FirstTI), Offset(0), Types(Types) {}
 
 Error CompactTypeDumpVisitor::visitTypeBegin(CVType &Record) {
   return Error::success();
 }
 
 Error CompactTypeDumpVisitor::visitTypeEnd(CVType &Record) {
   uint32_t I = TI.getIndex();
   StringRef Leaf = getLeafName(Record.Type);
-  StringRef Name = TypeDB.getTypeName(TI);
+  StringRef Name = Types.getTypeName(TI);
   W->printString(
       llvm::formatv("Index: {0:x} ({1:N} bytes, offset {2:N}) {3} \"{4}\"", I,
                     Record.length(), Offset, Leaf, Name)
           .str());
 
   Offset += Record.length();
   TI.setIndex(TI.getIndex() + 1);
 
   return Error::success();
 }

llvm/tools/llvm-pdbdump/LLVMOutputStyle.h

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/DebugInfo/CodeView/TypeDatabase.h"
 #include "llvm/Support/ScopedPrinter.h"
 
 #include <string>
 
 namespace llvm {
 class BitVector;
+
+namespace codeview {
+class LazyRandomTypeCollection;
+}
+
 namespace pdb {
 class LLVMOutputStyle : public OutputStyle {
 public:
   LLVMOutputStyle(PDBFile &File);
 
   Error dump() override;
 
 private:
-  Error buildTypeDatabase(uint32_t SN);
+  Expected<codeview::LazyRandomTypeCollection &>
+  initializeTypeDatabase(uint32_t SN);
 
   Error dumpFileHeaders();
   Error dumpStreamSummary();
   Error dumpFreePageMap();
   Error dumpBlockRanges();
   Error dumpGlobalsStream();
   Error dumpStreamBytes();
   Error dumpStreamBlocks();
   Error dumpStringTable();
   Error dumpInfoStream();
   Error dumpTpiStream(uint32_t StreamIdx);
   Error dumpDbiStream();
   Error dumpSectionContribs();
   Error dumpSectionMap();
   Error dumpPublicsStream();
   Error dumpSectionHeaders();
   Error dumpFpoStream();
 
   void dumpBitVector(StringRef Name, const BitVector &V);
 
   void flush();
 
   PDBFile &File;
   ScopedPrinter P;
-  Optional<codeview::TypeDatabase> TypeDB;
-  Optional<codeview::TypeDatabase> ItemDB;
+  std::unique_ptr<codeview::LazyRandomTypeCollection> TpiTypes;
+  std::unique_ptr<codeview::LazyRandomTypeCollection> IpiTypes;
   SmallVector<std::string, 32> StreamPurposes;
 };
 }
 }
 
 #endif

llvm/tools/llvm-pdbdump/LLVMOutputStyle.cpp

 //===- LLVMOutputStyle.cpp ------------------------------------ *- C++ --*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "LLVMOutputStyle.h"
 
 #include "C13DebugFragmentVisitor.h"
 #include "CompactTypeDumpVisitor.h"
 #include "StreamUtil.h"
 #include "llvm-pdbdump.h"
 
-#include "llvm/DebugInfo/CodeView/CVTypeDumper.h"
 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 #include "llvm/DebugInfo/CodeView/EnumTables.h"
+#include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
 #include "llvm/DebugInfo/CodeView/Line.h"
 #include "llvm/DebugInfo/CodeView/ModuleDebugFileChecksumFragment.h"
 #include "llvm/DebugInfo/CodeView/ModuleDebugFragmentVisitor.h"
 #include "llvm/DebugInfo/CodeView/ModuleDebugInlineeLinesFragment.h"
 #include "llvm/DebugInfo/CodeView/ModuleDebugLineFragment.h"
 #include "llvm/DebugInfo/CodeView/ModuleDebugUnknownFragment.h"
 #include "llvm/DebugInfo/CodeView/SymbolDumper.h"
 #include "llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h"
-#include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeDumpVisitor.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h"
 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
 #include "llvm/DebugInfo/PDB/Native/DbiModuleDescriptor.h"
 #include "llvm/DebugInfo/PDB/Native/DbiStream.h"
 #include "llvm/DebugInfo/PDB/Native/EnumTables.h"
 #include "llvm/DebugInfo/PDB/Native/GlobalsStream.h"
 #include "llvm/DebugInfo/PDB/Native/ISectionContribVisitor.h"
struct PageStats {
   BitVector OrphanedPages;
 
   // Pages which are marked free in the FPM but are used.
   BitVector UseAfterFreePages;
 };
 
 class C13RawVisitor : public C13DebugFragmentVisitor {
 public:
-  C13RawVisitor(ScopedPrinter &P, PDBFile &F, TypeDatabase &IPI)
+  C13RawVisitor(ScopedPrinter &P, PDBFile &F, LazyRandomTypeCollection &IPI)
       : C13DebugFragmentVisitor(F), P(P), IPI(IPI) {}
 
   Error handleLines() override {
     if (Lines.empty())
       return Error::success();
 
     DictScope DD(P, "Lines");
 
Error handleInlineeLines() override {
     for (const auto &IL : InlineeLines) {
       P.printBoolean("HasExtraFiles", IL.hasExtraFiles());
       ListScope LS(P, "Lines");
       for (const auto &L : IL) {
         DictScope DDD(P, "Inlinee");
         if (auto EC = printFileName("FileName", L.Header->FileID))
           return EC;
 
-        if (auto EC = dumpTypeRecord("Function", IPI, L.Header->Inlinee))
+        if (auto EC = dumpTypeRecord("Function", L.Header->Inlinee))
           return EC;
         P.printNumber("SourceLine", L.Header->SourceLineNum);
         if (IL.hasExtraFiles()) {
           ListScope DDDD(P, "ExtraFiles");
           for (const auto &EF : L.ExtraFiles) {
             if (auto EC = printFileName("File", EF))
               return EC;
           }
         }
       }
     }
     return Error::success();
   }
 
 private:
-  Error dumpTypeRecord(StringRef Label, TypeDatabase &DB, TypeIndex Index) {
-    CompactTypeDumpVisitor CTDV(DB, Index, &P);
+  Error dumpTypeRecord(StringRef Label, TypeIndex Index) {
+    CompactTypeDumpVisitor CTDV(IPI, Index, &P);
     DictScope D(P, Label);
-    if (DB.contains(Index)) {
-      CVType &Type = DB.getTypeRecord(Index);
+    if (IPI.contains(Index)) {
+      CVType Type = IPI.getType(Index);
       if (auto EC = codeview::visitTypeRecord(Type, CTDV))
         return EC;
     } else {
       P.printString(
           llvm::formatv("Index: {0:x} (unknown function)", Index.getIndex())
               .str());
     }
     return Error::success();
   }
   Error printFileName(StringRef Label, uint32_t Offset) {
     if (auto Result = getNameFromChecksumsBuffer(Offset)) {
       P.printString(Label, *Result);
       return Error::success();
     } else
       return Result.takeError();
   }
 
   ScopedPrinter &P;
-  TypeDatabase &IPI;
+  LazyRandomTypeCollection &IPI;
 };
 }
 
 static void recordKnownUsedPage(PageStats &Stats, uint32_t UsedIndex) {
   if (Stats.Upm.test(UsedIndex)) {
     if (Stats.ActualUsedPages.test(UsedIndex))
       Stats.MultiUsePages.set(UsedIndex);
     Stats.ActualUsedPages.set(UsedIndex);
if (!File.hasPDBIpiStream()) {
       return Error::success();
     }
     DumpRecordBytes = opts::raw::DumpIpiRecordBytes;
     DumpRecords = opts::raw::DumpIpiRecords;
     Label = "Type Info Stream (IPI)";
     VerLabel = "IPI Version";
   }
 
-  if (!DumpRecordBytes && !DumpRecords && !DumpTpiHash)
-    return Error::success();
-
   auto Tpi = (StreamIdx == StreamTPI) ? File.getPDBTpiStream()
                                       : File.getPDBIpiStream();
   if (!Tpi)
     return Tpi.takeError();
 
+  auto ExpectedTypes = initializeTypeDatabase(StreamIdx);
+  if (!ExpectedTypes)
+    return ExpectedTypes.takeError();
+  auto &Types = *ExpectedTypes;
+
+  if (!DumpRecordBytes && !DumpRecords && !DumpTpiHash)
+    return Error::success();
+
   std::unique_ptr<DictScope> StreamScope;
   std::unique_ptr<ListScope> RecordScope;
 
   StreamScope = llvm::make_unique<DictScope>(P, Label);
   P.printNumber(VerLabel, Tpi->getTpiVersion());
   P.printNumber("Record count", Tpi->getNumTypeRecords());
 
-  Optional<TypeDatabase> &StreamDB = (StreamIdx == StreamTPI) ? TypeDB : ItemDB;
-
   std::vector<std::unique_ptr<TypeVisitorCallbacks>> Visitors;
 
-  if (!StreamDB.hasValue()) {
-    StreamDB.emplace(Tpi->getNumTypeRecords());
-    Visitors.push_back(make_unique<TypeDatabaseVisitor>(*StreamDB));
-  }
   // If we're in dump mode, add a dumper with the appropriate detail level.
   if (DumpRecords) {
     std::unique_ptr<TypeVisitorCallbacks> Dumper;
     if (opts::raw::CompactRecords)
-      Dumper = make_unique<CompactTypeDumpVisitor>(*StreamDB, &P);
+      Dumper = make_unique<CompactTypeDumpVisitor>(Types, &P);
     else {
-      assert(TypeDB.hasValue());
+      assert(TpiTypes);
 
-      auto X = make_unique<TypeDumpVisitor>(*TypeDB, &P, false);
+      auto X = make_unique<TypeDumpVisitor>(*TpiTypes, &P, false);
       if (StreamIdx == StreamIPI)
-        X->setItemDB(*ItemDB);
+        X->setIpiTypes(*IpiTypes);
       Dumper = std::move(X);
     }
     Visitors.push_back(std::move(Dumper));
   }
   if (DumpRecordBytes)
     Visitors.push_back(make_unique<RecordBytesVisitor>(P));
 
   // We always need to deserialize and add it to the type database.  This is
   // true if even if we're not dumping anything, because we could need the
   // type database for the purposes of dumping symbols.
   TypeVisitorCallbackPipeline Pipeline;
   for (const auto &V : Visitors)
     Pipeline.addCallbackToPipeline(*V);
 
   if (DumpRecords || DumpRecordBytes)
     RecordScope = llvm::make_unique<ListScope>(P, "Records");
 
-  bool HadError = false;
-
-  TypeIndex T(TypeIndex::FirstNonSimpleIndex);
-  for (auto Type : Tpi->types(&HadError)) {
+  Optional<TypeIndex> I = Types.getFirst();
+  do {
     std::unique_ptr<DictScope> OneRecordScope;
 
     if ((DumpRecords || DumpRecordBytes) && !opts::raw::CompactRecords)
       OneRecordScope = llvm::make_unique<DictScope>(P, "");
 
-    if (auto EC = codeview::visitTypeRecord(Type, Pipeline))
+    auto T = Types.getType(*I);
+    if (auto EC = codeview::visitTypeRecord(T, *I, Pipeline))
       return EC;
-
-    ++T;
-  }
-  if (HadError)
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "TPI stream contained corrupt record");
+  } while (I = Types.getNext(*I));
 
   if (DumpTpiHash) {
     DictScope DD(P, "Hash");
     P.printNumber("Number of Hash Buckets", Tpi->getNumHashBuckets());
     P.printNumber("Hash Key Size", Tpi->getHashKeySize());
     P.printList("Values", Tpi->getHashValues());
 
     ListScope LHA(P, "Adjusters");
P.printString(formatv("Index: {0:x}, Offset: {1:N}", IO.Type.getIndex(),
                           (uint32_t)IO.Offset)
                       .str());
   }
 
   P.flush();
   return Error::success();
 }
 
-Error LLVMOutputStyle::buildTypeDatabase(uint32_t SN) {
-  assert(SN == StreamIPI || SN == StreamTPI);
-
-  auto &DB = (SN == StreamIPI) ? ItemDB : TypeDB;
-
-  if (DB.hasValue())
-    return Error::success();
-
+Expected<codeview::LazyRandomTypeCollection &>
+LLVMOutputStyle::initializeTypeDatabase(uint32_t SN) {
+  auto &TypeCollection = (SN == StreamTPI) ? TpiTypes : IpiTypes;
   auto Tpi =
       (SN == StreamTPI) ? File.getPDBTpiStream() : File.getPDBIpiStream();
-
   if (!Tpi)
     return Tpi.takeError();
 
-  DB.emplace(Tpi->getNumTypeRecords());
-
-  TypeDatabaseVisitor DBV(*DB);
-
-  auto HashValues = Tpi->getHashValues();
-  if (HashValues.empty())
-    return codeview::visitTypeStream(Tpi->typeArray(), DBV);
-
-  TypeVisitorCallbackPipeline Pipeline;
-  Pipeline.addCallbackToPipeline(DBV);
-
-  TpiHashVerifier HashVerifier(HashValues, Tpi->getNumHashBuckets());
-  Pipeline.addCallbackToPipeline(HashVerifier);
+  if (!TypeCollection) {
+    // Initialize the type collection, even if we're not going to dump it.  This
+    // way if some other part of the dumper decides it wants to use some or all
+    // of the records for whatever purposes, it can still access them lazily.
+    auto &Types = Tpi->typeArray();
+    uint32_t Count = Tpi->getNumTypeRecords();
+    auto Offsets = Tpi->getTypeIndexOffsets();
+    TypeCollection =
+        llvm::make_unique<LazyRandomTypeCollection>(Types, Count, Offsets);
+  }
 
-  return codeview::visitTypeStream(Tpi->typeArray(), Pipeline);
+  return *TypeCollection;
 }
 
 Error LLVMOutputStyle::dumpDbiStream() {
   bool DumpModules = opts::raw::DumpModules || opts::raw::DumpModuleSyms ||
                      opts::raw::DumpModuleFiles || opts::raw::DumpLineInfo;
   if (!opts::raw::DumpHeaders && !DumpModules)
     return Error::success();
   if (!File.hasPDBDbiStream()) {
for (uint32_t I = 0; I < Modules.getModuleCount(); ++I) {
             File.getMsfLayout(), File.getMsfBuffer(),
             Modi.getModuleStreamIndex());
 
         ModuleDebugStreamRef ModS(Modi, std::move(ModStreamData));
         if (auto EC = ModS.reload())
           return EC;
 
         if (ShouldDumpSymbols) {
-          if (auto EC = buildTypeDatabase(StreamTPI))
-            return EC;
+          auto ExpectedTypes = initializeTypeDatabase(StreamTPI);
+          if (!ExpectedTypes)
+            return ExpectedTypes.takeError();
+          auto &Types = *ExpectedTypes;
 
           ListScope SS(P, "Symbols");
-          codeview::CVSymbolDumper SD(P, *TypeDB, nullptr, false);
+          codeview::CVSymbolDumper SD(P, Types, nullptr, false);
           bool HadError = false;
           for (auto S : ModS.symbols(&HadError)) {
             DictScope LL(P, "");
             if (opts::raw::DumpModuleSyms) {
               if (auto EC = SD.dump(S)) {
                 llvm::consumeError(std::move(EC));
                 HadError = true;
                 break;
               }
             }
             if (opts::raw::DumpSymRecordBytes)
               P.printBinaryBlock("Bytes", S.content());
           }
           if (HadError)
             return make_error<RawError>(
                 raw_error_code::corrupt_file,
                 "DBI stream contained corrupt symbol record");
         }
         if (opts::raw::DumpLineInfo) {
           ListScope SS(P, "LineInfo");
-          if (auto EC = buildTypeDatabase(StreamIPI))
-            return EC;
-
-          C13RawVisitor V(P, File, *ItemDB);
+          auto ExpectedTypes = initializeTypeDatabase(StreamIPI);
+          if (!ExpectedTypes)
+            return ExpectedTypes.takeError();
+          auto &IpiItems = *ExpectedTypes;
+          C13RawVisitor V(P, File, IpiItems);
           if (auto EC = codeview::visitModuleDebugFragments(
                   ModS.linesAndChecksums(), V))
             return EC;
         }
       }
     }
   }
   return Error::success();
Error LLVMOutputStyle::dumpPublicsStream() {
   P.printNumber("AddrMap", Publics->getAddrMap());
   P.printNumber("Number of buckets", Publics->getNumBuckets());
   P.printList("Hash Buckets", Publics->getHashBuckets());
   P.printList("Address Map", Publics->getAddressMap());
   P.printList("Thunk Map", Publics->getThunkMap());
   P.printList("Section Offsets", Publics->getSectionOffsets(),
               printSectionOffset);
   ListScope L(P, "Symbols");
-  if (auto EC = buildTypeDatabase(StreamTPI))
-    return EC;
+  auto ExpectedTypes = initializeTypeDatabase(StreamTPI);
+  if (!ExpectedTypes)
+    return ExpectedTypes.takeError();
+  auto &Tpi = *ExpectedTypes;
 
-  codeview::CVSymbolDumper SD(P, *TypeDB, nullptr, false);
+  codeview::CVSymbolDumper SD(P, Tpi, nullptr, false);
   bool HadError = false;
   for (auto S : Publics->getSymbols(&HadError)) {
     DictScope DD(P, "");
 
     if (auto EC = SD.dump(S)) {
       HadError = true;
       break;
     }

llvm/tools/llvm-pdbdump/PdbYaml.cpp

 #include "YamlTypeDumper.h"
 
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/DebugInfo/CodeView/CVSymbolVisitor.h"
 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 #include "llvm/DebugInfo/CodeView/SymbolDeserializer.h"
 #include "llvm/DebugInfo/CodeView/SymbolSerializer.h"
 #include "llvm/DebugInfo/CodeView/SymbolVisitorCallbackPipeline.h"
-#include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeSerializer.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFile.h"
 #include "llvm/DebugInfo/PDB/Native/TpiHashing.h"
 #include "llvm/DebugInfo/PDB/PDBExtras.h"
 #include "llvm/DebugInfo/PDB/PDBTypes.h"
 
 using namespace llvm;
void MappingContextTraits<PdbInlineeInfo, SerializationContext>::mapping(
     IO &IO, PdbInlineeInfo &Obj, SerializationContext &Context) {
   IO.mapRequired("HasExtraFiles", Obj.HasExtraFiles);
   IO.mapRequired("Sites", Obj.Sites, Context);
 }
 
 void MappingContextTraits<PdbTpiRecord, pdb::yaml::SerializationContext>::
     mapping(IO &IO, pdb::yaml::PdbTpiRecord &Obj,
             pdb::yaml::SerializationContext &Context) {
-
   if (IO.outputting()) {
     // For PDB to Yaml, deserialize into a high level record type, then dump it.
     consumeError(codeview::visitTypeRecord(Obj.Record, Context.Dumper));
   } else {
     codeview::TypeVisitorCallbackPipeline Pipeline;
     codeview::TypeSerializer Serializer(Context.Allocator);
     pdb::TpiHashUpdater Hasher;
     // For Yaml to PDB, extract from the high level record type, then write it

llvm/tools/llvm-pdbdump/YAMLOutputStyle.h

 //===- YAMLOutputStyle.h -------------------------------------- *- C++ --*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVMPDBDUMP_YAMLOUTPUTSTYLE_H
 #define LLVM_TOOLS_LLVMPDBDUMP_YAMLOUTPUTSTYLE_H
 
 #include "OutputStyle.h"
 #include "PdbYaml.h"
 
-#include "llvm/DebugInfo/CodeView/CVTypeDumper.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/YAMLTraits.h"
 
 namespace llvm {
 namespace pdb {
 class ModuleDebugStreamRef;
 
 class YAMLOutputStyle : public OutputStyle {

llvm/tools/llvm-pdbdump/YamlTypeDumper.cpp

 //===- YamlTypeDumper.cpp ------------------------------------- *- C++ --*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "YamlTypeDumper.h"
 #include "PdbYaml.h"
 #include "YamlSerializationContext.h"
 
 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 #include "llvm/DebugInfo/CodeView/EnumTables.h"
-#include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeSerializer.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h"
 #include "llvm/DebugInfo/PDB/Native/TpiHashing.h"
 
 using namespace llvm;
 using namespace llvm::codeview;
 using namespace llvm::codeview::yaml;

llvm/tools/llvm-readobj/COFFDumper.cpp

 #include "Error.h"
 #include "ObjDumper.h"
 #include "StackMapPrinter.h"
 #include "Win64EHDumper.h"
 #include "llvm-readobj.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
-#include "llvm/DebugInfo/CodeView/CVTypeDumper.h"
+#include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 #include "llvm/DebugInfo/CodeView/CodeView.h"
+#include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
 #include "llvm/DebugInfo/CodeView/Line.h"
 #include "llvm/DebugInfo/CodeView/ModuleDebugFileChecksumFragment.h"
 #include "llvm/DebugInfo/CodeView/ModuleDebugInlineeLinesFragment.h"
 #include "llvm/DebugInfo/CodeView/ModuleDebugLineFragment.h"
 #include "llvm/DebugInfo/CodeView/RecordSerialization.h"
 #include "llvm/DebugInfo/CodeView/StringTable.h"
 #include "llvm/DebugInfo/CodeView/SymbolDeserializer.h"
 #include "llvm/DebugInfo/CodeView/SymbolDumpDelegate.h"
 #include "llvm/DebugInfo/CodeView/SymbolDumper.h"
 #include "llvm/DebugInfo/CodeView/SymbolRecord.h"
+#include "llvm/DebugInfo/CodeView/TypeDatabase.h"
 #include "llvm/DebugInfo/CodeView/TypeDumpVisitor.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
 #include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
+#include "llvm/DebugInfo/CodeView/TypeTableCollection.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/COFF.h"
-#include "llvm/Support/ConvertUTF.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/Support/ConvertUTF.h"
 #include "llvm/Support/DataExtractor.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/Win64EH.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cstring>
 #include <system_error>
 #include <time.h>
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::codeview;
 using namespace llvm::support;
 using namespace llvm::Win64EH;
 
 namespace {
 
 class COFFDumper : public ObjDumper {
 public:
   friend class COFFObjectDumpDelegate;
   COFFDumper(const llvm::object::COFFObjectFile *Obj, ScopedPrinter &Writer)
-      : ObjDumper(Writer), Obj(Obj), Writer(Writer), TypeDB(100) {}
+      : ObjDumper(Writer), Obj(Obj), Writer(Writer), Types(100) {}
 
   void printFileHeaders() override;
   void printSections() override;
   void printRelocations() override;
   void printSymbols() override;
   void printDynamicSymbols() override;
   void printUnwindInfo() override;
   void printCOFFImports() override;
private:
 
   void printCodeViewSymbolSection(StringRef SectionName, const SectionRef &Section);
   void printCodeViewTypeSection(StringRef SectionName, const SectionRef &Section);
   StringRef getTypeName(TypeIndex Ty);
   StringRef getFileNameForFileOffset(uint32_t FileOffset);
   void printFileNameForOffset(StringRef Label, uint32_t FileOffset);
   void printTypeIndex(StringRef FieldName, TypeIndex TI) {
     // Forward to CVTypeDumper for simplicity.
-    CVTypeDumper::printTypeIndex(Writer, FieldName, TI, TypeDB);
+    codeview::printTypeIndex(Writer, FieldName, TI, Types);
   }
 
   void printCodeViewSymbolsSubsection(StringRef Subsection,
                                       const SectionRef &Section,
                                       StringRef SectionContents);
 
   void printCodeViewFileChecksums(StringRef Subsection);
 
private:
   bool RelocCached = false;
   RelocMapTy RelocMap;
 
   VarStreamArray<FileChecksumEntry> CVFileChecksumTable;
 
   StringTableRef CVStringTable;
 
   ScopedPrinter &Writer;
-  TypeDatabase TypeDB;
+  BinaryByteStream TypeContents;
+  LazyRandomTypeCollection Types;
 };
 
 class COFFObjectDumpDelegate : public SymbolDumpDelegate {
 public:
   COFFObjectDumpDelegate(COFFDumper &CD, const SectionRef &SR,
                          const COFFObjectFile *Obj, StringRef SectionContents)
       : CD(CD), SR(SR), SectionContents(SectionContents) {
     Sec = Obj->getCOFFSection(SR);

 
 void COFFDumper::printCodeViewSymbolsSubsection(StringRef Subsection,
                                                 const SectionRef &Section,
                                                 StringRef SectionContents) {
   ArrayRef<uint8_t> BinaryData(Subsection.bytes_begin(),
                                Subsection.bytes_end());
   auto CODD = llvm::make_unique<COFFObjectDumpDelegate>(*this, Section, Obj,
                                                         SectionContents);
-
-  CVSymbolDumper CVSD(W, TypeDB, std::move(CODD),
-                      opts::CodeViewSubsectionBytes);
+  CVSymbolDumper CVSD(W, Types, std::move(CODD), opts::CodeViewSubsectionBytes);
   CVSymbolArray Symbols;
   BinaryStreamReader Reader(BinaryData, llvm::support::little);
   if (auto EC = Reader.readArray(Symbols, Reader.getLength())) {
     consumeError(std::move(EC));
     W.flush();
     error(object_error::parse_failed);
   }
 
if (opts::CodeViewSubsectionBytes)
     W.printBinaryBlock("Data", Data);
 
   uint32_t Magic;
   error(consume(Data, Magic));
   W.printHex("Magic", Magic);
   if (Magic != COFF::DEBUG_SECTION_MAGIC)
     return error(object_error::parse_failed);
 
-  CVTypeDumper CVTD(TypeDB);
-  TypeDumpVisitor TDV(TypeDB, &W, opts::CodeViewSubsectionBytes);
-  if (auto EC = CVTD.dump({Data.bytes_begin(), Data.bytes_end()}, TDV)) {
-    W.flush();
-    error(llvm::errorToErrorCode(std::move(EC)));
-  }
+  Types.reset(Data);
+
+  TypeDumpVisitor TDV(Types, &W, opts::CodeViewSubsectionBytes);
+  error(codeview::visitTypeStream(Types, TDV));
 }
 
 void COFFDumper::printSections() {
   ListScope SectionsD(W, "Sections");
   int SectionNumber = 0;
   for (const SectionRef &Sec : Obj->sections()) {
     ++SectionNumber;
     const coff_section *Section = Obj->getCOFFSection(Sec);
void llvm::dumpCodeViewMergedTypes(ScopedPrinter &Writer,
                                    llvm::codeview::TypeTableBuilder &IDTable,
                                    llvm::codeview::TypeTableBuilder &CVTypes) {
   // Flatten it first, then run our dumper on it.
   SmallString<0> TypeBuf;
   CVTypes.ForEachRecord([&](TypeIndex TI, ArrayRef<uint8_t> Record) {
     TypeBuf.append(Record.begin(), Record.end());
   });
 
-  TypeDatabase TypeDB(CVTypes.records().size());
+  TypeTableCollection TpiTypes(CVTypes.records());
   {
     ListScope S(Writer, "MergedTypeStream");
-    CVTypeDumper CVTD(TypeDB);
-    TypeDumpVisitor TDV(TypeDB, &Writer, opts::CodeViewSubsectionBytes);
-    if (auto EC = CVTD.dump(
-            {TypeBuf.str().bytes_begin(), TypeBuf.str().bytes_end()}, TDV)) {
-      Writer.flush();
-      error(std::move(EC));
-    }
+    TypeDumpVisitor TDV(TpiTypes, &Writer, opts::CodeViewSubsectionBytes);
+    error(codeview::visitTypeStream(TpiTypes, TDV));
   }
 
   // Flatten the id stream and print it next. The ID stream refers to names from
   // the type stream.
-  SmallString<0> IDBuf;
-  IDTable.ForEachRecord([&](TypeIndex TI, ArrayRef<uint8_t> Record) {
-    IDBuf.append(Record.begin(), Record.end());
-  });
-
+  TypeTableCollection IpiTypes(IDTable.records());
   {
     ListScope S(Writer, "MergedIDStream");
-    TypeDatabase IDDB(IDTable.records().size());
-    CVTypeDumper CVTD(IDDB);
-    TypeDumpVisitor TDV(TypeDB, &Writer, opts::CodeViewSubsectionBytes);
-    TDV.setItemDB(IDDB);
-    if (auto EC = CVTD.dump(
-            {IDBuf.str().bytes_begin(), IDBuf.str().bytes_end()}, TDV)) {
-      Writer.flush();
-      error(std::move(EC));
-    }
+    TypeDumpVisitor TDV(TpiTypes, &Writer, opts::CodeViewSubsectionBytes);
+    TDV.setIpiTypes(IpiTypes);
+    error(codeview::visitTypeStream(IpiTypes, TDV));
   }
 }

llvm/unittests/DebugInfo/CodeView/RandomAccessVisitorTest.cpp

 //===- llvm/unittest/DebugInfo/CodeView/RandomAccessVisitorTest.cpp -------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ErrorChecking.h"
 
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
-#include "llvm/DebugInfo/CodeView/RandomAccessTypeVisitor.h"
-#include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
+#include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeRecordMapping.h"
 #include "llvm/DebugInfo/CodeView/TypeSerializer.h"
 #include "llvm/DebugInfo/CodeView/TypeServerHandler.h"
 #include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
-#include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
 #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/BinaryItemStream.h"
 #include "llvm/Support/Error.h"
 
 #include "gtest/gtest.h"
 
static void SetUpTestCase() {
     GlobalState->ItemStream.setItems(GlobalState->TypeVector);
     GlobalState->TypeArray = VarStreamArray<CVType>(GlobalState->ItemStream);
   }
 
   static void TearDownTestCase() { GlobalState.reset(); }
 
   void SetUp() override {
     TestState = llvm::make_unique<PerTestState>();
-
-    TestState->Pipeline.addCallbackToPipeline(TestState->Deserializer);
-    TestState->Pipeline.addCallbackToPipeline(TestState->Callbacks);
   }
 
   void TearDown() override { TestState.reset(); }
 
 protected:
-  bool ValidateDatabaseRecord(const RandomAccessTypeVisitor &Visitor,
-                              uint32_t Index) {
+  bool ValidateDatabaseRecord(LazyRandomTypeCollection &Types, uint32_t Index) {
     TypeIndex TI = TypeIndex::fromArrayIndex(Index);
-    if (!Visitor.database().contains(TI))
+    if (!Types.contains(TI))
       return false;
-    if (GlobalState->TypeVector[Index] != Visitor.database().getTypeRecord(TI))
+    if (GlobalState->TypeVector[Index] != Types.getType(TI))
       return false;
     return true;
   }
 
   bool ValidateVisitedRecord(uint32_t VisitationOrder,
                              uint32_t GlobalArrayIndex) {
     TypeIndex TI = TypeIndex::fromArrayIndex(GlobalArrayIndex);
     if (TI != TestState->Callbacks.Indices[VisitationOrder])
struct GlobalTestState {
     VarStreamArray<CVType> TypeArray;
 
     MutableBinaryByteStream Stream;
   };
 
   struct PerTestState {
     FixedStreamArray<TypeIndexOffset> Offsets;
 
-    TypeVisitorCallbackPipeline Pipeline;
-    TypeDeserializer Deserializer;
     MockCallbacks Callbacks;
   };
 
   FixedStreamArray<TypeIndexOffset>
   createPartialOffsets(MutableBinaryByteStream &Storage,
                        std::initializer_list<uint32_t> Indices) {
 
     uint32_t Count = Indices.size();

 };
 
 std::unique_ptr<RandomAccessVisitorTest::GlobalTestState>
     RandomAccessVisitorTest::GlobalState;
 }
 
 TEST_F(RandomAccessVisitorTest, MultipleVisits) {
   TestState->Offsets = createPartialOffsets(GlobalState->Stream, {0, 8});
-  RandomAccessTypeVisitor Visitor(GlobalState->TypeArray,
-                                  GlobalState->TypeVector.size(),
-                                  TestState->Offsets);
+  LazyRandomTypeCollection Types(GlobalState->TypeArray,
 
   std::vector<uint32_t> IndicesToVisit = {5, 5, 5};
 
   for (uint32_t I : IndicesToVisit) {
     TypeIndex TI = TypeIndex::fromArrayIndex(I);
-    EXPECT_NO_ERROR(Visitor.visitTypeIndex(TI, TestState->Pipeline));
+    CVType T = Types.getType(TI);
+    EXPECT_NO_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks));
   }
 
   // [0,8) should be present
-  EXPECT_EQ(8u, Visitor.database().size());
+  EXPECT_EQ(8u, Types.size());
   for (uint32_t I = 0; I < 8; ++I)
-    EXPECT_TRUE(ValidateDatabaseRecord(Visitor, I));
+    EXPECT_TRUE(ValidateDatabaseRecord(Types, I));
 
   // 5, 5, 5
   EXPECT_EQ(3u, TestState->Callbacks.count());
   for (auto I : enumerate(IndicesToVisit))
     EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
 }
 
 TEST_F(RandomAccessVisitorTest, DescendingWithinChunk) {
   // Visit multiple items from the same "chunk" in reverse order.  In this
   // example, it's 7 then 4 then 2.  At the end, all records from 0 to 7 should
   // be known by the database, but only 2, 4, and 7 should have been visited.
   TestState->Offsets = createPartialOffsets(GlobalState->Stream, {0, 8});
 
   std::vector<uint32_t> IndicesToVisit = {7, 4, 2};
 
-  RandomAccessTypeVisitor Visitor(GlobalState->TypeArray,
-                                  GlobalState->TypeVector.size(),
-                                  TestState->Offsets);
-
+  LazyRandomTypeCollection Types(GlobalState->TypeArray,
   for (uint32_t I : IndicesToVisit) {
     TypeIndex TI = TypeIndex::fromArrayIndex(I);
-    EXPECT_NO_ERROR(Visitor.visitTypeIndex(TI, TestState->Pipeline));
+    CVType T = Types.getType(TI);
+    EXPECT_NO_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks));
   }
 
   // [0, 7]
-  EXPECT_EQ(8u, Visitor.database().size());
+  EXPECT_EQ(8u, Types.size());
   for (uint32_t I = 0; I < 8; ++I)
-    EXPECT_TRUE(ValidateDatabaseRecord(Visitor, I));
+    EXPECT_TRUE(ValidateDatabaseRecord(Types, I));
 
   // 2, 4, 7
   EXPECT_EQ(3u, TestState->Callbacks.count());
   for (auto I : enumerate(IndicesToVisit))
     EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
 }
 
 TEST_F(RandomAccessVisitorTest, AscendingWithinChunk) {
   // * Visit multiple items from the same chunk in ascending order, ensuring
   //   that intermediate items are not visited.  In the below example, it's
   //   5 -> 6 -> 7 which come from the [4,8) chunk.
   TestState->Offsets = createPartialOffsets(GlobalState->Stream, {0, 8});
 
   std::vector<uint32_t> IndicesToVisit = {2, 4, 7};
 
-  RandomAccessTypeVisitor Visitor(GlobalState->TypeArray,
-                                  GlobalState->TypeVector.size(),
-                                  TestState->Offsets);
-
+  LazyRandomTypeCollection Types(GlobalState->TypeArray,
   for (uint32_t I : IndicesToVisit) {
     TypeIndex TI = TypeIndex::fromArrayIndex(I);
-    EXPECT_NO_ERROR(Visitor.visitTypeIndex(TI, TestState->Pipeline));
+    CVType T = Types.getType(TI);
+    EXPECT_NO_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks));
   }
 
   // [0, 7]
-  EXPECT_EQ(8u, Visitor.database().size());
+  EXPECT_EQ(8u, Types.size());
   for (uint32_t I = 0; I < 8; ++I)
-    EXPECT_TRUE(ValidateDatabaseRecord(Visitor, I));
+    EXPECT_TRUE(ValidateDatabaseRecord(Types, I));
 
   // 2, 4, 7
   EXPECT_EQ(3u, TestState->Callbacks.count());
   for (auto &I : enumerate(IndicesToVisit))
     EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
 }
 
 TEST_F(RandomAccessVisitorTest, StopPrematurelyInChunk) {
   // * Don't visit the last item in one chunk, ensuring that visitation stops
   //   at the record you specify, and the chunk is only partially visited.
   //   In the below example, this is tested by visiting 0 and 1 but not 2,
   //   all from the [0,3) chunk.
   TestState->Offsets = createPartialOffsets(GlobalState->Stream, {0, 8});
 
   std::vector<uint32_t> IndicesToVisit = {0, 1, 2};
 
-  RandomAccessTypeVisitor Visitor(GlobalState->TypeArray,
-                                  GlobalState->TypeVector.size(),
-                                  TestState->Offsets);
+  LazyRandomTypeCollection Types(GlobalState->TypeArray,
 
   for (uint32_t I : IndicesToVisit) {
     TypeIndex TI = TypeIndex::fromArrayIndex(I);
-    EXPECT_NO_ERROR(Visitor.visitTypeIndex(TI, TestState->Pipeline));
+    CVType T = Types.getType(TI);
+    EXPECT_NO_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks));
   }
 
   // [0, 8) should be visited.
-  EXPECT_EQ(8u, Visitor.database().size());
+  EXPECT_EQ(8u, Types.size());
   for (uint32_t I = 0; I < 8; ++I)
-    EXPECT_TRUE(ValidateDatabaseRecord(Visitor, I));
+    EXPECT_TRUE(ValidateDatabaseRecord(Types, I));
 
   // [0, 2]
   EXPECT_EQ(3u, TestState->Callbacks.count());
   for (auto I : enumerate(IndicesToVisit))
     EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
 }
 
 TEST_F(RandomAccessVisitorTest, InnerChunk) {
   // Test that when a request comes from a chunk in the middle of the partial
   // offsets array, that items from surrounding chunks are not visited or
   // added to the database.
   TestState->Offsets = createPartialOffsets(GlobalState->Stream, {0, 4, 9});
 
   std::vector<uint32_t> IndicesToVisit = {5, 7};
 
-  RandomAccessTypeVisitor Visitor(GlobalState->TypeArray,
-                                  GlobalState->TypeVector.size(),
-                                  TestState->Offsets);
+  LazyRandomTypeCollection Types(GlobalState->TypeArray,
 
   for (uint32_t I : IndicesToVisit) {
     TypeIndex TI = TypeIndex::fromArrayIndex(I);
-    EXPECT_NO_ERROR(Visitor.visitTypeIndex(TI, TestState->Pipeline));
+    CVType T = Types.getType(TI);
+    EXPECT_NO_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks));
   }
 
   // [4, 9)
-  EXPECT_EQ(5u, Visitor.database().size());
+  EXPECT_EQ(5u, Types.size());
   for (uint32_t I = 4; I < 9; ++I)
-    EXPECT_TRUE(ValidateDatabaseRecord(Visitor, I));
+    EXPECT_TRUE(ValidateDatabaseRecord(Types, I));
 
   // 5, 7
   EXPECT_EQ(2u, TestState->Callbacks.count());
   for (auto &I : enumerate(IndicesToVisit))
     EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
 }