Re: Looking for diff4

[Paul Eggert]

Stuart Ballard <address@hidden> writes:

> Trunk  -- t1 -- t2 ------------ t3
>              \      \               \
> Branch       '- b1 -(m1)- b2 -- b3 -(m2)- b4
> ...
> m2, on the other hand, cannot be done adequately with diff3. The reason
> is that the 'common ancestor' file has already diverged - on the trunk
> it's t2, and on the branch it's b2.

Sorry, I don't get it.  From your diagram it appears that t2 is an
ancestor of both t3 and b3.  So m2 can computed by invoking "diff3 b3
t2 t3".

> Unfortunately I'm not familiar with how the diff3 algorithm actually
> works

It's not described outside the code, as far as I know.

> 2) Given diff3 a b c, calculate diff b a and diff b c, then combine the
> two diffs (resolving conflicts at this point) and apply the resulting
> patch to a.

Yes, that's what it does.

> If diff3 takes this approach, I can see a potential way to extend
> it into diff4

How about this idea instead:

"diff A B" currently finds a longest common subsequence between A and
B, and reports everything outside this common subsequence as a
difference.  (Actually, it sometimes finds a subsequence that is not
the longest, for efficiency reasons, but if you use the -d option it
goes ahead and does find a longest one.)

"diff3 A B C" could find a longest common subsequence among A, B, and C,
and report everything outside this common subsequence as a difference.
It doesn't do that now; it uses algorithm (2) you mentioned above.
But it _could_ do that, and that would be better than what it does now.

"diff4 A B C D" could find a longest commong subsequence among A, B,
C, and D, and report everything outside this common subsequence as a
difference.

etc.  Actually, we wouldn't need a "diff4" command, we could just
extend "diff" to accept an arbitrary number of arguments.

> Have I wasted a whole lot of time thinking about something that
> can't actually be done?  Has someone already done it?

I think it can be done, and I don't think anybody's done it.

> Is anyone interested in pursuing this problem at all?

It's been on my list of things to do for several years.
It's an interesting problem.

> PS Oh, and is there a good reason why sdiff seems to be limited to
> two-way diffs?

Historical reasons.  sdiff is present merely to support the System V
command interface.  Most people who want to do merges use other tools
these days, e.g. Emacs.

> [I really wanted to send this to a diffutils discussion mailing list,

bug-gnu-utils is the right list for diff.