merge-recursive.con commit revision.c: make --no-notes reset --notes list (92e0d42)
   1/*
   2 * Recursive Merge algorithm stolen from git-merge-recursive.py by
   3 * Fredrik Kuivinen.
   4 * The thieves were Alex Riesen and Johannes Schindelin, in June/July 2006
   5 */
   6#include "advice.h"
   7#include "cache.h"
   8#include "cache-tree.h"
   9#include "commit.h"
  10#include "blob.h"
  11#include "builtin.h"
  12#include "tree-walk.h"
  13#include "diff.h"
  14#include "diffcore.h"
  15#include "tag.h"
  16#include "unpack-trees.h"
  17#include "string-list.h"
  18#include "xdiff-interface.h"
  19#include "ll-merge.h"
  20#include "attr.h"
  21#include "merge-recursive.h"
  22#include "dir.h"
  23#include "submodule.h"
  24
  25static const char rename_limit_advice[] =
  26"inexact rename detection was skipped because there were too many\n"
  27"  files. You may want to set your merge.renamelimit variable to at least\n"
  28"  %d and retry this merge.";
  29
  30static struct tree *shift_tree_object(struct tree *one, struct tree *two,
  31                                      const char *subtree_shift)
  32{
  33        unsigned char shifted[20];
  34
  35        if (!*subtree_shift) {
  36                shift_tree(one->object.sha1, two->object.sha1, shifted, 0);
  37        } else {
  38                shift_tree_by(one->object.sha1, two->object.sha1, shifted,
  39                              subtree_shift);
  40        }
  41        if (!hashcmp(two->object.sha1, shifted))
  42                return two;
  43        return lookup_tree(shifted);
  44}
  45
  46/*
  47 * A virtual commit has (const char *)commit->util set to the name.
  48 */
  49
  50static struct commit *make_virtual_commit(struct tree *tree, const char *comment)
  51{
  52        struct commit *commit = xcalloc(1, sizeof(struct commit));
  53        commit->tree = tree;
  54        commit->util = (void*)comment;
  55        /* avoid warnings */
  56        commit->object.parsed = 1;
  57        return commit;
  58}
  59
  60/*
  61 * Since we use get_tree_entry(), which does not put the read object into
  62 * the object pool, we cannot rely on a == b.
  63 */
  64static int sha_eq(const unsigned char *a, const unsigned char *b)
  65{
  66        if (!a && !b)
  67                return 2;
  68        return a && b && hashcmp(a, b) == 0;
  69}
  70
  71enum rename_type {
  72        RENAME_NORMAL = 0,
  73        RENAME_DELETE,
  74        RENAME_ONE_FILE_TO_TWO
  75};
  76
  77struct rename_df_conflict_info {
  78        enum rename_type rename_type;
  79        struct diff_filepair *pair1;
  80        struct diff_filepair *pair2;
  81        const char *branch1;
  82        const char *branch2;
  83        struct stage_data *dst_entry1;
  84        struct stage_data *dst_entry2;
  85};
  86
  87/*
  88 * Since we want to write the index eventually, we cannot reuse the index
  89 * for these (temporary) data.
  90 */
  91struct stage_data {
  92        struct {
  93                unsigned mode;
  94                unsigned char sha[20];
  95        } stages[4];
  96        struct rename_df_conflict_info *rename_df_conflict_info;
  97        unsigned processed:1;
  98};
  99
 100static inline void setup_rename_df_conflict_info(enum rename_type rename_type,
 101                                                 struct diff_filepair *pair1,
 102                                                 struct diff_filepair *pair2,
 103                                                 const char *branch1,
 104                                                 const char *branch2,
 105                                                 struct stage_data *dst_entry1,
 106                                                 struct stage_data *dst_entry2)
 107{
 108        struct rename_df_conflict_info *ci = xcalloc(1, sizeof(struct rename_df_conflict_info));
 109        ci->rename_type = rename_type;
 110        ci->pair1 = pair1;
 111        ci->branch1 = branch1;
 112        ci->branch2 = branch2;
 113
 114        ci->dst_entry1 = dst_entry1;
 115        dst_entry1->rename_df_conflict_info = ci;
 116        dst_entry1->processed = 0;
 117
 118        assert(!pair2 == !dst_entry2);
 119        if (dst_entry2) {
 120                ci->dst_entry2 = dst_entry2;
 121                ci->pair2 = pair2;
 122                dst_entry2->rename_df_conflict_info = ci;
 123                dst_entry2->processed = 0;
 124        }
 125}
 126
 127static int show(struct merge_options *o, int v)
 128{
 129        return (!o->call_depth && o->verbosity >= v) || o->verbosity >= 5;
 130}
 131
 132static void flush_output(struct merge_options *o)
 133{
 134        if (o->obuf.len) {
 135                fputs(o->obuf.buf, stdout);
 136                strbuf_reset(&o->obuf);
 137        }
 138}
 139
 140__attribute__((format (printf, 3, 4)))
 141static void output(struct merge_options *o, int v, const char *fmt, ...)
 142{
 143        va_list ap;
 144
 145        if (!show(o, v))
 146                return;
 147
 148        strbuf_grow(&o->obuf, o->call_depth * 2 + 2);
 149        memset(o->obuf.buf + o->obuf.len, ' ', o->call_depth * 2);
 150        strbuf_setlen(&o->obuf, o->obuf.len + o->call_depth * 2);
 151
 152        va_start(ap, fmt);
 153        strbuf_vaddf(&o->obuf, fmt, ap);
 154        va_end(ap);
 155
 156        strbuf_add(&o->obuf, "\n", 1);
 157        if (!o->buffer_output)
 158                flush_output(o);
 159}
 160
 161static void output_commit_title(struct merge_options *o, struct commit *commit)
 162{
 163        int i;
 164        flush_output(o);
 165        for (i = o->call_depth; i--;)
 166                fputs("  ", stdout);
 167        if (commit->util)
 168                printf("virtual %s\n", (char *)commit->util);
 169        else {
 170                printf("%s ", find_unique_abbrev(commit->object.sha1, DEFAULT_ABBREV));
 171                if (parse_commit(commit) != 0)
 172                        printf("(bad commit)\n");
 173                else {
 174                        const char *title;
 175                        int len = find_commit_subject(commit->buffer, &title);
 176                        if (len)
 177                                printf("%.*s\n", len, title);
 178                }
 179        }
 180}
 181
 182static int add_cacheinfo(unsigned int mode, const unsigned char *sha1,
 183                const char *path, int stage, int refresh, int options)
 184{
 185        struct cache_entry *ce;
 186        ce = make_cache_entry(mode, sha1 ? sha1 : null_sha1, path, stage, refresh);
 187        if (!ce)
 188                return error("addinfo_cache failed for path '%s'", path);
 189        return add_cache_entry(ce, options);
 190}
 191
 192static void init_tree_desc_from_tree(struct tree_desc *desc, struct tree *tree)
 193{
 194        parse_tree(tree);
 195        init_tree_desc(desc, tree->buffer, tree->size);
 196}
 197
 198static int git_merge_trees(int index_only,
 199                           struct tree *common,
 200                           struct tree *head,
 201                           struct tree *merge)
 202{
 203        int rc;
 204        struct tree_desc t[3];
 205        struct unpack_trees_options opts;
 206
 207        memset(&opts, 0, sizeof(opts));
 208        if (index_only)
 209                opts.index_only = 1;
 210        else
 211                opts.update = 1;
 212        opts.merge = 1;
 213        opts.head_idx = 2;
 214        opts.fn = threeway_merge;
 215        opts.src_index = &the_index;
 216        opts.dst_index = &the_index;
 217        setup_unpack_trees_porcelain(&opts, "merge");
 218
 219        init_tree_desc_from_tree(t+0, common);
 220        init_tree_desc_from_tree(t+1, head);
 221        init_tree_desc_from_tree(t+2, merge);
 222
 223        rc = unpack_trees(3, t, &opts);
 224        cache_tree_free(&active_cache_tree);
 225        return rc;
 226}
 227
 228struct tree *write_tree_from_memory(struct merge_options *o)
 229{
 230        struct tree *result = NULL;
 231
 232        if (unmerged_cache()) {
 233                int i;
 234                fprintf(stderr, "BUG: There are unmerged index entries:\n");
 235                for (i = 0; i < active_nr; i++) {
 236                        struct cache_entry *ce = active_cache[i];
 237                        if (ce_stage(ce))
 238                                fprintf(stderr, "BUG: %d %.*s", ce_stage(ce),
 239                                        (int)ce_namelen(ce), ce->name);
 240                }
 241                die("Bug in merge-recursive.c");
 242        }
 243
 244        if (!active_cache_tree)
 245                active_cache_tree = cache_tree();
 246
 247        if (!cache_tree_fully_valid(active_cache_tree) &&
 248            cache_tree_update(active_cache_tree,
 249                              active_cache, active_nr, 0, 0) < 0)
 250                die("error building trees");
 251
 252        result = lookup_tree(active_cache_tree->sha1);
 253
 254        return result;
 255}
 256
 257static int save_files_dirs(const unsigned char *sha1,
 258                const char *base, int baselen, const char *path,
 259                unsigned int mode, int stage, void *context)
 260{
 261        int len = strlen(path);
 262        char *newpath = xmalloc(baselen + len + 1);
 263        struct merge_options *o = context;
 264
 265        memcpy(newpath, base, baselen);
 266        memcpy(newpath + baselen, path, len);
 267        newpath[baselen + len] = '\0';
 268
 269        if (S_ISDIR(mode))
 270                string_list_insert(&o->current_directory_set, newpath);
 271        else
 272                string_list_insert(&o->current_file_set, newpath);
 273        free(newpath);
 274
 275        return (S_ISDIR(mode) ? READ_TREE_RECURSIVE : 0);
 276}
 277
 278static int get_files_dirs(struct merge_options *o, struct tree *tree)
 279{
 280        int n;
 281        if (read_tree_recursive(tree, "", 0, 0, NULL, save_files_dirs, o))
 282                return 0;
 283        n = o->current_file_set.nr + o->current_directory_set.nr;
 284        return n;
 285}
 286
 287/*
 288 * Returns an index_entry instance which doesn't have to correspond to
 289 * a real cache entry in Git's index.
 290 */
 291static struct stage_data *insert_stage_data(const char *path,
 292                struct tree *o, struct tree *a, struct tree *b,
 293                struct string_list *entries)
 294{
 295        struct string_list_item *item;
 296        struct stage_data *e = xcalloc(1, sizeof(struct stage_data));
 297        get_tree_entry(o->object.sha1, path,
 298                        e->stages[1].sha, &e->stages[1].mode);
 299        get_tree_entry(a->object.sha1, path,
 300                        e->stages[2].sha, &e->stages[2].mode);
 301        get_tree_entry(b->object.sha1, path,
 302                        e->stages[3].sha, &e->stages[3].mode);
 303        item = string_list_insert(entries, path);
 304        item->util = e;
 305        return e;
 306}
 307
 308/*
 309 * Create a dictionary mapping file names to stage_data objects. The
 310 * dictionary contains one entry for every path with a non-zero stage entry.
 311 */
 312static struct string_list *get_unmerged(void)
 313{
 314        struct string_list *unmerged = xcalloc(1, sizeof(struct string_list));
 315        int i;
 316
 317        unmerged->strdup_strings = 1;
 318
 319        for (i = 0; i < active_nr; i++) {
 320                struct string_list_item *item;
 321                struct stage_data *e;
 322                struct cache_entry *ce = active_cache[i];
 323                if (!ce_stage(ce))
 324                        continue;
 325
 326                item = string_list_lookup(unmerged, ce->name);
 327                if (!item) {
 328                        item = string_list_insert(unmerged, ce->name);
 329                        item->util = xcalloc(1, sizeof(struct stage_data));
 330                }
 331                e = item->util;
 332                e->stages[ce_stage(ce)].mode = ce->ce_mode;
 333                hashcpy(e->stages[ce_stage(ce)].sha, ce->sha1);
 334        }
 335
 336        return unmerged;
 337}
 338
 339static void make_room_for_directories_of_df_conflicts(struct merge_options *o,
 340                                                      struct string_list *entries)
 341{
 342        /* If there are D/F conflicts, and the paths currently exist
 343         * in the working copy as a file, we want to remove them to
 344         * make room for the corresponding directory.  Such paths will
 345         * later be processed in process_df_entry() at the end.  If
 346         * the corresponding directory ends up being removed by the
 347         * merge, then the file will be reinstated at that time;
 348         * otherwise, if the file is not supposed to be removed by the
 349         * merge, the contents of the file will be placed in another
 350         * unique filename.
 351         *
 352         * NOTE: This function relies on the fact that entries for a
 353         * D/F conflict will appear adjacent in the index, with the
 354         * entries for the file appearing before entries for paths
 355         * below the corresponding directory.
 356         */
 357        const char *last_file = NULL;
 358        int last_len = 0;
 359        struct stage_data *last_e;
 360        int i;
 361
 362        for (i = 0; i < entries->nr; i++) {
 363                const char *path = entries->items[i].string;
 364                int len = strlen(path);
 365                struct stage_data *e = entries->items[i].util;
 366
 367                /*
 368                 * Check if last_file & path correspond to a D/F conflict;
 369                 * i.e. whether path is last_file+'/'+<something>.
 370                 * If so, remove last_file to make room for path and friends.
 371                 */
 372                if (last_file &&
 373                    len > last_len &&
 374                    memcmp(path, last_file, last_len) == 0 &&
 375                    path[last_len] == '/') {
 376                        output(o, 3, "Removing %s to make room for subdirectory; may re-add later.", last_file);
 377                        unlink(last_file);
 378                }
 379
 380                /*
 381                 * Determine whether path could exist as a file in the
 382                 * working directory as a possible D/F conflict.  This
 383                 * will only occur when it exists in stage 2 as a
 384                 * file.
 385                 */
 386                if (S_ISREG(e->stages[2].mode) || S_ISLNK(e->stages[2].mode)) {
 387                        last_file = path;
 388                        last_len = len;
 389                        last_e = e;
 390                } else {
 391                        last_file = NULL;
 392                }
 393        }
 394}
 395
 396struct rename {
 397        struct diff_filepair *pair;
 398        struct stage_data *src_entry;
 399        struct stage_data *dst_entry;
 400        unsigned processed:1;
 401};
 402
 403/*
 404 * Get information of all renames which occurred between 'o_tree' and
 405 * 'tree'. We need the three trees in the merge ('o_tree', 'a_tree' and
 406 * 'b_tree') to be able to associate the correct cache entries with
 407 * the rename information. 'tree' is always equal to either a_tree or b_tree.
 408 */
 409static struct string_list *get_renames(struct merge_options *o,
 410                                       struct tree *tree,
 411                                       struct tree *o_tree,
 412                                       struct tree *a_tree,
 413                                       struct tree *b_tree,
 414                                       struct string_list *entries)
 415{
 416        int i;
 417        struct string_list *renames;
 418        struct diff_options opts;
 419
 420        renames = xcalloc(1, sizeof(struct string_list));
 421        diff_setup(&opts);
 422        DIFF_OPT_SET(&opts, RECURSIVE);
 423        opts.detect_rename = DIFF_DETECT_RENAME;
 424        opts.rename_limit = o->merge_rename_limit >= 0 ? o->merge_rename_limit :
 425                            o->diff_rename_limit >= 0 ? o->diff_rename_limit :
 426                            1000;
 427        opts.rename_score = o->rename_score;
 428        opts.show_rename_progress = o->show_rename_progress;
 429        opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 430        if (diff_setup_done(&opts) < 0)
 431                die("diff setup failed");
 432        diff_tree_sha1(o_tree->object.sha1, tree->object.sha1, "", &opts);
 433        diffcore_std(&opts);
 434        if (opts.needed_rename_limit > o->needed_rename_limit)
 435                o->needed_rename_limit = opts.needed_rename_limit;
 436        for (i = 0; i < diff_queued_diff.nr; ++i) {
 437                struct string_list_item *item;
 438                struct rename *re;
 439                struct diff_filepair *pair = diff_queued_diff.queue[i];
 440                if (pair->status != 'R') {
 441                        diff_free_filepair(pair);
 442                        continue;
 443                }
 444                re = xmalloc(sizeof(*re));
 445                re->processed = 0;
 446                re->pair = pair;
 447                item = string_list_lookup(entries, re->pair->one->path);
 448                if (!item)
 449                        re->src_entry = insert_stage_data(re->pair->one->path,
 450                                        o_tree, a_tree, b_tree, entries);
 451                else
 452                        re->src_entry = item->util;
 453
 454                item = string_list_lookup(entries, re->pair->two->path);
 455                if (!item)
 456                        re->dst_entry = insert_stage_data(re->pair->two->path,
 457                                        o_tree, a_tree, b_tree, entries);
 458                else
 459                        re->dst_entry = item->util;
 460                item = string_list_insert(renames, pair->one->path);
 461                item->util = re;
 462        }
 463        opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 464        diff_queued_diff.nr = 0;
 465        diff_flush(&opts);
 466        return renames;
 467}
 468
 469static int update_stages_options(const char *path, struct diff_filespec *o,
 470                         struct diff_filespec *a, struct diff_filespec *b,
 471                         int clear, int options)
 472{
 473        if (clear)
 474                if (remove_file_from_cache(path))
 475                        return -1;
 476        if (o)
 477                if (add_cacheinfo(o->mode, o->sha1, path, 1, 0, options))
 478                        return -1;
 479        if (a)
 480                if (add_cacheinfo(a->mode, a->sha1, path, 2, 0, options))
 481                        return -1;
 482        if (b)
 483                if (add_cacheinfo(b->mode, b->sha1, path, 3, 0, options))
 484                        return -1;
 485        return 0;
 486}
 487
 488static int update_stages(const char *path, struct diff_filespec *o,
 489                         struct diff_filespec *a, struct diff_filespec *b,
 490                         int clear)
 491{
 492        int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE;
 493        return update_stages_options(path, o, a, b, clear, options);
 494}
 495
 496static int update_stages_and_entry(const char *path,
 497                                   struct stage_data *entry,
 498                                   struct diff_filespec *o,
 499                                   struct diff_filespec *a,
 500                                   struct diff_filespec *b,
 501                                   int clear)
 502{
 503        int options;
 504
 505        entry->processed = 0;
 506        entry->stages[1].mode = o->mode;
 507        entry->stages[2].mode = a->mode;
 508        entry->stages[3].mode = b->mode;
 509        hashcpy(entry->stages[1].sha, o->sha1);
 510        hashcpy(entry->stages[2].sha, a->sha1);
 511        hashcpy(entry->stages[3].sha, b->sha1);
 512        options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_SKIP_DFCHECK;
 513        return update_stages_options(path, o, a, b, clear, options);
 514}
 515
 516static int remove_file(struct merge_options *o, int clean,
 517                       const char *path, int no_wd)
 518{
 519        int update_cache = o->call_depth || clean;
 520        int update_working_directory = !o->call_depth && !no_wd;
 521
 522        if (update_cache) {
 523                if (remove_file_from_cache(path))
 524                        return -1;
 525        }
 526        if (update_working_directory) {
 527                if (remove_path(path))
 528                        return -1;
 529        }
 530        return 0;
 531}
 532
 533static char *unique_path(struct merge_options *o, const char *path, const char *branch)
 534{
 535        char *newpath = xmalloc(strlen(path) + 1 + strlen(branch) + 8 + 1);
 536        int suffix = 0;
 537        struct stat st;
 538        char *p = newpath + strlen(path);
 539        strcpy(newpath, path);
 540        *(p++) = '~';
 541        strcpy(p, branch);
 542        for (; *p; ++p)
 543                if ('/' == *p)
 544                        *p = '_';
 545        while (string_list_has_string(&o->current_file_set, newpath) ||
 546               string_list_has_string(&o->current_directory_set, newpath) ||
 547               lstat(newpath, &st) == 0)
 548                sprintf(p, "_%d", suffix++);
 549
 550        string_list_insert(&o->current_file_set, newpath);
 551        return newpath;
 552}
 553
 554static void flush_buffer(int fd, const char *buf, unsigned long size)
 555{
 556        while (size > 0) {
 557                long ret = write_in_full(fd, buf, size);
 558                if (ret < 0) {
 559                        /* Ignore epipe */
 560                        if (errno == EPIPE)
 561                                break;
 562                        die_errno("merge-recursive");
 563                } else if (!ret) {
 564                        die("merge-recursive: disk full?");
 565                }
 566                size -= ret;
 567                buf += ret;
 568        }
 569}
 570
 571static int would_lose_untracked(const char *path)
 572{
 573        int pos = cache_name_pos(path, strlen(path));
 574
 575        if (pos < 0)
 576                pos = -1 - pos;
 577        while (pos < active_nr &&
 578               !strcmp(path, active_cache[pos]->name)) {
 579                /*
 580                 * If stage #0, it is definitely tracked.
 581                 * If it has stage #2 then it was tracked
 582                 * before this merge started.  All other
 583                 * cases the path was not tracked.
 584                 */
 585                switch (ce_stage(active_cache[pos])) {
 586                case 0:
 587                case 2:
 588                        return 0;
 589                }
 590                pos++;
 591        }
 592        return file_exists(path);
 593}
 594
 595static int make_room_for_path(const char *path)
 596{
 597        int status;
 598        const char *msg = "failed to create path '%s'%s";
 599
 600        status = safe_create_leading_directories_const(path);
 601        if (status) {
 602                if (status == -3) {
 603                        /* something else exists */
 604                        error(msg, path, ": perhaps a D/F conflict?");
 605                        return -1;
 606                }
 607                die(msg, path, "");
 608        }
 609
 610        /*
 611         * Do not unlink a file in the work tree if we are not
 612         * tracking it.
 613         */
 614        if (would_lose_untracked(path))
 615                return error("refusing to lose untracked file at '%s'",
 616                             path);
 617
 618        /* Successful unlink is good.. */
 619        if (!unlink(path))
 620                return 0;
 621        /* .. and so is no existing file */
 622        if (errno == ENOENT)
 623                return 0;
 624        /* .. but not some other error (who really cares what?) */
 625        return error(msg, path, ": perhaps a D/F conflict?");
 626}
 627
 628static void update_file_flags(struct merge_options *o,
 629                              const unsigned char *sha,
 630                              unsigned mode,
 631                              const char *path,
 632                              int update_cache,
 633                              int update_wd)
 634{
 635        if (o->call_depth)
 636                update_wd = 0;
 637
 638        if (update_wd) {
 639                enum object_type type;
 640                void *buf;
 641                unsigned long size;
 642
 643                if (S_ISGITLINK(mode)) {
 644                        /*
 645                         * We may later decide to recursively descend into
 646                         * the submodule directory and update its index
 647                         * and/or work tree, but we do not do that now.
 648                         */
 649                        update_wd = 0;
 650                        goto update_index;
 651                }
 652
 653                buf = read_sha1_file(sha, &type, &size);
 654                if (!buf)
 655                        die("cannot read object %s '%s'", sha1_to_hex(sha), path);
 656                if (type != OBJ_BLOB)
 657                        die("blob expected for %s '%s'", sha1_to_hex(sha), path);
 658                if (S_ISREG(mode)) {
 659                        struct strbuf strbuf = STRBUF_INIT;
 660                        if (convert_to_working_tree(path, buf, size, &strbuf)) {
 661                                free(buf);
 662                                size = strbuf.len;
 663                                buf = strbuf_detach(&strbuf, NULL);
 664                        }
 665                }
 666
 667                if (make_room_for_path(path) < 0) {
 668                        update_wd = 0;
 669                        free(buf);
 670                        goto update_index;
 671                }
 672                if (S_ISREG(mode) || (!has_symlinks && S_ISLNK(mode))) {
 673                        int fd;
 674                        if (mode & 0100)
 675                                mode = 0777;
 676                        else
 677                                mode = 0666;
 678                        fd = open(path, O_WRONLY | O_TRUNC | O_CREAT, mode);
 679                        if (fd < 0)
 680                                die_errno("failed to open '%s'", path);
 681                        flush_buffer(fd, buf, size);
 682                        close(fd);
 683                } else if (S_ISLNK(mode)) {
 684                        char *lnk = xmemdupz(buf, size);
 685                        safe_create_leading_directories_const(path);
 686                        unlink(path);
 687                        if (symlink(lnk, path))
 688                                die_errno("failed to symlink '%s'", path);
 689                        free(lnk);
 690                } else
 691                        die("do not know what to do with %06o %s '%s'",
 692                            mode, sha1_to_hex(sha), path);
 693                free(buf);
 694        }
 695 update_index:
 696        if (update_cache)
 697                add_cacheinfo(mode, sha, path, 0, update_wd, ADD_CACHE_OK_TO_ADD);
 698}
 699
 700static void update_file(struct merge_options *o,
 701                        int clean,
 702                        const unsigned char *sha,
 703                        unsigned mode,
 704                        const char *path)
 705{
 706        update_file_flags(o, sha, mode, path, o->call_depth || clean, !o->call_depth);
 707}
 708
 709/* Low level file merging, update and removal */
 710
 711struct merge_file_info {
 712        unsigned char sha[20];
 713        unsigned mode;
 714        unsigned clean:1,
 715                 merge:1;
 716};
 717
 718static int merge_3way(struct merge_options *o,
 719                      mmbuffer_t *result_buf,
 720                      struct diff_filespec *one,
 721                      struct diff_filespec *a,
 722                      struct diff_filespec *b,
 723                      const char *branch1,
 724                      const char *branch2)
 725{
 726        mmfile_t orig, src1, src2;
 727        struct ll_merge_options ll_opts = {0};
 728        char *base_name, *name1, *name2;
 729        int merge_status;
 730
 731        ll_opts.renormalize = o->renormalize;
 732        ll_opts.xdl_opts = o->xdl_opts;
 733
 734        if (o->call_depth) {
 735                ll_opts.virtual_ancestor = 1;
 736                ll_opts.variant = 0;
 737        } else {
 738                switch (o->recursive_variant) {
 739                case MERGE_RECURSIVE_OURS:
 740                        ll_opts.variant = XDL_MERGE_FAVOR_OURS;
 741                        break;
 742                case MERGE_RECURSIVE_THEIRS:
 743                        ll_opts.variant = XDL_MERGE_FAVOR_THEIRS;
 744                        break;
 745                default:
 746                        ll_opts.variant = 0;
 747                        break;
 748                }
 749        }
 750
 751        if (strcmp(a->path, b->path) ||
 752            (o->ancestor != NULL && strcmp(a->path, one->path) != 0)) {
 753                base_name = o->ancestor == NULL ? NULL :
 754                        xstrdup(mkpath("%s:%s", o->ancestor, one->path));
 755                name1 = xstrdup(mkpath("%s:%s", branch1, a->path));
 756                name2 = xstrdup(mkpath("%s:%s", branch2, b->path));
 757        } else {
 758                base_name = o->ancestor == NULL ? NULL :
 759                        xstrdup(mkpath("%s", o->ancestor));
 760                name1 = xstrdup(mkpath("%s", branch1));
 761                name2 = xstrdup(mkpath("%s", branch2));
 762        }
 763
 764        read_mmblob(&orig, one->sha1);
 765        read_mmblob(&src1, a->sha1);
 766        read_mmblob(&src2, b->sha1);
 767
 768        merge_status = ll_merge(result_buf, a->path, &orig, base_name,
 769                                &src1, name1, &src2, name2, &ll_opts);
 770
 771        free(name1);
 772        free(name2);
 773        free(orig.ptr);
 774        free(src1.ptr);
 775        free(src2.ptr);
 776        return merge_status;
 777}
 778
 779static struct merge_file_info merge_file(struct merge_options *o,
 780                                         struct diff_filespec *one,
 781                                         struct diff_filespec *a,
 782                                         struct diff_filespec *b,
 783                                         const char *branch1,
 784                                         const char *branch2)
 785{
 786        struct merge_file_info result;
 787        result.merge = 0;
 788        result.clean = 1;
 789
 790        if ((S_IFMT & a->mode) != (S_IFMT & b->mode)) {
 791                result.clean = 0;
 792                if (S_ISREG(a->mode)) {
 793                        result.mode = a->mode;
 794                        hashcpy(result.sha, a->sha1);
 795                } else {
 796                        result.mode = b->mode;
 797                        hashcpy(result.sha, b->sha1);
 798                }
 799        } else {
 800                if (!sha_eq(a->sha1, one->sha1) && !sha_eq(b->sha1, one->sha1))
 801                        result.merge = 1;
 802
 803                /*
 804                 * Merge modes
 805                 */
 806                if (a->mode == b->mode || a->mode == one->mode)
 807                        result.mode = b->mode;
 808                else {
 809                        result.mode = a->mode;
 810                        if (b->mode != one->mode) {
 811                                result.clean = 0;
 812                                result.merge = 1;
 813                        }
 814                }
 815
 816                if (sha_eq(a->sha1, b->sha1) || sha_eq(a->sha1, one->sha1))
 817                        hashcpy(result.sha, b->sha1);
 818                else if (sha_eq(b->sha1, one->sha1))
 819                        hashcpy(result.sha, a->sha1);
 820                else if (S_ISREG(a->mode)) {
 821                        mmbuffer_t result_buf;
 822                        int merge_status;
 823
 824                        merge_status = merge_3way(o, &result_buf, one, a, b,
 825                                                  branch1, branch2);
 826
 827                        if ((merge_status < 0) || !result_buf.ptr)
 828                                die("Failed to execute internal merge");
 829
 830                        if (write_sha1_file(result_buf.ptr, result_buf.size,
 831                                            blob_type, result.sha))
 832                                die("Unable to add %s to database",
 833                                    a->path);
 834
 835                        free(result_buf.ptr);
 836                        result.clean = (merge_status == 0);
 837                } else if (S_ISGITLINK(a->mode)) {
 838                        result.clean = merge_submodule(result.sha, one->path, one->sha1,
 839                                                       a->sha1, b->sha1);
 840                } else if (S_ISLNK(a->mode)) {
 841                        hashcpy(result.sha, a->sha1);
 842
 843                        if (!sha_eq(a->sha1, b->sha1))
 844                                result.clean = 0;
 845                } else {
 846                        die("unsupported object type in the tree");
 847                }
 848        }
 849
 850        return result;
 851}
 852
 853static void conflict_rename_delete(struct merge_options *o,
 854                                   struct diff_filepair *pair,
 855                                   const char *rename_branch,
 856                                   const char *other_branch)
 857{
 858        char *dest_name = pair->two->path;
 859        int df_conflict = 0;
 860        struct stat st;
 861
 862        output(o, 1, "CONFLICT (rename/delete): Rename %s->%s in %s "
 863               "and deleted in %s",
 864               pair->one->path, pair->two->path, rename_branch,
 865               other_branch);
 866        if (!o->call_depth)
 867                update_stages(dest_name, NULL,
 868                              rename_branch == o->branch1 ? pair->two : NULL,
 869                              rename_branch == o->branch1 ? NULL : pair->two,
 870                              1);
 871        if (lstat(dest_name, &st) == 0 && S_ISDIR(st.st_mode)) {
 872                dest_name = unique_path(o, dest_name, rename_branch);
 873                df_conflict = 1;
 874        }
 875        update_file(o, 0, pair->two->sha1, pair->two->mode, dest_name);
 876        if (df_conflict)
 877                free(dest_name);
 878}
 879
 880static void conflict_rename_rename_1to2(struct merge_options *o,
 881                                        struct diff_filepair *pair1,
 882                                        const char *branch1,
 883                                        struct diff_filepair *pair2,
 884                                        const char *branch2)
 885{
 886        /* One file was renamed in both branches, but to different names. */
 887        char *del[2];
 888        int delp = 0;
 889        const char *ren1_dst = pair1->two->path;
 890        const char *ren2_dst = pair2->two->path;
 891        const char *dst_name1 = ren1_dst;
 892        const char *dst_name2 = ren2_dst;
 893        struct stat st;
 894        if (lstat(ren1_dst, &st) == 0 && S_ISDIR(st.st_mode)) {
 895                dst_name1 = del[delp++] = unique_path(o, ren1_dst, branch1);
 896                output(o, 1, "%s is a directory in %s adding as %s instead",
 897                       ren1_dst, branch2, dst_name1);
 898        }
 899        if (lstat(ren2_dst, &st) == 0 && S_ISDIR(st.st_mode)) {
 900                dst_name2 = del[delp++] = unique_path(o, ren2_dst, branch2);
 901                output(o, 1, "%s is a directory in %s adding as %s instead",
 902                       ren2_dst, branch1, dst_name2);
 903        }
 904        if (o->call_depth) {
 905                remove_file_from_cache(dst_name1);
 906                remove_file_from_cache(dst_name2);
 907                /*
 908                 * Uncomment to leave the conflicting names in the resulting tree
 909                 *
 910                 * update_file(o, 0, pair1->two->sha1, pair1->two->mode, dst_name1);
 911                 * update_file(o, 0, pair2->two->sha1, pair2->two->mode, dst_name2);
 912                 */
 913        } else {
 914                update_stages(ren1_dst, NULL, pair1->two, NULL, 1);
 915                update_stages(ren2_dst, NULL, NULL, pair2->two, 1);
 916
 917                update_file(o, 0, pair1->two->sha1, pair1->two->mode, dst_name1);
 918                update_file(o, 0, pair2->two->sha1, pair2->two->mode, dst_name2);
 919        }
 920        while (delp--)
 921                free(del[delp]);
 922}
 923
 924static void conflict_rename_rename_2to1(struct merge_options *o,
 925                                        struct rename *ren1,
 926                                        const char *branch1,
 927                                        struct rename *ren2,
 928                                        const char *branch2)
 929{
 930        /* Two files were renamed to the same thing. */
 931        char *new_path1 = unique_path(o, ren1->pair->two->path, branch1);
 932        char *new_path2 = unique_path(o, ren2->pair->two->path, branch2);
 933        output(o, 1, "Renaming %s to %s and %s to %s instead",
 934               ren1->pair->one->path, new_path1,
 935               ren2->pair->one->path, new_path2);
 936        remove_file(o, 0, ren1->pair->two->path, 0);
 937        update_file(o, 0, ren1->pair->two->sha1, ren1->pair->two->mode, new_path1);
 938        update_file(o, 0, ren2->pair->two->sha1, ren2->pair->two->mode, new_path2);
 939        free(new_path2);
 940        free(new_path1);
 941}
 942
 943static int process_renames(struct merge_options *o,
 944                           struct string_list *a_renames,
 945                           struct string_list *b_renames)
 946{
 947        int clean_merge = 1, i, j;
 948        struct string_list a_by_dst = STRING_LIST_INIT_NODUP;
 949        struct string_list b_by_dst = STRING_LIST_INIT_NODUP;
 950        const struct rename *sre;
 951
 952        for (i = 0; i < a_renames->nr; i++) {
 953                sre = a_renames->items[i].util;
 954                string_list_insert(&a_by_dst, sre->pair->two->path)->util
 955                        = sre->dst_entry;
 956        }
 957        for (i = 0; i < b_renames->nr; i++) {
 958                sre = b_renames->items[i].util;
 959                string_list_insert(&b_by_dst, sre->pair->two->path)->util
 960                        = sre->dst_entry;
 961        }
 962
 963        for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {
 964                char *src;
 965                struct string_list *renames1, *renames2Dst;
 966                struct rename *ren1 = NULL, *ren2 = NULL;
 967                const char *branch1, *branch2;
 968                const char *ren1_src, *ren1_dst;
 969
 970                if (i >= a_renames->nr) {
 971                        ren2 = b_renames->items[j++].util;
 972                } else if (j >= b_renames->nr) {
 973                        ren1 = a_renames->items[i++].util;
 974                } else {
 975                        int compare = strcmp(a_renames->items[i].string,
 976                                             b_renames->items[j].string);
 977                        if (compare <= 0)
 978                                ren1 = a_renames->items[i++].util;
 979                        if (compare >= 0)
 980                                ren2 = b_renames->items[j++].util;
 981                }
 982
 983                /* TODO: refactor, so that 1/2 are not needed */
 984                if (ren1) {
 985                        renames1 = a_renames;
 986                        renames2Dst = &b_by_dst;
 987                        branch1 = o->branch1;
 988                        branch2 = o->branch2;
 989                } else {
 990                        struct rename *tmp;
 991                        renames1 = b_renames;
 992                        renames2Dst = &a_by_dst;
 993                        branch1 = o->branch2;
 994                        branch2 = o->branch1;
 995                        tmp = ren2;
 996                        ren2 = ren1;
 997                        ren1 = tmp;
 998                }
 999                src = ren1->pair->one->path;
1000
1001                ren1->dst_entry->processed = 1;
1002                ren1->src_entry->processed = 1;
1003
1004                if (ren1->processed)
1005                        continue;
1006                ren1->processed = 1;
1007
1008                ren1_src = ren1->pair->one->path;
1009                ren1_dst = ren1->pair->two->path;
1010
1011                if (ren2) {
1012                        const char *ren2_src = ren2->pair->one->path;
1013                        const char *ren2_dst = ren2->pair->two->path;
1014                        /* Renamed in 1 and renamed in 2 */
1015                        if (strcmp(ren1_src, ren2_src) != 0)
1016                                die("ren1.src != ren2.src");
1017                        ren2->dst_entry->processed = 1;
1018                        ren2->processed = 1;
1019                        if (strcmp(ren1_dst, ren2_dst) != 0) {
1020                                setup_rename_df_conflict_info(RENAME_ONE_FILE_TO_TWO,
1021                                                              ren1->pair,
1022                                                              ren2->pair,
1023                                                              branch1,
1024                                                              branch2,
1025                                                              ren1->dst_entry,
1026                                                              ren2->dst_entry);
1027                        } else {
1028                                remove_file(o, 1, ren1_src, 1);
1029                                update_stages_and_entry(ren1_dst,
1030                                                        ren1->dst_entry,
1031                                                        ren1->pair->one,
1032                                                        ren1->pair->two,
1033                                                        ren2->pair->two,
1034                                                        1 /* clear */);
1035                        }
1036                } else {
1037                        /* Renamed in 1, maybe changed in 2 */
1038                        struct string_list_item *item;
1039                        /* we only use sha1 and mode of these */
1040                        struct diff_filespec src_other, dst_other;
1041                        int try_merge;
1042
1043                        /*
1044                         * unpack_trees loads entries from common-commit
1045                         * into stage 1, from head-commit into stage 2, and
1046                         * from merge-commit into stage 3.  We keep track
1047                         * of which side corresponds to the rename.
1048                         */
1049                        int renamed_stage = a_renames == renames1 ? 2 : 3;
1050                        int other_stage =   a_renames == renames1 ? 3 : 2;
1051
1052                        remove_file(o, 1, ren1_src, o->call_depth || renamed_stage == 2);
1053
1054                        hashcpy(src_other.sha1, ren1->src_entry->stages[other_stage].sha);
1055                        src_other.mode = ren1->src_entry->stages[other_stage].mode;
1056                        hashcpy(dst_other.sha1, ren1->dst_entry->stages[other_stage].sha);
1057                        dst_other.mode = ren1->dst_entry->stages[other_stage].mode;
1058                        try_merge = 0;
1059
1060                        if (sha_eq(src_other.sha1, null_sha1)) {
1061                                if (string_list_has_string(&o->current_directory_set, ren1_dst)) {
1062                                        ren1->dst_entry->processed = 0;
1063                                        setup_rename_df_conflict_info(RENAME_DELETE,
1064                                                                      ren1->pair,
1065                                                                      NULL,
1066                                                                      branch1,
1067                                                                      branch2,
1068                                                                      ren1->dst_entry,
1069                                                                      NULL);
1070                                } else {
1071                                        clean_merge = 0;
1072                                        conflict_rename_delete(o, ren1->pair, branch1, branch2);
1073                                }
1074                        } else if ((dst_other.mode == ren1->pair->two->mode) &&
1075                                   sha_eq(dst_other.sha1, ren1->pair->two->sha1)) {
1076                                /* Added file on the other side
1077                                   identical to the file being
1078                                   renamed: clean merge */
1079                                update_file(o, 1, ren1->pair->two->sha1, ren1->pair->two->mode, ren1_dst);
1080                        } else if (!sha_eq(dst_other.sha1, null_sha1)) {
1081                                const char *new_path;
1082                                clean_merge = 0;
1083                                try_merge = 1;
1084                                output(o, 1, "CONFLICT (rename/add): Rename %s->%s in %s. "
1085                                       "%s added in %s",
1086                                       ren1_src, ren1_dst, branch1,
1087                                       ren1_dst, branch2);
1088                                if (o->call_depth) {
1089                                        struct merge_file_info mfi;
1090                                        struct diff_filespec one, a, b;
1091
1092                                        one.path = a.path = b.path =
1093                                                (char *)ren1_dst;
1094                                        hashcpy(one.sha1, null_sha1);
1095                                        one.mode = 0;
1096                                        hashcpy(a.sha1, ren1->pair->two->sha1);
1097                                        a.mode = ren1->pair->two->mode;
1098                                        hashcpy(b.sha1, dst_other.sha1);
1099                                        b.mode = dst_other.mode;
1100                                        mfi = merge_file(o, &one, &a, &b,
1101                                                         branch1,
1102                                                         branch2);
1103                                        output(o, 1, "Adding merged %s", ren1_dst);
1104                                        update_file(o, 0,
1105                                                    mfi.sha,
1106                                                    mfi.mode,
1107                                                    ren1_dst);
1108                                        try_merge = 0;
1109                                } else {
1110                                        new_path = unique_path(o, ren1_dst, branch2);
1111                                        output(o, 1, "Adding as %s instead", new_path);
1112                                        update_file(o, 0, dst_other.sha1, dst_other.mode, new_path);
1113                                }
1114                        } else if ((item = string_list_lookup(renames2Dst, ren1_dst))) {
1115                                ren2 = item->util;
1116                                clean_merge = 0;
1117                                ren2->processed = 1;
1118                                output(o, 1, "CONFLICT (rename/rename): "
1119                                       "Rename %s->%s in %s. "
1120                                       "Rename %s->%s in %s",
1121                                       ren1_src, ren1_dst, branch1,
1122                                       ren2->pair->one->path, ren2->pair->two->path, branch2);
1123                                conflict_rename_rename_2to1(o, ren1, branch1, ren2, branch2);
1124                        } else
1125                                try_merge = 1;
1126
1127                        if (try_merge) {
1128                                struct diff_filespec *one, *a, *b;
1129                                src_other.path = (char *)ren1_src;
1130
1131                                one = ren1->pair->one;
1132                                if (a_renames == renames1) {
1133                                        a = ren1->pair->two;
1134                                        b = &src_other;
1135                                } else {
1136                                        b = ren1->pair->two;
1137                                        a = &src_other;
1138                                }
1139                                update_stages_and_entry(ren1_dst, ren1->dst_entry, one, a, b, 1);
1140                                if (string_list_has_string(&o->current_directory_set, ren1_dst)) {
1141                                        setup_rename_df_conflict_info(RENAME_NORMAL,
1142                                                                      ren1->pair,
1143                                                                      NULL,
1144                                                                      branch1,
1145                                                                      NULL,
1146                                                                      ren1->dst_entry,
1147                                                                      NULL);
1148                                }
1149                        }
1150                }
1151        }
1152        string_list_clear(&a_by_dst, 0);
1153        string_list_clear(&b_by_dst, 0);
1154
1155        return clean_merge;
1156}
1157
1158static unsigned char *stage_sha(const unsigned char *sha, unsigned mode)
1159{
1160        return (is_null_sha1(sha) || mode == 0) ? NULL: (unsigned char *)sha;
1161}
1162
1163static int read_sha1_strbuf(const unsigned char *sha1, struct strbuf *dst)
1164{
1165        void *buf;
1166        enum object_type type;
1167        unsigned long size;
1168        buf = read_sha1_file(sha1, &type, &size);
1169        if (!buf)
1170                return error("cannot read object %s", sha1_to_hex(sha1));
1171        if (type != OBJ_BLOB) {
1172                free(buf);
1173                return error("object %s is not a blob", sha1_to_hex(sha1));
1174        }
1175        strbuf_attach(dst, buf, size, size + 1);
1176        return 0;
1177}
1178
1179static int blob_unchanged(const unsigned char *o_sha,
1180                          const unsigned char *a_sha,
1181                          int renormalize, const char *path)
1182{
1183        struct strbuf o = STRBUF_INIT;
1184        struct strbuf a = STRBUF_INIT;
1185        int ret = 0; /* assume changed for safety */
1186
1187        if (sha_eq(o_sha, a_sha))
1188                return 1;
1189        if (!renormalize)
1190                return 0;
1191
1192        assert(o_sha && a_sha);
1193        if (read_sha1_strbuf(o_sha, &o) || read_sha1_strbuf(a_sha, &a))
1194                goto error_return;
1195        /*
1196         * Note: binary | is used so that both renormalizations are
1197         * performed.  Comparison can be skipped if both files are
1198         * unchanged since their sha1s have already been compared.
1199         */
1200        if (renormalize_buffer(path, o.buf, o.len, &o) |
1201            renormalize_buffer(path, a.buf, o.len, &a))
1202                ret = (o.len == a.len && !memcmp(o.buf, a.buf, o.len));
1203
1204error_return:
1205        strbuf_release(&o);
1206        strbuf_release(&a);
1207        return ret;
1208}
1209
1210static void handle_delete_modify(struct merge_options *o,
1211                                 const char *path,
1212                                 const char *new_path,
1213                                 unsigned char *a_sha, int a_mode,
1214                                 unsigned char *b_sha, int b_mode)
1215{
1216        if (!a_sha) {
1217                output(o, 1, "CONFLICT (delete/modify): %s deleted in %s "
1218                       "and modified in %s. Version %s of %s left in tree%s%s.",
1219                       path, o->branch1,
1220                       o->branch2, o->branch2, path,
1221                       path == new_path ? "" : " at ",
1222                       path == new_path ? "" : new_path);
1223                update_file(o, 0, b_sha, b_mode, new_path);
1224        } else {
1225                output(o, 1, "CONFLICT (delete/modify): %s deleted in %s "
1226                       "and modified in %s. Version %s of %s left in tree%s%s.",
1227                       path, o->branch2,
1228                       o->branch1, o->branch1, path,
1229                       path == new_path ? "" : " at ",
1230                       path == new_path ? "" : new_path);
1231                update_file(o, 0, a_sha, a_mode, new_path);
1232        }
1233}
1234
1235static int merge_content(struct merge_options *o,
1236                         const char *path,
1237                         unsigned char *o_sha, int o_mode,
1238                         unsigned char *a_sha, int a_mode,
1239                         unsigned char *b_sha, int b_mode,
1240                         const char *df_rename_conflict_branch)
1241{
1242        const char *reason = "content";
1243        struct merge_file_info mfi;
1244        struct diff_filespec one, a, b;
1245        struct stat st;
1246        unsigned df_conflict_remains = 0;
1247
1248        if (!o_sha) {
1249                reason = "add/add";
1250                o_sha = (unsigned char *)null_sha1;
1251        }
1252        one.path = a.path = b.path = (char *)path;
1253        hashcpy(one.sha1, o_sha);
1254        one.mode = o_mode;
1255        hashcpy(a.sha1, a_sha);
1256        a.mode = a_mode;
1257        hashcpy(b.sha1, b_sha);
1258        b.mode = b_mode;
1259
1260        mfi = merge_file(o, &one, &a, &b, o->branch1, o->branch2);
1261        if (df_rename_conflict_branch &&
1262            lstat(path, &st) == 0 && S_ISDIR(st.st_mode)) {
1263                df_conflict_remains = 1;
1264        }
1265
1266        if (mfi.clean && !df_conflict_remains &&
1267            sha_eq(mfi.sha, a_sha) && mfi.mode == a.mode)
1268                output(o, 3, "Skipped %s (merged same as existing)", path);
1269        else
1270                output(o, 2, "Auto-merging %s", path);
1271
1272        if (!mfi.clean) {
1273                if (S_ISGITLINK(mfi.mode))
1274                        reason = "submodule";
1275                output(o, 1, "CONFLICT (%s): Merge conflict in %s",
1276                                reason, path);
1277        }
1278
1279        if (df_conflict_remains) {
1280                const char *new_path;
1281                update_file_flags(o, mfi.sha, mfi.mode, path,
1282                                  o->call_depth || mfi.clean, 0);
1283                new_path = unique_path(o, path, df_rename_conflict_branch);
1284                mfi.clean = 0;
1285                output(o, 1, "Adding as %s instead", new_path);
1286                update_file_flags(o, mfi.sha, mfi.mode, new_path, 0, 1);
1287        } else {
1288                update_file(o, mfi.clean, mfi.sha, mfi.mode, path);
1289        }
1290        return mfi.clean;
1291
1292}
1293
1294/* Per entry merge function */
1295static int process_entry(struct merge_options *o,
1296                         const char *path, struct stage_data *entry)
1297{
1298        /*
1299        printf("processing entry, clean cache: %s\n", index_only ? "yes": "no");
1300        print_index_entry("\tpath: ", entry);
1301        */
1302        int clean_merge = 1;
1303        int normalize = o->renormalize;
1304        unsigned o_mode = entry->stages[1].mode;
1305        unsigned a_mode = entry->stages[2].mode;
1306        unsigned b_mode = entry->stages[3].mode;
1307        unsigned char *o_sha = stage_sha(entry->stages[1].sha, o_mode);
1308        unsigned char *a_sha = stage_sha(entry->stages[2].sha, a_mode);
1309        unsigned char *b_sha = stage_sha(entry->stages[3].sha, b_mode);
1310
1311        if (entry->rename_df_conflict_info)
1312                return 1; /* Such cases are handled elsewhere. */
1313
1314        entry->processed = 1;
1315        if (o_sha && (!a_sha || !b_sha)) {
1316                /* Case A: Deleted in one */
1317                if ((!a_sha && !b_sha) ||
1318                    (!b_sha && blob_unchanged(o_sha, a_sha, normalize, path)) ||
1319                    (!a_sha && blob_unchanged(o_sha, b_sha, normalize, path))) {
1320                        /* Deleted in both or deleted in one and
1321                         * unchanged in the other */
1322                        if (a_sha)
1323                                output(o, 2, "Removing %s", path);
1324                        /* do not touch working file if it did not exist */
1325                        remove_file(o, 1, path, !a_sha);
1326                } else if (string_list_has_string(&o->current_directory_set,
1327                                                  path)) {
1328                        entry->processed = 0;
1329                        return 1; /* Assume clean until processed */
1330                } else {
1331                        /* Deleted in one and changed in the other */
1332                        clean_merge = 0;
1333                        handle_delete_modify(o, path, path,
1334                                             a_sha, a_mode, b_sha, b_mode);
1335                }
1336
1337        } else if ((!o_sha && a_sha && !b_sha) ||
1338                   (!o_sha && !a_sha && b_sha)) {
1339                /* Case B: Added in one. */
1340                unsigned mode;
1341                const unsigned char *sha;
1342
1343                if (a_sha) {
1344                        mode = a_mode;
1345                        sha = a_sha;
1346                } else {
1347                        mode = b_mode;
1348                        sha = b_sha;
1349                }
1350                if (string_list_has_string(&o->current_directory_set, path)) {
1351                        /* Handle D->F conflicts after all subfiles */
1352                        entry->processed = 0;
1353                        return 1; /* Assume clean until processed */
1354                } else {
1355                        output(o, 2, "Adding %s", path);
1356                        update_file(o, 1, sha, mode, path);
1357                }
1358        } else if (a_sha && b_sha) {
1359                /* Case C: Added in both (check for same permissions) and */
1360                /* case D: Modified in both, but differently. */
1361                clean_merge = merge_content(o, path,
1362                                            o_sha, o_mode, a_sha, a_mode, b_sha, b_mode,
1363                                            NULL);
1364        } else if (!o_sha && !a_sha && !b_sha) {
1365                /*
1366                 * this entry was deleted altogether. a_mode == 0 means
1367                 * we had that path and want to actively remove it.
1368                 */
1369                remove_file(o, 1, path, !a_mode);
1370        } else
1371                die("Fatal merge failure, shouldn't happen.");
1372
1373        return clean_merge;
1374}
1375
1376/*
1377 * Per entry merge function for D/F (and/or rename) conflicts.  In the
1378 * cases we can cleanly resolve D/F conflicts, process_entry() can
1379 * clean out all the files below the directory for us.  All D/F
1380 * conflict cases must be handled here at the end to make sure any
1381 * directories that can be cleaned out, are.
1382 *
1383 * Some rename conflicts may also be handled here that don't necessarily
1384 * involve D/F conflicts, since the code to handle them is generic enough
1385 * to handle those rename conflicts with or without D/F conflicts also
1386 * being involved.
1387 */
1388static int process_df_entry(struct merge_options *o,
1389                            const char *path, struct stage_data *entry)
1390{
1391        int clean_merge = 1;
1392        unsigned o_mode = entry->stages[1].mode;
1393        unsigned a_mode = entry->stages[2].mode;
1394        unsigned b_mode = entry->stages[3].mode;
1395        unsigned char *o_sha = stage_sha(entry->stages[1].sha, o_mode);
1396        unsigned char *a_sha = stage_sha(entry->stages[2].sha, a_mode);
1397        unsigned char *b_sha = stage_sha(entry->stages[3].sha, b_mode);
1398        struct stat st;
1399
1400        entry->processed = 1;
1401        if (entry->rename_df_conflict_info) {
1402                struct rename_df_conflict_info *conflict_info = entry->rename_df_conflict_info;
1403                char *src;
1404                switch (conflict_info->rename_type) {
1405                case RENAME_NORMAL:
1406                        clean_merge = merge_content(o, path,
1407                                                    o_sha, o_mode, a_sha, a_mode, b_sha, b_mode,
1408                                                    conflict_info->branch1);
1409                        break;
1410                case RENAME_DELETE:
1411                        clean_merge = 0;
1412                        conflict_rename_delete(o, conflict_info->pair1,
1413                                               conflict_info->branch1,
1414                                               conflict_info->branch2);
1415                        break;
1416                case RENAME_ONE_FILE_TO_TWO:
1417                        src = conflict_info->pair1->one->path;
1418                        clean_merge = 0;
1419                        output(o, 1, "CONFLICT (rename/rename): "
1420                               "Rename \"%s\"->\"%s\" in branch \"%s\" "
1421                               "rename \"%s\"->\"%s\" in \"%s\"%s",
1422                               src, conflict_info->pair1->two->path, conflict_info->branch1,
1423                               src, conflict_info->pair2->two->path, conflict_info->branch2,
1424                               o->call_depth ? " (left unresolved)" : "");
1425                        if (o->call_depth) {
1426                                remove_file_from_cache(src);
1427                                update_file(o, 0, conflict_info->pair1->one->sha1,
1428                                            conflict_info->pair1->one->mode, src);
1429                        }
1430                        conflict_rename_rename_1to2(o, conflict_info->pair1,
1431                                                    conflict_info->branch1,
1432                                                    conflict_info->pair2,
1433                                                    conflict_info->branch2);
1434                        conflict_info->dst_entry2->processed = 1;
1435                        break;
1436                default:
1437                        entry->processed = 0;
1438                        break;
1439                }
1440        } else if (o_sha && (!a_sha || !b_sha)) {
1441                /* Modify/delete; deleted side may have put a directory in the way */
1442                const char *new_path = path;
1443                if (lstat(path, &st) == 0 && S_ISDIR(st.st_mode))
1444                        new_path = unique_path(o, path, a_sha ? o->branch1 : o->branch2);
1445                clean_merge = 0;
1446                handle_delete_modify(o, path, new_path,
1447                                     a_sha, a_mode, b_sha, b_mode);
1448        } else if (!o_sha && !!a_sha != !!b_sha) {
1449                /* directory -> (directory, file) */
1450                const char *add_branch;
1451                const char *other_branch;
1452                unsigned mode;
1453                const unsigned char *sha;
1454                const char *conf;
1455
1456                if (a_sha) {
1457                        add_branch = o->branch1;
1458                        other_branch = o->branch2;
1459                        mode = a_mode;
1460                        sha = a_sha;
1461                        conf = "file/directory";
1462                } else {
1463                        add_branch = o->branch2;
1464                        other_branch = o->branch1;
1465                        mode = b_mode;
1466                        sha = b_sha;
1467                        conf = "directory/file";
1468                }
1469                if (lstat(path, &st) == 0 && S_ISDIR(st.st_mode)) {
1470                        const char *new_path = unique_path(o, path, add_branch);
1471                        clean_merge = 0;
1472                        output(o, 1, "CONFLICT (%s): There is a directory with name %s in %s. "
1473                               "Adding %s as %s",
1474                               conf, path, other_branch, path, new_path);
1475                        update_file(o, 0, sha, mode, new_path);
1476                } else {
1477                        output(o, 2, "Adding %s", path);
1478                        update_file(o, 1, sha, mode, path);
1479                }
1480        } else {
1481                entry->processed = 0;
1482                return 1; /* not handled; assume clean until processed */
1483        }
1484
1485        return clean_merge;
1486}
1487
1488int merge_trees(struct merge_options *o,
1489                struct tree *head,
1490                struct tree *merge,
1491                struct tree *common,
1492                struct tree **result)
1493{
1494        int code, clean;
1495
1496        if (o->subtree_shift) {
1497                merge = shift_tree_object(head, merge, o->subtree_shift);
1498                common = shift_tree_object(head, common, o->subtree_shift);
1499        }
1500
1501        if (sha_eq(common->object.sha1, merge->object.sha1)) {
1502                output(o, 0, "Already up-to-date!");
1503                *result = head;
1504                return 1;
1505        }
1506
1507        code = git_merge_trees(o->call_depth, common, head, merge);
1508
1509        if (code != 0) {
1510                if (show(o, 4) || o->call_depth)
1511                        die("merging of trees %s and %s failed",
1512                            sha1_to_hex(head->object.sha1),
1513                            sha1_to_hex(merge->object.sha1));
1514                else
1515                        exit(128);
1516        }
1517
1518        if (unmerged_cache()) {
1519                struct string_list *entries, *re_head, *re_merge;
1520                int i;
1521                string_list_clear(&o->current_file_set, 1);
1522                string_list_clear(&o->current_directory_set, 1);
1523                get_files_dirs(o, head);
1524                get_files_dirs(o, merge);
1525
1526                entries = get_unmerged();
1527                make_room_for_directories_of_df_conflicts(o, entries);
1528                re_head  = get_renames(o, head, common, head, merge, entries);
1529                re_merge = get_renames(o, merge, common, head, merge, entries);
1530                clean = process_renames(o, re_head, re_merge);
1531                for (i = 0; i < entries->nr; i++) {
1532                        const char *path = entries->items[i].string;
1533                        struct stage_data *e = entries->items[i].util;
1534                        if (!e->processed
1535                                && !process_entry(o, path, e))
1536                                clean = 0;
1537                }
1538                for (i = 0; i < entries->nr; i++) {
1539                        const char *path = entries->items[i].string;
1540                        struct stage_data *e = entries->items[i].util;
1541                        if (!e->processed
1542                                && !process_df_entry(o, path, e))
1543                                clean = 0;
1544                }
1545                for (i = 0; i < entries->nr; i++) {
1546                        struct stage_data *e = entries->items[i].util;
1547                        if (!e->processed)
1548                                die("Unprocessed path??? %s",
1549                                    entries->items[i].string);
1550                }
1551
1552                string_list_clear(re_merge, 0);
1553                string_list_clear(re_head, 0);
1554                string_list_clear(entries, 1);
1555
1556        }
1557        else
1558                clean = 1;
1559
1560        if (o->call_depth)
1561                *result = write_tree_from_memory(o);
1562
1563        return clean;
1564}
1565
1566static struct commit_list *reverse_commit_list(struct commit_list *list)
1567{
1568        struct commit_list *next = NULL, *current, *backup;
1569        for (current = list; current; current = backup) {
1570                backup = current->next;
1571                current->next = next;
1572                next = current;
1573        }
1574        return next;
1575}
1576
1577/*
1578 * Merge the commits h1 and h2, return the resulting virtual
1579 * commit object and a flag indicating the cleanness of the merge.
1580 */
1581int merge_recursive(struct merge_options *o,
1582                    struct commit *h1,
1583                    struct commit *h2,
1584                    struct commit_list *ca,
1585                    struct commit **result)
1586{
1587        struct commit_list *iter;
1588        struct commit *merged_common_ancestors;
1589        struct tree *mrtree = mrtree;
1590        int clean;
1591
1592        if (show(o, 4)) {
1593                output(o, 4, "Merging:");
1594                output_commit_title(o, h1);
1595                output_commit_title(o, h2);
1596        }
1597
1598        if (!ca) {
1599                ca = get_merge_bases(h1, h2, 1);
1600                ca = reverse_commit_list(ca);
1601        }
1602
1603        if (show(o, 5)) {
1604                output(o, 5, "found %u common ancestor(s):", commit_list_count(ca));
1605                for (iter = ca; iter; iter = iter->next)
1606                        output_commit_title(o, iter->item);
1607        }
1608
1609        merged_common_ancestors = pop_commit(&ca);
1610        if (merged_common_ancestors == NULL) {
1611                /* if there is no common ancestor, make an empty tree */
1612                struct tree *tree = xcalloc(1, sizeof(struct tree));
1613
1614                tree->object.parsed = 1;
1615                tree->object.type = OBJ_TREE;
1616                pretend_sha1_file(NULL, 0, OBJ_TREE, tree->object.sha1);
1617                merged_common_ancestors = make_virtual_commit(tree, "ancestor");
1618        }
1619
1620        for (iter = ca; iter; iter = iter->next) {
1621                const char *saved_b1, *saved_b2;
1622                o->call_depth++;
1623                /*
1624                 * When the merge fails, the result contains files
1625                 * with conflict markers. The cleanness flag is
1626                 * ignored, it was never actually used, as result of
1627                 * merge_trees has always overwritten it: the committed
1628                 * "conflicts" were already resolved.
1629                 */
1630                discard_cache();
1631                saved_b1 = o->branch1;
1632                saved_b2 = o->branch2;
1633                o->branch1 = "Temporary merge branch 1";
1634                o->branch2 = "Temporary merge branch 2";
1635                merge_recursive(o, merged_common_ancestors, iter->item,
1636                                NULL, &merged_common_ancestors);
1637                o->branch1 = saved_b1;
1638                o->branch2 = saved_b2;
1639                o->call_depth--;
1640
1641                if (!merged_common_ancestors)
1642                        die("merge returned no commit");
1643        }
1644
1645        discard_cache();
1646        if (!o->call_depth)
1647                read_cache();
1648
1649        o->ancestor = "merged common ancestors";
1650        clean = merge_trees(o, h1->tree, h2->tree, merged_common_ancestors->tree,
1651                            &mrtree);
1652
1653        if (o->call_depth) {
1654                *result = make_virtual_commit(mrtree, "merged tree");
1655                commit_list_insert(h1, &(*result)->parents);
1656                commit_list_insert(h2, &(*result)->parents->next);
1657        }
1658        flush_output(o);
1659        if (o->needed_rename_limit)
1660                warning(rename_limit_advice, o->needed_rename_limit);
1661        return clean;
1662}
1663
1664static struct commit *get_ref(const unsigned char *sha1, const char *name)
1665{
1666        struct object *object;
1667
1668        object = deref_tag(parse_object(sha1), name, strlen(name));
1669        if (!object)
1670                return NULL;
1671        if (object->type == OBJ_TREE)
1672                return make_virtual_commit((struct tree*)object, name);
1673        if (object->type != OBJ_COMMIT)
1674                return NULL;
1675        if (parse_commit((struct commit *)object))
1676                return NULL;
1677        return (struct commit *)object;
1678}
1679
1680int merge_recursive_generic(struct merge_options *o,
1681                            const unsigned char *head,
1682                            const unsigned char *merge,
1683                            int num_base_list,
1684                            const unsigned char **base_list,
1685                            struct commit **result)
1686{
1687        int clean, index_fd;
1688        struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));
1689        struct commit *head_commit = get_ref(head, o->branch1);
1690        struct commit *next_commit = get_ref(merge, o->branch2);
1691        struct commit_list *ca = NULL;
1692
1693        if (base_list) {
1694                int i;
1695                for (i = 0; i < num_base_list; ++i) {
1696                        struct commit *base;
1697                        if (!(base = get_ref(base_list[i], sha1_to_hex(base_list[i]))))
1698                                return error("Could not parse object '%s'",
1699                                        sha1_to_hex(base_list[i]));
1700                        commit_list_insert(base, &ca);
1701                }
1702        }
1703
1704        index_fd = hold_locked_index(lock, 1);
1705        clean = merge_recursive(o, head_commit, next_commit, ca,
1706                        result);
1707        if (active_cache_changed &&
1708                        (write_cache(index_fd, active_cache, active_nr) ||
1709                         commit_locked_index(lock)))
1710                return error("Unable to write index.");
1711
1712        return clean ? 0 : 1;
1713}
1714
1715static int merge_recursive_config(const char *var, const char *value, void *cb)
1716{
1717        struct merge_options *o = cb;
1718        if (!strcasecmp(var, "merge.verbosity")) {
1719                o->verbosity = git_config_int(var, value);
1720                return 0;
1721        }
1722        if (!strcasecmp(var, "diff.renamelimit")) {
1723                o->diff_rename_limit = git_config_int(var, value);
1724                return 0;
1725        }
1726        if (!strcasecmp(var, "merge.renamelimit")) {
1727                o->merge_rename_limit = git_config_int(var, value);
1728                return 0;
1729        }
1730        return git_xmerge_config(var, value, cb);
1731}
1732
1733void init_merge_options(struct merge_options *o)
1734{
1735        memset(o, 0, sizeof(struct merge_options));
1736        o->verbosity = 2;
1737        o->buffer_output = 1;
1738        o->diff_rename_limit = -1;
1739        o->merge_rename_limit = -1;
1740        o->renormalize = 0;
1741        git_config(merge_recursive_config, o);
1742        if (getenv("GIT_MERGE_VERBOSITY"))
1743                o->verbosity =
1744                        strtol(getenv("GIT_MERGE_VERBOSITY"), NULL, 10);
1745        if (o->verbosity >= 5)
1746                o->buffer_output = 0;
1747        strbuf_init(&o->obuf, 0);
1748        memset(&o->current_file_set, 0, sizeof(struct string_list));
1749        o->current_file_set.strdup_strings = 1;
1750        memset(&o->current_directory_set, 0, sizeof(struct string_list));
1751        o->current_directory_set.strdup_strings = 1;
1752}
1753
1754int parse_merge_opt(struct merge_options *o, const char *s)
1755{
1756        if (!s || !*s)
1757                return -1;
1758        if (!strcmp(s, "ours"))
1759                o->recursive_variant = MERGE_RECURSIVE_OURS;
1760        else if (!strcmp(s, "theirs"))
1761                o->recursive_variant = MERGE_RECURSIVE_THEIRS;
1762        else if (!strcmp(s, "subtree"))
1763                o->subtree_shift = "";
1764        else if (!prefixcmp(s, "subtree="))
1765                o->subtree_shift = s + strlen("subtree=");
1766        else if (!strcmp(s, "patience"))
1767                o->xdl_opts |= XDF_PATIENCE_DIFF;
1768        else if (!strcmp(s, "ignore-space-change"))
1769                o->xdl_opts |= XDF_IGNORE_WHITESPACE_CHANGE;
1770        else if (!strcmp(s, "ignore-all-space"))
1771                o->xdl_opts |= XDF_IGNORE_WHITESPACE;
1772        else if (!strcmp(s, "ignore-space-at-eol"))
1773                o->xdl_opts |= XDF_IGNORE_WHITESPACE_AT_EOL;
1774        else if (!strcmp(s, "renormalize"))
1775                o->renormalize = 1;
1776        else if (!strcmp(s, "no-renormalize"))
1777                o->renormalize = 0;
1778        else if (!prefixcmp(s, "rename-threshold=")) {
1779                const char *score = s + strlen("rename-threshold=");
1780                if ((o->rename_score = parse_rename_score(&score)) == -1 || *score != 0)
1781                        return -1;
1782        }
1783        else
1784                return -1;
1785        return 0;
1786}