[libc++] Future-proof std::copy for ranges

[ldionne]

Summary

When we eventually get to implementing algorithms on ranges, we'll want
to avoid re-writing the algorithms from scratch. To do so, we'll need to
refactor how we write algorithms so that the same core implementation can
be used by both normal algorithms and ranges algorithms. The ranges
algorithms can't just call the iterator ones because the ranges algorithms
are more general (e.g. they accept an iterator and a sentinel).

The trick is to factor the algorithm into a private name and make sure
it works on an (iterator, sentinel) pair, and then use that from the
normal algorithm. Once we add the ranges algorithm, we will only need
to shim the result into the appropriate ranges result type (in_out_result
for ranges::copy).

[ldionne]

I am putting this up as a strawman because we will need to go through all of the algorithms and do something similar at some point (before we implement the ranges:: algorithms).

Basically, we could apply a similar change to all algorithms that require it so that we're ready to implement the ranges:: version when the time comes. Here's how we would implement ranges::copy:

template<std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O>
  requires std::indirectly_copyable<I, O>
constexpr ranges::copy_result<I, O> copy( I first, S last, O result ) {
  auto [r1, r2] = _VSTD::__copy(first, last, result);
  return {r1, r2};
}

template< ranges::input_range R, std::weakly_incrementable O >
  requires std::indirectly_copyable<ranges::iterator_t<R>, O>
constexpr ranges::copy_result<ranges::borrowed_iterator_t<R>, O> copy(R&& r, O result) {
  return ranges::copy(ranges::begin(r), ranges::end(r), result);
}

This avoid duplicating any of the actual code in the copy algorithm. That doesn't represent *that much* for std::copy, but for other algorithms it'll be more significant, so we want to have a mechanical way of doing it. For algorithms that take a projection, we can implement the internal algorithm taking a projection and simply pass an identity function to implement the regular std:: algorithm. There are still some issues to think about with this approach, notably that we're copying/moving iterators around a lot more than we used to, which may or may not be a problem depending on whether iterators are cheap to copy.

libcxx/include/__algorithm/unwrap_iter.h

88

This is pretty terrible, and we'll need to introduce one for algorithms that return triples.

I think we should probably write our own little in_out_result and in_in_out_result pre-C++20 to avoid depending on pair here.

[• Quuxplusone]

You can guess that I dislike any approach that seems to lead to one-file-per-function. :) What I personally would do is,
(1) Rename <algorithm> to <__algorithm/base.h>, and have <algorithm> simply #include <__algorithm/base.h>.
(2) Move all public entrypoints (sort, lower_bound, copy...) into <__algorithm/classic.h>, and have <algorithm> also include that. Leave all the private implementations (__sort, __lower_bound, __copy...) in <__algorithm/base.h>.
(3) Change all private implementations from template<class _Iter> to template<class _Iter, class _Sent>. (This change will be local to <__algorithm/base.h>.)
(4) Implement <__algorithm/ranges.h> as more-or-less an exact copy of <__algorithm/classic.h>, just using niebloids instead of plain old function templates.

The important thing IMO is to have a way for internal users to get the classic stuff without the Ranges stuff.

Btw, I observe that right now <string_view> includes <algorithm> AFAICT only for std::min. For that reason, I suggest that a "common prefix" (maybe the longest common prefix :P) of our two approaches would be for you to make a PR pulling out <__algorithm/min_max.h>, which could also serve as a testbed for some aspects of Ranges. (Eventually we'll have to create std::ranges::min and std::ranges::max, but we certainly don't want to drag all of Ranges into <string_view>...)

std::copy is also an "interesting" first testbed, because it's all tangled up with __wrap_iter and __is_cpp17_contiguous_iterator, which are still quite actively mutating at the moment.

[ldionne]

In D101948#2740500, @Quuxplusone wrote:

You can guess that I dislike any approach that seems to lead to one-file-per-function. :) What I personally would do is,
[...]

std::copy is also an "interesting" first testbed, because it's all tangled up with __wrap_iter and __is_cpp17_contiguous_iterator, which are still quite actively mutating at the moment.

Thanks for your comments. It seems that our two approaches are basically the same except when it comes to how we are to split the header files.

I would like to have more discussion around aspects like how we are to bridge between ranges and classic algorithms in the most efficient and simplest way possible.

[tcanens]

I think something like remove or rotate (and more generally algorithms that require the use of the new iter_move and iter_swap customization points) might be a more interesting exercise.

[zoecarver]

