The Superpower of Finite State Machines

In this article I’m going to describe one of the most underused computer science concepts: Finite State Machine (FSM). Unlike many other higher-level abstract concepts, FSMs are practically useful and don’t involve very steep learning curve (in most cases). Therefore, in my opinion, all software developers should know and use them.

Login Screen Example

Consider this controller which represents a fairly standard login screen:

public class LoginController implements
        LoginViewMvc.Listener,
        LoginUseCase.Listener {

    private final UserStateManager mUserStateManager;
    private final LoginUseCase mLoginUseCase;
    private final ScreensNavigator mScreensNavigator;
    private final DialogsNavigator mDialogsNavigator;

    private LoginViewMvc mViewMvc;

    public LoginController(UserStateManager userStateManager,
                           LoginUseCase loginUseCase,
                           ScreensNavigator screensNavigator,
                           DialogsNavigator dialogsNavigator) {
        mUserStateManager = userStateManager;
        mLoginUseCase = loginUseCase;
        mScreensNavigator = screensNavigator;
        mDialogsNavigator = dialogsNavigator;
    }

    public void bindView(LoginViewMvc viewMvc) {
        mViewMvc = viewMvc;
    }

    public void onStart() {
        mViewMvc.registerListener(this);
        mLoginUseCase.registerListener(this);

        if (mUserStateManager.isUserLoggedIn()) {
            mScreensNavigator.toMainScreen();
        } else {
            verifyUserInput();
        }
    }

    public void onStop() {
        mViewMvc.unregisterListener(this);
        mLoginUseCase.unregisterListener(this);
    }

    @Override
    public void onPasswordChanged(String password) {
        verifyUserInput();
    }

    @Override
    public void onUsernameChanged(String username) {
        verifyUserInput();
    }

    private void verifyUserInput() {
        if (mViewMvc.getUsername().length() > 0 && mViewMvc.getPassword().length() > 0) {
            mViewMvc.enableLoginButton();
        } else {
            mViewMvc.disableLoginButton();
        }
    }

    @Override
    public void onLogInClicked() {
        mViewMvc.showProgressIndication();
        mLoginUseCase.loginAndNotify(mViewMvc.getUsername(), mViewMvc.getPassword());
    }

    @Override
    public void onLoggedIn() {
        mViewMvc.hideProgressIndication();
        mScreensNavigator.toMainScreen();
    }

    @Override
    public void onLoginFailed(String errorMessage) {
        mViewMvc.hideProgressIndication();
        mDialogsNavigator.showLoginFailedDialog(errorMessage);
    }
}

The above controller is relatively simple, but it also contains a bug, which is classical for GUI applications. Can you spot it?

Consider the following sequence of method calls: onStart() -> onLogInClicked() -> onStop() -> onStart(). After these methods are called in this specific order, what’s the resulting UI’s state? Well, it depends on whether LoginUseCase completed its internal flow by the time onStart() is called for the second time or not, and whether the flow completed successfully.

If the flow is still active, then the controller will register as a listener during second onStart() and receive either onLoggedIn() or onLoginFailed(String) calls at a later time. That’s business as usual.

However, if the flow completed after onStop() and before second onStart(), the controller will miss the notificaiton about flow’s completion. In this case, if the flow completed successfully, then UserStateManager will reflect that and the app will navigate to main screen. However, if the flow failed, the screen will keep showing progress indication indefinitely. That’s a classical bug.

Login Screen with Finite State Machine

Before I fix the implementation of LoginController, I want to refactor it to a proper Finite State Machine:

