msm.hpp

Go to the documentation of this file.

#ifndef LIBJMMCG_CORE_MSM_HPP
#define LIBJMMCG_CORE_MSM_HPP
/******************************************************************************
** Copyright © 2014 by J.M.McGuiness, coder@hussar.me.uk
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Lesser General Public
** License as published by the Free Software Foundation; either
** version 2.1 of the License, or (at your option) any later version.
**
** This library is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
** Lesser General Public License for more details.
**
** You should have received a copy of the GNU Lesser General Public
** License along with this library; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
 
#include "unordered_tuple.hpp"
 
namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE {
 
/// A meta (or finite)-state machine that can represent UML-style state tables in C++.
/**
   This FSM is a very cut-down version of boost.msm [1,2], but it is much more simple to use!
*/
namespace msm {
 
struct unroll {
 
   /// A convenience class to make the rows a bit smaller when declaring the meta-state machine table.
   template<class States, class EndStates>
   struct row_types {
      using states=States;
      using end_states=EndStates;
 
      /// A row in the meta-state machine table.
      template<
         states Start,  ///< The start state.
         class Event,   ///< The event that will be executed to transition from the start to the next state. Must be a functor. This can only take a single argument in the ctor.
         end_states Next   ///< The state transitioned to.
      >
      class row;
      /// A row in the meta-state machine table that also has a guard.
      template<
         states Start,  ///< The start state.
         class Event,   ///< The event that will be executed to transition from the start to the next state. Must be a functor. This can only take a single argument in the ctor.
         end_states Next,  ///< The state transitioned to.
         class Guard    ///< The guard: if true the transition occurs, otherwise there is no change in state.
      >
      class g_row;
   };
 
   /// Derive from this object to implement your meta-state machine.
   /**
      The state transition table must be called or aliassed to the type state_transition_table to be accessible within this class.
   */
   template<
      class Deriv ///< The derived meta-state machine, that must itself be be stateless.
   >
   class state_transition_table {
   public:
      struct no_op {
         template<class ...Args>
         explicit no_op(Args &&...) noexcept(true) {}
 
         template<auto state, auto next, class ...Args>
         constexpr auto operator()(Args &&...) const noexcept(true) FORCE_INLINE {return next;}
         static constexpr void noop() noexcept(true) {}
      };
 
      /// The derived, implementation of the meta-state table, each row in rows is a state-transition of the meta-sate machine.
      /**
         The derived class must contain a type member called transition_table which implements the meta-state table as a collection of unroll::row_types::row. Note that the last row in the transisiton_table will not have the Start States checked, so will effectively "match all" incoming states.
 
         This technique is used because on gcc v>=8.1.0 it can optimise this into a jump table, so O(1)! (Or as a switch-statement, for O(log(n)).) Sadly clang & icc were baffled (like lower versions of gcc) & just produced the if-chain, for O(n).
 
         \see unroll::row_types::row
      */
      template<class Row, class... Rows>
      class rows;
 
   private:
      state_transition_table()=delete;
   };
 
   /// Instantiate this object to use the created state-machine.
   template<
      class STT   ///< The state transition table, the type derived from state_transition_table, above.
   >
   class machine {
   public:
      using element_type=STT;
      using states=typename element_type::transition_table::states;
      using end_states=typename element_type::transition_table::end_states;
      using rows_t=typename element_type::transition_table;
 
      constexpr machine() noexcept(true)=default;
      template<
         class Arg,
         class... Args,
         class =typename std::enable_if<!std::is_convertible<Arg, machine>::value>::type
      > explicit constexpr
      machine(Arg &&arg, Args &&...args) noexcept(noexcept(rows_t(std::forward<Arg>(arg), std::forward<Args>(args)...)));
      constexpr machine(machine const &) noexcept(noexcept(rows_t(std::declval<rows_t>())));
 
