Skip to content

Conversation

philnik777
Copy link
Contributor

@philnik777 philnik777 commented Aug 20, 2025

This patch replaces __can_extract_key with an overload set to try to extract the key. This simplifies the code, since we don't need to have separate overload sets for the unordered and associative containers. It also allows extending the set of extraction cases more easily, since we have a single place to define how the key is extracted.

@philnik777 philnik777 force-pushed the refactor_key_extraction branch 2 times, most recently from 6c47b2d to 3566390 Compare August 21, 2025 07:44
Copy link
Member

@ldionne ldionne left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM with small comments.

@ldionne ldionne marked this pull request as ready for review August 25, 2025 15:40
@ldionne ldionne requested a review from a team as a code owner August 25, 2025 15:40
@llvmbot llvmbot added the libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi. label Aug 25, 2025
@llvmbot
Copy link
Member

llvmbot commented Aug 25, 2025

@llvm/pr-subscribers-libcxx

Author: Nikolas Klauser (philnik777)

Changes

This patch replaces __can_extract_key with an overload set to try to extract the key. This simplifies the code, since we don't need to have separate overload sets for the unordered and associative containers. It also allows extending the set of extraction cases more easily, since we have a single place to define how the key is extracted.


Patch is 40.05 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/154512.diff

11 Files Affected:

  • (modified) libcxx/include/CMakeLists.txt (+1-1)
  • (modified) libcxx/include/__fwd/tuple.h (+6)
  • (modified) libcxx/include/__hash_table (+65-103)
  • (modified) libcxx/include/__tree (+58-141)
  • (removed) libcxx/include/__type_traits/can_extract_key.h (-53)
  • (added) libcxx/include/__utility/try_extract_key.h (+109)
  • (modified) libcxx/include/map (+13-25)
  • (modified) libcxx/include/module.modulemap.in (+1-1)
  • (modified) libcxx/include/set (+3-3)
  • (modified) libcxx/include/tuple (-6)
  • (modified) libcxx/include/unordered_map (+7-11)
diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index c6b87a34a43e9..92cea73081d70 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -792,7 +792,6 @@ set(files
   __type_traits/aligned_storage.h
   __type_traits/aligned_union.h
   __type_traits/alignment_of.h
-  __type_traits/can_extract_key.h
   __type_traits/common_reference.h
   __type_traits/common_type.h
   __type_traits/conditional.h
@@ -933,6 +932,7 @@ set(files
   __utility/small_buffer.h
   __utility/swap.h
   __utility/to_underlying.h
+  __utility/try_extract_key.h
   __utility/unreachable.h
   __variant/monostate.h
   __vector/comparison.h
diff --git a/libcxx/include/__fwd/tuple.h b/libcxx/include/__fwd/tuple.h
index 39ed94d9806e5..b3cac4e2a633d 100644
--- a/libcxx/include/__fwd/tuple.h
+++ b/libcxx/include/__fwd/tuple.h
@@ -26,6 +26,12 @@ struct tuple_element;
 template <class...>
 class tuple;
 
+template <class>
+inline const bool __is_tuple_v = false;
+
+template <class... _Tp>
+inline const bool __is_tuple_v<tuple<_Tp...>> = true;
+
 template <size_t _Ip, class... _Tp>
 struct tuple_element<_Ip, tuple<_Tp...> > {
   using type _LIBCPP_NODEBUG = __type_pack_element<_Ip, _Tp...>;
diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table
index 996ec9fa31ac3..48441fdfdffb2 100644
--- a/libcxx/include/__hash_table
+++ b/libcxx/include/__hash_table
@@ -29,7 +29,6 @@
 #include <__memory/swap_allocator.h>
 #include <__memory/unique_ptr.h>
 #include <__new/launder.h>
-#include <__type_traits/can_extract_key.h>
 #include <__type_traits/copy_cvref.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/invoke.h>
@@ -46,6 +45,7 @@
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <__utility/swap.h>
+#include <__utility/try_extract_key.h>
 #include <limits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -797,40 +797,66 @@ public:
   _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);
   _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
 
-  template <class _Key, class... _Args>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
-
-  template <class... _Args>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) {
-    return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
-  }
-
-  template <class _First,
-            class _Second,
-            __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) {
-    return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s));
-  }
-
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {
-    return __emplace_unique_impl(std::forward<_Args>(__args)...);
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
-    return __emplace_unique_impl(std::forward<_Pp>(__x));
-  }
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
-    return __emplace_unique_key_args(__x, std::forward<_Pp>(__x));
-  }
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
-    return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x));
+    return std::__try_key_extraction<key_type>(
+        [this](const key_type& __key, _Args&&... __args2) {
+          size_t __hash   = hash_function()(__key);
+          size_type __bc  = bucket_count();
+          bool __inserted = false;
+          __next_pointer __nd;
+          size_t __chash;
+          if (__bc != 0) {
+            __chash = std::__constrain_hash(__hash, __bc);
+            __nd    = __bucket_list_[__chash];
+            if (__nd != nullptr) {
+              for (__nd = __nd->__next_;
+                   __nd != nullptr &&
+                   (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
+                   __nd = __nd->__next_) {
+                if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __key))
+                  goto __done;
+              }
+            }
+          }
+          {
+            __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args2)...);
+            if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
+              __rehash_unique(std::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc),
+                                                  size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
+              __bc    = bucket_count();
+              __chash = std::__constrain_hash(__hash, __bc);
+            }
+            // insert_after __bucket_list_[__chash], or __first_node if bucket is null
+            __next_pointer __pn = __bucket_list_[__chash];
+            if (__pn == nullptr) {
+              __pn          = __first_node_.__ptr();
+              __h->__next_  = __pn->__next_;
+              __pn->__next_ = __h.get()->__ptr();
+              // fix up __bucket_list_
+              __bucket_list_[__chash] = __pn;
+              if (__h->__next_ != nullptr)
+                __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
+            } else {
+              __h->__next_  = __pn->__next_;
+              __pn->__next_ = static_cast<__next_pointer>(__h.get());
+            }
+            __nd = static_cast<__next_pointer>(__h.release());
+            // increment size
+            ++size();
+            __inserted = true;
+          }
+        __done:
+          return pair<iterator, bool>(iterator(__nd), __inserted);
+        },
+        [this](_Args&&... __args2) {
+          __node_holder __h        = __construct_node(std::forward<_Args>(__args2)...);
+          pair<iterator, bool> __r = __node_insert_unique(__h.get());
+          if (__r.second)
+            __h.release();
+          return __r;
+        },
+        std::forward<_Args>(__args)...);
   }
 
   template <class... _Args>
