Andrew's git - gitweb.git/blob

   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(path1, sha1);
  25        pathlen2 = tree_entry_len(path2, sha2);
  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, 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, 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        int match = 0;
  68        for (; desc->size; update_tree_entry(desc)) {
  69                if (match != 2) {
  70                        match = tree_entry_interesting(&desc->entry, base, 0,
  71                                                       &opt->pathspec);
  72                        if (match < 0)
  73                                break;
  74                        if (match == 0)
  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(path, sha1);
  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, 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, 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, int *match)
 118{
 119        while (t->size) {
 120                *match = tree_entry_interesting(&t->entry, base, 0, &opt->pathspec);
 121                if (*match) {
 122                        if (*match < 0)
 123                                t->size = 0;
 124                        break;
 125                }
 126                update_tree_entry(t);
 127        }
 128}
 129
 130int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 131              const char *base_str, struct diff_options *opt)
 132{
 133        struct strbuf base;
 134        int baselen = strlen(base_str);
 135        int t1_match = 0, t2_match = 0;
 136
 137        /* Enable recursion indefinitely */
 138        opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
 139        opt->pathspec.max_depth = -1;
 140
 141        strbuf_init(&base, PATH_MAX);
 142        strbuf_add(&base, base_str, baselen);
 143
 144        for (;;) {
 145                if (DIFF_OPT_TST(opt, QUICK) &&
 146                    DIFF_OPT_TST(opt, HAS_CHANGES))
 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        const char *paths[1];
 199        int i;
 200
 201        /* Remove the file creation entry from the diff queue, and remember it */
 202        choice = q->queue[0];
 203        q->nr = 0;
 204
 205        diff_setup(&diff_opts);
 206        DIFF_OPT_SET(&diff_opts, RECURSIVE);
 207        DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
 208        diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 209        diff_opts.single_follow = opt->pathspec.raw[0];
 210        diff_opts.break_opt = opt->break_opt;
 211        paths[0] = NULL;
 212        diff_tree_setup_paths(paths, &diff_opts);
 213        if (diff_setup_done(&diff_opts) < 0)
 214                die("unable to set up diff options to follow renames");
 215        diff_tree(t1, t2, base, &diff_opts);
 216        diffcore_std(&diff_opts);
 217        diff_tree_release_paths(&diff_opts);
 218
 219        /* Go through the new set of filepairing, and see if we find a more interesting one */
 220        opt->found_follow = 0;
 221        for (i = 0; i < q->nr; i++) {
 222                struct diff_filepair *p = q->queue[i];
 223
 224                /*
 225                 * Found a source? Not only do we use that for the new
 226                 * diff_queued_diff, we will also use that as the path in
 227                 * the future!
 228                 */
 229                if ((p->status == 'R' || p->status == 'C') &&
 230                    !strcmp(p->two->path, opt->pathspec.raw[0])) {
 231                        /* Switch the file-pairs around */
 232                        q->queue[i] = choice;
 233                        choice = p;
 234
 235                        /* Update the path we use from now on.. */
 236                        diff_tree_release_paths(opt);
 237                        opt->pathspec.raw[0] = xstrdup(p->one->path);
 238                        diff_tree_setup_paths(opt->pathspec.raw, opt);
 239
 240                        /*
 241                         * The caller expects us to return a set of vanilla
 242                         * filepairs to let a later call to diffcore_std()
 243                         * it makes to sort the renames out (among other
 244                         * things), but we already have found renames
 245                         * ourselves; signal diffcore_std() not to muck with
 246                         * rename information.
 247                         */
 248                        opt->found_follow = 1;
 249                        break;
 250                }
 251        }
 252
 253        /*
 254         * Then, discard all the non-relevant file pairs...
 255         */
 256        for (i = 0; i < q->nr; i++) {
 257                struct diff_filepair *p = q->queue[i];
 258                diff_free_filepair(p);
 259        }
 260
 261        /*
 262         * .. and re-instate the one we want (which might be either the
 263         * original one, or the rename/copy we found)
 264         */
 265        q->queue[0] = choice;
 266        q->nr = 1;
 267}
 268
 269int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
 270{
 271        void *tree1, *tree2;
 272        struct tree_desc t1, t2;
 273        unsigned long size1, size2;
 274        int retval;
 275
 276        tree1 = read_object_with_reference(old, tree_type, &size1, NULL);
 277        if (!tree1)
 278                die("unable to read source tree (%s)", sha1_to_hex(old));
 279        tree2 = read_object_with_reference(new, tree_type, &size2, NULL);
 280        if (!tree2)
 281                die("unable to read destination tree (%s)", sha1_to_hex(new));
 282        init_tree_desc(&t1, tree1, size1);
 283        init_tree_desc(&t2, tree2, size2);
 284        retval = diff_tree(&t1, &t2, base, opt);
 285        if (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename()) {
 286                init_tree_desc(&t1, tree1, size1);
 287                init_tree_desc(&t2, tree2, size2);
 288                try_to_follow_renames(&t1, &t2, base, opt);
 289        }
 290        free(tree1);
 291        free(tree2);
 292        return retval;
 293}
 294
 295int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)
 296{
 297        int retval;
 298        void *tree;
 299        unsigned long size;
 300        struct tree_desc empty, real;
 301
 302        tree = read_object_with_reference(new, tree_type, &size, NULL);
 303        if (!tree)
 304                die("unable to read root tree (%s)", sha1_to_hex(new));
 305        init_tree_desc(&real, tree, size);
 306
 307        init_tree_desc(&empty, "", 0);
 308        retval = diff_tree(&empty, &real, base, opt);
 309        free(tree);
 310        return retval;
 311}
 312
 313void diff_tree_release_paths(struct diff_options *opt)
 314{
 315        free_pathspec(&opt->pathspec);
 316}
 317
 318void diff_tree_setup_paths(const char **p, struct diff_options *opt)
 319{
 320        init_pathspec(&opt->pathspec, p);
 321}