Edit comment text.
[synfig.git] / ETL / trunk / ETL / _smach.h
1 /*! ========================================================================
2 ** Extended Template and Library
3 ** State Machine Abstraction Class Implementation
4 ** $Id$
5 **
6 ** Copyright (c) 2002 Robert B. Quattlebaum Jr.
7 ** Copyright (c) 2008 Chris Moore
8 **
9 ** This package is free software; you can redistribute it and/or
10 ** modify it under the terms of the GNU General Public License as
11 ** published by the Free Software Foundation; either version 2 of
12 ** the License, or (at your option) any later version.
13 **
14 ** This package is distributed in the hope that it will be useful,
15 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
16 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 ** General Public License for more details.
18 **
19 ** === N O T E S ===========================================================
20 **
21 ** ========================================================================= */
22
23 /* === S T A R T =========================================================== */
24
25 #ifndef __ETL__SMACH_H_
26 #define __ETL__SMACH_H_
27
28 /* === H E A D E R S ======================================================= */
29
30 #include <vector>
31 #include <algorithm>
32 #include <stdexcept>
33 #include "_mutex_null.h"
34 #include "_misc.h"
35
36 /* === M A C R O S ========================================================= */
37
38 #define SMACH_STATE_STACK_SIZE          (32)
39
40 #ifdef _MSC_VER
41 #pragma warning (disable:4786)
42 #pragma warning (disable:4290) // MSVC6 doesn't like function declarations with exception specs
43 #endif
44
45 //#define ETL_MUTEX_LOCK()              _mutex::lock lock(mutex)
46 #define ETL_MUTEX_LOCK()
47
48 /* === T Y P E D E F S ===================================================== */
49
50 /* === C L A S S E S & S T R U C T S ======================================= */
51
52 _ETL_BEGIN_NAMESPACE
53
54 /*! ========================================================================
55 ** \class       smach
56 ** \brief       Templatized State Machine
57 **
58 ** A more detailed description needs to be written.
59 */
60 template <typename CON, typename K=int, typename M=mutex_null>
61 class smach
62 {
63 public:
64
65         typedef K event_key;
66         typedef M _mutex;
67         typedef CON context_type;
68
69
70         struct egress_exception { };
71         struct pop_exception { };
72
73
74         //! Result type for event processing
75         enum event_result
76         {
77                 // These values are returned by the event
78                 // handlers cast to state pointers.
79                 RESULT_ERROR,           //!< General error or malfunction
80                 RESULT_OK,                      //!< Event has been processed
81                 RESULT_ACCEPT,          //!< The event has been explicitly accepted.
82                 RESULT_REJECT,          //!< The event has been explicitly rejected.
83
84                 RESULT_END                      //!< Not a valid result
85         };
86
87         //template<typename T> class state;
88
89         //! Event base class
90         struct event
91         {
92                 event_key key;
93
94                 event() { }
95                 event(const event_key& key):key(key) { }
96
97                 operator event_key()const { return key; }
98         };
99
100         //! Event definition class
101         template<typename T>
102         class event_def_internal
103         {
104                 // List our friends
105                 friend class smach;
106                 //friend class state<T>;
107
108         public:
109                 typedef T state_context_type;
110
111                 //! Event function type
112                 typedef event_result (T::*funcptr)(const event&);
113
114         //private:
115
116                 event_key id;           //<! Event ID
117                 funcptr handler;        //<! Pointer event handler
118
119         public:
120
121                 //! Less-than operator for sorting. Based on event_key value.
122                 bool operator<(const event_def_internal &rhs)const
123                         { return id<rhs.id; }
124
125                 //! Equal-to operator. Based on event_key value.
126                 bool operator==(const event_def_internal &rhs)const
127                         { return id==rhs.id; }
128
129                 //! Less-than operator for finding.
130                 bool operator<(const event_key &rhs)const
131                         { return id<rhs; }
132
133                 //! Equal-to operator. Based on event_key value.
134                 bool operator==(const event_key &rhs)const
135                         { return id==rhs; }
136
137                 //! Trivial Constructor
138                 event_def_internal() { }
139
140                 //! Constructor for creating an event_def_internal from the given key and function reference.
141                 event_def_internal(event_key a, funcptr b):id(a),handler(b) { }
142
143                 //! Copy constructor
144                 event_def_internal(const event_def_internal &x):id(x.id),handler(x.handler) { }
145
146         };
147
148         class state_base
149         {
150                 // Our parent is our friend
151                 friend class smach;
152         public:
153                 virtual ~state_base() { }
154
155                 virtual void* enter_state(context_type* machine_context)const=0;
156
157                 virtual bool leave_state(void* state_context)const=0;
158
159                 virtual event_result process_event(void* state_context,const event& id)const=0;
160
161                 virtual const char *get_name() const=0;
162         };
163
164         //! State class
165         template<typename T>
166         class state : public state_base
167         {
168                 // Our parent is our friend
169                 friend class smach;
170
171         public:
172                 typedef event_def_internal<T> event_def;
173                 typedef T state_context_type;
174
175
176         private:
177
178                 std::vector<event_def> event_list;
179
180                 smach *nested;          //! Nested machine
181                 event_key low,high;     //! Lowest and Highest event values
182                 const char *name;       //! Name of the state
183                 typename event_def::funcptr default_handler;    //! Default handler for unknown key
184
185         public:
186
187                 //! Constructor
188                 state(const char *n, smach* nest=0):
189                         nested(nest),name(n),default_handler(NULL)
190                 { }
191
192                 virtual ~state() { }
193
194                 //! Setup a nested state machine
195                 /*! A more detailed explanation needs to be written */
196                 void set_nested_machine(smach *sm) { nested=sm; }
197
198                 //! Sets the default handler
199                 void set_default_handler(const typename event_def::funcptr &x) { default_handler=x; }
200
201                 //! Returns given the name of the state
202                 virtual const char *get_name() const { return name; }
203
204                 state_context_type& get_context(smach& machine)
205                 {
206                         state_context_type *context(dynamic_cast<state_context_type*>(machine.state_context));
207                         if(context)
208                                 return context;
209
210                 }
211
212                 //! Adds an event_def onto the list and then make sure it is sorted correctly.
213                 void
214                 insert(const event_def &x)
215                 {
216                         // If this is our first event_def,
217                         // setup the high and low values.
218                         if(!event_list.size())
219                                 low=high=x.id;
220
221                         // Sort the event_def onto the list
222                         event_list.push_back(x);
223                         sort(event_list.begin(),event_list.end());
224
225                         // Update the low and high markers
226                         if(x.id<low)
227                                 low=x.id;
228                         if(high<x.id)
229                                 high=x.id;
230                 }
231
232                 typename std::vector<event_def>::iterator find(const event_key &x) { return binary_find(event_list.begin(),event_list.end(),x); }
233                 typename std::vector<event_def>::const_iterator find(const event_key &x)const { return binary_find(event_list.begin(),event_list.end(),x); }
234
235         protected:
236
237                 virtual void* enter_state(context_type* machine_context)const
238                 {
239                         return new state_context_type(machine_context);
240                 }
241
242                 virtual bool leave_state(void* x)const
243                 {
244                         state_context_type* state_context(reinterpret_cast<state_context_type*>(x));
245                         delete state_context;
246                         return true;
247                 }
248
249                 virtual event_result
250                 process_event(void* x,const event& id)const
251                 {
252                         state_context_type* state_context(reinterpret_cast<state_context_type*>(x));
253
254                         // Check for nested machine in state
255                         if(nested)
256                         {
257                                 const event_result ret(nested->process_event(id));
258                                 if(ret!=RESULT_OK)
259                                         return ret;
260                         }
261
262                         // Quick test to make sure that the
263                         // given event is in the state
264                         if(id.key<low || high<id.key)
265                                 return RESULT_OK;
266
267                         // Look for the event
268                         typename std::vector<event_def>::const_iterator iter(find(id.key));
269
270                         // If search results were negative, fail.
271                         if(iter->id!=id.key)
272                                 return RESULT_OK;
273
274                         // Execute event function
275                         event_result ret((state_context->*(iter->handler))(id));
276
277                         if(ret==RESULT_OK && default_handler)
278                                 ret=(state_context->*(default_handler))(id);
279
280                         return ret;
281                 }
282         };
283
284 private:
285
286         // Machine data
287         const state_base* curr_state;   //!< Current state of the machine
288         smach* child;                              //!< Child machine
289
290 public: // this really should be private
291         void* state_context;            //!< State Context
292 private:
293
294         context_type* machine_context;          //!< Machine Context
295
296         const state_base* default_state;
297         void*   default_context;
298
299 #ifdef ETL_MUTEX_LOCK
300         _mutex mutex;
301 #endif
302
303         //! State stack data
304         const state_base*       state_stack[SMACH_STATE_STACK_SIZE];
305         void*                           state_context_stack[SMACH_STATE_STACK_SIZE];
306         int                             states_on_stack;
307
308 public:
309
310         //! Gets the name of the currently active state
311         const char *
312         get_state_name()const
313         {
314 #ifdef ETL_MUTEX_LOCK
315                 ETL_MUTEX_LOCK();
316 #endif
317                 if(curr_state)
318                         return curr_state->get_name();
319                 if(default_state)
320                         return default_state->get_name();
321                 return 0;
322         }
323
324         //! Determines if a given event result is an error
325         /*! This function allows us to quickly see
326                 if an event_result contained an error */
327         static bool
328         event_error(const event_result &rhs)
329                 { return rhs<=RESULT_ERROR; }
330
331         bool
332         set_default_state(const state_base *nextstate)
333         {
334 #ifdef ETL_MUTEX_LOCK
335                 ETL_MUTEX_LOCK();
336 #endif
337                 // Keep track of the current state unless
338                 // the state switch fails
339                 const state_base *prev_state=default_state;
340
341                 // If we are already in a state, leave it and
342                 // collapse the state stack
343                 if(default_state)
344                         default_state->leave_state(default_context);
345
346                 // Set this as our current state
347                 default_state=nextstate;
348                 default_context=0;
349
350                 // Attempt to enter the state
351                 if(default_state)
352                 {
353                         default_context=default_state->enter_state(machine_context);
354                         if(default_context)
355                                 return true;
356                 }
357                 else
358                         return true;
359
360                 // We failed, so attempt to return to previous state
361                 default_state=prev_state;
362
363                 // If we had a previous state, enter it
364                 if(default_state)
365                         default_context=default_state->enter_state(machine_context);
366
367                 // At this point we are not in the
368                 // requested state, so return failure
369                 return false;
370         }
371
372         //! Leaves the current state
373         /*! Effectively makes the state_depth() function return zero. */
374         bool
375         egress()
376         {
377 #ifdef ETL_MUTEX_LOCK
378                 ETL_MUTEX_LOCK();
379 #endif
380
381                 // Pop all states off the state stack
382                 while(states_on_stack) pop_state();
383
384                 // If we are not in a state, then I guess
385                 // we were successful.
386                 if(!curr_state)
387                         return true;
388
389                 // Grab the return value from the exit function
390                 bool ret=true;
391
392                 const state_base* old_state=curr_state;
393                 void *old_context=state_context;
394
395                 // Clear out the current state and its state_context
396                 curr_state=0;state_context=0;
397
398                 // Leave the state
399                 return old_state->leave_state(old_context);
400
401                 return ret;
402         }
403
404         //! State entry function
405         /*! Attempts to enter the given state,
406                 popping off all states on the stack
407                 in the process. */
408         bool
409         enter(const state_base *nextstate)
410         {
411 #ifdef ETL_MUTEX_LOCK
412                 ETL_MUTEX_LOCK();
413 #endif
414
415                 // Keep track of the current state unless
416                 // the state switch fails
417                 const state_base *prev_state=curr_state;
418
419                 // If we are already in a state, leave it and
420                 // collapse the state stack
421                 if(curr_state)
422                         egress();
423
424                 // Set this as our current state
425                 curr_state=nextstate;
426                 state_context=0;
427
428                 // Attempt to enter the state
429                 state_context=curr_state->enter_state(machine_context);
430                 if(state_context)
431                         return true;
432
433                 // We failed, so attempt to return to previous state
434                 curr_state=prev_state;
435
436                 // If we had a previous state, enter it
437                 if(curr_state)
438                         state_context=curr_state->enter_state(machine_context);
439
440                 // At this point we are not in the
441                 // requested state, so return failure
442                 return false;
443         }
444
445         //! Pushes state onto state stack
446         /*! This allows you to enter a state without
447                 leaving your current state.
448                 \param   nextstate Pointer to the state to enter
449                 \sa      pop_state()
450         */
451         bool
452         push_state(const state_base *nextstate)
453         {
454 #ifdef ETL_MUTEX_LOCK
455                 ETL_MUTEX_LOCK();
456 #endif
457
458                 // If there are not enough slots, then throw something.
459                 if(states_on_stack==SMACH_STATE_STACK_SIZE)
460                         throw(std::overflow_error("smach<>::push_state(): state stack overflow!"));
461
462                 // If there is no current state, nor anything on stack,
463                 // just go ahead and enter the given state.
464                 if(!curr_state && !states_on_stack)
465                         return enter(nextstate);
466
467                 // Push the current state onto the stack
468                 state_stack[states_on_stack]=curr_state;
469                 state_context_stack[states_on_stack++]=state_context;
470
471                 // Make the next state the current state
472                 curr_state=nextstate;
473
474                 // Try to enter the next state
475                 state_context=curr_state->enter_state(machine_context);
476                 if(state_context)
477                         return true;
478
479                 // Unable to push state, return to old one
480                 curr_state=state_stack[--states_on_stack];
481                 state_context=state_context_stack[states_on_stack];
482                 return false;
483         }
484
485         //! Pops state off of state stack
486         /*! Decreases state depth */
487         void
488         pop_state()
489         {
490 #ifdef ETL_MUTEX_LOCK
491                 ETL_MUTEX_LOCK();
492 #endif
493
494                 // If we aren't in a state, then there is nothing
495                 // to do.
496                 if(!curr_state)
497                         throw(std::underflow_error("smach<>::pop_state(): stack is empty!"));
498
499                 if(states_on_stack)
500                 {
501                         const state_base* old_state=curr_state;
502                         void *old_context=state_context;
503
504                         // Pop previous state off of stack
505                         --states_on_stack;
506                         curr_state=state_stack[states_on_stack];
507                         state_context=state_context_stack[states_on_stack];
508
509                         old_state->leave_state(old_context);
510                 }
511                 else // If there are no states on stack, just egress
512                         egress();
513         }
514
515         //! State Machine Constructor
516         /*! A more detailed description needs to be written */
517         smach(context_type* machine_context=0):
518                 curr_state(0),
519                 child(0),
520                 state_context(0),
521                 machine_context(machine_context),
522                 default_state(0),
523                 default_context(0),
524                 states_on_stack(0)
525         { }
526
527         //! The destructor
528         ~smach()
529         {
530                 egress();
531
532                 if(default_state)
533                         default_state->leave_state(default_context);
534         }
535
536         //! Sets up a child state machine
537         /*! A child state machine runs in parallel with
538                 its parent, and gets event priority. This
539                 mechanism is useful in cases where an inherited
540                 object has its own state machine. */
541         void set_child(smach *x)
542         {
543 #ifdef ETL_MUTEX_LOCK
544                 ETL_MUTEX_LOCK();
545 #endif
546                 child=x;
547         }
548
549         //! Returns the number states currently active
550         int
551         state_depth()
552                 { return curr_state?states_on_stack+1:0; }
553
554         event_result
555         process_event(const event_key& id) { return process_event(event(id)); }
556
557         //! Process an event
558         event_result
559         process_event(const event& id)
560         {
561 #ifdef ETL_MUTEX_LOCK
562                 ETL_MUTEX_LOCK();
563 #endif
564
565                 event_result ret(RESULT_OK);
566
567                 // Check for child machine
568                 if(child)
569                 {
570                         ret=child->process_event(id);
571                         if(ret!=RESULT_OK)
572                                 return ret;
573                 }
574
575                 try
576                 {
577                         if(curr_state)
578                                 ret=curr_state->process_event(state_context,id);
579
580                         if(ret==RESULT_OK)
581                                 return default_state->process_event(default_context,id);
582
583                         return ret;
584                 }
585                 catch(egress_exception) { return egress()?RESULT_ACCEPT:RESULT_ERROR; }
586                 catch(pop_exception) { pop_state(); return RESULT_ACCEPT; }
587                 catch(const state_base* state) { return enter(state)?RESULT_ACCEPT:RESULT_ERROR; }
588         }
589
590 }; // END of template class smach
591
592 _ETL_END_NAMESPACE
593
594 /* === E X T E R N S ======================================================= */
595
596 /* === E N D =============================================================== */
597
598 #endif