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
, 0))
158 if (!dst
->cnt_data
&& diff_populate_filespec(dst
, 0))
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 delta_limit
= (unsigned long)
177 (base_size
* (MAX_SCORE
-minimum_score
) / MAX_SCORE
);
178 if (diffcore_count_changes(src
, dst
,
179 &src
->cnt_data
, &dst
->cnt_data
,
181 &src_copied
, &literal_added
))
184 /* How similar are they?
185 * what percentage of material in dst are from source?
188 score
= 0; /* should not happen */
190 score
= (int)(src_copied
* MAX_SCORE
/ max_size
);
194 static void record_rename_pair(int dst_index
, int src_index
, int score
)
196 struct diff_filespec
*src
, *dst
;
197 struct diff_filepair
*dp
;
199 if (rename_dst
[dst_index
].pair
)
200 die("internal error: dst already matched.");
202 src
= rename_src
[src_index
].one
;
206 dst
= rename_dst
[dst_index
].two
;
209 dp
= diff_queue(NULL
, src
, dst
);
210 dp
->renamed_pair
= 1;
211 if (!strcmp(src
->path
, dst
->path
))
212 dp
->score
= rename_src
[src_index
].score
;
215 rename_dst
[dst_index
].pair
= dp
;
219 * We sort the rename similarity matrix with the score, in descending
220 * order (the most similar first).
222 static int score_compare(const void *a_
, const void *b_
)
224 const struct diff_score
*a
= a_
, *b
= b_
;
226 /* sink the unused ones to the bottom */
228 return (0 <= b
->dst
);
232 if (a
->score
== b
->score
)
233 return b
->name_score
- a
->name_score
;
235 return b
->score
- a
->score
;
238 struct file_similarity
{
240 struct diff_filespec
*filespec
;
241 struct file_similarity
*next
;
244 static int find_identical_files(struct file_similarity
*src
,
245 struct file_similarity
*dst
)
250 * Walk over all the destinations ...
253 struct diff_filespec
*target
= dst
->filespec
;
254 struct file_similarity
*p
, *best
;
255 int i
= 100, best_score
= -1;
258 * .. to find the best source match
261 for (p
= src
; p
; p
= p
->next
) {
263 struct diff_filespec
*source
= p
->filespec
;
265 /* False hash collission? */
266 if (hashcmp(source
->sha1
, target
->sha1
))
268 /* Non-regular files? If so, the modes must match! */
269 if (!S_ISREG(source
->mode
) || !S_ISREG(target
->mode
)) {
270 if (source
->mode
!= target
->mode
)
273 /* Give higher scores to sources that haven't been used already */
274 score
= !source
->rename_used
;
275 score
+= basename_same(source
, target
);
276 if (score
> best_score
) {
283 /* Too many identical alternatives? Pick one */
288 record_rename_pair(dst
->index
, best
->index
, MAX_SCORE
);
291 } while ((dst
= dst
->next
) != NULL
);
295 static void free_similarity_list(struct file_similarity
*p
)
298 struct file_similarity
*entry
= p
;
304 static int find_same_files(void *ptr
)
307 struct file_similarity
*p
= ptr
;
308 struct file_similarity
*src
= NULL
, *dst
= NULL
;
310 /* Split the hash list up into sources and destinations */
312 struct file_similarity
*entry
= p
;
314 if (entry
->src_dst
< 0) {
324 * If we have both sources *and* destinations, see if
325 * we can match them up
327 ret
= (src
&& dst
) ? find_identical_files(src
, dst
) : 0;
329 /* Free the hashes and return the number of renames found */
330 free_similarity_list(src
);
331 free_similarity_list(dst
);
335 static unsigned int hash_filespec(struct diff_filespec
*filespec
)
338 if (!filespec
->sha1_valid
) {
339 if (diff_populate_filespec(filespec
, 0))
341 hash_sha1_file(filespec
->data
, filespec
->size
, "blob", filespec
->sha1
);
343 memcpy(&hash
, filespec
->sha1
, sizeof(hash
));
347 static void insert_file_table(struct hash_table
*table
, int src_dst
, int index
, struct diff_filespec
*filespec
)
351 struct file_similarity
*entry
= xmalloc(sizeof(*entry
));
353 entry
->src_dst
= src_dst
;
354 entry
->index
= index
;
355 entry
->filespec
= filespec
;
358 hash
= hash_filespec(filespec
);
359 pos
= insert_hash(hash
, entry
, table
);
361 /* We already had an entry there? */
369 * Find exact renames first.
371 * The first round matches up the up-to-date entries,
372 * and then during the second round we try to match
373 * cache-dirty entries as well.
375 static int find_exact_renames(void)
378 struct hash_table file_table
;
380 init_hash(&file_table
);
381 for (i
= 0; i
< rename_src_nr
; i
++)
382 insert_file_table(&file_table
, -1, i
, rename_src
[i
].one
);
384 for (i
= 0; i
< rename_dst_nr
; i
++)
385 insert_file_table(&file_table
, 1, i
, rename_dst
[i
].two
);
387 /* Find the renames */
388 i
= for_each_hash(&file_table
, find_same_files
);
390 /* .. and free the hash data structure */
391 free_hash(&file_table
);
396 #define NUM_CANDIDATE_PER_DST 4
397 static void record_if_better(struct diff_score m
[], struct diff_score
*o
)
401 /* find the worst one */
403 for (i
= 1; i
< NUM_CANDIDATE_PER_DST
; i
++)
404 if (score_compare(&m
[i
], &m
[worst
]) > 0)
407 /* is it better than the worst one? */
408 if (score_compare(&m
[worst
], o
) > 0)
412 void diffcore_rename(struct diff_options
*options
)
414 int detect_rename
= options
->detect_rename
;
415 int minimum_score
= options
->rename_score
;
416 int rename_limit
= options
->rename_limit
;
417 struct diff_queue_struct
*q
= &diff_queued_diff
;
418 struct diff_queue_struct outq
;
419 struct diff_score
*mx
;
420 int i
, j
, rename_count
;
421 int num_create
, num_src
, dst_cnt
;
424 minimum_score
= DEFAULT_RENAME_SCORE
;
426 for (i
= 0; i
< q
->nr
; i
++) {
427 struct diff_filepair
*p
= q
->queue
[i
];
428 if (!DIFF_FILE_VALID(p
->one
)) {
429 if (!DIFF_FILE_VALID(p
->two
))
430 continue; /* unmerged */
431 else if (options
->single_follow
&&
432 strcmp(options
->single_follow
, p
->two
->path
))
433 continue; /* not interested */
435 locate_rename_dst(p
->two
, 1);
437 else if (!DIFF_FILE_VALID(p
->two
)) {
439 * If the source is a broken "delete", and
440 * they did not really want to get broken,
441 * that means the source actually stays.
442 * So we increment the "rename_used" score
443 * by one, to indicate ourselves as a user
445 if (p
->broken_pair
&& !p
->score
)
446 p
->one
->rename_used
++;
447 register_rename_src(p
->one
, p
->score
);
449 else if (detect_rename
== DIFF_DETECT_COPY
) {
451 * Increment the "rename_used" score by
452 * one, to indicate ourselves as a user.
454 p
->one
->rename_used
++;
455 register_rename_src(p
->one
, p
->score
);
458 if (rename_dst_nr
== 0 || rename_src_nr
== 0)
459 goto cleanup
; /* nothing to do */
462 * We really want to cull the candidates list early
463 * with cheap tests in order to avoid doing deltas.
465 rename_count
= find_exact_renames();
467 /* Did we only want exact renames? */
468 if (minimum_score
== MAX_SCORE
)
472 * Calculate how many renames are left (but all the source
473 * files still remain as options for rename/copies!)
475 num_create
= (rename_dst_nr
- rename_count
);
476 num_src
= rename_src_nr
;
483 * This basically does a test for the rename matrix not
484 * growing larger than a "rename_limit" square matrix, ie:
486 * num_create * num_src > rename_limit * rename_limit
488 * but handles the potential overflow case specially (and we
489 * assume at least 32-bit integers)
491 if (rename_limit
<= 0 || rename_limit
> 32767)
492 rename_limit
= 32767;
493 if ((num_create
> rename_limit
&& num_src
> rename_limit
) ||
494 (num_create
* num_src
> rename_limit
* rename_limit
)) {
495 warning("too many files, skipping inexact rename detection");
499 mx
= xcalloc(num_create
* NUM_CANDIDATE_PER_DST
, sizeof(*mx
));
500 for (dst_cnt
= i
= 0; i
< rename_dst_nr
; i
++) {
501 struct diff_filespec
*two
= rename_dst
[i
].two
;
502 struct diff_score
*m
;
504 if (rename_dst
[i
].pair
)
505 continue; /* dealt with exact match already. */
507 m
= &mx
[dst_cnt
* NUM_CANDIDATE_PER_DST
];
508 for (j
= 0; j
< NUM_CANDIDATE_PER_DST
; j
++)
511 for (j
= 0; j
< rename_src_nr
; j
++) {
512 struct diff_filespec
*one
= rename_src
[j
].one
;
513 struct diff_score this_src
;
514 this_src
.score
= estimate_similarity(one
, two
,
516 this_src
.name_score
= basename_same(one
, two
);
519 record_if_better(m
, &this_src
);
520 diff_free_filespec_blob(one
);
522 /* We do not need the text anymore */
523 diff_free_filespec_blob(two
);
527 /* cost matrix sorted by most to least similar pair */
528 qsort(mx
, dst_cnt
* NUM_CANDIDATE_PER_DST
, sizeof(*mx
), score_compare
);
530 for (i
= 0; i
< dst_cnt
* NUM_CANDIDATE_PER_DST
; i
++) {
531 struct diff_rename_dst
*dst
;
533 if ((mx
[i
].dst
< 0) ||
534 (mx
[i
].score
< minimum_score
))
535 break; /* there is no more usable pair. */
536 dst
= &rename_dst
[mx
[i
].dst
];
538 continue; /* already done, either exact or fuzzy. */
539 if (rename_src
[mx
[i
].src
].one
->rename_used
)
541 record_rename_pair(mx
[i
].dst
, mx
[i
].src
, mx
[i
].score
);
545 for (i
= 0; i
< dst_cnt
* NUM_CANDIDATE_PER_DST
; i
++) {
546 struct diff_rename_dst
*dst
;
548 if ((mx
[i
].dst
< 0) ||
549 (mx
[i
].score
< minimum_score
))
550 break; /* there is no more usable pair. */
551 dst
= &rename_dst
[mx
[i
].dst
];
553 continue; /* already done, either exact or fuzzy. */
554 record_rename_pair(mx
[i
].dst
, mx
[i
].src
, mx
[i
].score
);
560 /* At this point, we have found some renames and copies and they
561 * are recorded in rename_dst. The original list is still in *q.
564 outq
.nr
= outq
.alloc
= 0;
565 for (i
= 0; i
< q
->nr
; i
++) {
566 struct diff_filepair
*p
= q
->queue
[i
];
567 struct diff_filepair
*pair_to_free
= NULL
;
569 if (!DIFF_FILE_VALID(p
->one
) && DIFF_FILE_VALID(p
->two
)) {
573 * We would output this create record if it has
574 * not been turned into a rename/copy already.
576 struct diff_rename_dst
*dst
=
577 locate_rename_dst(p
->two
, 0);
578 if (dst
&& dst
->pair
) {
579 diff_q(&outq
, dst
->pair
);
583 /* no matching rename/copy source, so
584 * record this as a creation.
588 else if (DIFF_FILE_VALID(p
->one
) && !DIFF_FILE_VALID(p
->two
)) {
592 * We would output this delete record if:
594 * (1) this is a broken delete and the counterpart
595 * broken create remains in the output; or
596 * (2) this is not a broken delete, and rename_dst
597 * does not have a rename/copy to move p->one->path
600 * Otherwise, the counterpart broken create
601 * has been turned into a rename-edit; or
602 * delete did not have a matching create to
605 if (DIFF_PAIR_BROKEN(p
)) {
607 struct diff_rename_dst
*dst
=
608 locate_rename_dst(p
->one
, 0);
609 if (dst
&& dst
->pair
)
610 /* counterpart is now rename/copy */
614 if (p
->one
->rename_used
)
615 /* this path remains */
624 else if (!diff_unmodified_pair(p
))
625 /* all the usual ones need to be kept */
628 /* no need to keep unmodified pairs */
632 diff_free_filepair(pair_to_free
);
634 diff_debug_queue("done copying original", &outq
);
638 diff_debug_queue("done collapsing", q
);
640 for (i
= 0; i
< rename_dst_nr
; i
++)
641 free_filespec(rename_dst
[i
].two
);
645 rename_dst_nr
= rename_dst_alloc
= 0;
648 rename_src_nr
= rename_src_alloc
= 0;