Testing finite state machines in C++

#cpp #testing #fsm

Introduction

The state machine design pattern is an incredibly useful tool for writing well structured and testable software. However, it quickly becomes difficult to efficiently test software components that make use of finite state machines (FSM) without repeating boilerplate code. In my experience, most of this boilerplate code is produced by providing stimuli to the component to transition to the desired state for a test case. The project layout and methodology presented in this article aim to improve test readability and maintainability. All source code is available on my GitHub.

This article is based on the classic UML state pattern. In order to understand the ideas presented in the following paragraphs it is necessary to have a good understand of this design pattern.

Project Layout

The project follows a component oriented approach. Consider the directory structure of the repository. The include directory contains the public interface of the component which only consists of a pure abstract class a.k.a. interface in C++. Furthermore, the directory contains the declaration of the factory which returns an implementation of the public interface.

The src directory contains implementation private source and header files which are fully consumed into the compiled library. The user of the component does not have access to this code. The component diagram below reflects the macro structure of the project. The user only has access to the public interface while the concrete implementation is opaquely instantiated through a simple factory. The states component is project internal and not accessible through the public interface.

Architecture

The program developed for this example simulates the behavior of a dog which offers the following functions:

Pet (state independent)
Perform a command that triggers a state transition (only possible in states STANDING, SITTING and LAYING)
Feed (only possible in state SITTING and state does not change)
Sleep (only possible in state LAYING)
Wake up (only possible in state SLEEPING)

The state machine below summarizes the state transitions of the dog:

Analyzing the situation from a testing perspective we can define three equivalence classes (EC):

State independent functions
State dependent functions that do not trigger a state transition
State dependent functions that trigger a state transition

In order to test the first EC it is desirable to have control over the state classes which are injected in the state dependent class. Since the functionality is state independent it must also expose the same behavior if no state is present. Therefore, state independent functionality may not use any functions which are defined in the state classes. In test cases this is asserted by simply providing an implementation that aborts the test in case a state function is called. Furthermore, the ability to artificially put the FSM in a certain state to test the non transitional behavior is important to test the second EC. The third EC is tested by providing a stimulus through the public interface and to assert correct transitioning. These requirements lead to the following architecture where the interface Dog is the public interface from the component diagram above:

The introduction of the class SharedAttributes enables the injection of an alternative implementation of the State interface as well as the artificial maneuvering of the FSM through the function setCurrentState for testing the first and second EC. Moreover, this class may be used to share resources like state instances, threads, mutexes etc. between states and the states owner. In production the State interface implementation is reflected by the following class diagram:

The class BaseState has been introduced because it is not possible to mock abstract classes with member variables with the chosen mocking framework FakeIt. Nevertheless, the concrete state implementations need access to the SharedAttributes class which is a protected member of BaseState. Conveniently, BaseState provides default implementations for certain functions which may be overwritten by the concrete states.

Using the design pattern "abstract factory" to instantiate the states component enables the provision of a factory which returns an alternative implementation for the states. This has been done in the state independent test cases.

Tests

The first two ECs are white box tests since they need access to the declarations of State and StateFactory which are not accessible through the public interface. This is reflected by the include directories for these targets which give access to the private src directory. For state independent functions the interface State is mocked and every function call throws an exception which aborts the test. For testing state functionality a handle to the m_attributes member of DogImpl is kept to manually set states.

The last EC is a black box test: The DogImpl class is instantiated through the factory provided in the public interface and the corresponding target only has access to the public include directory. Thereafter, appropriate stimulus is applied to the component and correct state transitioning is asserted.

This test methodology ensures that each aspect of the FSM is only tested once following the DRY principle. It produces highly readable and maintainable tests.