Return a borrowed value that references fields of &self


#1

Let’s say I have a Matrix trait and two concrete implementations—a RowMajorMatrix implementation and ColumnMajorMatrix implementation. Each struct stores the dimensions and a Vec of elements. In this design, implementing matrix transpose on an owned matrix is pretty straightforward, simply move the elements from the row major struct into a new column major struct and vice versa. The code looks like this:

trait Matrix<E> {
    type Transpose: Matrix<E>;
    fn height(&self) -> usize;
    fn width(&self) -> usize;
    fn t(self) -> Self::Transpose;
}

struct RowMajorMatrix<E> {
    n: usize,
    m: usize,
    elements: Vec<E>
}

impl<E> Matrix<E> for RowMajorMatrix<E> {
    type Transpose = ColumnMajorMatrix<E>;
    fn height(&self) -> usize { self.n }
    fn width(&self) -> usize { self.m }
    fn t(self) -> Self::Transpose {
        ColumnMajorMatrix { n: self.m, m: self.n, elements: self.elements }
    }
}

struct ColumnMajorMatrix<E> {
    n: usize,
    m: usize,
    elements: Vec<E>
}

impl<E> Matrix<E> for ColumnMajorMatrix<E> {
    type Transpose = RowMajorMatrix<E>;
    fn height(&self) -> usize { self.n }
    fn width(&self) -> usize { self.m }
    fn t(self) -> Self::Transpose {
        RowMajorMatrix { n: self.m, m: self.n, elements: self.elements }
    }
}

fn main() {
    let rowmat = RowMajorMatrix { n: 2, m: 3, elements: vec![1, 2, 3, 4, 5, 6] };
    let colmat = rowmat.t();
}

There should also be version of transpose for a borrowed matrix. Let’s call this method t_borrow, and I’ll figure out how to do the overloading later. If the receiver is &self, then I would like transpose to return &Self::Transpose, which doesn’t work for reasons that make sense to me, but it is not clear how to accomplish what I want.

trait Matrix<E> {
    ...
    fn t_borrow(&self) -> &Self::Transpose;
}

impl<E> Matrix<E> for RowMajorMatrix<E> {
    ...
    // Doesn't work obviously, but hopefully shows the goal
    fn t_borrow(&self) -> &Self::Transpose {
        &ColumnMajorMatrix { n: self.m, m: self.n, elements: self.elements }
    }
}

The returned value needs to have a shorter lifetime than &self and needs to never actually free its elements, but I don’t know how to say that in Rust.


#2

The expression ColumnMajorMatrix{…} creates a temporary, stack-allocated object that will cease to exist before the end of this function, and by using references, you’re trying to return a pointer to it.

That’s equivalent of a typical crash in C:

struct ColumnMajorMatrix t_borrow() {
    struct ColumnMajorMatrix tmp = {…};
    return &tmp;
}

In general, you can never return a reference to anything new. Returning references from functions is only for offering a view of existing data living in self (or some other argument).

So here if you want to create a new ColumnMajorMatrix, then you should pass ownership of that object.

fn transposed(&self) -> Self::Transpose {
     ColumnMajorMatrix {…}
}

The next error you’re going to run into is Rust complaining that you’re moving elements out of self. You’ll have to decide whether ColumnMajorMatrix shares elements with the object it was created from (if so, use &[E] for the type of elements in ColumnMajorMatrix), or whether it holds its own copy of the elements (in that case you’ll need self.elements.clone()).


#3

You can create a type which is itself concrete, but contains references, something like:

struct ColumnMajorMatrixRef<'a, E> {
    n: usize,
    m: usize,
    elements: &'a [E],
}

Then a function can return that from &self as a properly borrowed value.

However, there’s not yet any way to represent that in an associated type like Transform. Once we have associated type constructors, you’ll be able to write the trait like:

trait Matrix<E> {
    type Transpose: Matrix<E>;
    type TransposeRef<'a>: Matrix<E>;
    fn height(&self) -> usize;
    fn width(&self) -> usize;
    fn t(self) -> Self::Transpose;
    fn t_borrow(&self) -> Self::TransposeRef;
    //^same as: fn t_borrow<'a>(&'a self) -> Self::TransposeRef<'a>;
}

