Tracking Issue for structs which needs an allocator

TimDiekmann commented 5 years ago

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

[x] Box<T, A>: rust-lang/rust#77187
[ ] Rc<T, A>: rust-lang/rust#89132
[ ] Arc<T, A>: rust-lang/rust#89132
[ ] String<A>: https://github.com/rust-lang/rust/pull/101551
[ ] CString<A>: rust-lang/rust#79500
[x] Vec<T, A>: rust-lang/rust#78461
[x] VecDeque<T, A>: rust-lang/rust#86595
[x] LinkedList<T, A>: rust-lang/rust#103093
[ ] HashMap<K, V, S, A>: rust-lang/hashbrown#133
[x] BTreeMap<K, V, A>: rust-lang/rust#98103
[ ] HashSet<T, S, A>
[x] BTreeSet<T, A>: https://github.com/rust-lang/rust/pull/98103
[ ] BinaryHeap<T, A>: https://github.com/rust-lang/rust/pull/99339
[ ] (OsString<A>)
[ ] (PathBuf<A>)

Ericson2314 commented 5 years ago

I've started in https://github.com/rust-lang/rust/pull/60703 .

ErichDonGubler commented 4 years ago

@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 commented 4 years ago

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

ErichDonGubler commented 4 years ago

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

lachlansneff commented 4 years ago

@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 commented 4 years ago

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 commented 4 years ago

However, as @SimonSapin noticed in https://github.com/rust-lang/wg-allocators/issues/15#issuecomment-489595249, 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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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

lachlansneff commented 4 years ago

@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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

@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 commented 4 years ago

can't we make the clone method generic:

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

gnzlbg commented 4 years ago

@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 commented 4 years ago

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

Edit: I realize the problem with this

lqf96 commented 4 years ago

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

TimDiekmann commented 4 years ago

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.