Index: libcxx/docs/Status/Cxx2bIssues.csv =================================================================== --- libcxx/docs/Status/Cxx2bIssues.csv +++ libcxx/docs/Status/Cxx2bIssues.csv @@ -106,7 +106,7 @@ `3152 `__,"``common_type`` and ``common_reference`` have flaws in common","October 2021","","" `3293 `__,"``move_iterator operator+()`` has incorrect constraints","October 2021","","","|ranges|" `3361 `__,"``safe_range`` case","October 2021","","","|ranges|" -`3392 `__,"``ranges::distance()`` cannot be used on a move-only iterator with a sized sentinel","October 2021","","","|ranges|" +`3392 `__,"``ranges::distance()`` cannot be used on a move-only iterator with a sized sentinel","October 2021","|Complete|","14.0","|ranges|" `3407 `__,"Some problems with the wording changes of P1739R4","October 2021","","","|ranges|" `3422 `__,"Issues of ``seed_seq``'s constructors","October 2021","","" `3470 `__,"``convertible-to-non-slicing`` seems to reject valid case","October 2021","","","|ranges|" Index: libcxx/docs/Status/RangesPaper.csv =================================================================== --- libcxx/docs/Status/RangesPaper.csv +++ libcxx/docs/Status/RangesPaper.csv @@ -71,7 +71,7 @@ `[range.iter.ops] `_,"| `ranges::advance `_ | `ranges::distance `_ | `ranges::next `_ -| `ranges::prev `_",[iterator.concepts],Christopher Di Bella,In progress +| `ranges::prev `_",[iterator.concepts],Christopher Di Bella,Complete [predef.iterators],Updates to predefined iterators.,"| [iterator.concepts] | [iterator.cust.swap] | [iterator.cust.move]",Unassigned,Not started Index: libcxx/include/__iterator/distance.h =================================================================== --- libcxx/include/__iterator/distance.h +++ libcxx/include/__iterator/distance.h @@ -11,7 +11,13 @@ #define _LIBCPP___ITERATOR_DISTANCE_H #include <__config> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> #include <__iterator/iterator_traits.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/size.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header @@ -46,6 +52,56 @@ return _VSTD::__distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category()); } +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_RANGES) + +// [range.iter.op.distance] + +namespace ranges { +namespace __distance { + +struct __fn { + template _Sp> + requires (!sized_sentinel_for<_Sp, _Ip>) + _LIBCPP_HIDE_FROM_ABI + constexpr iter_difference_t<_Ip> operator()(_Ip __first, _Sp __last) const { + iter_difference_t<_Ip> __n = 0; + while (__first != __last) { + ++__first; + ++__n; + } + return __n; + } + + template> _Sp> + _LIBCPP_HIDE_FROM_ABI + constexpr iter_difference_t<_Ip> operator()(_Ip&& __first, _Sp __last) const { + if constexpr (sized_sentinel_for<_Sp, remove_reference_t<_Ip>>) { + return __last - __first; + } else { + return __last - decay_t<_Ip>(__first); + } + } + + template + _LIBCPP_HIDE_FROM_ABI + constexpr range_difference_t<_Rp> operator()(_Rp&& __r) const { + if constexpr (sized_range<_Rp>) { + return static_cast>(ranges::size(__r)); + } else { + return operator()(ranges::begin(__r), ranges::end(__r)); + } + } +}; + +} // namespace __distance + +inline namespace __cpo { + inline constexpr auto distance = __distance::__fn{}; +} // namespace __cpo +} // namespace ranges + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_RANGES) + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_DISTANCE_H Index: libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp @@ -0,0 +1,152 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts + +// template S> +// requires (!sized_sentinel_for) +// constexpr iter_difference_t ranges::distance(I first, S last); +// +// template> S> +// constexpr iter_difference_t ranges::distance(const I& first, S last); + +#include +#include + +#include "test_iterators.h" + +template +constexpr void test_unsized() { + static_assert(std::sentinel_for && !std::sized_sentinel_for); + int a[3] = {1,2,3}; + { + It first = It(a); + auto last = Sent(It(a)); + assert(std::ranges::distance(first, last) == 0); + assert(std::ranges::distance(It(a), last) == 0); + assert(std::ranges::distance(first, Sent(It(a))) == 0); + assert(std::ranges::distance(It(a), Sent(It(a))) == 0); + } + { + It first = It(a); + auto last = Sent(It(a + 3)); + assert(std::ranges::distance(first, last) == 3); + assert(std::ranges::distance(It(a), last) == 3); + assert(std::ranges::distance(first, Sent(It(a + 3))) == 3); + assert(std::ranges::distance(It(a), Sent(It(a + 3))) == 3); + } +} + +template +constexpr void test_sized() { + static_assert(std::sized_sentinel_for); + int a[] = {1,2,3}; + { + It first = It(a + 3); + auto last = Sent(It(a)); + assert(std::ranges::distance(first, last) == -3); + assert(std::ranges::distance(It(a + 3), last) == -3); + assert(std::ranges::distance(first, Sent(It(a))) == -3); + assert(std::ranges::distance(It(a + 3), Sent(It(a))) == -3); + } + { + It first = It(a); + auto last = Sent(It(a)); + assert(std::ranges::distance(first, last) == 0); + assert(std::ranges::distance(It(a), last) == 0); + assert(std::ranges::distance(first, Sent(It(a))) == 0); + assert(std::ranges::distance(It(a), Sent(It(a))) == 0); + } + { + It first = It(a); + auto last = Sent(It(a + 3)); + assert(std::ranges::distance(first, last) == 3); + assert(std::ranges::distance(It(a), last) == 3); + assert(std::ranges::distance(first, Sent(It(a + 3))) == 3); + assert(std::ranges::distance(It(a), Sent(It(a + 3))) == 3); + } +} + +constexpr bool test() { + { + int a[] = {1, 2, 3}; + assert(std::ranges::distance(a, a + 3) == 3); + assert(std::ranges::distance(a, a) == 0); + assert(std::ranges::distance(a + 3, a) == -3); + } + + test_unsized, sentinel_wrapper>>(); + test_unsized, sentinel_wrapper>>(); + test_unsized, sentinel_wrapper>>(); + test_unsized, sentinel_wrapper>>(); + test_unsized, sentinel_wrapper>>(); + test_unsized, sentinel_wrapper>>(); + test_unsized>(); + test_unsized>(); + test_unsized, forward_iterator>(); + test_unsized, bidirectional_iterator>(); + + test_sized, sized_sentinel>>(); + test_sized, sized_sentinel>>(); + test_sized, sized_sentinel>>(); + test_sized, sized_sentinel>>(); + test_sized, sized_sentinel>>(); + test_sized, sized_sentinel>>(); + test_sized, sized_sentinel>>(); + test_sized>(); + test_sized>(); + test_sized(); + test_sized(); + test_sized, random_access_iterator>(); + test_sized, contiguous_iterator>(); + + { + using It = cpp20_input_iterator; // non-copyable, thus not a sentinel for itself + static_assert(!std::is_copy_constructible_v); + static_assert(!std::sentinel_for); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + } + { + using It = cpp20_input_iterator; // non-copyable + using Sent = sentinel_wrapper; // not a sized sentinel + static_assert(std::sentinel_for && !std::sized_sentinel_for); + int a[] = {1,2,3}; + Sent last = Sent(It(a + 3)); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + assert(std::ranges::distance(It(a), last) == 3); + assert(std::ranges::distance(It(a), Sent(It(a + 3))) == 3); + } + { + using It = cpp17_input_iterator; // not a sentinel for itself + static_assert(!std::sentinel_for); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + } + + // Calling it on a non-iterator or non-sentinel isn't allowed. + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} Index: libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/lwg3664.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/lwg3664.pass.cpp @@ -0,0 +1,68 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts + +// template S> +// requires (!sized_sentinel_for) +// constexpr iter_difference_t ranges::distance(I first, S last); +// +// template> S> +// constexpr iter_difference_t ranges::distance(const I& first, S last); + +#include +#include + +#include "test_iterators.h" + +template +struct EvilSentinel { + It p_; + friend constexpr bool operator==(EvilSentinel s, It p) { return s.p_ == p; } + friend constexpr auto operator-(EvilSentinel s, It p) { return s.p_ - p; } + friend constexpr auto operator-(It p, EvilSentinel s) { return p - s.p_; } +}; +static_assert( std::sized_sentinel_for, int*>); +static_assert(!std::sized_sentinel_for, const int*>); +static_assert( std::sized_sentinel_for, int*>); +static_assert( std::sized_sentinel_for, const int*>); + +constexpr bool test() { + { + int a[] = {1, 2, 3}; + assert(std::ranges::distance(a, a + 3) == 3); + assert(std::ranges::distance(a, a) == 0); + assert(std::ranges::distance(a + 3, a) == -3); + } + { + int a[] = {1, 2, 3}; + assert(std::ranges::distance(a, EvilSentinel{a+3}) == 3); + assert(std::ranges::distance(a, EvilSentinel{a}) == 0); + assert(std::ranges::distance(a+3, EvilSentinel{a}) == -3); + assert(std::ranges::distance(std::move(a), EvilSentinel{a+3}) == 3); + } + { + const int a[] = {1, 2, 3}; + assert(std::ranges::distance(a, EvilSentinel{a+3}) == 3); + assert(std::ranges::distance(a, EvilSentinel{a}) == 0); + assert(std::ranges::distance(a+3, EvilSentinel{a}) == -3); + assert(std::ranges::distance(std::move(a), EvilSentinel{a+3}) == 3); + static_assert(!std::is_invocable_v>); + static_assert(!std::is_invocable_v>); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} Index: libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/range.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/range.pass.cpp @@ -0,0 +1,106 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template +// constexpr range_difference_t ranges::distance(R&& r); + +#include +#include +#include + +#include "test_iterators.h" + +template +constexpr void test_ordinary() { + struct R { + mutable int a[3] = {1, 2, 3}; + constexpr It begin() const { return It(a); } + constexpr Sent end() const { return Sent(It(a + 3)); } + }; + R r; + assert(std::ranges::distance(r) == 3); + assert(std::ranges::distance(static_cast(r)) == 3); + assert(std::ranges::distance(static_cast(r)) == 3); + assert(std::ranges::distance(static_cast(r)) == 3); +} + +constexpr bool test() { + { + using R = int[3]; + int a[] = {1, 2, 3}; + assert(std::ranges::distance(static_cast(a)) == 3); + assert(std::ranges::distance(static_cast(a)) == 3); + assert(std::ranges::distance(static_cast(a)) == 3); + assert(std::ranges::distance(static_cast(a)) == 3); + } + { + // Unsized range, non-copyable iterator type, rvalue-ref-qualified begin() + using It = cpp20_input_iterator; + using Sent = sentinel_wrapper>; + using R = std::ranges::subrange; + + int a[] = {1, 2, 3}; + auto r = R(It(a), Sent(It(a + 3))); + assert(std::ranges::distance(r) == 3); + assert(std::ranges::distance(static_cast(r)) == 3); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + } + { + // Sized range (unsized sentinel type), non-copyable iterator type, rvalue-ref-qualified begin() + using It = cpp20_input_iterator; + using Sent = sentinel_wrapper>; + using R = std::ranges::subrange; + + int a[] = {1, 2, 3}; + auto r = R(It(a), Sent(It(a + 3)), 3); + assert(std::ranges::distance(r) == 3); + assert(std::ranges::distance(static_cast(r)) == 3); + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + } + { + // Sized range (sized sentinel type), non-copyable iterator type + test_ordinary, sized_sentinel>>(); + } + test_ordinary, sentinel_wrapper>>(); + test_ordinary, sentinel_wrapper>>(); + test_ordinary, sentinel_wrapper>>(); + test_ordinary, sentinel_wrapper>>(); + test_ordinary, sentinel_wrapper>>(); + test_ordinary, sentinel_wrapper>>(); + test_ordinary, sentinel_wrapper>>(); + test_ordinary>(); + + test_ordinary, sized_sentinel>>(); + test_ordinary, sized_sentinel>>(); + test_ordinary, sized_sentinel>>(); + test_ordinary, sized_sentinel>>(); + test_ordinary, sized_sentinel>>(); + test_ordinary, sized_sentinel>>(); + test_ordinary, sized_sentinel>>(); + test_ordinary>(); + test_ordinary(); + + // Calling it on a non-range isn't allowed. + static_assert(!std::is_invocable_v); + static_assert(!std::is_invocable_v); + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} Index: libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp =================================================================== --- libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -178,8 +178,8 @@ static_assert(test(std::ranges::advance, p, 5)); static_assert(test(std::ranges::advance, p, 5, a+10)); static_assert(test(std::ranges::advance, p, a+10)); -//static_assert(test(std::ranges::distance, a)); -//static_assert(test(std::ranges::distance, a, a+10)); +static_assert(test(std::ranges::distance, a)); +static_assert(test(std::ranges::distance, a, a+10)); static_assert(test(std::ranges::next, a)); static_assert(test(std::ranges::next, a, 5)); static_assert(test(std::ranges::next, a, 5, a+10));