tree-diff.con commit Merge branches 'bw/ls-files-sans-the-index' and 'bw/config-h' into bw/repo-object (25bf951)
   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
  28static 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);
  32static int 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 */
  49static 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 */
  74static 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 */
 133static 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(p);
 145                p = NULL;
 146        }
 147
 148        if (!p) {
 149                p = xmalloc(alloclen);
 150
 151                /*
 152                 * until we go to it next round, .next holds how many bytes we
 153                 * allocated (for faster realloc - we don't need copying old data).
 154                 */
 155                p->next = (struct combine_diff_path *)(intptr_t)alloclen;
 156        }
 157
 158        last->next = p;
 159
 160        p->path = (char *)&(p->parent[nparent]);
 161        memcpy(p->path, base->buf, base->len);
 162        memcpy(p->path + base->len, path, pathlen);
 163        p->path[len] = 0;
 164        p->mode = mode;
 165        oidcpy(&p->oid, oid ? oid : &null_oid);
 166
 167        return p;
 168}
 169
 170/*
 171 * new path should be added to combine diff
 172 *
 173 * 3 cases on how/when it should be called and behaves:
 174 *
 175 *       t, !tp         -> path added, all parents lack it
 176 *      !t,  tp         -> path removed from all parents
 177 *       t,  tp         -> path modified/added
 178 *                         (M for tp[i]=tp[imin], A otherwise)
 179 */
 180static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 181        struct strbuf *base, struct diff_options *opt, int nparent,
 182        struct tree_desc *t, struct tree_desc *tp,
 183        int imin)
 184{
 185        unsigned mode;
 186        const char *path;
 187        const struct object_id *oid;
 188        int pathlen;
 189        int old_baselen = base->len;
 190        int i, isdir, recurse = 0, emitthis = 1;
 191
 192        /* at least something has to be valid */
 193        assert(t || tp);
 194
 195        if (t) {
 196                /* path present in resulting tree */
 197                oid = tree_entry_extract(t, &path, &mode);
 198                pathlen = tree_entry_len(&t->entry);
 199                isdir = S_ISDIR(mode);
 200        } else {
 201                /*
 202                 * a path was removed - take path from imin parent. Also take
 203                 * mode from that parent, to decide on recursion(1).
 204                 *
 205                 * 1) all modes for tp[i]=tp[imin] should be the same wrt
 206                 *    S_ISDIR, thanks to base_name_compare().
 207                 */
 208                tree_entry_extract(&tp[imin], &path, &mode);
 209                pathlen = tree_entry_len(&tp[imin].entry);
 210
 211                isdir = S_ISDIR(mode);
 212                oid = NULL;
 213                mode = 0;
 214        }
 215
 216        if (DIFF_OPT_TST(opt, RECURSIVE) && isdir) {
 217                recurse = 1;
 218                emitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE);
 219        }
 220
 221        if (emitthis) {
 222                int keep;
 223                struct combine_diff_path *pprev = p;
 224                p = path_appendnew(p, nparent, base, path, pathlen, mode, oid);
 225
 226                for (i = 0; i < nparent; ++i) {
 227                        /*
 228                         * tp[i] is valid, if present and if tp[i]==tp[imin] -
 229                         * otherwise, we should ignore it.
 230                         */
 231                        int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);
 232
 233                        const struct object_id *oid_i;
 234                        unsigned mode_i;
 235
 236                        p->parent[i].status =
 237                                !t ? DIFF_STATUS_DELETED :
 238                                        tpi_valid ?
 239                                                DIFF_STATUS_MODIFIED :
 240                                                DIFF_STATUS_ADDED;
 241
 242                        if (tpi_valid) {
 243                                oid_i = tp[i].entry.oid;
 244                                mode_i = tp[i].entry.mode;
 245                        }
 246                        else {
 247                                oid_i = &null_oid;
 248                                mode_i = 0;
 249                        }
 250
 251                        p->parent[i].mode = mode_i;
 252                        oidcpy(&p->parent[i].oid, oid_i);
 253                }
 254
 255                keep = 1;
 256                if (opt->pathchange)
 257                        keep = opt->pathchange(opt, p);
 258
 259                /*
 260                 * If a path was filtered or consumed - we don't need to add it
 261                 * to the list and can reuse its memory, leaving it as
 262                 * pre-allocated element on the tail.
 263                 *
 264                 * On the other hand, if path needs to be kept, we need to
 265                 * correct its .next to NULL, as it was pre-initialized to how
 266                 * much memory was allocated.
 267                 *
 268                 * see path_appendnew() for details.
 269                 */
 270                if (!keep)
 271                        p = pprev;
 272                else
 273                        p->next = NULL;
 274        }
 275
 276        if (recurse) {
 277                const struct object_id **parents_oid;
 278
 279                FAST_ARRAY_ALLOC(parents_oid, nparent);
 280                for (i = 0; i < nparent; ++i) {
 281                        /* same rule as in emitthis */
 282                        int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);
 283
 284                        parents_oid[i] = tpi_valid ? tp[i].entry.oid : NULL;
 285                }
 286
 287                strbuf_add(base, path, pathlen);
 288                strbuf_addch(base, '/');
 289                p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt);
 290                FAST_ARRAY_FREE(parents_oid, nparent);
 291        }
 292
 293        strbuf_setlen(base, old_baselen);
 294        return p;
 295}
 296
 297static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
 298                               struct diff_options *opt)
 299{
 300        enum interesting match;
 301
 302        while (t->size) {
 303                match = tree_entry_interesting(&t->entry, 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↓ */
 398static 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
 406static 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(&tp[i], parents_oid[i]->hash);
 426        ttree = fill_tree_descriptor(&t, oid->hash);
 427
 428        /* Enable recursion indefinitely */
 429        opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
 430
 431        for (;;) {
 432                int imin, cmp;
 433
 434                if (diff_can_quit_early(opt))
 435                        break;
 436
 437                if (opt->pathspec.nr) {
 438                        skip_uninteresting(&t, base, opt);
 439                        for (i = 0; i < nparent; i++)
 440                                skip_uninteresting(&tp[i], base, opt);
 441                }
 442
 443                /* comparing is finished when all trees are done */
 444                if (!t.size) {
 445                        int done = 1;
 446                        for (i = 0; i < nparent; ++i)
 447                                if (tp[i].size) {
 448                                        done = 0;
 449                                        break;
 450                                }
 451                        if (done)
 452                                break;
 453                }
 454
 455                /*
 456                 * lookup imin = argmin(p1...pn),
 457                 * mark entries whether they =p[imin] along the way
 458                 */
 459                imin = 0;
 460                tp[0].entry.mode &= ~S_IFXMIN_NEQ;
 461
 462                for (i = 1; i < nparent; ++i) {
 463                        cmp = tree_entry_pathcmp(&tp[i], &tp[imin]);
 464                        if (cmp < 0) {
 465                                imin = i;
 466                                tp[i].entry.mode &= ~S_IFXMIN_NEQ;
 467                        }
 468                        else if (cmp == 0) {
 469                                tp[i].entry.mode &= ~S_IFXMIN_NEQ;
 470                        }
 471                        else {
 472                                tp[i].entry.mode |= S_IFXMIN_NEQ;
 473                        }
 474                }
 475
 476                /* fixup markings for entries before imin */
 477                for (i = 0; i < imin; ++i)
 478                        tp[i].entry.mode |= S_IFXMIN_NEQ;       /* pi > p[imin] */
 479
 480
 481
 482                /* compare t vs p[imin] */
 483                cmp = tree_entry_pathcmp(&t, &tp[imin]);
 484
 485                /* t = p[imin] */
 486                if (cmp == 0) {
 487                        /* are either pi > p[imin] or diff(t,pi) != ø ? */
 488                        if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) {
 489                                for (i = 0; i < nparent; ++i) {
 490                                        /* p[i] > p[imin] */
 491                                        if (tp[i].entry.mode & S_IFXMIN_NEQ)
 492                                                continue;
 493
 494                                        /* diff(t,pi) != ø */
 495                                        if (oidcmp(t.entry.oid, tp[i].entry.oid) ||
 496                                            (t.entry.mode != tp[i].entry.mode))
 497                                                continue;
 498
 499                                        goto skip_emit_t_tp;
 500                                }
 501                        }
 502
 503                        /* D += {δ(t,pi) if pi=p[imin];  "+a" if pi > p[imin]} */
 504                        p = emit_path(p, base, opt, nparent,
 505                                        &t, tp, imin);
 506
 507                skip_emit_t_tp:
 508                        /* t↓,  ∀ pi=p[imin]  pi↓ */
 509                        update_tree_entry(&t);
 510                        update_tp_entries(tp, nparent);
 511                }
 512
 513                /* t < p[imin] */
 514                else if (cmp < 0) {
 515                        /* D += "+t" */
 516                        p = emit_path(p, base, opt, nparent,
 517                                        &t, /*tp=*/NULL, -1);
 518
 519                        /* t↓ */
 520                        update_tree_entry(&t);
 521                }
 522
 523                /* t > p[imin] */
 524                else {
 525                        /* ∀i pi=p[imin] -> D += "-p[imin]" */
 526                        if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) {
 527                                for (i = 0; i < nparent; ++i)
 528                                        if (tp[i].entry.mode & S_IFXMIN_NEQ)
 529                                                goto skip_emit_tp;
 530                        }
 531
 532                        p = emit_path(p, base, opt, nparent,
 533                                        /*t=*/NULL, tp, imin);
 534
 535                skip_emit_tp:
 536                        /* ∀ pi=p[imin]  pi↓ */
 537                        update_tp_entries(tp, nparent);
 538                }
 539        }
 540
 541        free(ttree);
 542        for (i = nparent-1; i >= 0; i--)
 543                free(tptree[i]);
 544        FAST_ARRAY_FREE(tptree, nparent);
 545        FAST_ARRAY_FREE(tp, nparent);
 546
 547        return p;
 548}
 549
 550struct combine_diff_path *diff_tree_paths(
 551        struct combine_diff_path *p, const struct object_id *oid,
 552        const struct object_id **parents_oid, int nparent,
 553        struct strbuf *base, struct diff_options *opt)
 554{
 555        p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt);
 556
 557        /*
 558         * free pre-allocated last element, if any
 559         * (see path_appendnew() for details about why)
 560         */
 561        if (p->next) {
 562                free(p->next);
 563                p->next = NULL;
 564        }
 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 */
 574static 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
 580static 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        diff_setup(&diff_opts);
 613        DIFF_OPT_SET(&diff_opts, RECURSIVE);
 614        DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
 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
 679static int 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        return 0;
 698}
 699
 700int diff_tree_oid(const struct object_id *old_oid,
 701                  const struct object_id *new_oid,
 702                  const char *base_str, struct diff_options *opt)
 703{
 704        struct strbuf base;
 705        int retval;
 706
 707        strbuf_init(&base, PATH_MAX);
 708        strbuf_addstr(&base, base_str);
 709
 710        retval = ll_diff_tree_oid(old_oid, new_oid, &base, opt);
 711        if (!*base_str && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename())
 712                try_to_follow_renames(old_oid, new_oid, &base, opt);
 713
 714        strbuf_release(&base);
 715
 716        return retval;
 717}
 718
 719int diff_root_tree_oid(const struct object_id *new_oid, const char *base, struct diff_options *opt)
 720{
 721        return diff_tree_oid(NULL, new_oid, base, opt);
 722}