Macho.hpp

#ifndef __MACHO_HPP__
#define __MACHO_HPP__

// Macho - C++ Machine Objects
//
// The Machine Objects class library (in short Macho) allows the creation of
// state machines based on the "State" design pattern in straight C++. It
// extends the pattern with the option to create hierarchical state machines,
// making it possible to convert the popular UML statechart notation to working
// code in a straightforward way. Other features are entry and exit actions,
// state histories and state variables.
//
// Copyright (c) 2005 by Eduard Hiti (feedback to macho@ehiti.de)
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
//
// You are encouraged to provide any changes, extensions and corrections for
// this software to the author at the above-mentioned email address for
// inclusion into future versions.
//
//
// Description:
//
// States are represented as C++ classes. The hierarchy of states follows the
// inheritance relation between these state classes. A set of state classes for
// a single state machine derives directly or indirectly from a top state class,
// making it the composite state holding all other states. Events are processed
// by calling virtual methods of the top state class. Substates redefine the
// behaviour of these event handler methods.
//
// Special methods "entry", "exit" and "init" are called on state entry, state
// exit and state initialization of super- and substates (in the order defined
// by statechart semantics and current machine state).
//
// An object of type "Machine" maintains the current state of a state machine
// and dispatches events to it. The "Machine" type is a template class
// parametrized with the top state class of the state machine to be run.
//
// State data is not kept in state classes (because state class instances are
// created just once and then reused, whereas state data should be instantiated
// or destroyed each time its state is entered or left). State data is put in
// "Box" types specific to each state class instead, which are managed by the
// Machine object. Boxes are retrieved by calling the "box" method.
// Superstate boxes are accessible by qualifiying the "box" method with the
// state class name (e.g. TOP::box()).
//
// A history of entered substates can be kept for superstates. With a special
// transition into the superstate the history substate can be reentered. History
// can be shallow (only direct substates) or deep (any substate).
//
//
// Example:
//
// #include "Macho.hpp"
// #include <iostream>
// using namespace std;
//
// namespace Example {
//	TOPSTATE(Top) {
//		struct Box {
//			Box() : data(0) {}
//			long data;
//		};
//
//		STATE(Top)
//
//		virtual void event1() {}
//		virtual void event2() {}
//
//	private:
//		void entry();
//		void exit();
//		void init();
//	};
//
//	SUBSTATE(Super, Top) {
//		STATE(Super)
//		HISTORY()
//
//	private:
//		void entry();
//		void exit();
//	};
//
//	SUBSTATE(StateA, Super) {
//		struct Box {
//			Box() : data(0) {}
//			int data;
//		};
//
//		STATE(StateA)
//
//		void event1();
//
//	 private:
//		void entry();
//		void exit();
//		void init(int i);
//	};
//
//	SUBSTATE(StateB, Super) {
//		STATE(StateB)
//
//		void event2();
//
//	private:
//		void entry();
//		void exit();
//	};
//
//	void Top::entry() { cout << "Top::entry" << endl; }
//	void Top::exit() { cout << "Top::exit" << endl; }
//	void Top::init() { setState<StateA>(42); }
//
//	void Super::entry() { cout << "Super::entry" << endl; }
//	void Super::exit() { cout << "Super::exit" << endl; }
//
//	void StateA::entry() { cout << "StateA::entry" << endl; }
//	void StateA::init(int i) { box().data = i; }
//	void StateA::exit() { cout << "StateA::exit" << endl; }
//	void StateA::event1() { setState<StateB>(); }
//
//	void StateB::entry() { cout << "StateB::entry" << endl; }
//	void StateB::exit() { cout << "StateB::exit" << endl; }
//	void StateB::event2() { setState<StateA>(); }
// }
//
// int main() {
//	Macho::Machine<Example::Top> m;
//	m->event1();
//	m->event2();
//
//	return 0;
// }
//
// Output is:
//
// Top::entry
// Super::entry
// StateA::entry
// StateA::exit
// StateB::entry
// StateB::exit
// StateA::entry
// StateA::exit
// Super::exit
// Top::exit
//
//
// Version History:
//
//	  0.9.7 (released 2007-12-1):
//		 - Introduction of template states
//		 - fixed rare memory leak
//
//	  0.9.6 (released 2007-09-01):
//		 - Changes to state transition semantics (see file
//"changes_0_9_6.txt")
//		 - New mechanism for state initialization
//		 - Runtime reflection on state relationships now possible
//
//	  0.9.5 (released 2007-05-01):
//		 - Introduction of parametrized state transitions
//
//	  0.9.4 (released 2006-06-01):
//		 - Snapshot functionality added
//
//	  0.9.3 (released 2006-04-20):
//		 - Code reorganization (file Macho.cpp added)
//
//	  0.9.2 (released 2006-04-10):
//		 - Memory leak plugged
//		 - MSVC6 version updated
//
//	  0.9.1 (released 2006-03-30):
//		 - Introduction of persistent boxes
//		 - Speed and size optimizations
//		 - Machine instance can be accessed in event handlers with
// method
//"machine"
//
//	  0.9 (released 2006-01-15):
//		 - Introduction of queuable event type
//
//	  0.8.2 (released 2005-12-15):
//		 - Code size reduction by minimizing use of template classes
//
//	  0.8.1 (released 2005-12-01):
//		 - Added MSVC6 variant (see directory "msvc6")
//		 - Added method "clearHistoryDeep"
//
//	  0.8 (released 2005-11-01):
//		 - Initial release
//

#include <cassert>
#include <new>
#include <tuple>
#include <utility>

class TestAccess;

