10.5: State machine (Advanced Internet Programming)

Problem

In the team shopping list, individual items change their state according to a complex set of rules that have been encoded using if-statements and boolean variables (see src/server/item.js):

// An item in the initial state can be made ready to purchase
readyToPurchase() {
    if (!this.isDeleted && !this.isBought) {
        this.isBuying = true;
        return true;
    } else {
        return false;
    }
}

// An item that is ready to purchase can be purchased
// Once purchased, it should no longer be seen by users
purchase() {
    if (this.isBuying) {
        this.isBuying = false;
        this.isBought = true;
        expenseService.createExpense(this.description, this.quantity);
        return true;
    } else {
        return false;
    }
}

// An item in the initial state can be permanently deleted
// Once deleted, it should no longer be seen by users
delete() {
    if (!this.isDeleted && !this.isBuying && !this.isBought) {
        notificationService.notifyDeletedItem(this.description);
        this.isDeleted = true;
        return true;
    } else {
        return false;
    }
}

While this code can still be understood, it is in danger of becoming unmanageable. In particular, as a developer, there are two concerns:

It isn’t apparent if I have addressed every possibility. How can I be sure that I haven’t missed a vital branch in the if-statements?
Adding more states and actions will add additional complexity.

Solution

State machines are a mathematical idea in which a system is modeled as a graph comprising:

Vertices, representing the separate states of the system
Edges, representing valid transitions between states

A visual representation of this graph in a ‘state diagram’ is perhaps the best way to understand a state machine.

For example, take the original item-management rules:

Users can buy items and then record those items as purchased
Users can delete items
Users can identify items that they’re currently in the process of buying

These rules translate into the following state diagram:

This diagram has the advantage of making all the valid transitions more obvious. It also reveals omissions.

For example, in this state diagram, a locked item can never be unlocked. Also, it doesn’t clarify the outcome of deleting a purchased item. Creating a state diagram reveals possible bugs and illuminates gaps in the system requirements.

As the system designer, I might decide that deletion does nothing and that locked items can also be unlocked (but purchased items cannot be unpurchased).

This results in a revised state diagram:

Implementation

State machines are a mathematical concept with many translations into code. For example, XState is a JavaScript framework for implementing state machines. The implementation of reducers in the popular Redux library (often used in React development) is similar to a state machine.

However, no framework is needed to translate a state diagram into code. First, declare separate states as constants. ^[1] State transitions are then handled using a switch or if statement.

For example, in the following code, each event is translated into a function call and the states are selected using a switch statement:

const STATE_ITEM = 'STATE_ITEM';
const STATE_LOCKED = 'STATE_LOCKED';
const STATE_PURCHASED = 'STATE_PURCHASED';
const STATE_DELETED = 'STATE_DELETED';

...

delete() {
    switch (this.state) {
        case STATE_ITEM:
            // Notify others and delete
            notificationService.notifyDeletedItem(this.description);
            this.state = STATE_DELETED;
            break;

        case STATE_LOCKED:
        case STATE_PURCHASED:
        case STATE_DELETED:
            // Ignore deletion when locked, purchased or already deleted
            break;

        default:
            throw new Error(`Unrecognized state: ${this.state}`);
    }
}

The code is slightly longer. However, it lends itself to verification by direct comparison with the state diagram.

In some situations, it may be useful to reify the event itself as a value. In such cases, the state machine might be wrapped into a single handle function:

const STATE_ITEM = 'STATE_ITEM';
const STATE_LOCKED = 'STATE_LOCKED';
const STATE_PURCHASED = 'STATE_PURCHASED';
const STATE_DELETED = 'STATE_DELETED';

const EVENT_READY = 'EVENT_READY';
const EVENT_PURCHASE = 'EVENT_PURCHASE';
const EVENT_DELETE = 'EVENT_DELETE';
const EVENT_CANCEL = 'EVENT_CANCEL';

...

handle(event) {
    switch (event) {
        case EVENT_READY:
            handleReadyEvent();
            break;

        case EVENT_PURCHASE:
            handlePurchaseEvent();
            break;

        case EVENT_DELETE:
            handleDeleteEvent();
            beak;

        case EVENT_CANCEL:
            handleCancelEvent();
            break;

        default:
            throw new Error(`Unrecognized event: ${event}`);
    }
}

handleDeleteEvent() {
    switch (this.state) {
        case STATE_ITEM:
            // Notify others and delete
            notificationService.notifyDeletedItem(this.description);
            this.state = STATE_DELETED;
            break;

        case STATE_LOCKED:
        case STATE_PURCHASED:
        case STATE_DELETED:
            // Ignore deletion when locked, purchased or already deleted
            break;

        default:
            throw new Error(`Unrecognized state: ${this.state}`);
    }
}

...

// Not shown: handlers for the other events

...

Reflection: Real-world scenarios

What are examples of real-world scenarios that would benefit from being modeled as a state machine?

Reflection: Reified events

Adding a handle(event) to the Item class is unnecessary in the current project.

When and why would it be useful to use an event object, such as EVENT_DELETE with a handle(event) method, rather than calling delete() directly?