How to refer to the anonymous lifetime within a closure in trait bounds

1

As an experiment I was trying to create an iterator filter() function that could take a set of different types of functions as filter arguments. I got half way there and ran in to some weird lifetime issues.

Consider the following code:

use std::slice::Iter;

struct Yin;
struct Yang;

// TODO: implement `filter()`

fn main() {
    let slice: &[(Yin, Yang)] = &[];

    let result: Vec<_> = filter(slice.iter(), |_: Yin| true).collect();
    let result: Vec<_> = filter(slice.iter(), |_: Yang| true).collect();
    let result: Vec<_> = filter(slice.iter(), |_: &Yin| true).collect();
    let result: Vec<_> = filter(slice.iter(), |_: &Yang| true).collect();
    let result: Vec<_> = filter(slice.iter(), |_: (&Yin, &Yang)| true).collect();
    let result: Vec<_> = filter(slice.iter(), |_: (Yin, Yang)| true).collect();
}

I want to be be able to create the function filter() such that the above works which requires that the following function types are accepted by filter().

  • FnMut(Yin) -> bool
  • FnMut(Yang) -> bool
  • FnMut(&Yin) -> bool
  • FnMut(&Yang) -> bool
  • FnMut((Yin, Yang)) -> bool
  • FnMut((&Yin, &Yang)) -> bool

I tried implementing a trait for all these closures but I quickly ran into coherence issues. So tried to do this using generics.

Playground

use std::marker::PhantomData;
use std::slice::Iter;

#[derive(Clone, Copy)]
struct Yin;

#[derive(Clone, Copy)]
struct Yang;

struct Args {
    yin: Yin,
    yang: Yang,
}

impl From<&Args> for Yin {
    fn from(args: &Args) -> Self {
        args.yin
    }
}

impl From<&Args> for Yang {
    fn from(args: &Args) -> Self {
        args.yang
    }
}
impl<'a> From<&'a Args> for (Yin, Yang) {
    fn from(args: &'a Args) -> Self {
        (args.yin, args.yang)
    }
}

impl<'a> From<&'a Args> for &'a Yin {
    fn from(args: &'a Args) -> Self {
        &args.yin
    }
}

impl<'a> From<&'a Args> for &'a Yang {
    fn from(args: &'a Args) -> Self {
        &args.yang
    }
}

impl<'a> From<&'a Args> for (&'a Yin, &'a Yang) {
    fn from(args: &'a Args) -> Self {
        (&args.yin, &args.yang)
    }
}

struct Filter<'a, F, A> {
    iter: Iter<'a, (Yin, Yang)>,
    f: F,
    args: PhantomData<A>,
}

impl<F, A> Iterator for Filter<'_, F, A>
where
    F: FnMut(A) -> bool,
    for<'a> A: From<&'a Args>,
{
    type Item = (Yin, Yang);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        let Self { iter, f, .. } = self;

        iter.find_map(move |(yin, yang)| {
            let args = Args {
                yin: *yin,
                yang: *yang,
            };
            f(A::from(&args)).then(|| (*yin, *yang))
        })
    }
}

fn filter<'a, F, A>(iter: Iter<'a, (Yin, Yang)>, f: F) -> Filter<'_, F, A>
where
    F: FnMut(A) -> bool,
    A: From<&'a Args>,
{
    Filter {
        iter,
        f,
        args: PhantomData,
    }
}

This works but only for the function types that take an owned argument. The problem is that the implementation bound for<'a> A: From<&'a Args> is too strict. You can also specify the bounds like

impl<'a, F, A> Iterator for Filter<'_, F, A>
where
    F: FnMut(A) -> bool,
    A: From<&'a Args>,
{
// ...
}

But this doesn't compile at all. Is it possible to do what I want, maybe using a completely different way?

2

Yeah, since there could be closures (in practice only in nightly) that could have multiple usable closure APIs / overloads, you do get coherence issues.

I haven't looked in detail into your From<&'a Args> based solution, but I'd say that in your case, you have the "chance" that the lifetime 'iter of your Filter and the lifetime 'args of the &'args Args can actually be the same (assuming you use (&'a Yin, &'a Yan) as your Args):

  impl<'a, F, A> Iterator
