pli/pattern/state/fsm.py

   1 #=======================================================================
   2
   3 __version__ = '''0.3.22'''
   4 __sub_version__ = '''20041121151606'''
   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 # TODO add transition mode: manual/automatic
 140 # modes:
 141 AUTO = 0
 142 MANUAL = 1
 143
 144 def transition(s1, s2, condition=None, mode=AUTO):
 145         '''
 146         create a transition from s1 to s2.
 147         '''
 148         if not isterminal(s1):
 149                 s1.transition(s2, condition, mode)
 150         else:
 151                 raise FiniteStateMachineError, 'can\'t add transition to a terminal state %s.' % s1
 152
 153
 154 #-----------------------------------------------------------------------
 155 #--------------------------------------------------------onEnterState---
 156 # TODO write more docs...
 157 class onEnterState(event.InstanceEvent):
 158         '''
 159         '''
 160         __suppress_exceptions__ = False
 161
 162         def __init__(self, state_name):
 163                 '''
 164                 '''
 165                 self.state_name = state_name
 166                 super(onEnterState, self).__init__()
 167
 168
 169 #---------------------------------------------------------onExitState---
 170 # TODO write more docs...
 171 class onExitState(event.InstanceEvent):
 172         '''
 173         '''
 174         __suppress_exceptions__ = False
 175
 176         def __init__(self, state_name):
 177                 '''
 178                 '''
 179                 self.state_name = state_name
 180                 super(onExitState, self).__init__()
 181
 182
 183 #--------------------------------------------onFiniteStateMachineStop---
 184 class onFiniteStateMachineStop(event.InstanceEvent):
 185         '''
 186         '''
 187         __suppress_exceptions__ = False
 188
 189         def __init__(self, state_name=None, fsm=None):
 190                 '''
 191                 '''
 192                 self.state_name = state_name
 193                 # XXX this is a cyclic reference....
 194                 if fsm != None:
 195                         self.fsm= fsm
 196                 super(onFiniteStateMachineStop, self).__init__()
 197
 198
 199 #--------------------------------------------------FiniteStateMachine---
 200 # WARNING: this has not been tested for being thread-safe...
 201 # NOTE: whole FSMs can not (yet) be reproduced by deep copying... (not
 202 #       tested)
 203 # TODO test for safety of parallel execution of two fsm instances...
 204 # TODO write more docs...
 205 # TODO error state handler...
 206 # TODO "Sub-FSMs"
 207 #
 208 # TODO name resolution through the fsm.... (as a default to the startup
 209 #      state...)
 210 #      this should look like the FSM subclass is mixed-in (or a
 211 #      superclass of every state) to the originil FSM, yet not touching
 212 #      the original...
 213 #
 214 class FiniteStateMachine(state.State):
 215         '''
 216         this is the base FSM class.
 217
 218         this acts as a collection of states.
 219
 220         if an initial state is defined for an FSM the instance of
 221         FiniteStateMachine will change state to the initial
 222         state on init.
 223         '''
 224         # class configuration:
 225         # these will define the state enter/exit event constructors..
 226         __state_enter_event__ = onEnterState
 227         __state_exit_event__ = onExitState
 228         # if this is set, all state changes without transitions will be
 229         # blocked (e.g. raise an exception)...
 230         __strict_transitions__ = True
 231         # this will enable automatic state changing...
 232         __auto_change_state__ = True
 233         # this will define the state to which we will auto-change...
 234         __next_state__ = None
 235
 236         # class data:
 237         __states__ = None
 238         __initial_state__ = None
 239         _stop_exception = None
 240         _stop_reason = None
 241
 242         # this is the super safe version of init.... (incase w mix the
 243         # incompatible classes....)
 244         def __init__(self, *p, **n):
 245                 '''
 246                 '''
 247                 # super-safe...
 248                 super(FiniteStateMachine, self).__init__(*p, **n)
 249                 # init all states...
 250                 self.initstates()
 251                 # store a ref to the original startup class....
 252                 # NOTE: this is an instance attribute! (might pose a problem on
 253                 #       serializatio....)
 254                 self.__startup_class__ = self.__class__
 255                 # change state to the initial state if one defined...
 256                 if hasattr(self, '__initial_state__') and self.__initial_state__ != None:
 257                         self.changestate(self.__initial_state__)
 258                 # create a general fsm stop event...
 259                 self.onFiniteStateMachineStop = onFiniteStateMachineStop(fsm=self)
 260         def start(self):
 261                 '''
 262                 this is the FSM main loop.
 263                 '''
 264 ##              # sanity checks...
 265 ##              if not hasattr(self, '__fsm__'):
 266 ##                      raise FiniteStateMachineError, 'can\'t start a raw FSM object (change to a valid state).'
 267                 # start the loop...
 268                 if hasattr(self, '__auto_change_state__') and self.__auto_change_state__:
 269                         if hasattr(self, '_running') and self._running:
 270                                 raise FiniteStateMachineError, 'the %s FSM is already running.' % self
 271                         self._running = True
 272                         try:
 273                                 while True:
 274                                         # break on terminal state...
 275                                         if isterminal(self):
 276                                                 # fire the state stop event...
 277                                                 evt_name = 'onStop' + self.__class__.__name__
 278                                                 if hasattr(self, evt_name):
 279                                                         getattr(self, evt_name).fire()
 280                                                 # exit...
 281                                                 break
 282 ##                                      # handle stops...
 283 ##                                      if self._running == False:
 284 ##                                              if self._stop_exception != None:
 285 ##                                                      raise self._stop_exception, self._stop_reason
 286 ##                                              return self._stop_reason
 287                                         if self.__next_state__ != None:
 288                                                 # change state...
 289                                                 tostate = self.__next_state__
 290                                                 self.__next_state__ = None
 291                                                 self._changestate(tostate)
 292                         except FiniteStateMachineStop:
 293                                 pass
 294                         self._running = False
 295                         # fire the fsm stop event...
 296                         self.onFiniteStateMachineStop.fire()
 297                 else:
 298                         raise FiniteStateMachineError, 'can\'t start a manual (non-auto-change-state) FSM.'
 299 ##      def stop(self, reason=None, exception=None):
 300 ##              '''
 301 ##              '''
 302 ##              self._stop_exception = exception
 303 ##              self._stop_reason = reason
 304 ##              self._running = False
 305         # TODO automaticly init newly added states per FSM object on their
 306         #      (event) addition to the FSM class...
 307         #      ...or do a lazy init (as in RPG.action)
 308         #      actually the best thing would be to do both...
 309         def initstates(self):
 310                 '''
 311                 this will init state event.
 312
 313                 NOTE: it is safe to run this more than once (though this might not be very fast).
 314                 '''
 315                 # init all states...
 316                 for state in self.__states__.values():
 317                         state_name = state.__name__
 318                         for evt_name, evt_cls in (('onEnter' + state_name, self.__state_enter_event__),
 319                                                                           ('onExit' + state_name, self.__state_exit_event__)):
 320                                 if not hasattr(self, evt_name):
 321                                         setattr(self, evt_name, evt_cls(state_name))
 322                         # the stop event...
 323                         if isterminal(state):
 324                                 setattr(self, 'onStop' + state_name, onFiniteStateMachineStop(state_name))
 325         def changestate(self, tostate):
 326                 '''
 327                 '''
 328                 if hasattr(self, '__auto_change_state__') and self.__auto_change_state__:
 329                         self.__next_state__ = tostate
 330                 else:
 331                         self._changestate(tostate)
 332         def _changestate(self, tostate):
 333                 '''
 334                 '''
 335                 # call the __onexitstate__...
 336                 if hasattr(self, '__onexitstate__'):
 337                         self.__onexitstate__()
 338                 # fire the exit event...
 339                 evt_name = 'onExit' + self.__class__.__name__
 340                 if hasattr(self, evt_name):
 341                         getattr(self, evt_name).fire()
 342                 # change the state...
 343                 super(FiniteStateMachine, self).changestate(tostate)
 344                 # fire the enter event...
 345                 evt_name = 'onEnter' + self.__class__.__name__
 346                 if hasattr(self, evt_name):
 347                         getattr(self, evt_name).fire()
 348                 # run the post init method...
 349                 if hasattr(self, '__onafterstatechange__'):
 350                         self.__onafterstatechange__()
 351                 if hasattr(self, '__onenterstate__'):
 352                         self.__onenterstate__()
 353
 354
 355 #--------------------------------------------------------------_State---
 356 class _StoredState(stored._StoredClass):
 357         '''
 358         this meta-class will register the state classes with the FSM.
 359         '''
 360         # _StoredClass configuration:
 361         __class_store_attr_name__ = '__fsm__'
 362
 363         def storeclass(cls, name, state):
 364                 '''
 365                 register the state with the FSM.
 366                 '''
 367                 fsm = getattr(cls, cls.__class_store_attr_name__)
 368                 # check state name...
 369                 if hasattr(fsm, name):
 370                         raise NameError, 'state named "%s" already exists.' % name
 371                 # register the state...
 372                 if fsm.__states__ == None:
 373                         fsm.__states__ = {name: state}
 374                 else:
 375                         fsm.__states__[name] = state
 376                 # set the fsm initial state...
 377                 if hasattr(state, '__is_initial_state__') and state.__is_initial_state__:
 378                         if hasattr(fsm, '__initial_state__') and fsm.__initial_state__ != None:
 379                                 raise FiniteStateMachineError, 'an initial state is already defined for the %s FSM.' % fsm
 380                         fsm.__initial_state__ = state
 381
 382
 383 #---------------------------------------------------------------State---
 384 # TODO write more docs...
 385 # TODO add doc paramiter to transitions...
 386 # TODO error state handler...
 387 # TODO "Sub-FSMs"
 388 # TODO revise magic method names and function...
 389 class State(FiniteStateMachine):
 390         '''
 391         this is the base state class for the FSM framwork.
 392
 393         there are three utility methods that can be defined:
 394                 __runonce__                     : this will be run only once per state, this is
 395                                                           done mainly to register callbacks.
 396                 __onstatechange__       : this is run once per state change, right after
 397                                                           the change is made and just before the onEnter
 398                                                           event is fired.
 399                 __onafterstatechange__
 400                                                         : this is called after the state is finalized.
 401                                                           that is, just after the state onEnter event
 402                                                           processing is done.
 403                                                           NOTE: by default, this will select the first
 404                                                                         usable transition and use it to change
 405                                                                         state.
 406                 __onenterstate__        : this is called once per state change, just after
 407                                                           the onEnter event is fired.
 408                                                           NOTE: this is fired after the __onafterstatechange__
 409                                                                 method, and does NOTHING by default.
 410                 __onexitstate__         : this is called once per state change, just before
 411                                                           the change and before the onExit event is fired.
 412                 __resolvestatechange__
 413                                                         : this is called by the above method if no usable
 414                                                           transition was found and current state is not
 415                                                           terminal.
 416                 NOTE: all of the above methods receive no arguments but the object
 417                           reference (e.g. self).
 418
 419         on state instance creation, two events will get defined and added to the FSM:
 420                 onEnter<state-name> : this is fired on state change, just after the
 421                                                           __onstatechange__ method is finished.
 422                 onExit<state-name>      : this is fired just before the state is changed,
 423                                                           just after the __onexitstate__ is done.
 424
 425         for more information see: pli.pattern.state.State
 426
 427         '''
 428         __metaclass__ = _StoredState
 429
 430         # class configuration:
 431         # this is the class of fsm this state will belong to
 432         __fsm__ = None
 433         # if this is set the state will be registered as initial/start state
 434         __is_initial_state__ = False
 435         # if this is set the state will be registered as terminal/end state
 436         __is_terminal_state__ = False
 437
 438 ##      ##!!! not yet implemmented section....
 439 ##      # Error Handling setop options:
 440 ##      # this will enable/disable the error case exit mechanism...
 441 ##      __error_exit_enabled__ = False
 442 ##      # if this is set, the value will be used a an error case exit from
 443 ##      # this state...
 444 ##      __error_state__ = None
 445 ##      # if this is true, this state will be used as the default error
 446 ##      # exit for the fsm...
 447 ##      # NOTE: there may be only one default error exit.
 448 ##      __is_default_error_state__ = False
 449
 450         # StoredClass options:
 451         # do not register this class... (not inherited)
 452         __ignore_registration__ = True
 453         # auto register  all subclasses (inherited)
 454         __auto_register_type__ = True
 455
 456         # class data:
 457         _transitions = None
 458
 459         # TODO add support for string state names... (+ check consistency... (?))
 460         # TODO write a "removetransition" method....
 461         def transition(cls, tostate, condition=None, mode=AUTO):
 462                 '''
 463                 this will create a transition from the current state to the tostate.
 464                 '''
 465                 transitions = cls._transitions
 466                 if transitions == None:
 467 ##                      transitions = cls._transitions = {tostate: condition}
 468                         transitions = cls._transitions = {tostate: (condition, mode)}
 469 ##              elif tostate in transitions:
 470 ##                      raise TransitionError, 'a transition from %s to %s already exists.' % (cls, tostate)
 471                 else:
 472 ##                      cls._transitions[tostate] = condition
 473                         cls._transitions[tostate] = (condition, mode)
 474         transition = classmethod(transition)
 475         def changestate(self, tostate):
 476                 '''
 477                 change the object stete
 478                 '''
 479                 # prevent moving out of a terminal state...
 480                 if hasattr(self, '__is_terminal_state__') and self.__is_terminal_state__:
 481                         raise FiniteStateMachineError, 'can\'t change state of a terminal FSM node %s.' % self
 482                 fsm = self.__fsm__
 483                 # check for transitions...
 484                 if hasattr(fsm, '__strict_transitions__') and fsm.__strict_transitions__ and \
 485                                 (not hasattr(self, '_transitions') or self._transitions == None or \
 486                                 tostate not in self._transitions):
 487                         raise TransitionError, 'can\'t change state of %s to state %s without a transition.' % (self, tostate)
 488                 # check condition...
 489                 transitions = self._transitions
 490 ##              if transitions[tostate] != None and not transitions[tostate](self):
 491 ##              if transitions[tostate] != None and transitions[tostate][0] != None and not transitions[tostate][0](self):
 492                 if transitions[tostate][0] != None and not transitions[tostate][0](self):
 493                         raise TransitionError, 'conditional transition from %s to state %s failed.' % (self, tostate)
 494                 super(State, self).changestate(tostate)
 495                 # restart the fsm if __auto_change_state__ is set and we are
 496                 # not running...
 497                 if hasattr(self, '__auto_change_state__') and self.__auto_change_state__ \
 498                                 and not self._running:
 499                         self.start()
 500         def iternextstates(self):
 501                 '''
 502                 this will iterate through the states directly reachable from
 503                 self (e.g. to which there are direct transitions).
 504                 '''
 505                 if self._transitions == None:
 506                         return
 507                 for n in self._transitions:
 508                         yield n
 509         iternextstates = classmethod(iternextstates)
 510         # this method is called after the state is finalized (e.g. after the
 511         # __onstatechange__ is called and the onEnter event is processed).
 512         def __onafterstatechange__(self):
 513                 '''
 514                 this will try to next change state.
 515                 '''
 516                 if hasattr(self, '__auto_change_state__') and self.__auto_change_state__:
 517                         transitions = self._transitions
 518                         if transitions != None:
 519                                 for tostate, (cond, mode) in transitions.items():
 520                                         try:
 521 ##                                              self.changestate(tostate)
 522 ##                                              return
 523                                                 if mode == AUTO:
 524                                                         self.changestate(tostate)
 525                                                         return
 526                                         except:
 527                                                 ##!!!
 528                                                 pass
 529 ##                      if not hasattr(self, '__is_terminal_state__') or not self.__is_terminal_state__:
 530 ##                              if hasattr(self, '__resolvestatechange__'):
 531 ##                                      # try to save the day and call the resolve method...
 532 ##                                      return self.__resolvestatechange__()
 533 ##                              # we endup here if there are no exiting transitions
 534 ##                              # from a non-terminal state...
 535 ##                              # Q: whay do we need a terminal state?
 536 ##                              # A: to prevent exiting from it...
 537 ##                              raise FiniteStateMachineError, 'can\'t exit a non-terminal state %s.' % self
 538                         if (not hasattr(self, '__is_terminal_state__') or not self.__is_terminal_state__) \
 539                                         and hasattr(self, '__resolvestatechange__'):
 540                                 # try to save the day and call the resolve method...
 541                                 return self.__resolvestatechange__()
 542                         else:
 543                                 raise FiniteStateMachineStop, 'stop.'
 544         # this is here for documentation...
 545 ##      def __resolvestatechange__(self):
 546 ##              '''
 547 ##              this is called if no transition from current state is found, to
 548 ##              resolve the situation.
 549 ##              '''
 550 ##              pass
 551         # Q: does this need to be __gatattr__ or __getattribute__ ????
 552         # NOTE: this might make the attr access quite slow...
 553         # Q: is there a faster way??? (via MRO manipulation or something...)
 554         def __getattr__(self, name):
 555                 '''
 556                 this will proxy the attr access to the original startup class....
 557                 '''
 558                 ##!!! check for looping searching !!!##
 559                 # get the name in the startup class...
 560                 try:
 561                         return getattr(self.__startup_class__, name)
 562                 except AttributeError:
 563                         raise AttributeError, '%s object has no attribute "%s"' % (self, name)
 564
 565
 566 #--------------------------------------------------------InitialState---
 567 class InitialState(State):
 568         '''
 569         '''
 570         __is_initial_state__ = True
 571         __ignore_registration__ = True
 572
 573
 574 #-------------------------------------------------------TerminalState---
 575 class TerminalState(State):
 576         '''
 577         '''
 578         __is_terminal_state__ = True
 579         __ignore_registration__ = True
 580
 581
 582
 583 #=======================================================================
 584 #                                            vim:set ts=4 sw=4 nowrap :