Aliasing rules and making Rust function "generic over aliasing"

Question

I have a routine which takes in an immutable slice of points and performs some transformation, writing to a mutable slice of points. (As a simple example, let's say we translate all the points by some constant.) Suppose also that the implementation cannot be reduced to a point-by-point processing. (In my case, I have vectorized the algorithm after confirming that the compiler can't do it automatically.)

While minimizing duplicate code, I want the routine to work with both 1. transforming one array to a different array, and 2. transforming a single, mutable array in-place.

Suppose the existing implementation has the form

fn transform(in_: &[Point], out: &mut [Point], translate: Point) {
   // ...
}

This solves case (1), but because we can't borrow the same array mutably and immutably at the same time, this will not work for case (2). Indeed, trying to use unsafe, and get simultaneous mutable and immutable references, is instant undefined behavior.

How can we get around this problem? Can we bypass the rules by doing something like

unsafe fn transform_impl(in_: &[UnsafeCell<Point>], out: &[UnsafeCell<Point>], translate: Point) {
  // ... promise we won't modify in_ here, nor have overlapping lifetimes
  // between values read from in_ and written to out ...
}

fn transform_in_place(inout: &mut [Point], translate: Point) {
  unsafe {
    let a: &[UnsafeCell<Point>] = std::mem::transmute(inout);
    transform_impl(a, a, translate);
  }
}

fn transform(in_: &[Point], out: &mut [FPoint], translate: Point) {
  unsafe {
    transform_impl(std::mem::transmute(in_), std::mem::transmute(out), translate);
  }
}

using interior mutability, and promise that we won't change values in out from "underneath" the values in in_? Or is casting an immutable slice to an UnsafeCell slice, like before, instant undefined behavior?

(In C, we can just use pointers, since non-restrict pointers of the same type may alias.)

I would prefer to have a single function to handle both cases, if only to minimize the amount of duplicate generated code. If this is ultimately impractical, what would be an elegant way to make this work without implementing the algorithm in source twice?

Answer 1

Transmuting &mut T to &UnsafeCell<T> (and therefore &mut [Point] to &[UnsafeCell<Point>] is definitely fine. This is documented. You do have to be careful to not hold a mutable and shared reference at the same time, though, which means restricting the access to either & from in_ or &mut from out, but not both at the same time for the same index. It may even be possible to do it safely, using Cell, with Cell::from_mut() and Cell::as_slice_of_cells() (depending on how you need to access the Points).

The problem is the other cast, &T to &UnsafeCell<T>. If the reference is then written into, this is undoubtedly UB. The question is what happens when we only create a reference and not write into it.

Stacked Borrows marks this UB. Tree Borrows (another possible aliasing model) accepts this. It is my understanding that people want this to be allowed, but it is unclear how to allow this with Stacked Borrows.

Given the aliasing model is not decided yet, I'd recommend to avoid this pattern. It is possible to do what you want if you take raw points and not references; this does mean more unsafe code, though.

Answer 2

As an alternative, instead of relying on transmute, I suggest defining transform_inplace() with all the details and provide simple adapters for cases in which the transform does not need to occur in place.

#[derive(Debug, Clone, Copy)]
struct Point {
    x: f64,
    y: f64,
}

fn transform_inplace(
    inout: &mut [Point],
    translate: Point,
) {
    for p in inout.iter_mut() {
        p.x += translate.x;
        p.y += translate.y;
    }
}

fn transform(
    input: &[Point],
    output: &mut [Point],
    translate: Point,
) {
    output.clone_from_slice(input);
    transform_inplace(output, translate);
}

fn transformed(
    input: &[Point],
    translate: Point,
) -> Vec<Point> {
    let mut output = input.to_owned();
    transform_inplace(&mut output, translate);
    output
}

fn main() {
    {
        let mut points = [
            Point { x: 1.1, y: 2.2 },
            Point { x: 3.3, y: 4.4 },
            Point { x: 5.5, y: 6.6 },
        ];
        transform_inplace(&mut points, Point { x: 10.0, y: 20.0 });
        println!("transform_inplace(): {:?}", points);
    }
    {
        let input = [
            Point { x: 1.1, y: 2.2 },
            Point { x: 3.3, y: 4.4 },
            Point { x: 5.5, y: 6.6 },
        ];
        let mut output = [Point { x: 0.0, y: 0.0 }; 3];
        transform(&input, &mut output, Point { x: 10.0, y: 20.0 });
        println!("transform(): {:?}", output);
    }
    {
        let input = [
            Point { x: 1.1, y: 2.2 },
            Point { x: 3.3, y: 4.4 },
            Point { x: 5.5, y: 6.6 },
        ];
        let output = transformed(&input, Point { x: 10.0, y: 20.0 });
        println!("transformed(): {:?}", output);
    }
}
/*
transform_inplace(): [Point { x: 11.1, y: 22.2 }, Point { x: 13.3, y: 24.4 }, Point { x: 15.5, y: 26.6 }]
transform(): [Point { x: 11.1, y: 22.2 }, Point { x: 13.3, y: 24.4 }, Point { x: 15.5, y: 26.6 }]
transformed(): [Point { x: 11.1, y: 22.2 }, Point { x: 13.3, y: 24.4 }, Point { x: 15.5, y: 26.6 }]
*/

Answer 3

Consider using traits to handle this case.

You can create a trait that defines "point I/O", with methods to get immutable and mutable slices. Then you can implement it for &mut [Point] (for the in-place case) and (&[Point], &mut [Point]) for the non-overlapping case.

The trait need not be public, as you can provide different public functions to handle each case, but that delegate to a common implementation function.

This requires that the implementation can be written in a way that doesn't require reads that overlap with writes.

use std::slice::SliceIndex;

struct Point;

trait PointIO {
    fn len(&self) -> usize;

    fn get<I: SliceIndex<[Point]>>(&self, range: I) -> &I::Output;
    fn get_mut<I: SliceIndex<[Point]>>(&mut self, range: I) -> &mut I::Output;
}

impl PointIO for &mut [Point] {
    fn len(&self) -> usize {
        <[Point]>::len(self)
    }

    fn get<I: SliceIndex<[Point]>>(&self, range: I) -> &I::Output {
        &self[range]
    }

    fn get_mut<I: SliceIndex<[Point]>>(&mut self, range: I) -> &mut I::Output {
        &mut self[range]
    }
}

impl PointIO for (&[Point], &mut [Point]) {
    fn len(&self) -> usize {
        std::cmp::min(self.0.len(), self.1.len())
    }

    fn get<I: SliceIndex<[Point]>>(&self, range: I) -> &I::Output {
        &self.0[range]
    }

    fn get_mut<I: SliceIndex<[Point]>>(&mut self, range: I) -> &mut I::Output {
        &mut self.1[range]
    }
}

fn transform_impl(points: impl PointIO, translate: Point) {
    todo!()
}

fn transform(in_: &[Point], out: &mut [Point], translate: Point) {
    transform_impl((in_, out), translate);
}

fn transform_overlapping(inout: &mut [Point], translate: Point) {
    transform_impl(inout, translate);
}