Tracking Issue for structs which needs an allocator

[TimDiekmann]

This WG wants to associate an allocator for all suitable structs. This issue tracks those structs, which are covered so far (non-exhaustive list):

• Box<T, A>: Support custom allocators in Box rust#77187
• Rc<T, A>: Add support for allocators in Rc & Arc rust#89132
• Arc<T, A>: Add support for allocators in Rc & Arc rust#89132
• String<A>: [WIP] Add support for custom allocator for String rust#101551
• CString<A>: Add support for custom allocator for (C)String rust#79500
• Vec<T, A>: Add support for custom allocators in Vec rust#78461
• VecDeque<T, A>: Add support for custom allocator in VecDeque rust#86595
• LinkedList<T, A>: Add support for allocators in LinkedList rust#103093
• HashMap<K, V, S, A>: Parametrize RawTable, HashSet and HashMap over an allocator hashbrown#133
• BTreeMap<K, V, A>: BTreeMap: Support custom allocators (v1.5) rust#98103
• HashSet<T, S, A>
• BTreeSet<T, A>: BTreeMap: Support custom allocators (v1.5) rust#98103
• BinaryHeap<T, A>: Make BinaryHeap parametric over Allocator rust#99339
• (OsString<A>)
• (PathBuf<A>)

[Ericson2314]

I've started in rust-lang/rust#60703 .

[ErichDonGubler]

@ObsidianMinor has asked about the Clone trait needing to also be modified:

(38183) Allocator aware std traits - rust-lang - Zulip

There's a number of traits that implicitly allocate to the global allocator like str ToOwned making a String<Global> and Clone String<Global> always making another String<Global> which would make it slightly more difficult to move data across allocators.

let  a: String<Global>  =  format!("hello world!");
let  b: String<System>  =  a.clone();  // nope, that's a String<Global>
let  b: String<System>  =  {  // we could do it manually
  let  mut  z: String<System>  =  String::new();
  z.push_str(a.as_str());
  z
};
let  b: String<System>  =  a.clone_in(System);  // or use a trait

let  s: &'static  str  =  "hello world!";
let  t: String<Global>  =  s.to_owned();
let  u: String<System>  =  s.to_owned();  // nope, it's Global again
let  v: String<System>  =  s.to\_owned\_in(System);

Is there an issue yet talking about traits like this?

Any reason this issue couldn't also accomodate Clone and any other traits/method we think of along the way? :)

[lachlansneff]

