Debian Codegraph @

llvm-project/llvm/unittests/DebugInfo/CodeView/RandomAccessVisitorTest.cpp

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