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
)) {
147 p
= xmalloc(alloclen
);
150 * until we go to it next round, .next holds how many bytes we
151 * allocated (for faster realloc - we don't need copying old data).
153 p
->next
= (struct combine_diff_path
*)(intptr_t)alloclen
;
158 p
->path
= (char *)&(p
->parent
[nparent
]);
159 memcpy(p
->path
, base
->buf
, base
->len
);
160 memcpy(p
->path
+ base
->len
, path
, pathlen
);
163 hashcpy(p
->oid
.hash
, sha1
? sha1
: null_sha1
);
169 * new path should be added to combine diff
171 * 3 cases on how/when it should be called and behaves:
173 * t, !tp -> path added, all parents lack it
174 * !t, tp -> path removed from all parents
175 * t, tp -> path modified/added
176 * (M for tp[i]=tp[imin], A otherwise)
178 static struct combine_diff_path
*emit_path(struct combine_diff_path
*p
,
179 struct strbuf
*base
, struct diff_options
*opt
, int nparent
,
180 struct tree_desc
*t
, struct tree_desc
*tp
,
185 const unsigned char *sha1
;
187 int old_baselen
= base
->len
;
188 int i
, isdir
, recurse
= 0, emitthis
= 1;
190 /* at least something has to be valid */
194 /* path present in resulting tree */
195 sha1
= tree_entry_extract(t
, &path
, &mode
)->hash
;
196 pathlen
= tree_entry_len(&t
->entry
);
197 isdir
= S_ISDIR(mode
);
200 * a path was removed - take path from imin parent. Also take
201 * mode from that parent, to decide on recursion(1).
203 * 1) all modes for tp[i]=tp[imin] should be the same wrt
204 * S_ISDIR, thanks to base_name_compare().
206 tree_entry_extract(&tp
[imin
], &path
, &mode
);
207 pathlen
= tree_entry_len(&tp
[imin
].entry
);
209 isdir
= S_ISDIR(mode
);
214 if (DIFF_OPT_TST(opt
, RECURSIVE
) && isdir
) {
216 emitthis
= DIFF_OPT_TST(opt
, TREE_IN_RECURSIVE
);
221 struct combine_diff_path
*pprev
= p
;
222 p
= path_appendnew(p
, nparent
, base
, path
, pathlen
, mode
, sha1
);
224 for (i
= 0; i
< nparent
; ++i
) {
226 * tp[i] is valid, if present and if tp[i]==tp[imin] -
227 * otherwise, we should ignore it.
229 int tpi_valid
= tp
&& !(tp
[i
].entry
.mode
& S_IFXMIN_NEQ
);
231 const unsigned char *sha1_i
;
234 p
->parent
[i
].status
=
235 !t
? DIFF_STATUS_DELETED
:
237 DIFF_STATUS_MODIFIED
:
241 sha1_i
= tp
[i
].entry
.oid
->hash
;
242 mode_i
= tp
[i
].entry
.mode
;
249 p
->parent
[i
].mode
= mode_i
;
250 hashcpy(p
->parent
[i
].oid
.hash
, sha1_i
? sha1_i
: null_sha1
);
255 keep
= opt
->pathchange(opt
, p
);
258 * If a path was filtered or consumed - we don't need to add it
259 * to the list and can reuse its memory, leaving it as
260 * pre-allocated element on the tail.
262 * On the other hand, if path needs to be kept, we need to
263 * correct its .next to NULL, as it was pre-initialized to how
264 * much memory was allocated.
266 * see path_appendnew() for details.
275 const unsigned char **parents_sha1
;
277 FAST_ARRAY_ALLOC(parents_sha1
, nparent
);
278 for (i
= 0; i
< nparent
; ++i
) {
279 /* same rule as in emitthis */
280 int tpi_valid
= tp
&& !(tp
[i
].entry
.mode
& S_IFXMIN_NEQ
);
282 parents_sha1
[i
] = tpi_valid
? tp
[i
].entry
.oid
->hash
286 strbuf_add(base
, path
, pathlen
);
287 strbuf_addch(base
, '/');
288 p
= ll_diff_tree_paths(p
, sha1
, parents_sha1
, nparent
, base
, opt
);
289 FAST_ARRAY_FREE(parents_sha1
, nparent
);
292 strbuf_setlen(base
, old_baselen
);
296 static void skip_uninteresting(struct tree_desc
*t
, struct strbuf
*base
,
297 struct diff_options
*opt
)
299 enum interesting match
;
302 match
= tree_entry_interesting(&t
->entry
, base
, 0, &opt
->pathspec
);
304 if (match
== all_entries_not_interesting
)
308 update_tree_entry(t
);
314 * generate paths for combined diff D(sha1,parents_sha1[])
316 * Resulting paths are appended to combine_diff_path linked list, and also, are
317 * emitted on the go via opt->pathchange() callback, so it is possible to
318 * process the result as batch or incrementally.
320 * The paths are generated scanning new tree and all parents trees
321 * simultaneously, similarly to what diff_tree() was doing for 2 trees.
322 * The theory behind such scan is as follows:
325 * D(T,P1...Pn) calculation scheme
326 * -------------------------------
328 * D(T,P1...Pn) = D(T,P1) ^ ... ^ D(T,Pn) (regarding resulting paths set)
330 * D(T,Pj) - diff between T..Pj
331 * D(T,P1...Pn) - combined diff from T to parents P1,...,Pn
334 * We start from all trees, which are sorted, and compare their entries in
340 * |-| |--| ... |--| imin = argmin(p1...pn)
347 * at any time there could be 3 cases:
353 * Schematic deduction of what every case means, and what to do, follows:
355 * 1) t < p[imin] -> ∀j t ∉ Pj -> "+t" ∈ D(T,Pj) -> D += "+t"; t↓
359 * 2.1) ∃j: pj > p[imin] -> "-p[imin]" ∉ D(T,Pj) -> D += ø; ∀ pi=p[imin] pi↓
360 * 2.2) ∀i pi = p[imin] -> pi ∉ T -> "-pi" ∈ D(T,Pi) -> D += "-p[imin]"; ∀i pi↓
364 * 3.1) ∃j: pj > p[imin] -> "+t" ∈ D(T,Pj) -> only pi=p[imin] remains to investigate
365 * 3.2) pi = p[imin] -> investigate δ(t,pi)
370 * 3.1+3.2) looking at δ(t,pi) ∀i: pi=p[imin] - if all != ø ->
372 * ⎧δ(t,pi) - if pi=p[imin]
374 * ⎩"+t" - if pi>p[imin]
377 * in any case t↓ ∀ pi=p[imin] pi↓
384 * Usual diff D(A,B) is by definition the same as combined diff D(A,[B]),
385 * so this diff paths generator can, and is used, for plain diffs
388 * Please keep attention to the common D(A,[B]) case when working on the
389 * code, in order not to slow it down.
392 * nparent must be > 0.
396 /* ∀ pi=p[imin] pi↓ */
397 static inline void update_tp_entries(struct tree_desc
*tp
, int nparent
)
400 for (i
= 0; i
< nparent
; ++i
)
401 if (!(tp
[i
].entry
.mode
& S_IFXMIN_NEQ
))
402 update_tree_entry(&tp
[i
]);
405 static struct combine_diff_path
*ll_diff_tree_paths(
406 struct combine_diff_path
*p
, const unsigned char *sha1
,
407 const unsigned char **parents_sha1
, int nparent
,
408 struct strbuf
*base
, struct diff_options
*opt
)
410 struct tree_desc t
, *tp
;
411 void *ttree
, **tptree
;
414 FAST_ARRAY_ALLOC(tp
, nparent
);
415 FAST_ARRAY_ALLOC(tptree
, nparent
);
418 * load parents first, as they are probably already cached.
420 * ( log_tree_diff() parses commit->parent before calling here via
421 * diff_tree_sha1(parent, commit) )
423 for (i
= 0; i
< nparent
; ++i
)
424 tptree
[i
] = fill_tree_descriptor(&tp
[i
], parents_sha1
[i
]);
425 ttree
= fill_tree_descriptor(&t
, sha1
);
427 /* Enable recursion indefinitely */
428 opt
->pathspec
.recursive
= DIFF_OPT_TST(opt
, RECURSIVE
);
433 if (diff_can_quit_early(opt
))
436 if (opt
->pathspec
.nr
) {
437 skip_uninteresting(&t
, base
, opt
);
438 for (i
= 0; i
< nparent
; i
++)
439 skip_uninteresting(&tp
[i
], base
, opt
);
442 /* comparing is finished when all trees are done */
445 for (i
= 0; i
< nparent
; ++i
)
455 * lookup imin = argmin(p1...pn),
456 * mark entries whether they =p[imin] along the way
459 tp
[0].entry
.mode
&= ~S_IFXMIN_NEQ
;
461 for (i
= 1; i
< nparent
; ++i
) {
462 cmp
= tree_entry_pathcmp(&tp
[i
], &tp
[imin
]);
465 tp
[i
].entry
.mode
&= ~S_IFXMIN_NEQ
;
468 tp
[i
].entry
.mode
&= ~S_IFXMIN_NEQ
;
471 tp
[i
].entry
.mode
|= S_IFXMIN_NEQ
;
475 /* fixup markings for entries before imin */
476 for (i
= 0; i
< imin
; ++i
)
477 tp
[i
].entry
.mode
|= S_IFXMIN_NEQ
; /* pi > p[imin] */
481 /* compare t vs p[imin] */
482 cmp
= tree_entry_pathcmp(&t
, &tp
[imin
]);
486 /* are either pi > p[imin] or diff(t,pi) != ø ? */
487 if (!DIFF_OPT_TST(opt
, FIND_COPIES_HARDER
)) {
488 for (i
= 0; i
< nparent
; ++i
) {
490 if (tp
[i
].entry
.mode
& S_IFXMIN_NEQ
)
493 /* diff(t,pi) != ø */
494 if (oidcmp(t
.entry
.oid
, tp
[i
].entry
.oid
) ||
495 (t
.entry
.mode
!= tp
[i
].entry
.mode
))
502 /* D += {δ(t,pi) if pi=p[imin]; "+a" if pi > p[imin]} */
503 p
= emit_path(p
, base
, opt
, nparent
,
507 /* t↓, ∀ pi=p[imin] pi↓ */
508 update_tree_entry(&t
);
509 update_tp_entries(tp
, nparent
);
515 p
= emit_path(p
, base
, opt
, nparent
,
516 &t
, /*tp=*/NULL
, -1);
519 update_tree_entry(&t
);
524 /* ∀i pi=p[imin] -> D += "-p[imin]" */
525 if (!DIFF_OPT_TST(opt
, FIND_COPIES_HARDER
)) {
526 for (i
= 0; i
< nparent
; ++i
)
527 if (tp
[i
].entry
.mode
& S_IFXMIN_NEQ
)
531 p
= emit_path(p
, base
, opt
, nparent
,
532 /*t=*/NULL
, tp
, imin
);
535 /* ∀ pi=p[imin] pi↓ */
536 update_tp_entries(tp
, nparent
);
541 for (i
= nparent
-1; i
>= 0; i
--)
543 FAST_ARRAY_FREE(tptree
, nparent
);
544 FAST_ARRAY_FREE(tp
, nparent
);
549 struct combine_diff_path
*diff_tree_paths(
550 struct combine_diff_path
*p
, const unsigned char *sha1
,
551 const unsigned char **parents_sha1
, int nparent
,
552 struct strbuf
*base
, struct diff_options
*opt
)
554 p
= ll_diff_tree_paths(p
, sha1
, parents_sha1
, nparent
, base
, opt
);
557 * free pre-allocated last element, if any
558 * (see path_appendnew() for details about why)
561 FREE_AND_NULL(p
->next
);
568 * Does it look like the resulting diff might be due to a rename?
570 * - not a valid previous file
572 static inline int diff_might_be_rename(void)
574 return diff_queued_diff
.nr
== 1 &&
575 !DIFF_FILE_VALID(diff_queued_diff
.queue
[0]->one
);
578 static void try_to_follow_renames(const unsigned char *old
, const unsigned char *new, struct strbuf
*base
, struct diff_options
*opt
)
580 struct diff_options diff_opts
;
581 struct diff_queue_struct
*q
= &diff_queued_diff
;
582 struct diff_filepair
*choice
;
586 * follow-rename code is very specific, we need exactly one
587 * path. Magic that matches more than one path is not
590 GUARD_PATHSPEC(&opt
->pathspec
, PATHSPEC_FROMTOP
| PATHSPEC_LITERAL
);
593 * We should reject wildcards as well. Unfortunately we
594 * haven't got a reliable way to detect that 'foo\*bar' in
595 * fact has no wildcards. nowildcard_len is merely a hint for
596 * optimization. Let it slip for now until wildmatch is taught
597 * about dry-run mode and returns wildcard info.
599 if (opt
->pathspec
.has_wildcard
)
600 die("BUG:%s:%d: wildcards are not supported",
604 /* Remove the file creation entry from the diff queue, and remember it */
605 choice
= q
->queue
[0];
608 diff_setup(&diff_opts
);
609 DIFF_OPT_SET(&diff_opts
, RECURSIVE
);
610 DIFF_OPT_SET(&diff_opts
, FIND_COPIES_HARDER
);
611 diff_opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
612 diff_opts
.single_follow
= opt
->pathspec
.items
[0].match
;
613 diff_opts
.break_opt
= opt
->break_opt
;
614 diff_opts
.rename_score
= opt
->rename_score
;
615 diff_setup_done(&diff_opts
);
616 ll_diff_tree_sha1(old
, new, base
, &diff_opts
);
617 diffcore_std(&diff_opts
);
618 clear_pathspec(&diff_opts
.pathspec
);
620 /* Go through the new set of filepairing, and see if we find a more interesting one */
621 opt
->found_follow
= 0;
622 for (i
= 0; i
< q
->nr
; i
++) {
623 struct diff_filepair
*p
= q
->queue
[i
];
626 * Found a source? Not only do we use that for the new
627 * diff_queued_diff, we will also use that as the path in
630 if ((p
->status
== 'R' || p
->status
== 'C') &&
631 !strcmp(p
->two
->path
, opt
->pathspec
.items
[0].match
)) {
634 /* Switch the file-pairs around */
635 q
->queue
[i
] = choice
;
638 /* Update the path we use from now on.. */
639 path
[0] = p
->one
->path
;
641 clear_pathspec(&opt
->pathspec
);
642 parse_pathspec(&opt
->pathspec
,
643 PATHSPEC_ALL_MAGIC
& ~PATHSPEC_LITERAL
,
644 PATHSPEC_LITERAL_PATH
, "", path
);
647 * The caller expects us to return a set of vanilla
648 * filepairs to let a later call to diffcore_std()
649 * it makes to sort the renames out (among other
650 * things), but we already have found renames
651 * ourselves; signal diffcore_std() not to muck with
652 * rename information.
654 opt
->found_follow
= 1;
660 * Then, discard all the non-relevant file pairs...
662 for (i
= 0; i
< q
->nr
; i
++) {
663 struct diff_filepair
*p
= q
->queue
[i
];
664 diff_free_filepair(p
);
668 * .. and re-instate the one we want (which might be either the
669 * original one, or the rename/copy we found)
671 q
->queue
[0] = choice
;
675 static int ll_diff_tree_sha1(const unsigned char *old
, const unsigned char *new,
676 struct strbuf
*base
, struct diff_options
*opt
)
678 struct combine_diff_path phead
, *p
;
679 pathchange_fn_t pathchange_old
= opt
->pathchange
;
682 opt
->pathchange
= emit_diff_first_parent_only
;
683 diff_tree_paths(&phead
, new, &old
, 1, base
, opt
);
685 for (p
= phead
.next
; p
;) {
686 struct combine_diff_path
*pprev
= p
;
691 opt
->pathchange
= pathchange_old
;
695 int diff_tree_sha1(const unsigned char *old
, const unsigned char *new, const char *base_str
, struct diff_options
*opt
)
700 strbuf_init(&base
, PATH_MAX
);
701 strbuf_addstr(&base
, base_str
);
703 retval
= ll_diff_tree_sha1(old
, new, &base
, opt
);
704 if (!*base_str
&& DIFF_OPT_TST(opt
, FOLLOW_RENAMES
) && diff_might_be_rename())
705 try_to_follow_renames(old
, new, &base
, opt
);
707 strbuf_release(&base
);
712 int diff_root_tree_sha1(const unsigned char *new, const char *base
, struct diff_options
*opt
)
714 return diff_tree_sha1(NULL
, new, base
, opt
);