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:
-
Alice implements Matrix as allowed by the current coherence rules:
impl Mul for Matrix
-
Bob implements Complex<T> if allowed under future coherence rules:
impl Mul for Complex impl Mul<Complex> for T
-
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.