1/* 2 * Copyright (C) 2005 Junio C Hamano 3 */ 4#include "cache.h" 5#include "diff.h" 6#include "diffcore.h" 7#include "hash.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 = alloc_filespec(two->path); 50 fill_filespec(rename_dst[first].two, two->sha1, two->mode); 51 rename_dst[first].pair = NULL; 52 return &(rename_dst[first]); 53} 54 55/* Table of rename/copy src files */ 56static struct diff_rename_src { 57 struct diff_filespec *one; 58 unsigned short score; /* to remember the break score */ 59} *rename_src; 60static int rename_src_nr, rename_src_alloc; 61 62static struct diff_rename_src *register_rename_src(struct diff_filespec *one, 63 unsigned short score) 64{ 65 int first, last; 66 67 first = 0; 68 last = rename_src_nr; 69 while (last > first) { 70 int next = (last + first) >> 1; 71 struct diff_rename_src *src = &(rename_src[next]); 72 int cmp = strcmp(one->path, src->one->path); 73 if (!cmp) 74 return src; 75 if (cmp < 0) { 76 last = next; 77 continue; 78 } 79 first = next+1; 80 } 81 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].score = score; 94 return &(rename_src[first]); 95} 96 97static int basename_same(struct diff_filespec *src, struct diff_filespec *dst) 98{ 99 int src_len = strlen(src->path), dst_len = strlen(dst->path); 100 while (src_len && dst_len) { 101 char c1 = src->path[--src_len]; 102 char c2 = dst->path[--dst_len]; 103 if (c1 != c2) 104 return 0; 105 if (c1 == '/') 106 return 1; 107 } 108 return (!src_len || src->path[src_len - 1] == '/') && 109 (!dst_len || dst->path[dst_len - 1] == '/'); 110} 111 112struct diff_score { 113 int src; /* index in rename_src */ 114 int dst; /* index in rename_dst */ 115 int score; 116 int name_score; 117}; 118 119static int estimate_similarity(struct diff_filespec *src, 120 struct diff_filespec *dst, 121 int 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 */ 136 unsigned long max_size, delta_size, base_size, src_copied, literal_added; 137 unsigned long delta_limit; 138 int 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 */ 144 if (!S_ISREG(src->mode) || !S_ISREG(dst->mode)) 145 return 0; 146 147 /* 148 * Need to check that source and destination sizes are 149 * filled in before comparing them. 150 * 151 * If we already have "cnt_data" filled in, we know it's 152 * all good (avoid checking the size for zero, as that 153 * is a possible size - we really should have a flag to 154 * say whether the size is valid or not!) 155 */ 156 if (!src->cnt_data && diff_populate_filespec(src, 0)) 157 return 0; 158 if (!dst->cnt_data && diff_populate_filespec(dst, 0)) 159 return 0; 160 161 max_size = ((src->size > dst->size) ? src->size : dst->size); 162 base_size = ((src->size < dst->size) ? src->size : dst->size); 163 delta_size = max_size - base_size; 164 165 /* We would not consider edits that change the file size so 166 * drastically. delta_size must be smaller than 167 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size). 168 * 169 * Note that base_size == 0 case is handled here already 170 * and the final score computation below would not have a 171 * divide-by-zero issue. 172 */ 173 if (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE) 174 return 0; 175 176 delta_limit = (unsigned long) 177 (base_size * (MAX_SCORE-minimum_score) / MAX_SCORE); 178 if (diffcore_count_changes(src, dst, 179 &src->cnt_data, &dst->cnt_data, 180 delta_limit, 181 &src_copied, &literal_added)) 182 return 0; 183 184 /* How similar are they? 185 * what percentage of material in dst are from source? 186 */ 187 if (!dst->size) 188 score = 0; /* should not happen */ 189 else 190 score = (int)(src_copied * MAX_SCORE / max_size); 191 return score; 192} 193 194static void record_rename_pair(int dst_index, int src_index, int score) 195{ 196 struct diff_filespec *src, *dst; 197 struct diff_filepair *dp; 198 199 if (rename_dst[dst_index].pair) 200 die("internal error: dst already matched."); 201 202 src = rename_src[src_index].one; 203 src->rename_used++; 204 src->count++; 205 206 dst = rename_dst[dst_index].two; 207 dst->count++; 208 209 dp = diff_queue(NULL, src, dst); 210 dp->renamed_pair = 1; 211 if (!strcmp(src->path, dst->path)) 212 dp->score = rename_src[src_index].score; 213 else 214 dp->score = score; 215 rename_dst[dst_index].pair = dp; 216} 217 218/* 219 * We sort the rename similarity matrix with the score, in descending 220 * order (the most similar first). 221 */ 222static int score_compare(const void *a_, const void *b_) 223{ 224 const struct diff_score *a = a_, *b = b_; 225 226 if (a->score == b->score) 227 return b->name_score - a->name_score; 228 229 return b->score - a->score; 230} 231 232struct file_similarity { 233 int src_dst, index; 234 struct diff_filespec *filespec; 235 struct file_similarity *next; 236}; 237 238static int find_identical_files(struct file_similarity *src, 239 struct file_similarity *dst) 240{ 241 int renames = 0; 242 243 /* 244 * Walk over all the destinations ... 245 */ 246 do { 247 struct diff_filespec *one = dst->filespec; 248 struct file_similarity *p, *best; 249 int i = 100; 250 251 /* 252 * .. to find the best source match 253 */ 254 best = NULL; 255 for (p = src; p; p = p->next) { 256 struct diff_filespec *two = p->filespec; 257 258 /* False hash collission? */ 259 if (hashcmp(one->sha1, two->sha1)) 260 continue; 261 /* Non-regular files? If so, the modes must match! */ 262 if (!S_ISREG(one->mode) || !S_ISREG(two->mode)) { 263 if (one->mode != two->mode) 264 continue; 265 } 266 best = p; 267 if (basename_same(one, two)) 268 break; 269 270 /* Too many identical alternatives? Pick one */ 271 if (!--i) 272 break; 273 } 274 if (best) { 275 record_rename_pair(dst->index, best->index, MAX_SCORE); 276 renames++; 277 } 278 } while ((dst = dst->next) != NULL); 279 return renames; 280} 281 282static void free_similarity_list(struct file_similarity *p) 283{ 284 while (p) { 285 struct file_similarity *entry = p; 286 p = p->next; 287 free(entry); 288 } 289} 290 291static int find_same_files(void *ptr) 292{ 293 int ret; 294 struct file_similarity *p = ptr; 295 struct file_similarity *src = NULL, *dst = NULL; 296 297 /* Split the hash list up into sources and destinations */ 298 do { 299 struct file_similarity *entry = p; 300 p = p->next; 301 if (entry->src_dst < 0) { 302 entry->next = src; 303 src = entry; 304 } else { 305 entry->next = dst; 306 dst = entry; 307 } 308 } while (p); 309 310 /* 311 * If we have both sources *and* destinations, see if 312 * we can match them up 313 */ 314 ret = (src && dst) ? find_identical_files(src, dst) : 0; 315 316 /* Free the hashes and return the number of renames found */ 317 free_similarity_list(src); 318 free_similarity_list(dst); 319 return ret; 320} 321 322static unsigned int hash_filespec(struct diff_filespec *filespec) 323{ 324 unsigned int hash; 325 if (!filespec->sha1_valid) { 326 if (diff_populate_filespec(filespec, 0)) 327 return 0; 328 hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1); 329 } 330 memcpy(&hash, filespec->sha1, sizeof(hash)); 331 return hash; 332} 333 334static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec) 335{ 336 void **pos; 337 unsigned int hash; 338 struct file_similarity *entry = xmalloc(sizeof(*entry)); 339 340 entry->src_dst = src_dst; 341 entry->index = index; 342 entry->filespec = filespec; 343 entry->next = NULL; 344 345 hash = hash_filespec(filespec); 346 pos = insert_hash(hash, entry, table); 347 348 /* We already had an entry there? */ 349 if (pos) { 350 entry->next = *pos; 351 *pos = entry; 352 } 353} 354 355/* 356 * Find exact renames first. 357 * 358 * The first round matches up the up-to-date entries, 359 * and then during the second round we try to match 360 * cache-dirty entries as well. 361 */ 362static int find_exact_renames(void) 363{ 364 int i; 365 struct hash_table file_table; 366 367 init_hash(&file_table); 368 for (i = 0; i < rename_src_nr; i++) 369 insert_file_table(&file_table, -1, i, rename_src[i].one); 370 371 for (i = 0; i < rename_dst_nr; i++) 372 insert_file_table(&file_table, 1, i, rename_dst[i].two); 373 374 /* Find the renames */ 375 i = for_each_hash(&file_table, find_same_files); 376 377 /* .. and free the hash data structure */ 378 free_hash(&file_table); 379 380 return i; 381} 382 383void diffcore_rename(struct diff_options *options) 384{ 385 int detect_rename = options->detect_rename; 386 int minimum_score = options->rename_score; 387 int rename_limit = options->rename_limit; 388 struct diff_queue_struct *q = &diff_queued_diff; 389 struct diff_queue_struct outq; 390 struct diff_score *mx; 391 int i, j, rename_count; 392 int num_create, num_src, dst_cnt; 393 394 if (!minimum_score) 395 minimum_score = DEFAULT_RENAME_SCORE; 396 397 for (i = 0; i < q->nr; i++) { 398 struct diff_filepair *p = q->queue[i]; 399 if (!DIFF_FILE_VALID(p->one)) { 400 if (!DIFF_FILE_VALID(p->two)) 401 continue; /* unmerged */ 402 else if (options->single_follow && 403 strcmp(options->single_follow, p->two->path)) 404 continue; /* not interested */ 405 else 406 locate_rename_dst(p->two, 1); 407 } 408 else if (!DIFF_FILE_VALID(p->two)) { 409 /* 410 * If the source is a broken "delete", and 411 * they did not really want to get broken, 412 * that means the source actually stays. 413 * So we increment the "rename_used" score 414 * by one, to indicate ourselves as a user 415 */ 416 if (p->broken_pair && !p->score) 417 p->one->rename_used++; 418 register_rename_src(p->one, p->score); 419 } 420 else if (detect_rename == DIFF_DETECT_COPY) { 421 /* 422 * Increment the "rename_used" score by 423 * one, to indicate ourselves as a user. 424 */ 425 p->one->rename_used++; 426 register_rename_src(p->one, p->score); 427 } 428 } 429 if (rename_dst_nr == 0 || rename_src_nr == 0) 430 goto cleanup; /* nothing to do */ 431 432 /* 433 * We really want to cull the candidates list early 434 * with cheap tests in order to avoid doing deltas. 435 */ 436 rename_count = find_exact_renames(); 437 438 /* 439 * This basically does a test for the rename matrix not 440 * growing larger than a "rename_limit" square matrix, ie: 441 * 442 * rename_dst_nr * rename_src_nr > rename_limit * rename_limit 443 * 444 * but handles the potential overflow case specially (and we 445 * assume at least 32-bit integers) 446 */ 447 if (rename_limit <= 0 || rename_limit > 32767) 448 rename_limit = 32767; 449 if (rename_dst_nr > rename_limit && rename_src_nr > rename_limit) 450 goto cleanup; 451 if (rename_dst_nr * rename_src_nr > rename_limit * rename_limit) 452 goto cleanup; 453 454 /* Have we run out the created file pool? If so we can avoid 455 * doing the delta matrix altogether. 456 */ 457 if (rename_count == rename_dst_nr) 458 goto cleanup; 459 460 if (minimum_score == MAX_SCORE) 461 goto cleanup; 462 463 num_create = (rename_dst_nr - rename_count); 464 num_src = rename_src_nr; 465 mx = xmalloc(sizeof(*mx) * num_create * num_src); 466 for (dst_cnt = i = 0; i < rename_dst_nr; i++) { 467 int base = dst_cnt * num_src; 468 struct diff_filespec *two = rename_dst[i].two; 469 if (rename_dst[i].pair) 470 continue; /* dealt with exact match already. */ 471 for (j = 0; j < rename_src_nr; j++) { 472 struct diff_filespec *one = rename_src[j].one; 473 struct diff_score *m = &mx[base+j]; 474 m->src = j; 475 m->dst = i; 476 m->score = estimate_similarity(one, two, 477 minimum_score); 478 m->name_score = basename_same(one, two); 479 diff_free_filespec_blob(one); 480 } 481 /* We do not need the text anymore */ 482 diff_free_filespec_blob(two); 483 dst_cnt++; 484 } 485 /* cost matrix sorted by most to least similar pair */ 486 qsort(mx, num_create * num_src, sizeof(*mx), score_compare); 487 for (i = 0; i < num_create * num_src; i++) { 488 struct diff_rename_dst *dst = &rename_dst[mx[i].dst]; 489 if (dst->pair) 490 continue; /* already done, either exact or fuzzy. */ 491 if (mx[i].score < minimum_score) 492 break; /* there is no more usable pair. */ 493 record_rename_pair(mx[i].dst, mx[i].src, mx[i].score); 494 rename_count++; 495 } 496 free(mx); 497 498 cleanup: 499 /* At this point, we have found some renames and copies and they 500 * are recorded in rename_dst. The original list is still in *q. 501 */ 502 outq.queue = NULL; 503 outq.nr = outq.alloc = 0; 504 for (i = 0; i < q->nr; i++) { 505 struct diff_filepair *p = q->queue[i]; 506 struct diff_filepair *pair_to_free = NULL; 507 508 if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) { 509 /* 510 * Creation 511 * 512 * We would output this create record if it has 513 * not been turned into a rename/copy already. 514 */ 515 struct diff_rename_dst *dst = 516 locate_rename_dst(p->two, 0); 517 if (dst && dst->pair) { 518 diff_q(&outq, dst->pair); 519 pair_to_free = p; 520 } 521 else 522 /* no matching rename/copy source, so 523 * record this as a creation. 524 */ 525 diff_q(&outq, p); 526 } 527 else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) { 528 /* 529 * Deletion 530 * 531 * We would output this delete record if: 532 * 533 * (1) this is a broken delete and the counterpart 534 * broken create remains in the output; or 535 * (2) this is not a broken delete, and rename_dst 536 * does not have a rename/copy to move p->one->path 537 * out of existence. 538 * 539 * Otherwise, the counterpart broken create 540 * has been turned into a rename-edit; or 541 * delete did not have a matching create to 542 * begin with. 543 */ 544 if (DIFF_PAIR_BROKEN(p)) { 545 /* broken delete */ 546 struct diff_rename_dst *dst = 547 locate_rename_dst(p->one, 0); 548 if (dst && dst->pair) 549 /* counterpart is now rename/copy */ 550 pair_to_free = p; 551 } 552 else { 553 if (p->one->rename_used) 554 /* this path remains */ 555 pair_to_free = p; 556 } 557 558 if (pair_to_free) 559 ; 560 else 561 diff_q(&outq, p); 562 } 563 else if (!diff_unmodified_pair(p)) 564 /* all the usual ones need to be kept */ 565 diff_q(&outq, p); 566 else 567 /* no need to keep unmodified pairs */ 568 pair_to_free = p; 569 570 if (pair_to_free) 571 diff_free_filepair(pair_to_free); 572 } 573 diff_debug_queue("done copying original", &outq); 574 575 free(q->queue); 576 *q = outq; 577 diff_debug_queue("done collapsing", q); 578 579 for (i = 0; i < rename_dst_nr; i++) 580 free_filespec(rename_dst[i].two); 581 582 free(rename_dst); 583 rename_dst = NULL; 584 rename_dst_nr = rename_dst_alloc = 0; 585 free(rename_src); 586 rename_src = NULL; 587 rename_src_nr = rename_src_alloc = 0; 588 return; 589}