coherence check affected by module ordering

[nikomatsakis]

As reported by @konstin on the rustfmt repo in rust-lang/rustfmt#2824, apparently the pyo3 project coherence check is affected by module ordering:

---

rusfmt breaks pyo3 in the sense that it doesn't build after running cargo fmt.

Reproducing:

git clone https://github.com/pyo3/pyo3
cd pyo3
git checkout 68c14a5707dd92ceef7619c0a5444cefcc78a0f6 # Recent, but fixed commit
cargo build # Fine
cargo fmt
cargo build # Broken

The last command results in a conflicting implementations error, even though only the formatting should have changed:

error[E0119]: conflicting implementations of trait `python::IntoPyDictPointer` for type `()`:
   --> src/objects/dict.rs:247:1
    |
247 | / impl<K, V, I> IntoPyDictPointer for I
248 | | where
249 | |     K: ToPyObject,
250 | |     V: ToPyObject,
...   |
260 | |     }
261 | | }
    | |_^ conflicting implementation for `()`
    | 
   ::: src/noargs.rs:61:1
    |
61  |   impl IntoPyDictPointer for () {
    |   ----------------------------- first implementation here
    |
    = note: upstream crates may add new impl of trait `std::iter::Iterator` for type `()` in future versions

Versions:

• cargo fmt --version: rustfmt 0.8.2-nightly (87edd75 2018-06-22)
• rustc --version: rustc 1.28.0-nightly (e3bf634 2018-06-28)

[nikomatsakis]

This may be related to incremental compilation. @Rantanen follows up with this:

---

Got curious about this so did some research into it.

This feels like a rustc bug. The offending file is src/objects/mod.rs and the cause is the reordering of the mod statements at the bottom.

After cargo fmt the mod import list is in the following order (highlights mine):

mod boolobject;
mod bytearray;
mod dict;  // <- dict
pub mod exc;
mod floatob;
mod iterator;
mod list;
mod module;  // <- module
mod sequence;
mod set;
mod slice;
mod stringdata;
mod stringutils;
mod tuple;
mod typeobject;  // <- typeobject

This causes the compilation error. I could fix this in two ways.

• Raise the highlighted lines on top of all the imports and order them as typeobject, module and dict.
• Drop the highlighted lines to the bottom of all the imports and order them as typeobject, dict and module.

Also once the crate has been built successfully, it will continue to compile just fine even with cargo fmt restoring the "broken" order. The build will fail only after deleting target/debug/incremental/pyo3* and target/debug/deps/pyo3*.

Also looking at the error message. That is an impl for I where I: IntoIterator<Item = (K, V)>. How is that a conflicting implementation for type () - is there some "empty tuple into any iterator" impl somewhere?

[nikomatsakis]

Nominating as it seems pretty important to know what is happening here.

[nikomatsakis]

I can reproduce the problem following the given steps.

[nikomatsakis]

Nominating as P-high, I will investigate.

[pnkfelix]

visited for triage. @nikomatsakis is currently out, but scheduled to be back early next week, so we'll just wait until next team mtg to see what progress is made.

[nikomatsakis]

egads I forgot about this. I will try to make progress on it this week.

[nikomatsakis]

Huh. Very curious. So I am able to reproduce the error (and lack of error) -- though with modern compilers something has changed with respect to proc macros so I had to remove a few pub use to get things building.

Applying cargo fmt does make the error start happening.

But reordering modules in the way described by @Rantanen did not (for me) make the error go away. I was however testing with CARGO_INCREMENTAL=0 which may be a factor.

Also, just applying cargo fmt to objects/mod.rs did not make the error start.

[nikomatsakis]

The error does seem to arise if I format just these two files: src/objects/mod.rs and src/lib.rs

[nikomatsakis]

Actually, just src/lib.rs is enough

[nikomatsakis]

specifically this diff:

diff --git a/src/lib.rs b/src/lib.rs
index 729185a..640234b 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -197,23 +197,23 @@ macro_rules! wrap_function (
     };
 );
 
