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