[libc++] Further improve the contiguous-iterator story, and fix some bugs in D94807.

[• Quuxplusone]

Summary

• Quality-of-implementation: Avoid calling __unwrap_iter in constexpr contexts. The user might conceivably write a contiguous iterator where normal iterator arithmetic is constexpr-friendly but std::to_address(it) isn't.
• Bugfix: When you pass contiguous iterators to std::copy, you should get back your contiguous iterator type, not a raw pointer. That means that libc++ can't __unwrap_iter unless it also does __rewrap_iter. Fortunately, this is implementable.
• Improve test coverage of the new contiguous_iterator test iterator. This catches the bug described above.
• Tests: Stop testing that we can std::copy into an input_iterator. Our test iterators may currently support that, but it seems nonsensical to me.

[• Quuxplusone]

Rebase on main (after landing D93661).

[• Quuxplusone]

libcxx/include/algorithm

1649

It's been pointed out to me that this is fine; std::copy is required to have the constexpr keyword on the front, but it's never required to actually be constexpr. libc++ can say "std::copy is constexpr unless you give us a contiguous iterator with a non-constexpr to_address and/or operator->."

1653

I still lack any great way to work around this one, though. I think if we want to use __unwrap_iter(first) on arbitrary user-provided contiguous iterators in copy, then we'll have to separately compute the return value using something like

template<class _OrigIter, class _UnwrappedIter>
_Iter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result)
{
    static_assert(__is_cpp17_contiguous_iterator<_OrigIter>, "");  // otherwise we won't get here
    return __first + (__result - _VSTD::__unwrap_iter(__first));
}

template<class _OrigIter>
_Iter __rewrap_iter(_OrigIter, _OrigIter __result)
{
    return __result;
}
[...]
return _VSTD::__rewrap_iter(__result,
     _VSTD::__copy(_VSTD::__unwrap_iter(__first),
                   _VSTD::__unwrap_iter(__last),
                   _VSTD::__unwrap_iter(__result)));

This mostly destroys our hopes of "reducing the number of template instantiations"; but it does permit us to keep using memmove for user-defined contiguous iterators.

[ldionne]

libcxx/include/algorithm

1656

I don't understand this change - didn't you work around the constexpr problem by *not* calling unwrap_iter on iterators when we're in a constexpr context?

Edit: Ah, I think you're trying to work around the *second* problem you pointed out, which is that you can't automatically re-create an arbitrary user-defined iterator from a raw pointer. Right? A solution for that could be to:

1. Introduce an indirection like __rewrap_iter_impl with a nested __apply that creates an iterator from a raw pointer. That can be specialized as needed.
2. Provide a default implementation for all iterators that are implicitly constructible from a pointer to their value_type.

That way, if the iterator isn't implicitly constructible from the pointer, a user like Chrome can still get the optimization by specializing the struct to tell libc++ how to get an iterator back from a pointer. And by default, it'll work for most iterators out of the box. Thoughts on that solution?

The only issue I can see is if implicit construction from a raw pointer is syntactically valid but doesn't do what we think it should do. I'm not sure how likely or dangerous that could be, but I would argue that if a contiguous iterator is constructible from a pointer but that constructor doesn't do the right thing, then you really voided your warranty with the Standard Library.

[ldionne]

Also, if we go down the road of adding a __rewrap_iter struct, can you add a test exercising that extension point under libcxx/?

Requesting changes for the review queue.

[• Quuxplusone]

libcxx/include/algorithm

1656

That way, if the iterator isn't implicitly constructible from the pointer, a user like Chrome can still get the optimization by specializing the struct to tell libc++ how to get an iterator back from a pointer.

I don't think we need __rewrap_iter to be a customization point at all. A contiguous iterator (even a user-defined one) is always a random-access iterator too, so we can use __first + (__result - _VSTD::__unwrap_iter(__first)) as I indicated in my Phab comment a few lines above this. (If __unwrap_iter is a no-op, meaning that _OrigIter wasn't a contiguous iterator, just return __result unmodified.)

I would argue that if a contiguous iterator is constructible from a pointer but that constructor doesn't do the right thing, then you really voided your warranty with the Standard Library.

