Revert "[libc++] Refactor key extraction for __hash_table and __tree (#154512)"

This reverts commit af1f06e41b05c267480f1629dc0fcdf18f3b59f6.

This is causing some build failures in premerge as some of the LLDB
tests fail.

11 files changed, 344 insertions, 268 deletions

diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index 6fd1641..c6b87a3 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -792,6 +792,7 @@ 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
@@ -932,7 +933,6 @@ set(files
   __utility/small_buffer.h
   __utility/swap.h
   __utility/to_underlying.h
-  __utility/try_key_extraction.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 b3cac4e..39ed94d 100644
--- a/libcxx/include/__fwd/tuple.h
+++ b/libcxx/include/__fwd/tuple.h
@@ -26,12 +26,6 @@ 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 91f660d..f0f335a 100644
--- a/libcxx/include/__hash_table
+++ b/libcxx/include/__hash_table
@@ -29,6 +29,7 @@
 #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>
@@ -45,7 +46,6 @@
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <__utility/swap.h>
-#include <__utility/try_key_extraction.h>
 #include <limits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -797,66 +797,40 @@ 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 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)...);
+    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... _Args>
@@ -1025,8 +999,8 @@ private:
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);
 
-  template <class... _Args>
-  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _Args&&... __args);
+  template <class _First, class... _Rest>
+  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
 
   _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>());
@@ -1641,6 +1615,69 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p
 }
 
 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
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) {
@@ -1891,14 +1928,15 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&&... __args) {
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class... _Args>
+template <class _First, class... _Rest>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__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");
+__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");
   __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<_Args>(__args)...);
+  __node_traits::construct(
+      __na, std::addressof(__h->__get_value()), std::forward<_First>(__f), std::forward<_Rest>(__rest)...);
   __h.get_deleter().__value_constructed = true;
   return __h;
 }
diff --git a/libcxx/include/__tree b/libcxx/include/__tree
index 3ad2129..0f3640e 100644
--- a/libcxx/include/__tree
+++ b/libcxx/include/__tree
@@ -23,6 +23,7 @@
 #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>
@@ -37,7 +38,6 @@
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <__utility/swap.h>
-#include <__utility/try_key_extraction.h>
 #include <limits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -900,74 +900,88 @@ 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 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)...);
+    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;
   }
 
   template <class... _Args>
-  _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)...);
+  _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;
   }
 
   template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type_v<_ValueT>, int> = 0>
@@ -1788,6 +1802,42 @@ void __tree<_Tp, _Compare, _Allocator>::__insert_node_at(
 }
 
 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();
