ACP: Add a fallible version of `Vec`

[ChrisDenton]

Proposal

Problem statement

Currently any failure to allocate in Vec methods will call the global OOM handler which diverges (try_reserve is the one stable exception), Some users want to be able to handle errors instead.

Motivating examples or use cases

There are a number of environments where handling allocation errors is expected. E.g. Linux, some embedded systems, high reliability systems or simply if you want to optimistically attempt a large allocation and fallback to a smaller one if it fails (assuming the platform doesn't have overcommit enabled). See also the related links section.

In Vec if you want to handle allocation failures currently you need to explicitly call try_reserve before anything that may allocate or otherwise check that the spare capacity is large enough to not require allocation.

Solution sketch

Note: this ACP is focused on Vec but I expect this to be applicable to other collections. But I'll leave that to future ACPs if this is accepted.

// in alloc::collections::fallible
struct Vec<T> { ... }
impl<T> Vec<T> {
    pub const fn new() -> Self;
    pub fn with_capacity(capacity: usize) -> Result<Self, AllocError>;
    pub fn reserve(&mut self, additional: usize) -> Result<(), AllocError>;
    pub fn push(&mut self, v: T) -> Result<(), AllocError>;

    ... a bunch of other Vec methods ...

    // Zero cost cast
    pub fn to_infallible(self) -> std::vec::Vec<T>;
}

And on the original std::vec::Vec:

// in alloc::vec
impl Vec<T> {
    // Zero cost cast
    pub fn to_fallible(sellf) -> alloc::collections::fallible::Vec<T>;
}

Alternatives

Make the allocator itself indicate whether it's fallible or infallible. E.g. see #797 or some variation thereof. Currently allocators are always fallible (as is e.g. malloc, by API at least) and its up to users of them to call handle_alloc_error if they want to wrap an allocator in an infallible API.

Have lots of try_ versions of existing methods on std::vec::Vec.

Links and related work

The linux kernel uses its own allocator types: https://elixir.bootlin.com/linux/v7.0.10/source/rust/kernel/alloc/kvec.rs#L325. If there was an std type (and some way to pass flags to a custom allocator) then they could more simply wrap the standard library type.

While the situation isn't exactly comparable, there is precedence for creating a fallible and non-fallible version of a type. We have std::sync::Mutex and std::sync::nonpoison::Mutex.

A fallible version of Vec has been favourable discussed by libs-api a number of times over the years so I think it should be part of the conversation now that Allocator is getting a lot of attention (although, to be clear, other opinions have also been expressed).

E.g. way back in 2021:

If we introduce separate types (VecFallible, HashMapFallible, needs much better naming), we can use the same name for every method (VecFallible::push would return Result, Vec::push is self.inner.push(...).unwrap() or equivalent).

Or more recently:

I'd still like to have [fallible functions] but under something like .as_fallible_vec() and have them under a separate type.

I should also add that this ACP was prompted by #797 and should be consider mutually exclusive with that.

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.

[programmerjake]

while we're at it maybe we can fix warts in Vec's API e.g. have FallibleVec::<T>::push return Result<&mut T, AllocError>

[programmerjake]

I think we'll want to guarantee that Vec<T, A> and FallibleVec<T, A> have the same ABI, so you can do things like cast between &mut [Vec<T, A>] and &mut [FallibleVec<T, A>]

[kennytm]

Will this new fallible::Vec implement traits which has no way to expose the AllocError, such as Extend<T> and FromIterator<T>? Clone? And I suppose the likes of From<&[T]> will all become TryFrom<&[T]>.

[ChrisDenton]

I think we'll want to guarantee that Vec<T, A> and FallibleVec<T, A> have the same ABI, so you can do things like cast between &mut [Vec<T, A>] and &mut [FallibleVec<T, A>]

Absolutely.

Will this new fallible::Vec implement traits which has no way to expose the AllocError, such as Extend<T> and FromIterator<T>? Clone? And I suppose the likes of From<&[T]> will all become TryFrom<&[T]>.

I do not think this should implement any infallible traits. That is what the cheap conversion to the old Vec is for. It could implement Try versions of traits but I think an MVP can punt on creating those. Though I'm happy to be corrected.

[okaneco]

Related work, closed RFC for adding try_* methods to Vec.
rust-lang/rfcs#3271
rust-lang/rust#95051

Aiming toward the concept of "make invalid state unrepresentable," I think having separate fallible collections is a better solution than mixing fallible and infallible methods on the collections we have today. My experience with try_reserve is that it's not ergonomic to use by itself, so I prefer a solution like this ACP where users don't have to re-implement their own wrappers and won't mistakenly use an infallible method.

It could implement Try versions of traits but I think an MVP can punt on creating those.

I don't have a specific design in mind, but TryExtend seems like something that could be desirable for performance reasons when appending in bulk. Not necessary for the MVP though.

[programmerjake]

TryFromIterator would also be useful for collecting into an array, so I'd like any design for that to support arrays and not just assume the only possible error is AllocError. It could also be useful for reporting collisions when collecting into a map or set.