I strongly agree in fantasy-everything-as-it-should-be-land, but I'm less sure in actual-C++-land. Remember this is the language that invented std::pointer_traits<It>::to_address(it) and std::pointer_traits<It>::pointer_to(ptr) instead of just using static_cast<T*>(it) and static_cast<It>(ptr).

[• Quuxplusone]

Massive update and (happily) this is now less of a revert and more of a bugfix.

[ldionne]

libcxx/include/algorithm

1656

The issue with this approach is that it requires the unwrapped iterator to be reachable from the original iterator. That works for the algorithms we want to apply it to, but I could imagine other circumstances where that doesn't work, say if we're allocating a new range.

libcxx/include/algorithm

 }
 
 // __unwrap_iter
 
 // The job of __unwrap_iter is to lower iterators-that-are-tantamount-to-pointers
 // (such as vector<T>::iterator) into pointers, to reduce the number of template
 // instantiations and to enable pointer-based optimizations e.g. in std::copy.
 // In debug mode, we don't do this.
+// Furthermore, we can't do this for user-defined iterators because their
+// `to_address` may be non-constexpr and/or have observable side effects.
+// Furthermore, some algorithms (e.g. std::copy, but not std::sort) need
+// to convert the "unwrapped" pointer back into an iterator, for which there
+// is no standard API: we rely on implicit conversion to do the right thing.
+// For user-defined iterators this isn't a conforming assumption.
+// So the only type we actually unwrap is our own __wrap_iter<T*>.
 
-template <class _Iter, bool = __is_cpp17_contiguous_iterator<_Iter>::value>
+template <class _Iter> class __wrap_iter;
+
+template <class _Iter>
 struct __unwrap_iter_impl {
     static _LIBCPP_CONSTEXPR _Iter
     __apply(_Iter __i) _NOEXCEPT {
         return __i;
     }
 };
 
 #if _LIBCPP_DEBUG_LEVEL < 2
 
 template <class _Iter>
-struct __unwrap_iter_impl<_Iter, true> {
-    static _LIBCPP_CONSTEXPR decltype(_VSTD::__to_address(declval<_Iter>()))
-    __apply(_Iter __i) _NOEXCEPT {
-        return _VSTD::__to_address(__i);
+struct __unwrap_iter_impl<__wrap_iter<_Iter> > {
+    static _LIBCPP_CONSTEXPR _Iter
+    __apply(__wrap_iter<_Iter> __i) _NOEXCEPT {
+        return __i.base();
     }
 };
 
 #endif  // _LIBCPP_DEBUG_LEVEL < 2
 
 template<class _Iter, class _Impl = __unwrap_iter_impl<_Iter> >
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 decltype(_Impl::__apply(_VSTD::declval<_Iter>()))

 }
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
     if (__libcpp_is_constant_evaluated()) {
-        return _VSTD::__copy_constexpr(
-            _VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result));
+        return _VSTD::__copy_constexpr(__first, __last, __result);
     } else {
-        return _VSTD::__copy(
-            _VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result));
+        return _VSTD::__copy(_VSTD::__unwrap_iter(__first),
+                             _VSTD::__unwrap_iter(__last),
+                             _VSTD::__unwrap_iter(__result));
     }
 }
 
 // copy_backward
 
 template <class _BidirectionalIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator

 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _BidirectionalIterator2
 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
               _BidirectionalIterator2 __result)
 {
     if (__libcpp_is_constant_evaluated()) {
-        return _VSTD::__copy_backward_constexpr(_VSTD::__unwrap_iter(__first),
-                                                _VSTD::__unwrap_iter(__last),
-                                                _VSTD::__unwrap_iter(__result));
+        return _VSTD::__copy_backward_constexpr(__first, __last, __result);
     } else {
         return _VSTD::__copy_backward(_VSTD::__unwrap_iter(__first),
                                       _VSTD::__unwrap_iter(__last),
                                       _VSTD::__unwrap_iter(__result));
     }
 }
 
 // copy_if

 {
     typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
     _IntegralSize __n = __orig_n;
     return _VSTD::copy(__first, __first + __n, __result);
 }
 
 // move
 
