Home | History | Annotate | Download | only in CodeView 
      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/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"
     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(BinaryStreamReader &Reader,
     62                                      uint32_t RecordCountHint) {
     63   Count = 0;
     64   PartialOffsets = PartialOffsetArray();
     65 
     66   error(Reader.readArray(Types, Reader.bytesRemaining()));
     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(StringRef Data, uint32_t RecordCountHint) {
     74   BinaryStreamReader Reader(Data, support::little);
     75   reset(Reader, RecordCountHint);
     76 }
     77 
     78 void LazyRandomTypeCollection::reset(ArrayRef<uint8_t> Data,
     79                                      uint32_t RecordCountHint) {
     80   BinaryStreamReader Reader(Data, support::little);
     81   reset(Reader, RecordCountHint);
     82 }
     83 
     84 uint32_t LazyRandomTypeCollection::getOffsetOfType(TypeIndex Index) {
     85   error(ensureTypeExists(Index));
     86   assert(contains(Index));
     87 
     88   return Records[Index.toArrayIndex()].Offset;
     89 }
     90 
     91 CVType LazyRandomTypeCollection::getType(TypeIndex Index) {
     92   auto EC = ensureTypeExists(Index);
     93   error(std::move(EC));
     94   assert(contains(Index));
     95 
     96   return Records[Index.toArrayIndex()].Type;
     97 }
     98 
     99 Optional<CVType> LazyRandomTypeCollection::tryGetType(TypeIndex Index) {
    100   if (auto EC = ensureTypeExists(Index)) {
    101     consumeError(std::move(EC));
    102     return None;
    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   uint32_t MinSize = Index.toArrayIndex() + 1;
    155 
    156   if (MinSize <= capacity())
    157     return;
    158 
    159   uint32_t NewCapacity = MinSize * 3 / 2;
    160 
    161   assert(NewCapacity > capacity());
    162   Records.resize(NewCapacity);
    163 }
    164 
    165 Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
    166   if (PartialOffsets.empty())
    167     return fullScanForType(TI);
    168 
    169   auto Next = std::upper_bound(PartialOffsets.begin(), PartialOffsets.end(), TI,
    170                                [](TypeIndex Value, const TypeIndexOffset &IO) {
    171                                  return Value < IO.Type;
    172                                });
    173 
    174   assert(Next != PartialOffsets.begin());
    175   auto Prev = std::prev(Next);
    176 
    177   TypeIndex TIB = Prev->Type;
    178   if (contains(TIB)) {
    179     // They've asked us to fetch a type index, but the entry we found in the
    180     // partial offsets array has already been visited.  Since we visit an entire
    181     // block every time, that means this record should have been previously
    182     // discovered.  Ultimately, this means this is a request for a non-existant
    183     // type index.
    184     return make_error<CodeViewError>("Invalid type index");
    185   }
    186 
    187   TypeIndex TIE;
    188   if (Next == PartialOffsets.end()) {
    189     TIE = TypeIndex::fromArrayIndex(capacity());
    190   } else {
    191     TIE = Next->Type;
    192   }
    193 
    194   visitRange(TIB, Prev->Offset, TIE);
    195   return Error::success();
    196 }
    197 
    198 Optional<TypeIndex> LazyRandomTypeCollection::getFirst() {
    199   TypeIndex TI = TypeIndex::fromArrayIndex(0);
    200   if (auto EC = ensureTypeExists(TI)) {
    201     consumeError(std::move(EC));
    202     return None;
    203   }
    204   return TI;
    205 }
    206 
    207 Optional<TypeIndex> LazyRandomTypeCollection::getNext(TypeIndex Prev) {
    208   // We can't be sure how long this type stream is, given that the initial count
    209   // given to the constructor is just a hint.  So just try to make sure the next
    210   // record exists, and if anything goes wrong, we must be at the end.
    211   if (auto EC = ensureTypeExists(Prev + 1)) {
    212     consumeError(std::move(EC));
    213     return None;
    214   }
    215 
    216   return Prev + 1;
    217 }
    218 
    219 Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
    220   assert(PartialOffsets.empty());
    221 
    222   TypeIndex CurrentTI = TypeIndex::fromArrayIndex(0);
    223   auto Begin = Types.begin();
    224 
    225   if (Count > 0) {
    226     // In the case of type streams which we don't know the number of records of,
    227     // it's possible to search for a type index triggering a full scan, but then
    228     // later additional records are added since we didn't know how many there
    229     // would be until we did a full visitation, then you try to access the new
    230     // type triggering another full scan.  To avoid this, we assume that if the
    231     // database has some records, this must be what's going on.  We can also
    232     // assume that this index must be larger than the largest type index we've
    233     // visited, so we start from there and scan forward.
    234     uint32_t Offset = Records[LargestTypeIndex.toArrayIndex()].Offset;
    235     CurrentTI = LargestTypeIndex + 1;
    236     Begin = Types.at(Offset);
    237     ++Begin;
    238   }
    239 
    240   auto End = Types.end();
    241   while (Begin != End) {
    242     ensureCapacityFor(CurrentTI);
    243     LargestTypeIndex = std::max(LargestTypeIndex, CurrentTI);
    244     auto Idx = CurrentTI.toArrayIndex();
    245     Records[Idx].Type = *Begin;
    246     Records[Idx].Offset = Begin.offset();
    247     ++Count;
    248     ++Begin;
    249     ++CurrentTI;
    250   }
    251   if (CurrentTI <= TI) {
    252     return make_error<CodeViewError>("Type Index does not exist!");
    253   }
    254   return Error::success();
    255 }
    256 
    257 void LazyRandomTypeCollection::visitRange(TypeIndex Begin, uint32_t BeginOffset,
    258                                           TypeIndex End) {
    259   auto RI = Types.at(BeginOffset);
    260   assert(RI != Types.end());
    261 
    262   ensureCapacityFor(End);
    263   while (Begin != End) {
    264     LargestTypeIndex = std::max(LargestTypeIndex, Begin);
    265     auto Idx = Begin.toArrayIndex();
    266     Records[Idx].Type = *RI;
    267     Records[Idx].Offset = RI.offset();
    268     ++Count;
    269     ++Begin;
    270     ++RI;
    271   }
    272 }
    273