Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- BinaryStreamArray.h - Array backed by an arbitrary stream *- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

///

/// \file

/// Lightweight arrays that are backed by an arbitrary BinaryStream.  This file

/// provides two different array implementations.

///

///     VarStreamArray - Arrays of variable length records.  The user specifies

///       an Extractor type that can extract a record from a given offset and

///       return the number of bytes consumed by the record.

///

///     FixedStreamArray - Arrays of fixed length records.  This is similar in

///       spirit to ArrayRef<T>, but since it is backed by a BinaryStream, the

///       elements of the array need not be laid out in contiguous memory.

///

#ifndef LLVM_SUPPORT_BINARYSTREAMARRAY_H

#define LLVM_SUPPORT_BINARYSTREAMARRAY_H

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/iterator.h"

#include "llvm/Support/Alignment.h"

#include "llvm/Support/BinaryStreamRef.h"

#include "llvm/Support/Error.h"

#include <cassert>

#include <cstdint>

namespace llvm {

/// VarStreamArrayExtractor is intended to be specialized to provide customized

/// extraction logic.  On input it receives a BinaryStreamRef pointing to the

/// beginning of the next record, but where the length of the record is not yet

/// known.  Upon completion, it should return an appropriate Error instance if

/// a record could not be extracted, or if one could be extracted it should

/// return success and set Len to the number of bytes this record occupied in

/// the underlying stream, and it should fill out the fields of the value type

/// Item appropriately to represent the current record.

///

/// You can specialize this template for your own custom value types to avoid

/// having to specify a second template argument to VarStreamArray (documented

/// below).

template <typename T> struct VarStreamArrayExtractor {

  // Method intentionally deleted.  You must provide an explicit specialization

  // with the following method implemented.

  Error operator()(BinaryStreamRef Stream, uint32_t &Len,

                   T &Item) const = delete;

};

/// VarStreamArray represents an array of variable length records backed by a

/// stream.  This could be a contiguous sequence of bytes in memory, it could

/// be a file on disk, or it could be a PDB stream where bytes are stored as

/// discontiguous blocks in a file.  Usually it is desirable to treat arrays

/// as contiguous blocks of memory, but doing so with large PDB files, for

/// example, could mean allocating huge amounts of memory just to allow

/// re-ordering of stream data to be contiguous before iterating over it.  By

/// abstracting this out, we need not duplicate this memory, and we can

/// iterate over arrays in arbitrarily formatted streams.  Elements are parsed

/// lazily on iteration, so there is no upfront cost associated with building

/// or copying a VarStreamArray, no matter how large it may be.

///

/// You create a VarStreamArray by specifying a ValueType and an Extractor type.

/// If you do not specify an Extractor type, you are expected to specialize

/// VarStreamArrayExtractor<T> for your ValueType.

///

/// By default an Extractor is default constructed in the class, but in some

/// cases you might find it useful for an Extractor to maintain state across

/// extractions.  In this case you can provide your own Extractor through a

/// secondary constructor.  The following examples show various ways of

/// creating a VarStreamArray.

///

///       // Will use VarStreamArrayExtractor<MyType> as the extractor.

///       VarStreamArray<MyType> MyTypeArray;

///

///       // Will use a default-constructed MyExtractor as the extractor.

///       VarStreamArray<MyType, MyExtractor> MyTypeArray2;

///

///       // Will use the specific instance of MyExtractor provided.

///       // MyExtractor need not be default-constructible in this case.

///       MyExtractor E(SomeContext);

///       VarStreamArray<MyType, MyExtractor> MyTypeArray3(E);

///

template <typename ValueType, typename Extractor> class VarStreamArrayIterator;

template <typename ValueType,

          typename Extractor = VarStreamArrayExtractor<ValueType>>

class VarStreamArray {

  friend class VarStreamArrayIterator<ValueType, Extractor>;

public:

  typedef VarStreamArrayIterator<ValueType, Extractor> Iterator;

  VarStreamArray() = default;

  explicit VarStreamArray(const Extractor &E) : E(E) {}

  explicit VarStreamArray(BinaryStreamRef Stream, uint32_t Skew = 0)

      : Stream(Stream), Skew(Skew) {}

  VarStreamArray(BinaryStreamRef Stream, const Extractor &E, uint32_t Skew = 0)

