Stack based automatic testcase generation
Testmachine is a new way of testing.
The core concept is that testmachine doesn’t generate data, it generates programs. These programs are composed of three things which you provide:
- Rules for generating values (like an Arbitrary in quickcheck)
- Assertions about values (like a Property in quickcheck)
- Rules for combining values (this is hard to do in quickcheck)
Testmachine takes these rules and attempts to find a combination of them which will produce an exception. If it finds one it then does its best to minimize it and compiles the final output into a simple SSA text format that will usually be interpretable as valid python (it’s generated by simple string expansion from patterns. If your values have reprs which are valid python and you don’t do anything too unusual then the output will be valid python. Otherwise it may take some editing but should be readable on its own).
There are some examples how to use it in the examples directory.
This code should be considered pretty experimental right now. You can use it and it will probably work, but I make no promises about the API being stable. It’s very much still a work in progress as I explore a new idea.
How does it work?
At its core, a Testmachine describes a language of programs that can be executed. These programs define execution on a machine with multiple named stacks. This language is a set of rules for generating operations on this stack machine.
A run of a testmachine performs a sequence of these operations. Each of these may read stacks, pop values off stacks, push values onto stacks, etc. If any of these operations throws an exception, testmachine has now found a bug.
Because of its definition in terms of stack operations it’s very easy to then minimize the program: A program is just a list of operations with no explicit dependencies between them. So you can just delete instructions from it, then remove any instructions which find themselves in an invalid state (e.g. if not enough values are on the stacks they need) and see if the program still fails. Most of the time this produces a substantially smaller program.
Once we have a minimal testmachine program we then compile it to remove the stacks. We do this by maintaining a set of shadow stacks with variable names, one for each of stacks in our machine. By tracking which variables are read and written in an operation we convert the stack operations into a set of variable reads and writes.