#include "vim.h"

#include "xdiff/xdiff.h"

#if defined(FEAT_DIFF) || defined(PROTO)

static int diff_busy = FALSE; // using diff structs, don't change them

static int diff_need_update = FALSE; // ex_diffupdate needs to be called

#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 */

static int diff_a_works = MAYBE; /* TRUE when "diff -a" works, FALSE when it

#if defined(MSWIN)

static int diff_bin_works = MAYBE; /* TRUE when "diff --binary" works, FALSE

typedef struct {

char_u *din_fname; // used for external diff

mmfile_t din_mmfile; // used for internal diff

} diffin_T;

typedef struct {

char_u *dout_fname; // used for external diff

garray_T dout_ga; // used for internal diff

} diffout_T;

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;

static int diff_buf_idx(buf_T *buf);

static int diff_buf_idx_tp(buf_T *buf, tabpage_T *tp);

static void diff_mark_adjust_tp(tabpage_T *tp, int idx, linenr_T line1, linenr_T line2, long amount, long amount_after);

static void diff_check_unchanged(tabpage_T *tp, diff_T *dp);

static int diff_check_sanity(tabpage_T *tp, diff_T *dp);

static void diff_redraw(int dofold);

static int check_external_diff(diffio_T *diffio);

static int diff_file(diffio_T *diffio);

static int diff_equal_entry(diff_T *dp, int idx1, int idx2);

static int diff_cmp(char_u *s1, char_u *s2);

#ifdef FEAT_FOLDING

static void diff_fold_update(diff_T *dp, int skip_idx);

static void diff_read(int idx_orig, int idx_new, diffout_T *fname);

static void diff_copy_entry(diff_T *dprev, diff_T *dp, int idx_orig, int idx_new);

static diff_T *diff_alloc_new(tabpage_T *tp, diff_T *dprev, diff_T *dp);

static int parse_diff_ed(char_u *line, linenr_T *lnum_orig, long *count_orig, linenr_T *lnum_new, long *count_new);

static int parse_diff_unified(char_u *line, linenr_T *lnum_orig, long *count_orig, linenr_T *lnum_new, long *count_new);

static int xdiff_out(void *priv, mmbuffer_t *mb, int nbuf);

void

diff_buf_delete(buf_T *buf)

{

int i;

tabpage_T *tp;

FOR_ALL_TABPAGES(tp)

{

i = diff_buf_idx_tp(buf, tp);

if (i != DB_COUNT)

{

tp->tp_diffbuf[i] = NULL;

tp->tp_diff_invalid = TRUE;

if (tp == curtab)

diff_redraw(TRUE);

}

}

}

void

diff_buf_adjust(win_T *win)

{

win_T *wp;

int i;

if (!win->w_p_diff)

{

/* When there is no window showing a diff for this buffer, remove

FOR_ALL_WINDOWS(wp)

if (wp->w_buffer == win->w_buffer && wp->w_p_diff)

break;

if (wp == NULL)

{

i = diff_buf_idx(win->w_buffer);

if (i != DB_COUNT)

{

curtab->tp_diffbuf[i] = NULL;

curtab->tp_diff_invalid = TRUE;

diff_redraw(TRUE);

}

}

}

else

diff_buf_add(win->w_buffer);

}

void

diff_buf_add(buf_T *buf)

{

int i;

if (diff_buf_idx(buf) != DB_COUNT)

return; /* It's already there. */

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);

return;

}

semsg(_("E96: Cannot diff more than %d buffers"), DB_COUNT);

}

static void

diff_buf_clear(void)

{

int i;

for (i = 0; i < DB_COUNT; ++i)

if (curtab->tp_diffbuf[i] != NULL)

{

curtab->tp_diffbuf[i] = NULL;

curtab->tp_diff_invalid = TRUE;

diff_redraw(TRUE);

}

}

static int

diff_buf_idx(buf_T *buf)

{

int idx;

for (idx = 0; idx < DB_COUNT; ++idx)

if (curtab->tp_diffbuf[idx] == buf)

break;

return idx;

}

