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 static void show_entry(struct diff_options *opt, const char *prefix,
  10                        struct tree_desc *desc, struct strbuf *base);
  11
  12 static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
  13                               struct strbuf *base, struct diff_options *opt)
  14 {
  15         unsigned mode1, mode2;
  16         const char *path1, *path2;
  17         const unsigned char *sha1, *sha2;
  18         int cmp, pathlen1, pathlen2;
  19         int old_baselen = base->len;
  20
  21         sha1 = tree_entry_extract(t1, &path1, &mode1);
  22         sha2 = tree_entry_extract(t2, &path2, &mode2);
  23
  24         pathlen1 = tree_entry_len(&t1->entry);
  25         pathlen2 = tree_entry_len(&t2->entry);
  26
  27         /*
  28          * NOTE files and directories *always* compare differently,
  29          * even when having the same name.
  30          */
  31         cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
  32         if (cmp < 0) {
  33                 show_entry(opt, "-", t1, base);
  34                 return -1;
  35         }
  36         if (cmp > 0) {
  37                 show_entry(opt, "+", t2, base);
  38                 return 1;
  39         }
  40         if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)
  41                 return 0;
  42
  43         strbuf_add(base, path1, pathlen1);
  44         if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode1)) {
  45                 if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE)) {
  46                         opt->change(opt, mode1, mode2,
  47                                     sha1, sha2, 1, 1, base->buf, 0, 0);
  48                 }
  49                 strbuf_addch(base, '/');
  50                 diff_tree_sha1(sha1, sha2, base->buf, opt);
  51         } else {
  52                 opt->change(opt, mode1, mode2, sha1, sha2, 1, 1, base->buf, 0, 0);
  53         }
  54         strbuf_setlen(base, old_baselen);
  55         return 0;
  56 }
  57
  58 /* An entry went away or appeared */
  59 static void show_entry(struct diff_options *opt, const char *prefix,
  60                        struct tree_desc *desc, struct strbuf *base)
  61 {
  62         unsigned mode;
  63         const char *path;
  64         const unsigned char *sha1 = tree_entry_extract(desc, &path, &mode);
  65         int pathlen = tree_entry_len(&desc->entry);
  66         int old_baselen = base->len;
  67
  68         strbuf_add(base, path, pathlen);
  69         if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode)) {
  70                 if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE))
  71                         opt->add_remove(opt, *prefix, mode, sha1, 1, base->buf, 0);
  72
  73                 strbuf_addch(base, '/');
  74                 diff_tree_sha1(*prefix == '-' ? sha1 : NULL,
  75                                *prefix == '+' ? sha1 : NULL, base->buf, opt);
  76         } else
  77                 opt->add_remove(opt, prefix[0], mode, sha1, 1, base->buf, 0);
  78
  79         strbuf_setlen(base, old_baselen);
  80 }
  81
  82 static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
  83                                struct diff_options *opt)
  84 {
  85         enum interesting match;
  86
  87         while (t->size) {
  88                 match = tree_entry_interesting(&t->entry, base, 0, &opt->pathspec);
  89                 if (match) {
  90                         if (match == all_entries_not_interesting)
  91                                 t->size = 0;
  92                         break;
  93                 }
  94                 update_tree_entry(t);
  95         }
  96 }
  97
  98 int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
  99               const char *base_str, struct diff_options *opt)
 100 {
 101         struct strbuf base;
 102         int baselen = strlen(base_str);
 103
 104         /* Enable recursion indefinitely */
 105         opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
 106
 107         strbuf_init(&base, PATH_MAX);
 108         strbuf_add(&base, base_str, baselen);
 109
 110         for (;;) {
 111                 if (diff_can_quit_early(opt))
 112                         break;
 113                 if (opt->pathspec.nr) {
 114                         skip_uninteresting(t1, &base, opt);
 115                         skip_uninteresting(t2, &base, opt);
 116                 }
 117                 if (!t1->size) {
 118                         if (!t2->size)
 119                                 break;
 120                         show_entry(opt, "+", t2, &base);
 121                         update_tree_entry(t2);
 122                         continue;
 123                 }
 124                 if (!t2->size) {
 125                         show_entry(opt, "-", t1, &base);
 126                         update_tree_entry(t1);
 127                         continue;
 128                 }
 129                 switch (compare_tree_entry(t1, t2, &base, opt)) {
 130                 case -1:
 131                         update_tree_entry(t1);
 132                         continue;
 133                 case 0:
 134                         update_tree_entry(t1);
 135                         /* Fallthrough */
 136                 case 1:
 137                         update_tree_entry(t2);
 138                         continue;
 139                 }
 140                 die("git diff-tree: internal error");
 141         }
 142
 143         strbuf_release(&base);
 144         return 0;
 145 }
 146
 147 /*
 148  * Does it look like the resulting diff might be due to a rename?
 149  *  - single entry
 150  *  - not a valid previous file
 151  */
 152 static inline int diff_might_be_rename(void)
 153 {
 154         return diff_queued_diff.nr == 1 &&
 155                 !DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
 156 }
 157
 158 static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
 159 {
 160         struct diff_options diff_opts;
 161         struct diff_queue_struct *q = &diff_queued_diff;
 162         struct diff_filepair *choice;
 163         int i;
 164
 165         /*
 166          * follow-rename code is very specific, we need exactly one
 167          * path. Magic that matches more than one path is not
 168          * supported.
 169          */
 170         GUARD_PATHSPEC(&opt->pathspec, PATHSPEC_FROMTOP | PATHSPEC_LITERAL);
 171 #if 0
 172         /*
 173          * We should reject wildcards as well. Unfortunately we
 174          * haven't got a reliable way to detect that 'foo\*bar' in
 175          * fact has no wildcards. nowildcard_len is merely a hint for
 176          * optimization. Let it slip for now until wildmatch is taught
 177          * about dry-run mode and returns wildcard info.
 178          */
 179         if (opt->pathspec.has_wildcard)
 180                 die("BUG:%s:%d: wildcards are not supported",
 181                     __FILE__, __LINE__);
 182 #endif
 183
 184         /* Remove the file creation entry from the diff queue, and remember it */
 185         choice = q->queue[0];
 186         q->nr = 0;
 187
 188         diff_setup(&diff_opts);
 189         DIFF_OPT_SET(&diff_opts, RECURSIVE);
 190         DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
 191         diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 192         diff_opts.single_follow = opt->pathspec.items[0].match;
 193         diff_opts.break_opt = opt->break_opt;
 194         diff_opts.rename_score = opt->rename_score;
 195         diff_setup_done(&diff_opts);
 196         diff_tree(t1, t2, base, &diff_opts);
 197         diffcore_std(&diff_opts);
 198         free_pathspec(&diff_opts.pathspec);
 199
 200         /* Go through the new set of filepairing, and see if we find a more interesting one */
 201         opt->found_follow = 0;
 202         for (i = 0; i < q->nr; i++) {
 203                 struct diff_filepair *p = q->queue[i];
 204
 205                 /*
 206                  * Found a source? Not only do we use that for the new
 207                  * diff_queued_diff, we will also use that as the path in
 208                  * the future!
 209                  */
 210                 if ((p->status == 'R' || p->status == 'C') &&
 211                     !strcmp(p->two->path, opt->pathspec.items[0].match)) {
 212                         const char *path[2];
 213
 214                         /* Switch the file-pairs around */
 215                         q->queue[i] = choice;
 216                         choice = p;
 217
 218                         /* Update the path we use from now on.. */
 219                         path[0] = p->one->path;
 220                         path[1] = NULL;
 221                         free_pathspec(&opt->pathspec);
 222                         parse_pathspec(&opt->pathspec,
 223                                        PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,
 224                                        PATHSPEC_LITERAL_PATH, "", path);
 225
 226                         /*
 227                          * The caller expects us to return a set of vanilla
 228                          * filepairs to let a later call to diffcore_std()
 229                          * it makes to sort the renames out (among other
 230                          * things), but we already have found renames
 231                          * ourselves; signal diffcore_std() not to muck with
 232                          * rename information.
 233                          */
 234                         opt->found_follow = 1;
 235                         break;
 236                 }
 237         }
 238
 239         /*
 240          * Then, discard all the non-relevant file pairs...
 241          */
 242         for (i = 0; i < q->nr; i++) {
 243                 struct diff_filepair *p = q->queue[i];
 244                 diff_free_filepair(p);
 245         }
 246
 247         /*
 248          * .. and re-instate the one we want (which might be either the
 249          * original one, or the rename/copy we found)
 250          */
 251         q->queue[0] = choice;
 252         q->nr = 1;
 253 }
 254
 255 int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
 256 {
 257         void *tree1, *tree2;
 258         struct tree_desc t1, t2;
 259         unsigned long size1, size2;
 260         int retval;
 261
 262         tree1 = fill_tree_descriptor(&t1, old);
 263         tree2 = fill_tree_descriptor(&t2, new);
 264         size1 = t1.size;
 265         size2 = t2.size;
 266         retval = diff_tree(&t1, &t2, base, opt);
 267         if (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename()) {
 268                 init_tree_desc(&t1, tree1, size1);
 269                 init_tree_desc(&t2, tree2, size2);
 270                 try_to_follow_renames(&t1, &t2, base, opt);
 271         }
 272         free(tree1);
 273         free(tree2);
 274         return retval;
 275 }
 276
 277 int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)
 278 {
 279         return diff_tree_sha1(NULL, new, base, opt);
 280 }