Specialization (enabled by default on Nightly) causes inference regressions

[SimonSapin]

Test case (reduced for macro-generated unit tests):

use im::*;

fn main() {
    let _ = {
        Some((1, (None::<i32>, None::<i32>.into_iter().collect())))
            .into_iter()
            .collect::<OrdMap<_, _>>()
    } == {
        let mut map = OrdMap::new();
        map.insert(1, (None, OrdSet::<i32>::new()));
        map
    };
}

Compiles successfully on rustc 1.52.1 (9bc8c42bb 2021-05-09), errors on rustc 1.54.0-nightly (3e99439f4 2021-05-17):

error[E0283]: type annotations needed
 --> src/main.rs:6:56
  |
6 |         Some((1, (None::<i32>, None::<i32>.into_iter().collect())))
  |                                                        ^^^^^^^ cannot infer type for type parameter `B` declared on the associated function `collect`
  |
  = note: cannot satisfy `_: FromIterator<i32>`
help: consider specifying the type argument in the method call
  |
6 |         Some((1, (None::<i32>, None::<i32>.into_iter().collect::<B>())))
  |                                                               ^^^^^

error: aborting due to previous error

Now this code heavily relies on type inference, and it would be easy to make it less so by adding an annotation as suggested by the compiler. However I still wanted to understand why this errors happens in one case but not the other.

At first I suspected that a new standard library impl made inference ambiguous where it wasn’t before, but the same error also happens with older Nightlies from before 1.52 was branched.

The difference turns out to be im-rs enabling impl specialization when building on the Nightly channel:

https://github.com/bodil/im-rs/blob/3f4e01a43254fe228d1ce64e47dfaf4edc8f4f19/build.rs#L9-L13

If I remove this println (effectively disabling specialization) the test case compiles successfully on Nightly.

I tried but failed to reproduce the error without the full im-rs crate by using this instead:

#![feature(specialization)]
#![allow(incomplete_features)]

use std::iter::FromIterator;

pub struct OrdSet<A>(A);

pub struct OrdMap<K, V>(K, V);

impl<A> OrdSet<A> {
    pub fn new() -> Self {
        unimplemented!()
    }
}

impl<K, V> OrdMap<K, V> {
    pub fn new() -> Self {
        unimplemented!()
    }

    pub fn insert(&mut self, _k: K, _v: V) -> Self {
        unimplemented!()
    }
}

impl<A, R> FromIterator<R> for OrdSet<A>
where
    A: Ord + Clone + From<R>,
{
    fn from_iter<T>(_i: T) -> Self
    where
        T: IntoIterator<Item = R>,
    {
        unimplemented!()
    }
}

impl<K, V, RK, RV> FromIterator<(RK, RV)> for OrdMap<K, V>
where
    K: Ord + Clone + From<RK>,
    V: Clone + From<RV>,
{
    fn from_iter<T>(_i: T) -> Self
    where
        T: IntoIterator<Item = (RK, RV)>,
    {
        unimplemented!()
    }
}

impl<A> Clone for OrdSet<A> {
    fn clone(&self) -> Self {
        unimplemented!()
    }
}

impl<A: Ord> PartialEq for OrdSet<A> {
    fn eq(&self, _other: &Self) -> bool {
        unimplemented!()
    }
}


// Unspecialized

//impl<K, V> PartialEq for OrdMap<K, V>
//where
//    K: Ord + PartialEq,
//    V: PartialEq,
//{
//    fn eq(&self, _other: &Self) -> bool {
//        unimplemented!()
//    }
//}


// Specialized

impl<K, V> PartialEq for OrdMap<K, V>
where
    K: Ord + PartialEq,
    V: PartialEq,
{
    default fn eq(&self, _other: &Self) -> bool {
        unimplemented!()
    }
}

impl<K, V> PartialEq for OrdMap<K, V>
where
    K: Ord + Eq,
    V: Eq,
{
    fn eq(&self, _other: &Self) -> bool {
        unimplemented!()
    }
}

Possible it’s adding some other impl that causes inference ambiguity, but reading through docs I don’t see what would be relevant:

• https://docs.rs/im/15.0.0/im/struct.OrdSet.html#trait-implementations
• https://docs.rs/im/15.0.0/im/struct.OrdMap.html#trait-implementations

The FromIterator impls involve From conversions of items, but the map value in the example is a tuple and tuples don’t implement From other than for the identity conversion.