git.oblomov.eu Git - git/blob - tree-diff.c

   1 /*
   2  * Helper functions for tree diff generation
   3  */
   4 #include "cache.h"
   5 #include "diff.h"
   6 #include "diffcore.h"
   7 #include "tree.h"
   8
   9 /*
  10  * internal mode marker, saying a tree entry != entry of tp[imin]
  11  * (see ll_diff_tree_paths for what it means there)
  12  *
  13  * we will update/use/emit entry for diff only with it unset.
  14  */
  15 #define S_IFXMIN_NEQ    S_DIFFTREE_IFXMIN_NEQ
  16
  17 #define FAST_ARRAY_ALLOC(x, nr) do { \
  18         if ((nr) <= 2) \
  19                 (x) = xalloca((nr) * sizeof(*(x))); \
  20         else \
  21                 ALLOC_ARRAY((x), nr); \
  22 } while(0)
  23 #define FAST_ARRAY_FREE(x, nr) do { \
  24         if ((nr) > 2) \
  25                 free((x)); \
  26 } while(0)
  27
  28 static struct combine_diff_path *ll_diff_tree_paths(
  29         struct combine_diff_path *p, const struct object_id *oid,
  30         const struct object_id **parents_oid, int nparent,
  31         struct strbuf *base, struct diff_options *opt);
  32 static void ll_diff_tree_oid(const struct object_id *old_oid,
  33                              const struct object_id *new_oid,
  34                              struct strbuf *base, struct diff_options *opt);
  35
  36 /*
  37  * Compare two tree entries, taking into account only path/S_ISDIR(mode),
  38  * but not their sha1's.
  39  *
  40  * NOTE files and directories *always* compare differently, even when having
  41  *      the same name - thanks to base_name_compare().
  42  *
  43  * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty,
  44  *      so that they sort *after* valid tree entries.
  45  *
  46  *      Due to this convention, if trees are scanned in sorted order, all
  47  *      non-empty descriptors will be processed first.
  48  */
  49 static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
  50 {
  51         struct name_entry *e1, *e2;
  52         int cmp;
  53
  54         /* empty descriptors sort after valid tree entries */
  55         if (!t1->size)
  56                 return t2->size ? 1 : 0;
  57         else if (!t2->size)
  58                 return -1;
  59
  60         e1 = &t1->entry;
  61         e2 = &t2->entry;
  62         cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode,
  63                                 e2->path, tree_entry_len(e2), e2->mode);
  64         return cmp;
  65 }
  66
  67
  68 /*
  69  * convert path -> opt->diff_*() callbacks
  70  *
  71  * emits diff to first parent only, and tells diff tree-walker that we are done
  72  * with p and it can be freed.
  73  */
  74 static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_diff_path *p)
  75 {
  76         struct combine_diff_parent *p0 = &p->parent[0];
  77         if (p->mode && p0->mode) {
  78                 opt->change(opt, p0->mode, p->mode, &p0->oid, &p->oid,
  79                         1, 1, p->path, 0, 0);
  80         }
  81         else {
  82                 const struct object_id *oid;
  83                 unsigned int mode;
  84                 int addremove;
  85
  86                 if (p->mode) {
  87                         addremove = '+';
  88                         oid = &p->oid;
  89                         mode = p->mode;
  90                 } else {
  91                         addremove = '-';
  92                         oid = &p0->oid;
  93                         mode = p0->mode;
  94                 }
  95
  96                 opt->add_remove(opt, addremove, mode, oid, 1, p->path, 0);
  97         }
  98
  99         return 0;       /* we are done with p */
 100 }
 101
 102
 103 /*
 104  * Make a new combine_diff_path from path/mode/sha1
 105  * and append it to paths list tail.
 106  *
 107  * Memory for created elements could be reused:
 108  *
 109  *      - if last->next == NULL, the memory is allocated;
 110  *
 111  *      - if last->next != NULL, it is assumed that p=last->next was returned
 112  *        earlier by this function, and p->next was *not* modified.
 113  *        The memory is then reused from p.
 114  *
 115  * so for clients,
 116  *
 117  * - if you do need to keep the element
 118  *
 119  *      p = path_appendnew(p, ...);
 120  *      process(p);
 121  *      p->next = NULL;
 122  *
 123  * - if you don't need to keep the element after processing
 124  *
 125  *      pprev = p;
 126  *      p = path_appendnew(p, ...);
 127  *      process(p);
 128  *      p = pprev;
 129  *      ; don't forget to free tail->next in the end
 130  *
 131  * p->parent[] remains uninitialized.
 132  */
 133 static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
 134         int nparent, const struct strbuf *base, const char *path, int pathlen,
 135         unsigned mode, const struct object_id *oid)
 136 {
 137         struct combine_diff_path *p;
 138         size_t len = st_add(base->len, pathlen);
 139         size_t alloclen = combine_diff_path_size(nparent, len);
 140
 141         /* if last->next is !NULL - it is a pre-allocated memory, we can reuse */
 142         p = last->next;
 143         if (p && (alloclen > (intptr_t)p->next)) {
 144                 FREE_AND_NULL(p);
 145         }
 146
 147         if (!p) {
 148                 p = xmalloc(alloclen);
 149
 150                 /*
 151                  * until we go to it next round, .next holds how many bytes we
 152                  * allocated (for faster realloc - we don't need copying old data).
 153                  */
 154                 p->next = (struct combine_diff_path *)(intptr_t)alloclen;
 155         }
 156
 157         last->next = p;
 158
 159         p->path = (char *)&(p->parent[nparent]);
 160         memcpy(p->path, base->buf, base->len);
 161         memcpy(p->path + base->len, path, pathlen);
 162         p->path[len] = 0;
 163         p->mode = mode;
 164         oidcpy(&p->oid, oid ? oid : &null_oid);
 165
 166         return p;
 167 }
 168
 169 /*
 170  * new path should be added to combine diff
 171  *
 172  * 3 cases on how/when it should be called and behaves:
 173  *
 174  *       t, !tp         -> path added, all parents lack it
 175  *      !t,  tp         -> path removed from all parents
 176  *       t,  tp         -> path modified/added
 177  *                         (M for tp[i]=tp[imin], A otherwise)
 178  */
 179 static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 180         struct strbuf *base, struct diff_options *opt, int nparent,
 181         struct tree_desc *t, struct tree_desc *tp,
 182         int imin)
 183 {
 184         unsigned short mode;
 185         const char *path;
 186         const struct object_id *oid;
 187         int pathlen;
 188         int old_baselen = base->len;
 189         int i, isdir, recurse = 0, emitthis = 1;
 190
 191         /* at least something has to be valid */
 192         assert(t || tp);
 193
 194         if (t) {
 195                 /* path present in resulting tree */
 196                 oid = tree_entry_extract(t, &path, &mode);
 197                 pathlen = tree_entry_len(&t->entry);
 198                 isdir = S_ISDIR(mode);
 199         } else {
 200                 /*
 201                  * a path was removed - take path from imin parent. Also take
 202                  * mode from that parent, to decide on recursion(1).
 203                  *
 204                  * 1) all modes for tp[i]=tp[imin] should be the same wrt
 205                  *    S_ISDIR, thanks to base_name_compare().
 206                  */
 207                 tree_entry_extract(&tp[imin], &path, &mode);
 208                 pathlen = tree_entry_len(&tp[imin].entry);
 209
 210                 isdir = S_ISDIR(mode);
 211                 oid = NULL;
 212                 mode = 0;
 213         }
 214
 215         if (opt->flags.recursive && isdir) {
 216                 recurse = 1;
 217                 emitthis = opt->flags.tree_in_recursive;
 218         }
 219
 220         if (emitthis) {
 221                 int keep;
 222                 struct combine_diff_path *pprev = p;
 223                 p = path_appendnew(p, nparent, base, path, pathlen, mode, oid);
 224
 225                 for (i = 0; i < nparent; ++i) {
 226                         /*
 227                          * tp[i] is valid, if present and if tp[i]==tp[imin] -
 228                          * otherwise, we should ignore it.
 229                          */
 230                         int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);
 231
 232                         const struct object_id *oid_i;
 233                         unsigned mode_i;
 234
 235                         p->parent[i].status =
 236                                 !t ? DIFF_STATUS_DELETED :
 237                                         tpi_valid ?
 238                                                 DIFF_STATUS_MODIFIED :
 239                                                 DIFF_STATUS_ADDED;
 240
 241                         if (tpi_valid) {
 242                                 oid_i = &tp[i].entry.oid;
 243                                 mode_i = tp[i].entry.mode;
 244                         }
 245                         else {
 246                                 oid_i = &null_oid;
 247                                 mode_i = 0;
 248                         }
 249
 250                         p->parent[i].mode = mode_i;
 251                         oidcpy(&p->parent[i].oid, oid_i);
 252                 }
 253
 254                 keep = 1;
 255                 if (opt->pathchange)
 256                         keep = opt->pathchange(opt, p);
 257
 258                 /*
 259                  * If a path was filtered or consumed - we don't need to add it
 260                  * to the list and can reuse its memory, leaving it as
 261                  * pre-allocated element on the tail.
 262                  *
 263                  * On the other hand, if path needs to be kept, we need to
 264                  * correct its .next to NULL, as it was pre-initialized to how
 265                  * much memory was allocated.
 266                  *
 267                  * see path_appendnew() for details.
 268                  */
 269                 if (!keep)
 270                         p = pprev;
 271                 else
 272                         p->next = NULL;
 273         }
 274
 275         if (recurse) {
 276                 const struct object_id **parents_oid;
 277
 278                 FAST_ARRAY_ALLOC(parents_oid, nparent);
 279                 for (i = 0; i < nparent; ++i) {
 280                         /* same rule as in emitthis */
 281                         int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);
 282
 283                         parents_oid[i] = tpi_valid ? &tp[i].entry.oid : NULL;
 284                 }
 285
 286                 strbuf_add(base, path, pathlen);
 287                 strbuf_addch(base, '/');
 288                 p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt);
 289                 FAST_ARRAY_FREE(parents_oid, nparent);
 290         }
 291
 292         strbuf_setlen(base, old_baselen);
 293         return p;
 294 }
 295
 296 static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
 297                                struct diff_options *opt)
 298 {
 299         enum interesting match;
 300
 301         while (t->size) {
 302                 match = tree_entry_interesting(opt->repo->index, &t->entry,
 303                                                base, 0, &opt->pathspec);
 304                 if (match) {
 305                         if (match == all_entries_not_interesting)
 306                                 t->size = 0;
 307                         break;
 308                 }
 309                 update_tree_entry(t);
 310         }
 311 }
 312
 313
 314 /*
 315  * generate paths for combined diff D(sha1,parents_oid[])
 316  *
 317  * Resulting paths are appended to combine_diff_path linked list, and also, are
 318  * emitted on the go via opt->pathchange() callback, so it is possible to
 319  * process the result as batch or incrementally.
 320  *
 321  * The paths are generated scanning new tree and all parents trees
 322  * simultaneously, similarly to what diff_tree() was doing for 2 trees.
 323  * The theory behind such scan is as follows:
 324  *
 325  *
 326  * D(T,P1...Pn) calculation scheme
 327  * -------------------------------
 328  *
 329  * D(T,P1...Pn) = D(T,P1) ^ ... ^ D(T,Pn)       (regarding resulting paths set)
 330  *
 331  *      D(T,Pj)         - diff between T..Pj
 332  *      D(T,P1...Pn)    - combined diff from T to parents P1,...,Pn
 333  *
 334  *
 335  * We start from all trees, which are sorted, and compare their entries in
 336  * lock-step:
 337  *
 338  *       T     P1       Pn
 339  *       -     -        -
 340  *      |t|   |p1|     |pn|
 341  *      |-|   |--| ... |--|      imin = argmin(p1...pn)
 342  *      | |   |  |     |  |
 343  *      |-|   |--|     |--|
 344  *      |.|   |. |     |. |
 345  *       .     .        .
 346  *       .     .        .
 347  *
 348  * at any time there could be 3 cases:
 349  *
 350  *      1)  t < p[imin];
 351  *      2)  t > p[imin];
 352  *      3)  t = p[imin].
 353  *
 354  * Schematic deduction of what every case means, and what to do, follows:
 355  *
 356  * 1)  t < p[imin]  ->  ∀j t ∉ Pj  ->  "+t" ∈ D(T,Pj)  ->  D += "+t";  t↓
 357  *
 358  * 2)  t > p[imin]
 359  *
 360  *     2.1) ∃j: pj > p[imin]  ->  "-p[imin]" ∉ D(T,Pj)  ->  D += ø;  ∀ pi=p[imin]  pi↓
 361  *     2.2) ∀i  pi = p[imin]  ->  pi ∉ T  ->  "-pi" ∈ D(T,Pi)  ->  D += "-p[imin]";  ∀i pi↓
 362  *
 363  * 3)  t = p[imin]
 364  *
 365  *     3.1) ∃j: pj > p[imin]  ->  "+t" ∈ D(T,Pj)  ->  only pi=p[imin] remains to investigate
 366  *     3.2) pi = p[imin]  ->  investigate δ(t,pi)
 367  *      |
 368  *      |
 369  *      v
 370  *
 371  *     3.1+3.2) looking at δ(t,pi) ∀i: pi=p[imin] - if all != ø  ->
 372  *
 373  *                       ⎧δ(t,pi)  - if pi=p[imin]
 374  *              ->  D += ⎨
 375  *                       ⎩"+t"     - if pi>p[imin]
 376  *
 377  *
 378  *     in any case t↓  ∀ pi=p[imin]  pi↓
 379  *
 380  *
 381  * ~~~~~~~~
 382  *
 383  * NOTE
 384  *
 385  *      Usual diff D(A,B) is by definition the same as combined diff D(A,[B]),
 386  *      so this diff paths generator can, and is used, for plain diffs
 387  *      generation too.
 388  *
 389  *      Please keep attention to the common D(A,[B]) case when working on the
 390  *      code, in order not to slow it down.
 391  *
 392  * NOTE
 393  *      nparent must be > 0.
 394  */
 395
 396
 397 /* ∀ pi=p[imin]  pi↓ */
 398 static inline void update_tp_entries(struct tree_desc *tp, int nparent)
 399 {
 400         int i;
 401         for (i = 0; i < nparent; ++i)
 402                 if (!(tp[i].entry.mode & S_IFXMIN_NEQ))
 403                         update_tree_entry(&tp[i]);
 404 }
 405
 406 static struct combine_diff_path *ll_diff_tree_paths(
 407         struct combine_diff_path *p, const struct object_id *oid,
 408         const struct object_id **parents_oid, int nparent,
 409         struct strbuf *base, struct diff_options *opt)
 410 {
 411         struct tree_desc t, *tp;
 412         void *ttree, **tptree;
 413         int i;
 414
 415         FAST_ARRAY_ALLOC(tp, nparent);
 416         FAST_ARRAY_ALLOC(tptree, nparent);
 417
 418         /*
 419          * load parents first, as they are probably already cached.
 420          *
 421          * ( log_tree_diff() parses commit->parent before calling here via
 422          *   diff_tree_oid(parent, commit) )
 423          */
 424         for (i = 0; i < nparent; ++i)
 425                 tptree[i] = fill_tree_descriptor(opt->repo, &tp[i], parents_oid[i]);
 426         ttree = fill_tree_descriptor(opt->repo, &t, oid);
 427
 428         /* Enable recursion indefinitely */
 429         opt->pathspec.recursive = opt->flags.recursive;
 430
 431         for (;;) {
 432                 int imin, cmp;
 433
 434                 if (diff_can_quit_early(opt))
 435                         break;
 436
 437                 if (opt->max_changes && diff_queued_diff.nr > opt->max_changes)
 438                         break;
 439
 440                 if (opt->pathspec.nr) {
 441                         skip_uninteresting(&t, base, opt);
 442                         for (i = 0; i < nparent; i++)
 443                                 skip_uninteresting(&tp[i], base, opt);
 444                 }
 445
 446                 /* comparing is finished when all trees are done */
 447                 if (!t.size) {
 448                         int done = 1;
 449                         for (i = 0; i < nparent; ++i)
 450                                 if (tp[i].size) {
 451                                         done = 0;
 452                                         break;
 453                                 }
 454                         if (done)
 455                                 break;
 456                 }
 457
 458                 /*
 459                  * lookup imin = argmin(p1...pn),
 460                  * mark entries whether they =p[imin] along the way
 461                  */
 462                 imin = 0;
 463                 tp[0].entry.mode &= ~S_IFXMIN_NEQ;
 464
 465                 for (i = 1; i < nparent; ++i) {
 466                         cmp = tree_entry_pathcmp(&tp[i], &tp[imin]);
 467                         if (cmp < 0) {
 468                                 imin = i;
 469                                 tp[i].entry.mode &= ~S_IFXMIN_NEQ;
 470                         }
 471                         else if (cmp == 0) {
 472                                 tp[i].entry.mode &= ~S_IFXMIN_NEQ;
 473                         }
 474                         else {
 475                                 tp[i].entry.mode |= S_IFXMIN_NEQ;
 476                         }
 477                 }
 478
 479                 /* fixup markings for entries before imin */
 480                 for (i = 0; i < imin; ++i)
 481                         tp[i].entry.mode |= S_IFXMIN_NEQ;       /* pi > p[imin] */
 482
 483
 484
 485                 /* compare t vs p[imin] */
 486                 cmp = tree_entry_pathcmp(&t, &tp[imin]);
 487
 488                 /* t = p[imin] */
 489                 if (cmp == 0) {
 490                         /* are either pi > p[imin] or diff(t,pi) != ø ? */
 491                         if (!opt->flags.find_copies_harder) {
 492                                 for (i = 0; i < nparent; ++i) {
 493                                         /* p[i] > p[imin] */
 494                                         if (tp[i].entry.mode & S_IFXMIN_NEQ)
 495                                                 continue;
 496
 497                                         /* diff(t,pi) != ø */
 498                                         if (!oideq(&t.entry.oid, &tp[i].entry.oid) ||
 499                                             (t.entry.mode != tp[i].entry.mode))
 500                                                 continue;
 501
 502                                         goto skip_emit_t_tp;
 503                                 }
 504                         }
 505
 506                         /* D += {δ(t,pi) if pi=p[imin];  "+a" if pi > p[imin]} */
 507                         p = emit_path(p, base, opt, nparent,
 508                                         &t, tp, imin);
 509
 510                 skip_emit_t_tp:
 511                         /* t↓,  ∀ pi=p[imin]  pi↓ */
 512                         update_tree_entry(&t);
 513                         update_tp_entries(tp, nparent);
 514                 }
 515
 516                 /* t < p[imin] */
 517                 else if (cmp < 0) {
 518                         /* D += "+t" */
 519                         p = emit_path(p, base, opt, nparent,
 520                                         &t, /*tp=*/NULL, -1);
 521
 522                         /* t↓ */
 523                         update_tree_entry(&t);
 524                 }
 525
 526                 /* t > p[imin] */
 527                 else {
 528                         /* ∀i pi=p[imin] -> D += "-p[imin]" */
 529                         if (!opt->flags.find_copies_harder) {
 530                                 for (i = 0; i < nparent; ++i)
 531                                         if (tp[i].entry.mode & S_IFXMIN_NEQ)
 532                                                 goto skip_emit_tp;
 533                         }
 534
 535                         p = emit_path(p, base, opt, nparent,
 536                                         /*t=*/NULL, tp, imin);
 537
 538                 skip_emit_tp:
 539                         /* ∀ pi=p[imin]  pi↓ */
 540                         update_tp_entries(tp, nparent);
 541                 }
 542         }
 543
 544         free(ttree);
 545         for (i = nparent-1; i >= 0; i--)
 546                 free(tptree[i]);
 547         FAST_ARRAY_FREE(tptree, nparent);
 548         FAST_ARRAY_FREE(tp, nparent);
 549
 550         return p;
 551 }
 552
 553 struct combine_diff_path *diff_tree_paths(
 554         struct combine_diff_path *p, const struct object_id *oid,
 555         const struct object_id **parents_oid, int nparent,
 556         struct strbuf *base, struct diff_options *opt)
 557 {
 558         p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt);
 559
 560         /*
 561          * free pre-allocated last element, if any
 562          * (see path_appendnew() for details about why)
 563          */
 564         FREE_AND_NULL(p->next);
 565
 566         return p;
 567 }
 568
 569 /*
 570  * Does it look like the resulting diff might be due to a rename?
 571  *  - single entry
 572  *  - not a valid previous file
 573  */
 574 static inline int diff_might_be_rename(void)
 575 {
 576         return diff_queued_diff.nr == 1 &&
 577                 !DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
 578 }
 579
 580 static void try_to_follow_renames(const struct object_id *old_oid,
 581                                   const struct object_id *new_oid,
 582                                   struct strbuf *base, struct diff_options *opt)
 583 {
 584         struct diff_options diff_opts;
 585         struct diff_queue_struct *q = &diff_queued_diff;
 586         struct diff_filepair *choice;
 587         int i;
 588
 589         /*
 590          * follow-rename code is very specific, we need exactly one
 591          * path. Magic that matches more than one path is not
 592          * supported.
 593          */
 594         GUARD_PATHSPEC(&opt->pathspec, PATHSPEC_FROMTOP | PATHSPEC_LITERAL);
 595 #if 0
 596         /*
 597          * We should reject wildcards as well. Unfortunately we
 598          * haven't got a reliable way to detect that 'foo\*bar' in
 599          * fact has no wildcards. nowildcard_len is merely a hint for
 600          * optimization. Let it slip for now until wildmatch is taught
 601          * about dry-run mode and returns wildcard info.
 602          */
 603         if (opt->pathspec.has_wildcard)
 604                 die("BUG:%s:%d: wildcards are not supported",
 605                     __FILE__, __LINE__);
 606 #endif
 607
 608         /* Remove the file creation entry from the diff queue, and remember it */
 609         choice = q->queue[0];
 610         q->nr = 0;
 611
 612         repo_diff_setup(opt->repo, &diff_opts);
 613         diff_opts.flags.recursive = 1;
 614         diff_opts.flags.find_copies_harder = 1;
 615         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 616         diff_opts.single_follow = opt->pathspec.items[0].match;
 617         diff_opts.break_opt = opt->break_opt;
 618         diff_opts.rename_score = opt->rename_score;
 619         diff_setup_done(&diff_opts);
 620         ll_diff_tree_oid(old_oid, new_oid, base, &diff_opts);
 621         diffcore_std(&diff_opts);
 622         clear_pathspec(&diff_opts.pathspec);
 623
 624         /* Go through the new set of filepairing, and see if we find a more interesting one */
 625         opt->found_follow = 0;
 626         for (i = 0; i < q->nr; i++) {
 627                 struct diff_filepair *p = q->queue[i];
 628
 629                 /*
 630                  * Found a source? Not only do we use that for the new
 631                  * diff_queued_diff, we will also use that as the path in
 632                  * the future!
 633                  */
 634                 if ((p->status == 'R' || p->status == 'C') &&
 635                     !strcmp(p->two->path, opt->pathspec.items[0].match)) {
 636                         const char *path[2];
 637
 638                         /* Switch the file-pairs around */
 639                         q->queue[i] = choice;
 640                         choice = p;
 641
 642                         /* Update the path we use from now on.. */
 643                         path[0] = p->one->path;
 644                         path[1] = NULL;
 645                         clear_pathspec(&opt->pathspec);
 646                         parse_pathspec(&opt->pathspec,
 647                                        PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,
 648                                        PATHSPEC_LITERAL_PATH, "", path);
 649
 650                         /*
 651                          * The caller expects us to return a set of vanilla
 652                          * filepairs to let a later call to diffcore_std()
 653                          * it makes to sort the renames out (among other
 654                          * things), but we already have found renames
 655                          * ourselves; signal diffcore_std() not to muck with
 656                          * rename information.
 657                          */
 658                         opt->found_follow = 1;
 659                         break;
 660                 }
 661         }
 662
 663         /*
 664          * Then, discard all the non-relevant file pairs...
 665          */
 666         for (i = 0; i < q->nr; i++) {
 667                 struct diff_filepair *p = q->queue[i];
 668                 diff_free_filepair(p);
 669         }
 670
 671         /*
 672          * .. and re-instate the one we want (which might be either the
 673          * original one, or the rename/copy we found)
 674          */
 675         q->queue[0] = choice;
 676         q->nr = 1;
 677 }
 678
 679 static void ll_diff_tree_oid(const struct object_id *old_oid,
 680                              const struct object_id *new_oid,
 681                              struct strbuf *base, struct diff_options *opt)
 682 {
 683         struct combine_diff_path phead, *p;
 684         pathchange_fn_t pathchange_old = opt->pathchange;
 685
 686         phead.next = NULL;
 687         opt->pathchange = emit_diff_first_parent_only;
 688         diff_tree_paths(&phead, new_oid, &old_oid, 1, base, opt);
 689
 690         for (p = phead.next; p;) {
 691                 struct combine_diff_path *pprev = p;
 692                 p = p->next;
 693                 free(pprev);
 694         }
 695
 696         opt->pathchange = pathchange_old;
 697 }
 698
 699 void diff_tree_oid(const struct object_id *old_oid,
 700                    const struct object_id *new_oid,
 701                    const char *base_str, struct diff_options *opt)
 702 {
 703         struct strbuf base;
 704
 705         strbuf_init(&base, PATH_MAX);
 706         strbuf_addstr(&base, base_str);
 707
 708         ll_diff_tree_oid(old_oid, new_oid, &base, opt);
 709         if (!*base_str && opt->flags.follow_renames && diff_might_be_rename())
 710                 try_to_follow_renames(old_oid, new_oid, &base, opt);
 711
 712         strbuf_release(&base);
 713 }
 714
 715 void diff_root_tree_oid(const struct object_id *new_oid,
 716                         const char *base,
 717                         struct diff_options *opt)
 718 {
 719         diff_tree_oid(NULL, new_oid, base, opt);
 720 }