Java – Trouble with circular dependency in state machine design

design-patternsfinite-state machinejavaobject-orientedobject-oriented-design

I am trying to develop the structure for a basic state machine that can also take in input and produce output. I've hit a bit of a mental block in trying to figure out how to model the relationship between states and transitions, where my design won't support the state machine having a cycle.

Here are a couple of the interfaces that should describe what I have and why it's a problem (ignore the parts that deal with how the context is stored and I/O is handled, this is a simplification):

public interface State<T extends StateInput> {
    int id();
    ContextAndOutput goContinuing(StorableContext context, Input input);
    ContextAndOutput render(T stateInput, Input input);
}

public interface InitialState<T extends StateInput> extends State<T> {
    ContextAndOutput buildInitial(Input input);
}

public interface Transition<T extends Context> {
    boolean canBeFollowed(T context, Input request);
    ContextAndOutput transition(T context, Input request);
}

public interface Context {
    StorableContext storable();
}

public class ContextAndOutput {
    private final StorableContext context;
    private final Output output;
}

public class StorableContext {
    private final int stateId;
    private final Object data;
}

public class Output {
    private final String raw;
}

public class Input {
    private final String raw;
}

And some example implementations to show how I'm envisioning them getting constructed (note this is in-progress):

public class Context0 implements Context {

    private final int stateId;
    private final String sampleContextData;

    @Override
    public StorableContext storable() {
        return new StorableContext(stateId, this);
    }
}

public class State0 implements InitialState<State0Input> {

    private final List<Transition<Context0>> transitions;

    @Override
    public ContextAndOutput buildInitial(Input input) {
        System.out.println(stateName() + ": building initial");
        Context0 initial = new Context0(id(), input.getRaw());
        return new ContextAndOutput(initial.storable(), 
                                    new Output("What would you like to buy?"));
    }

    @Override
    public int id() {
        return 0;
    }

    @Override
    public String stateName() {
        return this.getClass().getSimpleName();
    }

    @Override
    public ContextAndOutput goContinuing(StorableContext context, Input input) {
        System.out.println(stateName() + ": go continuing");

        // XXX here is the only place we go StorableContext->Context 
        // in a non type safe way, can we do something else?
        Context0 typedContext = (Context0) context.getData(); 
        System.out.println(String.format(
                "I know that the current user query is '%s' " + 
                "but the original one (from context) is '%s'",
                input.getRaw(),
                typedContext.getInitiateConversationQuery()));
        // XXX do something smarter
        Transition<Context0> bestFitTransition = transitions.iterator().next(); 
        return bestFitTransition.transition(typedContext, input);
    }

    @Override
    public ContextAndOutput render(State0Input stateInput, Input input) {
        System.out.println(stateName() + ": rendering");
        System.out.println(stateName() + ": building initial");
        Context0 initial = new Context0(
                               id(),
                               stateInput.getInitiateConversationQuery());

        return new ContextAndOutput(initial.storable(), new Output("Hello!"));
    }
}

public class OneToZero implements Transition<Context1> {

    private final State0 destination;

    @Override
    public boolean canBeFollowed(Context1 context, Input request) {
        return true;
    }

    @Override
    public ContextAndOutput transition(Context1 context, Input request) {
        // Build StateInput for State1 from context
        State0Input stateInput = null; // TODO
        return destination.render(stateInput, request);
    }
}

public class StateMachine {

    private final InitialState initialState;
    private final Map<Integer, State> everyStateIdToState;

    public StateMachine(
               InitialState initialState, 
               Set<ContinuingState> continuingStates) {

        this.initialState = initialState;
        this.everyStateIdToState = buildStateIdToState(initialState, continuingStates);
    }

    private Map<Integer, State> buildStateIdToState(
                                    InitialState state, 
                                    Set<ContinuingState> continuingStates) {

        Set<State> allStates = new HashSet<>(continuingStates.size() + 1);
        allStates.add(state);
        allStates.addAll(continuingStates);
        return allStates.stream()
                .collect(Collectors.toMap(
                        State::id,
                        Function.identity()));
    }

    public ContextAndOutput initiate(Input input) {
        return initialState.buildInitial(input);
    }

    public ContextAndOutput continuing(StorableContext context, Input input) {
        State currentState = everyStateIdToState.get(context.getStateId());
        return currentState.goContinuing(context, input);
    }
}

So, if a Transition is unique to a source and destination State, I have it parameterized on the type of the source State's context, so that it can do the transition of type from source State's context to destination State's input.

