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

vinay-deshmukh · 2025-04-04T00:41:50Z

Depends on:

Summary:

Apply _LIBCPP_CONSTEXPR_SINCE_CXX26 to map, __tree, node-handle, __libcpp_erase_if, __lazy_synth_three_way_comparator, __lazy_compare_result, libcxx/include/__utility/try_key_extraction.h
Skip test erase_if.pass.cpp for GCC during constant evaluation. AFAICT this appears to be a g++ bug, as the test passes with clang
Disable test for node-handle::key() during constant evaluation (CWG2514). It is annotated with a // FIXME
map.modifiers/try.emplace.pass.cpp : Start using the previously unused mv3. (Should this be a separate patch?)
Has a TODO for multimap and ohters
a. libcxx/test/std/containers/associative/map/map.ops/contains.pass.cpp
b. libcxx/test/std/containers/associative/map/map.ops/contains_transparent.pass.cpp
a. libcxx/test/std/containers/container.node/node_handle.pass.cpp
~~Fix typo in libcxx/include/__memory/pointer_traits.h~~ -> [NFC][libc++] Fix typo in libcxx/include/__memory/pointer_traits.h #157304
pair<const MoveOnly, ...>
a. move_assign.pass.cpp
b. move_alloc.pass.cpp
c. Fails to compile if static_assert(test()); is called in the test file
d. Has a // FIXME with commented code
~~Change __tree_node to construct it's __node_value_type during construction to avoid the: note: member call on object outside its lifetime is not allowed in a constant expression issue.~~ This became -> [libc++] Remove UB from std::__tree_node construction #153908

github-actions · 2025-04-04T00:43:27Z

⚠️ 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 Discourse for more information.

github-actions · 2025-04-04T00:44:15Z

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

…__value_type<int, int>')

libcxx/include/__utility/pair.h

vinay-deshmukh · 2025-04-10T12:09:13Z

At this point, I have fixed all the trivially fixable issues as far as I can tell, but naturally trying to fix the lifetime issue I saw when trying to fix it in:

cec33fb

