refs: move `struct pack_refs_opts` to where it's used
[alt-git.git] / diffcore-rename.c
blob5a6e2bcac7147e487624c1bf53e1572a54b0d93d
1 /*
3 * Copyright (C) 2005 Junio C Hamano
4 */
5 #include "git-compat-util.h"
6 #include "diff.h"
7 #include "diffcore.h"
8 #include "object-store-ll.h"
9 #include "hashmap.h"
10 #include "mem-pool.h"
11 #include "oid-array.h"
12 #include "progress.h"
13 #include "promisor-remote.h"
14 #include "string-list.h"
15 #include "strmap.h"
16 #include "trace2.h"
18 /* Table of rename/copy destinations */
20 static struct diff_rename_dst {
21 struct diff_filepair *p;
22 struct diff_filespec *filespec_to_free;
23 int is_rename; /* false -> just a create; true -> rename or copy */
24 } *rename_dst;
25 static int rename_dst_nr, rename_dst_alloc;
26 /* Mapping from break source pathname to break destination index */
27 static struct strintmap *break_idx = NULL;
29 static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)
31 /* Lookup by p->ONE->path */
32 int idx = break_idx ? strintmap_get(break_idx, p->one->path) : -1;
33 return (idx == -1) ? NULL : &rename_dst[idx];
37 * Returns 0 on success, -1 if we found a duplicate.
39 static int add_rename_dst(struct diff_filepair *p)
41 ALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);
42 rename_dst[rename_dst_nr].p = p;
43 rename_dst[rename_dst_nr].filespec_to_free = NULL;
44 rename_dst[rename_dst_nr].is_rename = 0;
45 rename_dst_nr++;
46 return 0;
49 /* Table of rename/copy src files */
50 static struct diff_rename_src {
51 struct diff_filepair *p;
52 unsigned short score; /* to remember the break score */
53 } *rename_src;
54 static int rename_src_nr, rename_src_alloc;
56 static void register_rename_src(struct diff_filepair *p)
58 if (p->broken_pair) {
59 if (!break_idx) {
60 break_idx = xmalloc(sizeof(*break_idx));
61 strintmap_init_with_options(break_idx, -1, NULL, 0);
63 strintmap_set(break_idx, p->one->path, rename_dst_nr);
66 ALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);
67 rename_src[rename_src_nr].p = p;
68 rename_src[rename_src_nr].score = p->score;
69 rename_src_nr++;
72 static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)
74 int src_len = strlen(src->path), dst_len = strlen(dst->path);
75 while (src_len && dst_len) {
76 char c1 = src->path[--src_len];
77 char c2 = dst->path[--dst_len];
78 if (c1 != c2)
79 return 0;
80 if (c1 == '/')
81 return 1;
83 return (!src_len || src->path[src_len - 1] == '/') &&
84 (!dst_len || dst->path[dst_len - 1] == '/');
87 struct diff_score {
88 int src; /* index in rename_src */
89 int dst; /* index in rename_dst */
90 unsigned short score;
91 short name_score;
94 struct inexact_prefetch_options {
95 struct repository *repo;
96 int skip_unmodified;
98 static void inexact_prefetch(void *prefetch_options)
100 struct inexact_prefetch_options *options = prefetch_options;
101 int i;
102 struct oid_array to_fetch = OID_ARRAY_INIT;
104 for (i = 0; i < rename_dst_nr; i++) {
105 if (rename_dst[i].p->renamed_pair)
107 * The loop in diffcore_rename() will not need these
108 * blobs, so skip prefetching.
110 continue; /* already found exact match */
111 diff_add_if_missing(options->repo, &to_fetch,
112 rename_dst[i].p->two);
114 for (i = 0; i < rename_src_nr; i++) {
115 if (options->skip_unmodified &&
116 diff_unmodified_pair(rename_src[i].p))
118 * The loop in diffcore_rename() will not need these
119 * blobs, so skip prefetching.
121 continue;
122 diff_add_if_missing(options->repo, &to_fetch,
123 rename_src[i].p->one);
125 promisor_remote_get_direct(options->repo, to_fetch.oid, to_fetch.nr);
126 oid_array_clear(&to_fetch);
129 static int estimate_similarity(struct repository *r,
130 struct diff_filespec *src,
131 struct diff_filespec *dst,
132 int minimum_score,
133 struct diff_populate_filespec_options *dpf_opt)
135 /* src points at a file that existed in the original tree (or
136 * optionally a file in the destination tree) and dst points
137 * at a newly created file. They may be quite similar, in which
138 * case we want to say src is renamed to dst or src is copied into
139 * dst, and then some edit has been applied to dst.
141 * Compare them and return how similar they are, representing
142 * the score as an integer between 0 and MAX_SCORE.
144 * When there is an exact match, it is considered a better
145 * match than anything else; the destination does not even
146 * call into this function in that case.
148 unsigned long max_size, delta_size, base_size, src_copied, literal_added;
149 int score;
151 /* We deal only with regular files. Symlink renames are handled
152 * only when they are exact matches --- in other words, no edits
153 * after renaming.
155 if (!S_ISREG(src->mode) || !S_ISREG(dst->mode))
156 return 0;
159 * Need to check that source and destination sizes are
160 * filled in before comparing them.
162 * If we already have "cnt_data" filled in, we know it's
163 * all good (avoid checking the size for zero, as that
164 * is a possible size - we really should have a flag to
165 * say whether the size is valid or not!)
167 dpf_opt->check_size_only = 1;
169 if (!src->cnt_data &&
170 diff_populate_filespec(r, src, dpf_opt))
171 return 0;
172 if (!dst->cnt_data &&
173 diff_populate_filespec(r, dst, dpf_opt))
174 return 0;
176 max_size = ((src->size > dst->size) ? src->size : dst->size);
177 base_size = ((src->size < dst->size) ? src->size : dst->size);
178 delta_size = max_size - base_size;
180 /* We would not consider edits that change the file size so
181 * drastically. delta_size must be smaller than
182 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
184 * Note that base_size == 0 case is handled here already
185 * and the final score computation below would not have a
186 * divide-by-zero issue.
188 if (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)
189 return 0;
191 dpf_opt->check_size_only = 0;
193 if (!src->cnt_data && diff_populate_filespec(r, src, dpf_opt))
194 return 0;
195 if (!dst->cnt_data && diff_populate_filespec(r, dst, dpf_opt))
196 return 0;
198 if (diffcore_count_changes(r, src, dst,
199 &src->cnt_data, &dst->cnt_data,
200 &src_copied, &literal_added))
201 return 0;
203 /* How similar are they?
204 * what percentage of material in dst are from source?
206 if (!dst->size)
207 score = 0; /* should not happen */
208 else
209 score = (int)(src_copied * MAX_SCORE / max_size);
210 return score;
213 static void record_rename_pair(int dst_index, int src_index, int score)
215 struct diff_filepair *src = rename_src[src_index].p;
216 struct diff_filepair *dst = rename_dst[dst_index].p;
218 if (dst->renamed_pair)
219 die("internal error: dst already matched.");
221 src->one->rename_used++;
222 src->one->count++;
224 rename_dst[dst_index].filespec_to_free = dst->one;
225 rename_dst[dst_index].is_rename = 1;
227 dst->one = src->one;
228 dst->renamed_pair = 1;
229 if (!strcmp(dst->one->path, dst->two->path))
230 dst->score = rename_src[src_index].score;
231 else
232 dst->score = score;
236 * We sort the rename similarity matrix with the score, in descending
237 * order (the most similar first).
239 static int score_compare(const void *a_, const void *b_)
241 const struct diff_score *a = a_, *b = b_;
243 /* sink the unused ones to the bottom */
244 if (a->dst < 0)
245 return (0 <= b->dst);
246 else if (b->dst < 0)
247 return -1;
249 if (a->score == b->score)
250 return b->name_score - a->name_score;
252 return b->score - a->score;
255 struct file_similarity {
256 struct hashmap_entry entry;
257 int index;
258 struct diff_filespec *filespec;
261 static unsigned int hash_filespec(struct repository *r,
262 struct diff_filespec *filespec)
264 if (!filespec->oid_valid) {
265 if (diff_populate_filespec(r, filespec, NULL))
266 return 0;
267 hash_object_file(r->hash_algo, filespec->data, filespec->size,
268 OBJ_BLOB, &filespec->oid);
270 return oidhash(&filespec->oid);
273 static int find_identical_files(struct hashmap *srcs,
274 int dst_index,
275 struct diff_options *options)
277 int renames = 0;
278 struct diff_filespec *target = rename_dst[dst_index].p->two;
279 struct file_similarity *p, *best = NULL;
280 int i = 100, best_score = -1;
281 unsigned int hash = hash_filespec(options->repo, target);
284 * Find the best source match for specified destination.
286 p = hashmap_get_entry_from_hash(srcs, hash, NULL,
287 struct file_similarity, entry);
288 hashmap_for_each_entry_from(srcs, p, entry) {
289 int score;
290 struct diff_filespec *source = p->filespec;
292 /* False hash collision? */
293 if (!oideq(&source->oid, &target->oid))
294 continue;
295 /* Non-regular files? If so, the modes must match! */
296 if (!S_ISREG(source->mode) || !S_ISREG(target->mode)) {
297 if (source->mode != target->mode)
298 continue;
300 /* Give higher scores to sources that haven't been used already */
301 score = !source->rename_used;
302 if (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)
303 continue;
304 score += basename_same(source, target);
305 if (score > best_score) {
306 best = p;
307 best_score = score;
308 if (score == 2)
309 break;
312 /* Too many identical alternatives? Pick one */
313 if (!--i)
314 break;
316 if (best) {
317 record_rename_pair(dst_index, best->index, MAX_SCORE);
318 renames++;
320 return renames;
323 static void insert_file_table(struct repository *r,
324 struct mem_pool *pool,
325 struct hashmap *table, int index,
326 struct diff_filespec *filespec)
328 struct file_similarity *entry = mem_pool_alloc(pool, sizeof(*entry));
330 entry->index = index;
331 entry->filespec = filespec;
333 hashmap_entry_init(&entry->entry, hash_filespec(r, filespec));
334 hashmap_add(table, &entry->entry);
338 * Find exact renames first.
340 * The first round matches up the up-to-date entries,
341 * and then during the second round we try to match
342 * cache-dirty entries as well.
344 static int find_exact_renames(struct diff_options *options,
345 struct mem_pool *pool)
347 int i, renames = 0;
348 struct hashmap file_table;
350 /* Add all sources to the hash table in reverse order, because
351 * later on they will be retrieved in LIFO order.
353 hashmap_init(&file_table, NULL, NULL, rename_src_nr);
354 for (i = rename_src_nr-1; i >= 0; i--)
355 insert_file_table(options->repo, pool,
356 &file_table, i,
357 rename_src[i].p->one);
359 /* Walk the destinations and find best source match */
360 for (i = 0; i < rename_dst_nr; i++)
361 renames += find_identical_files(&file_table, i, options);
363 /* Free the hash data structure (entries will be freed with the pool) */
364 hashmap_clear(&file_table);
366 return renames;
369 struct dir_rename_info {
370 struct strintmap idx_map;
371 struct strmap dir_rename_guess;
372 struct strmap *dir_rename_count;
373 struct strintmap *relevant_source_dirs;
374 unsigned setup;
377 static char *get_dirname(const char *filename)
379 char *slash = strrchr(filename, '/');
380 return slash ? xstrndup(filename, slash - filename) : xstrdup("");
383 static void dirname_munge(char *filename)
385 char *slash = strrchr(filename, '/');
386 if (!slash)
387 slash = filename;
388 *slash = '\0';
391 static const char *get_highest_rename_path(struct strintmap *counts)
393 int highest_count = 0;
394 const char *highest_destination_dir = NULL;
395 struct hashmap_iter iter;
396 struct strmap_entry *entry;
398 strintmap_for_each_entry(counts, &iter, entry) {
399 const char *destination_dir = entry->key;
400 intptr_t count = (intptr_t)entry->value;
401 if (count > highest_count) {
402 highest_count = count;
403 highest_destination_dir = destination_dir;
406 return highest_destination_dir;
409 static char *UNKNOWN_DIR = "/"; /* placeholder -- short, illegal directory */
411 static int dir_rename_already_determinable(struct strintmap *counts)
413 struct hashmap_iter iter;
414 struct strmap_entry *entry;
415 int first = 0, second = 0, unknown = 0;
416 strintmap_for_each_entry(counts, &iter, entry) {
417 const char *destination_dir = entry->key;
418 intptr_t count = (intptr_t)entry->value;
419 if (!strcmp(destination_dir, UNKNOWN_DIR)) {
420 unknown = count;
421 } else if (count >= first) {
422 second = first;
423 first = count;
424 } else if (count >= second) {
425 second = count;
428 return first > second + unknown;
431 static void increment_count(struct dir_rename_info *info,
432 char *old_dir,
433 char *new_dir)
435 struct strintmap *counts;
436 struct strmap_entry *e;
438 /* Get the {new_dirs -> counts} mapping using old_dir */
439 e = strmap_get_entry(info->dir_rename_count, old_dir);
440 if (e) {
441 counts = e->value;
442 } else {
443 counts = xmalloc(sizeof(*counts));
444 strintmap_init_with_options(counts, 0, NULL, 1);
445 strmap_put(info->dir_rename_count, old_dir, counts);
448 /* Increment the count for new_dir */
449 strintmap_incr(counts, new_dir, 1);
452 static void update_dir_rename_counts(struct dir_rename_info *info,
453 struct strintmap *dirs_removed,
454 const char *oldname,
455 const char *newname)
457 char *old_dir;
458 char *new_dir;
459 const char new_dir_first_char = newname[0];
460 int first_time_in_loop = 1;
462 if (!info->setup)
464 * info->setup is 0 here in two cases: (1) all auxiliary
465 * vars (like dirs_removed) were NULL so
466 * initialize_dir_rename_info() returned early, or (2)
467 * either break detection or copy detection are active so
468 * that we never called initialize_dir_rename_info(). In
469 * the former case, we don't have enough info to know if
470 * directories were renamed (because dirs_removed lets us
471 * know about a necessary prerequisite, namely if they were
472 * removed), and in the latter, we don't care about
473 * directory renames or find_basename_matches.
475 * This matters because both basename and inexact matching
476 * will also call update_dir_rename_counts(). In either of
477 * the above two cases info->dir_rename_counts will not
478 * have been properly initialized which prevents us from
479 * updating it, but in these two cases we don't care about
480 * dir_rename_counts anyway, so we can just exit early.
482 return;
485 old_dir = xstrdup(oldname);
486 new_dir = xstrdup(newname);
488 while (1) {
489 int drd_flag = NOT_RELEVANT;
491 /* Get old_dir, skip if its directory isn't relevant. */
492 dirname_munge(old_dir);
493 if (info->relevant_source_dirs &&
494 !strintmap_contains(info->relevant_source_dirs, old_dir))
495 break;
497 /* Get new_dir */
498 dirname_munge(new_dir);
501 * When renaming
502 * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"
503 * then this suggests that both
504 * a/b/c/d/e/ => a/b/some/thing/else/e/
505 * a/b/c/d/ => a/b/some/thing/else/
506 * so we want to increment counters for both. We do NOT,
507 * however, also want to suggest that there was the following
508 * rename:
509 * a/b/c/ => a/b/some/thing/
510 * so we need to quit at that point.
512 * Note the when first_time_in_loop, we only strip off the
513 * basename, and we don't care if that's different.
515 if (!first_time_in_loop) {
516 char *old_sub_dir = strchr(old_dir, '\0')+1;
517 char *new_sub_dir = strchr(new_dir, '\0')+1;
518 if (!*new_dir) {
520 * Special case when renaming to root directory,
521 * i.e. when new_dir == "". In this case, we had
522 * something like
523 * a/b/subdir => subdir
524 * and so dirname_munge() sets things up so that
525 * old_dir = "a/b\0subdir\0"
526 * new_dir = "\0ubdir\0"
527 * We didn't have a '/' to overwrite a '\0' onto
528 * in new_dir, so we have to compare differently.
530 if (new_dir_first_char != old_sub_dir[0] ||
531 strcmp(old_sub_dir+1, new_sub_dir))
532 break;
533 } else {
534 if (strcmp(old_sub_dir, new_sub_dir))
535 break;
540 * Above we suggested that we'd keep recording renames for
541 * all ancestor directories where the trailing directories
542 * matched, i.e. for
543 * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"
544 * we'd increment rename counts for each of
545 * a/b/c/d/e/ => a/b/some/thing/else/e/
546 * a/b/c/d/ => a/b/some/thing/else/
547 * However, we only need the rename counts for directories
548 * in dirs_removed whose value is RELEVANT_FOR_SELF.
549 * However, we add one special case of also recording it for
550 * first_time_in_loop because find_basename_matches() can
551 * use that as a hint to find a good pairing.
553 if (dirs_removed)
554 drd_flag = strintmap_get(dirs_removed, old_dir);
555 if (drd_flag == RELEVANT_FOR_SELF || first_time_in_loop)
556 increment_count(info, old_dir, new_dir);
558 first_time_in_loop = 0;
559 if (drd_flag == NOT_RELEVANT)
560 break;
561 /* If we hit toplevel directory ("") for old or new dir, quit */
562 if (!*old_dir || !*new_dir)
563 break;
566 /* Free resources we don't need anymore */
567 free(old_dir);
568 free(new_dir);
571 static void initialize_dir_rename_info(struct dir_rename_info *info,
572 struct strintmap *relevant_sources,
573 struct strintmap *dirs_removed,
574 struct strmap *dir_rename_count,
575 struct strmap *cached_pairs)
577 struct hashmap_iter iter;
578 struct strmap_entry *entry;
579 int i;
581 if (!dirs_removed && !relevant_sources) {
582 info->setup = 0;
583 return;
585 info->setup = 1;
587 info->dir_rename_count = dir_rename_count;
588 if (!info->dir_rename_count) {
589 info->dir_rename_count = xmalloc(sizeof(*dir_rename_count));
590 strmap_init(info->dir_rename_count);
592 strintmap_init_with_options(&info->idx_map, -1, NULL, 0);
593 strmap_init_with_options(&info->dir_rename_guess, NULL, 0);
595 /* Setup info->relevant_source_dirs */
596 info->relevant_source_dirs = NULL;
597 if (dirs_removed || !relevant_sources) {
598 info->relevant_source_dirs = dirs_removed; /* might be NULL */
599 } else {
600 info->relevant_source_dirs = xmalloc(sizeof(struct strintmap));
601 strintmap_init(info->relevant_source_dirs, 0 /* unused */);
602 strintmap_for_each_entry(relevant_sources, &iter, entry) {
603 char *dirname = get_dirname(entry->key);
604 if (!dirs_removed ||
605 strintmap_contains(dirs_removed, dirname))
606 strintmap_set(info->relevant_source_dirs,
607 dirname, 0 /* value irrelevant */);
608 free(dirname);
613 * Loop setting up both info->idx_map, and doing setup of
614 * info->dir_rename_count.
616 for (i = 0; i < rename_dst_nr; ++i) {
618 * For non-renamed files, make idx_map contain mapping of
619 * filename -> index (index within rename_dst, that is)
621 if (!rename_dst[i].is_rename) {
622 char *filename = rename_dst[i].p->two->path;
623 strintmap_set(&info->idx_map, filename, i);
624 continue;
628 * For everything else (i.e. renamed files), make
629 * dir_rename_count contain a map of a map:
630 * old_directory -> {new_directory -> count}
631 * In other words, for every pair look at the directories for
632 * the old filename and the new filename and count how many
633 * times that pairing occurs.
635 update_dir_rename_counts(info, dirs_removed,
636 rename_dst[i].p->one->path,
637 rename_dst[i].p->two->path);
640 /* Add cached_pairs to counts */
641 strmap_for_each_entry(cached_pairs, &iter, entry) {
642 const char *old_name = entry->key;
643 const char *new_name = entry->value;
644 if (!new_name)
645 /* known delete; ignore it */
646 continue;
648 update_dir_rename_counts(info, dirs_removed, old_name, new_name);
652 * Now we collapse
653 * dir_rename_count: old_directory -> {new_directory -> count}
654 * down to
655 * dir_rename_guess: old_directory -> best_new_directory
656 * where best_new_directory is the one with the highest count.
658 strmap_for_each_entry(info->dir_rename_count, &iter, entry) {
659 /* entry->key is source_dir */
660 struct strintmap *counts = entry->value;
661 char *best_newdir;
663 best_newdir = xstrdup(get_highest_rename_path(counts));
664 strmap_put(&info->dir_rename_guess, entry->key,
665 best_newdir);
669 void partial_clear_dir_rename_count(struct strmap *dir_rename_count)
671 struct hashmap_iter iter;
672 struct strmap_entry *entry;
674 strmap_for_each_entry(dir_rename_count, &iter, entry) {
675 struct strintmap *counts = entry->value;
676 strintmap_clear(counts);
678 strmap_partial_clear(dir_rename_count, 1);
681 static void cleanup_dir_rename_info(struct dir_rename_info *info,
682 struct strintmap *dirs_removed,
683 int keep_dir_rename_count)
685 struct hashmap_iter iter;
686 struct strmap_entry *entry;
687 struct string_list to_remove = STRING_LIST_INIT_NODUP;
688 int i;
690 if (!info->setup)
691 return;
693 /* idx_map */
694 strintmap_clear(&info->idx_map);
696 /* dir_rename_guess */
697 strmap_clear(&info->dir_rename_guess, 1);
699 /* relevant_source_dirs */
700 if (info->relevant_source_dirs &&
701 info->relevant_source_dirs != dirs_removed) {
702 strintmap_clear(info->relevant_source_dirs);
703 FREE_AND_NULL(info->relevant_source_dirs);
706 /* dir_rename_count */
707 if (!keep_dir_rename_count) {
708 partial_clear_dir_rename_count(info->dir_rename_count);
709 strmap_clear(info->dir_rename_count, 1);
710 FREE_AND_NULL(info->dir_rename_count);
711 return;
715 * Although dir_rename_count was passed in
716 * diffcore_rename_extended() and we want to keep it around and
717 * return it to that caller, we first want to remove any counts in
718 * the maps associated with UNKNOWN_DIR entries and any data
719 * associated with directories that weren't renamed.
721 strmap_for_each_entry(info->dir_rename_count, &iter, entry) {
722 const char *source_dir = entry->key;
723 struct strintmap *counts = entry->value;
725 if (!strintmap_get(dirs_removed, source_dir)) {
726 string_list_append(&to_remove, source_dir);
727 strintmap_clear(counts);
728 continue;
731 if (strintmap_contains(counts, UNKNOWN_DIR))
732 strintmap_remove(counts, UNKNOWN_DIR);
734 for (i = 0; i < to_remove.nr; ++i)
735 strmap_remove(info->dir_rename_count,
736 to_remove.items[i].string, 1);
737 string_list_clear(&to_remove, 0);
740 static const char *get_basename(const char *filename)
743 * gitbasename() has to worry about special drives, multiple
744 * directory separator characters, trailing slashes, NULL or
745 * empty strings, etc. We only work on filenames as stored in
746 * git, and thus get to ignore all those complications.
748 const char *base = strrchr(filename, '/');
749 return base ? base + 1 : filename;
752 static int idx_possible_rename(char *filename, struct dir_rename_info *info)
755 * Our comparison of files with the same basename (see
756 * find_basename_matches() below), is only helpful when after exact
757 * rename detection we have exactly one file with a given basename
758 * among the rename sources and also only exactly one file with
759 * that basename among the rename destinations. When we have
760 * multiple files with the same basename in either set, we do not
761 * know which to compare against. However, there are some
762 * filenames that occur in large numbers (particularly
763 * build-related filenames such as 'Makefile', '.gitignore', or
764 * 'build.gradle' that potentially exist within every single
765 * subdirectory), and for performance we want to be able to quickly
766 * find renames for these files too.
768 * The reason basename comparisons are a useful heuristic was that it
769 * is common for people to move files across directories while keeping
770 * their filename the same. If we had a way of determining or even
771 * making a good educated guess about which directory these non-unique
772 * basename files had moved the file to, we could check it.
773 * Luckily...
775 * When an entire directory is in fact renamed, we have two factors
776 * helping us out:
777 * (a) the original directory disappeared giving us a hint
778 * about when we can apply an extra heuristic.
779 * (a) we often have several files within that directory and
780 * subdirectories that are renamed without changes
781 * So, rules for a heuristic:
782 * (0) If there basename matches are non-unique (the condition under
783 * which this function is called) AND
784 * (1) the directory in which the file was found has disappeared
785 * (i.e. dirs_removed is non-NULL and has a relevant entry) THEN
786 * (2) use exact renames of files within the directory to determine
787 * where the directory is likely to have been renamed to. IF
788 * there is at least one exact rename from within that
789 * directory, we can proceed.
790 * (3) If there are multiple places the directory could have been
791 * renamed to based on exact renames, ignore all but one of them.
792 * Just use the destination with the most renames going to it.
793 * (4) Check if applying that directory rename to the original file
794 * would result in a destination filename that is in the
795 * potential rename set. If so, return the index of the
796 * destination file (the index within rename_dst).
797 * (5) Compare the original file and returned destination for
798 * similarity, and if they are sufficiently similar, record the
799 * rename.
801 * This function, idx_possible_rename(), is only responsible for (4).
802 * The conditions/steps in (1)-(3) are handled via setting up
803 * dir_rename_count and dir_rename_guess in
804 * initialize_dir_rename_info(). Steps (0) and (5) are handled by
805 * the caller of this function.
807 char *old_dir, *new_dir;
808 struct strbuf new_path = STRBUF_INIT;
809 int idx;
811 if (!info->setup)
812 return -1;
814 old_dir = get_dirname(filename);
815 new_dir = strmap_get(&info->dir_rename_guess, old_dir);
816 free(old_dir);
817 if (!new_dir)
818 return -1;
820 strbuf_addstr(&new_path, new_dir);
821 strbuf_addch(&new_path, '/');
822 strbuf_addstr(&new_path, get_basename(filename));
824 idx = strintmap_get(&info->idx_map, new_path.buf);
825 strbuf_release(&new_path);
826 return idx;
829 struct basename_prefetch_options {
830 struct repository *repo;
831 struct strintmap *relevant_sources;
832 struct strintmap *sources;
833 struct strintmap *dests;
834 struct dir_rename_info *info;
836 static void basename_prefetch(void *prefetch_options)
838 struct basename_prefetch_options *options = prefetch_options;
839 struct strintmap *relevant_sources = options->relevant_sources;
840 struct strintmap *sources = options->sources;
841 struct strintmap *dests = options->dests;
842 struct dir_rename_info *info = options->info;
843 int i;
844 struct oid_array to_fetch = OID_ARRAY_INIT;
847 * TODO: The following loops mirror the code/logic from
848 * find_basename_matches(), though not quite exactly. Maybe
849 * abstract the iteration logic out somehow?
851 for (i = 0; i < rename_src_nr; ++i) {
852 char *filename = rename_src[i].p->one->path;
853 const char *base = NULL;
854 intptr_t src_index;
855 intptr_t dst_index;
857 /* Skip irrelevant sources */
858 if (relevant_sources &&
859 !strintmap_contains(relevant_sources, filename))
860 continue;
863 * If the basename is unique among remaining sources, then
864 * src_index will equal 'i' and we can attempt to match it
865 * to a unique basename in the destinations. Otherwise,
866 * use directory rename heuristics, if possible.
868 base = get_basename(filename);
869 src_index = strintmap_get(sources, base);
870 assert(src_index == -1 || src_index == i);
872 if (strintmap_contains(dests, base)) {
873 struct diff_filespec *one, *two;
875 /* Find a matching destination, if possible */
876 dst_index = strintmap_get(dests, base);
877 if (src_index == -1 || dst_index == -1) {
878 src_index = i;
879 dst_index = idx_possible_rename(filename, info);
881 if (dst_index == -1)
882 continue;
884 /* Ignore this dest if already used in a rename */
885 if (rename_dst[dst_index].is_rename)
886 continue; /* already used previously */
888 one = rename_src[src_index].p->one;
889 two = rename_dst[dst_index].p->two;
891 /* Add the pairs */
892 diff_add_if_missing(options->repo, &to_fetch, two);
893 diff_add_if_missing(options->repo, &to_fetch, one);
897 promisor_remote_get_direct(options->repo, to_fetch.oid, to_fetch.nr);
898 oid_array_clear(&to_fetch);
901 static int find_basename_matches(struct diff_options *options,
902 int minimum_score,
903 struct dir_rename_info *info,
904 struct strintmap *relevant_sources,
905 struct strintmap *dirs_removed)
908 * When I checked in early 2020, over 76% of file renames in linux
909 * just moved files to a different directory but kept the same
910 * basename. gcc did that with over 64% of renames, gecko did it
911 * with over 79%, and WebKit did it with over 89%.
913 * Therefore we can bypass the normal exhaustive NxM matrix
914 * comparison of similarities between all potential rename sources
915 * and destinations by instead using file basename as a hint (i.e.
916 * the portion of the filename after the last '/'), checking for
917 * similarity between files with the same basename, and if we find
918 * a pair that are sufficiently similar, record the rename pair and
919 * exclude those two from the NxM matrix.
921 * This *might* cause us to find a less than optimal pairing (if
922 * there is another file that we are even more similar to but has a
923 * different basename). Given the huge performance advantage
924 * basename matching provides, and given the frequency with which
925 * people use the same basename in real world projects, that's a
926 * trade-off we are willing to accept when doing just rename
927 * detection.
929 * If someone wants copy detection that implies they are willing to
930 * spend more cycles to find similarities between files, so it may
931 * be less likely that this heuristic is wanted. If someone is
932 * doing break detection, that means they do not want filename
933 * similarity to imply any form of content similiarity, and thus
934 * this heuristic would definitely be incompatible.
937 int i, renames = 0;
938 struct strintmap sources;
939 struct strintmap dests;
940 struct diff_populate_filespec_options dpf_options = {
941 .check_binary = 0,
942 .missing_object_cb = NULL,
943 .missing_object_data = NULL
945 struct basename_prefetch_options prefetch_options = {
946 .repo = options->repo,
947 .relevant_sources = relevant_sources,
948 .sources = &sources,
949 .dests = &dests,
950 .info = info
954 * Create maps of basename -> fullname(s) for remaining sources and
955 * dests.
957 strintmap_init_with_options(&sources, -1, NULL, 0);
958 strintmap_init_with_options(&dests, -1, NULL, 0);
959 for (i = 0; i < rename_src_nr; ++i) {
960 char *filename = rename_src[i].p->one->path;
961 const char *base;
963 /* exact renames removed in remove_unneeded_paths_from_src() */
964 assert(!rename_src[i].p->one->rename_used);
966 /* Record index within rename_src (i) if basename is unique */
967 base = get_basename(filename);
968 if (strintmap_contains(&sources, base))
969 strintmap_set(&sources, base, -1);
970 else
971 strintmap_set(&sources, base, i);
973 for (i = 0; i < rename_dst_nr; ++i) {
974 char *filename = rename_dst[i].p->two->path;
975 const char *base;
977 if (rename_dst[i].is_rename)
978 continue; /* involved in exact match already. */
980 /* Record index within rename_dst (i) if basename is unique */
981 base = get_basename(filename);
982 if (strintmap_contains(&dests, base))
983 strintmap_set(&dests, base, -1);
984 else
985 strintmap_set(&dests, base, i);
988 if (options->repo == the_repository && repo_has_promisor_remote(the_repository)) {
989 dpf_options.missing_object_cb = basename_prefetch;
990 dpf_options.missing_object_data = &prefetch_options;
993 /* Now look for basename matchups and do similarity estimation */
994 for (i = 0; i < rename_src_nr; ++i) {
995 char *filename = rename_src[i].p->one->path;
996 const char *base = NULL;
997 intptr_t src_index;
998 intptr_t dst_index;
1000 /* Skip irrelevant sources */
1001 if (relevant_sources &&
1002 !strintmap_contains(relevant_sources, filename))
1003 continue;
1006 * If the basename is unique among remaining sources, then
1007 * src_index will equal 'i' and we can attempt to match it
1008 * to a unique basename in the destinations. Otherwise,
1009 * use directory rename heuristics, if possible.
1011 base = get_basename(filename);
1012 src_index = strintmap_get(&sources, base);
1013 assert(src_index == -1 || src_index == i);
1015 if (strintmap_contains(&dests, base)) {
1016 struct diff_filespec *one, *two;
1017 int score;
1019 /* Find a matching destination, if possible */
1020 dst_index = strintmap_get(&dests, base);
1021 if (src_index == -1 || dst_index == -1) {
1022 src_index = i;
1023 dst_index = idx_possible_rename(filename, info);
1025 if (dst_index == -1)
1026 continue;
1028 /* Ignore this dest if already used in a rename */
1029 if (rename_dst[dst_index].is_rename)
1030 continue; /* already used previously */
1032 /* Estimate the similarity */
1033 one = rename_src[src_index].p->one;
1034 two = rename_dst[dst_index].p->two;
1035 score = estimate_similarity(options->repo, one, two,
1036 minimum_score, &dpf_options);
1038 /* If sufficiently similar, record as rename pair */
1039 if (score < minimum_score)
1040 continue;
1041 record_rename_pair(dst_index, src_index, score);
1042 renames++;
1043 update_dir_rename_counts(info, dirs_removed,
1044 one->path, two->path);
1047 * Found a rename so don't need text anymore; if we
1048 * didn't find a rename, the filespec_blob would get
1049 * re-used when doing the matrix of comparisons.
1051 diff_free_filespec_blob(one);
1052 diff_free_filespec_blob(two);
1056 strintmap_clear(&sources);
1057 strintmap_clear(&dests);
1059 return renames;
1062 #define NUM_CANDIDATE_PER_DST 4
1063 static void record_if_better(struct diff_score m[], struct diff_score *o)
1065 int i, worst;
1067 /* find the worst one */
1068 worst = 0;
1069 for (i = 1; i < NUM_CANDIDATE_PER_DST; i++)
1070 if (score_compare(&m[i], &m[worst]) > 0)
1071 worst = i;
1073 /* is it better than the worst one? */
1074 if (score_compare(&m[worst], o) > 0)
1075 m[worst] = *o;
1079 * Returns:
1080 * 0 if we are under the limit;
1081 * 1 if we need to disable inexact rename detection;
1082 * 2 if we would be under the limit if we were given -C instead of -C -C.
1084 static int too_many_rename_candidates(int num_destinations, int num_sources,
1085 struct diff_options *options)
1087 int rename_limit = options->rename_limit;
1088 int i, limited_sources;
1090 options->needed_rename_limit = 0;
1093 * This basically does a test for the rename matrix not
1094 * growing larger than a "rename_limit" square matrix, ie:
1096 * num_destinations * num_sources > rename_limit * rename_limit
1098 * We use st_mult() to check overflow conditions; in the
1099 * exceptional circumstance that size_t isn't large enough to hold
1100 * the multiplication, the system won't be able to allocate enough
1101 * memory for the matrix anyway.
1103 if (rename_limit <= 0)
1104 return 0; /* treat as unlimited */
1105 if (st_mult(num_destinations, num_sources)
1106 <= st_mult(rename_limit, rename_limit))
1107 return 0;
1109 options->needed_rename_limit =
1110 num_sources > num_destinations ? num_sources : num_destinations;
1112 /* Are we running under -C -C? */
1113 if (!options->flags.find_copies_harder)
1114 return 1;
1116 /* Would we bust the limit if we were running under -C? */
1117 for (limited_sources = i = 0; i < num_sources; i++) {
1118 if (diff_unmodified_pair(rename_src[i].p))
1119 continue;
1120 limited_sources++;
1122 if (st_mult(num_destinations, limited_sources)
1123 <= st_mult(rename_limit, rename_limit))
1124 return 2;
1125 return 1;
1128 static int find_renames(struct diff_score *mx,
1129 int dst_cnt,
1130 int minimum_score,
1131 int copies,
1132 struct dir_rename_info *info,
1133 struct strintmap *dirs_removed)
1135 int count = 0, i;
1137 for (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {
1138 struct diff_rename_dst *dst;
1140 if ((mx[i].dst < 0) ||
1141 (mx[i].score < minimum_score))
1142 break; /* there is no more usable pair. */
1143 dst = &rename_dst[mx[i].dst];
1144 if (dst->is_rename)
1145 continue; /* already done, either exact or fuzzy. */
1146 if (!copies && rename_src[mx[i].src].p->one->rename_used)
1147 continue;
1148 record_rename_pair(mx[i].dst, mx[i].src, mx[i].score);
1149 count++;
1150 update_dir_rename_counts(info, dirs_removed,
1151 rename_src[mx[i].src].p->one->path,
1152 rename_dst[mx[i].dst].p->two->path);
1154 return count;
1157 static void remove_unneeded_paths_from_src(int detecting_copies,
1158 struct strintmap *interesting)
1160 int i, new_num_src;
1162 if (detecting_copies && !interesting)
1163 return; /* nothing to remove */
1164 if (break_idx)
1165 return; /* culling incompatible with break detection */
1168 * Note on reasons why we cull unneeded sources but not destinations:
1169 * 1) Pairings are stored in rename_dst (not rename_src), which we
1170 * need to keep around. So, we just can't cull rename_dst even
1171 * if we wanted to. But doing so wouldn't help because...
1173 * 2) There is a matrix pairwise comparison that follows the
1174 * "Performing inexact rename detection" progress message.
1175 * Iterating over the destinations is done in the outer loop,
1176 * hence we only iterate over each of those once and we can
1177 * easily skip the outer loop early if the destination isn't
1178 * relevant. That's only one check per destination path to
1179 * skip.
1181 * By contrast, the sources are iterated in the inner loop; if
1182 * we check whether a source can be skipped, then we'll be
1183 * checking it N separate times, once for each destination.
1184 * We don't want to have to iterate over known-not-needed
1185 * sources N times each, so avoid that by removing the sources
1186 * from rename_src here.
1188 for (i = 0, new_num_src = 0; i < rename_src_nr; i++) {
1189 struct diff_filespec *one = rename_src[i].p->one;
1192 * renames are stored in rename_dst, so if a rename has
1193 * already been detected using this source, we can just
1194 * remove the source knowing rename_dst has its info.
1196 if (!detecting_copies && one->rename_used)
1197 continue;
1199 /* If we don't care about the source path, skip it */
1200 if (interesting && !strintmap_contains(interesting, one->path))
1201 continue;
1203 if (new_num_src < i)
1204 memcpy(&rename_src[new_num_src], &rename_src[i],
1205 sizeof(struct diff_rename_src));
1206 new_num_src++;
1209 rename_src_nr = new_num_src;
1212 static void handle_early_known_dir_renames(struct dir_rename_info *info,
1213 struct strintmap *relevant_sources,
1214 struct strintmap *dirs_removed)
1217 * Directory renames are determined via an aggregate of all renames
1218 * under them and using a "majority wins" rule. The fact that
1219 * "majority wins", though, means we don't need all the renames
1220 * under the given directory, we only need enough to ensure we have
1221 * a majority.
1224 int i, new_num_src;
1225 struct hashmap_iter iter;
1226 struct strmap_entry *entry;
1228 if (!dirs_removed || !relevant_sources)
1229 return; /* nothing to cull */
1230 if (break_idx)
1231 return; /* culling incompatbile with break detection */
1234 * Supplement dir_rename_count with number of potential renames,
1235 * marking all potential rename sources as mapping to UNKNOWN_DIR.
1237 for (i = 0; i < rename_src_nr; i++) {
1238 char *old_dir;
1239 struct diff_filespec *one = rename_src[i].p->one;
1242 * sources that are part of a rename will have already been
1243 * removed by a prior call to remove_unneeded_paths_from_src()
1245 assert(!one->rename_used);
1247 old_dir = get_dirname(one->path);
1248 while (*old_dir != '\0' &&
1249 NOT_RELEVANT != strintmap_get(dirs_removed, old_dir)) {
1250 char *freeme = old_dir;
1252 increment_count(info, old_dir, UNKNOWN_DIR);
1253 old_dir = get_dirname(old_dir);
1255 /* Free resources we don't need anymore */
1256 free(freeme);
1259 * old_dir and new_dir free'd in increment_count, but
1260 * get_dirname() gives us a new pointer we need to free for
1261 * old_dir. Also, if the loop runs 0 times we need old_dir
1262 * to be freed.
1264 free(old_dir);
1268 * For any directory which we need a potential rename detected for
1269 * (i.e. those marked as RELEVANT_FOR_SELF in dirs_removed), check
1270 * whether we have enough renames to satisfy the "majority rules"
1271 * requirement such that detecting any more renames of files under
1272 * it won't change the result. For any such directory, mark that
1273 * we no longer need to detect a rename for it. However, since we
1274 * might need to still detect renames for an ancestor of that
1275 * directory, use RELEVANT_FOR_ANCESTOR.
1277 strmap_for_each_entry(info->dir_rename_count, &iter, entry) {
1278 /* entry->key is source_dir */
1279 struct strintmap *counts = entry->value;
1281 if (strintmap_get(dirs_removed, entry->key) ==
1282 RELEVANT_FOR_SELF &&
1283 dir_rename_already_determinable(counts)) {
1284 strintmap_set(dirs_removed, entry->key,
1285 RELEVANT_FOR_ANCESTOR);
1289 for (i = 0, new_num_src = 0; i < rename_src_nr; i++) {
1290 struct diff_filespec *one = rename_src[i].p->one;
1291 int val;
1293 val = strintmap_get(relevant_sources, one->path);
1296 * sources that were not found in relevant_sources should
1297 * have already been removed by a prior call to
1298 * remove_unneeded_paths_from_src()
1300 assert(val != -1);
1302 if (val == RELEVANT_LOCATION) {
1303 int removable = 1;
1304 char *dir = get_dirname(one->path);
1305 while (1) {
1306 char *freeme = dir;
1307 int res = strintmap_get(dirs_removed, dir);
1309 /* Quit if not found or irrelevant */
1310 if (res == NOT_RELEVANT)
1311 break;
1312 /* If RELEVANT_FOR_SELF, can't remove */
1313 if (res == RELEVANT_FOR_SELF) {
1314 removable = 0;
1315 break;
1317 /* Else continue searching upwards */
1318 assert(res == RELEVANT_FOR_ANCESTOR);
1319 dir = get_dirname(dir);
1320 free(freeme);
1322 free(dir);
1323 if (removable) {
1324 strintmap_set(relevant_sources, one->path,
1325 RELEVANT_NO_MORE);
1326 continue;
1330 if (new_num_src < i)
1331 memcpy(&rename_src[new_num_src], &rename_src[i],
1332 sizeof(struct diff_rename_src));
1333 new_num_src++;
1336 rename_src_nr = new_num_src;
1339 static void free_filespec_data(struct diff_filespec *spec)
1341 if (!--spec->count)
1342 diff_free_filespec_data(spec);
1345 static void pool_free_filespec(struct mem_pool *pool,
1346 struct diff_filespec *spec)
1348 if (!pool) {
1349 free_filespec(spec);
1350 return;
1354 * Similar to free_filespec(), but only frees the data. The spec
1355 * itself was allocated in the pool and should not be individually
1356 * freed.
1358 free_filespec_data(spec);
1361 void pool_diff_free_filepair(struct mem_pool *pool,
1362 struct diff_filepair *p)
1364 if (!pool) {
1365 diff_free_filepair(p);
1366 return;
1370 * Similar to diff_free_filepair() but only frees the data from the
1371 * filespecs; not the filespecs or the filepair which were
1372 * allocated from the pool.
1374 free_filespec_data(p->one);
1375 free_filespec_data(p->two);
1378 void diffcore_rename_extended(struct diff_options *options,
1379 struct mem_pool *pool,
1380 struct strintmap *relevant_sources,
1381 struct strintmap *dirs_removed,
1382 struct strmap *dir_rename_count,
1383 struct strmap *cached_pairs)
1385 int detect_rename = options->detect_rename;
1386 int minimum_score = options->rename_score;
1387 struct diff_queue_struct *q = &diff_queued_diff;
1388 struct diff_queue_struct outq;
1389 struct diff_score *mx;
1390 int i, j, rename_count, skip_unmodified = 0;
1391 int num_destinations, dst_cnt;
1392 int num_sources, want_copies;
1393 struct progress *progress = NULL;
1394 struct mem_pool local_pool;
1395 struct dir_rename_info info;
1396 struct diff_populate_filespec_options dpf_options = {
1397 .check_binary = 0,
1398 .missing_object_cb = NULL,
1399 .missing_object_data = NULL
1401 struct inexact_prefetch_options prefetch_options = {
1402 .repo = options->repo
1405 trace2_region_enter("diff", "setup", options->repo);
1406 info.setup = 0;
1407 assert(!dir_rename_count || strmap_empty(dir_rename_count));
1408 want_copies = (detect_rename == DIFF_DETECT_COPY);
1409 if (dirs_removed && (break_idx || want_copies))
1410 BUG("dirs_removed incompatible with break/copy detection");
1411 if (break_idx && relevant_sources)
1412 BUG("break detection incompatible with source specification");
1413 if (!minimum_score)
1414 minimum_score = DEFAULT_RENAME_SCORE;
1416 for (i = 0; i < q->nr; i++) {
1417 struct diff_filepair *p = q->queue[i];
1418 if (!DIFF_FILE_VALID(p->one)) {
1419 if (!DIFF_FILE_VALID(p->two))
1420 continue; /* unmerged */
1421 else if (options->single_follow &&
1422 strcmp(options->single_follow, p->two->path))
1423 continue; /* not interested */
1424 else if (!options->flags.rename_empty &&
1425 is_empty_blob_oid(&p->two->oid))
1426 continue;
1427 else if (add_rename_dst(p) < 0) {
1428 warning("skipping rename detection, detected"
1429 " duplicate destination '%s'",
1430 p->two->path);
1431 goto cleanup;
1434 else if (!options->flags.rename_empty &&
1435 is_empty_blob_oid(&p->one->oid))
1436 continue;
1437 else if (!DIFF_PAIR_UNMERGED(p) && !DIFF_FILE_VALID(p->two)) {
1439 * If the source is a broken "delete", and
1440 * they did not really want to get broken,
1441 * that means the source actually stays.
1442 * So we increment the "rename_used" score
1443 * by one, to indicate ourselves as a user
1445 if (p->broken_pair && !p->score)
1446 p->one->rename_used++;
1447 register_rename_src(p);
1449 else if (want_copies) {
1451 * Increment the "rename_used" score by
1452 * one, to indicate ourselves as a user.
1454 p->one->rename_used++;
1455 register_rename_src(p);
1458 trace2_region_leave("diff", "setup", options->repo);
1459 if (rename_dst_nr == 0 || rename_src_nr == 0)
1460 goto cleanup; /* nothing to do */
1462 trace2_region_enter("diff", "exact renames", options->repo);
1463 mem_pool_init(&local_pool, 32*1024);
1465 * We really want to cull the candidates list early
1466 * with cheap tests in order to avoid doing deltas.
1468 rename_count = find_exact_renames(options, &local_pool);
1470 * Discard local_pool immediately instead of at "cleanup:" in order
1471 * to reduce maximum memory usage; inexact rename detection uses up
1472 * a fair amount of memory, and mem_pools can too.
1474 mem_pool_discard(&local_pool, 0);
1475 trace2_region_leave("diff", "exact renames", options->repo);
1477 /* Did we only want exact renames? */
1478 if (minimum_score == MAX_SCORE)
1479 goto cleanup;
1481 num_sources = rename_src_nr;
1483 if (want_copies || break_idx) {
1485 * Cull sources:
1486 * - remove ones corresponding to exact renames
1487 * - remove ones not found in relevant_sources
1489 trace2_region_enter("diff", "cull after exact", options->repo);
1490 remove_unneeded_paths_from_src(want_copies, relevant_sources);
1491 trace2_region_leave("diff", "cull after exact", options->repo);
1492 } else {
1493 /* Determine minimum score to match basenames */
1494 double factor = 0.5;
1495 char *basename_factor = getenv("GIT_BASENAME_FACTOR");
1496 int min_basename_score;
1498 if (basename_factor)
1499 factor = strtol(basename_factor, NULL, 10)/100.0;
1500 assert(factor >= 0.0 && factor <= 1.0);
1501 min_basename_score = minimum_score +
1502 (int)(factor * (MAX_SCORE - minimum_score));
1505 * Cull sources:
1506 * - remove ones involved in renames (found via exact match)
1508 trace2_region_enter("diff", "cull after exact", options->repo);
1509 remove_unneeded_paths_from_src(want_copies, NULL);
1510 trace2_region_leave("diff", "cull after exact", options->repo);
1512 /* Preparation for basename-driven matching. */
1513 trace2_region_enter("diff", "dir rename setup", options->repo);
1514 initialize_dir_rename_info(&info, relevant_sources,
1515 dirs_removed, dir_rename_count,
1516 cached_pairs);
1517 trace2_region_leave("diff", "dir rename setup", options->repo);
1519 /* Utilize file basenames to quickly find renames. */
1520 trace2_region_enter("diff", "basename matches", options->repo);
1521 rename_count += find_basename_matches(options,
1522 min_basename_score,
1523 &info,
1524 relevant_sources,
1525 dirs_removed);
1526 trace2_region_leave("diff", "basename matches", options->repo);
1529 * Cull sources, again:
1530 * - remove ones involved in renames (found via basenames)
1531 * - remove ones not found in relevant_sources
1532 * and
1533 * - remove ones in relevant_sources which are needed only
1534 * for directory renames IF no ancestory directory
1535 * actually needs to know any more individual path
1536 * renames under them
1538 trace2_region_enter("diff", "cull basename", options->repo);
1539 remove_unneeded_paths_from_src(want_copies, relevant_sources);
1540 handle_early_known_dir_renames(&info, relevant_sources,
1541 dirs_removed);
1542 trace2_region_leave("diff", "cull basename", options->repo);
1545 /* Calculate how many rename destinations are left */
1546 num_destinations = (rename_dst_nr - rename_count);
1547 num_sources = rename_src_nr; /* rename_src_nr reflects lower number */
1549 /* All done? */
1550 if (!num_destinations || !num_sources)
1551 goto cleanup;
1553 switch (too_many_rename_candidates(num_destinations, num_sources,
1554 options)) {
1555 case 1:
1556 goto cleanup;
1557 case 2:
1558 options->degraded_cc_to_c = 1;
1559 skip_unmodified = 1;
1560 break;
1561 default:
1562 break;
1565 trace2_region_enter("diff", "inexact renames", options->repo);
1566 if (options->show_rename_progress) {
1567 progress = start_delayed_progress(
1568 _("Performing inexact rename detection"),
1569 (uint64_t)num_destinations * (uint64_t)num_sources);
1572 /* Finish setting up dpf_options */
1573 prefetch_options.skip_unmodified = skip_unmodified;
1574 if (options->repo == the_repository && repo_has_promisor_remote(the_repository)) {
1575 dpf_options.missing_object_cb = inexact_prefetch;
1576 dpf_options.missing_object_data = &prefetch_options;
1579 CALLOC_ARRAY(mx, st_mult(NUM_CANDIDATE_PER_DST, num_destinations));
1580 for (dst_cnt = i = 0; i < rename_dst_nr; i++) {
1581 struct diff_filespec *two = rename_dst[i].p->two;
1582 struct diff_score *m;
1584 if (rename_dst[i].is_rename)
1585 continue; /* exact or basename match already handled */
1587 m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];
1588 for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)
1589 m[j].dst = -1;
1591 for (j = 0; j < rename_src_nr; j++) {
1592 struct diff_filespec *one = rename_src[j].p->one;
1593 struct diff_score this_src;
1595 assert(!one->rename_used || want_copies || break_idx);
1597 if (skip_unmodified &&
1598 diff_unmodified_pair(rename_src[j].p))
1599 continue;
1601 this_src.score = estimate_similarity(options->repo,
1602 one, two,
1603 minimum_score,
1604 &dpf_options);
1605 this_src.name_score = basename_same(one, two);
1606 this_src.dst = i;
1607 this_src.src = j;
1608 record_if_better(m, &this_src);
1610 * Once we run estimate_similarity,
1611 * We do not need the text anymore.
1613 diff_free_filespec_blob(one);
1614 diff_free_filespec_blob(two);
1616 dst_cnt++;
1617 display_progress(progress,
1618 (uint64_t)dst_cnt * (uint64_t)num_sources);
1620 stop_progress(&progress);
1622 /* cost matrix sorted by most to least similar pair */
1623 STABLE_QSORT(mx, dst_cnt * NUM_CANDIDATE_PER_DST, score_compare);
1625 rename_count += find_renames(mx, dst_cnt, minimum_score, 0,
1626 &info, dirs_removed);
1627 if (want_copies)
1628 rename_count += find_renames(mx, dst_cnt, minimum_score, 1,
1629 &info, dirs_removed);
1630 free(mx);
1631 trace2_region_leave("diff", "inexact renames", options->repo);
1633 cleanup:
1634 /* At this point, we have found some renames and copies and they
1635 * are recorded in rename_dst. The original list is still in *q.
1637 trace2_region_enter("diff", "write back to queue", options->repo);
1638 DIFF_QUEUE_CLEAR(&outq);
1639 for (i = 0; i < q->nr; i++) {
1640 struct diff_filepair *p = q->queue[i];
1641 struct diff_filepair *pair_to_free = NULL;
1643 if (DIFF_PAIR_UNMERGED(p)) {
1644 diff_q(&outq, p);
1646 else if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {
1647 /* Creation */
1648 diff_q(&outq, p);
1650 else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {
1652 * Deletion
1654 * We would output this delete record if:
1656 * (1) this is a broken delete and the counterpart
1657 * broken create remains in the output; or
1658 * (2) this is not a broken delete, and rename_dst
1659 * does not have a rename/copy to move p->one->path
1660 * out of existence.
1662 * Otherwise, the counterpart broken create
1663 * has been turned into a rename-edit; or
1664 * delete did not have a matching create to
1665 * begin with.
1667 if (DIFF_PAIR_BROKEN(p)) {
1668 /* broken delete */
1669 struct diff_rename_dst *dst = locate_rename_dst(p);
1670 if (!dst)
1671 BUG("tracking failed somehow; failed to find associated dst for broken pair");
1672 if (dst->is_rename)
1673 /* counterpart is now rename/copy */
1674 pair_to_free = p;
1676 else {
1677 if (p->one->rename_used)
1678 /* this path remains */
1679 pair_to_free = p;
1682 if (!pair_to_free)
1683 diff_q(&outq, p);
1685 else if (!diff_unmodified_pair(p))
1686 /* all the usual ones need to be kept */
1687 diff_q(&outq, p);
1688 else
1689 /* no need to keep unmodified pairs */
1690 pair_to_free = p;
1692 if (pair_to_free)
1693 pool_diff_free_filepair(pool, pair_to_free);
1695 diff_debug_queue("done copying original", &outq);
1697 free(q->queue);
1698 *q = outq;
1699 diff_debug_queue("done collapsing", q);
1701 for (i = 0; i < rename_dst_nr; i++)
1702 if (rename_dst[i].filespec_to_free)
1703 pool_free_filespec(pool, rename_dst[i].filespec_to_free);
1705 cleanup_dir_rename_info(&info, dirs_removed, dir_rename_count != NULL);
1706 FREE_AND_NULL(rename_dst);
1707 rename_dst_nr = rename_dst_alloc = 0;
1708 FREE_AND_NULL(rename_src);
1709 rename_src_nr = rename_src_alloc = 0;
1710 if (break_idx) {
1711 strintmap_clear(break_idx);
1712 FREE_AND_NULL(break_idx);
1714 trace2_region_leave("diff", "write back to queue", options->repo);
1715 return;
1718 void diffcore_rename(struct diff_options *options)
1720 diffcore_rename_extended(options, NULL, NULL, NULL, NULL, NULL);