contrib/llvm/include/llvm/ADT/ArrayRef.h

   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() = default;
 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