contrib/llvm/lib/DebugInfo/CodeView/LazyRandomTypeCollection.cpp

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