Bug 90105 - std::forward_list::sort() is not "stable"
Summary: std::forward_list::sort() is not "stable"
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 7.3.0
: P3 normal
Target Milestone: 7.5
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2019-04-15 18:01 UTC by stoyanovmk
Modified: 2019-05-08 12:20 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2019-04-16 00:00:00


Attachments
Small example to reproduce the issue (344 bytes, text/x-csrc)
2019-04-15 18:01 UTC, stoyanovmk
Details

Note You need to log in before you can comment on or make changes to this bug.
Description stoyanovmk 2019-04-15 18:01:56 UTC
Created attachment 46175 [details]
Small example to reproduce the issue

From: https://en.cppreference.com/w/cpp/container/forward_list/sort

"Note: <snip> This function also differs from std::sort in that it does not require the element type of the forward_list to be swappable, preserves the values of all iterators, and performs a stable sort."

Output of the attached sample program:
```
List before sort:
a  1
b  2
c  1
d  0

List after sort:
d  0
c  1
a  1
b  2
```
Note that (a, 1) comes before (c, 1), but after the sort the order is reversed.

PS: Example used gcc 7.3.0 under Ubutnu 18.04, but the behavior is pretty consistent across versions, including 6.3 and 8.0.
Comment 1 Jonathan Wakely 2019-04-16 19:06:54 UTC
I think this is the fix:

--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -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;
Comment 2 stoyanovmk 2019-04-16 19:24:44 UTC
Tested the fix provided by Jonathan Wakely, I can confirm the fix.

Ran several tests with the included small example and the code where I found the issue in the first place.(In reply to Jonathan Wakely from comment #1)
> I think this is the fix:
> 
> --- a/libstdc++-v3/include/bits/forward_list.tcc
> +++ b/libstdc++-v3/include/bits/forward_list.tcc
> @@ -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;

Tested the fix, I can confirm it works.

Ran several tests with the included small example and the code where I found the issue in the first place.
Comment 3 Jonathan Wakely 2019-04-16 22:32:05 UTC
Patch posted to https://gcc.gnu.org/ml/gcc-patches/2019-04/msg00669.html
Comment 4 Jonathan Wakely 2019-04-17 21:47:55 UTC
Author: redi
Date: Wed Apr 17 21:47:20 2019
New Revision: 270427

URL: https://gcc.gnu.org/viewcvs?rev=270427&root=gcc&view=rev
Log:
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.

Added:
    trunk/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc
      - copied, changed from r270425, trunk/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/forward_list.tcc
    trunk/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
Comment 5 Jonathan Wakely 2019-05-07 15:47:03 UTC
Author: redi
Date: Tue May  7 15:46:32 2019
New Revision: 270965

URL: https://gcc.gnu.org/viewcvs?rev=270965&root=gcc&view=rev
Log:
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.

Backport from mainline
2019-04-17  Jonathan Wakely  <jwakely@redhat.com>

	PR libstdc++/90105
	* include/bits/forward_list.tcc (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.

Added:
    branches/gcc-8-branch/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc
      - copied, changed from r270964, branches/gcc-8-branch/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
Modified:
    branches/gcc-8-branch/libstdc++-v3/ChangeLog
    branches/gcc-8-branch/libstdc++-v3/include/bits/forward_list.tcc
    branches/gcc-8-branch/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
Comment 6 Jonathan Wakely 2019-05-07 15:52:13 UTC
Also fixed for 8.4 now.
Comment 7 Jonathan Wakely 2019-05-08 12:17:57 UTC
Author: redi
Date: Wed May  8 12:17:26 2019
New Revision: 271010

URL: https://gcc.gnu.org/viewcvs?rev=271010&root=gcc&view=rev
Log:
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.

Backport from mainline
2019-04-17  Jonathan Wakely  <jwakely@redhat.com>

	PR libstdc++/90105
	* include/bits/forward_list.tcc (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.

Added:
    branches/gcc-7-branch/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc
      - copied, changed from r271009, branches/gcc-7-branch/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
Modified:
    branches/gcc-7-branch/libstdc++-v3/ChangeLog
    branches/gcc-7-branch/libstdc++-v3/include/bits/forward_list.tcc
    branches/gcc-7-branch/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
Comment 8 Jonathan Wakely 2019-05-08 12:20:20 UTC
Fixed in 9.1, and will be fixed in 8.4 and 7.5 when they get released.