Following up from https://rust-lang.zulipchat.com/#narrow/stream/197181-t-libs.2Fwg-allocators/topic/Collections.20beyond.20box.2C.20allocation.20fallibility . I've done a preliminary rebase of rust-lang/rust#52420 at https://github.com/QuiltOS/rust/tree/allocator-error (old versions are https://github.com/QuiltOS/rust/tree/allocator-error-old, https://github.com/QuiltOS/rust/tree/allocator-error-old-1, etc.)

If we add an associated Err type to Alloc, we can set it to ! to indicate allocation is infallible (panics, aborts, etc). Allocators should be written with a non-empty Alloc::Err, but a AbortAdapter<A> is provided which calls handle_alloc_error so for<A: Alloc> <AbortAdapter<A> as Alloc>::Err = !.

This has many benefits.

1. We get try_ and traditional versions of every collections method that supports fallibility it for no extra cost! This is done by threading the abstract error type. We don't need to duplicate the original method, but can simply do:

   struct Collection<T, A: Alloc = AbortAdaptor<Global>> { ... }
   
   impl<T, A> Collection<T, A> {
     fn try_foo(&self) -> Result<T, A::Err> {
       ...
     }
   }
   
   impl<T> Collection<T> { // A::Err = !
     fn foo(&self) -> T {
       let Ok(x) = self.try_foo();
       x
     }
   }

   The legacy version would just call the non-try_ version and panic-free unwrap the Result<T, !>. Yes we have twice as many methods, but don't have any duplicated logic.

2. Any container (or individual method on the container) that can not handle fallible allocation can require Err = ! so as not to hold back the alloc-parameterization and fallible-allocation-recovery of the other containers. I.e. this proposal reduces the risk of refactoring the collection in that there's no all-or-nothing bifurcation of outcomes.

3. Polymorphism all the way up. Just as collections are fallibility-polymorphic with the try_methods (perhaps they should be renamed to indicate the are not always fallible), other crates using collections can also use A::Err to also be fallibility-polymorphic. This avoids an ecosystem split between those that want and don't want to manually deal with allocation failure.

Note that this seems to impose a downside of each collection having to commit to a fallibility up front. But since AbortAdapter can be #[repr(transparent)], we can freely cast/borrow between the two.

Original unclear version for posterity:

If we add an associated Err type to Alloc, we can set it to ! to indicate allocation is infallible (panics, aborts, etc). This has two purposes:

1. We instantly get try_ versions of every method that supports it for free by threading a non-empty error type. The legacy version would just call the non-try_ version and unwrap the Result<T, !>. Yes we have twice as many methods, but don't have any duplicated logic.

2. Any container (or individual method on the container) that can not handle fallible allocation can require Err = ! so as not to hold back the alloc-parameterization and fallible-allocation-recovery of the other containers.