1/* Copyright 2015 The TensorFlow Authors. All Rights Reserved.
2
3Licensed under the Apache License, Version 2.0 (the "License");
4you may not use this file except in compliance with the License.
5You may obtain a copy of the License at
6
7    http://www.apache.org/licenses/LICENSE-2.0
8
9Unless required by applicable law or agreed to in writing, software
10distributed under the License is distributed on an "AS IS" BASIS,
11WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12See the License for the specific language governing permissions and
13limitations under the License.
14==============================================================================*/
15
16// NOT FOR INCLUSION BY CLIENT CODE. This file is only to be included by
17// array_slice.h.
18
19// Helper functions and templates for ArraySlice.
20
21#ifndef TENSORFLOW_LIB_GTL_ARRAY_SLICE_INTERNAL_H_
22#define TENSORFLOW_LIB_GTL_ARRAY_SLICE_INTERNAL_H_
23
24#include <stddef.h>
25#include <algorithm>
26#include <iterator>
27#include <memory>
28#include <string>
29#include <type_traits>
30#include <utility>
31#include <vector>
32#include "tensorflow/core/platform/logging.h"
33
34namespace tensorflow {
35namespace gtl {
36namespace array_slice_internal {
37
38// Template logic for generic constructors.
39
40// Wrappers whose Get() delegates to the appropriate method of a container, and
41// is defined when this method exists. Delegates to the const method if C is a
42// const type.
43struct Data {
44  template <typename C>
45  static decltype(std::declval<C>().data()) Get(C* v) {
46    return v->data();
47  }
48};
49
50struct MutableData {
51  template <typename C>
52  static decltype(std::declval<C>().mutable_data()) Get(C* v) {
53    return v->mutable_data();
54  }
55};
56
57struct Size {
58  template <typename C>
59  static decltype(std::declval<C>().size()) Get(C* v) {
60    return v->size();
61  }
62};
63
64struct MutableStringData {
65  // Defined only for string.
66  static char* Get(string* v) { return v->empty() ? nullptr : &*v->begin(); }
67};
68
69// Checks whether M::Get(C*) is defined and has a return type R such that
70// Checker::valid<R>()==true.
71template <typename M, typename Checker, typename C>
72struct HasGetHelper : public M {
73 private:
74  struct None {};
75  // M::Get is selected when it is viable. Get(...) is selected otherwise.
76  using M::Get;
77  static None Get(...);
78
79 public:
80  static constexpr bool HasGet() {
81    using Result = decltype(Get(std::declval<C*>()));
82    return !std::is_same<Result, None>() && Checker::template valid<Result>();
83  }
84};
85
86// Defines HasGet() for a particular method, container, and checker. If
87// HasGet()==true, provides Get() that delegates to the method.
88template <typename M, typename Checker, typename C,
89          bool /*has_get*/ = HasGetHelper<M, Checker, C>::HasGet()>
90struct Wrapper {
91  static constexpr bool HasGet() { return false; }
92};
93
94template <typename M, typename Checker, typename C>
95struct Wrapper<M, Checker, C, true> {
96  static constexpr bool HasGet() { return true; }
97  static decltype(M::Get(std::declval<C*>())) Get(C* v) { return M::Get(v); }
98};
99
100// Type checker for a method returning an integral value.
101struct SizeChecker {
102  template <typename R>
103  static constexpr bool valid() {
104    return std::is_integral<R>::value;
105  }
106};
107
108// Type checker for a method returning either a pointer to T or a less const
109// version of that.
110template <typename T>
111struct DataChecker {
112  // We want to enable conversion from std::vector<T*> to ArraySlice<const T*>
113  // but
114  // disable conversion from std::vector<Derived> to ArraySlice<Base>. Here we
115  // use
116  // the fact that U** is convertible to Q* const* if and only if Q is the same
117  // type or a more cv-qualified version of U.
118  template <typename R>
119  static constexpr bool valid() {
120    return std::is_convertible<R*, T* const*>::value;
121  }
122};
123
124// Aliases to A if A::HasGet()==true, or to B otherwise.
125template <typename A, typename B>
126using FirstWithGet = typename std::conditional<A::HasGet(), A, B>::type;
127
128// Wraps C::data() const, returning a pointer to const data.
129template <typename T, typename C>
130using ContainerData = Wrapper<Data, DataChecker<const T>, const C>;
131
132// Wraps a method returning a pointer to mutable data. Prefers data() over
133// mutable_data(), and handles strings when T==char. If data() returns a pointer
134// to mutable data, it is most likely overloaded, but may also be a single
135// method 'T* C::data() const' in a non-STL-compliant container.
136template <typename T, typename C>
137using ContainerMutableData =
138    FirstWithGet<Wrapper<Data, DataChecker<T>, C>,
139                 FirstWithGet<Wrapper<MutableData, DataChecker<T>, C>,
140                              Wrapper<MutableStringData, DataChecker<T>, C>>>;
141
142// Wraps C::size() const.
143template <typename C>
144using ContainerSize = Wrapper<Size, SizeChecker, const C>;
145
146// Implementation class for ArraySlice and MutableArraySlice. In the case of
147// ArraySlice, T will be a const type; for MutableArraySlice, T will be a
148// mutable type.
149template <typename T>
150class ArraySliceImplBase {
151 public:
152  typedef T* pointer;
153  typedef const T* const_pointer;
154  typedef T& reference;
155  typedef const T& const_reference;
156  typedef pointer iterator;
157  typedef const_pointer const_iterator;
158  typedef std::reverse_iterator<iterator> reverse_iterator;
159  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
160  typedef size_t size_type;
161  typedef ptrdiff_t difference_type;
162
163  static const size_type npos = static_cast<size_type>(-1);
164
165  ArraySliceImplBase(pointer array, size_type length)
166      : ptr_(array), length_(length) {}
167
168  // Substring of another ArraySlice.
169  // pos must be non-negative and <= x.length().
170  // len must be non-negative and will be pinned to at most x.length() - pos.
171  ArraySliceImplBase(const ArraySliceImplBase& x, size_type pos, size_type len)
172      : ptr_(x.ptr_ + pos), length_(std::min(x.length_ - pos, len)) {}
173
174  // Some of the const methods below return pointers and references to mutable
175  // data. This is only the case in this internal class; ArraySlice and
176  // MutableArraySlice provide deep-constness.
177
178  pointer data() const { return ptr_; }
179  size_type size() const { return length_; }
180
181  void clear() {
182    ptr_ = nullptr;
183    length_ = 0;
184  }
185
186  reference operator[](size_type i) const { return ptr_[i]; }
187  reference at(size_type i) const {
188    DCHECK_LT(i, length_);
189    return ptr_[i];
190  }
191  reference front() const {
192    DCHECK_GT(length_, 0);
193    return ptr_[0];
194  }
195  reference back() const {
196    DCHECK_GT(length_, 0);
197    return ptr_[length_ - 1];
198  }
199
200  void remove_prefix(size_type n) {
201    DCHECK_GE(length_, n);
202    ptr_ += n;
203    length_ -= n;
204  }
205  void remove_suffix(size_type n) {
206    DCHECK_GE(length_, n);
207    length_ -= n;
208  }
209
210  iterator begin() const { return ptr_; }
211  iterator end() const { return ptr_ + length_; }
212  reverse_iterator rbegin() const { return reverse_iterator(end()); }
213  reverse_iterator rend() const { return reverse_iterator(begin()); }
214
215  bool operator==(const ArraySliceImplBase& other) const {
216    if (size() != other.size()) return false;
217    if (data() == other.data()) return true;
218    return std::equal(data(), data() + size(), other.data());
219  }
220  bool operator!=(const ArraySliceImplBase& other) const {
221    return !(*this == other);
222  }
223
224 private:
225  pointer ptr_;
226  size_type length_;
227};
228
229template <typename T>
230class ArraySliceImpl : public ArraySliceImplBase<const T> {
231 public:
232  using ArraySliceImplBase<const T>::ArraySliceImplBase;
233
234  // Defined iff the data and size accessors for the container C have been
235  // defined.
236  template <typename C>
237  using EnableIfConvertibleFrom =
238      typename std::enable_if<ContainerData<T, C>::HasGet() &&
239                              ContainerSize<C>::HasGet()>::type;
240
241  // Constructs from a container when EnableIfConvertibleFrom is
242  // defined. std::addressof handles types with overloaded operator&.
243  template <typename C>
244  explicit ArraySliceImpl(const C& v)
245      : ArraySliceImplBase<const T>(ContainerData<T, C>::Get(std::addressof(v)),
246                                    ContainerSize<C>::Get(std::addressof(v))) {}
247};
248
249template <typename T>
250class MutableArraySliceImpl : public ArraySliceImplBase<T> {
251 public:
252  using ArraySliceImplBase<T>::ArraySliceImplBase;
253
254  template <typename C>
255  using EnableIfConvertibleFrom =
256      typename std::enable_if<ContainerMutableData<T, C>::HasGet() &&
257                              ContainerSize<C>::HasGet()>::type;
258
259  template <typename C>
260  explicit MutableArraySliceImpl(C* v)
261      : ArraySliceImplBase<T>(ContainerMutableData<T, C>::Get(v),
262                              ContainerSize<C>::Get(v)) {}
263};
264
265}  // namespace array_slice_internal
266}  // namespace gtl
267}  // namespace tensorflow
268
269#endif  // TENSORFLOW_LIB_GTL_ARRAY_SLICE_INTERNAL_H_
270