Pre-RFC: Right-hand binary operator dispatch

language design
1

Motivation

One of the key paper cut encountered when implementing binary operators over custom types is that the dispatch is driven by the left-hand operand, and the ability to add binary operators on the left-hand operand is limited at the moment by E0210.

Consider the following Playground link:

#[derive(Clone, Copy, Debug)]
pub struct Speed(f64);

impl MulAssign<f64> for Speed {
    fn mul_assign(&mut self, other: f64) { self.0 *= other; }
}

impl Mul<f64> for Speed {
    type Output = Self;
    
    fn mul(mut self, other: f64) -> Self { self *= other; self }
}

impl Mul<Speed> for f64 {
    type Output = Speed;
    
    fn mul(self, mut other: Speed) -> Speed { other *= self; other }
}

The latter implementation is allowed because f64 is a concrete type.

On the other hand:

#[derive(Clone, Copy, Debug)]
pub struct Tagged<V, T> {
    value: V,
    tag: PhantomData<fn(T) -> T>,
}

impl<V, T> MulAssign<V> for Tagged<V, T>
where
    V: MulAssign,
{
    fn mul_assign(&mut self, other: V) { self.value *= other; }
}

impl<V, T> Mul<V> for Tagged<V, T>
where
    V: MulAssign,
{
    type Output = Self;
    
    fn mul(mut self, other: V) -> Self { self *= other; self }
}

impl<V, T> Mul<Tagged<V, T>> for V
where
    V: MulAssign,
{
    type Output = Tagged<V, T>;
    
    fn mul(self, mut other: Tagged<V, T>) -> Tagged<V, T> { other *= self; other }
}

On the other hand, the latter implementation fails due to E0210, as V is not "covered".

This means that code like untagged * tagged will later fails to compile, as there'll be no implementation of Mul which matches.

Guide-level Explanation

In Rust, the binary operators can be dispatched either by left-hand side, or right-hand side operand:

  • Add, Sub, Mul, Div, PartialEq, PartialOrd, etc... are dispatched by left-hand side.
  • AddAlt, SubAlt, MulAlt, DivAlt, PartialEqAlt, PartialOrdAlt, etc... are dispatched by right-hand side.

Dispatching by right-hand side is useful for implementing operators on generic left-hand side values:

#[derive(Clone, Copy, Debug)]
pub struct Tagged<V, T> {
    value: V,
    tag: PhantomData<fn(T) -> T>,
}

//  error[E0210]: type parameter `V` must be covered by another type when it appears
//  before the first local type (`Tagged<_, _>`)
impl<V, T> Mul<Tagged<V, T>> for V
where
    V: MulAssign,
{
    type Output = Tagged<V, T>;
    
    fn mul(self, mut other: Tagged<V, T>) -> Tagged<V, T> { other *= self; other }
}

impl<V, T> MulAlt<V> for Tagged<V, T>
where
    V: MulAssign,
{
    type Output = Self;

    fn mul_alt(mut self, other: V) -> Self { self.value *= other; self }
}

In the case of two implementations such Add and AddAlt both being available, depending on whether dispatching by left-hand side operand or right-hand side operand, then the implementation dispatching by left-hand side operand is used.

Reference-level Explanation

For each binary operator dispatching by left-hand side, a binary operator dispatching by right-hand side is introduced, with the suffix Alt.

For example:

trait Mul<Rhs = Self> {
    type Output;

    fn mul(self, other: Rhs) -> Self::Output;
}

trait MulAlt<Lhs> {
    type Output;

    fn mul_alt(self, other: Lhs) -> Self::Output;
}

When resolving a binary operation such as x * y:

  1. First, an implementation of Mul<Y> for X is looked up.
  2. If this lookup succeeds, then this implementation is used.
  3. Otherwise, an implentation of Mul<X> for Y is looked up.
  4. If this lookup succeeds, then this implementation is used. Do mind that it reverses arguments.
  5. Otherwise, an error is emitted.

Drawbacks

This may unreasonably (I have 0 clue) affect the resolution of binary operations. In particular, the extra flexibility in operator choice may make type inference a lot more difficult in complex scenarios. It is my hope that this drawback is strongly mitigated by the strict precedence offered to existing operators... but who knows.

A lesser drawback is the increase in API surface, and the extra documentation effort & potential for confusion for users which may result.

Rational and alternatives

There does not exist any reasonable alternative, language-wise, as far as I can see. E0210 exists for a reason.

Notably, whilst most binary operators are commutative (for integrals/floats) Sub and Div stand out as being non-commutative, and therefore rule out the idea of translating x <bin> y to Y::bin(y, x).

Prior art

None?

Would Haskell extremely flexible operator definitions fit here?

Unresolved questions

It is unclear whether this would make type-inference undecidable, or simply too costly for large arithmetic expressions.

Future possibilities

None. Once done, overloading operators is always possible.

2 Likes
2

Or maybe in very simple scenarios, too?

Already in Rust today, code like

fn main() {
    let x = 1;
    x.mul(2);
}

fails to compile because there is a fallback-rule in method resolution (this one to support not just implementations of the form LHS: Mul<RHS> but then also &LHS: Mul<RHS>, &mut LHS: Mul<RHS>, etc… to be used [following the standard chain of method resolution fallbacks], where I’m using LHS and RHS to refer to the types of the LHS and RHS expressions, respectively).

