Closed matklad closed 6 years ago
This is actually a monomorphisation issue, though I'm surprised it hangs since we do try to detect recursive monomorphisations too.
So this seems to be related to resolving the Iterator::chain
method, though I'm not sure exactly what is going on. It will eventually hit the recursion limit (probably) though.
After waiting for a little bit, this is the log I get. So I think part of the problem here is that we slowly recurse; that is, each step appears to take quite a while, so our recursion depth isn't really growing fast.
...
DEBUG:rustc_trans::collector: => recursion depth=18
DEBUG:rustc_trans::collector: => type length=56
DEBUG:rustc_trans::collector: visiting rvalue const false
DEBUG:rustc_trans::collector: visiting constant const false @ bb0[0]
DEBUG:rustc_trans::collector: visiting rvalue _1
DEBUG:rustc_trans::collector: visiting rvalue const true
DEBUG:rustc_trans::collector: visiting constant const true @ bb0[5]
DEBUG:rustc_trans::collector: visiting rvalue _2
DEBUG:rustc_trans::monomorphize: resolve(def_id=DefId { krate: CrateNum(2), node: DefIndex(1660) => core/3e7145548a52c52830e3a99346688b33::iter[0]::sources[0]::empty[0] }, substs=Slice([()]))
DEBUG:rustc_trans::monomorphize: => free item
DEBUG:rustc_trans::monomorphize: resolve(def_id=DefId { krate: CrateNum(2), node: DefIndex(1660) => core/3e7145548a52c52830e3a99346688b33::iter[0]::sources[0]::empty[0] }, substs=Slice([()])) = std::iter::empty::<()>
DEBUG:rustc_trans::collector: visit_item_use(Instance { def: Item(DefId { krate: CrateNum(2), node: DefIndex(1660) => core/3e7145548a52c52830e3a99346688b33::iter[0]::sources[0]::empty[0] }), substs: Slice([()]) }, is_direct_call=true)
DEBUG:rustc_trans::collector: create_fn_trans_item(instance=std::iter::empty::<()>)
DEBUG:rustc_trans::collector: visiting constant const std::iter::empty @ bb0[8]
DEBUG:rustc_trans::collector: visiting rvalue const false
DEBUG:rustc_trans::collector: visiting constant const false @ bb2[0]
DEBUG:rustc_trans::monomorphize: resolve(def_id=DefId { krate: CrateNum(2), node: DefIndex(1508) => core/3e7145548a52c52830e3a99346688b33::iter[0]::iterator[0]::Iterator[0]::chain[0] }, substs=Slice([std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Empty<()>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>]))
DEBUG:rustc_trans::monomorphize: => associated item, attempting to find impl
DEBUG:rustc_trans::monomorphize: resolve_associated_item(trait_item=DefId { krate: CrateNum(2), node: DefIndex(1508) => core/3e7145548a52c52830e3a99346688b33::iter[0]::iterator[0]::Iterator[0]::chain[0] }, trait_id=DefId { krate: CrateNum(2), node: DefIndex(1500) => core/3e7145548a52c52830e3a99346688b33::iter[0]::iterator[0]::Iterator[0] }, rcvr_substs=Slice([std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Chain<std::iter::Empty<()>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>>, std::iter::Empty<()>]))
Hello, I just wanted to say that I add the same problem with the following code :
pub enum Equation<A, B> {
Mul(A, B),
Value(A),
}
impl<A, B> Default for Equation<A, B>
where
A: Default,
{
fn default() -> Self {
Equation::Value(A::default())
}
}
impl<A, B, T> From<T> for Equation<Equation<A, B>, Equation<A, B>>
where
T: ToString,
Equation<A, B>: From<T>,
A: Default,
{
fn from(input: T) -> Self {
let left: Equation<A, B> = input.to_string().into();
let right = Equation::default();
let result: Equation<Equation<A, B>, Equation<A, B>> = Equation::Mul(left, right);
return result;
}
}
fn main() {
println!("nothing to see here");
}
Here is playground link. This was on the latest stable (1.21).
@Mark-Simulacrum could the slow part being caused by exponential blowup? We can only reproduce with infinite recursion currently, so we can't easily confirm what's going on here. However, it's possible something like breadth-first search was used and causing the blowup here.
Anyway, here's a log dump (from debug-assertions build) for examination:
This is exponential. Have fun.
for N in {10..100}; do echo -n "$N: "; python -c "print(''.join('fn silly%d<I: Iterator<Item=()>>(it: I) {silly%d(it.chain(std::iter::empty()))}' % (n+1,n) for n in range($N)) + 'fn silly0<I: Iterator<Item=()>>(_it: I) {}fn main() {silly${N}(std::iter::empty());}')" | rustc - -Z time-passes | rg "translation item" || break; done
10: time: 0.011; rss: 87MB translation item collection
11: time: 0.022; rss: 87MB translation item collection
12: time: 0.040; rss: 87MB translation item collection
13: time: 0.071; rss: 87MB translation item collection
14: time: 0.136; rss: 87MB translation item collection
15: time: 0.265; rss: 87MB translation item collection
16: time: 0.516; rss: 88MB translation item collection
17: time: 1.037; rss: 87MB translation item collection
18: time: 2.033; rss: 87MB translation item collection
19: time: 4.062; rss: 88MB translation item collection
20: time: 8.326; rss: 87MB translation item collection
This tracks down to the same cause as https://github.com/rust-lang/rust/issues/38528#issuecomment-356110422.
Random suspension stack trace:
#0 0x00007ffff4850381 in rustc::ty::context::TyCtxt::_intern_substs () from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#1 0x00007ffff4657d96 in rustc::ty::subst::<impl rustc::ty::fold::TypeFoldable<'tcx> for &'tcx rustc::ty::Slice<rustc::ty::subst::Kind<'tcx>>>::super_fold_with () from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#2 0x00007ffff460d165 in rustc::ty::fold::TypeFoldable::fold_with () from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#3 0x00007ffff45f1c85 in rustc::traits::select::SelectionContext::impl_or_trait_obligations::{{closure}} ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#4 0x00007ffff4426dbb in <core::iter::FlatMap<I, U, F> as core::iter::iterator::Iterator>::next ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#5 0x00007ffff42b8f27 in <alloc::vec::Vec<T>>::extend_desugared () from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#6 0x00007ffff441eea9 in <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T, I>>::from_iter ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#7 0x00007ffff45f1a83 in rustc::traits::select::SelectionContext::impl_or_trait_obligations ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#8 0x00007ffff45f0fd2 in rustc::traits::select::SelectionContext::confirm_impl_candidate::{{closure}} ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#9 0x00007ffff453559c in rustc::infer::InferCtxt::in_snapshot () from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#10 0x00007ffff45e9e4f in rustc::traits::select::SelectionContext::confirm_candidate ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#11 0x00007ffff45dee2d in rustc::traits::select::SelectionContext::select () from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#12 0x00007ffff45d68df in rustc::traits::project::confirm_candidate () from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#13 0x00007ffff45d5413 in rustc::traits::project::opt_normalize_projection_type ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#14 0x00007ffff45d2c34 in rustc::traits::project::normalize_projection_type ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#15 0x00007ffff45d259e in <rustc::traits::project::AssociatedTypeNormalizer<'a, 'b, 'gcx, 'tcx> as rustc::ty::fold::TypeFolder<'gcx, 'tcx>>::fold_ty () from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#16 0x00007ffff46812ab in rustc::ty::structural_impls::<impl rustc::ty::fold::TypeFoldable<'tcx> for rustc::ty::Predicate<'tcx>>::super_fold_with () from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#17 0x00007ffff45f1d87 in rustc::traits::select::SelectionContext::impl_or_trait_obligations::{{closure}} ()
---Type <return> to continue, or q <return> to quit---
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#18 0x00007ffff4426dbb in <core::iter::FlatMap<I, U, F> as core::iter::iterator::Iterator>::next ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#19 0x00007ffff441ec4c in <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T, I>>::from_iter ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#20 0x00007ffff45f1a83 in rustc::traits::select::SelectionContext::impl_or_trait_obligations ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#21 0x00007ffff45f0fd2 in rustc::traits::select::SelectionContext::confirm_impl_candidate::{{closure}} ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#22 0x00007ffff453559c in rustc::infer::InferCtxt::in_snapshot () from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#23 0x00007ffff45e9e4f in rustc::traits::select::SelectionContext::confirm_candidate ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#24 0x00007ffff45dee2d in rustc::traits::select::SelectionContext::select () from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#25 0x00007ffff45d639c in rustc::traits::project::assemble_candidates_from_impls::{{closure}} ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#26 0x00007ffff45d6219 in rustc::traits::project::assemble_candidates_from_impls ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#27 0x00007ffff45d4470 in rustc::traits::project::opt_normalize_projection_type ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
#28 0x00007ffff45d2c34 in rustc::traits::project::normalize_projection_type ()
from /usr/bin/../lib/../lib/librustc-5407144f5a31b71b.so
With PoC in #48296 this resolves in finite time. The error is too silly though.
This code causes compiler to be stuck wasting CPU cycles, instead of printing some kind of recursion limit error.