[libc++] P3372R3: constexpr `map`

[frederick-vs-ja]

Make map constexpr as part of P3372R3.

Note that node-handle::key() is intentionally left not constexpr.

Feature-test macro (also covers constexpr multimap):

#define __cpp_lib_constexpr_map 202502L // also in <map>

[vinay-deshmukh]

Hi,
I'd like to work on this issue.

[ldionne]

Feel free to submit a PR!

[vinay-deshmukh]

So might need some help to move ahead:

As of: def8261

In:
https://github.com/llvm/llvm-project/actions/runs/14295382585/job/40061871168?pr=134330

Particularly, the test for :

TEST 'llvm-libc++-shared.cfg.in :: std/containers/associative/map/map.access/at.pass.cpp'

I seem to stuck at the following error:

note: cast from 'void *' is not allowed in a constant expression because the pointed object type 'std::__tree_node<std::__value_type<int, double>, min_pointer<void>>' is not similar to the target type 'std::__tree_node_base<min_pointer<void>>

# COMPILED WITH
  /usr/bin/clang++-21 /__w/llvm-project/llvm-project/libcxx/test/std/containers/associative/map/map.access/at.pass.cpp -pthread --target=x86_64-unknown-linux-gnu -nostdinc++ -I /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/include/c++/v1 -I /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/include/c++/v1 -I /__w/llvm-project/llvm-project/libcxx/test/support -std=c++26 -Werror -Wall -Wctad-maybe-unsupported -Wextra -Wshadow -Wundef -Wunused-template -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-noexcept-type -Wno-atomic-alignment -Wno-reserved-module-identifier -Wdeprecated-copy -Wdeprecated-copy-dtor -Wshift-negative-value -Wno-user-defined-literals -Wno-tautological-compare -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -Wno-local-type-template-args -Wno-c++11-extensions -Wno-unknown-pragmas -Wno-pass-failed -Wno-mismatched-new-delete -Wno-redundant-move -Wno-self-move -Wno-nullability-completeness -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -D_LIBCPP_ENABLE_EXPERIMENTAL -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_NONE -Werror=thread-safety -Wuser-defined-warnings  -lc++experimental -nostdlib++ -L /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/lib -Wl,-rpath,/__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/lib -lc++ -latomic -o /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test/std/containers/associative/map/map.access/Output/at.pass.cpp.dir/t.tmp.exe
  # executed command: /usr/bin/clang++-21 /__w/llvm-project/llvm-project/libcxx/test/std/containers/associative/map/map.access/at.pass.cpp -pthread --target=x86_64-unknown-linux-gnu -nostdinc++ -I /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/include/c++/v1 -I /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/include/c++/v1 -I /__w/llvm-project/llvm-project/libcxx/test/support -std=c++26 -Werror -Wall -Wctad-maybe-unsupported -Wextra -Wshadow -Wundef -Wunused-template -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-noexcept-type -Wno-atomic-alignment -Wno-reserved-module-identifier -Wdeprecated-copy -Wdeprecated-copy-dtor -Wshift-negative-value -Wno-user-defined-literals -Wno-tautological-compare -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -Wno-local-type-template-args -Wno-c++11-extensions -Wno-unknown-pragmas -Wno-pass-failed -Wno-mismatched-new-delete -Wno-redundant-move -Wno-self-move -Wno-nullability-completeness -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -D_LIBCPP_ENABLE_EXPERIMENTAL -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_NONE -Werror=thread-safety -Wuser-defined-warnings -lc++experimental -nostdlib++ -L /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/lib -Wl,-rpath,/__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/lib -lc++ -latomic -o /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test/std/containers/associative/map/map.access/Output/at.pass.cpp.dir/t.tmp.exe
  # .---command stderr------------
  # | /__w/llvm-project/llvm-project/libcxx/test/std/containers/associative/map/map.access/at.pass.cpp:179:17: error: static assertion expression is not an integral constant expression
  # |   179 |   static_assert(test());
  # |       |                 ^~~~~~
  # | /__w/llvm-project/llvm-project/libcxx/test/support/min_allocator.h:251:93: note: cast from 'void *' is not allowed in a constant expression because the pointed object type 'std::__tree_node<std::__value_type<int, double>, min_pointer<void>>' is not similar to the target type 'std::__tree_node_base<min_pointer<void>>'
  # |   251 |     TEST_CONSTEXPR_CXX14 explicit min_pointer(min_pointer<void, ID> p) TEST_NOEXCEPT : ptr_(static_cast<T*>(p.ptr_)) {}
  # |       |                                                                                             ^
  # | /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/include/c++/v1/__tree:1844:48: note: in call to 'min_pointer({&{*new std::__tree_node<std::__value_type<int, double>, min_pointer<void>>[1]#14}[0]})'
  # |  1844 |     [[maybe_unused]] __node_base_pointer foo = static_cast<__node_base_pointer>(__h.get());
  # |       |                                                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # | /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/include/c++/v1/__tree:1111:12: note: in call to 'this->__emplace_hint_unique_key_args<int, const std::pair<const int, double> &>({{&m.__tree_.__end_node_}}, ar[0].first, ar[0])'
  # |  1111 |     return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v).first;
  # |       |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # | /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/include/c++/v1/map:1242:12: note: in call to 'this->__tree_.__insert_unique({{&m.__tree_.__end_node_}}, ar[0])'
  # |  1242 |     return __tree_.__insert_unique(__pos.__i_, std::forward<_Pp>(__p));
  # |       |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # | /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/include/c++/v1/map:1268:7: note: in call to 'this->insert<std::pair<const int, double> &, 0>({{{&m.__tree_.__end_node_}}}, ar[0])'
  # |  1268 |       insert(__e.__i_, *__f);
  # |       |       ^~~~~~~~~~~~~~~~~~~~~~
  # | /__w/llvm-project/llvm-project/build/generic-cxx26/libcxx/test-suite-install/include/c++/v1/map:1071:5: note: in call to 'this->insert<std::pair<const int, double> *>(&ar[0], &ar[7])'
  # |  1071 |     insert(__f, __l);
  # |       |     ^~~~~~~~~~~~~~~~
  # | /__w/llvm-project/llvm-project/libcxx/test/std/containers/associative/map/map.access/at.pass.cpp:123:61: note: in call to 'map<std::pair<const int, double> *>(&ar[0], &ar[7], key_compare())'
  # |   123 |     std::map<int, double, std::less<int>, min_allocator<V>> m(ar, ar + sizeof(ar) / sizeof(ar[0]));
  # |       |                                                             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # | /__w/llvm-project/llvm-project/libcxx/test/std/containers/associative/map/map.access/at.pass.cpp:179:17: note: in call to 'test()'
  # |   179 |   static_assert(test());
  # |       |                 ^~~~~~
  # | 1 error generated.
  # `-----------------------------
  # error: command failed with exit status: 1

