Optimizing std::copy and related algorithms for std::reverse_iterator.

[dyaroshev]

Summary

This patch makes std::copy/std::copy_backward/std::move/std::move_backward to unwrap 3 revesre_iterators call corresponding reverted algorithm.

The SFINAE magic was getting too complicated to read and to get right. Therefor I used regular if in "if constexpr" manner and relied on the dead code elimination optimization. (Compiler explorer: https://godbolt.org/g/kiHDjW). Is this OK?

My editor removed quite a few trailing whitespaces in the iterator header. Restore them?

I don't have the clang-format set up for libcxx, sorry for the formatting mistakes.

Bug: https://bugs.llvm.org/show_bug.cgi?id=34339

include/algorithm

 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, __convert_to_integral(__count),
                            __value_, __equal_to<__v, _Tp>());
 }
 
 // copy
+
+template <class _Iter>
+struct __is_move_iterator : false_type {};
+
+template <class _Iter>
+struct __is_move_iterator<move_iterator<_Iter>> : true_type {};
+
+template <class _Iter>
+struct __is_wrapped_iterator : false_type {};
+
+template <class _Iter>
+struct __is_wrapped_iterator<__wrap_iter<_Iter>> : true_type {};
+
 template <class _Iter>
+struct __is_reverse_iterator : false_type {};
+
+template <class _Iter>
+struct __is_reverse_iterator<reverse_iterator<_Iter>> : true_type {};
+
+template <bool __condition, class _Iter>
 inline _LIBCPP_INLINE_VISIBILITY
+typename enable_if
+<
+    !__condition,
     _Iter
