Additional traits for allocator aware types

[TimDiekmann]

When adding allocators, many current traits become useless. Those traits should be either extended to support allocators or orthogonal traits should be added.

• Default: Add DefaultIn:

  pub trait DefaultIn {
      type Alloc: Alloc;
  
      fn default_in(allocator: Self::Alloc) -> Self;
  }

• FromIterator: Add FromIteratorIn:

  pub trait FromIteratorIn<T, A: Alloc>: Sized {
      fn from_iter_in<I: IntoIterator<Item = T>>(iter: I, allocator: A) -> Self;
  }

• Iterator: Add collect_in:

  pub trait Iterator {
      // ...
  
      #[inline]
      #[must_use = "if you really need to exhaust the iterator, consider `.for_each(drop)` instead"]
      fn collect_in<T: FromIteratorIn<Self::Item, A>, A: Alloc>(self, allocator: A) -> T {
          FromIteratorIn::from_iter_in(self, allocator)
      }
  }

• (Try)From and (Try)Into: Add (Try)FromIn and (Try)IntoIn :

  pub trait FromIn<T> {
      type Alloc: Alloc;
  
      fn from_in(t: T, allocator: Self::Alloc) -> Self;
  }
  
  pub trait IntoIn<T> {
      type Alloc: Alloc;
  
      fn into_in(self, allocator: Self::Alloc) -> T;
  }
  
  
  impl<T, U: FromIn<T>> IntoIn<U> for T {
      type Alloc = U::Alloc;
  
      fn into_in(self, allocator: Self::Alloc) -> U {
          U::from_in(self, allocator)
      }
  }

[the8472]

What would various intermediate iterator ops that might need to allocate do? e.g. Iterator::cloned

[TimDiekmann]

This is not related to Alloc, because it clones element by element. It's up to Iterator::Item if it can be cloned.

[SimonSapin]

Those traits should be either extended to support allocators or orthogonal traits should be added.

Should they really? Rather than systematically adding new allocator-aware APIs for everything in the standard library that might allocate, I’d prefer to judge individual use cases.

For example, what actual generic code would need to have conversion traits for its type parameters, and need to be allocator-aware?

---

For APIs we do want to add, why should the allocator type ever be an associated type chosen by the impl rather than a type parameter of individual methods, chosen by the caller?

[TimDiekmann]

For APIs we do want to add, why should the allocator type ever be an associated type chosen by the impl rather than a type parameter of individual methods, chosen by the caller?

Good point, a generic parameter would match better I guess.

[gnzlbg]

I am not sure what problem each of the proposed traits actually solves. Maybe you could elaborate on that?

[TimDiekmann]

It's the same use case as before: if I want to create a Vec<T>, I use Iterator::collect(). But if I want to create a Vec<T, A> this is not possible without dropping some optimizations on FromIterator (e.g. TrustedLen). It makes sense to just call Iterator::collect_in(alloc)

[gnzlbg]

But if I want to create a Vec<T, A> this is not possible without dropping some optimizations on FromIterator (e.g. TrustedLen). It makes sense to just call Iterator::collect_in(alloc)

If A does not implement Default (which is what I suppose the FromIterator impl for Vec<T, A> would require), then one can't use Iterator::collect, but Vec::extend should work just fine in this case.

[TimDiekmann]

If A does not implement Default (which is what I suppose the FromIterator impl for Vec<T, A> would require), then one can't use Iterator::collect, but Vec::extend should work just fine in this case.

With this argument we could also deprecate Iterator::collect as Vec::extend also works here...

[SimonSapin]

collect exists in addition to extend for convenience. But at least so far, allocator-generic collections are a very niche use case so the same level of convenience is not necessarily warranted. At least it is not necessary to systematically have it from the start. We can see as usage grows which convenience APIs will be more useful.

[TimDiekmann]

In #7 the discussion came up to also provide CloneIn.

I liked the proposal in #7 (comment) and tested around a bit with this at the alloc-wg crate and came up with this solution:

pub trait CloneIn<A: AllocRef>: Sized {
    type Cloned;

    fn clone_in(&self, a: A) -> Self::Cloned
    where
        A: AllocRef<Error = !>;

    fn try_clone_in(&self, a: A) -> Result<Self::Cloned, A::Error>;
}

Adding this to Box is straight forward:

#[allow(clippy::use_self)]
impl<T: Clone, A: AllocRef, B: BuildAllocRef> CloneIn<A> for Box<T, B>
where
    B::Ref: AllocRef,
{
    type Cloned = Box<T, A::BuildAlloc>;

    fn clone_in(&self, a: A) -> Self::Cloned
    where
        A: AllocRef<Error = !>,
    {
        Box::new_in(self.as_ref().clone(), a)
    }

    fn try_clone_in(&self, a: A) -> Result<Self::Cloned, A::Error> {
        Box::try_new_in(self.as_ref().clone(), a)
    }
}

