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