Interesting. This seems similar to the variant I suggested where the user distinguishes explicit from auxiliary traits, but instead with a focus on ordering. It also seems like something we could add as a backwards compatible extension once people are clamoring for it (though no individual trait could adopt a distinct ordering with potentially breaking downstream impls). Can you give an example where there is a natural ordering but Self is not the type on which you would want to dispatch?
Oops, it looks like you've already considered this case. I think your proposal already captures this possibility, since I was thinking specifically about dispatch on self type. I retract my suggestion!
I guess one important point is that there do exist workarounds to the latter problem but not the former.
Do you mean using newtypes? Well, it's not cost free, both efficiency-wise (consider a list of T, and you need to newtype T. Richard and company wrote a paper about how to implement coercions so newtypes would be cost-free in this circumstance) and usability-wise (great, now you have to reimplement every function you want to use on the newtype.) Yes, in principle you can work around it but it can be pretty painful.
it can still happen that two libraries cannot (easily) be made to work together since one library defines a trait that the other does not implement.
I actually think the situation is worse than that. Let me try to give a concrete example. Suppose that I'm a library writer, writing a BSON (like JSON but binary) library. An obvious thing to want to do is provide a ToBson trait.
It will be pretty normal for me to provide impls for any types which are in the standard library. But what about types that live outside: should I give an impl for mysql::value::Value in rust-mysql-simple? Well, maybe someone who uses BSON and that library would find this impl useful. But obviously the core BSON library shouldn't depend on rust-mysql-simple, that would just be silly. Nor should rust-mysql-simple depend on BSON: what does BSON serializing have anything to do with querying the database?
The obvious thing to do: put the bson/rust-mysql-simple adapter in its own crate, is disallowed under any permutation of the orphan rules. And it must be, because what do you do if two people write adapters? But it's the "common sense" way of how to solve the problem.
Introducing incoherent traits is one possibility.
There is a way to do this properly, although I suspect the ship may have already sailed for Rust. In Dreyer et al's Modular Type Classes, the possibility of multiple instances being available for one type is planned for the same type is accounted for from the start. You're not allowed to have incoherent resolution (i.e. the type checker should not have to make an arbitrary choice), but you can selectively expose/hide instances in scopes. This is the other logical conclusion after you axiomatize "linking should not fail." The further conclusion is that users must not assume traits are global when constructing data types; so the types you've given to, e.g. std::collections::BinaryHeap, are no good.
There is a way to support something like BinaryHeap however: the key is that a BinaryHeap type should be specialized to a specific trait. (In the standard ML module lingo, BinaryHeap is a functor, and the trait is passed in as a parameter module. Then Applicative Functor semantics specifies that IF the parameter modules are equal, then the instantiated functor--and its internal types--are equal as well.) Then when you use any of the operations, the specific trait you specialized is used; furthermore, a BinaryHeap with the same element type but a different trait is incompatible and you can't, e.g. merge them. Unfortunately, I suspect that the Rust team will not be so keen on (1) adding a whole new type system feature and (2) changing all of the core library definitions at this stage in the game. Plus, Scala tried to allow local type class instances, but completely failed on the type system front and ended up with something worse. But if I could go back in time, I'd figure out how to make this work for Haskell and fix our standard libraries to do this properly.
However, that seems like it would ultimately lead to the same problems you are describing -- libraries might ship based on some assumption of what a trait means for a given type, assuming that this assumption will be fulfilled in the final crate, and that assumption may not be compatible with what another library expects.
Well, I actually don't think this is too much of a problem: if you ship a library that leaves the trait unspecified except for some contract, it seems reasonable to expect the final crate to need to fulfill the contract but otherwise be given latitude in the implementation choice. There are lots of other cases where user code might not fulfill a contract, and Rust has no way of checking.