[Bug libstdc++/82891] New: stable_sort() won't compile with function object that takes parameters by non-const reference

[TonyELewis at hotmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82891

            Bug ID: 82891
           Summary: stable_sort() won't compile with function object that
                    takes parameters by non-const reference
           Product: gcc
           Version: 8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: TonyELewis at hotmail dot com
  Target Milestone: ---

This fails to compile:

~~~
#include <algorithm>
#include <vector>

int main() {
        std::vector<int> a = { 5, 7, 1, 4, 1, 4, 2 };
        std::stable_sort(
                std::begin( a ),
                std::end  ( a ),
                [] (int &x, int &y) { return x < y; }
        );
}
~~~

...but works with std::sort(). The problem is that libstdc++ is trying to call
the function object with a const int (&), which the compiler can't bind a
non-const reference to.

Yet I suspect this code is valid. In point 9 (P896-897) of $25.1 of the C++14
draft at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf, it
says:

> The BinaryPredicate parameter is used whenever an algorithm expects a function object that when applied
> to the result of dereferencing two corresponding iterators or to dereferencing an iterator and type
> T when T is part of the signature returns a value testable as true. In other words, if an algorithm takes
> BinaryPredicate binary_pred as its argument and first1 and first2 as its iterator arguments, it should
> work correctly in the construct binary_pred(*first1, *first2) contextually converted to bool (Clause 4).
> BinaryPredicate always takes the first iterator’s value_type as its first argument, that is, in those cases
> when T value is part of the signature, it should work correctly in the construct binary_pred(*first1,
> value) contextually converted to bool (Clause 4). binary_pred shall not apply any non-constant function
> through the dereferenced iterators.

I'm not versed in standardese but I understand the middle part of this as
saying that an implementation of the standard library should work with any
predicate that can take dereferenced iterators as arguments and can be called
in a bool context (so long as it meets other specific requirements).

The errors on GodBolt are:

> In file included from /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algobase.h:71:0,
>                  from /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/algorithm:61,
>                  from <source>:1:
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Value = const int; _Compare = main()::<lambda(int&, int&)>]':
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algobase.h:959:14:   required from '_ForwardIterator std::__lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:2501:26:   required from 'void std::__merge_without_buffer(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance, _Compare) [with _BidirectionalIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Distance = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:2772:34:   required from 'void std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:5004:28:   required from 'void std::__stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:5075:36:   required from 'void std::stable_sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = main()::<lambda(int&, int&)>]'
> 10 : <source>:10:2:   required from here
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:177:11: error: no match for call to '(main()::<lambda(int&, int&)>) (int&, const int&)'
>   { return bool(_M_comp(*__it, __val)); }
>            ^~~~~~~~~~~~~~~~~~~~~~~~~~~
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:177:11: note: candidate: 'bool (*)(int&, int&)' <conversion>
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:177:11: note:   conversion of argument 3 would be ill-formed:
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:177:11: error: binding reference of type 'int&' to 'const int' discards qualifiers
> 9 : <source>:9:21: note: candidate: 'main()::<lambda(int&, int&)>' <near match>
>    [] (int &x, int &y) { return x < y; }
>                      ^
> 9 : <source>:9:21: note:   conversion of argument 2 would be ill-formed:
> In file included from /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algobase.h:71:0,
>                  from /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/algorithm:61,
>                  from <source>:1:
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:177:11: error: binding reference of type 'int&' to 'const int' discards qualifiers
>   { return bool(_M_comp(*__it, __val)); }
>            ^~~~~~~~~~~~~~~~~~~~~~~~~~~
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = const int; _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = main()::<lambda(int&, int&)>]':
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:2052:14:   required from '_ForwardIterator std::__upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Tp = int; _Compare = __gnu_cxx::__ops::_Val_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:2510:26:   required from 'void std::__merge_without_buffer(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance, _Compare) [with _BidirectionalIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Distance = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:2772:34:   required from 'void std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:5004:28:   required from 'void std::__stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:5075:36:   required from 'void std::stable_sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = main()::<lambda(int&, int&)>]'
> 10 : <source>:10:2:   required from here
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:215:11: error: no match for call to '(main()::<lambda(int&, int&)>) (const int&, int&)'
>   { return bool(_M_comp(__val, *__it)); }
>            ^~~~~~~~~~~~~~~~~~~~~~~~~~~
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:215:11: note: candidate: 'bool (*)(int&, int&)' <conversion>
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:215:11: note:   conversion of argument 2 would be ill-formed:
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:215:11: error: binding reference of type 'int&' to 'const int' discards qualifiers
> 9 : <source>:9:21: note: candidate: 'main()::<lambda(int&, int&)>' <near match>
>    [] (int &x, int &y) { return x < y; }
>                      ^
> 9 : <source>:9:21: note:   conversion of argument 1 would be ill-formed:
> In file included from /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algobase.h:71:0,
>                  from /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/algorithm:61,
>                  from <source>:1:
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:215:11: error: binding reference of type 'int&' to 'const int' discards qualifiers
>   { return bool(_M_comp(__val, *__it)); }
>            ^~~~~~~~~~~~~~~~~~~~~~~~~~~
> Compiler exited with result code 1

On a 6.2.0 version of the library, I have been able to get it to compile
cleanly by switching a few bits of code to perfect forward...

stl_algobase.h

~~~.diff
947c947
<                 const _Tp& __val, _Compare __comp)
---
> 		  _Tp&& __val, _Compare __comp)
959c959
<         if (__comp(__middle, __val))
---
> 	  if (__comp(__middle, forward<_Tp>(__val)))
~~~


stl_algo.h

~~~.diff
2037c2037
<                 const _Tp& __val, _Compare __comp)
---
> 		  _Tp&& __val, _Compare __comp)
2049c2049
<         if (__comp(__val, __middle))
---
> 	  if (__comp(forward<_Tp>(__val), __middle))
~~~