2 * Copyright (C) 2005 Junio C Hamano
8 #include "count-delta.h"
10 /* Table of rename/copy destinations */
12 static struct diff_rename_dst
{
13 struct diff_filespec
*two
;
14 struct diff_filepair
*pair
;
16 static int rename_dst_nr
, rename_dst_alloc
;
18 static struct diff_rename_dst
*locate_rename_dst(struct diff_filespec
*two
,
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
);
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
));
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
= two
;
51 rename_dst
[first
].pair
= NULL
;
52 return &(rename_dst
[first
]);
55 /* Table of rename/copy src files */
56 static struct diff_rename_src
{
57 struct diff_filespec
*one
;
58 unsigned src_stays
: 1;
60 static int rename_src_nr
, rename_src_alloc
;
62 static struct diff_rename_src
*register_rename_src(struct diff_filespec
*one
,
69 while (last
> first
) {
70 int next
= (last
+ first
) >> 1;
71 struct diff_rename_src
*src
= &(rename_src
[next
]);
72 int cmp
= strcmp(one
->path
, src
->one
->path
);
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
));
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_stays
= src_stays
;
94 return &(rename_src
[first
]);
97 static int is_exact_match(struct diff_filespec
*src
, struct diff_filespec
*dst
)
99 if (src
->sha1_valid
&& dst
->sha1_valid
&&
100 !memcmp(src
->sha1
, dst
->sha1
, 20))
102 if (diff_populate_filespec(src
, 1) || diff_populate_filespec(dst
, 1))
104 if (src
->size
!= dst
->size
)
106 if (diff_populate_filespec(src
, 0) || diff_populate_filespec(dst
, 0))
108 if (src
->size
== dst
->size
&&
109 !memcmp(src
->data
, dst
->data
, src
->size
))
115 int src
; /* index in rename_src */
116 int dst
; /* index in rename_dst */
120 static int estimate_similarity(struct diff_filespec
*src
,
121 struct diff_filespec
*dst
,
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.
130 * Compare them and return how similar they are, representing
131 * the score as an integer between 0 and MAX_SCORE.
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.
138 unsigned long delta_size
, base_size
, src_copied
, literal_added
;
141 /* We deal only with regular files. Symlink renames are handled
142 * only when they are exact matches --- in other words, no edits
145 if (!S_ISREG(src
->mode
) || !S_ISREG(dst
->mode
))
148 delta_size
= ((src
->size
< dst
->size
) ?
149 (dst
->size
- src
->size
) : (src
->size
- dst
->size
));
150 base_size
= ((src
->size
< dst
->size
) ? src
->size
: dst
->size
);
152 /* We would not consider edits that change the file size so
153 * drastically. delta_size must be smaller than
154 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
156 * Note that base_size == 0 case is handled here already
157 * and the final score computation below would not have a
158 * divide-by-zero issue.
160 if (base_size
* (MAX_SCORE
-minimum_score
) < delta_size
* MAX_SCORE
)
163 if (diff_populate_filespec(src
, 0) || diff_populate_filespec(dst
, 0))
164 return 0; /* error but caught downstream */
166 delta
= diff_delta(src
->data
, src
->size
,
167 dst
->data
, dst
->size
,
170 /* A delta that has a lot of literal additions would have
171 * big delta_size no matter what else it does.
173 if (base_size
* (MAX_SCORE
-minimum_score
) < delta_size
* MAX_SCORE
)
176 /* Estimate the edit size by interpreting delta. */
177 if (count_delta(delta
, delta_size
, &src_copied
, &literal_added
)) {
183 /* Extent of damage */
184 if (src
->size
+ literal_added
< src_copied
)
187 delta_size
= (src
->size
- src_copied
) + literal_added
;
190 * Now we will give some score to it. 100% edit gets 0 points
191 * and 0% edit gets MAX_SCORE points.
193 score
= MAX_SCORE
- (MAX_SCORE
* delta_size
/ base_size
);
194 if (score
< 0) return 0;
195 if (MAX_SCORE
< score
) return MAX_SCORE
;
199 static void record_rename_pair(struct diff_queue_struct
*renq
,
200 int dst_index
, int src_index
, int score
)
202 struct diff_filespec
*one
, *two
, *src
, *dst
;
203 struct diff_filepair
*dp
;
205 if (rename_dst
[dst_index
].pair
)
206 die("internal error: dst already matched.");
208 src
= rename_src
[src_index
].one
;
209 one
= alloc_filespec(src
->path
);
210 fill_filespec(one
, src
->sha1
, src
->mode
);
212 dst
= rename_dst
[dst_index
].two
;
213 two
= alloc_filespec(dst
->path
);
214 fill_filespec(two
, dst
->sha1
, dst
->mode
);
216 dp
= diff_queue(renq
, one
, two
);
218 dp
->source_stays
= rename_src
[src_index
].src_stays
;
219 rename_dst
[dst_index
].pair
= dp
;
223 * We sort the rename similarity matrix with the score, in descending
224 * order (the most similar first).
226 static int score_compare(const void *a_
, const void *b_
)
228 const struct diff_score
*a
= a_
, *b
= b_
;
229 return b
->score
- a
->score
;
232 int diff_scoreopt_parse(const char *opt
)
234 int diglen
, num
, scale
, i
;
235 if (opt
[0] != '-' || (opt
[1] != 'M' && opt
[1] != 'C' && opt
[1] != 'B'))
236 return -1; /* that is not a -M, -C nor -B option */
237 diglen
= strspn(opt
+2, "0123456789");
238 if (diglen
== 0 || strlen(opt
+2) != diglen
)
239 return 0; /* use default */
240 sscanf(opt
+2, "%d", &num
);
241 for (i
= 0, scale
= 1; i
< diglen
; i
++)
244 /* user says num divided by scale and we say internally that
245 * is MAX_SCORE * num / scale.
247 return MAX_SCORE
* num
/ scale
;
250 void diffcore_rename(int detect_rename
, int minimum_score
)
252 struct diff_queue_struct
*q
= &diff_queued_diff
;
253 struct diff_queue_struct renq
, outq
;
254 struct diff_score
*mx
;
256 int num_create
, num_src
, dst_cnt
;
259 minimum_score
= DEFAULT_RENAME_SCORE
;
261 renq
.nr
= renq
.alloc
= 0;
263 for (i
= 0; i
< q
->nr
; i
++) {
264 struct diff_filepair
*p
= q
->queue
[i
];
265 if (!DIFF_FILE_VALID(p
->one
))
266 if (!DIFF_FILE_VALID(p
->two
))
267 continue; /* unmerged */
269 locate_rename_dst(p
->two
, 1);
270 else if (!DIFF_FILE_VALID(p
->two
))
271 register_rename_src(p
->one
, 0);
272 else if (detect_rename
== DIFF_DETECT_COPY
)
273 register_rename_src(p
->one
, 1);
275 if (rename_dst_nr
== 0)
276 goto cleanup
; /* nothing to do */
278 /* We really want to cull the candidates list early
279 * with cheap tests in order to avoid doing deltas.
281 for (i
= 0; i
< rename_dst_nr
; i
++) {
282 struct diff_filespec
*two
= rename_dst
[i
].two
;
283 for (j
= 0; j
< rename_src_nr
; j
++) {
284 struct diff_filespec
*one
= rename_src
[j
].one
;
285 if (!is_exact_match(one
, two
))
287 record_rename_pair(&renq
, i
, j
, MAX_SCORE
);
288 break; /* we are done with this entry */
291 diff_debug_queue("done detecting exact", &renq
);
293 /* Have we run out the created file pool? If so we can avoid
294 * doing the delta matrix altogether.
296 if (renq
.nr
== rename_dst_nr
)
299 num_create
= (rename_dst_nr
- renq
.nr
);
300 num_src
= rename_src_nr
;
301 mx
= xmalloc(sizeof(*mx
) * num_create
* num_src
);
302 for (dst_cnt
= i
= 0; i
< rename_dst_nr
; i
++) {
303 int base
= dst_cnt
* num_src
;
304 struct diff_filespec
*two
= rename_dst
[i
].two
;
305 if (rename_dst
[i
].pair
)
306 continue; /* dealt with exact match already. */
307 for (j
= 0; j
< rename_src_nr
; j
++) {
308 struct diff_filespec
*one
= rename_src
[j
].one
;
309 struct diff_score
*m
= &mx
[base
+j
];
312 m
->score
= estimate_similarity(one
, two
,
317 /* cost matrix sorted by most to least similar pair */
318 qsort(mx
, num_create
* num_src
, sizeof(*mx
), score_compare
);
319 for (i
= 0; i
< num_create
* num_src
; i
++) {
320 struct diff_rename_dst
*dst
= &rename_dst
[mx
[i
].dst
];
322 continue; /* already done, either exact or fuzzy. */
323 if (mx
[i
].score
< minimum_score
)
324 break; /* there is no more usable pair. */
325 record_rename_pair(&renq
, mx
[i
].dst
, mx
[i
].src
, mx
[i
].score
);
328 diff_debug_queue("done detecting fuzzy", &renq
);
331 /* At this point, we have found some renames and copies and they
332 * are kept in renq. The original list is still in *q.
335 outq
.nr
= outq
.alloc
= 0;
336 for (i
= 0; i
< q
->nr
; i
++) {
337 struct diff_filepair
*p
= q
->queue
[i
];
338 struct diff_filepair
*pair_to_free
= NULL
;
340 if (!DIFF_FILE_VALID(p
->one
) && DIFF_FILE_VALID(p
->two
)) {
344 * We would output this create record if it has
345 * not been turned into a rename/copy already.
347 struct diff_rename_dst
*dst
=
348 locate_rename_dst(p
->two
, 0);
349 if (dst
&& dst
->pair
) {
350 diff_q(&outq
, dst
->pair
);
354 /* no matching rename/copy source, so
355 * record this as a creation.
359 else if (DIFF_FILE_VALID(p
->one
) && !DIFF_FILE_VALID(p
->two
)) {
363 * We would output this delete record if:
365 * (1) this is a broken delete and the counterpart
366 * broken create remains in the output; or
367 * (2) this is not a broken delete, and renq does
368 * not have a rename/copy to move p->one->path
371 * Otherwise, the counterpart broken create
372 * has been turned into a rename-edit; or
373 * delete did not have a matching create to
376 if (DIFF_PAIR_BROKEN(p
)) {
378 struct diff_rename_dst
*dst
=
379 locate_rename_dst(p
->one
, 0);
380 if (dst
&& dst
->pair
)
381 /* counterpart is now rename/copy */
385 for (j
= 0; j
< renq
.nr
; j
++)
386 if (!strcmp(renq
.queue
[j
]->one
->path
,
390 /* this path remains */
399 else if (!diff_unmodified_pair(p
))
400 /* all the usual ones need to be kept */
403 /* no need to keep unmodified pairs */
407 diff_free_filepair(pair_to_free
);
409 diff_debug_queue("done copying original", &outq
);
414 diff_debug_queue("done collapsing", q
);
418 rename_dst_nr
= rename_dst_alloc
= 0;
421 rename_src_nr
= rename_src_alloc
= 0;