Re: [PATCH 2/3] libstdc++: Implement C++20 constrained algorithms

[François Dumont]

Thanks for those additional information.

I still think that the same way we rely on STL algos for 
push_heap/pop_heap/... we should do it for copy/move/... from 
stl_algobase.h for RAI.


In fact range algos that are already trying to call C functions should 
just try to call the STL counterparts which will then forward to C 
functions.


On 2/13/20 8:00 PM, Jonathan Wakely wrote:

On 13/02/20 19:07 +0100, François Dumont wrote:

On 2/4/20 3:07 AM, Patrick Palka wrote:

This patch implements the C++20 ranges overloads for the algorithms in
[algorithms].  Most of the algorithms were reimplemented, with each 
of their

implementations very closely following the existing implementation in
bits/stl_algo.h and bits/stl_algobase.h.  The reason for 
reimplementing most of
the algorithms instead of forwarding to their STL-style overload is 
because
forwarding cannot be conformantly and efficiently performed for 
algorithms that

operate on non-random-access iterators.

Why ? Do you have a clear counter-example ?

Maybe at the time you wrote this code those algos were not constexpr 
qualified, but they are now.


It has nothing to do with constexpr.

If you call a ranges algo with an iterator and a sentinel that is a
different type to the iterator, you can't call the old STL algo unless
you can efficiently get an end iterator that refers to the same
position as the sentinel. For random access iterators that is:

auto last2 = first + (last - first);

But for non-random access iterators finding the distance between first
and last is not possible in O(1), and incrementing first by that
distance is also not possible in O(1).


  But algorithms that operate on random
access iterators can safely and efficiently be forwarded to the 
STL-style
implementation, and this patch does so for push_heap, pop_heap, 
make_heap,
sort_heap, sort, stable_sort, nth_element, inplace_merge and 
stable_partition.
IMHO we should try as much as possible to forward to algos in 
stl_algobase.h.


That would not be conforming in many cases.

The old code assumes iterators can be copied. It assumes they have an
iterator_category. It assumes they have operator->(). Most
importantly, it assumes the begin and end iterators have the same
type.

The old algorithms do tag dispatching, which adds function call
overhead at run-time and overload resolution overhead at compile-time.

The new constrained algos can be implemented much more cleanly using
if-constexpr and the new iterator concepts.

There are very good reasons to reimplement the new ranges algos.

Those are highly customized and will be even more in the future when 
some patches I have on my side will be integrated (I hope).


If you do so you won't have to care much about _GLIBCXX_DEBUG iterators.



What's missing from this patch is debug-iterator and container 
specializations
that are present for some of the STL-style algorithms that need to 
be ported
over to the ranges algos.  I marked them missing at TODO comments.  
There are

also some other minor outstanding TODOs.

The code that could use the most thorough review is 
ranges::__copy_or_move,

ranges::__copy_or_move_backward, ranges::__equal and
ranges::__lexicographical_compare.  In the tests, I tried to test 
the interface
of each new overload, as well as the correctness of the new 
implementation.

Re: [PATCH 2/3] libstdc++: Implement C++20 constrained algorithms

[Jonathan Wakely]

On 13/02/20 19:07 +0100, François Dumont wrote:

On 2/4/20 3:07 AM, Patrick Palka wrote:

This patch implements the C++20 ranges overloads for the algorithms in
[algorithms].  Most of the algorithms were reimplemented, with each of their
implementations very closely following the existing implementation in
bits/stl_algo.h and bits/stl_algobase.h.  The reason for reimplementing most of
the algorithms instead of forwarding to their STL-style overload is because
forwarding cannot be conformantly and efficiently performed for algorithms that
operate on non-random-access iterators.

Why ? Do you have a clear counter-example ?

Maybe at the time you wrote this code those algos were not constexpr 
qualified, but they are now.


It has nothing to do with constexpr.

If you call a ranges algo with an iterator and a sentinel that is a
different type to the iterator, you can't call the old STL algo unless
you can efficiently get an end iterator that refers to the same
position as the sentinel. For random access iterators that is:

auto last2 = first + (last - first);

But for non-random access iterators finding the distance between first
and last is not possible in O(1), and incrementing first by that
distance is also not possible in O(1).


  But algorithms that operate on random
access iterators can safely and efficiently be forwarded to the STL-style
implementation, and this patch does so for push_heap, pop_heap, make_heap,
sort_heap, sort, stable_sort, nth_element, inplace_merge and stable_partition.
IMHO we should try as much as possible to forward to algos in 
stl_algobase.h.


