Developing state machines with test-driven development




Since state machine models are widely used in embedded systems, this article explores several strategies to develop state machine (SM) software under the Test-Driven Development (TDD) approach. This publication starts by explaining basic state machine concepts and the TDD technique. Finally, it introduces simple and ordered methods to develop state machine software written in C using the TDD approach.

A SM model is composed of states, transitions and actions. While a state is a condition of a system or an element, a transition is a path from one state to another, usually initiated by an event of interest that connects a predecessor (source) state with a subsequent (target) state. The actual behaviors executed by the element are represented in actions.

In the UML state machine, actions may be associated with entry into a state, exit from a state, a transition per se, or what is called an ‘internal transition’ or ‘reaction’. All state machine’s formalisms (including UML state machines) universally assume that a state machine completes the processing of each event before it can start processing the next one. This model of execution is called Run To Completion (RTC). In this model, actions may take time, but any pending events must wait until the state machine has been completed — including the entire exit action, the transition action and the entry action sequence in that order.

Before dealing with the strategies to develop state machines by using TDD, it is worth to mention its definition, importance and application.

First of all, TDD is a technique for building software incrementally. Simply put, no production code is written without first writing a failing unit test. Tests are small. Tests are automated. Test-driving is logical, i.e. instead of diving into the production code (leaving testing for later) the TDD practitioner expresses the desired behavior of the code in a test. Once the test fails, the TDD practitioner writes the code, making the test pass. At the core of the TDD process, there is a repeating cycle composed of short steps known as “TDD microcycles”.

The steps of the TDD cycle in the following list are based on James Grenning’s ‘Test-Driven Development for Embedded C’ book:

  • Add a small test.
  • Run all the tests and if the new one fails, it may not even compile.
  • Make the small changes needed to pass the test.
  • Run all the tests and prove if the new one passes.
  • Refactor to remove duplication and improve expressiveness.

Let’s use the diagram in Figure 1 to find a simpler way to develop a state machine using TDD. When the state machine is initialized, it starts from the StateA state. Once it receives the Alpha event, the state machine transitions to the StateB state by executing the xStateA(), effect() and nStateB() actions in that order. So, how can one test the SM of Figure 1 to determine if it behaves appropriately?


Figure 1. Basic state machine (Source: VortexMakes)

The most traditional and simplest way of testing a SM like Figure 1 consists mainly on verifying the state transition table of the SMUT (State Machine Under Test). This makes a test case per state, in which the SMUT is stimulated by the events of interest to verify which transitions are triggered. At the same time, this will imply checking the target state and the executed actions for each fired transition. If an action is sufficiently complex, it is more suitable to make a specific test case for that. (The article Testing state machines using unit test explains this strategy in depth).

Every test case is divided into four distinct phases according to xUnit patterns:

  • Setup establishes the preconditions of the test, such as the SM’s current state (StateA), the event to be processed (Alpha), and the expected test results, which are the transition target state (StateB) and the sorted list of actions to be executed (xStateA(), effect() and nStateB()).
  • Exercise stimulates the state machine with the Alpha event.
  • Verify checks the obtained outcomes.
  • Cleanup returns the state machine under test to its initial state after the test. It is optional.

The strategy mentioned above is enough to develop a SM using TDD. However, in some cases more than a single transition is needed to check functionality. This is because the effect only gets visible due to a chain of actions of subsequent transitions, which means that functionality involves a set of states, events and transitions of the SMUT. In these cases, it is more appropriate to test a complete and functional scenario than isolated state transitions.  As a result, test cases are more functional and less abstract than the strategies previously mentioned.

Let’s use the state machine in Figure 2 to explore this concept.


Figure 2. The DoWhile state machine (Source: VortexMakes)

Figure 2 shows a state machine called DoWhile, which models an execution loop similar to ‘do-while’ one. DoWhile was drawn using Yakindu Statechart Tool. The ‘x = 0’ and ‘output = 0’ actions are called when DoWhile is created and these actions set the default value of all DoWhile’s attributes. The number of loop iterations must be set through ‘x++’ or ‘x = (x > 0) ? x–: x’ actions. The ‘i = 0’ action establishes initial conditions for the loop. The loop body is executed by ‘i++’ action, which keeps up the loop iterations, then the termination condition is evaluated by the choice pseudostate through the ‘i == x’ guard. If it is true, the loop body is evaluated again, and so on. When the termination condition becomes false, the loop terminates executing the ‘output = i’ action.

