Autonomous FSM with static states

[puzrin]

src: https://github.com/pdsink/pdsink/blob/master/src/pd/utils/afsm.h tests: https://github.com/pdsink/pdsink/tree/master/test/test_afsm

A popular FSM type, without input messages. The etl::fsm approach heavily inspires this implementation. In this implementation, states are static.

All etl::fsm:

RAM:   [=         ]   8.7% (used 28564 bytes from 327680 bytes)
Flash: [===       ]  25.6% (used 335336 bytes from 1310720 bytes)

PE => tick_fsm

RAM:   [=         ]   8.5% (used 27908 bytes from 327680 bytes)
Flash: [===       ]  25.3% (used 331722 bytes from 1310720 bytes)

PE, TC => tick_fsm

RAM:   [=         ]   8.5% (used 27828 bytes from 327680 bytes)
Flash: [===       ]  25.3% (used 331454 bytes from 1310720 bytes)

PE, TC, PRL => tick_fsm

RAM:   [=         ]   8.1% (used 26660 bytes from 327680 bytes)
Flash: [==        ]  24.8% (used 325614 bytes from 1310720 bytes)

This is how resource usage changed after the FSM replacement. ~ 50 states. Approx 10K flash and 2K ram difference.

I'm not 100% sure, maybe it will be helpful in ETL. Could you take a look? Personally, I never accept low-level optimizations as a key reason for architecture decisions, but the proposed implementation looks nice and can be convenient for some cases.

[jwellbelove]

Thanks, I'll take a look. Have you also looked at the ETL's etl::state_chart as a non-message FSM.

[puzrin]

Sure, inspected etl::state_chart prior to do anything (and the most popular FSM-s in another projects). It's a classic table-defined graph. "Must have", but for another kind of tasks. Autonomous FSM-s are covered by etl::fsm, but since it's heavily based on message routing, that adds unnecessary complexity (for usage too, need to add fake events and .get_context() calls).

Any concrete FSM implementation will likely be opinion-based. The essence is to find a proper balance between features/theory/flexibility, to make the API "comfortable to use". Surely, my existing code can be improved to fit ETL coding style better. Consider it as a "tested draft".

The key design points of the proposed autonomous FSM are:

• Passing new states via return xxx for most cases.
• States pack for comfortable list definition and compile-time checks (I'd suggest propagate this approach to etl::fsm/hfsm too).
• Still use set_states() to prevent circular dependencies (but that's very cheap).
• Static states in concrete implementation (not strict design requirement)
• Reserved Uninitialized state value, instead of reset/start (less academic, but more practical, IMHO)

PS. I do not insist on including any of the proposals in the ETL mainstream. That's feedback after using ETL in real projects, with my personal opinion. And with the hope of being useful :). Feel free to reject anything or everything - not a problem.

[jwellbelove]

I'll certainly give your implementation serious consideration. There is certainly not a 'one-size-fits-all' FSM implementation. I'm all for adding a new feature that expands the options an ETL user has. If it contains ideas that can improve the current code, even better.

[puzrin]

src: https://github.com/pdsink/pdsink/blob/master/src/pd/utils/afsm.h tests: https://github.com/pdsink/pdsink/tree/master/test/test_afsm

Reworked namespace/naming for more friendly use.

Added features:

• Getting previous state ID. Sometimes convenient. I used external flags for workarounding when the feature was not available. It can be used for log filtering, for quick return from subroutines, etc.
• State Interceptors (~ aspects/mixins). That's one of the standard FSM mutation paradigms. Very powerful and reasonably cheap. Useful to emulate subroutines, apply logs, local mode switches (for example, custom error processing), and so on.
• .is_uninitialized() helper
• .change_state(id, reenter = false) - second param to force on_enter_state even if state not changed.

The first two features reduce the need for an HSM. HSM is mighty, but IMHO it's the last choice, when everything else doesn't work :).

Interceptors are currently assigned via multiple inheritance (zero cost for statics). Alternatives (decorator, extra template param, ...) are possible, but postponed. It's better to coordinate such things with other FSMs to keep a unified "library spirit".

[puzrin]

Some updates after practice with the real project:

• Fixed prev state tracking, if state changed from .on_enter_state().
• Enforced build error if entry/run/exit method declaration is missed. Behaviour may be very unpleasant without, and difficult to debug. Since the guaranteed check via override is impossible for static classes, I decided to increase the requirements. Potential benefits of skipping empty declarations do not override the problems you can get with them.
• Added asserts for run/change_state recursive calls. Even with properly designed FSM internals, this can occur indirectly through the outer layers. For example, when an event loop is used instead of RTOS, and you "emit" an event from a state. So, I added asserts to strictly prohibit recursion UB and see messages in the error logger. Without this check, behaviour can be very unpleasant for debugging.

Still not used interceptors (planned, but had no time). But all the rest looks nice IMHO.

Probably, .reset() to the undefined state can be added instead of .change_state(afsm::Undefined). But not 100% sure, and this may diverge from the etl::fsm concept of reset, which is confusing. Postponed. Maybe .undefine()...