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