Exhaustive Tests

By exhaustive tests, I mean run tests with all possible combination
(not permutation for now!) of inputs. Here's the story. I was writing
ripl plugin collections, called ripl-rc. Plugins approach is good for
flexibility, but might fail to be fragile, that is only a small subset of
plugins combination would work correctly, others might be buggy.

It would be even harder for not only combination, but also permutation,
and by using Ruby's module system, we got this by nature.

I keep wondering how should I test those behaviour, and now I've
implemented it in rib, the successor of ripl-rc, a fork from ripl.
I would back port some of the enhancement to ripl-rc if one wants.
But if no one is really using it except me, then I might not develop
it further. Let me know if you need it.

So here's some interesting numbers.

My original tests report:

73 tests, 219 assertions, 0 failures, 0 errors

Not many tests, I admit. I am too lazy to write them.
But I can get "free" tests by running different plugins combination:
combination of 1:

493 tests, 1309 assertions, 0 failures, 0 errors

By combination of 1, I mean for each test, beside the testing
plugin, one additional unrelated plugin would also be enabled.
combination of 2:

2032 tests, 4880 assertions, 0 failures, 0 errors

By combination of 2, I mean for each test, beside the testing
plugin, two additional unrelated plugins would also be enabled.

So the complexity of combination of 1 test would be O(n),
n is the number of plugins. The complexity of combination of 2
test would be O( C(n, 2) ).

The most fun one would be... what about all combinations?
It would be O(2^n)!!!

I haven't succeeded to run this exhaustive test... It took over
an hour to run it, and the top blocker was rr I doubt. RR was getting
slower and slower after running thousands of thousands of tests.
Bond would also get slower and slower, but it's easy to turn it off.
Just only start bond once and never restart it. But I can do nothing
about rr, I need it to run the tests.

I think the problem is that the memory footprint would grow into 1G.
The bottleneck then might be GC or memory allocation or something.
There might have some memory leak or bad design for extensive runs.

I tried to write a lightweight replacement for rr, but then realized the
problem is still harder than my imagination. I need some more time to
write one to suit all my needs.

Since I have too many things to do recently, I'll just leave it alone
for a while. At least after rubyconf.tw/2011, I guess.

I really want to see something like:

999999 tests, 99999999 assertions, 0 failures, 0 errors

Should be fun....

Also, actually by running combination of 1, I did find some bugs.
So I believe this is the right path to go with... for correctness.
Running exhaustive tests is still easier than proofing my program. :P

p.s. here's how I wrote the O(2^n) exhaustive test:

def test_level3 plugins, block
  return block.call if plugins.empty?
  plugins[0].enable
  test_level3(plugins[1..-1], block)
  plugins[0].disable
  test_level3(plugins[1..-1], block)
end