I don’t have any amazing ideas, only some food for thought (mostly-disjoint courses, per paragraph, in a random order):
It’s worth remarking upon the fact that GHC fails to ensure coherence even in the absence of orphan instances. The problematic scenario is the same as the one we’re trying to solve here!
A way I like to think about type classes and coherence is that a type class Foo a is the combination of a dictionary type (Foo) and an open function (a: Type) -> Foo a which maps types to their dictionaries. Being an open function, its definitions (“arms” or whatever they’re called) do not need to be in one place, but may be interspersed throughout the program. (Correspondingly, Type is an "open enum" with “variants” interspersed throughout the program.) From this perspective, what we refer to as “coherence” boils down to ensuring that this function actually be a function - that it maps each input to no more than one output. (However, it will nearly always be partial, i.e. will lack an output for some inputs - when there is no impl.)
It’s not obvious to me that impl UnaryTrait for (A, B) is really “the same thing” as impl BinaryTrait<B> for A. It’s true that they are structurally similar from the perspective of coherence checking. But otherwise I think that this interpretation is just an accident of syntax and language. Syntax: Rust provides nice, privileged syntax for the built-in product types (including pairs). But product types have a particular meaning: what makes impl for Product<A, B> special here, as opposed to for Sum<A, B>, or for AnythingElse<A, B>? Language: we might want to read the first impl as "implement UnaryTrait for the pair of types A and B". But this is not actually right: "implement UnaryTrait for the pair type of A and B" is more accurate.
In the case of the MyVec and IntoIterator example from @nikomatsakis’s blog post, and all analogous cases, where you want both Add<MyVec<T>> for I as well as Add<I> for MyVec<T>, leading to overlap in the case of Add<MyVec<T>> for MyVec<T> (which impl should we choose?), what you really want to say is “it doesn’t matter, they have the same semantics”. But it’s not clear if there’s a good way to say this.
Along similar lines as the idea mentioned by @nikomatsakis, that orphan impls could be allowed in the “final” crate, which is the executable itself, an idea that has been bandied about a bit in the Haskell community to solve “the impl bson::ToBson for mysql::Value problem” is the ability to “forward declare” impls - to delegate the right to create the given impl, which would otherwise be considered an orphan, to a particular external crate. As the right is delegated only to a single, well-identified external crate, coherence is maintained. (This can be seen as a generalization of the “orphan impls in the executable crate” idea - where the right to create an orphan impl is delegated to “the main crate” by default, but can be overridden to specify a different crate where desired.) The big problem with this idea in the context of Rust, as far as I see it, is how in the world can a crate refer to the traits and types in the impl being forward declared, as well as the crate being delegated to, without depending on them? Haskell’s global module namespace otherwise feels like a misfeature, but it comes in handy here.
The long-time germ of an idea I’ve had myself for solving the same problem would be to allow “weak dependencies” between packages, along with “optionally present” items. If a package bee has a weak dependency on aye, then having aye is not a requirement to install bee, but certain (“optionally present”) items in bee (i.e. the ones which actually depend on aye) only become available when aye is installed. In practice, for example, bson would declare a weak dependency on mysql via Cargo, and have #[cfg(is_present(mysql))] impl ToBson for mysql::Value - or something like that. This raises various “interesting” engineering challenges, such as requiring bson to be recompiled if mysql is installed later on, which may or may not be surmountable. Notably this resolves “the triangle problem” at the technical level, but leaves it intact at the social level - the compatibility shim between mysql and bson must be provided and maintained by either mysql or bson, and the authors still need to come to an agreement about which it will be. That seems like a desirable thing, however. (Better than “disconnected” third-party compatibility shim packages from third-party authors floating around, I think.)
