[Bug libstdc++/52822] New: [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[Bug libstdc++/52822] New: [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[jyasskin at gcc dot gnu.org]

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

             Bug #: 52822
           Summary: [C++11] stable_partition destroys sequence due to
                    inappropriate self-move-assignment
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: jyasskin@gcc.gnu.org


The following test program should print "1" twice, since stable_partition is
only supposed to rearrange values, not modify them.

$ cat test.cc
#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
using namespace std;

bool pred(const vector<int>&) { return true; }

int main() {
  vector<vector<int> > v(1);
  v[0].push_back(7);
  cout << v[0].size() << '\n';
  stable_partition(v.begin(), v.end(), pred);
  cout << v[0].size() << '\n';
}
$ g++-4.6pre --version
g++-4.6pre (GCC) 4.6.4 20120330 (prerelease)
$ g++-4.6pre -std=c++98 -g3 test.cc -o test && ./test
1
1
$ g++-4.6pre -std=c++0x -g3 test.cc -o test && ./test
1
0
$ g++-4.7pre --version
g++-4.7pre (GCC) 4.7.1 20120330 (prerelease)
$ g++-4.7pre   -std=c++0x -g3 test.cc -o test && ./test
1
0
$ g++-4.8pre --version
g++-4.8pre (GCC) 4.8.0 20120330 (experimental)
$ g++-4.8pre -std=c++0x -g3 test.cc -o test && ./test
1
0


I believe this happens because
http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/include/bits/stl_algo.h?revision=184997&view=markup#l1827
move-assigns *__result1 from *__first even when those are the same object,
which violates
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#1204.

I haven't audited the rest of the library to look for more instances of this
mistake. I'm planning to switch the default compilation mode to c++0x and run
the gcc-4.6 test suite to look for more problems, but I'm not currently
planning to do the same for 4.7 or trunk.

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[jyasskin at gcc dot gnu.org]

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

--- Comment #1 from Jeffrey Yasskin <jyasskin at gcc dot gnu.org> 2012-04-01 20:41:43 UTC ---
Running the 4.6 testsuite with -std=c++0x as the default was unsuccessful, in
that it found only one error in an execution test, which was already known, and
didn't find the stable_partition bug. Manual inspection it is. :(

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-04-01
     Ever Confirmed|0                           |1

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-04-01 21:14:46 UTC ---
Yeah, I run the whole testsuite with -std=c++0x every now and then, and I think
Paolo does so more often.  Confirming this one though - thanks for finding it.

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[paolo.carlini at oracle dot com]

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

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-04-01 21:50:42 UTC ---
Lately, in 4.6 too, in the occasion of a similar issue, we also added a check
for self-move assignment to __gnu_test::rvalstruct. Evidently, the small
testcases we have got already do not trigger the offending case, unfortunately.

Anyway, luckily these issues are normally easy to fix. If Jeffrey, you are able
to quickly prepare a patch and send it to the mailing list, Jon can approve and
commit it (I will be traveling for a few days). Should be definitely suited for
4.7.1 and maybe 4.6 too, if small enough.

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[paolo.carlini at oracle dot com]

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

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-04-01 22:09:45 UTC ---
PS: then shall we just do the assignment only when __result1 != __first, or
algorithmically we can do better? In case we can also imagine having the
trivial fix for 4.6 and maybe even 4.7.1 and committing it to mainline too
without considering the issue resolved, in case later on somebody figures out
something smarter algorithmically.

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[jyasskin at gcc dot gnu.org]

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

--- Comment #5 from Jeffrey Yasskin <jyasskin at gcc dot gnu.org> 2012-04-02 02:15:24 UTC ---
Created attachment 27058
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27058
Fix by skipping past true-predicate values

Here's an algorithmic fix that passes check-c++. As a side-effect, it makes
__find_if_not available outside C++11 mode. Look good for trunk? Would you want
the simpler __result1!=__first fix for 4.6 and/or 4.7, or is this approach good
for them too?

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[paolo.carlini at oracle dot com]

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

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

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

--- Comment #6 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-04-02 09:10:16 UTC ---
Ah great, thanks. For the FSF branches, I would say, let's just condition the
assignment on 4.6 (+ testcase) and have the complete fix/improvement for
4.7/4.8. Can you send the patch to the mailing lists too? Minor nit: first
blush, doesn't seem completely obvious to me what a 'true' predicate is - and
normally we just have a test for each overload, eg, with/without predicate.
Thus I would recommend extending a bit the comment in the testcase, even better
also have a separate testcase (named as the PR #) for the specific case in the
PR and also extend at will the existing test(s).

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[jyasskin at gcc dot gnu.org]

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

--- Comment #7 from Jeffrey Yasskin <jyasskin at gcc dot gnu.org> 2012-04-02 16:41:41 UTC ---
Sounds good. Will send the patches to the list, probably tomorrow. Thanks!

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[paolo.carlini at oracle dot com]

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

--- Comment #8 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-04-12 12:21:04 UTC ---
Jeffrey, please commit and close the PR. Thanks.

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[jyasskin at gcc dot gnu.org]

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

--- Comment #9 from Jeffrey Yasskin <jyasskin at gcc dot gnu.org> 2012-04-12 20:59:14 UTC ---
Author: jyasskin
Date: Thu Apr 12 20:59:09 2012
New Revision: 186391

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=186391
Log:
Fix PR52822 (stable_partition move-assigns object to itself) by
scanning for the first value that doesn't match the predicate before
starting to rearrange values.

2012-04-03   Jeffrey Yasskin  <jyasskin@google.com>

    PR libstdc++/52822
    * include/bits/stl_algo.h (__find_if_not): Expose in
    C++98 mode.
    (__find_if_not_n): Like __find_if_not, but works on and updates a
    counted range instead of a bounded range.
    (stable_partition): Guarantee !__pred(*__first) in call to
    __stable_partition_adaptive() or __inplace_stable_partition().
    (__stable_partition_adaptive): Use new precondition to avoid
    moving/copying objects onto themselves.  Guarantee new
    precondition to recursive calls.
    (__inplace_stable_partition): Use new precondition to simplify
    base case, remove __last parameter.  Guarantee new precondition to
    recursive calls.
    * testsuite/25_algorithms/stable_partition/moveable.cc (test02):
    Test a sequence that starts with a value matching the predicate.
    * testsuite/25_algorithms/stable_partition/pr52822.cc:
    Test vectors, which have a destructive self-move-assignment.

Added:
    trunk/libstdc++-v3/testsuite/25_algorithms/stable_partition/pr52822.cc
      - copied, changed from r186389,
trunk/libstdc++-v3/testsuite/25_algorithms/stable_partition/moveable.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_algo.h
    trunk/libstdc++-v3/testsuite/25_algorithms/stable_partition/moveable.cc

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[jyasskin at gcc dot gnu.org]

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

--- Comment #10 from Jeffrey Yasskin <jyasskin at gcc dot gnu.org> 2012-04-12 21:42:00 UTC ---
Author: jyasskin
Date: Thu Apr 12 21:41:55 2012
New Revision: 186394

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=186394
Log:
Fix PR52822 (stable_partition move-assigns object to itself) by
scanning for the first value that doesn't match the predicate before
starting to rearrange values.

2012-04-03   Jeffrey Yasskin  <jyasskin@google.com>

    PR libstdc++/52822
    * include/bits/stl_algo.h (__find_if_not): Expose in
    C++98 mode.
    (__find_if_not_n): Like __find_if_not, but works on and updates a
    counted range instead of a bounded range.
    (stable_partition): Guarantee !__pred(*__first) in call to
    __stable_partition_adaptive() or __inplace_stable_partition().
    (__stable_partition_adaptive): Use new precondition to avoid
    moving/copying objects onto themselves.  Guarantee new
    precondition to recursive calls.
    (__inplace_stable_partition): Use new precondition to simplify
    base case, remove __last parameter.  Guarantee new precondition to
    recursive calls.
    * testsuite/25_algorithms/stable_partition/moveable.cc (test02):
    Test a sequence that starts with a value matching the predicate.
    * testsuite/25_algorithms/stable_partition/pr52822.cc:
    Test vectors, which have a destructive self-move-assignment.

Added:
   
branches/gcc-4_7-branch/libstdc++-v3/testsuite/25_algorithms/stable_partition/pr52822.cc
      - copied unchanged from r186391,
trunk/libstdc++-v3/testsuite/25_algorithms/stable_partition/pr52822.cc
Modified:
    branches/gcc-4_7-branch/   (props changed)
    branches/gcc-4_7-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_7-branch/libstdc++-v3/include/bits/stl_algo.h
   
branches/gcc-4_7-branch/libstdc++-v3/testsuite/25_algorithms/stable_partition/moveable.cc

Propchange: branches/gcc-4_7-branch/
            ('svn:mergeinfo' added)

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[jyasskin at gcc dot gnu.org]

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

--- Comment #11 from Jeffrey Yasskin <jyasskin at gcc dot gnu.org> 2012-04-12 22:26:08 UTC ---
Author: jyasskin
Date: Thu Apr 12 22:26:02 2012
New Revision: 186396

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=186396
Log:
Fix PR52822 by explicitly checking for object identity before
move-assigning.  This is a simpler fix than was committed to 4.7 and
4.8.

2012-04-12   Jeffrey Yasskin  <jyasskin@google.com>

    PR libstdc++/52822
    * include/bits/stl_algo.h (__stable_partition_adaptive): Avoid
    move-assigning an object to itself by explicitly testing for
    identity.
    * testsuite/25_algorithms/stable_partition/pr52822.cc: Test
    vectors, which have a destructive self-move-assignment.
    * testsuite/25_algorithms/stable_partition/moveable.cc (test02):
    Test with rvalstruct, which explicitly checks
    self-move-assignment.

Added:
   
branches/gcc-4_6-branch/libstdc++-v3/testsuite/25_algorithms/stable_partition/pr52822.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/testsuite/25_algorithms/stable_partition/moveable.cc

[Bug libstdc++/52822] [C++11] stable_partition destroys sequence due to inappropriate self-move-assignment

[jyasskin at gcc dot gnu.org]

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

Jeffrey Yasskin <jyasskin at gcc dot gnu.org> changed:

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

--- Comment #12 from Jeffrey Yasskin <jyasskin at gcc dot gnu.org> 2012-04-12 22:30:13 UTC ---
Fixed for 4.6.4, 4.7.1 and 4.8.
Sorry for the delay.