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

source code of llvm/include/llvm/ADT/ArrayRef.h