When the default allocator is used, this code works at:

llvm-project/libcxx/test/std/containers/associative/map/map.access/at.pass.cpp

Lines 26 to 44 in def8261

	typedef std::pair<const int, double> V;
	V ar[] = {
	V(1, 1.5),
	V(2, 2.5),
	V(3, 3.5),
	V(4, 4.5),
	V(5, 5.5),
	V(7, 7.5),
	V(8, 8.5),
	};
	std::map<int, double> m(ar, ar + sizeof(ar) / sizeof(ar[0]));
	assert(m.size() == 7);
	assert(m.at(1) == 1.5);
	m.at(1) = -1.5;
	assert(m.at(1) == -1.5);
	assert(m.at(2) == 2.5);
	assert(m.at(3) == 3.5);
	assert(m.at(4) == 4.5);
	assert(m.at(5) == 5.5);

But the above error shows up shows up when using min_allocator and min_pointer at:

llvm-project/libcxx/test/std/containers/associative/map/map.access/at.pass.cpp

Lines 123 to 131 in def8261

	std::map<int, double, std::less<int>, min_allocator<V>> m(ar, ar + sizeof(ar) / sizeof(ar[0]));
	assert(m.size() == 7);
	assert(m.at(1) == 1.5);
	m.at(1) = -1.5;
	assert(m.at(1) == -1.5);
	assert(m.at(2) == 2.5);
	assert(m.at(3) == 3.5);
	assert(m.at(4) == 4.5);
	assert(m.at(5) == 5.5);

What I understand about this error:

When casting void* to T* here:

llvm-project/libcxx/test/support/min_allocator.h

Line 251 in def8261

TEST_CONSTEXPR_CXX14 explicit min_pointer(min_pointer<void, ID> p) TEST_NOEXCEPT : ptr_(static_cast<T*>(p.ptr_)) {}

The operation is not allowed at compile time, because the compiler is unable to "see" that the void* at:

llvm-project/libcxx/test/support/min_allocator.h

Lines 220 to 223 in def8261

	template <class ID>
	class min_pointer<void, ID>
	{
	void* ptr_;

is "really" pointing to the right derived class instance.

Any ideas on how to fix/update this so it works both at runtime/compile time?

I could update min_pointer as well, but I'm not sure I understand exactly/fully what it does.

@ldionne @frederick-vs-ja

[frederick-vs-ja]

@vinay-deshmukh I think we need to avoid casting from void_pointer to arbitrary pointer. Perhaps we should obtain raw pointers from fancy pointers by std::to_address first, and then use pointer_to to obtain correct suitable fancy pointers.

[vinay-deshmukh]

Appreciate the input, not sure why but it's not occurring any more, so right now, I'm trying to get through all/most of the tests and keep the pending ones for later.