std::vector creation from immer::map/set iterator pair fails starting at gcc 14.3

[TheCoconutChef]

The following fails to compile starting from gcc 14.3 (godbolt link):

#include <immer/map.hpp>
#include <unordered_map>
#include <vector>

int main()
{
    auto um = std::unordered_map<int,int>{ {0,0}, {1,1}, {2,2} };
    auto uv = std::vector<std::pair<int,int>>(um.begin(), um.end());
    static_assert(!std::sized_sentinel_for<decltype(um.end()), decltype(um.begin())>);

    auto im = immer::map<int,int>{ {0,0}, {1,1}, {2,2} };
    auto iv = std::vector<std::pair<int,int>>(im.begin(), im.end());
    static_assert(std::sized_sentinel_for<decltype(im.end()), decltype(im.begin())>);

    return 0; 
}

with the following:

/opt/compiler-explorer/gcc-14.3.0/include/c++/14.3.0/bits/ranges_base.h:961:23:   required from 'constexpr std::iter_difference_t<typename std::decay<_Tp>::type> std::ranges::__distance_fn::operator()(_It&&, _Sent) const [with _It = immer::detail::hamts::champ_iterator<std::pair<int, int>, immer::map<int, int>::hash_key, immer::map<int, int>::equal_key, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy, immer::spinlock_policy>, 5>&; _Sent = immer::detail::hamts::champ_iterator<std::pair<int, int>, immer::map<int, int>::hash_key, immer::map<int, int>::equal_key, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy, immer::spinlock_policy>, 5>; std::iter_difference_t<typename std::decay<_Tp>::type> = long int; typename std::decay<_Tp>::type = immer::detail::hamts::champ_iterator<std::pair<int, int>, immer::map<int, int>::hash_key, immer::map<int, int>::equal_key, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy, immer::spinlock_policy>, 5>]'
  961 |       { return __last - static_cast<const decay_t<_It>&>(__first); }
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/gcc-14.3.0/include/c++/14.3.0/bits/stl_vector.h:718:44:   required from 'constexpr std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with _InputIterator = immer::detail::hamts::champ_iterator<std::pair<int, int>, immer::map<int, int>::hash_key, immer::map<int, int>::equal_key, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy, immer::spinlock_policy>, 5>; <template-parameter-2-2> = void; _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; allocator_type = std::allocator<std::pair<int, int> >]'
  718 |                 = static_cast<size_type>(ranges::distance(__first, __last));
      |                                          ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
<source>:12:67:   required from here
   12 |     auto iv = std::vector<std::pair<int,int>>(im.begin(), im.end());
      |                                                                   ^
/opt/compiler-explorer/libs/immer/trunk/immer/detail/iterator_facade.hpp:172:23: error: static assertion failed
  172 |         static_assert(is_random_access, "");

but the equivalent code for a std::unordered_map works.

The problem might be that immer::map/set have iterator pairs for which std::sized_sentinel_for is satisfied. This then causes the wrong implementation of std::ranges::distance to be selected at compile time.

Note that both the iterators for std::unordered_map and immer::map are forward_iterator.

This is likely to affect many std::ranges::* function. For instance std::ranges::copy(im, iv) also fails to compile for the same reason.

[arximboldi]

Thank you for noting this!

[TheCoconutChef]

I've found two possible solutions for this.

One is to modify iterator_facade.hpp such that all method / functions that use static_assert as "compile guard" are modified in order to use SFINAE, like so:

    template <typename U = iterator_facade,
              typename std::enable_if_t<U::is_random_access, bool> = true>
    friend DifferenceTypeT operator-(const DerivedT& a, const DerivedT& b)
    {
        return access_t::distance_to(b, a);
    }

Another solution would be to define std::disable_sized_sentinel_for conditioned on the proper C++ standard, adding the definition in champ_iterator.hpp, like so:

// IMMER_HAS_CPP20 defined as IMMER_HAS_CPP17 in config.hpp
#if IMMER_HAS_CPP20
namespace std {
template <typename T,
          typename Hash,
          typename Eq,
          typename MP,
          immer::detail::hamts::bits_t B>
inline constexpr bool disable_sized_sentinel_for<
    immer::detail::hamts::champ_iterator<T, Hash, Eq, MP, B>,
    immer::detail::hamts::champ_iterator<T, Hash, Eq, MP, B>> = true;
} // namespace std
#endif

See it work on godbolt.

Do you have a preference for either?

Edit: note that the doc states:

The disable_sized_sentinel_for variable template can be used to prevent iterators and sentinels that can be subtracted but do not actually model sized_sentinel_for from satisfying the concept.

which doesn't strike me as applicable for champ_iterator, as they can't be subtracted.

[arximboldi]

Thank you for investigating and resolving this!