1//===- LazyRandomTypeCollection.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/LazyRandomTypeCollection.h"
10#include "llvm/ADT/ArrayRef.h"
11#include "llvm/ADT/STLExtras.h"
12#include "llvm/ADT/StringRef.h"
13#include "llvm/DebugInfo/CodeView/CodeViewError.h"
14#include "llvm/DebugInfo/CodeView/RecordName.h"
15#include "llvm/Support/BinaryStreamReader.h"
16#include "llvm/Support/Error.h"
17#include <algorithm>
18#include <cassert>
19#include <cstdint>
20#include <iterator>
21
22using namespace llvm;
23using namespace llvm::codeview;
24
25static void error(Error &&EC) {
26 assert(!static_cast<bool>(EC));
27 if (EC)
28 consumeError(Err: std::move(EC));
29}
30
31LazyRandomTypeCollection::LazyRandomTypeCollection(uint32_t RecordCountHint)
32 : LazyRandomTypeCollection(CVTypeArray(), RecordCountHint,
33 PartialOffsetArray()) {}
34
35LazyRandomTypeCollection::LazyRandomTypeCollection(
36 const CVTypeArray &Types, uint32_t RecordCountHint,
37 PartialOffsetArray PartialOffsets)
38 : NameStorage(Allocator), Types(Types), PartialOffsets(PartialOffsets) {
39 Records.resize(new_size: RecordCountHint);
40}
41
42LazyRandomTypeCollection::LazyRandomTypeCollection(ArrayRef<uint8_t> Data,
43 uint32_t RecordCountHint)
44 : LazyRandomTypeCollection(RecordCountHint) {
45}
46
47LazyRandomTypeCollection::LazyRandomTypeCollection(StringRef Data,
48 uint32_t RecordCountHint)
49 : LazyRandomTypeCollection(ArrayRef(Data.bytes_begin(), Data.bytes_end()),
50 RecordCountHint) {}
51
52LazyRandomTypeCollection::LazyRandomTypeCollection(const CVTypeArray &Types,
53 uint32_t NumRecords)
54 : LazyRandomTypeCollection(Types, NumRecords, PartialOffsetArray()) {}
55
56void LazyRandomTypeCollection::reset(BinaryStreamReader &Reader,
57 uint32_t RecordCountHint) {
58 Count = 0;
59 PartialOffsets = PartialOffsetArray();
60
61 error(EC: Reader.readArray(Array&: Types, Size: Reader.bytesRemaining()));
62
63 // Clear and then resize, to make sure existing data gets destroyed.
64 Records.clear();
65 Records.resize(new_size: RecordCountHint);
66}
67
68void LazyRandomTypeCollection::reset(StringRef Data, uint32_t RecordCountHint) {
69 BinaryStreamReader Reader(Data, llvm::endianness::little);
70 reset(Reader, RecordCountHint);
71}
72
73void LazyRandomTypeCollection::reset(ArrayRef<uint8_t> Data,
74 uint32_t RecordCountHint) {
75 BinaryStreamReader Reader(Data, llvm::endianness::little);
76 reset(Reader, RecordCountHint);
77}
78
79uint32_t LazyRandomTypeCollection::getOffsetOfType(TypeIndex Index) {
80 error(EC: ensureTypeExists(Index));
81 assert(contains(Index));
82
83 return Records[Index.toArrayIndex()].Offset;
84}
85
86CVType LazyRandomTypeCollection::getType(TypeIndex Index) {
87 assert(!Index.isSimple());
88
89 auto EC = ensureTypeExists(Index);
90 error(EC: std::move(EC));
91 assert(contains(Index));
92
93 return Records[Index.toArrayIndex()].Type;
94}
95
96std::optional<CVType> LazyRandomTypeCollection::tryGetType(TypeIndex Index) {
97 if (Index.isSimple())
98 return std::nullopt;
99
100 if (auto EC = ensureTypeExists(Index)) {
101 consumeError(Err: std::move(EC));
102 return std::nullopt;
103 }
104
105 assert(contains(Index));
106 return Records[Index.toArrayIndex()].Type;
107}
108
109StringRef LazyRandomTypeCollection::getTypeName(TypeIndex Index) {
110 if (Index.isNoneType() || Index.isSimple())
111 return TypeIndex::simpleTypeName(TI: Index);
112
113 // Try to make sure the type exists. Even if it doesn't though, it may be
114 // because we're dumping a symbol stream with no corresponding type stream
115 // present, in which case we still want to be able to print <unknown UDT>
116 // for the type names.
117 if (auto EC = ensureTypeExists(Index)) {
118 consumeError(Err: std::move(EC));
119 return "<unknown UDT>";
120 }
121
122 uint32_t I = Index.toArrayIndex();
123 ensureCapacityFor(Index);
124 if (Records[I].Name.data() == nullptr) {
125 StringRef Result = NameStorage.save(S: computeTypeName(Types&: *this, Index));
126 Records[I].Name = Result;
127 }
128 return Records[I].Name;
129}
130
131bool LazyRandomTypeCollection::contains(TypeIndex Index) {
132 if (Index.isSimple() || Index.isNoneType())
133 return false;
134
135 if (Records.size() <= Index.toArrayIndex())
136 return false;
137 if (!Records[Index.toArrayIndex()].Type.valid())
138 return false;
139 return true;
140}
141
142uint32_t LazyRandomTypeCollection::size() { return Count; }
143
144uint32_t LazyRandomTypeCollection::capacity() { return Records.size(); }
145
146Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
147 if (contains(Index: TI))
148 return Error::success();
149
150 return visitRangeForType(TI);
151}
152
153void LazyRandomTypeCollection::ensureCapacityFor(TypeIndex Index) {
154 assert(!Index.isSimple());
155 uint32_t MinSize = Index.toArrayIndex() + 1;
156
157 if (MinSize <= capacity())
158 return;
159
160 uint32_t NewCapacity = MinSize * 3 / 2;
161
162 assert(NewCapacity > capacity());
163 Records.resize(new_size: NewCapacity);
164}
165
166Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
167 assert(!TI.isSimple());
168 if (PartialOffsets.empty())
169 return fullScanForType(TI);
170
171 auto Next = llvm::upper_bound(Range&: PartialOffsets, Value&: TI,
172 C: [](TypeIndex Value, const TypeIndexOffset &IO) {
173 return Value < IO.Type;
174 });
175
176 assert(Next != PartialOffsets.begin());
177 auto Prev = std::prev(x: Next);
178
179 TypeIndex TIB = Prev->Type;
180 if (contains(Index: TIB)) {
181 // They've asked us to fetch a type index, but the entry we found in the
182 // partial offsets array has already been visited. Since we visit an entire
183 // block every time, that means this record should have been previously
184 // discovered. Ultimately, this means this is a request for a non-existent
185 // type index.
186 return make_error<CodeViewError>(Args: "Invalid type index");
187 }
188
189 TypeIndex TIE;
190 if (Next == PartialOffsets.end()) {
191 TIE = TypeIndex::fromArrayIndex(Index: capacity());
192 } else {
193 TIE = Next->Type;
194 }
195
196 visitRange(Begin: TIB, BeginOffset: Prev->Offset, End: TIE);
197 return Error::success();
198}
199
200std::optional<TypeIndex> LazyRandomTypeCollection::getFirst() {
201 TypeIndex TI = TypeIndex::fromArrayIndex(Index: 0);
202 if (auto EC = ensureTypeExists(TI)) {
203 consumeError(Err: std::move(EC));
204 return std::nullopt;
205 }
206 return TI;
207}
208
209std::optional<TypeIndex> LazyRandomTypeCollection::getNext(TypeIndex Prev) {
210 // We can't be sure how long this type stream is, given that the initial count
211 // given to the constructor is just a hint. So just try to make sure the next
212 // record exists, and if anything goes wrong, we must be at the end.
213 if (auto EC = ensureTypeExists(TI: Prev + 1)) {
214 consumeError(Err: std::move(EC));
215 return std::nullopt;
216 }
217
218 return Prev + 1;
219}
220
221Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
222 assert(!TI.isSimple());
223 assert(PartialOffsets.empty());
224
225 TypeIndex CurrentTI = TypeIndex::fromArrayIndex(Index: 0);
226 auto Begin = Types.begin();
227
228 if (Count > 0) {
229 // In the case of type streams which we don't know the number of records of,
230 // it's possible to search for a type index triggering a full scan, but then
231 // later additional records are added since we didn't know how many there
232 // would be until we did a full visitation, then you try to access the new
233 // type triggering another full scan. To avoid this, we assume that if the
234 // database has some records, this must be what's going on. We can also
235 // assume that this index must be larger than the largest type index we've
236 // visited, so we start from there and scan forward.
237 uint32_t Offset = Records[LargestTypeIndex.toArrayIndex()].Offset;
238 CurrentTI = LargestTypeIndex + 1;
239 Begin = Types.at(Offset);
240 ++Begin;
241 }
242
243 auto End = Types.end();
244 while (Begin != End) {
245 ensureCapacityFor(Index: CurrentTI);
246 LargestTypeIndex = std::max(a: LargestTypeIndex, b: CurrentTI);
247 auto Idx = CurrentTI.toArrayIndex();
248 Records[Idx].Type = *Begin;
249 Records[Idx].Offset = Begin.offset();
250 ++Count;
251 ++Begin;
252 ++CurrentTI;
253 }
254 if (CurrentTI <= TI) {
255 return make_error<CodeViewError>(Args: "Type Index does not exist!");
256 }
257 return Error::success();
258}
259
260void LazyRandomTypeCollection::visitRange(TypeIndex Begin, uint32_t BeginOffset,
261 TypeIndex End) {
262 auto RI = Types.at(Offset: BeginOffset);
263 assert(RI != Types.end());
264
265 ensureCapacityFor(Index: End);
266 while (Begin != End) {
267 LargestTypeIndex = std::max(a: LargestTypeIndex, b: Begin);
268 auto Idx = Begin.toArrayIndex();
269 Records[Idx].Type = *RI;
270 Records[Idx].Offset = RI.offset();
271 ++Count;
272 ++Begin;
273 ++RI;
274 }
275}
276
277bool LazyRandomTypeCollection::replaceType(TypeIndex &Index, CVType Data,
278 bool Stabilize) {
279 llvm_unreachable("Method cannot be called");
280}
281