Here is the issue: in this way, the Transition has to have the destination State as part of the constructor such that it knows what object to call to provide input to. However, State also has to have Transition as part of its constructor so that it can determine which one to follow next. If it matters, I'd also like the ability to create 'global' Transitions that can be taken from any state, that will do some work and then drop back into the existing state.

The issue is demonstrated if I try to have two States and two Transitions, one for each direction:

// Can't give this a Transition back to State0
State1 state1 = new State1(Collections.emptyList()); 

List<Transition<Context0>> zerosOutboundTransitions = 
    Collections.singletonList(new ZeroToOne(state1));

//List<Transition<Context0>> onesOutboundTransitions =   
    Collections.singletonList(new OneToZero(state0));

Set<ContinuingState> continuingStates = ImmutableSet.of(state1);

InitialState initialState = new State0(zerosOutboundTransitions);

I'm looking for some help in either a design pattern or strategy for avoiding or handling this circular dependency, or how I should go about thinking about this design. I have taken a few attempts at different strategies here and am at a bit of a loss. I'd like to enforce as much structure through type safety as I can without losing much flexibility and am struggling to find a "great" solution. Thanks!

Edit: I understand that I COULD force a circular dependency like this, but I'm trying to figure out how I could change the design to not require this circular dependency, as they have quite a few downsides:

// Define the states
State0 initialState = new State0();
State1 state1 = new State1();

// Define the transitions
List<Transition<Context0>> zerosOutboundTransitions = 
    Collections.singletonList(new ZeroToOne(state1));

List<Transition<Context1>> onesOutboundTransitions = 
    Collections.singletonList(new OneToZero(initialState));

// Inform the states of the transitions they may use
initialState.setTransitions(zerosOutboundTransitions);
state1.setTransitions(onesOutboundTransitions);

Best Answer

... my question is more around how I should change the design to avoid needing this circular dependency. – Jordan

One method I've seen is to have each state construct the next state. That works but feels like it's abusing the garbage collector. Here's a method that lets you bounce back and forth from two immutable states.

interface State {
    boolean process(Context context);
}

enum States implements State {
    A {
        public boolean process(Context context) {
            System.out.println(States.A);
            context.setState(States.B);
            return true;
        }
    }, B {
        public boolean process(Context context) {
            System.out.println(States.B);
            context.setState(States.A);
            return true;
        }
    }
}

class Context{
    State state;

    public Context(State state) {
        this.state = state;
    }

    public State getState() {
        return state;
    }

    public void setState(State state) {
        this.state = state;
    }
}

class Processor {

    public void process(Context context) {
        while(context.getState().process(context));
    }
}

public class EntryPoint {
    public static void main(String[] args) {
        Processor p = new Processor();
        Context cd = new Context(States.A);
        p.process(cd);
    }
}

Inspired by this

Related Solutions

C# – Passing data between concrete states

I think you may be getting a little bogged down in the English meaning of state, when compared to the State Pattern (or Finite-State Machine, which is really a diagrammatic representation of a State Pattern). Both are appropriate here, but they shouldn't be confused.

The State Pattern is something which should, given various common stimuli, operate on the game state differently at different times in the game. So, as you've rightly concluded, the lobby stage (which I'm assuming to be while people are joining a game) is a State in that context.

The game state is a list of players, pieces, cards, dice, whatever else, and all the information required to simulate them. You might want to call that the context.

Each State should receive a UserClicked message from the application which receives the context and coordinates or area clicked and should operate on those accordingly. The information that you are trying to give ownership of to the State object does not belong there, it belongs in the game itself, alongside the State.

The state may also have a UserPressedKey method, a TimerTicked method or any other kind of stimulus on which it should act. But each of these should act on the game state rather than being the game state.

One important method of the State will be ScreenRefresh, which will draw the context for the user.

Here is a very rough example:

abstract class ApplicationState {

    void Begin(GameContext context);
    void UserClicked(GameContext context, int x, int y);
    void UserPressedKey(GameContext context, char key);
    void TimerTicked(GameContext context);
    void ScreenRefresh(GameContext context);

    protected void OnStateChanged(ApplicationState newState) {

        // inform interested parties that state has changed,
        // using the observer pattern

    }

}

class LobbyState : ApplicationState
{
    void Begin(GameContext context) {

        context.Players = new User[context.NoOfPlayers];

    }

