git

1
#define USE_THE_REPOSITORY_VARIABLE
2

3
#include "git-compat-util.h"
4
#include "object-store-ll.h"
5
#include "commit.h"
6
#include "convert.h"
7
#include "diff.h"
8
#include "diffcore.h"
9
#include "environment.h"
10
#include "hex.h"
11
#include "object-name.h"
12
#include "quote.h"
13
#include "xdiff-interface.h"
14
#include "xdiff/xmacros.h"
15
#include "log-tree.h"
16
#include "refs.h"
17
#include "tree.h"
18
#include "userdiff.h"
19
#include "oid-array.h"
20
#include "revision.h"
21

22
static int compare_paths(const struct combine_diff_path *one,
23
			  const struct diff_filespec *two)
24
{
25
	if (!S_ISDIR(one->mode) && !S_ISDIR(two->mode))
26
		return strcmp(one->path, two->path);
27

28
	return base_name_compare(one->path, strlen(one->path), one->mode,
29
				 two->path, strlen(two->path), two->mode);
30
}
31

32
static int filename_changed(char status)
33
{
34
	return status == 'R' || status == 'C';
35
}
36

37
static struct combine_diff_path *intersect_paths(
38
	struct combine_diff_path *curr,
39
	int n,
40
	int num_parent,
41
	int combined_all_paths)
42
{
43
	struct diff_queue_struct *q = &diff_queued_diff;
44
	struct combine_diff_path *p, **tail = &curr;
45
	int i, j, cmp;
46

47
	if (!n) {
48
		for (i = 0; i < q->nr; i++) {
49
			int len;
50
			const char *path;
51
			if (diff_unmodified_pair(q->queue[i]))
52
				continue;
53
			path = q->queue[i]->two->path;
54
			len = strlen(path);
55
			p = xmalloc(combine_diff_path_size(num_parent, len));
56
			p->path = (char *) &(p->parent[num_parent]);
57
			memcpy(p->path, path, len);
58
			p->path[len] = 0;
59
			p->next = NULL;
60
			memset(p->parent, 0,
61
			       sizeof(p->parent[0]) * num_parent);
62

63
			oidcpy(&p->oid, &q->queue[i]->two->oid);
64
			p->mode = q->queue[i]->two->mode;
65
			oidcpy(&p->parent[n].oid, &q->queue[i]->one->oid);
66
			p->parent[n].mode = q->queue[i]->one->mode;
67
			p->parent[n].status = q->queue[i]->status;
68

69
			if (combined_all_paths &&
70
			    filename_changed(p->parent[n].status)) {
71
				strbuf_init(&p->parent[n].path, 0);
72
				strbuf_addstr(&p->parent[n].path,
73
					      q->queue[i]->one->path);
74
			}
75
			*tail = p;
76
			tail = &p->next;
77
		}
78
		return curr;
79
	}
80

81
	/*
82
	 * paths in curr (linked list) and q->queue[] (array) are
83
	 * both sorted in the tree order.
84
	 */
85
	i = 0;
86
	while ((p = *tail) != NULL) {
87
		cmp = ((i >= q->nr)
88
		       ? -1 : compare_paths(p, q->queue[i]->two));
89

90
		if (cmp < 0) {
91
			/* p->path not in q->queue[]; drop it */
92
			*tail = p->next;
93
			for (j = 0; j < num_parent; j++)
94
				if (combined_all_paths &&
95
				    filename_changed(p->parent[j].status))
96
					strbuf_release(&p->parent[j].path);
97
			free(p);
98
			continue;
99
		}
100

101
		if (cmp > 0) {
102
			/* q->queue[i] not in p->path; skip it */
103
			i++;
104
			continue;
105
		}
106

107
		oidcpy(&p->parent[n].oid, &q->queue[i]->one->oid);
108
		p->parent[n].mode = q->queue[i]->one->mode;
109
		p->parent[n].status = q->queue[i]->status;
110
		if (combined_all_paths &&
111
		    filename_changed(p->parent[n].status))
112
			strbuf_addstr(&p->parent[n].path,
113
				      q->queue[i]->one->path);
114

115
		tail = &p->next;
116
		i++;
117
	}
118
	return curr;
119
}
120

121
/* Lines lost from parent */
122
struct lline {
123
	struct lline *next, *prev;
124
	int len;
125
	unsigned long parent_map;
126
	char line[FLEX_ARRAY];
127
};
128

129
/* Lines lost from current parent (before coalescing) */
130
struct plost {
131
	struct lline *lost_head, *lost_tail;
132
	int len;
133
};
134

135
/* Lines surviving in the merge result */
136
struct sline {
137
	/* Accumulated and coalesced lost lines */
138
	struct lline *lost;
139
	int lenlost;
140
	struct plost plost;
141
	char *bol;
142
	int len;
143
	/* bit 0 up to (N-1) are on if the parent has this line (i.e.
144
	 * we did not change it).
145
	 * bit N is used for "interesting" lines, including context.
146
	 * bit (N+1) is used for "do not show deletion before this".
147
	 */
148
	unsigned long flag;
149
	unsigned long *p_lno;
150
};
151

152
static int match_string_spaces(const char *line1, int len1,
153
			       const char *line2, int len2,
154
			       long flags)
155
{
156
	if (flags & XDF_WHITESPACE_FLAGS) {
157
		for (; len1 > 0 && XDL_ISSPACE(line1[len1 - 1]); len1--);
158
		for (; len2 > 0 && XDL_ISSPACE(line2[len2 - 1]); len2--);
159
	}
160

161
	if (!(flags & (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE)))
162
		return (len1 == len2 && !memcmp(line1, line2, len1));
163

164
	while (len1 > 0 && len2 > 0) {
165
		len1--;
166
		len2--;
167
		if (XDL_ISSPACE(line1[len1]) || XDL_ISSPACE(line2[len2])) {
168
			if ((flags & XDF_IGNORE_WHITESPACE_CHANGE) &&
169
			    (!XDL_ISSPACE(line1[len1]) || !XDL_ISSPACE(line2[len2])))
170
				return 0;
171

172
			for (; len1 > 0 && XDL_ISSPACE(line1[len1]); len1--);
173
			for (; len2 > 0 && XDL_ISSPACE(line2[len2]); len2--);
174
		}
175
		if (line1[len1] != line2[len2])
176
			return 0;
177
	}
178

179
	if (flags & XDF_IGNORE_WHITESPACE) {
180
		/* Consume remaining spaces */
181
		for (; len1 > 0 && XDL_ISSPACE(line1[len1 - 1]); len1--);
182
		for (; len2 > 0 && XDL_ISSPACE(line2[len2 - 1]); len2--);
183
	}
184

185
	/* We matched full line1 and line2 */
186
	if (!len1 && !len2)
187
		return 1;
188

189
	return 0;
190
}
191

192
enum coalesce_direction { MATCH, BASE, NEW };
193

194
/* Coalesce new lines into base by finding LCS */
195
static struct lline *coalesce_lines(struct lline *base, int *lenbase,
196
				    struct lline *newline, int lennew,
197
				    unsigned long parent, long flags)
