On Wed, 10 Jun 2020, Jonathan Wakely wrote:
> On 10/06/20 15:32 -0400, Patrick Palka via Libstdc++ wrote:
> > ranges::copy and a number of other ranges algorithms have unwrapping
> > optimizations for iterators of type __normal_iterator, move_iterator and
> > reverse_iterator. But in the checks that guard these optimizations we
> > currently only test that the iterator of the iterator/sentinel pair has
> > the appropriate type before proceeding with the corresponding
> > optimization, and we fail to also test the sentinel type.
> >
> > This breaks the testcase in this PR because this testcase constructs
> > via range adaptors a range whose begin() is a __normal_iterator and
> > whose end() is a custom sentinel type, and then does ranges::copy on it.
> > From there we bogusly perform the __normal_iterator unwrapping
> > optimization on this iterator/sentinel pair, which immediately leads to
> > a constraint failure since the custom sentinel type does not model
> > sentinel_for<int*>.
> >
> > This patch fixes this issue by augmenting each of the problematic checks
> > to also test that the iterator and sentinel types are the same before
> > applying the corresponding unwrapping optimization.
> >
> > Tested on x86_64-pc-linux-gnu, does this look OK to commit to master to
> > and to the 10.2 branch?
> >
> > libstdc++-v3/ChangeLog:
> >
> > PR libstdc++/95578
> > * include/bits/ranges_algo.h (__lexicographical_compare_fn):
> > Also check that the iterator and sentinel have the same type before
> > applying the unwrapping optimization for __normal_iterator.
> > Split the check into two, one for the first iterator/sentinel
> > pair and another for second iterator/sentinel pair. Stop using
> > __niter_base and stop doing std::move on a __normal_iterator.
> > * include/bits/ranges_algobase.c (__equal_fn): Likewise.
> > (__copy_or_move): Likewise. Perform similar adjustments for
> > the reverse_iterator and move_iterator optimizations. Inline
> > the checks into the if-constexprs, and use using-declarations to
> > make them less visually noisy. Don't use __niter_wrap.
> > (__copy_or_move_backward): Likewise.
> > * testsuite/25_algorithms/copy/95578.cc: New test.
> > * testsuite/25_algorithms/copy_backward/95578.cc: New test.
> > * testsuite/25_algorithms/equal/95578.cc: New test.
> > * testsuite/25_algorithms/lexicographical_compare/95578.cc: New test.
> > * testsuite/25_algorithms/move/95578.cc: New test.
> > * testsuite/25_algorithms/move_backward/95578.cc: New test.
> > ---
> > libstdc++-v3/include/bits/ranges_algo.h | 14 +--
> > libstdc++-v3/include/bits/ranges_algobase.h | 88 ++++++++++---------
> > .../testsuite/25_algorithms/copy/95578.cc | 74 ++++++++++++++++
> > .../25_algorithms/copy_backward/95578.cc | 62 +++++++++++++
> > .../testsuite/25_algorithms/equal/95578.cc | 74 ++++++++++++++++
> > .../lexicographical_compare/95578.cc | 74 ++++++++++++++++
> > .../testsuite/25_algorithms/move/95578.cc | 62 +++++++++++++
> > .../25_algorithms/move_backward/95578.cc | 62 +++++++++++++
> > 8 files changed, 465 insertions(+), 45 deletions(-)
> > create mode 100644 libstdc++-v3/testsuite/25_algorithms/copy/95578.cc
> > create mode 100644
> > libstdc++-v3/testsuite/25_algorithms/copy_backward/95578.cc
> > create mode 100644 libstdc++-v3/testsuite/25_algorithms/equal/95578.cc
> > create mode 100644
> > libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/95578.cc
> > create mode 100644 libstdc++-v3/testsuite/25_algorithms/move/95578.cc
> > create mode 100644
> > libstdc++-v3/testsuite/25_algorithms/move_backward/95578.cc
> >
> > diff --git a/libstdc++-v3/include/bits/ranges_algo.h
> > b/libstdc++-v3/include/bits/ranges_algo.h
> > index c038a505afa..94ca7b6488d 100644
> > --- a/libstdc++-v3/include/bits/ranges_algo.h
> > +++ b/libstdc++-v3/include/bits/ranges_algo.h
> > @@ -3452,11 +3452,15 @@ namespace ranges
> > _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
> > {
> > if constexpr (__detail::__is_normal_iterator<_Iter1>
> > - || __detail::__is_normal_iterator<_Iter2>)
> > - return (*this)(std::__niter_base(std::move(__first1)),
> > - std::__niter_base(std::move(__last1)),
> > - std::__niter_base(std::move(__first2)),
> > - std::__niter_base(std::move(__last2)),
> > + && same_as<_Iter1, _Sent1>)
> > + return (*this)(__first1.base(), __last1.base(),
> > + std::move(__first2), std::move(__last2),
> > + std::move(__comp),
> > + std::move(__proj1), std::move(__proj2));
> > + else if constexpr (__detail::__is_normal_iterator<_Iter2>
> > + && same_as<_Iter2, _Sent2>)
> > + return (*this)(std::move(__first1), std::move(__last1),
> > + __first2.base(), __last2.base(),
> > std::move(__comp),
> > std::move(__proj1), std::move(__proj2));
> > else
>
> So if all four iterators are normal_iterator then we first unwrap the
> first pair, and recurse, and then unwrap the second pair, and recurse,
> right?
>
> I don't love that additional step needed to unwrap the scond time, but
> I can live with it.
Hmm, yes.. I guess we could circumvent this second step by adding an
additional constexpr-if branch. Better might be to introduce new
helpers that are like __niter_base and __niter_wrap but instead take
iterator/sentinel pairs. I wonder if there are other options?
>
> OK for master and gcc-10, thanks.
Thanks.
