[libc++] Remove UB from `std::map` by updating `std::__tree_node` construction #153908

vinay-deshmukh · 2025-08-16T00:47:54Z

This patch also updates __hash_table to match what we do in __tree now.

…pp26

github-actions · 2025-08-16T00:49:34Z

⚠️ We detected that you are using a GitHub private e-mail address to contribute to the repo.
Please turn off Keep my email addresses private setting in your account.
See LLVM Developer Policy and LLVM Discourse for more information.

github-actions · 2025-08-16T00:51:12Z

✅ With the latest revision this PR passed the C/C++ code formatter.

libcxx/include/__tree

vinay-deshmukh · 2025-08-16T13:31:01Z

libcxx/include/__tree

@@ -1276,7 +1310,7 @@ private:
      return nullptr;
    }

-    __assign_value(__dest->__value_, __src->__value_);


As we no longer expose the member directly, all accesses need to go through the member function so the right type is used.

otherwise, every access needs to be updated to use ifndef CXX03

libcxx/include/set

vinay-deshmukh · 2025-08-16T16:32:54Z

libcxx/include/__tree

@@ -1808,7 +1842,7 @@ typename __tree<_Tp, _Compare, _Allocator>::__node_holder
 __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) {
  __node_allocator& __na = __node_alloc();
  __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
-  __node_traits::construct(__na, std::addressof(__h->__value_), std::forward<_Args>(__args)...);
+  std::__construct_at(std::addressof(*__h), __na, std::forward<_Args>(__args)...);


N.B. This is the line that prompts this change due to needing workarounds when implementing P3372 for map (Add constexpr)

vinay-deshmukh · 2025-08-16T16:47:41Z

Failed checks seem to have timed out after 2 hours:

libcxx/include/__tree

philnik777 · 2025-08-18T08:50:55Z

libcxx/include/__tree

@@ -572,7 +574,8 @@ public:

  _LIBCPP_HIDE_FROM_ABI void __set_parent(pointer __p) { __parent_ = static_cast<__end_node_pointer>(__p); }

-  ~__tree_node_base()                                  = delete;
+  _LIBCPP_HIDE_FROM_ABI __tree_node_base()             = default;
+  _LIBCPP_HIDE_FROM_ABI ~__tree_node_base()            = default;


I think we can just remove this line. Possibly also the the default constructor?

I believe the reason I had to add these was because I got errors like these:

Case 1):

Both 577 and 578 commented

failures

# .---command stderr------------ # | In file included from /source-dir/libcxx/test/std/containers/associative/map/compare.pass.cpp:18: # | In file included from /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/map:599: # | /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/__tree:611:34: error: constructor for 'std::__tree_node<std::__value_type<Key, int>, void *>' must explicitly initialize the base class '__tree_node_base<void *>' which does not have a default constructor # | 611 | _LIBCPP_HIDE_FROM_ABI explicit __tree_node(_Alloc& __na, _Args&&... __args) { # | | ^ # | /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/__memory/construct_at.h:38:49: note: in instantiation of function template specialization 'std::__tree_node<std::__value_type<Key, int>, void *>::__tree_node<std::allocator<std::__tree_node<std::__value_type<Key, int>, void *>>, const std::piecewise_construct_t &, std::tuple<Key &&>, std::tuple<>>' requested here # | 38 | return ::new (static_cast<void*>(__location)) _Tp(std::forward<_Args>(__args)...); # | | ^ # | /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/__tree:1812:25: note: in instantiation of function template specialization 'std::__tree<std::__value_type<Key, int>, std::__map_value_compare<Key, std::pair<const Key, int>, std::less<Key>>, std::allocator<std::pair<const Key, int>>>::__construct_node<const std::piecewise_construct_t &, std::tuple<Key &&>, std::tuple<>>' requested here # | 1812 | __node_holder __h = __construct_node(std::forward<_Args>(__args)...); # | | ^ # | /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/map:1410:8: note: in instantiation of function template specialization 'std::__tree<std::__value_type<Key, int>, std::__map_value_compare<Key, std::pair<const Key, int>, std::less<Key>>, std::allocator<std::pair<const Key, int>>>::__emplace_unique_key_args<Key, const std::piecewise_construct_t &, std::tuple<Key &&>, std::tuple<>>' requested here # | 1410 | .__emplace_unique_key_args( # | | ^ # | /source-dir/libcxx/test/std/containers/associative/map/compare.pass.cpp:37:15: note: in instantiation of member function 'std::map<Key, int>::operator[]' requested here # | 37 | m_contains[Key(0)] = 42; # | | ^ # | /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/__tree:564:1: note: 'std::__tree_node_base<void *>' declared here # | 564 | __tree_node_base : public __tree_end_node<__rebind_pointer_t<_VoidPtr, __tree_node_base<_VoidPtr> > > { # | | ^ ^

From 43/64 /map tests

Case 2): Only 578 commented, (maybe a default destructortor is created)

all pass

case 3): constructor() = default; and destructor = delete

failures