198
{
199
	int **lcs;
200
	enum coalesce_direction **directions;
201
	struct lline *baseend, *newend = NULL;
202
	int i, j, origbaselen = *lenbase;
203

204
	if (!newline)
205
		return base;
206

207
	if (!base) {
208
		*lenbase = lennew;
209
		return newline;
210
	}
211

212
	/*
213
	 * Coalesce new lines into base by finding the LCS
214
	 * - Create the table to run dynamic programming
215
	 * - Compute the LCS
216
	 * - Then reverse read the direction structure:
217
	 *   - If we have MATCH, assign parent to base flag, and consume
218
	 *   both baseend and newend
219
	 *   - Else if we have BASE, consume baseend
220
	 *   - Else if we have NEW, insert newend lline into base and
221
	 *   consume newend
222
	 */
223
	CALLOC_ARRAY(lcs, st_add(origbaselen, 1));
224
	CALLOC_ARRAY(directions, st_add(origbaselen, 1));
225
	for (i = 0; i < origbaselen + 1; i++) {
226
		CALLOC_ARRAY(lcs[i], st_add(lennew, 1));
227
		CALLOC_ARRAY(directions[i], st_add(lennew, 1));
228
		directions[i][0] = BASE;
229
	}
230
	for (j = 1; j < lennew + 1; j++)
231
		directions[0][j] = NEW;
232

233
	for (i = 1, baseend = base; i < origbaselen + 1; i++) {
234
		for (j = 1, newend = newline; j < lennew + 1; j++) {
235
			if (match_string_spaces(baseend->line, baseend->len,
236
						newend->line, newend->len, flags)) {
237
				lcs[i][j] = lcs[i - 1][j - 1] + 1;
238
				directions[i][j] = MATCH;
239
			} else if (lcs[i][j - 1] >= lcs[i - 1][j]) {
240
				lcs[i][j] = lcs[i][j - 1];
241
				directions[i][j] = NEW;
242
			} else {
243
				lcs[i][j] = lcs[i - 1][j];
244
				directions[i][j] = BASE;
245
			}
246
			if (newend->next)
247
				newend = newend->next;
248
		}
249
		if (baseend->next)
250
			baseend = baseend->next;
251
	}
252

253
	for (i = 0; i < origbaselen + 1; i++)
254
		free(lcs[i]);
255
	free(lcs);
256

257
	/* At this point, baseend and newend point to the end of each lists */
258
	i--;
259
	j--;
260
	while (i != 0 || j != 0) {
261
		if (directions[i][j] == MATCH) {
262
			baseend->parent_map |= 1<<parent;
263
			baseend = baseend->prev;
264
			newend = newend->prev;
265
			i--;
266
			j--;
267
		} else if (directions[i][j] == NEW) {
268
			struct lline *lline;
269

270
			lline = newend;
271
			/* Remove lline from new list and update newend */
272
			if (lline->prev)
273
				lline->prev->next = lline->next;
274
			else
275
				newline = lline->next;
276
			if (lline->next)
277
				lline->next->prev = lline->prev;
278

279
			newend = lline->prev;
280
			j--;
281

282
			/* Add lline to base list */
283
			if (baseend) {
284
				lline->next = baseend->next;
285
				lline->prev = baseend;
286
				if (lline->prev)
287
					lline->prev->next = lline;
288
			}
289
			else {
290
				lline->next = base;
291
				base = lline;
292
			}
293
			(*lenbase)++;
294

295
			if (lline->next)
296
				lline->next->prev = lline;
297

298
		} else {
299
			baseend = baseend->prev;
300
			i--;
301
		}
302
	}
303

304
	newend = newline;
305
	while (newend) {
306
		struct lline *lline = newend;
307
		newend = newend->next;
308
		free(lline);
309
	}
310

311
	for (i = 0; i < origbaselen + 1; i++)
312
		free(directions[i]);
313
	free(directions);
314

315
	return base;
316
}
317

318
static char *grab_blob(struct repository *r,
319
		       const struct object_id *oid, unsigned int mode,
320
		       unsigned long *size, struct userdiff_driver *textconv,
321
		       const char *path)
322
{
323
	char *blob;
324
	enum object_type type;
325

326
	if (S_ISGITLINK(mode)) {
327
		struct strbuf buf = STRBUF_INIT;
328
		strbuf_addf(&buf, "Subproject commit %s\n", oid_to_hex(oid));
329
		*size = buf.len;
330
		blob = strbuf_detach(&buf, NULL);
331
	} else if (is_null_oid(oid)) {
332
		/* deleted blob */
333
		*size = 0;
334
		return xcalloc(1, 1);
335
	} else if (textconv) {
336
		struct diff_filespec *df = alloc_filespec(path);
337
		fill_filespec(df, oid, 1, mode);
338
		*size = fill_textconv(r, textconv, df, &blob);
339
		free_filespec(df);
340
	} else {
341
		blob = repo_read_object_file(r, oid, &type, size);
342
		if (!blob)
343
			die(_("unable to read %s"), oid_to_hex(oid));
344
		if (type != OBJ_BLOB)
345
			die("object '%s' is not a blob!", oid_to_hex(oid));
346
	}
347
	return blob;
348
}
349

350
static void append_lost(struct sline *sline, int n, const char *line, int len)
351
{
352
	struct lline *lline;
353
	unsigned long this_mask = (1UL<<n);
354
	if (line[len-1] == '\n')
355
		len--;
356

357
	FLEX_ALLOC_MEM(lline, line, line, len);
358
	lline->len = len;
359
	lline->next = NULL;
360
	lline->prev = sline->plost.lost_tail;
361
	if (lline->prev)
362
		lline->prev->next = lline;
363
	else
364
		sline->plost.lost_head = lline;
365
	sline->plost.lost_tail = lline;
366
	sline->plost.len++;
367
	lline->parent_map = this_mask;
368
}
369

370
struct combine_diff_state {
371
	unsigned int lno;
372
	int ob, on, nb, nn;
373
	unsigned long nmask;
374
	int num_parent;
375
	int n;
376
	struct sline *sline;
377
	struct sline *lost_bucket;
378
};
379

380
static void consume_hunk(void *state_,
381
			 long ob, long on,
382
			 long nb, long nn,
383
			 const char *func UNUSED, long funclen UNUSED)
384
{
385
	struct combine_diff_state *state = state_;
386

387
	state->ob = ob;
388
	state->on = on;
389
	state->nb = nb;
390
	state->nn = nn;
391
	state->lno = state->nb;
392
	if (state->nn == 0) {
393
		/* @@ -X,Y +N,0 @@ removed Y lines
394
		 * that would have come *after* line N
395
		 * in the result.  Our lost buckets hang
396
		 * to the line after the removed lines,
397
		 *
398
		 * Note that this is correct even when N == 0,
399
		 * in which case the hunk removes the first
400
		 * line in the file.
401
		 */
402
		state->lost_bucket = &state->sline[state->nb];
403
		if (!state->nb)
404
			state->nb = 1;
405
	} else {
406
		state->lost_bucket = &state->sline[state->nb-1];
407
	}
408
	if (!state->sline[state->nb-1].p_lno)
409
		CALLOC_ARRAY(state->sline[state->nb - 1].p_lno,
410
			     state->num_parent);
411
	state->sline[state->nb-1].p_lno[state->n] = state->ob;
412
}
413

414
static int consume_line(void *state_, char *line, unsigned long len)
415
{
416
	struct combine_diff_state *state = state_;
417
	if (!state->lost_bucket)
418
		return 0; /* not in any hunk yet */
419
	switch (line[0]) {
420
	case '-':
421
		append_lost(state->lost_bucket, state->n, line+1, len-1);
422
		break;
423
	case '+':
424
		state->sline[state->lno-1].flag |= state->nmask;
425
		state->lno++;
426
		break;
427
	}
428
	return 0;
429
}
430

431
static void combine_diff(struct repository *r,
432
			 const struct object_id *parent, unsigned int mode,
433
			 mmfile_t *result_file,
434
			 struct sline *sline, unsigned int cnt, int n,
435
			 int num_parent, int result_deleted,
436
			 struct userdiff_driver *textconv,
437
			 const char *path, long flags)
