contrib/llvm/include/llvm/DebugInfo/MSF/StreamArray.h

   1 //===- StreamArray.h - Array backed by an arbitrary stream ------*- C++ -*-===//
   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 #ifndef LLVM_DEBUGINFO_MSF_STREAMARRAY_H
  11 #define LLVM_DEBUGINFO_MSF_STREAMARRAY_H
  12
  13 #include "llvm/ADT/ArrayRef.h"
  14 #include "llvm/ADT/iterator.h"
  15 #include "llvm/DebugInfo/MSF/StreamRef.h"
  16 #include "llvm/Support/Error.h"
  17 #include <cassert>
  18 #include <cstdint>
  19
  20 namespace llvm {
  21 namespace msf {
  22
  23 /// VarStreamArrayExtractor is intended to be specialized to provide customized
  24 /// extraction logic.  On input it receives a StreamRef pointing to the
  25 /// beginning of the next record, but where the length of the record is not yet
  26 /// known.  Upon completion, it should return an appropriate Error instance if
  27 /// a record could not be extracted, or if one could be extracted it should
  28 /// return success and set Len to the number of bytes this record occupied in
  29 /// the underlying stream, and it should fill out the fields of the value type
  30 /// Item appropriately to represent the current record.
  31 ///
  32 /// You can specialize this template for your own custom value types to avoid
  33 /// having to specify a second template argument to VarStreamArray (documented
  34 /// below).
  35 template <typename T> struct VarStreamArrayExtractor {
  36   // Method intentionally deleted.  You must provide an explicit specialization
  37   // with the following method implemented.
  38   Error operator()(ReadableStreamRef Stream, uint32_t &Len,
  39                    T &Item) const = delete;
  40 };
  41
  42 /// VarStreamArray represents an array of variable length records backed by a
  43 /// stream.  This could be a contiguous sequence of bytes in memory, it could
  44 /// be a file on disk, or it could be a PDB stream where bytes are stored as
  45 /// discontiguous blocks in a file.  Usually it is desirable to treat arrays
  46 /// as contiguous blocks of memory, but doing so with large PDB files, for
  47 /// example, could mean allocating huge amounts of memory just to allow
  48 /// re-ordering of stream data to be contiguous before iterating over it.  By
  49 /// abstracting this out, we need not duplicate this memory, and we can
  50 /// iterate over arrays in arbitrarily formatted streams.  Elements are parsed
  51 /// lazily on iteration, so there is no upfront cost associated with building
  52 /// a VarStreamArray, no matter how large it may be.
  53 ///
  54 /// You create a VarStreamArray by specifying a ValueType and an Extractor type.
  55 /// If you do not specify an Extractor type, it expects you to specialize
  56 /// VarStreamArrayExtractor<T> for your ValueType.
  57 ///
  58 /// By default an Extractor is default constructed in the class, but in some
  59 /// cases you might find it useful for an Extractor to maintain state across
  60 /// extractions.  In this case you can provide your own Extractor through a
  61 /// secondary constructor.  The following examples show various ways of
  62 /// creating a VarStreamArray.
  63 ///
  64 ///       // Will use VarStreamArrayExtractor<MyType> as the extractor.
  65 ///       VarStreamArray<MyType> MyTypeArray;
  66 ///
  67 ///       // Will use a default-constructed MyExtractor as the extractor.
  68 ///       VarStreamArray<MyType, MyExtractor> MyTypeArray2;
  69 ///
  70 ///       // Will use the specific instance of MyExtractor provided.
  71 ///       // MyExtractor need not be default-constructible in this case.
  72 ///       MyExtractor E(SomeContext);
  73 ///       VarStreamArray<MyType, MyExtractor> MyTypeArray3(E);
  74 ///
  75 template <typename ValueType, typename Extractor> class VarStreamArrayIterator;
  76
  77 template <typename ValueType,
  78           typename Extractor = VarStreamArrayExtractor<ValueType>>
  79
  80 class VarStreamArray {
  81   friend class VarStreamArrayIterator<ValueType, Extractor>;
  82
  83 public:
  84   typedef VarStreamArrayIterator<ValueType, Extractor> Iterator;
  85
  86   VarStreamArray() = default;
  87   explicit VarStreamArray(const Extractor &E) : E(E) {}
  88
  89   explicit VarStreamArray(ReadableStreamRef Stream) : Stream(Stream) {}
  90   VarStreamArray(ReadableStreamRef Stream, const Extractor &E)
  91       : Stream(Stream), E(E) {}
  92
  93   VarStreamArray(const VarStreamArray<ValueType, Extractor> &Other)
  94       : Stream(Other.Stream), E(Other.E) {}
  95
  96   Iterator begin(bool *HadError = nullptr) const {
  97     return Iterator(*this, E, HadError);
  98   }
  99
 100   Iterator end() const { return Iterator(E); }
 101
 102   const Extractor &getExtractor() const { return E; }
 103
 104   ReadableStreamRef getUnderlyingStream() const { return Stream; }
 105
 106 private:
 107   ReadableStreamRef Stream;
 108   Extractor E;
 109 };
 110
 111 template <typename ValueType, typename Extractor>
 112 class VarStreamArrayIterator
 113     : public iterator_facade_base<VarStreamArrayIterator<ValueType, Extractor>,
 114                                   std::forward_iterator_tag, ValueType> {
 115   typedef VarStreamArrayIterator<ValueType, Extractor> IterType;
 116   typedef VarStreamArray<ValueType, Extractor> ArrayType;
 117
 118 public:
 119   VarStreamArrayIterator(const ArrayType &Array, const Extractor &E,
 120                          bool *HadError = nullptr)
 121       : IterRef(Array.Stream), Array(&Array), HadError(HadError), Extract(E) {
 122     if (IterRef.getLength() == 0)
 123       moveToEnd();
 124     else {
 125       auto EC = Extract(IterRef, ThisLen, ThisValue);
 126       if (EC) {
 127         consumeError(std::move(EC));
 128         markError();
 129       }
 130     }
 131   }
 132   VarStreamArrayIterator() = default;
 133   explicit VarStreamArrayIterator(const Extractor &E) : Extract(E) {}
 134   ~VarStreamArrayIterator() = default;
 135
 136   bool operator==(const IterType &R) const {
 137     if (Array && R.Array) {
 138       // Both have a valid array, make sure they're same.
 139       assert(Array == R.Array);
 140       return IterRef == R.IterRef;
 141     }
 142
 143     // Both iterators are at the end.
 144     if (!Array && !R.Array)
 145       return true;
 146
 147     // One is not at the end and one is.
 148     return false;
 149   }
 150
 151   const ValueType &operator*() const {
 152     assert(Array && !HasError);
 153     return ThisValue;
 154   }
 155
 156   IterType &operator+=(std::ptrdiff_t N) {
 157     while (N > 0) {
 158       // We are done with the current record, discard it so that we are
 159       // positioned at the next record.
 160       IterRef = IterRef.drop_front(ThisLen);
 161       if (IterRef.getLength() == 0) {
 162         // There is nothing after the current record, we must make this an end
 163         // iterator.
 164         moveToEnd();
 165         return *this;
 166       } else {
 167         // There is some data after the current record.
 168         auto EC = Extract(IterRef, ThisLen, ThisValue);
 169         if (EC) {
 170           consumeError(std::move(EC));
 171           markError();
 172           return *this;
 173         } else if (ThisLen == 0) {
 174           // An empty record? Make this an end iterator.
 175           moveToEnd();
 176           return *this;
 177         }
 178       }
 179       --N;
 180     }
 181     return *this;
 182   }
 183
 184 private:
 185   void moveToEnd() {
 186     Array = nullptr;
 187     ThisLen = 0;
 188   }
 189   void markError() {
 190     moveToEnd();
 191     HasError = true;
 192     if (HadError != nullptr)
 193       *HadError = true;
 194   }
 195
 196   ValueType ThisValue;
 197   ReadableStreamRef IterRef;
 198   const ArrayType *Array{nullptr};
 199   uint32_t ThisLen{0};
 200   bool HasError{false};
 201   bool *HadError{nullptr};
 202   Extractor Extract;
 203 };
 204
 205 template <typename T> class FixedStreamArrayIterator;
 206
 207 template <typename T> class FixedStreamArray {
 208   friend class FixedStreamArrayIterator<T>;
 209
 210 public:
 211   FixedStreamArray() = default;
 212   FixedStreamArray(ReadableStreamRef Stream) : Stream(Stream) {
 213     assert(Stream.getLength() % sizeof(T) == 0);
 214   }
 215
 216   bool operator==(const FixedStreamArray<T> &Other) const {
 217     return Stream == Other.Stream;
 218   }
 219
 220   bool operator!=(const FixedStreamArray<T> &Other) const {
 221     return !(*this == Other);
 222   }
 223
 224   FixedStreamArray &operator=(const FixedStreamArray &) = default;
 225
 226   const T &operator[](uint32_t Index) const {
 227     assert(Index < size());
 228     uint32_t Off = Index * sizeof(T);
 229     ArrayRef<uint8_t> Data;
 230     if (auto EC = Stream.readBytes(Off, sizeof(T), Data)) {
 231       assert(false && "Unexpected failure reading from stream");
 232       // This should never happen since we asserted that the stream length was
 233       // an exact multiple of the element size.
 234       consumeError(std::move(EC));
 235     }
 236     return *reinterpret_cast<const T *>(Data.data());
 237   }
 238
 239   uint32_t size() const { return Stream.getLength() / sizeof(T); }
 240
 241   bool empty() const { return size() == 0; }
 242
 243   FixedStreamArrayIterator<T> begin() const {
 244     return FixedStreamArrayIterator<T>(*this, 0);
 245   }
 246
 247   FixedStreamArrayIterator<T> end() const {
 248     return FixedStreamArrayIterator<T>(*this, size());
 249   }
 250
 251   ReadableStreamRef getUnderlyingStream() const { return Stream; }
 252
 253 private:
 254   ReadableStreamRef Stream;
 255 };
 256
 257 template <typename T>
 258 class FixedStreamArrayIterator
 259     : public iterator_facade_base<FixedStreamArrayIterator<T>,
 260                                   std::random_access_iterator_tag, T> {
 261
 262 public:
 263   FixedStreamArrayIterator(const FixedStreamArray<T> &Array, uint32_t Index)
 264       : Array(Array), Index(Index) {}
 265
 266   FixedStreamArrayIterator<T> &
 267   operator=(const FixedStreamArrayIterator<T> &Other) {
 268     Array = Other.Array;
 269     Index = Other.Index;
 270     return *this;
 271   }
 272
 273   const T &operator*() const { return Array[Index]; }
 274
 275   bool operator==(const FixedStreamArrayIterator<T> &R) const {
 276     assert(Array == R.Array);
 277     return (Index == R.Index) && (Array == R.Array);
 278   }
 279
 280   FixedStreamArrayIterator<T> &operator+=(std::ptrdiff_t N) {
 281     Index += N;
 282     return *this;
 283   }
 284
 285   FixedStreamArrayIterator<T> &operator-=(std::ptrdiff_t N) {
 286     assert(Index >= N);
 287     Index -= N;
 288     return *this;
 289   }
 290
 291   std::ptrdiff_t operator-(const FixedStreamArrayIterator<T> &R) const {
 292     assert(Array == R.Array);
 293     assert(Index >= R.Index);
 294     return Index - R.Index;
 295   }
 296
 297   bool operator<(const FixedStreamArrayIterator<T> &RHS) const {
 298     assert(Array == RHS.Array);
 299     return Index < RHS.Index;
 300   }
 301
 302 private:
 303   FixedStreamArray<T> Array;
 304   uint32_t Index;
 305 };
 306
 307 } // namespace msf
 308 } // namespace llvm
 309
 310 #endif // LLVM_DEBUGINFO_MSF_STREAMARRAY_H