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