diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -41,6 +41,7 @@ __algorithm/is_sorted.h __algorithm/is_sorted_until.h __algorithm/iter_swap.h + __algorithm/iterator_operations.h __algorithm/lexicographical_compare.h __algorithm/lower_bound.h __algorithm/make_heap.h diff --git a/libcxx/include/__algorithm/equal_range.h b/libcxx/include/__algorithm/equal_range.h --- a/libcxx/include/__algorithm/equal_range.h +++ b/libcxx/include/__algorithm/equal_range.h @@ -12,6 +12,7 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/half_positive.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/lower_bound.h> #include <__algorithm/upper_bound.h> #include <__config> @@ -54,7 +55,7 @@ _ForwardIterator __mp1 = __m; return pair<_ForwardIterator, _ForwardIterator> ( - _VSTD::__lower_bound_impl(__first, __m, __value_, __comp, __proj), + _VSTD::__lower_bound_impl<_StdIterOps>(__first, __m, __value_, __comp, __proj), _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp) ); } diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/iterator_operations.h @@ -0,0 +1,47 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H +#define _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H + +#include <__config> +#include <__iterator/advance.h> +#include <__iterator/distance.h> +#include <__iterator/iterator_traits.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +struct _RangesIterOps { + static constexpr auto advance = ranges::advance; + static constexpr auto distance = ranges::distance; +}; +#endif + +struct _StdIterOps { + + template + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void advance(_Iterator& __iter, _Distance __count) { + return std::advance(__iter, __count); + } + + template + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 + typename iterator_traits<_Iterator>::difference_type distance(_Iterator __first, _Iterator __last) { + return std::distance(__first, __last); + } + +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H diff --git a/libcxx/include/__algorithm/lower_bound.h b/libcxx/include/__algorithm/lower_bound.h --- a/libcxx/include/__algorithm/lower_bound.h +++ b/libcxx/include/__algorithm/lower_bound.h @@ -11,6 +11,7 @@ #include <__algorithm/comp.h> #include <__algorithm/half_positive.h> +#include <__algorithm/iterator_operations.h> #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> @@ -26,15 +27,15 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter __lower_bound_impl(_Iter __first, _Sent __last, const _Type& __value, _Comp& __comp, _Proj& __proj) { - auto __len = std::__ranges_distance(__first, __last); + auto __len = _IterOps::distance(__first, __last); while (__len != 0) { auto __l2 = std::__half_positive(__len); _Iter __m = __first; - std::__ranges_advance(__m, __l2); + _IterOps::advance(__m, __l2); if (std::__invoke(__comp, std::__invoke(__proj, *__m), __value)) { __first = ++__m; __len -= __l2 + 1; @@ -51,7 +52,7 @@ static_assert(__is_callable<_Compare, decltype(*__first), const _Tp&>::value, "The comparator has to be callable"); auto __proj = std::__identity(); - return std::__lower_bound_impl(__first, __last, __value_, __comp, __proj); + return std::__lower_bound_impl<_StdIterOps>(__first, __last, __value_, __comp, __proj); } template diff --git a/libcxx/include/__algorithm/ranges_binary_search.h b/libcxx/include/__algorithm/ranges_binary_search.h --- a/libcxx/include/__algorithm/ranges_binary_search.h +++ b/libcxx/include/__algorithm/ranges_binary_search.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_BINARY_SEARCH_H #define _LIBCPP___ALGORITHM_RANGES_BINARY_SEARCH_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/lower_bound.h> #include <__config> #include <__functional/identity.h> @@ -34,7 +35,7 @@ indirect_strict_weak_order> _Comp = ranges::less> _LIBCPP_HIDE_FROM_ABI constexpr bool operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const { - auto __ret = std::__lower_bound_impl(__first, __last, __value, __comp, __proj); + auto __ret = std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj); return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first)); } @@ -44,7 +45,7 @@ bool operator()(_Range&& __r, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const { auto __first = ranges::begin(__r); auto __last = ranges::end(__r); - auto __ret = std::__lower_bound_impl(__first, __last, __value, __comp, __proj); + auto __ret = std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj); return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first)); } }; diff --git a/libcxx/include/__algorithm/ranges_lower_bound.h b/libcxx/include/__algorithm/ranges_lower_bound.h --- a/libcxx/include/__algorithm/ranges_lower_bound.h +++ b/libcxx/include/__algorithm/ranges_lower_bound.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_LOWER_BOUND_H #define _LIBCPP___ALGORITHM_RANGES_LOWER_BOUND_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/lower_bound.h> #include <__config> #include <__functional/identity.h> @@ -38,7 +39,7 @@ indirect_strict_weak_order> _Comp = ranges::less> _LIBCPP_HIDE_FROM_ABI constexpr _Iter operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const { - return std::__lower_bound_impl(__first, __last, __value, __comp, __proj); + return std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj); } template (ranges::begin(__r), ranges::end(__r), __value, __comp, __proj); } }; } // namespace __lower_bound diff --git a/libcxx/include/__algorithm/ranges_upper_bound.h b/libcxx/include/__algorithm/ranges_upper_bound.h --- a/libcxx/include/__algorithm/ranges_upper_bound.h +++ b/libcxx/include/__algorithm/ranges_upper_bound.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_UPPER_BOUND_H #define _LIBCPP___ALGORITHM_RANGES_UPPER_BOUND_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/lower_bound.h> #include <__config> #include <__functional/identity.h> @@ -39,7 +40,7 @@ return !std::invoke(__comp, __rhs, __lhs); }; - return std::__lower_bound_impl(__first, __last, __value, __comp_lhs_rhs_swapped, __proj); + return std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp_lhs_rhs_swapped, __proj); } template (ranges::begin(__r), + ranges::end(__r), + __value, + __comp_lhs_rhs_swapped, + __proj); } }; } // namespace __upper_bound diff --git a/libcxx/include/__iterator/advance.h b/libcxx/include/__iterator/advance.h --- a/libcxx/include/__iterator/advance.h +++ b/libcxx/include/__iterator/advance.h @@ -194,15 +194,6 @@ #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) -template -_LIBCPP_CONSTEXPR_AFTER_CXX11 void __ranges_advance(_Iter& __first, _Sent& __last) { -#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) - return ranges::advance(__first, __last); -#else - return std::advance(__first, __last); -#endif -} - _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_ADVANCE_H 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 @@ -102,16 +102,6 @@ #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) -template -_LIBCPP_CONSTEXPR_AFTER_CXX11 -typename iterator_traits<_Iter>::difference_type __ranges_distance(_Iter __first, _Sent __second) { -#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) - return ranges::distance(__first, __second); -#else - return std::distance(__first, __second); -#endif -} - _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_DISTANCE_H diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -280,6 +280,7 @@ module is_sorted { private header "__algorithm/is_sorted.h" } module is_sorted_until { private header "__algorithm/is_sorted_until.h" } module iter_swap { private header "__algorithm/iter_swap.h" } + module iterator_operations { private header "__algorithm/iterator_operations.h" } module lexicographical_compare { private header "__algorithm/lexicographical_compare.h" } module lower_bound { private header "__algorithm/lower_bound.h" } module make_heap { private header "__algorithm/make_heap.h" } diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -78,6 +78,7 @@ #include <__algorithm/is_sorted.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/is_sorted.h'}} #include <__algorithm/is_sorted_until.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/is_sorted_until.h'}} #include <__algorithm/iter_swap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/iter_swap.h'}} +#include <__algorithm/iterator_operations.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/iterator_operations.h'}} #include <__algorithm/lexicographical_compare.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/lexicographical_compare.h'}} #include <__algorithm/lower_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/lower_bound.h'}} #include <__algorithm/make_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/make_heap.h'}} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp @@ -21,6 +21,7 @@ #include "test_iterators.h" #if TEST_STD_VER > 17 + TEST_CONSTEXPR bool eq(int a, int b) { return a == b; } TEST_CONSTEXPR bool test_constexpr() { @@ -64,6 +65,11 @@ test(Iter(v.data()), Iter(v.data()+v.size()), x); } +void test_instantiation() { + auto iter = Cpp20HostileIterator(); + std::lower_bound(iter, iter, 0); +} + int main(int, char**) { int d[] = {0, 1, 2, 3}; diff --git a/libcxx/test/support/test_iterators.h b/libcxx/test/support/test_iterators.h --- a/libcxx/test/support/test_iterators.h +++ b/libcxx/test/support/test_iterators.h @@ -794,4 +794,59 @@ #endif // TEST_STD_VER > 17 +template +struct IteratorAdaptorBase { + using OutTraits = std::iterator_traits; + using iterator_category = typename OutTraits::iterator_category; + using value_type = typename OutTraits::value_type; + using pointer = typename OutTraits::pointer; + using reference = typename OutTraits::reference; + using difference_type = typename OutTraits::difference_type; + + IteratorAdaptorBase() {} + IteratorAdaptorBase(Iterator) {} + + Sub& sub() { return static_cast(*this); } + const Sub& sub() const { return static_cast(*this); } + + const Iterator& base() const { return it_; } + + reference get() const { return *it_; } + reference operator*() const { return *it_; } + pointer operator->() const { return it_; } + reference operator[](difference_type) const { return *it_; } + + Sub& operator++() { return static_cast(*this); } + Sub& operator--() { return static_cast(*this); } + Sub operator++(int) { return static_cast(*this); } + Sub operator--(int) { return static_cast(*this); } + + Sub& operator+=(difference_type) { return static_cast(*this); } + Sub& operator-=(difference_type) { return static_cast(*this); } + bool operator==(Sub) const { return false; } + bool operator!=(Sub) const { return false; } + bool operator==(Iterator b) const { return *this == Sub(b); } + bool operator!=(Iterator b) const { return *this != Sub(b); } + + friend Sub operator+(Sub, difference_type) { Sub(); } + friend Sub operator+(difference_type, Sub) { Sub(); } + friend Sub operator-(Sub, difference_type) { Sub(); } + friend difference_type operator-(Sub, Sub) { return 0; } + + friend bool operator<(Sub, Sub) { return false; } + friend bool operator>(Sub, Sub) { return false; } + friend bool operator<=(Sub, Sub) { return false; } + friend bool operator>=(Sub, Sub) { return false; } + + private: + Iterator it_; +}; + +template +struct Cpp20HostileIterator + : IteratorAdaptorBase, It> { + Cpp20HostileIterator() {} + Cpp20HostileIterator(It it); +}; + #endif // SUPPORT_TEST_ITERATORS_H