Existing diff3 implementations

[dominicjaeger]

I spent some time looking for well thought out implementations of diff3 algorithms.

FreeBSD for example has a GPL implementation in its contrib directory. But I guess doing this would interfere with

Elektra (except for some plugins) has no external dependency.

There are more similar resources under different licenses, for example under Apache License or GPL (this is not 3 way yet).

Unfortunately, we can use none of them and still publish Elektra as BSD 3-clause.
The only resource that we could maybe use is from OpenBSD. However, I'm not sure which of the two BSD licenses in this file takes effect, the 3 or 4-clause.

[kodebach]

or GPL (this is not 3 way yet).

The linked repository is under Apache 2.0 License, not GPL. Apache 2.0 would be fine, we already have a few files under Apache 2.0.

[dominicjaeger]

The linked repository is under Apache 2.0 License, not GPL

Oops, too many open tabs and copied links.

Apache 2.0 would be fine, we already have a few files under Apache 2.0.

Apparently the arrows in the wikipedia image don't work as I thought after a first glance. Thank you for taking a look! I'll look for more Apache (and according to the list MIT) stuff tomorrow :)

[markus2330]

Yes, and it would be more clear if you make a list or table of the different implementations, describing what you found out for each of those. Not only the license matters but also the features and if the data structure is suitable for you.

[dominicjaeger]

List of diff/diff3 programs

LibXDiff

http://www.xmailserver.org/xdiff-lib.html

The LibXDiff library implements basic and yet complete functionalities to create file differences/patches to both binary and text files. (...) While for text files it follows directives described in An O(ND) Difference Algorithm and Its Variations by Eugene W. Myers.

LibXDiff is made available through the GNU LGPL license together with the complete sources.

libgit2 for example uses LibXDiff

API is available at http://www.xmailserver.org/xdiff.html and there is especially xdl_merge3
Looks a lot smaller than libgit2

libgit2

(https://libgit2.org/)

libgit2 is a portable, pure C implementation of the Git core methods provided as a re-entrant linkable library with a solid API (...)

• Zero Dependencies: Builds out of the box with no dependencies. Works in embedded devices and iOS.
• C89: Written with portability in mind. Builds in GCC, Clang and MSVC.
• Permissive Licensing: GPLv2 with Linking Exception.

API is here, especially the diff function is interesting.

Arree Diff Match Patch

https://github.com/arrbee/diff-match-patch-c

C language port of google-diff-match-patch library

Right now, this is focused on the diff part of diff-match-patch.

This C version of Diff, Match and Patch Library is licensed under the MIT License (a.k.a. the Expat License) which is included here in the LICENSE file.

Really easy API
`extern int dmp_diff_new(
dmp_diff **diff,
const dmp_options *options,
const char *text1,
uint32_t len1,
const char *text2,
uint32_t len2);´

MatthieuTranCSUF/myers-diff

https://github.com/MatthieuTranCSUF/myers-diff

No license or description. Some lines of C that seem to implement Myers diff.
Has some own small datastructures defined for the "API".

OpenBSD diff3

http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/usr.bin/diff3/diff3prog.c

Dual licensed with BSD 3-clause and BSD-clause??

GNU Diffutils diff3

https://github.com/Distrotech/diffutils/blob/distrotech-diffutils/src/diff3.c

The well-known diff3. GPLv3. 1700 lines and has to call a regular diff which again has 1400 lines => Much blabla that we don't need.

Apple diff3

https://opensource.apple.com/source/gnudiff/gnudiff-10/diffutils/diff3.c.auto.html.
Looks pretty similar to GNU diff3. Ancestor of it? GPLv2

SVN diff3

https://svn.apache.org/repos/asf/subversion/trunk/tools/diff/

test driver for 3-way text merges

Apache License 2.0. Heavily integrated. No easily accessible API. C.

Git merge

https://github.com/git/git

No easily accessible API for simply diffing and merging 3 files.

git4idea

https://github.com/JetBrains/intellij-community/blob/master/plugins/git4idea/src/git4idea/merge/
JetBrains

No easily accessible API. Java.

Google Diff Match Patch

https://github.com/google/diff-match-patch/blob/master/LICENSE

Diff Match Patch is a high-performance library in multiple languages that manipulates plain text.

Many languages but not C99

This library implements Myer's diff algorithm which is generally considered to be the best general-purpose diff.

Apache License 2.0

Conclusion

I read in some forum posts that we could link LGPL programs into our BSD code, but found no reliable looking source yet. If this is true, then LibXDiff looks like the best solution to me at the moment.

[markus2330]

Thank you! Very nice summary! You can also put that into your thesis!

It is no problem to link against an LGPL library if the library is already available in the usual distributions. But it seems like all these libs are not present (at least not on Debian).

So it seems like we need to also deliver the source, and then LGPL is not ok.

[markus2330]

As discussed we will use libgit2 as optional dependency with a fallback where arrays will always conflict when they are different (as it is now).

This means:

• Elektra can still be compiled without any dep on any system, including the merging lib
• with libgit2 one gets better merging results, so it is recommended to have it