[Bug libstdc++/57010] New: priority_queue calls self-move-assignment operator

[Bug libstdc++/57010] New: priority_queue calls self-move-assignment operator

[philipp at fb dot com]

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

             Bug #: 57010
           Summary: priority_queue calls self-move-assignment operator
    Classification: Unclassified
           Product: gcc
           Version: 4.7.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: philipp@fb.com


#include <iostream>
#include <queue>

struct A {
  A() { }

  A(const A&) = default;
  A& operator=(const A&) = default;

  A(A&&) = default;
  A& operator=(A&& a) {
    if (this == &a) {
      std::cerr << "?!" << std::endl;
    }
    return *this;
  }

  bool operator<(const A&) const {
    return false;
  }
};

int main() {
  std::priority_queue<A> q;
  q.push(A());
  q.pop();  // prints '?!'
  return 0;
}


std::priority_queue<> calls self-move-assignment when pop() the last element. 
Verified in gcc-4.6.2 and gcc-4.7.1.

[Bug libstdc++/57010] [c++0x] priority_queue<>::pop() calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-04-20 08:25:11 UTC ---
Note that the implementation of priority_queue::push and pop is fully
constrained by the Standard, directly boils down to operations on the
underlying container and std::push_heap and std::pop_heap calls, thus this
can't be an issue with our implementation of std::priority_queue itself.

Looks like the problem in in the implementation of std::pop_heap, eg,
__pop_heap should not be called at all when __last - __first == 0.

[Bug libstdc++/57010] [c++0x] priority_queue<>::pop() calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2013-04-20
         AssignedTo|unassigned at gcc dot       |paolo.carlini at oracle dot
                   |gnu.org                     |com
     Ever Confirmed|0                           |1

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-04-20 10:15:59 UTC ---
Mine. I'm testing something like this:

Index: stl_heap.h
===================================================================
--- stl_heap.h    (revision 198008)
+++ stl_heap.h    (working copy)
@@ -291,8 +291,11 @@
       __glibcxx_requires_valid_range(__first, __last);
       __glibcxx_requires_heap(__first, __last);

-      --__last;
-      std::__pop_heap(__first, __last, __last);
+      if (__last - __first > 1)
+    {
+      --__last;
+      std::__pop_heap(__first, __last, __last);
+    }
     }

   template<typename _RandomAccessIterator, typename _Distance,
@@ -363,8 +366,11 @@
       __glibcxx_requires_non_empty_range(__first, __last);
       __glibcxx_requires_heap_pred(__first, __last, __comp);

-      --__last;
-      std::__pop_heap(__first, __last, __last, __comp);
+      if (__last - __first > 1)
+    {
+      --__last;
+      std::__pop_heap(__first, __last, __last, __comp);
+    }
     }

   /**

[Bug libstdc++/57010] [c++0x] priority_queue<>::pop() calls self-move-assignment operator

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |glisse at gcc dot gnu.org

--- Comment #3 from Marc Glisse <glisse at gcc dot gnu.org> 2013-04-20 10:47:03 UTC ---
(In reply to comment #2)
> Mine. I'm testing something like this:

Thanks.

> @@ -291,8 +291,11 @@

There's this cool diff option called -p that's recommended on the gcc website
;-)

>        __glibcxx_requires_valid_range(__first, __last);
>        __glibcxx_requires_heap(__first, __last);
> 
> -      --__last;
> -      std::__pop_heap(__first, __last, __last);
> +      if (__last - __first > 1)
> +    {
> +      --__last;
> +      std::__pop_heap(__first, __last, __last);
> +    }
>      }

Is that the same as:

      if (first != --__last)
std::__pop_heap(__first, __last, __last);

[Bug libstdc++/57010] [c++0x] priority_queue<>::pop() calls self-move-assignment operator

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|glisse at gcc dot gnu.org   |

--- Comment #4 from Marc Glisse <glisse at gcc dot gnu.org> 2013-04-20 10:49:59 UTC ---
[Gah, firefox has dumb key bindings that send unfinished messages...]

(In reply to comment #3)
> Is that the same as:
> 
>       if (first != --__last)
>         std::__pop_heap(__first, __last, __last);

?

it would save one or two additions.

[Bug libstdc++/57010] [c++0x] priority_queue<>::pop() calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #5 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-04-20 10:55:44 UTC ---
Then we should consistently change the while loops elsewhere, right? Did you
analyze at all why both can't be optimized the same way?

[Bug libstdc++/57010] [c++0x] priority_queue<>::pop() calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

--- Comment #6 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-04-20 11:07:38 UTC ---
By the way, traditionally, for *library* patches we never used -p + I'm
traveling sorry (C++ in Bristol), I barely installed some stuff on this tiny
laptop, I didn't mean to use it to do actual programming.

More to the point, I'm under the impression that preliminarily checking (__last
- __first > 1) is more user friendly as undefined behavior in case __first ==
__last happens to be true. I think we should just do that, consistently with
the existing while loops in the same file, at least to resolve this issue for
4.8.x too. Maybe reconsider later.

[Bug libstdc++/57010] [c++0x] priority_queue<>::pop() calls self-move-assignment operator

[glisse at gcc dot gnu.org]

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

--- Comment #7 from Marc Glisse <glisse at gcc dot gnu.org> 2013-04-20 11:17:27 UTC ---
(In reply to comment #6)
> By the way, traditionally, for *library* patches we never used -p + I'm
> traveling sorry (C++ in Bristol), I barely installed some stuff on this tiny
> laptop, I didn't mean to use it to do actual programming.

I hope it is clear that it wasn't a reproach :-(

> More to the point, I'm under the impression that preliminarily checking (__last
> - __first > 1) is more user friendly as undefined behavior in case __first ==
> __last happens to be true.

We do have __glibcxx_requires_non_empty_range in there, but that's only in some
debug mode I guess. By the way, sort_heap is the only similar while condition I
could see.

> I think we should just do that, consistently with
> the existing while loops in the same file, at least to resolve this issue for
> 4.8.x too. Maybe reconsider later.

Ok.

[Bug libstdc++/57010] [c++0x] priority_queue<>::pop() calls self-move-assignment operator

[glisse at gcc dot gnu.org]

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

--- Comment #8 from Marc Glisse <glisse at gcc dot gnu.org> 2013-04-20 11:25:30 UTC ---
(In reply to comment #6)
> More to the point, I'm under the impression that preliminarily checking (__last
> - __first > 1) is more user friendly as undefined behavior in case __first ==
> __last happens to be true.

Forgot to mention: this version should have the same user-friendliness, use of
!= vs < is mostly orthogonal.

  if (first < --__last)

(but you can stick to your version, I was only proposing an alternative)

[Bug libstdc++/57010] [c++0x] priority_queue<>::pop() calls self-move-assignment operator

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.8.1

--- Comment #9 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-04-22 10:09:49 UTC ---
Fixed mainline and 4.8.1.