mingw(is_msys2_sh): handle forward slashes in the `sh.exe` path, too
[git/debian.git] / diffcore-rename.c
blobfab45b10d7e8c0650a0609a92e4d4d379335a236
1 /*
3 * Copyright (C) 2005 Junio C Hamano
4 */
6 #define USE_THE_REPOSITORY_VARIABLE
8 #include "git-compat-util.h"
9 #include "diff.h"
10 #include "diffcore.h"
11 #include "object-store-ll.h"
12 #include "hashmap.h"
13 #include "mem-pool.h"
14 #include "oid-array.h"
15 #include "progress.h"
16 #include "promisor-remote.h"
17 #include "string-list.h"
18 #include "strmap.h"
19 #include "trace2.h"
21 /* Table of rename/copy destinations */
23 static struct diff_rename_dst {
24 struct diff_filepair *p;
25 struct diff_filespec *filespec_to_free;
26 int is_rename; /* false -> just a create; true -> rename or copy */
27 } *rename_dst;
28 static int rename_dst_nr, rename_dst_alloc;
29 /* Mapping from break source pathname to break destination index */
30 static struct strintmap *break_idx = NULL;
32 static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)
34 /* Lookup by p->ONE->path */
35 int idx = break_idx ? strintmap_get(break_idx, p->one->path) : -1;
36 return (idx == -1) ? NULL : &rename_dst[idx];
40 * Returns 0 on success, -1 if we found a duplicate.
42 static int add_rename_dst(struct diff_filepair *p)
44 ALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);
45 rename_dst[rename_dst_nr].p = p;
46 rename_dst[rename_dst_nr].filespec_to_free = NULL;
47 rename_dst[rename_dst_nr].is_rename = 0;
48 rename_dst_nr++;
49 return 0;
52 /* Table of rename/copy src files */
53 static struct diff_rename_src {
54 struct diff_filepair *p;
55 unsigned short score; /* to remember the break score */
56 } *rename_src;
57 static int rename_src_nr, rename_src_alloc;
59 static void register_rename_src(struct diff_filepair *p)
61 if (p->broken_pair) {
62 if (!break_idx) {
63 break_idx = xmalloc(sizeof(*break_idx));
64 strintmap_init_with_options(break_idx, -1, NULL, 0);
66 strintmap_set(break_idx, p->one->path, rename_dst_nr);
69 ALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);
70 rename_src[rename_src_nr].p = p;
71 rename_src[rename_src_nr].score = p->score;
72 rename_src_nr++;
75 static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)
77 int src_len = strlen(src->path), dst_len = strlen(dst->path);
78 while (src_len && dst_len) {
79 char c1 = src->path[--src_len];
80 char c2 = dst->path[--dst_len];
81 if (c1 != c2)
82 return 0;
83 if (c1 == '/')
84 return 1;
86 return (!src_len || src->path[src_len - 1] == '/') &&
87 (!dst_len || dst->path[dst_len - 1] == '/');
90 struct diff_score {
91 int src; /* index in rename_src */
92 int dst; /* index in rename_dst */
93 unsigned short score;
94 short name_score;
97 struct inexact_prefetch_options {
98 struct repository *repo;
99 int skip_unmodified;
101 static void inexact_prefetch(void *prefetch_options)
103 struct inexact_prefetch_options *options = prefetch_options;
104 int i;
105 struct oid_array to_fetch = OID_ARRAY_INIT;
107 for (i = 0; i < rename_dst_nr; i++) {
108 if (rename_dst[i].p->renamed_pair)
110 * The loop in diffcore_rename() will not need these
111 * blobs, so skip prefetching.
113 continue; /* already found exact match */
114 diff_add_if_missing(options->repo, &to_fetch,
115 rename_dst[i].p->two);
117 for (i = 0; i < rename_src_nr; i++) {
118 if (options->skip_unmodified &&
119 diff_unmodified_pair(rename_src[i].p))
121 * The loop in diffcore_rename() will not need these
122 * blobs, so skip prefetching.
124 continue;
125 diff_add_if_missing(options->repo, &to_fetch,
126 rename_src[i].p->one);
128 promisor_remote_get_direct(options->repo, to_fetch.oid, to_fetch.nr);
129 oid_array_clear(&to_fetch);
132 static int estimate_similarity(struct repository *r,
133 struct diff_filespec *src,
134 struct diff_filespec *dst,
135 int minimum_score,
136 struct diff_populate_filespec_options *dpf_opt)
138 /* src points at a file that existed in the original tree (or
139 * optionally a file in the destination tree) and dst points
140 * at a newly created file. They may be quite similar, in which
141 * case we want to say src is renamed to dst or src is copied into
142 * dst, and then some edit has been applied to dst.
144 * Compare them and return how similar they are, representing
145 * the score as an integer between 0 and MAX_SCORE.
147 * When there is an exact match, it is considered a better
148 * match than anything else; the destination does not even
149 * call into this function in that case.
151 unsigned long max_size, delta_size, base_size, src_copied, literal_added;
152 int score;
154 /* We deal only with regular files. Symlink renames are handled
155 * only when they are exact matches --- in other words, no edits
156 * after renaming.
158 if (!S_ISREG(src->mode) || !S_ISREG(dst->mode))
159 return 0;
162 * Need to check that source and destination sizes are
163 * filled in before comparing them.
165 * If we already have "cnt_data" filled in, we know it's
166 * all good (avoid checking the size for zero, as that
167 * is a possible size - we really should have a flag to
168 * say whether the size is valid or not!)
170 dpf_opt->check_size_only = 1;
172 if (!src->cnt_data &&
173 diff_populate_filespec(r, src, dpf_opt))
174 return 0;
175 if (!dst->cnt_data &&
176 diff_populate_filespec(r, dst, dpf_opt))
177 return 0;
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)
192 return 0;
194 dpf_opt->check_size_only = 0;
196 if (!src->cnt_data && diff_populate_filespec(r, src, dpf_opt))
197 return 0;
198 if (!dst->cnt_data && diff_populate_filespec(r, dst, dpf_opt))
199 return 0;
201 if (diffcore_count_changes(r, src, dst,
202 &src->cnt_data, &dst->cnt_data,
203 &src_copied, &literal_added))
204 return 0;
206 /* How similar are they?
207 * what percentage of material in dst are from source?
209 if (!dst->size)
210 score = 0; /* should not happen */
211 else
212 score = (int)(src_copied * MAX_SCORE / max_size);
213 return score;
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++;
225 src->one->count++;
227 rename_dst[dst_index].filespec_to_free = dst->one;
228 rename_dst[dst_index].is_rename = 1;
230 dst->one = src->one;
231 dst->renamed_pair = 1;
232 if (!strcmp(dst->one->path, dst->two->path))
233 dst->score = rename_src[src_index].score;
234 else
235 dst->score = 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 */
247 if (a->dst < 0)
248 return (0 <= b->dst);
249 else if (b->dst < 0)
250 return -1;
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;
260 int index;
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))
269 return 0;
270 hash_object_file(r->hash_algo, filespec->data, filespec->size,
271 OBJ_BLOB, &filespec->oid);
273 return oidhash(&filespec->oid);
276 static int find_identical_files(struct hashmap *srcs,
277 int dst_index,
278 struct diff_options *options)
280 int renames = 0;
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) {
292 int score;
293 struct diff_filespec *source = p->filespec;
295 /* False hash collision? */
296 if (!oideq(&source->oid, &target->oid))
297 continue;
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)
301 continue;
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)
306 continue;
307 score += basename_same(source, target);
308 if (score > best_score) {
309 best = p;
310 best_score = score;
311 if (score == 2)
312 break;
315 /* Too many identical alternatives? Pick one */
316 if (!--i)
317 break;
319 if (best) {
320 record_rename_pair(dst_index, best->index, MAX_SCORE);
321 renames++;
323 return renames;
326 static void insert_file_table(struct repository *r,
327 struct mem_pool *pool,
328 struct hashmap *table, int index,
329 struct diff_filespec *filespec)
331 struct file_similarity *entry = mem_pool_alloc(pool, sizeof(*entry));
333 entry->index = index;
334 entry->filespec = filespec;
336 hashmap_entry_init(&entry->entry, hash_filespec(r, filespec));
337 hashmap_add(table, &entry->entry);
341 * Find exact renames first.
343 * The first round matches up the up-to-date entries,
344 * and then during the second round we try to match
345 * cache-dirty entries as well.
347 static int find_exact_renames(struct diff_options *options,
348 struct mem_pool *pool)
350 int i, renames = 0;
351 struct hashmap file_table;
353 /* Add all sources to the hash table in reverse order, because
354 * later on they will be retrieved in LIFO order.
356 hashmap_init(&file_table, NULL, NULL, rename_src_nr);
357 for (i = rename_src_nr-1; i >= 0; i--)
358 insert_file_table(options->repo, pool,
359 &file_table, i,
360 rename_src[i].p->one);
362 /* Walk the destinations and find best source match */
363 for (i = 0; i < rename_dst_nr; i++)
364 renames += find_identical_files(&file_table, i, options);
366 /* Free the hash data structure (entries will be freed with the pool) */
367 hashmap_clear(&file_table);
369 return renames;
372 struct dir_rename_info {
373 struct strintmap idx_map;
374 struct strmap dir_rename_guess;
375 struct strmap *dir_rename_count;
376 struct strintmap *relevant_source_dirs;
377 unsigned setup;
380 static char *get_dirname(const char *filename)
382 char *slash = strrchr(filename, '/');
383 return slash ? xstrndup(filename, slash - filename) : xstrdup("");
386 static void dirname_munge(char *filename)
388 char *slash = strrchr(filename, '/');
389 if (!slash)
390 slash = filename;
391 *slash = '\0';
394 static const char *get_highest_rename_path(struct strintmap *counts)
396 int highest_count = 0;
397 const char *highest_destination_dir = NULL;
398 struct hashmap_iter iter;
399 struct strmap_entry *entry;
401 strintmap_for_each_entry(counts, &iter, entry) {
402 const char *destination_dir = entry->key;
403 intptr_t count = (intptr_t)entry->value;
404 if (count > highest_count) {
405 highest_count = count;
406 highest_destination_dir = destination_dir;
409 return highest_destination_dir;
412 static const char *UNKNOWN_DIR = "/"; /* placeholder -- short, illegal directory */
414 static int dir_rename_already_determinable(struct strintmap *counts)
416 struct hashmap_iter iter;
417 struct strmap_entry *entry;
418 int first = 0, second = 0, unknown = 0;
419 strintmap_for_each_entry(counts, &iter, entry) {
420 const char *destination_dir = entry->key;
421 intptr_t count = (intptr_t)entry->value;
422 if (!strcmp(destination_dir, UNKNOWN_DIR)) {
423 unknown = count;
424 } else if (count >= first) {
425 second = first;
426 first = count;
427 } else if (count >= second) {
428 second = count;
431 return first > second + unknown;
434 static void increment_count(struct dir_rename_info *info,
435 const char *old_dir,
436 const char *new_dir)
438 struct strintmap *counts;
439 struct strmap_entry *e;
441 /* Get the {new_dirs -> counts} mapping using old_dir */
442 e = strmap_get_entry(info->dir_rename_count, old_dir);
443 if (e) {
444 counts = e->value;
445 } else {
446 counts = xmalloc(sizeof(*counts));
447 strintmap_init_with_options(counts, 0, NULL, 1);
448 strmap_put(info->dir_rename_count, old_dir, counts);
451 /* Increment the count for new_dir */
452 strintmap_incr(counts, new_dir, 1);
455 static void update_dir_rename_counts(struct dir_rename_info *info,
456 struct strintmap *dirs_removed,
457 const char *oldname,
458 const char *newname)
460 char *old_dir;
461 char *new_dir;
462 const char new_dir_first_char = newname[0];
463 int first_time_in_loop = 1;
465 if (!info->setup)
467 * info->setup is 0 here in two cases: (1) all auxiliary
468 * vars (like dirs_removed) were NULL so
469 * initialize_dir_rename_info() returned early, or (2)
470 * either break detection or copy detection are active so
471 * that we never called initialize_dir_rename_info(). In
472 * the former case, we don't have enough info to know if
473 * directories were renamed (because dirs_removed lets us
474 * know about a necessary prerequisite, namely if they were
475 * removed), and in the latter, we don't care about
476 * directory renames or find_basename_matches.
478 * This matters because both basename and inexact matching
479 * will also call update_dir_rename_counts(). In either of
480 * the above two cases info->dir_rename_counts will not
481 * have been properly initialized which prevents us from
482 * updating it, but in these two cases we don't care about
483 * dir_rename_counts anyway, so we can just exit early.
485 return;
488 old_dir = xstrdup(oldname);
489 new_dir = xstrdup(newname);
491 while (1) {
492 int drd_flag = NOT_RELEVANT;
494 /* Get old_dir, skip if its directory isn't relevant. */
495 dirname_munge(old_dir);
496 if (info->relevant_source_dirs &&
497 !strintmap_contains(info->relevant_source_dirs, old_dir))
498 break;
500 /* Get new_dir */
501 dirname_munge(new_dir);
504 * When renaming
505 * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"
506 * then this suggests that both
507 * a/b/c/d/e/ => a/b/some/thing/else/e/
508 * a/b/c/d/ => a/b/some/thing/else/
509 * so we want to increment counters for both. We do NOT,
510 * however, also want to suggest that there was the following
511 * rename:
512 * a/b/c/ => a/b/some/thing/
513 * so we need to quit at that point.
515 * Note the when first_time_in_loop, we only strip off the
516 * basename, and we don't care if that's different.
518 if (!first_time_in_loop) {
519 char *old_sub_dir = strchr(old_dir, '\0')+1;
520 char *new_sub_dir = strchr(new_dir, '\0')+1;
521 if (!*new_dir) {
523 * Special case when renaming to root directory,
524 * i.e. when new_dir == "". In this case, we had
525 * something like
526 * a/b/subdir => subdir
527 * and so dirname_munge() sets things up so that
528 * old_dir = "a/b\0subdir\0"
529 * new_dir = "\0ubdir\0"
530 * We didn't have a '/' to overwrite a '\0' onto
531 * in new_dir, so we have to compare differently.
533 if (new_dir_first_char != old_sub_dir[0] ||
534 strcmp(old_sub_dir+1, new_sub_dir))
535 break;
536 } else {
537 if (strcmp(old_sub_dir, new_sub_dir))
538 break;
543 * Above we suggested that we'd keep recording renames for
544 * all ancestor directories where the trailing directories
545 * matched, i.e. for
546 * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"
547 * we'd increment rename counts for each of
548 * a/b/c/d/e/ => a/b/some/thing/else/e/
549 * a/b/c/d/ => a/b/some/thing/else/
550 * However, we only need the rename counts for directories
551 * in dirs_removed whose value is RELEVANT_FOR_SELF.
552 * However, we add one special case of also recording it for
553 * first_time_in_loop because find_basename_matches() can
554 * use that as a hint to find a good pairing.
556 if (dirs_removed)
557 drd_flag = strintmap_get(dirs_removed, old_dir);
558 if (drd_flag == RELEVANT_FOR_SELF || first_time_in_loop)
559 increment_count(info, old_dir, new_dir);
561 first_time_in_loop = 0;
562 if (drd_flag == NOT_RELEVANT)
563 break;
564 /* If we hit toplevel directory ("") for old or new dir, quit */
565 if (!*old_dir || !*new_dir)
566 break;
569 /* Free resources we don't need anymore */
570 free(old_dir);
571 free(new_dir);
574 static void initialize_dir_rename_info(struct dir_rename_info *info,
575 struct strintmap *relevant_sources,
576 struct strintmap *dirs_removed,
577 struct strmap *dir_rename_count,
578 struct strmap *cached_pairs)
580 struct hashmap_iter iter;
581 struct strmap_entry *entry;
582 int i;
584 if (!dirs_removed && !relevant_sources) {
585 info->setup = 0;
586 return;
588 info->setup = 1;
590 info->dir_rename_count = dir_rename_count;
591 if (!info->dir_rename_count) {
592 info->dir_rename_count = xmalloc(sizeof(*dir_rename_count));
593 strmap_init(info->dir_rename_count);
595 strintmap_init_with_options(&info->idx_map, -1, NULL, 0);
596 strmap_init_with_options(&info->dir_rename_guess, NULL, 0);
598 /* Setup info->relevant_source_dirs */
599 info->relevant_source_dirs = NULL;
600 if (dirs_removed || !relevant_sources) {
601 info->relevant_source_dirs = dirs_removed; /* might be NULL */
602 } else {
603 info->relevant_source_dirs = xmalloc(sizeof(struct strintmap));
604 strintmap_init(info->relevant_source_dirs, 0 /* unused */);
605 strintmap_for_each_entry(relevant_sources, &iter, entry) {
606 char *dirname = get_dirname(entry->key);
607 if (!dirs_removed ||
608 strintmap_contains(dirs_removed, dirname))
609 strintmap_set(info->relevant_source_dirs,
610 dirname, 0 /* value irrelevant */);
611 free(dirname);
616 * Loop setting up both info->idx_map, and doing setup of
617 * info->dir_rename_count.
619 for (i = 0; i < rename_dst_nr; ++i) {
621 * For non-renamed files, make idx_map contain mapping of
622 * filename -> index (index within rename_dst, that is)
624 if (!rename_dst[i].is_rename) {
625 char *filename = rename_dst[i].p->two->path;
626 strintmap_set(&info->idx_map, filename, i);
627 continue;
631 * For everything else (i.e. renamed files), make
632 * dir_rename_count contain a map of a map:
633 * old_directory -> {new_directory -> count}
634 * In other words, for every pair look at the directories for
635 * the old filename and the new filename and count how many
636 * times that pairing occurs.
638 update_dir_rename_counts(info, dirs_removed,
639 rename_dst[i].p->one->path,
640 rename_dst[i].p->two->path);
643 /* Add cached_pairs to counts */
644 strmap_for_each_entry(cached_pairs, &iter, entry) {
645 const char *old_name = entry->key;
646 const char *new_name = entry->value;
647 if (!new_name)
648 /* known delete; ignore it */
649 continue;
651 update_dir_rename_counts(info, dirs_removed, old_name, new_name);
655 * Now we collapse
656 * dir_rename_count: old_directory -> {new_directory -> count}
657 * down to
658 * dir_rename_guess: old_directory -> best_new_directory
659 * where best_new_directory is the one with the highest count.
661 strmap_for_each_entry(info->dir_rename_count, &iter, entry) {
662 /* entry->key is source_dir */
663 struct strintmap *counts = entry->value;
664 char *best_newdir;
666 best_newdir = xstrdup(get_highest_rename_path(counts));
667 strmap_put(&info->dir_rename_guess, entry->key,
668 best_newdir);
672 void partial_clear_dir_rename_count(struct strmap *dir_rename_count)
674 struct hashmap_iter iter;
675 struct strmap_entry *entry;
677 strmap_for_each_entry(dir_rename_count, &iter, entry) {
678 struct strintmap *counts = entry->value;
679 strintmap_clear(counts);
681 strmap_partial_clear(dir_rename_count, 1);
684 static void cleanup_dir_rename_info(struct dir_rename_info *info,
685 struct strintmap *dirs_removed,
686 int keep_dir_rename_count)
688 struct hashmap_iter iter;
689 struct strmap_entry *entry;
690 struct string_list to_remove = STRING_LIST_INIT_NODUP;
691 int i;
693 if (!info->setup)
694 return;
696 /* idx_map */
697 strintmap_clear(&info->idx_map);
699 /* dir_rename_guess */
700 strmap_clear(&info->dir_rename_guess, 1);
702 /* relevant_source_dirs */
703 if (info->relevant_source_dirs &&
704 info->relevant_source_dirs != dirs_removed) {
705 strintmap_clear(info->relevant_source_dirs);
706 FREE_AND_NULL(info->relevant_source_dirs);
709 /* dir_rename_count */
710 if (!keep_dir_rename_count) {
711 partial_clear_dir_rename_count(info->dir_rename_count);
712 strmap_clear(info->dir_rename_count, 1);
713 FREE_AND_NULL(info->dir_rename_count);
714 return;
718 * Although dir_rename_count was passed in
719 * diffcore_rename_extended() and we want to keep it around and
720 * return it to that caller, we first want to remove any counts in
721 * the maps associated with UNKNOWN_DIR entries and any data
722 * associated with directories that weren't renamed.
724 strmap_for_each_entry(info->dir_rename_count, &iter, entry) {
725 const char *source_dir = entry->key;
726 struct strintmap *counts = entry->value;
728 if (!strintmap_get(dirs_removed, source_dir)) {
729 string_list_append(&to_remove, source_dir);
730 strintmap_clear(counts);
731 continue;
734 if (strintmap_contains(counts, UNKNOWN_DIR))
735 strintmap_remove(counts, UNKNOWN_DIR);
737 for (i = 0; i < to_remove.nr; ++i)
738 strmap_remove(info->dir_rename_count,
739 to_remove.items[i].string, 1);
740 string_list_clear(&to_remove, 0);
743 static const char *get_basename(const char *filename)
746 * gitbasename() has to worry about special drives, multiple
747 * directory separator characters, trailing slashes, NULL or
748 * empty strings, etc. We only work on filenames as stored in
749 * git, and thus get to ignore all those complications.
751 const char *base = strrchr(filename, '/');
752 return base ? base + 1 : filename;
755 static int idx_possible_rename(char *filename, struct dir_rename_info *info)
758 * Our comparison of files with the same basename (see
759 * find_basename_matches() below), is only helpful when after exact
760 * rename detection we have exactly one file with a given basename
761 * among the rename sources and also only exactly one file with
762 * that basename among the rename destinations. When we have
763 * multiple files with the same basename in either set, we do not
764 * know which to compare against. However, there are some
765 * filenames that occur in large numbers (particularly
766 * build-related filenames such as 'Makefile', '.gitignore', or
767 * 'build.gradle' that potentially exist within every single
768 * subdirectory), and for performance we want to be able to quickly
769 * find renames for these files too.
771 * The reason basename comparisons are a useful heuristic was that it
772 * is common for people to move files across directories while keeping
773 * their filename the same. If we had a way of determining or even
774 * making a good educated guess about which directory these non-unique
775 * basename files had moved the file to, we could check it.
776 * Luckily...
778 * When an entire directory is in fact renamed, we have two factors
779 * helping us out:
780 * (a) the original directory disappeared giving us a hint
781 * about when we can apply an extra heuristic.
782 * (a) we often have several files within that directory and
783 * subdirectories that are renamed without changes
784 * So, rules for a heuristic:
785 * (0) If there basename matches are non-unique (the condition under
786 * which this function is called) AND
787 * (1) the directory in which the file was found has disappeared
788 * (i.e. dirs_removed is non-NULL and has a relevant entry) THEN
789 * (2) use exact renames of files within the directory to determine
790 * where the directory is likely to have been renamed to. IF
791 * there is at least one exact rename from within that
792 * directory, we can proceed.
793 * (3) If there are multiple places the directory could have been
794 * renamed to based on exact renames, ignore all but one of them.
795 * Just use the destination with the most renames going to it.
796 * (4) Check if applying that directory rename to the original file
797 * would result in a destination filename that is in the
798 * potential rename set. If so, return the index of the
799 * destination file (the index within rename_dst).
800 * (5) Compare the original file and returned destination for
801 * similarity, and if they are sufficiently similar, record the
802 * rename.
804 * This function, idx_possible_rename(), is only responsible for (4).
805 * The conditions/steps in (1)-(3) are handled via setting up
806 * dir_rename_count and dir_rename_guess in
807 * initialize_dir_rename_info(). Steps (0) and (5) are handled by
808 * the caller of this function.
810 char *old_dir, *new_dir;
811 struct strbuf new_path = STRBUF_INIT;
812 int idx;
814 if (!info->setup)
815 return -1;
817 old_dir = get_dirname(filename);
818 new_dir = strmap_get(&info->dir_rename_guess, old_dir);
819 free(old_dir);
820 if (!new_dir)
821 return -1;
823 strbuf_addstr(&new_path, new_dir);
824 strbuf_addch(&new_path, '/');
825 strbuf_addstr(&new_path, get_basename(filename));
827 idx = strintmap_get(&info->idx_map, new_path.buf);
828 strbuf_release(&new_path);
829 return idx;
832 struct basename_prefetch_options {
833 struct repository *repo;
834 struct strintmap *relevant_sources;
835 struct strintmap *sources;
836 struct strintmap *dests;
837 struct dir_rename_info *info;
839 static void basename_prefetch(void *prefetch_options)
841 struct basename_prefetch_options *options = prefetch_options;
842 struct strintmap *relevant_sources = options->relevant_sources;
843 struct strintmap *sources = options->sources;
844 struct strintmap *dests = options->dests;
845 struct dir_rename_info *info = options->info;
846 int i;
847 struct oid_array to_fetch = OID_ARRAY_INIT;
850 * TODO: The following loops mirror the code/logic from
851 * find_basename_matches(), though not quite exactly. Maybe
852 * abstract the iteration logic out somehow?
854 for (i = 0; i < rename_src_nr; ++i) {
855 char *filename = rename_src[i].p->one->path;
856 const char *base = NULL;
857 intptr_t src_index;
858 intptr_t dst_index;
860 /* Skip irrelevant sources */
861 if (relevant_sources &&
862 !strintmap_contains(relevant_sources, filename))
863 continue;
866 * If the basename is unique among remaining sources, then
867 * src_index will equal 'i' and we can attempt to match it
868 * to a unique basename in the destinations. Otherwise,
869 * use directory rename heuristics, if possible.
871 base = get_basename(filename);
872 src_index = strintmap_get(sources, base);
873 assert(src_index == -1 || src_index == i);
875 if (strintmap_contains(dests, base)) {
876 struct diff_filespec *one, *two;
878 /* Find a matching destination, if possible */
879 dst_index = strintmap_get(dests, base);
880 if (src_index == -1 || dst_index == -1) {
881 src_index = i;
882 dst_index = idx_possible_rename(filename, info);
884 if (dst_index == -1)
885 continue;
887 /* Ignore this dest if already used in a rename */
888 if (rename_dst[dst_index].is_rename)
889 continue; /* already used previously */
891 one = rename_src[src_index].p->one;
892 two = rename_dst[dst_index].p->two;
894 /* Add the pairs */
895 diff_add_if_missing(options->repo, &to_fetch, two);
896 diff_add_if_missing(options->repo, &to_fetch, one);
900 promisor_remote_get_direct(options->repo, to_fetch.oid, to_fetch.nr);
901 oid_array_clear(&to_fetch);
904 static int find_basename_matches(struct diff_options *options,
905 int minimum_score,
906 struct dir_rename_info *info,
907 struct strintmap *relevant_sources,
908 struct strintmap *dirs_removed)
911 * When I checked in early 2020, over 76% of file renames in linux
912 * just moved files to a different directory but kept the same
913 * basename. gcc did that with over 64% of renames, gecko did it
914 * with over 79%, and WebKit did it with over 89%.
916 * Therefore we can bypass the normal exhaustive NxM matrix
917 * comparison of similarities between all potential rename sources
918 * and destinations by instead using file basename as a hint (i.e.
919 * the portion of the filename after the last '/'), checking for
920 * similarity between files with the same basename, and if we find
921 * a pair that are sufficiently similar, record the rename pair and
922 * exclude those two from the NxM matrix.
924 * This *might* cause us to find a less than optimal pairing (if
925 * there is another file that we are even more similar to but has a
926 * different basename). Given the huge performance advantage
927 * basename matching provides, and given the frequency with which
928 * people use the same basename in real world projects, that's a
929 * trade-off we are willing to accept when doing just rename
930 * detection.
932 * If someone wants copy detection that implies they are willing to
933 * spend more cycles to find similarities between files, so it may
934 * be less likely that this heuristic is wanted. If someone is
935 * doing break detection, that means they do not want filename
936 * similarity to imply any form of content similiarity, and thus
937 * this heuristic would definitely be incompatible.
940 int i, renames = 0;
941 struct strintmap sources;
942 struct strintmap dests;
943 struct diff_populate_filespec_options dpf_options = {
944 .check_binary = 0,
945 .missing_object_cb = NULL,
946 .missing_object_data = NULL
948 struct basename_prefetch_options prefetch_options = {
949 .repo = options->repo,
950 .relevant_sources = relevant_sources,
951 .sources = &sources,
952 .dests = &dests,
953 .info = info
957 * Create maps of basename -> fullname(s) for remaining sources and
958 * dests.
960 strintmap_init_with_options(&sources, -1, NULL, 0);
961 strintmap_init_with_options(&dests, -1, NULL, 0);
962 for (i = 0; i < rename_src_nr; ++i) {
963 char *filename = rename_src[i].p->one->path;
964 const char *base;
966 /* exact renames removed in remove_unneeded_paths_from_src() */
967 assert(!rename_src[i].p->one->rename_used);
969 /* Record index within rename_src (i) if basename is unique */
970 base = get_basename(filename);
971 if (strintmap_contains(&sources, base))
972 strintmap_set(&sources, base, -1);
973 else
974 strintmap_set(&sources, base, i);
976 for (i = 0; i < rename_dst_nr; ++i) {
977 char *filename = rename_dst[i].p->two->path;
978 const char *base;
980 if (rename_dst[i].is_rename)
981 continue; /* involved in exact match already. */
983 /* Record index within rename_dst (i) if basename is unique */
984 base = get_basename(filename);
985 if (strintmap_contains(&dests, base))
986 strintmap_set(&dests, base, -1);
987 else
988 strintmap_set(&dests, base, i);
991 if (options->repo == the_repository && repo_has_promisor_remote(the_repository)) {
992 dpf_options.missing_object_cb = basename_prefetch;
993 dpf_options.missing_object_data = &prefetch_options;
996 /* Now look for basename matchups and do similarity estimation */
997 for (i = 0; i < rename_src_nr; ++i) {
998 char *filename = rename_src[i].p->one->path;
999 const char *base = NULL;
1000 intptr_t src_index;
1001 intptr_t dst_index;
1003 /* Skip irrelevant sources */
1004 if (relevant_sources &&
1005 !strintmap_contains(relevant_sources, filename))
1006 continue;
1009 * If the basename is unique among remaining sources, then
1010 * src_index will equal 'i' and we can attempt to match it
1011 * to a unique basename in the destinations. Otherwise,
1012 * use directory rename heuristics, if possible.
1014 base = get_basename(filename);
1015 src_index = strintmap_get(&sources, base);
1016 assert(src_index == -1 || src_index == i);
1018 if (strintmap_contains(&dests, base)) {
1019 struct diff_filespec *one, *two;
1020 int score;
1022 /* Find a matching destination, if possible */
1023 dst_index = strintmap_get(&dests, base);
1024 if (src_index == -1 || dst_index == -1) {
1025 src_index = i;
1026 dst_index = idx_possible_rename(filename, info);
1028 if (dst_index == -1)
1029 continue;
1031 /* Ignore this dest if already used in a rename */
1032 if (rename_dst[dst_index].is_rename)
1033 continue; /* already used previously */
1035 /* Estimate the similarity */
1036 one = rename_src[src_index].p->one;
1037 two = rename_dst[dst_index].p->two;
1038 score = estimate_similarity(options->repo, one, two,
1039 minimum_score, &dpf_options);
1041 /* If sufficiently similar, record as rename pair */
1042 if (score < minimum_score)
1043 continue;
1044 record_rename_pair(dst_index, src_index, score);
1045 renames++;
1046 update_dir_rename_counts(info, dirs_removed,
1047 one->path, two->path);
1050 * Found a rename so don't need text anymore; if we
1051 * didn't find a rename, the filespec_blob would get
1052 * re-used when doing the matrix of comparisons.
1054 diff_free_filespec_blob(one);
1055 diff_free_filespec_blob(two);
1059 strintmap_clear(&sources);
1060 strintmap_clear(&dests);
1062 return renames;
1065 #define NUM_CANDIDATE_PER_DST 4
1066 static void record_if_better(struct diff_score m[], struct diff_score *o)
1068 int i, worst;
1070 /* find the worst one */
1071 worst = 0;
1072 for (i = 1; i < NUM_CANDIDATE_PER_DST; i++)
1073 if (score_compare(&m[i], &m[worst]) > 0)
1074 worst = i;
1076 /* is it better than the worst one? */
1077 if (score_compare(&m[worst], o) > 0)
1078 m[worst] = *o;
1082 * Returns:
1083 * 0 if we are under the limit;
1084 * 1 if we need to disable inexact rename detection;
1085 * 2 if we would be under the limit if we were given -C instead of -C -C.
1087 static int too_many_rename_candidates(int num_destinations, int num_sources,
1088 struct diff_options *options)
1090 int rename_limit = options->rename_limit;
1091 int i, limited_sources;
1093 options->needed_rename_limit = 0;
1096 * This basically does a test for the rename matrix not
1097 * growing larger than a "rename_limit" square matrix, ie:
1099 * num_destinations * num_sources > rename_limit * rename_limit
1101 * We use st_mult() to check overflow conditions; in the
1102 * exceptional circumstance that size_t isn't large enough to hold
1103 * the multiplication, the system won't be able to allocate enough
1104 * memory for the matrix anyway.
1106 if (rename_limit <= 0)
1107 return 0; /* treat as unlimited */
1108 if (st_mult(num_destinations, num_sources)
1109 <= st_mult(rename_limit, rename_limit))
1110 return 0;
1112 options->needed_rename_limit =
1113 num_sources > num_destinations ? num_sources : num_destinations;
1115 /* Are we running under -C -C? */
1116 if (!options->flags.find_copies_harder)
1117 return 1;
1119 /* Would we bust the limit if we were running under -C? */
1120 for (limited_sources = i = 0; i < num_sources; i++) {
1121 if (diff_unmodified_pair(rename_src[i].p))
1122 continue;
1123 limited_sources++;
1125 if (st_mult(num_destinations, limited_sources)
1126 <= st_mult(rename_limit, rename_limit))
1127 return 2;
1128 return 1;
1131 static int find_renames(struct diff_score *mx,
1132 int dst_cnt,
1133 int minimum_score,
1134 int copies,
1135 struct dir_rename_info *info,
1136 struct strintmap *dirs_removed)
1138 int count = 0, i;
1140 for (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {
1141 struct diff_rename_dst *dst;
1143 if ((mx[i].dst < 0) ||
1144 (mx[i].score < minimum_score))
1145 break; /* there is no more usable pair. */
1146 dst = &rename_dst[mx[i].dst];
1147 if (dst->is_rename)
1148 continue; /* already done, either exact or fuzzy. */
1149 if (!copies && rename_src[mx[i].src].p->one->rename_used)
1150 continue;
1151 record_rename_pair(mx[i].dst, mx[i].src, mx[i].score);
1152 count++;
1153 update_dir_rename_counts(info, dirs_removed,
1154 rename_src[mx[i].src].p->one->path,
1155 rename_dst[mx[i].dst].p->two->path);
1157 return count;
1160 static void remove_unneeded_paths_from_src(int detecting_copies,
1161 struct strintmap *interesting)
1163 int i, new_num_src;
1165 if (detecting_copies && !interesting)
1166 return; /* nothing to remove */
1167 if (break_idx)
1168 return; /* culling incompatible with break detection */
1171 * Note on reasons why we cull unneeded sources but not destinations:
1172 * 1) Pairings are stored in rename_dst (not rename_src), which we
1173 * need to keep around. So, we just can't cull rename_dst even
1174 * if we wanted to. But doing so wouldn't help because...
1176 * 2) There is a matrix pairwise comparison that follows the
1177 * "Performing inexact rename detection" progress message.
1178 * Iterating over the destinations is done in the outer loop,
1179 * hence we only iterate over each of those once and we can
1180 * easily skip the outer loop early if the destination isn't
1181 * relevant. That's only one check per destination path to
1182 * skip.
1184 * By contrast, the sources are iterated in the inner loop; if
1185 * we check whether a source can be skipped, then we'll be
1186 * checking it N separate times, once for each destination.
1187 * We don't want to have to iterate over known-not-needed
1188 * sources N times each, so avoid that by removing the sources
1189 * from rename_src here.
1191 for (i = 0, new_num_src = 0; i < rename_src_nr; i++) {
1192 struct diff_filespec *one = rename_src[i].p->one;
1195 * renames are stored in rename_dst, so if a rename has
1196 * already been detected using this source, we can just
1197 * remove the source knowing rename_dst has its info.
1199 if (!detecting_copies && one->rename_used)
1200 continue;
1202 /* If we don't care about the source path, skip it */
1203 if (interesting && !strintmap_contains(interesting, one->path))
1204 continue;
1206 if (new_num_src < i)
1207 memcpy(&rename_src[new_num_src], &rename_src[i],
1208 sizeof(struct diff_rename_src));
1209 new_num_src++;
1212 rename_src_nr = new_num_src;
1215 static void handle_early_known_dir_renames(struct dir_rename_info *info,
1216 struct strintmap *relevant_sources,
1217 struct strintmap *dirs_removed)
1220 * Directory renames are determined via an aggregate of all renames
1221 * under them and using a "majority wins" rule. The fact that
1222 * "majority wins", though, means we don't need all the renames
1223 * under the given directory, we only need enough to ensure we have
1224 * a majority.
1227 int i, new_num_src;
1228 struct hashmap_iter iter;
1229 struct strmap_entry *entry;
1231 if (!dirs_removed || !relevant_sources)
1232 return; /* nothing to cull */
1233 if (break_idx)
1234 return; /* culling incompatbile with break detection */
1237 * Supplement dir_rename_count with number of potential renames,
1238 * marking all potential rename sources as mapping to UNKNOWN_DIR.
1240 for (i = 0; i < rename_src_nr; i++) {
1241 char *old_dir;
1242 struct diff_filespec *one = rename_src[i].p->one;
1245 * sources that are part of a rename will have already been
1246 * removed by a prior call to remove_unneeded_paths_from_src()
1248 assert(!one->rename_used);
1250 old_dir = get_dirname(one->path);
1251 while (*old_dir != '\0' &&
1252 NOT_RELEVANT != strintmap_get(dirs_removed, old_dir)) {
1253 char *freeme = old_dir;
1255 increment_count(info, old_dir, UNKNOWN_DIR);
1256 old_dir = get_dirname(old_dir);
1258 /* Free resources we don't need anymore */
1259 free(freeme);
1262 * old_dir and new_dir free'd in increment_count, but
1263 * get_dirname() gives us a new pointer we need to free for
1264 * old_dir. Also, if the loop runs 0 times we need old_dir
1265 * to be freed.
1267 free(old_dir);
1271 * For any directory which we need a potential rename detected for
1272 * (i.e. those marked as RELEVANT_FOR_SELF in dirs_removed), check
1273 * whether we have enough renames to satisfy the "majority rules"
1274 * requirement such that detecting any more renames of files under
1275 * it won't change the result. For any such directory, mark that
1276 * we no longer need to detect a rename for it. However, since we
1277 * might need to still detect renames for an ancestor of that
1278 * directory, use RELEVANT_FOR_ANCESTOR.
1280 strmap_for_each_entry(info->dir_rename_count, &iter, entry) {
1281 /* entry->key is source_dir */
1282 struct strintmap *counts = entry->value;
1284 if (strintmap_get(dirs_removed, entry->key) ==
1285 RELEVANT_FOR_SELF &&
1286 dir_rename_already_determinable(counts)) {
1287 strintmap_set(dirs_removed, entry->key,
1288 RELEVANT_FOR_ANCESTOR);
1292 for (i = 0, new_num_src = 0; i < rename_src_nr; i++) {
1293 struct diff_filespec *one = rename_src[i].p->one;
1294 int val;
1296 val = strintmap_get(relevant_sources, one->path);
1299 * sources that were not found in relevant_sources should
1300 * have already been removed by a prior call to
1301 * remove_unneeded_paths_from_src()
1303 assert(val != -1);
1305 if (val == RELEVANT_LOCATION) {
1306 int removable = 1;
1307 char *dir = get_dirname(one->path);
1308 while (1) {
1309 char *freeme = dir;
1310 int res = strintmap_get(dirs_removed, dir);
1312 /* Quit if not found or irrelevant */
1313 if (res == NOT_RELEVANT)
1314 break;
1315 /* If RELEVANT_FOR_SELF, can't remove */
1316 if (res == RELEVANT_FOR_SELF) {
1317 removable = 0;
1318 break;
1320 /* Else continue searching upwards */
1321 assert(res == RELEVANT_FOR_ANCESTOR);
1322 dir = get_dirname(dir);
1323 free(freeme);
1325 free(dir);
1326 if (removable) {
1327 strintmap_set(relevant_sources, one->path,
1328 RELEVANT_NO_MORE);
1329 continue;
1333 if (new_num_src < i)
1334 memcpy(&rename_src[new_num_src], &rename_src[i],
1335 sizeof(struct diff_rename_src));
1336 new_num_src++;
1339 rename_src_nr = new_num_src;
1342 static void free_filespec_data(struct diff_filespec *spec)
1344 if (!--spec->count)
1345 diff_free_filespec_data(spec);
1348 static void pool_free_filespec(struct mem_pool *pool,
1349 struct diff_filespec *spec)
1351 if (!pool) {
1352 free_filespec(spec);
1353 return;
1357 * Similar to free_filespec(), but only frees the data. The spec
1358 * itself was allocated in the pool and should not be individually
1359 * freed.
1361 free_filespec_data(spec);
1364 void pool_diff_free_filepair(struct mem_pool *pool,
1365 struct diff_filepair *p)
1367 if (!pool) {
1368 diff_free_filepair(p);
1369 return;
1373 * Similar to diff_free_filepair() but only frees the data from the
1374 * filespecs; not the filespecs or the filepair which were
1375 * allocated from the pool.
1377 free_filespec_data(p->one);
1378 free_filespec_data(p->two);
1381 void diffcore_rename_extended(struct diff_options *options,
1382 struct mem_pool *pool,
1383 struct strintmap *relevant_sources,
1384 struct strintmap *dirs_removed,
1385 struct strmap *dir_rename_count,
1386 struct strmap *cached_pairs)
1388 int detect_rename = options->detect_rename;
1389 int minimum_score = options->rename_score;
1390 struct diff_queue_struct *q = &diff_queued_diff;
1391 struct diff_queue_struct outq;
1392 struct diff_score *mx;
1393 int i, j, rename_count, skip_unmodified = 0;
1394 int num_destinations, dst_cnt;
1395 int num_sources, want_copies;
1396 struct progress *progress = NULL;
1397 struct mem_pool local_pool;
1398 struct dir_rename_info info;
1399 struct diff_populate_filespec_options dpf_options = {
1400 .check_binary = 0,
1401 .missing_object_cb = NULL,
1402 .missing_object_data = NULL
1404 struct inexact_prefetch_options prefetch_options = {
1405 .repo = options->repo
1408 trace2_region_enter("diff", "setup", options->repo);
1409 info.setup = 0;
1410 assert(!dir_rename_count || strmap_empty(dir_rename_count));
1411 want_copies = (detect_rename == DIFF_DETECT_COPY);
1412 if (dirs_removed && (break_idx || want_copies))
1413 BUG("dirs_removed incompatible with break/copy detection");
1414 if (break_idx && relevant_sources)
1415 BUG("break detection incompatible with source specification");
1416 if (!minimum_score)
1417 minimum_score = DEFAULT_RENAME_SCORE;
1419 for (i = 0; i < q->nr; i++) {
1420 struct diff_filepair *p = q->queue[i];
1421 if (!DIFF_FILE_VALID(p->one)) {
1422 if (!DIFF_FILE_VALID(p->two))
1423 continue; /* unmerged */
1424 else if (options->single_follow &&
1425 strcmp(options->single_follow, p->two->path))
1426 continue; /* not interested */
1427 else if (!options->flags.rename_empty &&
1428 is_empty_blob_oid(&p->two->oid, the_repository->hash_algo))
1429 continue;
1430 else if (add_rename_dst(p) < 0) {
1431 warning("skipping rename detection, detected"
1432 " duplicate destination '%s'",
1433 p->two->path);
1434 goto cleanup;
1437 else if (!options->flags.rename_empty &&
1438 is_empty_blob_oid(&p->one->oid, the_repository->hash_algo))
1439 continue;
1440 else if (!DIFF_PAIR_UNMERGED(p) && !DIFF_FILE_VALID(p->two)) {
1442 * If the source is a broken "delete", and
1443 * they did not really want to get broken,
1444 * that means the source actually stays.
1445 * So we increment the "rename_used" score
1446 * by one, to indicate ourselves as a user
1448 if (p->broken_pair && !p->score)
1449 p->one->rename_used++;
1450 register_rename_src(p);
1452 else if (want_copies) {
1454 * Increment the "rename_used" score by
1455 * one, to indicate ourselves as a user.
1457 p->one->rename_used++;
1458 register_rename_src(p);
1461 trace2_region_leave("diff", "setup", options->repo);
1462 if (rename_dst_nr == 0 || rename_src_nr == 0)
1463 goto cleanup; /* nothing to do */
1465 trace2_region_enter("diff", "exact renames", options->repo);
1466 mem_pool_init(&local_pool, 32*1024);
1468 * We really want to cull the candidates list early
1469 * with cheap tests in order to avoid doing deltas.
1471 rename_count = find_exact_renames(options, &local_pool);
1473 * Discard local_pool immediately instead of at "cleanup:" in order
1474 * to reduce maximum memory usage; inexact rename detection uses up
1475 * a fair amount of memory, and mem_pools can too.
1477 mem_pool_discard(&local_pool, 0);
1478 trace2_region_leave("diff", "exact renames", options->repo);
1480 /* Did we only want exact renames? */
1481 if (minimum_score == MAX_SCORE)
1482 goto cleanup;
1484 num_sources = rename_src_nr;
1486 if (want_copies || break_idx) {
1488 * Cull sources:
1489 * - remove ones corresponding to exact renames
1490 * - remove ones not found in relevant_sources
1492 trace2_region_enter("diff", "cull after exact", options->repo);
1493 remove_unneeded_paths_from_src(want_copies, relevant_sources);
1494 trace2_region_leave("diff", "cull after exact", options->repo);
1495 } else {
1496 /* Determine minimum score to match basenames */
1497 double factor = 0.5;
1498 char *basename_factor = getenv("GIT_BASENAME_FACTOR");
1499 int min_basename_score;
1501 if (basename_factor)
1502 factor = strtol(basename_factor, NULL, 10)/100.0;
1503 assert(factor >= 0.0 && factor <= 1.0);
1504 min_basename_score = minimum_score +
1505 (int)(factor * (MAX_SCORE - minimum_score));
1508 * Cull sources:
1509 * - remove ones involved in renames (found via exact match)
1511 trace2_region_enter("diff", "cull after exact", options->repo);
1512 remove_unneeded_paths_from_src(want_copies, NULL);
1513 trace2_region_leave("diff", "cull after exact", options->repo);
1515 /* Preparation for basename-driven matching. */
1516 trace2_region_enter("diff", "dir rename setup", options->repo);
1517 initialize_dir_rename_info(&info, relevant_sources,
1518 dirs_removed, dir_rename_count,
1519 cached_pairs);
1520 trace2_region_leave("diff", "dir rename setup", options->repo);
1522 /* Utilize file basenames to quickly find renames. */
1523 trace2_region_enter("diff", "basename matches", options->repo);
1524 rename_count += find_basename_matches(options,
1525 min_basename_score,
1526 &info,
1527 relevant_sources,
1528 dirs_removed);
1529 trace2_region_leave("diff", "basename matches", options->repo);
1532 * Cull sources, again:
1533 * - remove ones involved in renames (found via basenames)
1534 * - remove ones not found in relevant_sources
1535 * and
1536 * - remove ones in relevant_sources which are needed only
1537 * for directory renames IF no ancestory directory
1538 * actually needs to know any more individual path
1539 * renames under them
1541 trace2_region_enter("diff", "cull basename", options->repo);
1542 remove_unneeded_paths_from_src(want_copies, relevant_sources);
1543 handle_early_known_dir_renames(&info, relevant_sources,
1544 dirs_removed);
1545 trace2_region_leave("diff", "cull basename", options->repo);
1548 /* Calculate how many rename destinations are left */
1549 num_destinations = (rename_dst_nr - rename_count);
1550 num_sources = rename_src_nr; /* rename_src_nr reflects lower number */
1552 /* All done? */
1553 if (!num_destinations || !num_sources)
1554 goto cleanup;
1556 switch (too_many_rename_candidates(num_destinations, num_sources,
1557 options)) {
1558 case 1:
1559 goto cleanup;
1560 case 2:
1561 options->degraded_cc_to_c = 1;
1562 skip_unmodified = 1;
1563 break;
1564 default:
1565 break;
1568 trace2_region_enter("diff", "inexact renames", options->repo);
1569 if (options->show_rename_progress) {
1570 progress = start_delayed_progress(
1571 _("Performing inexact rename detection"),
1572 (uint64_t)num_destinations * (uint64_t)num_sources);
1575 /* Finish setting up dpf_options */
1576 prefetch_options.skip_unmodified = skip_unmodified;
1577 if (options->repo == the_repository && repo_has_promisor_remote(the_repository)) {
1578 dpf_options.missing_object_cb = inexact_prefetch;
1579 dpf_options.missing_object_data = &prefetch_options;
1582 CALLOC_ARRAY(mx, st_mult(NUM_CANDIDATE_PER_DST, num_destinations));
1583 for (dst_cnt = i = 0; i < rename_dst_nr; i++) {
1584 struct diff_filespec *two = rename_dst[i].p->two;
1585 struct diff_score *m;
1587 if (rename_dst[i].is_rename)
1588 continue; /* exact or basename match already handled */
1590 m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];
1591 for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)
1592 m[j].dst = -1;
1594 for (j = 0; j < rename_src_nr; j++) {
1595 struct diff_filespec *one = rename_src[j].p->one;
1596 struct diff_score this_src;
1598 assert(!one->rename_used || want_copies || break_idx);
1600 if (skip_unmodified &&
1601 diff_unmodified_pair(rename_src[j].p))
1602 continue;
1604 this_src.score = estimate_similarity(options->repo,
1605 one, two,
1606 minimum_score,
1607 &dpf_options);
1608 this_src.name_score = basename_same(one, two);
1609 this_src.dst = i;
1610 this_src.src = j;
1611 record_if_better(m, &this_src);
1613 * Once we run estimate_similarity,
1614 * We do not need the text anymore.
1616 diff_free_filespec_blob(one);
1617 diff_free_filespec_blob(two);
1619 dst_cnt++;
1620 display_progress(progress,
1621 (uint64_t)dst_cnt * (uint64_t)num_sources);
1623 stop_progress(&progress);
1625 /* cost matrix sorted by most to least similar pair */
1626 STABLE_QSORT(mx, dst_cnt * NUM_CANDIDATE_PER_DST, score_compare);
1628 rename_count += find_renames(mx, dst_cnt, minimum_score, 0,
1629 &info, dirs_removed);
1630 if (want_copies)
1631 rename_count += find_renames(mx, dst_cnt, minimum_score, 1,
1632 &info, dirs_removed);
1633 free(mx);
1634 trace2_region_leave("diff", "inexact renames", options->repo);
1636 cleanup:
1637 /* At this point, we have found some renames and copies and they
1638 * are recorded in rename_dst. The original list is still in *q.
1640 trace2_region_enter("diff", "write back to queue", options->repo);
1641 DIFF_QUEUE_CLEAR(&outq);
1642 for (i = 0; i < q->nr; i++) {
1643 struct diff_filepair *p = q->queue[i];
1644 struct diff_filepair *pair_to_free = NULL;
1646 if (DIFF_PAIR_UNMERGED(p)) {
1647 diff_q(&outq, p);
1649 else if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {
1650 /* Creation */
1651 diff_q(&outq, p);
1653 else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {
1655 * Deletion
1657 * We would output this delete record if:
1659 * (1) this is a broken delete and the counterpart
1660 * broken create remains in the output; or
1661 * (2) this is not a broken delete, and rename_dst
1662 * does not have a rename/copy to move p->one->path
1663 * out of existence.
1665 * Otherwise, the counterpart broken create
1666 * has been turned into a rename-edit; or
1667 * delete did not have a matching create to
1668 * begin with.
1670 if (DIFF_PAIR_BROKEN(p)) {
1671 /* broken delete */
1672 struct diff_rename_dst *dst = locate_rename_dst(p);
1673 if (!dst)
1674 BUG("tracking failed somehow; failed to find associated dst for broken pair");
1675 if (dst->is_rename)
1676 /* counterpart is now rename/copy */
1677 pair_to_free = p;
1679 else {
1680 if (p->one->rename_used)
1681 /* this path remains */
1682 pair_to_free = p;
1685 if (!pair_to_free)
1686 diff_q(&outq, p);
1688 else if (!diff_unmodified_pair(p))
1689 /* all the usual ones need to be kept */
1690 diff_q(&outq, p);
1691 else
1692 /* no need to keep unmodified pairs */
1693 pair_to_free = p;
1695 if (pair_to_free)
1696 pool_diff_free_filepair(pool, pair_to_free);
1698 diff_debug_queue("done copying original", &outq);
1700 free(q->queue);
1701 *q = outq;
1702 diff_debug_queue("done collapsing", q);
1704 for (i = 0; i < rename_dst_nr; i++)
1705 if (rename_dst[i].filespec_to_free)
1706 pool_free_filespec(pool, rename_dst[i].filespec_to_free);
1708 cleanup_dir_rename_info(&info, dirs_removed, dir_rename_count != NULL);
1709 FREE_AND_NULL(rename_dst);
1710 rename_dst_nr = rename_dst_alloc = 0;
1711 FREE_AND_NULL(rename_src);
1712 rename_src_nr = rename_src_alloc = 0;
1713 if (break_idx) {
1714 strintmap_clear(break_idx);
1715 FREE_AND_NULL(break_idx);
1717 trace2_region_leave("diff", "write back to queue", options->repo);
1718 return;
1721 void diffcore_rename(struct diff_options *options)
1723 diffcore_rename_extended(options, NULL, NULL, NULL, NULL, NULL);