[Kdiff3-user] Large set of testdata for alignmenttest

[Maurice v. d. P. <gri...@kf...>]

Hi Joachim and others,

tl;dr: I'm asking for some ideas on how to get a good test set for
the diff/alignment algorithm of kdiff3.

A while ago I wrote the alignmenttest in the test directory. This test
checks how kdiff3 arranges the lines of 3 files in a three-way
diff/merge, so which parts of the file it decides to put next to
each other.

This is a test that can be useful for catching regressions when making
changes to the alignment algorithm, but only if there is a large enough
test set available.

I've been thinking about how to create such a test set, but would like
to gather some feedback.

I can think of a few ways to create such a set:
1) manually create test cases based on the decisions that kdiff3 makes
   throughout this algorithm
   Disadvantage: this is a lot of work. Also it is not easy to construct
   input and expected output that will trigger a specified outcome of a
   decision that is made on an intermediate representation in the code
2) compose it from merges that showed problems in kdiff3's behaviour.
   Disadvantage: it takes a *looooong* time before you get decent
   coverage
3) generate test data systematically
   Disadvantage: the data set gets big really quickly if you cover all
   possible combinations of lines, even for small fragments
4) generate test data from real-life merges
   Disadvantage: the data gets big even more quickly than with 3,
   because there is a lot of overlap in which merged file tests which
   behaviour of kdiff3 and each file contains many lines that are
   irrelevant to the test

The first problem with large test sets is that you will not want to
check them in and distribute them with the source code of kdiff3.
The second is that a change in the algorithm likely affects a *lot* of
test cases, so you'll spend a lot of time looking through the test cases
that have started failing to see if the new behaviour is better than the
old.

However, I do think there's still value in 3, where the effort of
investigating new failures is much lower per test case than with 4. The
'input' data can be generated with a simple script. The 'expected output'
must be generated with the alignmenttest executable of a "known good"
kdiff3 version.

Can anyone come up with better/alternative ideas for creating test data?

Regards,
Maurice.

P.S.: I have scripts for 3 and 4, so if anyone wants them just ask. The
script for 4 finds merge commits in an arbitrary git repository (I used
the linux kernel repo), gets the files that were merged in these commits
and saves them to a format suitable for the alignmenttest.

-- 
Maurice van der Pot

Gnome Planner Developer  gri...@kf...  http://live.gnome.org/Planner