1//===--- ArrayRef.h - Array Reference Wrapper -------------------*- 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_ADT_ARRAYREF_H
11#define LLVM_ADT_ARRAYREF_H
12
13#include "llvm/ADT/Hashing.h"
14#include "llvm/ADT/None.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallVector.h"
17#include <array>
18#include <vector>
19
20namespace llvm {
21 /// ArrayRef - Represent a constant reference to an array (0 or more elements
22 /// consecutively in memory), i.e. a start pointer and a length. It allows
23 /// various APIs to take consecutive elements easily and conveniently.
24 ///
25 /// This class does not own the underlying data, it is expected to be used in
26 /// situations where the data resides in some other buffer, whose lifetime
27 /// extends past that of the ArrayRef. For this reason, it is not in general
28 /// safe to store an ArrayRef.
29 ///
30 /// This is intended to be trivially copyable, so it should be passed by
31 /// value.
32 template<typename T>
33 class LLVM_NODISCARD ArrayRef {
34 public:
35 typedef const T *iterator;
36 typedef const T *const_iterator;
37 typedef size_t size_type;
38
39 typedef std::reverse_iterator<iterator> reverse_iterator;
40
41 private:
42 /// The start of the array, in an external buffer.
43 const T *Data;
44
45 /// The number of elements.
46 size_type Length;
47
48 public:
49 /// @name Constructors
50 /// @{
51
52 /// Construct an empty ArrayRef.
53 /*implicit*/ ArrayRef() : Data(nullptr), Length(0) {}
54
55 /// Construct an empty ArrayRef from None.
56 /*implicit*/ ArrayRef(NoneType) : Data(nullptr), Length(0) {}
57
58 /// Construct an ArrayRef from a single element.
59 /*implicit*/ ArrayRef(const T &OneElt)
60 : Data(&OneElt), Length(1) {}
61
62 /// Construct an ArrayRef from a pointer and length.
63 /*implicit*/ ArrayRef(const T *data, size_t length)
64 : Data(data), Length(length) {}
65
66 /// Construct an ArrayRef from a range.
67 ArrayRef(const T *begin, const T *end)
68 : Data(begin), Length(end - begin) {}
69
70 /// Construct an ArrayRef from a SmallVector. This is templated in order to
71 /// avoid instantiating SmallVectorTemplateCommon<T> whenever we
72 /// copy-construct an ArrayRef.
73 template<typename U>
74 /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<T, U> &Vec)
75 : Data(Vec.data()), Length(Vec.size()) {
76 }
77
78 /// Construct an ArrayRef from a std::vector.
79 template<typename A>
80 /*implicit*/ ArrayRef(const std::vector<T, A> &Vec)
81 : Data(Vec.data()), Length(Vec.size()) {}
82
83 /// Construct an ArrayRef from a std::array
84 template <size_t N>
85 /*implicit*/ constexpr ArrayRef(const std::array<T, N> &Arr)
86 : Data(Arr.data()), Length(N) {}
87
88 /// Construct an ArrayRef from a C array.
89 template <size_t N>
90 /*implicit*/ constexpr ArrayRef(const T (&Arr)[N]) : Data(Arr), Length(N) {}
91
92 /// Construct an ArrayRef from a std::initializer_list.
93 /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec)
94 : Data(Vec.begin() == Vec.end() ? (T*)nullptr : Vec.begin()),
95 Length(Vec.size()) {}
96
97 /// Construct an ArrayRef<const T*> from ArrayRef<T*>. This uses SFINAE to
98 /// ensure that only ArrayRefs of pointers can be converted.
99 template <typename U>
100 ArrayRef(
101 const ArrayRef<U *> &A,
102 typename std::enable_if<
103 std::is_convertible<U *const *, T const *>::value>::type * = nullptr)
104 : Data(A.data()), Length(A.size()) {}
105
106 /// Construct an ArrayRef<const T*> from a SmallVector<T*>. This is
107 /// templated in order to avoid instantiating SmallVectorTemplateCommon<T>
108 /// whenever we copy-construct an ArrayRef.
109 template<typename U, typename DummyT>
110 /*implicit*/ ArrayRef(
111 const SmallVectorTemplateCommon<U *, DummyT> &Vec,
112 typename std::enable_if<
113 std::is_convertible<U *const *, T const *>::value>::type * = nullptr)
114 : Data(Vec.data()), Length(Vec.size()) {
115 }
116
117 /// Construct an ArrayRef<const T*> from std::vector<T*>. This uses SFINAE
118 /// to ensure that only vectors of pointers can be converted.
119 template<typename U, typename A>
120 ArrayRef(const std::vector<U *, A> &Vec,
121 typename std::enable_if<
122 std::is_convertible<U *const *, T const *>::value>::type* = 0)
123 : Data(Vec.data()), Length(Vec.size()) {}
124
125 /// @}
126 /// @name Simple Operations
127 /// @{
128
129 iterator begin() const { return Data; }
130 iterator end() const { return Data + Length; }
131
132 reverse_iterator rbegin() const { return reverse_iterator(end()); }
133 reverse_iterator rend() const { return reverse_iterator(begin()); }
134
135 /// empty - Check if the array is empty.
136 bool empty() const { return Length == 0; }
137
138 const T *data() const { return Data; }
139
140 /// size - Get the array size.
141 size_t size() const { return Length; }
142
143 /// front - Get the first element.
144 const T &front() const {
145 assert(!empty());
146 return Data[0];
147 }
148
149 /// back - Get the last element.
150 const T &back() const {
151 assert(!empty());
152 return Data[Length-1];
153 }
154
155 // copy - Allocate copy in Allocator and return ArrayRef<T> to it.
156 template <typename Allocator> ArrayRef<T> copy(Allocator &A) {
157 T *Buff = A.template Allocate<T>(Length);
158 std::uninitialized_copy(begin(), end(), Buff);
159 return ArrayRef<T>(Buff, Length);
160 }
161
162 /// equals - Check for element-wise equality.
163 bool equals(ArrayRef RHS) const {
164 if (Length != RHS.Length)
165 return false;
166 return std::equal(begin(), end(), RHS.begin());
167 }
168
169 /// slice(n, m) - Chop off the first N elements of the array, and keep M
170 /// elements in the array.
171 ArrayRef<T> slice(size_t N, size_t M) const {
172 assert(N+M <= size() && "Invalid specifier");
173 return ArrayRef<T>(data()+N, M);
174 }
175
176 /// slice(n) - Chop off the first N elements of the array.
177 ArrayRef<T> slice(size_t N) const { return slice(N, size() - N); }
178
179 /// \brief Drop the first \p N elements of the array.
180 ArrayRef<T> drop_front(size_t N = 1) const {
181 assert(size() >= N && "Dropping more elements than exist");
182 return slice(N, size() - N);
183 }
184
185 /// \brief Drop the last \p N elements of the array.
186 ArrayRef<T> drop_back(size_t N = 1) const {
187 assert(size() >= N && "Dropping more elements than exist");
188 return slice(0, size() - N);
189 }
190
191 /// \brief Return a copy of *this with the first N elements satisfying the
192 /// given predicate removed.
193 template <class PredicateT> ArrayRef<T> drop_while(PredicateT Pred) const {
194 return ArrayRef<T>(find_if_not(*this, Pred), end());
195 }
196
197 /// \brief Return a copy of *this with the first N elements not satisfying
198 /// the given predicate removed.
199 template <class PredicateT> ArrayRef<T> drop_until(PredicateT Pred) const {
200 return ArrayRef<T>(find_if(*this, Pred), end());
201 }
202
203 /// \brief Return a copy of *this with only the first \p N elements.
204 ArrayRef<T> take_front(size_t N = 1) const {
205 if (N >= size())
206 return *this;
207 return drop_back(size() - N);
208 }
209
210 /// \brief Return a copy of *this with only the last \p N elements.
211 ArrayRef<T> take_back(size_t N = 1) const {
212 if (N >= size())
213 return *this;
214 return drop_front(size() - N);
215 }
216
217 /// \brief Return the first N elements of this Array that satisfy the given
218 /// predicate.
219 template <class PredicateT> ArrayRef<T> take_while(PredicateT Pred) const {
220 return ArrayRef<T>(begin(), find_if_not(*this, Pred));
221 }
222
223 /// \brief Return the first N elements of this Array that don't satisfy the
224 /// given predicate.
225 template <class PredicateT> ArrayRef<T> take_until(PredicateT Pred) const {
226 return ArrayRef<T>(begin(), find_if(*this, Pred));
227 }
228
229 /// @}
230 /// @name Operator Overloads
231 /// @{
232 const T &operator[](size_t Index) const {
233 assert(Index < Length && "Invalid index!");
234 return Data[Index];
235 }
236
237 /// Disallow accidental assignment from a temporary.
238 ///
239 /// The declaration here is extra complicated so that "arrayRef = {}"
240 /// continues to select the move assignment operator.
241 template <typename U>
242 typename std::enable_if<std::is_same<U, T>::value, ArrayRef<T>>::type &
243 operator=(U &&Temporary) = delete;
244
245 /// Disallow accidental assignment from a temporary.
246 ///
247 /// The declaration here is extra complicated so that "arrayRef = {}"
248 /// continues to select the move assignment operator.
249 template <typename U>
250 typename std::enable_if<std::is_same<U, T>::value, ArrayRef<T>>::type &
251 operator=(std::initializer_list<U>) = delete;
252
253 /// @}
254 /// @name Expensive Operations
255 /// @{
256 std::vector<T> vec() const {
257 return std::vector<T>(Data, Data+Length);
258 }
259
260 /// @}
261 /// @name Conversion operators
262 /// @{
263 operator std::vector<T>() const {
264 return std::vector<T>(Data, Data+Length);
265 }
266
267 /// @}
268 };
269
270 /// MutableArrayRef - Represent a mutable reference to an array (0 or more
271 /// elements consecutively in memory), i.e. a start pointer and a length. It
272 /// allows various APIs to take and modify consecutive elements easily and
273 /// conveniently.
274 ///
275 /// This class does not own the underlying data, it is expected to be used in
276 /// situations where the data resides in some other buffer, whose lifetime
277 /// extends past that of the MutableArrayRef. For this reason, it is not in
278 /// general safe to store a MutableArrayRef.
279 ///
280 /// This is intended to be trivially copyable, so it should be passed by
281 /// value.
282 template<typename T>
283 class LLVM_NODISCARD MutableArrayRef : public ArrayRef<T> {
284 public:
285 typedef T *iterator;
286
287 typedef std::reverse_iterator<iterator> reverse_iterator;
288
289 /// Construct an empty MutableArrayRef.
290 /*implicit*/ MutableArrayRef() : ArrayRef<T>() {}
291
292 /// Construct an empty MutableArrayRef from None.
293 /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {}
294
295 /// Construct an MutableArrayRef from a single element.
296 /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {}
297
298 /// Construct an MutableArrayRef from a pointer and length.
299 /*implicit*/ MutableArrayRef(T *data, size_t length)
300 : ArrayRef<T>(data, length) {}
301
302 /// Construct an MutableArrayRef from a range.
303 MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {}
304
305 /// Construct an MutableArrayRef from a SmallVector.
306 /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec)
307 : ArrayRef<T>(Vec) {}
308
309 /// Construct a MutableArrayRef from a std::vector.
310 /*implicit*/ MutableArrayRef(std::vector<T> &Vec)
311 : ArrayRef<T>(Vec) {}
312
313 /// Construct an ArrayRef from a std::array
314 template <size_t N>
315 /*implicit*/ constexpr MutableArrayRef(std::array<T, N> &Arr)
316 : ArrayRef<T>(Arr) {}
317
318 /// Construct an MutableArrayRef from a C array.
319 template <size_t N>
320 /*implicit*/ constexpr MutableArrayRef(T (&Arr)[N]) : ArrayRef<T>(Arr) {}
321
322 T *data() const { return const_cast<T*>(ArrayRef<T>::data()); }
323
324 iterator begin() const { return data(); }
325 iterator end() const { return data() + this->size(); }
326
327 reverse_iterator rbegin() const { return reverse_iterator(end()); }
328 reverse_iterator rend() const { return reverse_iterator(begin()); }
329
330 /// front - Get the first element.
331 T &front() const {
332 assert(!this->empty());
333 return data()[0];
334 }
335
336 /// back - Get the last element.
337 T &back() const {
338 assert(!this->empty());
339 return data()[this->size()-1];
340 }
341
342 /// slice(n, m) - Chop off the first N elements of the array, and keep M
343 /// elements in the array.
344 MutableArrayRef<T> slice(size_t N, size_t M) const {
345 assert(N + M <= this->size() && "Invalid specifier");
346 return MutableArrayRef<T>(this->data() + N, M);
347 }
348
349 /// slice(n) - Chop off the first N elements of the array.
350 MutableArrayRef<T> slice(size_t N) const {
351 return slice(N, this->size() - N);
352 }
353
354 /// \brief Drop the first \p N elements of the array.
355 MutableArrayRef<T> drop_front(size_t N = 1) const {
356 assert(this->size() >= N && "Dropping more elements than exist");
357 return slice(N, this->size() - N);
358 }
359
360 MutableArrayRef<T> drop_back(size_t N = 1) const {
361 assert(this->size() >= N && "Dropping more elements than exist");
362 return slice(0, this->size() - N);
363 }
364
365 /// \brief Return a copy of *this with the first N elements satisfying the
366 /// given predicate removed.
367 template <class PredicateT>
368 MutableArrayRef<T> drop_while(PredicateT Pred) const {
369 return MutableArrayRef<T>(find_if_not(*this, Pred), end());
370 }
371
372 /// \brief Return a copy of *this with the first N elements not satisfying
373 /// the given predicate removed.
374 template <class PredicateT>
375 MutableArrayRef<T> drop_until(PredicateT Pred) const {
376 return MutableArrayRef<T>(find_if(*this, Pred), end());
377 }
378
379 /// \brief Return a copy of *this with only the first \p N elements.
380 MutableArrayRef<T> take_front(size_t N = 1) const {
381 if (N >= this->size())
382 return *this;
383 return drop_back(this->size() - N);
384 }
385
386 /// \brief Return a copy of *this with only the last \p N elements.
387 MutableArrayRef<T> take_back(size_t N = 1) const {
388 if (N >= this->size())
389 return *this;
390 return drop_front(this->size() - N);
391 }
392
393 /// \brief Return the first N elements of this Array that satisfy the given
394 /// predicate.
395 template <class PredicateT>
396 MutableArrayRef<T> take_while(PredicateT Pred) const {
397 return MutableArrayRef<T>(begin(), find_if_not(*this, Pred));
398 }
399
400 /// \brief Return the first N elements of this Array that don't satisfy the
401 /// given predicate.
402 template <class PredicateT>
403 MutableArrayRef<T> take_until(PredicateT Pred) const {
404 return MutableArrayRef<T>(begin(), find_if(*this, Pred));
405 }
406
407 /// @}
408 /// @name Operator Overloads
409 /// @{
410 T &operator[](size_t Index) const {
411 assert(Index < this->size() && "Invalid index!");
412 return data()[Index];
413 }
414 };
415
416 /// This is a MutableArrayRef that owns its array.
417 template <typename T> class OwningArrayRef : public MutableArrayRef<T> {
418 public:
419 OwningArrayRef() {}
420 OwningArrayRef(size_t Size) : MutableArrayRef<T>(new T[Size], Size) {}
421 OwningArrayRef(ArrayRef<T> Data)
422 : MutableArrayRef<T>(new T[Data.size()], Data.size()) {
423 std::copy(Data.begin(), Data.end(), this->begin());
424 }
425 OwningArrayRef(OwningArrayRef &&Other) { *this = Other; }
426 OwningArrayRef &operator=(OwningArrayRef &&Other) {
427 delete[] this->data();
428 this->MutableArrayRef<T>::operator=(Other);
429 Other.MutableArrayRef<T>::operator=(MutableArrayRef<T>());
430 return *this;
431 }
432 ~OwningArrayRef() { delete[] this->data(); }
433 };
434
435 /// @name ArrayRef Convenience constructors
436 /// @{
437
438 /// Construct an ArrayRef from a single element.
439 template<typename T>
440 ArrayRef<T> makeArrayRef(const T &OneElt) {
441 return OneElt;
442 }
443
444 /// Construct an ArrayRef from a pointer and length.
445 template<typename T>
446 ArrayRef<T> makeArrayRef(const T *data, size_t length) {
447 return ArrayRef<T>(data, length);
448 }
449
450 /// Construct an ArrayRef from a range.
451 template<typename T>
452 ArrayRef<T> makeArrayRef(const T *begin, const T *end) {
453 return ArrayRef<T>(begin, end);
454 }
455
456 /// Construct an ArrayRef from a SmallVector.
457 template <typename T>
458 ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) {
459 return Vec;
460 }
461
462 /// Construct an ArrayRef from a SmallVector.
463 template <typename T, unsigned N>
464 ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) {
465 return Vec;
466 }
467
468 /// Construct an ArrayRef from a std::vector.
469 template<typename T>
470 ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) {
471 return Vec;
472 }
473
474 /// Construct an ArrayRef from an ArrayRef (no-op) (const)
475 template <typename T> ArrayRef<T> makeArrayRef(const ArrayRef<T> &Vec) {
476 return Vec;
477 }
478
479 /// Construct an ArrayRef from an ArrayRef (no-op)
480 template <typename T> ArrayRef<T> &makeArrayRef(ArrayRef<T> &Vec) {
481 return Vec;
482 }
483
484 /// Construct an ArrayRef from a C array.
485 template<typename T, size_t N>
486 ArrayRef<T> makeArrayRef(const T (&Arr)[N]) {
487 return ArrayRef<T>(Arr);
488 }
489
490 /// @}
491 /// @name ArrayRef Comparison Operators
492 /// @{
493
494 template<typename T>
495 inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) {
496 return LHS.equals(RHS);
497 }
498
499 template<typename T>
500 inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) {
501 return !(LHS == RHS);
502 }
503
504 /// @}
505
506 // ArrayRefs can be treated like a POD type.
507 template <typename T> struct isPodLike;
508 template <typename T> struct isPodLike<ArrayRef<T> > {
509 static const bool value = true;
510 };
511
512 template <typename T> hash_code hash_value(ArrayRef<T> S) {
513 return hash_combine_range(S.begin(), S.end());
514 }
515} // end namespace llvm
516
517#endif // LLVM_ADT_ARRAYREF_H
518