State machine pattern and borrow checker

[tczajka]

I am thinking of a pattern like the following. I have a State that can generate all state changes legal in that state. Think: a board game and generating all legal moves in a given position. The StateChange holds a reference to State, thus maintaining the invariant that it is legal in that state. Then I pick one change, drop all the others, and want to apply it to the state.

This of course doesn't compile. I can't have a mutable reference and a shared reference at the same time.

However, logically this could be safe: this is the last remaining shared reference. Its lifetime could end in the middle of the apply method, before any modifications to State are made by the method.

The problem is that the lifetime can't look "inside" the method and end in the middle of it.

I can think of two solutions:

1. Use RefCell inside State. apply would drop the last remaining shared reference before it acquires a mutable reference. But this adds a runtime cost that seems unnecessary -- the compiler "knows" that it is the last remaining shared reference based on static analysis.

2. Have apply return a clone of State, rather than modifying in place. This adds an unnecessary cost of cloning, just before dropping the previous copy of State.

Any other ideas?

struct State;

struct StateChange<'a> {
    state: &'a State
}

impl State {
    fn possible_changes(&self) -> Vec<StateChange> {
        todo!()
    }

    fn apply(&mut self, change: StateChange) {
        todo!()
    }
}

fn main() {
    let mut state = State;
    let mut changes = state.possible_changes();
    let change = changes.pop().unwrap();
    drop(changes);
    state.apply(change);
}

[alice]

I believe the standard solution is to let your StateChange object not have a reference to the state.

[tczajka]

Right, that works, except now I don't know whether the state change is legal -- maybe it was generated for some other state -- and so have to validate it again in order to maintain invariants of State.

[RedDocMD]

So I guess, first validate and then store.

[tczajka]

That doesn't work if we don't know during apply for which State the change was generated / validated against. Storing a reference seems like a natural way to know that (it also prevents modifications).

I guess another solution is:
3. Store a unique ID in both State and StateChange and regenerate it after each modification.

[2e71828]

You could try something like this:

struct State;
struct StateChange;

struct Candidates<'a> {
    state: &'a mut State,
    options: Vec<StateChange>
} 

impl State {
    fn possible_changes(&mut self) -> Candidates<'_> {
        todo!()
    }
}

impl<'a> Candidates<'a> {
    fn apply(self, idx:usize) { todo!() }
    fn inspect(&self, idx)->&StateChange { todo!() }
}

fn main() {
    let mut state = State;
    let mut changes = state.possible_changes();
    changes.apply(0);
}