The Super State Design Pattern

Combining state design pattern and finite state machine

[TL;DR]

The state design pattern is used to encapsulate the behavior of an object depending on its state. The state implementation reflects the behavior the object should have when being in that state.

A finite state machine describes a computational machine that is in exactly one state at any given time. It can change from one to another state in response to some input / trigger / event.

The emphasis of the state design pattern is on encapsulation of behavior to create reusable, maintainable components (the states). The focus of the finite state machine is on states and their transitions (captured by the state diagram) but not on the actual behavior (that’s an implementation detail).

This article describes how these two concepts can be combined by using a finite state machine to describe and manage the states and their transitions for an object that delegates behavior to state objects using the state design pattern.

State Design Pattern

The state design pattern is one of twenty-three design patterns documented by the Gang of Four. It’s a strategy pattern set to solve these two main problems:

• An object should change its behavior when its state changes.
• State-specific behavior/code should be defined independently.

This is achieved by moving the state specific code into State classes/objects. The main class (called Context) keeps track of its state and delegates the behavior to the State objects. The following diagram shows the relation between the Context and the State objects:

• The Context holds a reference to its current State and delegates the execution of request() to state.handle().
• Each State object implements the handle() function. This is the state-specific behavior that gives us encapsulation and reuse.

The following code shows a simplified and not very generic implementation of the pattern (all code samples are in Kotlin and should be easy to understand regardless of your preferred language):

class Context(private var state: State) {
    fun print(text: String) = state.handle(text)
}

interface State {
    fun handle(text: String)
}

class UpperCaseState : State {
    override fun handle(text: String) = println(text.toUpperCase())
}

class LowerCaseState : State {
    override fun handle(text: String) = println(text.toLowerCase())
}

The Context class knows its internal state (state variable) and delegates the call to the print() function to State.handle(). The two concrete implementations of the State interface simply print the passed in text in upper/lower case.

A more conventional implementation (not using the state design pattern) would do something like this:

fun printConventional(text: String) {
    when(state) {
        is UpperCaseState -> println(text.toUpperCase())
        is LowerCaseState -> println(text.toLowerCase())
    }
}

You’ll find a very similar example (Java based) here: https://en.wikipedia.org/wiki/State_pattern. One difference you’ll notice is that the Wikipedia example also triggers state transitions, e.g.

context.setState(new LowerCaseState());

This brings us to “gaps” in the pattern. Its focus is, as mentioned above, on encapsulating state specific behavior, not on managing state and their transitions and so most implementations show only a basic way to manage and alter state, e.g.

• https://blogs.oracle.com/javamagazine/the-state-pattern: each State sets the new State (light.change(new Green(light));).
• https://medium.com/cocoaacademymag/how-use-state-design-pattern-to-create-a-stateful-viewcontroller-78c224781918: the Context exposes setter methods to set the State.
• https://www.baeldung.com/java-state-design-pattern: each State is responsible for setting the previous and/or next State.

For some use cases this might be good enough. Some even argue that with the state design pattern, there’s no need for finite state machines:

Using a State Design Pattern over Switch and If statements and over State Machines is a powerful tool that can make your life easier and save your employer time & money. It’s that simple.

https://www.codeproject.com/Articles/509234/The-State-Design-Pattern-vs-State-Machine

Obviously I disagree with this statement. Let me explain why.

Finite State Machine

A finite state machine is an abstract machine that can be in exactly one of a finite number of states at any given time. The state machine can change from one state to another in response to some external inputs. The change from one state to another is called a transition.

Typically a concrete state machine is modeled using a state diagram like the following one describing a coin operated turn-style:

Sometimes state transition tables are used:

(more ways to model state diagrams: https://en.wikipedia.org/wiki/State_diagram)

State machines are very powerful when dealing with a program that has a complex workflow with lots of conditional code (if then else, switch statements, loops etc.). State machines help us to:

• Model the control flow of the program using states, external inputs and transitions.
• Separate the control flow from the implementation of the states.
• Enforce rigidness in terms of possible states and triggers that lead to state transitions. A traffic light state machine can make sure that setting a red light to yellow leads to an error (because red lights typically turn green).

The last example mentions using a state machine for traffic light control. Most of us would probably consider this a good academic example because it’s very simple. After all we only have the transitions green - yellow - red - green, right?.

As a matter of fact traffic light control is very complex as you can see here https://en.wikipedia.org/wiki/Traffic-light_signalling_and_operation:

• Flashing red to signal stop.
• Flashing yellow to signal caution (but only in Australia and the US).
• Red and green simultaneously to signal turn prohibition:
  In Quebec, a signal may display a green straight arrow alone, usually for 5 to 9 seconds, and then the full green or right turn arrow.
  Green arrows appear with the red ball with the red ball is always illuminated -> intersection of Delaware Avenue at Harrison Street in Wilmington, Delaware, and at the intersection of West 3rd Street and Mesaba Avenue in Duluth, Minnesota).
