[Bug libstdc++/49559] New: stable_sort calls self-move-assignment operator

[Bug libstdc++/49559] New: stable_sort calls self-move-assignment operator

[joerg.richter@pdv-fs.de]

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

           Summary: stable_sort calls self-move-assignment operator
           Product: gcc
           Version: 4.6.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: joerg.richter@pdv-fs.de


$ cat t.cc
#include <cassert>
#include <algorithm>
#include <iostream>

struct MyMoveClass
{
    int val_;

    explicit MyMoveClass( int val = 0 )
      : val_( val )
    {
      std::cout << "ctr this=" << this << std::endl;
    }

    MyMoveClass( MyMoveClass const& rhs )
      : val_( rhs.val_ )
    {
      std::cout << "ctr copy this=" << this << " rhs=" << &rhs << std::endl;
    }

    MyMoveClass( MyMoveClass && rhs )
      : val_( rhs.val_ )
    {
      std::cout << "ctr move this=" << this << " rhs=" << &rhs << std::endl;
      rhs.val_ = 0;
    }

    MyMoveClass& operator=( MyMoveClass && rhs )
    {
      std::cout << "assign move this=" << this << " rhs=" << &rhs << std::endl;
      assert( this != &rhs );
      val_ = rhs.val_;
      rhs.val_ = 0;
      return *this;
    }

    MyMoveClass& operator=( MyMoveClass const& rhs )
    {
      std::cout << "assign copy this=" << this << " rhs=" << &rhs << std::endl;
      val_ = rhs.val_;
      return *this;
    }

    ~MyMoveClass()
    {
      std::cout << "dtr this=" << this << std::endl;
    }

    bool operator<( MyMoveClass const& rhs ) const
    {
      return val_ < rhs.val_;
    }
};

int main()
{
  MyMoveClass v(5);
  std::stable_sort( &v, &v+1 );
  return 0;
}


$ g++ -std=gnu++0x -o t t.cc

