libstdc++: Teach std::distance and std::advance about C++20 iterators [PR102181]

When the C++98 std::distance and std::advance functions (and C++11
std::next and std::prev) are used with C++20 iterators there can be
unexpected results, ranging from compilation failure to decreased
performance to undefined behaviour.

An iterator which satisfies std::input_iterator but does not meet the
Cpp17InputIterator requirements might have std::output_iterator_tag for
its std::iterator_traits<I>::iterator_category, which means it currently
cannot be used with std::advance at all. However, the implementation of
std::advance for a Cpp17InputIterator doesn't do anything that isn't
valid for iterator types satsifying C++20 std::input_iterator.

Similarly, a type satisfying C++20 std::bidirectional_iterator might be
usable with std::prev, if it weren't for the fact that its C++17
iterator_category is std::input_iterator_tag.

Finally, a type satisfying C++20 std::random_access_iterator might use a
slower implementation for std::distance or std::advance if its C++17
iterator_category is not std::random_access_iterator_tag.

This commit adds a __promotable_iterator concept to detect C++20
iterators which explicitly define an iterator_concept member, and which
either have no iterator_category, or their iterator_category is weaker
than their iterator_concept. This is used by std::distance and
std::advance to detect iterators which should dispatch based on their
iterator_concept instead of their iterator_category. This means that
those functions just work and do the right thing for C++20 iterators
which would otherwise fail to compile or have suboptimal performance.

This is related to LWG 3197, which considers making it undefined to use
std::prev with types which do not meet the Cpp17BidirectionalIterator
requirements.  I think making it work, as in this commit, is a better
solution than banning it (or rejecting it at compile-time as libc++
does).

	PR libstdc++/102181

libstdc++-v3/ChangeLog:

	* include/bits/stl_iterator_base_funcs.h (distance, advance):
	Check C++20 iterator concepts and handle appropriately.
	(__detail::__iter_category_converts_to_concept): New concept.
	(__detail::__promotable_iterator): New concept.
	* testsuite/24_iterators/operations/cxx20_iterators.cc: New
	test.

Reviewed-by: Patrick Palka <ppalka@redhat.com>
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>

0 files changed, 0 insertions, 0 deletions