src/base/state_machine_shell.h

// Copyright (c) 2014 Google Inc. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef BASE_STATE_MACHINE_SHELL_H_
#define BASE_STATE_MACHINE_SHELL_H_

#include <stdint.h>

#include <algorithm>
#include <climits>
#include <queue>
#include <string>
#include <vector>

#include "base/base_export.h"
#include "base/bind.h"
#include "base/callback.h"
#include "base/logging.h"
#include "base/optional.h"

namespace base {

// 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 StateMachineShell 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 BASE_EXPORT StateMachineBaseShell {
 public:
  // --- Nested Types and Constants ---

  typedef uint32_t State;
  typedef uint32_t Event;

  typedef optional<State> StateN;
  typedef optional<Event> EventN;

  // --- Public Methods ---

  // Constructor with name. The name is helpful for debugging.
  explicit StateMachineBaseShell(const std::string &name);
  virtual ~StateMachineBaseShell() { }

  // 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.
  StateN 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(StateN state) const;

  // Gets a printable string for the given event.
  const char *GetEventString(EventN 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)
        : 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)
        : target(transition_target),
          is_transition(true),
          is_external(external),
          is_handled(true) { }

    Result &operator=(HandledState rhs) {
      target = base::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.
    StateN 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;
  };


  // --- 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 StateN 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 StateN 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.
  StateN GetParentState(StateN state) const;

  // Gets the initial substate of given state.
  StateN GetInitialSubstate(StateN 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. Event handling is queued by
  // binding the parameters to this method and queueing the resulting Closure.
  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.
  StateN 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<Closure> 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 DLOG information about state transitions.
  bool should_log_;
};


// A convenience template wrapper for StateMachineBaseShell. 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
// StateMachineBaseShell'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
// StateMachineBaseShell.
template <typename StateEnum, typename EventEnum>
class BASE_EXPORT StateMachineShell {
 public:
  // --- Nested Types and Constants ---

  typedef optional<StateEnum> StateEnumN;
  typedef optional<EventEnum> EventEnumN;

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

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

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

  uint64_t version() const {
    return machine_.version();
  }

  StateEnumN state() const {
    BaseStateN wrappedState = machine_.state();
    return (wrappedState ? static_cast<StateEnum>(*wrappedState)
                         : StateEnumN());
  }

  bool IsIn(StateEnum state) const {
    return machine_.IsIn(static_cast<BaseState>(state));
  }

  const char *GetStateString(StateEnumN state) const {
    return machine_.GetStateString(state ? static_cast<BaseState>(*state)
                                         : BaseStateN());
  }

  const char *GetEventString(EventEnumN event) const {
    return machine_.GetEventString(event ? static_cast<BaseEvent>(*event)
                                         : BaseEventN());
  }

  void Handle(EventEnum event, void *data = NULL) {
    machine_.Handle(static_cast<BaseEvent>(event), data);
  }

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

  // See the other Result in StateMachineBaseShell.
  struct Result {
    // Not explicit on purpose, please see the other Result for justification.
    Result(HandledState handled)
        : target(),
          is_transition(false),
          is_external(false),
          is_handled(handled == kHandled) { }

    // Not explicit on purpose, please see the other Result for justification.
    Result(StateEnum transition_target, bool external = false)
        : target(transition_target),
          is_transition(true),
          is_external(external),
          is_handled(true) { }

    Result &operator=(HandledState rhs) {
      target = base::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;
    }

    StateEnumN target;
    bool is_transition;
    bool is_external;
    bool is_handled;
  };

  virtual StateEnumN GetUserParentState(StateEnum state) const = 0;
  virtual StateEnumN 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 StateMachineBaseShell::State BaseState;
  typedef StateMachineBaseShell::Event BaseEvent;
  typedef StateMachineBaseShell::StateN BaseStateN;
  typedef StateMachineBaseShell::EventN BaseEventN;

  // Private contained subclass that forwards and adapts all virtual methods
  // into this class's equivalent virtual methods.
  class WrappedMachine : public StateMachineBaseShell {
   public:
    WrappedMachine(StateMachineShell<StateEnum, EventEnum> *wrapper,
                   const std::string &name)
        : StateMachineBaseShell(name),
          wrapper_(wrapper) {
    }

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

    StateN GetUserInitialSubstate(State state) const OVERRIDE {
      StateEnumN result =
          wrapper_->GetUserInitialSubstate(static_cast<StateEnum>(state));
      return (result ? static_cast<State>(*result) : StateN());
    }

    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 {
      StateMachineShell<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:
    StateMachineShell<StateEnum, EventEnum> *wrapper_;
  };

  WrappedMachine machine_;
};

}  // namespace base

#endif  // BASE_CIRCULAR_BUFFER_SHELL_H_