1/* 2 * Copyright (C) 2005 Junio C Hamano 3 */ 4#include"cache.h" 5#include"diff.h" 6#include"diffcore.h" 7 8/* Table of rename/copy destinations */ 9 10static struct diff_rename_dst { 11struct diff_filespec *two; 12struct diff_filepair *pair; 13} *rename_dst; 14static int rename_dst_nr, rename_dst_alloc; 15 16static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two, 17int insert_ok) 18{ 19int first, last; 20 21 first =0; 22 last = rename_dst_nr; 23while(last > first) { 24int next = (last + first) >>1; 25struct diff_rename_dst *dst = &(rename_dst[next]); 26int cmp =strcmp(two->path, dst->two->path); 27if(!cmp) 28return dst; 29if(cmp <0) { 30 last = next; 31continue; 32} 33 first = next+1; 34} 35/* not found */ 36if(!insert_ok) 37return NULL; 38/* insert to make it at "first" */ 39if(rename_dst_alloc <= rename_dst_nr) { 40 rename_dst_alloc =alloc_nr(rename_dst_alloc); 41 rename_dst =xrealloc(rename_dst, 42 rename_dst_alloc *sizeof(*rename_dst)); 43} 44 rename_dst_nr++; 45if(first < rename_dst_nr) 46memmove(rename_dst + first +1, rename_dst + first, 47(rename_dst_nr - first -1) *sizeof(*rename_dst)); 48 rename_dst[first].two =alloc_filespec(two->path); 49fill_filespec(rename_dst[first].two, two->sha1, two->mode); 50 rename_dst[first].pair = NULL; 51return&(rename_dst[first]); 52} 53 54/* Table of rename/copy src files */ 55static struct diff_rename_src { 56struct diff_filespec *one; 57unsigned src_path_left :1; 58} *rename_src; 59static int rename_src_nr, rename_src_alloc; 60 61static struct diff_rename_src *register_rename_src(struct diff_filespec *one, 62int src_path_left) 63{ 64int first, last; 65 66 first =0; 67 last = rename_src_nr; 68while(last > first) { 69int next = (last + first) >>1; 70struct diff_rename_src *src = &(rename_src[next]); 71int cmp =strcmp(one->path, src->one->path); 72if(!cmp) 73return src; 74if(cmp <0) { 75 last = next; 76continue; 77} 78 first = next+1; 79} 80 81/* insert to make it at "first" */ 82if(rename_src_alloc <= rename_src_nr) { 83 rename_src_alloc =alloc_nr(rename_src_alloc); 84 rename_src =xrealloc(rename_src, 85 rename_src_alloc *sizeof(*rename_src)); 86} 87 rename_src_nr++; 88if(first < rename_src_nr) 89memmove(rename_src + first +1, rename_src + first, 90(rename_src_nr - first -1) *sizeof(*rename_src)); 91 rename_src[first].one = one; 92 rename_src[first].src_path_left = src_path_left; 93return&(rename_src[first]); 94} 95 96static intis_exact_match(struct diff_filespec *src,struct diff_filespec *dst) 97{ 98if(src->sha1_valid && dst->sha1_valid && 99!memcmp(src->sha1, dst->sha1,20)) 100return1; 101if(diff_populate_filespec(src,1) ||diff_populate_filespec(dst,1)) 102return0; 103if(src->size != dst->size) 104return0; 105if(diff_populate_filespec(src,0) ||diff_populate_filespec(dst,0)) 106return0; 107if(src->size == dst->size && 108!memcmp(src->data, dst->data, src->size)) 109return1; 110return0; 111} 112 113struct diff_score { 114int src;/* index in rename_src */ 115int dst;/* index in rename_dst */ 116int score; 117}; 118 119static intestimate_similarity(struct diff_filespec *src, 120struct diff_filespec *dst, 121int minimum_score) 122{ 123/* src points at a file that existed in the original tree (or 124 * optionally a file in the destination tree) and dst points 125 * at a newly created file. They may be quite similar, in which 126 * case we want to say src is renamed to dst or src is copied into 127 * dst, and then some edit has been applied to dst. 128 * 129 * Compare them and return how similar they are, representing 130 * the score as an integer between 0 and MAX_SCORE. 131 * 132 * When there is an exact match, it is considered a better 133 * match than anything else; the destination does not even 134 * call into this function in that case. 135 */ 136unsigned long delta_size, base_size, src_copied, literal_added; 137unsigned long delta_limit; 138int score; 139 140/* We deal only with regular files. Symlink renames are handled 141 * only when they are exact matches --- in other words, no edits 142 * after renaming. 143 */ 144if(!S_ISREG(src->mode) || !S_ISREG(dst->mode)) 145return0; 146 147 delta_size = ((src->size < dst->size) ? 148(dst->size - src->size) : (src->size - dst->size)); 149 base_size = ((src->size < dst->size) ? src->size : dst->size); 150 151/* We would not consider edits that change the file size so 152 * drastically. delta_size must be smaller than 153 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size). 154 * 155 * Note that base_size == 0 case is handled here already 156 * and the final score computation below would not have a 157 * divide-by-zero issue. 158 */ 159if(base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE) 160return0; 161 162if(diff_populate_filespec(src,0) ||diff_populate_filespec(dst,0)) 163return0;/* error but caught downstream */ 164 165 166 delta_limit = base_size * (MAX_SCORE-minimum_score) / MAX_SCORE; 167if(diffcore_count_changes(src->data, src->size, 168 dst->data, dst->size, 169&src->cnt_data, &dst->cnt_data, 170 delta_limit, 171&src_copied, &literal_added)) 172return0; 173 174/* How similar are they? 175 * what percentage of material in dst are from source? 176 */ 177if(dst->size < src_copied) 178 score = MAX_SCORE; 179else if(!dst->size) 180 score =0;/* should not happen */ 181else 182 score = src_copied * MAX_SCORE / dst->size; 183return score; 184} 185 186static voidrecord_rename_pair(int dst_index,int src_index,int score) 187{ 188struct diff_filespec *one, *two, *src, *dst; 189struct diff_filepair *dp; 190 191if(rename_dst[dst_index].pair) 192die("internal error: dst already matched."); 193 194 src = rename_src[src_index].one; 195 one =alloc_filespec(src->path); 196fill_filespec(one, src->sha1, src->mode); 197 198 dst = rename_dst[dst_index].two; 199 two =alloc_filespec(dst->path); 200fill_filespec(two, dst->sha1, dst->mode); 201 202 dp =diff_queue(NULL, one, two); 203 dp->score = score; 204 dp->source_stays = rename_src[src_index].src_path_left; 205 rename_dst[dst_index].pair = dp; 206} 207 208/* 209 * We sort the rename similarity matrix with the score, in descending 210 * order (the most similar first). 211 */ 212static intscore_compare(const void*a_,const void*b_) 213{ 214const struct diff_score *a = a_, *b = b_; 215return b->score - a->score; 216} 217 218static intcompute_stays(struct diff_queue_struct *q, 219struct diff_filespec *one) 220{ 221int i; 222for(i =0; i < q->nr; i++) { 223struct diff_filepair *p = q->queue[i]; 224if(strcmp(one->path, p->two->path)) 225continue; 226if(DIFF_PAIR_RENAME(p)) { 227return0;/* something else is renamed into this */ 228} 229} 230return1; 231} 232 233voiddiffcore_rename(struct diff_options *options) 234{ 235int detect_rename = options->detect_rename; 236int minimum_score = options->rename_score; 237int rename_limit = options->rename_limit; 238struct diff_queue_struct *q = &diff_queued_diff; 239struct diff_queue_struct outq; 240struct diff_score *mx; 241int i, j, rename_count; 242int num_create, num_src, dst_cnt; 243 244if(!minimum_score) 245 minimum_score = DEFAULT_RENAME_SCORE; 246 rename_count =0; 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;/* unmerged */ 253else 254locate_rename_dst(p->two,1); 255else if(!DIFF_FILE_VALID(p->two)) { 256/* If the source is a broken "delete", and 257 * they did not really want to get broken, 258 * that means the source actually stays. 259 */ 260int stays = (p->broken_pair && !p->score); 261register_rename_src(p->one, stays); 262} 263else if(detect_rename == DIFF_DETECT_COPY) 264register_rename_src(p->one,1); 265} 266if(rename_dst_nr ==0|| rename_src_nr ==0|| 267(0< rename_limit && rename_limit < rename_dst_nr)) 268goto cleanup;/* nothing to do */ 269 270/* We really want to cull the candidates list early 271 * with cheap tests in order to avoid doing deltas. 272 */ 273for(i =0; i < rename_dst_nr; i++) { 274struct diff_filespec *two = rename_dst[i].two; 275for(j =0; j < rename_src_nr; j++) { 276struct diff_filespec *one = rename_src[j].one; 277if(!is_exact_match(one, two)) 278continue; 279record_rename_pair(i, j, MAX_SCORE); 280 rename_count++; 281break;/* we are done with this entry */ 282} 283} 284 285/* Have we run out the created file pool? If so we can avoid 286 * doing the delta matrix altogether. 287 */ 288if(rename_count == rename_dst_nr) 289goto cleanup; 290 291if(minimum_score == MAX_SCORE) 292goto cleanup; 293 294 num_create = (rename_dst_nr - rename_count); 295 num_src = rename_src_nr; 296 mx =xmalloc(sizeof(*mx) * num_create * num_src); 297for(dst_cnt = i =0; i < rename_dst_nr; i++) { 298int base = dst_cnt * num_src; 299struct diff_filespec *two = rename_dst[i].two; 300if(rename_dst[i].pair) 301continue;/* dealt with exact match already. */ 302for(j =0; j < rename_src_nr; j++) { 303struct diff_filespec *one = rename_src[j].one; 304struct diff_score *m = &mx[base+j]; 305 m->src = j; 306 m->dst = i; 307 m->score =estimate_similarity(one, two, 308 minimum_score); 309} 310free(two->cnt_data); 311 two->cnt_data = NULL; 312 dst_cnt++; 313} 314/* cost matrix sorted by most to least similar pair */ 315qsort(mx, num_create * num_src,sizeof(*mx), score_compare); 316for(i =0; i < num_create * num_src; i++) { 317struct diff_rename_dst *dst = &rename_dst[mx[i].dst]; 318if(dst->pair) 319continue;/* already done, either exact or fuzzy. */ 320if(mx[i].score < minimum_score) 321break;/* there is no more usable pair. */ 322record_rename_pair(mx[i].dst, mx[i].src, mx[i].score); 323 rename_count++; 324} 325free(mx); 326 327 cleanup: 328/* At this point, we have found some renames and copies and they 329 * are recorded in rename_dst. The original list is still in *q. 330 */ 331 outq.queue = NULL; 332 outq.nr = outq.alloc =0; 333for(i =0; i < q->nr; i++) { 334struct diff_filepair *p = q->queue[i]; 335struct diff_filepair *pair_to_free = NULL; 336 337if(!DIFF_FILE_VALID(p->one) &&DIFF_FILE_VALID(p->two)) { 338/* 339 * Creation 340 * 341 * We would output this create record if it has 342 * not been turned into a rename/copy already. 343 */ 344struct diff_rename_dst *dst = 345locate_rename_dst(p->two,0); 346if(dst && dst->pair) { 347diff_q(&outq, dst->pair); 348 pair_to_free = p; 349} 350else 351/* no matching rename/copy source, so 352 * record this as a creation. 353 */ 354diff_q(&outq, p); 355} 356else if(DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) { 357/* 358 * Deletion 359 * 360 * We would output this delete record if: 361 * 362 * (1) this is a broken delete and the counterpart 363 * broken create remains in the output; or 364 * (2) this is not a broken delete, and rename_dst 365 * does not have a rename/copy to move p->one->path 366 * out of existence. 367 * 368 * Otherwise, the counterpart broken create 369 * has been turned into a rename-edit; or 370 * delete did not have a matching create to 371 * begin with. 372 */ 373if(DIFF_PAIR_BROKEN(p)) { 374/* broken delete */ 375struct diff_rename_dst *dst = 376locate_rename_dst(p->one,0); 377if(dst && dst->pair) 378/* counterpart is now rename/copy */ 379 pair_to_free = p; 380} 381else{ 382for(j =0; j < rename_dst_nr; j++) { 383if(!rename_dst[j].pair) 384continue; 385if(strcmp(rename_dst[j].pair-> 386 one->path, 387 p->one->path)) 388continue; 389break; 390} 391if(j < rename_dst_nr) 392/* this path remains */ 393 pair_to_free = p; 394} 395 396if(pair_to_free) 397; 398else 399diff_q(&outq, p); 400} 401else if(!diff_unmodified_pair(p)) 402/* all the usual ones need to be kept */ 403diff_q(&outq, p); 404else 405/* no need to keep unmodified pairs */ 406 pair_to_free = p; 407 408if(pair_to_free) 409diff_free_filepair(pair_to_free); 410} 411diff_debug_queue("done copying original", &outq); 412 413free(q->queue); 414*q = outq; 415diff_debug_queue("done collapsing", q); 416 417/* We need to see which rename source really stays here; 418 * earlier we only checked if the path is left in the result, 419 * but even if a path remains in the result, if that is coming 420 * from copying something else on top of it, then the original 421 * source is lost and does not stay. 422 */ 423for(i =0; i < q->nr; i++) { 424struct diff_filepair *p = q->queue[i]; 425if(DIFF_PAIR_RENAME(p) && p->source_stays) { 426/* If one appears as the target of a rename-copy, 427 * then mark p->source_stays = 0; otherwise 428 * leave it as is. 429 */ 430 p->source_stays =compute_stays(q, p->one); 431} 432} 433 434for(i =0; i < rename_dst_nr; i++) { 435diff_free_filespec_data(rename_dst[i].two); 436free(rename_dst[i].two); 437} 438 439free(rename_dst); 440 rename_dst = NULL; 441 rename_dst_nr = rename_dst_alloc =0; 442free(rename_src); 443 rename_src = NULL; 444 rename_src_nr = rename_src_alloc =0; 445return; 446}