Merge branch 'mz/maint-rename-unmerged' into maint
[git] / diffcore-rename.c
1 /*
2  * Copyright (C) 2005 Junio C Hamano
3  */
4 #include "cache.h"
5 #include "diff.h"
6 #include "diffcore.h"
7 #include "hash.h"
8 #include "progress.h"
9
10 /* Table of rename/copy destinations */
11
12 static struct diff_rename_dst {
13         struct diff_filespec *two;
14         struct diff_filepair *pair;
15 } *rename_dst;
16 static int rename_dst_nr, rename_dst_alloc;
17
18 static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
19                                                  int insert_ok)
20 {
21         int first, last;
22
23         first = 0;
24         last = rename_dst_nr;
25         while (last > first) {
26                 int next = (last + first) >> 1;
27                 struct diff_rename_dst *dst = &(rename_dst[next]);
28                 int cmp = strcmp(two->path, dst->two->path);
29                 if (!cmp)
30                         return dst;
31                 if (cmp < 0) {
32                         last = next;
33                         continue;
34                 }
35                 first = next+1;
36         }
37         /* not found */
38         if (!insert_ok)
39                 return NULL;
40         /* insert to make it at "first" */
41         if (rename_dst_alloc <= rename_dst_nr) {
42                 rename_dst_alloc = alloc_nr(rename_dst_alloc);
43                 rename_dst = xrealloc(rename_dst,
44                                       rename_dst_alloc * sizeof(*rename_dst));
45         }
46         rename_dst_nr++;
47         if (first < rename_dst_nr)
48                 memmove(rename_dst + first + 1, rename_dst + first,
49                         (rename_dst_nr - first - 1) * sizeof(*rename_dst));
50         rename_dst[first].two = alloc_filespec(two->path);
51         fill_filespec(rename_dst[first].two, two->sha1, two->mode);
52         rename_dst[first].pair = NULL;
53         return &(rename_dst[first]);
54 }
55
56 /* Table of rename/copy src files */
57 static struct diff_rename_src {
58         struct diff_filespec *one;
59         unsigned short score; /* to remember the break score */
60 } *rename_src;
61 static int rename_src_nr, rename_src_alloc;
62
63 static struct diff_rename_src *register_rename_src(struct diff_filespec *one,
64                                                    unsigned short score)
65 {
66         int first, last;
67
68         first = 0;
69         last = rename_src_nr;
70         while (last > first) {
71                 int next = (last + first) >> 1;
72                 struct diff_rename_src *src = &(rename_src[next]);
73                 int cmp = strcmp(one->path, src->one->path);
74                 if (!cmp)
75                         return src;
76                 if (cmp < 0) {
77                         last = next;
78                         continue;
79                 }
80                 first = next+1;
81         }
82
83         /* insert to make it at "first" */
84         if (rename_src_alloc <= rename_src_nr) {
85                 rename_src_alloc = alloc_nr(rename_src_alloc);
86                 rename_src = xrealloc(rename_src,
87                                       rename_src_alloc * sizeof(*rename_src));
88         }
89         rename_src_nr++;
90         if (first < rename_src_nr)
91                 memmove(rename_src + first + 1, rename_src + first,
92                         (rename_src_nr - first - 1) * sizeof(*rename_src));
93         rename_src[first].one = one;
94         rename_src[first].score = score;
95         return &(rename_src[first]);
96 }
97
98 static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)
99 {
100         int src_len = strlen(src->path), dst_len = strlen(dst->path);
101         while (src_len && dst_len) {
102                 char c1 = src->path[--src_len];
103                 char c2 = dst->path[--dst_len];
104                 if (c1 != c2)
105                         return 0;
106                 if (c1 == '/')
107                         return 1;
108         }
109         return (!src_len || src->path[src_len - 1] == '/') &&
110                 (!dst_len || dst->path[dst_len - 1] == '/');
111 }
112
113 struct diff_score {
114         int src; /* index in rename_src */
115         int dst; /* index in rename_dst */
116         unsigned short score;
117         short name_score;
118 };
119
120 static int estimate_similarity(struct diff_filespec *src,
121                                struct diff_filespec *dst,
122                                int minimum_score)
123 {
124         /* src points at a file that existed in the original tree (or
125          * optionally a file in the destination tree) and dst points
126          * at a newly created file.  They may be quite similar, in which
127          * case we want to say src is renamed to dst or src is copied into
128          * dst, and then some edit has been applied to dst.
129          *
130          * Compare them and return how similar they are, representing
131          * the score as an integer between 0 and MAX_SCORE.
132          *
133          * When there is an exact match, it is considered a better
134          * match than anything else; the destination does not even
135          * call into this function in that case.
136          */
137         unsigned long max_size, delta_size, base_size, src_copied, literal_added;
138         unsigned long delta_limit;
139         int score;
140
141         /* We deal only with regular files.  Symlink renames are handled
142          * only when they are exact matches --- in other words, no edits
143          * after renaming.
144          */
145         if (!S_ISREG(src->mode) || !S_ISREG(dst->mode))
146                 return 0;
147
148         /*
149          * Need to check that source and destination sizes are
150          * filled in before comparing them.
151          *
152          * If we already have "cnt_data" filled in, we know it's
153          * all good (avoid checking the size for zero, as that
154          * is a possible size - we really should have a flag to
155          * say whether the size is valid or not!)
156          */
157         if (!src->cnt_data && diff_populate_filespec(src, 1))
158                 return 0;
159         if (!dst->cnt_data && diff_populate_filespec(dst, 1))
160                 return 0;
161
162         max_size = ((src->size > dst->size) ? src->size : dst->size);
163         base_size = ((src->size < dst->size) ? src->size : dst->size);
164         delta_size = max_size - base_size;
165
166         /* We would not consider edits that change the file size so
167          * drastically.  delta_size must be smaller than
168          * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
169          *
170          * Note that base_size == 0 case is handled here already
171          * and the final score computation below would not have a
172          * divide-by-zero issue.
173          */
174         if (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)
175                 return 0;
176
177         if (!src->cnt_data && diff_populate_filespec(src, 0))
178                 return 0;
179         if (!dst->cnt_data && diff_populate_filespec(dst, 0))
180                 return 0;
181
182         delta_limit = (unsigned long)
183                 (base_size * (MAX_SCORE-minimum_score) / MAX_SCORE);
184         if (diffcore_count_changes(src, dst,
185                                    &src->cnt_data, &dst->cnt_data,
186                                    delta_limit,
187                                    &src_copied, &literal_added))
188                 return 0;
189
190         /* How similar are they?
191          * what percentage of material in dst are from source?
192          */
193         if (!dst->size)
194                 score = 0; /* should not happen */
195         else
196                 score = (int)(src_copied * MAX_SCORE / max_size);
197         return score;
198 }
199
200 static void record_rename_pair(int dst_index, int src_index, int score)
201 {
202         struct diff_filespec *src, *dst;
203         struct diff_filepair *dp;
204
205         if (rename_dst[dst_index].pair)
206                 die("internal error: dst already matched.");
207
208         src = rename_src[src_index].one;
209         src->rename_used++;
210         src->count++;
211
212         dst = rename_dst[dst_index].two;
213         dst->count++;
214
215         dp = diff_queue(NULL, src, dst);
216         dp->renamed_pair = 1;
217         if (!strcmp(src->path, dst->path))
218                 dp->score = rename_src[src_index].score;
219         else
220                 dp->score = score;
221         rename_dst[dst_index].pair = dp;
222 }
223
224 /*
225  * We sort the rename similarity matrix with the score, in descending
226  * order (the most similar first).
227  */
228 static int score_compare(const void *a_, const void *b_)
229 {
230         const struct diff_score *a = a_, *b = b_;
231
232         /* sink the unused ones to the bottom */
233         if (a->dst < 0)
234                 return (0 <= b->dst);
235         else if (b->dst < 0)
236                 return -1;
237
238         if (a->score == b->score)
239                 return b->name_score - a->name_score;
240
241         return b->score - a->score;
242 }
243
244 struct file_similarity {
245         int src_dst, index;
246         struct diff_filespec *filespec;
247         struct file_similarity *next;
248 };
249
250 static int find_identical_files(struct file_similarity *src,
251                                 struct file_similarity *dst,
252                                 struct diff_options *options)
253 {
254         int renames = 0;
255
256         /*
257          * Walk over all the destinations ...
258          */
259         do {
260                 struct diff_filespec *target = dst->filespec;
261                 struct file_similarity *p, *best;
262                 int i = 100, best_score = -1;
263
264                 /*
265                  * .. to find the best source match
266                  */
267                 best = NULL;
268                 for (p = src; p; p = p->next) {
269                         int score;
270                         struct diff_filespec *source = p->filespec;
271
272                         /* False hash collision? */
273                         if (hashcmp(source->sha1, target->sha1))
274                                 continue;
275                         /* Non-regular files? If so, the modes must match! */
276                         if (!S_ISREG(source->mode) || !S_ISREG(target->mode)) {
277                                 if (source->mode != target->mode)
278                                         continue;
279                         }
280                         /* Give higher scores to sources that haven't been used already */
281                         score = !source->rename_used;
282                         if (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)
283                                 continue;
284                         score += basename_same(source, target);
285                         if (score > best_score) {
286                                 best = p;
287                                 best_score = score;
288                                 if (score == 2)
289                                         break;
290                         }
291
292                         /* Too many identical alternatives? Pick one */
293                         if (!--i)
294                                 break;
295                 }
296                 if (best) {
297                         record_rename_pair(dst->index, best->index, MAX_SCORE);
298                         renames++;
299                 }
300         } while ((dst = dst->next) != NULL);
301         return renames;
302 }
303
304 static void free_similarity_list(struct file_similarity *p)
305 {
306         while (p) {
307                 struct file_similarity *entry = p;
308                 p = p->next;
309                 free(entry);
310         }
311 }
312
313 static int find_same_files(void *ptr, void *data)
314 {
315         int ret;
316         struct file_similarity *p = ptr;
317         struct file_similarity *src = NULL, *dst = NULL;
318         struct diff_options *options = data;
319
320         /* Split the hash list up into sources and destinations */
321         do {
322                 struct file_similarity *entry = p;
323                 p = p->next;
324                 if (entry->src_dst < 0) {
325                         entry->next = src;
326                         src = entry;
327                 } else {
328                         entry->next = dst;
329                         dst = entry;
330                 }
331         } while (p);
332
333         /*
334          * If we have both sources *and* destinations, see if
335          * we can match them up
336          */
337         ret = (src && dst) ? find_identical_files(src, dst, options) : 0;
338
339         /* Free the hashes and return the number of renames found */
340         free_similarity_list(src);
341         free_similarity_list(dst);
342         return ret;
343 }
344
345 static unsigned int hash_filespec(struct diff_filespec *filespec)
346 {
347         unsigned int hash;
348         if (!filespec->sha1_valid) {
349                 if (diff_populate_filespec(filespec, 0))
350                         return 0;
351                 hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1);
352         }
353         memcpy(&hash, filespec->sha1, sizeof(hash));
354         return hash;
355 }
356
357 static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec)
358 {
359         void **pos;
360         unsigned int hash;
361         struct file_similarity *entry = xmalloc(sizeof(*entry));
362
363         entry->src_dst = src_dst;
364         entry->index = index;
365         entry->filespec = filespec;
366         entry->next = NULL;
367
368         hash = hash_filespec(filespec);
369         pos = insert_hash(hash, entry, table);
370
371         /* We already had an entry there? */
372         if (pos) {
373                 entry->next = *pos;
374                 *pos = entry;
375         }
376 }
377
378 /*
379  * Find exact renames first.
380  *
381  * The first round matches up the up-to-date entries,
382  * and then during the second round we try to match
383  * cache-dirty entries as well.
384  */
385 static int find_exact_renames(struct diff_options *options)
386 {
387         int i;
388         struct hash_table file_table;
389
390         init_hash(&file_table);
391         for (i = 0; i < rename_src_nr; i++)
392                 insert_file_table(&file_table, -1, i, rename_src[i].one);
393
394         for (i = 0; i < rename_dst_nr; i++)
395                 insert_file_table(&file_table, 1, i, rename_dst[i].two);
396
397         /* Find the renames */
398         i = for_each_hash(&file_table, find_same_files, options);
399
400         /* .. and free the hash data structure */
401         free_hash(&file_table);
402
403         return i;
404 }
405
406 #define NUM_CANDIDATE_PER_DST 4
407 static void record_if_better(struct diff_score m[], struct diff_score *o)
408 {
409         int i, worst;
410
411         /* find the worst one */
412         worst = 0;
413         for (i = 1; i < NUM_CANDIDATE_PER_DST; i++)
414                 if (score_compare(&m[i], &m[worst]) > 0)
415                         worst = i;
416
417         /* is it better than the worst one? */
418         if (score_compare(&m[worst], o) > 0)
419                 m[worst] = *o;
420 }
421
422 static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, int copies)
423 {
424         int count = 0, i;
425
426         for (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {
427                 struct diff_rename_dst *dst;
428
429                 if ((mx[i].dst < 0) ||
430                     (mx[i].score < minimum_score))
431                         break; /* there is no more usable pair. */
432                 dst = &rename_dst[mx[i].dst];
433                 if (dst->pair)
434                         continue; /* already done, either exact or fuzzy. */
435                 if (!copies && rename_src[mx[i].src].one->rename_used)
436                         continue;
437                 record_rename_pair(mx[i].dst, mx[i].src, mx[i].score);
438                 count++;
439         }
440         return count;
441 }
442
443 void diffcore_rename(struct diff_options *options)
444 {
445         int detect_rename = options->detect_rename;
446         int minimum_score = options->rename_score;
447         int rename_limit = options->rename_limit;
448         struct diff_queue_struct *q = &diff_queued_diff;
449         struct diff_queue_struct outq;
450         struct diff_score *mx;
451         int i, j, rename_count;
452         int num_create, num_src, dst_cnt;
453         struct progress *progress = NULL;
454
455         if (!minimum_score)
456                 minimum_score = DEFAULT_RENAME_SCORE;
457
458         for (i = 0; i < q->nr; i++) {
459                 struct diff_filepair *p = q->queue[i];
460                 if (!DIFF_FILE_VALID(p->one)) {
461                         if (!DIFF_FILE_VALID(p->two))
462                                 continue; /* unmerged */
463                         else if (options->single_follow &&
464                                  strcmp(options->single_follow, p->two->path))
465                                 continue; /* not interested */
466                         else
467                                 locate_rename_dst(p->two, 1);
468                 }
469                 else if (!DIFF_PAIR_UNMERGED(p) && !DIFF_FILE_VALID(p->two)) {
470                         /*
471                          * If the source is a broken "delete", and
472                          * they did not really want to get broken,
473                          * that means the source actually stays.
474                          * So we increment the "rename_used" score
475                          * by one, to indicate ourselves as a user
476                          */
477                         if (p->broken_pair && !p->score)
478                                 p->one->rename_used++;
479                         register_rename_src(p->one, p->score);
480                 }
481                 else if (detect_rename == DIFF_DETECT_COPY) {
482                         /*
483                          * Increment the "rename_used" score by
484                          * one, to indicate ourselves as a user.
485                          */
486                         p->one->rename_used++;
487                         register_rename_src(p->one, p->score);
488                 }
489         }
490         if (rename_dst_nr == 0 || rename_src_nr == 0)
491                 goto cleanup; /* nothing to do */
492
493         /*
494          * We really want to cull the candidates list early
495          * with cheap tests in order to avoid doing deltas.
496          */
497         rename_count = find_exact_renames(options);
498
499         /* Did we only want exact renames? */
500         if (minimum_score == MAX_SCORE)
501                 goto cleanup;
502
503         /*
504          * Calculate how many renames are left (but all the source
505          * files still remain as options for rename/copies!)
506          */
507         num_create = (rename_dst_nr - rename_count);
508         num_src = rename_src_nr;
509
510         /* All done? */
511         if (!num_create)
512                 goto cleanup;
513
514         /*
515          * This basically does a test for the rename matrix not
516          * growing larger than a "rename_limit" square matrix, ie:
517          *
518          *    num_create * num_src > rename_limit * rename_limit
519          *
520          * but handles the potential overflow case specially (and we
521          * assume at least 32-bit integers)
522          */
523         options->needed_rename_limit = 0;
524         if (rename_limit <= 0 || rename_limit > 32767)
525                 rename_limit = 32767;
526         if ((num_create > rename_limit && num_src > rename_limit) ||
527             (num_create * num_src > rename_limit * rename_limit)) {
528                 options->needed_rename_limit =
529                         num_src > num_create ? num_src : num_create;
530                 goto cleanup;
531         }
532
533         if (options->show_rename_progress) {
534                 progress = start_progress_delay(
535                                 "Performing inexact rename detection",
536                                 rename_dst_nr * rename_src_nr, 50, 1);
537         }
538
539         mx = xcalloc(num_create * NUM_CANDIDATE_PER_DST, sizeof(*mx));
540         for (dst_cnt = i = 0; i < rename_dst_nr; i++) {
541                 struct diff_filespec *two = rename_dst[i].two;
542                 struct diff_score *m;
543
544                 if (rename_dst[i].pair)
545                         continue; /* dealt with exact match already. */
546
547                 m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];
548                 for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)
549                         m[j].dst = -1;
550
551                 for (j = 0; j < rename_src_nr; j++) {
552                         struct diff_filespec *one = rename_src[j].one;
553                         struct diff_score this_src;
554                         this_src.score = estimate_similarity(one, two,
555                                                              minimum_score);
556                         this_src.name_score = basename_same(one, two);
557                         this_src.dst = i;
558                         this_src.src = j;
559                         record_if_better(m, &this_src);
560                         /*
561                          * Once we run estimate_similarity,
562                          * We do not need the text anymore.
563                          */
564                         diff_free_filespec_blob(one);
565                         diff_free_filespec_blob(two);
566                 }
567                 dst_cnt++;
568                 display_progress(progress, (i+1)*rename_src_nr);
569         }
570         stop_progress(&progress);
571
572         /* cost matrix sorted by most to least similar pair */
573         qsort(mx, dst_cnt * NUM_CANDIDATE_PER_DST, sizeof(*mx), score_compare);
574
575         rename_count += find_renames(mx, dst_cnt, minimum_score, 0);
576         if (detect_rename == DIFF_DETECT_COPY)
577                 rename_count += find_renames(mx, dst_cnt, minimum_score, 1);
578         free(mx);
579
580  cleanup:
581         /* At this point, we have found some renames and copies and they
582          * are recorded in rename_dst.  The original list is still in *q.
583          */
584         DIFF_QUEUE_CLEAR(&outq);
585         for (i = 0; i < q->nr; i++) {
586                 struct diff_filepair *p = q->queue[i];
587                 struct diff_filepair *pair_to_free = NULL;
588
589                 if (DIFF_PAIR_UNMERGED(p)) {
590                         diff_q(&outq, p);
591                 }
592                 else if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {
593                         /*
594                          * Creation
595                          *
596                          * We would output this create record if it has
597                          * not been turned into a rename/copy already.
598                          */
599                         struct diff_rename_dst *dst =
600                                 locate_rename_dst(p->two, 0);
601                         if (dst && dst->pair) {
602                                 diff_q(&outq, dst->pair);
603                                 pair_to_free = p;
604                         }
605                         else
606                                 /* no matching rename/copy source, so
607                                  * record this as a creation.
608                                  */
609                                 diff_q(&outq, p);
610                 }
611                 else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {
612                         /*
613                          * Deletion
614                          *
615                          * We would output this delete record if:
616                          *
617                          * (1) this is a broken delete and the counterpart
618                          *     broken create remains in the output; or
619                          * (2) this is not a broken delete, and rename_dst
620                          *     does not have a rename/copy to move p->one->path
621                          *     out of existence.
622                          *
623                          * Otherwise, the counterpart broken create
624                          * has been turned into a rename-edit; or
625                          * delete did not have a matching create to
626                          * begin with.
627                          */
628                         if (DIFF_PAIR_BROKEN(p)) {
629                                 /* broken delete */
630                                 struct diff_rename_dst *dst =
631                                         locate_rename_dst(p->one, 0);
632                                 if (dst && dst->pair)
633                                         /* counterpart is now rename/copy */
634                                         pair_to_free = p;
635                         }
636                         else {
637                                 if (p->one->rename_used)
638                                         /* this path remains */
639                                         pair_to_free = p;
640                         }
641
642                         if (pair_to_free)
643                                 ;
644                         else
645                                 diff_q(&outq, p);
646                 }
647                 else if (!diff_unmodified_pair(p))
648                         /* all the usual ones need to be kept */
649                         diff_q(&outq, p);
650                 else
651                         /* no need to keep unmodified pairs */
652                         pair_to_free = p;
653
654                 if (pair_to_free)
655                         diff_free_filepair(pair_to_free);
656         }
657         diff_debug_queue("done copying original", &outq);
658
659         free(q->queue);
660         *q = outq;
661         diff_debug_queue("done collapsing", q);
662
663         for (i = 0; i < rename_dst_nr; i++)
664                 free_filespec(rename_dst[i].two);
665
666         free(rename_dst);
667         rename_dst = NULL;
668         rename_dst_nr = rename_dst_alloc = 0;
669         free(rename_src);
670         rename_src = NULL;
671         rename_src_nr = rename_src_alloc = 0;
672         return;
673 }