fsm.h

Go to the documentation of this file.

#ifndef ZTH_FSM_H
#define ZTH_FSM_H
/*
 * Zth (libzth), a cooperative userspace multitasking library.
 * Copyright (C) 2019-2022  Jochem Rutgers
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */
 
#ifdef __cplusplus
#       include <libzth/allocator.h>
#       include <libzth/time.h>
#       include <libzth/util.h>
#       include <libzth/waiter.h>
 
// Suppress missing braces, as this is what you do when you specify the FSM.
#       pragma GCC diagnostic ignored "-Wmissing-braces"
 
#       if __cplusplus >= 201402L
#               define deprecated14(msg) [[deprecated(msg)]]
#       else
#               define deprecated14(msg)
#       endif
 
namespace zth {
 
namespace guards {
 
enum End {
        end = 0
};
 
template <typename Fsm>
ZTH_EXPORT TimeInterval always(Fsm& fsm)
{
        zth_dbg(fsm, "[%s] Guard always", fsm.id_str());
        return TimeInterval();
}
 
template <typename FsmInput, typename FsmInput::Input i, typename Fsm>
ZTH_EXPORT TimeInterval input(Fsm& fsm)
{
        if(fsm.clearInput(i)) {
                zth_dbg(fsm, "[%s] Guard input %s", fsm.id_str(), str(i).c_str());
                return TimeInterval();
        } else
                return TimeInterval::infinity();
}
 
template <typename FsmInput, typename FsmInput::Input i, typename Fsm>
ZTH_EXPORT TimeInterval peek(Fsm& fsm)
{
        if(fsm.hasInput(i)) {
                zth_dbg(fsm, "[%s] Guard peek input %s", fsm.id_str(), str(i).c_str());
                return TimeInterval();
        } else
                return TimeInterval::infinity();
}
 
template <typename Fsm>
TimeInterval timeout_(Fsm& fsm, TimeInterval const& timeout)
{
        TimeInterval ti = timeout - fsm.dt();
        if(ti.hasPassed())
                zth_dbg(fsm, "[%s] Guard timeout %s", fsm.id_str(), timeout.str().c_str());
        return ti;
}
 
template <time_t s, typename Fsm>
ZTH_EXPORT TimeInterval timeout_s(Fsm& fsm)
{
        static constexpr TimeInterval const timeout(s);
        return timeout_<Fsm>(fsm, timeout);
}
 
template <unsigned int ms, typename Fsm>
ZTH_EXPORT TimeInterval timeout_ms(Fsm& fsm)
{
        static TimeInterval const timeout((double)ms * 1e-3);
        return timeout_<Fsm>(fsm, timeout);
}
 
template <uint64_t us, typename Fsm>
ZTH_EXPORT TimeInterval timeout_us(Fsm& fsm)
{
        static TimeInterval const timeout((double)us * 1e-6);
        return timeout_<Fsm>(fsm, timeout);
}
 
template <typename Fsm>
ZTH_EXPORT TimeInterval lock(Fsm& fsm)
{
        if(fsm.guardLock()) {
                zth_dbg(fsm, "[%s] Guard lock", fsm.id_str());
                return TimeInterval();
        } else
                return TimeInterval::infinity();
}
 
template <typename Fsm>
ZTH_EXPORT TimeInterval step(Fsm& fsm)
{
        if(fsm.guardStep()) {
                zth_dbg(fsm, "[%s] Guard step", fsm.id_str());
                return TimeInterval();
        } else
                return TimeInterval::infinity();
}
} // namespace guards
 
template <typename Fsm>
class FsmGuard {
public:
        typedef TimeInterval (*Function)(Fsm& fsm);
 
        // cppcheck-suppress noExplicitConstructor
        constexpr FsmGuard(Function function)
                : m_function(function)
        {}
 
        // cppcheck-suppress noExplicitConstructor
        FsmGuard(guards::End)
                : m_function()
        {}
 
        TimeInterval operator()(Fsm& fsm) const
        {
                zth_assert(valid());
                return m_function(fsm);
        }
        constexpr bool valid() const
        {
                return m_function;
        }
 
private:
        Function m_function;
};
 
template <typename Fsm>
struct FsmDescription {
        union {
                typename Fsm::State state;
                FsmDescription const* stateAddr;
        };
        FsmGuard<Fsm> guard;
};
 
template <typename Fsm>
class FsmCompiler {
public:
        constexpr explicit FsmCompiler(FsmDescription<Fsm>* description)
                : m_description(description)
                , m_compiled()
        {}
 
#       if GCC_VERSION >= 49000L
        __attribute__((returns_nonnull))
#       endif
        __attribute__((warn_unused_result)) Fsm*
        create() const
        {
                return new Fsm(*this);
        }
 
