3 * Copyright (C) 2005 Junio C Hamano
8 #include "object-store.h"
11 #include "promisor-remote.h"
14 /* Table of rename/copy destinations */
16 static struct diff_rename_dst
{
17 struct diff_filepair
*p
;
18 struct diff_filespec
*filespec_to_free
;
19 int is_rename
; /* false -> just a create; true -> rename or copy */
21 static int rename_dst_nr
, rename_dst_alloc
;
22 /* Mapping from break source pathname to break destination index */
23 static struct strintmap
*break_idx
= NULL
;
25 static struct diff_rename_dst
*locate_rename_dst(struct diff_filepair
*p
)
27 /* Lookup by p->ONE->path */
28 int idx
= break_idx
? strintmap_get(break_idx
, p
->one
->path
) : -1;
29 return (idx
== -1) ? NULL
: &rename_dst
[idx
];
33 * Returns 0 on success, -1 if we found a duplicate.
35 static int add_rename_dst(struct diff_filepair
*p
)
37 ALLOC_GROW(rename_dst
, rename_dst_nr
+ 1, rename_dst_alloc
);
38 rename_dst
[rename_dst_nr
].p
= p
;
39 rename_dst
[rename_dst_nr
].filespec_to_free
= NULL
;
40 rename_dst
[rename_dst_nr
].is_rename
= 0;
45 /* Table of rename/copy src files */
46 static struct diff_rename_src
{
47 struct diff_filepair
*p
;
48 unsigned short score
; /* to remember the break score */
50 static int rename_src_nr
, rename_src_alloc
;
52 static void register_rename_src(struct diff_filepair
*p
)
56 break_idx
= xmalloc(sizeof(*break_idx
));
57 strintmap_init(break_idx
, -1);
59 strintmap_set(break_idx
, p
->one
->path
, rename_dst_nr
);
62 ALLOC_GROW(rename_src
, rename_src_nr
+ 1, rename_src_alloc
);
63 rename_src
[rename_src_nr
].p
= p
;
64 rename_src
[rename_src_nr
].score
= p
->score
;
68 static int basename_same(struct diff_filespec
*src
, struct diff_filespec
*dst
)
70 int src_len
= strlen(src
->path
), dst_len
= strlen(dst
->path
);
71 while (src_len
&& dst_len
) {
72 char c1
= src
->path
[--src_len
];
73 char c2
= dst
->path
[--dst_len
];
79 return (!src_len
|| src
->path
[src_len
- 1] == '/') &&
80 (!dst_len
|| dst
->path
[dst_len
- 1] == '/');
84 int src
; /* index in rename_src */
85 int dst
; /* index in rename_dst */
90 struct prefetch_options
{
91 struct repository
*repo
;
94 static void prefetch(void *prefetch_options
)
96 struct prefetch_options
*options
= prefetch_options
;
98 struct oid_array to_fetch
= OID_ARRAY_INIT
;
100 for (i
= 0; i
< rename_dst_nr
; i
++) {
101 if (rename_dst
[i
].p
->renamed_pair
)
103 * The loop in diffcore_rename() will not need these
104 * blobs, so skip prefetching.
106 continue; /* already found exact match */
107 diff_add_if_missing(options
->repo
, &to_fetch
,
108 rename_dst
[i
].p
->two
);
110 for (i
= 0; i
< rename_src_nr
; i
++) {
111 if (options
->skip_unmodified
&&
112 diff_unmodified_pair(rename_src
[i
].p
))
114 * The loop in diffcore_rename() will not need these
115 * blobs, so skip prefetching.
118 diff_add_if_missing(options
->repo
, &to_fetch
,
119 rename_src
[i
].p
->one
);
121 promisor_remote_get_direct(options
->repo
, to_fetch
.oid
, to_fetch
.nr
);
122 oid_array_clear(&to_fetch
);
125 static int estimate_similarity(struct repository
*r
,
126 struct diff_filespec
*src
,
127 struct diff_filespec
*dst
,
131 /* src points at a file that existed in the original tree (or
132 * optionally a file in the destination tree) and dst points
133 * at a newly created file. They may be quite similar, in which
134 * case we want to say src is renamed to dst or src is copied into
135 * dst, and then some edit has been applied to dst.
137 * Compare them and return how similar they are, representing
138 * the score as an integer between 0 and MAX_SCORE.
140 * When there is an exact match, it is considered a better
141 * match than anything else; the destination does not even
142 * call into this function in that case.
144 unsigned long max_size
, delta_size
, base_size
, src_copied
, literal_added
;
146 struct diff_populate_filespec_options dpf_options
= {
149 struct prefetch_options prefetch_options
= {r
, skip_unmodified
};
151 if (r
== the_repository
&& has_promisor_remote()) {
152 dpf_options
.missing_object_cb
= prefetch
;
153 dpf_options
.missing_object_data
= &prefetch_options
;
156 /* We deal only with regular files. Symlink renames are handled
157 * only when they are exact matches --- in other words, no edits
160 if (!S_ISREG(src
->mode
) || !S_ISREG(dst
->mode
))
164 * Need to check that source and destination sizes are
165 * filled in before comparing them.
167 * If we already have "cnt_data" filled in, we know it's
168 * all good (avoid checking the size for zero, as that
169 * is a possible size - we really should have a flag to
170 * say whether the size is valid or not!)
172 if (!src
->cnt_data
&&
173 diff_populate_filespec(r
, src
, &dpf_options
))
175 if (!dst
->cnt_data
&&
176 diff_populate_filespec(r
, dst
, &dpf_options
))
179 max_size
= ((src
->size
> dst
->size
) ? src
->size
: dst
->size
);
180 base_size
= ((src
->size
< dst
->size
) ? src
->size
: dst
->size
);
181 delta_size
= max_size
- base_size
;
183 /* We would not consider edits that change the file size so
184 * drastically. delta_size must be smaller than
185 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
187 * Note that base_size == 0 case is handled here already
188 * and the final score computation below would not have a
189 * divide-by-zero issue.
191 if (max_size
* (MAX_SCORE
-minimum_score
) < delta_size
* MAX_SCORE
)
194 dpf_options
.check_size_only
= 0;
196 if (!src
->cnt_data
&& diff_populate_filespec(r
, src
, &dpf_options
))
198 if (!dst
->cnt_data
&& diff_populate_filespec(r
, dst
, &dpf_options
))
201 if (diffcore_count_changes(r
, src
, dst
,
202 &src
->cnt_data
, &dst
->cnt_data
,
203 &src_copied
, &literal_added
))
206 /* How similar are they?
207 * what percentage of material in dst are from source?
210 score
= 0; /* should not happen */
212 score
= (int)(src_copied
* MAX_SCORE
/ max_size
);
216 static void record_rename_pair(int dst_index
, int src_index
, int score
)
218 struct diff_filepair
*src
= rename_src
[src_index
].p
;
219 struct diff_filepair
*dst
= rename_dst
[dst_index
].p
;
221 if (dst
->renamed_pair
)
222 die("internal error: dst already matched.");
224 src
->one
->rename_used
++;
227 rename_dst
[dst_index
].filespec_to_free
= dst
->one
;
228 rename_dst
[dst_index
].is_rename
= 1;
231 dst
->renamed_pair
= 1;
232 if (!strcmp(dst
->one
->path
, dst
->two
->path
))
233 dst
->score
= rename_src
[src_index
].score
;
239 * We sort the rename similarity matrix with the score, in descending
240 * order (the most similar first).
242 static int score_compare(const void *a_
, const void *b_
)
244 const struct diff_score
*a
= a_
, *b
= b_
;
246 /* sink the unused ones to the bottom */
248 return (0 <= b
->dst
);
252 if (a
->score
== b
->score
)
253 return b
->name_score
- a
->name_score
;
255 return b
->score
- a
->score
;
258 struct file_similarity
{
259 struct hashmap_entry entry
;
261 struct diff_filespec
*filespec
;
264 static unsigned int hash_filespec(struct repository
*r
,
265 struct diff_filespec
*filespec
)
267 if (!filespec
->oid_valid
) {
268 if (diff_populate_filespec(r
, filespec
, NULL
))
270 hash_object_file(r
->hash_algo
, filespec
->data
, filespec
->size
,
271 "blob", &filespec
->oid
);
273 return oidhash(&filespec
->oid
);
276 static int find_identical_files(struct hashmap
*srcs
,
278 struct diff_options
*options
)
281 struct diff_filespec
*target
= rename_dst
[dst_index
].p
->two
;
282 struct file_similarity
*p
, *best
= NULL
;
283 int i
= 100, best_score
= -1;
284 unsigned int hash
= hash_filespec(options
->repo
, target
);
287 * Find the best source match for specified destination.
289 p
= hashmap_get_entry_from_hash(srcs
, hash
, NULL
,
290 struct file_similarity
, entry
);
291 hashmap_for_each_entry_from(srcs
, p
, entry
) {
293 struct diff_filespec
*source
= p
->filespec
;
295 /* False hash collision? */
296 if (!oideq(&source
->oid
, &target
->oid
))
298 /* Non-regular files? If so, the modes must match! */
299 if (!S_ISREG(source
->mode
) || !S_ISREG(target
->mode
)) {
300 if (source
->mode
!= target
->mode
)
303 /* Give higher scores to sources that haven't been used already */
304 score
= !source
->rename_used
;
305 if (source
->rename_used
&& options
->detect_rename
!= DIFF_DETECT_COPY
)
307 score
+= basename_same(source
, target
);
308 if (score
> best_score
) {
315 /* Too many identical alternatives? Pick one */
320 record_rename_pair(dst_index
, best
->index
, MAX_SCORE
);
326 static void insert_file_table(struct repository
*r
,
327 struct hashmap
*table
, int index
,
328 struct diff_filespec
*filespec
)
330 struct file_similarity
*entry
= xmalloc(sizeof(*entry
));
332 entry
->index
= index
;
333 entry
->filespec
= filespec
;
335 hashmap_entry_init(&entry
->entry
, hash_filespec(r
, filespec
));
336 hashmap_add(table
, &entry
->entry
);
340 * Find exact renames first.
342 * The first round matches up the up-to-date entries,
343 * and then during the second round we try to match
344 * cache-dirty entries as well.
346 static int find_exact_renames(struct diff_options
*options
)
349 struct hashmap file_table
;
351 /* Add all sources to the hash table in reverse order, because
352 * later on they will be retrieved in LIFO order.
354 hashmap_init(&file_table
, NULL
, NULL
, rename_src_nr
);
355 for (i
= rename_src_nr
-1; i
>= 0; i
--)
356 insert_file_table(options
->repo
,
358 rename_src
[i
].p
->one
);
360 /* Walk the destinations and find best source match */
361 for (i
= 0; i
< rename_dst_nr
; i
++)
362 renames
+= find_identical_files(&file_table
, i
, options
);
364 /* Free the hash data structure and entries */
365 hashmap_clear_and_free(&file_table
, struct file_similarity
, entry
);
370 #define NUM_CANDIDATE_PER_DST 4
371 static void record_if_better(struct diff_score m
[], struct diff_score
*o
)
375 /* find the worst one */
377 for (i
= 1; i
< NUM_CANDIDATE_PER_DST
; i
++)
378 if (score_compare(&m
[i
], &m
[worst
]) > 0)
381 /* is it better than the worst one? */
382 if (score_compare(&m
[worst
], o
) > 0)
388 * 0 if we are under the limit;
389 * 1 if we need to disable inexact rename detection;
390 * 2 if we would be under the limit if we were given -C instead of -C -C.
392 static int too_many_rename_candidates(int num_destinations
, int num_sources
,
393 struct diff_options
*options
)
395 int rename_limit
= options
->rename_limit
;
396 int i
, limited_sources
;
398 options
->needed_rename_limit
= 0;
401 * This basically does a test for the rename matrix not
402 * growing larger than a "rename_limit" square matrix, ie:
404 * num_destinations * num_sources > rename_limit * rename_limit
406 * We use st_mult() to check overflow conditions; in the
407 * exceptional circumstance that size_t isn't large enough to hold
408 * the multiplication, the system won't be able to allocate enough
409 * memory for the matrix anyway.
411 if (rename_limit
<= 0)
412 rename_limit
= 32767;
413 if (st_mult(num_destinations
, num_sources
)
414 <= st_mult(rename_limit
, rename_limit
))
417 options
->needed_rename_limit
=
418 num_sources
> num_destinations
? num_sources
: num_destinations
;
420 /* Are we running under -C -C? */
421 if (!options
->flags
.find_copies_harder
)
424 /* Would we bust the limit if we were running under -C? */
425 for (limited_sources
= i
= 0; i
< num_sources
; i
++) {
426 if (diff_unmodified_pair(rename_src
[i
].p
))
430 if (st_mult(num_destinations
, limited_sources
)
431 <= st_mult(rename_limit
, rename_limit
))
436 static int find_renames(struct diff_score
*mx
, int dst_cnt
, int minimum_score
, int copies
)
440 for (i
= 0; i
< dst_cnt
* NUM_CANDIDATE_PER_DST
; i
++) {
441 struct diff_rename_dst
*dst
;
443 if ((mx
[i
].dst
< 0) ||
444 (mx
[i
].score
< minimum_score
))
445 break; /* there is no more usable pair. */
446 dst
= &rename_dst
[mx
[i
].dst
];
448 continue; /* already done, either exact or fuzzy. */
449 if (!copies
&& rename_src
[mx
[i
].src
].p
->one
->rename_used
)
451 record_rename_pair(mx
[i
].dst
, mx
[i
].src
, mx
[i
].score
);
457 void diffcore_rename(struct diff_options
*options
)
459 int detect_rename
= options
->detect_rename
;
460 int minimum_score
= options
->rename_score
;
461 struct diff_queue_struct
*q
= &diff_queued_diff
;
462 struct diff_queue_struct outq
;
463 struct diff_score
*mx
;
464 int i
, j
, rename_count
, skip_unmodified
= 0;
465 int num_destinations
, dst_cnt
;
466 int num_sources
, want_copies
;
467 struct progress
*progress
= NULL
;
469 trace2_region_enter("diff", "setup", options
->repo
);
470 want_copies
= (detect_rename
== DIFF_DETECT_COPY
);
472 minimum_score
= DEFAULT_RENAME_SCORE
;
474 for (i
= 0; i
< q
->nr
; i
++) {
475 struct diff_filepair
*p
= q
->queue
[i
];
476 if (!DIFF_FILE_VALID(p
->one
)) {
477 if (!DIFF_FILE_VALID(p
->two
))
478 continue; /* unmerged */
479 else if (options
->single_follow
&&
480 strcmp(options
->single_follow
, p
->two
->path
))
481 continue; /* not interested */
482 else if (!options
->flags
.rename_empty
&&
483 is_empty_blob_oid(&p
->two
->oid
))
485 else if (add_rename_dst(p
) < 0) {
486 warning("skipping rename detection, detected"
487 " duplicate destination '%s'",
492 else if (!options
->flags
.rename_empty
&&
493 is_empty_blob_oid(&p
->one
->oid
))
495 else if (!DIFF_PAIR_UNMERGED(p
) && !DIFF_FILE_VALID(p
->two
)) {
497 * If the source is a broken "delete", and
498 * they did not really want to get broken,
499 * that means the source actually stays.
500 * So we increment the "rename_used" score
501 * by one, to indicate ourselves as a user
503 if (p
->broken_pair
&& !p
->score
)
504 p
->one
->rename_used
++;
505 register_rename_src(p
);
507 else if (want_copies
) {
509 * Increment the "rename_used" score by
510 * one, to indicate ourselves as a user.
512 p
->one
->rename_used
++;
513 register_rename_src(p
);
516 trace2_region_leave("diff", "setup", options
->repo
);
517 if (rename_dst_nr
== 0 || rename_src_nr
== 0)
518 goto cleanup
; /* nothing to do */
520 trace2_region_enter("diff", "exact renames", options
->repo
);
522 * We really want to cull the candidates list early
523 * with cheap tests in order to avoid doing deltas.
525 rename_count
= find_exact_renames(options
);
526 trace2_region_leave("diff", "exact renames", options
->repo
);
528 /* Did we only want exact renames? */
529 if (minimum_score
== MAX_SCORE
)
533 * Calculate how many renames are left (but all the source
534 * files still remain as options for rename/copies!)
536 num_destinations
= (rename_dst_nr
- rename_count
);
537 num_sources
= rename_src_nr
;
539 num_sources
-= rename_count
;
542 if (!num_destinations
|| !num_sources
)
545 switch (too_many_rename_candidates(num_destinations
, num_sources
,
550 options
->degraded_cc_to_c
= 1;
557 trace2_region_enter("diff", "inexact renames", options
->repo
);
558 if (options
->show_rename_progress
) {
559 progress
= start_delayed_progress(
560 _("Performing inexact rename detection"),
561 (uint64_t)num_destinations
* (uint64_t)num_sources
);
564 mx
= xcalloc(st_mult(NUM_CANDIDATE_PER_DST
, num_destinations
),
566 for (dst_cnt
= i
= 0; i
< rename_dst_nr
; i
++) {
567 struct diff_filespec
*two
= rename_dst
[i
].p
->two
;
568 struct diff_score
*m
;
570 if (rename_dst
[i
].is_rename
)
571 continue; /* dealt with exact match already. */
573 m
= &mx
[dst_cnt
* NUM_CANDIDATE_PER_DST
];
574 for (j
= 0; j
< NUM_CANDIDATE_PER_DST
; j
++)
577 for (j
= 0; j
< rename_src_nr
; j
++) {
578 struct diff_filespec
*one
= rename_src
[j
].p
->one
;
579 struct diff_score this_src
;
581 if (one
->rename_used
&& !want_copies
)
584 if (skip_unmodified
&&
585 diff_unmodified_pair(rename_src
[j
].p
))
588 this_src
.score
= estimate_similarity(options
->repo
,
592 this_src
.name_score
= basename_same(one
, two
);
595 record_if_better(m
, &this_src
);
597 * Once we run estimate_similarity,
598 * We do not need the text anymore.
600 diff_free_filespec_blob(one
);
601 diff_free_filespec_blob(two
);
604 display_progress(progress
,
605 (uint64_t)dst_cnt
* (uint64_t)num_sources
);
607 stop_progress(&progress
);
609 /* cost matrix sorted by most to least similar pair */
610 STABLE_QSORT(mx
, dst_cnt
* NUM_CANDIDATE_PER_DST
, score_compare
);
612 rename_count
+= find_renames(mx
, dst_cnt
, minimum_score
, 0);
614 rename_count
+= find_renames(mx
, dst_cnt
, minimum_score
, 1);
616 trace2_region_leave("diff", "inexact renames", options
->repo
);
619 /* At this point, we have found some renames and copies and they
620 * are recorded in rename_dst. The original list is still in *q.
622 trace2_region_enter("diff", "write back to queue", options
->repo
);
623 DIFF_QUEUE_CLEAR(&outq
);
624 for (i
= 0; i
< q
->nr
; i
++) {
625 struct diff_filepair
*p
= q
->queue
[i
];
626 struct diff_filepair
*pair_to_free
= NULL
;
628 if (DIFF_PAIR_UNMERGED(p
)) {
631 else if (!DIFF_FILE_VALID(p
->one
) && DIFF_FILE_VALID(p
->two
)) {
635 else if (DIFF_FILE_VALID(p
->one
) && !DIFF_FILE_VALID(p
->two
)) {
639 * We would output this delete record if:
641 * (1) this is a broken delete and the counterpart
642 * broken create remains in the output; or
643 * (2) this is not a broken delete, and rename_dst
644 * does not have a rename/copy to move p->one->path
647 * Otherwise, the counterpart broken create
648 * has been turned into a rename-edit; or
649 * delete did not have a matching create to
652 if (DIFF_PAIR_BROKEN(p
)) {
654 struct diff_rename_dst
*dst
= locate_rename_dst(p
);
656 BUG("tracking failed somehow; failed to find associated dst for broken pair");
658 /* counterpart is now rename/copy */
662 if (p
->one
->rename_used
)
663 /* this path remains */
670 else if (!diff_unmodified_pair(p
))
671 /* all the usual ones need to be kept */
674 /* no need to keep unmodified pairs; FIXME: remove earlier? */
678 diff_free_filepair(pair_to_free
);
680 diff_debug_queue("done copying original", &outq
);
684 diff_debug_queue("done collapsing", q
);
686 for (i
= 0; i
< rename_dst_nr
; i
++)
687 if (rename_dst
[i
].filespec_to_free
)
688 free_filespec(rename_dst
[i
].filespec_to_free
);
690 FREE_AND_NULL(rename_dst
);
691 rename_dst_nr
= rename_dst_alloc
= 0;
692 FREE_AND_NULL(rename_src
);
693 rename_src_nr
= rename_src_alloc
= 0;
695 strintmap_clear(break_idx
);
696 FREE_AND_NULL(break_idx
);
698 trace2_region_leave("diff", "write back to queue", options
->repo
);