Home | History | Annotate | Download | only in ADT
      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 
     28 namespace 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     /// \brief 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     /// \brief 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     /// \brief 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     /// \brief 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     /// \brief 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     /// \brief 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     /// \brief 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     /// \brief 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() : ArrayRef<T>() {}
    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     /// \brief 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     /// \brief 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     /// \brief 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     /// \brief 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     /// \brief 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     /// \brief 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     /// \brief 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