| 1 | package FSA::Engine; | ||
| 2 | our $VERSION = '0.01'; | ||
| 3 | $VERSION = eval $VERSION; | ||
| 4 | |||
| 5 | # | ||
| 6 | # Simple implementation of a Finite-state Automata as a Moose Role | ||
| 7 | # | ||
| 8 | use Moose::Role; | ||
| 9 | |||
| 10 | # The states table, with optional entry and exit actions | ||
| 11 | # | ||
| 12 | has 'fsa_states' => ( | ||
| 13 | is => 'rw', | ||
| 14 | isa => 'HashRef', | ||
| 15 | lazy_build => 1, | ||
| 16 | builder => '_build_fsa_states', | ||
| 17 | ); | ||
| 18 | |||
| 19 | # The transitions table, from state to state, with test conditions and transition actions | ||
| 20 | # | ||
| 21 | has 'fsa_transitions' => ( | ||
| 22 | is => 'rw', | ||
| 23 | isa => 'HashRef', | ||
| 24 | lazy_build => 1, | ||
| 25 | builder => '_build_fsa_transitions', | ||
| 26 | ); | ||
| 27 | |||
| 28 | # The current state of the FSA | ||
| 29 | # | ||
| 30 | has 'fsa_state' => ( | ||
| 31 | is => 'rw', | ||
| 32 | isa => 'Str', | ||
| 33 | required => 1, | ||
| 34 | trigger => \&_fsa_state_trigger, | ||
| 35 | ); | ||
| 36 | |||
| 37 | # The current input value | ||
| 38 | # | ||
| 39 | has 'fsa_input' => ( | ||
| 40 | is => 'rw', | ||
| 41 | ); | ||
| 42 | |||
| 43 | # The fsa_state change trigger | ||
| 44 | # | ||
| 45 | sub _fsa_state_trigger { | ||
| 46 | my ( $self, $new_state, $old_state ) = @_; | ||
| 47 | |||
| 48 | if (not $old_state or $new_state ne $old_state) { | ||
| 49 | my $state_actions = $self->fsa_states->{$new_state}; | ||
| 50 | if ($state_actions and $state_actions->{entry_action}) { | ||
| 51 | &{$state_actions->{entry_action}}; | ||
| 52 | } | ||
| 53 | } | ||
| 54 | } | ||
| 55 | |||
| 56 | |||
| 57 | # do the FSA State Change checks | ||
| 58 | # | ||
| 59 | sub fsa_check_state { | ||
| 60 | my ($self, $input) = @_; | ||
| 61 | |||
| 62 | $self->fsa_input($input) if defined $input; | ||
| 63 | |||
| 64 | # Do the transition tests for the current state | ||
| 65 | my $state_transitions = $self->fsa_transitions->{$self->fsa_state}; | ||
| 66 | |||
| 67 | for my $transition_name (keys %$state_transitions) { | ||
| 68 | my $transition = $state_transitions->{$transition_name}; | ||
| 69 | if ($transition->do_test($self->fsa_input)) { | ||
| 70 | # test succeeded, carry out transition | ||
| 71 | # First the leaving action (if any) of the current state | ||
| 72 | my $state_actions = $self->fsa_states->{$self->fsa_state}; | ||
| 73 | if ($state_actions and $state_actions->{exit_action}) { | ||
| 74 | &{$state_actions->{exit_action}}; | ||
| 75 | } | ||
| 76 | |||
| 77 | # Now carry out the transition action (if any) | ||
| 78 | if ($transition->action) { | ||
| 79 | &{$transition->action}($self->fsa_input); | ||
| 80 | } | ||
| 81 | |||
| 82 | # Change the state (note: the entry action will be carried | ||
| 83 | # out by virtue of the trigger, this ensures that the entry | ||
| 84 | # action is always done even when the fsa_state is changed | ||
| 85 | # manually) | ||
| 86 | $self->fsa_state($transition->state); | ||
| 87 | |||
| 88 | # return the new state | ||
| 89 | return $self->fsa_state; | ||
| 90 | } | ||
| 91 | } | ||
| 92 | # no state change occurred | ||
| 93 | return; | ||
| 94 | } | ||
| 95 | |||
| 96 | 1; | ||
| 97 | |||
| 98 | =head1 NAME | ||
| 99 | |||
| 100 | FSA::Engine - A Moose Role to convert an object into a Finite State Machine. | ||
| 101 | |||
| 102 | =head1 SYNOPSIS | ||
| 103 | |||
| 104 | Create a Package which defines your FSA states and transition rules. | ||
| 105 | |||
| 106 | package PingPong; | ||
| 107 | use Moose; | ||
| 108 | with 'FSA::Engine'; | ||
| 109 | |||
| 110 | has 'counter' => ( | ||
| 111 | is => 'rw', | ||
| 112 | isa => 'Int', | ||
| 113 | default => 0, | ||
| 114 | ); | ||
| 115 | |||
| 116 | sub _build_fsa_states { | ||
| 117 | return { | ||
| 118 | ping => { entry_action => sub {print "ping!\n";}, }, | ||
| 119 | pong => { entry_action => sub {print "pong!\n";}, }, | ||
| 120 | game_over => { }, | ||
| 121 | }; | ||
| 122 | } | ||
| 123 | |||
| 124 | sub _build_fsa_transitions { | ||
| 125 | return { | ||
| 126 | ping => { ... }, | ||
| 127 | pong => { ... }, | ||
| 128 | game_over => { ... }, | ||
| 129 | # see BUILD_METHODS below for a full example | ||
| 130 | }; | ||
| 131 | } | ||
| 132 | 1; | ||
| 133 | |||
| 134 | Create an instance of your class | ||
| 135 | |||
| 136 | use PingPong; | ||
| 137 | |||
| 138 | my $game = PingPong->new({ fsa_state => 'ping' }); | ||
| 139 | |||
| 140 | while ($game->fsa_state ne 'game_over') { | ||
| 141 | $game->fsa_check_state; | ||
| 142 | } | ||
| 143 | |||
| 144 | =head1 DESCRIPTION | ||
| 145 | |||
| 146 | This Moose Role allows you to implement a simple state machine in your class by | ||
| 147 | defining the transitions and the states that comprise that state machine. | ||
| 148 | |||
| 149 | All you need to do to transform your class into a FSA is to C<with 'FSA::Engine'>. | ||
| 150 | |||
| 151 | This is not an ideal DFA implementation since it does not enforce a single | ||
| 152 | possible switch from one state to another, instead it short-circuits the | ||
| 153 | evaluation at the first rule to return true. | ||
| 154 | |||
| 155 | FSA::Engine uses named states and named transitions so it is easier to | ||
| 156 | tell what state you are in. | ||
| 157 | |||
| 158 | Optionally, each state can have an entry and an exit action that are triggered | ||
| 159 | when the state is entered and exited. | ||
| 160 | |||
| 161 | Each state may define transition rules which determine the conditions to switch | ||
| 162 | to other states and these rules may optionally define actions to carry out if | ||
| 163 | the rules are followed. | ||
| 164 | |||
| 165 | =head1 BUILD METHODS | ||
| 166 | |||
| 167 | There are some attributes that require building methods. | ||
| 168 | |||
| 169 | =head2 _build_fsa_actions | ||
| 170 | |||
| 171 | sub _build_fsa_states { | ||
| 172 | return { | ||
| 173 | ping => { entry_action => sub {print "ping!\n";}, }, | ||
| 174 | pong => { entry_action => sub {print "pong!\n";}, }, | ||
| 175 | game_over => { }, | ||
| 176 | }; | ||
| 177 | } | ||
| 178 | |||
| 179 | The fsa_actions attribute is defined as a hash reference, where the keys are | ||
| 180 | the names of each state and the value is a hash reference. | ||
| 181 | |||
| 182 | In this example the states are B<ping>, B<pong> and B<game_over>. The hash | ||
| 183 | reference referred to by each state has the following optional keys. | ||
| 184 | |||
| 185 | =head3 entry_action | ||
| 186 | |||
| 187 | This is an anonymous subroutine that (if defined) will be called when the | ||
| 188 | state is entered. | ||
| 189 | |||
| 190 | The B<entry_action> will be called after any Transition action that may have | ||
| 191 | been called leading to this state. | ||
| 192 | |||
| 193 | =head3 exit_action | ||
| 194 | |||
| 195 | This is an anonymous subroutine that (if defined) will be called when the | ||
| 196 | state is exited. | ||
| 197 | |||
| 198 | The B<exit_action> is called before any Transition action called leaving this | ||
| 199 | state. | ||
| 200 | |||
| 201 | =head2 _build_fsa_transitions | ||
| 202 | |||
| 203 | sub _build_fsa_transitions { | ||
| 204 | return { | ||
| 205 | foo_state => { | ||
| 206 | transition_one => { ... }, | ||
| 207 | transition_two => { ... }, | ||
| 208 | }, | ||
| 209 | bar_state => { | ||
| 210 | transition_three => { ... }, | ||
| 211 | }, | ||
| 212 | }; | ||
| 213 | } | ||
| 214 | |||
| 215 | The fsa_transitions attribute is defined as a hash reference, where the keys are | ||
| 216 | the names of each state and the value is a hash reference of the transitions | ||
| 217 | possible from that state. A more complete example is as follows (which goes with | ||
| 218 | the SYNOPSIS) | ||
| 219 | |||
| 220 | sub _build_fsa_transitions { | ||
| 221 | my ($self) = @_; | ||
| 222 | |||
| 223 | return { | ||
| 224 | ping => { | ||
| 225 | volley => FSA::Engine::Transition->new({ | ||
| 226 | test => sub {$self->counter < 20;}, | ||
| 227 | action => sub {$self->counter($self->counter+1);}, | ||
| 228 | state => 'pong', | ||
| 229 | }), | ||
| 230 | end_of_game => FSA::Engine::Transition->new({ | ||
| 231 | test => sub {$self->counter >= 20;}, | ||
| 232 | action => sub {print "Game over\n";}, | ||
| 233 | state => 'game_over', | ||
| 234 | }), | ||
| 235 | }, | ||
| 236 | pong => { | ||
| 237 | return_volley => FSA::Engine::Transition->new({ | ||
| 238 | test => sub {1;}, # always goes back to ping | ||
| 239 | state => 'ping', | ||
| 240 | }), | ||
| 241 | }, | ||
| 242 | game_over => { | ||
| 243 | }, | ||
| 244 | }; | ||
| 245 | } | ||
| 246 | |||
| 247 | The transition names B<ping>, B<pong> and B<game_over> are keys to | ||
| 248 | L<FSA::Engine::Transition> objects which will define the | ||
| 249 | B<test> to carry out, an optional B<action> to carry out if the test succeeds | ||
| 250 | and the B<state> to move to if the test succeeds. | ||
| 251 | |||
| 252 | Each B<test> is made until one succeeds at which point the B<action> (if any) | ||
| 253 | is carried out and the FSA state is advanced to B<state>. | ||
| 254 | |||
| 255 | When a B<test> succeeds, all futher tests are short-circuited. Note that this | ||
| 256 | action may change in future releases. | ||
| 257 | |||
| 258 | =head1 METHODS | ||
| 259 | |||
| 260 | An FSA class will have the following additional methods: | ||
| 261 | |||
| 262 | =head2 fsa_check_state | ||
| 263 | |||
| 264 | $new_state = $my_fsa->fsa_check_state; | ||
| 265 | |||
| 266 | $new_state = $my_fsa->fsa_check_state($input); | ||
| 267 | |||
| 268 | Check for a state change in the FSA, optionally a new input value can be provided. | ||
| 269 | |||
| 270 | If the state machine changes state, then the new state (name) is returned, otherwise | ||
| 271 | it returns C<undef> | ||
| 272 | |||
| 273 | =head1 ATTRIBUTES | ||
| 274 | |||
| 275 | An FSA class will have the following additional attributes: | ||
| 276 | |||
| 277 | =head2 fsa_state | ||
| 278 | |||
| 279 | This is a required attribute. | ||
| 280 | |||
| 281 | my $game = PingPong->new({ | ||
| 282 | fsa_state => 'ping', | ||
| 283 | }); | ||
| 284 | |||
| 285 | When used during construction the C<fsa_state> determines the initial state of the | ||
| 286 | FSA. | ||
| 287 | |||
| 288 | $current_state = $my_fsa->fsa_state; | ||
| 289 | |||
| 290 | At other times it returns the current state of the FSA. | ||
| 291 | |||
| 292 | =head1 SUPPORT | ||
| 293 | |||
| 294 | You can find information at: | ||
| 295 | |||
| 296 | =over 4 | ||
| 297 | |||
| 298 | =item * AnnoCPAN: Annotated CPAN documentation | ||
| 299 | |||
| 300 | L<http://annocpan.org/dist/FSA-Engine> | ||
| 301 | |||
| 302 | =item * CPAN Ratings | ||
| 303 | |||
| 304 | L<http://cpanratings.perl.org/i/FSA-Engine> | ||
| 305 | |||
| 306 | =item * RT: CPAN's request tracker | ||
| 307 | |||
| 308 | L<http://rt.cpan.org/NoAuth/Bugs.html?Dist=FSA-Engine> | ||
| 309 | |||
| 310 | =item * Search CPAN | ||
| 311 | |||
| 312 | L<http://search.cpan.org/dist/FSA-Engine> | ||
| 313 | |||
| 314 | =back | ||
| 315 | |||
| 316 | =head1 SEE ALSO | ||
| 317 | |||
| 318 | This module was influenced in part by L<FSA::Rules> which implements | ||
| 319 | an FSA using a traditional Perl OO method. | ||
| 320 | |||
| 321 | =head1 AUTHOR | ||
| 322 | |||
| 323 | Ian C. Docherty <pause@iandocherty.com> | ||
| 324 | |||
| 325 | Thanks also to James Spurin <pause@twitchy.net> for support and advice. | ||
| 326 | |||
| 327 | Thanks to various members of the Moose mailing list for recommendations on how to name this module. | ||
| 328 | |||
| 329 | =head1 COPYRIGHT AND LICENSE | ||
| 330 | |||
| 331 | Copyright(c) 2011 Ian C. Docherty | ||
| 332 | |||
| 333 | This module is free software; you can distribute it and/or modify it under the same | ||
| 334 | terms as Perl itself. |