Tracking Issue for constifying some {BTreeMap,Set} functions

[LG3696]

This tracks stabilization of the const_btree_new feature, which allows calling the below in a constant expression:

• BTree{Map,Set}::new() (Make BTreeMap::new and BTreeSet::new const #71839)
• BTree{Map,Set}::{len,is_empty}() (Constantify more BTreeMap and BTreeSet functions #78581)

Steps

• Implementation Make BTreeMap::new and BTreeSet::new const #71839
• Stabilization PR

[a1phyr]

Can the following functions be added to the top statement ?

• BTreeMap::len
• BTreeMap::is_empty
• BTreeSet::len
• BTreeSet::is_empty

[tvladyslav]

@jonas-schievink @JohnTitor , could you please start FCP?
I'm about to add closing PR. There were some tests added in #71839 and #78581 but now they are gone. Should I add more tests?

[Noratrieb]

What's the state of this?

[JohnTitor]

cc @rust-lang/libs-api --^

[Amanieu]

I'm 100% in favor of making BTreeMap::new const, but len/is_empty seem a bit much given that we don't even have those as const on Vec.

So I'm starting an FCP just for constifying the new function.

@rfcbot fcp merge

[rfcbot]

Team member @Amanieu has proposed to merge this. The next step is review by the rest of the tagged team members:

• @Amanieu
• @BurntSushi
• @dtolnay
• @joshtriplett
• @m-ou-se
• @yaahc

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[jplatte]

len/is_empty seem a bit much given that we don't even have those as const on Vec.

This seemed wrong to me, so I looked it up. Apparently the [T] methods are const, but Vec has its own len and is_empty¹ that aren't const. I also discovered two rustdoc bugs while looking this up 😅

¹ so vec.len() is not exactly equivalent to (*vec).len() for some reason

[dtolnay]

for some reason

Actually a very good reason, if I recall correctly. vec.len() can get the len right out of the Vec's len field without materializing a reference to the heap data. Whereas taking the &Vec, derefing it to &[T], and then getting len via slice's len() method would needlessly invalidate all outstanding raw pointers into the heap data which are later used for mutable access.

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

This will be merged soon.

[Stebalien]

This was stabilized in 1.66.

[Amanieu]

Actually len and is_empty are still const-unstable, keeping this open.

[Stebalien]

Ah, sorry about that.

[bitdivine]

Hello all. This looks interesting, but is it possible to create a const BTreeMap with data? As far as I can see, new() is the only const fn for BTreeMap.

[jplatte]

No, that depends on #79597, which doesn't even have an experimental implementation yet AFAIK.

[bitdivine]

Thanks for the info and pointer, @jplatte .

[bitdivine]

I do wonder why this is ties to heap allocation though. A const, immutable BTree map would not have to live on the heap. I guess my mental model of const mem = a heap computed at compile time and immutable thereafter is wrong.

[oli-obk]

This is about the heap emulation during compile time. We need to figure out some way to store the data while doing const evaluation