[vim/vim] use xdiff to implement internal diff algorithm (#2732)
Christian Brabandt
Okay, this is very highly experimental and still work in progress. But it might be good enough to share what I have, because it seems to pass my very basic tests and I do not know how much time I have to work on it in the future.
This PR imports the libxdiff from the git source tree to implement an internal diff parser (this is from git-2.17.0-rc0, plus some slight style changes [added a couple of casts]). This will make creating diffs a lot faster, since we do not need to shell out to parse the output of diff foobar foobar.new.
Currently, it runs the xdiff algorithm on the already written temp files tmp_new and tmp_orig and write the result to tmp_diff. We can probably skip writing temp files for creating diffs at all, but I am currently not sure how to do it. So there is some room for even more performance improvements later.
In addition, by using the git diff included xdiff, we can in the future support several improvements to the diff algorithm, e.g. implement patience and histogram diff algorithm, without much fuzz. Currently this is not supported, but it should be easily possible. Also the new indent heuristics from git which is the default starting with 2.14 should be possible with some kind of a switch.
To use the new algorithm, make sure to :set diffopt+=internal. As said before, this is highly experimental and might crash :(
Also note, I have basically no clue of how to import that part into the Makefile, so I changed src/Makefile manually and it might be cumbersome. But at least, it seems to work :)
BTW: feedback welcome, however, I am not sure how much time in the future I have to work on it. So I leave this here and hopefully this will make it easier to implement an internal diff in Vim.
However, note, I did not yet check which files from git/git source xdiff directory are actually needed. Currently, it will compile a couple of files, which might not (all) be necessary. So it imports a couple of more files than currently needed. But it will enable additional diff options later.
However, once we have this change in place, it should be straight forward to make further adjustments as needed (e.g. do not write temp files at all to speed up diffing even further).
Also this has the further advantage to support unified diffs, when using a custom diffexpression. Currently only ed like style diffs are supported, which kind of sucks and prevents us from simply using :set diffexpr=git diff, because unified style diffs seems to be what most tools nowadays understand and ed like style diffs seem kind of traditional and even unsupported.
Note, there might be a some disadvantages with using libxdiff:
- the libxdiff algorithm is different from GNU diff. However, I suppose by using xdiff from git,
we got a lot of testing. (git has imported this library around 2006, so there are at least 10
years of thoroughly testing).
You can view, comment on, or merge this pull request online at:
https://github.com/vim/vim/pull/2732
Commit Summary
- import xdiff tree from git
- Use xdiff to create a diff if diffopt=internal
- Parse unified diff
- Update documentation
File Changes
- M Filelist (15)
- M runtime/doc/diff.txt (5)
- M runtime/doc/options.txt (4)
- M src/Makefile (44)
- M src/diff.c (453)
- M src/proto/diff.pro (1)
- A src/xdiff/xdiff.h (152)
- A src/xdiff/xdiffi.c (1049)
- A src/xdiff/xdiffi.h (64)
- A src/xdiff/xemit.c (312)
- A src/xdiff/xemit.h (36)
- A src/xdiff/xhistogram.c (363)
- A src/xdiff/xinclude.h (44)
- A src/xdiff/xmacros.h (54)
- A src/xdiff/xmerge.c (686)
- A src/xdiff/xpatience.c (390)
- A src/xdiff/xprepare.c (483)
- A src/xdiff/xprepare.h (34)
- A src/xdiff/xtypes.h (67)
- A src/xdiff/xutils.c (425)
- A src/xdiff/xutils.h (47)
Patch Links:
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
Codecov
Codecov Report
Merging #2732 into master will decrease coverage by
1.02%.
The diff coverage is3.53%.
@@ Coverage Diff @@ ## master #2732 +/- ## ========================================== - Coverage 75% 73.97% -1.03% ========================================== Files 92 99 +7 Lines 134149 136035 +1886 ========================================== + Hits 100617 100636 +19 - Misses 33532 35399 +1867
| Impacted Files | Coverage Δ | |
|---|---|---|
| src/xdiff/xutils.c | 0% <0%> (ø) |
|
| src/xdiff/xprepare.c | 0% <0%> (ø) |
|
| src/xdiff/xemit.c | 0% <0%> (ø) |
|
| src/xdiff/xhistogram.c | 0% <0%> (ø) |
|
| src/xdiff/xdiffi.c | 0% <0%> (ø) |
|
| src/xdiff/xmerge.c | 0% <0%> (ø) |
|
| src/xdiff/xpatience.c | 0% <0%> (ø) |
|
| src/diff.c | 75.89% <37.29%> (-6.58%) |
⬇️ |
| src/if_xcmdsrv.c | 84.17% <0%> (-1.44%) |
⬇️ |
| ... and 16 more |
Continue to review full report at Codecov.
Legend - Click here to learn more
Δ = absolute <relative> (impact),ø = not affected,? = missing data
Powered by Codecov. Last update 29dfa5a...543f2d5. Read the comment docs.
Christian Brabandt
I have disabled the libxdiff feature on Windows, because the windows Makefile has not been changed yet to include the xdiff source and there were some issues with mch_stat where I am not sure how to fix them for Windows.
Also I have not yet included any tests, mainly because I am not sure how to test the resulting diff. Perhaps it would be possible to run Vim recursively inside a terminal window in diff mode and snapshot the resulting diff using term_dumpwrite(). But I haven't looked at it how feasible this would be.
LemonBoy
Nice, I wrote a small tool using xdiff to have nice/fast diffs and avoid messing with the vim source code.
Christian Brabandt
Ha, I like the name ;)
BTW: I have implemented a vim-script solution to translate unified diff output to ed style diffs in vim-diff-enhanced
Christian Brabandt
Christian Brabandt
I think it is now in a shape, that is safe to include. I can squash it into a single commit if needed. Once this prooved to be stable enough, it might even allow us to get rid of distributing diff together with Vim.
I added a couple of tests, implemented the missing 'diffopt' values and made it work on Windows. Tests pass except for some slight differences in the term_dump() function. This can be seen here:
https://api.travis-ci.org/v3/job/357269023/log.txt
https://api.travis-ci.org/v3/job/357269024/log.txt
The only difference is this part:
@@ -17,4 +17,4 @@ | +0#0000e05#a8a8a8255@1|~+0#4040ff13#ffffff0| @33||+1#0000000&| +0#0000e05#a8a8a8255@1|~+0#4040ff13#ffffff0| @33 | +0#0000e05#a8a8a8255@1|~+0#4040ff13#ffffff0| @33||+1#0000000&| +0#0000e05#a8a8a8255@1|~+0#4040ff13#ffffff0| @33 |X+3#0000000&|f|i|l|e|1| @12|1|,|1| @11|A|l@1| |X+1&&|f|i|l|e|2| @12|1|,|1| @11|A|l@1 -|:+0&&> @73 +|:+0&&> | @72
which I think is a bug in the term_dump() function and I have already reported at vim-dev. Also there was one ASAN error reported here:
https://api.travis-ci.org/v3/job/357269032/log.txt
Which also looks like a bug in the f_term_dumpwrite function. And finally, it looks like there was one out of memory error on travis:
https://api.travis-ci.org/v3/job/357337067/log.txt
There is still room for improvement though. For one thing one could avoid the whole I/O overhead by making it use without using temporary files. But I have the feeling that is something I cannot easily implement and might take some additional time and effort, which I do not have currently.
Second, the :diffpatch function could make use of the xdiff library. However it looks like currently the xdl_patch() function has been removed from the xdiff library by the git folks. Anyhow, I have the feeling, that the :diffpatch command is actually not much used, since it currently requires the patch program available and that one is not even bundled with Vim. So this command already fails miserably on Windows with a command not found error :(
And finally it might make sense to allow context lines when parsing the unified diff. This would mean, one needs to actually adjust the hunk addresses (lnum_orig, count_orig, lnum_new and count_new) as one parses the file. I have not done so yet, so Vim always expects a unified diff with zero context lines. There won't be an error, just the diff will be rendered wrongly.
And finally here are two screencasts how to make use of the new diff algorithms in Vim that comes with xdiff:
- Using the build in patience algorithm: https://asciinema.org/a/YL035raOlEbadoWNLpj5cBXan
- Using the new indent-heuristics: https://asciinema.org/a/QyIhLUUmwMdpzIjRhkdcPdUyx
Kudos goes to the git developers for developing those parts.
Kazunobu Kuriyama
On my Mac, the build was done successfully, and the resulting Vim worked fine, just the same way as the screencasts are showing.
I have used my own Lua script to have Vim accept the output of git diff --no-index. I found that the xdiff of this PR gives just the same results that the script does, but I also found that the former gives a far better user experience than the latter: It's free from severe flicker or hiccups such as incompletely-finished-redrawing. In addition to making some nice diff algorithms available to Vim, I think this PR succeeded in showing the advantage of having a builtin xdiff.
As to the screen dump test, I got
Test results:
From test_diffmode.vim:
Found errors in Test_diff_screen():
function RunTheTest[38]..Test_diff_screen[14]..VerifyScreenDump line 14: See dump file difference: call term_dumpdiff("Test_diff_01.dump.failed", "dumps/Test_diff_01.dump")
function RunTheTest[38]..Test_diff_screen[14]..VerifyScreenDump line 16: --- dumps/Test_diff_01.dump 2018-03-23 21:31:49.000000000 +0900
function RunTheTest[38]..Test_diff_screen[14]..VerifyScreenDump line 16: +++ Test_diff_01.dump.failed 2018-03-23 21:41:51.000000000 +0900
function RunTheTest[38]..Test_diff_screen[14]..VerifyScreenDump line 16: @@ -17,4 +17,4 @@
function RunTheTest[38]..Test_diff_screen[14]..VerifyScreenDump line 16: | +0#0000e05#a8a8a8255@1|~+0#4040ff13#ffffff0| @33||+1#0000000&| +0#0000e05#a8a8a8255@1|~+0#4040ff13#ffffff0| @33
function RunTheTest[38]..Test_diff_screen[14]..VerifyScreenDump line 16: | +0#0000e05#a8a8a8255@1|~+0#4040ff13#ffffff0| @33||+1#0000000&| +0#0000e05#a8a8a8255@1|~+0#4040ff13#ffffff0| @33
function RunTheTest[38]..Test_diff_screen[14]..VerifyScreenDump line 16: |X+3#0000000&|f|i|l|e|1| @12|1|,|1| @11|A|l@1| |X+1&&|f|i|l|e|2| @12|1|,|1| @11|A|l@1
function RunTheTest[38]..Test_diff_screen[14]..VerifyScreenDump line 16: -|:+0&&> @73
function RunTheTest[38]..Test_diff_screen[14]..VerifyScreenDump line 16: +|:+0&&> | @72
TEST FAILURE
Also, when I tried to compile the patched source with -std=c89, I got
$ CFLAGS='-std=c89' ./configure && make
...
gcc -c -I. -Iproto -DHAVE_CONFIG_H -DMACOS_X -DMACOS_X_DARWIN -std=c89 -U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=1 -o objects/xdiffi.o xdiff/xdiffi.c
xdiff/xdiffi.c:733:8: error: unknown type name 'inline'
static inline int group_next(xdfile_t *xdf, struct xdlgroup *g)
^
xdiff/xdiffi.c:733:15: error: expected identifier or '('
static inline int group_next(xdfile_t *xdf, struct xdlgroup *g)
^
xdiff/xdiffi.c:749:8: error: unknown type name 'inline'
static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g)
^
xdiff/xdiffi.c:749:15: error: expected identifier or '('
static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g)
^
4 errors generated.
make: *** [objects/xdiffi.o] Error 1
Christian Brabandt
The screen dump diff looks similar to the one above from the CI. I am not sure, but I think the difference is only that for one dump there a 73 spaces while the result of the test was 1 single space followed by 72 spaces. If you load it into Vim using call term_dumpdiff("Test_diff_01.dump.failed", "dumps/Test_diff_01.dump") you'll probably not notice any difference.
regarding the C89 issue, I have seen a similar error on Windows and have therefore disabled the inline and attribute flags using 0c40761. Perhaps those should be done unconditionally? (I didn't do it, because I didn't want to change too much of the upstream source. Or is there a similar compile property available to check against when compiling?
Justin M. Keyes
This PR imports the libxdiff from the git source tree
Is libxdiff not available for linking instead of inlining the entire thing (GPL license) into the Vim tree?
Kazunobu Kuriyama
If you load it into Vim using call term_dumpdiff("Test_diff_01.dump.failed", "dumps/Test_diff_01.dump") you'll probably not notice any difference.
Indeed, I can't distinguish one from another. For convenience, I'm uploading a screenshot obtained by the suggested command:
regarding the C89 issue, I have seen a similar error on Windows and have therefore disabled the inline and attribute flags using 0c40761. Perhaps those should be done unconditionally?
I think that would be the easiest, practical way to go unless avoiding the inline ends up a noticeable deterioration in performance.
That said, I also understand
I didn't want to change too much of the upstream source.
as, IIRC, an option once introduced to git diff was abolished in a few month last year. The development has been so active even these days. Too much deviation from the original source surely makes it harder for us to catch up with improvement done by the upstream in the future...
Or is there a similar compile property available to check against when compiling?
I'm afraid there's not.
Christian Brabandt
Is libxdiff not available for linking instead of inlining the entire thing (GPL license) into the Vim tree?
As far as I can see, there is no libxdiff-dev available in Debian. Not even the original version. Also git seems to inline it (using a static library, not that it matters much in practice).
Christian Brabandt
[disable inline...]
I think that would be the easiest, practical way to go unless avoiding the inline ends up a noticeable deterioration in performance.
I tried and failed miserably.
https://ci.appveyor.com/project/chrisbra/vim-ch0ci/build/job/g1430v7vw08q6y3y
https://ci.appveyor.com/project/chrisbra/vim-ch0ci/build/job/g1430v7vw08q6y3y
duplicate symbol _isprint in:
objects/xdiffi.o
objects/xemit.o
duplicate symbol _digittoint in:
objects/xdiffi.o
objects/xemit.o
duplicate symbol _isxdigit in:
objects/xdiffi.o
objects/xemit.o
duplicate symbol _isdigit in:
objects/xdiffi.o
objects/xemit.o
On Mac and on Windows with Mingw. Wow, I did not expect that. So I am rolling it back for now.
Christian Brabandt
rebased and added another test for 'diffopt+=iwhite'
—
You are receiving this because you are subscribed to this thread.
Christian Brabandt
Justin M. Keyes
What are the implications of pasting GPL-licensed code into Vim's source?
—
You are receiving this because you are subscribed to this thread.
Tony Mechelynck
@justinmk : from a page or so below :help license:
- According to Richard Stallman the Vim license is GNU GPL compatible.
A few minor changes have been made since he checked it, but that should not
make a difference.
- If you link Vim with a library that goes under the GNU GPL, this limits
further distribution to the GNU GPL. Also when you didn't actually change
anything in Vim.
- Once a change is included that goes under the GNU GPL, this forces all
further changes to also be made under the GNU GPL or a compatible license.
micbou
The library is LGPL-licensed so including the library doesn't require changing the Vim license to GPL. There are other requirements though like mentioning that the library is used and covered by the LGPL (this could be added to the :version output for instance), and adding a copy of the GPL and LGPL to the project.
Christian Brabandt
Thanks for those comments. I added a commit mentioning the license of libxdiff and included the LGPL for further distribution. I leave the decision to mention the license in the :version output to Bram.
I also added a second commit to make the tests work better by disableing the SwapFile Exists warning.
There is still an ASAN failure which looks like term->tl_vterm-> screen gets somehow corrupted causing a segfault. Unfortunately, I can only reproduce this on the CI infrastructure and not locally. I don't actually know how to debug this.
Bram Moolenaar
> [The library is
> LGPL-licensed](http://www.xmailserver.org/xdiff-lib.html) so including
> the library doesn't require changing the Vim license to GPL. There are
> like mentioning that the library is used and covered by the LGPL (this
> could be added to the `:version` output for instance), and adding a
> copy of the GPL and LGPL to the project.
in the binary is only needed if other copyright notices are given, which
I don't think we do anywhere. Mentioning the copyright in the help
somewhere is appropriate.
I also think the code can be modified, since we will distribute it
together with the Vim source code.
Now back to actually making this work. And perhaps there is another
diff library that is better (faster/smaller/etc.).
--
hundred-and-one symptoms of being an internet addict:
142. You dream about creating the world's greatest web site.
/// Bram Moolenaar -- Br...@Moolenaar.net -- http://www.Moolenaar.net \\\
/// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
\\\ an exciting new programming language -- http://www.Zimbu.org ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///
chdiza
Vim doesn't even put it's own licensing info in the output of :version. I have no idea why we would put anything else's licensing info in there.
micbou
Vim doesn't even put it's own licensing info in the output of :version. I have no idea why we would put anything else's licensing info in there.
I thought the license was mentioned there as a lot of tools are displaying that kind of info when running them with --version on the command line. Anyway, this was just a suggestion of where it could be mentioned. Adding it to :h license should be fine.