rustc hangs in infinite loop with recursive unboxed closures

[ilammy]

I have been trying to write a generic tree diff, but during that I seem to have accidentally proved that something in rustc is Turing-complete.

Here is the minimal code I have been able to reproduce the issue with. If this is fed to rustc then it hangs itself in an infinite loop:

#[derive(Debug, PartialEq)]
struct Tree(Vec<Tree>);

fn process<F: Fn() -> ()>(tree: &Tree, fun: F) -> Tree {
    Tree(tree.0.iter()
             .map(|child| process(child, || fun()))
             .collect())
}

fn main() {
    assert_eq!(Tree(vec![]), process(&Tree(vec![]), || ()));
}

If generic F is replaced with an Fn reference then the snippet (obviously) compiles and runs just fine.

If fun is not used in process or the iter().map().collect() chain is rewritten into a for-loop then rustc fails (as expected, I believe) with

error: reached the recursion limit during monomorphization

Memory usage is constant when this happens, rustc just eats up all available CPU.

I have reproduced this on 64-bit Linux and Windows (GNU) versions, with current stable (1.8), beta, and nightly (d91f8ab) builds. The behavior is identical for all of them.

Here is an example stacktrace of the nightly rustc during the hang. It does not grow infinitely, just fluctuates around 160 calls when I break into gdb.

#0  0x00007ffff3e9da71 in _$LT$std..collections..HashMap$LT$K$C$$u20$V$C$$u20$S$GT$$GT$::get::ha5af14897e541d81 () from /usr/local/bin/../lib/librustc-cb705824.so
#1  0x00007ffff3e97eb5 in rustc::ty::context::TyCtxt::intern_ty::h3316d09e2cb92bd4 () from /usr/local/bin/../lib/librustc-cb705824.so
#2  0x00007ffff3cb49ca in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#3  0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#4  0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#5  0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#6  0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#7  0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#8  0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#9  0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#10 0x00007ffff3de9fe5 in rustc::ty::fold::TypeFolder::fold_substs::h3aaf2aa2e6bf8bc7 () from /usr/local/bin/../lib/librustc-cb705824.so
#11 0x00007ffff3e1fba5 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#12 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#13 0x00007ffff3de9fe5 in rustc::ty::fold::TypeFolder::fold_substs::h3aaf2aa2e6bf8bc7 () from /usr/local/bin/../lib/librustc-cb705824.so
#14 0x00007ffff3e1fba5 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#15 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#16 0x00007ffff3de9fe5 in rustc::ty::fold::TypeFolder::fold_substs::h3aaf2aa2e6bf8bc7 () from /usr/local/bin/../lib/librustc-cb705824.so
#17 0x00007ffff3e1fba5 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#18 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#19 0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#20 0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#21 0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#22 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#23 0x00007ffff3de9fe5 in rustc::ty::fold::TypeFolder::fold_substs::h3aaf2aa2e6bf8bc7 () from /usr/local/bin/../lib/librustc-cb705824.so
#24 0x00007ffff3e1fba5 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#25 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#26 0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#27 0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#28 0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#29 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#30 0x00007ffff3de9fe5 in rustc::ty::fold::TypeFolder::fold_substs::h3aaf2aa2e6bf8bc7 () from /usr/local/bin/../lib/librustc-cb705824.so
#31 0x00007ffff3e1fba5 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#32 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#33 0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#34 0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#35 0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#36 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#37 0x00007ffff3de9fe5 in rustc::ty::fold::TypeFolder::fold_substs::h3aaf2aa2e6bf8bc7 () from /usr/local/bin/../lib/librustc-cb705824.so
#38 0x00007ffff3e1fba5 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#39 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#40 0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#41 0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#42 0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#43 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#44 0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#45 0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#46 0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#47 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#48 0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#49 0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#50 0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#51 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#52 0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#53 0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#54 0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#55 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#56 0x00007ffff3de9fe5 in rustc::ty::fold::TypeFolder::fold_substs::h3aaf2aa2e6bf8bc7 () from /usr/local/bin/../lib/librustc-cb705824.so
#57 0x00007ffff3e1fba5 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#58 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#59 0x00007ffff3de9fe5 in rustc::ty::fold::TypeFolder::fold_substs::h3aaf2aa2e6bf8bc7 () from /usr/local/bin/../lib/librustc-cb705824.so
#60 0x00007ffff3e1fba5 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#61 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#62 0x00007ffff3de9fe5 in rustc::ty::fold::TypeFolder::fold_substs::h3aaf2aa2e6bf8bc7 () from /usr/local/bin/../lib/librustc-cb705824.so
#63 0x00007ffff3e1fba5 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#64 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#65 0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#66 0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#67 0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#68 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#69 0x00007ffff3de9fe5 in rustc::ty::fold::TypeFolder::fold_substs::h3aaf2aa2e6bf8bc7 () from /usr/local/bin/../lib/librustc-cb705824.so
#70 0x00007ffff3e1fba5 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#71 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#72 0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#73 0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#74 0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#75 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#76 0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#77 0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#78 0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#79 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#80 0x00007ffff3cb4fa5 in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#81 0x00007ffff3cb4782 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$collections..vec..Vec$LT$T$GT$$GT$::super_fold_with::h03b7b2c79b6c8a4a () from /usr/local/bin/../lib/librustc-cb705824.so
#82 0x00007ffff3e1fc4c in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..sty..ClosureSubsts$LT$$u27$tcx$GT$$GT$::super_fold_with::he8a3ca532786c7b7 () from /usr/local/bin/../lib/librustc-cb705824.so
#83 0x00007ffff3cb539b in _$LT$traits..project..AssociatedTypeNormalizer$LT$$u27$a$C$$u20$$u27$b$C$$u20$$u27$tcx$GT$$u20$as$u20$ty..fold..TypeFolder$LT$$u27$tcx$GT$$GT$::fold_ty::h68ee7bafadfb4356 () from /usr/local/bin/../lib/librustc-cb705824.so
#84 0x00007ffff3dea09e in rustc::ty::fold::TypeFolder::fold_substs::h3aaf2aa2e6bf8bc7 () from /usr/local/bin/../lib/librustc-cb705824.so
#85 0x00007ffff3de9d33 in rustc::ty::fold::TypeFolder::fold_trait_ref::h40721108f270d5d5 () from /usr/local/bin/../lib/librustc-cb705824.so
#86 0x00007ffff3de9bf5 in rustc::ty::structural_impls::_$LT$impl$u20$ty..fold..TypeFoldable$LT$$u27$tcx$GT$$u20$for$u20$ty..Predicate$LT$$u27$tcx$GT$$GT$::super_fold_with::h131e072307513cfa () from /usr/local/bin/../lib/librustc-cb705824.so
#87 0x00007ffff3e48b94 in rustc::traits::project::AssociatedTypeNormalizer::fold::h267ab7cb84e8dd89 () from /usr/local/bin/../lib/librustc-cb705824.so
#88 0x00007ffff3e48454 in rustc::traits::select::SelectionContext::impl_or_trait_obligations::_$u7b$$u7b$closure$u7d$$u7d$::hf7cc18488cdcd0a8 ()
   from /usr/local/bin/../lib/librustc-cb705824.so
