Question: would it be possible/worthwhile to do a similar optimization for the iterator + sentinel overload? It seems it should be possible to use std::size for the case where the sentinel is the same type as the iterator, or perhaps use subrange (presuming the overhead is negligible and easily optimizable).

Hmm, I'd like to double-check this. IIUC, the relevant section is

{i, i + (last2 - first2)}, where i is the first iterator in the range [first1, last1 - (last2 - first2)) such that for every non-negative integer n less than last2 - first2 the condition

bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n)))) is true.

However, if last2 - first2 is zero, there exists no non-negative integer n less than that. It seems like it would mean that no such iterator i can exist and thus the algorithm should go to the next clause and return {last1, last1}.

Hide from ABI?

Question: why is __m1 incremented? It was not incremented in the original.

Does this need to be in an else branch for this code to be guaranteed to be eliminated? Perhaps you might need to add another if constexpr (sized_sentinel_for<_Sent1, _Iter1> || sized_sentinel_for<_Sent2, _Iter2>) { condition to wrap up the optimizations?

Nit: consider moving the iterators.

Can you remove the trailing underscore from the name? (I know it's a preexistent thing)

Can you use using?

Same comment as in search.h regarding whether this should be an else branch of the if constexpr.

Nit: unnecessary blank line.

Should this work if _Sent is a different type from _Iter? If not, perhaps static assert?

Same question re. static_assert here.

I think I'd rather avoid adding these two functions. __make_begin_reverse_iterator seems to exist only for symmetry, but more importantly, the difference between language versions that is being abstracted away by __make_end_reverse_iterator is not specific to reverse iterators. How about something like

template <class _Iter, class _Sent>
decltype(auto) __end_iterator(const _Iter& __first, _Sent& __last) {
#if _LIBCPP_STD_VER > 17
    return ranges::next(__first, __last);
#else
    static_assert(is_same<_Iter, _Sent>::value, "Iterator and Sentinel have to be the same type pre-C++20");
    return __last;
#endif
}

and then use this function when creating the reverse iterators at the call site?

Please update the synopsis.

Missing synopsis.

Please check SFINAE as well.

Consider a helper function to take care of both the iterator overload and the range overload (can be done in a follow-up if you prefer).

Should be find_end.

Nit: decltype(auto).

Should be search_n.

why <=? as the size is unsigned, is it just ==0?

does it need to check _LIBCPP_HAS_NO_INCOMPLETE_RANGES too?

What if this line is called on C++20 mode with the classic algorithm/classic iterator?

C++20 sentinel_for requires the sentinel to be semiregular. But C++ 17's iterator are not required to be default constructible.

what happens if you call the classic algorithm with a classic iterator that is not default constructible?

This line can be set to done as well...

question: why do we need another alias for ranges::advance? we could have another overload for classic one with the same name

re @bgraur's bug report. this line should be

static_assert(__is_callable<_BinaryPredicate, decltype(*__first),  const _Tp&>::value, "BinaryPredicate has to be callable");