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#include "tensorflow/core/lib/gtl/array_slice.h"
17
18#include <algorithm>
19#include <array>
20#include <string>
21#include <vector>
22
23#include "tensorflow/core/lib/gtl/inlined_vector.h"
24#include "tensorflow/core/lib/gtl/stl_util.h"
25#include "tensorflow/core/platform/macros.h"
26#include "tensorflow/core/platform/test.h"
27#include "tensorflow/core/platform/types.h"
28
29namespace tensorflow {
30namespace gtl {
31namespace {
32
33typedef ArraySlice<int> IntSlice;
34typedef ArraySlice<char> CharSlice;
35typedef MutableArraySlice<int> MutableIntSlice;
36typedef MutableArraySlice<char> MutableCharSlice;
37typedef std::vector<int> IntVec;
38
39// Append 0..len-1 to *v
40template <typename Vector>
41static void Fill(Vector* v, int len, int offset = 0) {
42  for (int i = 0; i < len; i++) {
43    v->push_back(i + offset);
44  }
45}
46
47static void TestHelper(const IntSlice& vorig, const IntVec& vec) {
48  IntSlice other;  // To test the assignment return value.
49  IntSlice v = other = vorig;
50  const int len = vec.size();
51  EXPECT_EQ(v.size(), vec.size());
52
53  for (int i = 0; i < len; i++) {
54    EXPECT_EQ(v[i], vec[i]);
55    EXPECT_EQ(v.at(i), vec[i]);
56  }
57  EXPECT_EQ(v.begin(), gtl::vector_as_array(&vec));
58
59  int counter = 0;
60  for (IntSlice::iterator it = v.begin(); it != v.end(); ++it) {
61    EXPECT_EQ(counter, *it);
62    counter++;
63  }
64  EXPECT_EQ(counter, len);
65
66  counter = 0;
67  for (IntSlice::const_iterator it = v.begin(); it != v.end(); ++it) {
68    EXPECT_EQ(counter, *it);
69    counter++;
70  }
71  EXPECT_EQ(counter, len);
72
73  if (len > 0) {
74    EXPECT_EQ(0, v.front());
75    EXPECT_EQ(len - 1, v.back());
76    v.pop_back();
77    EXPECT_EQ(len - 1, v.size());
78    for (size_t i = 0; i < v.size(); ++i) {
79      EXPECT_EQ(i, v[i]);
80    }
81    if (len > 1) {
82      v.pop_front();
83      EXPECT_EQ(len - 2, v.size());
84      for (size_t i = 0; i < v.size(); ++i) {
85        EXPECT_EQ(i + 1, v[i]);
86      }
87    }
88  }
89}
90
91// The element access test that is applicable both when MutableArraySlice is
92// const and when it's not.
93template <class V>
94void MutableTestHelperTemplated(V v, int* ptr, const int len) {
95  CHECK_EQ(v.size(), len);
96
97  for (int i = 0; i < len; i++) {
98    EXPECT_EQ(ptr + i, &v[i]);
99    EXPECT_EQ(ptr + i, &v.at(i));
100  }
101  EXPECT_EQ(ptr, v.begin());
102  EXPECT_EQ(ptr + len, v.end());
103  EXPECT_EQ(ptr, v.data());
104
105  int counter = 0;
106  for (MutableIntSlice::const_iterator it = v.begin(); it != v.end(); ++it) {
107    EXPECT_EQ(ptr + counter, &*it);
108    counter++;
109  }
110  EXPECT_EQ(counter, len);
111
112  EXPECT_EQ(len, std::distance(v.rbegin(), v.rend()));
113
114  if (len > 0) {
115    EXPECT_EQ(ptr, &v.front());
116    EXPECT_EQ(ptr + len - 1, &v.back());
117    EXPECT_EQ(ptr + len - 1, &*v.rbegin());
118    EXPECT_EQ(ptr, &*(v.rend() - 1));
119  }
120}
121
122static void MutableTestHelper(const MutableIntSlice& vorig, int* ptr,
123                              const int len) {
124  // Test the data accessors both when the MutableArraySlice is declared const,
125  // and when it is not.
126  MutableTestHelperTemplated<const MutableIntSlice&>(vorig, ptr, len);
127  MutableTestHelperTemplated<MutableIntSlice>(vorig, ptr, len);
128
129  MutableIntSlice other;  // To test the assignment return value.
130  MutableIntSlice v = other = vorig;
131  EXPECT_EQ(ptr, v.mutable_data());
132
133  int counter = 0;
134  for (MutableIntSlice::iterator it = v.begin(); it != v.end(); ++it) {
135    EXPECT_EQ(ptr + counter, &*it);
136    counter++;
137  }
138  EXPECT_EQ(counter, len);
139
140  if (len > 0) {
141    // Test that elements are assignable.
142    v[0] = 1;
143    v.front() = 2;
144    v.back() = 5;
145    *v.mutable_data() = 4;
146    std::fill(v.begin(), v.end(), 5);
147    std::fill(v.rbegin(), v.rend(), 6);
148    // Test size-changing methods.
149    v.pop_back();
150    EXPECT_EQ(len - 1, v.size());
151    for (size_t i = 0; i < v.size(); ++i) {
152      EXPECT_EQ(ptr + i, &v[i]);
153    }
154    if (len > 1) {
155      v.pop_front();
156      EXPECT_EQ(len - 2, v.size());
157      for (size_t i = 0; i < v.size(); ++i) {
158        EXPECT_EQ(ptr + i + 1, &v[i]);
159      }
160    }
161  }
162}
163
164template <typename Vector>
165static void TestImplicitConversion(const IntSlice& v, const Vector& vec) {
166  EXPECT_EQ(v.size(), vec.size());
167  for (size_t i = 0; i < v.size(); i++) {
168    EXPECT_EQ(v[i], vec[i]);
169  }
170}
171
172template <typename Vector>
173static void TestImplicitConversion(const CharSlice& v, const Vector& vec) {
174  TestImplicitConversion(IntVec(v.begin(), v.end()), vec);
175}
176
177static void TestImplicitConversion(const MutableIntSlice& v, const int* data,
178                                   int size) {
179  EXPECT_EQ(size, v.size());
180  for (size_t i = 0; i < v.size(); i++) {
181    EXPECT_EQ(data + i, &v[i]);
182  }
183}
184
185static void TestImplicitConversion(const MutableCharSlice& v, const char* data,
186                                   int size) {
187  EXPECT_EQ(size, v.size());
188  for (size_t i = 0; i < v.size(); i++) {
189    EXPECT_EQ(data + i, &v[i]);
190  }
191}
192// A struct supplying the data(), mutable_data() and size() methods, just like
193// e.g. proto2::RepeatedField.
194struct RepeatedField {
195  std::vector<int> storage;
196  const int* data() const { return storage.data(); }
197  int* mutable_data() { return storage.data(); }
198  int size() const { return storage.size(); }
199};
200
201// A struct supplying the data() (both mutable and const versions) and
202// size(). It also supplies mutable_data() but we test that data() is selected
203// instead.
204struct ContainerWithOverloads {
205  std::vector<int> storage;
206  std::vector<int> wrong_storage;
207  const int* data() const { return storage.data(); }
208  int* data() { return storage.data(); }
209  // MutableArraySlice should not call mutable_data(), preferring data()
210  // instead.
211  int* mutable_data() { return wrong_storage.data(); }
212  int size() const { return storage.size(); }
213};
214
215// A struct supplying data() and size() methods.
216struct ContainerWithShallowConstData {
217  std::vector<int> storage;
218  int* data() const { return const_cast<int*>(storage.data()); }
219  int size() const { return storage.size(); }
220};
221
222TEST(IntSlice, Simple) {
223  for (int len = 0; len < 20; len++) {
224    IntVec vec;
225    Fill(&vec, len);
226    TestHelper(IntSlice(vec), vec);
227    TestHelper(IntSlice(vec.data(), vec.size()), vec);
228  }
229}
230
231TEST(IntSlice, WithPosAndLen) {
232  IntVec vec;
233  Fill(&vec, 20);
234  for (size_t len = 0; len < vec.size(); len++) {
235    IntVec subvec(vec.begin(), vec.begin() + len);
236    TestImplicitConversion(IntSlice(vec, 0, len), subvec);
237    TestImplicitConversion(IntSlice(IntSlice(vec), 0, len), subvec);
238  }
239  EXPECT_EQ(0, IntSlice(vec, 0, 0).size());
240  EXPECT_EQ(0, IntSlice(IntSlice(vec), 0, 0).size());
241  TestImplicitConversion(IntSlice(vec, 0, IntSlice::npos), vec);
242}
243
244TEST(IntSlice, Clear) {
245  for (int len = 0; len < 20; len++) {
246    IntVec vec;
247    Fill(&vec, len);
248    IntSlice v(vec);
249    v.clear();
250    EXPECT_EQ(0, v.size());
251    EXPECT_EQ(v.begin(), v.end());
252  }
253}
254
255TEST(IntSlice, Swap) {
256  for (int l1 = 0; l1 < 20; l1++) {
257    for (int l2 = 0; l2 < 20; l2++) {
258      IntVec avec, bvec;
259      Fill(&avec, l1);
260      Fill(&bvec, l2, 100);
261      IntSlice a(avec), b(bvec);
262      using std::swap;
263      swap(a, b);
264      EXPECT_EQ(l1, b.size());
265      EXPECT_EQ(l2, a.size());
266      for (int i = 0; i < l1; i++) {
267        EXPECT_EQ(i, b[i]);
268      }
269      for (int i = 0; i < l2; i++) {
270        EXPECT_EQ(100 + i, a[i]);
271      }
272    }
273  }
274}
275
276TEST(IntSlice, ImplicitConversion) {
277  for (int len = 0; len < 20; len++) {
278    IntVec vec;
279    Fill(&vec, len);
280    IntSlice slice;
281    slice = vec;
282    TestImplicitConversion(vec, vec);
283    TestImplicitConversion(slice, vec);
284    TestImplicitConversion(IntSlice(vec.data(), vec.size()), vec);
285  }
286}
287
288TEST(IntSlice, InlinedVectorConversion) {
289  for (int len = 0; len < 20; len++) {
290    InlinedVector<int, 4> inline_vec;
291    for (int i = 0; i < len; i++) {
292      inline_vec.push_back(i);
293    }
294    IntVec vec;
295    Fill(&vec, len);
296    IntSlice v = inline_vec;  // Test assignment
297    static_cast<void>(v);
298    TestImplicitConversion(inline_vec, vec);
299  }
300}
301
302TEST(IntSlice, StaticArrayConversion) {
303  int array[20];
304  IntVec vec;
305  Fill(&vec, TF_ARRAYSIZE(array));
306  std::copy(vec.begin(), vec.end(), array);
307  IntSlice v = array;  // Test assignment
308  static_cast<void>(v);
309  TestImplicitConversion(array, vec);
310}
311
312TEST(IntSlice, StdArrayConversion) {
313  std::array<int, 20> array;
314  IntVec vec;
315  Fill(&vec, array.size());
316  std::copy(vec.begin(), vec.end(), array.begin());
317
318  // Check assignment.
319  {
320    IntSlice v = array;
321    static_cast<void>(v);
322  }
323
324  // Check sub-slice initialization.
325  {
326    IntSlice v = {array, 10, 15};
327    static_cast<void>(v);
328  }
329
330  TestImplicitConversion(array, vec);
331}
332
333// Values according to the Fill function.
334static const int test_const_array[] = {0, 1, 2};
335
336TEST(IntSlice, ConstStaticArrayConversion) {
337  IntVec vec;
338  Fill(&vec, TF_ARRAYSIZE(test_const_array));
339  IntSlice v = test_const_array;  // Test assignment
340  static_cast<void>(v);
341  TestImplicitConversion(test_const_array, vec);
342}
343
344TEST(IntSlice, RepeatedFieldConversion) {
345  RepeatedField repeated_field;
346  IntVec vec;
347  Fill(&vec, 20);
348  repeated_field.storage = vec;
349  IntSlice v = repeated_field;  // Test assignment
350  static_cast<void>(v);
351  TestImplicitConversion(repeated_field, vec);
352}
353
354TEST(IntSlice, ContainerWithOverloadsConversion) {
355  ContainerWithOverloads container;
356  Fill(&container.storage, 20);
357  container.wrong_storage.resize(container.size());
358  IntSlice v = container;  // Test assignment
359  static_cast<void>(v);
360  TestImplicitConversion(container, container.storage);
361}
362
363TEST(IntSlice, ContainerWithShallowConstDataConversion) {
364  ContainerWithShallowConstData container;
365  Fill(&container.storage, 20);
366  IntSlice v = container;  // Test assignment
367  static_cast<void>(v);
368  TestImplicitConversion(container, container.storage);
369}
370
371TEST(IntSlice, MutableIntSliceConversion) {
372  IntVec vec(20);
373  IntSlice slice = MutableIntSlice(&vec);
374  EXPECT_EQ(vec.size(), slice.size());
375  EXPECT_EQ(vec.data(), slice.data());
376}
377
378TEST(IntSlice, Equality) {
379  IntVec vec1(20);
380  IntVec vec2(20);
381  // These two slices are from different vectors, but have the same
382  // size and have the same elements (right now).  They should
383  // compare equal.
384  const IntSlice from1(vec1);
385  const IntSlice from2(vec2);
386  EXPECT_EQ(from1, from1);
387  EXPECT_EQ(from1, from2);
388
389  // This verifies that MutableArraySlices can be compared freely with
390  // ArraySlices.
391  const MutableIntSlice mutable_from1(&vec1);
392  const MutableIntSlice mutable_from2(&vec2);
393  EXPECT_EQ(from1, mutable_from1);
394  EXPECT_EQ(mutable_from1, from1);
395  EXPECT_EQ(mutable_from1, mutable_from2);
396  EXPECT_EQ(mutable_from2, mutable_from1);
397
398  // With a different size, the array slices should not be equal.
399  EXPECT_NE(from1, IntSlice(from1, 0, from1.size() - 1));
400
401  // With different contents, the array slices should not be equal.
402  ++vec2.back();
403  EXPECT_NE(from1, from2);
404}
405
406// Compile-asserts that the argument has the expected type.
407template <typename Expected, typename T>
408void CheckType(const T& value) {
409  ::testing::StaticAssertTypeEq<Expected, T>();
410}
411
412TEST(IntSlice, ExposesContainerTypesAndConsts) {
413  IntSlice slice;
414  const IntSlice const_slice;
415  CheckType<IntSlice::iterator>(slice.begin());
416  CheckType<IntSlice::const_iterator>(const_slice.end());
417  CheckType<IntSlice::const_reverse_iterator>(const_slice.rbegin());
418  CheckType<IntSlice::reverse_iterator>(slice.rend());
419  ::testing::StaticAssertTypeEq<int, IntSlice::value_type>();
420  ::testing::StaticAssertTypeEq<const int*, IntSlice::pointer>();
421  ::testing::StaticAssertTypeEq<const int&, IntSlice::const_reference>();
422  EXPECT_EQ(static_cast<IntSlice::size_type>(-1), IntSlice::npos);
423}
424
425void TestEmpty(IntSlice slice) { ASSERT_TRUE(slice.empty()); }
426
427void TestRange(IntSlice slice, int from, int to) {
428  ASSERT_EQ(to - from + 1, slice.size());
429  for (size_t i = 0; i < slice.size(); ++i) {
430    EXPECT_EQ(from + i, slice[i]);
431  }
432}
433
434TEST(IntSlice, InitializerListConversion) {
435  TestEmpty({});
436  TestRange({1}, 1, 1);
437  TestRange({10, 11, 12, 13}, 10, 13);
438}
439
440TEST(CharSlice, StringConversion) {
441  IntVec vec;
442  Fill(&vec, 20);
443  string str(vec.begin(), vec.end());
444  CharSlice v = str;  // Test assignment
445  static_cast<void>(v);
446  TestImplicitConversion(str, vec);
447}
448
449TEST(IntPtrSlice, ConstConversion) {
450  int one = 1;
451  int two = 2;
452  std::vector<int*> vec;
453  vec.push_back(&one);
454  vec.push_back(&two);
455  ArraySlice<const int*> v = vec;
456  ASSERT_EQ(2, v.size());
457  EXPECT_EQ(&one, v[0]);
458  EXPECT_EQ(&two, v[1]);
459}
460
461TEST(MutableIntSlice, Simple) {
462  for (int len = 0; len < 20; len++) {
463    IntVec vec(len);
464    MutableTestHelper(MutableIntSlice(&vec), vec.data(), len);
465    MutableTestHelper(MutableIntSlice(vec.data(), vec.size()), vec.data(), len);
466  }
467}
468
469TEST(MutableIntSlice, WithPosAndLen) {
470  IntVec vec(20);
471  for (size_t len = 0; len < vec.size(); len++) {
472    TestImplicitConversion(MutableIntSlice(&vec, 0, len), vec.data(), len);
473    TestImplicitConversion(MutableIntSlice(MutableIntSlice(&vec), 0, len),
474                           vec.data(), len);
475  }
476  EXPECT_EQ(0, MutableIntSlice(&vec, 0, 0).size());
477  EXPECT_EQ(0, MutableIntSlice(MutableIntSlice(&vec), 0, 0).size());
478  TestImplicitConversion(MutableIntSlice(&vec, 0, MutableIntSlice::npos),
479                         vec.data(), vec.size());
480}
481
482TEST(MutableIntSlice, Clear) {
483  for (int len = 0; len < 20; len++) {
484    IntVec vec(len);
485    MutableIntSlice v(&vec);
486    v.clear();
487    EXPECT_EQ(0, v.size());
488    EXPECT_EQ(v.begin(), v.end());
489  }
490}
491
492TEST(MutableIntSlice, Swap) {
493  for (int l1 = 0; l1 < 20; l1++) {
494    for (int l2 = 0; l2 < 20; l2++) {
495      IntVec avec(l1), bvec(l2);
496      MutableIntSlice a(&avec), b(&bvec);
497      using std::swap;
498      swap(a, b);
499      EXPECT_EQ(l1, b.size());
500      EXPECT_EQ(l2, a.size());
501      for (int i = 0; i < l1; i++) {
502        EXPECT_EQ(&avec[i], &b[i]);
503      }
504      for (int i = 0; i < l2; i++) {
505        EXPECT_EQ(&bvec[i], &a[i]);
506      }
507    }
508  }
509}
510
511TEST(MutableIntSlice, ImplicitConversion) {
512  for (int len = 0; len < 20; len++) {
513    IntVec vec(len);
514    MutableIntSlice slice;
515    slice = &vec;
516    TestImplicitConversion(&vec, vec.data(), len);
517    TestImplicitConversion(slice, vec.data(), len);
518    TestImplicitConversion(MutableIntSlice(vec.data(), vec.size()), vec.data(),
519                           len);
520  }
521}
522
523TEST(MutableIntSlice, InlinedVectorConversion) {
524  for (int len = 0; len < 20; len++) {
525    InlinedVector<int, 4> inline_vec;
526    for (int i = 0; i < len; i++) {
527      inline_vec.push_back(i);
528    }
529    MutableIntSlice v = &inline_vec;  // Test assignment
530    static_cast<void>(v);
531    TestImplicitConversion(&inline_vec, inline_vec.data(), inline_vec.size());
532  }
533}
534
535TEST(MutableIntSlice, StaticArrayConversion) {
536  int array[20];
537  MutableIntSlice v = array;  // Test assignment
538  static_cast<void>(v);
539  TestImplicitConversion(array, array, TF_ARRAYSIZE(array));
540}
541
542TEST(MutableIntSlice, StdArrayConversion) {
543  std::array<int, 20> array;
544
545  // Check assignment.
546  {
547    MutableIntSlice v = &array;
548    static_cast<void>(v);
549  }
550
551  // Check sub-slice initialization.
552  {
553    MutableIntSlice v = {&array, 10, 15};
554    static_cast<void>(v);
555  }
556
557  TestImplicitConversion(&array, &array[0], array.size());
558}
559
560TEST(MutableIntSlice, RepeatedFieldConversion) {
561  RepeatedField repeated_field;
562  Fill(&repeated_field.storage, 20);
563  MutableIntSlice v = &repeated_field;  // Test assignment
564  static_cast<void>(v);
565  TestImplicitConversion(&repeated_field, repeated_field.storage.data(),
566                         repeated_field.storage.size());
567}
568
569TEST(MutableIntSlice, ContainerWithOverloadsConversion) {
570  ContainerWithOverloads container;
571  Fill(&container.storage, 20);
572  container.wrong_storage.resize(container.size());
573  MutableIntSlice v = &container;  // Test assignment
574  static_cast<void>(v);
575  TestImplicitConversion(&container, container.storage.data(),
576                         container.storage.size());
577}
578
579TEST(MutableIntSlice, ContainerWithShallowConstDataConversion) {
580  ContainerWithShallowConstData container;
581  Fill(&container.storage, 20);
582  MutableIntSlice v = &container;  // Test assignment
583  static_cast<void>(v);
584  TestImplicitConversion(&container, container.storage.data(),
585                         container.storage.size());
586}
587
588TEST(MutableIntSlice, TypedefsAndConstants) {
589  ::testing::StaticAssertTypeEq<int, MutableIntSlice::value_type>();
590  ::testing::StaticAssertTypeEq<int*, MutableIntSlice::pointer>();
591  ::testing::StaticAssertTypeEq<const int*, MutableIntSlice::const_pointer>();
592  ::testing::StaticAssertTypeEq<int&, MutableIntSlice::reference>();
593  ::testing::StaticAssertTypeEq<const int&, MutableIntSlice::const_reference>();
594
595  EXPECT_EQ(static_cast<MutableIntSlice::size_type>(-1), MutableIntSlice::npos);
596}
597
598TEST(MutableIntSlice, IteratorsAndReferences) {
599  auto accept_pointer = [](int* x) {};
600  auto accept_reference = [](int& x) {};
601  auto accept_iterator = [](MutableIntSlice::iterator x) {};
602  auto accept_reverse_iterator = [](MutableIntSlice::reverse_iterator x) {};
603
604  int a[1];
605  MutableIntSlice s = a;
606
607  accept_pointer(s.data());
608  accept_pointer(s.mutable_data());
609  accept_iterator(s.begin());
610  accept_iterator(s.end());
611  accept_reverse_iterator(s.rbegin());
612  accept_reverse_iterator(s.rend());
613
614  accept_reference(s[0]);
615  accept_reference(s.at(0));
616  accept_reference(s.front());
617  accept_reference(s.back());
618}
619
620TEST(MutableIntSlice, IteratorsAndReferences_Const) {
621  auto accept_pointer = [](int* x) {};
622  auto accept_reference = [](int& x) {};
623  auto accept_iterator = [](MutableIntSlice::iterator x) {};
624  auto accept_reverse_iterator = [](MutableIntSlice::reverse_iterator x) {};
625
626  int a[1];
627  const MutableIntSlice s = a;
628
629  accept_pointer(s.data());
630  accept_pointer(s.mutable_data());
631  accept_iterator(s.begin());
632  accept_iterator(s.end());
633  accept_reverse_iterator(s.rbegin());
634  accept_reverse_iterator(s.rend());
635
636  accept_reference(s[0]);
637  accept_reference(s.at(0));
638  accept_reference(s.front());
639  accept_reference(s.back());
640}
641
642bool TestMutableOverload(MutableIntSlice slice) { return false; }
643
644bool TestMutableOverload(MutableCharSlice slice) { return true; }
645
646TEST(MutableCharSlice, StringConversion) {
647  for (int len = 0; len < 20; len++) {
648    string str(len, '\0');
649    MutableCharSlice v = &str;  // Test assignment
650    static_cast<void>(v);
651    TestImplicitConversion(v, str.data(), str.size());
652  }
653  // Verify that only the correct overload is feasible. Note that this would
654  // fail if the string ctor was declared simply as MutableArraySlice(string*),
655  // since in that case both overloads would be feasible.
656  string str;
657  EXPECT_TRUE(TestMutableOverload(&str));
658
659  // Avoid warning "unused function 'TestMutableOverload'"
660  int a[1];
661  EXPECT_FALSE(TestMutableOverload(a));
662}
663
664}  // namespace
665}  // namespace gtl
666}  // namespace tensorflow
667