+    __inserted = true;
+  }
+  return pair<iterator, bool>(iterator(__r), __inserted);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
 template <class... _Args>
 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
 __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) {
@@ -1800,6 +1850,39 @@ __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) {
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class... _Args>
+pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
+__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args) {
+  __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
+  __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);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class... _Args>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args) {
+  __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
+  __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 iterator(__r);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class... _Args>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) {
   __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
diff --git a/libcxx/include/__type_traits/can_extract_key.h b/libcxx/include/__type_traits/can_extract_key.h
new file mode 100644
index 0000000..b8359d0
--- /dev/null
+++ b/libcxx/include/__type_traits/can_extract_key.h
@@ -0,0 +1,53 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___TYPE_TRAITS_CAN_EXTRACT_KEY_H
+#define _LIBCPP___TYPE_TRAITS_CAN_EXTRACT_KEY_H
+
+#include <__config>
+#include <__fwd/pair.h>
+#include <__type_traits/conditional.h>
+#include <__type_traits/integral_constant.h>
+#include <__type_traits/is_same.h>
+#include <__type_traits/remove_const.h>
+#include <__type_traits/remove_const_ref.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// These traits are used in __tree and __hash_table
+struct __extract_key_fail_tag {};
+struct __extract_key_self_tag {};
+struct __extract_key_first_tag {};
+
+template <class _ValTy, class _Key, class _RawValTy = __remove_const_ref_t<_ValTy> >
+struct __can_extract_key
+    : __conditional_t<_IsSame<_RawValTy, _Key>::value, __extract_key_self_tag, __extract_key_fail_tag> {};
+
+template <class _Pair, class _Key, class _First, class _Second>
+struct __can_extract_key<_Pair, _Key, pair<_First, _Second> >
+    : __conditional_t<_IsSame<__remove_const_t<_First>, _Key>::value, __extract_key_first_tag, __extract_key_fail_tag> {
+};
+
+// __can_extract_map_key uses true_type/false_type instead of the tags.
+// It returns true if _Key != _ContainerValueTy (the container is a map not a set)
+// and _ValTy == _Key.
+template <class _ValTy, class _Key, class _ContainerValueTy, class _RawValTy = __remove_const_ref_t<_ValTy> >
+struct __can_extract_map_key : integral_constant<bool, _IsSame<_RawValTy, _Key>::value> {};
+
+// This specialization returns __extract_key_fail_tag for non-map containers
+// because _Key == _ContainerValueTy
+template <class _ValTy, class _Key, class _RawValTy>
+struct __can_extract_map_key<_ValTy, _Key, _Key, _RawValTy> : false_type {};
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___TYPE_TRAITS_CAN_EXTRACT_KEY_H
diff --git a/libcxx/include/__utility/try_key_extraction.h b/libcxx/include/__utility/try_key_extraction.h
deleted file mode 100644
index 755c082..0000000
--- a/libcxx/include/__utility/try_key_extraction.h
+++ /dev/null
@@ -1,114 +0,0 @@
-//===----------------------------------------------------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef _LIBCPP___UTILITY_TRY_EXTRACT_KEY_H
-#define _LIBCPP___UTILITY_TRY_EXTRACT_KEY_H
-
-#include <__config>
-#include <__fwd/pair.h>
-#include <__fwd/tuple.h>
-#include <__type_traits/enable_if.h>
-#include <__type_traits/is_same.h>
-#include <__type_traits/remove_const.h>
-#include <__type_traits/remove_const_ref.h>
-#include <__utility/declval.h>
-#include <__utility/forward.h>
-#include <__utility/piecewise_construct.h>
-#include <__utility/priority_tag.h>
-
-#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
-#  pragma GCC system_header
-#endif
-
-_LIBCPP_BEGIN_NAMESPACE_STD
-
-template <class _KeyT, class _Ret, class _WithKey, class _WithoutKey, class... _Args>
-_LIBCPP_HIDE_FROM_ABI _Ret
-__try_key_extraction_impl(__priority_tag<0>, _WithKey, _WithoutKey __without_key, _Args&&... __args) {
-  return __without_key(std::forward<_Args>(__args)...);
-}
-
-template <class _KeyT,
-          class _Ret,
-          class _WithKey,
-          class _WithoutKey,
-          class _Arg,
-          __enable_if_t<is_same<_KeyT, __remove_const_ref_t<_Arg> >::value, int> = 0>
-_LIBCPP_HIDE_FROM_ABI _Ret
-__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg&& __arg) {
-  return __with_key(__arg, std::forward<_Arg>(__arg));
-}
-
-template <class _KeyT,
-          class _Ret,
-          class _WithKey,
-          class _WithoutKey,
-          class _Arg,
-          __enable_if_t<__is_pair_v<__remove_const_ref_t<_Arg> > &&
-                            is_same<__remove_const_t<typename __remove_const_ref_t<_Arg>::first_type>, _KeyT>::value,
-                        int> = 0>
-_LIBCPP_HIDE_FROM_ABI _Ret
-__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg&& __arg) {
-  return __with_key(__arg.first, std::forward<_Arg>(__arg));
-}
-
-template <class _KeyT,
-          class _Ret,
-          class _WithKey,
-          class _WithoutKey,
-          class _Arg1,
-          class _Arg2,
-          __enable_if_t<is_same<_KeyT, __remove_const_ref_t<_Arg1> >::value, int> = 0>
-_LIBCPP_HIDE_FROM_ABI _Ret
-__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg1&& __arg1, _Arg2&& __arg2) {
-  return __with_key(__arg1, std::forward<_Arg1>(__arg1), std::forward<_Arg2>(__arg2));
-}
-
-#ifndef _LIBCPP_CXX03_LANG
-template <class _KeyT,
-          class _Ret,
-          class _WithKey,
-          class _WithoutKey,
-          class _PiecewiseConstruct,
-          class _Tuple1,
-          class _Tuple2,
-          __enable_if_t<is_same<__remove_const_ref_t<_PiecewiseConstruct>, piecewise_construct_t>::value &&
-                            __is_tuple_v<_Tuple1> && tuple_size<_Tuple1>::value == 1 &&
-                            is_same<__remove_const_ref_t<typename tuple_element<0, _Tuple1>::type>, _KeyT>::value,
-                        int> = 0>
-_LIBCPP_HIDE_FROM_ABI _Ret __try_key_extraction_impl(
-    __priority_tag<1>,
-    _WithKey __with_key,
-    _WithoutKey,
-    _PiecewiseConstruct&& __pc,
-    _Tuple1&& __tuple1,
-    _Tuple2&& __tuple2) {
-  return __with_key(
-      std::get<0>(__tuple1),
-      std::forward<_PiecewiseConstruct>(__pc),
-      std::forward<_Tuple1>(__tuple1),
-      std::forward<_Tuple2>(__tuple2));
-}
-#endif // _LIBCPP_CXX03_LANG
-
-// This function tries extracting the given _KeyT from _Args...
-// If it succeeds to extract the key, it calls the `__with_key` function with the extracted key and all of the
-// arguments. Otherwise it calls the `__without_key` function with all of the arguments.
-//
-// Both `__with_key` and `__without_key` must take all arguments by reference.
-template <class _KeyT, class _WithKey, class _WithoutKey, class... _Args>
-_LIBCPP_HIDE_FROM_ABI decltype(std::declval<_WithoutKey>()(std::declval<_Args>()...))
-__try_key_extraction(_WithKey __with_key, _WithoutKey __without_key, _Args&&... __args) {
-  using _Ret = decltype(__without_key(std::forward<_Args>(__args)...));
-  return std::__try_key_extraction_impl<_KeyT, _Ret>(
-      __priority_tag<1>(), __with_key, __without_key, std::forward<_Args>(__args)...);
-}
-
-_LIBCPP_END_NAMESPACE_STD
-
-#endif // _LIBCPP___UTILITY_TRY_EXTRACT_KEY_H
diff --git a/libcxx/include/map b/libcxx/include/map
index b53e1c4..9bd2282 100644
--- a/libcxx/include/map
+++ b/libcxx/include/map
@@ -1055,7 +1055,7 @@ public:
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
-    return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...).first;
+    return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...);
   }
 
   template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
