2 * Copyright (C) 2005 Junio C Hamano
12 static const char *diff_opts
= "-pu";
13 static unsigned char null_sha1
[20] = { 0, };
14 #define MAX_SCORE 10000
15 #define DEFAULT_MINIMUM_SCORE 5000
17 static const char *external_diff(void)
19 static const char *external_diff_cmd
= NULL
;
20 static int done_preparing
= 0;
23 return external_diff_cmd
;
26 * Default values above are meant to match the
27 * Linux kernel development style. Examples of
28 * alternative styles you can specify via environment
33 if (gitenv("GIT_EXTERNAL_DIFF"))
34 external_diff_cmd
= gitenv("GIT_EXTERNAL_DIFF");
36 /* In case external diff fails... */
37 diff_opts
= gitenv("GIT_DIFF_OPTS") ? : diff_opts
;
40 return external_diff_cmd
;
43 /* Help to copy the thing properly quoted for the shell safety.
44 * any single quote is replaced with '\'', and the caller is
45 * expected to enclose the result within a single quote pair.
48 * original sq_expand result
49 * name ==> name ==> 'name'
50 * a b ==> a b ==> 'a b'
51 * a'b ==> a'\''b ==> 'a'\''b'
53 static char *sq_expand(const char *src
)
55 static char *buf
= NULL
;
60 /* count bytes needed to store the quoted string. */
61 for (cnt
= 1, cp
= src
; *cp
; cnt
++, cp
++)
67 while ((c
= *src
++)) {
71 bp
= strcpy(bp
, "'\\''");
79 static struct diff_tempfile
{
87 unsigned char blob_sha1
[20];
88 unsigned short mode
; /* file mode */
89 unsigned sha1_valid
: 1; /* if true, use blob_sha1 and trust mode;
90 * if false, use the name and read from
93 unsigned file_valid
: 1; /* if false the file does not exist */
96 static void builtin_diff(const char *name_a
,
98 struct diff_tempfile
*temp
,
101 int i
, next_at
, cmd_size
;
102 const char *diff_cmd
= "diff -L'%s%s' -L'%s%s'";
103 const char *diff_arg
= "'%s' '%s'||:"; /* "||:" is to return 0 */
104 const char *input_name_sq
[2];
105 const char *path0
[2];
106 const char *path1
[2];
107 const char *name_sq
[2];
110 name_sq
[0] = sq_expand(name_a
);
111 name_sq
[1] = sq_expand(name_b
);
113 /* diff_cmd and diff_arg have 6 %s in total which makes
114 * the sum of these strings 12 bytes larger than required.
115 * we use 2 spaces around diff-opts, and we need to count
116 * terminating NUL, so we subtract 9 here.
118 cmd_size
= (strlen(diff_cmd
) + strlen(diff_opts
) +
119 strlen(diff_arg
) - 9);
120 for (i
= 0; i
< 2; i
++) {
121 input_name_sq
[i
] = sq_expand(temp
[i
].name
);
122 if (!strcmp(temp
[i
].name
, "/dev/null")) {
123 path0
[i
] = "/dev/null";
126 path0
[i
] = i
? "b/" : "a/";
127 path1
[i
] = name_sq
[i
];
129 cmd_size
+= (strlen(path0
[i
]) + strlen(path1
[i
]) +
130 strlen(input_name_sq
[i
]));
133 cmd
= xmalloc(cmd_size
);
136 next_at
+= snprintf(cmd
+next_at
, cmd_size
-next_at
,
138 path0
[0], path1
[0], path0
[1], path1
[1]);
139 next_at
+= snprintf(cmd
+next_at
, cmd_size
-next_at
,
141 next_at
+= snprintf(cmd
+next_at
, cmd_size
-next_at
,
142 diff_arg
, input_name_sq
[0], input_name_sq
[1]);
144 printf("diff --git a/%s b/%s\n", name_a
, name_b
);
146 printf("new file mode %s\n", temp
[1].mode
);
147 else if (!path1
[1][0])
148 printf("deleted file mode %s\n", temp
[0].mode
);
150 if (strcmp(temp
[0].mode
, temp
[1].mode
)) {
151 printf("old mode %s\n", temp
[0].mode
);
152 printf("new mode %s\n", temp
[1].mode
);
154 if (strcmp(name_a
, name_b
)) {
155 if (0 < rename_score
)
156 printf("rename similarity index %d%%\n",
158 rename_score
*100.0/MAX_SCORE
));
159 printf("rename old %s\n", name_a
);
160 printf("rename new %s\n", name_b
);
162 if (strncmp(temp
[0].mode
, temp
[1].mode
, 3))
163 /* we do not run diff between different kind
169 execlp("/bin/sh","sh", "-c", cmd
, NULL
);
173 * Given a name and sha1 pair, if the dircache tells us the file in
174 * the work tree has that object contents, return true, so that
175 * prepare_temp_file() does not have to inflate and extract.
177 static int work_tree_matches(const char *name
, const unsigned char *sha1
)
179 struct cache_entry
*ce
;
183 /* We do not read the cache ourselves here, because the
184 * benchmark with my previous version that always reads cache
185 * shows that it makes things worse for diff-tree comparing
186 * two linux-2.6 kernel trees in an already checked out work
187 * tree. This is because most diff-tree comparisons deal with
188 * only a small number of files, while reading the cache is
189 * expensive for a large project, and its cost outweighs the
190 * savings we get by not inflating the object to a temporary
191 * file. Practically, this code only helps when we are used
192 * by diff-cache --cached, which does read the cache before
199 pos
= cache_name_pos(name
, len
);
202 ce
= active_cache
[pos
];
203 if ((lstat(name
, &st
) < 0) ||
204 !S_ISREG(st
.st_mode
) ||
205 ce_match_stat(ce
, &st
) ||
206 memcmp(sha1
, ce
->sha1
, 20))
211 static void prep_temp_blob(struct diff_tempfile
*temp
,
219 strcpy(temp
->tmp_path
, ".diff_XXXXXX");
220 fd
= mkstemp(temp
->tmp_path
);
222 die("unable to create temp-file");
223 if (write(fd
, blob
, size
) != size
)
224 die("unable to write temp-file");
226 temp
->name
= temp
->tmp_path
;
227 strcpy(temp
->hex
, sha1_to_hex(sha1
));
229 sprintf(temp
->mode
, "%06o", mode
);
232 static void prepare_temp_file(const char *name
,
233 struct diff_tempfile
*temp
,
234 struct diff_spec
*one
)
236 if (!one
->file_valid
) {
238 /* A '-' entry produces this for file-2, and
239 * a '+' entry produces this for file-1.
241 temp
->name
= "/dev/null";
242 strcpy(temp
->hex
, ".");
243 strcpy(temp
->mode
, ".");
247 if (!one
->sha1_valid
||
248 work_tree_matches(name
, one
->blob_sha1
)) {
251 if (lstat(temp
->name
, &st
) < 0) {
253 goto not_a_valid_file
;
254 die("stat(%s): %s", temp
->name
, strerror(errno
));
256 if (S_ISLNK(st
.st_mode
)) {
258 char *buf
, buf_
[1024];
259 buf
= ((sizeof(buf_
) < st
.st_size
) ?
260 xmalloc(st
.st_size
) : buf_
);
261 ret
= readlink(name
, buf
, st
.st_size
);
263 die("readlink(%s)", name
);
264 prep_temp_blob(temp
, buf
, st
.st_size
,
266 one
->blob_sha1
: null_sha1
),
268 one
->mode
: S_IFLNK
));
271 if (!one
->sha1_valid
)
272 strcpy(temp
->hex
, sha1_to_hex(null_sha1
));
274 strcpy(temp
->hex
, sha1_to_hex(one
->blob_sha1
));
275 sprintf(temp
->mode
, "%06o",
276 S_IFREG
|ce_permissions(st
.st_mode
));
285 blob
= read_sha1_file(one
->blob_sha1
, type
, &size
);
286 if (!blob
|| strcmp(type
, "blob"))
287 die("unable to read blob object for %s (%s)",
288 name
, sha1_to_hex(one
->blob_sha1
));
289 prep_temp_blob(temp
, blob
, size
, one
->blob_sha1
, one
->mode
);
294 static void remove_tempfile(void)
298 for (i
= 0; i
< 2; i
++)
299 if (diff_temp
[i
].name
== diff_temp
[i
].tmp_path
) {
300 unlink(diff_temp
[i
].name
);
301 diff_temp
[i
].name
= NULL
;
305 static void remove_tempfile_on_signal(int signo
)
310 static int detect_rename
;
311 static int reverse_diff
;
312 static int diff_raw_output
= -1;
313 static const char **pathspec
;
315 static int minimum_score
;
317 static int matches_pathspec(const char *name
)
325 namelen
= strlen(name
);
326 for (i
= 0; i
< speccnt
; i
++) {
327 int speclen
= strlen(pathspec
[i
]);
328 if (! strncmp(pathspec
[i
], name
, speclen
) &&
329 speclen
<= namelen
&&
330 (name
[speclen
] == 0 || name
[speclen
] == '/'))
336 /* An external diff command takes:
338 * diff-cmd name infile1 infile1-sha1 infile1-mode \
339 * infile2 infile2-sha1 infile2-mode [ rename-to ]
342 static void run_external_diff(const char *name
,
344 struct diff_spec
*one
,
345 struct diff_spec
*two
,
348 struct diff_tempfile
*temp
= diff_temp
;
351 static int atexit_asked
= 0;
353 if (!matches_pathspec(name
) && (!other
|| !matches_pathspec(other
)))
357 prepare_temp_file(name
, &temp
[0], one
);
358 prepare_temp_file(other
? : name
, &temp
[1], two
);
359 if (! atexit_asked
&&
360 (temp
[0].name
== temp
[0].tmp_path
||
361 temp
[1].name
== temp
[1].tmp_path
)) {
363 atexit(remove_tempfile
);
365 signal(SIGINT
, remove_tempfile_on_signal
);
371 die("unable to fork");
373 const char *pgm
= external_diff();
376 const char *exec_arg
[9];
377 const char **arg
= &exec_arg
[0];
380 *arg
++ = temp
[0].name
;
381 *arg
++ = temp
[0].hex
;
382 *arg
++ = temp
[0].mode
;
383 *arg
++ = temp
[1].name
;
384 *arg
++ = temp
[1].hex
;
385 *arg
++ = temp
[1].mode
;
389 execvp(pgm
, (char *const*) exec_arg
);
392 execlp(pgm
, pgm
, name
, NULL
);
395 * otherwise we use the built-in one.
398 builtin_diff(name
, other
? : name
, temp
, rename_score
);
400 printf("* Unmerged path %s\n", name
);
403 if (waitpid(pid
, &status
, 0) < 0 ||
404 !WIFEXITED(status
) || WEXITSTATUS(status
)) {
405 /* Earlier we did not check the exit status because
406 * diff exits non-zero if files are different, and
407 * we are not interested in knowing that. It was a
408 * mistake which made it harder to quit a diff-*
409 * session that uses the git-apply-patch-script as
410 * the GIT_EXTERNAL_DIFF. A custom GIT_EXTERNAL_DIFF
411 * should also exit non-zero only when it wants to
412 * abort the entire diff-* session.
415 fprintf(stderr
, "external diff died, stopping at %s.\n", name
);
422 * We do not detect circular renames. Just hold created and deleted
423 * entries and later attempt to match them up. If they do not match,
424 * then spit them out as deletes or creates as original.
427 static struct diff_spec_hold
{
428 struct diff_spec_hold
*next
;
433 #define SHOULD_FREE 2
434 #define SHOULD_MUNMAP 4
437 } *createdfile
, *deletedfile
;
439 static void hold_diff(const char *name
,
440 struct diff_spec
*one
,
441 struct diff_spec
*two
)
443 struct diff_spec_hold
**list
, *elem
;
445 if (one
->file_valid
&& two
->file_valid
)
446 die("internal error");
448 if (!detect_rename
) {
449 run_external_diff(name
, NULL
, one
, two
, -1);
452 elem
= xmalloc(sizeof(*elem
) + strlen(name
));
453 strcpy(elem
->path
, name
);
457 if (one
->file_valid
) {
469 static int populate_data(struct diff_spec_hold
*s
)
475 if (s
->it
.sha1_valid
) {
476 s
->data
= read_sha1_file(s
->it
.blob_sha1
, type
, &s
->size
);
477 s
->flags
|= SHOULD_FREE
;
482 fd
= open(s
->path
, O_RDONLY
);
485 if (fstat(fd
, &st
)) {
489 s
->size
= st
.st_size
;
490 s
->data
= mmap(NULL
, s
->size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
495 s
->flags
|= SHOULD_MUNMAP
;
500 static void free_data(struct diff_spec_hold
*s
)
502 if (s
->flags
& SHOULD_FREE
)
504 else if (s
->flags
& SHOULD_MUNMAP
)
505 munmap(s
->data
, s
->size
);
506 s
->flags
&= ~(SHOULD_FREE
|SHOULD_MUNMAP
);
510 static void flush_remaining_diff(struct diff_spec_hold
*elem
,
513 static struct diff_spec null_file_spec
;
515 null_file_spec
.file_valid
= 0;
516 for ( ; elem
; elem
= elem
->next
) {
518 if (elem
->flags
& MATCHED
)
521 run_external_diff(elem
->path
, NULL
,
522 &null_file_spec
, &elem
->it
, -1);
524 run_external_diff(elem
->path
, NULL
,
525 &elem
->it
, &null_file_spec
, -1);
529 static int is_exact_match(struct diff_spec_hold
*src
,
530 struct diff_spec_hold
*dst
)
532 if (src
->it
.sha1_valid
&& dst
->it
.sha1_valid
&&
533 !memcmp(src
->it
.blob_sha1
, dst
->it
.blob_sha1
, 20))
535 if (populate_data(src
) || populate_data(dst
))
536 /* this is an error but will be caught downstream */
538 if (src
->size
== dst
->size
&&
539 !memcmp(src
->data
, dst
->data
, src
->size
))
544 static int estimate_similarity(struct diff_spec_hold
*src
, struct diff_spec_hold
*dst
)
546 /* src points at a deleted file and dst points at a created
547 * file. They may be quite similar, in which case we want to
548 * say src is renamed to dst.
550 * Compare them and return how similar they are, representing
551 * the score as an integer between 0 and 10000, except
552 * where they match exactly it is considered better than anything
556 unsigned long delta_size
;
559 delta_size
= ((src
->size
< dst
->size
) ?
560 (dst
->size
- src
->size
) : (src
->size
- dst
->size
));
562 /* We would not consider rename followed by more than
563 * minimum_score/MAX_SCORE edits; that is, delta_size must be smaller
564 * than (src->size + dst->size)/2 * minimum_score/MAX_SCORE,
568 if ((src
->size
+dst
->size
)*minimum_score
< delta_size
*MAX_SCORE
*2)
571 delta
= diff_delta(src
->data
, src
->size
,
572 dst
->data
, dst
->size
,
576 /* This "delta" is really xdiff with adler32 and all the
577 * overheads but it is a quick and dirty approximation.
579 * Now we will give some score to it. 100% edit gets
580 * 0 points and 0% edit gets MAX_SCORE points. That is, every
581 * 1/MAX_SCORE edit gets 1 point penalty. The amount of penalty is:
583 * (delta_size * 2 / (src->size + dst->size)) * MAX_SCORE
586 score
= MAX_SCORE
-(MAX_SCORE
*2*delta_size
/(src
->size
+dst
->size
));
587 if (score
< 0) return 0;
588 if (MAX_SCORE
< score
) return MAX_SCORE
;
593 struct diff_spec_hold
*src
;
594 struct diff_spec_hold
*dst
;
598 static int score_compare(const void *a_
, const void *b_
)
600 const struct diff_score
*a
= a_
, *b
= b_
;
601 return b
->score
- a
->score
;
604 static void flush_rename_pair(struct diff_spec_hold
*src
,
605 struct diff_spec_hold
*dst
,
608 src
->flags
|= MATCHED
;
609 dst
->flags
|= MATCHED
;
612 run_external_diff(src
->path
, dst
->path
,
613 &src
->it
, &dst
->it
, rename_score
);
616 static void free_held_diff(struct diff_spec_hold
*list
)
618 struct diff_spec_hold
*h
;
619 for (h
= list
; list
; list
= h
) {
626 void diff_flush(void)
628 int num_create
, num_delete
, c
, d
;
629 struct diff_spec_hold
*elem
, *src
, *dst
;
630 struct diff_score
*mx
;
632 /* We really want to cull the candidates list early
633 * with cheap tests in order to avoid doing deltas.
635 * With the current callers, we should not have already
636 * matched entries at this point, but it is nonetheless
637 * checked for sanity.
639 for (dst
= createdfile
; dst
; dst
= dst
->next
) {
640 if (dst
->flags
& MATCHED
)
642 for (src
= deletedfile
; src
; src
= src
->next
) {
643 if (src
->flags
& MATCHED
)
645 if (! is_exact_match(src
, dst
))
647 flush_rename_pair(src
, dst
, MAX_SCORE
);
652 /* Count surviving candidates */
653 for (num_create
= 0, elem
= createdfile
; elem
; elem
= elem
->next
)
654 if (!(elem
->flags
& MATCHED
))
657 for (num_delete
= 0, elem
= deletedfile
; elem
; elem
= elem
->next
)
658 if (!(elem
->flags
& MATCHED
))
661 if (num_create
== 0 || num_delete
== 0)
664 mx
= xmalloc(sizeof(*mx
) * num_create
* num_delete
);
665 for (c
= 0, dst
= createdfile
; dst
; dst
= dst
->next
) {
666 int base
= c
* num_delete
;
667 if (dst
->flags
& MATCHED
)
669 for (d
= 0, src
= deletedfile
; src
; src
= src
->next
) {
670 struct diff_score
*m
= &mx
[base
+d
];
671 if (src
->flags
& MATCHED
)
675 m
->score
= estimate_similarity(src
, dst
);
680 qsort(mx
, num_create
*num_delete
, sizeof(*mx
), score_compare
);
683 for (c
= 0; c
< num_create
* num_delete
; c
++) {
686 if ((src
->flags
& MATCHED
) || (dst
->flags
& MATCHED
))
689 "**score ** %d %s %s\n",
690 mx
[c
].score
, src
->path
, dst
->path
);
694 for (c
= 0; c
< num_create
* num_delete
; c
++) {
697 if ((src
->flags
& MATCHED
) || (dst
->flags
& MATCHED
))
699 if (mx
[c
].score
< minimum_score
)
701 flush_rename_pair(src
, dst
, mx
[c
].score
);
706 flush_remaining_diff(createdfile
, 1);
707 flush_remaining_diff(deletedfile
, 0);
708 free_held_diff(createdfile
);
709 free_held_diff(deletedfile
);
710 createdfile
= deletedfile
= NULL
;
713 int diff_scoreopt_parse(const char *opt
)
715 int diglen
, num
, scale
, i
;
716 if (opt
[0] != '-' || opt
[1] != 'M')
717 return -1; /* that is not -M option */
718 diglen
= strspn(opt
+2, "0123456789");
719 if (diglen
== 0 || strlen(opt
+2) != diglen
)
720 return 0; /* use default */
721 sscanf(opt
+2, "%d", &num
);
722 for (i
= 0, scale
= 1; i
< diglen
; i
++)
725 /* user says num divided by scale and we say internally that
726 * is MAX_SCORE * num / scale.
728 return MAX_SCORE
* num
/ scale
;
731 void diff_setup(int detect_rename_
, int minimum_score_
, int reverse_diff_
,
732 int diff_raw_output_
,
733 const char **pathspec_
, int speccnt_
)
735 free_held_diff(createdfile
);
736 free_held_diff(deletedfile
);
737 createdfile
= deletedfile
= NULL
;
739 detect_rename
= detect_rename_
;
740 reverse_diff
= reverse_diff_
;
741 pathspec
= pathspec_
;
742 diff_raw_output
= diff_raw_output_
;
744 minimum_score
= minimum_score_
? : DEFAULT_MINIMUM_SCORE
;
747 static const char *git_object_type(unsigned mode
)
749 return S_ISDIR(mode
) ? "tree" : "blob";
752 void diff_addremove(int addremove
, unsigned mode
,
753 const unsigned char *sha1
,
754 const char *base
, const char *path
)
756 char concatpath
[PATH_MAX
];
757 struct diff_spec spec
[2], *one
, *two
;
760 addremove
= (addremove
== '+' ? '-' : '+');
762 if (0 <= diff_raw_output
) {
765 printf("%c%06o %s %s %s%s%c",
768 git_object_type(mode
), sha1_to_hex(sha1
),
769 base
, path
, diff_raw_output
);
775 memcpy(spec
[0].blob_sha1
, sha1
, 20);
777 spec
[0].sha1_valid
= !!memcmp(sha1
, null_sha1
, 20);
778 spec
[0].file_valid
= 1;
779 spec
[1].file_valid
= 0;
781 if (addremove
== '+') {
782 one
= spec
+ 1; two
= spec
;
784 one
= spec
; two
= one
+ 1;
788 strcpy(concatpath
, base
);
789 strcat(concatpath
, path
);
791 hold_diff(path
? concatpath
: base
, one
, two
);
794 void diff_change(unsigned old_mode
, unsigned new_mode
,
795 const unsigned char *old_sha1
,
796 const unsigned char *new_sha1
,
797 const char *base
, const char *path
) {
798 char concatpath
[PATH_MAX
];
799 struct diff_spec spec
[2];
803 const unsigned char *tmp_c
;
804 tmp
= old_mode
; old_mode
= new_mode
; new_mode
= tmp
;
805 tmp_c
= old_sha1
; old_sha1
= new_sha1
; new_sha1
= tmp_c
;
808 if (0 <= diff_raw_output
) {
810 strcpy(old_hex
, sha1_to_hex(old_sha1
));
814 printf("*%06o->%06o %s %s->%s %s%s%c",
816 git_object_type(new_mode
),
817 old_hex
, sha1_to_hex(new_sha1
),
818 base
, path
, diff_raw_output
);
821 if (S_ISDIR(new_mode
))
825 strcpy(concatpath
, base
);
826 strcat(concatpath
, path
);
829 memcpy(spec
[0].blob_sha1
, old_sha1
, 20);
830 spec
[0].mode
= old_mode
;
831 memcpy(spec
[1].blob_sha1
, new_sha1
, 20);
832 spec
[1].mode
= new_mode
;
833 spec
[0].sha1_valid
= !!memcmp(old_sha1
, null_sha1
, 20);
834 spec
[1].sha1_valid
= !!memcmp(new_sha1
, null_sha1
, 20);
835 spec
[1].file_valid
= spec
[0].file_valid
= 1;
837 /* We do not look at changed files as candidate for
838 * rename detection ever.
840 run_external_diff(path
? concatpath
: base
, NULL
,
841 &spec
[0], &spec
[1], -1);
844 void diff_unmerge(const char *path
)
846 if (0 <= diff_raw_output
) {
847 printf("U %s%c", path
, diff_raw_output
);
850 run_external_diff(path
, NULL
, NULL
, NULL
, -1);