/*
 * wiggle - apply rejected patches
 *
 * Copyright (C) 2003 Neil Brown <neilb@cse.unsw.edu.au>
 *
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *    Author: Neil Brown
 *    Email: <neilb@suse.de>
 */


/*
 * This file contains routines use to create a merge.
 * The core process is to take two coincidence lists, A-B and B-C,
 * which identify coincidences and, but ommission, changes, and
 * to apply to replace every part of A that matches B with the
 * part of C that aligns with that part of B.  In the case where
 * a B-C difference does not align completely with an A-B coincidence,
 * we have a conflict.
 *
 * Throught the processing of merges we need a concept of a position in the
 * overall merge.  This is represented by an index into one of the files, and
 * and indicator as to which file.
 * If the point is in:
 *    A - then it is an unmatched part of A, before a coincidence.
 *    B - then it is in a section where A matches B and B matches C.
 *    C - then it is in an unmatched part of C, but the corresponding part
 *        of B completely coincides with A.
 * With each position we keep indexes into the coincidence lists for
 * the containing or next coincidence in each.
 *
 *
 * The first stage of merge processing is to identify conflicts.
 * A conflict is identified by a start point and an end point.
 * The first approximation for the start point is the end
 * of the last A-B coincidence that starts before the B start
 * of the B-C difference that causes the conflict.

 *
 * We have a concept of a 'point'
 * The start and end of the file are each points.
 * Also the start and end of any conflict is a point.
 * Outside of a conflict, we can move points forwards or backwards
 * through the merger.  Inside a conflict movement is not well defined.
 * Any point is 'forward looking' or 'backward looking'.
 * A forward looking point can be moved forward but not backward.
 * A backward looking point can be moved backward, not forward.
 *
 * If a forward looking point is a tri-point, in a double-coincidence,
 * then c1/c2 will be set to the furthest forward double coincidence that is before
 * or contains the point, thus it well-defines the start of a double coincidence
 * or that end of a conflict.
 * inversely, a BL point well-defines the end of a DC or start of a conflict.
 *
 * The start of a conflict is a backward looking point.
 * The end of a conflict is a forward looking point.
 *
 * In normal (Word/line) mode, we move the boundaries of a conflict out
 * until they are at end-of-line.
 * When moving forward, this is until we cross over a newline word.
 * When moving backward, this is until one step before crossing over
 * a newline word, so we need to remember our last position.
 *
 * Away from a conflict, every point can be clearly defined as a
 * location either in A or in C.  The 'point' is immediately before
 * the word at that location.
 * At the end of a conflict, this is still well defined as the 'next word'
 * is outside a conflict.
 * At the start of a conflict this may not be well defined as there may not
 * be a clear 'next' word.  We choose the point the would be reached by
 * the step-forward algorithm so that it is easy to test if at start-of-conflict.
 *
 * A conflict is always bounded by a double coincidence.  i.e. the word before a conflict
 * is the same in all 3 texts, and the word after a conflict is the same in all
 * 3 texts.  To allow for conflicts at start and end of file, we consider the
 * start and end of the three texts to each be double co-incidences.
 *
 * Each double co-incidence has a start and an end.  When we find a conflict, it
 * is taken to extend from the end of the previous double coincidence to the
 * start of the next double co-incidence.
 * Between conflicts we can mergers which can be printed simply be advancing the start
 * point and printing each word as we go.
 *
 * The double co-incidence at the start begins forward-looking A=0 or C=0,
 * depending on which word is first, and ends at backward-looking A=0.
 * The double co-incidence at the end begins at forward-looking
 * C=max and ends at backward looking A=max or C=max depending on which
 * would be the last word.
 *
 * Each point is defined by a flag "in_a" which is true if the point is in A,
 * and index 'pos' which gives the position in A or C depending on "in_a", and
 * an index into each co-incidence list, c1 and c2.
 *
 * For forward looking points:
 *   if in_a:
 *       c1 is the first co-incidence that ends after pos. - or is tail co-incidence.
 *       c2 is the first co-incidence that ends at or after c1.b
 *   if in_c:
 *       c2 is the first co-incidence that ends after pos - or is tail co-incidence.
 *       c1 is the first co-incidence that ends at or after c2.a
 *
 * For a backward looking point:
 *   if in_a:
 *       c1 is the last co-incidence that starts before pos, or -1
 *       c2 is the last co-incidence that starts at or before c1.b
 *   if in_c:
 *       c2 is the last co-incidence that starts before pos, or -1
 *       c1 is the last co-incidence that .. lines up properly.
 *
 * To advance a point we increment pos, then
 *   if in_a and at start of c1
 *      slide up to c and if at end of c2, advance c2, then c1 and repeat
 *   if in_c and within c2 and corresponding a at end of c1, and c1->len != 0
 *      slide down to a, increment c1 and advance c2, then repeat.
 *
 * To retreat a backward facing point
 *   if in_a and at end of c1 and c1!=-1,
 *      slide up to c and if at start of c2, retreat c2, thenc 1, and repeat
 *   if in_c and within c2 and corresponding a at start of c1
 *      slide down to a, decrement c1 and retreat c2, then repeat.
 *   Then decrement pos.
 *
 * We never actually compare points for ordering.  We should 'know' the likely order
 * and only compare equal or not.  This can be tested independant of direction,
 * and done by simply comparing in_a and pos.
 */