@@ -1065,7 +1065,7 @@ public:
 
   template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
-    return __tree_.__emplace_hint_unique(__pos.__i_, std::forward<_Pp>(__p)).first;
+    return __tree_.__emplace_hint_unique(__pos.__i_, std::forward<_Pp>(__p));
   }
 
 #  endif // _LIBCPP_CXX03_LANG
@@ -1073,7 +1073,7 @@ public:
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__emplace_unique(__v); }
 
   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
-    return __tree_.__emplace_hint_unique(__p.__i_, __v).first;
+    return __tree_.__emplace_hint_unique(__p.__i_, __v);
   }
 
 #  ifndef _LIBCPP_CXX03_LANG
@@ -1082,7 +1082,7 @@ public:
   }
 
   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
-    return __tree_.__emplace_hint_unique(__p.__i_, std::move(__v)).first;
+    return __tree_.__emplace_hint_unique(__p.__i_, std::move(__v));
   }
 
   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
@@ -1108,13 +1108,17 @@ public:
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
-    return __tree_.__emplace_unique(
-        std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));
+    return __tree_.__emplace_unique_key_args(
+        __k,
+        std::piecewise_construct,
+        std::forward_as_tuple(__k),
+        std::forward_as_tuple(std::forward<_Args>(__args)...));
   }
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
-    return __tree_.__emplace_unique(
+    return __tree_.__emplace_unique_key_args(
+        __k,
         std::piecewise_construct,
         std::forward_as_tuple(std::move(__k)),
         std::forward_as_tuple(std::forward<_Args>(__args)...));
@@ -1123,8 +1127,9 @@ public:
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) {
     return __tree_
-        .__emplace_hint_unique(
+        .__emplace_hint_unique_key_args(
             __h.__i_,
+            __k,
             std::piecewise_construct,
             std::forward_as_tuple(__k),
             std::forward_as_tuple(std::forward<_Args>(__args)...))
@@ -1134,8 +1139,9 @@ public:
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) {
     return __tree_
-        .__emplace_hint_unique(
+        .__emplace_hint_unique_key_args(
             __h.__i_,
+            __k,
             std::piecewise_construct,
             std::forward_as_tuple(std::move(__k)),
             std::forward_as_tuple(std::forward<_Args>(__args)...))
@@ -1164,7 +1170,7 @@ public:
 
   template <class _Vp>
   _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) {
-    auto [__r, __inserted] = __tree_.__emplace_hint_unique(__h.__i_, __k, std::forward<_Vp>(__v));
+    auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, __k, std::forward<_Vp>(__v));
 
     if (!__inserted)
       __r->second = std::forward<_Vp>(__v);
@@ -1174,7 +1180,8 @@ public:
 
   template <class _Vp>
   _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) {
-    auto [__r, __inserted] = __tree_.__emplace_hint_unique(__h.__i_, std::move(__k), std::forward<_Vp>(__v));
+    auto [__r, __inserted] =
+        __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, std::move(__k), std::forward<_Vp>(__v));
 
     if (!__inserted)
       __r->second = std::forward<_Vp>(__v);
@@ -1391,15 +1398,20 @@ map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
-  return __tree_.__emplace_unique(std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
+  return __tree_
+      .__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
       .first->second;
 }
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) {
+  // TODO investigate this clang-tidy warning.
+  // NOLINTBEGIN(bugprone-use-after-move)
   return __tree_
-      .__emplace_unique(std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
+      .__emplace_unique_key_args(
+          __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
       .first->second;
+  // NOLINTEND(bugprone-use-after-move)
 }
 
 #  else // _LIBCPP_CXX03_LANG
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
index ee18d04..c431c0c 100644
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -70,6 +70,7 @@ module std_core [system] {
     module aligned_storage                            { header "__type_traits/aligned_storage.h" }
     module aligned_union                              { header "__type_traits/aligned_union.h" }
     module alignment_of                               { header "__type_traits/alignment_of.h" }
+    module can_extract_key                            { header "__type_traits/can_extract_key.h" }
     module common_reference                           { header "__type_traits/common_reference.h" }
     module common_type {
       header "__type_traits/common_type.h"
@@ -2177,7 +2178,6 @@ module std [system] {
     module small_buffer               { header "__utility/small_buffer.h" }
     module swap                       { header "__utility/swap.h" }
     module to_underlying              { header "__utility/to_underlying.h" }
-    module try_key_extraction         { header "__utility/try_key_extraction.h" }
     module unreachable                { header "__utility/unreachable.h" }
 
     header "utility"
diff --git a/libcxx/include/set b/libcxx/include/set
index b444e83..5190fc1 100644
--- a/libcxx/include/set
+++ b/libcxx/include/set
@@ -732,13 +732,13 @@ public:
   }
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
-    return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...).first;
+    return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...);
   }
 #  endif // _LIBCPP_CXX03_LANG
 
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__emplace_unique(__v); }
   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