438
{
439
	unsigned int p_lno, lno;
440
	unsigned long nmask = (1UL << n);
441
	xpparam_t xpp;
442
	xdemitconf_t xecfg;
443
	mmfile_t parent_file;
444
	struct combine_diff_state state;
445
	unsigned long sz;
446

447
	if (result_deleted)
448
		return; /* result deleted */
449

450
	parent_file.ptr = grab_blob(r, parent, mode, &sz, textconv, path);
451
	parent_file.size = sz;
452
	memset(&xpp, 0, sizeof(xpp));
453
	xpp.flags = flags;
454
	memset(&xecfg, 0, sizeof(xecfg));
455
	memset(&state, 0, sizeof(state));
456
	state.nmask = nmask;
457
	state.sline = sline;
458
	state.lno = 1;
459
	state.num_parent = num_parent;
460
	state.n = n;
461

462
	if (xdi_diff_outf(&parent_file, result_file, consume_hunk,
463
			  consume_line, &state, &xpp, &xecfg))
464
		die("unable to generate combined diff for %s",
465
		    oid_to_hex(parent));
466
	free(parent_file.ptr);
467

468
	/* Assign line numbers for this parent.
469
	 *
470
	 * sline[lno].p_lno[n] records the first line number
471
	 * (counting from 1) for parent N if the final hunk display
472
	 * started by showing sline[lno] (possibly showing the lost
473
	 * lines attached to it first).
474
	 */
475
	for (lno = 0,  p_lno = 1; lno <= cnt; lno++) {
476
		struct lline *ll;
477
		sline[lno].p_lno[n] = p_lno;
478

479
		/* Coalesce new lines */
480
		if (sline[lno].plost.lost_head) {
481
			struct sline *sl = &sline[lno];
482
			sl->lost = coalesce_lines(sl->lost, &sl->lenlost,
483
						  sl->plost.lost_head,
484
						  sl->plost.len, n, flags);
485
			sl->plost.lost_head = sl->plost.lost_tail = NULL;
486
			sl->plost.len = 0;
487
		}
488

489
		/* How many lines would this sline advance the p_lno? */
490
		ll = sline[lno].lost;
491
		while (ll) {
492
			if (ll->parent_map & nmask)
493
				p_lno++; /* '-' means parent had it */
494
			ll = ll->next;
495
		}
496
		if (lno < cnt && !(sline[lno].flag & nmask))
497
			p_lno++; /* no '+' means parent had it */
498
	}
499
	sline[lno].p_lno[n] = p_lno; /* trailer */
500
}
501

502
static unsigned long context = 3;
503
static char combine_marker = '@';
504

505
static int interesting(struct sline *sline, unsigned long all_mask)
506
{
507
	/* If some parents lost lines here, or if we have added to
508
	 * some parent, it is interesting.
509
	 */
510
	return ((sline->flag & all_mask) || sline->lost);
511
}
512

513
static unsigned long adjust_hunk_tail(struct sline *sline,
514
				      unsigned long all_mask,
515
				      unsigned long hunk_begin,
516
				      unsigned long i)
517
{
518
	/* i points at the first uninteresting line.  If the last line
519
	 * of the hunk was interesting only because it has some
520
	 * deletion, then it is not all that interesting for the
521
	 * purpose of giving trailing context lines.  This is because
522
	 * we output '-' line and then unmodified sline[i-1] itself in
523
	 * that case which gives us one extra context line.
524
	 */
525
	if ((hunk_begin + 1 <= i) && !(sline[i-1].flag & all_mask))
526
		i--;
527
	return i;
528
}
529

530
static unsigned long find_next(struct sline *sline,
531
			       unsigned long mark,
532
			       unsigned long i,
533
			       unsigned long cnt,
534
			       int look_for_uninteresting)
535
{
536
	/* We have examined up to i-1 and are about to look at i.
537
	 * Find next interesting or uninteresting line.  Here,
538
	 * "interesting" does not mean interesting(), but marked by
539
	 * the give_context() function below (i.e. it includes context
540
	 * lines that are not interesting to interesting() function
541
	 * that are surrounded by interesting() ones.
542
	 */
543
	while (i <= cnt)
544
		if (look_for_uninteresting
545
		    ? !(sline[i].flag & mark)
546
		    : (sline[i].flag & mark))
547
			return i;
548
		else
549
			i++;
550
	return i;
551
}
552

553
static int give_context(struct sline *sline, unsigned long cnt, int num_parent)
554
{
555
	unsigned long all_mask = (1UL<<num_parent) - 1;
556
	unsigned long mark = (1UL<<num_parent);
557
	unsigned long no_pre_delete = (2UL<<num_parent);
558
	unsigned long i;
559

560
	/* Two groups of interesting lines may have a short gap of
561
	 * uninteresting lines.  Connect such groups to give them a
562
	 * bit of context.
563
	 *
564
	 * We first start from what the interesting() function says,
565
	 * and mark them with "mark", and paint context lines with the
566
	 * mark.  So interesting() would still say false for such context
567
	 * lines but they are treated as "interesting" in the end.
568
	 */
569
	i = find_next(sline, mark, 0, cnt, 0);
570
	if (cnt < i)
571
		return 0;
572

573
	while (i <= cnt) {
574
		unsigned long j = (context < i) ? (i - context) : 0;
575
		unsigned long k;
576

577
		/* Paint a few lines before the first interesting line. */
578
		while (j < i) {
579
			if (!(sline[j].flag & mark))
580
				sline[j].flag |= no_pre_delete;
581
			sline[j++].flag |= mark;
582
		}
583

584
	again:
585
		/* we know up to i is to be included.  where does the
586
		 * next uninteresting one start?
587
		 */
588
		j = find_next(sline, mark, i, cnt, 1);
589
		if (cnt < j)
590
			break; /* the rest are all interesting */
591

592
		/* lookahead context lines */
593
		k = find_next(sline, mark, j, cnt, 0);
594
		j = adjust_hunk_tail(sline, all_mask, i, j);
595

596
		if (k < j + context) {
597
			/* k is interesting and [j,k) are not, but
598
			 * paint them interesting because the gap is small.
599
			 */
600
			while (j < k)
601
				sline[j++].flag |= mark;
602
			i = k;
603
			goto again;
604
		}
605

606
		/* j is the first uninteresting line and there is
607
		 * no overlap beyond it within context lines.  Paint
608
		 * the trailing edge a bit.
609
		 */
610
		i = k;
611
		k = (j + context < cnt+1) ? j + context : cnt+1;
612
		while (j < k)
613
			sline[j++].flag |= mark;
614
	}
615
	return 1;
616
}
617

618
static int make_hunks(struct sline *sline, unsigned long cnt,
619
		       int num_parent, int dense)
