[Bug libstdc++/61023] New: set/map move assignment doesn't move (or copy) the comparator

[Bug libstdc++/61023] New: set/map move assignment doesn't move (or copy) the comparator

[nevin at eviloverlord dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61023

            Bug ID: 61023
           Summary: set/map move assignment doesn't move (or copy) the
                    comparator
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: nevin at eviloverlord dot com

If you have a stateful comparator, set/map move assignment does not move (or
copy, for that matter) the comparator.

Test case:

struct Compare
{
    Compare(bool b) : b_(b) {}

    bool operator()(int l, int r) const
    { return b_ ? r < l : l < r; }

    bool b_; 
};

int main() 
{
    typedef std::set<int, Compare> S;

    S s(Compare(false));

    s.insert(2);
    s.insert(3);
    assert(*s.begin() == 2); 

    s.clear();
    S st(Compare(true));

    s = std::move(st); // move assignment

    s.insert(2);
    s.insert(3);
    assert(*s.begin() == 3); // fails

    return 0;
}

[Bug libstdc++/61023] set/map move assignment doesn't move (or copy) the comparator

[nevin at eviloverlord dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61023

--- Comment #1 from Nevin Liber <nevin at eviloverlord dot com> ---
Created attachment 32719
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32719&action=edit
Test case using set showing the problem

[Bug libstdc++/61023] set/map move assignment doesn't move (or copy) the comparator

[nevin at eviloverlord dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61023

--- Comment #2 from Nevin Liber <nevin at eviloverlord dot com> ---
Also happens with multiset and multimap.

[Bug libstdc++/61023] set/map move assignment doesn't move (or copy) the comparator

[nevin at eviloverlord dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61023

--- Comment #4 from Nevin Liber <nevin at eviloverlord dot com> ---
Good point about the Standard.

However, the current behavior for move assignment breaks the invariant of the
container, since the comparator is what enforces the insertion ordering and
element equivalence.

Take for example:

struct Compare
{
    Compare(bool b) : b_(b) {}

    bool operator()(int l, int r) const
    { return b_ ? r < l : l < r; }

    bool b_;
};

int main()
{
    typedef std::set<int, Compare> S;

    S s(Compare(false));
    s.insert(2);
    s.insert(3);

    S abracadabra(Compare(true));

    // The heisenbug 3...
    abracadabra = std::move(s);
    assert(abracadabra.find(2) == std::find(abracadabra.begin(),
abracadabra.end(), 2)); // works
    assert(abracadabra.find(3) == std::find(abracadabra.begin(),
abracadabra.end(), 3)); // fails
}


This behavior seems untenable to me.

The implementation needs to do something more reasonable.  Even something as
drastic as deleting the ordered associative container move assignment when
stateful comparators are involved is better than the status quo.

[Bug libstdc++/61023] set/map move assignment doesn't move (or copy) the comparator

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61023

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2014-05-04
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Agreed, and I think there's an obvious approach to solve it, so we don't need
to wait for a DR.

[Bug libstdc++/61023] set/map move assignment doesn't move (or copy) the comparator

[ppluzhnikov at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61023

Paul Pluzhnikov <ppluzhnikov at google dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ppluzhnikov at google dot com

--- Comment #6 from Paul Pluzhnikov <ppluzhnikov at google dot com> ---
Created attachment 32750
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32750&action=edit
test case for move assignment operator

Just discovered this in Google code as well. Ref b/14590795

Move assign operator is broken the same way:

  for no_rvalue in 1 0; do
    for test in TEST_{,MULTI}{SET,MAP}; do
      echo -e "$no_rvalue $test \c"; g++ -std=c++11 set.cc  -D$test -g
-DNO_RVALUE=$no_rvalue && ./a.out &> /dev/null &&
        echo OK
    done
  done

1 TEST_SET OK
1 TEST_MAP OK
1 TEST_MULTISET OK
1 TEST_MULTIMAP OK
0 TEST_SET Aborted (core dumped)
0 TEST_MAP Aborted (core dumped)
0 TEST_MULTISET Aborted (core dumped)
0 TEST_MULTIMAP Aborted (core dumped)


Note: this is a 4.9/4.10 regression -- 4.8.3 works correctly.

[Bug libstdc++/61023] [4.9/4.10 Regression] set/map move assignment doesn't move (or copy) the comparator

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61023

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.8.2
   Target Milestone|---                         |4.9.1
            Summary|set/map move assignment     |[4.9/4.10 Regression]
                   |doesn't move (or copy) the  |set/map move assignment
                   |comparator                  |doesn't move (or copy) the
                   |                            |comparator

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Testing this:

--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1073,6 +1073,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     _M_move_assign(_Rb_tree& __x)
     {
+      _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
       if (_Alloc_traits::_S_propagate_on_move_assign()
          || _Alloc_traits::_S_always_equal()
          || _M_get_Node_allocator() == __x._M_get_Node_allocator())

But the more I think about it the less sure I am whether we want to move or
just copy the functor from the source. In the move constructor we only copy.

[Bug libstdc++/61023] [4.9/4.10 Regression] set/map move assignment doesn't move (or copy) the comparator

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61023

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Wed May  7 14:12:06 2014
New Revision: 210158

URL: http://gcc.gnu.org/viewcvs?rev=210158&root=gcc&view=rev
Log:
    PR libstdc++/61023
    * include/bits/stl_tree.h (_Rb_tree::_M_move_assign): Copy the
    comparison function.
    * testsuite/23_containers/set/cons/61023.cc: New.

    PR libstdc++/61023
    * include/bits/stl_tree.h (_Rb_tree::_M_move_assign): Copy the
    comparison function.
    * testsuite/23_containers/set/cons/61023.cc: New.

Added:
   
branches/gcc-4_9-branch/libstdc++-v3/testsuite/23_containers/set/cons/61023.cc
Modified:
    branches/gcc-4_9-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_9-branch/libstdc++-v3/include/bits/stl_tree.h

[Bug libstdc++/61023] [4.9/4.10 Regression] set/map move assignment doesn't move (or copy) the comparator

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61023

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Wed May  7 14:12:37 2014
New Revision: 210159

URL: http://gcc.gnu.org/viewcvs?rev=210159&root=gcc&view=rev
Log:
    PR libstdc++/61023
    * include/bits/stl_tree.h (_Rb_tree::_M_move_assign): Copy the
    comparison function.
    * testsuite/23_containers/set/cons/61023.cc: New.

Added:
    trunk/libstdc++-v3/testsuite/23_containers/set/cons/61023.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_tree.h

[Bug libstdc++/61023] [4.9/4.10 Regression] set/map move assignment doesn't move (or copy) the comparator

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61023

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
fixed