[Summary view] [Print] [Text view]

   1  <?php
   2  /*
   3   * Limb PHP Framework
   4   *
   5   * @link http://limb-project.com 
   6   * @copyright  Copyright &copy; 2004-2007 BIT(http://bit-creative.com)
   7   * @license    LGPL http://www.gnu.org/copyleft/lesser.html 
   8   */
   9  
  10  /* vim: set expandtab softtabstop=4 tabstop=4 shiftwidth=4: */
  11  /*
  12   * Copyright (c) 2002-2006 Jon Parise <jon@php.net>
  13   *
  14   * Permission is hereby granted, free of charge, to any person obtaining a copy
  15   * of this software and associated documentation files (the "Software"), to
  16   * deal in the Software without restriction, including without limitation the
  17   * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  18   * sell copies of the Software, and to permit persons to whom the Software is
  19   * furnished to do so, subject to the following conditions:
  20   *
  21   * The above copyright notice and this permission notice shall be included in
  22   * all copies or substantial portions of the Software.
  23   *
  24   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  25   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  26   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  27   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  28   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  29   * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  30   * IN THE SOFTWARE.
  31   *
  32   * $Id: WactFSM.php 5945 2007-06-06 08:31:43Z pachanga $
  33   */
  34  
  35  /**
  36   * This class implements a Finite State Machine (FSM).
  37   *
  38   * In addition to maintaining state, this FSM also maintains a user-defined
  39   * payload, therefore effectively making the machine a Push-Down Automata
  40   * (a finite state machine with memory).
  41   *
  42   * This code is based on Noah Spurrier's Finite State Machine (FSM) submission
  43   * to the Python Cookbook:
  44   *
  45   *      http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/146262
  46   *
  47   * @author  Jon Parise <jon@php.net>
  48   * @version $Revision: 1.15 $
  49   * @package wact
  50   * @license http://www.opensource.org/licenses/mit-license.php MIT License
  51   *
  52   * @example rpn.php     A Reverse Polish Notation (RPN) calculator.
  53   */
  54  class WactFSM
  55  {
  56      /**
  57       * Represents the initial state of the machine.
  58       *
  59       * @var string
  60       * @see $_currentState
  61       * @access private
  62       */
  63      var $_initialState = '';
  64  
  65      /**
  66       * Contains the current state of the machine.
  67       *
  68       * @var string
  69       * @see $_initialState
  70       * @access private
  71       */
  72      var $_currentState = '';
  73  
  74      /**
  75       * Contains the payload that will be passed to each action function.
  76       *
  77       * @var mixed
  78       * @access private
  79       */
  80      var $_payload = null;
  81  
  82      /**
  83       * Maps (inputSymbol, currentState) --> (action, nextState).
  84       *
  85       * @var array
  86       * @see $_initialState, $_currentState
  87       * @access private
  88       */
  89      var $_transitions = array();
  90  
  91      /**
  92       * Maps (currentState) --> (action, nextState).
  93       *
  94       * @var array
  95       * @see $_inputState, $_currentState
  96       * @access private
  97       */
  98      var $_transitionsAny = array();
  99  
 100      /**
 101       * Contains the default transition that is used if no more appropriate
 102       * transition has been defined.
 103       *
 104       * @var array
 105       * @access private
 106       */
 107      var $_defaultTransition = null;
 108  
 109  
 110      /**
 111       * This method constructs a new Finite State Machine (FSM) object.
 112       *
 113       * In addition to defining the machine's initial state, a "payload" may
 114       * also be specified.  The payload represents a variable that will be
 115       * passed along to each of the action functions.  If the FSM is being used
 116       * for parsing, the payload is often a array that is used as a stack.
 117       *
 118       * @param   string  $initialState   The initial state of the FSM.
 119       * @param   mixed   $payload        A payload that will be passed to each
 120       *                                  action function.
 121       */
 122      function __construct($initialState, $payload)
 123      {
 124          $this->_initialState = $initialState;
 125          $this->_currentState = $initialState;
 126          $this->_payload = $payload;
 127      }
 128  
 129      /**
 130       * This method resets the FSM by setting the current state back to the
 131       * initial state (set by the constructor).
 132       */
 133      function reset()
 134      {
 135          $this->_currentState = $this->_initialState;
 136      }
 137  
 138      /**
 139       * This method adds a new transition that associates:
 140       *
 141       *      (symbol, currentState) --> (nextState, action)
 142       *
 143       * The action may be set to NULL, in which case the processing routine
 144       * will ignore the action and just set the next state.
 145       *
 146       * @param   string  $symbol         The input symbol.
 147       * @param   string  $state          This transition's starting state.
 148       * @param   string  $nextState      This transition's ending state.
 149       * @param   string  $action         The name of the function to invoke
 150       *                                  when this transition occurs.
 151       *
 152       * @see     addTransitions()
 153       */
 154      function addTransition($symbol, $state, $nextState, $action = null)
 155      {
 156          $this->_transitions["$symbol,$state"] = array($nextState, $action);
 157      }
 158  
 159      /**
 160       * This method adds the same transition for multiple different symbols.
 161       *
 162       * @param   array   $symbols        A list of input symbols.
 163       * @param   string  $state          This transition's starting state.
 164       * @param   string  $nextState      This transition's ending state.
 165       * @param   string  $action         The name of the function to invoke
 166       *                                  when this transition occurs.
 167       *
 168       * @see     addTransition()
 169       */
 170      function addTransitions($symbols, $state, $nextState, $action = null)
 171      {
 172          foreach ($symbols as $symbol) {
 173              $this->addTransition($symbol, $state, $nextState, $action);
 174          }
 175      }
 176  
 177      /**
 178       * This method adds an array of transitions.  Each transition is itself
 179       * defined as an array of values which will be passed to addTransition()
 180       * as parameters.
 181       *
 182       * @param   array   $transitions    An array of transitions.
 183       *
 184       * @see     addTransition
 185       * @see     addTransitions
 186       *
 187       * @since 1.2.4
 188       */
 189      function addTransitionsArray($transitions)
 190      {
 191          foreach ($transitions as $transition) {
 192              call_user_func_array(array($this, 'addTransition'), $transition);
 193          }
 194      }
 195  
 196      /**
 197       * This method adds a new transition that associates:
 198       *
 199       *      (currentState) --> (nextState, action)
 200       *
 201       * The processing routine checks these associations if it cannot first
 202       * find a match for (symbol, currentState).
 203       *
 204       * @param   string  $state          This transition's starting state.
 205       * @param   string  $nextState      This transition's ending state.
 206       * @param   string  $action         The name of the function to invoke
 207       *                                  when this transition occurs.
 208       *
 209       * @see     addTransition()
 210       */
 211      function addTransitionAny($state, $nextState, $action = null)
 212      {
 213          $this->_transitionsAny[$state] = array($nextState, $action);
 214      }
 215  
 216      /**
 217       * This method sets the default transition.  This defines an action and
 218       * next state that will be used if the processing routine cannot find a
 219       * suitable match in either transition list.  This is useful for catching
 220       * errors caused by undefined states.
 221       *
 222       * The default transition can be removed by setting $nextState to NULL.
 223       *
 224       * @param   string  $nextState      The transition's ending state.
 225       * @param   string  $action         The name of the function to invoke
 226       *                                  when this transition occurs.
 227       */
 228      function setDefaultTransition($nextState, $action)
 229      {
 230          if (is_null($nextState)) {
 231              $this->_defaultTransition = null;
 232              return;
 233          }
 234  
 235          $this->_defaultTransition = array($nextState, $action);
 236      }
 237  
 238      /**
 239       * This method returns (nextState, action) given an input symbol and
 240       * state.  The FSM is not modified in any way.  This method is rarely
 241       * called directly (generally only for informational purposes).
 242       *
 243       * If the transition cannot be found in either of the transitions lists,
 244       * the default transition will be returned.  Note that it is possible for
 245       * the default transition to be set to NULL.
 246       *
 247       * @param   string  $symbol         The input symbol.
 248       *
 249       * @return  mixed   Array representing (nextState, action), or NULL if the
 250       *                  transition could not be found and not default
 251       *                  transition has been defined.
 252       */
 253      function getTransition($symbol)
 254      {
 255          $state = $this->_currentState;
 256  
 257          if (!empty($this->_transitions["$symbol,$state"])) {
 258              return $this->_transitions["$symbol,$state"];
 259          } elseif (!empty($this->_transitionsAny[$state])) {
 260              return $this->_transitionsAny[$state];
 261          } else {
 262              return $this->_defaultTransition;
 263          }
 264      }
 265  
 266      /**
 267       * This method is the main processing routine.  It causes the FSM to
 268       * change states and execute actions.
 269       *
 270       * The transition is determined by calling getTransition() with the
 271       * provided symbol and the current state.  If no valid transition is found,
 272       * process() returns immediately.
 273       *
 274       * The action callback may return the name of a new state.  If one is
 275       * returned, the current state will be updated to the new value.
 276       *
 277       * If no action is defined for the transition, only the state will be
 278       * changed.
 279       *
 280       * @param   string  $symbol         The input symbol.
 281       *
 282       * @see     processList()
 283       */
 284      function process($symbol)
 285      {
 286          $transition = $this->getTransition($symbol);
 287  
 288          /* If a valid array wasn't returned, return immediately. */
 289          if (!is_array($transition) || (count($transition) != 2)) {
 290              return;
 291          }
 292  
 293          /* Update the current state to this transition's exit state. */
 294          $this->_currentState = $transition[0];
 295  
 296          /* If an action for this transition has been specified, execute it. */
 297          if (!empty($transition[1])) {
 298              $state = call_user_func_array($transition[1],
 299                                            array($symbol, $this->_payload));
 300  
 301              /* If a new state was returned, update the current state. */
 302              if (!empty($state) && is_string($state)) {
 303                  $this->_currentState = $state;
 304              }
 305          }
 306      }
 307  
 308      /**
 309       * This method processes a list of symbols.  Each symbol in the list is
 310       * sent to process().
 311       *
 312       * @param   array   $symbols        List of input symbols to process.
 313       */
 314      function processList($symbols)
 315      {
 316          foreach ($symbols as $symbol) {
 317              $this->process($symbol);
 318          }
 319      }
 320  }