Using Lithium

Lithium is an automated testcase reduction tool developed by Jesse Ruderman.

Most of what you need to know to use Lithium is in one of these pages:

Lithium's algorithm

By default, Lithium uses a clever algorithm that's efficient at reducing most large testcases. For a testcase with 2048 lines, it will try removing each chunk of size 1024, permanently removing it if it is still 'interesting'. It then does the same for each chunk of size 512, then 256, all the way down to chunks of size 1. It then does as many additional rounds at chunk size 1 as necessary until it completes a round without removing anything, at which point the file is 1-minimal (removing any single line from the file makes it 'uninteresting').

If n is the size of the testcase and m is the size of the 1-minimal testcase found by Lithium, then Lithium usually performs O(m ⋅ lg(n)) tests with a total test size of O(m ⋅ n). See the analysis of Lithium's algorithm for more information and proofs.

To keep m small, make sure Lithium's smallest removals won't introduce fatal syntax errors into the file it is trying to reduce. For example, don't use --char when trying to reduce a long sequence of JavaScript statements, and don't feed XHTML to Lithium. (Convert it to HTML first and let Firefox's tag-soup parser sort out the invalidity, or use serializeDOMAsScript.)

Command line syntax

    ./lithium.py [options] interestingness-test.py [arguments for interestingness test]

Command line options

--testcase=filename
Tells Lithium which file to reduce. By default, it will assume the last argument to the interestingness test is the file to reduce.
--char (-c)
By default, Lithium treats lines as atomic units. This is great if each line is a JavaScript statement, but sometimes you want to go further. Use this option to tell Lithium to treat the file as a sequence of characters instead of a sequence of lines.
--strategy=[minimize, remove-pair, remove-substring]
"minimize" is the default, the algorithm described above. "remove-pair" tries to find a pair of lines in the file that can both be removed. "remove-substring" tries to find a substring of the file that can be removed. "remove-pair" and "remove-substring" are O(n2), so you probably won't want to use them very often, and you'll only want to use them after using "minimize".
--repeat=[always, last, never].
By default, Lithium only repeats at the same chunk size if it just finished the last round (e.g. chunk size 1). You can use --repeat=always to tell it to repeat any chunk size if something was removed during the round, which can be useful for non-deterministic testcases or non-monotonic situations. You can use --repeat=never to tell it to exit immediately after a single round at the last chunk size, which can save a little time at the risk of leaving a little bit extra in the file.
--max=n. default: about half of the file.
--min=n. default: 1.
What chunk sizes to test. Must be powers of two. --max is useful if you're restarting Lithium after it has already gone through a few rounds. --min is useful if you're reducing HTML and want to do the final by hand.
--chunksize=n
Shortcut for "repeat=never, min=n, max=n". --chunksize=1 is a quick way to determine whether a file is 1-minimal, for example after making a change that you think might make some lines unnecessary.

Hints

If you find a non-deterministic bug, don't despair. Lithium will do fine as long as you make the bug happen at least 70% of the time. You can repeat the test either within the application, by adding a loop or reload in the testcase (outside of the DDBEGIN/DDEND markers!), or outside of the application, by adding a loop to the "interestingness test" script.

Requirements

Lithium is written in Python and requires Python 2.4. (It uses generator expressions and the subprocess module, both of which were introduced with Python 2.4)

Various versions of Lithium have been used successfully with:

It is known to not work well in MSYS, an alternative to Cygwin. I've seen Lithium sorta work in MSYS after adding add ", shell=True" to the call to "subprocess.call" removing the "./" before the test filename, but even then it was buggy. I recommend using Cygwin's Python instead.

Credits