`flat_map.equal_range` hard error when `Compare` is not a `std::relation`

[Quuxplusone]

https://godbolt.org/z/jTGz5sTPP

#include <cassert>
#include <flat_map>
#include <string>

struct StartsWith {
  explicit StartsWith(char ch) : lower_(1, ch), upper_(1, ch+1) {}
  struct Less {
    using is_transparent = void;
    bool operator()(const std::string& a, const std::string& b) const { return a < b; }
    bool operator()(const StartsWith& a, const std::string& b) const { return a.upper_ <= b; }
    bool operator()(const std::string& a, const StartsWith& b) const { return a < b.lower_; }
    //bool operator()(const StartsWith& a, const StartsWith& b) const;
  };
private:
  std::string lower_;
  std::string upper_;
};

int main() {
  using M = std::flat_map<std::string, int, StartsWith::Less>;
  M m = { {"alpha", 1}, {"beta", 2}, {"epsilon", 3}, {"eta", 4}, {"gamma", 5} };
  auto begin = m.begin();
  assert(m.equal_range(StartsWith('b')) == std::pair(begin+1, begin+2));
}

libc++ trunk complains:

__flat_map/flat_map.h:1035:19: error: no matching function for call to object of type 'const __lower_bound'
 1035 |     auto __it   = ranges::lower_bound(__self.__containers_.keys, __key, __self.__compare_);
      |                   ^~~~~~~~~~~~~~~~~~~

Ultimately because:

__concepts/invocable.h:34:29: note: because 'invocable<StartsWith::Less &, StartsWith &, StartsWith &>' evaluated to false
   34 | concept regular_invocable = invocable<_Fn, _Args...>;
      |                             ^

But [associative.reqmts] doesn't seem to require that any value c of type X::key_compare should model std::regular_invocable — it requires merely that expressions such as c(x, kx) and c(kx, x) should be well-formed, and that c should induce a strict weak ordering.

Uncommenting the member function operator()(const StartsWith& a, const StartsWith& b) above makes the test compile; but that shouldn't be necessary, as flat_map never has any reason to compare one StartsWith object against another.

[frederick-vs-ja]

Looks like that ranges::{lower,upper}_bound are overconstrained. LWG4171 is somehow related - where I think the real issue is that ranges::for_each(_n) are overconstrained.

[Quuxplusone]

@frederick-vs-ja: It has also been noted (now that array vs. array comparisons are ill-formed in C++26) that

  std::string_view a[2] = {"two", "four"};
  auto pos = ranges::find(a, "four");

no longer compiles, because equality_comparable_with<string_view&, const char(&)[5]> is now false, because const char(&)[5] is no longer comparable with itself. But nobody there ever tries to compare a const char(&)[5] with itself! The concept is simply over-constrained.

This issue has the same shape... except that in the equality_comparable_with case the paper standard requires the bad behavior (and therefore needs amending), whereas in this flat_map.equal_range case I believe libc++ is violating the paper standard by adding an over-constraint that isn't present on paper.

[frederick-vs-ja]

because equality_comparable_with<string_view&, const char(&)[5]> is now false

Oh. This doesn't seem the exact reason, because ranges algorithms don't use equality_comparable_with (or totally_ordered_with/three_way_comparable_with).

They eventually use the relation concept which is symmetrical for both type arguments. Perhaps we should introduce weak-relation, weak-strict-order, and weak-equivalence-relation, which don't subsume predicate<R, U, U>, to constrain some algorithms more precisely.

[Quuxplusone]

This doesn't seem the exact reason

We might be talking past each other here. :) I didn't mean that this issue (flat_map::equal_range) and the snippet above (ranges::find) have exactly the same mechanical cause: you're right, they have two different mechanical causes. But they are roughly the same "shape" philosophically.

• This issue: libc++ has a bug, in which their implementation of flat_map::equal_range accidentally requires that Compare satisfy std::relation. (The paper standard doesn't require this; it's a libc++ bug.) The effect of libc++'s extra requirement is that libc++ rejects the code because StartsWith::Less cannot compare two StartsWith objects against each other. The code never tries to pass two StartsWith objects to StartsWith::Less, but it's rejected anyway.

• The ranges::find issue: The paper standard has a defect, in which std::equality_comparable_with<T, U> requires that U also be equality-comparable against U. The effect of the paper standard's requirement is that all vendors in C++26 reject the ranges::find code because two char[5] objects cannot be compared against each other. The code never tries to compare two char[5] objects against each other, but it's rejected anyway.

Different mechanical root causes. Same philosophical root cause, namely, the addition of "moralizing requirements" prevent a sensible use-case from compiling. In this issue the "moralizing requirement" snuck in by accident (libc++ accidentally relying on std::relation when the paper standard doesn't allow that); in the ranges::find issue the "moralizing requirement" was deliberately designed in range-v3 and is only biting us now, in C++26, due to further language evolution in the meantime.

[frederick-vs-ja]

• The ranges::find issue: The paper standard has a defect, in which std::equality_comparable_with<T, U> requires that U also be equality-comparable against U. The effect of the paper standard's requirement is that all vendors in C++26 reject the ranges::find code because two char[5] objects cannot be compared against each other. The code never tries to compare two char[5] objects against each other, but it's rejected anyway.

Oops. You're right. I missed that the default comparator ranges::equal_to requires std::equality_comparable_with<T, U>. It seems that the validity of ranges::equal_to{}(t, u) essentially requires both ranges::equal_to{}(t, t) and ranges::equal_to{}(u, u) to be valid, which is not always desired. Perhaps the operator() should be constrained by weakly-equality-comparable-with...

[Quuxplusone]

Perhaps the operator() should be constrained by weakly-equality-comparable-with...

FWIW, yes, I'd love to see that direction taken. Are you interested in pursuing that at the level of a WG21 proposal?