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