Skip to content

Instantly share code, notes, and snippets.

@jix
Created January 29, 2022 17:09
Show Gist options
  • Save jix/42d0e4a36ace4c618a59f0ba03be5bf5 to your computer and use it in GitHub Desktop.
Save jix/42d0e4a36ace4c618a59f0ba03be5bf5 to your computer and use it in GitHub Desktop.
Lifetime GAT emulation on stable rust
// 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);
}
@jix
Copy link
Author

jix commented Jan 29, 2022

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment