llvm/lib/DebugInfo/CodeView/LazyRandomTypeCollection.cpp

   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
  22 using namespace llvm;
  23 using namespace llvm::codeview;
  24
  25 static void error(Error &&EC) {
  26   assert(!static_cast<bool>(EC));
  27   if (EC)
  28     consumeError(std::move(EC));
  29 }
  30
  31 LazyRandomTypeCollection::LazyRandomTypeCollection(uint32_t RecordCountHint)
  32     : LazyRandomTypeCollection(CVTypeArray(), RecordCountHint,
  33                                PartialOffsetArray()) {}
  34
  35 LazyRandomTypeCollection::LazyRandomTypeCollection(
  36     const CVTypeArray &Types, uint32_t RecordCountHint,
  37     PartialOffsetArray PartialOffsets)
  38     : NameStorage(Allocator), Types(Types), PartialOffsets(PartialOffsets) {
  39   Records.resize(RecordCountHint);
  40 }
  41
  42 LazyRandomTypeCollection::LazyRandomTypeCollection(ArrayRef<uint8_t> Data,
  43                                                    uint32_t RecordCountHint)
  44     : LazyRandomTypeCollection(RecordCountHint) {
  45 }
  46
  47 LazyRandomTypeCollection::LazyRandomTypeCollection(StringRef Data,
  48                                                    uint32_t RecordCountHint)
  49     : LazyRandomTypeCollection(ArrayRef(Data.bytes_begin(), Data.bytes_end()),
  50                                RecordCountHint) {}
  51
  52 LazyRandomTypeCollection::LazyRandomTypeCollection(const CVTypeArray &Types,
  53                                                    uint32_t NumRecords)
  54     : LazyRandomTypeCollection(Types, NumRecords, PartialOffsetArray()) {}
  55
  56 void LazyRandomTypeCollection::reset(BinaryStreamReader &Reader,
  57                                      uint32_t RecordCountHint) {
  58   Count = 0;
  59   PartialOffsets = PartialOffsetArray();
  60
  61   error(Reader.readArray(Types, Reader.bytesRemaining()));
  62
  63   // Clear and then resize, to make sure existing data gets destroyed.
  64   Records.clear();
  65   Records.resize(RecordCountHint);
  66 }
  67
  68 void LazyRandomTypeCollection::reset(StringRef Data, uint32_t RecordCountHint) {
  69   BinaryStreamReader Reader(Data, llvm::endianness::little);
  70   reset(Reader, RecordCountHint);
  71 }
  72
  73 void LazyRandomTypeCollection::reset(ArrayRef<uint8_t> Data,
  74                                      uint32_t RecordCountHint) {
  75   BinaryStreamReader Reader(Data, llvm::endianness::little);
  76   reset(Reader, RecordCountHint);
  77 }
  78
  79 uint32_t LazyRandomTypeCollection::getOffsetOfType(TypeIndex Index) {
  80   error(ensureTypeExists(Index));
  81   assert(contains(Index));
  82
  83   return Records[Index.toArrayIndex()].Offset;
  84 }
  85
  86 CVType LazyRandomTypeCollection::getType(TypeIndex Index) {
  87   assert(!Index.isSimple());
  88
  89   auto EC = ensureTypeExists(Index);
  90   error(std::move(EC));
  91   assert(contains(Index));
  92
  93   return Records[Index.toArrayIndex()].Type;
  94 }
  95
  96 std::optional<CVType> LazyRandomTypeCollection::tryGetType(TypeIndex Index) {
  97   if (Index.isSimple())
  98     return std::nullopt;
  99
 100   if (auto EC = ensureTypeExists(Index)) {
 101     consumeError(std::move(EC));
 102     return std::nullopt;
 103   }
 104
 105   assert(contains(Index));
 106   return Records[Index.toArrayIndex()].Type;
 107 }
 108
 109 StringRef LazyRandomTypeCollection::getTypeName(TypeIndex Index) {
 110   if (Index.isNoneType() || Index.isSimple())
 111     return TypeIndex::simpleTypeName(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(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(computeTypeName(*this, Index));
 126     Records[I].Name = Result;
 127   }
 128   return Records[I].Name;
 129 }
 130
 131 bool 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
 142 uint32_t LazyRandomTypeCollection::size() { return Count; }
 143
 144 uint32_t LazyRandomTypeCollection::capacity() { return Records.size(); }
 145
 146 Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
 147   if (contains(TI))
 148     return Error::success();
 149
 150   return visitRangeForType(TI);
 151 }
 152
 153 void 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(NewCapacity);
 164 }
 165
 166 Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
 167   assert(!TI.isSimple());
 168   if (PartialOffsets.empty())
 169     return fullScanForType(TI);
 170
 171   auto Next = llvm::upper_bound(PartialOffsets, TI,
 172                                 [](TypeIndex Value, const TypeIndexOffset &IO) {
 173                                   return Value < IO.Type;
 174                                 });
 175
 176   assert(Next != PartialOffsets.begin());
 177   auto Prev = std::prev(Next);
 178
 179   TypeIndex TIB = Prev->Type;
 180   if (contains(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>("Invalid type index");
 187   }
 188
 189   TypeIndex TIE;
 190   if (Next == PartialOffsets.end()) {
 191     TIE = TypeIndex::fromArrayIndex(capacity());
 192   } else {
 193     TIE = Next->Type;
 194   }
 195
 196   visitRange(TIB, Prev->Offset, TIE);
 197   return Error::success();
 198 }
 199
 200 std::optional<TypeIndex> LazyRandomTypeCollection::getFirst() {
 201   TypeIndex TI = TypeIndex::fromArrayIndex(0);
 202   if (auto EC = ensureTypeExists(TI)) {
 203     consumeError(std::move(EC));
 204     return std::nullopt;
 205   }
 206   return TI;
 207 }
 208
 209 std::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(Prev + 1)) {
 214     consumeError(std::move(EC));
 215     return std::nullopt;
 216   }
 217
 218   return Prev + 1;
 219 }
 220
 221 Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
 222   assert(!TI.isSimple());
 223   assert(PartialOffsets.empty());
 224
 225   TypeIndex CurrentTI = TypeIndex::fromArrayIndex(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(CurrentTI);
 246     LargestTypeIndex = std::max(LargestTypeIndex, 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>("Type Index does not exist!");
 256   }
 257   return Error::success();
 258 }
 259
 260 void LazyRandomTypeCollection::visitRange(TypeIndex Begin, uint32_t BeginOffset,
 261                                           TypeIndex End) {
 262   auto RI = Types.at(BeginOffset);
 263   assert(RI != Types.end());
 264
 265   ensureCapacityFor(End);
 266   while (Begin != End) {
 267     LargestTypeIndex = std::max(LargestTypeIndex, 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
 277 bool LazyRandomTypeCollection::replaceType(TypeIndex &Index, CVType Data,
 278                                            bool Stabilize) {
 279   llvm_unreachable("Method cannot be called");
 280 }