#4

Thank you, that’s a good solution. I have a lot of impls for the binary math (Add, Mul, etc.), like this:

impl<'a, E> Mul<&'a RowMajorMatrix<E>> for &'a RowMajorMatrix<E>
    where E: Mul<E, Output=E>
{
    type Output = RowMajorMatrix<E>;
    fn mul(self, rhs: &'a RowMajorMatrix<E>) -> Self::Output {
        ...
    }
}

When creating these new types like ColumnMajorMatrixRef, is there a way to avoid the quadratic increase in the number of impls for binary operations?


#5

I have been experimenting with Deref coercions to get a ColumnMajorMatrixRef to convert to a &ColumnMajorMatrix so that I don’t have to define all the possible binary operations on the Ref objects, like

impl<'a, E> Mul<ColumnMajorMatrixRef<E>> for &'a RowMajorMatrix<E> { ... }
impl<'a, E> Mul<ColumnMajorMatrix<E>> for &'a RowMajorMatrixRef<E> { ... }
...

Am I correct that this is not possible?


#6

I don’t think Deref can help with that.

A different idea is to use conditional ownership in the first place with Cow<[E]> instead of Vec<E>. But you’d have to deal with a lifetime everywhere for this, and I haven’t played with it to see if there are other problems.


#7

For lots of impls that look the same you can normally do something with macros.


#8

I am making another attempt at returning a reference. This is may not be a good design, but I would like to understand why if it is not. The return value from t_borrow(&self) needs to be a pointer of some type that cannot be accessed after the lifetime of &self and does not free its contents when it goes out of scope. I couldn’t find anywhere where this existed already, but I was able to create one which I’ll call LifeBox:

use std::ops::Deref;
use std::marker::PhantomData;

struct LifeBox<'a, T: 'a> {
    object: Box<T>,
    phantom: PhantomData<&'a T>
}

impl<'a, T: 'a> LifeBox<'a, T> {
    fn new(object: T) -> LifeBox<'a, T> {
        LifeBox { object: Box::new(object), phantom: PhantomData }
    }
}

# So that the contents aren't dropped because they are actually borrowed
impl<'a, T: 'a> Drop for LifeBox<'a, T> {
    fn drop(&mut self) {}
}

# This is so Deref coercions work
impl<'a, T: 'a> Deref for LifeBox<'a, T> {
    type Target = T;
    fn deref(&self) -> &T {
        &self.object
    }
}

Obviously, it is only wise to construct a LifeBox using unsafe because object should be doing some unsafe sharing of data with another object. It’s the unsafe sharing that I can’t figure out.

trait Matrix<E> {
    type Transpose: Matrix<E>;
    fn t_borrow<'a>(&'a self) -> LifeBox<'a, Self::Transpose>;
}

struct RowMajorMatrix<E, C> where C: Deref<Target=[E]> + Clone {
    n: usize,
    m: usize,
    elements: C
}

impl<E, C: Deref<Target=[E]> + Clone> Matrix<E> for RowMajorMatrix<E, C> {
    type Transpose = ColumnMajorMatrix<E, C>;
    fn t_borrow<'a>(&'a self) -> LifeBox<'a, Self::Transpose> {
        let elements = &self.elements as *const C;
        unsafe {
            let transpose = ColumnMajorMatrix::<E, C> { n: self.m, m: self.n, elements: *elements };
            return LifeBox::new(transpose)
        }
    }
}

struct ColumnMajorMatrix<E, C> where C: Deref<Target=[E]> + Clone {
    n: usize,
    m: usize,
    elements: C
}

impl<E, C: Deref<Target=[E]> + Clone> Matrix<E> for ColumnMajorMatrix<E, C> {
    type Transpose = RowMajorMatrix<E, C>;
    fn t_borrow<'a>(&'a self) -> LifeBox<'a, Self::Transpose> {
        let elements = &self.elements as *const C;
        unsafe {
            let transpose = RowMajorMatrix { n: self.m, m: self.n, elements: *elements };
            return LifeBox::new(transpose)
        }
    }
}

