Home

This project implements finite state machines (FSM) and hierarchical state machines (HSM) variants. They are used to manage state transitions, drive visualization, and automate actions.

Introduction

Conceptually an FSM consists of two sets:

1. A fixed set of possible named states.
2. A fixed set of named actions, which can transition from one state to another.

Frequently an FSM can be defined by a transition table, where every row is a triplet of strings:

1. Current state.
2. Action.
3. New state.

Given this table and the initial state, we can define a state machine. States and actions do not need to be explicitly defined, and can be collected from a transition table.

Example: a push button switch

Example of a transition table for a push button switch:

on  => click => off
off => click => on

The table above defines two states: on and off, and one action click, which changes a state to its opposite.

Example: a toggle switch

Example of a transition table for a two position toggle switch:

on  => down => off
off => up   => on

Now we have the same two states, yet two different actions: up and down. It introduces restrictions: now it is not possible to go up in on state, we can do down only. An FSM ignores illegal operations automatically. An FSM guarantees that only allowed state transitions will be performed.

In some cases we want to handle state transitions conditionally: some actions can be allowed only if some external conditions are met. The state machine implementation can incorporate such requirements.

When we switch states, we have two optional events: we exit one state, and enter another. An FSM guarantees that those events will be called sequentially in a given order. Enter/exit state events can be used to implement an initialization and a tear-down related to program states.

Sometimes it is not possible to model a problem with a single FSM. There are two big classes of sub-problems we can solve easily: unrelated FSMs acting independently, or driven programmatically as independent entities, and embedded FSMs, w. The first class is simple: we create as many machines as we need with different sets of states. The latter requires support of embedded states.

Example: a simple UI

For our next example, let's model a user interface of an application with "Account" and "Help" sections. The former may have two subsections: "General" and "Security". User reads help, and clicks on "Show me security questions", and we transition her right there bypassing all intermediate steps:

account => gotoHelp     => help
account => openGeneral  => account-general
account => openSecirity => account-security

account-general  => close => account
account-security => close => account

help => gotoAccount    => account
help => showMeGeneral  => account-general
help => showMeSecurity => account-security

Let's assume that this notation:

stateName => ENTER => onEnterMethod
stateName => EXIT  => onExitMethod

Allows us to specify what methods to call when we enter/exit a state. Using this meta-notation we can "program" our application:

account => ENTER => navigateToAccount
help    => ENTER => navigateToHelp

account-general => ENTER => openGeneralOptions
account-general => EXIT  => closeGeneralOptions

account-security => ENTER => openSecurityOptions
account-security => EXIT  => closeSecurityOptions

Possible meta-implementation of those methods:

{
  navigateToAccount: function () {
    openLocation("account");
  },
  openSecurityOptions: function () {
    openDialog("security");
  },
  closeSecurityOptions: function () {
    closeDialog("security");
  }
  // more implementation details
}

State machines and OOP

State machine operations can be described as a series of events: actions come in usually asynchronously, states are exited and entered. It is difficult to keep track of all state callbacks, even if we don't need to process most events directly. Our state machine implementation can map state events to callbacks, so we can easily implement required methods. If a method is not there, a state machine will ignore it.

If we assume that our FSM maps a state name like foo-bar to method names onStateFooBarEnter() and onStateFooBarExit(), we can rewrite our previous example:

{
  onStateAccountEnter: function () {
    openLocation("account");
  },
  onStateAccountSecurityEnter: function () {
    openDialog("security");
  },
  onStateAccountSecurityExit: function () {
    closeDialog("security");
  }
  // more implementation details
}

While it is a little bit verbose, it is direct, unlikely to clash with other methods. It allows us to skip all explicit enter/exit definitions, and we can add/remove relevant handlers at will, even dynamically. (We can still specify specific names for some events, and use generated names for others.)

Conventions introduce some boilerplate in naming, but reduces the amount of code we write.

State machines and CSS

Frequently UI of a web application is an informal state machine, where a visual states are driven by CSS classes. They can control visibility, visual highlights, animation, and other UI and UX aspects. Our state machine implementation can map states to CSS classes, and add/remove them automatically reflecting its current state, so we can harness them to update visuals.

For example, instead of a programmatic approach of our previous example we can implement it using simple HTML and CSS:

<div id="state-root">
  <div id="account">
    <div id="general">
      <!-- general account settings here -->
    </div>
    <div id="security">
      <!-- security account settings here -->
    </div>
  </div>
  <div id="help">
    <!-- help here -->
  </div>
</div>

Now imagine that a state machine reflects its current state by setting CSS classes on an element state-root, state is formed with a prefix "ui-" and a state name. In this case we can control visibility like that:

#account,
#general,
#security,
#help {
  /* not shown by default */
  display: none;
}