It is not clear to me how the situation would be any different for MulAlt. Hence, we would need an argument as for how the situation is different [or how they can be made different by some form of more conservative defaulting..]; or we would first need to search for, and find, solutions for making

fn main() {
    let x = 1;
    x.mul(2);
}

compile successfully; otherwise, we risk making

fn main() {
    let x = 1;
    x * 2;
}

no longer compile successfully, which seems highly unacceptable to me.

That mechanisms for approaching inference vs. fallbacks aren’t trivial is probably also indicated by how the (IMO somewhat related) issue of “defaulting” for type arguments à la fn foo<TypeArg = Default>() -> TypeArg {…} is completely unsolved/stalled for a very long time already, if I recall correctly.

1 Like
3

With MulAlt how would you write a function generic over something that supports the multiplication? The "correct" bound would be Mul OR MulAlt, but that's not expressible.

4

Would it?

I would expect that as specified -- ie, searching first for Mul implementations, and only going for MulAlt if no Mul implementations were found -- the situation would be no worse than today. If a Mul implementation exists, it's selected, and otherwise:

  • Before: it would have failed to compile.
  • After: it may succeed if a MulAlt implementation exists, and otherwise it would fail to compile still.

The maximally expressive bound would not be expressible, indeed.

I'm not sure it's so much of a problem in practice. This would mostly show up for:

  • Naked T and U parameters. If they are wrapped the function writer knows which traits exist on the wrapper.
  • Equal T and U parameters. With no indication that one is favored over the other.
  • In particular, for a "free" result type. If the result type is constrained to either parameter -- say T -- then in all likelihood T is the wrapper type, and the multiplication can be arranged to be T * U at the function writer discretion.

The case of equal naked parameters, with loose enough constraints on the result type that no distinction can be guessed at seems fairly theoretical to me.

I have no doubt it will happen, somewhere, somehow, but...

In practice, I would expect (and advise) that the writer of such a function requires Mul as the bound, and arranges the operations to be in the correct order. Most such functions would just require T: Mul<Output = T> anyway, and even folds/... can be expressed with just Mul, with the caller being given an opportunity to map the left-hand & right-hand prior to calling.

5

I always asked myself why doesn't Rust operator traits dispatch on both operands simultaneously, that is, why don't we have impl Add for (i32, i32) rather than impl Add<i32> for i32. Then the desugaring of a + b would be (a, b).add() rather than a.add(b). Is there a reason this can't work?

4 Likes
6

Tuples are foreign types and you wouldn't be able to implement AddWithNoTypeParameter for (Local, Local) ... or for any other tuple.

7

I don't think implementing add on tuples is being suggested, more that operators could be dispatched on either the left, right, or both arguments.

impl Mul for ???? {
    type Output = Matrix;

    fn mul(x: f64, m: Matrix) -> Matrix {
        ...
    }
}

or perhaps as some special kind of free function:

fn (*)(x: f64, m: Matrix) {
    ...
}
8

I was going to say “even if tuples were marked fundamental, there would still be this asymmetry” and then I noticed that, actually, nothing specifies what it would mean for a type with more than one type parameter to be fundamental.

1 Like
9

It can definitely work, see this playground link for example.

trait AddX {
    type Output;

    fn add_x(self) -> Self::Output;
}

impl AddX for (i32, i32) {
    type Output = i32;

    fn add_x(self) -> Self::Output {
        self.0 + self.1
    }
}

fn main() {
    let sum = (1, 2).add_x();
    
    println!("{sum}");
}

Surprisingly (EDIT: I was reminded this was normal for local traits) it even works with an uncovered left-hand side pattern, see this link:

impl<V, T> AddX for (V, Tagged<V, T>)
where
    V: AddAssign,
{
    type Output = Tagged<V, T>;

    fn add_x(mut self) -> Self::Output {
        self.1.value += self.0;
        
        self.1
    }
}

fn main() {
    let sum = (1, Tagged::<_, ()>::new(2)).add_x();
    
    println!("{sum:?}");
}

So it may have been a better solution, in hindsight... or perhaps it just exposes a weirdness of tuples that ought to be fixed.

10

your trait is local, so it allows any impl

11

Ah! That would explain it indeed.

Well, I can't show off an example with a different crate with the playground...

12

There’s a trick you can use to get two crates on the playground: define a doc-test and run it.

/// ```
/// impl playground::AddX for (i32, i32) {
///     type Output = i32;
/// 
///     fn add_x(self) -> Self::Output {
///         self.0 + self.1
///     }
/// }
/// 
/// let sum = (1, 2).add_x();
/// println!("{sum}");
/// ```
pub trait AddX {
    type Output;

    fn add_x(self) -> Self::Output;
}

This produces the error it should, “error[E0117]: only traits defined in the current crate can be implemented for arbitrary types”.

1 Like
13

Such a type already exists: Box accepts an (unstable) allocator parameter.

1 Like
14

But is there any documentation of how that behaves, or even that acknowledges the case exists? I stand by “nothing specifies”, if not “would”.

1 Like
15

The #[fundamental] attribute is an unstable implementation detail, so no it is not documented. However, the behavior of Box<T> is documented at Glossary - The Rust Reference.