On Fri, Apr 25, 2025 at 12:19 AM Jonathan Wakely <jwak...@redhat.com> wrote:
> 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. > > 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 // < C++17 > > 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. > LGTM with one very small change to comment. > > 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. > --- > > Tested x86_64-linux. > > libstdc++-v3/include/bits/stl_tree.h | 108 +++++++++++++-------------- > 1 file changed, 50 insertions(+), 58 deletions(-) > > diff --git a/libstdc++-v3/include/bits/stl_tree.h > b/libstdc++-v3/include/bits/stl_tree.h > index 6b35f99a25a..c7352093933 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(); } > > + // _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 > + // Enforce this here with a user-friendly message. > + static_assert( > + __is_invocable<const _Compare&, const _Key&, const > _Key&>::value, > + "comparison object must be invocable with two arguments of key > type" > + ); > +# endif // C++17 > This does not match the condition in if, should be C++11 > + return _M_impl._M_key_compare(__k1, __k2); > + } > + > static const _Key& > _S_key(const _Node& __node) > - { > -#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&>{}) > - static_assert( > - is_invocable_v<const _Compare&, const _Key&, const _Key&>, > - "comparison object must be invocable as const"); > -# endif // C++17 > -#endif // C++11 > I checked that _S_key seems to be mostly passed to __M_key_compare. There is one function _M_key or _Auto_node that calls is, but it get passed to M_get_insert_(hint_)?(equal|uniq)_pos, but that function is called _M_comapare. In short, yes, this was duplicate of check. > - > - return _KeyOfValue()(*__node._M_valptr()); > - } > + { 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) > -- > 2.49.0 > >
