Expected reference, found struct

Question

I'm trying to learn Rust by translating C++ code from the "Elements of Programming" book by Stepanov and McJones. Here's a simple code snippet:

extern crate num_bigint;

use num_bigint::BigInt;

pub fn fibonacci_matrix_multiply(x: (&BigInt, &BigInt), y: (&BigInt, &BigInt)) -> (BigInt, BigInt) {
    (x.0 * (y.1 + y.0) + x.1 * y.0, x.0 * y.0 + x.1 * y.1)
}

pub fn power_accumulate_positive(
    mut r: (&BigInt, &BigInt),
    mut a: (&BigInt, &BigInt),
    mut n: i32,
) -> (BigInt, BigInt) {
    loop {
        if n & 1 == 1 {
            r = fibonacci_matrix_multiply(r, a);
            if n == 1 {
                return r;
            }
        }
        a = fibonacci_matrix_multiply(a, a);
        n = n / 2;
    }
}

fn main() {}

Here's the error messages:

error[E0308]: mismatched types
  --> src/main.rs:16:17
   |
16 |             r = fibonacci_matrix_multiply(r, a);
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected reference, found struct `num_bigint::BigInt`
   |
   = note: expected type `(&num_bigint::BigInt, &num_bigint::BigInt)`
              found type `(num_bigint::BigInt, num_bigint::BigInt)`

error[E0308]: mismatched types
  --> src/main.rs:18:24
   |
18 |                 return r;
   |                        ^ expected struct `num_bigint::BigInt`, found reference
   |
   = note: expected type `(num_bigint::BigInt, num_bigint::BigInt)`
              found type `(&num_bigint::BigInt, &num_bigint::BigInt)`

error[E0308]: mismatched types
  --> src/main.rs:21:13
   |
21 |         a = fibonacci_matrix_multiply(a, a);
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected reference, found struct `num_bigint::BigInt`
   |
   = note: expected type `(&num_bigint::BigInt, &num_bigint::BigInt)`
              found type `(num_bigint::BigInt, num_bigint::BigInt)`

I understand that I'm returning a tuple of structs and trying to assign it to a tuple of references, but I don't know how to solve the problem.

TL;DR — references and non-references are different types, just like in C++. You want to store something that is either a reference or an owned value, that calls for a `Cow`. The [direct (and ugly) solution with `Cow`](https://play.integer32.com/?gist=c5cd2d2c92bd0a6d6c1a7a3173e969d4&version=stable). — Shepmaster, Aug 29 '17 at 17:26

score 4 · Accepted Answer · edited Aug 29 '17 at 17:17

Is there a reason you can't take the BigInts by value instead of by reference? This would remove all the borrow checker errors. Unless it's a clear and measured bottleneck to clone the BigInts, passing by reference won't be much faster and it's less ergonomic.

Here's a working solution that doesn't use references (and instead clones the values)

extern crate num_bigint;

use num_bigint::BigInt;

pub fn fibonacci_matrix_multiply(x: (BigInt, BigInt), y: (BigInt, BigInt)) -> (BigInt, BigInt) {
    (&x.0 * (&y.1 + &y.0) + &x.1 * &y.0, x.0 * y.0 + x.1 * y.1)
}

pub fn power_accumulate_positive(
    mut r: (BigInt, BigInt),
    mut a: (BigInt, BigInt),
    mut n: i32,
) -> (BigInt, BigInt) {
    loop {
        if n & 1 == 1 {
            r = fibonacci_matrix_multiply(r, a.clone());
            if n == 1 {
                return r;
            }
        }
        a = fibonacci_matrix_multiply(a.clone(), a);
        n = n / 2;
    }
}

Expected reference, found struct

1 Answers1