Add Allocator support for `String`

[zachs18]

Proposal

rust-lang/rust#101551

Add an unstable, defaulted generic parameter to alloc::string::String to allow use with custom allocators under #![feature(allocator_api)], and generalize most implementations on String to be generic over the allocator.

(There's a tracking issue rust-lang/wg-allocators#7 on wg-allocators, so I wasn't sure if this needed an ACP. I made one just to be safe.)

Problem statement

Currently, Vec and Box have a second, unstable, defaulted generic parameter A: Allocator = Global, allowing them to support custom allocators. String does not currently have this, so it does not yet support custom allocators.

Motivation, use-cases

Part of the effort to expand allocator_api to support more collection types. It could be useful to allow using common container types with different allocators that are better suited to different allocation patterns.

Solution sketches

Add an #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global generic to alloc::string::String, alloc::string::FromUtf8Error, and alloc::string::Drain, and make most inherent functions and trait implementations generic over this parameter.

Also make some corresponding non-allocator-generic functions and implementations on Box<str> allocator-generic.

• removed unstable trait implementations.
  • StructuralEq for String: String previously used derive(Eq), but manually implemented PartialEq. To prevent an A: Eq bound, I removed the derive and replaced it with a manual impl Eq without that bound. It should not be observable on stable, because String does not implement StructuralPartialEq, which is also required for structural matching.
    • Manual impl<A: Allocator> StructuralEq for String<A> {}, etc. can be added if necessary.
  • StructuralEq/StructralPartialEq for FromUtf8Error: FromUtf8Error previously used derive(PartialEq, Eq). However, it is not possible to get a value of type FromUtf8Error in constant evaluation on stable, so there is no way to construct anything that could even be used as a structural match pattern, so I don't think these removals are observable.
• Added allocator-generic inherent String functions (that already exist for Vec)
  • new_in/with_capacity_in
  • from_raw_parts_in/into_raw_parts_with_alloc
  • allocator
• Inherent functions which are not (currently) made allocator-generic
  • new/with_capacity/from_utf16/from_utf16_lossy: These could use A: (~const) Default, but seemed out of scope. Also, corresponding Vec functions are not allocator-generic.
  • from_utf8_lossy: This returns a Cow<str>, which is not allocator-generic.
  • from_raw_parts/into_raw_parts: These are tied to the global allocator.
• Added trait implementations that already are allocator-generic for Vec/[T]-like.
  • Clone for Box<str, A> where A: Clone
• Added trait implementations that are not yet allocator-generic for Vec/[T]-like
  • Borrow/BorrowMut<str> for String<A>
  • From<String<A>> for Rc<str>/Arc<str> edit: These have been removed from the linked PR to make room for future From<String<A>> for Rc<str, A>-like impls.
• Trait implementations which are not (currently) made allocator-generic:
  • Default where A: Default: this would require making Global implement const Default, which is probably fine, but seemed out-of-scope. Also, the corresponding Vec implementation is not allocator-generic.
    • Likewise for impl const Default for Box<str> (and Box<[T]>).
  • From<&String> for String: Unclear if it should be From<&String<A>> for String<A> where A: Clone or From<&String<A2>> for String<A1> where A1: Default
  • FromStr, From<&str-like>, From<char>, FromIterator<_>: Could be for String<A> where A: Default but seemed out-of-scope. Also, corresponding Vec implementations are not allocator-generic.
    • Likewise for From<&str> for Box<str> and From<&[T]> for Box<T> where T: Clone
• Other APIs which are not (currently) made allocator-generic
  • APIs involving CString, e.g. CString::into_string
  • APIs outside the alloc crate, e.g. std::io::Read::read_to_string, AsRef<OsStr> for String, ToSocketAddrs for String

All unmentioned inherent functions and trait implementations on String, FromUtf8Error, and Drain are made allocator-generic (with appropriate bounds, e.g. A: Allocator + Clone for String::split_off).

Several implementations involving Box<str> are also made allocator-generic

• From<Box<str, A>> for Box<[u8], A>
• From<Box<str, A>> for String<A>

From<String<A>> for Box<str, A> is not added currently because of trait coherence rules (help?).

Links and related work

• [WIP] Add support for custom allocator for String rust#101551
• Add support for custom allocator for (C)String rust#79500 (closed in favor of 101551 above)
• Tracking Issue for structs which needs an allocator wg-allocators#7
• Add support for custom allocators in Vec rust#78461
• Future work to do similar for CString and other containers.

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two.

[Amanieu]

We discussed this in the libs meeting. We're happy for this to move forward! To avoid splitting attention, the rest of the API discussion should occur on the PR.