-// __move_constexpr exists so that __move doesn't call itself when delegating to the constexpr
-// version of __move.
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 _OutputIterator
 __move_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
     for (; __first != __last; ++__first, (void) ++__result)
         *__result = _VSTD::move(*__first);
     return __result;

 typename enable_if
 <
     is_same<typename remove_const<_Tp>::type, _Up>::value &&
     is_trivially_move_assignable<_Up>::value,
     _Up*
 >::type
 __move(_Tp* __first, _Tp* __last, _Up* __result)
 {
-    if (__libcpp_is_constant_evaluated())
-        return _VSTD::__move_constexpr(__first, __last, __result);
     const size_t __n = static_cast<size_t>(__last - __first);
     if (__n > 0)
         _VSTD::memmove(__result, __first, __n * sizeof(_Up));
     return __result + __n;
 }
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
-    return _VSTD::__move(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result));
+    if (__libcpp_is_constant_evaluated()) {
+        return _VSTD::__move_constexpr(__first, __last, __result);
+    } else {
+        return _VSTD::__move(_VSTD::__unwrap_iter(__first),
+                             _VSTD::__unwrap_iter(__last),
+                             _VSTD::__unwrap_iter(__result));
+    }
 }
 
 // move_backward
 
-// __move_backward_constexpr exists so that __move_backward doesn't call itself when delegating to
-// the constexpr version of __move_backward.
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 _OutputIterator
 __move_backward_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
     while (__first != __last)
         *--__result = _VSTD::move(*--__last);
     return __result;

 typename enable_if
 <
     is_same<typename remove_const<_Tp>::type, _Up>::value &&
     is_trivially_move_assignable<_Up>::value,
     _Up*
 >::type
 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
 {
-    if (__libcpp_is_constant_evaluated())
-        return _VSTD::__move_backward_constexpr(__first, __last, __result);
     const size_t __n = static_cast<size_t>(__last - __first);
     if (__n > 0)
     {
         __result -= __n;
         _VSTD::memmove(__result, __first, __n * sizeof(_Up));
     }
     return __result;
 }
 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _BidirectionalIterator2
 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
               _BidirectionalIterator2 __result)
 {
-    return _VSTD::__move_backward(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result));
+    if (__libcpp_is_constant_evaluated()) {
+        return _VSTD::__move_backward_constexpr(__first, __last, __result);
+    } else {
+        return _VSTD::__move_backward(_VSTD::__unwrap_iter(__first),
+                                      _VSTD::__unwrap_iter(__last),
+                                      _VSTD::__unwrap_iter(__result));
+    }
 }
 
 // iter_swap
 
 // moved to <type_traits> for better swap / noexcept support
 
 // transform
 

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/contiguous_nonconstexpr.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
+//
+//===----------------------------------------------------------------------===//
+
+// Older compilers don't support std::is_constant_evaluated
+// UNSUPPORTED: clang-4, clang-5, clang-6, clang-7, clang-8
+// UNSUPPORTED: apple-clang-9, apple-clang-10
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <algorithm>
+
+#include <algorithm>
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+struct NCCI : public contiguous_iterator<int*> {
+    using contiguous_iterator::contiguous_iterator;
+};
+
+template<>
+struct std::pointer_traits<NCCI> {
+    static int *to_address(NCCI it) {
+        return it.base();
+    }
+};
+
+constexpr bool test()
+{
+    int ia[4] = {1,2,3,4};
+    int ib[4] = {0,0,0,0};
+
+    std::copy(NCCI(ia), NCCI(ia+4), ib);
+    std::copy(ia, ia+4, NCCI(ib));
+
+    std::copy_backward(NCCI(ia), NCCI(ia+4), ib+4);
+    std::copy_backward(ia, ia+4, NCCI(ib+4));
+
+    std::move(NCCI(ia), NCCI(ia+4), ib);
+    std::move(ia, ia+4, NCCI(ib));
+
+    std::move_backward(NCCI(ia), NCCI(ia+4), ib+4);
+    std::move_backward(ia, ia+4, NCCI(ib+4));
+
+    return true;
+}
+
+
+int main(int, char**)
+{
+    static_assert(test());
+
+    return 0;
+}