(need explicit constructors for std::__value_type and __tree_node_base to start the lifetime of a node at

https://github.com/llvm/llvm-project/blame/900d44976c89477607946fad4493e4b9ac09346f/libcxx/include/__tree#L1956)

And that has resulted in a im-perfect forwarding (I think)

I did find this commit that mentions that the code is UB (slightly less than previously), so maybe constexpr flagging that is expected

f52318b | https://reviews.llvm.org/D47607

@frederick-vs-ja

frederick-vs-ja · 2025-04-11T03:24:55Z

I did find this commit that mentions that the code is UB (slightly less than previously), so maybe constexpr flagging that is expected

f52318b | https://reviews.llvm.org/D47607

This is clearly UB in the core language. Per current rules we can't assign the first data member of a pair<const int, int>, even when the complete object is non-const.

IIUC we need to perform different operations (e.g. reconstructing the node) in constant evaluation.

vinay-deshmukh · 2025-04-14T23:54:18Z

Update:

Need to wait for #134819 to be merged before this PR can proceed.

That PR should get rid of some more UB, and later I should be able to:

There's still some UB left, but that' only in the __assign_value and __insert_from_orphaned_node functions, where you should be able to just destroy/construct instead of assigning to remove any UB during constant evaluation.

From Discord by philnik777

…660-P3372-constexpr-map

…P3372-constexpr-map

This reverts commit 9f931f5. # Conflicts: # libcxx/test/std/containers/associative/map/map.modifiers/insert_node_type.pass.cpp

…P3372-constexpr-map

Zingam · 2025-10-18T15:48:17Z

⚠️ 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 Discourse for more information.

Please also make your email public. It is a requirement for contributing to libc++/llvm.

vinay-deshmukh · 2025-10-18T17:14:13Z

⚠️ 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 Discourse for more information.

⚠️ 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 Discourse for more information.

Please also make your email public. It is a requirement for contributing to libc++/llvm.

I have disabled that checkbox.

but I believe the bot comment hasn't been updated since the first commit

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

H-G-Hristov · 2025-10-19T03:44:30Z

libcxx/docs/ReleaseNotes/22.rst

 - P3060R3: Add ``std::views::indices(n)`` (`Github <https://llvm.org/PR148175>`__)
 - P2835R7: Expose ``std::atomic_ref``'s object address (`Github <https://llvm.org/PR118377>`__)
 - P3168R2: Give ``std::optional`` Range Support (`Github <https://llvm.org/PR105430>`__)
+- P3372R3: ``constexpr map`` (`Github <https://llvm.org/PR134330>`__) (The paper is partially implemented. ``constexpr map`` is implemented in this release)


You don't need to add this release note for a partially implemented paper. You can update the status page though.

I was looking at this PR for a reference:
https://github.com/llvm/llvm-project/pull/137453/files

So Cxx2cPapers.csv already has an entry for it:

llvm-project/libcxx/docs/Status/Cxx2cPapers.csv

Line 107 in f5ae102

"`P3372R3 <https://wg21.link/P3372R3>`__","constexpr containers and adaptors","2025-02 (Hagenberg)","|In Progress|","","`#127876 <https://github.com/llvm/llvm-project/issues/127876>`__",""

and I originally added it here using this as a reference:

llvm-project/libcxx/docs/ReleaseNotes/21.rst

Line 51 in f5ae102

- P3372R3: ``constexpr`` containers and adaptors (`Github <https://github.com/llvm/llvm-project/issues/127876>`__) (``forward_list``, ``list``, ``priority_queue``, ``flat_map``, and ``flat_set`` are implemented)

~~So perhaps should I just remove this line for this review?~~

removed in 483a33b

libcxx/include/__tree

H-G-Hristov · 2025-10-19T03:54:39Z

libcxx/include/__tree

+      // within __insert_unique_from_orphaned_node, the code will fail to compile where the value is not
+      // copy_constructible for runtime execution as well; unless we use `if constexpr`. Given the copy-constructible
+      // code path will be a performance regression, we want to restrict it to only execute during constant evaluation
+      //, we need to delay the template instantiation


Suggested change

//, we need to delay the template instantiation

//, we need to delay the template instantiation.

Nit. Please do this everywhere too.

Added a few . and capitalized first letters of sentences. Rewrote some parts.

69bb9d3

let me know if this is better!

H-G-Hristov · 2025-10-19T03:58:22Z

libcxx/include/__tree

+      // we use copy, and not "move" as the constraint
+      // because we can NOT move from `const key_type`, which is how `value_type` is defined
+      // atleast for map
+      // typedef pair<const key_type, mapped_type> value_type;
+      // so we must copy it
+
+      // const_cast is not allowed at constexpr time.
+      // we get around this by deleting __lhs and creating a new node in-place
+      // to avoid const_cast __lhs.first
+
+      // We create a sfinae wrapper method here, because if the body of the true_type overload for
+      // __assign_value__sfinae() gets template instantiated within __assign_value, the code will fail to compile where
+      // the value is not copy_constructible for runtime execution as well; unless we use `if constexpr`. Given the
+      // copy-constructible code path will be a performance regression, we want to restrict it to only execute during
+      // constant evaluation
+      //, we need to delay the template instantiation


This is a bit formatted oddly, could you please update it and add punctuation, e.g (not complete).

Suggested change

// we use copy, and not "move" as the constraint

// because we can NOT move from `const key_type`, which is how `value_type` is defined

// atleast for map

// typedef pair<const key_type, mapped_type> value_type;

// so we must copy it

// const_cast is not allowed at constexpr time.

// we get around this by deleting __lhs and creating a new node in-place

// to avoid const_cast __lhs.first

// We create a sfinae wrapper method here, because if the body of the true_type overload for

// __assign_value__sfinae() gets template instantiated within __assign_value, the code will fail to compile where

// the value is not copy_constructible for runtime execution as well; unless we use `if constexpr`. Given the

// copy-constructible code path will be a performance regression, we want to restrict it to only execute during

// constant evaluation

//, we need to delay the template instantiation

// We use copy, and not "move" as the constraint because we can NOT move from `const key_type`, which is how `value_type` is defined

// atleast for map

// typedef pair<const key_type, mapped_type> value_type;

// so we must copy it

// const_cast is not allowed at constexpr time.

// we get around this by deleting __lhs and creating a new node in-place

// to avoid const_cast __lhs.first

// We create a sfinae wrapper method here, because if the body of the true_type overload for

// __assign_value__sfinae() gets template instantiated within __assign_value, the code will fail to compile where

// the value is not copy_constructible for runtime execution as well; unless we use `if constexpr`. Given the

// copy-constructible code path will be a performance regression, we want to restrict it to only execute during

// constant evaluation, we need to delay the template instantiation.

Added a few . and capitalized first letters of sentences. Rewrote some parts.

69bb9d3

let me know if this is better!

libcxx/test/std/containers/associative/map/map.ops/equal_range_transparent.pass.cpp

H-G-Hristov · 2025-10-19T04:05:35Z

libcxx/include/map

+        constexpr iterator emplace_hint(const_iterator position, Args&&... args); // constexpr since C++26
+    constexpr pair<iterator, bool> insert(const value_type& v); // constexpr since C++26
+    constexpr pair<iterator, bool> insert(      value_type&& v);                                // C++17, constexpr
+since C++26


Suggested change

constexpr iterator emplace_hint(const_iterator position, Args&&... args); // constexpr since C++26

constexpr pair<iterator, bool> insert(const value_type& v); // constexpr since C++26

constexpr pair<iterator, bool> insert( value_type&& v); // C++17, constexpr

since C++26

constexpr iterator emplace_hint(const_iterator position, Args&&... args); // constexpr since C++26

constexpr pair<iterator, bool> insert(const value_type& v); // constexpr since C++26

constexpr pair<iterator, bool> insert( value_type&& v); // C++17, constexpr since C++26

Can you align these comments a bit?

Done in
66b4d6f

Aligned it to each "stanza" / section, let me know if this looks good

libcxx/include/__tree

libcxx/test/std/containers/associative/map/map.nonmember/compare.three_way.pass.cpp

missing double //

vinay-deshmukh force-pushed the vinay-issue-128660-P3372-constexpr-map branch 2 times, most recently from 46d0bb9 to 9ea718f Compare April 7, 2025 22:25

vinay-deshmukh added 9 commits April 9, 2025 20:14

cleanup

b3218a7

Pass compare.pass.cpp

7cfa07f

pass incomplete_type.pass.cpp

7930edd

error: call to deleted constructor of '__node_value_type' (aka 'std::…

2ff98ea

…__value_type<int, int>')

clang-format

27f2bfe

Generate macro version correctly

10f536f

fix unrelated CI failures

1270c3e

pass map.modifiers/emplace.pass.cpp

97b00cd

pass map.modifiers/emplace_hint.pass.cpp

900d449

vinay-deshmukh commented Apr 10, 2025

View reviewed changes

libcxx/include/__utility/pair.h Outdated Show resolved Hide resolved

vinay-deshmukh added 13 commits June 8, 2025 13:09

WIP:Merge remote-tracking branch 'upstream/main' into vinay-issue-128…

71b4ffb

…660-P3372-constexpr-map

at.pass.cpp passes again

f470158

iterator.pass.cpp passes

687ca5f

move_assign.pass.cpp constexpr fixed

eb3c0f8

move_alloc.pass.cpp constexpr fixed, other remains

b5577a6

copy_assign.pass.cpp constexpr fixed, other remains

dda93ff

erase_iter.pass.cpp

ab52bea

fix typo

f9a4e70

map.ops pass

37110f1

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

fedf39b

…P3372-constexpr-map

Partially fix assign_initializer_list.pass.cpp

f3b5970

Fix assign_initializer_list.pass.cpp

1d9e310

fix placement new to use std::addressof

d8095a7

vinay-deshmukh added 3 commits October 16, 2025 06:23

Revert "Remove assert(test());"

3b772fd

This reverts commit 9f931f5. # Conflicts: # libcxx/test/std/containers/associative/map/map.modifiers/insert_node_type.pass.cpp

Fix the sed script

5bba72f

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

57183b4

…P3372-constexpr-map

vinay-deshmukh force-pushed the vinay-issue-128660-P3372-constexpr-map branch from 5c409c9 to 57183b4 Compare October 18, 2025 01:39

Add constexpr to the signature

f2a5a94

vinay-deshmukh requested a review from Zingam October 18, 2025 19:24