-__unwrap_iter(_Iter __i)
-{
+>::type
+__unwrap_iter(_Iter __i) {
+    _LIBCPP_DEBUG_ASSERT(false, "Internal error. This function should never be called.");
     return __i;
 }
 
-template <class _Tp>
+template <bool __condition, class _Iter>
 inline _LIBCPP_INLINE_VISIBILITY
 typename enable_if
 <
-    is_trivially_copy_assignable<_Tp>::value,
-    _Tp*
+  __condition,
+  typename _Iter::iterator_type
 >::type
-__unwrap_iter(move_iterator<_Tp*> __i)
-{
+__unwrap_iter(_Iter __i) {
     return __i.base();
 }
 
-#if _LIBCPP_DEBUG_LEVEL < 2
-
-template <class _Tp>
+template <bool __is_backward,
+          class _CopyTraits,  // customizable for testing.
+          class _InputIterator,
+          class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY
-typename enable_if
-<
-    is_trivially_copy_assignable<_Tp>::value,
-    _Tp*
->::type
-__unwrap_iter(__wrap_iter<_Tp*> __i)
+_OutputIterator
+__do_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
+    typedef typename iterator_traits<_InputIterator>::value_type _Tp;
+    typedef typename iterator_traits<_OutputIterator>::value_type _Up;
+
+    _LIBCPP_CONSTEXPR const bool __is_trivial_copy = std::is_trivially_copy_assignable<_Up>::value &&
+                                                     std::is_same<typename std::remove_const<_Tp>::type, _Up>::value;
+
+    if (__is_trivial_copy && is_pointer<_InputIterator>::value && is_pointer<_OutputIterator>::value)
+        return _OutputIterator(_CopyTraits::template __memmove<__is_backward>(__first, __last, __result));
+
     {
-    return __i.base();
+        _LIBCPP_CONSTEXPR const bool __condition = __is_wrapped_iterator<_OutputIterator>::value && !_CopyTraits::__is_debug;
+
+        if (__condition)
+            return _OutputIterator(__do_copy<__is_backward, _CopyTraits>(__first, __last, __unwrap_iter<__condition>(__result)));
     }
 
-#else
+    {
+        _LIBCPP_CONSTEXPR const bool __condition =
+            (__is_trivial_copy && __is_move_iterator<_InputIterator>::value) ||
+            (__is_wrapped_iterator<_InputIterator>::value && !_CopyTraits::__is_debug);
+
+        if (__condition)
+            return _OutputIterator(
+                __do_copy<__is_backward, _CopyTraits>(__unwrap_iter<__condition>(__first),
+                                                      __unwrap_iter<__condition>(__last),
+                                                      __result));
+    }
 
-template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY
-typename enable_if
-<
-    is_trivially_copy_assignable<_Tp>::value,
-    __wrap_iter<_Tp*>
->::type
-__unwrap_iter(__wrap_iter<_Tp*> __i)
     {
-    return __i;
+        _LIBCPP_CONSTEXPR const bool __condition =
+           __is_reverse_iterator<_InputIterator>::value && __is_reverse_iterator<_OutputIterator>::value;
+        _LIBCPP_CONSTEXPR const bool __new_is_backward = __condition ? !__is_backward : __is_backward;
+        if (__condition)
+            return _OutputIterator(
+                __do_copy<__new_is_backward, _CopyTraits>(__unwrap_iter<__condition>(__last),
+                                                          __unwrap_iter<__condition>(__first),
+                                                          __unwrap_iter<__condition>(__result)));
     }
 
-#endif  // _LIBCPP_DEBUG_LEVEL < 2
+    return _CopyTraits::template __loop<__is_backward>(__first, __last, __result);
+}
 
+template <bool __is_backward /* = false */>
+struct __loop_copy_impl
+{
     template <class _InputIterator, class _OutputIterator>
     inline _LIBCPP_INLINE_VISIBILITY
     _OutputIterator
-__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+    operator()(_InputIterator __first, _InputIterator __last, _OutputIterator __result) const
     {
-    for (; __first != __last; ++__first, (void) ++__result)
+        for (; __first != __last; ++__first, (void)++__result)
             *__result = *__first;
         return __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)
+template <>
+struct __loop_copy_impl</*__is_backward =*/ true>
 {
-    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
     _OutputIterator
-copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+    operator()(_InputIterator __first, _InputIterator __last, _OutputIterator __result) const
     {
-    return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
+        while (__first != __last)
+            *--__result = *--__last;
+        return __result;
     }
+};
 
-// copy_backward
+struct __copy_traits
+{
+#if _LIBCPP_DEBUG_LEVEL < 2
+    static _LIBCPP_CONSTEXPR const bool __is_debug = false;
+#else
+    static _LIBCPP_CONSTEXPR const bool __is_debug = true;
+#endif
 
-template <class _BidirectionalIterator, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+    template <bool __is_backward, class _InputIterator, class _OutputIterator>
+    inline _LIBCPP_INLINE_VISIBILITY static
     _OutputIterator
-__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
+    __memmove(_InputIterator, _InputIterator, _OutputIterator __result)
     {
-    while (__first != __last)
-        *--__result = *--__last;
+        _LIBCPP_DEBUG_ASSERT(false, "Internal error. This function should never be called.");
         return __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,
+    template <bool __is_backward, class _Tp, class _Up>
+    inline _LIBCPP_INLINE_VISIBILITY static
     _Up*
->::type
-__copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
+     __memmove(_Tp* __first, _Tp* __last, _Up* __result)
     {
         const size_t __n = static_cast<size_t>(__last - __first);
         if (__n > 0)
+            _VSTD::memmove(__is_backward ? __result - __n : __result, __first, __n * sizeof(_Up));
+        return __is_backward ? __result - __n : __result + __n;
+    }
+
+    template <bool __is_backward, class _InputIterator, class _OutputIterator>
+    inline _LIBCPP_INLINE_VISIBILITY static
+    _OutputIterator
+     __loop(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
     {
-        __result -= __n;
-        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+        return __loop_copy_impl<__is_backward>()(__first, __last, __result);
     }
-    return __result;
+};
+
+template <class _InputIterator, class _OutputIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_OutputIterator
+copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+{
+    return _VSTD::__do_copy</*__is_backward*/false, __copy_traits>(__first, __last, __result);
 }
 
+// copy_backward
+
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
 inline _LIBCPP_INLINE_VISIBILITY
 _BidirectionalIterator2
 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
               _BidirectionalIterator2 __result)
 {
-    return _VSTD::__copy_backward(__unwrap_iter(__first),
-                                  __unwrap_iter(__last),
-                                  __unwrap_iter(__result));
+    return _VSTD::__do_copy</*__is_backward*/true, __copy_traits>(__first, __last, __result);
 }
 
 // copy_if
 
 template<class _InputIterator, class _OutputIterator, class _Predicate>
 inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
 copy_if(_InputIterator __first, _InputIterator __last,
copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
     return _VSTD::copy(__first, __first + __n, __result);
 }
 
 // move
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
-__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
-{
-    for (; __first != __last; ++__first, (void) ++__result)
-        *__result = _VSTD::move(*__first);
-    return __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
-__move(_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
-_OutputIterator
 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
-    return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
+    return _VSTD::copy(_VSTD::make_move_iterator(__first), _VSTD::make_move_iterator(__last), __result);
 }
 
 // move_backward
 
-template <class _InputIterator, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY
-_OutputIterator
-__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
-{
-    while (__first != __last)
-        *--__result = _VSTD::move(*--__last);
-    return __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
-__move_backward(_Tp* __first, _Tp* __last, _Up* __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
 _BidirectionalIterator2
 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
               _BidirectionalIterator2 __result)
 {
-    return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
+    return _VSTD::copy_backward(_VSTD::make_move_iterator(__first), _VSTD::make_move_iterator(__last), __result);
 }
 
 // iter_swap
 
 // moved to <type_traits> for better swap / noexcept support
 
 // transform
 

include/iterator

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 BidirectionalIterator>  // constexpr in C++17
   constexpr BidirectionalIterator prev(BidirectionalIterator x,
-    typename iterator_traits<BidirectionalIterator>::difference_type n = 1);    
+    typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
 
 template <class Iterator>
 class reverse_iterator
     : public iterator<typename iterator_traits<Iterator>::iterator_category,
                       typename iterator_traits<Iterator>::value_type,
                       typename iterator_traits<Iterator>::difference_type,
                       typename iterator_traits<Iterator>::pointer,
                       typename iterator_traits<Iterator>::reference>

 
 template <class Iterator1, class Iterator2>
 constexpr auto
 operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
 -> decltype(__y.base() - __x.base());   // constexpr in C++17
 
 template <class Iterator>
 constexpr reverse_iterator<Iterator>
-operator+(typename reverse_iterator<Iterator>::difference_type n, 
+operator+(typename reverse_iterator<Iterator>::difference_type n,
           const reverse_iterator<Iterator>& x);   // constexpr in C++17
 
 template <class Iterator>
 constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14, constexpr in C++17
 
 template <class Container>
 class back_insert_iterator
 {

 class move_iterator {
 public:
     typedef Iterator                                              iterator_type;
     typedef typename iterator_traits<Iterator>::difference_type   difference_type;
     typedef Iterator                                              pointer;
     typedef typename iterator_traits<Iterator>::value_type        value_type;
     typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
     typedef value_type&&                                          reference;
- 
     constexpr move_iterator();  // all the constexprs are in C++17
     constexpr explicit move_iterator(Iterator i);
     template <class U>
       constexpr move_iterator(const move_iterator<U>& u);
     template <class U>
       constexpr move_iterator& operator=(const move_iterator<U>& u);
     constexpr iterator_type base() const;
     constexpr reference operator*() const;
     constexpr pointer operator->() const;
     constexpr move_iterator& operator++();
     constexpr move_iterator operator++(int);
     constexpr move_iterator& operator--();
     constexpr move_iterator operator--(int);
-    constexpr move_iterator operator+(difference_type n) const; 
-    constexpr move_iterator& operator+=(difference_type n); 
-    constexpr move_iterator operator-(difference_type n) const; 
-    constexpr move_iterator& operator-=(difference_type n); 
+    constexpr move_iterator operator+(difference_type n) const;
+    constexpr move_iterator& operator+=(difference_type n);
+    constexpr move_iterator operator-(difference_type n) const;
+    constexpr move_iterator& operator-=(difference_type n);
     constexpr unspecified operator[](difference_type n) const;
 private:
     Iterator current; // exposition only
 };
 
 template <class Iterator1, class Iterator2>
 constexpr bool   // constexpr in C++17
 operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

 
 template <class Iterator1, class Iterator2>
 constexpr auto   // constexpr in C++17
 operator-(const move_iterator<Iterator1>& x,
           const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
 
 template <class Iterator>
 constexpr move_iterator<Iterator> operator+(   // constexpr in C++17
-            typename move_iterator<Iterator>::difference_type n, 
+            typename move_iterator<Iterator>::difference_type n,
             const move_iterator<Iterator>& x);
 
 template <class Iterator>   // constexpr in C++17
 constexpr  move_iterator<Iterator> make_move_iterator(const Iterator& i);
 
 
 template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>
 class istream_iterator

 template <class _Tp>
 struct __is_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
 
 template <class _Tp>
 struct __is_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
 
 template <class _Tp>
 struct __is_exactly_input_iterator
-    : public integral_constant<bool, 
-         __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value && 
+    : public integral_constant<bool,
+         __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&
         !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {};
 
 template<class _Category, class _Tp, class _Distance = ptrdiff_t,
          class _Pointer = _Tp*, class _Reference = _Tp&>
 struct _LIBCPP_TEMPLATE_VIS iterator
 {
     typedef _Tp        value_type;
     typedef _Distance  difference_type;

 {
     return __distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category());
 }
 
 template <class _InputIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 typename enable_if
 <
-    __is_input_iterator<_InputIter>::value, 
+    __is_input_iterator<_InputIter>::value,
     _InputIter
 >::type
 next(_InputIter __x,
      typename iterator_traits<_InputIter>::difference_type __n = 1)
 {
     _VSTD::advance(__x, __n);
     return __x;
 }
 
 template <class _BidirectionalIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 typename enable_if
 <
-    __is_bidirectional_iterator<_BidirectionalIter>::value, 
+    __is_bidirectional_iterator<_BidirectionalIter>::value,
     _BidirectionalIter
 >::type
 prev(_BidirectionalIter __x,
      typename iterator_traits<_BidirectionalIter>::difference_type __n = 1)
 {
     _VSTD::advance(__x, -__n);
     return __x;
 }
#endif
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
     move_iterator() : __i() {}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
     explicit move_iterator(_Iter __x) : __i(__x) {}
     template <class _Up>
       _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
       move_iterator(const move_iterator<_Up>& __u) : __i(__u.base()) {}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 _Iter base() const {return __i;}
-    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
     reference operator*() const { return static_cast<reference>(*__i); }
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
     pointer  operator->() const { return __i;}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
     move_iterator& operator++() {++__i; return *this;}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
     move_iterator  operator++(int) {move_iterator __tmp(*this); ++__i; return __tmp;}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
#else
     operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT_DEBUG;
 #endif
 
     template <class _Iter1>
     friend
     __wrap_iter<_Iter1>
     operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT_DEBUG;
 
-    template <class _Ip, class _Op> friend _Op copy(_Ip, _Ip, _Op);
-    template <class _B1, class _B2> friend _B2 copy_backward(_B1, _B1, _B2);
-    template <class _Ip, class _Op> friend _Op move(_Ip, _Ip, _Op);
-    template <class _B1, class _B2> friend _B2 move_backward(_B1, _B1, _B2);
 
-#if _LIBCPP_DEBUG_LEVEL < 2
-    template <class _Tp>
+    template <bool __is_backward, class _CopyTraits, class _Ip, class _Op> friend _Op __do_copy(_Ip, _Ip, _Op);
+
+    template <bool __condition, class _Ip>
     friend
     typename enable_if
     <
-        is_trivially_copy_assignable<_Tp>::value,
-        _Tp*
-    >::type
-    __unwrap_iter(__wrap_iter<_Tp*>);
-#else
-  template <class _Tp>
-  inline _LIBCPP_INLINE_VISIBILITY
-  typename enable_if
-  <
-      is_trivially_copy_assignable<_Tp>::value,
-      __wrap_iter<_Tp*>
+        __condition,
+        typename _Ip::iterator_type
     >::type
-  __unwrap_iter(__wrap_iter<_Tp*> __i);
-#endif
+    __unwrap_iter(_Ip __i);
 };
 
 template <class _Iter1, class _Iter2>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT_DEBUG
 {
     return __x.base() == __y.base();

 {
     __x += __n;
     return __x;
 }
 
 template <class _Iter>
 struct __libcpp_is_trivial_iterator
     : public _LIBCPP_BOOL_CONSTANT(is_pointer<_Iter>::value) {};
-    
 template <class _Iter>
 struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
     : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
 
 template <class _Iter>
 struct __libcpp_is_trivial_iterator<reverse_iterator<_Iter> >
     : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
 

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

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template<InputIterator InIter, OutputIterator<auto, InIter::reference> OutIter>
+//   OutIter
+//   copy(InIter first, InIter last, OutIter result);
+
+#include <algorithm>
+#include <cassert>
+#include <iterator>
+
+#include "test_iterators.h"
+
+namespace {
+
+struct debug
+{
+    static constexpr bool __is_debug = true;
+};
+
+struct release
+{
+    static constexpr bool __is_debug = false;
+};
+
+template <class Mode>
+struct default_test_traits : Mode
+{
+    template <bool, class InIter, class OutIter>
+    static OutIter __memmove(InIter, InIter, OutIter o) {
+        assert(false);
+        return o;
+    }
+
+    template <bool, class InIter, class OutIter>
+    static OutIter __loop(InIter, InIter, OutIter o) {
+        assert(false);
+        return o;
+    }
+};
+
+template <class Mode, bool should_be_backward>
+struct memmove_traits : default_test_traits<Mode>
+{
+    template <bool is_backward, class InIter, class OutIter>
+    static OutIter __memmove(InIter, InIter, OutIter o)
+    {
+        assert(is_backward == should_be_backward);
+        return o;
+    }
+};
+
+template <class Mode, bool should_be_backward>
+struct loop_traits : default_test_traits<Mode>
+{
+    template <bool is_backward, class InIter, class OutIter>
+    static OutIter __loop(InIter, InIter, OutIter o)
+    {
+        assert(is_backward == should_be_backward);
+        return o;
+    }
+};
+
+template <class Mode>
+using should_mmove_fwd = memmove_traits<Mode, false>;
+
+template <class Mode>
+using should_mmove_backward = memmove_traits<Mode, true>;
+
+template <class Mode>
+using should_loop_fwd = loop_traits<Mode, false>;
+
+template <class Mode>
+using should_loop_backward = loop_traits<Mode, true>;
+
+template <bool is_backward, class Traits, class Ip, class Op>
+void test()
+{
+  Op res = _VSTD::__do_copy<is_backward, Traits>(Ip(), Ip(), Op());
+  (void)res;
+}
+
+}  // namespace
+
+int main()
+{
+    constexpr bool fwd = false;
+    constexpr bool backward = true;
+
+    {
+        typedef int* I;
+        typedef int* O;
+
+        test<fwd, should_mmove_fwd<debug>, I, O>();
+        test<fwd, should_mmove_fwd<release>, I, O>();
+        test<backward, should_mmove_backward<debug>, I, O>();
+        test<backward, should_mmove_backward<release>, I, O>();
+    }
+
+    {
+        typedef const int* I;
+        typedef int* O;
+
+        test<fwd, should_mmove_fwd<debug>, I, O>();
+        test<fwd, should_mmove_fwd<release>, I, O>();
+        test<backward, should_mmove_backward<debug>, I, O>();
+        test<backward, should_mmove_backward<release>, I, O>();
+    }
+
+    {
+        typedef std::move_iterator<int*> I;
+        typedef int* O;
+
+        test<fwd, should_mmove_fwd<debug>, I, O>();
+        test<fwd, should_mmove_fwd<release>, I, O>();
+        test<backward, should_mmove_backward<debug>, I, O>();
+        test<backward, should_mmove_backward<release>, I, O>();
+    }
+
+    {
+        typedef std::move_iterator<const int*> I;
+        typedef int* O;
+
+        test<fwd, should_mmove_fwd<debug>, I, O>();
+        test<fwd, should_mmove_fwd<release>, I, O>();
+        test<backward, should_mmove_backward<debug>, I, O>();
+        test<backward, should_mmove_backward<release>, I, O>();
+    }
+
+    {
+        typedef std::move_iterator<std::move_iterator<const int*>> I;
+        typedef int* O;
+
+        test<fwd, should_mmove_fwd<debug>, I, O>();
+        test<fwd, should_mmove_fwd<release>, I, O>();
+        test<backward, should_mmove_backward<debug>, I, O>();
+        test<backward, should_mmove_backward<release>, I, O>();
+    }
+
+    {
+        typedef int* I;
+        typedef _VSTD::__wrap_iter<int*> O;
+
+        test<fwd, should_loop_fwd<debug>, I, O>();
+        test<fwd, should_mmove_fwd<release>, I, O>();
+        test<backward, should_loop_backward<debug>, I, O>();
+        test<backward, should_mmove_backward<release>, I, O>();
+    }
+
+    {
+        typedef _VSTD::__wrap_iter<int*> I;
+        typedef _VSTD::__wrap_iter<int*> O;
+
+        test<fwd, should_loop_fwd<debug>, I, O>();
+        test<fwd, should_mmove_fwd<release>, I, O>();
+        test<backward, should_loop_backward<debug>, I, O>();
+        test<backward, should_mmove_backward<release>, I, O>();
+    }
+
+    {
+        typedef std::move_iterator<_VSTD::__wrap_iter<int*>> I;
+        typedef _VSTD::__wrap_iter<int*> O;
+
+        test<fwd, should_loop_fwd<debug>, I, O>();
+        test<fwd, should_mmove_fwd<release>, I, O>();
+        test<backward, should_loop_backward<debug>, I, O>();
+        test<backward, should_mmove_backward<release>, I, O>();
+    }
+
+    {
+        typedef std::reverse_iterator<int*> I;
+        typedef int* O;
+
+        test<fwd, should_loop_fwd<debug>, I, O>();
+        test<fwd, should_loop_fwd<release>, I, O>();
+        test<backward, should_loop_backward<debug>, I, O>();
+        test<backward, should_loop_backward<release>, I, O>();
+    }
+
+    {
+        typedef std::reverse_iterator<bidirectional_iterator<int*>> I;
+        typedef std::reverse_iterator<int*> O;
+
+        test<fwd, should_loop_backward<debug>, I, O>();
+        test<fwd, should_loop_backward<release>, I, O>();
+        test<backward, should_loop_fwd<debug>, I, O>();
+        test<backward, should_loop_fwd<release>, I, O>();
+    }
+
+    {
+        typedef std::reverse_iterator<int*> I;
+        typedef std::reverse_iterator<int*> O;
+
+        test<fwd, should_mmove_backward<debug>, I, O>();
+        test<fwd, should_mmove_backward<release>, I, O>();
+        test<backward, should_mmove_fwd<debug>, I, O>();
+        test<backward, should_mmove_fwd<release>, I, O>();
+    }
+
+    {
+        typedef std::reverse_iterator<std::move_iterator<std::reverse_iterator<int*>>> I;
+        typedef std::reverse_iterator<std::reverse_iterator<int*>> O;
+
+        test<fwd, should_mmove_fwd<debug>, I, O>();
+        test<fwd, should_mmove_fwd<release>, I, O>();
+        test<backward, should_mmove_backward<debug>, I, O>();
+        test<backward, should_mmove_backward<release>, I, O>();
+    }
+
+    {
+        typedef std::move_iterator<std::reverse_iterator<_VSTD::__wrap_iter<int*>>> I;
+        typedef std::reverse_iterator<_VSTD::__wrap_iter<int*>> O;
+
+        test<fwd, should_loop_backward<debug>, I, O>();
+        test<fwd, should_mmove_backward<release>, I, O>();
+        test<backward, should_loop_fwd<debug>, I, O>();
+        test<backward, should_mmove_fwd<release>, I, O>();
+    }
+}
+