unittests/CoreTests/RangeTest.cpp

   1 //===- lld/unittest/RangeTest.cpp -----------------------------------------===//
   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 /// \file
  11 /// \brief range.h unit tests.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "gtest/gtest.h"
  16 #include "lld/Core/range.h"
  17 #include <array>
  18 #include <assert.h>
  19 #include <deque>
  20 #include <forward_list>
  21 #include <iterator>
  22 #include <list>
  23 #include <numeric>
  24 #include <sstream>
  25 #include <vector>
  26
  27 template <typename T, typename U> struct AssertTypesSame;
  28 template <typename T> struct AssertTypesSame<T, T> {};
  29 #define ASSERT_TYPES_SAME(T, U) AssertTypesSame<T, U>()
  30
  31 struct no_begin {};
  32 struct member_begin {
  33   int *begin();
  34 };
  35 struct free_begin {};
  36 int *begin(free_begin);
  37
  38 template <typename T>
  39 auto type_of_forward(T &&t) -> decltype(std::forward<T>(t)) {
  40   return std::forward<T>(t);
  41 }
  42
  43 template <typename To> To implicit_cast(To val) { return val; }
  44
  45 void test_traits() {
  46   using namespace lld::detail;
  47   ASSERT_TYPES_SAME(begin_result<no_begin>::type, undefined);
  48   // This causes clang to segfault.
  49 #if 0
  50   ASSERT_TYPES_SAME(
  51       begin_result<decltype(type_of_forward(member_begin()))>::type, int *);
  52 #endif
  53   ASSERT_TYPES_SAME(begin_result<free_begin>::type, int *);
  54 }
  55
  56 TEST(Range, constructors) {
  57   std::vector<int> v(5);
  58   std::iota(v.begin(), v.end(), 0);
  59   lld::range<std::vector<int>::iterator> r = v;
  60   EXPECT_EQ(v.begin(), r.begin());
  61   EXPECT_EQ(v.end(), r.end());
  62
  63   int arr[] = { 1, 2, 3, 4, 5 };
  64   std::begin(arr);
  65   lld::range<int *> r2 = arr;
  66   EXPECT_EQ(5, r2.back());
  67 }
  68
  69 TEST(Range, conversion_to_pointer_range) {
  70   std::vector<int> v(5);
  71   std::iota(v.begin(), v.end(), 0);
  72   lld::range<int *> r = v;
  73   EXPECT_EQ(&*v.begin(), r.begin());
  74   EXPECT_EQ(2, r[2]);
  75 }
  76
  77 template <typename Iter> void takes_range(lld::range<Iter> r) {
  78   int expected = 0;
  79   for (int val : r) {
  80     EXPECT_EQ(expected++, val);
  81   }
  82 }
  83
  84 void takes_ptr_range(lld::range<const int *> r) {
  85   int expected = 0;
  86   for (int val : r) {
  87     EXPECT_EQ(expected++, val);
  88   }
  89 }
  90
  91 TEST(Range, passing) {
  92   using lld::make_range;
  93   using lld::make_ptr_range;
  94   std::list<int> l(5);
  95   std::iota(l.begin(), l.end(), 0);
  96   takes_range(make_range(l));
  97   takes_range(make_range(implicit_cast<const std::list<int> &>(l)));
  98   std::deque<int> d(5);
  99   std::iota(d.begin(), d.end(), 0);
 100   takes_range(make_range(d));
 101   takes_range(make_range(implicit_cast<const std::deque<int> &>(d)));
 102   std::vector<int> v(5);
 103   std::iota(v.begin(), v.end(), 0);
 104   takes_range(make_range(v));
 105   takes_range(make_range(implicit_cast<const std::vector<int> &>(v)));
 106   static_assert(
 107       std::is_same<decltype(make_ptr_range(v)), lld::range<int *>>::value,
 108       "make_ptr_range should return a range of pointers");
 109   takes_range(make_ptr_range(v));
 110   takes_range(make_ptr_range(implicit_cast<const std::vector<int> &>(v)));
 111   int arr[] = { 0, 1, 2, 3, 4 };
 112   takes_range(make_range(arr));
 113   const int carr[] = { 0, 1, 2, 3, 4 };
 114   takes_range(make_range(carr));
 115
 116   takes_ptr_range(v);
 117   takes_ptr_range(implicit_cast<const std::vector<int> &>(v));
 118   takes_ptr_range(arr);
 119   takes_ptr_range(carr);
 120 }
 121
 122 TEST(Range, access) {
 123   std::array<int, 5> a = { { 1, 2, 3, 4, 5 } };
 124   lld::range<decltype(a.begin())> r = a;
 125   EXPECT_EQ(4, r[3]);
 126   EXPECT_EQ(4, r[-2]);
 127 }
 128
 129 template <bool b> struct CompileAssert;
 130 template <> struct CompileAssert<true> {};
 131
 132 #if __has_feature(cxx_constexpr)
 133 constexpr int arr[] = { 1, 2, 3, 4, 5 };
 134 TEST(Range, constexpr) {
 135   constexpr lld::range<const int *> r(arr, arr + 5);
 136   CompileAssert<r.front() == 1>();
 137   CompileAssert<r.size() == 5>();
 138   CompileAssert<r[4] == 5>();
 139 }
 140 #endif
 141
 142 template <typename Container> void test_slice() {
 143   Container cont(10);
 144   std::iota(cont.begin(), cont.end(), 0);
 145   lld::range<decltype(cont.begin())> r = cont;
 146
 147   // One argument.
 148   EXPECT_EQ(10, r.slice(0).size());
 149   EXPECT_EQ(8, r.slice(2).size());
 150   EXPECT_EQ(2, r.slice(2).front());
 151   EXPECT_EQ(1, r.slice(-1).size());
 152   EXPECT_EQ(9, r.slice(-1).front());
 153
 154   // Two positive arguments.
 155   EXPECT_TRUE(r.slice(5, 2).empty());
 156   EXPECT_EQ(next(cont.begin(), 5), r.slice(5, 2).begin());
 157   EXPECT_EQ(1, r.slice(1, 2).size());
 158   EXPECT_EQ(1, r.slice(1, 2).front());
 159
 160   // Two negative arguments.
 161   EXPECT_TRUE(r.slice(-2, -5).empty());
 162   EXPECT_EQ(next(cont.begin(), 8), r.slice(-2, -5).begin());
 163   EXPECT_EQ(1, r.slice(-2, -1).size());
 164   EXPECT_EQ(8, r.slice(-2, -1).front());
 165
 166   // Positive start, negative stop.
 167   EXPECT_EQ(1, r.slice(6, -3).size());
 168   EXPECT_EQ(6, r.slice(6, -3).front());
 169   EXPECT_TRUE(r.slice(6, -5).empty());
 170   EXPECT_EQ(next(cont.begin(), 6), r.slice(6, -5).begin());
 171
 172   // Negative start, positive stop.
 173   EXPECT_TRUE(r.slice(-3, 6).empty());
 174   EXPECT_EQ(next(cont.begin(), 7), r.slice(-3, 6).begin());
 175   EXPECT_EQ(1, r.slice(-5, 6).size());
 176   EXPECT_EQ(5, r.slice(-5, 6).front());
 177 }
 178
 179 TEST(Range, slice) {
 180   // -fsanitize=undefined complains about this, but only if optimizations are
 181   // enabled.
 182 #if 0
 183   test_slice<std::forward_list<int>>();
 184 #endif
 185   test_slice<std::list<int>>();
 186 // This doesn't build with libstdc++ 4.7
 187 #if 0
 188   test_slice<std::deque<int>>();
 189 #endif
 190 }
 191
 192 // This test is flaky and I've yet to pin down why. Changing between
 193 // EXPECT_EQ(1, input.front()) and EXPECT_TRUE(input.front() == 1) makes it work
 194 // with VS 2012 in Debug mode. Clang on Linux seems to fail with -03 and -02 -g
 195 // -fsanitize=undefined.
 196 #if 0
 197 TEST(Range, istream_range) {
 198   std::istringstream stream("1 2 3 4 5");
 199   // MSVC interprets input as a function declaration if you don't declare start
 200   // and instead directly pass std::istream_iterator<int>(stream).
 201   auto start = std::istream_iterator<int>(stream);
 202   lld::range<std::istream_iterator<int>> input(
 203       start, std::istream_iterator<int>());
 204   EXPECT_TRUE(input.front() == 1);
 205   input.pop_front();
 206   EXPECT_TRUE(input.front() == 2);
 207   input.pop_front(2);
 208   EXPECT_TRUE(input.front() == 4);
 209   input.pop_front_upto(7);
 210   EXPECT_TRUE(input.empty());
 211 }
 212 #endif
 213
 214 //! [algorithm using range]
 215 template <typename T> void partial_sum(T &container) {
 216   using lld::make_range;
 217   auto range = make_range(container);
 218   typename T::value_type sum = 0;
 219   // One would actually use a range-based for loop
 220   // in this case, but you get the idea:
 221   for (; !range.empty(); range.pop_front()) {
 222     sum += range.front();
 223     range.front() = sum;
 224   }
 225 }
 226
 227 TEST(Range, user1) {
 228   std::vector<int> v(5, 2);
 229   partial_sum(v);
 230   EXPECT_EQ(8, v[3]);
 231 }
 232 //! [algorithm using range]
 233
 234 //! [algorithm using ptr_range]
 235 void my_write(int fd, lld::range<const char *> buffer) {}
 236
 237 TEST(Range, user2) {
 238   std::string s("Hello world");
 239   my_write(1, s);
 240 }