# | In file included from /source-dir/libcxx/test/std/containers/associative/map/map.cons/copy_assign.addressof.compile.pass.cpp:17: # | In file included from /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/map:599: # | /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/__tree:612:34: error: attempt to use a deleted function # | 612 | _LIBCPP_HIDE_FROM_ABI explicit __tree_node(_Alloc& __na, _Args&&... __args) { # | | ^ # | /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/__memory/construct_at.h:38:49: note: in instantiation of function template specialization 'std::__tree_node<std::__value_type<int, operator_hijacker>, void *>::__tree_node<std::allocator<std::__tree_node<std::__value_type<int, operator_hijacker>, void *>>, std::pair<const int, operator_hijacker> &>' requested here # | 38 | return ::new (static_cast<void*>(__location)) _Tp(std::forward<_Args>(__args)...); # | | ^ # | /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/__tree:1283:32: note: in instantiation of function template specialization 'std::__tree<std::__value_type<int, operator_hijacker>, std::__map_value_compare<int, std::pair<const int, operator_hijacker>, std::less<int>>, std::allocator<std::pair<const int, operator_hijacker>>>::__construct_node<std::pair<const int, operator_hijacker> &>' requested here # | 1283 | __node_holder __new_node = __construct_node(__src->__get_value()); # | | ^ # | /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/__tree:1414:54: note: in instantiation of member function 'std::__tree<std::__value_type<int, operator_hijacker>, std::__map_value_compare<int, std::pair<const int, operator_hijacker>, std::less<int>>, std::allocator<std::pair<const int, operator_hijacker>>>::__copy_construct_tree' requested here # | 1414 | *__root_ptr() = static_cast<__node_base_pointer>(__copy_construct_tree(__t.__root())); # | | ^ # | /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/map:977:64: note: in instantiation of member function 'std::__tree<std::__value_type<int, operator_hijacker>, std::__map_value_compare<int, std::pair<const int, operator_hijacker>, std::less<int>>, std::allocator<std::pair<const int, operator_hijacker>>>::operator=' requested here # | 977 | _LIBCPP_HIDE_FROM_ABI map& operator=(const map& __m) = default; # | | ^ # | /source-dir/build/myclang22/libcxx/test-suite-install/include/c++/v1/__tree:579:3: note: '~__tree_node_base' has been explicitly marked deleted here # | 579 | ~__tree_node_base() = delete; | ^~~~~~~~~~

</details?

I think we can just remove this line. Possibly also the the default constructor?

Seems like that the default constructor needs to be explicitly defaulted. Otherwise, it won't exist because its declaration will be suppressed.

I believe the reason I had to add these was because I got errors like these:

I don't think we need to explicitly declare the destructor.

I don't think we need to explicitly declare the destructor.

THis should be fixed as of 8e9153e

libcxx/include/__tree

libcxx/include/set

vinay-deshmukh · 2025-08-18T23:17:31Z

#153908 (comment)

You mean nothing complained when you made _value private? If that is the case we're definitely missing tests. Please file a bug about it or add some tests yourself. The latter would be appreciated, but not necessary

my bad, false alarm

I do get test failures if I don't update set and multiset...

…oval (#154225) Prepare for: #153908 (comment)

…map-ub

… for UB removal (#154225) Prepare for: llvm/llvm-project#153908 (comment)

vinay-deshmukh · 2025-08-30T02:20:53Z

Ping @philnik777 @frederick-vs-ja

…map-ub

…roject into vinay-issue-128660-map-ub

philnik777

LGTM with the last two open comments addressed.

libcxx/include/__tree

…map-ub

This reverts commit f7332e6.

philnik777 · 2025-09-04T06:52:25Z

libcxx/include/__hash_table

  //
  // We don't use the allocator's construct() method to construct the node itself since the
  // Cpp17FooInsertable named requirements don't require the allocator's construct() method
  // to work on anything other than the value_type.
-  std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ 0);
+  std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ 0, __na, std::forward<_Args>(__args)...);


Do we ever construct the node with anything but nullptr and 0? If not, I'd just move that into the constructor.

vinay-deshmukh added 2 commits August 15, 2025 20:42

use allocator as template arg and allocator_traits, tests passed in c…

2f689f9

…pp26

remove UB using list

bbc637a

vinay-deshmukh mentioned this pull request Aug 16, 2025

[libc++] Make <map> std::map constexpr as part of P3372R3 #134330

Open

vinay-deshmukh added 5 commits August 15, 2025 20:53

cf

99c2829

doc-fix

5afe3a4

Replace __value_ with __get_value() for __tree_node

ca72744

miss typo

47b71f8

fix ctor for cpp03 buffer

d16fabf

vinay-deshmukh changed the title ~~[libc++] Remove UB from std::map __tree_node constructor~~ [libc++] Remove UB from std::map __tree_node construction Aug 16, 2025

vinay-deshmukh added 5 commits August 15, 2025 21:13

cf

dcd4cb4

rename in map as well

08f5328

cf

4b5609c

include

d24dbc2

more?

9c47574

