diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -25,6 +25,7 @@ __algorithm/for_each_n.h __algorithm/generate.h __algorithm/generate_n.h + __algorithm/generic_algorithm_helper.h __algorithm/half_positive.h __algorithm/in_found_result.h __algorithm/in_fun_result.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 @@ -54,7 +54,7 @@ _ForwardIterator __mp1 = __m; return pair<_ForwardIterator, _ForwardIterator> ( - _VSTD::__lower_bound_impl(__first, __m, __value_, __comp, __proj), + _VSTD::__lower_bound_impl<_Namespace::_Std>(__first, __m, __value_, __comp, __proj), _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp) ); } diff --git a/libcxx/include/__algorithm/generic_algorithm_helper.h b/libcxx/include/__algorithm/generic_algorithm_helper.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/generic_algorithm_helper.h @@ -0,0 +1,23 @@ +//===----------------------------------------------------------------------===// +// +// 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_GENERIC_ALGORIHTM_HELPER_H +#define _LIBCPP___ALGORIHTM_GENERIC_ALGORIHTM_HELPER_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +enum _Namespace { + _Ranges, + _Std, +}; + +#endif // _LIBCPP___ALGORIHTM_GENERIC_ALGORIHTM_HELPER_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 @@ -10,6 +10,7 @@ #define _LIBCPP___ALGORITHM_LOWER_BOUND_H #include <__algorithm/comp.h> +#include <__algorithm/generic_algorithm_helper.h> #include <__algorithm/half_positive.h> #include <__config> #include <__functional/identity.h> @@ -26,15 +27,15 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template <_Namespace __ns, class _Iter, class _Sent, class _Type, class _Proj, class _Comp> _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 = std::__ranges_distance<__ns>(__first, __last); while (__len != 0) { auto __l2 = std::__half_positive(__len); _Iter __m = __first; - std::__ranges_advance(__m, __l2); + std::__ranges_advance<__ns>(__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<_Namespace::_Std>(__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 @@ -34,7 +34,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<_Namespace::_Ranges>(__first, __last, __value, __comp, __proj); return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first)); } @@ -44,7 +44,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<_Namespace::_Ranges>(__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 @@ -38,7 +38,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<_Namespace::_Ranges>(__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 @@ -39,7 +39,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<_Namespace::_Ranges>(__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 @@ -10,6 +10,7 @@ #ifndef _LIBCPP___ITERATOR_ADVANCE_H #define _LIBCPP___ITERATOR_ADVANCE_H +#include <__algorithm/generic_algorithm_helper.h> #include <__assert> #include <__config> #include <__iterator/concepts.h> @@ -194,10 +195,14 @@ #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) -template +template <_Namespace __ns, class _Iter, class _Sent> _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); + if constexpr (__ns == _Namespace::_Ranges) { + return ranges::advance(__first, __last); + } else { + return std::advance(__first, __last); + } #else return std::advance(__first, __last); #endif 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 @@ -10,6 +10,7 @@ #ifndef _LIBCPP___ITERATOR_DISTANCE_H #define _LIBCPP___ITERATOR_DISTANCE_H +#include <__algorithm/generic_algorithm_helper.h> #include <__config> #include <__iterator/concepts.h> #include <__iterator/incrementable_traits.h> @@ -102,11 +103,15 @@ #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) -template +template <_Namespace __ns, class _Iter, class _Sent> _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); + if constexpr (__ns == _Namespace::_Ranges) { + return ranges::distance(__first, __second); + } else { + return std::distance(__first, __second); + } #else return std::distance(__first, __second); #endif 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,12 @@ #include "test_iterators.h" #if TEST_STD_VER > 17 + +template +concept HasLowerBound = requires(Iter iter, Iter sent) { std::lower_bound(iter, sent, 0); }; + +static_assert(HasLowerBound>); + TEST_CONSTEXPR bool eq(int a, int b) { return a == b; } TEST_CONSTEXPR bool test_constexpr() { 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(); + const Sub& sub() const; + + const Iterator& base() const; + + reference get() const; + reference operator*() const; + pointer operator->() const; + reference operator[](difference_type d) const ; + + Sub& operator++(); + Sub& operator--(); + Sub operator++(int /*unused*/); + Sub operator--(int /*unused*/); + + Sub& operator+=(difference_type d); + Sub& operator-=(difference_type d); + bool operator==(Sub b) const; + bool operator!=(Sub b) const; + bool operator==(Iterator b) const { return *this == Sub(b); } + bool operator!=(Iterator b) const { return *this != Sub(b); } + + friend Sub operator+(Sub it, difference_type d); + friend Sub operator+(difference_type d, Sub it); + friend Sub operator-(Sub it, difference_type d) ; + friend difference_type operator-(Sub a, Sub b) ; + + friend bool operator<(Sub a, Sub b); + friend bool operator>(Sub a, Sub b); + friend bool operator<=(Sub a, Sub b); + friend bool operator>=(Sub a, Sub b); + + private: + Iterator it_; +}; + +template +struct Cpp20HostileIterator + : IteratorAdaptorBase, It> { + Cpp20HostileIterator(); + Cpp20HostileIterator(It it); +}; + #endif // SUPPORT_TEST_ITERATORS_H