LCOV - code coverage report
Current view: top level - lib/DebugInfo/CodeView - LazyRandomTypeCollection.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 114 128 89.1 %
Date: 2017-09-14 15:23:50 Functions: 19 22 86.4 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13