RA extension completely freezes in VS Code when using fn-memo crate

[matteomeli]

I ran into various issues while trying to use this crate. As soon as I import the crate and start using functions/types from it, RA gets stuck on formatting when trying to save the file. After that the extension becomes unusable, syntax highlighting is broken, formatting is broken, code navigation is broken, run/debug button don't work, etc. Tried to restart server but no luck, only way seems to be to close and restart VS Code, but same problem is encountered again as soon as the same file is edited and/or saved.

My guess is that the root of the problem might be related to recursive closures analysis, which fn-memo (and its dependency recur-fn) are about. But can't be sure.

Windows WSL2 Ubuntu
rust-analyzer version: 2021-03-01 (5df3ee8)
Cargo TOML:

[package]
name = "test"
version = "0.1.0"
authors = [""]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
fn-memo = { version = "1.2", default-features = false }

Minimal example. A lib project only having lib.rs containing the following:

#[cfg(test)]
mod tests {
    use fn_memo::{recur_fn::recur_fn, unsync, FnMemo};
    
    #[test]
    fn it_works() {
        let fib = unsync::memoize(recur_fn(|fib, n: usize| {
            println!("Evaluating {}", n);
            if n <= 1 {
                n
            } else {
                fib(n - 1) + fib(n - 2)
            }
        }));

        assert_eq!(55, fib.call(10));
        assert_eq!(5, fib.call(5));
    }
}

[jonas-schievink]

Can reproduce

[jonas-schievink]

Root source of the bug seems to be the recur-fn crate: https://github.com/Jason5Lee/rust-recur-fn/blob/master/src/lib.rs

[jonas-schievink]

Reduced to:

pub trait RecurFn<Arg, Output> {
    fn body(&self, recur: impl Fn(Arg) -> Output, arg: Arg) -> Output;

    fn call(&self, arg: Arg) -> Output;
}

pub struct Closure<F>(F);

impl<Arg, Output, F> RecurFn<Arg, Output> for Closure<F>
where
    F: Fn(&dyn Fn(Arg) -> Output, Arg) -> Output,
{
    fn body(&self, recur: impl Fn(Arg) -> Output, arg: Arg) -> Output {
        self.0(&recur, arg)
    }

    fn call(&self, arg: Arg) -> Output {
        self.0(&|arg| self.call(arg), arg)
    }
}

Seems to hang in chalk, not rust-analyzer.

cc @flodiebold

[detrumi]

This hangs on a Implements(Closure<F>: RecurFn<?0.0, ?0.1>).
These closure goals are really hard to debug, with debug output like this:

[DEBUG hir_ty::traits::chalk] impl ImplId(9282): Closure<?0.2>: RecurFn<?0.0, ?0.1> where [for<> Implemented(^1.2: Fn<2<[?0 := (&'static dyn for<type> [for<> Implemented(^1.0: Fn<1<[?0 := ^3.0]>>), for<> AliasEq(<^1.0 as FnOnce<1<[?0 := ^3.0]>>>::Output = ^3.1)] + 'static), ?1 := ^1.0]>>), for<> AliasEq(<^1.2 as FnOnce<2<[?0 := (&'static dyn for<type> [for<> Implemented(^1.0: Fn<1<[?0 := ^3.0]>>), for<> AliasEq(<^1.0 as FnOnce<1<[?0 := ^3.0]>>>::Output = ^3.1)] + 'static), ?1 := ^1.0]>>>::Output = ^1.1)]
[DEBUG hir_ty::traits::chalk] impl_datum: ImplDatumBound { trait_ref: Closure<[?0 := ^0.2]> as RecurFn<^0.0, ^0.1>, where_clauses: [for<> Implemented(^1.2: Fn<2<[?0 := (&'static dyn for<type> [for<> Implemented(^1.0: Fn<1<[?0 := ^3.0]>>), for<> AliasEq(<^1.0 as FnOnce<1<[?0 := ^3.0]>>>::Output = ^3.1)] + 'static), ?1 := ^1.0]>>), for<> AliasEq(<^1.2 as FnOnce<2<[?0 := (&'static dyn for<type> [for<> Implemented(^1.0: Fn<1<[?0 := ^3.0]>>), for<> AliasEq(<^1.0 as FnOnce<1<[?0 := ^3.0]>>>::Output = ^3.1)] + 'static), ?1 := ^1.0]>>>::Output = ^1.1)] }

[flodiebold]

Yeah, and it's really annoying that we can't easily reproduce these in the Chalk test harness... Might this be rust-lang/chalk#688 again?

[detrumi]

Yeah, and it's really annoying that we can't easily reproduce these in the Chalk test harness... Might this be rust-lang/chalk#688 again?

I was going to say no, but looking at it a bit more it does start creating longer goals:

(FnOnce::Output<[?0 := !0_3, ?1 :=
2<[?0 := (&'static dyn for<type> [for<> Implemented(^1.0: Fn<1<[?0 := ^2.0]>>), for<> AliasEq(<^1.0 as FnOnce<1<[?0 := ^2.0]>>>::Output = FnOnce::Output<[?0 := !0_3, ?1 :=
2<[?0 := (&'static dyn for<type> [for<> Implemented(^1.0: Fn<1<[?0 := ^4.0]>>), for<> AliasEq(<^1.0 as FnOnce<1<[?0 := ^4.0]>>>::Output = FnOnce::Output<[?0 := !0_3, ?1 :=
2<[?0 := (&'static dyn for<type> [for<> Implemented(^1.0: Fn<1<[?0 := ^6.0]>>), for<> AliasEq(<^1.0 as FnOnce<1<[?0 := ^6.0]>>>::Output = ^6.1)] + 'static), ?1 := ^4.0]>]>)] + 'static), ?1 := ^2.0]>]>)] + 'static), ?1 := ^0.0]>]> <: FnOnce::Output<[?0 := !0_3, ?1 :=
2<[?0 := (&'static dyn for<type> [for<> Implemented(^1.0: Fn<1<[?0 := ^2.0]>>), for<> AliasEq(<^1.0 as FnOnce<1<[?0 := ^2.0]>>>::Output = FnOnce::Output<[?0 := !0_3, ?1 :=
2<[?0 := (&'static dyn for<type> [for<> Implemented(^1.0: Fn<1<[?0 := ^4.0]>>), for<> AliasEq(<^1.0 as FnOnce<1<[?0 := ^4.0]>>>::Output = FnOnce::Output<[?0 := !0_3, ?1 :=
2<[?0 := (&'static dyn for<type> [for<> Implemented(^1.0: Fn<1<[?0 := ^6.0]>>), for<> AliasEq(<^1.0 as FnOnce<1<[?0 := ^6.0]>>>::Output = ^6.2)] + 'static), ?1 := ^4.0]>]>)] + 'static), ?1 := ^2.0]>]>)] + 'static), ?1 := ^0.0]>]>)

So it probably is another instance of the same problem.

[jackh726]

It would be nice to get better debug output about the closure - closure kind, inputs/output getting lowered, upvars.

I'm actually looking into rust-lang/chalk#688 right now and having a hard time reproducing

[detrumi]

It would be nice to get better debug output about the closure - closure kind, inputs/output getting lowered, upvars.

That's in the RustIrDatabase callbacks, closure_inputs_and_output and closure_upvars, right? It doesn't look like those ever get called for this reproduction.