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.
 137          *
 138          * To the final output routine, and in the diff-raw format
 139          * output, a rename/copy that is based on a path that has a
 140          * later entry that shares the same p->one->path and is not a
 141          * deletion is a copy.  Otherwise it is a rename.
 142          */
 143
 144         struct diff_filepair *dp = diff_queue(outq, src, dst);
 145         dp->rename_rank = rank * 2 + 1;
 146         dp->score = score;
 147         dst->xfrm_flags |= RENAME_DST_MATCHED;
 148 }
 149
 150 #if 0
 151 static void debug_filespec(struct diff_filespec *s, int x, const char *one)
 152 {
 153         fprintf(stderr, "queue[%d] %s (%s) %s %06o %s\n",
 154                 x, one,
 155                 s->path,
 156                 DIFF_FILE_VALID(s) ? "valid" : "invalid",
 157                 s->mode,
 158                 s->sha1_valid ? sha1_to_hex(s->sha1) : "");
 159         fprintf(stderr, "queue[%d] %s size %lu flags %d\n",
 160                 x, one,
 161                 s->size, s->xfrm_flags);
 162 }
 163
 164 static void debug_filepair(const struct diff_filepair *p, int i)
 165 {
 166         debug_filespec(p->one, i, "one");
 167         debug_filespec(p->two, i, "two");
 168         fprintf(stderr, "pair rank %d, orig order %d, score %d\n",
 169                 p->rename_rank, p->orig_order, p->score);
 170 }
 171
 172 static void debug_queue(const char *msg, struct diff_queue_struct *q)
 173 {
 174         int i;
 175         if (msg)
 176                 fprintf(stderr, "%s\n", msg);
 177         fprintf(stderr, "q->nr = %d\n", q->nr);
 178         for (i = 0; i < q->nr; i++) {
 179                 struct diff_filepair *p = q->queue[i];
 180                 debug_filepair(p, i);
 181         }
 182 }
 183 #else
 184 #define debug_queue(a,b) do { ; /*nothing*/ } while(0)
 185 #endif
 186
 187 /*
 188  * We sort the outstanding diff entries according to the rank (see
 189  * comment at the beginning of record_rename_pair) and tiebreak with
 190  * the order in the original input.
 191  */
 192 static int rank_compare(const void *a_, const void *b_)
 193 {
 194         const struct diff_filepair *a = *(const struct diff_filepair **)a_;
 195         const struct diff_filepair *b = *(const struct diff_filepair **)b_;
 196         int a_rank = a->rename_rank;
 197         int b_rank = b->rename_rank;
 198
 199         if (a_rank != b_rank)
 200                 return a_rank - b_rank;
 201         return a->orig_order - b->orig_order;
 202 }
 203
 204 /*
 205  * We sort the rename similarity matrix with the score, in descending
 206  * order (more similar first).
 207  */
 208 static int score_compare(const void *a_, const void *b_)
 209 {
 210         const struct diff_score *a = a_, *b = b_;
 211         return b->score - a->score;
 212 }
 213
 214 int diff_scoreopt_parse(const char *opt)
 215 {
 216         int diglen, num, scale, i;
 217         if (opt[0] != '-' || (opt[1] != 'M' && opt[1] != 'C'))
 218                 return -1; /* that is not a -M nor -C option */
 219         diglen = strspn(opt+2, "0123456789");
 220         if (diglen == 0 || strlen(opt+2) != diglen)
 221                 return 0; /* use default */
 222         sscanf(opt+2, "%d", &num);
 223         for (i = 0, scale = 1; i < diglen; i++)
 224                 scale *= 10;
 225
 226         /* user says num divided by scale and we say internally that
 227          * is MAX_SCORE * num / scale.
 228          */
 229         return MAX_SCORE * num / scale;
 230 }
 231
 232 void diffcore_rename(int detect_rename, int minimum_score)
 233 {
 234         struct diff_queue_struct *q = &diff_queued_diff;
 235         struct diff_queue_struct outq;
 236         struct diff_rename_pool created, deleted, stay;
 237         struct diff_rename_pool *(srcs[2]);
 238         struct diff_score *mx;
 239         int h, i, j;
 240         int num_create, num_src, dst_cnt, src_cnt;
 241
 242         if (!minimum_score)
 243                 minimum_score = DEFAULT_MINIMUM_SCORE;
 244         outq.queue = NULL;
 245         outq.nr = outq.alloc = 0;
 246
 247         diff_rename_pool_clear(&created);
 248         diff_rename_pool_clear(&deleted);
 249         diff_rename_pool_clear(&stay);
 250
 251         srcs[0] = &deleted;
 252         srcs[1] = &stay;
 253
 254         for (i = 0; i < q->nr; i++) {
 255                 struct diff_filepair *p = q->queue[i];
 256                 if (!DIFF_FILE_VALID(p->one))
 257                         if (!DIFF_FILE_VALID(p->two))
 258                                 continue; /* unmerged */
 259                         else
 260                                 diff_rename_pool_add(&created, p->two);
 261                 else if (!DIFF_FILE_VALID(p->two))
 262                         diff_rename_pool_add(&deleted, p->one);
 263                 else if (1 < detect_rename) /* find copy, too */
 264                         diff_rename_pool_add(&stay, p->one);
 265         }
 266         if (created.nr == 0)
 267                 goto cleanup; /* nothing to do */
 268
 269         /* We really want to cull the candidates list early
 270          * with cheap tests in order to avoid doing deltas.
 271          */
 272         for (i = 0; i < created.nr; i++) {
 273                 for (h = 0; h < sizeof(srcs)/sizeof(srcs[0]); h++) {
 274                         struct diff_rename_pool *p = srcs[h];
 275                         for (j = 0; j < p->nr; j++) {
 276                                 if (!is_exact_match(p->s[j], created.s[i]))
 277                                         continue;
 278                                 record_rename_pair(&outq,
 279                                                    p->s[j], created.s[i], h,
 280                                                    MAX_SCORE);
 281                                 break; /* we are done with this entry */
 282                         }
 283                 }
 284         }
 285         debug_queue("done detecting exact", &outq);
 286
 287         /* Have we run out the created file pool?  If so we can avoid
 288          * doing the delta matrix altogether.
 289          */
 290         if (outq.nr == created.nr)
 291                 goto flush_rest;
 292
 293         num_create = (created.nr - outq.nr);
 294         num_src = deleted.nr + stay.nr;
 295         mx = xmalloc(sizeof(*mx) * num_create * num_src);
 296         for (dst_cnt = i = 0; i < created.nr; i++) {
 297                 int base = dst_cnt * num_src;
 298                 if (created.s[i]->xfrm_flags & RENAME_DST_MATCHED)
 299                         continue; /* dealt with exact match already. */
 300                 for (src_cnt = h = 0; h < sizeof(srcs)/sizeof(srcs[0]); h++) {
 301                         struct diff_rename_pool *p = srcs[h];
 302                         for (j = 0; j < p->nr; j++, src_cnt++) {
 303                                 struct diff_score *m = &mx[base + src_cnt];
 304                                 m->src = p->s[j];
 305                                 m->dst = created.s[i];
 306                                 m->score = estimate_similarity(m->src, m->dst,
 307                                                                minimum_score);
 308                                 m->rank = h;
 309                         }
 310                 }
 311                 dst_cnt++;
 312         }
 313         /* cost matrix sorted by most to least similar pair */
 314         qsort(mx, num_create * num_src, sizeof(*mx), score_compare);
 315         for (i = 0; i < num_create * num_src; i++) {
 316                 if (mx[i].dst->xfrm_flags & RENAME_DST_MATCHED)
 317                         continue; /* alreayd done, either exact or fuzzy. */
 318                 if (mx[i].score < minimum_score)
 319                         break; /* there is not any more diffs applicable. */
 320                 record_rename_pair(&outq,
 321                                   mx[i].src, mx[i].dst, mx[i].rank,
 322                                   mx[i].score);
 323         }
 324         free(mx);
 325         debug_queue("done detecting fuzzy", &outq);
 326
 327  flush_rest:
 328         /* At this point, we have found some renames and copies and they
 329          * are kept in outq.  The original list is still in *q.
 330          *
 331          * Scan the original list and move them into the outq; we will sort
 332          * outq and swap it into the queue supplied to pass that to
 333          * downstream, so we assign the sort keys in this loop.
 334          *
 335          * See comments at the top of record_rename_pair for numbers used
 336          * to assign rename_rank.
 337          */
 338         for (i = 0; i < q->nr; i++) {
 339                 struct diff_filepair *dp, *p = q->queue[i];
 340                 if (!DIFF_FILE_VALID(p->one)) {
 341                         /* creation or unmerged entries */
 342                         dp = diff_queue(&outq, p->one, p->two);
 343                         dp->rename_rank = 4;
 344                 }
 345                 else if (!DIFF_FILE_VALID(p->two)) {
 346                         /* deletion */
 347                         dp = diff_queue(&outq, p->one, p->two);
 348                         dp->rename_rank = 2;
 349                 }
 350                 else {
 351                         /* modification, or stay as is */
 352                         dp = diff_queue(&outq, p->one, p->two);
 353                         dp->rename_rank = 4;
 354                 }
 355                 free(p);
 356         }
 357         debug_queue("done copying original", &outq);
 358
 359         /* Sort outq */
 360         qsort(outq.queue, outq.nr, sizeof(outq.queue[0]), rank_compare);
 361
 362         debug_queue("done sorting", &outq);
 363
 364         free(q->queue);
 365         q->nr = q->alloc = 0;
 366         q->queue = NULL;
 367
 368         /* Copy it out to q, removing duplicates. */
 369         for (i = 0; i < outq.nr; i++) {
 370                 struct diff_filepair *p = outq.queue[i];
 371                 if (!DIFF_FILE_VALID(p->one)) {
 372                         /* created or unmerged */
 373                         if (p->two->xfrm_flags & RENAME_DST_MATCHED)
 374                                 ; /* rename/copy created it already */
 375                         else
 376                                 diff_queue(q, p->one, p->two);
 377                 }
 378                 else if (!DIFF_FILE_VALID(p->two)) {
 379                         /* deleted */
 380                         diff_queue(q, p->one, p->two);
 381                 }
 382                 else if (strcmp(p->one->path, p->two->path)) {
 383                         /* rename or copy */
 384                         struct diff_filepair *dp =
 385                                 diff_queue(q, p->one, p->two);
 386                         dp->score = p->score;
 387                 }
 388                 else
 389                         /* otherwise it is a modified (or "stay") entry */
 390                         diff_queue(q, p->one, p->two);
 391                 free(p);
 392         }
 393
 394         free(outq.queue);
 395         debug_queue("done collapsing", q);
 396
 397  cleanup:
 398         free(created.s);
 399         free(deleted.s);
 400         free(stay.s);
 401         return;
 402 }