620
{
621
	unsigned long all_mask = (1UL<<num_parent) - 1;
622
	unsigned long mark = (1UL<<num_parent);
623
	unsigned long i;
624
	int has_interesting = 0;
625

626
	for (i = 0; i <= cnt; i++) {
627
		if (interesting(&sline[i], all_mask))
628
			sline[i].flag |= mark;
629
		else
630
			sline[i].flag &= ~mark;
631
	}
632
	if (!dense)
633
		return give_context(sline, cnt, num_parent);
634

635
	/* Look at each hunk, and if we have changes from only one
636
	 * parent, or the changes are the same from all but one
637
	 * parent, mark that uninteresting.
638
	 */
639
	i = 0;
640
	while (i <= cnt) {
641
		unsigned long j, hunk_begin, hunk_end;
642
		unsigned long same_diff;
643
		while (i <= cnt && !(sline[i].flag & mark))
644
			i++;
645
		if (cnt < i)
646
			break; /* No more interesting hunks */
647
		hunk_begin = i;
648
		for (j = i + 1; j <= cnt; j++) {
649
			if (!(sline[j].flag & mark)) {
650
				/* Look beyond the end to see if there
651
				 * is an interesting line after this
652
				 * hunk within context span.
653
				 */
654
				unsigned long la; /* lookahead */
655
				int contin = 0;
656
				la = adjust_hunk_tail(sline, all_mask,
657
						     hunk_begin, j);
658
				la = (la + context < cnt + 1) ?
659
					(la + context) : cnt + 1;
660
				while (la && j <= --la) {
661
					if (sline[la].flag & mark) {
662
						contin = 1;
663
						break;
664
					}
665
				}
666
				if (!contin)
667
					break;
668
				j = la;
669
			}
670
		}
671
		hunk_end = j;
672

673
		/* [i..hunk_end) are interesting.  Now is it really
674
		 * interesting?  We check if there are only two versions
675
		 * and the result matches one of them.  That is, we look
676
		 * at:
677
		 *   (+) line, which records lines added to which parents;
678
		 *       this line appears in the result.
679
		 *   (-) line, which records from what parents the line
680
		 *       was removed; this line does not appear in the result.
681
		 * then check the set of parents the result has difference
682
		 * from, from all lines.  If there are lines that has
683
		 * different set of parents that the result has differences
684
		 * from, that means we have more than two versions.
685
		 *
686
		 * Even when we have only two versions, if the result does
687
		 * not match any of the parents, the it should be considered
688
		 * interesting.  In such a case, we would have all '+' line.
689
		 * After passing the above "two versions" test, that would
690
		 * appear as "the same set of parents" to be "all parents".
691
		 */
692
		same_diff = 0;
693
		has_interesting = 0;
694
		for (j = i; j < hunk_end && !has_interesting; j++) {
695
			unsigned long this_diff = sline[j].flag & all_mask;
696
			struct lline *ll = sline[j].lost;
697
			if (this_diff) {
698
				/* This has some changes.  Is it the
699
				 * same as others?
700
				 */
701
				if (!same_diff)
702
					same_diff = this_diff;
703
				else if (same_diff != this_diff) {
704
					has_interesting = 1;
705
					break;
706
				}
707
			}
708
			while (ll && !has_interesting) {
709
				/* Lost this line from these parents;
710
				 * who are they?  Are they the same?
711
				 */
712
				this_diff = ll->parent_map;
713
				if (!same_diff)
714
					same_diff = this_diff;
715
				else if (same_diff != this_diff) {
716
					has_interesting = 1;
717
				}
718
				ll = ll->next;
719
			}
720
		}
721

722
		if (!has_interesting && same_diff != all_mask) {
723
			/* This hunk is not that interesting after all */
724
			for (j = hunk_begin; j < hunk_end; j++)
725
				sline[j].flag &= ~mark;
726
		}
727
		i = hunk_end;
728
	}
729

730
	has_interesting = give_context(sline, cnt, num_parent);
731
	return has_interesting;
732
}
733

734
static void show_parent_lno(struct sline *sline, unsigned long l0, unsigned long l1, int n, unsigned long null_context)
735
{
736
	l0 = sline[l0].p_lno[n];
737
	l1 = sline[l1].p_lno[n];
738
	printf(" -%lu,%lu", l0, l1-l0-null_context);
739
}
740

741
static int hunk_comment_line(const char *bol)
742
{
743
	int ch;
744

745
	if (!bol)
746
		return 0;
747
	ch = *bol & 0xff;
748
	return (isalpha(ch) || ch == '_' || ch == '$');
749
}
750

751
static void show_line_to_eol(const char *line, int len, const char *reset)
752
{
753
	int saw_cr_at_eol = 0;
754
	if (len < 0)
755
		len = strlen(line);
756
	saw_cr_at_eol = (len && line[len-1] == '\r');
757

758
	printf("%.*s%s%s\n", len - saw_cr_at_eol, line,
759
	       reset,
760
	       saw_cr_at_eol ? "\r" : "");
761
}
762

763
static void dump_sline(struct sline *sline, const char *line_prefix,
764
		       unsigned long cnt, int num_parent,
765
		       int use_color, int result_deleted)
766
{
767
	unsigned long mark = (1UL<<num_parent);
768
	unsigned long no_pre_delete = (2UL<<num_parent);
769
	int i;
770
	unsigned long lno = 0;
771
	const char *c_frag = diff_get_color(use_color, DIFF_FRAGINFO);
772
	const char *c_func = diff_get_color(use_color, DIFF_FUNCINFO);
773
	const char *c_new = diff_get_color(use_color, DIFF_FILE_NEW);
774
	const char *c_old = diff_get_color(use_color, DIFF_FILE_OLD);
775
	const char *c_context = diff_get_color(use_color, DIFF_CONTEXT);
776
	const char *c_reset = diff_get_color(use_color, DIFF_RESET);
777

778
	if (result_deleted)
779
		return; /* result deleted */
780

781
	while (1) {
782
		unsigned long hunk_end;
783
		unsigned long rlines;
784
		const char *hunk_comment = NULL;
785
		unsigned long null_context = 0;
786

787
		while (lno <= cnt && !(sline[lno].flag & mark)) {
788
			if (hunk_comment_line(sline[lno].bol))
789
				hunk_comment = sline[lno].bol;
790
			lno++;
791
		}
792
		if (cnt < lno)
793
			break;
794
		else {
795
			for (hunk_end = lno + 1; hunk_end <= cnt; hunk_end++)
796
				if (!(sline[hunk_end].flag & mark))
797
					break;
798
		}
799
		rlines = hunk_end - lno;
800
		if (cnt < hunk_end)
801
			rlines--; /* pointing at the last delete hunk */
802

803
		if (!context) {
804
			/*
805
			 * Even when running with --unified=0, all
806
			 * lines in the hunk needs to be processed in
807
			 * the loop below in order to show the
808
			 * deletion recorded in lost_head.  However,
809
			 * we do not want to show the resulting line
810
			 * with all blank context markers in such a
811
			 * case.  Compensate.
812
			 */
813
			unsigned long j;
814
			for (j = lno; j < hunk_end; j++)
815
				if (!(sline[j].flag & (mark-1)))
816
					null_context++;
817
			rlines -= null_context;
818
		}
819

820
		printf("%s%s", line_prefix, c_frag);
821
		for (i = 0; i <= num_parent; i++) putchar(combine_marker);
822
		for (i = 0; i < num_parent; i++)
823
			show_parent_lno(sline, lno, hunk_end, i, null_context);
824
		printf(" +%lu,%lu ", lno+1, rlines);
825
		for (i = 0; i <= num_parent; i++) putchar(combine_marker);
826

827
		if (hunk_comment) {
828
			int comment_end = 0;
829
			for (i = 0; i < 40; i++) {
830
				int ch = hunk_comment[i] & 0xff;
831
				if (!ch || ch == '\n')
832
					break;
833
				if (!isspace(ch))
834
				    comment_end = i;
835
			}
836
			if (comment_end)
837
				printf("%s%s %s%s", c_reset,
838
						    c_context, c_reset,
839
						    c_func);
840
			for (i = 0; i < comment_end; i++)
841
				putchar(hunk_comment[i]);
842
		}
843

844
		printf("%s\n", c_reset);
845
		while (lno < hunk_end) {
846
			struct lline *ll;
847
			int j;
848
			unsigned long p_mask;
849
			struct sline *sl = &sline[lno++];
850
			ll = (sl->flag & no_pre_delete) ? NULL : sl->lost;
851
			while (ll) {
852
				printf("%s%s", line_prefix, c_old);
853
				for (j = 0; j < num_parent; j++) {
854
					if (ll->parent_map & (1UL<<j))
855
						putchar('-');
856
					else
857
						putchar(' ');
858
				}
859
				show_line_to_eol(ll->line, -1, c_reset);
860
				ll = ll->next;
861
			}
862
			if (cnt < lno)
863
				break;
864
			p_mask = 1;
865
			fputs(line_prefix, stdout);
866
			if (!(sl->flag & (mark-1))) {
867
				/*
868
				 * This sline was here to hang the
869
				 * lost lines in front of it.
870
				 */
871
				if (!context)
872
					continue;
873
				fputs(c_context, stdout);
874
			}
875
			else
876
				fputs(c_new, stdout);
877
			for (j = 0; j < num_parent; j++) {
878
				if (p_mask & sl->flag)
879
					putchar('+');
880
				else
881
					putchar(' ');
882
				p_mask <<= 1;
883
			}
884
			show_line_to_eol(sl->bol, sl->len, c_reset);
885
		}
886
	}
887
}
888

