David Abrahams wrote:
"Andreas Huber" <ah2003@gmx.net> writes:
David Abrahams wrote:
[snip]
Also, do I note that there's always function pointer indirection for event dispatch?
I'm not sure I understand what you mean with "function pointer indirection". Event dispatch consists of a virtual function call followed by a linear search for a reaction matching the event.
That's what I mean. If you look at the FSM examples I posted, no virtual call is needed, and in fact the linear search could be optimized by the compiler into a hashed case statement or by metaprogramming into a log(n) search. The 2nd example uses a constant-time lookup, dispatching through a single function pointer. There are lots of dispatching tradeoffs available.
I finally found the time to have a closer look at your examples. I believe you can do away with one of the two double dispatch steps because you know at compile time exactly how the whole state machine looks like (i.e. your compile time algorithm "knows" all possible events and all possible states). This approach works well with small FSMs. It breaks down for large FSMs because either at some point the compiler will give up due to internal limits or the compilation times become unbearable. During state machine development, every little change (e.g. adding an event or a state) triggers a recompilation of the whole state machine. boost::fsm was designed to avoid these problems. You can spread a state machine over multiple translation units and even have multiple developers work on the same machine. Changes made by one developer (adding states, transitions, events to "his" part of the machine) will not trigger a recompilation of code implementing other parts of the machine. This virtually limitless scalability is possible exactly because there's no central algorithm that knows "everything". As a result, some stuff your examples can do at compile time has to be done at runtime by boost::fsm. More specifically, in your examples you know at compile time exactly which states have an outgoing transition for a given event. You therefore never need to runtime dispatch on an event that's known at compile time. boost::fsm does not have this information available at compile time. In fact, before a state becomes active at runtime my dispatch algorithm does not even know that such a state exists. Consequently, my dispatcher cannot know all the possible reactions for a given event and that's why I need to perform a linear search for the reaction after dispatching on the current state.
I really like your state representation; it seems as though it should be possible to get all these different dispatching options with your state representation, rather than requiring a monolithic STT sequence to be assembled as my examples do.
As long as no custom_reactions are used I think this should be possible, as all the necessary information is available at compile time in a single translation unit. However, I don't dare to explore what this would mean implementation-wise. It seems this pretty much requires a complete rewrite. I'd also need to change/extend the interface to provide replacements for some custom_reaction uses (guards and in-state reactions). Finally, I think custom_reactions are fundamentally incompatible with all dispatching options that implement one dispatch step at compile time. So, an interface-compatible boost::fsm variant offering the current as well as other dispatching options would somehow need to issue an error upon detecting a custom_reaction or somehow fall back to current dispatch algorithm... Regards, Andreas