Comments

08/19/05: State of Grace

Need a nice state machine? I've got a real beaut right under the fold. Barely used, gets great mileage. Here's what it can do for you:

  • pull together all sorts of disparate business logicky transitions into one nice, encapsulated, formally complete model
  • complain loudly when some application logic tries to make an illegal state transition
  • output itself in DOT format, creating nifty automatic documentation


This doesn't quite implement the State Pattern which, like Strategy, uses polymorphism to let an object change its behavior based on state. Rather, it's a Finite State Machine, representing only the nodes and arcs (states and actions) that make up the legal lifecycle of whatever concept.


By extracting the transition logic into a separate object, we apply Separation of Concerns and let the owning object deal with the business of actually verifying whether a transition is desirable, whether other business rules are met, of spawning other processes or notifying listeners, or attaching Command objects to perform entry, exit or transition actions. Of course, any of these features (especially notifying listeners) can easily be added to the machine itself, but let's keep it simple for now.
It's straightforward enough to refactor to the full State pattern (also described by Metzger) if and when we want to.


Why would you want to use a state machine in the first place instead of, say, a bunch of booleans, or just smart methods? As Metzger says:


When you model an object whose state is important, you may find that you have a variable that tracks how the object should behave, depending on its state. This variable may appear in complex, cascading if statements that focus on how to react to the events that an object can experience. One problem with this approach to modeling state is that if statements can become complex. Another problem is that when you adjust how you model the state, you often have to adjust if statements in several methods. The STATE pattern offers a cleaner, simpler approach, using a distributed operation.


But the real reason to use a state machine is social: with a large project, involving many engineers, product managers, QA testers, etc., it's good to have a formal, well-described model for the lifecycles of your objects; using the code below follows the principle of Don't Repeat Yourself by allowing the model, and its representation in actual, executing code, to reign supreme.



Here's a sample state machine, for tracking the transition from daytime to nighttime and back again, plus an extra terminal node for when the world explodes. (As we all know, Armageddon can only happen at night.)
 
    enum DayState { 
        DAYTIME, 
        NIGHT, 
        NEVER, 
    } 
 
    enum DayAction { 
        SUNSET, 
        SUNRISE, 
        ARMAGEDDON, 
    } 
 
    class DayMachine extends StateMachine<DayState, DayAction> { 
        { 
            addTransition(DayState.DAYTIME, DayAction.SUNSET, DayState.NIGHT); 
            addTransition(DayState.NIGHT, DayAction.SUNRISE, DayState.DAYTIME); 
            addTransition(DayState.NIGHT, DayAction.ARMAGEDDON, DayState.NEVER); 
        } 
    } 
That's all it takes to define a state machine. You can then use it from your domain object code:
 
    class Day { 
        private DayMachine dayMachine = new DayMachine(); 
        private DayState state = DayState.DAYTIME; 
 
        public void rotate() { 
            if (state == DayState.DAYTIME) { 
                doSunset(); 
            } 
            else if (state == DayState.NIGHT) { 
                state = dayMachine.move(state, DayAction.SUNRISE, DayState.DAYTIME); 
            } 
        } 
 
        public void doSunset() { 
            state = dayMachine.move(state, DayAction.SUNSET, DayState.NIGHT); 
        } 
 
    } 
Note that if someone calls doSunset() when it's already night, the machine will throw an exception. Also note the switching conditional in rotate(); this is ripe for refactoring to State Pattern. In that case we'd end up with a different subclass for each possible state, something like:
 
class Night extends DayState { 
  public DayState sunrise() { 
    return new Daytime(); 
  } 
  public DayState sunset() { 
    throw new InvalidStateTransition("performing sunset on night"); 
  } 
} 
...but there are some tricky OO decisions involved in that process which I won't go into now; suffice it to say that using a state machine accomplishes 60-80% of the power of the State Pattern and is a lot easier to do in Java. (In Smalltalk, OTOH...)

Finally, the coup de grace: the machine can output itself in DOT format:

 
digraph day { 
	daytime [label="daytime"]; 
	nighttime [label="nighttime"]; 
	never [label="never"];	 
	daytime -> nighttime [label="sunset"]; 
	nighttime -> daytime [label="sunrise"]; 
	nighttime -> never [label="armageddon"]; 
} 
which produces this pretty diagram: day states

Without further ado, here's the code, using Java 1.5 generics, and including (naturally) a unit test:

 
public class StateMachine<STATE extends Enum, ACTION extends Enum> { 
 
    static class Transition<STATE extends Enum, ACTION extends Enum> { 
        STATE from; 
        ACTION action; 
        STATE to; 
 
        public Transition(STATE from, ACTION action, STATE to) { 
            this.from = from; 
            this.action = action; 
            this.to = to; 
        } 
 
        public STATE getFrom() { 
            return from; 
        } 
 
        public STATE getTo() { 
            return to; 
        } 
 
        public ACTION getAction() { 
            return action; 
        } 
    } 
 
    LinkedHashSet<STATE> states = new LinkedHashSet<STATE>(); 
    List<Transition> transitions = new ArrayList<Transition>(); 
 
    public void addTransition(STATE initialState, ACTION action, STATE targetState) { 
        transitions.add(new Transition<STATE, ACTION>(initialState, action, targetState)); 
        states.add(initialState); 
        states.add(targetState); 
    } 
 
