starboard/common/state_machine.h

// 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.

#ifndef STARBOARD_COMMON_STATE_MACHINE_H_
#define STARBOARD_COMMON_STATE_MACHINE_H_

#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:
// http://en.wikipedia.org/wiki/UML_state_machine
//
// And Miro Samek's 3-part article on practical UML Statecharts:
// http://www.embedded.com/design/prototyping-and-development/4008247/A-crash-course-in-UML-state-machines-Part-1
//
// 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 {
 public:
  // --- 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:
  // --- 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.
    kHandled,

    // 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.
    kNotHandled,
  };

  // 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_external(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_transition(true),
          is_external(external),
          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:
    // http://en.wikipedia.org/wiki/UML_state_machine#Transition_execution_sequence
    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 descendants 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:
  // --- 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:
  // http://en.wikipedia.org/wiki/UML_state_machine#Transition_execution_sequence
  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 {
 public:
  // --- Nested Types and Constants ---

  explicit StateMachine(const std::string& name) : machine_(this, name) {}
  virtual ~StateMachine() {}

  void Initialize() { machine_.Initialize(); }

  const char* name() const { return machine_.name(); }

  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);
  }

 protected:
  // See the other HandledState in StateMachineBase.
  enum HandledState {
    kHandled,
    kNotHandled,
  };

  // See the other Result in StateMachineBase.
  struct Result {
    Result(HandledState handled)  // NOLINT(runtime/explicit)
        : target(),
          is_transition(false),
          is_external(false),
          is_handled(handled == kHandled) {}

    Result(StateEnum transition_target,
           bool external = false)  // NOLINT(runtime/explicit)
        : target(transition_target),
          is_transition(true),
          is_external(external),
          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(); }

 private:
  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 {
   public:
    WrappedMachine(StateMachine<StateEnum, EventEnum>* wrapper,
                   const std::string& name)
        : StateMachineBase(name), wrapper_(wrapper) {}

    optional<State> GetUserParentState(State state) const override {
      optional<StateEnum> result =
          wrapper_->GetUserParentState(static_cast<StateEnum>(state));
      return (result ? static_cast<State>(*result) : optional<State>());
    }

    optional<State> GetUserInitialSubstate(State state) const override {
      optional<StateEnum> result =
          wrapper_->GetUserInitialSubstate(static_cast<StateEnum>(state));
      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 =
          wrapper_->HandleUserStateEvent(static_cast<StateEnum>(state),
                                         static_cast<EventEnum>(event), data);
      if (result.is_transition) {
        return Result(static_cast<State>(*result.target), result.is_external);
      }

      return result.is_handled ? kHandled : kNotHandled;
    }

    void HandleUserStateEnter(State state) override {
      wrapper_->HandleUserStateEnter(static_cast<StateEnum>(state));
    }

    void HandleUserStateExit(State state) override {
      wrapper_->HandleUserStateExit(static_cast<StateEnum>(state));
    }

    // 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(); }

   private:
    StateMachine<StateEnum, EventEnum>* wrapper_;
  };

  WrappedMachine machine_;
};

}  // namespace starboard

#endif  // STARBOARD_COMMON_STATE_MACHINE_H_