Trying to convert a State Machine from dynamic dispatch to static dispatch


#1

I’ve written this State Machine:

// ----- State -----
trait State {
    fn execute(&mut self) -> Option<Box<State>>;
}

struct Connect;
struct CloseConnection;
struct GoodBye;

impl State for Connect {
    fn execute(&mut self) -> Option<Box<State>> {
        println!("Connect State executed");
        Some(Box::new(CloseConnection))
    }
}

impl State for CloseConnection {
    fn execute(&mut self) -> Option<Box<State>> {
        println!("CloseConnection State executed");
        Some(Box::new(GoodBye))
    }
}

impl State for GoodBye {
    fn execute(&mut self) -> Option<Box<State>> {
        println!("Good Bye my friend!");
        None
    }
}

// ----- State Machine -----
struct StateMachine {
    state: Box<State>,
}

impl Iterator for StateMachine {
    type Item = ();
    fn next(&mut self) -> Option<Self::Item> {
        self.state = match self.state.execute() {
            Some(next_state) => next_state,
            None => return None,
        };
        Some(())
    }
}

// ----- Application start -----
fn main() {
    let state_machine = StateMachine { state: Box::new(Connect) };
    for _state in state_machine {} // state_machine consumed, yay!
}

I cannot figure how to switch this to static dispatch.
My guess would be that I can throw around a bit of <T: State> or 'static, and remove the Box but however I change the code, I cannot make it work.
I tried using -> impl from nightly(I am okay with using nightly only features) and couldn’t make that work either.

Any suggestions?


#2

I usually implement state machines with an enum State, not a trait that’s implemented by all states. This way, you don’t need Box<State> and you can define methods directly on the State, no dynamic dispatch involved.


#3

I could do this ugly(impl State for GoodBye) code:

// ----- State -----
trait State {
    type NextState: State + Sized;
    fn execute(&mut self) -> Option<Self::NextState>;
}

struct Connect;
struct CloseConnection;
struct GoodBye;

impl State for Connect {
    type NextState = CloseConnection;
    fn execute(&mut self) -> Option<Self::NextState> {
        println!("Connect State executed");
        Some(CloseConnection)
    }
}

impl State for CloseConnection {
    type NextState = GoodBye;
    fn execute(&mut self) -> Option<Self::NextState> {
        println!("CloseConnection State executed");
        Some(GoodBye)
    }
}

impl State for GoodBye {
    type NextState = GoodBye;
    fn execute(&mut self) -> Option<Self::NextState> {
        println!("Good Bye my friend!");
        None
    }
}

//// ----- State Machine -----
struct StateMachine<T> where T: State + Sized {
    state: T,
}

//impl<T: State + Sized> Iterator for StateMachine<T> {
//    type Item = ();
//    fn next(&mut self) -> Option<Self::Item> {
//        self.state = match self.state.execute() {
//            Some(next_state) => next_state,
//            None             => return None,
//        };
//        Some(())
//    }
//}

// ----- Application start -----
fn main() {
    let mut state_machine = StateMachine { state: Connect };
    state_machine.state.execute().unwrap().execute().unwrap().execute();
}

But I cannot make it iterate and I cannot have a state return one of multiple different states(although the last issue is solvable with enums). That commented code complains about associated types…


#4

The issue with an enum is that it is not flexible. It locks down to my own code.
To change the states, you have to edit the enum.

Current implementation with boxes, means you can add at any point as many new states as you want without having access to the implementation. You just implement “State” and can have your own StateMachine.

So:

enum States {
  DoThis,
  DoThat,
}

is locked to my implementation.
Somebody else wants:

enum States {
  DoThis,
  DoThat,
  DoingSomethingElse,
  DoingSomethingCompletelyDifferent,
}

It is not flexible. Also, they can’t go into this code…


#5

The way you wrote the code, it is not possible to get rid of dynamic dispatch (nor the boxing), since the compiler can not possibly know the code the user wants to have executed in any custom states.

There are a few different ways to solve this. For example, instead of allowing users to add custom states, you could implement a callback mechanism (either statically or dynamically dispatched) instead of custom states, or use an enum and add a Custom(...) variant.

This all depends on what exactly you want to do, of course.


