[libc++] Don't force a conversion to difference_type in std::advance

[ldionne]

Summary

The Standard documents the signature of std::advance as

template <class Iter, class Distance>
constexpr void advance(Iter& i, Distance n);

Furthermore, it does not appear to put any restriction on what the type
of Distance should be. While it is understood that it should usually
be std::iterator_traits::difference_type, I couldn't find any wording
that mandates that. Similarly, I couldn't find wording that forces the
distance to be a signed type.

This patch changes std::advance to accept any type in the second argument,
which appears to be what the Standard mandates. I think it would be better
to at least restrict it to integral types, but that's not what the Standard
appears to say.

[ldionne]

@mclow.lists I'm curious to hear what you think about this patch.

I think it's weird to have a wide open template parameter like this in std::distance, but it appears to be what the Standard wants. And using difference_type leads to warnings when passing an unsigned type when -Wsign-conversion is enabled (which is where this change comes from).

[mclow.lists]

In D81425#2080807, @ldionne wrote:

I think it's weird to have a wide open template parameter like this in std::distance, but it appears to be what the Standard wants.

Personally, I think that this was a mistake in the original STL design. But there it is.

I think you need to do the same dance as copy_n does.

And make sure you don't break the advance(bidi, -3). There was an LWG issue about that.

[mclow.lists]

I wouldn't change the __advance definitions. That's just spreading the pain around. Convert from Distance to iterator_traits<...>::difference_type in advance

[ldionne]

Update per Marshall's comments

libcxx/include/iterator

 
 struct input_iterator_tag  {};
 struct output_iterator_tag {};
 struct forward_iterator_tag       : public input_iterator_tag         {};
 struct bidirectional_iterator_tag : public forward_iterator_tag       {};
 struct random_access_iterator_tag : public bidirectional_iterator_tag {};
 
 // 27.4.3, iterator operations
-// extension: second argument not conforming to C++03
-template <class InputIterator>  // constexpr in C++17
-  constexpr void advance(InputIterator& i,
-             typename iterator_traits<InputIterator>::difference_type n);
+template <class InputIterator, class Distance>  // constexpr in C++17
+  constexpr void advance(InputIterator& i, Distance n);
 
 template <class InputIterator>  // constexpr in C++17
   constexpr typename iterator_traits<InputIterator>::difference_type
     distance(InputIterator first, InputIterator last);
 
 template <class InputIterator>  // constexpr in C++17
   constexpr InputIterator next(InputIterator x,
 typename iterator_traits<InputIterator>::difference_type n = 1);

 template <class _RandIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 void __advance(_RandIter& __i,
              typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag)
 {
    __i += __n;
 }
 
-template <class _InputIter>
+template <class _InputIter, class _Distance>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
-void advance(_InputIter& __i,
-             typename iterator_traits<_InputIter>::difference_type __n)
+void advance(_InputIter& __i, _Distance __orig_n)
 {
-    _LIBCPP_ASSERT(__n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
-                       "Attempt to advance(it, -n) on a non-bidi iterator");
+    _LIBCPP_ASSERT(__orig_n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
+                   "Attempt to advance(it, n) with negative n on a non-bidirectional iterator");
+    typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
+    _IntegralSize __n = __orig_n;
     __advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
 }
 
 template <class _InputIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 typename iterator_traits<_InputIter>::difference_type
 __distance(_InputIter __first, _InputIter __last, input_iterator_tag)
 {

 <
     __is_cpp17_input_iterator<_InputIter>::value,
     _InputIter
 >::type
 next(_InputIter __x,
      typename iterator_traits<_InputIter>::difference_type __n = 1)
 {
     _LIBCPP_ASSERT(__n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
-                       "Attempt to next(it, -n) on a non-bidi iterator");
+                       "Attempt to next(it, n) with negative n on a non-bidirectional iterator");
 
     _VSTD::advance(__x, __n);
     return __x;
 }
 
 template <class _InputIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 typename enable_if
 <
     __is_cpp17_input_iterator<_InputIter>::value,
     _InputIter
 >::type
 prev(_InputIter __x,
      typename iterator_traits<_InputIter>::difference_type __n = 1)
 {
     _LIBCPP_ASSERT(__n <= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
-                       "Attempt to prev(it, +n) on a non-bidi iterator");
+                       "Attempt to prev(it, n) with a positive n on a non-bidirectional iterator");
     _VSTD::advance(__x, -__n);
     return __x;
 }
 
 
 template <class _Tp, class = void>
 struct __is_stashing_iterator : false_type {};
 

