2
\$\begingroup\$

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);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ I just saw that the log4j logger, added for debugging, is still there. If I would share this code, I would change it to slf4j \$\endgroup\$ – stuXnet May 29 '15 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.