It is helpful to create a test list before developing new functionality. The test list derives from the specification and it defines the best vision of what it should be done. Since it does not need to be perfect, the former list is just a temporary document that could be modified later on. The initial test list for DoWhile is shown below:

  • All data are set by default after SM is initialized
  • Increment X attribute
  • Decrement X attribute
  • A single iteration loop can be executed
  • A multiple iteration loop can be executed
  • A non iteration loop can be executed
  • Check out-of-bounds values

In order to develop DoWhile state machine, Ceedling and Unity will be used together with the most simple but lucid programming technique: use of ‘switch-case’ sentences. Ceedling is a build system to generate an entire test and build environment for a C project; Unity is a lightweight portable expressive C-language test harness for C projects.

Two files represent this state machine, DoWhile.h and DoWhile.c, so they are the source code under test. Code Listing 1 shows a fragment of test_DoWhile.c file, which implements the test list above by applying the previously mentioned strategy. In order to keep this article simple, Code Listing 1 only shows the test case:  ‘A single iteration loop can be executed‘, which is implemented by test_SingleIteration(). Both code and model are available in https://github.com/leanfrancucci/sm-tdd.git repository.


Code Listing 1: Single iteration test (Source: VortexMakes)

This test verifies that DoWhile can execute just one iteration correctly. To do that, the test_SingleIteration() initializes the DoWhile state machine by calling DoWhile_init() (line 96). It sets the iteration number for zero to be executed by DoWhile loop. After that, the DoWhile is ready to process events by calling DoWhile_dispatch(). To execute a single iteration, test_SingleIteration() sends the Up event to DoWhile (line 97). This event increments the iteration number to one. The test starts the loop by sending the Start event (line 98), then it sends the Alpha event so DoWhile executes a single iteration (line 99). This is checked by verifying that the value of the out attribute is equal to the number of executed iterations (line 101). Finally, DoWhile has to remain in the StateC state (line 102).

To prove that DoWhile can execute more than one iteration, the test_SingleIteration() is extended as shown in Code Listing 2.


Code Listing 2: Multiple iteration test (Source: VortexMakes)

The test_NoneIteration() test shown in Code Listing 3 checks that DoWhile does not execute any iteration when receiving an Alpha event without previously setting the iteration number through Up events.


Code Listing 3: Non iteration test (Source: VortexMakes)

Although DoWhile’s implementation details are not the aim of this article, Code Listing 4 and Code Listing 5 show part of the DoWhile.c and DoWhile.h files. These files actually represent a demonstrative implementation of DoWhile using ‘switch-case’ sentences in C.


Code Listing 4: Fragment of DoWhile implementation (Source: VortexMakes)


Code Listing 5: Fragment of DoWhile specification (Source: VortexMakes)

Both of the strategies introduced above provide simple and ordered methods to develop state machine software using TDD — one of the most important approaches to increase software quality.

The first strategy consists mainly of verifying the state transition table of the SMUT. This method  makes a test case per state. The other strategy proposes to realize a test case for a complete and functional scenario, which frequently involves a set of states, events and actions of the SMUT. This second strategy makes the test more functional and less abstract than the first one. Although these strategies are independent of a particular kind of system, programming language or tool, they are very useful in embedded systems, because many of them have state-based behavior that is typically defined in one or more state machines.

The C language was chosen because it is one of the most popular languages for embedded software development. So, in order to apply TDD in that language, Ceedling and Unity were chosen. To conclude, these methods definitely allow developers to build in a simpler and ordered way a much more flexible, maintainable and reusable software than traditional approaches.


Leandro Francucci is an electronic engineer who has focused in real-time embedded system development using software models in several industries for more than ten years, such as railway, medical, IoT, telecom, and energy. Leandro is the author of the free and open-source RKH state machine framework, and he is also the co-founder and owner of VortexMakes, a startup to provide consulting and training services in embedded software for companies of all sizes. Leandro is always interested in new challenges, as well as knowledge transfer, researching and constant learning.

 

The post Developing state machines with test-driven development appeared first on Embedded.com.





Original article: Developing state machines with test-driven development
Author: Leandro Francucci