8 struct path_list
*next
;
11 unsigned char sha1
[20];
12 unsigned char parent_sha1
[FLEX_ARRAY
][20];
15 static int uninteresting(struct diff_filepair
*p
)
17 if (diff_unmodified_pair(p
))
19 if (!S_ISREG(p
->one
->mode
) || !S_ISREG(p
->two
->mode
))
24 static struct path_list
*intersect_paths(struct path_list
*curr
,
25 int n
, int num_parent
)
27 struct diff_queue_struct
*q
= &diff_queued_diff
;
32 struct path_list
*list
= NULL
, **tail
= &list
;
33 for (i
= 0; i
< q
->nr
; i
++) {
36 if (uninteresting(q
->queue
[i
]))
38 path
= q
->queue
[i
]->two
->path
;
41 p
= xmalloc(sizeof(*p
) + len
+ 1 + num_parent
* 20);
42 p
->path
= (char*) &(p
->parent_sha1
[num_parent
][0]);
43 memcpy(p
->path
, path
, len
);
47 memcpy(p
->sha1
, q
->queue
[i
]->two
->sha1
, 20);
48 memcpy(p
->parent_sha1
[n
], q
->queue
[i
]->one
->sha1
, 20);
55 for (p
= curr
; p
; p
= p
->next
) {
59 for (i
= 0; i
< q
->nr
; i
++) {
63 if (uninteresting(q
->queue
[i
]))
65 path
= q
->queue
[i
]->two
->path
;
67 if (len
== p
->len
&& !memcmp(path
, p
->path
, len
)) {
69 memcpy(p
->parent_sha1
[n
],
70 q
->queue
[i
]->one
->sha1
, 20);
83 unsigned long parent_map
;
84 char line
[FLEX_ARRAY
];
88 struct lline
*lost_head
, **lost_tail
;
94 static char *grab_blob(const unsigned char *sha1
, unsigned long *size
)
98 if (!memcmp(sha1
, null_sha1
, 20)) {
101 return xcalloc(1, 1);
103 blob
= read_sha1_file(sha1
, type
, size
);
104 if (strcmp(type
, "blob"))
105 die("object '%s' is not a blob!", sha1_to_hex(sha1
));
109 #define TMPPATHLEN 50
110 #define MAXLINELEN 10240
112 static void write_to_temp_file(char *tmpfile
, void *blob
, unsigned long size
)
114 int fd
= git_mkstemp(tmpfile
, TMPPATHLEN
, ".diff_XXXXXX");
116 die("unable to create temp-file");
117 if (write(fd
, blob
, size
) != size
)
118 die("unable to write temp-file");
122 static void write_temp_blob(char *tmpfile
, const unsigned char *sha1
)
126 blob
= grab_blob(sha1
, &size
);
127 write_to_temp_file(tmpfile
, blob
, size
);
131 static int parse_num(char **cp_p
, unsigned int *num_p
)
134 unsigned int num
= 0;
137 while ('0' <= *cp
&& *cp
<= '9')
138 num
= num
* 10 + *cp
++ - '0';
139 if (!(read_some
= cp
- *cp_p
))
146 static int parse_hunk_header(char *line
, int len
,
147 unsigned int *ob
, unsigned int *on
,
148 unsigned int *nb
, unsigned int *nn
)
152 if (parse_num(&cp
, ob
)) {
154 return error("malformed diff output: %s", line
);
158 if (parse_num(&cp
, on
))
163 if (*cp
++ != ' ' || *cp
++ != '+')
165 if (parse_num(&cp
, nb
))
169 if (parse_num(&cp
, nn
))
174 return -!!memcmp(cp
, " @@", 3);
177 static void append_lost(struct sline
*sline
, int n
, const char *line
)
180 int len
= strlen(line
);
181 unsigned long this_mask
= (1UL<<n
);
182 if (line
[len
-1] == '\n')
185 /* Check to see if we can squash things */
186 if (sline
->lost_head
) {
187 struct lline
*last_one
= NULL
;
188 /* We cannot squash it with earlier one */
189 for (lline
= sline
->lost_head
;
192 if (lline
->parent_map
& this_mask
)
194 lline
= last_one
? last_one
->next
: sline
->lost_head
;
196 if (lline
->len
== len
&&
197 !memcmp(lline
->line
, line
, len
)) {
198 lline
->parent_map
|= this_mask
;
205 lline
= xmalloc(sizeof(*lline
) + len
+ 1);
208 lline
->parent_map
= this_mask
;
209 memcpy(lline
->line
, line
, len
);
210 lline
->line
[len
] = 0;
211 *sline
->lost_tail
= lline
;
212 sline
->lost_tail
= &lline
->next
;
215 static void combine_diff(const unsigned char *parent
, const char *ourtmp
,
216 struct sline
*sline
, int cnt
, int n
)
219 char parent_tmp
[TMPPATHLEN
];
220 char cmd
[TMPPATHLEN
* 2 + 1024];
221 char line
[MAXLINELEN
];
222 unsigned int lno
, ob
, on
, nb
, nn
;
223 unsigned long pmask
= ~(1UL << n
);
224 struct sline
*lost_bucket
= NULL
;
226 write_temp_blob(parent_tmp
, parent
);
227 sprintf(cmd
, "diff --unified=0 -La/x -Lb/x '%s' '%s'",
229 in
= popen(cmd
, "r");
234 while (fgets(line
, sizeof(line
), in
) != NULL
) {
235 int len
= strlen(line
);
236 if (5 < len
&& !memcmp("@@ -", line
, 4)) {
237 if (parse_hunk_header(line
, len
,
242 /* @@ -1,2 +0,0 @@ to remove the
247 lost_bucket
= &sline
[nb
-1]; /* sline is 0 based */
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 line_common_diff(struct sline
*sline
, unsigned long all_mask
)
277 * Look at the line and see from which parents we have the
281 /* Lower bits of sline->flag records if the parent had this
282 * line, so XOR with all_mask gives us on-bits for parents we
283 * have differences with.
285 unsigned long common_adds
= (sline
->flag
^ all_mask
) & all_mask
;
286 unsigned long common_removes
= all_mask
;
288 /* If all the parents have this line, that also counts as
289 * having the same difference.
292 common_adds
= all_mask
;
294 if (sline
->lost_head
) {
295 /* Lost head list records the lines removed from
296 * the parents, and parent_map records from which
297 * parent the line was removed.
300 for (ll
= sline
->lost_head
; ll
; ll
= ll
->next
) {
301 common_removes
&= ll
->parent_map
;
304 return common_adds
& common_removes
;
307 static unsigned long line_all_diff(struct sline
*sline
, unsigned long all_mask
)
310 * Look at the line and see from which parents we have some difference.
312 unsigned long different
= (sline
->flag
^ all_mask
) & all_mask
;
313 if (sline
->lost_head
) {
314 /* Lost head list records the lines removed from
315 * the parents, and parent_map records from which
316 * parent the line was removed.
319 for (ll
= sline
->lost_head
; ll
; ll
= ll
->next
) {
320 different
|= ll
->parent_map
;
326 static unsigned long adjust_hunk_tail(struct sline
*sline
,
327 unsigned long all_mask
,
328 unsigned long hunk_begin
,
331 /* i points at the first uninteresting line.
332 * If the last line of the hunk was interesting
333 * only because it has some deletion, then
334 * it is not all that interesting for the
335 * purpose of giving trailing context lines.
337 if ((hunk_begin
+ 1 <= i
) &&
338 ((sline
[i
-1].flag
& all_mask
) == all_mask
))
343 static unsigned long next_interesting(struct sline
*sline
,
351 !(sline
[i
].flag
& mark
) :
352 (sline
[i
].flag
& mark
))
359 static int give_context(struct sline
*sline
, unsigned long cnt
, int num_parent
)
361 unsigned long all_mask
= (1UL<<num_parent
) - 1;
362 unsigned long mark
= (1UL<<num_parent
);
365 i
= next_interesting(sline
, mark
, 0, cnt
, 0);
370 unsigned long j
= (context
< i
) ? (i
- context
) : 0;
373 sline
[j
++].flag
|= mark
;
376 j
= next_interesting(sline
, mark
, i
, cnt
, 1);
378 break; /* the rest are all interesting */
380 /* lookahead context lines */
381 k
= next_interesting(sline
, mark
, j
, cnt
, 0);
382 j
= adjust_hunk_tail(sline
, all_mask
, i
, j
);
384 if (k
< j
+ context
) {
385 /* k is interesting and [j,k) are not, but
386 * paint them interesting because the gap is small.
389 sline
[j
++].flag
|= mark
;
394 /* j is the first uninteresting line and there is
395 * no overlap beyond it within context lines.
398 k
= (j
+ context
< cnt
) ? j
+ context
: cnt
;
400 sline
[j
++].flag
|= mark
;
405 static int make_hunks(struct sline
*sline
, unsigned long cnt
,
406 int num_parent
, int dense
)
408 unsigned long all_mask
= (1UL<<num_parent
) - 1;
409 unsigned long mark
= (1UL<<num_parent
);
411 int has_interesting
= 0;
413 for (i
= 0; i
< cnt
; i
++) {
414 if (interesting(&sline
[i
], all_mask
))
415 sline
[i
].flag
|= mark
;
417 sline
[i
].flag
&= ~mark
;
420 return give_context(sline
, cnt
, num_parent
);
422 /* Look at each hunk, and if we have changes from only one
423 * parent, or the changes are the same from all but one
424 * parent, mark that uninteresting.
428 unsigned long j
, hunk_begin
, hunk_end
;
430 unsigned long same_diff
, all_diff
;
431 while (i
< cnt
&& !(sline
[i
].flag
& mark
))
434 break; /* No more interesting hunks */
436 for (j
= i
+ 1; j
< cnt
; j
++) {
437 if (!(sline
[j
].flag
& mark
)) {
438 /* Look beyond the end to see if there
439 * is an interesting line after this
440 * hunk within context span.
442 unsigned long la
; /* lookahead */
444 la
= adjust_hunk_tail(sline
, all_mask
,
446 la
= (la
+ context
< cnt
) ?
447 (la
+ context
) : cnt
;
449 if (sline
[la
].flag
& mark
) {
461 /* [i..hunk_end) are interesting. Now does it have
462 * the same change with all but one parent?
464 same_diff
= all_mask
;
466 for (j
= i
; j
< hunk_end
; j
++) {
467 same_diff
&= line_common_diff(sline
+ j
, all_mask
);
468 all_diff
|= line_all_diff(sline
+ j
, all_mask
);
471 for (j
= 0; j
< num_parent
; j
++) {
472 if (same_diff
& (1UL<<j
))
474 if (all_diff
& (1UL<<j
))
477 if ((num_parent
- 1 <= same
) || (diff
== 1)) {
478 /* This hunk is not that interesting after all */
479 for (j
= hunk_begin
; j
< hunk_end
; j
++)
480 sline
[j
].flag
&= ~mark
;
485 has_interesting
= give_context(sline
, cnt
, num_parent
);
486 return has_interesting
;
489 static void dump_sline(struct sline
*sline
, int cnt
, int num_parent
)
491 unsigned long mark
= (1UL<<num_parent
);
496 struct sline
*sl
= &sline
[lno
];
498 while (lno
< cnt
&& !(sline
[lno
].flag
& mark
))
502 for (hunk_end
= lno
+ 1; hunk_end
< cnt
; hunk_end
++)
503 if (!(sline
[hunk_end
].flag
& mark
))
505 for (i
= 0; i
<= num_parent
; i
++) putchar(combine_marker
);
506 printf(" +%d,%d ", lno
+1, hunk_end
-lno
);
507 for (i
= 0; i
<= num_parent
; i
++) putchar(combine_marker
);
509 while (lno
< hunk_end
) {
515 for (j
= 0; j
< num_parent
; j
++) {
516 if (ll
->parent_map
& (1UL<<j
))
524 for (j
= 0; j
< num_parent
; j
++) {
525 if ((1UL<<j
) & sl
->flag
)
530 printf("%.*s\n", sl
->len
, sl
->bol
);
535 static int show_combined_diff(struct path_list
*elem
, int num_parent
,
536 int dense
, const char *header
, int show_empty
)
538 unsigned long size
, cnt
, lno
;
539 char *result
, *cp
, *ep
;
540 struct sline
*sline
; /* survived lines */
541 int i
, show_hunks
, shown_header
= 0;
542 char ourtmp
[TMPPATHLEN
];
544 /* Read the result of merge first */
545 result
= grab_blob(elem
->sha1
, &size
);
546 write_to_temp_file(ourtmp
, result
, size
);
548 for (cnt
= 0, cp
= result
; cp
- result
< size
; cp
++) {
552 if (result
[size
-1] != '\n')
553 cnt
++; /* incomplete line */
555 sline
= xcalloc(cnt
, sizeof(*sline
));
557 sline
[0].bol
= result
;
558 for (lno
= 0, cp
= result
; cp
- result
< size
; cp
++) {
560 sline
[lno
].lost_tail
= &sline
[lno
].lost_head
;
561 sline
[lno
].len
= cp
- sline
[lno
].bol
;
562 sline
[lno
].flag
= (1UL<<num_parent
) - 1;
565 sline
[lno
].bol
= cp
+ 1;
568 if (result
[size
-1] != '\n') {
569 sline
[cnt
-1].lost_tail
= &sline
[cnt
-1].lost_head
;
570 sline
[cnt
-1].len
= size
- (sline
[cnt
-1].bol
- result
);
571 sline
[cnt
-1].flag
= (1UL<<num_parent
) - 1;
574 for (i
= 0; i
< num_parent
; i
++)
575 combine_diff(elem
->parent_sha1
[i
], ourtmp
, sline
, cnt
, i
);
577 show_hunks
= make_hunks(sline
, cnt
, num_parent
, dense
);
579 if (header
&& (show_hunks
|| show_empty
)) {
584 printf("diff --%s ", dense
? "cc" : "combined");
585 if (quote_c_style(elem
->path
, NULL
, NULL
, 0))
586 quote_c_style(elem
->path
, NULL
, stdout
, 0);
588 printf("%s", elem
->path
);
590 dump_sline(sline
, cnt
, num_parent
);
595 for (i
= 0; i
< cnt
; i
++) {
596 if (sline
[i
].lost_head
) {
597 struct lline
*ll
= sline
[i
].lost_head
;
599 struct lline
*tmp
= ll
;
609 int diff_tree_combined_merge(const unsigned char *sha1
,
611 int show_empty_merge
, int dense
)
613 struct commit
*commit
= lookup_commit(sha1
);
614 struct diff_options diffopts
;
615 struct commit_list
*parents
;
616 struct path_list
*p
, *paths
= NULL
;
617 int num_parent
, i
, num_paths
;
619 diff_setup(&diffopts
);
620 diffopts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
621 diffopts
.recursive
= 1;
624 for (parents
= commit
->parents
, num_parent
= 0;
626 parents
= parents
->next
, num_parent
++)
629 /* find set of paths that everybody touches */
630 for (parents
= commit
->parents
, i
= 0;
632 parents
= parents
->next
, i
++) {
633 struct commit
*parent
= parents
->item
;
634 diff_tree_sha1(parent
->object
.sha1
, commit
->object
.sha1
, "",
636 paths
= intersect_paths(paths
, i
, num_parent
);
637 diff_flush(&diffopts
);
640 /* find out surviving paths */
641 for (num_paths
= 0, p
= paths
; p
; p
= p
->next
) {
645 if (num_paths
|| show_empty_merge
) {
646 for (p
= paths
; p
; p
= p
->next
) {
649 if (show_combined_diff(p
, num_parent
, dense
, header
,
655 /* Clean things up */
657 struct path_list
*tmp
= paths
;