889
static void reuse_combine_diff(struct sline *sline, unsigned long cnt,
890
			       int i, int j)
891
{
892
	/* We have already examined parent j and we know parent i
893
	 * and parent j are the same, so reuse the combined result
894
	 * of parent j for parent i.
895
	 */
896
	unsigned long lno, imask, jmask;
897
	imask = (1UL<<i);
898
	jmask = (1UL<<j);
899

900
	for (lno = 0; lno <= cnt; lno++) {
901
		struct lline *ll = sline->lost;
902
		sline->p_lno[i] = sline->p_lno[j];
903
		while (ll) {
904
			if (ll->parent_map & jmask)
905
				ll->parent_map |= imask;
906
			ll = ll->next;
907
		}
908
		if (sline->flag & jmask)
909
			sline->flag |= imask;
910
		sline++;
911
	}
912
	/* the overall size of the file (sline[cnt]) */
913
	sline->p_lno[i] = sline->p_lno[j];
914
}
915

916
static void dump_quoted_path(const char *head,
917
			     const char *prefix,
918
			     const char *path,
919
			     const char *line_prefix,
920
			     const char *c_meta, const char *c_reset)
921
{
922
	static struct strbuf buf = STRBUF_INIT;
923

924
	strbuf_reset(&buf);
925
	strbuf_addstr(&buf, line_prefix);
926
	strbuf_addstr(&buf, c_meta);
927
	strbuf_addstr(&buf, head);
928
	quote_two_c_style(&buf, prefix, path, 0);
929
	strbuf_addstr(&buf, c_reset);
930
	puts(buf.buf);
931
}
932

933
static void show_combined_header(struct combine_diff_path *elem,
934
				 int num_parent,
935
				 struct rev_info *rev,
936
				 const char *line_prefix,
937
				 int mode_differs,
938
				 int show_file_header)
939
{
940
	struct diff_options *opt = &rev->diffopt;
941
	int abbrev = opt->flags.full_index ? the_hash_algo->hexsz : DEFAULT_ABBREV;
942
	const char *a_prefix = opt->a_prefix ? opt->a_prefix : "a/";
943
	const char *b_prefix = opt->b_prefix ? opt->b_prefix : "b/";
944
	const char *c_meta = diff_get_color_opt(opt, DIFF_METAINFO);
945
	const char *c_reset = diff_get_color_opt(opt, DIFF_RESET);
946
	const char *abb;
947
	int added = 0;
948
	int deleted = 0;
949
	int i;
950
	int dense = rev->dense_combined_merges;
951

952
	if (rev->loginfo && !rev->no_commit_id)
953
		show_log(rev);
954

955
	dump_quoted_path(dense ? "diff --cc " : "diff --combined ",
956
			 "", elem->path, line_prefix, c_meta, c_reset);
957
	printf("%s%sindex ", line_prefix, c_meta);
958
	for (i = 0; i < num_parent; i++) {
959
		abb = repo_find_unique_abbrev(the_repository,
960
					      &elem->parent[i].oid, abbrev);
961
		printf("%s%s", i ? "," : "", abb);
962
	}
963
	abb = repo_find_unique_abbrev(the_repository, &elem->oid, abbrev);
964
	printf("..%s%s\n", abb, c_reset);
965

966
	if (mode_differs) {
967
		deleted = !elem->mode;
968

969
		/* We say it was added if nobody had it */
970
		added = !deleted;
971
		for (i = 0; added && i < num_parent; i++)
972
			if (elem->parent[i].status !=
973
			    DIFF_STATUS_ADDED)
974
				added = 0;
975
		if (added)
976
			printf("%s%snew file mode %06o",
977
			       line_prefix, c_meta, elem->mode);
978
		else {
979
			if (deleted)
980
				printf("%s%sdeleted file ",
981
				       line_prefix, c_meta);
982
			printf("mode ");
983
			for (i = 0; i < num_parent; i++) {
984
				printf("%s%06o", i ? "," : "",
985
				       elem->parent[i].mode);
986
			}
987
			if (elem->mode)
988
				printf("..%06o", elem->mode);
989
		}
990
		printf("%s\n", c_reset);
991
	}
992

993
	if (!show_file_header)
994
		return;
995

996
	if (rev->combined_all_paths) {
997
		for (i = 0; i < num_parent; i++) {
998
			char *path = filename_changed(elem->parent[i].status)
999
				? elem->parent[i].path.buf : elem->path;
1000
			if (elem->parent[i].status == DIFF_STATUS_ADDED)
1001
				dump_quoted_path("--- ", "", "/dev/null",
1002
						 line_prefix, c_meta, c_reset);
1003
			else
1004
				dump_quoted_path("--- ", a_prefix, path,
1005
						 line_prefix, c_meta, c_reset);
1006
		}
1007
	} else {
1008
		if (added)
1009
			dump_quoted_path("--- ", "", "/dev/null",
1010
					 line_prefix, c_meta, c_reset);
1011
		else
1012
			dump_quoted_path("--- ", a_prefix, elem->path,
1013
					 line_prefix, c_meta, c_reset);
1014
	}
1015
	if (deleted)
1016
		dump_quoted_path("+++ ", "", "/dev/null",
1017
				 line_prefix, c_meta, c_reset);
1018
	else
1019
		dump_quoted_path("+++ ", b_prefix, elem->path,
1020
				 line_prefix, c_meta, c_reset);
1021
}
1022

1023
static void show_patch_diff(struct combine_diff_path *elem, int num_parent,
1024
			    int working_tree_file,
1025
			    struct rev_info *rev)
