2 * Copyright (C) 2005 Junio C Hamano
9 struct diff_rename_pool
{
10 struct diff_filespec
**s
;
14 static void diff_rename_pool_clear(struct diff_rename_pool
*pool
)
16 pool
->s
= NULL
; pool
->nr
= pool
->alloc
= 0;
19 static void diff_rename_pool_add(struct diff_rename_pool
*pool
,
20 struct diff_filespec
*s
)
23 return; /* rename/copy patch for tree does not make sense. */
25 if (pool
->alloc
<= pool
->nr
) {
26 pool
->alloc
= alloc_nr(pool
->alloc
);
27 pool
->s
= xrealloc(pool
->s
,
28 sizeof(*(pool
->s
)) * pool
->alloc
);
30 pool
->s
[pool
->nr
] = s
;
34 static int is_exact_match(struct diff_filespec
*src
, struct diff_filespec
*dst
)
36 if (src
->sha1_valid
&& dst
->sha1_valid
&&
37 !memcmp(src
->sha1
, dst
->sha1
, 20))
39 if (diff_populate_filespec(src
) || diff_populate_filespec(dst
))
40 /* this is an error but will be caught downstream */
42 if (src
->size
== dst
->size
&&
43 !memcmp(src
->data
, dst
->data
, src
->size
))
49 struct diff_filespec
*src
;
50 struct diff_filespec
*dst
;
55 static int estimate_similarity(struct diff_filespec
*src
,
56 struct diff_filespec
*dst
,
59 /* src points at a file that existed in the original tree (or
60 * optionally a file in the destination tree) and dst points
61 * at a newly created file. They may be quite similar, in which
62 * case we want to say src is renamed to dst or src is copied into
63 * dst, and then some edit has been applied to dst.
65 * Compare them and return how similar they are, representing
66 * the score as an integer between 0 and 10000, except
67 * where they match exactly it is considered better than anything
71 unsigned long delta_size
;
74 delta_size
= ((src
->size
< dst
->size
) ?
75 (dst
->size
- src
->size
) : (src
->size
- dst
->size
));
77 /* We would not consider rename followed by more than
78 * minimum_score/MAX_SCORE edits; that is, delta_size must be smaller
79 * than (src->size + dst->size)/2 * minimum_score/MAX_SCORE,
83 if ((src
->size
+dst
->size
)*minimum_score
< delta_size
*MAX_SCORE
*2)
86 delta
= diff_delta(src
->data
, src
->size
,
91 /* This "delta" is really xdiff with adler32 and all the
92 * overheads but it is a quick and dirty approximation.
94 * Now we will give some score to it. 100% edit gets
95 * 0 points and 0% edit gets MAX_SCORE points. That is, every
96 * 1/MAX_SCORE edit gets 1 point penalty. The amount of penalty is:
98 * (delta_size * 2 / (src->size + dst->size)) * MAX_SCORE
101 score
= MAX_SCORE
-(MAX_SCORE
*2*delta_size
/(src
->size
+dst
->size
));
102 if (score
< 0) return 0;
103 if (MAX_SCORE
< score
) return MAX_SCORE
;
107 static void record_rename_pair(struct diff_queue_struct
*outq
,
108 struct diff_filespec
*src
,
109 struct diff_filespec
*dst
,
113 /* The rank is used to sort the final output, because there
114 * are certain dependencies.
116 * - rank #0 depends on deleted ones.
117 * - rank #1 depends on kept files before they are modified.
118 * - rank #2 depends on kept files after they are modified;
119 * currently not used.
121 * Therefore, the final output order should be:
123 * 1. rank #0 rename/copy diffs.
124 * 2. deletions in the original.
125 * 3. rank #1 rename/copy diffs.
126 * 4. additions and modifications in the original.
127 * 5. rank #2 rename/copy diffs; currently not used.
129 * To achieve this sort order, we give xform_work the number
132 struct diff_filepair
*dp
= diff_queue(outq
, src
, dst
);
133 dp
->xfrm_work
= (rank
* 2 + 1) | (score
<<RENAME_SCORE_SHIFT
);
134 dst
->xfrm_flags
|= RENAME_DST_MATCHED
;
138 static void debug_filespec(struct diff_filespec
*s
, int x
, const char *one
)
140 fprintf(stderr
, "queue[%d] %s (%s) %s %06o %s\n",
143 s
->file_valid
? "valid" : "invalid",
145 s
->sha1_valid
? sha1_to_hex(s
->sha1
) : "");
146 fprintf(stderr
, "queue[%d] %s size %lu flags %d\n",
148 s
->size
, s
->xfrm_flags
);
151 static void debug_filepair(const struct diff_filepair
*p
, int i
)
153 debug_filespec(p
->one
, i
, "one");
154 debug_filespec(p
->two
, i
, "two");
155 fprintf(stderr
, "pair flags %d, orig order %d, score %d\n",
156 (p
->xfrm_work
& ((1<<RENAME_SCORE_SHIFT
) - 1)),
158 (p
->xfrm_work
>> RENAME_SCORE_SHIFT
));
161 static void debug_queue(const char *msg
, struct diff_queue_struct
*q
)
165 fprintf(stderr
, "%s\n", msg
);
166 fprintf(stderr
, "q->nr = %d\n", q
->nr
);
167 for (i
= 0; i
< q
->nr
; i
++) {
168 struct diff_filepair
*p
= q
->queue
[i
];
169 debug_filepair(p
, i
);
173 #define debug_queue(a,b) do { ; /*nothing*/ } while(0)
177 * We sort the outstanding diff entries according to the rank (see
178 * comment at the beginning of record_rename_pair) and tiebreak with
179 * the order in the original input.
181 static int rank_compare(const void *a_
, const void *b_
)
183 const struct diff_filepair
*a
= *(const struct diff_filepair
**)a_
;
184 const struct diff_filepair
*b
= *(const struct diff_filepair
**)b_
;
185 int a_rank
= a
->xfrm_work
& ((1<<RENAME_SCORE_SHIFT
) - 1);
186 int b_rank
= b
->xfrm_work
& ((1<<RENAME_SCORE_SHIFT
) - 1);
188 if (a_rank
!= b_rank
)
189 return a_rank
- b_rank
;
190 return a
->orig_order
- b
->orig_order
;
194 * We sort the rename similarity matrix with the score, in descending
195 * order (more similar first).
197 static int score_compare(const void *a_
, const void *b_
)
199 const struct diff_score
*a
= a_
, *b
= b_
;
200 return b
->score
- a
->score
;
203 static int needs_to_stay(struct diff_queue_struct
*q
, int i
,
204 struct diff_filespec
*it
)
206 /* If it will be used in later entry (either stay or used
207 * as the source of rename/copy), we need to copy, not rename.
210 struct diff_filepair
*p
= q
->queue
[i
++];
211 if (!p
->two
->file_valid
)
212 continue; /* removed is fine */
213 if (strcmp(p
->one
->path
, it
->path
))
214 continue; /* not relevant */
216 /* p has its src set to *it and it is not a delete;
217 * it will be used for in-place change or rename/copy,
218 * so we cannot rename it out.
225 void diff_detect_rename(struct diff_queue_struct
*q
,
229 struct diff_queue_struct outq
;
230 struct diff_rename_pool created
, deleted
, stay
;
231 struct diff_rename_pool
*(srcs
[2]);
232 struct diff_score
*mx
;
234 int num_create
, num_src
, dst_cnt
, src_cnt
;
237 outq
.nr
= outq
.alloc
= 0;
239 diff_rename_pool_clear(&created
);
240 diff_rename_pool_clear(&deleted
);
241 diff_rename_pool_clear(&stay
);
246 for (i
= 0; i
< q
->nr
; i
++) {
247 struct diff_filepair
*p
= q
->queue
[i
];
248 if (!p
->one
->file_valid
)
249 if (!p
->two
->file_valid
)
250 continue; /* ignore nonsense */
252 diff_rename_pool_add(&created
, p
->two
);
253 else if (!p
->two
->file_valid
)
254 diff_rename_pool_add(&deleted
, p
->one
);
255 else if (1 < detect_rename
) /* find copy, too */
256 diff_rename_pool_add(&stay
, p
->one
);
259 goto cleanup
; /* nothing to do */
261 /* We really want to cull the candidates list early
262 * with cheap tests in order to avoid doing deltas.
264 * With the current callers, we should not have already
265 * matched entries at this point, but it is nonetheless
266 * checked for sanity.
268 for (i
= 0; i
< created
.nr
; i
++) {
269 if (created
.s
[i
]->xfrm_flags
& RENAME_DST_MATCHED
)
270 continue; /* we have matched exactly already */
271 for (h
= 0; h
< sizeof(srcs
)/sizeof(srcs
[0]); h
++) {
272 struct diff_rename_pool
*p
= srcs
[h
];
273 for (j
= 0; j
< p
->nr
; j
++) {
274 if (!is_exact_match(p
->s
[j
], created
.s
[i
]))
276 record_rename_pair(&outq
,
277 p
->s
[j
], created
.s
[i
], h
,
279 break; /* we are done with this entry */
283 debug_queue("done detecting exact", &outq
);
285 /* Have we run out the created file pool? If so we can avoid
286 * doing the delta matrix altogether.
288 if (outq
.nr
== created
.nr
)
291 num_create
= (created
.nr
- outq
.nr
);
292 num_src
= deleted
.nr
+ stay
.nr
;
293 mx
= xmalloc(sizeof(*mx
) * num_create
* num_src
);
294 for (dst_cnt
= i
= 0; i
< created
.nr
; i
++) {
295 int base
= dst_cnt
* num_src
;
296 if (created
.s
[i
]->xfrm_flags
& RENAME_DST_MATCHED
)
297 continue; /* dealt with exact match already. */
298 for (src_cnt
= h
= 0; h
< sizeof(srcs
)/sizeof(srcs
[0]); h
++) {
299 struct diff_rename_pool
*p
= srcs
[h
];
300 for (j
= 0; j
< p
->nr
; j
++, src_cnt
++) {
301 struct diff_score
*m
= &mx
[base
+ src_cnt
];
303 m
->dst
= created
.s
[i
];
304 m
->score
= estimate_similarity(m
->src
, m
->dst
,
311 /* cost matrix sorted by most to least similar pair */
312 qsort(mx
, num_create
* num_src
, sizeof(*mx
), score_compare
);
313 for (i
= 0; i
< num_create
* num_src
; i
++) {
314 if (mx
[i
].dst
->xfrm_flags
& RENAME_DST_MATCHED
)
315 continue; /* alreayd done, either exact or fuzzy. */
316 if (mx
[i
].score
< minimum_score
)
318 record_rename_pair(&outq
,
319 mx
[i
].src
, mx
[i
].dst
, mx
[i
].rank
,
323 debug_queue("done detecting fuzzy", &outq
);
326 /* At this point, we have found some renames and copies and they
327 * are kept in outq. The original list is still in *q.
329 * Scan the original list and move them into the outq; we will sort
330 * outq and swap it into the queue supplied to pass that to
331 * downstream, so we assign the sort keys in this loop.
333 * See comments at the top of record_rename_pair for numbers used
334 * to assign xfrm_work.
336 * Note that we have not annotated the diff_filepair with any comment
337 * so there is nothing other than p to free.
339 for (i
= 0; i
< q
->nr
; i
++) {
340 struct diff_filepair
*dp
, *p
= q
->queue
[i
];
341 if (!p
->one
->file_valid
) {
342 if (p
->two
->file_valid
) {
344 dp
= diff_queue(&outq
, p
->one
, p
->two
);
347 /* otherwise it is a nonsense; just ignore it */
349 else if (!p
->two
->file_valid
) {
351 dp
= diff_queue(&outq
, p
->one
, p
->two
);
355 /* modification, or stay as is */
356 dp
= diff_queue(&outq
, p
->one
, p
->two
);
361 debug_queue("done copying original", &outq
);
364 qsort(outq
.queue
, outq
.nr
, sizeof(outq
.queue
[0]), rank_compare
);
366 debug_queue("done sorting", &outq
);
369 q
->nr
= q
->alloc
= 0;
372 /* Copy it out to q, removing duplicates. */
373 for (i
= 0; i
< outq
.nr
; i
++) {
374 struct diff_filepair
*p
= outq
.queue
[i
];
375 if (!p
->one
->file_valid
) {
377 if (p
->two
->xfrm_flags
& RENAME_DST_MATCHED
)
378 ; /* rename/copy created it already */
380 diff_queue(q
, p
->one
, p
->two
);
382 else if (!p
->two
->file_valid
) {
384 if (p
->one
->xfrm_flags
& RENAME_SRC_GONE
)
385 ; /* rename/copy deleted it already */
387 diff_queue(q
, p
->one
, p
->two
);
389 else if (strcmp(p
->one
->path
, p
->two
->path
)) {
391 struct diff_filepair
*dp
=
392 diff_queue(q
, p
->one
, p
->two
);
393 int msglen
= (strlen(p
->one
->path
) +
394 strlen(p
->two
->path
) + 100);
395 int score
= (p
->xfrm_work
>> RENAME_SCORE_SHIFT
);
396 dp
->xfrm_msg
= xmalloc(msglen
);
398 /* if we have a later entry that is a rename/copy
399 * that depends on p->one, then we copy here.
400 * otherwise we rename it.
402 if (needs_to_stay(&outq
, i
+1, p
->one
)) {
404 sprintf(dp
->xfrm_msg
,
405 "similarity index %d%%\n"
408 (int)(0.5 + score
* 100 / MAX_SCORE
),
409 p
->one
->path
, p
->two
->path
);
412 /* rename it, and mark it as gone. */
413 p
->one
->xfrm_flags
|= RENAME_SRC_GONE
;
414 sprintf(dp
->xfrm_msg
,
415 "similarity index %d%%\n"
418 (int)(0.5 + score
* 100 / MAX_SCORE
),
419 p
->one
->path
, p
->two
->path
);
423 /* otherwise it is a modified (or stayed) entry */
424 diff_queue(q
, p
->one
, p
->two
);
429 debug_queue("done collapsing", q
);