Closed hewillk closed 1 week ago
The root cause is that
inplace_merge
usesupper_bound
, which then requiresCompare
to satisfyindirect_strict_weak_order<const T*, I>
(note theconst
here), which is not guaranteed by the constraints ofinplace_merge
.
Pedantically wrong for all three major implementations. Implementations actually call the unconstrained (by possible static_assert
-ing) internal versions instead of ranges::upper_bound
. Although this perfectly indicates that the partial implementation posted on cppreference is currently incorrect.
At the first glance, I thought we should remove const
somewhere. It should be investigated whether additional fix is needed for proxy references.
At the first glance, I thought we should remove
const
somewhere. It should be investigated whether additional fix is needed for proxy references.
Not sure if making _Upper_bound_unchecked
/_Lower_bound_unchecked
accept _Ty&& _Val
instead of const _Ty& _Val
and doing the forwarding internally would fix this.
@barcharcraz and I talked about this at the weekly maintainer meeting. The fact that the Majestic Three implementations all reject this code, and the fact that it seems super pathological/useless for comparison function objects to reject const
arguments, indicates that we need to send this to the LWG and they need to decide what should happen here. Our initial reaction is that the sortable
concept should require const-comparisons to work, in the same way that ranges::upper_bound
is explicitly adding constness when checking for comparability, but mostly we just want the LWG to tell us exactly what should happen here.
@barcharcraz and I talked about this at the weekly maintainer meeting. The fact that the Majestic Three implementations all reject this code, and the fact that it seems super pathological/useless for comparison function objects to reject
const
arguments, indicates that we need to send this to the LWG and they need to decide what should happen here. Our initial reaction is that thesortable
concept should require const-comparisons to work, in the same way thatranges::upper_bound
is explicitly adding constness when checking for comparability, but mostly we just want the LWG to tell us exactly what should happen here.
OK. Let me change the example that is only rejected by MSVC-STL:
#include <algorithm>
#include <vector>
struct S {
operator int();
};
int main() {
std::vector<int> v;
auto cmp = [](const int&, const int&) { return true; };
std::ranges::inplace_merge(v, v.begin(), cmp, [](int) { return S{}; });
}
https://godbolt.org/z/M1z8aaq9s
Could this be considered a library bug?
Yeah, that looks more like a bug to me, since MSVC is alone there (with the nitpicks that a "do nothing" comparator really ought to return false
, and that it's confusing for the range to be int
s that are projected to S
and then compared as int
- it would be clearer if 3 different types were involved).
For the LWG issue part, LWG-3031 seems roughly related.
For the LWG issue part, LWG-3031 seems roughly related.
Quoted from LWG-3031:
Similar to the Ranges TS design, the P/R below requires
Predicate
,BinaryPredicate
, andCompare
to accept all mixes of const and non-const
arguments.
Doesn't this already indicate that this is a bug in the standard library implementation rather than a defect in the standard? The LWG considers these examples should work.
Quoted from LWG-3031:
Similar to the Ranges TS design, the P/R below requires
Predicate
,BinaryPredicate
, andCompare
to accept all mixes of const and non-const
arguments.Doesn't this already indicate that this is a bug in the standard library implementation rather than a defect in the standard? The LWG considers these examples should work.
I didn't know what the paragraph intended to mean. Sortable
in Ranges TS wasn't fundamentally different from the current std::sortable
and accepted non-const-only comparators. But the decision in that paragraph and the final resolution of LWG-3031 imposed stricter requirements on Compare
- which was, IIUC, inconsistent with Ranges TS.
https://godbolt.org/z/soe8sa75q
The above code is rejected by libstdc++, libc++, and MSVC-STL, which shouldn't be because
ranges::inplace_merge
has the same constraint signature asranges::sort
. The root cause is thatinplace_merge
usesupper_bound
, which then requiresCompare
to satisfyindirect_strict_weak_order<const T*, I>
(note theconst
here), which is not guaranteed by the constraints ofinplace_merge
.