]> git.ipfire.org Git - thirdparty/git.git/blame - diffcore-rename.c
diffcore-rename: compute dir_rename_counts in stages
[thirdparty/git.git] / diffcore-rename.c
CommitLineData
427dcb4b 1/*
95acf11a 2 *
427dcb4b
JH
3 * Copyright (C) 2005 Junio C Hamano
4 */
5#include "cache.h"
6#include "diff.h"
7#include "diffcore.h"
cbd53a21 8#include "object-store.h"
f79d9c58 9#include "hashmap.h"
3ac942d4 10#include "progress.h"
95acf11a 11#include "promisor-remote.h"
9db2ac56 12#include "strmap.h"
427dcb4b 13
25d5ea41
JH
14/* Table of rename/copy destinations */
15
16static struct diff_rename_dst {
9db2ac56
EN
17 struct diff_filepair *p;
18 struct diff_filespec *filespec_to_free;
19 int is_rename; /* false -> just a create; true -> rename or copy */
25d5ea41
JH
20} *rename_dst;
21static int rename_dst_nr, rename_dst_alloc;
9db2ac56
EN
22/* Mapping from break source pathname to break destination index */
23static struct strintmap *break_idx = NULL;
427dcb4b 24
9db2ac56 25static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)
f98c2f7e 26{
9db2ac56
EN
27 /* Lookup by p->ONE->path */
28 int idx = break_idx ? strintmap_get(break_idx, p->one->path) : -1;
29 return (idx == -1) ? NULL : &rename_dst[idx];
f98c2f7e
JK
30}
31
32/*
33 * Returns 0 on success, -1 if we found a duplicate.
34 */
9db2ac56 35static int add_rename_dst(struct diff_filepair *p)
f98c2f7e 36{
337ce247 37 ALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);
9db2ac56
EN
38 rename_dst[rename_dst_nr].p = p;
39 rename_dst[rename_dst_nr].filespec_to_free = NULL;
40 rename_dst[rename_dst_nr].is_rename = 0;
25d5ea41 41 rename_dst_nr++;
f98c2f7e 42 return 0;
427dcb4b
JH
43}
44
15d061b4 45/* Table of rename/copy src files */
25d5ea41 46static struct diff_rename_src {
e88d6bc6 47 struct diff_filepair *p;
fc580719 48 unsigned short score; /* to remember the break score */
25d5ea41
JH
49} *rename_src;
50static int rename_src_nr, rename_src_alloc;
427dcb4b 51
b970b4ef 52static void register_rename_src(struct diff_filepair *p)
25d5ea41 53{
9db2ac56
EN
54 if (p->broken_pair) {
55 if (!break_idx) {
56 break_idx = xmalloc(sizeof(*break_idx));
57 strintmap_init(break_idx, -1);
58 }
59 strintmap_set(break_idx, p->one->path, rename_dst_nr);
60 }
61
337ce247 62 ALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);
b970b4ef
EN
63 rename_src[rename_src_nr].p = p;
64 rename_src[rename_src_nr].score = p->score;
25d5ea41 65 rename_src_nr++;
427dcb4b
JH
66}
67
0ce39643
JS
68static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)
69{
70 int src_len = strlen(src->path), dst_len = strlen(dst->path);
71 while (src_len && dst_len) {
72 char c1 = src->path[--src_len];
73 char c2 = dst->path[--dst_len];
74 if (c1 != c2)
75 return 0;
76 if (c1 == '/')
77 return 1;
78 }
79 return (!src_len || src->path[src_len - 1] == '/') &&
80 (!dst_len || dst->path[dst_len - 1] == '/');
81}
82
427dcb4b 83struct diff_score {
25d5ea41
JH
84 int src; /* index in rename_src */
85 int dst; /* index in rename_dst */
6d24ad97
JH
86 unsigned short score;
87 short name_score;
427dcb4b
JH
88};
89
95acf11a
JT
90struct prefetch_options {
91 struct repository *repo;
92 int skip_unmodified;
93};
94static void prefetch(void *prefetch_options)
95{
96 struct prefetch_options *options = prefetch_options;
97 int i;
98 struct oid_array to_fetch = OID_ARRAY_INIT;
99
100 for (i = 0; i < rename_dst_nr; i++) {
9db2ac56 101 if (rename_dst[i].p->renamed_pair)
95acf11a
JT
102 /*
103 * The loop in diffcore_rename() will not need these
104 * blobs, so skip prefetching.
105 */
106 continue; /* already found exact match */
107 diff_add_if_missing(options->repo, &to_fetch,
9db2ac56 108 rename_dst[i].p->two);
95acf11a
JT
109 }
110 for (i = 0; i < rename_src_nr; i++) {
111 if (options->skip_unmodified &&
112 diff_unmodified_pair(rename_src[i].p))
113 /*
114 * The loop in diffcore_rename() will not need these
115 * blobs, so skip prefetching.
116 */
117 continue;
118 diff_add_if_missing(options->repo, &to_fetch,
119 rename_src[i].p->one);
120 }
121 promisor_remote_get_direct(options->repo, to_fetch.oid, to_fetch.nr);
122 oid_array_clear(&to_fetch);
123}
124
b78ea5fc
NTND
125static int estimate_similarity(struct repository *r,
126 struct diff_filespec *src,
427dcb4b 127 struct diff_filespec *dst,
95acf11a
JT
128 int minimum_score,
129 int skip_unmodified)
427dcb4b
JH
130{
131 /* src points at a file that existed in the original tree (or
132 * optionally a file in the destination tree) and dst points
133 * at a newly created file. They may be quite similar, in which
134 * case we want to say src is renamed to dst or src is copied into
135 * dst, and then some edit has been applied to dst.
136 *
137 * Compare them and return how similar they are, representing
f0c6b2a2
JH
138 * the score as an integer between 0 and MAX_SCORE.
139 *
140 * When there is an exact match, it is considered a better
141 * match than anything else; the destination does not even
142 * call into this function in that case.
427dcb4b 143 */
90bd932c 144 unsigned long max_size, delta_size, base_size, src_copied, literal_added;
427dcb4b 145 int score;
1c37e86a
JT
146 struct diff_populate_filespec_options dpf_options = {
147 .check_size_only = 1
148 };
95acf11a
JT
149 struct prefetch_options prefetch_options = {r, skip_unmodified};
150
151 if (r == the_repository && has_promisor_remote()) {
152 dpf_options.missing_object_cb = prefetch;
153 dpf_options.missing_object_data = &prefetch_options;
154 }
427dcb4b 155
60896c7b
JH
156 /* We deal only with regular files. Symlink renames are handled
157 * only when they are exact matches --- in other words, no edits
158 * after renaming.
159 */
160 if (!S_ISREG(src->mode) || !S_ISREG(dst->mode))
161 return 0;
162
81ac051d
LT
163 /*
164 * Need to check that source and destination sizes are
165 * filled in before comparing them.
166 *
167 * If we already have "cnt_data" filled in, we know it's
168 * all good (avoid checking the size for zero, as that
169 * is a possible size - we really should have a flag to
170 * say whether the size is valid or not!)
171 */
8e5dd3d6 172 if (!src->cnt_data &&
1c37e86a 173 diff_populate_filespec(r, src, &dpf_options))
81ac051d 174 return 0;
8e5dd3d6 175 if (!dst->cnt_data &&
1c37e86a 176 diff_populate_filespec(r, dst, &dpf_options))
81ac051d
LT
177 return 0;
178
90bd932c 179 max_size = ((src->size > dst->size) ? src->size : dst->size);
58b103f5 180 base_size = ((src->size < dst->size) ? src->size : dst->size);
90bd932c 181 delta_size = max_size - base_size;
427dcb4b 182
58b103f5
JH
183 /* We would not consider edits that change the file size so
184 * drastically. delta_size must be smaller than
cd1870ed 185 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
f0c6b2a2 186 *
58b103f5
JH
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.
427dcb4b 190 */
3a4d6769 191 if (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)
427dcb4b
JH
192 return 0;
193
95acf11a
JT
194 dpf_options.check_size_only = 0;
195
196 if (!src->cnt_data && diff_populate_filespec(r, src, &dpf_options))
885c716f 197 return 0;
95acf11a 198 if (!dst->cnt_data && diff_populate_filespec(r, dst, &dpf_options))
885c716f
BS
199 return 0;
200
b78ea5fc 201 if (diffcore_count_changes(r, src, dst,
c06c7966 202 &src->cnt_data, &dst->cnt_data,
65416758 203 &src_copied, &literal_added))
85976974 204 return 0;
355e76a4 205
1706306a
JH
206 /* How similar are they?
207 * what percentage of material in dst are from source?
427dcb4b 208 */
90bd932c 209 if (!dst->size)
1706306a 210 score = 0; /* should not happen */
cfc0aef1 211 else
dc49cd76 212 score = (int)(src_copied * MAX_SCORE / max_size);
427dcb4b
JH
213 return score;
214}
215
5098bafb 216static void record_rename_pair(int dst_index, int src_index, int score)
427dcb4b 217{
9db2ac56
EN
218 struct diff_filepair *src = rename_src[src_index].p;
219 struct diff_filepair *dst = rename_dst[dst_index].p;
f7c1512a 220
9db2ac56 221 if (dst->renamed_pair)
25d5ea41 222 die("internal error: dst already matched.");
427dcb4b 223
9db2ac56
EN
224 src->one->rename_used++;
225 src->one->count++;
427dcb4b 226
9db2ac56
EN
227 rename_dst[dst_index].filespec_to_free = dst->one;
228 rename_dst[dst_index].is_rename = 1;
427dcb4b 229
9db2ac56
EN
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;
fc580719 234 else
9db2ac56 235 dst->score = score;
427dcb4b
JH
236}
237
238/*
239 * We sort the rename similarity matrix with the score, in descending
15d061b4 240 * order (the most similar first).
427dcb4b
JH
241 */
242static int score_compare(const void *a_, const void *b_)
243{
244 const struct diff_score *a = a_, *b = b_;
cfc0aef1 245
6d24ad97
JH
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
cfc0aef1
RS
252 if (a->score == b->score)
253 return b->name_score - a->name_score;
254
427dcb4b
JH
255 return b->score - a->score;
256}
257
9027f53c 258struct file_similarity {
f79d9c58 259 struct hashmap_entry entry;
7c85f8ac 260 int index;
9027f53c 261 struct diff_filespec *filespec;
9027f53c
LT
262};
263
b78ea5fc
NTND
264static unsigned int hash_filespec(struct repository *r,
265 struct diff_filespec *filespec)
48f6407f 266{
41c9560e 267 if (!filespec->oid_valid) {
1c37e86a 268 if (diff_populate_filespec(r, filespec, NULL))
48f6407f 269 return 0;
2dcde20e
MT
270 hash_object_file(r->hash_algo, filespec->data, filespec->size,
271 "blob", &filespec->oid);
48f6407f 272 }
d40abc8e 273 return oidhash(&filespec->oid);
48f6407f
KB
274}
275
f79d9c58 276static int find_identical_files(struct hashmap *srcs,
7c85f8ac 277 int dst_index,
11f944dd 278 struct diff_options *options)
9027f53c
LT
279{
280 int renames = 0;
9db2ac56 281 struct diff_filespec *target = rename_dst[dst_index].p->two;
ab73a9d1 282 struct file_similarity *p, *best = NULL;
48f6407f 283 int i = 100, best_score = -1;
f0e63c41 284 unsigned int hash = hash_filespec(options->repo, target);
48f6407f
KB
285
286 /*
7c85f8ac 287 * Find the best source match for specified destination.
48f6407f 288 */
f0e63c41
EW
289 p = hashmap_get_entry_from_hash(srcs, hash, NULL,
290 struct file_similarity, entry);
23dee69f 291 hashmap_for_each_entry_from(srcs, p, entry) {
48f6407f
KB
292 int score;
293 struct diff_filespec *source = p->filespec;
294
295 /* False hash collision? */
9001dc2a 296 if (!oideq(&source->oid, &target->oid))
48f6407f
KB
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)
0940e5f2 301 continue;
9027f53c 302 }
48f6407f
KB
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;
9027f53c 313 }
48f6407f
KB
314
315 /* Too many identical alternatives? Pick one */
316 if (!--i)
317 break;
318 }
319 if (best) {
7c85f8ac 320 record_rename_pair(dst_index, best->index, MAX_SCORE);
48f6407f
KB
321 renames++;
322 }
9027f53c
LT
323 return renames;
324}
325
b78ea5fc
NTND
326static void insert_file_table(struct repository *r,
327 struct hashmap *table, int index,
328 struct diff_filespec *filespec)
9027f53c 329{
9027f53c
LT
330 struct file_similarity *entry = xmalloc(sizeof(*entry));
331
9027f53c
LT
332 entry->index = index;
333 entry->filespec = filespec;
9027f53c 334
d22245a2 335 hashmap_entry_init(&entry->entry, hash_filespec(r, filespec));
b94e5c1d 336 hashmap_add(table, &entry->entry);
9027f53c
LT
337}
338
cb1491b6
LT
339/*
340 * Find exact renames first.
341 *
342 * The first round matches up the up-to-date entries,
343 * and then during the second round we try to match
344 * cache-dirty entries as well.
cb1491b6 345 */
11f944dd 346static int find_exact_renames(struct diff_options *options)
cb1491b6 347{
7c85f8ac 348 int i, renames = 0;
f79d9c58 349 struct hashmap file_table;
cb1491b6 350
ca4e3ca0
SG
351 /* Add all sources to the hash table in reverse order, because
352 * later on they will be retrieved in LIFO order.
353 */
7663cdc8 354 hashmap_init(&file_table, NULL, NULL, rename_src_nr);
ca4e3ca0 355 for (i = rename_src_nr-1; i >= 0; i--)
b78ea5fc
NTND
356 insert_file_table(options->repo,
357 &file_table, i,
358 rename_src[i].p->one);
9027f53c 359
7c85f8ac 360 /* Walk the destinations and find best source match */
9027f53c 361 for (i = 0; i < rename_dst_nr; i++)
7c85f8ac 362 renames += find_identical_files(&file_table, i, options);
9027f53c 363
f79d9c58 364 /* Free the hash data structure and entries */
6da1a258 365 hashmap_clear_and_free(&file_table, struct file_similarity, entry);
9027f53c 366
7c85f8ac 367 return renames;
cb1491b6
LT
368}
369
bde8b9f3
EN
370struct dir_rename_info {
371 struct strintmap idx_map;
372 struct strmap dir_rename_guess;
373 struct strmap *dir_rename_count;
374 unsigned setup;
375};
376
377static char *get_dirname(const char *filename)
378{
379 char *slash = strrchr(filename, '/');
380 return slash ? xstrndup(filename, slash - filename) : xstrdup("");
381}
382
0c4fd732
EN
383static void dirname_munge(char *filename)
384{
385 char *slash = strrchr(filename, '/');
386 if (!slash)
387 slash = filename;
388 *slash = '\0';
389}
390
b6e3d274 391static void increment_count(struct dir_rename_info *info,
0c4fd732
EN
392 char *old_dir,
393 char *new_dir)
394{
395 struct strintmap *counts;
396 struct strmap_entry *e;
397
398 /* Get the {new_dirs -> counts} mapping using old_dir */
b6e3d274 399 e = strmap_get_entry(info->dir_rename_count, old_dir);
0c4fd732
EN
400 if (e) {
401 counts = e->value;
402 } else {
403 counts = xmalloc(sizeof(*counts));
404 strintmap_init_with_options(counts, 0, NULL, 1);
b6e3d274 405 strmap_put(info->dir_rename_count, old_dir, counts);
0c4fd732
EN
406 }
407
408 /* Increment the count for new_dir */
409 strintmap_incr(counts, new_dir, 1);
410}
411
b6e3d274 412static void update_dir_rename_counts(struct dir_rename_info *info,
0c4fd732
EN
413 struct strset *dirs_removed,
414 const char *oldname,
415 const char *newname)
416{
417 char *old_dir = xstrdup(oldname);
418 char *new_dir = xstrdup(newname);
419 char new_dir_first_char = new_dir[0];
420 int first_time_in_loop = 1;
421
1ad69eb0
EN
422 if (!info->setup)
423 /*
424 * info->setup is 0 here in two cases: (1) all auxiliary
425 * vars (like dirs_removed) were NULL so
426 * initialize_dir_rename_info() returned early, or (2)
427 * either break detection or copy detection are active so
428 * that we never called initialize_dir_rename_info(). In
429 * the former case, we don't have enough info to know if
430 * directories were renamed (because dirs_removed lets us
431 * know about a necessary prerequisite, namely if they were
432 * removed), and in the latter, we don't care about
433 * directory renames or find_basename_matches.
434 *
435 * This matters because both basename and inexact matching
436 * will also call update_dir_rename_counts(). In either of
437 * the above two cases info->dir_rename_counts will not
438 * have been properly initialized which prevents us from
439 * updating it, but in these two cases we don't care about
440 * dir_rename_counts anyway, so we can just exit early.
441 */
442 return;
443
0c4fd732
EN
444 while (1) {
445 dirname_munge(old_dir);
446 dirname_munge(new_dir);
447
448 /*
449 * When renaming
450 * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"
451 * then this suggests that both
452 * a/b/c/d/e/ => a/b/some/thing/else/e/
453 * a/b/c/d/ => a/b/some/thing/else/
454 * so we want to increment counters for both. We do NOT,
455 * however, also want to suggest that there was the following
456 * rename:
457 * a/b/c/ => a/b/some/thing/
458 * so we need to quit at that point.
459 *
460 * Note the when first_time_in_loop, we only strip off the
461 * basename, and we don't care if that's different.
462 */
463 if (!first_time_in_loop) {
464 char *old_sub_dir = strchr(old_dir, '\0')+1;
465 char *new_sub_dir = strchr(new_dir, '\0')+1;
466 if (!*new_dir) {
467 /*
468 * Special case when renaming to root directory,
469 * i.e. when new_dir == "". In this case, we had
470 * something like
471 * a/b/subdir => subdir
472 * and so dirname_munge() sets things up so that
473 * old_dir = "a/b\0subdir\0"
474 * new_dir = "\0ubdir\0"
475 * We didn't have a '/' to overwrite a '\0' onto
476 * in new_dir, so we have to compare differently.
477 */
478 if (new_dir_first_char != old_sub_dir[0] ||
479 strcmp(old_sub_dir+1, new_sub_dir))
480 break;
481 } else {
482 if (strcmp(old_sub_dir, new_sub_dir))
483 break;
484 }
485 }
486
487 if (strset_contains(dirs_removed, old_dir))
b6e3d274 488 increment_count(info, old_dir, new_dir);
0c4fd732
EN
489 else
490 break;
491
492 /* If we hit toplevel directory ("") for old or new dir, quit */
493 if (!*old_dir || !*new_dir)
494 break;
495
496 first_time_in_loop = 0;
497 }
498
499 /* Free resources we don't need anymore */
500 free(old_dir);
501 free(new_dir);
502}
503
1ad69eb0
EN
504static void initialize_dir_rename_info(struct dir_rename_info *info,
505 struct strset *dirs_removed,
506 struct strmap *dir_rename_count)
0c4fd732
EN
507{
508 int i;
509
1ad69eb0
EN
510 if (!dirs_removed) {
511 info->setup = 0;
512 return;
0c4fd732 513 }
ae8cf74d
EN
514 info->setup = 1;
515
1ad69eb0
EN
516 info->dir_rename_count = dir_rename_count;
517 if (!info->dir_rename_count) {
518 info->dir_rename_count = xmalloc(sizeof(*dir_rename_count));
519 strmap_init(info->dir_rename_count);
520 }
ae8cf74d
EN
521 strintmap_init_with_options(&info->idx_map, -1, NULL, 0);
522 strmap_init_with_options(&info->dir_rename_guess, NULL, 0);
ae8cf74d
EN
523
524 /*
1ad69eb0
EN
525 * Loop setting up both info->idx_map, and doing setup of
526 * info->dir_rename_count.
ae8cf74d
EN
527 */
528 for (i = 0; i < rename_dst_nr; ++i) {
529 /*
530 * For non-renamed files, make idx_map contain mapping of
531 * filename -> index (index within rename_dst, that is)
532 */
533 if (!rename_dst[i].is_rename) {
534 char *filename = rename_dst[i].p->two->path;
535 strintmap_set(&info->idx_map, filename, i);
1ad69eb0 536 continue;
ae8cf74d 537 }
1ad69eb0
EN
538
539 /*
540 * For everything else (i.e. renamed files), make
541 * dir_rename_count contain a map of a map:
542 * old_directory -> {new_directory -> count}
543 * In other words, for every pair look at the directories for
544 * the old filename and the new filename and count how many
545 * times that pairing occurs.
546 */
547 update_dir_rename_counts(info, dirs_removed,
548 rename_dst[i].p->one->path,
549 rename_dst[i].p->two->path);
ae8cf74d
EN
550 }
551}
552
cd52e005
EN
553void partial_clear_dir_rename_count(struct strmap *dir_rename_count)
554{
555 struct hashmap_iter iter;
556 struct strmap_entry *entry;
557
558 strmap_for_each_entry(dir_rename_count, &iter, entry) {
559 struct strintmap *counts = entry->value;
560 strintmap_clear(counts);
561 }
562 strmap_partial_clear(dir_rename_count, 1);
563}
564
b1473019
EN
565static void cleanup_dir_rename_info(struct dir_rename_info *info,
566 struct strset *dirs_removed,
567 int keep_dir_rename_count)
ae8cf74d 568{
b1473019
EN
569 struct hashmap_iter iter;
570 struct strmap_entry *entry;
571 struct string_list to_remove = STRING_LIST_INIT_NODUP;
572 int i;
573
ae8cf74d
EN
574 if (!info->setup)
575 return;
576
577 /* idx_map */
578 strintmap_clear(&info->idx_map);
579
580 /* dir_rename_guess */
581 strmap_clear(&info->dir_rename_guess, 1);
582
b6e3d274 583 /* dir_rename_count */
b1473019
EN
584 if (!keep_dir_rename_count) {
585 partial_clear_dir_rename_count(info->dir_rename_count);
586 strmap_clear(info->dir_rename_count, 1);
587 FREE_AND_NULL(info->dir_rename_count);
588 return;
589 }
590
591 /*
592 * Although dir_rename_count was passed in
593 * diffcore_rename_extended() and we want to keep it around and
594 * return it to that caller, we first want to remove any data
595 * associated with directories that weren't renamed.
596 */
597 strmap_for_each_entry(info->dir_rename_count, &iter, entry) {
598 const char *source_dir = entry->key;
599 struct strintmap *counts = entry->value;
600
601 if (!strset_contains(dirs_removed, source_dir)) {
602 string_list_append(&to_remove, source_dir);
603 strintmap_clear(counts);
604 continue;
605 }
606 }
607 for (i = 0; i < to_remove.nr; ++i)
608 strmap_remove(info->dir_rename_count,
609 to_remove.items[i].string, 1);
610 string_list_clear(&to_remove, 0);
ae8cf74d
EN
611}
612
a35df337
EN
613static const char *get_basename(const char *filename)
614{
615 /*
616 * gitbasename() has to worry about special drives, multiple
617 * directory separator characters, trailing slashes, NULL or
618 * empty strings, etc. We only work on filenames as stored in
619 * git, and thus get to ignore all those complications.
620 */
621 const char *base = strrchr(filename, '/');
622 return base ? base + 1 : filename;
623}
624
bde8b9f3 625static int idx_possible_rename(char *filename, struct dir_rename_info *info)
37a25143 626{
bde8b9f3
EN
627 /*
628 * Our comparison of files with the same basename (see
629 * find_basename_matches() below), is only helpful when after exact
630 * rename detection we have exactly one file with a given basename
631 * among the rename sources and also only exactly one file with
632 * that basename among the rename destinations. When we have
633 * multiple files with the same basename in either set, we do not
634 * know which to compare against. However, there are some
635 * filenames that occur in large numbers (particularly
636 * build-related filenames such as 'Makefile', '.gitignore', or
637 * 'build.gradle' that potentially exist within every single
638 * subdirectory), and for performance we want to be able to quickly
639 * find renames for these files too.
640 *
641 * The reason basename comparisons are a useful heuristic was that it
642 * is common for people to move files across directories while keeping
643 * their filename the same. If we had a way of determining or even
644 * making a good educated guess about which directory these non-unique
645 * basename files had moved the file to, we could check it.
646 * Luckily...
647 *
648 * When an entire directory is in fact renamed, we have two factors
649 * helping us out:
650 * (a) the original directory disappeared giving us a hint
651 * about when we can apply an extra heuristic.
652 * (a) we often have several files within that directory and
653 * subdirectories that are renamed without changes
654 * So, rules for a heuristic:
655 * (0) If there basename matches are non-unique (the condition under
656 * which this function is called) AND
657 * (1) the directory in which the file was found has disappeared
658 * (i.e. dirs_removed is non-NULL and has a relevant entry) THEN
659 * (2) use exact renames of files within the directory to determine
660 * where the directory is likely to have been renamed to. IF
661 * there is at least one exact rename from within that
662 * directory, we can proceed.
663 * (3) If there are multiple places the directory could have been
664 * renamed to based on exact renames, ignore all but one of them.
665 * Just use the destination with the most renames going to it.
666 * (4) Check if applying that directory rename to the original file
667 * would result in a destination filename that is in the
668 * potential rename set. If so, return the index of the
669 * destination file (the index within rename_dst).
670 * (5) Compare the original file and returned destination for
671 * similarity, and if they are sufficiently similar, record the
672 * rename.
673 *
674 * This function, idx_possible_rename(), is only responsible for (4).
675 * The conditions/steps in (1)-(3) will be handled via setting up
676 * dir_rename_count and dir_rename_guess in a future
677 * initialize_dir_rename_info() function. Steps (0) and (5) are
678 * handled by the caller of this function.
679 */
680 char *old_dir, *new_dir;
681 struct strbuf new_path = STRBUF_INIT;
682 int idx;
683
684 if (!info->setup)
685 return -1;
686
687 old_dir = get_dirname(filename);
688 new_dir = strmap_get(&info->dir_rename_guess, old_dir);
689 free(old_dir);
690 if (!new_dir)
691 return -1;
692
693 strbuf_addstr(&new_path, new_dir);
694 strbuf_addch(&new_path, '/');
695 strbuf_addstr(&new_path, get_basename(filename));
696
697 idx = strintmap_get(&info->idx_map, new_path.buf);
698 strbuf_release(&new_path);
699 return idx;
37a25143
EN
700}
701
a35df337 702static int find_basename_matches(struct diff_options *options,
bde8b9f3 703 int minimum_score,
1ad69eb0
EN
704 struct dir_rename_info *info,
705 struct strset *dirs_removed)
a35df337 706{
da09f651
EN
707 /*
708 * When I checked in early 2020, over 76% of file renames in linux
709 * just moved files to a different directory but kept the same
710 * basename. gcc did that with over 64% of renames, gecko did it
711 * with over 79%, and WebKit did it with over 89%.
712 *
713 * Therefore we can bypass the normal exhaustive NxM matrix
714 * comparison of similarities between all potential rename sources
715 * and destinations by instead using file basename as a hint (i.e.
716 * the portion of the filename after the last '/'), checking for
717 * similarity between files with the same basename, and if we find
718 * a pair that are sufficiently similar, record the rename pair and
719 * exclude those two from the NxM matrix.
720 *
721 * This *might* cause us to find a less than optimal pairing (if
722 * there is another file that we are even more similar to but has a
723 * different basename). Given the huge performance advantage
724 * basename matching provides, and given the frequency with which
725 * people use the same basename in real world projects, that's a
726 * trade-off we are willing to accept when doing just rename
727 * detection.
728 *
729 * If someone wants copy detection that implies they are willing to
730 * spend more cycles to find similarities between files, so it may
731 * be less likely that this heuristic is wanted. If someone is
732 * doing break detection, that means they do not want filename
733 * similarity to imply any form of content similiarity, and thus
734 * this heuristic would definitely be incompatible.
735 */
736
737 int i, renames = 0;
a35df337
EN
738 struct strintmap sources;
739 struct strintmap dests;
da09f651
EN
740
741 /*
742 * The prefeteching stuff wants to know if it can skip prefetching
743 * blobs that are unmodified...and will then do a little extra work
744 * to verify that the oids are indeed different before prefetching.
745 * Unmodified blobs are only relevant when doing copy detection;
746 * when limiting to rename detection, diffcore_rename[_extended]()
747 * will never be called with unmodified source paths fed to us, so
748 * the extra work necessary to check if rename_src entries are
749 * unmodified would be a small waste.
750 */
751 int skip_unmodified = 0;
a35df337
EN
752
753 /*
754 * Create maps of basename -> fullname(s) for remaining sources and
755 * dests.
756 */
757 strintmap_init_with_options(&sources, -1, NULL, 0);
758 strintmap_init_with_options(&dests, -1, NULL, 0);
759 for (i = 0; i < rename_src_nr; ++i) {
760 char *filename = rename_src[i].p->one->path;
761 const char *base;
762
763 /* exact renames removed in remove_unneeded_paths_from_src() */
764 assert(!rename_src[i].p->one->rename_used);
765
766 /* Record index within rename_src (i) if basename is unique */
767 base = get_basename(filename);
768 if (strintmap_contains(&sources, base))
769 strintmap_set(&sources, base, -1);
770 else
771 strintmap_set(&sources, base, i);
772 }
773 for (i = 0; i < rename_dst_nr; ++i) {
774 char *filename = rename_dst[i].p->two->path;
775 const char *base;
776
777 if (rename_dst[i].is_rename)
778 continue; /* involved in exact match already. */
779
780 /* Record index within rename_dst (i) if basename is unique */
781 base = get_basename(filename);
782 if (strintmap_contains(&dests, base))
783 strintmap_set(&dests, base, -1);
784 else
785 strintmap_set(&dests, base, i);
786 }
787
da09f651 788 /* Now look for basename matchups and do similarity estimation */
37a25143
EN
789 for (i = 0; i < rename_src_nr; ++i) {
790 char *filename = rename_src[i].p->one->path;
791 const char *base = NULL;
792 intptr_t src_index;
da09f651 793 intptr_t dst_index;
da09f651 794
37a25143
EN
795 /*
796 * If the basename is unique among remaining sources, then
797 * src_index will equal 'i' and we can attempt to match it
798 * to a unique basename in the destinations. Otherwise,
799 * use directory rename heuristics, if possible.
800 */
801 base = get_basename(filename);
802 src_index = strintmap_get(&sources, base);
803 assert(src_index == -1 || src_index == i);
804
805 if (strintmap_contains(&dests, base)) {
da09f651
EN
806 struct diff_filespec *one, *two;
807 int score;
808
37a25143
EN
809 /* Find a matching destination, if possible */
810 dst_index = strintmap_get(&dests, base);
811 if (src_index == -1 || dst_index == -1) {
812 src_index = i;
bde8b9f3 813 dst_index = idx_possible_rename(filename, info);
37a25143
EN
814 }
815 if (dst_index == -1)
816 continue;
817
818 /* Ignore this dest if already used in a rename */
819 if (rename_dst[dst_index].is_rename)
820 continue; /* already used previously */
821
da09f651
EN
822 /* Estimate the similarity */
823 one = rename_src[src_index].p->one;
824 two = rename_dst[dst_index].p->two;
825 score = estimate_similarity(options->repo, one, two,
826 minimum_score, skip_unmodified);
827
828 /* If sufficiently similar, record as rename pair */
829 if (score < minimum_score)
830 continue;
831 record_rename_pair(dst_index, src_index, score);
832 renames++;
1ad69eb0
EN
833 update_dir_rename_counts(info, dirs_removed,
834 one->path, two->path);
da09f651
EN
835
836 /*
837 * Found a rename so don't need text anymore; if we
838 * didn't find a rename, the filespec_blob would get
839 * re-used when doing the matrix of comparisons.
840 */
841 diff_free_filespec_blob(one);
842 diff_free_filespec_blob(two);
843 }
844 }
a35df337
EN
845
846 strintmap_clear(&sources);
847 strintmap_clear(&dests);
848
da09f651 849 return renames;
a35df337
EN
850}
851
6d24ad97
JH
852#define NUM_CANDIDATE_PER_DST 4
853static void record_if_better(struct diff_score m[], struct diff_score *o)
854{
855 int i, worst;
856
857 /* find the worst one */
858 worst = 0;
859 for (i = 1; i < NUM_CANDIDATE_PER_DST; i++)
860 if (score_compare(&m[i], &m[worst]) > 0)
861 worst = i;
862
863 /* is it better than the worst one? */
864 if (score_compare(&m[worst], o) > 0)
865 m[worst] = *o;
866}
867
f31027c9
JH
868/*
869 * Returns:
870 * 0 if we are under the limit;
871 * 1 if we need to disable inexact rename detection;
872 * 2 if we would be under the limit if we were given -C instead of -C -C.
873 */
00b8cccd 874static int too_many_rename_candidates(int num_destinations, int num_sources,
9d8a5a50
JH
875 struct diff_options *options)
876{
877 int rename_limit = options->rename_limit;
00b8cccd 878 int i, limited_sources;
9d8a5a50
JH
879
880 options->needed_rename_limit = 0;
881
882 /*
883 * This basically does a test for the rename matrix not
884 * growing larger than a "rename_limit" square matrix, ie:
885 *
00b8cccd 886 * num_destinations * num_sources > rename_limit * rename_limit
ad8a1be5
EN
887 *
888 * We use st_mult() to check overflow conditions; in the
889 * exceptional circumstance that size_t isn't large enough to hold
890 * the multiplication, the system won't be able to allocate enough
891 * memory for the matrix anyway.
9d8a5a50 892 */
89973554
JT
893 if (rename_limit <= 0)
894 rename_limit = 32767;
ad8a1be5
EN
895 if (st_mult(num_destinations, num_sources)
896 <= st_mult(rename_limit, rename_limit))
9d8a5a50
JH
897 return 0;
898
899 options->needed_rename_limit =
00b8cccd 900 num_sources > num_destinations ? num_sources : num_destinations;
f31027c9
JH
901
902 /* Are we running under -C -C? */
0d1e0e78 903 if (!options->flags.find_copies_harder)
f31027c9
JH
904 return 1;
905
906 /* Would we bust the limit if we were running under -C? */
00b8cccd 907 for (limited_sources = i = 0; i < num_sources; i++) {
f31027c9
JH
908 if (diff_unmodified_pair(rename_src[i].p))
909 continue;
00b8cccd 910 limited_sources++;
f31027c9 911 }
ad8a1be5
EN
912 if (st_mult(num_destinations, limited_sources)
913 <= st_mult(rename_limit, rename_limit))
f31027c9 914 return 2;
9d8a5a50
JH
915 return 1;
916}
917
1ad69eb0
EN
918static int find_renames(struct diff_score *mx,
919 int dst_cnt,
920 int minimum_score,
921 int copies,
922 struct dir_rename_info *info,
923 struct strset *dirs_removed)
0940e5f2
LT
924{
925 int count = 0, i;
926
927 for (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {
928 struct diff_rename_dst *dst;
929
930 if ((mx[i].dst < 0) ||
931 (mx[i].score < minimum_score))
932 break; /* there is no more usable pair. */
933 dst = &rename_dst[mx[i].dst];
9db2ac56 934 if (dst->is_rename)
0940e5f2 935 continue; /* already done, either exact or fuzzy. */
e88d6bc6 936 if (!copies && rename_src[mx[i].src].p->one->rename_used)
0940e5f2
LT
937 continue;
938 record_rename_pair(mx[i].dst, mx[i].src, mx[i].score);
939 count++;
1ad69eb0
EN
940 update_dir_rename_counts(info, dirs_removed,
941 rename_src[mx[i].src].p->one->path,
942 rename_dst[mx[i].dst].p->two->path);
0940e5f2
LT
943 }
944 return count;
945}
946
829514c5
EN
947static void remove_unneeded_paths_from_src(int detecting_copies)
948{
949 int i, new_num_src;
950
951 if (detecting_copies)
952 return; /* nothing to remove */
953 if (break_idx)
954 return; /* culling incompatible with break detection */
955
956 /*
957 * Note on reasons why we cull unneeded sources but not destinations:
958 * 1) Pairings are stored in rename_dst (not rename_src), which we
959 * need to keep around. So, we just can't cull rename_dst even
960 * if we wanted to. But doing so wouldn't help because...
961 *
962 * 2) There is a matrix pairwise comparison that follows the
963 * "Performing inexact rename detection" progress message.
964 * Iterating over the destinations is done in the outer loop,
965 * hence we only iterate over each of those once and we can
966 * easily skip the outer loop early if the destination isn't
967 * relevant. That's only one check per destination path to
968 * skip.
969 *
970 * By contrast, the sources are iterated in the inner loop; if
971 * we check whether a source can be skipped, then we'll be
972 * checking it N separate times, once for each destination.
973 * We don't want to have to iterate over known-not-needed
974 * sources N times each, so avoid that by removing the sources
975 * from rename_src here.
976 */
977 for (i = 0, new_num_src = 0; i < rename_src_nr; i++) {
978 /*
979 * renames are stored in rename_dst, so if a rename has
980 * already been detected using this source, we can just
981 * remove the source knowing rename_dst has its info.
982 */
983 if (rename_src[i].p->one->rename_used)
984 continue;
985
986 if (new_num_src < i)
987 memcpy(&rename_src[new_num_src], &rename_src[i],
988 sizeof(struct diff_rename_src));
989 new_num_src++;
990 }
991
992 rename_src_nr = new_num_src;
993}
994
0c4fd732
EN
995void diffcore_rename_extended(struct diff_options *options,
996 struct strset *dirs_removed,
997 struct strmap *dir_rename_count)
427dcb4b 998{
8082d8d3
JH
999 int detect_rename = options->detect_rename;
1000 int minimum_score = options->rename_score;
38c6f780 1001 struct diff_queue_struct *q = &diff_queued_diff;
5098bafb 1002 struct diff_queue_struct outq;
427dcb4b 1003 struct diff_score *mx;
f31027c9 1004 int i, j, rename_count, skip_unmodified = 0;
26a66a6b 1005 int num_destinations, dst_cnt;
f15eb7c1 1006 int num_sources, want_copies;
3ac942d4 1007 struct progress *progress = NULL;
bde8b9f3 1008 struct dir_rename_info info;
427dcb4b 1009
557ac035 1010 trace2_region_enter("diff", "setup", options->repo);
bde8b9f3 1011 info.setup = 0;
0c4fd732 1012 assert(!dir_rename_count || strmap_empty(dir_rename_count));
f15eb7c1 1013 want_copies = (detect_rename == DIFF_DETECT_COPY);
1ad69eb0
EN
1014 if (dirs_removed && (break_idx || want_copies))
1015 BUG("dirs_removed incompatible with break/copy detection");
26dee0ad 1016 if (!minimum_score)
f345b0a0 1017 minimum_score = DEFAULT_RENAME_SCORE;
427dcb4b 1018
427dcb4b 1019 for (i = 0; i < q->nr; i++) {
52e95789 1020 struct diff_filepair *p = q->queue[i];
2f3f8b21 1021 if (!DIFF_FILE_VALID(p->one)) {
81e50eab 1022 if (!DIFF_FILE_VALID(p->two))
60896c7b 1023 continue; /* unmerged */
2f3f8b21
JH
1024 else if (options->single_follow &&
1025 strcmp(options->single_follow, p->two->path))
1026 continue; /* not interested */
0d1e0e78 1027 else if (!options->flags.rename_empty &&
02491b67 1028 is_empty_blob_oid(&p->two->oid))
90d43b07 1029 continue;
9db2ac56 1030 else if (add_rename_dst(p) < 0) {
4d6be03b
JK
1031 warning("skipping rename detection, detected"
1032 " duplicate destination '%s'",
1033 p->two->path);
1034 goto cleanup;
1035 }
2f3f8b21 1036 }
0d1e0e78 1037 else if (!options->flags.rename_empty &&
02491b67 1038 is_empty_blob_oid(&p->one->oid))
90d43b07 1039 continue;
d7c9bf22 1040 else if (!DIFF_PAIR_UNMERGED(p) && !DIFF_FILE_VALID(p->two)) {
64479711
LT
1041 /*
1042 * If the source is a broken "delete", and
2210100a
JH
1043 * they did not really want to get broken,
1044 * that means the source actually stays.
64479711
LT
1045 * So we increment the "rename_used" score
1046 * by one, to indicate ourselves as a user
1047 */
1048 if (p->broken_pair && !p->score)
1049 p->one->rename_used++;
e88d6bc6 1050 register_rename_src(p);
64479711 1051 }
f15eb7c1 1052 else if (want_copies) {
64479711
LT
1053 /*
1054 * Increment the "rename_used" score by
1055 * one, to indicate ourselves as a user.
2210100a 1056 */
64479711 1057 p->one->rename_used++;
e88d6bc6 1058 register_rename_src(p);
2210100a 1059 }
427dcb4b 1060 }
557ac035 1061 trace2_region_leave("diff", "setup", options->repo);
0024a549 1062 if (rename_dst_nr == 0 || rename_src_nr == 0)
427dcb4b
JH
1063 goto cleanup; /* nothing to do */
1064
557ac035 1065 trace2_region_enter("diff", "exact renames", options->repo);
17559a64
LT
1066 /*
1067 * We really want to cull the candidates list early
1068 * with cheap tests in order to avoid doing deltas.
1069 */
11f944dd 1070 rename_count = find_exact_renames(options);
557ac035 1071 trace2_region_leave("diff", "exact renames", options->repo);
17559a64 1072
42899ac8
LT
1073 /* Did we only want exact renames? */
1074 if (minimum_score == MAX_SCORE)
1075 goto cleanup;
1076
f15eb7c1 1077 num_sources = rename_src_nr;
42899ac8 1078
bd24aa2f
EN
1079 if (want_copies || break_idx) {
1080 /*
1081 * Cull sources:
1082 * - remove ones corresponding to exact renames
1083 */
1084 trace2_region_enter("diff", "cull after exact", options->repo);
1085 remove_unneeded_paths_from_src(want_copies);
1086 trace2_region_leave("diff", "cull after exact", options->repo);
1087 } else {
1088 /* Determine minimum score to match basenames */
1089 double factor = 0.5;
1090 char *basename_factor = getenv("GIT_BASENAME_FACTOR");
1091 int min_basename_score;
1092
1093 if (basename_factor)
1094 factor = strtol(basename_factor, NULL, 10)/100.0;
1095 assert(factor >= 0.0 && factor <= 1.0);
1096 min_basename_score = minimum_score +
1097 (int)(factor * (MAX_SCORE - minimum_score));
1098
1099 /*
1100 * Cull sources:
1101 * - remove ones involved in renames (found via exact match)
1102 */
1103 trace2_region_enter("diff", "cull after exact", options->repo);
1104 remove_unneeded_paths_from_src(want_copies);
1105 trace2_region_leave("diff", "cull after exact", options->repo);
1106
ae8cf74d
EN
1107 /* Preparation for basename-driven matching. */
1108 trace2_region_enter("diff", "dir rename setup", options->repo);
1ad69eb0
EN
1109 initialize_dir_rename_info(&info,
1110 dirs_removed, dir_rename_count);
ae8cf74d
EN
1111 trace2_region_leave("diff", "dir rename setup", options->repo);
1112
bd24aa2f
EN
1113 /* Utilize file basenames to quickly find renames. */
1114 trace2_region_enter("diff", "basename matches", options->repo);
1115 rename_count += find_basename_matches(options,
bde8b9f3 1116 min_basename_score,
1ad69eb0 1117 &info, dirs_removed);
bd24aa2f
EN
1118 trace2_region_leave("diff", "basename matches", options->repo);
1119
1120 /*
1121 * Cull sources, again:
1122 * - remove ones involved in renames (found via basenames)
1123 */
1124 trace2_region_enter("diff", "cull basename", options->repo);
1125 remove_unneeded_paths_from_src(want_copies);
1126 trace2_region_leave("diff", "cull basename", options->repo);
1127 }
1128
1129 /* Calculate how many rename destinations are left */
1130 num_destinations = (rename_dst_nr - rename_count);
1131 num_sources = rename_src_nr; /* rename_src_nr reflects lower number */
1132
42899ac8 1133 /* All done? */
f15eb7c1 1134 if (!num_destinations || !num_sources)
42899ac8
LT
1135 goto cleanup;
1136
f15eb7c1 1137 switch (too_many_rename_candidates(num_destinations, num_sources,
00b8cccd 1138 options)) {
f31027c9 1139 case 1:
0024a549 1140 goto cleanup;
f31027c9
JH
1141 case 2:
1142 options->degraded_cc_to_c = 1;
1143 skip_unmodified = 1;
1144 break;
1145 default:
1146 break;
1147 }
0024a549 1148
557ac035 1149 trace2_region_enter("diff", "inexact renames", options->repo);
3ac942d4 1150 if (options->show_rename_progress) {
8aade107 1151 progress = start_delayed_progress(
754dbc43 1152 _("Performing inexact rename detection"),
f15eb7c1 1153 (uint64_t)num_destinations * (uint64_t)num_sources);
3ac942d4
JK
1154 }
1155
26a66a6b
EN
1156 mx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),
1157 sizeof(*mx));
25d5ea41 1158 for (dst_cnt = i = 0; i < rename_dst_nr; i++) {
9db2ac56 1159 struct diff_filespec *two = rename_dst[i].p->two;
6d24ad97
JH
1160 struct diff_score *m;
1161
9db2ac56 1162 if (rename_dst[i].is_rename)
bd24aa2f 1163 continue; /* exact or basename match already handled */
6d24ad97
JH
1164
1165 m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];
1166 for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)
1167 m[j].dst = -1;
1168
25d5ea41 1169 for (j = 0; j < rename_src_nr; j++) {
e88d6bc6 1170 struct diff_filespec *one = rename_src[j].p->one;
6d24ad97 1171 struct diff_score this_src;
f31027c9 1172
829514c5 1173 assert(!one->rename_used || want_copies || break_idx);
f15eb7c1 1174
f31027c9
JH
1175 if (skip_unmodified &&
1176 diff_unmodified_pair(rename_src[j].p))
1177 continue;
1178
b78ea5fc
NTND
1179 this_src.score = estimate_similarity(options->repo,
1180 one, two,
95acf11a
JT
1181 minimum_score,
1182 skip_unmodified);
6d24ad97
JH
1183 this_src.name_score = basename_same(one, two);
1184 this_src.dst = i;
1185 this_src.src = j;
1186 record_if_better(m, &this_src);
809809bb
JH
1187 /*
1188 * Once we run estimate_similarity,
1189 * We do not need the text anymore.
1190 */
8ae92e63 1191 diff_free_filespec_blob(one);
809809bb 1192 diff_free_filespec_blob(two);
427dcb4b
JH
1193 }
1194 dst_cnt++;
81c4bf02 1195 display_progress(progress,
f15eb7c1 1196 (uint64_t)dst_cnt * (uint64_t)num_sources);
427dcb4b 1197 }
3ac942d4 1198 stop_progress(&progress);
6d24ad97 1199
427dcb4b 1200 /* cost matrix sorted by most to least similar pair */
2049b8dc 1201 STABLE_QSORT(mx, dst_cnt * NUM_CANDIDATE_PER_DST, score_compare);
6d24ad97 1202
1ad69eb0
EN
1203 rename_count += find_renames(mx, dst_cnt, minimum_score, 0,
1204 &info, dirs_removed);
f15eb7c1 1205 if (want_copies)
1ad69eb0
EN
1206 rename_count += find_renames(mx, dst_cnt, minimum_score, 1,
1207 &info, dirs_removed);
427dcb4b 1208 free(mx);
557ac035 1209 trace2_region_leave("diff", "inexact renames", options->repo);
427dcb4b 1210
15d061b4 1211 cleanup:
427dcb4b 1212 /* At this point, we have found some renames and copies and they
5098bafb 1213 * are recorded in rename_dst. The original list is still in *q.
427dcb4b 1214 */
557ac035 1215 trace2_region_enter("diff", "write back to queue", options->repo);
9ca5df90 1216 DIFF_QUEUE_CLEAR(&outq);
427dcb4b 1217 for (i = 0; i < q->nr; i++) {
25d5ea41 1218 struct diff_filepair *p = q->queue[i];
25d5ea41
JH
1219 struct diff_filepair *pair_to_free = NULL;
1220
d7c9bf22
MZ
1221 if (DIFF_PAIR_UNMERGED(p)) {
1222 diff_q(&outq, p);
1223 }
1224 else if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {
9db2ac56
EN
1225 /* Creation */
1226 diff_q(&outq, p);
427dcb4b 1227 }
2cd68882
JH
1228 else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {
1229 /*
1230 * Deletion
1231 *
f345b0a0
JH
1232 * We would output this delete record if:
1233 *
1234 * (1) this is a broken delete and the counterpart
1235 * broken create remains in the output; or
5098bafb
JH
1236 * (2) this is not a broken delete, and rename_dst
1237 * does not have a rename/copy to move p->one->path
1238 * out of existence.
f345b0a0
JH
1239 *
1240 * Otherwise, the counterpart broken create
1241 * has been turned into a rename-edit; or
1242 * delete did not have a matching create to
1243 * begin with.
2cd68882 1244 */
f345b0a0
JH
1245 if (DIFF_PAIR_BROKEN(p)) {
1246 /* broken delete */
9db2ac56
EN
1247 struct diff_rename_dst *dst = locate_rename_dst(p);
1248 if (!dst)
1249 BUG("tracking failed somehow; failed to find associated dst for broken pair");
1250 if (dst->is_rename)
f345b0a0
JH
1251 /* counterpart is now rename/copy */
1252 pair_to_free = p;
1253 }
1254 else {
64479711 1255 if (p->one->rename_used)
f345b0a0
JH
1256 /* this path remains */
1257 pair_to_free = p;
1258 }
2cd68882 1259
9db2ac56 1260 if (!pair_to_free)
2cd68882
JH
1261 diff_q(&outq, p);
1262 }
25d5ea41 1263 else if (!diff_unmodified_pair(p))
15d061b4 1264 /* all the usual ones need to be kept */
25d5ea41 1265 diff_q(&outq, p);
15d061b4 1266 else
9db2ac56 1267 /* no need to keep unmodified pairs; FIXME: remove earlier? */
15d061b4
JH
1268 pair_to_free = p;
1269
226406f6
JH
1270 if (pair_to_free)
1271 diff_free_filepair(pair_to_free);
427dcb4b 1272 }
25d5ea41 1273 diff_debug_queue("done copying original", &outq);
427dcb4b 1274
25d5ea41
JH
1275 free(q->queue);
1276 *q = outq;
1277 diff_debug_queue("done collapsing", q);
427dcb4b 1278
9fb88419 1279 for (i = 0; i < rename_dst_nr; i++)
9db2ac56
EN
1280 if (rename_dst[i].filespec_to_free)
1281 free_filespec(rename_dst[i].filespec_to_free);
5098bafb 1282
b1473019 1283 cleanup_dir_rename_info(&info, dirs_removed, dir_rename_count != NULL);
6a83d902 1284 FREE_AND_NULL(rename_dst);
25d5ea41 1285 rename_dst_nr = rename_dst_alloc = 0;
6a83d902 1286 FREE_AND_NULL(rename_src);
25d5ea41 1287 rename_src_nr = rename_src_alloc = 0;
9db2ac56
EN
1288 if (break_idx) {
1289 strintmap_clear(break_idx);
1290 FREE_AND_NULL(break_idx);
1291 }
557ac035 1292 trace2_region_leave("diff", "write back to queue", options->repo);
427dcb4b
JH
1293 return;
1294}
0c4fd732
EN
1295
1296void diffcore_rename(struct diff_options *options)
1297{
1298 diffcore_rename_extended(options, NULL, NULL);
1299}