unittests/DebugInfo/CodeView/RandomAccessVisitorTest.cpp

   1 //===- llvm/unittest/DebugInfo/CodeView/RandomAccessVisitorTest.cpp -------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/DebugInfo/CodeView/AppendingTypeTableBuilder.h"
  10 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
  11 #include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
  12 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
  13 #include "llvm/DebugInfo/CodeView/TypeRecordMapping.h"
  14 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
  15 #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
  16 #include "llvm/Support/Allocator.h"
  17 #include "llvm/Support/BinaryItemStream.h"
  18 #include "llvm/Support/Error.h"
  19 #include "llvm/Testing/Support/Error.h"
  20
  21 #include "gtest/gtest.h"
  22
  23 using namespace llvm;
  24 using namespace llvm::codeview;
  25 using namespace llvm::pdb;
  26
  27 namespace llvm {
  28 namespace codeview {
  29 inline bool operator==(const ArrayRecord &R1, const ArrayRecord &R2) {
  30   if (R1.ElementType != R2.ElementType)
  31     return false;
  32   if (R1.IndexType != R2.IndexType)
  33     return false;
  34   if (R1.Name != R2.Name)
  35     return false;
  36   if (R1.Size != R2.Size)
  37     return false;
  38   return true;
  39 }
  40 inline bool operator!=(const ArrayRecord &R1, const ArrayRecord &R2) {
  41   return !(R1 == R2);
  42 }
  43
  44 inline bool operator==(const CVType &R1, const CVType &R2) {
  45   if (R1.RecordData != R2.RecordData)
  46     return false;
  47   return true;
  48 }
  49 inline bool operator!=(const CVType &R1, const CVType &R2) {
  50   return !(R1 == R2);
  51 }
  52 }
  53 }
  54
  55 namespace llvm {
  56 template <> struct BinaryItemTraits<CVType> {
  57   static size_t length(const CVType &Item) { return Item.length(); }
  58   static ArrayRef<uint8_t> bytes(const CVType &Item) { return Item.data(); }
  59 };
  60 }
  61
  62 namespace {
  63
  64 class MockCallbacks : public TypeVisitorCallbacks {
  65 public:
  66   virtual Error visitTypeBegin(CVType &CVR, TypeIndex Index) {
  67     Indices.push_back(Index);
  68     return Error::success();
  69   }
  70   virtual Error visitKnownRecord(CVType &CVR, ArrayRecord &AR) {
  71     VisitedRecords.push_back(AR);
  72     RawRecords.push_back(CVR);
  73     return Error::success();
  74   }
  75
  76   uint32_t count() const {
  77     assert(Indices.size() == RawRecords.size());
  78     assert(Indices.size() == VisitedRecords.size());
  79     return Indices.size();
  80   }
  81   std::vector<TypeIndex> Indices;
  82   std::vector<CVType> RawRecords;
  83   std::vector<ArrayRecord> VisitedRecords;
  84 };
  85
  86 class RandomAccessVisitorTest : public testing::Test {
  87 public:
  88   RandomAccessVisitorTest() {}
  89
  90   static void SetUpTestCase() {
  91     GlobalState = std::make_unique<GlobalTestState>();
  92
  93     AppendingTypeTableBuilder Builder(GlobalState->Allocator);
  94
  95     uint32_t Offset = 0;
  96     for (int I = 0; I < 11; ++I) {
  97       ArrayRecord AR(TypeRecordKind::Array);
  98       AR.ElementType = TypeIndex::Int32();
  99       AR.IndexType = TypeIndex::UInt32();
 100       AR.Size = I;
 101       std::string Name;
 102       raw_string_ostream Stream(Name);
 103       Stream << "Array [" << I << "]";
 104       AR.Name = GlobalState->Strings.save(Stream.str());
 105       GlobalState->Records.push_back(AR);
 106       GlobalState->Indices.push_back(Builder.writeLeafType(AR));
 107
 108       CVType Type(Builder.records().back());
 109       GlobalState->TypeVector.push_back(Type);
 110
 111       GlobalState->AllOffsets.push_back(
 112           {GlobalState->Indices.back(), ulittle32_t(Offset)});
 113       Offset += Type.length();
 114     }
 115
 116     GlobalState->ItemStream.setItems(GlobalState->TypeVector);
 117     GlobalState->TypeArray = VarStreamArray<CVType>(GlobalState->ItemStream);
 118   }
 119
 120   static void TearDownTestCase() { GlobalState.reset(); }
 121
 122   void SetUp() override {
 123     TestState = std::make_unique<PerTestState>();
 124   }
 125
 126   void TearDown() override { TestState.reset(); }
 127
 128 protected:
 129   bool ValidateDatabaseRecord(LazyRandomTypeCollection &Types, uint32_t Index) {
 130     TypeIndex TI = TypeIndex::fromArrayIndex(Index);
 131     if (!Types.contains(TI))
 132       return false;
 133     if (GlobalState->TypeVector[Index] != Types.getType(TI))
 134       return false;
 135     return true;
 136   }
 137
 138   bool ValidateVisitedRecord(uint32_t VisitationOrder,
 139                              uint32_t GlobalArrayIndex) {
 140     TypeIndex TI = TypeIndex::fromArrayIndex(GlobalArrayIndex);
 141     if (TI != TestState->Callbacks.Indices[VisitationOrder])
 142       return false;
 143
 144     if (GlobalState->TypeVector[TI.toArrayIndex()] !=
 145         TestState->Callbacks.RawRecords[VisitationOrder])
 146       return false;
 147
 148     if (GlobalState->Records[TI.toArrayIndex()] !=
 149         TestState->Callbacks.VisitedRecords[VisitationOrder])
 150       return false;
 151
 152     return true;
 153   }
 154
 155   struct GlobalTestState {
 156     GlobalTestState() : Strings(Allocator), ItemStream(llvm::support::little) {}
 157
 158     BumpPtrAllocator Allocator;
 159     StringSaver Strings;
 160
 161     std::vector<ArrayRecord> Records;
 162     std::vector<TypeIndex> Indices;
 163     std::vector<TypeIndexOffset> AllOffsets;
 164     std::vector<CVType> TypeVector;
 165     BinaryItemStream<CVType> ItemStream;
 166     VarStreamArray<CVType> TypeArray;
 167
 168     MutableBinaryByteStream Stream;
 169   };
 170
 171   struct PerTestState {
 172     FixedStreamArray<TypeIndexOffset> Offsets;
 173
 174     MockCallbacks Callbacks;
 175   };
 176
 177   FixedStreamArray<TypeIndexOffset>
 178   createPartialOffsets(MutableBinaryByteStream &Storage,
 179                        std::initializer_list<uint32_t> Indices) {
 180
 181     uint32_t Count = Indices.size();
 182     uint32_t Size = Count * sizeof(TypeIndexOffset);
 183     uint8_t *Buffer = GlobalState->Allocator.Allocate<uint8_t>(Size);
 184     MutableArrayRef<uint8_t> Bytes(Buffer, Size);
 185     Storage = MutableBinaryByteStream(Bytes, support::little);
 186     BinaryStreamWriter Writer(Storage);
 187     for (const auto I : Indices)
 188       consumeError(Writer.writeObject(GlobalState->AllOffsets[I]));
 189
 190     BinaryStreamReader Reader(Storage);
 191     FixedStreamArray<TypeIndexOffset> Result;
 192     consumeError(Reader.readArray(Result, Count));
 193     return Result;
 194   }
 195
 196   static std::unique_ptr<GlobalTestState> GlobalState;
 197   std::unique_ptr<PerTestState> TestState;
 198 };
 199
 200 std::unique_ptr<RandomAccessVisitorTest::GlobalTestState>
 201     RandomAccessVisitorTest::GlobalState;
 202 }
 203
 204 TEST_F(RandomAccessVisitorTest, MultipleVisits) {
 205   TestState->Offsets = createPartialOffsets(GlobalState->Stream, {0, 8});
 206   LazyRandomTypeCollection Types(GlobalState->TypeArray,
 207                                  GlobalState->TypeVector.size(),
 208                                  TestState->Offsets);
 209
 210   std::vector<uint32_t> IndicesToVisit = {5, 5, 5};
 211
 212   for (uint32_t I : IndicesToVisit) {
 213     TypeIndex TI = TypeIndex::fromArrayIndex(I);
 214     CVType T = Types.getType(TI);
 215     EXPECT_THAT_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks),
 216                       Succeeded());
 217   }
 218
 219   // [0,8) should be present
 220   EXPECT_EQ(8u, Types.size());
 221   for (uint32_t I = 0; I < 8; ++I)
 222     EXPECT_TRUE(ValidateDatabaseRecord(Types, I));
 223
 224   // 5, 5, 5
 225   EXPECT_EQ(3u, TestState->Callbacks.count());
 226   for (auto I : enumerate(IndicesToVisit))
 227     EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
 228 }
 229
 230 TEST_F(RandomAccessVisitorTest, DescendingWithinChunk) {
 231   // Visit multiple items from the same "chunk" in reverse order.  In this
 232   // example, it's 7 then 4 then 2.  At the end, all records from 0 to 7 should
 233   // be known by the database, but only 2, 4, and 7 should have been visited.
 234   TestState->Offsets = createPartialOffsets(GlobalState->Stream, {0, 8});
 235
 236   std::vector<uint32_t> IndicesToVisit = {7, 4, 2};
 237
 238   LazyRandomTypeCollection Types(GlobalState->TypeArray,
 239                                  GlobalState->TypeVector.size(),
 240                                  TestState->Offsets);
 241   for (uint32_t I : IndicesToVisit) {
 242     TypeIndex TI = TypeIndex::fromArrayIndex(I);
 243     CVType T = Types.getType(TI);
 244     EXPECT_THAT_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks),
 245                       Succeeded());
 246   }
 247
 248   // [0, 7]
 249   EXPECT_EQ(8u, Types.size());
 250   for (uint32_t I = 0; I < 8; ++I)
 251     EXPECT_TRUE(ValidateDatabaseRecord(Types, I));
 252
 253   // 2, 4, 7
 254   EXPECT_EQ(3u, TestState->Callbacks.count());
 255   for (auto I : enumerate(IndicesToVisit))
 256     EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
 257 }
 258
 259 TEST_F(RandomAccessVisitorTest, AscendingWithinChunk) {
 260   // * Visit multiple items from the same chunk in ascending order, ensuring
 261   //   that intermediate items are not visited.  In the below example, it's
 262   //   5 -> 6 -> 7 which come from the [4,8) chunk.
 263   TestState->Offsets = createPartialOffsets(GlobalState->Stream, {0, 8});
 264
 265   std::vector<uint32_t> IndicesToVisit = {2, 4, 7};
 266
 267   LazyRandomTypeCollection Types(GlobalState->TypeArray,
 268                                  GlobalState->TypeVector.size(),
 269                                  TestState->Offsets);
 270   for (uint32_t I : IndicesToVisit) {
 271     TypeIndex TI = TypeIndex::fromArrayIndex(I);
 272     CVType T = Types.getType(TI);
 273     EXPECT_THAT_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks),
 274                       Succeeded());
 275   }
 276
 277   // [0, 7]
 278   EXPECT_EQ(8u, Types.size());
 279   for (uint32_t I = 0; I < 8; ++I)
 280     EXPECT_TRUE(ValidateDatabaseRecord(Types, I));
 281
 282   // 2, 4, 7
 283   EXPECT_EQ(3u, TestState->Callbacks.count());
 284   for (auto &I : enumerate(IndicesToVisit))
 285     EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
 286 }
 287
 288 TEST_F(RandomAccessVisitorTest, StopPrematurelyInChunk) {
 289   // * Don't visit the last item in one chunk, ensuring that visitation stops
 290   //   at the record you specify, and the chunk is only partially visited.
 291   //   In the below example, this is tested by visiting 0 and 1 but not 2,
 292   //   all from the [0,3) chunk.
 293   TestState->Offsets = createPartialOffsets(GlobalState->Stream, {0, 8});
 294
 295   std::vector<uint32_t> IndicesToVisit = {0, 1, 2};
 296
 297   LazyRandomTypeCollection Types(GlobalState->TypeArray,
 298                                  GlobalState->TypeVector.size(),
 299                                  TestState->Offsets);
 300
 301   for (uint32_t I : IndicesToVisit) {
 302     TypeIndex TI = TypeIndex::fromArrayIndex(I);
 303     CVType T = Types.getType(TI);
 304     EXPECT_THAT_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks),
 305                       Succeeded());
 306   }
 307
 308   // [0, 8) should be visited.
 309   EXPECT_EQ(8u, Types.size());
 310   for (uint32_t I = 0; I < 8; ++I)
 311     EXPECT_TRUE(ValidateDatabaseRecord(Types, I));
 312
 313   // [0, 2]
 314   EXPECT_EQ(3u, TestState->Callbacks.count());
 315   for (auto I : enumerate(IndicesToVisit))
 316     EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
 317 }
 318
 319 TEST_F(RandomAccessVisitorTest, InnerChunk) {
 320   // Test that when a request comes from a chunk in the middle of the partial
 321   // offsets array, that items from surrounding chunks are not visited or
 322   // added to the database.
 323   TestState->Offsets = createPartialOffsets(GlobalState->Stream, {0, 4, 9});
 324
 325   std::vector<uint32_t> IndicesToVisit = {5, 7};
 326
 327   LazyRandomTypeCollection Types(GlobalState->TypeArray,
 328                                  GlobalState->TypeVector.size(),
 329                                  TestState->Offsets);
 330
 331   for (uint32_t I : IndicesToVisit) {
 332     TypeIndex TI = TypeIndex::fromArrayIndex(I);
 333     CVType T = Types.getType(TI);
 334     EXPECT_THAT_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks),
 335                       Succeeded());
 336   }
 337
 338   // [4, 9)
 339   EXPECT_EQ(5u, Types.size());
 340   for (uint32_t I = 4; I < 9; ++I)
 341     EXPECT_TRUE(ValidateDatabaseRecord(Types, I));
 342
 343   // 5, 7
 344   EXPECT_EQ(2u, TestState->Callbacks.count());
 345   for (auto &I : enumerate(IndicesToVisit))
 346     EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
 347 }
 348
 349 TEST_F(RandomAccessVisitorTest, CrossChunkName) {
 350   AppendingTypeTableBuilder Builder(GlobalState->Allocator);
 351
 352   // TypeIndex 0
 353   ClassRecord Class(TypeRecordKind::Class);
 354   Class.Name = "FooClass";
 355   Class.Options = ClassOptions::None;
 356   Class.MemberCount = 0;
 357   Class.Size = 4U;
 358   Class.DerivationList = TypeIndex::fromArrayIndex(0);
 359   Class.FieldList = TypeIndex::fromArrayIndex(0);
 360   Class.VTableShape = TypeIndex::fromArrayIndex(0);
 361   TypeIndex IndexZero = Builder.writeLeafType(Class);
 362
 363   // TypeIndex 1 refers to type index 0.
 364   ModifierRecord Modifier(TypeRecordKind::Modifier);
 365   Modifier.ModifiedType = TypeIndex::fromArrayIndex(0);
 366   Modifier.Modifiers = ModifierOptions::Const;
 367   TypeIndex IndexOne = Builder.writeLeafType(Modifier);
 368
 369   // set up a type stream that refers to the above two serialized records.
 370   std::vector<CVType> TypeArray = {
 371       {Builder.records()[0]},
 372       {Builder.records()[1]},
 373   };
 374   BinaryItemStream<CVType> ItemStream(llvm::support::little);
 375   ItemStream.setItems(TypeArray);
 376   VarStreamArray<CVType> TypeStream(ItemStream);
 377
 378   // Figure out the byte offset of the second item.
 379   auto ItemOneIter = TypeStream.begin();
 380   ++ItemOneIter;
 381
 382   // Set up a partial offsets buffer that contains the first and second items
 383   // in separate chunks.
 384   std::vector<TypeIndexOffset> TIO;
 385   TIO.push_back({IndexZero, ulittle32_t(0u)});
 386   TIO.push_back({IndexOne, ulittle32_t(ItemOneIter.offset())});
 387   ArrayRef<uint8_t> Buffer(reinterpret_cast<const uint8_t *>(TIO.data()),
 388                            TIO.size() * sizeof(TypeIndexOffset));
 389
 390   BinaryStreamReader Reader(Buffer, llvm::support::little);
 391   FixedStreamArray<TypeIndexOffset> PartialOffsets;
 392   ASSERT_THAT_ERROR(Reader.readArray(PartialOffsets, 2), Succeeded());
 393
 394   LazyRandomTypeCollection Types(TypeStream, 2, PartialOffsets);
 395
 396   StringRef Name = Types.getTypeName(IndexOne);
 397   EXPECT_EQ("const FooClass", Name);
 398 }