`<algorithm>`: `ranges::find()` rejects some sentinels due to iterator unwrapping

[StephanTLavavej]

Reported by Bjarne Stroustrup. Repros with VS 2022 17.2 Preview 1.

C:\Temp>type meow.cpp

#include <algorithm>
#include <cassert>
#include <vector>
using namespace std;

using Iter = vector<int>::iterator;

struct Sentinel {
    Sentinel() : val(0) {}
    explicit Sentinel(const int n) : val(n) {}
    bool operator==(const Iter& it) const {
        return val == *it;
    }
#ifdef WORKAROUND
    bool operator==(int* const ptr) const {
        return val == *ptr;
    }
#endif // WORKAROUND
    int val;
};

int main() {
    vector<int> v{11, 22, 33, 44, 55};
    Iter first{v.begin()};
    Sentinel last{33};

    assert(ranges::find(first, last, 22) == first + 1); // finds value
    assert(ranges::find(first, last, 44) == first + 2); // stops at sentinel
}

Click to expand lengthy compiler output.

C:\Temp>cl /EHsc /nologo /W4 /std:c++latest meow.cpp && meow
meow.cpp
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\xutility(5275): error C2672: 'std::ranges::_Find_unchecked': no matching overloaded function found
meow.cpp(27): note: see reference to function template instantiation '_It std::ranges::_Find_fn::operator ()<Iter,Sentinel,int,std::identity>(_It,_Se,const _Ty &,_Pj) const' being compiled
        with
        [
            _It=Iter,
            _Se=Sentinel,
            _Ty=int,
            _Pj=std::identity
        ]
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\xutility(5276): error C7602: 'std::ranges::_Find_unchecked': the associated constraints are not satisfied
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\xutility(5221): note: see declaration of 'std::ranges::_Find_unchecked'
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\xutility(5278): error C3536: '_UResult': cannot be used before it is initialized