        FsmDescription<Fsm> const* description() const
        {
                compile();
                return m_description;
        }
 
protected:
        void compile() const
        {
                if(likely(m_compiled))
                        return;
 
                typename map_type<typename Fsm::State, FsmDescription<Fsm> const*>::type stateAddr;
                FsmDescription<Fsm>* p = m_description;
                while(true) {
                        // Register this state
                        zth_assert(stateAddr.count(p->state) == 0);
                        stateAddr[p->state] = const_cast<FsmDescription<Fsm> const*>(p);
 
                        if(!p->guard.valid())
                                // End of description
                                break;
 
                        // Go to end of guard list
                        while((p++)->guard.valid())
                                ;
                }
 
                // Patch State references
                p = m_description;
                while(true) {
                        if(!p->guard.valid())
                                // End of description
                                break;
 
                        // Patch this state's guard list
                        while((p++)->guard.valid()) {
                                zth_assert(stateAddr.count(p->state) == 1);
                                p->stateAddr = stateAddr[p->state];
                        }
                }
 
                m_compiled = true;
        }
 
private:
        FsmDescription<Fsm>* const m_description;
        mutable bool m_compiled;
};
 
template <typename State_, typename Input_ = int, typename FsmImpl_ = void>
class Fsm : public UniqueID<Fsm<void, void, void> > {
        ZTH_CLASS_NEW_DELETE(Fsm)
public:
        typedef typename choose_type<FsmImpl_, Fsm>::type FsmImpl;
        typedef State_ State;
        typedef Input_ Input;
        typedef FsmCompiler<FsmImpl> Compiler;
        typedef FsmDescription<FsmImpl> Description[];
 
protected:
        enum EvalState { evalCompile, evalInit, evalReset, evalIdle, evalState, evalRecurse };
        typedef FsmDescription<FsmImpl> const* StateAddr;
 
        enum Lockstep {
                lockstepNormal,
                lockstepLock,
                lockstepStep,
                lockstepSteppingNext,
                lockstepStepping
        };
 
public:
        explicit Fsm(Compiler const& compiler, char const* name = "FSM")
                : UniqueID(name)
                , m_compiler(&compiler)
                , m_evalState(evalInit)
                , m_lockstep(lockstepNormal)
        {
#       if __cplusplus >= 201103L && !defined(DOXYGEN)
                static_assert(std::is_base_of<Fsm, FsmImpl>::value, "");
#       endif
        }
 
        explicit Fsm(Description description, char const* name = "FSM")
                : UniqueID(name)
                , m_description(description)
                , m_evalState(evalCompile)
                , m_lockstep(lockstepNormal)
        {}
 
        virtual ~Fsm() {}
 
        State const& state() const
        {
                switch(m_evalState) {
                default:
                        return m_state->state;
                case evalCompile:
                        return m_description->state;
                case evalInit:
                        return m_compiler->description()->state;
                case evalReset:
                        return m_compiledDescription->state;
                }
        }
 
        Timestamp const& t() const
        {
                return m_t;
        }
 
        TimeInterval dt() const
        {
                return Timestamp::now() - t();
        }
 
        State const& next() const
        {
                switch(m_evalState) {
                default:
                        zth_assert(exit() || m_stateNext == m_state);
                        return m_stateNext->state;
                case evalCompile:
                        return m_description->state;
                case evalInit:
                        return m_compiler->description()->state;
                case evalReset:
                        return m_compiledDescription->state;
                }
        }
 
        void reset()
        {
                zth_dbg(fsm, "[%s] Reset", id_str());
                switch(m_evalState) {
                default:
                        // If you get here, you probably called reset from within the callback
                        // function, which you shouldn't do.
                        zth_assert(false);
                        ZTH_FALLTHROUGH
                case evalIdle:
                        m_evalState = evalReset;
                        break;
                case evalCompile:
                case evalInit:
                case evalReset:
                        break;
                }
                clearInputs();
        }
 
        bool entry() const
        {
                return m_entry;
        }
 
        bool exit() const
        {
                return m_exit;
        }
 
        bool lockstep() const
        {
                return m_lockstep != lockstepNormal;
        }
 
        void setLockstep(bool enable)
        {
                if(lockstep() == enable)
                        return;
 
                switch(m_lockstep) {
                case lockstepNormal:
                        m_lockstep = lockstepLock;
                        break;
                default:
                        m_lockstep = lockstepNormal;
                        break;
                }
                trigger();
        }
 
        bool guardLock()
        {
                switch(m_lockstep) {
                case lockstepLock:
                case lockstepStep:
                        return true;
                default:
                        return false;
                }
        }
 
