blob: 21501a0f6369e73258519e8d459364fd8372e1af [file] [log] [blame]
// Copyright 2014 The Cobalt Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <queue>
#include <string>
#include "starboard/common/optional.h"
#include "starboard/configuration.h"
#include "starboard/export.h"
namespace starboard {
// An approximate implementation of a run-to-completion (RTC) Hierarchical State
// Machine (HSM), supporting most UML Statechart semantics.
// Some good background information on UML Statecharts, mostly written by Miro
// Samek:
// And Miro Samek's 3-part article on practical UML Statecharts:
// This class does not provide any intrinsic support for "orthogonal regions,"
// "extended state," or "deferred events." "Guard conditions" are easily
// implemented by the client directly in the event handler. It also minorly
// deviates from the UML Statechart specification by calling transition handlers
// before exiting the current states. This is because this implementation uses a
// simplification which combines the transition handlers and the
// state-event-transition map into a single function (HandleUserStateEvent).
// This class is not thread-safe. It is the user's responsibility to synchronize
// calls into the state machine, either with locks or by simply using from a
// single thread.
// Terse suggestions for using this class:
// * Use the templated StateMachine wrapper class instead of this class
// directly.
// * Define two enums, one for your states, and one for your events.
// * Subclass to define your state machine and event handlers.
// * Avoid directly exposing or passing around state machines (wrap instead).
// Handle() is not a great public interface.
// * Include your state machine in another class as a private by-value member.
// * Synchronize access to the state machine.
// * Prefer writing state machine event handlers over checking if the machine
// IsIn() a particular state.
// * Convert public methods into events, get into the state machine as quickly
// as possible.
// * You only need to define a state when you are going to leave the state
// machine in a particular condition where events can occur.
// * Create a superstate when you have an event you want to handle the same
// way for a collection of states.
// * When managing resources, create a state or superstate that represents the
// acquisition of that resource, and release the resource in the Exit
// handler.
// Some Definitions:
// Simple State - A State with no substates. The state machine is always
// left in exactly one Simple State.
// Composite State - A State with at least one substate.
// Guard Condition - An external condition on which an event handler
// branches.
// Run-To-Completion - A property specifying that the state machine handles
// one event at a time, and no events are handled until
// the previous event is done being handled.
// See the unittests for this class for a contrived example state machine
// implementation.
class StateMachineBase {
// --- Nested Types and Constants ---
typedef uint32_t State;
typedef uint32_t Event;
// --- Public Methods ---
// Constructor with name. The name is helpful for debugging.
explicit StateMachineBase(const std::string& name);
virtual ~StateMachineBase() {}
// Enters the initial state, as specified by |GetUserInitialState()| and
// follows the initial substates down to the first simple (childless) state
// found. Idempotent. Will happen automatically on the first |Handle()| call,
// if not done explicitly.
void Initialize();
// Gets the name of this state machine, for logging purposes.
const char* name() const { return name_.c_str(); }
// Gets a version number that increases monotonically with each state
// transition (unless it overflows |uint64_t|). This can be useful for timers
// and asynchronous events that only want to do their action if the state has
// not changed since they were queued.
// The state version changes exactly once per transition. In other words, it
// doesn't change for every Enter and Exit for a transition.
uint64_t version() const { return version_; }
// Gets the simplest current state that this state machine is in. To check if
// the state machine is in a particular composite state, use |IsIn()|. Returns
// null if uninitialized.
optional<State> state() const { return state_; }
// Reports whether the state machine is currently in the given state. A state
// machine is considered to be "in" the current simple state, but also "in"
// all superstates of the current simple state.
bool IsIn(State state) const;
// Gets a printable string for the given state.
const char* GetStateString(optional<State> state) const;
// Gets a printable string for the given event.
const char* GetEventString(optional<Event> event) const;
// Handles the given event in the context of the state machine's current
// state, executing the appropriate event handlers and performing any
// precipitate state transitions. If called reentrantly, the event will be
// queued until the current event has run to completion.
// |data| is a way to pass auxiliary data to the event handler. No retention
// or ref-counting is done on that data, it is simply passed through to the
// event handler. Since |Handle()| will queue the event if (and only if)
// called from an event handler, it is up to the caller to ensure the lifetime
// of whatever is passed in here.
void Handle(Event event, void* data = NULL);
// --- Protected Nested Types ---
// A type that can be returned from a state-event handler, which will be
// coerced into the appropriate Result structure.
enum HandledState {
// The event handler returns this to say that the handler consume the event,
// but caused no state transition.
// The event handler returns this to say that the handler did not consume
// the event, and it should bubble up to the parent state, if any.
// Structure that handlers return, allowing them to cause state transitions or
// prevent the event from bubbling. State-event handlers may just return a
// HandledState or a state to transition to, and it will be coerced into this
// structure.
struct Result {
// Default constructor is unhandled.
Result() : is_transition(false), is_external(false), is_handled(false) {}
// The no-transition constructor. Non-explicit so that the implementor of
// |HandleUserStateEvent()| just needs to return a |HandledState| and it
// does the right thing.
Result(HandledState handled) // NOLINT(runtime/explicit)
: is_transition(false),
is_handled(handled == kHandled) {}
// The state transition constructor. This implies that the event was
// handled. Non-explicit so that the implementor of |HandleUserStateEvent()|
// just needs to return a State and it does a non-external transition.
Result(State transition_target,
bool external = false) // NOLINT(runtime/explicit)
: target(transition_target),
is_handled(true) {}
Result& operator=(HandledState rhs) {
target = nullopt;
is_transition = false;
is_external = false;
is_handled = (rhs == kHandled);
return *this;
Result& operator=(State transition_target) {
target = transition_target;
is_transition = true;
is_external = false;
is_handled = true;
return *this;
// State to transition to. Only valid if is_transition is true.
optional<State> target;
// Whether this result indicates a state transition.
bool is_transition;
// Whether the specified transition is external. Only meaningful if
// is_transition is true.
// For more on state transitions, see:
bool is_external;
// Whether the event was handled by the handler. If true, consumes the
// event, and prevents bubbling up to superstates. False propagates the
// event to superstates.
bool is_handled;
struct EventWithData {
EventWithData(Event event, void* data) : event(event), data(data) {}
Event event;
void* data;
// --- Implementation Interface for Subclasses ---
// Abstract method for subclasses to define the state hierarchy. It is
// recommended that all user-defined states be descendents of a single "top"
// state.
virtual optional<State> GetUserParentState(State state) const = 0;
// Abstract method for subclasses to define the initial substate of their
// states, which is required for all complex states. If a state is a simple
// state (no substates), returns null.
virtual optional<State> GetUserInitialSubstate(State state) const = 0;
// Abstract method for subclasses to define the initial (top) state of their
// state machine. This must be a state that has no parent. This state will be
// entered upon calling |Initialize()|.
virtual State GetUserInitialState() const = 0;
// Optional method for subclasses to define strings for their states, solely
// used for debugging purposes.
virtual const char* GetUserStateString(State state) const { return NULL; }
// Optional method for subclasses to define strings for their events, solely
// used for debugging purposes.
virtual const char* GetUserEventString(Event event) const { return NULL; }
// Abstract method for subclasses to define handlers for events in given
// states. This method must return either:
// a) a state to transition to, meaning the event was handled and caused
// a transition
// b) |kHandled| meaning the event was handled but no transition occurred
// c) |kNotHandled|, meaning the event should bubble up to the parent state
// d) an explicit Result structure, mainly for external transitions.
// Implementations wishing to catch all unhandled events may do so in their
// top state.
// This method is generally implemented as a nested switch statement, with the
// outer switch on |state| and the inner switch on |event|. You may want to
// break this apart into per-state or per-state-event functions for
// readability and maintainability.
virtual Result HandleUserStateEvent(State state, Event event, void* data) = 0;
// Abstract method for subclasses to define state entry behaviors.
virtual void HandleUserStateEnter(State state) = 0;
// Abstract method for subclasses to define state exit behaviors.
virtual void HandleUserStateExit(State state) = 0;
// --- Helper Methods for Subclasses ---
// Subclasses can call this method to turn on logging. Logging is opt-in,
// because it can be very verbose, and is likely only useful during
// development of a particular state machine.
void EnableLogging() { should_log_ = true; }
// --- Private Helper Methods ---
// Gets the parent state of the given state.
optional<State> GetParentState(optional<State> state) const;
// Gets the initial substate of given state.
optional<State> GetInitialSubstate(optional<State> state) const;
// Handles all queued events until there are no more to run. Event handlers
// may queue more events by calling |Handle()|, and this method will also
// process all precipitate events.
void HandleQueuedEvents();
// Workhorse method for handling a single event.
void HandleOneEvent(Event event, void* data);
// Gets the path from the Top state to the given |state|, storing it in the
// given |out_path| array, up to |max_depth| entries. If specified,
// |out_depth| will be set to the number of valid states that fit in the given
// array.
void GetPath(State state,
size_t max_depth,
State* out_path,
size_t* out_depth) const;
// Transitions between the given source and target states, assuming that the
// source state is in the current state path to the Top state. The source
// state is the state whose handler generated the transition.
// See:
void Transition(Event event, State source, State target, bool is_external);
// Follows the initial substates from the current state until it reaches a
// simple state.
void FollowInitialSubstates();
// Enters the given state.
void EnterState(State state);
// Exits the current state to its parent.
void ExitCurrentState();
// --- Members ---
// The name of this state machine, for debugging purposes.
const std::string name_;
// The current state of this state machine. Null until initialized.
optional<State> state_;
// The unique version of this state machine's state, updated on every
// transition.
uint64_t version_;
// Queue of events to handle once the current event is done being
// handled. Should always be empty unless |is_handling_| is true.
std::queue<EventWithData> event_queue_;
// Whether this state machine is actively handling an event. Used to detect
// reentrant calls to |Handle()|.
bool is_handling_;
// Whether the state machine has been initialized into its initial state
// yet. Used to make |Initialize()| idempotent.
bool is_initialized_;
// Whether the state machine should log information about state transitions.
bool should_log_;
// A convenience template wrapper for StateMachineBase. See the above class
// for complete documentation. Basically, you define your states and events as
// two enums, and then pass them as template args to this template class. Your
// state machine should then subclass this template class. It then does the work
// of casting and converting back and forth from your enums to
// StateMachineBase's numeric State and Event definitions.
// All the methods in this class, protected and public, match the description
// and behavioral contracts of the equivalently named method in
// StateMachineBase.
template <typename StateEnum, typename EventEnum>
class StateMachine {
// --- Nested Types and Constants ---
explicit StateMachine(const std::string& name) : machine_(this, name) {}
virtual ~StateMachine() {}
void Initialize() { machine_.Initialize(); }
const char* name() const { return; }
uint64_t version() const { return machine_.version(); }
optional<StateEnum> state() const {
optional<BaseState> wrappedState = machine_.state();
return (wrappedState ? static_cast<StateEnum>(*wrappedState)
: optional<StateEnum>());
bool IsIn(StateEnum state) const {
return machine_.IsIn(static_cast<BaseState>(state));
const char* GetStateString(optional<StateEnum> state) const {
return machine_.GetStateString(state ? static_cast<BaseState>(*state)
: optional<BaseState>());
const char* GetEventString(optional<EventEnum> event) const {
return machine_.GetEventString(event ? static_cast<BaseEvent>(*event)
: optional<BaseEvent>());
void Handle(EventEnum event, void* data = NULL) {
machine_.Handle(static_cast<BaseEvent>(event), data);
// See the other HandledState in StateMachineBase.
enum HandledState {
// See the other Result in StateMachineBase.
struct Result {
Result(HandledState handled) // NOLINT(runtime/explicit)
: target(),
is_handled(handled == kHandled) {}
Result(StateEnum transition_target,
bool external = false) // NOLINT(runtime/explicit)
: target(transition_target),
is_handled(true) {}
Result& operator=(HandledState rhs) {
target = nullopt;
is_transition = false;
is_external = false;
is_handled = (rhs == kHandled);
return *this;
Result& operator=(StateEnum transition_target) {
target = transition_target;
is_transition = true;
is_external = false;
is_handled = true;
return *this;
optional<StateEnum> target;
bool is_transition;
bool is_external;
bool is_handled;
virtual optional<StateEnum> GetUserParentState(StateEnum state) const = 0;
virtual optional<StateEnum> GetUserInitialSubstate(StateEnum state) const = 0;
virtual StateEnum GetUserInitialState() const = 0;
virtual const char* GetUserStateString(StateEnum state) const { return NULL; }
virtual const char* GetUserEventString(EventEnum event) const { return NULL; }
virtual Result HandleUserStateEvent(StateEnum state,
EventEnum event,
void* data) = 0;
virtual void HandleUserStateEnter(StateEnum state) = 0;
virtual void HandleUserStateExit(StateEnum state) = 0;
void EnableLogging() { machine_.EnableLoggingPublic(); }
typedef StateMachineBase::State BaseState;
typedef StateMachineBase::Event BaseEvent;
// Private contained subclass that forwards and adapts all virtual methods
// into this class's equivalent virtual methods.
class WrappedMachine : public StateMachineBase {
WrappedMachine(StateMachine<StateEnum, EventEnum>* wrapper,
const std::string& name)
: StateMachineBase(name), wrapper_(wrapper) {}
optional<State> GetUserParentState(State state) const override {
optional<StateEnum> result =
return (result ? static_cast<State>(*result) : optional<State>());
optional<State> GetUserInitialSubstate(State state) const override {
optional<StateEnum> result =
return (result ? static_cast<State>(*result) : optional<State>());
State GetUserInitialState() const override {
return static_cast<State>(wrapper_->GetUserInitialState());
const char* GetUserStateString(State state) const override {
return wrapper_->GetUserStateString(static_cast<StateEnum>(state));
const char* GetUserEventString(Event event) const override {
return wrapper_->GetUserEventString(static_cast<EventEnum>(event));
Result HandleUserStateEvent(State state,
Event event,
void* data) override {
typename StateMachine<StateEnum, EventEnum>::Result result =
static_cast<EventEnum>(event), data);
if (result.is_transition) {
return Result(static_cast<State>(*, result.is_external);
return result.is_handled ? kHandled : kNotHandled;
void HandleUserStateEnter(State state) override {
void HandleUserStateExit(State state) override {
// A public exposure of EnableLogging so the wrapper can access it. Since
// this class is private to the wrapper, it is the only one who can see it.
void EnableLoggingPublic() { EnableLogging(); }
StateMachine<StateEnum, EventEnum>* wrapper_;
WrappedMachine machine_;
} // namespace starboard