/* Each point involves a location in each of A, B, and C.
 * There is a conflict for each change in B-C where the B section
 * is not wholey contained in an A-B co-incidence.
 * The start point of a conflict is determined as:
 *   C is the end of the C side of the  previous B-C coincidence (or
 *       start of file
 *   B is the end of the B side of the matching A-B coincidence if
 *       the point is in an A-B coincidence, or the end of the previous
 *       A-B coincidence of not.
 *     As B moves backwards searching for an A-B coincidence, if it enters
 *      a B-C coincidence, C is moved backwards too.
 *   A is the matching point to B in the A-B coincidence that B is in.
 *
 * The end point of a conflict is determined in a similar way,
 * except that B is in a coincidence that is at, or *follows* the
 * end of the next B-C coincidence.
 *
 * Once these coincidences have been enumerated, the endpoints are
 * optionally moved to be at start-of-line.  The start point is moved
 * backwards and the endpoint forwards.  The endofline must be in an
 * A-B coincidence and may be in C if there is also a B-C coincidence.
 *
 * The next step is to merge adjacent conflicts where the B point
 * from one overlaps the next.
 *
 */
#include	<unistd.h>
#include	<stdlib.h>
#include	"wiggle.h"

/* A point is somewhere either in_a or not in_a (in which case, in C).
 * if in_a, c1 points to the next a-b coincidence strictly after pos
 *          c2 points to the b-c coincidence that contains (possibly as end point) or follows c1.b
 * if !in_a, c2 points to the b-c coincidence that contains (possibly as endpoint) or follows pos
 *           c1 points to the a-b coincidence that contains c2.b
 *
 * A point is not well defined inside a conflict, Though it is at the
 * 'start' and 'end' of a conflict.
 *
 * At the start of the file c1 and c2 will be the firsts match in A-B and B-C
 * If [c1]->a is 0, then !in_a and pos is [c2]->b+x where x is
 * chosen such that [c1]->b == [c2]->a+x and x < [c2]->len.  If such choice
 * is not possible, there is a conflict at the start of the file and so we choose
 * a point as if [c1]->a were not 0.
 *
 * If [c1]->a is not 0, then in_a and pos == 0.
 *
 * To find the start of file, we set in_a and pos==-1, and advance one step.
 *
 * At the end of the file, c1 will be the EOF match in A-B, c2 will be the
 * EOF match in B-C, !in_a and pos == [c2]->b
 */
struct point { int pos, in_a; int c1,c2; };


static int tripoint(struct point *here,
		    struct csl *c1, struct csl *c2,
		    int *a, int *b, int *c)
{
	/* find a, b, and c for 'here'.
	 * If any are not well defined, return 0.
	 */
	c1 += here->c1;
	c2 += here->c2;

	if (here->in_a) {
		*a = here->pos;

		if (here->c1 < 0) {
			if (*a) return 0;
			*b = 0;
		} else if (c1->a <= *a && c1->a+c1->len >= *a)
			*b = c1->b + (*a - c1->a);
		else
			return 0;

		if (here->c2 < 0) {
			if (*b) return 0;
			*c = 0;
		} else if (c2->a <= *b && c2->a + c2->len >= *b)
			*c = c2->b + *b - c2->a;
		else
			return 0;
	} else {
		*c = here->pos;

		if (here->c2 < 0) {
			if (*c) return 0;
			*b = 0;
		} else if (c2->b <= *c && c2->b +c2->len >= *c)
			*b = c2->a + *c - c2->b;
		else
			return 0;


		if (here->c1 < 0) {
			if (*b) return 0;
			*a = 0;
		} else if (c1->b <= *b && c1->b + c1->len >= *b)
			*a = c1->a + *b - c1->b;
		else
			return 0;
	}
	return 1;
}