#89 0x00007ffff3e4729c in _$LT$core..iter..FlatMap$LT$I$C$$u20$U$C$$u20$F$GT$$u20$as$u20$core..iter..Iterator$GT$::next::h604d4ad004d72e71 ()
   from /usr/local/bin/../lib/librustc-cb705824.so
#90 0x00007ffff3e46749 in _$LT$collections..vec..Vec$LT$T$GT$$u20$as$u20$core..iter..FromIterator$LT$T$GT$$GT$::from_iter::hc8ebb6d2bda2fe12 ()
   from /usr/local/bin/../lib/librustc-cb705824.so
#91 0x00007ffff3e41137 in rustc::traits::select::SelectionContext::impl_or_trait_obligations::h9299969983c944b9 () from /usr/local/bin/../lib/librustc-cb705824.so
#92 0x00007ffff3e41c64 in rustc::traits::select::SelectionContext::vtable_impl::hf82e3ed500e09e97 () from /usr/local/bin/../lib/librustc-cb705824.so
#93 0x00007ffff3e41735 in rustc::infer::InferCtxt::in_snapshot::hfefa2a2f5f06ecb8 () from /usr/local/bin/../lib/librustc-cb705824.so
#94 0x00007ffff3e2d95d in rustc::traits::select::SelectionContext::confirm_candidate::h560246667e9ee7ff () from /usr/local/bin/../lib/librustc-cb705824.so
#95 0x00007ffff3e14da6 in rustc::traits::select::SelectionContext::select::haeac39fa699f74ae () from /usr/local/bin/../lib/librustc-cb705824.so
#96 0x00007ffff602700b in rustc_trans::common::fulfill_obligation::hb97500cd4d49823c () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#97 0x00007ffff60a233a in _$LT$collector..MirNeighborCollector$LT$$u27$a$C$$u20$$u27$tcx$GT$$u20$as$u20$rustc..mir..visit..Visitor$LT$$u27$tcx$GT$$GT$::visit_operand::he821f3fcf2b864dc () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#98 0x00007ffff609bc4e in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#99 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#100 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#101 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#102 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#103 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#104 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#105 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#106 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#107 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#108 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#109 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#110 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#111 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#112 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#113 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#114 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#115 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#116 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#117 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#118 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#119 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#120 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#121 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#122 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#123 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#124 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#125 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#126 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#127 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#128 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#129 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#130 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#131 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#132 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#133 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#134 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#135 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#136 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#137 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#138 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#139 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#140 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#141 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#142 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#143 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#144 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#145 0x00007ffff609c9d9 in rustc_trans::collector::collect_items_rec::h1ad7c2e6e81f5b01 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#146 0x00007ffff60660ae in rustc_trans::base::collect_translation_items::_$u7b$$u7b$closure$u7d$$u7d$::h33d9d5954414c1ad ()
   from /usr/local/bin/../lib/librustc_trans-cb705824.so
