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_with_options(break_idx
, -1, NULL
, 0);
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 inexact_prefetch_options
{
91 struct repository
*repo
;
94 static void inexact_prefetch(void *prefetch_options
)
96 struct inexact_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
,
129 struct diff_populate_filespec_options
*dpf_opt
)
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
;
147 /* We deal only with regular files. Symlink renames are handled
148 * only when they are exact matches --- in other words, no edits
151 if (!S_ISREG(src
->mode
) || !S_ISREG(dst
->mode
))
155 * Need to check that source and destination sizes are
156 * filled in before comparing them.
158 * If we already have "cnt_data" filled in, we know it's
159 * all good (avoid checking the size for zero, as that
160 * is a possible size - we really should have a flag to
161 * say whether the size is valid or not!)
163 dpf_opt
->check_size_only
= 1;
165 if (!src
->cnt_data
&&
166 diff_populate_filespec(r
, src
, dpf_opt
))
168 if (!dst
->cnt_data
&&
169 diff_populate_filespec(r
, dst
, dpf_opt
))
172 max_size
= ((src
->size
> dst
->size
) ? src
->size
: dst
->size
);
173 base_size
= ((src
->size
< dst
->size
) ? src
->size
: dst
->size
);
174 delta_size
= max_size
- base_size
;
176 /* We would not consider edits that change the file size so
177 * drastically. delta_size must be smaller than
178 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
180 * Note that base_size == 0 case is handled here already
181 * and the final score computation below would not have a
182 * divide-by-zero issue.
184 if (max_size
* (MAX_SCORE
-minimum_score
) < delta_size
* MAX_SCORE
)
187 dpf_opt
->check_size_only
= 0;
189 if (!src
->cnt_data
&& diff_populate_filespec(r
, src
, dpf_opt
))
191 if (!dst
->cnt_data
&& diff_populate_filespec(r
, dst
, dpf_opt
))
194 if (diffcore_count_changes(r
, src
, dst
,
195 &src
->cnt_data
, &dst
->cnt_data
,
196 &src_copied
, &literal_added
))
199 /* How similar are they?
200 * what percentage of material in dst are from source?
203 score
= 0; /* should not happen */
205 score
= (int)(src_copied
* MAX_SCORE
/ max_size
);
209 static void record_rename_pair(int dst_index
, int src_index
, int score
)
211 struct diff_filepair
*src
= rename_src
[src_index
].p
;
212 struct diff_filepair
*dst
= rename_dst
[dst_index
].p
;
214 if (dst
->renamed_pair
)
215 die("internal error: dst already matched.");
217 src
->one
->rename_used
++;
220 rename_dst
[dst_index
].filespec_to_free
= dst
->one
;
221 rename_dst
[dst_index
].is_rename
= 1;
224 dst
->renamed_pair
= 1;
225 if (!strcmp(dst
->one
->path
, dst
->two
->path
))
226 dst
->score
= rename_src
[src_index
].score
;
232 * We sort the rename similarity matrix with the score, in descending
233 * order (the most similar first).
235 static int score_compare(const void *a_
, const void *b_
)
237 const struct diff_score
*a
= a_
, *b
= b_
;
239 /* sink the unused ones to the bottom */
241 return (0 <= b
->dst
);
245 if (a
->score
== b
->score
)
246 return b
->name_score
- a
->name_score
;
248 return b
->score
- a
->score
;
251 struct file_similarity
{
252 struct hashmap_entry entry
;
254 struct diff_filespec
*filespec
;
257 static unsigned int hash_filespec(struct repository
*r
,
258 struct diff_filespec
*filespec
)
260 if (!filespec
->oid_valid
) {
261 if (diff_populate_filespec(r
, filespec
, NULL
))
263 hash_object_file(r
->hash_algo
, filespec
->data
, filespec
->size
,
264 "blob", &filespec
->oid
);
266 return oidhash(&filespec
->oid
);
269 static int find_identical_files(struct hashmap
*srcs
,
271 struct diff_options
*options
)
274 struct diff_filespec
*target
= rename_dst
[dst_index
].p
->two
;
275 struct file_similarity
*p
, *best
= NULL
;
276 int i
= 100, best_score
= -1;
277 unsigned int hash
= hash_filespec(options
->repo
, target
);
280 * Find the best source match for specified destination.
282 p
= hashmap_get_entry_from_hash(srcs
, hash
, NULL
,
283 struct file_similarity
, entry
);
284 hashmap_for_each_entry_from(srcs
, p
, entry
) {
286 struct diff_filespec
*source
= p
->filespec
;
288 /* False hash collision? */
289 if (!oideq(&source
->oid
, &target
->oid
))
291 /* Non-regular files? If so, the modes must match! */
292 if (!S_ISREG(source
->mode
) || !S_ISREG(target
->mode
)) {
293 if (source
->mode
!= target
->mode
)
296 /* Give higher scores to sources that haven't been used already */
297 score
= !source
->rename_used
;
298 if (source
->rename_used
&& options
->detect_rename
!= DIFF_DETECT_COPY
)
300 score
+= basename_same(source
, target
);
301 if (score
> best_score
) {
308 /* Too many identical alternatives? Pick one */
313 record_rename_pair(dst_index
, best
->index
, MAX_SCORE
);
319 static void insert_file_table(struct repository
*r
,
320 struct mem_pool
*pool
,
321 struct hashmap
*table
, int index
,
322 struct diff_filespec
*filespec
)
324 struct file_similarity
*entry
= mem_pool_alloc(pool
, sizeof(*entry
));
326 entry
->index
= index
;
327 entry
->filespec
= filespec
;
329 hashmap_entry_init(&entry
->entry
, hash_filespec(r
, filespec
));
330 hashmap_add(table
, &entry
->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
,
341 struct mem_pool
*pool
)
344 struct hashmap file_table
;
346 /* Add all sources to the hash table in reverse order, because
347 * later on they will be retrieved in LIFO order.
349 hashmap_init(&file_table
, NULL
, NULL
, rename_src_nr
);
350 for (i
= rename_src_nr
-1; i
>= 0; i
--)
351 insert_file_table(options
->repo
, pool
,
353 rename_src
[i
].p
->one
);
355 /* Walk the destinations and find best source match */
356 for (i
= 0; i
< rename_dst_nr
; i
++)
357 renames
+= find_identical_files(&file_table
, i
, options
);
359 /* Free the hash data structure (entries will be freed with the pool) */
360 hashmap_clear(&file_table
);
365 struct dir_rename_info
{
366 struct strintmap idx_map
;
367 struct strmap dir_rename_guess
;
368 struct strmap
*dir_rename_count
;
369 struct strintmap
*relevant_source_dirs
;
373 static char *get_dirname(const char *filename
)
375 char *slash
= strrchr(filename
, '/');
376 return slash
? xstrndup(filename
, slash
- filename
) : xstrdup("");
379 static void dirname_munge(char *filename
)
381 char *slash
= strrchr(filename
, '/');
387 static const char *get_highest_rename_path(struct strintmap
*counts
)
389 int highest_count
= 0;
390 const char *highest_destination_dir
= NULL
;
391 struct hashmap_iter iter
;
392 struct strmap_entry
*entry
;
394 strintmap_for_each_entry(counts
, &iter
, entry
) {
395 const char *destination_dir
= entry
->key
;
396 intptr_t count
= (intptr_t)entry
->value
;
397 if (count
> highest_count
) {
398 highest_count
= count
;
399 highest_destination_dir
= destination_dir
;
402 return highest_destination_dir
;
405 static char *UNKNOWN_DIR
= "/"; /* placeholder -- short, illegal directory */
407 static int dir_rename_already_determinable(struct strintmap
*counts
)
409 struct hashmap_iter iter
;
410 struct strmap_entry
*entry
;
411 int first
= 0, second
= 0, unknown
= 0;
412 strintmap_for_each_entry(counts
, &iter
, entry
) {
413 const char *destination_dir
= entry
->key
;
414 intptr_t count
= (intptr_t)entry
->value
;
415 if (!strcmp(destination_dir
, UNKNOWN_DIR
)) {
417 } else if (count
>= first
) {
420 } else if (count
>= second
) {
424 return first
> second
+ unknown
;
427 static void increment_count(struct dir_rename_info
*info
,
431 struct strintmap
*counts
;
432 struct strmap_entry
*e
;
434 /* Get the {new_dirs -> counts} mapping using old_dir */
435 e
= strmap_get_entry(info
->dir_rename_count
, old_dir
);
439 counts
= xmalloc(sizeof(*counts
));
440 strintmap_init_with_options(counts
, 0, NULL
, 1);
441 strmap_put(info
->dir_rename_count
, old_dir
, counts
);
444 /* Increment the count for new_dir */
445 strintmap_incr(counts
, new_dir
, 1);
448 static void update_dir_rename_counts(struct dir_rename_info
*info
,
449 struct strintmap
*dirs_removed
,
453 char *old_dir
= xstrdup(oldname
);
454 char *new_dir
= xstrdup(newname
);
455 char new_dir_first_char
= new_dir
[0];
456 int first_time_in_loop
= 1;
460 * info->setup is 0 here in two cases: (1) all auxiliary
461 * vars (like dirs_removed) were NULL so
462 * initialize_dir_rename_info() returned early, or (2)
463 * either break detection or copy detection are active so
464 * that we never called initialize_dir_rename_info(). In
465 * the former case, we don't have enough info to know if
466 * directories were renamed (because dirs_removed lets us
467 * know about a necessary prerequisite, namely if they were
468 * removed), and in the latter, we don't care about
469 * directory renames or find_basename_matches.
471 * This matters because both basename and inexact matching
472 * will also call update_dir_rename_counts(). In either of
473 * the above two cases info->dir_rename_counts will not
474 * have been properly initialized which prevents us from
475 * updating it, but in these two cases we don't care about
476 * dir_rename_counts anyway, so we can just exit early.
481 int drd_flag
= NOT_RELEVANT
;
483 /* Get old_dir, skip if its directory isn't relevant. */
484 dirname_munge(old_dir
);
485 if (info
->relevant_source_dirs
&&
486 !strintmap_contains(info
->relevant_source_dirs
, old_dir
))
490 dirname_munge(new_dir
);
494 * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"
495 * then this suggests that both
496 * a/b/c/d/e/ => a/b/some/thing/else/e/
497 * a/b/c/d/ => a/b/some/thing/else/
498 * so we want to increment counters for both. We do NOT,
499 * however, also want to suggest that there was the following
501 * a/b/c/ => a/b/some/thing/
502 * so we need to quit at that point.
504 * Note the when first_time_in_loop, we only strip off the
505 * basename, and we don't care if that's different.
507 if (!first_time_in_loop
) {
508 char *old_sub_dir
= strchr(old_dir
, '\0')+1;
509 char *new_sub_dir
= strchr(new_dir
, '\0')+1;
512 * Special case when renaming to root directory,
513 * i.e. when new_dir == "". In this case, we had
515 * a/b/subdir => subdir
516 * and so dirname_munge() sets things up so that
517 * old_dir = "a/b\0subdir\0"
518 * new_dir = "\0ubdir\0"
519 * We didn't have a '/' to overwrite a '\0' onto
520 * in new_dir, so we have to compare differently.
522 if (new_dir_first_char
!= old_sub_dir
[0] ||
523 strcmp(old_sub_dir
+1, new_sub_dir
))
526 if (strcmp(old_sub_dir
, new_sub_dir
))
532 * Above we suggested that we'd keep recording renames for
533 * all ancestor directories where the trailing directories
535 * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"
536 * we'd increment rename counts for each of
537 * a/b/c/d/e/ => a/b/some/thing/else/e/
538 * a/b/c/d/ => a/b/some/thing/else/
539 * However, we only need the rename counts for directories
540 * in dirs_removed whose value is RELEVANT_FOR_SELF.
541 * However, we add one special case of also recording it for
542 * first_time_in_loop because find_basename_matches() can
543 * use that as a hint to find a good pairing.
546 drd_flag
= strintmap_get(dirs_removed
, old_dir
);
547 if (drd_flag
== RELEVANT_FOR_SELF
|| first_time_in_loop
)
548 increment_count(info
, old_dir
, new_dir
);
550 first_time_in_loop
= 0;
551 if (drd_flag
== NOT_RELEVANT
)
553 /* If we hit toplevel directory ("") for old or new dir, quit */
554 if (!*old_dir
|| !*new_dir
)
558 /* Free resources we don't need anymore */
563 static void initialize_dir_rename_info(struct dir_rename_info
*info
,
564 struct strintmap
*relevant_sources
,
565 struct strintmap
*dirs_removed
,
566 struct strmap
*dir_rename_count
,
567 struct strmap
*cached_pairs
)
569 struct hashmap_iter iter
;
570 struct strmap_entry
*entry
;
573 if (!dirs_removed
&& !relevant_sources
) {
579 info
->dir_rename_count
= dir_rename_count
;
580 if (!info
->dir_rename_count
) {
581 info
->dir_rename_count
= xmalloc(sizeof(*dir_rename_count
));
582 strmap_init(info
->dir_rename_count
);
584 strintmap_init_with_options(&info
->idx_map
, -1, NULL
, 0);
585 strmap_init_with_options(&info
->dir_rename_guess
, NULL
, 0);
587 /* Setup info->relevant_source_dirs */
588 info
->relevant_source_dirs
= NULL
;
589 if (dirs_removed
|| !relevant_sources
) {
590 info
->relevant_source_dirs
= dirs_removed
; /* might be NULL */
592 info
->relevant_source_dirs
= xmalloc(sizeof(struct strintmap
));
593 strintmap_init(info
->relevant_source_dirs
, 0 /* unused */);
594 strintmap_for_each_entry(relevant_sources
, &iter
, entry
) {
595 char *dirname
= get_dirname(entry
->key
);
597 strintmap_contains(dirs_removed
, dirname
))
598 strintmap_set(info
->relevant_source_dirs
,
599 dirname
, 0 /* value irrelevant */);
605 * Loop setting up both info->idx_map, and doing setup of
606 * info->dir_rename_count.
608 for (i
= 0; i
< rename_dst_nr
; ++i
) {
610 * For non-renamed files, make idx_map contain mapping of
611 * filename -> index (index within rename_dst, that is)
613 if (!rename_dst
[i
].is_rename
) {
614 char *filename
= rename_dst
[i
].p
->two
->path
;
615 strintmap_set(&info
->idx_map
, filename
, i
);
620 * For everything else (i.e. renamed files), make
621 * dir_rename_count contain a map of a map:
622 * old_directory -> {new_directory -> count}
623 * In other words, for every pair look at the directories for
624 * the old filename and the new filename and count how many
625 * times that pairing occurs.
627 update_dir_rename_counts(info
, dirs_removed
,
628 rename_dst
[i
].p
->one
->path
,
629 rename_dst
[i
].p
->two
->path
);
632 /* Add cached_pairs to counts */
633 strmap_for_each_entry(cached_pairs
, &iter
, entry
) {
634 const char *old_name
= entry
->key
;
635 const char *new_name
= entry
->value
;
637 /* known delete; ignore it */
640 update_dir_rename_counts(info
, dirs_removed
, old_name
, new_name
);
645 * dir_rename_count: old_directory -> {new_directory -> count}
647 * dir_rename_guess: old_directory -> best_new_directory
648 * where best_new_directory is the one with the highest count.
650 strmap_for_each_entry(info
->dir_rename_count
, &iter
, entry
) {
651 /* entry->key is source_dir */
652 struct strintmap
*counts
= entry
->value
;
655 best_newdir
= xstrdup(get_highest_rename_path(counts
));
656 strmap_put(&info
->dir_rename_guess
, entry
->key
,
661 void partial_clear_dir_rename_count(struct strmap
*dir_rename_count
)
663 struct hashmap_iter iter
;
664 struct strmap_entry
*entry
;
666 strmap_for_each_entry(dir_rename_count
, &iter
, entry
) {
667 struct strintmap
*counts
= entry
->value
;
668 strintmap_clear(counts
);
670 strmap_partial_clear(dir_rename_count
, 1);
673 static void cleanup_dir_rename_info(struct dir_rename_info
*info
,
674 struct strintmap
*dirs_removed
,
675 int keep_dir_rename_count
)
677 struct hashmap_iter iter
;
678 struct strmap_entry
*entry
;
679 struct string_list to_remove
= STRING_LIST_INIT_NODUP
;
686 strintmap_clear(&info
->idx_map
);
688 /* dir_rename_guess */
689 strmap_clear(&info
->dir_rename_guess
, 1);
691 /* relevant_source_dirs */
692 if (info
->relevant_source_dirs
&&
693 info
->relevant_source_dirs
!= dirs_removed
) {
694 strintmap_clear(info
->relevant_source_dirs
);
695 FREE_AND_NULL(info
->relevant_source_dirs
);
698 /* dir_rename_count */
699 if (!keep_dir_rename_count
) {
700 partial_clear_dir_rename_count(info
->dir_rename_count
);
701 strmap_clear(info
->dir_rename_count
, 1);
702 FREE_AND_NULL(info
->dir_rename_count
);
707 * Although dir_rename_count was passed in
708 * diffcore_rename_extended() and we want to keep it around and
709 * return it to that caller, we first want to remove any counts in
710 * the maps associated with UNKNOWN_DIR entries and any data
711 * associated with directories that weren't renamed.
713 strmap_for_each_entry(info
->dir_rename_count
, &iter
, entry
) {
714 const char *source_dir
= entry
->key
;
715 struct strintmap
*counts
= entry
->value
;
717 if (!strintmap_get(dirs_removed
, source_dir
)) {
718 string_list_append(&to_remove
, source_dir
);
719 strintmap_clear(counts
);
723 if (strintmap_contains(counts
, UNKNOWN_DIR
))
724 strintmap_remove(counts
, UNKNOWN_DIR
);
726 for (i
= 0; i
< to_remove
.nr
; ++i
)
727 strmap_remove(info
->dir_rename_count
,
728 to_remove
.items
[i
].string
, 1);
729 string_list_clear(&to_remove
, 0);
732 static const char *get_basename(const char *filename
)
735 * gitbasename() has to worry about special drives, multiple
736 * directory separator characters, trailing slashes, NULL or
737 * empty strings, etc. We only work on filenames as stored in
738 * git, and thus get to ignore all those complications.
740 const char *base
= strrchr(filename
, '/');
741 return base
? base
+ 1 : filename
;
744 static int idx_possible_rename(char *filename
, struct dir_rename_info
*info
)
747 * Our comparison of files with the same basename (see
748 * find_basename_matches() below), is only helpful when after exact
749 * rename detection we have exactly one file with a given basename
750 * among the rename sources and also only exactly one file with
751 * that basename among the rename destinations. When we have
752 * multiple files with the same basename in either set, we do not
753 * know which to compare against. However, there are some
754 * filenames that occur in large numbers (particularly
755 * build-related filenames such as 'Makefile', '.gitignore', or
756 * 'build.gradle' that potentially exist within every single
757 * subdirectory), and for performance we want to be able to quickly
758 * find renames for these files too.
760 * The reason basename comparisons are a useful heuristic was that it
761 * is common for people to move files across directories while keeping
762 * their filename the same. If we had a way of determining or even
763 * making a good educated guess about which directory these non-unique
764 * basename files had moved the file to, we could check it.
767 * When an entire directory is in fact renamed, we have two factors
769 * (a) the original directory disappeared giving us a hint
770 * about when we can apply an extra heuristic.
771 * (a) we often have several files within that directory and
772 * subdirectories that are renamed without changes
773 * So, rules for a heuristic:
774 * (0) If there basename matches are non-unique (the condition under
775 * which this function is called) AND
776 * (1) the directory in which the file was found has disappeared
777 * (i.e. dirs_removed is non-NULL and has a relevant entry) THEN
778 * (2) use exact renames of files within the directory to determine
779 * where the directory is likely to have been renamed to. IF
780 * there is at least one exact rename from within that
781 * directory, we can proceed.
782 * (3) If there are multiple places the directory could have been
783 * renamed to based on exact renames, ignore all but one of them.
784 * Just use the destination with the most renames going to it.
785 * (4) Check if applying that directory rename to the original file
786 * would result in a destination filename that is in the
787 * potential rename set. If so, return the index of the
788 * destination file (the index within rename_dst).
789 * (5) Compare the original file and returned destination for
790 * similarity, and if they are sufficiently similar, record the
793 * This function, idx_possible_rename(), is only responsible for (4).
794 * The conditions/steps in (1)-(3) are handled via setting up
795 * dir_rename_count and dir_rename_guess in
796 * initialize_dir_rename_info(). Steps (0) and (5) are handled by
797 * the caller of this function.
799 char *old_dir
, *new_dir
;
800 struct strbuf new_path
= STRBUF_INIT
;
806 old_dir
= get_dirname(filename
);
807 new_dir
= strmap_get(&info
->dir_rename_guess
, old_dir
);
812 strbuf_addstr(&new_path
, new_dir
);
813 strbuf_addch(&new_path
, '/');
814 strbuf_addstr(&new_path
, get_basename(filename
));
816 idx
= strintmap_get(&info
->idx_map
, new_path
.buf
);
817 strbuf_release(&new_path
);
821 struct basename_prefetch_options
{
822 struct repository
*repo
;
823 struct strintmap
*relevant_sources
;
824 struct strintmap
*sources
;
825 struct strintmap
*dests
;
826 struct dir_rename_info
*info
;
828 static void basename_prefetch(void *prefetch_options
)
830 struct basename_prefetch_options
*options
= prefetch_options
;
831 struct strintmap
*relevant_sources
= options
->relevant_sources
;
832 struct strintmap
*sources
= options
->sources
;
833 struct strintmap
*dests
= options
->dests
;
834 struct dir_rename_info
*info
= options
->info
;
836 struct oid_array to_fetch
= OID_ARRAY_INIT
;
839 * TODO: The following loops mirror the code/logic from
840 * find_basename_matches(), though not quite exactly. Maybe
841 * abstract the iteration logic out somehow?
843 for (i
= 0; i
< rename_src_nr
; ++i
) {
844 char *filename
= rename_src
[i
].p
->one
->path
;
845 const char *base
= NULL
;
849 /* Skip irrelevant sources */
850 if (relevant_sources
&&
851 !strintmap_contains(relevant_sources
, filename
))
855 * If the basename is unique among remaining sources, then
856 * src_index will equal 'i' and we can attempt to match it
857 * to a unique basename in the destinations. Otherwise,
858 * use directory rename heuristics, if possible.
860 base
= get_basename(filename
);
861 src_index
= strintmap_get(sources
, base
);
862 assert(src_index
== -1 || src_index
== i
);
864 if (strintmap_contains(dests
, base
)) {
865 struct diff_filespec
*one
, *two
;
867 /* Find a matching destination, if possible */
868 dst_index
= strintmap_get(dests
, base
);
869 if (src_index
== -1 || dst_index
== -1) {
871 dst_index
= idx_possible_rename(filename
, info
);
876 /* Ignore this dest if already used in a rename */
877 if (rename_dst
[dst_index
].is_rename
)
878 continue; /* already used previously */
880 one
= rename_src
[src_index
].p
->one
;
881 two
= rename_dst
[dst_index
].p
->two
;
884 diff_add_if_missing(options
->repo
, &to_fetch
, two
);
885 diff_add_if_missing(options
->repo
, &to_fetch
, one
);
889 promisor_remote_get_direct(options
->repo
, to_fetch
.oid
, to_fetch
.nr
);
890 oid_array_clear(&to_fetch
);
893 static int find_basename_matches(struct diff_options
*options
,
895 struct dir_rename_info
*info
,
896 struct strintmap
*relevant_sources
,
897 struct strintmap
*dirs_removed
)
900 * When I checked in early 2020, over 76% of file renames in linux
901 * just moved files to a different directory but kept the same
902 * basename. gcc did that with over 64% of renames, gecko did it
903 * with over 79%, and WebKit did it with over 89%.
905 * Therefore we can bypass the normal exhaustive NxM matrix
906 * comparison of similarities between all potential rename sources
907 * and destinations by instead using file basename as a hint (i.e.
908 * the portion of the filename after the last '/'), checking for
909 * similarity between files with the same basename, and if we find
910 * a pair that are sufficiently similar, record the rename pair and
911 * exclude those two from the NxM matrix.
913 * This *might* cause us to find a less than optimal pairing (if
914 * there is another file that we are even more similar to but has a
915 * different basename). Given the huge performance advantage
916 * basename matching provides, and given the frequency with which
917 * people use the same basename in real world projects, that's a
918 * trade-off we are willing to accept when doing just rename
921 * If someone wants copy detection that implies they are willing to
922 * spend more cycles to find similarities between files, so it may
923 * be less likely that this heuristic is wanted. If someone is
924 * doing break detection, that means they do not want filename
925 * similarity to imply any form of content similiarity, and thus
926 * this heuristic would definitely be incompatible.
930 struct strintmap sources
;
931 struct strintmap dests
;
932 struct diff_populate_filespec_options dpf_options
= {
934 .missing_object_cb
= NULL
,
935 .missing_object_data
= NULL
937 struct basename_prefetch_options prefetch_options
= {
938 .repo
= options
->repo
,
939 .relevant_sources
= relevant_sources
,
946 * Create maps of basename -> fullname(s) for remaining sources and
949 strintmap_init_with_options(&sources
, -1, NULL
, 0);
950 strintmap_init_with_options(&dests
, -1, NULL
, 0);
951 for (i
= 0; i
< rename_src_nr
; ++i
) {
952 char *filename
= rename_src
[i
].p
->one
->path
;
955 /* exact renames removed in remove_unneeded_paths_from_src() */
956 assert(!rename_src
[i
].p
->one
->rename_used
);
958 /* Record index within rename_src (i) if basename is unique */
959 base
= get_basename(filename
);
960 if (strintmap_contains(&sources
, base
))
961 strintmap_set(&sources
, base
, -1);
963 strintmap_set(&sources
, base
, i
);
965 for (i
= 0; i
< rename_dst_nr
; ++i
) {
966 char *filename
= rename_dst
[i
].p
->two
->path
;
969 if (rename_dst
[i
].is_rename
)
970 continue; /* involved in exact match already. */
972 /* Record index within rename_dst (i) if basename is unique */
973 base
= get_basename(filename
);
974 if (strintmap_contains(&dests
, base
))
975 strintmap_set(&dests
, base
, -1);
977 strintmap_set(&dests
, base
, i
);
980 if (options
->repo
== the_repository
&& has_promisor_remote()) {
981 dpf_options
.missing_object_cb
= basename_prefetch
;
982 dpf_options
.missing_object_data
= &prefetch_options
;
985 /* Now look for basename matchups and do similarity estimation */
986 for (i
= 0; i
< rename_src_nr
; ++i
) {
987 char *filename
= rename_src
[i
].p
->one
->path
;
988 const char *base
= NULL
;
992 /* Skip irrelevant sources */
993 if (relevant_sources
&&
994 !strintmap_contains(relevant_sources
, filename
))
998 * If the basename is unique among remaining sources, then
999 * src_index will equal 'i' and we can attempt to match it
1000 * to a unique basename in the destinations. Otherwise,
1001 * use directory rename heuristics, if possible.
1003 base
= get_basename(filename
);
1004 src_index
= strintmap_get(&sources
, base
);
1005 assert(src_index
== -1 || src_index
== i
);
1007 if (strintmap_contains(&dests
, base
)) {
1008 struct diff_filespec
*one
, *two
;
1011 /* Find a matching destination, if possible */
1012 dst_index
= strintmap_get(&dests
, base
);
1013 if (src_index
== -1 || dst_index
== -1) {
1015 dst_index
= idx_possible_rename(filename
, info
);
1017 if (dst_index
== -1)
1020 /* Ignore this dest if already used in a rename */
1021 if (rename_dst
[dst_index
].is_rename
)
1022 continue; /* already used previously */
1024 /* Estimate the similarity */
1025 one
= rename_src
[src_index
].p
->one
;
1026 two
= rename_dst
[dst_index
].p
->two
;
1027 score
= estimate_similarity(options
->repo
, one
, two
,
1028 minimum_score
, &dpf_options
);
1030 /* If sufficiently similar, record as rename pair */
1031 if (score
< minimum_score
)
1033 record_rename_pair(dst_index
, src_index
, score
);
1035 update_dir_rename_counts(info
, dirs_removed
,
1036 one
->path
, two
->path
);
1039 * Found a rename so don't need text anymore; if we
1040 * didn't find a rename, the filespec_blob would get
1041 * re-used when doing the matrix of comparisons.
1043 diff_free_filespec_blob(one
);
1044 diff_free_filespec_blob(two
);
1048 strintmap_clear(&sources
);
1049 strintmap_clear(&dests
);
1054 #define NUM_CANDIDATE_PER_DST 4
1055 static void record_if_better(struct diff_score m
[], struct diff_score
*o
)
1059 /* find the worst one */
1061 for (i
= 1; i
< NUM_CANDIDATE_PER_DST
; i
++)
1062 if (score_compare(&m
[i
], &m
[worst
]) > 0)
1065 /* is it better than the worst one? */
1066 if (score_compare(&m
[worst
], o
) > 0)
1072 * 0 if we are under the limit;
1073 * 1 if we need to disable inexact rename detection;
1074 * 2 if we would be under the limit if we were given -C instead of -C -C.
1076 static int too_many_rename_candidates(int num_destinations
, int num_sources
,
1077 struct diff_options
*options
)
1079 int rename_limit
= options
->rename_limit
;
1080 int i
, limited_sources
;
1082 options
->needed_rename_limit
= 0;
1085 * This basically does a test for the rename matrix not
1086 * growing larger than a "rename_limit" square matrix, ie:
1088 * num_destinations * num_sources > rename_limit * rename_limit
1090 * We use st_mult() to check overflow conditions; in the
1091 * exceptional circumstance that size_t isn't large enough to hold
1092 * the multiplication, the system won't be able to allocate enough
1093 * memory for the matrix anyway.
1095 if (rename_limit
<= 0)
1096 rename_limit
= 32767;
1097 if (st_mult(num_destinations
, num_sources
)
1098 <= st_mult(rename_limit
, rename_limit
))
1101 options
->needed_rename_limit
=
1102 num_sources
> num_destinations
? num_sources
: num_destinations
;
1104 /* Are we running under -C -C? */
1105 if (!options
->flags
.find_copies_harder
)
1108 /* Would we bust the limit if we were running under -C? */
1109 for (limited_sources
= i
= 0; i
< num_sources
; i
++) {
1110 if (diff_unmodified_pair(rename_src
[i
].p
))
1114 if (st_mult(num_destinations
, limited_sources
)
1115 <= st_mult(rename_limit
, rename_limit
))
1120 static int find_renames(struct diff_score
*mx
,
1124 struct dir_rename_info
*info
,
1125 struct strintmap
*dirs_removed
)
1129 for (i
= 0; i
< dst_cnt
* NUM_CANDIDATE_PER_DST
; i
++) {
1130 struct diff_rename_dst
*dst
;
1132 if ((mx
[i
].dst
< 0) ||
1133 (mx
[i
].score
< minimum_score
))
1134 break; /* there is no more usable pair. */
1135 dst
= &rename_dst
[mx
[i
].dst
];
1137 continue; /* already done, either exact or fuzzy. */
1138 if (!copies
&& rename_src
[mx
[i
].src
].p
->one
->rename_used
)
1140 record_rename_pair(mx
[i
].dst
, mx
[i
].src
, mx
[i
].score
);
1142 update_dir_rename_counts(info
, dirs_removed
,
1143 rename_src
[mx
[i
].src
].p
->one
->path
,
1144 rename_dst
[mx
[i
].dst
].p
->two
->path
);
1149 static void remove_unneeded_paths_from_src(int detecting_copies
,
1150 struct strintmap
*interesting
)
1154 if (detecting_copies
&& !interesting
)
1155 return; /* nothing to remove */
1157 return; /* culling incompatible with break detection */
1160 * Note on reasons why we cull unneeded sources but not destinations:
1161 * 1) Pairings are stored in rename_dst (not rename_src), which we
1162 * need to keep around. So, we just can't cull rename_dst even
1163 * if we wanted to. But doing so wouldn't help because...
1165 * 2) There is a matrix pairwise comparison that follows the
1166 * "Performing inexact rename detection" progress message.
1167 * Iterating over the destinations is done in the outer loop,
1168 * hence we only iterate over each of those once and we can
1169 * easily skip the outer loop early if the destination isn't
1170 * relevant. That's only one check per destination path to
1173 * By contrast, the sources are iterated in the inner loop; if
1174 * we check whether a source can be skipped, then we'll be
1175 * checking it N separate times, once for each destination.
1176 * We don't want to have to iterate over known-not-needed
1177 * sources N times each, so avoid that by removing the sources
1178 * from rename_src here.
1180 for (i
= 0, new_num_src
= 0; i
< rename_src_nr
; i
++) {
1181 struct diff_filespec
*one
= rename_src
[i
].p
->one
;
1184 * renames are stored in rename_dst, so if a rename has
1185 * already been detected using this source, we can just
1186 * remove the source knowing rename_dst has its info.
1188 if (!detecting_copies
&& one
->rename_used
)
1191 /* If we don't care about the source path, skip it */
1192 if (interesting
&& !strintmap_contains(interesting
, one
->path
))
1195 if (new_num_src
< i
)
1196 memcpy(&rename_src
[new_num_src
], &rename_src
[i
],
1197 sizeof(struct diff_rename_src
));
1201 rename_src_nr
= new_num_src
;
1204 static void handle_early_known_dir_renames(struct dir_rename_info
*info
,
1205 struct strintmap
*relevant_sources
,
1206 struct strintmap
*dirs_removed
)
1209 * Directory renames are determined via an aggregate of all renames
1210 * under them and using a "majority wins" rule. The fact that
1211 * "majority wins", though, means we don't need all the renames
1212 * under the given directory, we only need enough to ensure we have
1217 struct hashmap_iter iter
;
1218 struct strmap_entry
*entry
;
1220 if (!dirs_removed
|| !relevant_sources
)
1221 return; /* nothing to cull */
1223 return; /* culling incompatbile with break detection */
1226 * Supplement dir_rename_count with number of potential renames,
1227 * marking all potential rename sources as mapping to UNKNOWN_DIR.
1229 for (i
= 0; i
< rename_src_nr
; i
++) {
1231 struct diff_filespec
*one
= rename_src
[i
].p
->one
;
1234 * sources that are part of a rename will have already been
1235 * removed by a prior call to remove_unneeded_paths_from_src()
1237 assert(!one
->rename_used
);
1239 old_dir
= get_dirname(one
->path
);
1240 while (*old_dir
!= '\0' &&
1241 NOT_RELEVANT
!= strintmap_get(dirs_removed
, old_dir
)) {
1242 char *freeme
= old_dir
;
1244 increment_count(info
, old_dir
, UNKNOWN_DIR
);
1245 old_dir
= get_dirname(old_dir
);
1247 /* Free resources we don't need anymore */
1251 * old_dir and new_dir free'd in increment_count, but
1252 * get_dirname() gives us a new pointer we need to free for
1253 * old_dir. Also, if the loop runs 0 times we need old_dir
1260 * For any directory which we need a potential rename detected for
1261 * (i.e. those marked as RELEVANT_FOR_SELF in dirs_removed), check
1262 * whether we have enough renames to satisfy the "majority rules"
1263 * requirement such that detecting any more renames of files under
1264 * it won't change the result. For any such directory, mark that
1265 * we no longer need to detect a rename for it. However, since we
1266 * might need to still detect renames for an ancestor of that
1267 * directory, use RELEVANT_FOR_ANCESTOR.
1269 strmap_for_each_entry(info
->dir_rename_count
, &iter
, entry
) {
1270 /* entry->key is source_dir */
1271 struct strintmap
*counts
= entry
->value
;
1273 if (strintmap_get(dirs_removed
, entry
->key
) ==
1274 RELEVANT_FOR_SELF
&&
1275 dir_rename_already_determinable(counts
)) {
1276 strintmap_set(dirs_removed
, entry
->key
,
1277 RELEVANT_FOR_ANCESTOR
);
1281 for (i
= 0, new_num_src
= 0; i
< rename_src_nr
; i
++) {
1282 struct diff_filespec
*one
= rename_src
[i
].p
->one
;
1285 val
= strintmap_get(relevant_sources
, one
->path
);
1288 * sources that were not found in relevant_sources should
1289 * have already been removed by a prior call to
1290 * remove_unneeded_paths_from_src()
1294 if (val
== RELEVANT_LOCATION
) {
1296 char *dir
= get_dirname(one
->path
);
1299 int res
= strintmap_get(dirs_removed
, dir
);
1301 /* Quit if not found or irrelevant */
1302 if (res
== NOT_RELEVANT
)
1304 /* If RELEVANT_FOR_SELF, can't remove */
1305 if (res
== RELEVANT_FOR_SELF
) {
1309 /* Else continue searching upwards */
1310 assert(res
== RELEVANT_FOR_ANCESTOR
);
1311 dir
= get_dirname(dir
);
1316 strintmap_set(relevant_sources
, one
->path
,
1322 if (new_num_src
< i
)
1323 memcpy(&rename_src
[new_num_src
], &rename_src
[i
],
1324 sizeof(struct diff_rename_src
));
1328 rename_src_nr
= new_num_src
;
1331 static void free_filespec_data(struct diff_filespec
*spec
)
1334 diff_free_filespec_data(spec
);
1337 static void pool_free_filespec(struct mem_pool
*pool
,
1338 struct diff_filespec
*spec
)
1341 free_filespec(spec
);
1346 * Similar to free_filespec(), but only frees the data. The spec
1347 * itself was allocated in the pool and should not be individually
1350 free_filespec_data(spec
);
1353 void pool_diff_free_filepair(struct mem_pool
*pool
,
1354 struct diff_filepair
*p
)
1357 diff_free_filepair(p
);
1362 * Similar to diff_free_filepair() but only frees the data from the
1363 * filespecs; not the filespecs or the filepair which were
1364 * allocated from the pool.
1366 free_filespec_data(p
->one
);
1367 free_filespec_data(p
->two
);
1370 void diffcore_rename_extended(struct diff_options
*options
,
1371 struct mem_pool
*pool
,
1372 struct strintmap
*relevant_sources
,
1373 struct strintmap
*dirs_removed
,
1374 struct strmap
*dir_rename_count
,
1375 struct strmap
*cached_pairs
)
1377 int detect_rename
= options
->detect_rename
;
1378 int minimum_score
= options
->rename_score
;
1379 struct diff_queue_struct
*q
= &diff_queued_diff
;
1380 struct diff_queue_struct outq
;
1381 struct diff_score
*mx
;
1382 int i
, j
, rename_count
, skip_unmodified
= 0;
1383 int num_destinations
, dst_cnt
;
1384 int num_sources
, want_copies
;
1385 struct progress
*progress
= NULL
;
1386 struct mem_pool local_pool
;
1387 struct dir_rename_info info
;
1388 struct diff_populate_filespec_options dpf_options
= {
1390 .missing_object_cb
= NULL
,
1391 .missing_object_data
= NULL
1393 struct inexact_prefetch_options prefetch_options
= {
1394 .repo
= options
->repo
1397 trace2_region_enter("diff", "setup", options
->repo
);
1399 assert(!dir_rename_count
|| strmap_empty(dir_rename_count
));
1400 want_copies
= (detect_rename
== DIFF_DETECT_COPY
);
1401 if (dirs_removed
&& (break_idx
|| want_copies
))
1402 BUG("dirs_removed incompatible with break/copy detection");
1403 if (break_idx
&& relevant_sources
)
1404 BUG("break detection incompatible with source specification");
1406 minimum_score
= DEFAULT_RENAME_SCORE
;
1408 for (i
= 0; i
< q
->nr
; i
++) {
1409 struct diff_filepair
*p
= q
->queue
[i
];
1410 if (!DIFF_FILE_VALID(p
->one
)) {
1411 if (!DIFF_FILE_VALID(p
->two
))
1412 continue; /* unmerged */
1413 else if (options
->single_follow
&&
1414 strcmp(options
->single_follow
, p
->two
->path
))
1415 continue; /* not interested */
1416 else if (!options
->flags
.rename_empty
&&
1417 is_empty_blob_oid(&p
->two
->oid
))
1419 else if (add_rename_dst(p
) < 0) {
1420 warning("skipping rename detection, detected"
1421 " duplicate destination '%s'",
1426 else if (!options
->flags
.rename_empty
&&
1427 is_empty_blob_oid(&p
->one
->oid
))
1429 else if (!DIFF_PAIR_UNMERGED(p
) && !DIFF_FILE_VALID(p
->two
)) {
1431 * If the source is a broken "delete", and
1432 * they did not really want to get broken,
1433 * that means the source actually stays.
1434 * So we increment the "rename_used" score
1435 * by one, to indicate ourselves as a user
1437 if (p
->broken_pair
&& !p
->score
)
1438 p
->one
->rename_used
++;
1439 register_rename_src(p
);
1441 else if (want_copies
) {
1443 * Increment the "rename_used" score by
1444 * one, to indicate ourselves as a user.
1446 p
->one
->rename_used
++;
1447 register_rename_src(p
);
1450 trace2_region_leave("diff", "setup", options
->repo
);
1451 if (rename_dst_nr
== 0 || rename_src_nr
== 0)
1452 goto cleanup
; /* nothing to do */
1454 trace2_region_enter("diff", "exact renames", options
->repo
);
1455 mem_pool_init(&local_pool
, 32*1024);
1457 * We really want to cull the candidates list early
1458 * with cheap tests in order to avoid doing deltas.
1460 rename_count
= find_exact_renames(options
, &local_pool
);
1462 * Discard local_pool immediately instead of at "cleanup:" in order
1463 * to reduce maximum memory usage; inexact rename detection uses up
1464 * a fair amount of memory, and mem_pools can too.
1466 mem_pool_discard(&local_pool
, 0);
1467 trace2_region_leave("diff", "exact renames", options
->repo
);
1469 /* Did we only want exact renames? */
1470 if (minimum_score
== MAX_SCORE
)
1473 num_sources
= rename_src_nr
;
1475 if (want_copies
|| break_idx
) {
1478 * - remove ones corresponding to exact renames
1479 * - remove ones not found in relevant_sources
1481 trace2_region_enter("diff", "cull after exact", options
->repo
);
1482 remove_unneeded_paths_from_src(want_copies
, relevant_sources
);
1483 trace2_region_leave("diff", "cull after exact", options
->repo
);
1485 /* Determine minimum score to match basenames */
1486 double factor
= 0.5;
1487 char *basename_factor
= getenv("GIT_BASENAME_FACTOR");
1488 int min_basename_score
;
1490 if (basename_factor
)
1491 factor
= strtol(basename_factor
, NULL
, 10)/100.0;
1492 assert(factor
>= 0.0 && factor
<= 1.0);
1493 min_basename_score
= minimum_score
+
1494 (int)(factor
* (MAX_SCORE
- minimum_score
));
1498 * - remove ones involved in renames (found via exact match)
1500 trace2_region_enter("diff", "cull after exact", options
->repo
);
1501 remove_unneeded_paths_from_src(want_copies
, NULL
);
1502 trace2_region_leave("diff", "cull after exact", options
->repo
);
1504 /* Preparation for basename-driven matching. */
1505 trace2_region_enter("diff", "dir rename setup", options
->repo
);
1506 initialize_dir_rename_info(&info
, relevant_sources
,
1507 dirs_removed
, dir_rename_count
,
1509 trace2_region_leave("diff", "dir rename setup", options
->repo
);
1511 /* Utilize file basenames to quickly find renames. */
1512 trace2_region_enter("diff", "basename matches", options
->repo
);
1513 rename_count
+= find_basename_matches(options
,
1518 trace2_region_leave("diff", "basename matches", options
->repo
);
1521 * Cull sources, again:
1522 * - remove ones involved in renames (found via basenames)
1523 * - remove ones not found in relevant_sources
1525 * - remove ones in relevant_sources which are needed only
1526 * for directory renames IF no ancestory directory
1527 * actually needs to know any more individual path
1528 * renames under them
1530 trace2_region_enter("diff", "cull basename", options
->repo
);
1531 remove_unneeded_paths_from_src(want_copies
, relevant_sources
);
1532 handle_early_known_dir_renames(&info
, relevant_sources
,
1534 trace2_region_leave("diff", "cull basename", options
->repo
);
1537 /* Calculate how many rename destinations are left */
1538 num_destinations
= (rename_dst_nr
- rename_count
);
1539 num_sources
= rename_src_nr
; /* rename_src_nr reflects lower number */
1542 if (!num_destinations
|| !num_sources
)
1545 switch (too_many_rename_candidates(num_destinations
, num_sources
,
1550 options
->degraded_cc_to_c
= 1;
1551 skip_unmodified
= 1;
1557 trace2_region_enter("diff", "inexact renames", options
->repo
);
1558 if (options
->show_rename_progress
) {
1559 progress
= start_delayed_progress(
1560 _("Performing inexact rename detection"),
1561 (uint64_t)num_destinations
* (uint64_t)num_sources
);
1564 /* Finish setting up dpf_options */
1565 prefetch_options
.skip_unmodified
= skip_unmodified
;
1566 if (options
->repo
== the_repository
&& has_promisor_remote()) {
1567 dpf_options
.missing_object_cb
= inexact_prefetch
;
1568 dpf_options
.missing_object_data
= &prefetch_options
;
1571 CALLOC_ARRAY(mx
, st_mult(NUM_CANDIDATE_PER_DST
, num_destinations
));
1572 for (dst_cnt
= i
= 0; i
< rename_dst_nr
; i
++) {
1573 struct diff_filespec
*two
= rename_dst
[i
].p
->two
;
1574 struct diff_score
*m
;
1576 if (rename_dst
[i
].is_rename
)
1577 continue; /* exact or basename match already handled */
1579 m
= &mx
[dst_cnt
* NUM_CANDIDATE_PER_DST
];
1580 for (j
= 0; j
< NUM_CANDIDATE_PER_DST
; j
++)
1583 for (j
= 0; j
< rename_src_nr
; j
++) {
1584 struct diff_filespec
*one
= rename_src
[j
].p
->one
;
1585 struct diff_score this_src
;
1587 assert(!one
->rename_used
|| want_copies
|| break_idx
);
1589 if (skip_unmodified
&&
1590 diff_unmodified_pair(rename_src
[j
].p
))
1593 this_src
.score
= estimate_similarity(options
->repo
,
1597 this_src
.name_score
= basename_same(one
, two
);
1600 record_if_better(m
, &this_src
);
1602 * Once we run estimate_similarity,
1603 * We do not need the text anymore.
1605 diff_free_filespec_blob(one
);
1606 diff_free_filespec_blob(two
);
1609 display_progress(progress
,
1610 (uint64_t)dst_cnt
* (uint64_t)num_sources
);
1612 stop_progress(&progress
);
1614 /* cost matrix sorted by most to least similar pair */
1615 STABLE_QSORT(mx
, dst_cnt
* NUM_CANDIDATE_PER_DST
, score_compare
);
1617 rename_count
+= find_renames(mx
, dst_cnt
, minimum_score
, 0,
1618 &info
, dirs_removed
);
1620 rename_count
+= find_renames(mx
, dst_cnt
, minimum_score
, 1,
1621 &info
, dirs_removed
);
1623 trace2_region_leave("diff", "inexact renames", options
->repo
);
1626 /* At this point, we have found some renames and copies and they
1627 * are recorded in rename_dst. The original list is still in *q.
1629 trace2_region_enter("diff", "write back to queue", options
->repo
);
1630 DIFF_QUEUE_CLEAR(&outq
);
1631 for (i
= 0; i
< q
->nr
; i
++) {
1632 struct diff_filepair
*p
= q
->queue
[i
];
1633 struct diff_filepair
*pair_to_free
= NULL
;
1635 if (DIFF_PAIR_UNMERGED(p
)) {
1638 else if (!DIFF_FILE_VALID(p
->one
) && DIFF_FILE_VALID(p
->two
)) {
1642 else if (DIFF_FILE_VALID(p
->one
) && !DIFF_FILE_VALID(p
->two
)) {
1646 * We would output this delete record if:
1648 * (1) this is a broken delete and the counterpart
1649 * broken create remains in the output; or
1650 * (2) this is not a broken delete, and rename_dst
1651 * does not have a rename/copy to move p->one->path
1654 * Otherwise, the counterpart broken create
1655 * has been turned into a rename-edit; or
1656 * delete did not have a matching create to
1659 if (DIFF_PAIR_BROKEN(p
)) {
1661 struct diff_rename_dst
*dst
= locate_rename_dst(p
);
1663 BUG("tracking failed somehow; failed to find associated dst for broken pair");
1665 /* counterpart is now rename/copy */
1669 if (p
->one
->rename_used
)
1670 /* this path remains */
1677 else if (!diff_unmodified_pair(p
))
1678 /* all the usual ones need to be kept */
1681 /* no need to keep unmodified pairs */
1685 pool_diff_free_filepair(pool
, pair_to_free
);
1687 diff_debug_queue("done copying original", &outq
);
1691 diff_debug_queue("done collapsing", q
);
1693 for (i
= 0; i
< rename_dst_nr
; i
++)
1694 if (rename_dst
[i
].filespec_to_free
)
1695 pool_free_filespec(pool
, rename_dst
[i
].filespec_to_free
);
1697 cleanup_dir_rename_info(&info
, dirs_removed
, dir_rename_count
!= NULL
);
1698 FREE_AND_NULL(rename_dst
);
1699 rename_dst_nr
= rename_dst_alloc
= 0;
1700 FREE_AND_NULL(rename_src
);
1701 rename_src_nr
= rename_src_alloc
= 0;
1703 strintmap_clear(break_idx
);
1704 FREE_AND_NULL(break_idx
);
1706 trace2_region_leave("diff", "write back to queue", options
->repo
);
1710 void diffcore_rename(struct diff_options
*options
)
1712 diffcore_rename_extended(options
, NULL
, NULL
, NULL
, NULL
, NULL
);