new fortune
[feisty_meow.git] / nucleus / library / processes / state_machine.cpp
1 /*****************************************************************************\
2 *                                                                             *
3 *  Name   : state_machine                                                     *
4 *  Author : Chris Koeritz                                                     *
5 *                                                                             *
6 *******************************************************************************
7 * Copyright (c) 1992-$now By Author.  This program is free software; you can  *
8 * redistribute it and/or modify it under the terms of the GNU General Public  *
9 * License as published by the Free Software Foundation; either version 2 of   *
10 * the License or (at your option) any later version.  This is online at:      *
11 *     http://www.fsf.org/copyleft/gpl.html                                    *
12 * Please send any updates to: fred@gruntose.com                               *
13 \*****************************************************************************/
14
15 #include "state_machine.h"
16
17 #include <basis/array.h>
18 #include <basis/functions.h>
19 #include <basis/guards.h>
20 #include <basis/astring.h>
21 #include <loggers/program_wide_logger.h>
22 #include <timely/time_stamp.h>
23
24 using namespace basis;
25 using namespace loggers;
26 using namespace timely;
27
28 namespace processes {
29
30 //////////////
31
32 //#define DEBUG_STATE_MACHINE
33   // uncomment if you want the debugging version.
34
35 //hmmm: implement logging...
36 #undef LOG
37 #ifndef DEBUG_STATE_MACHINE
38   #define LOG(to_print) CLASS_EMERGENCY_LOG(program_wide_logger::get(), to_print)
39 #else
40   #define LOG(to_print) {}
41 #endif
42
43 //////////////
44
45 // checks whether the machine passed in is valid or not.
46 #define CHECK_VALID(m) \
47   if (!m._current) return false; \
48   if (!m._last) return false
49
50 // checks whether the current and next states exist or not.
51 #define CHECK_STATES \
52   if (!current) return false; \
53   if (!next) return false; \
54   int indy = state_index(current); \
55   if (negative(indy)) return false; \
56   if (negative(state_index(next))) return false
57
58 // moves to a new state and resets the new state's timestamp.
59 #define MOVE_STATE(m, next, type, trigger) \
60   m._last = m._current; \
61   m._current = next; \
62   m._type = type; \
63   m._trig = trigger; \
64   m._start->reset()
65
66 // locates a state or returns.
67 #define FIND_STATE(state) \
68   int indy = state_index(state); \
69   if (negative(indy)) return
70
71 //////////////
72
73 struct override { int current; int next; int duration;
74   override(int _current = 0, int _next = 0, int _duration = 0)
75     : current(_current), next(_next), duration(_duration) {}
76 };
77
78         struct transition_info
79         {
80                 enum transition_type
81                 {
82                         SIMPLE, RANGE, TIMED
83                 };
84                 transition_type type;
85                 int next_state;
86                 int low_trigger, high_trigger;
87                 int time_span;
88
89                 // blank constructor.
90                 transition_info()
91                 : type(RANGE), next_state(0), low_trigger(0), high_trigger(0), time_span(0)
92                 {
93                 }
94
95                 transition_info(int next)
96                                 : type(SIMPLE), next_state(next),
97                                   low_trigger(0), high_trigger(0), time_span(0)
98                 {
99                 }
100
101                 transition_info(int next, int time)
102                                 : type(TIMED), next_state(next), time_span(time), low_trigger(0), high_trigger(0)
103                 {
104                 }
105
106                 transition_info(int next, int low, int high)
107                                 : type(RANGE), next_state(next), low_trigger(low), high_trigger(high), time_span(0)
108                 {
109                 }
110         };
111
112 struct state_info {
113   int state_id;  // id for this state.
114   array<transition_info> transitions;
115
116   state_info() : state_id(0) {}  // blank.
117   state_info(int state_id_in) : state_id(state_id_in) {}
118 };
119
120 //////////////
121
122 class state_machine_override_array : public array<override> {};
123 class state_machine_state_array : public array<state_info> {};
124
125 //////////////
126
127 state_machine::state_machine()
128 : _current(0),
129   _last(0),
130   _trig(0),
131   _type(SIMPLE),
132   _start(new time_stamp()),
133   _name(new astring()),
134   _overrides(new state_machine_override_array)
135 {}
136
137 state_machine::state_machine(const state_machine &to_copy)
138 : root_object(),
139   _current(0),
140   _last(0),
141   _trig(0),
142   _type(SIMPLE),
143   _start(new time_stamp()),
144   _name(new astring()),
145   _overrides(new state_machine_override_array)
146 { *this = to_copy; }
147
148 state_machine::~state_machine()
149 {
150   WHACK(_start);
151   WHACK(_name);
152   WHACK(_overrides);
153 }
154
155 int state_machine::update() { return 0; }
156
157 void state_machine::set_name(const astring &name) { *_name = name; }
158
159 astring state_machine::get_name() const { return *_name; }
160
161 state_machine &state_machine::operator = (const state_machine &to_copy)
162 {
163   if (&to_copy == this) return *this;
164   _current = to_copy._current;
165   _last = to_copy._last;
166   _trig = to_copy._trig;
167   _type = to_copy._type;
168   *_start = *to_copy._start;
169   *_name = *to_copy._name;
170   *_overrides = *to_copy._overrides;
171 //careful when overrides becomes hidden internal type.
172   return *this;
173 }
174
175 int state_machine::duration_index(int current, int next) const
176 {
177   for (int i = 0; i < _overrides->length(); i++)
178     if ( ((*_overrides)[i].current == current)
179         && ((*_overrides)[i].next == next) )
180       return i;
181   return common::NOT_FOUND;
182 }
183
184 void state_machine::set_state(int new_current, int new_last, int trigger,
185     transition_types type)
186 {
187   _current = new_current;
188   _last = new_last;
189   _trig = trigger;
190   _type = type;
191   _start->reset();
192 }
193
194 void state_machine::override_timing(int current, int next, int duration)
195 {
196   int indy = duration_index(current, next);
197   if (non_negative(indy)) {
198     // found an existing record for this current/next pair.
199     if (!duration) {
200       // zero duration means removal.
201       _overrides->zap(indy, indy);
202       return;
203     }
204     // reset the duration.
205     (*_overrides)[indy].duration = duration;
206     return;
207   }
208   // no existing record, so add one.
209   *_overrides += override(current, next, duration);
210 }
211
212 int state_machine::duration_override(int current, int next) const
213 {
214   int indy = duration_index(current, next);
215   if (negative(indy)) return 0;
216   return (*_overrides)[indy].duration;
217 }
218
219 time_stamp state_machine::start() const { return *_start; }
220
221 //////////////
222
223 transition_map::transition_map()
224 : _valid(false),
225   _start_state(0),
226   _state_list(new state_machine_state_array)
227 {}
228
229 transition_map::~transition_map()
230 {
231   _valid = false;
232   WHACK(_state_list);
233 }
234
235 // informational functions:
236
237 int transition_map::states() const { return _state_list->length(); }
238
239 int transition_map::state_index(int state_id) const
240 {
241   for (int i = 0; i < states(); i++)
242     if ((*_state_list)[i].state_id == state_id) return i;
243   return common::NOT_FOUND;
244 }
245
246 int transition_map::transition_index(int state_index, int next, int &start)
247 {
248   bounds_return(state_index, 0, states() - 1, common::BAD_INPUT);
249   state_info &state = (*_state_list)[state_index];
250   bounds_return(start, 0, state.transitions.length() - 1, common::BAD_INPUT);
251   // loop over the transitions by using our external index.
252   for (; start < state.transitions.length(); start++)
253     if (state.transitions[start].next_state == next) {
254       start++;  // position it after this index.
255       return start - 1;  // return this index.
256     }
257   return common::NOT_FOUND;
258 }
259
260 // configurational functions:
261
262 void transition_map::reconfigure() { _valid = false; }
263
264 outcome transition_map::validate(int &examine)
265 {
266   // check for a bad starting state...
267   examine = _start_state;
268   FIND_STATE(_start_state) BAD_START;
269
270   if (!check_reachability(examine)) return UNREACHABLE;
271     // a state is unreachable from the starting state.
272   if (!check_overlapping(examine)) return OVERLAPPING_RANGES;
273     // bad (overlapping) ranges were found in one state.
274   _valid = true;  // set us to operational.
275   return OKAY;
276 }
277
278 bool transition_map::add_state(int state_number)
279 {
280   if (valid()) return false;  // this is operational; no more config!
281   if (!state_number) return false;  // zero is disallowed.
282   if (non_negative(state_index(state_number))) return false;  // already exists.
283   *_state_list += state_info(state_number);
284   return true;
285 }
286
287 bool transition_map::set_start(int starting_state)
288 {
289   if (valid()) return false;  // this is operational; no more config!
290   if (!starting_state) return false;
291
292   FIND_STATE(starting_state) false;  // doesn't exist.
293
294   _start_state = starting_state;
295   return true;
296 }
297
298 bool transition_map::add_simple_transition(int current, int next)
299 {
300   if (valid()) return false;  // this is operational; no more config!
301   CHECK_STATES;
302   (*_state_list)[indy].transitions += transition_info(next);
303   return true;
304 }
305
306 bool transition_map::add_range_transition(int current, int next, int low, int high)
307 {
308   if (valid()) return false;  // this is operational; no more config!
309   CHECK_STATES;
310   (*_state_list)[indy].transitions += transition_info(next, low, high);
311   return true;
312 }
313
314 bool transition_map::add_timed_transition(int current, int next, int length)
315 {
316   if (valid()) return false;  // this is operational; no more config!
317   CHECK_STATES;
318   state_info &found = (*_state_list)[indy];
319   // locates any existing timed transition and re-uses its slot.
320   for (int i = 0; i < found.transitions.length(); i++)
321     if (found.transitions[i].type == transition_info::TIMED) {
322       found.transitions[i] = transition_info(next, length);
323       return true;
324     }
325   // no existing timed transition found, so add a new one.
326   (*_state_list)[indy].transitions += transition_info(next, length);
327   return true;
328 }
329
330 // operational functions:
331
332 bool transition_map::make_transition(state_machine &m, int next)
333 {
334   if (!valid()) return false;  // this is not operational yet!
335   CHECK_VALID(m);
336 #ifdef DEBUG_STATE_MACHINE
337   if (negative(state_index(m._current)))
338     LOG(astring("(%s) transition_map::make_transition: bad logic error; machine's "
339         "state is missing.", m._name->s()));
340   if (negative(state_index(next)))
341     LOG(astring("(%s) transition_map::make_transition: next state parameter is invalid.",
342         m._name->s()));
343 #endif
344   FIND_STATE(m._current) false;  // bad next state.
345   int start = 0;
346   if (negative(transition_index(indy, next, start))) return false;
347     // no transition exists for that next state.
348   MOVE_STATE(m, next, state_machine::SIMPLE, 0);
349   int trig = m.update();
350   if (trig) return pulse(m, trig);
351   return true;
352 }
353
354 bool transition_map::pulse(state_machine &m, int trigger)
355 {
356   if (!valid()) return false;  // this is not operational yet!
357   CHECK_VALID(m);
358 #ifdef DEBUG_STATE_MACHINE
359   if (negative(state_index(m._current)))
360     LOG(astring("(%s) transition_map::pulse: bad logic error; state is missing.", m._name->s()));
361 #endif
362   FIND_STATE(m._current) false;  // logic error!
363   state_info &found = (*_state_list)[indy];
364   for (int i = 0; i < found.transitions.length(); i++) {
365     if (found.transitions[i].type == transition_info::RANGE) {
366       // found the right type of transition.
367       transition_info &tran = found.transitions[i];
368       if ( (tran.low_trigger <= trigger)
369             && (tran.high_trigger >= trigger) ) {
370         // found a transition with an acceptable range.
371         MOVE_STATE(m, tran.next_state, state_machine::RANGE, trigger);
372         int trig = m.update();
373         if (trig) return pulse(m, trig);
374         return true;
375       }
376     }
377   }
378   return false;
379 }
380
381 bool transition_map::time_slice(state_machine &m)
382 {
383   if (!valid()) return false;  // this is not operational yet!
384   CHECK_VALID(m);
385
386 #ifdef DEBUG_STATE_MACHINE
387   if (negative(state_index(m._current)))
388     LOG(astring("(%s) transition_map::time_slice: bad logic error; state "
389         "is missing.", m._name->s()));
390 #endif
391   FIND_STATE(m._current) false;  // logic error!
392
393   state_info &found = (*_state_list)[indy];
394   for (int i = 0; i < found.transitions.length(); i++) {
395     if (found.transitions[i].type == transition_info::TIMED) {
396       // found the right type of transition.
397       transition_info &tran = found.transitions[i];
398       int duration = tran.time_span;
399       int override = m.duration_override(m._current, tran.next_state);
400       if (override) duration = override;
401       if (*m._start < time_stamp(-duration)) {
402         // found a transition with an expired time.
403         MOVE_STATE(m, tran.next_state, state_machine::TIMED, 0);
404         int trig = m.update();
405         if (trig) return pulse(m, trig);
406         return true;
407       }
408     }
409   }
410   return false;
411 }
412
413 bool transition_map::reset(state_machine &m)
414 {
415   if (!valid()) return false;  // this is not operational yet!
416   m._current = _start_state;
417   m._last = _start_state;
418   m._trig = 0;
419   m._type = state_machine::SIMPLE;
420   m._start->reset();
421   return true;
422 }
423
424 bool transition_map::check_overlapping(int &examine)
425 {
426   FUNCDEF("check_overlapping");
427   examine = 0;
428   for (int i = 0; i < states(); i++) {
429     examine = i;
430     for (int j = 0; j < (*_state_list)[i].transitions.length(); j++) {
431       transition_info &a = (*_state_list)[i].transitions[j];
432       if (a.type != transition_info::RANGE) continue;
433       for (int k = j + 1; k < (*_state_list)[i].transitions.length(); k++) {
434         transition_info &b = (*_state_list)[i].transitions[k];
435         if (b.type != transition_info::RANGE) continue;
436         if ( (b.low_trigger <= a.low_trigger)
437               && (b.high_trigger >= a.low_trigger) ) {
438           LOG(astring("intersecting range on low end!"));
439           return false;
440         }
441         if ( (b.low_trigger <= a.high_trigger)
442               && (b.high_trigger >= a.high_trigger) ) {
443           LOG(astring("intersecting range on high end!"));
444           return false;
445         }
446       }
447     }
448   }
449   return true;
450 }
451
452 bool transition_map::check_reachability(int &examine)
453 {
454   FUNCDEF("check_reachability");
455   examine = 0;
456
457   // list_to_add: the list of states that are definitely reachable and that
458   // need to be considered.
459   int_array list_to_add;
460   list_to_add += _start_state;
461
462   // already_checked: those states that have already been completely considered
463   // as to their reachability.
464   array<bool> already_checked(states());
465   for (int i = 0; i < already_checked.length(); i++)
466     already_checked[i] = false;
467
468   while (list_to_add.length()) {
469     // the next state that IS reachable has all of the states reachable from
470     // it added to the list of states that are to be checked...
471     examine = list_to_add[0];
472     int indy = state_index(examine);
473     if (negative(indy)) {
474       LOG(a_sprintf("bad state index for state %d!", examine));
475       return false;
476     }
477 #ifdef DEBUG_STATE_MACHINE
478     LOG(a_sprintf("state to add is %d, list size=%d.", examine,
479         list_to_add.length()));
480 #endif
481     // delete the item that we are now checking.
482     list_to_add.zap(0, 0);
483
484     // check whether this item has already had its kids (those states reachable
485     // from it) added to the list to add.  if so, skip it.
486     if (already_checked[indy]) continue;
487
488     // update the information for this state we are considering in the list of
489     // already checked states.
490     already_checked[indy] = true;
491
492     state_info &found = (*_state_list)[indy];
493
494     // all states this one can reach are added to the list to check.
495     for (int i = 0; i < found.transitions.length(); i++) {
496 #ifdef DEBUG_STATE_MACHINE
497       LOG(astring("checking transition %d: ", i));
498 #endif
499       int now_reachable = found.transitions[i].next_state;
500 #ifdef DEBUG_STATE_MACHINE
501       LOG(astring("now reaching %d.", now_reachable));
502 #endif
503       if (now_reachable == examine) continue;
504       else {
505         int indy = state_index(now_reachable);
506         if (already_checked[indy]) continue;
507       }
508       list_to_add += now_reachable;
509     }
510   }
511 #ifdef DEBUG_STATE_MACHINE
512   LOG("done checking reachability.");
513 #endif
514   for (int j = 0; j < already_checked.length(); j++)
515     if (!already_checked.get(j)) {
516       examine = (*_state_list)[j].state_id;
517       LOG(a_sprintf("state %d is not reachable", examine));
518       return false;
519     }
520   return true;  // all states are reachable.
521 }
522
523 } //namespace.
524