      /// Call this method to perform your state transition from the start state to the next state.
      /**
         Algorithmic complexity: see comment for state_transition_table::rows, above.
 
         \param   s  The start state for the transition to be selected. If s is not found in the state_transition_table, then there is no effect, nothing happens.
         \param   p  The parameters to pass to the event selected by the start state from the state_transition_table.
         \return  The resultant state of the row selected by the input state, s. If the row was a guard-row, then if the guard permitted it the resultant state, otherwise the input state, s.
      */
      template<class... Params>
      constexpr end_states process(states s, Params &&...p) const noexcept(noexcept(std::declval<rows_t>().process(s, std::forward<Params>(p)...)));
 
      /// Call this method to perform your state transition from the start state to the next state.
      /**
         Algorithmic complexity: see comment for rows, above.
 
         \param   s  The start state for the transition to be selected. If s is not found in the state_transition_table, then there is no effect, nothing happens.
         \param   p  The parameters to pass to the event selected by the start state from the state_transition_table.
         \return  The resultant state of the row selected by the input state, s. If the row was a guard-row, then if the guard permitted it the resultant state, otherwise the input state, s.
      */
      template<class... Params>
      constexpr end_states process(states s, Params &&...p) noexcept(noexcept(std::declval<rows_t>().process(s, std::forward<Params>(p)...)));
 
   private:
      rows_t rows_;
   };
 
};
 
/**
   gcc & clang can get somewhat confused when the event has a complex body and can create either if-else chains or switch-statements respectively. So force the compiler to always implement a jump-table instead. 
 
   Consider:
      <a href="https://stackoverflow.com/questions/1777990/is-it-possible-to-store-the-address-of-a-label-in-a-variable-and-use-goto-to-jum"/> and taking the address of labels...
*/
struct jump_table {
 
   /// A convenience class to make the rows a bit smaller when declaring the meta-state machine table.
   template<class States, class EndStates>
   struct row_types {
      using states=States;
      using end_states=EndStates;
 
      /// A row in the meta-state machine table.
      template<
         states Start,  ///< The start state.
         class Event,   ///< The event that will be executed to transition from the start to the next state. Must be a functor. This can only take a single argument in the ctor.
         end_states Next   ///< The state transitioned to.
      >
      class row;
      /// A row in the meta-state machine table that also has a guard.
      template<
         states Start,  ///< The start state.
         class Event,   ///< The event that will be executed to transition from the start to the next state. Must be a functor. This can only take a single argument in the ctor.
         end_states Next,  ///< The state transitioned to.
         class Guard    ///< The guard: if true the transition occurs, otherwise there is no change in state.
      >
      class g_row;
   };
 
   /// Derive from this object to implement your meta-state machine.
   /**
      The state transition table must be called or aliassed to the type state_transition_table to be accessible within this class.
   */
   template<
      class Deriv ///< The derived meta-state machine, that must itself be be stateless.
   >
   class state_transition_table {
   public:
      struct no_op {
         template<class ...Args>
         explicit no_op(Args &&...) noexcept(true) {}
 
         template<auto state, auto next, class ...Args>
         constexpr auto operator()(Args &&...) const noexcept(true) FORCE_INLINE {return next;}
         static constexpr void noop() noexcept(true) {}
      };
 
      /// The derived, implementation of the meta-state table, each row in rows is a state-transition of the meta-sate machine.
      /**
         The derived class must contain a type member called transition_table which implements the meta-state table as a collection of unroll::row_types::row.
 
         This technique is used because on gcc v>=8.1.0 it can optimise this into a jump table, so O(1)! (Or as a switch-statement, for O(log(n)).) Sadly clang & icc were baffled (like lower versions of gcc) & just produced the if-chain, for O(n).
 
         \see unroll::row_types::row
      */
      template<class Row, class... Rows>
      class rows;
 
   private:
      template<class Row, class... Rows>
      class rows_details;
      struct rows_base;
 
      state_transition_table()=delete;
   };
 
   /// Instantiate this object to use the created state-machine.
   template<
      class STT   ///< The state transition table, the type derived from state_transition_table, above.
   >
   class machine {
   public:
      using element_type=STT;
      using states=typename element_type::transition_table::states;
      using end_states=typename element_type::transition_table::end_states;
      using rows_t=typename element_type::transition_table;
 
