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