[libc++] undefined behaviour in std::set/std::map/std::unordered_set/std::unordered_map

[hanickadot]

I was implementing P3372 (constexpr containers and adaptors) in libc++ and found UB which fails evaluation in ExprConstant.cpp.

It's in these two files:
libcxx/include/__tree
libcxx/include/__hash_table

(link is to the locations of problems)

These are similar issue where a node / bucket is allocated, but NOT constructed, and then a subobject is constructed.

[hanickadot]

Another one is here: https://github.com/llvm/llvm-project/blob/main/libcxx/include/__hash_table#L1709-L1710

[hanickadot]

[hanickadot]

(lines can be a little different in screenshots as it's my constexpr branch)

[frederick-vs-ja]

Possibly off-topic: I attempted to add constexpr to MSVC STL's (multi)map, and then found that

• the manner of construction of the node needs to be fixed, while the fix is simple, and
• node-handle needs to be reworked to use a proper union, but
• the const-dropping key() function of node-handle is not yet fixable.

It's not yet possible to avoid core UB in modification of the key which is a const subobject. CWG2514 is related.

---

Maybe related: [class.cdtor]/1 and CWG1517.

Perhaps we should to start the lifetime of the node first and wrap the element into a union at this moment.

I don't understand why can't we refer to these subobjects (evaluate the member access expression?) before construction even if virtual base class is not involved.

---

BTW, you can use permanent links to show the code in the Github UI.

llvm-project/libcxx/include/__tree

Lines 1808 to 1815 in 00139ae

	typename __tree<_Tp, _Compare, _Allocator>::__node_holder
	__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) {
	static_assert(!__is_tree_value_type<_Args...>::value, "Cannot construct from __value_type");
	__node_allocator& __na = __node_alloc();
	__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
	__node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), std::forward<_Args>(__args)...);
	__h.get_deleter().__value_constructed = true;
	return __h;

llvm-project/libcxx/include/__hash_table

Lines 1813 to 1820 in 00139ae

	__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, _NodeTypes::__get_ptr(__h->__get_value()), std::forward<_First>(__f), std::forward<_Rest>(__rest)...);
	__h.get_deleter().__value_constructed = true;