freshlybakedca.ke
Git fork
1/*
2 *
3 * Copyright (C) 2005 Junio C Hamano
4 */
5
6#define USE_THE_REPOSITORY_VARIABLE
7
8#include "git-compat-util.h"
9#include "diff.h"
10#include "diffcore.h"
11#include "object-file.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"
20
21/* Table of rename/copy destinations */
22
23static 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;
28static int rename_dst_nr, rename_dst_alloc;
29/* Mapping from break source pathname to break destination index */
30static struct strintmap *break_idx = NULL;
31
32static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)
33{
34 /* Lookup by p->ONE->path */
35 int idx = break_idx ? strintmap_get(break_idx, p->one->path) : -1;
36 return (idx == -1 || idx == rename_dst_nr) ? NULL : &rename_dst[idx];
37}
38
39/*
40 * Returns 0 on success, -1 if we found a duplicate.
41 */
42static int add_rename_dst(struct diff_filepair *p)
43{
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;
50}
51
52/* Table of rename/copy src files */
53static struct diff_rename_src {
54 struct diff_filepair *p;
55 unsigned short score; /* to remember the break score */
56} *rename_src;
57static int rename_src_nr, rename_src_alloc;
58
59static void register_rename_src(struct diff_filepair *p)
60{
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);
65 }
66 strintmap_set(break_idx, p->one->path, rename_dst_nr);
67 }
68
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++;
73}
74
75static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)
76{
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;
85 }
86 return (!src_len || src->path[src_len - 1] == '/') &&
87 (!dst_len || dst->path[dst_len - 1] == '/');
88}
89
90struct diff_score {
91 int src; /* index in rename_src */
92 int dst; /* index in rename_dst */
93 unsigned short score;
94 short name_score;
95};
96
97struct inexact_prefetch_options {
98 struct repository *repo;
99 int skip_unmodified;
100};
101static void inexact_prefetch(void *prefetch_options)
102{
103 struct inexact_prefetch_options *options = prefetch_options;
104 int i;
105 struct oid_array to_fetch = OID_ARRAY_INIT;
106
107 for (i = 0; i < rename_dst_nr; i++) {
108 if (rename_dst[i].p->renamed_pair)
109 /*
110 * The loop in diffcore_rename() will not need these
111 * blobs, so skip prefetching.
112 */
113 continue; /* already found exact match */
114 diff_add_if_missing(options->repo, &to_fetch,
115 rename_dst[i].p->two);
116 }
117 for (i = 0; i < rename_src_nr; i++) {
118 if (options->skip_unmodified &&
119 diff_unmodified_pair(rename_src[i].p))
120 /*
121 * The loop in diffcore_rename() will not need these
122 * blobs, so skip prefetching.
123 */
124 continue;
125 diff_add_if_missing(options->repo, &to_fetch,
126 rename_src[i].p->one);
127 }
128 promisor_remote_get_direct(options->repo, to_fetch.oid, to_fetch.nr);
129 oid_array_clear(&to_fetch);
130}
131
132static 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)
137{
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.
143 *
144 * Compare them and return how similar they are, representing
145 * the score as an integer between 0 and MAX_SCORE.
146 *
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.
150 */
151 unsigned long max_size, delta_size, base_size, src_copied, literal_added;
152 int score;
153
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.
157 */
158 if (!S_ISREG(src->mode) || !S_ISREG(dst->mode))
159 return 0;
160
161 /*
162 * Need to check that source and destination sizes are
163 * filled in before comparing them.
164 *
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!)
169 */
170 dpf_opt->check_size_only = 1;
171
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;
178
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;
182
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).
186 *
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.
190 */
191 if (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)
192 return 0;
193
194 dpf_opt->check_size_only = 0;
195
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;
200
201 if (diffcore_count_changes(r, src, dst,
202 &src->cnt_data, &dst->cnt_data,
203 &src_copied, &literal_added))
204 return 0;
205
206 /* How similar are they?
207 * what percentage of material in dst are from source?
208 */
209 if (!dst->size)
210 score = 0; /* should not happen */
211 else
212 score = (int)(src_copied * MAX_SCORE / max_size);
213 return score;
214}
215
216static void record_rename_pair(int dst_index, int src_index, int score)
217{
218 struct diff_filepair *src = rename_src[src_index].p;
219 struct diff_filepair *dst = rename_dst[dst_index].p;
220
221 if (dst->renamed_pair)
222 die("internal error: dst already matched.");
223
224 src->one->rename_used++;
225 src->one->count++;
226
227 rename_dst[dst_index].filespec_to_free = dst->one;
228 rename_dst[dst_index].is_rename = 1;
229
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;
236}
237
238/*
239 * We sort the rename similarity matrix with the score, in descending
240 * order (the most similar first).
241 */
242static int score_compare(const void *a_, const void *b_)
243{
244 const struct diff_score *a = a_, *b = b_;
245
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;
251
252 if (a->score == b->score)
253 return b->name_score - a->name_score;
254
255 return b->score - a->score;
256}
257
258struct file_similarity {
259 struct hashmap_entry entry;
260 int index;
261 struct diff_filespec *filespec;
262};
263
264static unsigned int hash_filespec(struct repository *r,
265 struct diff_filespec *filespec)
266{
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);
272 }
273 return oidhash(&filespec->oid);
274}
275
276static int find_identical_files(struct hashmap *srcs,
277 int dst_index,
278 struct diff_options *options)
279{
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);
285
286 /*
287 * Find the best source match for specified destination.
288 */
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;
294
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;
302 }
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;
313 }
314
315 /* Too many identical alternatives? Pick one */
316 if (!--i)
317 break;
318 }
319 if (best) {
320 record_rename_pair(dst_index, best->index, MAX_SCORE);
321 renames++;
322 }
323 return renames;
324}
325
326static void insert_file_table(struct repository *r,
327 struct mem_pool *pool,
328 struct hashmap *table, int index,
329 struct diff_filespec *filespec)
330{
331 struct file_similarity *entry = mem_pool_alloc(pool, sizeof(*entry));
332
333 entry->index = index;
334 entry->filespec = filespec;
335
336 hashmap_entry_init(&entry->entry, hash_filespec(r, filespec));
337 hashmap_add(table, &entry->entry);
338}
339
340/*
341 * Find exact renames first.
342 *
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.
346 */
347static int find_exact_renames(struct diff_options *options,
348 struct mem_pool *pool)
349{
350 int i, renames = 0;
351 struct hashmap file_table;
352
353 /* Add all sources to the hash table in reverse order, because
354 * later on they will be retrieved in LIFO order.
355 */
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);
361
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);
365
366 /* Free the hash data structure (entries will be freed with the pool) */
367 hashmap_clear(&file_table);
368
369 return renames;
370}
371
372struct 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;
378};
379
380static char *get_dirname(const char *filename)
381{
382 char *slash = strrchr(filename, '/');
383 return slash ? xstrndup(filename, slash - filename) : xstrdup("");
384}
385
386static void dirname_munge(char *filename)
387{
388 char *slash = strrchr(filename, '/');
389 if (!slash)
390 slash = filename;
391 *slash = '\0';
392}
393
394static const char *get_highest_rename_path(struct strintmap *counts)
395{
396 int highest_count = 0;
397 const char *highest_destination_dir = NULL;
398 struct hashmap_iter iter;
399 struct strmap_entry *entry;
400
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;
407 }
408 }
409 return highest_destination_dir;
410}
411
412static const char *UNKNOWN_DIR = "/"; /* placeholder -- short, illegal directory */
413
414static int dir_rename_already_determinable(struct strintmap *counts)
415{
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;
429 }
430 }
431 return first > second + unknown;
432}
433
434static void increment_count(struct dir_rename_info *info,
435 const char *old_dir,
436 const char *new_dir)
437{
438 struct strintmap *counts;
439 struct strmap_entry *e;
440
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);
449 }
450
451 /* Increment the count for new_dir */
452 strintmap_incr(counts, new_dir, 1);
453}
454
455static void update_dir_rename_counts(struct dir_rename_info *info,
456 struct strintmap *dirs_removed,
457 const char *oldname,
458 const char *newname)
459{
460 char *old_dir;
461 char *new_dir;
462 const char new_dir_first_char = newname[0];
463 int first_time_in_loop = 1;
464
465 if (!info->setup)
466 /*
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.
477 *
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.
484 */
485 return;
486
487
488 old_dir = xstrdup(oldname);
489 new_dir = xstrdup(newname);
490
491 while (1) {
492 int drd_flag = NOT_RELEVANT;
493
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;
499
500 /* Get new_dir */
501 dirname_munge(new_dir);
502
503 /*
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.
514 *
515 * Note the when first_time_in_loop, we only strip off the
516 * basename, and we don't care if that's different.
517 */
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) {
522 /*
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.
532 */
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;
539 }
540 }
541
542 /*
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.
555 */
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);
560
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;
567 }
568
569 /* Free resources we don't need anymore */
570 free(old_dir);
571 free(new_dir);
572}
573
574static 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)
579{
580 struct hashmap_iter iter;
581 struct strmap_entry *entry;
582 int i;
583
584 if (!dirs_removed && !relevant_sources) {
585 info->setup = 0;
586 return;
587 }
588 info->setup = 1;
589
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);
594 }
595 strintmap_init_with_options(&info->idx_map, -1, NULL, 0);
596 strmap_init_with_options(&info->dir_rename_guess, NULL, 0);
597
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);
612 }
613 }
614
615 /*
616 * Loop setting up both info->idx_map, and doing setup of
617 * info->dir_rename_count.
618 */
619 for (i = 0; i < rename_dst_nr; ++i) {
620 /*
621 * For non-renamed files, make idx_map contain mapping of
622 * filename -> index (index within rename_dst, that is)
623 */
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;
628 }
629
630 /*
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.
637 */
638 update_dir_rename_counts(info, dirs_removed,
639 rename_dst[i].p->one->path,
640 rename_dst[i].p->two->path);
641 }
642
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;
650
651 update_dir_rename_counts(info, dirs_removed, old_name, new_name);
652 }
653
654 /*
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.
660 */
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;
665
666 best_newdir = xstrdup(get_highest_rename_path(counts));
667 strmap_put(&info->dir_rename_guess, entry->key,
668 best_newdir);
669 }
670}
671
672void partial_clear_dir_rename_count(struct strmap *dir_rename_count)
673{
674 struct hashmap_iter iter;
675 struct strmap_entry *entry;
676
677 strmap_for_each_entry(dir_rename_count, &iter, entry) {
678 struct strintmap *counts = entry->value;
679 strintmap_clear(counts);
680 }
681 strmap_partial_clear(dir_rename_count, 1);
682}
683
684static void cleanup_dir_rename_info(struct dir_rename_info *info,
685 struct strintmap *dirs_removed,
686 int keep_dir_rename_count)
687{
688 struct hashmap_iter iter;
689 struct strmap_entry *entry;
690 struct string_list to_remove = STRING_LIST_INIT_NODUP;
691
692 if (!info->setup)
693 return;
694
695 /* idx_map */
696 strintmap_clear(&info->idx_map);
697
698 /* dir_rename_guess */
699 strmap_clear(&info->dir_rename_guess, 1);
700
701 /* relevant_source_dirs */
702 if (info->relevant_source_dirs &&
703 info->relevant_source_dirs != dirs_removed) {
704 strintmap_clear(info->relevant_source_dirs);
705 FREE_AND_NULL(info->relevant_source_dirs);
706 }
707
708 /* dir_rename_count */
709 if (!keep_dir_rename_count) {
710 partial_clear_dir_rename_count(info->dir_rename_count);
711 strmap_clear(info->dir_rename_count, 1);
712 FREE_AND_NULL(info->dir_rename_count);
713 return;
714 }
715
716 /*
717 * Although dir_rename_count was passed in
718 * diffcore_rename_extended() and we want to keep it around and
719 * return it to that caller, we first want to remove any counts in
720 * the maps associated with UNKNOWN_DIR entries and any data
721 * associated with directories that weren't renamed.
722 */
723 strmap_for_each_entry(info->dir_rename_count, &iter, entry) {
724 const char *source_dir = entry->key;
725 struct strintmap *counts = entry->value;
726
727 if (!strintmap_get(dirs_removed, source_dir)) {
728 string_list_append(&to_remove, source_dir);
729 strintmap_clear(counts);
730 continue;
731 }
732
733 if (strintmap_contains(counts, UNKNOWN_DIR))
734 strintmap_remove(counts, UNKNOWN_DIR);
735 }
736 for (size_t i = 0; i < to_remove.nr; ++i)
737 strmap_remove(info->dir_rename_count,
738 to_remove.items[i].string, 1);
739 string_list_clear(&to_remove, 0);
740}
741
742static const char *get_basename(const char *filename)
743{
744 /*
745 * gitbasename() has to worry about special drives, multiple
746 * directory separator characters, trailing slashes, NULL or
747 * empty strings, etc. We only work on filenames as stored in
748 * git, and thus get to ignore all those complications.
749 */
750 const char *base = strrchr(filename, '/');
751 return base ? base + 1 : filename;
752}
753
754static int idx_possible_rename(char *filename, struct dir_rename_info *info)
755{
756 /*
757 * Our comparison of files with the same basename (see
758 * find_basename_matches() below), is only helpful when after exact
759 * rename detection we have exactly one file with a given basename
760 * among the rename sources and also only exactly one file with
761 * that basename among the rename destinations. When we have
762 * multiple files with the same basename in either set, we do not
763 * know which to compare against. However, there are some
764 * filenames that occur in large numbers (particularly
765 * build-related filenames such as 'Makefile', '.gitignore', or
766 * 'build.gradle' that potentially exist within every single
767 * subdirectory), and for performance we want to be able to quickly
768 * find renames for these files too.
769 *
770 * The reason basename comparisons are a useful heuristic was that it
771 * is common for people to move files across directories while keeping
772 * their filename the same. If we had a way of determining or even
773 * making a good educated guess about which directory these non-unique
774 * basename files had moved the file to, we could check it.
775 * Luckily...
776 *
777 * When an entire directory is in fact renamed, we have two factors
778 * helping us out:
779 * (a) the original directory disappeared giving us a hint
780 * about when we can apply an extra heuristic.
781 * (a) we often have several files within that directory and
782 * subdirectories that are renamed without changes
783 * So, rules for a heuristic:
784 * (0) If there basename matches are non-unique (the condition under
785 * which this function is called) AND
786 * (1) the directory in which the file was found has disappeared
787 * (i.e. dirs_removed is non-NULL and has a relevant entry) THEN
788 * (2) use exact renames of files within the directory to determine
789 * where the directory is likely to have been renamed to. IF
790 * there is at least one exact rename from within that
791 * directory, we can proceed.
792 * (3) If there are multiple places the directory could have been
793 * renamed to based on exact renames, ignore all but one of them.
794 * Just use the destination with the most renames going to it.
795 * (4) Check if applying that directory rename to the original file
796 * would result in a destination filename that is in the
797 * potential rename set. If so, return the index of the
798 * destination file (the index within rename_dst).
799 * (5) Compare the original file and returned destination for
800 * similarity, and if they are sufficiently similar, record the
801 * rename.
802 *
803 * This function, idx_possible_rename(), is only responsible for (4).
804 * The conditions/steps in (1)-(3) are handled via setting up
805 * dir_rename_count and dir_rename_guess in
806 * initialize_dir_rename_info(). Steps (0) and (5) are handled by
807 * the caller of this function.
808 */
809 char *old_dir, *new_dir;
810 struct strbuf new_path = STRBUF_INIT;
811 int idx;
812
813 if (!info->setup)
814 return -1;
815
816 old_dir = get_dirname(filename);
817 new_dir = strmap_get(&info->dir_rename_guess, old_dir);
818 free(old_dir);
819 if (!new_dir)
820 return -1;
821
822 strbuf_addstr(&new_path, new_dir);
823 strbuf_addch(&new_path, '/');
824 strbuf_addstr(&new_path, get_basename(filename));
825
826 idx = strintmap_get(&info->idx_map, new_path.buf);
827 strbuf_release(&new_path);
828 return idx;
829}
830
831struct basename_prefetch_options {
832 struct repository *repo;
833 struct strintmap *relevant_sources;
834 struct strintmap *sources;
835 struct strintmap *dests;
836 struct dir_rename_info *info;
837};
838static void basename_prefetch(void *prefetch_options)
839{
840 struct basename_prefetch_options *options = prefetch_options;
841 struct strintmap *relevant_sources = options->relevant_sources;
842 struct strintmap *sources = options->sources;
843 struct strintmap *dests = options->dests;
844 struct dir_rename_info *info = options->info;
845 int i;
846 struct oid_array to_fetch = OID_ARRAY_INIT;
847
848 /*
849 * TODO: The following loops mirror the code/logic from
850 * find_basename_matches(), though not quite exactly. Maybe
851 * abstract the iteration logic out somehow?
852 */
853 for (i = 0; i < rename_src_nr; ++i) {
854 char *filename = rename_src[i].p->one->path;
855 const char *base = NULL;
856 intptr_t src_index;
857 intptr_t dst_index;
858
859 /* Skip irrelevant sources */
860 if (relevant_sources &&
861 !strintmap_contains(relevant_sources, filename))
862 continue;
863
864 /*
865 * If the basename is unique among remaining sources, then
866 * src_index will equal 'i' and we can attempt to match it
867 * to a unique basename in the destinations. Otherwise,
868 * use directory rename heuristics, if possible.
869 */
870 base = get_basename(filename);
871 src_index = strintmap_get(sources, base);
872 assert(src_index == -1 || src_index == i);
873
874 if (strintmap_contains(dests, base)) {
875 struct diff_filespec *one, *two;
876
877 /* Find a matching destination, if possible */
878 dst_index = strintmap_get(dests, base);
879 if (src_index == -1 || dst_index == -1) {
880 src_index = i;
881 dst_index = idx_possible_rename(filename, info);
882 }
883 if (dst_index == -1)
884 continue;
885
886 /* Ignore this dest if already used in a rename */
887 if (rename_dst[dst_index].is_rename)
888 continue; /* already used previously */
889
890 one = rename_src[src_index].p->one;
891 two = rename_dst[dst_index].p->two;
892
893 /* Add the pairs */
894 diff_add_if_missing(options->repo, &to_fetch, two);
895 diff_add_if_missing(options->repo, &to_fetch, one);
896 }
897 }
898
899 promisor_remote_get_direct(options->repo, to_fetch.oid, to_fetch.nr);
900 oid_array_clear(&to_fetch);
901}
902
903static int find_basename_matches(struct diff_options *options,
904 int minimum_score,
905 struct dir_rename_info *info,
906 struct strintmap *relevant_sources,
907 struct strintmap *dirs_removed)
908{
909 /*
910 * When I checked in early 2020, over 76% of file renames in linux
911 * just moved files to a different directory but kept the same
912 * basename. gcc did that with over 64% of renames, gecko did it
913 * with over 79%, and WebKit did it with over 89%.
914 *
915 * Therefore we can bypass the normal exhaustive NxM matrix
916 * comparison of similarities between all potential rename sources
917 * and destinations by instead using file basename as a hint (i.e.
918 * the portion of the filename after the last '/'), checking for
919 * similarity between files with the same basename, and if we find
920 * a pair that are sufficiently similar, record the rename pair and
921 * exclude those two from the NxM matrix.
922 *
923 * This *might* cause us to find a less than optimal pairing (if
924 * there is another file that we are even more similar to but has a
925 * different basename). Given the huge performance advantage
926 * basename matching provides, and given the frequency with which
927 * people use the same basename in real world projects, that's a
928 * trade-off we are willing to accept when doing just rename
929 * detection.
930 *
931 * If someone wants copy detection that implies they are willing to
932 * spend more cycles to find similarities between files, so it may
933 * be less likely that this heuristic is wanted. If someone is
934 * doing break detection, that means they do not want filename
935 * similarity to imply any form of content similarity, and thus
936 * this heuristic would definitely be incompatible.
937 */
938
939 int i, renames = 0;
940 struct strintmap sources;
941 struct strintmap dests;
942 struct diff_populate_filespec_options dpf_options = {
943 .check_binary = 0,
944 .missing_object_cb = NULL,
945 .missing_object_data = NULL
946 };
947 struct basename_prefetch_options prefetch_options = {
948 .repo = options->repo,
949 .relevant_sources = relevant_sources,
950 .sources = &sources,
951 .dests = &dests,
952 .info = info
953 };
954
955 /*
956 * Create maps of basename -> fullname(s) for remaining sources and
957 * dests.
958 */
959 strintmap_init_with_options(&sources, -1, NULL, 0);
960 strintmap_init_with_options(&dests, -1, NULL, 0);
961 for (i = 0; i < rename_src_nr; ++i) {
962 char *filename = rename_src[i].p->one->path;
963 const char *base;
964
965 /* exact renames removed in remove_unneeded_paths_from_src() */
966 assert(!rename_src[i].p->one->rename_used);
967
968 /* Record index within rename_src (i) if basename is unique */
969 base = get_basename(filename);
970 if (strintmap_contains(&sources, base))
971 strintmap_set(&sources, base, -1);
972 else
973 strintmap_set(&sources, base, i);
974 }
975 for (i = 0; i < rename_dst_nr; ++i) {
976 char *filename = rename_dst[i].p->two->path;
977 const char *base;
978
979 if (rename_dst[i].is_rename)
980 continue; /* involved in exact match already. */
981
982 /* Record index within rename_dst (i) if basename is unique */
983 base = get_basename(filename);
984 if (strintmap_contains(&dests, base))
985 strintmap_set(&dests, base, -1);
986 else
987 strintmap_set(&dests, base, i);
988 }
989
990 if (options->repo == the_repository && repo_has_promisor_remote(the_repository)) {
991 dpf_options.missing_object_cb = basename_prefetch;
992 dpf_options.missing_object_data = &prefetch_options;
993 }
994
995 /* Now look for basename matchups and do similarity estimation */
996 for (i = 0; i < rename_src_nr; ++i) {
997 char *filename = rename_src[i].p->one->path;
998 const char *base = NULL;
999 intptr_t src_index;
1000 intptr_t dst_index;
1001
1002 /* Skip irrelevant sources */
1003 if (relevant_sources &&
1004 !strintmap_contains(relevant_sources, filename))
1005 continue;
1006
1007 /*
1008 * If the basename is unique among remaining sources, then
1009 * src_index will equal 'i' and we can attempt to match it
1010 * to a unique basename in the destinations. Otherwise,
1011 * use directory rename heuristics, if possible.
1012 */
1013 base = get_basename(filename);
1014 src_index = strintmap_get(&sources, base);
1015 assert(src_index == -1 || src_index == i);
1016
1017 if (strintmap_contains(&dests, base)) {
1018 struct diff_filespec *one, *two;
1019 int score;
1020
1021 /* Find a matching destination, if possible */
1022 dst_index = strintmap_get(&dests, base);
1023 if (src_index == -1 || dst_index == -1) {
1024 src_index = i;
1025 dst_index = idx_possible_rename(filename, info);
1026 }
1027 if (dst_index == -1)
1028 continue;
1029
1030 /* Ignore this dest if already used in a rename */
1031 if (rename_dst[dst_index].is_rename)
1032 continue; /* already used previously */
1033
1034 /* Estimate the similarity */
1035 one = rename_src[src_index].p->one;
1036 two = rename_dst[dst_index].p->two;
1037 score = estimate_similarity(options->repo, one, two,
1038 minimum_score, &dpf_options);
1039
1040 /* If sufficiently similar, record as rename pair */
1041 if (score < minimum_score)
1042 continue;
1043 record_rename_pair(dst_index, src_index, score);
1044 renames++;
1045 update_dir_rename_counts(info, dirs_removed,
1046 one->path, two->path);
1047
1048 /*
1049 * Found a rename so don't need text anymore; if we
1050 * didn't find a rename, the filespec_blob would get
1051 * re-used when doing the matrix of comparisons.
1052 */
1053 diff_free_filespec_blob(one);
1054 diff_free_filespec_blob(two);
1055 }
1056 }
1057
1058 strintmap_clear(&sources);
1059 strintmap_clear(&dests);
1060
1061 return renames;
1062}
1063
1064#define NUM_CANDIDATE_PER_DST 4
1065static void record_if_better(struct diff_score m[], struct diff_score *o)
1066{
1067 int i, worst;
1068
1069 /* find the worst one */
1070 worst = 0;
1071 for (i = 1; i < NUM_CANDIDATE_PER_DST; i++)
1072 if (score_compare(&m[i], &m[worst]) > 0)
1073 worst = i;
1074
1075 /* is it better than the worst one? */
1076 if (score_compare(&m[worst], o) > 0)
1077 m[worst] = *o;
1078}
1079
1080/*
1081 * Returns:
1082 * 0 if we are under the limit;
1083 * 1 if we need to disable inexact rename detection;
1084 * 2 if we would be under the limit if we were given -C instead of -C -C.
1085 */
1086static int too_many_rename_candidates(int num_destinations, int num_sources,
1087 struct diff_options *options)
1088{
1089 int rename_limit = options->rename_limit;
1090 int i, limited_sources;
1091
1092 options->needed_rename_limit = 0;
1093
1094 /*
1095 * This basically does a test for the rename matrix not
1096 * growing larger than a "rename_limit" square matrix, ie:
1097 *
1098 * num_destinations * num_sources > rename_limit * rename_limit
1099 *
1100 * We use st_mult() to check overflow conditions; in the
1101 * exceptional circumstance that size_t isn't large enough to hold
1102 * the multiplication, the system won't be able to allocate enough
1103 * memory for the matrix anyway.
1104 */
1105 if (rename_limit <= 0)
1106 return 0; /* treat as unlimited */
1107 if (st_mult(num_destinations, num_sources)
1108 <= st_mult(rename_limit, rename_limit))
1109 return 0;
1110
1111 options->needed_rename_limit =
1112 num_sources > num_destinations ? num_sources : num_destinations;
1113
1114 /* Are we running under -C -C? */
1115 if (!options->flags.find_copies_harder)
1116 return 1;
1117
1118 /* Would we bust the limit if we were running under -C? */
1119 for (limited_sources = i = 0; i < num_sources; i++) {
1120 if (diff_unmodified_pair(rename_src[i].p))
1121 continue;
1122 limited_sources++;
1123 }
1124 if (st_mult(num_destinations, limited_sources)
1125 <= st_mult(rename_limit, rename_limit))
1126 return 2;
1127 return 1;
1128}
1129
1130static int find_renames(struct diff_score *mx,
1131 int dst_cnt,
1132 int minimum_score,
1133 int copies,
1134 struct dir_rename_info *info,
1135 struct strintmap *dirs_removed)
1136{
1137 int count = 0, i;
1138
1139 for (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {
1140 struct diff_rename_dst *dst;
1141
1142 if ((mx[i].dst < 0) ||
1143 (mx[i].score < minimum_score))
1144 break; /* there is no more usable pair. */
1145 dst = &rename_dst[mx[i].dst];
1146 if (dst->is_rename)
1147 continue; /* already done, either exact or fuzzy. */
1148 if (!copies && rename_src[mx[i].src].p->one->rename_used)
1149 continue;
1150 record_rename_pair(mx[i].dst, mx[i].src, mx[i].score);
1151 count++;
1152 update_dir_rename_counts(info, dirs_removed,
1153 rename_src[mx[i].src].p->one->path,
1154 rename_dst[mx[i].dst].p->two->path);
1155 }
1156 return count;
1157}
1158
1159static void remove_unneeded_paths_from_src(int detecting_copies,
1160 struct strintmap *interesting)
1161{
1162 int i, new_num_src;
1163
1164 if (detecting_copies && !interesting)
1165 return; /* nothing to remove */
1166 if (break_idx)
1167 return; /* culling incompatible with break detection */
1168
1169 /*
1170 * Note on reasons why we cull unneeded sources but not destinations:
1171 * 1) Pairings are stored in rename_dst (not rename_src), which we
1172 * need to keep around. So, we just can't cull rename_dst even
1173 * if we wanted to. But doing so wouldn't help because...
1174 *
1175 * 2) There is a matrix pairwise comparison that follows the
1176 * "Performing inexact rename detection" progress message.
1177 * Iterating over the destinations is done in the outer loop,
1178 * hence we only iterate over each of those once and we can
1179 * easily skip the outer loop early if the destination isn't
1180 * relevant. That's only one check per destination path to
1181 * skip.
1182 *
1183 * By contrast, the sources are iterated in the inner loop; if
1184 * we check whether a source can be skipped, then we'll be
1185 * checking it N separate times, once for each destination.
1186 * We don't want to have to iterate over known-not-needed
1187 * sources N times each, so avoid that by removing the sources
1188 * from rename_src here.
1189 */
1190 for (i = 0, new_num_src = 0; i < rename_src_nr; i++) {
1191 struct diff_filespec *one = rename_src[i].p->one;
1192
1193 /*
1194 * renames are stored in rename_dst, so if a rename has
1195 * already been detected using this source, we can just
1196 * remove the source knowing rename_dst has its info.
1197 */
1198 if (!detecting_copies && one->rename_used)
1199 continue;
1200
1201 /* If we don't care about the source path, skip it */
1202 if (interesting && !strintmap_contains(interesting, one->path))
1203 continue;
1204
1205 if (new_num_src < i)
1206 memcpy(&rename_src[new_num_src], &rename_src[i],
1207 sizeof(struct diff_rename_src));
1208 new_num_src++;
1209 }
1210
1211 rename_src_nr = new_num_src;
1212}
1213
1214static void handle_early_known_dir_renames(struct dir_rename_info *info,
1215 struct strintmap *relevant_sources,
1216 struct strintmap *dirs_removed)
1217{
1218 /*
1219 * Directory renames are determined via an aggregate of all renames
1220 * under them and using a "majority wins" rule. The fact that
1221 * "majority wins", though, means we don't need all the renames
1222 * under the given directory, we only need enough to ensure we have
1223 * a majority.
1224 */
1225
1226 int i, new_num_src;
1227 struct hashmap_iter iter;
1228 struct strmap_entry *entry;
1229
1230 if (!dirs_removed || !relevant_sources)
1231 return; /* nothing to cull */
1232 if (break_idx)
1233 return; /* culling incompatbile with break detection */
1234
1235 /*
1236 * Supplement dir_rename_count with number of potential renames,
1237 * marking all potential rename sources as mapping to UNKNOWN_DIR.
1238 */
1239 for (i = 0; i < rename_src_nr; i++) {
1240 char *old_dir;
1241 struct diff_filespec *one = rename_src[i].p->one;
1242
1243 /*
1244 * sources that are part of a rename will have already been
1245 * removed by a prior call to remove_unneeded_paths_from_src()
1246 */
1247 assert(!one->rename_used);
1248
1249 old_dir = get_dirname(one->path);
1250 while (*old_dir != '\0' &&
1251 NOT_RELEVANT != strintmap_get(dirs_removed, old_dir)) {
1252 char *freeme = old_dir;
1253
1254 increment_count(info, old_dir, UNKNOWN_DIR);
1255 old_dir = get_dirname(old_dir);
1256
1257 /* Free resources we don't need anymore */
1258 free(freeme);
1259 }
1260 /*
1261 * old_dir and new_dir free'd in increment_count, but
1262 * get_dirname() gives us a new pointer we need to free for
1263 * old_dir. Also, if the loop runs 0 times we need old_dir
1264 * to be freed.
1265 */
1266 free(old_dir);
1267 }
1268
1269 /*
1270 * For any directory which we need a potential rename detected for
1271 * (i.e. those marked as RELEVANT_FOR_SELF in dirs_removed), check
1272 * whether we have enough renames to satisfy the "majority rules"
1273 * requirement such that detecting any more renames of files under
1274 * it won't change the result. For any such directory, mark that
1275 * we no longer need to detect a rename for it. However, since we
1276 * might need to still detect renames for an ancestor of that
1277 * directory, use RELEVANT_FOR_ANCESTOR.
1278 */
1279 strmap_for_each_entry(info->dir_rename_count, &iter, entry) {
1280 /* entry->key is source_dir */
1281 struct strintmap *counts = entry->value;
1282
1283 if (strintmap_get(dirs_removed, entry->key) ==
1284 RELEVANT_FOR_SELF &&
1285 dir_rename_already_determinable(counts)) {
1286 strintmap_set(dirs_removed, entry->key,
1287 RELEVANT_FOR_ANCESTOR);
1288 }
1289 }
1290
1291 for (i = 0, new_num_src = 0; i < rename_src_nr; i++) {
1292 struct diff_filespec *one = rename_src[i].p->one;
1293 int val;
1294
1295 val = strintmap_get(relevant_sources, one->path);
1296
1297 /*
1298 * sources that were not found in relevant_sources should
1299 * have already been removed by a prior call to
1300 * remove_unneeded_paths_from_src()
1301 */
1302 assert(val != -1);
1303
1304 if (val == RELEVANT_LOCATION) {
1305 int removable = 1;
1306 char *dir = get_dirname(one->path);
1307 while (1) {
1308 char *freeme = dir;
1309 int res = strintmap_get(dirs_removed, dir);
1310
1311 /* Quit if not found or irrelevant */
1312 if (res == NOT_RELEVANT)
1313 break;
1314 /* If RELEVANT_FOR_SELF, can't remove */
1315 if (res == RELEVANT_FOR_SELF) {
1316 removable = 0;
1317 break;
1318 }
1319 /* Else continue searching upwards */
1320 assert(res == RELEVANT_FOR_ANCESTOR);
1321 dir = get_dirname(dir);
1322 free(freeme);
1323 }
1324 free(dir);
1325 if (removable) {
1326 strintmap_set(relevant_sources, one->path,
1327 RELEVANT_NO_MORE);
1328 continue;
1329 }
1330 }
1331
1332 if (new_num_src < i)
1333 memcpy(&rename_src[new_num_src], &rename_src[i],
1334 sizeof(struct diff_rename_src));
1335 new_num_src++;
1336 }
1337
1338 rename_src_nr = new_num_src;
1339}
1340
1341static void free_filespec_data(struct diff_filespec *spec)
1342{
1343 if (!--spec->count)
1344 diff_free_filespec_data(spec);
1345}
1346
1347static void pool_free_filespec(struct mem_pool *pool,
1348 struct diff_filespec *spec)
1349{
1350 if (!pool) {
1351 free_filespec(spec);
1352 return;
1353 }
1354
1355 /*
1356 * Similar to free_filespec(), but only frees the data. The spec
1357 * itself was allocated in the pool and should not be individually
1358 * freed.
1359 */
1360 free_filespec_data(spec);
1361}
1362
1363void pool_diff_free_filepair(struct mem_pool *pool,
1364 struct diff_filepair *p)
1365{
1366 if (!pool) {
1367 diff_free_filepair(p);
1368 return;
1369 }
1370
1371 /*
1372 * Similar to diff_free_filepair() but only frees the data from the
1373 * filespecs; not the filespecs or the filepair which were
1374 * allocated from the pool.
1375 */
1376 free_filespec_data(p->one);
1377 free_filespec_data(p->two);
1378}
1379
1380void diffcore_rename_extended(struct diff_options *options,
1381 struct mem_pool *pool,
1382 struct strintmap *relevant_sources,
1383 struct strintmap *dirs_removed,
1384 struct strmap *dir_rename_count,
1385 struct strmap *cached_pairs)
1386{
1387 int detect_rename = options->detect_rename;
1388 int minimum_score = options->rename_score;
1389 struct diff_queue_struct *q = &diff_queued_diff;
1390 struct diff_queue_struct outq = DIFF_QUEUE_INIT;
1391 struct diff_score *mx;
1392 int i, j, rename_count, skip_unmodified = 0;
1393 int num_destinations, dst_cnt;
1394 int num_sources, want_copies;
1395 struct progress *progress = NULL;
1396 struct mem_pool local_pool;
1397 struct dir_rename_info info;
1398 struct diff_populate_filespec_options dpf_options = {
1399 .check_binary = 0,
1400 .missing_object_cb = NULL,
1401 .missing_object_data = NULL
1402 };
1403 struct inexact_prefetch_options prefetch_options = {
1404 .repo = options->repo
1405 };
1406
1407 trace2_region_enter("diff", "setup", options->repo);
1408 info.setup = 0;
1409 ASSERT(!dir_rename_count || strmap_empty(dir_rename_count));
1410 want_copies = (detect_rename == DIFF_DETECT_COPY);
1411 if (dirs_removed && (break_idx || want_copies))
1412 BUG("dirs_removed incompatible with break/copy detection");
1413 if (break_idx && relevant_sources)
1414 BUG("break detection incompatible with source specification");
1415 if (!minimum_score)
1416 minimum_score = DEFAULT_RENAME_SCORE;
1417
1418 for (i = 0; i < q->nr; i++) {
1419 struct diff_filepair *p = q->queue[i];
1420 if (!DIFF_FILE_VALID(p->one)) {
1421 if (!DIFF_FILE_VALID(p->two))
1422 continue; /* unmerged */
1423 else if (options->single_follow &&
1424 strcmp(options->single_follow, p->two->path))
1425 continue; /* not interested */
1426 else if (!options->flags.rename_empty &&
1427 is_empty_blob_oid(&p->two->oid, the_repository->hash_algo))
1428 continue;
1429 else if (add_rename_dst(p) < 0) {
1430 warning("skipping rename detection, detected"
1431 " duplicate destination '%s'",
1432 p->two->path);
1433 goto cleanup;
1434 }
1435 }
1436 else if (!options->flags.rename_empty &&
1437 is_empty_blob_oid(&p->one->oid, the_repository->hash_algo))
1438 continue;
1439 else if (!DIFF_PAIR_UNMERGED(p) && !DIFF_FILE_VALID(p->two)) {
1440 /*
1441 * If the source is a broken "delete", and
1442 * they did not really want to get broken,
1443 * that means the source actually stays.
1444 * So we increment the "rename_used" score
1445 * by one, to indicate ourselves as a user
1446 */
1447 if (p->broken_pair && !p->score)
1448 p->one->rename_used++;
1449 register_rename_src(p);
1450 }
1451 else if (want_copies) {
1452 /*
1453 * Increment the "rename_used" score by
1454 * one, to indicate ourselves as a user.
1455 */
1456 p->one->rename_used++;
1457 register_rename_src(p);
1458 }
1459 }
1460 trace2_region_leave("diff", "setup", options->repo);
1461 if (rename_dst_nr == 0 || rename_src_nr == 0)
1462 goto cleanup; /* nothing to do */
1463
1464 trace2_region_enter("diff", "exact renames", options->repo);
1465 mem_pool_init(&local_pool, 32*1024);
1466 /*
1467 * We really want to cull the candidates list early
1468 * with cheap tests in order to avoid doing deltas.
1469 */
1470 rename_count = find_exact_renames(options, &local_pool);
1471 /*
1472 * Discard local_pool immediately instead of at "cleanup:" in order
1473 * to reduce maximum memory usage; inexact rename detection uses up
1474 * a fair amount of memory, and mem_pools can too.
1475 */
1476 mem_pool_discard(&local_pool, 0);
1477 trace2_region_leave("diff", "exact renames", options->repo);
1478
1479 /* Did we only want exact renames? */
1480 if (minimum_score == MAX_SCORE)
1481 goto cleanup;
1482
1483 num_sources = rename_src_nr;
1484
1485 if (want_copies || break_idx) {
1486 /*
1487 * Cull sources:
1488 * - remove ones corresponding to exact renames
1489 * - remove ones not found in relevant_sources
1490 */
1491 trace2_region_enter("diff", "cull after exact", options->repo);
1492 remove_unneeded_paths_from_src(want_copies, relevant_sources);
1493 trace2_region_leave("diff", "cull after exact", options->repo);
1494 } else {
1495 /* Determine minimum score to match basenames */
1496 double factor = 0.5;
1497 char *basename_factor = getenv("GIT_BASENAME_FACTOR");
1498 int min_basename_score;
1499
1500 if (basename_factor)
1501 factor = strtol(basename_factor, NULL, 10)/100.0;
1502 assert(factor >= 0.0 && factor <= 1.0);
1503 min_basename_score = minimum_score +
1504 (int)(factor * (MAX_SCORE - minimum_score));
1505
1506 /*
1507 * Cull sources:
1508 * - remove ones involved in renames (found via exact match)
1509 */
1510 trace2_region_enter("diff", "cull after exact", options->repo);
1511 remove_unneeded_paths_from_src(want_copies, NULL);
1512 trace2_region_leave("diff", "cull after exact", options->repo);
1513
1514 /* Preparation for basename-driven matching. */
1515 trace2_region_enter("diff", "dir rename setup", options->repo);
1516 initialize_dir_rename_info(&info, relevant_sources,
1517 dirs_removed, dir_rename_count,
1518 cached_pairs);
1519 trace2_region_leave("diff", "dir rename setup", options->repo);
1520
1521 /* Utilize file basenames to quickly find renames. */
1522 trace2_region_enter("diff", "basename matches", options->repo);
1523 rename_count += find_basename_matches(options,
1524 min_basename_score,
1525 &info,
1526 relevant_sources,
1527 dirs_removed);
1528 trace2_region_leave("diff", "basename matches", options->repo);
1529
1530 /*
1531 * Cull sources, again:
1532 * - remove ones involved in renames (found via basenames)
1533 * - remove ones not found in relevant_sources
1534 * and
1535 * - remove ones in relevant_sources which are needed only
1536 * for directory renames IF no ancestry directory
1537 * actually needs to know any more individual path
1538 * renames under them
1539 */
1540 trace2_region_enter("diff", "cull basename", options->repo);
1541 remove_unneeded_paths_from_src(want_copies, relevant_sources);
1542 handle_early_known_dir_renames(&info, relevant_sources,
1543 dirs_removed);
1544 trace2_region_leave("diff", "cull basename", options->repo);
1545 }
1546
1547 /* Calculate how many rename destinations are left */
1548 num_destinations = (rename_dst_nr - rename_count);
1549 num_sources = rename_src_nr; /* rename_src_nr reflects lower number */
1550
1551 /* All done? */
1552 if (!num_destinations || !num_sources)
1553 goto cleanup;
1554
1555 switch (too_many_rename_candidates(num_destinations, num_sources,
1556 options)) {
1557 case 1:
1558 goto cleanup;
1559 case 2:
1560 options->degraded_cc_to_c = 1;
1561 skip_unmodified = 1;
1562 break;
1563 default:
1564 break;
1565 }
1566
1567 trace2_region_enter("diff", "inexact renames", options->repo);
1568 if (options->show_rename_progress) {
1569 progress = start_delayed_progress(
1570 the_repository,
1571 _("Performing inexact rename detection"),
1572 (uint64_t)num_destinations * (uint64_t)num_sources);
1573 }
1574
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;
1580 }
1581
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;
1586
1587 if (rename_dst[i].is_rename)
1588 continue; /* exact or basename match already handled */
1589
1590 m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];
1591 for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)
1592 m[j].dst = -1;
1593
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;
1597
1598 assert(!one->rename_used || want_copies || break_idx);
1599
1600 if (skip_unmodified &&
1601 diff_unmodified_pair(rename_src[j].p))
1602 continue;
1603
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);
1612 /*
1613 * Once we run estimate_similarity,
1614 * We do not need the text anymore.
1615 */
1616 diff_free_filespec_blob(one);
1617 diff_free_filespec_blob(two);
1618 }
1619 dst_cnt++;
1620 display_progress(progress,
1621 (uint64_t)dst_cnt * (uint64_t)num_sources);
1622 }
1623 stop_progress(&progress);
1624
1625 /* cost matrix sorted by most to least similar pair */
1626 STABLE_QSORT(mx, dst_cnt * NUM_CANDIDATE_PER_DST, score_compare);
1627
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);
1635
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.
1639 */
1640 trace2_region_enter("diff", "write back to queue", options->repo);
1641 for (i = 0; i < q->nr; i++) {
1642 struct diff_filepair *p = q->queue[i];
1643 struct diff_filepair *pair_to_free = NULL;
1644
1645 if (DIFF_PAIR_UNMERGED(p)) {
1646 diff_q(&outq, p);
1647 }
1648 else if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {
1649 /* Creation */
1650 diff_q(&outq, p);
1651 }
1652 else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {
1653 /*
1654 * Deletion
1655 *
1656 * We would output this delete record if:
1657 *
1658 * (1) this is a broken delete and the counterpart
1659 * broken create remains in the output; or
1660 * (2) this is not a broken delete, and rename_dst
1661 * does not have a rename/copy to move p->one->path
1662 * out of existence.
1663 *
1664 * Otherwise, the counterpart broken create
1665 * has been turned into a rename-edit; or
1666 * delete did not have a matching create to
1667 * begin with.
1668 */
1669 if (DIFF_PAIR_BROKEN(p)) {
1670 /* broken delete */
1671 struct diff_rename_dst *dst = locate_rename_dst(p);
1672 if (options->single_follow && dst &&
1673 strcmp(dst->p->two->path, p->two->path))
1674 dst = NULL;
1675 if (dst && dst->is_rename)
1676 /* counterpart is now rename/copy */
1677 pair_to_free = p;
1678 }
1679 else {
1680 if (p->one->rename_used)
1681 /* this path remains */
1682 pair_to_free = p;
1683 }
1684
1685 if (!pair_to_free)
1686 diff_q(&outq, p);
1687 }
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;
1694
1695 if (pair_to_free)
1696 pool_diff_free_filepair(pool, pair_to_free);
1697 }
1698 diff_debug_queue("done copying original", &outq);
1699
1700 free(q->queue);
1701 *q = outq;
1702 diff_debug_queue("done collapsing", q);
1703
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);
1707
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);
1716 }
1717 trace2_region_leave("diff", "write back to queue", options->repo);
1718 return;
1719}
1720
1721void diffcore_rename(struct diff_options *options)
1722{
1723 diffcore_rename_extended(options, NULL, NULL, NULL, NULL, NULL);
1724}