Lifetimes for type constraint where one reference is local

help
1

If I writing a generic function, I may need to add a type constraint saying that a particular implementation exists; for example, that Mul is implemented for two references of the type. This is probably a very dumb question, but how do I write the lifetimes for references in the type constraint when one of them is just a local temporary reference?

use std::ops::Mul;
#[derive(Clone)]
struct DenseMatrix{
    n_rows: usize,
    n_columns: usize,
    elements: Vec<f64>
}

impl<'a> Mul<&'a DenseMatrix> for &'a DenseMatrix {
    type Output = DenseMatrix;
    fn mul(self, rhs: &'a DenseMatrix) -> Self::Output { unimplemented!() }
}

fn square<'a, 'b>(x: &'a DenseMatrix) -> DenseMatrix
    where &'b DenseMatrix: Mul<&'a DenseMatrix, Output=DenseMatrix>
{
    &(*x).clone() * x
}

gives the error:

error: borrowed value does not live long enough
  --> src\main.rs:38:6
   |
38 |     &(*x).clone() * x
   |      ^^^^^^^^^^^^ does not live long enough
39 | }
   | - temporary value only lives until here
   |
note: borrowed value must be valid for the lifetime 'b as defined on the body at 37:0...
  --> src\main.rs:37:1
   |
37 |   {
   |  _^ starting here...
38 | |     &(*x).clone() * x
39 | | }
   | |_^ ...ending here
1 Like
2

This is probably a very dumb answer, but... what is it that you're trying to do? In your example, you don't need any constraints, explicit lifetimes, not even that clone() call:

fn square(x: &DenseMatrix) -> DenseMatrix { x * x }

works perfectly.

1 Like
3

You're making it more complicated than necessary :slight_smile:

Your square fn doesn't need any lifetime annotations (let lifetime elision do its thing) and you don't need the clone:

fn square (x: &DenseMatrix) -> DenseMatrix {
    x * x
}
1 Like
4

That being said, in a more complicated example you'd need Higher-Rank Trait Bounds (HRTBs):

fn square<'a>(x: &'a DenseMatrix) -> DenseMatrix
    where for<'b> &'b DenseMatrix: Mul<&'a DenseMatrix, Output=DenseMatrix>
{
    &(*x).clone() * x
}

The difference between

fn foo<'a>() where condition

and

fn foo() where for<'a> condition

is that in the latter the condition must hold for all 'a -- that is, for those that the implementation of foo() might need; whereas in the former it only holds for the 'a the caller supplies you with (and it's the caller who makes sure it holds).

1 Like
5

Should also mention that I think the "right" thing to do in this example is to change the Mul impl to be (note the independent lifetime parameters):

impl<'a, 'b> Mul<&'b DenseMatrix> for &'a DenseMatrix {
    type Output = DenseMatrix;
    fn mul(self, rhs: &'b DenseMatrix) -> Self::Output { unimplemented!() }
}

This allows both references to have different lifetimes, and makes the following work:

fn square(x: &DenseMatrix) -> DenseMatrix {
    let d = DenseMatrix {...};
    x * &d;
}
1 Like
6

Whoops, the danger of simplifying before posting is that one can oversimplify the problem. There was a base trait Matrix in my original problem, which is what actually drives the need for the type constraint. And the clone is needed for a transpose operation, which I also elided.

Yep, that was it. I didn't get to that chapter in the book yet. Is there any reason to not use where for<'b, 'c> &'b T: Mul<&'c T, Output=T>, which also works and lets me write the multiplication with the cloned object on either the right or left?

This makes sense and it works when I do it, so I'll make that my standard. But it seems to work either way for me. Do you have an example that doesn't work when Mul has only one lifetime parameter?

For future reference, this is the full code that works:

use std::ops::Mul;

trait Matrix: Clone {
    fn transpose(self) -> Self;
}

#[derive(Clone)]
struct DenseMatrix {
    n_rows: usize,
    n_columns: usize,
    elements: Vec<f64>
}

impl Matrix for DenseMatrix {
    fn transpose(self) -> Self { unimplemented!() }
}

impl<'a, 'b> Mul<&'b DenseMatrix> for &'a DenseMatrix {
    type Output = DenseMatrix;
    fn mul(self, rhs: &'b DenseMatrix) -> Self::Output { unimplemented!() }
}

fn squareify<'a, T: Matrix>(x: &'a T) -> T
    where for<'b> &'b T: Mul<&'a T, Output=T>
{
    &(*x).clone().transpose() * x
}
1 Like
7

Yeah, it was the example I gave in that post:

fn square(x: &DenseMatrix) -> DenseMatrix {
    let d = DenseMatrix {...};
    x * &d;
}

It's not really "square" anymore, but I was too lazy to change the name :slight_smile:.

1 Like
8

I think in this case you need it because you're dealing with a generic type parameter constrained to be a trait, and compiler gets nervous about lifetimes. Using HRTB allows the squareify function to pick the appropriate lifetime for the temporary, rather than the caller providing it (via lifetime parameters on the function), which it can't really.

9

Interesting. I had tested your example, but only in the generic context, which does work. Do the extra lifetime parameters give the compiler some flexibility in finding a common lifetime that both references can satisfy?

// Works
fn square_generic<'a, T: Matrix>(x: &'a T) -> T
    where for<'b> &'a T: Mul<&'b T, Output = T>
{
    let d = (*x).clone();
    x * &d
}

// Errors
fn square_concrete<'a>(x: &'a DenseMatrix) -> DenseMatrix {
    let d = (*x).clone();
    x * &d
}
1 Like
10

