Finite State Machine supporting shortest path transitions

Question

In our automated test framework, written in Java 8, there are different entities representing test data, having different states and transitions between them.

To model this behavior, I started to implement a simple finite state machine (or at least what I understand as a FSM).

The idea to use it would be like this:

public class Example {
    private enum Human {
        UNBORN, BORN, KID, ADULT, DEAD
    }

    @Test
    public void test() {
        StateMachine<Human> fsm = StateMachineBuilder.create(Human.class)
                .from(Human.UNBORN).to(Human.BORN).to(Human.DEAD, this::died)
                .from(Human.BORN).to(Human.KID).to(Human.DEAD, this::died)
                .from(Human.KID).to(Human.ADULT).to(Human.DEAD, this::died)
                .from(Human.ADULT).to(Human.DEAD).startAt(Human.UNBORN);

        // dying as an unborn :(
        fsm.go(Human.DEAD);

        // going from UNBORN to BORN, KID, ADULT
        fsm.reset();
        fsm.go(Human.ADULT);
    }

    private void died() {
        System.out.println("Oh no :(");
    }
}

The reason I chose to write an implementation by myself was that ie. stateless4j doesn't support going directly from UNBORN to ADULT, because it doesn't look for a shortest path.

Although I'm thankful for every feedback I can get, I'm mostly thinking about the following points:

• Is my state machine a state machine? The input it receives aren't any triggers or so, but a target state it should transition to.
• Is my builder really a builder?
• Is there a simple way to not allow multiple from calls like builder.from(KID).from(ADULT)? I know I could introduce another class as return value for the first call to form, and using TransitionAdder only for to, but it seems like an overkill.
• Are the names okay? In particular, I'm unhappy with TransitionAdder.
• Have I missed important information in the Javadoc?
• shortestRoute.get().add(0, from); - should I use LinkedLists if I want to do this, or is it okay with ArrayLists in this case?
• If I would share this and deploy it in a central maven repository - should I use a logger (if so, I would use slf4j instead of log4j) or none at all?
• Is it okay to use Runnable in this case, or should I introduce my own functional interface like Transition?

StateMachine.java

package fsm;

import com.google.common.collect.Table;
import org.apache.log4j.Logger;

import java.util.*;
import java.util.stream.Collectors;

/**
 * An implementation of a state machine able to choose the shortest path between two states.
 *
 * @param <S> the Enum describing the possible states of this machine
 */
public class StateMachine<S> {
    private static final Logger log = Logger.getLogger(StateMachine.class);

    private final Table<S, S, List<Runnable>> transitions;

    private final S initialState;
    private S currentState;
    private int transitionsDone = 0;

    StateMachine(Table<S, S, List<Runnable>> transitions, S initialState) {
        this.transitions = Objects.requireNonNull(transitions);
        this.initialState = currentState = Objects.requireNonNull(initialState);
    }

    /**
     * Tries to look for the shortest path from {@code currentState} to {@code state} and executing all registered
     * transition actions.
     *
     * @param state the state to go to
     * @return this
     * @throws IllegalArgumentException if there is no path to {@code state}
     */
    public StateMachine<S> go(S state) {
        if (currentState != state) {
            final List<Runnable> runnables = transitions.get(currentState, state);

            if (runnables != null) {
                // there's a direct path

                log.trace("Going to state " + state);
                runnables.forEach(Runnable::run);

                currentState = state;
                transitionsDone++;
            } else {
                // check if there is a path
                List<S> intermediaryStates = getShortestStatePathBetween(currentState, state);

                if (intermediaryStates != null) {
                    // the first item is the same as currentState, but since we ignore going to the current state,
                    // we don't have to strip it
                    intermediaryStates.forEach(this::go);
                } else {
                    throw new IllegalArgumentException("There is no valid transition!");
                }
            }
        }

        return this;
    }

    /**
     * Returns the current state the machine is in
     *
     * @return the current state of the machine
     */
    public S getCurrentState() {
        return currentState;
    }

    /**
     * Returns how many transitions were done by this machine.
     * <p>
     * Most used for debugging purpouses.
     *
     * @return an integer greater or equal to 0, describing how many transitions were done
     */
    public int getTransitionsDone() {
        return transitionsDone;
    }

