"error: reached the recursion limit during monomorphization" with unboxed closures

[japaric]

Came up with this issue while "unboxing" the collections::trie::map::InternalNode::each_reverse method.

Reduced test case

#![feature(unboxed_closures)]

struct Struct;

impl Struct {
    fn method_ok(&self, f: |()| -> bool) -> bool {
        self.method_ok(|t| f(t))
    }

    fn method_bad<F>(&self, f: F) -> bool where F: Fn(()) -> bool {
        self.method_bad(|t| f(t))
    }

    fn method_bad2<F>(&self, f: F) -> bool where F: Fn(()) -> bool {
        let f: &Fn(()) -> bool = &f;

        self.method_bad2(|t| f.call((t,)))
    }
}

fn main() {
    Struct.method_ok(|_| true);
    // Pick one
    Struct.method_bad(|_| true);
    //Struct.method_bad2(|_| true);
}

Output

limit.rs:10:5: 12:6 error: reached the recursion limit during monomorphization
limit.rs:10     fn method_bad<F>(&self, f: F) -> bool where F: Fn(()) -> bool {
limit.rs:11         self.method_bad(|t| f(t))
limit.rs:12     }

Version

rustc 0.13.0-dev (d9c7c00b9 2014-12-04 21:33:07 +0000)

cc @nikomatsakis (you already know, but I want to keep track of the issue)

[gereeter]

This seems like expected behavior to me. Passing a closure to either of the method_bads will cause a specialized version of that method_bad to be created, including a new type for the wrapper unboxed closure. This is then passed to method_bad, creating a new specialized version and a second new type for the wrapper closure. The cycle repeats indefinitely.

The only only way that I could see rustc accepting this would be if it were to recognize the |x| f(x) idiom and replace it with f. This seems very distateful, though I would be happy to see a lint recommending it.

This should work as a replacement:

fn method_ok_unboxed<F>(&self, f: F) -> bool where F: Fn(()) -> bool {
    self.method_ok_unboxed(f);
}

Additionally, it should be faster, as it won't be going through the useless indirection of |x| f(x).

[japaric]

@gereeter Sure, that works in the reduced case, but in the TrieMap code, it won't work because the method call is inside a for loop, and the operation you are suggesting moves the closure.

[gereeter]

@japaric Why not have it just take the closure by reference, then?

[japaric]

Changing the signature to always take the closure by reference is a loss in ergonomics:

trie_map.each_reverse(&mut |a, b| /* body */);
// vs
trie_map.each_reverse(|a, b| /* body */);

What we probably want to do is add the following impl:

impl<'a, Args, Result> FnMut<Args, Result> for &'a mut F where F: FnMut<Args, Result> { /* */ }

That way we can pass the closure either by value or by reference. However, due to #18835/#19032 we can't do that at the moment.

[huonw]

This seems like expected behavior to me.

I agree, but I think this is so subtle and hard to debug (the infinite chain of unique types is unexpected, since they all look the same in the source) that this is at least worth special error messages.

[SecondNature]

The compiler never returns when compiling this code. If you remove the predicate closure then you get "error: reached the recursion limit during monomorphization". But with both closures included it just loops and never returns. I would assume that the "recursion limit" test in the error message is failing with two closures.

rustc 1.0.0-nightly (3d0d9bb 2015-01-12 22:56:20 +0000)

#![crate_name = "compiler_bug"]

#![crate_type = "bin"]

#![allow(unused_variables)]

fn main() {
recursive(|| { false } , || { })
}

pub fn recursive< P: Fn() -> bool, F: Fn()>(predicate : P , function : F ) {
recursive( ||predicate(), ||function() );
}

I read that the error message may be expected behaviour. But this endless loop behaviour may influence your design choice or encourage a error to be added.

Can someone private message me a version of the included code that will compile.

[steveklabnik]

We now have a better message. Updated code:

#![feature(unboxed_closures)]
#![feature(core)]

struct Struct;

impl Struct {
    fn method_bad<F>(&self, f: F) -> bool where F: Fn(()) -> bool {
        self.method_bad(|t| f(t))
    }

    fn method_bad2<F>(&self, f: F) -> bool where F: Fn(()) -> bool {
        let f: &Fn(()) -> bool = &f;

        self.method_bad2(|t| f.call((t,)))
    }
}

fn main() {
    // Pick one
    Struct.method_bad(|_| true);
    //Struct.method_bad2(|_| true);
}

errors:

hello.rs:11:5: 15:6 warning: method is never used: `method_bad2`, #[warn(dead_code)] on by default
hello.rs:11     fn method_bad2<F>(&self, f: F) -> bool where F: Fn(()) -> bool {
hello.rs:12         let f: &Fn(()) -> bool = &f;
hello.rs:13 
hello.rs:14         self.method_bad2(|t| f.call((t,)))
hello.rs:15     }
hello.rs:7:5: 9:6 warning: function cannot return without recurring, #[warn(unconditional_recursion)] on by default
hello.rs:7     fn method_bad<F>(&self, f: F) -> bool where F: Fn(()) -> bool {
hello.rs:8         self.method_bad(|t| f(t))
hello.rs:9     }
hello.rs:8:9: 8:34 note: recursive call site
hello.rs:8         self.method_bad(|t| f(t))
                   ^~~~~~~~~~~~~~~~~~~~~~~~~
hello.rs:7:5: 9:6 help: a `loop` may express intention better if this is on purpose
hello.rs:11:5: 15:6 warning: function cannot return without recurring, #[warn(unconditional_recursion)] on by default
hello.rs:11     fn method_bad2<F>(&self, f: F) -> bool where F: Fn(()) -> bool {
hello.rs:12         let f: &Fn(()) -> bool = &f;
hello.rs:13 
hello.rs:14         self.method_bad2(|t| f.call((t,)))
hello.rs:15     }
hello.rs:14:9: 14:43 note: recursive call site
hello.rs:14         self.method_bad2(|t| f.call((t,)))
                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hello.rs:11:5: 15:6 help: a `loop` may express intention better if this is on purpose
hello.rs:7:5: 9:6 error: reached the recursion limit during monomorphization
hello.rs:7     fn method_bad<F>(&self, f: F) -> bool where F: Fn(()) -> bool {
hello.rs:8         self.method_bad(|t| f(t))
hello.rs:9     }

[oli-obk]

this doesn't look fixed to me, there's still various FIXME(#19596) in the source with workarounds, and fixing them still gives the following error message:

error: overflow evaluating the requirement `[closure@src/librustc/hir/pat_util.rs:177:14: 184:6 dm:&'static &'static std::collections::HashMap<u32, hir::def::PathResolution, core::hash::BuildHasherDefault<rustc_data_structures::fnv::FnvHasher>>, contains_bindings:&'static mut bool]: core::ops::FnMut<(&'static hir::Pat,)>` [E0275]
src/librustc/lib.rs:1:1: 1:1 note: consider adding a `#![recursion_limit="128"]` attribute to your crate
error: aborting due to previous error