This code gives me an error:

error[E0507]: cannot move out of dereference of raw pointer
  --> src\main.rs:54:89
   |
54 |             let transpose = ColumnMajorMatrix::<E, C> { n: self.m, m: self.n, elements: *elements };
   |                                                                                         ^^^^^^^^^ cannot move out of dereference of raw pointer

I didn’t understand this error after googling it. What is the point of a raw pointer if not to make unsafe shallow copies of the target?


#9

First of all, adding an empty drop implementation has no effect. Drop methods of all fields will still be called. If you want to prevent that, you can make the field an Option and set it to None in drop method. That being said, I’m not sure how Box can help in your task, as Box represent owned content, and you need borrowed content. If you want unsafe sharing, you can just pass raw pointers around, but it’s easy to do it wrong. Unsafe is the last thing you should use here.

In fact, a simple reference &T has all these properties. If you want something more complex, you can make a thin wrapped over a reference:

struct X(i32);
impl X {
    fn custom_borrow<'a>(&'a self) -> XBorrow<'a> {
        XBorrow(&self)
    }
}
struct XBorrow<'a>(&'a X);

fn main() {
    let x = X(1);
    let b = x.custom_borrow();
}

I think you really should use Cow as suggested earlier, because it will allow you to use just two types (RowMajorMatrix and ColumnMajorMatrix) and each of them can be either borrowed or owned. If you don’t use Cow, you will need 4 different types and implementation of the trait for each of them. Cow is a bit tricky but I managed to make a working example:

use std::borrow::{Borrow, Cow};

struct RowMajorMatrix<'a, E: Clone + 'a> {
    n: usize,
    m: usize,
    elements: Cow<'a, [E]>,
}

struct ColumnMajorMatrix<'a, E: Clone + 'a> {
    n: usize,
    m: usize,
    elements: Cow<'a, [E]>,
}


trait Matrix<'a, E> {
    type Transpose: Matrix<'a, E>;
    fn transpose(&'a self) -> Self::Transpose;
}


impl<'a, E: Clone + 'a> Matrix<'a, E> for RowMajorMatrix<'a, E> {
    type Transpose = ColumnMajorMatrix<'a, E>;
    fn transpose(&'a self) -> ColumnMajorMatrix<'a, E> {
        ColumnMajorMatrix {
            n: self.n, 
            m: self.m,
            elements: Cow::Borrowed(self.elements.borrow()),
        }
    }
}

impl<'a, E: Clone + 'a> Matrix<'a, E> for ColumnMajorMatrix<'a, E> {
    type Transpose = RowMajorMatrix<'a, E>;
    fn transpose(&'a self) -> RowMajorMatrix<'a, E> {
        RowMajorMatrix {
            n: self.n, 
            m: self.m,
            elements: Cow::Borrowed(self.elements.borrow()),
        }
    }
}

fn main() {
    let elements: Cow<[i32]> = Cow::Owned(vec![1, 2, 3, 4, 5, 6]);
    let matrix: RowMajorMatrix<i32> = 
        RowMajorMatrix { n: 3, m: 2, elements: elements };
}   

However it’s still possible to write it without unsafe and without Cow if you really want to.

Raw pointer is basically just a number. It’s not guaranteed to point at any valid data. And when it does point at data, there are no aliasing guarantees. If you have a raw pointer, you can dereference it anywhere anytime, and if it happens to point at data, you’re in luck. But you shouldn’t construct and store safe wrappers (&T, Box<T>, etc.) from it because it violates aliasing and ownership guarantees. This particular error (“cannot move out of dereference of raw pointer”) tells you that you can’t use move semantics on raw pointers at all. When you perform a move, Rust needs to make sure the object was properly removed from its original location (e.g. set a boolean flag indicating that drop method should not be called if this was a local variable). With raw pointers, it’s simply not possible, and move operations on dereferenced data don’t make sense. You can only copy the pointer itself or perform a low-level copy of the memory region if you know its size.