Changing module order causes specialization to fail

[tuxmark5]

The below example fails to compile with error "not all trait items implemented, missing: trait_1".
Swapping modules one and two causes the code to compile correctly.
The same issue happens when one and two are defined in external files.

Version: rustc 1.27.0-nightly (e82261d 2018-05-03)

#![feature(specialization)]

mod two {
    use one::{Foo, Trait};

    impl Trait for Foo<i32> {
        fn trait_2(&self) {}
    }
    
    impl Trait for Foo<i64> { // not all trait items implemented, missing: `trait_1`
        fn trait_2(&self) {}
    }
}

mod one {
    pub struct Foo<A> { data: A }
    
    pub trait Trait {
        fn trait_1(&self);
        fn trait_2(&self);
    }
    
    impl<A> Trait for Foo<A> {
        fn trait_1(&self) {}
        default fn trait_2(&self) {}
    }
}

fn main() {
}

[qnighy]

Minimized:

#![feature(specialization)]

pub trait Foo {
    fn foo();
}

impl Foo for i32 {}
impl Foo for i64 {
    // fn foo() {}
}
impl<T> Foo for T {
    fn foo() {}
}

In the current nightly, changing the order of the items or uncommenting the line will make it compile. The latter behavior is also strange.

[qnighy]

Ah, this is likely caused by a bug in specialization graph construction. Consider the following specialization graph:

  Tr1
   |
   I3
  /  \
 I1  I2

When we try to construct the graph by adding I1, I2, and I3 in this order, the intermediate graph will look like:

  Tr1
  /  \
 I1  I2

Then the compiler compares I1 and I3. The problem is, after the compiler find out that I1 specializes I3, it will immediately insert I3 between Tr1 and I1, resulting in the following graph:

  Tr1
  /  \
 I3  I2
  |
 I1

I will prepare a fix for this.