[darcs-devel] new test case generator

[Ben Franksen]

Hi Ganesh

Whatever was the motivation for TreeWithFlattenPos, we have a more
serious problem.

I have converted all the generic tests to use arbitrarySequence. I also
use this now to test the V3 repo properties. Sadly, this gives me a
failure with the following sequence of 4 patches: A) a hunk, B) a
conflicting hunk, C) a replace, and D) a conflicting hunk that conflicts
(only) with the previous conflictor B. This is exactly the kind of
situation that we never tested before.

The failure is that the conflictor B that the last patch conflicts with
cannot be commuted past the replace C (which D does not conflict with).
Conflict resolution relies on being able to do that, and when I designed
it, I actually thought about this scenario. My conclusion was that the
merge algorithm should make it impossible: if we have B;C;D and D
conflicts with B and C depends on B, then D must also conflict with C. I
still think that this should always hold and the fact that it doesn't is
a bug. But I am not excluding the possibility that the law simply
doesn't hold, which means I have to rethink the algorithm for conflict
resolution.

This is not the only problem, however.

When I converted the merge properties I thought I should be more
demanding and actually test the merge properties with sequences instead
of just single patches. So the generator for forking pairs now creates
two arbitrary sequences (which themselves could contain conflicts)
starting in the same state. This regularly gives me failures with V2 and
V3 when I crank up the number of tests (-q=2000 completes reasonably
fast on my machine). For instance I just had a failure of "nontrivial
merge either way" with RepoPatchV3 over Prim.V1 (which is what I am
concentrating on now). Unfortunately the test case is so complicated
that analyzing it manually is almost impossible.

This is all rather frustrating. Debugging this stuff is dreadfully hard.
I am beginning to see why Ian wanted to actually prove properties...

We really need shrinking. I think I'll just start implementing it for
the new generators.

We also need to design and implement a simple non-trivial prim patch
type for testing RepoPatches. Our existing prims are not well suited:
the may be useful for real version control but they make failing test
cases unnecessarily complex. With non-trivial I mean that such prims
should have a reasonable probability of not commuting with each other;
that commuting them may change their representation (so not all commutes
are trivial); and that they are complete in the sense that any state can
be reached from any other state via some sequence of prims. And with
simple I mean that the Show instance for the state as well as the
patches fits on a single line and that it should be possible to see at a
glance whether two of them commute. If the state space is small enough
this may even enable us to do exhaustive instead of random testing,
which in turn would allows us to profit from tools that fully automate
shrinking (leancheck).

(Here is a rough idea: as state we take a finite sequence of small
"words", say in the range 0..15, so presentable as a hex char. Prim
patches either remove a word at some position or add one, commuting if
they touch the same position, quite similar to hunks. If we drop the
requirement for non-trivial commutes (not sure if that is essential), we
could even use a fixed length sequence and let prims change the word at
some position without adding or removing words. With a length of 3 we'd
have a probability of 1/3 that patches don't commute; and the state
space would be 16^3=2^12=4096; if that seems too small, use one more bit
for the wordsize i.e. 0..31.)

> I remember that Ian had a good example of a tricky case to handle in an> conflict representation. Something like 6 patches A, B, C, D, E, F;>
where A B and C all merge cleanly, and D depends on B+C, E on A+C, F o>
A+B, and there are conflicts between D E and F. It's probably already
in> the existing tests somewhere, and probably needs to be a single
test> case rather than something that can be made with QuickCheck.
Thanks. I don't think this is our test code. I will try to find it in
the camp code and adapt.

Sigh
Ben