pli/pattern/state/fsm.py

   1 #=======================================================================
   2
   3 __version__ = '''0.3.19'''
   4 __sub_version__ = '''20041118120308'''
   5 __copyright__ = '''(c) Alex A. Naanou 2003'''
   6
   7
   8 #-----------------------------------------------------------------------
   9
  10 __doc__ = '''\
  11 This module defines a Finite State Machine framework.
  12 '''
  13
  14
  15 #-----------------------------------------------------------------------
  16
  17 import pli.pattern.store.stored as stored
  18 import pli.event as event
  19 ##import pli.event.instanceevent as instanceevent
  20
  21 import state
  22
  23
  24 #-----------------------------------------------------------------------
  25 #---------------------------------------------FiniteStateMachineError---
  26 # TODO write more docs...
  27 class FiniteStateMachineError(Exception):
  28         '''
  29         '''
  30
  31
  32 #----------------------------------------------FiniteStateMachineStop---
  33 class FiniteStateMachineStop(Exception):
  34         '''
  35         '''
  36
  37
  38 #-----------------------------------------------------TransitionError---
  39 # TODO write more docs...
  40 class TransitionError(FiniteStateMachineError):
  41         '''
  42         '''
  43
  44
  45
  46 #-----------------------------------------------------------------------
  47 # TODO consistency checks...
  48 # TODO more thorough documentation...
  49 #-----------------------------------------------------------------------
  50 # predicates based on transitions:
  51 #-----------------------------------------------------------isinitial---
  52 def isinitial(s):
  53         '''
  54         return True is s is the initial state of an FSM.
  55         '''
  56         return hasattr(s, '__is_initial_state__') and s.__is_initial_state__
  57
  58
  59 #----------------------------------------------------------isterminal---
  60 def isterminal(s):
  61         '''
  62         return True is s is a terminal state in an FSM.
  63         '''
  64         return hasattr(s, '__is_terminal_state__') and s.__is_terminal_state__
  65
  66
  67 #--------------------------------------------------------------isnext---
  68 def isnext(s1, s2):
  69         '''
  70         return True if there is a direct transition from s1 to s2.
  71         '''
  72         return s2 in s1.iternextstates()
  73
  74
  75 #--------------------------------------------------------------isprev---
  76 def isprev(s1, s2):
  77         '''
  78         return True if there is a direct transition from s2 to s1.
  79         '''
  80         return isnext(s2, s1)
  81
  82
  83 #------------------------------------------------------------isbefore---
  84 # TODO make an iterative version...
  85 # TODO might be good to make a breadth-first version...
  86 def isbefore(s1, s2, exclude=None):
  87         '''
  88         return True if s2 is reachable from s1.
  89         '''
  90         if exclude == None:
  91                 exclude = []
  92         # this is depth first...
  93         for n in [s1] + list(s1.iternextstates()):
  94                 if n not in exclude and (isnext(n, s2) or isbefore(n, s2, exclude=exclude+[n])):
  95                         return True
  96         return False
  97
  98
  99 #-------------------------------------------------------------isafter---
 100 def isafter(s1, s2):
 101         '''
 102         return True if s1 is reachable from s2.
 103         '''
 104         return isbefore(s2, s1)
 105
 106
 107 #-----------------------------------------------------------isbetween---
 108 def isbetween(s1, s2, s3):
 109         '''
 110         return True if s1 is reachable from s2 and s3 is reachable from s1 (e.g. s1 is between s2 and s3).
 111         '''
 112         return isbefore(s2, s1) and isbefore(s1, s3)
 113
 114
 115 #------------------------------------------------------------isonpath---
 116 def isonpath(s1, s2, s3, *p):
 117         '''
 118         return True if s2 is reachable from s1 and s3 from s2 ... sN from sN-1.
 119         '''
 120         r = (s1, s2, s3) + p
 121         for i, n in enumerate(p[1:-1]):
 122                 if not isbetween(n, p[i], p[i+2]):
 123                         return False
 124         return True
 125
 126
 127 #------------------------------------------------------------isinloop---
 128 def isinloop(s):
 129         '''
 130         return true if s is inside a loop (e.g. s is reachable from s)
 131         '''
 132         return isbefore(s, s)
 133
 134
 135
 136 #----------------------------------------------------------transition---
 137 # TODO add support for string state names... (+ check consistency... (?))
 138 # TODO add doc paramiter to transitions...
 139 def transition(s1, s2, condition=None):
 140         '''
 141         create a transition from s1 to s2.
 142         '''
 143         if not isterminal(s1):
 144                 s1.transition(s2, condition)
 145         else:
 146                 raise FiniteStateMachineError, 'can\'t add transition to a terminal state %s.' % s1
 147
 148
 149 #-----------------------------------------------------------------------
 150 #--------------------------------------------------------onEnterState---
 151 # TODO write more docs...
 152 class onEnterState(event.InstanceEvent):
 153         '''
 154         '''
 155         __suppress_exceptions__ = False
 156
 157         def __init__(self, state_name):
 158                 '''
 159                 '''
 160                 self.state_name = state_name
 161                 super(onEnterState, self).__init__()
 162
 163
 164 #---------------------------------------------------------onExitState---
 165 # TODO write more docs...
 166 class onExitState(event.InstanceEvent):
 167         '''
 168         '''
 169         __suppress_exceptions__ = False
 170
 171         def __init__(self, state_name):
 172                 '''
 173                 '''
 174                 self.state_name = state_name
 175                 super(onExitState, self).__init__()
 176
 177
 178 #--------------------------------------------onFiniteStateMachineStop---
 179 class onFiniteStateMachineStop(event.InstanceEvent):
 180         '''
 181         '''
 182         __suppress_exceptions__ = False
 183
 184         def __init__(self, state_name=None, fsm=None):
 185                 '''
 186                 '''
 187                 self.state_name = state_name
 188                 # XXX this is a cyclic reference....
 189                 if fsm != None:
 190                         self.fsm= fsm
 191                 super(onFiniteStateMachineStop, self).__init__()
 192
 193
 194 #--------------------------------------------------FiniteStateMachine---
 195 # WARNING: this has not been tested for being thread-safe...
 196 # NOTE: whole FSMs can not (yet) be reproduced by deep copying... (not
 197 #       tested)
 198 # TODO test for safety of parallel execution of two fsm instances...
 199 # TODO write more docs...
 200 # TODO error state handler...
 201 # TODO "Sub-FSMs"
 202 #
 203 # TODO name resolution through the fsm.... (as a default to the startup
 204 #      state...)
 205 #      this should look like the FSM subclass is mixed-in (or a
 206 #      superclass of every state) to the originil FSM, yet not touching
 207 #      the original...
 208 #
 209 class FiniteStateMachine(state.State):
 210         '''
 211         this is the base FSM class.
 212
 213         this acts as a collection of states.
 214
 215         if an initial state is defined for an FSM the instance of
 216         FiniteStateMachine will change state to the initial
 217         state on init.
 218         '''
 219         # class configuration:
 220         # these will define the state enter/exit event constructors..
 221         __state_enter_event__ = onEnterState
 222         __state_exit_event__ = onExitState
 223         # if this is set, all state changes without transitions will be
 224         # blocked (e.g. raise an exception)...
 225         __strict_transitions__ = True
 226         # this will enable automatic state changing...
 227         __auto_change_state__ = True
 228         # this will define the state to which we will auto-change...
 229         __next_state__ = None
 230
 231         # class data:
 232         __states__ = None
 233         __initial_state__ = None
 234         _stop_exception = None
 235         _stop_reason = None
 236
 237         # this is the super safe version of init.... (incase w mix the
 238         # incompatible classes....)
 239         def __init__(self, *p, **n):
 240                 '''
 241                 '''
 242                 # super-safe...
 243                 super(FiniteStateMachine, self).__init__(*p, **n)
 244                 # init all states...
 245                 self.initstates()
 246                 # store a ref to the original startup class....
 247                 # NOTE: this is an instance attribute! (might pose a problem on
 248                 #       serializatio....)
 249                 self.__startup_class__ = self.__class__
 250                 # change state to the initial state if one defined...
 251                 if hasattr(self, '__initial_state__') and self.__initial_state__ != None:
 252                         self.changestate(self.__initial_state__)
 253                 # create a general fsm stop event...
 254                 self.onFiniteStateMachineStop = onFiniteStateMachineStop(fsm=self)
 255         def start(self):
 256                 '''
 257                 this is the FSM main loop.
 258                 '''
 259 ##              # sanity checks...
 260 ##              if not hasattr(self, '__fsm__'):
 261 ##                      raise FiniteStateMachineError, 'can\'t start a raw FSM object (change to a valid state).'
 262                 # start the loop...
 263                 if hasattr(self, '__auto_change_state__') and self.__auto_change_state__:
 264                         if hasattr(self, '_running') and not self._running:
 265                                 raise FiniteStateMachineError, 'the %s FSM is already running.' % self
 266                         self._running = True
 267                         try:
 268                                 while True:
 269                                         # break on terminal state...
 270                                         if isterminal(self):
 271                                                 # fire the state stop event...
 272                                                 evt_name = 'onStop' + self.__class__.__name__
 273                                                 if hasattr(self, evt_name):
 274                                                         getattr(self, evt_name).fire()
 275                                                 # exit...
 276                                                 break
 277 ##                                      # handle stops...
 278 ##                                      if self._running == False:
 279 ##                                              if self._stop_exception != None:
 280 ##                                                      raise self._stop_exception, self._stop_reason
 281 ##                                              return self._stop_reason
 282                                         if self.__next_state__ != None:
 283                                                 # change state...
 284                                                 tostate = self.__next_state__
 285                                                 self.__next_state__ = None
 286                                                 self._changestate(tostate)
 287                         except FiniteStateMachineStop:
 288                                 pass
 289                         self._running = False
 290                         # fire the fsm stop event...
 291                         self.onFiniteStateMachineStop.fire()
 292                 else:
 293                         raise FiniteStateMachineError, 'can\'t start a manual (non-auto-change-state) FSM.'
 294 ##      def stop(self, reason=None, exception=None):
 295 ##              '''
 296 ##              '''
 297 ##              self._stop_exception = exception
 298 ##              self._stop_reason = reason
 299 ##              self._running = False
 300         # TODO automaticly init newly added states per FSM object on their
 301         #      (event) addition to the FSM class...
 302         #      ...or do a lazy init (as in RPG.action)
 303         #      actually the best thing would be to do both...
 304         def initstates(self):
 305                 '''
 306                 this will init state event.
 307
 308                 NOTE: it is safe to run this more than once (though this might not be very fast).
 309                 '''
 310                 # init all states...
 311                 for state in self.__states__.values():
 312                         state_name = state.__name__
 313                         for evt_name, evt_cls in (('onEnter' + state_name, self.__state_enter_event__),
 314                                                                           ('onExit' + state_name, self.__state_exit_event__)):
 315                                 if not hasattr(self, evt_name):
 316                                         setattr(self, evt_name, evt_cls(state_name))
 317                         # the stop event...
 318                         if isterminal(state):
 319                                 setattr(self, 'onStop' + state_name, onFiniteStateMachineStop(state_name))
 320         def changestate(self, tostate):
 321                 '''
 322                 '''
 323                 if hasattr(self, '__auto_change_state__') and self.__auto_change_state__:
 324                         self.__next_state__ = tostate
 325                 else:
 326                         self._changestate(tostate)
 327         def _changestate(self, tostate):
 328                 '''
 329                 '''
 330                 # call the __onexitstate__...
 331                 if hasattr(self, '__onexitstate__'):
 332                         self.__onexitstate__()
 333                 # fire the exit event...
 334                 evt_name = 'onExit' + self.__class__.__name__
 335                 if hasattr(self, evt_name):
 336                         getattr(self, evt_name).fire()
 337                 # change the state...
 338                 super(FiniteStateMachine, self).changestate(tostate)
 339                 # fire the enter event...
 340                 evt_name = 'onEnter' + self.__class__.__name__
 341                 if hasattr(self, evt_name):
 342                         getattr(self, evt_name).fire()
 343                 # run the post init method...
 344                 if hasattr(self, '__onafterstatechange__'):
 345                         self.__onafterstatechange__()
 346                 if hasattr(self, '__onenterstate__'):
 347                         self.__onenterstate__()
 348
 349
 350 #--------------------------------------------------------------_State---
 351 class _StoredState(stored._StoredClass):
 352         '''
 353         this meta-class will register the state classes with the FSM.
 354         '''
 355         # _StoredClass configuration:
 356         __class_store_attr_name__ = '__fsm__'
 357
 358         def storeclass(cls, name, state):
 359                 '''
 360                 register the state with the FSM.
 361                 '''
 362                 fsm = getattr(cls, cls.__class_store_attr_name__)
 363                 # check state name...
 364                 if hasattr(fsm, name):
 365                         raise NameError, 'state named "%s" already exists.' % name
 366                 # register the state...
 367                 if fsm.__states__ == None:
 368                         fsm.__states__ = {name: state}
 369                 else:
 370                         fsm.__states__[name] = state
 371                 # set the fsm initial state...
 372                 if hasattr(state, '__is_initial_state__') and state.__is_initial_state__:
 373                         if hasattr(fsm, '__initial_state__') and fsm.__initial_state__ != None:
 374                                 raise FiniteStateMachineError, 'an initial state is already defined for the %s FSM.' % fsm
 375                         fsm.__initial_state__ = state
 376
 377
 378 #---------------------------------------------------------------State---
 379 # TODO write more docs...
 380 # TODO add doc paramiter to transitions...
 381 # TODO error state handler...
 382 # TODO "Sub-FSMs"
 383 # TODO revise magic method names and function...
 384 class State(FiniteStateMachine):
 385         '''
 386         this is the base state class for the FSM framwork.
 387
 388         there are three utility methods that can be defined:
 389                 __runonce__                     : this will be run only once per state, this is
 390                                                           done mainly to register callbacks.
 391                 __onstatechange__       : this is run once per state change, right after
 392                                                           the change is made and just before the onEnter
 393                                                           event is fired.
 394                 __onafterstatechange__
 395                                                         : this is called after the state is finalized.
 396                                                           that is, just after the state onEnter event
 397                                                           processing is done.
 398                                                           NOTE: by default, this will select the first
 399                                                                         usable transition and use it to change
 400                                                                         state.
 401                 __onenterstate__        : this is called once per state change, just after
 402                                                           the onEnter event is fired.
 403                                                           NOTE: this is fired after the __onafterstatechange__
 404                                                                 method, and does NOTHING by default.
 405                 __onexitstate__         : this is called once per state change, just before
 406                                                           the change and before the onExit event is fired.
 407                 __resolvestatechange__
 408                                                         : this is called by the above method if no usable
 409                                                           transition was found and current state is not
 410                                                           terminal.
 411                 NOTE: all of the above methods receive no arguments but the object
 412                           reference (e.g. self).
 413
 414         on state instance creation, two events will get defined and added to the FSM:
 415                 onEnter<state-name> : this is fired on state change, just after the
 416                                                           __onstatechange__ method is finished.
 417                 onExit<state-name>      : this is fired just before the state is changed,
 418                                                           just after the __onexitstate__ is done.
 419
 420         for more information see: pli.pattern.state.State
 421
 422         '''
 423         __metaclass__ = _StoredState
 424
 425         # class configuration:
 426         # this is the class of fsm this state will belong to
 427         __fsm__ = None
 428         # if this is set the state will be registered as initial/start state
 429         __is_initial_state__ = False
 430         # if this is set the state will be registered as terminal/end state
 431         __is_terminal_state__ = False
 432
 433 ##      ##!!! not yet implemmented section....
 434 ##      # Error Handling setop options:
 435 ##      # this will enable/disable the error case exit mechanism...
 436 ##      __error_exit_enabled__ = False
 437 ##      # if this is set, the value will be used a an error case exit from
 438 ##      # this state...
 439 ##      __error_state__ = None
 440 ##      # if this is true, this state will be used as the default error
 441 ##      # exit for the fsm...
 442 ##      # NOTE: there may be only one default error exit.
 443 ##      __is_default_error_state__ = False
 444
 445         # StoredClass options:
 446         # do not register this class... (not inherited)
 447         __ignore_registration__ = True
 448         # auto register  all subclasses (inherited)
 449         __auto_register_type__ = True
 450
 451         # class data:
 452         _transitions = None
 453
 454         # TODO add support for string state names... (+ check consistency... (?))
 455         # TODO write a "removetransition" method....
 456         def transition(cls, tostate, condition=None):
 457                 '''
 458                 this will create a transition from the current state to the tostate.
 459                 '''
 460                 transitions = cls._transitions
 461                 if transitions == None:
 462                         transitions = cls._transitions = {tostate: condition}
 463 ##              elif tostate in transitions:
 464 ##                      raise TransitionError, 'a transition from %s to %s already exists.' % (cls, tostate)
 465                 else:
 466                         cls._transitions[tostate] = condition
 467         transition = classmethod(transition)
 468         def changestate(self, tostate):
 469                 '''
 470                 change the object stete
 471                 '''
 472                 # prevent moving out of a terminal state...
 473                 if hasattr(self, '__is_terminal_state__') and self.__is_terminal_state__:
 474                         raise FiniteStateMachineError, 'can\'t change state of a terminal FSM node %s.' % self
 475                 fsm = self.__fsm__
 476                 # check for transitions...
 477                 if hasattr(fsm, '__strict_transitions__') and fsm.__strict_transitions__ and \
 478                                 (not hasattr(self, '_transitions') or self._transitions == None or \
 479                                 tostate not in self._transitions):
 480                         raise TransitionError, 'can\'t change state of %s to state %s without a transition.' % (self, tostate)
 481                 # check condition...
 482                 transitions = self._transitions
 483                 if transitions[tostate] != None and not transitions[tostate](self):
 484                         raise TransitionError, 'conditional transition from %s to state %s failed.' % (self, tostate)
 485                 super(State, self).changestate(tostate)
 486         def iternextstates(self):
 487                 '''
 488                 this will iterate through the states directly reachable from
 489                 self (e.g. to which there are direct transitions).
 490                 '''
 491                 if self._transitions == None:
 492                         return
 493                 for n in self._transitions:
 494                         yield n
 495         iternextstates = classmethod(iternextstates)
 496         # this method is called after the state is finalized (e.g. after the
 497         # __onstatechange__ is called and the onEnter event is processed).
 498         def __onafterstatechange__(self):
 499                 '''
 500                 this will try to next change state.
 501                 '''
 502                 if hasattr(self, '__auto_change_state__') and self.__auto_change_state__:
 503                         if self._transitions != None:
 504                                 for tostate in self._transitions:
 505                                         try:
 506                                                 self.changestate(tostate)
 507                                                 return
 508                                         except:
 509                                                 ##!!!
 510                                                 pass
 511                         if not hasattr(self, '__is_terminal_state__') or not self.__is_terminal_state__:
 512                                 if hasattr(self, '__resolvestatechange__'):
 513                                         # try to save the day and call the resolve method...
 514                                         return self.__resolvestatechange__()
 515                                 raise FiniteStateMachineError, 'can\'t exit a non-terminal state %s.' % self
 516         # this is here for documentation...
 517 ##      def __resolvestatechange__(self):
 518 ##              '''
 519 ##              this is called if no transition from current state is found, to
 520 ##              resolve the situation.
 521 ##              '''
 522 ##              pass
 523         # Q: does this need to be __gatattr__ or __getattribute__ ????
 524         # NOTE: this might make the attr access quite slow...
 525         # Q: is there a faster way??? (via MRO manipulation or something...)
 526         def __getattr__(self, name):
 527                 '''
 528                 this will proxy the attr access to the original startup class....
 529                 '''
 530                 ##!!! check for looping searching !!!##
 531                 # get the name in the startup class...
 532                 try:
 533                         return getattr(self.__startup_class__, name)
 534                 except AttributeError:
 535                         raise AttributeError, '%s object has no attribute "%s"' % (self, name)
 536
 537
 538 #--------------------------------------------------------InitialState---
 539 class InitialState(State):
 540         '''
 541         '''
 542         __is_initial_state__ = True
 543         __ignore_registration__ = True
 544
 545
 546 #-------------------------------------------------------TerminalState---
 547 class TerminalState(State):
 548         '''
 549         '''
 550         __is_terminal_state__ = True
 551         __ignore_registration__ = True
 552
 553
 554
 555 #=======================================================================
 556 #                                            vim:set ts=4 sw=4 nowrap :