Questions about GAT?

#![feature(generic_associated_types)]

pub trait Iterable<T>: Sized
{
    type Iter<'a>: Iterator<Item = &'a T>
    where
        Self: 'a, T: 'a;

    fn iter<'a>(&'a self) -> Self::Iter<'a>
    where
        Self: 'a, T: 'a;
}

pub trait IterableMut<T>: Iterable<T>
{
    type IterMut<'a>: Iterator<Item = &'a mut T>
    where
        Self: 'a, T: 'a;

    fn iter_mut<'a>(&'a mut self) -> Self::IterMut<'a>
    where
        Self: 'a, T: 'a;
}

pub trait Collection<T>: Iterable<T>
where
    for<'a> Self::Iter<'a>: ExactSizeIterator,
{
    fn len<'a>(&'a self) -> usize where Self: 'a, T: 'a {
        self.iter().len()
    }
    fn is_empty<'a>(&'a self) -> bool where Self: 'a, T: 'a {
        self.len() == 0
    }
}

impl<T> Iterable<T> for Option<T> {
    type Iter<'a> = std::option::Iter<'a, T> where T: 'a;

    fn iter<'a>(&'a self) -> Self::Iter<'a>
    where
        T: 'a,
    {
        self.iter()
    }
}

impl<T> IterableMut<T> for Option<T> {
    type IterMut<'a> = std::option::IterMut<'a, T> where T: 'a;

    fn iter_mut<'a>(&'a mut self) -> Self::IterMut<'a>
    where
        T: 'a,
    {
        self.iter_mut()
    }
}

impl<T> Collection<T> for Option<T> {
    fn len(&self) -> usize {
        match self {
            Some(_) => 1,
            None => 0,
        }
    }
    fn is_empty(&self) -> bool {
        self.is_none()
    }
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0311]: the parameter type `T` may not live long enough
  --> src/lib.rs:59:9
   |
59 | impl<T> Collection<T> for Option<T> {
   |         ^^^^^^^^^^^^^ ...so that the type `Option<T>` will meet its required lifetime bounds
   |
help: consider adding an explicit lifetime bound...
   |
59 | impl<T: 'a> Collection<T> for Option<T> {
   |       ++++

error[E0311]: the parameter type `T` may not live long enough
  --> src/lib.rs:59:9
   |
59 | impl<T> Collection<T> for Option<T> {
   |         ^^^^^^^^^^^^^ ...so that the type `T` will meet its required lifetime bounds
   |
help: consider adding an explicit lifetime bound...
   |
59 | impl<T: 'a> Collection<T> for Option<T> {
   |       ++++

error: could not compile `playground` due to 2 previous errors

The error message is confusing, 'a is a higher-rank lifetime, I don't know where to add such trait bound to it.

Yes, the error message is bad. Let me see what’s the problem here.


So the problem comes from the

for<'a> Self::Iter<'a>: ExactSizeIterator,

apparently. GATs aren’t production ready yet, I suppose that’s one of their problems still: such for<'a> Self::Iter<'a>: … bound are not implicitly limited by the Self: 'a, T: 'a bound they require, and there’s no explicit way either. Unless I’m misinterpreting the situation… would need some further investigation to be 100% certain.

The for<'a> Self::Iter<'a>: ExactSizeIterator bound is going to get annoying quickly anyway, because AFAIK it will not become an implied bound of the trait, but instead it will be required at every use case of Collection. You can test whether or not this will be a problem for you e.g. by using T: 'static as a temporary solution against the other problem, and trying to work with the trait as desired with some simple types.

1 Like

So, I got curious about how ::nougat would handle this, and it turns out it's quite disappointing: the "implicit bound hack" is only "known" by the compiler (in order to allow for things such as &'a T to exist) when writing down impls or when dealing with subtraits (the bread & butter of nougat).

But in this instance, it's the trait definition which needs to name the &'a T type when expressing the Iterator bound. This thus leads #[gat], alone, to fail :pensive:.

That being said, I've been tinkering a bit, and by "delaying", through some "abstraction", the idea that the __ImplicitBounds will make it possible to name types such as &'a [mut] T, I've ended up with the following code, which does compile (alas no demo yet since no online playground features ::nougat):

#[macro_use]
extern crate nougat;

/// An implementor of this trait bears proof that `T : 'lt` holds,
/// and will thus be able to provide `Self::Ref[Mut]` to produce
/// `&'a [mut] T`.
pub
trait Outlives<'lt, T> {
    type Ref;
    type RefMut;
}

/// Note: this trait would probably have to be sealed.
impl<'lt, T> Outlives<'lt, T> for &'lt T {
    type Ref = &'lt T;
    type RefMut = &'lt mut T;
}

/// The weird naming convention is to be compatible with `#[gat]` in the `impl`.
pub
trait IterableඞIter<'a, T, __ImplicitBounds : Outlives<'a, T> = &'a T> {
 // type T : Iterator<Item = &'a T                                     >;
    type T : Iterator<Item = <__ImplicitBounds as Outlives<'a, T>>::Ref>;
}

pub
trait Iterable<T> : Sized + for<'a> IterableඞIter<'a, T> {
    fn iter<'a>(&'a self)
      -> <Self as IterableඞIter<'a, T>>::T
    where
        T : 'a,
    ;
}

#[gat]
impl<T> Iterable<T> for Option<T> {
    type Iter<'a> = std::option::Iter<'a, T>
    where
        T : 'a,
    ;

    fn iter<'a> (&'a self)
      -> Self::Iter<'a>
    where
        T : 'a,
    {
        self.iter()
    }
}

pub
trait IterableMutඞIterMut<'a, T, __ImplicitBounds : Outlives<'a, T> = &'a T> {
    type T : Iterator<Item = __ImplicitBounds::RefMut>;
}

pub
trait IterableMut<T> : Sized + for<'a> IterableMutඞIterMut<'a, T> {
    fn iter_mut<'a> (&'a mut self)
      -> <Self as IterableMutඞIterMut<'a, T>>::T
    where
        T : 'a,
    ;
}

#[gat]
impl<T> IterableMut<T> for Option<T> {
    type IterMut<'a> = std::option::IterMut<'a, T>
    where
        T : 'a,
    ;

    fn iter_mut<'a> (&'a mut self)
      -> Self::IterMut<'a>
    where
        T : 'a,
    {
        self.iter_mut()
    }
}

pub
trait Collection<T> : Iterable<T>
where
    for<'a>
        Gat!(<Self as Iterable<T>>::Iter<'a>) : ExactSizeIterator
    ,
{
    fn len<'a> (&'a self)
      -> usize
    where
        T : 'a,
    {
        self.iter().len()
    }

    fn is_empty<'a> (&'a self)
      -> bool
    where
        T : 'a,
    {
        self.len() == 0
    }
}

impl<T> Collection<T> for Option<T> {
    fn len<'a> (&'a self)
      -> usize
    where
        T : 'a,
    {
        match self {
            Some(_) => 1,
            None => 0,
        }
    }

    fn is_empty<'a> (&'a self)
      -> bool
    where
        T : 'a,
    {
        self.is_none()
    }
}
  • I've also removed the Self : 'a bound for the sake of simplicitly, but I think we could generalize the idea (Outlives<'lt, T> + Outlives<'lt, Self>).

I don't know how useful or exploitable this is, plus it's getting late in my time zone, but maybe this is enough to let some people come up with a more general idea to improve nougat / the GAT-polyfill workarounds :slightly_smiling_face:

2 Likes

Looks cool, Thank you! :heart:

I didn't know nougat before, and the code is not quite straight-forward to understand. I think I have to read its docs to figure out what is behand the macros #[gat] and Gat!(<Self as Iterable<T>>::Iter<'a>).

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.