public class LoginControllerFsm implements
        LoginViewMvc.Listener,
        LoginUseCase.Listener {

    private enum ScreenState {
        IDLE,
        INVALID_INPUT,
        VALID_INPUT,
        LOGIN_IN_PROGRESS,
        LOGIN_SUCCEEDED,
        LOGIN_FAILED
    }

    private final UserStateManager mUserStateManager;
    private final LoginUseCase mLoginUseCase;
    private final ScreensNavigator mScreensNavigator;
    private final DialogsNavigator mDialogsNavigator;

    private LoginViewMvc mViewMvc;

    private ScreenState mScreenState = ScreenState.IDLE;

    private String mLoginFailureErrorMessage;

    public LoginControllerFsm(UserStateManager userStateManager,
                              LoginUseCase loginUseCase,
                              ScreensNavigator screensNavigator,
                              DialogsNavigator dialogsNavigator) {
        mUserStateManager = userStateManager;
        mLoginUseCase = loginUseCase;
        mScreensNavigator = screensNavigator;
        mDialogsNavigator = dialogsNavigator;
    }

    public void bindView(LoginViewMvc viewMvc) {
        mViewMvc = viewMvc;
    }

    public void onStart() {
        mViewMvc.registerListener(this);
        mLoginUseCase.registerListener(this);

        if (mUserStateManager.isUserLoggedIn()) {
            setNewState(ScreenState.LOGIN_SUCCEEDED);
        } else {
            verifyUserInput();
        }
    }

    public void onStop() {
        mViewMvc.unregisterListener(this);
        mLoginUseCase.unregisterListener(this);
    }

    private void setNewState(ScreenState newState) {
        switch (newState) {
            case VALID_INPUT:
                mViewMvc.enableLoginButton();
                break;
            case INVALID_INPUT:
                mViewMvc.disableLoginButton();
                break;
            case LOGIN_IN_PROGRESS:
                mViewMvc.showProgressIndication();
                break;
            case LOGIN_SUCCEEDED:
                mViewMvc.hideProgressIndication();
                mScreensNavigator.toMainScreen();
                break;
            case LOGIN_FAILED:
                mViewMvc.hideProgressIndication();
                mDialogsNavigator.showLoginFailedDialog(mLoginFailureErrorMessage);
                break;
        }
        mScreenState = newState;
    }

    @Override
    public void onPasswordChanged(String password) {
        verifyUserInput();
    }

    @Override
    public void onUsernameChanged(String username) {
        verifyUserInput();
    }

    private void verifyUserInput() {
        if (mViewMvc.getUsername().length() > 0 && mViewMvc.getPassword().length() > 0) {
            setNewState(ScreenState.VALID_INPUT);
        } else {
            setNewState(ScreenState.INVALID_INPUT);
        }
    }

    @Override
    public void onLogInClicked() {
        mLoginUseCase.loginAndNotify(mViewMvc.getUsername(), mViewMvc.getPassword());
        setNewState(ScreenState.LOGIN_IN_PROGRESS);
    }

    @Override
    public void onLoggedIn() {
        setNewState(ScreenState.LOGIN_SUCCEEDED);
    }

    @Override
    public void onLoginFailed(String errorMessage) {
        mLoginFailureErrorMessage = errorMessage;
        setNewState(ScreenState.LOGIN_FAILED);
    }
}

The main feature of this refactored implementation is that I explicitly declared all controller’s states. In addition, now I manage all the side effects associated with transitions between different states in one place. In essence, by declaring the states and specifying what happens upon transitions between them, I implemented a Finite State Machine inside this controller.

Now, even though the implementation with FSM is longer and a bit more involved, it’s a major step forward in terms of readability. Every developer who will read this code in the future will immediately understand what’s happening on this screen just by reading the declaration of ScreenState enum.

In addition, if I’d design this controller with FSM from the beginning, I’d surely ask myself “should I account for controller’s state in onStart()?”. The answer to this question is “yes” for pretty much any non-trivial FSM.

Fixing the Bug

To fix the bug, I can add a bit of code in controller’s onStart() method and also handle the transition to IDLE state in FSM:

public class LoginControllerFsm implements
        LoginViewMvc.Listener,
        LoginUseCase.Listener {

    private enum ScreenState {
        IDLE,
        INVALID_INPUT,
        VALID_INPUT,
        LOGIN_IN_PROGRESS,
        LOGIN_SUCCEEDED,
        LOGIN_FAILED
    }

    private final UserStateManager mUserStateManager;
    private final LoginUseCase mLoginUseCase;
    private final ScreensNavigator mScreensNavigator;
    private final DialogsNavigator mDialogsNavigator;

    private LoginViewMvc mViewMvc;

    private ScreenState mScreenState = ScreenState.IDLE;

    private String mLoginFailureErrorMessage;

    public LoginControllerFsm(UserStateManager userStateManager,
                              LoginUseCase loginUseCase,
                              ScreensNavigator screensNavigator,
                              DialogsNavigator dialogsNavigator) {
        mUserStateManager = userStateManager;
        mLoginUseCase = loginUseCase;
        mScreensNavigator = screensNavigator;
        mDialogsNavigator = dialogsNavigator;
    }

    public void bindView(LoginViewMvc viewMvc) {
        mViewMvc = viewMvc;
    }

    public void onStart() {
        mViewMvc.registerListener(this);
        mLoginUseCase.registerListener(this);

        switch (mScreenState) {
            case LOGIN_IN_PROGRESS:
                if (mLoginUseCase.isBusy()) {
                    // login flow hasn't completed yet, so just wait for the result
                } else {
                    // login flow completed and we missed the notification
                    if (mUserStateManager.isUserLoggedIn()) {
                        setNewState(ScreenState.LOGIN_SUCCEEDED);
                    } else {
                        setNewState(ScreenState.IDLE);
                    }
                }
                break;
            default:
                verifyUserInput();

        }
    }

    public void onStop() {
        mViewMvc.unregisterListener(this);
        mLoginUseCase.unregisterListener(this);
    }

    private void setNewState(ScreenState newState) {
        switch (newState) {
            case IDLE:
                mViewMvc.hideProgressIndication();
                verifyUserInput();
            case VALID_INPUT:
                mViewMvc.enableLoginButton();
                break;
            case INVALID_INPUT:
                mViewMvc.disableLoginButton();
                break;
            case LOGIN_IN_PROGRESS:
                mViewMvc.showProgressIndication();
                break;
            case LOGIN_SUCCEEDED:
                mViewMvc.hideProgressIndication();
                mScreensNavigator.toMainScreen();
                break;
            case LOGIN_FAILED:
                mViewMvc.hideProgressIndication();
                mDialogsNavigator.showLoginFailedDialog(mLoginFailureErrorMessage);
                break;
        }
        mScreenState = newState;
    }

    @Override
    public void onPasswordChanged(String password) {
        verifyUserInput();
    }

    @Override
    public void onUsernameChanged(String username) {
        verifyUserInput();
    }

    private void verifyUserInput() {
        if (mViewMvc.getUsername().length() > 0 && mViewMvc.getPassword().length() > 0) {
            setNewState(ScreenState.VALID_INPUT);
        } else {
            setNewState(ScreenState.INVALID_INPUT);
        }
    }

    @Override
    public void onLogInClicked() {
        mLoginUseCase.loginAndNotify(mViewMvc.getUsername(), mViewMvc.getPassword());
        setNewState(ScreenState.LOGIN_IN_PROGRESS);
    }

    @Override
    public void onLoggedIn() {
        setNewState(ScreenState.LOGIN_SUCCEEDED);
    }

    @Override
    public void onLoginFailed(String errorMessage) {
        mLoginFailureErrorMessage = errorMessage;
        setNewState(ScreenState.LOGIN_FAILED);
    }
}

