Coherence rules for generic binary operator traits


In a discusion on another forum, @Manishearth was kind enough to talk with me about a few Rust topics, and a lot of what we said isn’t relevant here. However, after going back and forth a bit about the coherence rules for implementing generic traits for binary operators, I think he started to (at least slightly) agree with my point of view, and he recommended I make a post to this forum so other experts could look at it.

In short, if you’re revisiting the coherence rules, I hope to convince you these are both desirable and possible without breaking coherence or backwards compatibility:

impl<T>  Mul<T>  for  MyType<T>       //   MyType<T> * T
impl<T>  Mul<MyType<T>>  for  T       //   T * MyType<T>

As I’m sure most of you know, the current rules allow the first one but reject the second. This was very surprising to me, and it was my first introduction to the concept of coherence in Rust when I dove in nearly two years ago. Of course there are other languages which treat binary operators as methods on the first argument, and so I’ve seen things like this before:

a + b   // syntax sugar for a.add(b)

In many of those languages, if you aren’t in control of the implementation for a, you simply can’t replace its definition of add(), and you have to find another workaround. I don’t think this limitation applies to Rust. For example, despite not having control over the implementation of f64, both of these are allowed:

impl  Mul<f64>  for  MyType<f64>      //   MyType<T> * f64
impl  Mul<MyType<f64>>  for  f64      //   f64 * MyType<T>

In some cases, Rust does allow me to put methods on types which I don’t control, it only (currently) forbids me from doing it with generics. In any particular application, using only a subset of types, this could be adequate. Several library crates use macros to workaround this problem and then call those macros for each of the types they wish to support. That seems like a fine solution if you want to create a library which only supports a specific subset of types.

However, when writing a generic library intended for re-use with third party types, it’s a bit frustrating. Maybe a convention or design pattern would evolve where users got used to invoking macros from a library on their specific application types to import the functionality, but I hope you’ll agree that is not ideal.

Another workaround is to simply re-order the expression to only use the implementations which you’re currently allowed. However clarity is important when you’re translating an equation, and some operators are not commutative. This isn’t great, and it puts unnecessary burden on the writer and any future readers of the code:

 let z : Complex<f64> = f();
 // this should be  m = 1.0 - z
 let m = -(z - 1.0);

 let v : Complex<f64> = f();
 // this should be  d = 1.0 / v
 let d = Complex::new(1.0, 0.0) / v;

All of that to say, I think this is a problem worth solving if you can.

I’ve looked into the rationale for the current coherence rules (posts here, misc blogs, github discussions, etc), and I’ve read @nikomatsakis Little Orphan Impls blog post several times in the last 18 months. Copying from there, the two which seem most relevant are these:

| Impl Header                          | O | C | S | F | E |
| impl<T> Add<T> for MyBigInt          | X |   | X | X |   |
| impl<U> Add<MyBigInt> for U          |   |   |   |   |   |

Specifically in the context of binary operators, I’m really not sure either of those should be allowed. Even with appropriate bounds applied (presumably T or U supports a conversion to one of the integer types or implements a trait like Signed), they do not seem at all in the spirit of avoiding implicit conversions. I really like that Rust prevents me from adding i32 and i64 without a cast. Moreover, looking at the bigint definition in the num create, it doesn’t seem like it actually uses operators traits like this (obviously some other create could).

However, I’m not suggesting to break either of these (I appreciate your commitment to backwards compatibility). Instead, I want to suggest that the impls I’ve been talking about above seem like a different thing and could be treated differently.

If I had any say, my contribution to the list of desirable use cases would look like this:

| Impl Header                                        | ? |
| impl<T> Sub<T>  for  MyType<T>                     | X |
| impl<T> Sub<MyType<T>>  for  T                     | X |
| impl<T> Sub<MyType<T>>  for  MyType<T>             | X |
... and so on for 20 or 30 more lines of each operator :-)

These impls are declaring something stronger (and more restrictive) than the previous use cases above, and it doesn’t seem like they should introduce a coherence problem. If a third party explicitly instantiates your type, they’ve opted in to using it in a way that is more specific than MyBigInt above. Working through an example:

  1. Alice implements Matrix as allowed by the current coherence rules:

    impl Mul for Matrix

  2. Bob implements Complex<T> if allowed under future coherence rules:

    impl Mul for Complex impl Mul<Complex> for T

  3. Charlie starts using both crates, maybe one first and the other later:

    let A : Matrix = Matrix::ident(); let z : Complex = Complex::zero();

    // Provided by Alice’s crate, and it may work if // Complex satisfies all bounds required my Matrix let Q = A*z;

    // This is not provided by either crate, so it // does not cause a coherence problem problem // or break existing code. let P = z*A;

Obviously that’s not a complete proof of coherence, and I don’t have a definitive solution to recommend. I think it’s possible you could apply the Covered rule to just the binary operator traits where T is on both sides, and things might work out well. If you did special-case binary operators, it would not break the Hash use-case from Orphan Impls, which I think is where some of the tension comes from in previous analysis:

| Impl Header                          | O | C | S | F | E |
| impl<H> Hash<H> for MyStruct         | X |   | X | X | X |

I’d like to provide another example where Alice provided Matrix<T> instead of just Matrix, and Charlie uses Matrix<Complex<T>> with his own generics. However, I’m pretty sure that works well too, and this post is already pretty long.


