Selection ambiguity with specialization, closures and associated types

[dylanede]

This code:

#![feature(specialization)]

use std::marker::PhantomData;

struct Foo<A, B> {
    marker: PhantomData<(A, B)>
}

trait Trait1 {
    type Out;
}

impl Trait1 for () {
    type Out = ();
}

impl<B, F, V> Trait1 for Foo<F, B> where B : Trait1, F : Fn() -> V {
    type Out = V;
}

trait Trait2<T> {}

impl<T> Trait2<T> for () {}

trait Trait3 {
    type Out;
}

impl<S, B> Trait3 for Foo<S, B> where B : Trait1, S : Trait2<B::Out> {
    type Out = ();
}

trait Special<T> {
    fn special_stuff();
}
impl<I, T> Special<T> for I {
    default fn special_stuff() {}
}
impl<T> Special<T> for () where T : Trait3, T::Out : Send {
    fn special_stuff() {}
}

fn f<F>(_: F) -> Foo<(), Foo<F, ()>> {
    Foo { marker: PhantomData }
}

fn bar<T : 'static>(_: T) {
    <() as Special<T>>::special_stuff();
}

fn main() {
    bar(f(|| ()));
}

triggers

error: reached the recursion limit during monomorphization (selection ambiguity)

It seems to depend on the use of specialization, constraints involving Fn, and the use of constraints on associated types. Rustc debug output gives me this at the end of the log, which suggests that it is not actually a recursion limit problem:

DEBUG:rustc::traits::select: evaluate_predicate_recursively(Obligation(predicate=Binder(TraitPredicate(<() as std::marker::Send>)),depth=2)) = EvaluatedToOk
DEBUG:rustc::infer: rollback_to(cause=probe)
DEBUG:rustc::infer::type_variable: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(24)
DEBUG:rustc_data_structures::unify: TyVid: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(18)
DEBUG:rustc_data_structures::unify: TyVid: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(18)
DEBUG:rustc_data_structures::unify: IntVid: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(12)
DEBUG:rustc_data_structures::unify: FloatVid: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(12)
DEBUG:rustc::infer::region_inference: RegionVarBindings: rollback_to(RegionSnapshot(length=12,skolemization=0))
DEBUG:rustc_data_structures::unify: RegionVid: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(12)
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(1)
DEBUG:rustc::traits::select: evaluate_candidate: depth=1 result=EvaluatedToOk
DEBUG:rustc_metadata::decoder: def_path(id=DefIndex(735))
DEBUG:rustc::traits::select: CACHE MISS: EVAL(Binder(<() as std::marker::Send>))=EvaluatedToOk
DEBUG:rustc::ty::fold: HasTypeFlagsVisitor: t=() t.flags=0 self.flags=200
DEBUG:rustc_metadata::decoder: def_path(id=DefIndex(735))
DEBUG:rustc::traits::select: evaluate_predicate_recursively(Obligation(predicate=Binder(TraitPredicate(<() as std::marker::Send>)),depth=1)) = EvaluatedToOk
DEBUG:rustc::infer: rollback_to(cause=probe)
DEBUG:rustc::infer::type_variable: inference variable _#0t popped
DEBUG:rustc::infer::type_variable: inference variable _#1t popped
DEBUG:rustc::infer::type_variable: inference variable _#2t popped
DEBUG:rustc::infer::type_variable: inference variable _#3t popped
DEBUG:rustc::infer::type_variable: inference variable _#4t popped
DEBUG:rustc::infer::type_variable: inference variable _#5t popped
DEBUG:rustc::infer::type_variable: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(0)
DEBUG:rustc_data_structures::unify: TyVid: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(0)
DEBUG:rustc_data_structures::unify: TyVid: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(0)
DEBUG:rustc_data_structures::unify: IntVid: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(0)
DEBUG:rustc_data_structures::unify: FloatVid: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(0)
DEBUG:rustc::infer::region_inference: RegionVarBindings: rollback_to(RegionSnapshot(length=0,skolemization=0))
DEBUG:rustc_data_structures::unify: RegionVid: rollback_to()
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(0)
DEBUG:rustc_data_structures::snapshot_vec: rollback_to(0)
DEBUG:rustc::traits::select: evaluate_candidate: depth=0 result=EvaluatedToAmbig
DEBUG:rustc::traits::select: Retaining candidate #0/2: EvaluatedCandidate { candidate: ImplCandidate(DefId { krate: CrateNum(0), node: DefIndex(19) => desktop/b0ae575::{{impl}}[4] }), evaluation: EvaluatedToOk }
DEBUG:rustc::traits::specialize: specializes(DefId { krate: CrateNum(0), node: DefIndex(19) => desktop/b0ae575::{{impl}}[4] }, DefId { krate: CrateNum(0), node: DefIndex(21) => desktop/b0ae575::{{impl}}[5] })
DEBUG:rustc::traits::select: Retaining candidate #1/2: EvaluatedCandidate { candidate: ImplCandidate(DefId { krate: CrateNum(0), node: DefIndex(21) => desktop/b0ae575::{{impl}}[5] }), evaluation: EvaluatedToAmbig }
DEBUG:rustc::traits::select: multiple matches, ambig
DEBUG:rustc::ty::fold: HasTypeFlagsVisitor: t=() t.flags=0 self.flags=4
DEBUG:rustc::ty::fold: HasTypeFlagsVisitor: t=Foo<(), Foo<[closure@src\bin\desktop.rs:52:11: 52:16], ()>> t.flags=600 self.flags=4
DEBUG:rustc::traits::trans: Encountered ambiguity selecting `Binder(<() as Special<Foo<(), Foo<[closure@src\bin\desktop.rs:52:11: 52:16], ()>>>>)` during trans, presuming due to overflow
error: reached the recursion limit during monomorphization (selection ambiguity)

The two impls it is finding and being unable to pick between are the two impls of Special in the source, even though one specializes the other.

[dylanede]

@alexcrichton This might be related to the similar errors that pop up with the futures crate.

[goffrie]

I guess this was probably related to #40003 - seems to compile fine on nightly now.

[cyplo]

Compiles on rustc 1.25.0-nightly (27a046e93 2018-02-18) - would we need anything more to close this issue ? Thank you :)