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 9struct diff_rename_pool { 10struct diff_filespec **s; 11int nr, alloc; 12}; 13 14static voiddiff_rename_pool_clear(struct diff_rename_pool *pool) 15{ 16 pool->s = NULL; pool->nr = pool->alloc =0; 17} 18 19static voiddiff_rename_pool_add(struct diff_rename_pool *pool, 20struct diff_filespec *s) 21{ 22if(S_ISDIR(s->mode)) 23return;/* rename/copy patch for tree does not make sense. */ 24 25if(pool->alloc <= pool->nr) { 26 pool->alloc =alloc_nr(pool->alloc); 27 pool->s =xrealloc(pool->s, 28sizeof(*(pool->s)) * pool->alloc); 29} 30 pool->s[pool->nr] = s; 31 pool->nr++; 32} 33 34static intis_exact_match(struct diff_filespec *src,struct diff_filespec *dst) 35{ 36if(src->sha1_valid && dst->sha1_valid && 37!memcmp(src->sha1, dst->sha1,20)) 38return1; 39if(diff_populate_filespec(src) ||diff_populate_filespec(dst)) 40/* this is an error but will be caught downstream */ 41return0; 42if(src->size == dst->size && 43!memcmp(src->data, dst->data, src->size)) 44return1; 45return0; 46} 47 48struct diff_score { 49struct diff_filespec *src; 50struct diff_filespec *dst; 51int score; 52int rank; 53}; 54 55static intestimate_similarity(struct diff_filespec *src, 56struct diff_filespec *dst, 57int minimum_score) 58{ 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. 64 * 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 68 * else. 69 */ 70void*delta; 71unsigned long delta_size, base_size; 72int score; 73 74 delta_size = ((src->size < dst->size) ? 75(dst->size - src->size) : (src->size - dst->size)); 76 base_size = ((src->size < dst->size) ? src->size : dst->size); 77 78/* We would not consider edits that change the file size so 79 * drastically. delta_size must be smaller than 80 * minimum_score/MAX_SCORE * min(src->size, dst->size). 81 * Note that base_size == 0 case is handled here already 82 * and the final score computation below would not have a 83 * divide-by-zero issue. 84 */ 85if(base_size * minimum_score < delta_size * MAX_SCORE) 86return0; 87 88 delta =diff_delta(src->data, src->size, 89 dst->data, dst->size, 90&delta_size); 91/* 92 * We currently punt here, but we may later end up parsing the 93 * delta to really assess the extent of damage. A big consecutive 94 * remove would produce small delta_size that affects quite a 95 * big portion of the file. 96 */ 97free(delta); 98 99/* 100 * Now we will give some score to it. 100% edit gets 0 points 101 * and 0% edit gets MAX_SCORE points. 102 */ 103 score = MAX_SCORE - (MAX_SCORE * delta_size / base_size); 104if(score <0)return0; 105if(MAX_SCORE < score)return MAX_SCORE; 106return score; 107} 108 109static voidrecord_rename_pair(struct diff_queue_struct *outq, 110struct diff_filespec *src, 111struct diff_filespec *dst, 112int rank, 113int score) 114{ 115/* The rank is used to sort the final output, because there 116 * are certain dependencies. 117 * 118 * - rank #0 depends on deleted ones. 119 * - rank #1 depends on kept files before they are modified. 120 * - rank #2 depends on kept files after they are modified; 121 * currently not used. 122 * 123 * Therefore, the final output order should be: 124 * 125 * 1. rank #0 rename/copy diffs. 126 * 2. deletions in the original. 127 * 3. rank #1 rename/copy diffs. 128 * 4. additions and modifications in the original. 129 * 5. rank #2 rename/copy diffs; currently not used. 130 * 131 * To achieve this sort order, we give xform_work the number 132 * above. 133 */ 134struct diff_filepair *dp =diff_queue(outq, src, dst); 135 dp->xfrm_work = (rank *2+1) | (score<<RENAME_SCORE_SHIFT); 136 dst->xfrm_flags |= RENAME_DST_MATCHED; 137} 138 139#if 0 140static voiddebug_filespec(struct diff_filespec *s,int x,const char*one) 141{ 142fprintf(stderr,"queue[%d]%s(%s)%s %06o%s\n", 143 x, one, 144 s->path, 145DIFF_FILE_VALID(s) ?"valid":"invalid", 146 s->mode, 147 s->sha1_valid ?sha1_to_hex(s->sha1) :""); 148fprintf(stderr,"queue[%d]%ssize%lu flags%d\n", 149 x, one, 150 s->size, s->xfrm_flags); 151} 152 153static voiddebug_filepair(const struct diff_filepair *p,int i) 154{ 155debug_filespec(p->one, i,"one"); 156debug_filespec(p->two, i,"two"); 157fprintf(stderr,"pair flags%d, orig order%d, score%d\n", 158(p->xfrm_work & ((1<<RENAME_SCORE_SHIFT) -1)), 159 p->orig_order, 160(p->xfrm_work >> RENAME_SCORE_SHIFT)); 161} 162 163static voiddebug_queue(const char*msg,struct diff_queue_struct *q) 164{ 165int i; 166if(msg) 167fprintf(stderr,"%s\n", msg); 168fprintf(stderr,"q->nr =%d\n", q->nr); 169for(i =0; i < q->nr; i++) { 170struct diff_filepair *p = q->queue[i]; 171debug_filepair(p, i); 172} 173} 174#else 175#define debug_queue(a,b) do { ;/*nothing*/ } while(0) 176#endif 177 178/* 179 * We sort the outstanding diff entries according to the rank (see 180 * comment at the beginning of record_rename_pair) and tiebreak with 181 * the order in the original input. 182 */ 183static intrank_compare(const void*a_,const void*b_) 184{ 185const struct diff_filepair *a = *(const struct diff_filepair **)a_; 186const struct diff_filepair *b = *(const struct diff_filepair **)b_; 187int a_rank = a->xfrm_work & ((1<<RENAME_SCORE_SHIFT) -1); 188int b_rank = b->xfrm_work & ((1<<RENAME_SCORE_SHIFT) -1); 189 190if(a_rank != b_rank) 191return a_rank - b_rank; 192return a->orig_order - b->orig_order; 193} 194 195/* 196 * We sort the rename similarity matrix with the score, in descending 197 * order (more similar first). 198 */ 199static intscore_compare(const void*a_,const void*b_) 200{ 201const struct diff_score *a = a_, *b = b_; 202return b->score - a->score; 203} 204 205static intneeds_to_stay(struct diff_queue_struct *q,int i, 206struct diff_filespec *it) 207{ 208/* If it will be used in later entry (either stay or used 209 * as the source of rename/copy), we need to copy, not rename. 210 */ 211while(i < q->nr) { 212struct diff_filepair *p = q->queue[i++]; 213if(!DIFF_FILE_VALID(p->two)) 214continue;/* removed is fine */ 215if(strcmp(p->one->path, it->path)) 216continue;/* not relevant */ 217 218/* p has its src set to *it and it is not a delete; 219 * it will be used for in-place change or rename/copy, 220 * so we cannot rename it out. 221 */ 222return1; 223} 224return0; 225} 226 227voiddiff_detect_rename(int detect_rename, 228int minimum_score) 229{ 230struct diff_queue_struct *q = &diff_queued_diff; 231struct diff_queue_struct outq; 232struct diff_rename_pool created, deleted, stay; 233struct diff_rename_pool *(srcs[2]); 234struct diff_score *mx; 235int h, i, j; 236int num_create, num_src, dst_cnt, src_cnt; 237 238 outq.queue = NULL; 239 outq.nr = outq.alloc =0; 240 241diff_rename_pool_clear(&created); 242diff_rename_pool_clear(&deleted); 243diff_rename_pool_clear(&stay); 244 245 srcs[0] = &deleted; 246 srcs[1] = &stay; 247 248for(i =0; i < q->nr; i++) { 249struct diff_filepair *p = q->queue[i]; 250if(!DIFF_FILE_VALID(p->one)) 251if(!DIFF_FILE_VALID(p->two)) 252continue;/* ignore nonsense */ 253else 254diff_rename_pool_add(&created, p->two); 255else if(!DIFF_FILE_VALID(p->two)) 256diff_rename_pool_add(&deleted, p->one); 257else if(1< detect_rename)/* find copy, too */ 258diff_rename_pool_add(&stay, p->one); 259} 260if(created.nr ==0) 261goto cleanup;/* nothing to do */ 262 263/* We really want to cull the candidates list early 264 * with cheap tests in order to avoid doing deltas. 265 * 266 * With the current callers, we should not have already 267 * matched entries at this point, but it is nonetheless 268 * checked for sanity. 269 */ 270for(i =0; i < created.nr; i++) { 271if(created.s[i]->xfrm_flags & RENAME_DST_MATCHED) 272continue;/* we have matched exactly already */ 273for(h =0; h <sizeof(srcs)/sizeof(srcs[0]); h++) { 274struct diff_rename_pool *p = srcs[h]; 275for(j =0; j < p->nr; j++) { 276if(!is_exact_match(p->s[j], created.s[i])) 277continue; 278record_rename_pair(&outq, 279 p->s[j], created.s[i], h, 280 MAX_SCORE); 281break;/* we are done with this entry */ 282} 283} 284} 285debug_queue("done detecting exact", &outq); 286 287/* Have we run out the created file pool? If so we can avoid 288 * doing the delta matrix altogether. 289 */ 290if(outq.nr == created.nr) 291goto flush_rest; 292 293 num_create = (created.nr - outq.nr); 294 num_src = deleted.nr + stay.nr; 295 mx =xmalloc(sizeof(*mx) * num_create * num_src); 296for(dst_cnt = i =0; i < created.nr; i++) { 297int base = dst_cnt * num_src; 298if(created.s[i]->xfrm_flags & RENAME_DST_MATCHED) 299continue;/* dealt with exact match already. */ 300for(src_cnt = h =0; h <sizeof(srcs)/sizeof(srcs[0]); h++) { 301struct diff_rename_pool *p = srcs[h]; 302for(j =0; j < p->nr; j++, src_cnt++) { 303struct diff_score *m = &mx[base + src_cnt]; 304 m->src = p->s[j]; 305 m->dst = created.s[i]; 306 m->score =estimate_similarity(m->src, m->dst, 307 minimum_score); 308 m->rank = h; 309} 310} 311 dst_cnt++; 312} 313/* cost matrix sorted by most to least similar pair */ 314qsort(mx, num_create * num_src,sizeof(*mx), score_compare); 315for(i =0; i < num_create * num_src; i++) { 316if(mx[i].dst->xfrm_flags & RENAME_DST_MATCHED) 317continue;/* alreayd done, either exact or fuzzy. */ 318if(mx[i].score < minimum_score) 319break;/* there is not any more diffs applicable. */ 320record_rename_pair(&outq, 321 mx[i].src, mx[i].dst, mx[i].rank, 322 mx[i].score); 323} 324free(mx); 325debug_queue("done detecting fuzzy", &outq); 326 327 flush_rest: 328/* At this point, we have found some renames and copies and they 329 * are kept in outq. The original list is still in *q. 330 * 331 * Scan the original list and move them into the outq; we will sort 332 * outq and swap it into the queue supplied to pass that to 333 * downstream, so we assign the sort keys in this loop. 334 * 335 * See comments at the top of record_rename_pair for numbers used 336 * to assign xfrm_work. 337 * 338 * Note that we have not annotated the diff_filepair with any comment 339 * so there is nothing other than p to free. 340 */ 341for(i =0; i < q->nr; i++) { 342struct diff_filepair *dp, *p = q->queue[i]; 343if(!DIFF_FILE_VALID(p->one)) { 344if(DIFF_FILE_VALID(p->two)) { 345/* creation */ 346 dp =diff_queue(&outq, p->one, p->two); 347 dp->xfrm_work =4; 348} 349/* otherwise it is a nonsense; just ignore it */ 350} 351else if(!DIFF_FILE_VALID(p->two)) { 352/* deletion */ 353 dp =diff_queue(&outq, p->one, p->two); 354 dp->xfrm_work =2; 355} 356else{ 357/* modification, or stay as is */ 358 dp =diff_queue(&outq, p->one, p->two); 359 dp->xfrm_work =4; 360} 361free(p); 362} 363debug_queue("done copying original", &outq); 364 365/* Sort outq */ 366qsort(outq.queue, outq.nr,sizeof(outq.queue[0]), rank_compare); 367 368debug_queue("done sorting", &outq); 369 370free(q->queue); 371 q->nr = q->alloc =0; 372 q->queue = NULL; 373 374/* Copy it out to q, removing duplicates. */ 375for(i =0; i < outq.nr; i++) { 376struct diff_filepair *p = outq.queue[i]; 377if(!DIFF_FILE_VALID(p->one)) { 378/* created */ 379if(p->two->xfrm_flags & RENAME_DST_MATCHED) 380;/* rename/copy created it already */ 381else 382diff_queue(q, p->one, p->two); 383} 384else if(!DIFF_FILE_VALID(p->two)) { 385/* deleted */ 386if(p->one->xfrm_flags & RENAME_SRC_GONE) 387;/* rename/copy deleted it already */ 388else 389diff_queue(q, p->one, p->two); 390} 391else if(strcmp(p->one->path, p->two->path)) { 392/* rename or copy */ 393struct diff_filepair *dp = 394diff_queue(q, p->one, p->two); 395int msglen = (strlen(p->one->path) + 396strlen(p->two->path) +100); 397int score = (p->xfrm_work >> RENAME_SCORE_SHIFT); 398 dp->xfrm_msg =xmalloc(msglen); 399 400/* if we have a later entry that is a rename/copy 401 * that depends on p->one, then we copy here. 402 * otherwise we rename it. 403 */ 404if(needs_to_stay(&outq, i+1, p->one)) { 405/* copy it */ 406sprintf(dp->xfrm_msg, 407"similarity index%d%%\n" 408"copy from%s\n" 409"copy to%s\n", 410(int)(0.5+ score *100/ MAX_SCORE), 411 p->one->path, p->two->path); 412} 413else{ 414/* rename it, and mark it as gone. */ 415 p->one->xfrm_flags |= RENAME_SRC_GONE; 416sprintf(dp->xfrm_msg, 417"similarity index%d%%\n" 418"rename old%s\n" 419"rename new%s\n", 420(int)(0.5+ score *100/ MAX_SCORE), 421 p->one->path, p->two->path); 422} 423} 424else 425/* otherwise it is a modified (or stayed) entry */ 426diff_queue(q, p->one, p->two); 427free(p); 428} 429 430free(outq.queue); 431debug_queue("done collapsing", q); 432 433 cleanup: 434free(created.s); 435free(deleted.s); 436free(stay.s); 437return; 438}