diffcore-rename.con commit Merge branch 'jk/diff-files-assume-unchanged' (4144059)
   1/*
   2 * Copyright (C) 2005 Junio C Hamano
   3 */
   4#include "cache.h"
   5#include "diff.h"
   6#include "diffcore.h"
   7#include "hashmap.h"
   8#include "progress.h"
   9
  10/* Table of rename/copy destinations */
  11
  12static struct diff_rename_dst {
  13        struct diff_filespec *two;
  14        struct diff_filepair *pair;
  15} *rename_dst;
  16static int rename_dst_nr, rename_dst_alloc;
  17
  18static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
  19                                                 int insert_ok)
  20{
  21        int first, last;
  22
  23        first = 0;
  24        last = rename_dst_nr;
  25        while (last > first) {
  26                int next = (last + first) >> 1;
  27                struct diff_rename_dst *dst = &(rename_dst[next]);
  28                int cmp = strcmp(two->path, dst->two->path);
  29                if (!cmp)
  30                        return dst;
  31                if (cmp < 0) {
  32                        last = next;
  33                        continue;
  34                }
  35                first = next+1;
  36        }
  37        /* not found */
  38        if (!insert_ok)
  39                return NULL;
  40        /* insert to make it at "first" */
  41        ALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);
  42        rename_dst_nr++;
  43        if (first < rename_dst_nr)
  44                memmove(rename_dst + first + 1, rename_dst + first,
  45                        (rename_dst_nr - first - 1) * sizeof(*rename_dst));
  46        rename_dst[first].two = alloc_filespec(two->path);
  47        fill_filespec(rename_dst[first].two, two->sha1, two->sha1_valid, two->mode);
  48        rename_dst[first].pair = NULL;
  49        return &(rename_dst[first]);
  50}
  51
  52/* Table of rename/copy src files */
  53static struct diff_rename_src {
  54        struct diff_filepair *p;
  55        unsigned short score; /* to remember the break score */
  56} *rename_src;
  57static int rename_src_nr, rename_src_alloc;
  58
  59static struct diff_rename_src *register_rename_src(struct diff_filepair *p)
  60{
  61        int first, last;
  62        struct diff_filespec *one = p->one;
  63        unsigned short score = p->score;
  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->p->one->path);
  71                if (!cmp)
  72                        return src;
  73                if (cmp < 0) {
  74                        last = next;
  75                        continue;
  76                }
  77                first = next+1;
  78        }
  79
  80        /* insert to make it at "first" */
  81        ALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);
  82        rename_src_nr++;
  83        if (first < rename_src_nr)
  84                memmove(rename_src + first + 1, rename_src + first,
  85                        (rename_src_nr - first - 1) * sizeof(*rename_src));
  86        rename_src[first].p = p;
  87        rename_src[first].score = score;
  88        return &(rename_src[first]);
  89}
  90
  91static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)
  92{
  93        int src_len = strlen(src->path), dst_len = strlen(dst->path);
  94        while (src_len && dst_len) {
  95                char c1 = src->path[--src_len];
  96                char c2 = dst->path[--dst_len];
  97                if (c1 != c2)
  98                        return 0;
  99                if (c1 == '/')
 100                        return 1;
 101        }
 102        return (!src_len || src->path[src_len - 1] == '/') &&
 103                (!dst_len || dst->path[dst_len - 1] == '/');
 104}
 105
 106struct diff_score {
 107        int src; /* index in rename_src */
 108        int dst; /* index in rename_dst */
 109        unsigned short score;
 110        short name_score;
 111};
 112
 113static int estimate_similarity(struct diff_filespec *src,
 114                               struct diff_filespec *dst,
 115                               int minimum_score)
 116{
 117        /* src points at a file that existed in the original tree (or
 118         * optionally a file in the destination tree) and dst points
 119         * at a newly created file.  They may be quite similar, in which
 120         * case we want to say src is renamed to dst or src is copied into
 121         * dst, and then some edit has been applied to dst.
 122         *
 123         * Compare them and return how similar they are, representing
 124         * the score as an integer between 0 and MAX_SCORE.
 125         *
 126         * When there is an exact match, it is considered a better
 127         * match than anything else; the destination does not even
 128         * call into this function in that case.
 129         */
 130        unsigned long max_size, delta_size, base_size, src_copied, literal_added;
 131        unsigned long delta_limit;
 132        int score;
 133
 134        /* We deal only with regular files.  Symlink renames are handled
 135         * only when they are exact matches --- in other words, no edits
 136         * after renaming.
 137         */
 138        if (!S_ISREG(src->mode) || !S_ISREG(dst->mode))
 139                return 0;
 140
 141        /*
 142         * Need to check that source and destination sizes are
 143         * filled in before comparing them.
 144         *
 145         * If we already have "cnt_data" filled in, we know it's
 146         * all good (avoid checking the size for zero, as that
 147         * is a possible size - we really should have a flag to
 148         * say whether the size is valid or not!)
 149         */
 150        if (!src->cnt_data && diff_populate_filespec(src, 1))
 151                return 0;
 152        if (!dst->cnt_data && diff_populate_filespec(dst, 1))
 153                return 0;
 154
 155        max_size = ((src->size > dst->size) ? src->size : dst->size);
 156        base_size = ((src->size < dst->size) ? src->size : dst->size);
 157        delta_size = max_size - base_size;
 158
 159        /* We would not consider edits that change the file size so
 160         * drastically.  delta_size must be smaller than
 161         * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
 162         *
 163         * Note that base_size == 0 case is handled here already
 164         * and the final score computation below would not have a
 165         * divide-by-zero issue.
 166         */
 167        if (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)
 168                return 0;
 169
 170        if (!src->cnt_data && diff_populate_filespec(src, 0))
 171                return 0;
 172        if (!dst->cnt_data && diff_populate_filespec(dst, 0))
 173                return 0;
 174
 175        delta_limit = (unsigned long)
 176                (base_size * (MAX_SCORE-minimum_score) / MAX_SCORE);
 177        if (diffcore_count_changes(src, dst,
 178                                   &src->cnt_data, &dst->cnt_data,
 179                                   delta_limit,
 180                                   &src_copied, &literal_added))
 181                return 0;
 182
 183        /* How similar are they?
 184         * what percentage of material in dst are from source?
 185         */
 186        if (!dst->size)
 187                score = 0; /* should not happen */
 188        else
 189                score = (int)(src_copied * MAX_SCORE / max_size);
 190        return score;
 191}
 192
 193static void record_rename_pair(int dst_index, int src_index, int score)
 194{
 195        struct diff_filespec *src, *dst;
 196        struct diff_filepair *dp;
 197
 198        if (rename_dst[dst_index].pair)
 199                die("internal error: dst already matched.");
 200
 201        src = rename_src[src_index].p->one;
 202        src->rename_used++;
 203        src->count++;
 204
 205        dst = rename_dst[dst_index].two;
 206        dst->count++;
 207
 208        dp = diff_queue(NULL, src, dst);
 209        dp->renamed_pair = 1;
 210        if (!strcmp(src->path, dst->path))
 211                dp->score = rename_src[src_index].score;
 212        else
 213                dp->score = score;
 214        rename_dst[dst_index].pair = dp;
 215}
 216
 217/*
 218 * We sort the rename similarity matrix with the score, in descending
 219 * order (the most similar first).
 220 */
 221static int score_compare(const void *a_, const void *b_)
 222{
 223        const struct diff_score *a = a_, *b = b_;
 224
 225        /* sink the unused ones to the bottom */
 226        if (a->dst < 0)
 227                return (0 <= b->dst);
 228        else if (b->dst < 0)
 229                return -1;
 230
 231        if (a->score == b->score)
 232                return b->name_score - a->name_score;
 233
 234        return b->score - a->score;
 235}
 236
 237struct file_similarity {
 238        struct hashmap_entry entry;
 239        int index;
 240        struct diff_filespec *filespec;
 241};
 242
 243static unsigned int hash_filespec(struct diff_filespec *filespec)
 244{
 245        unsigned int hash;
 246        if (!filespec->sha1_valid) {
 247                if (diff_populate_filespec(filespec, 0))
 248                        return 0;
 249                hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1);
 250        }
 251        memcpy(&hash, filespec->sha1, sizeof(hash));
 252        return hash;
 253}
 254
 255static int find_identical_files(struct hashmap *srcs,
 256                                int dst_index,
 257                                struct diff_options *options)
 258{
 259        int renames = 0;
 260
 261        struct diff_filespec *target = rename_dst[dst_index].two;
 262        struct file_similarity *p, *best, dst;
 263        int i = 100, best_score = -1;
 264
 265        /*
 266         * Find the best source match for specified destination.
 267         */
 268        best = NULL;
 269        hashmap_entry_init(&dst, hash_filespec(target));
 270        for (p = hashmap_get(srcs, &dst, NULL); p; p = hashmap_get_next(srcs, p)) {
 271                int score;
 272                struct diff_filespec *source = p->filespec;
 273
 274                /* False hash collision? */
 275                if (hashcmp(source->sha1, target->sha1))
 276                        continue;
 277                /* Non-regular files? If so, the modes must match! */
 278                if (!S_ISREG(source->mode) || !S_ISREG(target->mode)) {
 279                        if (source->mode != target->mode)
 280                                continue;
 281                }
 282                /* Give higher scores to sources that haven't been used already */
 283                score = !source->rename_used;
 284                if (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)
 285                        continue;
 286                score += basename_same(source, target);
 287                if (score > best_score) {
 288                        best = p;
 289                        best_score = score;
 290                        if (score == 2)
 291                                break;
 292                }
 293
 294                /* Too many identical alternatives? Pick one */
 295                if (!--i)
 296                        break;
 297        }
 298        if (best) {
 299                record_rename_pair(dst_index, best->index, MAX_SCORE);
 300                renames++;
 301        }
 302        return renames;
 303}
 304
 305static void insert_file_table(struct hashmap *table, int index, struct diff_filespec *filespec)
 306{
 307        struct file_similarity *entry = xmalloc(sizeof(*entry));
 308
 309        entry->index = index;
 310        entry->filespec = filespec;
 311
 312        hashmap_entry_init(entry, hash_filespec(filespec));
 313        hashmap_add(table, entry);
 314}
 315
 316/*
 317 * Find exact renames first.
 318 *
 319 * The first round matches up the up-to-date entries,
 320 * and then during the second round we try to match
 321 * cache-dirty entries as well.
 322 */
 323static int find_exact_renames(struct diff_options *options)
 324{
 325        int i, renames = 0;
 326        struct hashmap file_table;
 327
 328        /* Add all sources to the hash table */
 329        hashmap_init(&file_table, NULL, rename_src_nr);
 330        for (i = 0; i < rename_src_nr; i++)
 331                insert_file_table(&file_table, i, rename_src[i].p->one);
 332
 333        /* Walk the destinations and find best source match */
 334        for (i = 0; i < rename_dst_nr; i++)
 335                renames += find_identical_files(&file_table, i, options);
 336
 337        /* Free the hash data structure and entries */
 338        hashmap_free(&file_table, 1);
 339
 340        return renames;
 341}
 342
 343#define NUM_CANDIDATE_PER_DST 4
 344static void record_if_better(struct diff_score m[], struct diff_score *o)
 345{
 346        int i, worst;
 347
 348        /* find the worst one */
 349        worst = 0;
 350        for (i = 1; i < NUM_CANDIDATE_PER_DST; i++)
 351                if (score_compare(&m[i], &m[worst]) > 0)
 352                        worst = i;
 353
 354        /* is it better than the worst one? */
 355        if (score_compare(&m[worst], o) > 0)
 356                m[worst] = *o;
 357}
 358
 359/*
 360 * Returns:
 361 * 0 if we are under the limit;
 362 * 1 if we need to disable inexact rename detection;
 363 * 2 if we would be under the limit if we were given -C instead of -C -C.
 364 */
 365static int too_many_rename_candidates(int num_create,
 366                                      struct diff_options *options)
 367{
 368        int rename_limit = options->rename_limit;
 369        int num_src = rename_src_nr;
 370        int i;
 371
 372        options->needed_rename_limit = 0;
 373
 374        /*
 375         * This basically does a test for the rename matrix not
 376         * growing larger than a "rename_limit" square matrix, ie:
 377         *
 378         *    num_create * num_src > rename_limit * rename_limit
 379         *
 380         * but handles the potential overflow case specially (and we
 381         * assume at least 32-bit integers)
 382         */
 383        if (rename_limit <= 0 || rename_limit > 32767)
 384                rename_limit = 32767;
 385        if ((num_create <= rename_limit || num_src <= rename_limit) &&
 386            (num_create * num_src <= rename_limit * rename_limit))
 387                return 0;
 388
 389        options->needed_rename_limit =
 390                num_src > num_create ? num_src : num_create;
 391
 392        /* Are we running under -C -C? */
 393        if (!DIFF_OPT_TST(options, FIND_COPIES_HARDER))
 394                return 1;
 395
 396        /* Would we bust the limit if we were running under -C? */
 397        for (num_src = i = 0; i < rename_src_nr; i++) {
 398                if (diff_unmodified_pair(rename_src[i].p))
 399                        continue;
 400                num_src++;
 401        }
 402        if ((num_create <= rename_limit || num_src <= rename_limit) &&
 403            (num_create * num_src <= rename_limit * rename_limit))
 404                return 2;
 405        return 1;
 406}
 407
 408static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, int copies)
 409{
 410        int count = 0, i;
 411
 412        for (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {
 413                struct diff_rename_dst *dst;
 414
 415                if ((mx[i].dst < 0) ||
 416                    (mx[i].score < minimum_score))
 417                        break; /* there is no more usable pair. */
 418                dst = &rename_dst[mx[i].dst];
 419                if (dst->pair)
 420                        continue; /* already done, either exact or fuzzy. */
 421                if (!copies && rename_src[mx[i].src].p->one->rename_used)
 422                        continue;
 423                record_rename_pair(mx[i].dst, mx[i].src, mx[i].score);
 424                count++;
 425        }
 426        return count;
 427}
 428
 429void diffcore_rename(struct diff_options *options)
 430{
 431        int detect_rename = options->detect_rename;
 432        int minimum_score = options->rename_score;
 433        struct diff_queue_struct *q = &diff_queued_diff;
 434        struct diff_queue_struct outq;
 435        struct diff_score *mx;
 436        int i, j, rename_count, skip_unmodified = 0;
 437        int num_create, dst_cnt;
 438        struct progress *progress = NULL;
 439
 440        if (!minimum_score)
 441                minimum_score = DEFAULT_RENAME_SCORE;
 442
 443        for (i = 0; i < q->nr; i++) {
 444                struct diff_filepair *p = q->queue[i];
 445                if (!DIFF_FILE_VALID(p->one)) {
 446                        if (!DIFF_FILE_VALID(p->two))
 447                                continue; /* unmerged */
 448                        else if (options->single_follow &&
 449                                 strcmp(options->single_follow, p->two->path))
 450                                continue; /* not interested */
 451                        else if (!DIFF_OPT_TST(options, RENAME_EMPTY) &&
 452                                 is_empty_blob_sha1(p->two->sha1))
 453                                continue;
 454                        else
 455                                locate_rename_dst(p->two, 1);
 456                }
 457                else if (!DIFF_OPT_TST(options, RENAME_EMPTY) &&
 458                         is_empty_blob_sha1(p->one->sha1))
 459                        continue;
 460                else if (!DIFF_PAIR_UNMERGED(p) && !DIFF_FILE_VALID(p->two)) {
 461                        /*
 462                         * If the source is a broken "delete", and
 463                         * they did not really want to get broken,
 464                         * that means the source actually stays.
 465                         * So we increment the "rename_used" score
 466                         * by one, to indicate ourselves as a user
 467                         */
 468                        if (p->broken_pair && !p->score)
 469                                p->one->rename_used++;
 470                        register_rename_src(p);
 471                }
 472                else if (detect_rename == DIFF_DETECT_COPY) {
 473                        /*
 474                         * Increment the "rename_used" score by
 475                         * one, to indicate ourselves as a user.
 476                         */
 477                        p->one->rename_used++;
 478                        register_rename_src(p);
 479                }
 480        }
 481        if (rename_dst_nr == 0 || rename_src_nr == 0)
 482                goto cleanup; /* nothing to do */
 483
 484        /*
 485         * We really want to cull the candidates list early
 486         * with cheap tests in order to avoid doing deltas.
 487         */
 488        rename_count = find_exact_renames(options);
 489
 490        /* Did we only want exact renames? */
 491        if (minimum_score == MAX_SCORE)
 492                goto cleanup;
 493
 494        /*
 495         * Calculate how many renames are left (but all the source
 496         * files still remain as options for rename/copies!)
 497         */
 498        num_create = (rename_dst_nr - rename_count);
 499
 500        /* All done? */
 501        if (!num_create)
 502                goto cleanup;
 503
 504        switch (too_many_rename_candidates(num_create, options)) {
 505        case 1:
 506                goto cleanup;
 507        case 2:
 508                options->degraded_cc_to_c = 1;
 509                skip_unmodified = 1;
 510                break;
 511        default:
 512                break;
 513        }
 514
 515        if (options->show_rename_progress) {
 516                progress = start_progress_delay(
 517                                _("Performing inexact rename detection"),
 518                                rename_dst_nr * rename_src_nr, 50, 1);
 519        }
 520
 521        mx = xcalloc(num_create * NUM_CANDIDATE_PER_DST, sizeof(*mx));
 522        for (dst_cnt = i = 0; i < rename_dst_nr; i++) {
 523                struct diff_filespec *two = rename_dst[i].two;
 524                struct diff_score *m;
 525
 526                if (rename_dst[i].pair)
 527                        continue; /* dealt with exact match already. */
 528
 529                m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];
 530                for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)
 531                        m[j].dst = -1;
 532
 533                for (j = 0; j < rename_src_nr; j++) {
 534                        struct diff_filespec *one = rename_src[j].p->one;
 535                        struct diff_score this_src;
 536
 537                        if (skip_unmodified &&
 538                            diff_unmodified_pair(rename_src[j].p))
 539                                continue;
 540
 541                        this_src.score = estimate_similarity(one, two,
 542                                                             minimum_score);
 543                        this_src.name_score = basename_same(one, two);
 544                        this_src.dst = i;
 545                        this_src.src = j;
 546                        record_if_better(m, &this_src);
 547                        /*
 548                         * Once we run estimate_similarity,
 549                         * We do not need the text anymore.
 550                         */
 551                        diff_free_filespec_blob(one);
 552                        diff_free_filespec_blob(two);
 553                }
 554                dst_cnt++;
 555                display_progress(progress, (i+1)*rename_src_nr);
 556        }
 557        stop_progress(&progress);
 558
 559        /* cost matrix sorted by most to least similar pair */
 560        qsort(mx, dst_cnt * NUM_CANDIDATE_PER_DST, sizeof(*mx), score_compare);
 561
 562        rename_count += find_renames(mx, dst_cnt, minimum_score, 0);
 563        if (detect_rename == DIFF_DETECT_COPY)
 564                rename_count += find_renames(mx, dst_cnt, minimum_score, 1);
 565        free(mx);
 566
 567 cleanup:
 568        /* At this point, we have found some renames and copies and they
 569         * are recorded in rename_dst.  The original list is still in *q.
 570         */
 571        DIFF_QUEUE_CLEAR(&outq);
 572        for (i = 0; i < q->nr; i++) {
 573                struct diff_filepair *p = q->queue[i];
 574                struct diff_filepair *pair_to_free = NULL;
 575
 576                if (DIFF_PAIR_UNMERGED(p)) {
 577                        diff_q(&outq, p);
 578                }
 579                else if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {
 580                        /*
 581                         * Creation
 582                         *
 583                         * We would output this create record if it has
 584                         * not been turned into a rename/copy already.
 585                         */
 586                        struct diff_rename_dst *dst =
 587                                locate_rename_dst(p->two, 0);
 588                        if (dst && dst->pair) {
 589                                diff_q(&outq, dst->pair);
 590                                pair_to_free = p;
 591                        }
 592                        else
 593                                /* no matching rename/copy source, so
 594                                 * record this as a creation.
 595                                 */
 596                                diff_q(&outq, p);
 597                }
 598                else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {
 599                        /*
 600                         * Deletion
 601                         *
 602                         * We would output this delete record if:
 603                         *
 604                         * (1) this is a broken delete and the counterpart
 605                         *     broken create remains in the output; or
 606                         * (2) this is not a broken delete, and rename_dst
 607                         *     does not have a rename/copy to move p->one->path
 608                         *     out of existence.
 609                         *
 610                         * Otherwise, the counterpart broken create
 611                         * has been turned into a rename-edit; or
 612                         * delete did not have a matching create to
 613                         * begin with.
 614                         */
 615                        if (DIFF_PAIR_BROKEN(p)) {
 616                                /* broken delete */
 617                                struct diff_rename_dst *dst =
 618                                        locate_rename_dst(p->one, 0);
 619                                if (dst && dst->pair)
 620                                        /* counterpart is now rename/copy */
 621                                        pair_to_free = p;
 622                        }
 623                        else {
 624                                if (p->one->rename_used)
 625                                        /* this path remains */
 626                                        pair_to_free = p;
 627                        }
 628
 629                        if (pair_to_free)
 630                                ;
 631                        else
 632                                diff_q(&outq, p);
 633                }
 634                else if (!diff_unmodified_pair(p))
 635                        /* all the usual ones need to be kept */
 636                        diff_q(&outq, p);
 637                else
 638                        /* no need to keep unmodified pairs */
 639                        pair_to_free = p;
 640
 641                if (pair_to_free)
 642                        diff_free_filepair(pair_to_free);
 643        }
 644        diff_debug_queue("done copying original", &outq);
 645
 646        free(q->queue);
 647        *q = outq;
 648        diff_debug_queue("done collapsing", q);
 649
 650        for (i = 0; i < rename_dst_nr; i++)
 651                free_filespec(rename_dst[i].two);
 652
 653        free(rename_dst);
 654        rename_dst = NULL;
 655        rename_dst_nr = rename_dst_alloc = 0;
 656        free(rename_src);
 657        rename_src = NULL;
 658        rename_src_nr = rename_src_alloc = 0;
 659        return;
 660}