#include "cache.h"

#include "commit.h"

#include "blob.h"

#include "diff.h"

#include "diffcore.h"

#include "quote.h"

#include "xdiff-interface.h"

#include "xdiff/xmacros.h"

#include "log-tree.h"

#include "refs.h"

#include "userdiff.h"

#include "sha1-array.h"

#include "revision.h"

static int compare_paths(const struct combine_diff_path *one,

			  const struct diff_filespec *two)

{

	if (!S_ISDIR(one->mode) && !S_ISDIR(two->mode))

		return strcmp(one->path, two->path);

	return base_name_compare(one->path, strlen(one->path), one->mode,

				 two->path, strlen(two->path), two->mode);

}

static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)

{

	struct diff_queue_struct *q = &diff_queued_diff;

	struct combine_diff_path *p, **tail = &curr;

	int i, cmp;

	if (!n) {

		for (i = 0; i < q->nr; i++) {

			int len;

			const char *path;

			if (diff_unmodified_pair(q->queue[i]))

				continue;

			path = q->queue[i]->two->path;

			len = strlen(path);

			p = xmalloc(combine_diff_path_size(num_parent, len));

			p->path = (char *) &(p->parent[num_parent]);

			memcpy(p->path, path, len);

			p->path[len] = 0;

			p->next = NULL;

			memset(p->parent, 0,

			       sizeof(p->parent[0]) * num_parent);

			oidcpy(&p->oid, &q->queue[i]->two->oid);

			p->mode = q->queue[i]->two->mode;

			oidcpy(&p->parent[n].oid, &q->queue[i]->one->oid);

			p->parent[n].mode = q->queue[i]->one->mode;

			p->parent[n].status = q->queue[i]->status;

			*tail = p;

			tail = &p->next;

		}

		return curr;

	}

	/*

	 * paths in curr (linked list) and q->queue[] (array) are

	 * both sorted in the tree order.

	 */

	i = 0;

	while ((p = *tail) != NULL) {

		cmp = ((i >= q->nr)

		       ? -1 : compare_paths(p, q->queue[i]->two));

		if (cmp < 0) {

			/* p->path not in q->queue[]; drop it */

			*tail = p->next;

			free(p);

			continue;

		}

		if (cmp > 0) {

			/* q->queue[i] not in p->path; skip it */

			i++;

			continue;

		}

		oidcpy(&p->parent[n].oid, &q->queue[i]->one->oid);

		p->parent[n].mode = q->queue[i]->one->mode;

		p->parent[n].status = q->queue[i]->status;

		tail = &p->next;

		i++;

	}

	return curr;

}

/* Lines lost from parent */

struct lline {

	struct lline *next, *prev;

	int len;

	unsigned long parent_map;

	char line[FLEX_ARRAY];

};

/* Lines lost from current parent (before coalescing) */

struct plost {

	struct lline *lost_head, *lost_tail;

	int len;

};

/* Lines surviving in the merge result */

struct sline {

	/* Accumulated and coalesced lost lines */

	struct lline *lost;

	int lenlost;

	struct plost plost;

	char *bol;

	int len;

	/* bit 0 up to (N-1) are on if the parent has this line (i.e.

	 * we did not change it).

	 * bit N is used for "interesting" lines, including context.

	 * bit (N+1) is used for "do not show deletion before this".

	 */

	unsigned long flag;

	unsigned long *p_lno;

};

static int match_string_spaces(const char *line1, int len1,

			       const char *line2, int len2,

			       long flags)

