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.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@270427 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 0d5e490befe1a31bfc5dbc8a25ac6b2503be19df..fb35a14e1a978e77285e6cd9f95466ee1bf17bad 100644 (file)
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,5 +1,15 @@
 2019-04-17  Jonathan Wakely  <jwakely@redhat.com>
 
+       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.
+
        * include/std/variant (__detail::__variant::_Traits::_S_copy_assign):
        Do not depend on whether all alternative types are move constructible.
        (__detail::__variant::_Copy_assign_base::operator=): Remove cv-quals

diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index 4fac52a8438663f63894815c6c62745fd5266364..088111e3330e5409738d02e2b8946c6b084aeb1d 100644 (file)
--- 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 cd921b7bc6b216f949c9af68659692de28a71762..252d9b5a423ecbd236abae1579710a72fd4c929b 100644 (file)
--- 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);
+}
+
+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; }
+  };
 
-  return 0;
+  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 (file)
index 0000000..3c1478e
--- /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();
+}