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