In-place update of slice of mutable refs

help
1

So I've got a tree-like datastructure, and I'm traversing a list of items at the same time.

I've reduced the borrowing issue to a tiny example: Playground

enum Node {
    Branch(Vec<Node>),
    Leaf
}

fn go_down_selected_node(many_nodes : &mut [&mut Node], idx: usize) {
    for n in many_nodes {
        let Node::Branch(br) = n else {unreachable!();};
        *n = &mut br[idx];
    }
}

The borrow checker complains (rightfully I believe) that many_nodes should have the type: &'a mut [&'a mut Node] because the list's lifetime latches on to each element due to the mutable iteration, but there should be a way to update every element of a mutable slice that doesn't latch onto the list's lifetime provided that the update of an element doesn't get to look at other elements.

Kind of like:

impl<'c, T> &'c mut [T] {
    pub fn update_with(self, mut f: impl FnMut(&mut T)) {
        // effectively:
        for v in self {
            f(v)
        }
    }
}

Do you know a standard way of doing this, or crates that provide this functionality?

Edit:
an even more compact example illustrating what I'd like to be able to do:

pub fn update_with<'e, T>(slice: &mut [&'e mut T], mut f: impl FnMut(&'e mut T) -> &'e mut T) {
    // explicit lifetime required in the type of `slice`. Lifetime `'e` required
    for v in slice {
        *v = f(*v)
    }
}
2

replace_with is one way.

    for n in many_nodes {
        replace_with::replace_with_or_abort(n, |n| {
            let Node::Branch(br) = n else {unreachable!();};
            &mut br[idx]
        });
    }
2 Likes
3

Note that this will abort if the indexing panics due to idx being out of bounds. This can be avoided by requiring the caller to provide a temporary value with the same lifetime (which will be observably swapped in if any panic happens):

fn go_down_selected_node<'n>(many_nodes: &mut [&'n mut Node], mut temp: &'n mut Node, idx: usize) {
    for n in many_nodes {
        std::mem::swap(n, &mut temp);
        temp = go_down_one(temp, idx);
        std::mem::swap(n, &mut temp);
    }
}

fn go_down_one<'n>(node: &'n mut Node, idx: usize) -> &'n mut Node {
    let Node::Branch(br): &'n mut Node = node else {
        unreachable!();
    };
    &mut br[idx]
}

(The separate go_down_one function is not necessary but the separate function signature helped me get the types/lifetimes right by separating the “mutable reference shuffle” problem from the actual application logic.)

2 Likes
4

Whoa, I didn't expect this to be possible in safe rust.

Now I just wonder what the actual cause of the lifetime issue is then. If we can swap out a value to 'n, then why can't we reborrow for 'n? n should have the lifetime of many_nodes due to the iteration, and that should prevent std::mem::swap right?

5

Oh wonderful! I've been wanting such an idiom for other things too. Often it leads to needing to use Option with take().

6

Hmm, but this does require temp to have the lifetime 'n, and it might not be possible to create such a lifetime.

7

The general of problem of replacing borrowed data is what to do during a panic. (In this case, your borrowed data is itself a &mut Node.)

As for lifetimes, it's unsound to grant a &'long mut Node through a &'short mut &'long mut Node as that can result in aliasing a &mut _, and more generally violating invariance can lead to dangling references and other UB.

Let me see if I can cook up a quick example... here you go. "Allowing" the long reborrow made it possible to smuggle a &'long mut Node out of the iteration loop. But many_nodes is supposed to be the exclusive access path after the iteration loop, when the 'local reborrow held by the iterator has expired.

8

The only way to get the same lifetime (i.e. a lifetime that is not shorter) out of reborrowing a mutable reference is to consume that mutable reference — to have an operation of the form fn(&'a mut A) -> &'a mut B, such as go_down_one is. That’s necessary for soundness — if it weren’t the case, then you could duplicate mutable references by performing the same reborrow operation on the same reference more than once.

1 Like
9

Ah I see, I had assumed a reborrow could have an equal lifetime, and thus would be storeable in the datastructure that the original could be stored in, but I see that was incorrect.

Ubiquitous implicit reborrowing makes it seem like a &mut is never "consumed", and can almost be viewed as being Copy, but in complicated cases like this it matters.

Thanks for yet again extending my borrow checking voodoo intuition a little further ^-^

10

Am I correct in intuiting that:

  • If a mutable ref is used somewhere and it is not used again later in the code it is consumed
  • whereas if it is used again later it is implicitly reborrowed?

Like, that that the criteria is for the compiler to decide to do a reborrow or not?

fn use_ref(r: &mut i32) {}

fn consume() {
  let mut a = 5;
  let a_ref = &mut a;
  use_ref(a_ref);
}
fn reborrow() {
  let mut b = 5;
  let b_ref = &mut b;
  use_ref(b_ref);
  *b_ref = 3;
}
11

If you have a &'a mut T, you can reborrow the T for 'a or shorter. So that reborrow can have an equal lifetime. Reborrowing for 'r makes the original unusable for 'r. So if you're in a function that received a &'a mut T, and you reborrow the T for all of 'a, you can't use the original again.

If you never use the original again, I don't think there's ever a relevant difference between moving it and reborrowing the direct referent (no difference between moving a_ref or passing &mut *a_ref in your example).

But in the OP, we have a situation with nested references. If you have a &'a mut &'b mut U, you can only reborrow the U for 'a or shorter. You can't reborrow for 'b. You can't safely move the &'b mut U from underneath the outer &'a mut _ due to the general problem of replacing borrowed data, so it's that's not an option in this case.[1]

So I think we're getting away from the OP, but I replied to this part anyway.

It's related to coercion sites. If you have some expected type that is annotated as a reference -- like the r arg of use_ref, or a let statement with a : &mut _ annotation, etc -- then implicit reborrows may happen. Actually, the way this topic usually comes up is when the compiler decides not to reborrow, which can happen due to a lack of annotation or because an argument type is some generic T and not a reference specifically.

let mut a = 5;
let a_ref = &mut a;
// reborrows
let _tmp: &mut _ = a_ref;
// moves
let _mv = a_ref;
// This will fail due to the move
println!("{a_ref}");

use std::fmt::Display;

fn generic<T: IntoIterator<Item: Display>>(iter: T) {
    for item in iter {
        println!("{item}");
    }
}

fn caller(slice: &mut [i32]) {
    // Moves because the arg is not a reference specifically,
    // it's a generic `T`
    generic(slice);
    // This will error due to the move
    println!("{slice:?}");
}

  1. without abstractions like replace_with, or having some temporary to put in place like the swap suggestion ↩︎

12

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.