libstdc++: Add _M_key_compare helper to associative containers

In r10-452-ge625ccc21a91f3 I noted that we don't have an accessor for
invoking _M_impl._M_key_compare in the associative containers. That
meant that the static assertions to check for valid comparison functions
were squirrelled away in _Rb_tree::_S_key instead. As Jason noted in
https://gcc.gnu.org/pipermail/gcc-patches/2025-April/681436.html this
means that the static assertions fail later than we'd like.

This change adds a new _Rb_tree::_M_key_compare member function which
invokes the _M_impl._M_key_compare function object, and then moves the
static_assert from _S_key into _M_key_compare. Now if the static_assert
fails, that's the first error we get, before the "no match for call" and
and "invalid conversion" errors.

Because the new function is const-qualified, we now treat LWG 2542 as a
DR for older standards, requiring the comparison function to be const
invocable. Previously we only enforced the LWG 2542 rule for C++17 and
later.

I did consider deprecating support for comparisons which aren't const
invocable, something like this:

  // Before LWG 2542 it wasn't strictly necessary for _Compare to be
  // const invocable, if you only used non-const container members.
  // Define a non-const overload for pre-C++17, deprecated for C++11/14.
  #if __cplusplus < 201103L
  bool
  _M_key_compare(const _Key& __k1, const _Key& __k2)
  { return _M_impl._M_key_compare(__k1, __k2); }
  #elif __cplusplus < 201703L
  template<typename _Key1, typename _Key2>
    [[__deprecated__("support for comparison functions that are not "
                     "const invocable is deprecated")]]
    __enable_if_t<
    __and_<__is_invocable<_Compare&, const _Key1&, const _Key2&>,
           __not_<__is_invocable<const _Compare&, const _Key1&, const _Key2&>>>::value,
           bool>
    _M_key_compare(const _Key1& __k1, const _Key2& __k2)
    {
      static_assert(
        __is_invocable<_Compare&, const _Key&, const _Key&>::value,
        "comparison object must be invocable with two arguments of key type"
      );
      return _M_impl._M_key_compare(__k1, __k2);
    }
  #endif

But I decided that this isn't necessary, because we've been enforcing
the C++17 rule since GCC 8.4 and 9.2, and C++17 has been the default
since GCC 11.1. Users have had plenty of time to fix their invalid
comparison functions.

libstdc++-v3/ChangeLog:

	* include/bits/stl_tree.h (_Rb_tree::_M_key_compare): New member
	function to invoke comparison function.
	(_Rb_tree): Use new member function instead of accessing the
	comparison function directly.

Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>

1 files changed, 49 insertions, 57 deletions

diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 6b35f99..6caf937 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1390,27 +1390,25 @@ namespace __rb_tree
       _M_end() const _GLIBCXX_NOEXCEPT
       { return this->_M_impl._M_header._M_base_ptr(); }
 
-      static const _Key&
-      _S_key(const _Node& __node)
-      {
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 2542. Missing const requirements for associative containers
+      template<typename _Key1, typename _Key2>
+	bool
+	_M_key_compare(const _Key1& __k1, const _Key2& __k2) const
+	{
 #if __cplusplus >= 201103L
-	// If we're asking for the key we're presumably using the comparison
-	// object, and so this is a good place to sanity check it.
-	static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
-		      "comparison object must be invocable "
-		      "with two arguments of key type");
-# if __cplusplus >= 201703L
-	// _GLIBCXX_RESOLVE_LIB_DEFECTS
-	// 2542. Missing const requirements for associative containers
-	if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{})
+	  // Enforce this here with a user-friendly message.
 	  static_assert(
-	      is_invocable_v<const _Compare&, const _Key&, const _Key&>,
-	      "comparison object must be invocable as const");
-# endif // C++17
-#endif // C++11
+	    __is_invocable<const _Compare&, const _Key&, const _Key&>::value,
+	    "comparison object must be invocable with two arguments of key type"
+	  );
+#endif
+	  return _M_impl._M_key_compare(__k1, __k2);
+	}
 
-	return _KeyOfValue()(*__node._M_valptr());
-      }
+      static const _Key&
+      _S_key(const _Node& __node)
+      { return _KeyOfValue()(*__node._M_valptr()); }
 
       static const _Key&
       _S_key(_Base_ptr __x)
@@ -1933,7 +1931,7 @@ namespace __rb_tree
 	_M_find_tr(const _Kt& __k) const
 	{
 	  const_iterator __j(_M_lower_bound_tr(__k));
-	  if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
+	  if (__j != end() && _M_key_compare(__k, _S_key(__j._M_node)))
 	    __j = end();
 	  return __j;
 	}
@@ -1955,7 +1953,7 @@ namespace __rb_tree
 	  auto __x = _M_begin();
 	  auto __y = _M_end();
 	  while (__x)
