[Bug libstdc++/85828] std::shuffle tries to swap element with itself

[Bug libstdc++/85828] std::shuffle tries to swap element with itself

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 from CVS 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:c2fb0a1a2e7a0fb15cf3cf876f621902ccd273f0

commit r11-2677-gc2fb0a1a2e7a0fb15cf3cf876f621902ccd273f0
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Aug 12 20:36:00 2020 +0100

    libstdc++: Make self-move well-defined for containers [PR 85828]

    The C++ LWG recently confirmed that self-move assignment should not have
    undefined behaviour for standard containers (see the proposed resolution
    of LWG 2839). The result should be a valid but unspecified value, just
    like other times when a container is moved from.

    Our std::list, std::__cxx11::basic_string and unordered containers all
    have bugs which result in undefined behaviour.

    For std::list the problem is that we clear the previous contents using
    _M_clear() instead of clear(). This means the _M_next, _M_prev and
    _M_size members are not zeroed, and so after we "update" them (with
    their existing values), we are left with dangling pointers and a
    non-zero size, but no elements.

    For the unordered containers the problem is similar. _Hashtable first
    deallocates the existing contents, then takes ownership of the pointers
    from the RHS object (which has just had its contents deallocated so the
    pointers are dangling).

    For std::basic_string it's a little more subtle. When the string is
    local (i.e. fits in the SSO buffer) we use char_traits::copy to copy the
    contents from this->data() to __rhs.data(). When &__rhs == this that
    copy violates the precondition that the ranges don't overlap. We only
    need to check for self-move for this case where it's local, because the
    only other case that can be true for self-move is that it's non-local
    but the allocators compare equal. In that case the data pointer is
    neither deallocated nor leaked, so the result is well-defined.

    This patch also makes a small optimization for std::deque move
    assignment, to use the efficient move when is_always_equal is false, but
    the allocators compare equal at runtime.

    Finally, we need to remove all the Debug Mode checks which abort the
    program when a self-move is detected, because it's not undefined to do
    that.

    Before PR 85828 can be closed we should also look into fixing
    std::shuffle so it doesn't do any redundant self-swaps.

    libstdc++-v3/ChangeLog:

            PR libstdc++/85828
            * include/bits/basic_string.h (operator=(basic_string&&)): Check
            for self-move before copying with char_traits::copy.
            * include/bits/hashtable.h (operator=(_Hashtable&&)): Check for
            self-move.
            * include/bits/stl_deque.h (_M_move_assign1(deque&&, false_type)):
            Check for equal allocators.
            * include/bits/stl_list.h (_M_move_assign(list&&, true_type)):
            Call clear() instead of _M_clear().
            * include/debug/formatter.h (__msg_self_move_assign): Change
            comment.
            * include/debug/macros.h (__glibcxx_check_self_move_assign):
            (_GLIBCXX_DEBUG_VERIFY): Remove.
            * include/debug/safe_container.h (operator=(_Safe_container&&)):
            Remove assertion check for safe move and make it well-defined.
            * include/debug/safe_iterator.h (operator=(_Safe_iterator&&)):
            Remove assertion check for self-move.
            * include/debug/safe_local_iterator.h
            (operator=(_Safe_local_iterator&&)): Likewise.
            * testsuite/21_strings/basic_string/cons/char/self_move.cc: New
test.
            * testsuite/23_containers/deque/cons/self_move.cc: New test.
            * testsuite/23_containers/forward_list/cons/self_move.cc: New test.
            * testsuite/23_containers/list/cons/self_move.cc: New test.
            * testsuite/23_containers/set/cons/self_move.cc: New test.
            * testsuite/23_containers/unordered_set/cons/self_move.cc: New
test.
            * testsuite/23_containers/vector/cons/self_move.cc: New test.

[Bug libstdc++/85828] std::shuffle tries to swap element with itself

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |NEW
           Assignee|redi at gcc dot gnu.org            |unassigned at gcc dot gnu.org