merge-recursive.con commit Merge branch 'sg/clean-nested-repo-with-ignored' (026428c)
   1/*
   2 * Recursive Merge algorithm stolen from git-merge-recursive.py by
   3 * Fredrik Kuivinen.
   4 * The thieves were Alex Riesen and Johannes Schindelin, in June/July 2006
   5 */
   6#include "cache.h"
   7#include "config.h"
   8#include "advice.h"
   9#include "lockfile.h"
  10#include "cache-tree.h"
  11#include "object-store.h"
  12#include "repository.h"
  13#include "commit.h"
  14#include "blob.h"
  15#include "builtin.h"
  16#include "tree-walk.h"
  17#include "diff.h"
  18#include "diffcore.h"
  19#include "tag.h"
  20#include "alloc.h"
  21#include "unpack-trees.h"
  22#include "string-list.h"
  23#include "xdiff-interface.h"
  24#include "ll-merge.h"
  25#include "attr.h"
  26#include "merge-recursive.h"
  27#include "dir.h"
  28#include "submodule.h"
  29#include "revision.h"
  30#include "commit-reach.h"
  31
  32struct path_hashmap_entry {
  33        struct hashmap_entry e;
  34        char path[FLEX_ARRAY];
  35};
  36
  37static int path_hashmap_cmp(const void *cmp_data,
  38                            const void *entry,
  39                            const void *entry_or_key,
  40                            const void *keydata)
  41{
  42        const struct path_hashmap_entry *a = entry;
  43        const struct path_hashmap_entry *b = entry_or_key;
  44        const char *key = keydata;
  45
  46        if (ignore_case)
  47                return strcasecmp(a->path, key ? key : b->path);
  48        else
  49                return strcmp(a->path, key ? key : b->path);
  50}
  51
  52static unsigned int path_hash(const char *path)
  53{
  54        return ignore_case ? strihash(path) : strhash(path);
  55}
  56
  57static struct dir_rename_entry *dir_rename_find_entry(struct hashmap *hashmap,
  58                                                      char *dir)
  59{
  60        struct dir_rename_entry key;
  61
  62        if (dir == NULL)
  63                return NULL;
  64        hashmap_entry_init(&key, strhash(dir));
  65        key.dir = dir;
  66        return hashmap_get(hashmap, &key, NULL);
  67}
  68
  69static int dir_rename_cmp(const void *unused_cmp_data,
  70                          const void *entry,
  71                          const void *entry_or_key,
  72                          const void *unused_keydata)
  73{
  74        const struct dir_rename_entry *e1 = entry;
  75        const struct dir_rename_entry *e2 = entry_or_key;
  76
  77        return strcmp(e1->dir, e2->dir);
  78}
  79
  80static void dir_rename_init(struct hashmap *map)
  81{
  82        hashmap_init(map, dir_rename_cmp, NULL, 0);
  83}
  84
  85static void dir_rename_entry_init(struct dir_rename_entry *entry,
  86                                  char *directory)
  87{
  88        hashmap_entry_init(entry, strhash(directory));
  89        entry->dir = directory;
  90        entry->non_unique_new_dir = 0;
  91        strbuf_init(&entry->new_dir, 0);
  92        string_list_init(&entry->possible_new_dirs, 0);
  93}
  94
  95static struct collision_entry *collision_find_entry(struct hashmap *hashmap,
  96                                                    char *target_file)
  97{
  98        struct collision_entry key;
  99
 100        hashmap_entry_init(&key, strhash(target_file));
 101        key.target_file = target_file;
 102        return hashmap_get(hashmap, &key, NULL);
 103}
 104
 105static int collision_cmp(void *unused_cmp_data,
 106                         const struct collision_entry *e1,
 107                         const struct collision_entry *e2,
 108                         const void *unused_keydata)
 109{
 110        return strcmp(e1->target_file, e2->target_file);
 111}
 112
 113static void collision_init(struct hashmap *map)
 114{
 115        hashmap_init(map, (hashmap_cmp_fn) collision_cmp, NULL, 0);
 116}
 117
 118static void flush_output(struct merge_options *opt)
 119{
 120        if (opt->buffer_output < 2 && opt->obuf.len) {
 121                fputs(opt->obuf.buf, stdout);
 122                strbuf_reset(&opt->obuf);
 123        }
 124}
 125
 126static int err(struct merge_options *opt, const char *err, ...)
 127{
 128        va_list params;
 129
 130        if (opt->buffer_output < 2)
 131                flush_output(opt);
 132        else {
 133                strbuf_complete(&opt->obuf, '\n');
 134                strbuf_addstr(&opt->obuf, "error: ");
 135        }
 136        va_start(params, err);
 137        strbuf_vaddf(&opt->obuf, err, params);
 138        va_end(params);
 139        if (opt->buffer_output > 1)
 140                strbuf_addch(&opt->obuf, '\n');
 141        else {
 142                error("%s", opt->obuf.buf);
 143                strbuf_reset(&opt->obuf);
 144        }
 145
 146        return -1;
 147}
 148
 149static struct tree *shift_tree_object(struct repository *repo,
 150                                      struct tree *one, struct tree *two,
 151                                      const char *subtree_shift)
 152{
 153        struct object_id shifted;
 154
 155        if (!*subtree_shift) {
 156                shift_tree(repo, &one->object.oid, &two->object.oid, &shifted, 0);
 157        } else {
 158                shift_tree_by(repo, &one->object.oid, &two->object.oid, &shifted,
 159                              subtree_shift);
 160        }
 161        if (oideq(&two->object.oid, &shifted))
 162                return two;
 163        return lookup_tree(repo, &shifted);
 164}
 165
 166static inline void set_commit_tree(struct commit *c, struct tree *t)
 167{
 168        c->maybe_tree = t;
 169}
 170
 171static struct commit *make_virtual_commit(struct repository *repo,
 172                                          struct tree *tree,
 173                                          const char *comment)
 174{
 175        struct commit *commit = alloc_commit_node(repo);
 176
 177        set_merge_remote_desc(commit, comment, (struct object *)commit);
 178        set_commit_tree(commit, tree);
 179        commit->object.parsed = 1;
 180        return commit;
 181}
 182
 183/*
 184 * Since we use get_tree_entry(), which does not put the read object into
 185 * the object pool, we cannot rely on a == b.
 186 */
 187static int oid_eq(const struct object_id *a, const struct object_id *b)
 188{
 189        if (!a && !b)
 190                return 2;
 191        return a && b && oideq(a, b);
 192}
 193
 194enum rename_type {
 195        RENAME_NORMAL = 0,
 196        RENAME_VIA_DIR,
 197        RENAME_ADD,
 198        RENAME_DELETE,
 199        RENAME_ONE_FILE_TO_ONE,
 200        RENAME_ONE_FILE_TO_TWO,
 201        RENAME_TWO_FILES_TO_ONE
 202};
 203
 204/*
 205 * Since we want to write the index eventually, we cannot reuse the index
 206 * for these (temporary) data.
 207 */
 208struct stage_data {
 209        struct diff_filespec stages[4]; /* mostly for oid & mode; maybe path */
 210        struct rename_conflict_info *rename_conflict_info;
 211        unsigned processed:1;
 212};
 213
 214struct rename {
 215        unsigned processed:1;
 216        struct diff_filepair *pair;
 217        const char *branch; /* branch that the rename occurred on */
 218        /*
 219         * If directory rename detection affected this rename, what was its
 220         * original type ('A' or 'R') and it's original destination before
 221         * the directory rename (otherwise, '\0' and NULL for these two vars).
 222         */
 223        char dir_rename_original_type;
 224        char *dir_rename_original_dest;
 225        /*
 226         * Purpose of src_entry and dst_entry:
 227         *
 228         * If 'before' is renamed to 'after' then src_entry will contain
 229         * the versions of 'before' from the merge_base, HEAD, and MERGE in
 230         * stages 1, 2, and 3; dst_entry will contain the respective
 231         * versions of 'after' in corresponding locations.  Thus, we have a
 232         * total of six modes and oids, though some will be null.  (Stage 0
 233         * is ignored; we're interested in handling conflicts.)
 234         *
 235         * Since we don't turn on break-rewrites by default, neither
 236         * src_entry nor dst_entry can have all three of their stages have
 237         * non-null oids, meaning at most four of the six will be non-null.
 238         * Also, since this is a rename, both src_entry and dst_entry will
 239         * have at least one non-null oid, meaning at least two will be
 240         * non-null.  Of the six oids, a typical rename will have three be
 241         * non-null.  Only two implies a rename/delete, and four implies a
 242         * rename/add.
 243         */
 244        struct stage_data *src_entry;
 245        struct stage_data *dst_entry;
 246};
 247
 248struct rename_conflict_info {
 249        enum rename_type rename_type;
 250        struct rename *ren1;
 251        struct rename *ren2;
 252};
 253
 254static inline void setup_rename_conflict_info(enum rename_type rename_type,
 255                                              struct merge_options *opt,
 256                                              struct rename *ren1,
 257                                              struct rename *ren2)
 258{
 259        struct rename_conflict_info *ci;
 260
 261        /*
 262         * When we have two renames involved, it's easiest to get the
 263         * correct things into stage 2 and 3, and to make sure that the
 264         * content merge puts HEAD before the other branch if we just
 265         * ensure that branch1 == opt->branch1.  So, simply flip arguments
 266         * around if we don't have that.
 267         */
 268        if (ren2 && ren1->branch != opt->branch1) {
 269                setup_rename_conflict_info(rename_type, opt, ren2, ren1);
 270                return;
 271        }
 272
 273        ci = xcalloc(1, sizeof(struct rename_conflict_info));
 274        ci->rename_type = rename_type;
 275        ci->ren1 = ren1;
 276        ci->ren2 = ren2;
 277
 278        ci->ren1->dst_entry->processed = 0;
 279        ci->ren1->dst_entry->rename_conflict_info = ci;
 280        if (ren2) {
 281                ci->ren2->dst_entry->rename_conflict_info = ci;
 282        }
 283}
 284
 285static int show(struct merge_options *opt, int v)
 286{
 287        return (!opt->call_depth && opt->verbosity >= v) || opt->verbosity >= 5;
 288}
 289
 290__attribute__((format (printf, 3, 4)))
 291static void output(struct merge_options *opt, int v, const char *fmt, ...)
 292{
 293        va_list ap;
 294
 295        if (!show(opt, v))
 296                return;
 297
 298        strbuf_addchars(&opt->obuf, ' ', opt->call_depth * 2);
 299
 300        va_start(ap, fmt);
 301        strbuf_vaddf(&opt->obuf, fmt, ap);
 302        va_end(ap);
 303
 304        strbuf_addch(&opt->obuf, '\n');
 305        if (!opt->buffer_output)
 306                flush_output(opt);
 307}
 308
 309static void output_commit_title(struct merge_options *opt, struct commit *commit)
 310{
 311        struct merge_remote_desc *desc;
 312
 313        strbuf_addchars(&opt->obuf, ' ', opt->call_depth * 2);
 314        desc = merge_remote_util(commit);
 315        if (desc)
 316                strbuf_addf(&opt->obuf, "virtual %s\n", desc->name);
 317        else {
 318                strbuf_add_unique_abbrev(&opt->obuf, &commit->object.oid,
 319                                         DEFAULT_ABBREV);
 320                strbuf_addch(&opt->obuf, ' ');
 321                if (parse_commit(commit) != 0)
 322                        strbuf_addstr(&opt->obuf, _("(bad commit)\n"));
 323                else {
 324                        const char *title;
 325                        const char *msg = get_commit_buffer(commit, NULL);
 326                        int len = find_commit_subject(msg, &title);
 327                        if (len)
 328                                strbuf_addf(&opt->obuf, "%.*s\n", len, title);
 329                        unuse_commit_buffer(commit, msg);
 330                }
 331        }
 332        flush_output(opt);
 333}
 334
 335static int add_cacheinfo(struct merge_options *opt,
 336                         const struct diff_filespec *blob,
 337                         const char *path, int stage, int refresh, int options)
 338{
 339        struct index_state *istate = opt->repo->index;
 340        struct cache_entry *ce;
 341        int ret;
 342
 343        ce = make_cache_entry(istate, blob->mode, &blob->oid, path, stage, 0);
 344        if (!ce)
 345                return err(opt, _("add_cacheinfo failed for path '%s'; merge aborting."), path);
 346
 347        ret = add_index_entry(istate, ce, options);
 348        if (refresh) {
 349                struct cache_entry *nce;
 350
 351                nce = refresh_cache_entry(istate, ce,
 352                                          CE_MATCH_REFRESH | CE_MATCH_IGNORE_MISSING);
 353                if (!nce)
 354                        return err(opt, _("add_cacheinfo failed to refresh for path '%s'; merge aborting."), path);
 355                if (nce != ce)
 356                        ret = add_index_entry(istate, nce, options);
 357        }
 358        return ret;
 359}
 360
 361static void init_tree_desc_from_tree(struct tree_desc *desc, struct tree *tree)
 362{
 363        parse_tree(tree);
 364        init_tree_desc(desc, tree->buffer, tree->size);
 365}
 366
 367static int unpack_trees_start(struct merge_options *opt,
 368                              struct tree *common,
 369                              struct tree *head,
 370                              struct tree *merge)
 371{
 372        int rc;
 373        struct tree_desc t[3];
 374        struct index_state tmp_index = { NULL };
 375
 376        memset(&opt->unpack_opts, 0, sizeof(opt->unpack_opts));
 377        if (opt->call_depth)
 378                opt->unpack_opts.index_only = 1;
 379        else
 380                opt->unpack_opts.update = 1;
 381        opt->unpack_opts.merge = 1;
 382        opt->unpack_opts.head_idx = 2;
 383        opt->unpack_opts.fn = threeway_merge;
 384        opt->unpack_opts.src_index = opt->repo->index;
 385        opt->unpack_opts.dst_index = &tmp_index;
 386        opt->unpack_opts.aggressive = !merge_detect_rename(opt);
 387        setup_unpack_trees_porcelain(&opt->unpack_opts, "merge");
 388
 389        init_tree_desc_from_tree(t+0, common);
 390        init_tree_desc_from_tree(t+1, head);
 391        init_tree_desc_from_tree(t+2, merge);
 392
 393        rc = unpack_trees(3, t, &opt->unpack_opts);
 394        cache_tree_free(&opt->repo->index->cache_tree);
 395
 396        /*
 397         * Update opt->repo->index to match the new results, AFTER saving a copy
 398         * in opt->orig_index.  Update src_index to point to the saved copy.
 399         * (verify_uptodate() checks src_index, and the original index is
 400         * the one that had the necessary modification timestamps.)
 401         */
 402        opt->orig_index = *opt->repo->index;
 403        *opt->repo->index = tmp_index;
 404        opt->unpack_opts.src_index = &opt->orig_index;
 405
 406        return rc;
 407}
 408
 409static void unpack_trees_finish(struct merge_options *opt)
 410{
 411        discard_index(&opt->orig_index);
 412        clear_unpack_trees_porcelain(&opt->unpack_opts);
 413}
 414
 415struct tree *write_tree_from_memory(struct merge_options *opt)
 416{
 417        struct tree *result = NULL;
 418        struct index_state *istate = opt->repo->index;
 419
 420        if (unmerged_index(istate)) {
 421                int i;
 422                fprintf(stderr, "BUG: There are unmerged index entries:\n");
 423                for (i = 0; i < istate->cache_nr; i++) {
 424                        const struct cache_entry *ce = istate->cache[i];
 425                        if (ce_stage(ce))
 426                                fprintf(stderr, "BUG: %d %.*s\n", ce_stage(ce),
 427                                        (int)ce_namelen(ce), ce->name);
 428                }
 429                BUG("unmerged index entries in merge-recursive.c");
 430        }
 431
 432        if (!istate->cache_tree)
 433                istate->cache_tree = cache_tree();
 434
 435        if (!cache_tree_fully_valid(istate->cache_tree) &&
 436            cache_tree_update(istate, 0) < 0) {
 437                err(opt, _("error building trees"));
 438                return NULL;
 439        }
 440
 441        result = lookup_tree(opt->repo, &istate->cache_tree->oid);
 442
 443        return result;
 444}
 445
 446static int save_files_dirs(const struct object_id *oid,
 447                           struct strbuf *base, const char *path,
 448                           unsigned int mode, int stage, void *context)
 449{
 450        struct path_hashmap_entry *entry;
 451        int baselen = base->len;
 452        struct merge_options *opt = context;
 453
 454        strbuf_addstr(base, path);
 455
 456        FLEX_ALLOC_MEM(entry, path, base->buf, base->len);
 457        hashmap_entry_init(entry, path_hash(entry->path));
 458        hashmap_add(&opt->current_file_dir_set, entry);
 459
 460        strbuf_setlen(base, baselen);
 461        return (S_ISDIR(mode) ? READ_TREE_RECURSIVE : 0);
 462}
 463
 464static void get_files_dirs(struct merge_options *opt, struct tree *tree)
 465{
 466        struct pathspec match_all;
 467        memset(&match_all, 0, sizeof(match_all));
 468        read_tree_recursive(opt->repo, tree, "", 0, 0,
 469                            &match_all, save_files_dirs, opt);
 470}
 471
 472static int get_tree_entry_if_blob(struct repository *r,
 473                                  const struct object_id *tree,
 474                                  const char *path,
 475                                  struct diff_filespec *dfs)
 476{
 477        int ret;
 478
 479        ret = get_tree_entry(r, tree, path, &dfs->oid, &dfs->mode);
 480        if (S_ISDIR(dfs->mode)) {
 481                oidcpy(&dfs->oid, &null_oid);
 482                dfs->mode = 0;
 483        }
 484        return ret;
 485}
 486
 487/*
 488 * Returns an index_entry instance which doesn't have to correspond to
 489 * a real cache entry in Git's index.
 490 */
 491static struct stage_data *insert_stage_data(struct repository *r,
 492                const char *path,
 493                struct tree *o, struct tree *a, struct tree *b,
 494                struct string_list *entries)
 495{
 496        struct string_list_item *item;
 497        struct stage_data *e = xcalloc(1, sizeof(struct stage_data));
 498        get_tree_entry_if_blob(r, &o->object.oid, path, &e->stages[1]);
 499        get_tree_entry_if_blob(r, &a->object.oid, path, &e->stages[2]);
 500        get_tree_entry_if_blob(r, &b->object.oid, path, &e->stages[3]);
 501        item = string_list_insert(entries, path);
 502        item->util = e;
 503        return e;
 504}
 505
 506/*
 507 * Create a dictionary mapping file names to stage_data objects. The
 508 * dictionary contains one entry for every path with a non-zero stage entry.
 509 */
 510static struct string_list *get_unmerged(struct index_state *istate)
 511{
 512        struct string_list *unmerged = xcalloc(1, sizeof(struct string_list));
 513        int i;
 514
 515        unmerged->strdup_strings = 1;
 516
 517        for (i = 0; i < istate->cache_nr; i++) {
 518                struct string_list_item *item;
 519                struct stage_data *e;
 520                const struct cache_entry *ce = istate->cache[i];
 521                if (!ce_stage(ce))
 522                        continue;
 523
 524                item = string_list_lookup(unmerged, ce->name);
 525                if (!item) {
 526                        item = string_list_insert(unmerged, ce->name);
 527                        item->util = xcalloc(1, sizeof(struct stage_data));
 528                }
 529                e = item->util;
 530                e->stages[ce_stage(ce)].mode = ce->ce_mode;
 531                oidcpy(&e->stages[ce_stage(ce)].oid, &ce->oid);
 532        }
 533
 534        return unmerged;
 535}
 536
 537static int string_list_df_name_compare(const char *one, const char *two)
 538{
 539        int onelen = strlen(one);
 540        int twolen = strlen(two);
 541        /*
 542         * Here we only care that entries for D/F conflicts are
 543         * adjacent, in particular with the file of the D/F conflict
 544         * appearing before files below the corresponding directory.
 545         * The order of the rest of the list is irrelevant for us.
 546         *
 547         * To achieve this, we sort with df_name_compare and provide
 548         * the mode S_IFDIR so that D/F conflicts will sort correctly.
 549         * We use the mode S_IFDIR for everything else for simplicity,
 550         * since in other cases any changes in their order due to
 551         * sorting cause no problems for us.
 552         */
 553        int cmp = df_name_compare(one, onelen, S_IFDIR,
 554                                  two, twolen, S_IFDIR);
 555        /*
 556         * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
 557         * that 'foo' comes before 'foo/bar'.
 558         */
 559        if (cmp)
 560                return cmp;
 561        return onelen - twolen;
 562}
 563
 564static void record_df_conflict_files(struct merge_options *opt,
 565                                     struct string_list *entries)
 566{
 567        /* If there is a D/F conflict and the file for such a conflict
 568         * currently exists in the working tree, we want to allow it to be
 569         * removed to make room for the corresponding directory if needed.
 570         * The files underneath the directories of such D/F conflicts will
 571         * be processed before the corresponding file involved in the D/F
 572         * conflict.  If the D/F directory ends up being removed by the
 573         * merge, then we won't have to touch the D/F file.  If the D/F
 574         * directory needs to be written to the working copy, then the D/F
 575         * file will simply be removed (in make_room_for_path()) to make
 576         * room for the necessary paths.  Note that if both the directory
 577         * and the file need to be present, then the D/F file will be
 578         * reinstated with a new unique name at the time it is processed.
 579         */
 580        struct string_list df_sorted_entries = STRING_LIST_INIT_NODUP;
 581        const char *last_file = NULL;
 582        int last_len = 0;
 583        int i;
 584
 585        /*
 586         * If we're merging merge-bases, we don't want to bother with
 587         * any working directory changes.
 588         */
 589        if (opt->call_depth)
 590                return;
 591
 592        /* Ensure D/F conflicts are adjacent in the entries list. */
 593        for (i = 0; i < entries->nr; i++) {
 594                struct string_list_item *next = &entries->items[i];
 595                string_list_append(&df_sorted_entries, next->string)->util =
 596                                   next->util;
 597        }
 598        df_sorted_entries.cmp = string_list_df_name_compare;
 599        string_list_sort(&df_sorted_entries);
 600
 601        string_list_clear(&opt->df_conflict_file_set, 1);
 602        for (i = 0; i < df_sorted_entries.nr; i++) {
 603                const char *path = df_sorted_entries.items[i].string;
 604                int len = strlen(path);
 605                struct stage_data *e = df_sorted_entries.items[i].util;
 606
 607                /*
 608                 * Check if last_file & path correspond to a D/F conflict;
 609                 * i.e. whether path is last_file+'/'+<something>.
 610                 * If so, record that it's okay to remove last_file to make
 611                 * room for path and friends if needed.
 612                 */
 613                if (last_file &&
 614                    len > last_len &&
 615                    memcmp(path, last_file, last_len) == 0 &&
 616                    path[last_len] == '/') {
 617                        string_list_insert(&opt->df_conflict_file_set, last_file);
 618                }
 619
 620                /*
 621                 * Determine whether path could exist as a file in the
 622                 * working directory as a possible D/F conflict.  This
 623                 * will only occur when it exists in stage 2 as a
 624                 * file.
 625                 */
 626                if (S_ISREG(e->stages[2].mode) || S_ISLNK(e->stages[2].mode)) {
 627                        last_file = path;
 628                        last_len = len;
 629                } else {
 630                        last_file = NULL;
 631                }
 632        }
 633        string_list_clear(&df_sorted_entries, 0);
 634}
 635
 636static int update_stages(struct merge_options *opt, const char *path,
 637                         const struct diff_filespec *o,
 638                         const struct diff_filespec *a,
 639                         const struct diff_filespec *b)
 640{
 641
 642        /*
 643         * NOTE: It is usually a bad idea to call update_stages on a path
 644         * before calling update_file on that same path, since it can
 645         * sometimes lead to spurious "refusing to lose untracked file..."
 646         * messages from update_file (via make_room_for path via
 647         * would_lose_untracked).  Instead, reverse the order of the calls
 648         * (executing update_file first and then update_stages).
 649         */
 650        int clear = 1;
 651        int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_SKIP_DFCHECK;
 652        if (clear)
 653                if (remove_file_from_index(opt->repo->index, path))
 654                        return -1;
 655        if (o)
 656                if (add_cacheinfo(opt, o, path, 1, 0, options))
 657                        return -1;
 658        if (a)
 659                if (add_cacheinfo(opt, a, path, 2, 0, options))
 660                        return -1;
 661        if (b)
 662                if (add_cacheinfo(opt, b, path, 3, 0, options))
 663                        return -1;
 664        return 0;
 665}
 666
 667static void update_entry(struct stage_data *entry,
 668                         struct diff_filespec *o,
 669                         struct diff_filespec *a,
 670                         struct diff_filespec *b)
 671{
 672        entry->processed = 0;
 673        entry->stages[1].mode = o->mode;
 674        entry->stages[2].mode = a->mode;
 675        entry->stages[3].mode = b->mode;
 676        oidcpy(&entry->stages[1].oid, &o->oid);
 677        oidcpy(&entry->stages[2].oid, &a->oid);
 678        oidcpy(&entry->stages[3].oid, &b->oid);
 679}
 680
 681static int remove_file(struct merge_options *opt, int clean,
 682                       const char *path, int no_wd)
 683{
 684        int update_cache = opt->call_depth || clean;
 685        int update_working_directory = !opt->call_depth && !no_wd;
 686
 687        if (update_cache) {
 688                if (remove_file_from_index(opt->repo->index, path))
 689                        return -1;
 690        }
 691        if (update_working_directory) {
 692                if (ignore_case) {
 693                        struct cache_entry *ce;
 694                        ce = index_file_exists(opt->repo->index, path, strlen(path),
 695                                               ignore_case);
 696                        if (ce && ce_stage(ce) == 0 && strcmp(path, ce->name))
 697                                return 0;
 698                }
 699                if (remove_path(path))
 700                        return -1;
 701        }
 702        return 0;
 703}
 704
 705/* add a string to a strbuf, but converting "/" to "_" */
 706static void add_flattened_path(struct strbuf *out, const char *s)
 707{
 708        size_t i = out->len;
 709        strbuf_addstr(out, s);
 710        for (; i < out->len; i++)
 711                if (out->buf[i] == '/')
 712                        out->buf[i] = '_';
 713}
 714
 715static char *unique_path(struct merge_options *opt, const char *path, const char *branch)
 716{
 717        struct path_hashmap_entry *entry;
 718        struct strbuf newpath = STRBUF_INIT;
 719        int suffix = 0;
 720        size_t base_len;
 721
 722        strbuf_addf(&newpath, "%s~", path);
 723        add_flattened_path(&newpath, branch);
 724
 725        base_len = newpath.len;
 726        while (hashmap_get_from_hash(&opt->current_file_dir_set,
 727                                     path_hash(newpath.buf), newpath.buf) ||
 728               (!opt->call_depth && file_exists(newpath.buf))) {
 729                strbuf_setlen(&newpath, base_len);
 730                strbuf_addf(&newpath, "_%d", suffix++);
 731        }
 732
 733        FLEX_ALLOC_MEM(entry, path, newpath.buf, newpath.len);
 734        hashmap_entry_init(entry, path_hash(entry->path));
 735        hashmap_add(&opt->current_file_dir_set, entry);
 736        return strbuf_detach(&newpath, NULL);
 737}
 738
 739/**
 740 * Check whether a directory in the index is in the way of an incoming
 741 * file.  Return 1 if so.  If check_working_copy is non-zero, also
 742 * check the working directory.  If empty_ok is non-zero, also return
 743 * 0 in the case where the working-tree dir exists but is empty.
 744 */
 745static int dir_in_way(struct index_state *istate, const char *path,
 746                      int check_working_copy, int empty_ok)
 747{
 748        int pos;
 749        struct strbuf dirpath = STRBUF_INIT;
 750        struct stat st;
 751
 752        strbuf_addstr(&dirpath, path);
 753        strbuf_addch(&dirpath, '/');
 754
 755        pos = index_name_pos(istate, dirpath.buf, dirpath.len);
 756
 757        if (pos < 0)
 758                pos = -1 - pos;
 759        if (pos < istate->cache_nr &&
 760            !strncmp(dirpath.buf, istate->cache[pos]->name, dirpath.len)) {
 761                strbuf_release(&dirpath);
 762                return 1;
 763        }
 764
 765        strbuf_release(&dirpath);
 766        return check_working_copy && !lstat(path, &st) && S_ISDIR(st.st_mode) &&
 767                !(empty_ok && is_empty_dir(path));
 768}
 769
 770/*
 771 * Returns whether path was tracked in the index before the merge started,
 772 * and its oid and mode match the specified values
 773 */
 774static int was_tracked_and_matches(struct merge_options *opt, const char *path,
 775                                   const struct diff_filespec *blob)
 776{
 777        int pos = index_name_pos(&opt->orig_index, path, strlen(path));
 778        struct cache_entry *ce;
 779
 780        if (0 > pos)
 781                /* we were not tracking this path before the merge */
 782                return 0;
 783
 784        /* See if the file we were tracking before matches */
 785        ce = opt->orig_index.cache[pos];
 786        return (oid_eq(&ce->oid, &blob->oid) && ce->ce_mode == blob->mode);
 787}
 788
 789/*
 790 * Returns whether path was tracked in the index before the merge started
 791 */
 792static int was_tracked(struct merge_options *opt, const char *path)
 793{
 794        int pos = index_name_pos(&opt->orig_index, path, strlen(path));
 795
 796        if (0 <= pos)
 797                /* we were tracking this path before the merge */
 798                return 1;
 799
 800        return 0;
 801}
 802
 803static int would_lose_untracked(struct merge_options *opt, const char *path)
 804{
 805        struct index_state *istate = opt->repo->index;
 806
 807        /*
 808         * This may look like it can be simplified to:
 809         *   return !was_tracked(opt, path) && file_exists(path)
 810         * but it can't.  This function needs to know whether path was in
 811         * the working tree due to EITHER having been tracked in the index
 812         * before the merge OR having been put into the working copy and
 813         * index by unpack_trees().  Due to that either-or requirement, we
 814         * check the current index instead of the original one.
 815         *
 816         * Note that we do not need to worry about merge-recursive itself
 817         * updating the index after unpack_trees() and before calling this
 818         * function, because we strictly require all code paths in
 819         * merge-recursive to update the working tree first and the index
 820         * second.  Doing otherwise would break
 821         * update_file()/would_lose_untracked(); see every comment in this
 822         * file which mentions "update_stages".
 823         */
 824        int pos = index_name_pos(istate, path, strlen(path));
 825
 826        if (pos < 0)
 827                pos = -1 - pos;
 828        while (pos < istate->cache_nr &&
 829               !strcmp(path, istate->cache[pos]->name)) {
 830                /*
 831                 * If stage #0, it is definitely tracked.
 832                 * If it has stage #2 then it was tracked
 833                 * before this merge started.  All other
 834                 * cases the path was not tracked.
 835                 */
 836                switch (ce_stage(istate->cache[pos])) {
 837                case 0:
 838                case 2:
 839                        return 0;
 840                }
 841                pos++;
 842        }
 843        return file_exists(path);
 844}
 845
 846static int was_dirty(struct merge_options *opt, const char *path)
 847{
 848        struct cache_entry *ce;
 849        int dirty = 1;
 850
 851        if (opt->call_depth || !was_tracked(opt, path))
 852                return !dirty;
 853
 854        ce = index_file_exists(opt->unpack_opts.src_index,
 855                               path, strlen(path), ignore_case);
 856        dirty = verify_uptodate(ce, &opt->unpack_opts) != 0;
 857        return dirty;
 858}
 859
 860static int make_room_for_path(struct merge_options *opt, const char *path)
 861{
 862        int status, i;
 863        const char *msg = _("failed to create path '%s'%s");
 864
 865        /* Unlink any D/F conflict files that are in the way */
 866        for (i = 0; i < opt->df_conflict_file_set.nr; i++) {
 867                const char *df_path = opt->df_conflict_file_set.items[i].string;
 868                size_t pathlen = strlen(path);
 869                size_t df_pathlen = strlen(df_path);
 870                if (df_pathlen < pathlen &&
 871                    path[df_pathlen] == '/' &&
 872                    strncmp(path, df_path, df_pathlen) == 0) {
 873                        output(opt, 3,
 874                               _("Removing %s to make room for subdirectory\n"),
 875                               df_path);
 876                        unlink(df_path);
 877                        unsorted_string_list_delete_item(&opt->df_conflict_file_set,
 878                                                         i, 0);
 879                        break;
 880                }
 881        }
 882
 883        /* Make sure leading directories are created */
 884        status = safe_create_leading_directories_const(path);
 885        if (status) {
 886                if (status == SCLD_EXISTS)
 887                        /* something else exists */
 888                        return err(opt, msg, path, _(": perhaps a D/F conflict?"));
 889                return err(opt, msg, path, "");
 890        }
 891
 892        /*
 893         * Do not unlink a file in the work tree if we are not
 894         * tracking it.
 895         */
 896        if (would_lose_untracked(opt, path))
 897                return err(opt, _("refusing to lose untracked file at '%s'"),
 898                           path);
 899
 900        /* Successful unlink is good.. */
 901        if (!unlink(path))
 902                return 0;
 903        /* .. and so is no existing file */
 904        if (errno == ENOENT)
 905                return 0;
 906        /* .. but not some other error (who really cares what?) */
 907        return err(opt, msg, path, _(": perhaps a D/F conflict?"));
 908}
 909
 910static int update_file_flags(struct merge_options *opt,
 911                             const struct diff_filespec *contents,
 912                             const char *path,
 913                             int update_cache,
 914                             int update_wd)
 915{
 916        int ret = 0;
 917
 918        if (opt->call_depth)
 919                update_wd = 0;
 920
 921        if (update_wd) {
 922                enum object_type type;
 923                void *buf;
 924                unsigned long size;
 925
 926                if (S_ISGITLINK(contents->mode)) {
 927                        /*
 928                         * We may later decide to recursively descend into
 929                         * the submodule directory and update its index
 930                         * and/or work tree, but we do not do that now.
 931                         */
 932                        update_wd = 0;
 933                        goto update_index;
 934                }
 935
 936                buf = read_object_file(&contents->oid, &type, &size);
 937                if (!buf)
 938                        return err(opt, _("cannot read object %s '%s'"),
 939                                   oid_to_hex(&contents->oid), path);
 940                if (type != OBJ_BLOB) {
 941                        ret = err(opt, _("blob expected for %s '%s'"),
 942                                  oid_to_hex(&contents->oid), path);
 943                        goto free_buf;
 944                }
 945                if (S_ISREG(contents->mode)) {
 946                        struct strbuf strbuf = STRBUF_INIT;
 947                        if (convert_to_working_tree(opt->repo->index, path, buf, size, &strbuf)) {
 948                                free(buf);
 949                                size = strbuf.len;
 950                                buf = strbuf_detach(&strbuf, NULL);
 951                        }
 952                }
 953
 954                if (make_room_for_path(opt, path) < 0) {
 955                        update_wd = 0;
 956                        goto free_buf;
 957                }
 958                if (S_ISREG(contents->mode) ||
 959                    (!has_symlinks && S_ISLNK(contents->mode))) {
 960                        int fd;
 961                        int mode = (contents->mode & 0100 ? 0777 : 0666);
 962
 963                        fd = open(path, O_WRONLY | O_TRUNC | O_CREAT, mode);
 964                        if (fd < 0) {
 965                                ret = err(opt, _("failed to open '%s': %s"),
 966                                          path, strerror(errno));
 967                                goto free_buf;
 968                        }
 969                        write_in_full(fd, buf, size);
 970                        close(fd);
 971                } else if (S_ISLNK(contents->mode)) {
 972                        char *lnk = xmemdupz(buf, size);
 973                        safe_create_leading_directories_const(path);
 974                        unlink(path);
 975                        if (symlink(lnk, path))
 976                                ret = err(opt, _("failed to symlink '%s': %s"),
 977                                          path, strerror(errno));
 978                        free(lnk);
 979                } else
 980                        ret = err(opt,
 981                                  _("do not know what to do with %06o %s '%s'"),
 982                                  contents->mode, oid_to_hex(&contents->oid), path);
 983        free_buf:
 984                free(buf);
 985        }
 986update_index:
 987        if (!ret && update_cache)
 988                if (add_cacheinfo(opt, contents, path, 0, update_wd,
 989                                  ADD_CACHE_OK_TO_ADD))
 990                        return -1;
 991        return ret;
 992}
 993
 994static int update_file(struct merge_options *opt,
 995                       int clean,
 996                       const struct diff_filespec *contents,
 997                       const char *path)
 998{
 999        return update_file_flags(opt, contents, path,
1000                                 opt->call_depth || clean, !opt->call_depth);
1001}
1002
1003/* Low level file merging, update and removal */
1004
1005struct merge_file_info {
1006        struct diff_filespec blob; /* mostly use oid & mode; sometimes path */
1007        unsigned clean:1,
1008                 merge:1;
1009};
1010
1011static int merge_3way(struct merge_options *opt,
1012                      mmbuffer_t *result_buf,
1013                      const struct diff_filespec *o,
1014                      const struct diff_filespec *a,
1015                      const struct diff_filespec *b,
1016                      const char *branch1,
1017                      const char *branch2,
1018                      const int extra_marker_size)
1019{
1020        mmfile_t orig, src1, src2;
1021        struct ll_merge_options ll_opts = {0};
1022        char *base_name, *name1, *name2;
1023        int merge_status;
1024
1025        ll_opts.renormalize = opt->renormalize;
1026        ll_opts.extra_marker_size = extra_marker_size;
1027        ll_opts.xdl_opts = opt->xdl_opts;
1028
1029        if (opt->call_depth) {
1030                ll_opts.virtual_ancestor = 1;
1031                ll_opts.variant = 0;
1032        } else {
1033                switch (opt->recursive_variant) {
1034                case MERGE_RECURSIVE_OURS:
1035                        ll_opts.variant = XDL_MERGE_FAVOR_OURS;
1036                        break;
1037                case MERGE_RECURSIVE_THEIRS:
1038                        ll_opts.variant = XDL_MERGE_FAVOR_THEIRS;
1039                        break;
1040                default:
1041                        ll_opts.variant = 0;
1042                        break;
1043                }
1044        }
1045
1046        assert(a->path && b->path);
1047        if (strcmp(a->path, b->path) ||
1048            (opt->ancestor != NULL && strcmp(a->path, o->path) != 0)) {
1049                base_name = opt->ancestor == NULL ? NULL :
1050                        mkpathdup("%s:%s", opt->ancestor, o->path);
1051                name1 = mkpathdup("%s:%s", branch1, a->path);
1052                name2 = mkpathdup("%s:%s", branch2, b->path);
1053        } else {
1054                base_name = opt->ancestor == NULL ? NULL :
1055                        mkpathdup("%s", opt->ancestor);
1056                name1 = mkpathdup("%s", branch1);
1057                name2 = mkpathdup("%s", branch2);
1058        }
1059
1060        read_mmblob(&orig, &o->oid);
1061        read_mmblob(&src1, &a->oid);
1062        read_mmblob(&src2, &b->oid);
1063
1064        merge_status = ll_merge(result_buf, a->path, &orig, base_name,
1065                                &src1, name1, &src2, name2,
1066                                opt->repo->index, &ll_opts);
1067
1068        free(base_name);
1069        free(name1);
1070        free(name2);
1071        free(orig.ptr);
1072        free(src1.ptr);
1073        free(src2.ptr);
1074        return merge_status;
1075}
1076
1077static int find_first_merges(struct repository *repo,
1078                             struct object_array *result, const char *path,
1079                             struct commit *a, struct commit *b)
1080{
1081        int i, j;
1082        struct object_array merges = OBJECT_ARRAY_INIT;
1083        struct commit *commit;
1084        int contains_another;
1085
1086        char merged_revision[GIT_MAX_HEXSZ + 2];
1087        const char *rev_args[] = { "rev-list", "--merges", "--ancestry-path",
1088                                   "--all", merged_revision, NULL };
1089        struct rev_info revs;
1090        struct setup_revision_opt rev_opts;
1091
1092        memset(result, 0, sizeof(struct object_array));
1093        memset(&rev_opts, 0, sizeof(rev_opts));
1094
1095        /* get all revisions that merge commit a */
1096        xsnprintf(merged_revision, sizeof(merged_revision), "^%s",
1097                  oid_to_hex(&a->object.oid));
1098        repo_init_revisions(repo, &revs, NULL);
1099        rev_opts.submodule = path;
1100        /* FIXME: can't handle linked worktrees in submodules yet */
1101        revs.single_worktree = path != NULL;
1102        setup_revisions(ARRAY_SIZE(rev_args)-1, rev_args, &revs, &rev_opts);
1103
1104        /* save all revisions from the above list that contain b */
1105        if (prepare_revision_walk(&revs))
1106                die("revision walk setup failed");
1107        while ((commit = get_revision(&revs)) != NULL) {
1108                struct object *o = &(commit->object);
1109                if (in_merge_bases(b, commit))
1110                        add_object_array(o, NULL, &merges);
1111        }
1112        reset_revision_walk();
1113
1114        /* Now we've got all merges that contain a and b. Prune all
1115         * merges that contain another found merge and save them in
1116         * result.
1117         */
1118        for (i = 0; i < merges.nr; i++) {
1119                struct commit *m1 = (struct commit *) merges.objects[i].item;
1120
1121                contains_another = 0;
1122                for (j = 0; j < merges.nr; j++) {
1123                        struct commit *m2 = (struct commit *) merges.objects[j].item;
1124                        if (i != j && in_merge_bases(m2, m1)) {
1125                                contains_another = 1;
1126                                break;
1127                        }
1128                }
1129
1130                if (!contains_another)
1131                        add_object_array(merges.objects[i].item, NULL, result);
1132        }
1133
1134        object_array_clear(&merges);
1135        return result->nr;
1136}
1137
1138static void print_commit(struct commit *commit)
1139{
1140        struct strbuf sb = STRBUF_INIT;
1141        struct pretty_print_context ctx = {0};
1142        ctx.date_mode.type = DATE_NORMAL;
1143        format_commit_message(commit, " %h: %m %s", &sb, &ctx);
1144        fprintf(stderr, "%s\n", sb.buf);
1145        strbuf_release(&sb);
1146}
1147
1148static int is_valid(const struct diff_filespec *dfs)
1149{
1150        return dfs->mode != 0 && !is_null_oid(&dfs->oid);
1151}
1152
1153static int merge_submodule(struct merge_options *opt,
1154                           struct object_id *result, const char *path,
1155                           const struct object_id *base, const struct object_id *a,
1156                           const struct object_id *b)
1157{
1158        struct commit *commit_base, *commit_a, *commit_b;
1159        int parent_count;
1160        struct object_array merges;
1161
1162        int i;
1163        int search = !opt->call_depth;
1164
1165        /* store a in result in case we fail */
1166        oidcpy(result, a);
1167
1168        /* we can not handle deletion conflicts */
1169        if (is_null_oid(base))
1170                return 0;
1171        if (is_null_oid(a))
1172                return 0;
1173        if (is_null_oid(b))
1174                return 0;
1175
1176        if (add_submodule_odb(path)) {
1177                output(opt, 1, _("Failed to merge submodule %s (not checked out)"), path);
1178                return 0;
1179        }
1180
1181        if (!(commit_base = lookup_commit_reference(opt->repo, base)) ||
1182            !(commit_a = lookup_commit_reference(opt->repo, a)) ||
1183            !(commit_b = lookup_commit_reference(opt->repo, b))) {
1184                output(opt, 1, _("Failed to merge submodule %s (commits not present)"), path);
1185                return 0;
1186        }
1187
1188        /* check whether both changes are forward */
1189        if (!in_merge_bases(commit_base, commit_a) ||
1190            !in_merge_bases(commit_base, commit_b)) {
1191                output(opt, 1, _("Failed to merge submodule %s (commits don't follow merge-base)"), path);
1192                return 0;
1193        }
1194
1195        /* Case #1: a is contained in b or vice versa */
1196        if (in_merge_bases(commit_a, commit_b)) {
1197                oidcpy(result, b);
1198                if (show(opt, 3)) {
1199                        output(opt, 3, _("Fast-forwarding submodule %s to the following commit:"), path);
1200                        output_commit_title(opt, commit_b);
1201                } else if (show(opt, 2))
1202                        output(opt, 2, _("Fast-forwarding submodule %s"), path);
1203                else
1204                        ; /* no output */
1205
1206                return 1;
1207        }
1208        if (in_merge_bases(commit_b, commit_a)) {
1209                oidcpy(result, a);
1210                if (show(opt, 3)) {
1211                        output(opt, 3, _("Fast-forwarding submodule %s to the following commit:"), path);
1212                        output_commit_title(opt, commit_a);
1213                } else if (show(opt, 2))
1214                        output(opt, 2, _("Fast-forwarding submodule %s"), path);
1215                else
1216                        ; /* no output */
1217
1218                return 1;
1219        }
1220
1221        /*
1222         * Case #2: There are one or more merges that contain a and b in
1223         * the submodule. If there is only one, then present it as a
1224         * suggestion to the user, but leave it marked unmerged so the
1225         * user needs to confirm the resolution.
1226         */
1227
1228        /* Skip the search if makes no sense to the calling context.  */
1229        if (!search)
1230                return 0;
1231
1232        /* find commit which merges them */
1233        parent_count = find_first_merges(opt->repo, &merges, path,
1234                                         commit_a, commit_b);
1235        switch (parent_count) {
1236        case 0:
1237                output(opt, 1, _("Failed to merge submodule %s (merge following commits not found)"), path);
1238                break;
1239
1240        case 1:
1241                output(opt, 1, _("Failed to merge submodule %s (not fast-forward)"), path);
1242                output(opt, 2, _("Found a possible merge resolution for the submodule:\n"));
1243                print_commit((struct commit *) merges.objects[0].item);
1244                output(opt, 2, _(
1245                       "If this is correct simply add it to the index "
1246                       "for example\n"
1247                       "by using:\n\n"
1248                       "  git update-index --cacheinfo 160000 %s \"%s\"\n\n"
1249                       "which will accept this suggestion.\n"),
1250                       oid_to_hex(&merges.objects[0].item->oid), path);
1251                break;
1252
1253        default:
1254                output(opt, 1, _("Failed to merge submodule %s (multiple merges found)"), path);
1255                for (i = 0; i < merges.nr; i++)
1256                        print_commit((struct commit *) merges.objects[i].item);
1257        }
1258
1259        object_array_clear(&merges);
1260        return 0;
1261}
1262
1263static int merge_mode_and_contents(struct merge_options *opt,
1264                                   const struct diff_filespec *o,
1265                                   const struct diff_filespec *a,
1266                                   const struct diff_filespec *b,
1267                                   const char *filename,
1268                                   const char *branch1,
1269                                   const char *branch2,
1270                                   const int extra_marker_size,
1271                                   struct merge_file_info *result)
1272{
1273        if (opt->branch1 != branch1) {
1274                /*
1275                 * It's weird getting a reverse merge with HEAD on the bottom
1276                 * side of the conflict markers and the other branch on the
1277                 * top.  Fix that.
1278                 */
1279                return merge_mode_and_contents(opt, o, b, a,
1280                                               filename,
1281                                               branch2, branch1,
1282                                               extra_marker_size, result);
1283        }
1284
1285        result->merge = 0;
1286        result->clean = 1;
1287
1288        if ((S_IFMT & a->mode) != (S_IFMT & b->mode)) {
1289                result->clean = 0;
1290                if (S_ISREG(a->mode)) {
1291                        result->blob.mode = a->mode;
1292                        oidcpy(&result->blob.oid, &a->oid);
1293                } else {
1294                        result->blob.mode = b->mode;
1295                        oidcpy(&result->blob.oid, &b->oid);
1296                }
1297        } else {
1298                if (!oid_eq(&a->oid, &o->oid) && !oid_eq(&b->oid, &o->oid))
1299                        result->merge = 1;
1300
1301                /*
1302                 * Merge modes
1303                 */
1304                if (a->mode == b->mode || a->mode == o->mode)
1305                        result->blob.mode = b->mode;
1306                else {
1307                        result->blob.mode = a->mode;
1308                        if (b->mode != o->mode) {
1309                                result->clean = 0;
1310                                result->merge = 1;
1311                        }
1312                }
1313
1314                if (oid_eq(&a->oid, &b->oid) || oid_eq(&a->oid, &o->oid))
1315                        oidcpy(&result->blob.oid, &b->oid);
1316                else if (oid_eq(&b->oid, &o->oid))
1317                        oidcpy(&result->blob.oid, &a->oid);
1318                else if (S_ISREG(a->mode)) {
1319                        mmbuffer_t result_buf;
1320                        int ret = 0, merge_status;
1321
1322                        merge_status = merge_3way(opt, &result_buf, o, a, b,
1323                                                  branch1, branch2,
1324                                                  extra_marker_size);
1325
1326                        if ((merge_status < 0) || !result_buf.ptr)
1327                                ret = err(opt, _("Failed to execute internal merge"));
1328
1329                        if (!ret &&
1330                            write_object_file(result_buf.ptr, result_buf.size,
1331                                              blob_type, &result->blob.oid))
1332                                ret = err(opt, _("Unable to add %s to database"),
1333                                          a->path);
1334
1335                        free(result_buf.ptr);
1336                        if (ret)
1337                                return ret;
1338                        result->clean = (merge_status == 0);
1339                } else if (S_ISGITLINK(a->mode)) {
1340                        result->clean = merge_submodule(opt, &result->blob.oid,
1341                                                        o->path,
1342                                                        &o->oid,
1343                                                        &a->oid,
1344                                                        &b->oid);
1345                } else if (S_ISLNK(a->mode)) {
1346                        switch (opt->recursive_variant) {
1347                        case MERGE_RECURSIVE_NORMAL:
1348                                oidcpy(&result->blob.oid, &a->oid);
1349                                if (!oid_eq(&a->oid, &b->oid))
1350                                        result->clean = 0;
1351                                break;
1352                        case MERGE_RECURSIVE_OURS:
1353                                oidcpy(&result->blob.oid, &a->oid);
1354                                break;
1355                        case MERGE_RECURSIVE_THEIRS:
1356                                oidcpy(&result->blob.oid, &b->oid);
1357                                break;
1358                        }
1359                } else
1360                        BUG("unsupported object type in the tree");
1361        }
1362
1363        if (result->merge)
1364                output(opt, 2, _("Auto-merging %s"), filename);
1365
1366        return 0;
1367}
1368
1369static int handle_rename_via_dir(struct merge_options *opt,
1370                                 struct rename_conflict_info *ci)
1371{
1372        /*
1373         * Handle file adds that need to be renamed due to directory rename
1374         * detection.  This differs from handle_rename_normal, because
1375         * there is no content merge to do; just move the file into the
1376         * desired final location.
1377         */
1378        const struct rename *ren = ci->ren1;
1379        const struct diff_filespec *dest = ren->pair->two;
1380        char *file_path = dest->path;
1381        int mark_conflicted = (opt->detect_directory_renames == 1);
1382        assert(ren->dir_rename_original_dest);
1383
1384        if (!opt->call_depth && would_lose_untracked(opt, dest->path)) {
1385                mark_conflicted = 1;
1386                file_path = unique_path(opt, dest->path, ren->branch);
1387                output(opt, 1, _("Error: Refusing to lose untracked file at %s; "
1388                                 "writing to %s instead."),
1389                       dest->path, file_path);
1390        }
1391
1392        if (mark_conflicted) {
1393                /*
1394                 * Write the file in worktree at file_path.  In the index,
1395                 * only record the file at dest->path in the appropriate
1396                 * higher stage.
1397                 */
1398                if (update_file(opt, 0, dest, file_path))
1399                        return -1;
1400                if (file_path != dest->path)
1401                        free(file_path);
1402                if (update_stages(opt, dest->path, NULL,
1403                                  ren->branch == opt->branch1 ? dest : NULL,
1404                                  ren->branch == opt->branch1 ? NULL : dest))
1405                        return -1;
1406                return 0; /* not clean, but conflicted */
1407        } else {
1408                /* Update dest->path both in index and in worktree */
1409                if (update_file(opt, 1, dest, dest->path))
1410                        return -1;
1411                return 1; /* clean */
1412        }
1413}
1414
1415static int handle_change_delete(struct merge_options *opt,
1416                                const char *path, const char *old_path,
1417                                const struct diff_filespec *o,
1418                                const struct diff_filespec *changed,
1419                                const char *change_branch,
1420                                const char *delete_branch,
1421                                const char *change, const char *change_past)
1422{
1423        char *alt_path = NULL;
1424        const char *update_path = path;
1425        int ret = 0;
1426
1427        if (dir_in_way(opt->repo->index, path, !opt->call_depth, 0) ||
1428            (!opt->call_depth && would_lose_untracked(opt, path))) {
1429                update_path = alt_path = unique_path(opt, path, change_branch);
1430        }
1431
1432        if (opt->call_depth) {
1433                /*
1434                 * We cannot arbitrarily accept either a_sha or b_sha as
1435                 * correct; since there is no true "middle point" between
1436                 * them, simply reuse the base version for virtual merge base.
1437                 */
1438                ret = remove_file_from_index(opt->repo->index, path);
1439                if (!ret)
1440                        ret = update_file(opt, 0, o, update_path);
1441        } else {
1442                /*
1443                 * Despite the four nearly duplicate messages and argument
1444                 * lists below and the ugliness of the nested if-statements,
1445                 * having complete messages makes the job easier for
1446                 * translators.
1447                 *
1448                 * The slight variance among the cases is due to the fact
1449                 * that:
1450                 *   1) directory/file conflicts (in effect if
1451                 *      !alt_path) could cause us to need to write the
1452                 *      file to a different path.
1453                 *   2) renames (in effect if !old_path) could mean that
1454                 *      there are two names for the path that the user
1455                 *      may know the file by.
1456                 */
1457                if (!alt_path) {
1458                        if (!old_path) {
1459                                output(opt, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1460                                       "and %s in %s. Version %s of %s left in tree."),
1461                                       change, path, delete_branch, change_past,
1462                                       change_branch, change_branch, path);
1463                        } else {
1464                                output(opt, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1465                                       "and %s to %s in %s. Version %s of %s left in tree."),
1466                                       change, old_path, delete_branch, change_past, path,
1467                                       change_branch, change_branch, path);
1468                        }
1469                } else {
1470                        if (!old_path) {
1471                                output(opt, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1472                                       "and %s in %s. Version %s of %s left in tree at %s."),
1473                                       change, path, delete_branch, change_past,
1474                                       change_branch, change_branch, path, alt_path);
1475                        } else {
1476                                output(opt, 1, _("CONFLICT (%s/delete): %s deleted in %s "
1477                                       "and %s to %s in %s. Version %s of %s left in tree at %s."),
1478                                       change, old_path, delete_branch, change_past, path,
1479                                       change_branch, change_branch, path, alt_path);
1480                        }
1481                }
1482                /*
1483                 * No need to call update_file() on path when change_branch ==
1484                 * opt->branch1 && !alt_path, since that would needlessly touch
1485                 * path.  We could call update_file_flags() with update_cache=0
1486                 * and update_wd=0, but that's a no-op.
1487                 */
1488                if (change_branch != opt->branch1 || alt_path)
1489                        ret = update_file(opt, 0, changed, update_path);
1490        }
1491        free(alt_path);
1492
1493        return ret;
1494}
1495
1496static int handle_rename_delete(struct merge_options *opt,
1497                                struct rename_conflict_info *ci)
1498{
1499        const struct rename *ren = ci->ren1;
1500        const struct diff_filespec *orig = ren->pair->one;
1501        const struct diff_filespec *dest = ren->pair->two;
1502        const char *rename_branch = ren->branch;
1503        const char *delete_branch = (opt->branch1 == ren->branch ?
1504                                     opt->branch2 : opt->branch1);
1505
1506        if (handle_change_delete(opt,
1507                                 opt->call_depth ? orig->path : dest->path,
1508                                 opt->call_depth ? NULL : orig->path,
1509                                 orig, dest,
1510                                 rename_branch, delete_branch,
1511                                 _("rename"), _("renamed")))
1512                return -1;
1513
1514        if (opt->call_depth)
1515                return remove_file_from_index(opt->repo->index, dest->path);
1516        else
1517                return update_stages(opt, dest->path, NULL,
1518                                     rename_branch == opt->branch1 ? dest : NULL,
1519                                     rename_branch == opt->branch1 ? NULL : dest);
1520}
1521
1522static int handle_file_collision(struct merge_options *opt,
1523                                 const char *collide_path,
1524                                 const char *prev_path1,
1525                                 const char *prev_path2,
1526                                 const char *branch1, const char *branch2,
1527                                 struct diff_filespec *a,
1528                                 struct diff_filespec *b)
1529{
1530        struct merge_file_info mfi;
1531        struct diff_filespec null;
1532        char *alt_path = NULL;
1533        const char *update_path = collide_path;
1534
1535        /*
1536         * It's easiest to get the correct things into stage 2 and 3, and
1537         * to make sure that the content merge puts HEAD before the other
1538         * branch if we just ensure that branch1 == opt->branch1.  So, simply
1539         * flip arguments around if we don't have that.
1540         */
1541        if (branch1 != opt->branch1) {
1542                return handle_file_collision(opt, collide_path,
1543                                             prev_path2, prev_path1,
1544                                             branch2, branch1,
1545                                             b, a);
1546        }
1547
1548        /*
1549         * In the recursive case, we just opt to undo renames
1550         */
1551        if (opt->call_depth && (prev_path1 || prev_path2)) {
1552                /* Put first file (a->oid, a->mode) in its original spot */
1553                if (prev_path1) {
1554                        if (update_file(opt, 1, a, prev_path1))
1555                                return -1;
1556                } else {
1557                        if (update_file(opt, 1, a, collide_path))
1558                                return -1;
1559                }
1560
1561                /* Put second file (b->oid, b->mode) in its original spot */
1562                if (prev_path2) {
1563                        if (update_file(opt, 1, b, prev_path2))
1564                                return -1;
1565                } else {
1566                        if (update_file(opt, 1, b, collide_path))
1567                                return -1;
1568                }
1569
1570                /* Don't leave something at collision path if unrenaming both */
1571                if (prev_path1 && prev_path2)
1572                        remove_file(opt, 1, collide_path, 0);
1573
1574                return 0;
1575        }
1576
1577        /* Remove rename sources if rename/add or rename/rename(2to1) */
1578        if (prev_path1)
1579                remove_file(opt, 1, prev_path1,
1580                            opt->call_depth || would_lose_untracked(opt, prev_path1));
1581        if (prev_path2)
1582                remove_file(opt, 1, prev_path2,
1583                            opt->call_depth || would_lose_untracked(opt, prev_path2));
1584
1585        /*
1586         * Remove the collision path, if it wouldn't cause dirty contents
1587         * or an untracked file to get lost.  We'll either overwrite with
1588         * merged contents, or just write out to differently named files.
1589         */
1590        if (was_dirty(opt, collide_path)) {
1591                output(opt, 1, _("Refusing to lose dirty file at %s"),
1592                       collide_path);
1593                update_path = alt_path = unique_path(opt, collide_path, "merged");
1594        } else if (would_lose_untracked(opt, collide_path)) {
1595                /*
1596                 * Only way we get here is if both renames were from
1597                 * a directory rename AND user had an untracked file
1598                 * at the location where both files end up after the
1599                 * two directory renames.  See testcase 10d of t6043.
1600                 */
1601                output(opt, 1, _("Refusing to lose untracked file at "
1602                               "%s, even though it's in the way."),
1603                       collide_path);
1604                update_path = alt_path = unique_path(opt, collide_path, "merged");
1605        } else {
1606                /*
1607                 * FIXME: It's possible that the two files are identical
1608                 * and that the current working copy happens to match, in
1609                 * which case we are unnecessarily touching the working
1610                 * tree file.  It's not a likely enough scenario that I
1611                 * want to code up the checks for it and a better fix is
1612                 * available if we restructure how unpack_trees() and
1613                 * merge-recursive interoperate anyway, so punting for
1614                 * now...
1615                 */
1616                remove_file(opt, 0, collide_path, 0);
1617        }
1618
1619        /* Store things in diff_filespecs for functions that need it */
1620        null.path = (char *)collide_path;
1621        oidcpy(&null.oid, &null_oid);
1622        null.mode = 0;
1623
1624        if (merge_mode_and_contents(opt, &null, a, b, collide_path,
1625                                    branch1, branch2, opt->call_depth * 2, &mfi))
1626                return -1;
1627        mfi.clean &= !alt_path;
1628        if (update_file(opt, mfi.clean, &mfi.blob, update_path))
1629                return -1;
1630        if (!mfi.clean && !opt->call_depth &&
1631            update_stages(opt, collide_path, NULL, a, b))
1632                return -1;
1633        free(alt_path);
1634        /*
1635         * FIXME: If both a & b both started with conflicts (only possible
1636         * if they came from a rename/rename(2to1)), but had IDENTICAL
1637         * contents including those conflicts, then in the next line we claim
1638         * it was clean.  If someone cares about this case, we should have the
1639         * caller notify us if we started with conflicts.
1640         */
1641        return mfi.clean;
1642}
1643
1644static int handle_rename_add(struct merge_options *opt,
1645                             struct rename_conflict_info *ci)
1646{
1647        /* a was renamed to c, and a separate c was added. */
1648        struct diff_filespec *a = ci->ren1->pair->one;
1649        struct diff_filespec *c = ci->ren1->pair->two;
1650        char *path = c->path;
1651        char *prev_path_desc;
1652        struct merge_file_info mfi;
1653
1654        const char *rename_branch = ci->ren1->branch;
1655        const char *add_branch = (opt->branch1 == rename_branch ?
1656                                  opt->branch2 : opt->branch1);
1657        int other_stage = (ci->ren1->branch == opt->branch1 ? 3 : 2);
1658
1659        output(opt, 1, _("CONFLICT (rename/add): "
1660               "Rename %s->%s in %s.  Added %s in %s"),
1661               a->path, c->path, rename_branch,
1662               c->path, add_branch);
1663
1664        prev_path_desc = xstrfmt("version of %s from %s", path, a->path);
1665        ci->ren1->src_entry->stages[other_stage].path = a->path;
1666        if (merge_mode_and_contents(opt, a, c,
1667                                    &ci->ren1->src_entry->stages[other_stage],
1668                                    prev_path_desc,
1669                                    opt->branch1, opt->branch2,
1670                                    1 + opt->call_depth * 2, &mfi))
1671                return -1;
1672        free(prev_path_desc);
1673
1674        ci->ren1->dst_entry->stages[other_stage].path = mfi.blob.path = c->path;
1675        return handle_file_collision(opt,
1676                                     c->path, a->path, NULL,
1677                                     rename_branch, add_branch,
1678                                     &mfi.blob,
1679                                     &ci->ren1->dst_entry->stages[other_stage]);
1680}
1681
1682static char *find_path_for_conflict(struct merge_options *opt,
1683                                    const char *path,
1684                                    const char *branch1,
1685                                    const char *branch2)
1686{
1687        char *new_path = NULL;
1688        if (dir_in_way(opt->repo->index, path, !opt->call_depth, 0)) {
1689                new_path = unique_path(opt, path, branch1);
1690                output(opt, 1, _("%s is a directory in %s adding "
1691                               "as %s instead"),
1692                       path, branch2, new_path);
1693        } else if (would_lose_untracked(opt, path)) {
1694                new_path = unique_path(opt, path, branch1);
1695                output(opt, 1, _("Refusing to lose untracked file"
1696                               " at %s; adding as %s instead"),
1697                       path, new_path);
1698        }
1699
1700        return new_path;
1701}
1702
1703static int handle_rename_rename_1to2(struct merge_options *opt,
1704                                     struct rename_conflict_info *ci)
1705{
1706        /* One file was renamed in both branches, but to different names. */
1707        struct merge_file_info mfi;
1708        struct diff_filespec *add;
1709        struct diff_filespec *o = ci->ren1->pair->one;
1710        struct diff_filespec *a = ci->ren1->pair->two;
1711        struct diff_filespec *b = ci->ren2->pair->two;
1712        char *path_desc;
1713
1714        output(opt, 1, _("CONFLICT (rename/rename): "
1715               "Rename \"%s\"->\"%s\" in branch \"%s\" "
1716               "rename \"%s\"->\"%s\" in \"%s\"%s"),
1717               o->path, a->path, ci->ren1->branch,
1718               o->path, b->path, ci->ren2->branch,
1719               opt->call_depth ? _(" (left unresolved)") : "");
1720
1721        path_desc = xstrfmt("%s and %s, both renamed from %s",
1722                            a->path, b->path, o->path);
1723        if (merge_mode_and_contents(opt, o, a, b, path_desc,
1724                                    ci->ren1->branch, ci->ren2->branch,
1725                                    opt->call_depth * 2, &mfi))
1726                return -1;
1727        free(path_desc);
1728
1729        if (opt->call_depth) {
1730                /*
1731                 * FIXME: For rename/add-source conflicts (if we could detect
1732                 * such), this is wrong.  We should instead find a unique
1733                 * pathname and then either rename the add-source file to that
1734                 * unique path, or use that unique path instead of src here.
1735                 */
1736                if (update_file(opt, 0, &mfi.blob, o->path))
1737                        return -1;
1738
1739                /*
1740                 * Above, we put the merged content at the merge-base's
1741                 * path.  Now we usually need to delete both a->path and
1742                 * b->path.  However, the rename on each side of the merge
1743                 * could also be involved in a rename/add conflict.  In
1744                 * such cases, we should keep the added file around,
1745                 * resolving the conflict at that path in its favor.
1746                 */
1747                add = &ci->ren1->dst_entry->stages[2 ^ 1];
1748                if (is_valid(add)) {
1749                        if (update_file(opt, 0, add, a->path))
1750                                return -1;
1751                }
1752                else
1753                        remove_file_from_index(opt->repo->index, a->path);
1754                add = &ci->ren2->dst_entry->stages[3 ^ 1];
1755                if (is_valid(add)) {
1756                        if (update_file(opt, 0, add, b->path))
1757                                return -1;
1758                }
1759                else
1760                        remove_file_from_index(opt->repo->index, b->path);
1761        } else {
1762                /*
1763                 * For each destination path, we need to see if there is a
1764                 * rename/add collision.  If not, we can write the file out
1765                 * to the specified location.
1766                 */
1767                add = &ci->ren1->dst_entry->stages[2 ^ 1];
1768                if (is_valid(add)) {
1769                        add->path = mfi.blob.path = a->path;
1770                        if (handle_file_collision(opt, a->path,
1771                                                  NULL, NULL,
1772                                                  ci->ren1->branch,
1773                                                  ci->ren2->branch,
1774                                                  &mfi.blob, add) < 0)
1775                                return -1;
1776                } else {
1777                        char *new_path = find_path_for_conflict(opt, a->path,
1778                                                                ci->ren1->branch,
1779                                                                ci->ren2->branch);
1780                        if (update_file(opt, 0, &mfi.blob,
1781                                        new_path ? new_path : a->path))
1782                                return -1;
1783                        free(new_path);
1784                        if (update_stages(opt, a->path, NULL, a, NULL))
1785                                return -1;
1786                }
1787
1788                add = &ci->ren2->dst_entry->stages[3 ^ 1];
1789                if (is_valid(add)) {
1790                        add->path = mfi.blob.path = b->path;
1791                        if (handle_file_collision(opt, b->path,
1792                                                  NULL, NULL,
1793                                                  ci->ren1->branch,
1794                                                  ci->ren2->branch,
1795                                                  add, &mfi.blob) < 0)
1796                                return -1;
1797                } else {
1798                        char *new_path = find_path_for_conflict(opt, b->path,
1799                                                                ci->ren2->branch,
1800                                                                ci->ren1->branch);
1801                        if (update_file(opt, 0, &mfi.blob,
1802                                        new_path ? new_path : b->path))
1803                                return -1;
1804                        free(new_path);
1805                        if (update_stages(opt, b->path, NULL, NULL, b))
1806                                return -1;
1807                }
1808        }
1809
1810        return 0;
1811}
1812
1813static int handle_rename_rename_2to1(struct merge_options *opt,
1814                                     struct rename_conflict_info *ci)
1815{
1816        /* Two files, a & b, were renamed to the same thing, c. */
1817        struct diff_filespec *a = ci->ren1->pair->one;
1818        struct diff_filespec *b = ci->ren2->pair->one;
1819        struct diff_filespec *c1 = ci->ren1->pair->two;
1820        struct diff_filespec *c2 = ci->ren2->pair->two;
1821        char *path = c1->path; /* == c2->path */
1822        char *path_side_1_desc;
1823        char *path_side_2_desc;
1824        struct merge_file_info mfi_c1;
1825        struct merge_file_info mfi_c2;
1826        int ostage1, ostage2;
1827
1828        output(opt, 1, _("CONFLICT (rename/rename): "
1829               "Rename %s->%s in %s. "
1830               "Rename %s->%s in %s"),
1831               a->path, c1->path, ci->ren1->branch,
1832               b->path, c2->path, ci->ren2->branch);
1833
1834        path_side_1_desc = xstrfmt("version of %s from %s", path, a->path);
1835        path_side_2_desc = xstrfmt("version of %s from %s", path, b->path);
1836        ostage1 = ci->ren1->branch == opt->branch1 ? 3 : 2;
1837        ostage2 = ostage1 ^ 1;
1838        ci->ren1->src_entry->stages[ostage1].path = a->path;
1839        ci->ren2->src_entry->stages[ostage2].path = b->path;
1840        if (merge_mode_and_contents(opt, a, c1,
1841                                    &ci->ren1->src_entry->stages[ostage1],
1842                                    path_side_1_desc,
1843                                    opt->branch1, opt->branch2,
1844                                    1 + opt->call_depth * 2, &mfi_c1) ||
1845            merge_mode_and_contents(opt, b,
1846                                    &ci->ren2->src_entry->stages[ostage2],
1847                                    c2, path_side_2_desc,
1848                                    opt->branch1, opt->branch2,
1849                                    1 + opt->call_depth * 2, &mfi_c2))
1850                return -1;
1851        free(path_side_1_desc);
1852        free(path_side_2_desc);
1853        mfi_c1.blob.path = path;
1854        mfi_c2.blob.path = path;
1855
1856        return handle_file_collision(opt, path, a->path, b->path,
1857                                     ci->ren1->branch, ci->ren2->branch,
1858                                     &mfi_c1.blob, &mfi_c2.blob);
1859}
1860
1861/*
1862 * Get the diff_filepairs changed between o_tree and tree.
1863 */
1864static struct diff_queue_struct *get_diffpairs(struct merge_options *opt,
1865                                               struct tree *o_tree,
1866                                               struct tree *tree)
1867{
1868        struct diff_queue_struct *ret;
1869        struct diff_options opts;
1870
1871        repo_diff_setup(opt->repo, &opts);
1872        opts.flags.recursive = 1;
1873        opts.flags.rename_empty = 0;
1874        opts.detect_rename = merge_detect_rename(opt);
1875        /*
1876         * We do not have logic to handle the detection of copies.  In
1877         * fact, it may not even make sense to add such logic: would we
1878         * really want a change to a base file to be propagated through
1879         * multiple other files by a merge?
1880         */
1881        if (opts.detect_rename > DIFF_DETECT_RENAME)
1882                opts.detect_rename = DIFF_DETECT_RENAME;
1883        opts.rename_limit = opt->merge_rename_limit >= 0 ? opt->merge_rename_limit :
1884                            opt->diff_rename_limit >= 0 ? opt->diff_rename_limit :
1885                            1000;
1886        opts.rename_score = opt->rename_score;
1887        opts.show_rename_progress = opt->show_rename_progress;
1888        opts.output_format = DIFF_FORMAT_NO_OUTPUT;
1889        diff_setup_done(&opts);
1890        diff_tree_oid(&o_tree->object.oid, &tree->object.oid, "", &opts);
1891        diffcore_std(&opts);
1892        if (opts.needed_rename_limit > opt->needed_rename_limit)
1893                opt->needed_rename_limit = opts.needed_rename_limit;
1894
1895        ret = xmalloc(sizeof(*ret));
1896        *ret = diff_queued_diff;
1897
1898        opts.output_format = DIFF_FORMAT_NO_OUTPUT;
1899        diff_queued_diff.nr = 0;
1900        diff_queued_diff.queue = NULL;
1901        diff_flush(&opts);
1902        return ret;
1903}
1904
1905static int tree_has_path(struct repository *r, struct tree *tree,
1906                         const char *path)
1907{
1908        struct object_id hashy;
1909        unsigned short mode_o;
1910
1911        return !get_tree_entry(r,
1912                               &tree->object.oid, path,
1913                               &hashy, &mode_o);
1914}
1915
1916/*
1917 * Return a new string that replaces the beginning portion (which matches
1918 * entry->dir), with entry->new_dir.  In perl-speak:
1919 *   new_path_name = (old_path =~ s/entry->dir/entry->new_dir/);
1920 * NOTE:
1921 *   Caller must ensure that old_path starts with entry->dir + '/'.
1922 */
1923static char *apply_dir_rename(struct dir_rename_entry *entry,
1924                              const char *old_path)
1925{
1926        struct strbuf new_path = STRBUF_INIT;
1927        int oldlen, newlen;
1928
1929        if (entry->non_unique_new_dir)
1930                return NULL;
1931
1932        oldlen = strlen(entry->dir);
1933        newlen = entry->new_dir.len + (strlen(old_path) - oldlen) + 1;
1934        strbuf_grow(&new_path, newlen);
1935        strbuf_addbuf(&new_path, &entry->new_dir);
1936        strbuf_addstr(&new_path, &old_path[oldlen]);
1937
1938        return strbuf_detach(&new_path, NULL);
1939}
1940
1941static void get_renamed_dir_portion(const char *old_path, const char *new_path,
1942                                    char **old_dir, char **new_dir)
1943{
1944        char *end_of_old, *end_of_new;
1945        int old_len, new_len;
1946
1947        *old_dir = NULL;
1948        *new_dir = NULL;
1949
1950        /*
1951         * For
1952         *    "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"
1953         * the "e/foo.c" part is the same, we just want to know that
1954         *    "a/b/c/d" was renamed to "a/b/some/thing/else"
1955         * so, for this example, this function returns "a/b/c/d" in
1956         * *old_dir and "a/b/some/thing/else" in *new_dir.
1957         *
1958         * Also, if the basename of the file changed, we don't care.  We
1959         * want to know which portion of the directory, if any, changed.
1960         */
1961        end_of_old = strrchr(old_path, '/');
1962        end_of_new = strrchr(new_path, '/');
1963
1964        if (end_of_old == NULL || end_of_new == NULL)
1965                return;
1966        while (*--end_of_new == *--end_of_old &&
1967               end_of_old != old_path &&
1968               end_of_new != new_path)
1969                ; /* Do nothing; all in the while loop */
1970        /*
1971         * We've found the first non-matching character in the directory
1972         * paths.  That means the current directory we were comparing
1973         * represents the rename.  Move end_of_old and end_of_new back
1974         * to the full directory name.
1975         */
1976        if (*end_of_old == '/')
1977                end_of_old++;
1978        if (*end_of_old != '/')
1979                end_of_new++;
1980        end_of_old = strchr(end_of_old, '/');
1981        end_of_new = strchr(end_of_new, '/');
1982
1983        /*
1984         * It may have been the case that old_path and new_path were the same
1985         * directory all along.  Don't claim a rename if they're the same.
1986         */
1987        old_len = end_of_old - old_path;
1988        new_len = end_of_new - new_path;
1989
1990        if (old_len != new_len || strncmp(old_path, new_path, old_len)) {
1991                *old_dir = xstrndup(old_path, old_len);
1992                *new_dir = xstrndup(new_path, new_len);
1993        }
1994}
1995
1996static void remove_hashmap_entries(struct hashmap *dir_renames,
1997                                   struct string_list *items_to_remove)
1998{
1999        int i;
2000        struct dir_rename_entry *entry;
2001
2002        for (i = 0; i < items_to_remove->nr; i++) {
2003                entry = items_to_remove->items[i].util;
2004                hashmap_remove(dir_renames, entry, NULL);
2005        }
2006        string_list_clear(items_to_remove, 0);
2007}
2008
2009/*
2010 * See if there is a directory rename for path, and if there are any file
2011 * level conflicts for the renamed location.  If there is a rename and
2012 * there are no conflicts, return the new name.  Otherwise, return NULL.
2013 */
2014static char *handle_path_level_conflicts(struct merge_options *opt,
2015                                         const char *path,
2016                                         struct dir_rename_entry *entry,
2017                                         struct hashmap *collisions,
2018                                         struct tree *tree)
2019{
2020        char *new_path = NULL;
2021        struct collision_entry *collision_ent;
2022        int clean = 1;
2023        struct strbuf collision_paths = STRBUF_INIT;
2024
2025        /*
2026         * entry has the mapping of old directory name to new directory name
2027         * that we want to apply to path.
2028         */
2029        new_path = apply_dir_rename(entry, path);
2030
2031        if (!new_path) {
2032                /* This should only happen when entry->non_unique_new_dir set */
2033                if (!entry->non_unique_new_dir)
2034                        BUG("entry->non_unqiue_dir not set and !new_path");
2035                output(opt, 1, _("CONFLICT (directory rename split): "
2036                               "Unclear where to place %s because directory "
2037                               "%s was renamed to multiple other directories, "
2038                               "with no destination getting a majority of the "
2039                               "files."),
2040                       path, entry->dir);
2041                clean = 0;
2042                return NULL;
2043        }
2044
2045        /*
2046         * The caller needs to have ensured that it has pre-populated
2047         * collisions with all paths that map to new_path.  Do a quick check
2048         * to ensure that's the case.
2049         */
2050        collision_ent = collision_find_entry(collisions, new_path);
2051        if (collision_ent == NULL)
2052                BUG("collision_ent is NULL");
2053
2054        /*
2055         * Check for one-sided add/add/.../add conflicts, i.e.
2056         * where implicit renames from the other side doing
2057         * directory rename(s) can affect this side of history
2058         * to put multiple paths into the same location.  Warn
2059         * and bail on directory renames for such paths.
2060         */
2061        if (collision_ent->reported_already) {
2062                clean = 0;
2063        } else if (tree_has_path(opt->repo, tree, new_path)) {
2064                collision_ent->reported_already = 1;
2065                strbuf_add_separated_string_list(&collision_paths, ", ",
2066                                                 &collision_ent->source_files);
2067                output(opt, 1, _("CONFLICT (implicit dir rename): Existing "
2068                               "file/dir at %s in the way of implicit "
2069                               "directory rename(s) putting the following "
2070                               "path(s) there: %s."),
2071                       new_path, collision_paths.buf);
2072                clean = 0;
2073        } else if (collision_ent->source_files.nr > 1) {
2074                collision_ent->reported_already = 1;
2075                strbuf_add_separated_string_list(&collision_paths, ", ",
2076                                                 &collision_ent->source_files);
2077                output(opt, 1, _("CONFLICT (implicit dir rename): Cannot map "
2078                               "more than one path to %s; implicit directory "
2079                               "renames tried to put these paths there: %s"),
2080                       new_path, collision_paths.buf);
2081                clean = 0;
2082        }
2083
2084        /* Free memory we no longer need */
2085        strbuf_release(&collision_paths);
2086        if (!clean && new_path) {
2087                free(new_path);
2088                return NULL;
2089        }
2090
2091        return new_path;
2092}
2093
2094/*
2095 * There are a couple things we want to do at the directory level:
2096 *   1. Check for both sides renaming to the same thing, in order to avoid
2097 *      implicit renaming of files that should be left in place.  (See
2098 *      testcase 6b in t6043 for details.)
2099 *   2. Prune directory renames if there are still files left in the
2100 *      the original directory.  These represent a partial directory rename,
2101 *      i.e. a rename where only some of the files within the directory
2102 *      were renamed elsewhere.  (Technically, this could be done earlier
2103 *      in get_directory_renames(), except that would prevent us from
2104 *      doing the previous check and thus failing testcase 6b.)
2105 *   3. Check for rename/rename(1to2) conflicts (at the directory level).
2106 *      In the future, we could potentially record this info as well and
2107 *      omit reporting rename/rename(1to2) conflicts for each path within
2108 *      the affected directories, thus cleaning up the merge output.
2109 *   NOTE: We do NOT check for rename/rename(2to1) conflicts at the
2110 *         directory level, because merging directories is fine.  If it
2111 *         causes conflicts for files within those merged directories, then
2112 *         that should be detected at the individual path level.
2113 */
2114static void handle_directory_level_conflicts(struct merge_options *opt,
2115                                             struct hashmap *dir_re_head,
2116                                             struct tree *head,
2117                                             struct hashmap *dir_re_merge,
2118                                             struct tree *merge)
2119{
2120        struct hashmap_iter iter;
2121        struct dir_rename_entry *head_ent;
2122        struct dir_rename_entry *merge_ent;
2123
2124        struct string_list remove_from_head = STRING_LIST_INIT_NODUP;
2125        struct string_list remove_from_merge = STRING_LIST_INIT_NODUP;
2126
2127        hashmap_iter_init(dir_re_head, &iter);
2128        while ((head_ent = hashmap_iter_next(&iter))) {
2129                merge_ent = dir_rename_find_entry(dir_re_merge, head_ent->dir);
2130                if (merge_ent &&
2131                    !head_ent->non_unique_new_dir &&
2132                    !merge_ent->non_unique_new_dir &&
2133                    !strbuf_cmp(&head_ent->new_dir, &merge_ent->new_dir)) {
2134                        /* 1. Renamed identically; remove it from both sides */
2135                        string_list_append(&remove_from_head,
2136                                           head_ent->dir)->util = head_ent;
2137                        strbuf_release(&head_ent->new_dir);
2138                        string_list_append(&remove_from_merge,
2139                                           merge_ent->dir)->util = merge_ent;
2140                        strbuf_release(&merge_ent->new_dir);
2141                } else if (tree_has_path(opt->repo, head, head_ent->dir)) {
2142                        /* 2. This wasn't a directory rename after all */
2143                        string_list_append(&remove_from_head,
2144                                           head_ent->dir)->util = head_ent;
2145                        strbuf_release(&head_ent->new_dir);
2146                }
2147        }
2148
2149        remove_hashmap_entries(dir_re_head, &remove_from_head);
2150        remove_hashmap_entries(dir_re_merge, &remove_from_merge);
2151
2152        hashmap_iter_init(dir_re_merge, &iter);
2153        while ((merge_ent = hashmap_iter_next(&iter))) {
2154                head_ent = dir_rename_find_entry(dir_re_head, merge_ent->dir);
2155                if (tree_has_path(opt->repo, merge, merge_ent->dir)) {
2156                        /* 2. This wasn't a directory rename after all */
2157                        string_list_append(&remove_from_merge,
2158                                           merge_ent->dir)->util = merge_ent;
2159                } else if (head_ent &&
2160                           !head_ent->non_unique_new_dir &&
2161                           !merge_ent->non_unique_new_dir) {
2162                        /* 3. rename/rename(1to2) */
2163                        /*
2164                         * We can assume it's not rename/rename(1to1) because
2165                         * that was case (1), already checked above.  So we
2166                         * know that head_ent->new_dir and merge_ent->new_dir
2167                         * are different strings.
2168                         */
2169                        output(opt, 1, _("CONFLICT (rename/rename): "
2170                                       "Rename directory %s->%s in %s. "
2171                                       "Rename directory %s->%s in %s"),
2172                               head_ent->dir, head_ent->new_dir.buf, opt->branch1,
2173                               head_ent->dir, merge_ent->new_dir.buf, opt->branch2);
2174                        string_list_append(&remove_from_head,
2175                                           head_ent->dir)->util = head_ent;
2176                        strbuf_release(&head_ent->new_dir);
2177                        string_list_append(&remove_from_merge,
2178                                           merge_ent->dir)->util = merge_ent;
2179                        strbuf_release(&merge_ent->new_dir);
2180                }
2181        }
2182
2183        remove_hashmap_entries(dir_re_head, &remove_from_head);
2184        remove_hashmap_entries(dir_re_merge, &remove_from_merge);
2185}
2186
2187static struct hashmap *get_directory_renames(struct diff_queue_struct *pairs)
2188{
2189        struct hashmap *dir_renames;
2190        struct hashmap_iter iter;
2191        struct dir_rename_entry *entry;
2192        int i;
2193
2194        /*
2195         * Typically, we think of a directory rename as all files from a
2196         * certain directory being moved to a target directory.  However,
2197         * what if someone first moved two files from the original
2198         * directory in one commit, and then renamed the directory
2199         * somewhere else in a later commit?  At merge time, we just know
2200         * that files from the original directory went to two different
2201         * places, and that the bulk of them ended up in the same place.
2202         * We want each directory rename to represent where the bulk of the
2203         * files from that directory end up; this function exists to find
2204         * where the bulk of the files went.
2205         *
2206         * The first loop below simply iterates through the list of file
2207         * renames, finding out how often each directory rename pair
2208         * possibility occurs.
2209         */
2210        dir_renames = xmalloc(sizeof(*dir_renames));
2211        dir_rename_init(dir_renames);
2212        for (i = 0; i < pairs->nr; ++i) {
2213                struct string_list_item *item;
2214                int *count;
2215                struct diff_filepair *pair = pairs->queue[i];
2216                char *old_dir, *new_dir;
2217
2218                /* File not part of directory rename if it wasn't renamed */
2219                if (pair->status != 'R')
2220                        continue;
2221
2222                get_renamed_dir_portion(pair->one->path, pair->two->path,
2223                                        &old_dir,        &new_dir);
2224                if (!old_dir)
2225                        /* Directory didn't change at all; ignore this one. */
2226                        continue;
2227
2228                entry = dir_rename_find_entry(dir_renames, old_dir);
2229                if (!entry) {
2230                        entry = xmalloc(sizeof(*entry));
2231                        dir_rename_entry_init(entry, old_dir);
2232                        hashmap_put(dir_renames, entry);
2233                } else {
2234                        free(old_dir);
2235                }
2236                item = string_list_lookup(&entry->possible_new_dirs, new_dir);
2237                if (!item) {
2238                        item = string_list_insert(&entry->possible_new_dirs,
2239                                                  new_dir);
2240                        item->util = xcalloc(1, sizeof(int));
2241                } else {
2242                        free(new_dir);
2243                }
2244                count = item->util;
2245                *count += 1;
2246        }
2247
2248        /*
2249         * For each directory with files moved out of it, we find out which
2250         * target directory received the most files so we can declare it to
2251         * be the "winning" target location for the directory rename.  This
2252         * winner gets recorded in new_dir.  If there is no winner
2253         * (multiple target directories received the same number of files),
2254         * we set non_unique_new_dir.  Once we've determined the winner (or
2255         * that there is no winner), we no longer need possible_new_dirs.
2256         */
2257        hashmap_iter_init(dir_renames, &iter);
2258        while ((entry = hashmap_iter_next(&iter))) {
2259                int max = 0;
2260                int bad_max = 0;
2261                char *best = NULL;
2262
2263                for (i = 0; i < entry->possible_new_dirs.nr; i++) {
2264                        int *count = entry->possible_new_dirs.items[i].util;
2265
2266                        if (*count == max)
2267                                bad_max = max;
2268                        else if (*count > max) {
2269                                max = *count;
2270                                best = entry->possible_new_dirs.items[i].string;
2271                        }
2272                }
2273                if (bad_max == max)
2274                        entry->non_unique_new_dir = 1;
2275                else {
2276                        assert(entry->new_dir.len == 0);
2277                        strbuf_addstr(&entry->new_dir, best);
2278                }
2279                /*
2280                 * The relevant directory sub-portion of the original full
2281                 * filepaths were xstrndup'ed before inserting into
2282                 * possible_new_dirs, and instead of manually iterating the
2283                 * list and free'ing each, just lie and tell
2284                 * possible_new_dirs that it did the strdup'ing so that it
2285                 * will free them for us.
2286                 */
2287                entry->possible_new_dirs.strdup_strings = 1;
2288                string_list_clear(&entry->possible_new_dirs, 1);
2289        }
2290
2291        return dir_renames;
2292}
2293
2294static struct dir_rename_entry *check_dir_renamed(const char *path,
2295                                                  struct hashmap *dir_renames)
2296{
2297        char *temp = xstrdup(path);
2298        char *end;
2299        struct dir_rename_entry *entry = NULL;
2300
2301        while ((end = strrchr(temp, '/'))) {
2302                *end = '\0';
2303                entry = dir_rename_find_entry(dir_renames, temp);
2304                if (entry)
2305                        break;
2306        }
2307        free(temp);
2308        return entry;
2309}
2310
2311static void compute_collisions(struct hashmap *collisions,
2312                               struct hashmap *dir_renames,
2313                               struct diff_queue_struct *pairs)
2314{
2315        int i;
2316
2317        /*
2318         * Multiple files can be mapped to the same path due to directory
2319         * renames done by the other side of history.  Since that other
2320         * side of history could have merged multiple directories into one,
2321         * if our side of history added the same file basename to each of
2322         * those directories, then all N of them would get implicitly
2323         * renamed by the directory rename detection into the same path,
2324         * and we'd get an add/add/.../add conflict, and all those adds
2325         * from *this* side of history.  This is not representable in the
2326         * index, and users aren't going to easily be able to make sense of
2327         * it.  So we need to provide a good warning about what's
2328         * happening, and fall back to no-directory-rename detection
2329         * behavior for those paths.
2330         *
2331         * See testcases 9e and all of section 5 from t6043 for examples.
2332         */
2333        collision_init(collisions);
2334
2335        for (i = 0; i < pairs->nr; ++i) {
2336                struct dir_rename_entry *dir_rename_ent;
2337                struct collision_entry *collision_ent;
2338                char *new_path;
2339                struct diff_filepair *pair = pairs->queue[i];
2340
2341                if (pair->status != 'A' && pair->status != 'R')
2342                        continue;
2343                dir_rename_ent = check_dir_renamed(pair->two->path,
2344                                                   dir_renames);
2345                if (!dir_rename_ent)
2346                        continue;
2347
2348                new_path = apply_dir_rename(dir_rename_ent, pair->two->path);
2349                if (!new_path)
2350                        /*
2351                         * dir_rename_ent->non_unique_new_path is true, which
2352                         * means there is no directory rename for us to use,
2353                         * which means it won't cause us any additional
2354                         * collisions.
2355                         */
2356                        continue;
2357                collision_ent = collision_find_entry(collisions, new_path);
2358                if (!collision_ent) {
2359                        collision_ent = xcalloc(1,
2360                                                sizeof(struct collision_entry));
2361                        hashmap_entry_init(collision_ent, strhash(new_path));
2362                        hashmap_put(collisions, collision_ent);
2363                        collision_ent->target_file = new_path;
2364                } else {
2365                        free(new_path);
2366                }
2367                string_list_insert(&collision_ent->source_files,
2368                                   pair->two->path);
2369        }
2370}
2371
2372static char *check_for_directory_rename(struct merge_options *opt,
2373                                        const char *path,
2374                                        struct tree *tree,
2375                                        struct hashmap *dir_renames,
2376                                        struct hashmap *dir_rename_exclusions,
2377                                        struct hashmap *collisions,
2378                                        int *clean_merge)
2379{
2380        char *new_path = NULL;
2381        struct dir_rename_entry *entry = check_dir_renamed(path, dir_renames);
2382        struct dir_rename_entry *oentry = NULL;
2383
2384        if (!entry)
2385                return new_path;
2386
2387        /*
2388         * This next part is a little weird.  We do not want to do an
2389         * implicit rename into a directory we renamed on our side, because
2390         * that will result in a spurious rename/rename(1to2) conflict.  An
2391         * example:
2392         *   Base commit: dumbdir/afile, otherdir/bfile
2393         *   Side 1:      smrtdir/afile, otherdir/bfile
2394         *   Side 2:      dumbdir/afile, dumbdir/bfile
2395         * Here, while working on Side 1, we could notice that otherdir was
2396         * renamed/merged to dumbdir, and change the diff_filepair for
2397         * otherdir/bfile into a rename into dumbdir/bfile.  However, Side
2398         * 2 will notice the rename from dumbdir to smrtdir, and do the
2399         * transitive rename to move it from dumbdir/bfile to
2400         * smrtdir/bfile.  That gives us bfile in dumbdir vs being in
2401         * smrtdir, a rename/rename(1to2) conflict.  We really just want
2402         * the file to end up in smrtdir.  And the way to achieve that is
2403         * to not let Side1 do the rename to dumbdir, since we know that is
2404         * the source of one of our directory renames.
2405         *
2406         * That's why oentry and dir_rename_exclusions is here.
2407         *
2408         * As it turns out, this also prevents N-way transient rename
2409         * confusion; See testcases 9c and 9d of t6043.
2410         */
2411        oentry = dir_rename_find_entry(dir_rename_exclusions, entry->new_dir.buf);
2412        if (oentry) {
2413                output(opt, 1, _("WARNING: Avoiding applying %s -> %s rename "
2414                               "to %s, because %s itself was renamed."),
2415                       entry->dir, entry->new_dir.buf, path, entry->new_dir.buf);
2416        } else {
2417                new_path = handle_path_level_conflicts(opt, path, entry,
2418                                                       collisions, tree);
2419                *clean_merge &= (new_path != NULL);
2420        }
2421
2422        return new_path;
2423}
2424
2425static void apply_directory_rename_modifications(struct merge_options *opt,
2426                                                 struct diff_filepair *pair,
2427                                                 char *new_path,
2428                                                 struct rename *re,
2429                                                 struct tree *tree,
2430                                                 struct tree *o_tree,
2431                                                 struct tree *a_tree,
2432                                                 struct tree *b_tree,
2433                                                 struct string_list *entries)
2434{
2435        struct string_list_item *item;
2436        int stage = (tree == a_tree ? 2 : 3);
2437        int update_wd;
2438
2439        /*
2440         * In all cases where we can do directory rename detection,
2441         * unpack_trees() will have read pair->two->path into the
2442         * index and the working copy.  We need to remove it so that
2443         * we can instead place it at new_path.  It is guaranteed to
2444         * not be untracked (unpack_trees() would have errored out
2445         * saying the file would have been overwritten), but it might
2446         * be dirty, though.
2447         */
2448        update_wd = !was_dirty(opt, pair->two->path);
2449        if (!update_wd)
2450                output(opt, 1, _("Refusing to lose dirty file at %s"),
2451                       pair->two->path);
2452        remove_file(opt, 1, pair->two->path, !update_wd);
2453
2454        /* Find or create a new re->dst_entry */
2455        item = string_list_lookup(entries, new_path);
2456        if (item) {
2457                /*
2458                 * Since we're renaming on this side of history, and it's
2459                 * due to a directory rename on the other side of history
2460                 * (which we only allow when the directory in question no
2461                 * longer exists on the other side of history), the
2462                 * original entry for re->dst_entry is no longer
2463                 * necessary...
2464                 */
2465                re->dst_entry->processed = 1;
2466
2467                /*
2468                 * ...because we'll be using this new one.
2469                 */
2470                re->dst_entry = item->util;
2471        } else {
2472                /*
2473                 * re->dst_entry is for the before-dir-rename path, and we
2474                 * need it to hold information for the after-dir-rename
2475                 * path.  Before creating a new entry, we need to mark the
2476                 * old one as unnecessary (...unless it is shared by
2477                 * src_entry, i.e. this didn't use to be a rename, in which
2478                 * case we can just allow the normal processing to happen
2479                 * for it).
2480                 */
2481                if (pair->status == 'R')
2482                        re->dst_entry->processed = 1;
2483
2484                re->dst_entry = insert_stage_data(opt->repo, new_path,
2485                                                  o_tree, a_tree, b_tree,
2486                                                  entries);
2487                item = string_list_insert(entries, new_path);
2488                item->util = re->dst_entry;
2489        }
2490
2491        /*
2492         * Update the stage_data with the information about the path we are
2493         * moving into place.  That slot will be empty and available for us
2494         * to write to because of the collision checks in
2495         * handle_path_level_conflicts().  In other words,
2496         * re->dst_entry->stages[stage].oid will be the null_oid, so it's
2497         * open for us to write to.
2498         *
2499         * It may be tempting to actually update the index at this point as
2500         * well, using update_stages_for_stage_data(), but as per the big
2501         * "NOTE" in update_stages(), doing so will modify the current
2502         * in-memory index which will break calls to would_lose_untracked()
2503         * that we need to make.  Instead, we need to just make sure that
2504         * the various handle_rename_*() functions update the index
2505         * explicitly rather than relying on unpack_trees() to have done it.
2506         */
2507        get_tree_entry(opt->repo,
2508                       &tree->object.oid,
2509                       pair->two->path,
2510                       &re->dst_entry->stages[stage].oid,
2511                       &re->dst_entry->stages[stage].mode);
2512
2513        /*
2514         * Record the original change status (or 'type' of change).  If it
2515         * was originally an add ('A'), this lets us differentiate later
2516         * between a RENAME_DELETE conflict and RENAME_VIA_DIR (they
2517         * otherwise look the same).  If it was originally a rename ('R'),
2518         * this lets us remember and report accurately about the transitive
2519         * renaming that occurred via the directory rename detection.  Also,
2520         * record the original destination name.
2521         */
2522        re->dir_rename_original_type = pair->status;
2523        re->dir_rename_original_dest = pair->two->path;
2524
2525        /*
2526         * We don't actually look at pair->status again, but it seems
2527         * pedagogically correct to adjust it.
2528         */
2529        pair->status = 'R';
2530
2531        /*
2532         * Finally, record the new location.
2533         */
2534        pair->two->path = new_path;
2535}
2536
2537/*
2538 * Get information of all renames which occurred in 'pairs', making use of
2539 * any implicit directory renames inferred from the other side of history.
2540 * We need the three trees in the merge ('o_tree', 'a_tree' and 'b_tree')
2541 * to be able to associate the correct cache entries with the rename
2542 * information; tree is always equal to either a_tree or b_tree.
2543 */
2544static struct string_list *get_renames(struct merge_options *opt,
2545                                       const char *branch,
2546                                       struct diff_queue_struct *pairs,
2547                                       struct hashmap *dir_renames,
2548                                       struct hashmap *dir_rename_exclusions,
2549                                       struct tree *tree,
2550                                       struct tree *o_tree,
2551                                       struct tree *a_tree,
2552                                       struct tree *b_tree,
2553                                       struct string_list *entries,
2554                                       int *clean_merge)
2555{
2556        int i;
2557        struct hashmap collisions;
2558        struct hashmap_iter iter;
2559        struct collision_entry *e;
2560        struct string_list *renames;
2561
2562        compute_collisions(&collisions, dir_renames, pairs);
2563        renames = xcalloc(1, sizeof(struct string_list));
2564
2565        for (i = 0; i < pairs->nr; ++i) {
2566                struct string_list_item *item;
2567                struct rename *re;
2568                struct diff_filepair *pair = pairs->queue[i];
2569                char *new_path; /* non-NULL only with directory renames */
2570
2571                if (pair->status != 'A' && pair->status != 'R') {
2572                        diff_free_filepair(pair);
2573                        continue;
2574                }
2575                new_path = check_for_directory_rename(opt, pair->two->path, tree,
2576                                                      dir_renames,
2577                                                      dir_rename_exclusions,
2578                                                      &collisions,
2579                                                      clean_merge);
2580                if (pair->status != 'R' && !new_path) {
2581                        diff_free_filepair(pair);
2582                        continue;
2583                }
2584
2585                re = xmalloc(sizeof(*re));
2586                re->processed = 0;
2587                re->pair = pair;
2588                re->branch = branch;
2589                re->dir_rename_original_type = '\0';
2590                re->dir_rename_original_dest = NULL;
2591                item = string_list_lookup(entries, re->pair->one->path);
2592                if (!item)
2593                        re->src_entry = insert_stage_data(opt->repo,
2594                                        re->pair->one->path,
2595                                        o_tree, a_tree, b_tree, entries);
2596                else
2597                        re->src_entry = item->util;
2598
2599                item = string_list_lookup(entries, re->pair->two->path);
2600                if (!item)
2601                        re->dst_entry = insert_stage_data(opt->repo,
2602                                        re->pair->two->path,
2603                                        o_tree, a_tree, b_tree, entries);
2604                else
2605                        re->dst_entry = item->util;
2606                item = string_list_insert(renames, pair->one->path);
2607                item->util = re;
2608                if (new_path)
2609                        apply_directory_rename_modifications(opt, pair, new_path,
2610                                                             re, tree, o_tree,
2611                                                             a_tree, b_tree,
2612                                                             entries);
2613        }
2614
2615        hashmap_iter_init(&collisions, &iter);
2616        while ((e = hashmap_iter_next(&iter))) {
2617                free(e->target_file);
2618                string_list_clear(&e->source_files, 0);
2619        }
2620        hashmap_free(&collisions, 1);
2621        return renames;
2622}
2623
2624static int process_renames(struct merge_options *opt,
2625                           struct string_list *a_renames,
2626                           struct string_list *b_renames)
2627{
2628        int clean_merge = 1, i, j;
2629        struct string_list a_by_dst = STRING_LIST_INIT_NODUP;
2630        struct string_list b_by_dst = STRING_LIST_INIT_NODUP;
2631        const struct rename *sre;
2632
2633        for (i = 0; i < a_renames->nr; i++) {
2634                sre = a_renames->items[i].util;
2635                string_list_insert(&a_by_dst, sre->pair->two->path)->util
2636                        = (void *)sre;
2637        }
2638        for (i = 0; i < b_renames->nr; i++) {
2639                sre = b_renames->items[i].util;
2640                string_list_insert(&b_by_dst, sre->pair->two->path)->util
2641                        = (void *)sre;
2642        }
2643
2644        for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {
2645                struct string_list *renames1, *renames2Dst;
2646                struct rename *ren1 = NULL, *ren2 = NULL;
2647                const char *ren1_src, *ren1_dst;
2648                struct string_list_item *lookup;
2649
2650                if (i >= a_renames->nr) {
2651                        ren2 = b_renames->items[j++].util;
2652                } else if (j >= b_renames->nr) {
2653                        ren1 = a_renames->items[i++].util;
2654                } else {
2655                        int compare = strcmp(a_renames->items[i].string,
2656                                             b_renames->items[j].string);
2657                        if (compare <= 0)
2658                                ren1 = a_renames->items[i++].util;
2659                        if (compare >= 0)
2660                                ren2 = b_renames->items[j++].util;
2661                }
2662
2663                /* TODO: refactor, so that 1/2 are not needed */
2664                if (ren1) {
2665                        renames1 = a_renames;
2666                        renames2Dst = &b_by_dst;
2667                } else {
2668                        renames1 = b_renames;
2669                        renames2Dst = &a_by_dst;
2670                        SWAP(ren2, ren1);
2671                }
2672
2673                if (ren1->processed)
2674                        continue;
2675                ren1->processed = 1;
2676                ren1->dst_entry->processed = 1;
2677                /* BUG: We should only mark src_entry as processed if we
2678                 * are not dealing with a rename + add-source case.
2679                 */
2680                ren1->src_entry->processed = 1;
2681
2682                ren1_src = ren1->pair->one->path;
2683                ren1_dst = ren1->pair->two->path;
2684
2685                if (ren2) {
2686                        /* One file renamed on both sides */
2687                        const char *ren2_src = ren2->pair->one->path;
2688                        const char *ren2_dst = ren2->pair->two->path;
2689                        enum rename_type rename_type;
2690                        if (strcmp(ren1_src, ren2_src) != 0)
2691                                BUG("ren1_src != ren2_src");
2692                        ren2->dst_entry->processed = 1;
2693                        ren2->processed = 1;
2694                        if (strcmp(ren1_dst, ren2_dst) != 0) {
2695                                rename_type = RENAME_ONE_FILE_TO_TWO;
2696                                clean_merge = 0;
2697                        } else {
2698                                rename_type = RENAME_ONE_FILE_TO_ONE;
2699                                /* BUG: We should only remove ren1_src in
2700                                 * the base stage (think of rename +
2701                                 * add-source cases).
2702                                 */
2703                                remove_file(opt, 1, ren1_src, 1);
2704                                update_entry(ren1->dst_entry,
2705                                             ren1->pair->one,
2706                                             ren1->pair->two,
2707                                             ren2->pair->two);
2708                        }
2709                        setup_rename_conflict_info(rename_type, opt, ren1, ren2);
2710                } else if ((lookup = string_list_lookup(renames2Dst, ren1_dst))) {
2711                        /* Two different files renamed to the same thing */
2712                        char *ren2_dst;
2713                        ren2 = lookup->util;
2714                        ren2_dst = ren2->pair->two->path;
2715                        if (strcmp(ren1_dst, ren2_dst) != 0)
2716                                BUG("ren1_dst != ren2_dst");
2717
2718                        clean_merge = 0;
2719                        ren2->processed = 1;
2720                        /*
2721                         * BUG: We should only mark src_entry as processed
2722                         * if we are not dealing with a rename + add-source
2723                         * case.
2724                         */
2725                        ren2->src_entry->processed = 1;
2726
2727                        setup_rename_conflict_info(RENAME_TWO_FILES_TO_ONE,
2728                                                   opt, ren1, ren2);
2729                } else {
2730                        /* Renamed in 1, maybe changed in 2 */
2731                        /* we only use sha1 and mode of these */
2732                        struct diff_filespec src_other, dst_other;
2733                        int try_merge;
2734
2735                        /*
2736                         * unpack_trees loads entries from common-commit
2737                         * into stage 1, from head-commit into stage 2, and
2738                         * from merge-commit into stage 3.  We keep track
2739                         * of which side corresponds to the rename.
2740                         */
2741                        int renamed_stage = a_renames == renames1 ? 2 : 3;
2742                        int other_stage =   a_renames == renames1 ? 3 : 2;
2743
2744                        /* BUG: We should only remove ren1_src in the base
2745                         * stage and in other_stage (think of rename +
2746                         * add-source case).
2747                         */
2748                        remove_file(opt, 1, ren1_src,
2749                                    renamed_stage == 2 || !was_tracked(opt, ren1_src));
2750
2751                        oidcpy(&src_other.oid,
2752                               &ren1->src_entry->stages[other_stage].oid);
2753                        src_other.mode = ren1->src_entry->stages[other_stage].mode;
2754                        oidcpy(&dst_other.oid,
2755                               &ren1->dst_entry->stages[other_stage].oid);
2756                        dst_other.mode = ren1->dst_entry->stages[other_stage].mode;
2757                        try_merge = 0;
2758
2759                        if (oid_eq(&src_other.oid, &null_oid) &&
2760                            ren1->dir_rename_original_type == 'A') {
2761                                setup_rename_conflict_info(RENAME_VIA_DIR,
2762                                                           opt, ren1, NULL);
2763                        } else if (oid_eq(&src_other.oid, &null_oid)) {
2764                                setup_rename_conflict_info(RENAME_DELETE,
2765                                                           opt, ren1, NULL);
2766                        } else if ((dst_other.mode == ren1->pair->two->mode) &&
2767                                   oid_eq(&dst_other.oid, &ren1->pair->two->oid)) {
2768                                /*
2769                                 * Added file on the other side identical to
2770                                 * the file being renamed: clean merge.
2771                                 * Also, there is no need to overwrite the
2772                                 * file already in the working copy, so call
2773                                 * update_file_flags() instead of
2774                                 * update_file().
2775                                 */
2776                                if (update_file_flags(opt,
2777                                                      ren1->pair->two,
2778                                                      ren1_dst,
2779                                                      1, /* update_cache */
2780                                                      0  /* update_wd    */))
2781                                        clean_merge = -1;
2782                        } else if (!oid_eq(&dst_other.oid, &null_oid)) {
2783                                /*
2784                                 * Probably not a clean merge, but it's
2785                                 * premature to set clean_merge to 0 here,
2786                                 * because if the rename merges cleanly and
2787                                 * the merge exactly matches the newly added
2788                                 * file, then the merge will be clean.
2789                                 */
2790                                setup_rename_conflict_info(RENAME_ADD,
2791                                                           opt, ren1, NULL);
2792                        } else
2793                                try_merge = 1;
2794
2795                        if (clean_merge < 0)
2796                                goto cleanup_and_return;
2797                        if (try_merge) {
2798                                struct diff_filespec *o, *a, *b;
2799                                src_other.path = (char *)ren1_src;
2800
2801                                o = ren1->pair->one;
2802                                if (a_renames == renames1) {
2803                                        a = ren1->pair->two;
2804                                        b = &src_other;
2805                                } else {
2806                                        b = ren1->pair->two;
2807                                        a = &src_other;
2808                                }
2809                                update_entry(ren1->dst_entry, o, a, b);
2810                                setup_rename_conflict_info(RENAME_NORMAL,
2811                                                           opt, ren1, NULL);
2812                        }
2813                }
2814        }
2815cleanup_and_return:
2816        string_list_clear(&a_by_dst, 0);
2817        string_list_clear(&b_by_dst, 0);
2818
2819        return clean_merge;
2820}
2821
2822struct rename_info {
2823        struct string_list *head_renames;
2824        struct string_list *merge_renames;
2825};
2826
2827static void initial_cleanup_rename(struct diff_queue_struct *pairs,
2828                                   struct hashmap *dir_renames)
2829{
2830        struct hashmap_iter iter;
2831        struct dir_rename_entry *e;
2832
2833        hashmap_iter_init(dir_renames, &iter);
2834        while ((e = hashmap_iter_next(&iter))) {
2835                free(e->dir);
2836                strbuf_release(&e->new_dir);
2837                /* possible_new_dirs already cleared in get_directory_renames */
2838        }
2839        hashmap_free(dir_renames, 1);
2840        free(dir_renames);
2841
2842        free(pairs->queue);
2843        free(pairs);
2844}
2845
2846static int detect_and_process_renames(struct merge_options *opt,
2847                                      struct tree *common,
2848                                      struct tree *head,
2849                                      struct tree *merge,
2850                                      struct string_list *entries,
2851                                      struct rename_info *ri)
2852{
2853        struct diff_queue_struct *head_pairs, *merge_pairs;
2854        struct hashmap *dir_re_head, *dir_re_merge;
2855        int clean = 1;
2856
2857        ri->head_renames = NULL;
2858        ri->merge_renames = NULL;
2859
2860        if (!merge_detect_rename(opt))
2861                return 1;
2862
2863        head_pairs = get_diffpairs(opt, common, head);
2864        merge_pairs = get_diffpairs(opt, common, merge);
2865
2866        if ((opt->detect_directory_renames == 2) ||
2867            (opt->detect_directory_renames == 1 && !opt->call_depth)) {
2868                dir_re_head = get_directory_renames(head_pairs);
2869                dir_re_merge = get_directory_renames(merge_pairs);
2870
2871                handle_directory_level_conflicts(opt,
2872                                                 dir_re_head, head,
2873                                                 dir_re_merge, merge);
2874        } else {
2875                dir_re_head  = xmalloc(sizeof(*dir_re_head));
2876                dir_re_merge = xmalloc(sizeof(*dir_re_merge));
2877                dir_rename_init(dir_re_head);
2878                dir_rename_init(dir_re_merge);
2879        }
2880
2881        ri->head_renames  = get_renames(opt, opt->branch1, head_pairs,
2882                                        dir_re_merge, dir_re_head, head,
2883                                        common, head, merge, entries,
2884                                        &clean);
2885        if (clean < 0)
2886                goto cleanup;
2887        ri->merge_renames = get_renames(opt, opt->branch2, merge_pairs,
2888                                        dir_re_head, dir_re_merge, merge,
2889                                        common, head, merge, entries,
2890                                        &clean);
2891        if (clean < 0)
2892                goto cleanup;
2893        clean &= process_renames(opt, ri->head_renames, ri->merge_renames);
2894
2895cleanup:
2896        /*
2897         * Some cleanup is deferred until cleanup_renames() because the
2898         * data structures are still needed and referenced in
2899         * process_entry().  But there are a few things we can free now.
2900         */
2901        initial_cleanup_rename(head_pairs, dir_re_head);
2902        initial_cleanup_rename(merge_pairs, dir_re_merge);
2903
2904        return clean;
2905}
2906
2907static void final_cleanup_rename(struct string_list *rename)
2908{
2909        const struct rename *re;
2910        int i;
2911
2912        if (rename == NULL)
2913                return;
2914
2915        for (i = 0; i < rename->nr; i++) {
2916                re = rename->items[i].util;
2917                diff_free_filepair(re->pair);
2918        }
2919        string_list_clear(rename, 1);
2920        free(rename);
2921}
2922
2923static void final_cleanup_renames(struct rename_info *re_info)
2924{
2925        final_cleanup_rename(re_info->head_renames);
2926        final_cleanup_rename(re_info->merge_renames);
2927}
2928
2929static int read_oid_strbuf(struct merge_options *opt,
2930                           const struct object_id *oid,
2931                           struct strbuf *dst)
2932{
2933        void *buf;
2934        enum object_type type;
2935        unsigned long size;
2936        buf = read_object_file(oid, &type, &size);
2937        if (!buf)
2938                return err(opt, _("cannot read object %s"), oid_to_hex(oid));
2939        if (type != OBJ_BLOB) {
2940                free(buf);
2941                return err(opt, _("object %s is not a blob"), oid_to_hex(oid));
2942        }
2943        strbuf_attach(dst, buf, size, size + 1);
2944        return 0;
2945}
2946
2947static int blob_unchanged(struct merge_options *opt,
2948                          const struct diff_filespec *o,
2949                          const struct diff_filespec *a,
2950                          int renormalize, const char *path)
2951{
2952        struct strbuf obuf = STRBUF_INIT;
2953        struct strbuf abuf = STRBUF_INIT;
2954        int ret = 0; /* assume changed for safety */
2955        const struct index_state *idx = opt->repo->index;
2956
2957        if (a->mode != o->mode)
2958                return 0;
2959        if (oid_eq(&o->oid, &a->oid))
2960                return 1;
2961        if (!renormalize)
2962                return 0;
2963
2964        if (read_oid_strbuf(opt, &o->oid, &obuf) ||
2965            read_oid_strbuf(opt, &a->oid, &abuf))
2966                goto error_return;
2967        /*
2968         * Note: binary | is used so that both renormalizations are
2969         * performed.  Comparison can be skipped if both files are
2970         * unchanged since their sha1s have already been compared.
2971         */
2972        if (renormalize_buffer(idx, path, obuf.buf, obuf.len, &obuf) |
2973            renormalize_buffer(idx, path, abuf.buf, abuf.len, &abuf))
2974                ret = (obuf.len == abuf.len && !memcmp(obuf.buf, abuf.buf, obuf.len));
2975
2976error_return:
2977        strbuf_release(&obuf);
2978        strbuf_release(&abuf);
2979        return ret;
2980}
2981
2982static int handle_modify_delete(struct merge_options *opt,
2983                                const char *path,
2984                                const struct diff_filespec *o,
2985                                const struct diff_filespec *a,
2986                                const struct diff_filespec *b)
2987{
2988        const char *modify_branch, *delete_branch;
2989        const struct diff_filespec *changed;
2990
2991        if (is_valid(a)) {
2992                modify_branch = opt->branch1;
2993                delete_branch = opt->branch2;
2994                changed = a;
2995        } else {
2996                modify_branch = opt->branch2;
2997                delete_branch = opt->branch1;
2998                changed = b;
2999        }
3000
3001        return handle_change_delete(opt,
3002                                    path, NULL,
3003                                    o, changed,
3004                                    modify_branch, delete_branch,
3005                                    _("modify"), _("modified"));
3006}
3007
3008static int handle_content_merge(struct merge_file_info *mfi,
3009                                struct merge_options *opt,
3010                                const char *path,
3011                                int is_dirty,
3012                                const struct diff_filespec *o,
3013                                const struct diff_filespec *a,
3014                                const struct diff_filespec *b,
3015                                struct rename_conflict_info *ci)
3016{
3017        const char *reason = _("content");
3018        unsigned df_conflict_remains = 0;
3019
3020        if (!is_valid(o))
3021                reason = _("add/add");
3022
3023        assert(o->path && a->path && b->path);
3024        if (ci && dir_in_way(opt->repo->index, path, !opt->call_depth,
3025                             S_ISGITLINK(ci->ren1->pair->two->mode)))
3026                df_conflict_remains = 1;
3027
3028        if (merge_mode_and_contents(opt, o, a, b, path,
3029                                    opt->branch1, opt->branch2,
3030                                    opt->call_depth * 2, mfi))
3031                return -1;
3032
3033        /*
3034         * We can skip updating the working tree file iff:
3035         *   a) The merge is clean
3036         *   b) The merge matches what was in HEAD (content, mode, pathname)
3037         *   c) The target path is usable (i.e. not involved in D/F conflict)
3038         */
3039        if (mfi->clean && was_tracked_and_matches(opt, path, &mfi->blob) &&
3040            !df_conflict_remains) {
3041                int pos;
3042                struct cache_entry *ce;
3043
3044                output(opt, 3, _("Skipped %s (merged same as existing)"), path);
3045                if (add_cacheinfo(opt, &mfi->blob, path,
3046                                  0, (!opt->call_depth && !is_dirty), 0))
3047                        return -1;
3048                /*
3049                 * However, add_cacheinfo() will delete the old cache entry
3050                 * and add a new one.  We need to copy over any skip_worktree
3051                 * flag to avoid making the file appear as if it were
3052                 * deleted by the user.
3053                 */
3054                pos = index_name_pos(&opt->orig_index, path, strlen(path));
3055                ce = opt->orig_index.cache[pos];
3056                if (ce_skip_worktree(ce)) {
3057                        pos = index_name_pos(opt->repo->index, path, strlen(path));
3058                        ce = opt->repo->index->cache[pos];
3059                        ce->ce_flags |= CE_SKIP_WORKTREE;
3060                }
3061                return mfi->clean;
3062        }
3063
3064        if (!mfi->clean) {
3065                if (S_ISGITLINK(mfi->blob.mode))
3066                        reason = _("submodule");
3067                output(opt, 1, _("CONFLICT (%s): Merge conflict in %s"),
3068                                reason, path);
3069                if (ci && !df_conflict_remains)
3070                        if (update_stages(opt, path, o, a, b))
3071                                return -1;
3072        }
3073
3074        if (df_conflict_remains || is_dirty) {
3075                char *new_path;
3076                if (opt->call_depth) {
3077                        remove_file_from_index(opt->repo->index, path);
3078                } else {
3079                        if (!mfi->clean) {
3080                                if (update_stages(opt, path, o, a, b))
3081                                        return -1;
3082                        } else {
3083                                int file_from_stage2 = was_tracked(opt, path);
3084
3085                                if (update_stages(opt, path, NULL,
3086                                                  file_from_stage2 ? &mfi->blob : NULL,
3087                                                  file_from_stage2 ? NULL : &mfi->blob))
3088                                        return -1;
3089                        }
3090
3091                }
3092                new_path = unique_path(opt, path, ci->ren1->branch);
3093                if (is_dirty) {
3094                        output(opt, 1, _("Refusing to lose dirty file at %s"),
3095                               path);
3096                }
3097                output(opt, 1, _("Adding as %s instead"), new_path);
3098                if (update_file(opt, 0, &mfi->blob, new_path)) {
3099                        free(new_path);
3100                        return -1;
3101                }
3102                free(new_path);
3103                mfi->clean = 0;
3104        } else if (update_file(opt, mfi->clean, &mfi->blob, path))
3105                return -1;
3106        return !is_dirty && mfi->clean;
3107}
3108
3109static int handle_rename_normal(struct merge_options *opt,
3110                                const char *path,
3111                                const struct diff_filespec *o,
3112                                const struct diff_filespec *a,
3113                                const struct diff_filespec *b,
3114                                struct rename_conflict_info *ci)
3115{
3116        struct rename *ren = ci->ren1;
3117        struct merge_file_info mfi;
3118        int clean;
3119        int side = (ren->branch == opt->branch1 ? 2 : 3);
3120
3121        /* Merge the content and write it out */
3122        clean = handle_content_merge(&mfi, opt, path, was_dirty(opt, path),
3123                                     o, a, b, ci);
3124
3125        if (clean && opt->detect_directory_renames == 1 &&
3126            ren->dir_rename_original_dest) {
3127                if (update_stages(opt, path,
3128                                  NULL,
3129                                  side == 2 ? &mfi.blob : NULL,
3130                                  side == 2 ? NULL : &mfi.blob))
3131                        return -1;
3132                clean = 0; /* not clean, but conflicted */
3133        }
3134        return clean;
3135}
3136
3137static void dir_rename_warning(const char *msg,
3138                               int is_add,
3139                               int clean,
3140                               struct merge_options *opt,
3141                               struct rename *ren)
3142{
3143        const char *other_branch;
3144        other_branch = (ren->branch == opt->branch1 ?
3145                        opt->branch2 : opt->branch1);
3146        if (is_add) {
3147                output(opt, clean ? 2 : 1, msg,
3148                       ren->pair->one->path, ren->branch,
3149                       other_branch, ren->pair->two->path);
3150                return;
3151        }
3152        output(opt, clean ? 2 : 1, msg,
3153               ren->pair->one->path, ren->dir_rename_original_dest, ren->branch,
3154               other_branch, ren->pair->two->path);
3155}
3156static int warn_about_dir_renamed_entries(struct merge_options *opt,
3157                                          struct rename *ren)
3158{
3159        const char *msg;
3160        int clean = 1, is_add;
3161
3162        if (!ren)
3163                return clean;
3164
3165        /* Return early if ren was not affected/created by a directory rename */
3166        if (!ren->dir_rename_original_dest)
3167                return clean;
3168
3169        /* Sanity checks */
3170        assert(opt->detect_directory_renames > 0);
3171        assert(ren->dir_rename_original_type == 'A' ||
3172               ren->dir_rename_original_type == 'R');
3173
3174        /* Check whether to treat directory renames as a conflict */
3175        clean = (opt->detect_directory_renames == 2);
3176
3177        is_add = (ren->dir_rename_original_type == 'A');
3178        if (ren->dir_rename_original_type == 'A' && clean) {
3179                msg = _("Path updated: %s added in %s inside a "
3180                        "directory that was renamed in %s; moving it to %s.");
3181        } else if (ren->dir_rename_original_type == 'A' && !clean) {
3182                msg = _("CONFLICT (file location): %s added in %s "
3183                        "inside a directory that was renamed in %s, "
3184                        "suggesting it should perhaps be moved to %s.");
3185        } else if (ren->dir_rename_original_type == 'R' && clean) {
3186                msg = _("Path updated: %s renamed to %s in %s, inside a "
3187                        "directory that was renamed in %s; moving it to %s.");
3188        } else if (ren->dir_rename_original_type == 'R' && !clean) {
3189                msg = _("CONFLICT (file location): %s renamed to %s in %s, "
3190                        "inside a directory that was renamed in %s, "
3191                        "suggesting it should perhaps be moved to %s.");
3192        } else {
3193                BUG("Impossible dir_rename_original_type/clean combination");
3194        }
3195        dir_rename_warning(msg, is_add, clean, opt, ren);
3196
3197        return clean;
3198}
3199
3200/* Per entry merge function */
3201static int process_entry(struct merge_options *opt,
3202                         const char *path, struct stage_data *entry)
3203{
3204        int clean_merge = 1;
3205        int normalize = opt->renormalize;
3206
3207        struct diff_filespec *o = &entry->stages[1];
3208        struct diff_filespec *a = &entry->stages[2];
3209        struct diff_filespec *b = &entry->stages[3];
3210        int o_valid = is_valid(o);
3211        int a_valid = is_valid(a);
3212        int b_valid = is_valid(b);
3213        o->path = a->path = b->path = (char*)path;
3214
3215        entry->processed = 1;
3216        if (entry->rename_conflict_info) {
3217                struct rename_conflict_info *ci = entry->rename_conflict_info;
3218                struct diff_filespec *temp;
3219                int path_clean;
3220
3221                path_clean = warn_about_dir_renamed_entries(opt, ci->ren1);
3222                path_clean &= warn_about_dir_renamed_entries(opt, ci->ren2);
3223
3224                /*
3225                 * For cases with a single rename, {o,a,b}->path have all been
3226                 * set to the rename target path; we need to set two of these
3227                 * back to the rename source.
3228                 * For rename/rename conflicts, we'll manually fix paths below.
3229                 */
3230                temp = (opt->branch1 == ci->ren1->branch) ? b : a;
3231                o->path = temp->path = ci->ren1->pair->one->path;
3232                if (ci->ren2) {
3233                        assert(opt->branch1 == ci->ren1->branch);
3234                }
3235
3236                switch (ci->rename_type) {
3237                case RENAME_NORMAL:
3238                case RENAME_ONE_FILE_TO_ONE:
3239                        clean_merge = handle_rename_normal(opt, path, o, a, b,
3240                                                           ci);
3241                        break;
3242                case RENAME_VIA_DIR:
3243                        clean_merge = handle_rename_via_dir(opt, ci);
3244                        break;
3245                case RENAME_ADD:
3246                        /*
3247                         * Probably unclean merge, but if the renamed file
3248                         * merges cleanly and the result can then be
3249                         * two-way merged cleanly with the added file, I
3250                         * guess it's a clean merge?
3251                         */
3252                        clean_merge = handle_rename_add(opt, ci);
3253                        break;
3254                case RENAME_DELETE:
3255                        clean_merge = 0;
3256                        if (handle_rename_delete(opt, ci))
3257                                clean_merge = -1;
3258                        break;
3259                case RENAME_ONE_FILE_TO_TWO:
3260                        /*
3261                         * Manually fix up paths; note:
3262                         * ren[12]->pair->one->path are equal.
3263                         */
3264                        o->path = ci->ren1->pair->one->path;
3265                        a->path = ci->ren1->pair->two->path;
3266                        b->path = ci->ren2->pair->two->path;
3267
3268                        clean_merge = 0;
3269                        if (handle_rename_rename_1to2(opt, ci))
3270                                clean_merge = -1;
3271                        break;
3272                case RENAME_TWO_FILES_TO_ONE:
3273                        /*
3274                         * Manually fix up paths; note,
3275                         * ren[12]->pair->two->path are actually equal.
3276                         */
3277                        o->path = NULL;
3278                        a->path = ci->ren1->pair->two->path;
3279                        b->path = ci->ren2->pair->two->path;
3280
3281                        /*
3282                         * Probably unclean merge, but if the two renamed
3283                         * files merge cleanly and the two resulting files
3284                         * can then be two-way merged cleanly, I guess it's
3285                         * a clean merge?
3286                         */
3287                        clean_merge = handle_rename_rename_2to1(opt, ci);
3288                        break;
3289                default:
3290                        entry->processed = 0;
3291                        break;
3292                }
3293                if (path_clean < clean_merge)
3294                        clean_merge = path_clean;
3295        } else if (o_valid && (!a_valid || !b_valid)) {
3296                /* Case A: Deleted in one */
3297                if ((!a_valid && !b_valid) ||
3298                    (!b_valid && blob_unchanged(opt, o, a, normalize, path)) ||
3299                    (!a_valid && blob_unchanged(opt, o, b, normalize, path))) {
3300                        /* Deleted in both or deleted in one and
3301                         * unchanged in the other */
3302                        if (a_valid)
3303                                output(opt, 2, _("Removing %s"), path);
3304                        /* do not touch working file if it did not exist */
3305                        remove_file(opt, 1, path, !a_valid);
3306                } else {
3307                        /* Modify/delete; deleted side may have put a directory in the way */
3308                        clean_merge = 0;
3309                        if (handle_modify_delete(opt, path, o, a, b))
3310                                clean_merge = -1;
3311                }
3312        } else if ((!o_valid && a_valid && !b_valid) ||
3313                   (!o_valid && !a_valid && b_valid)) {
3314                /* Case B: Added in one. */
3315                /* [nothing|directory] -> ([nothing|directory], file) */
3316
3317                const char *add_branch;
3318                const char *other_branch;
3319                const char *conf;
3320                const struct diff_filespec *contents;
3321
3322                if (a_valid) {
3323                        add_branch = opt->branch1;
3324                        other_branch = opt->branch2;
3325                        contents = a;
3326                        conf = _("file/directory");
3327                } else {
3328                        add_branch = opt->branch2;
3329                        other_branch = opt->branch1;
3330                        contents = b;
3331                        conf = _("directory/file");
3332                }
3333                if (dir_in_way(opt->repo->index, path,
3334                               !opt->call_depth && !S_ISGITLINK(a->mode),
3335                               0)) {
3336                        char *new_path = unique_path(opt, path, add_branch);
3337                        clean_merge = 0;
3338                        output(opt, 1, _("CONFLICT (%s): There is a directory with name %s in %s. "
3339                               "Adding %s as %s"),
3340                               conf, path, other_branch, path, new_path);
3341                        if (update_file(opt, 0, contents, new_path))
3342                                clean_merge = -1;
3343                        else if (opt->call_depth)
3344                                remove_file_from_index(opt->repo->index, path);
3345                        free(new_path);
3346                } else {
3347                        output(opt, 2, _("Adding %s"), path);
3348                        /* do not overwrite file if already present */
3349                        if (update_file_flags(opt, contents, path, 1, !a_valid))
3350                                clean_merge = -1;
3351                }
3352        } else if (a_valid && b_valid) {
3353                if (!o_valid) {
3354                        /* Case C: Added in both (check for same permissions) */
3355                        output(opt, 1,
3356                               _("CONFLICT (add/add): Merge conflict in %s"),
3357                               path);
3358                        clean_merge = handle_file_collision(opt,
3359                                                            path, NULL, NULL,
3360                                                            opt->branch1,
3361                                                            opt->branch2,
3362                                                            a, b);
3363                } else {
3364                        /* case D: Modified in both, but differently. */
3365                        struct merge_file_info mfi;
3366                        int is_dirty = 0; /* unpack_trees would have bailed if dirty */
3367                        clean_merge = handle_content_merge(&mfi, opt, path,
3368                                                           is_dirty,
3369                                                           o, a, b, NULL);
3370                }
3371        } else if (!o_valid && !a_valid && !b_valid) {
3372                /*
3373                 * this entry was deleted altogether. a_mode == 0 means
3374                 * we had that path and want to actively remove it.
3375                 */
3376                remove_file(opt, 1, path, !a->mode);
3377        } else
3378                BUG("fatal merge failure, shouldn't happen.");
3379
3380        return clean_merge;
3381}
3382
3383int merge_trees(struct merge_options *opt,
3384                struct tree *head,
3385                struct tree *merge,
3386                struct tree *common,
3387                struct tree **result)
3388{
3389        struct index_state *istate = opt->repo->index;
3390        int code, clean;
3391        struct strbuf sb = STRBUF_INIT;
3392
3393        if (!opt->call_depth && repo_index_has_changes(opt->repo, head, &sb)) {
3394                err(opt, _("Your local changes to the following files would be overwritten by merge:\n  %s"),
3395                    sb.buf);
3396                return -1;
3397        }
3398
3399        if (opt->subtree_shift) {
3400                merge = shift_tree_object(opt->repo, head, merge, opt->subtree_shift);
3401                common = shift_tree_object(opt->repo, head, common, opt->subtree_shift);
3402        }
3403
3404        if (oid_eq(&common->object.oid, &merge->object.oid)) {
3405                output(opt, 0, _("Already up to date!"));
3406                *result = head;
3407                return 1;
3408        }
3409
3410        code = unpack_trees_start(opt, common, head, merge);
3411
3412        if (code != 0) {
3413                if (show(opt, 4) || opt->call_depth)
3414                        err(opt, _("merging of trees %s and %s failed"),
3415                            oid_to_hex(&head->object.oid),
3416                            oid_to_hex(&merge->object.oid));
3417                unpack_trees_finish(opt);
3418                return -1;
3419        }
3420
3421        if (unmerged_index(istate)) {
3422                struct string_list *entries;
3423                struct rename_info re_info;
3424                int i;
3425                /*
3426                 * Only need the hashmap while processing entries, so
3427                 * initialize it here and free it when we are done running
3428                 * through the entries. Keeping it in the merge_options as
3429                 * opposed to decaring a local hashmap is for convenience
3430                 * so that we don't have to pass it to around.
3431                 */
3432                hashmap_init(&opt->current_file_dir_set, path_hashmap_cmp, NULL, 512);
3433                get_files_dirs(opt, head);
3434                get_files_dirs(opt, merge);
3435
3436                entries = get_unmerged(opt->repo->index);
3437                clean = detect_and_process_renames(opt, common, head, merge,
3438                                                   entries, &re_info);
3439                record_df_conflict_files(opt, entries);
3440                if (clean < 0)
3441                        goto cleanup;
3442                for (i = entries->nr-1; 0 <= i; i--) {
3443                        const char *path = entries->items[i].string;
3444                        struct stage_data *e = entries->items[i].util;
3445                        if (!e->processed) {
3446                                int ret = process_entry(opt, path, e);
3447                                if (!ret)
3448                                        clean = 0;
3449                                else if (ret < 0) {
3450                                        clean = ret;
3451                                        goto cleanup;
3452                                }
3453                        }
3454                }
3455                for (i = 0; i < entries->nr; i++) {
3456                        struct stage_data *e = entries->items[i].util;
3457                        if (!e->processed)
3458                                BUG("unprocessed path??? %s",
3459                                    entries->items[i].string);
3460                }
3461
3462        cleanup:
3463                final_cleanup_renames(&re_info);
3464
3465                string_list_clear(entries, 1);
3466                free(entries);
3467
3468                hashmap_free(&opt->current_file_dir_set, 1);
3469
3470                if (clean < 0) {
3471                        unpack_trees_finish(opt);
3472                        return clean;
3473                }
3474        }
3475        else
3476                clean = 1;
3477
3478        unpack_trees_finish(opt);
3479
3480        if (opt->call_depth && !(*result = write_tree_from_memory(opt)))
3481                return -1;
3482
3483        return clean;
3484}
3485
3486static struct commit_list *reverse_commit_list(struct commit_list *list)
3487{
3488        struct commit_list *next = NULL, *current, *backup;
3489        for (current = list; current; current = backup) {
3490                backup = current->next;
3491                current->next = next;
3492                next = current;
3493        }
3494        return next;
3495}
3496
3497/*
3498 * Merge the commits h1 and h2, return the resulting virtual
3499 * commit object and a flag indicating the cleanness of the merge.
3500 */
3501int merge_recursive(struct merge_options *opt,
3502                    struct commit *h1,
3503                    struct commit *h2,
3504                    struct commit_list *ca,
3505                    struct commit **result)
3506{
3507        struct commit_list *iter;
3508        struct commit *merged_common_ancestors;
3509        struct tree *mrtree;
3510        int clean;
3511
3512        if (show(opt, 4)) {
3513                output(opt, 4, _("Merging:"));
3514                output_commit_title(opt, h1);
3515                output_commit_title(opt, h2);
3516        }
3517
3518        if (!ca) {
3519                ca = get_merge_bases(h1, h2);
3520                ca = reverse_commit_list(ca);
3521        }
3522
3523        if (show(opt, 5)) {
3524                unsigned cnt = commit_list_count(ca);
3525
3526                output(opt, 5, Q_("found %u common ancestor:",
3527                                "found %u common ancestors:", cnt), cnt);
3528                for (iter = ca; iter; iter = iter->next)
3529                        output_commit_title(opt, iter->item);
3530        }
3531
3532        merged_common_ancestors = pop_commit(&ca);
3533        if (merged_common_ancestors == NULL) {
3534                /* if there is no common ancestor, use an empty tree */
3535                struct tree *tree;
3536
3537                tree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);
3538                merged_common_ancestors = make_virtual_commit(opt->repo, tree, "ancestor");
3539        }
3540
3541        for (iter = ca; iter; iter = iter->next) {
3542                const char *saved_b1, *saved_b2;
3543                opt->call_depth++;
3544                /*
3545                 * When the merge fails, the result contains files
3546                 * with conflict markers. The cleanness flag is
3547                 * ignored (unless indicating an error), it was never
3548                 * actually used, as result of merge_trees has always
3549                 * overwritten it: the committed "conflicts" were
3550                 * already resolved.
3551                 */
3552                discard_index(opt->repo->index);
3553                saved_b1 = opt->branch1;
3554                saved_b2 = opt->branch2;
3555                opt->branch1 = "Temporary merge branch 1";
3556                opt->branch2 = "Temporary merge branch 2";
3557                if (merge_recursive(opt, merged_common_ancestors, iter->item,
3558                                    NULL, &merged_common_ancestors) < 0)
3559                        return -1;
3560                opt->branch1 = saved_b1;
3561                opt->branch2 = saved_b2;
3562                opt->call_depth--;
3563
3564                if (!merged_common_ancestors)
3565                        return err(opt, _("merge returned no commit"));
3566        }
3567
3568        discard_index(opt->repo->index);
3569        if (!opt->call_depth)
3570                repo_read_index(opt->repo);
3571
3572        opt->ancestor = "merged common ancestors";
3573        clean = merge_trees(opt, get_commit_tree(h1), get_commit_tree(h2),
3574                            get_commit_tree(merged_common_ancestors),
3575                            &mrtree);
3576        if (clean < 0) {
3577                flush_output(opt);
3578                return clean;
3579        }
3580
3581        if (opt->call_depth) {
3582                *result = make_virtual_commit(opt->repo, mrtree, "merged tree");
3583                commit_list_insert(h1, &(*result)->parents);
3584                commit_list_insert(h2, &(*result)->parents->next);
3585        }
3586        flush_output(opt);
3587        if (!opt->call_depth && opt->buffer_output < 2)
3588                strbuf_release(&opt->obuf);
3589        if (show(opt, 2))
3590                diff_warn_rename_limit("merge.renamelimit",
3591                                       opt->needed_rename_limit, 0);
3592        return clean;
3593}
3594
3595static struct commit *get_ref(struct repository *repo, const struct object_id *oid,
3596                              const char *name)
3597{
3598        struct object *object;
3599
3600        object = deref_tag(repo, parse_object(repo, oid),
3601                           name, strlen(name));
3602        if (!object)
3603                return NULL;
3604        if (object->type == OBJ_TREE)
3605                return make_virtual_commit(repo, (struct tree*)object, name);
3606        if (object->type != OBJ_COMMIT)
3607                return NULL;
3608        if (parse_commit((struct commit *)object))
3609                return NULL;
3610        return (struct commit *)object;
3611}
3612
3613int merge_recursive_generic(struct merge_options *opt,
3614                            const struct object_id *head,
3615                            const struct object_id *merge,
3616                            int num_base_list,
3617                            const struct object_id **base_list,
3618                            struct commit **result)
3619{
3620        int clean;
3621        struct lock_file lock = LOCK_INIT;
3622        struct commit *head_commit = get_ref(opt->repo, head, opt->branch1);
3623        struct commit *next_commit = get_ref(opt->repo, merge, opt->branch2);
3624        struct commit_list *ca = NULL;
3625
3626        if (base_list) {
3627                int i;
3628                for (i = 0; i < num_base_list; ++i) {
3629                        struct commit *base;
3630                        if (!(base = get_ref(opt->repo, base_list[i], oid_to_hex(base_list[i]))))
3631                                return err(opt, _("Could not parse object '%s'"),
3632                                           oid_to_hex(base_list[i]));
3633                        commit_list_insert(base, &ca);
3634                }
3635        }
3636
3637        repo_hold_locked_index(opt->repo, &lock, LOCK_DIE_ON_ERROR);
3638        clean = merge_recursive(opt, head_commit, next_commit, ca,
3639                                result);
3640        if (clean < 0) {
3641                rollback_lock_file(&lock);
3642                return clean;
3643        }
3644
3645        if (write_locked_index(opt->repo->index, &lock,
3646                               COMMIT_LOCK | SKIP_IF_UNCHANGED))
3647                return err(opt, _("Unable to write index."));
3648
3649        return clean ? 0 : 1;
3650}
3651
3652static void merge_recursive_config(struct merge_options *opt)
3653{
3654        char *value = NULL;
3655        git_config_get_int("merge.verbosity", &opt->verbosity);
3656        git_config_get_int("diff.renamelimit", &opt->diff_rename_limit);
3657        git_config_get_int("merge.renamelimit", &opt->merge_rename_limit);
3658        if (!git_config_get_string("diff.renames", &value)) {
3659                opt->diff_detect_rename = git_config_rename("diff.renames", value);
3660                free(value);
3661        }
3662        if (!git_config_get_string("merge.renames", &value)) {
3663                opt->merge_detect_rename = git_config_rename("merge.renames", value);
3664                free(value);
3665        }
3666        if (!git_config_get_string("merge.directoryrenames", &value)) {
3667                int boolval = git_parse_maybe_bool(value);
3668                if (0 <= boolval) {
3669                        opt->detect_directory_renames = boolval ? 2 : 0;
3670                } else if (!strcasecmp(value, "conflict")) {
3671                        opt->detect_directory_renames = 1;
3672                } /* avoid erroring on values from future versions of git */
3673                free(value);
3674        }
3675        git_config(git_xmerge_config, NULL);
3676}
3677
3678void init_merge_options(struct merge_options *opt,
3679                        struct repository *repo)
3680{
3681        const char *merge_verbosity;
3682        memset(opt, 0, sizeof(struct merge_options));
3683        opt->repo = repo;
3684        opt->verbosity = 2;
3685        opt->buffer_output = 1;
3686        opt->diff_rename_limit = -1;
3687        opt->merge_rename_limit = -1;
3688        opt->renormalize = 0;
3689        opt->diff_detect_rename = -1;
3690        opt->merge_detect_rename = -1;
3691        opt->detect_directory_renames = 1;
3692        merge_recursive_config(opt);
3693        merge_verbosity = getenv("GIT_MERGE_VERBOSITY");
3694        if (merge_verbosity)
3695                opt->verbosity = strtol(merge_verbosity, NULL, 10);
3696        if (opt->verbosity >= 5)
3697                opt->buffer_output = 0;
3698        strbuf_init(&opt->obuf, 0);
3699        string_list_init(&opt->df_conflict_file_set, 1);
3700}
3701
3702int parse_merge_opt(struct merge_options *opt, const char *s)
3703{
3704        const char *arg;
3705
3706        if (!s || !*s)
3707                return -1;
3708        if (!strcmp(s, "ours"))
3709                opt->recursive_variant = MERGE_RECURSIVE_OURS;
3710        else if (!strcmp(s, "theirs"))
3711                opt->recursive_variant = MERGE_RECURSIVE_THEIRS;
3712        else if (!strcmp(s, "subtree"))
3713                opt->subtree_shift = "";
3714        else if (skip_prefix(s, "subtree=", &arg))
3715                opt->subtree_shift = arg;
3716        else if (!strcmp(s, "patience"))
3717                opt->xdl_opts = DIFF_WITH_ALG(opt, PATIENCE_DIFF);
3718        else if (!strcmp(s, "histogram"))
3719                opt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);
3720        else if (skip_prefix(s, "diff-algorithm=", &arg)) {
3721                long value = parse_algorithm_value(arg);
3722                if (value < 0)
3723                        return -1;
3724                /* clear out previous settings */
3725                DIFF_XDL_CLR(opt, NEED_MINIMAL);
3726                opt->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
3727                opt->xdl_opts |= value;
3728        }
3729        else if (!strcmp(s, "ignore-space-change"))
3730                DIFF_XDL_SET(opt, IGNORE_WHITESPACE_CHANGE);
3731        else if (!strcmp(s, "ignore-all-space"))
3732                DIFF_XDL_SET(opt, IGNORE_WHITESPACE);
3733        else if (!strcmp(s, "ignore-space-at-eol"))
3734                DIFF_XDL_SET(opt, IGNORE_WHITESPACE_AT_EOL);
3735        else if (!strcmp(s, "ignore-cr-at-eol"))
3736                DIFF_XDL_SET(opt, IGNORE_CR_AT_EOL);
3737        else if (!strcmp(s, "renormalize"))
3738                opt->renormalize = 1;
3739        else if (!strcmp(s, "no-renormalize"))
3740                opt->renormalize = 0;
3741        else if (!strcmp(s, "no-renames"))
3742                opt->merge_detect_rename = 0;
3743        else if (!strcmp(s, "find-renames")) {
3744                opt->merge_detect_rename = 1;
3745                opt->rename_score = 0;
3746        }
3747        else if (skip_prefix(s, "find-renames=", &arg) ||
3748                 skip_prefix(s, "rename-threshold=", &arg)) {
3749                if ((opt->rename_score = parse_rename_score(&arg)) == -1 || *arg != 0)
3750                        return -1;
3751                opt->merge_detect_rename = 1;
3752        }
3753        /*
3754         * Please update $__git_merge_strategy_options in
3755         * git-completion.bash when you add new options
3756         */
3757        else
3758                return -1;
3759        return 0;
3760}