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/Support/Allocator.h"
16#include "llvm/Support/BinaryByteStream.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
23using namespace llvm;
24using namespace llvm::codeview;
25
26namespace llvm {
27namespace codeview {
28inline bool operator==(const ArrayRecord &R1, const ArrayRecord &R2) {
29 if (R1.ElementType != R2.ElementType)
30 return false;
31 if (R1.IndexType != R2.IndexType)
32 return false;
33 if (R1.Name != R2.Name)
34 return false;
35 if (R1.Size != R2.Size)
36 return false;
37 return true;
38}
39inline bool operator!=(const ArrayRecord &R1, const ArrayRecord &R2) {
40 return !(R1 == R2);
41}
42
43inline bool operator==(const CVType &R1, const CVType &R2) {
44 if (R1.RecordData != R2.RecordData)
45 return false;
46 return true;
47}
48inline bool operator!=(const CVType &R1, const CVType &R2) {
49 return !(R1 == R2);
50}
51}
52}
53
54namespace llvm {
55template <> struct BinaryItemTraits<CVType> {
56 static size_t length(const CVType &Item) { return Item.length(); }
57 static ArrayRef<uint8_t> bytes(const CVType &Item) { return Item.data(); }
58};
59}
60
61namespace {
62
63class MockCallbacks : public TypeVisitorCallbacks {
64public:
65 Error visitTypeBegin(CVType &CVR, TypeIndex Index) override {
66 Indices.push_back(x: Index);
67 return Error::success();
68 }
69 Error visitKnownRecord(CVType &CVR, ArrayRecord &AR) override {
70 VisitedRecords.push_back(x: AR);
71 RawRecords.push_back(x: CVR);
72 return Error::success();
73 }
74
75 uint32_t count() const {
76 assert(Indices.size() == RawRecords.size());
77 assert(Indices.size() == VisitedRecords.size());
78 return Indices.size();
79 }
80 std::vector<TypeIndex> Indices;
81 std::vector<CVType> RawRecords;
82 std::vector<ArrayRecord> VisitedRecords;
83};
84
85class RandomAccessVisitorTest : public testing::Test {
86public:
87 RandomAccessVisitorTest() {}
88
89 static void SetUpTestCase() {
90 GlobalState = std::make_unique<GlobalTestState>();
91
92 AppendingTypeTableBuilder Builder(GlobalState->Allocator);
93
94 uint32_t Offset = 0;
95 for (int I = 0; I < 11; ++I) {
96 ArrayRecord AR(TypeRecordKind::Array);
97 AR.ElementType = TypeIndex::Int32();
98 AR.IndexType = TypeIndex::UInt32();
99 AR.Size = I;
100 std::string Name;
101 raw_string_ostream Stream(Name);
102 Stream << "Array [" << I << "]";
103 AR.Name = GlobalState->Strings.save(S: Stream.str());
104 GlobalState->Records.push_back(x: AR);
105 GlobalState->Indices.push_back(x: Builder.writeLeafType(Record&: AR));
106
107 CVType Type(Builder.records().back());
108 GlobalState->TypeVector.push_back(x: Type);
109
110 GlobalState->AllOffsets.push_back(
111 x: {.Type: GlobalState->Indices.back(), .Offset: ulittle32_t(Offset)});
112 Offset += Type.length();
113 }
114
115 GlobalState->ItemStream.setItems(GlobalState->TypeVector);
116 GlobalState->TypeArray = VarStreamArray<CVType>(GlobalState->ItemStream);
117 }
118
119 static void TearDownTestCase() { GlobalState.reset(); }
120
121 void SetUp() override {
122 TestState = std::make_unique<PerTestState>();
123 }
124
125 void TearDown() override { TestState.reset(); }
126
127protected:
128 bool ValidateDatabaseRecord(LazyRandomTypeCollection &Types, uint32_t Index) {
129 TypeIndex TI = TypeIndex::fromArrayIndex(Index);
130 if (!Types.contains(Index: TI))
131 return false;
132 if (GlobalState->TypeVector[Index] != Types.getType(Index: TI))
133 return false;
134 return true;
135 }
136
137 bool ValidateVisitedRecord(uint32_t VisitationOrder,
138 uint32_t GlobalArrayIndex) {
139 TypeIndex TI = TypeIndex::fromArrayIndex(Index: GlobalArrayIndex);
140 if (TI != TestState->Callbacks.Indices[VisitationOrder])
141 return false;
142
143 if (GlobalState->TypeVector[TI.toArrayIndex()] !=
144 TestState->Callbacks.RawRecords[VisitationOrder])
145 return false;
146
147 if (GlobalState->Records[TI.toArrayIndex()] !=
148 TestState->Callbacks.VisitedRecords[VisitationOrder])
149 return false;
150
151 return true;
152 }
153
154 struct GlobalTestState {
155 GlobalTestState()
156 : Strings(Allocator), ItemStream(llvm::endianness::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>(Num: Size);
184 MutableArrayRef<uint8_t> Bytes(Buffer, Size);
185 Storage = MutableBinaryByteStream(Bytes, llvm::endianness::little);
186 BinaryStreamWriter Writer(Storage);
187 for (const auto I : Indices)
188 consumeError(Err: Writer.writeObject(Obj: GlobalState->AllOffsets[I]));
189
190 BinaryStreamReader Reader(Storage);
191 FixedStreamArray<TypeIndexOffset> Result;
192 consumeError(Err: Reader.readArray(Array&: Result, NumItems: Count));
193 return Result;
194 }
195
196 static std::unique_ptr<GlobalTestState> GlobalState;
197 std::unique_ptr<PerTestState> TestState;
198};
199
200std::unique_ptr<RandomAccessVisitorTest::GlobalTestState>
201 RandomAccessVisitorTest::GlobalState;
202}
203
204TEST_F(RandomAccessVisitorTest, MultipleVisits) {
205 TestState->Offsets = createPartialOffsets(Storage&: GlobalState->Stream, Indices: {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(Index: I);
214 CVType T = Types.getType(Index: 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 (const auto &I : enumerate(First&: IndicesToVisit))
227 EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
228}
229
230TEST_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(Storage&: GlobalState->Stream, Indices: {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(Index: I);
243 CVType T = Types.getType(Index: 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 (const auto &I : enumerate(First&: IndicesToVisit))
256 EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
257}
258
259TEST_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(Storage&: GlobalState->Stream, Indices: {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(Index: I);
272 CVType T = Types.getType(Index: 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 (const auto &I : enumerate(First&: IndicesToVisit))
285 EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
286}
287
288TEST_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(Storage&: GlobalState->Stream, Indices: {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(Index: I);
303 CVType T = Types.getType(Index: 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 (const auto &I : enumerate(First&: IndicesToVisit))
316 EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
317}
318
319TEST_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(Storage&: GlobalState->Stream, Indices: {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(Index: I);
333 CVType T = Types.getType(Index: 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 (const auto &I : enumerate(First&: IndicesToVisit))
346 EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value()));
347}
348
349TEST_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(Index: 0);
359 Class.FieldList = TypeIndex::fromArrayIndex(Index: 0);
360 Class.VTableShape = TypeIndex::fromArrayIndex(Index: 0);
361 TypeIndex IndexZero = Builder.writeLeafType(Record&: Class);
362
363 // TypeIndex 1 refers to type index 0.
364 ModifierRecord Modifier(TypeRecordKind::Modifier);
365 Modifier.ModifiedType = TypeIndex::fromArrayIndex(Index: 0);
366 Modifier.Modifiers = ModifierOptions::Const;
367 TypeIndex IndexOne = Builder.writeLeafType(Record&: 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::endianness::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(x: {.Type: IndexZero, .Offset: ulittle32_t(0u)});
386 TIO.push_back(x: {.Type: IndexOne, .Offset: 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::endianness::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(Index: IndexOne);
397 EXPECT_EQ("const FooClass", Name);
398}
399

source code of llvm/unittests/DebugInfo/CodeView/RandomAccessVisitorTest.cpp