Bind to std::equal plumbing in ranges::equal

Message ID 97fdeb63-e758-a3a7-f9b4-0b0890a956f8@gmail.com
State New
Headers show
Series
  • Bind to std::equal plumbing in ranges::equal
Related show

Commit Message

François Dumont March 6, 2020, 6:06 a.m.
I started to work on ranges::equal to find out if what I am trying to do 
is totally silly.

With this patch ranges::equal is in pare with std::equal specializations 
that is to say that it correctly deals with Debug mode or std::deque 
iterators.

Once below patch is in:

https://gcc.gnu.org/ml/libstdc++/2019-12/msg00032.html

We will even be able to call std::__equal_aux1 directly using 
__niter_base to get rid of the Debug safe iterator layer. And even in 
this case get rid of the branch __use_memcmp and leave it to __equal_aux1.

I mainly fear the usage of std::iterator_traits in __equal_aux1 to be a 
problem. Is it in this context of sized_sentinel ?

In addition to testsuite I checked running gdb that it does the right thing.

Ok to commit ?

     libstdc++ Leverage on std::equal plumbing in ranges::equal.

     Benefit from the std::equal plumbing to correctly deal with
     _GLIBCXX_DEBUG mode and std::deque iterators.

             * include/bits/ranges_algobase.h (__equal_fn::operator()):
             Review conditions to call std::__equal_aux.
             * testsuite/25_algorithms/equal/constrained.cc (test04): New.

François

Comments

Jonathan Wakely March 6, 2020, 10:09 a.m. | #1
On 06/03/20 07:06 +0100, François Dumont wrote:
>I started to work on ranges::equal to find out if what I am trying to 

>do is totally silly.

>

>With this patch ranges::equal is in pare with std::equal 

>specializations that is to say that it correctly deals with Debug mode 

>or std::deque iterators.

>

>Once below patch is in:

>

>https://gcc.gnu.org/ml/libstdc++/2019-12/msg00032.html

>

>We will even be able to call std::__equal_aux1 directly using 

>__niter_base to get rid of the Debug safe iterator layer. And even in 

>this case get rid of the branch __use_memcmp and leave it to 

>__equal_aux1.

>

>I mainly fear the usage of std::iterator_traits in __equal_aux1 to be 

>a problem. Is it in this context of sized_sentinel ?


I don't understand the question. No sentinel of type _Sent1 or _Sent2
gets passed to __equal_aux1 with your patch, you only pass iterators.

But I think the patch is wrong:

>+		  return !std::__memcmp(__first1, __first2, __d1);

>+		else

>+		  return std::__equal_aux(__first1, __first1 + __d1, __first2);


This last line will only compile if _Iter1 is random access, but all
we know at this point is that _Sent1 is a sized sentinel for _Iter1.
That doesn't mean it's necessarily random access.
Jonathan Wakely March 6, 2020, 10:12 a.m. | #2
On 06/03/20 10:09 +0000, Jonathan Wakely wrote:
>On 06/03/20 07:06 +0100, François Dumont wrote:

>>I started to work on ranges::equal to find out if what I am trying 

>>to do is totally silly.

>>

>>With this patch ranges::equal is in pare with std::equal 

>>specializations that is to say that it correctly deals with Debug 

>>mode or std::deque iterators.

>>

>>Once below patch is in:

>>

>>https://gcc.gnu.org/ml/libstdc++/2019-12/msg00032.html

>>

>>We will even be able to call std::__equal_aux1 directly using 

>>__niter_base to get rid of the Debug safe iterator layer. And even 

>>in this case get rid of the branch __use_memcmp and leave it to 

>>__equal_aux1.

>>

>>I mainly fear the usage of std::iterator_traits in __equal_aux1 to 

>>be a problem. Is it in this context of sized_sentinel ?

>

>I don't understand the question. No sentinel of type _Sent1 or _Sent2

>gets passed to __equal_aux1 with your patch, you only pass iterators.

>

>But I think the patch is wrong:

>

>>+		  return !std::__memcmp(__first1, __first2, __d1);

>>+		else

>>+		  return std::__equal_aux(__first1, __first1 + __d1, __first2);

>

>This last line will only compile if _Iter1 is random access, but all

>we know at this point is that _Sent1 is a sized sentinel for _Iter1.

>That doesn't mean it's necessarily random access.


Please try the example at https://wg21.link/counted.iterator#2 which
uses counted_iterator<list<string>::iterator> and default_sentinel.
The sized_sentinel_for concept is satisfied, but you can't do first1+d1.
François Dumont March 9, 2020, 6:29 a.m. | #3
On 3/6/20 11:12 AM, Jonathan Wakely wrote:
> On 06/03/20 10:09 +0000, Jonathan Wakely wrote:

>> On 06/03/20 07:06 +0100, François Dumont wrote:

