Tracking issue for #![feature(entry_insert)]

[passcod]

This is a tracking issue for the Entry::insert_entry method on HashMap and BTreeMap introduced in #60142 (comment).

• Implementation for HashMap: Implement (HashMap) Entry::insert as per #60142 #64656
  • Stabilised in 1.59: Stabilise entry_insert #90345 Re-stabilised in 1.83: Stabilize entry_insert #130290
    • De-stabilized in Destabilise entry_insert #94105

   impl<'a, K, V> Entry<'a, K, V> {
      pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {…}
  }

• Implementation for BTreeMap: btree: add {Entry,VacantEntry}::insert_entry #133042
  • Stabilization

[TethysSvensson]

This does not appear to be compatible with #44286, as the following code will panic.

#![feature(map_entry_replace, entry_insert)]
use std::collections::HashMap;

fn main() {
    HashMap::new().entry(0).insert(0).replace_key();
}

It seems to me that the two APIs are fundamentally incompatible, or at least they are currently incompatible without panicking.

The API in #44286 assumes that an OccupiedEntry will always refer to two keys, the existing one and the one used for the lookup, while this feature will break that assumption. In fact, the key field in OccupiedEntry and RustcOccupiedEntry in hashbrown could be a K instead of an Option<K> if this API was not supported.

[TethysSvensson]

It seems to me that it is a bit silly to use an Option to track at run-time what we should already know at compile time. Wouldn't it make more sense to have a different type from OccupiedEntry, which did not contain a key?

I could imagine this would also be useful as a stepping stone towards implementing something like rust-lang/rfcs#1769.

[passcod]

 if this API was not supported.

I'm a bit rusty with this PR, but am I correct in saying that the entry_insert API is impossible to replicate from user code, while the map_entry_replace one is, as per the original PR? (Albeit not with the same efficiency) Of course I'd much rather a solution that supports both uses is found

[TethysSvensson]

@passcod I believe you mostly are correct on both parts of your statement.

I do not think the Entry::insert function can be implemented in safe rust, as it allows the creation of an OccupiedEntry without an associated key. I cannot see how it would be possible to do that in safe rust.

The OccupiedEntry::replace_entry and OccupiedEntry::replace_key functionality can be implemented in safe rust, using a combination of OccupiedEntry::remove and HashMap::insert.

However I do not think it is possible to implement it as a function in safe rust. You would need to pass both the HashMap and the Entry as an argument in the same function, however the lifetime on the Entry prevents use of the HashMap until the Entry has been dropped.

[Nokel81]

Why isn't the signature of this method pub fn insert(self, value: V) -> &'a mut V like the or_*** methods?

[passcod]

The motivation is to be able to reference the key (or the entry, more generally) even after inserting a value.

[lamafab]

The current implementation is kind of limited, you cannot do something like this:

fn insert(&mut self, msg: Message) -> &Message {
  self.map.entry(msg).insert(0).key()

error[E0515]: cannot return value referencing temporary value

It would be convenient if you could implement this in a way which says "insert the key and return a reference of the key from within the HashMap".

Currently, you'd have to do this ugly work-around:

fn insert(&mut self, msg: Message) -> &Message {
  let msg2 = msg.clone();
  self.map.entry(msg).insert(0); // or just `.or_insert()`
  self.map.get_key_value(&msg2).unwrap().0

[shepmaster]

@lamafab I think you want a function like

impl<'a, K, V> OccupiedEntry<'a, K, V> {
    pub fn into_key(self) -> &'a K { /* ... */ }
}

[joshtriplett]

We reviewed this in today's @rust-lang/libs-api meeting.

We'd like to see a similar method added to BTreeMap::Entry, but that's not a blocker for stabilizing the method for HashMap::Entry.

We feel like this should be named insert_entry, rather than just insert, since it returns an OccupiedEntry, unlike the similar insert method that returns just a value.

Could you rename this method to insert_entry, and then provide a stabilization PR?

Could you also consider adding an insert_entry method to VacantEntry?

[passcod]

Heyho! Awesome 🦀 I'll try to get to it sometime this month.

Edit: still on my radar, probably end of October.

[bluecheetah001]

I recently needed something similar to lamafab where I wanted a reference to the key in the map after inserting
I was wondering if insert_entry could instead return a new type which I will call EntryRef.
EntryRef.getKey could use the map's lifetime
EntryRef.replace_key wouldn't exist as it doesn't own a key

OccupiedEntry.insert_entry could return (K, EntryRef) or something analogous
VacantEntry.insert_entry could return EntryRef
Entry.insert_entry could return (Option<K>, EntryRef) or something analogous

[dhardy]

Suggestion: replace insert_entry with simpler insert as @Nokel81 suggested above: pub fn insert(self, value: V) -> &'a mut V

This covers most uses (anything not needing to access the key), and since the only motivation for this method is convenience, there's no need to worry about that case. This then removes the conflict with #44286.

[passcod]

Didn't want to jump the horse during the unstabilisation moment but I'm unfortunately not terribly interested in this feature anymore, so am unsubbing from it all. This has nothing to do with anyone involved and only to do with me/time, and I generally/superficially agree with the concerns raised for the stabilisation revert. Thanks for all the fish 🐬

[m-ou-se]

We briefly discussed this issue last week in the Library API meeting. We'd like to see a more complete proposal for an alternative API, such as the EntryRef idea that was mentioned before.

[maboesanman]

One very odd part of this api is that insert_entry gives you an OccupiedEntry but remove_entry doesn't give you a VacantEntry

This could be useful in situations where you remove an item, but may or may not need to replace it. In this case you can use .entry(k).remove_entry(), then keep the resulting VacantEntry around for use later.

Useful additions to this api would be next_occupied and prev_occupied on btree_map::Entry, and implementations of all of these functions on HashSet and BTreeSet, though that is likely a question for a more stable version of this api.

On the topic of key ownership, I think the most consistent approach is to have the OccupiedEntry borrow it's key from the collection, and VacantEntry own its key. have the entry method be generic over an std::borrow::ToOwned type for the key. At the point entry needs to decide between OccupiedEntry and VacantEntry, it will either drop the search key in favor of borrowing the key from the collection (for occupied) or call to_owned on the search key and move it into the entry (for vacant).

insert_entry on VacantEntry will move the key from the entry into the collection, borrow it, and store the borrow in an OccupiedEntry. remove_entry on OccupiedEntry will move the key from the collection to the entry.

insert_entry on Entry::OccupiedEntry is an in place change to the value, so that doesn't really need to do anything special with keys, and remove_entry on Entry::VacantEntry could just return a None variant.

one final note: I am in general not a fan of any method with a _entry suffix that returns anything but an entry. things which return (&K, &mut V) seem mostly like half measures whose functionality would follow from returning a proper Entry.

[maboesanman]

I've created a mockup for what I think this api could be: https://github.com/maboesanman/InPlace
and cargo docs here: https://maboesanman.github.io/InPlace/in_place/

curious what people's thoughts are.

[mcclure]

Am I reading correct there is no movement on this since March? This seems like an unusual omission from the stable API (right now Entry can conditionally insert but not unconditionally insert). I understand the intent of the API is for inserting when key is not present, but there are reasonable purposes for unconditional insert as well, for example, checking the value then inserting if a condition is met:

// Code fragment I actually wrote today, before discovering insert_entry is nightly only
fn map_write_if_greater<K,T>(map:HashMap<K,T>, key:K, v:T) where K:Eq+std::hash::Hash, T:PartialEq+PartialOrd {
	let entry = map.entry(key);
	if match entry { Entry::Vacant(_) => true, Entry::Occupied(v2) => v>*v2.get()} {
		entry.insert_entry(v); // Avoid second hash lookup
	}
}

It seems like the holdup here is not whether the function should go in, but rather disagreement over the return value / naming; but it's been a long time without that disagreement being resolved. (I personally agree with nokel that pub fn insert(self, value: V) -> &'a mut V is superior to insert_entry -> Occupied(T), but also I don't personally care that much as long as the feature is present.)

[Ekleog-NEAR]

@passcod In the top-comment, the checked checkbox writing that insert_entry was stabilized in 1.59 should be unchecked: it was destabilized in #94105 (just writing that so other people don’t feel compelled to try it out on play.rlo because the docs and this tracking issue currently have different opinions on whether this is stable yet)

[joshtriplett]

Since #44286 is in FCP to close now, I'm going to FCP this one to stabilize:

@rfcbot merge

[rfcbot]

Team member @joshtriplett 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

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.

[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.

[passcod]

I'm not sure that a new stabilization PR has been done for this? Sorry if this is normal process, I just got pinged on the release note issue and was confused.

[slanterns]

I think there is no stabilization PR yet.

[Amanieu]

A stabilization PR needs to be submitted for this, anyone can do it.