libcxx/include/__algorithm/copy.h

28

What's the benefit of putting these into a namespace? Once we add the CPOs we're going to create two more namespaces. I think this namespace might add a bit of confusions, and I don't see any benefit (especially in such a small file).

libcxx/include/__algorithm/unwrap_iter.h

1

My personal preference: do this in three PRs:

1. Move unwrap_iter into its own header. This you could just land without review; it's an obviously correct nfc.
2. Move copy into its own header.
3. Add the CPO.

I'd also support combining 2 and 3.

[ldionne]

After giving more thought to this, it appears that we're going to have to handle each algorithm on its own. We'll try to avoid duplication as much as possible, however it's not clear to me that a 100% mechanical approach is going to work for all algorithms.

libcxx/include/CMakeLists.txt

 set(files
+  __algorithm/copy.h
+  __algorithm/unwrap_iter.h
   __availability
   __bit_reference
   __bits
   __bsd_locale_defaults.h
   __bsd_locale_fallbacks.h
   __config
   __debug
   __errc

libcxx/include/__algorithm/copy.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_COPY_H
+#define _LIBCPP___ALGORITHM_COPY_H
+
+#include <__config>
+#include <__algorithm/unwrap_iter.h>
+#include <cstddef>
+#include <type_traits>
+#include <utility>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace __copy_impl {
+    template <class _InputIterator, class _Sentinel, class _OutputIterator>
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+    std::pair<_InputIterator, _OutputIterator>
+    __copy_constexpr(_InputIterator __first, _Sentinel __last, _OutputIterator __result)
+    {
+        for (; __first != __last; ++__first, (void) ++__result)
+            *__result = *__first;
+        return {__first, __result};
+    }
+
+    template <class _InputIterator, class _Sentinel, class _OutputIterator>
+    _LIBCPP_INLINE_VISIBILITY
+    std::pair<_InputIterator, _OutputIterator>
+    __copy_runtime(_InputIterator __first, _Sentinel __last, _OutputIterator __result)
+    {
+        return __copy_impl::__copy_constexpr(__first, __last, __result);
+    }
+
+    template <class _Tp, class _Up, class = _EnableIf<
+      is_same<typename remove_const<_Tp>::type, _Up>::value &&
+      is_trivially_copy_assignable<_Up>::value
+    > >
+    _LIBCPP_INLINE_VISIBILITY
+    std::pair<_Tp*, _Up*>
+    __copy_runtime(_Tp* __first, _Tp* __last, _Up* __result)
+    {
+        const size_t __n = static_cast<size_t>(__last - __first);
+        if (__n > 0)
+            _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+        return {__first + __n, __result + __n};
+    }
+} // end namespace __copy_impl
+
+template <class _InputIterator, class _Sentinel, class _OutputIterator>
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+std::pair<_InputIterator, _OutputIterator>
+__copy(_InputIterator __first, _Sentinel __last, _OutputIterator __result)
+{
+    if (__libcpp_is_constant_evaluated()) {
+        return __copy_impl::__copy_constexpr(__first, __last, __result);
+    } else {
+        return _VSTD::__rewrap_iters(std::make_pair(__first, __result),
+            __copy_impl::__copy_runtime(_VSTD::__unwrap_iter(__first),
+                                        _VSTD::__unwrap_iter(__last),
+                                        _VSTD::__unwrap_iter(__result)));
+    }
+}
+
+template <class _InputIterator, class _OutputIterator>
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_OutputIterator
+copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+{
+    return _VSTD::__copy(_VSTD::move(__first), _VSTD::move(__last), _VSTD::move(__result)).second;
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_COPY_H

libcxx/include/__algorithm/unwrap_iter.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_UNWRAP_ITER_H
+#define _LIBCPP___ALGORITHM_UNWRAP_ITER_H
+
+#include <__config>
+#include <__iterator/iterator_traits.h> // __is_cpp17_contiguous_iterator
+#include <__memory/pointer_traits.h> // __to_address
+#include <utility>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// __unwrap_iter, __rewrap_iter
+
+// The job of __unwrap_iter is to lower contiguous iterators (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.
+// For iterators that are not contiguous, it must be a no-op.
+// In debug mode, we don't do this.
+//
+// __unwrap_iter is non-constexpr for user-defined iterators whose
+// `to_address` and/or `operator->` is non-constexpr. This is okay; but we
+// try to avoid doing __unwrap_iter in constant-evaluated contexts anyway.
+//
+// Some algorithms (e.g. std::copy, but not std::sort) need to convert an
+// "unwrapped" result back into a contiguous iterator. Since contiguous iterators
+// are random-access, we can do this portably using iterator arithmetic; this
+// is the job of __rewrap_iter.
+
+template <class _Iter, bool = __is_cpp17_contiguous_iterator<_Iter>::value>
+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);
+    }
+};
+
+#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>()))
+__unwrap_iter(_Iter __i) _NOEXCEPT
+{
+    return _Impl::__apply(__i);
+}
+
+template<class _OrigIter>
+_OrigIter __rewrap_iter(_OrigIter, _OrigIter __result)
+{
+    return __result;
+}
+
+template<class _OrigIter, class _UnwrappedIter>
+_OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result)
+{
+    // Precondition: __result is reachable from __first
+    // Precondition: _OrigIter is a contiguous iterator
+    return __first + (__result - _VSTD::__unwrap_iter(__first));
+}
+
+template<class _OrigIter1, class _OrigIter2, class _UnwrappedIter1, class _UnwrappedIter2>
+std::pair<_OrigIter1, _OrigIter2>
+__rewrap_iters(std::pair<_OrigIter1, _OrigIter2> __its,
+               std::pair<_UnwrappedIter1, _UnwrappedIter2> __results)
+{
+    return std::pair<_OrigIter1, _OrigIter2>(_VSTD::__rewrap_iter(__its.first, __results.first),
+                                             _VSTD::__rewrap_iter(__its.second, __results.second));
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_UNWRAP_ITER_H

libcxx/include/algorithm

 #include <utility> // needed to provide swap_ranges.
 #include <memory>
 #include <functional>
 #include <iterator>
 #include <cstddef>
 #include <bit>
 #include <version>
 
+#include <__algorithm/copy.h>
+#include <__algorithm/unwrap_iter.h>
+
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

 _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, _VSTD::__convert_to_integral(__count),
                            __value_, __equal_to<__v, _Tp>());
 }
 
