Nick Parker
2012-10-11 19:30:12 UTC
Hello, I'm on a project at work which has been using Boost's Meta State Machine (boost::msm) library in a couple places. A major downside for us is that our state machines are apparently quite large by boost::msm standards (on the order of 50-80 transitions), resulting in very resource intensive builds which need a couple minutes and several GB of ram to complete. Long story short, I figured this would be a good opportunity to learn Ragel. I've made pretty good progress in writing Ragelized versions of our current machines, but have encountered some corner cases where I wasn't able to think up an obvious Ragel equivalent to a boost::msm feature:
1) Let some events be considered valid during any state. In boost::msm, we've been handling this via a secondary orthogonal state[1] dedicated to handling those events, leaving the main state unchanged. The best Ragel equivalent I found was to do something like this, where a no-op submachine containing those events would be manually added to each state:
anytime_events = (
e_sneeze @a_sneeze_from_any_to_same |
e_laugh @a_laugh_from_any_to_same
);
talk_sm = (
start: (
e_hello @a_hello_from_start_to_hello -> hello |
e_goodbye @a_goodbye_from_start_to_final -> final |
anytime_events -> start
),
hello: (
e_convo @a_convo_from_hello_to_conversation -> conversation |
e_nevermind @a_nevermind_from_hello_to_final -> final |
anytime_events -> hello
),
conversation: (
e_talk @a_talk_from_conversation_to_conversation -> conversation |
e_goodbye @a_goodbye_from_conversation_to_final -> final |
anytime_events -> conversation
)
);
This solution works fine and is also fairly intuitive, but it felt a little clunky adding this thing to every state. Is there a more direct alternative that I missed?
2) boost::msm has a feature called "Guards"[2], which are user-defined functions that get called before a transition completes and determine whether the transition should be aborted. Would a reasonable Ragel-based implementation of this be an action which calls "fgoto *fcurs" or similar when a condition fails? Assuming it's not too cumbersome to do so, it'd be nice if this could be done "natively" without the fgoto, if only so that the guard failure case appears as a transition in graphviz exports, but this isn't a big deal.
3) In one case, there's a heirarchical machine with submachines that effectively act as modes of operation within a larger state. The tricky part is that these submachines have multiple exit states into the parent machine, depending on what happened within the submachine. This feels like a common scenario, but I couldn't really think of a good equivalent in Ragel for this. Syntactically, I think it'd look something like this:
eat_sm = (
start: (
pick_up_fork -> hungry
),
hungry: (
put_food_in_mouth -> eating |
die_of_starvation -> final
),
not_hungry: (
put_down_fork -> final
),
eating: (
start: [] -> chewing,
chewing: (
chew -> chewing |
spit_out -> hungry | #exit to parent's "hungry" state
swallow -> swallowing
),
swallowing: (
cough_up -> chewing |
swallowed -> not_hungry #exit to parent's "not_hungry" state
)
)
)
The best solution I could think of was to move all the submachine content to the parent machine, which wouldn't be so bad in the above example. However, the real-world case I'm trying to solve has 4 of these submachines, each with 4-5 states, so it'd start to look pretty messy if all of these were all merged into one big list, and the explicit partitioning of these modes into submachines would be nice to keep as well.
4) Unrelated to boost::msm: I've been making very good use of the graphviz export feature. One thing I've found to be missing is that the state circles are only labeled with a seemingly arbitrary integer (1,2,3,...) instead of the state label (state_x,state_y,state_z,...). As a result, I end up needing to go by the transition action labels to figure out which graphviz circles correspond to which states. This can rapidly get cumbersome when the machine is large. Is this a limitation of the dot file format itself or just an unimplemented feature in Ragel? I'm using Ragel 6.7 from Debian unstable, and xdot to view the graphviz output.
[1] "Submachines, orthogonal regions, pseudostates" http://www.boost.org/doc/libs/1_51_0/libs/msm/doc/HTML/ch02s02.html#d0e151
[2] "the guard is a Boolean operation executed [before the transition] which can prevent the transition from firing by returning false" www.boost.org/doc/libs/1_51_0/libs/msm/doc/HTML/ch02s02.html#d0e121
1) Let some events be considered valid during any state. In boost::msm, we've been handling this via a secondary orthogonal state[1] dedicated to handling those events, leaving the main state unchanged. The best Ragel equivalent I found was to do something like this, where a no-op submachine containing those events would be manually added to each state:
anytime_events = (
e_sneeze @a_sneeze_from_any_to_same |
e_laugh @a_laugh_from_any_to_same
);
talk_sm = (
start: (
e_hello @a_hello_from_start_to_hello -> hello |
e_goodbye @a_goodbye_from_start_to_final -> final |
anytime_events -> start
),
hello: (
e_convo @a_convo_from_hello_to_conversation -> conversation |
e_nevermind @a_nevermind_from_hello_to_final -> final |
anytime_events -> hello
),
conversation: (
e_talk @a_talk_from_conversation_to_conversation -> conversation |
e_goodbye @a_goodbye_from_conversation_to_final -> final |
anytime_events -> conversation
)
);
This solution works fine and is also fairly intuitive, but it felt a little clunky adding this thing to every state. Is there a more direct alternative that I missed?
2) boost::msm has a feature called "Guards"[2], which are user-defined functions that get called before a transition completes and determine whether the transition should be aborted. Would a reasonable Ragel-based implementation of this be an action which calls "fgoto *fcurs" or similar when a condition fails? Assuming it's not too cumbersome to do so, it'd be nice if this could be done "natively" without the fgoto, if only so that the guard failure case appears as a transition in graphviz exports, but this isn't a big deal.
3) In one case, there's a heirarchical machine with submachines that effectively act as modes of operation within a larger state. The tricky part is that these submachines have multiple exit states into the parent machine, depending on what happened within the submachine. This feels like a common scenario, but I couldn't really think of a good equivalent in Ragel for this. Syntactically, I think it'd look something like this:
eat_sm = (
start: (
pick_up_fork -> hungry
),
hungry: (
put_food_in_mouth -> eating |
die_of_starvation -> final
),
not_hungry: (
put_down_fork -> final
),
eating: (
start: [] -> chewing,
chewing: (
chew -> chewing |
spit_out -> hungry | #exit to parent's "hungry" state
swallow -> swallowing
),
swallowing: (
cough_up -> chewing |
swallowed -> not_hungry #exit to parent's "not_hungry" state
)
)
)
The best solution I could think of was to move all the submachine content to the parent machine, which wouldn't be so bad in the above example. However, the real-world case I'm trying to solve has 4 of these submachines, each with 4-5 states, so it'd start to look pretty messy if all of these were all merged into one big list, and the explicit partitioning of these modes into submachines would be nice to keep as well.
4) Unrelated to boost::msm: I've been making very good use of the graphviz export feature. One thing I've found to be missing is that the state circles are only labeled with a seemingly arbitrary integer (1,2,3,...) instead of the state label (state_x,state_y,state_z,...). As a result, I end up needing to go by the transition action labels to figure out which graphviz circles correspond to which states. This can rapidly get cumbersome when the machine is large. Is this a limitation of the dot file format itself or just an unimplemented feature in Ragel? I'm using Ragel 6.7 from Debian unstable, and xdot to view the graphviz output.
[1] "Submachines, orthogonal regions, pseudostates" http://www.boost.org/doc/libs/1_51_0/libs/msm/doc/HTML/ch02s02.html#d0e151
[2] "the guard is a Boolean operation executed [before the transition] which can prevent the transition from firing by returning false" www.boost.org/doc/libs/1_51_0/libs/msm/doc/HTML/ch02s02.html#d0e121