2 * Copyright (C) 2005 Junio C Hamano
8 #include "levenshtein.h"
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 struct diff_rename_dst
*locate_rename_dst(struct diff_filespec
*two
,
25 while (last
> first
) {
26 int next
= (last
+ first
) >> 1;
27 struct diff_rename_dst
*dst
= &(rename_dst
[next
]);
28 int cmp
= strcmp(two
->path
, dst
->two
->path
);
40 /* insert to make it at "first" */
41 if (rename_dst_alloc
<= rename_dst_nr
) {
42 rename_dst_alloc
= alloc_nr(rename_dst_alloc
);
43 rename_dst
= xrealloc(rename_dst
,
44 rename_dst_alloc
* sizeof(*rename_dst
));
47 if (first
< rename_dst_nr
)
48 memmove(rename_dst
+ first
+ 1, rename_dst
+ first
,
49 (rename_dst_nr
- first
- 1) * sizeof(*rename_dst
));
50 rename_dst
[first
].two
= alloc_filespec(two
->path
);
51 fill_filespec(rename_dst
[first
].two
, two
->sha1
, two
->mode
);
52 rename_dst
[first
].pair
= NULL
;
53 return &(rename_dst
[first
]);
56 /* Table of rename/copy src files */
57 static struct diff_rename_src
{
58 struct diff_filespec
*one
;
59 unsigned short score
; /* to remember the break score */
61 static int rename_src_nr
, rename_src_alloc
;
63 static struct diff_rename_src
*register_rename_src(struct diff_filespec
*one
,
70 while (last
> first
) {
71 int next
= (last
+ first
) >> 1;
72 struct diff_rename_src
*src
= &(rename_src
[next
]);
73 int cmp
= strcmp(one
->path
, src
->one
->path
);
83 /* insert to make it at "first" */
84 if (rename_src_alloc
<= rename_src_nr
) {
85 rename_src_alloc
= alloc_nr(rename_src_alloc
);
86 rename_src
= xrealloc(rename_src
,
87 rename_src_alloc
* sizeof(*rename_src
));
90 if (first
< rename_src_nr
)
91 memmove(rename_src
+ first
+ 1, rename_src
+ first
,
92 (rename_src_nr
- first
- 1) * sizeof(*rename_src
));
93 rename_src
[first
].one
= one
;
94 rename_src
[first
].score
= score
;
95 return &(rename_src
[first
]);
98 static int basename_same(struct diff_filespec
*src
, struct diff_filespec
*dst
)
100 int src_len
= strlen(src
->path
), dst_len
= strlen(dst
->path
);
101 while (src_len
&& dst_len
) {
102 char c1
= src
->path
[--src_len
];
103 char c2
= dst
->path
[--dst_len
];
109 return (!src_len
|| src
->path
[src_len
- 1] == '/') &&
110 (!dst_len
|| dst
->path
[dst_len
- 1] == '/');
114 int src
; /* index in rename_src */
115 int dst
; /* index in rename_dst */
116 unsigned short score
;
120 static int estimate_similarity(struct diff_filespec
*src
,
121 struct diff_filespec
*dst
,
124 /* src points at a file that existed in the original tree (or
125 * optionally a file in the destination tree) and dst points
126 * at a newly created file. They may be quite similar, in which
127 * case we want to say src is renamed to dst or src is copied into
128 * dst, and then some edit has been applied to dst.
130 * Compare them and return how similar they are, representing
131 * the score as an integer between 0 and MAX_SCORE.
133 * When there is an exact match, it is considered a better
134 * match than anything else; the destination does not even
135 * call into this function in that case.
137 unsigned long max_size
, delta_size
, base_size
, src_copied
, literal_added
;
138 unsigned long delta_limit
;
141 /* We deal only with regular files. Symlink renames are handled
142 * only when they are exact matches --- in other words, no edits
145 if (!S_ISREG(src
->mode
) || !S_ISREG(dst
->mode
))
149 * Need to check that source and destination sizes are
150 * filled in before comparing them.
152 * If we already have "cnt_data" filled in, we know it's
153 * all good (avoid checking the size for zero, as that
154 * is a possible size - we really should have a flag to
155 * say whether the size is valid or not!)
157 if (!src
->cnt_data
&& diff_populate_filespec(src
, 1))
159 if (!dst
->cnt_data
&& diff_populate_filespec(dst
, 1))
162 max_size
= ((src
->size
> dst
->size
) ? src
->size
: dst
->size
);
163 base_size
= ((src
->size
< dst
->size
) ? src
->size
: dst
->size
);
164 delta_size
= max_size
- base_size
;
166 /* We would not consider edits that change the file size so
167 * drastically. delta_size must be smaller than
168 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
170 * Note that base_size == 0 case is handled here already
171 * and the final score computation below would not have a
172 * divide-by-zero issue.
174 if (base_size
* (MAX_SCORE
-minimum_score
) < delta_size
* MAX_SCORE
)
177 if (!src
->cnt_data
&& diff_populate_filespec(src
, 0))
179 if (!dst
->cnt_data
&& diff_populate_filespec(dst
, 0))
182 delta_limit
= (unsigned long)
183 (base_size
* (MAX_SCORE
-minimum_score
) / MAX_SCORE
);
184 if (diffcore_count_changes(src
, dst
,
185 &src
->cnt_data
, &dst
->cnt_data
,
187 &src_copied
, &literal_added
))
190 /* How similar are they?
191 * what percentage of material in dst are from source?
194 score
= 0; /* should not happen */
196 score
= (int)(src_copied
* MAX_SCORE
/ max_size
)
197 - (getenv("GIT_USE_LEVENSHTEIN") ?
198 levenshtein(src
->path
, dst
->path
, 1, 1, 1, 1) : 0);
202 static void record_rename_pair(int dst_index
, int src_index
, int score
)
204 struct diff_filespec
*src
, *dst
;
205 struct diff_filepair
*dp
;
207 if (rename_dst
[dst_index
].pair
)
208 die("internal error: dst already matched.");
210 src
= rename_src
[src_index
].one
;
214 dst
= rename_dst
[dst_index
].two
;
217 dp
= diff_queue(NULL
, src
, dst
);
218 dp
->renamed_pair
= 1;
219 if (!strcmp(src
->path
, dst
->path
))
220 dp
->score
= rename_src
[src_index
].score
;
223 rename_dst
[dst_index
].pair
= dp
;
227 * We sort the rename similarity matrix with the score, in descending
228 * order (the most similar first).
230 static int score_compare(const void *a_
, const void *b_
)
232 const struct diff_score
*a
= a_
, *b
= b_
;
234 /* sink the unused ones to the bottom */
236 return (0 <= b
->dst
);
240 if (a
->score
== b
->score
)
241 return b
->name_score
- a
->name_score
;
243 return b
->score
- a
->score
;
246 struct file_similarity
{
248 struct diff_filespec
*filespec
;
249 struct file_similarity
*next
;
252 static int find_identical_files(struct file_similarity
*src
,
253 struct file_similarity
*dst
)
258 * Walk over all the destinations ...
261 struct diff_filespec
*target
= dst
->filespec
;
262 struct file_similarity
*p
, *best
;
263 int i
= 100, best_score
= -1;
266 * .. to find the best source match
269 for (p
= src
; p
; p
= p
->next
) {
271 struct diff_filespec
*source
= p
->filespec
;
273 /* False hash collision? */
274 if (hashcmp(source
->sha1
, target
->sha1
))
276 /* Non-regular files? If so, the modes must match! */
277 if (!S_ISREG(source
->mode
) || !S_ISREG(target
->mode
)) {
278 if (source
->mode
!= target
->mode
)
281 /* Give higher scores to sources that haven't been used already */
282 score
= !source
->rename_used
;
283 score
+= basename_same(source
, target
);
284 if (score
> best_score
) {
291 /* Too many identical alternatives? Pick one */
296 record_rename_pair(dst
->index
, best
->index
, MAX_SCORE
);
299 } while ((dst
= dst
->next
) != NULL
);
303 static void free_similarity_list(struct file_similarity
*p
)
306 struct file_similarity
*entry
= p
;
312 static int find_same_files(void *ptr
)
315 struct file_similarity
*p
= ptr
;
316 struct file_similarity
*src
= NULL
, *dst
= NULL
;
318 /* Split the hash list up into sources and destinations */
320 struct file_similarity
*entry
= p
;
322 if (entry
->src_dst
< 0) {
332 * If we have both sources *and* destinations, see if
333 * we can match them up
335 ret
= (src
&& dst
) ? find_identical_files(src
, dst
) : 0;
337 /* Free the hashes and return the number of renames found */
338 free_similarity_list(src
);
339 free_similarity_list(dst
);
343 static unsigned int hash_filespec(struct diff_filespec
*filespec
)
346 if (!filespec
->sha1_valid
) {
347 if (diff_populate_filespec(filespec
, 0))
349 hash_sha1_file(filespec
->data
, filespec
->size
, "blob", filespec
->sha1
);
351 memcpy(&hash
, filespec
->sha1
, sizeof(hash
));
355 static void insert_file_table(struct hash_table
*table
, int src_dst
, int index
, struct diff_filespec
*filespec
)
359 struct file_similarity
*entry
= xmalloc(sizeof(*entry
));
361 entry
->src_dst
= src_dst
;
362 entry
->index
= index
;
363 entry
->filespec
= filespec
;
366 hash
= hash_filespec(filespec
);
367 pos
= insert_hash(hash
, entry
, table
);
369 /* We already had an entry there? */
377 * Find exact renames first.
379 * The first round matches up the up-to-date entries,
380 * and then during the second round we try to match
381 * cache-dirty entries as well.
383 static int find_exact_renames(void)
386 struct hash_table file_table
;
388 init_hash(&file_table
);
389 for (i
= 0; i
< rename_src_nr
; i
++)
390 insert_file_table(&file_table
, -1, i
, rename_src
[i
].one
);
392 for (i
= 0; i
< rename_dst_nr
; i
++)
393 insert_file_table(&file_table
, 1, i
, rename_dst
[i
].two
);
395 /* Find the renames */
396 i
= for_each_hash(&file_table
, find_same_files
);
398 /* .. and free the hash data structure */
399 free_hash(&file_table
);
404 #define NUM_CANDIDATE_PER_DST 4
405 static void record_if_better(struct diff_score m
[], struct diff_score
*o
)
409 /* find the worst one */
411 for (i
= 1; i
< NUM_CANDIDATE_PER_DST
; i
++)
412 if (score_compare(&m
[i
], &m
[worst
]) > 0)
415 /* is it better than the worst one? */
416 if (score_compare(&m
[worst
], o
) > 0)
420 void diffcore_rename(struct diff_options
*options
)
422 int detect_rename
= options
->detect_rename
;
423 int minimum_score
= options
->rename_score
;
424 int rename_limit
= options
->rename_limit
;
425 struct diff_queue_struct
*q
= &diff_queued_diff
;
426 struct diff_queue_struct outq
;
427 struct diff_score
*mx
;
428 int i
, j
, rename_count
;
429 int num_create
, num_src
, dst_cnt
;
432 minimum_score
= DEFAULT_RENAME_SCORE
;
434 for (i
= 0; i
< q
->nr
; i
++) {
435 struct diff_filepair
*p
= q
->queue
[i
];
436 if (!DIFF_FILE_VALID(p
->one
)) {
437 if (!DIFF_FILE_VALID(p
->two
))
438 continue; /* unmerged */
439 else if (options
->single_follow
&&
440 strcmp(options
->single_follow
, p
->two
->path
))
441 continue; /* not interested */
443 locate_rename_dst(p
->two
, 1);
445 else if (!DIFF_FILE_VALID(p
->two
)) {
447 * If the source is a broken "delete", and
448 * they did not really want to get broken,
449 * that means the source actually stays.
450 * So we increment the "rename_used" score
451 * by one, to indicate ourselves as a user
453 if (p
->broken_pair
&& !p
->score
)
454 p
->one
->rename_used
++;
455 register_rename_src(p
->one
, p
->score
);
457 else if (detect_rename
== DIFF_DETECT_COPY
) {
459 * Increment the "rename_used" score by
460 * one, to indicate ourselves as a user.
462 p
->one
->rename_used
++;
463 register_rename_src(p
->one
, p
->score
);
466 if (rename_dst_nr
== 0 || rename_src_nr
== 0)
467 goto cleanup
; /* nothing to do */
470 * We really want to cull the candidates list early
471 * with cheap tests in order to avoid doing deltas.
473 rename_count
= find_exact_renames();
475 /* Did we only want exact renames? */
476 if (minimum_score
== MAX_SCORE
)
480 * Calculate how many renames are left (but all the source
481 * files still remain as options for rename/copies!)
483 num_create
= (rename_dst_nr
- rename_count
);
484 num_src
= rename_src_nr
;
491 * This basically does a test for the rename matrix not
492 * growing larger than a "rename_limit" square matrix, ie:
494 * num_create * num_src > rename_limit * rename_limit
496 * but handles the potential overflow case specially (and we
497 * assume at least 32-bit integers)
499 if (rename_limit
<= 0 || rename_limit
> 32767)
500 rename_limit
= 32767;
501 if ((num_create
> rename_limit
&& num_src
> rename_limit
) ||
502 (num_create
* num_src
> rename_limit
* rename_limit
)) {
503 if (options
->warn_on_too_large_rename
)
504 warning("too many files (created: %d deleted: %d), skipping inexact rename detection", num_create
, num_src
);
508 mx
= xcalloc(num_create
* NUM_CANDIDATE_PER_DST
, sizeof(*mx
));
509 for (dst_cnt
= i
= 0; i
< rename_dst_nr
; i
++) {
510 struct diff_filespec
*two
= rename_dst
[i
].two
;
511 struct diff_score
*m
;
513 if (rename_dst
[i
].pair
)
514 continue; /* dealt with exact match already. */
516 m
= &mx
[dst_cnt
* NUM_CANDIDATE_PER_DST
];
517 for (j
= 0; j
< NUM_CANDIDATE_PER_DST
; j
++)
520 for (j
= 0; j
< rename_src_nr
; j
++) {
521 struct diff_filespec
*one
= rename_src
[j
].one
;
522 struct diff_score this_src
;
523 this_src
.score
= estimate_similarity(one
, two
,
525 this_src
.name_score
= basename_same(one
, two
);
528 record_if_better(m
, &this_src
);
530 * Once we run estimate_similarity,
531 * We do not need the text anymore.
533 diff_free_filespec_blob(one
);
534 diff_free_filespec_blob(two
);
539 /* cost matrix sorted by most to least similar pair */
540 qsort(mx
, dst_cnt
* NUM_CANDIDATE_PER_DST
, sizeof(*mx
), score_compare
);
542 for (i
= 0; i
< dst_cnt
* NUM_CANDIDATE_PER_DST
; i
++) {
543 struct diff_rename_dst
*dst
;
545 if ((mx
[i
].dst
< 0) ||
546 (mx
[i
].score
< minimum_score
))
547 break; /* there is no more usable pair. */
548 dst
= &rename_dst
[mx
[i
].dst
];
550 continue; /* already done, either exact or fuzzy. */
551 if (rename_src
[mx
[i
].src
].one
->rename_used
)
553 record_rename_pair(mx
[i
].dst
, mx
[i
].src
, mx
[i
].score
);
557 for (i
= 0; i
< dst_cnt
* NUM_CANDIDATE_PER_DST
; i
++) {
558 struct diff_rename_dst
*dst
;
560 if ((mx
[i
].dst
< 0) ||
561 (mx
[i
].score
< minimum_score
))
562 break; /* there is no more usable pair. */
563 dst
= &rename_dst
[mx
[i
].dst
];
565 continue; /* already done, either exact or fuzzy. */
566 record_rename_pair(mx
[i
].dst
, mx
[i
].src
, mx
[i
].score
);
572 /* At this point, we have found some renames and copies and they
573 * are recorded in rename_dst. The original list is still in *q.
576 outq
.nr
= outq
.alloc
= 0;
577 for (i
= 0; i
< q
->nr
; i
++) {
578 struct diff_filepair
*p
= q
->queue
[i
];
579 struct diff_filepair
*pair_to_free
= NULL
;
581 if (!DIFF_FILE_VALID(p
->one
) && DIFF_FILE_VALID(p
->two
)) {
585 * We would output this create record if it has
586 * not been turned into a rename/copy already.
588 struct diff_rename_dst
*dst
=
589 locate_rename_dst(p
->two
, 0);
590 if (dst
&& dst
->pair
) {
591 diff_q(&outq
, dst
->pair
);
595 /* no matching rename/copy source, so
596 * record this as a creation.
600 else if (DIFF_FILE_VALID(p
->one
) && !DIFF_FILE_VALID(p
->two
)) {
604 * We would output this delete record if:
606 * (1) this is a broken delete and the counterpart
607 * broken create remains in the output; or
608 * (2) this is not a broken delete, and rename_dst
609 * does not have a rename/copy to move p->one->path
612 * Otherwise, the counterpart broken create
613 * has been turned into a rename-edit; or
614 * delete did not have a matching create to
617 if (DIFF_PAIR_BROKEN(p
)) {
619 struct diff_rename_dst
*dst
=
620 locate_rename_dst(p
->one
, 0);
621 if (dst
&& dst
->pair
)
622 /* counterpart is now rename/copy */
626 if (p
->one
->rename_used
)
627 /* this path remains */
636 else if (!diff_unmodified_pair(p
))
637 /* all the usual ones need to be kept */
640 /* no need to keep unmodified pairs */
644 diff_free_filepair(pair_to_free
);
646 diff_debug_queue("done copying original", &outq
);
650 diff_debug_queue("done collapsing", q
);
652 for (i
= 0; i
< rename_dst_nr
; i
++)
653 free_filespec(rename_dst
[i
].two
);
657 rename_dst_nr
= rename_dst_alloc
= 0;
660 rename_src_nr
= rename_src_alloc
= 0;