Delta: the coolest tool you've never heard of

One of the challenges that any developer faces is finding a small test case that reproduces a defect reported by users. That's often easier said than done: when the defect originally shows up during parsing of a makefile consisting of 20,000 lines of nested calls to $(eval), separating the interesting lines from the irrelevant lines can seem like an exercise in futility. Thankfully, you don't have to do it alone. Some clever guys at UC Berkeley wrote a tool called delta to assist with just this problem. In this post I'll show you how you can use delta to distill useful test cases out of otherwise intractable inputs. The example involves makefiles of course, but the tool and the techniques are useful to developers and QA engineers in all fields.

Delta isolates the interesting portions of an input file by iteratively partitioning the input, then testing each partition to see if it produces the behavior you want. If any partition does, the other partitions can be discarded. After numerous rounds of this, the uninteresting chaff is eliminated and you are left with an input file containing only those parts of the original that are really necessary. Conceptually it's like doing a binary search on the input, although it's more clever than that because it handles the case where the interesting lines are not strictly contiguous in the input.

--- START JOB (3.80) Compiling foo.bar with flags -fbase -ffoo --- FINISH JOB

Compare that to the output when using gmake 3.81:

--- START JOB (3.81) Compiling foo.bar with flags -fbase -ffoo -fbar --- FINISH JOB

I've highlighted the difference to make it easier to see: the flags used to build the target have changed.

The next step is to write a shell script that will tell delta if a given permutation of the makefile produces the behavior we want or not. Technically you could use any kind of program you want here as long as it adheres to delta's convention of returning zero if the input is "interesting" and non-zero otherwise; shell scripts are just an easy way to do it. Here's the script I wrote for this example:

#!/bin/sh if gmake-3.80 | fgrep "flags -fbase -ffoo" > /dev/null ; then if gmake-3.81 | fgrep "flags -fbase -ffoo -fbar" > /dev/null ; then exit 0 fi fi exit 1

The script runs gmake 3.80 and gmake 3.81, checking the output of each to verify that the flags are printed and that they have the expected values. I named the script check.sh and made it executable with chmod , then ran it once to ensure it does in fact return zero as expected:

$ ./check.sh $ echo $? 0

If you haven't already, download delta (.tar.gz) and unpack it. Delta itself is a Perl script, so make sure you have Perl installed. Now we're ready to go.

Delta will modify the input file in place, so make sure to save a backup copy first, and then run delta, telling it the name of the check script and the input file to minimize:

$ cp Makefile Makefile.orig $ delta -in_place -test=./check.sh Makefile

This will produce a boatload of output like this:

SUCCESS, lines: 1851 **************** gmake-3.80: *** No rule to make target `foo.bar'. Stop. Increase granularity Before 0 After 0 1 Makefile:3: *** commands commence before first target. Stop. ...

Generally you can ignore this output, but it's worth looking at once just to get a better understanding of what delta is doing. The output log tells you the partitions that delta tries, expressed as ranges of lines from the original input. The first test is on the full input, ; next delta splits the file in two and tries each half, and . You can see sometimes these partitions result in a completely broken makefile -- syntax errors, missing rules, etc. Delta doesn't care -- all it needs to know is whether or not the partition is "interesting" according to our check.sh script. Looking further on in the output, you can see how the test makefile gets smaller and smaller as delta discovers ranges of the original input that are relevant. Eventually it ends up with trials like , indicating that it has constructed a makefile from lines 3-7, 93-96, 198-202, etc, of the original input. Finally delta hits a point where it cannot reduce the input any further -- if it removes anything more, the resulting makefile is no longer interesting:

Could not increase granularity; we are done. A log of successful runs is in log delta done

On my laptop, delta takes all of about two seconds to trim the original makefile, consisting of nearly 2,000 lines of text, to a trivial 15 line makefile. Not too shabby.

Depending on your situation, you may find that delta stops too soon. It's strength is also its weakness: it is not at all domain aware. It doesn't understand the syntax of makefiles or whatever else you might throw at it, so sometimes it hits a dead end. You may be able to help it along a bit by applying your own domain knowledge to the problem at that point. That is, once delta has had a first crack at the input, take a look at it yourself and see if there are ways you can simplify the input manually. When dealing with makefiles, that could mean doing things like inlining makefile includes, or flattening nested variable definitions. After you tweak the input manually, you can feed it back into delta again for another round.

I've used delta myself on several occasions to help pull simple test cases out of seemingly intractable makefiles. It's not perfect, but it's earned a place in my toolbox. Hopefully you'll find room for it in yours.

UPDATE : changed URL of the sample Makefile.