Merge #9306 'vim-patch: integrate xdiff library'

closes #1466
closes #1007
closes #1391

30 files changed, 6015 insertions, 306 deletions

diff --git a/runtime/doc/autocmd.txt b/runtime/doc/autocmd.txt
index 4702656c41..c34dbaaf60 100644
--- a/runtime/doc/autocmd.txt
+++ b/runtime/doc/autocmd.txt
@@ -628,6 +628,11 @@ CursorMoved			After the cursor was moved in Normal or Visual
 CursorMovedI			After the cursor was moved in Insert mode.
 				Not triggered when the popup menu is visible.
 				Otherwise the same as CursorMoved.
+							*DiffUpdated*
+DiffUpdated			After diffs have been updated.  Depending on
+				what kind of diff is being used (internal or
+				external) this can be triggered on every
+				change or when doing |:diffupdate|.
 							*DirChanged*
 DirChanged			After the |current-directory| was changed.
 				Sets these |v:event| keys:
diff --git a/runtime/doc/diff.txt b/runtime/doc/diff.txt
index 766240dfb0..ab002b4dcb 100644
--- a/runtime/doc/diff.txt
+++ b/runtime/doc/diff.txt
@@ -27,7 +27,9 @@ The second and following arguments may also be a directory name.  Vim will
 then append the file name of the first argument to the directory name to find
 the file.
 
-This only works when a standard "diff" command is available.  See 'diffexpr'.
+By default an internal diff library will be used.  When 'diffopt' or
+'diffexpr' has been set an external "diff" command will be used.  This only
+works when such a diff program is available.
 
 Diffs are local to the current tab page |tab-page|.  You can't see diffs with
 a window in another tab page.  This does make it possible to have several
@@ -332,8 +334,9 @@ between file1 and file2: >
 
 The ">" is replaced with the value of 'shellredir'.
 
-The output of "diff" must be a normal "ed" style diff.  Do NOT use a context
-diff.  This example explains the format that Vim expects: >
+The output of "diff" must be a normal "ed" style diff or a unified diff.  Do
+NOT use a context diff.  This example explains the format that Vim expects for
+the "ed" style diff: >
 
 	1a2
 	> bbb
diff --git a/runtime/doc/options.txt b/runtime/doc/options.txt
index 29d9a60aa2..9aaae6a527 100644
--- a/runtime/doc/options.txt
+++ b/runtime/doc/options.txt
@@ -1859,13 +1859,13 @@ A jump table for the options with a short description can be found at |Q_op|.
 						*'dex'* *'diffexpr'*
 'diffexpr' 'dex'	string	(default "")
 			global
-	Expression which is evaluated to obtain an ed-style diff file from two
-	versions of a file.  See |diff-diffexpr|.
+	Expression which is evaluated to obtain a diff file (either ed-style
+	or unified-style) from two versions of a file.  See |diff-diffexpr|.
 	This option cannot be set from a |modeline| or in the |sandbox|, for
 	security reasons.
 
 						*'dip'* *'diffopt'*
-'diffopt' 'dip'		string	(default "filler")
+'diffopt' 'dip'		string	(default "internal,filler")
 			global
 	Option settings for diff mode.  It can consist of the following items.
 	All are optional.  Items must be separated by a comma.
@@ -1925,11 +1925,31 @@ A jump table for the options with a short description can be found at |Q_op|.
 		foldcolumn:{n}	Set the 'foldcolumn' option to {n} when
 				starting diff mode.  Without this 2 is used.
 
-	Examples: >
+		internal	Use the internal diff library.  This is
+				ignored when 'diffexpr' is set.  *E960*
+				When running out of memory when writing a
+				buffer this item will be ignored for diffs
+				involving that buffer.  Set the 'verbose'
+				option to see when this happens.
+
+		indent-heuristic
+				Use the indent heuristic for the internal
+				diff library.
+
+                algorithm:{text} Use the specified diff algorithm with the
+				internal diff engine. Currently supported 
+				algorithms are:
+				myers      the default algorithm
+				minimal    spend extra time to generate the
+					   smallest possible diff
+				patience   patience diff algorithm
+				histogram  histogram diff algorithm
 