{

	if (flags & XDF_WHITESPACE_FLAGS) {

		for (; len1 > 0 && XDL_ISSPACE(line1[len1 - 1]); len1--);

		for (; len2 > 0 && XDL_ISSPACE(line2[len2 - 1]); len2--);

	}

	if (!(flags & (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE)))

		return (len1 == len2 && !memcmp(line1, line2, len1));

	while (len1 > 0 && len2 > 0) {

		len1--;

		len2--;

		if (XDL_ISSPACE(line1[len1]) || XDL_ISSPACE(line2[len2])) {

			if ((flags & XDF_IGNORE_WHITESPACE_CHANGE) &&

			    (!XDL_ISSPACE(line1[len1]) || !XDL_ISSPACE(line2[len2])))

				return 0;

			for (; len1 > 0 && XDL_ISSPACE(line1[len1]); len1--);

			for (; len2 > 0 && XDL_ISSPACE(line2[len2]); len2--);

		}

		if (line1[len1] != line2[len2])

			return 0;

	}

	if (flags & XDF_IGNORE_WHITESPACE) {

		/* Consume remaining spaces */

		for (; len1 > 0 && XDL_ISSPACE(line1[len1 - 1]); len1--);

		for (; len2 > 0 && XDL_ISSPACE(line2[len2 - 1]); len2--);

	}

	/* We matched full line1 and line2 */

	if (!len1 && !len2)

		return 1;

	return 0;

}

enum coalesce_direction { MATCH, BASE, NEW };

/* Coalesce new lines into base by finding LCS */

static struct lline *coalesce_lines(struct lline *base, int *lenbase,

				    struct lline *newline, int lennew,

				    unsigned long parent, long flags)

{

	int **lcs;

	enum coalesce_direction **directions;

	struct lline *baseend, *newend = NULL;

	int i, j, origbaselen = *lenbase;

	if (newline == NULL)

		return base;

	if (base == NULL) {

		*lenbase = lennew;

		return newline;

	}

	/*

	 * Coalesce new lines into base by finding the LCS

	 * - Create the table to run dynamic programming

	 * - Compute the LCS

	 * - Then reverse read the direction structure:

	 *   - If we have MATCH, assign parent to base flag, and consume

	 *   both baseend and newend

	 *   - Else if we have BASE, consume baseend

	 *   - Else if we have NEW, insert newend lline into base and

	 *   consume newend

	 */

	lcs = xcalloc(st_add(origbaselen, 1), sizeof(int*));

	directions = xcalloc(st_add(origbaselen, 1), sizeof(enum coalesce_direction*));

	for (i = 0; i < origbaselen + 1; i++) {

		lcs[i] = xcalloc(st_add(lennew, 1), sizeof(int));

		directions[i] = xcalloc(st_add(lennew, 1), sizeof(enum coalesce_direction));

		directions[i][0] = BASE;

	}

	for (j = 1; j < lennew + 1; j++)

		directions[0][j] = NEW;

	for (i = 1, baseend = base; i < origbaselen + 1; i++) {

		for (j = 1, newend = newline; j < lennew + 1; j++) {

			if (match_string_spaces(baseend->line, baseend->len,

						newend->line, newend->len, flags)) {

				lcs[i][j] = lcs[i - 1][j - 1] + 1;

				directions[i][j] = MATCH;

			} else if (lcs[i][j - 1] >= lcs[i - 1][j]) {

				lcs[i][j] = lcs[i][j - 1];

				directions[i][j] = NEW;

			} else {

				lcs[i][j] = lcs[i - 1][j];

				directions[i][j] = BASE;

			}

			if (newend->next)

				newend = newend->next;

		}

		if (baseend->next)

			baseend = baseend->next;

	}

	for (i = 0; i < origbaselen + 1; i++)

		free(lcs[i]);

	free(lcs);

	/* At this point, baseend and newend point to the end of each lists */

	i--;

	j--;

	while (i != 0 || j != 0) {

		if (directions[i][j] == MATCH) {

			baseend->parent_map |= 1<

			baseend = baseend->prev;

			newend = newend->prev;

			i--;

			j--;

		} else if (directions[i][j] == NEW) {

			struct lline *lline;

			lline = newend;

			/* Remove lline from new list and update newend */

			if (lline->prev)

				lline->prev->next = lline->next;

			else

				newline = lline->next;

			if (lline->next)

				lline->next->prev = lline->prev;

			newend = lline->prev;

			j--;

			/* Add lline to base list */

			if (baseend) {

				lline->next = baseend->next;

				lline->prev = baseend;

				if (lline->prev)

					lline->prev->next = lline;

			}

			else {

				lline->next = base;

				base = lline;

			}

			(*lenbase)++;

			if (lline->next)

				lline->next->prev = lline;

		} else {

			baseend = baseend->prev;

			i--;

		}

	}

	newend = newline;

	while (newend) {

		struct lline *lline = newend;

		newend = newend->next;

		free(lline);

	}

	for (i = 0; i < origbaselen + 1; i++)

		free(directions[i]);

	free(directions);

	return base;

}