        bool guardStep()
        {
                switch(m_lockstep) {
                case lockstepLock:
                        return false;
                case lockstepStep:
                        m_lockstep = lockstepSteppingNext;
                        return true;
                default:
                        return true;
                }
        }
 
        void step()
        {
                switch(m_lockstep) {
                case lockstepLock:
                        m_lockstep = lockstepStep;
                        trigger();
                        break;
                default:;
                }
        }
 
        void input(Input i)
        {
                m_inputs.push_back(i);
                trigger();
        }
 
        bool clearInput(Input i)
        {
                for(size_t j = 0; j < m_inputs.size(); j++)
                        if(m_inputs[j] == i) {
                                m_inputs[j] = m_inputs.back();
                                m_inputs.pop_back();
                                return true;
                        }
                return false;
        }
 
        void clearInputs()
        {
                m_inputs.clear();
        }
 
        void setInputsCapacity(size_t capacity)
        {
#       if __cplusplus >= 201103L
                if(m_inputs.capacity() > capacity * 2U) {
                        // Shrink when the current capacity is significantly more.
                        m_inputs.shrink_to_fit();
                }
#       endif
 
                m_inputs.reserve(capacity);
        }
 
        bool hasInput(Input i) const
        {
                for(size_t j = 0; j < m_inputs.size(); j++)
                        if(m_inputs[j] == i)
                                return true;
                return false;
        }
 
        TimeInterval eval(bool alwaysDoCallback = false)
        {
                bool didCallback = false;
                TimeInterval wait = TimeInterval::null();
 
                switch(m_evalState) {
                case evalCompile:
                        m_compiledDescription = Compiler(m_description).description();
                        if(false) {
                                ZTH_FALLTHROUGH
                        case evalInit:
                                m_compiledDescription = (StateAddr)m_compiler->description();
                        }
                        ZTH_FALLTHROUGH
                case evalReset:
                        m_stateNext = m_state = m_compiledDescription;
                        m_evalState = evalState;
                        zth_dbg(fsm, "[%s] Initial state %s", id_str(), str(state()).c_str());
                        m_t = Timestamp::now();
                        m_exit = false;
                        m_entry = true;
                        callback();
                        m_entry = false;
                        didCallback = true;
                        ZTH_FALLTHROUGH
                case evalIdle: {
                        do {
                                m_evalState = evalState;
                                while((wait = evalOnce()).hasPassed())
                                        didCallback = true;
                                if(alwaysDoCallback && !didCallback)
                                        callback();
                        } while(m_evalState == evalRecurse);
                        m_evalState = evalIdle;
                        break;
                }
                case evalState:
                        m_evalState = evalRecurse;
                        ZTH_FALLTHROUGH
                case evalRecurse:
                        break;
                }
                return wait;
        }
 
        deprecated14("Use zth::fsm::compile() instead") void run()
        {
                TimeInterval wait = eval();
                if(!m_state->guard.valid()) {
done:
                        zth_dbg(fsm, "[%s] Final state %s", id_str(), str(state()).c_str());
                        return;
                }
 
                PolledMemberWaiting<Fsm> wake_up(*this, &Fsm::trigger_, wait);
                do {
                        if(wake_up.interval().isInfinite()) {
                                m_trigger.wait();
                        } else {
                                scheduleTask(wake_up);
                                m_trigger.wait();
                                unscheduleTask(wake_up);
                        }
                        wait = eval();
                        wake_up.setInterval(wait, currentFiber().runningSince());
                } while(m_state->guard.valid());
                goto done;
        }
 
        void trigger()
        {
                m_trigger.signal(false);
        }
 
private:
        bool trigger_()
        {
                m_trigger.signal(false);
                return true;
        }
 
        TimeInterval evalOnce()
        {
                TimeInterval wait = TimeInterval::infinity();
                StateAddr p = m_state;
                while(p->guard.valid()) {
                        TimeInterval ti((p++)->guard(static_cast<FsmImpl&>(*this)));
                        if(ti.hasPassed()) {
                                setState(p->stateAddr);
                                wait = ti;   // NVRO
                                return wait; // Return any passed TimeInterval, which indicates that
                                             // a transition was taken.
                        } else if(ti < wait) {
                                // Save shortest wait interval.
                                wait = ti;
                        }
                }
                zth_dbg(fsm, "[%s] State %s blocked for %s", id_str(), str(state()).c_str(),
                        wait.str().c_str());
                return wait;
        }
 
