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