Thoughts on CloneIn: Clone trait instead of adding an additional clone_in method to `Clone?

[ErichDonGubler]

@lachlansneff: What would your motivation be for splitting into another trait?

[lachlansneff]

@ErichDonGubler

Adding it to Clone would be a breaking change. I can't think of a valid default implementation for Clone::clone_in and many types would have nothing to do with an allocator.

[TimDiekmann]

I think this should be added to the list in #15.
When implementing Box and RawVec I had to limit those traits to allocators, which implements Default which is rather limiting.

[TimDiekmann]

However, as @SimonSapin noticed in #15 (comment), it's probably fine to add them at a later point.
Additionally, if you really need those traits, I think a third party trait should be possible here until landed.

[ErichDonGubler]

Okay. I'm guessing it'd look something like this?

pub trait CloneIn {
    type Alloc: Alloc;

    fn clone_in(&self, allocator: Self::Alloc) -> T;
}

[Amanieu]

Adding it to Clone would be a breaking change. I can't think of a valid default implementation for Clone::clone_in and many types would have nothing to do with an allocator.

Wouldn't just calling regular clone and ignoring the allocator be a valid default implementation?

[lachlansneff]

@Amanieu, how could it produce a SomeType<A> when Clone::clone would just create a SomeType<System>?

[lachlansneff]

@ErichDonGubler, I don't think it'd need a Alloc associated type, but it would need a generic self type I think.

pub trait CloneIn {
    type This<A: Alloc>;
    fn clone_in<A: Alloc>(&self, allocator: A) -> Self::This<A>;
}

This won't be possible until generic associated types, maybe there's another way of doing it?

[ObsidianMinor]

I was thinking something like

pub trait CloneIn<A: Alloc> {
    type Cloned;

    fn clone_in(&self, allocator: A) -> Self::Cloned;
}

Then you can implement it like

impl<S, A: Alloc> CloneIn<A> for String<S> {
    type Cloned = String<A>;

    fn clone_in(&self, allocator: A) -> Self::Cloned {
        String { vec: self.vec.clone_in(allocator) }
    }
}

[TimDiekmann]

I had this in mind:

pub trait CloneIn<B: BuildAllocRef>: Sized
where
    B::Ref: AllocRef,
{
    fn clone_in(&self, a: B::Ref) -> Self
    where
        B::Ref: AllocRef<Error = crate::Never>;

    fn try_clone_in(&self, a: B::Ref) -> Result<Self, <B::Ref as AllocRef>::Error>;
}

But this has to be enhanced by an associative Self type.

I think this should be discussed in #15 or in a new Issue.

[gnzlbg]

@Amanieu

Wouldn't just calling regular clone and ignoring the allocator be a valid default implementation?

How would you add this method to Clone ? (*)

IIUC what you are proposing, what would something like this do

let x: Vec<T, A>;
let y: Vec<T, U> = x.clone_in();

if Clone::clone_in is implemented on top of clone ?

(*) I can imagine that we either have Clone<A> for T which would be a breaking change, or Clone::clone_in<Other>(&self) -> Other where Self: Sized or something like that, but I'm probably missing some more obvious extension.

[95th]

can't we make the clone method generic:

fn clone<A = Global>(&self) -> Self where A: Alloc;

[gnzlbg]

@95th You would need to return a different type than Self to be able to clone a Box<T, A> into one that has a different type because it has a different allocator, e.g., Box<T, B>.

[95th]

@gnzlbg you're right sorry.. A type based on generic param..

Edit: I realize the problem with this

[lqf96]

Do we also need to associate an allocator for owned strings types from std::ffi module? That will include CString and OSString...

[TimDiekmann]

On Sonntag, 10. November 2019 23:23:43 CET Qifan Lu wrote: Do we also need to associate an allocator for owned strings types from `std::ffi` module? That will include `CString` and `OSString`...

Adding an associated allocator to `CString` should be pretty straightforward, as it's basically a `Box<[u8]>`. `OSString` depends on the Os, but this shouldn't be a problem as well. Based on this, also `PathBuf` may should get an allocator, too. All three have a low priority at time of writing though.

[TimDiekmann]

Currently, there is a PR upstream for Box and BTreeMap. After Box is merged, I'll adjust Vec and String.
I updated the OP to reflect this.

cc @exrook

[pickfire]

When can we put Vec<T, A> into std? I keep track of vec more than the rest, maybe I can help out with vec?

[TimDiekmann]

I just answered the question right above. And my fat fingers clicked the wrong button :D

[a1phyr]

@TimDiekmann I have just sent a PR for VecDeque, could you add it to the top-level list ?

[Cyborus04]

@TimDiekmann I made a PR for Rc in rust-lang/rust#89132, could you add that to the list?

[yanchith]

I might have a usecase for BinaryHeap with custom allocators. Looking at the source, BinaryHeap is just a wrapper around Vec, which is already allocatorized, so extending it to support allocator api should be relatively straightforward.. I hope.

I notice there is no linked issue. If I want to add this, should I create an issue in rust-lang/rust and go from there?

[Amanieu]

I think you can just go ahead and write a pull request for it. All the allocators are under the #32838 tracking issue.

[rytheo]

@TimDiekmann I have a PR for LinkedList here: rust-lang/rust#103093

[TimDiekmann]

Thanks, updated!

[yanchith]

Oh, I didn't realize I had to post back here, but I made a PR for BinaryHeap some time ago, but it looks like it got buried rust-lang/rust#99339

[tgross35]

There are a few changes to the list in the issue - @TimDiekmann would you want to update these items?

• String: new PR, blocked(?) [WIP] Add support for custom allocator for String rust#101551
• LinkedList<T, A>: completed, will be available in 1.71
• BTreeMap<K, V, A>: new PR, completed BTreeMap: Support custom allocators (v1.5) rust#98103
• BTreeSet<T, A>: new PR, completed BTreeMap: Support custom allocators (v1.5) rust#98103
• BinaryHeap<T, A>: new PR, awaiting review as @yanchith mentioned, Make BinaryHeap parametric over Allocator rust#99339

[TimDiekmann]

Thank you, I updated the comment.

[tgross35]

Rc and Arc just landed! rust-lang/rust#89132 (comment)