[PATCH] Redo rename/copy detection logic.
[git/git.git] / diffcore-rename.c
CommitLineData
427dcb4b
JH
1/*
2 * Copyright (C) 2005 Junio C Hamano
3 */
4#include "cache.h"
5#include "diff.h"
6#include "diffcore.h"
7#include "delta.h"
8
25d5ea41
JH
9/* Table of rename/copy destinations */
10
11static struct diff_rename_dst {
12 struct diff_filespec *two;
13 struct diff_filepair *pair;
14} *rename_dst;
15static int rename_dst_nr, rename_dst_alloc;
427dcb4b 16
25d5ea41
JH
17static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
18 int insert_ok)
427dcb4b 19{
25d5ea41
JH
20 int first, last;
21
22 first = 0;
23 last = rename_dst_nr;
24 while (last > first) {
25 int next = (last + first) >> 1;
26 struct diff_rename_dst *dst = &(rename_dst[next]);
27 int cmp = strcmp(two->path, dst->two->path);
28 if (!cmp)
29 return dst;
30 if (cmp < 0) {
31 last = next;
32 continue;
33 }
34 first = next+1;
35 }
36 /* not found */
37 if (!insert_ok)
38 return NULL;
39 /* insert to make it at "first" */
40 if (rename_dst_alloc <= rename_dst_nr) {
41 rename_dst_alloc = alloc_nr(rename_dst_alloc);
42 rename_dst = xrealloc(rename_dst,
43 rename_dst_alloc * sizeof(*rename_dst));
44 }
45 rename_dst_nr++;
46 if (first < rename_dst_nr)
47 memmove(rename_dst + first + 1, rename_dst + first,
48 (rename_dst_nr - first - 1) * sizeof(*rename_dst));
49 rename_dst[first].two = two;
50 rename_dst[first].pair = NULL;
51 return &(rename_dst[first]);
427dcb4b
JH
52}
53
25d5ea41
JH
54static struct diff_rename_src {
55 struct diff_filespec *one;
56 unsigned src_used : 1;
57} *rename_src;
58static int rename_src_nr, rename_src_alloc;
427dcb4b 59
25d5ea41
JH
60static struct diff_rename_src *locate_rename_src(struct diff_filespec *one,
61 int insert_ok)
62{
63 int first, last;
64
65 first = 0;
66 last = rename_src_nr;
67 while (last > first) {
68 int next = (last + first) >> 1;
69 struct diff_rename_src *src = &(rename_src[next]);
70 int cmp = strcmp(one->path, src->one->path);
71 if (!cmp)
72 return src;
73 if (cmp < 0) {
74 last = next;
75 continue;
76 }
77 first = next+1;
78 }
79 /* not found */
80 if (!insert_ok)
81 return NULL;
82 /* insert to make it at "first" */
83 if (rename_src_alloc <= rename_src_nr) {
84 rename_src_alloc = alloc_nr(rename_src_alloc);
85 rename_src = xrealloc(rename_src,
86 rename_src_alloc * sizeof(*rename_src));
427dcb4b 87 }
25d5ea41
JH
88 rename_src_nr++;
89 if (first < rename_src_nr)
90 memmove(rename_src + first + 1, rename_src + first,
91 (rename_src_nr - first - 1) * sizeof(*rename_src));
92 rename_src[first].one = one;
93 rename_src[first].src_used = 0;
94 return &(rename_src[first]);
427dcb4b
JH
95}
96
97static int is_exact_match(struct diff_filespec *src, struct diff_filespec *dst)
98{
99 if (src->sha1_valid && dst->sha1_valid &&
100 !memcmp(src->sha1, dst->sha1, 20))
101 return 1;
102 if (diff_populate_filespec(src) || diff_populate_filespec(dst))
103 /* this is an error but will be caught downstream */
104 return 0;
105 if (src->size == dst->size &&
106 !memcmp(src->data, dst->data, src->size))
107 return 1;
108 return 0;
109}
110
111struct diff_score {
25d5ea41
JH
112 int src; /* index in rename_src */
113 int dst; /* index in rename_dst */
427dcb4b
JH
114 int score;
115 int rank;
116};
117
118static int estimate_similarity(struct diff_filespec *src,
119 struct diff_filespec *dst,
120 int minimum_score)
121{
122 /* src points at a file that existed in the original tree (or
123 * optionally a file in the destination tree) and dst points
124 * at a newly created file. They may be quite similar, in which
125 * case we want to say src is renamed to dst or src is copied into
126 * dst, and then some edit has been applied to dst.
127 *
128 * Compare them and return how similar they are, representing
129 * the score as an integer between 0 and 10000, except
130 * where they match exactly it is considered better than anything
131 * else.
132 */
133 void *delta;
58b103f5 134 unsigned long delta_size, base_size;
427dcb4b
JH
135 int score;
136
60896c7b
JH
137 /* We deal only with regular files. Symlink renames are handled
138 * only when they are exact matches --- in other words, no edits
139 * after renaming.
140 */
141 if (!S_ISREG(src->mode) || !S_ISREG(dst->mode))
142 return 0;
143
427dcb4b
JH
144 delta_size = ((src->size < dst->size) ?
145 (dst->size - src->size) : (src->size - dst->size));
58b103f5 146 base_size = ((src->size < dst->size) ? src->size : dst->size);
427dcb4b 147
58b103f5
JH
148 /* We would not consider edits that change the file size so
149 * drastically. delta_size must be smaller than
cd1870ed 150 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
58b103f5
JH
151 * Note that base_size == 0 case is handled here already
152 * and the final score computation below would not have a
153 * divide-by-zero issue.
427dcb4b 154 */
cd1870ed 155 if (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)
427dcb4b
JH
156 return 0;
157
158 delta = diff_delta(src->data, src->size,
159 dst->data, dst->size,
160 &delta_size);
58b103f5
JH
161 /*
162 * We currently punt here, but we may later end up parsing the
163 * delta to really assess the extent of damage. A big consecutive
164 * remove would produce small delta_size that affects quite a
165 * big portion of the file.
166 */
427dcb4b
JH
167 free(delta);
168
58b103f5
JH
169 /*
170 * Now we will give some score to it. 100% edit gets 0 points
171 * and 0% edit gets MAX_SCORE points.
427dcb4b 172 */
58b103f5 173 score = MAX_SCORE - (MAX_SCORE * delta_size / base_size);
427dcb4b
JH
174 if (score < 0) return 0;
175 if (MAX_SCORE < score) return MAX_SCORE;
176 return score;
177}
178
25d5ea41
JH
179static void record_rename_pair(struct diff_queue_struct *renq,
180 int dst_index, int src_index, int score)
427dcb4b 181{
25d5ea41
JH
182 struct diff_filespec *one, *two, *src, *dst;
183 struct diff_filepair *dp;
f7c1512a 184
25d5ea41
JH
185 if (rename_dst[dst_index].pair)
186 die("internal error: dst already matched.");
427dcb4b 187
25d5ea41
JH
188 src = rename_src[src_index].one;
189 one = alloc_filespec(src->path);
190 fill_filespec(one, src->sha1, src->mode);
427dcb4b 191
25d5ea41
JH
192 dst = rename_dst[dst_index].two;
193 two = alloc_filespec(dst->path);
194 fill_filespec(two, dst->sha1, dst->mode);
427dcb4b 195
25d5ea41
JH
196 dp = diff_queue(renq, one, two);
197 dp->score = score;
427dcb4b 198
25d5ea41
JH
199 rename_src[src_index].src_used = 1;
200 rename_dst[dst_index].pair = dp;
427dcb4b
JH
201}
202
203/*
204 * We sort the rename similarity matrix with the score, in descending
205 * order (more similar first).
206 */
207static int score_compare(const void *a_, const void *b_)
208{
209 const struct diff_score *a = a_, *b = b_;
210 return b->score - a->score;
211}
212
6b14d7fa
JH
213int diff_scoreopt_parse(const char *opt)
214{
215 int diglen, num, scale, i;
216 if (opt[0] != '-' || (opt[1] != 'M' && opt[1] != 'C'))
217 return -1; /* that is not a -M nor -C option */
218 diglen = strspn(opt+2, "0123456789");
219 if (diglen == 0 || strlen(opt+2) != diglen)
220 return 0; /* use default */
221 sscanf(opt+2, "%d", &num);
222 for (i = 0, scale = 1; i < diglen; i++)
223 scale *= 10;
224
225 /* user says num divided by scale and we say internally that
226 * is MAX_SCORE * num / scale.
227 */
228 return MAX_SCORE * num / scale;
229}
230
231void diffcore_rename(int detect_rename, int minimum_score)
427dcb4b 232{
38c6f780 233 struct diff_queue_struct *q = &diff_queued_diff;
25d5ea41 234 struct diff_queue_struct renq, outq;
427dcb4b 235 struct diff_score *mx;
25d5ea41
JH
236 int i, j;
237 int num_create, num_src, dst_cnt;
427dcb4b 238
26dee0ad
JH
239 if (!minimum_score)
240 minimum_score = DEFAULT_MINIMUM_SCORE;
25d5ea41
JH
241 renq.queue = NULL;
242 renq.nr = renq.alloc = 0;
427dcb4b 243
427dcb4b 244 for (i = 0; i < q->nr; i++) {
52e95789 245 struct diff_filepair *p = q->queue[i];
81e50eab
JH
246 if (!DIFF_FILE_VALID(p->one))
247 if (!DIFF_FILE_VALID(p->two))
60896c7b 248 continue; /* unmerged */
427dcb4b 249 else
25d5ea41 250 locate_rename_dst(p->two, 1);
81e50eab 251 else if (!DIFF_FILE_VALID(p->two))
25d5ea41 252 locate_rename_src(p->one, 1);
427dcb4b 253 else if (1 < detect_rename) /* find copy, too */
25d5ea41 254 locate_rename_src(p->one, 1);
427dcb4b 255 }
25d5ea41 256 if (rename_dst_nr == 0)
427dcb4b
JH
257 goto cleanup; /* nothing to do */
258
259 /* We really want to cull the candidates list early
260 * with cheap tests in order to avoid doing deltas.
427dcb4b 261 */
25d5ea41
JH
262 for (i = 0; i < rename_dst_nr; i++) {
263 struct diff_filespec *two = rename_dst[i].two;
264 for (j = 0; j < rename_src_nr; j++) {
265 struct diff_filespec *one = rename_src[j].one;
266 if (!is_exact_match(one, two))
267 continue;
268 record_rename_pair(&renq, i, j, MAX_SCORE);
269 break; /* we are done with this entry */
427dcb4b
JH
270 }
271 }
25d5ea41 272 diff_debug_queue("done detecting exact", &renq);
427dcb4b
JH
273
274 /* Have we run out the created file pool? If so we can avoid
275 * doing the delta matrix altogether.
276 */
25d5ea41 277 if (renq.nr == rename_dst_nr)
427dcb4b
JH
278 goto flush_rest;
279
25d5ea41
JH
280 num_create = (rename_dst_nr - renq.nr);
281 num_src = rename_src_nr;
427dcb4b 282 mx = xmalloc(sizeof(*mx) * num_create * num_src);
25d5ea41 283 for (dst_cnt = i = 0; i < rename_dst_nr; i++) {
427dcb4b 284 int base = dst_cnt * num_src;
25d5ea41
JH
285 struct diff_filespec *two = rename_dst[i].two;
286 if (rename_dst[i].pair)
427dcb4b 287 continue; /* dealt with exact match already. */
25d5ea41
JH
288 for (j = 0; j < rename_src_nr; j++) {
289 struct diff_filespec *one = rename_src[j].one;
290 struct diff_score *m = &mx[base+j];
291 m->src = j;
292 m->dst = i;
293 m->score = estimate_similarity(one, two,
294 minimum_score);
427dcb4b
JH
295 }
296 dst_cnt++;
297 }
298 /* cost matrix sorted by most to least similar pair */
299 qsort(mx, num_create * num_src, sizeof(*mx), score_compare);
300 for (i = 0; i < num_create * num_src; i++) {
25d5ea41
JH
301 struct diff_rename_dst *dst = &rename_dst[mx[i].dst];
302 if (dst->pair)
303 continue; /* already done, either exact or fuzzy. */
427dcb4b 304 if (mx[i].score < minimum_score)
58b103f5 305 break; /* there is not any more diffs applicable. */
25d5ea41 306 record_rename_pair(&renq, mx[i].dst, mx[i].src, mx[i].score);
427dcb4b
JH
307 }
308 free(mx);
25d5ea41 309 diff_debug_queue("done detecting fuzzy", &renq);
427dcb4b
JH
310
311 flush_rest:
312 /* At this point, we have found some renames and copies and they
25d5ea41 313 * are kept in renq. The original list is still in *q.
427dcb4b
JH
314 *
315 * Scan the original list and move them into the outq; we will sort
316 * outq and swap it into the queue supplied to pass that to
317 * downstream, so we assign the sort keys in this loop.
318 *
319 * See comments at the top of record_rename_pair for numbers used
f7c1512a 320 * to assign rename_rank.
427dcb4b 321 */
25d5ea41
JH
322 outq.queue = NULL;
323 outq.nr = outq.alloc = 0;
427dcb4b 324 for (i = 0; i < q->nr; i++) {
25d5ea41
JH
325 struct diff_filepair *p = q->queue[i];
326 struct diff_rename_src *src = locate_rename_src(p->one, 0);
327 struct diff_rename_dst *dst = locate_rename_dst(p->two, 0);
328 struct diff_filepair *pair_to_free = NULL;
329
330 if (dst) {
331 /* creation */
332 if (dst->pair) {
333 /* renq has rename/copy already to produce
334 * this file, so we do not emit the creation
335 * record in the output.
336 */
337 diff_q(&outq, dst->pair);
338 pair_to_free = p;
339 }
340 else
341 /* no matching rename/copy source, so record
342 * this as a creation.
343 */
344 diff_q(&outq, p);
427dcb4b 345 }
25d5ea41
JH
346 else if (!diff_unmodified_pair(p))
347 /* all the other cases need to be recorded as is */
348 diff_q(&outq, p);
427dcb4b 349 else {
25d5ea41
JH
350 /* unmodified pair needs to be recorded only if
351 * it is used as the source of rename/copy
352 */
353 if (src && src->src_used)
354 diff_q(&outq, p);
427dcb4b 355 else
25d5ea41 356 pair_to_free = p;
427dcb4b 357 }
25d5ea41
JH
358 if (pair_to_free) {
359 diff_free_filespec_data(pair_to_free->one);
360 diff_free_filespec_data(pair_to_free->two);
361 free(pair_to_free);
427dcb4b 362 }
427dcb4b 363 }
25d5ea41 364 diff_debug_queue("done copying original", &outq);
427dcb4b 365
25d5ea41
JH
366 free(renq.queue);
367 free(q->queue);
368 *q = outq;
369 diff_debug_queue("done collapsing", q);
427dcb4b
JH
370
371 cleanup:
25d5ea41
JH
372 free(rename_dst);
373 rename_dst = NULL;
374 rename_dst_nr = rename_dst_alloc = 0;
375 free(rename_src);
376 rename_src = NULL;
377 rename_src_nr = rename_src_alloc = 0;
427dcb4b
JH
378 return;
379}