-pub mod python;
-mod err;
+#[doc(hidden)]
+pub mod argparse;
+pub mod buffer;
+#[doc(hidden)]
+pub mod callback;
 mod conversion;
+mod err;
+pub mod freelist;
 mod instance;
+mod noargs;
 mod object;
-mod objects;
 mod objectprotocol;
-mod noargs;
+mod objects;
+pub mod prelude;
+pub mod python;
 mod pythonrun;
-#[doc(hidden)]
-pub mod callback;
 pub mod typeob;
-#[doc(hidden)]
-pub mod argparse;
-pub mod buffer;
-pub mod freelist;
-pub mod prelude;
 
 // re-export for simplicity
 #[doc(hidden)]

[konstin]

though with modern compilers something has changed with respect to proc macros so I had to remove a few pub use to get things building.

Yep, that's fixed on master since the v0.3.0 tag

[nikomatsakis]

This diff seems to suffice to make the error start to happen:

Unstaged changes (1)
modified   src/lib.rs
@@ -201,10 +201,10 @@ pub mod python;
 mod err;
 mod conversion;
 mod instance;
+mod noargs;
 mod object;
 mod objects;
 mod objectprotocol;
-mod noargs;
 mod pythonrun;
 #[doc(hidden)]
 pub mod callback;

[nikomatsakis]

OK so it turns out that this is a specialization bug. Here is a minimized test case which (incorrectly) compiles:

#![feature(specialization)]

use std::iter::Iterator;

trait IntoPyDictPointer { }

struct Foo { }

impl Iterator for Foo {
  type Item = ();
  fn next(&mut self) -> Option<()> {
      None
  }
}

impl IntoPyDictPointer for Foo { }

impl<I> IntoPyDictPointer for I
where
    I: Iterator,
{
}

impl IntoPyDictPointer for ()
{
}

fn main() { }

The problem is that -- when building the spec graph -- we somehow wind up such that the impl for () and the impl for T are never compared. Not 100% sure the cause yet. Not clear though that the P-high priority is justified, since stabilization is unstable -- but would be good to fix!

[nikomatsakis]

OK, I think I see the bug. It's kind of subtle and has to do with the interaction with simplified type improvements.

[nikomatsakis]

So the strategy of inserting into the tree is that it walks over a list of &mut DefId representing the children at any given level:

rust/src/librustc/traits/specialize/specialization_graph.rs

Lines 113 to 116 in 5ba2184

	for slot in match simplified_self {
	Some(sty) => self.filtered_mut(sty),
	None => self.iter_mut(),
	} {

If it finds that the current def-id D is broader than some child C, it replaces C with D:

rust/src/librustc/traits/specialize/specialization_graph.rs

Lines 167 to 173 in 5ba2184

	} else if ge && !le {
	debug!("placing as parent of TraitRef {:?}",
	tcx.impl_trait_ref(possible_sibling).unwrap());
	// possible_sibling specializes the impl
	*slot = impl_def_id;
	return Ok(Inserted::Replaced(possible_sibling));

and adds C as a child of D:

rust/src/librustc/traits/specialize/specialization_graph.rs

Lines 262 to 268 in 5ba2184

	Replaced(new_child) => {
	self.parent.insert(new_child, impl_def_id);
	let mut new_children = Children::new();
	new_children.insert_blindly(tcx, new_child);
	self.children.insert(impl_def_id, new_children);
	break;
	}

The flaw here is that there is not a single list of children. Rather, there are many lists, sorted by the simplified types. If the simplied type of C is not equal to the simplified type of D, then D ends up in the wrong list.

Probably the fix is to not try to be so clever. We can just remove C from the appropriate list and then (separately) add D -- or, if we want to micro-optimize, we could replace C with D if they share a simplified type, but that feels a bit overkill to me.

[nikomatsakis]

Fix pending in #52546 -- needs review.