blob: 8d3200f9cc99e8c9c258eb42e24457a8fbff089a [file] [log] [blame]
// 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 {
typename 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_