      constexpr machine() noexcept(true)=default;
      template<
         class Arg,
         class... Args,
         class =typename std::enable_if<!std::is_convertible<Arg, machine>::value>::type
      > explicit constexpr
      machine(Arg &&arg, Args &&...args) noexcept(noexcept(rows_t(std::forward<Arg>(arg), std::forward<Args>(args)...)));
      constexpr machine(machine const &) noexcept(noexcept(rows_t(std::declval<rows_t>())));
 
      /// Call this method to perform your state transition from the start state to the next state.
      /**
         Algorithmic complexity: see comment for rows, above.
 
         \param   s  The start state for the transition to be selected. If s is not found in the state_transition_table, then there is no effect, nothing happens. The states must be uniformly, linearly, increasing in underlying value.
         \param   p  The parameters to pass to the event selected by the start state from the state_transition_table.
         \return  The resultant state of the row selected by the input state, s. If the row was a guard-row, then if the guard permitted it the resultant state, otherwise the input state, s.
      */
      template<class... Params>
      constexpr end_states process(states s, Params &&...p) const noexcept(false);
 
      /// Call this method to perform your state transition from the start state to the next state.
      /**
         Algorithmic complexity: see comment for rows, above.
 
         \param   s  The start state for the transition to be selected. If s is not found in the state_transition_table, then there is no effect, nothing happens. The states must be uniformly, linearly, increasing in underlying value.
         \param   p  The parameters to pass to the event selected by the start state from the state_transition_table.
         \return  The resultant state of the row selected by the input state, s. If the row was a guard-row, then if the guard permitted it the resultant state, otherwise the input state, s.
      */
      template<class... Params>
      constexpr end_states process(states s, Params &&...p) noexcept(false);
 
   private:
      rows_t rows_;
   };
 
};
 
/**
   In this case we shall force the compiler to generate a computed goto. This should be optimal.
*/
struct computed_goto {
 
   /// A convenience class to make the rows a bit smaller when declaring the meta-state machine table.
   template<class States, class EndStates>
   struct row_types {
      using states=States;
      using end_states=EndStates;
 
      /// A row in the meta-state machine table.
      template<
         states Start,  ///< The start state.
         class Event,   ///< The event that will be executed to transition from the start to the next state. Must be a functor. This can only take a single argument in the ctor.
         end_states Next   ///< The state transitioned to.
      >
      class row;
      /// A row in the meta-state machine table that also has a guard.
      template<
         states Start,  ///< The start state.
         class Event,   ///< The event that will be executed to transition from the start to the next state. Must be a functor. This can only take a single argument in the ctor.
         end_states Next,  ///< The state transitioned to.
         class Guard    ///< The guard: if true the transition occurs, otherwise there is no change in state.
      >
      class g_row;
   };
 
   /// Derive from this object to implement your meta-state machine.
   /**
      The state transition table must be called or aliassed to the type state_transition_table to be accessible within this class.
   */
   template<
      class Deriv ///< The derived meta-state machine, that must itself be be stateless.
   >
   class state_transition_table {
   public:
      struct no_op {
         template<class ...Args>
         explicit no_op(Args &&...) noexcept(true) {}
 
         template<auto state, auto next, class ...Args>
         constexpr auto operator()(Args &&...) const noexcept(true) FORCE_INLINE {return next;}
         static constexpr void noop() noexcept(true) {}
      };
 
      /// The derived, implementation of the meta-state table, each row in rows is a state-transition of the meta-sate machine.
      /**
         The derived class must contain a type member called transition_table which implements the meta-state table as a collection of unroll::row_types::row.
 
         This technique is used because on gcc v>=8.1.0 it can optimise this into a jump table, so O(1)! (Or as a switch-statement, for O(log(n)).) Sadly clang & icc were baffled (like lower versions of gcc) & just produced the if-chain, for O(n).
 
         \see unroll::row_types::row
      */
      template<class Row, class... Rows>
      class rows;
 
   private:
      template<class Row, class... Rows>
      class rows_details;
 
