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 9/* Table of rename/copy destinations */ 10 11static struct diff_rename_dst { 12struct diff_filespec *two; 13struct diff_filepair *pair; 14} *rename_dst; 15static int rename_dst_nr, rename_dst_alloc; 16 17static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two, 18int insert_ok) 19{ 20int first, last; 21 22 first =0; 23 last = rename_dst_nr; 24while(last > first) { 25int next = (last + first) >>1; 26struct diff_rename_dst *dst = &(rename_dst[next]); 27int cmp =strcmp(two->path, dst->two->path); 28if(!cmp) 29return dst; 30if(cmp <0) { 31 last = next; 32continue; 33} 34 first = next+1; 35} 36/* not found */ 37if(!insert_ok) 38return NULL; 39/* insert to make it at "first" */ 40if(rename_dst_alloc <= rename_dst_nr) { 41 rename_dst_alloc =alloc_nr(rename_dst_alloc); 42 rename_dst =xrealloc(rename_dst, 43 rename_dst_alloc *sizeof(*rename_dst)); 44} 45 rename_dst_nr++; 46if(first < rename_dst_nr) 47memmove(rename_dst + first +1, rename_dst + first, 48(rename_dst_nr - first -1) *sizeof(*rename_dst)); 49 rename_dst[first].two = two; 50 rename_dst[first].pair = NULL; 51return&(rename_dst[first]); 52} 53 54static struct diff_rename_src { 55struct diff_filespec *one; 56unsigned src_used :1; 57} *rename_src; 58static int rename_src_nr, rename_src_alloc; 59 60static struct diff_rename_src *locate_rename_src(struct diff_filespec *one, 61int insert_ok) 62{ 63int first, last; 64 65 first =0; 66 last = rename_src_nr; 67while(last > first) { 68int next = (last + first) >>1; 69struct diff_rename_src *src = &(rename_src[next]); 70int cmp =strcmp(one->path, src->one->path); 71if(!cmp) 72return src; 73if(cmp <0) { 74 last = next; 75continue; 76} 77 first = next+1; 78} 79/* not found */ 80if(!insert_ok) 81return NULL; 82/* insert to make it at "first" */ 83if(rename_src_alloc <= rename_src_nr) { 84 rename_src_alloc =alloc_nr(rename_src_alloc); 85 rename_src =xrealloc(rename_src, 86 rename_src_alloc *sizeof(*rename_src)); 87} 88 rename_src_nr++; 89if(first < rename_src_nr) 90memmove(rename_src + first +1, rename_src + first, 91(rename_src_nr - first -1) *sizeof(*rename_src)); 92 rename_src[first].one = one; 93 rename_src[first].src_used =0; 94return&(rename_src[first]); 95} 96 97static intis_exact_match(struct diff_filespec *src,struct diff_filespec *dst) 98{ 99if(src->sha1_valid && dst->sha1_valid && 100!memcmp(src->sha1, dst->sha1,20)) 101return1; 102if(diff_populate_filespec(src) ||diff_populate_filespec(dst)) 103/* this is an error but will be caught downstream */ 104return0; 105if(src->size == dst->size && 106!memcmp(src->data, dst->data, src->size)) 107return1; 108return0; 109} 110 111struct diff_score { 112int src;/* index in rename_src */ 113int dst;/* index in rename_dst */ 114int score; 115int rank; 116}; 117 118static intestimate_similarity(struct diff_filespec *src, 119struct diff_filespec *dst, 120int minimum_score) 121{ 122/* src points at a file that existed in the original tree (or 123 * optionally a file in the destination tree) and dst points 124 * at a newly created file. They may be quite similar, in which 125 * case we want to say src is renamed to dst or src is copied into 126 * dst, and then some edit has been applied to dst. 127 * 128 * Compare them and return how similar they are, representing 129 * the score as an integer between 0 and 10000, except 130 * where they match exactly it is considered better than anything 131 * else. 132 */ 133void*delta; 134unsigned long delta_size, base_size; 135int score; 136 137/* We deal only with regular files. Symlink renames are handled 138 * only when they are exact matches --- in other words, no edits 139 * after renaming. 140 */ 141if(!S_ISREG(src->mode) || !S_ISREG(dst->mode)) 142return0; 143 144 delta_size = ((src->size < dst->size) ? 145(dst->size - src->size) : (src->size - dst->size)); 146 base_size = ((src->size < dst->size) ? src->size : dst->size); 147 148/* We would not consider edits that change the file size so 149 * drastically. delta_size must be smaller than 150 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size). 151 * Note that base_size == 0 case is handled here already 152 * and the final score computation below would not have a 153 * divide-by-zero issue. 154 */ 155if(base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE) 156return0; 157 158 delta =diff_delta(src->data, src->size, 159 dst->data, dst->size, 160&delta_size); 161/* 162 * We currently punt here, but we may later end up parsing the 163 * delta to really assess the extent of damage. A big consecutive 164 * remove would produce small delta_size that affects quite a 165 * big portion of the file. 166 */ 167free(delta); 168 169/* 170 * Now we will give some score to it. 100% edit gets 0 points 171 * and 0% edit gets MAX_SCORE points. 172 */ 173 score = MAX_SCORE - (MAX_SCORE * delta_size / base_size); 174if(score <0)return0; 175if(MAX_SCORE < score)return MAX_SCORE; 176return score; 177} 178 179static voidrecord_rename_pair(struct diff_queue_struct *renq, 180int dst_index,int src_index,int score) 181{ 182struct diff_filespec *one, *two, *src, *dst; 183struct diff_filepair *dp; 184 185if(rename_dst[dst_index].pair) 186die("internal error: dst already matched."); 187 188 src = rename_src[src_index].one; 189 one =alloc_filespec(src->path); 190fill_filespec(one, src->sha1, src->mode); 191 192 dst = rename_dst[dst_index].two; 193 two =alloc_filespec(dst->path); 194fill_filespec(two, dst->sha1, dst->mode); 195 196 dp =diff_queue(renq, one, two); 197 dp->score = score; 198 199 rename_src[src_index].src_used =1; 200 rename_dst[dst_index].pair = dp; 201} 202 203/* 204 * We sort the rename similarity matrix with the score, in descending 205 * order (more similar first). 206 */ 207static intscore_compare(const void*a_,const void*b_) 208{ 209const struct diff_score *a = a_, *b = b_; 210return b->score - a->score; 211} 212 213intdiff_scoreopt_parse(const char*opt) 214{ 215int diglen, num, scale, i; 216if(opt[0] !='-'|| (opt[1] !='M'&& opt[1] !='C')) 217return-1;/* that is not a -M nor -C option */ 218 diglen =strspn(opt+2,"0123456789"); 219if(diglen ==0||strlen(opt+2) != diglen) 220return0;/* use default */ 221sscanf(opt+2,"%d", &num); 222for(i =0, scale =1; i < diglen; i++) 223 scale *=10; 224 225/* user says num divided by scale and we say internally that 226 * is MAX_SCORE * num / scale. 227 */ 228return MAX_SCORE * num / scale; 229} 230 231voiddiffcore_rename(int detect_rename,int minimum_score) 232{ 233struct diff_queue_struct *q = &diff_queued_diff; 234struct diff_queue_struct renq, outq; 235struct diff_score *mx; 236int i, j; 237int num_create, num_src, dst_cnt; 238 239if(!minimum_score) 240 minimum_score = DEFAULT_MINIMUM_SCORE; 241 renq.queue = NULL; 242 renq.nr = renq.alloc =0; 243 244for(i =0; i < q->nr; i++) { 245struct diff_filepair *p = q->queue[i]; 246if(!DIFF_FILE_VALID(p->one)) 247if(!DIFF_FILE_VALID(p->two)) 248continue;/* unmerged */ 249else 250locate_rename_dst(p->two,1); 251else if(!DIFF_FILE_VALID(p->two)) 252locate_rename_src(p->one,1); 253else if(1< detect_rename)/* find copy, too */ 254locate_rename_src(p->one,1); 255} 256if(rename_dst_nr ==0) 257goto cleanup;/* nothing to do */ 258 259/* We really want to cull the candidates list early 260 * with cheap tests in order to avoid doing deltas. 261 */ 262for(i =0; i < rename_dst_nr; i++) { 263struct diff_filespec *two = rename_dst[i].two; 264for(j =0; j < rename_src_nr; j++) { 265struct diff_filespec *one = rename_src[j].one; 266if(!is_exact_match(one, two)) 267continue; 268record_rename_pair(&renq, i, j, MAX_SCORE); 269break;/* we are done with this entry */ 270} 271} 272diff_debug_queue("done detecting exact", &renq); 273 274/* Have we run out the created file pool? If so we can avoid 275 * doing the delta matrix altogether. 276 */ 277if(renq.nr == rename_dst_nr) 278goto flush_rest; 279 280 num_create = (rename_dst_nr - renq.nr); 281 num_src = rename_src_nr; 282 mx =xmalloc(sizeof(*mx) * num_create * num_src); 283for(dst_cnt = i =0; i < rename_dst_nr; i++) { 284int base = dst_cnt * num_src; 285struct diff_filespec *two = rename_dst[i].two; 286if(rename_dst[i].pair) 287continue;/* dealt with exact match already. */ 288for(j =0; j < rename_src_nr; j++) { 289struct diff_filespec *one = rename_src[j].one; 290struct diff_score *m = &mx[base+j]; 291 m->src = j; 292 m->dst = i; 293 m->score =estimate_similarity(one, two, 294 minimum_score); 295} 296 dst_cnt++; 297} 298/* cost matrix sorted by most to least similar pair */ 299qsort(mx, num_create * num_src,sizeof(*mx), score_compare); 300for(i =0; i < num_create * num_src; i++) { 301struct diff_rename_dst *dst = &rename_dst[mx[i].dst]; 302if(dst->pair) 303continue;/* already done, either exact or fuzzy. */ 304if(mx[i].score < minimum_score) 305break;/* there is not any more diffs applicable. */ 306record_rename_pair(&renq, mx[i].dst, mx[i].src, mx[i].score); 307} 308free(mx); 309diff_debug_queue("done detecting fuzzy", &renq); 310 311 flush_rest: 312/* At this point, we have found some renames and copies and they 313 * are kept in renq. The original list is still in *q. 314 * 315 * Scan the original list and move them into the outq; we will sort 316 * outq and swap it into the queue supplied to pass that to 317 * downstream, so we assign the sort keys in this loop. 318 * 319 * See comments at the top of record_rename_pair for numbers used 320 * to assign rename_rank. 321 */ 322 outq.queue = NULL; 323 outq.nr = outq.alloc =0; 324for(i =0; i < q->nr; i++) { 325struct diff_filepair *p = q->queue[i]; 326struct diff_rename_src *src =locate_rename_src(p->one,0); 327struct diff_rename_dst *dst =locate_rename_dst(p->two,0); 328struct diff_filepair *pair_to_free = NULL; 329 330if(dst) { 331/* creation */ 332if(dst->pair) { 333/* renq has rename/copy already to produce 334 * this file, so we do not emit the creation 335 * record in the output. 336 */ 337diff_q(&outq, dst->pair); 338 pair_to_free = p; 339} 340else 341/* no matching rename/copy source, so record 342 * this as a creation. 343 */ 344diff_q(&outq, p); 345} 346else if(!diff_unmodified_pair(p)) 347/* all the other cases need to be recorded as is */ 348diff_q(&outq, p); 349else{ 350/* unmodified pair needs to be recorded only if 351 * it is used as the source of rename/copy 352 */ 353if(src && src->src_used) 354diff_q(&outq, p); 355else 356 pair_to_free = p; 357} 358if(pair_to_free) { 359diff_free_filespec_data(pair_to_free->one); 360diff_free_filespec_data(pair_to_free->two); 361free(pair_to_free); 362} 363} 364diff_debug_queue("done copying original", &outq); 365 366free(renq.queue); 367free(q->queue); 368*q = outq; 369diff_debug_queue("done collapsing", q); 370 371 cleanup: 372free(rename_dst); 373 rename_dst = NULL; 374 rename_dst_nr = rename_dst_alloc =0; 375free(rename_src); 376 rename_src = NULL; 377 rename_src_nr = rename_src_alloc =0; 378return; 379}