1026
{
1027
	struct diff_options *opt = &rev->diffopt;
1028
	unsigned long result_size, cnt, lno;
1029
	int result_deleted = 0;
1030
	char *result, *cp;
1031
	struct sline *sline; /* survived lines */
1032
	int mode_differs = 0;
1033
	int i, show_hunks;
1034
	mmfile_t result_file;
1035
	struct userdiff_driver *userdiff;
1036
	struct userdiff_driver *textconv = NULL;
1037
	int is_binary;
1038
	const char *line_prefix = diff_line_prefix(opt);
1039

1040
	context = opt->context;
1041
	userdiff = userdiff_find_by_path(opt->repo->index, elem->path);
1042
	if (!userdiff)
1043
		userdiff = userdiff_find_by_name("default");
1044
	if (opt->flags.allow_textconv)
1045
		textconv = userdiff_get_textconv(opt->repo, userdiff);
1046

1047
	/* Read the result of merge first */
1048
	if (!working_tree_file)
1049
		result = grab_blob(opt->repo, &elem->oid, elem->mode, &result_size,
1050
				   textconv, elem->path);
1051
	else {
1052
		/* Used by diff-tree to read from the working tree */
1053
		struct stat st;
1054
		int fd = -1;
1055

1056
		if (lstat(elem->path, &st) < 0)
1057
			goto deleted_file;
1058

1059
		if (S_ISLNK(st.st_mode)) {
1060
			struct strbuf buf = STRBUF_INIT;
1061

1062
			if (strbuf_readlink(&buf, elem->path, st.st_size) < 0) {
1063
				error_errno("readlink(%s)", elem->path);
1064
				return;
1065
			}
1066
			result_size = buf.len;
1067
			result = strbuf_detach(&buf, NULL);
1068
			elem->mode = canon_mode(st.st_mode);
1069
		} else if (S_ISDIR(st.st_mode)) {
1070
			struct object_id oid;
1071
			if (repo_resolve_gitlink_ref(the_repository, elem->path,
1072
						     "HEAD", &oid) < 0)
1073
				result = grab_blob(opt->repo, &elem->oid,
1074
						   elem->mode, &result_size,
1075
						   NULL, NULL);
1076
			else
1077
				result = grab_blob(opt->repo, &oid, elem->mode,
1078
						   &result_size, NULL, NULL);
1079
		} else if (textconv) {
1080
			struct diff_filespec *df = alloc_filespec(elem->path);
1081
			fill_filespec(df, null_oid(), 0, st.st_mode);
1082
			result_size = fill_textconv(opt->repo, textconv, df, &result);
1083
			free_filespec(df);
1084
		} else if (0 <= (fd = open(elem->path, O_RDONLY))) {
1085
			size_t len = xsize_t(st.st_size);
1086
			ssize_t done;
1087
			int is_file, i;
1088

1089
			elem->mode = canon_mode(st.st_mode);
1090
			/* if symlinks don't work, assume symlink if all parents
1091
			 * are symlinks
1092
			 */
1093
			is_file = has_symlinks;
1094
			for (i = 0; !is_file && i < num_parent; i++)
1095
				is_file = !S_ISLNK(elem->parent[i].mode);
1096
			if (!is_file)
1097
				elem->mode = canon_mode(S_IFLNK);
1098

1099
			result_size = len;
1100
			result = xmallocz(len);
1101

1102
			done = read_in_full(fd, result, len);
1103
			if (done < 0)
1104
				die_errno("read error '%s'", elem->path);
1105
			else if (done < len)
1106
				die("early EOF '%s'", elem->path);
1107

1108
			/* If not a fake symlink, apply filters, e.g. autocrlf */
1109
			if (is_file) {
1110
				struct strbuf buf = STRBUF_INIT;
1111

1112
				if (convert_to_git(rev->diffopt.repo->index,
1113
						   elem->path, result, len, &buf, global_conv_flags_eol)) {
1114
					free(result);
1115
					result = strbuf_detach(&buf, &len);
1116
					result_size = len;
1117
				}
1118
			}
1119
		}
1120
		else {
1121
		deleted_file:
1122
			result_deleted = 1;
1123
			result_size = 0;
1124
			elem->mode = 0;
1125
			result = xcalloc(1, 1);
1126
		}
1127

1128
		if (0 <= fd)
1129
			close(fd);
1130
	}
1131

1132
	for (i = 0; i < num_parent; i++) {
1133
		if (elem->parent[i].mode != elem->mode) {
1134
			mode_differs = 1;
1135
			break;
1136
		}
1137
	}
1138

1139
	if (textconv)
1140
		is_binary = 0;
1141
	else if (userdiff->binary != -1)
1142
		is_binary = userdiff->binary;
1143
	else {
1144
		is_binary = buffer_is_binary(result, result_size);
1145
		for (i = 0; !is_binary && i < num_parent; i++) {
1146
			char *buf;
1147
			unsigned long size;
1148
			buf = grab_blob(opt->repo,
1149
					&elem->parent[i].oid,
1150
					elem->parent[i].mode,
1151
					&size, NULL, NULL);
1152
			if (buffer_is_binary(buf, size))
1153
				is_binary = 1;
1154
			free(buf);
1155
		}
1156
	}
1157
	if (is_binary) {
1158
		show_combined_header(elem, num_parent, rev,
1159
				     line_prefix, mode_differs, 0);
1160
		printf("Binary files differ\n");
1161
		free(result);
1162
		return;
1163
	}
1164

1165
	for (cnt = 0, cp = result; cp < result + result_size; cp++) {
1166
		if (*cp == '\n')
1167
			cnt++;
1168
	}
1169
	if (result_size && result[result_size-1] != '\n')
1170
		cnt++; /* incomplete line */
1171

1172
	CALLOC_ARRAY(sline, st_add(cnt, 2));
1173
	sline[0].bol = result;
1174
	for (lno = 0, cp = result; cp < result + result_size; cp++) {
1175
		if (*cp == '\n') {
1176
			sline[lno].len = cp - sline[lno].bol;
1177
			lno++;
1178
			if (lno < cnt)
1179
				sline[lno].bol = cp + 1;
1180
		}
1181
	}
1182
	if (result_size && result[result_size-1] != '\n')
1183
		sline[cnt-1].len = result_size - (sline[cnt-1].bol - result);
1184

1185
	result_file.ptr = result;
1186
	result_file.size = result_size;
1187

1188
	/* Even p_lno[cnt+1] is valid -- that is for the end line number
1189
	 * for deletion hunk at the end.
1190
	 */
1191
	CALLOC_ARRAY(sline[0].p_lno, st_mult(st_add(cnt, 2), num_parent));
1192
	for (lno = 0; lno <= cnt; lno++)
1193
		sline[lno+1].p_lno = sline[lno].p_lno + num_parent;
1194

1195
	for (i = 0; i < num_parent; i++) {
1196
		int j;
1197
		for (j = 0; j < i; j++) {
1198
			if (oideq(&elem->parent[i].oid,
1199
				  &elem->parent[j].oid)) {
1200
				reuse_combine_diff(sline, cnt, i, j);
1201
				break;
1202
			}
1203
		}
1204
		if (i <= j)
1205
			combine_diff(opt->repo,
1206
				     &elem->parent[i].oid,
1207
				     elem->parent[i].mode,
1208
				     &result_file, sline,
1209
				     cnt, i, num_parent, result_deleted,
1210
				     textconv, elem->path, opt->xdl_opts);
1211
	}
1212

1213
	show_hunks = make_hunks(sline, cnt, num_parent, rev->dense_combined_merges);
1214

1215
	if (show_hunks || mode_differs || working_tree_file) {
1216
		show_combined_header(elem, num_parent, rev,
1217
				     line_prefix, mode_differs, 1);
1218
		dump_sline(sline, line_prefix, cnt, num_parent,
1219
			   opt->use_color, result_deleted);
1220
	}
1221
	free(result);
1222

1223
	for (lno = 0; lno < cnt; lno++) {
1224
		if (sline[lno].lost) {
1225
			struct lline *ll = sline[lno].lost;
1226
			while (ll) {
1227
				struct lline *tmp = ll;
1228
				ll = ll->next;
1229
				free(tmp);
1230
			}
1231
		}
1232
	}
1233
	free(sline[0].p_lno);
1234
	free(sline);
1235
}
1236

1237
static void show_raw_diff(struct combine_diff_path *p, int num_parent, struct rev_info *rev)
1238
{
1239
	struct diff_options *opt = &rev->diffopt;
1240
	int line_termination, inter_name_termination, i;
1241
	const char *line_prefix = diff_line_prefix(opt);
1242

1243
	line_termination = opt->line_termination;
1244
	inter_name_termination = '\t';
1245
	if (!line_termination)
1246
		inter_name_termination = 0;
1247

1248
	if (rev->loginfo && !rev->no_commit_id)
1249
		show_log(rev);
1250

1251

1252
	if (opt->output_format & DIFF_FORMAT_RAW) {
1253
		printf("%s", line_prefix);
1254

1255
		/* As many colons as there are parents */
1256
		for (i = 0; i < num_parent; i++)
1257
			putchar(':');
1258

1259
		/* Show the modes */
1260
		for (i = 0; i < num_parent; i++)
1261
			printf("%06o ", p->parent[i].mode);
1262
		printf("%06o", p->mode);
1263

1264
		/* Show sha1's */
1265
		for (i = 0; i < num_parent; i++)
1266
			printf(" %s", diff_aligned_abbrev(&p->parent[i].oid,
1267
							  opt->abbrev));
1268
		printf(" %s ", diff_aligned_abbrev(&p->oid, opt->abbrev));
1269
	}
1270

1271
	if (opt->output_format & (DIFF_FORMAT_RAW | DIFF_FORMAT_NAME_STATUS)) {
1272
		for (i = 0; i < num_parent; i++)
1273
			putchar(p->parent[i].status);
1274
		putchar(inter_name_termination);
1275
	}
1276

1277
	for (i = 0; i < num_parent; i++)
1278
		if (rev->combined_all_paths) {
1279
			if (filename_changed(p->parent[i].status))
1280
				write_name_quoted(p->parent[i].path.buf, stdout,
1281
						  inter_name_termination);
1282
			else
1283
				write_name_quoted(p->path, stdout,
1284
						  inter_name_termination);
1285
		}
1286
	write_name_quoted(p->path, stdout, line_termination);
1287
}
1288

