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 { 11 struct diff_filespec *two; 12 struct 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, 17 int insert_ok) 18{ 19 int first, last; 20 21 first = 0; 22 last = rename_dst_nr; 23 while (last > first) { 24 int next = (last + first) >> 1; 25 struct diff_rename_dst *dst = &(rename_dst[next]); 26 int cmp = strcmp(two->path, dst->two->path); 27 if (!cmp) 28 return dst; 29 if (cmp < 0) { 30 last = next; 31 continue; 32 } 33 first = next+1; 34 } 35 /* not found */ 36 if (!insert_ok) 37 return NULL; 38 /* insert to make it at "first" */ 39 if (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++; 45 if (first < rename_dst_nr) 46 memmove(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); 49 fill_filespec(rename_dst[first].two, two->sha1, two->mode); 50 rename_dst[first].pair = NULL; 51 return &(rename_dst[first]); 52} 53 54/* Table of rename/copy src files */ 55static struct diff_rename_src { 56 struct diff_filespec *one; 57 unsigned short score; /* to remember the break score */ 58} *rename_src; 59static int rename_src_nr, rename_src_alloc; 60 61static struct diff_rename_src *register_rename_src(struct diff_filespec *one, 62 unsigned short score) 63{ 64 int first, last; 65 66 first = 0; 67 last = rename_src_nr; 68 while (last > first) { 69 int next = (last + first) >> 1; 70 struct diff_rename_src *src = &(rename_src[next]); 71 int cmp = strcmp(one->path, src->one->path); 72 if (!cmp) 73 return src; 74 if (cmp < 0) { 75 last = next; 76 continue; 77 } 78 first = next+1; 79 } 80 81 /* insert to make it at "first" */ 82 if (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++; 88 if (first < rename_src_nr) 89 memmove(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].score = score; 93 return &(rename_src[first]); 94} 95 96static int is_exact_match(struct diff_filespec *src, 97 struct diff_filespec *dst, 98 int contents_too) 99{ 100 if (src->sha1_valid && dst->sha1_valid && 101 !hashcmp(src->sha1, dst->sha1)) 102 return 1; 103 if (!contents_too) 104 return 0; 105 if (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1)) 106 return 0; 107 if (src->size != dst->size) 108 return 0; 109 if (src->sha1_valid && dst->sha1_valid) 110 return !hashcmp(src->sha1, dst->sha1); 111 if (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0)) 112 return 0; 113 if (src->size == dst->size && 114 !memcmp(src->data, dst->data, src->size)) 115 return 1; 116 return 0; 117} 118 119static int basename_same(struct diff_filespec *src, struct diff_filespec *dst) 120{ 121 int src_len = strlen(src->path), dst_len = strlen(dst->path); 122 while (src_len && dst_len) { 123 char c1 = src->path[--src_len]; 124 char c2 = dst->path[--dst_len]; 125 if (c1 != c2) 126 return 0; 127 if (c1 == '/') 128 return 1; 129 } 130 return (!src_len || src->path[src_len - 1] == '/') && 131 (!dst_len || dst->path[dst_len - 1] == '/'); 132} 133 134struct diff_score { 135 int src; /* index in rename_src */ 136 int dst; /* index in rename_dst */ 137 int score; 138 int name_score; 139}; 140 141static int estimate_similarity(struct diff_filespec *src, 142 struct diff_filespec *dst, 143 int minimum_score) 144{ 145 /* src points at a file that existed in the original tree (or 146 * optionally a file in the destination tree) and dst points 147 * at a newly created file. They may be quite similar, in which 148 * case we want to say src is renamed to dst or src is copied into 149 * dst, and then some edit has been applied to dst. 150 * 151 * Compare them and return how similar they are, representing 152 * the score as an integer between 0 and MAX_SCORE. 153 * 154 * When there is an exact match, it is considered a better 155 * match than anything else; the destination does not even 156 * call into this function in that case. 157 */ 158 unsigned long max_size, delta_size, base_size, src_copied, literal_added; 159 unsigned long delta_limit; 160 int score; 161 162 /* We deal only with regular files. Symlink renames are handled 163 * only when they are exact matches --- in other words, no edits 164 * after renaming. 165 */ 166 if (!S_ISREG(src->mode) || !S_ISREG(dst->mode)) 167 return 0; 168 169 max_size = ((src->size > dst->size) ? src->size : dst->size); 170 base_size = ((src->size < dst->size) ? src->size : dst->size); 171 delta_size = max_size - base_size; 172 173 /* We would not consider edits that change the file size so 174 * drastically. delta_size must be smaller than 175 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size). 176 * 177 * Note that base_size == 0 case is handled here already 178 * and the final score computation below would not have a 179 * divide-by-zero issue. 180 */ 181 if (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE) 182 return 0; 183 184 if ((!src->cnt_data && diff_populate_filespec(src, 0)) 185 || (!dst->cnt_data && diff_populate_filespec(dst, 0))) 186 return 0; /* error but caught downstream */ 187 188 189 delta_limit = (unsigned long) 190 (base_size * (MAX_SCORE-minimum_score) / MAX_SCORE); 191 if (diffcore_count_changes(src, dst, 192 &src->cnt_data, &dst->cnt_data, 193 delta_limit, 194 &src_copied, &literal_added)) 195 return 0; 196 197 /* How similar are they? 198 * what percentage of material in dst are from source? 199 */ 200 if (!dst->size) 201 score = 0; /* should not happen */ 202 else 203 score = (int)(src_copied * MAX_SCORE / max_size); 204 return score; 205} 206 207static void record_rename_pair(int dst_index, int src_index, int score) 208{ 209 struct diff_filespec *src, *dst; 210 struct diff_filepair *dp; 211 212 if (rename_dst[dst_index].pair) 213 die("internal error: dst already matched."); 214 215 src = rename_src[src_index].one; 216 src->rename_used++; 217 src->count++; 218 219 dst = rename_dst[dst_index].two; 220 dst->count++; 221 222 dp = diff_queue(NULL, src, dst); 223 dp->renamed_pair = 1; 224 if (!strcmp(src->path, dst->path)) 225 dp->score = rename_src[src_index].score; 226 else 227 dp->score = score; 228 rename_dst[dst_index].pair = dp; 229} 230 231/* 232 * We sort the rename similarity matrix with the score, in descending 233 * order (the most similar first). 234 */ 235static int score_compare(const void *a_, const void *b_) 236{ 237 const struct diff_score *a = a_, *b = b_; 238 239 if (a->score == b->score) 240 return b->name_score - a->name_score; 241 242 return b->score - a->score; 243} 244 245/* 246 * Find exact renames first. 247 * 248 * The first round matches up the up-to-date entries, 249 * and then during the second round we try to match 250 * cache-dirty entries as well. 251 * 252 * Note: the rest of the rename logic depends on this 253 * phase also populating all the filespecs for any 254 * entry that isn't matched up with an exact rename, 255 * see "is_exact_match()". 256 */ 257static int find_exact_renames(void) 258{ 259 int rename_count = 0; 260 int contents_too; 261 262 for (contents_too = 0; contents_too < 2; contents_too++) { 263 int i; 264 265 for (i = 0; i < rename_dst_nr; i++) { 266 struct diff_filespec *two = rename_dst[i].two; 267 int j; 268 269 if (rename_dst[i].pair) 270 continue; /* dealt with an earlier round */ 271 for (j = 0; j < rename_src_nr; j++) { 272 int k; 273 struct diff_filespec *one = rename_src[j].one; 274 if (!is_exact_match(one, two, contents_too)) 275 continue; 276 277 /* see if there is a basename match, too */ 278 for (k = j; k < rename_src_nr; k++) { 279 one = rename_src[k].one; 280 if (basename_same(one, two) && 281 is_exact_match(one, two, 282 contents_too)) { 283 j = k; 284 break; 285 } 286 } 287 288 record_rename_pair(i, j, (int)MAX_SCORE); 289 rename_count++; 290 break; /* we are done with this entry */ 291 } 292 } 293 } 294 return rename_count; 295} 296 297void diffcore_rename(struct diff_options *options) 298{ 299 int detect_rename = options->detect_rename; 300 int minimum_score = options->rename_score; 301 int rename_limit = options->rename_limit; 302 struct diff_queue_struct *q = &diff_queued_diff; 303 struct diff_queue_struct outq; 304 struct diff_score *mx; 305 int i, j, rename_count; 306 int num_create, num_src, dst_cnt; 307 308 if (!minimum_score) 309 minimum_score = DEFAULT_RENAME_SCORE; 310 311 for (i = 0; i < q->nr; i++) { 312 struct diff_filepair *p = q->queue[i]; 313 if (!DIFF_FILE_VALID(p->one)) { 314 if (!DIFF_FILE_VALID(p->two)) 315 continue; /* unmerged */ 316 else if (options->single_follow && 317 strcmp(options->single_follow, p->two->path)) 318 continue; /* not interested */ 319 else 320 locate_rename_dst(p->two, 1); 321 } 322 else if (!DIFF_FILE_VALID(p->two)) { 323 /* 324 * If the source is a broken "delete", and 325 * they did not really want to get broken, 326 * that means the source actually stays. 327 * So we increment the "rename_used" score 328 * by one, to indicate ourselves as a user 329 */ 330 if (p->broken_pair && !p->score) 331 p->one->rename_used++; 332 register_rename_src(p->one, p->score); 333 } 334 else if (detect_rename == DIFF_DETECT_COPY) { 335 /* 336 * Increment the "rename_used" score by 337 * one, to indicate ourselves as a user. 338 */ 339 p->one->rename_used++; 340 register_rename_src(p->one, p->score); 341 } 342 } 343 if (rename_dst_nr == 0 || rename_src_nr == 0) 344 goto cleanup; /* nothing to do */ 345 346 /* 347 * This basically does a test for the rename matrix not 348 * growing larger than a "rename_limit" square matrix, ie: 349 * 350 * rename_dst_nr * rename_src_nr > rename_limit * rename_limit 351 * 352 * but handles the potential overflow case specially (and we 353 * assume at least 32-bit integers) 354 */ 355 if (rename_limit <= 0 || rename_limit > 32767) 356 rename_limit = 32767; 357 if (rename_dst_nr > rename_limit && rename_src_nr > rename_limit) 358 goto cleanup; 359 if (rename_dst_nr * rename_src_nr > rename_limit * rename_limit) 360 goto cleanup; 361 362 /* 363 * We really want to cull the candidates list early 364 * with cheap tests in order to avoid doing deltas. 365 */ 366 rename_count = find_exact_renames(); 367 368 /* Have we run out the created file pool? If so we can avoid 369 * doing the delta matrix altogether. 370 */ 371 if (rename_count == rename_dst_nr) 372 goto cleanup; 373 374 if (minimum_score == MAX_SCORE) 375 goto cleanup; 376 377 num_create = (rename_dst_nr - rename_count); 378 num_src = rename_src_nr; 379 mx = xmalloc(sizeof(*mx) * num_create * num_src); 380 for (dst_cnt = i = 0; i < rename_dst_nr; i++) { 381 int base = dst_cnt * num_src; 382 struct diff_filespec *two = rename_dst[i].two; 383 if (rename_dst[i].pair) 384 continue; /* dealt with exact match already. */ 385 for (j = 0; j < rename_src_nr; j++) { 386 struct diff_filespec *one = rename_src[j].one; 387 struct diff_score *m = &mx[base+j]; 388 m->src = j; 389 m->dst = i; 390 m->score = estimate_similarity(one, two, 391 minimum_score); 392 m->name_score = basename_same(one, two); 393 diff_free_filespec_blob(one); 394 } 395 /* We do not need the text anymore */ 396 diff_free_filespec_blob(two); 397 dst_cnt++; 398 } 399 /* cost matrix sorted by most to least similar pair */ 400 qsort(mx, num_create * num_src, sizeof(*mx), score_compare); 401 for (i = 0; i < num_create * num_src; i++) { 402 struct diff_rename_dst *dst = &rename_dst[mx[i].dst]; 403 if (dst->pair) 404 continue; /* already done, either exact or fuzzy. */ 405 if (mx[i].score < minimum_score) 406 break; /* there is no more usable pair. */ 407 record_rename_pair(mx[i].dst, mx[i].src, mx[i].score); 408 rename_count++; 409 } 410 free(mx); 411 412 cleanup: 413 /* At this point, we have found some renames and copies and they 414 * are recorded in rename_dst. The original list is still in *q. 415 */ 416 outq.queue = NULL; 417 outq.nr = outq.alloc = 0; 418 for (i = 0; i < q->nr; i++) { 419 struct diff_filepair *p = q->queue[i]; 420 struct diff_filepair *pair_to_free = NULL; 421 422 if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) { 423 /* 424 * Creation 425 * 426 * We would output this create record if it has 427 * not been turned into a rename/copy already. 428 */ 429 struct diff_rename_dst *dst = 430 locate_rename_dst(p->two, 0); 431 if (dst && dst->pair) { 432 diff_q(&outq, dst->pair); 433 pair_to_free = p; 434 } 435 else 436 /* no matching rename/copy source, so 437 * record this as a creation. 438 */ 439 diff_q(&outq, p); 440 } 441 else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) { 442 /* 443 * Deletion 444 * 445 * We would output this delete record if: 446 * 447 * (1) this is a broken delete and the counterpart 448 * broken create remains in the output; or 449 * (2) this is not a broken delete, and rename_dst 450 * does not have a rename/copy to move p->one->path 451 * out of existence. 452 * 453 * Otherwise, the counterpart broken create 454 * has been turned into a rename-edit; or 455 * delete did not have a matching create to 456 * begin with. 457 */ 458 if (DIFF_PAIR_BROKEN(p)) { 459 /* broken delete */ 460 struct diff_rename_dst *dst = 461 locate_rename_dst(p->one, 0); 462 if (dst && dst->pair) 463 /* counterpart is now rename/copy */ 464 pair_to_free = p; 465 } 466 else { 467 if (p->one->rename_used) 468 /* this path remains */ 469 pair_to_free = p; 470 } 471 472 if (pair_to_free) 473 ; 474 else 475 diff_q(&outq, p); 476 } 477 else if (!diff_unmodified_pair(p)) 478 /* all the usual ones need to be kept */ 479 diff_q(&outq, p); 480 else 481 /* no need to keep unmodified pairs */ 482 pair_to_free = p; 483 484 if (pair_to_free) 485 diff_free_filepair(pair_to_free); 486 } 487 diff_debug_queue("done copying original", &outq); 488 489 free(q->queue); 490 *q = outq; 491 diff_debug_queue("done collapsing", q); 492 493 for (i = 0; i < rename_dst_nr; i++) 494 free_filespec(rename_dst[i].two); 495 496 free(rename_dst); 497 rename_dst = NULL; 498 rename_dst_nr = rename_dst_alloc = 0; 499 free(rename_src); 500 rename_src = NULL; 501 rename_src_nr = rename_src_alloc = 0; 502 return; 503}