libcxx/test/std/iterators/iterator.primitives/iterator.operations/advance.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // <iterator>
 
 //   All of these became constexpr in C++17
 //
-// template <InputIterator Iter>
-//   constexpr void advance(Iter& i, Iter::difference_type n);
+// template <InputIterator Iter, class Distance>
+//   constexpr void advance(Iter& i, Distance n);
 //
-// template <BidirectionalIterator Iter>
-//   constexpr void advance(Iter& i, Iter::difference_type n);
+// template <BidirectionalIterator Iter, class Distance>
+//   constexpr void advance(Iter& i, Distance n);
 //
-// template <RandomAccessIterator Iter>
-//   constexpr void advance(Iter& i, Iter::difference_type n);
+// template <RandomAccessIterator Iter, class Distance>
+//   constexpr void advance(Iter& i, Distance n);
+
+// Make sure we catch forced conversions to the difference_type if they happen.
+// ADDITIONAL_COMPILER_FLAGS: -Wsign-conversion
 
 #include <iterator>
 #include <cassert>
+#include <cstddef>
 #include <type_traits>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
-template <class It>
+template <class Distance, class It>
 TEST_CONSTEXPR_CXX17
-void check_advance(It it, typename std::iterator_traits<It>::difference_type n, It result)
+void check_advance(It it, Distance n, It result)
 {
     static_assert(std::is_same<decltype(std::advance(it, n)), void>::value, "");
     std::advance(it, n);
     assert(it == result);
 }
 
 TEST_CONSTEXPR_CXX17 bool tests()
 {
     const char* s = "1234567890";
-    check_advance(input_iterator<const char*>(s), 10, input_iterator<const char*>(s+10));
-    check_advance(forward_iterator<const char*>(s), 10, forward_iterator<const char*>(s+10));
-    check_advance(bidirectional_iterator<const char*>(s+5), 5, bidirectional_iterator<const char*>(s+10));
-    check_advance(bidirectional_iterator<const char*>(s+5), -5, bidirectional_iterator<const char*>(s));
-    check_advance(random_access_iterator<const char*>(s+5), 5, random_access_iterator<const char*>(s+10));
-    check_advance(random_access_iterator<const char*>(s+5), -5, random_access_iterator<const char*>(s));
-    check_advance(s+5, 5, s+10);
-    check_advance(s+5, -5, s);
+    typedef std::iterator_traits<const char*>::difference_type Distance;
+    check_advance<Distance>(input_iterator<const char*>(s), 10, input_iterator<const char*>(s+10));
+    check_advance<Distance>(forward_iterator<const char*>(s), 10, forward_iterator<const char*>(s+10));
+    check_advance<Distance>(bidirectional_iterator<const char*>(s+5), 5, bidirectional_iterator<const char*>(s+10));
+    check_advance<Distance>(bidirectional_iterator<const char*>(s+5), -5, bidirectional_iterator<const char*>(s));
+    check_advance<Distance>(random_access_iterator<const char*>(s+5), 5, random_access_iterator<const char*>(s+10));
+    check_advance<Distance>(random_access_iterator<const char*>(s+5), -5, random_access_iterator<const char*>(s));
+    check_advance<Distance>(s+5, 5, s+10);
+    check_advance<Distance>(s+5, -5, s);
+
+    // Also check with other distance types
+    check_advance<std::size_t>(input_iterator<const char*>(s), 10u, input_iterator<const char*>(s+10));
+    check_advance<std::size_t>(forward_iterator<const char*>(s), 10u, forward_iterator<const char*>(s+10));
+    check_advance<std::size_t>(bidirectional_iterator<const char*>(s), 10u, bidirectional_iterator<const char*>(s+10));
+    check_advance<std::size_t>(random_access_iterator<const char*>(s), 10u, random_access_iterator<const char*>(s+10));
 
     return true;
 }
 
 int main(int, char**)
 {
     tests();
 #if TEST_STD_VER >= 17
     static_assert(tests(), "");
 #endif
     return 0;
 }