1289
/*
1290
 * The result (p->elem) is from the working tree and their
1291
 * parents are typically from multiple stages during a merge
1292
 * (i.e. diff-files) or the state in HEAD and in the index
1293
 * (i.e. diff-index).
1294
 */
1295
void show_combined_diff(struct combine_diff_path *p,
1296
		       int num_parent,
1297
		       struct rev_info *rev)
1298
{
1299
	struct diff_options *opt = &rev->diffopt;
1300

1301
	if (opt->output_format & (DIFF_FORMAT_RAW |
1302
				  DIFF_FORMAT_NAME |
1303
				  DIFF_FORMAT_NAME_STATUS))
1304
		show_raw_diff(p, num_parent, rev);
1305
	else if (opt->output_format & DIFF_FORMAT_PATCH)
1306
		show_patch_diff(p, num_parent, 1, rev);
1307
}
1308

1309
static void free_combined_pair(struct diff_filepair *pair)
1310
{
1311
	free(pair->two);
1312
	free(pair);
1313
}
1314

1315
/*
1316
 * A combine_diff_path expresses N parents on the LHS against 1 merge
1317
 * result. Synthesize a diff_filepair that has N entries on the "one"
1318
 * side and 1 entry on the "two" side.
1319
 *
1320
 * In the future, we might want to add more data to combine_diff_path
1321
 * so that we can fill fields we are ignoring (most notably, size) here,
1322
 * but currently nobody uses it, so this should suffice for now.
1323
 */
1324
static struct diff_filepair *combined_pair(struct combine_diff_path *p,
1325
					   int num_parent)
1326
{
1327
	int i;
1328
	struct diff_filepair *pair;
1329
	struct diff_filespec *pool;
1330

1331
	pair = xmalloc(sizeof(*pair));
1332
	CALLOC_ARRAY(pool, st_add(num_parent, 1));
1333
	pair->one = pool + 1;
1334
	pair->two = pool;
1335

1336
	for (i = 0; i < num_parent; i++) {
1337
		pair->one[i].path = p->path;
1338
		pair->one[i].mode = p->parent[i].mode;
1339
		oidcpy(&pair->one[i].oid, &p->parent[i].oid);
1340
		pair->one[i].oid_valid = !is_null_oid(&p->parent[i].oid);
1341
		pair->one[i].has_more_entries = 1;
1342
	}
1343
	pair->one[num_parent - 1].has_more_entries = 0;
1344

1345
	pair->two->path = p->path;
1346
	pair->two->mode = p->mode;
1347
	oidcpy(&pair->two->oid, &p->oid);
1348
	pair->two->oid_valid = !is_null_oid(&p->oid);
1349
	return pair;
1350
}
1351

1352
static void handle_combined_callback(struct diff_options *opt,
1353
				     struct combine_diff_path *paths,
1354
				     int num_parent,
1355
				     int num_paths)
1356
{
1357
	struct combine_diff_path *p;
1358
	struct diff_queue_struct q;
1359
	int i;
1360

1361
	CALLOC_ARRAY(q.queue, num_paths);
1362
	q.alloc = num_paths;
1363
	q.nr = num_paths;
1364
	for (i = 0, p = paths; p; p = p->next)
1365
		q.queue[i++] = combined_pair(p, num_parent);
1366
	opt->format_callback(&q, opt, opt->format_callback_data);
1367
	for (i = 0; i < num_paths; i++)
1368
		free_combined_pair(q.queue[i]);
1369
	free(q.queue);
1370
}
1371

1372
static const char *path_path(void *obj)
1373
{
1374
	struct combine_diff_path *path = (struct combine_diff_path *)obj;
1375

1376
	return path->path;
1377
}
1378

1379
/*
1380
 * Diff stat formats which we always compute solely against the first parent.
1381
 */
1382
#define STAT_FORMAT_MASK (DIFF_FORMAT_NUMSTAT \
1383
			  | DIFF_FORMAT_SHORTSTAT \
1384
			  | DIFF_FORMAT_SUMMARY \
1385
			  | DIFF_FORMAT_DIRSTAT \
1386
			  | DIFF_FORMAT_DIFFSTAT)
1387

1388
/* find set of paths that every parent touches */
1389
static struct combine_diff_path *find_paths_generic(const struct object_id *oid,
1390
	const struct oid_array *parents,
1391
	struct diff_options *opt,
1392
	int combined_all_paths)
1393
{
1394
	struct combine_diff_path *paths = NULL;
1395
	int i, num_parent = parents->nr;
1396

1397
	int output_format = opt->output_format;
1398
	const char *orderfile = opt->orderfile;
1399

1400
	opt->output_format = DIFF_FORMAT_NO_OUTPUT;
1401
	/* tell diff_tree to emit paths in sorted (=tree) order */
1402
	opt->orderfile = NULL;
1403

1404
	/* D(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn)  (wrt paths) */
1405
	for (i = 0; i < num_parent; i++) {
1406
		/*
1407
		 * show stat against the first parent even when doing
1408
		 * combined diff.
1409
		 */
1410
		int stat_opt = output_format & STAT_FORMAT_MASK;
1411
		if (i == 0 && stat_opt)
1412
			opt->output_format = stat_opt;
1413
		else
1414
			opt->output_format = DIFF_FORMAT_NO_OUTPUT;
1415
		diff_tree_oid(&parents->oid[i], oid, "", opt);
1416
		diffcore_std(opt);
1417
		paths = intersect_paths(paths, i, num_parent,
1418
					combined_all_paths);
1419

1420
		/* if showing diff, show it in requested order */
1421
		if (opt->output_format != DIFF_FORMAT_NO_OUTPUT &&
1422
		    orderfile) {
1423
			diffcore_order(orderfile);
1424
		}
1425

1426
		diff_flush(opt);
1427
	}
1428

1429
	opt->output_format = output_format;
1430
	opt->orderfile = orderfile;
1431
	return paths;
1432
}
1433

1434

1435
/*
1436
 * find set of paths that everybody touches, assuming diff is run without
1437
 * rename/copy detection, etc, comparing all trees simultaneously (= faster).
1438
 */
1439
static struct combine_diff_path *find_paths_multitree(
1440
	const struct object_id *oid, const struct oid_array *parents,
1441
	struct diff_options *opt)
1442
{
1443
	int i, nparent = parents->nr;
1444
	const struct object_id **parents_oid;
1445
	struct combine_diff_path paths_head;
1446
	struct strbuf base;
1447

1448
	ALLOC_ARRAY(parents_oid, nparent);
1449
	for (i = 0; i < nparent; i++)
1450
		parents_oid[i] = &parents->oid[i];
1451

1452
	/* fake list head, so worker can assume it is non-NULL */
1453
	paths_head.next = NULL;
1454

1455
	strbuf_init(&base, PATH_MAX);
1456
	diff_tree_paths(&paths_head, oid, parents_oid, nparent, &base, opt);
1457

1458
	strbuf_release(&base);
1459
	free(parents_oid);
1460
	return paths_head.next;
1461
}
1462

1463
static int match_objfind(struct combine_diff_path *path,
1464
			 int num_parent,
1465
			 const struct oidset *set)
