rustborrow-checkerownership

Can I create an immutable vector from another immutable vector in Rust without copying?


I'm new to Rust and write a library for linear algebra on binary matrices. I have a sparse matrix struct storing a matrix in column major format (CscMatrix). The CscMatrix stores the positions of ones in each column, each column takes up a contiguous segment in the 'ones' vector. The index of the first entry for the i-th column is stored at start[i]. Now I want to be able to take the transpose of such a matrix and receive the result in row major format (ans instance of CsrMatrix, which does the exact same thing as CscMatrix, just with each row taking up a contiguous segment in 'ones'). To do this, of course, no actual computation needs to be done, the data stored in the CscMatrix just needs to be reinterpreted as a CsrMatrix.

pub struct CscMatrix {
    start: Vec<u32>, // start index of each column in 'ones'
    ones: Vec<u32>,  // positions of ones
}

pub struct CsrMatrix {
    start: Vec<u32>, // start index of each row in 'ones'
    ones: Vec<u32>,  // positions of ones
}

impl CscMatrix {
    pub fn transpose(&self) -> CsrMatrix {
        return CsrMatrix {
            start: self.start,
            ones: self.ones,
        };
    }
}

The given CscMatrix is always immutable and the returned CsrMatrix will not be modified.

My two questions are now:

  • Can I initialize the 'start' and 'ones' vectors of the CsrMatrix with the exact same data as in the given CscMatrix without having to copy it? Intuitively, it should be possible, since I do not want to modify the returned CsrMatrix and the given CscMatrix is immutable. So it's possible to just copy the pointers of the memory locations 'start' and 'ones' point to.
  • Can I make the transpose function return an immutable reference to the CsrMatrix object created?

Solution

  • Some object, either the original CscMatrix, the obtained CsrMatrix, or a cooperation of the two needs to own the data - someone needs to be responsible for holding onto the actual Vec containing data and freeing it at some point.

    You have a few options:

    • CscMatrix and CsrMatrix may hold Rc<Vec<u32>> fields, where Rc is a reference-counted container that provides immutable access. In this case, you would clone the Rc when constructing a CsrMatrix, but cloning the Rc would only increment the reference count, not actually copy the whole vector. When the last clone of the Rc is freed, the actual vector is freed and its memory is released.

      • There's also a thread-safe variant called std::sync::Arc.
      • Rc cannot safely provide mutable access on its own, since there might be other clones of the Rc pointing to the same data.
    • CsrMatrix can be a lightweight view over the CscMatrix, borrowing from it:

      pub struct CsrMatrix<'a> {
          borrowed: &'a CscMatrix
      }
      

      This is quite restrictive - the CsrMatrix must not outlive the CscMatrix, the CscMatrix can't be moved while the CsrMatrix is live, and so on. This is mostly useful for short-lived, temporary usages of CsrMatrix.

    • As cdhowie's answer points out, Cow which provides flexibility to either own or borrow data.

    Can I make the transpose function return an immutable reference to the CsrMatrix object created?

    Not really - if it creates a CsrMatrix object in a local variable, then the reference it returns would be a dangling reference. If you're OK with reference-like semantics, you'd probably want to use the second option above.