.ui-account #account {
  display: block;
}

.ui-help #help {
  display: block;
}

.ui-account-general #general {
  display: block;
}

.ui-account-security #security {
  display: block;
}

With this CSS when we transition states, DOM nodes will be accordingly shown/hidden, all without any code from us.

Advantages of state machines

Note that following things are done automatically for us:

• We are assured that security options are opened in the right context — when we are in "Account".
  • Security options cannot be opened directly in "Help", nor when other options, like "General" are opened.
  • It is not possible to pop a second dialog box when security options are opened.
• We cannot go to help directly from security options. We have to close the dialog first (and transition to account).
  • We can easily add an action to go to help directly from options. No new code will be required for that, yet security options will be correctly closed anyway.
  • Unexpected actions will be automatically ignored.
• Adding more sections and actions do not affect our existing code. Any state transitions will be orchestrated by our state machine correctly.
  • We are scalable and maintainable.
• State callbacks can be easily added/removed.
  • With a convention in place we reduce the amount of code we write.
• CSS can be managed on DOM nodes automatically. It is up to us to supply proper CSS definitions to drive a web-based UI.
  • Putting more emphasis on CSS we improve the overall performance and reduce our codebase.

StateMachine

StateMachine implements a FSM/HSM.

The constructor takes four arguments:

new StateMachine(name, host, states, options);

• name — a unique state machine name as a string. It is used by custom elements to distinguish between state machines, and route requests approprietly. Additionally it is used to generate standard names for CSS classes, and callback methods.
• host — an object to consult when changing states, and to call callbacks on (see below for details).
• states — an object describing states (see below for details).
• options — an optional object with additional parameters. Following properties are recognized (all optional):
  • root — a DOM node. Used to set/remove CSS classes on.
  • init — an initial state as a string. Default: null (meaning no state).
  • cssClass — a CSS prefix, if string, or a function to map states to CSS classes (see details below). Default: a prefix composed of a state machine name and "-".
  • stateMethodName — a prefix for a method name, if string, or a function to map states to method names (see details below). In case of a prefix a suffix is added ("Enter" or "Exit") whenever appropriate. Default: a prefix composed from "onState" and a capitalized state machine name.
  • deferredInit — a Boolean value. If truthy, no initial state is set on construction.

State description

States are described by tree-like structures. The top (AKA main) level (which is the only level for regular FSMs) is described as a dictionary, where state names serve as keys, and values are objects with a following structure:

• enter — an optional method name, if string, or a function to call when entering this state.
• exit — an optional method name, if string, or a function to call when exiting this state.
• cssClass — an optional CSS class name to set when this state is entered.
• transitions — a dictionary that specifies all valid transitions to other states. Its keys are action names, and values are new state names. For embedded states, a name should include all parent names separated by "-".
• children — an optional dictionary of sub-states identical in shape to the main dictionary.

If enter, exit, and/or cssClass are not specified, they are generated using the constructor's options cssClass or stateMethodName.

Generating CSS class names

If cssClass a string, it is used as a prefix with a state name to make up a CSS class name.

Examples:

• If we didn't specify cssClass at all, and our state machine is named ui, following CSS class names will be generated:
  • for account ⇒ "ui-account",
  • for account-general ⇒ "ui-account-general".
• If we specified a prefix "MAIN_", following CSS class names will be generated:
  • for account ⇒ "MAIN_account",
  • for account-general ⇒ "MAIN_account-general".

If a function is specified, it will be called with a following signature:

var result = cssClass(stateNames);

• stateNames — an array of strings. It lists all names starting from the top parent.
• result — a generated CSS name as a string.

Generating state method names

If stateMethodName a string, it is used as a prefix with a state name to make up a CSS class name.

Examples:

• If we didn't specify stateMethodName at all, and our state machine is named ui, following method names will be generated:
  • for account ⇒ "onStateUiAccountEnter" and "onStateUiAccountExit",
  • for account-general ⇒ "onStateUiAccountGeneralEnter" and "onStateUiAccountGeneralExit".
• If we specified a prefix "on", following CSS class names will be generated:
  • for account ⇒ "onAccountEnter" and "onAccountExit",
  • for account-general ⇒ "onAccountGeneralEnter" and "onAccountGeneralExit".

If a function is specified, it will be called with a following signature:

var result = stateMethodName(stateNames, isEnter);

• stateNames — an array of strings. It lists all names starting from the top parent.
• isEnter — a Boolean value: true for ENTER, false for EXIT.
• result — a generated state method name as a string.

StateMachine main API

A StateMachine instance defines a set of public properties and methods.

name

Name of a state machine as a string.

host

Host object, which is used to consult for state changes, and defines callbacks for state events. This property can be reassigned dynamically.

root