@@ -999,8 +1025,8 @@ private:
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);
 
-  template <class _First, class... _Rest>
-  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
+  template <class... _Args>
+  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _Args&&... __args);
 
   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u) {
     __copy_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
@@ -1613,69 +1639,6 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p
   return __node_insert_multi(__cp);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _Key, class... _Args>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
-  size_t __hash   = hash_function()(__k);
-  size_type __bc  = bucket_count();
-  bool __inserted = false;
-  __next_pointer __nd;
-  size_t __chash;
-  if (__bc != 0) {
-    __chash = std::__constrain_hash(__hash, __bc);
-    __nd    = __bucket_list_[__chash];
-    if (__nd != nullptr) {
-      for (__nd = __nd->__next_;
-           __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
-           __nd = __nd->__next_) {
-        if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
-          goto __done;
-      }
-    }
-  }
-  {
-    __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args)...);
-    if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
-      __rehash_unique(std::max<size_type>(
-          2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
-      __bc    = bucket_count();
-      __chash = std::__constrain_hash(__hash, __bc);
-    }
-    // insert_after __bucket_list_[__chash], or __first_node if bucket is null
-    __next_pointer __pn = __bucket_list_[__chash];
-    if (__pn == nullptr) {
-      __pn          = __first_node_.__ptr();
-      __h->__next_  = __pn->__next_;
-      __pn->__next_ = __h.get()->__ptr();
-      // fix up __bucket_list_
-      __bucket_list_[__chash] = __pn;
-      if (__h->__next_ != nullptr)
-        __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
-    } else {
-      __h->__next_  = __pn->__next_;
-      __pn->__next_ = static_cast<__next_pointer>(__h.get());
-    }
-    __nd = static_cast<__next_pointer>(__h.release());
-    // increment size
-    ++size();
-    __inserted = true;
-  }
-__done:
-  return pair<iterator, bool>(iterator(__nd), __inserted);
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class... _Args>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args) {
-  __node_holder __h        = __construct_node(std::forward<_Args>(__args)...);
-  pair<iterator, bool> __r = __node_insert_unique(__h.get());
-  if (__r.second)
-    __h.release();
-  return __r;
-}
-
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class... _Args>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
@@ -1927,15 +1890,14 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&&... __args) {
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _First, class... _Rest>
+template <class... _Args>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest) {
-  static_assert(!__is_hash_value_type<_First, _Rest...>::value, "Construct cannot be called with a hash value type");
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _Args&&... __args) {
+  static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");
   __node_allocator& __na = __node_alloc();
   __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
   std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ __hash);
