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/None.h" 14 #include "llvm/ADT/STLExtras.h" 15 #include "llvm/ADT/SmallVector.h" 16 #include <vector> 17 18 namespace llvm { 19 20 /// ArrayRef - Represent a constant reference to an array (0 or more elements 21 /// consecutively in memory), i.e. a start pointer and a length. It allows 22 /// various APIs to take consecutive elements easily and conveniently. 23 /// 24 /// This class does not own the underlying data, it is expected to be used in 25 /// situations where the data resides in some other buffer, whose lifetime 26 /// extends past that of the ArrayRef. For this reason, it is not in general 27 /// safe to store an ArrayRef. 28 /// 29 /// This is intended to be trivially copyable, so it should be passed by 30 /// value. 31 template<typename T> 32 class ArrayRef { 33 public: 34 typedef const T *iterator; 35 typedef const T *const_iterator; 36 typedef size_t size_type; 37 38 typedef std::reverse_iterator<iterator> reverse_iterator; 39 40 private: 41 /// The start of the array, in an external buffer. 42 const T *Data; 43 44 /// The number of elements. 45 size_type Length; 46 47 /// \brief A dummy "optional" type that is only created by implicit 48 /// conversion from a reference to T. 49 /// 50 /// This type must *only* be used in a function argument or as a copy of 51 /// a function argument, as otherwise it will hold a pointer to a temporary 52 /// past that temporaries' lifetime. 53 struct TRefOrNothing { 54 const T *TPtr; 55 TRefOrNothingTRefOrNothing56 TRefOrNothing() : TPtr(nullptr) {} TRefOrNothingTRefOrNothing57 TRefOrNothing(const T &TRef) : TPtr(&TRef) {} 58 }; 59 60 public: 61 /// @name Constructors 62 /// @{ 63 64 /// Construct an empty ArrayRef. ArrayRef()65 /*implicit*/ ArrayRef() : Data(nullptr), Length(0) {} 66 67 /// Construct an empty ArrayRef from None. ArrayRef(NoneType)68 /*implicit*/ ArrayRef(NoneType) : Data(nullptr), Length(0) {} 69 70 /// Construct an ArrayRef from a single element. ArrayRef(const T & OneElt)71 /*implicit*/ ArrayRef(const T &OneElt) 72 : Data(&OneElt), Length(1) {} 73 74 /// Construct an ArrayRef from a pointer and length. ArrayRef(const T * data,size_t length)75 /*implicit*/ ArrayRef(const T *data, size_t length) 76 : Data(data), Length(length) {} 77 78 /// Construct an ArrayRef from a range. ArrayRef(const T * begin,const T * end)79 ArrayRef(const T *begin, const T *end) 80 : Data(begin), Length(end - begin) {} 81 82 /// Construct an ArrayRef from a SmallVector. This is templated in order to 83 /// avoid instantiating SmallVectorTemplateCommon<T> whenever we 84 /// copy-construct an ArrayRef. 85 template<typename U> ArrayRef(const SmallVectorTemplateCommon<T,U> & Vec)86 /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<T, U> &Vec) 87 : Data(Vec.data()), Length(Vec.size()) { 88 } 89 90 /// Construct an ArrayRef from a std::vector. 91 template<typename A> ArrayRef(const std::vector<T,A> & Vec)92 /*implicit*/ ArrayRef(const std::vector<T, A> &Vec) 93 : Data(Vec.data()), Length(Vec.size()) {} 94 95 /// Construct an ArrayRef from a C array. 96 template <size_t N> ArrayRef(const T (& Arr)[N])97 /*implicit*/ LLVM_CONSTEXPR ArrayRef(const T (&Arr)[N]) 98 : Data(Arr), Length(N) {} 99 100 #if LLVM_HAS_INITIALIZER_LISTS 101 /// Construct an ArrayRef from a std::initializer_list. ArrayRef(const std::initializer_list<T> & Vec)102 /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec) 103 : Data(Vec.begin() == Vec.end() ? (T*)0 : Vec.begin()), 104 Length(Vec.size()) {} 105 #endif 106 107 /// Construct an ArrayRef<const T*> from ArrayRef<T*>. This uses SFINAE to 108 /// ensure that only ArrayRefs of pointers can be converted. 109 template <typename U> 110 ArrayRef(const ArrayRef<U *> &A, 111 typename std::enable_if< 112 std::is_convertible<U *const *, T const *>::value>::type* = 0) 113 : Data(A.data()), Length(A.size()) {} 114 115 /// @} 116 /// @name Simple Operations 117 /// @{ 118 begin()119 iterator begin() const { return Data; } end()120 iterator end() const { return Data + Length; } 121 rbegin()122 reverse_iterator rbegin() const { return reverse_iterator(end()); } rend()123 reverse_iterator rend() const { return reverse_iterator(begin()); } 124 125 /// empty - Check if the array is empty. empty()126 bool empty() const { return Length == 0; } 127 data()128 const T *data() const { return Data; } 129 130 /// size - Get the array size. size()131 size_t size() const { return Length; } 132 133 /// front - Get the first element. front()134 const T &front() const { 135 assert(!empty()); 136 return Data[0]; 137 } 138 139 /// back - Get the last element. back()140 const T &back() const { 141 assert(!empty()); 142 return Data[Length-1]; 143 } 144 145 // copy - Allocate copy in Allocator and return ArrayRef<T> to it. copy(Allocator & A)146 template <typename Allocator> ArrayRef<T> copy(Allocator &A) { 147 T *Buff = A.template Allocate<T>(Length); 148 std::copy(begin(), end(), Buff); 149 return ArrayRef<T>(Buff, Length); 150 } 151 152 /// equals - Check for element-wise equality. equals(ArrayRef RHS)153 bool equals(ArrayRef RHS) const { 154 if (Length != RHS.Length) 155 return false; 156 // Don't use std::equal(), since it asserts in MSVC on nullptr iterators. 157 for (auto L = begin(), LE = end(), R = RHS.begin(); L != LE; ++L, ++R) 158 // Match std::equal() in using == (instead of !=) to minimize API 159 // requirements of ArrayRef'ed types. 160 if (!(*L == *R)) 161 return false; 162 return true; 163 } 164 165 /// slice(n) - Chop off the first N elements of the array. slice(unsigned N)166 ArrayRef<T> slice(unsigned N) const { 167 assert(N <= size() && "Invalid specifier"); 168 return ArrayRef<T>(data()+N, size()-N); 169 } 170 171 /// slice(n, m) - Chop off the first N elements of the array, and keep M 172 /// elements in the array. slice(unsigned N,unsigned M)173 ArrayRef<T> slice(unsigned N, unsigned M) const { 174 assert(N+M <= size() && "Invalid specifier"); 175 return ArrayRef<T>(data()+N, M); 176 } 177 178 // \brief Drop the last \p N elements of the array. 179 ArrayRef<T> drop_back(unsigned N = 1) const { 180 assert(size() >= N && "Dropping more elements than exist"); 181 return slice(0, size() - N); 182 } 183 184 /// @} 185 /// @name Operator Overloads 186 /// @{ 187 const T &operator[](size_t Index) const { 188 assert(Index < Length && "Invalid index!"); 189 return Data[Index]; 190 } 191 192 /// @} 193 /// @name Expensive Operations 194 /// @{ vec()195 std::vector<T> vec() const { 196 return std::vector<T>(Data, Data+Length); 197 } 198 199 /// @} 200 /// @name Conversion operators 201 /// @{ 202 operator std::vector<T>() const { 203 return std::vector<T>(Data, Data+Length); 204 } 205 206 /// @} 207 /// @{ 208 /// @name Convenience methods 209 210 /// @brief Predicate for testing that the array equals the exact sequence of 211 /// arguments. 212 /// 213 /// Will return false if the size is not equal to the exact number of 214 /// arguments given or if the array elements don't equal the argument 215 /// elements in order. Currently supports up to 16 arguments, but can 216 /// easily be extended. 217 bool equals(TRefOrNothing Arg0 = TRefOrNothing(), 218 TRefOrNothing Arg1 = TRefOrNothing(), 219 TRefOrNothing Arg2 = TRefOrNothing(), 220 TRefOrNothing Arg3 = TRefOrNothing(), 221 TRefOrNothing Arg4 = TRefOrNothing(), 222 TRefOrNothing Arg5 = TRefOrNothing(), 223 TRefOrNothing Arg6 = TRefOrNothing(), 224 TRefOrNothing Arg7 = TRefOrNothing(), 225 TRefOrNothing Arg8 = TRefOrNothing(), 226 TRefOrNothing Arg9 = TRefOrNothing(), 227 TRefOrNothing Arg10 = TRefOrNothing(), 228 TRefOrNothing Arg11 = TRefOrNothing(), 229 TRefOrNothing Arg12 = TRefOrNothing(), 230 TRefOrNothing Arg13 = TRefOrNothing(), 231 TRefOrNothing Arg14 = TRefOrNothing(), 232 TRefOrNothing Arg15 = TRefOrNothing()) { 233 TRefOrNothing Args[] = {Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, 234 Arg6, Arg7, Arg8, Arg9, Arg10, Arg11, 235 Arg12, Arg13, Arg14, Arg15}; 236 if (size() > array_lengthof(Args)) 237 return false; 238 239 for (unsigned i = 0, e = size(); i != e; ++i) 240 if (Args[i].TPtr == nullptr || (*this)[i] != *Args[i].TPtr) 241 return false; 242 243 // Either the size is exactly as many args, or the next arg must be null. 244 return size() == array_lengthof(Args) || Args[size()].TPtr == nullptr; 245 } 246 247 /// @} 248 }; 249 250 /// MutableArrayRef - Represent a mutable reference to an array (0 or more 251 /// elements consecutively in memory), i.e. a start pointer and a length. It 252 /// allows various APIs to take and modify consecutive elements easily and 253 /// conveniently. 254 /// 255 /// This class does not own the underlying data, it is expected to be used in 256 /// situations where the data resides in some other buffer, whose lifetime 257 /// extends past that of the MutableArrayRef. For this reason, it is not in 258 /// general safe to store a MutableArrayRef. 259 /// 260 /// This is intended to be trivially copyable, so it should be passed by 261 /// value. 262 template<typename T> 263 class MutableArrayRef : public ArrayRef<T> { 264 public: 265 typedef T *iterator; 266 267 typedef std::reverse_iterator<iterator> reverse_iterator; 268 269 /// Construct an empty MutableArrayRef. MutableArrayRef()270 /*implicit*/ MutableArrayRef() : ArrayRef<T>() {} 271 272 /// Construct an empty MutableArrayRef from None. MutableArrayRef(NoneType)273 /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {} 274 275 /// Construct an MutableArrayRef from a single element. MutableArrayRef(T & OneElt)276 /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {} 277 278 /// Construct an MutableArrayRef from a pointer and length. MutableArrayRef(T * data,size_t length)279 /*implicit*/ MutableArrayRef(T *data, size_t length) 280 : ArrayRef<T>(data, length) {} 281 282 /// Construct an MutableArrayRef from a range. MutableArrayRef(T * begin,T * end)283 MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {} 284 285 /// Construct an MutableArrayRef from a SmallVector. MutableArrayRef(SmallVectorImpl<T> & Vec)286 /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec) 287 : ArrayRef<T>(Vec) {} 288 289 /// Construct a MutableArrayRef from a std::vector. MutableArrayRef(std::vector<T> & Vec)290 /*implicit*/ MutableArrayRef(std::vector<T> &Vec) 291 : ArrayRef<T>(Vec) {} 292 293 /// Construct an MutableArrayRef from a C array. 294 template <size_t N> MutableArrayRef(T (& Arr)[N])295 /*implicit*/ LLVM_CONSTEXPR MutableArrayRef(T (&Arr)[N]) 296 : ArrayRef<T>(Arr) {} 297 data()298 T *data() const { return const_cast<T*>(ArrayRef<T>::data()); } 299 begin()300 iterator begin() const { return data(); } end()301 iterator end() const { return data() + this->size(); } 302 rbegin()303 reverse_iterator rbegin() const { return reverse_iterator(end()); } rend()304 reverse_iterator rend() const { return reverse_iterator(begin()); } 305 306 /// front - Get the first element. front()307 T &front() const { 308 assert(!this->empty()); 309 return data()[0]; 310 } 311 312 /// back - Get the last element. back()313 T &back() const { 314 assert(!this->empty()); 315 return data()[this->size()-1]; 316 } 317 318 /// slice(n) - Chop off the first N elements of the array. slice(unsigned N)319 MutableArrayRef<T> slice(unsigned N) const { 320 assert(N <= this->size() && "Invalid specifier"); 321 return MutableArrayRef<T>(data()+N, this->size()-N); 322 } 323 324 /// slice(n, m) - Chop off the first N elements of the array, and keep M 325 /// elements in the array. slice(unsigned N,unsigned M)326 MutableArrayRef<T> slice(unsigned N, unsigned M) const { 327 assert(N+M <= this->size() && "Invalid specifier"); 328 return MutableArrayRef<T>(data()+N, M); 329 } 330 331 /// @} 332 /// @name Operator Overloads 333 /// @{ 334 T &operator[](size_t Index) const { 335 assert(Index < this->size() && "Invalid index!"); 336 return data()[Index]; 337 } 338 }; 339 340 /// @name ArrayRef Convenience constructors 341 /// @{ 342 343 /// Construct an ArrayRef from a single element. 344 template<typename T> makeArrayRef(const T & OneElt)345 ArrayRef<T> makeArrayRef(const T &OneElt) { 346 return OneElt; 347 } 348 349 /// Construct an ArrayRef from a pointer and length. 350 template<typename T> makeArrayRef(const T * data,size_t length)351 ArrayRef<T> makeArrayRef(const T *data, size_t length) { 352 return ArrayRef<T>(data, length); 353 } 354 355 /// Construct an ArrayRef from a range. 356 template<typename T> makeArrayRef(const T * begin,const T * end)357 ArrayRef<T> makeArrayRef(const T *begin, const T *end) { 358 return ArrayRef<T>(begin, end); 359 } 360 361 /// Construct an ArrayRef from a SmallVector. 362 template <typename T> makeArrayRef(const SmallVectorImpl<T> & Vec)363 ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) { 364 return Vec; 365 } 366 367 /// Construct an ArrayRef from a SmallVector. 368 template <typename T, unsigned N> makeArrayRef(const SmallVector<T,N> & Vec)369 ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) { 370 return Vec; 371 } 372 373 /// Construct an ArrayRef from a std::vector. 374 template<typename T> makeArrayRef(const std::vector<T> & Vec)375 ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) { 376 return Vec; 377 } 378 379 /// Construct an ArrayRef from a C array. 380 template<typename T, size_t N> makeArrayRef(const T (& Arr)[N])381 ArrayRef<T> makeArrayRef(const T (&Arr)[N]) { 382 return ArrayRef<T>(Arr); 383 } 384 385 /// @} 386 /// @name ArrayRef Comparison Operators 387 /// @{ 388 389 template<typename T> 390 inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) { 391 return LHS.equals(RHS); 392 } 393 394 template<typename T> 395 inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) { 396 return !(LHS == RHS); 397 } 398 399 /// @} 400 401 // ArrayRefs can be treated like a POD type. 402 template <typename T> struct isPodLike; 403 template <typename T> struct isPodLike<ArrayRef<T> > { 404 static const bool value = true; 405 }; 406 } 407 408 #endif 409