vinay-deshmukh marked this pull request as ready for review August 16, 2025 02:00

vinay-deshmukh requested a review from a team as a code owner August 16, 2025 02:00

hide from abi

8b1278e

vinay-deshmukh commented Aug 16, 2025

View reviewed changes

libcxx/include/__tree Outdated Show resolved Hide resolved

vinay-deshmukh commented Aug 16, 2025

View reviewed changes

libcxx/include/set Outdated Show resolved Hide resolved

vinay-deshmukh commented Aug 16, 2025

View reviewed changes

terser

b241636

philnik777 requested changes Aug 18, 2025

View reviewed changes

vinay-deshmukh added 2 commits August 18, 2025 07:36

redundant launder

f5cc9c3

single branch

c1a776e

vinay-deshmukh mentioned this pull request Aug 18, 2025

[libc++] Make std::__tree_node member private to prepare for UB removal #154225

Merged

vinay-deshmukh added 3 commits August 18, 2025 19:24

remove the & from buffer

4e905fe

remove _LIBCPP_STANDALONE_DEBUG

225b03c

cf

1b01b80

philnik777 pushed a commit that referenced this pull request Aug 19, 2025

[libc++] Make std::__tree_node member private to prepare for UB rem…

d286f2e

…oval (#154225) Prepare for: #153908 (comment)

Merge remote-tracking branch 'upstream/main' into vinay-issue-128660-…

62df872

…map-ub

vinay-deshmukh requested review from philnik777 and frederick-vs-ja August 19, 2025 09:43

llvm-sync bot pushed a commit to arm/arm-toolchain that referenced this pull request Aug 19, 2025

Automerge: [libc++] Make std::__tree_node member private to prepare…

2508513

… for UB removal (#154225) Prepare for: llvm/llvm-project#153908 (comment)

Merge branch 'main' into vinay-issue-128660-map-ub

e035df9

vinay-deshmukh added 2 commits August 31, 2025 11:34

Merge remote-tracking branch 'upstream/main' into vinay-issue-128660-…

675a0ca

…map-ub

Merge branch 'vinay-issue-128660-map-ub' of out:vinay-deshmukh/llvm-p…

54951dd

…roject into vinay-issue-128660-map-ub

philnik777 reviewed Sep 1, 2025

View reviewed changes

libcxx/include/__tree Show resolved Hide resolved

vinay-deshmukh added 2 commits September 1, 2025 13:30

Remove ~__tree_node_base() = default;

77c1569

Update __hash_node constructor to be similar to __tree_node

0698243

vinay-deshmukh changed the title ~~[libc++] Remove UB from std::map __tree_node construction~~ [libc++] Remove UB from std::map by updating std::__tree_node construction / Update std::__hash_node construction Sep 1, 2025

vinay-deshmukh added 4 commits September 1, 2025 14:15

cf

5cd0195

Merge remote-tracking branch 'upstream/main' into vinay-issue-128660-…

881284a

…map-ub

delete ~__tree_node_base

f7332e6

Revert "delete ~__tree_node_base"

8e9153e

This reverts commit f7332e6.

vinay-deshmukh requested a review from philnik777 September 4, 2025 01:16

philnik777 changed the title ~~[libc++] Remove UB from std::map by updating std::__tree_node construction / Update std::__hash_node construction~~ [libc++] Remove UB from std::map by updating std::__tree_node construction Sep 4, 2025

philnik777 reviewed Sep 4, 2025

View reviewed changes

[libc++] Remove UB from std::map by updating std::__tree_node construction #153908

Are you sure you want to change the base?

[libc++] Remove UB from std::map by updating std::__tree_node construction #153908

Uh oh!

Conversation

vinay-deshmukh commented Aug 16, 2025 • edited by philnik777 Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions bot commented Aug 16, 2025

Uh oh!

github-actions bot commented Aug 16, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

vinay-deshmukh Aug 16, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

vinay-deshmukh Aug 16, 2025

Choose a reason for hiding this comment

Uh oh!

vinay-deshmukh commented Aug 16, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

philnik777 Aug 18, 2025

Choose a reason for hiding this comment

Uh oh!

vinay-deshmukh Aug 18, 2025

Choose a reason for hiding this comment

Uh oh!

frederick-vs-ja Sep 1, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vinay-deshmukh Sep 4, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

vinay-deshmukh commented Aug 18, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vinay-deshmukh commented Aug 30, 2025

Uh oh!

philnik777 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

philnik777 Sep 4, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

[libc++] Remove UB from `std::map` by updating `std::__tree_node` construction #153908

[libc++] Remove UB from `std::map` by updating `std::__tree_node` construction #153908

vinay-deshmukh commented Aug 16, 2025 •

edited by philnik777

Loading

github-actions bot commented Aug 16, 2025 •

edited

Loading

vinay-deshmukh commented Aug 16, 2025 •

edited

Loading

frederick-vs-ja Sep 1, 2025 •

edited

Loading

vinay-deshmukh commented Aug 18, 2025 •

edited

Loading