    void UserClicked(GameContext context, int x, int y) {

        // Find a displayed player box which contains click coords

        int index = -1;
        for (i=0; i < context.Players.Length; i++) {
            if (PlayerBox[i].Contains(x, y)) {
                index = i;
            }
        }

        if (index > -1) {

            if (context.Player[index] == null) {
                context.Player[index] = context.ActivePlayer;
            } else if (context.Player[index] == context.ActivePlayer()) {
                context.Player[index] = null;
            } else {
                ErrorSound.Play();
            }

        } else if (CloseIcon.Contains(x, y)) {

            OnStateChanged(new ExittingState());

        } else {

            ErrorSound.Play();

        }

    }

    void UserPressedKey(GameContext context, char key) {

         if (key = 'J' or key = 'j') {

             if (! context.AddPlayerRandomly(context.ActiveUser)) {
                 ErrorSound.Play();
             }

             if (context.GameIsNowFull()) {
                 OnStateChanged(new InitializingState());
             }

         } else if key = Esc {

             if (!context.RemovePlayer(context.ActiveUser)) {
                 ErrorSound.Play();
             }

         } else {

             ErrorSound.Play();

         }

    }

    void TimerTicked(GameContext context) {

        // there is no use for a game timer while
        // we're trying to fill the game, but you
        // want one to tick anyway, because the
        // application doesn't know which state
        // it is in.

    }

    void ScreenRefresh(GameContext context) {

       DrawPlayerBoxes(context.Screen, context.Players);
       DrawExitIcon(context.Screen);

    }

}

class InitializingState : ApplicationState {

    private double waitSpinnerAngle = 0;

    void Begin(GameContext context) {

        context.RandomizePlayOrder();
        context.ShuffleCards();

        // all other game initialization rules here

        OnContextChanged(new PlayerUpState(context.Players[0]));

    }

    void UserClicked(GameContext context, int x, int y) {

        // Not responding to user input for a moment
        ErrorSound.Play();

    }

    void UserPressedKey(GameContext context, char key) {

        // Not responding to user input for a moment
        ErrorSound.Play();

    }

    void TimerTicked(GameContext context) {

        waitSpinnerAngle += 0.05;
        if (waitSpinnerAngle > 1) waitSpinnerAngle = 0;

    }

    void ScreenRefresh(GameContext context) {

         DrawWaitSpinner(waitSpinnerAngle);

    }

}

See where I'm going with this? The Application itself is then as simple as setting the initial State, hooking a listener into the OnStateChanged event and calling Begin. When the listener hears that the event is called, unhook your old State, hook in the new one, and call Begin again.

Everything else is triggered by events from the mouse, keyboard or timer, passed directly to the current State without knowledge of which State the game is currently in. If you are running this game across a network then you will also need an event for changes of state received from other players.

Everything in your State and Context is now very unit-testable and separation of concerns are observed. Although, you may want to refactor that LobbyState#UserClicked method a bit, among other things.

Remember, this is just a free example and you get what you paid for it. Don't try to apply it directly to your game. Just use it to understand how the State Pattern should work in the context of a game.

Object-oriented – Finite state machine menu design

Probably the best way to implement FSMs in OOP languages is sticking to the State Design Pattern

That pattern provides a general structure to design and implement FSMs, dividing the FSM in two "sides": The context and the state, being the state a hierarchy of all the different states the context can have (a context can only have a very limited amount of states at a single time, usually only one). Then, the state transitions are modeled, usually either in the client (the class that uses the context will decide when to explicitly transition to a new state, making the context instance behave differently), or in the states (when each state is responsible of checking the transition conditions and perform the actual transition). The first approach has the advantage of a lower cohesion between states, making them reusable in implementations of other FSMs, but with a much more complex client class. The second approach has the opposite side effects.

In your case, I'd model System with the role of Context, State with the role of State, and Menu (and its submenus) as different ConcreteStates. If StepSequencer and SamplePad are to be exclusive of a single menu/submenu, they'd be attributes of that individual state. Otherwise, (i.e., shared or persistent between menus), as attributes of System. That decision will depend on your actual needs.

Now, about your design (and this is a little off-topic), StepSequencer and SamplePad don't look like actual states (neither by their uses nor by their names). Personally, I'd bet it's that way just because their interface is apparently identical to that of states (def buttonPress(self, numberButton):). If that's the reason, and you did it that way to avoid duplicating code, don't. It's okay to have code duplicated in certain occasions (e.g., when the base interface is likely to change in different directions over time, as stated by Robert C. Martin in his book Clean Architecture). Keep this in mind and consider deriving them from a different base class other than State.

Best Answer

Related Solutions

C# – Passing data between concrete states

Object-oriented – Finite state machine menu design

Related Topic