rstdocs/examples/simplestates_test.py

   1 #!/usr/bin/env python
   2
   3 # # -*- coding: iso-8859-1 -*-
   4 #
   5 # Test the simplestates.py generic state machine
   6 # ==============================================
   7 #
   8 # :Status:    draft
   9 # :Date:      2006-12-01
  10 # :Copyright: 2006 Guenter Milde.
  11 #             Released under the terms of the GNU General Public License
  12 #             (v. 2 or later)
  13 #
  14 # .. default-role:: literal
  15 # .. sectnum::
  16 #
  17 # .. contents:: :depth: 2
  18 #
  19 #
  20 # Abstract State Machine Class
  21 # ============================
  22 #
  23 # First version of an abstract state machine
  24 # ::
  25
  26 class SimpleStates1:
  27     """generic state machine acting on iterable data
  28
  29     Class attributes
  30     init_state -- name of the first state_handler method
  31     """
  32     init_state = 'start'
  33
  34 # Initialisation
  35 #
  36 # * sets the data object to the `data` argument.
  37 # * remaining keyword arguments are stored as class attributes (or methods, if
  38 #   they are function objects) overwriting class defaults (a neat little trick
  39 #   I found somewhere on the net)
  40 # * the `state_handler` attribute is set to the method named in `init_state`
  41 #
  42 # ::
  43
  44     def __init__(self, data, **keyw):
  45         """data   --  iterable data object
  46                       (list, file, generator, string, ...)
  47            **keyw --  all remaining keyword arguments are
  48                       stored as class attributes
  49         """
  50         self.data = data
  51         self.__dict__.update(keyw)
  52
  53 # The special `__iter__` method returns an iterator_. This allows to use
  54 # a  class instance directly in an iteration loop.  We define it as is a
  55 # generator_ method that sets the initial state and then iterates over the
  56 # data calling the state methods::
  57
  58     def __iter__(self):
  59         self.state_handler = getattr(self, self.init_state)
  60         for token in self.data:
  61             yield self.state_handler(token)
  62
  63 # To use class instances as callable objects, we add a `__call__` method::
  64
  65     def __call__(self):
  66         """Run state-machine and return tokens as a list"""
  67         return [token for token in self]
  68
  69 # Example 1: A two-state machine sorting numbers
  70 # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  71 #
  72 # Our small example state machine subclasses the `SimpleStates1` class::
  73
  74 class Example1(SimpleStates1):
  75     """A silly example two-state machine sorting numbers
  76     in the categories "low" (< 3) and "high" (>= 3).
  77     """
  78
  79 # It will be completed by two state methods and a `__str__` method.
  80 #
  81 # State Methods
  82 # -------------
  83 #
  84 # State methods are functions that are called to iterate over the data. They
  85 # will typically
  86 #
  87 # * test the data token for a change of state indicator
  88 # * return the data token after some processing
  89 #
  90 # In our example, the `low` method switches to `high` (and calls it with the
  91 # data token), if token is bigger than 3. If not, it returns "l(token)"::
  92
  93     def low(self, token):
  94         # print "low(", token, ")",
  95         if token > 3:
  96             self.state_handler = self.high
  97             # backtracking
  98             return self.state_handler(token)
  99         return "l(%d)"%token
 100
 101 # The `high` method switches to `low`, if token is bigger than 3. If not, it
 102 # returns "h(token)"::
 103
 104     def high(self, token):
 105         # print "high(", token, ")",
 106         if token <= 3:
 107             self.state_handler = self.low
 108             # backtracking
 109             return self.state_handler(token)
 110         return "h(%d)"%token
 111
 112 # Conversion of the class instance to a string is done by joining the list
 113 # that is returned by a call to the instance with spaces::
 114
 115     def __str__(self):
 116         return " ".join(self())
 117
 118 # Test
 119 # ----
 120 #
 121 # Testing is done with the nose_ test framework. This will collect and
 122 # execute all test functions and methods (basically everything that starts or
 123 # ends with "[Tt]est"). This is similar to the more known "py.test".
 124 #
 125 # .. _nose: http://somethingaboutorange.com/mrl/projects/nose/
 126 #
 127 # We set up some test data::
 128
 129 testdata = [1, 2, 3, 4, 5, 4, 3, 2, 1]
 130
 131 # and define a test function::
 132
 133 def test_Example1():
 134     statemachine = Example1(testdata, init_state='low')
 135     for result in statemachine:
 136         print result,
 137     print
 138
 139     # Calling an instance should return a list of results
 140     print statemachine()
 141     assert statemachine() == ['l(1)','l(2)','l(3)',  # low numbers
 142                              'h(4)','h(5)','h(4)',  # high numbers
 143                              'l(3)','l(2)','l(1)']  # low again
 144
 145     # Converting to a string should call the __str__ method::
 146     print str(statemachine)
 147     assert str(statemachine) == "l(1) l(2) l(3) h(4) h(5) h(4) l(3) l(2) l(1)"
 148
 149 # Discussion
 150 # ----------
 151 #
 152 # The sorting works as expected. However, as the state handlers get the data
 153 # token by token, acting on subsequent tokens or tests that combine the
 154 # knowledge of several tokens are hard to achieve.
 155 #
 156 # An example would be a state handler that sums up the data tokens and
 157 # returns the result if it exceeds a threshold.
 158 #
 159 #
 160 #
 161 # Varied State Machine Class Template
 162 # ===================================
 163 #
 164 # The second version of an abstract state machine converts the test data to an
 165 # iterator which is shared by the state methods.
 166 #
 167 # There is no need to pass this on via arguments, as class methods share the
 168 # class instances attributes (class variables).
 169 #
 170 # We subclass our first version and modify to our needs::
 171
 172 class SimpleStates2(SimpleStates1):
 173     """second version of the abstract state machine class
 174     """
 175
 176 # We add the initialization of the data to the `__iter__` method. The data is
 177 # transformed inta an iterator_ first. ::
 178
 179     def __iter__(self):
 180         self.data_iterator = iter(self.data)
 181         self.state_handler = getattr(self, self.init_state)
 182         # do not pass data tokens as argument
 183         # (state methods should call self.data_iterator.next() instead)
 184         while True:
 185             yield self.state_handler()
 186
 187 # Iterators "use up" the data, so the state methods will always get a "new"
 188 # token until the data is fully "used up" and `StopIteration` is raised
 189 # aborting the iteration.
 190 #
 191 # Doing the conversion from iterable to iterator in `__iter__` and not in
 192 # `__init__` allows repeated iteration over the class instance (if the data is
 193 # a list or a file and not already a generator) as the "used up" generator is
 194 # replaced by a new one.
 195 #
 196 # Example 2: Another two-state machine sorting numbers
 197 # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 198 #
 199 # Our small example state machine subclasses the `SimpleStates2` class
 200 # and adds 2 methods as state handlers. ::
 201
 202 class Example2(SimpleStates2):
 203     """An example two-state machine sorting numbers
 204     in the categories "low" (< 3) and "high" (>= 3).
 205     """
 206
 207 # State methods
 208 # -------------
 209 #
 210 # This time, the state methods will get the data tokens not as argument but
 211 # take them from the `data_iterator`. Note that *backtracking* is impossible
 212 # with a standard iterator. See below for the problem this causes for our
 213 # sorting algorithm. ::
 214
 215     def low(self):
 216         # print "low(", token, ")",
 217         token = self.data_iterator.next()
 218         if token > 3:
 219             self.state_handler = self.high
 220         return "l(%d)"%token
 221     def high(self):
 222         # print "high(", token, ")",
 223         token = self.data_iterator.next()
 224         if token <= 3:
 225             self.state_handler = self.low
 226         return "h(%d)"%token
 227
 228 # Test
 229 # ----
 230 #
 231 # Define a second test function::
 232
 233 def test_Example2():
 234     statemachine = Example2(testdata, init_state='low')
 235
 236 # Calling an instance should return a list of results. However, as
 237 # we cannot backtrack on a normal iterator, the result is not as we expected:
 238 # There is a "hysteresis" the "switch triggering" token is always processed by
 239 # the "old" state::
 240
 241     print statemachine()
 242     assert statemachine() == ['l(1)', 'l(2)', 'l(3)', # low numbers
 243                              'l(4)', 'h(5)', 'h(4)', # high numbers
 244                              'h(3)', 'l(2)', 'l(1)'] # low numbers
 245
 246 # Discussion
 247 # ----------
 248 #
 249 # Missing backtracks break our number sorting machine. The remedy
 250 # is the use of an iterator with an appendleft() method (known from the
 251 # dqueue() standard class). We will come to this in `Example 4`__
 252 #
 253 # __ `Example 4: A two-state machine with generators and backtracking`_
 254 #
 255 # OTOH, as the state methods do the fetching of data tokens themself, a state
 256 # handler that sums up the data tokens and returns the result if it exceeds a
 257 # threshold would be easy to implement. We will do this in our next example
 258 # using state handler generators.
 259 #
 260 #
 261 # State Machine class using state_handler generators
 262 # ==================================================
 263 #
 264 # The variations in `StateMachine2` complicate the StateMachine design. They
 265 # makes sense, however, if we use generated iterators to handle the states.
 266 # No changes are needed to the abstract base class, so that Example 3 can
 267 # build on `StateMachine2`::
 268
 269 class Example3(SimpleStates2):
 270
 271 # Example 3: A two-state machine with state handler generators
 272 # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 273 #
 274 # State Generators
 275 # ----------------
 276 #
 277 # State Generators generate and return an iterator that will handle the next
 278 # data token(s) if its .next() method is called. This is easily achieved with a
 279 # for loop over self.data and the `yield` keyword.
 280 # ::
 281
 282     def high_handler_generator(self):
 283         """Return an iterator, whose next() method
 284         returns "h(token)" and switches to `low`, if token > 3
 285         """
 286         for token in self.data_iterator:
 287             if token <= 3:
 288                 self.state_handler = self.low
 289             yield "h(%d)"%token
 290     #
 291     def low_handler_generator(self):
 292         """Return an iterator, whose next() method sums up data tokens.
 293         If the sum exceeds 8, it is returned and the state
 294         switches to `high`.
 295         """
 296         sum = 0
 297         for token in self.data_iterator:
 298             sum += token
 299             if sum > 8:
 300                 self.state_handler = self.high
 301                 yield "s=%d"%sum
 302                 sum = 0 # next iteration continues here
 303         # no more tokens but sum not reached
 304         yield "p=%d"%sum # partial sum
 305
 306 # The iterator must instanciate the state-iterators before starting the
 307 # iteration loop::
 308
 309     def __iter__(self):
 310         """Generate and return an iterator
 311
 312         * convert `data` to an iterator
 313         * convert the state generators into iterators
 314         * (re) set the state_handler attribute to the init-state
 315         * pass control to the active states state_handler
 316           which should call and process self.data_iterator.next()
 317         """
 318         self.data_iterator = iter(self.data)
 319         self.high = self.high_handler_generator().next
 320         self.low = self.low_handler_generator().next
 321         # init state
 322         self.state_handler = getattr(self, self.init_state)
 323         # now start the iteration, aborts if data is empty
 324         while True:
 325             yield self.state_handler()
 326
 327 # Test
 328 # -------
 329 #
 330 # Again define a test function that gets an instance of the Example3 class ::
 331
 332 def test_Example3():
 333     statemachine = Example3(testdata, init_state='low')
 334
 335 # Calling statemachine() should iterate over the test data and return the
 336 # processed values as list::
 337
 338     print statemachine()
 339     assert statemachine() == ['s=10','h(5)','h(4)','h(3)', 'p=3']
 340
 341 # Backtracking
 342 # ============
 343 #
 344 # the iterqueue module provides an "extendable" iterator with, e.g.,
 345 # an `appendleft` method to push back values::
 346
 347 from iterqueue import XIter
 348
 349 # Thus we can prepend a non-processed data item
 350 # to the data iterator for use by the next state handler
 351 #
 352 # Example 4: A two-state machine with generators and backtracking
 353 # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 354 #
 355 # Again we start from the `SimpleStates2` base class::
 356
 357 class Example4(SimpleStates2):
 358     """two-state machine with generators and backtracking
 359     """
 360
 361 # Let the iterator wrap the data in an XIter instance with `appendleft`
 362 # method::
 363
 364     def __iter__(self):
 365         """Generate and return an iterator
 366
 367         * convert `data` to an iterator queue
 368         * convert the state generators into iterators
 369         * (re) set the state_handler attribute to the init-state
 370         * pass control to the active states state_handler
 371           which should call and process self.data_iterator.next()
 372         """
 373         self.data_iterator = XIter(self.data) # queue with `appendleft` method
 374         self.high = self.high_handler_generator().next
 375         self.low = self.low_handler_generator().next
 376         self.state_handler = getattr(self, self.init_state)
 377         # now start the iteration
 378         while True:
 379             yield self.state_handler()
 380
 381 # Add state method generators that use the "backtracking" feature::
 382
 383     def high_handler_generator(self):
 384         """Return an iterator, whose next() method
 385         returns "h(token)" and switches to `low`, if token > 3
 386         """
 387         for token in self.data_iterator:
 388             # print "high got", token
 389             if token <= 3:
 390                 # push back data token
 391                 self.data_iterator.appendleft(token)
 392                 # set the new state
 393                 self.state_handler = self.low
 394                 # return non-value indicating the state switch
 395                 yield None
 396             else:
 397                 yield "h(%d)"%token
 398     #
 399     def low_handler_generator(self):
 400         """Return an iterator, whose next() method
 401         returns "l(token)" and switches to `high`, if token <=3
 402         """
 403         for token in self.data_iterator:
 404             # print "low got", token
 405             if token > 3:
 406                 self.data_iterator.appendleft(token) # push back
 407                 # set and run the new state
 408                 self.state_handler = self.high
 409                 # alternatively, return the token processed by the new
 410                 # state handler
 411                 yield self.state_handler()
 412             else:
 413                 yield "l(%d)"%token
 414
 415 # The `__str__` converter should ignore the switch-indicator::
 416
 417     def __str__(self):
 418         tokens = [token for token in self() if token != None]
 419         return " ".join(tokens)
 420
 421 # Test
 422 # -------
 423 #
 424 # Again define a test function. This time with an instance of the Example4
 425 # class ::
 426
 427 def test_Example4():
 428     statemachine = Example4(testdata, init_state='low')
 429
 430 # Calling statemachine() should iterate over the test data and return the
 431 # processed values as list. If the state of the machine changes, the special
 432 # "non-value" `None` is returned. ::
 433
 434     print statemachine() # only printed if something goes wrong
 435     assert statemachine() == ['l(1)', 'l(2)', 'l(3)',
 436                              'h(4)', 'h(5)', 'h(4)', None, # switch indicator
 437                              'l(3)', 'l(2)', 'l(1)']
 438
 439 # Converting to a string should skip the `None` values::
 440
 441     print statemachine
 442     assert str(statemachine) == "l(1) l(2) l(3) h(4) h(5) h(4) l(3) l(2) l(1)"
 443
 444 # Discussion
 445 # ----------
 446 #
 447 # The `XIter` class allows backtracking also in a state machine with state
 448 # handlers acting on a common iterator object. The "high" and "low" handlers
 449 # demonstrate two possible actions for the state-transition with backtrack:
 450 # Either call the new state handler from the current one
 451 # (like the `low_handler_generator`) or return a "non-value" that signifies
 452 # that processing the data token did not produce any output data.
 453 #
 454 # Using generators made the state handlers shorter and (once the concept of a
 455 # generator is clear) easier. Further advantages of the generator concept are
 456 #
 457 # * internal variables are easily saved over subsequent invocations
 458 # * no function-call overhead (not relevant in this example but maybe for a
 459 #   state machine that has to process long data lists.
 460 #
 461 #
 462 # Converting all state method generators with a generic function
 463 # ==============================================================
 464 #
 465 # In `Example4`, we had to redefine the `__iter__` method to convert the
 466 # methode state generators into iterators. It would be nice if this could be
 467 # done in the base class.
 468 #
 469 # `SimpleStates3` adds a generic function for this task that relies on a
 470 # simple naming convention: functions whose name matches
 471 # `<state>_handler_generator` should be converted to iterators and their
 472 # `.next()` method stored as `<state>`.
 473 # ::
 474
 475 class SimpleStates5(SimpleStates2):
 476     """generic state machine acting on iterable data
 477     """
 478     def _initialize_state_generators(self):
 479         """Generic function to initialize state handlers from generators
 480
 481         functions whose name matches `[^_]<state>_handler_generator` should
 482         be converted to iterators and their `.next()` method stored as
 483         `<state>`.
 484         """
 485         suffix = "_handler_generator"
 486         shg_names = [name for name in dir(self)
 487                       if name.endswith(suffix)
 488                       and not name.startswith("_")]
 489         for name in shg_names:
 490             shg = getattr(self, name)
 491             print shg
 492             setattr(self, name[:-len(suffix)], shg().next)
 493
 494
 495     def __iter__(self):
 496         """Generate and return an iterator
 497
 498         * convert `data` to an iterator queue
 499         * convert the state generators into iterators
 500         * (re) set the state_handler attribute to the init-state
 501         * pass control to the active states state_handler
 502           which should call and process self.data_iterator.next()
 503         """
 504         self.data_iterator = XIter(self.data) # queue with `appendleft` method
 505         self._initialize_state_generators()
 506         self.state_handler = getattr(self, self.init_state)
 507         # now start the iteration
 508         while True:
 509             yield self.state_handler()
 510
 511 # Example 5
 512 # ~~~~~~~~~
 513 #
 514 # The next example combines the state handlers from Example 4 and the new
 515 # class.::
 516
 517 class Example5(Example4, SimpleStates5):
 518     """one more example"""
 519     pass
 520
 521 # Test
 522 # ----
 523 #
 524 # A function that has the generator-suffix but is prefixed with an underscore,
 525 # should be skipped by the `_initialize_state_generators` method::
 526
 527 class Test_SimpleStates5:
 528     E5 = Example5(testdata)
 529     E5._bogus_handler_generator = "low"
 530     def test_initialize_state_generators(self):
 531         self.E5._initialize_state_generators()
 532
 533 # A test function. This time with an instance of the Example5 class ::
 534
 535 def test_Example5():
 536     statemachine = Example5(testdata, init_state='low')
 537     print statemachine.__dict__
 538
 539 # Calling statemachine() should iterate over the test data and return the
 540 # processed values as list. If the state of the machine changes, the special
 541 # "non-value" `None` is returned. ::
 542
 543     print statemachine() # only printed if something goes wrong
 544     assert statemachine() == ['l(1)', 'l(2)', 'l(3)',
 545                              'h(4)', 'h(5)', 'h(4)', None, # switch indicator
 546                              'l(3)', 'l(2)', 'l(1)']
 547
 548 # Converting to a string should skip the `None` values::
 549
 550     print statemachine
 551     assert str(statemachine) == "l(1) l(2) l(3) h(4) h(5) h(4) l(3) l(2) l(1)"
 552
 553 # Putting it together
 554 # ===================
 555 #
 556 # The file `simplestates.py` contains the full definition of the `SimpleStates5`
 557 # class in a self-contained version.
 558 #
 559 # Example 6
 560 # ~~~~~~~~~
 561 #
 562 # The final Example is used to test whether we have put it together well. It
 563 # subclasses SimpleStates and adds state method generators for "high" and
 564 # "low"::
 565
 566 import simplestates
 567 class Example6(simplestates.SimpleStates):
 568     """two-state machine with generators and backtracking
 569     """
 570     def high_handler_generator(self):
 571         """Return an iterator, whose next() method
 572         returns "h(token)" and switches to `low`, if token > 3
 573         """
 574         for token in self.data_iterator:
 575             # print "high got", token
 576             if token <= 3:
 577                 # push back data token
 578                 self.data_iterator.appendleft(token)
 579                 # set the new state
 580                 self.state_handler = self.low
 581                 # return the token processed by the new state handler
 582                 yield self.state_handler()
 583             else:
 584                 yield "h(%d)"%token
 585     #
 586     def low_handler_generator(self):
 587         """Return an iterator, whose next() method
 588         returns "l(token)" and switches to `high`, if token <=3
 589         """
 590         for token in self.data_iterator:
 591             # print "low got", token
 592             if token > 3:
 593                 self.data_iterator.appendleft(token) # push back
 594                 # set and run the new state
 595                 self.state_handler = self.high
 596                 # return the token processed by the new state handler
 597                 yield self.state_handler()
 598             else:
 599                 yield "l(%d)"%token
 600
 601 # Test
 602 # ----
 603 #
 604 # In order not to make it dependent on the iterqueue module, the final
 605 # `SimpleStates` doesnot wrap the data in an XIter instance. This step should
 606 # be done at the instanciation of a state machine. ::
 607
 608 def test_Example5():
 609     statemachine = Example5(XIter(testdata), init_state='low')
 610     print statemachine.__dict__
 611
 612 # Calling statemachine() should iterate over the test data and return the
 613 # processed values as list::
 614
 615     print statemachine() # only printed if something goes wrong
 616     # reset the data iterator as it is "used up" now
 617     statemachine.data = XIter(testdata)
 618     assert statemachine() == ['l(1)', 'l(2)', 'l(3)',
 619                              'h(4)', 'h(5)', 'h(4)', None,
 620                              'l(3)', 'l(2)', 'l(1)']
 621
 622 # Index
 623 # =====
 624 #
 625 #
 626 # :_`generator`: A function with a `yield` keyword. Calling this function will
 627 #                return an iterator_
 628 #
 629 # :_`iterator`: An object with a `next()` method. Calling `<iterator>.next()`
 630 #               will (typically) return one data token (list element, line in
 631 #               a file, ...). If there is no more data the `StopIteration`
 632 #               exception is raised.
 633 #
 634 # Command line usage
 635 # ==================
 636 #
 637 # running this script should explore it in the "nose" test framework::
 638
 639 if __name__ == "__main__":
 640     import nose, doctest
 641     # first run any doctests
 642     doctest.testmod()
 643     # then run nose on this module
 644     nose.runmodule() # requires nose 0.9.1