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