//===- ArrayRef.h - Array Reference Wrapper ---------------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_ARRAYREF_H #define LLVM_ADT_ARRAYREF_H #include "llvm/ADT/Hashing.h" #include "llvm/ADT/None.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Support/Compiler.h" #include #include #include #include #include #include #include #include #include namespace llvm { /// ArrayRef - Represent a constant reference to an array (0 or more elements /// consecutively in memory), i.e. a start pointer and a length. It allows /// various APIs to take consecutive elements easily and conveniently. /// /// This class does not own the underlying data, it is expected to be used in /// situations where the data resides in some other buffer, whose lifetime /// extends past that of the ArrayRef. For this reason, it is not in general /// safe to store an ArrayRef. /// /// This is intended to be trivially copyable, so it should be passed by /// value. template class LLVM_NODISCARD ArrayRef { public: using iterator = const T *; using const_iterator = const T *; using size_type = size_t; using reverse_iterator = std::reverse_iterator; private: /// The start of the array, in an external buffer. const T *Data = nullptr; /// The number of elements. size_type Length = 0; public: /// @name Constructors /// @{ /// Construct an empty ArrayRef. /*implicit*/ ArrayRef() = default; /// Construct an empty ArrayRef from None. /*implicit*/ ArrayRef(NoneType) {} /// Construct an ArrayRef from a single element. /*implicit*/ ArrayRef(const T &OneElt) : Data(&OneElt), Length(1) {} /// Construct an ArrayRef from a pointer and length. /*implicit*/ ArrayRef(const T *data, size_t length) : Data(data), Length(length) {} /// Construct an ArrayRef from a range. ArrayRef(const T *begin, const T *end) : Data(begin), Length(end - begin) {} /// Construct an ArrayRef from a SmallVector. This is templated in order to /// avoid instantiating SmallVectorTemplateCommon whenever we /// copy-construct an ArrayRef. template /*implicit*/ ArrayRef(const SmallVectorTemplateCommon &Vec) : Data(Vec.data()), Length(Vec.size()) { } /// Construct an ArrayRef from a std::vector. template /*implicit*/ ArrayRef(const std::vector &Vec) : Data(Vec.data()), Length(Vec.size()) {} /// Construct an ArrayRef from a std::array template /*implicit*/ constexpr ArrayRef(const std::array &Arr) : Data(Arr.data()), Length(N) {} /// Construct an ArrayRef from a C array. template /*implicit*/ constexpr ArrayRef(const T (&Arr)[N]) : Data(Arr), Length(N) {} /// Construct an ArrayRef from a std::initializer_list. /*implicit*/ ArrayRef(const std::initializer_list &Vec) : Data(Vec.begin() == Vec.end() ? (T*)nullptr : Vec.begin()), Length(Vec.size()) {} /// Construct an ArrayRef from ArrayRef. This uses SFINAE to /// ensure that only ArrayRefs of pointers can be converted. template ArrayRef( const ArrayRef &A, typename std::enable_if< std::is_convertible::value>::type * = nullptr) : Data(A.data()), Length(A.size()) {} /// Construct an ArrayRef from a SmallVector. This is /// templated in order to avoid instantiating SmallVectorTemplateCommon /// whenever we copy-construct an ArrayRef. template /*implicit*/ ArrayRef( const SmallVectorTemplateCommon &Vec, typename std::enable_if< std::is_convertible::value>::type * = nullptr) : Data(Vec.data()), Length(Vec.size()) { } /// Construct an ArrayRef from std::vector. This uses SFINAE /// to ensure that only vectors of pointers can be converted. template ArrayRef(const std::vector &Vec, typename std::enable_if< std::is_convertible::value>::type* = 0) : Data(Vec.data()), Length(Vec.size()) {} /// @} /// @name Simple Operations /// @{ iterator begin() const { return Data; } iterator end() const { return Data + Length; } reverse_iterator rbegin() const { return reverse_iterator(end()); } reverse_iterator rend() const { return reverse_iterator(begin()); } /// empty - Check if the array is empty. bool empty() const { return Length == 0; } const T *data() const { return Data; } /// size - Get the array size. size_t size() const { return Length; } /// front - Get the first element. const T &front() const { assert(!empty()); return Data[0]; } /// back - Get the last element. const T &back() const { assert(!empty()); return Data[Length-1]; } // copy - Allocate copy in Allocator and return ArrayRef to it. template ArrayRef copy(Allocator &A) { T *Buff = A.template Allocate(Length); std::uninitialized_copy(begin(), end(), Buff); return ArrayRef(Buff, Length); } /// equals - Check for element-wise equality. bool equals(ArrayRef RHS) const { if (Length != RHS.Length) return false; return std::equal(begin(), end(), RHS.begin()); } /// slice(n, m) - Chop off the first N elements of the array, and keep M /// elements in the array. ArrayRef slice(size_t N, size_t M) const { assert(N+M <= size() && "Invalid specifier"); return ArrayRef(data()+N, M); } /// slice(n) - Chop off the first N elements of the array. ArrayRef slice(size_t N) const { return slice(N, size() - N); } /// Drop the first \p N elements of the array. ArrayRef drop_front(size_t N = 1) const { assert(size() >= N && "Dropping more elements than exist"); return slice(N, size() - N); } /// Drop the last \p N elements of the array. ArrayRef drop_back(size_t N = 1) const { assert(size() >= N && "Dropping more elements than exist"); return slice(0, size() - N); } /// Return a copy of *this with the first N elements satisfying the /// given predicate removed. template ArrayRef drop_while(PredicateT Pred) const { return ArrayRef(find_if_not(*this, Pred), end()); } /// Return a copy of *this with the first N elements not satisfying /// the given predicate removed. template ArrayRef drop_until(PredicateT Pred) const { return ArrayRef(find_if(*this, Pred), end()); } /// Return a copy of *this with only the first \p N elements. ArrayRef take_front(size_t N = 1) const { if (N >= size()) return *this; return drop_back(size() - N); } /// Return a copy of *this with only the last \p N elements. ArrayRef take_back(size_t N = 1) const { if (N >= size()) return *this; return drop_front(size() - N); } /// Return the first N elements of this Array that satisfy the given /// predicate. template ArrayRef take_while(PredicateT Pred) const { return ArrayRef(begin(), find_if_not(*this, Pred)); } /// Return the first N elements of this Array that don't satisfy the /// given predicate. template ArrayRef take_until(PredicateT Pred) const { return ArrayRef(begin(), find_if(*this, Pred)); } /// @} /// @name Operator Overloads /// @{ const T &operator[](size_t Index) const { assert(Index < Length && "Invalid index!"); return Data[Index]; } /// Disallow accidental assignment from a temporary. /// /// The declaration here is extra complicated so that "arrayRef = {}" /// continues to select the move assignment operator. template typename std::enable_if::value, ArrayRef>::type & operator=(U &&Temporary) = delete; /// Disallow accidental assignment from a temporary. /// /// The declaration here is extra complicated so that "arrayRef = {}" /// continues to select the move assignment operator. template typename std::enable_if::value, ArrayRef>::type & operator=(std::initializer_list) = delete; /// @} /// @name Expensive Operations /// @{ std::vector vec() const { return std::vector(Data, Data+Length); } /// @} /// @name Conversion operators /// @{ operator std::vector() const { return std::vector(Data, Data+Length); } /// @} }; /// MutableArrayRef - Represent a mutable reference to an array (0 or more /// elements consecutively in memory), i.e. a start pointer and a length. It /// allows various APIs to take and modify consecutive elements easily and /// conveniently. /// /// This class does not own the underlying data, it is expected to be used in /// situations where the data resides in some other buffer, whose lifetime /// extends past that of the MutableArrayRef. For this reason, it is not in /// general safe to store a MutableArrayRef. /// /// This is intended to be trivially copyable, so it should be passed by /// value. template class LLVM_NODISCARD MutableArrayRef : public ArrayRef { public: using iterator = T *; using reverse_iterator = std::reverse_iterator; /// Construct an empty MutableArrayRef. /*implicit*/ MutableArrayRef() = default; /// Construct an empty MutableArrayRef from None. /*implicit*/ MutableArrayRef(NoneType) : ArrayRef() {} /// Construct an MutableArrayRef from a single element. /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef(OneElt) {} /// Construct an MutableArrayRef from a pointer and length. /*implicit*/ MutableArrayRef(T *data, size_t length) : ArrayRef(data, length) {} /// Construct an MutableArrayRef from a range. MutableArrayRef(T *begin, T *end) : ArrayRef(begin, end) {} /// Construct an MutableArrayRef from a SmallVector. /*implicit*/ MutableArrayRef(SmallVectorImpl &Vec) : ArrayRef(Vec) {} /// Construct a MutableArrayRef from a std::vector. /*implicit*/ MutableArrayRef(std::vector &Vec) : ArrayRef(Vec) {} /// Construct an ArrayRef from a std::array template /*implicit*/ constexpr MutableArrayRef(std::array &Arr) : ArrayRef(Arr) {} /// Construct an MutableArrayRef from a C array. template /*implicit*/ constexpr MutableArrayRef(T (&Arr)[N]) : ArrayRef(Arr) {} T *data() const { return const_cast(ArrayRef::data()); } iterator begin() const { return data(); } iterator end() const { return data() + this->size(); } reverse_iterator rbegin() const { return reverse_iterator(end()); } reverse_iterator rend() const { return reverse_iterator(begin()); } /// front - Get the first element. T &front() const { assert(!this->empty()); return data()[0]; } /// back - Get the last element. T &back() const { assert(!this->empty()); return data()[this->size()-1]; } /// slice(n, m) - Chop off the first N elements of the array, and keep M /// elements in the array. MutableArrayRef slice(size_t N, size_t M) const { assert(N + M <= this->size() && "Invalid specifier"); return MutableArrayRef(this->data() + N, M); } /// slice(n) - Chop off the first N elements of the array. MutableArrayRef slice(size_t N) const { return slice(N, this->size() - N); } /// Drop the first \p N elements of the array. MutableArrayRef drop_front(size_t N = 1) const { assert(this->size() >= N && "Dropping more elements than exist"); return slice(N, this->size() - N); } MutableArrayRef drop_back(size_t N = 1) const { assert(this->size() >= N && "Dropping more elements than exist"); return slice(0, this->size() - N); } /// Return a copy of *this with the first N elements satisfying the /// given predicate removed. template MutableArrayRef drop_while(PredicateT Pred) const { return MutableArrayRef(find_if_not(*this, Pred), end()); } /// Return a copy of *this with the first N elements not satisfying /// the given predicate removed. template MutableArrayRef drop_until(PredicateT Pred) const { return MutableArrayRef(find_if(*this, Pred), end()); } /// Return a copy of *this with only the first \p N elements. MutableArrayRef take_front(size_t N = 1) const { if (N >= this->size()) return *this; return drop_back(this->size() - N); } /// Return a copy of *this with only the last \p N elements. MutableArrayRef take_back(size_t N = 1) const { if (N >= this->size()) return *this; return drop_front(this->size() - N); } /// Return the first N elements of this Array that satisfy the given /// predicate. template MutableArrayRef take_while(PredicateT Pred) const { return MutableArrayRef(begin(), find_if_not(*this, Pred)); } /// Return the first N elements of this Array that don't satisfy the /// given predicate. template MutableArrayRef take_until(PredicateT Pred) const { return MutableArrayRef(begin(), find_if(*this, Pred)); } /// @} /// @name Operator Overloads /// @{ T &operator[](size_t Index) const { assert(Index < this->size() && "Invalid index!"); return data()[Index]; } }; /// This is a MutableArrayRef that owns its array. template class OwningArrayRef : public MutableArrayRef { public: OwningArrayRef() = default; OwningArrayRef(size_t Size) : MutableArrayRef(new T[Size], Size) {} OwningArrayRef(ArrayRef Data) : MutableArrayRef(new T[Data.size()], Data.size()) { std::copy(Data.begin(), Data.end(), this->begin()); } OwningArrayRef(OwningArrayRef &&Other) { *this = std::move(Other); } OwningArrayRef &operator=(OwningArrayRef &&Other) { delete[] this->data(); this->MutableArrayRef::operator=(Other); Other.MutableArrayRef::operator=(MutableArrayRef()); return *this; } ~OwningArrayRef() { delete[] this->data(); } }; /// @name ArrayRef Convenience constructors /// @{ /// Construct an ArrayRef from a single element. template ArrayRef makeArrayRef(const T &OneElt) { return OneElt; } /// Construct an ArrayRef from a pointer and length. template ArrayRef makeArrayRef(const T *data, size_t length) { return ArrayRef(data, length); } /// Construct an ArrayRef from a range. template ArrayRef makeArrayRef(const T *begin, const T *end) { return ArrayRef(begin, end); } /// Construct an ArrayRef from a SmallVector. template ArrayRef makeArrayRef(const SmallVectorImpl &Vec) { return Vec; } /// Construct an ArrayRef from a SmallVector. template ArrayRef makeArrayRef(const SmallVector &Vec) { return Vec; } /// Construct an ArrayRef from a std::vector. template ArrayRef makeArrayRef(const std::vector &Vec) { return Vec; } /// Construct an ArrayRef from a std::array. template ArrayRef makeArrayRef(const std::array &Arr) { return Arr; } /// Construct an ArrayRef from an ArrayRef (no-op) (const) template ArrayRef makeArrayRef(const ArrayRef &Vec) { return Vec; } /// Construct an ArrayRef from an ArrayRef (no-op) template ArrayRef &makeArrayRef(ArrayRef &Vec) { return Vec; } /// Construct an ArrayRef from a C array. template ArrayRef makeArrayRef(const T (&Arr)[N]) { return ArrayRef(Arr); } /// Construct a MutableArrayRef from a single element. template MutableArrayRef makeMutableArrayRef(T &OneElt) { return OneElt; } /// Construct a MutableArrayRef from a pointer and length. template MutableArrayRef makeMutableArrayRef(T *data, size_t length) { return MutableArrayRef(data, length); } /// @} /// @name ArrayRef Comparison Operators /// @{ template inline bool operator==(ArrayRef LHS, ArrayRef RHS) { return LHS.equals(RHS); } template inline bool operator!=(ArrayRef LHS, ArrayRef RHS) { return !(LHS == RHS); } /// @} template hash_code hash_value(ArrayRef S) { return hash_combine_range(S.begin(), S.end()); } } // end namespace llvm #endif // LLVM_ADT_ARRAYREF_H