[Bug libstdc++/59603] New: std::random_shuffle tries to swap element with itself

[Bug libstdc++/59603] New: std::random_shuffle tries to swap element with itself

[fab at orlen dot de]

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

            Bug ID: 59603
           Summary: std::random_shuffle tries to swap element with itself
           Product: gcc
           Version: 4.8.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: fab at orlen dot de

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.

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[fab at orlen dot de]

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

--- Comment #1 from Fabian Emmes <fab at orlen dot de> ---
Created attachment 31518
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31518&action=edit
program triggering the error

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[joerg.richter@pdv-fs.de]

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

Jörg Richter <joerg.richter@pdv-fs.de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |joerg.richter@pdv-fs.de

--- Comment #2 from Jörg Richter <joerg.richter@pdv-fs.de> ---
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.
>From gcc-bugs-return-442496-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Tue Feb 04 08:42:20 2014
Return-Path: <gcc-bugs-return-442496-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 24450 invoked by alias); 4 Feb 2014 08:42:20 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 24381 invoked by uid 48); 4 Feb 2014 08:42:15 -0000
From: "jakub at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug sanitizer/60055] Invalid binding of __tsan_default_options
Date: Tue, 04 Feb 2014 08:42:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: sanitizer
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: jakub at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-60055-4-G0KOl6rmVn@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-60055-4@http.gcc.gnu.org/bugzilla/>
References: <bug-60055-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-02/txt/msg00253.txt.bz2
Content-length: 219

http://gcc.gnu.org/bugzilla/show_bug.cgi?id`055

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Shouldn't __tsan::OnFinalize also have SANITIZER_INTERFACE_ATTRIBUTE ?
__tsan::OnReport does have it.

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-02-04
     Ever confirmed|0                           |1

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
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).

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[joerg.richter@pdv-fs.de]

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

--- Comment #4 from Jörg Richter <joerg.richter@pdv-fs.de> ---
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.
>From gcc-bugs-return-443131-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sun Feb 09 17:32:47 2014
Return-Path: <gcc-bugs-return-443131-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 17998 invoked by alias); 9 Feb 2014 17:32:46 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 17640 invoked by uid 55); 9 Feb 2014 17:32:42 -0000
From: "janus at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug fortran/58803] Proc-pointer component: free_components deallocates twice pointer p->tb at symbol.c:2068
Date: Sun, 09 Feb 2014 17:32:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: fortran
X-Bugzilla-Version: 4.8.2
X-Bugzilla-Keywords: wrong-code
X-Bugzilla-Severity: normal
X-Bugzilla-Who: janus at gcc dot gnu.org
X-Bugzilla-Status: RESOLVED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-58803-4-PCpW7zTBkD@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-58803-4@http.gcc.gnu.org/bugzilla/>
References: <bug-58803-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-02/txt/msg00888.txt.bz2
Content-length: 909

http://gcc.gnu.org/bugzilla/show_bug.cgi?idX803

--- Comment #4 from janus at gcc dot gnu.org ---
Author: janus
Date: Sun Feb  9 17:32:07 2014
New Revision: 207644

URL: http://gcc.gnu.org/viewcvs?rev 7644&root=gcc&view=rev
Log:
2014-02-09  Janus Weil  <janus@gcc.gnu.org>

    Backport from mainline
    2013-10-21  Tobias Burnus  <burnus@net-b.de>

    PR fortran/58803
    PR fortran/59395
    * decl.c (match_ppc_decl): Prevent later double free.


2014-02-09  Janus Weil  <janus@gcc.gnu.org>

    Backport from mainline
    2013-10-21  Tobias Burnus  <burnus@net-b.de>

    PR fortran/58803
    PR fortran/59395
    * gfortran.dg/proc_ptr_comp_38.f90: New.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/gfortran.dg/proc_ptr_comp_38.f90
Modified:
    branches/gcc-4_8-branch/gcc/fortran/ChangeLog
    branches/gcc-4_8-branch/gcc/fortran/decl.c
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
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)

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(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).
>From gcc-bugs-return-461667-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Fri Sep 12 11:53:26 2014
Return-Path: <gcc-bugs-return-461667-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 2071 invoked by alias); 12 Sep 2014 11:53:26 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 2001 invoked by uid 48); 12 Sep 2014 11:53:21 -0000
From: "mark at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug debug/16063] Debuggers need more information about enum types in C++
Date: Fri, 12 Sep 2014 11:53:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: debug
X-Bugzilla-Version: 3.4.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: enhancement
X-Bugzilla-Who: mark at gcc dot gnu.org
X-Bugzilla-Status: RESOLVED
X-Bugzilla-Priority: P2
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status resolution
Message-ID: <bug-16063-4-B5dgusn8i2@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-16063-4@http.gcc.gnu.org/bugzilla/>
References: <bug-16063-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-09/txt/msg01501.txt.bz2
Content-length: 547

https://gcc.gnu.org/bugzilla/show_bug.cgi?id\x16063

Mark Wielaard <mark at gcc dot gnu.org> changed:

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

--- Comment #10 from Mark Wielaard <mark at gcc dot gnu.org> ---
(In reply to Marek Polacek from comment #9)
> So, is this fixed?

Yes, I do believe so, in gcc trunk. Sorry for not closing earlier.

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[redi at gcc dot gnu.org]

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

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
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

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed on trunk so far.

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[redi at gcc dot gnu.org]

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

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
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

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[redi at gcc dot gnu.org]

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

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

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

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed in all active branches.

[Bug libstdc++/59603] std::random_shuffle tries to swap element with itself

[TonyELewis at hotmail dot com]

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

Tony E Lewis <TonyELewis at hotmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |TonyELewis at hotmail dot com

--- Comment #12 from Tony E Lewis <TonyELewis at hotmail dot com> ---
Thanks for work on this.

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