U007D · March 26, 2022 13:51 · Jan 29, 2022
diff --git a/main.rs b/main.rs
@@ -0,0 +1,122 @@
+// 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);
+}