[PATCH] PR libstdc++/90105 make forward_list::sort stable

[PATCH] PR libstdc++/90105 make forward_list::sort stable

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 790 bytes --]

While testing the fix I also discovered that operator== assumes the
elements are comparable with operator!= which is not required.

	PR libstdc++/90105
	* include/bits/forward_list.h (operator==): Do not use operator!= to
	compare elements.
	(forward_list<T, A>::sort(Comp)): When elements are equal take the one
	earlier in the list, so that sort is stable.
	* testsuite/23_containers/forward_list/operations/90105.cc: New test.
	* testsuite/23_containers/forward_list/comparable.cc: Test with
	types that meet the minimum EqualityComparable and LessThanComparable
	requirements. Remove irrelevant comment.

Tested powerpc64le-linux.

I'm surprised nobody has noticed either of these bugs before! I think
this is safe for stage 4, and for backporting to active branches. Any
objections?



[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 5273 bytes --]

commit 2618f400ea46ce881c056543457daa33b3141e7c
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Apr 16 20:37:57 2019 +0100

    PR libstdc++/90105 make forward_list::sort stable
    
    While testing the fix I also discovered that operator== assumes the
    elements are comparable with operator!= which is not required.
    
            PR libstdc++/90105
            * include/bits/forward_list.h (operator==): Do not use operator!= to
            compare elements.
            (forward_list<T, A>::sort(Comp)): When elements are equal take the one
            earlier in the list, so that sort is stable.
            * testsuite/23_containers/forward_list/operations/90105.cc: New test.
            * testsuite/23_containers/forward_list/comparable.cc: Test with
            types that meet the minimum EqualityComparable and LessThanComparable
            requirements. Remove irrelevant comment.

diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index 4fac52a8438..088111e3330 100644
--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -399,7 +399,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       auto __iy = __ly.cbegin();
       while (__ix != __lx.cend() && __iy != __ly.cend())
 	{
-	  if (*__ix != *__iy)
+	  if (!(*__ix == *__iy))
 	    return false;
 	  ++__ix;
 	  ++__iy;
@@ -469,9 +469,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 			__p = static_cast<_Node*>(__p->_M_next);
 			--__psize;
 		      }
-		    else if (__comp(*__p->_M_valptr(), *__q->_M_valptr()))
+		    else if (!__comp(*__q->_M_valptr(), *__p->_M_valptr()))
 		      {
-			// First node of p is lower; e must come from p.
+			// First node of q is not lower; e must come from p.
 			__e = __p;
 			__p = static_cast<_Node*>(__p->_M_next);
 			--__psize;
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc b/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
index cd921b7bc6b..252d9b5a423 100644
--- a/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
@@ -17,15 +17,11 @@
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.
 
-
-// NOTE: This makes use of the fact that we know how moveable
-// is implemented on list (via swap). If the implementation changed
-// this test may begin to fail.
-
 #include <forward_list>
 #include <testsuite_hooks.h>
 
-int main()
+void
+test01()
 {
   std::forward_list<double> a = {0.0, 1.0, 2.0, 3.0, 4.0};
   std::forward_list<double> b = {0.0, 1.0, 2.0, 3.0, 4.0, 5.0};
@@ -43,6 +39,40 @@ int main()
   VERIFY((b >  a) == true);
   VERIFY((b >= a) == true);
   VERIFY((b <= a) == false);
-
-  return 0;
+}
+
+void
+test02()
+{
+  // The EqualityComparable requirements only require ==
+  struct X {
+    bool operator==(const X&) const { return true; }
+  };
+
+  std::forward_list<X> a(2);
+  const auto b = a;
+  VERIFY( a == b );
+}
+
+void
+test03()
+{
+  // The LessThanComparable requirements only require <
+  struct X {
+    bool operator<(const X&) const { return false; }
+  };
+
+  std::forward_list<X> a(2);
+  const auto b = a;
+  VERIFY( !(a < b) );
+  VERIFY( !(a > b) );
+  VERIFY( a <= b );
+  VERIFY( a >= b );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
 }
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc b/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc
new file mode 100644
index 00000000000..3c1478e2e34
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc
@@ -0,0 +1,60 @@
+// Copyright (C) 2019 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+
+#include <forward_list>
+#include <testsuite_hooks.h>
+
+// PR libstdc++/90105 - std::forward_list::sort() is not "stable"
+
+struct X
+{
+  int key;
+  int val;
+};
+
+bool operator<(const X& l, const X& r)
+{ return l.key < r.key; }
+
+bool operator==(const X& l, const X& r)
+{ return l.key == r.key && l.val == r.val; }
+
+void
+test01()
+{
+  std::forward_list<X> l{ {1, 1}, {2, 2}, {1, 3}, {0, 4}, {2, 5}, {0, 6} };
+  l.sort();
+  std::forward_list<X> exp{ {0, 4}, {0, 6}, {1, 1}, {1, 3}, {2, 2}, {2, 5} };
+  VERIFY( l == exp );
+}
+
+void
+test02()
+{
+  std::forward_list<X> l{ {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6} };
+  const std::forward_list<X> exp = l;
+  l.sort();
+  VERIFY( l == exp );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}

Re: [PATCH] PR libstdc++/90105 make forward_list::sort stable

[Jonathan Wakely]

On 16/04/19 23:16 +0100, Jonathan Wakely wrote:
>While testing the fix I also discovered that operator== assumes the
>elements are comparable with operator!= which is not required.
>
>	PR libstdc++/90105
>	* include/bits/forward_list.h (operator==): Do not use operator!= to
>	compare elements.
>	(forward_list<T, A>::sort(Comp)): When elements are equal take the one
>	earlier in the list, so that sort is stable.
>	* testsuite/23_containers/forward_list/operations/90105.cc: New test.
>	* testsuite/23_containers/forward_list/comparable.cc: Test with
>	types that meet the minimum EqualityComparable and LessThanComparable
>	requirements. Remove irrelevant comment.
>
>Tested powerpc64le-linux.
>
>I'm surprised nobody has noticed either of these bugs before! I think
>this is safe for stage 4, and for backporting to active branches. Any
>objections?

Committed to trunk.