An optional root property is a DOM node, or null. When defined, it is used to set/remove CSS classes by helper methods (see below). This property can be reassigned dynamically.

init

The optional initial state as a string, or null. It should specify a valid state name, which can be used by initialize() to set the initial state by issuing all proper calls to host's callbacks.

current

This property points to a current state object, or null. A state object corresponds to "State description" above, but is augmented with following properties:

• name — state name as a string.
  • Examples: "account", "account-general".
• names — state name as an array of strings.
  • Examples: ["account"], or ["account", "general"].
• parent — points to a parent state object, or null for top-most states.

deferredInit

A Boolean flag indicating to the constructor to skip calling initialize(). Default: false.

This flag is used, when a host is not ready to perform callbacks while constructing of a state machine. For example, we may construct our state machine before DOM is created, so root is not defined yet, and we cannot use it to set proper CSS classes. In this case we may delay the initialization until later.

states

An object similar to states argument of the constructor, but augmented with properties described above for current property:

• name — state name as a string.
  • Examples: "account", "account-general".
• names — state name as an array of strings.
  • Examples: ["account"], or ["account", "general"].
• parent — points to a parent state object, or null for top-most states.

Additionally, it has all missing cssClass, enter, and exit properties calculated as described above.

initialize()

The method changes a current state without an action. Usually this is what we want to set an initial state. The method takes one optional argument:

this.initialize(init);

• init — state name as a string, or null.

If a state name is specified, a transition is performed with both action, and args arguments set to null. If a state name is not specified, the previous value of init is used, making this method suitable for periodically resetting the state machine. The method does nothing if no state name was specified, and the previous initial state was null.

This method is called from the constructor, if deferredInit is falsy. Its return value is always ignored.

In performing a transition, this method calls host.onStateEnter() and host.onStateExit() methods described below.

changeState()

The method changes a current state. It takes up to two arguments:

var transitioned = this.changeState(action, args);

• action — action name as a string.
• args — optional action-specific argument. Can be anything. A state machine never analyzes it, but passes it through to host methods.

It returns a Boolean value, which is truthy if a transition was performed, and falsy, if it was suppressed.

In making a decision, this method consults host.getNextState() method described below. In performing a transition, this method calls host.onStateEnter() and host.onStateExit() methods described below.

StateMachine helper API

These are convenience methods to simplify implementing host objects. They are named like corresponding host methods, and have a compatible set of arguments.

getNextState()

The method checks if an action is allowed in the current state using a transition table, and returns a name of next state, or null otherwise. It takes up to two arguments:

var futureState = this.getNextState(action, args);

• action — an action name as a string.
• args — an optional action-specific object.

onStateEnter()

The method sets a corresponding CSS class on root, if it is defined, and calls a relevant callback on host, if it is available. It takes three arguments:

this.onStateEnter(action, args, futureState);

• action — an action name as a string, or null if transition is requested by initialize().
• args — an optional action-specific object.
• futureState — a state name as a string we transition to ultimately.

onStateExit()

The method removes a corresponding CSS class from root, if it is defined, and calls a relevant callback on host, if it is available.

this.onStateExit(action, args, futureState);

• action — an action name as a string, or null if transition is requested by initialize().
• args — an optional action-specific object.
• futureState — a state name as a string we transition to ultimately.

Host definition

A host object specified as a required host argument of the constructor. It should implement following methods:

• getNextState(stateMachine, action, args)
• onStateEnter(stateMachine, action, args, futureState)
• onStateExit (stateMachine, action, args, futureState)

Optionally, a host may implement necessary state callback methods specified in a state description, or automatically generated.

getNextState()

The method returns a name of future state to transition to, or null to indicate that no transition should be performed. It takes three arguments:

var futureState = host.getNextState(stateMachine, action, args);

• stateMachine — this state machine object, which requests a decision.
• action — an action name as a string.
• args — an optional action-specific object.

If host returns a truthy value, it should be a string indicating a future state withing stateMachine. Host may suppress a transition by returning null, or decide on a transition dynamically. In most cases its implementation uses a helper provided by StateMachine as described above:

function getNextState (stateMachine, action, args) {
  return stateMachine.getNextState(action, args);
}

The StateMachine helper checks if an action is allowed in the current state using a transition table, and returns a name of next state, or null otherwise.

onStateEnter()

The method provides a reaction on entering a certain state. It takes four arguments, and return no value:

host.onStateEnter(stateMachine, action, args, futureState);

• stateMachine — this state machine object, which requests a reaction.
• action — an action name as a string, or null if transition is requested by initialize().
• args — an optional action-specific object.
• futureState — a state name as a string we transition to ultimately.

It is up to a host to implement any actions required on entering a state. In most cases its implementation uses a helper provided by StateMachine as described above:

function onStateEnter (stateMachine, action, args, futureState) {
  stateMachine.onStateEnter(action, args, futureState);
}

The default implementation provided by StateMachine sets a corresponding CSS class on root, and calls a relevant callback on host, if it is available.

onStateExit()

The method provides a reaction on exiting a certain state. It takes four arguments, and return no value:

host.onStateExit(stateMachine, action, args, futureState);

• stateMachine — this state machine object, which requests a reaction.
• action — an action name as a string, or null if transition is requested by initialize().
• args — an optional action-specific object.
• futureState — a state name as a string we transition to ultimately.

It is up to a host to implement any actions required on exiting a state. In most cases its implementation uses a helper provided by StateMachine as described above:

function onStateExit (stateMachine, action, args, futureState) {
  stateMachine.onStateExit(action, args, futureState);
}

The default implementation provided by StateMachine removes a corresponding CSS class from root, and calls a relevant callback on host, if it is available.

makeState()

makeState() is a helper to define state machines declaratively. Its return value can be used directly as states argument of StateMachine constructor. It takes a variable number of arguments. All arguments can be of three forms, and listed sequentially. Generally, their relative order is unimportant.

makeState() provides a simple way to describe a transition table, and enter/exit state callbacks. It infers names of all states, and actions indirectly, greatly simplifying the task of defining a potentially complex state machine.

(1) a transition string

This type of an argument specifies a single transition as a triplet:

state1 => action => state2

All three values are separated by arrows "=>". The first value is a name of state we transition from. The second value is a name of action. The third value is a name of state we transition to. Embedded states use a dash to indicate parent states:

account => openGeneral => account-general

(2) a callback string

Visually this one looks like the previous one. The difference is that instead of an action name a predefined event name is used. Presently two such events are defined: ENTER and EXIT:

state1 => ENTER => method1
state1 => EXIT  => method2

The first value is a state name like before. The second one is ENTER or EXIT, which defines an event we target. The third one is a method name on host object, which should be called, when an event occurs.

If callbacks are named regularly using a default naming schema, or correctly generated by stateMethodName option property of the constructor, no need to list them at all — they will be called automatically, if they are defined. It is even possible to add/remove them dynamically.

(3) a callback string + a callback function

The third version is similar to the second version, but requires to specify a pair of values: a string, which defines a state name, and a "magic" value: either ENTER or EXIT, and a function. Examples:

"state1 => ENTER =>", onStateOneEnter,
"state2 => EXIT  =>", closeEverything

A function will be called as a regular callback, with the same arguments, and in a context of host. While it is possible to specify a host's method as function, the second form is usually used as more declarative one.

It is possible to use a less canonical form, which lacks the second arrow:

"state1 => ENTER", onStateOneEnter,
"state2 => EXIT",  closeEverything

(4) a CSS class string

The fourth version allows to specify a custom CSS class name for a state using a "magic" pseudo-action name CLASS. Example:

state1 => CLASS => my-css-class-name

While it is suggested to use CSS class names generated by cssClass option property of the constructor, it is a useful short-cut for exceptions, or to reuse existing CSS classes.

Example

Let's redo the example mentioned in "Introduction" above:

var states = makeState(
  "account => gotoHelp     => help",
  "account => openGeneral  => account-general",
  "account => openSecirity => account-security",

  "account-general  => close => account",
  "account-security => close => account",

  "help => gotoAccount    => account",
  "help => showMeGeneral  => account-general",
  "help => showMeSecurity => account-security",

  "account => ENTER =>", navigateToAccount,
  "help    => ENTER =>", navigateToHelp,

  "account-general => ENTER => openGeneralOptions",
  "account-general => EXIT  => closeGeneralOptions",

  "account-security => ENTER => openSecurityOptions",
  "account-security => EXIT  => closeSecurityOptions"
);

var host = {
  // state-related methods
  getNextState: function (stateMachine, action, args) {
    return stateMachine.getNextState(action, args);
  },
  onStateEnter: function (stateMachine, action, args, futureState) {
    stateMachine.onStateEnter(action, args, futureState);
  },
  onStateExit: function (stateMachine, action, args, futureState) {
    stateMachine.onStateExit(action, args, futureState);
  },

  // custom named callbacks
  openGeneralOptions:   function () { /* impl */ },
  closeGeneralOptions:  function () { /* impl */ },
  openSecurityOptions:  function () { /* impl */ },
  closeSecurityOptions: function () { /* impl */ },

  // optional automatically named callbacks
  onStateUiHelpExit:    function () { /* impl */ }
};

// stand-alone callback functions
function navigateToAccount () { /* impl */ }
function navigateToHelp    () { /* impl */ }

var sm = new StateMachine("ui", host, states, {init: "help"});