cc @nikomatsakis @withoutboats


Your example doesn’t work. Alice’s first impl & Bob’s second impl are overlapping:

impl<T> Mul<T> for Matrix
impl<U> Mul<Complex<U>> for U

// T := Complex<Matrix>,
// U := Matrix

// Conflicting impls:
impl Mul<Complex<Matrix>> for Matrix
impl Mul<Complex<Matrix>> for Matrix


Well, the first impl isn’t even allowed, due to unconstrained type parameters. I think @excess meant impl<T> Mul<T> for Matrix<T>? This doesn’t conflict, I think.


The first impl doesn’t have an unconstrainted type parameter, the parameter is used at Mul<T>. And its definitely allowed today (which means it can’t be unallowed without a breaking change).


I want to be clear though that this is definitely well-motivated, I just don’t think there’s a workable solution to the problem short of giving up the properties the orphan rules give us.


Thank you both for taking the time to look at it. I’m pretty disappointed it doesn’t solve the whole problem.

I was thinking in terms of “first Charlie uses one crate, then he grabs another”, and I couldn’t see how that would break his existing code in either order. However, if Charlie grabs both at the same time and starts mixing them the way you’ve shown, it breaks again. Very frustrating.

If you ever do decide to make a breaking change in this area, I hope you will add my use cases to your list.


The idea of using different orphan rules for the binary op traits is interesting. Its a special case, but it makes sense. I’m not sure if its sound - that is, if the binary traits used the ‘covered’ rules, but other traits use another rule, can you leverage that difference to break the orphan rules? I’m not sure.


If the covered rule is sound and the current rule is sound, and they don’t mix - maybe, but I really don’t know. I don’t have anything close to a proof.


Yeah, this is along the lines of what I was suggesting.

Else, it might be possible to design lattice/intersection specialization to work with this.


Intersection impls can allow these two impls to overlap if there is a third impl Mul<Complex<Matrix>> for Matrix, but who defines it? Neither crate knows about both Complex and Matrix. This was basically a trade off between allowing Alice’s crate and allowing Bob’s crate, and we chose Alice.

More broadly what we concluded recently was that because we cannot force impls to be specializable (because they can always contain a ‘final’ associated type), specialization doesn’t allow us to relax the orphan rules at all. I think Aaron’s blog post explains this but it may not emphasize the fact that this discover is applicable in general (not just to making blanket impls backwards compatible); there is no restriction we can loosen because of specialization.


I’ve not read the back-and-forth in detail, but I wanted to say that I definitely consider the “binary operator” use case to arise all the time. If you go back to my Little Orphan Impls blog post, you’ll see that I talked about “self-like” parameters. I think that the binary operator is a case where you have two parameter that wish to be treated as self-like – this implies the “covered” rules, as opposed to the “ordered” rules (as it happens, the rules we implement today are not described there; this is I think accidental, but they turn out to be a kind of intersection of two of the other rules, which is actually good, as it gives us more room to expand in any direction we choose).

I sort of like the idea of being able to choose, on the trait, from different variants of the orphan rules. Changing the rules for a given trait would be backwards incompatible, which is unfortunate, since there are existing traits (notably Add but also others) where I might like to change. Still, we might be able to get away with it. However, I’ve been holding off on suggesting it until I can find a better mental model for how to explain it. (And right now it’s not in cache, so I won’t even try…)


Thank you for the reply. Do people use this one in practice?

impl<T: SomeBounds> Add<T> for SomeType

I tried to downplay it above (because I know Rust’s stance on backwards compatibility), but it just seems wrong. To my neophyte eyes, it looks like it provides implicit conversions in a language which otherwise discourages that kind of thing. Maybe I’d understand better if I knew of a real world example.


My easy_strings library contains the following impls.

impl<'a, T: AsRef<str> + ?Sized> AddAssign<&'a T> for EZString {
    fn add_assign(&mut self, other: &T) { *self.deref_mut() += &other.as_ref(); }

// Should be Borrow instead of AsRef, but Rust won't allow it
impl<T: AsRef<str> + ?Sized> PartialEq<T> for EZString {
    fn eq(&self, other: &T) -> bool { *self.0 == other.as_ref() }

I originally did this for Add as well, but had to remove it due to a conflicting impls issue. I’ll probably add it back once specialization is stabilized.

As for whether this is a good idea, that’s a matter of taste.


Thank you for the example. I understand why people like implicit conversions for strings, but it always seems to get messier when you take format options into account as well. Anyway, it shows that some people are using binop traits that way. I assume you would prefer this worked too:

impl<T: ...> Add<EZString> for T


It would be nice. In fact, I manually implemented it for &String, &&String, and &&str.

impl<'a, 'b> Add<&'a EZString> for &'b String {
    type Output = EZString;
    fn add(self, other: &EZString) -> Self::Output { Self::Output::from(self.clone()) + other }
impl<'a, 'b, 'c> Add<&'a EZString> for &'c &'b String {
    type Output = EZString;
    fn add(self, other: &EZString) -> Self::Output { *self + other }
impl<'a, 'b, 'c> Add<&'a EZString> for &'c &'b str {
    type Output = EZString;
    fn add(self, other: &EZString) -> Self::Output { Self::Output::from(*self) + other }