#147 0x00007ffff6051844 in rustc_trans::base::trans_crate::h6ed1dbd6e572a8c2 () from /usr/local/bin/../lib/librustc_trans-cb705824.so
#148 0x00007ffff7a8f0b0 in rustc_driver::driver::phase_4_translate_to_llvm::hd7579aae98641824 () from /usr/local/bin/../lib/librustc_driver-cb705824.so
#149 0x00007ffff7a8d6f2 in rustc_driver::driver::compile_input::_$u7b$$u7b$closure$u7d$$u7d$::he3c6b6ab9afe28dd () from /usr/local/bin/../lib/librustc_driver-cb705824.so
#150 0x00007ffff7a89ca1 in rustc_driver::driver::phase_3_run_analysis_passes::_$u7b$$u7b$closure$u7d$$u7d$::hfdd8d88ff571b474 ()
   from /usr/local/bin/../lib/librustc_driver-cb705824.so
#151 0x00007ffff7a835cf in rustc::ty::context::TyCtxt::create_and_enter::ha551c2427049829f () from /usr/local/bin/../lib/librustc_driver-cb705824.so
#152 0x00007ffff7a4eaa6 in rustc_driver::driver::compile_input::h0629572e6f316b31 () from /usr/local/bin/../lib/librustc_driver-cb705824.so
#153 0x00007ffff7a3e57e in rustc_driver::run_compiler::h8902aebf8b1849a8 () from /usr/local/bin/../lib/librustc_driver-cb705824.so
#154 0x00007ffff7a3b83e in std::sys_common::unwind::try::try_fn::h4c74456035d0fcc7 () from /usr/local/bin/../lib/librustc_driver-cb705824.so
#155 0x00007ffff752c4fc in __rust_try () from /usr/local/bin/../lib/libstd-cb705824.so
#156 0x00007ffff752c48e in std::sys_common::unwind::inner_try::h47a4d9cd4a369dcd () from /usr/local/bin/../lib/libstd-cb705824.so
#157 0x00007ffff7a3c26b in _$LT$F$u20$as$u20$std..boxed..FnBox$LT$A$GT$$GT$::call_box::h27f542a39f1d61ef () from /usr/local/bin/../lib/librustc_driver-cb705824.so
#158 0x00007ffff753a6d5 in std::sys::thread::Thread::new::thread_start::h6f266e069bf4ec2b () from /usr/local/bin/../lib/libstd-cb705824.so
#159 0x00007fffef2b1182 in start_thread (arg=0x7fffed7ff700) at pthread_create.c:312
#160 0x00007ffff718747d in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:111

[nathdobson]

Most common non-terminating cases will reach the recursion limit in linear time, but some take an exponential amount of time. For example (verified in rust 1.8):

use std::marker::PhantomData;
struct Zero;
struct Succ<T>(PhantomData<T>);
trait Nat {
    fn slow<T>();
}
impl Nat for Zero {
    fn slow<T>() {}
}
impl<N: Nat> Nat for Succ<N> {
    fn slow<T>() {
        N::slow::<(f32,T)>();
        N::slow::<(f64,T)>();
    }
}
fn slow<N: Nat>() {
    N::slow::<()>();
}
fn explode<N: Nat>(){
    slow::<N>();
    explode::<Succ<N>>();
}
fn main(){
    explode::<Zero>();
}

I'm pretty sure that it's not decidable whether monomorphization will terminate, so we're probably stuck with some cases like this. In addition, the compiler probably just guarantees that non-terminating cases won't compile, not what happens when you try to compile them.
I'm not sure what's going on with your case, because I don't know how closures get specialized. I'll continue looking for an explanation.

[DemiMarie]

Is it possible for the recursion limit to take more than exponential time to reach?

[nathdobson]

It seems unlikely. When monomorphizing a function, the compiler will monomorphize a bounded number of other functions. Assuming recursion depth actually increases with each call, the number of distinct monomorphized functions should be at most exponential in the recursion limit. However, you should be able to use #[inline(always)] to generate functions with exponential size in the recursion depth. If the compiler uses any optimizations that are exponential in code size, and these optimizations occur during monomorphization, then it would take a superexponential amount of time to reach the recursion limit. In all likelihood, such optimizations turn off once code reaches a certain size.

I haven't had any luck understanding what happens with the original code.

[arielb1]

Not sure what is the best way to resolve this. Maybe we could add a polymorphic monomorphization recursion checker that detects cases of foo<T> requires foo<X<T>>. Problem is, there can be loops involving associated types. Maybe just drop them? But that will just cause confusion.

Maybe limit the amount of monomorphizations per function to a million or something? Testing shows this would take too much (10s on this trivial example, so worse on bigger ones). 64k sounds too small.

Maybe limit polymorphically recursive functions to recursion_limit*1024 monomorphizations? That will ignore a bajillion calls to Option::unwrap etc. while catching the interesting cases.

[ishitatsuyuki]

I believe this is fixed with #48296. Playground: https://play.rust-lang.org/?gist=e8a4ee3a198c6c8c543cce18e6eb8bbb&version=nightly