    /**
     * Resets the current state to the state the machine was created with, without doing any transitions.
     * <p/>
     * Also, {@link StateMachine#getTransitionsDone()} will return 0 again after {@code reset}
     */
    public void reset() {
        currentState = initialState;
        transitionsDone = 0;
    }

    /**
     * Looks for the shortest available state path between the states {@code from} and {@code to}
     * <p>
     * Given the transitions {@code A -&gt; B -&gt; C -&gt; D -&gt; E}, a call to
     * {@code getShortestStatePathBetween(B, D)} will return the list {@code [B, C, D]}
     *
     * @param from the state to start looking
     * @param to   the state to find a path to
     * @return either a list describing the shortest path from {@code from} to {@code to} (including themselves),
     * or null if no path could be found
     */
    private List<S> getShortestStatePathBetween(S from, S to) {
        final Set<S> reachableStates = getKeysWithoutValue(transitions.row(from));

        if (reachableStates.contains(to)) {
            final List<S> l = new ArrayList<>();
            l.add(from);
            l.add(to);
            return l;
        }

        final List<List<S>> routes = new ArrayList<>();

        for (S reachableState : reachableStates) {
            final List<S> statesBetween = getShortestStatePathBetween(reachableState, to);

            if (statesBetween != null) {
                routes.add(statesBetween);
            }
        }

        final Optional<List<S>> shortestRoute = getShortestList(routes);

        if (shortestRoute.isPresent()) {
            shortestRoute.get().add(0, from);
            return shortestRoute.get();
        } else {
            return null;
        }
    }

    protected static <T> Set<T> getKeysWithoutValue(Map<T, ?> map) {
        return map.entrySet().stream().filter(e -> e.getValue() != null).map(Map.Entry::getKey).collect(Collectors
                .toSet());
    }

    protected static <T> Optional<List<T>> getShortestList(List<List<T>> lists) {
        return lists.stream().min((l1, l2) -> l1.size() - l2.size());
    }
}

StateMachineBuilder.java

package fsm;

import com.google.common.collect.ArrayTable;
import com.google.common.collect.Table;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;

/**
 * Configuration class for creating enum based StateMachines.
 * <p>
 * To create a builder, call the static factory method {@link StateMachineBuilder#create(Class)}
 * <p>
 * Configuration is fluently done using {@link StateMachineBuilder#from(Enum)} and
 * {@link fsm.StateMachineBuilder.TransitionAdder#to(Enum)}.
 * <p>
 * Example usage:
 * <pre>
 *     StateMachineBuilder&lt;SomeEnum&gt; builder = StateMachineBuilder.create(SomeEnum.class);
 *
 *     builder.from(SomeEnum.A).to(SomeEnum.B)
 *     .from(SomeEnum.B).to(SomeEnum.C).to(SomeEnum.D)
 *     .from(SomeEnum.A).to(SomeEnum.C, () -&gt; System.out.println(&quot;Transition to C&quot;);
 *
 *     StateMachine&lt;SomeEnum<&gt; stateMachine = builder.startAt(SomeEnum.A);
 * </pre>
 *
 * @param <S> the used Enum
 */
public class StateMachineBuilder<S extends Enum<S>> {
    private final Table<S, S, List<Runnable>> transitions;

    private StateMachineBuilder(S[] validStates) {
        final List<S> valueList = Arrays.asList(validStates);
        transitions = ArrayTable.create(valueList, valueList);
    }

    public static <T extends Enum<T>> StateMachineBuilder<T> create(Class<T> e) {
        return new StateMachineBuilder<>(e.getEnumConstants());
    }

    public TransitionAdder from(S state) {
        return new TransitionAdder(transitions.row(state));
    }

    /**
     * Creates a new {@link StateMachine} using the current configuration
     *
     * @param initialState the starting state of the state machine
     * @return a new StateMachine
     */
    public StateMachine<S> startAt(S initialState) {
        return new StateMachine<>(transitions, initialState);
    }

    public class TransitionAdder {
        private final Map<S, List<Runnable>> transitionsTo;

        private TransitionAdder(Map<S, List<Runnable>> transitionsTo) {
            this.transitionsTo = transitionsTo;
        }

