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

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