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