-  __node_traits::construct(
-      __na, std::addressof(__h->__get_value()), std::forward<_First>(__f), std::forward<_Rest>(__rest)...);
+  __node_traits::construct(__na, std::addressof(__h->__get_value()), std::forward<_Args>(__args)...);
   __h.get_deleter().__value_constructed = true;
   return __h;
 }
diff --git a/libcxx/include/__tree b/libcxx/include/__tree
index a84a0e43d3dda..21a129322a980 100644
--- a/libcxx/include/__tree
+++ b/libcxx/include/__tree
@@ -23,7 +23,6 @@
 #include <__memory/pointer_traits.h>
 #include <__memory/swap_allocator.h>
 #include <__memory/unique_ptr.h>
-#include <__type_traits/can_extract_key.h>
 #include <__type_traits/copy_cvref.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/invoke.h>
@@ -38,6 +37,7 @@
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <__utility/swap.h>
+#include <__utility/try_extract_key.h>
 #include <limits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -900,88 +900,74 @@ public:
       _NOEXCEPT_(__is_nothrow_swappable_v<value_compare>);
 #endif
 
-  template <class _Key, class... _Args>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args&&... __args);
-  template <class _Key, class... _Args>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);
-
-  template <class... _Args>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
-
-  template <class... _Args>
-  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args);
-
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
 
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) {
-    return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
-  }
-
-  template <class _First,
-            class _Second,
-            __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) {
-    return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s));
-  }
-
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {
-    return __emplace_unique_impl(std::forward<_Args>(__args)...);
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
-    return __emplace_unique_impl(std::forward<_Pp>(__x));
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
-    return __emplace_unique_key_args(__x, std::forward<_Pp>(__x));
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
-    return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x));
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) {
-    return __emplace_hint_unique_extract_key(__p, std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
-  }
-
-  template <class _First,
-            class _Second,
-            __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0>
-  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) {
-    return __emplace_hint_unique_key_args(__p, __f, std::forward<_First>(__f), std::forward<_Second>(__s)).first;
+    return std::__try_key_extraction<key_type>(
+        [this](const key_type& __key, _Args&&... __args2) {
+          __end_node_pointer __parent;
+          __node_base_pointer& __child = __find_equal(__parent, __key);
+          __node_pointer __r           = static_cast<__node_pointer>(__child);
+          bool __inserted              = false;
+          if (__child == nullptr) {
+            __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+            __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+            __r        = __h.release();
+            __inserted = true;
+          }
+          return pair<iterator, bool>(iterator(__r), __inserted);
+        },
+        [this](_Args&&... __args2) {
+          __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+          __end_node_pointer __parent;
+          __node_base_pointer& __child = __find_equal(__parent, __h->__get_value());
+          __node_pointer __r           = static_cast<__node_pointer>(__child);
+          bool __inserted              = false;
+          if (__child == nullptr) {
+            __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+            __r        = __h.release();
+            __inserted = true;
+          }
+          return pair<iterator, bool>(iterator(__r), __inserted);
+        },
+        std::forward<_Args>(__args)...);
   }
 
   template <class... _Args>
-  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
-    return __emplace_hint_unique_impl(__p, std::forward<_Args>(__args)...);
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI iterator
-  __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {
-    return __emplace_hint_unique_impl(__p, std::forward<_Pp>(__x));
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI iterator
-  __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
-    return __emplace_hint_unique_key_args(__p, __x, std::forward<_Pp>(__x)).first;
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI iterator
-  __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
-    return __emplace_hint_unique_key_args(__p, __x.first, std::forward<_Pp>(__x)).first;
+  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
+    return std::__try_key_extraction<key_type>(
+        [this, __p](const key_type& __key, _Args&&... __args2) {
+          __end_node_pointer __parent;
+          __node_base_pointer __dummy;
+          __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __key);
+          __node_pointer __r           = static_cast<__node_pointer>(__child);
+          bool __inserted              = false;
+          if (__child == nullptr) {
+            __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+            __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+            __r        = __h.release();
+            __inserted = true;
+          }
+          return pair<iterator, bool>(iterator(__r), __inserted);
+        },
+        [this, __p](_Args&&... __args2) {
+          __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+          __end_node_pointer __parent;
+          __node_base_pointer __dummy;
+          __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__get_value());
+          __node_pointer __r           = static_cast<__node_pointer>(__child);
+          if (__child == nullptr) {
+            __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+            __r = __h.release();
+          }
+          return pair<iterator, bool>(iterator(__r), __child == nullptr);
+        },
+        std::forward<_Args>(__args)...);
   }
 
   template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type_v<_ValueT>, int> = 0>
