{"thread":{"id":"43116","subject":"Re: [PATCH] xdiff: add xdl_merge() (was: (unknown))","startedAt":"2006-11-21T22:24:34Z","lastAt":"2006-11-22T20:16:58Z","messageCount":5,"participants":["Jakub Narebski","Johannes Schindelin","Ramsay Jones","Davide Libenzi"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"296153","messageId":"Pine.LNX.4.63.0611212316080.26827@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"43116","inReplyTo":null,"subject":"(unknown)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-11-21T22:24:34Z","receivedAt":"2006-11-21T22:24:34Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"[PATCH] xdiff: add xdl_merge()\n\nThis new function implements the functionality of RCS merge, but\nin-memory. It returns < 0 on error, otherwise the number of conflicts.\n\nFinding the conflicting lines can be a very expensive task. You can\ncontrol the eagerness of this algorithm:\n\n- a level value of 0 means that all overlapping changes are treated\n  as conflicts,\n- a value of 1 means that if the overlapping changes are identical,\n  it is not treated as a conflict.\n- If you set level to 2, overlapping changes will be analyzed, so that\n  almost identical changes will not result in huge conflicts. Rather,\n  only the conflicting lines will be shown inside conflict markers.\n\nWith each increasing level, the algorithm gets slower, but more accurate.\nNote that the code for level 2 depends on the simple definition of\nmmfile_t specific to git, and therefore it will be harder to port that\nto LibXDiff.\n\nSigned-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>\n\n---\n\n\tThis code is only lightly tested, but I am tired and hungry.\n\n\tMy hopes are that when I wake up in the morning, all bugs are\n\tfixed, git-merge-one-file is rewritten as a builtin,\n\tgit-merge-index defaults to calling xdl_merge() directly when\n\tno program is passed with \"-o\", and git-merge-recursive also\n\tavoids fork()ing RCS' merge.\n\n\tA funny side effect is that you can merge with white space\n\tcorruption by setting the xpparam flags to ignore whitespace.\n\tThe file passed as mf1 wins over mf2 in that case.\n\n\tOh, and maybe I did not need to use xdl_change_compact() (and\n\tthus could have left that static to xdiffi.c)? Davide, if you \n\tcould enlighten me, I will take the time next weekend to port this \n\tto LibXDiff ;-)\n\n\tBTW if anybody wonders why these diffstats do not look correct:\n\t\"git apply --stat\" does not yet have our new scaling...\n\n Makefile       |    3 \n xdiff/xdiff.h  |    7 +\n xdiff/xdiffi.c |    3 \n xdiff/xdiffi.h |    1 \n xdiff/xmerge.c |  433 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 5 files changed, 444 insertions(+), 3 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 4c3f87f..b10d65e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -769,7 +769,8 @@ $(DIFF_OBJS): diffcore.h\n $(LIB_FILE): $(LIB_OBJS)\n \trm -f $@ && $(AR) rcs $@ $(LIB_OBJS)\n \n-XDIFF_OBJS=xdiff/xdiffi.o xdiff/xprepare.o xdiff/xutils.o xdiff/xemit.o\n+XDIFF_OBJS=xdiff/xdiffi.o xdiff/xprepare.o xdiff/xutils.o xdiff/xemit.o \\\n+\txdiff/xmerge.o\n $(XDIFF_OBJS): xdiff/xinclude.h xdiff/xmacros.h xdiff/xdiff.h xdiff/xtypes.h \\\n \txdiff/xutils.h xdiff/xprepare.h xdiff/xdiffi.h xdiff/xemit.h\n \ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex c9f8178..fa409d5 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -49,6 +49,9 @@ extern \"C\" {\n #define XDL_BDOP_CPY 2\n #define XDL_BDOP_INSB 3\n \n+#define XDL_MERGE_MINIMAL 0\n+#define XDL_MERGE_EAGER 1\n+#define XDL_MERGE_ZEALOUS 2\n \n typedef struct s_mmfile {\n \tchar *ptr;\n@@ -90,6 +93,10 @@ long xdl_mmfile_size(mmfile_t *mmf);\n int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t     xdemitconf_t const *xecfg, xdemitcb_t *ecb);\n \n+int xdl_merge(mmfile_t *orig, mmfile_t *mf1, const char *name1,\n+\t\tmmfile_t *mf2, const char *name2,\n+\t\txpparam_t const *xpp, int level, mmbuffer_t *result);\n+\n #ifdef __cplusplus\n }\n #endif /* #ifdef __cplusplus */\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex d76e76a..9aeebc4 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -45,7 +45,6 @@ static long xdl_split(unsigned long cons\n \t\t      long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,\n \t\t      xdalgoenv_t *xenv);\n static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2);\n-static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags);\n \n \n \n@@ -397,7 +396,7 @@ static xdchange_t *xdl_add_change(xdchan\n }\n \n \n-static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n+int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \tlong ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;\n \tchar *rchg = xdf->rchg, *rchgo = xdfo->rchg;\n \txrecord_t **recs = xdf->recs;\ndiff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h\nindex d3b7271..472aeae 100644\n--- a/xdiff/xdiffi.h\n+++ b/xdiff/xdiffi.h\n@@ -50,6 +50,7 @@ int xdl_recs_cmp(diffdata_t *dd1, long o\n \t\t long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv);\n int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\txdfenv_t *xe);\n+int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags);\n int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr);\n void xdl_free_script(xdchange_t *xscr);\n int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\ndiff --git a/xdiff/xmerge.c b/xdiff/xmerge.c\nnew file mode 100644\nindex 0000000..7b85aa5\n--- /dev/null\n+++ b/xdiff/xmerge.c\n@@ -0,0 +1,433 @@\n+/*\n+ *  LibXDiff by Davide Libenzi ( File Differential Library )\n+ *  Copyright (C) 2003-2006 Davide Libenzi, Johannes E. Schindelin\n+ *\n+ *  This library is free software; you can redistribute it and/or\n+ *  modify it under the terms of the GNU Lesser General Public\n+ *  License as published by the Free Software Foundation; either\n+ *  version 2.1 of the License, or (at your option) any later version.\n+ *\n+ *  This library is distributed in the hope that it will be useful,\n+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\n+ *  Lesser General Public License for more details.\n+ *\n+ *  You should have received a copy of the GNU Lesser General Public\n+ *  License along with this library; if not, write to the Free Software\n+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\n+ *\n+ *  Davide Libenzi <davidel@xmailserver.org>\n+ *\n+ */\n+\n+#include \"xinclude.h\"\n+\n+typedef struct s_xdmerge {\n+\tstruct s_xdmerge *next;\n+\t/*\n+\t * 0 = conflict,\n+\t * 1 = no conflict, take first,\n+\t * 2 = no conflict, take second.\n+\t */\n+\tint mode;\n+\tlong i1, i2;\n+\tlong chg1, chg2;\n+} xdmerge_t;\n+\n+static int xdl_append_merge(xdmerge_t **merge, int mode,\n+\t\tlong i1, long chg1, long i2, long chg2)\n+{\n+\txdmerge_t *m = *merge;\n+\tif (m && mode == m->mode &&\n+\t\t\t(i1 == m->i1 + m->chg1 || i2 == m->i2 + m->chg2)) {\n+\t\tm->chg1 = i1 + chg1 - m->i1;\n+\t\tm->chg2 = i2 + chg2 - m->i2;\n+\t} else {\n+\t\tm = xdl_malloc(sizeof(xdmerge_t));\n+\t\tif (!m)\n+\t\t\treturn -1;\n+\t\tm->next = NULL;\n+\t\tm->mode = mode;\n+\t\tm->i1 = i1;\n+\t\tm->chg1 = chg1;\n+\t\tm->i2 = i2;\n+\t\tm->chg2 = chg2;\n+\t\tif (*merge)\n+\t\t\t(*merge)->next = m;\n+\t\t*merge = m;\n+\t}\n+\treturn 0;\n+}\n+\n+static int xdl_cleanup_merge(xdmerge_t *c)\n+{\n+\tint count = 0;\n+\txdmerge_t *next_c;\n+\n+\t/* were there conflicts? */\n+\tfor (; c; c = next_c) {\n+\t\tif (c->mode == 0)\n+\t\t\tcount++;\n+\t\tnext_c = c->next;\n+\t\tfree(c);\n+\t}\n+\treturn count;\n+}\n+\n+static int xdl_merge_cmp_lines(xdfenv_t *xe1, int i1, xdfenv_t *xe2, int i2,\n+\t\tint line_count, long flags)\n+{\n+\tint i;\n+\txrecord_t **rec1 = xe1->xdf2.recs + i1;\n+\txrecord_t **rec2 = xe2->xdf2.recs + i2;\n+\n+\tfor (i = 0; i < line_count; i++) {\n+\t\tint result = xdl_recmatch(rec1[i]->ptr, rec1[i]->size,\n+\t\t\trec2[i]->ptr, rec2[i]->size, flags);\n+\t\tif (!result)\n+\t\t\treturn -1;\n+\t}\n+\treturn 0;\n+}\n+\n+static int xdl_recs_copy(xdfenv_t *xe, int i, int count, int add_nl, char *dest)\n+{\n+\txrecord_t **recs = xe->xdf2.recs + i;\n+\tint size = 0;\n+\n+\tif (count < 1)\n+\t\treturn 0;\n+\n+\tfor (i = 0; i < count; size += recs[i++]->size)\n+\t\tif (dest)\n+\t\t\tmemcpy(dest + size, recs[i]->ptr, recs[i]->size);\n+\tif (add_nl) {\n+\t\ti = recs[count - 1]->size;\n+\t\tif (i == 0 || recs[count - 1]->ptr[i - 1] != '\\n') {\n+\t\t\tif (dest)\n+\t\t\t\tdest[size] = '\\n';\n+\t\t\tsize++;\n+\t\t}\n+\t}\n+\treturn size;\n+}\n+\n+static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1,\n+\t\txdfenv_t *xe2, const char *name2, xdmerge_t *m, char *dest)\n+{\n+\tconst int marker_size = 7;\n+\tint marker1_size = (name1 ? strlen(name1) + 1 : 0);\n+\tint marker2_size = (name2 ? strlen(name2) + 1 : 0);\n+\tint conflict_marker_size = 3 * (marker_size + 1)\n+\t\t+ marker1_size + marker2_size;\n+\tint size, i1, j;\n+\n+\tfor (size = i1 = 0; m; m = m->next) {\n+\t\tif (m->mode == 0) {\n+\t\t\tsize += xdl_recs_copy(xe1, i1, m->i1 - i1, 0,\n+\t\t\t\t\tdest ? dest + size : NULL);\n+\t\t\tif (dest) {\n+\t\t\t\tfor (j = 0; j < marker_size; j++)\n+\t\t\t\t\tdest[size++] = '<';\n+\t\t\t\tif (marker1_size) {\n+\t\t\t\t\tdest[size] = ' ';\n+\t\t\t\t\tmemcpy(dest + size + 1, name1,\n+\t\t\t\t\t\t\tmarker1_size - 1);\n+\t\t\t\t\tsize += marker1_size;\n+\t\t\t\t}\n+\t\t\t\tdest[size++] = '\\n';\n+\t\t\t} else\n+\t\t\t\tsize += conflict_marker_size;\n+\t\t\tsize += xdl_recs_copy(xe1, m->i1, m->chg1, 1,\n+\t\t\t\t\tdest ? dest + size : NULL);\n+\t\t\tif (dest) {\n+\t\t\t\tfor (j = 0; j < marker_size; j++)\n+\t\t\t\t\tdest[size++] = '=';\n+\t\t\t\tdest[size++] = '\\n';\n+\t\t\t}\n+\t\t\tsize += xdl_recs_copy(xe2, m->i2, m->chg2, 1,\n+\t\t\t\t\tdest ? dest + size : NULL);\n+\t\t\tif (dest) {\n+\t\t\t\tfor (j = 0; j < marker_size; j++)\n+\t\t\t\t\tdest[size++] = '>';\n+\t\t\t\tif (marker2_size) {\n+\t\t\t\t\tdest[size] = ' ';\n+\t\t\t\t\tmemcpy(dest + size + 1, name2,\n+\t\t\t\t\t\t\tmarker2_size - 1);\n+\t\t\t\t\tsize += marker2_size;\n+\t\t\t\t}\n+\t\t\t\tdest[size++] = '\\n';\n+\t\t\t}\n+\t\t} else if (m->mode == 1)\n+\t\t\tsize += xdl_recs_copy(xe1, i1, m->i1 + m->chg1 - i1, 0,\n+\t\t\t\t\tdest ? dest + size : NULL);\n+\t\telse if (m->mode == 2)\n+\t\t\tsize += xdl_recs_copy(xe2, m->i2 - m->i1 + i1,\n+\t\t\t\t\tm->i1 + m->chg2 - i1, 0,\n+\t\t\t\t\tdest ? dest + size : NULL);\n+\t\ti1 = m->i1 + m->chg1;\n+\t}\n+\tsize += xdl_recs_copy(xe1, i1, xe1->xdf2.nrec - i1, 0,\n+\t\t\tdest ? dest + size : NULL);\n+\treturn size;\n+}\n+\n+/*\n+ * Sometimes, changes are not quite identical, but differ in only a few\n+ * lines. Try hard to show only these few lines as conflicting.\n+ */\n+static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,\n+\t\txpparam_t const *xpp)\n+{\n+\tfor (; m; m = m->next) {\n+\t\tmmfile_t t1, t2;\n+\t\txdfenv_t xe;\n+\t\txdchange_t *xscr, *x;\n+\t\tint i1 = m->i1, i2 = m->i2;\n+\n+\t\t/* let's handle just the conflicts */\n+\t\tif (m->mode)\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * This probably does not work outside git, since\n+\t\t * we have a very simple mmfile structure.\n+\t\t */\n+\t\tt1.ptr = (char *)xe1->xdf2.recs[m->i1]->ptr;\n+\t\tt1.size = xe1->xdf2.recs[m->i1 + m->chg1]->ptr\n+\t\t\t+ xe1->xdf2.recs[m->i1 + m->chg1]->size - t1.ptr;\n+\t\tt2.ptr = (char *)xe2->xdf2.recs[m->i1]->ptr;\n+\t\tt2.size = xe2->xdf2.recs[m->i1 + m->chg1]->ptr\n+\t\t\t+ xe2->xdf2.recs[m->i1 + m->chg1]->size - t2.ptr;\n+\t\tif (xdl_do_diff(&t1, &t2, xpp, &xe) < 0)\n+\t\t\treturn -1;\n+\t\tif (xdl_change_compact(&xe.xdf1, &xe.xdf2, xpp->flags) < 0 ||\n+\t\t    xdl_change_compact(&xe.xdf2, &xe.xdf1, xpp->flags) < 0 ||\n+\t\t    xdl_build_script(&xe, &xscr) < 0) {\n+\t\t\txdl_free_env(&xe);\n+\t\t\treturn -1;\n+\t\t}\n+\t\tif (!xscr) {\n+\t\t\t/* If this happens, it's a bug. */\n+\t\t\txdl_free_env(&xe);\n+\t\t\treturn -2;\n+\t\t}\n+\t\tx = xscr;\n+\t\tm->i1 = xscr->i1 + i1;\n+\t\tm->chg1 = xscr->chg1;\n+\t\tm->i2 = xscr->i2 + i2;\n+\t\tm->chg2 = xscr->chg2;\n+\t\twhile (xscr->next) {\n+\t\t\txdmerge_t *m2 = xdl_malloc(sizeof(xdmerge_t));\n+\t\t\tif (!m2) {\n+\t\t\t\txdl_free_env(&xe);\n+\t\t\t\txdl_free_script(x);\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t\txscr = xscr->next;\n+\t\t\tm2->next = m->next;\n+\t\t\tm->next = m2;\n+\t\t\tm = m2;\n+\t\t\tm->mode = 0;\n+\t\t\tm->i1 = xscr->i1 + i1;\n+\t\t\tm->chg1 = xscr->chg1;\n+\t\t\tm->i2 = xscr->i2 + i2;\n+\t\t\tm->chg2 = xscr->chg2;\n+\t\t}\n+\t\txdl_free_env(&xe);\n+\t\txdl_free_script(x);\n+\t}\n+\treturn 0;\n+}\n+\n+/*\n+ * level == 0: mark all overlapping changes as conflict\n+ * level == 1: mark overlapping changes as conflict only if not identical\n+ * level == 2: analyze non-identical changes for minimal conflict set\n+ *\n+ * returns < 0 on error, == 0 for no conflicts, else number of conflicts\n+ */\n+static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1, const char *name1,\n+\t\txdfenv_t *xe2, xdchange_t *xscr2, const char *name2,\n+\t\tint level, xpparam_t const *xpp, mmbuffer_t *result) {\n+\txdmerge_t *changes, *c;\n+\tint i1, i2, chg1, chg2;\n+\n+\tc = changes = NULL;\n+\n+\twhile (xscr1 && xscr2) {\n+\t\tif (!changes)\n+\t\t\tchanges = c;\n+\t\tif (xscr1->i1 + xscr1->chg1 < xscr2->i1) {\n+\t\t\ti1 = xscr1->i2;\n+\t\t\ti2 = xscr2->i2 - xscr2->i1 + xscr1->i1;\n+\t\t\tchg1 = xscr1->chg2;\n+\t\t\tchg2 = xscr1->chg1;\n+\t\t\tif (xdl_append_merge(&c, 1, i1, chg1, i2, chg2)) {\n+\t\t\t\txdl_cleanup_merge(changes);\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t\txscr1 = xscr1->next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (xscr2->i1 + xscr2->chg1 < xscr1->i1) {\n+\t\t\ti1 = xscr1->i2 - xscr1->i1 + xscr2->i1;\n+\t\t\ti2 = xscr2->i2;\n+\t\t\tchg1 = xscr2->chg1;\n+\t\t\tchg2 = xscr2->chg2;\n+\t\t\tif (xdl_append_merge(&c, 2, i1, chg1, i2, chg2)) {\n+\t\t\t\txdl_cleanup_merge(changes);\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t\txscr2 = xscr2->next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (level < 1 || xscr1->i1 != xscr2->i1 ||\n+\t\t\t\txscr1->chg1 != xscr2->chg1 ||\n+\t\t\t\txscr1->chg2 != xscr2->chg2 ||\n+\t\t\t\txdl_merge_cmp_lines(xe1, xscr1->i2,\n+\t\t\t\t\txe2, xscr2->i2,\n+\t\t\t\t\txscr1->chg2, xpp->flags)) {\n+\t\t\t/* conflict */\n+\t\t\tint off = xscr1->i1 - xscr2->i1;\n+\t\t\tint ffo = off + xscr1->chg1 - xscr2->chg1;\n+\n+\t\t\ti1 = xscr1->i2;\n+\t\t\ti2 = xscr2->i2;\n+\t\t\tif (off > 0)\n+\t\t\t\ti1 -= off;\n+\t\t\telse\n+\t\t\t\ti2 += off;\n+\t\t\tchg1 = xscr1->i2 + xscr1->chg2 - i1;\n+\t\t\tchg2 = xscr2->i2 + xscr2->chg2 - i2;\n+\t\t\tif (ffo > 0)\n+\t\t\t\tchg2 += ffo;\n+\t\t\telse\n+\t\t\t\tchg1 -= ffo;\n+\t\t\tif (xdl_append_merge(&c, 0, i1, chg1, i2, chg2)) {\n+\t\t\t\txdl_cleanup_merge(changes);\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t}\n+\n+\t\ti1 = xscr1->i1 + xscr1->chg1;\n+\t\ti2 = xscr2->i1 + xscr2->chg1;\n+\n+\t\tif (i1 > i2) {\n+\t\t\txscr1->chg1 -= i1 - i2;\n+\t\t\txscr1->i1 = i2;\n+\t\t\txscr1->i2 += xscr1->chg2;\n+\t\t\txscr1->chg2 = 0;\n+\t\t\txscr1 = xscr1->next;\n+\t\t} else if (i2 > i1) {\n+\t\t\txscr2->chg1 -= i2 - i1;\n+\t\t\txscr2->i1 = i1;\n+\t\t\txscr2->i2 += xscr2->chg2;\n+\t\t\txscr2->chg2 = 0;\n+\t\t\txscr2 = xscr2->next;\n+\t\t} else {\n+\t\t\txscr1 = xscr1->next;\n+\t\t\txscr2 = xscr2->next;\n+\t\t}\n+\t}\n+\twhile (xscr1) {\n+\t\tif (!changes)\n+\t\t\tchanges = c;\n+\t\ti1 = xscr1->i2;\n+\t\ti2 = xscr1->i1 + xe2->xdf2.nrec - xe2->xdf1.nrec;\n+\t\tchg1 = xscr1->chg2;\n+\t\tchg2 = xscr1->chg1;\n+\t\tif (xdl_append_merge(&c, 1, i1, chg1, i2, chg2)) {\n+\t\t\txdl_cleanup_merge(changes);\n+\t\t\treturn -1;\n+\t\t}\n+\t\txscr1 = xscr1->next;\n+\t}\n+\twhile (xscr2) {\n+\t\tif (!changes)\n+\t\t\tchanges = c;\n+\t\ti1 = xscr2->i1 + xe1->xdf2.nrec - xe1->xdf1.nrec;\n+\t\ti2 = xscr2->i2;\n+\t\tchg1 = xscr2->chg1;\n+\t\tchg2 = xscr2->chg2;\n+\t\tif (xdl_append_merge(&c, 2, i1, chg1, i2, chg2)) {\n+\t\t\txdl_cleanup_merge(changes);\n+\t\t\treturn -1;\n+\t\t}\n+\t\txscr2 = xscr2->next;\n+\t}\n+\tif (!changes)\n+\t\tchanges = c;\n+\t/* refine conflicts */\n+\tif (level > 1 && xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0) {\n+\t\txdl_cleanup_merge(changes);\n+\t\treturn -1;\n+\t}\n+\t/* output */\n+\tif (result) {\n+\t\tint size = xdl_fill_merge_buffer(xe1, name1, xe2, name2,\n+\t\t\tchanges, NULL);\n+\t\tresult->ptr = xdl_malloc(size);\n+\t\tif (!result->ptr) {\n+\t\t\txdl_cleanup_merge(changes);\n+\t\t\treturn -1;\n+\t\t}\n+\t\tresult->size = size;\n+\t\txdl_fill_merge_buffer(xe1, name1, xe2, name2, changes,\n+\t\t\t\tresult->ptr);\n+\t}\n+\treturn xdl_cleanup_merge(changes);\n+}\n+\n+int xdl_merge(mmfile_t *orig, mmfile_t *mf1, const char *name1,\n+\t\tmmfile_t *mf2, const char *name2,\n+\t\txpparam_t const *xpp, int level, mmbuffer_t *result) {\n+\txdchange_t *xscr1, *xscr2;\n+\txdfenv_t xe1, xe2;\n+\n+\tresult->ptr = NULL;\n+\tresult->size = 0;\n+\n+\tif (xdl_do_diff(orig, mf1, xpp, &xe1) < 0 ||\n+\t\t\txdl_do_diff(orig, mf2, xpp, &xe2) < 0) {\n+\t\treturn -1;\n+\t}\n+\tif (xdl_change_compact(&xe1.xdf1, &xe1.xdf2, xpp->flags) < 0 ||\n+\t    xdl_change_compact(&xe1.xdf2, &xe1.xdf1, xpp->flags) < 0 ||\n+\t    xdl_build_script(&xe1, &xscr1) < 0) {\n+\t\txdl_free_env(&xe1);\n+\t\treturn -1;\n+\t}\n+\tif (xdl_change_compact(&xe2.xdf1, &xe2.xdf2, xpp->flags) < 0 ||\n+\t    xdl_change_compact(&xe2.xdf2, &xe2.xdf1, xpp->flags) < 0 ||\n+\t    xdl_build_script(&xe2, &xscr2) < 0) {\n+\t\txdl_free_env(&xe2);\n+\t\treturn -1;\n+\t}\n+\tif (xscr1 || xscr2) {\n+\t\tif (!xscr1) {\n+\t\t\tresult->ptr = xdl_malloc(mf2->size);\n+\t\t\tmemcpy(result->ptr, mf2->ptr, mf2->size);\n+\t\t\tresult->size = mf2->size;\n+\t\t} else if (!xscr2) {\n+\t\t\tresult->ptr = xdl_malloc(mf1->size);\n+\t\t\tmemcpy(result->ptr, mf1->ptr, mf1->size);\n+\t\t\tresult->size = mf1->size;\n+\t\t} else if (xdl_do_merge(&xe1, xscr1, name1,\n+\t\t\t\t\t&xe2, xscr2, name2,\n+\t\t\t\t\tlevel, xpp, result) < 0) {\n+\t\t\txdl_free_script(xscr1);\n+\t\t\txdl_free_script(xscr2);\n+\t\t\txdl_free_env(&xe1);\n+\t\t\txdl_free_env(&xe2);\n+\t\t\treturn -1;\n+\t\t}\n+\t\txdl_free_script(xscr1);\n+\t\txdl_free_script(xscr2);\n+\t}\n+\txdl_free_env(&xe1);\n+\txdl_free_env(&xe2);\n+\n+\treturn 0;\n+}\n"},{"id":"293867","messageId":"ek0170$h53$1@sea.gmane.org","threadId":"43116","inReplyTo":"Pine.LNX.4.63.0611212316080.26827@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] xdiff: add xdl_merge() (was: (unknown))","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-11-21T23:15:09Z","receivedAt":"2006-11-21T23:15:09Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Johannes Schindelin wrote:\n\n> [PATCH] xdiff: add xdl_merge()\n\nShouldn't this be in the subject of message?\n\n> This new function implements the functionality of RCS merge, but\n> in-memory. It returns < 0 on error, otherwise the number of conflicts.\n\nOnly RCS merge, or can you implement whole diff3 (from GNU diffutils)\nfunctionality with that?\n\n> Finding the conflicting lines can be a very expensive task. You can\n> control the eagerness of this algorithm:\n> \n> - a level value of 0 means that all overlapping changes are treated\n>   as conflicts,\n> - a value of 1 means that if the overlapping changes are identical,\n>   it is not treated as a conflict.\n> - If you set level to 2, overlapping changes will be analyzed, so that\n>   almost identical changes will not result in huge conflicts. Rather,\n>   only the conflicting lines will be shown inside conflict markers.\n> \n> With each increasing level, the algorithm gets slower, but more accurate.\n> Note that the code for level 2 depends on the simple definition of\n> mmfile_t specific to git, and therefore it will be harder to port that\n> to LibXDiff.\n\nHow it compares performance with RCS merge/GNU diff3?\n\n\nIt is really nice to have that. Bram Cohen (of Codeville, SCM built around\nsophisticated merge algorithm) wrote about recursive three-way merge in\nhttp://revctrl.org/CrissCrossMerge\n\n   Recursive three-way merge _usually_ provides the right answer, however\n   there are some edge cases. For example, conflict markers can be matched\n   incorrectly, because they aren't given any special semantic meaning for\n   the merge algorithm, and are simply treated as lines. In particular,\n   there are (somewhat complicated) cases where the conflict markers of two\n   unrelated conflicts get matched against each other, even though the\n   content sections of them are totally unrelated.\n\nI'm not sure if he has specific examples, or is it just theoretical talk,\nbut having built-in merge would certainly help revursive merge strategy\n(and perhaps also git-rerere).\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n\n"},{"id":"298725","messageId":"Pine.LNX.4.63.0611221005470.30004@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"43116","inReplyTo":"ek0170$h53$1@sea.gmane.org","subject":"Re: [PATCH] xdiff: add xdl_merge() (was: (unknown))","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-11-22T09:29:55Z","receivedAt":"2006-11-22T09:29:55Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 22 Nov 2006, Jakub Narebski wrote:\n\n> Johannes Schindelin wrote:\n> \n> > [PATCH] xdiff: add xdl_merge()\n> \n> Shouldn't this be in the subject of message?\n\nDid I mention that I was tired and hungry?\n\n> > This new function implements the functionality of RCS merge, but \n> > in-memory. It returns < 0 on error, otherwise the number of conflicts.\n> \n> Only RCS merge, or can you implement whole diff3 (from GNU diffutils) \n> functionality with that?\n\nAs I am interested only in the in-memory merge, only RCS merge. Which \nfeature would you be interested in? An ed script? :-)\n\n> > Finding the conflicting lines can be a very expensive task. You can\n> > control the eagerness of this algorithm:\n> > \n> > - a level value of 0 means that all overlapping changes are treated\n> >   as conflicts,\n> > - a value of 1 means that if the overlapping changes are identical,\n> >   it is not treated as a conflict.\n> > - If you set level to 2, overlapping changes will be analyzed, so that\n> >   almost identical changes will not result in huge conflicts. Rather,\n> >   only the conflicting lines will be shown inside conflict markers.\n> > \n> > With each increasing level, the algorithm gets slower, but more accurate.\n> > Note that the code for level 2 depends on the simple definition of\n> > mmfile_t specific to git, and therefore it will be harder to port that\n> > to LibXDiff.\n> \n> How it compares performance with RCS merge/GNU diff3?\n\nSpeedwise, I have no clue. It was enough work for a day.\n\nAccuracywise: often I sent a patch (series) which was in my current git \ntree (no topic branch), and Junio did some minor adjustments. I _hated_ \nthe fact that RCS merge marked _all_ overlapping changes as conflicts, \neven when there was just a minor correction here and there. And \"git diff \n--ours\" does not help at all.\n\nHere is where my implementation should help. With level 2, it will look \nagain at these conflicting regions, and only output the actual differences \nas conflicts.\n\n> It is really nice to have that. Bram Cohen (of Codeville, SCM built around\n> sophisticated merge algorithm) wrote about recursive three-way merge in\n> http://revctrl.org/CrissCrossMerge\n> \n>    Recursive three-way merge _usually_ provides the right answer, however\n>    there are some edge cases. For example, conflict markers can be matched\n>    incorrectly, because they aren't given any special semantic meaning for\n>    the merge algorithm, and are simply treated as lines. In particular,\n>    there are (somewhat complicated) cases where the conflict markers of two\n>    unrelated conflicts get matched against each other, even though the\n>    content sections of them are totally unrelated.\n> \n> I'm not sure if he has specific examples, or is it just theoretical talk,\n> but having built-in merge would certainly help revursive merge strategy\n> (and perhaps also git-rerere).\n\nIt should be easy to construct such an example. However, the relevance in \npractice is about zero.\n\nGit was built from the beginning to aim to do a merge as good as possible, \nbut not perfect. There is no such thing as a perfect merge algorithm. You \nwill always be able to construct cases which are mismerged.\n\nThus, git takes the pragmatic approach and stops \"early\": merges work in \n99% of the time, and in 99% of the remaining 1% the merge will fail so \nthat you know you have to fix it manually. (Take these numbers with a \ngrain of salt, please.) The advantage of stopping there is that we can \nmake it really fast.\n\nYou could probably raise the 99% to 99.5%, by implementing a \"rebasing \nmerge\", i.e. cherry-picking the branch-to-be-merged committing only in the \nend (if there has not been any conflict). Obviously, this is slow as \nParnell's pitch[1].\n\nAs for git-rerere: I could not use it everywhere, because of some Perl \ndependencies which I could not compile on some platforms. However, IMHO \ngit-rerere does not necessarily depend on merge being available in libgit.\n\nCiao,\nDscho\n\nFootnote 1: http://www.physics.uq.edu.au/pitchdrop/pitchdrop.shtml\n"},{"id":"296211","messageId":"4564ABE3.6080605@ramsay1.demon.co.uk","threadId":"43116","inReplyTo":"Pine.LNX.4.63.0611212316080.26827@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] xdiff: add xdl_merge()","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsay1.demon.co.uk","sentAt":"2006-11-22T19:58:27Z","receivedAt":"2006-11-22T19:58:27Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"Hi Johannes,\n\nJohannes Schindelin wrote:\n> This new function implements the functionality of RCS merge, but\n> in-memory. It returns < 0 on error, otherwise the number of conflicts.\n> \n\nI had a similar idea (removing the RCS dependency) and, about two months\nago, implemented a git-diff3 that used the internal xdiff library.\nUnfortunately, I then got distracted by other things and left this as a\nWIP, without posting it to the list. [I had an email exchange with Junio\nabout it, but then dropped the ball - sorry Junio!]\n\n> Finding the conflicting lines can be a very expensive task. You can\n> control the eagerness of this algorithm:\n> \n> - a level value of 0 means that all overlapping changes are treated\n>   as conflicts,\n> - a value of 1 means that if the overlapping changes are identical,\n>   it is not treated as a conflict.\n> - If you set level to 2, overlapping changes will be analyzed, so that\n>   almost identical changes will not result in huge conflicts. Rather,\n>   only the conflicting lines will be shown inside conflict markers.\n> \n> With each increasing level, the algorithm gets slower, but more accurate.\n> Note that the code for level 2 depends on the simple definition of\n> mmfile_t specific to git, and therefore it will be harder to port that\n> to LibXDiff.\n> \n\nErm, I guess I need to read the code! I haven't had an opportunity to\ndo that yet, but I hope to have time at the weekend.\n\n> \tMy hopes are that when I wake up in the morning, all bugs are\n> \tfixed, git-merge-one-file is rewritten as a builtin,\n> \tgit-merge-index defaults to calling xdl_merge() directly when\n> \tno program is passed with \"-o\", and git-merge-recursive also\n> \tavoids fork()ing RCS' merge.\n\nYep, I had a similar todo list.\n\n> \n> \tA funny side effect is that you can merge with white space\n> \tcorruption by setting the xpparam flags to ignore whitespace.\n> \tThe file passed as mf1 wins over mf2 in that case.\n\nYes, I had this on my todo list. In fact you can already try it out\nby using --diff-program=\"diff -wb\" (which uses the external diff).\n[To be fair, you can also write an obvious script and use GNU diff3]\n\n> \n>  Makefile       |    3 \n>  xdiff/xdiff.h  |    7 +\n>  xdiff/xdiffi.c |    3 \n>  xdiff/xdiffi.h |    1 \n>  xdiff/xmerge.c |  433 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n>  5 files changed, 444 insertions(+), 3 deletions(-)\n> \n\n From the above, I would guess that your code integrates well with the\nxdiff library and, as a result, would be more memory efficient than my\ncode. I had considered doing this, but I wanted to support an external\ndiff option, so it was easier to implement the diff3 algorithm outside\nthe library, treating it just like an external diff (that I didn't need\nto fork()/exec()). Also, I didn't need to understand the xdiff code, I\njust treat it as a black box (and I'm lazy!).\n\n[Having an external diff option was actually a debugging aid to ensure\nthat the main diff3 algorithm was implemented correctly. In the end I\ndidn't use it for debugging anyway!]\n\n[snip patch]\n\nI have attached a version of my patch, against v1.4.2, just for the\ninterested. Also it contains some tests which I found very helpful\nin squashing bugs, so you might like to give them a try with your code.\n\nNote: the fact that the patch is against v1.4.2 should not cause too\nmuch of a problem, since it is mostly new files and the changes to\nMakefile, builtin.h and git.c you could probably do in your sleep.\n\n[Junio, this is almost exactly the same patch I sent you last time,\nmodulo some minor code clean-up/formatting]\n\nAll the best,\n\nRamsay\n\n\n\n\n>From f23d8df5d7774cb85b834357019c725cf8c1e231 Mon Sep 17 00:00:00 2001\nFrom: Ramsay Jones <ramsay@ramsay1.demon.co.uk>\nDate: Mon, 13 Nov 2006 23:04:37 +0000\nSubject: [PATCH] Initial implementation of builtin diff3\n\nThe intention of this work is to remove the dependancy on\nthe rcs merge program. As a first step, we implement a\nbuiltin clone of diff3. (A builtin merge replacement command\nwill be able to reuse this code, since merge is a thin\nwrapper around diff3). So git-diff3 is only a stepping stone\nto a merge replacement and is not meant to stay!\n\nSigned-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk>\n---\n Makefile         |    5 \n builtin-diff3.c  | 1824 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n builtin.h        |    2 \n git.c            |    1 \n t/txxxx-diff3.sh |  175 +++++\n t/txxxx/lao      |   11 \n t/txxxx/lao1     |    8 \n t/txxxx/lao2     |   16 \n t/txxxx/lao3     |   13 \n t/txxxx/lao4     |   12 \n t/txxxx/tao      |   14 \n t/txxxx/tao1     |   10 \n t/txxxx/tao2     |   16 \n t/txxxx/tao3     |   13 \n t/txxxx/tao4     |   15 \n t/txxxx/tzu      |   13 \n 16 files changed, 2146 insertions(+), 2 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 0761d6c..60f5adc 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -198,7 +198,7 @@ BUILT_INS = git-log$X git-whatchanged$X \n \tgit-apply$X git-show-branch$X git-diff-files$X git-update-index$X \\\n \tgit-diff-index$X git-diff-stages$X git-diff-tree$X git-cat-file$X \\\n \tgit-fmt-merge-msg$X git-prune$X git-mv$X git-prune-packed$X \\\n-\tgit-repo-config$X\n+\tgit-repo-config$X git-diff3$X\n \n # what 'all' will build and 'install' will install, in gitexecdir\n ALL_PROGRAMS = $(PROGRAMS) $(SIMPLE_PROGRAMS) $(SCRIPTS)\n@@ -255,7 +255,8 @@ BUILTIN_OBJS = \\\n \tbuiltin-diff-index.o builtin-diff-stages.o builtin-diff-tree.o \\\n \tbuiltin-cat-file.o builtin-mailsplit.o builtin-stripspace.o \\\n \tbuiltin-update-ref.o builtin-fmt-merge-msg.o builtin-prune.o \\\n-\tbuiltin-mv.o builtin-prune-packed.o builtin-repo-config.o\n+\tbuiltin-mv.o builtin-prune-packed.o builtin-repo-config.o \\\n+\tbuiltin-diff3.o\n \n GITLIBS = $(LIB_FILE) $(XDIFF_LIB)\n LIBS = $(GITLIBS) -lz\ndiff --git a/builtin-diff3.c b/builtin-diff3.c\nnew file mode 100644\nindex 0000000..9f5698f\n--- /dev/null\n+++ b/builtin-diff3.c\n@@ -0,0 +1,1824 @@\n+/*\n+ * Builtin \"git diff3\"\n+ *\n+ */\n+#include \"cache.h\"\n+#include \"builtin.h\"\n+#include \"xdiff-interface.h\"\n+#include <sys/wait.h>\n+#include <assert.h>\n+\n+\n+#define MAX_DIFF_ARGS 32\n+\n+/* diff3 options */\n+struct diff3_options {\n+\tunsigned show_all:1;     /* show all changes, including merged       */\n+\tunsigned overlap_only:1; /* restrict to overlapping changes          */\n+\tunsigned unmerged_only:1;/* restrict to unmerged non-overlapping     */\n+\tunsigned initial_tab:1;  /* output initial tab                       */\n+\tunsigned markers:1;      /* output conflict markers                  */\n+\tunsigned edscript:1;     /* output an ed script to perform the merge */\n+\tunsigned merge:1;        /* actually output the merged file          */\n+\tconst char *diff_prog;   /* external diff program (command line)     */\n+};\n+\n+/* input file info */\n+struct finfo {\n+\tconst char *name;   /* filename                       */\n+\tconst char *label;  /* label to use for markers       */\n+\tint         num;    /* 0 = ours, 1 = base, 2 = theirs */\n+\tmmfile_t    mf;     /* file mmap() info               */\n+};\n+\n+/* pipe info when running external diff */\n+struct pinfo {\n+\tint   fd;   /* pipe read/write fd    */\n+\tpid_t pid;  /* child pid to wait for */\n+};\n+\n+/* argv info for external diff */\n+struct diff_argv {\n+\tchar *args;         /* argument string memory */\n+\tconst char **argv;  /* argument pointer array */\n+\tint argc;           /* argument count         */\n+};\n+\n+/* callback info used with internal diff */\n+struct ecb_info {\n+\tchar *text;  /* pointer to text of diff output    */\n+\tlong size;   /* size of memory block holding text */\n+\tlong used;   /* length of diff output             */\n+};\n+\n+/* type of diff */\n+enum {\n+\tUNKNOWN_FORMAT,\n+\tNORMAL_FORMAT,\n+\tUNIFIED_FORMAT,\n+\tCONTEXT_FORMAT\n+};\n+\n+/* normal format diff hunk header */\n+struct hunk_header {\n+\tint fs, fe;  /* from-file start and end line numbers */\n+\tint type;    /* 'a' add, 'c' change, 'd' delete      */\n+\tint ts, te;  /* to-file start and end line numbers   */\n+};\n+\n+/* unified format diff hunk header */\n+struct unified_hunk_header {\n+\tint fs, fc;  /* from-file start line and count */\n+\tint ts, tc;  /* to-file start line and count   */\n+};\n+\n+/* lines from one file referenced by a hunk */\n+struct hunk_lines {\n+\tint  start;     /* start line number of hunk         */\n+\tint  end;       /* end line number of hunk           */\n+\tchar **lines;   /* pointer to array of line pointers */\n+\tint  *lengths;  /* pointer to array of line lengths  */\n+\tint  size;      /* size of the above arrays          */\n+};\n+\n+/* 2way diff hunk */\n+struct diff2_hunk {\n+\tint               type;   /* hunk type: 'a', 'c', 'd'   */\n+\tstruct hunk_lines from;   /* from-file hunk lines       */\n+\tstruct hunk_lines to;     /* to-file hunk lines         */\n+\tstruct diff2_hunk *next;  /* next hunk in list          */\n+};\n+\n+/* 2way diff */\n+struct diff2 {\n+\tstruct finfo      *ff;      /* from file            */\n+\tstruct finfo      *ft;      /* to file              */\n+\tmmbuffer_t        content;  /* text content of diff */\n+\tstruct diff2_hunk *hunks;   /* list of diff hunks   */\n+};\n+\n+/* a segment (sub-list) of diff2 hunks */\n+struct segment {\n+\tint               from;   /* from-file number          */\n+\tint               to;     /* to-file number            */\n+\tstruct diff2_hunk *head;  /* head of hunk list segment */\n+\tstruct diff2_hunk *tail;  /* tail of hunk list segment */\n+\tint               count;  /* count of hunks            */\n+};\n+\n+/* 3way diff hunk */\n+struct diff3_hunk {\n+\tint               type;  /* 'a' all, '1' 1st, '2' 2nd, '3' 3rd */\n+\tstruct hunk_lines f[3];  /* hunk lines for files 0, 1, 2       */\n+\tstruct diff3_hunk *next; /* next hunk in list                  */\n+};\n+\n+/* 3way diff */\n+struct diff3 {\n+\tstruct diff2      *diff01;  /* diff ours -> base   */\n+\tstruct diff2      *diff21;  /* diff theirs -> base */\n+\tstruct diff3_hunk *hunks;   /* list of diff3 hunks */\n+};\n+\n+static void init_finfo(struct finfo *f, const char *name, const char *lab, int num)\n+{\n+\tif (f) {\n+\t\tf->name  = name;\n+\t\tf->label = lab;\n+\t\tf->num   = num;\n+\n+\t\tf->mf.ptr  = 0;\n+\t\tf->mf.size = 0;\n+\t}\n+}\n+\n+static void alloc_line_arrays(int num, struct hunk_lines *h)\n+{\n+\tassert(h);\n+\th->lines   = xcalloc(num, sizeof(char *));\n+\th->lengths = xcalloc(num, sizeof(int));\n+\th->size    = num;\n+}\n+\n+static struct diff2_hunk *new_diff2_hunk(void)\n+{\n+\tstruct diff2_hunk *new = xmalloc(sizeof(*new));\n+\n+\tmemset(new, 0, sizeof(*new));\n+\n+\treturn new;\n+}\n+\n+static void free_diff2_hunk(struct diff2_hunk *p)\n+{\n+\tif (p->from.lines)\n+\t\tfree(p->from.lines);\n+\tif (p->from.lengths)\n+\t\tfree(p->from.lengths);\n+\n+\tif (p->to.lines)\n+\t\tfree(p->to.lines);\n+\tif (p->to.lengths)\n+\t\tfree(p->to.lengths);\n+\n+\tfree(p);\n+}\n+\n+static struct diff2 *new_diff2(struct finfo *ff, struct finfo *ft)\n+{\n+\tstruct diff2 *new = xmalloc(sizeof(*new));\n+\n+\tmemset(new, 0, sizeof(*new));\n+\n+\tnew->ff = ff;\n+\tnew->ft = ft;\n+\n+\treturn new;\n+}\n+\n+static void free_diff2(struct diff2 *p)\n+{\n+\tstruct diff2_hunk *h, *next;\n+\n+\tfor (h = p->hunks; h; h = next) {\n+\t\tnext = h->next;\n+\t\tfree_diff2_hunk(h);\n+\t}\n+\n+\tif (p->content.ptr)\n+\t\tfree(p->content.ptr);\n+\n+\tfree(p);\n+}\n+\n+static struct diff3_hunk *new_diff3_hunk(void)\n+{\n+\tstruct diff3_hunk *new = xmalloc(sizeof(*new));\n+\n+\tmemset(new, 0, sizeof(*new));\n+\n+\treturn new;\n+}\n+\n+static void free_diff3_hunk(struct diff3_hunk *p)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < 3; i++) {\n+\t\tif (p->f[i].lines)\n+\t\t\tfree(p->f[i].lines);\n+\t\tif (p->f[i].lengths)\n+\t\t\tfree(p->f[i].lengths);\n+\t}\n+\n+\tfree(p);\n+}\n+\n+static struct diff3 *new_diff3(struct diff2 *diff01, struct diff2 *diff21)\n+{\n+\tstruct diff3 *new = xmalloc(sizeof(*new));\n+\n+\tmemset(new, 0, sizeof(*new));\n+\n+\tnew->diff01 = diff01;\n+\tnew->diff21 = diff21;\n+\n+\treturn new;\n+}\n+\n+static void free_diff3(struct diff3 *p)\n+{\n+\tstruct diff3_hunk *h, *next;\n+\n+\tfor (h = p->hunks; h; h = next) {\n+\t\tnext = h->next;\n+\t\tfree_diff3_hunk(h);\n+\t}\n+\n+\tfree_diff2(p->diff01);\n+\tfree_diff2(p->diff21);\n+\n+\tfree(p);\n+}\n+\n+static int init_mmfile(mmfile_t *mf, const char *file)\n+{\n+\tchar *data;\n+\tlong size;\n+\tstruct stat st;\n+\tint fd;\n+\n+\tassert(mf && file && *file);\n+\n+\tmf->ptr  = 0;\n+\tmf->size = 0;\n+\n+\tif (lstat(file, &st) < 0)\n+\t\treturn -1;\n+\tsize = st.st_size;\n+\tif (!size) {\n+\t\tmf->ptr = \"\";\n+\t\treturn 0;\n+\t}\n+\n+\tfd = open(file, O_RDONLY);\n+\tif (fd < 0)\n+\t\treturn -1;\n+\tdata = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\tif (data == MAP_FAILED)\n+\t\treturn -1;\n+\n+\tmf->ptr  = data;\n+\tmf->size = size;\n+\treturn 0;\n+}\n+\n+static void free_mmfile(mmfile_t *mf)\n+{\n+\tif (mf) {\n+\t\tif (mf->ptr && mf->size != 0)\n+\t\t\tmunmap(mf->ptr, mf->size);\n+\t\tmf->ptr  = 0;\n+\t\tmf->size = 0;\n+\t}\n+}\n+\n+static void map_file(struct finfo *f)\n+{\n+\tif (!f->mf.ptr && (init_mmfile(&f->mf, f->name) < 0))\n+\t\tdie(\"can't read file '%s': %s\", f->name, strerror(errno));\n+}\n+\n+static int popenv(int argc, const char *argv[], const char *type, struct pinfo *p)\n+{\n+\tint pfd[2];\n+\tpid_t pid;\n+\tint fd;\n+\n+\tif (!argv || !type || !p) {\n+\t\terrno = EINVAL;\n+\t\treturn -1;\n+\t}\n+\tp->fd = -1;\n+\tp->pid = 0;\n+\n+\tif (!*type || (*type != 'r' && *type != 'w') || type[1] != 0) {\n+\t\terrno = EINVAL;\n+\t\treturn -1;\n+\t}\n+\n+\tif (pipe(pfd) < 0)\n+\t\treturn -1;\n+\n+\tif ((pid = fork()) < 0) {\n+\t\treturn -1;\n+\t} else if (pid == 0) {  /* child */\n+\t\tif (*type == 'r') {\n+\t\t\tclose(pfd[0]);\n+\t\t\tif(pfd[1] != STDOUT_FILENO) {\n+\t\t\t\tdup2(pfd[1], STDOUT_FILENO);\n+\t\t\t\tclose(pfd[1]);\n+\t\t\t}\n+\t\t} else { /* *type == 'w' */\n+\t\t\tclose(pfd[1]);\n+\t\t\tif(pfd[0] != STDIN_FILENO) {\n+\t\t\t\tdup2(pfd[0], STDIN_FILENO);\n+\t\t\t\tclose(pfd[0]);\n+\t\t\t}\n+\n+\t\t}\n+\n+#ifdef DUMMY\n+\t\tfd = open(\"/dev/null\", O_RDWR);\n+\t\tdup2(fd, STDERR_FILENO);\n+\t\tclose(fd);\n+#endif\n+\n+\t\texecvp(argv[0], (char *const *)argv);\n+\t\t_exit(127);\n+\t}\n+\n+\t/* parent */\n+\tif (*type == 'r') {\n+\t\tclose(pfd[1]);\n+\t\tfd = pfd[0];\n+\t} else {\n+\t\tclose(pfd[0]);\n+\t\tfd = pfd[1];\n+\t}\n+\n+\tp->fd = fd;\n+\tp->pid = pid;\n+\n+\treturn 0;\n+}\n+\n+static int pclosev(struct pinfo *p)\n+{\n+\tint stat;\n+\n+\tif (!p || p->fd == -1 || p->pid == 0) {\n+\t\terrno = EINVAL;\n+\t\treturn -1;\n+\t}\n+\n+\tclose(p->fd);  /* XXX check for close() failure? */\n+\tp->fd = -1;\n+\n+\twhile (waitpid(p->pid, &stat, 0) < 0)\n+\t\tif (errno != EINTR)\n+\t\t\treturn -1;\n+\n+\tp->pid = 0;\n+\n+\treturn stat;\n+}\n+\n+static int split_cmdline(const char *cmdline, int max, struct diff_argv *prog)\n+{\n+\tassert(prog);\n+\n+\tif (cmdline && *cmdline && (prog->args = xmalloc(strlen(cmdline)+2))) {\n+\n+\t\tconst char *p = cmdline;\n+\t\tchar *a = prog->args;\n+\t\tint argc = 0;\n+\n+\t\tprog->argv = xmalloc(max * sizeof(char *));\n+\n+\t\twhile( *p ) {\n+\n+\t\t\twhile (*p == ' ' || *p == '\\t')\n+\t\t\t\tp++;\n+\t\t\tif ( !*p )\n+\t\t\t\tbreak;\n+\n+\t\t\tif (argc >= max)\n+\t\t\t\tbreak;\n+\n+\t\t\tprog->argv[argc++] = a;\n+\t\t\twhile ((*a = *p) && *a != ' ' && *a != '\\t')\n+\t\t\t\ta++,p++;\n+\t\t\t*a++ = 0;\n+\n+\t\t}\n+\n+\t\t*a++ = 0;\n+\t\tprog->argc = argc;\n+\t\tprog->argv[argc] = 0;\n+\n+\t\tif (argc == 0) {\n+\t\t\tfree(prog->args);\n+\t\t\tfree(prog->argv);\n+\t\t\treturn -1;\n+\t\t}\n+\n+\t\treturn 0;\n+\t}\n+\n+\treturn -1;\n+}\n+\n+static struct diff_argv *new_diff_argv(const char *cmdline)\n+{\n+\tstruct diff_argv *a = xmalloc(sizeof(*a));\n+\n+\tmemset(a, 0, sizeof(*a));\n+\n+\tif (split_cmdline(cmdline, MAX_DIFF_ARGS, a) < 0) {\n+\t\tfree(a);\n+\t\treturn 0;\n+\t}\n+\n+\treturn a;\n+}\n+\n+static void free_diff_argv(struct diff_argv *a)\n+{\n+\tif (a) {\n+\t\tif (a->args)\n+\t\t\tfree(a->args);\n+\t\tif (a->argv)\n+\t\t\tfree(a->argv);\n+\t\tfree(a);\n+\t}\n+}\n+\n+static int read_from_pipe(int fd, mmbuffer_t *content)\n+{\n+\tssize_t n, size = 1024, total = 0;\n+\tchar *text = xmalloc(size);\n+\n+\tassert(content != 0);\n+\n+\twhile ((n = read(fd, text+total, size-total)) > 0) {\n+\t\tif (n == size-total) {\n+\t\t\tsize *= 2;\n+\t\t\ttext = xrealloc(text, size);\n+\t\t}\n+\t\ttotal += n;\n+\t}\n+\tif (n < 0)\n+\t\treturn -1;\n+\n+\tif (total == 0)\n+\t\tfree(text);\n+\telse {\n+\t\tcontent->ptr  = text;\n+\t\tcontent->size = total;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static void run_external_diff(struct diff_argv *prog, const char* file1, const char* file2, mmbuffer_t *content)\n+{\n+\tchar const **ap;\n+\tstruct pinfo pi;\n+\tint stat, code;\n+\n+\tif (!prog || !prog->args || !prog->argv || prog->argc < 1)\n+\t\tdie(\"internal error: invalid diff argv\");\n+\n+\tif (prog->argc > MAX_DIFF_ARGS - 4)\n+\t\tdie(\"too many arguments for external diff-program\");\n+\n+\tap = &prog->argv[prog->argc];\n+\t*ap++ = \"--\";\n+\t*ap++ = file1;\n+\t*ap++ = file2;\n+\t*ap++ = 0;\n+\n+\tif(popenv(prog->argc+4, prog->argv, \"r\", &pi) < 0)\n+\t\tdie(\"popenv() failed: %s\", strerror(errno));\n+\n+\tif (read_from_pipe(pi.fd, content) < 0)\n+\t\tdie(\"read_from_pipe() failed: %s\", strerror(errno));\n+\n+\tif ((stat = pclosev(&pi)) < 0)\n+\t\tdie(\"pclosev() failed: %s\", strerror(errno));\n+\n+\tif (!WIFEXITED(stat))\n+\t\tdie(\"diff-program '%s' terminated abnormally\", prog->argv[0]);\n+\n+\tif ((code = WEXITSTATUS(stat)) == 127)\n+\t\tdie(\"can't execute external diff-program '%s'\", prog->argv[0]);\n+\n+\tif (code < 0 || code > 1)\n+\t\tdie(\"external diff-program '%s' failed\", prog->argv[0]);\n+}\n+\n+#ifdef DUMMY\n+static void print_buffer(mmbuffer_t *b)\n+{\n+\tssize_t count = 0, n;\n+\n+\tif (b->size == 0)\n+\t\treturn;\n+\n+\twhile ((n = xwrite(STDOUT_FILENO, b->ptr+count, b->size-count)) > 0)\n+\t\tcount += n;\n+}\n+#endif\n+\n+static void external_diff(struct diff_argv *prog, struct finfo *ff, struct finfo *ft, mmbuffer_t *diff)\n+{\n+\tassert(ff != 0 && ft != 0 && diff != 0);\n+\n+\trun_external_diff(prog, ff->name, ft->name, diff);\n+\n+#ifdef DUMMY\n+\tprintf(\"diff %s %s\\n\", ff->name, ft->name);\n+\tprint_buffer(diff);\n+\tprintf(\"--------\\n\");\n+#endif\n+}\n+\n+static int xdiff_output(void *priv_, mmbuffer_t *mb, int nbuf)\n+{\n+\tstruct ecb_info *b = priv_;\n+\tint i;\n+\n+\tfor (i = 0; i < nbuf; i++) {\n+\n+\t\tif (b->used + mb[i].size > b->size) {\n+\t\t\tif (b->size > mb[i].size)\n+\t\t\t\tb->size *= 2;\n+\t\t\telse\n+\t\t\t\tb->size += mb[i].size;\n+\t\t\tb->text = xrealloc(b->text, b->size);\n+\t\t}\n+\n+\t\tmemcpy(b->text+b->used, mb[i].ptr, mb[i].size);\n+\t\tb->used += mb[i].size;\n+\n+\t}\n+\treturn 0;\n+}\n+\n+static void run_internal_diff(mmfile_t *mf1, mmfile_t *mf2, mmbuffer_t *diff)\n+{\n+\txpparam_t xpp;\n+\txdemitconf_t xecfg;\n+\txdemitcb_t ecb;\n+\tstruct ecb_info ecb_data;\n+\n+\tecb_data.text = xmalloc(1024);\n+\tecb_data.size = 1024;\n+\tecb_data.used = 0;\n+\n+\txpp.flags = XDF_NEED_MINIMAL;\n+\n+\txecfg.ctxlen = 0;\n+\txecfg.flags  = 0;\n+\n+\tecb.outf = xdiff_output;\n+\tecb.priv = &ecb_data;\n+\n+\txdl_diff(mf1, mf2, &xpp, &xecfg, &ecb);\n+\n+\tif (ecb_data.used == 0)\n+\t\tfree(ecb_data.text);\n+\telse {\n+\t\tdiff->ptr  = ecb_data.text;\n+\t\tdiff->size = ecb_data.used;\n+\t}\n+}\n+\n+static void internal_diff(struct finfo *ff, struct finfo *ft, mmbuffer_t *diff)\n+{\n+\tassert(ff != 0 && ft != 0 && diff != 0);\n+\n+\tmap_file(ff);\n+\tmap_file(ft);\n+\n+\trun_internal_diff(&ff->mf, &ft->mf, diff);\n+\n+#ifdef DUMMY\n+\tprintf(\"diff %s %s\\n\", ff->name, ft->name);\n+\tprint_buffer(diff);\n+\tprintf(\"--------\\n\");\n+#endif\n+}\n+\n+\n+static void read_diff(struct diff_argv *prog, struct finfo *ff, struct finfo *ft, mmbuffer_t *diff)\n+{\n+\tif (prog)\n+\t\texternal_diff(prog, ff, ft, diff);\n+\telse\n+\t\tinternal_diff(ff, ft, diff);\n+}\n+\n+static char *nextline(char *p, char *limit)\n+{\n+\twhile (p < limit)\n+\t\tif (*p++ == '\\n')\n+\t\t\treturn p;\n+\treturn 0;\n+}\n+\n+static int get_num(char **tp, int *np)\n+{\n+\tchar *p  = *tp;\n+\tint  neg = 0;\n+\tint  num = 0;\n+\n+\t/* can't use: num = strtol(p, tp, 10); because strtol() will\n+\t * skip using isspace() which includes '\\n'.\n+\t */\n+\n+\twhile (*p == ' ' || *p == '\\t') p++;\n+\n+\tif (*p == '-' || *p == '+') {\n+\t\tneg = *p == '-';\n+\t\tp++;\n+\t}\n+\n+\twhile (isdigit(*p))\n+\t\tnum = num * 10 + (*p++ - '0');\n+\n+\tif (*tp == p)\n+\t\treturn 0;\n+\n+\t*tp = p;\n+\t*np = (neg) ? -num : num;\n+\treturn 1;\n+}\n+\n+static int have(char **tp, char c)\n+{\n+\tchar *p = *tp;\n+\n+\twhile (*p == ' ' || *p == '\\t') p++;\n+\n+\tif (*p == c) {\n+\t\t*tp = ++p;\n+\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int at_eol(char **tp)\n+{\n+\tchar *p = *tp;\n+\n+\twhile (*p == ' ' || *p == '\\t') p++;\n+\t*tp = p;\n+\n+\tif (*p == '\\n')\n+\t\treturn 1;\n+\n+\treturn 0;\n+}\n+\n+static int normal_header(char **curp, struct hunk_header *header)\n+{\n+\tchar *p = *curp;\n+\n+\tif (!get_num(&p, &header->fs))\n+\t\treturn 0;\n+\n+\theader->fe = header->fs;\n+\tif (have(&p, ',')) {\n+\t\tif(!get_num(&p, &header->fe))\n+\t\t\treturn 0;\n+\t}\n+\n+\tif (have(&p, 'a'))\n+\t\theader->type = 'a';\n+\telse if (have(&p, 'c'))\n+\t\theader->type = 'c';\n+\telse if (have(&p, 'd'))\n+\t\theader->type = 'd';\n+\telse\n+\t\treturn 0;\n+\n+\tif (header->type == 'a') {\n+\t\tassert(header->fs == header->fe);\n+\t\theader->fe--;  /* null (zero) range of lines */\n+\t}\n+\n+\tif (!get_num(&p, &header->ts))\n+\t\treturn 0;\n+\n+\theader->te = header->ts;\n+\tif (have(&p, ',')) {\n+\t\tif(!get_num(&p, &header->te))\n+\t\t\treturn 0;\n+\t}\n+\n+\tif (header->type == 'd') {\n+\t\tassert(header->ts == header->te);\n+\t\theader->te--;  /* null (zero) range of lines */\n+\t}\n+\n+\tif(!at_eol(&p))\n+\t\treturn 0;\n+\n+\t*curp = ++p;\n+\treturn 1;\n+}\n+\n+static int determine_diff_format(mmbuffer_t *content, char** curp)\n+{\n+\tchar *p     = content->ptr;\n+\tchar *limit = p + content->size;\n+\tchar *p2, *p3, *p4;\n+\tstruct hunk_header head;\n+\n+\t*curp = p;\n+\n+\tif((p2 = nextline(p, limit)) == 0)\n+\t\treturn UNKNOWN_FORMAT;\n+\n+\t/* internal (unified) diff, no header */\n+\tif (memcmp(p, \"@@ \", 3) == 0)\n+\t\treturn UNIFIED_FORMAT;\n+\n+\t/* normal format diff */\n+\tif (normal_header(&p, &head))\n+\t\treturn NORMAL_FORMAT;\n+\n+\tif((p3 = nextline(p2, limit)) == 0)\n+\t\treturn UNKNOWN_FORMAT;\n+\n+\t/* external (unified) diff, with header */\n+\tif (memcmp(p,  \"--- \", 4) == 0 &&\n+\t    memcmp(p2, \"+++ \", 4) == 0 &&\n+\t    memcmp(p3, \"@@ \",  3) == 0) {\n+\n+\t\t*curp = p3;\n+\t\treturn UNIFIED_FORMAT;\n+\t}\n+\n+\t/* context diff */\n+\tif (memcmp(p,  \"*** \", 4) == 0 &&\n+\t    memcmp(p2, \"--- \", 4) == 0 &&\n+\t    memcmp(p3, \"****\", 4) == 0) {\n+\n+\t\tif((p4 = nextline(p3, limit)) == 0)\n+\t\t\treturn UNKNOWN_FORMAT;\n+\n+\t\t*curp = p4;\n+\t\treturn CONTEXT_FORMAT;\n+\t}\n+\n+\treturn UNKNOWN_FORMAT;\n+}\n+\n+static void get_line(char **curp, char *limit, char type, int num, struct hunk_lines *hl)\n+{\n+\tchar *p = *curp;\n+\tint  normal = (type == '<') || (type == '>');\n+\tchar *pn;\n+\n+\tassert(p < limit);\n+\n+\tif (*p++ != type || (normal && *p++ != ' '))\n+\t\tdie(\"invalid diff: leading line chars\");\n+\n+\thl->lines[num] = p;\n+\n+\tif ((pn = nextline(p, limit)) == 0)\n+\t\tdie(\"invalid diff: missing eol #3\");\n+\n+\thl->lengths[num] = (int)(pn - p);\n+\n+\t/* check for \"\\ No newline at end of file\" */\n+\tif (pn < limit && *pn == '\\\\') {\n+\t\t/* remove nl from length and skip */\n+\t\thl->lengths[num] = (int)(pn - p) - 1;\n+\t\tpn = nextline(pn, limit);\n+\t}\n+\n+\t*curp = pn;\n+}\n+\n+static void process_normal_diff(struct diff2 *d, char *p)\n+{\n+\tmmbuffer_t *content = &d->content;\n+\tchar *limit = content->ptr + content->size;\n+\tstruct diff2_hunk *hunk, **last_hunk;\n+\tint i;\n+\n+\tlast_hunk = &d->hunks;\n+\n+\twhile (p < limit) {\n+\t\tstruct hunk_header head;\n+\n+\t\thunk = new_diff2_hunk();\n+\n+\t\t/* hunk header: <int>[,<int>]<type><int>[,<int>] */\n+\t\tif (!normal_header(&p, &head))\n+\t\t\tdie(\"invalid diff: header\");\n+\n+\t\thunk->type = head.type;\n+\n+\t\t/* from-file hunk lines (if any) */\n+\t\thunk->from.start = head.fs;\n+\t\thunk->from.end   = head.fe;\n+\t\tif (head.type != 'a') {\n+\t\t\tint numlines = head.fe - head.fs + 1;\n+\n+\t\t\tassert(numlines > 0);\n+\n+\t\t\talloc_line_arrays(numlines, &hunk->from);\n+\n+\t\t\tfor (i = 0; i < numlines; i++)\n+\t\t\t\tget_line(&p, limit, '<', i, &hunk->from);\n+\t\t}\n+\n+\t\t/* skip change hunk separator (if any) */\n+\t\tif (head.type == 'c') {\n+\t\t\tif (memcmp(p, \"---\\n\", 4) != 0)\n+\t\t\t\tdie(\"invalid diff: missing change separator\");\n+\t\t\tp += 4;\n+\t\t}\n+\n+\t\t/* to-file hunk lines (if any) */\n+\t\thunk->to.start = head.ts;\n+\t\thunk->to.end   = head.te;\n+\t\tif (head.type != 'd') {\n+\t\t\tint numlines = head.te - head.ts + 1;\n+\n+\t\t\tassert(numlines > 0);\n+\n+\t\t\talloc_line_arrays(numlines, &hunk->to);\n+\n+\t\t\tfor (i = 0; i < numlines; i++)\n+\t\t\t\tget_line(&p, limit, '>', i, &hunk->to);\n+\t\t}\n+\n+\t\t/* add this hunk to the end of the list */\n+\t\t*last_hunk = hunk;\n+\t\tlast_hunk  = &hunk->next;\n+\n+\t}\n+\n+\t*last_hunk = 0;\n+}\n+\n+static int have_str(char **tp, char *s)\n+{\n+\tchar *p = *tp;\n+\tint  len = strlen(s);\n+\n+\tif (memcmp(p, s, len) == 0) {\n+\t\tp += len;\n+\t\t*tp = p;\n+\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int unified_header(char **curp, struct unified_hunk_header *header)\n+{\n+\tchar *p = *curp;\n+\n+\tif (!have_str(&p, \"@@ -\"))\n+\t\treturn 0;\n+\n+\tif (!get_num(&p, &header->fs))\n+\t\treturn 0;\n+\n+\theader->fc = 1;\n+\tif (have(&p, ',')) {\n+\t\tif(!get_num(&p, &header->fc))\n+\t\t\treturn 0;\n+\t}\n+\n+\tif (!have_str(&p, \" +\"))\n+\t\treturn 0;\n+\n+\tif (!get_num(&p, &header->ts))\n+\t\treturn 0;\n+\n+\theader->tc = 1;\n+\tif (have(&p, ',')) {\n+\t\tif(!get_num(&p, &header->tc))\n+\t\t\treturn 0;\n+\t}\n+\n+\tif (!have_str(&p, \" @@\"))\n+\t\treturn 0;\n+\n+\tif(!at_eol(&p))\n+\t\treturn 0;\n+\n+\t*curp = ++p;\n+\treturn 1;\n+}\n+\n+static int count_hunk_lines(char *p, char *limit, char type)\n+{\n+\tint num = 0;\n+\n+\twhile (p < limit && *p == type) {\n+\t\tchar *pn;\n+\n+\t\tif ((pn = nextline(p, limit)) == 0)\n+\t\t\tdie(\"invalid diff: missing eol #1\");\n+\n+\t\tnum++;\n+\t\tp = pn;\n+\t}\n+\n+\treturn num;\n+}\n+\n+static void process_unified_diff(struct diff2 *d, char *p)\n+{\n+\tmmbuffer_t *content = &d->content;\n+\tchar *limit = content->ptr + content->size;\n+\tstruct diff2_hunk *hunk, **last_hunk;\n+\tint i;\n+\n+\tlast_hunk = &d->hunks;\n+\n+\twhile (p < limit) {\n+\t\tstruct unified_hunk_header head;\n+\t\tint single_hunk = 0;\n+\n+\t\t/* hunk header: @@ -<int>[,<int>] +<int>[,<int>] @@ */\n+\t\tif (!unified_header(&p, &head))\n+\t\t\tdie(\"invalid diff: header\");\n+\n+\t\tsingle_hunk = (head.fc == 0 || head.tc == 0);\n+\n+\t\tfor (;;) {  /* for all hunks */\n+\t\t\tint cc = 0, fc = 0, tc = 0;\n+\n+\t\t\t/* find begining of next hunk: skip common lines */\n+\t\t\twhile (p < limit && *p == ' ') {\n+\t\t\t\tchar *pn;\n+\n+\t\t\t\tcc++;\n+\t\t\t\thead.fs++; head.fc--;\n+\t\t\t\thead.ts++; head.tc--;\n+\n+\t\t\t\tif ((pn = nextline(p, limit)) == 0)\n+\t\t\t\t\tdie(\"invalid diff: missing eol #2\");\n+\t\t\t\tp = pn;\n+\t\t\t}\n+\n+\t\t\t/* finished? */\n+\t\t\tif (limit <= p || *p == '@') {\n+\t\t\t\tassert(head.fc == 0 && head.tc == 0);\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (*p != '-' && *p != '+')\n+\t\t\t\tdie(\"invalid diff: missing -/+ lines\");\n+\n+\t\t\thunk = new_diff2_hunk();\n+\n+\t\t\thunk->from.start = hunk->from.end = head.fs;\n+\t\t\thunk->to.start   = hunk->to.end   = head.ts;\n+\n+\t\t\t/* from-file hunk lines (if any) */\n+\t\t\tfc = count_hunk_lines(p, limit, '-');\n+\t\t\tif (fc > 0) {\n+\t\t\t\talloc_line_arrays(fc, &hunk->from);\n+\n+\t\t\t\tfor (i = 0; i < fc; i++)\n+\t\t\t\t\tget_line(&p, limit, '-', i, &hunk->from);\n+\n+\t\t\t\thunk->from.end += fc-1;\n+\n+\t\t\t\thead.fs += fc;\n+\t\t\t\thead.fc -= fc;\n+\t\t\t}\n+\n+\t\t\t/* to-file hunk lines (if any) */\n+\t\t\ttc = count_hunk_lines(p, limit, '+');\n+\t\t\tif (tc > 0) {\n+\t\t\t\talloc_line_arrays(tc, &hunk->to);\n+\n+\t\t\t\tfor (i = 0; i < tc; i++)\n+\t\t\t\t\tget_line(&p, limit, '+', i, &hunk->to);\n+\n+\t\t\t\thunk->to.end += tc-1;\n+\n+\t\t\t\thead.ts += tc;\n+\t\t\t\thead.tc -= tc;\n+\t\t\t}\n+\n+\t\t\t/* set hunk type */\n+\t\t\tassert(fc > 0 || tc > 0);\n+\t\t\tif (fc == 0) {\n+\t\t\t\thunk->type = 'a';\n+\t\t\t\tif (!single_hunk)\n+\t\t\t\t\thunk->from.start--;\n+\t\t\t\thunk->from.end = hunk->from.start - 1;\n+\t\t\t} else if (tc == 0) {\n+\t\t\t\thunk->type = 'd';\n+\t\t\t\tif (!single_hunk)\n+\t\t\t\t\thunk->to.start--;\n+\t\t\t\thunk->to.end = hunk->to.start - 1;\n+\t\t\t} else {\n+\t\t\t\thunk->type = 'c';\n+\t\t\t}\n+\n+\t\t\t/* add this hunk to the end of the list */\n+\t\t\t*last_hunk = hunk;\n+\t\t\tlast_hunk  = &hunk->next;\n+\t\t}\n+\n+\t}\n+\n+\t*last_hunk = 0;\n+\n+}\n+\n+struct diff2* process_diff(struct diff_argv *prog, struct finfo *ff, struct finfo *ft)\n+{\n+\tstruct diff2 *result = new_diff2(ff, ft);\n+\tchar *scan;\n+\n+\tread_diff(prog, ff, ft, &result->content);\n+\n+\tif (result->content.size == 0)\n+\t\treturn result;  /* empty diff is ok */\n+\n+\tassert(result->content.size > 0);\n+\n+\tif (result->content.ptr[result->content.size-1] != '\\n')\n+\t\tdie(\"invalid diff: missing eol on last line\");\n+\n+\tswitch (determine_diff_format(&result->content, &scan)) {\n+\t\tcase NORMAL_FORMAT:\n+\t\t\tprocess_normal_diff(result, scan);\n+\t\t\tbreak;\n+\t\tcase UNIFIED_FORMAT:\n+\t\t\tprocess_unified_diff(result, scan);\n+\t\t\tbreak;\n+\t\tcase CONTEXT_FORMAT:\n+\t\t\tdie(\"context diff format not supported\");\n+\t\t\tbreak;\n+\t\tcase UNKNOWN_FORMAT:\n+\t\tdefault:\n+\t\t\tdie(\"unknown diff format\");\n+\t\t\tbreak;\n+\t}\n+\n+\treturn result;\n+}\n+\n+static void adjust_diff2(struct diff2 *d)\n+{\n+\tstruct diff2_hunk *p;\n+\n+\tfor (p = d->hunks; p; p = p->next) {\n+\t\tif (p->type == 'a') {\n+\t\t\tp->from.start++;\n+\t\t\tp->from.end++;\n+\t\t} else if (p->type == 'd') {\n+\t\t\tp->to.start++;\n+\t\t\tp->to.end++;\n+\t\t}\n+\t}\n+}\n+\n+static int copy_lines(struct hunk_lines *dst, int off, struct hunk_lines *src)\n+{\n+\tchar **s = src->lines;\n+\tint  *sl = src->lengths;\n+\tchar **d = dst->lines + off;\n+\tint  *dl = dst->lengths + off;\n+\tint  n   = src->size;\n+\n+\tassert(n <= dst->size - off);\n+\n+\twhile(n--) {\n+\t\tif (*d) {\n+\t\t\tif (*sl != *dl || memcmp(*s, *d, *sl)) {\n+\t\t\t\treturn 0;\n+\t\t\t}\n+\t\t} else {\n+\t\t\t*d  = *s;\n+\t\t\t*dl = *sl;\n+\t\t}\n+\t\td++; dl++;\n+\t\ts++; sl++;\n+\t}\n+\treturn 1;\n+}\n+\n+static int equal_lines(struct hunk_lines *lhs, struct hunk_lines *rhs)\n+{\n+\tchar **l = lhs->lines;\n+\tint  *ll = lhs->lengths;\n+\tchar **r = rhs->lines;\n+\tint  *rl = rhs->lengths;\n+\tint  n   = lhs->size;\n+\n+\tif (n != rhs->size)\n+\t\treturn 0;\n+\n+\twhile (n--) {\n+\t\tif (!*l || !*r || *ll != *rl || memcmp(*l, *r, *ll))\n+\t\t\treturn 0;\n+\t\tl++; ll++;\n+\t\tr++; rl++;\n+\t}\n+\treturn 1;\n+}\n+\n+static int get_low_thread(struct diff2_hunk *p[2])\n+{\n+\tif (!p[0])\n+\t\treturn 1;\n+\tif (!p[1])\n+\t\treturn 0;\n+\treturn (p[0]->to.start > p[1]->to.start) ? 1 : 0;\n+}\n+\n+static void init_segment(struct segment *s, int from, int to)\n+{\n+\ts->from  = from;\n+\ts->to    = to;\n+\ts->head  = 0;\n+\ts->tail  = 0;\n+\ts->count = 0;\n+}\n+\n+static void add_segment(struct segment *s, struct diff2_hunk *d)\n+{\n+\tassert(d != 0);\n+\n+\tif (!s->head)\n+\t\ts->head = s->tail = d;\n+\telse\n+\t\ts->tail = d;\n+\ts->count++;\n+}\n+\n+static struct diff3_hunk *make_diff3_hunk(struct segment use[2],\n+\t\tint low_thread, int high_thread, struct diff3_hunk *last)\n+{\n+\tstruct diff3_hunk *result = new_diff3_hunk();\n+\tint startc, endc;\n+\tint i, common;\n+\tint from0, from1;\n+\n+\tassert(use[0].to == use[1].to);\n+\tassert(use[0].from != use[1].from);\n+\n+\tfrom0 = use[0].from;\n+\tfrom1 = use[1].from;\n+\n+\tcommon = use[0].to;\n+\tassert(common >= 0 && common <= 2);\n+\n+\t/* find start/end line numbers from the common file */\n+\tstartc = result->f[common].start = use[low_thread].head->to.start;\n+\tendc   = result->f[common].end   = use[high_thread].tail->to.end;\n+\n+\t/* find start/end line numbers for other files */\n+\tfor (i = 0; i < 2; i++) {\n+\t\tstruct segment *s = &use[i];\n+\t\tstruct diff2_hunk *h = s->head;\n+\t\tstruct diff2_hunk *t = s->tail;\n+\t\tint file = s->from;\n+\t\tint start = startc, end = endc;\n+\n+\t\tassert(file >= 0 && file <= 2);\n+\n+\t\tif (h) {\n+\t\t\tstart = startc - h->to.start + h->from.start;\n+\t\t\tend   = endc   - t->to.end   + t->from.end;\n+\t\t} else if (last) {\n+\t\t\tint d = last->f[file].end - last->f[common].end;\n+\t\t\tstart = startc + d;\n+\t\t\tend   = endc   + d;\n+\t\t}\n+\t\tresult->f[file].start = start;\n+\t\tresult->f[file].end   = end;\n+\t}\n+\n+\t/* allocate hunk_lines line pointer and lengths arrays */\n+\tfor (i = 0; i < 3; i++) {\n+\t\tint numlines = result->f[i].end - result->f[i].start + 1;\n+\n+\t\tif (numlines > 0)\n+\t\t\talloc_line_arrays(numlines, &result->f[i]);\n+\t}\n+\n+\t/* copy line info for common file */\n+\tfor (i = 0; i < 2; i++) {\n+\t\tstruct segment *s = &use[i];\n+\t\tstruct diff2_hunk *h = s->head;\n+\t\tint j;\n+\n+\t\tfor (j = 0; j < s->count; j++,h = h->next) {\n+\t\t\tint offset = h->to.start - startc;\n+\n+\t\t\tif (!copy_lines(&result->f[common], offset, &h->to))\n+\t\t\t\tdie(\"internal error: copy_lines()\");\n+\n+\t\t}\n+\t}\n+\n+\t/* copy line info for other files */\n+\tfor (i = 0; i < 2; i++) {\n+\t\tstruct segment *s = &use[i];\n+\t\tstruct diff2_hunk *h = s->head;\n+\t\tstruct hunk_lines *tf, *cf;\n+\t\tint start, end, file = s->from;\n+\t\tint j, k, l, m;\n+\n+\t\tassert(file >= 0 && file <= 2);\n+\n+\t\ttf = &result->f[file];\n+\t\tcf = &result->f[common];\n+\n+\t\tstart = tf->start;\n+\t\tend   = tf->end;\n+\n+\t\t/* before first hunk */\n+\t\tk = (h) ? h->from.start : end+1;\n+\t\tfor (j = 0; j + start < k; j++) {\n+\t\t\ttf->lines[j]   = cf->lines[j];\n+\t\t\ttf->lengths[j] = cf->lengths[j];\n+\t\t}\n+\n+\t\t/* hunk list */\n+\t\tfor (j = 0; j < s->count; j++,h = h->next) {\n+\t\t\tint offset = h->from.start - start;\n+\n+\t\t\tif (!copy_lines(&result->f[file], offset, &h->from))\n+\t\t\t\tdie(\"internal error:\");\n+\n+\t\t\t/* between this and next hunk */\n+\t\t\tl = h->to.end + 1 - startc;\n+\t\t\tif (j < s->count-1)\n+\t\t\t\tk = h->next->from.start - start;\n+\t\t\telse\n+\t\t\t\tk = end+1 - start;\n+\t\t\tfor (m = h->from.end + 1 - start; m < k; m++,l++) {\n+\t\t\t\ttf->lines[m]   = cf->lines[l];\n+\t\t\t\ttf->lengths[m] = cf->lengths[l];\n+\t\t\t}\n+\n+\t\t}\n+\n+\t}\n+\n+\t/* set diff3 hunk type */\n+\tif (!use[0].head)\n+\t\tresult->type = '0' + from1;\n+\telse if (!use[1].head)\n+\t\tresult->type = '0' + from0;\n+\telse {\n+\t\tif (equal_lines(&result->f[from0], &result->f[from1]))\n+\t\t\tresult->type = '0' + common;\n+\t\telse\n+\t\t\tresult->type = 'a';\n+\t}\n+\n+\treturn result;\n+}\n+\n+static struct diff3 *make_3way_diff(struct diff2 *d01, struct diff2 *d21)\n+{\n+\tstruct diff3 *result = new_diff3(d01, d21);\n+\tstruct diff2_hunk *diff01 = d01->hunks;\n+\tstruct diff2_hunk *diff21 = d21->hunks;\n+\tstruct diff2_hunk *p[2], *high_diff, *other_diff;\n+\tstruct diff3_hunk *hunk, **last_hunk;\n+\tstruct diff3_hunk *last;\n+\tstruct segment use[2];\n+\tint low_thread, high_thread;\n+\tint other_thread, high_line;\n+\n+\tassert(d01->ft->num == d21->ft->num);\n+\tassert(d01->ff->num != d21->ff->num);\n+\n+\tadjust_diff2(d01);\n+\tadjust_diff2(d21);\n+\n+\tlast_hunk = &result->hunks;\n+\tlast = 0;\n+\tp[0] = diff01;\n+\tp[1] = diff21;\n+\n+\twhile (p[0] || p[1]) {\n+\t\tinit_segment(&use[0], d01->ff->num, d01->ft->num);\n+\t\tinit_segment(&use[1], d21->ff->num, d21->ft->num);\n+\n+\t\thigh_thread = low_thread = get_low_thread(p);\n+\n+\t\thigh_diff = p[high_thread];\n+\t\thigh_line = high_diff->to.end;\n+\n+\t\tadd_segment(&use[high_thread], high_diff);\n+\t\tp[high_thread] = high_diff->next;\n+\n+\t\tother_thread = high_thread ^ 0x1;\n+\t\tother_diff   = p[other_thread];\n+\n+\t\twhile (other_diff && other_diff->to.start <= high_line+1) {\n+\n+\t\t\tadd_segment(&use[other_thread], other_diff);\n+\t\t\tp[other_thread] = p[other_thread]->next;\n+\n+\t\t\tif (high_line < other_diff->to.end) {\n+\t\t\t\thigh_thread ^= 0x1;\n+\t\t\t\thigh_diff = other_diff;\n+\t\t\t\thigh_line = other_diff->to.end;\n+\t\t\t}\n+\n+\t\t\tother_thread = high_thread ^ 0x1;\n+\t\t\tother_diff   = p[other_thread];\n+\t\t}\n+\n+\t\thunk = make_diff3_hunk(use, low_thread, high_thread, last);\n+\n+\t\tif (!hunk)\n+\t\t\tdie(\"can't create diff3 hunk\");\n+\n+\t\t/* add this hunk to the end of the list */\n+\t\t*last_hunk = hunk;\n+\t\tlast_hunk  = &hunk->next;\n+\n+\t\tlast = hunk;\n+\t}\n+\n+\t*last_hunk = 0;\n+\n+\treturn result;\n+}\n+\n+#ifdef DUMMY\n+static void print_diff2_hunk(struct diff2_hunk *p)\n+{\n+\tstruct hunk_lines *f = &p->from;\n+\tstruct hunk_lines *t = &p->to;\n+\tint i, type = p->type;\n+\n+\tprintf(\"%d,%d %c %d,%d\\n\", f->start, f->end, type, t->start, t->end);\n+\n+\tfor (i = 0; i < f->size; i++)\n+\t\tprintf(\"< %.*s\", f->lengths[i], f->lines[i]);\n+\n+\tprintf(\"---\\n\");\n+\n+\tfor (i = 0; i < t->size; i++)\n+\t\tprintf(\"> %.*s\", t->lengths[i], t->lines[i]);\n+\n+\tprintf(\"+++\\n\");\n+}\n+\n+static void print_diff2(struct diff2 *d)\n+{\n+\tstruct diff2_hunk *p;\n+\n+\tprintf(\"<--- diff2 --->\\n\");\n+\tfor (p = d->hunks; p; p = p->next)\n+\t\tprint_diff2_hunk(p);\n+\tprintf(\">=============<\\n\");\n+}\n+#endif\n+\n+static void print_diff3_hunk(FILE *outf, struct diff3_hunk *p, char *prefix)\n+{\n+\tint i, j, k, skip_print;\n+\n+\tif (p->type == 'a')\n+\t\tfprintf(outf, \"====\\n\");\n+\telse\n+\t\tfprintf(outf, \"====%c\\n\", p->type+1);\n+\n+\tswitch (p->type) {\n+\t\tcase '0': skip_print = 1; break;\n+\t\tcase '1': skip_print = 0; break;\n+\t\tcase '2': skip_print = 0; break;\n+\t\tcase 'a': skip_print = 3; break;\n+\t\tdefault:\n+\t\t\tdie(\"internal error: invalid diff3 hunk type\");\n+\t\t\tbreak;\n+\t}\n+\n+\tfor (j = 0,k = 0; j < 3; j++,k++) {\n+\t\tint  numlines, start, end, len;\n+\t\tchar *s;\n+\n+\t\tif (p->type == '1' && j > 0)\n+\t\t\tk = (j == 1) ? 2 : 1;\n+\n+\t\tstart = p->f[k].start;\n+\t\tend   = p->f[k].end;\n+\n+\t\tnumlines = end - start + 1;\n+\n+\t\tif (numlines == 0)\n+\t\t\tfprintf(outf, \"%d:%da\\n\", k+1, start-1);\n+\t\telse if (numlines == 1)\n+\t\t\tfprintf(outf, \"%d:%dc\\n\", k+1, start);\n+\t\telse\n+\t\t\tfprintf(outf, \"%d:%d,%dc\\n\", k+1, start, end);\n+\n+\t\tif (k == skip_print)\n+\t\t\tcontinue;\n+\n+\t\tassert(numlines == p->f[k].size);\n+\n+\t\tif (p->f[k].size <= 0)\n+\t\t\tcontinue;\n+\n+\t\ts   = 0;\n+\t\tlen = 0;\n+\n+\t\tfor (i = 0; i < p->f[k].size; i++) {\n+\t\t\ts = p->f[k].lines[i];\n+\t\t\tlen = p->f[k].lengths[i];\n+\t\t\tfprintf(outf, \"%s\", prefix);\n+\t\t\tfwrite(s, 1, len, outf);\n+\t\t}\n+\n+\t\tif (s && (len == 0 || s[len-1] != '\\n'))\n+\t\t\tfprintf(outf, \"\\n\\\\ No newline at end of file\\n\");\n+\n+\t}\n+\n+}\n+\n+static void print_diff3(FILE *outf, struct diff3 *d, struct diff3_options *o)\n+{\n+\tstruct diff3_hunk *p;\n+\tchar *prefix = (o->initial_tab) ? \"\\t\" : \"  \";\n+\n+\tfor (p = d->hunks; p; p = p->next)\n+\t\tprint_diff3_hunk(outf, p, prefix);\n+}\n+\n+static int write_lines(FILE *outf, char **curp, char *limit, int num)\n+{\n+\tchar *p = *curp;\n+\tchar *pn;\n+\tint  size;\n+\n+\tassert(num >= 0);\n+\n+\twhile (num--) {\n+\t\tif ((pn = nextline(p, limit)) == 0) {\n+\t\t\tif (num > 0)\n+\t\t\t\treturn -1;\n+\t\t\tpn = limit;\n+\t\t}\n+\t\tp = pn;\n+\t}\n+\tsize = (int)(p - *curp);\n+\tif (size > 0)\n+\t\tfwrite(*curp, 1, size, outf);\n+\t*curp = p;\n+\treturn 0;\n+}\n+\n+static int skip_lines(char **curp, char *limit, int num)\n+{\n+\tchar *p = *curp;\n+\tchar *pn;\n+\n+\tassert(num >= 0);\n+\n+\twhile (num--) {\n+\t\tif ((pn = nextline(p, limit)) == 0) {\n+\t\t\tif (num > 0)\n+\t\t\t\treturn -1;\n+\t\t\tpn = limit;\n+\t\t}\n+\t\tp = pn;\n+\t}\n+\t*curp = p;\n+\treturn 0;\n+}\n+\n+static int diff3_merge(FILE *outf, mmfile_t *inf, struct diff3 *d, struct finfo f[3], struct diff3_options *opts)\n+{\n+\tstruct diff3_hunk *p;\n+\tint conflicts = 0;\n+\tint inf_lines = 0;\n+\tchar *infp, *inf_limit;\n+\n+\tinfp = inf->ptr;\n+\tinf_limit = infp + inf->size;\n+\n+\tfor (p = d->hunks; p; p = p->next) {\n+\t\tint conflict = 0;\n+\t\tint i, lines;\n+\n+\t\t/* check if we can skip this block */\n+\t\tswitch (p->type) {\n+\t\t\tdefault:\n+\t\t\tcase '0': /* change unique to our file: skip */\n+\t\t\t\tcontinue;\n+\t\t\t\tbreak;\n+\t\t\tcase '1': /* same in ours and theirs: merged change */\n+\t\t\t\tif (!opts->show_all)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tconflict = 1;\n+\t\t\t\tbreak;\n+\t\t\tcase '2': /* change only in theirs: un-merged change */\n+\t\t\t\tif (opts->overlap_only)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tbreak;\n+\t\t\tcase 'a': /* all files differ: overlapping change */\n+\t\t\t\tif (opts->unmerged_only)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tconflict = opts->markers;\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\t/* write lines from '0' (our) file (if any) */\n+\t\tlines = p->f[0].start - inf_lines - 1;\n+\t\tif (lines > 0) {\n+\t\t\tif (write_lines(outf, &infp, inf_limit, lines) < 0)\n+\t\t\t\tdie(\"unexpected eof on file\");\n+\t\t\tinf_lines += lines;\n+\t\t}\n+\n+\t\tif (conflict) {\n+\t\t\t/* write lines from files with conflict markers */\n+\t\t\tchar *marker_fmt = \"<<<<<<< %s\\n\";\n+\n+\t\t\tconflicts++;\n+\n+\t\t\tif (p->type == 'a') {\n+\t\t\t\t/* write lines from '0' (our) file */\n+\t\t\t\tfprintf(outf, marker_fmt, f[0].label);\n+\t\t\t\tfor (i = 0; i < p->f[0].size; i++) {\n+\t\t\t\t\tchar *s = p->f[0].lines[i];\n+\t\t\t\t\tint len = p->f[0].lengths[i];\n+\t\t\t\t\tfwrite(s, 1, len, outf);\n+\t\t\t\t}\n+\t\t\t\tmarker_fmt = \"||||||| %s\\n\";\n+\t\t\t}\n+\n+\t\t\tif (opts->show_all) {\n+\t\t\t\t/* write lines from '1' (base) file */\n+\t\t\t\tfprintf(outf, marker_fmt, f[1].label);\n+\t\t\t\tfor (i = 0; i < p->f[1].size; i++) {\n+\t\t\t\t\tchar *s = p->f[1].lines[i];\n+\t\t\t\t\tint len = p->f[1].lengths[i];\n+\t\t\t\t\tfwrite(s, 1, len, outf);\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tfprintf(outf, \"=======\\n\");\n+\n+\t\t}\n+\n+\t\t/* write lines from '2' (their) file */\n+\t\tfor (i = 0; i < p->f[2].size; i++) {\n+\t\t\tchar *s = p->f[2].lines[i];\n+\t\t\tint len = p->f[2].lengths[i];\n+\t\t\tfwrite(s, 1, len, outf);\n+\t\t}\n+\n+\t\t/* add conflict marker */\n+\t\tif (conflict)\n+\t\t\tfprintf(outf, \">>>>>>> %s\\n\", f[2].label);\n+\n+\t\t/* skip lines from '0' (our) file */\n+\t\tlines = p->f[0].size;\n+\t\tif (lines > 0) {\n+\t\t\tif (skip_lines(&infp, inf_limit, lines) < 0)\n+\t\t\t\tdie(\"unexpected eof\");\n+\t\t\tinf_lines += lines;\n+\t\t}\n+\n+\t}\n+\n+\t/* write remainder of '0' (our) file */\n+\tif (infp < inf_limit)\n+\t\tfwrite(infp, 1, (int)(inf_limit - infp), outf);\n+\n+\treturn conflicts;\n+}\n+\n+int diff3(FILE *outf, const char *file[3], const char *label[3], struct diff3_options *opts)\n+{\n+\tint i;\n+\tstruct finfo f[3];\n+\tstruct diff2 *d1, *d2;\n+\tstruct diff3 *d3;\n+\tstruct diff_argv *prog = 0;\n+\tint conflicts = 0;\n+\n+\tfor ( i = 0; i < 3; i++ )\n+\t\tinit_finfo(&f[i], file[i], label[i], i);\n+\n+\tif (opts->diff_prog)\n+\t\tprog = new_diff_argv(opts->diff_prog);\n+\n+\td2 = process_diff(prog, &f[2], &f[1]);\n+\tfree_mmfile(&f[2].mf);\n+\n+\td1 = process_diff(prog, &f[0], &f[1]);\n+\tfree_mmfile(&f[1].mf);\n+\n+\td3 = make_3way_diff(d1, d2);\n+\n+\tif (opts->merge) {\n+\t\tmap_file(&f[0]);\n+\t\tconflicts = diff3_merge(outf, &f[0].mf, d3, f, opts);\n+\t} else {\n+\t\tprint_diff3(outf, d3, opts);\n+\t}\n+\n+\tfree_mmfile(&f[0].mf);\n+\tfree_diff3(d3);  /* also free()'s d1 and d2 */\n+\tfree_diff_argv(prog);\n+\n+\treturn conflicts;\n+}\n+\n+\n+static const char builtin_diff3_usage[] =\n+\"git-diff3 [options]... ours base theirs\\n\"\n+\"\\n\"\n+\"  -e  --ed            output unmerged changes from BASE to THEIRS into OURS\\n\"\n+\"  -E  --show-overlap  output unmerged changes, bracketing conflicts\\n\"\n+\"  -A  --show-all      output all changes, bracketing conflicts\\n\"\n+\"  -x  --overlap-only  output overlapping changes\\n\"\n+\"  -X                  output overlapping changes, bracketing them\\n\"\n+\"  -3  --easy-only     output unmerged non-overlapping changes\\n\"\n+\"\\n\"\n+\"  -m  --merge         output merged file instead of ed script\\n\"\n+\"  -T  --initial-tab   make tabs line up by prepending a tab\\n\"\n+\"\\n\"\n+\"  -L LABEL  --label=LABEL  use LABEL instead of filename\\n\"\n+\"  --diff-program=PROGRAM   use PROGRAM to compare files\\n\"\n+;\n+\n+\n+int cmd_diff3(int argc, const char **argv, const char *prefix)\n+{\n+\tint i;\n+\tconst char *label_strings[3];\n+\tint label_count = 0;\n+\tint conflicts = 0;\n+\tint edarg = 0;\n+\tconst char **file;\n+\tstruct diff3_options opts;\n+\n+\tmemset(&opts, 0, sizeof(opts));\n+\n+\tfor (i = 1 ; i < argc ; i++) {\n+\t\tconst char *arg = argv[i];\n+\n+\t\tif (*arg != '-')\n+\t\t\tbreak;\n+\t\tif (!strcmp(arg, \"--\")) {\n+\t\t\ti++;\n+\t\t\tbreak;\n+\t\t}\n+\t\tif (!strcmp(arg, \"-e\") || !strcmp(arg, \"--ed\")) {\n+\t\t\tedarg++;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"-E\") || !strcmp(arg, \"--show-overlap\")) {\n+\t\t\tedarg++;\n+\t\t\topts.markers = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"-A\") || !strcmp(arg, \"--show-all\")) {\n+\t\t\tedarg++;\n+\t\t\topts.show_all = 1;\n+\t\t\topts.markers = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"-x\") || !strcmp(arg, \"--overlap-only\")) {\n+\t\t\tedarg++;\n+\t\t\topts.overlap_only = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"-X\")) {\n+\t\t\tedarg++;\n+\t\t\topts.overlap_only = 1;\n+\t\t\topts.markers = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"-3\") || !strcmp(arg, \"--easy-only\")) {\n+\t\t\tedarg++;\n+\t\t\topts.unmerged_only = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"-m\") || !strcmp(arg, \"--merge\")) {\n+\t\t\topts.merge = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"-T\") || !strcmp(arg, \"--initial-tab\")) {\n+\t\t\topts.initial_tab = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"-L\")) {\n+\t\t\tif ( argc <= i+1 )\n+\t\t\t\tdie(\"-L needs a LABEL argument\");\n+\t\t\tif ( label_count < 3 )\n+\t\t\t\tlabel_strings[label_count++] = argv[++i];\n+\t\t\telse\n+\t\t\t\tdie(\"too many labels options specified\");\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strncmp(arg, \"--label=\", 8)) {\n+\t\t\tif ( !*(arg+8) )\n+\t\t\t\tdie(\"--label needs a LABEL argument\");\n+\t\t\tif ( label_count < 3 )\n+\t\t\t\tlabel_strings[label_count++] = arg+8;\n+\t\t\telse\n+\t\t\t\tdie(\"too many labels options specified\");\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strncmp(arg, \"--diff-program=\", 15)) {\n+\t\t\tif ( !*(arg+15) )\n+\t\t\t\tdie(\"--diff-program needs a PROGRAM argument\");\n+\t\t\topts.diff_prog = arg+15;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (*(arg+1) != '-') {\n+\t\t\tconst char *a = arg+1;\n+\n+\t\t\twhile (*a) {\n+\t\t\t\tswitch (*a) {\n+\t\t\t\t\tcase 'A':\n+\t\t\t\t\t\tedarg++;\n+\t\t\t\t\t\topts.show_all = 1;\n+\t\t\t\t\t\topts.markers = 1;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\tcase 'e':\n+\t\t\t\t\t\tedarg++;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\tcase 'E':\n+\t\t\t\t\t\tedarg++;\n+\t\t\t\t\t\topts.markers = 1;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\tcase 'x':\n+\t\t\t\t\t\tedarg++;\n+\t\t\t\t\t\topts.overlap_only = 1;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\tcase 'X':\n+\t\t\t\t\t\tedarg++;\n+\t\t\t\t\t\topts.overlap_only = 1;\n+\t\t\t\t\t\topts.markers = 1;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\tcase '3':\n+\t\t\t\t\t\tedarg++;\n+\t\t\t\t\t\topts.unmerged_only = 1;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\tcase 'm':\n+\t\t\t\t\t\topts.merge = 1;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\tcase 'T':\n+\t\t\t\t\t\topts.initial_tab = 1;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\tdefault:\n+\t\t\t\t\t\terror(\"unknown option: %c\\n\", *a);\n+\t\t\t\t\t\tusage(builtin_diff3_usage);\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t\ta++;\n+\t\t\t}\n+\t\t\tcontinue;\n+\t\t}\n+\t\terror(\"unrecognised option: %s\\n\", arg);\n+\t\tusage(builtin_diff3_usage);\n+\t}\n+\n+\tif (edarg > 1)\n+\t\tdie(\"at most one of the AeExX3 options are allowed\");\n+\n+\t/* -AeExX3 without -m implies ed script */\n+\topts.edscript = edarg && !opts.merge;\n+\t/* -m without -AeExX3 implies -A */\n+\tif (opts.merge && !edarg) {\n+\t\topts.show_all = 1;\n+\t\topts.markers = 1;\n+\t}\n+\n+\tif (opts.edscript)\n+\t\tdie(\"ed scripts not yet supported!\");\n+\n+\tif (argc != i+3) {\n+\t\tif ( argc < i+3 )\n+\t\t\terror(\"missing file argument(s)\\n\");\n+\t\telse\n+\t\t\terror(\"too many arguments ('%s'...)\\n\", argv[i+3]);\n+\t\tusage(builtin_diff3_usage);\n+\t}\n+\n+\tfile = &argv[i];\n+\n+\tfor ( i = label_count; i < 3; i++ )\n+\t\tlabel_strings[i] = file[i];\n+\n+\tconflicts = diff3(stdout, file, label_strings, &opts);\n+\n+\treturn conflicts > 0;\n+}\n+\n+\ndiff --git a/builtin.h b/builtin.h\nindex 26ebcaf..a0e9ab7 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -12,6 +12,8 @@ extern void help_unknown_cmd(const char \n extern int cmd_help(int argc, const char **argv, const char *prefix);\n extern int cmd_version(int argc, const char **argv, const char *prefix);\n \n+extern int cmd_diff3(int argc, const char **argv, const char *prefix);\n+\n extern int cmd_whatchanged(int argc, const char **argv, const char *prefix);\n extern int cmd_show(int argc, const char **argv, const char *prefix);\n extern int cmd_log(int argc, const char **argv, const char *prefix);\ndiff --git a/git.c b/git.c\nindex 18ba14a..a76c7b6 100644\n--- a/git.c\n+++ b/git.c\n@@ -233,6 +233,7 @@ static void handle_internal_command(int \n \t\t{ \"format-patch\", cmd_format_patch, NEEDS_PREFIX },\n \t\t{ \"count-objects\", cmd_count_objects },\n \t\t{ \"diff\", cmd_diff, NEEDS_PREFIX },\n+\t\t{ \"diff3\", cmd_diff3 },\n \t\t{ \"grep\", cmd_grep, NEEDS_PREFIX },\n \t\t{ \"rm\", cmd_rm, NEEDS_PREFIX },\n \t\t{ \"add\", cmd_add, NEEDS_PREFIX },\ndiff --git a/t/txxxx-diff3.sh b/t/txxxx-diff3.sh\nnew file mode 100755\nindex 0000000..3b515e7\n--- /dev/null\n+++ b/t/txxxx-diff3.sh\n@@ -0,0 +1,175 @@\n+#!/bin/sh\n+\n+test_description='diff3 tests'\n+\n+. ./test-lib.sh\n+\n+###########################################################\n+# initialise counts\n+\n+diff3_count=0\n+diff3_fails=0\n+diff3_stats=0\n+total_count=0\n+total_fails=0\n+total_stats=0\n+\n+###########################################################\n+# test that \"git diff3\" and \"diff3\" give the same output\n+# and the same exit code for a given set of arguments.\n+\n+test_diff3 () {\n+\n+    diff3_count=$(expr $diff3_count + 1)\n+\n+    diff3 \"$@\" >out-diff3\n+    dret=\"$?\"\n+\n+    git diff3 \"$@\" >out-git\n+    gret=\"$?\"\n+\n+    diff out-diff3 out-git >out-diff 2>&1\n+\n+    if [ \"$?\" != 0 ]\n+    then\n+        diff3_fails=$(expr $diff3_fails + 1)\n+        echo \"*   FAIL: --- \" \"$@\" \" ---\"\n+    fi\n+    if [ \"$dret\" != \"$gret\" ]\n+    then\n+        diff3_stats=$(expr $diff3_stats + 1)\n+        echo \"*   STAT: ($dret != $gret) --- \" \"$@\" \" ---\"\n+    fi\n+\n+}\n+\n+###########################################################\n+# test that \"git diff3\" and \"diff3\" give the same output\n+# and the same exit code for several invocations of git\n+# with different external diff command lines. (ie \"normal\"\n+# diff and several unified diffs with context lines 0->5)\n+\n+test_diff3_extra () {\n+\n+    diff3 \"$@\" >out-diff3\n+    dret=\"$?\"\n+\n+    for dopt in \"\" \"-U0\" \"-U1\" \"-U2\" \"-u\" \"-U4\" \"-U5\"\n+    do\n+        diff3_count=$(expr $diff3_count + 1)\n+\n+        git diff3 --diff-program=\"diff $dopt\" \"$@\" >out-git\n+        gret=\"$?\"\n+\n+        diff out-diff3 out-git >out-diff 2>&1\n+\n+        if [ \"$?\" != 0 ]\n+        then\n+            diff3_fails=$(expr $diff3_fails + 1)\n+            echo \"*   FAIL: --- --diff-program='diff $dopt'\" \"$@\" \" ---\"\n+        fi\n+        if [ \"$dret\" != \"$gret\" ]\n+        then\n+            diff3_stats=$(expr $diff3_stats + 1)\n+            echo \"*   STAT: ($dret != $gret) --- --diff-program='diff $dopt'\" \"$@\" \" ---\"\n+        fi\n+    done\n+\n+}\n+\n+###########################################################\n+# given some options ($1) and three input files ($2->$4)\n+# test git diff3 on permutations of the input files.\n+\n+test_perm_files () {\n+    test_diff3 $1 $2 $3 $4\n+    test_diff3 $1 $4 $3 $2\n+    test_diff3 $1 $3 $2 $4\n+    test_diff3 $1 $4 $2 $3\n+    test_diff3 $1 $2 $4 $3\n+    test_diff3 $1 $3 $4 $2\n+}\n+\n+###########################################################\n+# given three input files ($1->$3) test git diff3 output\n+# ($opt == \"\") and all merge types for several permutaions\n+# of the input files.  also test the external diff support.\n+\n+test_files () {\n+\n+    diff3_count=0\n+    diff3_fails=0\n+    diff3_stats=0\n+\n+    for opt in \"\" \"-mA\" \"-me\" \"-mE\" \"-mx\" \"-mX\" \"-m3\"\n+    do\n+        test_perm_files $opt $1 $2 $3\n+    done\n+\n+    test_diff3_extra -mA -L our                  $1 $2 $3\n+    test_diff3_extra -mA -L our -L base          $1 $2 $3\n+    test_diff3_extra -mA -L our -L base -L their $1 $2 $3\n+\n+    total_count=$(expr $total_count + $diff3_count)\n+    total_fails=$(expr $total_fails + $diff3_fails)\n+    total_stats=$(expr $total_stats + $diff3_stats)\n+\n+    fails_and_stats=$(expr $diff3_fails + $diff3_stats)\n+\n+    case \"$fails_and_stats\" in\n+    0)\n+        return 0 ;;\n+    *)\n+        echo \"    tests: $diff3_count, fails: $diff3_fails, stats: $diff3_stats\"\n+        return 1 ;;\n+    esac\n+\n+}\n+\n+###########################################################\n+# ok so test some files.\n+\n+test_expect_success \\\n+    \"test files lao tzu tao\" \\\n+    'test_files ../txxxx/lao ../txxxx/tzu ../txxxx/tao'\n+\n+test_expect_success \\\n+    \"test files lao1 tzu tao1\" \\\n+    'test_files ../txxxx/lao1 ../txxxx/tzu ../txxxx/tao1'\n+\n+test_expect_success \\\n+    \"test files lao2 tzu tao2\" \\\n+    'test_files ../txxxx/lao2 ../txxxx/tzu ../txxxx/tao2'\n+\n+test_expect_success \\\n+    \"test files lao3 tzu tao3\" \\\n+    'test_files ../txxxx/lao3 ../txxxx/tzu ../txxxx/tao3'\n+\n+test_expect_success \\\n+    \"test files lao4 tzu tao4\" \\\n+    'test_files ../txxxx/lao4 ../txxxx/tzu ../txxxx/tao4'\n+\n+test_expect_success \\\n+    \"test files tzu tzu tzu\" \\\n+    'test_files ../txxxx/tzu ../txxxx/tzu ../txxxx/tzu'\n+\n+test_expect_success \\\n+    \"test files lao tzu tzu\" \\\n+    'test_files ../txxxx/lao ../txxxx/tzu ../txxxx/tzu'\n+\n+test_expect_success \\\n+    \"test files lao tzu /dev/null\" \\\n+    'test_files ../txxxx/lao ../txxxx/tzu /dev/null'\n+\n+test_expect_success \\\n+    \"test files /dev/null tzu /dev/null\" \\\n+    'test_files /dev/null ../txxxx/tzu /dev/null'\n+\n+###########################################################\n+# ok we are done.\n+\n+echo \"    tests: $total_count, fails: $total_fails, stats: $total_stats\"\n+\n+test_done\n+\n+\ndiff --git a/t/txxxx/lao b/t/txxxx/lao\nnew file mode 100644\nindex 0000000..635ef2c\n--- /dev/null\n+++ b/t/txxxx/lao\n@@ -0,0 +1,11 @@\n+The Way that can be told of is not the eternal Way;\n+The name that can be named is not the eternal name.\n+The Nameless is the origin of Heaven and Earth;\n+The Named is the mother of all things.\n+Therefore let there always be non-being,\n+  so we may see their subtlety,\n+And let there always be being,\n+  so we may see their outcome.\n+The two are the same,\n+But after they are produced,\n+  they have different names.\ndiff --git a/t/txxxx/lao1 b/t/txxxx/lao1\nnew file mode 100644\nindex 0000000..831654a\n--- /dev/null\n+++ b/t/txxxx/lao1\n@@ -0,0 +1,8 @@\n+The Nameless is the origin of Heaven and Earth;\n+\n+  so we may see their subtlety,\n+  so we may see their outcome.\n+The two are the same,\n+But after they are produced,\n+They both may be called deep and profound.\n+The door of all subtleties!\ndiff --git a/t/txxxx/lao2 b/t/txxxx/lao2\nnew file mode 100644\nindex 0000000..a7babdc\n--- /dev/null\n+++ b/t/txxxx/lao2\n@@ -0,0 +1,16 @@\n+The Nameless is the origin of Heaven and Earth;\n+home, away\n+The named is the mother of all things.\n+\n+Amy, Helen, Kym\n+Therefore let there always be non-being,\n+  so we may see their subtlety,\n+fred, bill, george\n+And let there always be being,\n+  so we may see their outcome.\n+The two are the same,\n+But after they are produced,\n+  they have different names.\n+They both may be called deep and profound.\n+Deeper and more profound,\n+The door of all subtleties!\ndiff --git a/t/txxxx/lao3 b/t/txxxx/lao3\nnew file mode 100644\nindex 0000000..ea500e5\n--- /dev/null\n+++ b/t/txxxx/lao3\n@@ -0,0 +1,13 @@\n+The Nameless is the origin of Heaven and Earth;\n+The named is the mother of ALL things.\n+\n+Therefore let there ALWAYS be non-being,\n+  so we may see their subtlety,\n+And let there ALWAYS be being,\n+  so we may see their outcome.\n+The two are the same,\n+But after they are produced,\n+  they have different names.\n+They both may be called deep and profound.\n+Deeper and more profound,\n+The door of all subtleties!\ndiff --git a/t/txxxx/lao4 b/t/txxxx/lao4\nnew file mode 100644\nindex 0000000..2ca7ddd\n--- /dev/null\n+++ b/t/txxxx/lao4\n@@ -0,0 +1,12 @@\n+The Way that can be told of is not the eternal Way;\n+The name that can be named is not the eternal name.\n+The Nameless is the origin of Heaven and Earth;\n+The Named is the mother of all things.\n+Therefore let there always be non-being,\n+  so we may see their subtlety,\n+And let there always be being,\n+  so we may see their outcome.\n+The two are the same,\n+But after they are produced,\n+  they have different names.\n+unfinished symphony\n\\ No newline at end of file\ndiff --git a/t/txxxx/tao b/t/txxxx/tao\nnew file mode 100644\nindex 0000000..ffe1ba3\n--- /dev/null\n+++ b/t/txxxx/tao\n@@ -0,0 +1,14 @@\n+The Way that can be told of is not the eternal Way;\n+The name that can be named is not the eternal name.\n+The Nameless is the origin of Heaven and Earth;\n+The named is the mother of all things.\n+\n+Therefore let there always be non-being,\n+  so we may see their subtlety,\n+And let there always be being,\n+  so we may see their result.\n+The two are the same,\n+But after they are produced,\n+  they have different names.\n+\n+  -- The Way of Lao-Tzu, tr. Wing-tsit Chan\ndiff --git a/t/txxxx/tao1 b/t/txxxx/tao1\nnew file mode 100644\nindex 0000000..7c0e98a\n--- /dev/null\n+++ b/t/txxxx/tao1\n@@ -0,0 +1,10 @@\n+The Nameless is the origin of Heaven and Earth;\n+The named is the mother of all things.\n+Therefore let there always be non-being,\n+And let there always be being,\n+The two are the same,\n+But after they are produced,\n+  they have different names.\n+They both may be called DEEP and profound.\n+Deeper and more profound,\n+The door of ALL subtleties!\ndiff --git a/t/txxxx/tao2 b/t/txxxx/tao2\nnew file mode 100644\nindex 0000000..033360b\n--- /dev/null\n+++ b/t/txxxx/tao2\n@@ -0,0 +1,16 @@\n+The Nameless is the origin of Heaven and Earth;\n+The named is the mother of all things.\n+mars, venus, neptune\n+\n+Therefore let there always be non-being,\n+quartz, diamond, ruby\n+  so we may see their subtlety,\n+And let there always be being,\n+lilly, rose, tulip\n+  so we may see their outcome.\n+The two are the same,\n+But after they are produced,\n+  they have different names.\n+They both may be called deep and profound.\n+Deeper and more profound,\n+The door of all subtleties!\ndiff --git a/t/txxxx/tao3 b/t/txxxx/tao3\nnew file mode 100644\nindex 0000000..0457551\n--- /dev/null\n+++ b/t/txxxx/tao3\n@@ -0,0 +1,13 @@\n+The Nameless is the origin of Heaven and Earth;\n+The named is the mother of all things.\n+THEIR\n+Therefore let there always be non-being,\n+  so we may see THEIR subtlety,\n+And let there always be being,\n+  so we may see THEIR outcome.\n+The two are the same,\n+But after they are produced,\n+  they have different names.\n+They both may be called deep and profound.\n+Deeper and more profound,\n+The door of all subtleties!\ndiff --git a/t/txxxx/tao4 b/t/txxxx/tao4\nnew file mode 100644\nindex 0000000..fbe30fd\n--- /dev/null\n+++ b/t/txxxx/tao4\n@@ -0,0 +1,15 @@\n+The Way that can be told of is not the eternal Way;\n+The name that can be named is not the eternal name.\n+The Nameless is the origin of Heaven and Earth;\n+The named is the mother of all things.\n+\n+Therefore let there always be non-being,\n+  so we may see their subtlety,\n+And let there always be being,\n+  so we may see their result.\n+The two are the same,\n+But after they are produced,\n+  they have different names.\n+\n+  -- The Way of Lao-Tzu, tr. Wing-tsit Chan\n+unchained melody\n\\ No newline at end of file\ndiff --git a/t/txxxx/tzu b/t/txxxx/tzu\nnew file mode 100644\nindex 0000000..5af88a8\n--- /dev/null\n+++ b/t/txxxx/tzu\n@@ -0,0 +1,13 @@\n+The Nameless is the origin of Heaven and Earth;\n+The named is the mother of all things.\n+\n+Therefore let there always be non-being,\n+  so we may see their subtlety,\n+And let there always be being,\n+  so we may see their outcome.\n+The two are the same,\n+But after they are produced,\n+  they have different names.\n+They both may be called deep and profound.\n+Deeper and more profound,\n+The door of all subtleties!\n-- \n1.4.2\n\n"},{"id":"297339","messageId":"Pine.LNX.4.64.0611221208430.27569@alien.or.mcafeemobile.com","threadId":"43116","inReplyTo":"Pine.LNX.4.63.0611212316080.26827@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: your mail","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-11-22T20:16:58Z","receivedAt":"2006-11-22T20:16:58Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Tue, 21 Nov 2006, Johannes Schindelin wrote:\n\n> [PATCH] xdiff: add xdl_merge()\n> \n> This new function implements the functionality of RCS merge, but\n> in-memory. It returns < 0 on error, otherwise the number of conflicts.\n> \n> Finding the conflicting lines can be a very expensive task. You can\n> control the eagerness of this algorithm:\n> \n> - a level value of 0 means that all overlapping changes are treated\n>   as conflicts,\n> - a value of 1 means that if the overlapping changes are identical,\n>   it is not treated as a conflict.\n> - If you set level to 2, overlapping changes will be analyzed, so that\n>   almost identical changes will not result in huge conflicts. Rather,\n>   only the conflicting lines will be shown inside conflict markers.\n> \n> With each increasing level, the algorithm gets slower, but more accurate.\n> Note that the code for level 2 depends on the simple definition of\n> mmfile_t specific to git, and therefore it will be harder to port that\n> to LibXDiff.\n\nJohannes, at the moment I'm chased by a huge storm of never ending emails, \nso I won't be able to follow up this one soon. A smart 3-way merge is in \nmy plans for LibXDiff though.\nThere is quite some nice code around, that does pretty smart tricks and \ngoes down to resolve sub-hunk non-trivial conflicts. You may want to take \na look at that code too.\n\n\n\n- Davide\n\n"}]}