Trouble with circular dependency in state machine design

Question

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);

Answer 1

... 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

Answer 2

This makes no sense:

A a = new A(b);

B b = new B(a);

The fundamental problem here is you can't build a circular object graph if each object learns what it points to in a constructor. You need at least one that allows for a setter rather than constructor so it can exist before it knows what to point to.

A a = new A();

B b = new B(a);

a.setRef(b);

Now you have a circular reference.

Keep in mind circular references have drawbacks.