Inferred closure type is not general enough

1

Background

I was trying to make a trait that generalizes iterating through a collection:

trait MakeIter<'a, C, T>
where
    C: ?Sized,
    T: 'a,
{
    type Iter: Iterator<Item = &'a T>;

    fn make_iter(&mut self, collection: &'a C) -> Self::Iter;
}

Then, I implement this trait for functions that return iterators:

impl<'a, C, T, F, R> MakeIter<'a, C, T> for F
where
    C: 'a + ?Sized,
    T: 'a,
    F: FnMut(&'a C) -> R,
    R: Iterator<Item = &'a T>,
{
    type Iter = R;

    fn make_iter(&mut self, collection: &'a C) -> Self::Iter {
        self(collection)
    }
}

To test the trait, I use this function:

fn test_make_iter(mut make_iter: impl for<'a> MakeIter<'a, [i32], i32>) {
    let data = [1, 2, 3, 4];

    for x in make_iter.make_iter(&data) {
        println!("{}", x);
    }
}

This works for normal functions:

fn make_iter(slice: &[i32]) -> impl Iterator<Item = &i32> {
    slice.iter()
}

test_make_iter(make_iter); // OK.

But not for closures:

test_make_iter(|s: &[i32]| s.iter()); // Error: implementation of `MakeIter` is not general enough.

Unless I use a helper function:

fn infer_helper<F: FnMut(&[i32]) -> std::slice::Iter<i32>>(f: F) -> F {
    f
}

test_make_iter(infer_helper(|s: &[i32]| s.iter())); // OK.

The test code can be found here.

Analysis

I am guessing for test_make_iter(|s: &[i32]| s.iter()), the type of |s: &[i32]| s.iter() is impl FnMut(&'a [i32]) -> std::slice::Iter<'a, i32>, where 'a is some concrete lifetime.

But for test_make_iter(infer_helper(|s: &[i32]| s.iter())), the type of |s: &[i32]| s.iter() is for <'a> impl FnMut(&'a [i32]) -> std::slice::Iter<'a, i32>, where 'a may be any lifetime, that is why it works.

Question

If my analysis is correct, why doesn’t Rust infer the type of the closure to the more general one (the for <'a> version) so I don’t need the helper function? Is this something Rust can improve on?

2

I believe this is Issue 70263. You've already hit upon a workaround.

test_make_iter(<[i32]>::iter); works for your example (but yes, I recognize it's just an example).

Bug aside, do you know about the IntoIterator trait?

1 Like
3

My personal experience suggests that your analysis might be almost correct. I think, AFAICT, that writing a closure with an argument |s: &…| that is explicitly annotated to be a reference type then the resulting closure will ge generic over the lifetime of the argument, but still not over the return type. The return type still seems to get collapsed to always be same single type, even if explicitly annotated to be a reference type, too. Unlike for functions, there's no syntax for specifying a generic lifetimes and lifetime dependencies between arguments and return type in the closure definition/expression itself. The only way to get a return type generic is with some very clearly stated explicit Fn* trait bounds around the closure, like your helper functions.

By the way, without such an explicit type annotation on the argument type, that type seems to not become generic either, so e. g if you want a Fn(&Foo) -> Bar (that's for<'a> Fn(&'a Foo) -> Bar) but without something like your helper function, then you need to write |foo: &Foo| or "foo: &_|, whereas |foo|` doesn't work.

I share the opinion that Rust should improve on this in the future.

1 Like
4

Seems so.

1 Like
5

To my understanding, for each type, there can be one IntoIterator implementation at most. I need to iterate through a collection of one type in different ways. For example:

  • Forward: |s| s.iter(),
  • Backward: |s| s.iter().rev(),
  • Filtering: |s| s.iter().filter(|x| x % 2 == 0).

What I need is something like for<'a> FnMut(&'a C) -> impl Iterator<&'a T>, which is not possible to specify in Rust today.

6

Another, older issue about the same phenomenon.

Quite possibly I don't understand all the constraints, since this is just another example, but that's still possible with stdlib trait bounds. Anyway, not relevant to your question, just thought I'd mention it.

7

This is actually a follow-up to my one Stack Overflow question: https://stackoverflow.com/questions/67458566/how-to-define-a-generic-function-that-takes-a-function-that-converts-a-slice-to.

Originally, I encountered this problem when I am solving a LeetCode problem. My final solution is this. No need to fully understand the solution, since it is a fairly non-trivial problem, just notice the Solution::update function, which updates the matrix with the specified order. I need to update the matrix twice, one time forward, and one time backward. This means that Solution::update is generic over the iterating order.

1 Like
8

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.