Contents
delta
delta in an implementation of an algorithm for automatically minimizing the input which causes a failure. As distributed, it works well for finding bugs in programs which consume C/C++ code (such as finding bugs in a compiler like gcc).
With some fairly simple modifications, it can be used to minimize SDL code which exhibits a bug in the Vesta evaluator.
(This page doesn't really describe delta or how it works. Refer to its home page for more information about it.)
Modifications for SDL
There are two key midifications I made to delta to get it working well for SDL, described below.
A patch for these two changes is attached to this page: delta-vesta-sdl.patch
Also attached here is the version of delat which the patch is relative to (in case if becomes unavailable elsewhere): delta-2005.09.13.tar.gz
topformlat and bindings
delta includes a filter called topformflat which suppress any newlines past a particular nesting depth. This groups large blocks of the file into single lines, making it easier for the algorithm to discard unecessary pieces with large granularity.
For C/C++ the nesting is just curly braces ("{" and "}"). For SDL, it makes sense to also include the nesting of binding literals, which use suare brakcets ("[" and "]"). This requires a small modification to the lex file which defines the filter.
multidelta and cpp
The multidelta script passes the input through the C pre-processor before passing it to topformflat. For SDL this is a problem as it will remove the pragmas which affect caching. These can be crucial to reproducing a subtle bug, so I simply removed the use of the C pre-processor.
It would be a good idea to replace this with a different filter which stripped out all non-pragma comments. However, it's not really necessary as the delta algorithm will wind up dropping the unecessary comment lines (albeit reather inefficiently).
Start with -level=1
When running multidelta on a file of Vesta SDL, start with "-level=1" rather than "-level=0". SDL files always have an outer set of curly braces for the model body, so using "-level=0" would collapse the entire body to a single line, which wouldn't be any use.
Test Script
In order for delta to determine whether a given candidate input exhibits a failure, it must be given a script which tests for the presence of the desired result (usually a specific error message or otherwise detectable problem).
Caching effects can be an issue with reproducing evaluator bugs. Some will only occur against an empty cache. For this reason you may want your testing script to run its own cache server and start with an empty cache at the beginning of each test.
Here's an example testing script which was used in minimizing the reproducer for a bug which was fixed in eval/77: example-test.pl
Of course this example may not be appropriate in your case, for any one of several reasons:
- You may not want to start from an empty cache on each run, especially if the error only occurs after a large amount of work which can be cached.
- The SDL files to minimize could be split across several packages, so you might need to have the test script:
Example Command Lines
Suppose you have a reproducer made up of two SDL files named "foo.ves" and "bar.ves" with one importing the other. Suppose your test script is called "test.pl". Here's how you might run multidelta on these file:
multidelta -level=1 ./test.pl foo.ves multidelta -level=2 ./test.pl foo.ves multidelta -level=3 ./test.pl foo.ves ...possibly more levels... multidelta -level=1 ./test.pl bar.ves multidelta -level=2 ./test.pl bar.ves multidelta -level=3 ./test.pl bar.ves ...possibly more levels...
After this, you might then want to start over with another few multidelta runs, as the work done on one file might enable further minimization of the other.
You might also want to go through and do some cleanup by hand, possibly deleting more dead code, using the test script to make sure it's still exhibiting the failure. This can sometimes make reductions which delta cannot perform on its own and even enable further multidelta runs to make additional minimization progress.
Delete the Session Directory when Done
When using delta with a Vesta build, it will generate a large number of individual snapshots as it tries various experiments. Most of these will be syntactically incorrect or otherwise uninteresting. (In fact, probably the only interesting one is the final minimized one.) You chould be prepared to ghost (i.e. with vrm) the session directory in which all the delta experiments are saved as snapshots.
Sample Results
One reproducer minimized with delta can be found in the evaluator package:
/vesta/vestasys.org/vesta/eval/79/src/tests/fixed_bugs/pickled_path_bug
This started out as an import tree of 8 models with 1319 lines total (717 lines in the 3 local ones). delta did most of the work of minimizing it, including eliminating all of the imports to get it down to just those three files. Some hand editing was done in-between steps as well as at the end. (Hand editing in the middle can help delta make further progress.) Excluding comments, the result is 59 lines of SDL.