core/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   enum transition_type { SIMPLE, RANGE, TIMED };
  80   transition_type type;
  81   int next_state;
  82   int low_trigger, high_trigger;
  83   int time_span;
  84
  85   transition_info() {}  // blank.
  86   transition_info(int next) : type(SIMPLE), next_state(next) {}
  87   transition_info(int next, int time) : type(TIMED), next_state(next),
  88       time_span(time) {}
  89   transition_info(int next, int low, int high) : type(RANGE),
  90       next_state(next), low_trigger(low), high_trigger(high) {}
  91 };
  92
  93 struct state_info {
  94   int state_id;  // id for this state.
  95   array<transition_info> transitions;
  96
  97   state_info() : state_id(0) {}  // blank.
  98   state_info(int state_id_in) : state_id(state_id_in) {}
  99 };
 100
 101 //////////////
 102
 103 class state_machine_override_array : public array<override> {};
 104 class state_machine_state_array : public array<state_info> {};
 105
 106 //////////////
 107
 108 state_machine::state_machine()
 109 : _current(0),
 110   _last(0),
 111   _trig(0),
 112   _type(SIMPLE),
 113   _start(new time_stamp()),
 114   _name(new astring()),
 115   _overrides(new state_machine_override_array)
 116 {}
 117
 118 state_machine::state_machine(const state_machine &to_copy)
 119 : root_object(),
 120   _current(0),
 121   _last(0),
 122   _trig(0),
 123   _type(SIMPLE),
 124   _start(new time_stamp()),
 125   _name(new astring()),
 126   _overrides(new state_machine_override_array)
 127 { *this = to_copy; }
 128
 129 state_machine::~state_machine()
 130 {
 131   WHACK(_start);
 132   WHACK(_name);
 133   WHACK(_overrides);
 134 }
 135
 136 int state_machine::update() { return 0; }
 137
 138 void state_machine::set_name(const astring &name) { *_name = name; }
 139
 140 astring state_machine::get_name() const { return *_name; }
 141
 142 state_machine &state_machine::operator = (const state_machine &to_copy)
 143 {
 144   if (&to_copy == this) return *this;
 145   _current = to_copy._current;
 146   _last = to_copy._last;
 147   _trig = to_copy._trig;
 148   _type = to_copy._type;
 149   *_start = *to_copy._start;
 150   *_name = *to_copy._name;
 151   *_overrides = *to_copy._overrides;
 152 //careful when overrides becomes hidden internal type.
 153   return *this;
 154 }
 155
 156 int state_machine::duration_index(int current, int next) const
 157 {
 158   for (int i = 0; i < _overrides->length(); i++)
 159     if ( ((*_overrides)[i].current == current)
 160         && ((*_overrides)[i].next == next) )
 161       return i;
 162   return common::NOT_FOUND;
 163 }
 164
 165 void state_machine::set_state(int new_current, int new_last, int trigger,
 166     transition_types type)
 167 {
 168   _current = new_current;
 169   _last = new_last;
 170   _trig = trigger;
 171   _type = type;
 172   _start->reset();
 173 }
 174
 175 void state_machine::override_timing(int current, int next, int duration)
 176 {
 177   int indy = duration_index(current, next);
 178   if (non_negative(indy)) {
 179     // found an existing record for this current/next pair.
 180     if (!duration) {
 181       // zero duration means removal.
 182       _overrides->zap(indy, indy);
 183       return;
 184     }
 185     // reset the duration.
 186     (*_overrides)[indy].duration = duration;
 187     return;
 188   }
 189   // no existing record, so add one.
 190   *_overrides += override(current, next, duration);
 191 }
 192
 193 int state_machine::duration_override(int current, int next) const
 194 {
 195   int indy = duration_index(current, next);
 196   if (negative(indy)) return 0;
 197   return (*_overrides)[indy].duration;
 198 }
 199
 200 time_stamp state_machine::start() const { return *_start; }
 201
 202 //////////////
 203
 204 transition_map::transition_map()
 205 : _valid(false),
 206   _start_state(0),
 207   _state_list(new state_machine_state_array)
 208 {}
 209
 210 transition_map::~transition_map()
 211 {
 212   _valid = false;
 213   WHACK(_state_list);
 214 }
 215
 216 // informational functions:
 217
 218 int transition_map::states() const { return _state_list->length(); }
 219
 220 int transition_map::state_index(int state_id) const
 221 {
 222   for (int i = 0; i < states(); i++)
 223     if ((*_state_list)[i].state_id == state_id) return i;
 224   return common::NOT_FOUND;
 225 }
 226
 227 int transition_map::transition_index(int state_index, int next, int &start)
 228 {
 229   bounds_return(state_index, 0, states() - 1, common::BAD_INPUT);
 230   state_info &state = (*_state_list)[state_index];
 231   bounds_return(start, 0, state.transitions.length() - 1, common::BAD_INPUT);
 232   // loop over the transitions by using our external index.
 233   for (start = start; start < state.transitions.length(); start++)
 234     if (state.transitions[start].next_state == next) {
 235       start++;  // position it after this index.
 236       return start - 1;  // return this index.
 237     }
 238   return common::NOT_FOUND;
 239 }
 240
 241 // configurational functions:
 242
 243 void transition_map::reconfigure() { _valid = false; }
 244
 245 outcome transition_map::validate(int &examine)
 246 {
 247   // check for a bad starting state...
 248   examine = _start_state;
 249   FIND_STATE(_start_state) BAD_START;
 250
 251   if (!check_reachability(examine)) return UNREACHABLE;
 252     // a state is unreachable from the starting state.
 253   if (!check_overlapping(examine)) return OVERLAPPING_RANGES;
 254     // bad (overlapping) ranges were found in one state.
 255   _valid = true;  // set us to operational.
 256   return OKAY;
 257 }
 258
 259 bool transition_map::add_state(int state_number)
 260 {
 261   if (valid()) return false;  // this is operational; no more config!
 262   if (!state_number) return false;  // zero is disallowed.
 263   if (non_negative(state_index(state_number))) return false;  // already exists.
 264   *_state_list += state_info(state_number);
 265   return true;
 266 }
 267
 268 bool transition_map::set_start(int starting_state)
 269 {
 270   if (valid()) return false;  // this is operational; no more config!
 271   if (!starting_state) return false;
 272
 273   FIND_STATE(starting_state) false;  // doesn't exist.
 274
 275   _start_state = starting_state;
 276   return true;
 277 }
 278
 279 bool transition_map::add_simple_transition(int current, int next)
 280 {
 281   if (valid()) return false;  // this is operational; no more config!
 282   CHECK_STATES;
 283   (*_state_list)[indy].transitions += transition_info(next);
 284   return true;
 285 }
 286
 287 bool transition_map::add_range_transition(int current, int next, int low, int high)
 288 {
 289   if (valid()) return false;  // this is operational; no more config!
 290   CHECK_STATES;
 291   (*_state_list)[indy].transitions += transition_info(next, low, high);
 292   return true;
 293 }
 294
 295 bool transition_map::add_timed_transition(int current, int next, int length)
 296 {
 297   if (valid()) return false;  // this is operational; no more config!
 298   CHECK_STATES;
 299   state_info &found = (*_state_list)[indy];
 300   // locates any existing timed transition and re-uses its slot.
 301   for (int i = 0; i < found.transitions.length(); i++)
 302     if (found.transitions[i].type == transition_info::TIMED) {
 303       found.transitions[i] = transition_info(next, length);
 304       return true;
 305     }
 306   // no existing timed transition found, so add a new one.
 307   (*_state_list)[indy].transitions += transition_info(next, length);
 308   return true;
 309 }
 310
 311 // operational functions:
 312
 313 bool transition_map::make_transition(state_machine &m, int next)
 314 {
 315   if (!valid()) return false;  // this is not operational yet!
 316   CHECK_VALID(m);
 317 #ifdef DEBUG_STATE_MACHINE
 318   if (negative(state_index(m._current)))
 319     LOG(astring("(%s) transition_map::make_transition: bad logic error; machine's "
 320         "state is missing.", m._name->s()));
 321   if (negative(state_index(next)))
 322     LOG(astring("(%s) transition_map::make_transition: next state parameter is invalid.",
 323         m._name->s()));
 324 #endif
 325   FIND_STATE(m._current) false;  // bad next state.
 326   int start = 0;
 327   if (negative(transition_index(indy, next, start))) return false;
 328     // no transition exists for that next state.
 329   MOVE_STATE(m, next, state_machine::SIMPLE, 0);
 330   int trig = m.update();
 331   if (trig) return pulse(m, trig);
 332   return true;
 333 }
 334
 335 bool transition_map::pulse(state_machine &m, int trigger)
 336 {
 337   if (!valid()) return false;  // this is not operational yet!
 338   CHECK_VALID(m);
 339 #ifdef DEBUG_STATE_MACHINE
 340   if (negative(state_index(m._current)))
 341     LOG(astring("(%s) transition_map::pulse: bad logic error; state is missing.", m._name->s()));
 342 #endif
 343   FIND_STATE(m._current) false;  // logic error!
 344   state_info &found = (*_state_list)[indy];
 345   for (int i = 0; i < found.transitions.length(); i++) {
 346     if (found.transitions[i].type == transition_info::RANGE) {
 347       // found the right type of transition.
 348       transition_info &tran = found.transitions[i];
 349       if ( (tran.low_trigger <= trigger)
 350             && (tran.high_trigger >= trigger) ) {
 351         // found a transition with an acceptable range.
 352         MOVE_STATE(m, tran.next_state, state_machine::RANGE, trigger);
 353         int trig = m.update();
 354         if (trig) return pulse(m, trig);
 355         return true;
 356       }
 357     }
 358   }
 359   return false;
 360 }
 361
 362 bool transition_map::time_slice(state_machine &m)
 363 {
 364   if (!valid()) return false;  // this is not operational yet!
 365   CHECK_VALID(m);
 366
 367 #ifdef DEBUG_STATE_MACHINE
 368   if (negative(state_index(m._current)))
 369     LOG(astring("(%s) transition_map::time_slice: bad logic error; state "
 370         "is missing.", m._name->s()));
 371 #endif
 372   FIND_STATE(m._current) false;  // logic error!
 373
 374   state_info &found = (*_state_list)[indy];
 375   for (int i = 0; i < found.transitions.length(); i++) {
 376     if (found.transitions[i].type == transition_info::TIMED) {
 377       // found the right type of transition.
 378       transition_info &tran = found.transitions[i];
 379       int duration = tran.time_span;
 380       int override = m.duration_override(m._current, tran.next_state);
 381       if (override) duration = override;
 382       if (*m._start < time_stamp(-duration)) {
 383         // found a transition with an expired time.
 384         MOVE_STATE(m, tran.next_state, state_machine::TIMED, 0);
 385         int trig = m.update();
 386         if (trig) return pulse(m, trig);
 387         return true;
 388       }
 389     }
 390   }
 391   return false;
 392 }
 393
 394 bool transition_map::reset(state_machine &m)
 395 {
 396   if (!valid()) return false;  // this is not operational yet!
 397   m._current = _start_state;
 398   m._last = _start_state;
 399   m._trig = 0;
 400   m._type = state_machine::SIMPLE;
 401   m._start->reset();
 402   return true;
 403 }
 404
 405 bool transition_map::check_overlapping(int &examine)
 406 {
 407   FUNCDEF("check_overlapping");
 408   examine = 0;
 409   for (int i = 0; i < states(); i++) {
 410     examine = i;
 411     for (int j = 0; j < (*_state_list)[i].transitions.length(); j++) {
 412       transition_info &a = (*_state_list)[i].transitions[j];
 413       if (a.type != transition_info::RANGE) continue;
 414       for (int k = j + 1; k < (*_state_list)[i].transitions.length(); k++) {
 415         transition_info &b = (*_state_list)[i].transitions[k];
 416         if (b.type != transition_info::RANGE) continue;
 417         if ( (b.low_trigger <= a.low_trigger)
 418               && (b.high_trigger >= a.low_trigger) ) {
 419           LOG(astring("intersecting range on low end!"));
 420           return false;
 421         }
 422         if ( (b.low_trigger <= a.high_trigger)
 423               && (b.high_trigger >= a.high_trigger) ) {
 424           LOG(astring("intersecting range on high end!"));
 425           return false;
 426         }
 427       }
 428     }
 429   }
 430   return true;
 431 }
 432
 433 bool transition_map::check_reachability(int &examine)
 434 {
 435   FUNCDEF("check_reachability");
 436   examine = 0;
 437
 438   // list_to_add: the list of states that are definitely reachable and that
 439   // need to be considered.
 440   int_array list_to_add;
 441   list_to_add += _start_state;
 442
 443   // already_checked: those states that have already been completely considered
 444   // as to their reachability.
 445   array<bool> already_checked(states());
 446   for (int i = 0; i < already_checked.length(); i++)
 447     already_checked[i] = false;
 448
 449   while (list_to_add.length()) {
 450     // the next state that IS reachable has all of the states reachable from
 451     // it added to the list of states that are to be checked...
 452     examine = list_to_add[0];
 453     int indy = state_index(examine);
 454     if (negative(indy)) {
 455       LOG(a_sprintf("bad state index for state %d!", examine));
 456       return false;
 457     }
 458 #ifdef DEBUG_STATE_MACHINE
 459     LOG(a_sprintf("state to add is %d, list size=%d.", examine,
 460         list_to_add.length()));
 461 #endif
 462     // delete the item that we are now checking.
 463     list_to_add.zap(0, 0);
 464
 465     // check whether this item has already had its kids (those states reachable
 466     // from it) added to the list to add.  if so, skip it.
 467     if (already_checked[indy]) continue;
 468
 469     // update the information for this state we are considering in the list of
 470     // already checked states.
 471     already_checked[indy] = true;
 472
 473     state_info &found = (*_state_list)[indy];
 474
 475     // all states this one can reach are added to the list to check.
 476     for (int i = 0; i < found.transitions.length(); i++) {
 477 #ifdef DEBUG_STATE_MACHINE
 478       LOG(astring("checking transition %d: ", i));
 479 #endif
 480       int now_reachable = found.transitions[i].next_state;
 481 #ifdef DEBUG_STATE_MACHINE
 482       LOG(astring("now reaching %d.", now_reachable));
 483 #endif
 484       if (now_reachable == examine) continue;
 485       else {
 486         int indy = state_index(now_reachable);
 487         if (already_checked[indy]) continue;
 488       }
 489       list_to_add += now_reachable;
 490     }
 491   }
 492 #ifdef DEBUG_STATE_MACHINE
 493   LOG("done checking reachability.");
 494 #endif
 495   for (int j = 0; j < already_checked.length(); j++)
 496     if (!already_checked.get(j)) {
 497       examine = (*_state_list)[j].state_id;
 498       LOG(a_sprintf("state %d is not reachable", examine));
 499       return false;
 500     }
 501   return true;  // all states are reachable.
 502 }
 503
 504 } //namespace.
 505