1 //===- LazyRandomTypeCollection.cpp ---------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/None.h"
13 #include "llvm/ADT/StringExtras.h"
14 #include "llvm/ADT/StringRef.h"
15 #include "llvm/DebugInfo/CodeView/CodeViewError.h"
16 #include "llvm/DebugInfo/CodeView/RecordName.h"
17 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
18 #include "llvm/Support/BinaryStreamReader.h"
19 #include "llvm/Support/Endian.h"
20 #include "llvm/Support/Error.h"
27 using namespace llvm::codeview;
29 static void error(Error &&EC) {
30 assert(!static_cast<bool>(EC));
32 consumeError(std::move(EC));
35 LazyRandomTypeCollection::LazyRandomTypeCollection(uint32_t RecordCountHint)
36 : LazyRandomTypeCollection(CVTypeArray(), RecordCountHint,
37 PartialOffsetArray()) {}
39 LazyRandomTypeCollection::LazyRandomTypeCollection(
40 const CVTypeArray &Types, uint32_t RecordCountHint,
41 PartialOffsetArray PartialOffsets)
42 : NameStorage(Allocator), Types(Types), PartialOffsets(PartialOffsets) {
43 Records.resize(RecordCountHint);
46 LazyRandomTypeCollection::LazyRandomTypeCollection(ArrayRef<uint8_t> Data,
47 uint32_t RecordCountHint)
48 : LazyRandomTypeCollection(RecordCountHint) {
51 LazyRandomTypeCollection::LazyRandomTypeCollection(StringRef Data,
52 uint32_t RecordCountHint)
53 : LazyRandomTypeCollection(
54 makeArrayRef(Data.bytes_begin(), Data.bytes_end()), RecordCountHint) {
57 LazyRandomTypeCollection::LazyRandomTypeCollection(const CVTypeArray &Types,
59 : LazyRandomTypeCollection(Types, NumRecords, PartialOffsetArray()) {}
61 void LazyRandomTypeCollection::reset(BinaryStreamReader &Reader,
62 uint32_t RecordCountHint) {
64 PartialOffsets = PartialOffsetArray();
66 error(Reader.readArray(Types, Reader.bytesRemaining()));
68 // Clear and then resize, to make sure existing data gets destroyed.
70 Records.resize(RecordCountHint);
73 void LazyRandomTypeCollection::reset(StringRef Data, uint32_t RecordCountHint) {
74 BinaryStreamReader Reader(Data, support::little);
75 reset(Reader, RecordCountHint);
78 void LazyRandomTypeCollection::reset(ArrayRef<uint8_t> Data,
79 uint32_t RecordCountHint) {
80 BinaryStreamReader Reader(Data, support::little);
81 reset(Reader, RecordCountHint);
84 uint32_t LazyRandomTypeCollection::getOffsetOfType(TypeIndex Index) {
85 error(ensureTypeExists(Index));
86 assert(contains(Index));
88 return Records[Index.toArrayIndex()].Offset;
91 CVType LazyRandomTypeCollection::getType(TypeIndex Index) {
92 assert(!Index.isSimple());
94 auto EC = ensureTypeExists(Index);
96 assert(contains(Index));
98 return Records[Index.toArrayIndex()].Type;
101 Optional<CVType> LazyRandomTypeCollection::tryGetType(TypeIndex Index) {
102 if (Index.isSimple())
105 if (auto EC = ensureTypeExists(Index)) {
106 consumeError(std::move(EC));
110 assert(contains(Index));
111 return Records[Index.toArrayIndex()].Type;
114 StringRef LazyRandomTypeCollection::getTypeName(TypeIndex Index) {
115 if (Index.isNoneType() || Index.isSimple())
116 return TypeIndex::simpleTypeName(Index);
118 // Try to make sure the type exists. Even if it doesn't though, it may be
119 // because we're dumping a symbol stream with no corresponding type stream
120 // present, in which case we still want to be able to print <unknown UDT>
121 // for the type names.
122 if (auto EC = ensureTypeExists(Index)) {
123 consumeError(std::move(EC));
124 return "<unknown UDT>";
127 uint32_t I = Index.toArrayIndex();
128 ensureCapacityFor(Index);
129 if (Records[I].Name.data() == nullptr) {
130 StringRef Result = NameStorage.save(computeTypeName(*this, Index));
131 Records[I].Name = Result;
133 return Records[I].Name;
136 bool LazyRandomTypeCollection::contains(TypeIndex Index) {
137 if (Index.isSimple() || Index.isNoneType())
140 if (Records.size() <= Index.toArrayIndex())
142 if (!Records[Index.toArrayIndex()].Type.valid())
147 uint32_t LazyRandomTypeCollection::size() { return Count; }
149 uint32_t LazyRandomTypeCollection::capacity() { return Records.size(); }
151 Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
153 return Error::success();
155 return visitRangeForType(TI);
158 void LazyRandomTypeCollection::ensureCapacityFor(TypeIndex Index) {
159 assert(!Index.isSimple());
160 uint32_t MinSize = Index.toArrayIndex() + 1;
162 if (MinSize <= capacity())
165 uint32_t NewCapacity = MinSize * 3 / 2;
167 assert(NewCapacity > capacity());
168 Records.resize(NewCapacity);
171 Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
172 assert(!TI.isSimple());
173 if (PartialOffsets.empty())
174 return fullScanForType(TI);
176 auto Next = std::upper_bound(PartialOffsets.begin(), PartialOffsets.end(), TI,
177 [](TypeIndex Value, const TypeIndexOffset &IO) {
178 return Value < IO.Type;
181 assert(Next != PartialOffsets.begin());
182 auto Prev = std::prev(Next);
184 TypeIndex TIB = Prev->Type;
186 // They've asked us to fetch a type index, but the entry we found in the
187 // partial offsets array has already been visited. Since we visit an entire
188 // block every time, that means this record should have been previously
189 // discovered. Ultimately, this means this is a request for a non-existant
191 return make_error<CodeViewError>("Invalid type index");
195 if (Next == PartialOffsets.end()) {
196 TIE = TypeIndex::fromArrayIndex(capacity());
201 visitRange(TIB, Prev->Offset, TIE);
202 return Error::success();
205 Optional<TypeIndex> LazyRandomTypeCollection::getFirst() {
206 TypeIndex TI = TypeIndex::fromArrayIndex(0);
207 if (auto EC = ensureTypeExists(TI)) {
208 consumeError(std::move(EC));
214 Optional<TypeIndex> LazyRandomTypeCollection::getNext(TypeIndex Prev) {
215 // We can't be sure how long this type stream is, given that the initial count
216 // given to the constructor is just a hint. So just try to make sure the next
217 // record exists, and if anything goes wrong, we must be at the end.
218 if (auto EC = ensureTypeExists(Prev + 1)) {
219 consumeError(std::move(EC));
226 Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
227 assert(!TI.isSimple());
228 assert(PartialOffsets.empty());
230 TypeIndex CurrentTI = TypeIndex::fromArrayIndex(0);
231 auto Begin = Types.begin();
234 // In the case of type streams which we don't know the number of records of,
235 // it's possible to search for a type index triggering a full scan, but then
236 // later additional records are added since we didn't know how many there
237 // would be until we did a full visitation, then you try to access the new
238 // type triggering another full scan. To avoid this, we assume that if the
239 // database has some records, this must be what's going on. We can also
240 // assume that this index must be larger than the largest type index we've
241 // visited, so we start from there and scan forward.
242 uint32_t Offset = Records[LargestTypeIndex.toArrayIndex()].Offset;
243 CurrentTI = LargestTypeIndex + 1;
244 Begin = Types.at(Offset);
248 auto End = Types.end();
249 while (Begin != End) {
250 ensureCapacityFor(CurrentTI);
251 LargestTypeIndex = std::max(LargestTypeIndex, CurrentTI);
252 auto Idx = CurrentTI.toArrayIndex();
253 Records[Idx].Type = *Begin;
254 Records[Idx].Offset = Begin.offset();
259 if (CurrentTI <= TI) {
260 return make_error<CodeViewError>("Type Index does not exist!");
262 return Error::success();
265 void LazyRandomTypeCollection::visitRange(TypeIndex Begin, uint32_t BeginOffset,
267 auto RI = Types.at(BeginOffset);
268 assert(RI != Types.end());
270 ensureCapacityFor(End);
271 while (Begin != End) {
272 LargestTypeIndex = std::max(LargestTypeIndex, Begin);
273 auto Idx = Begin.toArrayIndex();
274 Records[Idx].Type = *RI;
275 Records[Idx].Offset = RI.offset();