Limit Debug mode impact: overload __niter_base

Message ID c0881e52-910a-2042-0db4-50dd209e72eb@gmail.com
State New
Headers show
Series
  • Limit Debug mode impact: overload __niter_base
Related show

Commit Message

François Dumont June 18, 2018, 9:01 p.m.
Hi

     I abandon the idea of providing Debug algos, it would be too much 
code to add and maintain. However I haven't quit on reducing Debug mode 
performance impact.

     So this patch make use of the existing std::__niter_base to get rid 
of the debug layer around __gnu_debug::vector<>::iterator so that 
__builtin_memmove replacement can take place.

     As _Safe_iterator<> do not have a constructor taking a pointer I 
change algos implementation so that we do not try to instantiate the 
iterator type ourselves but rather rely on its operators + or -.

     The small drawback is that for std::equal algo where we can't use 
the __glibcxx_can_increment we need to keep the debug layer to make sure 
we don't reach past-the-end iterator. So I had to remove usage of 
__niter_base when in Debug mode, doing so it also disable potential 
usage of __builtin_memcmp when calling std::equal on 
std::__cxx1998::vector<> iterators. A rather rare situation I think.

     Note that I don't know how to test that __builtin_memmove has been 
indeed used. So I've been through some debug sessions to check that.

     I am not really happy with ChangeLog entry I came up with, I'll try 
to improve it before this patch is validated.


     * include/bits/stl_algobase.h
     (__copy_move<_IsMove, _IsSimple, random_access_iterator_tag>
     ::__copy_impl): New.
     (__copy_move<_IsMove, _IsSimple, random_access_iterator_tag>
     ::__copy_m): Use latter.
     (__copy_move<_IsMove, true, random_access_iterator_tag>::__copy_m):
     Add __base_res parameter.
     (__copy_move<_IsMove, true, random_access_iterator_tag>::__copy_m): Add
     __res_base parameter and use it to call __builtin_memmove.
     (__copy_move_a): Adapt.
     (__copy_move_a2): Adapt.
     (__copy_move_backward<_IsMove, _IsSimple, random_access_iterator_tag>
     ::__copy_b_impl): New.
     (__copy_move_backward<_IsMove, _IsSimple, random_access_iterator_tag>
     ::__copy_move_b): Use latter.
     (__copy_move_backward<_IsMove, true, random_access_iterator_tag>
     ::__copy_move_b): Add __res_base parameter and use it to call
     __builtin_memmove.
     (__copy_move_backward_a): Adapt.
     (__copy_move_backward_a2): Adapt.
     (__fill_n_a): Add _OI template parameter.
     (std::equal<>(_II1, _II1, _II2)): Remove usage of __niter_base on
     __first2 in _GLIBCXX_DEBUG mode.
     * include/debug/stl_iterator.h
     (std::__niter_base(const __gnu_cxx::_Safe_iterator<
     __gnu_cxx::__normal_iterator<>, _Sequence>&)): New declaration.
     * include/debug/vector (__niter_base(const __gnu_cxx::_Safe_iterator<
     __gnu_cxx::__normal_iterator<>, _Sequence>&)): New.

Tested under x86_64 linux.

Ok to commit ?

François

Comments

Jonathan Wakely June 26, 2018, 4:03 p.m. | #1
On 18/06/18 23:01 +0200, François Dumont wrote:
>Hi

>

>    I abandon the idea of providing Debug algos, it would be too much 

>code to add and maintain. However I haven't quit on reducing Debug 

>mode performance impact.

>

>    So this patch make use of the existing std::__niter_base to get 

>rid of the debug layer around __gnu_debug::vector<>::iterator so that 

>__builtin_memmove replacement can take place.

>

>    As _Safe_iterator<> do not have a constructor taking a pointer I 

>change algos implementation so that we do not try to instantiate the 

>iterator type ourselves but rather rely on its operators + or -.

>

>    The small drawback is that for std::equal algo where we can't use 

>the __glibcxx_can_increment we need to keep the debug layer to make 

>sure we don't reach past-the-end iterator. So I had to remove usage of 

>__niter_base when in Debug mode, doing so it also disable potential 

>usage of __builtin_memcmp when calling std::equal on 

>std::__cxx1998::vector<> iterators. A rather rare situation I think.

>

>    Note that I don't know how to test that __builtin_memmove has been 

>indeed used. So I've been through some debug sessions to check that.


The attached patch (not fully tested) seems to be a much simpler way
to achieve the same thing. Instead of modifying all the helper
structs, just define a new function to re-wrap the result into the
desired iterator type.


>diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h

>index a6a2a76..eca7203 100644

>--- a/libstdc++-v3/include/debug/stl_iterator.h

>+++ b/libstdc++-v3/include/debug/stl_iterator.h

>@@ -120,4 +120,19 @@ namespace __gnu_debug

> #endif

> }

> 

>+#if __cplusplus >= 201103L

>+namespace std

>+{

>+_GLIBCXX_BEGIN_NAMESPACE_VERSION

>+

>+template<typename _Iterator, typename _Container, typename _Sequence>

>+    _Iterator

>+    __niter_base(const __gnu_debug::_Safe_iterator<

>+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,

>+		 _Sequence>&);

>+

>+_GLIBCXX_END_NAMESPACE_VERSION

>+}

>+#endif


Why is this overload only defined for C++11 and later? I defined it
unconditionally in the attached patch.

What do you think?
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 022a3f1598b..91d673e6c81 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -415,13 +415,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
 		   istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
 
