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