Re: [PATCH] xdiff: add xdl_merge()

[Ramsay Jones <ramsay@ramsay1.demon.co.uk>]

[-- Attachment #1: Type: text/plain, Size: 3583 bytes --]

Hi Johannes,

Johannes Schindelin wrote:
> This new function implements the functionality of RCS merge, but
> in-memory. It returns < 0 on error, otherwise the number of conflicts.
> 

I had a similar idea (removing the RCS dependency) and, about two months
ago, implemented a git-diff3 that used the internal xdiff library.
Unfortunately, I then got distracted by other things and left this as a
WIP, without posting it to the list. [I had an email exchange with Junio
about it, but then dropped the ball - sorry Junio!]

> Finding the conflicting lines can be a very expensive task. You can
> control the eagerness of this algorithm:
> 
> - a level value of 0 means that all overlapping changes are treated
>   as conflicts,
> - a value of 1 means that if the overlapping changes are identical,
>   it is not treated as a conflict.
> - If you set level to 2, overlapping changes will be analyzed, so that
>   almost identical changes will not result in huge conflicts. Rather,
>   only the conflicting lines will be shown inside conflict markers.
> 
> With each increasing level, the algorithm gets slower, but more accurate.
> Note that the code for level 2 depends on the simple definition of
> mmfile_t specific to git, and therefore it will be harder to port that
> to LibXDiff.
> 

Erm, I guess I need to read the code! I haven't had an opportunity to
do that yet, but I hope to have time at the weekend.

> 	My hopes are that when I wake up in the morning, all bugs are
> 	fixed, git-merge-one-file is rewritten as a builtin,
> 	git-merge-index defaults to calling xdl_merge() directly when
> 	no program is passed with "-o", and git-merge-recursive also
> 	avoids fork()ing RCS' merge.

Yep, I had a similar todo list.

> 
> 	A funny side effect is that you can merge with white space
> 	corruption by setting the xpparam flags to ignore whitespace.
> 	The file passed as mf1 wins over mf2 in that case.

Yes, I had this on my todo list. In fact you can already try it out
by using --diff-program="diff -wb" (which uses the external diff).
[To be fair, you can also write an obvious script and use GNU diff3]

> 
>  Makefile       |    3 
>  xdiff/xdiff.h  |    7 +
>  xdiff/xdiffi.c |    3 
>  xdiff/xdiffi.h |    1 
>  xdiff/xmerge.c |  433 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  5 files changed, 444 insertions(+), 3 deletions(-)
> 

 From the above, I would guess that your code integrates well with the
xdiff library and, as a result, would be more memory efficient than my
code. I had considered doing this, but I wanted to support an external
diff option, so it was easier to implement the diff3 algorithm outside
the library, treating it just like an external diff (that I didn't need
to fork()/exec()). Also, I didn't need to understand the xdiff code, I
just treat it as a black box (and I'm lazy!).

[Having an external diff option was actually a debugging aid to ensure
that the main diff3 algorithm was implemented correctly. In the end I
didn't use it for debugging anyway!]

[snip patch]

I have attached a version of my patch, against v1.4.2, just for the
interested. Also it contains some tests which I found very helpful
in squashing bugs, so you might like to give them a try with your code.

Note: the fact that the patch is against v1.4.2 should not cause too
much of a problem, since it is mostly new files and the changes to
Makefile, builtin.h and git.c you could probably do in your sleep.

[Junio, this is almost exactly the same patch I sent you last time,
modulo some minor code clean-up/formatting]

All the best,

Ramsay



[-- Attachment #2: p0016.txt --]
[-- Type: text/plain, Size: 52987 bytes --]

>From f23d8df5d7774cb85b834357019c725cf8c1e231 Mon Sep 17 00:00:00 2001
From: Ramsay Jones <ramsay@ramsay1.demon.co.uk>
Date: Mon, 13 Nov 2006 23:04:37 +0000
Subject: [PATCH] Initial implementation of builtin diff3

The intention of this work is to remove the dependancy on
the rcs merge program. As a first step, we implement a
builtin clone of diff3. (A builtin merge replacement command
will be able to reuse this code, since merge is a thin
wrapper around diff3). So git-diff3 is only a stepping stone
to a merge replacement and is not meant to stay!

Signed-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk>
---
 Makefile         |    5 
 builtin-diff3.c  | 1824 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 builtin.h        |    2 
 git.c            |    1 
 t/txxxx-diff3.sh |  175 +++++
 t/txxxx/lao      |   11 
 t/txxxx/lao1     |    8 
 t/txxxx/lao2     |   16 
 t/txxxx/lao3     |   13 
 t/txxxx/lao4     |   12 
 t/txxxx/tao      |   14 
 t/txxxx/tao1     |   10 
 t/txxxx/tao2     |   16 
 t/txxxx/tao3     |   13 
 t/txxxx/tao4     |   15 
 t/txxxx/tzu      |   13 
 16 files changed, 2146 insertions(+), 2 deletions(-)

diff --git a/Makefile b/Makefile
index 0761d6c..60f5adc 100644
--- a/Makefile
+++ b/Makefile
@@ -198,7 +198,7 @@ BUILT_INS = git-log$X git-whatchanged$X 
 	git-apply$X git-show-branch$X git-diff-files$X git-update-index$X \
 	git-diff-index$X git-diff-stages$X git-diff-tree$X git-cat-file$X \
 	git-fmt-merge-msg$X git-prune$X git-mv$X git-prune-packed$X \
-	git-repo-config$X
+	git-repo-config$X git-diff3$X
 
 # what 'all' will build and 'install' will install, in gitexecdir
 ALL_PROGRAMS = $(PROGRAMS) $(SIMPLE_PROGRAMS) $(SCRIPTS)
@@ -255,7 +255,8 @@ BUILTIN_OBJS = \
 	builtin-diff-index.o builtin-diff-stages.o builtin-diff-tree.o \
 	builtin-cat-file.o builtin-mailsplit.o builtin-stripspace.o \
 	builtin-update-ref.o builtin-fmt-merge-msg.o builtin-prune.o \
-	builtin-mv.o builtin-prune-packed.o builtin-repo-config.o
+	builtin-mv.o builtin-prune-packed.o builtin-repo-config.o \
+	builtin-diff3.o
 
 GITLIBS = $(LIB_FILE) $(XDIFF_LIB)
 LIBS = $(GITLIBS) -lz
diff --git a/builtin-diff3.c b/builtin-diff3.c
new file mode 100644
index 0000000..9f5698f
--- /dev/null
+++ b/builtin-diff3.c
@@ -0,0 +1,1824 @@
+/*
+ * Builtin "git diff3"
+ *
+ */
+#include "cache.h"
+#include "builtin.h"
+#include "xdiff-interface.h"
+#include <sys/wait.h>
+#include <assert.h>
+
+
+#define MAX_DIFF_ARGS 32
+
+/* diff3 options */
+struct diff3_options {
+	unsigned show_all:1;     /* show all changes, including merged       */
+	unsigned overlap_only:1; /* restrict to overlapping changes          */
+	unsigned unmerged_only:1;/* restrict to unmerged non-overlapping     */
+	unsigned initial_tab:1;  /* output initial tab                       */
+	unsigned markers:1;      /* output conflict markers                  */
+	unsigned edscript:1;     /* output an ed script to perform the merge */
+	unsigned merge:1;        /* actually output the merged file          */
+	const char *diff_prog;   /* external diff program (command line)     */
+};
+
+/* input file info */
+struct finfo {
+	const char *name;   /* filename                       */
+	const char *label;  /* label to use for markers       */
+	int         num;    /* 0 = ours, 1 = base, 2 = theirs */
+	mmfile_t    mf;     /* file mmap() info               */
+};
+
+/* pipe info when running external diff */
+struct pinfo {
+	int   fd;   /* pipe read/write fd    */
+	pid_t pid;  /* child pid to wait for */
+};
+
+/* argv info for external diff */
+struct diff_argv {
+	char *args;         /* argument string memory */
+	const char **argv;  /* argument pointer array */
+	int argc;           /* argument count         */
+};
+
+/* callback info used with internal diff */
+struct ecb_info {
+	char *text;  /* pointer to text of diff output    */
+	long size;   /* size of memory block holding text */
+	long used;   /* length of diff output             */
+};
+
+/* type of diff */
+enum {
+	UNKNOWN_FORMAT,
+	NORMAL_FORMAT,
+	UNIFIED_FORMAT,
+	CONTEXT_FORMAT
+};
+
+/* normal format diff hunk header */
+struct hunk_header {
+	int fs, fe;  /* from-file start and end line numbers */
+	int type;    /* 'a' add, 'c' change, 'd' delete      */
+	int ts, te;  /* to-file start and end line numbers   */
+};
+
+/* unified format diff hunk header */
+struct unified_hunk_header {
+	int fs, fc;  /* from-file start line and count */
+	int ts, tc;  /* to-file start line and count   */
+};
+
+/* lines from one file referenced by a hunk */
+struct hunk_lines {
+	int  start;     /* start line number of hunk         */
+	int  end;       /* end line number of hunk           */
+	char **lines;   /* pointer to array of line pointers */
+	int  *lengths;  /* pointer to array of line lengths  */
+	int  size;      /* size of the above arrays          */
+};
+
+/* 2way diff hunk */
+struct diff2_hunk {
+	int               type;   /* hunk type: 'a', 'c', 'd'   */
+	struct hunk_lines from;   /* from-file hunk lines       */
+	struct hunk_lines to;     /* to-file hunk lines         */
+	struct diff2_hunk *next;  /* next hunk in list          */
+};
+
+/* 2way diff */
+struct diff2 {
+	struct finfo      *ff;      /* from file            */
+	struct finfo      *ft;      /* to file              */
+	mmbuffer_t        content;  /* text content of diff */
+	struct diff2_hunk *hunks;   /* list of diff hunks   */
+};
+
+/* a segment (sub-list) of diff2 hunks */
+struct segment {
+	int               from;   /* from-file number          */
+	int               to;     /* to-file number            */
+	struct diff2_hunk *head;  /* head of hunk list segment */
+	struct diff2_hunk *tail;  /* tail of hunk list segment */
+	int               count;  /* count of hunks            */
+};
+
+/* 3way diff hunk */
+struct diff3_hunk {
+	int               type;  /* 'a' all, '1' 1st, '2' 2nd, '3' 3rd */
+	struct hunk_lines f[3];  /* hunk lines for files 0, 1, 2       */
+	struct diff3_hunk *next; /* next hunk in list                  */
+};
+
+/* 3way diff */
+struct diff3 {
+	struct diff2      *diff01;  /* diff ours -> base   */
+	struct diff2      *diff21;  /* diff theirs -> base */
+	struct diff3_hunk *hunks;   /* list of diff3 hunks */
+};
+
+static void init_finfo(struct finfo *f, const char *name, const char *lab, int num)
+{
+	if (f) {
+		f->name  = name;
+		f->label = lab;
+		f->num   = num;
+
+		f->mf.ptr  = 0;
+		f->mf.size = 0;
+	}
+}
+
+static void alloc_line_arrays(int num, struct hunk_lines *h)
+{
+	assert(h);
+	h->lines   = xcalloc(num, sizeof(char *));
+	h->lengths = xcalloc(num, sizeof(int));
+	h->size    = num;
+}
+
+static struct diff2_hunk *new_diff2_hunk(void)
+{
+	struct diff2_hunk *new = xmalloc(sizeof(*new));
+
+	memset(new, 0, sizeof(*new));
+
+	return new;
+}
+
+static void free_diff2_hunk(struct diff2_hunk *p)
+{
+	if (p->from.lines)
+		free(p->from.lines);
+	if (p->from.lengths)
+		free(p->from.lengths);
+
+	if (p->to.lines)
+		free(p->to.lines);
+	if (p->to.lengths)
+		free(p->to.lengths);
+
+	free(p);
+}
+
+static struct diff2 *new_diff2(struct finfo *ff, struct finfo *ft)
+{
+	struct diff2 *new = xmalloc(sizeof(*new));
+
+	memset(new, 0, sizeof(*new));
+
+	new->ff = ff;
+	new->ft = ft;
+
+	return new;
+}
+
+static void free_diff2(struct diff2 *p)
+{
+	struct diff2_hunk *h, *next;
+
+	for (h = p->hunks; h; h = next) {
+		next = h->next;
+		free_diff2_hunk(h);
+	}
+
+	if (p->content.ptr)
+		free(p->content.ptr);
+
+	free(p);
+}
+
+static struct diff3_hunk *new_diff3_hunk(void)
+{
+	struct diff3_hunk *new = xmalloc(sizeof(*new));
+
+	memset(new, 0, sizeof(*new));
+
+	return new;
+}
+
+static void free_diff3_hunk(struct diff3_hunk *p)
+{
+	int i;
+
+	for (i = 0; i < 3; i++) {
+		if (p->f[i].lines)
+			free(p->f[i].lines);
+		if (p->f[i].lengths)
+			free(p->f[i].lengths);
+	}
+
+	free(p);
+}
+
+static struct diff3 *new_diff3(struct diff2 *diff01, struct diff2 *diff21)
+{
+	struct diff3 *new = xmalloc(sizeof(*new));
+
+	memset(new, 0, sizeof(*new));
+
+	new->diff01 = diff01;
+	new->diff21 = diff21;
+
+	return new;
+}
+
+static void free_diff3(struct diff3 *p)
+{
+	struct diff3_hunk *h, *next;
+
+	for (h = p->hunks; h; h = next) {
+		next = h->next;
+		free_diff3_hunk(h);
+	}
+
+	free_diff2(p->diff01);
+	free_diff2(p->diff21);
+
+	free(p);
+}
+
+static int init_mmfile(mmfile_t *mf, const char *file)
+{
+	char *data;
+	long size;
+	struct stat st;
+	int fd;
+
+	assert(mf && file && *file);
+
+	mf->ptr  = 0;
+	mf->size = 0;
+
+	if (lstat(file, &st) < 0)
+		return -1;
+	size = st.st_size;
+	if (!size) {
+		mf->ptr = "";
+		return 0;
+	}
+
+	fd = open(file, O_RDONLY);
+	if (fd < 0)
+		return -1;
+	data = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
+	close(fd);
+	if (data == MAP_FAILED)
+		return -1;
+
+	mf->ptr  = data;
+	mf->size = size;
+	return 0;
+}
+
+static void free_mmfile(mmfile_t *mf)
+{
+	if (mf) {
+		if (mf->ptr && mf->size != 0)
+			munmap(mf->ptr, mf->size);
+		mf->ptr  = 0;
+		mf->size = 0;
+	}
+}
+
+static void map_file(struct finfo *f)
+{
+	if (!f->mf.ptr && (init_mmfile(&f->mf, f->name) < 0))
+		die("can't read file '%s': %s", f->name, strerror(errno));
+}
+
+static int popenv(int argc, const char *argv[], const char *type, struct pinfo *p)
+{
+	int pfd[2];
+	pid_t pid;
+	int fd;
+
+	if (!argv || !type || !p) {
+		errno = EINVAL;
+		return -1;
+	}
+	p->fd = -1;
+	p->pid = 0;
+
+	if (!*type || (*type != 'r' && *type != 'w') || type[1] != 0) {
+		errno = EINVAL;
+		return -1;
+	}
+
+	if (pipe(pfd) < 0)
+		return -1;
+
+	if ((pid = fork()) < 0) {
+		return -1;
+	} else if (pid == 0) {  /* child */
+		if (*type == 'r') {
+			close(pfd[0]);
+			if(pfd[1] != STDOUT_FILENO) {
+				dup2(pfd[1], STDOUT_FILENO);
+				close(pfd[1]);
+			}
+		} else { /* *type == 'w' */
+			close(pfd[1]);
+			if(pfd[0] != STDIN_FILENO) {
+				dup2(pfd[0], STDIN_FILENO);
+				close(pfd[0]);
+			}
+
+		}
+
+#ifdef DUMMY
+		fd = open("/dev/null", O_RDWR);
+		dup2(fd, STDERR_FILENO);
+		close(fd);
+#endif
+
+		execvp(argv[0], (char *const *)argv);
+		_exit(127);
+	}
+
+	/* parent */
+	if (*type == 'r') {
+		close(pfd[1]);
+		fd = pfd[0];
+	} else {
+		close(pfd[0]);
+		fd = pfd[1];
+	}
+
+	p->fd = fd;
+	p->pid = pid;
+
+	return 0;
+}
+
+static int pclosev(struct pinfo *p)
+{
+	int stat;
+
+	if (!p || p->fd == -1 || p->pid == 0) {
+		errno = EINVAL;
+		return -1;
+	}
+
+	close(p->fd);  /* XXX check for close() failure? */
+	p->fd = -1;
+
+	while (waitpid(p->pid, &stat, 0) < 0)
+		if (errno != EINTR)
+			return -1;
+
+	p->pid = 0;
+
+	return stat;
+}
+
+static int split_cmdline(const char *cmdline, int max, struct diff_argv *prog)
+{
+	assert(prog);
+
+	if (cmdline && *cmdline && (prog->args = xmalloc(strlen(cmdline)+2))) {
+
+		const char *p = cmdline;
+		char *a = prog->args;
+		int argc = 0;
+
+		prog->argv = xmalloc(max * sizeof(char *));
+
+		while( *p ) {
+
+			while (*p == ' ' || *p == '\t')
+				p++;
+			if ( !*p )
+				break;
+
+			if (argc >= max)
+				break;
+
+			prog->argv[argc++] = a;
+			while ((*a = *p) && *a != ' ' && *a != '\t')
+				a++,p++;
+			*a++ = 0;
+
+		}
+
+		*a++ = 0;
+		prog->argc = argc;
+		prog->argv[argc] = 0;
+
+		if (argc == 0) {
+			free(prog->args);
+			free(prog->argv);
+			return -1;
+		}
+
+		return 0;
+	}
+
+	return -1;
+}
+
+static struct diff_argv *new_diff_argv(const char *cmdline)
+{
+	struct diff_argv *a = xmalloc(sizeof(*a));
+
+	memset(a, 0, sizeof(*a));
+
+	if (split_cmdline(cmdline, MAX_DIFF_ARGS, a) < 0) {
+		free(a);
+		return 0;
+	}
+
+	return a;
+}
+
+static void free_diff_argv(struct diff_argv *a)
+{
+	if (a) {
+		if (a->args)
+			free(a->args);
+		if (a->argv)
+			free(a->argv);
+		free(a);
+	}
+}
+
+static int read_from_pipe(int fd, mmbuffer_t *content)
+{
+	ssize_t n, size = 1024, total = 0;
+	char *text = xmalloc(size);
+
+	assert(content != 0);
+
+	while ((n = read(fd, text+total, size-total)) > 0) {
+		if (n == size-total) {
+			size *= 2;
+			text = xrealloc(text, size);
+		}
+		total += n;
+	}
+	if (n < 0)
+		return -1;
+
+	if (total == 0)
+		free(text);
+	else {
+		content->ptr  = text;
+		content->size = total;
+	}
+
+	return 0;
+}
+
+static void run_external_diff(struct diff_argv *prog, const char* file1, const char* file2, mmbuffer_t *content)
+{
+	char const **ap;
+	struct pinfo pi;
+	int stat, code;
+
+	if (!prog || !prog->args || !prog->argv || prog->argc < 1)
+		die("internal error: invalid diff argv");
+
+	if (prog->argc > MAX_DIFF_ARGS - 4)
+		die("too many arguments for external diff-program");
+
+	ap = &prog->argv[prog->argc];
+	*ap++ = "--";
+	*ap++ = file1;
+	*ap++ = file2;
+	*ap++ = 0;
+
+	if(popenv(prog->argc+4, prog->argv, "r", &pi) < 0)
+		die("popenv() failed: %s", strerror(errno));
+
+	if (read_from_pipe(pi.fd, content) < 0)
+		die("read_from_pipe() failed: %s", strerror(errno));
+
+	if ((stat = pclosev(&pi)) < 0)
+		die("pclosev() failed: %s", strerror(errno));
+
+	if (!WIFEXITED(stat))
+		die("diff-program '%s' terminated abnormally", prog->argv[0]);
+
+	if ((code = WEXITSTATUS(stat)) == 127)
+		die("can't execute external diff-program '%s'", prog->argv[0]);
+
+	if (code < 0 || code > 1)
+		die("external diff-program '%s' failed", prog->argv[0]);
+}
+
+#ifdef DUMMY
+static void print_buffer(mmbuffer_t *b)
+{
+	ssize_t count = 0, n;
+
+	if (b->size == 0)
+		return;
+
+	while ((n = xwrite(STDOUT_FILENO, b->ptr+count, b->size-count)) > 0)
+		count += n;
+}
+#endif
+
+static void external_diff(struct diff_argv *prog, struct finfo *ff, struct finfo *ft, mmbuffer_t *diff)
+{
+	assert(ff != 0 && ft != 0 && diff != 0);
+
+	run_external_diff(prog, ff->name, ft->name, diff);
+
+#ifdef DUMMY
+	printf("diff %s %s\n", ff->name, ft->name);
+	print_buffer(diff);
+	printf("--------\n");
+#endif
+}
+
+static int xdiff_output(void *priv_, mmbuffer_t *mb, int nbuf)
+{
+	struct ecb_info *b = priv_;
+	int i;
+
+	for (i = 0; i < nbuf; i++) {
+
+		if (b->used + mb[i].size > b->size) {
+			if (b->size > mb[i].size)
+				b->size *= 2;
+			else
+				b->size += mb[i].size;
+			b->text = xrealloc(b->text, b->size);
+		}
+
+		memcpy(b->text+b->used, mb[i].ptr, mb[i].size);
+		b->used += mb[i].size;
+
+	}
+	return 0;
+}
+
+static void run_internal_diff(mmfile_t *mf1, mmfile_t *mf2, mmbuffer_t *diff)
+{
+	xpparam_t xpp;
+	xdemitconf_t xecfg;
+	xdemitcb_t ecb;
+	struct ecb_info ecb_data;
+
+	ecb_data.text = xmalloc(1024);
+	ecb_data.size = 1024;
+	ecb_data.used = 0;
+
+	xpp.flags = XDF_NEED_MINIMAL;
+
+	xecfg.ctxlen = 0;
+	xecfg.flags  = 0;
+
+	ecb.outf = xdiff_output;
+	ecb.priv = &ecb_data;
+
+	xdl_diff(mf1, mf2, &xpp, &xecfg, &ecb);
+
+	if (ecb_data.used == 0)
+		free(ecb_data.text);
+	else {
+		diff->ptr  = ecb_data.text;
+		diff->size = ecb_data.used;
+	}
+}
+
+static void internal_diff(struct finfo *ff, struct finfo *ft, mmbuffer_t *diff)
+{
+	assert(ff != 0 && ft != 0 && diff != 0);
+
+	map_file(ff);
+	map_file(ft);
+
+	run_internal_diff(&ff->mf, &ft->mf, diff);
+
+#ifdef DUMMY
+	printf("diff %s %s\n", ff->name, ft->name);
+	print_buffer(diff);
+	printf("--------\n");
+#endif
+}
+
+
+static void read_diff(struct diff_argv *prog, struct finfo *ff, struct finfo *ft, mmbuffer_t *diff)
+{
+	if (prog)
+		external_diff(prog, ff, ft, diff);
+	else
+		internal_diff(ff, ft, diff);
+}
+
+static char *nextline(char *p, char *limit)
+{
+	while (p < limit)
+		if (*p++ == '\n')
+			return p;
+	return 0;
+}
+
+static int get_num(char **tp, int *np)
+{
+	char *p  = *tp;
+	int  neg = 0;
+	int  num = 0;
+
+	/* can't use: num = strtol(p, tp, 10); because strtol() will
+	 * skip using isspace() which includes '\n'.
+	 */
+
+	while (*p == ' ' || *p == '\t') p++;
+
+	if (*p == '-' || *p == '+') {
+		neg = *p == '-';
+		p++;
+	}
+
+	while (isdigit(*p))
+		num = num * 10 + (*p++ - '0');
+
+	if (*tp == p)
+		return 0;
+
+	*tp = p;
+	*np = (neg) ? -num : num;
+	return 1;
+}
+
+static int have(char **tp, char c)
+{
+	char *p = *tp;
+
+	while (*p == ' ' || *p == '\t') p++;
+
+	if (*p == c) {
+		*tp = ++p;
+		return 1;
+	}
+
+	return 0;
+}
+
+static int at_eol(char **tp)
+{
+	char *p = *tp;
+
+	while (*p == ' ' || *p == '\t') p++;
+	*tp = p;
+
+	if (*p == '\n')
+		return 1;
+
+	return 0;
+}
+
+static int normal_header(char **curp, struct hunk_header *header)
+{
+	char *p = *curp;
+
+	if (!get_num(&p, &header->fs))
+		return 0;
+
+	header->fe = header->fs;
+	if (have(&p, ',')) {
+		if(!get_num(&p, &header->fe))
+			return 0;
+	}
+
+	if (have(&p, 'a'))
+		header->type = 'a';
+	else if (have(&p, 'c'))
+		header->type = 'c';
+	else if (have(&p, 'd'))
+		header->type = 'd';
+	else
+		return 0;
+
+	if (header->type == 'a') {
+		assert(header->fs == header->fe);
+		header->fe--;  /* null (zero) range of lines */
+	}
+
+	if (!get_num(&p, &header->ts))
+		return 0;
+
+	header->te = header->ts;
+	if (have(&p, ',')) {
+		if(!get_num(&p, &header->te))
+			return 0;
+	}
+
+	if (header->type == 'd') {
+		assert(header->ts == header->te);
+		header->te--;  /* null (zero) range of lines */
+	}
+
+	if(!at_eol(&p))
+		return 0;
+
+	*curp = ++p;
+	return 1;
+}
+
+static int determine_diff_format(mmbuffer_t *content, char** curp)
+{
+	char *p     = content->ptr;
+	char *limit = p + content->size;
+	char *p2, *p3, *p4;
+	struct hunk_header head;
+
+	*curp = p;
+
+	if((p2 = nextline(p, limit)) == 0)
+		return UNKNOWN_FORMAT;
+
+	/* internal (unified) diff, no header */
+	if (memcmp(p, "@@ ", 3) == 0)
+		return UNIFIED_FORMAT;
+
+	/* normal format diff */
+	if (normal_header(&p, &head))
+		return NORMAL_FORMAT;
+
+	if((p3 = nextline(p2, limit)) == 0)
+		return UNKNOWN_FORMAT;
+
+	/* external (unified) diff, with header */
+	if (memcmp(p,  "--- ", 4) == 0 &&
+	    memcmp(p2, "+++ ", 4) == 0 &&
+	    memcmp(p3, "@@ ",  3) == 0) {
+
+		*curp = p3;
+		return UNIFIED_FORMAT;
+	}
+
+	/* context diff */
+	if (memcmp(p,  "*** ", 4) == 0 &&
+	    memcmp(p2, "--- ", 4) == 0 &&
+	    memcmp(p3, "****", 4) == 0) {
+
+		if((p4 = nextline(p3, limit)) == 0)
+			return UNKNOWN_FORMAT;
+
+		*curp = p4;
+		return CONTEXT_FORMAT;
+	}
+
+	return UNKNOWN_FORMAT;
+}
+
+static void get_line(char **curp, char *limit, char type, int num, struct hunk_lines *hl)
+{
+	char *p = *curp;
+	int  normal = (type == '<') || (type == '>');
+	char *pn;
+
+	assert(p < limit);
+
+	if (*p++ != type || (normal && *p++ != ' '))
+		die("invalid diff: leading line chars");
+
+	hl->lines[num] = p;
+
+	if ((pn = nextline(p, limit)) == 0)
+		die("invalid diff: missing eol #3");
+
+	hl->lengths[num] = (int)(pn - p);
+
+	/* check for "\ No newline at end of file" */
+	if (pn < limit && *pn == '\\') {
+		/* remove nl from length and skip */
+		hl->lengths[num] = (int)(pn - p) - 1;
+		pn = nextline(pn, limit);
+	}
+
+	*curp = pn;
+}
+
+static void process_normal_diff(struct diff2 *d, char *p)
+{
+	mmbuffer_t *content = &d->content;
+	char *limit = content->ptr + content->size;
+	struct diff2_hunk *hunk, **last_hunk;
+	int i;
+
+	last_hunk = &d->hunks;
+
+	while (p < limit) {
+		struct hunk_header head;
+
+		hunk = new_diff2_hunk();
+
+		/* hunk header: <int>[,<int>]<type><int>[,<int>] */
+		if (!normal_header(&p, &head))
+			die("invalid diff: header");
+
+		hunk->type = head.type;
+
+		/* from-file hunk lines (if any) */
+		hunk->from.start = head.fs;
+		hunk->from.end   = head.fe;
+		if (head.type != 'a') {
+			int numlines = head.fe - head.fs + 1;
+
+			assert(numlines > 0);
+
+			alloc_line_arrays(numlines, &hunk->from);
+
+			for (i = 0; i < numlines; i++)
+				get_line(&p, limit, '<', i, &hunk->from);
+		}
+
+		/* skip change hunk separator (if any) */
+		if (head.type == 'c') {
+			if (memcmp(p, "---\n", 4) != 0)
+				die("invalid diff: missing change separator");
+			p += 4;
+		}
+
+		/* to-file hunk lines (if any) */
+		hunk->to.start = head.ts;
+		hunk->to.end   = head.te;
+		if (head.type != 'd') {
+			int numlines = head.te - head.ts + 1;
+
+			assert(numlines > 0);
+
+			alloc_line_arrays(numlines, &hunk->to);
+
+			for (i = 0; i < numlines; i++)
+				get_line(&p, limit, '>', i, &hunk->to);
+		}
+
+		/* add this hunk to the end of the list */
+		*last_hunk = hunk;
+		last_hunk  = &hunk->next;
+
+	}
+
+	*last_hunk = 0;
+}
+
+static int have_str(char **tp, char *s)
+{
+	char *p = *tp;
+	int  len = strlen(s);
+
+	if (memcmp(p, s, len) == 0) {
+		p += len;
+		*tp = p;
+		return 1;
+	}
+
+	return 0;
+}
+
+static int unified_header(char **curp, struct unified_hunk_header *header)
+{
+	char *p = *curp;
+
+	if (!have_str(&p, "@@ -"))
+		return 0;
+
+	if (!get_num(&p, &header->fs))
+		return 0;
+
+	header->fc = 1;
+	if (have(&p, ',')) {
+		if(!get_num(&p, &header->fc))
+			return 0;
+	}
+
+	if (!have_str(&p, " +"))
+		return 0;
+
+	if (!get_num(&p, &header->ts))
+		return 0;
+
+	header->tc = 1;
+	if (have(&p, ',')) {
+		if(!get_num(&p, &header->tc))
+			return 0;
+	}
+
+	if (!have_str(&p, " @@"))
+		return 0;
+
+	if(!at_eol(&p))
+		return 0;
+
+	*curp = ++p;
+	return 1;
+}
+
+static int count_hunk_lines(char *p, char *limit, char type)
+{
+	int num = 0;
+
+	while (p < limit && *p == type) {
+		char *pn;
+
+		if ((pn = nextline(p, limit)) == 0)
+			die("invalid diff: missing eol #1");
+
+		num++;
+		p = pn;
+	}
+
+	return num;
+}
+
+static void process_unified_diff(struct diff2 *d, char *p)
+{
+	mmbuffer_t *content = &d->content;
+	char *limit = content->ptr + content->size;
+	struct diff2_hunk *hunk, **last_hunk;
+	int i;
+
+	last_hunk = &d->hunks;
+
+	while (p < limit) {
+		struct unified_hunk_header head;
+		int single_hunk = 0;
+
+		/* hunk header: @@ -<int>[,<int>] +<int>[,<int>] @@ */
+		if (!unified_header(&p, &head))
+			die("invalid diff: header");
+
+		single_hunk = (head.fc == 0 || head.tc == 0);
+
+		for (;;) {  /* for all hunks */
+			int cc = 0, fc = 0, tc = 0;
+
+			/* find begining of next hunk: skip common lines */
+			while (p < limit && *p == ' ') {
+				char *pn;
+
+				cc++;
+				head.fs++; head.fc--;
+				head.ts++; head.tc--;
+
+				if ((pn = nextline(p, limit)) == 0)
+					die("invalid diff: missing eol #2");
+				p = pn;
+			}
+
+			/* finished? */
+			if (limit <= p || *p == '@') {
+				assert(head.fc == 0 && head.tc == 0);
+				break;
+			}
+			if (*p != '-' && *p != '+')
+				die("invalid diff: missing -/+ lines");
+
+			hunk = new_diff2_hunk();
+
+			hunk->from.start = hunk->from.end = head.fs;
+			hunk->to.start   = hunk->to.end   = head.ts;
+
+			/* from-file hunk lines (if any) */
+			fc = count_hunk_lines(p, limit, '-');
+			if (fc > 0) {
+				alloc_line_arrays(fc, &hunk->from);
+
+				for (i = 0; i < fc; i++)
+					get_line(&p, limit, '-', i, &hunk->from);
+
+				hunk->from.end += fc-1;
+
+				head.fs += fc;
+				head.fc -= fc;
+			}
+
+			/* to-file hunk lines (if any) */
+			tc = count_hunk_lines(p, limit, '+');
+			if (tc > 0) {
+				alloc_line_arrays(tc, &hunk->to);
+
+				for (i = 0; i < tc; i++)
+					get_line(&p, limit, '+', i, &hunk->to);
+
+				hunk->to.end += tc-1;
+
+				head.ts += tc;
+				head.tc -= tc;
+			}
+
+			/* set hunk type */
+			assert(fc > 0 || tc > 0);
+			if (fc == 0) {
+				hunk->type = 'a';
+				if (!single_hunk)
+					hunk->from.start--;
+				hunk->from.end = hunk->from.start - 1;
+			} else if (tc == 0) {
+				hunk->type = 'd';
+				if (!single_hunk)
+					hunk->to.start--;
+				hunk->to.end = hunk->to.start - 1;
+			} else {
+				hunk->type = 'c';
+			}
+
+			/* add this hunk to the end of the list */
+			*last_hunk = hunk;
+			last_hunk  = &hunk->next;
+		}
+
+	}
+
+	*last_hunk = 0;
+
+}
+
+struct diff2* process_diff(struct diff_argv *prog, struct finfo *ff, struct finfo *ft)
+{
+	struct diff2 *result = new_diff2(ff, ft);
+	char *scan;
+
+	read_diff(prog, ff, ft, &result->content);
+
+	if (result->content.size == 0)
+		return result;  /* empty diff is ok */
+
+	assert(result->content.size > 0);
+
+	if (result->content.ptr[result->content.size-1] != '\n')
+		die("invalid diff: missing eol on last line");
+
+	switch (determine_diff_format(&result->content, &scan)) {
+		case NORMAL_FORMAT:
+			process_normal_diff(result, scan);
+			break;
+		case UNIFIED_FORMAT:
+			process_unified_diff(result, scan);
+			break;
+		case CONTEXT_FORMAT:
+			die("context diff format not supported");
+			break;
+		case UNKNOWN_FORMAT:
+		default:
+			die("unknown diff format");
+			break;
+	}
+
+	return result;
+}
+
+static void adjust_diff2(struct diff2 *d)
+{
+	struct diff2_hunk *p;
+
+	for (p = d->hunks; p; p = p->next) {
+		if (p->type == 'a') {
+			p->from.start++;
+			p->from.end++;
+		} else if (p->type == 'd') {
+			p->to.start++;
+			p->to.end++;
+		}
+	}
+}
+
+static int copy_lines(struct hunk_lines *dst, int off, struct hunk_lines *src)
+{
+	char **s = src->lines;
+	int  *sl = src->lengths;
+	char **d = dst->lines + off;
+	int  *dl = dst->lengths + off;
+	int  n   = src->size;
+
+	assert(n <= dst->size - off);
+
+	while(n--) {
+		if (*d) {
+			if (*sl != *dl || memcmp(*s, *d, *sl)) {
+				return 0;
+			}
+		} else {
+			*d  = *s;
+			*dl = *sl;
+		}
+		d++; dl++;
+		s++; sl++;
+	}
+	return 1;
+}
+
+static int equal_lines(struct hunk_lines *lhs, struct hunk_lines *rhs)
+{
+	char **l = lhs->lines;
+	int  *ll = lhs->lengths;
+	char **r = rhs->lines;
+	int  *rl = rhs->lengths;
+	int  n   = lhs->size;
+
+	if (n != rhs->size)
+		return 0;
+
+	while (n--) {
+		if (!*l || !*r || *ll != *rl || memcmp(*l, *r, *ll))
+			return 0;
+		l++; ll++;
+		r++; rl++;
+	}
+	return 1;
+}
+
+static int get_low_thread(struct diff2_hunk *p[2])
+{
+	if (!p[0])
+		return 1;
+	if (!p[1])
+		return 0;
+	return (p[0]->to.start > p[1]->to.start) ? 1 : 0;
+}
+
+static void init_segment(struct segment *s, int from, int to)
+{
+	s->from  = from;
+	s->to    = to;
+	s->head  = 0;
+	s->tail  = 0;
+	s->count = 0;
+}
+
+static void add_segment(struct segment *s, struct diff2_hunk *d)
+{
+	assert(d != 0);
+
+	if (!s->head)
+		s->head = s->tail = d;
+	else
+		s->tail = d;
+	s->count++;
+}
+
+static struct diff3_hunk *make_diff3_hunk(struct segment use[2],
+		int low_thread, int high_thread, struct diff3_hunk *last)
+{
+	struct diff3_hunk *result = new_diff3_hunk();
+	int startc, endc;
+	int i, common;
+	int from0, from1;
+
+	assert(use[0].to == use[1].to);
+	assert(use[0].from != use[1].from);
+
+	from0 = use[0].from;
+	from1 = use[1].from;
+
+	common = use[0].to;
+	assert(common >= 0 && common <= 2);
+
+	/* find start/end line numbers from the common file */
+	startc = result->f[common].start = use[low_thread].head->to.start;
+	endc   = result->f[common].end   = use[high_thread].tail->to.end;
+
+	/* find start/end line numbers for other files */
+	for (i = 0; i < 2; i++) {
+		struct segment *s = &use[i];
+		struct diff2_hunk *h = s->head;
+		struct diff2_hunk *t = s->tail;
+		int file = s->from;
+		int start = startc, end = endc;
+
+		assert(file >= 0 && file <= 2);
+
+		if (h) {
+			start = startc - h->to.start + h->from.start;
+			end   = endc   - t->to.end   + t->from.end;
+		} else if (last) {
+			int d = last->f[file].end - last->f[common].end;
+			start = startc + d;
+			end   = endc   + d;
+		}
+		result->f[file].start = start;
+		result->f[file].end   = end;
+	}
+
+	/* allocate hunk_lines line pointer and lengths arrays */
+	for (i = 0; i < 3; i++) {
+		int numlines = result->f[i].end - result->f[i].start + 1;
+
+		if (numlines > 0)
+			alloc_line_arrays(numlines, &result->f[i]);
+	}
+
+	/* copy line info for common file */
+	for (i = 0; i < 2; i++) {
+		struct segment *s = &use[i];
+		struct diff2_hunk *h = s->head;
+		int j;
+
+		for (j = 0; j < s->count; j++,h = h->next) {
+			int offset = h->to.start - startc;
+
+			if (!copy_lines(&result->f[common], offset, &h->to))
+				die("internal error: copy_lines()");
+
+		}
+	}
+
+	/* copy line info for other files */
+	for (i = 0; i < 2; i++) {
+		struct segment *s = &use[i];
+		struct diff2_hunk *h = s->head;
+		struct hunk_lines *tf, *cf;
+		int start, end, file = s->from;
+		int j, k, l, m;
+
+		assert(file >= 0 && file <= 2);
+
+		tf = &result->f[file];
+		cf = &result->f[common];
+
+		start = tf->start;
+		end   = tf->end;
+
+		/* before first hunk */
+		k = (h) ? h->from.start : end+1;
+		for (j = 0; j + start < k; j++) {
+			tf->lines[j]   = cf->lines[j];
+			tf->lengths[j] = cf->lengths[j];
+		}
+
+		/* hunk list */
+		for (j = 0; j < s->count; j++,h = h->next) {
+			int offset = h->from.start - start;
+
+			if (!copy_lines(&result->f[file], offset, &h->from))
+				die("internal error:");
+
+			/* between this and next hunk */
+			l = h->to.end + 1 - startc;
+			if (j < s->count-1)
+				k = h->next->from.start - start;
+			else
+				k = end+1 - start;
+			for (m = h->from.end + 1 - start; m < k; m++,l++) {
+				tf->lines[m]   = cf->lines[l];
+				tf->lengths[m] = cf->lengths[l];
+			}
+
+		}
+
+	}
+
+	/* set diff3 hunk type */
+	if (!use[0].head)
+		result->type = '0' + from1;
+	else if (!use[1].head)
+		result->type = '0' + from0;
+	else {
+		if (equal_lines(&result->f[from0], &result->f[from1]))
+			result->type = '0' + common;
+		else
+			result->type = 'a';
+	}
+
+	return result;
+}
+
+static struct diff3 *make_3way_diff(struct diff2 *d01, struct diff2 *d21)
+{
+	struct diff3 *result = new_diff3(d01, d21);
+	struct diff2_hunk *diff01 = d01->hunks;
+	struct diff2_hunk *diff21 = d21->hunks;
+	struct diff2_hunk *p[2], *high_diff, *other_diff;
+	struct diff3_hunk *hunk, **last_hunk;
+	struct diff3_hunk *last;
+	struct segment use[2];
+	int low_thread, high_thread;
+	int other_thread, high_line;
+
+	assert(d01->ft->num == d21->ft->num);
+	assert(d01->ff->num != d21->ff->num);
+
+	adjust_diff2(d01);
+	adjust_diff2(d21);
+
+	last_hunk = &result->hunks;
+	last = 0;
+	p[0] = diff01;
+	p[1] = diff21;
+
+	while (p[0] || p[1]) {
+		init_segment(&use[0], d01->ff->num, d01->ft->num);
+		init_segment(&use[1], d21->ff->num, d21->ft->num);
+
+		high_thread = low_thread = get_low_thread(p);
+
+		high_diff = p[high_thread];
+		high_line = high_diff->to.end;
+
+		add_segment(&use[high_thread], high_diff);
+		p[high_thread] = high_diff->next;
+
+		other_thread = high_thread ^ 0x1;
+		other_diff   = p[other_thread];
+
+		while (other_diff && other_diff->to.start <= high_line+1) {
+
+			add_segment(&use[other_thread], other_diff);
+			p[other_thread] = p[other_thread]->next;
+
+			if (high_line < other_diff->to.end) {
+				high_thread ^= 0x1;
+				high_diff = other_diff;
+				high_line = other_diff->to.end;
+			}
+
+			other_thread = high_thread ^ 0x1;
+			other_diff   = p[other_thread];
+		}
+
+		hunk = make_diff3_hunk(use, low_thread, high_thread, last);
+
+		if (!hunk)
+			die("can't create diff3 hunk");
+
+		/* add this hunk to the end of the list */
+		*last_hunk = hunk;
+		last_hunk  = &hunk->next;
+
+		last = hunk;
+	}
+
+	*last_hunk = 0;
+
+	return result;
+}
+
+#ifdef DUMMY
+static void print_diff2_hunk(struct diff2_hunk *p)
+{
+	struct hunk_lines *f = &p->from;
+	struct hunk_lines *t = &p->to;
+	int i, type = p->type;
+
+	printf("%d,%d %c %d,%d\n", f->start, f->end, type, t->start, t->end);
+
+	for (i = 0; i < f->size; i++)
+		printf("< %.*s", f->lengths[i], f->lines[i]);
+
+	printf("---\n");
+
+	for (i = 0; i < t->size; i++)
+		printf("> %.*s", t->lengths[i], t->lines[i]);
+
+	printf("+++\n");
+}
+
+static void print_diff2(struct diff2 *d)
+{
+	struct diff2_hunk *p;
+
+	printf("<--- diff2 --->\n");
+	for (p = d->hunks; p; p = p->next)
+		print_diff2_hunk(p);
+	printf(">=============<\n");
+}
+#endif
+
+static void print_diff3_hunk(FILE *outf, struct diff3_hunk *p, char *prefix)
+{
+	int i, j, k, skip_print;
+
+	if (p->type == 'a')
+		fprintf(outf, "====\n");
+	else
+		fprintf(outf, "====%c\n", p->type+1);
+
+	switch (p->type) {
+		case '0': skip_print = 1; break;
+		case '1': skip_print = 0; break;
+		case '2': skip_print = 0; break;
+		case 'a': skip_print = 3; break;
+		default:
+			die("internal error: invalid diff3 hunk type");
+			break;
+	}
+
+	for (j = 0,k = 0; j < 3; j++,k++) {
+		int  numlines, start, end, len;
+		char *s;
+
+		if (p->type == '1' && j > 0)
+			k = (j == 1) ? 2 : 1;
+
+		start = p->f[k].start;
+		end   = p->f[k].end;
+
+		numlines = end - start + 1;
+
+		if (numlines == 0)
+			fprintf(outf, "%d:%da\n", k+1, start-1);
+		else if (numlines == 1)
+			fprintf(outf, "%d:%dc\n", k+1, start);
+		else
+			fprintf(outf, "%d:%d,%dc\n", k+1, start, end);
+
+		if (k == skip_print)
+			continue;
+
+		assert(numlines == p->f[k].size);
+
+		if (p->f[k].size <= 0)
+			continue;
+
+		s   = 0;
+		len = 0;
+
+		for (i = 0; i < p->f[k].size; i++) {
+			s = p->f[k].lines[i];
+			len = p->f[k].lengths[i];
+			fprintf(outf, "%s", prefix);
+			fwrite(s, 1, len, outf);
+		}
+
+		if (s && (len == 0 || s[len-1] != '\n'))
+			fprintf(outf, "\n\\ No newline at end of file\n");
+
+	}
+
+}
+
+static void print_diff3(FILE *outf, struct diff3 *d, struct diff3_options *o)
+{
+	struct diff3_hunk *p;
+	char *prefix = (o->initial_tab) ? "\t" : "  ";
+
+	for (p = d->hunks; p; p = p->next)
+		print_diff3_hunk(outf, p, prefix);
+}
+
+static int write_lines(FILE *outf, char **curp, char *limit, int num)
+{
+	char *p = *curp;
+	char *pn;
+	int  size;
+
+	assert(num >= 0);
+
+	while (num--) {
+		if ((pn = nextline(p, limit)) == 0) {
+			if (num > 0)
+				return -1;
+			pn = limit;
+		}
+		p = pn;
+	}
+	size = (int)(p - *curp);
+	if (size > 0)
+		fwrite(*curp, 1, size, outf);
+	*curp = p;
+	return 0;
+}
+
+static int skip_lines(char **curp, char *limit, int num)
+{
+	char *p = *curp;
+	char *pn;
+
+	assert(num >= 0);
+
+	while (num--) {
+		if ((pn = nextline(p, limit)) == 0) {
+			if (num > 0)
+				return -1;
+			pn = limit;
+		}
+		p = pn;
+	}
+	*curp = p;
+	return 0;
+}
+
+static int diff3_merge(FILE *outf, mmfile_t *inf, struct diff3 *d, struct finfo f[3], struct diff3_options *opts)
+{
+	struct diff3_hunk *p;
+	int conflicts = 0;
+	int inf_lines = 0;
+	char *infp, *inf_limit;
+
+	infp = inf->ptr;
+	inf_limit = infp + inf->size;
+
+	for (p = d->hunks; p; p = p->next) {
+		int conflict = 0;
+		int i, lines;
+
+		/* check if we can skip this block */
+		switch (p->type) {
+			default:
+			case '0': /* change unique to our file: skip */
+				continue;
+				break;
+			case '1': /* same in ours and theirs: merged change */
+				if (!opts->show_all)
+					continue;
+				conflict = 1;
+				break;
+			case '2': /* change only in theirs: un-merged change */
+				if (opts->overlap_only)
+					continue;
+				break;
+			case 'a': /* all files differ: overlapping change */
+				if (opts->unmerged_only)
+					continue;
+				conflict = opts->markers;
+				break;
+		}
+
+		/* write lines from '0' (our) file (if any) */
+		lines = p->f[0].start - inf_lines - 1;
+		if (lines > 0) {
+			if (write_lines(outf, &infp, inf_limit, lines) < 0)
+				die("unexpected eof on file");
+			inf_lines += lines;
+		}
+
+		if (conflict) {
+			/* write lines from files with conflict markers */
+			char *marker_fmt = "<<<<<<< %s\n";
+
+			conflicts++;
+
+			if (p->type == 'a') {
+				/* write lines from '0' (our) file */
+				fprintf(outf, marker_fmt, f[0].label);
+				for (i = 0; i < p->f[0].size; i++) {
+					char *s = p->f[0].lines[i];
+					int len = p->f[0].lengths[i];
+					fwrite(s, 1, len, outf);
+				}
+				marker_fmt = "||||||| %s\n";
+			}
+
+			if (opts->show_all) {
+				/* write lines from '1' (base) file */
+				fprintf(outf, marker_fmt, f[1].label);
+				for (i = 0; i < p->f[1].size; i++) {
+					char *s = p->f[1].lines[i];
+					int len = p->f[1].lengths[i];
+					fwrite(s, 1, len, outf);
+				}
+			}
+
+			fprintf(outf, "=======\n");
+
+		}
+
+		/* write lines from '2' (their) file */
+		for (i = 0; i < p->f[2].size; i++) {
+			char *s = p->f[2].lines[i];
+			int len = p->f[2].lengths[i];
+			fwrite(s, 1, len, outf);
+		}
+
+		/* add conflict marker */
+		if (conflict)
+			fprintf(outf, ">>>>>>> %s\n", f[2].label);
+
+		/* skip lines from '0' (our) file */
+		lines = p->f[0].size;
+		if (lines > 0) {
+			if (skip_lines(&infp, inf_limit, lines) < 0)
+				die("unexpected eof");
+			inf_lines += lines;
+		}
+
+	}
+
+	/* write remainder of '0' (our) file */
+	if (infp < inf_limit)
+		fwrite(infp, 1, (int)(inf_limit - infp), outf);
+
+	return conflicts;
+}
+
+int diff3(FILE *outf, const char *file[3], const char *label[3], struct diff3_options *opts)
+{
+	int i;
+	struct finfo f[3];
+	struct diff2 *d1, *d2;
+	struct diff3 *d3;
+	struct diff_argv *prog = 0;
+	int conflicts = 0;
+
+	for ( i = 0; i < 3; i++ )
+		init_finfo(&f[i], file[i], label[i], i);
+
+	if (opts->diff_prog)
+		prog = new_diff_argv(opts->diff_prog);
+
+	d2 = process_diff(prog, &f[2], &f[1]);
+	free_mmfile(&f[2].mf);
+
+	d1 = process_diff(prog, &f[0], &f[1]);
+	free_mmfile(&f[1].mf);
+
+	d3 = make_3way_diff(d1, d2);
+
+	if (opts->merge) {
+		map_file(&f[0]);
+		conflicts = diff3_merge(outf, &f[0].mf, d3, f, opts);
+	} else {
+		print_diff3(outf, d3, opts);
+	}
+
+	free_mmfile(&f[0].mf);
+	free_diff3(d3);  /* also free()'s d1 and d2 */
+	free_diff_argv(prog);
+
+	return conflicts;
+}
+
+
+static const char builtin_diff3_usage[] =
+"git-diff3 [options]... ours base theirs\n"
+"\n"
+"  -e  --ed            output unmerged changes from BASE to THEIRS into OURS\n"
+"  -E  --show-overlap  output unmerged changes, bracketing conflicts\n"
+"  -A  --show-all      output all changes, bracketing conflicts\n"
+"  -x  --overlap-only  output overlapping changes\n"
+"  -X                  output overlapping changes, bracketing them\n"
+"  -3  --easy-only     output unmerged non-overlapping changes\n"
+"\n"
+"  -m  --merge         output merged file instead of ed script\n"
+"  -T  --initial-tab   make tabs line up by prepending a tab\n"
+"\n"
+"  -L LABEL  --label=LABEL  use LABEL instead of filename\n"
+"  --diff-program=PROGRAM   use PROGRAM to compare files\n"
+;
+
+
+int cmd_diff3(int argc, const char **argv, const char *prefix)
+{
+	int i;
+	const char *label_strings[3];
+	int label_count = 0;
+	int conflicts = 0;
+	int edarg = 0;
+	const char **file;
+	struct diff3_options opts;
+
+	memset(&opts, 0, sizeof(opts));
+
+	for (i = 1 ; i < argc ; i++) {
+		const char *arg = argv[i];
+
+		if (*arg != '-')
+			break;
+		if (!strcmp(arg, "--")) {
+			i++;
+			break;
+		}
+		if (!strcmp(arg, "-e") || !strcmp(arg, "--ed")) {
+			edarg++;
+			continue;
+		}
+		if (!strcmp(arg, "-E") || !strcmp(arg, "--show-overlap")) {
+			edarg++;
+			opts.markers = 1;
+			continue;
+		}
+		if (!strcmp(arg, "-A") || !strcmp(arg, "--show-all")) {
+			edarg++;
+			opts.show_all = 1;
+			opts.markers = 1;
+			continue;
+		}
+		if (!strcmp(arg, "-x") || !strcmp(arg, "--overlap-only")) {
+			edarg++;
+			opts.overlap_only = 1;
+			continue;
+		}
+		if (!strcmp(arg, "-X")) {
+			edarg++;
+			opts.overlap_only = 1;
+			opts.markers = 1;
+			continue;
+		}
+		if (!strcmp(arg, "-3") || !strcmp(arg, "--easy-only")) {
+			edarg++;
+			opts.unmerged_only = 1;
+			continue;
+		}
+		if (!strcmp(arg, "-m") || !strcmp(arg, "--merge")) {
+			opts.merge = 1;
+			continue;
+		}
+		if (!strcmp(arg, "-T") || !strcmp(arg, "--initial-tab")) {
+			opts.initial_tab = 1;
+			continue;
+		}
+		if (!strcmp(arg, "-L")) {
+			if ( argc <= i+1 )
+				die("-L needs a LABEL argument");
+			if ( label_count < 3 )
+				label_strings[label_count++] = argv[++i];
+			else
+				die("too many labels options specified");
+			continue;
+		}
+		if (!strncmp(arg, "--label=", 8)) {
+			if ( !*(arg+8) )
+				die("--label needs a LABEL argument");
+			if ( label_count < 3 )
+				label_strings[label_count++] = arg+8;
+			else
+				die("too many labels options specified");
+			continue;
+		}
+		if (!strncmp(arg, "--diff-program=", 15)) {
+			if ( !*(arg+15) )
+				die("--diff-program needs a PROGRAM argument");
+			opts.diff_prog = arg+15;
+			continue;
+		}
+		if (*(arg+1) != '-') {
+			const char *a = arg+1;
+
+			while (*a) {
+				switch (*a) {
+					case 'A':
+						edarg++;
+						opts.show_all = 1;
+						opts.markers = 1;
+						break;
+					case 'e':
+						edarg++;
+						break;
+					case 'E':
+						edarg++;
+						opts.markers = 1;
+						break;
+					case 'x':
+						edarg++;
+						opts.overlap_only = 1;
+						break;
+					case 'X':
+						edarg++;
+						opts.overlap_only = 1;
+						opts.markers = 1;
+						break;
+					case '3':
+						edarg++;
+						opts.unmerged_only = 1;
+						break;
+					case 'm':
+						opts.merge = 1;
+						break;
+					case 'T':
+						opts.initial_tab = 1;
+						break;
+					default:
+						error("unknown option: %c\n", *a);
+						usage(builtin_diff3_usage);
+						break;
+				}
+				a++;
+			}
+			continue;
+		}
+		error("unrecognised option: %s\n", arg);
+		usage(builtin_diff3_usage);
+	}
+
+	if (edarg > 1)
+		die("at most one of the AeExX3 options are allowed");
+
+	/* -AeExX3 without -m implies ed script */
+	opts.edscript = edarg && !opts.merge;
+	/* -m without -AeExX3 implies -A */
+	if (opts.merge && !edarg) {
+		opts.show_all = 1;
+		opts.markers = 1;
+	}
+
+	if (opts.edscript)
+		die("ed scripts not yet supported!");
+
+	if (argc != i+3) {
+		if ( argc < i+3 )
+			error("missing file argument(s)\n");
+		else
+			error("too many arguments ('%s'...)\n", argv[i+3]);
+		usage(builtin_diff3_usage);
+	}
+
+	file = &argv[i];
+
+	for ( i = label_count; i < 3; i++ )
+		label_strings[i] = file[i];
+
+	conflicts = diff3(stdout, file, label_strings, &opts);
+
+	return conflicts > 0;
+}
+
+
diff --git a/builtin.h b/builtin.h
index 26ebcaf..a0e9ab7 100644
--- a/builtin.h
+++ b/builtin.h
@@ -12,6 +12,8 @@ extern void help_unknown_cmd(const char 
 extern int cmd_help(int argc, const char **argv, const char *prefix);
 extern int cmd_version(int argc, const char **argv, const char *prefix);
 
+extern int cmd_diff3(int argc, const char **argv, const char *prefix);
+
 extern int cmd_whatchanged(int argc, const char **argv, const char *prefix);
 extern int cmd_show(int argc, const char **argv, const char *prefix);
 extern int cmd_log(int argc, const char **argv, const char *prefix);
diff --git a/git.c b/git.c
index 18ba14a..a76c7b6 100644
--- a/git.c
+++ b/git.c
@@ -233,6 +233,7 @@ static void handle_internal_command(int 
 		{ "format-patch", cmd_format_patch, NEEDS_PREFIX },
 		{ "count-objects", cmd_count_objects },
 		{ "diff", cmd_diff, NEEDS_PREFIX },
+		{ "diff3", cmd_diff3 },
 		{ "grep", cmd_grep, NEEDS_PREFIX },
 		{ "rm", cmd_rm, NEEDS_PREFIX },
 		{ "add", cmd_add, NEEDS_PREFIX },
diff --git a/t/txxxx-diff3.sh b/t/txxxx-diff3.sh
new file mode 100755
index 0000000..3b515e7
--- /dev/null
+++ b/t/txxxx-diff3.sh
@@ -0,0 +1,175 @@
+#!/bin/sh
+
+test_description='diff3 tests'
+
+. ./test-lib.sh
+
+###########################################################
+# initialise counts
+
+diff3_count=0
+diff3_fails=0
+diff3_stats=0
+total_count=0
+total_fails=0
+total_stats=0
+
+###########################################################
+# test that "git diff3" and "diff3" give the same output
+# and the same exit code for a given set of arguments.
+
+test_diff3 () {
+
+    diff3_count=$(expr $diff3_count + 1)
+
+    diff3 "$@" >out-diff3
+    dret="$?"
+
+    git diff3 "$@" >out-git
+    gret="$?"
+
+    diff out-diff3 out-git >out-diff 2>&1
+
+    if [ "$?" != 0 ]
+    then
+        diff3_fails=$(expr $diff3_fails + 1)
+        echo "*   FAIL: --- " "$@" " ---"
+    fi
+    if [ "$dret" != "$gret" ]
+    then
+        diff3_stats=$(expr $diff3_stats + 1)
+        echo "*   STAT: ($dret != $gret) --- " "$@" " ---"
+    fi
+
+}
+
+###########################################################
+# test that "git diff3" and "diff3" give the same output
+# and the same exit code for several invocations of git
+# with different external diff command lines. (ie "normal"
+# diff and several unified diffs with context lines 0->5)
+
+test_diff3_extra () {
+
+    diff3 "$@" >out-diff3
+    dret="$?"
+
+    for dopt in "" "-U0" "-U1" "-U2" "-u" "-U4" "-U5"
+    do
+        diff3_count=$(expr $diff3_count + 1)
+
+        git diff3 --diff-program="diff $dopt" "$@" >out-git
+        gret="$?"
+
+        diff out-diff3 out-git >out-diff 2>&1
+
+        if [ "$?" != 0 ]
+        then
+            diff3_fails=$(expr $diff3_fails + 1)
+            echo "*   FAIL: --- --diff-program='diff $dopt'" "$@" " ---"
+        fi
+        if [ "$dret" != "$gret" ]
+        then
+            diff3_stats=$(expr $diff3_stats + 1)
+            echo "*   STAT: ($dret != $gret) --- --diff-program='diff $dopt'" "$@" " ---"
+        fi
+    done
+
+}
+
+###########################################################
+# given some options ($1) and three input files ($2->$4)
+# test git diff3 on permutations of the input files.
+
+test_perm_files () {
+    test_diff3 $1 $2 $3 $4
+    test_diff3 $1 $4 $3 $2
+    test_diff3 $1 $3 $2 $4
+    test_diff3 $1 $4 $2 $3
+    test_diff3 $1 $2 $4 $3
+    test_diff3 $1 $3 $4 $2
+}
+
+###########################################################
+# given three input files ($1->$3) test git diff3 output
+# ($opt == "") and all merge types for several permutaions
+# of the input files.  also test the external diff support.
+
+test_files () {
+
+    diff3_count=0
+    diff3_fails=0
+    diff3_stats=0
+
+    for opt in "" "-mA" "-me" "-mE" "-mx" "-mX" "-m3"
+    do
+        test_perm_files $opt $1 $2 $3
+    done
+
+    test_diff3_extra -mA -L our                  $1 $2 $3
+    test_diff3_extra -mA -L our -L base          $1 $2 $3
+    test_diff3_extra -mA -L our -L base -L their $1 $2 $3
+
+    total_count=$(expr $total_count + $diff3_count)
+    total_fails=$(expr $total_fails + $diff3_fails)
+    total_stats=$(expr $total_stats + $diff3_stats)
+
+    fails_and_stats=$(expr $diff3_fails + $diff3_stats)
+
+    case "$fails_and_stats" in
+    0)
+        return 0 ;;
+    *)
+        echo "    tests: $diff3_count, fails: $diff3_fails, stats: $diff3_stats"
+        return 1 ;;
+    esac
+
+}
+
+###########################################################
+# ok so test some files.
+
+test_expect_success \
+    "test files lao tzu tao" \
+    'test_files ../txxxx/lao ../txxxx/tzu ../txxxx/tao'
+
+test_expect_success \
+    "test files lao1 tzu tao1" \
+    'test_files ../txxxx/lao1 ../txxxx/tzu ../txxxx/tao1'
+
+test_expect_success \
+    "test files lao2 tzu tao2" \
+    'test_files ../txxxx/lao2 ../txxxx/tzu ../txxxx/tao2'
+
+test_expect_success \
+    "test files lao3 tzu tao3" \
+    'test_files ../txxxx/lao3 ../txxxx/tzu ../txxxx/tao3'
+
+test_expect_success \
+    "test files lao4 tzu tao4" \
+    'test_files ../txxxx/lao4 ../txxxx/tzu ../txxxx/tao4'
+
+test_expect_success \
+    "test files tzu tzu tzu" \
+    'test_files ../txxxx/tzu ../txxxx/tzu ../txxxx/tzu'
+
+test_expect_success \
+    "test files lao tzu tzu" \
+    'test_files ../txxxx/lao ../txxxx/tzu ../txxxx/tzu'
+
+test_expect_success \
+    "test files lao tzu /dev/null" \
+    'test_files ../txxxx/lao ../txxxx/tzu /dev/null'
+
+test_expect_success \
+    "test files /dev/null tzu /dev/null" \
+    'test_files /dev/null ../txxxx/tzu /dev/null'
+
+###########################################################
+# ok we are done.
+
+echo "    tests: $total_count, fails: $total_fails, stats: $total_stats"
+
+test_done
+
+
diff --git a/t/txxxx/lao b/t/txxxx/lao
new file mode 100644
index 0000000..635ef2c
--- /dev/null
+++ b/t/txxxx/lao
@@ -0,0 +1,11 @@
+The Way that can be told of is not the eternal Way;
+The name that can be named is not the eternal name.
+The Nameless is the origin of Heaven and Earth;
+The Named is the mother of all things.
+Therefore let there always be non-being,
+  so we may see their subtlety,
+And let there always be being,
+  so we may see their outcome.
+The two are the same,
+But after they are produced,
+  they have different names.
diff --git a/t/txxxx/lao1 b/t/txxxx/lao1
new file mode 100644
index 0000000..831654a
--- /dev/null
+++ b/t/txxxx/lao1
@@ -0,0 +1,8 @@
+The Nameless is the origin of Heaven and Earth;
+
+  so we may see their subtlety,
+  so we may see their outcome.
+The two are the same,
+But after they are produced,
+They both may be called deep and profound.
+The door of all subtleties!
diff --git a/t/txxxx/lao2 b/t/txxxx/lao2
new file mode 100644
index 0000000..a7babdc
--- /dev/null
+++ b/t/txxxx/lao2
@@ -0,0 +1,16 @@
+The Nameless is the origin of Heaven and Earth;
+home, away
+The named is the mother of all things.
+
+Amy, Helen, Kym
+Therefore let there always be non-being,
+  so we may see their subtlety,
+fred, bill, george
+And let there always be being,
+  so we may see their outcome.
+The two are the same,
+But after they are produced,
+  they have different names.
+They both may be called deep and profound.
+Deeper and more profound,
+The door of all subtleties!
diff --git a/t/txxxx/lao3 b/t/txxxx/lao3
new file mode 100644
index 0000000..ea500e5
--- /dev/null
+++ b/t/txxxx/lao3
@@ -0,0 +1,13 @@
+The Nameless is the origin of Heaven and Earth;
+The named is the mother of ALL things.
+
+Therefore let there ALWAYS be non-being,
+  so we may see their subtlety,
+And let there ALWAYS be being,
+  so we may see their outcome.
+The two are the same,
+But after they are produced,
+  they have different names.
+They both may be called deep and profound.
+Deeper and more profound,
+The door of all subtleties!
diff --git a/t/txxxx/lao4 b/t/txxxx/lao4
new file mode 100644
index 0000000..2ca7ddd
--- /dev/null
+++ b/t/txxxx/lao4
@@ -0,0 +1,12 @@
+The Way that can be told of is not the eternal Way;
+The name that can be named is not the eternal name.
+The Nameless is the origin of Heaven and Earth;
+The Named is the mother of all things.
+Therefore let there always be non-being,
+  so we may see their subtlety,
+And let there always be being,
+  so we may see their outcome.
+The two are the same,
+But after they are produced,
+  they have different names.
+unfinished symphony
\ No newline at end of file
diff --git a/t/txxxx/tao b/t/txxxx/tao
new file mode 100644
index 0000000..ffe1ba3
--- /dev/null
+++ b/t/txxxx/tao
@@ -0,0 +1,14 @@
+The Way that can be told of is not the eternal Way;
+The name that can be named is not the eternal name.
+The Nameless is the origin of Heaven and Earth;
+The named is the mother of all things.
+
+Therefore let there always be non-being,
+  so we may see their subtlety,
+And let there always be being,
+  so we may see their result.
+The two are the same,
+But after they are produced,
+  they have different names.
+
+  -- The Way of Lao-Tzu, tr. Wing-tsit Chan
diff --git a/t/txxxx/tao1 b/t/txxxx/tao1
new file mode 100644
index 0000000..7c0e98a
--- /dev/null
+++ b/t/txxxx/tao1
@@ -0,0 +1,10 @@
+The Nameless is the origin of Heaven and Earth;
+The named is the mother of all things.
+Therefore let there always be non-being,
+And let there always be being,
+The two are the same,
+But after they are produced,
+  they have different names.
+They both may be called DEEP and profound.
+Deeper and more profound,
+The door of ALL subtleties!
diff --git a/t/txxxx/tao2 b/t/txxxx/tao2
new file mode 100644
index 0000000..033360b
--- /dev/null
+++ b/t/txxxx/tao2
@@ -0,0 +1,16 @@
+The Nameless is the origin of Heaven and Earth;
+The named is the mother of all things.
+mars, venus, neptune
+
+Therefore let there always be non-being,
+quartz, diamond, ruby
+  so we may see their subtlety,
+And let there always be being,
+lilly, rose, tulip
+  so we may see their outcome.
+The two are the same,
+But after they are produced,
+  they have different names.
+They both may be called deep and profound.
+Deeper and more profound,
+The door of all subtleties!
diff --git a/t/txxxx/tao3 b/t/txxxx/tao3
new file mode 100644
index 0000000..0457551
--- /dev/null
+++ b/t/txxxx/tao3
@@ -0,0 +1,13 @@
+The Nameless is the origin of Heaven and Earth;
+The named is the mother of all things.
+THEIR
+Therefore let there always be non-being,
+  so we may see THEIR subtlety,
+And let there always be being,
+  so we may see THEIR outcome.
+The two are the same,
+But after they are produced,
+  they have different names.
+They both may be called deep and profound.
+Deeper and more profound,
+The door of all subtleties!
diff --git a/t/txxxx/tao4 b/t/txxxx/tao4
new file mode 100644
index 0000000..fbe30fd
--- /dev/null
+++ b/t/txxxx/tao4
@@ -0,0 +1,15 @@
+The Way that can be told of is not the eternal Way;
+The name that can be named is not the eternal name.
+The Nameless is the origin of Heaven and Earth;
+The named is the mother of all things.
+
+Therefore let there always be non-being,
+  so we may see their subtlety,
+And let there always be being,
+  so we may see their result.
+The two are the same,
+But after they are produced,
+  they have different names.
+
+  -- The Way of Lao-Tzu, tr. Wing-tsit Chan
+unchained melody
\ No newline at end of file
diff --git a/t/txxxx/tzu b/t/txxxx/tzu
new file mode 100644
index 0000000..5af88a8
--- /dev/null
+++ b/t/txxxx/tzu
@@ -0,0 +1,13 @@
+The Nameless is the origin of Heaven and Earth;
+The named is the mother of all things.
+
+Therefore let there always be non-being,
+  so we may see their subtlety,
+And let there always be being,
+  so we may see their outcome.
+The two are the same,
+But after they are produced,
+  they have different names.
+They both may be called deep and profound.
+Deeper and more profound,
+The door of all subtleties!
-- 
1.4.2