[libcxx] Properly convert the count arguments to the *_n algorithms before use.

[EricWF]

Summary

The requirement on the Size type passed to *_n algorithms is that it is convertible to an integral type. This means we can't use a variable of type Size directly. Instead we need to convert it to an integral type first. The problem is finding out what integral type to convert it to. __convert_to_integral figures out what integral type to convert it to and performs the conversion, It also promotes the resulting integral type so that it is at least as big as an integer. __convert_to_integral also has a special case for converting enums. This should only work on non-scoped enumerations because it does not apply an explicit conversion from the enum to its underlying type.

[mclow.lists]

A few nits; but in general, this looks fine to me

include/algorithm

1675 ↗

(On Diff #19435)

I don't think you need a _VSTD:: in front of __convert_to_integral, since it's not a legal identifier, so people can't define their own.

include/type_traits

3663 ↗

(On Diff #19435)

Do you need cases for signed char and unsigned char ?

test/libcxx/type_traits/convert_to_integral.pass.cpp

73 ↗

(On Diff #19435)

As long as you're modifying this file, please add a newline at the end.

test/std/algorithms/alg.modifying.operations/alg.copy/copy_n.pass.cpp

21 ↗

(On Diff #19435)

Rather than having this IntegralConvertible in several source files, should it go into test/support?

(suggestion, not requirement)

[EricWF]

Address @mclow.lists comments.

[EricWF]

Add inline comments.

include/algorithm

1675 ↗

(On Diff #19435)

Acknowledged.

include/type_traits

3663 ↗

(On Diff #19435)

I thought you might if char was signed char and you wanted to convert unsigned char x = -1; but it actually seems you don't need the char overload at all.

I've updated the tests to check the conversion of both the min and max values for each type and I've removed the char overload.

test/libcxx/type_traits/convert_to_integral.pass.cpp

73 ↗

(On Diff #19435)

Acknowledged.

test/std/algorithms/alg.modifying.operations/alg.copy/copy_n.pass.cpp

21 ↗

(On Diff #19435)

Acknowledged.

[mclow.lists]

LGTM

libcxx/trunk/include/algorithm

 
 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
 inline _LIBCPP_INLINE_VISIBILITY
 _ForwardIterator
 search_n(_ForwardIterator __first, _ForwardIterator __last,
          _Size __count, const _Tp& __value_, _BinaryPredicate __pred)
 {
     return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
-           (__first, __last, __count, __value_, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
+           (__first, __last, __convert_to_integral(__count), __value_, __pred,
+           typename iterator_traits<_ForwardIterator>::iterator_category());
 }
 
 template <class _ForwardIterator, class _Size, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY
 _ForwardIterator
 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
 {
     typedef typename iterator_traits<_ForwardIterator>::value_type __v;
-    return _VSTD::search_n(__first, __last, __count, __value_, __equal_to<__v, _Tp>());
+    return _VSTD::search_n(__first, __last, __convert_to_integral(__count),
+                           __value_, __equal_to<__v, _Tp>());
 }
 
 // copy
 
 template <class _Iter>
 struct __libcpp_is_trivial_iterator
 {
     static const bool value = is_pointer<_Iter>::value;

 template<class _InputIterator, class _Size, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 typename enable_if
 <
     __is_input_iterator<_InputIterator>::value &&
    !__is_random_access_iterator<_InputIterator>::value,
     _OutputIterator
 >::type
-copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
+copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
 {
+    typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
+    _IntegralSize __n = __orig_n;
     if (__n > 0)
     {
         *__result = *__first;
         ++__result;
         for (--__n; __n > 0; --__n)
         {
             ++__first;
             *__result = *__first;
             ++__result;
         }
     }
     return __result;
 }
 
 template<class _InputIterator, class _Size, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 typename enable_if
 <
     __is_random_access_iterator<_InputIterator>::value,
     _OutputIterator
 >::type
-copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
+copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
 {
+    typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
+    _IntegralSize __n = __orig_n;
     return _VSTD::copy(__first, __first + __n, __result);
 }
 
 // move
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
__fill_n(_Tp* __first, _Size __n,_Up __value_)
     return __first + __n;
 }
 
 template <class _OutputIterator, class _Size, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
 {
-   return _VSTD::__fill_n(__first, __n, __value_);
+   return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);
 }
 
 // fill
 
 template <class _ForwardIterator, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
for (; __first != __last; ++__first)
         *__first = __gen();
 }
 
 // generate_n
 
 template <class _OutputIterator, class _Size, class _Generator>
 inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
-generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
+generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
 {
+    typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
+    _IntegralSize __n = __orig_n;
     for (; __n > 0; ++__first, (void) --__n)
         *__first = __gen();
     return __first;
 }
 
 // remove
 
 template <class _ForwardIterator, class _Tp>

libcxx/trunk/include/type_traits

 {
     static_assert(_Support, "The underyling_type trait requires compiler "
                             "support. Either no such support exists or "
                             "libc++ does not know how to use it.");
 };
 
 #endif // _LIBCPP_UNDERLYING_TYPE
 
+
+template <class _Tp, bool = std::is_enum<_Tp>::value>
+struct __sfinae_underlying_type
+{
+    typedef typename underlying_type<_Tp>::type type;
+    typedef decltype(((type)1) + 0) __promoted_type;
+};
+
+template <class _Tp>
+struct __sfinae_underlying_type<_Tp, false> {};
+
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
+int __convert_to_integral(int __val) { return __val; }
+
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
+unsigned __convert_to_integral(unsigned __val) { return __val; }
+
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
+long __convert_to_integral(long __val) { return __val; }
+
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
+unsigned long __convert_to_integral(unsigned long __val) { return __val; }
+
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
+long long __convert_to_integral(long long __val) { return __val; }
+
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
+unsigned long long __convert_to_integral(unsigned long long __val) {return __val; }
+
+#ifndef _LIBCPP_HAS_NO_INT128
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
+__int128_t __convert_to_integral(__int128_t __val) { return __val; }
+
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
+__uint128_t __convert_to_integral(__uint128_t __val) { return __val; }
+#endif
+
+template <class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
+typename __sfinae_underlying_type<_Tp>::__promoted_type
+__convert_to_integral(_Tp __val) { return __val; }
+
 #ifndef _LIBCPP_HAS_NO_ADVANCED_SFINAE
 
 template <class _Tp>
 struct __has_operator_addressof_member_imp
 {
     template <class _Up>
         static auto __test(int)
             -> typename __select_2nd<decltype(_VSTD::declval<_Up>().operator&()), true_type>::type;

libcxx/trunk/test/libcxx/type_traits/convert_to_integral.pass.cpp

+
+#include <limits>
+#include <type_traits>
+#include <cstdint>
+#include <cassert>
+
+#include "user_defined_integral.hpp"
+
+template <class T>
+struct EnumType
+{
+  enum type : T {E_zero, E_one};
+};
+
+
+template <class From, class To>
+void check_integral_types()
+{
+  typedef std::numeric_limits<From> Limits;
+  const From max = Limits::max();
+  const From min = Limits::min();
+  {
+  auto ret = std::__convert_to_integral((From)max);
+  assert(ret == max);
+  ret = std::__convert_to_integral((From)min);
+  assert(ret == min);
+  static_assert(std::is_same<decltype(ret), To>::value, "");
+  }
+  {
+  UserDefinedIntegral<From> f(max);
+  auto ret = std::__convert_to_integral(f);
+  assert(ret == max);
+  f.value = min;
+  ret = std::__convert_to_integral(f);
+  assert(ret == min);
+  static_assert(std::is_same<decltype(ret), To>::value, "");
+  }
+  {
+  typedef typename EnumType<From>::type Enum;
+  Enum e(static_cast<Enum>(max));
+  auto ret = std::__convert_to_integral(e);
+  assert(ret == max);
+  e = static_cast<Enum>(min);
+  ret = std::__convert_to_integral(min);
+  assert(ret == min);
+  static_assert(std::is_same<decltype(ret), To>::value, "");
+  }
+}
+
+
+template <class From, class To>
+void check_enum_types()
+{
+  auto ret = std::__convert_to_integral((From)1);
+  assert(ret == 1);
+  static_assert(std::is_same<decltype(ret), To>::value, "");
+}
+
+
+enum enum1 {};
+enum enum2 {
+  value = std::numeric_limits<unsigned long>::max()
+};
+
+int main()
+{
+  check_integral_types<bool, int>();
+  check_integral_types<char, int>();
+  check_integral_types<signed char, int>();
+  check_integral_types<unsigned char, int>();
+  check_integral_types<wchar_t, int>();
+  check_integral_types<char16_t, int>();
+  check_integral_types<char32_t, uint32_t>();
+  check_integral_types<short, int>();
+  check_integral_types<unsigned short, int>();
+  check_integral_types<int, int>();
+  check_integral_types<unsigned, unsigned>();
+  check_integral_types<long, long>();
+  check_integral_types<unsigned long, unsigned long>();
+  check_integral_types<long long, long long>();
+  check_integral_types<unsigned long long, unsigned long long>();
+#ifndef _LIBCPP_HAS_NO_INT128
+  check_integral_types<__int128_t, __int128_t>();
+  check_integral_types<__uint128_t, __uint128_t>();
+#endif
+    // TODO(ericwf): Not standard
+  check_enum_types<enum1, unsigned>();
+  check_enum_types<enum2, unsigned long>();
+}

libcxx/trunk/test/std/algorithms/alg.modifying.operations/alg.copy/copy_n.pass.cpp

 // template<InputIterator InIter, OutputIterator<auto, InIter::reference> OutIter>
 //   OutIter
 //   copy_n(InIter first, InIter::difference_type n, OutIter result);
 
 #include <algorithm>
 #include <cassert>
 
 #include "test_iterators.h"
+#include "user_defined_integral.hpp"
+
+typedef UserDefinedIntegral<unsigned> UDI;
 
 template <class InIter, class OutIter>
 void
 test()
 {
     const unsigned N = 1000;
     int ia[N];
     for (unsigned i = 0; i < N; ++i)
         ia[i] = i;
     int ib[N] = {0};
 
-    OutIter r = std::copy_n(InIter(ia), N/2, OutIter(ib));
+    OutIter r = std::copy_n(InIter(ia), UDI(N/2), OutIter(ib));
     assert(base(r) == ib+N/2);
     for (unsigned i = 0; i < N/2; ++i)
         assert(ia[i] == ib[i]);
 }
 
 int main()
 {
     test<input_iterator<const int*>, output_iterator<int*> >();

libcxx/trunk/test/std/algorithms/alg.modifying.operations/alg.fill/fill_n.pass.cpp

 //   requires OutputIterator<Iter, const T&>
 //   OutputIterator
 //   fill_n(Iter first, Size n, const T& value);
 
 #include <algorithm>
 #include <cassert>
 
 #include "test_iterators.h"
+#include "user_defined_integral.hpp"
+
+typedef UserDefinedIntegral<unsigned> UDI;
 
 template <class Iter>
 void
 test_char()
 {
     const unsigned n = 4;
     char ca[n] = {0};
-    assert(std::fill_n(Iter(ca), n, char(1)) == std::next(Iter(ca), n));
+    assert(std::fill_n(Iter(ca), UDI(n), char(1)) == std::next(Iter(ca), n));
     assert(ca[0] == 1);
     assert(ca[1] == 1);
     assert(ca[2] == 1);
     assert(ca[3] == 1);
 }
 
 template <class Iter>
 void
 test_int()
 {
     const unsigned n = 4;
     int ia[n] = {0};
-    assert(std::fill_n(Iter(ia), n, 1) == std::next(Iter(ia), n));
+    assert(std::fill_n(Iter(ia), UDI(n), 1) == std::next(Iter(ia), n));
     assert(ia[0] == 1);
     assert(ia[1] == 1);
     assert(ia[2] == 1);
     assert(ia[3] == 1);
 }
 
 void
 test_int_array()
 {
     const unsigned n = 4;
     int ia[n] = {0};
-    assert(std::fill_n(ia, n, static_cast<char>(1)) == std::next(ia, n));
+    assert(std::fill_n(ia, UDI(n), static_cast<char>(1)) == std::next(ia, n));
     assert(ia[0] == 1);
     assert(ia[1] == 1);
     assert(ia[2] == 1);
     assert(ia[3] == 1);
 }
 
 struct source {
     source() : i(0) { }
     
     operator int() const { return i++; }
     mutable int i;
 };
 
 void
 test_int_array_struct_source()
 {
     const unsigned n = 4;
     int ia[n] = {0};
-    assert(std::fill_n(ia, n, source()) == std::next(ia, n));
+    assert(std::fill_n(ia, UDI(n), source()) == std::next(ia, n));
     assert(ia[0] == 0);
     assert(ia[1] == 1);
     assert(ia[2] == 2);
     assert(ia[3] == 3);
 }
 
 struct test1 {
     test1() : c(0) { }
     test1(char c) : c(c + 1) { }
     char c;
 };
 
 void
 test_struct_array()
 {
     const unsigned n = 4;
     test1 test1a[n] = {0};
-    assert(std::fill_n(test1a, n, static_cast<char>(10)) == std::next(test1a, n));    
+    assert(std::fill_n(test1a, UDI(n), static_cast<char>(10)) == std::next(test1a, n));
     assert(test1a[0].c == 11);
     assert(test1a[1].c == 11);
     assert(test1a[2].c == 11);
     assert(test1a[3].c == 11);
 }
 
 class A
 {
     char a_;
 public:
     A() {}
     explicit A(char a) : a_(a) {}
     operator unsigned char() const {return 'b';}
 
     friend bool operator==(const A& x, const A& y)
         {return x.a_ == y.a_;}
 };
 
 void
 test5()
 {
     A a[3];
-    assert(std::fill_n(&a[0], 3, A('a')) == a+3);
+    assert(std::fill_n(&a[0], UDI(3), A('a')) == a+3);
     assert(a[0] == A('a'));
     assert(a[1] == A('a'));
     assert(a[2] == A('a'));
 }
 
 struct Storage
 {
   union
   {
     unsigned char a;
     unsigned char b;
   };
 };
- 
 void test6()
 {
   Storage foo[5];
-  std::fill_n(&foo[0], 5, Storage());
+  std::fill_n(&foo[0], UDI(5), Storage());
 }
 
 
 int main()
 {
     test_char<forward_iterator<char*> >();
     test_char<bidirectional_iterator<char*> >();
     test_char<random_access_iterator<char*> >();
     test_char<char*>();
 
     test_int<forward_iterator<int*> >();
     test_int<bidirectional_iterator<int*> >();
     test_int<random_access_iterator<int*> >();
     test_int<int*>();
-    
     test_int_array();
     test_int_array_struct_source();
     test_struct_array();
 
     test5();
     test6();
 }

libcxx/trunk/test/std/algorithms/alg.modifying.operations/alg.generate/generate_n.pass.cpp

 //         && CopyConstructible<Generator>
 //   void
 //   generate_n(Iter first, Size n, Generator gen);
 
 #include <algorithm>
 #include <cassert>
 
 #include "test_iterators.h"
+#include "user_defined_integral.hpp"
+
+typedef UserDefinedIntegral<unsigned> UDI;
 
 struct gen_test
 {
     int operator()() const {return 2;}
 };
 
 template <class Iter>
 void
 test()
 {
     const unsigned n = 4;
     int ia[n] = {0};
-    assert(std::generate_n(Iter(ia), n, gen_test()) == Iter(ia+n));
+    assert(std::generate_n(Iter(ia), UDI(n), gen_test()) == Iter(ia+n));
     assert(ia[0] == 2);
     assert(ia[1] == 2);
     assert(ia[2] == 2);
     assert(ia[3] == 2);
 }
 
 int main()
 {
     test<forward_iterator<int*> >();
     test<bidirectional_iterator<int*> >();
     test<random_access_iterator<int*> >();
     test<int*>();
 }

libcxx/trunk/test/std/algorithms/alg.nonmodifying/alg.search/search_n.pass.cpp

 //   ForwardIterator
 //   search_n(ForwardIterator first, ForwardIterator last, Size count,
 //            const T& value);
 
 #include <algorithm>
 #include <cassert>
 
 #include "test_iterators.h"
+#include "user_defined_integral.hpp"
 
 template <class Iter>
 void
 test()
 {
     int ia[] = {0, 1, 2, 3, 4, 5};
     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
     assert(std::search_n(Iter(ia), Iter(ia+sa), 0, 0) == Iter(ia));
test()
 
     int ic[] = {0, 0, 0};
     const unsigned sc = sizeof(ic)/sizeof(ic[0]);
     assert(std::search_n(Iter(ic), Iter(ic+sc), 0, 0) == Iter(ic));
     assert(std::search_n(Iter(ic), Iter(ic+sc), 1, 0) == Iter(ic));
     assert(std::search_n(Iter(ic), Iter(ic+sc), 2, 0) == Iter(ic));
     assert(std::search_n(Iter(ic), Iter(ic+sc), 3, 0) == Iter(ic));
     assert(std::search_n(Iter(ic), Iter(ic+sc), 4, 0) == Iter(ic+sc));
+
+    // Check that we properly convert the size argument to an integral.
+    std::search_n(Iter(ic), Iter(ic+sc), UserDefinedIntegral<unsigned>(0), 0);
 }
 
 int main()
 {
     test<forward_iterator<const int*> >();
     test<bidirectional_iterator<const int*> >();
     test<random_access_iterator<const int*> >();
 }

libcxx/trunk/test/std/algorithms/alg.nonmodifying/alg.search/search_n_pred.pass.cpp

 //   ForwardIterator
 //   search_n(ForwardIterator first, ForwardIterator last, Size count,
 //            const T& value, BinaryPredicate pred);
 
 #include <algorithm>
 #include <cassert>
 
 #include "test_iterators.h"
+#include "user_defined_integral.hpp"
 
 struct count_equal
 {
     static unsigned count;
     template <class T>
     bool operator()(const T& x, const T& y)
         {++count; return x == y;}
 };
 
 unsigned count_equal::count = 0;
 
+
 template <class Iter>
 void
 test()
 {
     int ia[] = {0, 1, 2, 3, 4, 5};
     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
     count_equal::count = 0;
     assert(std::search_n(Iter(ia), Iter(ia+sa), 0, 0, count_equal()) == Iter(ia));
test()
     assert(count_equal::count <= sc);
     count_equal::count = 0;
     assert(std::search_n(Iter(ic), Iter(ic+sc), 3, 0, count_equal()) == Iter(ic));
     assert(count_equal::count <= sc);
     count_equal::count = 0;
     assert(std::search_n(Iter(ic), Iter(ic+sc), 4, 0, count_equal()) == Iter(ic+sc));
     assert(count_equal::count <= sc);
     count_equal::count = 0;
+
+    // Check that we properly convert the size argument to an integral.
+    std::search_n(Iter(ic), Iter(ic+sc), UserDefinedIntegral<unsigned>(4), 0, count_equal());
+    count_equal::count = 0;
 }
 
 int main()
 {
     test<forward_iterator<const int*> >();
     test<bidirectional_iterator<const int*> >();
     test<random_access_iterator<const int*> >();
 }

libcxx/trunk/test/support/user_defined_integral.hpp

+#ifndef SUPPORT_USER_DEFINED_INTEGRAL_HPP
+#define SUPPORT_USER_DEFINED_INTEGRAL_HPP
+
+template <class T>
+struct UserDefinedIntegral
+{
+    UserDefinedIntegral() : value(0) {}
+    UserDefinedIntegral(T v) : value(v) {}
+    operator T() const { return value; }
+    T value;
+};
+
+// Poison the arithmetic and comparison operations
+template <class T, class U>
+void operator+(UserDefinedIntegral<T>, UserDefinedIntegral<U>);
+
+template <class T, class U>
+void operator-(UserDefinedIntegral<T>, UserDefinedIntegral<U>);
+
+template <class T, class U>
+void operator*(UserDefinedIntegral<T>, UserDefinedIntegral<U>);
+
+template <class T, class U>
+void operator/(UserDefinedIntegral<T>, UserDefinedIntegral<U>);
+
+template <class T, class U>
+void operator==(UserDefinedIntegral<T>, UserDefinedIntegral<U>);
+
+template <class T, class U>
+void operator!=(UserDefinedIntegral<T>, UserDefinedIntegral<U>);
+
+template <class T, class U>
+void operator<(UserDefinedIntegral<T>, UserDefinedIntegral<U>);
+
+template <class T, class U>
+void operator>(UserDefinedIntegral<T>, UserDefinedIntegral<U>);
+
+template <class T, class U>
+void operator<=(UserDefinedIntegral<T>, UserDefinedIntegral<U>);
+
+template <class T, class U>
+void operator>=(UserDefinedIntegral<T>, UserDefinedIntegral<U>);
+
+#endif // SUPPORT_USER_DEFINED_INTEGRAL_HPP