[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator
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=gccview=revrev=179242 Log: 2011-09-27 Paolo Carlini paolo.carl...@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
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.
[Bug libstdc++/49559] [C++0x] stable_sort calls self-move-assignment operator
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49559
--- Comment #22 from joerg.rich...@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** )
{
vectorint 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
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
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=gccview=revrev=176174 Log: 2011-07-11 Paolo Carlini paolo.carl...@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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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...