>>> I started to work on ranges::equal to find out if what I am trying 

>>> to do is totally silly.

>>>

>>> With this patch ranges::equal is in pare with std::equal 

>>> specializations that is to say that it correctly deals with Debug 

>>> mode or std::deque iterators.

>>>

>>> Once below patch is in:

>>>

>>> https://gcc.gnu.org/ml/libstdc++/2019-12/msg00032.html

>>>

>>> We will even be able to call std::__equal_aux1 directly using 

>>> __niter_base to get rid of the Debug safe iterator layer. And even 

>>> in this case get rid of the branch __use_memcmp and leave it to 

>>> __equal_aux1.

>>>

>>> I mainly fear the usage of std::iterator_traits in __equal_aux1 to 

>>> be a problem. Is it in this context of sized_sentinel ?

>>

>> I don't understand the question. No sentinel of type _Sent1 or _Sent2

>> gets passed to __equal_aux1 with your patch, you only pass iterators.


I just thought that std::iterator_traits was becoming somehow obsolete 
is the more recent Standard and that it was the reason for not using 
existing std algos.


>>

>> But I think the patch is wrong:

>>

>>> +          return !std::__memcmp(__first1, __first2, __d1);

>>> +        else

>>> +          return std::__equal_aux(__first1, __first1 + __d1, 

>>> __first2);

>>

>> This last line will only compile if _Iter1 is random access, but all

>> we know at this point is that _Sent1 is a sized sentinel for _Iter1.

>> That doesn't mean it's necessarily random access.

>

> Please try the example at https://wg21.link/counted.iterator#2 which

> uses counted_iterator<list<string>::iterator> and default_sentinel.

> The sized_sentinel_for concept is satisfied, but you can't do first1+d1.

>

>

Thanks for this example, now I know what has to be supported. I'll see 
if I can find a solution before you do.

François

Patch

diff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h
index 80c9a774301..d4f89cb9fb2 100644
--- a/libstdc++-v3/include/bits/ranges_algobase.h
+++ b/libstdc++-v3/include/bits/ranges_algobase.h
@@ -82,8 +82,6 @@  namespace ranges
 		 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
 		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
       {
-	// TODO: implement more specializations to at least have parity with
-	// std::equal.
 	if constexpr (__detail::__is_normal_iterator<_Iter1>
 		      || __detail::__is_normal_iterator<_Iter2>)
 	  return (*this)(std::__niter_base(std::move(__first1)),
@@ -100,19 +98,24 @@  namespace ranges
 	    if (__d1 != __d2)
 	      return false;
 
+	    if (!__d1)
+	      return true;
+
+	    constexpr bool __is_simple_equal
+	      = (is_same_v<_Pred, ranges::equal_to>
+		 && is_same_v<_Proj1, identity>
+		 && is_same_v<_Proj2, identity>);
+	    if constexpr (__is_simple_equal)
+	      {
 		using _ValueType1 = iter_value_t<_Iter1>;
 		using _ValueType2 = iter_value_t<_Iter2>;
 		constexpr bool __use_memcmp
 		  = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
-		 && __memcmpable<_Iter1, _Iter2>::__value
-		 && is_same_v<_Pred, ranges::equal_to>
-		 && is_same_v<_Proj1, identity>
-		 && is_same_v<_Proj2, identity>);
+		     && __memcmpable<_Iter1, _Iter2>::__value);
 		if constexpr (__use_memcmp)
-	      {
-		if (const size_t __len = (__last1 - __first1))
-		  return !std::__memcmp(__first1, __first2, __len);
-		return true;
+		  return !std::__memcmp(__first1, __first2, __d1);
+		else
+		  return std::__equal_aux(__first1, __first1 + __d1, __first2);
 	      }
 	    else
 	      {
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/equal/constrained.cc
index 231bd8cfeaa..aa27fd195a2 100644
--- a/libstdc++-v3/testsuite/25_algorithms/equal/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/constrained.cc
@@ -19,6 +19,9 @@ 
 // { dg-do run { target c++2a } }
 
 #include <algorithm>
+#include <vector>
+#include <deque>
+
 #include <testsuite_hooks.h>
 #include <testsuite_iterators.h>
 
@@ -87,10 +90,21 @@  test03()
   VERIFY( !ranges::equal(x, z) );
 }
 
+void
+test04()
+{
+  std::deque<int> x = { {2}, {2}, {6}, {8}, {10}, {11} };
+  std::deque<int> y = { {2}, {2}, {6}, {8}, {10}, {11} };
+  std::deque<int> z = { {2}, {2}, {6}, {8}, {10}, {12} };
+  VERIFY( ranges::equal(x, y) );
+  VERIFY( !ranges::equal(x, z) );
+}
+
 int
 main()
 {
   test01();
   test02();
   test03();
+  test04();
 }