Repository files navigation

Property-based testing (PBT), i.e. generating random inputs and checking someproperty of the output, of pure programs is an established practice by now. It'staught in introductory university classes and it's part of test suites inindustry.

Most real world programs are not pure though, they are stateful. While it'soften possible to structure your program in such a way that the impure stuff isdone inmain, e.g. read the contents of a file, and then passed on to a purefunction, e.g. a parser, it's not always possible. Consider a long-runningprogram that interacts with the filesystem and with other programs over thenetwork, e.g. some kind of web service or a distributed database. It's difficultto split such a program up into doing a little bit of impure stuff at the start,then hand it over to a pure function (which we can apply PBT on).

Given this it's perhaps a bit surprising that there are relatively few resourcesabout applying PBT to stateful systems. This repository is an attempt to closethat gap and try to make PBT stateful systems more common.

The goals we'd like to achieve are:

• Show how to test stateful (i.e. impure/monadic) programs usingproperty-based testing;

• Show how we can do concurrent testing to help uncover problems such as raceconditions;

• Show how we can build bigger systems in a modular way by applying theproperty-based testing equivalent of integration and contract tests;

• Show how to use fault injection and so called simulation testing to"end-to-end" test distributed systems;

• Introduce the reader to related work and open problems in the area along theway.

In the interest of brevity, we assume that the reader already has:

• Enough familiarity with Haskell to be able to read simple programs, forexample if you can follow along in theLearn You a Haskell for Great Good!tutorial, then you should be fine;

• Some experience with property-based testing of non-stateful (i.e. pure)programs. For example as explained in the official QuickCheckmanual or in thefollowingtutorial;

• Basic knowledge of state machines (i.e.Mealy /Mooremachines andtransducers).

Other than that this tutorial is striving to be as self-contained as possibly aswell as accessible to non-Haskell programmers.

The tutorial is split up into five parts (so far), and each part has thefollowing structure:

• Motivation: explains why we are doing what we are about to do;
• Plan: how we will do it;
• Code: a concrete implementation of the idea (in case you get stuck when tryingto implement it yourself);
• Discussion: common questions or objections;
• Exercises: things the authors were to lazy to do, but they know how to;
• Problems: things the authors don't know how to do (yet);
• See also: links to further reading about the topic or related topics;
• Summary: the most important take away.

The parts build upon each other. We start by modelling and testing a simplecounter using a state machine in part 1, we then reuse the same state machinemodel to test the counter for thread-safety using linearisability in part 2. Inpart 3 we will implement a queue and a web service that uses said queue, thestate machine model for the queue and the real implementation of the queue willbe contract tested to ensure that the model is faithful to the implementation,subsequently while testing the web service we will use the model in place of thereal queue. In part 4 we introduce fault injection to the queue allowing us totest how the web service performs when its dependency fails. Finally, in part 5,we combine all the above ideas in what, sometimes is called simulation testing,to test a distributed system that uses replicated state machines.

1. State machine testing
2. Concurrent state machine testing withlinearisability
3. Integration tests against state machine fakes and consumer-driven contracttests for the fakes
4. Fault-injection
5. Simulation testing

This repository contains literate Haskell code insrc. If you want to interactwith it, installghcup and then typecabal repl. Alternatively, if you are using thenix package manager, then runningnix-shell in the root directory should give you the rightghc version andall other dependencies you might need.

The literate code is transformed into markdown usingpandoc intools/generate_markdown.sh and the markdown isput inside thedocs directory for easier browsing.

The following is a link to thefirst part of thegenerate markdown, at the end it will link to the second part and so on. Or youcan use the table of contents above or thedocs directory to jump to desiredpart straight away.

Any feedback, suggestions for improvement or questions are most welcome via theissue tracker!

See theCONTRIBUTING.md file for more detailedguidelines regarding contributing.

See theLICENSE file.