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