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