merge-recursive.con commit Merge branch 'ar/request-pull-phrasofix' into maint (d9f5ea4)
   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 "cache.h"
   7#include "config.h"
   8#include "advice.h"
   9#include "lockfile.h"
  10#include "cache-tree.h"
  11#include "commit.h"
  12#include "blob.h"
  13#include "builtin.h"
  14#include "tree-walk.h"
  15#include "diff.h"
  16#include "diffcore.h"
  17#include "tag.h"
  18#include "unpack-trees.h"
  19#include "string-list.h"
  20#include "xdiff-interface.h"
  21#include "ll-merge.h"
  22#include "attr.h"
  23#include "merge-recursive.h"
  24#include "dir.h"
  25#include "submodule.h"
  26
  27static void flush_output(struct merge_options *o)
  28{
  29        if (o->buffer_output < 2 && o->obuf.len) {
  30                fputs(o->obuf.buf, stdout);
  31                strbuf_reset(&o->obuf);
  32        }
  33}
  34
  35static int err(struct merge_options *o, const char *err, ...)
  36{
  37        va_list params;
  38
  39        if (o->buffer_output < 2)
  40                flush_output(o);
  41        else {
  42                strbuf_complete(&o->obuf, '\n');
  43                strbuf_addstr(&o->obuf, "error: ");
  44        }
  45        va_start(params, err);
  46        strbuf_vaddf(&o->obuf, err, params);
  47        va_end(params);
  48        if (o->buffer_output > 1)
  49                strbuf_addch(&o->obuf, '\n');
  50        else {
  51                error("%s", o->obuf.buf);
  52                strbuf_reset(&o->obuf);
  53        }
  54
  55        return -1;
  56}
  57
  58static struct tree *shift_tree_object(struct tree *one, struct tree *two,
  59                                      const char *subtree_shift)
  60{
  61        struct object_id shifted;
  62
  63        if (!*subtree_shift) {
  64                shift_tree(&one->object.oid, &two->object.oid, &shifted, 0);
  65        } else {
  66                shift_tree_by(&one->object.oid, &two->object.oid, &shifted,
  67                              subtree_shift);
  68        }
  69        if (!oidcmp(&two->object.oid, &shifted))
  70                return two;
  71        return lookup_tree(&shifted);
  72}
  73
  74static struct commit *make_virtual_commit(struct tree *tree, const char *comment)
  75{
  76        struct commit *commit = alloc_commit_node();
  77
  78        set_merge_remote_desc(commit, comment, (struct object *)commit);
  79        commit->tree = tree;
  80        commit->object.parsed = 1;
  81        return commit;
  82}
  83
  84/*
  85 * Since we use get_tree_entry(), which does not put the read object into
  86 * the object pool, we cannot rely on a == b.
  87 */
  88static int oid_eq(const struct object_id *a, const struct object_id *b)
  89{
  90        if (!a && !b)
  91                return 2;
  92        return a && b && oidcmp(a, b) == 0;
  93}
  94
  95enum rename_type {
  96        RENAME_NORMAL = 0,
  97        RENAME_DELETE,
  98        RENAME_ONE_FILE_TO_ONE,
  99        RENAME_ONE_FILE_TO_TWO,
 100        RENAME_TWO_FILES_TO_ONE
 101};
 102
 103struct rename_conflict_info {
 104        enum rename_type rename_type;
 105        struct diff_filepair *pair1;
 106        struct diff_filepair *pair2;
 107        const char *branch1;
 108        const char *branch2;
 109        struct stage_data *dst_entry1;
 110        struct stage_data *dst_entry2;
 111        struct diff_filespec ren1_other;
 112        struct diff_filespec ren2_other;
 113};
 114
 115/*
 116 * Since we want to write the index eventually, we cannot reuse the index
 117 * for these (temporary) data.
 118 */
 119struct stage_data {
 120        struct {
 121                unsigned mode;
 122                struct object_id oid;
 123        } stages[4];
 124        struct rename_conflict_info *rename_conflict_info;
 125        unsigned processed:1;
 126};
 127
 128static inline void setup_rename_conflict_info(enum rename_type rename_type,
 129                                              struct diff_filepair *pair1,
 130                                              struct diff_filepair *pair2,
 131                                              const char *branch1,
 132                                              const char *branch2,
 133                                              struct stage_data *dst_entry1,
 134                                              struct stage_data *dst_entry2,
 135                                              struct merge_options *o,
 136                                              struct stage_data *src_entry1,
 137                                              struct stage_data *src_entry2)
 138{
 139        struct rename_conflict_info *ci = xcalloc(1, sizeof(struct rename_conflict_info));
 140        ci->rename_type = rename_type;
 141        ci->pair1 = pair1;
 142        ci->branch1 = branch1;
 143        ci->branch2 = branch2;
 144
 145        ci->dst_entry1 = dst_entry1;
 146        dst_entry1->rename_conflict_info = ci;
 147        dst_entry1->processed = 0;
 148
 149        assert(!pair2 == !dst_entry2);
 150        if (dst_entry2) {
 151                ci->dst_entry2 = dst_entry2;
 152                ci->pair2 = pair2;
 153                dst_entry2->rename_conflict_info = ci;
 154        }
 155
 156        if (rename_type == RENAME_TWO_FILES_TO_ONE) {
 157                /*
 158                 * For each rename, there could have been
 159                 * modifications on the side of history where that
 160                 * file was not renamed.
 161                 */
 162                int ostage1 = o->branch1 == branch1 ? 3 : 2;
 163                int ostage2 = ostage1 ^ 1;
 164
 165                ci->ren1_other.path = pair1->one->path;
 166                oidcpy(&ci->ren1_other.oid, &src_entry1->stages[ostage1].oid);
 167                ci->ren1_other.mode = src_entry1->stages[ostage1].mode;
 168
 169                ci->ren2_other.path = pair2->one->path;
 170                oidcpy(&ci->ren2_other.oid, &src_entry2->stages[ostage2].oid);
 171                ci->ren2_other.mode = src_entry2->stages[ostage2].mode;
 172        }
 173}
 174
 175static int show(struct merge_options *o, int v)
 176{
 177        return (!o->call_depth && o->verbosity >= v) || o->verbosity >= 5;
 178}
 179
 180__attribute__((format (printf, 3, 4)))
 181static void output(struct merge_options *o, int v, const char *fmt, ...)
 182{
 183        va_list ap;
 184
 185        if (!show(o, v))
 186                return;
 187
 188        strbuf_addchars(&o->obuf, ' ', o->call_depth * 2);
 189
 190        va_start(ap, fmt);
 191        strbuf_vaddf(&o->obuf, fmt, ap);
 192        va_end(ap);
 193
 194        strbuf_addch(&o->obuf, '\n');
 195        if (!o->buffer_output)
 196                flush_output(o);
 197}
 198
 199static void output_commit_title(struct merge_options *o, struct commit *commit)
 200{
 201        strbuf_addchars(&o->obuf, ' ', o->call_depth * 2);
 202        if (commit->util)
 203                strbuf_addf(&o->obuf, "virtual %s\n",
 204                        merge_remote_util(commit)->name);
 205        else {
 206                strbuf_add_unique_abbrev(&o->obuf, commit->object.oid.hash,
 207                                         DEFAULT_ABBREV);
 208                strbuf_addch(&o->obuf, ' ');
 209                if (parse_commit(commit) != 0)
 210                        strbuf_addstr(&o->obuf, _("(bad commit)\n"));
 211                else {
 212                        const char *title;
 213                        const char *msg = get_commit_buffer(commit, NULL);
 214                        int len = find_commit_subject(msg, &title);
 215                        if (len)
 216                                strbuf_addf(&o->obuf, "%.*s\n", len, title);
 217                        unuse_commit_buffer(commit, msg);
 218                }
 219        }
 220        flush_output(o);
 221}
 222
 223static int add_cacheinfo(struct merge_options *o,
 224                unsigned int mode, const struct object_id *oid,
 225                const char *path, int stage, int refresh, int options)
 226{
 227        struct cache_entry *ce;
 228        int ret;
 229
 230        ce = make_cache_entry(mode, oid ? oid->hash : null_sha1, path, stage, 0);
 231        if (!ce)
 232                return err(o, _("addinfo_cache failed for path '%s'"), path);
 233
 234        ret = add_cache_entry(ce, options);
 235        if (refresh) {
 236                struct cache_entry *nce;
 237
 238                nce = refresh_cache_entry(ce, CE_MATCH_REFRESH | CE_MATCH_IGNORE_MISSING);
 239                if (!nce)
 240                        return err(o, _("addinfo_cache failed for path '%s'"), path);
 241                if (nce != ce)
 242                        ret = add_cache_entry(nce, options);
 243        }
 244        return ret;
 245}
 246
 247static void init_tree_desc_from_tree(struct tree_desc *desc, struct tree *tree)
 248{
 249        parse_tree(tree);
 250        init_tree_desc(desc, tree->buffer, tree->size);
 251}
 252
 253static int git_merge_trees(int index_only,
 254                           struct tree *common,
 255                           struct tree *head,
 256                           struct tree *merge)
 257{
 258        int rc;
 259        struct tree_desc t[3];
 260        struct unpack_trees_options opts;
 261
 262        memset(&opts, 0, sizeof(opts));
 263        if (index_only)
 264                opts.index_only = 1;
 265        else
 266                opts.update = 1;
 267        opts.merge = 1;
 268        opts.head_idx = 2;
 269        opts.fn = threeway_merge;
 270        opts.src_index = &the_index;
 271        opts.dst_index = &the_index;
 272        setup_unpack_trees_porcelain(&opts, "merge");
 273
 274        init_tree_desc_from_tree(t+0, common);
 275        init_tree_desc_from_tree(t+1, head);
 276        init_tree_desc_from_tree(t+2, merge);
 277
 278        rc = unpack_trees(3, t, &opts);
 279        cache_tree_free(&active_cache_tree);
 280        return rc;
 281}
 282
 283struct tree *write_tree_from_memory(struct merge_options *o)
 284{
 285        struct tree *result = NULL;
 286
 287        if (unmerged_cache()) {
 288                int i;
 289                fprintf(stderr, "BUG: There are unmerged index entries:\n");
 290                for (i = 0; i < active_nr; i++) {
 291                        const struct cache_entry *ce = active_cache[i];
 292                        if (ce_stage(ce))
 293                                fprintf(stderr, "BUG: %d %.*s\n", ce_stage(ce),
 294                                        (int)ce_namelen(ce), ce->name);
 295                }
 296                die("BUG: unmerged index entries in merge-recursive.c");
 297        }
 298
 299        if (!active_cache_tree)
 300                active_cache_tree = cache_tree();
 301
 302        if (!cache_tree_fully_valid(active_cache_tree) &&
 303            cache_tree_update(&the_index, 0) < 0) {
 304                err(o, _("error building trees"));
 305                return NULL;
 306        }
 307
 308        result = lookup_tree(&active_cache_tree->oid);
 309
 310        return result;
 311}
 312
 313static int save_files_dirs(const unsigned char *sha1,
 314                struct strbuf *base, const char *path,
 315                unsigned int mode, int stage, void *context)
 316{
 317        int baselen = base->len;
 318        struct merge_options *o = context;
 319
 320        strbuf_addstr(base, path);
 321
 322        if (S_ISDIR(mode))
 323                string_list_insert(&o->current_directory_set, base->buf);
 324        else
 325                string_list_insert(&o->current_file_set, base->buf);
 326
 327        strbuf_setlen(base, baselen);
 328        return (S_ISDIR(mode) ? READ_TREE_RECURSIVE : 0);
 329}
 330
 331static int get_files_dirs(struct merge_options *o, struct tree *tree)
 332{
 333        int n;
 334        struct pathspec match_all;
 335        memset(&match_all, 0, sizeof(match_all));
 336        if (read_tree_recursive(tree, "", 0, 0, &match_all, save_files_dirs, o))
 337                return 0;
 338        n = o->current_file_set.nr + o->current_directory_set.nr;
 339        return n;
 340}
 341
 342/*
 343 * Returns an index_entry instance which doesn't have to correspond to
 344 * a real cache entry in Git's index.
 345 */
 346static struct stage_data *insert_stage_data(const char *path,
 347                struct tree *o, struct tree *a, struct tree *b,
 348                struct string_list *entries)
 349{
 350        struct string_list_item *item;
 351        struct stage_data *e = xcalloc(1, sizeof(struct stage_data));
 352        get_tree_entry(o->object.oid.hash, path,
 353                        e->stages[1].oid.hash, &e->stages[1].mode);
 354        get_tree_entry(a->object.oid.hash, path,
 355                        e->stages[2].oid.hash, &e->stages[2].mode);
 356        get_tree_entry(b->object.oid.hash, path,
 357                        e->stages[3].oid.hash, &e->stages[3].mode);
 358        item = string_list_insert(entries, path);
 359        item->util = e;
 360        return e;
 361}
 362
 363/*
 364 * Create a dictionary mapping file names to stage_data objects. The
 365 * dictionary contains one entry for every path with a non-zero stage entry.
 366 */
 367static struct string_list *get_unmerged(void)
 368{
 369        struct string_list *unmerged = xcalloc(1, sizeof(struct string_list));
 370        int i;
 371
 372        unmerged->strdup_strings = 1;
 373
 374        for (i = 0; i < active_nr; i++) {
 375                struct string_list_item *item;
 376                struct stage_data *e;
 377                const struct cache_entry *ce = active_cache[i];
 378                if (!ce_stage(ce))
 379                        continue;
 380
 381                item = string_list_lookup(unmerged, ce->name);
 382                if (!item) {
 383                        item = string_list_insert(unmerged, ce->name);
 384                        item->util = xcalloc(1, sizeof(struct stage_data));
 385                }
 386                e = item->util;
 387                e->stages[ce_stage(ce)].mode = ce->ce_mode;
 388                oidcpy(&e->stages[ce_stage(ce)].oid, &ce->oid);
 389        }
 390
 391        return unmerged;
 392}
 393
 394static int string_list_df_name_compare(const char *one, const char *two)
 395{
 396        int onelen = strlen(one);
 397        int twolen = strlen(two);
 398        /*
 399         * Here we only care that entries for D/F conflicts are
 400         * adjacent, in particular with the file of the D/F conflict
 401         * appearing before files below the corresponding directory.
 402         * The order of the rest of the list is irrelevant for us.
 403         *
 404         * To achieve this, we sort with df_name_compare and provide
 405         * the mode S_IFDIR so that D/F conflicts will sort correctly.
 406         * We use the mode S_IFDIR for everything else for simplicity,
 407         * since in other cases any changes in their order due to
 408         * sorting cause no problems for us.
 409         */
 410        int cmp = df_name_compare(one, onelen, S_IFDIR,
 411                                  two, twolen, S_IFDIR);
 412        /*
 413         * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
 414         * that 'foo' comes before 'foo/bar'.
 415         */
 416        if (cmp)
 417                return cmp;
 418        return onelen - twolen;
 419}
 420
 421static void record_df_conflict_files(struct merge_options *o,
 422                                     struct string_list *entries)
 423{
 424        /* If there is a D/F conflict and the file for such a conflict
 425         * currently exist in the working tree, we want to allow it to be
 426         * removed to make room for the corresponding directory if needed.
 427         * The files underneath the directories of such D/F conflicts will
 428         * be processed before the corresponding file involved in the D/F
 429         * conflict.  If the D/F directory ends up being removed by the
 430         * merge, then we won't have to touch the D/F file.  If the D/F
 431         * directory needs to be written to the working copy, then the D/F
 432         * file will simply be removed (in make_room_for_path()) to make
 433         * room for the necessary paths.  Note that if both the directory
 434         * and the file need to be present, then the D/F file will be
 435         * reinstated with a new unique name at the time it is processed.
 436         */
 437        struct string_list df_sorted_entries = STRING_LIST_INIT_NODUP;
 438        const char *last_file = NULL;
 439        int last_len = 0;
 440        int i;
 441
 442        /*
 443         * If we're merging merge-bases, we don't want to bother with
 444         * any working directory changes.
 445         */
 446        if (o->call_depth)
 447                return;
 448
 449        /* Ensure D/F conflicts are adjacent in the entries list. */
 450        for (i = 0; i < entries->nr; i++) {
 451                struct string_list_item *next = &entries->items[i];
 452                string_list_append(&df_sorted_entries, next->string)->util =
 453                                   next->util;
 454        }
 455        df_sorted_entries.cmp = string_list_df_name_compare;
 456        string_list_sort(&df_sorted_entries);
 457
 458        string_list_clear(&o->df_conflict_file_set, 1);
 459        for (i = 0; i < df_sorted_entries.nr; i++) {
 460                const char *path = df_sorted_entries.items[i].string;
 461                int len = strlen(path);
 462                struct stage_data *e = df_sorted_entries.items[i].util;
 463
 464                /*
 465                 * Check if last_file & path correspond to a D/F conflict;
 466                 * i.e. whether path is last_file+'/'+<something>.
 467                 * If so, record that it's okay to remove last_file to make
 468                 * room for path and friends if needed.
 469                 */
 470                if (last_file &&
 471                    len > last_len &&
 472                    memcmp(path, last_file, last_len) == 0 &&
 473                    path[last_len] == '/') {
 474                        string_list_insert(&o->df_conflict_file_set, last_file);
 475                }
 476
 477                /*
 478                 * Determine whether path could exist as a file in the
 479                 * working directory as a possible D/F conflict.  This
 480                 * will only occur when it exists in stage 2 as a
 481                 * file.
 482                 */
 483                if (S_ISREG(e->stages[2].mode) || S_ISLNK(e->stages[2].mode)) {
 484                        last_file = path;
 485                        last_len = len;
 486                } else {
 487                        last_file = NULL;
 488                }
 489        }
 490        string_list_clear(&df_sorted_entries, 0);
 491}
 492
 493struct rename {
 494        struct diff_filepair *pair;
 495        struct stage_data *src_entry;
 496        struct stage_data *dst_entry;
 497        unsigned processed:1;
 498};
 499
 500/*
 501 * Get information of all renames which occurred between 'o_tree' and
 502 * 'tree'. We need the three trees in the merge ('o_tree', 'a_tree' and
 503 * 'b_tree') to be able to associate the correct cache entries with
 504 * the rename information. 'tree' is always equal to either a_tree or b_tree.
 505 */
 506static struct string_list *get_renames(struct merge_options *o,
 507                                       struct tree *tree,
 508                                       struct tree *o_tree,
 509                                       struct tree *a_tree,
 510                                       struct tree *b_tree,
 511                                       struct string_list *entries)
 512{
 513        int i;
 514        struct string_list *renames;
 515        struct diff_options opts;
 516
 517        renames = xcalloc(1, sizeof(struct string_list));
 518        if (!o->detect_rename)
 519                return renames;
 520
 521        diff_setup(&opts);
 522        DIFF_OPT_SET(&opts, RECURSIVE);
 523        DIFF_OPT_CLR(&opts, RENAME_EMPTY);
 524        opts.detect_rename = DIFF_DETECT_RENAME;
 525        opts.rename_limit = o->merge_rename_limit >= 0 ? o->merge_rename_limit :
 526                            o->diff_rename_limit >= 0 ? o->diff_rename_limit :
 527                            1000;
 528        opts.rename_score = o->rename_score;
 529        opts.show_rename_progress = o->show_rename_progress;
 530        opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 531        diff_setup_done(&opts);
 532        diff_tree_oid(&o_tree->object.oid, &tree->object.oid, "", &opts);
 533        diffcore_std(&opts);
 534        if (opts.needed_rename_limit > o->needed_rename_limit)
 535                o->needed_rename_limit = opts.needed_rename_limit;
 536        for (i = 0; i < diff_queued_diff.nr; ++i) {
 537                struct string_list_item *item;
 538                struct rename *re;
 539                struct diff_filepair *pair = diff_queued_diff.queue[i];
 540                if (pair->status != 'R') {
 541                        diff_free_filepair(pair);
 542                        continue;
 543                }
 544                re = xmalloc(sizeof(*re));
 545                re->processed = 0;
 546                re->pair = pair;
 547                item = string_list_lookup(entries, re->pair->one->path);
 548                if (!item)
 549                        re->src_entry = insert_stage_data(re->pair->one->path,
 550                                        o_tree, a_tree, b_tree, entries);
 551                else
 552                        re->src_entry = item->util;
 553
 554                item = string_list_lookup(entries, re->pair->two->path);
 555                if (!item)
 556                        re->dst_entry = insert_stage_data(re->pair->two->path,
 557                                        o_tree, a_tree, b_tree, entries);
 558                else
 559                        re->dst_entry = item->util;
 560                item = string_list_insert(renames, pair->one->path);
 561                item->util = re;
 562        }
 563        opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 564        diff_queued_diff.nr = 0;
 565        diff_flush(&opts);
 566        return renames;
 567}
 568
 569static int update_stages(struct merge_options *opt, const char *path,
 570                         const struct diff_filespec *o,
 571                         const struct diff_filespec *a,
 572                         const struct diff_filespec *b)
 573{
 574
 575        /*
 576         * NOTE: It is usually a bad idea to call update_stages on a path
 577         * before calling update_file on that same path, since it can
 578         * sometimes lead to spurious "refusing to lose untracked file..."
 579         * messages from update_file (via make_room_for path via
 580         * would_lose_untracked).  Instead, reverse the order of the calls
 581         * (executing update_file first and then update_stages).
 582         */
 583        int clear = 1;
 584        int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_SKIP_DFCHECK;
 585        if (clear)
 586                if (remove_file_from_cache(path))
 587                        return -1;
 588        if (o)
 589                if (add_cacheinfo(opt, o->mode, &o->oid, path, 1, 0, options))
 590                        return -1;
 591        if (a)
 592                if (add_cacheinfo(opt, a->mode, &a->oid, path, 2, 0, options))
 593                        return -1;
 594        if (b)
 595                if (add_cacheinfo(opt, b->mode, &b->oid, path, 3, 0, options))
 596                        return -1;
 597        return 0;
 598}
 599
 600static void update_entry(struct stage_data *entry,
 601                         struct diff_filespec *o,
 602                         struct diff_filespec *a,
 603                         struct diff_filespec *b)
 604{
 605        entry->processed = 0;
 606        entry->stages[1].mode = o->mode;
 607        entry->stages[2].mode = a->mode;
 608        entry->stages[3].mode = b->mode;
 609        oidcpy(&entry->stages[1].oid, &o->oid);
 610        oidcpy(&entry->stages[2].oid, &a->oid);
 611        oidcpy(&entry->stages[3].oid, &b->oid);
 612}
 613
 614static int remove_file(struct merge_options *o, int clean,
 615                       const char *path, int no_wd)
 616{
 617        int update_cache = o->call_depth || clean;
 618        int update_working_directory = !o->call_depth && !no_wd;
 619
 620        if (update_cache) {
 621                if (remove_file_from_cache(path))
 622                        return -1;
 623        }
 624        if (update_working_directory) {
 625                if (ignore_case) {
 626                        struct cache_entry *ce;
 627                        ce = cache_file_exists(path, strlen(path), ignore_case);
 628                        if (ce && ce_stage(ce) == 0)
 629                                return 0;
 630                }
 631                if (remove_path(path))
 632                        return -1;
 633        }
 634        return 0;
 635}
 636
 637/* add a string to a strbuf, but converting "/" to "_" */
 638static void add_flattened_path(struct strbuf *out, const char *s)
 639{
 640        size_t i = out->len;
 641        strbuf_addstr(out, s);
 642        for (; i < out->len; i++)
 643                if (out->buf[i] == '/')
 644                        out->buf[i] = '_';
 645}
 646
 647static char *unique_path(struct merge_options *o, const char *path, const char *branch)
 648{
 649        struct strbuf newpath = STRBUF_INIT;
 650        int suffix = 0;
 651        size_t base_len;
 652
 653        strbuf_addf(&newpath, "%s~", path);
 654        add_flattened_path(&newpath, branch);
 655
 656        base_len = newpath.len;
 657        while (string_list_has_string(&o->current_file_set, newpath.buf) ||
 658               string_list_has_string(&o->current_directory_set, newpath.buf) ||
 659               (!o->call_depth && file_exists(newpath.buf))) {
 660                strbuf_setlen(&newpath, base_len);
 661                strbuf_addf(&newpath, "_%d", suffix++);
 662        }
 663
 664        string_list_insert(&o->current_file_set, newpath.buf);
 665        return strbuf_detach(&newpath, NULL);
 666}
 667
 668/**
 669 * Check whether a directory in the index is in the way of an incoming
 670 * file.  Return 1 if so.  If check_working_copy is non-zero, also
 671 * check the working directory.  If empty_ok is non-zero, also return
 672 * 0 in the case where the working-tree dir exists but is empty.
 673 */
 674static int dir_in_way(const char *path, int check_working_copy, int empty_ok)
 675{
 676        int pos;
 677        struct strbuf dirpath = STRBUF_INIT;
 678        struct stat st;
 679
 680        strbuf_addstr(&dirpath, path);
 681        strbuf_addch(&dirpath, '/');
 682
 683        pos = cache_name_pos(dirpath.buf, dirpath.len);
 684
 685        if (pos < 0)
 686                pos = -1 - pos;
 687        if (pos < active_nr &&
 688            !strncmp(dirpath.buf, active_cache[pos]->name, dirpath.len)) {
 689                strbuf_release(&dirpath);
 690                return 1;
 691        }
 692
 693        strbuf_release(&dirpath);
 694        return check_working_copy && !lstat(path, &st) && S_ISDIR(st.st_mode) &&
 695                !(empty_ok && is_empty_dir(path));
 696}
 697
 698static int was_tracked(const char *path)
 699{
 700        int pos = cache_name_pos(path, strlen(path));
 701
 702        if (0 <= pos)
 703                /* we have been tracking this path */
 704                return 1;
 705
 706        /*
 707         * Look for an unmerged entry for the path,
 708         * specifically stage #2, which would indicate
 709         * that "our" side before the merge started
 710         * had the path tracked (and resulted in a conflict).
 711         */
 712        for (pos = -1 - pos;
 713             pos < active_nr && !strcmp(path, active_cache[pos]->name);
 714             pos++)
 715                if (ce_stage(active_cache[pos]) == 2)
 716                        return 1;
 717        return 0;
 718}
 719
 720static int would_lose_untracked(const char *path)
 721{
 722        return !was_tracked(path) && file_exists(path);
 723}
 724
 725static int make_room_for_path(struct merge_options *o, const char *path)
 726{
 727        int status, i;
 728        const char *msg = _("failed to create path '%s'%s");
 729
 730        /* Unlink any D/F conflict files that are in the way */
 731        for (i = 0; i < o->df_conflict_file_set.nr; i++) {
 732                const char *df_path = o->df_conflict_file_set.items[i].string;
 733                size_t pathlen = strlen(path);
 734                size_t df_pathlen = strlen(df_path);
 735                if (df_pathlen < pathlen &&
 736                    path[df_pathlen] == '/' &&
 737                    strncmp(path, df_path, df_pathlen) == 0) {
 738                        output(o, 3,
 739                               _("Removing %s to make room for subdirectory\n"),
 740                               df_path);
 741                        unlink(df_path);
 742                        unsorted_string_list_delete_item(&o->df_conflict_file_set,
 743                                                         i, 0);
 744                        break;
 745                }
 746        }
 747
 748        /* Make sure leading directories are created */
 749        status = safe_create_leading_directories_const(path);
 750        if (status) {
 751                if (status == SCLD_EXISTS)
 752                        /* something else exists */
 753                        return err(o, msg, path, _(": perhaps a D/F conflict?"));
 754                return err(o, msg, path, "");
 755        }
 756
 757        /*
 758         * Do not unlink a file in the work tree if we are not
 759         * tracking it.
 760         */
 761        if (would_lose_untracked(path))
 762                return err(o, _("refusing to lose untracked file at '%s'"),
 763                             path);
 764
 765        /* Successful unlink is good.. */
 766        if (!unlink(path))
 767                return 0;
 768        /* .. and so is no existing file */
 769        if (errno == ENOENT)
 770                return 0;
 771        /* .. but not some other error (who really cares what?) */
 772        return err(o, msg, path, _(": perhaps a D/F conflict?"));
 773}
 774
 775static int update_file_flags(struct merge_options *o,
 776                             const struct object_id *oid,
 777                             unsigned mode,
 778                             const char *path,
 779                             int update_cache,
 780                             int update_wd)
 781{
 782        int ret = 0;
 783
 784        if (o->call_depth)
 785                update_wd = 0;
 786
 787        if (update_wd) {
 788                enum object_type type;
 789                void *buf;
 790                unsigned long size;
 791
 792                if (S_ISGITLINK(mode)) {
 793                        /*
 794                         * We may later decide to recursively descend into
 795                         * the submodule directory and update its index
 796                         * and/or work tree, but we do not do that now.
 797                         */
 798                        update_wd = 0;
 799                        goto update_index;
 800                }
 801
 802                buf = read_sha1_file(oid->hash, &type, &size);
 803                if (!buf)
 804                        return err(o, _("cannot read object %s '%s'"), oid_to_hex(oid), path);
 805                if (type != OBJ_BLOB) {
 806                        ret = err(o, _("blob expected for %s '%s'"), oid_to_hex(oid), path);
 807                        goto free_buf;
 808                }
 809                if (S_ISREG(mode)) {
 810                        struct strbuf strbuf = STRBUF_INIT;
 811                        if (convert_to_working_tree(path, buf, size, &strbuf)) {
 812                                free(buf);
 813                                size = strbuf.len;
 814                                buf = strbuf_detach(&strbuf, NULL);
 815                        }
 816                }
 817
 818                if (make_room_for_path(o, path) < 0) {
 819                        update_wd = 0;
 820                        goto free_buf;
 821                }
 822                if (S_ISREG(mode) || (!has_symlinks && S_ISLNK(mode))) {
 823                        int fd;
 824                        if (mode & 0100)
 825                                mode = 0777;
 826                        else
 827                                mode = 0666;
 828                        fd = open(path, O_WRONLY | O_TRUNC | O_CREAT, mode);
 829                        if (fd < 0) {
 830                                ret = err(o, _("failed to open '%s': %s"),
 831                                          path, strerror(errno));
 832                                goto free_buf;
 833                        }
 834                        write_in_full(fd, buf, size);
 835                        close(fd);
 836                } else if (S_ISLNK(mode)) {
 837                        char *lnk = xmemdupz(buf, size);
 838                        safe_create_leading_directories_const(path);
 839                        unlink(path);
 840                        if (symlink(lnk, path))
 841                                ret = err(o, _("failed to symlink '%s': %s"),
 842                                        path, strerror(errno));
 843                        free(lnk);
 844                } else
 845                        ret = err(o,
 846                                  _("do not know what to do with %06o %s '%s'"),
 847                                  mode, oid_to_hex(oid), path);
 848 free_buf:
 849                free(buf);
 850        }
 851 update_index:
 852        if (!ret && update_cache)
 853                add_cacheinfo(o, mode, oid, path, 0, update_wd, ADD_CACHE_OK_TO_ADD);
 854        return ret;
 855}
 856
 857static int update_file(struct merge_options *o,
 858                       int clean,
 859                       const struct object_id *oid,
 860                       unsigned mode,
 861                       const char *path)
 862{
 863        return update_file_flags(o, oid, mode, path, o->call_depth || clean, !o->call_depth);
 864}
 865
 866/* Low level file merging, update and removal */
 867
 868struct merge_file_info {
 869        struct object_id oid;
 870        unsigned mode;
 871        unsigned clean:1,
 872                 merge:1;
 873};
 874
 875static int merge_3way(struct merge_options *o,
 876                      mmbuffer_t *result_buf,
 877                      const struct diff_filespec *one,
 878                      const struct diff_filespec *a,
 879                      const struct diff_filespec *b,
 880                      const char *branch1,
 881                      const char *branch2)
 882{
 883        mmfile_t orig, src1, src2;
 884        struct ll_merge_options ll_opts = {0};
 885        char *base_name, *name1, *name2;
 886        int merge_status;
 887
 888        ll_opts.renormalize = o->renormalize;
 889        ll_opts.xdl_opts = o->xdl_opts;
 890
 891        if (o->call_depth) {
 892                ll_opts.virtual_ancestor = 1;
 893                ll_opts.variant = 0;
 894        } else {
 895                switch (o->recursive_variant) {
 896                case MERGE_RECURSIVE_OURS:
 897                        ll_opts.variant = XDL_MERGE_FAVOR_OURS;
 898                        break;
 899                case MERGE_RECURSIVE_THEIRS:
 900                        ll_opts.variant = XDL_MERGE_FAVOR_THEIRS;
 901                        break;
 902                default:
 903                        ll_opts.variant = 0;
 904                        break;
 905                }
 906        }
 907
 908        if (strcmp(a->path, b->path) ||
 909            (o->ancestor != NULL && strcmp(a->path, one->path) != 0)) {
 910                base_name = o->ancestor == NULL ? NULL :
 911                        mkpathdup("%s:%s", o->ancestor, one->path);
 912                name1 = mkpathdup("%s:%s", branch1, a->path);
 913                name2 = mkpathdup("%s:%s", branch2, b->path);
 914        } else {
 915                base_name = o->ancestor == NULL ? NULL :
 916                        mkpathdup("%s", o->ancestor);
 917                name1 = mkpathdup("%s", branch1);
 918                name2 = mkpathdup("%s", branch2);
 919        }
 920
 921        read_mmblob(&orig, &one->oid);
 922        read_mmblob(&src1, &a->oid);
 923        read_mmblob(&src2, &b->oid);
 924
 925        merge_status = ll_merge(result_buf, a->path, &orig, base_name,
 926                                &src1, name1, &src2, name2, &ll_opts);
 927
 928        free(base_name);
 929        free(name1);
 930        free(name2);
 931        free(orig.ptr);
 932        free(src1.ptr);
 933        free(src2.ptr);
 934        return merge_status;
 935}
 936
 937static int merge_file_1(struct merge_options *o,
 938                                           const struct diff_filespec *one,
 939                                           const struct diff_filespec *a,
 940                                           const struct diff_filespec *b,
 941                                           const char *branch1,
 942                                           const char *branch2,
 943                                           struct merge_file_info *result)
 944{
 945        result->merge = 0;
 946        result->clean = 1;
 947
 948        if ((S_IFMT & a->mode) != (S_IFMT & b->mode)) {
 949                result->clean = 0;
 950                if (S_ISREG(a->mode)) {
 951                        result->mode = a->mode;
 952                        oidcpy(&result->oid, &a->oid);
 953                } else {
 954                        result->mode = b->mode;
 955                        oidcpy(&result->oid, &b->oid);
 956                }
 957        } else {
 958                if (!oid_eq(&a->oid, &one->oid) && !oid_eq(&b->oid, &one->oid))
 959                        result->merge = 1;
 960
 961                /*
 962                 * Merge modes
 963                 */
 964                if (a->mode == b->mode || a->mode == one->mode)
 965                        result->mode = b->mode;
 966                else {
 967                        result->mode = a->mode;
 968                        if (b->mode != one->mode) {
 969                                result->clean = 0;
 970                                result->merge = 1;
 971                        }
 972                }
 973
 974                if (oid_eq(&a->oid, &b->oid) || oid_eq(&a->oid, &one->oid))
 975                        oidcpy(&result->oid, &b->oid);
 976                else if (oid_eq(&b->oid, &one->oid))
 977                        oidcpy(&result->oid, &a->oid);
 978                else if (S_ISREG(a->mode)) {
 979                        mmbuffer_t result_buf;
 980                        int ret = 0, merge_status;
 981
 982                        merge_status = merge_3way(o, &result_buf, one, a, b,
 983                                                  branch1, branch2);
 984
 985                        if ((merge_status < 0) || !result_buf.ptr)
 986                                ret = err(o, _("Failed to execute internal merge"));
 987
 988                        if (!ret && write_sha1_file(result_buf.ptr, result_buf.size,
 989                                                    blob_type, result->oid.hash))
 990                                ret = err(o, _("Unable to add %s to database"),
 991                                          a->path);
 992
 993                        free(result_buf.ptr);
 994                        if (ret)
 995                                return ret;
 996                        result->clean = (merge_status == 0);
 997                } else if (S_ISGITLINK(a->mode)) {
 998                        result->clean = merge_submodule(&result->oid,
 999                                                       one->path,
1000                                                       &one->oid,
1001                                                       &a->oid,
1002                                                       &b->oid,
1003                                                       !o->call_depth);
1004                } else if (S_ISLNK(a->mode)) {
1005                        oidcpy(&result->oid, &a->oid);
1006
1007                        if (!oid_eq(&a->oid, &b->oid))
1008                                result->clean = 0;
1009                } else
1010                        die("BUG: unsupported object type in the tree");
1011        }
1012
1013        return 0;
1014}
1015
1016static int merge_file_special_markers(struct merge_options *o,
1017                           const struct diff_filespec *one,
1018                           const struct diff_filespec *a,
1019                           const struct diff_filespec *b,
1020                           const char *branch1,
1021                           const char *filename1,
1022                           const char *branch2,
1023                           const char *filename2,
1024                           struct merge_file_info *mfi)
1025{
1026        char *side1 = NULL;
1027        char *side2 = NULL;
1028        int ret;
1029
1030        if (filename1)
1031                side1 = xstrfmt("%s:%s", branch1, filename1);
1032        if (filename2)
1033                side2 = xstrfmt("%s:%s", branch2, filename2);
1034
1035        ret = merge_file_1(o, one, a, b,
1036                           side1 ? side1 : branch1,
1037                           side2 ? side2 : branch2, mfi);
1038        free(side1);
1039        free(side2);
1040        return ret;
1041}
1042
1043static int merge_file_one(struct merge_options *o,
1044                                         const char *path,
1045                                         const struct object_id *o_oid, int o_mode,
1046                                         const struct object_id *a_oid, int a_mode,
1047                                         const struct object_id *b_oid, int b_mode,
1048                                         const char *branch1,
1049                                         const char *branch2,
1050                                         struct merge_file_info *mfi)
1051{
1052        struct diff_filespec one, a, b;
1053
1054        one.path = a.path = b.path = (char *)path;
1055        oidcpy(&one.oid, o_oid);
1056        one.mode = o_mode;
1057        oidcpy(&a.oid, a_oid);
1058        a.mode = a_mode;
1059        oidcpy(&b.oid, b_oid);
1060        b.mode = b_mode;
1061        return merge_file_1(o, &one, &a, &b, branch1, branch2, mfi);
1062}
1063
1064static int handle_change_delete(struct merge_options *o,
1065                                 const char *path, const char *old_path,
1066                                 const struct object_id *o_oid, int o_mode,
1067                                 const struct object_id *changed_oid,
1068                                 int changed_mode,
1069                                 const char *change_branch,
1070                                 const char *delete_branch,
1071                                 const char *change, const char *change_past)
1072{
1073        char *alt_path = NULL;
1074        const char *update_path = path;
1075        int ret = 0;
1076
1077        if (dir_in_way(path, !o->call_depth, 0)) {
1078                update_path = alt_path = unique_path(o, path, change_branch);
1079        }
1080
1081        if (o->call_depth) {
1082                /*
1083                 * We cannot arbitrarily accept either a_sha or b_sha as
1084                 * correct; since there is no true "middle point" between
1085                 * them, simply reuse the base version for virtual merge base.
1086                 */
1087                ret = remove_file_from_cache(path);
1088                if (!ret)
1089                        ret = update_file(o, 0, o_oid, o_mode, update_path);
1090        } else {
1091                if (!alt_path) {
1092                        if (!old_path) {
1093                                output(o, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1094                                       "and %s in %s. Version %s of %s left in tree."),
1095                                       change, path, delete_branch, change_past,
1096                                       change_branch, change_branch, path);
1097                        } else {
1098                                output(o, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1099                                       "and %s to %s in %s. Version %s of %s left in tree."),
1100                                       change, old_path, delete_branch, change_past, path,
1101                                       change_branch, change_branch, path);
1102                        }
1103                } else {
1104                        if (!old_path) {
1105                                output(o, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1106                                       "and %s in %s. Version %s of %s left in tree at %s."),
1107                                       change, path, delete_branch, change_past,
1108                                       change_branch, change_branch, path, alt_path);
1109                        } else {
1110                                output(o, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1111                                       "and %s to %s in %s. Version %s of %s left in tree at %s."),
1112                                       change, old_path, delete_branch, change_past, path,
1113                                       change_branch, change_branch, path, alt_path);
1114                        }
1115                }
1116                /*
1117                 * No need to call update_file() on path when change_branch ==
1118                 * o->branch1 && !alt_path, since that would needlessly touch
1119                 * path.  We could call update_file_flags() with update_cache=0
1120                 * and update_wd=0, but that's a no-op.
1121                 */
1122                if (change_branch != o->branch1 || alt_path)
1123                        ret = update_file(o, 0, changed_oid, changed_mode, update_path);
1124        }
1125        free(alt_path);
1126
1127        return ret;
1128}
1129
1130static int conflict_rename_delete(struct merge_options *o,
1131                                   struct diff_filepair *pair,
1132                                   const char *rename_branch,
1133                                   const char *delete_branch)
1134{
1135        const struct diff_filespec *orig = pair->one;
1136        const struct diff_filespec *dest = pair->two;
1137
1138        if (handle_change_delete(o,
1139                                 o->call_depth ? orig->path : dest->path,
1140                                 o->call_depth ? NULL : orig->path,
1141                                 &orig->oid, orig->mode,
1142                                 &dest->oid, dest->mode,
1143                                 rename_branch, delete_branch,
1144                                 _("rename"), _("renamed")))
1145                return -1;
1146
1147        if (o->call_depth)
1148                return remove_file_from_cache(dest->path);
1149        else
1150                return update_stages(o, dest->path, NULL,
1151                                     rename_branch == o->branch1 ? dest : NULL,
1152                                     rename_branch == o->branch1 ? NULL : dest);
1153}
1154
1155static struct diff_filespec *filespec_from_entry(struct diff_filespec *target,
1156                                                 struct stage_data *entry,
1157                                                 int stage)
1158{
1159        struct object_id *oid = &entry->stages[stage].oid;
1160        unsigned mode = entry->stages[stage].mode;
1161        if (mode == 0 || is_null_oid(oid))
1162                return NULL;
1163        oidcpy(&target->oid, oid);
1164        target->mode = mode;
1165        return target;
1166}
1167
1168static int handle_file(struct merge_options *o,
1169                        struct diff_filespec *rename,
1170                        int stage,
1171                        struct rename_conflict_info *ci)
1172{
1173        char *dst_name = rename->path;
1174        struct stage_data *dst_entry;
1175        const char *cur_branch, *other_branch;
1176        struct diff_filespec other;
1177        struct diff_filespec *add;
1178        int ret;
1179
1180        if (stage == 2) {
1181                dst_entry = ci->dst_entry1;
1182                cur_branch = ci->branch1;
1183                other_branch = ci->branch2;
1184        } else {
1185                dst_entry = ci->dst_entry2;
1186                cur_branch = ci->branch2;
1187                other_branch = ci->branch1;
1188        }
1189
1190        add = filespec_from_entry(&other, dst_entry, stage ^ 1);
1191        if (add) {
1192                char *add_name = unique_path(o, rename->path, other_branch);
1193                if (update_file(o, 0, &add->oid, add->mode, add_name))
1194                        return -1;
1195
1196                remove_file(o, 0, rename->path, 0);
1197                dst_name = unique_path(o, rename->path, cur_branch);
1198        } else {
1199                if (dir_in_way(rename->path, !o->call_depth, 0)) {
1200                        dst_name = unique_path(o, rename->path, cur_branch);
1201                        output(o, 1, _("%s is a directory in %s adding as %s instead"),
1202                               rename->path, other_branch, dst_name);
1203                }
1204        }
1205        if ((ret = update_file(o, 0, &rename->oid, rename->mode, dst_name)))
1206                ; /* fall through, do allow dst_name to be released */
1207        else if (stage == 2)
1208                ret = update_stages(o, rename->path, NULL, rename, add);
1209        else
1210                ret = update_stages(o, rename->path, NULL, add, rename);
1211
1212        if (dst_name != rename->path)
1213                free(dst_name);
1214
1215        return ret;
1216}
1217
1218static int conflict_rename_rename_1to2(struct merge_options *o,
1219                                        struct rename_conflict_info *ci)
1220{
1221        /* One file was renamed in both branches, but to different names. */
1222        struct diff_filespec *one = ci->pair1->one;
1223        struct diff_filespec *a = ci->pair1->two;
1224        struct diff_filespec *b = ci->pair2->two;
1225
1226        output(o, 1, _("CONFLICT (rename/rename): "
1227               "Rename \"%s\"->\"%s\" in branch \"%s\" "
1228               "rename \"%s\"->\"%s\" in \"%s\"%s"),
1229               one->path, a->path, ci->branch1,
1230               one->path, b->path, ci->branch2,
1231               o->call_depth ? _(" (left unresolved)") : "");
1232        if (o->call_depth) {
1233                struct merge_file_info mfi;
1234                struct diff_filespec other;
1235                struct diff_filespec *add;
1236                if (merge_file_one(o, one->path,
1237                                 &one->oid, one->mode,
1238                                 &a->oid, a->mode,
1239                                 &b->oid, b->mode,
1240                                 ci->branch1, ci->branch2, &mfi))
1241                        return -1;
1242
1243                /*
1244                 * FIXME: For rename/add-source conflicts (if we could detect
1245                 * such), this is wrong.  We should instead find a unique
1246                 * pathname and then either rename the add-source file to that
1247                 * unique path, or use that unique path instead of src here.
1248                 */
1249                if (update_file(o, 0, &mfi.oid, mfi.mode, one->path))
1250                        return -1;
1251
1252                /*
1253                 * Above, we put the merged content at the merge-base's
1254                 * path.  Now we usually need to delete both a->path and
1255                 * b->path.  However, the rename on each side of the merge
1256                 * could also be involved in a rename/add conflict.  In
1257                 * such cases, we should keep the added file around,
1258                 * resolving the conflict at that path in its favor.
1259                 */
1260                add = filespec_from_entry(&other, ci->dst_entry1, 2 ^ 1);
1261                if (add) {
1262                        if (update_file(o, 0, &add->oid, add->mode, a->path))
1263                                return -1;
1264                }
1265                else
1266                        remove_file_from_cache(a->path);
1267                add = filespec_from_entry(&other, ci->dst_entry2, 3 ^ 1);
1268                if (add) {
1269                        if (update_file(o, 0, &add->oid, add->mode, b->path))
1270                                return -1;
1271                }
1272                else
1273                        remove_file_from_cache(b->path);
1274        } else if (handle_file(o, a, 2, ci) || handle_file(o, b, 3, ci))
1275                return -1;
1276
1277        return 0;
1278}
1279
1280static int conflict_rename_rename_2to1(struct merge_options *o,
1281                                        struct rename_conflict_info *ci)
1282{
1283        /* Two files, a & b, were renamed to the same thing, c. */
1284        struct diff_filespec *a = ci->pair1->one;
1285        struct diff_filespec *b = ci->pair2->one;
1286        struct diff_filespec *c1 = ci->pair1->two;
1287        struct diff_filespec *c2 = ci->pair2->two;
1288        char *path = c1->path; /* == c2->path */
1289        struct merge_file_info mfi_c1;
1290        struct merge_file_info mfi_c2;
1291        int ret;
1292
1293        output(o, 1, _("CONFLICT (rename/rename): "
1294               "Rename %s->%s in %s. "
1295               "Rename %s->%s in %s"),
1296               a->path, c1->path, ci->branch1,
1297               b->path, c2->path, ci->branch2);
1298
1299        remove_file(o, 1, a->path, o->call_depth || would_lose_untracked(a->path));
1300        remove_file(o, 1, b->path, o->call_depth || would_lose_untracked(b->path));
1301
1302        if (merge_file_special_markers(o, a, c1, &ci->ren1_other,
1303                                       o->branch1, c1->path,
1304                                       o->branch2, ci->ren1_other.path, &mfi_c1) ||
1305            merge_file_special_markers(o, b, &ci->ren2_other, c2,
1306                                       o->branch1, ci->ren2_other.path,
1307                                       o->branch2, c2->path, &mfi_c2))
1308                return -1;
1309
1310        if (o->call_depth) {
1311                /*
1312                 * If mfi_c1.clean && mfi_c2.clean, then it might make
1313                 * sense to do a two-way merge of those results.  But, I
1314                 * think in all cases, it makes sense to have the virtual
1315                 * merge base just undo the renames; they can be detected
1316                 * again later for the non-recursive merge.
1317                 */
1318                remove_file(o, 0, path, 0);
1319                ret = update_file(o, 0, &mfi_c1.oid, mfi_c1.mode, a->path);
1320                if (!ret)
1321                        ret = update_file(o, 0, &mfi_c2.oid, mfi_c2.mode,
1322                                          b->path);
1323        } else {
1324                char *new_path1 = unique_path(o, path, ci->branch1);
1325                char *new_path2 = unique_path(o, path, ci->branch2);
1326                output(o, 1, _("Renaming %s to %s and %s to %s instead"),
1327                       a->path, new_path1, b->path, new_path2);
1328                remove_file(o, 0, path, 0);
1329                ret = update_file(o, 0, &mfi_c1.oid, mfi_c1.mode, new_path1);
1330                if (!ret)
1331                        ret = update_file(o, 0, &mfi_c2.oid, mfi_c2.mode,
1332                                          new_path2);
1333                free(new_path2);
1334                free(new_path1);
1335        }
1336
1337        return ret;
1338}
1339
1340static int process_renames(struct merge_options *o,
1341                           struct string_list *a_renames,
1342                           struct string_list *b_renames)
1343{
1344        int clean_merge = 1, i, j;
1345        struct string_list a_by_dst = STRING_LIST_INIT_NODUP;
1346        struct string_list b_by_dst = STRING_LIST_INIT_NODUP;
1347        const struct rename *sre;
1348
1349        for (i = 0; i < a_renames->nr; i++) {
1350                sre = a_renames->items[i].util;
1351                string_list_insert(&a_by_dst, sre->pair->two->path)->util
1352                        = (void *)sre;
1353        }
1354        for (i = 0; i < b_renames->nr; i++) {
1355                sre = b_renames->items[i].util;
1356                string_list_insert(&b_by_dst, sre->pair->two->path)->util
1357                        = (void *)sre;
1358        }
1359
1360        for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {
1361                struct string_list *renames1, *renames2Dst;
1362                struct rename *ren1 = NULL, *ren2 = NULL;
1363                const char *branch1, *branch2;
1364                const char *ren1_src, *ren1_dst;
1365                struct string_list_item *lookup;
1366
1367                if (i >= a_renames->nr) {
1368                        ren2 = b_renames->items[j++].util;
1369                } else if (j >= b_renames->nr) {
1370                        ren1 = a_renames->items[i++].util;
1371                } else {
1372                        int compare = strcmp(a_renames->items[i].string,
1373                                             b_renames->items[j].string);
1374                        if (compare <= 0)
1375                                ren1 = a_renames->items[i++].util;
1376                        if (compare >= 0)
1377                                ren2 = b_renames->items[j++].util;
1378                }
1379
1380                /* TODO: refactor, so that 1/2 are not needed */
1381                if (ren1) {
1382                        renames1 = a_renames;
1383                        renames2Dst = &b_by_dst;
1384                        branch1 = o->branch1;
1385                        branch2 = o->branch2;
1386                } else {
1387                        renames1 = b_renames;
1388                        renames2Dst = &a_by_dst;
1389                        branch1 = o->branch2;
1390                        branch2 = o->branch1;
1391                        SWAP(ren2, ren1);
1392                }
1393
1394                if (ren1->processed)
1395                        continue;
1396                ren1->processed = 1;
1397                ren1->dst_entry->processed = 1;
1398                /* BUG: We should only mark src_entry as processed if we
1399                 * are not dealing with a rename + add-source case.
1400                 */
1401                ren1->src_entry->processed = 1;
1402
1403                ren1_src = ren1->pair->one->path;
1404                ren1_dst = ren1->pair->two->path;
1405
1406                if (ren2) {
1407                        /* One file renamed on both sides */
1408                        const char *ren2_src = ren2->pair->one->path;
1409                        const char *ren2_dst = ren2->pair->two->path;
1410                        enum rename_type rename_type;
1411                        if (strcmp(ren1_src, ren2_src) != 0)
1412                                die("BUG: ren1_src != ren2_src");
1413                        ren2->dst_entry->processed = 1;
1414                        ren2->processed = 1;
1415                        if (strcmp(ren1_dst, ren2_dst) != 0) {
1416                                rename_type = RENAME_ONE_FILE_TO_TWO;
1417                                clean_merge = 0;
1418                        } else {
1419                                rename_type = RENAME_ONE_FILE_TO_ONE;
1420                                /* BUG: We should only remove ren1_src in
1421                                 * the base stage (think of rename +
1422                                 * add-source cases).
1423                                 */
1424                                remove_file(o, 1, ren1_src, 1);
1425                                update_entry(ren1->dst_entry,
1426                                             ren1->pair->one,
1427                                             ren1->pair->two,
1428                                             ren2->pair->two);
1429                        }
1430                        setup_rename_conflict_info(rename_type,
1431                                                   ren1->pair,
1432                                                   ren2->pair,
1433                                                   branch1,
1434                                                   branch2,
1435                                                   ren1->dst_entry,
1436                                                   ren2->dst_entry,
1437                                                   o,
1438                                                   NULL,
1439                                                   NULL);
1440                } else if ((lookup = string_list_lookup(renames2Dst, ren1_dst))) {
1441                        /* Two different files renamed to the same thing */
1442                        char *ren2_dst;
1443                        ren2 = lookup->util;
1444                        ren2_dst = ren2->pair->two->path;
1445                        if (strcmp(ren1_dst, ren2_dst) != 0)
1446                                die("BUG: ren1_dst != ren2_dst");
1447
1448                        clean_merge = 0;
1449                        ren2->processed = 1;
1450                        /*
1451                         * BUG: We should only mark src_entry as processed
1452                         * if we are not dealing with a rename + add-source
1453                         * case.
1454                         */
1455                        ren2->src_entry->processed = 1;
1456
1457                        setup_rename_conflict_info(RENAME_TWO_FILES_TO_ONE,
1458                                                   ren1->pair,
1459                                                   ren2->pair,
1460                                                   branch1,
1461                                                   branch2,
1462                                                   ren1->dst_entry,
1463                                                   ren2->dst_entry,
1464                                                   o,
1465                                                   ren1->src_entry,
1466                                                   ren2->src_entry);
1467
1468                } else {
1469                        /* Renamed in 1, maybe changed in 2 */
1470                        /* we only use sha1 and mode of these */
1471                        struct diff_filespec src_other, dst_other;
1472                        int try_merge;
1473
1474                        /*
1475                         * unpack_trees loads entries from common-commit
1476                         * into stage 1, from head-commit into stage 2, and
1477                         * from merge-commit into stage 3.  We keep track
1478                         * of which side corresponds to the rename.
1479                         */
1480                        int renamed_stage = a_renames == renames1 ? 2 : 3;
1481                        int other_stage =   a_renames == renames1 ? 3 : 2;
1482
1483                        /* BUG: We should only remove ren1_src in the base
1484                         * stage and in other_stage (think of rename +
1485                         * add-source case).
1486                         */
1487                        remove_file(o, 1, ren1_src,
1488                                    renamed_stage == 2 || !was_tracked(ren1_src));
1489
1490                        oidcpy(&src_other.oid,
1491                               &ren1->src_entry->stages[other_stage].oid);
1492                        src_other.mode = ren1->src_entry->stages[other_stage].mode;
1493                        oidcpy(&dst_other.oid,
1494                               &ren1->dst_entry->stages[other_stage].oid);
1495                        dst_other.mode = ren1->dst_entry->stages[other_stage].mode;
1496                        try_merge = 0;
1497
1498                        if (oid_eq(&src_other.oid, &null_oid)) {
1499                                setup_rename_conflict_info(RENAME_DELETE,
1500                                                           ren1->pair,
1501                                                           NULL,
1502                                                           branch1,
1503                                                           branch2,
1504                                                           ren1->dst_entry,
1505                                                           NULL,
1506                                                           o,
1507                                                           NULL,
1508                                                           NULL);
1509                        } else if ((dst_other.mode == ren1->pair->two->mode) &&
1510                                   oid_eq(&dst_other.oid, &ren1->pair->two->oid)) {
1511                                /*
1512                                 * Added file on the other side identical to
1513                                 * the file being renamed: clean merge.
1514                                 * Also, there is no need to overwrite the
1515                                 * file already in the working copy, so call
1516                                 * update_file_flags() instead of
1517                                 * update_file().
1518                                 */
1519                                if (update_file_flags(o,
1520                                                      &ren1->pair->two->oid,
1521                                                      ren1->pair->two->mode,
1522                                                      ren1_dst,
1523                                                      1, /* update_cache */
1524                                                      0  /* update_wd    */))
1525                                        clean_merge = -1;
1526                        } else if (!oid_eq(&dst_other.oid, &null_oid)) {
1527                                clean_merge = 0;
1528                                try_merge = 1;
1529                                output(o, 1, _("CONFLICT (rename/add): Rename %s->%s in %s. "
1530                                       "%s added in %s"),
1531                                       ren1_src, ren1_dst, branch1,
1532                                       ren1_dst, branch2);
1533                                if (o->call_depth) {
1534                                        struct merge_file_info mfi;
1535                                        if (merge_file_one(o, ren1_dst, &null_oid, 0,
1536                                                           &ren1->pair->two->oid,
1537                                                           ren1->pair->two->mode,
1538                                                           &dst_other.oid,
1539                                                           dst_other.mode,
1540                                                           branch1, branch2, &mfi)) {
1541                                                clean_merge = -1;
1542                                                goto cleanup_and_return;
1543                                        }
1544                                        output(o, 1, _("Adding merged %s"), ren1_dst);
1545                                        if (update_file(o, 0, &mfi.oid,
1546                                                        mfi.mode, ren1_dst))
1547                                                clean_merge = -1;
1548                                        try_merge = 0;
1549                                } else {
1550                                        char *new_path = unique_path(o, ren1_dst, branch2);
1551                                        output(o, 1, _("Adding as %s instead"), new_path);
1552                                        if (update_file(o, 0, &dst_other.oid,
1553                                                        dst_other.mode, new_path))
1554                                                clean_merge = -1;
1555                                        free(new_path);
1556                                }
1557                        } else
1558                                try_merge = 1;
1559
1560                        if (clean_merge < 0)
1561                                goto cleanup_and_return;
1562                        if (try_merge) {
1563                                struct diff_filespec *one, *a, *b;
1564                                src_other.path = (char *)ren1_src;
1565
1566                                one = ren1->pair->one;
1567                                if (a_renames == renames1) {
1568                                        a = ren1->pair->two;
1569                                        b = &src_other;
1570                                } else {
1571                                        b = ren1->pair->two;
1572                                        a = &src_other;
1573                                }
1574                                update_entry(ren1->dst_entry, one, a, b);
1575                                setup_rename_conflict_info(RENAME_NORMAL,
1576                                                           ren1->pair,
1577                                                           NULL,
1578                                                           branch1,
1579                                                           NULL,
1580                                                           ren1->dst_entry,
1581                                                           NULL,
1582                                                           o,
1583                                                           NULL,
1584                                                           NULL);
1585                        }
1586                }
1587        }
1588cleanup_and_return:
1589        string_list_clear(&a_by_dst, 0);
1590        string_list_clear(&b_by_dst, 0);
1591
1592        return clean_merge;
1593}
1594
1595static struct object_id *stage_oid(const struct object_id *oid, unsigned mode)
1596{
1597        return (is_null_oid(oid) || mode == 0) ? NULL: (struct object_id *)oid;
1598}
1599
1600static int read_oid_strbuf(struct merge_options *o,
1601        const struct object_id *oid, struct strbuf *dst)
1602{
1603        void *buf;
1604        enum object_type type;
1605        unsigned long size;
1606        buf = read_sha1_file(oid->hash, &type, &size);
1607        if (!buf)
1608                return err(o, _("cannot read object %s"), oid_to_hex(oid));
1609        if (type != OBJ_BLOB) {
1610                free(buf);
1611                return err(o, _("object %s is not a blob"), oid_to_hex(oid));
1612        }
1613        strbuf_attach(dst, buf, size, size + 1);
1614        return 0;
1615}
1616
1617static int blob_unchanged(struct merge_options *opt,
1618                          const struct object_id *o_oid,
1619                          unsigned o_mode,
1620                          const struct object_id *a_oid,
1621                          unsigned a_mode,
1622                          int renormalize, const char *path)
1623{
1624        struct strbuf o = STRBUF_INIT;
1625        struct strbuf a = STRBUF_INIT;
1626        int ret = 0; /* assume changed for safety */
1627
1628        if (a_mode != o_mode)
1629                return 0;
1630        if (oid_eq(o_oid, a_oid))
1631                return 1;
1632        if (!renormalize)
1633                return 0;
1634
1635        assert(o_oid && a_oid);
1636        if (read_oid_strbuf(opt, o_oid, &o) || read_oid_strbuf(opt, a_oid, &a))
1637                goto error_return;
1638        /*
1639         * Note: binary | is used so that both renormalizations are
1640         * performed.  Comparison can be skipped if both files are
1641         * unchanged since their sha1s have already been compared.
1642         */
1643        if (renormalize_buffer(&the_index, path, o.buf, o.len, &o) |
1644            renormalize_buffer(&the_index, path, a.buf, a.len, &a))
1645                ret = (o.len == a.len && !memcmp(o.buf, a.buf, o.len));
1646
1647error_return:
1648        strbuf_release(&o);
1649        strbuf_release(&a);
1650        return ret;
1651}
1652
1653static int handle_modify_delete(struct merge_options *o,
1654                                 const char *path,
1655                                 struct object_id *o_oid, int o_mode,
1656                                 struct object_id *a_oid, int a_mode,
1657                                 struct object_id *b_oid, int b_mode)
1658{
1659        const char *modify_branch, *delete_branch;
1660        struct object_id *changed_oid;
1661        int changed_mode;
1662
1663        if (a_oid) {
1664                modify_branch = o->branch1;
1665                delete_branch = o->branch2;
1666                changed_oid = a_oid;
1667                changed_mode = a_mode;
1668        } else {
1669                modify_branch = o->branch2;
1670                delete_branch = o->branch1;
1671                changed_oid = b_oid;
1672                changed_mode = b_mode;
1673        }
1674
1675        return handle_change_delete(o,
1676                                    path, NULL,
1677                                    o_oid, o_mode,
1678                                    changed_oid, changed_mode,
1679                                    modify_branch, delete_branch,
1680                                    _("modify"), _("modified"));
1681}
1682
1683static int merge_content(struct merge_options *o,
1684                         const char *path,
1685                         struct object_id *o_oid, int o_mode,
1686                         struct object_id *a_oid, int a_mode,
1687                         struct object_id *b_oid, int b_mode,
1688                         struct rename_conflict_info *rename_conflict_info)
1689{
1690        const char *reason = _("content");
1691        const char *path1 = NULL, *path2 = NULL;
1692        struct merge_file_info mfi;
1693        struct diff_filespec one, a, b;
1694        unsigned df_conflict_remains = 0;
1695
1696        if (!o_oid) {
1697                reason = _("add/add");
1698                o_oid = (struct object_id *)&null_oid;
1699        }
1700        one.path = a.path = b.path = (char *)path;
1701        oidcpy(&one.oid, o_oid);
1702        one.mode = o_mode;
1703        oidcpy(&a.oid, a_oid);
1704        a.mode = a_mode;
1705        oidcpy(&b.oid, b_oid);
1706        b.mode = b_mode;
1707
1708        if (rename_conflict_info) {
1709                struct diff_filepair *pair1 = rename_conflict_info->pair1;
1710
1711                path1 = (o->branch1 == rename_conflict_info->branch1) ?
1712                        pair1->two->path : pair1->one->path;
1713                /* If rename_conflict_info->pair2 != NULL, we are in
1714                 * RENAME_ONE_FILE_TO_ONE case.  Otherwise, we have a
1715                 * normal rename.
1716                 */
1717                path2 = (rename_conflict_info->pair2 ||
1718                         o->branch2 == rename_conflict_info->branch1) ?
1719                        pair1->two->path : pair1->one->path;
1720
1721                if (dir_in_way(path, !o->call_depth,
1722                               S_ISGITLINK(pair1->two->mode)))
1723                        df_conflict_remains = 1;
1724        }
1725        if (merge_file_special_markers(o, &one, &a, &b,
1726                                       o->branch1, path1,
1727                                       o->branch2, path2, &mfi))
1728                return -1;
1729
1730        if (mfi.clean && !df_conflict_remains &&
1731            oid_eq(&mfi.oid, a_oid) && mfi.mode == a_mode) {
1732                int path_renamed_outside_HEAD;
1733                output(o, 3, _("Skipped %s (merged same as existing)"), path);
1734                /*
1735                 * The content merge resulted in the same file contents we
1736                 * already had.  We can return early if those file contents
1737                 * are recorded at the correct path (which may not be true
1738                 * if the merge involves a rename).
1739                 */
1740                path_renamed_outside_HEAD = !path2 || !strcmp(path, path2);
1741                if (!path_renamed_outside_HEAD) {
1742                        add_cacheinfo(o, mfi.mode, &mfi.oid, path,
1743                                      0, (!o->call_depth), 0);
1744                        return mfi.clean;
1745                }
1746        } else
1747                output(o, 2, _("Auto-merging %s"), path);
1748
1749        if (!mfi.clean) {
1750                if (S_ISGITLINK(mfi.mode))
1751                        reason = _("submodule");
1752                output(o, 1, _("CONFLICT (%s): Merge conflict in %s"),
1753                                reason, path);
1754                if (rename_conflict_info && !df_conflict_remains)
1755                        if (update_stages(o, path, &one, &a, &b))
1756                                return -1;
1757        }
1758
1759        if (df_conflict_remains) {
1760                char *new_path;
1761                if (o->call_depth) {
1762                        remove_file_from_cache(path);
1763                } else {
1764                        if (!mfi.clean) {
1765                                if (update_stages(o, path, &one, &a, &b))
1766                                        return -1;
1767                        } else {
1768                                int file_from_stage2 = was_tracked(path);
1769                                struct diff_filespec merged;
1770                                oidcpy(&merged.oid, &mfi.oid);
1771                                merged.mode = mfi.mode;
1772
1773                                if (update_stages(o, path, NULL,
1774                                                  file_from_stage2 ? &merged : NULL,
1775                                                  file_from_stage2 ? NULL : &merged))
1776                                        return -1;
1777                        }
1778
1779                }
1780                new_path = unique_path(o, path, rename_conflict_info->branch1);
1781                output(o, 1, _("Adding as %s instead"), new_path);
1782                if (update_file(o, 0, &mfi.oid, mfi.mode, new_path)) {
1783                        free(new_path);
1784                        return -1;
1785                }
1786                free(new_path);
1787                mfi.clean = 0;
1788        } else if (update_file(o, mfi.clean, &mfi.oid, mfi.mode, path))
1789                return -1;
1790        return mfi.clean;
1791}
1792
1793/* Per entry merge function */
1794static int process_entry(struct merge_options *o,
1795                         const char *path, struct stage_data *entry)
1796{
1797        int clean_merge = 1;
1798        int normalize = o->renormalize;
1799        unsigned o_mode = entry->stages[1].mode;
1800        unsigned a_mode = entry->stages[2].mode;
1801        unsigned b_mode = entry->stages[3].mode;
1802        struct object_id *o_oid = stage_oid(&entry->stages[1].oid, o_mode);
1803        struct object_id *a_oid = stage_oid(&entry->stages[2].oid, a_mode);
1804        struct object_id *b_oid = stage_oid(&entry->stages[3].oid, b_mode);
1805
1806        entry->processed = 1;
1807        if (entry->rename_conflict_info) {
1808                struct rename_conflict_info *conflict_info = entry->rename_conflict_info;
1809                switch (conflict_info->rename_type) {
1810                case RENAME_NORMAL:
1811                case RENAME_ONE_FILE_TO_ONE:
1812                        clean_merge = merge_content(o, path,
1813                                                    o_oid, o_mode, a_oid, a_mode, b_oid, b_mode,
1814                                                    conflict_info);
1815                        break;
1816                case RENAME_DELETE:
1817                        clean_merge = 0;
1818                        if (conflict_rename_delete(o,
1819                                                   conflict_info->pair1,
1820                                                   conflict_info->branch1,
1821                                                   conflict_info->branch2))
1822                                clean_merge = -1;
1823                        break;
1824                case RENAME_ONE_FILE_TO_TWO:
1825                        clean_merge = 0;
1826                        if (conflict_rename_rename_1to2(o, conflict_info))
1827                                clean_merge = -1;
1828                        break;
1829                case RENAME_TWO_FILES_TO_ONE:
1830                        clean_merge = 0;
1831                        if (conflict_rename_rename_2to1(o, conflict_info))
1832                                clean_merge = -1;
1833                        break;
1834                default:
1835                        entry->processed = 0;
1836                        break;
1837                }
1838        } else if (o_oid && (!a_oid || !b_oid)) {
1839                /* Case A: Deleted in one */
1840                if ((!a_oid && !b_oid) ||
1841                    (!b_oid && blob_unchanged(o, o_oid, o_mode, a_oid, a_mode, normalize, path)) ||
1842                    (!a_oid && blob_unchanged(o, o_oid, o_mode, b_oid, b_mode, normalize, path))) {
1843                        /* Deleted in both or deleted in one and
1844                         * unchanged in the other */
1845                        if (a_oid)
1846                                output(o, 2, _("Removing %s"), path);
1847                        /* do not touch working file if it did not exist */
1848                        remove_file(o, 1, path, !a_oid);
1849                } else {
1850                        /* Modify/delete; deleted side may have put a directory in the way */
1851                        clean_merge = 0;
1852                        if (handle_modify_delete(o, path, o_oid, o_mode,
1853                                                 a_oid, a_mode, b_oid, b_mode))
1854                                clean_merge = -1;
1855                }
1856        } else if ((!o_oid && a_oid && !b_oid) ||
1857                   (!o_oid && !a_oid && b_oid)) {
1858                /* Case B: Added in one. */
1859                /* [nothing|directory] -> ([nothing|directory], file) */
1860
1861                const char *add_branch;
1862                const char *other_branch;
1863                unsigned mode;
1864                const struct object_id *oid;
1865                const char *conf;
1866
1867                if (a_oid) {
1868                        add_branch = o->branch1;
1869                        other_branch = o->branch2;
1870                        mode = a_mode;
1871                        oid = a_oid;
1872                        conf = _("file/directory");
1873                } else {
1874                        add_branch = o->branch2;
1875                        other_branch = o->branch1;
1876                        mode = b_mode;
1877                        oid = b_oid;
1878                        conf = _("directory/file");
1879                }
1880                if (dir_in_way(path, !o->call_depth,
1881                               S_ISGITLINK(a_mode))) {
1882                        char *new_path = unique_path(o, path, add_branch);
1883                        clean_merge = 0;
1884                        output(o, 1, _("CONFLICT (%s): There is a directory with name %s in %s. "
1885                               "Adding %s as %s"),
1886                               conf, path, other_branch, path, new_path);
1887                        if (update_file(o, 0, oid, mode, new_path))
1888                                clean_merge = -1;
1889                        else if (o->call_depth)
1890                                remove_file_from_cache(path);
1891                        free(new_path);
1892                } else {
1893                        output(o, 2, _("Adding %s"), path);
1894                        /* do not overwrite file if already present */
1895                        if (update_file_flags(o, oid, mode, path, 1, !a_oid))
1896                                clean_merge = -1;
1897                }
1898        } else if (a_oid && b_oid) {
1899                /* Case C: Added in both (check for same permissions) and */
1900                /* case D: Modified in both, but differently. */
1901                clean_merge = merge_content(o, path,
1902                                            o_oid, o_mode, a_oid, a_mode, b_oid, b_mode,
1903                                            NULL);
1904        } else if (!o_oid && !a_oid && !b_oid) {
1905                /*
1906                 * this entry was deleted altogether. a_mode == 0 means
1907                 * we had that path and want to actively remove it.
1908                 */
1909                remove_file(o, 1, path, !a_mode);
1910        } else
1911                die("BUG: fatal merge failure, shouldn't happen.");
1912
1913        return clean_merge;
1914}
1915
1916int merge_trees(struct merge_options *o,
1917                struct tree *head,
1918                struct tree *merge,
1919                struct tree *common,
1920                struct tree **result)
1921{
1922        int code, clean;
1923
1924        if (o->subtree_shift) {
1925                merge = shift_tree_object(head, merge, o->subtree_shift);
1926                common = shift_tree_object(head, common, o->subtree_shift);
1927        }
1928
1929        if (oid_eq(&common->object.oid, &merge->object.oid)) {
1930                output(o, 0, _("Already up-to-date!"));
1931                *result = head;
1932                return 1;
1933        }
1934
1935        code = git_merge_trees(o->call_depth, common, head, merge);
1936
1937        if (code != 0) {
1938                if (show(o, 4) || o->call_depth)
1939                        err(o, _("merging of trees %s and %s failed"),
1940                            oid_to_hex(&head->object.oid),
1941                            oid_to_hex(&merge->object.oid));
1942                return -1;
1943        }
1944
1945        if (unmerged_cache()) {
1946                struct string_list *entries, *re_head, *re_merge;
1947                int i;
1948                string_list_clear(&o->current_file_set, 1);
1949                string_list_clear(&o->current_directory_set, 1);
1950                get_files_dirs(o, head);
1951                get_files_dirs(o, merge);
1952
1953                entries = get_unmerged();
1954                record_df_conflict_files(o, entries);
1955                re_head  = get_renames(o, head, common, head, merge, entries);
1956                re_merge = get_renames(o, merge, common, head, merge, entries);
1957                clean = process_renames(o, re_head, re_merge);
1958                if (clean < 0)
1959                        return clean;
1960                for (i = entries->nr-1; 0 <= i; i--) {
1961                        const char *path = entries->items[i].string;
1962                        struct stage_data *e = entries->items[i].util;
1963                        if (!e->processed) {
1964                                int ret = process_entry(o, path, e);
1965                                if (!ret)
1966                                        clean = 0;
1967                                else if (ret < 0)
1968                                        return ret;
1969                        }
1970                }
1971                for (i = 0; i < entries->nr; i++) {
1972                        struct stage_data *e = entries->items[i].util;
1973                        if (!e->processed)
1974                                die("BUG: unprocessed path??? %s",
1975                                    entries->items[i].string);
1976                }
1977
1978                string_list_clear(re_merge, 0);
1979                string_list_clear(re_head, 0);
1980                string_list_clear(entries, 1);
1981
1982                free(re_merge);
1983                free(re_head);
1984                free(entries);
1985        }
1986        else
1987                clean = 1;
1988
1989        if (o->call_depth && !(*result = write_tree_from_memory(o)))
1990                return -1;
1991
1992        return clean;
1993}
1994
1995static struct commit_list *reverse_commit_list(struct commit_list *list)
1996{
1997        struct commit_list *next = NULL, *current, *backup;
1998        for (current = list; current; current = backup) {
1999                backup = current->next;
2000                current->next = next;
2001                next = current;
2002        }
2003        return next;
2004}
2005
2006/*
2007 * Merge the commits h1 and h2, return the resulting virtual
2008 * commit object and a flag indicating the cleanness of the merge.
2009 */
2010int merge_recursive(struct merge_options *o,
2011                    struct commit *h1,
2012                    struct commit *h2,
2013                    struct commit_list *ca,
2014                    struct commit **result)
2015{
2016        struct commit_list *iter;
2017        struct commit *merged_common_ancestors;
2018        struct tree *mrtree = mrtree;
2019        int clean;
2020
2021        if (show(o, 4)) {
2022                output(o, 4, _("Merging:"));
2023                output_commit_title(o, h1);
2024                output_commit_title(o, h2);
2025        }
2026
2027        if (!ca) {
2028                ca = get_merge_bases(h1, h2);
2029                ca = reverse_commit_list(ca);
2030        }
2031
2032        if (show(o, 5)) {
2033                unsigned cnt = commit_list_count(ca);
2034
2035                output(o, 5, Q_("found %u common ancestor:",
2036                                "found %u common ancestors:", cnt), cnt);
2037                for (iter = ca; iter; iter = iter->next)
2038                        output_commit_title(o, iter->item);
2039        }
2040
2041        merged_common_ancestors = pop_commit(&ca);
2042        if (merged_common_ancestors == NULL) {
2043                /* if there is no common ancestor, use an empty tree */
2044                struct tree *tree;
2045
2046                tree = lookup_tree(&empty_tree_oid);
2047                merged_common_ancestors = make_virtual_commit(tree, "ancestor");
2048        }
2049
2050        for (iter = ca; iter; iter = iter->next) {
2051                const char *saved_b1, *saved_b2;
2052                o->call_depth++;
2053                /*
2054                 * When the merge fails, the result contains files
2055                 * with conflict markers. The cleanness flag is
2056                 * ignored (unless indicating an error), it was never
2057                 * actually used, as result of merge_trees has always
2058                 * overwritten it: the committed "conflicts" were
2059                 * already resolved.
2060                 */
2061                discard_cache();
2062                saved_b1 = o->branch1;
2063                saved_b2 = o->branch2;
2064                o->branch1 = "Temporary merge branch 1";
2065                o->branch2 = "Temporary merge branch 2";
2066                if (merge_recursive(o, merged_common_ancestors, iter->item,
2067                                    NULL, &merged_common_ancestors) < 0)
2068                        return -1;
2069                o->branch1 = saved_b1;
2070                o->branch2 = saved_b2;
2071                o->call_depth--;
2072
2073                if (!merged_common_ancestors)
2074                        return err(o, _("merge returned no commit"));
2075        }
2076
2077        discard_cache();
2078        if (!o->call_depth)
2079                read_cache();
2080
2081        o->ancestor = "merged common ancestors";
2082        clean = merge_trees(o, h1->tree, h2->tree, merged_common_ancestors->tree,
2083                            &mrtree);
2084        if (clean < 0) {
2085                flush_output(o);
2086                return clean;
2087        }
2088
2089        if (o->call_depth) {
2090                *result = make_virtual_commit(mrtree, "merged tree");
2091                commit_list_insert(h1, &(*result)->parents);
2092                commit_list_insert(h2, &(*result)->parents->next);
2093        }
2094        flush_output(o);
2095        if (!o->call_depth && o->buffer_output < 2)
2096                strbuf_release(&o->obuf);
2097        if (show(o, 2))
2098                diff_warn_rename_limit("merge.renamelimit",
2099                                       o->needed_rename_limit, 0);
2100        return clean;
2101}
2102
2103static struct commit *get_ref(const struct object_id *oid, const char *name)
2104{
2105        struct object *object;
2106
2107        object = deref_tag(parse_object(oid), name, strlen(name));
2108        if (!object)
2109                return NULL;
2110        if (object->type == OBJ_TREE)
2111                return make_virtual_commit((struct tree*)object, name);
2112        if (object->type != OBJ_COMMIT)
2113                return NULL;
2114        if (parse_commit((struct commit *)object))
2115                return NULL;
2116        return (struct commit *)object;
2117}
2118
2119int merge_recursive_generic(struct merge_options *o,
2120                            const struct object_id *head,
2121                            const struct object_id *merge,
2122                            int num_base_list,
2123                            const struct object_id **base_list,
2124                            struct commit **result)
2125{
2126        int clean;
2127        struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));
2128        struct commit *head_commit = get_ref(head, o->branch1);
2129        struct commit *next_commit = get_ref(merge, o->branch2);
2130        struct commit_list *ca = NULL;
2131
2132        if (base_list) {
2133                int i;
2134                for (i = 0; i < num_base_list; ++i) {
2135                        struct commit *base;
2136                        if (!(base = get_ref(base_list[i], oid_to_hex(base_list[i]))))
2137                                return err(o, _("Could not parse object '%s'"),
2138                                        oid_to_hex(base_list[i]));
2139                        commit_list_insert(base, &ca);
2140                }
2141        }
2142
2143        hold_locked_index(lock, LOCK_DIE_ON_ERROR);
2144        clean = merge_recursive(o, head_commit, next_commit, ca,
2145                        result);
2146        if (clean < 0)
2147                return clean;
2148
2149        if (active_cache_changed &&
2150            write_locked_index(&the_index, lock, COMMIT_LOCK))
2151                return err(o, _("Unable to write index."));
2152
2153        return clean ? 0 : 1;
2154}
2155
2156static void merge_recursive_config(struct merge_options *o)
2157{
2158        git_config_get_int("merge.verbosity", &o->verbosity);
2159        git_config_get_int("diff.renamelimit", &o->diff_rename_limit);
2160        git_config_get_int("merge.renamelimit", &o->merge_rename_limit);
2161        git_config(git_xmerge_config, NULL);
2162}
2163
2164void init_merge_options(struct merge_options *o)
2165{
2166        memset(o, 0, sizeof(struct merge_options));
2167        o->verbosity = 2;
2168        o->buffer_output = 1;
2169        o->diff_rename_limit = -1;
2170        o->merge_rename_limit = -1;
2171        o->renormalize = 0;
2172        o->detect_rename = 1;
2173        merge_recursive_config(o);
2174        if (getenv("GIT_MERGE_VERBOSITY"))
2175                o->verbosity =
2176                        strtol(getenv("GIT_MERGE_VERBOSITY"), NULL, 10);
2177        if (o->verbosity >= 5)
2178                o->buffer_output = 0;
2179        strbuf_init(&o->obuf, 0);
2180        string_list_init(&o->current_file_set, 1);
2181        string_list_init(&o->current_directory_set, 1);
2182        string_list_init(&o->df_conflict_file_set, 1);
2183}
2184
2185int parse_merge_opt(struct merge_options *o, const char *s)
2186{
2187        const char *arg;
2188
2189        if (!s || !*s)
2190                return -1;
2191        if (!strcmp(s, "ours"))
2192                o->recursive_variant = MERGE_RECURSIVE_OURS;
2193        else if (!strcmp(s, "theirs"))
2194                o->recursive_variant = MERGE_RECURSIVE_THEIRS;
2195        else if (!strcmp(s, "subtree"))
2196                o->subtree_shift = "";
2197        else if (skip_prefix(s, "subtree=", &arg))
2198                o->subtree_shift = arg;
2199        else if (!strcmp(s, "patience"))
2200                o->xdl_opts = DIFF_WITH_ALG(o, PATIENCE_DIFF);
2201        else if (!strcmp(s, "histogram"))
2202                o->xdl_opts = DIFF_WITH_ALG(o, HISTOGRAM_DIFF);
2203        else if (skip_prefix(s, "diff-algorithm=", &arg)) {
2204                long value = parse_algorithm_value(arg);
2205                if (value < 0)
2206                        return -1;
2207                /* clear out previous settings */
2208                DIFF_XDL_CLR(o, NEED_MINIMAL);
2209                o->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
2210                o->xdl_opts |= value;
2211        }
2212        else if (!strcmp(s, "ignore-space-change"))
2213                DIFF_XDL_SET(o, IGNORE_WHITESPACE_CHANGE);
2214        else if (!strcmp(s, "ignore-all-space"))
2215                DIFF_XDL_SET(o, IGNORE_WHITESPACE);
2216        else if (!strcmp(s, "ignore-space-at-eol"))
2217                DIFF_XDL_SET(o, IGNORE_WHITESPACE_AT_EOL);
2218        else if (!strcmp(s, "renormalize"))
2219                o->renormalize = 1;
2220        else if (!strcmp(s, "no-renormalize"))
2221                o->renormalize = 0;
2222        else if (!strcmp(s, "no-renames"))
2223                o->detect_rename = 0;
2224        else if (!strcmp(s, "find-renames")) {
2225                o->detect_rename = 1;
2226                o->rename_score = 0;
2227        }
2228        else if (skip_prefix(s, "find-renames=", &arg) ||
2229                 skip_prefix(s, "rename-threshold=", &arg)) {
2230                if ((o->rename_score = parse_rename_score(&arg)) == -1 || *arg != 0)
2231                        return -1;
2232                o->detect_rename = 1;
2233        }
2234        else
2235                return -1;
2236        return 0;
2237}