How to add a trait bound to a generic associated type?

Question

Recently, the post "The push for GATs stabilization" was published on the Rust blog. I'm interested in the LendingIterator trait but hit a problem when trying to use it. This is the definition from the post:

trait LendingIterator {
    type Item<'a> where Self: 'a;
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

All the things advertised in the blog post work fine and I see how GATs help in several ways. But: how do you add a trait bound to the associated Item type?

With the standard Iterator trait, it's easy:

fn print_all<I>(mut i: I) 
where
    I: Iterator,
    I::Item: std::fmt::Debug,    // <-------
{
    while let Some(x) = i.next() {
        println!("{:?}", x);
    }
}

But with the new trait, the bound this bound does not compile (Playground):

where
    I: LendingIterator,
    I::Item: std::fmt::Debug,

Compiler says:

error[E0107]: missing generics for associated type `LendingIterator::Item`
  --> src/lib.rs:12:8
   |
12 |     I::Item: std::fmt::Debug,
   |        ^^^^ expected 1 lifetime argument
   |
note: associated type defined here, with 1 lifetime parameter: `'a`
  --> src/lib.rs:5:10
   |
5  |     type Item<'a> where Self: 'a;
   |          ^^^^ --
help: add missing lifetime argument
   |
12 |     I::Item<'a>: std::fmt::Debug,
   |        ^^^^^^^^

So we need a lifetime parameter somehow. Apart from just using 'static (which is overly restrictive), I see two ways to achieve that. However, both have subtle but significant disadvantages/problems.

Lifetime parameter on function

fn print_all<'a, I>(mut i: I) 
where
    I: 'a + LendingIterator,
    I::Item<'a>: std::fmt::Debug,
{
    while let Some(x) = i.next() {
        println!("{:?}", x);
    }
}

(Playground)

This fails to compile with:

error[E0499]: cannot borrow `i` as mutable more than once at a time
  --> src/lib.rs:14:25
   |
9  | fn print_all<'a, I>(mut i: I) 
   |              -- lifetime `'a` defined here
...
14 |     while let Some(x) = i.next() {
   |                         ^-------
   |                         |
   |                         `i` was mutably borrowed here in the previous iteration of the loop
   |                         argument requires that `i` is borrowed for `'a`

The reason for this is that lifetime parameters (actually, all generic parameters) of print_all are chosen by the caller. This implies that the lifetime is larger than the scope of print_all: the caller cannot know of any lifetime that is just inside of print_all. That means that the call to next has to borrow i for the whole lifetime 'a. But that includes all of print_all, so we can only borrow exactly once!

In any case, this solution is not viable.

Higher kinded trait bounds (♥y bois)

fn print_all<I>(mut i: I) 
where
    I: LendingIterator,
    for<'a> I::Item<'a>: std::fmt::Debug,

(Playground)

Hey, it compiles! However, there is a subtle problem with it. Lets take the WindowsMut iterator from the blog post and try to pass it to print_all: Playground. It does not compile:

error[E0277]: `<_ as LendingIterator>::Item<'a>` doesn't implement `Debug`
  --> src/main.rs:43:5
   |
9  | fn print_all<I>(mut i: I) 
   |    --------- required by a bound in this
...
12 |     for<'a> I::Item<'a>: std::fmt::Debug,
   |                          --------------- required by this bound in `print_all`
...
43 |     print_all(windows);
   |     ^^^^^^^^^ `<_ as LendingIterator>::Item<'a>` cannot be formatted using `{:?}` because it doesn't implement `Debug`
   |
   = help: the trait `for<'a> Debug` is not implemented for `<_ as LendingIterator>::Item<'a>`

Strange! Remember:

type Item<'a> where Self: 'a = &'a mut [T];

And std::fmt::Debug is definitely implemented for mutable references to slices. Regardless of lifetime. (Compared the docs).

I think that the bound is not satisfied because for<'a> means "for all possible lifetimes", which includes 'static. Let's write that out:

Does WindowsMut<'t, T>::Item<'a> implement Debug for all possible 'as? Does WindowsMut<'t, T>::Item<'static> implement Debug? That's &'static mut [T]. That type is only valid if T: 'static. And there is also this weird where Self: 'a bound. And WindowsMut<'t, T>: 'static is definitely not satisfied unless 't == 'static.

---

How do I properly add a bound to the Item type of LendingIterator and implement print_all? This should be possible, right? Has this problem been discussed already? Is my reasoning above incorrect, in particular regarding the HRTBs?

Answer 1

I see your reasoning why this this pattern should extend, but isn't this maybe just a limitation of GATs at the moment (or just a bug)? Though, you can refactor your trait bound farther up the chain for this to work just fine by requiring ...

trait LendingIterator {
    type Item<'a>: std::fmt::Debug where Self: 'a; // Require Debug trait
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

// Require T has Debug trait
impl<'t, T: std::fmt::Debug> LendingIterator for WindowsMut<'t, T> {
    type Item<'a> where Self: 'a = &'a mut [T];
    
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>> {
        let retval = self.slice[self.start..].get_mut(..self.window_size)?;
        self.start += 1;
        Some(retval)
    }
}

and removing your bound on the function ...

fn print_all<I>(mut i: I) 
where
    I: LendingIterator,
    // Remove 
    // for<'a> I::Item<'a>: std::fmt::Debug, 
{
    while let Some(x) = i.next() {
        println!("{:?}", x);
    }
}

But if I then un-remove the trait bound, I get a different error than you had before ...

   Compiling playground v0.0.1 (/playground)
error[E0271]: type mismatch resolving `for<'a> <WindowsMut<'_, {integer}> as LendingIterator>::Item<'a> == <WindowsMut<'_, {integer}> as LendingIterator>::Item<'a>`
  --> src/main.rs:45:5
   |
9  | fn print_all<I>(mut i: I) 
   |    --------- required by a bound in this
...
13 |     for<'a> I::Item<'a>: std::fmt::Debug, 
   |                          --------------- required by this bound in `print_all`
...
45 |     print_all(windows);
   |     ^^^^^^^^^ expected associated type, found `&mut [_]`
   |
   = note: expected associated type `<WindowsMut<'_, {integer}> as LendingIterator>::Item<'a>`
            found mutable reference `&'a mut [{integer}]`
   = help: consider constraining the associated type `<WindowsMut<'_, {integer}> as LendingIterator>::Item<'a>` to `&'a mut [_]` or calling a method that returns `<WindowsMut<'_, {integer}> as LendingIterator>::Item<'a>`
   = note: for more information, visit https://doc.rust-lang.org/book/ch19-03-advanced-traits.html

For more information about this error, try `rustc --explain E0271`.
error: could not compile `playground` due to previous error

I would think that this additional trait bound is a tautology to the others, which to me is a red flag the compiler is complaining for no reason.

Playground to show the example works.