Get mutable references to two elements of a slice by transmuting them

Hi there, just wanted to make sure following (simplified) snippet is sound.
Miri tells me that it's not, but that might be because of stacked borrows.

use core::mem::transmute;

pub struct SlotAccessor<'a> {
    slots_a: &'a mut [u16],
    slots_b: &'a mut [u16],
}

impl<'a> SlotAccessor<'a> {
    pub fn get_mut(&mut self, idx: usize) -> Option<&mut u16> {
        if idx < self.slots_a.len() {
            self.slots_a.get_mut(idx)
        } else if idx - self.slots_a.len() < self.slots_b.len() {
            let b_idx = idx - self.slots_a.len();
            self.slots_b.get_mut(b_idx)
        } else {
            None
        }
    }

    /// Returns pair of mutable references to two different slots.
    ///
    /// # Panics
    /// Panics if `first` == `second`.
    pub fn get_pair_mut(
        &'a mut self,
        first: usize,
        second: usize,
    ) -> Option<(&'a mut u16, &'a mut u16)> {
        assert!(first != second);
        unsafe {
            let first = transmute(self.get_mut(first)?);
            let second = transmute(self.get_mut(second)?);

            Some((first, second))
        }
    }
}

fn main() {
    let mut a = [0, 1, 2, 3, 4, 5];
    let mut b = [6, 7, 8, 9];

    let mut accessor = SlotAccessor {
        slots_a: &mut a,
        slots_b: &mut b,
    };

    let (first, second) = accessor.get_pair_mut(5, 6).unwrap();

    dbg!(first, second);
}

My reasoning is: it should be sound, as it follows similar logic to that of split_at() of slices. Obviously the way I am getting those mutable references is different - I transmute references returned from get_mut of each slice, but I think it still follows all the borrowing rules.

What do you think?

P.S. Miri error:

error: Undefined Behavior: trying to reborrow for Unique at alloc1077+0xa, but parent tag <1993> does not have an appropriate item in the borrow stack
  --> src/main.rs:34:19
   |
34 |             Some((first, second))
   |                   ^^^^^ trying to reborrow for Unique at alloc1077+0xa, but parent tag <1993> does not have an appropriate item in the borrow stack
   |
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
   = help: see "https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information"

Then it is not. Miri has no false positives, only false negatives.

You should do this using split_at_mut() instead of performing unsafe tricks. Also, transmuting pointers themselves is a code smell and is usually a sign of lack of understanding, since transmutation is not transitive (T -> U being transmutable doens't imply &T -> &U being transmutable, for exampe, nor does it imply the opposite direction.)

Here's a safe, generic alternative:

pub fn get_pair_mut<T>(
        slice: &mut [T],
        i: usize,
        j: usize,
) -> Option<(&mut T, &mut T)> {
    let (first, second) = (min(i, j), max(i, j));
    
    if i == j || second >= slice.len() {
        return None;
    }
    
    let (_, tmp) = slice.split_at_mut(first);
    let (x, rest) = tmp.split_at_mut(1);
    let (_, y) = rest.split_at_mut(second - first - 1);
    let pair = if i < j { 
        (&mut x[0], &mut y[0])
    } else {
        (&mut y[0], &mut x[0])
    };
    
    Some(pair)
}
4 Likes

Firstly, I'll second @H2CO3's advice to avoid unsafe here; the safety rules, especially around references, are often subtle and unintuitive— I am not good enough with unsafe to assert that everything I say below is completely correct.

The problem with your code is that accessing the inner &muts during self.get_mut(second) invalidates the pointers you got from them during self.get_mut(first). To make this work, you'll need to get raw pointers from a_slots and b_slots only once during get_pair_mut(). In fact, Rust's aliasing rules are hard enough to follow, I'd recommend storing raw pointers in your structure instead of references. I've modified your code to pass Miri, but I can't vouch for it being actually sound.

"Stacked borrows" is the closest thing we have right now to a specification of what is and isn't undefined behavior. This statement is like saying a C program doesn't have UB because it only violates the language spec, but appears to work— UB has everything to do with the spec, because it defines what future compilers might do with your code.

6 Likes

Here’s a possible way to write API for such a 2-slice SlotAccessor struct to support a get_pair_mut method using slice::split_at_mut: Rust Playground

Edit: Just noticing, the SlotAccessor::split_at_mut method should probably also support idx == slots_a.len() + slots_b.len(). The playground above doesn’t support that. Modified playground: Rust Playground

2 Likes

Thank you all for your input!

Wow, didn't know that - this is actually awesome.

Yeah, that was my initial idea, thank you.

Did you mean, references here?

I changed get_pair_mut slightly, so that I now de-reference two mutable pointers (so technically I don't have two mutable references which refer to the self at the same time). This time Miri doesn't issue any errors, but it might be that false negative.

pub fn get_pair_mut<'b>(
    &'b mut self,
    first: usize,
    second: usize,
) -> Option<(&'b mut u16, &'b mut u16)> {
    if first == second { return None; }
    
    let first = self.get_mut(first)? as *mut _;
    let second = self.get_mut(second)? as *mut _;
    
    unsafe {
        Some((&mut *first, &mut *second))
    }
}

So basically making my own slice :stuck_out_tongue:

Yeah, I heard about it. I assumed it could be a bug because of the Miri message: but the rules it violated are still experimental, but as @H2CO3 explained - Miri apparently has only false negatives.

Miri accurately checks the stacked borrows rules, but they haven't been formally adopted by the Rust maintainers yet. It seems likely, but that sort of thing is a big commitment that shouldn't be rushed into— It's possible that the stacked borrows model has unforseen hazards for either program authors or the Rust maintainers.

3 Likes

You should take a look at how swap works on slices. There's some good context in this issue about how to do this correctly without accidentally overlapping &muts:

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.