-// __unwrap_iter, __rewrap_iter
-
-// The job of __unwrap_iter is to lower contiguous iterators (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.
-// For iterators that are not contiguous, it must be a no-op.
-// In debug mode, we don't do this.
-//
-// __unwrap_iter is non-constexpr for user-defined iterators whose
-// `to_address` and/or `operator->` is non-constexpr. This is okay; but we
-// try to avoid doing __unwrap_iter in constant-evaluated contexts anyway.
-//
-// Some algorithms (e.g. std::copy, but not std::sort) need to convert an
-// "unwrapped" result back into a contiguous iterator. Since contiguous iterators
-// are random-access, we can do this portably using iterator arithmetic; this
-// is the job of __rewrap_iter.
-
-template <class _Iter, bool = __is_cpp17_contiguous_iterator<_Iter>::value>
-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);
-    }
-};
-
-#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>()))
-__unwrap_iter(_Iter __i) _NOEXCEPT
-{
-    return _Impl::__apply(__i);
-}
-
-template<class _OrigIter>
-_OrigIter __rewrap_iter(_OrigIter, _OrigIter __result)
-{
-    return __result;
-}
-
-template<class _OrigIter, class _UnwrappedIter>
-_OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result)
-{
-    // Precondition: __result is reachable from __first
-    // Precondition: _OrigIter is a contiguous iterator
-    return __first + (__result - _VSTD::__unwrap_iter(__first));
-}
-
-// copy
-
-template <class _InputIterator, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_OutputIterator
-__copy_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
-{
-    for (; __first != __last; ++__first, (void) ++__result)
-        *__result = *__first;
-    return __result;
-}
-
-template <class _InputIterator, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY
-_OutputIterator
-__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
-{
-    return _VSTD::__copy_constexpr(__first, __last, __result);
-}
-
-template <class _Tp, class _Up>
-inline _LIBCPP_INLINE_VISIBILITY
-typename enable_if
-<
-    is_same<typename remove_const<_Tp>::type, _Up>::value &&
-    is_trivially_copy_assignable<_Up>::value,
-    _Up*
->::type
-__copy(_Tp* __first, _Tp* __last, _Up* __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
-copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
-{
-    if (__libcpp_is_constant_evaluated()) {
-        return _VSTD::__copy_constexpr(__first, __last, __result);
-    } else {
-        return _VSTD::__rewrap_iter(__result,
-            _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
 __copy_backward_constexpr(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
 {
     while (__first != __last)