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 delta_limit, 170&src_copied, &literal_added)) 171return0; 172 173/* How similar are they? 174 * what percentage of material in dst are from source? 175 */ 176if(dst->size < src_copied) 177 score = MAX_SCORE; 178else if(!dst->size) 179 score =0;/* should not happen */ 180else 181 score = src_copied * MAX_SCORE / dst->size; 182return score; 183} 184 185static voidrecord_rename_pair(int dst_index,int src_index,int score) 186{ 187struct diff_filespec *one, *two, *src, *dst; 188struct diff_filepair *dp; 189 190if(rename_dst[dst_index].pair) 191die("internal error: dst already matched."); 192 193 src = rename_src[src_index].one; 194 one =alloc_filespec(src->path); 195fill_filespec(one, src->sha1, src->mode); 196 197 dst = rename_dst[dst_index].two; 198 two =alloc_filespec(dst->path); 199fill_filespec(two, dst->sha1, dst->mode); 200 201 dp =diff_queue(NULL, one, two); 202 dp->score = score; 203 dp->source_stays = rename_src[src_index].src_path_left; 204 rename_dst[dst_index].pair = dp; 205} 206 207/* 208 * We sort the rename similarity matrix with the score, in descending 209 * order (the most 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 217static intcompute_stays(struct diff_queue_struct *q, 218struct diff_filespec *one) 219{ 220int i; 221for(i =0; i < q->nr; i++) { 222struct diff_filepair *p = q->queue[i]; 223if(strcmp(one->path, p->two->path)) 224continue; 225if(DIFF_PAIR_RENAME(p)) { 226return0;/* something else is renamed into this */ 227} 228} 229return1; 230} 231 232voiddiffcore_rename(struct diff_options *options) 233{ 234int detect_rename = options->detect_rename; 235int minimum_score = options->rename_score; 236int rename_limit = options->rename_limit; 237struct diff_queue_struct *q = &diff_queued_diff; 238struct diff_queue_struct outq; 239struct diff_score *mx; 240int i, j, rename_count; 241int num_create, num_src, dst_cnt; 242 243if(!minimum_score) 244 minimum_score = DEFAULT_RENAME_SCORE; 245 rename_count =0; 246 247for(i =0; i < q->nr; i++) { 248struct diff_filepair *p = q->queue[i]; 249if(!DIFF_FILE_VALID(p->one)) 250if(!DIFF_FILE_VALID(p->two)) 251continue;/* unmerged */ 252else 253locate_rename_dst(p->two,1); 254else if(!DIFF_FILE_VALID(p->two)) { 255/* If the source is a broken "delete", and 256 * they did not really want to get broken, 257 * that means the source actually stays. 258 */ 259int stays = (p->broken_pair && !p->score); 260register_rename_src(p->one, stays); 261} 262else if(detect_rename == DIFF_DETECT_COPY) 263register_rename_src(p->one,1); 264} 265if(rename_dst_nr ==0|| rename_src_nr ==0|| 266(0< rename_limit && rename_limit < rename_dst_nr)) 267goto cleanup;/* nothing to do */ 268 269/* We really want to cull the candidates list early 270 * with cheap tests in order to avoid doing deltas. 271 */ 272for(i =0; i < rename_dst_nr; i++) { 273struct diff_filespec *two = rename_dst[i].two; 274for(j =0; j < rename_src_nr; j++) { 275struct diff_filespec *one = rename_src[j].one; 276if(!is_exact_match(one, two)) 277continue; 278record_rename_pair(i, j, MAX_SCORE); 279 rename_count++; 280break;/* we are done with this entry */ 281} 282} 283 284/* Have we run out the created file pool? If so we can avoid 285 * doing the delta matrix altogether. 286 */ 287if(rename_count == rename_dst_nr) 288goto cleanup; 289 290if(minimum_score == MAX_SCORE) 291goto cleanup; 292 293 num_create = (rename_dst_nr - rename_count); 294 num_src = rename_src_nr; 295 mx =xmalloc(sizeof(*mx) * num_create * num_src); 296for(dst_cnt = i =0; i < rename_dst_nr; i++) { 297int base = dst_cnt * num_src; 298struct diff_filespec *two = rename_dst[i].two; 299if(rename_dst[i].pair) 300continue;/* dealt with exact match already. */ 301for(j =0; j < rename_src_nr; j++) { 302struct diff_filespec *one = rename_src[j].one; 303struct diff_score *m = &mx[base+j]; 304 m->src = j; 305 m->dst = i; 306 m->score =estimate_similarity(one, two, 307 minimum_score); 308} 309 dst_cnt++; 310} 311/* cost matrix sorted by most to least similar pair */ 312qsort(mx, num_create * num_src,sizeof(*mx), score_compare); 313for(i =0; i < num_create * num_src; i++) { 314struct diff_rename_dst *dst = &rename_dst[mx[i].dst]; 315if(dst->pair) 316continue;/* already done, either exact or fuzzy. */ 317if(mx[i].score < minimum_score) 318break;/* there is no more usable pair. */ 319record_rename_pair(mx[i].dst, mx[i].src, mx[i].score); 320 rename_count++; 321} 322free(mx); 323 324 cleanup: 325/* At this point, we have found some renames and copies and they 326 * are recorded in rename_dst. The original list is still in *q. 327 */ 328 outq.queue = NULL; 329 outq.nr = outq.alloc =0; 330for(i =0; i < q->nr; i++) { 331struct diff_filepair *p = q->queue[i]; 332struct diff_filepair *pair_to_free = NULL; 333 334if(!DIFF_FILE_VALID(p->one) &&DIFF_FILE_VALID(p->two)) { 335/* 336 * Creation 337 * 338 * We would output this create record if it has 339 * not been turned into a rename/copy already. 340 */ 341struct diff_rename_dst *dst = 342locate_rename_dst(p->two,0); 343if(dst && dst->pair) { 344diff_q(&outq, dst->pair); 345 pair_to_free = p; 346} 347else 348/* no matching rename/copy source, so 349 * record this as a creation. 350 */ 351diff_q(&outq, p); 352} 353else if(DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) { 354/* 355 * Deletion 356 * 357 * We would output this delete record if: 358 * 359 * (1) this is a broken delete and the counterpart 360 * broken create remains in the output; or 361 * (2) this is not a broken delete, and rename_dst 362 * does not have a rename/copy to move p->one->path 363 * out of existence. 364 * 365 * Otherwise, the counterpart broken create 366 * has been turned into a rename-edit; or 367 * delete did not have a matching create to 368 * begin with. 369 */ 370if(DIFF_PAIR_BROKEN(p)) { 371/* broken delete */ 372struct diff_rename_dst *dst = 373locate_rename_dst(p->one,0); 374if(dst && dst->pair) 375/* counterpart is now rename/copy */ 376 pair_to_free = p; 377} 378else{ 379for(j =0; j < rename_dst_nr; j++) { 380if(!rename_dst[j].pair) 381continue; 382if(strcmp(rename_dst[j].pair-> 383 one->path, 384 p->one->path)) 385continue; 386break; 387} 388if(j < rename_dst_nr) 389/* this path remains */ 390 pair_to_free = p; 391} 392 393if(pair_to_free) 394; 395else 396diff_q(&outq, p); 397} 398else if(!diff_unmodified_pair(p)) 399/* all the usual ones need to be kept */ 400diff_q(&outq, p); 401else 402/* no need to keep unmodified pairs */ 403 pair_to_free = p; 404 405if(pair_to_free) 406diff_free_filepair(pair_to_free); 407} 408diff_debug_queue("done copying original", &outq); 409 410free(q->queue); 411*q = outq; 412diff_debug_queue("done collapsing", q); 413 414/* We need to see which rename source really stays here; 415 * earlier we only checked if the path is left in the result, 416 * but even if a path remains in the result, if that is coming 417 * from copying something else on top of it, then the original 418 * source is lost and does not stay. 419 */ 420for(i =0; i < q->nr; i++) { 421struct diff_filepair *p = q->queue[i]; 422if(DIFF_PAIR_RENAME(p) && p->source_stays) { 423/* If one appears as the target of a rename-copy, 424 * then mark p->source_stays = 0; otherwise 425 * leave it as is. 426 */ 427 p->source_stays =compute_stays(q, p->one); 428} 429} 430 431for(i =0; i < rename_dst_nr; i++) { 432diff_free_filespec_data(rename_dst[i].two); 433free(rename_dst[i].two); 434} 435 436free(rename_dst); 437 rename_dst = NULL; 438 rename_dst_nr = rename_dst_alloc =0; 439free(rename_src); 440 rename_src = NULL; 441 rename_src_nr = rename_src_alloc =0; 442return; 443}