[Bug libstdc++/48038] New: stable_sort problem with C++0x and comparator by value

[Bug libstdc++/48038] New: stable_sort problem with C++0x and comparator by value

[vincenzo.innocente at cern dot ch]

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

           Summary: stable_sort problem with C++0x and comparator by value
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: critical
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: vincenzo.innocente@cern.ch


if one uses a comparator where arguments are passed by value such as
inline bool operator<(V rh, V lh) {
something goes wrong with "move" and default constructed objects are passed in
the comparator
It happens in stable_sort for sure
I'm using a recent version of 4.6
g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/local/libexec/gcc/x86_64-unknown-linux-gnu/4.6.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ./configure --enable-gold=yes --enable-lto --with-fpmath=avx
Thread model: posix
gcc version 4.6.0 20110205 (experimental) (GCC) 

this is an example I use that produces a seg-fault (easy to detect)
 g++ -O2 -std=gnu++0x -g rvalue.cpp -DBYVALUE
will seg-fault
 g++ -O2 -std=gnu++0x -g rvalue.cpp
is ok
the seg-fault is in
Program received signal SIGSEGV, Segmentation fault.
std::merge<std::move_iterator<V*>,
std::move_iterator<__gnu_cxx::__normal_iterator<V*, std::vector<V,
std::allocator<V> > > >, __gnu_cxx::__normal_iterator<V*, std::vector<V,
std::allocator<V> > > > (__first1=..., __last1=..., __first2=<value optimized
out>, __last2=..., 
    __result=<value optimized out>) at
/usr/local/lib/gcc/x86_64-unknown-linux-gnu/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h:5390
5390          if (*__first2 < *__first1)
Missing separate debuginfos, use: debuginfo-install
glibc-2.12-1.7.el6_0.3.x86_64
(gdb) where
#0  std::merge<std::move_iterator<V*>,
std::move_iterator<__gnu_cxx::__normal_iterator<V*, std::vector<V,
std::allocator<V> > > >, __gnu_cxx::__normal_iterator<V*, std::vector<V,
std::allocator<V> > > > (__first1=..., __last1=..., __first2=<value optimized
out>, __last2=..., 
    __result=<value optimized out>) at
/usr/local/lib/gcc/x86_64-unknown-linux-gnu/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h:5390
#1  0x0000000000406f86 in
std::__merge_adaptive<__gnu_cxx::__normal_iterator<V*, std::vector<V,
std::allocator<V> > >, long, V*> (__first=..., 
    __middle=..., __last=..., __len1=<value optimized out>, __len2=<value
optimized out>, __buffer=0x615cc0, __buffer_size=6)
    at
/usr/local/lib/gcc/x86_64-unknown-linux-gnu/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h:2835
#2  0x0000000000408195 in
std::__stable_sort_adaptive<__gnu_cxx::__normal_iterator<V*, std::vector<V,
std::allocator<V> > >, V*, long> (
    __first=..., __last=..., __buffer=0x615cc0, __buffer_size=6)
    at
/usr/local/lib/gcc/x86_64-unknown-linux-gnu/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h:3312
#3  0x000000000040d0e0 in stable_sort<__gnu_cxx::__normal_iterator<V*,
std::vector<V, std::allocator<V> > > > ()
    at
/usr/local/lib/gcc/x86_64-unknown-linux-gnu/4.6.0/../../../../include/c++/4.6.0/bits/stl_algo.h:5508
#4  go<V> () at rvalue.cpp:114
#5  0x000000000040f6f9 in main () at rvalue.cpp:135

the test program
cat rvalue.cpp
#include <vector>
#include <iostream>
#include<functional>
#include<algorithm>

typedef std::vector<double> VI;

struct V {
   VI v;

   V(){std::cout <<"dc" << std::endl;}

   virtual ~V(){std::cout <<"dd " << v.size()<< std::endl;}

   V(V const & rh) : v(rh.v) {
     std::cout <<"cc" << std::endl;
   }

   V(size_t n, double d) : v(n,d){} 


   V & operator=(V const &rh) {
     std::cout <<"ac" << std::endl;
     V tmp(rh);
     v.swap(tmp.v);
     return *this;
  }

#if defined( __GXX_EXPERIMENTAL_CXX0X__)

   V(V && rh) : v(std::move(rh.v)) {
     std::cout <<"rc" << std::endl;
   }

   V & operator=(V && rh) {
     std::cout <<"ar" << std::endl;
     std::swap(rh.v,v);
     return *this;
  }

#else

  void swap(V & rh) {
    std::cout <<"V::swap" << std::endl;
    std::swap(rh.v,v);
  }


#endif

};


struct A : public V {
  A(size_t n, double d) : V(n,d){}

};

/*
inline
void swap(V & lh, V & rh) {
    std::cout <<"::swap" << std::endl;
    std::swap(lh.v,rh.v);
}
*/

#ifdef BYVALUE
inline bool operator<(V rh, V lh) {
#else
 inline bool operator<(V const& rh, V const& lh) {
#endif
  return rh.v[0]<lh.v[0];
}


template<typename T>
void go() {

   std::vector<T> vvs;
   std::cout << "push_back " << std::endl;
   vvs.push_back(T(50,0.));
   for (int i=1;i<5; ++i) 
     vvs.push_back(T(100*i,i));
   std::cout << "push_front " << std::endl;
   vvs.insert(vvs.begin(),T(300,1.));


#if defined( __GXX_EXPERIMENTAL_CXX0X__)

   auto vov = std::bind(&T::v,std::placeholders::_1);
   vov(vvs[0]).size();


   auto myless = std::bind<bool>(std::less<VI>(),
               std::bind<VI const&>(&V::v,std::placeholders::_1),
               std::bind<VI const&>(&V::v,std::placeholders::_2)
               );

   std::cout << ( myless(vvs[0],vvs[2]) ? "less" : "greater" ) << std::endl;
#endif

   std::cout << "shuffle " << std::endl;
   std::random_shuffle(vvs.begin(),vvs.end());

   std::cout << "sort " << std::endl;
   std::sort(vvs.begin(),vvs.end());

#if defined( __GXX_EXPERIMENTAL_CXX0X__)
   std::cout << "sort myless" << std::endl;
   std::sort(vvs.begin(),vvs.end(), myless);
#endif

   std::cout << "stable sort " << std::endl;
   std::stable_sort(vvs.begin(),vvs.end());

#if defined( __GXX_EXPERIMENTAL_CXX0X__)
   std::cout << "stable sort myless" << std::endl;
   std::stable_sort(vvs.begin(),vvs.end(), myless);
#endif

   {
     std::cout << "swap " << std::endl;
     T v(5,3.);
     std::swap(v,vvs[3]);
     std::cout << "swap done" << std::endl;

   }

   for (int i=1;i<vvs.size(); ++i)
     std::cout << vvs[i].v.size() << ", ";
  std::cout << "\nthe end\n" << std::endl;
}

int main() {
  go<V>();
  go<A>();
  return 0;
}

[Bug libstdc++/48038] stable_sort problem with C++0x and comparator by value

[redi at gcc dot gnu.org]

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

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-03-09 09:30:17 UTC ---
I will analyse this properly asap, but there are a few things that look odd in
your example. Why does your move assignment do a swap not a move?

[Bug libstdc++/48038] stable_sort problem with C++0x and comparator by value

[vincenzo.innocente at cern dot ch]

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

--- Comment #2 from vincenzo Innocente <vincenzo.innocente at cern dot ch> 2011-03-09 09:40:33 UTC ---
Thanks for the quick answer.

On 9 Mar, 2011, at 10:30 AM, redi at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48038
> 
> --- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-03-09 09:30:17 UTC ---
> I will analyse this properly asap, but there are a few things that look odd in
> your example. Why does your move assignment do a swap not a move?
> 
Most probably for symmetry w.r.t. the "copy" assignment.
In any case this is "test code" I started to write long ago trying several
variants (move, forward, swap)
I'm sure it is not "optimized" for the current compiler, so please feel free to
suggest the best idiom to use in each case.

     vincenzo

> -- 
> Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
> ------- You are receiving this mail because: -------
> You reported the bug.

[Bug libstdc++/48038] stable_sort problem with C++0x and comparator by value

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-03-09 09:42:25 UTC ---
(In reply to comment #0)
> 
> #ifdef BYVALUE
> inline bool operator<(V rh, V lh) {
> #else
>  inline bool operator<(V const& rh, V const& lh) {
> #endif
>   return rh.v[0]<lh.v[0];

Changing this to use vector::at() results in an out_of_range exception

[Bug libstdc++/48038] stable_sort problem with C++0x and comparator by value

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-03-09 09:47:33 UTC ---
replacing the swap in the move assignment doesn't change anything, so ignore my
comment on that, still looking...

[Bug libstdc++/48038] stable_sort problem with C++0x and comparator by value

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-03-09 10:24:42 UTC ---
slightly reduced ...

#include <vector>
#include <iostream>
#include<algorithm>

typedef std::vector<double> VI;

struct V {
   VI v;

   V(){std::cout <<"dc" << std::endl;}

   ~V(){std::cout <<"dd " << v.size()<< std::endl;}

   V(V const & rh) : v(rh.v) {
     std::cout <<"cc" << std::endl;
   }

   V(size_t n, double d) : v(n,d){} 


   V & operator=(V const &rh) {
     std::cout <<"ac" << std::endl;
     V tmp(rh);
     v.swap(tmp.v);
     return *this;
  }

   V(V && rh) : v(std::move(rh.v)) {
     std::cout <<"rc" << std::endl;
   }

   V & operator=(V && rh) {
     std::cout <<"ar" << std::endl;
     v = std::move(rh.v);
     return *this;
  }

};


inline bool operator<(V lh, V rh) {
  return lh.v.at(0) < rh.v.at(0);
}


int main()
{
   std::vector<V> vvs;
   vvs.push_back(V(1, 0.));
   vvs.push_back(V(1, 1.));
   vvs.insert(vvs.begin(),V(1, 2.));

   std::stable_sort(vvs.begin(), vvs.end());

}

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.03.09 11:11:23
                 CC|                            |paolo.carlini at oracle dot
                   |                            |com
            Summary|stable_sort problem with    |[C++0x] stable_sort problem
                   |C++0x and comparator by     |with C++0x and comparator
                   |value                       |by value
     Ever Confirmed|0                           |1

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-03-09 11:11:23 UTC ---
#include <algorithm>
#include <assert.h>

struct V
{
    int val;
    bool ok;

    V(int v) : val(v), ok(true) { } 

    V(V const & rh) : val(rh.val), ok(rh.ok) {
        assert(rh.ok);
    }

    V & operator=(V const &rh) {
        assert(rh.ok);
        val = rh.val;
        ok = rh.ok;
        return *this;
    }

    V(V && rh) : val(rh.val), ok(rh.ok) {
        assert(rh.ok);
        rh.ok = false;
    }

    V & operator=(V && rh) {
        assert(rh.ok);
        val = rh.val;
        rh.ok = false;
        return *this;
    }

};


inline bool operator<(V lh, V rh) {
  assert(rh.ok);
  assert(lh.ok);
  return lh.val < rh.val;
}


int main()
{
   V vvs[] = { 2, 0 };

   std::stable_sort(vvs, vvs+2);
}

The first element has ok=false after constructing the Temporary_buffer in
std::stable_sort, because __uninitialized_construct_buf_dispatch::__ucr uses
_GLIBCXX_MOVE which leaves vvs[0] in a moved-from state

Paolo, could you take a look?

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[paolo.carlini at oracle dot com]

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

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

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

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 11:18:02 UTC ---
Let's ask first Chris, he invented that logic.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-03-09 11:18:09 UTC ---
N.B. that last testcase still fails if operator< takes its arguments by
reference, the problem is not caused by taking the args by value, that just
made it show up in the original example

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[chris at bubblescope dot net]

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

--- Comment #9 from Chris Jefferson <chris at bubblescope dot net> 2011-03-09 11:28:13 UTC ---
Just to say, I am looking at this. Thanks for the small test case.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[paolo.carlini at oracle dot com]

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

--- Comment #10 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 11:29:22 UTC ---
Of course we already have testcases using the checked __gnu_test::rvalstruct.
We should figure out first what's special here.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[paolo.carlini at oracle dot com]

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

--- Comment #11 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 11:30:06 UTC ---
Thanks a lot Chris, it would be nice if we could resolve it in time for 4.6.0.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[vincenzo.innocente at cern dot ch]

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

--- Comment #12 from vincenzo Innocente <vincenzo.innocente at cern dot ch> 2011-03-09 11:39:24 UTC ---
On 9 Mar, 2011, at 12:30 PM, paolo.carlini at oracle dot com wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48038
> 
> --- Comment #11 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 11:30:06 UTC ---
> Thanks a lot Chris, it would be nice if we could resolve it in time for 4.6.0.
> 
It would be critical for us.
We need 4.6 for other reasons (for instance real support of AVX).
stable_sort not working (and pontentially other subbtle bugs in "move")   makes
it unusable for our scopes.

Thanks for the effort you all are putting in resolving this issue.
We are ready to test a new snapshot of the compiler as soon as posted.

   vincenzo

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[redi at gcc dot gnu.org]

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

--- Comment #13 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-03-09 11:43:00 UTC ---
gah - there was a bug in my reduced testcase, the move assignment operator
should have done:
      ok = rh.ok;
that was missing which is why Temporary_buffer left the first element !ok

The logic in __ucr is ok, sorry!

This one still fails (and only if the operator< takes args by value)

#include <algorithm>
#include <assert.h>

struct V
{
    int val;
    bool ok;

    V(int v) : val(v), ok(true) { } 

    V(V const & rh) : val(rh.val), ok(rh.ok) {
        // assert(rh.ok);
    }

    V & operator=(V const &rh) {
        // assert(rh.ok);
        val = rh.val;
        ok = rh.ok;
        return *this;
    }

    V(V && rh) : val(rh.val), ok(rh.ok) {
        // assert(rh.ok);
        rh.ok = false;
    }

    V & operator=(V && rh) {
        // assert(rh.ok);
        val = rh.val;
        ok = rh.ok;
        rh.ok = false;
        return *this;
    }

};


inline bool operator<(V lh, V rh) {
  assert(rh.ok);
  assert(lh.ok);
  return lh.val < rh.val;
}


int main()
{
   V vvs[] = { 2, 0, 1 };

   std::stable_sort(vvs, vvs+3);
}

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[chris at bubblescope dot net]

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

--- Comment #14 from Chris Jefferson <chris at bubblescope dot net> 2011-03-09 11:51:24 UTC ---
Ah yes, I see the problem now.

The problem is to do with using move_iterator. When we compare two values which
we dereference from a move_iterator, then we end up "moving" into the
comparator, which breaks things.

Hmm.. to be honest, this seems like a fairly serious practical flaw in
move_iterator, removing most of the practical reasons for it's presence in the
standard.

I'm having a very quick think about the best way to fix this. Will report back
shortly.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[paolo.carlini at oracle dot com]

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

--- Comment #15 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 11:55:05 UTC ---
hum, if that is confirmed, we should also quickly audit the other uses of
move_iterator as implementation detail, we have a few, not many.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[paolo.carlini at oracle dot com]

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

--- Comment #16 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 12:46:07 UTC ---
By the way, as a note to Vincenzo, in general I don't really see the point of
comparators taking the arguments by value, thus ruling out move-only types,
among other issues (that clearly shows up in other areas of C++0x). In other
terms, I don't see the temporary workaround for this issue as a proper
workaround, more as a best practice ;)

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[chris at bubblescope dot net]

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

--- Comment #17 from Chris Jefferson <chris at bubblescope dot net> 2011-03-09 13:34:22 UTC ---
Created attachment 23599
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=23599
Patch to make stable_sort work with comparitors that take by value.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[chris at bubblescope dot net]

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

--- Comment #18 from Chris Jefferson <chris at bubblescope dot net> 2011-03-09 13:34:51 UTC ---
Just to update:

I have checked other users of MOVE_ITERATOR (there are only two) and they
appear fine, as they do not use a comparator.

Attached is an initial patch. Very sorry if the formatting (particular tabs)
are off, I am using a different texteditor to normal and am having trouble
configuring correctly.

This patch might look quite long but it is actually fairly minimal.

Basically we introduce methods __move_merge_backward and __move_merge, which
act similarly to merge but move values. We call the comparitor methods without
any moving, so they behave themselves.

__merge_backward was only ever used with arguments that move, so I have renamed
it to __move_merge_backward for clarity and changed the places it is called.
Also introduce __move_merge which is identical to std::merge, except it moves
values into place rather than copies them.

Then fix all places which call merge or __merge_backward with MOVE_ITERATORS to
use the new methods.

Finally, there is a little testcase.


As a sanity check, I would like to make sure that other types (the other sorts
being the obvious target) also work correctly. I can't imagine why they
wouldn't, but I'm very suprised this broke!

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[chris at bubblescope dot net]

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

--- Comment #19 from Chris Jefferson <chris at bubblescope dot net> 2011-03-09 13:35:48 UTC ---
Ignore that patch, there is a problem with it (tester wasn't working properly).
Sorry.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[chris at bubblescope dot net]

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

Chris Jefferson <chris at bubblescope dot net> changed:

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

--- Comment #20 from Chris Jefferson <chris at bubblescope dot net> 2011-03-09 15:25:19 UTC ---
Created attachment 23602
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=23602
Stable sort patch with testcases

Corrected patch.

This is designed the same as the first one, just with some typos fixed.

I have added some more tests for the various sorting algorithms, just so we can
keep an eye on things.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[vincenzo.innocente at cern dot ch]

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

--- Comment #21 from vincenzo Innocente <vincenzo.innocente at cern dot ch> 2011-03-09 15:27:49 UTC ---
On 9 Mar, 2011, at 1:46 PM, paolo.carlini at oracle dot com wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48038
> 
> --- Comment #16 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 12:46:07 UTC ---
> By the way, as a note to Vincenzo, in general I don't really see the point of
> comparators taking the arguments by value, thus ruling out move-only types,
> among other issues (that clearly shows up in other areas of C++0x). In other
> terms, I don't see the temporary workaround for this issue as a proper
> workaround, more as a best practice ;)
> 
The bug showed up initially in a real-software use case were we use a vector of
smart pointer which are typically handled by value.
I then resued an old test of mine to fast prove that the issue was in gcc 4.6.
I will try to build an example using std::shared_ptr  (ours are boost intrusive
shared pointers!)
if is of interest for you.

vincenzo

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[paolo.carlini at oracle dot com]

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

--- Comment #22 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 15:28:55 UTC ---
Great. While I test it locally, can you please prepare a ChangeLog entry? For
sure it's much easier for you to write down which are the new functions, the
renames, etc.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[paolo.carlini at oracle dot com]

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

--- Comment #23 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 15:33:33 UTC ---
Vincenzo no hurry, thankfully Chris has a patch essentially ready (apparently)
and most likely we can fix the problem over the next hours. But in general I'm
unconvinced that it makes sense for a comparison operator of class types to use
pass by value. I would be interested in understanding more about your use case
(maybe in private, whatever you prefer)

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[redi at gcc dot gnu.org]

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

--- Comment #24 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-03-09 15:53:43 UTC ---
Chris, thanks for dealing with this so quickly.
A small nit, in the new testcase I think the move-assignment operator should
use
    ok = rh.ok;
instead of
    ok = true;
to preserve the "moved-from-ness" of the source.
i.e. move-assigning from a moved-from value should make the target have the
same "valid but unspecified state" as the source.
That's certainly what happens if you move-assign from e.g. an empty unique_ptr,
you don't summon up a new pointee out of nowhere!

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[paolo.carlini at oracle dot com]

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

--- Comment #25 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 15:55:38 UTC ---
Jon, I'm doing that here, while reformatting a bit the testcases.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[chris at bubblescope dot net]

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

--- Comment #26 from Chris Jefferson <chris at bubblescope dot net> 2011-03-09 15:58:24 UTC ---
But, the first line of the method (of all the methods) is:

VERIFY(rh.ok);

So, we know it's true. That might still look more consistent/clear.

Very sorry about the formatting. If this can wait until tomorrow I can get to a
computer with a better editor. It's time like this I wish I'd ever bothered to
learn emacs or vim, or some other editor that runs on all machines and won't
mangle tabs.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[paolo.carlini at oracle dot com]

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

--- Comment #27 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 16:00:52 UTC ---
No problem Chris with the trivial formatting, but please spend a minute on the
ChangeLog, if you can. Thanks.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[vincenzo.innocente at cern dot ch]

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

--- Comment #28 from vincenzo Innocente <vincenzo.innocente at cern dot ch> 2011-03-09 16:01:33 UTC ---
The use case was "sloppy" coders (we have hundreds of them, a real resource to
find bugs!)

I personally have no problem with "const &".
Still I remember many tutorials and code examples that suggest that smart
pointers should be passed by value.
"const&" is often perceived as an implementation detail by many non
professional software developers that would like to see those details hidden.
Smart pointers were seen as one of the way to hide memory management from them. 
Move semantics gives new opportunities to move optimization away from user
code: this is one of the reason we are pushing C++0x and we would really like
to be usable now.

vincenzo


here is the code for the shared pointer.

#include<memory>
#include<vector>
#include<functional>

#include<iostream>
#include<algorithm>


struct A {
  A(int ii=-1) : i(ii){}
  int i;
};

typedef std::shared_ptr<A> Aptr;

struct Aless {
  bool operator()(Aptr lh, Aptr rh) {
    return lh->i < rh->i;
  }
};

int main() {

  std::vector<Aptr> v;
  v.push_back(Aptr(new A(2)));
  v.push_back(Aptr(new A(0)));
  v.push_back(Aptr(new A(1)));
  v.push_back(v[1]);

  for (auto p=v.begin(); p!=v.end(); ++p)
    std::cout <<  (*p)->i << " ";
  std::cout << std::endl;


  std::stable_sort(v.begin(),v.end(),Aless());

  for (auto p=v.begin(); p!=v.end(); ++p)
    std::cout <<  (*p)->i << " ";
  std::cout << std::endl;

}

On 9 Mar, 2011, at 4:33 PM, paolo.carlini at oracle dot com wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48038
> 
> --- Comment #23 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 15:33:33 UTC ---
> Vincenzo no hurry, thankfully Chris has a patch essentially ready (apparently)
> and most likely we can fix the problem over the next hours. But in general I'm
> unconvinced that it makes sense for a comparison operator of class types to use
> pass by value. I would be interested in understanding more about your use case
> (maybe in private, whatever you prefer)
> 
> -- 
> Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
> ------- You are receiving this mail because: -------
> You reported the bug.

--
Il est bon de suivre sa pente, pourvu que ce soit en montant. 
A.G.
http://www.flickr.com/photos/vin60/1320965757/

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[chris at bubblescope dot net]

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

--- Comment #29 from Chris Jefferson <chris at bubblescope dot net> 2011-03-09 16:07:15 UTC ---
Created attachment 23604
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=23604
Changelog for stable sort change

Changelog

I've put Jonathan in here, because part of the test case is his example,
copy+pasted.

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[paolo at gcc dot gnu.org]

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

--- Comment #30 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> 2011-03-09 18:30:16 UTC ---
Author: paolo
Date: Wed Mar  9 18:30:11 2011
New Revision: 170827

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

    * testsuite/util/testsuite_rvalref.h: Minor tweaks.

2011-03-09  Jonathan Wakely  <redi@gcc.gnu.org>
        Chris Jefferson  <chris@bubblescope.net>
        Paolo Carlini  <paolo.carlini@oracle.com>

    * testsuite/util/testsuite_rvalref.h (rvalstruct_compare_by_value):
    New.
    * testsuite/25_algorithms/sort_heap/check_compare_by_value.cc:
    Likewise.
    * testsuite/25_algorithms/partial_sort/check_compare_by_value:
    Likewise.
    * testsuite/25_algorithms/stable_sort/check_compare_by_value.cc:
    Likewise.
    * testsuite/25_algorithms/sort/check_compare_by_value: Likewise.

2011-03-09  Chris Jefferson  <chris@bubblescope.net>

    PR libstdc++/48038
    * include/bits/stl_algo.h (__merge_backward): Rename to
    __move_merge_backward and change to always move rather than copy.
    (__move_merge): New function similar to std::merge except values
    are moved instead of copied.
    (__merge_adaptive, __merge_sort_loop): Change from using std::merge
    and __merge_backward to __move_merge and __move_merge_backward.

Added:
   
trunk/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc
    trunk/libstdc++-v3/testsuite/25_algorithms/sort/check_compare_by_value.cc
   
trunk/libstdc++-v3/testsuite/25_algorithms/sort_heap/check_compare_by_value.cc
   
trunk/libstdc++-v3/testsuite/25_algorithms/stable_sort/check_compare_by_value.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_algo.h
    trunk/libstdc++-v3/testsuite/util/testsuite_rvalref.h

[Bug libstdc++/48038] [C++0x] stable_sort problem with C++0x and comparator by value

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.6.0
           Severity|critical                    |normal

--- Comment #31 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-09 18:33:31 UTC ---
Done.