STL: `expected<any, T>` and its friends can break container iterator comparison

[frederick-vs-ja]

Describe the bug

The bug reported in GCC Bugzilla #115939 is currently also present in MSVC STL. Iterator comparison is currently broken for all but set containers.

The reason of the bug is that expected<any, T> is so permissive on implicit conversion that operator== for expected can cause ambiguity. Note that while there may be a defect in expected, such ambiguity can also caused by some (misdesigned) user-defined types in C++14 mode.

Command-line test case

Godbolt link

#include <any>
#include <expected>

#include <vector>
#include <forward_list>
#include <deque>
#include <list>
#include <array>
#include <map>
// #include <set> // possibly fine
#include <unordered_map>
// #include <unordered_set> // possibly fine

int main()
{
    {
        std::array<std::expected<std::any, char>, 1> cont{};
        (void)(cont.begin() == cont.end());
    }
    {
        std::vector<std::expected<std::any, char>> cont;
        (void)(cont.begin() == cont.end());
    }
    {
        std::forward_list<std::expected<std::any, char>> cont;
        (void)(cont.begin() == cont.end());
    }
    {
        std::list<std::expected<std::any, char>> cont;
        (void)(cont.begin() == cont.end());
    }
    {
        std::deque<std::expected<std::any, char>> cont;
        (void)(cont.begin() == cont.end());
    }

    {
        std::map<int, std::expected<std::any, char>> cont;
        (void)(cont.begin() == cont.end());
    }
    {
        std::multimap<int, std::expected<std::any, char>> cont;
        (void)(cont.begin() == cont.end());
    }
    {
        std::unordered_map<int, std::expected<std::any, char>> cont;
        (void)(cont.begin() == cont.end());
    }
    {
        std::unordered_multimap<int, std::expected<std::any, char>> cont;
        (void)(cont.begin() == cont.end());
    }
}

Expected behavior

This program compiles and operator== overloads for iterators are selected.

STL version

Microsoft Visual Studio Community 2022 Version 17.11.0 Preview ? (14.41.33923 from Godbolt)

Still present in 17.11.0 Preview 4.0 and ecbc1efa09936f4ef5af529e770a95a29a4290d3.

Additional context

[frederick-vs-ja]

I'm working on fixing this.

BTW, I guess we should change all container iterators to something like _Meow_provider<_Args...>::_Iterator and provide comparison operators as hidden friends in vNext, which will be more ADL-proof and avoid most undesired implicit conversions.

[frederick-vs-ja]

This program shows that all standard library implementations are currently buggy. Godbolt link.

#include <cstddef>
#include <vector>
#include <array>
#include <deque>

struct any_convertible_subtractable {
    any_convertible_subtractable() = default;

    template<class T>
    any_convertible_subtractable(T&&) {}

    template<class T>
    friend std::ptrdiff_t operator-(any_convertible_subtractable, T&&)
    {
        return 0;
    }

    template<class T>
    friend std::ptrdiff_t operator-(T&&, any_convertible_subtractable)
    {
        return 0;
    }
};

template<class Cont>
void test_container(Cont&& c)
{
    (void)(c.end() - c.begin());
}

int main()
{
    test_container(std::vector<any_convertible_subtractable>{});
    test_container(std::array<any_convertible_subtractable, 1>{});
    test_container(std::deque<any_convertible_subtractable>{});
}

Edit: NOT SURE whether the issue with forwarding references can be fixed.

[kamrann]

I just found my way here after a day banging my head against the table/reproducing cut-down versions of STL concept checks, trying to comprehend why MSVC was telling me my vector wasn't a range. I see that an attempted fix was rejected (#4860), and I can understand the risks, but is there even a suggested way to work around this @StephanTLavavej?

It would seem very unfortunate (not to mention unexpected!) for there to be such an arbitrary exclusion of certain types from being usable with STL containers. Regarding your comment in the linked PR, I can say that for sure usage of std::expected<std::any> will most definitely not become common if people are faced with the kind of error messages I've been digging through when they attempt to use it. But std::expected and std::any are both fairly straightforward, well-behaved value types and I think it's super unintuitive that this combination would not be permitted. FWIW I hit the error using std::vector<std::expected<something_else, err>> where something_else was an any-like type but in no way pathological.

I'm also a little curious as to why optional<any> doesn't suffer from the same issue despite providing a similar equality comparison to the contained type; perhaps there is a potential fix to be found somewhere in there?

[StephanTLavavej]

is there even a suggested way to work around this

If you have a wrapper struct where the expected is a data member, that should insulate the vector from any wacky conversions.

I'm also a little curious as to why optional<any> doesn't suffer from the same issue

Yeah, that's a good question, it's not obvious to me from a brief glance. Someone (possibly me, later; busy now) should figure out the root cause of the difference, and then it might be possible to raise an LWG issue.

[kamrann]

If you have a wrapper struct where the expected is a data member, that should insulate the vector from any wacky conversions.

Thank you!

I've tagged the point in my code so if at any point you could use some more info or want an additional test case, feel free to ping me here.

[CaseyCarter]

Bit of a hack that fixes only expected<any> iterators - and not an entire class of such problems. Tell expected<any> that it is equal to nothing:

 template <class _Uty>
+    requires (!same_as<any, _Ty>)
 _NODISCARD friend constexpr bool operator==(const expected& _Left, const _Uty& _Right) noexcept(
     noexcept(static_cast<bool>(_Left._Value == _Right))) /* strengthened */ {

This may be "good enough" to tide us over until we can completely rework our iterators to avoid having T be an associated type of container<T>::iterator.

The problem is that e.g. forward_list<expected<any>>::iterator has expected<any> as an associated type, and iterator == iterator is implemented by an operator for a base class. Overload resolution for iterator == iterator finds this operator== for expected. Such an iterator is convertible to expected<any> (most things are) so this overload is viable. Its first argument requires a user-defined conversion from the iterator, but the second is an exact match. The intended overload requires a derived-to-base conversion for both arguments, which is better then the other overload's user-defined conversion for its first argument, but worse than the exact match for the second. Neither overload is better (not worse for all arguments) so we have ambiguity.

Note that we can't simply constrain this operator== to require static_cast<bool>(_Value == _Right) be well-formed, because that expression is any == iterator-associated-with-expected<any> for which this same overload is viable. Textbook constraint recursion. This is the crux of why expected<any> is kryptonite: it's omniconvertible, and it unwraps into something omniconvertible. The Standard Library's practice of writing constrained cross-type operators for wrapper<T> and U that require the operation to be valid for T and U doesn't work in the presence of omniconvertible-wrapping-omniconvertible.

EDIT: "For which this same overload is viable" in the above seems questionable. We were looking at expected<any>::operator==<iterator-associated-with-expected<any>>. Constraining would want to check any == iterator-associated-with-expected<any> which should find expected<any>::operator==<any> - a different specialization of the same operator== template. That specialization wants to check the new-and-different constraint any == any which I think fails cleanly. expected<any> isn't an associated class of any, so we can't find our way back to expected<any>::operator==. I'm either missing something or compiler checks for constraint recursion are more simplistic than expected (pun intended). MSVC seems to agree with me that the naive constraint should work (https://godbolt.org/z/ToGEzj73P), but clang and GCC do not.

[kamrann]

Interesting. I guess this is just predicated on the knowledge that std::any isn't equality comparable anyway so there's (I guess) no harm in just removing the overload for expected<any>?

Seems like a nightmare generally though, I really wonder why std::expected was made so widely implicitly convertible to. Presumably just for ergonomics, but in my experience this kind of painful corner case inevitably comes up somewhere when you allow more than one level of convertibility, so it kind of surprises me.

[CaseyCarter]

Interesting. I guess this is just predicated on the knowledge that std::any isn't equality comparable anyway so there's (I guess) no harm in just removing the overload for expected<any>?

It's still a bit iffy since a user could (please don't) create a type that defines equality with any which should then be comparable with expected<any>.

Seems like a nightmare generally though, I really wonder why std::expected was made so widely implicitly convertible to.

WG21 really wanted expected to be like optional, despite that type's many failings. I observe that if the template converting constructor of either any or expected is made unconditionally explicit (the expected<T>(U) constructor is explicit only when U isn't implicitly convertible to T) this becomes a non-issue.

[CaseyCarter]

For posterity, my reduced repro:

struct any {
    template <class U> any(U&&);
};

template <class T> struct expected {
    template <class U> expected(U&&);

    template <class U>
        requires requires(const T& t, const U& u) { t == u; } // line 9
    friend bool operator==(const expected&, const U&) { return true; }
};

template <class> struct const_iterator {
    bool operator==(const const_iterator&) const = default;
};

template <class T> struct iterator : const_iterator<T> {};

int main() {
    using I = iterator<expected<any>>;
    return I{} == I{};
}

MSVC is happy with the workaround constraint I've added on line 9. Clang and GCC say the program has constraint recursion (https://godbolt.org/z/PMh4rdbYe). I (and apparently MSVC) believe that I{} == I{} finds expected<any>::operator==<I>, which requires any{} == I{}, which finds expected<any>::operator==<any>, which requires any{} == any{}, which is ill-formed. I'm wary of submitting an issue to LWG with a PR that won't solve our problem, so I've sent feelers out to some C++ experts for comment and I'll submit bug reports if I don't learn anything more.