1466
{
1467
	int i;
1468
	if (oidset_contains(set, &path->oid))
1469
		return 1;
1470
	for (i = 0; i < num_parent; i++) {
1471
		if (oidset_contains(set, &path->parent[i].oid))
1472
			return 1;
1473
	}
1474
	return 0;
1475
}
1476

1477
static struct combine_diff_path *combined_objfind(struct diff_options *opt,
1478
						  struct combine_diff_path *paths,
1479
						  int num_parent)
1480
{
1481
	struct combine_diff_path *ret = NULL, **tail = &ret;
1482
	struct combine_diff_path *p = paths;
1483

1484
	while (p) {
1485
		struct combine_diff_path *next = p->next;
1486

1487
		if (match_objfind(p, num_parent, opt->objfind)) {
1488
			p->next = NULL;
1489
			*tail = p;
1490
			tail = &p->next;
1491
		} else {
1492
			free(p);
1493
		}
1494
		p = next;
1495
	}
1496

1497
	return ret;
1498
}
1499

1500
void diff_tree_combined(const struct object_id *oid,
1501
			const struct oid_array *parents,
1502
			struct rev_info *rev)
1503
{
1504
	struct diff_options *opt = &rev->diffopt;
1505
	struct diff_options diffopts;
1506
	struct combine_diff_path *p, *paths;
1507
	int i, num_paths, needsep, show_log_first, num_parent = parents->nr;
1508
	int need_generic_pathscan;
1509

1510
	if (opt->ignore_regex_nr)
1511
		die("combined diff and '%s' cannot be used together",
1512
		    "--ignore-matching-lines");
1513
	if (opt->close_file)
1514
		die("combined diff and '%s' cannot be used together",
1515
		    "--output");
1516

1517
	/* nothing to do, if no parents */
1518
	if (!num_parent)
1519
		return;
1520

1521
	show_log_first = !!rev->loginfo && !rev->no_commit_id;
1522
	needsep = 0;
1523
	if (show_log_first) {
1524
		show_log(rev);
1525

1526
		if (rev->verbose_header && opt->output_format &&
1527
		    opt->output_format != DIFF_FORMAT_NO_OUTPUT &&
1528
		    !commit_format_is_empty(rev->commit_format))
1529
			printf("%s%c", diff_line_prefix(opt),
1530
			       opt->line_termination);
1531
	}
1532

1533
	diffopts = *opt;
1534
	copy_pathspec(&diffopts.pathspec, &opt->pathspec);
1535
	diffopts.flags.recursive = 1;
1536
	diffopts.flags.allow_external = 0;
1537

1538
	/* find set of paths that everybody touches
1539
	 *
1540
	 * NOTE
1541
	 *
1542
	 * Diffcore transformations are bound to diff_filespec and logic
1543
	 * comparing two entries - i.e. they do not apply directly to combine
1544
	 * diff.
1545
	 *
1546
	 * If some of such transformations is requested - we launch generic
1547
	 * path scanning, which works significantly slower compared to
1548
	 * simultaneous all-trees-in-one-go scan in find_paths_multitree().
1549
	 *
1550
	 * TODO some of the filters could be ported to work on
1551
	 * combine_diff_paths - i.e. all functionality that skips paths, so in
1552
	 * theory, we could end up having only multitree path scanning.
1553
	 *
1554
	 * NOTE please keep this semantically in sync with diffcore_std()
1555
	 */
1556
	need_generic_pathscan = opt->skip_stat_unmatch	||
1557
			opt->flags.follow_renames	||
1558
			opt->break_opt != -1	||
1559
			opt->detect_rename	||
1560
			(opt->pickaxe_opts &
1561
			 (DIFF_PICKAXE_KINDS_MASK & ~DIFF_PICKAXE_KIND_OBJFIND)) ||
1562
			opt->filter;
1563

1564
	if (need_generic_pathscan) {
1565
		/*
1566
		 * NOTE generic case also handles --stat, as it computes
1567
		 * diff(sha1,parent_i) for all i to do the job, specifically
1568
		 * for parent0.
1569
		 */
1570
		paths = find_paths_generic(oid, parents, &diffopts,
1571
					   rev->combined_all_paths);
1572
	}
1573
	else {
1574
		int stat_opt;
1575
		paths = find_paths_multitree(oid, parents, &diffopts);
1576

1577
		if (opt->pickaxe_opts & DIFF_PICKAXE_KIND_OBJFIND)
1578
			paths = combined_objfind(opt, paths, num_parent);
1579

1580
		/*
1581
		 * show stat against the first parent even
1582
		 * when doing combined diff.
1583
		 */
1584
		stat_opt = opt->output_format & STAT_FORMAT_MASK;
1585
		if (stat_opt) {
1586
			diffopts.output_format = stat_opt;
1587

1588
			diff_tree_oid(&parents->oid[0], oid, "", &diffopts);
1589
			diffcore_std(&diffopts);
1590
			if (opt->orderfile)
1591
				diffcore_order(opt->orderfile);
1592
			diff_flush(&diffopts);
1593
		}
1594
	}
1595

1596
	/* find out number of surviving paths */
1597
	for (num_paths = 0, p = paths; p; p = p->next)
1598
		num_paths++;
1599

1600
	/* order paths according to diffcore_order */
1601
	if (opt->orderfile && num_paths) {
1602
		struct obj_order *o;
1603

1604
		ALLOC_ARRAY(o, num_paths);
1605
		for (i = 0, p = paths; p; p = p->next, i++)
1606
			o[i].obj = p;
1607
		order_objects(opt->orderfile, path_path, o, num_paths);
1608
		for (i = 0; i < num_paths - 1; i++) {
1609
			p = o[i].obj;
1610
			p->next = o[i+1].obj;
1611
		}
1612

1613
		p = o[num_paths-1].obj;
1614
		p->next = NULL;
1615
		paths = o[0].obj;
1616
		free(o);
1617
	}
1618

1619

1620
	if (num_paths) {
1621
		if (opt->output_format & (DIFF_FORMAT_RAW |
1622
					  DIFF_FORMAT_NAME |
1623
					  DIFF_FORMAT_NAME_STATUS)) {
1624
			for (p = paths; p; p = p->next)
1625
				show_raw_diff(p, num_parent, rev);
1626
			needsep = 1;
1627
		}
1628
		else if (opt->output_format & STAT_FORMAT_MASK)
1629
			needsep = 1;
1630
		else if (opt->output_format & DIFF_FORMAT_CALLBACK)
1631
			handle_combined_callback(opt, paths, num_parent, num_paths);
1632

1633
		if (opt->output_format & DIFF_FORMAT_PATCH) {
1634
			if (needsep)
1635
				printf("%s%c", diff_line_prefix(opt),
1636
				       opt->line_termination);
1637
			for (p = paths; p; p = p->next)
1638
				show_patch_diff(p, num_parent, 0, rev);
1639
		}
1640
	}
1641

1642
	/* Clean things up */
1643
	while (paths) {
1644
		struct combine_diff_path *tmp = paths;
1645
		paths = paths->next;
1646
		for (i = 0; i < num_parent; i++)
1647
			if (rev->combined_all_paths &&
1648
			    filename_changed(tmp->parent[i].status))
1649
				strbuf_release(&tmp->parent[i].path);
1650
		free(tmp);
1651
	}
1652

1653
	clear_pathspec(&diffopts.pathspec);
1654
}
1655

1656
void diff_tree_combined_merge(const struct commit *commit,
1657
			      struct rev_info *rev)
1658
{
1659
	struct commit_list *parent = get_saved_parents(rev, commit);
1660
	struct oid_array parents = OID_ARRAY_INIT;
1661

1662
	while (parent) {
1663
		oid_array_append(&parents, &parent->item->object.oid);
1664
		parent = parent->next;
1665
	}
1666
	diff_tree_combined(&commit->object.oid, &parents, rev);
1667
	oid_array_clear(&parents);
1668
}
1669