merge-recursive.c

   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 "cache-tree.h"
   8 #include "commit.h"
   9 #include "blob.h"
  10 #include "builtin.h"
  11 #include "tree-walk.h"
  12 #include "diff.h"
  13 #include "diffcore.h"
  14 #include "tag.h"
  15 #include "unpack-trees.h"
  16 #include "string-list.h"
  17 #include "xdiff-interface.h"
  18 #include "ll-merge.h"
  19 #include "interpolate.h"
  20 #include "attr.h"
  21 #include "merge-recursive.h"
  22
  23 static int subtree_merge;
  24
  25 static struct tree *shift_tree_object(struct tree *one, struct tree *two)
  26 {
  27         unsigned char shifted[20];
  28
  29         /*
  30          * NEEDSWORK: this limits the recursion depth to hardcoded
  31          * value '2' to avoid excessive overhead.
  32          */
  33         shift_tree(one->object.sha1, two->object.sha1, shifted, 2);
  34         if (!hashcmp(two->object.sha1, shifted))
  35                 return two;
  36         return lookup_tree(shifted);
  37 }
  38
  39 /*
  40  * A virtual commit has
  41  * - (const char *)commit->util set to the name, and
  42  * - *(int *)commit->object.sha1 set to the virtual id.
  43  */
  44
  45 struct commit *make_virtual_commit(struct tree *tree, const char *comment)
  46 {
  47         struct commit *commit = xcalloc(1, sizeof(struct commit));
  48         static unsigned virtual_id = 1;
  49         commit->tree = tree;
  50         commit->util = (void*)comment;
  51         *(int*)commit->object.sha1 = virtual_id++;
  52         /* avoid warnings */
  53         commit->object.parsed = 1;
  54         return commit;
  55 }
  56
  57 /*
  58  * Since we use get_tree_entry(), which does not put the read object into
  59  * the object pool, we cannot rely on a == b.
  60  */
  61 static int sha_eq(const unsigned char *a, const unsigned char *b)
  62 {
  63         if (!a && !b)
  64                 return 2;
  65         return a && b && hashcmp(a, b) == 0;
  66 }
  67
  68 /*
  69  * Since we want to write the index eventually, we cannot reuse the index
  70  * for these (temporary) data.
  71  */
  72 struct stage_data
  73 {
  74         struct
  75         {
  76                 unsigned mode;
  77                 unsigned char sha[20];
  78         } stages[4];
  79         unsigned processed:1;
  80 };
  81
  82 static struct string_list current_file_set = {NULL, 0, 0, 1};
  83 static struct string_list current_directory_set = {NULL, 0, 0, 1};
  84
  85 static int call_depth = 0;
  86 int merge_recursive_verbosity = 2;
  87 static int diff_rename_limit = -1;
  88 static int merge_rename_limit = -1;
  89 static int buffer_output = 1;
  90 static struct strbuf obuf = STRBUF_INIT;
  91
  92 static int show(int v)
  93 {
  94         return (!call_depth && merge_recursive_verbosity >= v) ||
  95                 merge_recursive_verbosity >= 5;
  96 }
  97
  98 static void flush_output(void)
  99 {
 100         if (obuf.len) {
 101                 fputs(obuf.buf, stdout);
 102                 strbuf_reset(&obuf);
 103         }
 104 }
 105
 106 static void output(int v, const char *fmt, ...)
 107 {
 108         int len;
 109         va_list ap;
 110
 111         if (!show(v))
 112                 return;
 113
 114         strbuf_grow(&obuf, call_depth * 2 + 2);
 115         memset(obuf.buf + obuf.len, ' ', call_depth * 2);
 116         strbuf_setlen(&obuf, obuf.len + call_depth * 2);
 117
 118         va_start(ap, fmt);
 119         len = vsnprintf(obuf.buf + obuf.len, strbuf_avail(&obuf), fmt, ap);
 120         va_end(ap);
 121
 122         if (len < 0)
 123                 len = 0;
 124         if (len >= strbuf_avail(&obuf)) {
 125                 strbuf_grow(&obuf, len + 2);
 126                 va_start(ap, fmt);
 127                 len = vsnprintf(obuf.buf + obuf.len, strbuf_avail(&obuf), fmt, ap);
 128                 va_end(ap);
 129                 if (len >= strbuf_avail(&obuf)) {
 130                         die("this should not happen, your snprintf is broken");
 131                 }
 132         }
 133         strbuf_setlen(&obuf, obuf.len + len);
 134         strbuf_add(&obuf, "\n", 1);
 135         if (!buffer_output)
 136                 flush_output();
 137 }
 138
 139 static void output_commit_title(struct commit *commit)
 140 {
 141         int i;
 142         flush_output();
 143         for (i = call_depth; i--;)
 144                 fputs("  ", stdout);
 145         if (commit->util)
 146                 printf("virtual %s\n", (char *)commit->util);
 147         else {
 148                 printf("%s ", find_unique_abbrev(commit->object.sha1, DEFAULT_ABBREV));
 149                 if (parse_commit(commit) != 0)
 150                         printf("(bad commit)\n");
 151                 else {
 152                         const char *s;
 153                         int len;
 154                         for (s = commit->buffer; *s; s++)
 155                                 if (*s == '\n' && s[1] == '\n') {
 156                                         s += 2;
 157                                         break;
 158                                 }
 159                         for (len = 0; s[len] && '\n' != s[len]; len++)
 160                                 ; /* do nothing */
 161                         printf("%.*s\n", len, s);
 162                 }
 163         }
 164 }
 165
 166 static int add_cacheinfo(unsigned int mode, const unsigned char *sha1,
 167                 const char *path, int stage, int refresh, int options)
 168 {
 169         struct cache_entry *ce;
 170         ce = make_cache_entry(mode, sha1 ? sha1 : null_sha1, path, stage, refresh);
 171         if (!ce)
 172                 return error("addinfo_cache failed for path '%s'", path);
 173         return add_cache_entry(ce, options);
 174 }
 175
 176 /*
 177  * This is a global variable which is used in a number of places but
 178  * only written to in the 'merge' function.
 179  *
 180  * index_only == 1    => Don't leave any non-stage 0 entries in the cache and
 181  *                       don't update the working directory.
 182  *               0    => Leave unmerged entries in the cache and update
 183  *                       the working directory.
 184  */
 185 static int index_only = 0;
 186
 187 static void init_tree_desc_from_tree(struct tree_desc *desc, struct tree *tree)
 188 {
 189         parse_tree(tree);
 190         init_tree_desc(desc, tree->buffer, tree->size);
 191 }
 192
 193 static int git_merge_trees(int index_only,
 194                            struct tree *common,
 195                            struct tree *head,
 196                            struct tree *merge)
 197 {
 198         int rc;
 199         struct tree_desc t[3];
 200         struct unpack_trees_options opts;
 201
 202         memset(&opts, 0, sizeof(opts));
 203         if (index_only)
 204                 opts.index_only = 1;
 205         else
 206                 opts.update = 1;
 207         opts.merge = 1;
 208         opts.head_idx = 2;
 209         opts.fn = threeway_merge;
 210         opts.src_index = &the_index;
 211         opts.dst_index = &the_index;
 212
 213         init_tree_desc_from_tree(t+0, common);
 214         init_tree_desc_from_tree(t+1, head);
 215         init_tree_desc_from_tree(t+2, merge);
 216
 217         rc = unpack_trees(3, t, &opts);
 218         cache_tree_free(&active_cache_tree);
 219         return rc;
 220 }
 221
 222 struct tree *write_tree_from_memory(void)
 223 {
 224         struct tree *result = NULL;
 225
 226         if (unmerged_cache()) {
 227                 int i;
 228                 output(0, "There are unmerged index entries:");
 229                 for (i = 0; i < active_nr; i++) {
 230                         struct cache_entry *ce = active_cache[i];
 231                         if (ce_stage(ce))
 232                                 output(0, "%d %.*s", ce_stage(ce), ce_namelen(ce), ce->name);
 233                 }
 234                 return NULL;
 235         }
 236
 237         if (!active_cache_tree)
 238                 active_cache_tree = cache_tree();
 239
 240         if (!cache_tree_fully_valid(active_cache_tree) &&
 241             cache_tree_update(active_cache_tree,
 242                               active_cache, active_nr, 0, 0) < 0)
 243                 die("error building trees");
 244
 245         result = lookup_tree(active_cache_tree->sha1);
 246
 247         return result;
 248 }
 249
 250 static int save_files_dirs(const unsigned char *sha1,
 251                 const char *base, int baselen, const char *path,
 252                 unsigned int mode, int stage, void *context)
 253 {
 254         int len = strlen(path);
 255         char *newpath = xmalloc(baselen + len + 1);
 256         memcpy(newpath, base, baselen);
 257         memcpy(newpath + baselen, path, len);
 258         newpath[baselen + len] = '\0';
 259
 260         if (S_ISDIR(mode))
 261                 string_list_insert(newpath, &current_directory_set);
 262         else
 263                 string_list_insert(newpath, &current_file_set);
 264         free(newpath);
 265
 266         return READ_TREE_RECURSIVE;
 267 }
 268
 269 static int get_files_dirs(struct tree *tree)
 270 {
 271         int n;
 272         if (read_tree_recursive(tree, "", 0, 0, NULL, save_files_dirs, NULL))
 273                 return 0;
 274         n = current_file_set.nr + current_directory_set.nr;
 275         return n;
 276 }
 277
 278 /*
 279  * Returns an index_entry instance which doesn't have to correspond to
 280  * a real cache entry in Git's index.
 281  */
 282 static struct stage_data *insert_stage_data(const char *path,
 283                 struct tree *o, struct tree *a, struct tree *b,
 284                 struct string_list *entries)
 285 {
 286         struct string_list_item *item;
 287         struct stage_data *e = xcalloc(1, sizeof(struct stage_data));
 288         get_tree_entry(o->object.sha1, path,
 289                         e->stages[1].sha, &e->stages[1].mode);
 290         get_tree_entry(a->object.sha1, path,
 291                         e->stages[2].sha, &e->stages[2].mode);
 292         get_tree_entry(b->object.sha1, path,
 293                         e->stages[3].sha, &e->stages[3].mode);
 294         item = string_list_insert(path, entries);
 295         item->util = e;
 296         return e;
 297 }
 298
 299 /*
 300  * Create a dictionary mapping file names to stage_data objects. The
 301  * dictionary contains one entry for every path with a non-zero stage entry.
 302  */
 303 static struct string_list *get_unmerged(void)
 304 {
 305         struct string_list *unmerged = xcalloc(1, sizeof(struct string_list));
 306         int i;
 307
 308         unmerged->strdup_strings = 1;
 309
 310         for (i = 0; i < active_nr; i++) {
 311                 struct string_list_item *item;
 312                 struct stage_data *e;
 313                 struct cache_entry *ce = active_cache[i];
 314                 if (!ce_stage(ce))
 315                         continue;
 316
 317                 item = string_list_lookup(ce->name, unmerged);
 318                 if (!item) {
 319                         item = string_list_insert(ce->name, unmerged);
 320                         item->util = xcalloc(1, sizeof(struct stage_data));
 321                 }
 322                 e = item->util;
 323                 e->stages[ce_stage(ce)].mode = ce->ce_mode;
 324                 hashcpy(e->stages[ce_stage(ce)].sha, ce->sha1);
 325         }
 326
 327         return unmerged;
 328 }
 329
 330 struct rename
 331 {
 332         struct diff_filepair *pair;
 333         struct stage_data *src_entry;
 334         struct stage_data *dst_entry;
 335         unsigned processed:1;
 336 };
 337
 338 /*
 339  * Get information of all renames which occurred between 'o_tree' and
 340  * 'tree'. We need the three trees in the merge ('o_tree', 'a_tree' and
 341  * 'b_tree') to be able to associate the correct cache entries with
 342  * the rename information. 'tree' is always equal to either a_tree or b_tree.
 343  */
 344 static struct string_list *get_renames(struct tree *tree,
 345                                         struct tree *o_tree,
 346                                         struct tree *a_tree,
 347                                         struct tree *b_tree,
 348                                         struct string_list *entries)
 349 {
 350         int i;
 351         struct string_list *renames;
 352         struct diff_options opts;
 353
 354         renames = xcalloc(1, sizeof(struct string_list));
 355         diff_setup(&opts);
 356         DIFF_OPT_SET(&opts, RECURSIVE);
 357         opts.detect_rename = DIFF_DETECT_RENAME;
 358         opts.rename_limit = merge_rename_limit >= 0 ? merge_rename_limit :
 359                             diff_rename_limit >= 0 ? diff_rename_limit :
 360                             500;
 361         opts.warn_on_too_large_rename = 1;
 362         opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 363         if (diff_setup_done(&opts) < 0)
 364                 die("diff setup failed");
 365         diff_tree_sha1(o_tree->object.sha1, tree->object.sha1, "", &opts);
 366         diffcore_std(&opts);
 367         for (i = 0; i < diff_queued_diff.nr; ++i) {
 368                 struct string_list_item *item;
 369                 struct rename *re;
 370                 struct diff_filepair *pair = diff_queued_diff.queue[i];
 371                 if (pair->status != 'R') {
 372                         diff_free_filepair(pair);
 373                         continue;
 374                 }
 375                 re = xmalloc(sizeof(*re));
 376                 re->processed = 0;
 377                 re->pair = pair;
 378                 item = string_list_lookup(re->pair->one->path, entries);
 379                 if (!item)
 380                         re->src_entry = insert_stage_data(re->pair->one->path,
 381                                         o_tree, a_tree, b_tree, entries);
 382                 else
 383                         re->src_entry = item->util;
 384
 385                 item = string_list_lookup(re->pair->two->path, entries);
 386                 if (!item)
 387                         re->dst_entry = insert_stage_data(re->pair->two->path,
 388                                         o_tree, a_tree, b_tree, entries);
 389                 else
 390                         re->dst_entry = item->util;
 391                 item = string_list_insert(pair->one->path, renames);
 392                 item->util = re;
 393         }
 394         opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 395         diff_queued_diff.nr = 0;
 396         diff_flush(&opts);
 397         return renames;
 398 }
 399
 400 static int update_stages(const char *path, struct diff_filespec *o,
 401                          struct diff_filespec *a, struct diff_filespec *b,
 402                          int clear)
 403 {
 404         int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE;
 405         if (clear)
 406                 if (remove_file_from_cache(path))
 407                         return -1;
 408         if (o)
 409                 if (add_cacheinfo(o->mode, o->sha1, path, 1, 0, options))
 410                         return -1;
 411         if (a)
 412                 if (add_cacheinfo(a->mode, a->sha1, path, 2, 0, options))
 413                         return -1;
 414         if (b)
 415                 if (add_cacheinfo(b->mode, b->sha1, path, 3, 0, options))
 416                         return -1;
 417         return 0;
 418 }
 419
 420 static int remove_path(const char *name)
 421 {
 422         int ret;
 423         char *slash, *dirs;
 424
 425         ret = unlink(name);
 426         if (ret)
 427                 return ret;
 428         dirs = xstrdup(name);
 429         while ((slash = strrchr(name, '/'))) {
 430                 *slash = '\0';
 431                 if (rmdir(name) != 0)
 432                         break;
 433         }
 434         free(dirs);
 435         return ret;
 436 }
 437
 438 static int remove_file(int clean, const char *path, int no_wd)
 439 {
 440         int update_cache = index_only || clean;
 441         int update_working_directory = !index_only && !no_wd;
 442
 443         if (update_cache) {
 444                 if (remove_file_from_cache(path))
 445                         return -1;
 446         }
 447         if (update_working_directory) {
 448                 unlink(path);
 449                 if (errno != ENOENT || errno != EISDIR)
 450                         return -1;
 451                 remove_path(path);
 452         }
 453         return 0;
 454 }
 455
 456 static char *unique_path(const char *path, const char *branch)
 457 {
 458         char *newpath = xmalloc(strlen(path) + 1 + strlen(branch) + 8 + 1);
 459         int suffix = 0;
 460         struct stat st;
 461         char *p = newpath + strlen(path);
 462         strcpy(newpath, path);
 463         *(p++) = '~';
 464         strcpy(p, branch);
 465         for (; *p; ++p)
 466                 if ('/' == *p)
 467                         *p = '_';
 468         while (string_list_has_string(&current_file_set, newpath) ||
 469                string_list_has_string(&current_directory_set, newpath) ||
 470                lstat(newpath, &st) == 0)
 471                 sprintf(p, "_%d", suffix++);
 472
 473         string_list_insert(newpath, &current_file_set);
 474         return newpath;
 475 }
 476
 477 static void flush_buffer(int fd, const char *buf, unsigned long size)
 478 {
 479         while (size > 0) {
 480                 long ret = write_in_full(fd, buf, size);
 481                 if (ret < 0) {
 482                         /* Ignore epipe */
 483                         if (errno == EPIPE)
 484                                 break;
 485                         die("merge-recursive: %s", strerror(errno));
 486                 } else if (!ret) {
 487                         die("merge-recursive: disk full?");
 488                 }
 489                 size -= ret;
 490                 buf += ret;
 491         }
 492 }
 493
 494 static int make_room_for_path(const char *path)
 495 {
 496         int status;
 497         const char *msg = "failed to create path '%s'%s";
 498
 499         status = safe_create_leading_directories_const(path);
 500         if (status) {
 501                 if (status == -3) {
 502                         /* something else exists */
 503                         error(msg, path, ": perhaps a D/F conflict?");
 504                         return -1;
 505                 }
 506                 die(msg, path, "");
 507         }
 508
 509         /* Successful unlink is good.. */
 510         if (!unlink(path))
 511                 return 0;
 512         /* .. and so is no existing file */
 513         if (errno == ENOENT)
 514                 return 0;
 515         /* .. but not some other error (who really cares what?) */
 516         return error(msg, path, ": perhaps a D/F conflict?");
 517 }
 518
 519 static void update_file_flags(const unsigned char *sha,
 520                               unsigned mode,
 521                               const char *path,
 522                               int update_cache,
 523                               int update_wd)
 524 {
 525         if (index_only)
 526                 update_wd = 0;
 527
 528         if (update_wd) {
 529                 enum object_type type;
 530                 void *buf;
 531                 unsigned long size;
 532
 533                 if (S_ISGITLINK(mode))
 534                         die("cannot read object %s '%s': It is a submodule!",
 535                             sha1_to_hex(sha), path);
 536
 537                 buf = read_sha1_file(sha, &type, &size);
 538                 if (!buf)
 539                         die("cannot read object %s '%s'", sha1_to_hex(sha), path);
 540                 if (type != OBJ_BLOB)
 541                         die("blob expected for %s '%s'", sha1_to_hex(sha), path);
 542                 if (S_ISREG(mode)) {
 543                         struct strbuf strbuf;
 544                         strbuf_init(&strbuf, 0);
 545                         if (convert_to_working_tree(path, buf, size, &strbuf)) {
 546                                 free(buf);
 547                                 size = strbuf.len;
 548                                 buf = strbuf_detach(&strbuf, NULL);
 549                         }
 550                 }
 551
 552                 if (make_room_for_path(path) < 0) {
 553                         update_wd = 0;
 554                         free(buf);
 555                         goto update_index;
 556                 }
 557                 if (S_ISREG(mode) || (!has_symlinks && S_ISLNK(mode))) {
 558                         int fd;
 559                         if (mode & 0100)
 560                                 mode = 0777;
 561                         else
 562                                 mode = 0666;
 563                         fd = open(path, O_WRONLY | O_TRUNC | O_CREAT, mode);
 564                         if (fd < 0)
 565                                 die("failed to open %s: %s", path, strerror(errno));
 566                         flush_buffer(fd, buf, size);
 567                         close(fd);
 568                 } else if (S_ISLNK(mode)) {
 569                         char *lnk = xmemdupz(buf, size);
 570                         safe_create_leading_directories_const(path);
 571                         unlink(path);
 572                         symlink(lnk, path);
 573                         free(lnk);
 574                 } else
 575                         die("do not know what to do with %06o %s '%s'",
 576                             mode, sha1_to_hex(sha), path);
 577                 free(buf);
 578         }
 579  update_index:
 580         if (update_cache)
 581                 add_cacheinfo(mode, sha, path, 0, update_wd, ADD_CACHE_OK_TO_ADD);
 582 }
 583
 584 static void update_file(int clean,
 585                         const unsigned char *sha,
 586                         unsigned mode,
 587                         const char *path)
 588 {
 589         update_file_flags(sha, mode, path, index_only || clean, !index_only);
 590 }
 591
 592 /* Low level file merging, update and removal */
 593
 594 struct merge_file_info
 595 {
 596         unsigned char sha[20];
 597         unsigned mode;
 598         unsigned clean:1,
 599                  merge:1;
 600 };
 601
 602 static void fill_mm(const unsigned char *sha1, mmfile_t *mm)
 603 {
 604         unsigned long size;
 605         enum object_type type;
 606
 607         if (!hashcmp(sha1, null_sha1)) {
 608                 mm->ptr = xstrdup("");
 609                 mm->size = 0;
 610                 return;
 611         }
 612
 613         mm->ptr = read_sha1_file(sha1, &type, &size);
 614         if (!mm->ptr || type != OBJ_BLOB)
 615                 die("unable to read blob object %s", sha1_to_hex(sha1));
 616         mm->size = size;
 617 }
 618
 619 static int merge_3way(mmbuffer_t *result_buf,
 620                       struct diff_filespec *o,
 621                       struct diff_filespec *a,
 622                       struct diff_filespec *b,
 623                       const char *branch1,
 624                       const char *branch2)
 625 {
 626         mmfile_t orig, src1, src2;
 627         char *name1, *name2;
 628         int merge_status;
 629
 630         name1 = xstrdup(mkpath("%s:%s", branch1, a->path));
 631         name2 = xstrdup(mkpath("%s:%s", branch2, b->path));
 632
 633         fill_mm(o->sha1, &orig);
 634         fill_mm(a->sha1, &src1);
 635         fill_mm(b->sha1, &src2);
 636
 637         merge_status = ll_merge(result_buf, a->path, &orig,
 638                                 &src1, name1, &src2, name2,
 639                                 index_only);
 640
 641         free(name1);
 642         free(name2);
 643         free(orig.ptr);
 644         free(src1.ptr);
 645         free(src2.ptr);
 646         return merge_status;
 647 }
 648
 649 static struct merge_file_info merge_file(struct diff_filespec *o,
 650                 struct diff_filespec *a, struct diff_filespec *b,
 651                 const char *branch1, const char *branch2)
 652 {
 653         struct merge_file_info result;
 654         result.merge = 0;
 655         result.clean = 1;
 656
 657         if ((S_IFMT & a->mode) != (S_IFMT & b->mode)) {
 658                 result.clean = 0;
 659                 if (S_ISREG(a->mode)) {
 660                         result.mode = a->mode;
 661                         hashcpy(result.sha, a->sha1);
 662                 } else {
 663                         result.mode = b->mode;
 664                         hashcpy(result.sha, b->sha1);
 665                 }
 666         } else {
 667                 if (!sha_eq(a->sha1, o->sha1) && !sha_eq(b->sha1, o->sha1))
 668                         result.merge = 1;
 669
 670                 /*
 671                  * Merge modes
 672                  */
 673                 if (a->mode == b->mode || a->mode == o->mode)
 674                         result.mode = b->mode;
 675                 else {
 676                         result.mode = a->mode;
 677                         if (b->mode != o->mode) {
 678                                 result.clean = 0;
 679                                 result.merge = 1;
 680                         }
 681                 }
 682
 683                 if (sha_eq(a->sha1, b->sha1) || sha_eq(a->sha1, o->sha1))
 684                         hashcpy(result.sha, b->sha1);
 685                 else if (sha_eq(b->sha1, o->sha1))
 686                         hashcpy(result.sha, a->sha1);
 687                 else if (S_ISREG(a->mode)) {
 688                         mmbuffer_t result_buf;
 689                         int merge_status;
 690
 691                         merge_status = merge_3way(&result_buf, o, a, b,
 692                                                   branch1, branch2);
 693
 694                         if ((merge_status < 0) || !result_buf.ptr)
 695                                 die("Failed to execute internal merge");
 696
 697                         if (write_sha1_file(result_buf.ptr, result_buf.size,
 698                                             blob_type, result.sha))
 699                                 die("Unable to add %s to database",
 700                                     a->path);
 701
 702                         free(result_buf.ptr);
 703                         result.clean = (merge_status == 0);
 704                 } else if (S_ISGITLINK(a->mode)) {
 705                         result.clean = 0;
 706                         hashcpy(result.sha, a->sha1);
 707                 } else if (S_ISLNK(a->mode)) {
 708                         hashcpy(result.sha, a->sha1);
 709
 710                         if (!sha_eq(a->sha1, b->sha1))
 711                                 result.clean = 0;
 712                 } else {
 713                         die("unsupported object type in the tree");
 714                 }
 715         }
 716
 717         return result;
 718 }
 719
 720 static void conflict_rename_rename(struct rename *ren1,
 721                                    const char *branch1,
 722                                    struct rename *ren2,
 723                                    const char *branch2)
 724 {
 725         char *del[2];
 726         int delp = 0;
 727         const char *ren1_dst = ren1->pair->two->path;
 728         const char *ren2_dst = ren2->pair->two->path;
 729         const char *dst_name1 = ren1_dst;
 730         const char *dst_name2 = ren2_dst;
 731         if (string_list_has_string(&current_directory_set, ren1_dst)) {
 732                 dst_name1 = del[delp++] = unique_path(ren1_dst, branch1);
 733                 output(1, "%s is a directory in %s adding as %s instead",
 734                        ren1_dst, branch2, dst_name1);
 735                 remove_file(0, ren1_dst, 0);
 736         }
 737         if (string_list_has_string(&current_directory_set, ren2_dst)) {
 738                 dst_name2 = del[delp++] = unique_path(ren2_dst, branch2);
 739                 output(1, "%s is a directory in %s adding as %s instead",
 740                        ren2_dst, branch1, dst_name2);
 741                 remove_file(0, ren2_dst, 0);
 742         }
 743         if (index_only) {
 744                 remove_file_from_cache(dst_name1);
 745                 remove_file_from_cache(dst_name2);
 746                 /*
 747                  * Uncomment to leave the conflicting names in the resulting tree
 748                  *
 749                  * update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, dst_name1);
 750                  * update_file(0, ren2->pair->two->sha1, ren2->pair->two->mode, dst_name2);
 751                  */
 752         } else {
 753                 update_stages(dst_name1, NULL, ren1->pair->two, NULL, 1);
 754                 update_stages(dst_name2, NULL, NULL, ren2->pair->two, 1);
 755         }
 756         while (delp--)
 757                 free(del[delp]);
 758 }
 759
 760 static void conflict_rename_dir(struct rename *ren1,
 761                                 const char *branch1)
 762 {
 763         char *new_path = unique_path(ren1->pair->two->path, branch1);
 764         output(1, "Renaming %s to %s instead", ren1->pair->one->path, new_path);
 765         remove_file(0, ren1->pair->two->path, 0);
 766         update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, new_path);
 767         free(new_path);
 768 }
 769
 770 static void conflict_rename_rename_2(struct rename *ren1,
 771                                      const char *branch1,
 772                                      struct rename *ren2,
 773                                      const char *branch2)
 774 {
 775         char *new_path1 = unique_path(ren1->pair->two->path, branch1);
 776         char *new_path2 = unique_path(ren2->pair->two->path, branch2);
 777         output(1, "Renaming %s to %s and %s to %s instead",
 778                ren1->pair->one->path, new_path1,
 779                ren2->pair->one->path, new_path2);
 780         remove_file(0, ren1->pair->two->path, 0);
 781         update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, new_path1);
 782         update_file(0, ren2->pair->two->sha1, ren2->pair->two->mode, new_path2);
 783         free(new_path2);
 784         free(new_path1);
 785 }
 786
 787 static int process_renames(struct string_list *a_renames,
 788                            struct string_list *b_renames,
 789                            const char *a_branch,
 790                            const char *b_branch)
 791 {
 792         int clean_merge = 1, i, j;
 793         struct string_list a_by_dst = {NULL, 0, 0, 0}, b_by_dst = {NULL, 0, 0, 0};
 794         const struct rename *sre;
 795
 796         for (i = 0; i < a_renames->nr; i++) {
 797                 sre = a_renames->items[i].util;
 798                 string_list_insert(sre->pair->two->path, &a_by_dst)->util
 799                         = sre->dst_entry;
 800         }
 801         for (i = 0; i < b_renames->nr; i++) {
 802                 sre = b_renames->items[i].util;
 803                 string_list_insert(sre->pair->two->path, &b_by_dst)->util
 804                         = sre->dst_entry;
 805         }
 806
 807         for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {
 808                 int compare;
 809                 char *src;
 810                 struct string_list *renames1, *renames2, *renames2Dst;
 811                 struct rename *ren1 = NULL, *ren2 = NULL;
 812                 const char *branch1, *branch2;
 813                 const char *ren1_src, *ren1_dst;
 814
 815                 if (i >= a_renames->nr) {
 816                         compare = 1;
 817                         ren2 = b_renames->items[j++].util;
 818                 } else if (j >= b_renames->nr) {
 819                         compare = -1;
 820                         ren1 = a_renames->items[i++].util;
 821                 } else {
 822                         compare = strcmp(a_renames->items[i].string,
 823                                         b_renames->items[j].string);
 824                         if (compare <= 0)
 825                                 ren1 = a_renames->items[i++].util;
 826                         if (compare >= 0)
 827                                 ren2 = b_renames->items[j++].util;
 828                 }
 829
 830                 /* TODO: refactor, so that 1/2 are not needed */
 831                 if (ren1) {
 832                         renames1 = a_renames;
 833                         renames2 = b_renames;
 834                         renames2Dst = &b_by_dst;
 835                         branch1 = a_branch;
 836                         branch2 = b_branch;
 837                 } else {
 838                         struct rename *tmp;
 839                         renames1 = b_renames;
 840                         renames2 = a_renames;
 841                         renames2Dst = &a_by_dst;
 842                         branch1 = b_branch;
 843                         branch2 = a_branch;
 844                         tmp = ren2;
 845                         ren2 = ren1;
 846                         ren1 = tmp;
 847                 }
 848                 src = ren1->pair->one->path;
 849
 850                 ren1->dst_entry->processed = 1;
 851                 ren1->src_entry->processed = 1;
 852
 853                 if (ren1->processed)
 854                         continue;
 855                 ren1->processed = 1;
 856
 857                 ren1_src = ren1->pair->one->path;
 858                 ren1_dst = ren1->pair->two->path;
 859
 860                 if (ren2) {
 861                         const char *ren2_src = ren2->pair->one->path;
 862                         const char *ren2_dst = ren2->pair->two->path;
 863                         /* Renamed in 1 and renamed in 2 */
 864                         if (strcmp(ren1_src, ren2_src) != 0)
 865                                 die("ren1.src != ren2.src");
 866                         ren2->dst_entry->processed = 1;
 867                         ren2->processed = 1;
 868                         if (strcmp(ren1_dst, ren2_dst) != 0) {
 869                                 clean_merge = 0;
 870                                 output(1, "CONFLICT (rename/rename): "
 871                                        "Rename \"%s\"->\"%s\" in branch \"%s\" "
 872                                        "rename \"%s\"->\"%s\" in \"%s\"%s",
 873                                        src, ren1_dst, branch1,
 874                                        src, ren2_dst, branch2,
 875                                        index_only ? " (left unresolved)": "");
 876                                 if (index_only) {
 877                                         remove_file_from_cache(src);
 878                                         update_file(0, ren1->pair->one->sha1,
 879                                                     ren1->pair->one->mode, src);
 880                                 }
 881                                 conflict_rename_rename(ren1, branch1, ren2, branch2);
 882                         } else {
 883                                 struct merge_file_info mfi;
 884                                 remove_file(1, ren1_src, 1);
 885                                 mfi = merge_file(ren1->pair->one,
 886                                                  ren1->pair->two,
 887                                                  ren2->pair->two,
 888                                                  branch1,
 889                                                  branch2);
 890                                 if (mfi.merge || !mfi.clean)
 891                                         output(1, "Renaming %s->%s", src, ren1_dst);
 892
 893                                 if (mfi.merge)
 894                                         output(2, "Auto-merging %s", ren1_dst);
 895
 896                                 if (!mfi.clean) {
 897                                         output(1, "CONFLICT (content): merge conflict in %s",
 898                                                ren1_dst);
 899                                         clean_merge = 0;
 900
 901                                         if (!index_only)
 902                                                 update_stages(ren1_dst,
 903                                                               ren1->pair->one,
 904                                                               ren1->pair->two,
 905                                                               ren2->pair->two,
 906                                                               1 /* clear */);
 907                                 }
 908                                 update_file(mfi.clean, mfi.sha, mfi.mode, ren1_dst);
 909                         }
 910                 } else {
 911                         /* Renamed in 1, maybe changed in 2 */
 912                         struct string_list_item *item;
 913                         /* we only use sha1 and mode of these */
 914                         struct diff_filespec src_other, dst_other;
 915                         int try_merge, stage = a_renames == renames1 ? 3: 2;
 916
 917                         remove_file(1, ren1_src, index_only || stage == 3);
 918
 919                         hashcpy(src_other.sha1, ren1->src_entry->stages[stage].sha);
 920                         src_other.mode = ren1->src_entry->stages[stage].mode;
 921                         hashcpy(dst_other.sha1, ren1->dst_entry->stages[stage].sha);
 922                         dst_other.mode = ren1->dst_entry->stages[stage].mode;
 923
 924                         try_merge = 0;
 925
 926                         if (string_list_has_string(&current_directory_set, ren1_dst)) {
 927                                 clean_merge = 0;
 928                                 output(1, "CONFLICT (rename/directory): Rename %s->%s in %s "
 929                                        " directory %s added in %s",
 930                                        ren1_src, ren1_dst, branch1,
 931                                        ren1_dst, branch2);
 932                                 conflict_rename_dir(ren1, branch1);
 933                         } else if (sha_eq(src_other.sha1, null_sha1)) {
 934                                 clean_merge = 0;
 935                                 output(1, "CONFLICT (rename/delete): Rename %s->%s in %s "
 936                                        "and deleted in %s",
 937                                        ren1_src, ren1_dst, branch1,
 938                                        branch2);
 939                                 update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, ren1_dst);
 940                         } else if (!sha_eq(dst_other.sha1, null_sha1)) {
 941                                 const char *new_path;
 942                                 clean_merge = 0;
 943                                 try_merge = 1;
 944                                 output(1, "CONFLICT (rename/add): Rename %s->%s in %s. "
 945                                        "%s added in %s",
 946                                        ren1_src, ren1_dst, branch1,
 947                                        ren1_dst, branch2);
 948                                 new_path = unique_path(ren1_dst, branch2);
 949                                 output(1, "Adding as %s instead", new_path);
 950                                 update_file(0, dst_other.sha1, dst_other.mode, new_path);
 951                         } else if ((item = string_list_lookup(ren1_dst, renames2Dst))) {
 952                                 ren2 = item->util;
 953                                 clean_merge = 0;
 954                                 ren2->processed = 1;
 955                                 output(1, "CONFLICT (rename/rename): Rename %s->%s in %s. "
 956                                        "Rename %s->%s in %s",
 957                                        ren1_src, ren1_dst, branch1,
 958                                        ren2->pair->one->path, ren2->pair->two->path, branch2);
 959                                 conflict_rename_rename_2(ren1, branch1, ren2, branch2);
 960                         } else
 961                                 try_merge = 1;
 962
 963                         if (try_merge) {
 964                                 struct diff_filespec *o, *a, *b;
 965                                 struct merge_file_info mfi;
 966                                 src_other.path = (char *)ren1_src;
 967
 968                                 o = ren1->pair->one;
 969                                 if (a_renames == renames1) {
 970                                         a = ren1->pair->two;
 971                                         b = &src_other;
 972                                 } else {
 973                                         b = ren1->pair->two;
 974                                         a = &src_other;
 975                                 }
 976                                 mfi = merge_file(o, a, b,
 977                                                 a_branch, b_branch);
 978
 979                                 if (mfi.clean &&
 980                                     sha_eq(mfi.sha, ren1->pair->two->sha1) &&
 981                                     mfi.mode == ren1->pair->two->mode)
 982                                         /*
 983                                          * This messaged is part of
 984                                          * t6022 test. If you change
 985                                          * it update the test too.
 986                                          */
 987                                         output(3, "Skipped %s (merged same as existing)", ren1_dst);
 988                                 else {
 989                                         if (mfi.merge || !mfi.clean)
 990                                                 output(1, "Renaming %s => %s", ren1_src, ren1_dst);
 991                                         if (mfi.merge)
 992                                                 output(2, "Auto-merging %s", ren1_dst);
 993                                         if (!mfi.clean) {
 994                                                 output(1, "CONFLICT (rename/modify): Merge conflict in %s",
 995                                                        ren1_dst);
 996                                                 clean_merge = 0;
 997
 998                                                 if (!index_only)
 999                                                         update_stages(ren1_dst,
1000                                                                       o, a, b, 1);
1001                                         }
1002                                         update_file(mfi.clean, mfi.sha, mfi.mode, ren1_dst);
1003                                 }
1004                         }
1005                 }
1006         }
1007         string_list_clear(&a_by_dst, 0);
1008         string_list_clear(&b_by_dst, 0);
1009
1010         return clean_merge;
1011 }
1012
1013 static unsigned char *stage_sha(const unsigned char *sha, unsigned mode)
1014 {
1015         return (is_null_sha1(sha) || mode == 0) ? NULL: (unsigned char *)sha;
1016 }
1017
1018 /* Per entry merge function */
1019 static int process_entry(const char *path, struct stage_data *entry,
1020                          const char *branch1,
1021                          const char *branch2)
1022 {
1023         /*
1024         printf("processing entry, clean cache: %s\n", index_only ? "yes": "no");
1025         print_index_entry("\tpath: ", entry);
1026         */
1027         int clean_merge = 1;
1028         unsigned o_mode = entry->stages[1].mode;
1029         unsigned a_mode = entry->stages[2].mode;
1030         unsigned b_mode = entry->stages[3].mode;
1031         unsigned char *o_sha = stage_sha(entry->stages[1].sha, o_mode);
1032         unsigned char *a_sha = stage_sha(entry->stages[2].sha, a_mode);
1033         unsigned char *b_sha = stage_sha(entry->stages[3].sha, b_mode);
1034
1035         if (o_sha && (!a_sha || !b_sha)) {
1036                 /* Case A: Deleted in one */
1037                 if ((!a_sha && !b_sha) ||
1038                     (sha_eq(a_sha, o_sha) && !b_sha) ||
1039                     (!a_sha && sha_eq(b_sha, o_sha))) {
1040                         /* Deleted in both or deleted in one and
1041                          * unchanged in the other */
1042                         if (a_sha)
1043                                 output(2, "Removing %s", path);
1044                         /* do not touch working file if it did not exist */
1045                         remove_file(1, path, !a_sha);
1046                 } else {
1047                         /* Deleted in one and changed in the other */
1048                         clean_merge = 0;
1049                         if (!a_sha) {
1050                                 output(1, "CONFLICT (delete/modify): %s deleted in %s "
1051                                        "and modified in %s. Version %s of %s left in tree.",
1052                                        path, branch1,
1053                                        branch2, branch2, path);
1054                                 update_file(0, b_sha, b_mode, path);
1055                         } else {
1056                                 output(1, "CONFLICT (delete/modify): %s deleted in %s "
1057                                        "and modified in %s. Version %s of %s left in tree.",
1058                                        path, branch2,
1059                                        branch1, branch1, path);
1060                                 update_file(0, a_sha, a_mode, path);
1061                         }
1062                 }
1063
1064         } else if ((!o_sha && a_sha && !b_sha) ||
1065                    (!o_sha && !a_sha && b_sha)) {
1066                 /* Case B: Added in one. */
1067                 const char *add_branch;
1068                 const char *other_branch;
1069                 unsigned mode;
1070                 const unsigned char *sha;
1071                 const char *conf;
1072
1073                 if (a_sha) {
1074                         add_branch = branch1;
1075                         other_branch = branch2;
1076                         mode = a_mode;
1077                         sha = a_sha;
1078                         conf = "file/directory";
1079                 } else {
1080                         add_branch = branch2;
1081                         other_branch = branch1;
1082                         mode = b_mode;
1083                         sha = b_sha;
1084                         conf = "directory/file";
1085                 }
1086                 if (string_list_has_string(&current_directory_set, path)) {
1087                         const char *new_path = unique_path(path, add_branch);
1088                         clean_merge = 0;
1089                         output(1, "CONFLICT (%s): There is a directory with name %s in %s. "
1090                                "Adding %s as %s",
1091                                conf, path, other_branch, path, new_path);
1092                         remove_file(0, path, 0);
1093                         update_file(0, sha, mode, new_path);
1094                 } else {
1095                         output(2, "Adding %s", path);
1096                         update_file(1, sha, mode, path);
1097                 }
1098         } else if (a_sha && b_sha) {
1099                 /* Case C: Added in both (check for same permissions) and */
1100                 /* case D: Modified in both, but differently. */
1101                 const char *reason = "content";
1102                 struct merge_file_info mfi;
1103                 struct diff_filespec o, a, b;
1104
1105                 if (!o_sha) {
1106                         reason = "add/add";
1107                         o_sha = (unsigned char *)null_sha1;
1108                 }
1109                 output(2, "Auto-merging %s", path);
1110                 o.path = a.path = b.path = (char *)path;
1111                 hashcpy(o.sha1, o_sha);
1112                 o.mode = o_mode;
1113                 hashcpy(a.sha1, a_sha);
1114                 a.mode = a_mode;
1115                 hashcpy(b.sha1, b_sha);
1116                 b.mode = b_mode;
1117
1118                 mfi = merge_file(&o, &a, &b,
1119                                  branch1, branch2);
1120
1121                 clean_merge = mfi.clean;
1122                 if (mfi.clean)
1123                         update_file(1, mfi.sha, mfi.mode, path);
1124                 else if (S_ISGITLINK(mfi.mode))
1125                         output(1, "CONFLICT (submodule): Merge conflict in %s "
1126                                "- needs %s", path, sha1_to_hex(b.sha1));
1127                 else {
1128                         output(1, "CONFLICT (%s): Merge conflict in %s",
1129                                         reason, path);
1130
1131                         if (index_only)
1132                                 update_file(0, mfi.sha, mfi.mode, path);
1133                         else
1134                                 update_file_flags(mfi.sha, mfi.mode, path,
1135                                               0 /* update_cache */, 1 /* update_working_directory */);
1136                 }
1137         } else if (!o_sha && !a_sha && !b_sha) {
1138                 /*
1139                  * this entry was deleted altogether. a_mode == 0 means
1140                  * we had that path and want to actively remove it.
1141                  */
1142                 remove_file(1, path, !a_mode);
1143         } else
1144                 die("Fatal merge failure, shouldn't happen.");
1145
1146         return clean_merge;
1147 }
1148
1149 int merge_trees(struct tree *head,
1150                 struct tree *merge,
1151                 struct tree *common,
1152                 const char *branch1,
1153                 const char *branch2,
1154                 struct tree **result)
1155 {
1156         int code, clean;
1157
1158         if (subtree_merge) {
1159                 merge = shift_tree_object(head, merge);
1160                 common = shift_tree_object(head, common);
1161         }
1162
1163         if (sha_eq(common->object.sha1, merge->object.sha1)) {
1164                 output(0, "Already uptodate!");
1165                 *result = head;
1166                 return 1;
1167         }
1168
1169         code = git_merge_trees(index_only, common, head, merge);
1170
1171         if (code != 0)
1172                 die("merging of trees %s and %s failed",
1173                     sha1_to_hex(head->object.sha1),
1174                     sha1_to_hex(merge->object.sha1));
1175
1176         if (unmerged_cache()) {
1177                 struct string_list *entries, *re_head, *re_merge;
1178                 int i;
1179                 string_list_clear(&current_file_set, 1);
1180                 string_list_clear(&current_directory_set, 1);
1181                 get_files_dirs(head);
1182                 get_files_dirs(merge);
1183
1184                 entries = get_unmerged();
1185                 re_head  = get_renames(head, common, head, merge, entries);
1186                 re_merge = get_renames(merge, common, head, merge, entries);
1187                 clean = process_renames(re_head, re_merge,
1188                                 branch1, branch2);
1189                 for (i = 0; i < entries->nr; i++) {
1190                         const char *path = entries->items[i].string;
1191                         struct stage_data *e = entries->items[i].util;
1192                         if (!e->processed
1193                                 && !process_entry(path, e, branch1, branch2))
1194                                 clean = 0;
1195                 }
1196
1197                 string_list_clear(re_merge, 0);
1198                 string_list_clear(re_head, 0);
1199                 string_list_clear(entries, 1);
1200
1201         }
1202         else
1203                 clean = 1;
1204
1205         if (index_only)
1206                 *result = write_tree_from_memory();
1207
1208         return clean;
1209 }
1210
1211 static struct commit_list *reverse_commit_list(struct commit_list *list)
1212 {
1213         struct commit_list *next = NULL, *current, *backup;
1214         for (current = list; current; current = backup) {
1215                 backup = current->next;
1216                 current->next = next;
1217                 next = current;
1218         }
1219         return next;
1220 }
1221
1222 /*
1223  * Merge the commits h1 and h2, return the resulting virtual
1224  * commit object and a flag indicating the cleanness of the merge.
1225  */
1226 int merge_recursive(struct commit *h1,
1227                     struct commit *h2,
1228                     const char *branch1,
1229                     const char *branch2,
1230                     struct commit_list *ca,
1231                     struct commit **result)
1232 {
1233         struct commit_list *iter;
1234         struct commit *merged_common_ancestors;
1235         struct tree *mrtree = mrtree;
1236         int clean;
1237
1238         if (show(4)) {
1239                 output(4, "Merging:");
1240                 output_commit_title(h1);
1241                 output_commit_title(h2);
1242         }
1243
1244         if (!ca) {
1245                 ca = get_merge_bases(h1, h2, 1);
1246                 ca = reverse_commit_list(ca);
1247         }
1248
1249         if (show(5)) {
1250                 output(5, "found %u common ancestor(s):", commit_list_count(ca));
1251                 for (iter = ca; iter; iter = iter->next)
1252                         output_commit_title(iter->item);
1253         }
1254
1255         merged_common_ancestors = pop_commit(&ca);
1256         if (merged_common_ancestors == NULL) {
1257                 /* if there is no common ancestor, make an empty tree */
1258                 struct tree *tree = xcalloc(1, sizeof(struct tree));
1259
1260                 tree->object.parsed = 1;
1261                 tree->object.type = OBJ_TREE;
1262                 pretend_sha1_file(NULL, 0, OBJ_TREE, tree->object.sha1);
1263                 merged_common_ancestors = make_virtual_commit(tree, "ancestor");
1264         }
1265
1266         for (iter = ca; iter; iter = iter->next) {
1267                 call_depth++;
1268                 /*
1269                  * When the merge fails, the result contains files
1270                  * with conflict markers. The cleanness flag is
1271                  * ignored, it was never actually used, as result of
1272                  * merge_trees has always overwritten it: the committed
1273                  * "conflicts" were already resolved.
1274                  */
1275                 discard_cache();
1276                 merge_recursive(merged_common_ancestors, iter->item,
1277                                 "Temporary merge branch 1",
1278                                 "Temporary merge branch 2",
1279                                 NULL,
1280                                 &merged_common_ancestors);
1281                 call_depth--;
1282
1283                 if (!merged_common_ancestors)
1284                         die("merge returned no commit");
1285         }
1286
1287         discard_cache();
1288         if (!call_depth) {
1289                 read_cache();
1290                 index_only = 0;
1291         } else
1292                 index_only = 1;
1293
1294         clean = merge_trees(h1->tree, h2->tree, merged_common_ancestors->tree,
1295                             branch1, branch2, &mrtree);
1296
1297         if (index_only) {
1298                 *result = make_virtual_commit(mrtree, "merged tree");
1299                 commit_list_insert(h1, &(*result)->parents);
1300                 commit_list_insert(h2, &(*result)->parents->next);
1301         }
1302         flush_output();
1303         return clean;
1304 }
1305
1306 static struct commit *get_ref(const unsigned char *sha1, const char *name)
1307 {
1308         struct object *object;
1309
1310         object = deref_tag(parse_object(sha1), name, strlen(name));
1311         if (!object)
1312                 return NULL;
1313         if (object->type == OBJ_TREE)
1314                 return make_virtual_commit((struct tree*)object, name);
1315         if (object->type != OBJ_COMMIT)
1316                 return NULL;
1317         if (parse_commit((struct commit *)object))
1318                 return NULL;
1319         return (struct commit *)object;
1320 }
1321
1322 int merge_recursive_generic(const char **base_list,
1323                 const unsigned char *head_sha1, const char *head_name,
1324                 const unsigned char *next_sha1, const char *next_name)
1325 {
1326         int clean, index_fd;
1327         struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));
1328         struct commit *result;
1329         struct commit *head_commit = get_ref(head_sha1, head_name);
1330         struct commit *next_commit = get_ref(next_sha1, next_name);
1331         struct commit_list *ca = NULL;
1332
1333         if (base_list) {
1334                 int i;
1335                 for (i = 0; base_list[i]; ++i) {
1336                         unsigned char sha[20];
1337                         struct commit *base;
1338                         if (get_sha1(base_list[i], sha))
1339                                 return error("Could not resolve ref '%s'",
1340                                                                 base_list[i]);
1341                         if (!(base = get_ref(sha, base_list[i])))
1342                                 return error("Could not parse object '%s'",
1343                                                                 base_list[i]);
1344                         commit_list_insert(base, &ca);
1345                 }
1346         }
1347
1348         index_fd = hold_locked_index(lock, 1);
1349         clean = merge_recursive(head_commit, next_commit,
1350                                 head_name, next_name, ca, &result);
1351         if (active_cache_changed &&
1352                         (write_cache(index_fd, active_cache, active_nr) ||
1353                          commit_locked_index(lock)))
1354                 return error("Unable to write index.");
1355
1356         return clean ? 0 : 1;
1357 }
1358
1359 int merge_recursive_config(const char *var, const char *value, void *cb)
1360 {
1361         if (!strcasecmp(var, "merge.verbosity")) {
1362                 merge_recursive_verbosity = git_config_int(var, value);
1363                 return 0;
1364         }
1365         if (!strcasecmp(var, "diff.renamelimit")) {
1366                 diff_rename_limit = git_config_int(var, value);
1367                 return 0;
1368         }
1369         if (!strcasecmp(var, "merge.renamelimit")) {
1370                 merge_rename_limit = git_config_int(var, value);
1371                 return 0;
1372         }
1373         return git_default_config(var, value, cb);
1374 }
1375
1376 void merge_recursive_setup(int is_subtree_merge)
1377 {
1378         if (getenv("GIT_MERGE_VERBOSITY"))
1379                 merge_recursive_verbosity =
1380                         strtol(getenv("GIT_MERGE_VERBOSITY"), NULL, 10);
1381         if (merge_recursive_verbosity >= 5)
1382                 buffer_output = 0;
1383         subtree_merge = is_subtree_merge;
1384 }