tree-diff.con commit Merge branch 'as/api-allocation-doc' into maint (ab60f2c)
   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        opt->pathspec.max_depth = -1;
 142
 143        strbuf_init(&base, PATH_MAX);
 144        strbuf_add(&base, base_str, baselen);
 145
 146        for (;;) {
 147                if (diff_can_quit_early(opt))
 148                        break;
 149                if (opt->pathspec.nr) {
 150                        skip_uninteresting(t1, &base, opt, &t1_match);
 151                        skip_uninteresting(t2, &base, opt, &t2_match);
 152                }
 153                if (!t1->size) {
 154                        if (!t2->size)
 155                                break;
 156                        show_entry(opt, "+", t2, &base);
 157                        update_tree_entry(t2);
 158                        continue;
 159                }
 160                if (!t2->size) {
 161                        show_entry(opt, "-", t1, &base);
 162                        update_tree_entry(t1);
 163                        continue;
 164                }
 165                switch (compare_tree_entry(t1, t2, &base, opt)) {
 166                case -1:
 167                        update_tree_entry(t1);
 168                        continue;
 169                case 0:
 170                        update_tree_entry(t1);
 171                        /* Fallthrough */
 172                case 1:
 173                        update_tree_entry(t2);
 174                        continue;
 175                }
 176                die("git diff-tree: internal error");
 177        }
 178
 179        strbuf_release(&base);
 180        return 0;
 181}
 182
 183/*
 184 * Does it look like the resulting diff might be due to a rename?
 185 *  - single entry
 186 *  - not a valid previous file
 187 */
 188static inline int diff_might_be_rename(void)
 189{
 190        return diff_queued_diff.nr == 1 &&
 191                !DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
 192}
 193
 194static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
 195{
 196        struct diff_options diff_opts;
 197        struct diff_queue_struct *q = &diff_queued_diff;
 198        struct diff_filepair *choice;
 199        const char *paths[1];
 200        int i;
 201
 202        /* Remove the file creation entry from the diff queue, and remember it */
 203        choice = q->queue[0];
 204        q->nr = 0;
 205
 206        diff_setup(&diff_opts);
 207        DIFF_OPT_SET(&diff_opts, RECURSIVE);
 208        DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
 209        diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 210        diff_opts.single_follow = opt->pathspec.raw[0];
 211        diff_opts.break_opt = opt->break_opt;
 212        diff_opts.rename_score = opt->rename_score;
 213        paths[0] = NULL;
 214        diff_tree_setup_paths(paths, &diff_opts);
 215        diff_setup_done(&diff_opts);
 216        diff_tree(t1, t2, base, &diff_opts);
 217        diffcore_std(&diff_opts);
 218        diff_tree_release_paths(&diff_opts);
 219
 220        /* Go through the new set of filepairing, and see if we find a more interesting one */
 221        opt->found_follow = 0;
 222        for (i = 0; i < q->nr; i++) {
 223                struct diff_filepair *p = q->queue[i];
 224
 225                /*
 226                 * Found a source? Not only do we use that for the new
 227                 * diff_queued_diff, we will also use that as the path in
 228                 * the future!
 229                 */
 230                if ((p->status == 'R' || p->status == 'C') &&
 231                    !strcmp(p->two->path, opt->pathspec.raw[0])) {
 232                        /* Switch the file-pairs around */
 233                        q->queue[i] = choice;
 234                        choice = p;
 235
 236                        /* Update the path we use from now on.. */
 237                        diff_tree_release_paths(opt);
 238                        opt->pathspec.raw[0] = xstrdup(p->one->path);
 239                        diff_tree_setup_paths(opt->pathspec.raw, opt);
 240
 241                        /*
 242                         * The caller expects us to return a set of vanilla
 243                         * filepairs to let a later call to diffcore_std()
 244                         * it makes to sort the renames out (among other
 245                         * things), but we already have found renames
 246                         * ourselves; signal diffcore_std() not to muck with
 247                         * rename information.
 248                         */
 249                        opt->found_follow = 1;
 250                        break;
 251                }
 252        }
 253
 254        /*
 255         * Then, discard all the non-relevant file pairs...
 256         */
 257        for (i = 0; i < q->nr; i++) {
 258                struct diff_filepair *p = q->queue[i];
 259                diff_free_filepair(p);
 260        }
 261
 262        /*
 263         * .. and re-instate the one we want (which might be either the
 264         * original one, or the rename/copy we found)
 265         */
 266        q->queue[0] = choice;
 267        q->nr = 1;
 268}
 269
 270int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
 271{
 272        void *tree1, *tree2;
 273        struct tree_desc t1, t2;
 274        unsigned long size1, size2;
 275        int retval;
 276
 277        tree1 = read_object_with_reference(old, tree_type, &size1, NULL);
 278        if (!tree1)
 279                die("unable to read source tree (%s)", sha1_to_hex(old));
 280        tree2 = read_object_with_reference(new, tree_type, &size2, NULL);
 281        if (!tree2)
 282                die("unable to read destination tree (%s)", sha1_to_hex(new));
 283        init_tree_desc(&t1, tree1, size1);
 284        init_tree_desc(&t2, tree2, size2);
 285        retval = diff_tree(&t1, &t2, base, opt);
 286        if (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename()) {
 287                init_tree_desc(&t1, tree1, size1);
 288                init_tree_desc(&t2, tree2, size2);
 289                try_to_follow_renames(&t1, &t2, base, opt);
 290        }
 291        free(tree1);
 292        free(tree2);
 293        return retval;
 294}
 295
 296int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)
 297{
 298        int retval;
 299        void *tree;
 300        unsigned long size;
 301        struct tree_desc empty, real;
 302
 303        tree = read_object_with_reference(new, tree_type, &size, NULL);
 304        if (!tree)
 305                die("unable to read root tree (%s)", sha1_to_hex(new));
 306        init_tree_desc(&real, tree, size);
 307
 308        init_tree_desc(&empty, "", 0);
 309        retval = diff_tree(&empty, &real, base, opt);
 310        free(tree);
 311        return retval;
 312}
 313
 314void diff_tree_release_paths(struct diff_options *opt)
 315{
 316        free_pathspec(&opt->pathspec);
 317}
 318
 319void diff_tree_setup_paths(const char **p, struct diff_options *opt)
 320{
 321        init_pathspec(&opt->pathspec, p);
 322}