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/Hashing.h"
14#include "llvm/ADT/None.h"
15#include "llvm/ADT/SmallVector.h"
16#include <vector>
17
18namespace 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  public:
48    /// @name Constructors
49    /// @{
50
51    /// Construct an empty ArrayRef.
52    /*implicit*/ ArrayRef() : Data(nullptr), Length(0) {}
53
54    /// Construct an empty ArrayRef from None.
55    /*implicit*/ ArrayRef(NoneType) : Data(nullptr), Length(0) {}
56
57    /// Construct an ArrayRef from a single element.
58    /*implicit*/ ArrayRef(const T &OneElt)
59      : Data(&OneElt), Length(1) {}
60
61    /// Construct an ArrayRef from a pointer and length.
62    /*implicit*/ ArrayRef(const T *data, size_t length)
63      : Data(data), Length(length) {}
64
65    /// Construct an ArrayRef from a range.
66    ArrayRef(const T *begin, const T *end)
67      : Data(begin), Length(end - begin) {}
68
69    /// Construct an ArrayRef from a SmallVector. This is templated in order to
70    /// avoid instantiating SmallVectorTemplateCommon<T> whenever we
71    /// copy-construct an ArrayRef.
72    template<typename U>
73    /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<T, U> &Vec)
74      : Data(Vec.data()), Length(Vec.size()) {
75    }
76
77    /// Construct an ArrayRef from a std::vector.
78    template<typename A>
79    /*implicit*/ ArrayRef(const std::vector<T, A> &Vec)
80      : Data(Vec.data()), Length(Vec.size()) {}
81
82    /// Construct an ArrayRef from a C array.
83    template <size_t N>
84    /*implicit*/ LLVM_CONSTEXPR ArrayRef(const T (&Arr)[N])
85      : Data(Arr), Length(N) {}
86
87    /// Construct an ArrayRef from a std::initializer_list.
88    /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec)
89    : Data(Vec.begin() == Vec.end() ? (T*)nullptr : Vec.begin()),
90      Length(Vec.size()) {}
91
92    /// Construct an ArrayRef<const T*> from ArrayRef<T*>. This uses SFINAE to
93    /// ensure that only ArrayRefs of pointers can be converted.
94    template <typename U>
95    ArrayRef(const ArrayRef<U *> &A,
96             typename std::enable_if<
97                 std::is_convertible<U *const *, T const *>::value>::type* = 0)
98      : Data(A.data()), Length(A.size()) {}
99
100    /// Construct an ArrayRef<const T*> from a SmallVector<T*>. This is
101    /// templated in order to avoid instantiating SmallVectorTemplateCommon<T>
102    /// whenever we copy-construct an ArrayRef.
103    template<typename U, typename DummyT>
104    /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<U*, DummyT> &Vec,
105                          typename std::enable_if<
106                              std::is_convertible<U *const *,
107                                                  T const *>::value>::type* = 0)
108      : Data(Vec.data()), Length(Vec.size()) {
109    }
110
111    /// Construct an ArrayRef<const T*> from std::vector<T*>. This uses SFINAE
112    /// to ensure that only vectors of pointers can be converted.
113    template<typename U, typename A>
114    ArrayRef(const std::vector<U *, A> &Vec,
115             typename std::enable_if<
116                 std::is_convertible<U *const *, T const *>::value>::type* = 0)
117      : Data(Vec.data()), Length(Vec.size()) {}
118
119    /// @}
120    /// @name Simple Operations
121    /// @{
122
123    iterator begin() const { return Data; }
124    iterator end() const { return Data + Length; }
125
126    reverse_iterator rbegin() const { return reverse_iterator(end()); }
127    reverse_iterator rend() const { return reverse_iterator(begin()); }
128
129    /// empty - Check if the array is empty.
130    bool empty() const { return Length == 0; }
131
132    const T *data() const { return Data; }
133
134    /// size - Get the array size.
135    size_t size() const { return Length; }
136
137    /// front - Get the first element.
138    const T &front() const {
139      assert(!empty());
140      return Data[0];
141    }
142
143    /// back - Get the last element.
144    const T &back() const {
145      assert(!empty());
146      return Data[Length-1];
147    }
148
149    // copy - Allocate copy in Allocator and return ArrayRef<T> to it.
150    template <typename Allocator> ArrayRef<T> copy(Allocator &A) {
151      T *Buff = A.template Allocate<T>(Length);
152      std::uninitialized_copy(begin(), end(), Buff);
153      return ArrayRef<T>(Buff, Length);
154    }
155
156    /// equals - Check for element-wise equality.
157    bool equals(ArrayRef RHS) const {
158      if (Length != RHS.Length)
159        return false;
160      return std::equal(begin(), end(), RHS.begin());
161    }
162
163    /// slice(n) - Chop off the first N elements of the array.
164    ArrayRef<T> slice(unsigned N) const {
165      assert(N <= size() && "Invalid specifier");
166      return ArrayRef<T>(data()+N, size()-N);
167    }
168
169    /// slice(n, m) - Chop off the first N elements of the array, and keep M
170    /// elements in the array.
171    ArrayRef<T> slice(unsigned N, unsigned M) const {
172      assert(N+M <= size() && "Invalid specifier");
173      return ArrayRef<T>(data()+N, M);
174    }
175
176    // \brief Drop the last \p N elements of the array.
177    ArrayRef<T> drop_back(unsigned N = 1) const {
178      assert(size() >= N && "Dropping more elements than exist");
179      return slice(0, size() - N);
180    }
181
182    /// @}
183    /// @name Operator Overloads
184    /// @{
185    const T &operator[](size_t Index) const {
186      assert(Index < Length && "Invalid index!");
187      return Data[Index];
188    }
189
190    /// @}
191    /// @name Expensive Operations
192    /// @{
193    std::vector<T> vec() const {
194      return std::vector<T>(Data, Data+Length);
195    }
196
197    /// @}
198    /// @name Conversion operators
199    /// @{
200    operator std::vector<T>() const {
201      return std::vector<T>(Data, Data+Length);
202    }
203
204    /// @}
205  };
206
207  /// MutableArrayRef - Represent a mutable reference to an array (0 or more
208  /// elements consecutively in memory), i.e. a start pointer and a length.  It
209  /// allows various APIs to take and modify consecutive elements easily and
210  /// conveniently.
211  ///
212  /// This class does not own the underlying data, it is expected to be used in
213  /// situations where the data resides in some other buffer, whose lifetime
214  /// extends past that of the MutableArrayRef. For this reason, it is not in
215  /// general safe to store a MutableArrayRef.
216  ///
217  /// This is intended to be trivially copyable, so it should be passed by
218  /// value.
219  template<typename T>
220  class MutableArrayRef : public ArrayRef<T> {
221  public:
222    typedef T *iterator;
223
224    typedef std::reverse_iterator<iterator> reverse_iterator;
225
226    /// Construct an empty MutableArrayRef.
227    /*implicit*/ MutableArrayRef() : ArrayRef<T>() {}
228
229    /// Construct an empty MutableArrayRef from None.
230    /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {}
231
232    /// Construct an MutableArrayRef from a single element.
233    /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {}
234
235    /// Construct an MutableArrayRef from a pointer and length.
236    /*implicit*/ MutableArrayRef(T *data, size_t length)
237      : ArrayRef<T>(data, length) {}
238
239    /// Construct an MutableArrayRef from a range.
240    MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {}
241
242    /// Construct an MutableArrayRef from a SmallVector.
243    /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec)
244    : ArrayRef<T>(Vec) {}
245
246    /// Construct a MutableArrayRef from a std::vector.
247    /*implicit*/ MutableArrayRef(std::vector<T> &Vec)
248    : ArrayRef<T>(Vec) {}
249
250    /// Construct an MutableArrayRef from a C array.
251    template <size_t N>
252    /*implicit*/ LLVM_CONSTEXPR MutableArrayRef(T (&Arr)[N])
253      : ArrayRef<T>(Arr) {}
254
255    T *data() const { return const_cast<T*>(ArrayRef<T>::data()); }
256
257    iterator begin() const { return data(); }
258    iterator end() const { return data() + this->size(); }
259
260    reverse_iterator rbegin() const { return reverse_iterator(end()); }
261    reverse_iterator rend() const { return reverse_iterator(begin()); }
262
263    /// front - Get the first element.
264    T &front() const {
265      assert(!this->empty());
266      return data()[0];
267    }
268
269    /// back - Get the last element.
270    T &back() const {
271      assert(!this->empty());
272      return data()[this->size()-1];
273    }
274
275    /// slice(n) - Chop off the first N elements of the array.
276    MutableArrayRef<T> slice(unsigned N) const {
277      assert(N <= this->size() && "Invalid specifier");
278      return MutableArrayRef<T>(data()+N, this->size()-N);
279    }
280
281    /// slice(n, m) - Chop off the first N elements of the array, and keep M
282    /// elements in the array.
283    MutableArrayRef<T> slice(unsigned N, unsigned M) const {
284      assert(N+M <= this->size() && "Invalid specifier");
285      return MutableArrayRef<T>(data()+N, M);
286    }
287
288    MutableArrayRef<T> drop_back(unsigned N) const {
289      assert(this->size() >= N && "Dropping more elements than exist");
290      return slice(0, this->size() - N);
291    }
292
293    /// @}
294    /// @name Operator Overloads
295    /// @{
296    T &operator[](size_t Index) const {
297      assert(Index < this->size() && "Invalid index!");
298      return data()[Index];
299    }
300  };
301
302  /// @name ArrayRef Convenience constructors
303  /// @{
304
305  /// Construct an ArrayRef from a single element.
306  template<typename T>
307  ArrayRef<T> makeArrayRef(const T &OneElt) {
308    return OneElt;
309  }
310
311  /// Construct an ArrayRef from a pointer and length.
312  template<typename T>
313  ArrayRef<T> makeArrayRef(const T *data, size_t length) {
314    return ArrayRef<T>(data, length);
315  }
316
317  /// Construct an ArrayRef from a range.
318  template<typename T>
319  ArrayRef<T> makeArrayRef(const T *begin, const T *end) {
320    return ArrayRef<T>(begin, end);
321  }
322
323  /// Construct an ArrayRef from a SmallVector.
324  template <typename T>
325  ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) {
326    return Vec;
327  }
328
329  /// Construct an ArrayRef from a SmallVector.
330  template <typename T, unsigned N>
331  ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) {
332    return Vec;
333  }
334
335  /// Construct an ArrayRef from a std::vector.
336  template<typename T>
337  ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) {
338    return Vec;
339  }
340
341  /// Construct an ArrayRef from an ArrayRef (no-op) (const)
342  template <typename T> ArrayRef<T> makeArrayRef(const ArrayRef<T> &Vec) {
343    return Vec;
344  }
345
346  /// Construct an ArrayRef from an ArrayRef (no-op)
347  template <typename T> ArrayRef<T> &makeArrayRef(ArrayRef<T> &Vec) {
348    return Vec;
349  }
350
351  /// Construct an ArrayRef from a C array.
352  template<typename T, size_t N>
353  ArrayRef<T> makeArrayRef(const T (&Arr)[N]) {
354    return ArrayRef<T>(Arr);
355  }
356
357  /// @}
358  /// @name ArrayRef Comparison Operators
359  /// @{
360
361  template<typename T>
362  inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) {
363    return LHS.equals(RHS);
364  }
365
366  template<typename T>
367  inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) {
368    return !(LHS == RHS);
369  }
370
371  /// @}
372
373  // ArrayRefs can be treated like a POD type.
374  template <typename T> struct isPodLike;
375  template <typename T> struct isPodLike<ArrayRef<T> > {
376    static const bool value = true;
377  };
378
379  template <typename T> hash_code hash_value(ArrayRef<T> S) {
380    return hash_combine_range(S.begin(), S.end());
381  }
382}
383
384#endif
385