php__phplib/Finite_State_Machine.php

<?php
/**
 * Finite state machine skeleton
 *
 * @copyright  (c) 2007 OSI
 * @author     Frédéric G. MARAND
 * @license    Licensed under the CeCILL 2.0
 * @version    CVS: $Id: Finite_State_Machine.php,v 1.7 2007-06-03 21:24:29 marand Exp $
 * @link       http://drupal.org/project/offload
 * @since      Not applicable yet
 * @package    fsm
 */

require_once('misc.php'); // for func_name()
error_reporting(E_ALL|E_STRICT);

/**
 * This class defines a possible outcome for a given FSM transition
 *
 */
class fsm_result
  {
  /**
   * The return value of the event handler
   * @var mixed
   */
  public $fsm_return;

  /**
   * The name of the state to which the FSM must change. If NULL, do not change
   * the current state.
   *
   * @var string
   */
  public $fsm_state;

  /**
   * The name of an event to be fired after the state change has been applied
   *
   * @var string
   */
  public $fsm_action;

  /**
   * @param string $state
   * @param string $action
   * @return void
   */
  public function __construct($return = NULL, $state = NULL, $action = NULL)
    {
    $this->fsm_return = $return;
    $this->fsm_state = $state;
    $this->fsm_action = $action;
    }
  }

/**
 * This class must be inherited by code implementing actual FSMs.
 *
 * Applications must create a fsm descendant in which they will:
 *
 *   - define the f_transitions table, usually in their constructor
 *   - invoke the parent constructor to set up the FSM from the transitions table
 *   - create "f_foo" functions for each "foo" event, except "idle", which is builtin.
 *
 * Applications may:
 *   - disable event processing by setting $this->event to one of the fsm::EVENT_* constants
 *   - disable post-event actions by setting $this->allows actions to false
 *   - disable the builtin idle event by setting $this->idle_work to false
 *   - query the current state by using $this->get_state()
 *   - send an idle event by using $this->idle()
 *   - submit any event (including idle) by using $this->apply_event($event_name)
 *
 */
abstract class Finite_State_Machine
  {
  const IDLE_EVENT   = 'idle'; // must not change name: method f_idle depends on it

  const INIT_STATE   = 'init';
  const FINAL_STATE  = 'final';

  const EVENT_NORMAL = 1; // processes events
  const EVENT_QUEUE  = 2; // queue events for later use
  const EVENT_SINK   = 3; // throw away events

  public $idle_work     = TRUE;
  public $allow_actions = TRUE;

  protected $f_event_mode = Finite_State_Machine::EVENT_NORMAL;
  protected $f_queue      = array(); // event queue for EVENT_QUEUE mode

  /**
   * the current state of the object
   * @var string
   */
  protected $f_state;

  /**
   * Transitions holds the transitions table
   * state1
   *   event1
   *     result1
   *     state_name|fsm_result
   *   event2
   *     ...
   *   ..
   * ..
   * @var array
   */
  protected $f_transitions = null;

  /**
   * constructor initializes the FSM to the first
   * state in the transitions table
   * @return void
   */
  public function __construct()
    {
    $this->_check_transitions();

    reset($this->f_transitions);
    $x = each($this->f_transitions);
    $x = $x[0];
    $this->f_state = $x;
    }

  /**
   * make sure a transitions graph has been defined
   * @return void
   */
  private function _check_transitions()
    {
    if (!isset($this->f_transitions))
      throw new Exception('No FSM processing is allowed without a transitions table\n');
    }

  /**
   * getter for f_state
   * @return string
   */
  public function get_state()
    {
    return $this->f_state;
    }

  /**
   * return the list of events accepted in the current state
   * @return array
   */
  public function get_accepted_events()
    {
    $this->_check_transitions();

    try
      {
      $events = array_keys($this->f_transitions[$this->f_state]);
      // echo func_name() . ": state $this->f_state, accepted events are:\n" . print_r($events, true). "\n";
      }
    catch (Exception $e)
      {
      echo "Exception in get_accepted_events" . print_r($e);
      print_r(debug_backtrace());
      $events = array();
      }

    return $events;
    }

  /**
   * return the list of outcome accepted in the current state for the give event
   * @param string $event_name
   * @param mixed $outcome
   * @return array
   */
  public function get_accepted_outcomes($event_name)
    {
    // echo func_name() . "\n";
    $this->_check_transitions();

    /**
     * Spare some paranioa
     *
    if (!$this->is_event_allowed($event_name))
      throw new Exception(func_name() . ": event \"$event_name\" not allowed in state \"$this->f_state\"\n");
     */

    $outcomes = array_keys($this->f_transitions[$this->f_state][$event_name]);
    // print_r($this->f_transitions[$this->f_state][$event_name]);
    // echo "outcomes for event $event_name: " . var_dump($outcomes) . "\n";
    return $outcomes;
    }

  /**
   * is this event accepted in the current state
   * the FSM is in ?
   *
   * @param string $event_name
   * @return boolean
   */
  public function is_event_allowed($event_name)
    {
    // echo func_name() . "($event_name)";
    $this->_check_transitions();

    $ret = in_array($event_name, $this->get_accepted_events());
    // echo " in state $this->f_state, result = <$ret>\n";
    return $ret;
    }

  /**
   * is a given outcome available for a given event,
   * considering the current context ?
   *
   * @param string $event_name
   * @param mixed $outcome
   * @return boolean
   */
  public function is_outcome_allowed($event_name, $outcome)
    {
    $this->_check_transitions();

    if (!$this->is_event_allowed($event_name))
      return false;

    $ret = array_key_exists($outcome, $this->get_accepted_outcomes($event_name));
    return $ret;
    }

  /**
   * apply an event, and the resulting event chain if needed
   *
   * @param string $event_name
   * @param array $params the
   * @return fsm_result resulting state
   */
  public function apply_event($event_name)
    {
    // echo "Start of " . func_name() . "\n";

    do {
      $result = $this->apply_simple_event($event_name);
      if ($this->allow_actions)
        {
        $event_name = $result->fsm_action; // can be NULL
        }
      else
        {
        $event_name = NULL;
        }
      } while($event_name);
    // echo "End of " . func_name() . "\n";
    return $result;
    }

  /**
   * Helper for apply_event that does not implement the post-transition action
   *
   * @param string $event_name
   * @return fsm_result
   * @see apply_event()
   */
  private function apply_simple_event($event_name)
    {
    // echo "Start of " . func_name() . ", event = $event_name\n";
    $current_state = $this->f_state;
    if (($event_name == Finite_State_Machine::IDLE_EVENT) && !$this->idle_work)
      {
      return new fsm_result();
      }

    if (!$this->is_event_allowed($event_name))
      {
      die("Event $event_name not allowed in current state $current_state.\n");
      /* throw new Exception(func_name()
        . ":  Event \"$event_name\" not accepted in current state \"$current_state\"");
      */
      }

    $outcomes = $this->get_accepted_outcomes($event_name);

    $method_name = "event$event_name";
    if (!method_exists($this, $method_name))
      {
      die (func_name() . ": missing method "
        . get_class($this) . "::$method_name. Aborting.\n");
      }
    $outcome = $this->$method_name();

    if (!in_array($outcome, $outcomes))
      {
      throw new Exception(func_name()
        . ": event guard. Transition on \"$event_name\" return invalid outcome: "
        . print_r($outcome, true)
        . " for state $this->f_state\n");
      }

    $transition = &$this->f_transitions[$current_state][$event_name][$outcome];
    $result = new fsm_result
      (
      $outcome,
      $transition[0],
      $transition[1]
      );
    if (isset($result->fsm_state))
      {
      $this->f_state = $result->fsm_state;
      }
    /* print_r($this->f_transitions[$current_state][$event_name]);
    var_dump($result); */
    if (!isset($outcome))
      $outcome = 'NULL';
    /*
    echo func_name()
      . ": $current_state: " . $event_name . '[' . $outcome . ']'
      . " -> $this->f_state / " . $result->fsm_action . PHP_EOL;
    */
    return $result;
    }

  /**
   * Default event
   * @return boolean
   */
  public function f_idle()
    {
    return TRUE;
    }

  /**
   * Apply an fsm::IDLE_EVENT event. Do not confuse with f_idle !
   *
   * @return fsm_result
   */
  public function idle()
    {
    return $this->apply_event(Finite_State_Machine::IDLE_EVENT);
    }

  /**
   * return the current operating mode of the FSM
   * @return int
   */
  public function get_event_mode()
    {
    return $this->f_event_mode;
    }

  /**
   * set the current operating mode for the FSM
   *
   * @param int $mode fsm::EVENT_* constants
   * @return int $mode fsm::EVENT_* constants
   */
  public function set_event_mode($mode)
    {
    switch ($mode)
      {
      case Finite_State_Machine::EVENT_NORMAL :
        if (count($this->f_queue) > 0)
          {
          while (($event = array_shift($this->f_queue)) !== NULL)
            {
            $this->apply_event($event);
            }
          }
        break;
      case Finite_State_Machine::EVENT_QUEUE  : // nothing special to do
        break;
      case Finite_State_Machine::EVENT_SINK : // empty queue if needed
        if (count($this->f_queue) > 0)
          {
          $this->f_queue = array();
          }
        break;
      default:
        throw new Exception("Trying to set unknown FSM mode $mode");
      }
    $this->f_event_mode = $mode;
    return $this->f_event_mode;
    }

  /**
   * Load the f_transitions table from an external resource.
   *
   * @param string $url Optional: defaults to the name of the class, . ".xml"
   */
  public function load_fsm($url = NULL)
    {
    $osd = FALSE; // on screen display (debug)
    if ($osd)
      echo "Loading FSM from $url\n";

    if (!isset($url))
      {
      $url = get_class($this) . ".xml";
      }

    $fsm = simplexml_load_file($url);
    $fsm_version = (string) $fsm['fsm_version'];
    if ($fsm_version !== '1.3')
      {
      die("Revision $fsm_version of schema is not supported.\n");
      }

    $this->idle_work     = ($fsm['idle_work']     == 1);
    $this->allow_actions = ($fsm['allow_actions'] == 1);

    $this->f_transitions = array();
    $t = &$this->f_transitions;

    // (string) casts in this loop are required: RHS is a SimpleXMLElement
    foreach ($fsm->state as $state)
      {
      $id = (string) $state['id'];
      if ($osd)
        echo "State $id :\n";
      $t[$id] = array();
      switch ($id)
        {
        case Finite_State_Machine::INIT_STATE :
          if ($osd)
            echo "  Initial state\n";
          break;
        case Finite_State_Machine::FINAL_STATE :
          if ($osd)
            echo "  Final state\n";
          break;
        }
      foreach ($state->event as $event)
        {
        $ename = (string) $event['name'];
        if ($osd)
          echo "  Event $ename";

        if (!isset($event['type']))
          $event['type'] = 'void';
        $etype = (string) $event['type'];
        if ($osd)
          echo ", type $etype\n";

        foreach ($event as $next)
          {
          if ($event['type'] == 'void')
            {
            $next['result'] = 'always';
            $eresult = null;
            }
          else
            $eresult = (string) $next['result'];

          if (!isset($next['state']))
            $next['state'] = (string) $state['id'];
          if ($osd)
            {
            echo "    Next(" . $next['result'] . ') = ' . $next['state'];
            if (isset($next['action']))
              echo " + event " . $next['action'];
            echo PHP_EOL;
            }
          $t[$id][$ename][$eresult] = array(
            (string) $next['state'],
            (string) $next['action']);
          }
        }
      }
    }
  }