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 { 12 struct diff_filespec *two; 13 struct 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, 18 int insert_ok) 19{ 20 int first, last; 21 22 first = 0; 23 last = rename_dst_nr; 24 while (last > first) { 25 int next = (last + first) >> 1; 26 struct diff_rename_dst *dst = &(rename_dst[next]); 27 int cmp = strcmp(two->path, dst->two->path); 28 if (!cmp) 29 return dst; 30 if (cmp < 0) { 31 last = next; 32 continue; 33 } 34 first = next+1; 35 } 36 /* not found */ 37 if (!insert_ok) 38 return NULL; 39 /* insert to make it at "first" */ 40 if (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++; 46 if (first < rename_dst_nr) 47 memmove(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; 51 return &(rename_dst[first]); 52} 53 54static struct diff_rename_src { 55 struct diff_filespec *one; 56 unsigned 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, 61 int insert_ok) 62{ 63 int first, last; 64 65 first = 0; 66 last = rename_src_nr; 67 while (last > first) { 68 int next = (last + first) >> 1; 69 struct diff_rename_src *src = &(rename_src[next]); 70 int cmp = strcmp(one->path, src->one->path); 71 if (!cmp) 72 return src; 73 if (cmp < 0) { 74 last = next; 75 continue; 76 } 77 first = next+1; 78 } 79 /* not found */ 80 if (!insert_ok) 81 return NULL; 82 /* insert to make it at "first" */ 83 if (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++; 89 if (first < rename_src_nr) 90 memmove(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; 94 return &(rename_src[first]); 95} 96 97static int is_exact_match(struct diff_filespec *src, struct diff_filespec *dst) 98{ 99 if (src->sha1_valid && dst->sha1_valid && 100 !memcmp(src->sha1, dst->sha1, 20)) 101 return 1; 102 if (diff_populate_filespec(src) || diff_populate_filespec(dst)) 103 /* this is an error but will be caught downstream */ 104 return 0; 105 if (src->size == dst->size && 106 !memcmp(src->data, dst->data, src->size)) 107 return 1; 108 return 0; 109} 110 111struct diff_score { 112 int src; /* index in rename_src */ 113 int dst; /* index in rename_dst */ 114 int score; 115 int rank; 116}; 117 118static int estimate_similarity(struct diff_filespec *src, 119 struct diff_filespec *dst, 120 int 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 */ 133 void *delta; 134 unsigned long delta_size, base_size; 135 int 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 */ 141 if (!S_ISREG(src->mode) || !S_ISREG(dst->mode)) 142 return 0; 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 */ 155 if (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE) 156 return 0; 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 */ 167 free(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); 174 if (score < 0) return 0; 175 if (MAX_SCORE < score) return MAX_SCORE; 176 return score; 177} 178 179static void record_rename_pair(struct diff_queue_struct *renq, 180 int dst_index, int src_index, int score) 181{ 182 struct diff_filespec *one, *two, *src, *dst; 183 struct diff_filepair *dp; 184 185 if (rename_dst[dst_index].pair) 186 die("internal error: dst already matched."); 187 188 src = rename_src[src_index].one; 189 one = alloc_filespec(src->path); 190 fill_filespec(one, src->sha1, src->mode); 191 192 dst = rename_dst[dst_index].two; 193 two = alloc_filespec(dst->path); 194 fill_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 int score_compare(const void *a_, const void *b_) 208{ 209 const struct diff_score *a = a_, *b = b_; 210 return b->score - a->score; 211} 212 213int diff_scoreopt_parse(const char *opt) 214{ 215 int diglen, num, scale, i; 216 if (opt[0] != '-' || (opt[1] != 'M' && opt[1] != 'C')) 217 return -1; /* that is not a -M nor -C option */ 218 diglen = strspn(opt+2, "0123456789"); 219 if (diglen == 0 || strlen(opt+2) != diglen) 220 return 0; /* use default */ 221 sscanf(opt+2, "%d", &num); 222 for (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 */ 228 return MAX_SCORE * num / scale; 229} 230 231void diffcore_rename(int detect_rename, int minimum_score) 232{ 233 struct diff_queue_struct *q = &diff_queued_diff; 234 struct diff_queue_struct renq, outq; 235 struct diff_score *mx; 236 int i, j; 237 int num_create, num_src, dst_cnt; 238 239 if (!minimum_score) 240 minimum_score = DEFAULT_MINIMUM_SCORE; 241 renq.queue = NULL; 242 renq.nr = renq.alloc = 0; 243 244 for (i = 0; i < q->nr; i++) { 245 struct diff_filepair *p = q->queue[i]; 246 if (!DIFF_FILE_VALID(p->one)) 247 if (!DIFF_FILE_VALID(p->two)) 248 continue; /* unmerged */ 249 else 250 locate_rename_dst(p->two, 1); 251 else if (!DIFF_FILE_VALID(p->two)) 252 locate_rename_src(p->one, 1); 253 else if (1 < detect_rename) /* find copy, too */ 254 locate_rename_src(p->one, 1); 255 } 256 if (rename_dst_nr == 0) 257 goto 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 */ 262 for (i = 0; i < rename_dst_nr; i++) { 263 struct diff_filespec *two = rename_dst[i].two; 264 for (j = 0; j < rename_src_nr; j++) { 265 struct diff_filespec *one = rename_src[j].one; 266 if (!is_exact_match(one, two)) 267 continue; 268 record_rename_pair(&renq, i, j, MAX_SCORE); 269 break; /* we are done with this entry */ 270 } 271 } 272 diff_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 */ 277 if (renq.nr == rename_dst_nr) 278 goto 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); 283 for (dst_cnt = i = 0; i < rename_dst_nr; i++) { 284 int base = dst_cnt * num_src; 285 struct diff_filespec *two = rename_dst[i].two; 286 if (rename_dst[i].pair) 287 continue; /* dealt with exact match already. */ 288 for (j = 0; j < rename_src_nr; j++) { 289 struct diff_filespec *one = rename_src[j].one; 290 struct 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 */ 299 qsort(mx, num_create * num_src, sizeof(*mx), score_compare); 300 for (i = 0; i < num_create * num_src; i++) { 301 struct diff_rename_dst *dst = &rename_dst[mx[i].dst]; 302 if (dst->pair) 303 continue; /* already done, either exact or fuzzy. */ 304 if (mx[i].score < minimum_score) 305 break; /* there is not any more diffs applicable. */ 306 record_rename_pair(&renq, mx[i].dst, mx[i].src, mx[i].score); 307 } 308 free(mx); 309 diff_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; 324 for (i = 0; i < q->nr; i++) { 325 struct diff_filepair *p = q->queue[i]; 326 struct diff_rename_src *src = locate_rename_src(p->one, 0); 327 struct diff_rename_dst *dst = locate_rename_dst(p->two, 0); 328 struct diff_filepair *pair_to_free = NULL; 329 330 if (dst) { 331 /* creation */ 332 if (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 */ 337 diff_q(&outq, dst->pair); 338 pair_to_free = p; 339 } 340 else 341 /* no matching rename/copy source, so record 342 * this as a creation. 343 */ 344 diff_q(&outq, p); 345 } 346 else if (!diff_unmodified_pair(p)) 347 /* all the other cases need to be recorded as is */ 348 diff_q(&outq, p); 349 else { 350 /* unmodified pair needs to be recorded only if 351 * it is used as the source of rename/copy 352 */ 353 if (src && src->src_used) 354 diff_q(&outq, p); 355 else 356 pair_to_free = p; 357 } 358 if (pair_to_free) { 359 diff_free_filespec_data(pair_to_free->one); 360 diff_free_filespec_data(pair_to_free->two); 361 free(pair_to_free); 362 } 363 } 364 diff_debug_queue("done copying original", &outq); 365 366 free(renq.queue); 367 free(q->queue); 368 *q = outq; 369 diff_debug_queue("done collapsing", q); 370 371 cleanup: 372 free(rename_dst); 373 rename_dst = NULL; 374 rename_dst_nr = rename_dst_alloc = 0; 375 free(rename_src); 376 rename_src = NULL; 377 rename_src_nr = rename_src_alloc = 0; 378 return; 379}