static char *grab_blob(const struct object_id *oid, unsigned int mode,

		       unsigned long *size, struct userdiff_driver *textconv,

		       const char *path)

{

	char *blob;

	enum object_type type;

	if (S_ISGITLINK(mode)) {

		struct strbuf buf = STRBUF_INIT;

		strbuf_addf(&buf, "Subproject commit %s\n", oid_to_hex(oid));

		*size = buf.len;

		blob = strbuf_detach(&buf, NULL);

	} else if (is_null_oid(oid)) {

		/* deleted blob */

		*size = 0;

		return xcalloc(1, 1);

	} else if (textconv) {

		struct diff_filespec *df = alloc_filespec(path);

		fill_filespec(df, oid, 1, mode);

		*size = fill_textconv(textconv, df, &blob;;

		free_filespec(df);

	} else {

		blob = read_object_file(oid, &type, size);

		if (type != OBJ_BLOB)

			die("object '%s' is not a blob!", oid_to_hex(oid));

	}

	return blob;

}

static void append_lost(struct sline *sline, int n, const char *line, int len)

{

	struct lline *lline;

	unsigned long this_mask = (1UL<

	if (line[len-1] == '\n')

		len--;

	FLEX_ALLOC_MEM(lline, line, line, len);

	lline->len = len;

	lline->next = NULL;

	lline->prev = sline->plost.lost_tail;

	if (lline->prev)

		lline->prev->next = lline;

	else

		sline->plost.lost_head = lline;

	sline->plost.lost_tail = lline;

	sline->plost.len++;

	lline->parent_map = this_mask;

}

struct combine_diff_state {

	unsigned int lno;

	int ob, on, nb, nn;

	unsigned long nmask;

	int num_parent;

	int n;

	struct sline *sline;

	struct sline *lost_bucket;

};

static void consume_line(void *state_, char *line, unsigned long len)

{

	struct combine_diff_state *state = state_;

	if (5 < len && !memcmp("@@ -", line, 4)) {

		if (parse_hunk_header(line, len,

				      &state->ob, &state->on,

				      &state->nb, &state->nn))

			return;

		state->lno = state->nb;

		if (state->nn == 0) {

			/* @@ -X,Y +N,0 @@ removed Y lines

			 * that would have come *after* line N

			 * in the result.  Our lost buckets hang

			 * to the line after the removed lines,

			 *

			 * Note that this is correct even when N == 0,

			 * in which case the hunk removes the first

			 * line in the file.

			 */

			state->lost_bucket = &state->sline[state->nb];

			if (!state->nb)

				state->nb = 1;

		} else {

			state->lost_bucket = &state->sline[state->nb-1];

		}

		if (!state->sline[state->nb-1].p_lno)

			state->sline[state->nb-1].p_lno =

				xcalloc(state->num_parent,

					sizeof(unsigned long));

		state->sline[state->nb-1].p_lno[state->n] = state->ob;

		return;

	}

	if (!state->lost_bucket)

		return; /* not in any hunk yet */

	switch (line[0]) {

	case '-':

		append_lost(state->lost_bucket, state->n, line+1, len-1);

		break;

	case '+':

		state->sline[state->lno-1].flag |= state->nmask;

		state->lno++;

		break;

	}

}

static void combine_diff(const struct object_id *parent, unsigned int mode,

			 mmfile_t *result_file,

			 struct sline *sline, unsigned int cnt, int n,

			 int num_parent, int result_deleted,

			 struct userdiff_driver *textconv,

			 const char *path, long flags)

{

	unsigned int p_lno, lno;

	unsigned long nmask = (1UL << n);

	xpparam_t xpp;

	xdemitconf_t xecfg;

	mmfile_t parent_file;

	struct combine_diff_state state;

	unsigned long sz;

	if (result_deleted)

		return; /* result deleted */

	parent_file.ptr = grab_blob(parent, mode, &sz, textconv, path);

	parent_file.size = sz;

	memset(&xpp, 0, sizeof(xpp));

	xpp.flags = flags;

	memset(&xecfg, 0, sizeof(xecfg));

	memset(&state, 0, sizeof(state));

	state.nmask = nmask;

	state.sline = sline;

	state.lno = 1;

	state.num_parent = num_parent;

	state.n = n;

	if (xdi_diff_outf(&parent_file, result_file, consume_line, &state,

			  &xpp, &xecfg))

		die("unable to generate combined diff for %s",

		    oid_to_hex(parent));

	free(parent_file.ptr);

	/* Assign line numbers for this parent.

	 *

	 * sline[lno].p_lno[n] records the first line number

	 * (counting from 1) for parent N if the final hunk display

	 * started by showing sline[lno] (possibly showing the lost

	 * lines attached to it first).

	 */

	for (lno = 0,  p_lno = 1; lno <= cnt; lno++) {

		struct lline *ll;

		sline[lno].p_lno[n] = p_lno;

		/* Coalesce new lines */

		if (sline[lno].plost.lost_head) {

			struct sline *sl = &sline[lno];

			sl->lost = coalesce_lines(sl->lost, &sl->lenlost,

						  sl->plost.lost_head,

						  sl->plost.len, n, flags);

			sl->plost.lost_head = sl->plost.lost_tail = NULL;

			sl->plost.len = 0;

		}

		/* How many lines would this sline advance the p_lno? */

		ll = sline[lno].lost;

		while (ll) {

			if (ll->parent_map & nmask)

				p_lno++; /* '-' means parent had it */

			ll = ll->next;

		}

		if (lno < cnt && !(sline[lno].flag & nmask))

			p_lno++; /* no '+' means parent had it */

	}

	sline[lno].p_lno[n] = p_lno; /* trailer */

}

static unsigned long context = 3;

static char combine_marker = '@';

static int interesting(struct sline *sline, unsigned long all_mask)

{

	/* If some parents lost lines here, or if we have added to

	 * some parent, it is interesting.

	 */

	return ((sline->flag & all_mask) || sline->lost);

}

static unsigned long adjust_hunk_tail(struct sline *sline,

				      unsigned long all_mask,

				      unsigned long hunk_begin,

				      unsigned long i)

{

	/* i points at the first uninteresting line.  If the last line

	 * of the hunk was interesting only because it has some

	 * deletion, then it is not all that interesting for the

	 * purpose of giving trailing context lines.  This is because

	 * we output '-' line and then unmodified sline[i-1] itself in

	 * that case which gives us one extra context line.

	 */

	if ((hunk_begin + 1 <= i) && !(sline[i-1].flag & all_mask))

		i--;

	return i;

}

static unsigned long find_next(struct sline *sline,

			       unsigned long mark,

			       unsigned long i,

			       unsigned long cnt,

			       int look_for_uninteresting)

{

	/* We have examined up to i-1 and are about to look at i.

	 * Find next interesting or uninteresting line.  Here,

	 * "interesting" does not mean interesting(), but marked by

	 * the give_context() function below (i.e. it includes context

	 * lines that are not interesting to interesting() function

	 * that are surrounded by interesting() ones.

	 */

	while (i <= cnt)

		if (look_for_uninteresting

		    ? !(sline[i].flag & mark)

		    : (sline[i].flag & mark))

			return i;

		else

			i++;

	return i;

}

static int give_context(struct sline *sline, unsigned long cnt, int num_parent)

{

	unsigned long all_mask = (1UL<

	unsigned long mark = (1UL<

	unsigned long no_pre_delete = (2UL<

	unsigned long i;

	/* Two groups of interesting lines may have a short gap of

	 * uninteresting lines.  Connect such groups to give them a

	 * bit of context.

	 *

	 * We first start from what the interesting() function says,

	 * and mark them with "mark", and paint context lines with the

	 * mark.  So interesting() would still say false for such context

	 * lines but they are treated as "interesting" in the end.

	 */

	i = find_next(sline, mark, 0, cnt, 0);

	if (cnt < i)

		return 0;

	while (i <= cnt) {

		unsigned long j = (context < i) ? (i - context) : 0;

		unsigned long k;

		/* Paint a few lines before the first interesting line. */

		while (j < i) {

			if (!(sline[j].flag & mark))

				sline[j].flag |= no_pre_delete;

			sline[j++].flag |= mark;

		}

	again:

		/* we know up to i is to be included.  where does the

		 * next uninteresting one start?

		 */

		j = find_next(sline, mark, i, cnt, 1);

		if (cnt < j)

			break; /* the rest are all interesting */

		/* lookahead context lines */

		k = find_next(sline, mark, j, cnt, 0);

		j = adjust_hunk_tail(sline, all_mask, i, j);

		if (k < j + context) {

			/* k is interesting and [j,k) are not, but

			 * paint them interesting because the gap is small.

			 */

			while (j < k)

				sline[j++].flag |= mark;

			i = k;

			goto again;

		}

		/* j is the first uninteresting line and there is

		 * no overlap beyond it within context lines.  Paint

		 * the trailing edge a bit.

		 */

		i = k;

		k = (j + context < cnt+1) ? j + context : cnt+1;

		while (j < k)

			sline[j++].flag |= mark;

	}

	return 1;

}

static int make_hunks(struct sline *sline, unsigned long cnt,

		       int num_parent, int dense)

{

	unsigned long all_mask = (1UL<

	unsigned long mark = (1UL<

	unsigned long i;

	int has_interesting = 0;

	for (i = 0; i <= cnt; i++) {

		if (interesting(&sline[i], all_mask))

			sline[i].flag |= mark;

		else

			sline[i].flag &= ~mark;

	}

	if (!dense)

		return give_context(sline, cnt, num_parent);

	/* Look at each hunk, and if we have changes from only one

	 * parent, or the changes are the same from all but one

	 * parent, mark that uninteresting.

	 */

	i = 0;

	while (i <= cnt) {

		unsigned long j, hunk_begin, hunk_end;

		unsigned long same_diff;

		while (i <= cnt && !(sline[i].flag & mark))

			i++;

		if (cnt < i)

			break; /* No more interesting hunks */

		hunk_begin = i;

		for (j = i + 1; j <= cnt; j++) {

			if (!(sline[j].flag & mark)) {

				/* Look beyond the end to see if there

				 * is an interesting line after this

				 * hunk within context span.

				 */

				unsigned long la; /* lookahead */

				int contin = 0;

				la = adjust_hunk_tail(sline, all_mask,

						     hunk_begin, j);

				la = (la + context < cnt + 1) ?

					(la + context) : cnt + 1;

				while (la && j <= --la) {

					if (sline[la].flag & mark) {

						contin = 1;

						break;

					}

				}

				if (!contin)

					break;

				j = la;

			}

		}

		hunk_end = j;

		/* [i..hunk_end) are interesting.  Now is it really

		 * interesting?  We check if there are only two versions

		 * and the result matches one of them.  That is, we look

		 * at:

		 *   (+) line, which records lines added to which parents;

		 *       this line appears in the result.

		 *   (-) line, which records from what parents the line

		 *       was removed; this line does not appear in the result.

		 * then check the set of parents the result has difference

		 * from, from all lines.  If there are lines that has

		 * different set of parents that the result has differences

		 * from, that means we have more than two versions.

		 *

		 * Even when we have only two versions, if the result does

		 * not match any of the parents, the it should be considered

		 * interesting.  In such a case, we would have all '+' line.

		 * After passing the above "two versions" test, that would

		 * appear as "the same set of parents" to be "all parents".

		 */

		same_diff = 0;

		has_interesting = 0;

		for (j = i; j < hunk_end && !has_interesting; j++) {

			unsigned long this_diff = sline[j].flag & all_mask;

			struct lline *ll = sline[j].lost;

			if (this_diff) {

				/* This has some changes.  Is it the

				 * same as others?

				 */

				if (!same_diff)

					same_diff = this_diff;

				else if (same_diff != this_diff) {

					has_interesting = 1;

					break;

				}

			}

			while (ll && !has_interesting) {

				/* Lost this line from these parents;

				 * who are they?  Are they the same?

				 */

				this_diff = ll->parent_map;

				if (!same_diff)

					same_diff = this_diff;

				else if (same_diff != this_diff) {

					has_interesting = 1;

				}

				ll = ll->next;

			}

		}

		if (!has_interesting && same_diff != all_mask) {

			/* This hunk is not that interesting after all */

			for (j = hunk_begin; j < hunk_end; j++)

				sline[j].flag &= ~mark;

		}

		i = hunk_end;

	}

	has_interesting = give_context(sline, cnt, num_parent);

	return has_interesting;

}

static void show_parent_lno(struct sline *sline, unsigned long l0, unsigned long l1, int n, unsigned long null_context)

{

	l0 = sline[l0].p_lno[n];

	l1 = sline[l1].p_lno[n];

	printf(" -%lu,%lu", l0, l1-l0-null_context);

}

static int hunk_comment_line(const char *bol)

{

	int ch;

	if (!bol)

		return 0;

	ch = *bol & 0xff;

	return (isalpha(ch) || ch == '_' || ch == '$');

}

static void show_line_to_eol(const char *line, int len, const char *reset)

{

	int saw_cr_at_eol = 0;

	if (len < 0)

		len = strlen(line);

	saw_cr_at_eol = (len && line[len-1] == '\r');

	printf("%.*s%s%s\n", len - saw_cr_at_eol, line,

	       reset,

	       saw_cr_at_eol ? "\r" : "");

}

static void dump_sline(struct sline *sline, const char *line_prefix,

		       unsigned long cnt, int num_parent,

		       int use_color, int result_deleted)

{

	unsigned long mark = (1UL<

	unsigned long no_pre_delete = (2UL<

	int i;

	unsigned long lno = 0;

	const char *c_frag = diff_get_color(use_color, DIFF_FRAGINFO);

	const char *c_func = diff_get_color(use_color, DIFF_FUNCINFO);

	const char *c_new = diff_get_color(use_color, DIFF_FILE_NEW);

	const char *c_old = diff_get_color(use_color, DIFF_FILE_OLD);

	const char *c_context = diff_get_color(use_color, DIFF_CONTEXT);

	const char *c_reset = diff_get_color(use_color, DIFF_RESET);

	if (result_deleted)

		return; /* result deleted */

	while (1) {

		unsigned long hunk_end;

		unsigned long rlines;

		const char *hunk_comment = NULL;

		unsigned long null_context = 0;

		while (lno <= cnt && !(sline[lno].flag & mark)) {

			if (hunk_comment_line(sline[lno].bol))

				hunk_comment = sline[lno].bol;

			lno++;

		}

		if (cnt < lno)

			break;

		else {

			for (hunk_end = lno + 1; hunk_end <= cnt; hunk_end++)

				if (!(sline[hunk_end].flag & mark))

					break;

		}

		rlines = hunk_end - lno;

		if (cnt < hunk_end)

			rlines--; /* pointing at the last delete hunk */

		if (!context) {

			/*

			 * Even when running with --unified=0, all

			 * lines in the hunk needs to be processed in

			 * the loop below in order to show the

			 * deletion recorded in lost_head.  However,

			 * we do not want to show the resulting line

			 * with all blank context markers in such a

			 * case.  Compensate.

			 */

			unsigned long j;

			for (j = lno; j < hunk_end; j++)

				if (!(sline[j].flag & (mark-1)))

					null_context++;

			rlines -= null_context;

		}

		printf("%s%s", line_prefix, c_frag);

		for (i = 0; i <= num_parent; i++) putchar(combine_marker);

		for (i = 0; i < num_parent; i++)

			show_parent_lno(sline, lno, hunk_end, i, null_context);

		printf(" +%lu,%lu ", lno+1, rlines);

		for (i = 0; i <= num_parent; i++) putchar(combine_marker);

		if (hunk_comment) {

			int comment_end = 0;

			for (i = 0; i < 40; i++) {

				int ch = hunk_comment[i] & 0xff;

				if (!ch || ch == '\n')

					break;

				if (!isspace(ch))

				    comment_end = i;

			}

			if (comment_end)

				printf("%s%s %s%s", c_reset,

						    c_context, c_reset,

						    c_func);

			for (i = 0; i < comment_end; i++)

				putchar(hunk_comment[i]);

		}

		printf("%s\n", c_reset);

		while (lno < hunk_end) {

			struct lline *ll;

			int j;

			unsigned long p_mask;

			struct sline *sl = &sline[lno++];

			ll = (sl->flag & no_pre_delete) ? NULL : sl->lost;

			while (ll) {

				printf("%s%s", line_prefix, c_old);

				for (j = 0; j < num_parent; j++) {

					if (ll->parent_map & (1UL<

						putchar('-');

					else

						putchar(' ');

				}

				show_line_to_eol(ll->line, -1, c_reset);

				ll = ll->next;

			}

			if (cnt < lno)

				break;

			p_mask = 1;

			fputs(line_prefix, stdout);

			if (!(sl->flag & (mark-1))) {

				/*

				 * This sline was here to hang the

				 * lost lines in front of it.

				 */

				if (!context)

					continue;

				fputs(c_context, stdout);

			}

			else

				fputs(c_new, stdout);

			for (j = 0; j < num_parent; j++) {

				if (p_mask & sl->flag)

					putchar('+');

				else

					putchar(' ');

				p_mask <<= 1;

			}

			show_line_to_eol(sl->bol, sl->len, c_reset);

		}

	}

}

static void reuse_combine_diff(struct sline *sline, unsigned long cnt,

			       int i, int j)

{

	/* We have already examined parent j and we know parent i

	 * and parent j are the same, so reuse the combined result

	 * of parent j for parent i.

	 */

	unsigned long lno, imask, jmask;

	imask = (1UL<

	jmask = (1UL<

	for (lno = 0; lno <= cnt; lno++) {

		struct lline *ll = sline->lost;

		sline->p_lno[i] = sline->p_lno[j];

		while (ll) {

			if (ll->parent_map & jmask)

				ll->parent_map |= imask;

			ll = ll->next;

		}

		if (sline->flag & jmask)

			sline->flag |= imask;

		sline++;

	}

	/* the overall size of the file (sline[cnt]) */

	sline->p_lno[i] = sline->p_lno[j];

}

static void dump_quoted_path(const char *head,

			     const char *prefix,

			     const char *path,

			     const char *line_prefix,

			     const char *c_meta, const char *c_reset)

{