* Re: [PATCH] xdiff: add xdl_merge()
2006-11-21 22:24 (unknown) Johannes Schindelin
2006-11-21 23:15 ` [PATCH] xdiff: add xdl_merge() (was: (unknown)) Jakub Narebski
@ 2006-11-22 19:58 ` Ramsay Jones
2006-11-22 20:16 ` your mail Davide Libenzi
2 siblings, 0 replies; 5+ messages in thread
From: Ramsay Jones @ 2006-11-22 19:58 UTC (permalink / raw)
To: Johannes Schindelin; +Cc: Davide Libenzi, git, Junio C Hamano
[-- 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
^ permalink raw reply related [flat|nested] 5+ messages in thread