Merge branch 'sb/submodule-recommend-shallowness'
[alt-git.git] / tree-diff.c
blobff4e0d3cb60b51080d2f6100e38d1476e6eb6dcf
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"
9 /*
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
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);
26 * Compare two tree entries, taking into account only path/S_ISDIR(mode),
27 * but not their sha1's.
29 * NOTE files and directories *always* compare differently, even when having
30 * the same name - thanks to base_name_compare().
32 * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty,
33 * so that they sort *after* valid tree entries.
35 * Due to this convention, if trees are scanned in sorted order, all
36 * non-empty descriptors will be processed first.
38 static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
40 struct name_entry *e1, *e2;
41 int cmp;
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;
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;
58 * convert path -> opt->diff_*() callbacks
60 * emits diff to first parent only, and tells diff tree-walker that we are done
61 * with p and it can be freed.
63 static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_diff_path *p)
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);
70 else {
71 const unsigned char *sha1;
72 unsigned int mode;
73 int addremove;
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;
85 opt->add_remove(opt, addremove, mode, sha1, 1, p->path, 0);
88 return 0; /* we are done with p */
93 * Make a new combine_diff_path from path/mode/sha1
94 * and append it to paths list tail.
96 * Memory for created elements could be reused:
98 * - if last->next == NULL, the memory is allocated;
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.
104 * so for clients,
106 * - if you do need to keep the element
108 * p = path_appendnew(p, ...);
109 * process(p);
110 * p->next = NULL;
112 * - if you don't need to keep the element after processing
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
120 * p->parent[] remains uninitialized.
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)
126 struct combine_diff_path *p;
127 size_t len = st_add(base->len, pathlen);
128 size_t alloclen = combine_diff_path_size(nparent, len);
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;
137 if (!p) {
138 p = xmalloc(alloclen);
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).
144 p->next = (struct combine_diff_path *)(intptr_t)alloclen;
147 last->next = p;
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);
156 return p;
160 * new path should be added to combine diff
162 * 3 cases on how/when it should be called and behaves:
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)
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)
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;
181 /* at least something has to be valid */
182 assert(t || tp);
184 if (t) {
185 /* path present in resulting tree */
186 sha1 = tree_entry_extract(t, &path, &mode)->hash;
187 pathlen = tree_entry_len(&t->entry);
188 isdir = S_ISDIR(mode);
189 } else {
191 * a path was removed - take path from imin parent. Also take
192 * mode from that parent, to decide on recursion(1).
194 * 1) all modes for tp[i]=tp[imin] should be the same wrt
195 * S_ISDIR, thanks to base_name_compare().
197 tree_entry_extract(&tp[imin], &path, &mode);
198 pathlen = tree_entry_len(&tp[imin].entry);
200 isdir = S_ISDIR(mode);
201 sha1 = NULL;
202 mode = 0;
205 if (DIFF_OPT_TST(opt, RECURSIVE) && isdir) {
206 recurse = 1;
207 emitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE);
210 if (emitthis) {
211 int keep;
212 struct combine_diff_path *pprev = p;
213 p = path_appendnew(p, nparent, base, path, pathlen, mode, sha1);
215 for (i = 0; i < nparent; ++i) {
217 * tp[i] is valid, if present and if tp[i]==tp[imin] -
218 * otherwise, we should ignore it.
220 int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);
222 const unsigned char *sha1_i;
223 unsigned mode_i;
225 p->parent[i].status =
226 !t ? DIFF_STATUS_DELETED :
227 tpi_valid ?
228 DIFF_STATUS_MODIFIED :
229 DIFF_STATUS_ADDED;
231 if (tpi_valid) {
232 sha1_i = tp[i].entry.oid->hash;
233 mode_i = tp[i].entry.mode;
235 else {
236 sha1_i = NULL;
237 mode_i = 0;
240 p->parent[i].mode = mode_i;
241 hashcpy(p->parent[i].oid.hash, sha1_i ? sha1_i : null_sha1);
244 keep = 1;
245 if (opt->pathchange)
246 keep = opt->pathchange(opt, p);
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.
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.
257 * see path_appendnew() for details.
259 if (!keep)
260 p = pprev;
261 else
262 p->next = NULL;
265 if (recurse) {
266 const unsigned char **parents_sha1;
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);
273 parents_sha1[i] = tpi_valid ? tp[i].entry.oid->hash
274 : NULL;
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);
283 strbuf_setlen(base, old_baselen);
284 return p;
287 static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
288 struct diff_options *opt)
290 enum interesting match;
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;
299 update_tree_entry(t);
305 * generate paths for combined diff D(sha1,parents_sha1[])
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.
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:
316 * D(T,P1...Pn) calculation scheme
317 * -------------------------------
319 * D(T,P1...Pn) = D(T,P1) ^ ... ^ D(T,Pn) (regarding resulting paths set)
321 * D(T,Pj) - diff between T..Pj
322 * D(T,P1...Pn) - combined diff from T to parents P1,...,Pn
325 * We start from all trees, which are sorted, and compare their entries in
326 * lock-step:
328 * T P1 Pn
329 * - - -
330 * |t| |p1| |pn|
331 * |-| |--| ... |--| imin = argmin(p1...pn)
332 * | | | | | |
333 * |-| |--| |--|
334 * |.| |. | |. |
335 * . . .
336 * . . .
338 * at any time there could be 3 cases:
340 * 1) t < p[imin];
341 * 2) t > p[imin];
342 * 3) t = p[imin].
344 * Schematic deduction of what every case means, and what to do, follows:
346 * 1) t < p[imin] -> ∀j t ∉ Pj -> "+t" ∈ D(T,Pj) -> D += "+t"; t↓
348 * 2) t > p[imin]
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↓
353 * 3) t = p[imin]
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)
361 * 3.1+3.2) looking at δ(t,pi) ∀i: pi=p[imin] - if all != ø ->
363 * ⎧δ(t,pi) - if pi=p[imin]
364 * -> D += ⎨
365 * ⎩"+t" - if pi>p[imin]
368 * in any case t↓ ∀ pi=p[imin] pi↓
371 * ~~~~~~~~
373 * NOTE
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.
379 * Please keep attention to the common D(A,[B]) case when working on the
380 * code, in order not to slow it down.
382 * NOTE
383 * nparent must be > 0.
387 /* ∀ pi=p[imin] pi↓ */
388 static inline void update_tp_entries(struct tree_desc *tp, int nparent)
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]);
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)
401 struct tree_desc t, *tp;
402 void *ttree, **tptree;
403 int i;
405 tp = xalloca(nparent * sizeof(tp[0]));
406 tptree = xalloca(nparent * sizeof(tptree[0]));
409 * load parents first, as they are probably already cached.
411 * ( log_tree_diff() parses commit->parent before calling here via
412 * diff_tree_sha1(parent, commit) )
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);
418 /* Enable recursion indefinitely */
419 opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
421 for (;;) {
422 int imin, cmp;
424 if (diff_can_quit_early(opt))
425 break;
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);
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;
441 if (done)
442 break;
446 * lookup imin = argmin(p1...pn),
447 * mark entries whether they =p[imin] along the way
449 imin = 0;
450 tp[0].entry.mode &= ~S_IFXMIN_NEQ;
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;
458 else if (cmp == 0) {
459 tp[i].entry.mode &= ~S_IFXMIN_NEQ;
461 else {
462 tp[i].entry.mode |= S_IFXMIN_NEQ;
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] */
472 /* compare t vs p[imin] */
473 cmp = tree_entry_pathcmp(&t, &tp[imin]);
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;
484 /* diff(t,pi) != ø */
485 if (oidcmp(t.entry.oid, tp[i].entry.oid) ||
486 (t.entry.mode != tp[i].entry.mode))
487 continue;
489 goto skip_emit_t_tp;
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);
497 skip_emit_t_tp:
498 /* t↓, ∀ pi=p[imin] pi↓ */
499 update_tree_entry(&t);
500 update_tp_entries(tp, nparent);
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);
509 /* t↓ */
510 update_tree_entry(&t);
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;
522 p = emit_path(p, base, opt, nparent,
523 /*t=*/NULL, tp, imin);
525 skip_emit_tp:
526 /* ∀ pi=p[imin] pi↓ */
527 update_tp_entries(tp, nparent);
531 free(ttree);
532 for (i = nparent-1; i >= 0; i--)
533 free(tptree[i]);
534 xalloca_free(tptree);
535 xalloca_free(tp);
537 return p;
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)
545 p = ll_diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);
548 * free pre-allocated last element, if any
549 * (see path_appendnew() for details about why)
551 if (p->next) {
552 free(p->next);
553 p->next = NULL;
556 return p;
560 * Does it look like the resulting diff might be due to a rename?
561 * - single entry
562 * - not a valid previous file
564 static inline int diff_might_be_rename(void)
566 return diff_queued_diff.nr == 1 &&
567 !DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
570 static void try_to_follow_renames(const unsigned char *old, const unsigned char *new, struct strbuf *base, struct diff_options *opt)
572 struct diff_options diff_opts;
573 struct diff_queue_struct *q = &diff_queued_diff;
574 struct diff_filepair *choice;
575 int i;
578 * follow-rename code is very specific, we need exactly one
579 * path. Magic that matches more than one path is not
580 * supported.
582 GUARD_PATHSPEC(&opt->pathspec, PATHSPEC_FROMTOP | PATHSPEC_LITERAL);
583 #if 0
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.
591 if (opt->pathspec.has_wildcard)
592 die("BUG:%s:%d: wildcards are not supported",
593 __FILE__, __LINE__);
594 #endif
596 /* Remove the file creation entry from the diff queue, and remember it */
597 choice = q->queue[0];
598 q->nr = 0;
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);
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];
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!
622 if ((p->status == 'R' || p->status == 'C') &&
623 !strcmp(p->two->path, opt->pathspec.items[0].match)) {
624 const char *path[2];
626 /* Switch the file-pairs around */
627 q->queue[i] = choice;
628 choice = p;
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);
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.
646 opt->found_follow = 1;
647 break;
652 * Then, discard all the non-relevant file pairs...
654 for (i = 0; i < q->nr; i++) {
655 struct diff_filepair *p = q->queue[i];
656 diff_free_filepair(p);
660 * .. and re-instate the one we want (which might be either the
661 * original one, or the rename/copy we found)
663 q->queue[0] = choice;
664 q->nr = 1;
667 static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
668 struct strbuf *base, struct diff_options *opt)
670 struct combine_diff_path phead, *p;
671 pathchange_fn_t pathchange_old = opt->pathchange;
673 phead.next = NULL;
674 opt->pathchange = emit_diff_first_parent_only;
675 diff_tree_paths(&phead, new, &old, 1, base, opt);
677 for (p = phead.next; p;) {
678 struct combine_diff_path *pprev = p;
679 p = p->next;
680 free(pprev);
683 opt->pathchange = pathchange_old;
684 return 0;
687 int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base_str, struct diff_options *opt)
689 struct strbuf base;
690 int retval;
692 strbuf_init(&base, PATH_MAX);
693 strbuf_addstr(&base, base_str);
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);
699 strbuf_release(&base);
701 return retval;
704 int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)
706 return diff_tree_sha1(NULL, new, base, opt);