Re: [PATCH] xdiff: add xdl_merge()

Hi Johannes,

Johannes Schindelin wrote:

This new function implements the functionality of RCS merge, but
in-memory. It returns < 0 on error, otherwise the number of conflicts.

I had a similar idea (removing the RCS dependency) and, about two months
ago, implemented a git-diff3 that used the internal xdiff library.
Unfortunately, I then got distracted by other things and left this as a
WIP, without posting it to the list. [I had an email exchange with Junio
about it, but then dropped the ball - sorry Junio!]

Finding the conflicting lines can be a very expensive task. You can
control the eagerness of this algorithm:

- a level value of 0 means that all overlapping changes are treated
  as conflicts,
- a value of 1 means that if the overlapping changes are identical,
  it is not treated as a conflict.
- If you set level to 2, overlapping changes will be analyzed, so that
  almost identical changes will not result in huge conflicts. Rather,
  only the conflicting lines will be shown inside conflict markers.

With each increasing level, the algorithm gets slower, but more accurate.
Note that the code for level 2 depends on the simple definition of
mmfile_t specific to git, and therefore it will be harder to port that
to LibXDiff.

Erm, I guess I need to read the code! I haven't had an opportunity to
do that yet, but I hope to have time at the weekend.

	My hopes are that when I wake up in the morning, all bugs are
	fixed, git-merge-one-file is rewritten as a builtin,
	git-merge-index defaults to calling xdl_merge() directly when
	no program is passed with "-o", and git-merge-recursive also
	avoids fork()ing RCS' merge.

Yep, I had a similar todo list.

	A funny side effect is that you can merge with white space
	corruption by setting the xpparam flags to ignore whitespace.
	The file passed as mf1 wins over mf2 in that case.

Yes, I had this on my todo list. In fact you can already try it out
by using --diff-program="diff -wb" (which uses the external diff).
[To be fair, you can also write an obvious script and use GNU diff3]

 Makefile       |    3 
 xdiff/xdiff.h  |    7 +
 xdiff/xdiffi.c |    3 
 xdiff/xdiffi.h |    1 
 xdiff/xmerge.c |  433 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 444 insertions(+), 3 deletions(-)

 From the above, I would guess that your code integrates well with the
xdiff library and, as a result, would be more memory efficient than my
code. I had considered doing this, but I wanted to support an external
diff option, so it was easier to implement the diff3 algorithm outside
the library, treating it just like an external diff (that I didn't need
to fork()/exec()). Also, I didn't need to understand the xdiff code, I
just treat it as a black box (and I'm lazy!).

[Having an external diff option was actually a debugging aid to ensure
that the main diff3 algorithm was implemented correctly. In the end I
didn't use it for debugging anyway!]

[snip patch]

I have attached a version of my patch, against v1.4.2, just for the
interested. Also it contains some tests which I found very helpful
in squashing bugs, so you might like to give them a try with your code.

Note: the fact that the patch is against v1.4.2 should not cause too
much of a problem, since it is mostly new files and the changes to
Makefile, builtin.h and git.c you could probably do in your sleep.

[Junio, this is almost exactly the same patch I sent you last time,
modulo some minor code clean-up/formatting]

All the best,

Ramsay