      : Stream(Stream), E(E), Skew(Skew) {}

  Iterator begin(bool *HadError = nullptr) const {

    return Iterator(*this, E, Skew, nullptr);

  }

  bool valid() const { return Stream.valid(); }

  bool isOffsetValid(uint32_t Offset) const { return at(Offset) != end(); }

  uint32_t skew() const { return Skew; }

  Iterator end() const { return Iterator(E); }

  bool empty() const { return Stream.getLength() == 0; }

  VarStreamArray<ValueType, Extractor> substream(uint32_t Begin,

                                                 uint32_t End) const {

    assert(Begin >= Skew);

    // We should never cut off the beginning of the stream since it might be

    // skewed, meaning the initial bytes are important.

    BinaryStreamRef NewStream = Stream.slice(0, End);

    return {NewStream, E, Begin};

  }

  /// given an offset into the array's underlying stream, return an

  /// iterator to the record at that offset.  This is considered unsafe

  /// since the behavior is undefined if \p Offset does not refer to the

  /// beginning of a valid record.

  Iterator at(uint32_t Offset) const {

    return Iterator(*this, E, Offset, nullptr);

  }

  const Extractor &getExtractor() const { return E; }

  Extractor &getExtractor() { return E; }

  BinaryStreamRef getUnderlyingStream() const { return Stream; }

  void setUnderlyingStream(BinaryStreamRef NewStream, uint32_t NewSkew = 0) {

    Stream = NewStream;

    Skew = NewSkew;

  }

  void drop_front() { Skew += begin()->length(); }

private:

  BinaryStreamRef Stream;

  Extractor E;

  uint32_t Skew = 0;

};

template <typename ValueType, typename Extractor>

class VarStreamArrayIterator

    : public iterator_facade_base<VarStreamArrayIterator<ValueType, Extractor>,

                                  std::forward_iterator_tag, const ValueType> {

  typedef VarStreamArrayIterator<ValueType, Extractor> IterType;

  typedef VarStreamArray<ValueType, Extractor> ArrayType;

public:

  VarStreamArrayIterator(const ArrayType &Array, const Extractor &E,

                         uint32_t Offset, bool *HadError)

      : IterRef(Array.Stream.drop_front(Offset)), Extract(E),

        Array(&Array), AbsOffset(Offset), HadError(HadError) {

    if (IterRef.getLength() == 0)

      moveToEnd();

    else {

      auto EC = Extract(IterRef, ThisLen, ThisValue);

      if (EC) {

        consumeError(std::move(EC));

        markError();

      }

    }

  }

  VarStreamArrayIterator() = default;

  explicit VarStreamArrayIterator(const Extractor &E) : Extract(E) {}

  ~VarStreamArrayIterator() = default;

  bool operator==(const IterType &R) const {

    if (Array && R.Array) {

      // Both have a valid array, make sure they're same.

      assert(Array == R.Array);

      return IterRef == R.IterRef;

    }

    // Both iterators are at the end.

    if (!Array && !R.Array)

      return true;

    // One is not at the end and one is.

    return false;

  }

  const ValueType &operator*() const {

    assert(Array && !HasError);

    return ThisValue;

  }

  IterType &operator+=(unsigned N) {

    for (unsigned I = 0; I < N; ++I) {

      // We are done with the current record, discard it so that we are

      // positioned at the next record.

      AbsOffset += ThisLen;

      IterRef = IterRef.drop_front(ThisLen);

      if (IterRef.getLength() == 0) {

        // There is nothing after the current record, we must make this an end

        // iterator.

        moveToEnd();

      } else {

        // There is some data after the current record.

        auto EC = Extract(IterRef, ThisLen, ThisValue);

        if (EC) {

          consumeError(std::move(EC));

          markError();

        } else if (ThisLen == 0) {

          // An empty record? Make this an end iterator.

          moveToEnd();

        }

      }

    }

    return *this;

  }

  uint32_t offset() const { return AbsOffset; }

  uint32_t getRecordLength() const { return ThisLen; }

private:

  void moveToEnd() {

    Array = nullptr;

    ThisLen = 0;

  }

  void markError() {

    moveToEnd();

    HasError = true;

    if (HadError != nullptr)

      *HadError = true;

  }

  ValueType ThisValue;

  BinaryStreamRef IterRef;

  Extractor Extract;

  const ArrayType *Array{nullptr};

  uint32_t ThisLen{0};

  uint32_t AbsOffset{0};

  bool HasError{false};

  bool *HadError{nullptr};

};

template <typename T> class FixedStreamArrayIterator;

/// FixedStreamArray is similar to VarStreamArray, except with each record

/// having a fixed-length.  As with VarStreamArray, there is no upfront

/// cost associated with building or copying a FixedStreamArray, as the

/// memory for each element is not read from the backing stream until that

/// element is iterated.

template <typename T> class FixedStreamArray {

  friend class FixedStreamArrayIterator<T>;

public:

  typedef FixedStreamArrayIterator<T> Iterator;

  FixedStreamArray() = default;

  explicit FixedStreamArray(BinaryStreamRef Stream) : Stream(Stream) {

    assert(Stream.getLength() % sizeof(T) == 0);

  }

  bool operator==(const FixedStreamArray<T> &Other) const {

    return Stream == Other.Stream;

  }

  bool operator!=(const FixedStreamArray<T> &Other) const {

    return !(*this == Other);

  }

  FixedStreamArray(const FixedStreamArray &) = default;

  FixedStreamArray &operator=(const FixedStreamArray &) = default;

  const T &operator[](uint32_t Index) const {

    assert(Index < size());

    uint32_t Off = Index * sizeof(T);

    ArrayRef<uint8_t> Data;

    if (auto EC = Stream.readBytes(Off, sizeof(T), Data)) {

      assert(false && "Unexpected failure reading from stream");

      // This should never happen since we asserted that the stream length was

      // an exact multiple of the element size.

      consumeError(std::move(EC));

    }

    assert(isAddrAligned(Align::Of<T>(), Data.data()));

    return *reinterpret_cast<const T *>(Data.data());

  }

  uint32_t size() const { return Stream.getLength() / sizeof(T); }

  bool empty() const { return size() == 0; }

  FixedStreamArrayIterator<T> begin() const {

    return FixedStreamArrayIterator<T>(*this, 0);

  }

  FixedStreamArrayIterator<T> end() const {

    return FixedStreamArrayIterator<T>(*this, size());

  }

  const T &front() const { return *begin(); }

  const T &back() const {

    FixedStreamArrayIterator<T> I = end();

    return *(--I);

  }

  BinaryStreamRef getUnderlyingStream() const { return Stream; }

private:

  BinaryStreamRef Stream;

};

template <typename T>

class FixedStreamArrayIterator

    : public iterator_facade_base<FixedStreamArrayIterator<T>,

                                  std::random_access_iterator_tag, const T> {

public:

  FixedStreamArrayIterator(const FixedStreamArray<T> &Array, uint32_t Index)

      : Array(Array), Index(Index) {}

  FixedStreamArrayIterator(const FixedStreamArrayIterator<T> &Other)

      : Array(Other.Array), Index(Other.Index) {}

  FixedStreamArrayIterator<T> &

  operator=(const FixedStreamArrayIterator<T> &Other) {

    Array = Other.Array;

    Index = Other.Index;

    return *this;

  }

  const T &operator*() const { return Array[Index]; }

  const T &operator*() { return Array[Index]; }

  bool operator==(const FixedStreamArrayIterator<T> &R) const {

    assert(Array == R.Array);

    return (Index == R.Index) && (Array == R.Array);

  }

  FixedStreamArrayIterator<T> &operator+=(std::ptrdiff_t N) {

    Index += N;

    return *this;

  }

  FixedStreamArrayIterator<T> &operator-=(std::ptrdiff_t N) {

    assert(std::ptrdiff_t(Index) >= N);

    Index -= N;

    return *this;

  }

  std::ptrdiff_t operator-(const FixedStreamArrayIterator<T> &R) const {

    assert(Array == R.Array);

    assert(Index >= R.Index);

    return Index - R.Index;

  }

  bool operator<(const FixedStreamArrayIterator<T> &RHS) const {

    assert(Array == RHS.Array);

    return Index < RHS.Index;

  }

private:

  FixedStreamArray<T> Array;

  uint32_t Index;

};

} // namespace llvm

#endif // LLVM_SUPPORT_BINARYSTREAMARRAY_H