C:\Temp>clang-cl /EHsc /nologo /W4 /std:c++latest meow.cpp && meow
In file included from meow.cpp:1:
In file included from C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\algorithm:11:
In file included from C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\xmemory:16:
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\xutility(5275,29): error: no
      matching function for call to '_Find_unchecked'
            auto _UResult = _RANGES _Find_unchecked(
                            ^~~~~~~~~~~~~~~~~~~~~~~
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\yvals_core.h(1411,20): note:
      expanded from macro '_RANGES'
#define _RANGES    ::std::ranges::
                   ^
meow.cpp(27,24): note: in instantiation of function template specialization
      'std::ranges::_Find_fn::operator()<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<int>>>, Sentinel,
      int, std::identity>' requested here
    assert(ranges::find(first, last, 22) == first + 1); // finds value
                       ^
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\xutility(5221,30): note:
      candidate template ignored: constraints not satisfied [with _It = int *, _Se = Sentinel, _Ty = int, _Pj =
      std::identity]
    _NODISCARD constexpr _It _Find_unchecked(_It _First, const _Se _Last, const _Ty& _Val, _Pj _Proj = {}) {
                             ^
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\xutility(5219,35): note:
      because 'sentinel_for<Sentinel, int *>' evaluated to false
    template <input_iterator _It, sentinel_for<_It> _Se, class _Ty, class _Pj = identity>
                                  ^
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\xutility(787,8): note: because
      '_Weakly_equality_comparable_with<Sentinel, int *>' evaluated to false
    && _Weakly_equality_comparable_with<_Se, _It>;
       ^
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\concepts(198,5): note: because
      '_Half_equality_comparable<Sentinel, int *>' evaluated to false
    _Half_equality_comparable<_Ty1, _Ty2> && _Half_equality_comparable<_Ty2, _Ty1>;
    ^
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\concepts(192,15): note: because
      '__x == __y' would be invalid: invalid operands to binary expression ('const remove_reference_t<Sentinel>'
      (aka 'const Sentinel') and 'const remove_reference_t<int *>' (aka 'int *const'))
        { __x == __y } -> _Boolean_testable;
              ^
meow.cpp(28,12): error: no matching function for call to object of type 'const std::ranges::_Find_fn'
    assert(ranges::find(first, last, 44) == first + 2); // stops at sentinel
           ^~~~~~~~~~~~
C:\Program Files (x86)\Windows Kits\10\include\10.0.19041.0\ucrt\assert.h(37,17): note: expanded from macro 'assert'
            (!!(expression)) ||                                                              \
                ^~~~~~~~~~
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\xutility(5273,34): note:
      candidate template ignored: substitution failure [with _It =
      std::_Vector_iterator<std::_Vector_val<std::_Simple_types<int>>>, _Se = Sentinel, _Ty = int, _Pj = std::identity]
        _NODISCARD constexpr _It operator()(_It _First, _Se _Last, const _Ty& _Val, _Pj _Proj = {}) const {
                                 ^
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.32.31114\include\xutility(5284,56): note:
      candidate template ignored: substitution failure [with _Rng =
      std::_Vector_iterator<std::_Vector_val<std::_Simple_types<int>>> &, _Ty = Sentinel, _Pj = int]: constraints not
      satisfied for alias template 'borrowed_iterator_t' [with _Rng =
      std::_Vector_iterator<std::_Vector_val<std::_Simple_types<int>>> &]
        _NODISCARD constexpr borrowed_iterator_t<_Rng> operator()(
                             ~~~~~~~~~~~~~~~~~~~       ^
2 errors generated.

C:\Temp>cl /EHsc /nologo /W4 /std:c++latest meow.cpp /DWORKAROUND && meow
meow.cpp

C:\Temp>clang-cl /EHsc /nologo /W4 /std:c++latest meow.cpp /DWORKAROUND && meow

C:\Temp>

The problem appears to be that ranges::find() takes input_iterator _It, sentinel_for<_It> _Se which this Iter, Sentinel pair satisfies, but then unwraps them:

STL/stl/inc/xutility

Lines 5279 to 5284 in ff54450

	template <input_iterator _It, sentinel_for<_It> _Se, class _Ty, class _Pj = identity>
	requires indirect_binary_predicate<ranges::equal_to, projected<_It, _Pj>, const _Ty*>
	_NODISCARD constexpr _It operator()(_It _First, _Se _Last, const _Ty& _Val, _Pj _Proj = {}) const {
	_Adl_verify_range(_First, _Last);
	auto _UResult = _RANGES _Find_unchecked(
	_Get_unwrapped(_STD move(_First)), _Get_unwrapped(_STD move(_Last)), _Val, _Pass_fn(_Proj));

_Find_unchecked() also takes input_iterator _It, sentinel_for<_It> _Se, but these are unwrapped: 🙀

STL/stl/inc/xutility

Lines 5227 to 5229 in ff54450

	template <input_iterator _It, sentinel_for<_It> _Se, class _Ty, class _Pj = identity>
	requires indirect_binary_predicate<ranges::equal_to, projected<_It, _Pj>, const _Ty*>
	_NODISCARD constexpr _It _Find_unchecked(_It _First, const _Se _Last, const _Ty& _Val, _Pj _Proj = {}) {

Although we could compare Iter == Sentinel, we can't compare int* == Sentinel, so this fails to compile (with an accurate but unhelpful warning in MSVC; Clang's error is lengthy but explains the chain of events clearly).

We need to do something different here, although I'm not immediately sure what. (Unwrapping only when the unwrapped types would satisfy sentinel_for could be a solution.)

This problem may also be extremely widespread throughout the range algorithms - marking as high priority unless we determine that this is an isolated obscure issue.

[miscco]

Urgh,

That is a nasty one and I am really close to saying. Screw that and use a proper ranges facility like take_while

Long story short, this does affects all ranges algorithms. We would need to introduce a new helper that checks both _It and _Se

template<input_iterator _It, sentinel_for<_It> _Se>
iter_sentinel_result_t _Get_unwrapped(_It _First, _Se _Last) const noexcept {
    if constexpr(sentinel_for<decltype(_Get_unwrapped(_STD declval<_It>()), _Get_unwrapped(_STD decltype<_Se>())>) {
        return { _Get_unwrapped(_STD move(_First)), _Get_unwrapped(_STD move(_Last)) };
    } else {
        return { _STD move(_First), _STD move(_Last) };
    }
}

Casey Carter (@CaseyCarter) does that fit?

[CaseyCarter]

Casey Carter (@CaseyCarter) does that fit?

It's close. We are forbidden to "duck type" by throwing arbitrary expressions at user types to see what works. If a user passes a custom sentinel and a standard library iterator to an algorithm we're well within our rights to evaluate sentinel_for<S, I>, but sentinel_for<S, _Unwrapped_t<I>> would be out-of-contract. I think we should unwrap only when both iterator and sentinel types opt-in to the unwrapping machinery, that is, when both _Unwrappable_v<I> and _Unwrappable_v<S> are true. It's not clear to me if we should also check if the resulting types model sentinel_for, or if we should simply require that they do so.

(Yes, we can make default_sentinel and unreachable_sentinel unwrap to themselves. It's only a teensy bit weird.)

[strega-nil-ms]

Fixed by #3024