[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<typename _It>
   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.