-    return __tree_.__emplace_hint_unique(__p, __v).first;
+    return __tree_.__emplace_hint_unique(__p, __v);
   }
 
   template <class _InputIterator>
@@ -763,7 +763,7 @@ public:
   }
 
   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
-    return __tree_.__emplace_hint_unique(__p, std::move(__v)).first;
+    return __tree_.__emplace_hint_unique(__p, std::move(__v));
   }
 
   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
diff --git a/libcxx/include/tuple b/libcxx/include/tuple
index d2cc0f5..8cc061c 100644
--- a/libcxx/include/tuple
+++ b/libcxx/include/tuple
@@ -324,6 +324,12 @@ _LIBCPP_HIDE_FROM_ABI constexpr _Ret __tuple_compare_three_way(const _Tp& __x, c
 #    endif // _LIBCPP_STD_VER >= 20
 
 #    if _LIBCPP_STD_VER >= 23
+template <class>
+inline constexpr bool __is_tuple_v = false;
+
+template <class... _Tp>
+inline constexpr bool __is_tuple_v<tuple<_Tp...>> = true;
+
 template <class _Tp>
 concept __tuple_like_no_tuple = __tuple_like<_Tp> && !__is_tuple_v<_Tp>;
 
diff --git a/libcxx/include/unordered_map b/libcxx/include/unordered_map
index 9b02ecf0..a934953 100644
--- a/libcxx/include/unordered_map
+++ b/libcxx/include/unordered_map
@@ -1172,13 +1172,14 @@ public:
 #  if _LIBCPP_STD_VER >= 17
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
-    return __table_.__emplace_unique(
-        piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));
+    return __table_.__emplace_unique_key_args(
+        __k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));
   }
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
-    return __table_.__emplace_unique(
+    return __table_.__emplace_unique_key_args(
+        __k,
         piecewise_construct,
         std::forward_as_tuple(std::move(__k)),
         std::forward_as_tuple(std::forward<_Args>(__args)...));
@@ -1196,7 +1197,7 @@ public:
 
   template <class _Vp>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {
-    pair<iterator, bool> __res = __table_.__emplace_unique(__k, std::forward<_Vp>(__v));
+    pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, __k, std::forward<_Vp>(__v));
     if (!__res.second) {
       __res.first->second = std::forward<_Vp>(__v);
     }
@@ -1205,7 +1206,7 @@ public:
 
   template <class _Vp>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {
-    pair<iterator, bool> __res = __table_.__emplace_unique(std::move(__k), std::forward<_Vp>(__v));
+    pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, std::move(__k), std::forward<_Vp>(__v));
     if (!__res.second) {
       __res.first->second = std::forward<_Vp>(__v);
     }
@@ -1611,13 +1612,16 @@ inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterato
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
-  return __table_.__emplace_unique(piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
+  return __table_
+      .__emplace_unique_key_args(__k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
       .first->second;
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) {
-  return __table_.__emplace_unique(piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
+  return __table_
+      .__emplace_unique_key_args(
+          __k, piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
       .first->second;
 }
 #  else // _LIBCPP_CXX03_LANG