[libc++] Fix std::lower_bound with C++20-hostile iterators

[philnik]

• Generate files

[EricWF]

Is this missing module map changes?

This needs a test that fails prior to the fix. Otherwise this looks good once the inline comments are addressed.

libcxx/include/__algorithm/generic_algorithm_helper.h

18 ↗

(On Diff #436161)

• Inside namespace std please.
• Scoped enum please. Implicit conversions are evil.
• Pin the underlying type to prevent -fshort-enums from changing it.

libcxx/include/__iterator/advance.h

197–198

Same comment about this #ifdef as I left on __distance.

libcxx/include/__iterator/distance.h

13

I would love a more descriptive name for this header.

105–106

Can we lose this #ifdef, since I assume we are not passing _Ranges when we don't have complete ranges?
And if we are passing _Ranges we shouldn't be silently falling back to std::

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp

25

Can we write this without concepts so we can test it in all the dialects it affects?

Also, I don't think this tests anything. It's my understanding that concepts can't detect failures outside of the immediate context. So because the call itself is well formed, this test will always pass.

[EricWF]

libcxx/test/support/test_iterators.h

831

You'll probably need to stub out these functions so we can write a actual runtime test, since the compile time tests can't catch the breakage we're fixing here.

[philnik]

• Address comments

libcxx/include/__iterator/distance.h

13

Do you have a good suggestion? I think namespace is a lot worse than what I've got currently.

105–106

ranges::distance has to exist for if constexpr to be happy. I've added a static_assert(__ns == _Namespace::_Std).

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp

25

What exactly do you mean? C++20 is the only dialect where it is interesting AFAICT. Otherwise we always call std::advance and std::distance anyways.

For HasLowerBound to be true the instantiation of std::lower_bound has to be valid. So if HasLowerBound is true int main() { std::lower_bound(iter, sent, 0); } has to compile.

[EricWF]

This LGTM, as a temporary fix; once we test it.

I'm going to request further changes, but this is a OK intermediate state, so we don't have to address them before landing this.
Thank you for you diligent work fixing this on the weekend.

---

Given the mess with C++03 and strong enumerations types, I'm believe we should move to using a policy object like

struct RangesIterOps {
  static It advance(...);
  static diff_t distance(...);
};
struct StdIterOps {
  static It advance(...);
  static diff_t distance(...);
};

I think it has the added benefits of:

• Making it clear exactly what set of functions are overloaded for std iterators and ranges iterators. (it's the set of functions provided by the policy object, rather than a subset of functions discoverable only by reading every single iterator/ranges headers to see which are overloaded).
• Removing the need for almost every single compile time branch (both #ifdef and if constexpr.) currently used by __ranges_distance and __ranges_advance. And every single compile time branch in libc++ is a bug manifest, or at least a future bug that will manifest; at least that's been my experience).
• It removes the need for the __ranges_foo overloads entirely. Because it's not obvious to the reader that __distance is std::distance, and __ranges_distance is a dispatcher that may call ranges::distance or std::distance. In fact, __ranges_distance seems easily mistakable for the ranges::distance implementation.
• It further isolates us from differences in behavior, for example like iterator_traits<_Iter>::difference_type being different than std::iter_distance_t<Iter> and similar.

libcxx/include/__algorithm/generic_algorithm_helper.h

9 ↗

(On Diff #436235)

I'm going to complain about the header name again.

One of the primary reasons I've been given for splitting up the headers is that "it makes it easier to know where an implementation actually lives", but "generic_algorithm_helper.h" doesn't indicate to me that it contains the _Namespace utility.

21 ↗

(On Diff #436235)

Or struct _Namespace { enum : bool { _Std, _Ranges }; };. Having the symbol have two entirely different meanings has a mean code smell.

libcxx/include/__iterator/distance.h

105–106

Ah, that makes sense.

This further pushes me towards the idea that a IteratorOperations policy object is the right way to go.

105–106

Is it the case that iterator_traits<_Iter>::difference_type is always the same type as std::iter_distance_t<_Iter>? It's not obvious that it is a requirement.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp

25

That's not correct. Concepts only consider the validity of the call expression, not everything that would be instantiated. (Because it can't back of of an instantiation once it's started instantiating, since there could be side effects and the like). So it doesn't consider the body of lower bound.

This test passes without your fix. See https://godbolt.org/z/5hfv8njeo

So we need a test that actually runs and produces an output to be sure we've fully instantiated everything.

[EricWF]

libcxx/include/__algorithm/generic_algorithm_helper.h

21 ↗

(On Diff #436235)

That said, I don't really care to see this addressed at the moment. So just ignore me.

[philnik]

• Address comments

[EricWF]

Thank you!

libcxx/include/__algorithm/iterator_operations.h

25

That's beautiful as we avoid any additional instantiations!

[EricWF]

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp

69

I feel like the fact that this doesn't produce a linker error is a happy coincidence rather than a required behavior.

[philnik]

• Generate files

[philnik]

• Try to fix CI

libcxx/include/__iterator/distance.h

105–106

I'm not sure. Might be another bug. I'm switching to a policy-based solution, so this shouldn't be a problem.

[philnik]

• Next try

[philnik]

• And another one

[philnik]

• Add stubs

[ldionne]

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp

72

We need to add this test for equal_range, upper_bound and other STL-classic algorithms that we fixed with this patch.

libcxx/include/CMakeLists.txt

set(files
   __algorithm/inplace_merge.h
   __algorithm/is_heap.h
   __algorithm/is_heap_until.h
   __algorithm/is_partitioned.h
   __algorithm/is_permutation.h
   __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
   __algorithm/max.h
   __algorithm/max_element.h
   __algorithm/merge.h
   __algorithm/min.h
   __algorithm/min_element.h

libcxx/include/__algorithm/equal_range.h

while (__len != 0)
             __len = __l2;
         }
         else
         {
             auto __proj = std::__identity();
             _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)
                    );
         }
     }
     return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
 }
 
 template <class _ForwardIterator, class _Tp, class _Compare>

libcxx/include/__algorithm/iterator_operations.h

+//===----------------------------------------------------------------------===//
+//
+// 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 <class _Iterator, class _Distance>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR void advance(_Iterator& __iter, _Distance __count) {
+    return std::advance(__iter, __count);
+  }
+
+  template <class _Iterator>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR
+  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

libcxx/include/__algorithm/lower_bound.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_LOWER_BOUND_H
 #define _LIBCPP___ALGORITHM_LOWER_BOUND_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/half_positive.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/is_callable.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Iter, class _Sent, class _Type, class _Proj, class _Comp>
+template <class _IterOps, 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 = _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;
     } else {
       __len = __l2;
     }
   }
   return __first;
 }
 
 template <class _ForwardIterator, class _Tp, class _Compare>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) {
   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 <class _ForwardIterator, class _Tp>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) {
   return std::lower_bound(__first, __last, __value_,
                           __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_LOWER_BOUND_H

libcxx/include/__algorithm/ranges_binary_search.h

 
 namespace ranges {
 namespace __binary_search {
 struct __fn {
   template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _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));
   }
 
   template <forward_range _Range, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   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));
   }
 };
 } // namespace __binary_search
 
 inline namespace __cpo {
   inline constexpr auto binary_search = __binary_search::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_BINARY_SEARCH_H

libcxx/include/__algorithm/ranges_lower_bound.h

 //===----------------------------------------------------------------------===//
 //
 // 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___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>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/advance.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>

 namespace ranges {
 
 namespace __lower_bound {
 struct __fn {
   template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _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 <forward_range _Range, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   borrowed_iterator_t<_Range> operator()(_Range&& __r,
                                          const _Type& __value,
                                          _Comp __comp = {},
                                          _Proj __proj = {}) const {
-    return std::__lower_bound_impl(ranges::begin(__r), ranges::end(__r), __value, __comp, __proj);
+    return std::__lower_bound_impl<_RangesIterOps>(ranges::begin(__r), ranges::end(__r), __value, __comp, __proj);
   }
 };
 } // namespace __lower_bound
 
 inline namespace __cpo {
   inline constexpr auto lower_bound = __lower_bound::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_LOWER_BOUND_H

libcxx/include/__algorithm/ranges_upper_bound.h

struct __fn {
   template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const {
     auto __comp_lhs_rhs_swapped = [&](const auto& __lhs, const auto& __rhs) {
       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 <forward_range _Range, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   borrowed_iterator_t<_Range> operator()(_Range&& __r,
                                          const _Type& __value,
                                          _Comp __comp = {},
                                          _Proj __proj = {}) const {
     auto __comp_lhs_rhs_swapped = [&](const auto& __lhs, const auto& __rhs) {
       return !std::invoke(__comp, __rhs, __lhs);
     };
 
-    return std::__lower_bound_impl(ranges::begin(__r), ranges::end(__r), __value, __comp_lhs_rhs_swapped, __proj);
+    return std::__lower_bound_impl<_RangesIterOps>(ranges::begin(__r),
+                                                   ranges::end(__r),
+                                                   __value,
+                                                   __comp_lhs_rhs_swapped,
+                                                   __proj);
   }
 };
 } // namespace __upper_bound
 
 inline namespace __cpo {
   inline constexpr auto upper_bound = __upper_bound::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_UPPER_BOUND_H

libcxx/include/__iterator/advance.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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___ITERATOR_ADVANCE_H
 #define _LIBCPP___ITERATOR_ADVANCE_H
 
+#include <__algorithm/generic_algorithm_helper.h>
 #include <__assert>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 #include <__utility/unreachable.h>
 #include <concepts>

 } // namespace __advance
 
 inline namespace __cpo {
   inline constexpr auto advance = __advance::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
-template <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);
-#else
-  return std::advance(__first, __last);
-#endif
-}
-
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_ADVANCE_H

libcxx/include/__iterator/distance.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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___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>
 #include <__iterator/iterator_traits.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/size.h>
 #include <type_traits>

 } // namespace __distance
 
 inline namespace __cpo {
   inline constexpr auto distance = __distance::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
-template <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);
-#else
-  return std::distance(__first, __second);
-#endif
-}
-
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_DISTANCE_H

libcxx/include/module.modulemap.in

module __algorithm {
       module find_end                 { private header "__algorithm/find_end.h" }
       module find_first_of            { private header "__algorithm/find_first_of.h" }
       module find_if                  { private header "__algorithm/find_if.h" }
       module find_if_not              { private header "__algorithm/find_if_not.h" }
       module for_each                 { private header "__algorithm/for_each.h" }
       module for_each_n               { private header "__algorithm/for_each_n.h" }
       module generate                 { private header "__algorithm/generate.h" }
       module generate_n               { private header "__algorithm/generate_n.h" }
+      module generic_algorithm_helper { private header "__algorithm/generic_algorithm_helper.h" }
       module half_positive            { private header "__algorithm/half_positive.h" }
       module in_found_result          { private header "__algorithm/in_found_result.h" }
       module in_fun_result            { private header "__algorithm/in_fun_result.h" }
       module in_in_out_result         { private header "__algorithm/in_in_out_result.h" }
       module in_in_result             { private header "__algorithm/in_in_result.h" }
       module in_out_out_result        { private header "__algorithm/in_out_out_result.h" }
       module in_out_result            { private header "__algorithm/in_out_result.h" }
       module includes                 { private header "__algorithm/includes.h" }

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/inplace_merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/inplace_merge.h'}}
 #include <__algorithm/is_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/is_heap.h'}}
 #include <__algorithm/is_heap_until.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/is_heap_until.h'}}
 #include <__algorithm/is_partitioned.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/is_partitioned.h'}}
 #include <__algorithm/is_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/is_permutation.h'}}
 #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'}}
 #include <__algorithm/max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/max.h'}}
 #include <__algorithm/max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/max_element.h'}}
 #include <__algorithm/merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/merge.h'}}
 #include <__algorithm/min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/min.h'}}
 #include <__algorithm/min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/min_element.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp

 #include <vector>
 #include <cassert>
 #include <cstddef>
 
 #include "test_macros.h"
 #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() {
     int ia[] = {1, 3, 6, 7};
 
     return (std::lower_bound(std::begin(ia), std::end(ia), 2) == ia+1)
         && (std::lower_bound(std::begin(ia), std::end(ia), 3) == ia+1)
         && (std::lower_bound(std::begin(ia), std::end(ia), 9) == std::end(ia))
         ;
for (std::size_t i = 0; i < v.size(); ++i)
         if (++x == M)
             x = 0;
     }
     std::sort(v.begin(), v.end());
     for (x = 0; x <= M; ++x)
         test(Iter(v.data()), Iter(v.data()+v.size()), x);
 }
 
+void test_instantiation() {
+    auto iter = Cpp20HostileIterator<int*>{};
+    std::lower_bound(iter, iter, 0);
+}
+
 int main(int, char**)
 {
     int d[] = {0, 1, 2, 3};
     for (int* e = d; e <= d+4; ++e)
         for (int x = -1; x <= 4; ++x)
             test(d, e, x);
 
     test<forward_iterator<const int*> >();

libcxx/test/support/test_iterators.h

public:
 
   constexpr friend bool operator==(const Iterator& lhs, const Iterator& rhs) { return lhs.ptr_ == rhs.ptr_; }
 };
 
 } // namespace adl
 
 #endif // TEST_STD_VER > 17
 
+template <class Sub, class Iterator>
+struct IteratorAdaptorBase {
+  using OutTraits = std::iterator_traits<Iterator>;
+  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 <typename It>
+struct Cpp20HostileIterator
+    : IteratorAdaptorBase<Cpp20HostileIterator<It>, It> {
+  Cpp20HostileIterator() {}
+  Cpp20HostileIterator(It it);
+};
+
 #endif // SUPPORT_TEST_ITERATORS_H