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. ArrayRef(NoneType)70 /*implicit*/ ArrayRef(NoneType) {} 71 72 /// Construct an ArrayRef from a single element. ArrayRef(const T & OneElt)73 /*implicit*/ ArrayRef(const T &OneElt) 74 : Data(&OneElt), Length(1) {} 75 76 /// Construct an ArrayRef from a pointer and length. ArrayRef(const T * data,size_t length)77 /*implicit*/ ArrayRef(const T *data, size_t length) 78 : Data(data), Length(length) {} 79 80 /// Construct an ArrayRef from a range. ArrayRef(const T * begin,const T * end)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> ArrayRef(const SmallVectorTemplateCommon<T,U> & Vec)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> ArrayRef(const std::vector<T,A> & Vec)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> ArrayRef(const std::array<T,N> & Arr)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> ArrayRef(const T (& Arr)[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 ArrayRef(const std::initializer_list<T> & Vec)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 * = 0) 145 : Data(Vec.data()), Length(Vec.size()) {} 146 147 /// @} 148 /// @name Simple Operations 149 /// @{ 150 begin()151 iterator begin() const { return Data; } end()152 iterator end() const { return Data + Length; } 153 rbegin()154 reverse_iterator rbegin() const { return reverse_iterator(end()); } rend()155 reverse_iterator rend() const { return reverse_iterator(begin()); } 156 157 /// empty - Check if the array is empty. empty()158 bool empty() const { return Length == 0; } 159 data()160 const T *data() const { return Data; } 161 162 /// size - Get the array size. size()163 size_t size() const { return Length; } 164 165 /// front - Get the first element. front()166 const T &front() const { 167 assert(!empty()); 168 return Data[0]; 169 } 170 171 /// back - Get the last element. back()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. copy(Allocator & A)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. equals(ArrayRef RHS)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. slice(size_t N,size_t M)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. slice(size_t N)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. drop_while(PredicateT Pred)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. drop_until(PredicateT Pred)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. take_while(PredicateT Pred)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. take_until(PredicateT Pred)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 /// @{ vec()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. MutableArrayRef(NoneType)323 /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {} 324 325 /// Construct a MutableArrayRef from a single element. MutableArrayRef(T & OneElt)326 /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {} 327 328 /// Construct a MutableArrayRef from a pointer and length. MutableArrayRef(T * data,size_t length)329 /*implicit*/ MutableArrayRef(T *data, size_t length) 330 : ArrayRef<T>(data, length) {} 331 332 /// Construct a MutableArrayRef from a range. MutableArrayRef(T * begin,T * end)333 MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {} 334 335 /// Construct a MutableArrayRef from a SmallVector. MutableArrayRef(SmallVectorImpl<T> & Vec)336 /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec) 337 : ArrayRef<T>(Vec) {} 338 339 /// Construct a MutableArrayRef from a std::vector. MutableArrayRef(std::vector<T> & Vec)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> MutableArrayRef(std::array<T,N> & Arr)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> MutableArrayRef(T (& Arr)[N])350 /*implicit*/ constexpr MutableArrayRef(T (&Arr)[N]) : ArrayRef<T>(Arr) {} 351 data()352 T *data() const { return const_cast<T*>(ArrayRef<T>::data()); } 353 begin()354 iterator begin() const { return data(); } end()355 iterator end() const { return data() + this->size(); } 356 rbegin()357 reverse_iterator rbegin() const { return reverse_iterator(end()); } rend()358 reverse_iterator rend() const { return reverse_iterator(begin()); } 359 360 /// front - Get the first element. front()361 T &front() const { 362 assert(!this->empty()); 363 return data()[0]; 364 } 365 366 /// back - Get the last element. back()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. slice(size_t N,size_t M)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. slice(size_t N)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> drop_while(PredicateT Pred)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> drop_until(PredicateT Pred)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> take_while(PredicateT Pred)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> take_until(PredicateT Pred)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; OwningArrayRef(size_t Size)450 OwningArrayRef(size_t Size) : MutableArrayRef<T>(new T[Size], Size) {} 451 OwningArrayRef(ArrayRef<T> Data)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 OwningArrayRef(OwningArrayRef && Other)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 ~OwningArrayRef()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> makeArrayRef(const T & OneElt)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> makeArrayRef(const T * data,size_t length)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> makeArrayRef(const T * begin,const T * end)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> makeArrayRef(const SmallVectorImpl<T> & Vec)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> makeArrayRef(const SmallVector<T,N> & Vec)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> makeArrayRef(const std::vector<T> & Vec)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> makeArrayRef(const std::array<T,N> & Arr)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) makeArrayRef(const ArrayRef<T> & Vec)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) makeArrayRef(ArrayRef<T> & Vec)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> makeArrayRef(const T (& Arr)[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> makeMutableArrayRef(T & OneElt)532 MutableArrayRef<T> makeMutableArrayRef(T &OneElt) { 533 return OneElt; 534 } 535 536 /// Construct a MutableArrayRef from a pointer and length. 537 template<typename T> makeMutableArrayRef(T * data,size_t length)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 hash_value(ArrayRef<T> S)568 template <typename T> hash_code hash_value(ArrayRef<T> S) { 569 return hash_combine_range(S.begin(), S.end()); 570 } 571 572 } // end namespace llvm 573 574 #endif // LLVM_ADT_ARRAYREF_H 575