    public List<STATE> transitionsFrom(STATE initialState) { 
        List<STATE> targetStates = new ArrayList<STATE>(); 
        for (Transition<STATE, ACTION> transition : transitions) { 
            if (transition.getFrom().equals(initialState)) { 
                targetStates.add(transition.getTo()); 
            } 
        } 
        return targetStates; 
    } 
 
    public STATE move(STATE initialState, ACTION action, STATE targetState) { 
 
        for (Transition<STATE, ACTION> transition : transitions) { 
            if (transition.getFrom().equals(initialState) && transition.getAction().equals(action)) { 
                return transition.getTo(); 
            } 
        } 
        throw new IllegalStateTransition(initialState, action, targetState); 
    } 
 
    public void writeDotFormat(Writer writer) { 
        PrintWriter out = new PrintWriter(writer); 
        out.println("digraph state {"); 
        for (STATE state : states) { 
            out.println(state.name() + " [label=\"" + state.name() + "\"];"); 
        } 
        for (Transition transition : transitions) { 
            out.print(transition.getFrom().name()); 
            out.print(" -> "); 
            out.print(transition.getTo().name()); 
            out.print(" [label=\""); 
            out.print(transition.getAction().toString().toLowerCase()); 
            out.print("\"];"); 
            out.println(); 
        } 
        out.println("}"); 
    } 
} 
 
public class IllegalStateTransition extends RuntimeException { 
    public IllegalStateTransition(Enum initialState, Enum action, Enum targetState) { 
        super("Attempting to perform " + action + " to move from " + initialState + " to " + targetState); 
    } 
} 
 
--- 
 
public class StateMachineTest extends TestCase { 

    private DayMachine dayMachine; 
 
    protected void setUp() throws Exception { 
        super.setUp(); 
        dayMachine = new DayMachine(); 
    } 
 
    public void testTerminalState() throws Exception { 
        assertEmpty(dayMachine.transitionsFrom(DayState.NEVER)); 
    } 
 
    public void testMoveToValidState() throws Exception { 
        assertEquals(DayState.NIGHT, dayMachine.move(DayState.DAYTIME, DayAction.SUNSET, DayState.NIGHT)); 
    } 
 
    public void testMoveToInvalidState() throws Exception { 
        try { 
            dayMachine.move(DayState.DAYTIME, DayAction.ARMAGEDDON, DayState.NEVER); 
            fail("Should have failed"); 
        } 
        catch (IllegalStateTransition e) { 
            assertEquals("Attempting to perform ARMAGEDDON to move from DAYTIME to NEVER", e.getMessage()); 
        } 
    } 
 
    public void testDotFormat() throws Exception { 
        StringWriter writer = new StringWriter(); 
        dayMachine.writeDotFormat(writer); 
 
        BufferedReader reader = new BufferedReader(new StringReader(writer.toString())); 
 
        assertEquals("digraph state {", reader.readLine()); 
        assertEquals("DAYTIME [label=\"DAYTIME\"];", reader.readLine()); 
        assertEquals("NIGHT [label=\"NIGHT\"];", reader.readLine()); 
        assertEquals("NEVER [label=\"NEVER\"];", reader.readLine()); 
        assertEquals("DAYTIME -> NIGHT [label=\"sunset\"];", reader.readLine()); 
        assertEquals("NIGHT -> DAYTIME [label=\"sunrise\"];", reader.readLine()); 
        assertEquals("NIGHT -> NEVER [label=\"armageddon\"];", reader.readLine()); 
        assertEquals("}", reader.readLine()); 
    } 
 
    private void assertEmpty(List<DayState> list) { 
        assertEquals(0, list.size()); 
    } 
 
} 

Comments made

Given that the destination state is uniquely determined by the starting state and the action, why is the destination state an argument to move? I can see the value that it allows move to throw an exception if the calling code expects the destination state to be Foo, but the state machine describes it as Bar. (This actually should be inserted into your code and your test, as currently, dayMachine.move(DayState.DAYTIME, DayAction.SUNSET, DayState.ARMAGEDDON) will succeed and return DayState.NIGHT.)

However, frequently I would expect that I'd want my code to take an action on a state, but not have a dependence on what the next state will be. Is there any reason not to add a method:

public STATE move(STATE initialState, ACTION action);

I'd also like the state machine to make sure that {initialState, action} tuples are unique, so as not to violate this constraint. You can do this by having a HashMap<Pair<STATE, ACTION>, STATE> and having addTransition throw if the transition already exists with a different destination state.
08/26/05 13:05:22
Tim - you're quite right, and I've changed the code accordingly. In fact, I've separated out the above code as a StateDiagram and made a separate StateMachine which contains a state. Actually it's cooler than that -- the StateMachine is responsible for getting and setting state, so it can be an inner class of your domain object, with type-specific methods. In the above example, that would turn into "dayMachine.sunset()" which is implemented as a call to "this.dayDiagram.move(DayAction.SUNSET)".
11/12/05 20:44:31
Selecting the right http://www.discountednorthf... backpacks for camping also signifies selecting one particular that is cost-effective, and has several capabilities included for the most sensible price as probable.
02/28/12 23:54:44
In the summer season, the cheap [url=http://www.oakleysglassesfa...]replica oakleys[/url] designer have made the chic sunglasses, which have become the necessary fashionable accessories, which also makes world's big fashion. It is really so nice to wear the Newest design [url=http://www.oakleysglassesfa...]replica oakley sunglasses[/url] to be the top number one fashion model.
04/26/12 02:29:18

Add comment

Sorry, but due to blog comment spam, I have to ask you to create an account before you post a comment. Please log in (using the form on the top right of the page) or click here to create an account: Create an account!