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);
71 /* Lines lost from parent */
75 unsigned long parent_map
;
76 char line
[FLEX_ARRAY
];
79 /* Lines surviving in the merge result */
81 struct lline
*lost_head
, **lost_tail
;
84 /* bit 0 up to (N-1) are on if the parent does _not_
85 * have this line (i.e. we changed it).
86 * bit N is used for "interesting" lines, including context.
91 static char *grab_blob(const unsigned char *sha1
, unsigned long *size
)
95 if (!memcmp(sha1
, null_sha1
, 20)) {
100 blob
= read_sha1_file(sha1
, type
, size
);
101 if (strcmp(type
, "blob"))
102 die("object '%s' is not a blob!", sha1_to_hex(sha1
));
106 #define TMPPATHLEN 50
107 #define MAXLINELEN 10240
109 static void write_to_temp_file(char *tmpfile
, void *blob
, unsigned long size
)
111 int fd
= git_mkstemp(tmpfile
, TMPPATHLEN
, ".diff_XXXXXX");
113 die("unable to create temp-file");
114 if (write(fd
, blob
, size
) != size
)
115 die("unable to write temp-file");
119 static void write_temp_blob(char *tmpfile
, const unsigned char *sha1
)
123 blob
= grab_blob(sha1
, &size
);
124 write_to_temp_file(tmpfile
, blob
, size
);
128 static int parse_num(char **cp_p
, unsigned int *num_p
)
131 unsigned int num
= 0;
134 while ('0' <= *cp
&& *cp
<= '9')
135 num
= num
* 10 + *cp
++ - '0';
136 if (!(read_some
= cp
- *cp_p
))
143 static int parse_hunk_header(char *line
, int len
,
144 unsigned int *ob
, unsigned int *on
,
145 unsigned int *nb
, unsigned int *nn
)
149 if (parse_num(&cp
, ob
)) {
151 return error("malformed diff output: %s", line
);
155 if (parse_num(&cp
, on
))
160 if (*cp
++ != ' ' || *cp
++ != '+')
162 if (parse_num(&cp
, nb
))
166 if (parse_num(&cp
, nn
))
171 return -!!memcmp(cp
, " @@", 3);
174 static void append_lost(struct sline
*sline
, int n
, const char *line
)
177 int len
= strlen(line
);
178 unsigned long this_mask
= (1UL<<n
);
179 if (line
[len
-1] == '\n')
182 /* Check to see if we can squash things */
183 if (sline
->lost_head
) {
184 struct lline
*last_one
= NULL
;
185 /* We cannot squash it with earlier one */
186 for (lline
= sline
->lost_head
;
189 if (lline
->parent_map
& this_mask
)
191 lline
= last_one
? last_one
->next
: sline
->lost_head
;
193 if (lline
->len
== len
&&
194 !memcmp(lline
->line
, line
, len
)) {
195 lline
->parent_map
|= this_mask
;
202 lline
= xmalloc(sizeof(*lline
) + len
+ 1);
205 lline
->parent_map
= this_mask
;
206 memcpy(lline
->line
, line
, len
);
207 lline
->line
[len
] = 0;
208 *sline
->lost_tail
= lline
;
209 sline
->lost_tail
= &lline
->next
;
212 static void combine_diff(const unsigned char *parent
, const char *ourtmp
,
213 struct sline
*sline
, int cnt
, int n
)
216 char parent_tmp
[TMPPATHLEN
];
217 char cmd
[TMPPATHLEN
* 2 + 1024];
218 char line
[MAXLINELEN
];
219 unsigned int lno
, ob
, on
, nb
, nn
;
220 unsigned long pmask
= ~(1UL << n
);
221 struct sline
*lost_bucket
= NULL
;
223 write_temp_blob(parent_tmp
, parent
);
224 sprintf(cmd
, "diff --unified=0 -La/x -Lb/x '%s' '%s'",
226 in
= popen(cmd
, "r");
231 while (fgets(line
, sizeof(line
), in
) != NULL
) {
232 int len
= strlen(line
);
233 if (5 < len
&& !memcmp("@@ -", line
, 4)) {
234 if (parse_hunk_header(line
, len
,
239 /* @@ -1,2 +0,0 @@ to remove the
245 lost_bucket
= &sline
[nb
];
247 lost_bucket
= &sline
[nb
-1];
251 continue; /* not in any hunk yet */
254 append_lost(lost_bucket
, n
, line
+1);
257 sline
[lno
-1].flag
&= pmask
;
266 static unsigned long context
= 3;
267 static char combine_marker
= '@';
269 static int interesting(struct sline
*sline
, unsigned long all_mask
)
271 return ((sline
->flag
& all_mask
) != all_mask
|| sline
->lost_head
);
274 static unsigned long adjust_hunk_tail(struct sline
*sline
,
275 unsigned long all_mask
,
276 unsigned long hunk_begin
,
279 /* i points at the first uninteresting line.
280 * If the last line of the hunk was interesting
281 * only because it has some deletion, then
282 * it is not all that interesting for the
283 * purpose of giving trailing context lines.
285 if ((hunk_begin
+ 1 <= i
) &&
286 ((sline
[i
-1].flag
& all_mask
) == all_mask
))
291 static unsigned long next_interesting(struct sline
*sline
,
299 !(sline
[i
].flag
& mark
) :
300 (sline
[i
].flag
& mark
))
307 static int give_context(struct sline
*sline
, unsigned long cnt
, int num_parent
)
309 unsigned long all_mask
= (1UL<<num_parent
) - 1;
310 unsigned long mark
= (1UL<<num_parent
);
313 i
= next_interesting(sline
, mark
, 0, cnt
, 0);
318 unsigned long j
= (context
< i
) ? (i
- context
) : 0;
321 sline
[j
++].flag
|= mark
;
324 j
= next_interesting(sline
, mark
, i
, cnt
, 1);
326 break; /* the rest are all interesting */
328 /* lookahead context lines */
329 k
= next_interesting(sline
, mark
, j
, cnt
, 0);
330 j
= adjust_hunk_tail(sline
, all_mask
, i
, j
);
332 if (k
< j
+ context
) {
333 /* k is interesting and [j,k) are not, but
334 * paint them interesting because the gap is small.
337 sline
[j
++].flag
|= mark
;
342 /* j is the first uninteresting line and there is
343 * no overlap beyond it within context lines.
346 k
= (j
+ context
< cnt
) ? j
+ context
: cnt
;
348 sline
[j
++].flag
|= mark
;
353 static int make_hunks(struct sline
*sline
, unsigned long cnt
,
354 int num_parent
, int dense
)
356 unsigned long all_mask
= (1UL<<num_parent
) - 1;
357 unsigned long mark
= (1UL<<num_parent
);
359 int has_interesting
= 0;
361 for (i
= 0; i
< cnt
; i
++) {
362 if (interesting(&sline
[i
], all_mask
))
363 sline
[i
].flag
|= mark
;
365 sline
[i
].flag
&= ~mark
;
368 return give_context(sline
, cnt
, num_parent
);
370 /* Look at each hunk, and if we have changes from only one
371 * parent, or the changes are the same from all but one
372 * parent, mark that uninteresting.
376 unsigned long j
, hunk_begin
, hunk_end
;
377 unsigned long same_diff
;
378 while (i
< cnt
&& !(sline
[i
].flag
& mark
))
381 break; /* No more interesting hunks */
383 for (j
= i
+ 1; j
< cnt
; j
++) {
384 if (!(sline
[j
].flag
& mark
)) {
385 /* Look beyond the end to see if there
386 * is an interesting line after this
387 * hunk within context span.
389 unsigned long la
; /* lookahead */
391 la
= adjust_hunk_tail(sline
, all_mask
,
393 la
= (la
+ context
< cnt
) ?
394 (la
+ context
) : cnt
;
396 if (sline
[la
].flag
& mark
) {
408 /* [i..hunk_end) are interesting. Now is it really
409 * interesting? We check if there are only two versions
410 * and the result matches one of them. That is, we look
412 * (+) line, which records lines added to which parents;
413 * this line appears in the result.
414 * (-) line, which records from what parents the line
415 * was removed; this line does not appear in the result.
416 * then check the set of parents the result has difference
417 * from, from all lines. If there are lines that has
418 * different set of parents that the result has differences
419 * from, that means we have more than two versions.
421 * Even when we have only two versions, if the result does
422 * not match any of the parents, the it should be considered
423 * interesting. In such a case, we would have all '+' line.
424 * After passing the above "two versions" test, that would
425 * appear as "the same set of parents" to be "all parents".
429 for (j
= i
; j
< hunk_end
&& !has_interesting
; j
++) {
430 unsigned long this_diff
= ~sline
[j
].flag
& all_mask
;
431 struct lline
*ll
= sline
[j
].lost_head
;
433 /* This has some changes. Is it the
437 same_diff
= this_diff
;
438 else if (same_diff
!= this_diff
) {
443 while (ll
&& !has_interesting
) {
444 /* Lost this line from these parents;
445 * who are they? Are they the same?
447 this_diff
= ll
->parent_map
;
449 same_diff
= this_diff
;
450 else if (same_diff
!= this_diff
) {
457 if (!has_interesting
&& same_diff
!= all_mask
) {
458 /* This hunk is not that interesting after all */
459 for (j
= hunk_begin
; j
< hunk_end
; j
++)
460 sline
[j
].flag
&= ~mark
;
465 has_interesting
= give_context(sline
, cnt
, num_parent
);
466 return has_interesting
;
469 static void dump_sline(struct sline
*sline
, int cnt
, int num_parent
)
471 unsigned long mark
= (1UL<<num_parent
);
476 struct sline
*sl
= &sline
[lno
];
478 while (lno
< cnt
&& !(sline
[lno
].flag
& mark
))
482 for (hunk_end
= lno
+ 1; hunk_end
< cnt
; hunk_end
++)
483 if (!(sline
[hunk_end
].flag
& mark
))
485 for (i
= 0; i
<= num_parent
; i
++) putchar(combine_marker
);
486 printf(" +%d,%d ", lno
+1, hunk_end
-lno
);
487 for (i
= 0; i
<= num_parent
; i
++) putchar(combine_marker
);
489 while (lno
< hunk_end
) {
495 for (j
= 0; j
< num_parent
; j
++) {
496 if (ll
->parent_map
& (1UL<<j
))
504 for (j
= 0; j
< num_parent
; j
++) {
505 if ((1UL<<j
) & sl
->flag
)
510 printf("%.*s\n", sl
->len
, sl
->bol
);
515 static void reuse_combine_diff(struct sline
*sline
, unsigned long cnt
,
518 /* We have already examined parent j and we know parent i
519 * and parent j are the same, so reuse the combined result
520 * of parent j for parent i.
522 unsigned long lno
, imask
, jmask
;
526 for (lno
= 0; lno
< cnt
; lno
++) {
527 struct lline
*ll
= sline
->lost_head
;
529 if (ll
->parent_map
& jmask
)
530 ll
->parent_map
|= imask
;
533 if (!(sline
->flag
& jmask
))
534 sline
->flag
&= ~imask
;
539 int show_combined_diff(struct combine_diff_path
*elem
, int num_parent
,
540 int dense
, const char *header
, int show_empty
)
542 unsigned long size
, cnt
, lno
;
543 char *result
, *cp
, *ep
;
544 struct sline
*sline
; /* survived lines */
545 int i
, show_hunks
, shown_header
= 0;
546 char ourtmp_buf
[TMPPATHLEN
];
547 char *ourtmp
= ourtmp_buf
;
549 /* Read the result of merge first */
550 if (memcmp(elem
->sha1
, null_sha1
, 20)) {
551 result
= grab_blob(elem
->sha1
, &size
);
552 write_to_temp_file(ourtmp
, result
, size
);
558 if (0 <= (fd
= open(ourtmp
, O_RDONLY
)) &&
560 int len
= st
.st_size
;
564 result
= xmalloc(len
+ 1);
566 int done
= xread(fd
, result
+cnt
, len
-cnt
);
570 die("read error '%s'", ourtmp
);
580 ourtmp
= "/dev/null";
586 for (cnt
= 0, cp
= result
; cp
- result
< size
; cp
++) {
590 if (result
[size
-1] != '\n')
591 cnt
++; /* incomplete line */
593 sline
= xcalloc(cnt
, sizeof(*sline
));
595 sline
[0].bol
= result
;
596 for (lno
= 0, cp
= result
; cp
- result
< size
; cp
++) {
598 sline
[lno
].lost_tail
= &sline
[lno
].lost_head
;
599 sline
[lno
].len
= cp
- sline
[lno
].bol
;
600 sline
[lno
].flag
= (1UL<<num_parent
) - 1;
603 sline
[lno
].bol
= cp
+ 1;
606 if (result
[size
-1] != '\n') {
607 sline
[cnt
-1].lost_tail
= &sline
[cnt
-1].lost_head
;
608 sline
[cnt
-1].len
= size
- (sline
[cnt
-1].bol
- result
);
609 sline
[cnt
-1].flag
= (1UL<<num_parent
) - 1;
612 for (i
= 0; i
< num_parent
; i
++) {
614 for (j
= 0; j
< i
; j
++) {
615 if (!memcmp(elem
->parent_sha1
[i
],
616 elem
->parent_sha1
[j
], 20)) {
617 reuse_combine_diff(sline
, cnt
, i
, j
);
622 combine_diff(elem
->parent_sha1
[i
], ourtmp
, sline
,
626 show_hunks
= make_hunks(sline
, cnt
, num_parent
, dense
);
628 if (header
&& (show_hunks
|| show_empty
)) {
633 printf("diff --%s ", dense
? "cc" : "combined");
634 if (quote_c_style(elem
->path
, NULL
, NULL
, 0))
635 quote_c_style(elem
->path
, NULL
, stdout
, 0);
637 printf("%s", elem
->path
);
640 for (i
= 0; i
< num_parent
; i
++) {
643 find_unique_abbrev(elem
->parent_sha1
[i
],
647 find_unique_abbrev(elem
->sha1
, DEFAULT_ABBREV
));
648 dump_sline(sline
, cnt
, num_parent
);
650 if (ourtmp
== ourtmp_buf
)
654 for (i
= 0; i
< cnt
; i
++) {
655 if (sline
[i
].lost_head
) {
656 struct lline
*ll
= sline
[i
].lost_head
;
658 struct lline
*tmp
= ll
;
668 int diff_tree_combined_merge(const unsigned char *sha1
,
670 int show_empty_merge
, int dense
)
672 struct commit
*commit
= lookup_commit(sha1
);
673 struct diff_options diffopts
;
674 struct commit_list
*parents
;
675 struct combine_diff_path
*p
, *paths
= NULL
;
676 int num_parent
, i
, num_paths
;
678 diff_setup(&diffopts
);
679 diffopts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
680 diffopts
.recursive
= 1;
683 for (parents
= commit
->parents
, num_parent
= 0;
685 parents
= parents
->next
, num_parent
++)
688 /* find set of paths that everybody touches */
689 for (parents
= commit
->parents
, i
= 0;
691 parents
= parents
->next
, i
++) {
692 struct commit
*parent
= parents
->item
;
693 diff_tree_sha1(parent
->object
.sha1
, commit
->object
.sha1
, "",
695 paths
= intersect_paths(paths
, i
, num_parent
);
696 diff_flush(&diffopts
);
699 /* find out surviving paths */
700 for (num_paths
= 0, p
= paths
; p
; p
= p
->next
) {
704 if (num_paths
|| show_empty_merge
) {
705 for (p
= paths
; p
; p
= p
->next
) {
708 if (show_combined_diff(p
, num_parent
, dense
, header
,
714 /* Clean things up */
716 struct combine_diff_path
*tmp
= paths
;