#6

I encode states as a tags and and then use a decorated struct for every state. I don’t have enough time for a long writeup, but an example can be found here: http://laze.rs/lazers-replicator/src/verify_peers/index.html


#7

These 2 days I played around with all kind of options(even hit a compiler bug) and I ended up on the simplest(from the ones I tried) that still fits the task I wanted to achieve. If the optimizer works well, this should be optimized away as if it was hand-written:

trait State {
    #[inline] fn execute(self);
}

struct Connect;
struct SuccessfulConnection;
struct FailedConnection;

impl State for Connect {
    #[inline]
    fn execute(self) {
        println!("Connect State executed");
        let connection_failed = false;

        if connection_failed {
            FailedConnection.execute()
        } else {
            SuccessfulConnection.execute()
        }
    }
}

impl State for SuccessfulConnection {
    #[inline]
    fn execute(self) {
        println!("SuccessfulConnection state executed");
    }
}

impl State for FailedConnection {
    #[inline]
    fn execute(self) {
        println!("FailedConnection state executed");
    }
}

fn main() {
    Connect.execute()
}

But this won’t be very usable.
What if one of the states fail at some point?
This could be one way to do it:

// ----- State -----
type StateResult = Result<(), &'static str>; // str as an example

trait State: Sized + Send {
    fn execute(self) -> StateResult;
}

struct TryConnecting;
struct Connect;
struct TransferData;
struct CloseConnection;

impl State for TryConnecting {
    fn execute(self) -> StateResult {
        println!("Attempting to connect"); // using `log` here of course
        match Connect.execute() {
            Err(ref reason) => {
                println!("Failed to execute all states: {}", reason);
                CloseConnection.execute()
            }
            Ok(_) => Ok(()),
        }
    }
}

impl State for Connect {
    fn execute(self) -> StateResult {
        let connection_failed = false;
        if connection_failed {
            Err("Connection failed. Why: lorem ipsum")
        } else {
            TransferData.execute()
        }
    }
}

impl State for TransferData {
    fn execute(self) -> StateResult {
        println!("Transferring data");
        let transfer_failed = false;
        if transfer_failed {
            Err("Data transfer failed. Why: lorem")
        } else {
            CloseConnection.execute()
        }
    }
}

impl State for CloseConnection {
    fn execute(self) -> StateResult {
        println!("Attempting to close connection");
        let operation_failed = false;
        if operation_failed {
            Err("Maybe somebody wants to try again? You can save states back there, \
                like the number of attempts")
        } else {
            println!("Good Bye!");
            Ok(())
        }
    }
}

// ----- Application start -----
fn main() {
    match TryConnecting.execute() {
        Err(_) => {}, // D'oh!
        Ok(_)  => {}, // It's ok... I take
    }
    // Maybe a queue of states?...
}

#8

Looking at the assembly of the first(simpler) static dispatch example, I see this:

	leaq	ref7711(%rip), %rax
	movq	%rax, (%rsp)
	movq	$1, 8(%rsp)
	movq	$0, 16(%rsp)
	leaq	ref7708(%rip), %rbx
	movq	%rbx, 32(%rsp)
	movq	$0, 40(%rsp)
	leaq	(%rsp), %rdi
	callq	_ZN3std2io5stdio6_print17h1fa1e74f0fbe2e89E@PLT
.........
ref7708:
	.size	ref7708, 0

	.type	str7710,@object
	.section	.rodata.str7710,"a",@progbits
	.p2align	4
str7710:
	.ascii	"Connect State executed\n"
	.size	str7710, 23

	.type	ref7711,@object
	.section	.data.rel.ro.ref7711,"aw",@progbits
	.p2align	3
ref7711:
	.quad	str7710
	.quad	23
	.size	ref7711, 16

	.type	str7712,@object
	.section	.rodata.str7712,"a",@progbits
	.p2align	4
str7712:
	.ascii	"SuccessfulConnection state executed\n"
	.size	str7712, 36

	.type	ref7713,@object
	.section	.data.rel.ro.ref7713,"aw",@progbits
	.p2align	3

Do I understand tihs correctly?
It loads the strings from println! from both functions and prints them in 1 single call to print?