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