diffcore-rename.c

   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 struct diff_rename_pool {
  10         struct diff_filespec **s;
  11         int nr, alloc;
  12 };
  13
  14 static void diff_rename_pool_clear(struct diff_rename_pool *pool)
  15 {
  16         pool->s = NULL; pool->nr = pool->alloc = 0;
  17 }
  18
  19 static void diff_rename_pool_add(struct diff_rename_pool *pool,
  20                                  struct diff_filespec *s)
  21 {
  22         if (S_ISDIR(s->mode))
  23                 return;  /* no trees, please */
  24
  25         if (pool->alloc <= pool->nr) {
  26                 pool->alloc = alloc_nr(pool->alloc);
  27                 pool->s = xrealloc(pool->s,
  28                                    sizeof(*(pool->s)) * pool->alloc);
  29         }
  30         pool->s[pool->nr] = s;
  31         pool->nr++;
  32 }
  33
  34 static int is_exact_match(struct diff_filespec *src, struct diff_filespec *dst)
  35 {
  36         if (src->sha1_valid && dst->sha1_valid &&
  37             !memcmp(src->sha1, dst->sha1, 20))
  38                 return 1;
  39         if (diff_populate_filespec(src) || diff_populate_filespec(dst))
  40                 /* this is an error but will be caught downstream */
  41                 return 0;
  42         if (src->size == dst->size &&
  43             !memcmp(src->data, dst->data, src->size))
  44                 return 1;
  45         return 0;
  46 }
  47
  48 struct diff_score {
  49         struct diff_filespec *src;
  50         struct diff_filespec *dst;
  51         int score;
  52         int rank;
  53 };
  54
  55 static int estimate_similarity(struct diff_filespec *src,
  56                                struct diff_filespec *dst,
  57                                int minimum_score)
  58 {
  59         /* src points at a file that existed in the original tree (or
  60          * optionally a file in the destination tree) and dst points
  61          * at a newly created file.  They may be quite similar, in which
  62          * case we want to say src is renamed to dst or src is copied into
  63          * dst, and then some edit has been applied to dst.
  64          *
  65          * Compare them and return how similar they are, representing
  66          * the score as an integer between 0 and 10000, except
  67          * where they match exactly it is considered better than anything
  68          * else.
  69          */
  70         void *delta;
  71         unsigned long delta_size, base_size;
  72         int score;
  73
  74         /* We deal only with regular files.  Symlink renames are handled
  75          * only when they are exact matches --- in other words, no edits
  76          * after renaming.
  77          */
  78         if (!S_ISREG(src->mode) || !S_ISREG(dst->mode))
  79                 return 0;
  80
  81         delta_size = ((src->size < dst->size) ?
  82                       (dst->size - src->size) : (src->size - dst->size));
  83         base_size = ((src->size < dst->size) ? src->size : dst->size);
  84
  85         /* We would not consider edits that change the file size so
  86          * drastically.  delta_size must be smaller than
  87          * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
  88          * Note that base_size == 0 case is handled here already
  89          * and the final score computation below would not have a
  90          * divide-by-zero issue.
  91          */
  92         if (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)
  93                 return 0;
  94
  95         delta = diff_delta(src->data, src->size,
  96                            dst->data, dst->size,
  97                            &delta_size);
  98         /*
  99          * We currently punt here, but we may later end up parsing the
 100          * delta to really assess the extent of damage.  A big consecutive
 101          * remove would produce small delta_size that affects quite a
 102          * big portion of the file.
 103          */
 104         free(delta);
 105
 106         /*
 107          * Now we will give some score to it.  100% edit gets 0 points
 108          * and 0% edit gets MAX_SCORE points.
 109          */
 110         score = MAX_SCORE - (MAX_SCORE * delta_size / base_size);
 111         if (score < 0) return 0;
 112         if (MAX_SCORE < score) return MAX_SCORE;
 113         return score;
 114 }
 115
 116 static void record_rename_pair(struct diff_queue_struct *outq,
 117                                struct diff_filespec *src,
 118                                struct diff_filespec *dst,
 119                                int rank,
 120                                int score)
 121 {
 122         /*
 123          * These ranks are used to sort the final output, because there
 124          * are certain dependencies:
 125          *
 126          *  1. rename/copy that depends on deleted ones.
 127          *  2. deletions in the original.
 128          *  3. rename/copy that depends on the pre-edit image of kept files.
 129          *  4. additions, modifications and no-modifications in the original.
 130          *  5. rename/copy that depends on the post-edit image of kept files
 131          *     (note that we currently do not detect such rename/copy).
 132          *
 133          * The downstream diffcore transformers are free to reorder
 134          * the entries as long as they keep file pairs that has the
 135          * same p->one->path in earlier rename_rank to appear before
 136          * later ones.  This ordering is used by the diff_flush()
 137          * logic to tell renames from copies, and also used by the
 138          * diffcore_prune() logic to omit unnecessary
 139          * "no-modification" entries.
 140          *
 141          * To the final output routine, and in the diff-raw format
 142          * output, a rename/copy that is based on a path that has a
 143          * later entry that shares the same p->one->path and is not a
 144          * deletion is a copy.  Otherwise it is a rename.
 145          */
 146
 147         struct diff_filepair *dp = diff_queue(outq, src, dst);
 148         dp->rename_rank = rank * 2 + 1;
 149         dp->score = score;
 150         dst->xfrm_flags |= RENAME_DST_MATCHED;
 151 }
 152
 153 #if 0
 154 static void debug_filespec(struct diff_filespec *s, int x, const char *one)
 155 {
 156         fprintf(stderr, "queue[%d] %s (%s) %s %06o %s\n",
 157                 x, one,
 158                 s->path,
 159                 DIFF_FILE_VALID(s) ? "valid" : "invalid",
 160                 s->mode,
 161                 s->sha1_valid ? sha1_to_hex(s->sha1) : "");
 162         fprintf(stderr, "queue[%d] %s size %lu flags %d\n",
 163                 x, one,
 164                 s->size, s->xfrm_flags);
 165 }
 166
 167 static void debug_filepair(const struct diff_filepair *p, int i)
 168 {
 169         debug_filespec(p->one, i, "one");
 170         debug_filespec(p->two, i, "two");
 171         fprintf(stderr, "pair rank %d, orig order %d, score %d\n",
 172                 p->rename_rank, p->orig_order, p->score);
 173 }
 174
 175 static void debug_queue(const char *msg, struct diff_queue_struct *q)
 176 {
 177         int i;
 178         if (msg)
 179                 fprintf(stderr, "%s\n", msg);
 180         fprintf(stderr, "q->nr = %d\n", q->nr);
 181         for (i = 0; i < q->nr; i++) {
 182                 struct diff_filepair *p = q->queue[i];
 183                 debug_filepair(p, i);
 184         }
 185 }
 186 #else
 187 #define debug_queue(a,b) do { ; /*nothing*/ } while(0)
 188 #endif
 189
 190 /*
 191  * We sort the outstanding diff entries according to the rank (see
 192  * comment at the beginning of record_rename_pair) and tiebreak with
 193  * the order in the original input.
 194  */
 195 static int rank_compare(const void *a_, const void *b_)
 196 {
 197         const struct diff_filepair *a = *(const struct diff_filepair **)a_;
 198         const struct diff_filepair *b = *(const struct diff_filepair **)b_;
 199         int a_rank = a->rename_rank;
 200         int b_rank = b->rename_rank;
 201
 202         if (a_rank != b_rank)
 203                 return a_rank - b_rank;
 204         return a->orig_order - b->orig_order;
 205 }
 206
 207 /*
 208  * We sort the rename similarity matrix with the score, in descending
 209  * order (more similar first).
 210  */
 211 static int score_compare(const void *a_, const void *b_)
 212 {
 213         const struct diff_score *a = a_, *b = b_;
 214         return b->score - a->score;
 215 }
 216
 217 int diff_scoreopt_parse(const char *opt)
 218 {
 219         int diglen, num, scale, i;
 220         if (opt[0] != '-' || (opt[1] != 'M' && opt[1] != 'C'))
 221                 return -1; /* that is not a -M nor -C option */
 222         diglen = strspn(opt+2, "0123456789");
 223         if (diglen == 0 || strlen(opt+2) != diglen)
 224                 return 0; /* use default */
 225         sscanf(opt+2, "%d", &num);
 226         for (i = 0, scale = 1; i < diglen; i++)
 227                 scale *= 10;
 228
 229         /* user says num divided by scale and we say internally that
 230          * is MAX_SCORE * num / scale.
 231          */
 232         return MAX_SCORE * num / scale;
 233 }
 234
 235 void diffcore_rename(int detect_rename, int minimum_score)
 236 {
 237         struct diff_queue_struct *q = &diff_queued_diff;
 238         struct diff_queue_struct outq;
 239         struct diff_rename_pool created, deleted, stay;
 240         struct diff_rename_pool *(srcs[2]);
 241         struct diff_score *mx;
 242         int h, i, j;
 243         int num_create, num_src, dst_cnt, src_cnt;
 244
 245         if (!minimum_score)
 246                 minimum_score = DEFAULT_MINIMUM_SCORE;
 247         outq.queue = NULL;
 248         outq.nr = outq.alloc = 0;
 249
 250         diff_rename_pool_clear(&created);
 251         diff_rename_pool_clear(&deleted);
 252         diff_rename_pool_clear(&stay);
 253
 254         srcs[0] = &deleted;
 255         srcs[1] = &stay;
 256
 257         for (i = 0; i < q->nr; i++) {
 258                 struct diff_filepair *p = q->queue[i];
 259                 if (!DIFF_FILE_VALID(p->one))
 260                         if (!DIFF_FILE_VALID(p->two))
 261                                 continue; /* unmerged */
 262                         else
 263                                 diff_rename_pool_add(&created, p->two);
 264                 else if (!DIFF_FILE_VALID(p->two))
 265                         diff_rename_pool_add(&deleted, p->one);
 266                 else if (1 < detect_rename) /* find copy, too */
 267                         diff_rename_pool_add(&stay, p->one);
 268         }
 269         if (created.nr == 0)
 270                 goto cleanup; /* nothing to do */
 271
 272         /* We really want to cull the candidates list early
 273          * with cheap tests in order to avoid doing deltas.
 274          *
 275          * With the current callers, we should not have already
 276          * matched entries at this point, but it is nonetheless
 277          * checked for sanity.
 278          */
 279         for (i = 0; i < created.nr; i++) {
 280                 if (created.s[i]->xfrm_flags & RENAME_DST_MATCHED)
 281                         continue; /* we have matched exactly already */
 282                 for (h = 0; h < sizeof(srcs)/sizeof(srcs[0]); h++) {
 283                         struct diff_rename_pool *p = srcs[h];
 284                         for (j = 0; j < p->nr; j++) {
 285                                 if (!is_exact_match(p->s[j], created.s[i]))
 286                                         continue;
 287                                 record_rename_pair(&outq,
 288                                                    p->s[j], created.s[i], h,
 289                                                    MAX_SCORE);
 290                                 break; /* we are done with this entry */
 291                         }
 292                 }
 293         }
 294         debug_queue("done detecting exact", &outq);
 295
 296         /* Have we run out the created file pool?  If so we can avoid
 297          * doing the delta matrix altogether.
 298          */
 299         if (outq.nr == created.nr)
 300                 goto flush_rest;
 301
 302         num_create = (created.nr - outq.nr);
 303         num_src = deleted.nr + stay.nr;
 304         mx = xmalloc(sizeof(*mx) * num_create * num_src);
 305         for (dst_cnt = i = 0; i < created.nr; i++) {
 306                 int base = dst_cnt * num_src;
 307                 if (created.s[i]->xfrm_flags & RENAME_DST_MATCHED)
 308                         continue; /* dealt with exact match already. */
 309                 for (src_cnt = h = 0; h < sizeof(srcs)/sizeof(srcs[0]); h++) {
 310                         struct diff_rename_pool *p = srcs[h];
 311                         for (j = 0; j < p->nr; j++, src_cnt++) {
 312                                 struct diff_score *m = &mx[base + src_cnt];
 313                                 m->src = p->s[j];
 314                                 m->dst = created.s[i];
 315                                 m->score = estimate_similarity(m->src, m->dst,
 316                                                                minimum_score);
 317                                 m->rank = h;
 318                         }
 319                 }
 320                 dst_cnt++;
 321         }
 322         /* cost matrix sorted by most to least similar pair */
 323         qsort(mx, num_create * num_src, sizeof(*mx), score_compare);
 324         for (i = 0; i < num_create * num_src; i++) {
 325                 if (mx[i].dst->xfrm_flags & RENAME_DST_MATCHED)
 326                         continue; /* alreayd done, either exact or fuzzy. */
 327                 if (mx[i].score < minimum_score)
 328                         break; /* there is not any more diffs applicable. */
 329                 record_rename_pair(&outq,
 330                                   mx[i].src, mx[i].dst, mx[i].rank,
 331                                   mx[i].score);
 332         }
 333         free(mx);
 334         debug_queue("done detecting fuzzy", &outq);
 335
 336  flush_rest:
 337         /* At this point, we have found some renames and copies and they
 338          * are kept in outq.  The original list is still in *q.
 339          *
 340          * Scan the original list and move them into the outq; we will sort
 341          * outq and swap it into the queue supplied to pass that to
 342          * downstream, so we assign the sort keys in this loop.
 343          *
 344          * See comments at the top of record_rename_pair for numbers used
 345          * to assign rename_rank.
 346          */
 347         for (i = 0; i < q->nr; i++) {
 348                 struct diff_filepair *dp, *p = q->queue[i];
 349                 if (!DIFF_FILE_VALID(p->one)) {
 350                         /* creation or unmerged entries */
 351                         dp = diff_queue(&outq, p->one, p->two);
 352                         dp->rename_rank = 4;
 353                 }
 354                 else if (!DIFF_FILE_VALID(p->two)) {
 355                         /* deletion */
 356                         dp = diff_queue(&outq, p->one, p->two);
 357                         dp->rename_rank = 2;
 358                 }
 359                 else {
 360                         /* modification, or stay as is */
 361                         dp = diff_queue(&outq, p->one, p->two);
 362                         dp->rename_rank = 4;
 363                 }
 364                 free(p);
 365         }
 366         debug_queue("done copying original", &outq);
 367
 368         /* Sort outq */
 369         qsort(outq.queue, outq.nr, sizeof(outq.queue[0]), rank_compare);
 370
 371         debug_queue("done sorting", &outq);
 372
 373         free(q->queue);
 374         q->nr = q->alloc = 0;
 375         q->queue = NULL;
 376
 377         /* Copy it out to q, removing duplicates. */
 378         for (i = 0; i < outq.nr; i++) {
 379                 struct diff_filepair *p = outq.queue[i];
 380                 if (!DIFF_FILE_VALID(p->one)) {
 381                         /* created or unmerged */
 382                         if (p->two->xfrm_flags & RENAME_DST_MATCHED)
 383                                 ; /* rename/copy created it already */
 384                         else
 385                                 diff_queue(q, p->one, p->two);
 386                 }
 387                 else if (!DIFF_FILE_VALID(p->two)) {
 388                         /* deleted */
 389                         if (p->one->xfrm_flags & RENAME_SRC_GONE)
 390                                 ; /* rename/copy deleted it already */
 391                         else
 392                                 diff_queue(q, p->one, p->two);
 393                 }
 394                 else if (strcmp(p->one->path, p->two->path)) {
 395                         /* rename or copy */
 396                         struct diff_filepair *dp =
 397                                 diff_queue(q, p->one, p->two);
 398                         dp->score = p->score;
 399
 400                         /* if we have a later entry that is a rename/copy
 401                          * that depends on p->one, then we copy here.
 402                          * otherwise we rename it.
 403                          */
 404                         if (!diff_needs_to_stay(&outq, i+1, p->one))
 405                                 /* this is the last one, so mark it as gone.
 406                                  */
 407                                 p->one->xfrm_flags |= RENAME_SRC_GONE;
 408                 }
 409                 else
 410                         /* otherwise it is a modified (or "stay") entry */
 411                         diff_queue(q, p->one, p->two);
 412                 free(p);
 413         }
 414
 415         free(outq.queue);
 416         debug_queue("done collapsing", q);
 417
 418  cleanup:
 419         free(created.s);
 420         free(deleted.s);
 421         free(stay.s);
 422         return;
 423 }