How do I implement the Add trait for a reference to a struct?

You need to implement Add on &Vector rather than on Vector.

impl<'a, 'b> Add<&'b Vector> for &'a Vector {
    type Output = Vector;

    fn add(self, other: &'b Vector) -> Vector {
        Vector {
            x: self.x + other.x,
            y: self.y + other.y,
        }
    }
}

In its definition, Add::add always takes self by value. But references are types like any other¹, so they can implement traits too. When a trait is implemented on a reference type, the type of self is a reference; the reference is passed by value. Normally, passing by value in Rust implies transferring ownership, but when references are passed by value, they're simply copied (or reborrowed/moved if it's a mutable reference), and that doesn't transfer ownership of the referent (because a reference doesn't own its referent in the first place). Considering all this, it makes sense for Add::add (and many other operators) to take self by value: if you need to take ownership of the operands, you can implement Add on structs/enums directly, and if you don't, you can implement Add on references.

Here, self is of type &'a Vector, because that's the type we're implementing Add on.

Note that I also specified the RHS type parameter with a different lifetime to emphasize the fact that the lifetimes of the two input parameters are unrelated.

¹ Actually, reference types are special in that you can implement traits for references to types defined in your crate (i.e. if you're allowed to implement a trait for T, then you're also allowed to implement it for &T). &mut T and Box<T> have the same behavior, but that's not true in general for U<T> where U is not defined in the same crate.

If you want to support all scenarios, you must support all the combinations:

• &T op U
• T op &U
• &T op &U
• T op U

In rust proper, this was done through an internal macro.

Luckily, there is a rust crate, impl_ops, that also offers a macro to write that boilerplate for us: the crate offers the impl_op_ex! macro, which generates all the combinations.

Here is their sample:

#[macro_use] extern crate impl_ops;
use std::ops;

impl_op_ex!(+ |a: &DonkeyKong, b: &DonkeyKong| -> i32 { a.bananas + b.bananas });

fn main() {
    let total_bananas = &DonkeyKong::new(2) + &DonkeyKong::new(4);
    assert_eq!(6, total_bananas);
    let total_bananas = &DonkeyKong::new(2) + DonkeyKong::new(4);
    assert_eq!(6, total_bananas);
    let total_bananas = DonkeyKong::new(2) + &DonkeyKong::new(4);
    assert_eq!(6, total_bananas);
    let total_bananas = DonkeyKong::new(2) + DonkeyKong::new(4);
    assert_eq!(6, total_bananas);
}

Even better, they have a impl_op_ex_commutative! that'll also generate the operators with the parameters reversed if your operator happens to be commutative.