Bound infallible methods on alloc types behind `A: InfallibleAllocator`

Proposal

Problem statement

There should be a way to allow allocation operations which panic (or equivalently invoke the alloc error handler) to be allowed if the allocator wants this (presumably because it can be assumed to be as good as infallible in practice).

Motivating examples or use cases

In low-level contexts, it is often useful to gracefully handle allocation failures without panicking. This makes the current situation with rust rather precarious: the only way to handle them is to write your own collection types entirely, which is a lot of effort and it is very hard to get both ecosystem integration for them and write correct implementations for them.

There are many examples of this kind of need:

• Rust for linux has APIs which return AllocError inside of their custom collection types
• Maestro, which is a hobby OS project, does the same with their own custom collection types
• My hobby kernel also more or less does this but I don't have the sources available (and I only implement a subset of collection types).

Right now the only API like this in the standard library at all (I think?) is try_reserve which is opt-in and is extremely rough to work with (you have to make sure you definitely did everything right or else you can have subtle bugs that are inherently extremely hard to test for).

Solution sketch

• One new trait, defined as trait InfallibleAllocator: Allocator {} should be added.
  • This trait can be safe because crashing is not unsafe.
• The trait bounds on all Box/Vec/etc methods which allocate using the allocator API should require the InfallibleAllocator bound if they can call the alloc error hook.
• Possibly, the InfallibleAllocator API could (and maybe even should) be extended to provide variants of the allocation functions which implicitly call the alloc error hook if this can be implemented more efficiently by the allocator.
  • Although if this is implemented, then obviously InfallibleAllocator would have to be unsafe.

Alternatives

• Do nothing and let libraries take up the slack. This may work but it would likely end up with some crate reimplementing collections from the standard library (possibly incompatibly).
• Create separate FallibleAllocator and InfallibleAllocator traits which are both subtraits of Deallocator. This would allow for push to be fallible or infallible depending on which allocator is in use. Although I'm not sure how good this would be for ergonomics.
• Make all allocator_api usage fallible. This has worse ergonomics and many users don't really care about OOM conditions.
• Add a bunch of try_* methods and have a clippy lint or something to help people avoid infallible methods if they want to. This is a bit tricky on an ecosystem level though (do you just run clippy on your deps? That sounds, unfun. What about transitive dependencies? etc).
• Probably others I'm missing.

Links and related work

As linked above:

• Rust for linux's collections
• maestro's collections

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.

Start by reviewing the allocator API and existing Box/Vec allocation methods, especially try_reserve, against the proposed InfallibleAllocator bounds. Compare the Rust for Linux and Maestro collection examples linked in the issue. Done would require a libs-api decision on the problem and a concrete approved API design.