Why does this result of a binary operator need an

Question

This is related to my earlier question on making a modular exponentiation method generic. I've now arrived at the following code:

fn powm<T>(fbase: &T, exponent: &T, modulus: &T) -> T
where
    T: Mul<T, Output = T>
        + From<u8>
        + PartialEq<T>
        + Rem<T, Output = T>
        + Copy
        + for<'a> Rem<&'a T, Output = T>
        + Clone
        + PartialOrd<T>
        + ShrAssign<T>,
    for<'a> &'a T: PartialEq<T> + Rem<&'a T, Output = T>,
{
    if modulus == T::from(1) {
        T::from(0)
    } else {
        let mut result = T::from(1);
        let mut base = fbase % modulus;
        let mut exp = exponent.clone();
        while exp > T::from(0) {
            if exp % T::from(2) == T::from(1) {
                result = (result * base) % modulus;
            }
            exp >>= T::from(1);
            base = (base * base) % modulus;
        }
        result
    }
}

It is my understanding that by defining the trait bound where for<'a> &'a T: Rem<&'a T, Output=T> that it is understood that I can use the modulo operator % on two operands of type &'a T, and the result will be of type T. However, I get the following error:

error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
  --> src/main.rs:20:30
   |
20 |         let mut base = fbase % modulus;
   |                              ^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #3 defined on the function body at 3:1...
  --> src/main.rs:3:1
   |
3  | / fn powm<T>(fbase: &T, exponent: &T, modulus: &T) -> T
4  | | where
5  | |     T: Mul<T, Output = T>
6  | |         + From<u8>
...  |
30 | |     }
31 | | }
   | |_^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:20:32
   |
20 |         let mut base = fbase % modulus;
   |                                ^^^^^^^
note: but, the lifetime must be valid for the anonymous lifetime #1 defined on the function body at 3:1...
  --> src/main.rs:3:1
   |
3  | / fn powm<T>(fbase: &T, exponent: &T, modulus: &T) -> T
4  | | where
5  | |     T: Mul<T, Output = T>
6  | |         + From<u8>
...  |
30 | |     }
31 | | }
   | |_^
note: ...so that types are compatible (expected std::ops::Rem, found std::ops::Rem<&T>)
  --> src/main.rs:20:30
   |
20 |         let mut base = fbase % modulus;
   |                              ^

The code does work if I replace the line in question by

let mut base = fbase.clone() % modulus;

I don't see why I would need to clone in the first place if I can use the modulo operator already to return a "fresh" element of type T. Do I need to modify my trait bounds instead? Why does this go wrong?

Answer 1

When programming, it's very useful to learn how to create a Minimal, Complete, and Verifiable example (MCVE). This allows you to ignore irrelevant details and focus on the core of the problem.

As one example, your entire blob of code can be reduced down to:

use std::ops::Rem;

fn powm<T>(fbase: &T, modulus: &T)
where
    for<'a> &'a T: Rem<&'a T, Output = T>,
{
    fbase % modulus;
}

fn main() {}

Once you have a MCVE, you can make permutations to it to explore. For example, we can remove the lifetime elision:

fn powm<'a, 'b, T>(fbase: &'a T, modulus: &'b T)
where
    for<'x> &'x T: Rem<&'x T, Output = T>,
{
    fbase % modulus;
}

Now we start to see something: what is the relation between all three lifetimes? Well, there isn't one, really. What happens if we make one?

• If we say that the input references can be unified to the same lifetime, it works:

  fn powm<'a, T>(fbase: &'a T, modulus: &'a T)
  

• If we say that 'b outlives 'a, it works:

  fn powm<'a, 'b: 'a, T>(fbase: &'a T, modulus: &'b T)
  

• If we say that we can have two different lifetimes in the operator, it works:

  for<'x, 'y> &'x T: Rem<&'y T, Output = T>,
  

What about if we poke at the call site?

• If we directly call the Rem::rem method, it works:

  Rem::rem(fbase, modulus);
  

• If we dereference and re-reference, it works:

  &*fbase % &*modulus;
  

I don't know exactly why the original doesn't work — conceptually both the input references should be able to be unified to one lifetime. It's possible that there's a piece of inference that either cannot or isn't happening, but I'm not aware of it.

Some further discussion with a Rust compiler developer led to an issue as it doesn't quite seem right. This issue has now been resolved and should theoretically be available in Rust 1.23.