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