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