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  /// ArrayRef - Represent a constant reference to an array (0 or more elements
20  /// consecutively in memory), i.e. a start pointer and a length.  It allows
21  /// various APIs to take consecutive elements easily and conveniently.
22  ///
23  /// This class does not own the underlying data, it is expected to be used in
24  /// situations where the data resides in some other buffer, whose lifetime
25  /// extends past that of the ArrayRef. For this reason, it is not in general
26  /// safe to store an ArrayRef.
27  ///
28  /// This is intended to be trivially copyable, so it should be passed by
29  /// value.
30  template<typename T>
31  class ArrayRef {
32  public:
33    typedef const T *iterator;
34    typedef const T *const_iterator;
35    typedef size_t size_type;
36
37    typedef std::reverse_iterator<iterator> reverse_iterator;
38
39  private:
40    /// The start of the array, in an external buffer.
41    const T *Data;
42
43    /// The number of elements.
44    size_type Length;
45
46  public:
47    /// @name Constructors
48    /// @{
49
50    /// Construct an empty ArrayRef.
51    /*implicit*/ ArrayRef() : Data(nullptr), Length(0) {}
52
53    /// Construct an empty ArrayRef from None.
54    /*implicit*/ ArrayRef(NoneType) : Data(nullptr), Length(0) {}
55
56    /// Construct an ArrayRef from a single element.
57    /*implicit*/ ArrayRef(const T &OneElt)
58      : Data(&OneElt), Length(1) {}
59
60    /// Construct an ArrayRef from a pointer and length.
61    /*implicit*/ ArrayRef(const T *data, size_t length)
62      : Data(data), Length(length) {}
63
64    /// Construct an ArrayRef from a range.
65    ArrayRef(const T *begin, const T *end)
66      : Data(begin), Length(end - begin) {}
67
68    /// Construct an ArrayRef from a SmallVector. This is templated in order to
69    /// avoid instantiating SmallVectorTemplateCommon<T> whenever we
70    /// copy-construct an ArrayRef.
71    template<typename U>
72    /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<T, U> &Vec)
73      : Data(Vec.data()), Length(Vec.size()) {
74    }
75
76    /// Construct an ArrayRef from a std::vector.
77    template<typename A>
78    /*implicit*/ ArrayRef(const std::vector<T, A> &Vec)
79      : Data(Vec.data()), Length(Vec.size()) {}
80
81    /// Construct an ArrayRef from a C array.
82    template <size_t N>
83    /*implicit*/ LLVM_CONSTEXPR ArrayRef(const T (&Arr)[N])
84      : Data(Arr), Length(N) {}
85
86    /// Construct an ArrayRef from a std::initializer_list.
87    /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec)
88    : Data(Vec.begin() == Vec.end() ? (T*)nullptr : Vec.begin()),
89      Length(Vec.size()) {}
90
91    /// Construct an ArrayRef<const T*> from ArrayRef<T*>. This uses SFINAE to
92    /// ensure that only ArrayRefs of pointers can be converted.
93    template <typename U>
94    ArrayRef(
95        const ArrayRef<U *> &A,
96        typename std::enable_if<
97           std::is_convertible<U *const *, T const *>::value>::type * = nullptr)
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(
105      const SmallVectorTemplateCommon<U *, DummyT> &Vec,
106      typename std::enable_if<
107          std::is_convertible<U *const *, T const *>::value>::type * = nullptr)
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(size_t 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(size_t N, size_t M) const {
172      assert(N+M <= size() && "Invalid specifier");
173      return ArrayRef<T>(data()+N, M);
174    }
175
176    /// \brief Drop the first \p N elements of the array.
177    ArrayRef<T> drop_front(size_t N = 1) const {
178      assert(size() >= N && "Dropping more elements than exist");
179      return slice(N, size() - N);
180    }
181
182    /// \brief Drop the last \p N elements of the array.
183    ArrayRef<T> drop_back(size_t N = 1) const {
184      assert(size() >= N && "Dropping more elements than exist");
185      return slice(0, size() - N);
186    }
187
188    /// @}
189    /// @name Operator Overloads
190    /// @{
191    const T &operator[](size_t Index) const {
192      assert(Index < Length && "Invalid index!");
193      return Data[Index];
194    }
195
196    /// @}
197    /// @name Expensive Operations
198    /// @{
199    std::vector<T> vec() const {
200      return std::vector<T>(Data, Data+Length);
201    }
202
203    /// @}
204    /// @name Conversion operators
205    /// @{
206    operator std::vector<T>() const {
207      return std::vector<T>(Data, Data+Length);
208    }
209
210    /// @}
211  };
212
213  /// MutableArrayRef - Represent a mutable reference to an array (0 or more
214  /// elements consecutively in memory), i.e. a start pointer and a length.  It
215  /// allows various APIs to take and modify consecutive elements easily and
216  /// conveniently.
217  ///
218  /// This class does not own the underlying data, it is expected to be used in
219  /// situations where the data resides in some other buffer, whose lifetime
220  /// extends past that of the MutableArrayRef. For this reason, it is not in
221  /// general safe to store a MutableArrayRef.
222  ///
223  /// This is intended to be trivially copyable, so it should be passed by
224  /// value.
225  template<typename T>
226  class MutableArrayRef : public ArrayRef<T> {
227  public:
228    typedef T *iterator;
229
230    typedef std::reverse_iterator<iterator> reverse_iterator;
231
232    /// Construct an empty MutableArrayRef.
233    /*implicit*/ MutableArrayRef() : ArrayRef<T>() {}
234
235    /// Construct an empty MutableArrayRef from None.
236    /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {}
237
238    /// Construct an MutableArrayRef from a single element.
239    /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {}
240
241    /// Construct an MutableArrayRef from a pointer and length.
242    /*implicit*/ MutableArrayRef(T *data, size_t length)
243      : ArrayRef<T>(data, length) {}
244
245    /// Construct an MutableArrayRef from a range.
246    MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {}
247
248    /// Construct an MutableArrayRef from a SmallVector.
249    /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec)
250    : ArrayRef<T>(Vec) {}
251
252    /// Construct a MutableArrayRef from a std::vector.
253    /*implicit*/ MutableArrayRef(std::vector<T> &Vec)
254    : ArrayRef<T>(Vec) {}
255
256    /// Construct an MutableArrayRef from a C array.
257    template <size_t N>
258    /*implicit*/ LLVM_CONSTEXPR MutableArrayRef(T (&Arr)[N])
259      : ArrayRef<T>(Arr) {}
260
261    T *data() const { return const_cast<T*>(ArrayRef<T>::data()); }
262
263    iterator begin() const { return data(); }
264    iterator end() const { return data() + this->size(); }
265
266    reverse_iterator rbegin() const { return reverse_iterator(end()); }
267    reverse_iterator rend() const { return reverse_iterator(begin()); }
268
269    /// front - Get the first element.
270    T &front() const {
271      assert(!this->empty());
272      return data()[0];
273    }
274
275    /// back - Get the last element.
276    T &back() const {
277      assert(!this->empty());
278      return data()[this->size()-1];
279    }
280
281    /// slice(n) - Chop off the first N elements of the array.
282    MutableArrayRef<T> slice(size_t N) const {
283      assert(N <= this->size() && "Invalid specifier");
284      return MutableArrayRef<T>(data()+N, this->size()-N);
285    }
286
287    /// slice(n, m) - Chop off the first N elements of the array, and keep M
288    /// elements in the array.
289    MutableArrayRef<T> slice(size_t N, size_t M) const {
290      assert(N+M <= this->size() && "Invalid specifier");
291      return MutableArrayRef<T>(data()+N, M);
292    }
293
294    /// \brief Drop the first \p N elements of the array.
295    MutableArrayRef<T> drop_front(size_t N = 1) const {
296      assert(this->size() >= N && "Dropping more elements than exist");
297      return slice(N, this->size() - N);
298    }
299
300    MutableArrayRef<T> drop_back(size_t N = 1) const {
301      assert(this->size() >= N && "Dropping more elements than exist");
302      return slice(0, this->size() - N);
303    }
304
305    /// @}
306    /// @name Operator Overloads
307    /// @{
308    T &operator[](size_t Index) const {
309      assert(Index < this->size() && "Invalid index!");
310      return data()[Index];
311    }
312  };
313
314  /// @name ArrayRef Convenience constructors
315  /// @{
316
317  /// Construct an ArrayRef from a single element.
318  template<typename T>
319  ArrayRef<T> makeArrayRef(const T &OneElt) {
320    return OneElt;
321  }
322
323  /// Construct an ArrayRef from a pointer and length.
324  template<typename T>
325  ArrayRef<T> makeArrayRef(const T *data, size_t length) {
326    return ArrayRef<T>(data, length);
327  }
328
329  /// Construct an ArrayRef from a range.
330  template<typename T>
331  ArrayRef<T> makeArrayRef(const T *begin, const T *end) {
332    return ArrayRef<T>(begin, end);
333  }
334
335  /// Construct an ArrayRef from a SmallVector.
336  template <typename T>
337  ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) {
338    return Vec;
339  }
340
341  /// Construct an ArrayRef from a SmallVector.
342  template <typename T, unsigned N>
343  ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) {
344    return Vec;
345  }
346
347  /// Construct an ArrayRef from a std::vector.
348  template<typename T>
349  ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) {
350    return Vec;
351  }
352
353  /// Construct an ArrayRef from an ArrayRef (no-op) (const)
354  template <typename T> ArrayRef<T> makeArrayRef(const ArrayRef<T> &Vec) {
355    return Vec;
356  }
357
358  /// Construct an ArrayRef from an ArrayRef (no-op)
359  template <typename T> ArrayRef<T> &makeArrayRef(ArrayRef<T> &Vec) {
360    return Vec;
361  }
362
363  /// Construct an ArrayRef from a C array.
364  template<typename T, size_t N>
365  ArrayRef<T> makeArrayRef(const T (&Arr)[N]) {
366    return ArrayRef<T>(Arr);
367  }
368
369  /// @}
370  /// @name ArrayRef Comparison Operators
371  /// @{
372
373  template<typename T>
374  inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) {
375    return LHS.equals(RHS);
376  }
377
378  template<typename T>
379  inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) {
380    return !(LHS == RHS);
381  }
382
383  /// @}
384
385  // ArrayRefs can be treated like a POD type.
386  template <typename T> struct isPodLike;
387  template <typename T> struct isPodLike<ArrayRef<T> > {
388    static const bool value = true;
389  };
390
391  template <typename T> hash_code hash_value(ArrayRef<T> S) {
392    return hash_combine_range(S.begin(), S.end());
393  }
394} // end namespace llvm
395
396#endif // LLVM_ADT_ARRAYREF_H
397