::nougat

Use (lifetime-)GATs on stable rust.

Example

#![forbid(unsafe_code)]
# use ::core::convert::TryInto;

#[macro_use]
extern crate nougat;

#[gat]
trait LendingIterator {
    type Item<'next>
    where
        Self : 'next,
    ;

    fn next(&mut self)
      -> Option<Self::Item<'_>>
    ;
}

struct WindowsMut<Slice, const SIZE: usize> {
    slice: Slice,
    start: usize,
}

#[gat]
impl<'iter, Item, const SIZE: usize>
    LendingIterator
for
    WindowsMut<&'iter mut [Item], SIZE>
{
    type Item<'next>
    where
        Self : 'next,
    =
        &'next mut [Item; SIZE]
    ;

    /// For reference, the signature of `.array_chunks_mut::<SIZE>()`'s
    /// implementation of `Iterator::next()` would be:
    /** ```rust ,ignore
    fn next<'next> (
        self: &'next mut AChunksMut<&'iter mut [Item], SIZE>,
    ) -> Option<&'iter mut [Item; SIZE]> // <- no `'next` nor "lending-ness"! ``` */
    fn next<'next> (
        self: &'next mut WindowsMut<&'iter mut [Item], SIZE>,
    ) -> Option<&'next mut [Item; SIZE]> // <- `'next` instead of `'iter`: lending!
    {
        let to_yield =
            self.slice
                .get_mut(self.start ..)?
                .get_mut(.. SIZE)?
                .try_into() // `&mut [Item]` -> `&mut [Item; SIZE]`
                .expect("slice has the right SIZE")
        ;
        self.start += 1;
        Some(to_yield)
    }
}

fn main() {
    let mut array = [0, 1, 2, 3, 4];
    let slice = &mut array[..];
    // Cumulative sums pattern:
    let mut windows_iter = WindowsMut::<_, 2> { slice, start: 0 };
    while let Some(item) = windows_iter.next() {
        let [fst, ref mut snd] = *item;
        *snd += fst;
    }
    assert_eq!(
        array,
        [0, 1, 3, 6, 10],
    );
}

Debugging / tracing the macro expansions

You can make the macros go through intermediary generated files so as to get well-spanned error messages and files which you can open and inspect yourself, with the remaining macro non-expanded for readability, by:

1. enabling the debug-macros Cargo feature of this dependency:

   [dependencies]
   ## …
   nougat.version = "…"
   nougat.features = ["debug-macros"]  # <- ADD THIS
   

2. Setting the DEBUG_MACROS_LOCATION env var to some absolute path where the macros will write the so-generated files.

Demo

How does the macro work?

Some historical context

1. 2021/02/24: Experimentation with for<'lt> Trait<'lt> as a super-trait to emulate GATs

   • (I suspect there may even be previous experimentations and usages over URLO; but I just can't find them at the moment)

   This already got GATs almost done, but for two things, regarding which I did complain at the time 😅:

   • The Trait<'lt> embedded all the associated items, including the methods, and not just the associated "generic" type.

     This, in turn, could lead to problems if these other items relied on the associated type being fully generic, as I observe here, on the 2021/03/06.

   • I was unable to express the where Self : 'next GAT-bounds.

2. 2022/03/08: I officially mention the workaround for "late/for-quantifying where T : 'lt" clauses thanks implicit bounds on types such as &'lt T.

• I didn't come out with this idea by myself; it's a bit fuzzy but I recall URLO user steffahn working a lot with similar shenanigans (e.g., this 2021/04/26 issue), and I clearly remember Kestrer over the community Discord pointing out the implicit bound hack.

  • For those interested, I used this technique, later on, to work around a nasty "overly restrictive lifetime-bound in higher-order closure context" issue in a very detailed URLO post that I think you'll find interesting.

  So all this, around that time became "advanced knowledge" shared amongst some URLO regulars (such as steffahn and quinedot), but never really actioned from there on: the idea was to wait for the proper solution, that is, GATs.

• Nonetheless, I started pondering about the idea of this very crate, dubbed autogatic at the time:

  • post summary

  • a post with near identical examples to what this crate currently offers

  • Sadly the proposal was received rather coldly: GATs were very close to stabilization, so a tool to automate a workaround/polyfill that was expected to quickly become stale was not deemed useful.

    So I waited. And waited. Finally the stabilization issue was opened, and… kind of "shut down" (more precisely, delayed until a bunch of aspects can be sorted out, see that issue for more info). And truth be told, the arguments not to stabilize right now seem quite legitimate and well-founded, imho, even if I still hope for a mid-term stabilization of the issue.

    What all that made was justify my autogatic idea, and so I committed to writing that prototypical idea I had in mind: nougat was born 🙂

• At which point user Jannis Harder chimed in and suggested another implementation / alternative to polyfilling GATs:

  1. to use the "standard GAT workaround" to define a HKT trait:

     trait WithLifetime<'lt> {
         type T;
     }
     
     trait HKT : for<'any> WithLifetime<'any> {}
     impl<T : ?Sized + for<'any> WithLifetime<'any>> HKT for T {}
     

  2. And then, to replace type Assoc<'lt>; with:

     type Assoc : ?Sized + HKT;
     

     • and use <Self::Assoc as WithLifetime<'lt>>::T instead of Self::Assoc<'lt> when resolving the type with a concrete lifetime.

  3. So as to, on the implementor side, use:

     impl LendingIterator for Thing {
      // type Item
      //     <'next>
      //     = &'next str
      // ;
         type Item           = dyn
             for<'next>      WithLifetime<'next, T
             = &'next str
         >;
         // formatted:
         type Item = dyn for<'next> WithLifetime<'next, T = &'next str>;
     }
     

     • (or use for<…> fn… pointers, but in practice they don't work as well as dyn for<…> Traits)

  This approach has a certain number of drawbacks (implicit bounds are harder (but not impossible!) to squeeze in), and when Assoc<'lt> has bounds of its own, a dedicated HKT trait featuring such bounds on T seems to be needed.

  That being said, this HKT-based approach has the advantage of being the only one that is remotely capable of being dyn-friendly(-ish), which is not the case for the "classical workaround" approach.

  See Sabrina Jewson's blog post below to see a more in-depth comparison of these two approaches.

The actual explanation

As I was bracing myself to spend hours detailing these tricks 😅, luckily for me, I learned that somebody had already done all that work, with definitely nicer prose than mine: Sabrina Jewson 🙏. She has written a very complete and thorough blog post about GATs, their stable polyfills, and how they compare with each other (funnily enough, GATs are currently worse than their polyfills since due to a compiler bug whenever one adds a trait bound to a GAT, then the GAT in question ends up having to be : 'static, for no actual reason other than the compiler brain-farting on it).

Here is the link to said blog post, pointing directly at the workaround that this crate happens to be using, but feel free to remove the anchor and read the full post, it's definitely worth it:

📕 The Better Alternative to Lifetime GATs – by Sabrina Jewson 📕

Limitations

• Only lifetime GATs are supported (no type Assoc<T> nor type Assoc<const …>).

• The code generated by the macro is currently not dyn-friendly at all. This will likely be improved in the future; potentially using another desugaring for the implementation.

• In order to refer to GATs outside of #[gat]-annotated items using Gat! is needed.

• Adding trait bounds to GATs in functions breaks type inference for that function (thanks to Discord use Globi for identifying and reporting this)