ls-tree: disable negative pathspec because it's not supported
[git] / 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->sha1, p->sha1,
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->sha1;
78                         mode = p->mode;
79                 } else {
80                         addremove = '-';
81                         sha1 = p0->sha1;
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->sha1, 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].sha1, 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 }