Clarify git-cherry documentation.
[git] / combine-diff.c
1 #include "cache.h"
2 #include "commit.h"
3 #include "blob.h"
4 #include "diff.h"
5 #include "diffcore.h"
6 #include "quote.h"
7 #include "xdiff-interface.h"
8 #include "log-tree.h"
9
10 static int uninteresting(struct diff_filepair *p)
11 {
12         if (diff_unmodified_pair(p))
13                 return 1;
14         return 0;
15 }
16
17 static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)
18 {
19         struct diff_queue_struct *q = &diff_queued_diff;
20         struct combine_diff_path *p;
21         int i;
22
23         if (!n) {
24                 struct combine_diff_path *list = NULL, **tail = &list;
25                 for (i = 0; i < q->nr; i++) {
26                         int len;
27                         const char *path;
28                         if (uninteresting(q->queue[i]))
29                                 continue;
30                         path = q->queue[i]->two->path;
31                         len = strlen(path);
32                         p = xmalloc(combine_diff_path_size(num_parent, len));
33                         p->path = (char*) &(p->parent[num_parent]);
34                         memcpy(p->path, path, len);
35                         p->path[len] = 0;
36                         p->len = len;
37                         p->next = NULL;
38                         memset(p->parent, 0,
39                                sizeof(p->parent[0]) * num_parent);
40
41                         memcpy(p->sha1, q->queue[i]->two->sha1, 20);
42                         p->mode = q->queue[i]->two->mode;
43                         memcpy(p->parent[n].sha1, q->queue[i]->one->sha1, 20);
44                         p->parent[n].mode = q->queue[i]->one->mode;
45                         p->parent[n].status = q->queue[i]->status;
46                         *tail = p;
47                         tail = &p->next;
48                 }
49                 return list;
50         }
51
52         for (p = curr; p; p = p->next) {
53                 int found = 0;
54                 if (!p->len)
55                         continue;
56                 for (i = 0; i < q->nr; i++) {
57                         const char *path;
58                         int len;
59
60                         if (uninteresting(q->queue[i]))
61                                 continue;
62                         path = q->queue[i]->two->path;
63                         len = strlen(path);
64                         if (len == p->len && !memcmp(path, p->path, len)) {
65                                 found = 1;
66                                 memcpy(p->parent[n].sha1,
67                                        q->queue[i]->one->sha1, 20);
68                                 p->parent[n].mode = q->queue[i]->one->mode;
69                                 p->parent[n].status = q->queue[i]->status;
70                                 break;
71                         }
72                 }
73                 if (!found)
74                         p->len = 0;
75         }
76         return curr;
77 }
78
79 /* Lines lost from parent */
80 struct lline {
81         struct lline *next;
82         int len;
83         unsigned long parent_map;
84         char line[FLEX_ARRAY];
85 };
86
87 /* Lines surviving in the merge result */
88 struct sline {
89         struct lline *lost_head, **lost_tail;
90         char *bol;
91         int len;
92         /* bit 0 up to (N-1) are on if the parent has this line (i.e.
93          * we did not change it).
94          * bit N is used for "interesting" lines, including context.
95          */
96         unsigned long flag;
97         unsigned long *p_lno;
98 };
99
100 static char *grab_blob(const unsigned char *sha1, unsigned long *size)
101 {
102         char *blob;
103         char type[20];
104         if (!memcmp(sha1, null_sha1, 20)) {
105                 /* deleted blob */
106                 *size = 0;
107                 return xcalloc(1, 1);
108         }
109         blob = read_sha1_file(sha1, type, size);
110         if (strcmp(type, blob_type))
111                 die("object '%s' is not a blob!", sha1_to_hex(sha1));
112         return blob;
113 }
114
115 static void append_lost(struct sline *sline, int n, const char *line, int len)
116 {
117         struct lline *lline;
118         unsigned long this_mask = (1UL<<n);
119         if (line[len-1] == '\n')
120                 len--;
121
122         /* Check to see if we can squash things */
123         if (sline->lost_head) {
124                 struct lline *last_one = NULL;
125                 /* We cannot squash it with earlier one */
126                 for (lline = sline->lost_head;
127                      lline;
128                      lline = lline->next)
129                         if (lline->parent_map & this_mask)
130                                 last_one = lline;
131                 lline = last_one ? last_one->next : sline->lost_head;
132                 while (lline) {
133                         if (lline->len == len &&
134                             !memcmp(lline->line, line, len)) {
135                                 lline->parent_map |= this_mask;
136                                 return;
137                         }
138                         lline = lline->next;
139                 }
140         }
141
142         lline = xmalloc(sizeof(*lline) + len + 1);
143         lline->len = len;
144         lline->next = NULL;
145         lline->parent_map = this_mask;
146         memcpy(lline->line, line, len);
147         lline->line[len] = 0;
148         *sline->lost_tail = lline;
149         sline->lost_tail = &lline->next;
150 }
151
152 struct combine_diff_state {
153         struct xdiff_emit_state xm;
154
155         unsigned int lno;
156         int ob, on, nb, nn;
157         unsigned long nmask;
158         int num_parent;
159         int n;
160         struct sline *sline;
161         struct sline *lost_bucket;
162 };
163
164 static void consume_line(void *state_, char *line, unsigned long len)
165 {
166         struct combine_diff_state *state = state_;
167         if (5 < len && !memcmp("@@ -", line, 4)) {
168                 if (parse_hunk_header(line, len,
169                                       &state->ob, &state->on,
170                                       &state->nb, &state->nn))
171                         return;
172                 state->lno = state->nb;
173                 if (!state->nb)
174                         /* @@ -1,2 +0,0 @@ to remove the
175                          * first two lines...
176                          */
177                         state->nb = 1;
178                 if (state->nn == 0)
179                         /* @@ -X,Y +N,0 @@ removed Y lines
180                          * that would have come *after* line N
181                          * in the result.  Our lost buckets hang
182                          * to the line after the removed lines,
183                          */
184                         state->lost_bucket = &state->sline[state->nb];
185                 else
186                         state->lost_bucket = &state->sline[state->nb-1];
187                 if (!state->sline[state->nb-1].p_lno)
188                         state->sline[state->nb-1].p_lno =
189                                 xcalloc(state->num_parent,
190                                         sizeof(unsigned long));
191                 state->sline[state->nb-1].p_lno[state->n] = state->ob;
192                 return;
193         }
194         if (!state->lost_bucket)
195                 return; /* not in any hunk yet */
196         switch (line[0]) {
197         case '-':
198                 append_lost(state->lost_bucket, state->n, line+1, len-1);
199                 break;
200         case '+':
201                 state->sline[state->lno-1].flag |= state->nmask;
202                 state->lno++;
203                 break;
204         }
205 }
206
207 static void combine_diff(const unsigned char *parent, mmfile_t *result_file,
208                          struct sline *sline, int cnt, int n, int num_parent)
209 {
210         unsigned int p_lno, lno;
211         unsigned long nmask = (1UL << n);
212         xpparam_t xpp;
213         xdemitconf_t xecfg;
214         mmfile_t parent_file;
215         xdemitcb_t ecb;
216         struct combine_diff_state state;
217         unsigned long sz;
218
219         if (!cnt)
220                 return; /* result deleted */
221
222         parent_file.ptr = grab_blob(parent, &sz);
223         parent_file.size = sz;
224         xpp.flags = XDF_NEED_MINIMAL;
225         xecfg.ctxlen = 0;
226         xecfg.flags = 0;
227         ecb.outf = xdiff_outf;
228         ecb.priv = &state;
229         memset(&state, 0, sizeof(state));
230         state.xm.consume = consume_line;
231         state.nmask = nmask;
232         state.sline = sline;
233         state.lno = 1;
234         state.num_parent = num_parent;
235         state.n = n;
236
237         xdl_diff(&parent_file, result_file, &xpp, &xecfg, &ecb);
238         free(parent_file.ptr);
239
240         /* Assign line numbers for this parent.
241          *
242          * sline[lno].p_lno[n] records the first line number
243          * (counting from 1) for parent N if the final hunk display
244          * started by showing sline[lno] (possibly showing the lost
245          * lines attached to it first).
246          */
247         for (lno = 0,  p_lno = 1; lno <= cnt; lno++) {
248                 struct lline *ll;
249                 sline[lno].p_lno[n] = p_lno;
250
251                 /* How many lines would this sline advance the p_lno? */
252                 ll = sline[lno].lost_head;
253                 while (ll) {
254                         if (ll->parent_map & nmask)
255                                 p_lno++; /* '-' means parent had it */
256                         ll = ll->next;
257                 }
258                 if (lno < cnt && !(sline[lno].flag & nmask))
259                         p_lno++; /* no '+' means parent had it */
260         }
261         sline[lno].p_lno[n] = p_lno; /* trailer */
262 }
263
264 static unsigned long context = 3;
265 static char combine_marker = '@';
266
267 static int interesting(struct sline *sline, unsigned long all_mask)
268 {
269         /* If some parents lost lines here, or if we have added to
270          * some parent, it is interesting.
271          */
272         return ((sline->flag & all_mask) || sline->lost_head);
273 }
274
275 static unsigned long adjust_hunk_tail(struct sline *sline,
276                                       unsigned long all_mask,
277                                       unsigned long hunk_begin,
278                                       unsigned long i)
279 {
280         /* i points at the first uninteresting line.  If the last line
281          * of the hunk was interesting only because it has some
282          * deletion, then it is not all that interesting for the
283          * purpose of giving trailing context lines.  This is because
284          * we output '-' line and then unmodified sline[i-1] itself in
285          * that case which gives us one extra context line.
286          */
287         if ((hunk_begin + 1 <= i) && !(sline[i-1].flag & all_mask))
288                 i--;
289         return i;
290 }
291
292 static unsigned long find_next(struct sline *sline,
293                                unsigned long mark,
294                                unsigned long i,
295                                unsigned long cnt,
296                                int uninteresting)
297 {
298         /* We have examined up to i-1 and are about to look at i.
299          * Find next interesting or uninteresting line.  Here,
300          * "interesting" does not mean interesting(), but marked by
301          * the give_context() function below (i.e. it includes context
302          * lines that are not interesting to interesting() function
303          * that are surrounded by interesting() ones.
304          */
305         while (i <= cnt)
306                 if (uninteresting
307                     ? !(sline[i].flag & mark)
308                     : (sline[i].flag & mark))
309                         return i;
310                 else
311                         i++;
312         return i;
313 }
314
315 static int give_context(struct sline *sline, unsigned long cnt, int num_parent)
316 {
317         unsigned long all_mask = (1UL<<num_parent) - 1;
318         unsigned long mark = (1UL<<num_parent);
319         unsigned long i;
320
321         /* Two groups of interesting lines may have a short gap of
322          * unintersting lines.  Connect such groups to give them a
323          * bit of context.
324          *
325          * We first start from what the interesting() function says,
326          * and mark them with "mark", and paint context lines with the
327          * mark.  So interesting() would still say false for such context
328          * lines but they are treated as "interesting" in the end.
329          */
330         i = find_next(sline, mark, 0, cnt, 0);
331         if (cnt < i)
332                 return 0;
333
334         while (i <= cnt) {
335                 unsigned long j = (context < i) ? (i - context) : 0;
336                 unsigned long k;
337
338                 /* Paint a few lines before the first interesting line. */
339                 while (j < i)
340                         sline[j++].flag |= mark;
341
342         again:
343                 /* we know up to i is to be included.  where does the
344                  * next uninteresting one start?
345                  */
346                 j = find_next(sline, mark, i, cnt, 1);
347                 if (cnt < j)
348                         break; /* the rest are all interesting */
349
350                 /* lookahead context lines */
351                 k = find_next(sline, mark, j, cnt, 0);
352                 j = adjust_hunk_tail(sline, all_mask, i, j);
353
354                 if (k < j + context) {
355                         /* k is interesting and [j,k) are not, but
356                          * paint them interesting because the gap is small.
357                          */
358                         while (j < k)
359                                 sline[j++].flag |= mark;
360                         i = k;
361                         goto again;
362                 }
363
364                 /* j is the first uninteresting line and there is
365                  * no overlap beyond it within context lines.  Paint
366                  * the trailing edge a bit.
367                  */
368                 i = k;
369                 k = (j + context < cnt+1) ? j + context : cnt+1;
370                 while (j < k)
371                         sline[j++].flag |= mark;
372         }
373         return 1;
374 }
375
376 static int make_hunks(struct sline *sline, unsigned long cnt,
377                        int num_parent, int dense)
378 {
379         unsigned long all_mask = (1UL<<num_parent) - 1;
380         unsigned long mark = (1UL<<num_parent);
381         unsigned long i;
382         int has_interesting = 0;
383
384         for (i = 0; i <= cnt; i++) {
385                 if (interesting(&sline[i], all_mask))
386                         sline[i].flag |= mark;
387                 else
388                         sline[i].flag &= ~mark;
389         }
390         if (!dense)
391                 return give_context(sline, cnt, num_parent);
392
393         /* Look at each hunk, and if we have changes from only one
394          * parent, or the changes are the same from all but one
395          * parent, mark that uninteresting.
396          */
397         i = 0;
398         while (i <= cnt) {
399                 unsigned long j, hunk_begin, hunk_end;
400                 unsigned long same_diff;
401                 while (i <= cnt && !(sline[i].flag & mark))
402                         i++;
403                 if (cnt < i)
404                         break; /* No more interesting hunks */
405                 hunk_begin = i;
406                 for (j = i + 1; j <= cnt; j++) {
407                         if (!(sline[j].flag & mark)) {
408                                 /* Look beyond the end to see if there
409                                  * is an interesting line after this
410                                  * hunk within context span.
411                                  */
412                                 unsigned long la; /* lookahead */
413                                 int contin = 0;
414                                 la = adjust_hunk_tail(sline, all_mask,
415                                                      hunk_begin, j);
416                                 la = (la + context < cnt + 1) ?
417                                         (la + context) : cnt + 1;
418                                 while (j <= --la) {
419                                         if (sline[la].flag & mark) {
420                                                 contin = 1;
421                                                 break;
422                                         }
423                                 }
424                                 if (!contin)
425                                         break;
426                                 j = la;
427                         }
428                 }
429                 hunk_end = j;
430
431                 /* [i..hunk_end) are interesting.  Now is it really
432                  * interesting?  We check if there are only two versions
433                  * and the result matches one of them.  That is, we look
434                  * at:
435                  *   (+) line, which records lines added to which parents;
436                  *       this line appears in the result.
437                  *   (-) line, which records from what parents the line
438                  *       was removed; this line does not appear in the result.
439                  * then check the set of parents the result has difference
440                  * from, from all lines.  If there are lines that has
441                  * different set of parents that the result has differences
442                  * from, that means we have more than two versions.
443                  *
444                  * Even when we have only two versions, if the result does
445                  * not match any of the parents, the it should be considered
446                  * interesting.  In such a case, we would have all '+' line.
447                  * After passing the above "two versions" test, that would
448                  * appear as "the same set of parents" to be "all parents".
449                  */
450                 same_diff = 0;
451                 has_interesting = 0;
452                 for (j = i; j < hunk_end && !has_interesting; j++) {
453                         unsigned long this_diff = sline[j].flag & all_mask;
454                         struct lline *ll = sline[j].lost_head;
455                         if (this_diff) {
456                                 /* This has some changes.  Is it the
457                                  * same as others?
458                                  */
459                                 if (!same_diff)
460                                         same_diff = this_diff;
461                                 else if (same_diff != this_diff) {
462                                         has_interesting = 1;
463                                         break;
464                                 }
465                         }
466                         while (ll && !has_interesting) {
467                                 /* Lost this line from these parents;
468                                  * who are they?  Are they the same?
469                                  */
470                                 this_diff = ll->parent_map;
471                                 if (!same_diff)
472                                         same_diff = this_diff;
473                                 else if (same_diff != this_diff) {
474                                         has_interesting = 1;
475                                 }
476                                 ll = ll->next;
477                         }
478                 }
479
480                 if (!has_interesting && same_diff != all_mask) {
481                         /* This hunk is not that interesting after all */
482                         for (j = hunk_begin; j < hunk_end; j++)
483                                 sline[j].flag &= ~mark;
484                 }
485                 i = hunk_end;
486         }
487
488         has_interesting = give_context(sline, cnt, num_parent);
489         return has_interesting;
490 }
491
492 static void show_parent_lno(struct sline *sline, unsigned long l0, unsigned long l1, unsigned long cnt, int n)
493 {
494         l0 = sline[l0].p_lno[n];
495         l1 = sline[l1].p_lno[n];
496         printf(" -%lu,%lu", l0, l1-l0);
497 }
498
499 static void dump_sline(struct sline *sline, unsigned long cnt, int num_parent)
500 {
501         unsigned long mark = (1UL<<num_parent);
502         int i;
503         unsigned long lno = 0;
504
505         if (!cnt)
506                 return; /* result deleted */
507
508         while (1) {
509                 struct sline *sl = &sline[lno];
510                 unsigned long hunk_end;
511                 unsigned long rlines;
512                 while (lno <= cnt && !(sline[lno].flag & mark))
513                         lno++;
514                 if (cnt < lno)
515                         break;
516                 else {
517                         for (hunk_end = lno + 1; hunk_end <= cnt; hunk_end++)
518                                 if (!(sline[hunk_end].flag & mark))
519                                         break;
520                 }
521                 rlines = hunk_end - lno;
522                 if (cnt < hunk_end)
523                         rlines--; /* pointing at the last delete hunk */
524                 for (i = 0; i <= num_parent; i++) putchar(combine_marker);
525                 for (i = 0; i < num_parent; i++)
526                         show_parent_lno(sline, lno, hunk_end, cnt, i);
527                 printf(" +%lu,%lu ", lno+1, rlines);
528                 for (i = 0; i <= num_parent; i++) putchar(combine_marker);
529                 putchar('\n');
530                 while (lno < hunk_end) {
531                         struct lline *ll;
532                         int j;
533                         unsigned long p_mask;
534                         sl = &sline[lno++];
535                         ll = sl->lost_head;
536                         while (ll) {
537                                 for (j = 0; j < num_parent; j++) {
538                                         if (ll->parent_map & (1UL<<j))
539                                                 putchar('-');
540                                         else
541                                                 putchar(' ');
542                                 }
543                                 puts(ll->line);
544                                 ll = ll->next;
545                         }
546                         if (cnt < lno)
547                                 break;
548                         p_mask = 1;
549                         for (j = 0; j < num_parent; j++) {
550                                 if (p_mask & sl->flag)
551                                         putchar('+');
552                                 else
553                                         putchar(' ');
554                                 p_mask <<= 1;
555                         }
556                         printf("%.*s\n", sl->len, sl->bol);
557                 }
558         }
559 }
560
561 static void reuse_combine_diff(struct sline *sline, unsigned long cnt,
562                                int i, int j)
563 {
564         /* We have already examined parent j and we know parent i
565          * and parent j are the same, so reuse the combined result
566          * of parent j for parent i.
567          */
568         unsigned long lno, imask, jmask;
569         imask = (1UL<<i);
570         jmask = (1UL<<j);
571
572         for (lno = 0; lno <= cnt; lno++) {
573                 struct lline *ll = sline->lost_head;
574                 sline->p_lno[i] = sline->p_lno[j];
575                 while (ll) {
576                         if (ll->parent_map & jmask)
577                                 ll->parent_map |= imask;
578                         ll = ll->next;
579                 }
580                 if (sline->flag & jmask)
581                         sline->flag |= imask;
582                 sline++;
583         }
584         /* the overall size of the file (sline[cnt]) */
585         sline->p_lno[i] = sline->p_lno[j];
586 }
587
588 static void dump_quoted_path(const char *prefix, const char *path)
589 {
590         fputs(prefix, stdout);
591         if (quote_c_style(path, NULL, NULL, 0))
592                 quote_c_style(path, NULL, stdout, 0);
593         else
594                 printf("%s", path);
595         putchar('\n');
596 }
597
598 static int show_patch_diff(struct combine_diff_path *elem, int num_parent,
599                            int dense, struct rev_info *rev)
600 {
601         struct diff_options *opt = &rev->diffopt;
602         unsigned long result_size, cnt, lno;
603         char *result, *cp;
604         struct sline *sline; /* survived lines */
605         int mode_differs = 0;
606         int i, show_hunks, shown_header = 0;
607         int working_tree_file = !memcmp(elem->sha1, null_sha1, 20);
608         int abbrev = opt->full_index ? 40 : DEFAULT_ABBREV;
609         mmfile_t result_file;
610
611         /* Read the result of merge first */
612         if (!working_tree_file)
613                 result = grab_blob(elem->sha1, &result_size);
614         else {
615                 /* Used by diff-tree to read from the working tree */
616                 struct stat st;
617                 int fd;
618                 if (0 <= (fd = open(elem->path, O_RDONLY)) &&
619                     !fstat(fd, &st)) {
620                         int len = st.st_size;
621                         int cnt = 0;
622
623                         elem->mode = canon_mode(st.st_mode);
624                         result_size = len;
625                         result = xmalloc(len + 1);
626                         while (cnt < len) {
627                                 int done = xread(fd, result+cnt, len-cnt);
628                                 if (done == 0)
629                                         break;
630                                 if (done < 0)
631                                         die("read error '%s'", elem->path);
632                                 cnt += done;
633                         }
634                         result[len] = 0;
635                 }
636                 else {
637                         /* deleted file */
638                         result_size = 0;
639                         elem->mode = 0;
640                         result = xmalloc(1);
641                         result[0] = 0;
642                 }
643                 if (0 <= fd)
644                         close(fd);
645         }
646
647         for (cnt = 0, cp = result; cp - result < result_size; cp++) {
648                 if (*cp == '\n')
649                         cnt++;
650         }
651         if (result_size && result[result_size-1] != '\n')
652                 cnt++; /* incomplete line */
653
654         sline = xcalloc(cnt+2, sizeof(*sline));
655         sline[0].bol = result;
656         for (lno = 0; lno <= cnt + 1; lno++) {
657                 sline[lno].lost_tail = &sline[lno].lost_head;
658                 sline[lno].flag = 0;
659         }
660         for (lno = 0, cp = result; cp - result < result_size; cp++) {
661                 if (*cp == '\n') {
662                         sline[lno].len = cp - sline[lno].bol;
663                         lno++;
664                         if (lno < cnt)
665                                 sline[lno].bol = cp + 1;
666                 }
667         }
668         if (result_size && result[result_size-1] != '\n')
669                 sline[cnt-1].len = result_size - (sline[cnt-1].bol - result);
670
671         result_file.ptr = result;
672         result_file.size = result_size;
673
674         /* Even p_lno[cnt+1] is valid -- that is for the end line number
675          * for deletion hunk at the end.
676          */
677         sline[0].p_lno = xcalloc((cnt+2) * num_parent, sizeof(unsigned long));
678         for (lno = 0; lno <= cnt; lno++)
679                 sline[lno+1].p_lno = sline[lno].p_lno + num_parent;
680
681         for (i = 0; i < num_parent; i++) {
682                 int j;
683                 for (j = 0; j < i; j++) {
684                         if (!memcmp(elem->parent[i].sha1,
685                                     elem->parent[j].sha1, 20)) {
686                                 reuse_combine_diff(sline, cnt, i, j);
687                                 break;
688                         }
689                 }
690                 if (i <= j)
691                         combine_diff(elem->parent[i].sha1, &result_file, sline,
692                                      cnt, i, num_parent);
693                 if (elem->parent[i].mode != elem->mode)
694                         mode_differs = 1;
695         }
696
697         show_hunks = make_hunks(sline, cnt, num_parent, dense);
698
699         if (show_hunks || mode_differs || working_tree_file) {
700                 const char *abb;
701
702                 if (rev->loginfo)
703                         show_log(rev, rev->loginfo, "\n");
704                 dump_quoted_path(dense ? "diff --cc " : "diff --combined ", elem->path);
705                 printf("index ");
706                 for (i = 0; i < num_parent; i++) {
707                         abb = find_unique_abbrev(elem->parent[i].sha1,
708                                                  abbrev);
709                         printf("%s%s", i ? "," : "", abb);
710                 }
711                 abb = find_unique_abbrev(elem->sha1, abbrev);
712                 printf("..%s\n", abb);
713
714                 if (mode_differs) {
715                         int added = !!elem->mode;
716                         for (i = 0; added && i < num_parent; i++)
717                                 if (elem->parent[i].status !=
718                                     DIFF_STATUS_ADDED)
719                                         added = 0;
720                         if (added)
721                                 printf("new file mode %06o", elem->mode);
722                         else {
723                                 if (!elem->mode)
724                                         printf("deleted file ");
725                                 printf("mode ");
726                                 for (i = 0; i < num_parent; i++) {
727                                         printf("%s%06o", i ? "," : "",
728                                                elem->parent[i].mode);
729                                 }
730                                 if (elem->mode)
731                                         printf("..%06o", elem->mode);
732                         }
733                         putchar('\n');
734                 }
735                 dump_quoted_path("--- a/", elem->path);
736                 dump_quoted_path("+++ b/", elem->path);
737                 dump_sline(sline, cnt, num_parent);
738         }
739         free(result);
740
741         for (i = 0; i < cnt; i++) {
742                 if (sline[i].lost_head) {
743                         struct lline *ll = sline[i].lost_head;
744                         while (ll) {
745                                 struct lline *tmp = ll;
746                                 ll = ll->next;
747                                 free(tmp);
748                         }
749                 }
750         }
751         free(sline[0].p_lno);
752         free(sline);
753         return shown_header;
754 }
755
756 #define COLONS "::::::::::::::::::::::::::::::::"
757
758 static void show_raw_diff(struct combine_diff_path *p, int num_parent, struct rev_info *rev)
759 {
760         struct diff_options *opt = &rev->diffopt;
761         int i, offset;
762         const char *prefix;
763         int line_termination, inter_name_termination;
764
765         line_termination = opt->line_termination;
766         inter_name_termination = '\t';
767         if (!line_termination)
768                 inter_name_termination = 0;
769
770         if (rev->loginfo)
771                 show_log(rev, rev->loginfo, "\n");
772
773         if (opt->output_format == DIFF_FORMAT_RAW) {
774                 offset = strlen(COLONS) - num_parent;
775                 if (offset < 0)
776                         offset = 0;
777                 prefix = COLONS + offset;
778
779                 /* Show the modes */
780                 for (i = 0; i < num_parent; i++) {
781                         printf("%s%06o", prefix, p->parent[i].mode);
782                         prefix = " ";
783                 }
784                 printf("%s%06o", prefix, p->mode);
785
786                 /* Show sha1's */
787                 for (i = 0; i < num_parent; i++)
788                         printf(" %s", diff_unique_abbrev(p->parent[i].sha1,
789                                                          opt->abbrev));
790                 printf(" %s ", diff_unique_abbrev(p->sha1, opt->abbrev));
791         }
792
793         if (opt->output_format == DIFF_FORMAT_RAW ||
794             opt->output_format == DIFF_FORMAT_NAME_STATUS) {
795                 for (i = 0; i < num_parent; i++)
796                         putchar(p->parent[i].status);
797                 putchar(inter_name_termination);
798         }
799
800         if (line_termination) {
801                 if (quote_c_style(p->path, NULL, NULL, 0))
802                         quote_c_style(p->path, NULL, stdout, 0);
803                 else
804                         printf("%s", p->path);
805                 putchar(line_termination);
806         }
807         else {
808                 printf("%s%c", p->path, line_termination);
809         }
810 }
811
812 void show_combined_diff(struct combine_diff_path *p,
813                        int num_parent,
814                        int dense,
815                        struct rev_info *rev)
816 {
817         struct diff_options *opt = &rev->diffopt;
818         if (!p->len)
819                 return;
820         switch (opt->output_format) {
821         case DIFF_FORMAT_RAW:
822         case DIFF_FORMAT_NAME_STATUS:
823         case DIFF_FORMAT_NAME:
824                 show_raw_diff(p, num_parent, rev);
825                 return;
826         case DIFF_FORMAT_PATCH:
827                 show_patch_diff(p, num_parent, dense, rev);
828                 return;
829         default:
830                 return;
831         }
832 }
833
834 void diff_tree_combined(const unsigned char *sha1,
835                         const unsigned char parent[][20],
836                         int num_parent,
837                         int dense,
838                         struct rev_info *rev)
839 {
840         struct diff_options *opt = &rev->diffopt;
841         struct diff_options diffopts;
842         struct combine_diff_path *p, *paths = NULL;
843         int i, num_paths;
844         int do_diffstat;
845
846         do_diffstat = (opt->output_format == DIFF_FORMAT_DIFFSTAT ||
847                        opt->with_stat);
848         diffopts = *opt;
849         diffopts.with_raw = 0;
850         diffopts.with_stat = 0;
851         diffopts.recursive = 1;
852
853         /* find set of paths that everybody touches */
854         for (i = 0; i < num_parent; i++) {
855                 /* show stat against the first parent even
856                  * when doing combined diff.
857                  */
858                 if (i == 0 && do_diffstat)
859                         diffopts.output_format = DIFF_FORMAT_DIFFSTAT;
860                 else
861                         diffopts.output_format = DIFF_FORMAT_NO_OUTPUT;
862                 diff_tree_sha1(parent[i], sha1, "", &diffopts);
863                 diffcore_std(&diffopts);
864                 paths = intersect_paths(paths, i, num_parent);
865
866                 if (do_diffstat && rev->loginfo)
867                         show_log(rev, rev->loginfo,
868                                  opt->with_stat ? "---\n" : "\n");
869                 diff_flush(&diffopts);
870                 if (opt->with_stat)
871                         putchar('\n');
872         }
873
874         /* find out surviving paths */
875         for (num_paths = 0, p = paths; p; p = p->next) {
876                 if (p->len)
877                         num_paths++;
878         }
879         if (num_paths) {
880                 if (opt->with_raw) {
881                         int saved_format = opt->output_format;
882                         opt->output_format = DIFF_FORMAT_RAW;
883                         for (p = paths; p; p = p->next) {
884                                 show_combined_diff(p, num_parent, dense, rev);
885                         }
886                         opt->output_format = saved_format;
887                         putchar(opt->line_termination);
888                 }
889                 for (p = paths; p; p = p->next) {
890                         show_combined_diff(p, num_parent, dense, rev);
891                 }
892         }
893
894         /* Clean things up */
895         while (paths) {
896                 struct combine_diff_path *tmp = paths;
897                 paths = paths->next;
898                 free(tmp);
899         }
900 }
901
902 void diff_tree_combined_merge(const unsigned char *sha1,
903                              int dense, struct rev_info *rev)
904 {
905         int num_parent;
906         const unsigned char (*parent)[20];
907         struct commit *commit = lookup_commit(sha1);
908         struct commit_list *parents;
909
910         /* count parents */
911         for (parents = commit->parents, num_parent = 0;
912              parents;
913              parents = parents->next, num_parent++)
914                 ; /* nothing */
915
916         parent = xmalloc(num_parent * sizeof(*parent));
917         for (parents = commit->parents, num_parent = 0;
918              parents;
919              parents = parents->next, num_parent++)
920                 memcpy(parent + num_parent, parents->item->object.sha1, 20);
921         diff_tree_combined(sha1, parent, num_parent, dense, rev);
922 }