[95th]

The above proposed CloneIn doesn't work well with RawVec, Vec at the moment because those return CollectionAllocErr everywhere and not A::Error. You would either need to have an associated error type or have two different traits CloneIn and TryCloneIn

[TimDiekmann]

Do you mean it doesn't work well when implementing CloneIn on Vec, as Vec is based on RawVec or implementing CloneIn on RawVec? The letter doesn't make sense anyway, as RawVec may contains uninitialized memory.

[95th]

I mean implementing CloneIn on Vec because it uses RawVec and all fallible constructors of that return CollectionAllocError.

[TimDiekmann]

I think this is fine, as CollectionAllocError::CapacityOverflow is not possible when cloning. However, It's unlucky, that the layout is dropped when forwarding the AllocError. Maybe we should introduce CloneError, which is aware of the inner allocation error and the layout, which was used for the allocation?

[CeleritasCelery]

Has anyone attempted this yet? From the discussions it looks like these are the traits we are interested in:

• Default: Add DefaultIn:

pub trait DefaultIn<A: Allocator> {
    fn default_in(allocator: A) -> Self;
}

• FromIterator: Add FromIteratorIn:

pub trait FromIteratorIn<T, A: Allocator>: Sized {
    fn from_iter_in<I: IntoIterator<Item = T>>(iter: I, allocator: A) -> Self;
}

pub trait Iterator {
    // ...

    #[inline]
    fn collect_in<T: FromIteratorIn<Self::Item, A>, A: Allocator>(self, allocator: A) -> T {
        FromIteratorIn::from_iter_in(self, allocator)
    }
}

• (Try)From and (Try)Into: Add (Try)FromIn and (Try)IntoIn:

pub trait FromIn<T, A: Allocator> {
    fn from_in(t: T, allocator: A) -> Self;
}

pub trait IntoIn<T, A: Allocator> {
    fn into_in(self, allocator: A) -> T;
}

...

impl<T, U: FromIn<T, A>, A: Allocator> IntoIn<U, A> for T {
    fn into_in(self, allocator: A) -> U {
        U::from_in(self, allocator)
    }
}

Just spitballing, but would it be possible to add generic impl's for some of these traits (similar to From and Into)? For example if you implement DefaultIn it would auto implement Deafult with GlobalAlloc? It doesn't seem like that would be possible due to differences between the two traits.

[tema3210]

Has anyone attempted this yet? From the discussions it looks like these are the traits we are interested in:

* `Default`: Add `DefaultIn`:

pub trait DefaultIn<A: Allocator> {
    fn default_in(allocator: A) -> Self;
}

* `FromIterator`: Add `FromIteratorIn`:

pub trait FromIteratorIn<T, A: Allocator>: Sized {
    fn from_iter_in<I: IntoIterator<Item = T>>(iter: I, allocator: A) -> Self;
}

pub trait Iterator {
    // ...

    #[inline]
    fn collect_in<T: FromIteratorIn<Self::Item, A>, A: Allocator>(self, allocator: A) -> T {
        FromIteratorIn::from_iter_in(self, allocator)
    }
}

* `(Try)From` and `(Try)Into`: Add `(Try)FromIn` and `(Try)IntoIn`:

pub trait FromIn<T, A: Allocator> {
    fn from_in(t: T, allocator: A) -> Self;
}

pub trait IntoIn<T, A: Allocator> {
    fn into_in(self, allocator: A) -> T;
}

...

impl<T, U: FromIn<T, A>, A: Allocator> IntoIn<U, A> for T {
    fn into_in(self, allocator: A) -> U {
        U::from_in(self, allocator)
    }
}

Just spitballing, but would it be possible to add generic impl's for some of these traits (similar to From and Into)? For example if you implement DefaultIn it would auto implement Deafult with GlobalAlloc? It doesn't seem like that would be possible due to differences between the two traits.

I think it'd be way better if we add generic methods to existing traits because it reduces API surface.

[petertodd]

I think it'd be way better if we add generic methods to existing traits because it reduces API surface.

The challenge is you want something like:

trait Default<A = Global> {
    fn default() -> Self
        where A: Default;

    fn default_in(alloc: &mut A) -> Self;
}

But for backwards compatibility, a default implementation of default_in has to be provided. And that's not possible in existing stable Rust because of the where bound.

Providing allocators via context seems to be a much better idea to me.

[CeleritasCelery]

Is there even an RFC for Contexts? That seems like it was just an idea (a really good one IMHO). I don’t think allocators can wait on that.

[tema3210]

Is there even an RFC for Contexts? That seems like it was just an idea (a really good one IMHO). I don’t think allocators can wait on that.

Given they're not stable, they can wait indefinitely. Contexts are very good idea, which I believe is the first thing add to the type system after const generics. It would be nice to have them before stable alloc