blob: a87e0c784ba3c7725cf7653f6453c204fa954002 [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.
#include "starboard/common/state_machine.h"
#include <algorithm>
#include "starboard/log.h"
// --- Macros for common logging idioms ---
#define SM_STATE(s) GetStateString(s) << "(" << s << ")"
#define SM_STATEN(s) GetStateString(s) << "(" << s.value_or(0) << ")"
#define SM_EVENT(e) GetEventString(e) << "(" << e << ")"
#define SM_PREFIX name_ << "-" << SM_STATEN(state_) << "v" << version_ << ": "
#define SM_DLOG(level) SB_DLOG(level) << SM_PREFIX
namespace starboard {
StateMachineBase::StateMachineBase(const std::string& name)
: name_(name),
version_(0),
is_handling_(false),
is_initialized_(false),
should_log_(false) {}
void StateMachineBase::Initialize() {
if (is_initialized_) {
return;
}
if (should_log_) {
SM_DLOG(INFO) << "INITIALIZING";
}
SB_DCHECK(!state_) << SM_PREFIX;
SB_DCHECK(!GetParentState(GetUserInitialState())) << SM_PREFIX;
is_initialized_ = true;
FollowInitialSubstates();
}
bool StateMachineBase::IsIn(State state) const {
optional<State> currentState = state_;
while (currentState) {
if (state == currentState.value()) {
return true;
}
currentState = GetParentState(currentState);
}
return false;
}
const char* StateMachineBase::GetStateString(optional<State> state) const {
if (!state) {
return "<none>";
}
const char* user = GetUserStateString(state.value());
if (user) {
return user;
}
return "UNKNOWN_STATE";
}
const char* StateMachineBase::GetEventString(optional<Event> event) const {
if (!event) {
return "<none>";
}
const char* user = GetUserEventString(event.value());
if (user) {
return user;
}
return "UNKNOWN_EVENT";
}
void StateMachineBase::Handle(Event event, void* data) {
Initialize();
if (is_handling_) {
if (should_log_) {
SM_DLOG(INFO) << "QUEUEING " << SM_EVENT(event);
}
event_queue_.push(EventWithData(event, data));
return;
}
HandleOneEvent(event, data);
HandleQueuedEvents();
}
optional<StateMachineBase::State> StateMachineBase::GetParentState(
optional<State> state) const {
if (!state) {
return optional<State>();
}
return GetUserParentState(state.value());
}
optional<StateMachineBase::State> StateMachineBase::GetInitialSubstate(
optional<State> state) const {
if (!state) {
return optional<State>();
}
return GetUserInitialSubstate(state.value());
}
void StateMachineBase::HandleQueuedEvents() {
while (!event_queue_.empty()) {
EventWithData& event = event_queue_.front();
HandleOneEvent(event.event, event.data);
event_queue_.pop();
}
}
void StateMachineBase::HandleOneEvent(Event event, void* data) {
if (should_log_) {
SM_DLOG(INFO) << "HANDLING " << SM_EVENT(event);
}
SB_DCHECK(!is_handling_) << SM_PREFIX;
is_handling_ = true;
// Walk up the hierarchy from the simplest current state, looking for event
// handlers, stopping at the first state that decides to handle the event.
optional<State> source = state_;
Result result;
while (source) {
result = HandleUserStateEvent(source.value(), event, data);
if (!result.is_handled) {
// Result was not handled, so we continue up the state chain.
source = GetParentState(source);
continue;
}
break;
}
// Log that the event was completely unhandled, because that's kinda weird.
// It's better if the state machine handler explicitly consumes and ignores
// events that should be ignored.
if (!result.is_handled && should_log_) {
SM_DLOG(WARNING) << "Event " << SM_EVENT(event) << " was unhandled.";
}
// If a transition was triggered, execute it.
if (result.is_transition) {
Transition(event, source.value(), result.target.value(),
result.is_external);
}
is_handling_ = false;
}
// Returns the index of |state| in |path|, or -1 if not found in |path_length|
// elements. If |state| is null, then it will always return -1.
static int IndexOf(optional<StateMachineBase::State> state,
const StateMachineBase::State* path,
size_t path_length) {
if (!state) {
return -1;
}
int i;
for (i = 0; !(path[i] == state) && i < path_length; ++i) {
}
return (i == path_length ? -1 : i);
}
// Finds the least common ancestor between the two state paths. If there is no
// common ancestor, returns null.
static optional<StateMachineBase::State> FindLeastCommonAncestor(
const StateMachineBase::State* path_a,
size_t length_a,
const StateMachineBase::State* path_b,
size_t length_b) {
size_t max = std::min(length_a, length_b);
size_t i;
for (i = 0; path_a[i] == path_b[i] && i < max; ++i) {
}
return (i == 0 ? optional<StateMachineBase::State>() : path_a[i - 1]);
}
void StateMachineBase::GetPath(State state,
size_t max_depth,
State* out_path,
size_t* out_depth) const {
if (max_depth == 0) {
SM_DLOG(FATAL) << "max_depth must be > 0";
if (out_depth) {
*out_depth = 0;
}
return;
}
size_t depth = 0;
optional<State> currentState = state;
while (currentState && depth < max_depth) {
out_path[depth] = currentState.value();
++depth;
currentState = GetParentState(currentState);
}
// Reverse so the path is in ascending depth order.
std::reverse(out_path, out_path + depth);
if (out_depth) {
*out_depth = depth;
}
}
void StateMachineBase::Transition(Event event,
State source,
State target,
bool is_external) {
if (should_log_) {
SM_DLOG(INFO) << SM_EVENT(event) << " caused " << SM_STATE(source) << " -> "
<< SM_STATE(target) << (is_external ? " (external)" : "");
}
// Define a reasonable max depth so we don't have to heap allocate. I've never
// seen an HSM as deep as whatever arbitrary value this is defined to be at
// the moment.
static const size_t kMaxDepth = 16;
State source_path[kMaxDepth];
size_t source_depth;
GetPath(source, kMaxDepth, source_path, &source_depth);
State target_path[kMaxDepth];
size_t target_depth;
GetPath(target, kMaxDepth, target_path, &target_depth);
optional<State> least_common_ancestor = FindLeastCommonAncestor(
source_path, source_depth, target_path, target_depth);
// External transitions must exit the source state and enter the target
// state, so if the LCA is one of the two, we need to go one level up.
if (is_external &&
(least_common_ancestor == source || least_common_ancestor == target)) {
least_common_ancestor = GetParentState(least_common_ancestor);
}
// Unwind (exit) states up to the closest common ancestor.
while (state_ && !(state_ == least_common_ancestor)) {
ExitCurrentState();
}
// Update version before we wind down to the target.
++version_;
// Wind (enter) states down to the target state.
size_t next_depth = IndexOf(state_, target_path, target_depth) + 1;
SB_DCHECK(next_depth <= target_depth);
while (next_depth < target_depth) {
EnterState(target_path[next_depth]);
++next_depth;
}
FollowInitialSubstates();
}
void StateMachineBase::FollowInitialSubstates() {
while (true) {
optional<State> substate =
(state_ ? GetInitialSubstate(state_) : GetUserInitialState());
if (!substate) {
break;
}
EnterState(substate.value());
}
}
void StateMachineBase::EnterState(State state) {
state_ = state;
if (should_log_) {
SM_DLOG(INFO) << "ENTER";
}
HandleUserStateEnter(state);
}
void StateMachineBase::ExitCurrentState() {
if (should_log_) {
SM_DLOG(INFO) << "EXIT";
}
HandleUserStateExit(state_.value());
state_ = GetParentState(state_);
}
} // namespace starboard