static int retreat(struct csl *c1, struct csl *c2, struct point *p)
{
	int a,b,c;
	int slid = 0;

 retry:
	if (p->in_a) {
		/* retreat c1 to first coincidence containing or after pos */
		a = p->pos;
		while ((p->c1 == 0 && a == 0) ||
		       (p->c1 > 0 && c1[p->c1-1].a + c1[p->c1-1].len >= a)) {
			if (!slid)
				if ( a >= c1[p->c1].a)
					break;
			p->c1--;
		}

		/* if we aren't in a co-incidence, just return */
		if (p->c1 >=0 &&
		    c1[p->c1].a > a)
			return 1;

		/* retreat c2 to first coincidence containing or after pos->b */
		if (p->c1 == -1)
			b = 0;
		else
			b = c1[p->c1].b + a - c1[p->c1].a;
		while ((p->c2 == 0 && b == 0) ||
		       (p->c1 > 0 && c2[p->c2-1].a + c2[p->c2-1].len >= b)) {
			if (!slid)
				if (b >= c2[p->c2].a)
					break;
			p->c2--;
		}

		/* check if this is a conflict */
		if ((p->c2>=0 && c2[p->c2].a > b))
			return 2;

		if (p->c2 == -1)
			c = 0;
		else
			c = c2[p->c2].b + b - c2[p->c2].a;

		/* ok, this is the furthest backward double coincidence
		 * if we are not at the start of the A-B coincidence,
		 * slip up to C
		 */
		if (p->c1 >= 0 && a > c1[p->c1].a) {
			p->in_a = 0;
			p->pos = c;
			slid = 1;
			goto retry;
		}
	} else {
		/* retreat c2 to first coincidence containing or after pos */
		c = p->pos;
		while ((p->c2 == 0 && c == 0) ||
		       (p->c2 > 0 && c2[p->c2-1].b + c2[p->c2-1].len >= c)) {
			if (!slid)
				if (c >= c2[p->c2].b)
					break;
			p->c2--;
		}

		/* if we aren't in a coincidence, return */
		if (p->c2 >= 0 &&
		    c2[p->c2].b > c)
			return 1;

		/* retreat c1 to first coincidence containing or afer pos->b */
		if (p->c2 == -1)
			b = 0;
		else
			b = c2[p->c2].a + c - c2[p->c2].b;
		while ((p->c1==0 && b == 0) ||
		       (p->c1 > 0 && c1[p->c1-1].b + c1[p->c1-1].len >= b)) {
			if (!slid)
				if (b >= c1[p->c1].b)
					break;
			p->c1--;
		}

		/* check if this is a conflict */
		if ((p->c1>=0 && c1[p->c1].b > b))
			return 2;

		if (p->c1 == -1)
			a = 0;
		else
			a = c1[p->c1].a + b - c1[p->c1].b;

		/* ok, this is the furthest backward double coincidence
		 * if we are at the start of the A-B coincidence, slide down to A
		 */
		if (p->c1 == -1 ||
		    a == c1[p->c1].a) {
			p->in_a = 1;
			p->pos = a;
			slid = 1;
			goto retry;
		}
	}
	if (p->pos == 0)
		return 0; /* StartOfFile */

	if (!slid) {
		slid = 1;
		goto retry;
	}

	return 1;
}

