diff --git a/libcxx/docs/Status/Cxx2bIssues.csv b/libcxx/docs/Status/Cxx2bIssues.csv --- a/libcxx/docs/Status/Cxx2bIssues.csv +++ b/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","|Nothing To Do|","","|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","|Complete|","14.0" `3470 `__,"``convertible-to-non-slicing`` seems to reject valid case","October 2021","|Complete|","14.0","|ranges|" diff --git a/libcxx/docs/Status/RangesPaper.csv b/libcxx/docs/Status/RangesPaper.csv --- a/libcxx/docs/Status/RangesPaper.csv +++ b/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 and Arthur O'Dwyer,✅ `[predef.iterators] `_,Updates to predefined iterators.,"| [iterator.concepts] | [iterator.cust.swap] | [iterator.cust.move]",Unassigned,Not started diff --git a/libcxx/include/__iterator/distance.h b/libcxx/include/__iterator/distance.h --- a/libcxx/include/__iterator/distance.h +++ b/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_CONCEPTS) + +// [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, __uncvref_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_CONCEPTS) + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_DISTANCE_H diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp @@ -0,0 +1,236 @@ +//===----------------------------------------------------------------------===// +// +// 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(I&& first, S last); // TODO: update when LWG3664 is resolved + +#include +#include + +#include "test_iterators.h" +#include "test_macros.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); + ASSERT_SAME_TYPE(decltype(std::ranges::distance(It(a), Sent(It(a)))), std::iter_difference_t); + } + { + It first = It(a); + auto last = Sent(It(a + 3)); + assert(std::ranges::distance(first, last) == 3); + + // Test all const/ref-qualifications of both operands. + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == 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); + + // Test all const/ref-qualifications of both operands. + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -3); + assert(std::ranges::distance(static_cast(first), static_cast(last)) == -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); + ASSERT_SAME_TYPE(decltype(std::ranges::distance(It(a), Sent(It(a)))), std::iter_difference_t); + } + { + 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); + } +} + +struct StrideCounter { + int *it_; + int *inc_; + using value_type = int; + using difference_type = int; + explicit StrideCounter(); + constexpr explicit StrideCounter(int *it, int *inc) : it_(it), inc_(inc) {} + constexpr auto& operator++() { ++it_; *inc_ += 1; return *this; } + StrideCounter operator++(int); + int& operator*() const; + bool operator==(StrideCounter) const; +}; +static_assert(std::forward_iterator); +static_assert(!std::sized_sentinel_for); + +struct SizedStrideCounter { + int *it_; + int *minus_; + using value_type = int; + explicit SizedStrideCounter(); + constexpr explicit SizedStrideCounter(int *it, int *minus) : it_(it), minus_(minus) {} + SizedStrideCounter& operator++(); + SizedStrideCounter operator++(int); + int& operator*() const; + bool operator==(SizedStrideCounter) const; + constexpr int operator-(SizedStrideCounter rhs) const { *minus_ += 1; return it_ - rhs.it_; } +}; +static_assert(std::forward_iterator); +static_assert(std::sized_sentinel_for); + +constexpr void test_stride_counting() { + { + int a[] = {1, 2, 3}; + int inc = 0; + StrideCounter first(a, &inc); + StrideCounter last(a+3, nullptr); + std::same_as auto result = std::ranges::distance(first, last); + assert(result == 3); + assert(inc == 3); + } + { + int a[] = {1, 2, 3}; + int minus = 0; + SizedStrideCounter first(a, &minus); + SizedStrideCounter last(a+3, nullptr); + std::same_as auto result = std::ranges::distance(first, last); + assert(result == 3); + assert(minus == 1); + } +} + +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; +} diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/lwg3664.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/lwg3664.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/lwg3664.pass.cpp @@ -0,0 +1,72 @@ +//===----------------------------------------------------------------------===// +// +// 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_; } + friend constexpr void operator-(EvilSentinel s, int(&)[3]) = delete; + friend constexpr void operator-(EvilSentinel s, int(&&)[3]) = delete; + friend constexpr void operator-(EvilSentinel s, const int(&)[3]) = delete; + friend constexpr void operator-(EvilSentinel s, const int(&&)[3]) = delete; +}; +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; +} diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/range.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/range.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/range.pass.cpp @@ -0,0 +1,110 @@ +//===----------------------------------------------------------------------===// +// +// 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" +#include "test_macros.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); + ASSERT_SAME_TYPE(decltype(std::ranges::distance(r)), std::ranges::range_difference_t); +} + +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); + ASSERT_SAME_TYPE(decltype(std::ranges::distance(a)), std::ptrdiff_t); + ASSERT_SAME_TYPE(decltype(std::ranges::distance(a)), std::ranges::range_difference_t); + } + { + // 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; +} diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/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));