static int

diff_buf_idx_tp(buf_T *buf, tabpage_T *tp)

{

int idx;

for (idx = 0; idx < DB_COUNT; ++idx)

if (tp->tp_diffbuf[idx] == buf)

break;

return idx;

}

void

diff_invalidate(buf_T *buf)

{

tabpage_T *tp;

int i;

FOR_ALL_TABPAGES(tp)

{

i = diff_buf_idx_tp(buf, tp);

if (i != DB_COUNT)

{

tp->tp_diff_invalid = TRUE;

if (tp == curtab)

diff_redraw(TRUE);

}

}

}

void

diff_mark_adjust(

long amount_after)

{

int idx;

tabpage_T *tp;

/* Handle all tab pages that use the current buffer in a diff. */

FOR_ALL_TABPAGES(tp)

{

idx = diff_buf_idx_tp(curbuf, tp);

if (idx != DB_COUNT)

diff_mark_adjust_tp(tp, idx, line1, line2, amount, amount_after);

}

}

static void

diff_mark_adjust_tp(

long amount_after)

{

diff_T *dp;

diff_T *dprev;

diff_T *dnext;

int i;

int inserted, deleted;

int n, off;

linenr_T last;

linenr_T lnum_deleted = line1; /* lnum of remaining deletion */

int check_unchanged;

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;

}

if (line2 == MAXLNUM)

{

/* mark_adjust(99, MAXLNUM, 9, 0): insert lines */

inserted = amount;

deleted = 0;

}

else if (amount_after > 0)

{

/* mark_adjust(99, 98, MAXLNUM, 9): a change that inserts lines*/

inserted = amount_after;

deleted = 0;

}

else

{

/* mark_adjust(98, 99, MAXLNUM, -2): delete lines */

inserted = 0;

deleted = -amount_after;

}

dprev = NULL;

dp = tp->tp_first_diff;

for (;;)