static int advance(struct csl *c1, struct csl *c2, struct point *p)
{
	int a,b,c;
	int slid = 0;
	/* make next char at point is the 'right' one, either in a or c.
	 * This might involve move p->c1 and p->c2 forward
	 * and changing pos/in_a to an 'equivalent' point
	 */
/*
	if (!p->in_a && c2[p->c2].b == p->pos && c2[p->c2].len == 0)
		return 0; / * at end of file * /
*/
 retry:
	if (p->in_a) {
		/* advance c1 to last coincidence containing or before pos */
		a = p->pos;
		while ((p->c1 == -1 || c1[p->c1].len) &&
		       c1[p->c1+1].a <= a) {
			if (!slid)
				if ((p->c1== -1 && a ==0) ||
				    (p->c1>=0 && a <= c1[p->c1].a+c1[p->c1].len))
					break;
			p->c1++;
		}

		/* if we aren't in a co-incidence, just return */
		if (p->c1 == -1 || c1[p->c1].a+c1[p->c1].len < a)
			return 1;

		/* advance c2 to last coincidence containing or before pos->b */
		b = c1[p->c1].b + a- c1[p->c1].a;
		while ((p->c2 == -1 || c2[p->c2].len) &&
		       c2[p->c2+1].a <= b) {
			if (!slid)
				if ((p->c2 == -1 && b == 0) ||
				    (p->c2 >= 0 && b <= c2[p->c2].a+c2[p->c2].len))
					break;
			p->c2++;
		}

		/* check if this is a conflict */
		if ((p->c2 == -1 && b >0) ||
		    (p->c2>=0 && c2[p->c2].a + c2[p->c2].len < b))
			return 2;

		if (p->c2 == -1)
			c = 0;
		else
			c = c2[p->c2].b + b - c2[p->c2].a;

		/* Ok, this is the furthest forward double coincidence
		 * If we are at eof, or the next char is in the coincidence
		 * slip up to c
		 */
		if (c1[p->c1].len == 0 ||
		    a < c1[p->c1].a + c1[p->c1].len) {
			p->in_a = 0;
			/*
			 * if we've slid, make sure not to skip over
			 * the stuff in c2.
			 */
			if(slid && p->c2 != -1 && c2[p->c2].a == b &&
			   c2[p->c2].b > c2[p->c2].a) {
				c -= c2[p->c2].b - c2[p->c2].a;
			}

			p->pos = c;
			slid = 1;
			goto retry;
		}
	} else {
		/* advance c2 to last coincidence containing or before pos */
		c = p->pos;
		while ((p->c2 == -1 || c2[p->c2].len) &&
		       c2[p->c2+1].b <= c) {
			if (!slid)
				if ((p->c2 == -1 && c == 0) ||
				    (p->c2 >= 0 && c <= c2[p->c2].b+c2[p->c2].len))
					break;
			p->c2++;
		}

		/* if we aren't in a co-incidence then just return */
		if (p->c2 == -1 || c2[p->c2].b+c2[p->c2].len < c)
			return 1;

		/* advance c1 to last coincidence containing or before pos->b */
		b = c2[p->c2].a + c - c2[p->c2].b;
		while ((p->c1 == -1 || c1[p->c1].len) &&
		       c1[p->c1+1].b <= b) {
			if (!slid)
				if ((p->c1 == -1 && b ==0) ||
				    (p->c1 >= 0 && b <= c1[p->c1].b+c1[p->c1].len))
					break;
			p->c1++;
		}

		/* check if this is a conflict */
		if (p->c1 == -1 || c1[p->c1].b + c1[p->c1].len < b)
			return 2;

		a = c1[p->c1].a + b - c1[p->c1].b;

		/* ok, this is the furthest forward double coincidence
		 * If it is the end of an A-B coincidence but not EOF,
		 * slide down to A
		 */
		if (a == c1[p->c1].a+ c1[p->c1].len &&
		    c1[p->c1].len) {
			p->in_a = 1;
			p->pos = a;
			slid = 1;
			goto retry;
		}
	}
	if (!p->in_a && c2[p->c2].b == p->pos && c2[p->c2].len == 0)
		return 0; /* at end of file */
	if (!slid) {
		slid = 1;
		goto retry;
	}
	return 1;
}

static int point_crossed(struct point first, struct point second,
		      struct csl *cs1, struct csl *cs2)
{
	int a1,b1,c1;
	int a2,b2,c2;

	if (tripoint(&first, cs1,cs2, &a1,&b1,&c1) &&
	    tripoint(&second, cs1,cs2, &a2,&b2,&c2))
		return a1>=a2 && b1>=b2 && c1>=c2;
	return 0;
/*
	return first.in_a == second.in_a &&
		first.pos == second.pos;
*/
}


