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
= 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
]);
56 /* Table of rename/copy src files */
57 static struct diff_rename_src
{
58 struct diff_filespec
*one
;
59 unsigned src_path_left
: 1;
61 static int rename_src_nr
, rename_src_alloc
;
63 static struct diff_rename_src
*register_rename_src(struct diff_filespec
*one
,
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
);
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
));
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
].src_path_left
= src_path_left
;
95 return &(rename_src
[first
]);
98 static int is_exact_match(struct diff_filespec
*src
, struct diff_filespec
*dst
)
100 if (src
->sha1_valid
&& dst
->sha1_valid
&&
101 !memcmp(src
->sha1
, dst
->sha1
, 20))
103 if (diff_populate_filespec(src
, 1) || diff_populate_filespec(dst
, 1))
105 if (src
->size
!= dst
->size
)
107 if (diff_populate_filespec(src
, 0) || diff_populate_filespec(dst
, 0))
109 if (src
->size
== dst
->size
&&
110 !memcmp(src
->data
, dst
->data
, src
->size
))
116 int src
; /* index in rename_src */
117 int dst
; /* index in rename_dst */
121 static int estimate_similarity(struct diff_filespec
*src
,
122 struct diff_filespec
*dst
,
125 /* src points at a file that existed in the original tree (or
126 * optionally a file in the destination tree) and dst points
127 * at a newly created file. They may be quite similar, in which
128 * case we want to say src is renamed to dst or src is copied into
129 * dst, and then some edit has been applied to dst.
131 * Compare them and return how similar they are, representing
132 * the score as an integer between 0 and MAX_SCORE.
134 * When there is an exact match, it is considered a better
135 * match than anything else; the destination does not even
136 * call into this function in that case.
139 unsigned long delta_size
, base_size
, src_copied
, literal_added
;
140 unsigned long delta_limit
;
143 /* We deal only with regular files. Symlink renames are handled
144 * only when they are exact matches --- in other words, no edits
147 if (!S_ISREG(src
->mode
) || !S_ISREG(dst
->mode
))
150 delta_size
= ((src
->size
< dst
->size
) ?
151 (dst
->size
- src
->size
) : (src
->size
- dst
->size
));
152 base_size
= ((src
->size
< dst
->size
) ? src
->size
: dst
->size
);
154 /* We would not consider edits that change the file size so
155 * drastically. delta_size must be smaller than
156 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
158 * Note that base_size == 0 case is handled here already
159 * and the final score computation below would not have a
160 * divide-by-zero issue.
162 if (base_size
* (MAX_SCORE
-minimum_score
) < delta_size
* MAX_SCORE
)
165 if (diff_populate_filespec(src
, 0) || diff_populate_filespec(dst
, 0))
166 return 0; /* error but caught downstream */
168 delta_limit
= base_size
* (MAX_SCORE
-minimum_score
) / MAX_SCORE
;
169 delta
= diff_delta(src
->data
, src
->size
,
170 dst
->data
, dst
->size
,
171 &delta_size
, delta_limit
);
173 /* If delta_limit is exceeded, we have too much differences */
176 /* A delta that has a lot of literal additions would have
177 * big delta_size no matter what else it does.
179 if (base_size
* (MAX_SCORE
-minimum_score
) < delta_size
* MAX_SCORE
)
182 /* Estimate the edit size by interpreting delta. */
183 if (count_delta(delta
, delta_size
, &src_copied
, &literal_added
)) {
189 /* Extent of damage */
190 if (src
->size
+ literal_added
< src_copied
)
193 delta_size
= (src
->size
- src_copied
) + literal_added
;
196 * Now we will give some score to it. 100% edit gets 0 points
197 * and 0% edit gets MAX_SCORE points.
199 score
= MAX_SCORE
- (MAX_SCORE
* delta_size
/ base_size
);
200 if (score
< 0) return 0;
201 if (MAX_SCORE
< score
) return MAX_SCORE
;
205 static void record_rename_pair(int dst_index
, int src_index
, int score
)
207 struct diff_filespec
*one
, *two
, *src
, *dst
;
208 struct diff_filepair
*dp
;
210 if (rename_dst
[dst_index
].pair
)
211 die("internal error: dst already matched.");
213 src
= rename_src
[src_index
].one
;
214 one
= alloc_filespec(src
->path
);
215 fill_filespec(one
, src
->sha1
, src
->mode
);
217 dst
= rename_dst
[dst_index
].two
;
218 two
= alloc_filespec(dst
->path
);
219 fill_filespec(two
, dst
->sha1
, dst
->mode
);
221 dp
= diff_queue(NULL
, one
, two
);
223 dp
->source_stays
= rename_src
[src_index
].src_path_left
;
224 rename_dst
[dst_index
].pair
= dp
;
228 * We sort the rename similarity matrix with the score, in descending
229 * order (the most similar first).
231 static int score_compare(const void *a_
, const void *b_
)
233 const struct diff_score
*a
= a_
, *b
= b_
;
234 return b
->score
- a
->score
;
237 static int compute_stays(struct diff_queue_struct
*q
,
238 struct diff_filespec
*one
)
241 for (i
= 0; i
< q
->nr
; i
++) {
242 struct diff_filepair
*p
= q
->queue
[i
];
243 if (strcmp(one
->path
, p
->two
->path
))
245 if (DIFF_PAIR_RENAME(p
)) {
246 return 0; /* something else is renamed into this */
252 void diffcore_rename(struct diff_options
*options
)
254 int detect_rename
= options
->detect_rename
;
255 int minimum_score
= options
->rename_score
;
256 int rename_limit
= options
->rename_limit
;
257 struct diff_queue_struct
*q
= &diff_queued_diff
;
258 struct diff_queue_struct outq
;
259 struct diff_score
*mx
;
260 int i
, j
, rename_count
;
261 int num_create
, num_src
, dst_cnt
;
264 minimum_score
= DEFAULT_RENAME_SCORE
;
267 for (i
= 0; i
< q
->nr
; i
++) {
268 struct diff_filepair
*p
= q
->queue
[i
];
269 if (!DIFF_FILE_VALID(p
->one
))
270 if (!DIFF_FILE_VALID(p
->two
))
271 continue; /* unmerged */
273 locate_rename_dst(p
->two
, 1);
274 else if (!DIFF_FILE_VALID(p
->two
)) {
275 /* If the source is a broken "delete", and
276 * they did not really want to get broken,
277 * that means the source actually stays.
279 int stays
= (p
->broken_pair
&& !p
->score
);
280 register_rename_src(p
->one
, stays
);
282 else if (detect_rename
== DIFF_DETECT_COPY
)
283 register_rename_src(p
->one
, 1);
285 if (rename_dst_nr
== 0 || rename_src_nr
== 0 ||
286 (0 < rename_limit
&& rename_limit
< rename_dst_nr
))
287 goto cleanup
; /* nothing to do */
289 /* We really want to cull the candidates list early
290 * with cheap tests in order to avoid doing deltas.
292 for (i
= 0; i
< rename_dst_nr
; i
++) {
293 struct diff_filespec
*two
= rename_dst
[i
].two
;
294 for (j
= 0; j
< rename_src_nr
; j
++) {
295 struct diff_filespec
*one
= rename_src
[j
].one
;
296 if (!is_exact_match(one
, two
))
298 record_rename_pair(i
, j
, MAX_SCORE
);
300 break; /* we are done with this entry */
304 /* Have we run out the created file pool? If so we can avoid
305 * doing the delta matrix altogether.
307 if (rename_count
== rename_dst_nr
)
310 if (minimum_score
== MAX_SCORE
)
313 num_create
= (rename_dst_nr
- rename_count
);
314 num_src
= rename_src_nr
;
315 mx
= xmalloc(sizeof(*mx
) * num_create
* num_src
);
316 for (dst_cnt
= i
= 0; i
< rename_dst_nr
; i
++) {
317 int base
= dst_cnt
* num_src
;
318 struct diff_filespec
*two
= rename_dst
[i
].two
;
319 if (rename_dst
[i
].pair
)
320 continue; /* dealt with exact match already. */
321 for (j
= 0; j
< rename_src_nr
; j
++) {
322 struct diff_filespec
*one
= rename_src
[j
].one
;
323 struct diff_score
*m
= &mx
[base
+j
];
326 m
->score
= estimate_similarity(one
, two
,
331 /* cost matrix sorted by most to least similar pair */
332 qsort(mx
, num_create
* num_src
, sizeof(*mx
), score_compare
);
333 for (i
= 0; i
< num_create
* num_src
; i
++) {
334 struct diff_rename_dst
*dst
= &rename_dst
[mx
[i
].dst
];
336 continue; /* already done, either exact or fuzzy. */
337 if (mx
[i
].score
< minimum_score
)
338 break; /* there is no more usable pair. */
339 record_rename_pair(mx
[i
].dst
, mx
[i
].src
, mx
[i
].score
);
345 /* At this point, we have found some renames and copies and they
346 * are recorded in rename_dst. The original list is still in *q.
349 outq
.nr
= outq
.alloc
= 0;
350 for (i
= 0; i
< q
->nr
; i
++) {
351 struct diff_filepair
*p
= q
->queue
[i
];
352 struct diff_filepair
*pair_to_free
= NULL
;
354 if (!DIFF_FILE_VALID(p
->one
) && DIFF_FILE_VALID(p
->two
)) {
358 * We would output this create record if it has
359 * not been turned into a rename/copy already.
361 struct diff_rename_dst
*dst
=
362 locate_rename_dst(p
->two
, 0);
363 if (dst
&& dst
->pair
) {
364 diff_q(&outq
, dst
->pair
);
368 /* no matching rename/copy source, so
369 * record this as a creation.
373 else if (DIFF_FILE_VALID(p
->one
) && !DIFF_FILE_VALID(p
->two
)) {
377 * We would output this delete record if:
379 * (1) this is a broken delete and the counterpart
380 * broken create remains in the output; or
381 * (2) this is not a broken delete, and rename_dst
382 * does not have a rename/copy to move p->one->path
385 * Otherwise, the counterpart broken create
386 * has been turned into a rename-edit; or
387 * delete did not have a matching create to
390 if (DIFF_PAIR_BROKEN(p
)) {
392 struct diff_rename_dst
*dst
=
393 locate_rename_dst(p
->one
, 0);
394 if (dst
&& dst
->pair
)
395 /* counterpart is now rename/copy */
399 for (j
= 0; j
< rename_dst_nr
; j
++) {
400 if (!rename_dst
[j
].pair
)
402 if (strcmp(rename_dst
[j
].pair
->
408 if (j
< rename_dst_nr
)
409 /* this path remains */
418 else if (!diff_unmodified_pair(p
))
419 /* all the usual ones need to be kept */
422 /* no need to keep unmodified pairs */
426 diff_free_filepair(pair_to_free
);
428 diff_debug_queue("done copying original", &outq
);
432 diff_debug_queue("done collapsing", q
);
434 /* We need to see which rename source really stays here;
435 * earlier we only checked if the path is left in the result,
436 * but even if a path remains in the result, if that is coming
437 * from copying something else on top of it, then the original
438 * source is lost and does not stay.
440 for (i
= 0; i
< q
->nr
; i
++) {
441 struct diff_filepair
*p
= q
->queue
[i
];
442 if (DIFF_PAIR_RENAME(p
) && p
->source_stays
) {
443 /* If one appears as the target of a rename-copy,
444 * then mark p->source_stays = 0; otherwise
447 p
->source_stays
= compute_stays(q
, p
->one
);
451 for (i
= 0; i
< rename_dst_nr
; i
++) {
452 diff_free_filespec_data(rename_dst
[i
].two
);
453 free(rename_dst
[i
].two
);
458 rename_dst_nr
= rename_dst_alloc
= 0;
461 rename_src_nr
= rename_src_alloc
= 0;