<algorithm>: ranges::inplace_merge doesn't seem to be able to utilize ranges::upper_bound

[hewillk]

#include <algorithm>
#include <vector>

int main() {
  std::vector<int> v;
  auto cmp = [](int&, int&) { return true; };
  std::ranges::sort(v, cmp);
  std::ranges::inplace_merge(v, v.begin(), cmp); // hard error
}

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 as ranges::sort.
The root cause is that inplace_merge uses upper_bound, which then requires Compare to satisfy indirect_strict_weak_order<const T*, I> (note the const here), which is not guaranteed by the constraints of inplace_merge.

[frederick-vs-ja]

The root cause is that inplace_merge uses upper_bound, which then requires Compare to satisfy indirect_strict_weak_order<const T*, I> (note the const here), which is not guaranteed by the constraints of inplace_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.

[hewillk]

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.

[StephanTLavavej]

@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.

[hewillk]

@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.

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?

[StephanTLavavej]

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 ints that are projected to S and then compared as int - it would be clearer if 3 different types were involved).

[frederick-vs-ja]

For the LWG issue part, LWG-3031 seems roughly related.

[hewillk]

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, and Compare 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.

[frederick-vs-ja]

Quoted from LWG-3031:

Similar to the Ranges TS design, the P/R below requires Predicate, BinaryPredicate, and Compare 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.