This should fix the erroneous behavior.

Finite State Machine and Process Death

Since the refactoring to FSM resulted in addition of explicit variable for screen’s state, it should immediately trigger the question: “should this state be persisted over process death?”. In my opinion, the default answer for “screen” FSMs should be “yes”. Therefore, unless you have special reasons for clearing the state of this screen after process death, you should implement support for save & restore in your code.

In this case, I’d do something like this:

public Serializable getInstanceState() {
    return mScreenState;
}

public void restoreInstanceState(Serializable state) {
    mScreenState = (ScreenState) state;
}

Then call these methods from the enclosing Activity or Fragment.

Simple and Complex Finite State Machines

The implementation of a Finite State Machine that you saw above is relatively simple. You can see another simple example in the context of a full project in this tutorial app that I wrote for my architecture course.

More involved components might call for FSM implementations which use polymorphic sets of classes to represent the states (in which case, Kotlin’s sealed classes can come in very handy). In other cases, you might want to use so-called Hierarchical FSMs. There is also a distinction between Mealy and Moore types of FMSs, and, probably, more nuances and complications. I’m pretty sure there are entire books written about FSMs, so, please, don’t assume that this article exhausted this topic.

However, you can go surprisingly long way with just the basics outlined in this post. For example, I implemented a custom media player for one of my clients using this simple FSM (approximately, don’t remember the exact list of states):

private enum PlayerState {
    IDLE,
    PLAYING,
    PREVIEW_ONE_FRAME,
    PAUSED,
    STOPPING,
    STOPPED
}

Therefore, you can absolutely use the tools you learned in this post in your professional projects.

Scope of Applicability of Finite State Machines

Just like with any other tool, FSMs aren’t golden hammer. If you abuse them, or use incorrectly, you’ll pay the price.

I wouldn’t use FSMs for components that have just one or two states. For example, imagine an info screen with a button that simply takes the user to another screens. Formal FSM would probably be an overkill there. On the other hand, I’d consider a proper FSM for any component that has three or more states. In my experience, extracting a full formal FSM for components that have five or more states has always been a very good idea.

The general rule of thumb with FSMs is: the more states a component has, the higher ROI of using a FSM there.

Conclusion

Finite State Machines are extremely powerful abstractions. While I’m sure that there are books about FSMs out there, even the simple examples you saw in this articles can be extremely useful in professional projects.

Let me tell you a story in this context.

I wrote an application once which implemented extremely complex multimedia features. Something really special. One software development agency which took a shot at this project before me had to refund the client after six months of development. I saw their code. They made the right call with the refund because they haven’t been on track to completing this project.

To implement the core functionality of the app, I decided to implement a formal FSM using TDD. I realized that this multimedia player is going to be complex, but, boy, did I underestimate the complexity. The final implementation involved hierarchical FSM with more than 30 states! If I wouldn’t use FSM in this player (and TDD), I would probably still be debugging that app today. Not a good outcome when you charge fixed price.

As always, thanks for reading and you can leave your comments and questions below.

4 thoughts on “The Superpower of Finite State Machines”

Leave a Comment

Subscribe for new posts