-		:set diffopt=filler,context:4
+	Examples: >
+		:set diffopt=internal,filler,context:4
 		:set diffopt=
-		:set diffopt=filler,foldcolumn:3
+		:set diffopt=internal,filler,foldcolumn:3
+		:set diffopt-=internal  " do NOT use the internal diff parser
 <
 				     *'digraph'* *'dg'* *'nodigraph'* *'nodg'*
 'digraph' 'dg'		boolean	(default off)
diff --git a/src/nvim/CMakeLists.txt b/src/nvim/CMakeLists.txt
index 29a4e1e163..a2c4e677d4 100644
--- a/src/nvim/CMakeLists.txt
+++ b/src/nvim/CMakeLists.txt
@@ -79,6 +79,8 @@ file(MAKE_DIRECTORY ${LINT_SUPPRESSES_ROOT}/src)
 
 file(GLOB NVIM_SOURCES *.c)
 file(GLOB NVIM_HEADERS *.h)
+file(GLOB XDIFF_SOURCES xdiff/*.c)
+file(GLOB XDIFF_HEADERS xdiff/*.h)
 
 foreach(subdir
         os
@@ -148,12 +150,13 @@ set(CONV_SOURCES
   syntax.c
   tag.c
   window.c)
-
 foreach(sfile ${CONV_SOURCES})
   if(NOT EXISTS "${CMAKE_CURRENT_LIST_DIR}/${sfile}")
     message(FATAL_ERROR "${sfile} doesn't exist (it was added to CONV_SOURCES)")
   endif()
 endforeach()
+# xdiff: inlined external project, we don't maintain it. #9306
+list(APPEND CONV_SOURCES ${XDIFF_SOURCES})
 
 if(NOT MSVC)
   set_source_files_properties(
@@ -404,7 +407,8 @@ if(POLICY CMP0069)
 endif()
 
 add_executable(nvim ${NVIM_GENERATED_FOR_SOURCES} ${NVIM_GENERATED_FOR_HEADERS}
-  ${NVIM_GENERATED_SOURCES} ${NVIM_SOURCES} ${NVIM_HEADERS})
+  ${NVIM_GENERATED_SOURCES} ${NVIM_SOURCES} ${NVIM_HEADERS}
+  ${XDIFF_SOURCES} ${XDIFF_HEADERS})
 target_link_libraries(nvim ${NVIM_EXEC_LINK_LIBRARIES})
 install_helper(TARGETS nvim)
 
@@ -490,6 +494,7 @@ add_library(
   EXCLUDE_FROM_ALL
   ${NVIM_SOURCES} ${NVIM_GENERATED_SOURCES}
   ${NVIM_HEADERS} ${NVIM_GENERATED_FOR_SOURCES} ${NVIM_GENERATED_FOR_HEADERS}
+  ${XDIFF_SOURCES} ${XDIFF_HEADERS}
 )
 set_property(TARGET libnvim APPEND PROPERTY
              INCLUDE_DIRECTORIES ${LUA_PREFERRED_INCLUDE_DIRS})
@@ -514,6 +519,7 @@ else()
     EXCLUDE_FROM_ALL
     ${NVIM_SOURCES} ${NVIM_GENERATED_SOURCES}
     ${NVIM_HEADERS} ${NVIM_GENERATED_FOR_SOURCES} ${NVIM_GENERATED_FOR_HEADERS}
+    ${XDIFF_SOURCES} ${XDIFF_HEADERS}
     ${UNIT_TEST_FIXTURES}
   )
   target_link_libraries(nvim-test ${NVIM_TEST_LINK_LIBRARIES})
diff --git a/src/nvim/auevents.lua b/src/nvim/auevents.lua
index a6290aaac1..ab92e84799 100644
--- a/src/nvim/auevents.lua
+++ b/src/nvim/auevents.lua
@@ -33,6 +33,7 @@ return {
     'CursorHoldI',            -- idem, in Insert mode
     'CursorMoved',            -- cursor was moved
     'CursorMovedI',           -- cursor was moved in Insert mode
+    'DiffUpdated',            -- diffs have been updated
     'DirChanged',             -- directory changed
     'EncodingChanged',        -- after changing the 'encoding' option
     'ExitPre',                -- before exiting
diff --git a/src/nvim/buffer_defs.h b/src/nvim/buffer_defs.h
index e86eaf010f..d270714611 100644
--- a/src/nvim/buffer_defs.h
+++ b/src/nvim/buffer_defs.h
@@ -58,10 +58,10 @@ typedef struct {
  * functions that set or reset the flags.
  *
  * VALID_BOTLINE    VALID_BOTLINE_AP
- *     on		on		w_botline valid
- *     off		on		w_botline approximated
- *     off		off		w_botline not valid
- *     on		off		not possible
+ *     on       on      w_botline valid
+ *     off      on      w_botline approximated
+ *     off      off     w_botline not valid
+ *     on       off     not possible
  */
 #define VALID_WROW      0x01    /* w_wrow (window row) is valid */
 #define VALID_WCOL      0x02    /* w_wcol (window col) is valid */
@@ -159,7 +159,7 @@ typedef struct {
   int wo_arab;
 # define w_p_arab w_onebuf_opt.wo_arab  /* 'arabic' */
   int wo_bri;
-# define w_p_bri w_onebuf_opt.wo_bri	/* 'breakindent' */
+# define w_p_bri w_onebuf_opt.wo_bri    // 'breakindent'
   char_u *wo_briopt;
 # define w_p_briopt w_onebuf_opt.wo_briopt /* 'breakindentopt' */
   int wo_diff;
@@ -412,13 +412,13 @@ typedef struct {
    * syntax state too often.
    * b_sst_array[] is allocated to hold the state for all displayed lines,
    * and states for 1 out of about 20 other lines.
-   * b_sst_array	pointer to an array of synstate_T
-   * b_sst_len	number of entries in b_sst_array[]
-   * b_sst_first	pointer to first used entry in b_sst_array[] or NULL
-   * b_sst_firstfree	pointer to first free entry in b_sst_array[] or NULL
-   * b_sst_freecount	number of free entries in b_sst_array[]
-   * b_sst_check_lnum	entries after this lnum need to be checked for
-   *			validity (MAXLNUM means no check needed)
+   * b_sst_array        pointer to an array of synstate_T
+   * b_sst_len          number of entries in b_sst_array[]
+   * b_sst_first        pointer to first used entry in b_sst_array[] or NULL
+   * b_sst_firstfree    pointer to first free entry in b_sst_array[] or NULL
+   * b_sst_freecount    number of free entries in b_sst_array[]
+   * b_sst_check_lnum   entries after this lnum need to be checked for
+   *                    validity (MAXLNUM means no check needed)
    */
   synstate_T  *b_sst_array;
   int b_sst_len;
@@ -475,15 +475,15 @@ struct file_buffer {
   int b_locked;                 // Buffer is being closed or referenced, don't
                                 // let autocommands wipe it out.
 
-  /*
-   * b_ffname has the full path of the file (NULL for no name).
-   * b_sfname is the name as the user typed it (or NULL).
-   * b_fname is the same as b_sfname, unless ":cd" has been done,
-   *		then it is the same as b_ffname (NULL for no name).
-   */
-  char_u      *b_ffname;        /* full path file name */
-  char_u      *b_sfname;        /* short file name */
-  char_u      *b_fname;         /* current file name */
+  //
+  // b_ffname   has the full path of the file (NULL for no name).
+  // b_sfname   is the name as the user typed it (or NULL).
+  // b_fname    is the same as b_sfname, unless ":cd" has been done,
+  //            then it is the same as b_ffname (NULL for no name).
+  //
+  char_u      *b_ffname;        // full path file name
+  char_u      *b_sfname;        // short file name
+  char_u      *b_fname;         // current file name
 
   bool file_id_valid;
   FileID file_id;
@@ -587,12 +587,12 @@ struct file_buffer {
 
   bool b_scanned;               /* ^N/^P have scanned this buffer */
 
-  /* flags for use of ":lmap" and IM control */
-  long b_p_iminsert;            /* input mode for insert */
-  long b_p_imsearch;            /* input mode for search */
-#define B_IMODE_USE_INSERT -1   /*	Use b_p_iminsert value for search */
-#define B_IMODE_NONE 0          /*	Input via none */
-#define B_IMODE_LMAP 1          /*	Input via langmap */
+  // flags for use of ":lmap" and IM control
+  long b_p_iminsert;            // input mode for insert
+  long b_p_imsearch;            // input mode for search
+#define B_IMODE_USE_INSERT -1   //  Use b_p_iminsert value for search
+#define B_IMODE_NONE 0          //  Input via none
+#define B_IMODE_LMAP 1          //  Input via langmap
 # define B_IMODE_LAST 1
 
   short b_kmap_state;           /* using "lmap" mappings */
@@ -760,7 +760,7 @@ struct file_buffer {
   /* Two special kinds of buffers:
    * help buffer  - used for help files, won't use a swap file.
    * spell buffer - used for spell info, never displayed and doesn't have a
-   *		      file name.
+   *                file name.
    */
   bool b_help;                  /* TRUE for help file buffer (when set b_p_bt
                                    is "help") */
@@ -787,6 +787,8 @@ struct file_buffer {
   // array of channelids which have asked to receive updates for this
   // buffer.
   kvec_t(uint64_t) update_channels;
+
+  int b_diff_failed;    // internal diff failed for this buffer
 };
 
 /*
@@ -840,6 +842,7 @@ struct tabpage_S {
   diff_T          *tp_first_diff;
   buf_T           *(tp_diffbuf[DB_COUNT]);
   int tp_diff_invalid;              ///< list of diffs is outdated
+  int tp_diff_update;               ///< update diffs before redrawing
   frame_T         *(tp_snapshot[SNAP_COUNT]);    ///< window layout snapshots
   ScopeDictDictItem tp_winvar;      ///< Variable for "t:" Dictionary.
   dict_T          *tp_vars;         ///< Internal variables, local to tab page.
@@ -916,9 +919,9 @@ typedef struct {
 /// Same as lpos_T, but with additional field len.
 typedef struct
 {
-    linenr_T    lnum;	///< line number
-    colnr_T     col;	///< column number
-    int         len;	///< length: 0 - to the end of line
+    linenr_T    lnum;   ///< line number
+    colnr_T     col;    ///< column number
+    int         len;    ///< length: 0 - to the end of line
 } llpos_T;
 
 /// posmatch_T provides an array for storing match items for matchaddpos()
@@ -926,10 +929,10 @@ typedef struct
 typedef struct posmatch posmatch_T;
 struct posmatch
 {
-    llpos_T     pos[MAXPOSMATCH];	///< array of positions
-    int         cur;			///< internal position counter 
-    linenr_T    toplnum;		///< top buffer line
-    linenr_T    botlnum;		///< bottom buffer line
+    llpos_T     pos[MAXPOSMATCH];   ///< array of positions
+    int         cur;                ///< internal position counter
+    linenr_T    toplnum;            ///< top buffer line
+    linenr_T    botlnum;            ///< bottom buffer line
 };
 
 /*
@@ -1036,7 +1039,7 @@ struct window_S {
    * Recomputing is minimized by storing the result of computations.
    * Use functions in screen.c to check if they are valid and to update.
    * w_valid is a bitfield of flags, which indicate if specific values are
-   * valid or need to be recomputed.	
+   * valid or need to be recomputed.
    */
   int w_valid;
   pos_T w_valid_cursor;             /* last known position of w_cursor, used
diff --git a/src/nvim/diff.c b/src/nvim/diff.c
index 4bfe67c9d3..2e0b198c13 100644
--- a/src/nvim/diff.c
+++ b/src/nvim/diff.c
@@ -4,11 +4,17 @@
 /// @file diff.c
 ///
 /// Code for diff'ing two, three or four buffers.
+///
+/// There are three ways to diff:
+/// - Shell out to an external diff program, using files.
+/// - Use the compiled-in xdiff library.
+/// - Let 'diffexpr' do the work, using files.
 
 #include <inttypes.h>
 #include <stdbool.h>
 
 #include "nvim/vim.h"
+#include "xdiff/xdiff.h"
 #include "nvim/ascii.h"
 #include "nvim/diff.h"
 #include "nvim/buffer.h"
@@ -36,16 +42,24 @@
 #include "nvim/os/os.h"
 #include "nvim/os/shell.h"
 
-static int diff_busy = FALSE;    // ex_diffgetput() is busy
+static int diff_busy = false;         // using diff structs, don't change them
+static int diff_need_update = false;  // ex_diffupdate needs to be called
 
 // Flags obtained from the 'diffopt' option
-#define DIFF_FILLER     1        // display filler lines
-#define DIFF_ICASE      2        // ignore case
-#define DIFF_IWHITE     4        // ignore change in white space
-#define DIFF_HORIZONTAL 8        // horizontal splits
-#define DIFF_VERTICAL   16       // vertical splits
-#define DIFF_HIDDEN_OFF 32       // diffoff when hidden
-static int diff_flags = DIFF_FILLER;
+#define DIFF_FILLER     0x001   // display filler lines
+#define DIFF_IBLANK     0x002   // ignore empty lines
+#define DIFF_ICASE      0x004   // ignore case
+#define DIFF_IWHITE     0x008   // ignore change in white space
+#define DIFF_IWHITEALL  0x010   // ignore all white space changes
+#define DIFF_IWHITEEOL  0x020   // ignore change in white space at EOL
+#define DIFF_HORIZONTAL 0x040   // horizontal splits
+#define DIFF_VERTICAL   0x080   // vertical splits
+#define DIFF_HIDDEN_OFF 0x100   // diffoff when hidden
+#define DIFF_INTERNAL   0x200   // use internal xdiff algorithm
+#define ALL_WHITE_DIFF (DIFF_IWHITE | DIFF_IWHITEALL | DIFF_IWHITEEOL)
+static int diff_flags = DIFF_INTERNAL | DIFF_FILLER;
+
+static long diff_algorithm = 0;
 
 #define LBUFLEN 50               // length of line in diff file
 
@@ -53,6 +67,25 @@ static int diff_flags = DIFF_FILLER;
 // kNone when not checked yet
 static TriState diff_a_works = kNone;
 
+// used for diff input
+typedef struct {
+    char_u   *din_fname;   // used for external diff
+    mmfile_t  din_mmfile;  // used for internal diff
+} diffin_T;
+
+// used for diff result
+typedef struct {
+    char_u   *dout_fname;  // used for external diff
+    garray_T  dout_ga;     // used for internal diff
+} diffout_T;
+
+// two diff inputs and one result
+typedef struct {
+    diffin_T    dio_orig;      // original file input
+    diffin_T    dio_new;       // new file input
+    diffout_T   dio_diff;      // diff result
+    int         dio_internal;  // using internal diff
+} diffio_T;
 
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "diff.c.generated.h"
@@ -68,10 +101,10 @@ void diff_buf_delete(buf_T *buf)
 
     if (i != DB_COUNT) {
       tp->tp_diffbuf[i] = NULL;
-      tp->tp_diff_invalid = TRUE;
+      tp->tp_diff_invalid = true;
 
       if (tp == curtab) {
-        diff_redraw(TRUE);
+        diff_redraw(true);
       }
     }
   }
@@ -98,8 +131,8 @@ void diff_buf_adjust(win_T *win)
       int i = diff_buf_idx(win->w_buffer);
       if (i != DB_COUNT) {
         curtab->tp_diffbuf[i] = NULL;
-        curtab->tp_diff_invalid = TRUE;
-        diff_redraw(TRUE);
+        curtab->tp_diff_invalid = true;
+        diff_redraw(true);
       }
     }
   } else {
@@ -127,8 +160,8 @@ void diff_buf_add(buf_T *buf)
   for (i = 0; i < DB_COUNT; ++i) {
     if (curtab->tp_diffbuf[i] == NULL) {
       curtab->tp_diffbuf[i] = buf;
-      curtab->tp_diff_invalid = TRUE;
-      diff_redraw(TRUE);
+      curtab->tp_diff_invalid = true;
+      diff_redraw(true);
       return;
     }
   }
@@ -192,9 +225,9 @@ void diff_invalidate(buf_T *buf)
   FOR_ALL_TABS(tp) {
     int i = diff_buf_idx_tp(buf, tp);
     if (i != DB_COUNT) {
-      tp->tp_diff_invalid = TRUE;
+      tp->tp_diff_invalid = true;
       if (tp == curtab) {
-        diff_redraw(TRUE);
+        diff_redraw(true);
       }
     }
   }
@@ -234,6 +267,15 @@ void diff_mark_adjust(linenr_T line1, linenr_T line2, long amount,
 static void diff_mark_adjust_tp(tabpage_T *tp, int idx, linenr_T line1,
                                 linenr_T line2, long amount, long amount_after)
 {
+  if (diff_internal()) {
+    // Will update diffs before redrawing.  Set _invalid to update the
+    // diffs themselves, set _update to also update folds properly just
+    // before redrawing.
+    // Do update marks here, it is needed for :%diffput.
+    tp->tp_diff_invalid = true;
+    tp->tp_diff_update = true;
+  }
+
   int inserted;
   int deleted;
   if (line2 == MAXLNUM) {
@@ -293,14 +335,14 @@ static void diff_mark_adjust_tp(tabpage_T *tp, int idx, linenr_T line1,
 
     //
     // Check for these situations:
-    //	  1  2	3
-    //	  1  2	3
-    // line1     2	3  4  5
-    //	     2	3  4  5
-    //	     2	3  4  5
-    // line2     2	3  4  5
-    //		3     5  6
-    //		3     5  6
+    //    1  2  3
+    //    1  2  3
+    // line1     2  3  4  5
+    //       2  3  4  5
+    //       2  3  4  5
+    // line2     2  3  4  5
+    //      3     5  6
+    //      3     5  6
 
     // compute last line of this change
     last = dp->df_lnum[idx] + dp->df_count[idx] - 1;
@@ -316,7 +358,7 @@ static void diff_mark_adjust_tp(tabpage_T *tp, int idx, linenr_T line1,
         }
         dp->df_lnum[idx] += amount_after;
       } else {
-        int check_unchanged = FALSE;
+        int check_unchanged = false;
 
         // 2. 3. 4. 5.: inserted/deleted lines touching this diff.
         if (deleted > 0) {
@@ -341,7 +383,7 @@ static void diff_mark_adjust_tp(tabpage_T *tp, int idx, linenr_T line1,
               // 5. delete lines at or just before top of diff
               n = off;
               dp->df_count[idx] -= line2 - dp->df_lnum[idx] + 1;
-              check_unchanged = TRUE;
+              check_unchanged = true;
             }
             dp->df_lnum[idx] = line1;
           } else {
@@ -361,7 +403,7 @@ static void diff_mark_adjust_tp(tabpage_T *tp, int idx, linenr_T line1,
               } else {
                 n = line2 - last;
               }
-              check_unchanged = TRUE;
+              check_unchanged = true;
             } else {
               // 3. delete lines inside the diff
               n = 0;
@@ -380,7 +422,7 @@ static void diff_mark_adjust_tp(tabpage_T *tp, int idx, linenr_T line1,
           if (dp->df_lnum[idx] <= line1) {
             // inserted lines somewhere in this diff
             dp->df_count[idx] += inserted;
-            check_unchanged = TRUE;
+            check_unchanged = true;
           } else {
             // inserted lines somewhere above this diff
             dp->df_lnum[idx] += inserted;
@@ -447,12 +489,12 @@ static void diff_mark_adjust_tp(tabpage_T *tp, int idx, linenr_T line1,
   }
 
   if (tp == curtab) {
-    diff_redraw(TRUE);
+    diff_redraw(true);
 
     // Need to recompute the scroll binding, may remove or add filler
     // lines (e.g., when adding lines above w_topline). But it's slow when
     // making many changes, postpone until redrawing.
-    diff_need_scrollbind = TRUE;
+    diff_need_scrollbind = true;
   }
 }
 
@@ -519,7 +561,7 @@ static void diff_check_unchanged(tabpage_T *tp, diff_T *dp)
       }
       char_u *line_org = vim_strsave(ml_get_buf(tp->tp_diffbuf[i_org],
                                                 dp->df_lnum[i_org] + off_org,
-                                                FALSE));
+                                                false));
 
       int i_new;
       for (i_new = i_org + 1; i_new < DB_COUNT; ++i_new) {
@@ -538,7 +580,7 @@ static void diff_check_unchanged(tabpage_T *tp, diff_T *dp)
 
         if (diff_cmp(line_org, ml_get_buf(tp->tp_diffbuf[i_new],
                                           dp->df_lnum[i_new] + off_new,
-                                          FALSE)) != 0) {
+                                          false)) != 0) {
           break;
         }
       }
@@ -612,42 +654,243 @@ static void diff_redraw(int dofold)
       } else if ((n > 0) && (n > wp->w_topfill)) {
         wp->w_topfill = n;
       }
-      check_topfill(wp, FALSE);
+      check_topfill(wp, false);
+    }
+  }
+}
+
+static void clear_diffin(diffin_T *din)
+{
+  if (din->din_fname == NULL) {
+    xfree(din->din_mmfile.ptr);
+    din->din_mmfile.ptr = NULL;
+  } else {
+    os_remove((char *)din->din_fname);
+  }
+}
+
+static void clear_diffout(diffout_T *dout)
+{
+  if (dout->dout_fname == NULL) {
+    ga_clear_strings(&dout->dout_ga);
+  } else {
+    os_remove((char *)dout->dout_fname);
+  }
+}
+
+/// Write buffer "buf" to a memory buffer.
+///
+/// @param buf
+/// @param din
+///
+/// @return FAIL for failure.
+static int diff_write_buffer(buf_T *buf, diffin_T *din)
+{
+  linenr_T   lnum;
+  char_u    *s;
+  long       len = 0;
+  char_u    *ptr;
+
+  // xdiff requires one big block of memory with all the text.
+  for (lnum = 1; lnum <= buf->b_ml.ml_line_count; lnum++) {
+    len += (long)STRLEN(ml_get_buf(buf, lnum, false)) + 1;
+  }
+  ptr = xmalloc(len);
+  if (ptr == NULL) {
+    // Allocating memory failed.  This can happen, because we try to read
+    // the whole buffer text into memory.  Set the failed flag, the diff
+    // will be retried with external diff.  The flag is never reset.
+    buf->b_diff_failed = true;
+    if (p_verbose > 0) {
+      verbose_enter();
+      smsg(_("Not enough memory to use internal diff for buffer \"%s\""),
+           buf->b_fname);
+      verbose_leave();
+    }
+    return FAIL;
+  }
+  din->din_mmfile.ptr = (char *)ptr;
+  din->din_mmfile.size = len;
+
+  len = 0;
+  for (lnum = 1; lnum <= buf->b_ml.ml_line_count; lnum++) {
+    for (s = ml_get_buf(buf, lnum, false); *s != NUL; ) {
+      if (diff_flags & DIFF_ICASE) {
+        int c;
+
+        // xdiff doesn't support ignoring case, fold-case the text.
+        int     orig_len;
+        char_u  cbuf[MB_MAXBYTES + 1];
+
+        c = PTR2CHAR(s);
+        c = enc_utf8 ? utf_fold(c) : TOLOWER_LOC(c);
+        orig_len = MB_PTR2LEN(s);
+        if (utf_char2bytes(c, cbuf) != orig_len) {
+          // TODO(Bram): handle byte length difference
+          memmove(ptr + len, s, orig_len);
+        } else {
+          memmove(ptr + len, cbuf, orig_len);
+        }
+
+        s += orig_len;
+        len += orig_len;
+      } else {
+        ptr[len++] = *s++;
+      }
     }
+    ptr[len++] = NL;
   }
+  return OK;
 }
 
-/// Write buffer "buf" to file "name".
+/// Write buffer "buf" to file or memory buffer.
 ///
 /// Always use 'fileformat' set to "unix".
 ///
 /// @param buf
-/// @param fname
+/// @param din
 ///
 /// @return FAIL for failure
-static int diff_write(buf_T *buf, char_u *fname)
+static int diff_write(buf_T *buf, diffin_T *din)
 {
+  if (din->din_fname == NULL) {
+    return diff_write_buffer(buf, din);
+  }
+
+  // Always use 'fileformat' set to "unix".
   char_u *save_ff = buf->b_p_ff;
   buf->b_p_ff = vim_strsave((char_u *)FF_UNIX);
-  int r = buf_write(buf, fname, NULL, (linenr_T)1, buf->b_ml.ml_line_count,
-                    NULL, FALSE, FALSE, FALSE, TRUE);
+  int r = buf_write(buf, din->din_fname, NULL,
+                    (linenr_T)1, buf->b_ml.ml_line_count,
+                    NULL, false, false, false, true);
   free_string_option(buf->b_p_ff);
   buf->b_p_ff = save_ff;
   return r;
 }
 
+///
+/// Update the diffs for all buffers involved.
+///
+/// @param dio
+/// @param idx_orig
+/// @param eap   can be NULL
+static void diff_try_update(diffio_T    *dio,
+                            int     idx_orig,
+                            exarg_T     *eap)
+{
+  buf_T *buf;
+  int    idx_new;
+
+  if (dio->dio_internal) {
+    ga_init(&dio->dio_diff.dout_ga, sizeof(char *), 1000);
+  } else {
+    // We need three temp file names.
+    dio->dio_orig.din_fname = vim_tempname();
+    dio->dio_new.din_fname = vim_tempname();
+    dio->dio_diff.dout_fname = vim_tempname();
+    if (dio->dio_orig.din_fname == NULL
+        || dio->dio_new.din_fname == NULL
+        || dio->dio_diff.dout_fname == NULL) {
+      goto theend;
+    }
+  }
+
+  // Check external diff is actually working.
+  if (!dio->dio_internal && check_external_diff(dio) == FAIL) {
+    goto theend;
+  }
+
+  // :diffupdate!
+  if (eap != NULL && eap->forceit) {
+    for (idx_new = idx_orig; idx_new < DB_COUNT; idx_new++) {
+      buf = curtab->tp_diffbuf[idx_new];
+      if (buf_valid(buf)) {
+        buf_check_timestamp(buf, false);
+      }
+    }
+  }
+
+  // Write the first buffer to a tempfile or mmfile_t.
+  buf = curtab->tp_diffbuf[idx_orig];
+  if (diff_write(buf, &dio->dio_orig) == FAIL) {
+    goto theend;
+  }
+
+  // Make a difference between the first buffer and every other.
+  for (idx_new = idx_orig + 1; idx_new < DB_COUNT; idx_new++) {
+    buf = curtab->tp_diffbuf[idx_new];
+    if (buf == NULL || buf->b_ml.ml_mfp == NULL) {
+      continue;  // skip buffer that isn't loaded
+    }
+
+    // Write the other buffer and diff with the first one.
+    if (diff_write(buf, &dio->dio_new) == FAIL) {
+      continue;
+    }
+    if (diff_file(dio) == FAIL) {
+      continue;
+    }
+
+    // Read the diff output and add each entry to the diff list.
+    diff_read(idx_orig, idx_new, &dio->dio_diff);
+
+    clear_diffin(&dio->dio_new);
+    clear_diffout(&dio->dio_diff);
+  }
+  clear_diffin(&dio->dio_orig);
+
+theend:
+  xfree(dio->dio_orig.din_fname);
+  xfree(dio->dio_new.din_fname);
+  xfree(dio->dio_diff.dout_fname);
+}
+
+///
+/// Return true if the options are set to use the internal diff library.
+/// Note that if the internal diff failed for one of the buffers, the external
+/// diff will be used anyway.
+///
+int diff_internal(void)
+{
+  return (diff_flags & DIFF_INTERNAL) != 0 && *p_dex == NUL;
+}
+
+///
+/// Return true if the internal diff failed for one of the diff buffers.
+///
+static int diff_internal_failed(void)
+{
+  int idx;
+
+  // Only need to