+#ifdef _GLIBCXX_DEBUG
+  template<typename _Base, typename _Seq, typename _From>
+    inline __gnu_debug::_Safe_iterator<_Base, _Seq>
+    __wrap_iter(__gnu_debug::_Safe_iterator<_Base, _Seq> __safe, _From __from)
+    {
+      return __gnu_debug::_Safe_iterator<_Base, _Seq>(_Base(__from),
+						   __safe._M_sequence);
+    }
+#endif
+
+  template<typename _To, typename _From>
+    inline _To
+    __wrap_iter(_To, _From __from)
+    { return _To(__from); }
+
   template<bool _IsMove, typename _II, typename _OI>
     inline _OI
     __copy_move_a2(_II __first, _II __last, _OI __result)
     {
-      return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
-					     std::__niter_base(__last),
-					     std::__niter_base(__result)));
+      return std::__wrap_iter(__result,
+	  std::__copy_move_a<_IsMove>(std::__niter_base(__first),
+				      std::__niter_base(__last),
+				      std::__niter_base(__result)));
     }
 
   /**
@@ -593,9 +609,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _BI2
     __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
     {
-      return _BI2(std::__copy_move_backward_a<_IsMove>
-		  (std::__niter_base(__first), std::__niter_base(__last),
-		   std::__niter_base(__result)));
+      return std::__wrap_iter(__result,
+	  std::__copy_move_backward_a<_IsMove>(std::__niter_base(__first),
+					       std::__niter_base(__last),
+					       std::__niter_base(__result)));
     }
 
   /**
@@ -785,7 +802,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
       __glibcxx_requires_can_increment(__first, __n);
 
-      return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
+      return std::__wrap_iter(__first,
+	  std::__fill_n_a(std::__niter_base(__first), __n, __value));
     }
 
   template<bool _BoolType>
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index a6a2a762766..431293bdec9 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -118,6 +118,19 @@ namespace __gnu_debug
     -> decltype(std::make_move_iterator(__base(__it.base())))
     { return std::make_move_iterator(__base(__it.base())); }
 #endif
-}
+} // namespace __gnu_debug
+
+namespace std
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>&);
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
 
 #endif
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 8d60da328e1..54697030974 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -784,7 +784,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     };
 
 _GLIBCXX_END_NAMESPACE_VERSION
-#endif
+#endif // C++11
+
+ template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>& __it)
+    { return std::__niter_base(__it.base()); }
 
 } // namespace std
Jonathan Wakely June 27, 2018, 12:13 a.m. | #2
On 26/06/18 17:03 +0100, Jonathan Wakely wrote:
>On 18/06/18 23:01 +0200, François Dumont wrote:

>>Hi

>>

>>    I abandon the idea of providing Debug algos, it would be too 

>>much code to add and maintain. However I haven't quit on reducing 

>>Debug mode performance impact.

>>

>>    So this patch make use of the existing std::__niter_base to get 

>>rid of the debug layer around __gnu_debug::vector<>::iterator so 

>>that __builtin_memmove replacement can take place.

>>

>>    As _Safe_iterator<> do not have a constructor taking a pointer I 

>>change algos implementation so that we do not try to instantiate the 

>>iterator type ourselves but rather rely on its operators + or -.

>>

>>    The small drawback is that for std::equal algo where we can't 

>>use the __glibcxx_can_increment we need to keep the debug layer to 

>>make sure we don't reach past-the-end iterator. So I had to remove 

>>usage of __niter_base when in Debug mode, doing so it also disable 

>>potential usage of __builtin_memcmp when calling std::equal on 

>>std::__cxx1998::vector<> iterators. A rather rare situation I think.


We don't need to give up all checks in std::equal, we can do this:

@@ -1044,7 +1085,13 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
            typename iterator_traits<_II1>::value_type,
            typename iterator_traits<_II2>::value_type>)
       __glibcxx_requires_valid_range(__first1, __last1);
-
+#ifdef _GLIBCXX_DEBUG
+      typedef typename iterator_traits<_II1>::iterator_category _Cat1;
+      typedef typename iterator_traits<_II2>::iterator_category _Cat2;
+      if (!__are_same<_Cat1, input_iterator_tag>::__value
+         && __are_same<_Cat2, random_access_iterator_tag>::__value)
+       __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
+#endif
       return std::__equal_aux(std::__niter_base(__first1),
                              std::__niter_base(__last1),
                              std::__niter_base(__first2));



>>    Note that I don't know how to test that __builtin_memmove has 

>>been indeed used. So I've been through some debug sessions to check 

>>that.

>

>The attached patch (not fully tested) seems to be a much simpler way

>to achieve the same thing. Instead of modifying all the helper

>structs, just define a new function to re-wrap the result into the

>desired iterator type.

>

>

>>diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h

>>index a6a2a76..eca7203 100644

>>--- a/libstdc++-v3/include/debug/stl_iterator.h

>>+++ b/libstdc++-v3/include/debug/stl_iterator.h

>>@@ -120,4 +120,19 @@ namespace __gnu_debug

>>#endif

>>}

>>

>>+#if __cplusplus >= 201103L

>>+namespace std

>>+{

>>+_GLIBCXX_BEGIN_NAMESPACE_VERSION

>>+

>>+template<typename _Iterator, typename _Container, typename _Sequence>

>>+    _Iterator

>>+    __niter_base(const __gnu_debug::_Safe_iterator<

>>+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,

>>+		 _Sequence>&);

>>+

>>+_GLIBCXX_END_NAMESPACE_VERSION

>>+}

>>+#endif

>

>Why is this overload only defined for C++11 and later? I defined it

>unconditionally in the attached patch.

>

>What do you think?


Here's a complete patch that passes all tests in normal mode and
causes no regressions in debug mode (we already have some debug test
failing).

I wondered whether we need another overload of __wrap_iter for
handling move_iterator, but I think the first overload works OK.
commit 8c22777c71589de7351b34ed4e94f3d3d2a216ee
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Jun 26 18:07:26 2018 +0100

    Unwrap debug mode vector iterators to use optimized algorithms
    
    By defining __niter_base for iterators from debug mode vectors more
    algorithms can use the optimized implementations using memcpy or memset.
    The new function __wrap_iter converts back to the original iterator
    type, handling the case where it's a debug mode iterator and needs a
    pointer to the container.
    
    2018-06-27  Fran??ois Dumont  <fdumont@gcc.gnu.org>
                Jonathan Wakely  <jwakely@redhat.com>
    
            * include/bits/stl_algobase.h (__wrap_iter<_To, _From>): Define new
            function to convert unwrapped iterator back to result type.
            [_GLIBCXX_DEBUG] (__wrap_iter<_Iter,_Seq, _From>): Overload for
            converting to _Safe_iterator.
            [_GLIBCXX_DEBUG] (__wrap_iter<_Iter,_Seq>): Overload for converting
            from reverse_iterator<I> to reverse_iterator<_Safe_iterator<I,S>>.
            (__copy_move_a2, __copy_move_backward_a2, fill_n): Use __wrap_iter.
            [_GLIBCXX_DEBUG] (equal<_II1, _II2>(_II1, _II1, _II2)): Use
            __glibcxx_requires_can_increment_range to check for valid ranges.
            * include/debug/stl_iterator.h (__niter_base): Declare overload for
            iterators from debug mode vector.
            * include/debug/vector (__niter_base): Define.

diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 022a3f1598b..31b2801d749 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -415,13 +415,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
 		   istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
 
+  // Convert an iterator of type _From to an iterator of type _To.
+  // e.g. from int* to __normal_iterator<int*, Seq>.
+  template<typename _To, typename _From>
+    inline _To
+    __wrap_iter(_To, _From __from)
+    { return _To(__from); }
+
+#ifdef _GLIBCXX_DEBUG
+  // Convert an iterator of type _From to a safe iterator
+  // for the same sequence as __to.
+  template<typename _Iter, typename _Seq, typename _From>
+    inline __gnu_debug::_Safe_iterator<_Iter, _Seq>
+    __wrap_iter(__gnu_debug::_Safe_iterator<_Iter, _Seq> __to, _From __from)
+    {
+      return __gnu_debug::_Safe_iterator<_Iter, _Seq>(_Iter(__from),
+						      __to._M_sequence);
+    }
+
+  // Conversion from reverse_iterator<> to reverse_iterator<_Safe_iterator<>>
+  template<typename _Iter, typename _Seq, typename _From>
+    inline reverse_iterator<__gnu_debug::_Safe_iterator<_Iter, _Seq> >
+    __wrap_iter(
+	reverse_iterator<__gnu_debug::_Safe_iterator<_Iter, _Seq> > __to,
+	reverse_iterator<_From> __from)
+    {
+      typedef __gnu_debug::_Safe_iterator<_Iter, _Seq> _Safe;
+      typedef reverse_iterator<_Safe> _RevIter;
+      return _RevIter(_Safe(_Iter(__from.base()), __to.base()._M_sequence));
+    }
+
+  // No conversion needed when already a safe iterator.
+  template<typename _Iter, typename _Seq>
+    inline __gnu_debug::_Safe_iterator<_Iter, _Seq>
+    __wrap_iter(__gnu_debug::_Safe_iterator<_Iter, _Seq>,
+		__gnu_debug::_Safe_iterator<_Iter, _Seq> __iter)
+    { return __iter; }
+#endif
+
   template<bool _IsMove, typename _II, typename _OI>
     inline _OI
     __copy_move_a2(_II __first, _II __last, _OI __result)
     {
-      return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
-					     std::__niter_base(__last),
-					     std::__niter_base(__result)));
+      return std::__wrap_iter(__result,
+	  std::__copy_move_a<_IsMove>(std::__niter_base(__first),
+				      std::__niter_base(__last),
+				      std::__niter_base(__result)));
     }
 
   /**
@@ -593,9 +632,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _BI2
     __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
     {
-      return _BI2(std::__copy_move_backward_a<_IsMove>
-		  (std::__niter_base(__first), std::__niter_base(__last),
-		   std::__niter_base(__result)));
+      return std::__wrap_iter(__result,
+	  std::__copy_move_backward_a<_IsMove>(std::__niter_base(__first),
+					       std::__niter_base(__last),
+					       std::__niter_base(__result)));
     }
 
   /**
@@ -785,7 +825,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
       __glibcxx_requires_can_increment(__first, __n);
 
-      return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
+      return std::__wrap_iter(__first,
+	  std::__fill_n_a(std::__niter_base(__first), __n, __value));
     }
 
   template<bool _BoolType>
@@ -1044,7 +1085,13 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_II1>::value_type,
 	    typename iterator_traits<_II2>::value_type>)
       __glibcxx_requires_valid_range(__first1, __last1);
-
+#ifdef _GLIBCXX_DEBUG
+      typedef typename iterator_traits<_II1>::iterator_category _Cat1;
+      typedef typename iterator_traits<_II2>::iterator_category _Cat2;
+      if (!__are_same<_Cat1, input_iterator_tag>::__value
+	  && __are_same<_Cat2, random_access_iterator_tag>::__value)
+	__glibcxx_requires_can_increment_range(__first1, __last1, __first2);
+#endif
       return std::__equal_aux(std::__niter_base(__first1),
 			      std::__niter_base(__last1),
 			      std::__niter_base(__first2));
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index a6a2a762766..431293bdec9 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -118,6 +118,19 @@ namespace __gnu_debug
     -> decltype(std::make_move_iterator(__base(__it.base())))
     { return std::make_move_iterator(__base(__it.base())); }
 #endif
-}
+} // namespace __gnu_debug
+
+namespace std
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>&);
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
 
 #endif
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 8d60da328e1..54697030974 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -784,7 +784,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     };
 
 _GLIBCXX_END_NAMESPACE_VERSION
-#endif
+#endif // C++11
+
+ template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>& __it)
+    { return std::__niter_base(__it.base()); }
 
 } // namespace std
François Dumont June 27, 2018, 7:03 p.m. | #3
On 26/06/2018 18:03, Jonathan Wakely wrote:
> On 18/06/18 23:01 +0200, François Dumont wrote:

>> Hi

>>

>>     I abandon the idea of providing Debug algos, it would be too much 

>> code to add and maintain. However I haven't quit on reducing Debug 

>> mode performance impact.

>>

>>     So this patch make use of the existing std::__niter_base to get 

>> rid of the debug layer around __gnu_debug::vector<>::iterator so that 

>> __builtin_memmove replacement can take place.

>>

>>     As _Safe_iterator<> do not have a constructor taking a pointer I 

>> change algos implementation so that we do not try to instantiate the 

>> iterator type ourselves but rather rely on its operators + or -.

>>

>>     The small drawback is that for std::equal algo where we can't use 

>> the __glibcxx_can_increment we need to keep the debug layer to make 

>> sure we don't reach past-the-end iterator. So I had to remove usage 

>> of __niter_base when in Debug mode, doing so it also disable 

>> potential usage of __builtin_memcmp when calling std::equal on 

>> std::__cxx1998::vector<> iterators. A rather rare situation I think.

>>

>>     Note that I don't know how to test that __builtin_memmove has 

>> been indeed used. So I've been through some debug sessions to check 

>> that.

>

> The attached patch (not fully tested) seems to be a much simpler way

> to achieve the same thing. Instead of modifying all the helper

> structs, just define a new function to re-wrap the result into the

> desired iterator type.


Through my proposal I tried to limit the presence of Debug code in the 
normal mode code. If you prefer to preserve existing code it is indeed a 
simpler approach.

>

>

>> diff --git a/libstdc++-v3/include/debug/stl_iterator.h 

>> b/libstdc++-v3/include/debug/stl_iterator.h

>> index a6a2a76..eca7203 100644

>> --- a/libstdc++-v3/include/debug/stl_iterator.h

>> +++ b/libstdc++-v3/include/debug/stl_iterator.h

>> @@ -120,4 +120,19 @@ namespace __gnu_debug

>> #endif

>> }

>>

>> +#if __cplusplus >= 201103L

>> +namespace std

>> +{

>> +_GLIBCXX_BEGIN_NAMESPACE_VERSION

>> +

>> +template<typename _Iterator, typename _Container, typename _Sequence>

>> +    _Iterator

>> +    __niter_base(const __gnu_debug::_Safe_iterator<

>> +         __gnu_cxx::__normal_iterator<_Iterator, _Container>,

>> +         _Sequence>&);

>> +

>> +_GLIBCXX_END_NAMESPACE_VERSION

>> +}

>> +#endif

>

> Why is this overload only defined for C++11 and later? I defined it

> unconditionally in the attached patch.


I initially wrote something like:
template<typename _Iterator, typename _Sequence>
     inline auto
     __niter_base(const __gnu_debug::_Safe_iterator<_Iterator, 
_Container>& __it)
     -> decltype(__niter_base(__it.base()))
     { return __niter_base(__it.base()); }

which require C++11

I forgot to remove the __cplusplus check when I eventually use a more 
specific overload.

>

> What do you think?

>

>

Yes, that is a fine approach. Do you wat to apply it or do you want me 
to work on it a little and re-submit the patch ?

François
Jonathan Wakely June 27, 2018, 7:17 p.m. | #4
On 27/06/18 21:03 +0200, François Dumont wrote:
>On 26/06/2018 18:03, Jonathan Wakely wrote:

>>On 18/06/18 23:01 +0200, François Dumont wrote:

>>>Hi

>>>

>>>    I abandon the idea of providing Debug algos, it would be too 

>>>much code to add and maintain. However I haven't quit on reducing 

>>>Debug mode performance impact.

>>>

>>>    So this patch make use of the existing std::__niter_base to 

>>>get rid of the debug layer around __gnu_debug::vector<>::iterator 

>>>so that __builtin_memmove replacement can take place.

>>>

>>>    As _Safe_iterator<> do not have a constructor taking a pointer 

>>>I change algos implementation so that we do not try to instantiate 

>>>the iterator type ourselves but rather rely on its operators + or 

>>>-.

>>>

>>>    The small drawback is that for std::equal algo where we can't 

>>>use the __glibcxx_can_increment we need to keep the debug layer to 

>>>make sure we don't reach past-the-end iterator. So I had to remove 

>>>usage of __niter_base when in Debug mode, doing so it also disable 

>>>potential usage of __builtin_memcmp when calling std::equal on 

>>>std::__cxx1998::vector<> iterators. A rather rare situation I 

>>>think.

>>>

>>>    Note that I don't know how to test that __builtin_memmove has 

>>>been indeed used. So I've been through some debug sessions to 

>>>check that.

>>

>>The attached patch (not fully tested) seems to be a much simpler way

>>to achieve the same thing. Instead of modifying all the helper

>>structs, just define a new function to re-wrap the result into the

>>desired iterator type.

>

>Through my proposal I tried to limit the presence of Debug code in the 

>normal mode code. If you prefer to preserve existing code it is indeed 

>a simpler approach.


But to avoid any dependency on _GLIBCXX_DEBUG you had to make more
changes in more places, and complicate all the helper structs.

If we really want to avoid the #ifdef _GLIBCXX_DEBUG code in
<bits/stl_algobase.h> we could move the debug mode overloads into
<debug/stl_iterator.h>. I don't feel strongly about that, I think it's
OK in <bits/stl_algobase.h> and would be OK in the debug header too
(assuming it still works).


>>>diff --git a/libstdc++-v3/include/debug/stl_iterator.h 

>>>b/libstdc++-v3/include/debug/stl_iterator.h

>>>index a6a2a76..eca7203 100644

>>>--- a/libstdc++-v3/include/debug/stl_iterator.h

>>>+++ b/libstdc++-v3/include/debug/stl_iterator.h

>>>@@ -120,4 +120,19 @@ namespace __gnu_debug

>>>#endif

>>>}

>>>

>>>+#if __cplusplus >= 201103L

>>>+namespace std

>>>+{

>>>+_GLIBCXX_BEGIN_NAMESPACE_VERSION

>>>+

>>>+template<typename _Iterator, typename _Container, typename _Sequence>

>>>+    _Iterator

>>>+    __niter_base(const __gnu_debug::_Safe_iterator<

>>>+         __gnu_cxx::__normal_iterator<_Iterator, _Container>,

>>>+         _Sequence>&);

>>>+

>>>+_GLIBCXX_END_NAMESPACE_VERSION

>>>+}

>>>+#endif

>>

>>Why is this overload only defined for C++11 and later? I defined it

>>unconditionally in the attached patch.

>

>I initially wrote something like:

>template<typename _Iterator, typename _Sequence>

>    inline auto

>    __niter_base(const __gnu_debug::_Safe_iterator<_Iterator, 

>_Container>& __it)

>    -> decltype(__niter_base(__it.base()))

>    { return __niter_base(__it.base()); }

>

>which require C++11

>

>I forgot to remove the __cplusplus check when I eventually use a more 

>specific overload.


Ah OK, I wondered if there was some reason I had missed.


>>

>>What do you think?

>>

>>

>Yes, that is a fine approach. Do you wat to apply it or do you want me 

>to work on it a little and re-submit the patch ?


I sent a follow-up with a complete patch that passes the testsuite.
I'm happy with that version of the patch, but do you have any
suggestions to improve it?
François Dumont June 27, 2018, 7:25 p.m. | #5
On 27/06/2018 02:13, Jonathan Wakely wrote:
> On 26/06/18 17:03 +0100, Jonathan Wakely wrote:

>> On 18/06/18 23:01 +0200, François Dumont wrote:

>>> Hi

>>>

>>>     I abandon the idea of providing Debug algos, it would be too 

>>> much code to add and maintain. However I haven't quit on reducing 

>>> Debug mode performance impact.

>>>

>>>     So this patch make use of the existing std::__niter_base to get 

>>> rid of the debug layer around __gnu_debug::vector<>::iterator so 

>>> that __builtin_memmove replacement can take place.

>>>

>>>     As _Safe_iterator<> do not have a constructor taking a pointer I 

>>> change algos implementation so that we do not try to instantiate the 

>>> iterator type ourselves but rather rely on its operators + or -.

>>>

>>>     The small drawback is that for std::equal algo where we can't 

>>> use the __glibcxx_can_increment we need to keep the debug layer to 

>>> make sure we don't reach past-the-end iterator. So I had to remove 

>>> usage of __niter_base when in Debug mode, doing so it also disable 

>>> potential usage of __builtin_memcmp when calling std::equal on 

>>> std::__cxx1998::vector<> iterators. A rather rare situation I think.

>

> We don't need to give up all checks in std::equal, we can do this:

>

> @@ -1044,7 +1085,13 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO

>            typename iterator_traits<_II1>::value_type,

>            typename iterator_traits<_II2>::value_type>)

>       __glibcxx_requires_valid_range(__first1, __last1);

> -

> +#ifdef _GLIBCXX_DEBUG

> +      typedef typename iterator_traits<_II1>::iterator_category _Cat1;

> +      typedef typename iterator_traits<_II2>::iterator_category _Cat2;

> +      if (!__are_same<_Cat1, input_iterator_tag>::__value

> +         && __are_same<_Cat2, random_access_iterator_tag>::__value)

> +       __glibcxx_requires_can_increment_range(__first1, __last1, 

> __first2);

> +#endif

>       return std::__equal_aux(std::__niter_base(__first1),

>                              std::__niter_base(__last1),

>                              std::__niter_base(__first2));


We don't give up any check. We only give up on using the 
__builtin_memcmp when std::equal is being used while Debug mode is 
active and std::equal is called directly with std::__cxx1998::vector.

Moreover this check is wrong and will introduce regression when running 
testsuite in Debug mode (this is why I know). It will assert in the 
following case:
vector<int> v1 { 0, 0, 0 };
vector<int> v2 { 0, 1 };
equal(v1.begin(), v1.end(), v2.begin());

>

>

>

>>>     Note that I don't know how to test that __builtin_memmove has 

>>> been indeed used. So I've been through some debug sessions to check 

>>> that.

>>

>> The attached patch (not fully tested) seems to be a much simpler way

>> to achieve the same thing. Instead of modifying all the helper

>> structs, just define a new function to re-wrap the result into the

>> desired iterator type.

>>

>>

>>> diff --git a/libstdc++-v3/include/debug/stl_iterator.h 

>>> b/libstdc++-v3/include/debug/stl_iterator.h

>>> index a6a2a76..eca7203 100644

>>> --- a/libstdc++-v3/include/debug/stl_iterator.h

>>> +++ b/libstdc++-v3/include/debug/stl_iterator.h

>>> @@ -120,4 +120,19 @@ namespace __gnu_debug

>>> #endif

>>> }

>>>

>>> +#if __cplusplus >= 201103L

>>> +namespace std

>>> +{

>>> +_GLIBCXX_BEGIN_NAMESPACE_VERSION

>>> +

>>> +template<typename _Iterator, typename _Container, typename _Sequence>

>>> +    _Iterator

>>> +    __niter_base(const __gnu_debug::_Safe_iterator<

>>> +         __gnu_cxx::__normal_iterator<_Iterator, _Container>,

>>> +         _Sequence>&);

>>> +

>>> +_GLIBCXX_END_NAMESPACE_VERSION

>>> +}

>>> +#endif

>>

>> Why is this overload only defined for C++11 and later? I defined it

>> unconditionally in the attached patch.

>>

>> What do you think?

>

> Here's a complete patch that passes all tests in normal mode and

> causes no regressions in debug mode (we already have some debug test

> failing).

>

> I wondered whether we need another overload of __wrap_iter for

> handling move_iterator, but I think the first overload works OK.

>

>

I don't think we need it neither. Algos that handle move iterator are 
already doing it.

François
Jonathan Wakely June 27, 2018, 8:02 p.m. | #6
On 27/06/18 21:25 +0200, François Dumont wrote:
>On 27/06/2018 02:13, Jonathan Wakely wrote:

>>On 26/06/18 17:03 +0100, Jonathan Wakely wrote:

>>>On 18/06/18 23:01 +0200, François Dumont wrote:

>>>>Hi

>>>>

>>>>    I abandon the idea of providing Debug algos, it would be too 

>>>>much code to add and maintain. However I haven't quit on 

>>>>reducing Debug mode performance impact.

>>>>

>>>>    So this patch make use of the existing std::__niter_base to 

>>>>get rid of the debug layer around 

>>>>__gnu_debug::vector<>::iterator so that __builtin_memmove 

>>>>replacement can take place.

>>>>

>>>>    As _Safe_iterator<> do not have a constructor taking a 

>>>>pointer I change algos implementation so that we do not try to 

>>>>instantiate the iterator type ourselves but rather rely on its 

>>>>operators + or -.

>>>>

>>>>    The small drawback is that for std::equal algo where we 

>>>>can't use the __glibcxx_can_increment we need to keep the debug 

>>>>layer to make sure we don't reach past-the-end iterator. So I 

>>>>had to remove usage of __niter_base when in Debug mode, doing so 

>>>>it also disable potential usage of __builtin_memcmp when calling 

>>>>std::equal on std::__cxx1998::vector<> iterators. A rather rare 

>>>>situation I think.

>>

>>We don't need to give up all checks in std::equal, we can do this:

>>

>>@@ -1044,7 +1085,13 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO

>>           typename iterator_traits<_II1>::value_type,

>>           typename iterator_traits<_II2>::value_type>)

>>      __glibcxx_requires_valid_range(__first1, __last1);

>>-

>>+#ifdef _GLIBCXX_DEBUG

>>+      typedef typename iterator_traits<_II1>::iterator_category _Cat1;

>>+      typedef typename iterator_traits<_II2>::iterator_category _Cat2;

>>+      if (!__are_same<_Cat1, input_iterator_tag>::__value

>>+         && __are_same<_Cat2, random_access_iterator_tag>::__value)

>>+       __glibcxx_requires_can_increment_range(__first1, __last1, 

>>__first2);

>>+#endif

>>      return std::__equal_aux(std::__niter_base(__first1),

>>                             std::__niter_base(__last1),

>>                             std::__niter_base(__first2));

>

>We don't give up any check.


We do for my version of the patch, because with the new __niter_base
overload the debug layer gets removed. Your patch kept the checking by
not removing the debug layer, but loses the memcmp optimization.

My suggestion above removes the debug layer so uses the optimization,
but adds a separate range check, so we still get checking as well.

>We only give up on using the 

>__builtin_memcmp when std::equal is being used while Debug mode is 

>active and std::equal is called directly with std::__cxx1998::vector.

>

>Moreover this check is wrong and will introduce regression when 

>running testsuite in Debug mode (this is why I know). It will assert 

>in the following case:

>vector<int> v1 { 0, 0, 0 };

>vector<int> v2 { 0, 1 };

>equal(v1.begin(), v1.end(), v2.begin());


We should assert for that test, it's undefined behaviour.


>

>>

>>

>>

>>>>    Note that I don't know how to test that __builtin_memmove 

>>>>has been indeed used. So I've been through some debug sessions 

>>>>to check that.

>>>

>>>The attached patch (not fully tested) seems to be a much simpler way

>>>to achieve the same thing. Instead of modifying all the helper

>>>structs, just define a new function to re-wrap the result into the

>>>desired iterator type.

>>>

>>>

>>>>diff --git a/libstdc++-v3/include/debug/stl_iterator.h 

>>>>b/libstdc++-v3/include/debug/stl_iterator.h

>>>>index a6a2a76..eca7203 100644

>>>>--- a/libstdc++-v3/include/debug/stl_iterator.h

>>>>+++ b/libstdc++-v3/include/debug/stl_iterator.h

>>>>@@ -120,4 +120,19 @@ namespace __gnu_debug

>>>>#endif

>>>>}

>>>>

>>>>+#if __cplusplus >= 201103L

>>>>+namespace std

>>>>+{

>>>>+_GLIBCXX_BEGIN_NAMESPACE_VERSION

>>>>+

>>>>+template<typename _Iterator, typename _Container, typename _Sequence>

>>>>+    _Iterator

>>>>+    __niter_base(const __gnu_debug::_Safe_iterator<

>>>>+         __gnu_cxx::__normal_iterator<_Iterator, _Container>,

>>>>+         _Sequence>&);

>>>>+

>>>>+_GLIBCXX_END_NAMESPACE_VERSION

>>>>+}

>>>>+#endif

>>>

>>>Why is this overload only defined for C++11 and later? I defined it

>>>unconditionally in the attached patch.

>>>

>>>What do you think?

>>

>>Here's a complete patch that passes all tests in normal mode and

>>causes no regressions in debug mode (we already have some debug test

>>failing).

>>

>>I wondered whether we need another overload of __wrap_iter for

>>handling move_iterator, but I think the first overload works OK.

>>

>>

>I don't think we need it neither. Algos that handle move iterator are 

>already doing it.


OK great.
François Dumont June 27, 2018, 8:33 p.m. | #7
On 27/06/2018 22:02, Jonathan Wakely wrote:
> On 27/06/18 21:25 +0200, François Dumont wrote:

>> On 27/06/2018 02:13, Jonathan Wakely wrote:

>>> On 26/06/18 17:03 +0100, Jonathan Wakely wrote:

>>>> On 18/06/18 23:01 +0200, François Dumont wrote:

>>>>> Hi

>>>>>

>>>>>     I abandon the idea of providing Debug algos, it would be too 

>>>>> much code to add and maintain. However I haven't quit on reducing 

>>>>> Debug mode performance impact.

>>>>>

>>>>>     So this patch make use of the existing std::__niter_base to 

>>>>> get rid of the debug layer around __gnu_debug::vector<>::iterator 

>>>>> so that __builtin_memmove replacement can take place.

>>>>>

>>>>>     As _Safe_iterator<> do not have a constructor taking a pointer 

>>>>> I change algos implementation so that we do not try to instantiate 

>>>>> the iterator type ourselves but rather rely on its operators + or -.

>>>>>

>>>>>     The small drawback is that for std::equal algo where we can't 

>>>>> use the __glibcxx_can_increment we need to keep the debug layer to 

>>>>> make sure we don't reach past-the-end iterator. So I had to remove 

>>>>> usage of __niter_base when in Debug mode, doing so it also disable 

>>>>> potential usage of __builtin_memcmp when calling std::equal on 

>>>>> std::__cxx1998::vector<> iterators. A rather rare situation I think.

>>>

>>> We don't need to give up all checks in std::equal, we can do this:

>>>

>>> @@ -1044,7 +1085,13 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO

>>>            typename iterator_traits<_II1>::value_type,

>>>            typename iterator_traits<_II2>::value_type>)

>>>       __glibcxx_requires_valid_range(__first1, __last1);

>>> -

>>> +#ifdef _GLIBCXX_DEBUG

>>> +      typedef typename iterator_traits<_II1>::iterator_category _Cat1;

>>> +      typedef typename iterator_traits<_II2>::iterator_category _Cat2;

>>> +      if (!__are_same<_Cat1, input_iterator_tag>::__value

>>> +         && __are_same<_Cat2, random_access_iterator_tag>::__value)

>>> +       __glibcxx_requires_can_increment_range(__first1, __last1, 

>>> __first2);

>>> +#endif

>>>       return std::__equal_aux(std::__niter_base(__first1),

>>>                              std::__niter_base(__last1),

>>>                              std::__niter_base(__first2));

>>

>> We don't give up any check.

>

> We do for my version of the patch, because with the new __niter_base

> overload the debug layer gets removed. Your patch kept the checking by

> not removing the debug layer, but loses the memcmp optimization.

>

> My suggestion above removes the debug layer so uses the optimization,

> but adds a separate range check, so we still get checking as well.

>

>> We only give up on using the __builtin_memcmp when std::equal is 

>> being used while Debug mode is active and std::equal is called 

>> directly with std::__cxx1998::vector.

>>

>> Moreover this check is wrong and will introduce regression when 

>> running testsuite in Debug mode (this is why I know). It will assert 

>> in the following case:

>> vector<int> v1 { 0, 0, 0 };

>> vector<int> v2 { 0, 1 };

>> equal(v1.begin(), v1.end(), v2.begin());

>

> We should assert for that test, it's undefined behaviour.


Oh, ok, then __glibcxx_requires_can_increment_range can be called 
unconditionnaly. It already takes care of doing the right thing.

And some tests might need to be fixed because they contain this 
undefined behavior. I'll do it.

François
François Dumont July 1, 2018, 7:20 p.m. | #8
Here is a new proposal between yours and mine.

     It is still adding a function to wrap what __niter_base unwrap, I 
called it __nwrap_iter for this reason. But it takes advantage of 
knowing that __niter_base will only unwrap random access iterator to use 
an expression to that will do the right thing, no matter the original 
iterator type.

     I eventually found no issue in the testsuite, despite the 
std::equal change. I might have had a local invalid test.

     Ok to commit ?

François


On 27/06/2018 22:02, Jonathan Wakely wrote:
> On 27/06/18 21:25 +0200, François Dumont wrote:

>> On 27/06/2018 02:13, Jonathan Wakely wrote:

>>> On 26/06/18 17:03 +0100, Jonathan Wakely wrote:

>>>> On 18/06/18 23:01 +0200, François Dumont wrote:

>>>>> Hi

>>>>>

>>>>>     I abandon the idea of providing Debug algos, it would be too 

>>>>> much code to add and maintain. However I haven't quit on reducing 

>>>>> Debug mode performance impact.

>>>>>

>>>>>     So this patch make use of the existing std::__niter_base to 

>>>>> get rid of the debug layer around __gnu_debug::vector<>::iterator 

>>>>> so that __builtin_memmove replacement can take place.

>>>>>

>>>>>     As _Safe_iterator<> do not have a constructor taking a pointer 

>>>>> I change algos implementation so that we do not try to instantiate 

>>>>> the iterator type ourselves but rather rely on its operators + or -.

>>>>>

>>>>>     The small drawback is that for std::equal algo where we can't 

>>>>> use the __glibcxx_can_increment we need to keep the debug layer to 

>>>>> make sure we don't reach past-the-end iterator. So I had to remove 

>>>>> usage of __niter_base when in Debug mode, doing so it also disable 

>>>>> potential usage of __builtin_memcmp when calling std::equal on 

>>>>> std::__cxx1998::vector<> iterators. A rather rare situation I think.

>>>

>>> We don't need to give up all checks in std::equal, we can do this:

>>>

>>> @@ -1044,7 +1085,13 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO

>>>            typename iterator_traits<_II1>::value_type,

>>>            typename iterator_traits<_II2>::value_type>)

>>>       __glibcxx_requires_valid_range(__first1, __last1);

>>> -

>>> +#ifdef _GLIBCXX_DEBUG

>>> +      typedef typename iterator_traits<_II1>::iterator_category _Cat1;

>>> +      typedef typename iterator_traits<_II2>::iterator_category _Cat2;

>>> +      if (!__are_same<_Cat1, input_iterator_tag>::__value

>>> +         && __are_same<_Cat2, random_access_iterator_tag>::__value)

>>> +       __glibcxx_requires_can_increment_range(__first1, __last1, 

>>> __first2);

>>> +#endif

>>>       return std::__equal_aux(std::__niter_base(__first1),

>>>                              std::__niter_base(__last1),

>>>                              std::__niter_base(__first2));

>>

>> We don't give up any check.

>

> We do for my version of the patch, because with the new __niter_base

> overload the debug layer gets removed. Your patch kept the checking by

> not removing the debug layer, but loses the memcmp optimization.

>

> My suggestion above removes the debug layer so uses the optimization,

> but adds a separate range check, so we still get checking as well.

>

>> We only give up on using the __builtin_memcmp when std::equal is 

>> being used while Debug mode is active and std::equal is called 

>> directly with std::__cxx1998::vector.

>>

>> Moreover this check is wrong and will introduce regression when 

>> running testsuite in Debug mode (this is why I know). It will assert 

>> in the following case:

>> vector<int> v1 { 0, 0, 0 };

>> vector<int> v2 { 0, 1 };

>> equal(v1.begin(), v1.end(), v2.begin());

>

> We should assert for that test, it's undefined behaviour.

>

>

>>

>>>

>>>

>>>

>>>>>     Note that I don't know how to test that __builtin_memmove has 

>>>>> been indeed used. So I've been through some debug sessions to 

>>>>> check that.

>>>>

>>>> The attached patch (not fully tested) seems to be a much simpler way

>>>> to achieve the same thing. Instead of modifying all the helper

>>>> structs, just define a new function to re-wrap the result into the

>>>> desired iterator type.

>>>>

>>>>

>>>>> diff --git a/libstdc++-v3/include/debug/stl_iterator.h 

>>>>> b/libstdc++-v3/include/debug/stl_iterator.h

>>>>> index a6a2a76..eca7203 100644

>>>>> --- a/libstdc++-v3/include/debug/stl_iterator.h

>>>>> +++ b/libstdc++-v3/include/debug/stl_iterator.h

>>>>> @@ -120,4 +120,19 @@ namespace __gnu_debug

>>>>> #endif

>>>>> }

>>>>>

>>>>> +#if __cplusplus >= 201103L

>>>>> +namespace std

>>>>> +{

>>>>> +_GLIBCXX_BEGIN_NAMESPACE_VERSION

>>>>> +

>>>>> +template<typename _Iterator, typename _Container, typename 

>>>>> _Sequence>

>>>>> +    _Iterator

>>>>> +    __niter_base(const __gnu_debug::_Safe_iterator<

>>>>> +         __gnu_cxx::__normal_iterator<_Iterator, _Container>,

>>>>> +         _Sequence>&);

>>>>> +

>>>>> +_GLIBCXX_END_NAMESPACE_VERSION

>>>>> +}

>>>>> +#endif

>>>>

>>>> Why is this overload only defined for C++11 and later? I defined it

>>>> unconditionally in the attached patch.

>>>>

>>>> What do you think?

>>>

>>> Here's a complete patch that passes all tests in normal mode and

>>> causes no regressions in debug mode (we already have some debug test

>>> failing).

>>>

>>> I wondered whether we need another overload of __wrap_iter for

>>> handling move_iterator, but I think the first overload works OK.

>>>

>>>

>> I don't think we need it neither. Algos that handle move iterator are 

>> already doing it.

>

> OK great.

>

>

>
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index d429943..003ae8d 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -277,6 +277,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __niter_base(_Iterator __it)
     { return __it; }
 
+  // Convert an iterator of type _From to an iterator of type _To.
+  // e.g. from int* to __normal_iterator<int*, Seq>.
+  template<typename _Iterator>
+    inline _Iterator
+    __nwrap_iter(_Iterator, _Iterator, _Iterator __res)
+    { return __res; }
+
+  template<typename _From, typename _To>
+    inline _From
+    __nwrap_iter(_From __from, _To __to, _To __res)
+    { return __from + (__res - __to); }
+
   // All of these auxiliary structs serve two purposes.  (1) Replace
   // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
   // because the input and output ranges are permitted to overlap.)
@@ -419,9 +431,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _OI
     __copy_move_a2(_II __first, _II __last, _OI __result)
     {
-      return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
-					     std::__niter_base(__last),
-					     std::__niter_base(__result)));
+      return std::__nwrap_iter(__result,
+		std::__niter_base(__result),
+		std::__copy_move_a<_IsMove>(std::__niter_base(__first),
+					    std::__niter_base(__last),
+					    std::__niter_base(__result)));
     }
 
   /**
@@ -593,7 +607,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _BI2
     __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
     {
-      return _BI2(std::__copy_move_backward_a<_IsMove>
+      return std::__nwrap_iter(__result,
+		std::__niter_base(__result),
+		std::__copy_move_backward_a<_IsMove>
 		  (std::__niter_base(__first), std::__niter_base(__last),
 		   std::__niter_base(__result)));
     }
@@ -804,7 +820,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
       __glibcxx_requires_can_increment(__first, __n);
 
-      return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
+      return std::__nwrap_iter(__first,
+		std::__niter_base(__first),
+		std::__fill_n_a(std::__niter_base(__first), __n, __value));
     }
 
   template<bool _BoolType>
@@ -1062,7 +1080,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_function_requires(_EqualOpConcept<
 	    typename iterator_traits<_II1>::value_type,
 	    typename iterator_traits<_II2>::value_type>)
-      __glibcxx_requires_valid_range(__first1, __last1);
+	__glibcxx_requires_can_increment_range(__first1, __last1, __first2);
 
       return std::__equal_aux(std::__niter_base(__first1),
 			      std::__niter_base(__last1),
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index a6a2a76..f20b000 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -120,4 +120,17 @@ namespace __gnu_debug
 #endif
 }
 
+namespace std
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>&);
+
+_GLIBCXX_END_NAMESPACE_VERSION
+}
+
 #endif
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 802f4fd..ced5520 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -785,6 +785,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
     };
 
+ template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>& __it)
+    { return std::__niter_base(__it.base()); }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 #endif
Jonathan Wakely July 2, 2018, 11:57 a.m. | #9
On 01/07/18 21:20 +0200, François Dumont wrote:
>    Here is a new proposal between yours and mine.

>

>    It is still adding a function to wrap what __niter_base unwrap, I 

>called it __nwrap_iter for this reason. But it takes advantage of 


Since "niter" refers to __normal_iterator I think a name based on
"niter" would be better than nsomething_iter.

__niter_wrap
__niter_rewrap
__niter_lift (misuse of functional programming term?)
__niter_raise (misuse of linear algebra term?)
__make_niter
__remake_niter


>knowing that __niter_base will only unwrap random access iterator to 

>use an expression to that will do the right thing, no matter the 

>original iterator type.


OK, since __niter_base only transforms types based on 
__normal_iterator that seems safe to assume (in theory we could use
__normal_iterator with non-random access iterators, but we don't).

Could you please add a comment to the __nwrap_iter saying something
like:

  // Reverse the __niter_base transformation to get a
  // __normal_iterator back again (this assumes that __normal_iterator
  // is only used to wrap random access iterators, like pointers).


>    I eventually found no issue in the testsuite, despite the 

>std::equal change. I might have had a local invalid test.


Yes, I *did* test it already :-)




>diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h

>index d429943..003ae8d 100644

>--- a/libstdc++-v3/include/bits/stl_algobase.h

>+++ b/libstdc++-v3/include/bits/stl_algobase.h

>@@ -277,6 +277,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

>     __niter_base(_Iterator __it)

>     { return __it; }

> 

>+  // Convert an iterator of type _From to an iterator of type _To.

>+  // e.g. from int* to __normal_iterator<int*, Seq>.

>+  template<typename _Iterator>

>+    inline _Iterator

>+    __nwrap_iter(_Iterator, _Iterator, _Iterator __res)

>+    { return __res; }

>+

>+  template<typename _From, typename _To>

>+    inline _From

>+    __nwrap_iter(_From __from, _To __to, _To __res)

>+    { return __from + (__res - __to); }


Every time you call this function you pass it:

  __nwrap_iter(x, __niter_base(x), y)

So can the __niter_base(x) call happen inside __nwrap_iter?

i.e.

  template<typename _From, typename _To>
    inline _From
    __nwrap_iter(_From __from, _To __res)
    { return __from + (__res - __niter_base(__from)); }
François Dumont July 3, 2018, 5:47 a.m. | #10
Here is the updated patch.

     * include/bits/stl_algobase.h (__niter_wrap): New.
     (__copy_move_a2(_II, _II, _OI)): Use latter.
     (__copy_move_backward_a2(_BI1, _BI1, _BI2)): Likewise.
     (fill_n(_OI, _Size, const _Tp&)): Likewise.
     (equal(_II1, _II1, _II2)): Use __glibcxx_requires_can_increment.
     * include/debug/stl_iterator.h
     (std::__niter_base(const __gnu_cxx::_Safe_iterator<
     __gnu_cxx::__normal_iterator<>, _Sequence>&)): New declaration.
     * include/debug/vector (__niter_base(const __gnu_cxx::_Safe_iterator<
     __gnu_cxx::__normal_iterator<>, _Sequence>&)): New.

Ok to commit ?


On 02/07/2018 13:57, Jonathan Wakely wrote:
> On 01/07/18 21:20 +0200, François Dumont wrote:

>>     Here is a new proposal between yours and mine.

>>

>>     It is still adding a function to wrap what __niter_base unwrap, I 

>> called it __nwrap_iter for this reason. But it takes advantage of 

>

> Since "niter" refers to __normal_iterator I think a name based on

> "niter" would be better than nsomething_iter.

>

> __niter_wrap

> __niter_rewrap

> __niter_lift (misuse of functional programming term?)

> __niter_raise (misuse of linear algebra term?)

> __make_niter

> __remake_niter

>

>

>> knowing that __niter_base will only unwrap random access iterator to 

>> use an expression to that will do the right thing, no matter the 

>> original iterator type.

>

> OK, since __niter_base only transforms types based on 

> __normal_iterator that seems safe to assume (in theory we could use

> __normal_iterator with non-random access iterators, but we don't).

>

> Could you please add a comment to the __nwrap_iter saying something

> like:

>

>  // Reverse the __niter_base transformation to get a

>  // __normal_iterator back again (this assumes that __normal_iterator

>  // is only used to wrap random access iterators, like pointers).

>

>

>>     I eventually found no issue in the testsuite, despite the 

>> std::equal change. I might have had a local invalid test.

>

> Yes, I *did* test it already :-)

>

>

>

>

>> diff --git a/libstdc++-v3/include/bits/stl_algobase.h 

>> b/libstdc++-v3/include/bits/stl_algobase.h

>> index d429943..003ae8d 100644

>> --- a/libstdc++-v3/include/bits/stl_algobase.h

>> +++ b/libstdc++-v3/include/bits/stl_algobase.h

>> @@ -277,6 +277,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

>>     __niter_base(_Iterator __it)

>>     { return __it; }

>>

>> +  // Convert an iterator of type _From to an iterator of type _To.

>> +  // e.g. from int* to __normal_iterator<int*, Seq>.

>> +  template<typename _Iterator>

>> +    inline _Iterator

>> +    __nwrap_iter(_Iterator, _Iterator, _Iterator __res)

>> +    { return __res; }

>> +

>> +  template<typename _From, typename _To>

>> +    inline _From

>> +    __nwrap_iter(_From __from, _To __to, _To __res)

>> +    { return __from + (__res - __to); }

>

> Every time you call this function you pass it:

>

>  __nwrap_iter(x, __niter_base(x), y)

>

> So can the __niter_base(x) call happen inside __nwrap_iter?

>

> i.e.

>

>  template<typename _From, typename _To>

>    inline _From

>    __nwrap_iter(_From __from, _To __res)

>    { return __from + (__res - __niter_base(__from)); }

>

>

>
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index d429943..e5e7d15 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -277,6 +277,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __niter_base(_Iterator __it)
     { return __it; }
 
+  // Reverse the __niter_base transformation to get a
+  // __normal_iterator back again (this assumes that __normal_iterator
+  // is only used to wrap random access iterators, like pointers).
+  template<typename _Iterator>
+    inline _Iterator
+    __niter_wrap(_Iterator, _Iterator __res)
+    { return __res; }
+
+  template<typename _From, typename _To>
+    inline _From
+    __niter_wrap(_From __from, _To __res)
+    { return __from + (__res - __niter_base(__from)); }
+
   // All of these auxiliary structs serve two purposes.  (1) Replace
   // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
   // because the input and output ranges are permitted to overlap.)
@@ -419,9 +432,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _OI
     __copy_move_a2(_II __first, _II __last, _OI __result)
     {
-      return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
-					     std::__niter_base(__last),
-					     std::__niter_base(__result)));
+      return std::__niter_wrap(__result,
+		std::__copy_move_a<_IsMove>(std::__niter_base(__first),
+					    std::__niter_base(__last),
+					    std::__niter_base(__result)));
     }
 
   /**
@@ -593,7 +607,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _BI2
     __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
     {
-      return _BI2(std::__copy_move_backward_a<_IsMove>
+      return std::__niter_wrap(__result,
+		std::__copy_move_backward_a<_IsMove>
 		  (std::__niter_base(__first), std::__niter_base(__last),
 		   std::__niter_base(__result)));
     }
@@ -804,7 +819,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
       __glibcxx_requires_can_increment(__first, __n);
 
-      return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
+      return std::__niter_wrap(__first,
+		std::__fill_n_a(std::__niter_base(__first), __n, __value));
     }
 
   template<bool _BoolType>
@@ -1062,7 +1078,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_function_requires(_EqualOpConcept<
 	    typename iterator_traits<_II1>::value_type,
 	    typename iterator_traits<_II2>::value_type>)
-      __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
 
       return std::__equal_aux(std::__niter_base(__first1),
 			      std::__niter_base(__last1),
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index a6a2a76..f20b000 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -120,4 +120,17 @@ namespace __gnu_debug
 #endif
 }
 
+namespace std
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>&);
+
+_GLIBCXX_END_NAMESPACE_VERSION
+}
+
 #endif
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 802f4fd..ced5520 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -785,6 +785,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
     };
 
+ template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>& __it)
+    { return std::__niter_base(__it.base()); }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 #endif
Jonathan Wakely July 3, 2018, 8:55 a.m. | #11
On 03/07/18 07:47 +0200, François Dumont wrote:
>Here is the updated patch.

>

>    * include/bits/stl_algobase.h (__niter_wrap): New.

>    (__copy_move_a2(_II, _II, _OI)): Use latter.

>    (__copy_move_backward_a2(_BI1, _BI1, _BI2)): Likewise.

>    (fill_n(_OI, _Size, const _Tp&)): Likewise.

>    (equal(_II1, _II1, _II2)): Use __glibcxx_requires_can_increment.

>    * include/debug/stl_iterator.h

>    (std::__niter_base(const __gnu_cxx::_Safe_iterator<

>    __gnu_cxx::__normal_iterator<>, _Sequence>&)): New declaration.

>    * include/debug/vector (__niter_base(const __gnu_cxx::_Safe_iterator<

>    __gnu_cxx::__normal_iterator<>, _Sequence>&)): New.

>

>Ok to commit ?

>

>

>On 02/07/2018 13:57, Jonathan Wakely wrote:

>>On 01/07/18 21:20 +0200, François Dumont wrote:

>>>    Here is a new proposal between yours and mine.

>>>

>>>    It is still adding a function to wrap what __niter_base 

>>>unwrap, I called it __nwrap_iter for this reason. But it takes 

>>>advantage of

>>

>>Since "niter" refers to __normal_iterator I think a name based on

>>"niter" would be better than nsomething_iter.

>>

>>__niter_wrap

>>__niter_rewrap

>>__niter_lift (misuse of functional programming term?)

>>__niter_raise (misuse of linear algebra term?)

>>__make_niter

>>__remake_niter

>>

>>

>>>knowing that __niter_base will only unwrap random access iterator 

>>>to use an expression to that will do the right thing, no matter 

>>>the original iterator type.

>>

>>OK, since __niter_base only transforms types based on 

>>__normal_iterator that seems safe to assume (in theory we could use

>>__normal_iterator with non-random access iterators, but we don't).

>>

>>Could you please add a comment to the __nwrap_iter saying something

>>like:

>>

>> // Reverse the __niter_base transformation to get a

>> // __normal_iterator back again (this assumes that __normal_iterator

>> // is only used to wrap random access iterators, like pointers).

>>

>>

>>>    I eventually found no issue in the testsuite, despite the 

>>>std::equal change. I might have had a local invalid test.

>>

>>Yes, I *did* test it already :-)

>>

>>

>>

>>

>>>diff --git a/libstdc++-v3/include/bits/stl_algobase.h 

>>>b/libstdc++-v3/include/bits/stl_algobase.h

>>>index d429943..003ae8d 100644

>>>--- a/libstdc++-v3/include/bits/stl_algobase.h

>>>+++ b/libstdc++-v3/include/bits/stl_algobase.h

>>>@@ -277,6 +277,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

>>>    __niter_base(_Iterator __it)

>>>    { return __it; }

>>>

>>>+  // Convert an iterator of type _From to an iterator of type _To.

>>>+  // e.g. from int* to __normal_iterator<int*, Seq>.

>>>+  template<typename _Iterator>

>>>+    inline _Iterator

>>>+    __nwrap_iter(_Iterator, _Iterator, _Iterator __res)

>>>+    { return __res; }

>>>+

>>>+  template<typename _From, typename _To>

>>>+    inline _From

>>>+    __nwrap_iter(_From __from, _To __to, _To __res)

>>>+    { return __from + (__res - __to); }

>>

>>Every time you call this function you pass it:

>>

>> __nwrap_iter(x, __niter_base(x), y)

>>

>>So can the __niter_base(x) call happen inside __nwrap_iter?

>>

>>i.e.

>>

>> template<typename _From, typename _To>

>>   inline _From

>>   __nwrap_iter(_From __from, _To __res)

>>   { return __from + (__res - __niter_base(__from)); }

>>

>>

>>

>


>diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h

>index d429943..e5e7d15 100644

>--- a/libstdc++-v3/include/bits/stl_algobase.h

>+++ b/libstdc++-v3/include/bits/stl_algobase.h

>@@ -277,6 +277,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

>     __niter_base(_Iterator __it)

>     { return __it; }

> 

>+  // Reverse the __niter_base transformation to get a

>+  // __normal_iterator back again (this assumes that __normal_iterator

>+  // is only used to wrap random access iterators, like pointers).


Please move the comment onto the other overload, since that's the one
that actually does the wrapping.

Maybe we should re-order the overloads, so the __niter_wrap<_From, _To>
overload comes first, then on the second one add a comment:

    // No need to wrap, iterator already has the right type

>+  template<typename _Iterator>

>+    inline _Iterator

>+    __niter_wrap(_Iterator, _Iterator __res)

>+    { return __res; }

>+

>+  template<typename _From, typename _To>

>+    inline _From

>+    __niter_wrap(_From __from, _To __res)

>+    { return __from + (__res - __niter_base(__from)); }


Please qualify this call as std::__niter_base

OK with those changes, thanks.

Patch

diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index d429943..100676b 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -286,9 +286,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<bool, bool, typename>
     struct __copy_move
     {
-      template<typename _II, typename _OI>
+      template<typename _II, typename _OI, typename _OIBase>
 	static _OI
-	__copy_m(_II __first, _II __last, _OI __result)
+	__copy_m(_II __first, _II __last, _OI __result, _OIBase)
 	{
 	  for (; __first != __last; ++__result, (void)++__first)
 	    *__result = *__first;
@@ -300,9 +300,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<typename _Category>
     struct __copy_move<true, false, _Category>
     {
-      template<typename _II, typename _OI>
+      template<typename _II, typename _OI, typename _OIBase>
 	static _OI
-	__copy_m(_II __first, _II __last, _OI __result)
+	__copy_m(_II __first, _II __last, _OI __result, _OIBase)
 	{
 	  for (; __first != __last; ++__result, (void)++__first)
 	    *__result = std::move(*__first);
@@ -314,9 +314,10 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<>
     struct __copy_move<false, false, random_access_iterator_tag>
     {
+    private:
       template<typename _II, typename _OI>
 	static _OI
-	__copy_m(_II __first, _II __last, _OI __result)
+	__copy_impl(_II __first, _II __last, _OI __result)
 	{
 	  typedef typename iterator_traits<_II>::difference_type _Distance;
 	  for (_Distance __n = __last - __first; __n > 0; --__n)
@@ -327,15 +328,30 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    }
 	  return __result;
 	}
+
+    public:
+      template<typename _II, typename _OI>
+	static _OI
+	__copy_m(_II __first, _II __last, _OI __result, _OI)
+	{ return __copy_impl(__first, __last, __result); }
+
+      template<typename _II, typename _OI, typename _OIBase>
+	static _OI
+	__copy_m(_II __first, _II __last, _OI __result, _OIBase __res_base)
+	{
+	  _OIBase __end = __copy_impl(__first, __last, __res_base);
+	  return __result + (__end - __res_base);
+	}
     };
 
 #if __cplusplus >= 201103L
   template<>
     struct __copy_move<true, false, random_access_iterator_tag>
     {
+    private:
       template<typename _II, typename _OI>
 	static _OI
-	__copy_m(_II __first, _II __last, _OI __result)
+	__copy_impl(_II __first, _II __last, _OI __result)
 	{
 	  typedef typename iterator_traits<_II>::difference_type _Distance;
 	  for (_Distance __n = __last - __first; __n > 0; --__n)
@@ -346,15 +362,30 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    }
 	  return __result;
 	}
+
+    public:
+      template<typename _II, typename _OI>
+	static _OI
+	__copy_m(_II __first, _II __last, _OI __result, _OI)
+	{ return __copy_impl(__first, __last, __result); }
+
+      template<typename _II, typename _OI, typename _OIBase>
+	static _OI
+	__copy_m(_II __first, _II __last, _OI __result, _OIBase __res_base)
+	{
+	  _OIBase __end = __copy_impl(__first, __last, __res_base);
+	  return __result + (__end - __res_base);
+	}
     };
 #endif
 
   template<bool _IsMove>
     struct __copy_move<_IsMove, true, random_access_iterator_tag>
     {
-      template<typename _Tp>
-	static _Tp*
-	__copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
+      template<typename _Tp, typename _OI>
+	static _OI
+        __copy_m(const _Tp* __first, const _Tp* __last, _OI __result,
+		 _Tp* __res_base)
 	{
 #if __cplusplus >= 201103L
 	  using __assignable = conditional<_IsMove,
@@ -365,25 +396,25 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif
 	  const ptrdiff_t _Num = __last - __first;
 	  if (_Num)
-	    __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
+	    __builtin_memmove(__res_base, __first, sizeof(_Tp) * _Num);
 	  return __result + _Num;
 	}
     };
 
-  template<bool _IsMove, typename _II, typename _OI>
+  template<bool _IsMove, typename _II, typename _OI, typename _OIBase>
     inline _OI
-    __copy_move_a(_II __first, _II __last, _OI __result)
+    __copy_move_a(_II __first, _II __last, _OI __result, _OIBase __res_base)
     {
       typedef typename iterator_traits<_II>::value_type _ValueTypeI;
-      typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
+      typedef typename iterator_traits<_OIBase>::value_type _ValueTypeO;
       typedef typename iterator_traits<_II>::iterator_category _Category;
       const bool __simple = (__is_trivial(_ValueTypeI)
 			     && __is_pointer<_II>::__value
-			     && __is_pointer<_OI>::__value
+			     && __is_pointer<_OIBase>::__value
 			     && __are_same<_ValueTypeI, _ValueTypeO>::__value);
 
-      return std::__copy_move<_IsMove, __simple,
-			      _Category>::__copy_m(__first, __last, __result);
+      return std::__copy_move<_IsMove, __simple, _Category>
+	::__copy_m(__first, __last, __result, __res_base);
     }
 
   // Helpers for streambuf iterators (either istream or ostream).
@@ -419,9 +450,10 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _OI
     __copy_move_a2(_II __first, _II __last, _OI __result)
     {
-      return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
+      return std::__copy_move_a<_IsMove>(std::__niter_base(__first),
 					 std::__niter_base(__last),
-					     std::__niter_base(__result)));
+					 __result,
+					 std::__niter_base(__result));
     }
 
   /**
@@ -495,9 +527,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<bool, bool, typename>
     struct __copy_move_backward
     {
-      template<typename _BI1, typename _BI2>
+      template<typename _BI1, typename _BI2, typename _BI2Base>
 	static _BI2
-	__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
+	__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result, _BI2Base)
 	{
 	  while (__first != __last)
 	    *--__result = *--__last;
@@ -509,9 +541,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<typename _Category>
     struct __copy_move_backward<true, false, _Category>
     {
-      template<typename _BI1, typename _BI2>
+      template<typename _BI1, typename _BI2, typename _BI2Base>
 	static _BI2
-	__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
+	__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result, _BI2Base)
 	{
 	  while (__first != __last)
 	    *--__result = std::move(*--__last);
@@ -523,39 +555,72 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<>
     struct __copy_move_backward<false, false, random_access_iterator_tag>
     {
+    private:
       template<typename _BI1, typename _BI2>
 	static _BI2
-	__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
+	__copy_b_impl(_BI1 __first, _BI1 __last, _BI2 __result)
 	{
 	  typename iterator_traits<_BI1>::difference_type __n;
 	  for (__n = __last - __first; __n > 0; --__n)
 	    *--__result = *--__last;
 	  return __result;
 	}
+
+    public:
+      template<typename _BI1, typename _BI2>
+	static _BI2
+	__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result, _BI2)
+	{ return __copy_b_impl(__first, __last, __result); }
+
+      template<typename _BI1, typename _BI2, typename _BI2Base>
+	static _BI2
+	__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result,
+		      _BI2Base __res_base)
+	{
+	  _BI2Base __rend = __copy_b_impl(__first, __last, __res_base);
+	  return __result + (__rend - __res_base);
+	}
     };
 
 #if __cplusplus >= 201103L
   template<>
     struct __copy_move_backward<true, false, random_access_iterator_tag>
     {
+    private:
       template<typename _BI1, typename _BI2>
 	static _BI2
-	__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
+	__copy_b_impl(_BI1 __first, _BI1 __last, _BI2 __result)
 	{
 	  typename iterator_traits<_BI1>::difference_type __n;
 	  for (__n = __last - __first; __n > 0; --__n)
 	    *--__result = std::move(*--__last);
 	  return __result;
 	}
+
+    public:
+      template<typename _BI1, typename _BI2>
+	static _BI2
+	__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result, _BI2)
+	{ return __copy_b_impl(__first, __last, __result); }
+
+      template<typename _BI1, typename _BI2, typename _BI2Base>
+	static _BI2
+	__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result,
+		      _BI2Base __res_base)
+	{
+	  _BI2Base __rend = __copy_b_impl(__first, __last, __res_base);
+	  return __result + (__rend - __res_base);
+	}
     };
 #endif
 
   template<bool _IsMove>
     struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
     {
-      template<typename _Tp>
-	static _Tp*
-	__copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
+      template<typename _Tp, typename _BI2>
+	static _BI2
+	__copy_move_b(const _Tp* __first, const _Tp* __last, _BI2 __result,
+		      _Tp* __res_base)
 	{
 #if __cplusplus >= 201103L
 	  using __assignable = conditional<_IsMove,
@@ -566,36 +631,35 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif
 	  const ptrdiff_t _Num = __last - __first;
 	  if (_Num)
-	    __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
+	    __builtin_memmove(__res_base - _Num, __first, sizeof(_Tp) * _Num);
 	  return __result - _Num;
 	}
     };
 
-  template<bool _IsMove, typename _BI1, typename _BI2>
+  template<bool _IsMove, typename _BI1, typename _BI2, typename _BI2Base>
     inline _BI2
-    __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
+    __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result,
+			   _BI2Base __res_base)
     {
       typedef typename iterator_traits<_BI1>::value_type _ValueType1;
-      typedef typename iterator_traits<_BI2>::value_type _ValueType2;
+      typedef typename iterator_traits<_BI2Base>::value_type _ValueType2;
       typedef typename iterator_traits<_BI1>::iterator_category _Category;
       const bool __simple = (__is_trivial(_ValueType1)
 			     && __is_pointer<_BI1>::__value
-			     && __is_pointer<_BI2>::__value
+			     && __is_pointer<_BI2Base>::__value
 			     && __are_same<_ValueType1, _ValueType2>::__value);
 
-      return std::__copy_move_backward<_IsMove, __simple,
-				       _Category>::__copy_move_b(__first,
-								 __last,
-								 __result);
+      return std::__copy_move_backward<_IsMove, __simple, _Category>
+	::__copy_move_b(__first, __last, __result, __res_base);
     }
 
   template<bool _IsMove, typename _BI1, typename _BI2>
     inline _BI2
     __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
     {
-      return _BI2(std::__copy_move_backward_a<_IsMove>
+      return std::__copy_move_backward_a<_IsMove>
 	      (std::__niter_base(__first), std::__niter_base(__last),
-		   std::__niter_base(__result)));
+	       __result, std::__niter_base(__result));
     }
 
   /**
@@ -749,10 +813,10 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		    __value);
     }
 
-  template<typename _OutputIterator, typename _Size, typename _Tp>
+  template<typename _OutputIterator, typename _OI, typename _Size, typename _Tp>
     inline typename
     __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
-    __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
+    __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value, _OI)
     {
       for (__decltype(__n + 0) __niter = __n;
 	   __niter > 0; --__niter, (void) ++__first)
@@ -760,10 +824,10 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return __first;
     }
 
-  template<typename _OutputIterator, typename _Size, typename _Tp>
+  template<typename _OutputIterator, typename _OI, typename _Size, typename _Tp>
     inline typename
     __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
-    __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
+    __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value, _OI)
     {
       const _Tp __tmp = __value;
       for (__decltype(__n + 0) __niter = __n;
@@ -772,12 +836,12 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return __first;
     }
 
-  template<typename _Size, typename _Tp>
+  template<typename _OutputIterator, typename _Size, typename _Tp>
     inline typename
-    __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type
-    __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)
+    __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _OutputIterator>::__type
+    __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __c, _Tp* __res)
     {
-      std::__fill_a(__first, __first + __n, __c);
+      std::__fill_a(__res, __res + __n, __c);
       return __first + __n;
     }
 
@@ -804,7 +868,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
       __glibcxx_requires_can_increment(__first, __n);
 
-      return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
+      return std::__fill_n_a(__first, __n, __value, std::__niter_base(__first));
     }
 
   template<bool _BoolType>
@@ -1066,7 +1130,11 @@  _GLIBCXX_BEGIN_NAMESPACE_ALGO
 
       return std::__equal_aux(std::__niter_base(__first1),
 			      std::__niter_base(__last1),
+#if _GLIBCXX_DEBUG
+			      __first2);
+#else
 			      std::__niter_base(__first2));
+#endif
     }
 
   /**
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index a6a2a76..eca7203 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -120,4 +120,19 @@  namespace __gnu_debug
 #endif
 }
 
+#if __cplusplus >= 201103L
+namespace std
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>&);
+
+_GLIBCXX_END_NAMESPACE_VERSION
+}
+#endif
+
 #endif
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 8d60da3..40a991f 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -783,6 +783,13 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
     };
 
+ template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>& __it)
+    { return std::__niter_base(__it.base()); }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 #endif