{

/* If the change is after the previous diff block and before the next

if ((dp == NULL || dp->df_lnum[idx] - 1 > line2

|| (line2 == MAXLNUM && dp->df_lnum[idx] > line1))

&& (dprev == NULL

|| dprev->df_lnum[idx] + dprev->df_count[idx] < line1)

&& !diff_busy)

{

dnext = diff_alloc_new(tp, dprev, dp);

if (dnext == NULL)

return;

dnext->df_lnum[idx] = line1;

dnext->df_count[idx] = inserted;

for (i = 0; i < DB_COUNT; ++i)

if (tp->tp_diffbuf[i] != NULL && i != idx)

{

if (dprev == NULL)

dnext->df_lnum[i] = line1;

else

dnext->df_lnum[i] = line1

+ (dprev->df_lnum[i] + dprev->df_count[i])

- (dprev->df_lnum[idx] + dprev->df_count[idx]);

dnext->df_count[i] = deleted;

}

}

/* if at end of the list, quit */

if (dp == NULL)

break;

/*

/* compute last line of this change */

last = dp->df_lnum[idx] + dp->df_count[idx] - 1;

/* 1. change completely above line1: nothing to do */

if (last >= line1 - 1)

{

/* 6. change below line2: only adjust for amount_after; also when

if (dp->df_lnum[idx] - (deleted + inserted != 0) > line2)

{

if (amount_after == 0)

break; /* nothing left to change */

dp->df_lnum[idx] += amount_after;

}

else

{

check_unchanged = FALSE;

/* 2. 3. 4. 5.: inserted/deleted lines touching this diff. */

if (deleted > 0)

{

if (dp->df_lnum[idx] >= line1)

{

off = dp->df_lnum[idx] - lnum_deleted;

if (last <= line2)

{

/* 4. delete all lines of diff */

if (dp->df_next != NULL

&& dp->df_next->df_lnum[idx] - 1 <= line2)

{

/* delete continues in next diff, only do

n = dp->df_next->df_lnum[idx] - lnum_deleted;

deleted -= n;

n -= dp->df_count[idx];

lnum_deleted = dp->df_next->df_lnum[idx];

}

else

n = deleted - dp->df_count[idx];

dp->df_count[idx] = 0;

}

else

{

/* 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;

}

dp->df_lnum[idx] = line1;

}

else

{

off = 0;

if (last < line2)

{

/* 2. delete at end of of diff */

dp->df_count[idx] -= last - lnum_deleted + 1;

if (dp->df_next != NULL

&& dp->df_next->df_lnum[idx] - 1 <= line2)

{

/* delete continues in next diff, only do

n = dp->df_next->df_lnum[idx] - 1 - last;

deleted -= dp->df_next->df_lnum[idx]

- lnum_deleted;

lnum_deleted = dp->df_next->df_lnum[idx];

}

else

n = line2 - last;

check_unchanged = TRUE;

}

else

{

/* 3. delete lines inside the diff */

n = 0;

dp->df_count[idx] -= deleted;

}

}

for (i = 0; i < DB_COUNT; ++i)

if (tp->tp_diffbuf[i] != NULL && i != idx)

{

dp->df_lnum[i] -= off;

dp->df_count[i] += n;

}

}

else

{

if (dp->df_lnum[idx] <= line1)

{

/* inserted lines somewhere in this diff */

dp->df_count[idx] += inserted;

check_unchanged = TRUE;

}

else

/* inserted lines somewhere above this diff */

dp->df_lnum[idx] += inserted;

}

if (check_unchanged)

/* Check if inserted lines are equal, may reduce the

diff_check_unchanged(tp, dp);

}

}

/* check if this block touches the previous one, may merge them. */

if (dprev != NULL && dprev->df_lnum[idx] + dprev->df_count[idx]

== dp->df_lnum[idx])

{

for (i = 0; i < DB_COUNT; ++i)

if (tp->tp_diffbuf[i] != NULL)

dprev->df_count[i] += dp->df_count[i];

dprev->df_next = dp->df_next;

vim_free(dp);

dp = dprev->df_next;

}

else

{

/* Advance to next entry. */

dprev = dp;

dp = dp->df_next;

}

}

dprev = NULL;

dp = tp->tp_first_diff;

while (dp != NULL)

{

/* All counts are zero, remove this entry. */

for (i = 0; i < DB_COUNT; ++i)

if (tp->tp_diffbuf[i] != NULL && dp->df_count[i] != 0)

break;

if (i == DB_COUNT)

{

dnext = dp->df_next;

vim_free(dp);

dp = dnext;

if (dprev == NULL)

tp->tp_first_diff = dnext;

else

dprev->df_next = dnext;

}

else

{

/* Advance to next entry. */

dprev = dp;

dp = dp->df_next;

}

}

if (tp == curtab)

{

diff_redraw(TRUE);

/* Need to recompute the scroll binding, may remove or add filler

diff_need_scrollbind = TRUE;

}

}

static diff_T *

diff_alloc_new(tabpage_T *tp, diff_T *dprev, diff_T *dp)

{

diff_T *dnew;

dnew = (diff_T *)alloc((unsigned)sizeof(diff_T));

if (dnew != NULL)

{

dnew->df_next = dp;

if (dprev == NULL)

tp->tp_first_diff = dnew;

else

dprev->df_next = dnew;

}

return dnew;

}

static void

diff_check_unchanged(tabpage_T *tp, diff_T *dp)

{

int i_org;

int i_new;

int off_org, off_new;

char_u *line_org;

int dir = FORWARD;

/* Find the first buffers, use it as the original, compare the other

for (i_org = 0; i_org < DB_COUNT; ++i_org)

if (tp->tp_diffbuf[i_org] != NULL)

break;

if (i_org == DB_COUNT) /* safety check */

return;

if (diff_check_sanity(tp, dp) == FAIL)

return;

/* First check lines at the top, then at the bottom. */

off_org = 0;

off_new = 0;

for (;;)

{

/* Repeat until a line is found which is different or the number of

while (dp->df_count[i_org] > 0)

{

/* Copy the line, the next ml_get() will invalidate it. */

if (dir == BACKWARD)

off_org = dp->df_count[i_org] - 1;

line_org = vim_strsave(ml_get_buf(tp->tp_diffbuf[i_org],

dp->df_lnum[i_org] + off_org, FALSE));

if (line_org == NULL)

return;

for (i_new = i_org + 1; i_new < DB_COUNT; ++i_new)

{

if (tp->tp_diffbuf[i_new] == NULL)

continue;

if (dir == BACKWARD)

off_new = dp->df_count[i_new] - 1;

/* if other buffer doesn't have this line, it was inserted */

if (off_new < 0 || off_new >= dp->df_count[i_new])

break;

if (diff_cmp(line_org, ml_get_buf(tp->tp_diffbuf[i_new],

dp->df_lnum[i_new] + off_new, FALSE)) != 0)

break;

}

vim_free(line_org);

/* Stop when a line isn't equal in all diff buffers. */

if (i_new != DB_COUNT)

break;

/* Line matched in all buffers, remove it from the diff. */

for (i_new = i_org; i_new < DB_COUNT; ++i_new)

if (tp->tp_diffbuf[i_new] != NULL)

{

if (dir == FORWARD)

++dp->df_lnum[i_new];

--dp->df_count[i_new];

}

}

if (dir == BACKWARD)

break;

dir = BACKWARD;

}

}

static int

diff_check_sanity(tabpage_T *tp, diff_T *dp)

{

int i;

for (i = 0; i < DB_COUNT; ++i)

if (tp->tp_diffbuf[i] != NULL)

if (dp->df_lnum[i] + dp->df_count[i] - 1

> tp->tp_diffbuf[i]->b_ml.ml_line_count)

return FAIL;

return OK;

}

static void

diff_redraw(

int dofold) // also recompute the folds

{

win_T *wp;

int n;

FOR_ALL_WINDOWS(wp)

if (wp->w_p_diff)

{

redraw_win_later(wp, SOME_VALID);

#ifdef FEAT_FOLDING

if (dofold && foldmethodIsDiff(wp))

foldUpdateAll(wp);

/* A change may have made filler lines invalid, need to take care

n = diff_check(wp, wp->w_topline);

if ((wp != curwin && wp->w_topfill > 0) || n > 0)

{

if (wp->w_topfill > n)

wp->w_topfill = (n < 0 ? 0 : n);

else if (n > 0 && n > wp->w_topfill)

wp->w_topfill = n;

check_topfill(wp, FALSE);

}

}

}

static void

clear_diffin(diffin_T *din)

{

if (din->din_fname == NULL)

{

vim_free(din->din_mmfile.ptr);

din->din_mmfile.ptr = NULL;

}

else

mch_remove(din->din_fname);

}

static void

clear_diffout(diffout_T *dout)

{

if (dout->dout_fname == NULL)

ga_clear_strings(&dout->dout_ga);

else

mch_remove(dout->dout_fname);

}

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 = lalloc(len, TRUE);

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;

int orig_len;

char_u cbuf[MB_MAXBYTES + 1];

// xdiff doesn't support ignoring case, fold-case the text.

c = PTR2CHAR(s);

c = enc_utf8 ? utf_fold(c) : MB_TOLOWER(c);

orig_len = MB_PTR2LEN(s);

if (mb_char2bytes(c, cbuf) != orig_len)

// TODO: handle byte length difference

mch_memmove(ptr + len, s, orig_len);

else

mch_memmove(ptr + len, cbuf, orig_len);

s += orig_len;

len += orig_len;

}

else

ptr[len++] = *s++;

}

ptr[len++] = NL;

}

return OK;

}

static int

diff_write(buf_T *buf, diffin_T *din)

{

int r;

char_u *save_ff;

if (din->din_fname == NULL)

return diff_write_buffer(buf, din);

// Always use 'fileformat' set to "unix".

save_ff = buf->b_p_ff;

buf->b_p_ff = vim_strsave((char_u *)FF_UNIX);

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;

}

static void

diff_try_update(

diffio_T *dio,

int idx_orig,

exarg_T *eap) // "eap" can be NULL

{

buf_T *buf;

int idx_new;

if (dio->dio_internal)

{

ga_init2(&dio->dio_diff.dout_ga, sizeof(char *), 1000);

}

else

{

// We need three temp file names.

dio->dio_orig.din_fname = vim_tempname('o', TRUE);

dio->dio_new.din_fname = vim_tempname('n', TRUE);

dio->dio_diff.dout_fname = vim_tempname('d', TRUE);

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:

vim_free(dio->dio_orig.din_fname);

vim_free(dio->dio_new.din_fname);

vim_free(dio->dio_diff.dout_fname);

}

int

diff_internal(void)

{

return (diff_flags & DIFF_INTERNAL) != 0

#ifdef FEAT_EVAL

&& *p_dex == NUL

;

}

static int

diff_internal_failed(void)

{

int idx;

// Only need to do something when there is another buffer.

for (idx = 0; idx < DB_COUNT; ++idx)

if (curtab->tp_diffbuf[idx] != NULL

&& curtab->tp_diffbuf[idx]->b_diff_failed)

return TRUE;

return FALSE;

}

void

ex_diffupdate(exarg_T *eap) // "eap" can be NULL

{

int idx_orig;

int idx_new;

diffio_T diffio;

int had_diffs = curtab->tp_first_diff != NULL;

if (diff_busy)

{

diff_need_update = TRUE;

return;

}

// Delete all diffblocks.

diff_clear(curtab);

curtab->tp_diff_invalid = FALSE;

// Use the first buffer as the original text.

for (idx_orig = 0; idx_orig < DB_COUNT; ++idx_orig)

if (curtab->tp_diffbuf[idx_orig] != NULL)

break;

if (idx_orig == DB_COUNT)

goto theend;

// Only need to do something when there is another buffer.

for (idx_new = idx_orig + 1; idx_new < DB_COUNT; ++idx_new)

if (curtab->tp_diffbuf[idx_new] != NULL)

break;

if (idx_new == DB_COUNT)

goto theend;

// Only use the internal method if it did not fail for one of the buffers.

vim_memset(&diffio, 0, sizeof(diffio));

diffio.dio_internal = diff_internal() && !diff_internal_failed();

diff_try_update(&diffio, idx_orig, eap);

if (diffio.dio_internal && diff_internal_failed())

{

// Internal diff failed, use external diff instead.

vim_memset(&diffio, 0, sizeof(diffio));

diff_try_update(&diffio, idx_orig, eap);

}

// force updating cursor position on screen

curwin->w_valid_cursor.lnum = 0;

theend:

// A redraw is needed if there were diffs and they were cleared, or there

// are diffs now, which means they got updated.

if (had_diffs || curtab->tp_first_diff != NULL)

{

diff_redraw(TRUE);

apply_autocmds(EVENT_DIFFUPDATED, NULL, NULL, FALSE, curbuf);

}

}

static int

check_external_diff(diffio_T *diffio)

{

FILE *fd;

int ok;

int io_error = FALSE;

// May try twice, first with "-a" and then without.

for (;;)

{

ok = FALSE;

fd = mch_fopen((char *)diffio->dio_orig.din_fname, "w");

if (fd == NULL)

io_error = TRUE;

else

{

if (fwrite("line1\n", (size_t)6, (size_t)1, fd) != 1)

io_error = TRUE;

fclose(fd);

fd = mch_fopen((char *)diffio->dio_new.din_fname, "w");

if (fd == NULL)

io_error = TRUE;

else

{

if (fwrite("line2\n", (size_t)6, (size_t)1, fd) != 1)

io_error = TRUE;

fclose(fd);

fd = NULL;

if (diff_file(diffio) == OK)

fd = mch_fopen((char *)diffio->dio_diff.dout_fname, "r");

if (fd == NULL)

io_error = TRUE;

else

{

char_u linebuf[LBUFLEN];

for (;;)

{

/* There must be a line that contains "1c1". */

if (vim_fgets(linebuf, LBUFLEN, fd))

break;