Trouble writing an extension trait for a trait that includes a GAT

Hello, I'm getting myself tangled up in knots fighting with the compiler trying to implement an extension trait for trait that features a GAT. In particular, I have an extension trait for Iterator, and I'm trying to write a mirror extension trait for LendingIterator, which is of course one the classic applications of GATs. I have a minimal example in a repository here. I would have simply made a Rust Playground for it but evidently you cannot use arbitrary crates there and, in particular, I could not use the gat-lending-iterator crate.

For completeness, here is the complete code that will not compile:

use gat_lending_iterator::LendingIterator;

// The extension trait for normal Iterator.
trait IteratorExt<T> {
    fn filter_count(self, f: impl Fn(&T) -> bool) -> usize;
}
// The blanket implementation for normal Iterator.
impl<T, I: Iterator<Item = T>> IteratorExt<T> for I {
    fn filter_count(self, f: impl Fn(&T) -> bool) -> usize {
        self.filter(f).count()
    }
}

// The attempted extension trait for LendingIterator
pub trait LendingIteratorExt<T> {
    fn filter_count<P>(self, f: P) -> usize
    where
        P: FnMut(&T) -> bool;
}
// The attempted blanket implementation for normal LendingIterator.
impl<'a, I: LendingIterator + Sized> LendingIteratorExt<I::Item<'a>> for I {
    fn filter_count<P>(self, f: P) -> usize
    where
        P: FnMut(&I::Item<'a>) -> bool,
    {
        self.filter(f).count();
    }
}

struct LendingIter(usize);
impl LendingIterator for LendingIter {
    type Item<'a> = &'a usize
    where
        Self: 'a;

    fn next(&mut self) -> Option<Self::Item<'_>> {
        if self.0 > 9 {
            None
        } else {
            self.0 += 1;
            Some(&self.0)
        }
    }
}

// Example usage
fn main() {
    let arr = [1, 5, 3, 4, 6, 7, 2];
    assert_eq!(arr.iter().filter_count(|n| **n > 4), 3);

    let iter = LendingIter(0);
    //let count = iter.filter(|n| **n > 5).count();
    let count = iter.filter_count(|n| **n > 5);
    assert_eq!(count, 5);
}

The pertinent compiler error for the above is:

error[E0277]: expected a `FnMut(&<I as LendingIterator>::Item<'a>)` closure, found `P`
   --> src/main.rs:26:21
    |
26  |         self.filter(f).count();
    |              ------ ^ the trait `for<'b, 'a> FnMut<(&'b <I as LendingIterator>::Item<'a>,)>` is not implemented for `P`
    |              |
    |              required by a bound introduced by this call
    |
    = note: the trait bound `for<'b, 'a> P: FnMut(&'b <I as LendingIterator>::Item<'a>)` is not satisfied
note: required by a bound in `gat_lending_iterator::LendingIterator::filter`
   --> /home/dwhitman/.cargo/registry/src/index.crates.io-6f17d22bba15001f/gat-lending-iterator-0.1.5/src/traits/lending_iterator.rs:160:12
    |
157 |     fn filter<P>(self, predicate: P) -> Filter<Self, P>
    |        ------ required by a bound in this associated function
...
160 |         P: for<'a> FnMut(&Self::Item<'a>) -> bool,
    |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `LendingIterator::filter`
help: consider mutably borrowing here
    |
26  |         self.filter(&mut f).count();
    |                     ++++

For convenience, this is the documentation for the gat_lending_iterator::LendingIterator I am using.

A few things to note:

  1. The LendingIteratorExt trait is identical to the IteratorExt trait. I do not like the duplication here but apparently it is necessary since the extension requires blanket implementation on types that implement Iterator or LendingIterator and, since an item could theoretically implement both, distinct extension traits are required. It is not a requirement that the traits be identical if lifetimes or even a GAT needs to be added to LendingIteratorExt.
  2. I have tried all manner of adding lifetimes to the LendingIteratorExt trait and functions and the blanket impl to try to remedy the above compiler error, but I always end up with some other compiler error! Rather than review everything I have tried, I figured it would be easier to post the original problem and see what solutions might be available.

Any insight or solution that compiles would be much appreciated!

The error is saying that the predicate bound on filter...

            P: for<'a> FnMut(&Self::Item<'a>) -> bool,

...requires the method to work on an item with any lifetime, where as your bound...

        // In the trait definition
        P: FnMut(&T) -> bool,

        // In the impl
        P: FnMut(&I::Item<'a>) -> bool,

...can only work on arguments with a single, fixed lifetime. Note that type parameters like T resolve to a single type, including fixed values for any lifetimes -- so

Fn(&T) -> bool /* can never satisfy*/ for<'a> Fn(&Item<'a>) -> bool

That T is tripping you up. You need a way to talk about the GAT in the definition of your extension trait. You can do that by adding a supertrait bound:

pub trait LendingIteratorExt: LendingIterator {
    fn filter_count<P>(self, f: P) -> usize
    where
        P: FnMut(&Self::Item<'_>) -> bool;
}

impl<I: LendingIterator + Sized> LendingIteratorExt for I {
    fn filter_count<P>(self, f: P) -> usize
    where
        P: FnMut(&I::Item<'_>) -> bool,
    {
        self.filter(f).count()
    }
}

It never would have occurred to me to add the trait bound on LendingIteratorExt, and this completely fixes the problem! It makes complete sense though in order to talk about the GAT such that the closure trait bound matches.

Thank you very much for the response!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.