LLVM  10.0.0svn
BinaryStreamArray.h
Go to the documentation of this file.
1 //===- BinaryStreamArray.h - Array backed by an arbitrary stream *- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef LLVM_SUPPORT_BINARYSTREAMARRAY_H
10 #define LLVM_SUPPORT_BINARYSTREAMARRAY_H
11 
12 #include "llvm/ADT/ArrayRef.h"
13 #include "llvm/ADT/iterator.h"
15 #include "llvm/Support/Error.h"
16 #include <cassert>
17 #include <cstdint>
18 
19 /// Lightweight arrays that are backed by an arbitrary BinaryStream. This file
20 /// provides two different array implementations.
21 ///
22 /// VarStreamArray - Arrays of variable length records. The user specifies
23 /// an Extractor type that can extract a record from a given offset and
24 /// return the number of bytes consumed by the record.
25 ///
26 /// FixedStreamArray - Arrays of fixed length records. This is similar in
27 /// spirit to ArrayRef<T>, but since it is backed by a BinaryStream, the
28 /// elements of the array need not be laid out in contiguous memory.
29 namespace llvm {
30 
31 /// VarStreamArrayExtractor is intended to be specialized to provide customized
32 /// extraction logic. On input it receives a BinaryStreamRef pointing to the
33 /// beginning of the next record, but where the length of the record is not yet
34 /// known. Upon completion, it should return an appropriate Error instance if
35 /// a record could not be extracted, or if one could be extracted it should
36 /// return success and set Len to the number of bytes this record occupied in
37 /// the underlying stream, and it should fill out the fields of the value type
38 /// Item appropriately to represent the current record.
39 ///
40 /// You can specialize this template for your own custom value types to avoid
41 /// having to specify a second template argument to VarStreamArray (documented
42 /// below).
43 template <typename T> struct VarStreamArrayExtractor {
44  // Method intentionally deleted. You must provide an explicit specialization
45  // with the following method implemented.
47  T &Item) const = delete;
48 };
49 
50 /// VarStreamArray represents an array of variable length records backed by a
51 /// stream. This could be a contiguous sequence of bytes in memory, it could
52 /// be a file on disk, or it could be a PDB stream where bytes are stored as
53 /// discontiguous blocks in a file. Usually it is desirable to treat arrays
54 /// as contiguous blocks of memory, but doing so with large PDB files, for
55 /// example, could mean allocating huge amounts of memory just to allow
56 /// re-ordering of stream data to be contiguous before iterating over it. By
57 /// abstracting this out, we need not duplicate this memory, and we can
58 /// iterate over arrays in arbitrarily formatted streams. Elements are parsed
59 /// lazily on iteration, so there is no upfront cost associated with building
60 /// or copying a VarStreamArray, no matter how large it may be.
61 ///
62 /// You create a VarStreamArray by specifying a ValueType and an Extractor type.
63 /// If you do not specify an Extractor type, you are expected to specialize
64 /// VarStreamArrayExtractor<T> for your ValueType.
65 ///
66 /// By default an Extractor is default constructed in the class, but in some
67 /// cases you might find it useful for an Extractor to maintain state across
68 /// extractions. In this case you can provide your own Extractor through a
69 /// secondary constructor. The following examples show various ways of
70 /// creating a VarStreamArray.
71 ///
72 /// // Will use VarStreamArrayExtractor<MyType> as the extractor.
73 /// VarStreamArray<MyType> MyTypeArray;
74 ///
75 /// // Will use a default-constructed MyExtractor as the extractor.
76 /// VarStreamArray<MyType, MyExtractor> MyTypeArray2;
77 ///
78 /// // Will use the specific instance of MyExtractor provided.
79 /// // MyExtractor need not be default-constructible in this case.
80 /// MyExtractor E(SomeContext);
81 /// VarStreamArray<MyType, MyExtractor> MyTypeArray3(E);
82 ///
83 
84 template <typename ValueType, typename Extractor> class VarStreamArrayIterator;
85 
86 template <typename ValueType,
87  typename Extractor = VarStreamArrayExtractor<ValueType>>
89  friend class VarStreamArrayIterator<ValueType, Extractor>;
90 
91 public:
93 
94  VarStreamArray() = default;
95 
96  explicit VarStreamArray(const Extractor &E) : E(E) {}
97 
98  explicit VarStreamArray(BinaryStreamRef Stream, uint32_t Skew = 0)
99  : Stream(Stream), Skew(Skew) {}
100 
101  VarStreamArray(BinaryStreamRef Stream, const Extractor &E, uint32_t Skew = 0)
102  : Stream(Stream), E(E), Skew(Skew) {}
103 
104  Iterator begin(bool *HadError = nullptr) const {
105  return Iterator(*this, E, Skew, nullptr);
106  }
107 
108  bool valid() const { return Stream.valid(); }
109 
110  uint32_t skew() const { return Skew; }
111  Iterator end() const { return Iterator(E); }
112 
113  bool empty() const { return Stream.getLength() == 0; }
114 
116  uint32_t End) const {
117  assert(Begin >= Skew);
118  // We should never cut off the beginning of the stream since it might be
119  // skewed, meaning the initial bytes are important.
120  BinaryStreamRef NewStream = Stream.slice(0, End);
121  return {NewStream, E, Begin};
122  }
123 
124  /// given an offset into the array's underlying stream, return an
125  /// iterator to the record at that offset. This is considered unsafe
126  /// since the behavior is undefined if \p Offset does not refer to the
127  /// beginning of a valid record.
128  Iterator at(uint32_t Offset) const {
129  return Iterator(*this, E, Offset, nullptr);
130  }
131 
132  const Extractor &getExtractor() const { return E; }
133  Extractor &getExtractor() { return E; }
134 
135  BinaryStreamRef getUnderlyingStream() const { return Stream; }
137  Stream = S;
138  this->Skew = Skew;
139  }
140 
141  void drop_front() { Skew += begin()->length(); }
142 
143 private:
144  BinaryStreamRef Stream;
145  Extractor E;
146  uint32_t Skew;
147 };
148 
149 template <typename ValueType, typename Extractor>
151  : public iterator_facade_base<VarStreamArrayIterator<ValueType, Extractor>,
152  std::forward_iterator_tag, ValueType> {
155 
156 public:
157  VarStreamArrayIterator(const ArrayType &Array, const Extractor &E,
158  uint32_t Offset, bool *HadError)
159  : IterRef(Array.Stream.drop_front(Offset)), Extract(E),
160  Array(&Array), AbsOffset(Offset), HadError(HadError) {
161  if (IterRef.getLength() == 0)
162  moveToEnd();
163  else {
164  auto EC = Extract(IterRef, ThisLen, ThisValue);
165  if (EC) {
166  consumeError(std::move(EC));
167  markError();
168  }
169  }
170  }
171 
172  VarStreamArrayIterator() = default;
173  explicit VarStreamArrayIterator(const Extractor &E) : Extract(E) {}
174  ~VarStreamArrayIterator() = default;
175 
176  bool operator==(const IterType &R) const {
177  if (Array && R.Array) {
178  // Both have a valid array, make sure they're same.
179  assert(Array == R.Array);
180  return IterRef == R.IterRef;
181  }
182 
183  // Both iterators are at the end.
184  if (!Array && !R.Array)
185  return true;
186 
187  // One is not at the end and one is.
188  return false;
189  }
190 
191  const ValueType &operator*() const {
192  assert(Array && !HasError);
193  return ThisValue;
194  }
195 
197  assert(Array && !HasError);
198  return ThisValue;
199  }
200 
201  IterType &operator+=(unsigned N) {
202  for (unsigned I = 0; I < N; ++I) {
203  // We are done with the current record, discard it so that we are
204  // positioned at the next record.
205  AbsOffset += ThisLen;
206  IterRef = IterRef.drop_front(ThisLen);
207  if (IterRef.getLength() == 0) {
208  // There is nothing after the current record, we must make this an end
209  // iterator.
210  moveToEnd();
211  } else {
212  // There is some data after the current record.
213  auto EC = Extract(IterRef, ThisLen, ThisValue);
214  if (EC) {
215  consumeError(std::move(EC));
216  markError();
217  } else if (ThisLen == 0) {
218  // An empty record? Make this an end iterator.
219  moveToEnd();
220  }
221  }
222  }
223  return *this;
224  }
225 
226  uint32_t offset() const { return AbsOffset; }
227  uint32_t getRecordLength() const { return ThisLen; }
228 
229 private:
230  void moveToEnd() {
231  Array = nullptr;
232  ThisLen = 0;
233  }
234  void markError() {
235  moveToEnd();
236  HasError = true;
237  if (HadError != nullptr)
238  *HadError = true;
239  }
240 
241  ValueType ThisValue;
242  BinaryStreamRef IterRef;
243  Extractor Extract;
244  const ArrayType *Array{nullptr};
245  uint32_t ThisLen{0};
246  uint32_t AbsOffset{0};
247  bool HasError{false};
248  bool *HadError{nullptr};
249 };
250 
251 template <typename T> class FixedStreamArrayIterator;
252 
253 /// FixedStreamArray is similar to VarStreamArray, except with each record
254 /// having a fixed-length. As with VarStreamArray, there is no upfront
255 /// cost associated with building or copying a FixedStreamArray, as the
256 /// memory for each element is not read from the backing stream until that
257 /// element is iterated.
258 template <typename T> class FixedStreamArray {
260 
261 public:
263 
264  FixedStreamArray() = default;
265  explicit FixedStreamArray(BinaryStreamRef Stream) : Stream(Stream) {
266  assert(Stream.getLength() % sizeof(T) == 0);
267  }
268 
269  bool operator==(const FixedStreamArray<T> &Other) const {
270  return Stream == Other.Stream;
271  }
272 
273  bool operator!=(const FixedStreamArray<T> &Other) const {
274  return !(*this == Other);
275  }
276 
277  FixedStreamArray &operator=(const FixedStreamArray &) = default;
278 
279  const T &operator[](uint32_t Index) const {
280  assert(Index < size());
281  uint32_t Off = Index * sizeof(T);
283  if (auto EC = Stream.readBytes(Off, sizeof(T), Data)) {
284  assert(false && "Unexpected failure reading from stream");
285  // This should never happen since we asserted that the stream length was
286  // an exact multiple of the element size.
287  consumeError(std::move(EC));
288  }
289  assert(llvm::alignmentAdjustment(Data.data(), alignof(T)) == 0);
290  return *reinterpret_cast<const T *>(Data.data());
291  }
292 
293  uint32_t size() const { return Stream.getLength() / sizeof(T); }
294 
295  bool empty() const { return size() == 0; }
296 
298  return FixedStreamArrayIterator<T>(*this, 0);
299  }
300 
302  return FixedStreamArrayIterator<T>(*this, size());
303  }
304 
305  const T &front() const { return *begin(); }
306  const T &back() const {
308  return *(--I);
309  }
310 
311  BinaryStreamRef getUnderlyingStream() const { return Stream; }
312 
313 private:
314  BinaryStreamRef Stream;
315 };
316 
317 template <typename T>
319  : public iterator_facade_base<FixedStreamArrayIterator<T>,
320  std::random_access_iterator_tag, const T> {
321 
322 public:
324  : Array(Array), Index(Index) {}
325 
328  Array = Other.Array;
329  Index = Other.Index;
330  return *this;
331  }
332 
333  const T &operator*() const { return Array[Index]; }
334  const T &operator*() { return Array[Index]; }
335 
337  assert(Array == R.Array);
338  return (Index == R.Index) && (Array == R.Array);
339  }
340 
342  Index += N;
343  return *this;
344  }
345 
347  assert(std::ptrdiff_t(Index) >= N);
348  Index -= N;
349  return *this;
350  }
351 
352  std::ptrdiff_t operator-(const FixedStreamArrayIterator<T> &R) const {
353  assert(Array == R.Array);
354  assert(Index >= R.Index);
355  return Index - R.Index;
356  }
357 
358  bool operator<(const FixedStreamArrayIterator<T> &RHS) const {
359  assert(Array == RHS.Array);
360  return Index < RHS.Index;
361  }
362 
363 private:
364  FixedStreamArray<T> Array;
365  uint32_t Index;
366 };
367 
368 } // namespace llvm
369 
370 #endif // LLVM_SUPPORT_BINARYSTREAMARRAY_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
bool operator==(const IterType &R) const
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
RefType slice(uint32_t Offset, uint32_t Len) const
Return a new BinaryStreamRef with the first Offset elements removed, and retaining exactly Len elemen...
const ValueType & operator*() const
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Iterator end() const
VarStreamArray(const Extractor &E)
VarStreamArray(BinaryStreamRef Stream, const Extractor &E, uint32_t Skew=0)
bool operator!=(const FixedStreamArray< T > &Other) const
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:948
BinaryStreamRef getUnderlyingStream() const
VarStreamArray(BinaryStreamRef Stream, uint32_t Skew=0)
FixedStreamArray is similar to VarStreamArray, except with each record having a fixed-length.
VarStreamArrayExtractor is intended to be specialized to provide customized extraction logic...
VarStreamArray< ValueType, Extractor > substream(uint32_t Begin, uint32_t End) const
FixedStreamArrayIterator< T > Iterator
const T & operator[](uint32_t Index) const
void setUnderlyingStream(BinaryStreamRef S, uint32_t Skew=0)
FixedStreamArrayIterator< T > & operator=(const FixedStreamArrayIterator< T > &Other)
Class to represent array types.
Definition: DerivedTypes.h:403
uint32_t skew() const
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:67
VarStreamArrayIterator(const ArrayType &Array, const Extractor &E, uint32_t Offset, bool *HadError)
Extractor & getExtractor()
VarStreamArrayIterator< ValueType, Extractor > Iterator
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
size_t alignmentAdjustment(const void *Ptr, size_t Alignment)
Returns the necessary adjustment for aligning Ptr to Alignment bytes, rounding up.
Definition: MathExtras.h:638
VarStreamArrayIterator(const Extractor &E)
bool operator==(const FixedStreamArrayIterator< T > &R) const
IterType & operator+=(unsigned N)
void consumeError(Error Err)
Consume a Error without doing anything.
Definition: Error.h:981
const T & front() const
FixedStreamArray(BinaryStreamRef Stream)
uint32_t getLength() const
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1146
FixedStreamArrayIterator(const FixedStreamArray< T > &Array, uint32_t Index)
BinaryStreamRef is to BinaryStream what ArrayRef is to an Array.
VarStreamArray represents an array of variable length records backed by a stream. ...
FixedStreamArrayIterator< T > & operator-=(std::ptrdiff_t N)
FixedStreamArrayIterator< T > & operator+=(std::ptrdiff_t N)
const T & back() const
BinaryStreamRef getUnderlyingStream() const
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
Error operator()(BinaryStreamRef Stream, uint32_t &Len, T &Item) const =delete
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
FixedStreamArrayIterator< T > end() const
Iterator at(uint32_t Offset) const
given an offset into the array&#39;s underlying stream, return an iterator to the record at that offset...
Iterator begin(bool *HadError=nullptr) const
const Extractor & getExtractor() const
std::ptrdiff_t operator-(const FixedStreamArrayIterator< T > &R) const
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
bool operator==(const FixedStreamArray< T > &Other) const
FixedStreamArrayIterator< T > begin() const
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:156