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;/* no trees, please */ 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/* We deal only with regular files. Symlink renames are handled 75 * only when they are exact matches --- in other words, no edits 76 * after renaming. 77 */ 78if(!S_ISREG(src->mode) || !S_ISREG(dst->mode)) 79return0; 80 81 delta_size = ((src->size < dst->size) ? 82(dst->size - src->size) : (src->size - dst->size)); 83 base_size = ((src->size < dst->size) ? src->size : dst->size); 84 85/* We would not consider edits that change the file size so 86 * drastically. delta_size must be smaller than 87 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size). 88 * Note that base_size == 0 case is handled here already 89 * and the final score computation below would not have a 90 * divide-by-zero issue. 91 */ 92if(base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE) 93return0; 94 95 delta =diff_delta(src->data, src->size, 96 dst->data, dst->size, 97&delta_size); 98/* 99 * We currently punt here, but we may later end up parsing the 100 * delta to really assess the extent of damage. A big consecutive 101 * remove would produce small delta_size that affects quite a 102 * big portion of the file. 103 */ 104free(delta); 105 106/* 107 * Now we will give some score to it. 100% edit gets 0 points 108 * and 0% edit gets MAX_SCORE points. 109 */ 110 score = MAX_SCORE - (MAX_SCORE * delta_size / base_size); 111if(score <0)return0; 112if(MAX_SCORE < score)return MAX_SCORE; 113return score; 114} 115 116static voidrecord_rename_pair(struct diff_queue_struct *outq, 117struct diff_filespec *src, 118struct diff_filespec *dst, 119int rank, 120int score) 121{ 122/* 123 * These ranks are used to sort the final output, because there 124 * are certain dependencies: 125 * 126 * 1. rename/copy that depends on deleted ones. 127 * 2. deletions in the original. 128 * 3. rename/copy that depends on the pre-edit image of kept files. 129 * 4. additions, modifications and no-modifications in the original. 130 * 5. rename/copy that depends on the post-edit image of kept files 131 * (note that we currently do not detect such rename/copy). 132 * 133 * The downstream diffcore transformers are free to reorder 134 * the entries as long as they keep file pairs that has the 135 * same p->one->path in earlier rename_rank to appear before 136 * later ones. This ordering is used by the diff_flush() 137 * logic to tell renames from copies, and also used by the 138 * diffcore_prune() logic to omit unnecessary 139 * "no-modification" entries. 140 * 141 * To the final output routine, and in the diff-raw format 142 * output, a rename/copy that is based on a path that has a 143 * later entry that shares the same p->one->path and is not a 144 * deletion is a copy. Otherwise it is a rename. 145 */ 146 147struct diff_filepair *dp =diff_queue(outq, src, dst); 148 dp->rename_rank = rank *2+1; 149 dp->score = score; 150 dst->xfrm_flags |= RENAME_DST_MATCHED; 151} 152 153#if 0 154static voiddebug_filespec(struct diff_filespec *s,int x,const char*one) 155{ 156fprintf(stderr,"queue[%d]%s(%s)%s %06o%s\n", 157 x, one, 158 s->path, 159DIFF_FILE_VALID(s) ?"valid":"invalid", 160 s->mode, 161 s->sha1_valid ?sha1_to_hex(s->sha1) :""); 162fprintf(stderr,"queue[%d]%ssize%lu flags%d\n", 163 x, one, 164 s->size, s->xfrm_flags); 165} 166 167static voiddebug_filepair(const struct diff_filepair *p,int i) 168{ 169debug_filespec(p->one, i,"one"); 170debug_filespec(p->two, i,"two"); 171fprintf(stderr,"pair rank%d, orig order%d, score%d\n", 172 p->rename_rank, p->orig_order, p->score); 173} 174 175static voiddebug_queue(const char*msg,struct diff_queue_struct *q) 176{ 177int i; 178if(msg) 179fprintf(stderr,"%s\n", msg); 180fprintf(stderr,"q->nr =%d\n", q->nr); 181for(i =0; i < q->nr; i++) { 182struct diff_filepair *p = q->queue[i]; 183debug_filepair(p, i); 184} 185} 186#else 187#define debug_queue(a,b) do { ;/*nothing*/ } while(0) 188#endif 189 190/* 191 * We sort the outstanding diff entries according to the rank (see 192 * comment at the beginning of record_rename_pair) and tiebreak with 193 * the order in the original input. 194 */ 195static intrank_compare(const void*a_,const void*b_) 196{ 197const struct diff_filepair *a = *(const struct diff_filepair **)a_; 198const struct diff_filepair *b = *(const struct diff_filepair **)b_; 199int a_rank = a->rename_rank; 200int b_rank = b->rename_rank; 201 202if(a_rank != b_rank) 203return a_rank - b_rank; 204return a->orig_order - b->orig_order; 205} 206 207/* 208 * We sort the rename similarity matrix with the score, in descending 209 * order (more similar first). 210 */ 211static intscore_compare(const void*a_,const void*b_) 212{ 213const struct diff_score *a = a_, *b = b_; 214return b->score - a->score; 215} 216 217intdiff_scoreopt_parse(const char*opt) 218{ 219int diglen, num, scale, i; 220if(opt[0] !='-'|| (opt[1] !='M'&& opt[1] !='C')) 221return-1;/* that is not a -M nor -C option */ 222 diglen =strspn(opt+2,"0123456789"); 223if(diglen ==0||strlen(opt+2) != diglen) 224return0;/* use default */ 225sscanf(opt+2,"%d", &num); 226for(i =0, scale =1; i < diglen; i++) 227 scale *=10; 228 229/* user says num divided by scale and we say internally that 230 * is MAX_SCORE * num / scale. 231 */ 232return MAX_SCORE * num / scale; 233} 234 235voiddiffcore_rename(int detect_rename,int minimum_score) 236{ 237struct diff_queue_struct *q = &diff_queued_diff; 238struct diff_queue_struct outq; 239struct diff_rename_pool created, deleted, stay; 240struct diff_rename_pool *(srcs[2]); 241struct diff_score *mx; 242int h, i, j; 243int num_create, num_src, dst_cnt, src_cnt; 244 245if(!minimum_score) 246 minimum_score = DEFAULT_MINIMUM_SCORE; 247 outq.queue = NULL; 248 outq.nr = outq.alloc =0; 249 250diff_rename_pool_clear(&created); 251diff_rename_pool_clear(&deleted); 252diff_rename_pool_clear(&stay); 253 254 srcs[0] = &deleted; 255 srcs[1] = &stay; 256 257for(i =0; i < q->nr; i++) { 258struct diff_filepair *p = q->queue[i]; 259if(!DIFF_FILE_VALID(p->one)) 260if(!DIFF_FILE_VALID(p->two)) 261continue;/* unmerged */ 262else 263diff_rename_pool_add(&created, p->two); 264else if(!DIFF_FILE_VALID(p->two)) 265diff_rename_pool_add(&deleted, p->one); 266else if(1< detect_rename)/* find copy, too */ 267diff_rename_pool_add(&stay, p->one); 268} 269if(created.nr ==0) 270goto cleanup;/* nothing to do */ 271 272/* We really want to cull the candidates list early 273 * with cheap tests in order to avoid doing deltas. 274 * 275 * With the current callers, we should not have already 276 * matched entries at this point, but it is nonetheless 277 * checked for sanity. 278 */ 279for(i =0; i < created.nr; i++) { 280if(created.s[i]->xfrm_flags & RENAME_DST_MATCHED) 281continue;/* we have matched exactly already */ 282for(h =0; h <sizeof(srcs)/sizeof(srcs[0]); h++) { 283struct diff_rename_pool *p = srcs[h]; 284for(j =0; j < p->nr; j++) { 285if(!is_exact_match(p->s[j], created.s[i])) 286continue; 287record_rename_pair(&outq, 288 p->s[j], created.s[i], h, 289 MAX_SCORE); 290break;/* we are done with this entry */ 291} 292} 293} 294debug_queue("done detecting exact", &outq); 295 296/* Have we run out the created file pool? If so we can avoid 297 * doing the delta matrix altogether. 298 */ 299if(outq.nr == created.nr) 300goto flush_rest; 301 302 num_create = (created.nr - outq.nr); 303 num_src = deleted.nr + stay.nr; 304 mx =xmalloc(sizeof(*mx) * num_create * num_src); 305for(dst_cnt = i =0; i < created.nr; i++) { 306int base = dst_cnt * num_src; 307if(created.s[i]->xfrm_flags & RENAME_DST_MATCHED) 308continue;/* dealt with exact match already. */ 309for(src_cnt = h =0; h <sizeof(srcs)/sizeof(srcs[0]); h++) { 310struct diff_rename_pool *p = srcs[h]; 311for(j =0; j < p->nr; j++, src_cnt++) { 312struct diff_score *m = &mx[base + src_cnt]; 313 m->src = p->s[j]; 314 m->dst = created.s[i]; 315 m->score =estimate_similarity(m->src, m->dst, 316 minimum_score); 317 m->rank = h; 318} 319} 320 dst_cnt++; 321} 322/* cost matrix sorted by most to least similar pair */ 323qsort(mx, num_create * num_src,sizeof(*mx), score_compare); 324for(i =0; i < num_create * num_src; i++) { 325if(mx[i].dst->xfrm_flags & RENAME_DST_MATCHED) 326continue;/* alreayd done, either exact or fuzzy. */ 327if(mx[i].score < minimum_score) 328break;/* there is not any more diffs applicable. */ 329record_rename_pair(&outq, 330 mx[i].src, mx[i].dst, mx[i].rank, 331 mx[i].score); 332} 333free(mx); 334debug_queue("done detecting fuzzy", &outq); 335 336 flush_rest: 337/* At this point, we have found some renames and copies and they 338 * are kept in outq. The original list is still in *q. 339 * 340 * Scan the original list and move them into the outq; we will sort 341 * outq and swap it into the queue supplied to pass that to 342 * downstream, so we assign the sort keys in this loop. 343 * 344 * See comments at the top of record_rename_pair for numbers used 345 * to assign rename_rank. 346 */ 347for(i =0; i < q->nr; i++) { 348struct diff_filepair *dp, *p = q->queue[i]; 349if(!DIFF_FILE_VALID(p->one)) { 350/* creation or unmerged entries */ 351 dp =diff_queue(&outq, p->one, p->two); 352 dp->rename_rank =4; 353} 354else if(!DIFF_FILE_VALID(p->two)) { 355/* deletion */ 356 dp =diff_queue(&outq, p->one, p->two); 357 dp->rename_rank =2; 358} 359else{ 360/* modification, or stay as is */ 361 dp =diff_queue(&outq, p->one, p->two); 362 dp->rename_rank =4; 363} 364free(p); 365} 366debug_queue("done copying original", &outq); 367 368/* Sort outq */ 369qsort(outq.queue, outq.nr,sizeof(outq.queue[0]), rank_compare); 370 371debug_queue("done sorting", &outq); 372 373free(q->queue); 374 q->nr = q->alloc =0; 375 q->queue = NULL; 376 377/* Copy it out to q, removing duplicates. */ 378for(i =0; i < outq.nr; i++) { 379struct diff_filepair *p = outq.queue[i]; 380if(!DIFF_FILE_VALID(p->one)) { 381/* created or unmerged */ 382if(p->two->xfrm_flags & RENAME_DST_MATCHED) 383;/* rename/copy created it already */ 384else 385diff_queue(q, p->one, p->two); 386} 387else if(!DIFF_FILE_VALID(p->two)) { 388/* deleted */ 389if(p->one->xfrm_flags & RENAME_SRC_GONE) 390;/* rename/copy deleted it already */ 391else 392diff_queue(q, p->one, p->two); 393} 394else if(strcmp(p->one->path, p->two->path)) { 395/* rename or copy */ 396struct diff_filepair *dp = 397diff_queue(q, p->one, p->two); 398 dp->score = p->score; 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(!diff_needs_to_stay(&outq, i+1, p->one)) 405/* this is the last one, so mark it as gone. 406 */ 407 p->one->xfrm_flags |= RENAME_SRC_GONE; 408} 409else 410/* otherwise it is a modified (or "stay") entry */ 411diff_queue(q, p->one, p->two); 412free(p); 413} 414 415free(outq.queue); 416debug_queue("done collapsing", q); 417 418 cleanup: 419free(created.s); 420free(deleted.s); 421free(stay.s); 422return; 423}