-	    if (!_M_impl._M_key_compare(_S_key(__x), __k))
+	    if (!_M_key_compare(_S_key(__x), __k))
 	      {
 		__y = __x;
 		__x = _S_left(__x);
@@ -1973,7 +1971,7 @@ namespace __rb_tree
 	  auto __x = _M_begin();
 	  auto __y = _M_end();
 	  while (__x)
-	    if (_M_impl._M_key_compare(__k, _S_key(__x)))
+	    if (_M_key_compare(__k, _S_key(__x)))
 	      {
 		__y = __x;
 		__x = _S_left(__x);
@@ -2474,8 +2472,8 @@ namespace __rb_tree
 		 _NodeGen& __node_gen)
       {
 	bool __insert_left = (__x || __p == _M_end()
-			      || _M_impl._M_key_compare(_KeyOfValue()(__v),
-							_S_key(__p)));
+			      || _M_key_compare(_KeyOfValue()(__v),
+						_S_key(__p)));
 
 	_Base_ptr __z =
 	  __node_gen(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr();
@@ -2500,8 +2498,8 @@ namespace __rb_tree
 #endif
     {
       bool __insert_left = (__p == _M_end()
-			    || !_M_impl._M_key_compare(_S_key(__p),
-						       _KeyOfValue()(__v)));
+			    || !_M_key_compare(_S_key(__p),
+					       _KeyOfValue()(__v)));
 
       _Base_ptr __z =
 	_M_create_node(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr();
@@ -2529,7 +2527,7 @@ namespace __rb_tree
       while (__x)
 	{
 	  __y = __x;
-	  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
+	  __x = !_M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
 		_S_left(__x) : _S_right(__x);
 	}
       return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
@@ -2601,7 +2599,7 @@ namespace __rb_tree
 		   const _Key& __k) const
     {
       while (__x)
-	if (!_M_impl._M_key_compare(_S_key(__x), __k))
+	if (!_M_key_compare(_S_key(__x), __k))
 	  __y = __x, __x = _S_left(__x);
 	else
 	  __x = _S_right(__x);
@@ -2617,7 +2615,7 @@ namespace __rb_tree
 		   const _Key& __k) const
     {
       while (__x)
-	if (_M_impl._M_key_compare(__k, _S_key(__x)))
+	if (_M_key_compare(__k, _S_key(__x)))
 	  __y = __x, __x = _S_left(__x);
 	else
 	  __x = _S_right(__x);
@@ -2639,9 +2637,9 @@ namespace __rb_tree
       _Base_ptr __y = _M_end();
       while (__x)
 	{
-	  if (_M_impl._M_key_compare(_S_key(__x), __k))
+	  if (_M_key_compare(_S_key(__x), __k))
 	    __x = _S_right(__x);
-	  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
+	  else if (_M_key_compare(__k, _S_key(__x)))
 	    __y = __x, __x = _S_left(__x);
 	  else
 	    {
@@ -2671,9 +2669,9 @@ namespace __rb_tree
       _Base_ptr __y = _M_end();
       while (__x)
 	{
-	  if (_M_impl._M_key_compare(_S_key(__x), __k))
+	  if (_M_key_compare(_S_key(__x), __k))
 	    __x = _S_right(__x);
-	  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
+	  else if (_M_key_compare(__k, _S_key(__x)))
 	    __y = __x, __x = _S_left(__x);
 	  else
 	    {
@@ -2737,7 +2735,7 @@ namespace __rb_tree
       while (__x)
 	{
 	  __y = __x;
-	  __comp = _M_impl._M_key_compare(__k, _S_key(__x));
+	  __comp = _M_key_compare(__k, _S_key(__x));
 	  __x = __comp ? _S_left(__x) : _S_right(__x);
 	}
       iterator __j = iterator(__y);
@@ -2748,7 +2746,7 @@ namespace __rb_tree
 	  else
 	    --__j;
 	}
-      if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
+      if (_M_key_compare(_S_key(__j._M_node), __k))
 	return _Res(__x, __y);
       return _Res(__j._M_node, _Base_ptr());
     }
@@ -2768,8 +2766,7 @@ namespace __rb_tree
       while (__x)
 	{
 	  __y = __x;
-	  __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
-		_S_left(__x) : _S_right(__x);
+	  __x = _M_key_compare(__k, _S_key(__x)) ? _S_left(__x) : _S_right(__x);
 	}
       return _Res(__x, __y);
     }
@@ -2838,19 +2835,18 @@ namespace __rb_tree
       // end()
       if (__position._M_node == _M_end())
 	{
-	  if (size() > 0
-	      && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
+	  if (size() > 0 && _M_key_compare(_S_key(_M_rightmost()), __k))
 	    return _Res(_Base_ptr(), _M_rightmost());
 	  else
 	    return _M_get_insert_unique_pos(__k);
 	}
-      else if (_M_impl._M_key_compare(__k, _S_key(__position._M_node)))
+      else if (_M_key_compare(__k, _S_key(__position._M_node)))
 	{
 	  // First, try before...
 	  iterator __before(__position._M_node);
 	  if (__position._M_node == _M_leftmost()) // begin()
 	    return _Res(_M_leftmost(), _M_leftmost());
-	  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
+	  else if (_M_key_compare(_S_key((--__before)._M_node), __k))
 	    {
 	      if (!_S_right(__before._M_node))
 		return _Res(_Base_ptr(), __before._M_node);
@@ -2860,13 +2856,13 @@ namespace __rb_tree
 	  else
 	    return _M_get_insert_unique_pos(__k);
 	}
-      else if (_M_impl._M_key_compare(_S_key(__position._M_node), __k))
+      else if (_M_key_compare(_S_key(__position._M_node), __k))
 	{
 	  // ... then try after.
 	  iterator __after(__position._M_node);
 	  if (__position._M_node == _M_rightmost())
 	    return _Res(_Base_ptr(), _M_rightmost());
-	  else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
+	  else if (_M_key_compare(__k, _S_key((++__after)._M_node)))
 	    {
 	      if (!_S_right(__position._M_node))
 		return _Res(_Base_ptr(), __position._M_node);
@@ -2923,18 +2919,18 @@ namespace __rb_tree
       if (__position._M_node == _M_end())
 	{
 	  if (size() > 0
-	      && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
+	      && !_M_key_compare(__k, _S_key(_M_rightmost())))
 	    return _Res(_Base_ptr(), _M_rightmost());
 	  else
 	    return _M_get_insert_equal_pos(__k);
 	}
-      else if (!_M_impl._M_key_compare(_S_key(__position._M_node), __k))
+      else if (!_M_key_compare(_S_key(__position._M_node), __k))
 	{
 	  // First, try before...
 	  iterator __before(__position._M_node);
 	  if (__position._M_node == _M_leftmost()) // begin()
 	    return _Res(_M_leftmost(), _M_leftmost());
-	  else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
+	  else if (!_M_key_compare(__k, _S_key((--__before)._M_node)))
 	    {
 	      if (!_S_right(__before._M_node))
 		return _Res(_Base_ptr(), __before._M_node);
@@ -2950,7 +2946,7 @@ namespace __rb_tree
 	  iterator __after(__position._M_node);
 	  if (__position._M_node == _M_rightmost())
 	    return _Res(_Base_ptr(), _M_rightmost());
-	  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
+	  else if (!_M_key_compare(_S_key((++__after)._M_node), __k))
 	    {
 	      if (!_S_right(__position._M_node))
 		return _Res(_Base_ptr(), __position._M_node);
@@ -2999,8 +2995,7 @@ namespace __rb_tree
     -> iterator
     {
       bool __insert_left = (__x || __p == _M_end()
-			    || _M_impl._M_key_compare(_S_key(__z),
-						      _S_key(__p)));
+			    || _M_key_compare(_S_key(__z), _S_key(__p)));
 
       _Base_ptr __base_z = __z->_M_base_ptr();
       _Node_traits::_S_insert_and_rebalance
@@ -3017,8 +3012,7 @@ namespace __rb_tree
     -> iterator
     {
       bool __insert_left = (__p == _M_end()
-			    || !_M_impl._M_key_compare(_S_key(__p),
-						       _S_key(__z)));
+			    || !_M_key_compare(_S_key(__p), _S_key(__z)));
 
       _Base_ptr __base_z = __z->_M_base_ptr();
       _Node_traits::_S_insert_and_rebalance
@@ -3039,7 +3033,7 @@ namespace __rb_tree
       while (__x)
 	{
 	  __y = __x;
-	  __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
+	  __x = !_M_key_compare(_S_key(__x), _S_key(__z)) ?
 		_S_left(__x) : _S_right(__x);
 	}
       return _M_insert_lower_node(__y, __z);
@@ -3151,8 +3145,7 @@ namespace __rb_tree
     {
       iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));
       return (__j == end()
-	      || _M_impl._M_key_compare(__k,
-					_S_key(__j._M_node))) ? end() : __j;
+	      || _M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -3164,8 +3157,7 @@ namespace __rb_tree
     {
       const_iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));
       return (__j == end()
-	      || _M_impl._M_key_compare(__k,
-					_S_key(__j._M_node))) ? end() : __j;
+	      || _M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -3205,9 +3197,9 @@ namespace __rb_tree
 		|| (__R && __R->_M_color == _S_red))
 	      return false;
 
-	  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
+	  if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
 	    return false;
-	  if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
+	  if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
 	    return false;
 
 	  if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)