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 if (EC) {
91 assert(false && "Invalid type index (use tryGetType or getTypeOrError)");
92 llvm::consumeError(Err: std::move(EC));
93 return {};
94 }
95 assert(contains(Index));
96
97 return Records[Index.toArrayIndex()].Type;
98}
99
100llvm::Expected<CVType>
101LazyRandomTypeCollection::getTypeOrError(TypeIndex Index) {
102 if (Index.isSimple())
103 return llvm::createStringError(Fmt: "Type index too low (%d)", Vals: Index.getIndex());
104
105 if (auto EC = ensureTypeExists(Index))
106 return EC;
107
108 if (!contains(Index))
109 return llvm::createStringError(Fmt: "Type index too high (%d)",
110 Vals: Index.getIndex());
111 return Records[Index.toArrayIndex()].Type;
112}
113
114std::optional<CVType> LazyRandomTypeCollection::tryGetType(TypeIndex Index) {
115 return llvm::expectedToOptional(E: getTypeOrError(Index));
116}
117
118StringRef LazyRandomTypeCollection::getTypeName(TypeIndex Index) {
119 if (Index.isNoneType() || Index.isSimple())
120 return TypeIndex::simpleTypeName(TI: Index);
121
122 // Try to make sure the type exists. Even if it doesn't though, it may be
123 // because we're dumping a symbol stream with no corresponding type stream
124 // present, in which case we still want to be able to print <unknown UDT>
125 // for the type names.
126 if (auto EC = ensureTypeExists(Index)) {
127 consumeError(Err: std::move(EC));
128 return "<unknown UDT>";
129 }
130
131 uint32_t I = Index.toArrayIndex();
132 ensureCapacityFor(Index);
133 if (Records[I].Name.data() == nullptr) {
134 StringRef Result = NameStorage.save(S: computeTypeName(Types&: *this, Index));
135 Records[I].Name = Result;
136 }
137 return Records[I].Name;
138}
139
140bool LazyRandomTypeCollection::contains(TypeIndex Index) {
141 if (Index.isSimple() || Index.isNoneType())
142 return false;
143
144 if (Records.size() <= Index.toArrayIndex())
145 return false;
146 if (!Records[Index.toArrayIndex()].Type.valid())
147 return false;
148 return true;
149}
150
151uint32_t LazyRandomTypeCollection::size() { return Count; }
152
153uint32_t LazyRandomTypeCollection::capacity() { return Records.size(); }
154
155Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
156 if (contains(Index: TI))
157 return Error::success();
158
159 return visitRangeForType(TI);
160}
161
162void LazyRandomTypeCollection::ensureCapacityFor(TypeIndex Index) {
163 assert(!Index.isSimple());
164 uint32_t MinSize = Index.toArrayIndex() + 1;
165
166 if (MinSize <= capacity())
167 return;
168
169 uint32_t NewCapacity = MinSize * 3 / 2;
170
171 assert(NewCapacity > capacity());
172 Records.resize(new_size: NewCapacity);
173}
174
175Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
176 assert(!TI.isSimple());
177 if (PartialOffsets.empty())
178 return fullScanForType(TI);
179
180 auto Next = llvm::upper_bound(Range&: PartialOffsets, Value&: TI,
181 C: [](TypeIndex Value, const TypeIndexOffset &IO) {
182 return Value < IO.Type;
183 });
184
185 assert(Next != PartialOffsets.begin());
186 auto Prev = std::prev(x: Next);
187
188 TypeIndex TIB = Prev->Type;
189 if (contains(Index: TIB)) {
190 // They've asked us to fetch a type index, but the entry we found in the
191 // partial offsets array has already been visited. Since we visit an entire
192 // block every time, that means this record should have been previously
193 // discovered. Ultimately, this means this is a request for a non-existent
194 // type index.
195 return make_error<CodeViewError>(Args: "Invalid type index");
196 }
197
198 TypeIndex TIE;
199 if (Next == PartialOffsets.end()) {
200 TIE = TypeIndex::fromArrayIndex(Index: capacity());
201 } else {
202 TIE = Next->Type;
203 }
204
205 visitRange(Begin: TIB, BeginOffset: Prev->Offset, End: TIE);
206 return Error::success();
207}
208
209std::optional<TypeIndex> LazyRandomTypeCollection::getFirst() {
210 TypeIndex TI = TypeIndex::fromArrayIndex(Index: 0);
211 if (auto EC = ensureTypeExists(TI)) {
212 consumeError(Err: std::move(EC));
213 return std::nullopt;
214 }
215 return TI;
216}
217
218std::optional<TypeIndex> LazyRandomTypeCollection::getNext(TypeIndex Prev) {
219 // We can't be sure how long this type stream is, given that the initial count
220 // given to the constructor is just a hint. So just try to make sure the next
221 // record exists, and if anything goes wrong, we must be at the end.
222 if (auto EC = ensureTypeExists(TI: Prev + 1)) {
223 consumeError(Err: std::move(EC));
224 return std::nullopt;
225 }
226
227 return Prev + 1;
228}
229
230Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
231 assert(!TI.isSimple());
232 assert(PartialOffsets.empty());
233
234 TypeIndex CurrentTI = TypeIndex::fromArrayIndex(Index: 0);
235 auto Begin = Types.begin();
236
237 if (Count > 0) {
238 // In the case of type streams which we don't know the number of records of,
239 // it's possible to search for a type index triggering a full scan, but then
240 // later additional records are added since we didn't know how many there
241 // would be until we did a full visitation, then you try to access the new
242 // type triggering another full scan. To avoid this, we assume that if the
243 // database has some records, this must be what's going on. We can also
244 // assume that this index must be larger than the largest type index we've
245 // visited, so we start from there and scan forward.
246 uint32_t Offset = Records[LargestTypeIndex.toArrayIndex()].Offset;
247 CurrentTI = LargestTypeIndex + 1;
248 Begin = Types.at(Offset);
249 ++Begin;
250 }
251
252 auto End = Types.end();
253 while (Begin != End) {
254 ensureCapacityFor(Index: CurrentTI);
255 LargestTypeIndex = std::max(a: LargestTypeIndex, b: CurrentTI);
256 auto Idx = CurrentTI.toArrayIndex();
257 Records[Idx].Type = *Begin;
258 Records[Idx].Offset = Begin.offset();
259 ++Count;
260 ++Begin;
261 ++CurrentTI;
262 }
263 if (CurrentTI <= TI) {
264 return make_error<CodeViewError>(Args: "Type Index does not exist!");
265 }
266 return Error::success();
267}
268
269void LazyRandomTypeCollection::visitRange(TypeIndex Begin, uint32_t BeginOffset,
270 TypeIndex End) {
271 auto RI = Types.at(Offset: BeginOffset);
272 assert(RI != Types.end());
273
274 ensureCapacityFor(Index: End);
275 while (Begin != End) {
276 LargestTypeIndex = std::max(a: LargestTypeIndex, b: Begin);
277 auto Idx = Begin.toArrayIndex();
278 Records[Idx].Type = *RI;
279 Records[Idx].Offset = RI.offset();
280 ++Count;
281 ++Begin;
282 ++RI;
283 }
284}
285
286bool LazyRandomTypeCollection::replaceType(TypeIndex &Index, CVType Data,
287 bool Stabilize) {
288 llvm_unreachable("Method cannot be called");
289}
290