[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 00000000000..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
> +// <http://www.gnu.org/licenses/>.
> +
> +/** @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 <compare>
> +#include <cmath>
> +#include <iterator>
> +// #include <bits/range_concepts.h>
> +#include <ranges>
> +#include <bits/invoke.h>
> +#include <bits/cpp_type_traits.h> // __is_byte
> +#include <bits/random.h> // concept uniform_random_bit_generator
> +
> +#if __cpp_lib_concepts
> +namespace std _GLIBCXX_VISIBILITY(default)
> +{
> +_GLIBCXX_BEGIN_NAMESPACE_VERSION
> +namespace ranges
> +{
> +  namespace __detail
> +  {
> +    template<typename _Tp>
> +    constexpr inline bool __is_normal_iterator = false;
> +
> +    template<typename _Iterator, typename _Container>
> +    constexpr inline bool
> +      __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator, _Container>>
> +      = true;
> +
> +    template<typename _Tp>
> +    constexpr inline bool __is_reverse_iterator = false;
> +
> +    template<typename _Iterator>
> +    constexpr inline bool
> +      __is_reverse_iterator<reverse_iterator<_Iterator>> = true;
> +
> +    template<typename _Tp>
> +    constexpr inline bool __is_move_iterator = false;
> +
> +    template<typename _Iterator>
> +    constexpr inline bool
> +      __is_move_iterator<move_iterator<_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