$ ./t
ctr this=0xbfe1730c
ctr move this=0x8afd008 rhs=0xbfe1730c
assign move this=0xbfe1730c rhs=0x8afd008
assign move this=0xbfe1730c rhs=0xbfe1730c
template: template.cc:31: MyMoveClass& MyMoveClass::operator=(MyMoveClass&&):
Assertion `this != &rhs' failed.


>From DR 1204: "Additionally this clarifies that move assignment operators need
not perform the traditional if (this != &rhs) test commonly found (and needed)
in copy assignment operators."

Note that std::sort() calls no copy constructor or assignment operator at all. 
Seems sensible when there is only one element.

[Bug libstdc++/49559] stable_sort calls self-move-assignment operator

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.06.28 08:41:06
     Ever Confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-06-28 08:41:06 UTC ---
confirmed, __copy_move_b in stl_algobase.h performs the redundant self-move

this untested change fixes the testcase but I haven't checked if it's correct
or passes the testsuite:

Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h (revision 175389)
+++ include/bits/stl_algobase.h (working copy)
@@ -541,8 +541,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
         static _BI2
         __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
         {
-         typename iterator_traits<_BI1>::difference_type __n;
-         for (__n = __last - __first; __n > 0; --__n)
+         typename iterator_traits<_BI1>::difference_type __n
+           = __last - __first;
+         if (__n <= 1)
+           return __first;
+         for (; __n > 0; --__n)
            *--__result = std::move(*--__last);
          return __result;
        }

[Bug libstdc++/49559] stable_sort calls self-move-assignment operator

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-06-28 08:56:39 UTC ---
bah, that's testing the wrong thing
the test should be:
      if (__result == __last)
        return __first;

[Bug libstdc++/49559] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jwakely.gcc at gmail dot
                   |                            |com

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-06-28 09:45:22 UTC ---
Irrespective of what happens in other functions, I think we want to check at
the beginning of stable_sort whether __last - __first > 1 and thus avoid the
_Temporary_buffer dance otherwise. Then, Jon, I'm not sure to understand what
you propose to do, note that __last and __result have different types. Also
note that the FDIS is *very* explicit about what move_backward does (+ I see
now that we have a typo in the documentation comment: "Result may not be in the
range (first,last]" *not* "Result may not be in the range [first,last)"

[Bug libstdc++/49559] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot       |paolo.carlini at oracle dot
                   |gnu.org                     |com
   Target Milestone|---                         |4.6.2

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |chris at bubblescope dot
                   |                            |net

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-06-28 10:41:20 UTC ---
So, I added a:

Index: util/testsuite_rvalref.h
===================================================================
--- util/testsuite_rvalref.h    (revision 175578)
+++ util/testsuite_rvalref.h    (working copy)
@@ -68,6 +68,7 @@
     operator=(rvalstruct&& in)
     {
       bool test __attribute__((unused)) = true;
+      VERIFY( this != &in );
       VERIFY( in.valid == true );
       val = in.val;
       in.valid = false;

and got fails for the 25_algorithms/inplace_merge/moveable.cc tests.

Chris, are you willing to have a look? I seem to remember that you did a lot of
work in this area...

I'm not seeing other fails, luckily.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-06-28 10:45:11 UTC ---
(In reply to comment #3)
> note that the FDIS is *very* explicit about what move_backward does

Ah ok - but if move_backward has to do that then we should avoid calling it at
all when nothing needs to move, maybe in __move_merge_backward

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #6 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-06-28 10:56:50 UTC ---
Maybe, yes. I'm going to attaching as a draft patch what I have so far, if you
could coordinate with Chris and complete it, would be great...

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-06-28 10:58:09 UTC ---
Created attachment 24613
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24613
Draft patch. inplace_merge still needs work.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #8 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-06-28 13:38:06 UTC ---
For inplace_merge the problem happens with the _GLIBCXX_MOVE3 calls in
__move_merge, at some point __first == __result != __last.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |paolo.carlini at oracle dot
                   |                            |com

--- Comment #9 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-06-28 14:11:32 UTC ---
Given the specific instantiations we have of __move_merge, something like the
new draft I'm attaching seems correct and avoids the regressions for
inplace_merge. But actually it seems __first2 always == __result after the
first move, thus I think we really want to rework and possibly simplify these
__move_merge helpers.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #10 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-06-28 14:12:36 UTC ---
Created attachment 24617
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24617
New draft

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #24617|0                           |1
        is obsolete|                            |

--- Comment #11 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-06-28 16:22:05 UTC ---
Comment on attachment 24617
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24617
New draft

Never mind the last patch, isn't ok for stable_sort etc.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #12 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-06-28 18:06:54 UTC ---
I'm looking at __merge_adaptive and it seems to me that self move assignment
can happen very generically. Consider:

 if (__len1 <= __len2 && __len1 <= __buffer_size)
   {
     _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
     std::__move_merge(__buffer, __buffer_end, __middle, __last, __first);
   }

here __first comes in memory before __middle and when __move_merge has filled
all the positions before __middle then any element can be move assigned from
itself. Of course we could always move to the buffer the entire range __first,
__last. Still looking for Chris' opinion on this, he updated this code to move
instead of copy...

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[chris at bubblescope dot net]

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

--- Comment #13 from Chris Jefferson <chris at bubblescope dot net> 2011-06-28 19:16:00 UTC ---
I am on holiday until tomorrow night, and away from a computer. Once I get
back, I promise to give this my full attention. This code got messy in the
first place because I was trying to make minimal changes to already confusing
code. I still see if this can be easily cleaned, our if we should use a
different method.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #14 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-06-28 19:38:47 UTC ---
Thanks Chris, I appreciate that, I know I can always count on you. Actually, I
will be on vacation for a few days starting tomorrow, but I will bring the
laptop will be and will be able to provide feedback and all due attention to
your work. I'm thinking, we could also prepare two different fixes: one
minimally invasive for 4.6.2 and another more invasive for 4.7. At the moment,
I'm under the impression that a proper fix involves massaging __merge_adaptive
quite a bit...

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #15 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-07-07 09:53:23 UTC ---
Chris, shall we attack this issue? Thanks.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #16 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-07-08 11:01:06 UTC ---
I believe I'm making good progress in analyzing, thus fixing, the issue with
inplace_merge: what I see clearly now is that - as noticed in Comment 9 for the
first time - __move_merge, for the purpose of __merge_adaptive, can be safely
changed to simply end with:

      return _GLIBCXX_MOVE3(__first1, __last1, __result);

and the self-move assignment issue is solved. The reason being that when the
main while loop is exited with __first2 != __last2, __first2 always points to
the same position pointed by __result: indeed, in the case of inplace_merge the
overall source and destination ranges coincide and nothing else is possible.

However, __move_merge is also used by __merge_sort_loop, where different
assumptions hold. I don't know at the moment if we can do something better than
just specializing __move_merge for __merge_adaptive per the above.

Also, remains to be analyzed the *_backward case.

Chris, any help is welcome.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #17 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-07-08 11:46:10 UTC ---
The *_backward case seems rather straightforward, with the roles of the
__first1, __last1 and __first2, __last2 ranges swapped.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #24613|0                           |1
        is obsolete|                            |

--- Comment #18 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-07-08 15:46:35 UTC ---
Created attachment 24717
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24717
Draft patch, passes testing.

This is what I have so far. Looks pretty good to me.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #24717|0                           |1
        is obsolete|                            |

--- Comment #19 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-07-08 16:20:59 UTC ---
Created attachment 24718
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24718
Slightly better, testcases fixed.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo at gcc dot gnu.org]

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

--- Comment #20 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> 2011-07-11 18:39:03 UTC ---
Author: paolo
Date: Mon Jul 11 18:38:54 2011
New Revision: 176174

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=176174
Log:
2011-07-11  Paolo Carlini  <paolo.carlini@oracle.com>

    PR libstdc++/49559
    * include/bits/stl_algo.h (__move_merge_backward): Remove.
    (__move_merge_adaptive, __move_merge_adaptive_backward): New.
    (__merge_adaptive): Use the latter two.
    (__rotate_adaptive): Avoid self move-assignment.
    * include/bits/stl_algobase.h (move_backward): Fix comment.
    * testsuite/25_algorithms/stable_sort/49559.cc: New.
    * testsuite/25_algorithms/inplace_merge/49559.cc: Likewise.
    * testsuite/25_algorithms/inplace_merge/moveable.cc: Extend.
    * testsuite/25_algorithms/inplace_merge/moveable2.cc: Likewise.
    * testsuite/util/testsuite_rvalref.h (rvalstruct::operator=
    (rvalstruct&&)): Check for self move-assignment.

Added:
    trunk/libstdc++-v3/testsuite/25_algorithms/inplace_merge/49559.cc
    trunk/libstdc++-v3/testsuite/25_algorithms/stable_sort/49559.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_algo.h
    trunk/libstdc++-v3/include/bits/stl_algobase.h
    trunk/libstdc++-v3/testsuite/25_algorithms/inplace_merge/moveable.cc
    trunk/libstdc++-v3/testsuite/25_algorithms/inplace_merge/moveable2.cc
    trunk/libstdc++-v3/testsuite/util/testsuite_rvalref.h

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

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

--- Comment #21 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-07-11 18:42:57 UTC ---
Fixed for 4.7.0.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[joerg.richter@pdv-fs.de]

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

--- Comment #22 from joerg.richter@pdv-fs.de 2011-07-13 15:11:21 UTC ---
Is it possible to fix it for 4.6.2?
Following program is a 4.4 regression (when using -std=gnu++0x):

-------8<---------
#include <cassert>
#include <vector>
#include <algorithm>

using namespace std;

int main( int, char** )
{
  vector<int> v;
  v.push_back( 1 );
  stable_sort( &v, &v+1 );
  assert( v.size() == 1 );
  return 0;
}
-------8<---------

Works with 4.4.1, fails with 4.5 and 4.6

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #23 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-07-13 15:20:23 UTC ---
To be honest, isn't a real regression, because you are using -std=gnu++0x, and
simply in 4.4.x we had no C++0x conforming std::stable_sort. In general, my
feeling is that the fix is too invasive for 4.6.x, but please stress it as much
as possible and if in a couple of weeks no regressions will appear we can
reconsider a backport.

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo at gcc dot gnu.org]

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

--- Comment #24 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> 2011-09-27 08:22:22 UTC ---
Author: paolo
Date: Tue Sep 27 08:22:07 2011
New Revision: 179242

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=179242
Log:
2011-09-27  Paolo Carlini  <paolo.carlini@oracle.com>

    PR libstdc++/49559
    * include/bits/stl_algo.h (__move_merge_backward): Remove.
    (__move_merge_adaptive, __move_merge_adaptive_backward): New.
    (__merge_adaptive): Use the latter two.
    (__rotate_adaptive): Avoid self move-assignment.
    * include/bits/stl_algobase.h (move_backward): Fix comment.
    * testsuite/25_algorithms/stable_sort/49559.cc: New.
    * testsuite/25_algorithms/inplace_merge/49559.cc: Likewise.
    * testsuite/25_algorithms/inplace_merge/moveable.cc: Extend.
    * testsuite/25_algorithms/inplace_merge/moveable2.cc: Likewise.
    * testsuite/util/testsuite_rvalref.h (rvalstruct::operator=
    (rvalstruct&&)): Check for self move-assignment.

Added:
   
branches/gcc-4_6-branch/libstdc++-v3/testsuite/25_algorithms/inplace_merge/49559.cc
   
branches/gcc-4_6-branch/libstdc++-v3/testsuite/25_algorithms/stable_sort/49559.cc
Modified:
    branches/gcc-4_6-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_6-branch/libstdc++-v3/include/bits/stl_algo.h
    branches/gcc-4_6-branch/libstdc++-v3/include/bits/stl_algobase.h
   
branches/gcc-4_6-branch/libstdc++-v3/testsuite/25_algorithms/inplace_merge/moveable.cc
   
branches/gcc-4_6-branch/libstdc++-v3/testsuite/25_algorithms/inplace_merge/moveable2.cc
    branches/gcc-4_6-branch/libstdc++-v3/testsuite/util/testsuite_rvalref.h

[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.0                       |4.6.2

--- Comment #25 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-09-27 08:23:53 UTC ---
Fixed for 4.6.2 too.