Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tracking Issue for structs which needs an allocator #7

Open
6 of 15 tasks
TimDiekmann opened this issue May 3, 2019 · 43 comments
Open
6 of 15 tasks

Tracking Issue for structs which needs an allocator #7

TimDiekmann opened this issue May 3, 2019 · 43 comments
Assignees

Comments

@TimDiekmann
Copy link
Member

TimDiekmann commented May 3, 2019

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

@TimDiekmann TimDiekmann pinned this issue May 3, 2019
@TimDiekmann TimDiekmann changed the title Tracking Issue for structs which needs to be associated with an allocator Tracking Issue for structs which needs an allocator May 3, 2019
@Ericson2314
Copy link

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

@ErichDonGubler
Copy link

@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
Copy link

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

@ErichDonGubler
Copy link

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

@lachlansneff
Copy link

@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
Copy link
Member Author

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
Copy link
Member Author

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
Copy link

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
Copy link
Member

Amanieu commented Oct 16, 2019

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
Copy link

lachlansneff commented Oct 16, 2019

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

@lachlansneff
Copy link

@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
Copy link

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
Copy link
Member Author

TimDiekmann commented Oct 16, 2019

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
Copy link

gnzlbg commented Oct 17, 2019

@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
Copy link

95th commented Oct 18, 2019

can't we make the clone method generic:

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

@gnzlbg
Copy link

gnzlbg commented Oct 18, 2019

@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
Copy link

95th commented Oct 18, 2019

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

Edit: I realize the problem with this

@lqf96
Copy link

lqf96 commented Nov 10, 2019

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

@TimDiekmann
Copy link
Member Author

TimDiekmann commented Nov 10, 2019 via email

@Wodann Wodann mentioned this issue Aug 5, 2020
18 tasks
@TimDiekmann
Copy link
Member Author

TimDiekmann commented Oct 3, 2020

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
Copy link

pickfire commented Oct 4, 2020

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
Copy link
Member Author

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

@a1phyr
Copy link

a1phyr commented Jun 24, 2021

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

bors added a commit to rust-lang-ci/rust that referenced this issue Jul 25, 2021
…Amanieu

Add support for custom allocator in `VecDeque`

This follows the [roadmap](rust-lang/wg-allocators#7) of the allocator WG to add custom allocators to collections.

`@rustbot` modify labels: +A-allocators +T-libs
@Cyborus04
Copy link

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

@yanchith
Copy link

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
Copy link
Member

Amanieu commented Jul 16, 2022

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

@rytheo
Copy link

rytheo commented Oct 18, 2022

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

@TimDiekmann
Copy link
Member Author

Thanks, updated!

@yanchith
Copy link

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
Copy link

tgross35 commented Jun 9, 2023

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

@TimDiekmann
Copy link
Member Author

Thank you, I updated the comment.

bors added a commit to rust-lang-ci/rust that referenced this issue Jun 13, 2023
Make BinaryHeap parametric over Allocator

Tracking issue: rust-lang#32838
Related: rust-lang/wg-allocators#7

This parametrizes `BinaryHeap` with `A`, similarly to how other collections are parametrized.

A couple things I left out:

```
BinaryHeap::append

    Currently requires both structures to have the same allocator type. Could
    change, but depends on Vec::append, which has the same constraints.

impl<T: Ord> Default for BinaryHeap<T>

    Not parametrized, because there's nowhere to conjure the allocator from.

impl<T: Ord> FromIterator<T> for BinaryHeap<T>

    Not parametrized, because there's nowhere to conjure the allocator from.

impl<T: Ord, const N: usize> From<[T; N]> for BinaryHeap<T>

    Not parametrized, because there's nowhere to conjure the allocator from.

unsafe impl<I> AsVecIntoIter for IntoIter<I>

    AsVecIntoIter is not allocator aware, and I didn't dare change it without guidance. Is this something important?
```

I've seen very few tests for allocator_api in general, but I'd like to at least test this on some usage code in my projects before moving forward.

EDIT: Updated the list of impls and functions that are not affected by this. `BinaryHeap` no longer has a `SpecExtend` impl, and prior work made implementing `Extend` possible.
@tgross35
Copy link

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

thomcc pushed a commit to tcdi/postgrestd that referenced this issue Aug 24, 2023
Make BinaryHeap parametric over Allocator

Tracking issue: #32838
Related: rust-lang/wg-allocators#7

This parametrizes `BinaryHeap` with `A`, similarly to how other collections are parametrized.

A couple things I left out:

```
BinaryHeap::append

    Currently requires both structures to have the same allocator type. Could
    change, but depends on Vec::append, which has the same constraints.

impl<T: Ord> Default for BinaryHeap<T>

    Not parametrized, because there's nowhere to conjure the allocator from.

impl<T: Ord> FromIterator<T> for BinaryHeap<T>

    Not parametrized, because there's nowhere to conjure the allocator from.

impl<T: Ord, const N: usize> From<[T; N]> for BinaryHeap<T>

    Not parametrized, because there's nowhere to conjure the allocator from.

unsafe impl<I> AsVecIntoIter for IntoIter<I>

    AsVecIntoIter is not allocator aware, and I didn't dare change it without guidance. Is this something important?
```

I've seen very few tests for allocator_api in general, but I'd like to at least test this on some usage code in my projects before moving forward.

EDIT: Updated the list of impls and functions that are not affected by this. `BinaryHeap` no longer has a `SpecExtend` impl, and prior work made implementing `Extend` possible.
spikespaz pushed a commit to spikespaz/dotwalk-rs that referenced this issue Aug 29, 2024
Make BinaryHeap parametric over Allocator

Tracking issue: #32838
Related: rust-lang/wg-allocators#7

This parametrizes `BinaryHeap` with `A`, similarly to how other collections are parametrized.

A couple things I left out:

```
BinaryHeap::append

    Currently requires both structures to have the same allocator type. Could
    change, but depends on Vec::append, which has the same constraints.

impl<T: Ord> Default for BinaryHeap<T>

    Not parametrized, because there's nowhere to conjure the allocator from.

impl<T: Ord> FromIterator<T> for BinaryHeap<T>

    Not parametrized, because there's nowhere to conjure the allocator from.

impl<T: Ord, const N: usize> From<[T; N]> for BinaryHeap<T>

    Not parametrized, because there's nowhere to conjure the allocator from.

unsafe impl<I> AsVecIntoIter for IntoIter<I>

    AsVecIntoIter is not allocator aware, and I didn't dare change it without guidance. Is this something important?
```

I've seen very few tests for allocator_api in general, but I'd like to at least test this on some usage code in my projects before moving forward.

EDIT: Updated the list of impls and functions that are not affected by this. `BinaryHeap` no longer has a `SpecExtend` impl, and prior work made implementing `Extend` possible.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests