Lifetime GAT emulation on stable rust

main.rs

// This is a technique to emulate lifetime GATs (generic associated types) on stable rust starting
// with rustc 1.33.
//
// I haven't seen this exact technique before, but I would be surprised if no one else came up with
// it. I think this avoids most downsides of other lifetime GAT workarounds I've seen.
//
// In particular, neither implementing nor using traits with emulated lifetime GATs requires adding
// any helper items. Only defining the trait requires a single helper trait (+ a single helper impl
// for the 2nd variant) per GAT. This also makes the technique viable without any boilerplate
// reducing macros.
//
// Below is a complete example explaining two variants of this technique, illustrated using the
// lending/streaming iterator trait which is often cited as motivation for GATs.

// First we define a trait for types that represent a lifetime-generic item type. This is the place
// to add additional trait bounds on `Item` when needed. (Here we just have the implicit `Sized`
// bound.)
pub trait GenericItem<'a> {
    type Item;
}

// When using this to define a trait, instead of an `Item` associated type (which would have to be a
// GAT) we have an associated `GenericItem` type. Using HRTBs we ensure that `GenericItem` provides
// us with an `Item` type for any given lifetime. The reason for the `?Sized` bound will be
// explained below.
pub trait LendingIterator {
    type GenericItem: ?Sized + for<'any> GenericItem<'any>;

    // The lifetimes on `&mut self` and `as GenericItem` are elided (i.e. the same). This means the
    // lifetime of self is passed as parameter to the `GenericItem` trait on `Self::GenericItem`,
    // giving us an associated `Item` with the correct lifetime.
    fn next(&mut self) -> Option<<Self::GenericItem as GenericItem>::Item>;
}

// Now let's implement an iterator over overlapping mutable subslices within a larger mutable slice:

pub struct WindowsMut<'a, T> {
    slice: &'a mut [T],
    offset: usize,
    size: usize,
}

impl<'a, T> WindowsMut<'a, T> {
    pub fn new(slice: &'a mut [T], size: usize) -> Self {
        Self {
            slice,
            offset: 0,
            size,
        }
    }
}

// To implement the trait we need to supply an `GenericItem`. Instead of defining a type and
// implementing a trait, we can use a trait object type. Those allow us to specify HRTBs inline
// without defining any new types and without actually implementing the trait. Since trait objects
// are unsized, we needed the `?Sized` bound above.
impl<'a, T> LendingIterator for WindowsMut<'a, T> {
    type GenericItem = dyn for<'any> GenericItem<'any, Item = &'any mut [T]>;

    // Using the non-generic type in implementations keeps this perfectly readable
    fn next(&mut self) -> Option<&mut [T]> {
        let offset = self.offset;
        self.offset += 1;
        self.slice.get_mut(offset..offset + self.size)
    }
}

// As an alternative to trait object types, we can use function pointer types if we add a suitable
// blanket impl for them like this:
impl<'a, Item, T> GenericItem<'a> for T
where
    T: FnOnce(&'a ()) -> Item,
{
    type Item = Item;
}

// Lets implement another iterator.
pub struct PrefixesMut<'a, T> {
    slice: &'a mut [T],
    size: usize,
}

impl<'a, T> PrefixesMut<'a, T> {
    pub fn new(slice: &'a mut [T]) -> Self {
        Self { slice, size: 0 }
    }
}

// The `FnOnce` blanket impl allows us to use lifetime elision and implicit HRTBs (a feature of the
// `fn` syntax) in the trait implementation. I find this a bit more readable than `dyn for<'any>
// GenericItem<'any, Item = ...`.
impl<'a, T> LendingIterator for PrefixesMut<'a, T> {
    type GenericItem = fn(&()) -> &mut [T];

    fn next(&mut self) -> Option<&mut [T]> {
        self.size += 1;
        self.slice.get_mut(..self.size)
    }
}

// Using these trait impls also works without the need to specify anything unusual.
fn main() {
    let mut numbers = vec![0; 20];

    let mut windows = WindowsMut::new(&mut numbers, 5);

    while let Some(window) = windows.next() {
        for x in window {
            *x += 1;
        }
    }

    println!("{:?}", numbers);

    let mut chunk_prefixes = PrefixesMut::new(&mut numbers);

    while let Some(prefix) = chunk_prefixes.next() {
        prefix.swap(prefix.len() / 2, prefix.len() - 1);
    }

    println!("{:?}", numbers);
}

Playground link