[Bug libstdc++/114316] New: assert failure with _GLIBCXX_DEBUG and empty range of singular iterators passed std:: algorithm

[Bug libstdc++/114316] New: assert failure with _GLIBCXX_DEBUG and empty range of singular iterators passed std:: algorithm

[ammiera at hotmail dot com]

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

            Bug ID: 114316
           Summary: assert failure with _GLIBCXX_DEBUG and empty range of
                    singular iterators passed std:: algorithm
           Product: gcc
           Version: 12.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ammiera at hotmail dot com
  Target Milestone: ---

Compiling the attached snippet with -D_GLIBCXX_DEBUG causes an assert to fire:

#include <map>
#include <algorithm>
#include <iterator>

int main()
{
    std::multimap<char, int>::iterator it1{};
    std::multimap<char, int>::iterator it2{};

    (void) (it1==it2); // OK
    (void) std::find_if(
        it1, it2, [](const auto& el) { return el.second == 8;});
}

The runtime error:

In function:
    constexpr _IIter std::find_if(_IIter, _IIter, _Predicate) [with _IIter = 
    gnu_debug::_Safe_iterator<_Rb_tree_iterator<pair<const char, int> >, 
    debug::multimap<char, int>, bidirectional_iterator_tag>; _Predicate = 
    main()::<lambda(const auto:16&)>]

Error: function requires a valid iterator range [first, last).

Objects involved in the operation:
    iterator "first" @ 0x7ffc275311a0 {
      type = std::_Rb_tree_iterator<std::pair<char const, int> > (mutable
iterator);
      state = singular;
    }
    iterator "last" @ 0x7ffc275311d0 {
      type = std::_Rb_tree_iterator<std::pair<char const, int> > (mutable
iterator);
      state = singular;
    }
Program terminated with signal: SIGSEGV

https://godbolt.org/z/e8xa5Eoqn

Tested with C++17 and C++20 mode.

Initially discussed on the mailing list:
https://gcc.gnu.org/pipermail/libstdc++/2024-March/058461.html

[Bug libstdc++/114316] assert failure with _GLIBCXX_DEBUG and empty range of singular iterators passed to std:: algorithm

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2024-03-12
     Ever confirmed|0                           |1

[Bug libstdc++/114316] assert failure with _GLIBCXX_DEBUG and empty range of singular iterators passed to std:: algorithm

[redi at gcc dot gnu.org]

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

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
For a debug mode _Safe_iterator pair __valid_range uses this overload:

  template<typename _Iterator, typename _Sequence, typename _Category>
    inline bool
    __valid_range(const _Safe_iterator<_Iterator, _Sequence,
                                       _Category>& __first,
                  const _Safe_iterator<_Iterator, _Sequence,
                                       _Category>& __last)
    {
      typename _Distance_traits<_Iterator>::__type __dist;
      return __first._M_valid_range(__last, __dist);
    }


Which calls:

  template<typename _Iterator, typename _Sequence, typename _Category>
    bool
    _Safe_iterator<_Iterator, _Sequence, _Category>::
    _M_valid_range(const _Safe_iterator& __rhs,
                   std::pair<difference_type, _Distance_precision>& __dist,
                   bool __check_dereferenceable) const
    {
      if (_M_singular() || __rhs._M_singular() || !_M_can_compare(__rhs))
        return false;

So it doesn't consider whether the range is empty.

For non-debug mode iterators we have:

  template<typename _InputIterator>
    _GLIBCXX_CONSTEXPR
    inline bool
    __valid_range_aux(_InputIterator __first, _InputIterator __last,
                      std::input_iterator_tag)
    {
      return __first == __last
        || (!__gnu_debug::__check_singular(__first)
              && !__gnu_debug::__check_singular(__last));
    }

which gets it right.

[Bug libstdc++/114316] assert failure with _GLIBCXX_DEBUG and empty range of singular iterators passed to std:: algorithm

[cvs-commit at gcc dot gnu.org]

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

--- Comment #2 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Francois Dumont <fdumont@gcc.gnu.org>:

https://gcc.gnu.org/g:07fad7a7fc245369989e9ca746728ea78b924715

commit r14-9507-g07fad7a7fc245369989e9ca746728ea78b924715
Author: François Dumont <fdumont@gcc.gnu.org>
Date:   Thu Mar 14 22:13:57 2024 +0100

    libstdc++: Implement N3644 on _Safe_iterator<> [PR114316]

    Consider range of value-initialized iterators as valid and empty.

    libstdc++-v3/ChangeLog:

            PR libstdc++/114316
            * include/debug/safe_iterator.tcc
(_Safe_iterator<>::_M_valid_range):
            First check if both iterators are value-initialized before checking
if
            singular.
            * testsuite/23_containers/set/debug/114316.cc: New test case.
            * testsuite/23_containers/vector/debug/114316.cc: New test case.

[Bug libstdc++/114316] assert failure with _GLIBCXX_DEBUG and empty range of singular iterators passed to std:: algorithm

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Francois Dumont
<fdumont@gcc.gnu.org>:

https://gcc.gnu.org/g:c1f57ff40738bbce9902ea25865ed6d729b10127

commit r13-8460-gc1f57ff40738bbce9902ea25865ed6d729b10127
Author: François Dumont <fdumont@gcc.gnu.org>
Date:   Thu Mar 14 22:13:57 2024 +0100

    libstdc++: Implement N3644 on _Safe_iterator<> [PR114316]

    Consider range of value-initialized iterators as valid and empty.

    libstdc++-v3/ChangeLog:

            PR libstdc++/114316
            * include/debug/safe_iterator.tcc
(_Safe_iterator<>::_M_valid_range):
            First check if both iterators are value-initialized before checking
if
            singular.
            * testsuite/23_containers/set/debug/114316.cc: New test case.
            * testsuite/23_containers/vector/debug/114316.cc: New test case.

    (cherry picked from commit 07fad7a7fc245369989e9ca746728ea78b924715)

[Bug libstdc++/114316] assert failure with _GLIBCXX_DEBUG and empty range of singular iterators passed to std:: algorithm

[fdumont at gcc dot gnu.org]

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

François Dumont <fdumont at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED
   Target Milestone|---                         |14.0

--- Comment #4 from François Dumont <fdumont at gcc dot gnu.org> ---
Similar issues with N3344 also fixed and back-ported to GCC 13.

[Bug libstdc++/114316] assert failure with _GLIBCXX_DEBUG and empty range of singular iterators passed to std:: algorithm

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|14.0                        |13.3