Recursion limit during monomorphization hit quicker on beta

[alexcrichton]

This program compiles successfully on stable but hits the recursion limit on beta/nightly. This seems like a regression where we hit it too quickly? Is it something we can perhaps fix?

The specific error is:

$ rustc +beta foo.rs
error: reached the recursion limit during monomorphization (selection ambiguity)

cc @rust-lang/compiler
originally reported as rust-lang-nursery/futures-rs#262

[alexcrichton]

Inlining for posterity:

use std::marker;
use std::mem;

fn main() {
    let workers = (0..0).map(|_| result::<u32, ()>());
    drop(join_all(workers).poll());
}

trait Future {
    type Item;
    type Error;

    fn poll(&mut self) -> Result<Self::Item, Self::Error>;
}

trait IntoFuture {
    type Future: Future<Item=Self::Item, Error=Self::Error>;
    type Item;
    type Error;

    fn into_future(self) -> Self::Future;
}

impl<F: Future> IntoFuture for F {
    type Future = F;
    type Item = F::Item;
    type Error = F::Error;

    fn into_future(self) -> F {
        self
    }
}

struct FutureResult<T, E> {
    _inner: marker::PhantomData<(T, E)>,
}

fn result<T, E>() -> FutureResult<T, E> {
    loop {}
}

impl<T, E> Future for FutureResult<T, E> {
    type Item = T;
    type Error = E;

    fn poll(&mut self) -> Result<T, E> {
        loop {}
    }
}

struct JoinAll<I>
    where I: IntoIterator,
          I::Item: IntoFuture,
{
    elems: Vec<<I::Item as IntoFuture>::Item>,
}

fn join_all<I>(_: I) -> JoinAll<I>
    where I: IntoIterator,
          I::Item: IntoFuture,
{
    loop {}
}

impl<I> Future for JoinAll<I>
    where I: IntoIterator,
          I::Item: IntoFuture,
{
    type Item = Vec<<I::Item as IntoFuture>::Item>;
    type Error = <I::Item as IntoFuture>::Error;

    fn poll(&mut self) -> Result<Self::Item, Self::Error> {
        let elems = mem::replace(&mut self.elems, Vec::new());
        elems.into_iter().map(|e| {
            e
        }).collect::<Vec<_>>();
        loop {}
    }
}

[arielb1]

Thats... not a recursion limit error

                    debug!("Encountered ambiguity selecting `{:?}` during trans, \
                            presuming due to overflow",
                           trait_ref);
                    tcx.sess.span_fatal(span,
                        "reached the recursion limit during monomorphization \
                         (selection ambiguity)");

Overflow does not cause ambiguity for quite some time.

[eddyb]

@arielb1 You mean this used to be the case, but now this is just ambiguous and not due to an overflow?

[arielb1]

DEBUG:rustc_trans::common: Encountered ambiguity selecting `Binder(<std::vec::Vec<u32> as std::vec::SpecExtend<std::iter::Map<std::vec::IntoIter<u32>, [closure@not-a-recursion-error.rs:74:31: 76:10]>>>)` during trans, presuming due to overflow

[arielb1]

There's no overflow, only ambiguity and a very outdated error message - overflow last caused ambiguity in the 0.X days.

[eddyb]

Then this looks like it's caused by an interaction between a bug(?) in specialization and the new (in beta?) specialization of Extend for Vec.
cc @bluss Have you seen this fatal error before, when working on code using specialization?

[arielb1]

Sure. Trans-time ambiguity is always a bug.

[arielb1]

DEBUG:rustc::traits::select: assembled 2 candidates for TraitObligationStack(Obligation(predicate=Binder(TraitPredicate(<std::vec::Vec<u32> as std::vec::SpecExtend<std::iter::Map<std::vec::IntoIter<u32>, [closure@not-a-recursion-error.rs:74:31: 76:10]>>>)),depth=0)): [ImplCandidate(DefId { krate: CrateNum(3), node: DefIndex(4218) => collections/92fdee2a092512a3f348f1bfb6992470::vec[0]::{{impl}}[28] }), ImplCandidate(DefId { krate: CrateNum(3), node: DefIndex(4231) => collections/92fdee2a092512a3f348f1bfb6992470::vec[0]::{{impl}}[29] })]

Could we have a -Z non-verbose-def-ids mode for logs?

[eddyb]

Oh I remember why this is so familiar: on one of my branches I broke a similar specialization by not sorting the predicates for constraining purposes. But here we can't just look at the history, this could be a bug that was always present in specialization, whether in this sorting logic or elsewhere.

[bluss]

@eddyb No, I have never seen it.

[arielb1]

This is like an annoying problem with the projection cache's handling of nested obligations.

Nested projection obligations enter here in this case:

DEBUG:rustc::traits::project: AssociatedTypeNormalizer: depth=3 normalized 
<std::iter::Map<std::ops::Range<i32>, [closure@not-a-recursion-error.rs:5:30: 5:53]> as 
std::iter::IntoIterator>::Item to _#7t with 12 add'l obligations

Here the normalization result is the result of the nested impl <[closure@not-a-recursion-error.rs:5:30: 5:53] as FnMut(i32)>::Output, which is an additional obligation that is a part of "add'l obligations".

By itself, this is proper behaviour - the additional obligation is returned, and the RFC 447 rules ensure that it is processed before the output #_7t is used in any way.

However, the projection cache breaks this - it caches the <std::iter::Map<std::ops::Range<i32>,[closure@not-a-recursion-error.rs:5:30: 5:53]> as std::iter::IntoIterator>::Item = #_7t resolution. Now everybody else that attempts to look up the projection will just get #_7t without any additional obligations. This obviously causes all sorts of trouble (here a spurious EvaluatedToAmbig results in specializations not being discarded here).

This appears to work in most cases because during "one-pass evaluation" we tend to process obligations in LIFO order - after an obligation is added to the cache, we process its nested obligations before we do anything else (and if we have a cycle, we handle it specifically). And this specific case can be fixed by this little patch that removes the violation of LIFO order:

diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index 76bead9..24731e8 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -1215,8 +1215,8 @@ fn confirm_closure_candidate<'cx, 'gcx, 'tcx>(
                                obligation,
                                &closure_type.sig,
                                util::TupleArgumentsFlag::No)
-        .with_addl_obligations(obligations)
         .with_addl_obligations(vtable.nested)
+        .with_addl_obligations(obligations)
 }
 
 fn confirm_callable_candidate<'cx, 'gcx, 'tcx>(

However, I am not sure relying on this "strict LIFO order evaluation" is particularly wise. cc @rust-lang/compiler .

[eddyb]

@arielb1 I'd r+ that patch, backport it to beta, and separately decide on the underlying design problem.

[nikomatsakis]

@arielb1 I feel like I fixed this bug recently

UPDATE: Or perhaps a related one. I can't find the branch I was thinking of just now.

[nikomatsakis]

Huh. Ah, I dimly recall now. I at one point had a fix that included the obligations in the cache entry, but I wasn't happy about it, and ultimately the problem was fixed by adding a call to with_addl_obligations(), probably the very same one you are talking about now. I think it's ok to rely on LIFO for the time being, though in general I hope we rework a lot of this code to be more general (I... "have thoughts").

[arielb1]

Opened PR.