static void print_merger(FILE *out, struct file *a, struct file *c,
		 struct csl *cs1, struct csl *cs2,
		 struct point start, struct point end)
{
	while (!point_crossed(start, end, cs1,cs2)) {
#if 0
		printf("%c %d (%d,%d)\n", start.in_a?'A':'C', start.pos, start.c1,start.c2);
#endif
		if (start.in_a)
			printword(out, a->list[start.pos]);
		else
			printword(out, c->list[start.pos]);
		fflush(out); /* DEBUG */

		start.pos++;
		if (point_crossed(start, end, cs1,cs2))
			break;
		advance(cs1, cs2, &start);

	}
}

static int inline at_sol(struct file *f, int i)
{
	return i == 0 || i == f->elcnt ||
		ends_line(f->list[i-1]);
}

static void print_range(FILE *out, struct file *f, int start, int end)
{
	for (; start < end ; start++)
		printword(out, f->list[start]);
}

static int print_conflict(FILE *out, struct file *a, struct file *b, struct file *c,
		    struct csl *c1, struct csl *c2,
		    struct point start, struct point end,
		    int words)
{
	int astart, bstart, cstart;
	int aend, bend, cend;
	int bi;

#if 0
	if (point_same(start,end))
		return 0; /* no conflict here !! */
#endif
	if (!tripoint(&start, c1,c2, &astart, &bstart, &cstart))
		abort();
	if (!tripoint(&end,   c1,c2, &aend,   &bend,   &cend))
		abort();


	/* Now contract the conflict if possible, but insist on
	 * an end-of-line boundary unless 'words'.
	 */
	/* first contract leading removed text.
	 * so <<<--- X 1 ||| X 2 === 3 --->>> becomes <<<--- 1 ||| 2 === 3 --->>>
	 */
	bi = bstart;
	while (bi < bend && start.c1 >= 0 && bi >= c1[start.c1].b && bi < c1[start.c1].b + c1[start.c1].len) {
		bi++;
		if (words || at_sol(b,bi)) {
			astart += bi-bstart;
			bstart = bi;
		}
	}
	/* and contract trailing removed text */
	bi = bend;
	while (bi > bstart && bi > c1[end.c1].b) {
		bi--;
		if (words || at_sol(b, bi)) {
			aend -= bend-bi;
			bend = bi;
		}
	}

	/* now contract leading unmatched text so
	 * <<<--- 1 ||| X 2 === X 3 --->>> becomes <<<--- 1 ||| 2 === 3 --->>>
	 */
	bi = bstart;
	while (bi < bend && start.c2 >= 0 && bi >= c2[start.c2].a && bi < c2[start.c2].a + c2[start.c2].len) {
		bi++;
		if (words || at_sol(b,bi)) {
			cstart += bi-bstart;
			bstart = bi;
		}
	}
	/* and trailing unmatched */
	bi = bend;
	while (bi > bstart && bi > c2[end.c2].a) {
		bi--;
		if (words || at_sol(b,bi)) {
			cend -= bend-bi;
			bend = bi;
		}
	}
	if (astart >= aend && bstart >= bend && cstart >= cend)
		return 0;

	fputs(words?"<<<---":"<<<<<<<\n", out);
	print_range(out, a, astart, aend);
	fputs(words?"|||":"|||||||\n", out);
	print_range(out, b, bstart, bend);
	fputs(words?"===":"=======\n", out);
	print_range(out, c, cstart, cend);
	fputs(words?"--->>>":">>>>>>>\n", out);
	return 1;
}

static int end_of_file(struct point p, struct csl *c1, struct csl *c2)
{
	return advance(c1,c2,&p)==0;
}

static int next_conflict(struct point here, struct csl *start_c1, struct csl *start_c2,
			 struct point *start, struct point *end,
			 struct file *a, struct file *b, struct file *c)
{
	/* We want to find the start and end of the 'next' conflict.
	 * There may not be another conflict, in which case set start and
	 * end to the end of the files.
	 * The start and end of a conflict must be the end and start of
	 * regions where A matches B and B matches C - except for
	 * The start which might be the start of the file.
	 * 'here' is a potentially valid starting point. Any other starting
	 * point must be the end of a double coincidence.
	 *
	 * So we walk c1 and c2 looking for double coincidences and conflicts.
	 * When we find a conflict, we remember the fact.
	 * When we find a double coincidence we:
	 *   Set 'end' to the start of the DC.
	 *   If conflict-found - return.
	 *   Set 'start' to the end of the DC.
	 *   If the DC was EOF, start will == end == EOF, and we return.
	 *
	 * A double coincidence is easily detected by just looking at a single
	 * entry in c1 and c2.  If
	 *    c1->b+c1->len > c2->a && c2->a+c2->len > c1->b
	 *    || c1->len == c2->len == 0
	 * then we have a double coincidence.
	 *
	 * A conflict is detected when stepping forward.
	 * If we step c2 forward and the new coincidence is beyond or at the
	 * end of c1, or we step forward c1 and it's start is beyond or at the end of c2,
	 * then that is a conflict.
	 * Also, we can detect a conflict at start-of-file (here.in_a, here.pos==0) if
	 * c2 doesn't start at 0.
	 *
	 * 'here' is significant only for its c1/c2 values. They will contain a
	 * double coincidence, though it might be start-of-file.
	 * start must be set to a backward-looking point at the end of a double-coincidence
	 * and end to a forward-looking point and the start of a double-coincidence
	 */