        void setState(StateAddr nextState)
        {
                if(nextState == m_state)
                        zth_dbg(fsm, "[%s] Selfloop of state %s", id_str(), str(state()).c_str());
                else
                        zth_dbg(fsm, "[%s] Transition %s -> %s", id_str(), str(state()).c_str(),
                                str(nextState->state).c_str());
 
                m_stateNext = nextState;
 
                m_exit = true;
                callback();
                m_exit = false;
 
                m_state = nextState;
                m_t = Timestamp::now();
 
                switch(m_lockstep) {
                case lockstepSteppingNext:
                        m_lockstep = lockstepStepping;
                        break;
                case lockstepStepping:
                        m_lockstep = lockstepLock;
                        break;
                default:;
                }
 
                m_entry = true;
                callback();
                m_entry = false;
        }
 
protected:
        virtual void callback() = 0;
 
private:
        union {
                FsmDescription<FsmImpl>* m_description; // only valid during stateCompile
                Compiler const* m_compiler;             // only valid during stateInit
                FsmDescription<FsmImpl> const* m_compiledDescription; // otherwise
        };
        StateAddr m_state;
        StateAddr m_stateNext;
        EvalState m_evalState;
        Timestamp m_t;
        bool m_entry;
        bool m_exit;
        Lockstep m_lockstep;
        Signal m_trigger;
        typename vector_type<Input>::type m_inputs;
};
 
template <
        typename State_, typename CallbackArg_ = void, typename Input_ = int,
        typename FsmImpl_ = void>
class FsmCallback
        : public Fsm<
                  State_, Input_,
                  typename choose_type<
                          FsmImpl_, FsmCallback<State_, CallbackArg_, Input_, void> >::type> {
        ZTH_CLASS_NEW_DELETE(FsmCallback)
public:
        typedef typename choose_type<
                FsmImpl_, FsmCallback<State_, CallbackArg_, Input_, void> >::type FsmImpl;
        typedef Fsm<State_, Input_, FsmImpl> base;
        typedef CallbackArg_ CallbackArg;
        typedef void (*Callback)(FsmCallback&, CallbackArg);
 
        FsmCallback(
                // cppcheck-suppress constParameter
                typename base::Compiler const& compiler, Callback callback, CallbackArg callbackArg,
                char const* name = "FSM")
                : base(compiler, name)
                , m_callback(callback)
                , m_callbackArg(callbackArg)
        {}
 
        FsmCallback(
                // cppcheck-suppress passedByValue
                // cppcheck-suppress constParameter
                typename base::Description description, Callback callback, CallbackArg callbackArg,
                char const* name = "FSM")
                : base(description, name)
                , m_callback(callback)
                , m_callbackArg(callbackArg)
        {}
 
        virtual ~FsmCallback() {}
 
        CallbackArg callbackArg() const
        {
                return m_callbackArg;
        }
 
protected:
        virtual void callback() override
        {
                if(m_callback) {
                        zth_dbg(fsm, "[%s] Callback for %s%s", this->id_str(),
                                str(this->state()).c_str(),
                                this->entry() ? " (entry)" : this->exit() ? " (exit)" : "");
                        m_callback(*this, m_callbackArg);
                }
        }
 
private:
        Callback const m_callback;
        CallbackArg const m_callbackArg;
};
 
template <typename State_, typename Input_, typename FsmImpl_>
class FsmCallback<State_, void, Input_, FsmImpl_>
        : public Fsm<
                  State_, Input_,
                  typename choose_type<
                          FsmImpl_, FsmCallback<State_, void, Input_, void> >::type> {
        ZTH_CLASS_NEW_DELETE(FsmCallback)
public:
        typedef typename choose_type<FsmImpl_, FsmCallback<State_, void, Input_, void> >::type
                FsmImpl;
        typedef Fsm<State_, Input_, FsmImpl> base;
        typedef void (*Callback)(FsmCallback&);
 
        explicit FsmCallback(
                typename base::Compiler const& compiler, Callback callback = nullptr,
                char const* name = "FSM")
                : base(compiler, name)
                , m_callback(callback)
        {}
 
        explicit FsmCallback(
                // cppcheck-suppress passedByValue
                typename base::Description description, Callback callback = nullptr,
                char const* name = "FSM")
                : base(description, name)
                , m_callback(callback)
        {}
 
        virtual ~FsmCallback() {}
 
protected:
        virtual void callback() override
        {
                if(m_callback) {
                        zth_dbg(fsm, "[%s] Callback for %s%s", this->id_str(),
                                str(this->state()).c_str(),
                                this->entry() ? " (entry)" : this->exit() ? " (exit)" : "");
                        m_callback(*this);
                }
        }
 
private:
        Callback const m_callback;
};
 
} // namespace zth
#endif // __cplusplus
#endif // ZTH_FSM_H