summaryrefslogtreecommitdiff
path: root/xdiff
diff options
context:
space:
mode:
Diffstat (limited to 'xdiff')
-rw-r--r--xdiff/xdiff.h29
-rw-r--r--xdiff/xdiffi.c12
-rw-r--r--xdiff/xdiffi.h2
-rw-r--r--xdiff/xemit.c43
-rw-r--r--xdiff/xmacros.h1
-rw-r--r--xdiff/xmerge.c130
-rw-r--r--xdiff/xpatience.c381
-rw-r--r--xdiff/xprepare.c3
-rw-r--r--xdiff/xutils.c92
9 files changed, 571 insertions, 122 deletions
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h
index 84fff583e2..711048ea36 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h
@@ -32,6 +32,7 @@ extern "C" {
#define XDF_IGNORE_WHITESPACE (1 << 2)
#define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3)
#define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4)
+#define XDF_PATIENCE_DIFF (1 << 5)
#define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL)
#define XDL_PATCH_NORMAL '-'
@@ -55,11 +56,14 @@ extern "C" {
#define XDL_MERGE_EAGER 1
#define XDL_MERGE_ZEALOUS 2
#define XDL_MERGE_ZEALOUS_ALNUM 3
-#define XDL_MERGE_LEVEL_MASK 0x0f
+
+/* merge favor modes */
+#define XDL_MERGE_FAVOR_OURS 1
+#define XDL_MERGE_FAVOR_THEIRS 2
+#define XDL_MERGE_FAVOR_UNION 3
/* merge output styles */
-#define XDL_MERGE_DIFF3 0x8000
-#define XDL_MERGE_STYLE_MASK 0x8000
+#define XDL_MERGE_DIFF3 1
typedef struct s_mmfile {
char *ptr;
@@ -84,6 +88,7 @@ typedef long (*find_func_t)(const char *line, long line_len, char *buffer, long
typedef struct s_xdemitconf {
long ctxlen;
+ long interhunkctxlen;
unsigned long flags;
find_func_t find_func;
void *find_func_priv;
@@ -106,9 +111,21 @@ long xdl_mmfile_size(mmfile_t *mmf);
int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
xdemitconf_t const *xecfg, xdemitcb_t *ecb);
-int xdl_merge(mmfile_t *orig, mmfile_t *mf1, const char *name1,
- mmfile_t *mf2, const char *name2,
- xpparam_t const *xpp, int level, mmbuffer_t *result);
+typedef struct s_xmparam {
+ xpparam_t xpp;
+ int marker_size;
+ int level;
+ int favor;
+ int style;
+ const char *ancestor; /* label for orig */
+ const char *file1; /* label for mf1 */
+ const char *file2; /* label for mf2 */
+} xmparam_t;
+
+#define DEFAULT_CONFLICT_MARKER_SIZE 7
+
+int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2,
+ xmparam_t const *xmp, mmbuffer_t *result);
#ifdef __cplusplus
}
diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 9d0324a38c..da67c04357 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -26,7 +26,7 @@
#define XDL_MAX_COST_MIN 256
#define XDL_HEUR_MIN_COST 256
-#define XDL_LINE_MAX (long)((1UL << (8 * sizeof(long) - 1)) - 1)
+#define XDL_LINE_MAX (long)((1UL << (CHAR_BIT * sizeof(long) - 1)) - 1)
#define XDL_SNAKE_CNT 20
#define XDL_K_HEUR 4
@@ -293,15 +293,14 @@ int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1,
for (; off1 < lim1; off1++)
rchg1[rindex1[off1]] = 1;
} else {
- long ec;
xdpsplit_t spl;
spl.i1 = spl.i2 = 0;
/*
* Divide ...
*/
- if ((ec = xdl_split(ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb,
- need_min, &spl, xenv)) < 0) {
+ if (xdl_split(ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb,
+ need_min, &spl, xenv) < 0) {
return -1;
}
@@ -329,6 +328,9 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
xdalgoenv_t xenv;
diffdata_t dd1, dd2;
+ if (xpp->flags & XDF_PATIENCE_DIFF)
+ return xdl_do_patience_diff(mf1, mf2, xpp, xe);
+
if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {
return -1;
@@ -454,7 +456,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
/*
* Record the end-of-group position in case we are matched
* with a group of changes in the other file (that is, the
- * change record before the enf-of-group index in the other
+ * change record before the end-of-group index in the other
* file is set).
*/
ixref = rchgo[ixo - 1] ? ix: nrec;
diff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h
index 3e099dc445..ad033a8e6a 100644
--- a/xdiff/xdiffi.h
+++ b/xdiff/xdiffi.h
@@ -55,5 +55,7 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr);
void xdl_free_script(xdchange_t *xscr);
int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
xdemitconf_t const *xecfg);
+int xdl_do_patience_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
+ xdfenv_t *env);
#endif /* #if !defined(XDIFFI_H) */
diff --git a/xdiff/xemit.c b/xdiff/xemit.c
index 4625c1b421..277e2eec5b 100644
--- a/xdiff/xemit.c
+++ b/xdiff/xemit.c
@@ -59,9 +59,10 @@ static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t *
*/
xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg) {
xdchange_t *xch, *xchp;
+ long max_common = 2 * xecfg->ctxlen + xecfg->interhunkctxlen;
for (xchp = xscr, xch = xscr->next; xch; xchp = xch, xch = xch->next)
- if (xch->i1 - (xchp->i1 + xchp->chg1) > 2 * xecfg->ctxlen)
+ if (xch->i1 - (xchp->i1 + xchp->chg1) > max_common)
break;
return xchp;
@@ -84,27 +85,6 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)
return -1;
}
-static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,
- find_func_t ff, void *ff_priv) {
-
- /*
- * Be quite stupid about this for now. Find a line in the old file
- * before the start of the hunk (and context) which starts with a
- * plausible character.
- */
-
- const char *rec;
- long len;
-
- while (i-- > 0) {
- len = xdl_get_rec(xf, i, &rec);
- if ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0)
- return;
- }
- *ll = 0;
-}
-
-
static int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
xdemitconf_t const *xecfg) {
xdfile_t *xdf = &xe->xdf1;
@@ -126,12 +106,13 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
xdchange_t *xch, *xche;
char funcbuf[80];
long funclen = 0;
+ long funclineprev = -1;
find_func_t ff = xecfg->find_func ? xecfg->find_func : def_ff;
if (xecfg->flags & XDL_EMIT_COMMON)
return xdl_emit_common(xe, xscr, ecb, xecfg);
- for (xch = xche = xscr; xch; xch = xche->next) {
+ for (xch = xscr; xch; xch = xche->next) {
xche = xdl_get_hunk(xch, xecfg);
s1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0);
@@ -149,9 +130,19 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
*/
if (xecfg->flags & XDL_EMIT_FUNCNAMES) {
- xdl_find_func(&xe->xdf1, s1, funcbuf,
- sizeof(funcbuf), &funclen,
- ff, xecfg->find_func_priv);
+ long l;
+ for (l = s1 - 1; l >= 0 && l > funclineprev; l--) {
+ const char *rec;
+ long reclen = xdl_get_rec(&xe->xdf1, l, &rec);
+ long newfunclen = ff(rec, reclen, funcbuf,
+ sizeof(funcbuf),
+ xecfg->find_func_priv);
+ if (newfunclen >= 0) {
+ funclen = newfunclen;
+ break;
+ }
+ }
+ funclineprev = s1 - 1;
}
if (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,
funcbuf, funclen, ecb) < 0)
diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h
index 8ef232cfad..165a895a93 100644
--- a/xdiff/xmacros.h
+++ b/xdiff/xmacros.h
@@ -30,6 +30,7 @@
#define XDL_MAX(a, b) ((a) > (b) ? (a): (b))
#define XDL_ABS(v) ((v) >= 0 ? (v): -(v))
#define XDL_ISDIGIT(c) ((c) >= '0' && (c) <= '9')
+#define XDL_ISSPACE(c) (isspace((unsigned char)(c)))
#define XDL_ADDBITS(v,b) ((v) + ((v) >> (b)))
#define XDL_MASKBITS(b) ((1UL << (b)) - 1)
#define XDL_HASHLONG(v,b) (XDL_ADDBITS((unsigned long)(v), b) & XDL_MASKBITS(b))
diff --git a/xdiff/xmerge.c b/xdiff/xmerge.c
index d9737f04c2..9e13b25abc 100644
--- a/xdiff/xmerge.c
+++ b/xdiff/xmerge.c
@@ -28,6 +28,7 @@ typedef struct s_xdmerge {
* 0 = conflict,
* 1 = no conflict, take first,
* 2 = no conflict, take second.
+ * 3 = no conflict, take both.
*/
int mode;
/*
@@ -144,13 +145,16 @@ static int xdl_orig_copy(xdfenv_t *xe, int i, int count, int add_nl, char *dest)
static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1,
xdfenv_t *xe2, const char *name2,
+ const char *name3,
int size, int i, int style,
- xdmerge_t *m, char *dest)
+ xdmerge_t *m, char *dest, int marker_size)
{
- const int marker_size = 7;
int marker1_size = (name1 ? strlen(name1) + 1 : 0);
int marker2_size = (name2 ? strlen(name2) + 1 : 0);
- int j;
+ int marker3_size = (name3 ? strlen(name3) + 1 : 0);
+
+ if (marker_size <= 0)
+ marker_size = DEFAULT_CONFLICT_MARKER_SIZE;
/* Before conflicting part */
size += xdl_recs_copy(xe1, i, m->i1 - i, 0,
@@ -159,8 +163,8 @@ static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1,
if (!dest) {
size += marker_size + 1 + marker1_size;
} else {
- for (j = 0; j < marker_size; j++)
- dest[size++] = '<';
+ memset(dest + size, '<', marker_size);
+ size += marker_size;
if (marker1_size) {
dest[size] = ' ';
memcpy(dest + size + 1, name1, marker1_size - 1);
@@ -176,10 +180,15 @@ static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1,
if (style == XDL_MERGE_DIFF3) {
/* Shared preimage */
if (!dest) {
- size += marker_size + 1;
+ size += marker_size + 1 + marker3_size;
} else {
- for (j = 0; j < marker_size; j++)
- dest[size++] = '|';
+ memset(dest + size, '|', marker_size);
+ size += marker_size;
+ if (marker3_size) {
+ dest[size] = ' ';
+ memcpy(dest + size + 1, name3, marker3_size - 1);
+ size += marker3_size;
+ }
dest[size++] = '\n';
}
size += xdl_orig_copy(xe1, m->i0, m->chg0, 1,
@@ -189,8 +198,8 @@ static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1,
if (!dest) {
size += marker_size + 1;
} else {
- for (j = 0; j < marker_size; j++)
- dest[size++] = '=';
+ memset(dest + size, '=', marker_size);
+ size += marker_size;
dest[size++] = '\n';
}
@@ -200,8 +209,8 @@ static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1,
if (!dest) {
size += marker_size + 1 + marker2_size;
} else {
- for (j = 0; j < marker_size; j++)
- dest[size++] = '>';
+ memset(dest + size, '>', marker_size);
+ size += marker_size;
if (marker2_size) {
dest[size] = ' ';
memcpy(dest + size + 1, name2, marker2_size - 1);
@@ -214,22 +223,35 @@ static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1,
static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1,
xdfenv_t *xe2, const char *name2,
- xdmerge_t *m, char *dest, int style)
+ const char *ancestor_name,
+ int favor,
+ xdmerge_t *m, char *dest, int style,
+ int marker_size)
{
int size, i;
for (size = i = 0; m; m = m->next) {
+ if (favor && !m->mode)
+ m->mode = favor;
+
if (m->mode == 0)
size = fill_conflict_hunk(xe1, name1, xe2, name2,
- size, i, style, m, dest);
- else if (m->mode == 1)
- size += xdl_recs_copy(xe1, i, m->i1 + m->chg1 - i, 0,
+ ancestor_name,
+ size, i, style, m, dest,
+ marker_size);
+ else if (m->mode & 3) {
+ /* Before conflicting part */
+ size += xdl_recs_copy(xe1, i, m->i1 - i, 0,
dest ? dest + size : NULL);
- else if (m->mode == 2)
- size += xdl_recs_copy(xe2, m->i2 - m->i1 + i,
- m->i1 + m->chg2 - i, 0,
- dest ? dest + size : NULL);
- else
+ /* Postimage from side #1 */
+ if (m->mode & 1)
+ size += xdl_recs_copy(xe1, m->i1, m->chg1, 1,
+ dest ? dest + size : NULL);
+ /* Postimage from side #2 */
+ if (m->mode & 2)
+ size += xdl_recs_copy(xe2, m->i2, m->chg2, 1,
+ dest ? dest + size : NULL);
+ } else
continue;
i = m->i1 + m->chg1;
}
@@ -314,7 +336,7 @@ static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
static int line_contains_alnum(const char *ptr, long size)
{
while (size--)
- if (isalnum(*(ptr++)))
+ if (isalnum((unsigned char)*(ptr++)))
return 1;
return 0;
}
@@ -384,13 +406,19 @@ static int xdl_simplify_non_conflicts(xdfenv_t *xe1, xdmerge_t *m,
*
* returns < 0 on error, == 0 for no conflicts, else number of conflicts
*/
-static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1, const char *name1,
- xdfenv_t *xe2, xdchange_t *xscr2, const char *name2,
- int flags, xpparam_t const *xpp, mmbuffer_t *result) {
+static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
+ xdfenv_t *xe2, xdchange_t *xscr2,
+ xmparam_t const *xmp, mmbuffer_t *result)
+{
xdmerge_t *changes, *c;
+ xpparam_t const *xpp = &xmp->xpp;
+ const char *const ancestor_name = xmp->ancestor;
+ const char *const name1 = xmp->file1;
+ const char *const name2 = xmp->file2;
int i0, i1, i2, chg0, chg1, chg2;
- int level = flags & XDL_MERGE_LEVEL_MASK;
- int style = flags & XDL_MERGE_STYLE_MASK;
+ int level = xmp->level;
+ int style = xmp->style;
+ int favor = xmp->favor;
if (style == XDL_MERGE_DIFF3) {
/*
@@ -522,26 +550,31 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1, const char *name1,
}
/* output */
if (result) {
+ int marker_size = xmp->marker_size;
int size = xdl_fill_merge_buffer(xe1, name1, xe2, name2,
- changes, NULL, style);
+ ancestor_name,
+ favor, changes, NULL, style,
+ marker_size);
result->ptr = xdl_malloc(size);
if (!result->ptr) {
xdl_cleanup_merge(changes);
return -1;
}
result->size = size;
- xdl_fill_merge_buffer(xe1, name1, xe2, name2, changes,
- result->ptr, style);
+ xdl_fill_merge_buffer(xe1, name1, xe2, name2,
+ ancestor_name, favor, changes,
+ result->ptr, style, marker_size);
}
return xdl_cleanup_merge(changes);
}
-int xdl_merge(mmfile_t *orig, mmfile_t *mf1, const char *name1,
- mmfile_t *mf2, const char *name2,
- xpparam_t const *xpp, int flags, mmbuffer_t *result) {
+int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2,
+ xmparam_t const *xmp, mmbuffer_t *result)
+{
xdchange_t *xscr1, *xscr2;
xdfenv_t xe1, xe2;
int status;
+ xpparam_t const *xpp = &xmp->xpp;
result->ptr = NULL;
result->size = 0;
@@ -563,23 +596,22 @@ int xdl_merge(mmfile_t *orig, mmfile_t *mf1, const char *name1,
return -1;
}
status = 0;
- if (xscr1 || xscr2) {
- if (!xscr1) {
- result->ptr = xdl_malloc(mf2->size);
- memcpy(result->ptr, mf2->ptr, mf2->size);
- result->size = mf2->size;
- } else if (!xscr2) {
- result->ptr = xdl_malloc(mf1->size);
- memcpy(result->ptr, mf1->ptr, mf1->size);
- result->size = mf1->size;
- } else {
- status = xdl_do_merge(&xe1, xscr1, name1,
- &xe2, xscr2, name2,
- flags, xpp, result);
- }
- xdl_free_script(xscr1);
- xdl_free_script(xscr2);
+ if (!xscr1) {
+ result->ptr = xdl_malloc(mf2->size);
+ memcpy(result->ptr, mf2->ptr, mf2->size);
+ result->size = mf2->size;
+ } else if (!xscr2) {
+ result->ptr = xdl_malloc(mf1->size);
+ memcpy(result->ptr, mf1->ptr, mf1->size);
+ result->size = mf1->size;
+ } else {
+ status = xdl_do_merge(&xe1, xscr1,
+ &xe2, xscr2,
+ xmp, result);
}
+ xdl_free_script(xscr1);
+ xdl_free_script(xscr2);
+
xdl_free_env(&xe1);
xdl_free_env(&xe2);
diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c
new file mode 100644
index 0000000000..e42c16a807
--- /dev/null
+++ b/xdiff/xpatience.c
@@ -0,0 +1,381 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003-2009 Davide Libenzi, Johannes E. Schindelin
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+#include "xinclude.h"
+#include "xtypes.h"
+#include "xdiff.h"
+
+/*
+ * The basic idea of patience diff is to find lines that are unique in
+ * both files. These are intuitively the ones that we want to see as
+ * common lines.
+ *
+ * The maximal ordered sequence of such line pairs (where ordered means
+ * that the order in the sequence agrees with the order of the lines in
+ * both files) naturally defines an initial set of common lines.
+ *
+ * Now, the algorithm tries to extend the set of common lines by growing
+ * the line ranges where the files have identical lines.
+ *
+ * Between those common lines, the patience diff algorithm is applied
+ * recursively, until no unique line pairs can be found; these line ranges
+ * are handled by the well-known Myers algorithm.
+ */
+
+#define NON_UNIQUE ULONG_MAX
+
+/*
+ * This is a hash mapping from line hash to line numbers in the first and
+ * second file.
+ */
+struct hashmap {
+ int nr, alloc;
+ struct entry {
+ unsigned long hash;
+ /*
+ * 0 = unused entry, 1 = first line, 2 = second, etc.
+ * line2 is NON_UNIQUE if the line is not unique
+ * in either the first or the second file.
+ */
+ unsigned long line1, line2;
+ /*
+ * "next" & "previous" are used for the longest common
+ * sequence;
+ * initially, "next" reflects only the order in file1.
+ */
+ struct entry *next, *previous;
+ } *entries, *first, *last;
+ /* were common records found? */
+ unsigned long has_matches;
+ mmfile_t *file1, *file2;
+ xdfenv_t *env;
+ xpparam_t const *xpp;
+};
+
+/* The argument "pass" is 1 for the first file, 2 for the second. */
+static void insert_record(int line, struct hashmap *map, int pass)
+{
+ xrecord_t **records = pass == 1 ?
+ map->env->xdf1.recs : map->env->xdf2.recs;
+ xrecord_t *record = records[line - 1], *other;
+ /*
+ * After xdl_prepare_env() (or more precisely, due to
+ * xdl_classify_record()), the "ha" member of the records (AKA lines)
+ * is _not_ the hash anymore, but a linearized version of it. In
+ * other words, the "ha" member is guaranteed to start with 0 and
+ * the second record's ha can only be 0 or 1, etc.
+ *
+ * So we multiply ha by 2 in the hope that the hashing was
+ * "unique enough".
+ */
+ int index = (int)((record->ha << 1) % map->alloc);
+
+ while (map->entries[index].line1) {
+ other = map->env->xdf1.recs[map->entries[index].line1 - 1];
+ if (map->entries[index].hash != record->ha ||
+ !xdl_recmatch(record->ptr, record->size,
+ other->ptr, other->size,
+ map->xpp->flags)) {
+ if (++index >= map->alloc)
+ index = 0;
+ continue;
+ }
+ if (pass == 2)
+ map->has_matches = 1;
+ if (pass == 1 || map->entries[index].line2)
+ map->entries[index].line2 = NON_UNIQUE;
+ else
+ map->entries[index].line2 = line;
+ return;
+ }
+ if (pass == 2)
+ return;
+ map->entries[index].line1 = line;
+ map->entries[index].hash = record->ha;
+ if (!map->first)
+ map->first = map->entries + index;
+ if (map->last) {
+ map->last->next = map->entries + index;
+ map->entries[index].previous = map->last;
+ }
+ map->last = map->entries + index;
+ map->nr++;
+}
+
+/*
+ * This function has to be called for each recursion into the inter-hunk
+ * parts, as previously non-unique lines can become unique when being
+ * restricted to a smaller part of the files.
+ *
+ * It is assumed that env has been prepared using xdl_prepare().
+ */
+static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,
+ xpparam_t const *xpp, xdfenv_t *env,
+ struct hashmap *result,
+ int line1, int count1, int line2, int count2)
+{
+ result->file1 = file1;
+ result->file2 = file2;
+ result->xpp = xpp;
+ result->env = env;
+
+ /* We know exactly how large we want the hash map */
+ result->alloc = count1 * 2;
+ result->entries = (struct entry *)
+ xdl_malloc(result->alloc * sizeof(struct entry));
+ if (!result->entries)
+ return -1;
+ memset(result->entries, 0, result->alloc * sizeof(struct entry));
+
+ /* First, fill with entries from the first file */
+ while (count1--)
+ insert_record(line1++, result, 1);
+
+ /* Then search for matches in the second file */
+ while (count2--)
+ insert_record(line2++, result, 2);
+
+ return 0;
+}
+
+/*
+ * Find the longest sequence with a smaller last element (meaning a smaller
+ * line2, as we construct the sequence with entries ordered by line1).
+ */
+static int binary_search(struct entry **sequence, int longest,
+ struct entry *entry)
+{
+ int left = -1, right = longest;
+
+ while (left + 1 < right) {
+ int middle = (left + right) / 2;
+ /* by construction, no two entries can be equal */
+ if (sequence[middle]->line2 > entry->line2)
+ right = middle;
+ else
+ left = middle;
+ }
+ /* return the index in "sequence", _not_ the sequence length */
+ return left;
+}
+
+/*
+ * The idea is to start with the list of common unique lines sorted by
+ * the order in file1. For each of these pairs, the longest (partial)
+ * sequence whose last element's line2 is smaller is determined.
+ *
+ * For efficiency, the sequences are kept in a list containing exactly one
+ * item per sequence length: the sequence with the smallest last
+ * element (in terms of line2).
+ */
+static struct entry *find_longest_common_sequence(struct hashmap *map)
+{
+ struct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *));
+ int longest = 0, i;
+ struct entry *entry;
+
+ for (entry = map->first; entry; entry = entry->next) {
+ if (!entry->line2 || entry->line2 == NON_UNIQUE)
+ continue;
+ i = binary_search(sequence, longest, entry);
+ entry->previous = i < 0 ? NULL : sequence[i];
+ sequence[++i] = entry;
+ if (i == longest)
+ longest++;
+ }
+
+ /* No common unique lines were found */
+ if (!longest) {
+ xdl_free(sequence);
+ return NULL;
+ }
+
+ /* Iterate starting at the last element, adjusting the "next" members */
+ entry = sequence[longest - 1];
+ entry->next = NULL;
+ while (entry->previous) {
+ entry->previous->next = entry;
+ entry = entry->previous;
+ }
+ xdl_free(sequence);
+ return entry;
+}
+
+static int match(struct hashmap *map, int line1, int line2)
+{
+ xrecord_t *record1 = map->env->xdf1.recs[line1 - 1];
+ xrecord_t *record2 = map->env->xdf2.recs[line2 - 1];
+ return xdl_recmatch(record1->ptr, record1->size,
+ record2->ptr, record2->size, map->xpp->flags);
+}
+
+static int patience_diff(mmfile_t *file1, mmfile_t *file2,
+ xpparam_t const *xpp, xdfenv_t *env,
+ int line1, int count1, int line2, int count2);
+
+static int walk_common_sequence(struct hashmap *map, struct entry *first,
+ int line1, int count1, int line2, int count2)
+{
+ int end1 = line1 + count1, end2 = line2 + count2;
+ int next1, next2;
+
+ for (;;) {
+ /* Try to grow the line ranges of common lines */
+ if (first) {
+ next1 = first->line1;
+ next2 = first->line2;
+ while (next1 > line1 && next2 > line2 &&
+ match(map, next1 - 1, next2 - 1)) {
+ next1--;
+ next2--;
+ }
+ } else {
+ next1 = end1;
+ next2 = end2;
+ }
+ while (line1 < next1 && line2 < next2 &&
+ match(map, line1, line2)) {
+ line1++;
+ line2++;
+ }
+
+ /* Recurse */
+ if (next1 > line1 || next2 > line2) {
+ struct hashmap submap;
+
+ memset(&submap, 0, sizeof(submap));
+ if (patience_diff(map->file1, map->file2,
+ map->xpp, map->env,
+ line1, next1 - line1,
+ line2, next2 - line2))
+ return -1;
+ }
+
+ if (!first)
+ return 0;
+
+ while (first->next &&
+ first->next->line1 == first->line1 + 1 &&
+ first->next->line2 == first->line2 + 1)
+ first = first->next;
+
+ line1 = first->line1 + 1;
+ line2 = first->line2 + 1;
+
+ first = first->next;
+ }
+}
+
+static int fall_back_to_classic_diff(struct hashmap *map,
+ int line1, int count1, int line2, int count2)
+{
+ /*
+ * This probably does not work outside Git, since
+ * we have a very simple mmfile structure.
+ *
+ * Note: ideally, we would reuse the prepared environment, but
+ * the libxdiff interface does not (yet) allow for diffing only
+ * ranges of lines instead of the whole files.
+ */
+ mmfile_t subfile1, subfile2;
+ xpparam_t xpp;
+ xdfenv_t env;
+
+ subfile1.ptr = (char *)map->env->xdf1.recs[line1 - 1]->ptr;
+ subfile1.size = map->env->xdf1.recs[line1 + count1 - 2]->ptr +
+ map->env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;
+ subfile2.ptr = (char *)map->env->xdf2.recs[line2 - 1]->ptr;
+ subfile2.size = map->env->xdf2.recs[line2 + count2 - 2]->ptr +
+ map->env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;
+ xpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF;
+ if (xdl_do_diff(&subfile1, &subfile2, &xpp, &env) < 0)
+ return -1;
+
+ memcpy(map->env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);
+ memcpy(map->env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);
+
+ xdl_free_env(&env);
+
+ return 0;
+}
+
+/*
+ * Recursively find the longest common sequence of unique lines,
+ * and if none was found, ask xdl_do_diff() to do the job.
+ *
+ * This function assumes that env was prepared with xdl_prepare_env().
+ */
+static int patience_diff(mmfile_t *file1, mmfile_t *file2,
+ xpparam_t const *xpp, xdfenv_t *env,
+ int line1, int count1, int line2, int count2)
+{
+ struct hashmap map;
+ struct entry *first;
+ int result = 0;
+
+ /* trivial case: one side is empty */
+ if (!count1) {
+ while(count2--)
+ env->xdf2.rchg[line2++ - 1] = 1;
+ return 0;
+ } else if (!count2) {
+ while(count1--)
+ env->xdf1.rchg[line1++ - 1] = 1;
+ return 0;
+ }
+
+ memset(&map, 0, sizeof(map));
+ if (fill_hashmap(file1, file2, xpp, env, &map,
+ line1, count1, line2, count2))
+ return -1;
+
+ /* are there any matching lines at all? */
+ if (!map.has_matches) {
+ while(count1--)
+ env->xdf1.rchg[line1++ - 1] = 1;
+ while(count2--)
+ env->xdf2.rchg[line2++ - 1] = 1;
+ xdl_free(map.entries);
+ return 0;
+ }
+
+ first = find_longest_common_sequence(&map);
+ if (first)
+ result = walk_common_sequence(&map, first,
+ line1, count1, line2, count2);
+ else
+ result = fall_back_to_classic_diff(&map,
+ line1, count1, line2, count2);
+
+ xdl_free(map.entries);
+ return result;
+}
+
+int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2,
+ xpparam_t const *xpp, xdfenv_t *env)
+{
+ if (xdl_prepare_env(file1, file2, xpp, env) < 0)
+ return -1;
+
+ /* environment is cleaned up in xdl_diff() */
+ return patience_diff(file1, file2, xpp, env,
+ 1, env->xdf1.nrec, 1, env->xdf2.nrec);
+}
diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index a43aa72cd0..1689085235 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c
@@ -290,7 +290,8 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
xdl_free_classifier(&cf);
- if (xdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {
+ if (!(xpp->flags & XDF_PATIENCE_DIFF) &&
+ xdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {
xdl_free_ctx(&xe->xdf2);
xdl_free_ctx(&xe->xdf1);
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index 04ad468702..ab6503460f 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -190,48 +190,68 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
{
int i1, i2;
+ if (s1 == s2 && !memcmp(l1, l2, s1))
+ return 1;
+ if (!(flags & XDF_WHITESPACE_FLAGS))
+ return 0;
+
+ i1 = 0;
+ i2 = 0;
+
+ /*
+ * -w matches everything that matches with -b, and -b in turn
+ * matches everything that matches with --ignore-space-at-eol.
+ *
+ * Each flavor of ignoring needs different logic to skip whitespaces
+ * while we have both sides to compare.
+ */
if (flags & XDF_IGNORE_WHITESPACE) {
- for (i1 = i2 = 0; i1 < s1 && i2 < s2; ) {
- if (isspace(l1[i1]))
- while (isspace(l1[i1]) && i1 < s1)
- i1++;
- if (isspace(l2[i2]))
- while (isspace(l2[i2]) && i2 < s2)
- i2++;
- if (i1 < s1 && i2 < s2 && l1[i1++] != l2[i2++])
+ goto skip_ws;
+ while (i1 < s1 && i2 < s2) {
+ if (l1[i1++] != l2[i2++])
return 0;
+ skip_ws:
+ while (i1 < s1 && XDL_ISSPACE(l1[i1]))
+ i1++;
+ while (i2 < s2 && XDL_ISSPACE(l2[i2]))
+ i2++;
}
- return (i1 >= s1 && i2 >= s2);
} else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
- for (i1 = i2 = 0; i1 < s1 && i2 < s2; ) {
- if (isspace(l1[i1])) {
- if (!isspace(l2[i2]))
- return 0;
- while (isspace(l1[i1]) && i1 < s1)
+ while (i1 < s1 && i2 < s2) {
+ if (XDL_ISSPACE(l1[i1]) && XDL_ISSPACE(l2[i2])) {
+ /* Skip matching spaces and try again */
+ while (i1 < s1 && XDL_ISSPACE(l1[i1]))
i1++;
- while (isspace(l2[i2]) && i2 < s2)
+ while (i2 < s2 && XDL_ISSPACE(l2[i2]))
i2++;
- } else if (l1[i1++] != l2[i2++])
+ continue;
+ }
+ if (l1[i1++] != l2[i2++])
return 0;
}
- return (i1 >= s1 && i2 >= s2);
} else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL) {
- for (i1 = i2 = 0; i1 < s1 && i2 < s2; ) {
- if (l1[i1] != l2[i2]) {
- while (i1 < s1 && isspace(l1[i1]))
- i1++;
- while (i2 < s2 && isspace(l2[i2]))
- i2++;
- if (i1 < s1 || i2 < s2)
- return 0;
- return 1;
- }
+ while (i1 < s1 && i2 < s2 && l1[i1++] == l2[i2++])
+ ; /* keep going */
+ }
+
+ /*
+ * After running out of one side, the remaining side must have
+ * nothing but whitespace for the lines to match. Note that
+ * ignore-whitespace-at-eol case may break out of the loop
+ * while there still are characters remaining on both lines.
+ */
+ if (i1 < s1) {
+ while (i1 < s1 && XDL_ISSPACE(l1[i1]))
i1++;
+ if (s1 != i1)
+ return 0;
+ }
+ if (i2 < s2) {
+ while (i2 < s2 && XDL_ISSPACE(l2[i2]))
i2++;
- }
- return i1 >= s1 && i2 >= s2;
- } else
- return s1 == s2 && !memcmp(l1, l2, s1);
+ return (s2 == i2);
+ }
+ return 1;
}
static unsigned long xdl_hash_record_with_whitespace(char const **data,
@@ -240,20 +260,22 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,
char const *ptr = *data;
for (; ptr < top && *ptr != '\n'; ptr++) {
- if (isspace(*ptr)) {
+ if (XDL_ISSPACE(*ptr)) {
const char *ptr2 = ptr;
- while (ptr + 1 < top && isspace(ptr[1])
+ int at_eol;
+ while (ptr + 1 < top && XDL_ISSPACE(ptr[1])
&& ptr[1] != '\n')
ptr++;
+ at_eol = (top <= ptr + 1 || ptr[1] == '\n');
if (flags & XDF_IGNORE_WHITESPACE)
; /* already handled */
else if (flags & XDF_IGNORE_WHITESPACE_CHANGE
- && ptr[1] != '\n') {
+ && !at_eol) {
ha += (ha << 5);
ha ^= (unsigned long) ' ';
}
else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL
- && ptr[1] != '\n') {
+ && !at_eol) {
while (ptr2 != ptr + 1) {
ha += (ha << 5);
ha ^= (unsigned long) *ptr2;
generated by cgit v1.2.3 (git 2.25.1) at 2025-02-08 01:59:54 +0000