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 <stdarg.h>
   7 #include <string.h>
   8 #include <assert.h>
   9 #include <sys/wait.h>
  10 #include <sys/types.h>
  11 #include <sys/stat.h>
  12 #include <time.h>
  13 #include "cache.h"
  14 #include "cache-tree.h"
  15 #include "commit.h"
  16 #include "blob.h"
  17 #include "tree-walk.h"
  18 #include "diff.h"
  19 #include "diffcore.h"
  20 #include "run-command.h"
  21 #include "tag.h"
  22
  23 #include "path-list.h"
  24
  25 /*#define DEBUG*/
  26
  27 #ifdef DEBUG
  28 #define debug(args, ...) fprintf(stderr, args, ## __VA_ARGS__)
  29 #else
  30 #define debug(args, ...)
  31 #endif
  32
  33 #ifdef DEBUG
  34 #include "quote.h"
  35 static void show_ce_entry(const char *tag, struct cache_entry *ce)
  36 {
  37         if (tag && *tag &&
  38             (ce->ce_flags & htons(CE_VALID))) {
  39                 static char alttag[4];
  40                 memcpy(alttag, tag, 3);
  41                 if (isalpha(tag[0]))
  42                         alttag[0] = tolower(tag[0]);
  43                 else if (tag[0] == '?')
  44                         alttag[0] = '!';
  45                 else {
  46                         alttag[0] = 'v';
  47                         alttag[1] = tag[0];
  48                         alttag[2] = ' ';
  49                         alttag[3] = 0;
  50                 }
  51                 tag = alttag;
  52         }
  53
  54         fprintf(stderr,"%s%06o %s %d\t",
  55                         tag,
  56                         ntohl(ce->ce_mode),
  57                         sha1_to_hex(ce->sha1),
  58                         ce_stage(ce));
  59         write_name_quoted("", 0, ce->name,
  60                         '\n', stderr);
  61         fputc('\n', stderr);
  62 }
  63
  64 static void ls_files() {
  65         int i;
  66         for (i = 0; i < active_nr; i++) {
  67                 struct cache_entry *ce = active_cache[i];
  68                 show_ce_entry("", ce);
  69         }
  70         fprintf(stderr, "---\n");
  71 }
  72 #endif
  73
  74 /*
  75  * A virtual commit has
  76  * - (const char *)commit->util set to the name, and
  77  * - *(int *)commit->object.sha1 set to the virtual id.
  78  */
  79 static const char *commit_title(struct commit *commit, int *len)
  80 {
  81         const char *s = "(null commit)";
  82         *len = strlen(s);
  83
  84         if ( commit->util ) {
  85                 s = commit->util;
  86                 *len = strlen(s);
  87         } else {
  88                 if ( parse_commit(commit) != 0 ) {
  89                         s = "(bad commit)";
  90                         *len = strlen(s);
  91                 } else {
  92                         s = commit->buffer;
  93                         char prev = '\0';
  94                         while ( *s ) {
  95                                 if ( '\n' == prev && '\n' == *s ) {
  96                                         ++s;
  97                                         break;
  98                                 }
  99                                 prev = *s++;
 100                         }
 101                         *len = 0;
 102                         while ( s[*len] && '\n' != s[*len] )
 103                                 ++(*len);
 104                 }
 105         }
 106         return s;
 107 }
 108
 109 static const char *commit_hex_sha1(const struct commit *commit)
 110 {
 111         return commit->util ? "virtual" : commit ?
 112                 sha1_to_hex(commit->object.sha1) : "undefined";
 113 }
 114
 115 static unsigned commit_list_count(const struct commit_list *l)
 116 {
 117         unsigned c = 0;
 118         for (; l; l = l->next )
 119                 c++;
 120         return c;
 121 }
 122
 123 static struct commit *make_virtual_commit(struct tree *tree, const char *comment)
 124 {
 125         struct commit *commit = xcalloc(1, sizeof(struct commit));
 126         static unsigned virtual_id = 1;
 127         commit->tree = tree;
 128         commit->util = (void*)comment;
 129         *(int*)commit->object.sha1 = virtual_id++;
 130         return commit;
 131 }
 132
 133 /*
 134  * TODO: we should not have to copy the SHA1s around, but rather reference
 135  * them. That way, sha_eq() is just sha1 == sha2.
 136  */
 137 static int sha_eq(const unsigned char *a, const unsigned char *b)
 138 {
 139         if ( !a && !b )
 140                 return 2;
 141         return a && b && memcmp(a, b, 20) == 0;
 142 }
 143
 144 static void memswp(void *p1, void *p2, unsigned n)
 145 {
 146         unsigned char *a = p1, *b = p2;
 147         while ( n-- ) {
 148                 *a ^= *b;
 149                 *b ^= *a;
 150                 *a ^= *b;
 151                 ++a;
 152                 ++b;
 153         }
 154 }
 155
 156 /*
 157  * TODO: we should convert the merge_result users to
 158  *      int blabla(..., struct commit **result)
 159  * like everywhere else in git.
 160  * Same goes for merge_tree_result and merge_file_info.
 161  */
 162 struct merge_result
 163 {
 164         struct commit *commit;
 165         unsigned clean:1;
 166 };
 167
 168 struct merge_tree_result
 169 {
 170         struct tree *tree;
 171         unsigned clean:1;
 172 };
 173
 174 /*
 175  * TODO: check if we can just reuse the active_cache structure: it is already
 176  * sorted (by name, stage).
 177  * Only problem: do not write it when flushing the cache.
 178  */
 179 struct stage_data
 180 {
 181         struct
 182         {
 183                 unsigned mode;
 184                 unsigned char sha[20];
 185         } stages[4];
 186         unsigned processed:1;
 187 };
 188
 189 static struct path_list currentFileSet = {NULL, 0, 0, 1};
 190 static struct path_list currentDirectorySet = {NULL, 0, 0, 1};
 191
 192 static int output_indent = 0;
 193
 194 static void output(const char *fmt, ...)
 195 {
 196         va_list args;
 197         int i;
 198         for ( i = output_indent; i--; )
 199                 fputs("  ", stdout);
 200         va_start(args, fmt);
 201         vfprintf(stdout, fmt, args);
 202         va_end(args);
 203         fputc('\n', stdout);
 204 }
 205
 206 static const char *original_index_file;
 207 static const char *temporary_index_file;
 208 static int cache_dirty = 0;
 209
 210 static int flush_cache()
 211 {
 212         /* flush temporary index */
 213         struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));
 214         int fd = hold_lock_file_for_update(lock, getenv("GIT_INDEX_FILE"));
 215         if (fd < 0)
 216                 die("could not lock %s", temporary_index_file);
 217         if (write_cache(fd, active_cache, active_nr) ||
 218                         close(fd) || commit_lock_file(lock))
 219                 die ("unable to write %s", getenv("GIT_INDEX_FILE"));
 220         discard_cache();
 221         cache_dirty = 0;
 222         return 0;
 223 }
 224
 225 static void setup_index(int temp)
 226 {
 227         const char *idx = temp ? temporary_index_file: original_index_file;
 228         if (cache_dirty)
 229                 die("fatal: cache changed flush_cache();");
 230         unlink(temporary_index_file);
 231         setenv("GIT_INDEX_FILE", idx, 1);
 232         discard_cache();
 233 }
 234
 235 static struct cache_entry *make_cache_entry(unsigned int mode,
 236                 const unsigned char *sha1, const char *path, int stage, int refresh)
 237 {
 238         int size, len;
 239         struct cache_entry *ce;
 240
 241         if (!verify_path(path))
 242                 return NULL;
 243
 244         len = strlen(path);
 245         size = cache_entry_size(len);
 246         ce = xcalloc(1, size);
 247
 248         memcpy(ce->sha1, sha1, 20);
 249         memcpy(ce->name, path, len);
 250         ce->ce_flags = create_ce_flags(len, stage);
 251         ce->ce_mode = create_ce_mode(mode);
 252
 253         if (refresh)
 254                 return refresh_cache_entry(ce, 0);
 255
 256         return ce;
 257 }
 258
 259 static int add_cacheinfo(unsigned int mode, const unsigned char *sha1,
 260                 const char *path, int stage, int refresh, int options)
 261 {
 262         struct cache_entry *ce;
 263         if (!cache_dirty)
 264                 read_cache_from(getenv("GIT_INDEX_FILE"));
 265         cache_dirty++;
 266         ce = make_cache_entry(mode, sha1 ? sha1 : null_sha1, path, stage, refresh);
 267         if (!ce)
 268                 return error("cache_addinfo failed: %s", strerror(cache_errno));
 269         return add_cache_entry(ce, options);
 270 }
 271
 272 /*
 273  * This is a global variable which is used in a number of places but
 274  * only written to in the 'merge' function.
 275  *
 276  * index_only == 1    => Don't leave any non-stage 0 entries in the cache and
 277  *                       don't update the working directory.
 278  *               0    => Leave unmerged entries in the cache and update
 279  *                       the working directory.
 280  */
 281 static int index_only = 0;
 282
 283 /*
 284  * TODO: this can be streamlined by refactoring builtin-read-tree.c
 285  */
 286 static int git_read_tree(const struct tree *tree)
 287 {
 288 #if 0
 289         fprintf(stderr, "GIT_INDEX_FILE='%s' git-read-tree %s\n",
 290                 getenv("GIT_INDEX_FILE"),
 291                 sha1_to_hex(tree->object.sha1));
 292 #endif
 293         const char *argv[] = { "git-read-tree", NULL, NULL, };
 294         if (cache_dirty)
 295                 die("read-tree with dirty cache");
 296         argv[1] = sha1_to_hex(tree->object.sha1);
 297         int rc = run_command_v(2, argv);
 298         return rc < 0 ? -1: rc;
 299 }
 300
 301 /*
 302  * TODO: this can be streamlined by refactoring builtin-read-tree.c
 303  */
 304 static int git_merge_trees(const char *update_arg,
 305                            struct tree *common,
 306                            struct tree *head,
 307                            struct tree *merge)
 308 {
 309 #if 0
 310         fprintf(stderr, "GIT_INDEX_FILE='%s' git-read-tree %s -m %s %s %s\n",
 311                 getenv("GIT_INDEX_FILE"),
 312                 update_arg,
 313                 sha1_to_hex(common->object.sha1),
 314                 sha1_to_hex(head->object.sha1),
 315                 sha1_to_hex(merge->object.sha1));
 316 #endif
 317         const char *argv[] = {
 318                 "git-read-tree", NULL, "-m", NULL, NULL, NULL,
 319                 NULL,
 320         };
 321         if (cache_dirty)
 322                 flush_cache();
 323         argv[1] = update_arg;
 324         argv[3] = sha1_to_hex(common->object.sha1);
 325         argv[4] = sha1_to_hex(head->object.sha1);
 326         argv[5] = sha1_to_hex(merge->object.sha1);
 327         int rc = run_command_v(6, argv);
 328         return rc < 0 ? -1: rc;
 329 }
 330
 331 /*
 332  * TODO: this can be streamlined by refactoring builtin-write-tree.c
 333  */
 334 static struct tree *git_write_tree()
 335 {
 336 #if 0
 337         fprintf(stderr, "GIT_INDEX_FILE='%s' git-write-tree\n",
 338                 getenv("GIT_INDEX_FILE"));
 339 #endif
 340         if (cache_dirty)
 341                 flush_cache();
 342         FILE *fp = popen("git-write-tree 2>/dev/null", "r");
 343         char buf[41];
 344         unsigned char sha1[20];
 345         int ch;
 346         unsigned i = 0;
 347         while ( (ch = fgetc(fp)) != EOF )
 348                 if ( i < sizeof(buf)-1 && ch >= '0' && ch <= 'f' )
 349                         buf[i++] = ch;
 350                 else
 351                         break;
 352         int rc = pclose(fp);
 353         if ( rc == -1 || WEXITSTATUS(rc) )
 354                 return NULL;
 355         buf[i] = '\0';
 356         if ( get_sha1(buf, sha1) != 0 )
 357                 return NULL;
 358         return lookup_tree(sha1);
 359 }
 360
 361 /*
 362  * TODO: get rid of files_and_dirs; we do not use it except for
 363  * current_file_set and current_dir_set, which are global already.
 364  */
 365 static struct
 366 {
 367         struct path_list *files;
 368         struct path_list *dirs;
 369 } files_and_dirs;
 370
 371 static int save_files_dirs(const unsigned char *sha1,
 372                 const char *base, int baselen, const char *path,
 373                 unsigned int mode, int stage)
 374 {
 375         int len = strlen(path);
 376         char *newpath = malloc(baselen + len + 1);
 377         memcpy(newpath, base, baselen);
 378         memcpy(newpath + baselen, path, len);
 379         newpath[baselen + len] = '\0';
 380
 381         if (S_ISDIR(mode))
 382                 path_list_insert(newpath, files_and_dirs.dirs);
 383         else
 384                 path_list_insert(newpath, files_and_dirs.files);
 385         free(newpath);
 386
 387         return READ_TREE_RECURSIVE;
 388 }
 389
 390 static int get_files_dirs(struct tree *tree,
 391                           struct path_list *files,
 392                           struct path_list *dirs)
 393 {
 394         int n;
 395         files_and_dirs.files = files;
 396         files_and_dirs.dirs = dirs;
 397         debug("get_files_dirs ...\n");
 398         if (read_tree_recursive(tree, "", 0, 0, NULL, save_files_dirs) != 0) {
 399                 debug("  get_files_dirs done (0)\n");
 400                 return 0;
 401         }
 402         n = files->nr + dirs->nr;
 403         debug("  get_files_dirs done (%d)\n", n);
 404         return n;
 405 }
 406
 407 /*
 408  * TODO: this wrapper is so small, we can use path_list_lookup directly.
 409  * Same goes for index_entry_get(), free_index_entries(), find_rename_bysrc(),
 410  * free_rename_entries().
 411  */
 412 static struct stage_data *index_entry_find(struct path_list *ents,
 413                                             const char *path)
 414 {
 415         struct path_list_item *item = path_list_lookup(path, ents);
 416         if (item)
 417                 return item->util;
 418         return NULL;
 419 }
 420
 421 static struct stage_data *index_entry_get(struct path_list *ents,
 422                                            const char *path)
 423 {
 424         struct path_list_item *item = path_list_lookup(path, ents);
 425
 426         if (item == NULL) {
 427                 item = path_list_insert(path, ents);
 428                 item->util = xcalloc(1, sizeof(struct stage_data));
 429         }
 430         return item->util;
 431 }
 432
 433 /*
 434  * TODO: since the result of index_entry_from_db() is tucked into a
 435  * path_list anyway, this helper can do that already.
 436  */
 437 /*
 438  * Returns a index_entry instance which doesn't have to correspond to
 439  * a real cache entry in Git's index.
 440  */
 441 static struct stage_data *index_entry_from_db(const char *path,
 442                                                struct tree *o,
 443                                                struct tree *a,
 444                                                struct tree *b)
 445 {
 446         struct stage_data *e = xcalloc(1, sizeof(struct stage_data));
 447         get_tree_entry(o->object.sha1, path,
 448                         e->stages[1].sha, &e->stages[1].mode);
 449         get_tree_entry(a->object.sha1, path,
 450                         e->stages[2].sha, &e->stages[2].mode);
 451         get_tree_entry(b->object.sha1, path,
 452                         e->stages[3].sha, &e->stages[3].mode);
 453         return e;
 454 }
 455
 456 static void free_index_entries(struct path_list **ents)
 457 {
 458         if (!*ents)
 459                 return;
 460
 461         path_list_clear(*ents, 1);
 462         free(*ents);
 463         *ents = NULL;
 464 }
 465
 466 /*
 467  * Create a dictionary mapping file names to CacheEntry objects. The
 468  * dictionary contains one entry for every path with a non-zero stage entry.
 469  */
 470 static struct path_list *get_unmerged()
 471 {
 472         struct path_list *unmerged = xcalloc(1, sizeof(struct path_list));
 473         int i;
 474
 475         unmerged->strdup_paths = 1;
 476         if (!cache_dirty) {
 477                 read_cache_from(getenv("GIT_INDEX_FILE"));
 478                 cache_dirty++;
 479         }
 480         for (i = 0; i < active_nr; i++) {
 481                 struct cache_entry *ce = active_cache[i];
 482                 if (!ce_stage(ce))
 483                         continue;
 484
 485                 struct stage_data *e = index_entry_get(unmerged, ce->name);
 486                 e->stages[ce_stage(ce)].mode = ntohl(ce->ce_mode);
 487                 memcpy(e->stages[ce_stage(ce)].sha, ce->sha1, 20);
 488         }
 489
 490         debug("  get_unmerged done\n");
 491         return unmerged;
 492 }
 493
 494 struct rename
 495 {
 496         struct diff_filepair *pair;
 497         struct stage_data *src_entry;
 498         struct stage_data *dst_entry;
 499         unsigned processed:1;
 500 };
 501
 502 static struct rename *find_rename_bysrc(struct path_list *e,
 503                                               const char *name)
 504 {
 505         struct path_list_item *item = path_list_lookup(name, e);
 506         if (item)
 507                 return item->util;
 508         return NULL;
 509 }
 510
 511 static void free_rename_entries(struct path_list **list)
 512 {
 513         if (!*list)
 514                 return;
 515
 516         path_list_clear(*list, 0);
 517         free(*list);
 518         *list = NULL;
 519 }
 520
 521 /*
 522  * Get information of all renames which occured between 'oTree' and
 523  * 'tree'. We need the three trees in the merge ('oTree', 'aTree' and
 524  * 'bTree') to be able to associate the correct cache entries with
 525  * the rename information. 'tree' is always equal to either aTree or bTree.
 526  */
 527 static struct path_list *get_renames(struct tree *tree,
 528                                         struct tree *oTree,
 529                                         struct tree *aTree,
 530                                         struct tree *bTree,
 531                                         struct path_list *entries)
 532 {
 533 #ifdef DEBUG
 534         time_t t = time(0);
 535         debug("getRenames ...\n");
 536 #endif
 537         int i;
 538         struct path_list *renames = xcalloc(1, sizeof(struct path_list));
 539         struct diff_options opts;
 540         diff_setup(&opts);
 541         opts.recursive = 1;
 542         opts.detect_rename = DIFF_DETECT_RENAME;
 543         opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 544         if (diff_setup_done(&opts) < 0)
 545                 die("diff setup failed");
 546         diff_tree_sha1(oTree->object.sha1, tree->object.sha1, "", &opts);
 547         diffcore_std(&opts);
 548         for (i = 0; i < diff_queued_diff.nr; ++i) {
 549                 struct rename *re;
 550                 struct diff_filepair *pair = diff_queued_diff.queue[i];
 551                 if (pair->status != 'R') {
 552                         diff_free_filepair(pair);
 553                         continue;
 554                 }
 555                 re = xmalloc(sizeof(*re));
 556                 re->processed = 0;
 557                 re->pair = pair;
 558                 re->src_entry = index_entry_find(entries, re->pair->one->path);
 559                 /* TODO: should it not be an error, if src_entry was found? */
 560                 if ( !re->src_entry ) {
 561                         re->src_entry = index_entry_from_db(re->pair->one->path,
 562                                         oTree, aTree, bTree);
 563                         struct path_list_item *item =
 564                                 path_list_insert(re->pair->one->path, entries);
 565                         item->util = re->src_entry;
 566                 }
 567                 re->dst_entry = index_entry_find(entries, re->pair->two->path);
 568                 if ( !re->dst_entry ) {
 569                         re->dst_entry = index_entry_from_db(re->pair->two->path,
 570                                         oTree, aTree, bTree);
 571                         struct path_list_item *item =
 572                                 path_list_insert(re->pair->two->path, entries);
 573                         item->util = re->dst_entry;
 574                 }
 575                 struct path_list_item *item = path_list_insert(pair->one->path, renames);
 576                 item->util = re;
 577         }
 578         opts.output_format = DIFF_FORMAT_NO_OUTPUT;
 579         diff_queued_diff.nr = 0;
 580         diff_flush(&opts);
 581         debug("  getRenames done in %ld\n", time(0)-t);
 582         return renames;
 583 }
 584
 585 /*
 586  * TODO: the code would be way nicer, if we had a struct containing just sha1 and mode.
 587  * In this particular case, we might get away reusing stage_data, no?
 588  */
 589 int update_stages(const char *path,
 590                    unsigned char *osha, unsigned omode,
 591                    unsigned char *asha, unsigned amode,
 592                    unsigned char *bsha, unsigned bmode,
 593                    int clear /* =True */)
 594 {
 595         int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE;
 596         if ( clear )
 597                 if (add_cacheinfo(0, null_sha1, path, 0, 0, options))
 598                         return -1;
 599         if ( omode )
 600                 if (add_cacheinfo(omode, osha, path, 1, 0, options))
 601                         return -1;
 602         if ( amode )
 603                 if (add_cacheinfo(omode, osha, path, 2, 0, options))
 604                         return -1;
 605         if ( bmode )
 606                 if (add_cacheinfo(omode, osha, path, 3, 0, options))
 607                         return -1;
 608         return 0;
 609 }
 610
 611 /*
 612  * TODO: there has to be a function in libgit doing this exact thing.
 613  */
 614 static int remove_path(const char *name)
 615 {
 616         int ret;
 617         char *slash;
 618
 619         ret = unlink(name);
 620         if ( ret )
 621                 return ret;
 622         int len = strlen(name);
 623         char *dirs = malloc(len+1);
 624         memcpy(dirs, name, len);
 625         dirs[len] = '\0';
 626         while ( (slash = strrchr(name, '/')) ) {
 627                 *slash = '\0';
 628                 len = slash - name;
 629                 if ( rmdir(name) != 0 )
 630                         break;
 631         }
 632         free(dirs);
 633         return ret;
 634 }
 635
 636 /* General TODO: unC99ify the code: no declaration after code */
 637 /* General TODO: no javaIfiCation: rename updateCache to update_cache */
 638 /*
 639  * TODO: once we no longer call external programs, we'd probably be better of
 640  * not setting / getting the environment variable GIT_INDEX_FILE all the time.
 641  */
 642 int remove_file(int clean, const char *path)
 643 {
 644         int updateCache = index_only || clean;
 645         int updateWd = !index_only;
 646
 647         if ( updateCache ) {
 648                 if (!cache_dirty)
 649                         read_cache_from(getenv("GIT_INDEX_FILE"));
 650                 cache_dirty++;
 651                 if (remove_file_from_cache(path))
 652                         return -1;
 653         }
 654         if ( updateWd )
 655         {
 656                 unlink(path);
 657                 if ( errno != ENOENT || errno != EISDIR )
 658                         return -1;
 659                 remove_path(path);
 660         }
 661         return 0;
 662 }
 663
 664 static char *unique_path(const char *path, const char *branch)
 665 {
 666         char *newpath = xmalloc(strlen(path) + 1 + strlen(branch) + 8 + 1);
 667         strcpy(newpath, path);
 668         strcat(newpath, "~");
 669         char *p = newpath + strlen(newpath);
 670         strcpy(p, branch);
 671         for ( ; *p; ++p )
 672                 if ( '/' == *p )
 673                         *p = '_';
 674         int suffix = 0;
 675         struct stat st;
 676         while ( path_list_has_path(&currentFileSet, newpath) ||
 677                 path_list_has_path(&currentDirectorySet, newpath) ||
 678                 lstat(newpath, &st) == 0 ) {
 679                 sprintf(p, "_%d", suffix++);
 680         }
 681         path_list_insert(newpath, &currentFileSet);
 682         return newpath;
 683 }
 684
 685 /*
 686  * TODO: except for create_last, this so looks like
 687  * safe_create_leading_directories().
 688  */
 689 static int mkdir_p(const char *path, unsigned long mode, int create_last)
 690 {
 691         char *buf = strdup(path);
 692         char *p;
 693
 694         for ( p = buf; *p; ++p ) {
 695                 if ( *p != '/' )
 696                         continue;
 697                 *p = '\0';
 698                 if (mkdir(buf, mode)) {
 699                         int e = errno;
 700                         if ( e == EEXIST ) {
 701                                 struct stat st;
 702                                 if ( !stat(buf, &st) && S_ISDIR(st.st_mode) )
 703                                         goto next; /* ok */
 704                                 errno = e;
 705                         }
 706                         free(buf);
 707                         return -1;
 708                 }
 709         next:
 710                 *p = '/';
 711         }
 712         free(buf);
 713         if ( create_last && mkdir(path, mode) )
 714                 return -1;
 715         return 0;
 716 }
 717
 718 static void flush_buffer(int fd, const char *buf, unsigned long size)
 719 {
 720         while (size > 0) {
 721                 long ret = xwrite(fd, buf, size);
 722                 if (ret < 0) {
 723                         /* Ignore epipe */
 724                         if (errno == EPIPE)
 725                                 break;
 726                         die("merge-recursive: %s", strerror(errno));
 727                 } else if (!ret) {
 728                         die("merge-recursive: disk full?");
 729                 }
 730                 size -= ret;
 731                 buf += ret;
 732         }
 733 }
 734
 735 /* General TODO: reindent according to guide lines (no if ( blabla )) */
 736 void update_file_flags(const unsigned char *sha,
 737                    unsigned mode,
 738                    const char *path,
 739                    int updateCache,
 740                    int updateWd)
 741 {
 742         if ( index_only )
 743                 updateWd = 0;
 744
 745         if ( updateWd ) {
 746                 char type[20];
 747                 void *buf;
 748                 unsigned long size;
 749
 750                 buf = read_sha1_file(sha, type, &size);
 751                 if (!buf)
 752                         die("cannot read object %s '%s'", sha1_to_hex(sha), path);
 753                 if ( strcmp(type, blob_type) != 0 )
 754                         die("blob expected for %s '%s'", sha1_to_hex(sha), path);
 755
 756                 if ( S_ISREG(mode) ) {
 757                         if ( mkdir_p(path, 0777, 0 /* don't create last element */) )
 758                                 die("failed to create path %s: %s", path, strerror(errno));
 759                         unlink(path);
 760                         if ( mode & 0100 )
 761                                 mode = 0777;
 762                         else
 763                                 mode = 0666;
 764                         int fd = open(path, O_WRONLY | O_TRUNC | O_CREAT, mode);
 765                         if ( fd < 0 )
 766                                 die("failed to open %s: %s", path, strerror(errno));
 767                         flush_buffer(fd, buf, size);
 768                         close(fd);
 769                 } else if ( S_ISLNK(mode) ) {
 770                         char *linkTarget = malloc(size + 1);
 771                         memcpy(linkTarget, buf, size);
 772                         linkTarget[size] = '\0';
 773                         mkdir_p(path, 0777, 0);
 774                         symlink(linkTarget, path);
 775                 } else
 776                         die("do not know what to do with %06o %s '%s'",
 777                             mode, sha1_to_hex(sha), path);
 778         }
 779         if ( updateCache )
 780                 add_cacheinfo(mode, sha, path, 0, updateWd, ADD_CACHE_OK_TO_ADD);
 781 }
 782
 783 /* TODO: is this often used? if not, do direct call */
 784 void update_file(int clean,
 785                 const unsigned char *sha,
 786                 unsigned mode,
 787                 const char *path)
 788 {
 789         update_file_flags(sha, mode, path, index_only || clean, !index_only);
 790 }
 791
 792 /* Low level file merging, update and removal */
 793
 794 struct merge_file_info
 795 {
 796         unsigned char sha[20];
 797         unsigned mode;
 798         unsigned clean:1,
 799                  merge:1;
 800 };
 801
 802 static char *git_unpack_file(const unsigned char *sha1, char *path)
 803 {
 804         void *buf;
 805         char type[20];
 806         unsigned long size;
 807         int fd;
 808
 809         buf = read_sha1_file(sha1, type, &size);
 810         if (!buf || strcmp(type, blob_type))
 811                 die("unable to read blob object %s", sha1_to_hex(sha1));
 812
 813         strcpy(path, ".merge_file_XXXXXX");
 814         fd = mkstemp(path);
 815         if (fd < 0)
 816                 die("unable to create temp-file");
 817         flush_buffer(fd, buf, size);
 818         close(fd);
 819         return path;
 820 }
 821
 822 /*
 823  * TODO: the signature would be much more efficient using stage_data
 824  */
 825 static struct merge_file_info merge_file(const char *oPath,
 826                                          const unsigned char *oSha,
 827                                          unsigned oMode,
 828                                          const char *aPath,
 829                                          const unsigned char *aSha,
 830                                          unsigned aMode,
 831                                          const char *bPath,
 832                                          const unsigned char *bSha,
 833                                          unsigned bMode,
 834                                          const char *branch1Name,
 835                                          const char *branch2Name)
 836 {
 837         struct merge_file_info result;
 838         result.merge = 0;
 839         result.clean = 1;
 840
 841         if ( (S_IFMT & aMode) != (S_IFMT & bMode) ) {
 842                 result.clean = 0;
 843                 if ( S_ISREG(aMode) ) {
 844                         result.mode = aMode;
 845                         memcpy(result.sha, aSha, 20);
 846                 } else {
 847                         result.mode = bMode;
 848                         memcpy(result.sha, bSha, 20);
 849                 }
 850         } else {
 851                 if ( memcmp(aSha, oSha, 20) != 0 && memcmp(bSha, oSha, 20) != 0 )
 852                         result.merge = 1;
 853
 854                 result.mode = aMode == oMode ? bMode: aMode;
 855
 856                 if ( memcmp(aSha, oSha, 20) == 0 )
 857                         memcpy(result.sha, bSha, 20);
 858                 else if ( memcmp(bSha, oSha, 20) == 0 )
 859                         memcpy(result.sha, aSha, 20);
 860                 else if ( S_ISREG(aMode) ) {
 861
 862                         int code = 1;
 863                         char orig[PATH_MAX];
 864                         char src1[PATH_MAX];
 865                         char src2[PATH_MAX];
 866
 867                         git_unpack_file(oSha, orig);
 868                         git_unpack_file(aSha, src1);
 869                         git_unpack_file(bSha, src2);
 870
 871                         const char *argv[] = {
 872                                 "merge", "-L", NULL, "-L", NULL, "-L", NULL,
 873                                 src1, orig, src2,
 874                                 NULL
 875                         };
 876                         char *la, *lb, *lo;
 877                         argv[2] = la = strdup(mkpath("%s/%s", branch1Name, aPath));
 878                         argv[6] = lb = strdup(mkpath("%s/%s", branch2Name, bPath));
 879                         argv[4] = lo = strdup(mkpath("orig/%s", oPath));
 880
 881 #if 0
 882                         printf("%s %s %s %s %s %s %s %s %s %s\n",
 883                                argv[0], argv[1], argv[2], argv[3], argv[4],
 884                                argv[5], argv[6], argv[7], argv[8], argv[9]);
 885 #endif
 886                         code = run_command_v(10, argv);
 887
 888                         free(la);
 889                         free(lb);
 890                         free(lo);
 891                         if ( code && code < -256 ) {
 892                                 die("Failed to execute 'merge'. merge(1) is used as the "
 893                                     "file-level merge tool. Is 'merge' in your path?");
 894                         }
 895                         struct stat st;
 896                         int fd = open(src1, O_RDONLY);
 897                         if (fd < 0 || fstat(fd, &st) < 0 ||
 898                                         index_fd(result.sha, fd, &st, 1,
 899                                                 "blob"))
 900                                 die("Unable to add %s to database", src1);
 901                         close(fd);
 902
 903                         unlink(orig);
 904                         unlink(src1);
 905                         unlink(src2);
 906
 907                         result.clean = WEXITSTATUS(code) == 0;
 908                 } else {
 909                         if ( !(S_ISLNK(aMode) || S_ISLNK(bMode)) )
 910                                 die("cannot merge modes?");
 911
 912                         memcpy(result.sha, aSha, 20);
 913
 914                         if ( memcmp(aSha, bSha, 20) != 0 )
 915                                 result.clean = 0;
 916                 }
 917         }
 918
 919         return result;
 920 }
 921
 922 static void conflict_rename_rename(struct rename *ren1,
 923                                    const char *branch1,
 924                                    struct rename *ren2,
 925                                    const char *branch2)
 926 {
 927         char *del[2];
 928         int delp = 0;
 929         const char *ren1_dst = ren1->pair->two->path;
 930         const char *ren2_dst = ren2->pair->two->path;
 931         const char *dstName1 = ren1_dst;
 932         const char *dstName2 = ren2_dst;
 933         if (path_list_has_path(&currentDirectorySet, ren1_dst)) {
 934                 dstName1 = del[delp++] = unique_path(ren1_dst, branch1);
 935                 output("%s is a directory in %s adding as %s instead",
 936                        ren1_dst, branch2, dstName1);
 937                 remove_file(0, ren1_dst);
 938         }
 939         if (path_list_has_path(&currentDirectorySet, ren2_dst)) {
 940                 dstName2 = del[delp++] = unique_path(ren2_dst, branch2);
 941                 output("%s is a directory in %s adding as %s instead",
 942                        ren2_dst, branch1, dstName2);
 943                 remove_file(0, ren2_dst);
 944         }
 945         update_stages(dstName1,
 946                       NULL, 0,
 947                       ren1->pair->two->sha1, ren1->pair->two->mode,
 948                       NULL, 0,
 949                       1 /* clear */);
 950         update_stages(dstName2,
 951                       NULL, 0,
 952                       NULL, 0,
 953                       ren2->pair->two->sha1, ren2->pair->two->mode,
 954                       1 /* clear */);
 955         while ( delp-- )
 956                 free(del[delp]);
 957 }
 958
 959 static void conflict_rename_dir(struct rename *ren1,
 960                                 const char *branch1)
 961 {
 962         char *newPath = unique_path(ren1->pair->two->path, branch1);
 963         output("Renaming %s to %s instead", ren1->pair->one->path, newPath);
 964         remove_file(0, ren1->pair->two->path);
 965         update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, newPath);
 966         free(newPath);
 967 }
 968
 969 static void conflict_rename_rename_2(struct rename *ren1,
 970                                      const char *branch1,
 971                                      struct rename *ren2,
 972                                      const char *branch2)
 973 {
 974         char *newPath1 = unique_path(ren1->pair->two->path, branch1);
 975         char *newPath2 = unique_path(ren2->pair->two->path, branch2);
 976         output("Renaming %s to %s and %s to %s instead",
 977                ren1->pair->one->path, newPath1,
 978                ren2->pair->one->path, newPath2);
 979         remove_file(0, ren1->pair->two->path);
 980         update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, newPath1);
 981         update_file(0, ren2->pair->two->sha1, ren2->pair->two->mode, newPath2);
 982         free(newPath2);
 983         free(newPath1);
 984 }
 985
 986 /* General TODO: get rid of all the debug messages */
 987 static int process_renames(struct path_list *renamesA,
 988                            struct path_list *renamesB,
 989                            const char *branchNameA,
 990                            const char *branchNameB)
 991 {
 992         int cleanMerge = 1, i;
 993         struct path_list srcNames = {NULL, 0, 0, 0}, byDstA = {NULL, 0, 0, 0}, byDstB = {NULL, 0, 0, 0};
 994         const struct rename *sre;
 995
 996         /*
 997          * TODO: think about a saner way to do this.
 998          * Since both renamesA and renamesB are sorted, it should
 999          * be much more efficient to traverse both simultaneously,
1000          * only byDstA and byDstB should be needed.
1001          */
1002         debug("processRenames...\n");
1003         for (i = 0; i < renamesA->nr; i++) {
1004                 sre = renamesA->items[i].util;
1005                 path_list_insert(sre->pair->one->path, &srcNames);
1006                 path_list_insert(sre->pair->two->path, &byDstA)->util
1007                         = sre->dst_entry;
1008         }
1009         for (i = 0; i < renamesB->nr; i++) {
1010                 sre = renamesB->items[i].util;
1011                 path_list_insert(sre->pair->one->path, &srcNames);
1012                 path_list_insert(sre->pair->two->path, &byDstB)->util
1013                         = sre->dst_entry;
1014         }
1015
1016         for (i = 0; i < srcNames.nr; i++) {
1017                 char *src = srcNames.items[i].path;
1018                 struct path_list *renames1, *renames2, *renames2Dst;
1019                 struct rename *ren1, *ren2;
1020                 const char *branchName1, *branchName2;
1021                 ren1 = find_rename_bysrc(renamesA, src);
1022                 ren2 = find_rename_bysrc(renamesB, src);
1023                 /* TODO: refactor, so that 1/2 are not needed */
1024                 if ( ren1 ) {
1025                         renames1 = renamesA;
1026                         renames2 = renamesB;
1027                         renames2Dst = &byDstB;
1028                         branchName1 = branchNameA;
1029                         branchName2 = branchNameB;
1030                 } else {
1031                         renames1 = renamesB;
1032                         renames2 = renamesA;
1033                         renames2Dst = &byDstA;
1034                         branchName1 = branchNameB;
1035                         branchName2 = branchNameA;
1036                         struct rename *tmp = ren2;
1037                         ren2 = ren1;
1038                         ren1 = tmp;
1039                 }
1040
1041                 ren1->dst_entry->processed = 1;
1042                 ren1->src_entry->processed = 1;
1043
1044                 if ( ren1->processed )
1045                         continue;
1046                 ren1->processed = 1;
1047
1048                 const char *ren1_src = ren1->pair->one->path;
1049                 const char *ren1_dst = ren1->pair->two->path;
1050
1051                 if ( ren2 ) {
1052                         const char *ren2_src = ren2->pair->one->path;
1053                         const char *ren2_dst = ren2->pair->two->path;
1054                         /* Renamed in 1 and renamed in 2 */
1055                         if (strcmp(ren1_src, ren2_src) != 0)
1056                                 die("ren1.src != ren2.src");
1057                         ren2->dst_entry->processed = 1;
1058                         ren2->processed = 1;
1059                         if (strcmp(ren1_dst, ren2_dst) != 0) {
1060                                 cleanMerge = 0;
1061                                 output("CONFLICT (rename/rename): "
1062                                        "Rename %s->%s in branch %s "
1063                                        "rename %s->%s in %s",
1064                                        src, ren1_dst, branchName1,
1065                                        src, ren2_dst, branchName2);
1066                                 conflict_rename_rename(ren1, branchName1, ren2, branchName2);
1067                         } else {
1068                                 remove_file(1, ren1_src);
1069                                 struct merge_file_info mfi;
1070                                 mfi = merge_file(ren1_src,
1071                                                  ren1->pair->one->sha1,
1072                                                  ren1->pair->one->mode,
1073                                                  ren1_dst,
1074                                                  ren1->pair->two->sha1,
1075                                                  ren1->pair->two->mode,
1076                                                  ren2_dst,
1077                                                  ren2->pair->two->sha1,
1078                                                  ren2->pair->two->mode,
1079                                                  branchName1,
1080                                                  branchName2);
1081                                 if ( mfi.merge || !mfi.clean )
1082                                         output("Renaming %s->%s", src, ren1_dst);
1083
1084                                 if ( mfi.merge )
1085                                         output("Auto-merging %s", ren1_dst);
1086
1087                                 if ( !mfi.clean ) {
1088                                         output("CONFLICT (content): merge conflict in %s",
1089                                                ren1_dst);
1090                                         cleanMerge = 0;
1091
1092                                         if ( !index_only )
1093                                                 update_stages(ren1_dst,
1094                                                               ren1->pair->one->sha1,
1095                                                               ren1->pair->one->mode,
1096                                                               ren1->pair->two->sha1,
1097                                                               ren1->pair->two->mode,
1098                                                               ren2->pair->two->sha1,
1099                                                               ren2->pair->two->mode,
1100                                                               1 /* clear */);
1101                                 }
1102                                 update_file(mfi.clean, mfi.sha, mfi.mode, ren1_dst);
1103                         }
1104                 } else {
1105                         /* Renamed in 1, maybe changed in 2 */
1106                         remove_file(1, ren1_src);
1107
1108                         unsigned char srcShaOtherBranch[20], dstShaOtherBranch[20];
1109                         unsigned srcModeOtherBranch, dstModeOtherBranch;
1110
1111                         int stage = renamesA == renames1 ? 3: 2;
1112
1113                         memcpy(srcShaOtherBranch, ren1->src_entry->stages[stage].sha, 20);
1114                         srcModeOtherBranch = ren1->src_entry->stages[stage].mode;
1115
1116                         memcpy(dstShaOtherBranch, ren1->dst_entry->stages[stage].sha, 20);
1117                         dstModeOtherBranch = ren1->dst_entry->stages[stage].mode;
1118
1119                         int tryMerge = 0;
1120                         char *newPath;
1121
1122                         if (path_list_has_path(&currentDirectorySet, ren1_dst)) {
1123                                 cleanMerge = 0;
1124                                 output("CONFLICT (rename/directory): Rename %s->%s in %s "
1125                                        " directory %s added in %s",
1126                                        ren1_src, ren1_dst, branchName1,
1127                                        ren1_dst, branchName2);
1128                                 conflict_rename_dir(ren1, branchName1);
1129                         } else if ( memcmp(srcShaOtherBranch, null_sha1, 20) == 0 ) {
1130                                 cleanMerge = 0;
1131                                 output("CONFLICT (rename/delete): Rename %s->%s in %s "
1132                                        "and deleted in %s",
1133                                        ren1_src, ren1_dst, branchName1,
1134                                        branchName2);
1135                                 update_file(0, ren1->pair->two->sha1, ren1->pair->two->mode, ren1_dst);
1136                         } else if ( memcmp(dstShaOtherBranch, null_sha1, 20) != 0 ) {
1137                                 cleanMerge = 0;
1138                                 tryMerge = 1;
1139                                 output("CONFLICT (rename/add): Rename %s->%s in %s. "
1140                                        "%s added in %s",
1141                                        ren1_src, ren1_dst, branchName1,
1142                                        ren1_dst, branchName2);
1143                                 newPath = unique_path(ren1_dst, branchName2);
1144                                 output("Adding as %s instead", newPath);
1145                                 update_file(0, dstShaOtherBranch, dstModeOtherBranch, newPath);
1146                         } else if ( (ren2 = find_rename_bysrc(renames2Dst, ren1_dst)) ) {
1147                                 cleanMerge = 0;
1148                                 ren2->processed = 1;
1149                                 output("CONFLICT (rename/rename): Rename %s->%s in %s. "
1150                                        "Rename %s->%s in %s",
1151                                        ren1_src, ren1_dst, branchName1,
1152                                        ren2->pair->one->path, ren2->pair->two->path, branchName2);
1153                                 conflict_rename_rename_2(ren1, branchName1, ren2, branchName2);
1154                         } else
1155                                 tryMerge = 1;
1156
1157                         if ( tryMerge ) {
1158                                 const char *oname = ren1_src;
1159                                 const char *aname = ren1_dst;
1160                                 const char *bname = ren1_src;
1161                                 unsigned char osha[20], asha[20], bsha[20];
1162                                 unsigned omode = ren1->pair->one->mode;
1163                                 unsigned amode = ren1->pair->two->mode;
1164                                 unsigned bmode = srcModeOtherBranch;
1165                                 memcpy(osha, ren1->pair->one->sha1, 20);
1166                                 memcpy(asha, ren1->pair->two->sha1, 20);
1167                                 memcpy(bsha, srcShaOtherBranch, 20);
1168                                 const char *aBranch = branchName1;
1169                                 const char *bBranch = branchName2;
1170
1171                                 if ( renamesA != renames1 ) {
1172                                         memswp(&aname, &bname, sizeof(aname));
1173                                         memswp(asha, bsha, 20);
1174                                         memswp(&aBranch, &bBranch, sizeof(aBranch));
1175                                 }
1176                                 struct merge_file_info mfi;
1177                                 mfi = merge_file(oname, osha, omode,
1178                                                  aname, asha, amode,
1179                                                  bname, bsha, bmode,
1180                                                  aBranch, bBranch);
1181
1182                                 if ( mfi.merge || !mfi.clean )
1183                                         output("Renaming %s => %s", ren1_src, ren1_dst);
1184                                 if ( mfi.merge )
1185                                         output("Auto-merging %s", ren1_dst);
1186                                 if ( !mfi.clean ) {
1187                                         output("CONFLICT (rename/modify): Merge conflict in %s",
1188                                                ren1_dst);
1189                                         cleanMerge = 0;
1190
1191                                         if ( !index_only )
1192                                                 update_stages(ren1_dst,
1193                                                               osha, omode,
1194                                                               asha, amode,
1195                                                               bsha, bmode,
1196                                                               1 /* clear */);
1197                                 }
1198                                 update_file(mfi.clean, mfi.sha, mfi.mode, ren1_dst);
1199                         }
1200                 }
1201         }
1202         path_list_clear(&srcNames, 0);
1203         debug("  processRenames done\n");
1204
1205         if (cache_dirty)
1206                 flush_cache();
1207         return cleanMerge;
1208 }
1209
1210 static unsigned char *has_sha(const unsigned char *sha)
1211 {
1212         return memcmp(sha, null_sha1, 20) == 0 ? NULL: (unsigned char *)sha;
1213 }
1214
1215 /* Per entry merge function */
1216 static int process_entry(const char *path, struct stage_data *entry,
1217                          const char *branch1Name,
1218                          const char *branch2Name)
1219 {
1220         /*
1221         printf("processing entry, clean cache: %s\n", index_only ? "yes": "no");
1222         print_index_entry("\tpath: ", entry);
1223         */
1224         int cleanMerge = 1;
1225         unsigned char *oSha = has_sha(entry->stages[1].sha);
1226         unsigned char *aSha = has_sha(entry->stages[2].sha);
1227         unsigned char *bSha = has_sha(entry->stages[3].sha);
1228         unsigned oMode = entry->stages[1].mode;
1229         unsigned aMode = entry->stages[2].mode;
1230         unsigned bMode = entry->stages[3].mode;
1231
1232         if ( oSha && (!aSha || !bSha) ) {
1233                 /* Case A: Deleted in one */
1234                 if ( (!aSha && !bSha) ||
1235                      (sha_eq(aSha, oSha) && !bSha) ||
1236                      (!aSha && sha_eq(bSha, oSha)) ) {
1237                         /* Deleted in both or deleted in one and
1238                          * unchanged in the other */
1239                         if ( aSha )
1240                                 output("Removing %s", path);
1241                         remove_file(1, path);
1242                 } else {
1243                         /* Deleted in one and changed in the other */
1244                         cleanMerge = 0;
1245                         if ( !aSha ) {
1246                                 output("CONFLICT (delete/modify): %s deleted in %s "
1247                                        "and modified in %s. Version %s of %s left in tree.",
1248                                        path, branch1Name,
1249                                        branch2Name, branch2Name, path);
1250                                 update_file(0, bSha, bMode, path);
1251                         } else {
1252                                 output("CONFLICT (delete/modify): %s deleted in %s "
1253                                        "and modified in %s. Version %s of %s left in tree.",
1254                                        path, branch2Name,
1255                                        branch1Name, branch1Name, path);
1256                                 update_file(0, aSha, aMode, path);
1257                         }
1258                 }
1259
1260         } else if ( (!oSha && aSha && !bSha) ||
1261                     (!oSha && !aSha && bSha) ) {
1262                 /* Case B: Added in one. */
1263                 const char *addBranch;
1264                 const char *otherBranch;
1265                 unsigned mode;
1266                 const unsigned char *sha;
1267                 const char *conf;
1268
1269                 if ( aSha ) {
1270                         addBranch = branch1Name;
1271                         otherBranch = branch2Name;
1272                         mode = aMode;
1273                         sha = aSha;
1274                         conf = "file/directory";
1275                 } else {
1276                         addBranch = branch2Name;
1277                         otherBranch = branch1Name;
1278                         mode = bMode;
1279                         sha = bSha;
1280                         conf = "directory/file";
1281                 }
1282                 if ( path_list_has_path(&currentDirectorySet, path) ) {
1283                         cleanMerge = 0;
1284                         const char *newPath = unique_path(path, addBranch);
1285                         output("CONFLICT (%s): There is a directory with name %s in %s. "
1286                                "Adding %s as %s",
1287                                conf, path, otherBranch, path, newPath);
1288                         remove_file(0, path);
1289                         update_file(0, sha, mode, newPath);
1290                 } else {
1291                         output("Adding %s", path);
1292                         update_file(1, sha, mode, path);
1293                 }
1294         } else if ( !oSha && aSha && bSha ) {
1295                 /* Case C: Added in both (check for same permissions). */
1296                 if ( sha_eq(aSha, bSha) ) {
1297                         if ( aMode != bMode ) {
1298                                 cleanMerge = 0;
1299                                 output("CONFLICT: File %s added identically in both branches, "
1300                                        "but permissions conflict %06o->%06o",
1301                                        path, aMode, bMode);
1302                                 output("CONFLICT: adding with permission: %06o", aMode);
1303                                 update_file(0, aSha, aMode, path);
1304                         } else {
1305                                 /* This case is handled by git-read-tree */
1306                                 assert(0 && "This case must be handled by git-read-tree");
1307                         }
1308                 } else {
1309                         cleanMerge = 0;
1310                         const char *newPath1 = unique_path(path, branch1Name);
1311                         const char *newPath2 = unique_path(path, branch2Name);
1312                         output("CONFLICT (add/add): File %s added non-identically "
1313                                "in both branches. Adding as %s and %s instead.",
1314                                path, newPath1, newPath2);
1315                         remove_file(0, path);
1316                         update_file(0, aSha, aMode, newPath1);
1317                         update_file(0, bSha, bMode, newPath2);
1318                 }
1319
1320         } else if ( oSha && aSha && bSha ) {
1321                 /* case D: Modified in both, but differently. */
1322                 output("Auto-merging %s", path);
1323                 struct merge_file_info mfi;
1324                 mfi = merge_file(path, oSha, oMode,
1325                                  path, aSha, aMode,
1326                                  path, bSha, bMode,
1327                                  branch1Name, branch2Name);
1328
1329                 if ( mfi.clean )
1330                         update_file(1, mfi.sha, mfi.mode, path);
1331                 else {
1332                         cleanMerge = 0;
1333                         output("CONFLICT (content): Merge conflict in %s", path);
1334
1335                         if ( index_only )
1336                                 update_file(0, mfi.sha, mfi.mode, path);
1337                         else
1338                                 update_file_flags(mfi.sha, mfi.mode, path,
1339                                               0 /* updateCache */, 1 /* updateWd */);
1340                 }
1341         } else
1342                 die("Fatal merge failure, shouldn't happen.");
1343
1344         if (cache_dirty)
1345                 flush_cache();
1346
1347         return cleanMerge;
1348 }
1349
1350 static struct merge_tree_result merge_trees(struct tree *head,
1351                                             struct tree *merge,
1352                                             struct tree *common,
1353                                             const char *branch1Name,
1354                                             const char *branch2Name)
1355 {
1356         int code;
1357         struct merge_tree_result result = { NULL, 0 };
1358         if ( !memcmp(common->object.sha1, merge->object.sha1, 20) ) {
1359                 output("Already uptodate!");
1360                 result.tree = head;
1361                 result.clean = 1;
1362                 return result;
1363         }
1364
1365         debug("merge_trees ...\n");
1366         code = git_merge_trees(index_only ? "-i": "-u", common, head, merge);
1367
1368         if ( code != 0 )
1369                 die("merging of trees %s and %s failed",
1370                     sha1_to_hex(head->object.sha1),
1371                     sha1_to_hex(merge->object.sha1));
1372
1373         result.tree = git_write_tree();
1374
1375         if ( !result.tree ) {
1376                 path_list_clear(&currentFileSet, 1);
1377                 path_list_clear(&currentDirectorySet, 1);
1378                 get_files_dirs(head, &currentFileSet, &currentDirectorySet);
1379                 get_files_dirs(merge, &currentFileSet, &currentDirectorySet);
1380
1381                 struct path_list *entries = get_unmerged();
1382                 struct path_list *re_head, *re_merge;
1383                 re_head  = get_renames(head, common, head, merge, entries);
1384                 re_merge = get_renames(merge, common, head, merge, entries);
1385                 result.clean = process_renames(re_head, re_merge,
1386                                                branch1Name, branch2Name);
1387                 debug("\tprocessing entries...\n");
1388                 int i;
1389                 for (i = 0; i < entries->nr; i++) {
1390                         const char *path = entries->items[i].path;
1391                         struct stage_data *e = entries->items[i].util;
1392                         if (e->processed)
1393                                 continue;
1394                         if (!process_entry(path, e, branch1Name, branch2Name))
1395                                 result.clean = 0;
1396                 }
1397
1398                 free_rename_entries(&re_merge);
1399                 free_rename_entries(&re_head);
1400                 free_index_entries(&entries);
1401
1402                 if (result.clean || index_only)
1403                         result.tree = git_write_tree();
1404                 else
1405                         result.tree = NULL;
1406                 debug("\t  processing entries done\n");
1407         } else {
1408                 result.clean = 1;
1409                 printf("merging of trees %s and %s resulted in %s\n",
1410                        sha1_to_hex(head->object.sha1),
1411                        sha1_to_hex(merge->object.sha1),
1412                        sha1_to_hex(result.tree->object.sha1));
1413         }
1414
1415         debug("  merge_trees done\n");
1416         return result;
1417 }
1418
1419 /*
1420  * Merge the commits h1 and h2, return the resulting virtual
1421  * commit object and a flag indicating the cleaness of the merge.
1422  */
1423 static
1424 struct merge_result merge(struct commit *h1,
1425                           struct commit *h2,
1426                           const char *branch1Name,
1427                           const char *branch2Name,
1428                           int callDepth /* =0 */,
1429                           struct commit *ancestor /* =None */)
1430 {
1431         struct merge_result result = { NULL, 0 };
1432         const char *msg;
1433         int msglen;
1434         struct commit_list *ca = NULL, *iter;
1435         struct commit *mergedCA;
1436         struct merge_tree_result mtr;
1437
1438         output("Merging:");
1439         msg = commit_title(h1, &msglen);
1440         /* TODO: refactor. we always show the sha1 with the title */
1441         output("%s %.*s", commit_hex_sha1(h1), msglen, msg);
1442         msg = commit_title(h2, &msglen);
1443         output("%s %.*s", commit_hex_sha1(h2), msglen, msg);
1444
1445         if ( ancestor )
1446                 commit_list_insert(ancestor, &ca);
1447         else
1448                 ca = get_merge_bases(h1, h2, 1);
1449
1450         output("found %u common ancestor(s):", commit_list_count(ca));
1451         for (iter = ca; iter; iter = iter->next) {
1452                 msg = commit_title(iter->item, &msglen);
1453                 output("%s %.*s", commit_hex_sha1(iter->item), msglen, msg);
1454         }
1455
1456         mergedCA = pop_commit(&ca);
1457
1458         /* TODO: what happens when merge with virtual commits fails? */
1459         for (iter = ca; iter; iter = iter->next) {
1460                 output_indent = callDepth + 1;
1461                 result = merge(mergedCA, iter->item,
1462                                "Temporary merge branch 1",
1463                                "Temporary merge branch 2",
1464                                callDepth + 1,
1465                                NULL);
1466                 mergedCA = result.commit;
1467                 output_indent = callDepth;
1468
1469                 if ( !mergedCA )
1470                         die("merge returned no commit");
1471         }
1472
1473         if ( callDepth == 0 ) {
1474                 setup_index(0);
1475                 index_only = 0;
1476         } else {
1477                 setup_index(1);
1478                 git_read_tree(h1->tree);
1479                 index_only = 1;
1480         }
1481
1482         mtr = merge_trees(h1->tree, h2->tree,
1483                           mergedCA->tree, branch1Name, branch2Name);
1484
1485         if ( !ancestor && (mtr.clean || index_only) ) {
1486                 result.commit = make_virtual_commit(mtr.tree, "merged tree");
1487                 commit_list_insert(h1, &result.commit->parents);
1488                 commit_list_insert(h2, &result.commit->parents->next);
1489         } else
1490                 result.commit = NULL;
1491
1492         result.clean = mtr.clean;
1493         return result;
1494 }
1495
1496 static struct commit *get_ref(const char *ref)
1497 {
1498         unsigned char sha1[20];
1499         struct object *object;
1500
1501         if (get_sha1(ref, sha1))
1502                 die("Could not resolve ref '%s'", ref);
1503         object = deref_tag(parse_object(sha1), ref, strlen(ref));
1504         if (object->type != TYPE_COMMIT)
1505                 return NULL;
1506         if (parse_commit((struct commit *)object))
1507                 die("Could not parse commit '%s'", sha1_to_hex(object->sha1));
1508         return (struct commit *)object;
1509 }
1510
1511 int main(int argc, char *argv[])
1512 {
1513         static const char *bases[2];
1514         static unsigned bases_count = 0;
1515
1516         original_index_file = getenv("GIT_INDEX_FILE");
1517
1518         if (!original_index_file)
1519                 original_index_file = strdup(git_path("index"));
1520
1521         temporary_index_file = strdup(git_path("mrg-rcrsv-tmp-idx"));
1522
1523         if (argc < 4)
1524                 die("Usage: %s <base>... -- <head> <remote> ...\n", argv[0]);
1525
1526         int i;
1527         for (i = 1; i < argc; ++i) {
1528                 if (!strcmp(argv[i], "--"))
1529                         break;
1530                 if (bases_count < sizeof(bases)/sizeof(*bases))
1531                         bases[bases_count++] = argv[i];
1532         }
1533         if (argc - i != 3) /* "--" "<head>" "<remote>" */
1534                 die("Not handling anything other than two heads merge.");
1535
1536         const char *branch1, *branch2;
1537
1538         branch1 = argv[++i];
1539         branch2 = argv[++i];
1540         printf("Merging %s with %s\n", branch1, branch2);
1541
1542         struct merge_result result;
1543         struct commit *h1 = get_ref(branch1);
1544         struct commit *h2 = get_ref(branch2);
1545
1546         if (bases_count == 1) {
1547                 struct commit *ancestor = get_ref(bases[0]);
1548                 result = merge(h1, h2, branch1, branch2, 0, ancestor);
1549         } else
1550                 result = merge(h1, h2, branch1, branch2, 0, NULL);
1551
1552         if (cache_dirty)
1553                 flush_cache();
1554
1555         return result.clean ? 0: 1;
1556 }
1557
1558 /*
1559 vim: sw=8 noet
1560 */