	int conflict_found = 0;
	struct csl *c1 = start_c1;
	struct csl *c2 = start_c2;


	c1 += here.c1;
	c2 += here.c2;

	*start = here;

	while (1) {
		/* Step one of c1 or c2 forward
		 * depending on which ends earlier.
		 * Watch to see if we are stepping over a conflict.
		 */
		if (c2 < start_c2) {
			/* start-of-file.
			 * Move both c1 and c2 forward.
			 *
			 * We have a conflict iff new c1->b > 0 and c2->a > 0
			 * or c1->b >0 && c2->b > 0
			 */
			c1++; c2++;
			if (c1->b > 0 &&
			    (c2->a > 0 || c2->b > 0))
				conflict_found = 1;
			if (c2->a+c2->len < c1->b)
				conflict_found = 1;
		} else if (c1->b+c1->len == c2->a+c2->len) {
			/* both coincidences end at same place. There is
			 * a conflict if there is a gap in c1->b or
			 * c2->a has no gap but c2->b does (implying insertion
			 * at undefined location
			 */
			if (c1->len && c2->len) {
				if (c1[1].b > c1->b + c1->len ||
				    (c2[1].a == c2->a + c2->len &&
				     c2[1].b > c2->b + c2->len))
					conflict_found = 1;
			}
			if (c1->len)
				c1++;
			if (c2->len)
				c2++;
		} else if (c2->len ==0 || (c1->len && c1->b+c1->len < c2->a+c2->len)) {
			/* c1 ends earlier.  If the new start of c1 is
			 * beyond the current end of c2, we have a conflict
			 */
			c1++;
			if (c1->b > c2->a+c2->len)
				conflict_found = 1;
		} else {
			/* c2 ends earlier. If the new start of c2 is
			 * beyond the end of c1, we have a conflict.
			 * Also if the new start of c2 is at the end of c1,
			 * and the old end of c2 is also at end of c1,
			 * then have a conflict, as long as there was actually
			 * something inserted there...
			 */
			c2++;
			if (c2->a > c1->b+c1->len)
				conflict_found = 1;
		}
		if ((c1->len == 0 && c2->len ==0) ||
		    (c1->b+c1->len >= c2->a && c2->a+c2->len >= c1->b)
			) {
			/* double coincidence !
			 * It starts at max of c1->b and c2->a, in c
			 * and ends at min of c1->b+len (in a), c2->a+len (in c)
			 */
			end->c1 = c1-start_c1;
			end->c2 = c2-start_c2;

			if (conflict_found) {
				/* end->c1/c2 holds the end of the conflict,
				 * and start->c1/c2 holds the start
				 * We need to set in_a and pos for each
				 * so that start is backward-looking and the end
				 * of a double-coincidence, and end is forward-looking
				 * at the start of a double-coincidence.
				 */

				c1 = start_c1;
				c2 = start_c2;

				if (start->c1 == -1) {
					start->in_a = 1;
					start->pos = 0;
				} else if (c1[start->c1].b+c1[start->c1].len <=
					   c2[start->c2].a+c2[start->c2].len) {
					start->in_a = 1;
					start->pos = c1[start->c1].a+c1[start->c1].len;
				} else {
					start->in_a = 0;
					start->pos = c2[start->c2].b+c2[start->c2].len;
				}
				retreat(c1,c2, start);

				if (c1[end->c1].b <= c2[end->c2].a) {
					end->in_a = 0;
					end->pos = c2[end->c2].b;
				} else {
					end->in_a = 0;
					end->pos = c2[end->c2].b +
						c1[end->c1].b - c2[end->c2].a;
				}
				advance(c1,c2, end);
				return 1;
			}
			start->c1 = c1-start_c1;
			start->c2 = c2-start_c2;

			if (c1->len == 0 && c2->len == 0) {
				/* eof and no conflict found.
				 * set start and end to eof
				 */
				start->in_a = end->in_a = 0;
				start->pos = end->pos = c2->b;
				return 0;
			}
		}
	}
}

