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/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.