-     for Filter<'_, F, A>
+     for Filter<'a, F, A>
  where
      F : FnMut(A) -> bool,
      A : From<('a Yin, &'a Yan)>,
  {
      // …
  }
3

The next problem after that is you're constructing a new Args but then borrowing it for some call-site determined length -- which could be (is) longer than the life of the function body (where the Args is stored).

A partial solution is to implement From<&'_ (Yin, Yang)> so you don't borrow a locally created data structure... but you can't do that for tuples because they are foreign types and you run into the orphan rule.

So instead, you can make Args be a borrowing newtype so that it's a local type and you can avoid the orphan rule.

1 Like
4

Nice! So just to clarify the reason this works is because

  • We make sure Args is valid for the lifetime of the elements in the iterator.
  • We make Args store references so that we don't borrow a locally created structure. (Playground)

Is this correct?

Going further

Okay now what would happen if we had a situation where the underlying iterator yielded owned types :thinking:? Say for example it was dynamically generating structs. Now we don't have a lifetime to refer to.

Playground

struct Filter<'a, F, A> {
    iter: IntoIter<(Yin, Yang)>,
    f: F,
    args: PhantomData<&'a A>,
}

impl<'a, F, A> Iterator for Filter<'a, F, A>
where
    F: FnMut(A) -> bool,
    A: From<Args<'a>>,
{
    type Item = (Yin, Yang);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        let Self { iter, f, .. } = self;
        iter.find(move |args| f(A::from(Args::new(args))))
    }
}

fn filter<'a, F, A>(iter: IntoIter<(Yin, Yang)>, f: F) -> Filter<'a, F, A>
where
    F: FnMut(A) -> bool,
    A: From<Args<'a>>,
{
    Filter {
        iter,
        f,
        args: PhantomData,
    }
}

fn main() {
    let vec: Vec<(Yin, Yang)> = vec![];

    let result: Vec<_> = filter(vec.into_iter(), |_: Yin| true).collect();
    let result: Vec<_> = filter(vec.into_iter(), |_: Yang| true).collect();
    let result: Vec<_> = filter(vec.into_iter(), |_: &Yin| true).collect();
    let result: Vec<_> = filter(vec.into_iter(), |_: &Yang| true).collect();
    let result: Vec<_> = filter(vec.into_iter(), |_: (&Yin, &Yang)| true).collect();
    let result: Vec<_> = filter(vec.into_iter(), |_: (Yin, Yang)| true).collect();
}
5

You don't want your data structures constrained by some lifetime when they don't need to be, so that would be the first thing I would get rid of. You can abstract over the lifetimes with generics and trait implementations. I chose this trait:

trait FilterYY<T> {
    fn test(&mut self, args: &Args) -> bool;
}

(It can sort of be thought of as an "I wish all my filter closures just took &Args" adapter.) Then I implemented, for example,

impl<'b, F: for<'a> FnMut(&'a Yin) -> bool> FilterYY<&'b Yin> for F {
    fn test(&mut self, args: &Args) -> bool {
        self(&args.yin)
    }
}

And then in your Filter struct, the &Yin corresponds to type parameter A.

Unfortunately I did run into a need to force inference for the reference-taking closures, as recently talked about elsewhere on this forum. I'm unsure if there's a way to get the forcing out of the call site and onto the constructor function or similar. It's also possible a different approach would avoid the kludge.

Playground.

2 Likes
6

Yeah, a closure only gets a higher-order input if the "lifetime placeholders" are known before inference kicks in, or if it is fed to a function explicitly requiring a higher-order Fn… bound.

The "worst" offender of the latter limitation is that the "trait alias" trick does not work that well with Fn… traits:

fn call_on_local_1 (f: impl FnOnce(&str))
{
    f(&String::from("local"))
}

fn main ()
{
    call_on_local_1(|s| println!("{}", s)); // OK
    call_on_local_2(|s| println!("{}", s)); // Error, lifetime is not general enough
}

trait Alias : FnOnce(&str) {}
impl<F> Alias for F where Self : FnOnce(&str) {}

fn call_on_local_2 (f: impl Alias)
{
    f(&String::from("local"))
}
2 Likes
7

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.