jeudi 5 mai 2022

Implementing a "hierarchical state machine" (HSM) in modern C++

I've been toying with this for the past couple of days but am not sure what the best way to design it is - particularly in regard to the top-level interface. I've looked at this:

https://barrgroup.com/embedded-systems/how-to/introduction-hierarchical-state-machines

and this quite old article indeed:

https://state-machine.com/doc/Heinzmann04.pdf

and am wondering what can be done nowadays with contemporary C++ and the features it offers, including advanced metaprogramming facilities such as in BOOST.

For those who don't know, a "hierarchical state machine" is basically a reorganization of the "finite state machine" so that each state becomes, in effect, its own FSM (though with the important exception that transitions are allowed to cross hierarchical levels so technically each inner "FSM" is not closed under transition and thus not a true FSM), thus allowing one greater expressive power to model relationships of conditionality that crop up often in things like GUIs where that the state of one set of widgets may affect another set which in turn may affect a third, while also improving code reuse. And when I noticed how messy my old GUI code was and then found this pattern, I thought of giving it a shot.

In particular, my "ideal" interface for the HSM would look like this:

class MyHsm : public Hsm<MyHsm, int> {
    public:
        MyHsm() : m_data(0) {}
    private:
        int m_data;
};

class MyHsmRootState : public HsmRootState<MyHsm> {
    public:
        void enter(MyHsm *a_hsm) const { ... }
        void exit(MyHsm *a_hsm) const { ... }
};

class MyHsmState1 : public HsmInnerState<MyHsmRootState> {
    public:
        void enter(MyHsm *a_hsm) const { ... }
        void exit(MyHsm *a_hsm) const { ... }
};

class MyHsmState2 : public HsmDefaultInnerState<MyHsmRootState> {
    public:
        void enter(MyHsm *a_hsm) const { ... }
        void exit(MyHsm *a_hsm) const { ... }
};

class MyHsmState11 : public HsmValidState<MyHsmState1> {
    public:
        void processInput(int a_input) const { ... }

        void enter(MyHsm *a_hsm) const { ... }
        void exit(MyHsm *a_hsm) const { ... }
};

class MyHsmState12 : public HsmDefaultValidState<MyHsmState1> {
    public:
        void processInput(int a_input) const { ... }

        void enter(MyHsm *a_hsm) const { ... }
        void exit(MyHsm *a_hsm) const { ... }
};

class MyHsmState21 : public HsmValidState<MyHsmState2> {
    public:
        void processInput(int a_input) const { ... }

        void enter(MyHsm *a_hsm) const { ... }
        void exit(MyHsm *a_hsm) const { ... }
};

class MyHsmState22 : public HsmDefaultValidState<MyHsmState2> {
    public:
        void processInput(int a_input) const {
            if(a_input == 0) {
                hsmTran<MyHsmState21>(a_hsm); // or whatever
            }
        }

        void enter(MyHsm *a_hsm) const { ... }
        void exit(MyHsm *a_hsm) const { ... }
};

where an inheritance tree is used to represent the state hierarchy, and to initiate the HSM we do

void f() {
    MyHsm hsm;
    hsm.commence<MyHsmRootState>();
    ...
}

The idea is that, upon calling this command, the HSM must transition to the innermost default state (it is only possible for the HSM to actually be in a leaf, i.e. not further inherited, state, which then implies being also in all the states further up the hierarchy from it as well). Here that is MyHsmState22. And that's the behavior I'm finding tricky to implement.

In particular, in order to do this transition, MyHsm somehow has to know that there is a derived class MyHsmState2 that inherited HsmDefaultInnerState<MyHsmRootState> from MyHsmRootState (which it knows of), and then on to know that there is, from that, the derived class MyHsmState22. And the question is, is there some way to do that? Anything I come up with seems to be very complicated at the least (if not even an external code processor to scan the C++ code and generate some kind of annotation a la Qt's MOC).

The alternative I think of is changing the interface to appease the constraints of the implementation, and instead treat the defaults as type members, so the downward-pointing links are easily accessed in templatese:

class MyHsmRootState : public HsmRootState<MyHsm> {
    public:
        typedef class MyHsmState2 Default;

        void enter(MyHsm *a_hsm) const { ... }
        void exit(MyHsm *a_hsm) const { ... }
};

however this requires a forward declaration and thus in effect is a cyclical dependency of MyHsmRootState upon MyHsmState2 and conversely. That said, if it simplifies things and makes the code neater, it can't hurt, right? But I've also heard that generally introducing cyclical dependencies is not "good practice".

Aucun commentaire:

Enregistrer un commentaire