tree-diff.c

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