2 * Helper functions for tree diff generation
10 * internal mode marker, saying a tree entry != entry of tp[imin]
11 * (see ll_diff_tree_paths for what it means there)
13 * we will update/use/emit entry for diff only with it unset.
15 #define S_IFXMIN_NEQ S_DIFFTREE_IFXMIN_NEQ
17 #define FAST_ARRAY_ALLOC(x, nr) do { \
19 (x) = xalloca((nr) * sizeof(*(x))); \
21 ALLOC_ARRAY((x), nr); \
23 #define FAST_ARRAY_FREE(x, nr) do { \
28 static struct combine_diff_path *ll_diff_tree_paths(
29 struct combine_diff_path *p, const unsigned char *sha1,
30 const unsigned char **parents_sha1, int nparent,
31 struct strbuf *base, struct diff_options *opt);
32 static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
33 struct strbuf *base, struct diff_options *opt);
36 * Compare two tree entries, taking into account only path/S_ISDIR(mode),
37 * but not their sha1's.
39 * NOTE files and directories *always* compare differently, even when having
40 * the same name - thanks to base_name_compare().
42 * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty,
43 * so that they sort *after* valid tree entries.
45 * Due to this convention, if trees are scanned in sorted order, all
46 * non-empty descriptors will be processed first.
48 static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
50 struct name_entry *e1, *e2;
53 /* empty descriptors sort after valid tree entries */
55 return t2->size ? 1 : 0;
61 cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode,
62 e2->path, tree_entry_len(e2), e2->mode);
68 * convert path -> opt->diff_*() callbacks
70 * emits diff to first parent only, and tells diff tree-walker that we are done
71 * with p and it can be freed.
73 static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_diff_path *p)
75 struct combine_diff_parent *p0 = &p->parent[0];
76 if (p->mode && p0->mode) {
77 opt->change(opt, p0->mode, p->mode, p0->oid.hash, p->oid.hash,
81 const unsigned char *sha1;
95 opt->add_remove(opt, addremove, mode, sha1, 1, p->path, 0);
98 return 0; /* we are done with p */
103 * Make a new combine_diff_path from path/mode/sha1
104 * and append it to paths list tail.
106 * Memory for created elements could be reused:
108 * - if last->next == NULL, the memory is allocated;
110 * - if last->next != NULL, it is assumed that p=last->next was returned
111 * earlier by this function, and p->next was *not* modified.
112 * The memory is then reused from p.
116 * - if you do need to keep the element
118 * p = path_appendnew(p, ...);
122 * - if you don't need to keep the element after processing
125 * p = path_appendnew(p, ...);
128 * ; don't forget to free tail->next in the end
130 * p->parent[] remains uninitialized.
132 static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
133 int nparent, const struct strbuf *base, const char *path, int pathlen,
134 unsigned mode, const unsigned char *sha1)
136 struct combine_diff_path *p;
137 size_t len = st_add(base->len, pathlen);
138 size_t alloclen = combine_diff_path_size(nparent, len);
140 /* if last->next is !NULL - it is a pre-allocated memory, we can reuse */
142 if (p && (alloclen > (intptr_t)p->next)) {
148 p = xmalloc(alloclen);
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).
154 p->next = (struct combine_diff_path *)(intptr_t)alloclen;
159 p->path = (char *)&(p->parent[nparent]);
160 memcpy(p->path, base->buf, base->len);
161 memcpy(p->path + base->len, path, pathlen);
164 hashcpy(p->oid.hash, sha1 ? sha1 : null_sha1);
170 * new path should be added to combine diff
172 * 3 cases on how/when it should be called and behaves:
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)
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,
186 const unsigned char *sha1;
188 int old_baselen = base->len;
189 int i, isdir, recurse = 0, emitthis = 1;
191 /* at least something has to be valid */
195 /* path present in resulting tree */
196 sha1 = tree_entry_extract(t, &path, &mode)->hash;
197 pathlen = tree_entry_len(&t->entry);
198 isdir = S_ISDIR(mode);
201 * a path was removed - take path from imin parent. Also take
202 * mode from that parent, to decide on recursion(1).
204 * 1) all modes for tp[i]=tp[imin] should be the same wrt
205 * S_ISDIR, thanks to base_name_compare().
207 tree_entry_extract(&tp[imin], &path, &mode);
208 pathlen = tree_entry_len(&tp[imin].entry);
210 isdir = S_ISDIR(mode);
215 if (DIFF_OPT_TST(opt, RECURSIVE) && isdir) {
217 emitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE);
222 struct combine_diff_path *pprev = p;
223 p = path_appendnew(p, nparent, base, path, pathlen, mode, sha1);
225 for (i = 0; i < nparent; ++i) {
227 * tp[i] is valid, if present and if tp[i]==tp[imin] -
228 * otherwise, we should ignore it.
230 int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);
232 const unsigned char *sha1_i;
235 p->parent[i].status =
236 !t ? DIFF_STATUS_DELETED :
238 DIFF_STATUS_MODIFIED :
242 sha1_i = tp[i].entry.oid->hash;
243 mode_i = tp[i].entry.mode;
250 p->parent[i].mode = mode_i;
251 hashcpy(p->parent[i].oid.hash, sha1_i ? sha1_i : null_sha1);
256 keep = opt->pathchange(opt, p);
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.
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.
267 * see path_appendnew() for details.
276 const unsigned char **parents_sha1;
278 FAST_ARRAY_ALLOC(parents_sha1, 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);
283 parents_sha1[i] = tpi_valid ? tp[i].entry.oid->hash
287 strbuf_add(base, path, pathlen);
288 strbuf_addch(base, '/');
289 p = ll_diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);
290 FAST_ARRAY_FREE(parents_sha1, nparent);
293 strbuf_setlen(base, old_baselen);
297 static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
298 struct diff_options *opt)
300 enum interesting match;
303 match = tree_entry_interesting(&t->entry, base, 0, &opt->pathspec);
305 if (match == all_entries_not_interesting)
309 update_tree_entry(t);
315 * generate paths for combined diff D(sha1,parents_sha1[])
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.
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:
326 * D(T,P1...Pn) calculation scheme
327 * -------------------------------
329 * D(T,P1...Pn) = D(T,P1) ^ ... ^ D(T,Pn) (regarding resulting paths set)
331 * D(T,Pj) - diff between T..Pj
332 * D(T,P1...Pn) - combined diff from T to parents P1,...,Pn
335 * We start from all trees, which are sorted, and compare their entries in
341 * |-| |--| ... |--| imin = argmin(p1...pn)
348 * at any time there could be 3 cases:
354 * Schematic deduction of what every case means, and what to do, follows:
356 * 1) t < p[imin] -> ∀j t ∉ Pj -> "+t" ∈ D(T,Pj) -> D += "+t"; t↓
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↓
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)
371 * 3.1+3.2) looking at δ(t,pi) ∀i: pi=p[imin] - if all != ø ->
373 * ⎧δ(t,pi) - if pi=p[imin]
375 * ⎩"+t" - if pi>p[imin]
378 * in any case t↓ ∀ pi=p[imin] pi↓
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
389 * Please keep attention to the common D(A,[B]) case when working on the
390 * code, in order not to slow it down.
393 * nparent must be > 0.
397 /* ∀ pi=p[imin] pi↓ */
398 static inline void update_tp_entries(struct tree_desc *tp, int nparent)
401 for (i = 0; i < nparent; ++i)
402 if (!(tp[i].entry.mode & S_IFXMIN_NEQ))
403 update_tree_entry(&tp[i]);
406 static struct combine_diff_path *ll_diff_tree_paths(
407 struct combine_diff_path *p, const unsigned char *sha1,
408 const unsigned char **parents_sha1, int nparent,
409 struct strbuf *base, struct diff_options *opt)
411 struct tree_desc t, *tp;
412 void *ttree, **tptree;
415 FAST_ARRAY_ALLOC(tp, nparent);
416 FAST_ARRAY_ALLOC(tptree, nparent);
419 * load parents first, as they are probably already cached.
421 * ( log_tree_diff() parses commit->parent before calling here via
422 * diff_tree_sha1(parent, commit) )
424 for (i = 0; i < nparent; ++i)
425 tptree[i] = fill_tree_descriptor(&tp[i], parents_sha1[i]);
426 ttree = fill_tree_descriptor(&t, sha1);
428 /* Enable recursion indefinitely */
429 opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
434 if (diff_can_quit_early(opt))
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);
443 /* comparing is finished when all trees are done */
446 for (i = 0; i < nparent; ++i)
456 * lookup imin = argmin(p1...pn),
457 * mark entries whether they =p[imin] along the way
460 tp[0].entry.mode &= ~S_IFXMIN_NEQ;
462 for (i = 1; i < nparent; ++i) {
463 cmp = tree_entry_pathcmp(&tp[i], &tp[imin]);
466 tp[i].entry.mode &= ~S_IFXMIN_NEQ;
469 tp[i].entry.mode &= ~S_IFXMIN_NEQ;
472 tp[i].entry.mode |= S_IFXMIN_NEQ;
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] */
482 /* compare t vs p[imin] */
483 cmp = tree_entry_pathcmp(&t, &tp[imin]);
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) {
491 if (tp[i].entry.mode & S_IFXMIN_NEQ)
494 /* diff(t,pi) != ø */
495 if (oidcmp(t.entry.oid, tp[i].entry.oid) ||
496 (t.entry.mode != tp[i].entry.mode))
503 /* D += {δ(t,pi) if pi=p[imin]; "+a" if pi > p[imin]} */
504 p = emit_path(p, base, opt, nparent,
508 /* t↓, ∀ pi=p[imin] pi↓ */
509 update_tree_entry(&t);
510 update_tp_entries(tp, nparent);
516 p = emit_path(p, base, opt, nparent,
517 &t, /*tp=*/NULL, -1);
520 update_tree_entry(&t);
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)
532 p = emit_path(p, base, opt, nparent,
533 /*t=*/NULL, tp, imin);
536 /* ∀ pi=p[imin] pi↓ */
537 update_tp_entries(tp, nparent);
542 for (i = nparent-1; i >= 0; i--)
544 FAST_ARRAY_FREE(tptree, nparent);
545 FAST_ARRAY_FREE(tp, nparent);
550 struct combine_diff_path *diff_tree_paths(
551 struct combine_diff_path *p, const unsigned char *sha1,
552 const unsigned char **parents_sha1, int nparent,
553 struct strbuf *base, struct diff_options *opt)
555 p = ll_diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);
558 * free pre-allocated last element, if any
559 * (see path_appendnew() for details about why)
570 * Does it look like the resulting diff might be due to a rename?
572 * - not a valid previous file
574 static inline int diff_might_be_rename(void)
576 return diff_queued_diff.nr == 1 &&
577 !DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
580 static void try_to_follow_renames(const unsigned char *old, const unsigned char *new, struct strbuf *base, struct diff_options *opt)
582 struct diff_options diff_opts;
583 struct diff_queue_struct *q = &diff_queued_diff;
584 struct diff_filepair *choice;
588 * follow-rename code is very specific, we need exactly one
589 * path. Magic that matches more than one path is not
592 GUARD_PATHSPEC(&opt->pathspec, PATHSPEC_FROMTOP | PATHSPEC_LITERAL);
595 * We should reject wildcards as well. Unfortunately we
596 * haven't got a reliable way to detect that 'foo\*bar' in
597 * fact has no wildcards. nowildcard_len is merely a hint for
598 * optimization. Let it slip for now until wildmatch is taught
599 * about dry-run mode and returns wildcard info.
601 if (opt->pathspec.has_wildcard)
602 die("BUG:%s:%d: wildcards are not supported",
606 /* Remove the file creation entry from the diff queue, and remember it */
607 choice = q->queue[0];
610 diff_setup(&diff_opts);
611 DIFF_OPT_SET(&diff_opts, RECURSIVE);
612 DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
613 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
614 diff_opts.single_follow = opt->pathspec.items[0].match;
615 diff_opts.break_opt = opt->break_opt;
616 diff_opts.rename_score = opt->rename_score;
617 diff_setup_done(&diff_opts);
618 ll_diff_tree_sha1(old, new, base, &diff_opts);
619 diffcore_std(&diff_opts);
620 clear_pathspec(&diff_opts.pathspec);
622 /* Go through the new set of filepairing, and see if we find a more interesting one */
623 opt->found_follow = 0;
624 for (i = 0; i < q->nr; i++) {
625 struct diff_filepair *p = q->queue[i];
628 * Found a source? Not only do we use that for the new
629 * diff_queued_diff, we will also use that as the path in
632 if ((p->status == 'R' || p->status == 'C') &&
633 !strcmp(p->two->path, opt->pathspec.items[0].match)) {
636 /* Switch the file-pairs around */
637 q->queue[i] = choice;
640 /* Update the path we use from now on.. */
641 path[0] = p->one->path;
643 clear_pathspec(&opt->pathspec);
644 parse_pathspec(&opt->pathspec,
645 PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,
646 PATHSPEC_LITERAL_PATH, "", path);
649 * The caller expects us to return a set of vanilla
650 * filepairs to let a later call to diffcore_std()
651 * it makes to sort the renames out (among other
652 * things), but we already have found renames
653 * ourselves; signal diffcore_std() not to muck with
654 * rename information.
656 opt->found_follow = 1;
662 * Then, discard all the non-relevant file pairs...
664 for (i = 0; i < q->nr; i++) {
665 struct diff_filepair *p = q->queue[i];
666 diff_free_filepair(p);
670 * .. and re-instate the one we want (which might be either the
671 * original one, or the rename/copy we found)
673 q->queue[0] = choice;
677 static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
678 struct strbuf *base, struct diff_options *opt)
680 struct combine_diff_path phead, *p;
681 pathchange_fn_t pathchange_old = opt->pathchange;
684 opt->pathchange = emit_diff_first_parent_only;
685 diff_tree_paths(&phead, new, &old, 1, base, opt);
687 for (p = phead.next; p;) {
688 struct combine_diff_path *pprev = p;
693 opt->pathchange = pathchange_old;
697 int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base_str, struct diff_options *opt)
702 strbuf_init(&base, PATH_MAX);
703 strbuf_addstr(&base, base_str);
705 retval = ll_diff_tree_sha1(old, new, &base, opt);
706 if (!*base_str && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename())
707 try_to_follow_renames(old, new, &base, opt);
709 strbuf_release(&base);
714 int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)
716 return diff_tree_sha1(NULL, new, base, opt);