ACP: Vec::push_mut and Vec::insert_mut

[chorman0773]

Proposal

Problem statement

Currently, there is no safe, infallible way to obtain an particular element in a Vec: This is reasonable because there may not be any elements in a Vec. However, an occasionally useful operation is "Insert an Element and get that Element" which is infallible (modulo allocation failure). Currently, performing this ad-hoc requires inserting an element, and doing some form of unwrap on .last() which is excessively verbose for what could reasonably be a one-liner.

Motivating examples or use cases

In the visitor pattern, elements are built from another input format in groups. The two common designs are either to return some visitor that contains internal state or pass that internal state to an Fn of some kind - in either case, the state will almost always borrow (probably mutably) from the internal state of the current visitor. Where a subset of elements can be visited multiple times, this may involve borrowing new elements of a Vec or other extensible data structure. As an example, a simple visitor that accepts rust arrays might look like

struct ArrayVisitor(Vec<SomeExpr>, /* other state */);

struct ExprVisitor<'a>(&'a mut SomeExpr, /* other state */);

impl ArrayVisitor {
     fn visit_array(&mut self) -> ExprVisitor<'_> {
           // ExprVisitor(self.0.push_mut(/* init state for expr */), /* other state */) // One-liner using `push_mut`
           self.0.push(/* init state for expr */); // Two lines of code when this could just be inlined
           // `.last_mut()` is guaranteed to be Some unless the stdlib just decided not to do the `.push()`
           ExprVisitor(self.0.last_mut().unwrap(), /* init state for expr */) // ugly .unwrap or worse: .unwrap_unchecked()
     }
}

Solution sketch

impl<T, A: Allocator> Vec<T, A> {
     /// Inserts `val` into the end of the [`Vec`] and returns a reference to it in the array
     pub fn push_mut(&mut self, val: T) -> &mut T;
     /// Inserts `val` into the [`Vec`] at `idx`, and returns a reference to it in the array
     /// # Panics
     /// Panics if `idx > self.len()`
     pub fn insert_mut(&mut self, idx: usize, val: T) -> &mut T;
}

insert_mut is included for completeness with Vec::push_mut and Vec::index, and is less important to this proposal than the base Vec::push_mut

(The A: Allocator in the trait bound is to indicate that, albeit likely obviously, the particular choice of allocator does not interfere with the API and doesn't depend on stabilizing allocator_api as-is)

Alternatives

A few alternatives could be panicking and/or unchecked versions of <[T]>::{first,last}. While these remove the need to unwrap() an option, they still require the same justification of infallibility as the .unwrap() and also haven't reduced a two-line operation to a clean one-liner where the justification is encapsilated by the library.

This can also be an extension trait or free function in another using a canonical implementation, like

impl<T> PushMutExt for Vec<T> {
     fn push_mut(&mut self, val: T) -> &mut T {
         let n = self.len();
         self.push(val);
         &mut self[n]
     }
     fn insert_mut(&mut self, idx: usize, val: T) -> &mut T {
          self.insert(idx, val);
          &mut self[idx]
      }
}

However a direct implementation would be more readily able to take advantage of new support in Vec.

Links and Related Work

Option has .insert, .get_or_insert, and .get_or_insert_with, and via the Entry api std::collections::HashMap has .insert, .or_insert, and .or_insert_with. These methods also see use in visitor pattern implementations when you may have a single element or have associated elements.

In C++, std::vector returns either an iterator (insert and emplace) or a reference (emplace_back) on insert, emplace, and emplace_back (though as I've discovered, not on push_back). For background, an iterator in C++ is a handle to a particular element or sequence of elements that can be dereferenced (in the case of a vector, other than std::vector<bool>, this is a simple pointer or a thin wrapper arround a pointer).

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[scottmcm]

push_mut is already approved; see rust-lang/rust#135974.

[pitaj]

I think this makes sense for the same reason as push_mut. Are there any other insertion operations on Vec that don't return &mut? The only one I could find with a quick look was push_within_capacity, which probably can't be made to return &mut without borrow checker issues.

[Amanieu]

We discussed this in the @rust-lang/libs-api meeting. As mentioned, push_mut is already approved and tracked in rust-lang/rust#135974. We would be happy to add insert_mut under the same tracking issue. Additionally, these methods could also be added to VecDeque.

[balt-dev]

I'm more than happy to implement insert_mut and the respective functions on VecDeque! (See rust-lang/rust#135975.)
Let me know if you want that to happen.

[traviscross]

We want that to happen, as per @Amanieu's message.