• Protected turn:
  Green arrow indicates protected movement in the direction of the arrow (Canada + US).
  In Ireland and the UK, a right arrow may sometimes be displayed alongside a green light to indicate that oncoming traffic has been stopped and that it is safe to turn right.
  In Japan, a green arrow with the circular green is never shown. Instead, green arrows must be shown with the circular red.
• You get the picture…

Imagine the nightmare to model/implement these rules without a state machine or the state design pattern…

State Design Pattern vs. State Machine

The state design pattern and finite state machines have similarities (not just because they have “state” in their names). Questions like the following are indications that there’s no easy answer to the questions: 1) what are the differences and 2) when to use one over the other?

What is the difference between a state machine and the implementation of the state pattern?

As mentioned before some consider state machines obsolete due to the all powerful state design pattern (https://www.codeproject.com/Articles/509234/The-State-Design-Pattern-vs-State-Machine). Others consider the state design pattern inferior:

In general, this design pattern [State Design Pattern] is great for relatively simple applications, but for a more advanced approach, we can have a look at Spring’s State Machine tutorial.

https://www.baeldung.com/java-state-design-pattern

Truth is, they complement each other:

• The strength of the state design pattern is the encapsulation of state specific behavior.
• The strength of a state machine is its ability to define and control the flow of our application.

Let’s put everything together…

The Super State Design Pattern

We start with simple interfaces/classes for the state design pattern:

interface State<C : Context, P: Any?, R : Any?> {
    fun handle(context: C, parameters: P): R
}
interface Context {
   fun transition(event: Event)
}
open class Event

• The State interface has one function to perform its core functionality.
  A reference to its Context is passed into that function so it can trigger a transition using an Event.
  The second parameter P passed into that function is used to pass in more parameters if needed (using the Context to retrieve those parameters is possible but can lead to clunky implementations on Context class side).
  The function also returns a parameter R, which can be literally anything (https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/-any).
  We’re using generics for this class (C for Context, P for the input parameters, R for the result) so we can re-use it.
• The Context interface’s purpose is to expose the transition function to the State. That’s all it needs from the design pattern’s perspective.
• The Event class can be anything really. Concrete implementations of that class can have properties that can be passed from one to the next State (and read by concrete State implementations).

Our demo code prints the days of the week upper case / lower case depending on the state (see https://en.wikipedia.org/wiki/State_pattern#Example):

monday
TUESDAY
WEDNESDAY
thursday
FRIDAY
SATURDAY
sunday

Because we want a finite state machine to manage states and transitions, we will use the following abstract base class for our actual Context. Please note that we’re passing in a StateMachine.Graph in the constructor (more about the state machine below).

abstract class ContextImpl<C : Context, P: Any?, R : Any?>(
    graph: StateMachine.Graph<State<C, P, R>, Event, Any>
) : Context {
    private val stateMachine = StateMachine.create(graph) { }

    fun getState() = stateMachine.state

    override fun transition(event: Event) {
        stateMachine.transition(event)
    }
}

All this class does is:

• Implement the transition function (inherited from the Context interface).
• Encapsulate the state machine (details see below).
• Expose the state so it can be used by the Context class implementation to call the State’s one and only handle(Context) function.

Now we’re ready to implement our actual Context:

interface Writer {
    fun write(text: String)
}
class WriterContext : 
      ContextImpl<WriterContext, String, Any?>(graph), Writer 
{
    override fun write(text: String) {
        getState().handle(this, text)
    }
}

What this class does is delegate execution of the write function to the current State (managed by the state machine). All the interactions with the state machine are handled by its super class.

The States and the Events that trigger state transitions are pretty straight forward:

object OnLowerCaseDone : Event()

object OnUpperCaseDone : Event()

class LowerCaseState : State<WriterContext, String, Any?> {
    override fun handle(context: WriterContext, text: String) : Any? 
    {
        println(text.toLowerCase())
        context.transition(OnLowerCaseDone)
        return null
    }
}
class MultipleUpperCaseState : State<WriterContext, String, Any?> {
    private var count = 0

    override fun handle(context: WriterContext, text: String) : Any?
    {
        println(text.toUpperCase())
        if (++count > 1) context.transition(OnUpperCaseDone)
        return null
    }
}

Important here is that the States hold mostly behavior related code. The only control flow related code is the one emitting Events to trigger a state transition. The states themselves don’t know where that transition leads to, only the state machine knows.

The state machine implementation is the missing piece.
In past projects I evaluated this implementation: https://github.com/Tinder/StateMachine. It has a fluent API due to it’s use of a DSL (domain specific language) but it has two main disadvantages (that’s why I used my own less elegant but more flexible implementation):

1. To separate state behavior from the state machine I had to wrap it to expose state as a stream of events (in my case I wrapped it in an Rx Observable). That stream of events was processed by an observer that could dispatch States to the code that implemented the desired behavior.
2. When States want to trigger a transition to another State by emitting an Event, they needed access to the state machine which created a vicious cycle of dependencies from States to the state machine that I could never solve to my satisfaction (not with above library).

Using the state design pattern both of these problems are solved. The first issue goes away because we’re not using a reactive pattern but simply call some function of the Context expecting behavior depending on its state. The second issue goes away because we tie the State to the state machine through the Context that offers the “transition(event: Event)” function.

Now using the https://github.com/Tinder/StateMachine we can simply write:

private val graph = StateMachine
    .createGraph<State<WriterContext, String, Any?>, Event, Any> {
        initialState(LowerCaseState())
        state<LowerCaseState> {
            on<OnLowerCaseDone> { 
                transitionTo(MultipleUpperCaseState()) 
            }
        }
        state<MultipleUpperCaseState> {
            on<OnUpperCaseDone> { 
                transitionTo(LowerCaseState()) 
            }
        }
    }

Above code is pure control flow code, there’s no reference to the behavior of the States!

Now we simply do:

val writer = WriterContext(graph)
Observable.just("Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday")
    .subscribe { writer.write(it) }

To get:

monday
TUESDAY
WEDNESDAY
thursday
FRIDAY
SATURDAY
sunday

Circuit Breaker Design Pattern

Using the “Super State Design Pattern” to write days of the weeks alternating in upper- & lowercase is certainly overkill. A more practical application would be the implementation of the circuit breaker pattern.

In essence we want to detect failures and encapsulate the logic of preventing a failure from constantly recurring (e.g. during maintenance, temporary external system failure or unexpected system difficulties): https://en.wikipedia.org/wiki/Circuit_breaker_design_pattern.

The following state diagram taken from https://martinfowler.com/bliki/CircuitBreaker.html describes the desired behavior:

To implement this using the super state design pattern we need three states and three events (we ignore state transitions from a state to itself or rather encapsulate that logic in the state):

object OnSuccess : Event()
object OnFailed : Event()
object OnResetTimeout : Event()
class Closed(private val failAfter: Int) : State...
class Open(private val timeout: Long) : State...
class HalfClosed : State...

Each State holds only the state specific code, e.g. the Closed state would:

• call a target URL
• count the number of consecutive failures, if those number exceeds the threshold it would trigger a state transition using OnFailed
• reset the failure count with each successful call

The handle function for this is very simple:

override fun handle(context: CircuitBreaker, url: String) =
    call(url)
        .doOnError {
            if (failures.incrementAndGet() >= failAfter) {
                context.transition(OnFailed)
            }
        }
        .doOnSuccess { 
            failures.set(0) 
        }

The state machine that controls the flow shown in the state diagram above is simple too:

const val timeout = 5 * 1000L
const val failAfter = 5
private val graph = StateMachine
    .createGraph<State<CircuitBreaker, String, Single<String>>, Event, Any> {
        initialState(Closed(failAfter))
        state<Closed> {
            on<OnFailed> {
                transitionTo(Open(timeout))
            }
        }
        state<Open> {
            on<OnResetTimeout> {
                transitionTo(HalfClosed())
            }
        }
        state<HalfClosed> {
            on<OnFailed> {
                transitionTo(Open(timeout))
            }
            on<OnSuccess> {
                transitionTo(Closed(failAfter))
            }
        }
    }

Summary

What does the super state design pattern do for us?

• Objects change behavior based on their internal state.
• State specific behavior is completely encapsulated in that state allowing us to write loosely coupled, reusable and testable components.
• State control flow is encapsulated in a state machine with all its benefits:
  - easy modelling of states and transitions
  - easy to prevent out of order execution even in multi-threaded environments
  - easy to understand, change and maintain

The full code sample can be found here: https://github.com/1gravity/state_patterns