2 * Copyright (C) 2005 Junio C Hamano
9 /* Table of rename/copy destinations */
11 static struct diff_rename_dst
{
12 struct diff_filespec
*two
;
13 struct diff_filepair
*pair
;
15 static int rename_dst_nr
, rename_dst_alloc
;
17 static struct diff_rename_dst
*locate_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 /* insert to make it at "first" */
40 if (rename_dst_alloc
<= rename_dst_nr
) {
41 rename_dst_alloc
= alloc_nr(rename_dst_alloc
);
42 rename_dst
= xrealloc(rename_dst
,
43 rename_dst_alloc
* sizeof(*rename_dst
));
46 if (first
< rename_dst_nr
)
47 memmove(rename_dst
+ first
+ 1, rename_dst
+ first
,
48 (rename_dst_nr
- first
- 1) * sizeof(*rename_dst
));
49 rename_dst
[first
].two
= alloc_filespec(two
->path
);
50 fill_filespec(rename_dst
[first
].two
, two
->sha1
, two
->mode
);
51 rename_dst
[first
].pair
= NULL
;
52 return &(rename_dst
[first
]);
55 /* Table of rename/copy src files */
56 static struct diff_rename_src
{
57 struct diff_filespec
*one
;
58 unsigned short score
; /* to remember the break score */
60 static int rename_src_nr
, rename_src_alloc
;
62 static struct diff_rename_src
*register_rename_src(struct diff_filespec
*one
,
69 while (last
> first
) {
70 int next
= (last
+ first
) >> 1;
71 struct diff_rename_src
*src
= &(rename_src
[next
]);
72 int cmp
= strcmp(one
->path
, src
->one
->path
);
82 /* insert to make it at "first" */
83 if (rename_src_alloc
<= rename_src_nr
) {
84 rename_src_alloc
= alloc_nr(rename_src_alloc
);
85 rename_src
= xrealloc(rename_src
,
86 rename_src_alloc
* sizeof(*rename_src
));
89 if (first
< rename_src_nr
)
90 memmove(rename_src
+ first
+ 1, rename_src
+ first
,
91 (rename_src_nr
- first
- 1) * sizeof(*rename_src
));
92 rename_src
[first
].one
= one
;
93 rename_src
[first
].score
= score
;
94 return &(rename_src
[first
]);
97 static int basename_same(struct diff_filespec
*src
, struct diff_filespec
*dst
)
99 int src_len
= strlen(src
->path
), dst_len
= strlen(dst
->path
);
100 while (src_len
&& dst_len
) {
101 char c1
= src
->path
[--src_len
];
102 char c2
= dst
->path
[--dst_len
];
108 return (!src_len
|| src
->path
[src_len
- 1] == '/') &&
109 (!dst_len
|| dst
->path
[dst_len
- 1] == '/');
113 int src
; /* index in rename_src */
114 int dst
; /* index in rename_dst */
115 unsigned short score
;
119 static int estimate_similarity(struct diff_filespec
*src
,
120 struct diff_filespec
*dst
,
123 /* src points at a file that existed in the original tree (or
124 * optionally a file in the destination tree) and dst points
125 * at a newly created file. They may be quite similar, in which
126 * case we want to say src is renamed to dst or src is copied into
127 * dst, and then some edit has been applied to dst.
129 * Compare them and return how similar they are, representing
130 * the score as an integer between 0 and MAX_SCORE.
132 * When there is an exact match, it is considered a better
133 * match than anything else; the destination does not even
134 * call into this function in that case.
136 unsigned long max_size
, delta_size
, base_size
, src_copied
, literal_added
;
137 unsigned long delta_limit
;
140 /* We deal only with regular files. Symlink renames are handled
141 * only when they are exact matches --- in other words, no edits
144 if (!S_ISREG(src
->mode
) || !S_ISREG(dst
->mode
))
148 * Need to check that source and destination sizes are
149 * filled in before comparing them.
151 * If we already have "cnt_data" filled in, we know it's
152 * all good (avoid checking the size for zero, as that
153 * is a possible size - we really should have a flag to
154 * say whether the size is valid or not!)
156 if (!src
->cnt_data
&& diff_populate_filespec(src
, 1))
158 if (!dst
->cnt_data
&& diff_populate_filespec(dst
, 1))
161 max_size
= ((src
->size
> dst
->size
) ? src
->size
: dst
->size
);
162 base_size
= ((src
->size
< dst
->size
) ? src
->size
: dst
->size
);
163 delta_size
= max_size
- base_size
;
165 /* We would not consider edits that change the file size so
166 * drastically. delta_size must be smaller than
167 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
169 * Note that base_size == 0 case is handled here already
170 * and the final score computation below would not have a
171 * divide-by-zero issue.
173 if (base_size
* (MAX_SCORE
-minimum_score
) < delta_size
* MAX_SCORE
)
176 if (!src
->cnt_data
&& diff_populate_filespec(src
, 0))
178 if (!dst
->cnt_data
&& diff_populate_filespec(dst
, 0))
181 delta_limit
= (unsigned long)
182 (base_size
* (MAX_SCORE
-minimum_score
) / MAX_SCORE
);
183 if (diffcore_count_changes(src
, dst
,
184 &src
->cnt_data
, &dst
->cnt_data
,
186 &src_copied
, &literal_added
))
189 /* How similar are they?
190 * what percentage of material in dst are from source?
193 score
= 0; /* should not happen */
195 score
= (int)(src_copied
* MAX_SCORE
/ max_size
);
199 static void record_rename_pair(int dst_index
, int src_index
, int score
)
201 struct diff_filespec
*src
, *dst
;
202 struct diff_filepair
*dp
;
204 if (rename_dst
[dst_index
].pair
)
205 die("internal error: dst already matched.");
207 src
= rename_src
[src_index
].one
;
211 dst
= rename_dst
[dst_index
].two
;
214 dp
= diff_queue(NULL
, src
, dst
);
215 dp
->renamed_pair
= 1;
216 if (!strcmp(src
->path
, dst
->path
))
217 dp
->score
= rename_src
[src_index
].score
;
220 rename_dst
[dst_index
].pair
= dp
;
224 * We sort the rename similarity matrix with the score, in descending
225 * order (the most similar first).
227 static int score_compare(const void *a_
, const void *b_
)
229 const struct diff_score
*a
= a_
, *b
= b_
;
231 /* sink the unused ones to the bottom */
233 return (0 <= b
->dst
);
237 if (a
->score
== b
->score
)
238 return b
->name_score
- a
->name_score
;
240 return b
->score
- a
->score
;
243 struct file_similarity
{
245 struct diff_filespec
*filespec
;
246 struct file_similarity
*next
;
249 static int find_identical_files(struct file_similarity
*src
,
250 struct file_similarity
*dst
,
251 struct diff_options
*options
)
256 * Walk over all the destinations ...
259 struct diff_filespec
*target
= dst
->filespec
;
260 struct file_similarity
*p
, *best
;
261 int i
= 100, best_score
= -1;
264 * .. to find the best source match
267 for (p
= src
; p
; p
= p
->next
) {
269 struct diff_filespec
*source
= p
->filespec
;
271 /* False hash collision? */
272 if (hashcmp(source
->sha1
, target
->sha1
))
274 /* Non-regular files? If so, the modes must match! */
275 if (!S_ISREG(source
->mode
) || !S_ISREG(target
->mode
)) {
276 if (source
->mode
!= target
->mode
)
279 /* Give higher scores to sources that haven't been used already */
280 score
= !source
->rename_used
;
281 score
+= basename_same(source
, target
);
282 if (score
> best_score
) {
289 /* Too many identical alternatives? Pick one */
294 record_rename_pair(dst
->index
, best
->index
, MAX_SCORE
);
297 } while ((dst
= dst
->next
) != NULL
);
301 static void free_similarity_list(struct file_similarity
*p
)
304 struct file_similarity
*entry
= p
;
310 static int find_same_files(void *ptr
, void *data
)
313 struct file_similarity
*p
= ptr
;
314 struct file_similarity
*src
= NULL
, *dst
= NULL
;
315 struct diff_options
*options
= data
;
317 /* Split the hash list up into sources and destinations */
319 struct file_similarity
*entry
= p
;
321 if (entry
->src_dst
< 0) {
331 * If we have both sources *and* destinations, see if
332 * we can match them up
334 ret
= (src
&& dst
) ? find_identical_files(src
, dst
, options
) : 0;
336 /* Free the hashes and return the number of renames found */
337 free_similarity_list(src
);
338 free_similarity_list(dst
);
342 static unsigned int hash_filespec(struct diff_filespec
*filespec
)
345 if (!filespec
->sha1_valid
) {
346 if (diff_populate_filespec(filespec
, 0))
348 hash_sha1_file(filespec
->data
, filespec
->size
, "blob", filespec
->sha1
);
350 memcpy(&hash
, filespec
->sha1
, sizeof(hash
));
354 static void insert_file_table(struct hash_table
*table
, int src_dst
, int index
, struct diff_filespec
*filespec
)
358 struct file_similarity
*entry
= xmalloc(sizeof(*entry
));
360 entry
->src_dst
= src_dst
;
361 entry
->index
= index
;
362 entry
->filespec
= filespec
;
365 hash
= hash_filespec(filespec
);
366 pos
= insert_hash(hash
, entry
, table
);
368 /* We already had an entry there? */
376 * Find exact renames first.
378 * The first round matches up the up-to-date entries,
379 * and then during the second round we try to match
380 * cache-dirty entries as well.
382 static int find_exact_renames(struct diff_options
*options
)
385 struct hash_table file_table
;
387 init_hash(&file_table
);
388 for (i
= 0; i
< rename_src_nr
; i
++)
389 insert_file_table(&file_table
, -1, i
, rename_src
[i
].one
);
391 for (i
= 0; i
< rename_dst_nr
; i
++)
392 insert_file_table(&file_table
, 1, i
, rename_dst
[i
].two
);
394 /* Find the renames */
395 i
= for_each_hash(&file_table
, find_same_files
, options
);
397 /* .. and free the hash data structure */
398 free_hash(&file_table
);
403 #define NUM_CANDIDATE_PER_DST 4
404 static void record_if_better(struct diff_score m
[], struct diff_score
*o
)
408 /* find the worst one */
410 for (i
= 1; i
< NUM_CANDIDATE_PER_DST
; i
++)
411 if (score_compare(&m
[i
], &m
[worst
]) > 0)
414 /* is it better than the worst one? */
415 if (score_compare(&m
[worst
], o
) > 0)
419 void diffcore_rename(struct diff_options
*options
)
421 int detect_rename
= options
->detect_rename
;
422 int minimum_score
= options
->rename_score
;
423 int rename_limit
= options
->rename_limit
;
424 struct diff_queue_struct
*q
= &diff_queued_diff
;
425 struct diff_queue_struct outq
;
426 struct diff_score
*mx
;
427 int i
, j
, rename_count
;
428 int num_create
, num_src
, dst_cnt
;
431 minimum_score
= DEFAULT_RENAME_SCORE
;
433 for (i
= 0; i
< q
->nr
; i
++) {
434 struct diff_filepair
*p
= q
->queue
[i
];
435 if (!DIFF_FILE_VALID(p
->one
)) {
436 if (!DIFF_FILE_VALID(p
->two
))
437 continue; /* unmerged */
438 else if (options
->single_follow
&&
439 strcmp(options
->single_follow
, p
->two
->path
))
440 continue; /* not interested */
442 locate_rename_dst(p
->two
, 1);
444 else if (!DIFF_FILE_VALID(p
->two
)) {
446 * If the source is a broken "delete", and
447 * they did not really want to get broken,
448 * that means the source actually stays.
449 * So we increment the "rename_used" score
450 * by one, to indicate ourselves as a user
452 if (p
->broken_pair
&& !p
->score
)
453 p
->one
->rename_used
++;
454 register_rename_src(p
->one
, p
->score
);
456 else if (detect_rename
== DIFF_DETECT_COPY
) {
458 * Increment the "rename_used" score by
459 * one, to indicate ourselves as a user.
461 p
->one
->rename_used
++;
462 register_rename_src(p
->one
, p
->score
);
465 if (rename_dst_nr
== 0 || rename_src_nr
== 0)
466 goto cleanup
; /* nothing to do */
469 * We really want to cull the candidates list early
470 * with cheap tests in order to avoid doing deltas.
472 rename_count
= find_exact_renames(options
);
474 /* Did we only want exact renames? */
475 if (minimum_score
== MAX_SCORE
)
479 * Calculate how many renames are left (but all the source
480 * files still remain as options for rename/copies!)
482 num_create
= (rename_dst_nr
- rename_count
);
483 num_src
= rename_src_nr
;
490 * This basically does a test for the rename matrix not
491 * growing larger than a "rename_limit" square matrix, ie:
493 * num_create * num_src > rename_limit * rename_limit
495 * but handles the potential overflow case specially (and we
496 * assume at least 32-bit integers)
498 if (rename_limit
<= 0 || rename_limit
> 32767)
499 rename_limit
= 32767;
500 if ((num_create
> rename_limit
&& num_src
> rename_limit
) ||
501 (num_create
* num_src
> rename_limit
* rename_limit
)) {
502 if (options
->warn_on_too_large_rename
)
503 warning("too many files (created: %d deleted: %d), skipping inexact rename detection", num_create
, num_src
);
507 mx
= xcalloc(num_create
* NUM_CANDIDATE_PER_DST
, sizeof(*mx
));
508 for (dst_cnt
= i
= 0; i
< rename_dst_nr
; i
++) {
509 struct diff_filespec
*two
= rename_dst
[i
].two
;
510 struct diff_score
*m
;
512 if (rename_dst
[i
].pair
)
513 continue; /* dealt with exact match already. */
515 m
= &mx
[dst_cnt
* NUM_CANDIDATE_PER_DST
];
516 for (j
= 0; j
< NUM_CANDIDATE_PER_DST
; j
++)
519 for (j
= 0; j
< rename_src_nr
; j
++) {
520 struct diff_filespec
*one
= rename_src
[j
].one
;
521 struct diff_score this_src
;
522 this_src
.score
= estimate_similarity(one
, two
,
524 this_src
.name_score
= basename_same(one
, two
);
527 record_if_better(m
, &this_src
);
529 * Once we run estimate_similarity,
530 * We do not need the text anymore.
532 diff_free_filespec_blob(one
);
533 diff_free_filespec_blob(two
);
538 /* cost matrix sorted by most to least similar pair */
539 qsort(mx
, dst_cnt
* NUM_CANDIDATE_PER_DST
, sizeof(*mx
), score_compare
);
541 for (i
= 0; i
< dst_cnt
* NUM_CANDIDATE_PER_DST
; i
++) {
542 struct diff_rename_dst
*dst
;
544 if ((mx
[i
].dst
< 0) ||
545 (mx
[i
].score
< minimum_score
))
546 break; /* there is no more usable pair. */
547 dst
= &rename_dst
[mx
[i
].dst
];
549 continue; /* already done, either exact or fuzzy. */
550 if (rename_src
[mx
[i
].src
].one
->rename_used
)
552 record_rename_pair(mx
[i
].dst
, mx
[i
].src
, mx
[i
].score
);
556 for (i
= 0; i
< dst_cnt
* NUM_CANDIDATE_PER_DST
; i
++) {
557 struct diff_rename_dst
*dst
;
559 if ((mx
[i
].dst
< 0) ||
560 (mx
[i
].score
< minimum_score
))
561 break; /* there is no more usable pair. */
562 dst
= &rename_dst
[mx
[i
].dst
];
564 continue; /* already done, either exact or fuzzy. */
565 record_rename_pair(mx
[i
].dst
, mx
[i
].src
, mx
[i
].score
);
571 /* At this point, we have found some renames and copies and they
572 * are recorded in rename_dst. The original list is still in *q.
574 DIFF_QUEUE_CLEAR(&outq
);
575 for (i
= 0; i
< q
->nr
; i
++) {
576 struct diff_filepair
*p
= q
->queue
[i
];
577 struct diff_filepair
*pair_to_free
= NULL
;
579 if (!DIFF_FILE_VALID(p
->one
) && DIFF_FILE_VALID(p
->two
)) {
583 * We would output this create record if it has
584 * not been turned into a rename/copy already.
586 struct diff_rename_dst
*dst
=
587 locate_rename_dst(p
->two
, 0);
588 if (dst
&& dst
->pair
) {
589 diff_q(&outq
, dst
->pair
);
593 /* no matching rename/copy source, so
594 * record this as a creation.
598 else if (DIFF_FILE_VALID(p
->one
) && !DIFF_FILE_VALID(p
->two
)) {
602 * We would output this delete record if:
604 * (1) this is a broken delete and the counterpart
605 * broken create remains in the output; or
606 * (2) this is not a broken delete, and rename_dst
607 * does not have a rename/copy to move p->one->path
610 * Otherwise, the counterpart broken create
611 * has been turned into a rename-edit; or
612 * delete did not have a matching create to
615 if (DIFF_PAIR_BROKEN(p
)) {
617 struct diff_rename_dst
*dst
=
618 locate_rename_dst(p
->one
, 0);
619 if (dst
&& dst
->pair
)
620 /* counterpart is now rename/copy */
624 if (p
->one
->rename_used
)
625 /* this path remains */
634 else if (!diff_unmodified_pair(p
))
635 /* all the usual ones need to be kept */
638 /* no need to keep unmodified pairs */
642 diff_free_filepair(pair_to_free
);
644 diff_debug_queue("done copying original", &outq
);
648 diff_debug_queue("done collapsing", q
);
650 for (i
= 0; i
< rename_dst_nr
; i
++)
651 free_filespec(rename_dst
[i
].two
);
655 rename_dst_nr
= rename_dst_alloc
= 0;
658 rename_src_nr
= rename_src_alloc
= 0;