////////////////////////////////////////////////////////////////////////////////
// Various macros for state and history declaration

// Use this macro to define your top state class.
#define TOPSTATE(TOP)                                                          \
  struct TOP : public ::Macho::Link<TOP, ::Macho::TopBase<TOP>>

// Use this macro for all other state classes.
#define SUBSTATE(STATE, SUPERSTATE)                                            \
  struct STATE : public ::Macho::Link<STATE, SUPERSTATE>

// Use this macro for template states that receive an anchor as template
// parameter.
#define TSUBSTATE(STATE, SUPERSTATE)                                           \
  struct STATE : public ::Macho::Link<STATE<typename SUPERSTATE::ANCHOR>,      \
                                      typename SUPERSTATE::SELF>

// Use this macro in your class definition to give it state functionality
// (mandatory). If you have a state box declare it BEFORE macro invocation!
#define STATE(S)                                                               \
public:                                                                        \
  typedef S SELF;                                                              \
  typedef S ANCHOR; /* Anchor is the first non-template state in the           \
                       inheritance chain */                                    \
  /* Constructor and destructor already defined: you can't (and shouldn't)     \
   * have your own! */                                                         \
  /* For the user a state class "constructor" and "destructor" are its entry   \
   * and exit method! */                                                       \
  S(::Macho::_StateInstance &instance) : LINK(instance) {}                     \
  ~S() {}                                                                      \
  static const char *_state_name() { return #S; }                              \
  /* Get to your Box with this method: */                                      \
  Box &box() { return *static_cast<Box *>(_box()); }                           \
  friend class ::_VS8_Bug_101615;

// Use this macro in your template class definition to give it state
// functionality
// (mandatory). If you have a state box declare it BEFORE macro invocation!
#define TSTATE(S)                                                              \
  typedef S SELF;                                                              \
  typedef typename S::SUPER SUPER;                                             \
  typedef typename S::TOP TOP;                                                 \
  typedef typename S::ANCHOR                                                   \
      ANCHOR; /* Anchor is the first non-template state in the inheritance     \
                 chain */                                                      \
  typedef ::Macho::Link<S, SUPER> LINK;                                        \
  S(::Macho::_StateInstance &instance) : LINK(instance) {}                     \
  ~S() {}                                                                      \
  static const char *_state_name() { return #S; }                              \
  typename S::Box &box() {                                                     \
    return *static_cast<typename S::Box *>(this->_box());                      \
  }                                                                            \
  friend class ::_VS8_Bug_101615;                                              \
  using LINK::dispatch;                                                        \
  using LINK::machine;                                                         \
  /* must have these methods to quieten gcc */                                 \
  template <class U, class... P> void setState(const P... p) {                 \
    LINK::template setState<U, P...>(p...);                                    \
  }                                                                            \
  template <class U> void setStateHistory() {                                  \
    LINK::template setStateHistory<U>();                                       \
  }                                                                            \
  void setState(const class Alias &state) { LINK::setState(state); }

// Use this macro to select deep history strategy.
#define DEEPHISTORY()                                                          \
private:                                                                       \
  /* If no superstate has history, SUPER::_setHistorySuper is a NOOP */        \
  virtual void _saveHistory(::Macho::_StateInstance &self,                     \
                            ::Macho::_StateInstance &shallow,                  \
                            ::Macho::_StateInstance &deep) {                   \
    self.setHistory(&deep);                                                    \
    SELF::SUPER::_setHistorySuper(self, deep);                                 \
  }                                                                            \
                                                                               \
protected:                                                                     \
  /* Substates may use _setHistorySuper to bubble up history */                \
  virtual void _setHistorySuper(::Macho::_StateInstance &self,                 \
                                ::Macho::_StateInstance &deep) {               \
    self.setHistorySuper(deep);                                                \
  }                                                                            \
                                                                               \
public:

// Use this macro to select shallow history strategy.
#define HISTORY()                                                              \
private:                                                                       \
  /* If no superstate has history, SUPER::_setHistorySuper is a NOOP */        \
  virtual void _saveHistory(::Macho::_StateInstance &self,                     \
                            ::Macho::_StateInstance &shallow,                  \
                            ::Macho::_StateInstance &deep) {                   \
    self.setHistory(&shallow);                                                 \
    SELF::SUPER::_setHistorySuper(self, deep);                                 \
  }                                                                            \
                                                                               \
protected:                                                                     \
  /* Substates may use _setHistorySuper to bubble up history */                \
  virtual void _setHistorySuper(::Macho::_StateInstance &self,                 \
                                ::Macho::_StateInstance &deep) {               \
    self.setHistorySuper(deep);                                                \
  }                                                                            \
                                                                               \
public:

// Use this macro to have boxes survive state transitions
#define PERSISTENT()                                                           \
private:                                                                       \
  virtual void _deleteBox(::Macho::_StateInstance &instance) {}                \
                                                                               \
public:

////////////////////////////////////////////////////////////////////////////////
// Everything else is put into namespace 'Macho'.
// Some identifiers are prefixed with an underscore to prevent name clashes with
// deriving classes or to mark things as library internal. Don't touch things
// with an underscore prefix!
namespace Macho {

class _MachineBase;

template <class T> class Machine;

template <class T> class IEvent;

class _StateInstance;

// Unique identifier of states, build from consecutive integers.
// Use Alias to get to ID.
typedef unsigned int ID;

// Key is used to build Alias object (points to _KeyData).
typedef void *Key;

////////////////////////////////////////////////////////////////////////////////
// Metaprogramming tools

// Check type equality at compile time.
template <class T, class U> struct _SameType {};

template <class T> struct _SameType<T, T> { typedef bool Check; };

// Remove reference modifier from type.
template <class R> struct DR { typedef R T; };

template <class R> struct DR<R &> { typedef R T; };

template <class R> struct DR<const R &> { typedef R T; };

////////////////////////////////////////////////////////////////////////////////
// Superstate for template states: allows multiple numbered instances of the
// same
// template state for a single anchor state.
template <class T, int I> struct Anchor : public T {
  typedef Anchor<T, I> SELF;
  typedef SELF ANCHOR;
  enum { NUMBER = I };

protected:
  Anchor(_StateInstance &instance) : T(instance) {}
};

////////////////////////////////////////////////////////////////////////////////
// Box for states which don't declare own Box class.
class _EmptyBox {
  _EmptyBox() {}

public:
  static _EmptyBox theEmptyBox;
};

////////////////////////////////////////////////////////////////////////////////
// Helper functions for box creation
template <class B> void *_createBox(void *&place) {
  if (!place)
    place = ::operator new(sizeof(B));

  new (place) B;

  void *box = place;
  place = 0;

  return box;
}

template <class B> void _deleteBox(void *&box, void *&place) {
  assert(box);
  assert(!place);

  static_cast<B *>(box)->~B();
  place = box;
  box = 0;
}

#ifdef MACHO_SNAPSHOTS
template <class B> void *_cloneBox(void *other) {
  assert(other);
  return new B(*static_cast<B *>(other));
}
#endif

// Specializations for EmptyBox:
// EmptyBox object gets reused over and over and never is deleted.
template <> void *_createBox<_EmptyBox>(void *&place);

template <> void _deleteBox<_EmptyBox>(void *&box, void *&place);

#ifdef MACHO_SNAPSHOTS
template <> void *_cloneBox<_EmptyBox>(void *other);
#endif

////////////////////////////////////////////////////////////////////////////////
// Essential information pointed at by state key.
struct _KeyData {
  typedef _StateInstance &(*Generator)(_MachineBase &machine);
  typedef bool (*Predicate)(Key);
  typedef const char *(*NameFn)();

  // Get StateInstance object from key.
  const Generator instanceGenerator;

  // Is state of given key a child state?
  const Predicate childPredicate;

  const NameFn name;
  const ID id;
};

////////////////////////////////////////////////////////////////////////////////
// Base class for all state classes.
// Also serves as 'Root' state. By entering this state we trigger entry
// and exit actions of user's top state.
class _StateSpecification {
public:
  virtual ~_StateSpecification() {}

  static bool isChild(Key key) { return false; }

protected:
  _StateSpecification(_StateInstance &instance) : _myStateInstance(instance) {}

  // Initiate transition to a new state.
  // Template parameter S is the new state to enter.
  // Transition is performed AFTER control flow returns to the Machine object.
  // Initiating more than one transition is considered an error!
  // The new state may receive parameters for its 'init' methods:
  // setState<StateA>("someData");
  template <class S, class... P> void setState(const P... p);

  // Initiate transition to a state's history.
  // If state has no history, transition is to the state itself.
  template <class S> void setStateHistory();

  // Initiate transition to a new state.
  // Parameter 'state' is the new state to enter.
  // See above and class 'Alias' for more information.
  void setState(const class Alias &state);

  // Deprectated!
  template <class S> void setStateBox(typename S::Box *box = 0);

  // Deprectated!
  template <class S> void setStateDirect(typename S::Box *box = 0);

  // 'Restore from snapshot' event: set current state.
  // Default implementation: Does not trigger entry actions!
  virtual void _restore(_StateInstance &current);

  // only to be used in _restore
  void setState(_StateInstance &current);

  // 'Shutdown machine' event: exit all states.
  // Default implementation: Triggers exit actions!
  // Override empty to omit calling exit actions.
  virtual void _shutdown();

  // This is the method to bubble up history information
  // for states whose superstates have no history (so does nothing).
  virtual void _setHistorySuper(_StateInstance &self, _StateInstance &deep) {}

private:
  // State exit. Not allowed to initiate state change.
  virtual void exit() {}

  // State entry. Not allowed to initiate state change.
  virtual void entry() {}

  // Special kind of state entry: Upon transition to a new state,
  // entry methods of that state and its superstates are called;
  // 'init' however is called only on the one state the transition
  // actually goes to.
  // Is allowed to change state (to child states).
  virtual void init() {}

private:
  // C++ needs something like package visibility

  // for _myStateInstance
  template <class T> friend class TopBase;

  // for _getInstance
  template <class C, class P> friend class Link;

  friend class _StateInstance;
  friend class _RootInstance;

  friend class _MachineBase;

  // Create StateInstance object of state.
  static _StateInstance &_getInstance(_MachineBase &machine);

  virtual void _deleteBox(_StateInstance &instance) {}

  // Default history strategy (no history).
  virtual void _saveHistory(_StateInstance &self, _StateInstance &shallow,
                            _StateInstance &deep) {}

private:
  _StateInstance &_myStateInstance;
};

////////////////////////////////////////////////////////////////////////////////
// Base class for user defined top state (and indirectly all other states).
template <class T> class TopBase : public _StateSpecification {
public:
  // This typedef is an alias for user defined top state in all (sub)states.
  typedef T TOP;

protected:
  TopBase(_StateInstance &instance) : _StateSpecification(instance) {}

  void dispatch(IEvent<TOP> *event);

  _MachineBase &machine();
};

////////////////////////////////////////////////////////////////////////////////
// This class links substate specifications to superstate specifications by
// deriving from the superstate and being derived from by the substate.
// Substates inherit event handlers from superstates for reuse or redefinition
// this way.
template <class C, class P> class Link : public P {
public:
  // Alias for superstate.
  typedef P SUPER;

  // Alias for topstate.
  typedef typename P::TOP TOP;

  // Default box type.
  typedef _EmptyBox Box;

  // Key is used to build Alias.
  static Key key();

  // Alias represents state.
  static Alias alias();

  static bool isChild(Key other) {
    return key() == other || SUPER::isChild(other);
  }

  static bool isParent(Key other) {
    return static_cast<_KeyData *>(other)->childPredicate(key());
  }

  // Is machine m in this state?
  static bool isCurrent(const _MachineBase &m);

  // Deprecated!
  // Is machine m in exactly this state?
  static bool isCurrentDirect(const _MachineBase &m);

  static void clearHistory(_MachineBase &m);

  static void clearHistoryDeep(_MachineBase &m);

  static Alias history(const _MachineBase &m);

protected:
  // Needed to perform compile time checks.
  typedef Link<C, P> LINK;

  Link(_StateInstance &instance);

  // These definitions seem redundant but they are not!
  // They override parent definitions so each substate gets either
  // this default or their own, but never its parents definitions.
  virtual void entry() {}
  virtual void init() {}
  virtual void exit() {}

  // This method keeps '_myStateInstance' attribute private.
  void *_box();

private:
  // for _getInstance
  template <class U, class V> friend class Link;

  // for _getInstance
  friend class _StateSpecification;

  // for _getInstance
  friend class Machine<TOP>;

  // for _getInstance
  friend class Alias;

  // for Tests
  friend class ::TestAccess;

  // Create StateInstance object of state.
  static _StateInstance &_getInstance(_MachineBase &machine);

  // Box is by default not persistent. Not redundant!
  virtual void _deleteBox(_StateInstance &instance);

  // Default history strategy (no history). Not redundant!
  virtual void _saveHistory(_StateInstance &self, _StateInstance &shallow,
                            _StateInstance &deep) {
    // Bubble up history. If no superstate has history, _setHistorySuper will do
    // nothing.
    this->_setHistorySuper(self, deep);
  }

private:
  _StateInstance &_myStateInstance;
};

////////////////////////////////////////////////////////////////////////////////
// Unique identifier for state S.
template <class S> class StateID {
public:
  static const ID value;
};

////////////////////////////////////////////////////////////////////////////////
// StateInstance maintains machine specific data about a state. Keeps history,
// box
// and state object for state. StateInstance object is created the first time
// state
// is entered. There is at most one StateInstance object per state per machine
// instance.
class _StateInstance {
protected:
  _StateInstance(_MachineBase &machine, _StateInstance *parent);

public:
  virtual ~_StateInstance();

  // Perform entry actions.
  // 'first' is true on very first call.
  void entry(_StateInstance &previous, bool first = true);

  // Perform exit actions.
  void exit(_StateInstance &next);

  // Perform init action.
  void init(bool history);

  void saveHistory(_StateInstance &shallow, _StateInstance &deep) {
    // Check state's history strategy.
    mySpecification->_saveHistory(*this, shallow, deep);
  }

  // Update superstate's history information:
  void setHistorySuper(_StateInstance &deep) {
    if (myParent)
      // Let it choose between deep or shallow history.
      myParent->saveHistory(*this, deep);
  }

#ifdef MACHO_SNAPSHOTS
  // Copy state of another StateInstance object.
  void copy(_StateInstance &original);

  // Create a clone of StateInstance object for another machine.
  _StateInstance *clone(_MachineBase &newMachine);
#endif

  void shutdown() { mySpecification->_shutdown(); }

  void restore(_StateInstance &instance) {
    mySpecification->_restore(instance);
  }

  virtual ID id() = 0;

  virtual Key key() = 0;

  virtual const char *name() = 0;

  // 'Virtual constructor' needed for cloning.
  virtual _StateInstance *create(_MachineBase &machine,
                                 _StateInstance *parent) = 0;

  virtual void createBox() = 0;
  virtual void deleteBox() = 0;
#ifdef MACHO_SNAPSHOTS
  virtual void cloneBox(void *box) = 0;
#endif

  // Only needed for top state (constructor of Machine calls this)
  void setBox(void *box) {
    assert(!myBox);

    if (myBoxPlace) {
      // Free cached memory of previously used box.
      ::operator delete(myBoxPlace);
      myBoxPlace = 0;
    }

    myBox = box;
  }

  // Is 'instance' a superstate?
  bool isChild(const _StateInstance &instance) {
    return this == &instance || (myParent && myParent->isChild(instance));
  }

  _StateSpecification &specification() {
    assert(mySpecification);
    return *mySpecification;
  }

  void *box() {
    assert(myBox);
    return myBox;
  }

  _MachineBase &machine() { return myMachine; }

  // const: History can be manipulated even on a const object.
  void setHistory(_StateInstance *history) const { myHistory = history; }

  _StateInstance *history() const { return myHistory; }

protected:
  _MachineBase &myMachine;
  _StateSpecification *mySpecification; // Instance of state class
  mutable _StateInstance *myHistory;
  _StateInstance *myParent;
  void *myBox;
  void *myBoxPlace; // Reused box heap memory
};

////////////////////////////////////////////////////////////////////////////////
// StateInstance for Root state (the real top state).
class _RootInstance : public _StateInstance {
protected:
  friend class _StateSpecification;

  _RootInstance(_MachineBase &machine, _StateInstance *parent)
      : _StateInstance(machine, parent) {
    mySpecification = new _StateSpecification(*this);
  }

public:
  virtual ID id() { return 0; }

  virtual Key key() {
    // Can't happen: key is only called by users, and they don't know about
    // Root.
    assert(false);
    return 0;
  }

  virtual void createBox() {}
  virtual void deleteBox() {}
#ifdef MACHO_SNAPSHOTS
  virtual void cloneBox(void *box) {}
#endif

  virtual const char *name() { return "Root"; }

  // 'Virtual constructor' needed for cloning.
  virtual _StateInstance *create(_MachineBase &machine,
                                 _StateInstance *parent) {
    return new _RootInstance(machine, parent);
  }
};

////////////////////////////////////////////////////////////////////////////////
// StateInstance for substates (including Top ;-)
// Has methods to create state specific objects.
template <class S> class _SubstateInstance : public _StateInstance {
protected:
  template <class C, class P> friend class Link;

  _SubstateInstance(_MachineBase &machine, _StateInstance *parent)
      : _StateInstance(machine, parent) {
    assert(parent);
    this->mySpecification = new S(*this);
  }

public:
  typedef typename S::Box Box;

  virtual ~_SubstateInstance() {
    if (this->myBox)
      Macho::_deleteBox<Box>(myBox, myBoxPlace);
  }

  virtual const char *name() { return S::_state_name(); }

  virtual ID id() { return StateID<S>::value; }

  virtual Key key() { return S::key(); }

  // 'Virtual constructor' needed for cloning.
  virtual _StateInstance *create(_MachineBase &machine,
                                 _StateInstance *parent) {
    return new _SubstateInstance<S>(machine, parent);
  }

  virtual void createBox() {
    if (!this->myBox)
      this->myBox = Macho::_createBox<Box>(myBoxPlace);
  }

  virtual void deleteBox() {
    assert(myBox);
    Macho::_deleteBox<Box>(myBox, myBoxPlace);
  }

#ifdef MACHO_SNAPSHOTS
  virtual void cloneBox(void *box) {
    assert(!myBox);
    assert(!myBoxPlace);
    // Needs copy constructor in ALL box types.
    myBox = Macho::_cloneBox<Box>(box);
  }
#endif
};

////////////////////////////////////////////////////////////////////////////////
// Definitions for queuable event types

// Generic interface for event objects (available only to MachineBase)
class _IEventBase {
public:
  virtual ~_IEventBase() {}
  virtual void dispatch(_StateInstance &) = 0;
};

// Interface for event objects (bound to a top state)
template <class TOP> class IEvent : protected _IEventBase {
  friend class Machine<TOP>;
  friend class TopBase<TOP>;
};

template <class TOP, class R, class... P> class _Event : public IEvent<TOP> {
  typedef R (TOP::*Signature)(P...);

public:
  _Event(Signature handler, const typename DR<P>::T... p)
      : myHandler(handler), tuple_(std::tuple<typename DR<P>::T...>(p...)) {}

protected:
  void dispatch(_StateInstance &instance) {
    callDispatchWithTuple(tuple_, instance,
                          std::index_sequence_for<typename DR<P>::T...>());
  }

  Signature myHandler;

private:
  template <std::size_t... Is>
  void callDispatchWithTuple(const std::tuple<P...> &tuple,
                             _StateInstance &instance,
                             std::index_sequence<Is...>) {
    TOP &behaviour = static_cast<TOP &>(instance.specification());
    (behaviour.*myHandler)(std::get<Is>(tuple)...);
  }

  std::tuple<typename DR<P>::T...> tuple_;
};

// // Event creating functions using type inference
template <class... P, class R, class TOP>
inline IEvent<TOP> *Event(R (TOP::*handler)(P...),
                          const typename DR<P>::T... p) {
  return new _Event<TOP, R, P...>(handler, p...);
}

} // namespace Macho

////////////////////////////////////////////////////////////////////////////////
// MSVC++ 8.0 does not handle qualified member template friends:
// http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=101615
// Otherwise call could happen directly in Initializer classes.
class _VS8_Bug_101615 {
public:
  template <class S, class... P>
  static inline void execute(Macho::_StateInstance &instance, const P... p) {
    S &behaviour = static_cast<S &>(instance.specification());
    behaviour.init(p...);
  }
};

namespace Macho {

////////////////////////////////////////////////////////////////////////////////
// Base class for state initializers.
// Initializer are used to provide parameters to states.
// The 'execute' method of Initializers will call a state's init method with
// the data of the initializer object.
class _Initializer {
public:
  virtual ~_Initializer() {}

  // Create copy of initializer.
  virtual _Initializer *clone() = 0;

  // Deallocate object.
  virtual void destroy() { delete this; }

  virtual Key adapt(Key key) { return key; }

  // Initialize given state. State is new current state of a state machine.
  virtual void execute(_StateInstance &instance) = 0;
};

// Base class for Singleton initializers.
class _StaticInitializer : public _Initializer {
  // Copy of Singleton is Singleton.
  virtual _Initializer *clone() { return this; }

  // Singletons are never destroyed.
  virtual void destroy() {}
};

// Default initializer: provides no parameters, calls state's 'init' method
// only.
class _DefaultInitializer : public _StaticInitializer {
public:
  virtual void execute(_StateInstance &instance) { instance.init(false); }
};

// History initializer: provides no parameters, performs transition to
// history of state if available.
class _HistoryInitializer : public _StaticInitializer {
public:
  virtual void execute(_StateInstance &instance) { instance.init(true); }
};

// Special initializer: Helps alias impersonate as history state of given state.
class _AdaptingInitializer : public _Initializer {
public:
  _AdaptingInitializer(const _MachineBase &machine) : myMachine(machine) {}

  virtual void execute(_StateInstance &instance) { instance.init(true); }

  virtual _Initializer *clone() { return new _AdaptingInitializer(myMachine); }

  virtual Key adapt(Key key);

protected:
  const _MachineBase &myMachine;
};

template <class S, class... P> class _InitializerMain : public _Initializer {
public:
  _InitializerMain(P... p) : tuple_(std::tuple<P...>(p...)) {}

  virtual _Initializer *clone() {
    return cloneWithTuple(tuple_, std::index_sequence_for<P...>());
  }

  virtual void execute(_StateInstance &instance) {
    callExecuteWithTuple(tuple_, instance, std::index_sequence_for<P...>());
  }

private:
  // The helper method.
  template <std::size_t... Is>
  void callExecuteWithTuple(const std::tuple<P...> &tuple,
                            _StateInstance &instance,
                            std::index_sequence<Is...>) {
    ::_VS8_Bug_101615::execute<S, P...>(instance, std::get<Is>(tuple)...);
  }

  template <std::size_t... Is>
  _Initializer *cloneWithTuple(const std::tuple<P...> &tuple,
                               std::index_sequence<Is...>) {
    return new _InitializerMain<S, P...>(std::get<Is>(tuple)...);
  }

  std::tuple<P...> tuple_;
};

////////////////////////////////////////////////////////////////////////////////
// Singleton initializers.
static _DefaultInitializer _theDefaultInitializer;
static _HistoryInitializer _theHistoryInitializer;

////////////////////////////////////////////////////////////////////////////////
// Base class for Machine objects.
class _MachineBase {
public:
  class Alias currentState() const;

protected:
  _MachineBase();
  ~_MachineBase();

  // Transition to new state.
  void setState(_StateInstance &instance, _Initializer *init);

  // Transition to new state specified by state alias.
  void setState(const Alias &state);

  // Prepare transition to new state (performed on call to 'rattleOn').
  // There can be only one state transition pending (asserts otherwise)!
  // 'init' is an initializer for the new state.
  void setPendingState(_StateInstance &instance, _Initializer *init) {
    assert((!myPendingState ||
            (myPendingState == &instance && myPendingInit == init)) &&
           "There is already a state transition pending!");

    myPendingState = &instance;
    myPendingInit = init;
  }

  // Provide event object to be executed on current state.
  void setPendingEvent(_IEventBase *event) {
    assert(event);
    assert(!myPendingEvent && "There is already an event pending!");

    myPendingEvent = event;
  }

  // Performs pending state transition.
  void rattleOn();

  // Get StateInstance object for ID.
  _StateInstance *&getInstance(ID id) { return myInstances[id]; }

  // Get StateInstance object for ID.
  const _StateInstance *getInstance(ID id) const { return myInstances[id]; }

  // Starts the machine with the specified start state.
  void start(_StateInstance &instance);
  void start(const Alias &state);

  // Shuts machine down. Will exit any states and free all allocated
  // resources.
  void shutdown();

  // Allocate space for pointers to StateInstance objects.
  void allocate(unsigned int count);

  // Free all StateInstance objects.
  void free(unsigned int count);

  void clearHistoryDeep(unsigned int count, const _StateInstance &instance);

#ifdef MACHO_SNAPSHOTS
  // Create a copy of another machines StateInstance objects (includes boxes).
  void copy(_StateInstance **other, unsigned int count);

  // Create a copy of another machines StateInstance object.
  _StateInstance *createClone(ID id, _StateInstance *original);
#endif

protected:
  // C++ needs something like package visibility

  // for getInstance
  template <class C, class P> friend class Link;

  // for setPendingEvent
  template <class T> friend class TopBase;

  // for getInstance
  friend class _StateSpecification;

  // for getInstance
  friend class Alias;

  // for getInstance
  friend class _AdaptingInitializer;

  // for setPendingState
  friend class _StateInstance;

  // for Tests
  friend class ::TestAccess;

  // Current state of Machine object.
  _StateInstance *myCurrentState;

  // Information about pending state transition.
  _StateInstance *myPendingState;
  _Initializer *myPendingInit;

  // Deprecated!
  void *myPendingBox;

  _IEventBase *myPendingEvent;

  // Array of StateInstance objects.
  _StateInstance **myInstances;
};

////////////////////////////////////////////////////////////////////////////////
// This is the base class for state aliases. A state alias represents a
// state of a machine. A transition to that state can be initiated by
// giving the alias object to the 'setState' method.
//
// State aliases are created by the template functions 'State' further below.
// Parameters can be provided to these functions that will be used to
// initialize the state on transition to it.
class Alias {
public:
  explicit Alias(Key key, bool history = false)
      : myStateKey(key),
        myInitializer(
            history ? static_cast<_Initializer *>(&_theHistoryInitializer)
                    : static_cast<_Initializer *>(&_theDefaultInitializer)) {
    assert(key);
  }

  Alias(Key key, _Initializer *init) : myStateKey(key), myInitializer(init) {
    assert(key);
  }

  Alias(const Alias &other)
      : myStateKey(other.myStateKey),
        myInitializer(other.myInitializer->clone()) {}

  Alias &operator=(const Alias &other) {
    if (this == &other)
      return *this;

    myInitializer->destroy();

    myStateKey = other.myStateKey;
    myInitializer = other.myInitializer->clone();

    return *this;
  }

  ~Alias() { myInitializer->destroy(); }

  operator Key() const { return key(); }

  bool isChild(Key k) const { return key()->childPredicate(k); }

  bool isParent(Key k) const {
    return static_cast<_KeyData *>(k)->childPredicate(key());
  }

  const char *name() const { return key()->name(); }

  ID id() const { return key()->id; }

protected:
  friend class _MachineBase;
  friend class _StateSpecification;

  void setState(_MachineBase &machine) const;

  _KeyData *key() const {
    return static_cast<_KeyData *>(myInitializer->adapt(myStateKey));
  }

protected:
  // Key of specified state.
  Key myStateKey;

  // Initializer of this alias.
  _Initializer *myInitializer;
};

// Deprecated: alias for Alias
typedef Alias StateAlias;

// Create alias with any amount parameters.
template <class S, class... P> Alias State(const P... p) {
  return Alias(S::key(), new _InitializerMain<S, P...>(p...));
}

// Create alias for state's history: not the current history state, but
// really the history of a state. This means that the alias may point to
// different states during its life. Needs a machine instance to take history
// from.
template <class S> Alias StateHistory(const _MachineBase &machine) {
  return Alias(S::key(), new _AdaptingInitializer(machine));
}

////////////////////////////////////////////////////////////////////////////////
// Snapshot of a machine object.
// Saves the state of a machine object at a specific point in time to be
// restored
// later (can be used to achieve something like backtracking).
// Includes boxes of current state and persistent boxes.
// Assign a snapshot to a machine (operator=) to restore state.
// Note that no exit/entry actions of the overwritten machine state are
// performed!
// Box destructors however are executed!
#ifdef MACHO_SNAPSHOTS
template <class TOP> class Snapshot : public _MachineBase {
public:
  Snapshot(Machine<TOP> &machine);

  ~Snapshot() { free(Machine<TOP>::theStateCount); }

private:
  friend class Machine<TOP>;

  Snapshot(const Snapshot<TOP> &other);
  Snapshot &operator=(const Snapshot<TOP> &other);
};
#endif

////////////////////////////////////////////////////////////////////////////////
// A Machine object maintains a current state.
// The state can be any substate of template parameter TOP.
// TOP is the Machine's top most and inital state. TOP must be defined by
// the macro TOPSTATE. Event processing is done by calling methods (event
// handlers) on the current state.
// This is realized by defining an arrow ('->') operator on Machine,
// forwarding to the interface of TOP.
// Every possible event handler to be called must therefore appear in the
// interface of TOP. Events are dispatched by using this operator on a
// Machine object (e.g. 'machine->event()').
template <class TOP> class Machine : public _MachineBase {
public:
  // This class performs an action in its destructor after an event
  // handler has finished. Comparable to an After Advice in AOP.
  struct AfterAdvice {
    AfterAdvice(Machine<TOP> &m) : myMachine(m) {}

    // Event handler has finished execution. Execute pending transitions now.
    ~AfterAdvice() { myMachine.rattleOn(); }

    // this arrow operator finally dispatches to TOP interface.
    TOP *operator->() {
      return static_cast<TOP *>(&(myMachine.myCurrentState->specification()));
    }

  private:
    Machine<TOP> &myMachine;
  };

  // State machine instance can be initialized with a top state box.
  Machine(typename TOP::Box *box = 0) {
    // Compile time check: TOP must directly derive from TopBase<TOP>
    typedef typename _SameType<TopBase<TOP>, typename TOP::SUPER>::Check
        MustDeriveFromTopBase;

    allocate(theStateCount);

    _StateInstance &top = TOP::_getInstance(*this);
    top.setBox(box);

    start(top);
  }

  // Initialize with a state alias object to have machine go to a state
  // other than TOP on startup. Box of top state may also be initialized.
  Machine(const Alias &state, typename TOP::Box *box = 0) {
    // Compile time check: TOP must directly derive from TopBase<TOP>
    typedef typename _SameType<TopBase<TOP>, typename TOP::SUPER>::Check
        MustDeriveFromTopBase;

    allocate(theStateCount);

    _StateInstance &top = TOP::_getInstance(*this);
    top.setBox(box);

    start(state);
  }

#ifdef MACHO_SNAPSHOTS
  // Create machine from a snapshot.
  Machine(const Snapshot<TOP> &snapshot) {
    allocate(theStateCount);
    copy(snapshot.myInstances, theStateCount);
  }

  // Overwrite current machine state by snapshot.
  Machine<TOP> &operator=(const Snapshot<TOP> &snapshot) {
    assert(!myPendingState);
    assert(!myPendingEvent);

    myCurrentState->shutdown();

    free(theStateCount);
    copy(snapshot.myInstances, theStateCount);

    // Go to Root state first
    myCurrentState = getInstance(0);

    // Then set previous current state
    _StateInstance *current = getInstance(snapshot.myCurrentState->id());
    current->restore(*current);
    rattleOn();

    return *this;
  }
#endif

  ~Machine() {
    myCurrentState->shutdown();
    free(theStateCount);
  }

  // Don't return pointer to interface right now: we need to know when the
  // event handler has finished; return an AfterAdvice object instead:
  // it allows us to perform actions after access.
  AfterAdvice operator->() {
    assert(myCurrentState);
    assert(!myPendingState);

    // We need to know when the event handler has finished.
    return AfterAdvice(*this);
  }

  // Dispatch an event object to machine.
  void dispatch(IEvent<TOP> *event, bool destroy = true) {
    assert(event);

    event->dispatch(*myCurrentState);
    if (destroy)
      delete event;

    rattleOn();
  }

  // Allow (const) access to top state's box (for state data extraction).
  const typename TOP::Box &box() const {
    assert(myCurrentState);
    return static_cast<TOP &>(myCurrentState->specification()).TOP::box();
  }

private:
  template <class C, class P> friend class Link;

private:
  Machine(const Machine<TOP> &other);
  Machine<TOP> &operator=(const Machine<TOP> &other);

#ifdef MACHO_SNAPSHOTS
  friend class Snapshot<TOP>;
#endif

  template <class T> friend class StateID;

  // Next free identifier for StateInstance objects.
  static ID theStateCount;
};

// Root is always there and has ID 0, so start from 1
template <class TOP> ID Machine<TOP>::theStateCount = 1;

// Each state has a unique ID number.
// The identifiers are consecutive integers starting from zero,
// which allows use as index into a vector for fast access.
// 'Root' always has zero as id.
template <class S>
const ID StateID<S>::value = Machine<typename S::TOP>::theStateCount++;

////////////////////////////////////////////////////////////////////////////////
// Implementation for StateSpecification

// Initiate state transition with any amount parameters.
template <class S, class... P>
void _StateSpecification::setState(const P... p) {
  _MachineBase &m = _myStateInstance.machine();
  _StateInstance &instance = S::_getInstance(m);
  m.setPendingState(instance, new _InitializerMain<S, P...>(p...));
}

// Initiate state transition to a state's history.
template <class S> inline void _StateSpecification::setStateHistory() {
  _MachineBase &m = _myStateInstance.machine();
  _StateInstance &instance = S::_getInstance(m);
  m.setPendingState(instance, &_theHistoryInitializer);
}

// Deprecated!
template <class S>
inline void _StateSpecification::setStateBox(typename S::Box *box) {
  _MachineBase &m = _myStateInstance.machine();
  _StateInstance &instance = S::_getInstance(m);
  m.myPendingBox = box;
  m.setPendingState(instance, &_theHistoryInitializer);
}

// Deprecated!
template <class S>
inline void _StateSpecification::setStateDirect(typename S::Box *box) {
  _MachineBase &m = _myStateInstance.machine();
  _StateInstance &instance = S::_getInstance(m);
  m.myPendingBox = box;
  m.setPendingState(instance, &_theDefaultInitializer);
}

////////////////////////////////////////////////////////////////////////////////
// Implementation for TopBase
template <class T> inline void TopBase<T>::dispatch(IEvent<TOP> *event) {
  assert(event);
  _myStateInstance.machine().setPendingEvent(event);
}

template <class T>
// Returns current state machine instance.
inline _MachineBase &TopBase<T>::machine() {
  return this->_myStateInstance.machine();
}

////////////////////////////////////////////////////////////////////////////////
// Implementation for Link
template <class C, class P>
inline Link<C, P>::Link(_StateInstance &instance)
    : P(P::_getInstance(instance.machine()))
      // Can't initialize _myStateInstance with _getInstance,
      // because this would result in an endless loop (at least for first call)
      ,
      _myStateInstance(instance) {}

// This method keeps '_myStateInstance' attribute private.
template <class C, class P> inline void *Link<C, P>::_box() {
  return _myStateInstance.box();
}

// Default behaviour: free box on exit.
template <class C, class P>
inline void Link<C, P>::_deleteBox(_StateInstance &instance) {
  instance.deleteBox();
}

// Create StateInstance object of state.
template <class C, class P>
/* static */ inline _StateInstance &
Link<C, P>::_getInstance(_MachineBase &machine) {
  // Look first in machine for existing StateInstance.
  _StateInstance *&instance = machine.getInstance(StateID<C>::value);
  if (!instance)
    // Will create parent StateInstance object if not already created.
    instance = new _SubstateInstance<C>(machine, &P::_getInstance(machine));

  return *instance;
}

template <class C, class P>
/* static */ inline bool Link<C, P>::isCurrent(const _MachineBase &machine) {
  return machine.currentState().isChild(key());
}

// Deprecated!
template <class C, class P>
/* static */ inline bool
Link<C, P>::isCurrentDirect(const _MachineBase &machine) {
  return key() == machine.currentState();
}

template <class C, class P>
/* static */ void Link<C, P>::clearHistory(_MachineBase &machine) {
  const _StateInstance *instance = machine.getInstance(StateID<C>::value);
  if (instance)
    instance->setHistory(0);
}

template <class C, class P>
/* static */ void Link<C, P>::clearHistoryDeep(_MachineBase &machine) {
  const _StateInstance *instance = machine.getInstance(StateID<C>::value);
  if (instance)
    machine.clearHistoryDeep(Machine<TOP>::theStateCount, *instance);
}

template <class C, class P>
/* static */ Alias Link<C, P>::history(const _MachineBase &machine) {
  const _StateInstance *instance = machine.getInstance(StateID<C>::value);
  _StateInstance *history = 0;

  if (instance)
    history = instance->history();

  return Alias(history ? history->key() : key());
}

template <class C, class P>
/* static */ inline Key Link<C, P>::key() {
  static _KeyData k = {_getInstance, isChild, C::_state_name,
                       StateID<C>::value};
  return &k;
}

template <class C, class P>
/* static */ inline Alias Link<C, P>::alias() {
  return Alias(key());
}

////////////////////////////////////////////////////////////////////////////////
// Implementation for Snapshot
#ifdef MACHO_SNAPSHOTS
template <class TOP> Snapshot<TOP>::Snapshot(Machine<TOP> &machine) {
  assert(!machine.myPendingState);
  assert(!machine.myPendingEvent);
  assert(machine.myCurrentState);

  allocate(Machine<TOP>::theStateCount);
  copy(machine.myInstances, Machine<TOP>::theStateCount);

  myCurrentState = getInstance(machine.myCurrentState->id());
}
#endif

} // namespace Macho

#endif // __MACHO_HPP__