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