If you have been following Lintian’s development closely, you will probably have noticed that I have not really done anything there for the past week. Instead I have turned my focus on our testing migration script, britney2. First, I have created a minimal test suite. It started as 4 simple tests and by now it contains about 30 tests.
The size of each test is rather small; the largest tests are about 1600 binary packages in total, but most are 2-20 binary packages in total. Thus the test suite is rather fast compared to a “live data sample”, which easily takes more than 10 minutes for a single run. Unfortunately, hand-crafting the test data is somewhat annoying and easy to get wrong.
The test suite has a somewhat unfair focus on “auto-hint” cases, so the current britney2 fails up to 14 tests. Some of these appears to fail because the auto-hinter (for some reason) receives incomplete information about the situation. To my knowledge we not been able to debug the situation, but Adam has a refactor branch that does not seem to have this issue. Personally I am hoping it will soon be merged into the master branch, especially because it seems to simplify a lot of common operations.
Joachim Breitner (who has been working on a SAT-solver based britney) also contributed a couple of test cases. Allegedly, SAT-britney does rather well on the test suite, failing only 2 tests as far as I can tell. On the other hand, it does solve a some of the more interesting cases britney2 does not solve.
On a more mathematical note, the britney2 implementation behaves like a function with an attractive fixed point. This is interesting, because for some cases it may take britney2 a couple of iterations to reach the right solution. This fixed point is somewhat simple to find by using the following steps (pseudo-code):
// Runtime complexity O(n * br * diff), where "n" is the number of iterations until
// a fixed point is reached, "br" is the complexity of "run_britney" and "diff" is
// the runtime of the "last != current" comparison.
last = run_britney(initial)
current = run_britney(last)
while last != current ; do
last = current
current = run_britney(last)
This gives us a simple way to test if britney will eventually solve the issue herself (and when she will do it). Currently britney2 is automatically run twice a day, so for every 2 iterations (beyond the first) roughly translates to a 24-hours delay. So far the test suite does not have a lot of problems that requires more than one iteration. Personally I would be pleased if it turned out to stay that way as the test suite coverage grows.
If you are interested in playing around with this, you can get sources from:
- Currently only works in stable (i.e. requires python2.5 and python-apt < 0.8 or so)
- See the INSTALL file for instructions
- Adam’s branch
- I haven’t tested this one and I do not know the requirements here
- See the README file for instructions
 These tests are auto-generated, so it is merely an “up-scaled pattern”.
 Basically if two (or more) packages needs to migrate into testing at the exact same time, they need to be hinted in.
 Not to mention all the copy-waste errors he pointed out in mine. Apparently, SAT-britney has stricter requirements to the data than britney2. :P
 I assume the test called “sat-britney-death” (created by Joachim) was named that way for a reason. The second failure is caused by SAT britney not reading hints (yet?), so the “approve tpu package” test case should fail.
 A function that maps an “archive” into another “archive”… erh, I mean, it maps a set of packages into another set of packages… :P
Assuming my claim to be true, the function will have more than one fixed point. The obtained fixed point depends on the initial state of testing.
As an example:
– y depends on x
– x in testing has RC bugs
If x is not in testing, it cannot migrate to testing (due to its RC bugs). If x is not in testing, then y cannot migrate into testing. But if x starts in testing, then y may be able to migrate. This can happen if x migrated to testing before an RC bug was filed against it.
(Dis-)Proving my claim is an exercise left for the reader.