Is there any plan to support (mutually) recursive closure?

Hi forums,

When I play Rust in leetcode, the most un-happy thing for me is Rust can not easily make a recursive closure, and nearly impossible make a mutually recursive closure. So I must use a Env struct to manually wrap the captured variables, or put them all together in argument list.

I have searched the forum and found few useful result, and after some study I realize it's maybe not possible in case of borrow-checker when trying to construct a mutually recursive closure. It seems must need the language support for that.

e.g. this is a demo for get all combines for k items in 1..=n ranges:

fn make_combines(k: i32, n: i32) -> Vec<Vec<i32>> {
    fn dfs(i: i32, k: i32, n: i32, cur: &mut Vec<i32>, r: &mut Vec<Vec<i32>>) {
        if cur.len() == k as usize {
            r.push(cur.clone());
            return
        }
        for i in (i+1)..=(n-k+cur.len() as i32+1) {
            cur.push(i);
            dfs(i, k, n, cur, r);
            cur.pop();
        }
    }
    let mut r = vec![];
    dfs(0, k, n, &mut vec![], &mut r);
    r
}

fn main() {
    println!("{:?}", make_combines(2, 4));
}
  

I think maybe some syntax like this may work:

fn make_combines(k: i32, n: i32) -> Vec<Vec<i32>> {
    let mut cur = vec![];
    let mut r = vec![];
    let mut dfs = |i| {
        if cur.len() == k as usize {
            r.push(cur.clone());
            return
        }
        for i in (i+1)..=(n-k+cur.len() as i32+1) {
            cur.push(i);
            fn(i);
            cur.pop();
        }
    };
    dfs(0);
    r
}

So is there any hope for this feature in future? :slight_smile:

Closures are just anonymous struct with compiler-generated Fn* trait impl. So recursive closure means self-referential struct and mutually recursive closure means mutually referential structs. Both are nightmare for lifetime analysis.

If you have a two values which reference each other, how can they be dropped in some order without producing dangling reference, even by temporarily?

1 Like

We already have limited support for self reference structs with Pin API, because the struct is generated by compiler, so as this example.

We could easily make a recursive "closure" using impl block, or a manually closure object after fn_trait stabilized. So the compiler-generated version seems no problem here.

The mutually one indeed is a hard problem. But we should still just allow reference that can not reference each other, just like the normal Env struct that has several mutually reference? Maybe I'm wrong, but IMO there is at least a small set could make clear lifetime analyses.

Another proposal is to allow dynamic capture in nest fn item, this even doesn't change any syntax, just semantics. So since we have error message likes below:

error[E0434]: can't capture dynamic environment in a fn item
 --> noname/2020-09-10-1.rs:5:12
  |
5 |         if cur.len() == k as usize {
  |            ^^^
  |
  = help: use the `|| { ... }` closure form instead

Is there any chance to allow this structure in future?

This thread https://internals.rust-lang.org/t/proposal-explicit-reference-to-self-for-closures/7467 examines ideas that allow closure recursions. I'm not sure if there is an RFC related to this idea.