@@ -1772,42 +1758,6 @@ void __tree<_Tp, _Compare, _Allocator>::__insert_node_at(
   ++__size_;
 }
 
-template <class _Tp, class _Compare, class _Allocator>
-template <class _Key, class... _Args>
-pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
-__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
-  __end_node_pointer __parent;
-  __node_base_pointer& __child = __find_equal(__parent, __k);
-  __node_pointer __r           = static_cast<__node_pointer>(__child);
-  bool __inserted              = false;
-  if (__child == nullptr) {
-    __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
-    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
-    __r        = __h.release();
-    __inserted = true;
-  }
-  return pair<iterator, bool>(iterator(__r), __inserted);
-}
-
-template <class _Tp, class _Compare, class _Allocator>
-template <class _Key, class... _Args>
-pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
-__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
-    const_iterator __p, _Key const& __k, _Args&&... __args) {
-  __end_node_pointer __parent;
-  __node_base_pointer __dummy;
-  __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
-  __node_pointer __r           = static_cast<__node_pointer>(__child);
-  bool __inserted              = false;
-  if (__child == nullptr) {
-    __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
-    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
-    __r        = __h.release();
- ...
[truncated]

@philnik777 philnik777 force-pushed the refactor_key_extraction branch from 3566390 to e50b1bf Compare August 26, 2025 06:54
@philnik777 philnik777 force-pushed the refactor_key_extraction branch from e50b1bf to a03b09d Compare August 26, 2025 08:34
@philnik777 philnik777 merged commit af1f06e into llvm:main Aug 26, 2025
65 of 70 checks passed
@philnik777 philnik777 deleted the refactor_key_extraction branch August 26, 2025 14:27
@boomanaiden154
Copy link
Contributor

I'm seeing LLDB build failures caused by this change. https://lab.llvm.org/staging/#/builders/192/builds/1880

Is someone on the LLDB side able to take a look and fix this? @Michael137?

@Michael137
Copy link
Member

I'm seeing LLDB build failures caused by this change. https://lab.llvm.org/staging/#/builders/192/builds/1880

Is someone on the LLDB side able to take a look and fix this? @Michael137?

Did the pre-merge checks pass?

Let me have a look later today. Can we revert in the meantime if this is making the bots red?

@boomanaiden154
Copy link
Contributor

Did the pre-merge checks pass?

We don't currently run the monorepo wide premerge pipeline on libc++ changes, just the libc++ premerge pipeline. I put up #155188 to get that fixed but wanted one of the libc++ maintainers to take a look before landing it.

Let me have a look later today. Can we revert in the meantime if this is making the bots red?

Yeah. This one I think we can given it's just a refactoring. I'll give @philnik777 a little bit longer otherwise I'll revert.

@philnik777
Copy link
Contributor Author

Did the pre-merge checks pass?

We don't currently run the monorepo wide premerge pipeline on libc++ changes, just the libc++ premerge pipeline. I put up #155188 to get that fixed but wanted one of the libc++ maintainers to take a look before landing it.

Let me have a look later today. Can we revert in the meantime if this is making the bots red?

Yeah. This one I think we can given it's just a refactoring. I'll give @philnik777 a little bit longer otherwise I'll revert.

Sorry, I thought the CI failure was unrelated, since the bootstrapping build was red a few times in the past days and I didn't expect this to impact pretty printers in any way. Feel free to revert for now.

boomanaiden154 added a commit that referenced this pull request Aug 26, 2025
…154512)"

This reverts commit af1f06e.

This is causing some build failures in premerge as some of the LLDB
tests fail.
@boomanaiden154
Copy link
Contributor

72c04bb. Thanks for the quick response.

@Michael137
Copy link
Member

Michael137 commented Aug 26, 2025

Ok had a look at the test failure (TestLibcxxInternalsRecognizer.py). Seems like after this libc++ patch, the backtrace that LLDB prints when stopped inside a std::map comparator is:

(lldb) bt
* thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
  * frame #0: 0x00000001000097e8 a.out`MyKey::operator<(this=0x000000016fdfebbc, other=0x00000001007f5c3c) at main.cpp:70:5
    frame #1: 0x00000001000097c0 a.out`std::__1::less<MyKey>::operator()[abi:se220000](this=0x000000016fdfebf8, __x=0x000000016fdfebbc, __y=0x00000001007f5c3c) at operations.h:357:16
    frame #4: 0x0000000100009224 a.out`std::__1::pair<std::__1::__tree_iterator<std::__1::__value_type<MyKey, int>, std::__1::__tree_node<std::__1::__value_type<MyKey, int>, void*>*, long>, bool> std::__1::__tree<std::__1::__value_type<MyKey, int>, std::__1::__map_value_compare<MyKey, std::__1::pair<MyKey const, int>, std::__1::less<MyKey>, true>, std::__1::allocator<std::__1::pair<MyKey const, int>>>::__emplace_unique[abi:se220000]<MyKey, int>(MyKey&&, int&&)::'lambda'(MyKey const&, MyKey&&, int&&)::operator()(this=0x000000016fdfe9d8, __key=0x000000016fdfebbc, __args2=0x000000016fdfebbc, __args2=0x000000016fdfebb8) at __tree:914:42
    frame #8: 0x0000000100000f54 a.out`std::__1::map<MyKey, int, std::__1::less<MyKey>, std::__1::allocator<std::__1::pair<MyKey const, int>>>::emplace[abi:se220000]<MyKey, int>(this=size=1, __args=0x000000016fdfebbc, __args=0x000000016fdfebb8) at map:1053:20
    frame #9: 0x0000000100000ea0 a.out`test_containers() at main.cpp:78:7
    frame #10: 0x000000010000100c a.out`main at main.cpp:84:3
    frame #11: 0x0000000193ec1d54 dyld`start + 7184

We have a regex that will try to determine which libc++ frames to hide (introduced in #108870). So the test expects following frames to show up in the backtrace:

            "MyKey::operator<(MyKey const&) const": [
                "less",
                "::emplace",
                "test_containers",
            ],

But now we have that lambda operator() in the backtrace which doesn't get hidden.

A quick fix to get this PR unblocked is to adjust the test expectations:

diff --git i/lldb/test/API/lang/cpp/libcxx-internals-recognizer/TestLibcxxInternalsRecognizer.py w/lldb/test/API/lang/cpp/libcxx-internals-recognizer/TestLibcxxInternalsRecognizer.py
index 8efa53bdbf72..aaee45b60819 100644
--- i/lldb/test/API/lang/cpp/libcxx-internals-recognizer/TestLibcxxInternalsRecognizer.py
+++ w/lldb/test/API/lang/cpp/libcxx-internals-recognizer/TestLibcxxInternalsRecognizer.py
@@ -40,6 +40,7 @@ class LibCxxInternalsRecognizerTestCase(TestBase):
             "Callable::operator()(int) const": ["::invoke", "test_invoke"],
             # Containers
             "MyKey::operator<(MyKey const&) const": [
+                "::operator()",
                 "less",
                 "::emplace",
                 "test_containers",

But as a follow-up, I'd like @vogelsgesang to chime in on whether he thinks the regex should be adjusted/whether these lambdas should get hidden (I think we do want to hide those since they are implementation details). TBH I'm not sure why these lambdas don't get hidden. I thought we just hide everything in the __1 namespace..

@Michael137
Copy link
Member

TBH I'm not sure why these lambdas don't get hidden. I thought we just hide everything in the __1 namespace..

Ahh nvm we only hide things that start with __ in the __1 namespace. And since the operator() doesn't start with a __, it's not hidden. We should probably adjust the regex to account for this.

philnik777 added a commit to philnik777/llvm-project that referenced this pull request Aug 27, 2025
philnik777 added a commit to philnik777/llvm-project that referenced this pull request Aug 27, 2025
philnik777 added a commit that referenced this pull request Aug 27, 2025
…#154512)" (#155565)

The original PR has been reverted because of an LLDB test failure. This
patch now works around the test failure by simply allowing the new
symbols to show up in a stack trace.

This reverts commit 72c04bb.

Original commit message:

This patch replaces `__can_extract_key` with an overload set to try to
extract the key. This simplifies the code, since we don't need to have
separate overload sets for the unordered and associative containers. It
also allows extending the set of extraction cases more easily, since we
have a single place to define how the key is extracted.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

5 participants