        /**
         * Creates a new transition to {@code state}, executing the transition {@code transition} when
         * switching the state to it
         *
         * @param state the state to create the transition to
         * @param transition a functional interface which should be executed when transitioning to {@code state}
         */
        public TransitionAdder to(S state, Runnable transition) {
            List<Runnable> runnables = transitionsTo.get(state);

            if (runnables == null) {
                runnables = new ArrayList<>();
                transitionsTo.put(state, runnables);
            }

            runnables.add(transition);

            return this;
        }

        /**
         * Creates a new transition to {@code state} without an action
         *
         * @param state the state to create the transition to
         */
        public TransitionAdder to(S state) {
            List<Runnable> runnables = transitionsTo.get(state);

            if (runnables == null) {
                runnables = new ArrayList<>();
                transitionsTo.put(state, runnables);
            }

            return this;
        }

        /**
         * @see StateMachineBuilder#from(Enum)
         */
        public TransitionAdder from(S state) {
            return StateMachineBuilder.this.from(state);
        }

        /**
         * @see StateMachineBuilder#startAt(Enum)
         */
        public StateMachine<S> startAt(S initialState) {
            return StateMachineBuilder.this.startAt(initialState);
        }
    }
}

Answer 1

Runnable Review

From Reference Docs:

When an object implementing interface Runnable is used to create a thread, starting the thread causes the object's run method to be called in that separately executing thread.

This goes completely against the run-to-completion model of a state machine. Runnable is implied to run in a dedicated thread, while your state machine operations (like transitions) are meant to run in the main state machine thread. So I suggest to create a custom ITransition interface.

State Machine Review

Is my state machine a state machine? The input it receives aren't any triggers or so, but a target state it should transition to.

There is no single formal definition of a state machine. Different specifications such as Mealy, Moore and UML exist. And even within these specifications, you are not limited to using formal constraints. So yes, your state machine is a state machine, as you have states, transitions and a run-to-completion flow go. In fact, your state machine is a subset of a Mealy machine, where transitions are the driver for state changes. This can be seen in go:

log.trace("Going to state " + state);
runnables.forEach(Runnable::run);   // Mealy flow with transitions
currentState = state;

If you would have picked a Moore machine instead, go would have looked like this:

log.trace("Going to state " + state);
currentState.exit();     // Moore machine Exit old state
currentState = state;
currentState.enter();    // Moore machine Enter new state

I do have a couple of considerations to make this state machine more robust:

Error Handling

When no valid transition is found, you throw IllegalArgumentException("There is no valid transition!") leaving the state machine in the current state. Who should handle the error? In a run-to-completion model, it is expected that each run step completes, even if an error occurs. I would opt adding an error state with a default transition to this state on any error in any other state.

Transition Integrity

When transitioning, you are calling the transition behavior runnables.forEach(Runnable::run) be careful that anything may happen in these operations, including throwing errors (already discussed in the previous point) and other state changes (calling go inside a transition). This latter flow is violating the flow integrity, as the current transitions get put on hold, new transitions take place, and then the remaining previous (obsolete) transitions continue, resulting in unwanted transitions. This could be solved by adding a boolean isTransitioninig in go and throwing an error when go is called from within another ongoing transition.

---

Builder Review

Is my builder really a builder?

You have designed a fluent API for building a state machine with its transitions. This definately is a builder pattern.

StateMachineBuilder
    .create(Human.class)
        .from(Human.UNBORN)
        .to(Human.DEAD, this::died);

I would indent and nest each builder method, though, to make the hierarchy more clear.

Is there a simple way to not allow multiple from calls like builder.from(KID).from(ADULT)? I know I could introduce another class as return value for the first call to form, and using TransitionAdder only for to, but it seems like an overkill.

It's unfortunate you find your own suggestion overkill. You should have indeed split the TransitionAdder up in a TransitionFromBuilder and TransitionToBuilder. This way, you could preserve integrity by removing from() from TransitionFromBuilder and having to() return a TransitionFromBuilder. You could always create a public reference back to the previous level. From TransitionToBuilder you should be able to go back to TransitionFromBuilder and from TransitionFromBuilder back to StateMachineBuilder.

---