Model based testing made simplistic
Property based testing is an effective way to verify the input/output relation of pure functions, leveraging predicates (properties) to declaratively describe such relation.
Model based testing extends the scope to stateful systems, whose behavior is described in terms of an abstract model, leveraging state machines.
This is an introduction aimed at providing a basic understanding of the idea. It is yet another poor man's approach which may also work in practice but, since it is deliberately simplistic, you may also want to invest some time learning about the APIs provided by libraries.
A simple example
Our system under test is the Queue
class from the .NET base library.
We model its state as a list and we focus on two actions only: enqueue and dequeue.
1: 2: 3: 4: 5: 6: 7: |
|
The whole point of the approach is to perform an action both on the abstract model and on the actual system, and then check that the resulting state is the same.
The system and its model
The functions fromModel
and toModel
define the correspondance between the actual system and its abstract model.
They are easy to implement in this example but may be challenging in more realistic scenarios.
Such challenges may arise from the system hiding its internal state or persisting it in a distributed
environment. Most libraries for model based testing in fact take a different route (as we will see later)
but for now we naively assume that:
fromModel
puts the system under test in the given state.toModel
retrieves the state of the system under test.
1: 2: 3: 4: 5: |
|
State transitions
The essence of our model is captured by the following function defining state transitions:
1: 2: 3: 4: |
|
The effect of enqueing an item corresponds (in the abstract model) to appending it to the list representing the state of the system.
The abstract effect of a dequeue is to remove the head of the list representing the state.
The run
function is the actual counterpart to the nextState
function above.
This time the action is executed on the system under test.
1: 2: 3: 4: 5: |
|
Invariant and Precondition
Next we define two predicates: an invariant (that should hold in every state) and a precondition (that should hold in order to perform an action):
1: 2: 3: 4: 5: 6: |
|
In this case the invariant always holds, we made illegal states unrepresentable! (but it was an easy win, let me suggest a nice article about this topic).
With the precondition we express that a dequeue action may not be performed on an empty queue.
Running a test
The test
function initializes the system under test with the given state,
then runs the given action on it and finally checks that its resulting state
conforms to the model.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: |
|
Let's examine the code in more detail.
First we check that the input satisfies the invariant and the precondition.
Then we initialize the system under test, establishing the given state (and we verify that the initialization succeded by checking the state).
Next we use the model to get the state expected after the execution of the action (and we verify that this next state produced by the model still satisfies the invariant).
Then we run the action on the actual system, and we verify that, after the execution, the state of the system under test is the same as the expected one according to the model.
Random input
To run test
with many random inputs we need a generator of state-action pairs satisfying invariant and precondition:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: |
|
|
FsCheck state machines
As anticipated, initializing a real system to an arbitrary state may be hard. But we can explore many states executing a sequence of actions starting from a state that's easy to establish.
FsCheck state machines allow this. It requires a bit of boilerplate,
but we can reuse actionGenerator
, nextState
and run
:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: |
|
|
Among the benefits of using a real library, we get shrinking and useful error messages in
case of test failures.
Notice also the added flexibility given by the Check
method: if the state is hard to retrieve,
instead of calling run
and checking the whole state, we are free to focus only on the relevant part of the system.
Model View Update
Instead of discussing how effective the approach is for verification,
let me point out that modeling is valuable at least for documentation:
the nextState
function expresses our understanding of the system.
If you're familiar with the ELM Architecture,
looking at nextState
should ring a bell: just add a view function and you have the MVU pattern!
And the nice thing is that F# allows to use
the same code, both for verification with .NET and for visualization with JavaScript.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: |
|
I think this live documentation aspect is worth exploring.
Final remark
The provided example was not meant to precisely capture the essence of the queue concept. It may be improved and refined to this aim, but I just wanted to describe a small stateful system, with no attempt to define a proper abstraction.
I often praise abstract data types but, quoting Leslie Lamport (via Ron Pressler):
The lesson I learned from the specification work of the early ’80s is that axiomatic specifications don’t work. The idea of specifying a system by writing down all the properties it satisfies seems perfect. We just list what the system must and must not do, and we have a completely abstract specification. It sounds wonderful; it just doesn’t work in practice.
I have to admit we rarely encounter formal ADT specifications besides simple examples and stacks (a quip of Djikstra, according to Bertrand Meyer, is that the purpose of ADT theory is to define stacks).
So, if we leave aside philosophy, we can lower a bit our theoretical pretenses and understand our systems better, embracing the operational paradigm of state machines.
type Queue<'T> = interface IEnumerable<'T> interface IEnumerable interface IReadOnlyCollection<'T> interface ICollection new : unit -> unit + 2 overloads member Clear : unit -> unit member Contains : item: 'T -> bool member CopyTo : array: 'T [] * arrayIndex: int -> unit member Dequeue : unit -> 'T member Enqueue : item: 'T -> unit ...
<summary>Represents a first-in, first-out collection of objects.</summary>
<typeparam name="T">Specifies the type of elements in the queue.</typeparam>
--------------------
System.Collections.Generic.Queue() : System.Collections.Generic.Queue<'T>
System.Collections.Generic.Queue(collection: System.Collections.Generic.IEnumerable<'T>) : System.Collections.Generic.Queue<'T>
System.Collections.Generic.Queue(capacity: int) : System.Collections.Generic.Queue<'T>
val int : value:'T -> int (requires member op_Explicit)
<summary>Converts the argument to signed 32-bit integer. This is a direct conversion for all primitive numeric types. For strings, the input is converted using <c>Int32.Parse()</c> with InvariantCulture settings. Otherwise the operation requires an appropriate static conversion method on the input type.</summary>
<param name="value">The input value.</param>
<returns>The converted int</returns>
--------------------
[<Struct>] type int = int32
<summary>An abbreviation for the CLI type <see cref="T:System.Int32" />.</summary>
<category>Basic Types</category>
--------------------
type int<'Measure> = int
<summary>The type of 32-bit signed integer numbers, annotated with a unit of measure. The unit of measure is erased in compiled code and when values of this type are analyzed using reflection. The type is representationally equivalent to <see cref="T:System.Int32" />.</summary>
<category>Basic Types with Units of Measure</category>
<summary>The type of immutable singly-linked lists. </summary>
<remarks>See the <see cref="T:Microsoft.FSharp.Collections.ListModule" /> module for further operations related to lists. Use the constructors <c>[]</c> and <c>::</c> (infix) to create values of this type, or the notation <c>[1; 2; 3]</c>. Use the values in the <c>List</c> module to manipulate values of this type, or pattern match against the values directly. See also <a href="https://docs.microsoft.com/dotnet/fsharp/language-reference/lists">F# Language Guide - Lists</a>. </remarks>
module List from Microsoft.FSharp.Collections
<summary>Contains operations for working with values of type <see cref="T:Microsoft.FSharp.Collections.list`1" />.</summary>
<namespacedoc><summary>Operations for collections such as lists, arrays, sets, maps and sequences. See also <a href="https://docs.microsoft.com/dotnet/fsharp/language-reference/fsharp-collection-types">F# Collection Types</a> in the F# Language Guide. </summary></namespacedoc>
--------------------
type List<'T> = | ( [] ) | ( :: ) of Head: 'T * Tail: 'T list interface IReadOnlyList<'T> interface IReadOnlyCollection<'T> interface IEnumerable interface IEnumerable<'T> member GetReverseIndex : rank:int * offset:int -> int member GetSlice : startIndex:int option * endIndex:int option -> 'T list static member Cons : head:'T * tail:'T list -> 'T list member Head : 'T member IsEmpty : bool member Item : index:int -> 'T with get ...
<summary>The type of immutable singly-linked lists.</summary>
<remarks>Use the constructors <c>[]</c> and <c>::</c> (infix) to create values of this type, or the notation <c>[1;2;3]</c>. Use the values in the <c>List</c> module to manipulate values of this type, or pattern match against the values directly. </remarks>
<exclude />
<summary>Builds a new list from the given enumerable object.</summary>
<param name="source">The input sequence.</param>
<returns>The list of elements from the sequence.</returns>
<summary>Returns a new list that contains the elements of the first list followed by elements of the second.</summary>
<param name="list1">The first input list.</param>
<param name="list2">The second input list.</param>
<returns>The resulting list.</returns>
<summary>Gets the tail of the list, which is a list containing all the elements of the list, excluding the first element </summary>
<summary>Ignore the passed value. This is often used to throw away results of a computation.</summary>
<param name="value">The value to ignore.</param>
<summary>Negate a logical value. Not True equals False and not False equals True</summary>
<param name="value">The value to negate.</param>
<returns>The result of the negation.</returns>
<summary>Throw a <see cref="T:System.Exception" /> exception.</summary>
<param name="message">The exception message.</param>
<returns>The result value.</returns>
module Gen from FsCheck
<summary> Combinators to build custom random generators for any type. </summary>
--------------------
type Gen<'a> = private | Gen of (int -> StdGen -> 'a) interface IGen member private Map : f:('a -> 'b) -> Gen<'b> static member ( <!> ) : f:('a1 -> 'a2) * a:Gen<'a1> -> Gen<'a2> static member ( <*> ) : f:Gen<('a1 -> 'a2)> * a:Gen<'a1> -> Gen<'a2> static member ( >>= ) : m:Gen<'a1> * k:('a1 -> Gen<'a2>) -> Gen<'a2>
<summary> Generator of a random value, based on a size parameter and a randomly generated int. </summary>
<summary> Apply the function f to the value in the generator, yielding a new generator. </summary>
<summary> Returns a Gen<'Value> </summary>
<summary> Always generate the same instance v. See also fresh. </summary>
<summary>Gets a value indicating if the list contains no entries</summary>
<summary> Build a generator that generates a value from one of the generators in the given non-empty seq, with equal probability. </summary>
<summary> The workflow function for generators, e.g. gen { ... } </summary>
<summary> Generates a list of random length. The maximum length depends on the size parameter. </summary>
<summary> Construct an Arbitrary instance from a generator. Shrink is not supported for this type. </summary>
<summary> Combinators to build properties, which define the property to be tested, with some convenience methods to investigate the generated arguments and any found counter-examples. </summary>
<summary> Quantified property combinator. Provide a custom test data generator to a property. </summary>
static member Check.Quick : name:string * property:'Testable -> unit
type Machine<'Actual,'Model> = new : maxNumberOfCommands:int -> Machine<'Actual,'Model> + 1 overload abstract member Next : 'Model -> Gen<Operation<'Actual,'Model>> abstract member ShrinkOperations : Operation<'Actual,'Model> list -> seq<Operation<'Actual,'Model> list> + 1 overload member MaxNumberOfCommands : int abstract member Setup : Arbitrary<Setup<'Actual,'Model>> override TearDown : TearDown<'Actual> abstract member TearDown : TearDown<'Actual>
<summary> Defines the initial state for actual and model object, and allows to define the generator to use for the next state, based on the model. </summary>
--------------------
new : unit -> Machine<'Actual,'Model>
new : maxNumberOfCommands:int -> Machine<'Actual,'Model>
type Setup<'Actual,'Model> = new : unit -> Setup<'Actual,'Model> abstract member Actual : unit -> 'Actual abstract member Model : unit -> 'Model override ToString : unit -> string
--------------------
new : unit -> Setup<'Actual,'Model>
type Operation<'Actual,'Model> = interface IOperation new : unit -> Operation<'Actual,'Model> abstract member Check : 'Actual * 'Model -> Property abstract member Pre : 'Model -> bool + 1 overload abstract member Run : 'Model -> 'Model
<summary> An operation describes pre and post conditions and the model for a single operation under test. The post-conditions are the invariants that will be checked; when these do not hold the test fails. </summary>
--------------------
new : unit -> Operation<'Actual,'Model>
<summary>Print to a string using the given format.</summary>
<param name="format">The formatter.</param>
<returns>The formatted result.</returns>
<summary> Turn a machine specification into a property. </summary>
type Random = new : unit -> unit + 1 overload member Next : unit -> int + 2 overloads member NextBytes : buffer: byte [] -> unit + 1 overload member NextDouble : unit -> float member Sample : unit -> float
<summary>Represents a pseudo-random number generator, which is an algorithm that produces a sequence of numbers that meet certain statistical requirements for randomness.</summary>
--------------------
System.Random() : System.Random
System.Random(Seed: int) : System.Random
<summary>Gets the total number of elements in all the dimensions of the <see cref="T:System.Array" />.</summary>
<exception cref="T:System.OverflowException">The array is multidimensional and contains more than <see cref="F:System.Int32.MaxValue" /> elements.</exception>
<returns>The total number of elements in all the dimensions of the <see cref="T:System.Array" />; zero if there are no elements in the array.</returns>
<summary> Alias of `ofString` </summary>
val string : value:'T -> string
<summary>Converts the argument to a string using <c>ToString</c>.</summary>
<remarks>For standard integer and floating point values the and any type that implements <c>IFormattable</c><c>ToString</c> conversion uses <c>CultureInfo.InvariantCulture</c>. </remarks>
<param name="value">The input value.</param>
<returns>The converted string.</returns>
--------------------
type string = System.String
<summary>An abbreviation for the CLI type <see cref="T:System.String" />.</summary>
<category>Basic Types</category>
union case HTMLAttr.Action: string -> HTMLAttr
--------------------
type Action = | Enqueue of int | Dequeue
<summary>The type 'unit', which has only one value "()". This value is special and always uses the representation 'null'.</summary>
<category index="1">Basic Types</category>
System.Random.Next(maxValue: int) : int
System.Random.Next(minValue: int, maxValue: int) : int
union case HTMLAttr.List: string -> HTMLAttr
--------------------
module List from Microsoft.FSharp.Collections
<summary>Contains operations for working with values of type <see cref="T:Microsoft.FSharp.Collections.list`1" />.</summary>
<namespacedoc><summary>Operations for collections such as lists, arrays, sets, maps and sequences. See also <a href="https://docs.microsoft.com/dotnet/fsharp/language-reference/fsharp-collection-types">F# Collection Types</a> in the F# Language Guide. </summary></namespacedoc>
--------------------
type List<'T> = | ( [] ) | ( :: ) of Head: 'T * Tail: 'T list interface IReadOnlyList<'T> interface IReadOnlyCollection<'T> interface IEnumerable interface IEnumerable<'T> member GetReverseIndex : rank:int * offset:int -> int member GetSlice : startIndex:int option * endIndex:int option -> 'T list static member Cons : head:'T * tail:'T list -> 'T list member Head : 'T member IsEmpty : bool member Item : index:int -> 'T with get ...
<summary>The type of immutable singly-linked lists.</summary>
<remarks>Use the constructors <c>[]</c> and <c>::</c> (infix) to create values of this type, or the notation <c>[1;2;3]</c>. Use the values in the <c>List</c> module to manipulate values of this type, or pattern match against the values directly. </remarks>
<exclude />
<summary>Returns a new list with the elements in reverse order.</summary>
<param name="list">The input list.</param>
<returns>The reversed list.</returns>
<summary>Builds a new collection whose elements are the results of applying the given function to each of the elements of the collection.</summary>
<param name="mapping">The function to transform elements from the input list.</param>
<param name="list">The input list.</param>
<returns>The list of transformed elements.</returns>
module Program from Elmish.React
--------------------
module Program from Elmish
<summary> Program module - functions to manipulate program instances </summary>
--------------------
type Program<'arg,'model,'msg,'view> = private { init: 'arg -> 'model * Cmd<'msg> update: 'msg -> 'model -> 'model * Cmd<'msg> subscribe: 'model -> Cmd<'msg> view: 'model -> Dispatch<'msg> -> 'view setState: 'model -> Dispatch<'msg> -> unit onError: string * exn -> unit syncDispatch: Dispatch<'msg> -> Dispatch<'msg> }
<summary> Program type captures various aspects of program behavior </summary>
<summary> Simple program that produces only new state with `init` and `update`. </summary>
<summary> Renders React root component inside html element identified by placeholderId. New renders are triggered immediately after an update. </summary>
<summary> Start the dispatch loop with `unit` for the init() function. </summary>