[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 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.
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
> > +// <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.
The __is_move_iterator in stl_iterator.h is "deep" in that it looks
through other iterator adaptors and returns true if the iterator is in
some level wrapped by a move_iterator. It turned out that for the
implementation of __copy_or_move, we need just a "shallow" version of
__is_move_iterator which returns true iff the outermost iterator adaptor
is a move_iterator.
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.
>
> François
>
>
0002-libstdc-Implement-C-20-constrained-algorithms.patch.gz
Description: application/gzip
