Bug 59603 - std::random_shuffle tries to swap element with itself
Summary: std::random_shuffle tries to swap element with itself
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 4.8.2
: P3 normal
Target Milestone: 4.8.4
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2013-12-26 16:36 UTC by Fabian Emmes
Modified: 2015-09-16 11:37 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2014-02-04 00:00:00


Attachments
program triggering the error (204 bytes, text/x-c++src)
2013-12-26 16:37 UTC, Fabian Emmes
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Fabian Emmes 2013-12-26 16:36:21 UTC
When using the debugging macro _GLIBCXX_DEBUG, calling random_shuffle fails on some types, because it might try to swap an element with itself.

Output of attached program:

/tmp$ g++ -o random_shuffle_bug -std=c++11 random_shuffle_bug.cc 
/tmp$ ./random_shuffle_bug 
/usr/include/c++/4.8.2/debug/vector:159:error: attempt to self move assign.

Objects involved in the operation:
sequence "this" @ 0x0xa600c8 {
  type = NSt7__debug6vectorIiSaIiEEE;
}
Aborted (core dumped)

return code: 134

I could not find any information about whether swapping an element with itself is allowed.
Comment 1 Fabian Emmes 2013-12-26 16:37:16 UTC
Created attachment 31518 [details]
program triggering the error
Comment 2 Jörg Richter 2014-02-04 08:37:53 UTC
Seems like we have hit this bug too.  It happens not only in debug mode.  We have a testcase that triggers valgrind errors in non-debug mode while calling random_shuffle.  I can try to reduce this testcase if it would help.
Comment 3 Jonathan Wakely 2014-02-08 20:19:26 UTC
This patch avoids the self-move:

index 4c6ca8a..6ce2d21 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -4430,7 +4430,12 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 
       if (__first != __last)
        for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
-         std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
+         {
+           int __offset = std::rand() % ((__i - __first) + 1);
+           _RandomAccessIterator __j = __first + __offset;
+           if (__i != __j)
+             std::iter_swap(__i, __j);
+         }
     }
 
   /**

But I'm not sure whether this is a real bug, or types used with random_shuffle should be safe against self-move (which means they can't use an implicit move ctor if they have types that are not safe against self-move, which includes most std::lib types).
Comment 4 Jörg Richter 2014-02-09 17:31:02 UTC
Are you sure that this is not a iter_swap problem? I have found nothing in the standard that iter_swap( x, x ) is undefined.

I always thought types do not have to be prepared to handle self move assignment.
Comment 5 Jonathan Wakely 2014-02-10 19:00:42 UTC
Even if swapping an object with itself is well-defined it's a waste of time, so we shouldn't do it.

There's a discussion happening now with the C++ library working group to resolve whether self-move-assignment is user error or supposed to be allowed (i.e. whether the debug mode assertion is ok or not)
Comment 6 Jonathan Wakely 2014-09-12 11:45:32 UTC
(In reply to Jörg Richter from comment #2)
> Seems like we have hit this bug too.  It happens not only in debug mode.  We
> have a testcase that triggers valgrind errors in non-debug mode while
> calling random_shuffle.  I can try to reduce this testcase if it would help.

Would you be able to provide such a test? self-move in non-debug mode should not cause valgrind errors, it should just cause the vector to be left empty (so the valgrind errors might come later if you assume the vector still contains data and try to access it).
Comment 7 Jonathan Wakely 2014-09-12 13:31:08 UTC
Author: redi
Date: Fri Sep 12 13:30:35 2014
New Revision: 215219

URL: https://gcc.gnu.org/viewcvs?rev=215219&root=gcc&view=rev
Log:
	PR libstdc++/59603
	* include/bits/stl_algo.h (random_shuffle): Prevent self-swapping.
	* testsuite/25_algorithms/random_shuffle/59603.cc: New.

Added:
    trunk/libstdc++-v3/testsuite/25_algorithms/random_shuffle/59603.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_algo.h
Comment 8 Jonathan Wakely 2014-09-12 13:35:10 UTC
Fixed on trunk so far.
Comment 9 Jonathan Wakely 2014-10-01 12:34:36 UTC
Author: redi
Date: Wed Oct  1 12:34:04 2014
New Revision: 215754

URL: https://gcc.gnu.org/viewcvs?rev=215754&root=gcc&view=rev
Log:
	PR libstdc++/59603
	* include/bits/stl_algo.h (random_shuffle): Prevent self-swapping.
	* testsuite/25_algorithms/random_shuffle/59603.cc: New.

Added:
    branches/gcc-4_9-branch/libstdc++-v3/testsuite/25_algorithms/random_shuffle/59603.cc
Modified:
    branches/gcc-4_9-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_9-branch/libstdc++-v3/include/bits/stl_algo.h
Comment 10 Jonathan Wakely 2014-12-06 20:38:39 UTC
Author: redi
Date: Sat Dec  6 20:38:07 2014
New Revision: 218454

URL: https://gcc.gnu.org/viewcvs?rev=218454&root=gcc&view=rev
Log:
	PR libstdc++/59603
	* include/bits/stl_algo.h (random_shuffle): Prevent self-swapping.
	* testsuite/25_algorithms/random_shuffle/59603.cc: New.

Added:
    branches/gcc-4_8-branch/libstdc++-v3/testsuite/25_algorithms/random_shuffle/59603.cc
Modified:
    branches/gcc-4_8-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_8-branch/libstdc++-v3/include/bits/stl_algo.h
Comment 11 Jonathan Wakely 2014-12-06 22:04:30 UTC
Fixed in all active branches.
Comment 12 Tony E Lewis 2015-09-16 11:37:26 UTC
Thanks for work on this.

Should this fix be applied to shuffle() as well as to random_shuffle()?