Tracking Issue for Vec::push_within_capacity

[the8472]

Feature gate: #![feature(vec_push_within_capacity)]

This is a tracking issue for Vec::push_within_capacity

It enables pushing into a Vec if there is any capacity left and otherwise returns the value. I.e. it avoids implicit resizing. This can be useful when one wants to explicitly control it (e.g. via try_reserve) or uses a Vec in an unsafe manner where moving the elements would be a problem.

Public API

// alloc::Vec

impl Vec<T, A> {
    pub fn push_within_capacity(&mut self, value: T) -> Result<(), T>;
}

Steps / History

• Implementation: add Vec::push_within_capacity - fallible, does not allocate #89123
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• naming (e.g. push_in_capacity)
• may become redundant due to larger-scale work in RFC: Add more support for fallible allocations in Vec rfcs#3271

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[em-tg]

Would it be possible for push_within_capacity to take self by shared reference? If the backing store is never re-allocated then calling this wouldn't invalidate any references to the Vec's contents, I'd think.

[the8472]

It still needs to bump the length field.

[em-tg]

Wouldn't wrapping the length in UnsafeCell work for that? The public api only exposes the len() getter.

[em-tg]

Ah wait I think I see the issue. You'd lose Sync by doing that. Sorry, still pretty new to Rust and just thought I'd ask!

[tiby312]

I think this is a great feature. I often find myself just assuming my buffer reserving code is working since it is a hard bug to catch when it's not working given push automatically reserves.

[krtab]

Hi!

I think this could enter its FCP:

• RFC: Add more support for fallible allocations in Vec rfcs#3271 is not merged. Parts of it were released as a crate, part of it has been delegated to keyword genericity (so, pretty far away)
• The code of add Vec::push_within_capacity - fallible, does not allocate #89123 has been in nightly for a year and received no criticisms afaict
• This API can prove very useful to add optimization hints by marking its Err return value as unreachable

[kornelski]

I find it very useful, and have similar helpers in my codebases. It generates much leaner code than the usual push when the optimizer can't be convinced that the capacity is sufficient (e.g. when it's calculated in a non-trivial way, or the vec-appending code isn't all inlined). It has a useful side effect of verifying that a sufficient capacity has been precalculated, and there aren't unexpected reallocations.

However, just push is not enough. I'm missing similar functionality for extend_from_slice — _within_capacity.

[elichai]

I hope this isn't completely useful,
But is there some kind of mechanism we can use to allow all these try_ functionality without adding dozens of try_ in all collections, could being generic over the effect of try allow something like this?

[Darksonn]

How about insert_within_capacity? It's very non-trivial to reimplement insert without an allocation codepath.

[the8472]

Sounds interesting, though a bit niche (just like this method). If you have a use-case you should file an ACP for it.
Ditto @kornelski

If you several a bunch of methods like this in mind then we could perhaps bundle them to see if there are some overarching things to consider.

[zeroflaw]

Now that it's possible to do a try_reserve, I find myself using these extension methods a lot more often. push_within_capacity here gives us an escape hatch to do an unchecked_push.
I included an example of insert_within_capacity and try_insert_within_capacity

// ===== trait Ext =====

pub trait Ext<T> {
    /// Appends an element to the back of a collection without checking
    /// if the collection has enough capacity.
    ///
    /// # Safety
    /// The user must ensure that `self.len() < self.capacity()`.
    ///
    unsafe fn unchecked_push(&mut self, value: T);

    /// Removes the last element from a vector without checking
    /// if the collection is empty.
    ///
    /// # Safety
    /// The user must ensure that `self.len() != 0`.
    ///
    unsafe fn unchecked_pop(&mut self) -> T;

    /// Inserts an element at position index within the vector, 
    /// without checking if the collection has enough capacity, 
    /// or the position index is out of bounds.
    /// all elements after the position index are shifted to the right. 
    /// 
    /// # Safety
    /// The user must ensure that `index <= self.len()` and `self.len() < self.capacity()`
    ///
    unsafe fn unchecked_insert(&mut self, index: usize, value: T);


    /// Inserts an element at position index within the vector, 
    /// if there is sufficient spare capacity, otherwise an error is returned with the element.
    /// 
    /// # Errors
    /// if insufficient capacity, an error is returned with the element
    /// 
    /// # Panics
    /// Panics if index > len.
    /// 
    fn insert_within_capacity(&mut self, index: usize, element: T) -> Result<(), T>;

    /// Inserts an element at position index within the vector, 
    /// if there is sufficient spare capacity, and index is within bounds,
    /// otherwise an error is returned with the element.
    /// 
    /// # Errors
    /// if insufficient capacity, or the index is out of bounds, an error is returned with the element
    /// 
    fn try_insert_within_capacity(&mut self, index: usize, element: T) -> Result<(), T>;
}

// ===== impl Vec =====

impl<T> Ext<T> for Vec<T> {
    unsafe fn unchecked_push(&mut self, value: T) {
        std::hint::assert_unchecked(self.len() < self.capacity());
        self.push_within_capacity(value).unwrap_unchecked();
    }

    unsafe fn unchecked_pop(&mut self) -> T {
        std::hint::assert_unchecked(!self.is_empty());
        self.pop().unwrap_unchecked()
    }
    
    unsafe fn unchecked_insert(&mut self, index: usize, element: T) {
        std::hint::assert_unchecked(index <= self.len());
        std::hint::assert_unchecked(self.len() < self.capacity());
        self.insert(index, element);
    }
    
    fn insert_within_capacity(&mut self, index: usize, element: T) -> Result<(), T> {
        if self.len() == self.capacity() {
            return Err(element);
        }
        unsafe { std::hint::assert_unchecked(self.len() < self.capacity()) };
        self.insert(index, element);
        Ok(())
    }
    
    fn try_insert_within_capacity(&mut self, index: usize, element: T) -> Result<(), T> {
        if self.len() == self.capacity() || index > self.len() {
            return Err(element);
        }
        unsafe { self.unchecked_insert(index, element); }
        Ok(())
    }
}

[kornelski]

There are two ways to implement such functionality, and I'm not sure which way to propose:

1. Add more methods on Vec with a _within_capacity version. I think this would work well, but I've got a lot of pushback about adding try_ versions of methods. Rust doesn't have a feature like Swift's function naming/overloading to keep all of these functionality tweaks elegantly together.

2. A reference type like FixedCapacityVecView<'_> that imitates interface of Vec, but without reallocation. This seems like a big addition, especially if it will duplicate most of Vec's interface, but most users will probably only need push and extend.