Recursive calling of a closure

Can’t compile this

Hello!

I’ve got an issue of calling a function passing a closure. I get the program compiled if I pass closure as rvalue (line 27). Something goes wrong if I pass a closure as a variable (line 29).

As far as I got the compilation error I should define lifetime for the closure arguments. But I don’t know why the compiler starts care about it. I can lock environment using rvalue of a closure as well as lvalue.

Ok. I tried to define a lifetime for the closure. Code here. Compiler says that heap argument doesn’t outlive borrowed content in recursive calling. I pointed the lifetime of the heap covers parent time and I don’t understand what it should cover else. There is no other options except the closure argument.

How can I help the compiler to understand that heap lives long enough? Why does it work for a closure passed as rvalue?

One more tip. I can get the code compiled if I pass function instead of closure (line 29). I though that the compiler infers function type instead of closure type on line 27 and I lock an outside variable. Look

let ref a = 1;
make_tree(&mut Node::new(123), &mut vec!(1,2,3), &|x, _| x == a);

It compiles as well. So I see only one difference. The compiler can’t infer lifetimes only if I pass lvalue of a closure.

1 Like

Your hitting a limitation of the compiler that when you directly assign a closure to a variable it uses regular lifetimes and does not know your intent is to use hrtb.

Current workaround if still intent on using variable is pass it through type-fixing function. (Has zero runtime cost.)

fn hr<T>(c: impl Fn(&T, &T) -> bool) -> impl Fn(&T, &T) -> bool {c}
let is_child_closure = hr(|x, y| x == y);
1 Like

I’ve read the chapter but I can’t figure out the issue. So the borrow checker is not able to get the lifetime of references locked by a closure. But I don’t understand why. In the example I see the fake closure that owns and borrows references. And I understand that the references live as long as the fake closure. So the returned reference lives as long as the fake closure. Where am I wrong?

  • short solution: write let is_child_closure = |x: &_, y: &_| x == y;, with an explicit lifetime elision on the input borrows

The posters before me have adequately explained your original error. Now let me explain where you got sidetracked.

Your compile error is in main. Adding explicit lifetimes to make_tree can only decrease the number of valid programs, not increase it. Here’s what happened when you added those lifetimes:

fn make_tree<'n, 'h: 'n, T, F>(parent: &'n mut Node<T>, heap: &'h mut Vec<T>, is_child: &F)
where
    F: Fn(&'n T, &'h T) -> bool
{
    parent.children.iter_mut().for_each(|mut x| make_tree(&mut x, heap, is_child));
}

Here, you specify that F is only valid for a single possible value of 'n and 'h. But in fact, both of these variables have a shorter lifetime in the recursive call than they do in the function signature:

In the recursive call, parent very clearly a shorter lifetime than 'n, because you’re borrowing from a temporary that only exists as long as the closure call:

//                v--- you created a borrow of a temporary here
|mut x| make_tree(&mut x, heap, is_child)

heap also has a shorter lifetime, but for a more obscure reason: Because the closure is not annotated with the move keyword, all upvars are borrowed:

fn make_tree<'n, 'h: 'n, T, F>(parent: &'n mut Node<T>, heap: &'h mut Vec<T>, is_child: &F)
where
    F: Fn(&'n T, &'h T) -> bool
{
    struct Closure<'f0, 'f1, 'r0, 'h, T, F>{
        is_child: &'f0 &'r0 F,
        heap: &'f1 mut &'h mut Vec<T>,
    }

    let closure = Closure {
        is_child: &is_child,
        heap: &mut heap, // <-- here, a shorter lifetime than 'h is created
    };
    parent.children.iter_mut().for_each(closure);
}

what you want is not for F: to impl Fn for a single set of lifetimes 'n, 'h, but for all lifetimes 'n, 'h. This can be written explicitly as follows:

fn make_tree<'n, 'h: 'n, T, F>(parent: &'n mut Node<T>, heap: &'h mut Vec<T>, is_child: &F)
where
    F: for<'a, 'b> Fn(&'a T, &'b T) -> bool

which can be simplified because there is automatic sugar for for<'a> lifetimes:

fn make_tree<'n, 'h: 'n, T, F>(parent: &'n mut Node<T>, heap: &'h mut Vec<T>, is_child: &F)
where
    F: Fn(&T, &T) -> bool

and then because 'h only appears once in the signature, it can be removed. And then 'n will only appear once, so it can also be removed:

fn make_tree<T, F>(parent: &mut Node<T>, heap: &mut Vec<T>, is_child: &F)
where
    F: Fn(&T, &T) -> bool

tl;dr: Your original function signature was the correct one.

1 Like

I’m still not clear with what compiler assumes in my case. I’ve read the explaination, I’ve got that in the case of the thread the compiler assumes HRTB if type is not annotated. In fact the closures become functions that don’t borrows environment. I’ve got how to define a closure to prevent it. So I’ve got new questions.

Does the compiler assume HTRB every time when a closure is passed by lvalue and the closure borrows something implicitly?
What does it assumes if I pass the closure with an explicit lifetime elision on the input borrows?
Does it still assumes HRTB and it resolves some way?

It looks like I didn’t read something or I misunderstood something in the book for beginners.

A beginner should only know that the thing here is kind of a “bug” with type inference, and that this “bug” may be avoided / circumvented by explicitely annotating the type of the input parameters of the closure :wink:

Does the compiler assume HTRB every time when a closure is passed by lvalue and the closure borrows something implicitly?

I think you’ve misunderstood. HRTB has nothing to do with the things implicitly borrowed by a closure. It has to do with lifetimes that appear in the function signature of the closure.