Re: [Kdiff3-user] diff/merge algorithm improvements

[Joachim E. <joa...@gm...>]

Hi Fran=E7ois,

A feature like you suggest is on my todo list, because I know that it would=
=20
yield many benefits.
But I'm very careful to modify the core algorithms because it took a long t=
ime=20
to get them to be as stable as they are now.

The same probably applies to original GNU-diff. So I think your chances wit=
h=20
KDiff3 are not so bad. But if the original GNU-diff is extended in such a w=
ay=20
I will gladly upgrade KDiff3 as well.

As for the algorithm: One important reason, why this is not a standard feat=
ure=20
yet, is that there is no really universal and fast algorithm. A line based=
=20
diff can be fast because it compares hash values for equal lines, but if=20
lines are not equal the complexity grows quadratically with the maximum=20
distance where a match is searched for and a single comparison already take=
s=20
long. So I would make it an optional feature only.

I'll investigate.

Joachim


Am Freitag, 27. April 2007 17:46 schrieb Fran=E7ois Cerbelle:
> Hi,
>
> I searched throught the list but did not find a similar question to mine.
> The test files are :
> a.txt b.txt c.txt
>  DEF   DZF   ABC
>  GHI   GHI   DEF
>              GHI
>
> When I use KDiff3 with:
> - a and b, it detects that the first line whas modified : OK.
>  a   b
> DEF DZF
> GHI GHI
>
> - a and c, it detects that a new line was added in c : OK.
>  a   c
>     ABC
> DEF DEF
> GHI GHI
>
> - b and c, it detects that  the first line changed and that a new line was
> added : it is true, but not optimal.
>  b   c
> DZF ABC
>     DEF
> GHI GHI
>
> a more logical diff would be :
>  b   c
>     ABC
> DZF DEF
> GHI GHI
>
> - a, b and c : KDiff align DEF(a) with DEF(c) but not with DZF(b), it
> aligns DZF(b) with ABC(c), which is not very logic (from a user point of
> view). In fact, it would be more accurate if the result was :
>  a   b   c
>     DZF ABC
> DEF     DEF
> GHI GHI GHI
>
> a more logical diff would be:
>  a   b   c
>         ABC
> DEF DZF DEF
> GHI GHI GHI
>
> We encountered theses behaviours when using the couple
> Mercurial(hg)/KDiff3 to manage our source repository. Such "more logical"
> or "more smart" diffs would be very useful to merge files.
>
> I think the problem comes from the GNU Diff lib as "vimdiff" (part of
> "vim") has the same behaviour. But as you changed the GNU diff lib, if I
> submit the problem to the GNU Team, I am not sure the fix (if they do)
> will go into KDiff3.
>
> What do you think ? Is it technicaly possible to do such a diff ? Who
> should do it (KDiff or GNU) ? Such a diff does not break the "spirit" of
> diff/KDiff ?
>
> Have a nice day
> Fran=E7ois