Yeah, so both of these cases work if you have two independent lifetime parameters in the Mul impl. But if you only have 1, then square_concrete doesn't compile, as you say. The reason is because the Mul impl with a single lifetime parameter requires that the rhs has the same lifetime as the left-hand side. Since you have a temporary here, that doesn't work because the temp's lifetime is shorter - the compiler error message indicates that via borrowed value must be valid for the lifetime 'a as defined on the body.

In the square_generic case, you're adding an additional constraint, via HRTB, that effectively says "a T reference, with a generic lifetime parameter 'a that the caller picks, can be multiplied by another T reference for every lifetime 'b". Crucially, the HRTB constraint allows the callee, square_generic in this case, to pick the appropriate lifetime for the temporary, and decouples this from the caller (who only specifies the 'a lifetime of the x parameter).

I'm probably doing HRTB some injustice in my explanation attempt above. Here's a better and more thorough explanation of HRTB: rust - How does for<> syntax differ from a regular lifetime bound? - Stack Overflow

1 Like
11

That was actually in the Rustonomicon, not the usual book. I don't know why the book doesn't mention HRTBs (neither in the first nor in the second editions -- or maybe it does, but I can't find it).

Not really.

Strictly speaking, this is the place where you ask yourself what do you need for the implementation and what flexibility you are willing to provide (to the caller). If you need to use the cloned object on the left and right, then you should require that that property holds for all 'b, 'c. If you don't, you can use for any given 'a for all 'b. The latter gives a little bit more flexibility to the caller, because it theoretically enables the caller to call your function in more cases. That is all to say, you should only require what you really need.

But in practice the type will either implement &obj * &obj or not, and particular lifetimes are very unlikely to make any difference. So, it's fine to require stuff for all 'b, 'c.

And then again, as @vitalyd mentioned, the right way is to move all the constraints to the impl. Notice how they become for any given 'a, 'b constraints -- because this way the square function is the caller, and square requiring an impl exists for all 'a, 'b matches the impl existing for any given 'a, 'b.

Lastly, just in case you don't already know, there already are good and high-performance matrix and linear algebra implementations in Rust, so you don't have to write your own if you don't want to. See http://nalgebra.org and ndarray - Rust

1 Like
12

I've read the whole regular book. I think the Rustonomicon undersells itself by starting off saying it is for unsafe Rust. The Rust book leaves out a lot of safe Rust that is well covered in Rustonomicon.

Most of my questions come from trying to understand these and other existing linear algebra libraries--specifically, why were they designed this way; what benefits and limitations come associated with these designs. This has also been a good way to learn Rust, I think.

1 Like
13

Here's why: Go into detail about Higher-Ranked Trait Bounds (HRTB) in ch 19 · Issue #698 · rust-lang/book · GitHub :slight_smile:

1 Like