[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);

 {
     typedef _Tp        value_type;
     typedef _Distance  difference_type;
     typedef _Pointer   pointer;
     typedef _Reference reference;
     typedef _Category  iterator_category;
 };
 
-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, input_iterator_tag)
+void __advance(_InputIter& __i, _Distance __n, input_iterator_tag)
 {
     for (; __n > 0; --__n)
         ++__i;
 }
 
-template <class _BiDirIter>
+template <class _BiDirIter, class _Distance>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
-void __advance(_BiDirIter& __i,
-             typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag)
+void __advance(_BiDirIter& __i, _Distance __n, bidirectional_iterator_tag)
 {
     if (__n >= 0)
         for (; __n > 0; --__n)
             ++__i;
     else
         for (; __n < 0; ++__n)
             --__i;
 }
 
-template <class _RandIter>
+template <class _RandIter, class _Distance>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
-void __advance(_RandIter& __i,
-             typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag)
+void __advance(_RandIter& __i, _Distance __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 __n)
 {
     _LIBCPP_ASSERT(__n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
                        "Attempt to advance(it, -n) on a non-bidi iterator");
     __advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
 }
 
 template <class _InputIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14

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;
 }