Range algorithms don't work when used with unwrappable iterators and custom sentinels

[JMazurkiewicz]

Description

Range algorithms, constructors (#2806) and iterator operations won't compile when used with unwrappable iterator "It" (e.g. string::const_iterator) and custom sentinel "Se", such that sentinel_for<Se, X> is true if and only if X is convertible to It.

Impact

Custom sentinels and unwrappable iterators don't work together

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>

using namespace std;

struct question_sentinel_t {
    constexpr bool operator==(string::const_iterator it) const noexcept {
        return *it == '?' || *it == '\0';
    }
};

int main() {
    string str = "qwerty?uiopasdfghjklzxcvbnm";
    ranges::copy(str.begin(), question_sentinel_t{}, ostreambuf_iterator<char>{cout});
    cout << '\n';
}

• Expected behavior: This code should compile (compiler explorer).
• Expected output: qwerty

Ranges with custom sentinels and unwrappable iterators cannot be used as inputs to algorithms

#include <algorithm>
#include <iostream>
#include <ranges>
#include <string>

using namespace std;

template<ranges::view V>
    requires ranges::input_range<V>
class question_view : public ranges::view_interface<question_view<V>> {
private:
    struct sentinel {
        constexpr bool operator==(const ranges::iterator_t<V>& it) const noexcept {
            return *it == '?' || *it == '\0';
        }
    };

public:
    constexpr explicit question_view(V base)
        : m_base(std::move(base)) { }
    
    constexpr auto begin() const {
        return ranges::begin(m_base);
    }

    constexpr auto end() const noexcept {
        return sentinel{};
    }

private:
    V m_base;
};

template<typename R>
question_view(R&&) -> question_view<views::all_t<R>>;

int main() {
    string str = "qwerty?uiopasdfghjklzxcvbnm";
    auto v = question_view{str};
    static_assert(ranges::view<decltype(v)>);
    ranges::copy(v, ostreambuf_iterator<char>{cout});
    cout << '\n';
}

• Expected behavior: This code should compile (compiler explorer).
• Expected output: qwerty

Conversions from ranges to containers do not work

#include <algorithm>
#include <forward_list>
#include <iostream>
#include <ranges>
#include <string>

using namespace std;

template<ranges::view V>
    requires ranges::input_range<V>
class question_view : public ranges::view_interface<question_view<V>> {
private:
    struct sentinel {
        constexpr bool operator==(const ranges::iterator_t<V>& it) const noexcept {
            return *it == '?' || *it == '\0';
        }
    };

public:
    constexpr explicit question_view(V base)
        : m_base(std::move(base)) { }
    
    constexpr auto begin() const {
        return ranges::begin(m_base);
    }

    constexpr auto end() const noexcept {
        return sentinel{};
    }

private:
    V m_base;
};

template<typename R>
question_view(R&&) -> question_view<views::all_t<R>>;

int main() {
    auto str = "qwerty?uiopasdfghjklzxcvbnm"s;
    (void) (question_view{str} | ranges::to<forward_list>());
}

Expected behavior: This code should compile (assuming #2806 was merged).

Summary

1. Some algorithms (possibly all of them) don't work with custom sentinels and unwrappable iterators. I've tested:
   • ranges::all_of, ranges::any_of, ranges::none_of,
   • ranges::copy,
   • ranges::sort.
2. Some functions from <iterator> header don't work too (e.g. ranges::distance),
3. Same thing applies to range constructors (and possibly other operations) from P1206R7 Conversions From Ranges To Containers #2806.

[frederick-vs-ja]

I think this has been reported as #2591.

[CaseyCarter]

I think this has been reported as #2591.

Yes, although it's far from obvious: this is a good description of the general issue, whereas #2591 is a particular occurrence. I'll keep this around for now and link it up to the meta-issue.

[strega-nil-ms]

Working on this in #3024

[JMazurkiewicz]

I think that this and #2591 are not bugs anymore (thanks to #3024).

[strega-nil-ms]

Fixed by #3024 (you're right, thanks @JMazurkiewicz!)