[Bug libstdc++/103501] New: associative containers left invalid after allocator-extended move construction

[Bug libstdc++/103501] New: associative containers left invalid after allocator-extended move construction

[redi at gcc dot gnu.org]

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

            Bug ID: 103501
           Summary: associative containers left invalid after
                    allocator-extended move construction
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org
  Target Milestone: ---

#include <set>
#include <iostream>

template<typename T>
struct Alloc : std::allocator<T>
{
  template<typename U> struct rebind { using other = Alloc<U>; };

  Alloc(int i) : id(i) { }

  template<typename U>
    Alloc(const Alloc<U>& a) : id(a.id) { }

  int id;

  using is_always_equal = std::false_type;

  bool operator==(const Alloc& a) const { return id == a.id; }
  bool operator!=(const Alloc& a) const { return id != a.id; }
};


struct X
{
  int i;

  X(int i) : i(i) { }
  X(const X& x) noexcept : i(x.i) { }
  X(X&& x) noexcept : i(x.i) { x.i = -1; }

  bool operator<(const X& rhs) const { return i < rhs.i; }
};

struct Y
{
  int i;

  Y(int i) : i(i) { }
  Y(const Y& y) noexcept : i(y.i) { }
  Y(Y&& y) noexcept : i(y.i) { y.i = -y.i; }

  bool operator<(const Y& rhs) const { return i < rhs.i; }
};


int main()
{
  std::set<X, std::less<>, Alloc<X>> s1{ {1, 2, 3}, Alloc<X>(1)};
  std::set<X, std::less<>, Alloc<X>> s2{ std::move(s1), Alloc<X>(2) };
  for (auto& x : s1)
    std::cout << x.i << '\n';

  std::cout << '\n';

  std::multiset<Y, std::less<>, Alloc<Y>> m1{ {1, 2, 3}, Alloc<Y>(1)};
  std::multiset<Y, std::less<>, Alloc<Y>> m2{ std::move(m1), Alloc<Y>(2) };
  for (auto& y : m1)
    std::cout << y.i << '\n';
}

The sets are left with broken invariants, printing:

-1
-1
-1

-1
-2
-3

(the std::set has non-unique elements, the std::multiset has elements in
non-increasing order).

The problem is that we move each individual element when the allocators are not
equal, and that can leave non-unique elements behind.

I think we need to clear the moved-from sets in this case.

I haven't checked the unordered containers yet to see if they have the same
issue.

[Bug libstdc++/103501] associative containers left invalid after allocator-extended move construction

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-11-30
     Ever confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This causes the following failures when using --enable-fully-dynamic-string on
trunk:

FAIL: 23_containers/multiset/allocator/move_cons.cc execution test
FAIL: 23_containers/map/allocator/move_cons.cc execution test
FAIL: 23_containers/multimap/allocator/move_cons.cc execution test
FAIL: 23_containers/set/allocator/move_cons.cc execution test

This is because a moved-from fully-dynamic string is no longer empty. As shown
above, the problem is broader than just fully-dynamic strings.

[Bug libstdc++/103501] associative containers left invalid after allocator-extended move construction

[cvs-commit at gcc dot gnu.org]

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

--- Comment #2 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:056551414a328b427c4bf4955b9a3832f344685c

commit r12-5693-g056551414a328b427c4bf4955b9a3832f344685c
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Nov 30 23:32:50 2021 +0000

    libstdc++: Clear RB tree after moving elements [PR103501]

    If the allocator-extended move constructor move-constructs each element
    into the new container, the contents of the old container are left in
    moved-from states. We cannot know if those states preserve the
    container's ordering and uniqueness guarantees, so just erase all
    moved-from elements.

    libstdc++-v3/ChangeLog:

            PR libstdc++/103501
            * include/bits/stl_tree.h (_Rb_tree(_Rb_tree&&, false_type)):
            Clear container if elements have been moved-from.
            * testsuite/23_containers/map/allocator/move_cons.cc: Expect
            moved-from container to be empty.
            * testsuite/23_containers/multimap/allocator/move_cons.cc:
            Likewise.
            * testsuite/23_containers/multiset/allocator/103501.cc: New test.
            * testsuite/23_containers/set/allocator/103501.cc: New test.

[Bug libstdc++/103501] associative containers left invalid after allocator-extended move construction

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #0)
> I haven't checked the unordered containers yet to see if they have the same
> issue.

This still needs to be done.

[Bug libstdc++/103501] associative containers left invalid after allocator-extended move construction

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

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

commit r11-9438-gbae757f80970824fbc6a1a2598b233ff489efa4a
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Nov 30 23:32:50 2021 +0000

    libstdc++: Clear RB tree after moving elements [PR103501]

    If the allocator-extended move constructor move-constructs each element
    into the new container, the contents of the old container are left in
    moved-from states. We cannot know if those states preserve the
    container's ordering and uniqueness guarantees, so just erase all
    moved-from elements.

    libstdc++-v3/ChangeLog:

            PR libstdc++/103501
            * include/bits/stl_tree.h (_Rb_tree(_Rb_tree&&, false_type)):
            Clear container if elements have been moved-from.
            * testsuite/23_containers/map/allocator/move_cons.cc: Expect
            moved-from container to be empty.
            * testsuite/23_containers/multimap/allocator/move_cons.cc:
            Likewise.
            * testsuite/23_containers/multiset/allocator/103501.cc: New test.
            * testsuite/23_containers/set/allocator/103501.cc: New test.

    (cherry picked from commit 056551414a328b427c4bf4955b9a3832f344685c)

[Bug libstdc++/103501] associative containers left invalid after allocator-extended move construction

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

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

commit r10-10837-gd4fdb293004f2e104edf823d4820d4ee73aa2660
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Nov 30 23:32:50 2021 +0000

    libstdc++: Clear RB tree after moving elements [PR103501]

    If the allocator-extended move constructor move-constructs each element
    into the new container, the contents of the old container are left in
    moved-from states. We cannot know if those states preserve the
    container's ordering and uniqueness guarantees, so just erase all
    moved-from elements.

    libstdc++-v3/ChangeLog:

            PR libstdc++/103501
            * include/bits/stl_tree.h (_Rb_tree(_Rb_tree&&, false_type)):
            Clear container if elements have been moved-from.
            * testsuite/23_containers/multiset/allocator/103501.cc: New test.
            * testsuite/23_containers/set/allocator/103501.cc: New test.

    (cherry picked from commit 056551414a328b427c4bf4955b9a3832f344685c)

[Bug libstdc++/103501] associative containers left invalid after allocator-extended move construction

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |10.4

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 10.4 and 11.3 and 12.1, but I still need to check the unordered
containers.

[Bug libstdc++/103501] associative containers left invalid after allocator-extended move construction

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.4                        |10.5

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 10.4 is being released, retargeting bugs to GCC 10.5.

[Bug libstdc++/103501] associative containers left invalid after allocator-extended move construction

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.5                        |10.4

[Bug libstdc++/103501] associative containers left invalid after allocator-extended move construction

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |10.3.0
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.