tree-diff.con commit lib-patch-mode tests: change from skip_all=* to prereq skip (f2f7b6a)
   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 char *malloc_base(const char *base, int baselen, const char *path, int pathlen)
  10{
  11        char *newbase = xmalloc(baselen + pathlen + 2);
  12        memcpy(newbase, base, baselen);
  13        memcpy(newbase + baselen, path, pathlen);
  14        memcpy(newbase + baselen + pathlen, "/", 2);
  15        return newbase;
  16}
  17
  18static char *malloc_fullname(const char *base, int baselen, const char *path, int pathlen)
  19{
  20        char *fullname = xmalloc(baselen + pathlen + 1);
  21        memcpy(fullname, base, baselen);
  22        memcpy(fullname + baselen, path, pathlen);
  23        fullname[baselen + pathlen] = 0;
  24        return fullname;
  25}
  26
  27static void show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc,
  28                       const char *base, int baselen);
  29
  30static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const char *base, int baselen, struct diff_options *opt)
  31{
  32        unsigned mode1, mode2;
  33        const char *path1, *path2;
  34        const unsigned char *sha1, *sha2;
  35        int cmp, pathlen1, pathlen2;
  36        char *fullname;
  37
  38        sha1 = tree_entry_extract(t1, &path1, &mode1);
  39        sha2 = tree_entry_extract(t2, &path2, &mode2);
  40
  41        pathlen1 = tree_entry_len(path1, sha1);
  42        pathlen2 = tree_entry_len(path2, sha2);
  43        cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
  44        if (cmp < 0) {
  45                show_entry(opt, "-", t1, base, baselen);
  46                return -1;
  47        }
  48        if (cmp > 0) {
  49                show_entry(opt, "+", t2, base, baselen);
  50                return 1;
  51        }
  52        if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)
  53                return 0;
  54
  55        /*
  56         * If the filemode has changed to/from a directory from/to a regular
  57         * file, we need to consider it a remove and an add.
  58         */
  59        if (S_ISDIR(mode1) != S_ISDIR(mode2)) {
  60                show_entry(opt, "-", t1, base, baselen);
  61                show_entry(opt, "+", t2, base, baselen);
  62                return 0;
  63        }
  64
  65        if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode1)) {
  66                int retval;
  67                char *newbase = malloc_base(base, baselen, path1, pathlen1);
  68                if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE)) {
  69                        newbase[baselen + pathlen1] = 0;
  70                        opt->change(opt, mode1, mode2,
  71                                    sha1, sha2, newbase, 0, 0);
  72                        newbase[baselen + pathlen1] = '/';
  73                }
  74                retval = diff_tree_sha1(sha1, sha2, newbase, opt);
  75                free(newbase);
  76                return retval;
  77        }
  78
  79        fullname = malloc_fullname(base, baselen, path1, pathlen1);
  80        opt->change(opt, mode1, mode2, sha1, sha2, fullname, 0, 0);
  81        free(fullname);
  82        return 0;
  83}
  84
  85/*
  86 * Is a tree entry interesting given the pathspec we have?
  87 *
  88 * Return:
  89 *  - 2 for "yes, and all subsequent entries will be"
  90 *  - 1 for yes
  91 *  - zero for no
  92 *  - negative for "no, and no subsequent entries will be either"
  93 */
  94static int tree_entry_interesting(struct tree_desc *desc, const char *base, int baselen, struct diff_options *opt)
  95{
  96        const char *path;
  97        const unsigned char *sha1;
  98        unsigned mode;
  99        int i;
 100        int pathlen;
 101        int never_interesting = -1;
 102
 103        if (!opt->nr_paths)
 104                return 1;
 105
 106        sha1 = tree_entry_extract(desc, &path, &mode);
 107
 108        pathlen = tree_entry_len(path, sha1);
 109
 110        for (i = 0; i < opt->nr_paths; i++) {
 111                const char *match = opt->paths[i];
 112                int matchlen = opt->pathlens[i];
 113                int m = -1; /* signals that we haven't called strncmp() */
 114
 115                if (baselen >= matchlen) {
 116                        /* If it doesn't match, move along... */
 117                        if (strncmp(base, match, matchlen))
 118                                continue;
 119
 120                        /*
 121                         * If the base is a subdirectory of a path which
 122                         * was specified, all of them are interesting.
 123                         */
 124                        if (!matchlen ||
 125                            base[matchlen] == '/' ||
 126                            match[matchlen - 1] == '/')
 127                                return 2;
 128
 129                        /* Just a random prefix match */
 130                        continue;
 131                }
 132
 133                /* Does the base match? */
 134                if (strncmp(base, match, baselen))
 135                        continue;
 136
 137                match += baselen;
 138                matchlen -= baselen;
 139
 140                if (never_interesting) {
 141                        /*
 142                         * We have not seen any match that sorts later
 143                         * than the current path.
 144                         */
 145
 146                        /*
 147                         * Does match sort strictly earlier than path
 148                         * with their common parts?
 149                         */
 150                        m = strncmp(match, path,
 151                                    (matchlen < pathlen) ? matchlen : pathlen);
 152                        if (m < 0)
 153                                continue;
 154
 155                        /*
 156                         * If we come here even once, that means there is at
 157                         * least one pathspec that would sort equal to or
 158                         * later than the path we are currently looking at.
 159                         * In other words, if we have never reached this point
 160                         * after iterating all pathspecs, it means all
 161                         * pathspecs are either outside of base, or inside the
 162                         * base but sorts strictly earlier than the current
 163                         * one.  In either case, they will never match the
 164                         * subsequent entries.  In such a case, we initialized
 165                         * the variable to -1 and that is what will be
 166                         * returned, allowing the caller to terminate early.
 167                         */
 168                        never_interesting = 0;
 169                }
 170
 171                if (pathlen > matchlen)
 172                        continue;
 173
 174                if (matchlen > pathlen) {
 175                        if (match[pathlen] != '/')
 176                                continue;
 177                        if (!S_ISDIR(mode))
 178                                continue;
 179                }
 180
 181                if (m == -1)
 182                        /*
 183                         * we cheated and did not do strncmp(), so we do
 184                         * that here.
 185                         */
 186                        m = strncmp(match, path, pathlen);
 187
 188                /*
 189                 * If common part matched earlier then it is a hit,
 190                 * because we rejected the case where path is not a
 191                 * leading directory and is shorter than match.
 192                 */
 193                if (!m)
 194                        return 1;
 195        }
 196        return never_interesting; /* No matches */
 197}
 198
 199/* A whole sub-tree went away or appeared */
 200static void show_tree(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base, int baselen)
 201{
 202        int all_interesting = 0;
 203        while (desc->size) {
 204                int show;
 205
 206                if (all_interesting)
 207                        show = 1;
 208                else {
 209                        show = tree_entry_interesting(desc, base, baselen,
 210                                                      opt);
 211                        if (show == 2)
 212                                all_interesting = 1;
 213                }
 214                if (show < 0)
 215                        break;
 216                if (show)
 217                        show_entry(opt, prefix, desc, base, baselen);
 218                update_tree_entry(desc);
 219        }
 220}
 221
 222/* A file entry went away or appeared */
 223static void show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc,
 224                       const char *base, int baselen)
 225{
 226        unsigned mode;
 227        const char *path;
 228        const unsigned char *sha1 = tree_entry_extract(desc, &path, &mode);
 229        int pathlen = tree_entry_len(path, sha1);
 230
 231        if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode)) {
 232                enum object_type type;
 233                char *newbase = malloc_base(base, baselen, path, pathlen);
 234                struct tree_desc inner;
 235                void *tree;
 236                unsigned long size;
 237
 238                tree = read_sha1_file(sha1, &type, &size);
 239                if (!tree || type != OBJ_TREE)
 240                        die("corrupt tree sha %s", sha1_to_hex(sha1));
 241
 242                if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE)) {
 243                        newbase[baselen + pathlen] = 0;
 244                        opt->add_remove(opt, *prefix, mode, sha1, newbase, 0);
 245                        newbase[baselen + pathlen] = '/';
 246                }
 247
 248                init_tree_desc(&inner, tree, size);
 249                show_tree(opt, prefix, &inner, newbase, baselen + 1 + pathlen);
 250
 251                free(tree);
 252                free(newbase);
 253        } else {
 254                char *fullname = malloc_fullname(base, baselen, path, pathlen);
 255                opt->add_remove(opt, prefix[0], mode, sha1, fullname, 0);
 256                free(fullname);
 257        }
 258}
 259
 260static void skip_uninteresting(struct tree_desc *t, const char *base, int baselen, struct diff_options *opt)
 261{
 262        int all_interesting = 0;
 263        while (t->size) {
 264                int show;
 265
 266                if (all_interesting)
 267                        show = 1;
 268                else {
 269                        show = tree_entry_interesting(t, base, baselen, opt);
 270                        if (show == 2)
 271                                all_interesting = 1;
 272                }
 273                if (!show) {
 274                        update_tree_entry(t);
 275                        continue;
 276                }
 277                /* Skip it all? */
 278                if (show < 0)
 279                        t->size = 0;
 280                return;
 281        }
 282}
 283
 284int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
 285{
 286        int baselen = strlen(base);
 287
 288        for (;;) {
 289                if (DIFF_OPT_TST(opt, QUICK) &&
 290                    DIFF_OPT_TST(opt, HAS_CHANGES))
 291                        break;
 292                if (opt->nr_paths) {
 293                        skip_uninteresting(t1, base, baselen, opt);
 294                        skip_uninteresting(t2, base, baselen, opt);
 295                }
 296                if (!t1->size) {
 297                        if (!t2->size)
 298                                break;
 299                        show_entry(opt, "+", t2, base, baselen);
 300                        update_tree_entry(t2);
 301                        continue;
 302                }
 303                if (!t2->size) {
 304                        show_entry(opt, "-", t1, base, baselen);
 305                        update_tree_entry(t1);
 306                        continue;
 307                }
 308                switch (compare_tree_entry(t1, t2, base, baselen, opt)) {
 309                case -1:
 310                        update_tree_entry(t1);
 311                        continue;
 312                case 0:
 313                        update_tree_entry(t1);
 314                        /* Fallthrough */
 315                case 1:
 316                        update_tree_entry(t2);
 317                        continue;
 318                }
 319                die("git diff-tree: internal error");
 320        }
 321        return 0;
 322}
 323
 324/*
 325 * Does it look like the resulting diff might be due to a rename?
 326 *  - single entry
 327 *  - not a valid previous file
 328 */
 329static inline int diff_might_be_rename(void)
 330{
 331        return diff_queued_diff.nr == 1 &&
 332                !DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
 333}
 334
 335static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
 336{
 337        struct diff_options diff_opts;
 338        struct diff_queue_struct *q = &diff_queued_diff;
 339        struct diff_filepair *choice;
 340        const char *paths[1];
 341        int i;
 342
 343        /* Remove the file creation entry from the diff queue, and remember it */
 344        choice = q->queue[0];
 345        q->nr = 0;
 346
 347        diff_setup(&diff_opts);
 348        DIFF_OPT_SET(&diff_opts, RECURSIVE);
 349        DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
 350        diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 351        diff_opts.single_follow = opt->paths[0];
 352        diff_opts.break_opt = opt->break_opt;
 353        paths[0] = NULL;
 354        diff_tree_setup_paths(paths, &diff_opts);
 355        if (diff_setup_done(&diff_opts) < 0)
 356                die("unable to set up diff options to follow renames");
 357        diff_tree(t1, t2, base, &diff_opts);
 358        diffcore_std(&diff_opts);
 359        diff_tree_release_paths(&diff_opts);
 360
 361        /* Go through the new set of filepairing, and see if we find a more interesting one */
 362        for (i = 0; i < q->nr; i++) {
 363                struct diff_filepair *p = q->queue[i];
 364
 365                /*
 366                 * Found a source? Not only do we use that for the new
 367                 * diff_queued_diff, we will also use that as the path in
 368                 * the future!
 369                 */
 370                if ((p->status == 'R' || p->status == 'C') && !strcmp(p->two->path, opt->paths[0])) {
 371                        /* Switch the file-pairs around */
 372                        q->queue[i] = choice;
 373                        choice = p;
 374
 375                        /* Update the path we use from now on.. */
 376                        diff_tree_release_paths(opt);
 377                        opt->paths[0] = xstrdup(p->one->path);
 378                        diff_tree_setup_paths(opt->paths, opt);
 379                        break;
 380                }
 381        }
 382
 383        /*
 384         * Then, discard all the non-relevant file pairs...
 385         */
 386        for (i = 0; i < q->nr; i++) {
 387                struct diff_filepair *p = q->queue[i];
 388                diff_free_filepair(p);
 389        }
 390
 391        /*
 392         * .. and re-instate the one we want (which might be either the
 393         * original one, or the rename/copy we found)
 394         */
 395        q->queue[0] = choice;
 396        q->nr = 1;
 397}
 398
 399int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
 400{
 401        void *tree1, *tree2;
 402        struct tree_desc t1, t2;
 403        unsigned long size1, size2;
 404        int retval;
 405
 406        tree1 = read_object_with_reference(old, tree_type, &size1, NULL);
 407        if (!tree1)
 408                die("unable to read source tree (%s)", sha1_to_hex(old));
 409        tree2 = read_object_with_reference(new, tree_type, &size2, NULL);
 410        if (!tree2)
 411                die("unable to read destination tree (%s)", sha1_to_hex(new));
 412        init_tree_desc(&t1, tree1, size1);
 413        init_tree_desc(&t2, tree2, size2);
 414        retval = diff_tree(&t1, &t2, base, opt);
 415        if (DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename()) {
 416                init_tree_desc(&t1, tree1, size1);
 417                init_tree_desc(&t2, tree2, size2);
 418                try_to_follow_renames(&t1, &t2, base, opt);
 419        }
 420        free(tree1);
 421        free(tree2);
 422        return retval;
 423}
 424
 425int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)
 426{
 427        int retval;
 428        void *tree;
 429        unsigned long size;
 430        struct tree_desc empty, real;
 431
 432        tree = read_object_with_reference(new, tree_type, &size, NULL);
 433        if (!tree)
 434                die("unable to read root tree (%s)", sha1_to_hex(new));
 435        init_tree_desc(&real, tree, size);
 436
 437        init_tree_desc(&empty, "", 0);
 438        retval = diff_tree(&empty, &real, base, opt);
 439        free(tree);
 440        return retval;
 441}
 442
 443static int count_paths(const char **paths)
 444{
 445        int i = 0;
 446        while (*paths++)
 447                i++;
 448        return i;
 449}
 450
 451void diff_tree_release_paths(struct diff_options *opt)
 452{
 453        free(opt->pathlens);
 454}
 455
 456void diff_tree_setup_paths(const char **p, struct diff_options *opt)
 457{
 458        opt->nr_paths = 0;
 459        opt->pathlens = NULL;
 460        opt->paths = NULL;
 461
 462        if (p) {
 463                int i;
 464
 465                opt->paths = p;
 466                opt->nr_paths = count_paths(p);
 467                if (opt->nr_paths == 0) {
 468                        opt->pathlens = NULL;
 469                        return;
 470                }
 471                opt->pathlens = xmalloc(opt->nr_paths * sizeof(int));
 472                for (i=0; i < opt->nr_paths; i++)
 473                        opt->pathlens[i] = strlen(p[i]);
 474        }
 475}