      state_transition_table()=delete;
   };
 
   /// Instantiate this object to use the created state-machine.
   template<
      class STT   ///< The state transition table, the type derived from state_transition_table, above.
   >
   class machine {
   public:
      using element_type=STT;
      using states=typename element_type::transition_table::states;
      using end_states=typename element_type::transition_table::end_states;
      using rows_t=typename element_type::transition_table;
 
      constexpr machine() noexcept(true)=default;
      template<
         class Arg,
         class... Args,
         class =typename std::enable_if<!std::is_convertible<Arg, machine>::value>::type
      > explicit constexpr
      machine(Arg &&arg, Args &&...args) noexcept(noexcept(rows_t(std::forward<Arg>(arg), std::forward<Args>(args)...)));
      constexpr machine(machine const &) noexcept(noexcept(rows_t(std::declval<rows_t>())));
 
      /// Call this method to perform your state transition from the start state to the next state.
      /**
         Algorithmic complexity: see comment for rows, above.
 
         \param   s  The start state for the transition to be selected. If s is not found in the state_transition_table, then there is no effect, nothing happens. The states must be uniformly, linearly, increasing in underlying value.
         \param   p  The parameters to pass to the event selected by the start state from the state_transition_table.
         \return  The resultant state of the row selected by the input state, s. If the row was a guard-row, then if the guard permitted it the resultant state, otherwise the input state, s.
      */
      template<class... Params>
      constexpr end_states process(states s, Params &&...p) const noexcept(false);
 
      /// Call this method to perform your state transition from the start state to the next state.
      /**
         Algorithmic complexity: see comment for rows, above.
 
         \param   s  The start state for the transition to be selected. If s is not found in the state_transition_table, then there is no effect, nothing happens. The states must be uniformly, linearly, increasing in underlying value.
         \param   p  The parameters to pass to the event selected by the start state from the state_transition_table.
         \return  The resultant state of the row selected by the input state, s. If the row was a guard-row, then if the guard permitted it the resultant state, otherwise the input state, s.
      */
      template<class... Params>
      constexpr end_states process(states s, Params &&...p) noexcept(false);
 
   private:
      rows_t rows_;
   };
 
};
 
struct hash {
 
   /// A convenience class to make the rows a bit smaller when declaring the meta-state machine table.
   template<class States, class EndStates>
   struct row_types {
      using states=States;
      using end_states=EndStates;
 
      struct compat_row_base;
      /// A row in the meta-state machine table.
      template<
         states Start,  ///< The start state.
         class Event,   ///< The event that will be executed to transition from the start to the next state. Must be a functor.
         end_states Next   ///< The state transitioned to.
      >
      class row;
      /// A row in the meta-state machine table that also has a guard.
      template<
         states Start,  ///< The start state.
         class Event,   ///< The event that will be executed to transition from the start to the next state. Must be a functor.
         end_states Next,  ///< The state transitioned to.
         class Guard    ///< The guard: if true the transition occurs, otherwise there is no change in state.
      >
      class g_row;
   };
 
   /// Derive from this object to implement your meta-state machine.
   /**
      The state transition table must be called or aliassed to the type state_transition_table to be accessible within this class.
   */
   template<
      class Deriv ///< The derived meta-state machine, that must itself be be stateless.
   >
   class state_transition_table {
   public:
      struct no_op {
         template<class ...Args>
         explicit no_op(Args &&...) noexcept(true) {}
 
         template<auto state, auto next, class ...Args>
         constexpr auto operator()(Args &&...) const noexcept(true) FORCE_INLINE {return next;}
         static constexpr void noop() noexcept(true) {}
      };
 
      /// The derived, implementation of the meta-state table.
      /**
         The derived class must contain a type member called transition_table which implements the meta-state table as a collection of hash::row_types::row.
 
         \see hash::row_types::row
      */
      template<class Row, class... Rows>
      struct rows;
 
   private:
      template<class Row> struct get_state_as_hash;
 
      state_transition_table()=delete;
   };
 
   /// Instantiate this object to use the created state-machine.
   template<
      class STT   ///< The state transition table, the type derived from state_transition_table, above.
   >
   class machine {
   public:
      using element_type=STT;
      using states=typename element_type::transition_table::states;
      using end_states=typename element_type::transition_table::end_states;
 
   private:
      using states_to_actions_table_t=typename element_type::transition_table::states_to_actions_table_t;
 
   public:
      constexpr machine()=default;
      template<
         class Arg,
         class... Args,
         class =typename std::enable_if<!std::is_convertible<Arg, machine>::value>::type
      > explicit constexpr
      machine(Arg &&arg, Args &&...args) noexcept(noexcept(states_to_actions_table_t(std::forward<Arg>(arg), std::forward<Args>(args)...)));
      constexpr machine(machine const &) noexcept(noexcept(states_to_actions_table_t(std::declval<states_to_actions_table_t>())));
 
      /// Call this method to perform your state transition from the start state to the next state.
      /**
         Algorithmic complexity: O(1) where n is the number of entries in the meta-state table with a small constant. This is thread-safe (thus re-entrant) only if all of the called actions are.
 
         \param   s  The start state for the transition to be selected. If s is not found in the state_transition_table, then there is no effect, nothing happens.
         \param   p  The parameters to pass to the event selected by the start state from the state_transition_table. Note that the events must have a member-using called argument_type that specifies this type, otherwise there will be a compile-time error.
         \return  The resultant state of the row selected by the input state, s. If the row was a guard-row, then if the guard permitted it the resultant state, otherwise the input state, s.
      */
      template<class Params>
      end_states process(states s, Params &p) const noexcept(
         noexcept(
            std::declval<states_to_actions_table_t>()[s].process(reinterpret_cast<void *>(&p))
         )
      );
 
      /// Call this method to perform your state transition from the start state to the next state.
      /**
         Algorithmic complexity: O(1) where n is the number of entries in the meta-state table with a small constant. This is thread-safe (thus re-entrant) only if all of the called actions are.
 
         \param   s  The start state for the transition to be selected. If s is not found in the state_transition_table, then there is no effect, nothing happens.
         \param   p  The parameters to pass to the event selected by the start state from the state_transition_table. Note that the events must have a member-using called argument_type that specifies this type, otherwise there will be a compile-time error.
         \return  The resultant state of the row selected by the input state, s. If the row was a guard-row, then if the guard permitted it the resultant state, otherwise the input state, s.
      */
      template<class Params>
      end_states process(states s, Params &p) noexcept(
         noexcept(
            std::declval<states_to_actions_table_t>()[s].process(reinterpret_cast<void *>(&p))
         )
      );
 
   private:
      const states_to_actions_table_t tbl;
   };
 
};
 
} } }
 
/**
   \todo How can this be used...? Inspired by talks with Jon Chesterfield.
 
#include <functional>
 
enum states : std::uint64_t {
    state1=0, ///< Need to set this...
    state2=134726432, ///< Need to set this...
    state3=24664 ///< Need to set this...
};
 
struct row_base {
//    virtual states process()=0;
};
struct row : row_base {
    states process();// override;
};
struct row1 : row {
    states process();// override;
};
struct row2 : row1 {
    states process();// override;
};
 
// target pointer, possible targets
#define jumpto(a, ...) asm goto("jmp *%0" : : "r"(a) : : __VA_ARGS__)
 
states process(states s, row_base &r)
{
  void* the_label_pointer=reinterpret_cast<void *>(s);
  jumpto(the_label_pointer, state1, state2, state3);
 
state1:
    // 32-byte boundary.
    asm ("p2align 10,0xff,16");
  return static_cast<row &>(r).process();
state2:
    // 32-byte boundary.
    asm ("p2align 5");
  return static_cast<row1 &>(r).process();
 
state3:
    // 32-byte boundary.
    asm ("p2align 5");
  return static_cast<row2 &>(r).process();
    // 32-byte boundary.
    asm ("p2align 5");
}
 
states foo(row_base &r) {
    return process(state3, r);
}
*/
 
#include "msm_impl.hpp"
 
#endif