Satisfying the borrow checker with a struct that processes a queue of actions

user_18568281 0
Viewed 80

I am trying to write a struct which owns some data in a Vec (or perhaps contains a Vec of mutable references - not really important which one), and which can process a queue of "actions", where each action is some sort of calculation which mutates the elements of this Vec. Here is a minimal example of what I have written so far:

// some arbitrary data - may be large, so should not be cloned or copied
#[derive(PartialEq)]
struct T(i32, &'static str);

struct S(Vec<T>);
impl S {
    fn get_mut(&mut self, t: &T) -> &mut T {
        self.0.iter_mut().find(|a| *a == t).unwrap()
    }
    fn process_actions(&mut self, queue: ActionQueue) {
        // some arbitrary calculation on the elements of self.0
        for a in queue.actions {
            let t1 = self.get_mut(a.t1);
            t1.0 += a.t2.0;
        }
    }
}

#[derive(Debug)]
enum Error {
    ActionError,
    ActionQueueError,
}

struct Action<'a> {
    s: &'a S,
    t1: &'a T,
    t2: &'a T,
}
impl<'a> Action<'a> {
    pub fn new(s: &'a S, t1: &'a T, t2: &'a T) -> Result<Action<'a>, Error> {
        if s.0.contains(&t1) && s.0.contains(&t2) {
            Ok(Action { s, t1, t2 })
        } else {
            Err(Error::ActionError)
        }
    }
}

struct ActionQueue<'a> {
    s: &'a S,
    actions: Vec<Action<'a>>,
}
impl<'a> ActionQueue<'a> {
    pub fn new(s: &'a S, actions: Vec<Action<'a>>) -> Result<ActionQueue<'a>, Error> {
        if actions.iter().all(|a| std::ptr::eq(a.s, s)) {
            Ok(ActionQueue { s, actions })
        } else {
            Err(Error::ActionQueueError)
        }
    }
}

fn main() -> Result<(), Error> {
    let t1 = T(1, "a");
    let t2 = T(2, "b");
    let mut s = S(vec![t1, t2]);

    let a = Action::new(&s, &t1, &t2)?; // error: borrow of moved value: `t1`
    let q = ActionQueue::new(&s, vec![a])?;
    s.process_actions(q); // cannot borrow `s` as mutable because it is also borrowed as immutable

    Ok(())
}

There are a few problems with this:

  1. I can't create the Action because t1 and t2 have already been moved.
  2. Even if I could, I can't process the action queue because s is already immutably borrowed in the Action. The reason I want the Action (and ActionQueue) to contain a reference to s is because, from what I understand, it's good to use types prevent the creation of invalid data, e.g. an Action (to be processed by s) referring to data not contained in s.
  3. The get_mut function of S seems a bit weird and hacky, like I shouldn't need to have such a function.

I understand why the errors occur and what they mean, but I don't see any way to get around this problem, because in order to define any Action, I need to refer to elements of s.0 which I am not allowed to do. So my question is, how should this code be rewritten so that it will actually compile? It doesn't matter if the design is completely different, as long as it achieves the same goal (i.e. allows to queue up actions to be processed later).

borrow-checker rust design-patterns
1 Answers

I managed to get the desired behavior by:

  1. I changed the references in T to usize indices, which refer to the same data as before, but now only when an action is being performed, and thus in a new scope. This does require slightly more forethought, and would be a lot more expensive if you moved the T items in place (in the S vector), since you would need to find the new indices of the items- potentially braking it (i haven't tested, but don't see why anything more than a simple iteration search would be needed)

2.limiting the number of borrows. I removed the S reference in Action, which makes this possible, although it sacrifices some reliability (more on that later) it was redundant anyway.

  1. The usize index search solves the get_mut() problem, but also means that now to use the data, you have to refer to the individual fields of T. The reason get_mut() seems so hacky is because it's essentially a hypercondensed iteration search. It would be really helpful if you move the Ts inside S, so you may want to keep it in your source, but its not needed in this example.
// some arbitrary data - may be large, so should not be cloned or copied
use std::marker::PhantomData;
struct T(i32, &'static str);
struct S(Vec<T>);
impl S {
    fn process_actions(&mut self, changes: [usize;2]) {
        let mut a = self.0[changes[0]].0;
        a += self.0[changes[1]].0;
        println!("the total is {}",a);
    }
}

#[derive(Debug)]
enum Error {
    ActionQueueError,
}

struct Action<'a> {
    t1: usize,
    t2: usize,
    phantom_lifetime: PhantomData<&'a u8>,
}
impl<'a> Action<'a> {
    pub fn new(ts: [usize;2]) -> Action<'a> {
        Action {
            t1: ts[0],
            t2: ts[1],
            phantom_lifetime: PhantomData,
        }
    }
}
struct ActionQueue<'a> {
    s: S,
    actions: Vec<Action<'a>>,
}
impl<'a> ActionQueue<'a> {
    pub fn new(s: S, actions: Vec<Action<'a>>) -> Result<ActionQueue<'a>, Error> {
        if actions.iter().all(|a| s.0.len() > a.t1 && s.0.len() > a.t2) {
            Ok(ActionQueue { s, actions })
        } else {
            Err(Error::ActionQueueError)
        }
    }
    pub fn process_many_actions(&mut self) {
        for gos in self.actions.iter_mut() {
            self.s.process_actions([gos.t1,gos.t2])
        }
    }
}

fn main() -> Result<(), Error> {
    let t1 = T(1, "a");
    let t2 = T(2, "b");
    let s = S(vec![t1, t2]);
    let a = Action::new([0,1]);
    let mut q = ActionQueue::new(s, vec![a])?;
    q.process_many_actions();
    Ok(())
}

On safety, you probably noticed i removed both checks from the question. the first check was a fairly simple replacement, the only real changes being that now it makes the check when moving into ActionQueue instead of immediately, and it checks that the indices will find something, not that it will 110% be the same element in that index as when you put it in. The second check is obsolete, since S is moved into ActionQueue and then changes on a method to ActionQueue. While maybe a bit harder to debug, that will at least make the function calls simpler and safer.

T'was quite the pickle you got yourself in! In the future, to make debugging easier( or at least take less time for answerers, and attract more people... there are other people on this site, I think《?》), keep the rules of rust borrowing in mind as you write. This won't eliminate errors, not even close, but should keep you out of as big of trouble you've had.

user_167920370
Related