[Bug libstdc++/115939] New: Cannot unambiguously compare iterators in std::unordered_map with mapped type std::expected<std::any, Y>>

[Bug libstdc++/115939] New: Cannot unambiguously compare iterators in std::unordered_map with mapped type std::expected<std::any, Y>>

[halfflat at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115939

            Bug ID: 115939
           Summary: Cannot unambiguously compare iterators in
                    std::unordered_map with mapped type
                    std::expected<std::any, Y>>
           Product: gcc
           Version: 14.1.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: halfflat at gmail dot com
  Target Milestone: ---

Created attachment 58667
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58667&action=edit
Preprocessed .ii file from example code

Consider the following code:


#include <any>
#include <expected>
#include <unordered_map>

struct Y {};
std::unordered_map<int, std::expected<std::any, Y>> m;
bool r = m.begin()==m.end();


When compiled with g++ -c -std=c++23 -pedantic we get an "ambiguous overload
for ‘operator==’" error. This issue has been replicated on Compiler Explorer
(https://godbolt.org/z/cqoedqKbr). It is not clear to me if this results from a
fundamental issue in the standard library specification or is a consequence of
the implementation in libstdc++.

The original context of the bug was in code that was attempting to use a
std::unordered_map<std::type_index, std::function<std::expected<std::any,
failure> (std::string_view)>> (where failure was a separately defined type). 

Compiler output below:

% g++ -v -save-temps  -c -std=c++23 -pedantic bug.cc
Using built-in specs.
COLLECT_GCC=g++
Target: x86_64-pc-linux-gnu
Configured with: /build/gcc/src/gcc/configure
--enable-languages=ada,c,c++,d,fortran,go,lto,m2,objc,obj-c++,rust
--enable-bootstrap --prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib
--mandir=/usr/share/man --infodir=/usr/share/info
--with-bugurl=https://gitea.artixlinux.org/packages/gcc/issues
--with-build-config=bootstrap-lto --with-linker-hash-style=gnu
--with-system-zlib --enable-__cxa_atexit --enable-cet=auto
--enable-checking=release --enable-clocale=gnu --enable-default-pie
--enable-default-ssp --enable-gnu-indirect-function --enable-gnu-unique-object
--enable-libstdcxx-backtrace --enable-link-serialization=1
--enable-linker-build-id --enable-lto --enable-multilib --enable-plugin
--enable-shared --enable-threads=posix --disable-libssp --disable-libstdcxx-pch
--disable-werror
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 14.1.1 20240507 (GCC) 
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-c' '-std=c++23' '-Wpedantic'
'-shared-libgcc' '-mtune=generic' '-march=x86-64'
 /usr/lib/gcc/x86_64-pc-linux-gnu/14.1.1/cc1plus -E -quiet -v -D_GNU_SOURCE
bug.cc -mtune=generic -march=x86-64 -std=c++23 -Wpedantic -fpch-preprocess -o
bug.ii
ignoring nonexistent directory
"/usr/lib/gcc/x86_64-pc-linux-gnu/14.1.1/../../../../x86_64-pc-linux-gnu/include"
ignoring nonexistent directory "/home/sam/pkg/include"
#include "..." search starts here:
#include <...> search starts here:
 /usr/lib/gcc/x86_64-pc-linux-gnu/14.1.1/../../../../include/c++/14.1.1

/usr/lib/gcc/x86_64-pc-linux-gnu/14.1.1/../../../../include/c++/14.1.1/x86_64-pc-linux-gnu

/usr/lib/gcc/x86_64-pc-linux-gnu/14.1.1/../../../../include/c++/14.1.1/backward
 /usr/lib/gcc/x86_64-pc-linux-gnu/14.1.1/include
 /usr/local/include
 /usr/lib/gcc/x86_64-pc-linux-gnu/14.1.1/include-fixed
 /usr/include
End of search list.
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-c' '-std=c++23' '-Wpedantic'
'-shared-libgcc' '-mtune=generic' '-march=x86-64'
 /usr/lib/gcc/x86_64-pc-linux-gnu/14.1.1/cc1plus -fpreprocessed bug.ii -quiet
-dumpbase bug.cc -dumpbase-ext .cc -mtune=generic -march=x86-64 -Wpedantic
-std=c++23 -version -o bug.s
GNU C++23 (GCC) version 14.1.1 20240507 (x86_64-pc-linux-gnu)
        compiled by GNU C version 14.1.1 20240507, GMP version 6.3.0, MPFR
version 4.2.1, MPC version 1.3.1, isl version isl-0.26-GMP

GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
Compiler executable checksum: 79593118236b8aa0b562fa91bdea97d6
bug.cc:7:19: error: ambiguous overload for ‘operator==’ (operand types are
‘std::unordered_map<int, std::expected<std::any, Y> >::iterator’ {aka
‘std::__detail::_Insert_base<int, std::pair<const int, std::expected<std::any,
Y> >, std::allocator<std::pair<const int, std::expected<std::any, Y> > >,
std::__detail::_Select1st, std::equal_to<int>, std::hash<int>,
std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash,
std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false,
false, true> >::iterator’} and ‘std::unordered_map<int, std::expected<std::any,
Y> >::iterator’ {aka ‘std::__detail::_Insert_base<int, std::pair<const int,
std::expected<std::any, Y> >, std::allocator<std::pair<const int,
std::expected<std::any, Y> > >, std::__detail::_Select1st, std::equal_to<int>,
std::hash<int>, std::__detail::_Mod_range_hashing,
std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy,
std::__detail::_Hashtable_traits<false, false, true> >::iterator’})
    7 | bool r = m.begin()==m.end();
      |          ~~~~~~~~~^~~~~~~~~
      |                 |        |
      |                 |        _Node_iterator<[...],[...],[...]>
      |                 _Node_iterator<[...],[...],[...]>
In file included from bug.cc:2:
/usr/include/c++/14.1.1/expected:1133:9: note: candidate: ‘constexpr bool
std::operator==(const expected<_Tp, _Er>&, const _Up&) [with _Up =
__detail::_Node_iterator<pair<const int, expected<any, Y> >, false, false>; _Tp
= any; _Er = Y]’ (reversed)
 1133 |         operator==(const expected& __x, const _Up& __v)
      |         ^~~~~~~~
In file included from /usr/include/c++/14.1.1/bits/hashtable.h:35,
                 from /usr/include/c++/14.1.1/bits/unordered_map.h:33,
                 from /usr/include/c++/14.1.1/unordered_map:41,
                 from bug.cc:3:
/usr/include/c++/14.1.1/bits/hashtable_policy.h:407:7: note: candidate: ‘bool
std::__detail::operator==(const _Node_iterator_base<std::pair<const int,
std::expected<std::any, Y> >, false>&, const
_Node_iterator_base<std::pair<const int, std::expected<std::any, Y> >,
false>&)’
  407 |       operator==(const _Node_iterator_base& __x, const
_Node_iterator_base& __y)
      |       ^~~~~~~~

[Bug libstdc++/115939] Cannot unambiguously compare iterators in std::unordered_map with mapped type std::expected<std::any, Y>>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115939

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2024-07-15
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I think this is the expected (no pun intended) behaviour. It's a consequence of
std::any being constructible from anything, so the operator== for expected<T,E>
is a candidate for ... well ... anything. Your std::expected<std::any, Y> can
be constructed from nearly every possible type, so the equality comparison
considers a conversion to std::expected<std::any, Y> to be viable, and then use
the operator== for std::expected.

It doesn't help that the operator== is a hidden friend, so only found by ADL,
because your unordered_map::iterator has std::expected<std::any,Y> as an
associated class, so the hidden friend is a candidate.

The way libstdc++ defines the equality operator for unordered_map::iterator
also involves conversions, from unordered_map::iterator to its
_Node_iterator_base base class, so the C++ standard considers them ambiguous.
Without -pedantic GCC does the right thing.

I see two possible solutions to this, but neither of them is possible for you.

Firstly, I have a C++ standard proposal to constrain operator==(expected<T,E>,
U), so that it will not be viable if std::expected<T,E> is not equality
comparable with U (which ti isn't in this case, because U is the
unordered_map::iterator).

Secondly, we could add operator== for the actual iterator type, so that there's
no derived-to-base conversion needed to find a candidate.

I think the only workarounds available to you are to not use -pedantic, and to
not use std::any in this way, where it greedily converts from anything.

[Bug libstdc++/115939] Cannot unambiguously compare iterators in std::unordered_map with mapped type std::expected<std::any, Y>>

[halfflat at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115939

--- Comment #2 from Sam Yates <halfflat at gmail dot com> ---
Thank you for the prompt assessment! A standards proposal or DR does seem like
the more robust solution for the longer term.

In the interim, for my application, I am boxing-up the std::any in another
struct [1] and unboxing as required; this breaks the chain of implicit
conversions. Ultimately this code will need to be buildable in C++20 and I will
use a back-ported std::expected workalike which can implement your proposed
restriction on operator==.


[1] This, basically:
template <typename T>
struct box {
    template <typename... Ts>
    explicit box(Ts&&... ts): value(std::forward<Ts>(ts)...) {}
    T value;
};

[Bug libstdc++/115939] Cannot unambiguously compare iterators in std::unordered_map with mapped type std::expected<std::any, Y>>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115939

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Created attachment 58668
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58668&action=edit
Add operator== overloads for hash table iterators

(In reply to Jonathan Wakely from comment #1)
> Secondly, we could add operator== for the actual iterator type, so that
> there's no derived-to-base conversion needed to find a candidate.

This patch implements this change. The new operator== overloads are exact
matches, so no derived-to-base or user-defined conversions are required.

I'll get to work on the std::expected proposal (which I expect will get treated
as a DR for C++23 by all implementers, certainly in libstdc++). Once I've
drafted that proposal, I'll push the corresponding code changes to libstdc++.

N.B. this slightly modified example shows why the patch needs so many new
overloads:

#include <any>
#include <expected>
#include <unordered_map>

struct Y {};
std::unordered_map<int, std::expected<std::any, Y>> m;
bool r = m.begin()==m.cend();

Using m.cend() means we need overloads for comparing iterator to const_iterator
(which is why the comparisons were defined on the base class in the first
place, since they only need to be done once and they work for both iterator and
const_iterator ... unless there is some other candidate that's viable).

[Bug libstdc++/115939] Cannot unambiguously compare iterators in std::unordered_map with mapped type std::expected<std::any, Y>>

[de34 at live dot cn]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115939

Jiang An <de34 at live dot cn> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |de34 at live dot cn

--- Comment #4 from Jiang An <de34 at live dot cn> ---
(In reply to Jonathan Wakely from comment #3)

> I'll get to work on the std::expected proposal (which I expect will get
> treated as a DR for C++23 by all implementers, certainly in libstdc++). Once
> I've drafted that proposal, I'll push the corresponding code changes to
> libstdc++.

It seems to me that it's still needed to fix operator== for container iterators
after patching std::expected. IIUC the current standard wording doesn't allow
such iterator comparison to be hacked.

[Bug libstdc++/115939] Cannot unambiguously compare iterators in std::unordered_map with mapped type std::expected<std::any, Y>>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115939

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Agreed, that's what the patch in comment 3 is for, and that's why I implemented
that before working on the std::expected changes.

[Bug libstdc++/115939] Cannot unambiguously compare iterators in std::unordered_map with mapped type std::expected<std::any, Y>>

[de34 at live dot cn]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115939

--- Comment #6 from Jiang An <de34 at live dot cn> ---
I found that we may also need to add some operator- overloads
(https://godbolt.org/z/jTTcYhxMc).

All standard library implementations are currently broken.


```
#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>{});
}

```

[Bug libstdc++/115939] Cannot unambiguously compare iterators in std::unordered_map with mapped type std::expected<std::any, Y>>

[de34 at live dot cn]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115939

--- Comment #7 from Jiang An <de34 at live dot cn> ---
(In reply to Jiang An from comment #6)
> I found that we may also need to add some operator- overloads
> (https://godbolt.org/z/jTTcYhxMc).
> 
> All standard library implementations are currently broken.

Oops, it's extremely difficult (if possible) to defend against forwarding
references. libstdc++ seems to be fine for const T& now.

[Bug libstdc++/115939] Cannot unambiguously compare iterators in std::unordered_map with mapped type std::expected<std::any, Y>>

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115939

--- Comment #8 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:591b71993f15ed95eb38f3314f3d9ac159b9d051

commit r15-3130-g591b71993f15ed95eb38f3314f3d9ac159b9d051
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Jul 16 09:43:06 2024 +0100

    libstdc++: Define operator== for hash table iterators [PR115939]

    Currently iterators for unordered containers do not directly define
    operator== and operator!= overloads. Instead they rely on the base class
    defining them, which is done so that iterator and const_iterator
    comparisons work using the same overloads.

    However this means a derived-to-base conversion is needed to call those
    operators, and PR libstdc++/115939 shows that this can be ambiguous (for
    -pedantic) when another overloaded operator could be used after an
    implicit conversion.

    This change defines operator== and operator!= directly for
    _Node_iterator and _Node_const_iterator so that no derived-to-base
    conversions are needed. The new overloads just forward to the base class
    ones, so the implementation is still shared and doesn't need to be
    duplicated.

    libstdc++-v3/ChangeLog:

            PR libstdc++/115939
            * include/bits/hashtable_policy.h (_Node_iterator): Add
            operator== and operator!=.
            (_Node_const_iterator): Likewise.
            * testsuite/23_containers/unordered_map/115939.cc: New test.

[Bug libstdc++/115939] Cannot unambiguously compare iterators in std::unordered_map with mapped type std::expected<std::any, Y>>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115939

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed on trunk so far.