static int already_applied(struct csl *cs1, struct csl *cs2,
			   struct point start, struct point end,
			   struct file *a, struct file *b, struct file *c)
{
	/* check if this conflict reflects and already-applied change
	 * i.e. the section in a matches the section in b
	 */
	int a1,b1,c1;
	int a2,b2,c2;

	if (!tripoint(&start,cs1,cs2,&a1,&b1,&c1))
		abort();
	if (!tripoint(&end,cs1,cs2,&a2,&b2,&c2))
		abort();
	if (a1==a2 && b1==b2) return 0;
	if ((a2-a1) != (c2-c1)) return 0;

	while (a1<a2) {
		if (!match(&a->list[a1], &c->list[c1]))
			return 0;
		a1++;
		c1++;
	}
	return 1;
}

static int Startofline(struct point p, struct csl *cs1, struct csl *cs2,
		       struct file *a, struct file *b, struct file *c)
{
	int a1,b1,c1;
	return
		tripoint(&p,cs1,cs2,&a1,&b1,&c1) &&
		at_sol(a,a1) && at_sol(b,b1) && at_sol(c,c1);

}

struct ci print_merge(FILE *out, struct file *a, struct file *b, struct file *c,
		 struct csl *c1, struct csl *c2,
		 int words)
{
	struct point start_last, end_last, start_next, end_next;

	struct ci rv;
	rv.ignored = rv.conflicts = 0;

#if 0
	{ int i;
	for (i=0; c1[i].len; i++) printf("%2d c1 %d:%d %d\n", i, c1[i].a,c1[i].b,c1[i].len);
	printf("%2d c1 %d:%d END\n", i, c1[i].a,c1[i].b);
	for (i=0; c2[i].len; i++) printf("%2d c2 %d:%d %d\n", i, c2[i].a,c2[i].b,c2[i].len);
	printf("%2d c2 %d:%d END\n", i, c2[i].a,c2[i].b);
	}
#endif
	/* end_last is a forward looking point */
	end_last.pos = 0;
	end_last.in_a = 1;
	end_last.c1 = end_last.c2 = -1;
	advance(c1,c2, &end_last);

	/* start_last is a backward looking point */
	start_last.pos = 0;
	start_last.in_a = 1;
	start_last.c1 = start_last.c2 = 0;
	retreat(c1,c2, &start_last);

	while (!end_of_file(end_last, c1, c2)) {
		next_conflict(end_last, c1, c2, &start_next, &end_next, a, b, c);
		while (already_applied(c1,c2,start_next,end_next,a,b,c)) {
			rv.ignored++;
			next_conflict(end_next, c1,c2,&start_next,&end_next,a,b,c);
		}
#if 0
		printf("start %d %d (%d,%d)  end %d %d (%d,%d)\n",
		       start_next.in_a, start_next.pos, start_next.c1, start_next.c2,
		       end_next.in_a, end_next.pos, end_next.c1, end_next.c2);
#endif
		while (!point_crossed(end_last, start_next,c1,c2) &&
		       !(words || Startofline(end_last, c1,c2, a,b,c))) {
			end_last.pos++;
			advance(c1,c2, &end_last);
		}

		while (!point_crossed(end_last, start_next, c1,c2) &&
		       !(words || Startofline(start_next, c1,c2, a,b,c))) {
			start_next.pos--;
			retreat(c1,c2, &start_next);
		}

		if (point_crossed(end_last, start_next, c1,c2)) {
			end_last = end_next;
			continue;
		}
		if (print_conflict(out, a,b,c, c1,c2, start_last, end_last, words))
			rv.conflicts++;

		print_merger(out, a,c, c1,c2, end_last, start_next);
		start_last = start_next;
		end_last = end_next;
	}
	if (print_conflict(out,a,b,c, c1,c2, start_last, end_last, words))
		rv.conflicts++;
	return rv;
}