Consider making operators transparently work on borrows wherever possible

[isislovecruft]

Hello!

I've been working on a pure-Rust elliptic curve cryptography library with @hdevalence, called curve25519-dalek. We've implemented operators Add, Sub, Mul, Neg, for the field and, similarly, Add and Sub for elliptic curve points. At first, we implemented the operators on the types T. (T in this case is some representation of a point, comprised internally four FieldElements). But that was obviously sloooooow, because now everytime you want to add two points together, you're copying all those internal FieldElements around (and each FieldElement is itself, internally, basically an [i32; 10]). With that implementation, we were copying 160 bytes around everytime we did any point operation. We then switched to implementing them for &T to avoid copies, e.g.:

impl<'a,'b> Add<&'b PreComputedPoint> for &'a ExtendedPoint {
    type Output = CompletedPoint;

    fn add(self, other: &'b PreComputedPoint) -> CompletedPoint {
        let Y_plus_X  = &self.Y + &self.X;
        let Y_minus_X = &self.Y - &self.X;
        let PP        = &Y_plus_X  * &other.y_plus_x;
        let MM        = &Y_minus_X * &other.y_minus_x;
        let Txy2d     = &self.T * &other.xy2d;
        let Z2        = &self.Z + &self.Z;

        CompletedPoint{
            X: &PP - &MM,
            Y: &PP + &MM,
            Z: &Z2 + &Txy2d,
            T: &Z2 - &Txy2d
        }
    }
}

Voilá, fast as hell! No more copies. And it's still quite readable. However, now, as I'm implementing the Elligator2 mapping (a way encode a point into a uniformly random string), I'm started to see the ampersands pile up pretty quickly:

pub fn elligator2(X: &FieldElement) -> UniformRepresentative {
    let one:    FieldElement = FieldElement::one();
    let n:      FieldElement = FieldElement([2, 0, 0, 0, 0, 0, 0, 0, 0, 0]); // n = 2
    let nrr:    FieldElement = &n * &X.square();                             // nr²
    let mut u:  FieldElement = &(-(&A)) * &(&one + &nrr).invert();           // u = -A/(1 + nr²)
    let w:      FieldElement = &u * &(&(&u.square() + &(&A * &u)) + &one);   // w = u(u² + Au + 1)
    let uprime: FieldElement = &(-(&A)) - &u;
    // If u and u' are integers modulo p such that u' = -A - u and u/u' = nr²
    // for any r and fixed nonsquare n, then the Montgomery curve equation
    // v = u(u² + Au + 1) has a solution for u = u or u = u', or both.
    //
    // From the above lemma, it follows that u = -A/(1 + nr²) and
    // u' = -Anr²/(1 + nr²). Thus, given r, we can easily calculate u and u' and
    // use the Legendre symbol to choose whichever value gives a square w.
    let nonsquare: u8 = legendre_is_nonsquare(&w);

    // If w is non-square, then we recompute u to be u' = -A - u:
    u.conditional_assign(&uprime, nonsquare);

    UniformRepresentative(u)
}

let mut u: FieldElement = &(-(&A)) * &(&one + &nrr).invert();

Wat. I just wanted u = -A/(1 + nr²)!

let w: FieldElement = &u * &(&(&u.square() + &(&A * &u)) + &one);

Wat the wat. I wanted w = u(u² + Au + 1).

It seems @aturon and others have discussed potential solutions to this issue on Reddit, namely providing some "auto-ref" functionality, similar to &self.

Is this a change Rust would like to see? Are there more concerns which might arise if this were implemented? I really want to have the "my code is pretty" cake and eat the "my code is fast" cake too. :)

[burdges]

I find it helps readability if I borrow everything as early as possible. I write roughly this sometimes :

let mut r = &mut [0u8; 32+12];
let sha = Sha3::shake_256();
sha.input(foo);
sha.input(bar);
sha.result(r);
sha.reset();
let (chacha_nonce,chacha_key) = array_refs![r,12,32];
...

Your constants could be borrows :

const A: &'static FieldElement = &FieldElement([
    486662, 0, 0, 0, 0, 0, 0, 0, 0, 0, ]);

You can move some &s to the first three let statements :

pub fn elligator2(X: &FieldElement) -> UniformRepresentative {
    let one:    &FieldElement = &FieldElement::one();
    let n:      &FieldElement = &FieldElement([2, 0, 0, 0, 0, 0, 0, 0, 0, 0]); // n = 2
    let nrr:    &FieldElement = &( n * &X.square() );                             // nr²
    let mut u:  FieldElement = &(-A) * &(one + nrr).invert();           // u = -A/(1 + nr²)
    let w:      FieldElement = &u * &(&(&u.square() + &(A * &u)) + one);   // w = u(u² + Au + 1)
    let uprime: FieldElement = &(-A) - &u;
    ...

All that costs you some consistency though.

In general, we should expect APIs to give users the choice locally with the Borrow trait. And the BorrowMut trait for assignment forms.

impl<EP,PCP> Add<PCP> for EP where 
  where EP: Borrow<ExtendedPoint>,
        PCP: Borrow<PreComputedPoint>
 {
    type Output = CompletedPoint;

    fn add(self, other: PCP) -> CompletedPoint {
        let s = self.borrow();
        let o = other.borrow();
        // .. replace self by s and other by o everywhere ..
    }
}

Yet, this only hides performance problems by permitting pass by value. I could imagine deactivating impl Borrow<T> for T as a performance audit though, maybe by temporarily using some broken_borrow crate.

In fact, I wonder if Borrow/BorrowMut bounds, along with maybe AsRef/AsMut and Deref/DerefMut bounds, could be special cased to prefer borrowing, as they demonstrate that you only want a reference? There are cases like tail calls where you still want pass-by-value though.

[burdges]

It appears one can mostly address this with #[inline(always)] by-value wrappers invoke a by-reference method.

Aside from numerical operators though, the builder pattern needs fast by value operation too. It's possible #[inline(always)] would help there too, but maybe rustc should try harder to avoid copies when passing and returning a common owned value, ala f(mut owned: T) -> T.