[CodeView] Add an amortized O(1) random access type visitor

[zturner]

Summary

Type streams are notoriously slow to access, because records are variable length, and so given a particular TypeIndex, finding the record with the given TypeIndex is O(n). But if we know the offsets of *some* of the elements, we can do better.

The type visitor here provides lazy, random access to an arbitrary type stream, only ever doing as much work as is necessary to find the requested type, and never doing a linear scan more than once for any record, even if it is visited more than once.

To do so, it makes use of a "type index offset array", which is essentially an array of pairs, where the first item is a TypeIndex, and the second item is a byte offset into the global type stream. Such an array is present as part of the serialized format of a PDB file, but in theory we could construct these on the fly for non-serialization purposes as well.

Using this visitor, When a given TypeIndex is requested, there are three possible outcomes.

1. The TypeIndex has already been requested by the user before. In this case the absolute offset of this record will be cached. We just seek to the appropriate offset, deserialize one record, and invoke the user's callback immediately.
2. The TypeIndex has not been requested by the user before, but it *has* visited internally while doing a linear scan for a different TypeIndex that the user did request. In this case, we also know the absolute offset of the record (see #3 below for how), and we proceed as in #1
3. Neither 1 or 2 above apply. In this case we begin by finding the nearest item from the type index offset array that comes before the requested item. This is a log(M) operation where M is the number of known offsets, assuming the entries are roughly evenly spaced. There is guaranteed to be at least one, because TypeIndex 0 has an offset of 0.

Then, we also look for the nearest TypeIndex that meets the criteria in either 1 or 2 above. Whichever of these two is larger gives us the nearest known offset to the requested index. From there, we do a linear scan forward to the requested TypeIndex, caching offsets along the way as we deserialize each record. On subsequent attempts to fetch a record with a given TypeIndex, any of the records scanned during the execution of this step will have O(1) lookups.

While this process is going on, a TypeDatabase that the user supplies is being populated with the various individual records providing quick lookup to type names and data of known records without having to go through the visitor.

[zturner]

A few minor cleanups. Mostly added a doxygen blurb at the beginning of the visitor class, and also changed the TypeDatabase from being stored by reference to being stored by value inside the visitor. It doesn't really make sense to have the user be responsible for creating the database, since the two things are so tightly coupled that neither can exist without the other.

[krytarowski]

llvm/unittests/DebugInfo/CodeView/ErrorChecking.h

10 ↗

(On Diff #98499)

LLVM_UNITTESTS_DEBUGINFO_CODEVIEW_ERRORCHECKING_H ?

[krytarowski]

llvm/unittests/DebugInfo/CodeView/RandomAccessVisitorTest.cpp

1 ↗

(On Diff #98499)

llvm/unittest/DebugInfo/CodeView/RandomAccessVisitorTest.cpp ?

[zturner]

Completely deleted RandomAccessTypeDatabase. It made it really awkward not having the random and sequential databases being able to interoperate with each other. For example, you might run llvm-pdbdump with the option to dump everything, and include another option which will trigger a type lookup. But since they used different databases, the two operations couldn't be made to work together. The only real difference between the two was that one used a BitVector and the other didn't, so it wasn't too much work to combine them into a single TypeDatabase that supports both appending and random access.

[rnk]

I think you probably want to go to the simpler strategy we described at lunch, which looks more like:

• Maintain the KnownOffsets map from TypeIndex to offset, where all offsets start off unknown. You could use a sentinel value (~0U) or a separate BitVector to track if the offset is known.
• If an offset is unknown, binary search the IndexToOffset array to find the start and end offsets of that range of records.
• Scan that range of records and update KnownOffsets for all records in that range.

This avoids bad worst case behavior that might come up if the user scans forwards or backwards through type indices. The difference between this algorithm and what you have is that you're trying to avoid scanning the complete range, but that means you have to do scans through the BitVector to try to resume scanning where you left off. That isn't strictly necessary to get the fast random access that we're looking for.

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

71 ↗

(On Diff #98541)

You should try to use the Doxygen /// comments when it makes sense here and below. I don't consume the Doxygen, but there are people who do.

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

27 ↗

(On Diff #98541)

No caller uses IL_FirstAvailable. What's the use case? Do we need this overload at all, or can we standardize on calling recordType with TypeIndex?

llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp

156 ↗

(On Diff #98541)

This will most likely be O(n^2) because it bypasses the growth multiplier in vector push_back.

165 ↗

(On Diff #98541)

This is linear, it might scan to the beginning of the BitVector without stopping at the beginning of the range.

[zturner]

In D33009#751659, @rnk wrote:

I think you probably want to go to the simpler strategy we described at lunch, which looks more like:

• Maintain the KnownOffsets map from TypeIndex to offset, where all offsets start off unknown. You could use a sentinel value (~0U) or a separate BitVector to track if the offset is known.
• If an offset is unknown, binary search the IndexToOffset array to find the start and end offsets of that range of records.
• Scan that range of records and update KnownOffsets for all records in that range.

This avoids bad worst case behavior that might come up if the user scans forwards or backwards through type indices. The difference between this algorithm and what you have is that you're trying to avoid scanning the complete range, but that means you have to do scans through the BitVector to try to resume scanning where you left off. That isn't strictly necessary to get the fast random access that we're looking for.

I'm still not entirely convinced. At lunch we discussed doing this as a way to avoid having a BitVector at all. But it turns out we need the BitVector regardless, because the TypeDatabase needs to know what records are valid, and it is decoupled from the visitor. So that aspect doesn't really buy us anything.

I think it comes down to access patterns. 90% or more of the types in a PDB are never going to be accessed. You're looking for a symbol, it says the type of the symbol is 329082, what are the odds you're going to later access symbol 329075? Pretty low by my estimation. Type accesses will be sparse, and so while it will increase our cache hit ratio to scan the whole block up front, it doesn't necessarily seem like a win to me. Most type accesses are going to come from un-examined chunks.

[zturner]

llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp

165 ↗

(On Diff #98541)

I could update BitVector to have an overload that stops at a certain point?

[zturner]

Fix the linear scan to the beginning of the BitVector as well as the poorly performing resize operation.

[rnk]

In D33009#751668, @zturner wrote:

I'm still not entirely convinced. At lunch we discussed doing this as a way to avoid having a BitVector at all. But it turns out we need the BitVector regardless, because the TypeDatabase needs to know what records are valid, and it is decoupled from the visitor. So that aspect doesn't really buy us anything.

I think it comes down to access patterns. 90% or more of the types in a PDB are never going to be accessed. You're looking for a symbol, it says the type of the symbol is 329082, what are the odds you're going to later access symbol 329075? Pretty low by my estimation. Type accesses will be sparse, and so while it will increase our cache hit ratio to scan the whole block up front, it doesn't necessarily seem like a win to me. Most type accesses are going to come from un-examined chunks.

I think it avoids extra complexity that isn't necessary to get the same algorithmic guarantees. It lets us reduce the API surface area of TypeDatabase to avoid findPrevoius / find_last_in. I feel like data-structurey code needs to be as simple as humanly possible to make it easy to reason about the algorithmic properties. If we can get by with less ifs, the better.

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

27 ↗

(On Diff #98541)

What's the plan for IL_FirstAvailable?

[zturner]

Updated with fixes.

[rnk]

Thanks, one more round of comments and I think we're done. I'm just staring at data structure code trying to make it simple.

llvm/lib/DebugInfo/CodeView/RandomAccessTypeVisitor.cpp

34 ↗

(On Diff #98674)

I think extracting this if block into a private method would improve readability. Using upper_bound is always tricky.

35 ↗

(On Diff #98674)

Shouldn't this be .begin() not .end()? If it's empty, they'll be equivalent anyway.

48 ↗

(On Diff #98674)

I think you can simplify this to three cases:

1. PartialOffsets.empty(): Scan all type indices. You can probably handle this step first and return early, so that Begin is always valid.
2. std::next(Begin) == PartialOffsets.end(): In this case, TIE is based on capacity like you have it.
3. Otherwise, TIE is std::next(Begin)->Type

50 ↗

(On Diff #98674)

Maybe std::next?

llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp

159 ↗

(On Diff #98674)

Isn't this a linear scan from the end of the bitvector? Does Count work instead?

[zturner]

llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp

159 ↗

(On Diff #98674)

This is something I've been kinda struggling with. Count works as long as you assume the user is *only* append or *only* inserting randomly. The API doesn't enforce that, and there's no good way to make it enforce that. In practice that's how it's used though.

[rnk]

lgtm

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

71 ↗

(On Diff #98541)

Thoughts?

llvm/trunk/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/CVTypeVisitor.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/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;
+
+  /// The deserializer which deserializes new records.
+  TypeDeserializer Deserializer;
+
+  /// The visitation callback pipeline to use.  By default this contains a
+  /// deserializer and a type database visitor.  But the callback specified
+  /// in the constructor is also added.
+  TypeVisitorCallbackPipeline Pipeline;
+
+  /// The visitor used to visit the internal pipeline for deserialization and
+  /// database maintenance.
+  CVTypeVisitor InternalVisitor;
+
+  /// 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/trunk/include/llvm/DebugInfo/CodeView/TypeDatabase.h

 #include "llvm/Support/StringSaver.h"
 
 namespace llvm {
 namespace codeview {
 class TypeDatabase {
   friend class RandomAccessTypeVisitor;
 
 public:
-  explicit TypeDatabase(uint32_t ExpectedSize);
+  explicit TypeDatabase(uint32_t Capacity);
 
-  /// Gets the type index for the next type record.
-  TypeIndex getNextTypeIndex() const;
+  /// 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, const CVType &Data);
+  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 containsTypeIndex(TypeIndex Index) const;
+  bool contains(TypeIndex Index) const;
 
   uint32_t size() const;
+  uint32_t capacity() const;
+  bool empty() const;
+
+  TypeIndex getAppendIndex() const;
 
-protected:
-  uint32_t toArrayIndex(TypeIndex Index) const;
+private:
+  void grow();
 
   BumpPtrAllocator Allocator;
 
+  uint32_t Count = 0;
+
   /// 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;
-};
-
-class RandomAccessTypeDatabase : private TypeDatabase {
-public:
-  explicit RandomAccessTypeDatabase(uint32_t ExpectedSize);
-
-  /// Records the name of a type, and reserves its type index.
-  void recordType(StringRef Name, TypeIndex Index, const CVType &Data);
 
-  using TypeDatabase::saveTypeName;
-
-  StringRef getTypeName(TypeIndex Index) const;
-
-  const CVType &getTypeRecord(TypeIndex Index) const;
-  CVType &getTypeRecord(TypeIndex Index);
-
-  bool containsTypeIndex(TypeIndex Index) const;
-
-  uint32_t size() const;
-
-private:
   BitVector ValidRecords;
 };
 }
 }
 
 #endif
 No newline at end of file

llvm/trunk/include/llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h

 
 namespace llvm {
 namespace codeview {
 
 /// Dumper for CodeView type streams found in COFF object files and PDB files.
 class TypeDatabaseVisitor : public TypeVisitorCallbacks {
 public:
   explicit TypeDatabaseVisitor(TypeDatabase &TypeDB) : TypeDB(&TypeDB) {}
-  explicit TypeDatabaseVisitor(RandomAccessTypeDatabase &TypeDB)
-      : TypeDB(&TypeDB) {}
 
   /// Paired begin/end actions for all types. Receives all record data,
   /// including the fixed-length record prefix.
   Error visitTypeBegin(CVType &Record) override;
   Error visitTypeBegin(CVType &Record, TypeIndex Index) override;
   Error visitTypeEnd(CVType &Record) override;
   Error visitMemberBegin(CVMemberRecord &Record) override;
   Error visitMemberEnd(CVMemberRecord &Record) override;
private:
   StringRef saveTypeName(StringRef Name);
 
   bool IsInFieldList = false;
 
   /// Name of the current type. Only valid before visitTypeEnd.
   StringRef Name;
   /// Current type index.  Only valid before visitTypeEnd, and if we are
   /// visiting a random access type database.
-  TypeIndex CurrentTypeIndex;
+  Optional<TypeIndex> CurrentTypeIndex;
 
-  PointerUnion<TypeDatabase *, RandomAccessTypeDatabase *> TypeDB;
+  TypeDatabase *TypeDB;
 };
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_TYPEDUMPER_H

llvm/trunk/include/llvm/DebugInfo/CodeView/TypeDeserializer.h

public:
   TypeDeserializer() = default;
 
   Error visitTypeBegin(CVType &Record) override {
     assert(!Mapping && "Already in a type mapping!");
     Mapping = llvm::make_unique<MappingInfo>(Record.content());
     return Mapping->Mapping.visitTypeBegin(Record);
   }
 
+  Error visitTypeBegin(CVType &Record, TypeIndex Index) override {
+    return visitTypeBegin(Record);
+  }
+
   Error visitTypeEnd(CVType &Record) override {
     assert(Mapping && "Not in a type mapping!");
     auto EC = Mapping->Mapping.visitTypeEnd(Record);
     Mapping.reset();
     return EC;
   }
 
 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \

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

public:
 
   /// Action to take on unknown types. By default, they are ignored.
   Error visitUnknownType(CVType &Record) override;
   Error visitUnknownMember(CVMemberRecord &Record) override;
 
   /// Paired begin/end actions for all types. Receives all record data,
   /// including the fixed-length record prefix.
   Error visitTypeBegin(CVType &Record) override;
+  Error visitTypeBegin(CVType &Record, TypeIndex Index) override;
   Error visitTypeEnd(CVType &Record) override;
   Error visitMemberBegin(CVMemberRecord &Record) override;
   Error visitMemberEnd(CVMemberRecord &Record) override;
 
 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
   Error visitKnownRecord(CVType &CVR, Name##Record &Record) override;
 #define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
   Error visitKnownMember(CVMemberRecord &CVR, Name##Record &Record) override;

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

friend inline TypeIndex operator-(const TypeIndex &A, uint32_t N) {
     Result -= N;
     return Result;
   }
 
 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;
+};
 }
 }
 
 #endif

llvm/trunk/include/llvm/DebugInfo/PDB/Native/RawTypes.h

support::ulittle16_t ClassName;     // Byte index of the class name in the
                                       // sstSegName table, or 0xFFFF.
   support::ulittle32_t Offset;        // Byte offset of the logical segment
                                       // within the specified physical segment.
                                       // If group is set in flags, offset is the
                                       // offset of the group.
   support::ulittle32_t SecByteLength; // Byte count of the segment or group.
 };
 
-// Used for serialized hash table in TPI stream.
-// In the reference, it is an array of TI and cbOff pair.
-struct TypeIndexOffset {
-  codeview::TypeIndex Type;
-  support::ulittle32_t Offset;
-};
-
 /// Some of the values are stored in bitfields.  Since this needs to be portable
 /// across compilers and architectures (big / little endian in particular) we
 /// can't use the actual structures below, but must instead do the shifting
 /// and masking ourselves.  The struct definitions are provided for reference.
 struct DbiFlags {
   ///  uint16_t IncrementalLinking : 1; // True if linked incrementally
   ///  uint16_t IsStripped : 1;         // True if private symbols were
   ///  stripped.

llvm/trunk/include/llvm/DebugInfo/PDB/Native/TpiStream.h

public:
   uint32_t TypeIndexEnd() const;
   uint32_t getNumTypeRecords() const;
   uint16_t getTypeHashStreamIndex() const;
   uint16_t getTypeHashStreamAuxIndex() const;
 
   uint32_t getHashKeySize() const;
   uint32_t getNumHashBuckets() const;
   FixedStreamArray<support::ulittle32_t> getHashValues() const;
-  FixedStreamArray<TypeIndexOffset> getTypeIndexOffsets() const;
+  FixedStreamArray<codeview::TypeIndexOffset> getTypeIndexOffsets() const;
   HashTable &getHashAdjusters();
 
   codeview::CVTypeRange types(bool *HadError) const;
 
   Error commit();
 
 private:
   const PDBFile &Pdb;
   std::unique_ptr<msf::MappedBlockStream> Stream;
 
   codeview::CVTypeArray TypeRecords;
 
   std::unique_ptr<BinaryStream> HashStream;
   FixedStreamArray<support::ulittle32_t> HashValues;
-  FixedStreamArray<TypeIndexOffset> TypeIndexOffsets;
+  FixedStreamArray<codeview::TypeIndexOffset> TypeIndexOffsets;
   HashTable HashAdjusters;
 
   const TpiStreamHeader *Header;
 };
 }
 }
 
 #endif

llvm/trunk/include/llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h

private:
   msf::MSFBuilder &Msf;
   BumpPtrAllocator &Allocator;
 
   size_t TypeRecordBytes = 0;
 
   Optional<PdbRaw_TpiVer> VerHeader;
   std::vector<ArrayRef<uint8_t>> TypeRecords;
   std::vector<uint32_t> TypeHashes;
-  std::vector<TypeIndexOffset> TypeIndexOffsets;
+  std::vector<codeview::TypeIndexOffset> TypeIndexOffsets;
   uint32_t HashStreamIndex = kInvalidStreamIndex;
   std::unique_ptr<BinaryByteStream> HashValueStream;
 
   const TpiStreamHeader *Header;
   uint32_t Idx;
 };
 }
 }
 
 #endif

llvm/trunk/include/llvm/Support/BinaryStreamArray.h

for (unsigned I = 0; I < N; ++I) {
           moveToEnd();
         }
       }
     }
     return *this;
   }
 
   uint32_t offset() const { return AbsOffset; }
+  uint32_t getRecordLength() const { return ThisLen; }
 
 private:
   void moveToEnd() {
     Array = nullptr;
     ThisLen = 0;
   }
   void markError() {
     moveToEnd();

 /// having a fixed-length.  As with VarStreamArray, there is no upfront
 /// cost associated with building or copying a FixedStreamArray, as the
 /// memory for each element is not read from the backing stream until that
 /// element is iterated.
 template <typename T> class FixedStreamArray {
   friend class FixedStreamArrayIterator<T>;
 
 public:
+  typedef FixedStreamArrayIterator<T> Iterator;
+
   FixedStreamArray() = default;
   explicit FixedStreamArray(BinaryStreamRef Stream) : Stream(Stream) {
     assert(Stream.getLength() % sizeof(T) == 0);
   }
 
   bool operator==(const FixedStreamArray<T> &Other) const {
     return Stream == Other.Stream;
   }
public:
   }
 
   FixedStreamArrayIterator<T> &operator+=(std::ptrdiff_t N) {
     Index += N;
     return *this;
   }
 
   FixedStreamArrayIterator<T> &operator-=(std::ptrdiff_t N) {
-    assert(Index >= N);
+    assert(std::ptrdiff_t(Index) >= N);
     Index -= N;
     return *this;
   }
 
   std::ptrdiff_t operator-(const FixedStreamArrayIterator<T> &R) const {
     assert(Array == R.Array);
     assert(Index >= R.Index);
     return Index - R.Index;

llvm/trunk/lib/DebugInfo/CodeView/CMakeLists.txt

 add_llvm_library(LLVMDebugInfoCodeView
   CodeViewError.cpp
   CodeViewRecordIO.cpp
   CVSymbolVisitor.cpp
   CVTypeDumper.cpp
   CVTypeVisitor.cpp
   EnumTables.cpp
   Formatters.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
   TypeRecordMapping.cpp
   TypeSerializer.cpp
   TypeStreamMerger.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo/CodeView
   )

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

 
 using namespace llvm;
 using namespace llvm::codeview;
 
 CVTypeVisitor::CVTypeVisitor(TypeVisitorCallbacks &Callbacks)
     : Callbacks(Callbacks) {}
 
 template <typename T>
-static Error visitKnownRecord(CVTypeVisitor &Visitor, CVType &Record,
-                              TypeVisitorCallbacks &Callbacks) {
+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();
 }
 
 template <typename T>

 Error CVTypeVisitor::finishVisitation(CVType &Record) {
   switch (Record.Type) {
   default:
     if (auto EC = Callbacks.visitUnknownType(Record))
       return EC;
     break;
 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
   case EnumName: {                                                             \
-    if (auto EC = visitKnownRecord<Name##Record>(*this, Record, Callbacks))    \
+    if (auto EC = visitKnownRecord<Name##Record>(Record, Callbacks))           \
       return EC;                                                               \
     break;                                                                     \
   }
 #define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)                  \
   TYPE_RECORD(EnumVal, EnumVal, AliasName)
 #define MEMBER_RECORD(EnumName, EnumVal, Name)
 #define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
 #include "llvm/DebugInfo/CodeView/TypeRecords.def"

llvm/trunk/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/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),
+      InternalVisitor(Pipeline), PartialOffsets(PartialOffsets) {
+  Pipeline.addCallbackToPipeline(Deserializer);
+  Pipeline.addCallbackToPipeline(DatabaseVisitor);
+
+  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);
+  CVTypeVisitor V(Callbacks);
+  return V.visitTypeRecord(Record, TI);
+}
+
+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 = InternalVisitor.visitTypeRecord(*RI, Begin))
+      return EC;
+    KnownOffsets[Begin.toArrayIndex()] = BeginOffset;
+
+    BeginOffset += RI.getRecordLength();
+    ++Begin;
+    ++RI;
+  }
+
+  return Error::success();
+}

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

static const SimpleTypeEntry SimpleTypeNames[] = {
     {"_Complex long double*", SimpleTypeKind::Complex80},
     {"_Complex __float128*", SimpleTypeKind::Complex128},
     {"bool*", SimpleTypeKind::Boolean8},
     {"__bool16*", SimpleTypeKind::Boolean16},
     {"__bool32*", SimpleTypeKind::Boolean32},
     {"__bool64*", SimpleTypeKind::Boolean64},
 };
 
-TypeDatabase::TypeDatabase(uint32_t ExpectedSize) : TypeNameStorage(Allocator) {
-  CVUDTNames.reserve(ExpectedSize);
-  TypeRecords.reserve(ExpectedSize);
+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())
+    grow();
+  recordType(Name, TI, Data);
+  return TI;
 }
 
-/// Gets the type index for the next type record.
-TypeIndex TypeDatabase::getNextTypeIndex() const {
-  return TypeIndex(TypeIndex::FirstNonSimpleIndex + CVUDTNames.size());
-}
+void TypeDatabase::recordType(StringRef Name, TypeIndex Index,
+                              const CVType &Data) {
+  uint32_t AI = Index.toArrayIndex();
 
-/// Records the name of a type, and reserves its type index.
-void TypeDatabase::recordType(StringRef Name, const CVType &Data) {
-  CVUDTNames.push_back(Name);
-  TypeRecords.push_back(Data);
+  assert(!contains(Index));
+  assert(AI < capacity());
+
+  CVUDTNames[AI] = Name;
+  TypeRecords[AI] = Data;
+  ValidRecords.set(AI);
+  ++Count;
 }
 
 /// Saves the name in a StringSet and creates a stable StringRef.
 StringRef TypeDatabase::saveTypeName(StringRef TypeName) {
   return TypeNameStorage.save(TypeName);
 }
 
 StringRef TypeDatabase::getTypeName(TypeIndex Index) const {
for (const auto &SimpleTypeName : SimpleTypeNames) {
         // Otherwise, this is a pointer type. We gloss over the distinction
         // between near, far, 64, 32, etc, and just give a pointer type.
         return SimpleTypeName.Name;
       }
     }
     return "<unknown simple type>";
   }
 
-  uint32_t I = Index.getIndex() - TypeIndex::FirstNonSimpleIndex;
-  if (I < CVUDTNames.size())
-    return CVUDTNames[I];
+  if (contains(Index))
+    return CVUDTNames[Index.toArrayIndex()];
 
   return "<unknown UDT>";
 }
 
 const CVType &TypeDatabase::getTypeRecord(TypeIndex Index) const {
-  return TypeRecords[toArrayIndex(Index)];
+  assert(contains(Index));
+  return TypeRecords[Index.toArrayIndex()];
 }
 
 CVType &TypeDatabase::getTypeRecord(TypeIndex Index) {
-  return TypeRecords[toArrayIndex(Index)];
+  assert(contains(Index));
+  return TypeRecords[Index.toArrayIndex()];
 }
 
-bool TypeDatabase::containsTypeIndex(TypeIndex Index) const {
-  return toArrayIndex(Index) < CVUDTNames.size();
-}
+bool TypeDatabase::contains(TypeIndex Index) const {
+  uint32_t AI = Index.toArrayIndex();
+  if (AI >= capacity())
+    return false;
 
-uint32_t TypeDatabase::size() const { return CVUDTNames.size(); }
-
-uint32_t TypeDatabase::toArrayIndex(TypeIndex Index) const {
-  assert(Index.getIndex() >= TypeIndex::FirstNonSimpleIndex);
-  return Index.getIndex() - TypeIndex::FirstNonSimpleIndex;
+  return ValidRecords.test(AI);
 }
 
-RandomAccessTypeDatabase::RandomAccessTypeDatabase(uint32_t ExpectedSize)
-    : TypeDatabase(ExpectedSize) {
-  ValidRecords.resize(ExpectedSize);
-  CVUDTNames.resize(ExpectedSize);
-  TypeRecords.resize(ExpectedSize);
-}
+uint32_t TypeDatabase::size() const { return Count; }
 
-void RandomAccessTypeDatabase::recordType(StringRef Name, TypeIndex Index,
-                                          const CVType &Data) {
-  assert(!containsTypeIndex(Index));
-  uint32_t ZI = Index.getIndex() - TypeIndex::FirstNonSimpleIndex;
+uint32_t TypeDatabase::capacity() const { return TypeRecords.size(); }
 
-  CVUDTNames[ZI] = Name;
-  TypeRecords[ZI] = Data;
-  ValidRecords.set(ZI);
+void TypeDatabase::grow() {
+  TypeRecords.emplace_back();
+  CVUDTNames.emplace_back();
+  ValidRecords.resize(ValidRecords.size() + 1);
 }
 
-StringRef RandomAccessTypeDatabase::getTypeName(TypeIndex Index) const {
-  assert(containsTypeIndex(Index));
-  return TypeDatabase::getTypeName(Index);
-}
-
-const CVType &RandomAccessTypeDatabase::getTypeRecord(TypeIndex Index) const {
-  assert(containsTypeIndex(Index));
-  return TypeDatabase::getTypeRecord(Index);
-}
+bool TypeDatabase::empty() const { return size() == 0; }
 
-CVType &RandomAccessTypeDatabase::getTypeRecord(TypeIndex Index) {
-  assert(containsTypeIndex(Index));
-  return TypeDatabase::getTypeRecord(Index);
-}
-
-bool RandomAccessTypeDatabase::containsTypeIndex(TypeIndex Index) const {
-  if (Index.isSimple())
-    return true;
+TypeIndex TypeDatabase::getAppendIndex() const {
+  if (empty())
+    return TypeIndex::fromArrayIndex(0);
 
-  return ValidRecords.test(toArrayIndex(Index));
+  int Index = ValidRecords.find_last();
+  assert(Index != -1);
+  return TypeIndex::fromArrayIndex(Index) + 1;
 }
-
-uint32_t RandomAccessTypeDatabase::size() const { return ValidRecords.count(); }

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

 
 #include "llvm/ADT/SmallString.h"
 
 using namespace llvm;
 
 using namespace llvm::codeview;
 
 Error TypeDatabaseVisitor::visitTypeBegin(CVType &Record) {
-  assert(TypeDB.is<TypeDatabase *>());
-
   assert(!IsInFieldList);
   // Reset Name to the empty string. If the visitor sets it, we know it.
   Name = "";
 
   if (Record.Type == LF_FIELDLIST) {
     // Record that we're in a field list so that members do not get assigned
     // type indices.
     IsInFieldList = true;
   }
   return Error::success();
 }
 
-StringRef TypeDatabaseVisitor::getTypeName(TypeIndex Index) const {
-  if (auto DB = TypeDB.get<TypeDatabase *>())
-    return DB->getTypeName(Index);
-  else if (auto DB = TypeDB.get<RandomAccessTypeDatabase *>())
-    return DB->getTypeName(Index);
-
-  llvm_unreachable("Invalid TypeDB Kind!");
-}
-
-StringRef TypeDatabaseVisitor::saveTypeName(StringRef Name) {
-  if (auto DB = TypeDB.get<TypeDatabase *>())
-    return DB->saveTypeName(Name);
-  else if (auto DB = TypeDB.get<RandomAccessTypeDatabase *>())
-    return DB->saveTypeName(Name);
-
-  llvm_unreachable("Invalid TypeDB Kind!");
-}
-
 Error TypeDatabaseVisitor::visitTypeBegin(CVType &Record, TypeIndex Index) {
-  assert(TypeDB.is<RandomAccessTypeDatabase *>());
-
   if (auto EC = visitTypeBegin(Record))
     return EC;
 
   CurrentTypeIndex = Index;
   return Error::success();
 }
 
+StringRef TypeDatabaseVisitor::getTypeName(TypeIndex Index) const {
+  return TypeDB->getTypeName(Index);
+}
+
+StringRef TypeDatabaseVisitor::saveTypeName(StringRef Name) {
+  return TypeDB->saveTypeName(Name);
+}
+
 Error TypeDatabaseVisitor::visitTypeEnd(CVType &CVR) {
   if (CVR.Type == LF_FIELDLIST) {
     assert(IsInFieldList);
     IsInFieldList = false;
   }
   assert(!IsInFieldList);
 
   // Record every type that is not a field list member, even if Name is empty.
   // CVUDTNames is indexed by type index, and must have one entry for every
   // type.  Field list members are not recorded, and are only referenced by
   // their containing field list record.
-  if (auto DB = TypeDB.get<TypeDatabase *>())
-    DB->recordType(Name, CVR);
-  else if (auto DB = TypeDB.get<RandomAccessTypeDatabase *>())
-    DB->recordType(Name, CurrentTypeIndex, CVR);
+  if (CurrentTypeIndex)
+    TypeDB->recordType(Name, *CurrentTypeIndex, CVR);
+  else
+    TypeDB->appendType(Name, CVR);
 
+  CurrentTypeIndex.reset();
   return Error::success();
 }
 
 Error TypeDatabaseVisitor::visitMemberBegin(CVMemberRecord &Record) {
   assert(IsInFieldList);
   // Reset Name to the empty string. If the visitor sets it, we know it.
   Name = "";
   return Error::success();

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

void TypeDumpVisitor::printTypeIndex(StringRef FieldName, TypeIndex TI) const {
   CVTypeDumper::printTypeIndex(*W, FieldName, TI, TypeDB);
 }
 
 void TypeDumpVisitor::printItemIndex(StringRef FieldName, TypeIndex TI) const {
   CVTypeDumper::printTypeIndex(*W, FieldName, TI, getSourceDB());
 }
 
 Error TypeDumpVisitor::visitTypeBegin(CVType &Record) {
+  TypeIndex TI = getSourceDB().getAppendIndex();
+  return visitTypeBegin(Record, TI);
+}
+
+Error TypeDumpVisitor::visitTypeBegin(CVType &Record, TypeIndex Index) {
   W->startLine() << getLeafTypeName(Record.Type);
-  W->getOStream() << " ("
-                  << HexNumber(getSourceDB().getNextTypeIndex().getIndex())
-                  << ")";
+  W->getOStream() << " (" << HexNumber(Index.getIndex()) << ")";
   W->getOStream() << " {\n";
   W->indent();
   W->printEnum("TypeLeafKind", unsigned(Record.Type),
                makeArrayRef(LeafTypeNames));
   return Error::success();
 }
 
 Error TypeDumpVisitor::visitTypeEnd(CVType &Record) {

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

 
 uint32_t TpiStreamBuilder::calculateHashBufferSize() const {
   assert((TypeRecords.size() == TypeHashes.size() || TypeHashes.empty()) &&
          "either all or no type records should have hashes");
   return TypeHashes.size() * sizeof(ulittle32_t);
 }
 
 uint32_t TpiStreamBuilder::calculateIndexOffsetSize() const {
-  return TypeIndexOffsets.size() * sizeof(TypeIndexOffset);
+  return TypeIndexOffsets.size() * sizeof(codeview::TypeIndexOffset);
 }
 
 Error TpiStreamBuilder::finalizeMsfLayout() {
   uint32_t Length = calculateSerializedLength();
   if (auto EC = Msf.setStreamSize(Idx, Length))
     return EC;
 
   uint32_t HashStreamSize =

llvm/trunk/tools/llvm-pdbdump/LLVMOutputStyle.cpp

Error handleInlineeLines() override {
     return Error::success();
   }
 
 private:
   Error dumpTypeRecord(StringRef Label, TypeDatabase &DB, TypeIndex Index) {
     CompactTypeDumpVisitor CTDV(DB, Index, &P);
     CVTypeVisitor Visitor(CTDV);
     DictScope D(P, Label);
-    if (DB.containsTypeIndex(Index)) {
+    if (DB.contains(Index)) {
       CVType &Type = DB.getTypeRecord(Index);
       if (auto EC = Visitor.visitTypeRecord(Type))
         return EC;
     } else {
       P.printString(
           llvm::formatv("Index: {0:x} (unknown function)", Index.getIndex())
               .str());
     }

llvm/trunk/unittests/DebugInfo/CMakeLists.txt

-
+add_subdirectory(CodeView)
 add_subdirectory(DWARF)
 add_subdirectory(PDB)

llvm/trunk/unittests/DebugInfo/CodeView/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  DebugInfoCodeView
+  )
+
+set(DebugInfoCodeViewSources
+  RandomAccessVisitorTest.cpp
+  )
+
+add_llvm_unittest(DebugInfoCodeViewTests
+  ${DebugInfoCodeViewSources}
+  )

llvm/trunk/unittests/DebugInfo/CodeView/ErrorChecking.h

+//===- ErrorChecking.h - Helpers for verifying llvm::Errors -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UNITTESTS_DEBUGINFO_CODEVIEW_ERRORCHECKING_H
+#define LLVM_UNITTESTS_DEBUGINFO_CODEVIEW_ERRORCHECKING_H
+
+#define EXPECT_NO_ERROR(Err)                                                   \
+  {                                                                            \
+    auto E = Err;                                                              \
+    EXPECT_FALSE(static_cast<bool>(E));                                        \
+    if (E)                                                                     \
+      consumeError(std::move(E));                                              \
+  }
+
+#define EXPECT_ERROR(Err)                                                      \
+  {                                                                            \
+    auto E = Err;                                                              \
+    EXPECT_TRUE(static_cast<bool>(E));                                         \
+    if (E)                                                                     \
+      consumeError(std::move(E));                                              \
+  }
+
+#define EXPECT_EXPECTED(Exp)                                                   \
+  {                                                                            \
+    auto E = Exp.takeError();                                                  \
+    EXPECT_FALSE(static_cast<bool>(E));                                        \
+    if (E) {                                                                   \
+      consumeError(std::move(E));                                              \
+      return;                                                                  \
+    }                                                                          \
+  }
+
+#define EXPECT_EXPECTED_EQ(Val, Exp)                                           \
+  {                                                                            \
+    auto Result = Exp;                                                         \
+    auto E = Result.takeError();                                               \
+    EXPECT_FALSE(static_cast<bool>(E));                                        \
+    if (E) {                                                                   \
+      consumeError(std::move(E));                                              \
+      return;                                                                  \
+    }                                                                          \
+    EXPECT_EQ(Val, *Result);                                                   \
+  }
+
+#define EXPECT_UNEXPECTED(Exp)                                                 \
+  {                                                                            \
+    auto E = Exp.takeError();                                                  \
+    EXPECT_TRUE(static_cast<bool>(E));                                         \
+    if (E) {                                                                   \
+      consumeError(std::move(E));                                              \
+      return;                                                                  \
+    }                                                                          \
+  }
+
+#endif

llvm/trunk/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/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"
+
+using namespace llvm;
+using namespace llvm::codeview;
+using namespace llvm::pdb;
+
+namespace llvm {
+namespace codeview {
+inline bool operator==(const ArrayRecord &R1, const ArrayRecord &R2) {
+  if (R1.ElementType != R2.ElementType)
+    return false;
+  if (R1.IndexType != R2.IndexType)
+    return false;
+  if (R1.Name != R2.Name)
+    return false;
+  if (R1.Size != R2.Size)
+    return false;
+  return true;
+}
+inline bool operator!=(const ArrayRecord &R1, const ArrayRecord &R2) {
+  return !(R1 == R2);
+}
+
+inline bool operator==(const CVType &R1, const CVType &R2) {
+  if (R1.Type != R2.Type)
+    return false;
+  if (R1.RecordData != R2.RecordData)
+    return false;
+  return true;
+}
+inline bool operator!=(const CVType &R1, const CVType &R2) {
+  return !(R1 == R2);
+}
+}
+}
+
+namespace llvm {
+template <> struct BinaryItemTraits<CVType> {
+  static size_t length(const CVType &Item) { return Item.length(); }
+  static ArrayRef<uint8_t> bytes(const CVType &Item) { return Item.data(); }
+};
+}
+
+namespace {
+
+class MockCallbacks : public TypeVisitorCallbacks {
+public:
+  virtual Error visitTypeBegin(CVType &CVR, TypeIndex Index) {
+    Indices.push_back(Index);
+    return Error::success();
+  }
+  virtual Error visitKnownRecord(CVType &CVR, ArrayRecord &AR) {
+    VisitedRecords.push_back(AR);
+    RawRecords.push_back(CVR);
+    return Error::success();
+  }
+
+  uint32_t count() const {
+    assert(Indices.size() == RawRecords.size());
+    assert(Indices.size() == VisitedRecords.size());
+    return Indices.size();
+  }
+  std::vector<TypeIndex> Indices;
+  std::vector<CVType> RawRecords;
+  std::vector<ArrayRecord> VisitedRecords;
+};
+
+class RandomAccessVisitorTest : public testing::Test {
+public:
+  RandomAccessVisitorTest() {}
+
+  static void SetUpTestCase() {
+    GlobalState = llvm::make_unique<GlobalTestState>();
+
+    TypeTableBuilder Builder(GlobalState->Allocator);
+
+    uint32_t Offset = 0;
+    for (int I = 0; I < 11; ++I) {
+      ArrayRecord AR(TypeRecordKind::Array);
+      AR.ElementType = TypeIndex::Int32();
+      AR.IndexType = TypeIndex::UInt32();
+      AR.Size = I;
+      std::string Name;
+      raw_string_ostream Stream(Name);
+      Stream << "Array [" << I << "]";
+      AR.Name = GlobalState->Strings.save(Stream.str());
+      GlobalState->Records.push_back(AR);
+      GlobalState->Indices.push_back(Builder.writeKnownType(AR));
+
+      CVType Type(TypeLeafKind::LF_ARRAY, Builder.records().back());
+      GlobalState->TypeVector.push_back(Type);
+
+      GlobalState->AllOffsets.push_back(
+          {GlobalState->Indices.back(), ulittle32_t(Offset)});
+      Offset += Type.length();
+    }
+
+    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) {
+    TypeIndex TI = TypeIndex::fromArrayIndex(Index);
+    if (!Visitor.database().contains(TI))
+      return false;
+    if (GlobalState->TypeVector[Index] != Visitor.database().getTypeRecord(TI))
+      return false;
+    return true;
+  }
+
+  bool ValidateVisitedRecord(uint32_t VisitationOrder,
+                             uint32_t GlobalArrayIndex) {
+    TypeIndex TI = TypeIndex::fromArrayIndex(GlobalArrayIndex);
+    if (TI != TestState->Callbacks.Indices[VisitationOrder])
+      return false;
+
+    if (GlobalState->TypeVector[TI.toArrayIndex()] !=
+        TestState->Callbacks.RawRecords[VisitationOrder])
+      return false;
+
+    if (GlobalState->Records[TI.toArrayIndex()] !=
+        TestState->Callbacks.VisitedRecords[VisitationOrder])
+      return false;
+
+    return true;
+  }
+
+  struct GlobalTestState {
+    GlobalTestState() : Strings(Allocator), ItemStream(llvm::support::little) {}
+
+    BumpPtrAllocator Allocator;
+    StringSaver Strings;
+
+    std::vector<ArrayRecord> Records;
+    std::vector<TypeIndex> Indices;
+    std::vector<TypeIndexOffset> AllOffsets;
+    std::vector<CVType> TypeVector;
+    BinaryItemStream<CVType> ItemStream;
+    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();
+    uint32_t Size = Count * sizeof(TypeIndexOffset);
+    uint8_t *Buffer = GlobalState->Allocator.Allocate<uint8_t>(Size);
+    MutableArrayRef<uint8_t> Bytes(Buffer, Size);
+    Storage = MutableBinaryByteStream(Bytes, support::little);
+    BinaryStreamWriter Writer(Storage);
+    for (const auto I : Indices)
+      consumeError(Writer.writeObject(GlobalState->AllOffsets[I]));
+
+    BinaryStreamReader Reader(Storage);
+    FixedStreamArray<TypeIndexOffset> Result;
+    consumeError(Reader.readArray(Result, Count));
+    return Result;
+  }
+
+  static std::unique_ptr<GlobalTestState> GlobalState;
+  std::unique_ptr<PerTestState> TestState;
+};
+
+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);
+
+  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));
+  }
+
+  // [0,8) should be present
+  EXPECT_EQ(8, Visitor.database().size());
+  for (uint32_t I = 0; I < 8; ++I)
+    EXPECT_TRUE(ValidateDatabaseRecord(Visitor, I));
+
+  // 5, 5, 5
+  EXPECT_EQ(3, 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);
+
+  for (uint32_t I : IndicesToVisit) {
+    TypeIndex TI = TypeIndex::fromArrayIndex(I);
+    EXPECT_NO_ERROR(Visitor.visitTypeIndex(TI, TestState->Pipeline));
+  }
+
+  // [0, 7]
+  EXPECT_EQ(8, Visitor.database().size());
+  for (uint32_t I = 0; I < 8; ++I)
+    EXPECT_TRUE(ValidateDatabaseRecord(Visitor, I));
+
+  // 2, 4, 7
+  EXPECT_EQ(3, 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);
+
+  for (uint32_t I : IndicesToVisit) {
+    TypeIndex TI = TypeIndex::fromArrayIndex(I);
+    EXPECT_NO_ERROR(Visitor.visitTypeIndex(TI, TestState->Pipeline));
+  }
+
+  // [0, 7]
+  EXPECT_EQ(8, Visitor.database().size());
+  for (uint32_t I = 0; I < 8; ++I)
+    EXPECT_TRUE(ValidateDatabaseRecord(Visitor, I));
+
+  // 2, 4, 7
+  EXPECT_EQ(3, 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);
+
+  for (uint32_t I : IndicesToVisit) {
+    TypeIndex TI = TypeIndex::fromArrayIndex(I);
+    EXPECT_NO_ERROR(Visitor.visitTypeIndex(TI, TestState->Pipeline));
+  }
+
+  // [0, 8) should be visited.
+  EXPECT_EQ(8, Visitor.database().size());
+  for (uint32_t I = 0; I < 8; ++I)
+    EXPECT_TRUE(ValidateDatabaseRecord(Visitor, I));
+
+  // [0, 2]
+  EXPECT_EQ(3, 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);
+
+  for (uint32_t I : IndicesToVisit) {
+    TypeIndex TI = TypeIndex::fromArrayIndex(I);
+    EXPECT_NO_ERROR(Visitor.visitTypeIndex(TI, TestState->Pipeline));
+  }
+
+  // [4, 9)
+  EXPECT_EQ(5, Visitor.database().size());
+  for (uint32_t I = 4; I < 9; ++I)
+    EXPECT_TRUE(ValidateDatabaseRecord(Visitor, I));
+
+  // 5, 7
+  EXPECT_EQ(2, TestState->Callbacks.count());
+  for (auto &I : enumerate(IndicesToVisit))
+    EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
+}