An interesting idea that Daniel Wagner, Vilhelm Sjöberg and I just came up with: a minimal test case generator. Here’s the idea: you have a program which exhibits error X, which you want to understand better; or perhaps you suspect it is a bug in the compiler, and you want to submit a test case along with your bug report. As input to the minimal test case generator, you give your program along with some sort of description of error X. It then tries to shrink your program as much as possible while still exhibiting error X. Of course, doing the shrinking would be nontrivial: you’d have to parse the program and do some sort of call graph analysis, and then only delete leaves in the call graph. But, of course, tools for analyzing call graphs already exist.
How difficult would this be to develop? Does anything like this already exist?
Sounds like a special case of QuickCheck’s shrinking — where the random test data are “random” ASTs.
Not sure there’s anything that looks at call graphs, but see e.g. http://delta.tigris.org/ for more general stuff in this area.
Another interesting tool would be one that creates minimal test cases, but not necessarily trimming the code, but simplifying the test input. This would probably be harder than trimming the call graph since it would require domain knowledge of the test cases. Is it possible to have a test case generator (like QuickCheck) or use Generics to create test cases that can be automatically reduced?
LLVM has the bugpoint utility for reducing test cases that exhibit errors in IR transformations or code generation. It’s meant to be amazingly effective.
This idea reminds me of SmallCheck (Runciman, Naylor, and Lindblad, Haskell 2008). But in your case, if it is easy to *check* whether any given program is a test case that exhibits the error, then perhaps it is practical to just try deleting each substring of the initial test case (which takes quadratic time) repeatedly (which takes cubic time)?
Sounds like delta debugging, see http://www.st.cs.uni-saarland.de/dd/
The original version of QuickCheck, for Erlang, was written by John Hughes. He founded QuviQ (http://quviq.com/) to sell the Erlang QuickCheck, which does simplification on the test input.
IIUC, QuickCheck-2 already does what Jared said. Look at the documentation for the Arbitrary class. There is a shrink function that returns a list of “smaller” versions of a value. It checks if any of the shrinks also fail the test and iterates to a fixed point.
Of course, you don’t get this for free with generics, but Arbitrary instances are pretty easy to write.
In the case of a single threaded programm, it should be possible to use coverage tools. If your program terminates abruptly at the error, but coverage information is still written, the the code coverage tells you exactly which code was executed and which not. Just a simple idea.