7 static int uninteresting(struct diff_filepair
*p
)
9 if (diff_unmodified_pair(p
))
11 if (!S_ISREG(p
->one
->mode
) || !S_ISREG(p
->two
->mode
))
16 static struct combine_diff_path
*intersect_paths(struct combine_diff_path
*curr
, int n
, int num_parent
)
18 struct diff_queue_struct
*q
= &diff_queued_diff
;
19 struct combine_diff_path
*p
;
23 struct combine_diff_path
*list
= NULL
, **tail
= &list
;
24 for (i
= 0; i
< q
->nr
; i
++) {
27 if (uninteresting(q
->queue
[i
]))
29 path
= q
->queue
[i
]->two
->path
;
32 p
= xmalloc(sizeof(*p
) + len
+ 1 + num_parent
* 20);
33 p
->path
= (char*) &(p
->parent_sha1
[num_parent
][0]);
34 memcpy(p
->path
, path
, len
);
38 memcpy(p
->sha1
, q
->queue
[i
]->two
->sha1
, 20);
39 memcpy(p
->parent_sha1
[n
], q
->queue
[i
]->one
->sha1
, 20);
46 for (p
= curr
; p
; p
= p
->next
) {
50 for (i
= 0; i
< q
->nr
; i
++) {
54 if (uninteresting(q
->queue
[i
]))
56 path
= q
->queue
[i
]->two
->path
;
58 if (len
== p
->len
&& !memcmp(path
, p
->path
, len
)) {
60 memcpy(p
->parent_sha1
[n
],
61 q
->queue
[i
]->one
->sha1
, 20);
74 unsigned long parent_map
;
75 char line
[FLEX_ARRAY
];
79 struct lline
*lost_head
, **lost_tail
;
85 static char *grab_blob(const unsigned char *sha1
, unsigned long *size
)
89 if (!memcmp(sha1
, null_sha1
, 20)) {
94 blob
= read_sha1_file(sha1
, type
, size
);
95 if (strcmp(type
, "blob"))
96 die("object '%s' is not a blob!", sha1_to_hex(sha1
));
100 #define TMPPATHLEN 50
101 #define MAXLINELEN 10240
103 static void write_to_temp_file(char *tmpfile
, void *blob
, unsigned long size
)
105 int fd
= git_mkstemp(tmpfile
, TMPPATHLEN
, ".diff_XXXXXX");
107 die("unable to create temp-file");
108 if (write(fd
, blob
, size
) != size
)
109 die("unable to write temp-file");
113 static void write_temp_blob(char *tmpfile
, const unsigned char *sha1
)
117 blob
= grab_blob(sha1
, &size
);
118 write_to_temp_file(tmpfile
, blob
, size
);
122 static int parse_num(char **cp_p
, unsigned int *num_p
)
125 unsigned int num
= 0;
128 while ('0' <= *cp
&& *cp
<= '9')
129 num
= num
* 10 + *cp
++ - '0';
130 if (!(read_some
= cp
- *cp_p
))
137 static int parse_hunk_header(char *line
, int len
,
138 unsigned int *ob
, unsigned int *on
,
139 unsigned int *nb
, unsigned int *nn
)
143 if (parse_num(&cp
, ob
)) {
145 return error("malformed diff output: %s", line
);
149 if (parse_num(&cp
, on
))
154 if (*cp
++ != ' ' || *cp
++ != '+')
156 if (parse_num(&cp
, nb
))
160 if (parse_num(&cp
, nn
))
165 return -!!memcmp(cp
, " @@", 3);
168 static void append_lost(struct sline
*sline
, int n
, const char *line
)
171 int len
= strlen(line
);
172 unsigned long this_mask
= (1UL<<n
);
173 if (line
[len
-1] == '\n')
176 /* Check to see if we can squash things */
177 if (sline
->lost_head
) {
178 struct lline
*last_one
= NULL
;
179 /* We cannot squash it with earlier one */
180 for (lline
= sline
->lost_head
;
183 if (lline
->parent_map
& this_mask
)
185 lline
= last_one
? last_one
->next
: sline
->lost_head
;
187 if (lline
->len
== len
&&
188 !memcmp(lline
->line
, line
, len
)) {
189 lline
->parent_map
|= this_mask
;
196 lline
= xmalloc(sizeof(*lline
) + len
+ 1);
199 lline
->parent_map
= this_mask
;
200 memcpy(lline
->line
, line
, len
);
201 lline
->line
[len
] = 0;
202 *sline
->lost_tail
= lline
;
203 sline
->lost_tail
= &lline
->next
;
206 static void combine_diff(const unsigned char *parent
, const char *ourtmp
,
207 struct sline
*sline
, int cnt
, int n
)
210 char parent_tmp
[TMPPATHLEN
];
211 char cmd
[TMPPATHLEN
* 2 + 1024];
212 char line
[MAXLINELEN
];
213 unsigned int lno
, ob
, on
, nb
, nn
;
214 unsigned long pmask
= ~(1UL << n
);
215 struct sline
*lost_bucket
= NULL
;
217 write_temp_blob(parent_tmp
, parent
);
218 sprintf(cmd
, "diff --unified=0 -La/x -Lb/x '%s' '%s'",
220 in
= popen(cmd
, "r");
225 while (fgets(line
, sizeof(line
), in
) != NULL
) {
226 int len
= strlen(line
);
227 if (5 < len
&& !memcmp("@@ -", line
, 4)) {
228 if (parse_hunk_header(line
, len
,
233 /* @@ -1,2 +0,0 @@ to remove the
239 lost_bucket
= &sline
[nb
];
241 lost_bucket
= &sline
[nb
-1];
248 append_lost(lost_bucket
, n
, line
+1);
251 sline
[lno
-1].flag
&= pmask
;
260 static unsigned long context
= 3;
261 static char combine_marker
= '@';
263 static int interesting(struct sline
*sline
, unsigned long all_mask
)
265 return ((sline
->flag
& all_mask
) != all_mask
|| sline
->lost_head
);
268 static unsigned long adjust_hunk_tail(struct sline
*sline
,
269 unsigned long all_mask
,
270 unsigned long hunk_begin
,
273 /* i points at the first uninteresting line.
274 * If the last line of the hunk was interesting
275 * only because it has some deletion, then
276 * it is not all that interesting for the
277 * purpose of giving trailing context lines.
279 if ((hunk_begin
+ 1 <= i
) &&
280 ((sline
[i
-1].flag
& all_mask
) == all_mask
))
285 static unsigned long next_interesting(struct sline
*sline
,
293 !(sline
[i
].flag
& mark
) :
294 (sline
[i
].flag
& mark
))
301 static int give_context(struct sline
*sline
, unsigned long cnt
, int num_parent
)
303 unsigned long all_mask
= (1UL<<num_parent
) - 1;
304 unsigned long mark
= (1UL<<num_parent
);
307 i
= next_interesting(sline
, mark
, 0, cnt
, 0);
312 unsigned long j
= (context
< i
) ? (i
- context
) : 0;
315 sline
[j
++].flag
|= mark
;
318 j
= next_interesting(sline
, mark
, i
, cnt
, 1);
320 break; /* the rest are all interesting */
322 /* lookahead context lines */
323 k
= next_interesting(sline
, mark
, j
, cnt
, 0);
324 j
= adjust_hunk_tail(sline
, all_mask
, i
, j
);
326 if (k
< j
+ context
) {
327 /* k is interesting and [j,k) are not, but
328 * paint them interesting because the gap is small.
331 sline
[j
++].flag
|= mark
;
336 /* j is the first uninteresting line and there is
337 * no overlap beyond it within context lines.
340 k
= (j
+ context
< cnt
) ? j
+ context
: cnt
;
342 sline
[j
++].flag
|= mark
;
347 static int make_hunks(struct sline
*sline
, unsigned long cnt
,
348 int num_parent
, int dense
)
350 unsigned long all_mask
= (1UL<<num_parent
) - 1;
351 unsigned long mark
= (1UL<<num_parent
);
353 int has_interesting
= 0;
355 for (i
= 0; i
< cnt
; i
++) {
356 if (interesting(&sline
[i
], all_mask
))
357 sline
[i
].flag
|= mark
;
359 sline
[i
].flag
&= ~mark
;
362 return give_context(sline
, cnt
, num_parent
);
364 /* Look at each hunk, and if we have changes from only one
365 * parent, or the changes are the same from all but one
366 * parent, mark that uninteresting.
370 unsigned long j
, hunk_begin
, hunk_end
;
371 unsigned long same_diff
;
372 while (i
< cnt
&& !(sline
[i
].flag
& mark
))
375 break; /* No more interesting hunks */
377 for (j
= i
+ 1; j
< cnt
; j
++) {
378 if (!(sline
[j
].flag
& mark
)) {
379 /* Look beyond the end to see if there
380 * is an interesting line after this
381 * hunk within context span.
383 unsigned long la
; /* lookahead */
385 la
= adjust_hunk_tail(sline
, all_mask
,
387 la
= (la
+ context
< cnt
) ?
388 (la
+ context
) : cnt
;
390 if (sline
[la
].flag
& mark
) {
402 /* [i..hunk_end) are interesting. Now is it really
403 * interesting? We check if there are only two versions
404 * and the result matches one of them. That is, we look
406 * (+) line, which records lines added to which parents;
407 * this line appears in the result.
408 * (-) line, which records from what parents the line
409 * was removed; this line does not appear in the result.
410 * then check the set of parents the result has difference
411 * from, from all lines. If there are lines that has
412 * different set of parents that the result has differences
413 * from, that means we have more than two versions.
415 * Even when we have only two versions, if the result does
416 * not match any of the parents, the it should be considered
417 * interesting. In such a case, we would have all '+' line.
418 * After passing the above "two versions" test, that would
419 * appear as "the same set of parents" to be "all parents".
423 for (j
= i
; j
< hunk_end
&& !has_interesting
; j
++) {
424 unsigned long this_diff
= ~sline
[j
].flag
& all_mask
;
425 struct lline
*ll
= sline
[j
].lost_head
;
427 /* This has some changes. Is it the
431 same_diff
= this_diff
;
432 else if (same_diff
!= this_diff
) {
437 while (ll
&& !has_interesting
) {
438 /* Lost this line from these parents;
439 * who are they? Are they the same?
441 this_diff
= ll
->parent_map
;
443 same_diff
= this_diff
;
444 else if (same_diff
!= this_diff
) {
451 if (!has_interesting
&& same_diff
!= all_mask
) {
452 /* This hunk is not that interesting after all */
453 for (j
= hunk_begin
; j
< hunk_end
; j
++)
454 sline
[j
].flag
&= ~mark
;
459 has_interesting
= give_context(sline
, cnt
, num_parent
);
460 return has_interesting
;
463 static void dump_sline(struct sline
*sline
, int cnt
, int num_parent
)
465 unsigned long mark
= (1UL<<num_parent
);
470 struct sline
*sl
= &sline
[lno
];
472 while (lno
< cnt
&& !(sline
[lno
].flag
& mark
))
476 for (hunk_end
= lno
+ 1; hunk_end
< cnt
; hunk_end
++)
477 if (!(sline
[hunk_end
].flag
& mark
))
479 for (i
= 0; i
<= num_parent
; i
++) putchar(combine_marker
);
480 printf(" +%d,%d ", lno
+1, hunk_end
-lno
);
481 for (i
= 0; i
<= num_parent
; i
++) putchar(combine_marker
);
483 while (lno
< hunk_end
) {
489 for (j
= 0; j
< num_parent
; j
++) {
490 if (ll
->parent_map
& (1UL<<j
))
498 for (j
= 0; j
< num_parent
; j
++) {
499 if ((1UL<<j
) & sl
->flag
)
504 printf("%.*s\n", sl
->len
, sl
->bol
);
509 static void reuse_combine_diff(struct sline
*sline
, unsigned long cnt
,
512 /* We have already examined parent j and we know parent i
513 * and parent j are the same, so reuse the combined result
514 * of parent j for parent i.
516 unsigned long lno
, imask
, jmask
;
520 for (lno
= 0; lno
< cnt
; lno
++) {
521 struct lline
*ll
= sline
->lost_head
;
523 if (ll
->parent_map
& jmask
)
524 ll
->parent_map
|= imask
;
527 if (!(sline
->flag
& jmask
))
528 sline
->flag
&= ~imask
;
533 int show_combined_diff(struct combine_diff_path
*elem
, int num_parent
,
534 int dense
, const char *header
, int show_empty
)
536 unsigned long size
, cnt
, lno
;
537 char *result
, *cp
, *ep
;
538 struct sline
*sline
; /* survived lines */
539 int i
, show_hunks
, shown_header
= 0;
540 char ourtmp_buf
[TMPPATHLEN
];
541 char *ourtmp
= ourtmp_buf
;
543 /* Read the result of merge first */
544 if (memcmp(elem
->sha1
, null_sha1
, 20)) {
545 result
= grab_blob(elem
->sha1
, &size
);
546 write_to_temp_file(ourtmp
, result
, size
);
552 if (0 <= (fd
= open(ourtmp
, O_RDONLY
)) &&
554 int len
= st
.st_size
;
558 result
= xmalloc(len
+ 1);
560 int done
= xread(fd
, result
+cnt
, len
-cnt
);
564 die("read error '%s'", ourtmp
);
574 ourtmp
= "/dev/null";
580 for (cnt
= 0, cp
= result
; cp
- result
< size
; cp
++) {
584 if (result
[size
-1] != '\n')
585 cnt
++; /* incomplete line */
587 sline
= xcalloc(cnt
, sizeof(*sline
));
589 sline
[0].bol
= result
;
590 for (lno
= 0, cp
= result
; cp
- result
< size
; cp
++) {
592 sline
[lno
].lost_tail
= &sline
[lno
].lost_head
;
593 sline
[lno
].len
= cp
- sline
[lno
].bol
;
594 sline
[lno
].flag
= (1UL<<num_parent
) - 1;
597 sline
[lno
].bol
= cp
+ 1;
600 if (result
[size
-1] != '\n') {
601 sline
[cnt
-1].lost_tail
= &sline
[cnt
-1].lost_head
;
602 sline
[cnt
-1].len
= size
- (sline
[cnt
-1].bol
- result
);
603 sline
[cnt
-1].flag
= (1UL<<num_parent
) - 1;
606 for (i
= 0; i
< num_parent
; i
++) {
608 for (j
= 0; j
< i
; j
++) {
609 if (!memcmp(elem
->parent_sha1
[i
],
610 elem
->parent_sha1
[j
], 20)) {
611 reuse_combine_diff(sline
, cnt
, i
, j
);
616 combine_diff(elem
->parent_sha1
[i
], ourtmp
, sline
,
620 show_hunks
= make_hunks(sline
, cnt
, num_parent
, dense
);
622 if (header
&& (show_hunks
|| show_empty
)) {
627 printf("diff --%s ", dense
? "cc" : "combined");
628 if (quote_c_style(elem
->path
, NULL
, NULL
, 0))
629 quote_c_style(elem
->path
, NULL
, stdout
, 0);
631 printf("%s", elem
->path
);
634 for (i
= 0; i
< num_parent
; i
++) {
637 find_unique_abbrev(elem
->parent_sha1
[i
],
641 find_unique_abbrev(elem
->sha1
, DEFAULT_ABBREV
));
642 dump_sline(sline
, cnt
, num_parent
);
644 if (ourtmp
== ourtmp_buf
)
648 for (i
= 0; i
< cnt
; i
++) {
649 if (sline
[i
].lost_head
) {
650 struct lline
*ll
= sline
[i
].lost_head
;
652 struct lline
*tmp
= ll
;
662 int diff_tree_combined_merge(const unsigned char *sha1
,
664 int show_empty_merge
, int dense
)
666 struct commit
*commit
= lookup_commit(sha1
);
667 struct diff_options diffopts
;
668 struct commit_list
*parents
;
669 struct combine_diff_path
*p
, *paths
= NULL
;
670 int num_parent
, i
, num_paths
;
672 diff_setup(&diffopts
);
673 diffopts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
674 diffopts
.recursive
= 1;
677 for (parents
= commit
->parents
, num_parent
= 0;
679 parents
= parents
->next
, num_parent
++)
682 /* find set of paths that everybody touches */
683 for (parents
= commit
->parents
, i
= 0;
685 parents
= parents
->next
, i
++) {
686 struct commit
*parent
= parents
->item
;
687 diff_tree_sha1(parent
->object
.sha1
, commit
->object
.sha1
, "",
689 paths
= intersect_paths(paths
, i
, num_parent
);
690 diff_flush(&diffopts
);
693 /* find out surviving paths */
694 for (num_paths
= 0, p
= paths
; p
; p
= p
->next
) {
698 if (num_paths
|| show_empty_merge
) {
699 for (p
= paths
; p
; p
= p
->next
) {
702 if (show_combined_diff(p
, num_parent
, dense
, header
,
708 /* Clean things up */
710 struct combine_diff_path
*tmp
= paths
;