That would not be conforming in many cases.

The old code assumes iterators can be copied. It assumes they have an
iterator_category. It assumes they have operator->(). Most
importantly, it assumes the begin and end iterators have the same
type.

The old algorithms do tag dispatching, which adds function call
overhead at run-time and overload resolution overhead at compile-time.

The new constrained algos can be implemented much more cleanly using
if-constexpr and the new iterator concepts.

There are very good reasons to reimplement the new ranges algos.

Those are highly customized and will be even more in the future when 
some patches I have on my side will be integrated (I hope).


If you do so you won't have to care much about _GLIBCXX_DEBUG iterators.



What's missing from this patch is debug-iterator and container specializations
that are present for some of the STL-style algorithms that need to be ported
over to the ranges algos.  I marked them missing at TODO comments.  There are
also some other minor outstanding TODOs.

The code that could use the most thorough review is ranges::__copy_or_move,
ranges::__copy_or_move_backward, ranges::__equal and
ranges::__lexicographical_compare.  In the tests, I tried to test the interface
of each new overload, as well as the correctness of the new implementation.

Re: [PATCH 2/3] libstdc++: Implement C++20 constrained algorithms

[François Dumont]

On 2/4/20 3:07 AM, Patrick Palka wrote:

This patch implements the C++20 ranges overloads for the algorithms in
[algorithms].  Most of the algorithms were reimplemented, with each of their
implementations very closely following the existing implementation in
bits/stl_algo.h and bits/stl_algobase.h.  The reason for reimplementing most of
the algorithms instead of forwarding to their STL-style overload is because
forwarding cannot be conformantly and efficiently performed for algorithms that
operate on non-random-access iterators.

Why ? Do you have a clear counter-example ?

Maybe at the time you wrote this code those algos were not constexpr 
qualified, but they are now.



   But algorithms that operate on random
access iterators can safely and efficiently be forwarded to the STL-style
implementation, and this patch does so for push_heap, pop_heap, make_heap,
sort_heap, sort, stable_sort, nth_element, inplace_merge and stable_partition.
IMHO we should try as much as possible to forward to algos in 
stl_algobase.h.


Those are highly customized and will be even more in the future when 
some patches I have on my side will be integrated (I hope).


If you do so you won't have to care much about _GLIBCXX_DEBUG iterators.



What's missing from this patch is debug-iterator and container specializations
that are present for some of the STL-style algorithms that need to be ported
over to the ranges algos.  I marked them missing at TODO comments.  There are
also some other minor outstanding TODOs.

The code that could use the most thorough review is ranges::__copy_or_move,
ranges::__copy_or_move_backward, ranges::__equal and
ranges::__lexicographical_compare.  In the tests, I tried to test the interface
of each new overload, as well as the correctness of the new implementation.

Re: [PATCH 2/3] libstdc++: Implement C++20 constrained algorithms

[Jonathan Wakely]

On 03/02/20 21:07 -0500, Patrick Palka wrote:

+  template
+struct binary_transform_result
+{
+  [[no_unique_address]] _Iter1 in1;
+  [[no_unique_address]] _Iter2 in2;
+  [[no_unique_address]] _Out  out;
+
+  template
+   requires convertible_to &&
+ && convertible_to


WHAT IS HAPPENING HERE?!

Notice we have requires A && && B

I'm fixing it, but that needs following up to see if there's a
compiler bug!

Re: [PATCH 2/3] libstdc++: Implement C++20 constrained algorithms

[Patrick Palka]

On Thu, 6 Feb 2020, Jonathan Wakely wrote:

> On 03/02/20 21:07 -0500, Patrick Palka wrote:
> > +#ifndef _RANGES_ALGO_H
> > +#define _RANGES_ALGO_H 1
> > +
> > +#if __cplusplus > 201703L
> > +
> > +#include 
> > +#include 
> > +#include 
> > +// #include 
> 
> This line could be removed, or leave it as a reminder to me to
> refactor  so that the small utility pieces are in a small
> utility header (like  that can be included
> instead of the whole of .

I guess I'll leave it in then.

> 
> > +#include 
> > +#include 
> > +#include  // __is_byte
> > +#include  // concept uniform_random_bit_generator
> 
> I wonder if we want to move that concept to 
> instead, which already exists to allow  to avoid including
> the whole of . If we do that, it would make sense to rename
>  to  or something like
> that.

That makes sense -- I can try to do that in a followup patch.

> 
> > +
> > +#if __cpp_lib_concepts
> > +namespace std _GLIBCXX_VISIBILITY(default)
> > +{
> > +_GLIBCXX_BEGIN_NAMESPACE_VERSION
> > +namespace ranges
> > +{
> > +  namespace __detail
> > +  {
> > +template
> > +constexpr inline bool __is_normal_iterator = false;
> 
> All these templates in the __detail namespace should be indented by
> two spaces after the template-head i.e.
> 
> template
>   constexpr inline bool __is_normal_iterator = false;
> 
> (That indentation scheme has been in the libstdc++ style guide for
> longer than I've been contributing to the project, but it doesn't seem
> very popular with new contributors, and it wastes a level of
> indentation for templates, which means most of the library. Maybe we
> should revisit that convention.)

Fixed

> 
> 
> > +  template
> > +using unary_transform_result = copy_result<_Iter, _Out>;
> > +
> > +  template _Sent,
> > +  weakly_incrementable _Out,
> > +  copy_constructible _Fp, typename _Proj = identity>
> > +requires writable<_Out, indirect_result_t<_Fp&, projected<_Iter,
> > _Proj>>>
> 
> I have a pending patch to implement P1878R1, which renames writable
> (and a few other concepts). I'll wait until your patch is in, and
> change these places using it.

Sounds good.

> 
> > +partial_sort_copy(_Iter1 __first, _Sent1 __last,
> > + _Iter2 __result_first, _Sent2 __result_last,
> > + _Comp __comp = {},
> > + _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
> > +{
> > +  if (__result_first == __result_last)
> > +   {
> > + // TODO: Eliminating the variable __lasti triggers an ICE.
> > + auto __lasti = ranges::next(std::move(__first),
> > + std::move(__last));
> > + return {std::move(__lasti), std::move(__result_first)};
> 
> Please try to reduce that and report it to bugzilla at some point,
> thanks.

Will do!  Interestingly, it was an ICE in the middle-end.  I wasn't able
to reproduce it anymore, but I'll try more carefully tomorrow.

> 
> > +++ b/libstdc++-v3/testsuite/25_algorithms/all_of/constrained.cc
> > @@ -0,0 +1,90 @@
> > +// Copyright (C) 2019 Free Software Foundation, Inc.
> 
> This should be 2020. That's the only change necessary though, please
> adjust that and commit to master. Great work, thank you!

Fixed.  Thank you for the review!  Patch committed, hopefully without
any fallout.

Re: [PATCH 2/3] libstdc++: Implement C++20 constrained algorithms

[Jonathan Wakely]

On 03/02/20 21:07 -0500, Patrick Palka wrote:

+#ifndef _RANGES_ALGO_H
+#define _RANGES_ALGO_H 1
+
+#if __cplusplus > 201703L
+
+#include 
+#include 
+#include 
+// #include 


This line could be removed, or leave it as a reminder to me to
refactor  so that the small utility pieces are in a small
utility header (like  that can be included
instead of the whole of .


+#include 
+#include 
+#include  // __is_byte
+#include  // concept uniform_random_bit_generator


I wonder if we want to move that concept to 
instead, which already exists to allow  to avoid including
the whole of . If we do that, it would make sense to rename
 to  or something like
that.


+
+#if __cpp_lib_concepts
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+namespace ranges
+{
+  namespace __detail
+  {
+template
+constexpr inline bool __is_normal_iterator = false;


All these templates in the __detail namespace should be indented by
two spaces after the template-head i.e.

template
  constexpr inline bool __is_normal_iterator = false;

(That indentation scheme has been in the libstdc++ style guide for
longer than I've been contributing to the project, but it doesn't seem
very popular with new contributors, and it wastes a level of
indentation for templates, which means most of the library. Maybe we
should revisit that convention.)



+  template
+using unary_transform_result = copy_result<_Iter, _Out>;
+
+  template _Sent,
+  weakly_incrementable _Out,
+  copy_constructible _Fp, typename _Proj = identity>
+requires writable<_Out, indirect_result_t<_Fp&, projected<_Iter, _Proj>>>


I have a pending patch to implement P1878R1, which renames writable
(and a few other concepts). I'll wait until your patch is in, and
change these places using it.


+partial_sort_copy(_Iter1 __first, _Sent1 __last,
+ _Iter2 __result_first, _Sent2 __result_last,
+ _Comp __comp = {},
+ _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
+{
+  if (__result_first == __result_last)
+   {
+ // TODO: Eliminating the variable __lasti triggers an ICE.
+ auto __lasti = ranges::next(std::move(__first),
+ std::move(__last));
+ return {std::move(__lasti), std::move(__result_first)};


Please try to reduce that and report it to bugzilla at some point,
thanks.


+++ b/libstdc++-v3/testsuite/25_algorithms/all_of/constrained.cc
@@ -0,0 +1,90 @@
+// Copyright (C) 2019 Free Software Foundation, Inc.


This should be 2020. That's the only change necessary though, please
adjust that and commit to master. Great work, thank you!

Re: [PATCH 2/3] libstdc++: Implement C++20 constrained algorithms

[Jonathan Wakely]

On 05/02/20 19:39 +0100, François Dumont wrote:

Hi

    Is it me or the patch isn't an attachment ? It is far more 
convenient to provide something easy to extract and apply locally.


On 2/4/20 3:07 AM, Patrick Palka wrote:

This patch implements the C++20 ranges overloads for the algorithms in
[algorithms].  Most of the algorithms were reimplemented, with each of their
implementations very closely following the existing implementation in
bits/stl_algo.h and bits/stl_algobase.h.  The reason for reimplementing most of
the algorithms instead of forwarding to their STL-style overload is because
forwarding cannot be conformantly and efficiently performed for algorithms that
operate on non-random-access iterators.  But algorithms that operate on random
access iterators can safely and efficiently be forwarded to the STL-style
implementation, and this patch does so for push_heap, pop_heap, make_heap,
sort_heap, sort, stable_sort, nth_element, inplace_merge and stable_partition.

What's missing from this patch is debug-iterator


Always the 5th wheel of the car like we say in French :-)

I'll be looking at this point once I manage to apply the patch.


 and container specializations
that are present for some of the STL-style algorithms that need to be ported
over to the ranges algos.  I marked them missing at TODO comments.  There are
also some other minor outstanding TODOs.

The code that could use the most thorough review is ranges::__copy_or_move,
ranges::__copy_or_move_backward, ranges::__equal and
ranges::__lexicographical_compare.  In the tests, I tried to test the interface
of each new overload, as well as the correctness of the new implementation.

diff --git a/libstdc++-v3/include/bits/ranges_algo.h 
b/libstdc++-v3/include/bits/ranges_algo.h
new file mode 100644
index 000..2e177ce7f7a
--- /dev/null
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -0,0 +1,3640 @@
+// Core algorithmic facilities -*- C++ -*-
+
+// Copyright (C) 2019-2020 Free Software Foundation, Inc.


Copyright for new files is wrong, should be only 2020. I know it is 
painful to maintain that when you work on patch on several years.


I assume Patrick kept the 2019 date because his patch started from a
file I sent him with a few of the algos, and that was dated 2019.

I can't remember what the actual rule is for new files that contain
old code. The copyright on some of the new file *is* from 2019, even
if it wasn't added to the GCC repo yet.

New files containing new code should definitely only have the new date
(usually when I point out wrong dates in patch review it's because
somebody's just copied the comment header from an old testcase and so
the old dates are wrong).

I only wrote that code in December 2019 though, so it doesn't make a
lot of difference either way, 2020 is fine.

Re: [PATCH 2/3] libstdc++: Implement C++20 constrained algorithms

[Jonathan Wakely]

On 05/02/20 14:24 -0500, Patrick Palka wrote:

Also IIRC, the way __miter_base() is currently defined assumes that the
underlying iterator is copyable which is not necessarily true anymore
for non-forward iterators.  So I would have to also fix __miter_base()
which might be risky to do at this stage.


Agreed. The current patch only affects C++20, which makes it much less
risky.

I was thinking about how range algos interact with debug mode, and I
think we might want to take the opportunity to do things a bit
differently.

Just like if-constexpr allows algos to use different implementations
without tag-dispatching, we might be able to simplify how we deal with
debug iterators.

For example, instead of spliting every algo into foo and __foo parts
and making foo do the debug checks, then unwrap the debug iterators
and call __foo, we could just unwrap them and recursively call the
same function again:

template
  constexpr It
  foo(It __first, __last)
  {
if constexpr (__is_debug_iter<_It>)
  {
// do debug checks ...
// and the work on unwrapped iterators:
return std::__niter_wrap(foo(std::__niter_base(__first),
 std::__niter_base(__last)));
  }

  // ...
  }

It's OK to use the functions that assume the iterators are copyable
here, because we know that our debug iterators are copyable.

We should also consider when we even need debug checks for the algos
taking a range. In many cases, calling foo(vec) doesn't need to check
if the iterators are valid, because we know that ranges::begin(vec)
and ranges::end(vec) will call vec.begin() and vec.end() which are
valid. That won't always be true, because somebody could create an
invalid range by trying hard enough, but I think in many cases we can
assume that a range doesn't contain invalid iterators. However, since
they just forward to the overload taking a pair of iterators, we will
get the debug checks there anyway. But I don't think the overloads
taking a range should do any debug checks explicitly.

We can add debug assertions to subrange, and to range adaptors like
take_view and drop_view to prevent the creation of invalid ranges in
the first place, so that we can assume they're valid after that.

I'll talk to the Microsoft library team about this topic when I see
them next week. I assume they've already been thinking about it and
will probably have some useful input.

Re: [PATCH 2/3] libstdc++: Implement C++20 constrained algorithms

[Patrick Palka]

[resending with attachment now compressed]

On Wed, 5 Feb 2020, François Dumont wrote:

> Hi
> 
>     Is it me or the patch isn't an attachment ? It is far more convenient to
> provide something easy to extract and apply locally.

Good point, I've attached the patch as an attachment and I'll make sure
to provide big patches as an attachment in the future.  I should also
have noted that the patches are also available in my user branch
libstdcxx-constrained-algo-adaptors which you can fetch with

git fetch origin 
refs/users/ppalka/heads/libstdcxx-constrained-algos-adaptors

> 
> On 2/4/20 3:07 AM, Patrick Palka wrote:
> > This patch implements the C++20 ranges overloads for the algorithms in
> > [algorithms].  Most of the algorithms were reimplemented, with each of their
> > implementations very closely following the existing implementation in
> > bits/stl_algo.h and bits/stl_algobase.h.  The reason for reimplementing most
> > of
> > the algorithms instead of forwarding to their STL-style overload is because
> > forwarding cannot be conformantly and efficiently performed for algorithms
> > that
> > operate on non-random-access iterators.  But algorithms that operate on
> > random
> > access iterators can safely and efficiently be forwarded to the STL-style
> > implementation, and this patch does so for push_heap, pop_heap, make_heap,
> > sort_heap, sort, stable_sort, nth_element, inplace_merge and
> > stable_partition.
> > 
> > What's missing from this patch is debug-iterator
> 
> Always the 5th wheel of the car like we say in French :-)
> 
> I'll be looking at this point once I manage to apply the patch.

That would be much appreciated! :)

> 
> >   and container specializations
> > that are present for some of the STL-style algorithms that need to be ported
> > over to the ranges algos.  I marked them missing at TODO comments.  There
> > are
> > also some other minor outstanding TODOs.
> > 
> > The code that could use the most thorough review is ranges::__copy_or_move,
> > ranges::__copy_or_move_backward, ranges::__equal and
> > ranges::__lexicographical_compare.  In the tests, I tried to test the
> > interface
> > of each new overload, as well as the correctness of the new implementation.
> > 
> > diff --git a/libstdc++-v3/include/bits/ranges_algo.h
> > b/libstdc++-v3/include/bits/ranges_algo.h
> > new file mode 100644
> > index 000..2e177ce7f7a
> > --- /dev/null
> > +++ b/libstdc++-v3/include/bits/ranges_algo.h
> > @@ -0,0 +1,3640 @@
> > +// Core algorithmic facilities -*- C++ -*-
> > +
> > +// Copyright (C) 2019-2020 Free Software Foundation, Inc.
> 
> Copyright for new files is wrong, should be only 2020. I know it is painful to
> maintain that when you work on patch on several years.

Thanks, fixed!

> 
> > 
> > +//
> > +// This file is part of the GNU ISO C++ Library.  This library is free
> > +// software; you can redistribute it and/or modify it under the
> > +// terms of the GNU General Public License as published by the
> > +// Free Software Foundation; either version 3, or (at your option)
> > +// any later version.
> > +
> > +// This library is distributed in the hope that it will be useful,
> > +// but WITHOUT ANY WARRANTY; without even the implied warranty of
> > +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> > +// GNU General Public License for more details.
> > +
> > +// Under Section 7 of GPL version 3, you are granted additional
> > +// permissions described in the GCC Runtime Library Exception, version
> > +// 3.1, as published by the Free Software Foundation.
> > +
> > +// You should have received a copy of the GNU General Public License and
> > +// a copy of the GCC Runtime Library Exception along with this program;
> > +// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
> > +// .
> > +
> > +/** @file bits/ranges_algo.h
> > + *  This is an internal header file, included by other library headers.
> > + *  Do not attempt to use it directly. @headername{algorithm}
> > + */
> > +
> > +#ifndef _RANGES_ALGO_H
> > +#define _RANGES_ALGO_H 1
> > +
> > +#if __cplusplus > 201703L
> > +
> > +#include 
> > +#include 
> > +#include 
> > +// #include 
> > +#include 
> > +#include 
> > +#include  // __is_byte
> > +#include  // concept uniform_random_bit_generator
> > +
> > +#if __cpp_lib_concepts
> > +namespace std _GLIBCXX_VISIBILITY(default)
> > +{
> > +_GLIBCXX_BEGIN_NAMESPACE_VERSION
> > +namespace ranges
> > +{
> > +  namespace __detail
> > +  {
> > +template
> > +constexpr inline bool __is_normal_iterator = false;
> > +
> > +template
> > +constexpr inline bool
> > +  __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator,
> > _Container>>
> > +  = true;
> > +
> > +template
> > +constexpr inline bool __is_reverse_iterator = false;
> > +
> > +template
> > +constexpr inline bool
> > +  __is_reverse_iterator> = true;
> > +
> > +template
> > +constexpr inline 

Re: [PATCH 2/3] libstdc++: Implement C++20 constrained algorithms

[François Dumont]

Hi

    Is it me or the patch isn't an attachment ? It is far more 
convenient to provide something easy to extract and apply locally.


On 2/4/20 3:07 AM, Patrick Palka wrote:

This patch implements the C++20 ranges overloads for the algorithms in
[algorithms].  Most of the algorithms were reimplemented, with each of their
implementations very closely following the existing implementation in
bits/stl_algo.h and bits/stl_algobase.h.  The reason for reimplementing most of
the algorithms instead of forwarding to their STL-style overload is because
forwarding cannot be conformantly and efficiently performed for algorithms that
operate on non-random-access iterators.  But algorithms that operate on random
access iterators can safely and efficiently be forwarded to the STL-style
implementation, and this patch does so for push_heap, pop_heap, make_heap,
sort_heap, sort, stable_sort, nth_element, inplace_merge and stable_partition.

What's missing from this patch is debug-iterator


Always the 5th wheel of the car like we say in French :-)

I'll be looking at this point once I manage to apply the patch.


  and container specializations
that are present for some of the STL-style algorithms that need to be ported
over to the ranges algos.  I marked them missing at TODO comments.  There are
also some other minor outstanding TODOs.

The code that could use the most thorough review is ranges::__copy_or_move,
ranges::__copy_or_move_backward, ranges::__equal and
ranges::__lexicographical_compare.  In the tests, I tried to test the interface
of each new overload, as well as the correctness of the new implementation.

diff --git a/libstdc++-v3/include/bits/ranges_algo.h 
b/libstdc++-v3/include/bits/ranges_algo.h
new file mode 100644
index 000..2e177ce7f7a
--- /dev/null
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -0,0 +1,3640 @@
+// Core algorithmic facilities -*- C++ -*-
+
+// Copyright (C) 2019-2020 Free Software Foundation, Inc.


Copyright for new files is wrong, should be only 2020. I know it is 
painful to maintain that when you work on patch on several years.




+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// .
+
+/** @file bits/ranges_algo.h
+ *  This is an internal header file, included by other library headers.
+ *  Do not attempt to use it directly. @headername{algorithm}
+ */
+
+#ifndef _RANGES_ALGO_H
+#define _RANGES_ALGO_H 1
+
+#if __cplusplus > 201703L
+
+#include 
+#include 
+#include 
+// #include 
+#include 
+#include 
+#include  // __is_byte
+#include  // concept uniform_random_bit_generator
+
+#if __cpp_lib_concepts
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+namespace ranges
+{
+  namespace __detail
+  {
+template
+constexpr inline bool __is_normal_iterator = false;
+
+template
+constexpr inline bool
+  __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator, _Container>>
+  = true;
+
+template
+constexpr inline bool __is_reverse_iterator = false;
+
+template
+constexpr inline bool
+  __is_reverse_iterator> = true;
+
+template
+constexpr inline bool __is_move_iterator = false;
+
+template
+constexpr inline bool
+  __is_move_iterator> = true;


Did you consider the __is_move_iterator in stl_iterator.h ?

At least this version will also detect a move_iterator in different 
situation. I haven't check yet what you are doing with that but it might 
be an easy way to get better debug iterators integration for instance.


François