1
0

Finite_State_Machine.php 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467
  1. <?php
  2. /**
  3. * Finite state machine skeleton
  4. *
  5. * @copyright (c) 2007 OSI
  6. * @author Frédéric G. MARAND
  7. * @license Licensed under the CeCILL 2.0
  8. * @version CVS: $Id: Finite_State_Machine.php,v 1.7 2007-06-03 21:24:29 marand Exp $
  9. * @link http://drupal.org/project/offload
  10. * @since Not applicable yet
  11. * @package fsm
  12. */
  13. require_once('misc.php'); // for func_name()
  14. error_reporting(E_ALL|E_STRICT);
  15. /**
  16. * This class defines a possible outcome for a given FSM transition
  17. *
  18. */
  19. class fsm_result
  20. {
  21. /**
  22. * The return value of the event handler
  23. * @var mixed
  24. */
  25. public $fsm_return;
  26. /**
  27. * The name of the state to which the FSM must change. If NULL, do not change
  28. * the current state.
  29. *
  30. * @var string
  31. */
  32. public $fsm_state;
  33. /**
  34. * The name of an event to be fired after the state change has been applied
  35. *
  36. * @var string
  37. */
  38. public $fsm_action;
  39. /**
  40. * @param string $state
  41. * @param string $action
  42. * @return void
  43. */
  44. public function __construct($return = NULL, $state = NULL, $action = NULL)
  45. {
  46. $this->fsm_return = $return;
  47. $this->fsm_state = $state;
  48. $this->fsm_action = $action;
  49. }
  50. }
  51. /**
  52. * This class must be inherited by code implementing actual FSMs.
  53. *
  54. * Applications must create a fsm descendant in which they will:
  55. *
  56. * - define the f_transitions table, usually in their constructor
  57. * - invoke the parent constructor to set up the FSM from the transitions table
  58. * - create "f_foo" functions for each "foo" event, except "idle", which is builtin.
  59. *
  60. * Applications may:
  61. * - disable event processing by setting $this->event to one of the fsm::EVENT_* constants
  62. * - disable post-event actions by setting $this->allows actions to false
  63. * - disable the builtin idle event by setting $this->idle_work to false
  64. * - query the current state by using $this->get_state()
  65. * - send an idle event by using $this->idle()
  66. * - submit any event (including idle) by using $this->apply_event($event_name)
  67. *
  68. */
  69. abstract class Finite_State_Machine
  70. {
  71. const IDLE_EVENT = 'idle'; // must not change name: method f_idle depends on it
  72. const INIT_STATE = 'init';
  73. const FINAL_STATE = 'final';
  74. const EVENT_NORMAL = 1; // processes events
  75. const EVENT_QUEUE = 2; // queue events for later use
  76. const EVENT_SINK = 3; // throw away events
  77. public $idle_work = TRUE;
  78. public $allow_actions = TRUE;
  79. protected $f_event_mode = Finite_State_Machine::EVENT_NORMAL;
  80. protected $f_queue = array(); // event queue for EVENT_QUEUE mode
  81. /**
  82. * the current state of the object
  83. * @var string
  84. */
  85. protected $f_state;
  86. /**
  87. * Transitions holds the transitions table
  88. * state1
  89. * event1
  90. * result1
  91. * state_name|fsm_result
  92. * event2
  93. * ...
  94. * ..
  95. * ..
  96. * @var array
  97. */
  98. protected $f_transitions = null;
  99. /**
  100. * constructor initializes the FSM to the first
  101. * state in the transitions table
  102. * @return void
  103. */
  104. public function __construct()
  105. {
  106. $this->_check_transitions();
  107. reset($this->f_transitions);
  108. $x = each($this->f_transitions);
  109. $x = $x[0];
  110. $this->f_state = $x;
  111. }
  112. /**
  113. * make sure a transitions graph has been defined
  114. * @return void
  115. */
  116. private function _check_transitions()
  117. {
  118. if (!isset($this->f_transitions))
  119. throw new Exception('No FSM processing is allowed without a transitions table\n');
  120. }
  121. /**
  122. * getter for f_state
  123. * @return string
  124. */
  125. public function get_state()
  126. {
  127. return $this->f_state;
  128. }
  129. /**
  130. * return the list of events accepted in the current state
  131. * @return array
  132. */
  133. public function get_accepted_events()
  134. {
  135. $this->_check_transitions();
  136. try
  137. {
  138. $events = array_keys($this->f_transitions[$this->f_state]);
  139. // echo func_name() . ": state $this->f_state, accepted events are:\n" . print_r($events, true). "\n";
  140. }
  141. catch (Exception $e)
  142. {
  143. echo "Exception in get_accepted_events" . print_r($e);
  144. print_r(debug_backtrace());
  145. $events = array();
  146. }
  147. return $events;
  148. }
  149. /**
  150. * return the list of outcome accepted in the current state for the give event
  151. * @param string $event_name
  152. * @param mixed $outcome
  153. * @return array
  154. */
  155. public function get_accepted_outcomes($event_name)
  156. {
  157. // echo func_name() . "\n";
  158. $this->_check_transitions();
  159. /**
  160. * Spare some paranioa
  161. *
  162. if (!$this->is_event_allowed($event_name))
  163. throw new Exception(func_name() . ": event \"$event_name\" not allowed in state \"$this->f_state\"\n");
  164. */
  165. $outcomes = array_keys($this->f_transitions[$this->f_state][$event_name]);
  166. // print_r($this->f_transitions[$this->f_state][$event_name]);
  167. // echo "outcomes for event $event_name: " . var_dump($outcomes) . "\n";
  168. return $outcomes;
  169. }
  170. /**
  171. * is this event accepted in the current state
  172. * the FSM is in ?
  173. *
  174. * @param string $event_name
  175. * @return boolean
  176. */
  177. public function is_event_allowed($event_name)
  178. {
  179. // echo func_name() . "($event_name)";
  180. $this->_check_transitions();
  181. $ret = in_array($event_name, $this->get_accepted_events());
  182. // echo " in state $this->f_state, result = <$ret>\n";
  183. return $ret;
  184. }
  185. /**
  186. * is a given outcome available for a given event,
  187. * considering the current context ?
  188. *
  189. * @param string $event_name
  190. * @param mixed $outcome
  191. * @return boolean
  192. */
  193. public function is_outcome_allowed($event_name, $outcome)
  194. {
  195. $this->_check_transitions();
  196. if (!$this->is_event_allowed($event_name))
  197. return false;
  198. $ret = array_key_exists($outcome, $this->get_accepted_outcomes($event_name));
  199. return $ret;
  200. }
  201. /**
  202. * apply an event, and the resulting event chain if needed
  203. *
  204. * @param string $event_name
  205. * @param array $params the
  206. * @return fsm_result resulting state
  207. */
  208. public function apply_event($event_name)
  209. {
  210. // echo "Start of " . func_name() . "\n";
  211. do {
  212. $result = $this->apply_simple_event($event_name);
  213. if ($this->allow_actions)
  214. {
  215. $event_name = $result->fsm_action; // can be NULL
  216. }
  217. else
  218. {
  219. $event_name = NULL;
  220. }
  221. } while($event_name);
  222. // echo "End of " . func_name() . "\n";
  223. return $result;
  224. }
  225. /**
  226. * Helper for apply_event that does not implement the post-transition action
  227. *
  228. * @param string $event_name
  229. * @return fsm_result
  230. * @see apply_event()
  231. */
  232. private function apply_simple_event($event_name)
  233. {
  234. // echo "Start of " . func_name() . ", event = $event_name\n";
  235. $current_state = $this->f_state;
  236. if (($event_name == Finite_State_Machine::IDLE_EVENT) && !$this->idle_work)
  237. {
  238. return new fsm_result();
  239. }
  240. if (!$this->is_event_allowed($event_name))
  241. {
  242. die("Event $event_name not allowed in current state $current_state.\n");
  243. /* throw new Exception(func_name()
  244. . ": Event \"$event_name\" not accepted in current state \"$current_state\"");
  245. */
  246. }
  247. $outcomes = $this->get_accepted_outcomes($event_name);
  248. $method_name = "event$event_name";
  249. if (!method_exists($this, $method_name))
  250. {
  251. die (func_name() . ": missing method "
  252. . get_class($this) . "::$method_name. Aborting.\n");
  253. }
  254. $outcome = $this->$method_name();
  255. if (!in_array($outcome, $outcomes))
  256. {
  257. throw new Exception(func_name()
  258. . ": event guard. Transition on \"$event_name\" return invalid outcome: "
  259. . print_r($outcome, true)
  260. . " for state $this->f_state\n");
  261. }
  262. $transition = &$this->f_transitions[$current_state][$event_name][$outcome];
  263. $result = new fsm_result
  264. (
  265. $outcome,
  266. $transition[0],
  267. $transition[1]
  268. );
  269. if (isset($result->fsm_state))
  270. {
  271. $this->f_state = $result->fsm_state;
  272. }
  273. /* print_r($this->f_transitions[$current_state][$event_name]);
  274. var_dump($result); */
  275. if (!isset($outcome))
  276. $outcome = 'NULL';
  277. /*
  278. echo func_name()
  279. . ": $current_state: " . $event_name . '[' . $outcome . ']'
  280. . " -> $this->f_state / " . $result->fsm_action . PHP_EOL;
  281. */
  282. return $result;
  283. }
  284. /**
  285. * Default event
  286. * @return boolean
  287. */
  288. public function f_idle()
  289. {
  290. return TRUE;
  291. }
  292. /**
  293. * Apply an fsm::IDLE_EVENT event. Do not confuse with f_idle !
  294. *
  295. * @return fsm_result
  296. */
  297. public function idle()
  298. {
  299. return $this->apply_event(Finite_State_Machine::IDLE_EVENT);
  300. }
  301. /**
  302. * return the current operating mode of the FSM
  303. * @return int
  304. */
  305. public function get_event_mode()
  306. {
  307. return $this->f_event_mode;
  308. }
  309. /**
  310. * set the current operating mode for the FSM
  311. *
  312. * @param int $mode fsm::EVENT_* constants
  313. * @return int $mode fsm::EVENT_* constants
  314. */
  315. public function set_event_mode($mode)
  316. {
  317. switch ($mode)
  318. {
  319. case Finite_State_Machine::EVENT_NORMAL :
  320. if (count($this->f_queue) > 0)
  321. {
  322. while (($event = array_shift($this->f_queue)) !== NULL)
  323. {
  324. $this->apply_event($event);
  325. }
  326. }
  327. break;
  328. case Finite_State_Machine::EVENT_QUEUE : // nothing special to do
  329. break;
  330. case Finite_State_Machine::EVENT_SINK : // empty queue if needed
  331. if (count($this->f_queue) > 0)
  332. {
  333. $this->f_queue = array();
  334. }
  335. break;
  336. default:
  337. throw new Exception("Trying to set unknown FSM mode $mode");
  338. }
  339. $this->f_event_mode = $mode;
  340. return $this->f_event_mode;
  341. }
  342. /**
  343. * Load the f_transitions table from an external resource.
  344. *
  345. * @param string $url Optional: defaults to the name of the class, . ".xml"
  346. */
  347. public function load_fsm($url = NULL)
  348. {
  349. $osd = FALSE; // on screen display (debug)
  350. if ($osd)
  351. echo "Loading FSM from $url\n";
  352. if (!isset($url))
  353. {
  354. $url = get_class($this) . ".xml";
  355. }
  356. $fsm = simplexml_load_file($url);
  357. $fsm_version = (string) $fsm['fsm_version'];
  358. if ($fsm_version !== '1.3')
  359. {
  360. die("Revision $fsm_version of schema is not supported.\n");
  361. }
  362. $this->idle_work = ($fsm['idle_work'] == 1);
  363. $this->allow_actions = ($fsm['allow_actions'] == 1);
  364. $this->f_transitions = array();
  365. $t = &$this->f_transitions;
  366. // (string) casts in this loop are required: RHS is a SimpleXMLElement
  367. foreach ($fsm->state as $state)
  368. {
  369. $id = (string) $state['id'];
  370. if ($osd)
  371. echo "State $id :\n";
  372. $t[$id] = array();
  373. switch ($id)
  374. {
  375. case Finite_State_Machine::INIT_STATE :
  376. if ($osd)
  377. echo " Initial state\n";
  378. break;
  379. case Finite_State_Machine::FINAL_STATE :
  380. if ($osd)
  381. echo " Final state\n";
  382. break;
  383. }
  384. foreach ($state->event as $event)
  385. {
  386. $ename = (string) $event['name'];
  387. if ($osd)
  388. echo " Event $ename";
  389. if (!isset($event['type']))
  390. $event['type'] = 'void';
  391. $etype = (string) $event['type'];
  392. if ($osd)
  393. echo ", type $etype\n";
  394. foreach ($event as $next)
  395. {
  396. if ($event['type'] == 'void')
  397. {
  398. $next['result'] = 'always';
  399. $eresult = null;
  400. }
  401. else
  402. $eresult = (string) $next['result'];
  403. if (!isset($next['state']))
  404. $next['state'] = (string) $state['id'];
  405. if ($osd)
  406. {
  407. echo " Next(" . $next['result'] . ') = ' . $next['state'];
  408. if (isset($next['action']))
  409. echo " + event " . $next['action'];
  410. echo PHP_EOL;
  411. }
  412. $t[$id][$ename][$eresult] = array(
  413. (string) $next['state'],
  414. (string) $next['action']);
  415. }
  416. }
  417. }
  418. }
  419. }