2 * Copyright (C) 2005 Junio C Hamano
10 /* Table of rename/copy destinations */
12 static struct diff_rename_dst
{
13 struct diff_filespec
*two
;
14 struct diff_filepair
*pair
;
16 static int rename_dst_nr
, rename_dst_alloc
;
18 static int find_rename_dst(struct diff_filespec
*two
)
24 while (last
> first
) {
25 int next
= (last
+ first
) >> 1;
26 struct diff_rename_dst
*dst
= &(rename_dst
[next
]);
27 int cmp
= strcmp(two
->path
, dst
->two
->path
);
39 static struct diff_rename_dst
*locate_rename_dst(struct diff_filespec
*two
)
41 int ofs
= find_rename_dst(two
);
42 return ofs
< 0 ? NULL
: &rename_dst
[ofs
];
46 * Returns 0 on success, -1 if we found a duplicate.
48 static int add_rename_dst(struct diff_filespec
*two
)
50 int first
= find_rename_dst(two
);
56 /* insert to make it at "first" */
57 ALLOC_GROW(rename_dst
, rename_dst_nr
+ 1, rename_dst_alloc
);
59 if (first
< rename_dst_nr
)
60 memmove(rename_dst
+ first
+ 1, rename_dst
+ first
,
61 (rename_dst_nr
- first
- 1) * sizeof(*rename_dst
));
62 rename_dst
[first
].two
= alloc_filespec(two
->path
);
63 fill_filespec(rename_dst
[first
].two
, two
->oid
.hash
, two
->sha1_valid
,
65 rename_dst
[first
].pair
= NULL
;
69 /* Table of rename/copy src files */
70 static struct diff_rename_src
{
71 struct diff_filepair
*p
;
72 unsigned short score
; /* to remember the break score */
74 static int rename_src_nr
, rename_src_alloc
;
76 static struct diff_rename_src
*register_rename_src(struct diff_filepair
*p
)
79 struct diff_filespec
*one
= p
->one
;
80 unsigned short score
= p
->score
;
84 while (last
> first
) {
85 int next
= (last
+ first
) >> 1;
86 struct diff_rename_src
*src
= &(rename_src
[next
]);
87 int cmp
= strcmp(one
->path
, src
->p
->one
->path
);
97 /* insert to make it at "first" */
98 ALLOC_GROW(rename_src
, rename_src_nr
+ 1, rename_src_alloc
);
100 if (first
< rename_src_nr
)
101 memmove(rename_src
+ first
+ 1, rename_src
+ first
,
102 (rename_src_nr
- first
- 1) * sizeof(*rename_src
));
103 rename_src
[first
].p
= p
;
104 rename_src
[first
].score
= score
;
105 return &(rename_src
[first
]);
108 static int basename_same(struct diff_filespec
*src
, struct diff_filespec
*dst
)
110 int src_len
= strlen(src
->path
), dst_len
= strlen(dst
->path
);
111 while (src_len
&& dst_len
) {
112 char c1
= src
->path
[--src_len
];
113 char c2
= dst
->path
[--dst_len
];
119 return (!src_len
|| src
->path
[src_len
- 1] == '/') &&
120 (!dst_len
|| dst
->path
[dst_len
- 1] == '/');
124 int src
; /* index in rename_src */
125 int dst
; /* index in rename_dst */
126 unsigned short score
;
130 static int estimate_similarity(struct diff_filespec
*src
,
131 struct diff_filespec
*dst
,
134 /* src points at a file that existed in the original tree (or
135 * optionally a file in the destination tree) and dst points
136 * at a newly created file. They may be quite similar, in which
137 * case we want to say src is renamed to dst or src is copied into
138 * dst, and then some edit has been applied to dst.
140 * Compare them and return how similar they are, representing
141 * the score as an integer between 0 and MAX_SCORE.
143 * When there is an exact match, it is considered a better
144 * match than anything else; the destination does not even
145 * call into this function in that case.
147 unsigned long max_size
, delta_size
, base_size
, src_copied
, literal_added
;
148 unsigned long delta_limit
;
151 /* We deal only with regular files. Symlink renames are handled
152 * only when they are exact matches --- in other words, no edits
155 if (!S_ISREG(src
->mode
) || !S_ISREG(dst
->mode
))
159 * Need to check that source and destination sizes are
160 * filled in before comparing them.
162 * If we already have "cnt_data" filled in, we know it's
163 * all good (avoid checking the size for zero, as that
164 * is a possible size - we really should have a flag to
165 * say whether the size is valid or not!)
167 if (!src
->cnt_data
&&
168 diff_populate_filespec(src
, CHECK_SIZE_ONLY
))
170 if (!dst
->cnt_data
&&
171 diff_populate_filespec(dst
, CHECK_SIZE_ONLY
))
174 max_size
= ((src
->size
> dst
->size
) ? src
->size
: dst
->size
);
175 base_size
= ((src
->size
< dst
->size
) ? src
->size
: dst
->size
);
176 delta_size
= max_size
- base_size
;
178 /* We would not consider edits that change the file size so
179 * drastically. delta_size must be smaller than
180 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
182 * Note that base_size == 0 case is handled here already
183 * and the final score computation below would not have a
184 * divide-by-zero issue.
186 if (max_size
* (MAX_SCORE
-minimum_score
) < delta_size
* MAX_SCORE
)
189 if (!src
->cnt_data
&& diff_populate_filespec(src
, 0))
191 if (!dst
->cnt_data
&& diff_populate_filespec(dst
, 0))
194 delta_limit
= (unsigned long)
195 (base_size
* (MAX_SCORE
-minimum_score
) / MAX_SCORE
);
196 if (diffcore_count_changes(src
, dst
,
197 &src
->cnt_data
, &dst
->cnt_data
,
199 &src_copied
, &literal_added
))
202 /* How similar are they?
203 * what percentage of material in dst are from source?
206 score
= 0; /* should not happen */
208 score
= (int)(src_copied
* MAX_SCORE
/ max_size
);
212 static void record_rename_pair(int dst_index
, int src_index
, int score
)
214 struct diff_filespec
*src
, *dst
;
215 struct diff_filepair
*dp
;
217 if (rename_dst
[dst_index
].pair
)
218 die("internal error: dst already matched.");
220 src
= rename_src
[src_index
].p
->one
;
224 dst
= rename_dst
[dst_index
].two
;
227 dp
= diff_queue(NULL
, src
, dst
);
228 dp
->renamed_pair
= 1;
229 if (!strcmp(src
->path
, dst
->path
))
230 dp
->score
= rename_src
[src_index
].score
;
233 rename_dst
[dst_index
].pair
= dp
;
237 * We sort the rename similarity matrix with the score, in descending
238 * order (the most similar first).
240 static int score_compare(const void *a_
, const void *b_
)
242 const struct diff_score
*a
= a_
, *b
= b_
;
244 /* sink the unused ones to the bottom */
246 return (0 <= b
->dst
);
250 if (a
->score
== b
->score
)
251 return b
->name_score
- a
->name_score
;
253 return b
->score
- a
->score
;
256 struct file_similarity
{
257 struct hashmap_entry entry
;
259 struct diff_filespec
*filespec
;
262 static unsigned int hash_filespec(struct diff_filespec
*filespec
)
264 if (!filespec
->sha1_valid
) {
265 if (diff_populate_filespec(filespec
, 0))
267 hash_sha1_file(filespec
->data
, filespec
->size
, "blob",
270 return sha1hash(filespec
->oid
.hash
);
273 static int find_identical_files(struct hashmap
*srcs
,
275 struct diff_options
*options
)
279 struct diff_filespec
*target
= rename_dst
[dst_index
].two
;
280 struct file_similarity
*p
, *best
= NULL
;
281 int i
= 100, best_score
= -1;
284 * Find the best source match for specified destination.
286 p
= hashmap_get_from_hash(srcs
, hash_filespec(target
), NULL
);
287 for (; p
; p
= hashmap_get_next(srcs
, p
)) {
289 struct diff_filespec
*source
= p
->filespec
;
291 /* False hash collision? */
292 if (oidcmp(&source
->oid
, &target
->oid
))
294 /* Non-regular files? If so, the modes must match! */
295 if (!S_ISREG(source
->mode
) || !S_ISREG(target
->mode
)) {
296 if (source
->mode
!= target
->mode
)
299 /* Give higher scores to sources that haven't been used already */
300 score
= !source
->rename_used
;
301 if (source
->rename_used
&& options
->detect_rename
!= DIFF_DETECT_COPY
)
303 score
+= basename_same(source
, target
);
304 if (score
> best_score
) {
311 /* Too many identical alternatives? Pick one */
316 record_rename_pair(dst_index
, best
->index
, MAX_SCORE
);
322 static void insert_file_table(struct hashmap
*table
, int index
, struct diff_filespec
*filespec
)
324 struct file_similarity
*entry
= xmalloc(sizeof(*entry
));
326 entry
->index
= index
;
327 entry
->filespec
= filespec
;
329 hashmap_entry_init(entry
, hash_filespec(filespec
));
330 hashmap_add(table
, entry
);
334 * Find exact renames first.
336 * The first round matches up the up-to-date entries,
337 * and then during the second round we try to match
338 * cache-dirty entries as well.
340 static int find_exact_renames(struct diff_options
*options
)
343 struct hashmap file_table
;
345 /* Add all sources to the hash table in reverse order, because
346 * later on they will be retrieved in LIFO order.
348 hashmap_init(&file_table
, NULL
, rename_src_nr
);
349 for (i
= rename_src_nr
-1; i
>= 0; i
--)
350 insert_file_table(&file_table
, i
, rename_src
[i
].p
->one
);
352 /* Walk the destinations and find best source match */
353 for (i
= 0; i
< rename_dst_nr
; i
++)
354 renames
+= find_identical_files(&file_table
, i
, options
);
356 /* Free the hash data structure and entries */
357 hashmap_free(&file_table
, 1);
362 #define NUM_CANDIDATE_PER_DST 4
363 static void record_if_better(struct diff_score m
[], struct diff_score
*o
)
367 /* find the worst one */
369 for (i
= 1; i
< NUM_CANDIDATE_PER_DST
; i
++)
370 if (score_compare(&m
[i
], &m
[worst
]) > 0)
373 /* is it better than the worst one? */
374 if (score_compare(&m
[worst
], o
) > 0)
380 * 0 if we are under the limit;
381 * 1 if we need to disable inexact rename detection;
382 * 2 if we would be under the limit if we were given -C instead of -C -C.
384 static int too_many_rename_candidates(int num_create
,
385 struct diff_options
*options
)
387 int rename_limit
= options
->rename_limit
;
388 int num_src
= rename_src_nr
;
391 options
->needed_rename_limit
= 0;
394 * This basically does a test for the rename matrix not
395 * growing larger than a "rename_limit" square matrix, ie:
397 * num_create * num_src > rename_limit * rename_limit
399 * but handles the potential overflow case specially (and we
400 * assume at least 32-bit integers)
402 if (rename_limit
<= 0 || rename_limit
> 32767)
403 rename_limit
= 32767;
404 if ((num_create
<= rename_limit
|| num_src
<= rename_limit
) &&
405 (num_create
* num_src
<= rename_limit
* rename_limit
))
408 options
->needed_rename_limit
=
409 num_src
> num_create
? num_src
: num_create
;
411 /* Are we running under -C -C? */
412 if (!DIFF_OPT_TST(options
, FIND_COPIES_HARDER
))
415 /* Would we bust the limit if we were running under -C? */
416 for (num_src
= i
= 0; i
< rename_src_nr
; i
++) {
417 if (diff_unmodified_pair(rename_src
[i
].p
))
421 if ((num_create
<= rename_limit
|| num_src
<= rename_limit
) &&
422 (num_create
* num_src
<= rename_limit
* rename_limit
))
427 static int find_renames(struct diff_score
*mx
, int dst_cnt
, int minimum_score
, int copies
)
431 for (i
= 0; i
< dst_cnt
* NUM_CANDIDATE_PER_DST
; i
++) {
432 struct diff_rename_dst
*dst
;
434 if ((mx
[i
].dst
< 0) ||
435 (mx
[i
].score
< minimum_score
))
436 break; /* there is no more usable pair. */
437 dst
= &rename_dst
[mx
[i
].dst
];
439 continue; /* already done, either exact or fuzzy. */
440 if (!copies
&& rename_src
[mx
[i
].src
].p
->one
->rename_used
)
442 record_rename_pair(mx
[i
].dst
, mx
[i
].src
, mx
[i
].score
);
448 void diffcore_rename(struct diff_options
*options
)
450 int detect_rename
= options
->detect_rename
;
451 int minimum_score
= options
->rename_score
;
452 struct diff_queue_struct
*q
= &diff_queued_diff
;
453 struct diff_queue_struct outq
;
454 struct diff_score
*mx
;
455 int i
, j
, rename_count
, skip_unmodified
= 0;
456 int num_create
, dst_cnt
;
457 struct progress
*progress
= NULL
;
460 minimum_score
= DEFAULT_RENAME_SCORE
;
462 for (i
= 0; i
< q
->nr
; i
++) {
463 struct diff_filepair
*p
= q
->queue
[i
];
464 if (!DIFF_FILE_VALID(p
->one
)) {
465 if (!DIFF_FILE_VALID(p
->two
))
466 continue; /* unmerged */
467 else if (options
->single_follow
&&
468 strcmp(options
->single_follow
, p
->two
->path
))
469 continue; /* not interested */
470 else if (!DIFF_OPT_TST(options
, RENAME_EMPTY
) &&
471 is_empty_blob_sha1(p
->two
->oid
.hash
))
473 else if (add_rename_dst(p
->two
) < 0) {
474 warning("skipping rename detection, detected"
475 " duplicate destination '%s'",
480 else if (!DIFF_OPT_TST(options
, RENAME_EMPTY
) &&
481 is_empty_blob_sha1(p
->one
->oid
.hash
))
483 else if (!DIFF_PAIR_UNMERGED(p
) && !DIFF_FILE_VALID(p
->two
)) {
485 * If the source is a broken "delete", and
486 * they did not really want to get broken,
487 * that means the source actually stays.
488 * So we increment the "rename_used" score
489 * by one, to indicate ourselves as a user
491 if (p
->broken_pair
&& !p
->score
)
492 p
->one
->rename_used
++;
493 register_rename_src(p
);
495 else if (detect_rename
== DIFF_DETECT_COPY
) {
497 * Increment the "rename_used" score by
498 * one, to indicate ourselves as a user.
500 p
->one
->rename_used
++;
501 register_rename_src(p
);
504 if (rename_dst_nr
== 0 || rename_src_nr
== 0)
505 goto cleanup
; /* nothing to do */
508 * We really want to cull the candidates list early
509 * with cheap tests in order to avoid doing deltas.
511 rename_count
= find_exact_renames(options
);
513 /* Did we only want exact renames? */
514 if (minimum_score
== MAX_SCORE
)
518 * Calculate how many renames are left (but all the source
519 * files still remain as options for rename/copies!)
521 num_create
= (rename_dst_nr
- rename_count
);
527 switch (too_many_rename_candidates(num_create
, options
)) {
531 options
->degraded_cc_to_c
= 1;
538 if (options
->show_rename_progress
) {
539 progress
= start_progress_delay(
540 _("Performing inexact rename detection"),
541 rename_dst_nr
* rename_src_nr
, 50, 1);
544 mx
= xcalloc(st_mult(num_create
, NUM_CANDIDATE_PER_DST
), sizeof(*mx
));
545 for (dst_cnt
= i
= 0; i
< rename_dst_nr
; i
++) {
546 struct diff_filespec
*two
= rename_dst
[i
].two
;
547 struct diff_score
*m
;
549 if (rename_dst
[i
].pair
)
550 continue; /* dealt with exact match already. */
552 m
= &mx
[dst_cnt
* NUM_CANDIDATE_PER_DST
];
553 for (j
= 0; j
< NUM_CANDIDATE_PER_DST
; j
++)
556 for (j
= 0; j
< rename_src_nr
; j
++) {
557 struct diff_filespec
*one
= rename_src
[j
].p
->one
;
558 struct diff_score this_src
;
560 if (skip_unmodified
&&
561 diff_unmodified_pair(rename_src
[j
].p
))
564 this_src
.score
= estimate_similarity(one
, two
,
566 this_src
.name_score
= basename_same(one
, two
);
569 record_if_better(m
, &this_src
);
571 * Once we run estimate_similarity,
572 * We do not need the text anymore.
574 diff_free_filespec_blob(one
);
575 diff_free_filespec_blob(two
);
578 display_progress(progress
, (i
+1)*rename_src_nr
);
580 stop_progress(&progress
);
582 /* cost matrix sorted by most to least similar pair */
583 qsort(mx
, dst_cnt
* NUM_CANDIDATE_PER_DST
, sizeof(*mx
), score_compare
);
585 rename_count
+= find_renames(mx
, dst_cnt
, minimum_score
, 0);
586 if (detect_rename
== DIFF_DETECT_COPY
)
587 rename_count
+= find_renames(mx
, dst_cnt
, minimum_score
, 1);
591 /* At this point, we have found some renames and copies and they
592 * are recorded in rename_dst. The original list is still in *q.
594 DIFF_QUEUE_CLEAR(&outq
);
595 for (i
= 0; i
< q
->nr
; i
++) {
596 struct diff_filepair
*p
= q
->queue
[i
];
597 struct diff_filepair
*pair_to_free
= NULL
;
599 if (DIFF_PAIR_UNMERGED(p
)) {
602 else if (!DIFF_FILE_VALID(p
->one
) && DIFF_FILE_VALID(p
->two
)) {
606 * We would output this create record if it has
607 * not been turned into a rename/copy already.
609 struct diff_rename_dst
*dst
= locate_rename_dst(p
->two
);
610 if (dst
&& dst
->pair
) {
611 diff_q(&outq
, dst
->pair
);
615 /* no matching rename/copy source, so
616 * record this as a creation.
620 else if (DIFF_FILE_VALID(p
->one
) && !DIFF_FILE_VALID(p
->two
)) {
624 * We would output this delete record if:
626 * (1) this is a broken delete and the counterpart
627 * broken create remains in the output; or
628 * (2) this is not a broken delete, and rename_dst
629 * does not have a rename/copy to move p->one->path
632 * Otherwise, the counterpart broken create
633 * has been turned into a rename-edit; or
634 * delete did not have a matching create to
637 if (DIFF_PAIR_BROKEN(p
)) {
639 struct diff_rename_dst
*dst
= locate_rename_dst(p
->one
);
640 if (dst
&& dst
->pair
)
641 /* counterpart is now rename/copy */
645 if (p
->one
->rename_used
)
646 /* this path remains */
655 else if (!diff_unmodified_pair(p
))
656 /* all the usual ones need to be kept */
659 /* no need to keep unmodified pairs */
663 diff_free_filepair(pair_to_free
);
665 diff_debug_queue("done copying original", &outq
);
669 diff_debug_queue("done collapsing", q
);
671 for (i
= 0; i
< rename_dst_nr
; i
++)
672 free_filespec(rename_dst
[i
].two
);
676 rename_dst_nr
= rename_dst_alloc
= 0;
679 rename_src_nr
= rename_src_alloc
= 0;